1 // Copyright (c) 2013-2014 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 under
6 // the terms of the GNU Lesser General Public License 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>
28 #include <BRepMesh_WireInterferenceChecker.hxx>
32 class BRepMesh_Array1OfVertexOfDelaun;
33 class BRepMesh_Vertex;
34 class TColStd_Array1OfInteger;
35 class TColStd_SequenceOfInteger;
36 class TColStd_MapOfInteger;
38 //! Compute the Delaunay's triangulation with the algorithm of Watson.
45 //! Creates the triangulation with an empty Mesh data structure.
46 Standard_EXPORT BRepMesh_Delaun (BRepMesh_Array1OfVertexOfDelaun& theVertices,
47 const Standard_Boolean isPositive = Standard_True);
49 //! Creates the triangulation with an existent Mesh data structure.
50 Standard_EXPORT BRepMesh_Delaun (const Handle(BRepMesh_DataStructureOfDelaun)& theOldMesh,
51 BRepMesh_Array1OfVertexOfDelaun& theVertices,
52 const Standard_Boolean isPositive = Standard_True);
54 //! Creates the triangulation with an existant Mesh data structure.
55 Standard_EXPORT BRepMesh_Delaun (const Handle(BRepMesh_DataStructureOfDelaun)& theOldMesh,
56 TColStd_Array1OfInteger& theVertexIndices,
57 const Standard_Boolean isPositive = Standard_True);
59 //! Initializes the triangulation with an array of vertices.
60 Standard_EXPORT void Init (BRepMesh_Array1OfVertexOfDelaun& theVertices);
62 //! Removes a vertex from the triangulation.
63 Standard_EXPORT void RemoveVertex (const BRepMesh_Vertex& theVertex);
65 //! Adds some vertices into the triangulation.
66 Standard_EXPORT void AddVertices (BRepMesh_Array1OfVertexOfDelaun& theVertices);
68 //! Modify mesh to use the edge.
69 //! @return True if done
70 Standard_EXPORT Standard_Boolean UseEdge (const Standard_Integer theEdge);
72 //! Gives the Mesh data structure.
73 const Handle(BRepMesh_DataStructureOfDelaun)& Result() const
78 //! Gives the list of frontier edges.
79 inline Handle(BRepMesh_MapOfInteger) Frontier() const
81 return getEdgesByType (BRepMesh_Frontier);
84 //! Gives the list of internal edges.
85 inline Handle(BRepMesh_MapOfInteger) InternalEdges() const
87 return getEdgesByType (BRepMesh_Fixed);
90 //! Gives the list of free edges used only one time
91 inline Handle(BRepMesh_MapOfInteger) FreeEdges() const
93 return getEdgesByType (BRepMesh_Free);
96 //! Gives vertex with the given index
97 inline const BRepMesh_Vertex& GetVertex (const Standard_Integer theIndex) const
99 return myMeshData->GetNode (theIndex);
102 //! Gives edge with the given index
103 inline const BRepMesh_Edge& GetEdge (const Standard_Integer theIndex) const
105 return myMeshData->GetLink (theIndex);
108 //! Gives triangle with the given index
109 inline const BRepMesh_Triangle& GetTriangle (const Standard_Integer theIndex) const
111 return myMeshData->GetElement (theIndex);
114 //! Test is the given triangle contains the given vertex.
115 //! If theEdgeOn != 0 the vertex lies onto the edge index
116 //! returned through this parameter.
117 Standard_EXPORT Standard_Boolean Contains (const Standard_Integer theTriangleId,
118 const BRepMesh_Vertex& theVertex,
119 Standard_Integer& theEdgeOn) const;
130 typedef NCollection_DataMap<Standard_Integer, NCollection_Map<Standard_Integer> > DataMapOfMap;
132 typedef NCollection_Handle<NCollection_Map<Standard_Integer> > HandleOfMapOfInteger;
134 //! Add boundig box for edge defined by start & end point to
135 //! the given vector of bounding boxes for triangulation edges.
136 void fillBndBox (NCollection_Sequence<Bnd_B2d>& theBoxes,
137 const BRepMesh_Vertex& theV1,
138 const BRepMesh_Vertex& theV2);
140 //! Gives the list of edges with type defined by the input parameter.
141 //! If the given type is BRepMesh_Free returns list of edges
142 //! that have number of connected elements less or equal 1.
143 Handle(BRepMesh_MapOfInteger) getEdgesByType (const BRepMesh_DegreeOfFreedom theEdgeType) const;
145 //! Create super mesh and run triangulation procedure.
146 void perform (Bnd_Box2d& theBndBox,
147 TColStd_Array1OfInteger& theVertexIndices);
149 //! Build the super mesh.
150 void superMesh (const Bnd_Box2d& theBox);
152 //! Computes the triangulation and adds the vertices,
153 //! edges and triangles to the Mesh data structure.
154 void compute (TColStd_Array1OfInteger& theVertexIndices);
156 //! Adjust the mesh on the frontier.
157 void frontierAdjust();
159 //! Find left polygon of the given edge and call meshPolygon.
160 Standard_Boolean meshLeftPolygonOf (const Standard_Integer theEdgeIndex,
161 const Standard_Boolean isForward,
162 HandleOfMapOfInteger theSkipped = NULL);
164 //! Find next link starting from the given node and has maximum
165 //! angle respect the given reference link.
166 //! Each time the next link is found other neighbor links at the pivot
167 //! node are marked as leprous and will be excluded from consideration
168 //! next time until a hanging end is occured.
169 Standard_Integer findNextPolygonLink (const Standard_Integer& theFirstNode,
170 const Standard_Integer& thePivotNode,
171 const BRepMesh_Vertex& thePivotVertex,
172 const gp_Vec2d& theRefLinkDir,
173 const NCollection_Sequence<Bnd_B2d>& theBoxes,
174 const TColStd_SequenceOfInteger& thePolygon,
175 const HandleOfMapOfInteger theSkipped,
176 const Standard_Boolean& isSkipLeprous,
177 NCollection_Map<Standard_Integer>& theLeprousLinks,
178 NCollection_Map<Standard_Integer>& theDeadLinks,
179 Standard_Integer& theNextPivotNode,
180 gp_Vec2d& theNextLinkDir,
181 Bnd_B2d& theNextLinkBndBox);
183 //! Check is the given link intersects the polygon boundaries.
184 //! Returns bounding box for the given link trough the theLinkBndBox parameter.
185 Standard_Boolean checkIntersection (const BRepMesh_Edge& theLink,
186 const TColStd_SequenceOfInteger& thePolygon,
187 const NCollection_Sequence<Bnd_B2d>& thePolyBoxes,
188 const Standard_Boolean isConsiderEndPointTouch,
189 const Standard_Boolean isConsiderPointOnEdge,
190 const Standard_Boolean isSkipLastEdge,
191 Bnd_B2d& theLinkBndBox) const;
193 //! Triangulatiion of a closed polygon described by the list
194 //! of indexes of its edges in the structure.
195 //! (negative index means reversed edge)
196 void meshPolygon (TColStd_SequenceOfInteger& thePolygon,
197 NCollection_Sequence<Bnd_B2d>& thePolyBoxes,
198 HandleOfMapOfInteger theSkipped = NULL);
200 //! Triangulatiion of a closed simple polygon (polygon without glued edges and loops)
201 //! described by the list of indexes of its edges in the structure.
202 //! (negative index means reversed edge)
203 void meshSimplePolygon (TColStd_SequenceOfInteger& thePolygon,
204 NCollection_Sequence<Bnd_B2d>& thePolyBoxes);
206 //! Triangulation of closed polygon containing only three edges.
207 inline Standard_Boolean meshElementaryPolygon (const TColStd_SequenceOfInteger& thePolygon);
209 //! Creates the triangles beetween the given node and the given polyline.
210 void createTriangles (const Standard_Integer theVertexIndex,
211 BRepMesh_MapOfIntegerInteger& thePoly);
213 //! Add a triangle based on the given oriented edges into mesh
214 inline void addTriangle (const Standard_Integer (&theEdgesId)[3],
215 const Standard_Boolean (&theEdgesOri)[3],
216 const Standard_Integer (&theNodesId)[3]);
218 //! Deletes the triangle with the given index and adds the free edges into the map.
219 //! When an edge is suppressed more than one time it is destroyed.
220 void deleteTriangle (const Standard_Integer theIndex,
221 BRepMesh_MapOfIntegerInteger& theLoopEdges);
223 //! Returns start and end nodes of the given edge in respect to its orientation.
224 void getOrientedNodes (const BRepMesh_Edge& theEdge,
225 const Standard_Boolean isForward,
226 Standard_Integer* theNodes) const;
228 //! Processes loop within the given polygon formed by range of its
229 //! links specified by start and end link indices.
230 void processLoop (const Standard_Integer theLinkFrom,
231 const Standard_Integer theLinkTo,
232 const TColStd_SequenceOfInteger& thePolygon,
233 const NCollection_Sequence<Bnd_B2d>& thePolyBoxes);
235 //! Creates new link based on the given nodes and updates the given polygon.
236 Standard_Integer createAndReplacePolygonLink (const Standard_Integer theNodes[],
237 const gp_Pnt2d thePnts [],
238 const Standard_Integer theRootIndex,
239 const ReplaceFlag theReplaceFlag,
240 TColStd_SequenceOfInteger& thePolygon,
241 NCollection_Sequence<Bnd_B2d>& thePolyBoxes);
243 //! Creates the triangles on new nodes.
244 void createTrianglesOnNewVertices (TColStd_Array1OfInteger& theVertexIndices);
246 //! Cleanup mesh from the free triangles.
249 //! Goes through the neighbour triangles around the given node started
250 //! from the given link, returns TRUE if some triangle has a bounding
251 //! frontier edge or FALSE elsewhere.
252 //! Stop link is used to prevent cycles.
253 //! Previous element Id is used to identify next neighbor element.
254 Standard_Boolean isBoundToFrontier (const Standard_Integer theRefNodeId,
255 const Standard_Integer theRefLinkId,
256 const Standard_Integer theStopLinkId,
257 const Standard_Integer thePrevElementId);
259 //! Remove internal triangles from the given polygon.
260 void cleanupPolygon (const TColStd_SequenceOfInteger& thePolygon,
261 const NCollection_Sequence<Bnd_B2d>& thePolyBoxes);
263 //! Checks is the given vertex lies inside the polygon.
264 Standard_Boolean isVertexInsidePolygon (const Standard_Integer& theVertexId,
265 const NCollection_Vector<Standard_Integer>& thePolygonVertices) const;
267 //! Remove all triangles and edges that are placed inside the polygon or crossed it.
268 void killTrianglesAroundVertex (const Standard_Integer theZombieNodeId,
269 const NCollection_Vector<Standard_Integer>& thePolyVertices,
270 const NCollection_Map<Standard_Integer>& thePolyVerticesFindMap,
271 const TColStd_SequenceOfInteger& thePolygon,
272 const NCollection_Sequence<Bnd_B2d>& thePolyBoxes,
273 NCollection_Map<Standard_Integer>& theSurvivedLinks,
274 BRepMesh_MapOfIntegerInteger& theLoopEdges);
276 //! Checks is the given link crosses the polygon boundary.
277 //! If yes, kills its triangles and checks neighbor links on boundary intersection. Does nothing elsewhere.
278 void killTrianglesOnIntersectingLinks (const Standard_Integer& theLinkToCheckId,
279 const BRepMesh_Edge& theLinkToCheck,
280 const Standard_Integer& theEndPoint,
281 const TColStd_SequenceOfInteger& thePolygon,
282 const NCollection_Sequence<Bnd_B2d>& thePolyBoxes,
283 NCollection_Map<Standard_Integer>& theSurvivedLinks,
284 BRepMesh_MapOfIntegerInteger& theLoopEdges);
286 //! Kill triangles bound to the given link.
287 void killLinkTriangles (const Standard_Integer& theLinkId,
288 BRepMesh_MapOfIntegerInteger& theLoopEdges);
290 //! Calculates distances between the given point and edges of triangle.
291 Standard_Real calculateDist (const gp_XY theVEdges[3],
292 const gp_XY thePoints[3],
293 const Standard_Integer theEdgesId[3],
294 const BRepMesh_Vertex& theVertex,
295 Standard_Real theDistance[3],
296 Standard_Real theSqModulus[3],
297 Standard_Integer& theEdgeOn) const;
299 //! Checks intersection between the two segments.
300 BRepMesh_WireInterferenceChecker::IntFlag intSegSeg (
301 const BRepMesh_Edge& theEdge1,
302 const BRepMesh_Edge& theEdge2,
303 const Standard_Boolean isConsiderEndPointTouch,
304 const Standard_Boolean isConsiderPointOnEdge,
305 gp_Pnt2d& theIntPnt) const;
307 //! Returns area of the loop of the given polygon defined by indices of its start and end links.
308 Standard_Real polyArea (const TColStd_SequenceOfInteger& thePolygon,
309 const Standard_Integer theStartIndex,
310 const Standard_Integer theEndIndex) const;
314 Handle(BRepMesh_DataStructureOfDelaun) myMeshData;
315 Standard_Boolean myIsPositiveOrientation;
316 BRepMesh_CircleTool myCircles;
317 Standard_Integer mySupVert[3];
318 BRepMesh_Triangle mySupTrian;