1 // Copyright (C) 2007-2016 CEA/DEN, EDF R&D, OPEN CASCADE
3 // Copyright (C) 2003-2007 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN,
4 // CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
6 // This library is free software; you can redistribute it and/or
7 // modify it under the terms of the GNU Lesser General Public
8 // License as published by the Free Software Foundation; either
9 // version 2.1 of the License, or (at your option) any later version.
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // Lesser General Public License for more details.
16 // You should have received a copy of the GNU Lesser General Public
17 // License along with this library; if not, write to the Free Software
18 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
22 // File : SMESH_MeshAlgos.hxx
23 // Created : Tue Apr 30 18:00:36 2013
24 // Author : Edward AGAPOV (eap)
26 // This file holds some low level algorithms extracted from SMESH_MeshEditor
27 // to make them accessible from Controls package, and more
30 #ifndef __SMESH_MeshAlgos_HXX__
31 #define __SMESH_MeshAlgos_HXX__
33 #include "SMESH_Utils.hxx"
35 #include "SMDSAbs_ElementType.hxx"
36 #include "SMDS_ElemIterator.hxx"
37 #include "SMESH_TypeDefs.hxx"
39 #include <TopAbs_State.hxx>
46 class SMDS_MeshElement;
49 //=======================================================================
51 * \brief Searcher for the node closest to a point
53 //=======================================================================
55 struct SMESHUtils_EXPORT SMESH_NodeSearcher
57 virtual const SMDS_MeshNode* FindClosestTo( const gp_Pnt& pnt ) = 0;
58 virtual void MoveNode( const SMDS_MeshNode* node, const gp_Pnt& toPnt ) = 0;
59 virtual int FindNearPoint(const gp_Pnt& point,
60 const double tolerance,
61 std::vector< const SMDS_MeshNode* >& foundNodes) = 0;
62 virtual ~SMESH_NodeSearcher() {}
65 //=======================================================================
67 * \brief Searcher for elements
69 //=======================================================================
71 struct SMESHUtils_EXPORT SMESH_ElementSearcher
74 * \brief Find elements of given type where the given point is IN or ON.
75 * Returns nb of found elements and elements them-selves.
77 * 'ALL' type means elements of any type excluding nodes and 0D elements
79 virtual int FindElementsByPoint(const gp_Pnt& point,
80 SMDSAbs_ElementType type,
81 std::vector< const SMDS_MeshElement* >& foundElems) = 0;
83 * \brief Return an element most close to the given point
85 virtual const SMDS_MeshElement* FindClosestTo( const gp_Pnt& point,
86 SMDSAbs_ElementType type) = 0;
88 * \brief Return elements possibly intersecting the line
90 virtual void GetElementsNearLine( const gp_Ax1& line,
91 SMDSAbs_ElementType type,
92 std::vector< const SMDS_MeshElement* >& foundElems) = 0;
94 * \brief Return elements whose bounding box intersects a sphere
96 virtual void GetElementsInSphere( const gp_XYZ& center,
98 SMDSAbs_ElementType type,
99 std::vector< const SMDS_MeshElement* >& foundElems) = 0;
101 * \brief Return elements whose bounding box intersects a given bounding box
103 virtual void GetElementsInBox( const Bnd_B3d& box,
104 SMDSAbs_ElementType type,
105 std::vector< const SMDS_MeshElement* >& foundElems) = 0;
107 * \brief Find out if the given point is out of closed 2D mesh.
109 virtual TopAbs_State GetPointState(const gp_Pnt& point) = 0;
112 * \brief Return a projection of a given point to a 2D mesh.
113 * Optionally return the closest face
115 virtual gp_XYZ Project(const gp_Pnt& point,
116 SMDSAbs_ElementType type,
117 const SMDS_MeshElement** closestFace= 0) = 0;
119 virtual ~SMESH_ElementSearcher();
122 namespace SMESH_MeshAlgos
125 * \brief Return SMESH_NodeSearcher. The caller is responsible for deleting it
128 SMESH_NodeSearcher* GetNodeSearcher( SMDS_Mesh& mesh );
131 SMESH_NodeSearcher* GetNodeSearcher( SMDS_ElemIteratorPtr elemIt );
134 * \brief Return SMESH_ElementSearcher. The caller is responsible for deleting it
137 SMESH_ElementSearcher* GetElementSearcher( SMDS_Mesh& mesh,
138 double tolerance=-1.);
140 SMESH_ElementSearcher* GetElementSearcher( SMDS_Mesh& mesh,
141 SMDS_ElemIteratorPtr elemIt,
142 double tolerance=-1. );
146 * \brief Return true if the point is IN or ON of the element
149 bool IsOut( const SMDS_MeshElement* element, const gp_Pnt& point, double tol );
152 double GetDistance( const SMDS_MeshElement* elem, const gp_Pnt& point, gp_XYZ* closestPnt = 0 );
155 double GetDistance( const SMDS_MeshEdge* edge, const gp_Pnt& point, gp_XYZ* closestPnt = 0 );
158 double GetDistance( const SMDS_MeshFace* face, const gp_Pnt& point, gp_XYZ* closestPnt = 0 );
161 double GetDistance( const SMDS_MeshVolume* volume, const gp_Pnt& point, gp_XYZ* closestPnt = 0 );
164 void GetBarycentricCoords( const gp_XY& point,
165 const gp_XY& t0, const gp_XY& t1, const gp_XY& t2,
166 double & bc0, double & bc1);
169 * Return a face having linked nodes n1 and n2 and which is
171 * - in elemSet provided that !elemSet.empty()
172 * i1 and i2 optionally returns indices of n1 and n2
175 const SMDS_MeshElement* FindFaceInSet(const SMDS_MeshNode* n1,
176 const SMDS_MeshNode* n2,
177 const TIDSortedElemSet& elemSet,
178 const TIDSortedElemSet& avoidSet,
182 * \brief Calculate normal of a mesh face
185 bool FaceNormal(const SMDS_MeshElement* F, gp_XYZ& normal, bool normalized=true);
188 * \brief Return nodes common to two elements
191 std::vector< const SMDS_MeshNode*> GetCommonNodes(const SMDS_MeshElement* e1,
192 const SMDS_MeshElement* e2);
194 * \brief Return true if node1 encounters first in the face and node2, after.
195 * The nodes are supposed to be neighbor nodes in the face.
198 bool IsRightOrder( const SMDS_MeshElement* face,
199 const SMDS_MeshNode* node0,
200 const SMDS_MeshNode* node1 );
203 * \brief Mark elements given by SMDS_Iterator
205 template< class ElemIter >
206 void MarkElems( ElemIter it, const bool isMarked )
208 while ( it->more() ) it->next()->setIsMarked( isMarked );
211 * \brief Mark elements given by std iterators
213 template< class ElemIter >
214 void MarkElems( ElemIter it, ElemIter end, const bool isMarked )
216 for ( ; it != end; ++it ) (*it)->setIsMarked( isMarked );
219 * \brief Mark nodes of elements given by SMDS_Iterator
221 template< class ElemIter >
222 void MarkElemNodes( ElemIter it, const bool isMarked, const bool markElem = false )
225 while ( it->more() ) {
226 const SMDS_MeshElement* e = it->next();
227 e->setIsMarked( isMarked );
228 MarkElems( e->nodesIterator(), isMarked );
232 MarkElems( it->next()->nodesIterator(), isMarked );
235 * \brief Mark elements given by std iterators
237 template< class ElemIter >
238 void MarkElemNodes( ElemIter it, ElemIter end, const bool isMarked, const bool markElem = false )
241 for ( ; it != end; ++it ) {
242 (*it)->setIsMarked( isMarked );
243 MarkElems( (*it)->nodesIterator(), isMarked );
246 for ( ; it != end; ++it )
247 MarkElems( (*it)->nodesIterator(), isMarked );
252 typedef std::vector<const SMDS_MeshNode*> TFreeBorder;
253 typedef std::vector<TFreeBorder> TFreeBorderVec;
254 struct TFreeBorderPart
256 int _border; // border index within a TFreeBorderVec
257 int _node1; // node index within the border-th TFreeBorder
261 typedef std::vector<TFreeBorderPart> TCoincidentGroup;
262 typedef std::vector<TCoincidentGroup> TCoincidentGroupVec;
263 struct CoincidentFreeBorders
265 TFreeBorderVec _borders; // nodes of all free borders
266 TCoincidentGroupVec _coincidentGroups; // groups of coincident parts of borders
270 * Returns TFreeBorder's coincident within the given tolerance.
271 * If the tolerance <= 0.0 then one tenth of an average size of elements adjacent
272 * to free borders being compared is used.
275 void FindCoincidentFreeBorders(SMDS_Mesh& mesh,
277 CoincidentFreeBorders & foundFreeBordes);
278 // Implemented in ./SMESH_FreeBorders.cxx
281 * Returns all or only closed TFreeBorder's.
282 * Optionally check if the mesh is manifold and if faces are correctly oriented.
285 void FindFreeBorders(SMDS_Mesh& mesh,
286 TFreeBorderVec & foundFreeBordes,
287 const bool closedOnly,
288 bool* isManifold = 0,
289 bool* isGoodOri = 0);
290 // Implemented in ./SMESH_FreeBorders.cxx
293 * Fill a hole defined by a TFreeBorder with 2D elements.
296 void FillHole(const TFreeBorder & freeBorder,
298 std::vector<const SMDS_MeshElement*>& newFaces);
299 // Implemented in ./SMESH_FillHole.cxx
303 * \brief Find nodes whose merge makes the element invalid
306 void DeMerge(const SMDS_MeshElement* elem,
307 std::vector< const SMDS_MeshNode* >& newNodes,
308 std::vector< const SMDS_MeshNode* >& noMergeNodes);
309 // Implemented in SMESH_DeMerge.cxx
312 typedef std::vector< std::pair< const SMDS_MeshElement*, const SMDS_MeshElement* > > TEPairVec;
313 typedef std::vector< std::pair< const SMDS_MeshNode*, const SMDS_MeshNode* > > TNPairVec;
315 * \brief Create an offset mesh of given faces
316 * \param [in] faceIt - the input faces
317 * \param [in] theFixIntersections - to fix self intersections of the offset mesh or not
318 * \param [out] new2OldFaces - history of faces
319 * \param [out] new2OldNodes - history of nodes
320 * \return SMDS_Mesh* - the new offset mesh, a caller should delete
323 SMDS_Mesh* MakeOffset( SMDS_ElemIteratorPtr faceIt,
326 const bool theFixIntersections,
327 TEPairVec& new2OldFaces,
328 TNPairVec& new2OldNodes );
329 // Implemented in ./SMESH_Offset.cxx
333 * \brief Divide a mesh face into triangles
335 // Implemented in ./SMESH_Triangulate.cxx
337 class SMESHUtils_EXPORT Triangulate
341 static int GetNbTriangles( const SMDS_MeshElement* face );
343 int GetTriangles( const SMDS_MeshElement* face,
344 std::vector< const SMDS_MeshNode*>& nodes);
347 bool triangulate( std::vector< const SMDS_MeshNode*>& nodes, const size_t nbNodes );
350 * \brief Vertex of a polygon. Together with 2 neighbor Vertices represents a triangle
359 void SetNodeAndNext( const SMDS_MeshNode* n, PolyVertex& v );
360 void GetTriaNodes( const SMDS_MeshNode** nodes) const;
361 double TriaArea() const;
362 bool IsInsideTria( const PolyVertex* v );
363 PolyVertex* Delete();
365 std::vector< PolyVertex > _pv;
369 } // namespace SMESH_MeshAlgos