-// Copyright (C) 2007-2008 CEA/DEN, EDF R&D, OPEN CASCADE
+// Copyright (C) 2007-2011 CEA/DEN, EDF R&D, OPEN CASCADE
//
-// Copyright (C) 2003-2007 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN,
-// CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
+// Copyright (C) 2003-2007 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 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.
+// 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
+// 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
+// See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
//
+
// SMESH SMESH_OctreeNode : Octree with Nodes set
// inherites global class SMESH_Octree
-//
// File : SMESH_OctreeNode.cxx
// Created : Tue Jan 16 16:00:00 2007
-// Author : Nicolas Geimer & Aurélien Motteux (OCC)
+// Author : Nicolas Geimer & Aurelien Motteux (OCC)
// Module : SMESH
-
+//
#include "SMESH_OctreeNode.hxx"
-#include "SMDS_MeshNode.hxx"
#include "SMDS_SetIterator.hxx"
#include <gp_Pnt.hxx>
* \param minBoxSize - Minimal size of the Octree Box
*/
//================================================================
-SMESH_OctreeNode::SMESH_OctreeNode (const set<const SMDS_MeshNode*> & theNodes, const int maxLevel,
+SMESH_OctreeNode::SMESH_OctreeNode (const TIDSortedNodeSet & theNodes, const int maxLevel,
const int maxNbNodes , const double minBoxSize )
- :SMESH_Octree(maxLevel,minBoxSize),
+ :SMESH_Octree( new SMESH_Octree::Limit( 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) ||
- (maxSize(myBox) <= myMinBoxSize));
- // All the children (Boxes and Data) are computed in Compute()
- Compute();
+ compute();
+}
+
+//================================================================================
+/*!
+ * \brief Constructor used to allocate a child
+ */
+//================================================================================
+
+SMESH_OctreeNode::SMESH_OctreeNode (int maxNbNodes):
+ SMESH_Octree(), myMaxNbNodes(maxNbNodes)
+{
}
//==================================================================================
* \brief Construct an empty SMESH_OctreeNode used by SMESH_Octree::buildChildren()
*/
//==================================================================================
-SMESH_Octree* SMESH_OctreeNode::allocateOctreeChild()
+
+SMESH_Octree* SMESH_OctreeNode::allocateOctreeChild() const
{
- 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;
+ return new SMESH_OctreeNode(myMaxNbNodes);
}
//======================================
* We take the max/min coord of the nodes
*/
//======================================
-void SMESH_OctreeNode::computeBoxForFather()
+
+Bnd_B3d* SMESH_OctreeNode::buildRootBox()
{
- set<const SMDS_MeshNode*>::iterator it = myNodes.begin();
+ Bnd_B3d* box = new Bnd_B3d;
+ TIDSortedNodeSet::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);
+ box->Add(p1);
}
-}
+ if ( myNodes.size() <= myMaxNbNodes )
+ myIsLeaf = true;
-//====================================================================================
-/*!
- * \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;
+ return box;
}
//====================================================================================
* \retval bool - True if Node is in the box within precision
*/
//====================================================================================
-const bool SMESH_OctreeNode::isInside (const SMDS_MeshNode * Node, const double precision)
+
+const bool SMESH_OctreeNode::isInside (const gp_XYZ& p, 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;
- getBox(BoxWithPrecision);
+ return !(getBox().IsOut(p));
+ Bnd_B3d BoxWithPrecision = getBox();
BoxWithPrecision.Enlarge(precision);
- Out = BoxWithPrecision.IsOut(gp_XYZ(X,Y,Z));
- return !(Out);
+ return ! BoxWithPrecision.IsOut(p);
}
//================================================
//================================================
void SMESH_OctreeNode::buildChildrenData()
{
- gp_XYZ min = myBox->CornerMin();
- gp_XYZ max = myBox->CornerMax();
+ gp_XYZ min = getBox().CornerMin();
+ gp_XYZ max = getBox().CornerMax();
gp_XYZ mid = (min + max)/2.;
- set<const SMDS_MeshNode*>::iterator it = myNodes.begin();
- int ChildBoxNum;
+ TIDSortedNodeSet::iterator it = myNodes.begin();
while (it != myNodes.end())
{
const SMDS_MeshNode* n1 = *it;
- ChildBoxNum = (n1->X() > mid.X()) + (n1->Y() > mid.Y())*2 + (n1->Z() > mid.Z())*4;
+ int ChildBoxNum = getChildIndex( n1->X(), n1->Y(), n1->Z(), mid );
SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[ChildBoxNum]);
myChild->myNodes.insert(myChild->myNodes.end(),n1);
myNodes.erase( it );
for (int i = 0; i < 8; i++)
{
SMESH_OctreeNode* myChild = dynamic_cast<SMESH_OctreeNode*> (myChildren[i]);
- myChild->myNbNodes = (myChild->myNodes).size();
- myChild->myIsLeaf = ((myChild->myLevel == myMaxLevel) ||
- (myChild->myNbNodes <= myMaxNbNodes) ||
- (maxSize(myChild->myBox) <= myMinBoxSize));
+ if ( myChild->myNodes.size() <= myMaxNbNodes )
+ myChild->myIsLeaf = true;
}
}
list<const SMDS_MeshNode*>* Result,
const double precision)
{
- if (isInside(Node,precision))
+ gp_XYZ p(Node->X(), Node->Y(), Node->Z());
+ if (isInside(p, precision))
{
- if (myIsLeaf)
+ if (isLeaf())
{
Result->insert(Result->end(), myNodes.begin(), myNodes.end());
}
}
}
+//================================================================================
+/*!
+ * \brief Return in dist2Nodes nodes mapped to their square distance from Node
+ * \param node - node to find nodes closest to
+ * \param dist2Nodes - map of found nodes and their distances
+ * \param precision - radius of a sphere to check nodes inside
+ * \retval bool - true if an exact overlapping found
+ */
+//================================================================================
+
+bool SMESH_OctreeNode::NodesAround(const gp_XYZ &node,
+ map<double, const SMDS_MeshNode*>& dist2Nodes,
+ double precision)
+{
+ if ( !dist2Nodes.empty() )
+ precision = min ( precision, sqrt( dist2Nodes.begin()->first ));
+ else if ( precision == 0. )
+ precision = maxSize() / 2;
+
+ //gp_XYZ p(node->X(), node->Y(), node->Z());
+ if (isInside(node, precision))
+ {
+ if (!isLeaf())
+ {
+ // first check a child containing node
+ gp_XYZ mid = (getBox().CornerMin() + getBox().CornerMax()) / 2.;
+ int nodeChild = getChildIndex( node.X(), node.Y(), node.Z(), mid );
+ if ( ((SMESH_OctreeNode*) myChildren[nodeChild])->NodesAround(node, dist2Nodes, precision))
+ return true;
+
+ for (int i = 0; i < 8; i++)
+ if ( i != nodeChild )
+ if (((SMESH_OctreeNode*) myChildren[i])->NodesAround(node, dist2Nodes, precision))
+ return true;
+ }
+ else if ( NbNodes() > 0 )
+ {
+ double minDist = precision * precision;
+ gp_Pnt p1 ( node.X(), node.Y(), node.Z() );
+ set<const SMDS_MeshNode*>::iterator nIt = myNodes.begin();
+ for ( ; nIt != myNodes.end(); ++nIt )
+ {
+ gp_Pnt p2 ( (*nIt)->X(), (*nIt)->Y(), (*nIt)->Z() );
+ double dist2 = p1.SquareDistance( p2 );
+ if ( dist2 < minDist )
+ dist2Nodes.insert( make_pair( minDist = dist2, *nIt ));
+ }
+// if ( dist2Nodes.size() > 1 ) // leave only closest node in dist2Nodes
+// dist2Nodes.erase( ++dist2Nodes.begin(), dist2Nodes.end());
+
+ return ( sqrt( minDist) <= precision * 1e-12 );
+ }
+ }
+ return false;
+}
+
//=============================
/*!
* \brief Return in theGroupsOfNodes a list of group of nodes close to each other within theTolerance
* \param maxNbNodes - maximum Nodes in a Leaf of the SMESH_OctreeNode constructed, default value is 5
*/
//=============================
-void SMESH_OctreeNode::FindCoincidentNodes (set<const SMDS_MeshNode*> theSetOfNodes,
+void SMESH_OctreeNode::FindCoincidentNodes (TIDSortedNodeSet& theSetOfNodes,
list< list< const SMDS_MeshNode*> >* theGroupsOfNodes,
const double theTolerance,
const int maxLevel,
const int maxNbNodes)
{
- SMESH_OctreeNode* theOctreeNode = new SMESH_OctreeNode(theSetOfNodes, maxLevel, maxNbNodes, theTolerance);
- theOctreeNode->FindCoincidentNodes (&theSetOfNodes, theTolerance, theGroupsOfNodes);
- delete theOctreeNode;
+ SMESH_OctreeNode theOctreeNode(theSetOfNodes, maxLevel, maxNbNodes, theTolerance);
+ theOctreeNode.FindCoincidentNodes (&theSetOfNodes, theTolerance, theGroupsOfNodes);
}
//=============================
* \param theGroupsOfNodes - list of nodes closed to each other returned
*/
//=============================
-void SMESH_OctreeNode::FindCoincidentNodes ( set<const SMDS_MeshNode*>* theSetOfNodes,
+void SMESH_OctreeNode::FindCoincidentNodes ( TIDSortedNodeSet* theSetOfNodes,
const double theTolerance,
list< list< const SMDS_MeshNode*> >* theGroupsOfNodes)
{
- set<const SMDS_MeshNode*>::iterator it1 = theSetOfNodes->begin();
+ TIDSortedNodeSet::iterator it1 = theSetOfNodes->begin();
list<const SMDS_MeshNode*>::iterator it2;
while (it1 != theSetOfNodes->end())
*/
//======================================================================================
void SMESH_OctreeNode::FindCoincidentNodes (const SMDS_MeshNode * Node,
- set<const SMDS_MeshNode*>* SetOfNodes,
+ TIDSortedNodeSet* SetOfNodes,
list<const SMDS_MeshNode*>* Result,
const double precision)
{
- bool isInsideBool = isInside(Node,precision);
+ gp_XYZ p(Node->X(), Node->Y(), Node->Z());
+ bool isInsideBool = isInside(p, precision);
if (isInsideBool)
{
// I'm only looking in the leaves, since all the nodes are stored there.
- if (myIsLeaf)
+ if (isLeaf())
{
gp_Pnt p1 (Node->X(), Node->Y(), Node->Z());
- set<const SMDS_MeshNode*> myNodesCopy = myNodes;
- set<const SMDS_MeshNode*>::iterator it = myNodesCopy.begin();
+ TIDSortedNodeSet myNodesCopy = myNodes;
+ TIDSortedNodeSet::iterator it = myNodesCopy.begin();
double tol2 = precision * precision;
bool squareBool;
}
}
+//================================================================================
+/*!
+ * \brief Update data according to node movement
+ */
+//================================================================================
+
+void SMESH_OctreeNode::UpdateByMoveNode( const SMDS_MeshNode* node, const gp_Pnt& toPnt )
+{
+ if ( isLeaf() )
+ {
+ TIDSortedNodeSet::iterator pNode = myNodes.find( node );
+ bool nodeInMe = ( pNode != myNodes.end() );
+
+ bool pointInMe = isInside( toPnt.Coord(), 1e-10 );
+
+ if ( pointInMe != nodeInMe )
+ {
+ if ( pointInMe )
+ myNodes.insert( node );
+ else
+ myNodes.erase( node );
+ }
+ }
+ else if ( myChildren )
+ {
+ gp_XYZ mid = (getBox().CornerMin() + getBox().CornerMax()) / 2.;
+ int nodeChild = getChildIndex( node->X(), node->Y(), node->Z(), mid );
+ int pointChild = getChildIndex( toPnt.X(), toPnt.Y(), toPnt.Z(), mid );
+ if ( nodeChild != pointChild )
+ {
+ ((SMESH_OctreeNode*) myChildren[ nodeChild ])->UpdateByMoveNode( node, toPnt );
+ ((SMESH_OctreeNode*) myChildren[ pointChild ])->UpdateByMoveNode( node, toPnt );
+ }
+ }
+}
+
//================================================================================
/*!
* \brief Return iterator over children
{
return SMESH_OctreeNodeIteratorPtr
( new SMDS_SetIterator< SMESH_OctreeNode*, SMESH_Octree** >
- ( myChildren, ( isLeaf() ? myChildren : &myChildren[ 8 ] )));
+ ( myChildren, (( isLeaf() || !myChildren ) ? myChildren : &myChildren[ 8 ] )));
}
//================================================================================
SMDS_NodeIteratorPtr SMESH_OctreeNode::GetNodeIterator()
{
return SMDS_NodeIteratorPtr
- ( new SMDS_SetIterator< SMDS_pNode, set< SMDS_pNode >::const_iterator >
- ( myNodes.begin(), myNodes.end() ));
+ ( new SMDS_SetIterator< SMDS_pNode, TIDSortedNodeSet::const_iterator >
+ ( myNodes.begin(), myNodes.size() ? myNodes.end() : myNodes.begin()));
}
