octreelocalizer.h

Go to the documentation of this file.

/*
 *
 *                 #####    #####   ######  ######  ###   ###
 *               ##   ##  ##   ##  ##      ##      ## ### ##
 *              ##   ##  ##   ##  ####    ####    ##  #  ##
 *             ##   ##  ##   ##  ##      ##      ##     ##
 *            ##   ##  ##   ##  ##      ##      ##     ##
 *            #####    #####   ##      ######  ##     ##
 *
 *
 *             OOFEM : Object Oriented Finite Element Code
 *
 *               Copyright (C) 1993 - 2025   Borek Patzak
 *
 *
 *
 *       Czech Technical University, Faculty of Civil Engineering,
 *   Department of Structural Mechanics, 166 29 Prague, Czech Republic
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Lesser General Public
 *  License as published by the Free Software Foundation; either
 *  version 2.1 of the License, or (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *  Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public
 *  License along with this library; if not, write to the Free Software
 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
 */
 
#ifndef octreelocalizer_h
#define octreelocalizer_h
 
#include "oofemenv.h"
#include "spatiallocalizer.h"
#include "floatarray.h"
#include "intarray.h"
 
#include <set>
#include <list>
#include <vector>
#include <memory>
 
#ifdef _OPENMP
#include <omp.h>
#endif
 
namespace oofem {
class Domain;
class Element;
class TimeStep;
class OctreeSpatialLocalizer;
#define OCTREE_MAX_NODES_LIMIT 10
#define OCTREE_MAX_DEPTH 15
 

class OOFEM_NO_EXPORT OctantRec
{
protected:
    OctantRec *parent;
    std::unique_ptr<OctantRec> child [ 2 ] [ 2 ] [ 2 ];
    //std::unique_ptr<OctantRec[2][2][2]> child2;
    FloatArray origin;
    double halfWidth;
    int depth;

    std :: list< int > nodeList;
    IntArray elementIPList;
    std :: vector< std :: list< int > >elementList;
 
 
public:
    enum BoundingBoxStatus { BBS_OutsideCell, BBS_InsideCell, BBS_ContainsCell };
    enum ChildStatus { CS_ChildFound, CS_NoChild };

    OctantRec(OctantRec * parent, FloatArray origin, double halfWidth);
    ~OctantRec() {}

    OctantRec *giveParent() { return this->parent; }
    const FloatArray & giveOrigin() { return this->origin; }
    double giveWidth() { return 2. * this->halfWidth; }
    int giveCellDepth() { return this->depth; }
    OctantRec *giveChild(int xi, int yi, int zi);
    ChildStatus giveChildContainingPoint(OctantRec *&child, const FloatArray &coords, const IntArray &mask);
    bool isTerminalOctant();
    std :: list< int > &giveNodeList();
    IntArray &giveIPElementList();
    std :: list< int > &giveElementList(int region);

    void divideLocally(int level, const IntArray &octantMask);
    BoundingBoxStatus testBoundingBox(const FloatArray &coords, double radius, const IntArray &mask);
    void addElementIP(int elementNum) { this->giveIPElementList().insertSortedOnce(elementNum); }
    void addElement(int region, int elementNum) { this->giveElementList(region).push_back(elementNum); }
    void addNode(int nodeNum) { this->giveNodeList().push_back(nodeNum); }
    void deleteNodeList() {
        nodeList.clear();
    }

    void printYourself();
    std :: string errorInfo(const char *func) const { return std :: string("OctantRec") + func; }
};
 

class OOFEM_EXPORT OctreeSpatialLocalizer : public SpatialLocalizer
{
protected:
    std::unique_ptr<OctantRec> rootCell;
    IntArray octreeMask;
    bool elementIPListsInitialized;
    IntArray elementListsInitialized;
    bool initialized;
#ifdef _OPENMP
    omp_lock_t initLock;
    omp_lock_t buildOctreeDataStructureLock;
    omp_lock_t ElementIPDataStructureLock;
#endif
public:
    OctreeSpatialLocalizer(Domain * d);
    virtual ~OctreeSpatialLocalizer() {}

    int giveOctreeMaskValue(int indx) { return octreeMask.at(indx); }

    int init(bool force = false) override;
 
    Element *giveElementContainingPoint(const FloatArray &coords, const IntArray *regionList = nullptr) override;
    Element *giveElementContainingPoint(const FloatArray &coords, const Set &eset) override;
    Element *giveElementClosestToPoint(FloatArray &lcoords, FloatArray &closest, const FloatArray &gcoords, int region) override;
 
    GaussPoint *giveClosestIP(const FloatArray &coords, int region, bool iCohesiveZoneGP = false) override;
    GaussPoint *giveClosestIP(const FloatArray &coords, Set &elemSet, bool iCohesiveZoneGP = false) override;
 
    void giveAllElementsWithIpWithinBox_EvenIfEmpty(elementContainerType &elemSet, const FloatArray &coords, const double radius) override { giveAllElementsWithIpWithinBox_EvenIfEmpty(elemSet, coords, radius, false); }
    void giveAllElementsWithIpWithinBox(elementContainerType &elemSet, const FloatArray &coords, const double radius) override { giveAllElementsWithIpWithinBox(elemSet, coords, radius, false); }
    void giveAllElementsWithIpWithinBox_EvenIfEmpty(elementContainerType &elemSet, const FloatArray &coords, const double radius, bool iCohesiveZoneGP);
    void giveAllElementsWithIpWithinBox(elementContainerType &elemSet, const FloatArray &coords, const double radius, bool iCohesiveZoneGP);
 
    void giveAllNodesWithinBox(nodeContainerType &nodeList, const FloatArray &coords, const double radius) override;
    Node * giveNodeClosestToPoint(const FloatArray &coords, double maxDist) override;
 
    const char *giveClassName() const override { return "OctreeSpatialLocalizer"; }
 
protected:
    bool buildOctreeDataStructure();
    void initElementIPDataStructure();
    void initElementDataStructure(int region = 0);
    OctantRec *findTerminalContaining(OctantRec &startCell, const FloatArray &coords);
    void insertNodeIntoOctree(OctantRec &rootCell, int nodeNum, const FloatArray &coords);
    void insertIPElementIntoOctree(OctantRec &rootCell, int elemNum, const FloatArray &coords);
    void insertElementIntoOctree(OctantRec &rootCell, int region, int elemNum, const FloatArray &b0, const FloatArray &b1);
    void insertElementsUsingNodalConnectivitiesIntoOctree(OctantRec &rootCell);
    void giveElementsWithIPWithinBox(elementContainerType &elemSet, OctantRec &currentCell,
                                     const FloatArray &coords, const double radius, bool iCohesiveZoneGP = false);
    void giveNodesWithinBox(nodeContainerType &nodeList, OctantRec &currentCell,
                            const FloatArray &coords, const double radius);

    void giveClosestIPWithinOctant(OctantRec &currentCell, //elementContainerType& visitedElems,
                                   const FloatArray &coords,
                                   int region, double &dist, GaussPoint *&answer, bool iCohesiveZoneGP);
    void giveClosestIPWithinOctant(OctantRec &currentCell, //elementContainerType& visitedElems,
                                   const FloatArray &coords,
                                   Set &elemSet, double &dist, GaussPoint *&answer, bool iCohesiveZoneGP);
    Element *giveElementContainingPoint(OctantRec &cell, const FloatArray &coords,
                                        OctantRec *scannedChild = nullptr, const IntArray *regionList = nullptr);
    Element *giveElementContainingPoint(OctantRec &cell, const FloatArray &coords,
                                        OctantRec *scannedChild = nullptr, const Set *elset = nullptr);
    void giveElementClosestToPointWithinOctant(OctantRec &currCell, const FloatArray &gcoords,
                                               double &minDist, FloatArray &lcoords, FloatArray &closest, Element * &answer, int region);
    void giveNodeClosestToPointWithinOctant(OctantRec &cell, const FloatArray &gcoords, double &minDist, Node * &answer);
    int giveMaxTreeDepthFrom(OctantRec &root);
    void giveListOfTerminalCellsInBoundingBox(std :: list< OctantRec * > &cellList, const FloatArray &coords,
                                              const double radius, double innerRadius, OctantRec &currentCell);
};
} // end namespace oofem
#endif // octreelocalizer_h