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