From: nge Date: Mon, 22 Jan 2007 15:14:44 +0000 (+0000) Subject: PAL 14158 Add the Octree and OctreeNode classes to accelerate detection of close... X-Git-Tag: V4_1_2rc1~33 X-Git-Url: http://git.salome-platform.org/gitweb/?p=modules%2Fsmesh.git;a=commitdiff_plain;h=984c4ffdd7df62aeaedc544cd0b8e64ff8f53f1a PAL 14158 Add the Octree and OctreeNode classes to accelerate detection of close nodes. Octree is virtual pure, OctreeNode inherites from Octree. --- diff --git a/src/SMESH/SMESH_Octree.cxx b/src/SMESH/SMESH_Octree.cxx new file mode 100644 index 000000000..5b224ae5d --- /dev/null +++ b/src/SMESH/SMESH_Octree.cxx @@ -0,0 +1,181 @@ +// SMESH SMESH_Octree : global Octree implementation +// +// Copyright (C) 2003 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN, +// CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS +// +// 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. +// +// This library 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA +// +// See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com +// +// +// +// File : SMESH_Octree.cxx +// Created : Tue Jan 16 16:00:00 2007 +// Author : Nicolas Geimer & Aurélien Motteux(OCC) +// Module : SMESH + +#include "SMESH_Octree.hxx" + +//=========================================================================== +/*! + * \brief SMESH_Octree Constructor + * \param maxLevel - The level max the octree can reach (If <0 unlimited) + */ +//=========================================================================== +SMESH_Octree::SMESH_Octree (const int maxLevel, const double minBoxSize): + myFather(NULL), + myLevel(0), + myMaxLevel(maxLevel), + myMinBoxSize(minBoxSize), + myIsLeaf(-1) +{ + myBox = new Bnd_B3d(); +} + +//====================================== +/*! + * \brief SMESH_Octree Destructor + */ +//====================================== +SMESH_Octree::~SMESH_Octree () +{ + if(myChildren != NULL) + { + if(!myIsLeaf) + { + for(int i = 0; i<8; i++) + delete myChildren[i]; + delete[] myChildren ; + } + } + delete myBox; +} + +//=========================================================================== +/*! + * \brief Set the bounding box of the Octree + * \param box - 3d Bounding Box of the Octree + */ +//=========================================================================== +void SMESH_Octree::setBox(const Bnd_B3d* box) +{ + delete myBox; + myBox=new Bnd_B3d(*box); +} + +//=========================================================================== +/*! + * \brief Set box to the 3d Bounding Box of the Octree + * \param box - Set box to the 3d Bounding Box of the Octree + */ +//=========================================================================== +void SMESH_Octree::getBox(Bnd_B3d* box) +{ + if(box != NULL) + delete box; + box = new Bnd_B3d (*myBox); +} + +//=========================================================================== +/*! + * \brief Set the max level of the Octree + * \param maxLevel - The level max the octree can reach (If <0 unlimited) + */ +//=========================================================================== +void SMESH_Octree::setMaxLevel(const int maxLevel) +{myMaxLevel = maxLevel;} + + +//=========================================================================== +/*! + * \brief Compute the bigger dimension of the box + * \param box - 3d Box + * \retval double - bigger dimension of the box + */ +//=========================================================================== +double SMESH_Octree::maxSize(const Bnd_B3d* box) +{ + if(box ==NULL) + return 0; + gp_XYZ min = box->CornerMin(); + gp_XYZ max = box->CornerMax(); + gp_XYZ Size = (max - min); + double returnVal = (Size.X()>Size.Y())?Size.X():Size.Y(); + return (returnVal>Size.Z())?returnVal:Size.Z(); +} + +//============================= +/*! + * \brief Compute the Octree + */ +//============================= +void SMESH_Octree::Compute() +{ + // As soon as the Octree is a Leaf, I stop building his children + if(!isLeaf()) + buildChildren(); +} + +//================================================================= +/*! + * \brief Build the 8 children boxes and call buildChildrenData() + */ +//================================================================= +void SMESH_Octree::buildChildren() +{ + myChildren = new (SMESH_Octree*)[8]; + + gp_XYZ min = myBox->CornerMin(); + gp_XYZ max = myBox->CornerMax(); + gp_XYZ HSize = (max - min)/2.; + gp_XYZ mid = min + HSize; + gp_XYZ childHsize = HSize/2.; + + Standard_Real XminChild, YminChild, ZminChild; + Bnd_B3d* box; + gp_XYZ minChild; + for (int i =0; i<8; i++) + { + // We build the eight boxes, we need 2 points to do that. + // Min, and Mid + // In binary, we can write i from 0 to 7 + // For instance : + // 5 is 101, it corresponds here in coordinates to ZYX + // If coordinate is 0 in Y-> box from Ymin to Ymid + // If coordinate is 1 in Y-> box from Ymid to Ymax + // Same scheme for X and Z + // I need the minChild to build the Bnd_B3d box. + + XminChild= (i%2==0)?min.X():mid.X(); + YminChild= ((i%4)/2==0)?min.Y():mid.Y(); + ZminChild= (i<4)?min.Z():mid.Z(); + minChild.SetCoord(XminChild, YminChild, ZminChild); + + box = new Bnd_B3d(minChild+childHsize,childHsize); + // The child is of the same type than its father (For instance, a SMESH_OctreeNode) + // We allocate the memory we need fot the child + myChildren[i] = allocateOctreeChild(); + // and we assign to him its box. + myChildren[i]->setBox(box); + delete box; + } + + // After building the 8 boxes, we put the data into the children.. + buildChildrenData(); + + //After we pass to the next level of the Octree + for (int i =0; i<8; i++) + myChildren[i]->Compute(); +} diff --git a/src/SMESH/SMESH_Octree.hxx b/src/SMESH/SMESH_Octree.hxx new file mode 100644 index 000000000..d9615b8dd --- /dev/null +++ b/src/SMESH/SMESH_Octree.hxx @@ -0,0 +1,97 @@ +// SMESH SMESH_Octree : global Octree implementation +// +// Copyright (C) 2003 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN, +// CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS +// +// 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. +// +// This library 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA +// +// See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com +// +// +// +// File : SMESH_Octree.hxx +// Created : Tue Jan 16 16:00:00 2007 +// Author : Nicolas Geimer & Aurélien Motteux (OCC) +// Module : SMESH + +#ifndef _SMESH_OCTREE_HXX_ +#define _SMESH_OCTREE_HXX_ + +#include + +class SMESH_Octree { + +public: + // Constructor + SMESH_Octree (const int maxLevel = -1, const double minBoxSize = 0.); + + // Destructor + virtual ~SMESH_Octree (); + + // Tell if Octree is a leaf or not (has to be implemented in inherited classes) + virtual const bool isLeaf() = 0; + + // Compute the Octree + void Compute(); + + // Set the maximal level of the Octree + void setMaxLevel(const int maxLevel); + + // Set the minimal size of the Box + void setMinBoxSize(const double minBoxSize){myMinBoxSize = minBoxSize;}; + + // Set the bounding box of the Octree + void setBox(const Bnd_B3d* box); + + // Set box to the 3d Bounding Box of the Octree + void getBox(Bnd_B3d* box); + + // Compute the bigger dimension of the box + static double maxSize(const Bnd_B3d* box); + +protected: + // Constructor for children (has to be implemented in inherited classes) + virtual SMESH_Octree* allocateOctreeChild() = 0; + + // Build the 8 children boxes + void buildChildren(); + + // Build the data in the 8 children (has to be implemented in inherited classes) + virtual void buildChildrenData() = 0; + + // members + + // Box of the Octree + Bnd_B3d* myBox; + + // Array of 8 Octree children + SMESH_Octree** myChildren; + + // Point the father, set to NULL for the level 0 + SMESH_Octree* myFather; + + // Level of the Octree + int myLevel; + + // MaxLevel of the Octree + int myMaxLevel; + + // Minimal size of the Box + double myMinBoxSize; + + // Tell us if the Octree is a leaf or not (-1 if not initialized) + int myIsLeaf; +}; +#endif diff --git a/src/SMESH/SMESH_OctreeNode.cxx b/src/SMESH/SMESH_OctreeNode.cxx new file mode 100644 index 000000000..52f1e3071 --- /dev/null +++ b/src/SMESH/SMESH_OctreeNode.cxx @@ -0,0 +1,327 @@ +// SMESH SMESH_OctreeNode : Octree with Nodes set +// inherites global class SMESH_Octree +// +// Copyright (C) 2003 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN, +// CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS +// +// 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. +// +// This library 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA +// +// See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com +// +// +// +// File : SMESH_OctreeNode.cxx +// Created : Tue Jan 16 16:00:00 2007 +// Author : Nicolas Geimer & Aurélien Motteux (OCC) +// Module : SMESH + +#include "SMESH_OctreeNode.hxx" +#include +#include + +using namespace std; + +//=============================================================== +/*! + * \brief Constructor : Build all the Octree using Compute() + * \param theNodes - Set of nodes, the Octree is built from this nodes + * \param maxLevel - Maximum level for the leaves + * \param maxNbNodes - Maximum number of nodes, a leaf can contain + * \param minBoxSize - Minimal size of the Octree Box + */ +//================================================================ +SMESH_OctreeNode::SMESH_OctreeNode (set theNodes, const int maxLevel, + const int maxNbNodes , const double minBoxSize ) + :SMESH_Octree(maxLevel,minBoxSize), + myMaxNbNodes(maxNbNodes), + myNodes(theNodes) +{ + // We need to compute the first bounding box via a special method + computeBoxForFather(); + myNbNodes = myNodes.size(); + myIsLeaf = (myLevel == myMaxLevel)||(myNbNodes<=myMaxNbNodes)||(myMinBoxSize>=maxSize(myBox)); + // All the children (Boxes and Data) are computed in Compute() + Compute(); +} + +//================================================================================== +/*! + * \brief Construct an empty SMESH_OctreeNode used by SMESH_Octree::buildChildren() + */ +//================================================================================== +SMESH_Octree* SMESH_OctreeNode::allocateOctreeChild() +{ + SMESH_OctreeNode * theOctree = new SMESH_OctreeNode(); + theOctree->myFather = this; + theOctree->myLevel = myLevel + 1; + theOctree->myMaxLevel = myMaxLevel; + theOctree->myMaxNbNodes = myMaxNbNodes; + theOctree->myMinBoxSize = myMinBoxSize; + theOctree->myNbNodes = 0; + return theOctree; +} + + + +//====================================== +/*! + * \brief Compute the first bounding box + * + * We take the max/min coord of the nodes + */ +//====================================== +void SMESH_OctreeNode::computeBoxForFather() +{ + set::iterator it=myNodes.begin(); + for( ;it!=myNodes.end();it++){ + const SMDS_MeshNode* n1 = *it; + gp_XYZ p1( n1->X(), n1->Y(), n1->Z() ); + myBox->Add(p1); + } +} + +//==================================================================================== +/*! + * \brief Tell if Octree is a leaf or not (has to be implemented in inherited classes) + * \retval - True if the Octree is a leaf + */ +//==================================================================================== +const bool SMESH_OctreeNode::isLeaf() +{ + return myIsLeaf; +} + +//==================================================================================== +/*! + * \brief Tells us if Node is inside the current box with the precision "precision" + * \param Node - Node + * \param precision - The box is enlarged with this precision + * \retval bool - True if Node is in the box within precision + */ +//==================================================================================== +const bool SMESH_OctreeNode::isInside(const SMDS_MeshNode * Node, const double precision ) +{ + double X=Node->X(); + double Y=Node->Y(); + double Z=Node->Z(); + bool Out = 1 ; + if (precision<=0.) + return !(myBox->IsOut(gp_XYZ(X,Y,Z))); + Bnd_B3d * BoxWithPrecision = new Bnd_B3d(); + getBox(BoxWithPrecision); + BoxWithPrecision->Enlarge(precision); + Out=BoxWithPrecision->IsOut(gp_XYZ(X,Y,Z)); + delete BoxWithPrecision; + return !(Out); +} + + +//================================================ +/*! + * \brief Set the data of the children + * Shares the father's data with each of his child + */ +//================================================ +void SMESH_OctreeNode::buildChildrenData() +{ + gp_XYZ min = myBox->CornerMin(); + gp_XYZ max = myBox->CornerMax(); + gp_XYZ mid = (min + max)/2.; + + set::iterator it=myNodes.begin(); + int ChildBoxNum; + while( it!=myNodes.end()) + { + const SMDS_MeshNode* n1 = *it; + ChildBoxNum= (n1->X()>mid.X()) + (n1->Y()>mid.Y())*2 + (n1->Z()>mid.Z())*4; + SMESH_OctreeNode* myChild = dynamic_cast (myChildren[ChildBoxNum]); + myChild->myNodes.insert(myChild->myNodes.end(),n1); + myNodes.erase( it ); + it=myNodes.begin(); + } + for (int i = 0; i<8; i++) + { + SMESH_OctreeNode* myChild = dynamic_cast (myChildren[i]); + myChild->myNbNodes = (myChild->myNodes).size(); + myChild->myIsLeaf = (myChild->myLevel == myMaxLevel)||(myChild->myNbNodes<=myMaxNbNodes)||(myMinBoxSize>=maxSize(myChild->myBox)); + } +} + +//=================================================================== +/*! + * \brief Return in Result a list of Nodes potentials to be near Node + * \param Node - Node + * \param precision - precision used + * \param Result - list of Nodes potentials to be near Node + */ +//==================================================================== +void SMESH_OctreeNode::NodesAround( const SMDS_MeshNode * Node, + list* Result, const double precision) +{ + if (isInside(Node,precision)) + { + if (myIsLeaf) + { + Result->insert( Result->end(), myNodes.begin(), myNodes.end() ); + } + else + { + for(int i=0;i<8;i++) + { + SMESH_OctreeNode* myChild = dynamic_cast (myChildren[i]); + myChild->NodesAround( Node, Result, precision); + } + } + } +} + + + +//============================= +/*! + * \brief Return in theGroupsOfNodes a list of group of nodes close to each other within theTolerance + * Search for all the nodes in nodes + * Static Method : no need to create an SMESH_OctreeNode + * \param nodes - set of nodes we look at, modified during research + * \param theGroupsOfNodes - list of nodes closed to each other returned + * \param theTolerance - Precision used, default value is 0.00001 + * \param maxLevel - Maximum level for SMESH_OctreeNode constructed, default value is -1 (Infinite) + * \param maxNbNodes - maximum Nodes in a Leaf of the SMESH_OctreeNode constructed, default value is 5 + */ +//============================= +void SMESH_OctreeNode::FindCoincidentNodes ( set nodes, + list< list< const SMDS_MeshNode*> >* theGroupsOfNodes, + const double theTolerance, const int maxLevel, + const int maxNbNodes) +{ + SMESH_OctreeNode* theOctreeNode = new SMESH_OctreeNode(nodes, maxLevel, maxNbNodes, theTolerance); + theOctreeNode->FindCoincidentNodes (&nodes, theTolerance, theGroupsOfNodes); + delete theOctreeNode; +} + + +//============================= +/*! + * \brief Return in theGroupsOfNodes a list of group of nodes close to each other within theTolerance + * Search for all the nodes in nodes + * \param nodes - set of nodes we look at, modified during research + * \param theTolerance - Precision used + * \param theGroupsOfNodes - list of nodes closed to each other returned + */ +//============================= +void SMESH_OctreeNode::FindCoincidentNodes ( set* nodes, + const double theTolerance, + list< list< const SMDS_MeshNode*> >* theGroupsOfNodes) +{ + set::iterator it1 = nodes->begin(); + list::iterator it2; + + while (it1 != nodes->end()) + { + const SMDS_MeshNode * n1 = *it1; + + list ListofCoincidentNodes;// Initialize the lists via a declaration, it's enough + + list * groupPtr = 0; + + // Searching for Nodes around n1 and put them in ListofCoincidentNodes + FindCoincidentNodes(n1, nodes, &ListofCoincidentNodes, theTolerance); + + // We build a list {n1 + his neigbours} and add this list in theGroupsOfNodes + for (it2=ListofCoincidentNodes.begin();it2 != ListofCoincidentNodes.end(); it2++) + { + const SMDS_MeshNode* n2 = *it2; + if ( !groupPtr ) + { + theGroupsOfNodes->push_back( list() ); + groupPtr = & theGroupsOfNodes->back(); + groupPtr->push_back( n1 ); + } + if(groupPtr->front()>n2) + groupPtr->push_front( n2 ); + else + groupPtr->push_back( n2 ); + } + if(groupPtr != 0) + groupPtr->sort(); + + nodes->erase(it1); + it1=nodes->begin(); + } +} + +//====================================================================================== +/*! + * \brief Return a list of nodes closed to Node and remove it from SetOfNodes + * \param Node - We're searching the nodes next to him. + * \param SetOfNodes - set of nodes in which we erase the found nodes + * \param Result - list of nodes closed to Node + * \param precision - Precision used + */ +//====================================================================================== +void SMESH_OctreeNode::FindCoincidentNodes( const SMDS_MeshNode * Node, + set* SetOfNodes, + list* Result, + const double precision) +{ + bool isInsideBool = isInside(Node,precision); + + if (isInsideBool) + { + // I'm only looking in the leaves, since all the nodes are stored there. + if (myIsLeaf) + { + gp_Pnt p1( Node->X(), Node->Y(), Node->Z() ); + + set myNodesCopy = myNodes; + set::iterator it = myNodesCopy.begin(); + double tol2 = precision * precision; + bool squareBool; + + while (it != myNodesCopy.end()) + { + const SMDS_MeshNode* n2 = *it; + // We're only looking at nodes with a superior Id. + if(Node->GetID() < n2->GetID()) + { + gp_Pnt p2( n2->X(), n2->Y(), n2->Z() ); + // Distance optimized computation + squareBool = (p1.SquareDistance( p2 ) <= tol2); + + // If n2 inside the SquareDistance, we add it in Result and remove it from SetOfNodes and myNodes + if(squareBool) + { + Result->insert(Result->begin(), n2); + SetOfNodes->erase( n2 ); + myNodes.erase( n2 ); + } + } + myNodesCopy.erase( it ); + it = myNodesCopy.begin(); + } + + } + else + { + // If I'm not a leaf, I'm going to see my children ! + for(int i = 0; i < 8; i++) + { + SMESH_OctreeNode* myChild = dynamic_cast (myChildren[i]); + myChild->FindCoincidentNodes(Node, SetOfNodes, Result, precision); + } + } + } +} + diff --git a/src/SMESH/SMESH_OctreeNode.hxx b/src/SMESH/SMESH_OctreeNode.hxx new file mode 100644 index 000000000..ce8bfde26 --- /dev/null +++ b/src/SMESH/SMESH_OctreeNode.hxx @@ -0,0 +1,112 @@ +// SMESH SMESH_OctreeNode : Octree with Nodes set +// inherites global class SMESH_Octree +// +// Copyright (C) 2003 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN, +// CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS +// +// 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. +// +// This library 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA +// +// See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com +// +// +// +// File : SMESH_OctreeNode.hxx +// Created : Tue Jan 16 16:00:00 2007 +// Author : Nicolas Geimer & Aurélien Motteux (OCC) +// Module : SMESH + +#ifndef _SMESH_OCTREENODE_HXX_ +#define _SMESH_OCTREENODE_HXX_ + +#include "SMESH_Octree.hxx" + +//forward declaration +class SMDS_MeshNode; + +#include +#include + +class SMESH_OctreeNode : public SMESH_Octree{ + +public: + + // Constructor + SMESH_OctreeNode (set theNodes, const int maxLevel = -1, + const int maxNbNodes = 5 , const double minBoxSize = 0.); + +//============================= +/*! + * \brief Empty destructor + */ +//============================= + virtual ~SMESH_OctreeNode () {}; + + // Tells us if SMESH_OctreeNode is a leaf or not (-1 = not initialiazed) + virtual const bool isLeaf(); + + // Tells us if Node is inside the current box with the precision "precision" + virtual const bool isInside(const SMDS_MeshNode * Node, const double precision = 0. ); + + // Return in Result a list of Nodes potentials to be near Node + void NodesAround( const SMDS_MeshNode * Node , list* Result, + const double precision = 0. ); + + // Return in theGroupsOfNodes a list of group of nodes close to each other within theTolerance + // Search for all the nodes in nodes + void FindCoincidentNodes ( set* nodes, + const double theTolerance, + list< list< const SMDS_MeshNode*> >* theGroupsOfNodes); + + // Static method that return in theGroupsOfNodes a list of group of nodes close to each other within + // theTolerance search for all the nodes in nodes + static void FindCoincidentNodes ( set nodes, + list< list< const SMDS_MeshNode*> >* theGroupsOfNodes, + const double theTolerance = 0.00001, const int maxLevel = -1, + const int maxNbNodes = 5); + + protected: + +//============================= +/*! + * \brief Empty constructor + */ +//============================= + SMESH_OctreeNode (){}; + + // Shares the father's data with each of his child + virtual void buildChildrenData(); + + // Compute the bounding box of the whole set of nodes myNodes (only used for OctreeNode level 0) + void computeBoxForFather(); + + // Construct an empty SMESH_OctreeNode used by SMESH_Octree::buildChildren() + virtual SMESH_Octree* allocateOctreeChild(); + + // Return in result a list of nodes closed to Node and remove it from SetOfNodes + void FindCoincidentNodes( const SMDS_MeshNode * Node, + set* SetOfNodes, + list* Result, + const double precision); + + // The max number of nodes a leaf box can contain + int myMaxNbNodes; + + // The set of nodes inside the box of the Octree (Empty if Octree is not a leaf) + set myNodes; + + // The number of nodes I have inside the box + int myNbNodes; +}; +#endif