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