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>
29 #include <TColStd_Array1OfInteger.hxx>
30 #include <TColStd_SequenceOfInteger.hxx>
31 #include <TColStd_MapOfInteger.hxx>
35 class BRepMesh_Vertex;
37 //! Compute the Delaunay's triangulation with the algorithm of Watson.
44 //! Creates the triangulation with an empty Mesh data structure.
45 Standard_EXPORT BRepMesh_Delaun (BRepMesh::Array1OfVertexOfDelaun& theVertices);
47 //! Creates the triangulation with an existent Mesh data structure.
48 Standard_EXPORT BRepMesh_Delaun (const Handle(BRepMesh_DataStructureOfDelaun)& theOldMesh,
49 BRepMesh::Array1OfVertexOfDelaun& theVertices);
51 //! Creates the triangulation with an existant Mesh data structure.
52 Standard_EXPORT BRepMesh_Delaun (const Handle(BRepMesh_DataStructureOfDelaun)& theOldMesh,
53 BRepMesh::Array1OfInteger& theVertexIndices);
55 //! Initializes the triangulation with an array of vertices.
56 Standard_EXPORT void Init (BRepMesh::Array1OfVertexOfDelaun& theVertices);
58 //! Removes a vertex from the triangulation.
59 Standard_EXPORT void RemoveVertex (const BRepMesh_Vertex& theVertex);
61 //! Adds some vertices into the triangulation.
62 Standard_EXPORT void AddVertices (BRepMesh::Array1OfVertexOfDelaun& theVertices);
64 //! Modify mesh to use the edge.
65 //! @return True if done
66 Standard_EXPORT Standard_Boolean UseEdge (const Standard_Integer theEdge);
68 //! Gives the Mesh data structure.
69 inline const Handle(BRepMesh_DataStructureOfDelaun)& Result() const
74 //! Gives the list of frontier edges.
75 inline BRepMesh::HMapOfInteger Frontier() const
77 return getEdgesByType (BRepMesh_Frontier);
80 //! Gives the list of internal edges.
81 inline BRepMesh::HMapOfInteger InternalEdges() const
83 return getEdgesByType (BRepMesh_Fixed);
86 //! Gives the list of free edges used only one time
87 inline BRepMesh::HMapOfInteger FreeEdges() const
89 return getEdgesByType (BRepMesh_Free);
92 //! Gives vertex with the given index
93 inline const BRepMesh_Vertex& GetVertex (const Standard_Integer theIndex) const
95 return myMeshData->GetNode (theIndex);
98 //! Gives edge with the given index
99 inline const BRepMesh_Edge& GetEdge (const Standard_Integer theIndex) const
101 return myMeshData->GetLink (theIndex);
104 //! Gives triangle with the given index
105 inline const BRepMesh_Triangle& GetTriangle (const Standard_Integer theIndex) const
107 return myMeshData->GetElement (theIndex);
110 //! Returns tool used to build mesh consistent to Delaunay criteria.
111 inline const BRepMesh_CircleTool& Circles() const
116 //! Test is the given triangle contains the given vertex.
117 //! @param theSqTolerance square tolerance to check closeness to some edge
118 //! @param theEdgeOn If it is != 0 the vertex lies onto the edge index
119 //! returned through this parameter.
120 Standard_EXPORT Standard_Boolean Contains (const Standard_Integer theTriangleId,
121 const BRepMesh_Vertex& theVertex,
122 const Standard_Real theSqTolerance,
123 Standard_Integer& theEdgeOn) const;
134 typedef NCollection_DataMap<Standard_Integer, BRepMesh::MapOfInteger> DataMapOfMap;
136 //! Add boundig box for edge defined by start & end point to
137 //! the given vector of bounding boxes for triangulation edges.
138 void fillBndBox (BRepMesh::SequenceOfBndB2d& theBoxes,
139 const BRepMesh_Vertex& theV1,
140 const BRepMesh_Vertex& theV2);
142 //! Gives the list of edges with type defined by the input parameter.
143 //! If the given type is BRepMesh_Free returns list of edges
144 //! that have number of connected elements less or equal 1.
145 BRepMesh::HMapOfInteger getEdgesByType (const BRepMesh_DegreeOfFreedom theEdgeType) const;
147 //! Create super mesh and run triangulation procedure.
148 void perform (Bnd_Box2d& theBndBox,
149 BRepMesh::Array1OfInteger& theVertexIndices);
151 //! Build the super mesh.
152 void superMesh (const Bnd_Box2d& theBox);
154 //! Computes the triangulation and adds the vertices,
155 //! edges and triangles to the Mesh data structure.
156 void compute (BRepMesh::Array1OfInteger& theVertexIndices);
158 //! Adjust the mesh on the frontier.
159 void frontierAdjust();
161 //! Find left polygon of the given edge and call meshPolygon.
162 Standard_Boolean meshLeftPolygonOf(
163 const Standard_Integer theEdgeIndex,
164 const Standard_Boolean isForward,
165 BRepMesh::HMapOfInteger theSkipped = NULL);
167 //! Find next link starting from the given node and has maximum
168 //! angle respect the given reference link.
169 //! Each time the next link is found other neighbor links at the pivot
170 //! node are marked as leprous and will be excluded from consideration
171 //! next time until a hanging end is occured.
172 Standard_Integer findNextPolygonLink (const Standard_Integer& theFirstNode,
173 const Standard_Integer& thePivotNode,
174 const BRepMesh_Vertex& thePivotVertex,
175 const gp_Vec2d& theRefLinkDir,
176 const BRepMesh::SequenceOfBndB2d& theBoxes,
177 const BRepMesh::SequenceOfInteger& thePolygon,
178 const BRepMesh::HMapOfInteger theSkipped,
179 const Standard_Boolean& isSkipLeprous,
180 BRepMesh::MapOfInteger& theLeprousLinks,
181 BRepMesh::MapOfInteger& theDeadLinks,
182 Standard_Integer& theNextPivotNode,
183 gp_Vec2d& theNextLinkDir,
184 Bnd_B2d& theNextLinkBndBox);
186 //! Check is the given link intersects the polygon boundaries.
187 //! Returns bounding box for the given link trough the theLinkBndBox parameter.
188 Standard_Boolean checkIntersection (const BRepMesh_Edge& theLink,
189 const BRepMesh::SequenceOfInteger& thePolygon,
190 const BRepMesh::SequenceOfBndB2d& thePolyBoxes,
191 const Standard_Boolean isConsiderEndPointTouch,
192 const Standard_Boolean isConsiderPointOnEdge,
193 const Standard_Boolean isSkipLastEdge,
194 Bnd_B2d& theLinkBndBox) const;
196 //! Triangulatiion of a closed polygon described by the list
197 //! of indexes of its edges in the structure.
198 //! (negative index means reversed edge)
199 void meshPolygon (BRepMesh::SequenceOfInteger& thePolygon,
200 BRepMesh::SequenceOfBndB2d& thePolyBoxes,
201 BRepMesh::HMapOfInteger theSkipped = NULL);
203 //! Decomposes the given closed simple polygon (polygon without glued edges
204 //! and loops) on two simpler ones by adding new link at the most thin part
205 //! in respect to end point of the first link.
206 //! In case if source polygon consists of three links, creates new triangle
207 //! and clears source container.
208 //! @param thePolygon source polygon to be decomposed (first part of decomposition).
209 //! @param thePolyBoxes bounding boxes corresponded to source polygon's links.
210 //! @param thePolygonCut product of decomposition of source polygon (second part of decomposition).
211 //! @param thePolyBoxesCut bounding boxes corresponded to resulting polygon's links.
212 void decomposeSimplePolygon (
213 BRepMesh::SequenceOfInteger& thePolygon,
214 BRepMesh::SequenceOfBndB2d& thePolyBoxes,
215 BRepMesh::SequenceOfInteger& thePolygonCut,
216 BRepMesh::SequenceOfBndB2d& thePolyBoxesCut);
218 //! Triangulation of closed polygon containing only three edges.
219 inline Standard_Boolean meshElementaryPolygon (const BRepMesh::SequenceOfInteger& thePolygon);
221 //! Creates the triangles beetween the given node and the given polyline.
222 void createTriangles (const Standard_Integer theVertexIndex,
223 BRepMesh::MapOfIntegerInteger& thePoly);
225 //! Add a triangle based on the given oriented edges into mesh
226 inline void addTriangle (const Standard_Integer (&theEdgesId)[3],
227 const Standard_Boolean (&theEdgesOri)[3],
228 const Standard_Integer (&theNodesId)[3]);
230 //! Deletes the triangle with the given index and adds the free edges into the map.
231 //! When an edge is suppressed more than one time it is destroyed.
232 void deleteTriangle (const Standard_Integer theIndex,
233 BRepMesh::MapOfIntegerInteger& theLoopEdges);
235 //! Returns start and end nodes of the given edge in respect to its orientation.
236 void getOrientedNodes (const BRepMesh_Edge& theEdge,
237 const Standard_Boolean isForward,
238 Standard_Integer* theNodes) const;
240 //! Processes loop within the given polygon formed by range of its
241 //! links specified by start and end link indices.
242 void processLoop (const Standard_Integer theLinkFrom,
243 const Standard_Integer theLinkTo,
244 const BRepMesh::SequenceOfInteger& thePolygon,
245 const BRepMesh::SequenceOfBndB2d& thePolyBoxes);
247 //! Creates new link based on the given nodes and updates the given polygon.
248 Standard_Integer createAndReplacePolygonLink (const Standard_Integer theNodes[],
249 const gp_Pnt2d thePnts [],
250 const Standard_Integer theRootIndex,
251 const ReplaceFlag theReplaceFlag,
252 BRepMesh::SequenceOfInteger& thePolygon,
253 BRepMesh::SequenceOfBndB2d& thePolyBoxes);
255 //! Creates the triangles on new nodes.
256 void createTrianglesOnNewVertices (BRepMesh::Array1OfInteger& theVertexIndices);
258 //! Cleanup mesh from the free triangles.
261 //! Goes through the neighbour triangles around the given node started
262 //! from the given link, returns TRUE if some triangle has a bounding
263 //! frontier edge or FALSE elsewhere.
264 //! Stop link is used to prevent cycles.
265 //! Previous element Id is used to identify next neighbor element.
266 Standard_Boolean isBoundToFrontier (const Standard_Integer theRefNodeId,
267 const Standard_Integer theRefLinkId,
268 const Standard_Integer theStopLinkId,
269 const Standard_Integer thePrevElementId);
271 //! Remove internal triangles from the given polygon.
272 void cleanupPolygon (const BRepMesh::SequenceOfInteger& thePolygon,
273 const BRepMesh::SequenceOfBndB2d& thePolyBoxes);
275 //! Checks is the given vertex lies inside the polygon.
276 Standard_Boolean isVertexInsidePolygon (const Standard_Integer& theVertexId,
277 const BRepMesh::VectorOfInteger& thePolygonVertices) const;
279 //! Remove all triangles and edges that are placed inside the polygon or crossed it.
280 void killTrianglesAroundVertex (const Standard_Integer theZombieNodeId,
281 const BRepMesh::VectorOfInteger& thePolyVertices,
282 const BRepMesh::MapOfInteger& thePolyVerticesFindMap,
283 const BRepMesh::SequenceOfInteger& thePolygon,
284 const BRepMesh::SequenceOfBndB2d& thePolyBoxes,
285 BRepMesh::MapOfInteger& theSurvivedLinks,
286 BRepMesh::MapOfIntegerInteger& theLoopEdges);
288 //! Checks is the given link crosses the polygon boundary.
289 //! If yes, kills its triangles and checks neighbor links on boundary intersection. Does nothing elsewhere.
290 void killTrianglesOnIntersectingLinks (const Standard_Integer& theLinkToCheckId,
291 const BRepMesh_Edge& theLinkToCheck,
292 const Standard_Integer& theEndPoint,
293 const BRepMesh::SequenceOfInteger& thePolygon,
294 const BRepMesh::SequenceOfBndB2d& thePolyBoxes,
295 BRepMesh::MapOfInteger& theSurvivedLinks,
296 BRepMesh::MapOfIntegerInteger& theLoopEdges);
298 //! Kill triangles bound to the given link.
299 void killLinkTriangles (const Standard_Integer& theLinkId,
300 BRepMesh::MapOfIntegerInteger& theLoopEdges);
302 //! Calculates distances between the given point and edges of triangle.
303 Standard_Real calculateDist (const gp_XY theVEdges[3],
304 const gp_XY thePoints[3],
305 const BRepMesh_Vertex& theVertex,
306 Standard_Real theDistance[3],
307 Standard_Real theSqModulus[3],
308 Standard_Integer& theEdgeOn) const;
310 //! Checks intersection between the two segments.
311 BRepMesh_GeomTool::IntFlag intSegSeg(
312 const BRepMesh_Edge& theEdge1,
313 const BRepMesh_Edge& theEdge2,
314 const Standard_Boolean isConsiderEndPointTouch,
315 const Standard_Boolean isConsiderPointOnEdge,
316 gp_Pnt2d& theIntPnt) const;
318 //! Returns area of the loop of the given polygon defined by indices of its start and end links.
319 Standard_Real polyArea (const BRepMesh::SequenceOfInteger& thePolygon,
320 const Standard_Integer theStartIndex,
321 const Standard_Integer theEndIndex) const;
325 Handle(BRepMesh_DataStructureOfDelaun) myMeshData;
326 BRepMesh_CircleTool myCircles;
327 Standard_Integer mySupVert[3];
328 BRepMesh_Triangle mySupTrian;