1 // Copyright (C) 2007-2023 CEA, EDF, 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 // Initially this file held 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>
48 class SMDS_MeshElement;
52 //=======================================================================
54 * \brief Searcher for the node closest to a point
56 //=======================================================================
58 struct SMESHUtils_EXPORT SMESH_NodeSearcher
60 virtual const SMDS_MeshNode* FindClosestTo( const gp_Pnt& pnt ) = 0;
61 virtual void MoveNode( const SMDS_MeshNode* node, const gp_Pnt& toPnt ) = 0;
62 virtual int FindNearPoint(const gp_Pnt& point,
63 const double tolerance,
64 std::vector< const SMDS_MeshNode* >& foundNodes) = 0;
65 virtual ~SMESH_NodeSearcher() {}
68 //=======================================================================
70 * \brief Searcher for elements
72 //=======================================================================
74 struct SMESHUtils_EXPORT SMESH_ElementSearcher
77 * \brief Find elements of given type where the given point is IN or ON.
78 * Returns nb of found elements and elements them-selves.
80 * 'ALL' type means elements of any type excluding nodes and 0D elements
82 virtual int FindElementsByPoint(const gp_Pnt& point,
83 SMDSAbs_ElementType type,
84 std::vector< const SMDS_MeshElement* >& foundElems) = 0;
86 * \brief Return an element most close to the given point
88 virtual const SMDS_MeshElement* FindClosestTo( const gp_Pnt& point,
89 SMDSAbs_ElementType type) = 0;
91 * \brief Return elements possibly intersecting the line
93 virtual void GetElementsNearLine( const gp_Ax1& line,
94 SMDSAbs_ElementType type,
95 std::vector< const SMDS_MeshElement* >& foundElems) = 0;
97 * \brief Return elements whose bounding box intersects a sphere
99 virtual void GetElementsInSphere( const gp_XYZ& center,
101 SMDSAbs_ElementType type,
102 std::vector< const SMDS_MeshElement* >& foundElems) = 0;
104 * \brief Return elements whose bounding box intersects a given bounding box
106 virtual void GetElementsInBox( const Bnd_B3d& box,
107 SMDSAbs_ElementType type,
108 std::vector< const SMDS_MeshElement* >& foundElems) = 0;
110 * \brief Find out if the given point is out of closed 2D mesh.
112 virtual TopAbs_State GetPointState(const gp_Pnt& point) = 0;
115 * \brief Return a projection of a given point to a 2D mesh.
116 * Optionally return the closest face
118 virtual gp_XYZ Project(const gp_Pnt& point,
119 SMDSAbs_ElementType type,
120 const SMDS_MeshElement** closestFace= 0) = 0;
122 virtual ~SMESH_ElementSearcher();
125 namespace SMESH_MeshAlgos
128 * \brief Return SMESH_NodeSearcher. The caller is responsible for deleting it
131 SMESH_NodeSearcher* GetNodeSearcher( SMDS_Mesh& mesh );
134 SMESH_NodeSearcher* GetNodeSearcher( SMDS_ElemIteratorPtr elemIt );
137 * \brief Return SMESH_ElementSearcher. The caller is responsible for deleting it
140 SMESH_ElementSearcher* GetElementSearcher( SMDS_Mesh& mesh,
141 double tolerance=-1.);
143 SMESH_ElementSearcher* GetElementSearcher( SMDS_Mesh& mesh,
144 SMDS_ElemIteratorPtr elemIt,
145 double tolerance=-1. );
149 * \brief Return true if the point is IN or ON of the element
152 bool IsOut( const SMDS_MeshElement* element, const gp_Pnt& point, double tol );
155 double GetDistance( const SMDS_MeshElement* elem, const gp_Pnt& point, gp_XYZ* closestPnt = 0 );
158 double GetDistance( const SMDS_MeshEdge* edge, const gp_Pnt& point, gp_XYZ* closestPnt = 0 );
161 double GetDistance( const SMDS_MeshFace* face, const gp_Pnt& point, gp_XYZ* closestPnt = 0 );
164 double GetDistance( const SMDS_MeshVolume* volume, const gp_Pnt& point, gp_XYZ* closestPnt = 0 );
167 void GetBarycentricCoords( const gp_XY& point,
168 const gp_XY& t0, const gp_XY& t1, const gp_XY& t2,
169 double & bc0, double & bc1);
172 * \brief Intersect volume by a ray
174 bool IntersectRayVolume( const gp_Ax1& ray, const double rayLen,
175 const SMDS_MeshElement* vol,
176 double & tMin, double & tMax,
177 int & iFacetMin, int & iFacetMax);
179 * Return a face having linked nodes n1 and n2 and which is
181 * - in elemSet provided that !elemSet.empty()
182 * i1 and i2 optionally returns indices of n1 and n2
185 const SMDS_MeshElement* FindFaceInSet(const SMDS_MeshNode* n1,
186 const SMDS_MeshNode* n2,
187 const TIDSortedElemSet& elemSet,
188 const TIDSortedElemSet& avoidSet,
192 * \brief Calculate normal of a mesh face
195 bool FaceNormal(const SMDS_MeshElement* F, gp_XYZ& normal, bool normalized=true);
198 * \brief Return number of nodes common to two elements
201 int NbCommonNodes(const SMDS_MeshElement* e1,
202 const SMDS_MeshElement* e2);
204 * \brief Return nodes common to two elements
207 std::vector< const SMDS_MeshNode*> GetCommonNodes(const SMDS_MeshElement* e1,
208 const SMDS_MeshElement* e2);
210 * \brief Return true if a node is on a boundary of 2D mesh.
211 * Optionally returns two neighboring boundary nodes (or more in non-manifold mesh)
213 SMESHUtils_EXPORT bool IsOn2DBoundary( const SMDS_MeshNode* node,
214 std::vector< const SMDS_MeshNode*> * neibors = nullptr );
216 * \brief Return true if node1 encounters first in the face and node2, after.
217 * The nodes are supposed to be neighbor nodes in the face.
220 bool IsRightOrder( const SMDS_MeshElement* face,
221 const SMDS_MeshNode* node0,
222 const SMDS_MeshNode* node1 );
224 typedef std::vector< std::vector< const SMDS_MeshElement* > > TElemGroupVector;
225 typedef std::vector< std::vector< const SMDS_MeshNode* > > TNodeGroupVector;
227 * \brief Partition given 1D elements into groups of contiguous edges.
228 * A node where number of meeting edges != 2 is a group end.
229 * An optional startNode is used to orient groups it belongs to.
230 * \return a list of edge groups and a list of corresponding node groups.
231 * If a group is closed, the first and last nodes of the group are same.
234 void Get1DBranches( SMDS_ElemIteratorPtr edgeIt,
235 TElemGroupVector& edgeGroups,
236 TNodeGroupVector& nodeGroups,
237 const SMDS_MeshNode* startNode = 0 );
240 * \brief Mark elements given by SMDS_Iterator
241 * \sa SMDS_Mesh::SetAllNodesNotMarked() and SMDS_Mesh::SetAllCellsNotMarked()
243 template< class ElemIter >
244 void MarkElems( ElemIter it, const bool isMarked )
246 while ( it->more() ) it->next()->setIsMarked( isMarked );
249 * \brief Mark elements given by std iterators
251 template< class ElemIter >
252 void MarkElems( ElemIter it, ElemIter end, const bool isMarked )
254 for ( ; it != end; ++it ) (*it)->setIsMarked( isMarked );
257 * \brief Mark nodes of elements given by SMDS_Iterator
259 template< class ElemIter >
260 void MarkElemNodes( ElemIter it, const bool isMarked, const bool markElem = false )
263 while ( it->more() ) {
264 const SMDS_MeshElement* e = it->next();
265 e->setIsMarked( isMarked );
266 MarkElems( e->nodesIterator(), isMarked );
270 MarkElems( it->next()->nodesIterator(), isMarked );
273 * \brief Mark elements given by std iterators
275 template< class ElemIter >
276 void MarkElemNodes( ElemIter it, ElemIter end, const bool isMarked, const bool markElem = false )
279 for ( ; it != end; ++it ) {
280 (*it)->setIsMarked( isMarked );
281 MarkElems( (*it)->nodesIterator(), isMarked );
284 for ( ; it != end; ++it )
285 MarkElems( (*it)->nodesIterator(), isMarked );
288 // 2 nodes + optional medium node
291 const SMDS_MeshNode* _node1;
292 const SMDS_MeshNode* _node2;
293 const SMDS_MeshNode* _medium;
297 * Return sharp edges of faces and non-manifold ones.
298 * Optionally adds existing edges to the result. Angle is in degrees.
301 std::vector< Edge > FindSharpEdges( SMDS_Mesh* mesh,
306 * Distribute all faces of the mesh between groups using given edges.
309 std::vector< std::vector< const SMDS_MeshElement* > >
310 SeparateFacesByEdges( SMDS_Mesh* mesh, const std::vector< Edge >& edges );
313 typedef std::vector<const SMDS_MeshNode*> TFreeBorder;
314 typedef std::vector<TFreeBorder> TFreeBorderVec;
315 struct TFreeBorderPart
317 int _border; // border index within a TFreeBorderVec
318 int _node1; // node index within the border-th TFreeBorder
322 typedef std::vector<TFreeBorderPart> TCoincidentGroup;
323 typedef std::vector<TCoincidentGroup> TCoincidentGroupVec;
324 struct CoincidentFreeBorders
326 TFreeBorderVec _borders; // nodes of all free borders
327 TCoincidentGroupVec _coincidentGroups; // groups of coincident parts of borders
331 * Returns TFreeBorder's coincident within the given tolerance.
332 * If the tolerance <= 0.0 then one tenth of an average size of elements adjacent
333 * to free borders being compared is used.
336 void FindCoincidentFreeBorders(SMDS_Mesh& mesh,
338 CoincidentFreeBorders & foundFreeBordes);
339 // Implemented in ./SMESH_FreeBorders.cxx
342 * Returns all or only closed TFreeBorder's.
343 * Optionally check if the mesh is manifold and if faces are correctly oriented.
346 void FindFreeBorders(SMDS_Mesh& mesh,
347 TFreeBorderVec & foundFreeBordes,
348 const bool closedOnly,
349 bool* isManifold = 0,
350 bool* isGoodOri = 0);
351 // Implemented in ./SMESH_FreeBorders.cxx
354 * Fill a hole defined by a TFreeBorder with 2D elements.
357 void FillHole(const TFreeBorder & freeBorder,
359 std::vector<const SMDS_MeshElement*>& newFaces);
360 // Implemented in ./SMESH_FillHole.cxx
363 * \brief Find nodes whose merge makes the element invalid
366 void DeMerge(const SMDS_MeshElement* elem,
367 std::vector< const SMDS_MeshNode* >& newNodes,
368 std::vector< const SMDS_MeshNode* >& noMergeNodes);
369 // Implemented in SMESH_DeMerge.cxx
372 typedef std::vector< std::pair< const SMDS_MeshElement*, int > > TElemIntPairVec;
373 typedef std::vector< std::pair< const SMDS_MeshNode*, int > > TNodeIntPairVec;
375 * \brief Create an offset mesh of given faces
376 * \param [in] faceIt - the input faces
377 * \param [in] theFixIntersections - to fix self intersections of the offset mesh or not
378 * \param [out] new2OldFaces - history of faces
379 * \param [out] new2OldNodes - history of nodes
380 * \return SMDS_Mesh* - the new offset mesh, a caller should delete
383 SMDS_Mesh* MakeOffset( SMDS_ElemIteratorPtr faceIt,
386 const bool theFixIntersections,
387 TElemIntPairVec& new2OldFaces,
388 TNodeIntPairVec& new2OldNodes );
389 // Implemented in ./SMESH_Offset.cxx
392 //=======================================================================
394 * \brief Cut faces of a triangular mesh.
395 * Usage work-flow: 1) call Cut() methods as many times as needed
396 * 2) call MakeNewFaces() to really modify the mesh faces
398 //=======================================================================
399 // implemented in SMESH_Offset.cxx
401 class SMESHUtils_EXPORT Intersector
404 Intersector( SMDS_Mesh* mesh, double tol, const std::vector< gp_XYZ >& normals );
407 //! Compute cut of two faces of the mesh
408 void Cut( const SMDS_MeshElement* face1,
409 const SMDS_MeshElement* face2,
410 const int nbCommonNodes = -1 );
412 //! Store a face cut by a line given by its ends lying either on face edges or inside the face.
413 // Line ends are accompanied by indices of intersected face edges.
414 // Edge index is <0 if a line end is inside the face.
415 void Cut( const SMDS_MeshElement* face,
416 SMESH_NodeXYZ& lineEnd1,
418 SMESH_NodeXYZ& lineEnd2,
421 //! Split all faces intersected by Cut() methods.
422 // theSign = (-1|1) is used to choose which part of a face cut by another one to remove.
423 // 1 means to remove a part opposite to face normal.
424 // Optionally optimize quality of split faces by edge swapping.
425 void MakeNewFaces( SMESH_MeshAlgos::TElemIntPairVec& theNew2OldFaces,
426 SMESH_MeshAlgos::TNodeIntPairVec& theNew2OldNodes,
427 const double theSign = 1.,
428 const bool theOptimize = false );
430 typedef std::vector< SMESH_NodeXYZ > TFace;
432 //! Cut a face by planes, whose normals point to parts to keep.
433 // Return true if the whole face is cut off
434 static bool CutByPlanes(const SMDS_MeshElement* face,
435 const std::vector< gp_Ax1 > & planes,
437 std::vector< TFace > & newFaceConnectivity );
444 //=======================================================================
446 * \brief Divide a mesh face into triangles
448 //=======================================================================
449 // Implemented in ./SMESH_Triangulate.cxx
451 class SMESHUtils_EXPORT Triangulate
455 Triangulate(bool optimize=false);
458 static int GetNbTriangles( const SMDS_MeshElement* face );
460 int GetTriangles( const SMDS_MeshElement* face,
461 std::vector< const SMDS_MeshNode*>& nodes);
464 bool triangulate( std::vector< const SMDS_MeshNode*>& nodes, const size_t nbNodes );
471 Optimizer* _optimizer;
474 // structure used in MakePolyLine() to define a cutting plane
477 // 2 points, each defined as follows:
478 // ( myNode1 && myNode2 ) ==> point is in the middle of an edge defined by two nodes
479 // ( myNode1 && !myNode2 ) ==> point is at myNode1 of a some face
480 // else ==> point is at myXYZ
481 const SMDS_MeshNode* myNode1[2];
482 const SMDS_MeshNode* myNode2[2];
485 // face on which myXYZ projects (found by MakePolyLine())
486 const SMDS_MeshElement* myFace [2];
488 // vector on the plane; to use a default plane set vector = (0,0,0)
491 // point returning coordinates of a middle of the two points, projected to mesh
492 gp_Pnt myMidProjPoint;
494 typedef std::vector<PolySegment> TListOfPolySegments;
497 * \brief Create a polyline consisting of 1D mesh elements each lying on a 2D element of
498 * the initial mesh. Positions of new nodes are found by cutting the mesh by the
499 * plane passing through pairs of points specified by each PolySegment structure.
500 * If there are several paths connecting a pair of points, the shortest path is
501 * selected by the module. Position of the cutting plane is defined by the two
502 * points and an optional vector lying on the plane specified by a PolySegment.
503 * By default the vector is defined by Mesh module as following. A middle point
504 * of the two given points is computed. The middle point is projected to the mesh.
505 * The vector goes from the middle point to the projection point. In case of planar
506 * mesh, the vector is normal to the mesh.
507 * \param [inout] segments - PolySegment's defining positions of cutting planes.
508 * Return the used vector and position of the middle point.
509 * \param [in] group - an optional group where created mesh segments will
512 // Implemented in ./SMESH_PolyLine.cxx
514 void MakePolyLine( SMDS_Mesh* mesh,
515 TListOfPolySegments& segments,
516 std::vector<const SMDS_MeshElement*>& newEdges,
517 std::vector<const SMDS_MeshNode*>& newNodes,
518 SMDS_MeshGroup* group=0,
519 SMESH_ElementSearcher* searcher=0);
522 * Create a slot of given width around given 1D elements lying on a triangle mesh.
523 * The slot is constructed by cutting faces by cylindrical surfaces made around each segment.
524 * \return Edges located at the slot boundary
526 // Implemented in ./SMESH_Slot.cxx
528 std::vector< Edge > MakeSlot( SMDS_ElemIteratorPtr segmentIt,
531 std::vector< SMDS_MeshGroup* > & groupsToUpdate);
533 } // namespace SMESH_MeshAlgos