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