1 // Copyright (c) 2013 OPEN CASCADE SAS
3 // This file is part of Open CASCADE Technology software library.
5 // This library is free software; you can redistribute it and / or modify it
6 // under the terms of the GNU Lesser General Public version 2.1 as published
7 // by the Free Software Foundation, with special exception defined in the file
8 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
9 // distribution for complete text of the license and disclaimer of any warranty.
11 // Alternatively, this file may be used under the terms of Open CASCADE
12 // commercial license or contractual agreement.
14 #ifndef _BRepMesh_Delaun_HeaderFile
15 #define _BRepMesh_Delaun_HeaderFile
17 #include <Standard.hxx>
18 #include <Standard_DefineAlloc.hxx>
19 #include <Standard_Macro.hxx>
21 #include <BRepMesh_CircleTool.hxx>
22 #include <BRepMesh_Triangle.hxx>
23 #include <BRepMesh_Edge.hxx>
24 #include <BRepMesh_MapOfInteger.hxx>
25 #include <BRepMesh_MapOfIntegerInteger.hxx>
26 #include <BRepMesh_DataStructureOfDelaun.hxx>
27 #include <NCollection_Sequence.hxx>
31 class BRepMesh_Array1OfVertexOfDelaun;
32 class BRepMesh_Vertex;
33 class TColStd_Array1OfInteger;
34 class TColStd_SequenceOfInteger;
35 class TColStd_MapOfInteger;
37 //! Compute the Delaunay's triangulation with the <br>
38 //! algorithm of Watson. <br>
39 class BRepMesh_Delaun {
44 //! Creates the triangulation with an empty Mesh <br>
45 //! data structure. <br>
46 Standard_EXPORT BRepMesh_Delaun( BRepMesh_Array1OfVertexOfDelaun& theVertices,
47 const Standard_Boolean isPositive = Standard_True );
49 //! Creates the triangulation with and existent <br>
50 //! Mesh data structure. <br>
51 Standard_EXPORT BRepMesh_Delaun( const Handle(BRepMesh_DataStructureOfDelaun)& theOldMesh,
52 BRepMesh_Array1OfVertexOfDelaun& theVertices,
53 const Standard_Boolean isPositive = Standard_True );
55 //! Creates the triangulation with and existant <br>
56 //! Mesh data structure. <br>
57 Standard_EXPORT BRepMesh_Delaun( const Handle(BRepMesh_DataStructureOfDelaun)& theOldMesh,
58 TColStd_Array1OfInteger& theVertexIndices,
59 const Standard_Boolean isPositive = Standard_True );
61 //! Initializes the triangulation with an array of <br>
63 Standard_EXPORT void Init( BRepMesh_Array1OfVertexOfDelaun& theVertices );
65 //! Removes a vertex from the triangulation. <br>
66 Standard_EXPORT void RemoveVertex( const BRepMesh_Vertex& theVertex );
68 //! Adds some vertices into the triangulation. <br>
69 Standard_EXPORT void AddVertices( BRepMesh_Array1OfVertexOfDelaun& theVertices );
71 //! Modify mesh to use the edge. Return True if done. <br>
72 Standard_EXPORT Standard_Boolean UseEdge( const Standard_Integer theEdge );
74 //! Gives the Mesh data structure. <br>
75 Standard_EXPORT const Handle(BRepMesh_DataStructureOfDelaun)& Result() const
80 //! Gives the list of frontier edges <br>
81 inline Handle(BRepMesh_MapOfInteger) Frontier() const
83 return getEdgesByType( BRepMesh_Frontier );
86 //! Gives the list of internal edges <br>
87 inline Handle(BRepMesh_MapOfInteger) InternalEdges() const
89 return getEdgesByType( BRepMesh_Fixed );
92 //! Gives the list of free edges used only one time <br>
93 inline Handle(BRepMesh_MapOfInteger) FreeEdges() const
95 return getEdgesByType( BRepMesh_Free );
98 //! Gives vertex with the given index <br>
99 inline const BRepMesh_Vertex& GetVertex( const Standard_Integer theIndex ) const
101 return myMeshData->GetNode( theIndex );
104 //! Gives edge with the given index <br>
105 inline const BRepMesh_Edge& GetEdge( const Standard_Integer theIndex ) const
107 return myMeshData->GetLink( theIndex );
110 //! Gives triangle with the given index <br>
111 inline const BRepMesh_Triangle& GetTriangle( const Standard_Integer theIndex ) const
113 return myMeshData->GetElement( theIndex );
116 //! Test is the given triangle contains the given vertex. <br>
117 //! If <theEdgeOn> != 0 the vertex lies onto the edge index <br>
118 //! returned through this parameter. <br>
119 Standard_EXPORT Standard_Boolean Contains( const Standard_Integer theTriangleId,
120 const BRepMesh_Vertex& theVertex,
121 Standard_Integer& theEdgeOn ) const;
142 typedef NCollection_DataMap<Standard_Integer, NCollection_Map<Standard_Integer> > DataMapOfMap;
144 typedef NCollection_Handle<NCollection_Map<Standard_Integer> > HandleOfMapOfInteger;
146 //! Add boundig box for edge defined by start & end point to <br>
147 //! the given vector of bounding boxes for triangulation edges <br>
148 void fillBndBox( NCollection_Sequence<Bnd_B2d>& theBoxes,
149 const BRepMesh_Vertex& theV1,
150 const BRepMesh_Vertex& theV2 );
152 //! Gives the list of edges with type defined by the input parameter. <br>
153 //! If the given type is BRepMesh_Free returns list of edges <br>
154 //! that have number of connected elements less or equal 1 <br>
155 Handle(BRepMesh_MapOfInteger) getEdgesByType( const BRepMesh_DegreeOfFreedom theEdgeType ) const;
157 //! Create super mesh and run triangulation procedure <br>
158 void perform( Bnd_Box2d& theBndBox,
159 TColStd_Array1OfInteger& theVertexIndices );
161 //! Build the super mesh. <br>
162 void superMesh( const Bnd_Box2d& theBox );
164 //! Computes the triangulation and adds the vertices, <br>
165 //! edges and triangles to the Mesh data structure. <br>
166 void compute( TColStd_Array1OfInteger& theVertexIndices );
168 //! Adjust the mesh on the frontier. <br>
169 void frontierAdjust();
171 //! Find left polygon of the given edge and call meshPolygon. <br>
172 Standard_Boolean meshLeftPolygonOf( const Standard_Integer theEdgeIndex,
173 const Standard_Boolean isForward,
174 HandleOfMapOfInteger theSkipped = NULL );
176 //! Find next link starting from the given node and has maximum <br>
177 //! angle respect the given reference link. <br>
178 //! Each time the next link is found other neighbor links at the pivot <br>
179 //! node are marked as leprous and will be excluded from consideration <br>
180 //! next time until a hanging end is occured. <br>
181 Standard_Integer findNextPolygonLink( const Standard_Integer& theFirstNode,
182 const Standard_Integer& thePivotNode,
183 const BRepMesh_Vertex& thePivotVertex,
184 const gp_Vec2d& theRefLinkDir,
185 const NCollection_Sequence<Bnd_B2d>& theBoxes,
186 const TColStd_SequenceOfInteger& thePolygon,
187 const HandleOfMapOfInteger theSkipped,
188 const Standard_Boolean& isSkipLeprous,
189 NCollection_Map<Standard_Integer>& theLeprousLinks,
190 NCollection_Map<Standard_Integer>& theDeadLinks,
191 Standard_Integer& theNextPivotNode,
192 gp_Vec2d& theNextLinkDir,
193 Bnd_B2d& theNextLinkBndBox );
195 //! Check is the given link intersects the polygon boundaries. <br>
196 //! Returns bounding box for the given link trough the <theLinkBndBox> parameter. <br>
197 Standard_Boolean checkIntersection( const BRepMesh_Edge& theLink,
198 const TColStd_SequenceOfInteger& thePolygon,
199 const NCollection_Sequence<Bnd_B2d>& thePolyBoxes,
200 const Standard_Boolean isConsiderEndPointTouch,
201 const Standard_Boolean isConsiderPointOnEdge,
202 const Standard_Boolean isSkipLastEdge,
203 Bnd_B2d& theLinkBndBox ) const;
205 //! Triangulatiion of a closed polygon described by the list <br>
206 //! of indexes of its edges in the structure. <br>
207 //! (negative index means reversed edge) <br>
208 void meshPolygon( TColStd_SequenceOfInteger& thePolygon,
209 NCollection_Sequence<Bnd_B2d>& thePolyBoxes,
210 HandleOfMapOfInteger theSkipped = NULL );
212 //! Triangulatiion of a closed simple polygon (polygon without glued edges and loops) <br>
213 //! described by the list of indexes of its edges in the structure. <br>
214 //! (negative index means reversed edge) <br>
215 void meshSimplePolygon( TColStd_SequenceOfInteger& thePolygon,
216 NCollection_Sequence<Bnd_B2d>& thePolyBoxes );
218 //! Triangulation of closed polygon containing only three edges.
219 inline Standard_Boolean meshElementaryPolygon( const TColStd_SequenceOfInteger& thePolygon );
221 //! Creates the triangles beetween the given node <br>
222 //! and the given polyline. <br>
223 void createTriangles( const Standard_Integer theVertexIndex,
224 BRepMesh_MapOfIntegerInteger& thePoly );
226 //! Add a triangle based on the given oriented edges into mesh <br>
227 inline void addTriangle( const Standard_Integer (&theEdgesId)[3],
228 const Standard_Boolean (&theEdgesOri)[3],
229 const Standard_Integer (&theNodesId)[3] );
231 //! Deletes the triangle with the given index and <br>
232 //! adds the free edges into the map. <br>
233 //! When an edge is suppressed more than one time <br>
234 //! it is destroyed. <br>
235 void deleteTriangle( const Standard_Integer theIndex,
236 BRepMesh_MapOfIntegerInteger& theLoopEdges );
238 //! Returns start and end nodes of the given edge <br>
239 //! in respect to its orientation. <br>
240 void getOrientedNodes(const BRepMesh_Edge& theEdge,
241 const Standard_Boolean isForward,
242 Standard_Integer *theNodes) const;
244 //! Processes loop within the given polygon formed by range of its <br>
245 //! links specified by start and end link indices. <br>
246 void processLoop(const Standard_Integer theLinkFrom,
247 const Standard_Integer theLinkTo,
248 const TColStd_SequenceOfInteger& thePolygon,
249 const NCollection_Sequence<Bnd_B2d>& thePolyBoxes);
251 //! Creates new link based on the given nodes and updates the given polygon.
252 Standard_Integer createAndReplacePolygonLink(const Standard_Integer theNodes[],
253 const gp_Pnt2d thePnts [],
254 const Standard_Integer theRootIndex,
255 const ReplaceFlag theReplaceFlag,
256 TColStd_SequenceOfInteger& thePolygon,
257 NCollection_Sequence<Bnd_B2d>& thePolyBoxes);
259 //! Creates the triangles on new nodes <br>
260 void createTrianglesOnNewVertices( TColStd_Array1OfInteger& theVertexIndices );
262 //! Cleanup mesh from the free triangles <br>
265 //! Goes through the neighbour triangles around the given node started
266 //! from the given link, returns TRUE if some triangle has a bounding
267 //! frontier edge or FALSE elsewhere.
268 //! Stop link is used to prevent cycles.
269 //! Previous element Id is used to identify next neighbor element.
270 Standard_Boolean isBoundToFrontier(const Standard_Integer theRefNodeId,
271 const Standard_Integer theRefLinkId,
272 const Standard_Integer theStopLinkId,
273 const Standard_Integer thePrevElementId);
275 //! Remove internal triangles from the given polygon <br>
276 void cleanupPolygon( const TColStd_SequenceOfInteger& thePolygon,
277 const NCollection_Sequence<Bnd_B2d>& thePolyBoxes );
279 //! Checks is the given vertex lies inside the polygon <br>
280 Standard_Boolean isVertexInsidePolygon( const Standard_Integer& theVertexId,
281 const NCollection_Vector<Standard_Integer>& thePolygonVertices ) const;
283 //! Remove all triangles and edges that are placed <br>
284 //! inside the polygon or crossed it. <br>
285 void killTrianglesAroundVertex( const Standard_Integer theZombieNodeId,
286 const NCollection_Vector<Standard_Integer>& thePolyVertices,
287 const NCollection_Map<Standard_Integer>& thePolyVerticesFindMap,
288 const TColStd_SequenceOfInteger& thePolygon,
289 const NCollection_Sequence<Bnd_B2d>& thePolyBoxes,
290 NCollection_Map<Standard_Integer>& theSurvivedLinks,
291 BRepMesh_MapOfIntegerInteger& theLoopEdges );
293 //! Checks is the given link crosses the polygon boundary. <br>
294 //! If yes, kills its triangles and checks neighbor links on <br>
295 //! boundary intersection. Does nothing elsewhere. <br>
296 void killTrianglesOnIntersectingLinks( const Standard_Integer& theLinkToCheckId,
297 const BRepMesh_Edge& theLinkToCheck,
298 const Standard_Integer& theEndPoint,
299 const TColStd_SequenceOfInteger& thePolygon,
300 const NCollection_Sequence<Bnd_B2d>& thePolyBoxes,
301 NCollection_Map<Standard_Integer>& theSurvivedLinks,
302 BRepMesh_MapOfIntegerInteger& theLoopEdges );
304 //! Kill triangles bound to the given link. <br>
305 void killLinkTriangles( const Standard_Integer& theLinkId,
306 BRepMesh_MapOfIntegerInteger& theLoopEdges );
308 //! Calculates distances between the given point <br>
309 //! and edges of triangle. <br>
310 Standard_Real calculateDist( const gp_XY theVEdges[3],
311 const gp_XY thePoints[3],
312 const Standard_Integer theEdgesId[3],
313 const BRepMesh_Vertex& theVertex,
314 Standard_Real theDistance[3],
315 Standard_Real theSqModulus[3],
316 Standard_Integer& theEdgeOn ) const;
318 //! Classifies the point in case of coincidence of two vectors. <br>
319 //! Returns zero value if point is out of segment and non zero <br>
320 //! value if point is between the first and the second point of segment. <br>
321 //! thePoint1 - the start point of a segment (base point) <br>
322 //! thePoint2 - the end point of a segment <br>
323 //! thePointToCheck - the point to classify <br>
324 Standard_Integer classifyPoint( const gp_XY& thePoint1,
325 const gp_XY& thePoint2,
326 const gp_XY& thePointToCheck ) const;
328 //! Checks intersection between the two segments. <br>
329 IntFlag intSegSeg( const BRepMesh_Edge& theEdge1,
330 const BRepMesh_Edge& theEdge2,
331 const Standard_Boolean isConsiderEndPointTouch,
332 const Standard_Boolean isConsiderPointOnEdge,
333 gp_Pnt2d& theIntPnt) const;
335 //! Returns area of the loop of the given polygon defined by <br>
336 //! indices of its start and end links. <br>
337 Standard_Real polyArea( const TColStd_SequenceOfInteger& thePolygon,
338 const Standard_Integer theStartIndex,
339 const Standard_Integer theEndIndex ) const;
342 Handle(BRepMesh_DataStructureOfDelaun) myMeshData;
343 Standard_Boolean myIsPositiveOrientation;
344 BRepMesh_CircleTool myCircles;
345 Standard_Integer mySupVert[3];
346 BRepMesh_Triangle mySupTrian;