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