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