d5f74e42 |
1 | // Copyright (c) 2013-2014 OPEN CASCADE SAS |
304c45c8 |
2 | // |
973c2be1 |
3 | // This file is part of Open CASCADE Technology software library. |
304c45c8 |
4 | // |
d5f74e42 |
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 |
973c2be1 |
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. |
304c45c8 |
10 | // |
973c2be1 |
11 | // Alternatively, this file may be used under the terms of Open CASCADE |
12 | // commercial license or contractual agreement. |
304c45c8 |
13 | |
14 | #ifndef _BRepMesh_Delaun_HeaderFile |
15 | #define _BRepMesh_Delaun_HeaderFile |
16 | |
17 | #include <Standard.hxx> |
18 | #include <Standard_DefineAlloc.hxx> |
19 | #include <Standard_Macro.hxx> |
20 | |
fc9b36d6 |
21 | #include <gp_XY.hxx> |
22 | #include <gp_XYZ.hxx> |
304c45c8 |
23 | #include <BRepMesh_CircleTool.hxx> |
24 | #include <BRepMesh_Triangle.hxx> |
25 | #include <BRepMesh_Edge.hxx> |
848fa7e3 |
26 | #include <BRepMesh.hxx> |
304c45c8 |
27 | #include <BRepMesh_DataStructureOfDelaun.hxx> |
fc9b36d6 |
28 | #include <BRepMesh_GeomTool.hxx> |
b7c077b9 |
29 | #include <TColStd_Array1OfInteger.hxx> |
30 | #include <TColStd_SequenceOfInteger.hxx> |
31 | #include <TColStd_MapOfInteger.hxx> |
304c45c8 |
32 | |
33 | class Bnd_B2d; |
34 | class Bnd_Box2d; |
304c45c8 |
35 | class BRepMesh_Vertex; |
304c45c8 |
36 | |
ebc93ae7 |
37 | //! Compute the Delaunay's triangulation with the algorithm of Watson. |
38 | class BRepMesh_Delaun |
39 | { |
304c45c8 |
40 | public: |
41 | |
42 | DEFINE_STANDARD_ALLOC |
43 | |
ebc93ae7 |
44 | //! Creates the triangulation with an empty Mesh data structure. |
848fa7e3 |
45 | Standard_EXPORT BRepMesh_Delaun (BRepMesh::Array1OfVertexOfDelaun& theVertices); |
304c45c8 |
46 | |
ebc93ae7 |
47 | //! Creates the triangulation with an existent Mesh data structure. |
48 | Standard_EXPORT BRepMesh_Delaun (const Handle(BRepMesh_DataStructureOfDelaun)& theOldMesh, |
848fa7e3 |
49 | BRepMesh::Array1OfVertexOfDelaun& theVertices); |
304c45c8 |
50 | |
ebc93ae7 |
51 | //! Creates the triangulation with an existant Mesh data structure. |
52 | Standard_EXPORT BRepMesh_Delaun (const Handle(BRepMesh_DataStructureOfDelaun)& theOldMesh, |
848fa7e3 |
53 | BRepMesh::Array1OfInteger& theVertexIndices); |
304c45c8 |
54 | |
ebc93ae7 |
55 | //! Initializes the triangulation with an array of vertices. |
848fa7e3 |
56 | Standard_EXPORT void Init (BRepMesh::Array1OfVertexOfDelaun& theVertices); |
304c45c8 |
57 | |
ebc93ae7 |
58 | //! Removes a vertex from the triangulation. |
59 | Standard_EXPORT void RemoveVertex (const BRepMesh_Vertex& theVertex); |
304c45c8 |
60 | |
ebc93ae7 |
61 | //! Adds some vertices into the triangulation. |
848fa7e3 |
62 | Standard_EXPORT void AddVertices (BRepMesh::Array1OfVertexOfDelaun& theVertices); |
304c45c8 |
63 | |
ebc93ae7 |
64 | //! Modify mesh to use the edge. |
65 | //! @return True if done |
66 | Standard_EXPORT Standard_Boolean UseEdge (const Standard_Integer theEdge); |
304c45c8 |
67 | |
ebc93ae7 |
68 | //! Gives the Mesh data structure. |
fc9b36d6 |
69 | inline const Handle(BRepMesh_DataStructureOfDelaun)& Result() const |
304c45c8 |
70 | { |
71 | return myMeshData; |
72 | } |
73 | |
ebc93ae7 |
74 | //! Gives the list of frontier edges. |
848fa7e3 |
75 | inline BRepMesh::HMapOfInteger Frontier() const |
304c45c8 |
76 | { |
ebc93ae7 |
77 | return getEdgesByType (BRepMesh_Frontier); |
304c45c8 |
78 | } |
79 | |
ebc93ae7 |
80 | //! Gives the list of internal edges. |
848fa7e3 |
81 | inline BRepMesh::HMapOfInteger InternalEdges() const |
304c45c8 |
82 | { |
ebc93ae7 |
83 | return getEdgesByType (BRepMesh_Fixed); |
304c45c8 |
84 | } |
85 | |
ebc93ae7 |
86 | //! Gives the list of free edges used only one time |
848fa7e3 |
87 | inline BRepMesh::HMapOfInteger FreeEdges() const |
304c45c8 |
88 | { |
ebc93ae7 |
89 | return getEdgesByType (BRepMesh_Free); |
304c45c8 |
90 | } |
ebc93ae7 |
91 | |
92 | //! Gives vertex with the given index |
93 | inline const BRepMesh_Vertex& GetVertex (const Standard_Integer theIndex) const |
304c45c8 |
94 | { |
ebc93ae7 |
95 | return myMeshData->GetNode (theIndex); |
304c45c8 |
96 | } |
97 | |
ebc93ae7 |
98 | //! Gives edge with the given index |
99 | inline const BRepMesh_Edge& GetEdge (const Standard_Integer theIndex) const |
304c45c8 |
100 | { |
ebc93ae7 |
101 | return myMeshData->GetLink (theIndex); |
304c45c8 |
102 | } |
103 | |
ebc93ae7 |
104 | //! Gives triangle with the given index |
105 | inline const BRepMesh_Triangle& GetTriangle (const Standard_Integer theIndex) const |
304c45c8 |
106 | { |
ebc93ae7 |
107 | return myMeshData->GetElement (theIndex); |
304c45c8 |
108 | } |
109 | |
74da0216 |
110 | //! Returns tool used to build mesh consistent to Delaunay criteria. |
111 | inline const BRepMesh_CircleTool& Circles() const |
112 | { |
113 | return myCircles; |
114 | } |
115 | |
ebc93ae7 |
116 | //! Test is the given triangle contains the given vertex. |
117 | //! If theEdgeOn != 0 the vertex lies onto the edge index |
118 | //! returned through this parameter. |
119 | Standard_EXPORT Standard_Boolean Contains (const Standard_Integer theTriangleId, |
304c45c8 |
120 | const BRepMesh_Vertex& theVertex, |
ebc93ae7 |
121 | Standard_Integer& theEdgeOn) const; |
304c45c8 |
122 | |
123 | private: |
124 | |
304c45c8 |
125 | enum ReplaceFlag |
126 | { |
127 | Replace, |
128 | InsertAfter, |
129 | InsertBefore |
130 | }; |
131 | |
848fa7e3 |
132 | typedef NCollection_DataMap<Standard_Integer, BRepMesh::MapOfInteger> DataMapOfMap; |
304c45c8 |
133 | |
ebc93ae7 |
134 | //! Add boundig box for edge defined by start & end point to |
135 | //! the given vector of bounding boxes for triangulation edges. |
848fa7e3 |
136 | void fillBndBox (BRepMesh::SequenceOfBndB2d& theBoxes, |
137 | const BRepMesh_Vertex& theV1, |
138 | const BRepMesh_Vertex& theV2); |
304c45c8 |
139 | |
ebc93ae7 |
140 | //! Gives the list of edges with type defined by the input parameter. |
141 | //! If the given type is BRepMesh_Free returns list of edges |
142 | //! that have number of connected elements less or equal 1. |
848fa7e3 |
143 | BRepMesh::HMapOfInteger getEdgesByType (const BRepMesh_DegreeOfFreedom theEdgeType) const; |
304c45c8 |
144 | |
ebc93ae7 |
145 | //! Create super mesh and run triangulation procedure. |
848fa7e3 |
146 | void perform (Bnd_Box2d& theBndBox, |
147 | BRepMesh::Array1OfInteger& theVertexIndices); |
304c45c8 |
148 | |
ebc93ae7 |
149 | //! Build the super mesh. |
150 | void superMesh (const Bnd_Box2d& theBox); |
304c45c8 |
151 | |
ebc93ae7 |
152 | //! Computes the triangulation and adds the vertices, |
153 | //! edges and triangles to the Mesh data structure. |
848fa7e3 |
154 | void compute (BRepMesh::Array1OfInteger& theVertexIndices); |
304c45c8 |
155 | |
ebc93ae7 |
156 | //! Adjust the mesh on the frontier. |
304c45c8 |
157 | void frontierAdjust(); |
158 | |
ebc93ae7 |
159 | //! Find left polygon of the given edge and call meshPolygon. |
2caff0b3 |
160 | Standard_Boolean meshLeftPolygonOf( |
161 | const Standard_Integer theEdgeIndex, |
162 | const Standard_Boolean isForward, |
163 | BRepMesh::HMapOfInteger theSkipped = NULL); |
ebc93ae7 |
164 | |
165 | //! Find next link starting from the given node and has maximum |
166 | //! angle respect the given reference link. |
167 | //! Each time the next link is found other neighbor links at the pivot |
168 | //! node are marked as leprous and will be excluded from consideration |
169 | //! next time until a hanging end is occured. |
848fa7e3 |
170 | Standard_Integer findNextPolygonLink (const Standard_Integer& theFirstNode, |
171 | const Standard_Integer& thePivotNode, |
172 | const BRepMesh_Vertex& thePivotVertex, |
173 | const gp_Vec2d& theRefLinkDir, |
174 | const BRepMesh::SequenceOfBndB2d& theBoxes, |
175 | const BRepMesh::SequenceOfInteger& thePolygon, |
176 | const BRepMesh::HMapOfInteger theSkipped, |
177 | const Standard_Boolean& isSkipLeprous, |
178 | BRepMesh::MapOfInteger& theLeprousLinks, |
179 | BRepMesh::MapOfInteger& theDeadLinks, |
180 | Standard_Integer& theNextPivotNode, |
181 | gp_Vec2d& theNextLinkDir, |
182 | Bnd_B2d& theNextLinkBndBox); |
304c45c8 |
183 | |
ebc93ae7 |
184 | //! Check is the given link intersects the polygon boundaries. |
185 | //! Returns bounding box for the given link trough the theLinkBndBox parameter. |
848fa7e3 |
186 | Standard_Boolean checkIntersection (const BRepMesh_Edge& theLink, |
187 | const BRepMesh::SequenceOfInteger& thePolygon, |
188 | const BRepMesh::SequenceOfBndB2d& thePolyBoxes, |
189 | const Standard_Boolean isConsiderEndPointTouch, |
190 | const Standard_Boolean isConsiderPointOnEdge, |
191 | const Standard_Boolean isSkipLastEdge, |
192 | Bnd_B2d& theLinkBndBox) const; |
304c45c8 |
193 | |
ebc93ae7 |
194 | //! Triangulatiion of a closed polygon described by the list |
195 | //! of indexes of its edges in the structure. |
196 | //! (negative index means reversed edge) |
848fa7e3 |
197 | void meshPolygon (BRepMesh::SequenceOfInteger& thePolygon, |
198 | BRepMesh::SequenceOfBndB2d& thePolyBoxes, |
199 | BRepMesh::HMapOfInteger theSkipped = NULL); |
304c45c8 |
200 | |
0a9b38ef |
201 | //! Decomposes the given closed simple polygon (polygon without glued edges |
202 | //! and loops) on two simpler ones by adding new link at the most thin part |
203 | //! in respect to end point of the first link. |
204 | //! In case if source polygon consists of three links, creates new triangle |
205 | //! and clears source container. |
206 | //! @param thePolygon source polygon to be decomposed (first part of decomposition). |
207 | //! @param thePolyBoxes bounding boxes corresponded to source polygon's links. |
208 | //! @param thePolygonCut product of decomposition of source polygon (second part of decomposition). |
209 | //! @param thePolyBoxesCut bounding boxes corresponded to resulting polygon's links. |
210 | void decomposeSimplePolygon ( |
211 | BRepMesh::SequenceOfInteger& thePolygon, |
212 | BRepMesh::SequenceOfBndB2d& thePolyBoxes, |
213 | BRepMesh::SequenceOfInteger& thePolygonCut, |
214 | BRepMesh::SequenceOfBndB2d& thePolyBoxesCut); |
304c45c8 |
215 | |
216 | //! Triangulation of closed polygon containing only three edges. |
848fa7e3 |
217 | inline Standard_Boolean meshElementaryPolygon (const BRepMesh::SequenceOfInteger& thePolygon); |
304c45c8 |
218 | |
ebc93ae7 |
219 | //! Creates the triangles beetween the given node and the given polyline. |
848fa7e3 |
220 | void createTriangles (const Standard_Integer theVertexIndex, |
221 | BRepMesh::MapOfIntegerInteger& thePoly); |
304c45c8 |
222 | |
ebc93ae7 |
223 | //! Add a triangle based on the given oriented edges into mesh |
224 | inline void addTriangle (const Standard_Integer (&theEdgesId)[3], |
304c45c8 |
225 | const Standard_Boolean (&theEdgesOri)[3], |
ebc93ae7 |
226 | const Standard_Integer (&theNodesId)[3]); |
227 | |
228 | //! Deletes the triangle with the given index and adds the free edges into the map. |
229 | //! When an edge is suppressed more than one time it is destroyed. |
848fa7e3 |
230 | void deleteTriangle (const Standard_Integer theIndex, |
231 | BRepMesh::MapOfIntegerInteger& theLoopEdges); |
ebc93ae7 |
232 | |
233 | //! Returns start and end nodes of the given edge in respect to its orientation. |
234 | void getOrientedNodes (const BRepMesh_Edge& theEdge, |
235 | const Standard_Boolean isForward, |
236 | Standard_Integer* theNodes) const; |
237 | |
238 | //! Processes loop within the given polygon formed by range of its |
239 | //! links specified by start and end link indices. |
848fa7e3 |
240 | void processLoop (const Standard_Integer theLinkFrom, |
241 | const Standard_Integer theLinkTo, |
242 | const BRepMesh::SequenceOfInteger& thePolygon, |
243 | const BRepMesh::SequenceOfBndB2d& thePolyBoxes); |
304c45c8 |
244 | |
245 | //! Creates new link based on the given nodes and updates the given polygon. |
848fa7e3 |
246 | Standard_Integer createAndReplacePolygonLink (const Standard_Integer theNodes[], |
247 | const gp_Pnt2d thePnts [], |
248 | const Standard_Integer theRootIndex, |
249 | const ReplaceFlag theReplaceFlag, |
250 | BRepMesh::SequenceOfInteger& thePolygon, |
251 | BRepMesh::SequenceOfBndB2d& thePolyBoxes); |
304c45c8 |
252 | |
ebc93ae7 |
253 | //! Creates the triangles on new nodes. |
848fa7e3 |
254 | void createTrianglesOnNewVertices (BRepMesh::Array1OfInteger& theVertexIndices); |
304c45c8 |
255 | |
ebc93ae7 |
256 | //! Cleanup mesh from the free triangles. |
304c45c8 |
257 | void cleanupMesh(); |
258 | |
259 | //! Goes through the neighbour triangles around the given node started |
260 | //! from the given link, returns TRUE if some triangle has a bounding |
261 | //! frontier edge or FALSE elsewhere. |
262 | //! Stop link is used to prevent cycles. |
263 | //! Previous element Id is used to identify next neighbor element. |
ebc93ae7 |
264 | Standard_Boolean isBoundToFrontier (const Standard_Integer theRefNodeId, |
265 | const Standard_Integer theRefLinkId, |
266 | const Standard_Integer theStopLinkId, |
267 | const Standard_Integer thePrevElementId); |
268 | |
269 | //! Remove internal triangles from the given polygon. |
848fa7e3 |
270 | void cleanupPolygon (const BRepMesh::SequenceOfInteger& thePolygon, |
271 | const BRepMesh::SequenceOfBndB2d& thePolyBoxes); |
ebc93ae7 |
272 | |
273 | //! Checks is the given vertex lies inside the polygon. |
848fa7e3 |
274 | Standard_Boolean isVertexInsidePolygon (const Standard_Integer& theVertexId, |
275 | const BRepMesh::VectorOfInteger& thePolygonVertices) const; |
ebc93ae7 |
276 | |
277 | //! Remove all triangles and edges that are placed inside the polygon or crossed it. |
848fa7e3 |
278 | void killTrianglesAroundVertex (const Standard_Integer theZombieNodeId, |
279 | const BRepMesh::VectorOfInteger& thePolyVertices, |
280 | const BRepMesh::MapOfInteger& thePolyVerticesFindMap, |
281 | const BRepMesh::SequenceOfInteger& thePolygon, |
282 | const BRepMesh::SequenceOfBndB2d& thePolyBoxes, |
283 | BRepMesh::MapOfInteger& theSurvivedLinks, |
284 | BRepMesh::MapOfIntegerInteger& theLoopEdges); |
304c45c8 |
285 | |
ebc93ae7 |
286 | //! Checks is the given link crosses the polygon boundary. |
287 | //! If yes, kills its triangles and checks neighbor links on boundary intersection. Does nothing elsewhere. |
848fa7e3 |
288 | void killTrianglesOnIntersectingLinks (const Standard_Integer& theLinkToCheckId, |
289 | const BRepMesh_Edge& theLinkToCheck, |
290 | const Standard_Integer& theEndPoint, |
291 | const BRepMesh::SequenceOfInteger& thePolygon, |
292 | const BRepMesh::SequenceOfBndB2d& thePolyBoxes, |
293 | BRepMesh::MapOfInteger& theSurvivedLinks, |
294 | BRepMesh::MapOfIntegerInteger& theLoopEdges); |
304c45c8 |
295 | |
ebc93ae7 |
296 | //! Kill triangles bound to the given link. |
848fa7e3 |
297 | void killLinkTriangles (const Standard_Integer& theLinkId, |
298 | BRepMesh::MapOfIntegerInteger& theLoopEdges); |
304c45c8 |
299 | |
ebc93ae7 |
300 | //! Calculates distances between the given point and edges of triangle. |
301 | Standard_Real calculateDist (const gp_XY theVEdges[3], |
304c45c8 |
302 | const gp_XY thePoints[3], |
303 | const Standard_Integer theEdgesId[3], |
304 | const BRepMesh_Vertex& theVertex, |
305 | Standard_Real theDistance[3], |
306 | Standard_Real theSqModulus[3], |
ebc93ae7 |
307 | Standard_Integer& theEdgeOn) const; |
308 | |
ebc93ae7 |
309 | //! Checks intersection between the two segments. |
fc9b36d6 |
310 | BRepMesh_GeomTool::IntFlag intSegSeg( |
01a6e62b |
311 | const BRepMesh_Edge& theEdge1, |
312 | const BRepMesh_Edge& theEdge2, |
313 | const Standard_Boolean isConsiderEndPointTouch, |
314 | const Standard_Boolean isConsiderPointOnEdge, |
315 | gp_Pnt2d& theIntPnt) const; |
304c45c8 |
316 | |
ebc93ae7 |
317 | //! Returns area of the loop of the given polygon defined by indices of its start and end links. |
848fa7e3 |
318 | Standard_Real polyArea (const BRepMesh::SequenceOfInteger& thePolygon, |
319 | const Standard_Integer theStartIndex, |
320 | const Standard_Integer theEndIndex) const; |
ebc93ae7 |
321 | |
304c45c8 |
322 | private: |
323 | |
ebc93ae7 |
324 | Handle(BRepMesh_DataStructureOfDelaun) myMeshData; |
ebc93ae7 |
325 | BRepMesh_CircleTool myCircles; |
326 | Standard_Integer mySupVert[3]; |
327 | BRepMesh_Triangle mySupTrian; |
328 | |
304c45c8 |
329 | }; |
330 | |
331 | #endif |