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 <IMeshData_Types.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>
32 #include <Message_ProgressRange.hxx>
36 class BRepMesh_Vertex;
38 //! Compute the Delaunay's triangulation with the algorithm of Watson.
45 //! Creates instance of triangulator, but do not run the algorithm automatically.
46 Standard_EXPORT BRepMesh_Delaun (const Handle(BRepMesh_DataStructureOfDelaun)& theOldMesh,
47 const Standard_Integer theCellsCountU,
48 const Standard_Integer theCellsCountV,
49 const Standard_Boolean isFillCircles);
51 //! Creates the triangulation with an empty Mesh data structure.
52 Standard_EXPORT BRepMesh_Delaun (IMeshData::Array1OfVertexOfDelaun& theVertices);
54 //! Creates the triangulation with an existent Mesh data structure.
55 Standard_EXPORT BRepMesh_Delaun (const Handle(BRepMesh_DataStructureOfDelaun)& theOldMesh,
56 IMeshData::Array1OfVertexOfDelaun& theVertices);
58 //! Creates the triangulation with an existant Mesh data structure.
59 Standard_EXPORT BRepMesh_Delaun (const Handle(BRepMesh_DataStructureOfDelaun)& theOldMesh,
60 IMeshData::VectorOfInteger& theVertexIndices);
62 //! Creates the triangulation with an existant Mesh data structure.
63 Standard_EXPORT BRepMesh_Delaun (const Handle (BRepMesh_DataStructureOfDelaun)& theOldMesh,
64 IMeshData::VectorOfInteger& theVertexIndices,
65 const Standard_Integer theCellsCountU,
66 const Standard_Integer theCellsCountV);
68 //! Initializes the triangulation with an array of vertices.
69 Standard_EXPORT void Init (IMeshData::Array1OfVertexOfDelaun& theVertices);
71 //! Forces initialization of circles cell filter using working structure.
72 Standard_EXPORT void InitCirclesTool (const Standard_Integer theCellsCountU,
73 const Standard_Integer theCellsCountV);
75 //! Removes a vertex from the triangulation.
76 Standard_EXPORT void RemoveVertex (const BRepMesh_Vertex& theVertex);
78 //! Adds some vertices into the triangulation.
79 Standard_EXPORT void AddVertices (IMeshData::VectorOfInteger& theVerticesIndices,
80 const Message_ProgressRange& theRange = Message_ProgressRange());
82 //! Modify mesh to use the edge.
83 //! @return True if done
84 Standard_EXPORT Standard_Boolean UseEdge (const Standard_Integer theEdge);
86 //! Gives the Mesh data structure.
87 const Handle(BRepMesh_DataStructureOfDelaun)& Result() const
92 //! Forces insertion of constraint edges into the base triangulation.
93 void ProcessConstraints()
95 insertInternalEdges();
97 // Adjustment of meshes to boundary edges
101 //! Gives the list of frontier edges.
102 Handle(IMeshData::MapOfInteger) Frontier() const
104 return getEdgesByType (BRepMesh_Frontier);
107 //! Gives the list of internal edges.
108 Handle(IMeshData::MapOfInteger) InternalEdges() const
110 return getEdgesByType (BRepMesh_Fixed);
113 //! Gives the list of free edges used only one time
114 Handle(IMeshData::MapOfInteger) FreeEdges() const
116 return getEdgesByType (BRepMesh_Free);
119 //! Gives vertex with the given index
120 const BRepMesh_Vertex& GetVertex (const Standard_Integer theIndex) const
122 return myMeshData->GetNode (theIndex);
125 //! Gives edge with the given index
126 const BRepMesh_Edge& GetEdge (const Standard_Integer theIndex) const
128 return myMeshData->GetLink (theIndex);
131 //! Gives triangle with the given index
132 const BRepMesh_Triangle& GetTriangle (const Standard_Integer theIndex) const
134 return myMeshData->GetElement (theIndex);
137 //! Returns tool used to build mesh consistent to Delaunay criteria.
138 const BRepMesh_CircleTool& Circles() const
143 //! Test is the given triangle contains the given vertex.
144 //! @param theSqTolerance square tolerance to check closeness to some edge
145 //! @param theEdgeOn If it is != 0 the vertex lies onto the edge index
146 //! returned through this parameter.
147 Standard_EXPORT Standard_Boolean Contains (const Standard_Integer theTriangleId,
148 const BRepMesh_Vertex& theVertex,
149 const Standard_Real theSqTolerance,
150 Standard_Integer& theEdgeOn) const;
152 //! Explicitly sets ids of auxiliary vertices used to build mesh and used by 3rd-party algorithms.
153 inline void SetAuxVertices (const IMeshData::VectorOfInteger& theSupVert)
155 mySupVert = theSupVert;
158 //! Destruction of auxiliary triangles containing the given vertices.
159 //! Removes auxiliary vertices also.
160 //! @param theAuxVertices auxiliary vertices to be cleaned up.
161 Standard_EXPORT void RemoveAuxElements ();
172 typedef NCollection_DataMap<Standard_Integer, IMeshData::MapOfInteger> DataMapOfMap;
174 //! Performs initialization of circles cell filter tool.
175 void initCirclesTool (const Bnd_Box2d& theBox,
176 const Standard_Integer theCellsCountU,
177 const Standard_Integer theCellsCountV);
179 //! Add boundig box for edge defined by start & end point to
180 //! the given vector of bounding boxes for triangulation edges.
181 void fillBndBox (IMeshData::SequenceOfBndB2d& theBoxes,
182 const BRepMesh_Vertex& theV1,
183 const BRepMesh_Vertex& theV2);
185 //! Gives the list of edges with type defined by the input parameter.
186 //! If the given type is BRepMesh_Free returns list of edges
187 //! that have number of connected elements less or equal 1.
188 Handle(IMeshData::MapOfInteger) getEdgesByType (const BRepMesh_DegreeOfFreedom theEdgeType) const;
190 //! Run triangulation procedure.
191 void perform (IMeshData::VectorOfInteger& theVertexIndices,
192 const Standard_Integer theCellsCountU = -1,
193 const Standard_Integer theCellsCountV = -1);
195 //! Build the super mesh.
196 void superMesh (const Bnd_Box2d& theBox);
198 //! Computes the triangulation and adds the vertices,
199 //! edges and triangles to the Mesh data structure.
200 void compute (IMeshData::VectorOfInteger& theVertexIndices);
202 //! Adjust the mesh on the frontier.
203 void frontierAdjust();
205 //! Find left polygon of the given edge and call meshPolygon.
206 Standard_Boolean meshLeftPolygonOf(
207 const Standard_Integer theEdgeIndex,
208 const Standard_Boolean isForward,
209 Handle(IMeshData::MapOfInteger) theSkipped = NULL);
211 //! Find next link starting from the given node and has maximum
212 //! angle respect the given reference link.
213 //! Each time the next link is found other neighbor links at the pivot
214 //! node are marked as leprous and will be excluded from consideration
215 //! next time until a hanging end is occured.
216 Standard_Integer findNextPolygonLink (const Standard_Integer& theFirstNode,
217 const Standard_Integer& thePivotNode,
218 const BRepMesh_Vertex& thePivotVertex,
219 const gp_Vec2d& theRefLinkDir,
220 const IMeshData::SequenceOfBndB2d& theBoxes,
221 const IMeshData::SequenceOfInteger& thePolygon,
222 const Handle(IMeshData::MapOfInteger) theSkipped,
223 const Standard_Boolean& isSkipLeprous,
224 IMeshData::MapOfInteger& theLeprousLinks,
225 IMeshData::MapOfInteger& theDeadLinks,
226 Standard_Integer& theNextPivotNode,
227 gp_Vec2d& theNextLinkDir,
228 Bnd_B2d& theNextLinkBndBox);
230 //! Check is the given link intersects the polygon boundaries.
231 //! Returns bounding box for the given link trough the theLinkBndBox parameter.
232 Standard_Boolean checkIntersection (const BRepMesh_Edge& theLink,
233 const IMeshData::SequenceOfInteger& thePolygon,
234 const IMeshData::SequenceOfBndB2d& thePolyBoxes,
235 const Standard_Boolean isConsiderEndPointTouch,
236 const Standard_Boolean isConsiderPointOnEdge,
237 const Standard_Boolean isSkipLastEdge,
238 Bnd_B2d& theLinkBndBox) const;
240 //! Triangulatiion of a closed polygon described by the list
241 //! of indexes of its edges in the structure.
242 //! (negative index means reversed edge)
243 void meshPolygon (IMeshData::SequenceOfInteger& thePolygon,
244 IMeshData::SequenceOfBndB2d& thePolyBoxes,
245 Handle(IMeshData::MapOfInteger) theSkipped = NULL);
247 //! Decomposes the given closed simple polygon (polygon without glued edges
248 //! and loops) on two simpler ones by adding new link at the most thin part
249 //! in respect to end point of the first link.
250 //! In case if source polygon consists of three links, creates new triangle
251 //! and clears source container.
252 //! @param thePolygon source polygon to be decomposed (first part of decomposition).
253 //! @param thePolyBoxes bounding boxes corresponded to source polygon's links.
254 //! @param thePolygonCut product of decomposition of source polygon (second part of decomposition).
255 //! @param thePolyBoxesCut bounding boxes corresponded to resulting polygon's links.
256 void decomposeSimplePolygon (
257 IMeshData::SequenceOfInteger& thePolygon,
258 IMeshData::SequenceOfBndB2d& thePolyBoxes,
259 IMeshData::SequenceOfInteger& thePolygonCut,
260 IMeshData::SequenceOfBndB2d& thePolyBoxesCut);
262 //! Triangulation of closed polygon containing only three edges.
263 Standard_Boolean meshElementaryPolygon (const IMeshData::SequenceOfInteger& thePolygon);
265 //! Creates the triangles beetween the given node and the given polyline.
266 void createTriangles (const Standard_Integer theVertexIndex,
267 IMeshData::MapOfIntegerInteger& thePoly);
269 //! Add a triangle based on the given oriented edges into mesh
270 void addTriangle (const Standard_Integer (&theEdgesId)[3],
271 const Standard_Boolean (&theEdgesOri)[3],
272 const Standard_Integer (&theNodesId)[3]);
274 //! Deletes the triangle with the given index and adds the free edges into the map.
275 //! When an edge is suppressed more than one time it is destroyed.
276 void deleteTriangle (const Standard_Integer theIndex,
277 IMeshData::MapOfIntegerInteger& theLoopEdges);
279 //! Returns start and end nodes of the given edge in respect to its orientation.
280 void getOrientedNodes (const BRepMesh_Edge& theEdge,
281 const Standard_Boolean isForward,
282 Standard_Integer* theNodes) const;
284 //! Processes loop within the given polygon formed by range of its
285 //! links specified by start and end link indices.
286 void processLoop (const Standard_Integer theLinkFrom,
287 const Standard_Integer theLinkTo,
288 const IMeshData::SequenceOfInteger& thePolygon,
289 const IMeshData::SequenceOfBndB2d& thePolyBoxes);
291 //! Creates new link based on the given nodes and updates the given polygon.
292 Standard_Integer createAndReplacePolygonLink (const Standard_Integer theNodes[],
293 const gp_Pnt2d thePnts [],
294 const Standard_Integer theRootIndex,
295 const ReplaceFlag theReplaceFlag,
296 IMeshData::SequenceOfInteger& thePolygon,
297 IMeshData::SequenceOfBndB2d& thePolyBoxes);
299 //! Creates the triangles on new nodes.
300 void createTrianglesOnNewVertices (IMeshData::VectorOfInteger& theVertexIndices,
301 const Message_ProgressRange& theRange);
303 //! Cleanup mesh from the free triangles.
306 //! Goes through the neighbour triangles around the given node started
307 //! from the given link, returns TRUE if some triangle has a bounding
308 //! frontier edge or FALSE elsewhere.
309 Standard_Boolean isBoundToFrontier (const Standard_Integer theRefNodeId,
310 const Standard_Integer theRefLinkId);
312 //! Remove internal triangles from the given polygon.
313 void cleanupPolygon (const IMeshData::SequenceOfInteger& thePolygon,
314 const IMeshData::SequenceOfBndB2d& thePolyBoxes);
316 //! Checks is the given vertex lies inside the polygon.
317 Standard_Boolean isVertexInsidePolygon (const Standard_Integer& theVertexId,
318 const IMeshData::VectorOfInteger& thePolygonVertices) const;
320 //! Remove all triangles and edges that are placed inside the polygon or crossed it.
321 void killTrianglesAroundVertex (const Standard_Integer theZombieNodeId,
322 const IMeshData::VectorOfInteger& thePolyVertices,
323 const IMeshData::MapOfInteger& thePolyVerticesFindMap,
324 const IMeshData::SequenceOfInteger& thePolygon,
325 const IMeshData::SequenceOfBndB2d& thePolyBoxes,
326 IMeshData::MapOfInteger& theSurvivedLinks,
327 IMeshData::MapOfIntegerInteger& theLoopEdges);
329 //! Checks is the given link crosses the polygon boundary.
330 //! If yes, kills its triangles and checks neighbor links on boundary intersection. Does nothing elsewhere.
331 void killTrianglesOnIntersectingLinks (const Standard_Integer& theLinkToCheckId,
332 const BRepMesh_Edge& theLinkToCheck,
333 const Standard_Integer& theEndPoint,
334 const IMeshData::SequenceOfInteger& thePolygon,
335 const IMeshData::SequenceOfBndB2d& thePolyBoxes,
336 IMeshData::MapOfInteger& theSurvivedLinks,
337 IMeshData::MapOfIntegerInteger& theLoopEdges);
339 //! Kill triangles bound to the given link.
340 void killLinkTriangles (const Standard_Integer& theLinkId,
341 IMeshData::MapOfIntegerInteger& theLoopEdges);
343 //! Calculates distances between the given point and edges of triangle.
344 Standard_Real calculateDist (const gp_XY theVEdges[3],
345 const gp_XY thePoints[3],
346 const BRepMesh_Vertex& theVertex,
347 Standard_Real theDistance[3],
348 Standard_Real theSqModulus[3],
349 Standard_Integer& theEdgeOn) const;
351 //! Checks intersection between the two segments.
352 BRepMesh_GeomTool::IntFlag intSegSeg(
353 const BRepMesh_Edge& theEdge1,
354 const BRepMesh_Edge& theEdge2,
355 const Standard_Boolean isConsiderEndPointTouch,
356 const Standard_Boolean isConsiderPointOnEdge,
357 gp_Pnt2d& theIntPnt) const;
359 //! Returns area of the loop of the given polygon defined by indices of its start and end links.
360 Standard_Real polyArea (const IMeshData::SequenceOfInteger& thePolygon,
361 const Standard_Integer theStartIndex,
362 const Standard_Integer theEndIndex) const;
364 //! Performs insertion of internal edges into mesh.
365 void insertInternalEdges();
367 //! Checks whether the given vertex id relates to super contour.
368 Standard_Boolean isSupVertex (const Standard_Integer theVertexIdx) const
370 for (IMeshData::VectorOfInteger::Iterator aIt (mySupVert); aIt.More (); aIt.Next ())
372 if (theVertexIdx == aIt.Value ())
374 return Standard_True;
378 return Standard_False;
383 Handle(BRepMesh_DataStructureOfDelaun) myMeshData;
384 BRepMesh_CircleTool myCircles;
385 IMeshData::VectorOfInteger mySupVert;
386 Standard_Boolean myInitCircles;
387 BRepMesh_Triangle mySupTrian;