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