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>
31 class BRepMesh_Array1OfVertexOfDelaun;
32 class BRepMesh_Vertex;
33 class TColStd_Array1OfInteger;
34 class TColStd_SequenceOfInteger;
35 class TColStd_MapOfInteger;
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,
46 const Standard_Boolean isPositive = Standard_True);
48 //! Creates the triangulation with an existent Mesh data structure.
49 Standard_EXPORT BRepMesh_Delaun (const Handle(BRepMesh_DataStructureOfDelaun)& theOldMesh,
50 BRepMesh_Array1OfVertexOfDelaun& theVertices,
51 const Standard_Boolean isPositive = Standard_True);
53 //! Creates the triangulation with an existant Mesh data structure.
54 Standard_EXPORT BRepMesh_Delaun (const Handle(BRepMesh_DataStructureOfDelaun)& theOldMesh,
55 TColStd_Array1OfInteger& theVertexIndices,
56 const Standard_Boolean isPositive = Standard_True);
58 //! Initializes the triangulation with an array of vertices.
59 Standard_EXPORT void Init (BRepMesh_Array1OfVertexOfDelaun& theVertices);
61 //! Removes a vertex from the triangulation.
62 Standard_EXPORT void RemoveVertex (const BRepMesh_Vertex& theVertex);
64 //! Adds some vertices into the triangulation.
65 Standard_EXPORT void AddVertices (BRepMesh_Array1OfVertexOfDelaun& theVertices);
67 //! Modify mesh to use the edge.
68 //! @return True if done
69 Standard_EXPORT Standard_Boolean UseEdge (const Standard_Integer theEdge);
71 //! Gives the Mesh data structure.
72 const Handle(BRepMesh_DataStructureOfDelaun)& Result() const
77 //! Gives the list of frontier edges.
78 inline Handle(BRepMesh_MapOfInteger) Frontier() const
80 return getEdgesByType (BRepMesh_Frontier);
83 //! Gives the list of internal edges.
84 inline Handle(BRepMesh_MapOfInteger) InternalEdges() const
86 return getEdgesByType (BRepMesh_Fixed);
89 //! Gives the list of free edges used only one time
90 inline Handle(BRepMesh_MapOfInteger) FreeEdges() const
92 return getEdgesByType (BRepMesh_Free);
95 //! Gives vertex with the given index
96 inline const BRepMesh_Vertex& GetVertex (const Standard_Integer theIndex) const
98 return myMeshData->GetNode (theIndex);
101 //! Gives edge with the given index
102 inline const BRepMesh_Edge& GetEdge (const Standard_Integer theIndex) const
104 return myMeshData->GetLink (theIndex);
107 //! Gives triangle with the given index
108 inline const BRepMesh_Triangle& GetTriangle (const Standard_Integer theIndex) const
110 return myMeshData->GetElement (theIndex);
113 //! Test is the given triangle contains the given vertex.
114 //! If theEdgeOn != 0 the vertex lies onto the edge index
115 //! returned through this parameter.
116 Standard_EXPORT Standard_Boolean Contains (const Standard_Integer theTriangleId,
117 const BRepMesh_Vertex& theVertex,
118 Standard_Integer& theEdgeOn) const;
139 typedef NCollection_DataMap<Standard_Integer, NCollection_Map<Standard_Integer> > DataMapOfMap;
141 typedef NCollection_Handle<NCollection_Map<Standard_Integer> > HandleOfMapOfInteger;
143 //! Add boundig box for edge defined by start & end point to
144 //! the given vector of bounding boxes for triangulation edges.
145 void fillBndBox (NCollection_Sequence<Bnd_B2d>& theBoxes,
146 const BRepMesh_Vertex& theV1,
147 const BRepMesh_Vertex& theV2);
149 //! Gives the list of edges with type defined by the input parameter.
150 //! If the given type is BRepMesh_Free returns list of edges
151 //! that have number of connected elements less or equal 1.
152 Handle(BRepMesh_MapOfInteger) getEdgesByType (const BRepMesh_DegreeOfFreedom theEdgeType) const;
154 //! Create super mesh and run triangulation procedure.
155 void perform (Bnd_Box2d& theBndBox,
156 TColStd_Array1OfInteger& theVertexIndices);
158 //! Build the super mesh.
159 void superMesh (const Bnd_Box2d& theBox);
161 //! Computes the triangulation and adds the vertices,
162 //! edges and triangles to the Mesh data structure.
163 void compute (TColStd_Array1OfInteger& theVertexIndices);
165 //! Adjust the mesh on the frontier.
166 void frontierAdjust();
168 //! Find left polygon of the given edge and call meshPolygon.
169 Standard_Boolean meshLeftPolygonOf (const Standard_Integer theEdgeIndex,
170 const Standard_Boolean isForward,
171 HandleOfMapOfInteger theSkipped = NULL);
173 //! Find next link starting from the given node and has maximum
174 //! angle respect the given reference link.
175 //! Each time the next link is found other neighbor links at the pivot
176 //! node are marked as leprous and will be excluded from consideration
177 //! next time until a hanging end is occured.
178 Standard_Integer findNextPolygonLink (const Standard_Integer& theFirstNode,
179 const Standard_Integer& thePivotNode,
180 const BRepMesh_Vertex& thePivotVertex,
181 const gp_Vec2d& theRefLinkDir,
182 const NCollection_Sequence<Bnd_B2d>& theBoxes,
183 const TColStd_SequenceOfInteger& thePolygon,
184 const HandleOfMapOfInteger theSkipped,
185 const Standard_Boolean& isSkipLeprous,
186 NCollection_Map<Standard_Integer>& theLeprousLinks,
187 NCollection_Map<Standard_Integer>& theDeadLinks,
188 Standard_Integer& theNextPivotNode,
189 gp_Vec2d& theNextLinkDir,
190 Bnd_B2d& theNextLinkBndBox);
192 //! Check is the given link intersects the polygon boundaries.
193 //! Returns bounding box for the given link trough the theLinkBndBox parameter.
194 Standard_Boolean checkIntersection (const BRepMesh_Edge& theLink,
195 const TColStd_SequenceOfInteger& thePolygon,
196 const NCollection_Sequence<Bnd_B2d>& thePolyBoxes,
197 const Standard_Boolean isConsiderEndPointTouch,
198 const Standard_Boolean isConsiderPointOnEdge,
199 const Standard_Boolean isSkipLastEdge,
200 Bnd_B2d& theLinkBndBox) const;
202 //! Triangulatiion of a closed polygon described by the list
203 //! of indexes of its edges in the structure.
204 //! (negative index means reversed edge)
205 void meshPolygon (TColStd_SequenceOfInteger& thePolygon,
206 NCollection_Sequence<Bnd_B2d>& thePolyBoxes,
207 HandleOfMapOfInteger theSkipped = NULL);
209 //! Triangulatiion of a closed simple polygon (polygon without glued edges and loops)
210 //! described by the list of indexes of its edges in the structure.
211 //! (negative index means reversed edge)
212 void meshSimplePolygon (TColStd_SequenceOfInteger& thePolygon,
213 NCollection_Sequence<Bnd_B2d>& thePolyBoxes);
215 //! Triangulation of closed polygon containing only three edges.
216 inline Standard_Boolean meshElementaryPolygon (const TColStd_SequenceOfInteger& thePolygon);
218 //! Creates the triangles beetween the given node and the given polyline.
219 void createTriangles (const Standard_Integer theVertexIndex,
220 BRepMesh_MapOfIntegerInteger& thePoly);
222 //! Add a triangle based on the given oriented edges into mesh
223 inline void addTriangle (const Standard_Integer (&theEdgesId)[3],
224 const Standard_Boolean (&theEdgesOri)[3],
225 const Standard_Integer (&theNodesId)[3]);
227 //! Deletes the triangle with the given index and adds the free edges into the map.
228 //! When an edge is suppressed more than one time it is destroyed.
229 void deleteTriangle (const Standard_Integer theIndex,
230 BRepMesh_MapOfIntegerInteger& theLoopEdges);
232 //! Returns start and end nodes of the given edge in respect to its orientation.
233 void getOrientedNodes (const BRepMesh_Edge& theEdge,
234 const Standard_Boolean isForward,
235 Standard_Integer* theNodes) const;
237 //! Processes loop within the given polygon formed by range of its
238 //! links specified by start and end link indices.
239 void processLoop (const Standard_Integer theLinkFrom,
240 const Standard_Integer theLinkTo,
241 const TColStd_SequenceOfInteger& thePolygon,
242 const NCollection_Sequence<Bnd_B2d>& thePolyBoxes);
244 //! Creates new link based on the given nodes and updates the given polygon.
245 Standard_Integer createAndReplacePolygonLink (const Standard_Integer theNodes[],
246 const gp_Pnt2d thePnts [],
247 const Standard_Integer theRootIndex,
248 const ReplaceFlag theReplaceFlag,
249 TColStd_SequenceOfInteger& thePolygon,
250 NCollection_Sequence<Bnd_B2d>& thePolyBoxes);
252 //! Creates the triangles on new nodes.
253 void createTrianglesOnNewVertices (TColStd_Array1OfInteger& theVertexIndices);
255 //! Cleanup mesh from the free triangles.
258 //! Goes through the neighbour triangles around the given node started
259 //! from the given link, returns TRUE if some triangle has a bounding
260 //! frontier edge or FALSE elsewhere.
261 //! Stop link is used to prevent cycles.
262 //! Previous element Id is used to identify next neighbor element.
263 Standard_Boolean isBoundToFrontier (const Standard_Integer theRefNodeId,
264 const Standard_Integer theRefLinkId,
265 const Standard_Integer theStopLinkId,
266 const Standard_Integer thePrevElementId);
268 //! Remove internal triangles from the given polygon.
269 void cleanupPolygon (const TColStd_SequenceOfInteger& thePolygon,
270 const NCollection_Sequence<Bnd_B2d>& thePolyBoxes);
272 //! Checks is the given vertex lies inside the polygon.
273 Standard_Boolean isVertexInsidePolygon (const Standard_Integer& theVertexId,
274 const NCollection_Vector<Standard_Integer>& thePolygonVertices) const;
276 //! Remove all triangles and edges that are placed inside the polygon or crossed it.
277 void killTrianglesAroundVertex (const Standard_Integer theZombieNodeId,
278 const NCollection_Vector<Standard_Integer>& thePolyVertices,
279 const NCollection_Map<Standard_Integer>& thePolyVerticesFindMap,
280 const TColStd_SequenceOfInteger& thePolygon,
281 const NCollection_Sequence<Bnd_B2d>& thePolyBoxes,
282 NCollection_Map<Standard_Integer>& theSurvivedLinks,
283 BRepMesh_MapOfIntegerInteger& theLoopEdges);
285 //! Checks is the given link crosses the polygon boundary.
286 //! If yes, kills its triangles and checks neighbor links on boundary intersection. Does nothing elsewhere.
287 void killTrianglesOnIntersectingLinks (const Standard_Integer& theLinkToCheckId,
288 const BRepMesh_Edge& theLinkToCheck,
289 const Standard_Integer& theEndPoint,
290 const TColStd_SequenceOfInteger& thePolygon,
291 const NCollection_Sequence<Bnd_B2d>& thePolyBoxes,
292 NCollection_Map<Standard_Integer>& theSurvivedLinks,
293 BRepMesh_MapOfIntegerInteger& theLoopEdges);
295 //! Kill triangles bound to the given link.
296 void killLinkTriangles (const Standard_Integer& theLinkId,
297 BRepMesh_MapOfIntegerInteger& theLoopEdges);
299 //! Calculates distances between the given point and edges of triangle.
300 Standard_Real calculateDist (const gp_XY theVEdges[3],
301 const gp_XY thePoints[3],
302 const Standard_Integer theEdgesId[3],
303 const BRepMesh_Vertex& theVertex,
304 Standard_Real theDistance[3],
305 Standard_Real theSqModulus[3],
306 Standard_Integer& theEdgeOn) const;
308 //! Classifies the point in case of coincidence of two vectors.
309 //! @param thePoint1 the start point of a segment (base point)
310 //! @param thePoint2 the end point of a segment
311 //! @param thePointToCheck the point to classify
312 //! @returns zero value if point is out of segment and non zero value if point is between the first and the second point of segment
313 Standard_Integer classifyPoint (const gp_XY& thePoint1,
314 const gp_XY& thePoint2,
315 const gp_XY& thePointToCheck) const;
317 //! Checks intersection between the two segments.
318 IntFlag intSegSeg (const BRepMesh_Edge& theEdge1,
319 const BRepMesh_Edge& theEdge2,
320 const Standard_Boolean isConsiderEndPointTouch,
321 const Standard_Boolean isConsiderPointOnEdge,
322 gp_Pnt2d& theIntPnt) const;
324 //! Returns area of the loop of the given polygon defined by indices of its start and end links.
325 Standard_Real polyArea (const TColStd_SequenceOfInteger& thePolygon,
326 const Standard_Integer theStartIndex,
327 const Standard_Integer theEndIndex) const;
331 Handle(BRepMesh_DataStructureOfDelaun) myMeshData;
332 Standard_Boolean myIsPositiveOrientation;
333 BRepMesh_CircleTool myCircles;
334 Standard_Integer mySupVert[3];
335 BRepMesh_Triangle mySupTrian;