Commit | Line | Data |
---|---|---|
b311480e | 1 | // Created on: 1993-05-12 |
2 | // Created by: Didier PIFFAULT | |
3 | // Copyright (c) 1993-1999 Matra Datavision | |
4 | // Copyright (c) 1999-2012 OPEN CASCADE SAS | |
5 | // | |
6 | // The content of this file is subject to the Open CASCADE Technology Public | |
7 | // License Version 6.5 (the "License"). You may not use the content of this file | |
8 | // except in compliance with the License. Please obtain a copy of the License | |
9 | // at http://www.opencascade.org and read it completely before using this file. | |
10 | // | |
11 | // The Initial Developer of the Original Code is Open CASCADE S.A.S., having its | |
12 | // main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France. | |
13 | // | |
14 | // The Original Code and all software distributed under the License is | |
15 | // distributed on an "AS IS" basis, without warranty of any kind, and the | |
16 | // Initial Developer hereby disclaims all such warranties, including without | |
17 | // limitation, any warranties of merchantability, fitness for a particular | |
18 | // purpose or non-infringement. Please see the License for the specific terms | |
19 | // and conditions governing the rights and limitations under the License. | |
20 | ||
0d88155b O |
21 | |
22 | #include <BRepMesh_Delaun.ixx> | |
23 | #include <gp_XY.hxx> | |
24 | #include <gp_Pnt2d.hxx> | |
25 | #include <gp_Vec2d.hxx> | |
26 | #include <TColStd_ListIteratorOfListOfInteger.hxx> | |
27 | #include <TColStd_ListOfInteger.hxx> | |
28 | #include <Precision.hxx> | |
29 | #include <Bnd_Box2d.hxx> | |
30 | #include <gp.hxx> | |
31 | #include <TColStd_MapOfInteger.hxx> | |
90dc2e5b | 32 | #include <TColStd_MapIteratorOfMapOfInteger.hxx> |
2b59653e | 33 | #include <TColStd_Array1OfBoolean.hxx> |
0d88155b O |
34 | #include <BRepMesh_MapOfIntegerInteger.hxx> |
35 | #include <BRepMesh_HeapSortIndexedVertexOfDelaun.hxx> | |
36 | #include <BRepMesh_ComparatorOfIndexedVertexOfDelaun.hxx> | |
37 | #include <BRepMesh_HeapSortIndexedVertexOfDelaun.hxx> | |
38 | #include <BRepMesh_SelectorOfDataStructureOfDelaun.hxx> | |
39 | #include <BRepMesh_HeapSortVertexOfDelaun.hxx> | |
40 | #include <BRepMesh_ComparatorOfVertexOfDelaun.hxx> | |
2b59653e E |
41 | #include <TColgp_Array1OfXY.hxx> |
42 | #include <TColStd_Array1OfReal.hxx> | |
0d88155b O |
43 | |
44 | typedef TColStd_ListIteratorOfListOfInteger IteratorOnListOfInteger; | |
45 | typedef TColStd_ListOfInteger ListOfInteger; | |
46 | ||
90dc2e5b | 47 | const Standard_Real EPSEPS = Precision::PConfusion() * Precision::PConfusion(); |
0d88155b O |
48 | const gp_XY SortingDirection(M_SQRT1_2, M_SQRT1_2); |
49 | ||
90dc2e5b | 50 | //======================================================================= |
51 | //function : fillBndBox | |
52 | //purpose : Add boundig box for edge defined by start & end point to | |
53 | // the given vector of bounding boxes for triangulation edges | |
54 | //======================================================================= | |
55 | static void fillBndBox( NCollection_Vector <Bnd_Box2d>& theVB, | |
56 | const BRepMesh_Vertex& theV1, | |
57 | const BRepMesh_Vertex& theV2 ) | |
58 | { | |
59 | Bnd_Box2d aBox; | |
60 | aBox.Add( gp_Pnt2d( theV1.Coord() ) ); | |
61 | aBox.Add( gp_Pnt2d( theV2.Coord() ) ); | |
62 | theVB.Append( aBox ); | |
63 | } | |
0d88155b O |
64 | |
65 | //======================================================================= | |
66 | //function : BRepMesh_Delaun | |
90dc2e5b | 67 | //purpose : Creates the triangulation with an empty Mesh data structure |
0d88155b | 68 | //======================================================================= |
90dc2e5b | 69 | BRepMesh_Delaun::BRepMesh_Delaun( BRepMesh_Array1OfVertexOfDelaun& theVertices, |
70 | const Standard_Boolean isPositive ) | |
71 | : myPositiveOrientation( isPositive ), | |
72 | myCircles( theVertices.Length(), new NCollection_IncAllocator() ) | |
0d88155b | 73 | { |
90dc2e5b | 74 | if ( theVertices.Length() > 2 ) |
75 | { | |
76 | myMeshData = new BRepMesh_DataStructureOfDelaun( new NCollection_IncAllocator(), | |
77 | theVertices.Length() ); | |
78 | Init( theVertices ); | |
0d88155b O |
79 | } |
80 | } | |
81 | ||
82 | //======================================================================= | |
83 | //function : BRepMesh_Delaun | |
90dc2e5b | 84 | //purpose : Creates the triangulation with and existent Mesh data structure |
0d88155b | 85 | //======================================================================= |
90dc2e5b | 86 | BRepMesh_Delaun::BRepMesh_Delaun ( const Handle( BRepMesh_DataStructureOfDelaun )& theOldMesh, |
87 | BRepMesh_Array1OfVertexOfDelaun& theVertices, | |
88 | const Standard_Boolean isPositive ) | |
89 | : myPositiveOrientation( isPositive ), | |
90 | myCircles( theVertices.Length(), theOldMesh->Allocator() ) | |
0d88155b | 91 | { |
90dc2e5b | 92 | myMeshData = theOldMesh; |
93 | if ( theVertices.Length() > 2 ) | |
94 | Init( theVertices ); | |
0d88155b O |
95 | } |
96 | ||
90dc2e5b | 97 | //======================================================================= |
98 | //function : BRepMesh_Delaun | |
99 | //purpose : Creates the triangulation with and existent Mesh data structure | |
100 | //======================================================================= | |
101 | BRepMesh_Delaun::BRepMesh_Delaun( const Handle( BRepMesh_DataStructureOfDelaun )& theOldMesh, | |
102 | TColStd_Array1OfInteger& theVertexIndexes, | |
103 | const Standard_Boolean isPositive ) | |
104 | : myPositiveOrientation( isPositive ), | |
105 | myCircles( theVertexIndexes.Length(), theOldMesh->Allocator() ) | |
106 | { | |
107 | myMeshData = theOldMesh; | |
108 | if ( theVertexIndexes.Length() > 2 ) | |
109 | { | |
110 | Bnd_Box2d aBox; | |
111 | Standard_Integer anIndex = theVertexIndexes.Lower(); | |
112 | Standard_Integer anUpper = theVertexIndexes.Upper(); | |
113 | for ( ; anIndex <= anUpper; ++anIndex ) | |
114 | aBox.Add( gp_Pnt2d( GetVertex( theVertexIndexes( anIndex) ).Coord() ) ); | |
115 | ||
116 | Perform( aBox, theVertexIndexes ); | |
117 | } | |
118 | } | |
0d88155b O |
119 | |
120 | //======================================================================= | |
121 | //function : Init | |
90dc2e5b | 122 | //purpose : Initializes the triangulation with an Array of Vertex |
0d88155b | 123 | //======================================================================= |
90dc2e5b | 124 | void BRepMesh_Delaun::Init( BRepMesh_Array1OfVertexOfDelaun& theVertices ) |
0d88155b | 125 | { |
90dc2e5b | 126 | Bnd_Box2d aBox; |
127 | Standard_Integer aLowerIdx = theVertices.Lower(); | |
128 | Standard_Integer anUpperIdx = theVertices.Upper(); | |
129 | TColStd_Array1OfInteger aVertexIndexes( aLowerIdx, anUpperIdx ); | |
130 | ||
131 | Standard_Integer anIndex = aLowerIdx; | |
132 | for ( ; anIndex <= anUpperIdx; ++anIndex ) | |
133 | { | |
134 | aBox.Add( gp_Pnt2d( theVertices( anIndex ).Coord() ) ); | |
135 | aVertexIndexes( anIndex ) = myMeshData->AddNode( theVertices( anIndex ) ); | |
0d88155b O |
136 | } |
137 | ||
90dc2e5b | 138 | Perform( aBox, aVertexIndexes ); |
0d88155b O |
139 | } |
140 | ||
90dc2e5b | 141 | //======================================================================= |
142 | //function : Perform | |
143 | //purpose : Create super mesh and run triangulation procedure | |
144 | //======================================================================= | |
145 | void BRepMesh_Delaun::Perform( Bnd_Box2d& theBndBox, | |
146 | TColStd_Array1OfInteger& theVertexIndexes ) | |
147 | { | |
148 | theBndBox.Enlarge( Precision::PConfusion() ); | |
149 | SuperMesh( theBndBox ); | |
150 | ||
151 | BRepMesh_HeapSortIndexedVertexOfDelaun::Sort( theVertexIndexes, | |
152 | BRepMesh_ComparatorOfIndexedVertexOfDelaun( SortingDirection, | |
153 | Precision::PConfusion(), myMeshData ) ); | |
154 | ||
155 | Compute( theVertexIndexes ); | |
156 | } | |
0d88155b O |
157 | |
158 | //======================================================================= | |
90dc2e5b | 159 | //function : SuperMesh |
160 | //purpose : Build the super mesh | |
0d88155b | 161 | //======================================================================= |
90dc2e5b | 162 | void BRepMesh_Delaun::SuperMesh( const Bnd_Box2d& theBox ) |
0d88155b | 163 | { |
90dc2e5b | 164 | Standard_Real aMinX, aMinY, aMaxX, aMaxY; |
165 | theBox.Get( aMinX, aMinY, aMaxX, aMaxY ); | |
166 | Standard_Real aDeltaX = aMaxX - aMinX; | |
167 | Standard_Real aDeltaY = aMaxY - aMinY; | |
168 | ||
169 | Standard_Real aDeltaMin = Min( aDeltaX, aDeltaY ); | |
170 | Standard_Real aDeltaMax = Max( aDeltaX, aDeltaY ); | |
171 | Standard_Real aDelta = aDeltaX + aDeltaY; | |
172 | ||
173 | myCircles.SetMinMaxSize( gp_XY( aMinX, aMinY ), gp_XY( aMaxX, aMaxY ) ); | |
174 | ||
175 | Standard_Integer aScaler = 2; | |
176 | if ( myMeshData->NbNodes() > 100 ) | |
177 | aScaler = 5; | |
178 | else if( myMeshData->NbNodes() > 1000 ) | |
179 | aScaler = 7; | |
180 | ||
181 | myCircles.SetCellSize( aDeltaX / aScaler, | |
182 | aDeltaY / aScaler ); | |
0d88155b | 183 | |
90dc2e5b | 184 | mySupVert1 = myMeshData->AddNode( |
185 | BRepMesh_Vertex( ( aMinX + aMaxX ) / 2, aMaxY + aDeltaMax, BRepMesh_Free ) ); | |
186 | ||
187 | mySupVert2 = myMeshData->AddNode( | |
188 | BRepMesh_Vertex( aMinX - aDelta, aMinY - aDeltaMin, BRepMesh_Free ) ); | |
189 | ||
190 | mySupVert3 = myMeshData->AddNode( | |
191 | BRepMesh_Vertex( aMaxX + aDelta, aMinY - aDeltaMin, BRepMesh_Free ) ); | |
192 | ||
193 | if ( !myPositiveOrientation ) | |
194 | { | |
195 | Standard_Integer aTmp; | |
196 | aTmp = mySupVert2; | |
197 | mySupVert2 = mySupVert3; | |
198 | mySupVert3 = aTmp; | |
2b59653e | 199 | } |
90dc2e5b | 200 | |
201 | Standard_Integer anEdge1, anEdge2, anEdge3; | |
202 | ||
203 | anEdge1 = myMeshData->AddLink( BRepMesh_Edge( mySupVert1, mySupVert2, BRepMesh_Free ) ); | |
204 | anEdge2 = myMeshData->AddLink( BRepMesh_Edge( mySupVert2, mySupVert3, BRepMesh_Free ) ); | |
205 | anEdge3 = myMeshData->AddLink( BRepMesh_Edge( mySupVert3, mySupVert1, BRepMesh_Free ) ); | |
206 | ||
207 | mySupTrian = BRepMesh_Triangle( Abs( anEdge1 ), Abs( anEdge2 ), Abs( anEdge3 ), | |
208 | ( anEdge1 > 0 ), ( anEdge2 > 0 ), ( anEdge1 > 0), BRepMesh_Free); | |
2b59653e E |
209 | } |
210 | ||
211 | //======================================================================= | |
90dc2e5b | 212 | //function : DeleteTriangle |
213 | //purpose : The concerned triangles are deleted and the freed edges are added in | |
214 | // <theLoopEdges>. If an edge is added twice, it does not exist and | |
215 | // it is necessary to destroy it. This corresponds to the destruction of two | |
216 | // connected triangles. | |
2b59653e | 217 | //======================================================================= |
90dc2e5b | 218 | void BRepMesh_Delaun::DeleteTriangle( const Standard_Integer theIndex, |
219 | BRepMesh_MapOfIntegerInteger& theLoopEdges ) | |
2b59653e | 220 | { |
90dc2e5b | 221 | myCircles.Delete( theIndex ); |
0d88155b | 222 | |
90dc2e5b | 223 | Standard_Integer e[3]; |
224 | Standard_Boolean o[3]; | |
225 | GetTriangle( theIndex ).Edges( e[0], e[1], e[2], | |
226 | o[0], o[1], o[2] ); | |
227 | ||
228 | myMeshData->RemoveElement( theIndex ); | |
0d88155b | 229 | |
90dc2e5b | 230 | for ( Standard_Integer i = 0; i < 3; ++i ) |
231 | { | |
232 | if ( !theLoopEdges.Bind( e[i], o[i] ) ) | |
233 | { | |
234 | theLoopEdges.UnBind( e[i] ); | |
235 | myMeshData->RemoveLink( e[i] ); | |
236 | } | |
237 | } | |
0d88155b O |
238 | } |
239 | ||
240 | //======================================================================= | |
241 | //function : Compute | |
90dc2e5b | 242 | //purpose : Computes the triangulation and add the vertices edges and |
243 | // triangles to the Mesh data structure | |
0d88155b | 244 | //======================================================================= |
90dc2e5b | 245 | void BRepMesh_Delaun::Compute( TColStd_Array1OfInteger& theVertexIndexes ) |
0d88155b O |
246 | { |
247 | // Insertion of edges of super triangles in the list of free edges: | |
90dc2e5b | 248 | BRepMesh_MapOfIntegerInteger aLoopEdges( 10, myMeshData->Allocator() ); |
249 | Standard_Integer e[3]; | |
250 | Standard_Boolean o[3]; | |
251 | mySupTrian.Edges( e[0], e[1], e[2], | |
252 | o[0], o[1], o[2] ); | |
253 | ||
254 | aLoopEdges.Bind( e[0], Standard_True ); | |
255 | aLoopEdges.Bind( e[1], Standard_True ); | |
256 | aLoopEdges.Bind( e[2], Standard_True ); | |
257 | ||
258 | if ( theVertexIndexes.Length() > 0 ) | |
259 | { | |
260 | // Creation of 3 trianglers with the first node and the edges of the super triangle: | |
261 | Standard_Integer anVertexIdx = theVertexIndexes.Lower(); | |
262 | CreateTriangles( theVertexIndexes( anVertexIdx ), aLoopEdges ); | |
0d88155b | 263 | |
90dc2e5b | 264 | // Add other nodes to the mesh |
265 | CreateTrianglesOnNewVertices( theVertexIndexes ); | |
0d88155b O |
266 | } |
267 | ||
90dc2e5b | 268 | // Destruction of triangles containing a top of the super triangle |
269 | BRepMesh_SelectorOfDataStructureOfDelaun aSelector( myMeshData ); | |
270 | aSelector.NeighboursOfNode( mySupVert1 ); | |
271 | aSelector.NeighboursOfNode( mySupVert2 ); | |
272 | aSelector.NeighboursOfNode( mySupVert3 ); | |
273 | ||
274 | aLoopEdges.Clear(); | |
275 | BRepMesh_MapOfInteger::Iterator aFreeTriangles( aSelector.Elements() ); | |
276 | for ( ; aFreeTriangles.More(); aFreeTriangles.Next() ) | |
277 | DeleteTriangle( aFreeTriangles.Key(), aLoopEdges ); | |
278 | ||
279 | // All edges that remain free are removed from aLoopEdges; | |
280 | // only the boundary edges of the triangulation remain there | |
281 | BRepMesh_MapOfIntegerInteger::Iterator aFreeEdges( aLoopEdges ); | |
282 | for ( ; aFreeEdges.More(); aFreeEdges.Next() ) | |
283 | { | |
284 | if ( myMeshData->ElemConnectedTo( aFreeEdges.Key() ).IsEmpty() ) | |
285 | myMeshData->RemoveLink( aFreeEdges.Key() ); | |
0d88155b O |
286 | } |
287 | ||
90dc2e5b | 288 | // The tops of the super triangle are destroyed |
289 | myMeshData->RemoveNode( mySupVert1 ); | |
290 | myMeshData->RemoveNode( mySupVert2 ); | |
291 | myMeshData->RemoveNode( mySupVert3 ); | |
0d88155b O |
292 | } |
293 | ||
0d88155b | 294 | //======================================================================= |
90dc2e5b | 295 | //function : CreateTriangles |
296 | //purpose : Creates the triangles beetween the node and the polyline. | |
0d88155b | 297 | //======================================================================= |
90dc2e5b | 298 | void BRepMesh_Delaun::CreateTriangles ( const Standard_Integer theVertexIndex, |
299 | BRepMesh_MapOfIntegerInteger& thePoly ) | |
0d88155b | 300 | { |
90dc2e5b | 301 | ListOfInteger aLoopEdges, anExternalEdges; |
302 | const gp_XY& aVertexCoord = myMeshData->GetNode( theVertexIndex ).Coord(); | |
303 | ||
304 | BRepMesh_MapOfIntegerInteger::Iterator anEdges( thePoly ); | |
305 | for ( ; anEdges.More(); anEdges.Next() ) | |
2b59653e | 306 | { |
90dc2e5b | 307 | const BRepMesh_Edge& anEdge = GetEdge( anEdges.Key() ); |
308 | Standard_Integer aFirstNode = anEdge.FirstNode(); | |
309 | Standard_Integer aLastNode = anEdge.LastNode(); | |
310 | Standard_Boolean isPositive = (Standard_Boolean)thePoly( anEdges.Key() ); | |
311 | if ( !isPositive ) | |
312 | { | |
313 | Standard_Integer aTmp; | |
314 | aTmp = aFirstNode; | |
315 | aFirstNode = aLastNode; | |
316 | aLastNode = aTmp; | |
0d88155b | 317 | } |
0d88155b | 318 | |
90dc2e5b | 319 | const BRepMesh_Vertex& aFirstVertex = GetVertex( aFirstNode ); |
320 | const BRepMesh_Vertex& aLastVertex = GetVertex( aLastNode ); | |
0d88155b | 321 | |
90dc2e5b | 322 | gp_XY aVEdge1, aVEdge2, aVEdge3; |
323 | aVEdge1 = aFirstVertex.Coord(); | |
324 | aVEdge1.Subtract( aVertexCoord ); | |
325 | ||
326 | aVEdge2 = aLastVertex.Coord(); | |
327 | aVEdge2.Subtract( aFirstVertex.Coord() ); | |
328 | ||
329 | aVEdge3 = aVertexCoord; | |
330 | aVEdge3.Subtract( aLastVertex.Coord() ); | |
0d88155b | 331 | |
90dc2e5b | 332 | Standard_Real aDist12 = 0., aDist23 = 0.; |
333 | Standard_Real aV2Len = aVEdge2.Modulus(); | |
334 | if ( aV2Len > Precision::PConfusion() ) | |
335 | { | |
336 | aVEdge2.SetCoord( aVEdge2.X() / aV2Len, | |
337 | aVEdge2.Y() / aV2Len ); | |
338 | ||
339 | aDist12 = aVEdge1 ^ aVEdge2; | |
340 | aDist23 = aVEdge2 ^ aVEdge3; | |
2b59653e | 341 | } |
0d88155b | 342 | |
90dc2e5b | 343 | if ( Abs( aDist12 ) >= Precision::PConfusion() && |
344 | Abs( aDist23 ) >= Precision::PConfusion() ) | |
2b59653e | 345 | { |
90dc2e5b | 346 | Standard_Boolean isSensOK; |
347 | if ( myPositiveOrientation ) | |
348 | isSensOK = ( aDist12 > 0. && aDist23 > 0.); | |
349 | else | |
350 | isSensOK = ( aDist12 < 0. && aDist23 < 0.); | |
351 | ||
90dc2e5b | 352 | if ( isSensOK ) |
353 | { | |
f404c5c2 | 354 | BRepMesh_Edge aNewEdge1 (theVertexIndex, aFirstNode, BRepMesh_Free); |
355 | BRepMesh_Edge aNewEdge3 (aLastNode, theVertexIndex, BRepMesh_Free); | |
356 | ||
357 | Standard_Integer iNewEdge1 = myMeshData->AddLink (aNewEdge1); | |
358 | Standard_Integer iNewEdge3 = myMeshData->AddLink (aNewEdge3); | |
90dc2e5b | 359 | |
f404c5c2 | 360 | BRepMesh_Triangle aNewTri (Abs (iNewEdge1), anEdges.Key(), Abs (iNewEdge3), |
361 | (iNewEdge1 > 0), isPositive, (iNewEdge3 > 0), | |
362 | BRepMesh_Free); | |
363 | Standard_Integer iNewTri = myMeshData->AddElement(aNewTri); | |
90dc2e5b | 364 | |
365 | Standard_Boolean isCircleCreated = | |
f404c5c2 | 366 | myCircles.Add (aVertexCoord, aFirstVertex.Coord(), aLastVertex.Coord(), iNewTri); |
90dc2e5b | 367 | |
368 | if ( !isCircleCreated ) | |
f404c5c2 | 369 | myMeshData->RemoveElement (iNewTri); |
90dc2e5b | 370 | } |
371 | else | |
372 | { | |
373 | if ( isPositive ) | |
374 | aLoopEdges.Append( anEdges.Key() ); | |
375 | else | |
376 | aLoopEdges.Append( -anEdges.Key() ); | |
377 | ||
378 | if ( aVEdge1.SquareModulus() > aVEdge3.SquareModulus() ) | |
379 | { | |
f404c5c2 | 380 | BRepMesh_Edge aNewEdge (theVertexIndex, aFirstNode, BRepMesh_Free); |
381 | Standard_Integer iNewEdge = myMeshData->AddLink(aNewEdge); | |
382 | anExternalEdges.Append (Abs (iNewEdge)); | |
90dc2e5b | 383 | } |
384 | else | |
385 | { | |
f404c5c2 | 386 | BRepMesh_Edge aNewEdge (aLastNode, theVertexIndex, BRepMesh_Free); |
387 | Standard_Integer iNewEdge = myMeshData->AddLink (aNewEdge); | |
388 | anExternalEdges.Append (Abs (iNewEdge)); | |
90dc2e5b | 389 | } |
390 | } | |
2b59653e | 391 | } |
90dc2e5b | 392 | } |
393 | ||
394 | thePoly.Clear(); | |
395 | while ( !anExternalEdges.IsEmpty() ) | |
396 | { | |
397 | const BRepMesh_PairOfIndex& aPair = | |
398 | myMeshData->ElemConnectedTo( Abs( anExternalEdges.First() ) ); | |
399 | ||
400 | ||
401 | if ( !aPair.IsEmpty() ) | |
402 | DeleteTriangle( aPair.FirstIndex(), thePoly ); | |
403 | ||
404 | anExternalEdges.RemoveFirst(); | |
405 | } | |
406 | ||
407 | for ( anEdges.Initialize( thePoly ); anEdges.More(); anEdges.Next() ) | |
408 | { | |
409 | if ( myMeshData->ElemConnectedTo( anEdges.Key() ).IsEmpty() ) | |
410 | myMeshData->RemoveLink( anEdges.Key() ); | |
411 | } | |
412 | ||
413 | while ( !aLoopEdges.IsEmpty() ) | |
414 | { | |
415 | const BRepMesh_Edge& anEdge = GetEdge( Abs( aLoopEdges.First() ) ); | |
416 | if ( anEdge.Movability() != BRepMesh_Deleted ) | |
2b59653e | 417 | { |
90dc2e5b | 418 | Standard_Integer anEdgeIdx = aLoopEdges.First(); |
419 | MeshLeftPolygonOf( Abs( anEdgeIdx ), ( anEdgeIdx > 0 ) ); | |
2b59653e | 420 | } |
90dc2e5b | 421 | |
422 | aLoopEdges.RemoveFirst(); | |
423 | } | |
424 | } | |
425 | ||
426 | //======================================================================= | |
427 | //function : CreateTrianglesOnNewVertices | |
428 | //purpose : Creation of triangles from the new nodes | |
429 | //======================================================================= | |
430 | void BRepMesh_Delaun::CreateTrianglesOnNewVertices( TColStd_Array1OfInteger& theVertexIndexes ) | |
431 | { | |
432 | BRepMesh_MapOfIntegerInteger aLoopEdges( 10, myMeshData->Allocator() ); | |
433 | ||
434 | // Insertion of nodes : | |
435 | Standard_Boolean isModify = Standard_True; | |
436 | ||
437 | Standard_Integer anIndex = theVertexIndexes.Lower(); | |
438 | Standard_Integer anUpper = theVertexIndexes.Upper(); | |
439 | for( ; anIndex <= anUpper; ++anIndex ) | |
440 | { | |
441 | aLoopEdges.Clear(); | |
2b59653e | 442 | |
90dc2e5b | 443 | Standard_Integer aVertexIdx = theVertexIndexes( anIndex ); |
444 | const BRepMesh_Vertex& aVertex = GetVertex( aVertexIdx ); | |
0d88155b | 445 | |
90dc2e5b | 446 | // Iterator in the list of indexes of circles containing the node |
447 | BRepMesh_ListOfInteger& aCirclesList = myCircles.Select( aVertex.Coord() ); | |
448 | ||
449 | Standard_Integer onEgdeId = 0, aTriangleId = 0; | |
450 | BRepMesh_ListOfInteger::Iterator aCircleIt( aCirclesList ); | |
451 | for ( ; aCircleIt.More(); aCircleIt.Next() ) | |
452 | { | |
453 | // To add a node in the mesh it is necessary to check conditions: | |
454 | // - the node should be within the boundaries of the mesh and so in an existing triangle | |
455 | // - all adjacent triangles should belong to a component connected with this triangle | |
456 | if ( Contains( aCircleIt.Value(), aVertex, onEgdeId ) ) | |
457 | { | |
458 | if ( onEgdeId == 0 ) | |
459 | { | |
460 | aTriangleId = aCircleIt.Value(); | |
461 | aCirclesList.Remove( aCircleIt ); | |
462 | break; | |
463 | } | |
464 | else if ( GetEdge( onEgdeId ).Movability() == BRepMesh_Free ) | |
465 | { | |
466 | aTriangleId = aCircleIt.Value(); | |
467 | aCirclesList.Remove( aCircleIt ); | |
468 | break; | |
0d88155b O |
469 | } |
470 | } | |
90dc2e5b | 471 | } |
0d88155b | 472 | |
90dc2e5b | 473 | if ( aTriangleId > 0 ) |
474 | { | |
475 | DeleteTriangle( aTriangleId, aLoopEdges ); | |
0d88155b | 476 | |
90dc2e5b | 477 | isModify = Standard_True; |
478 | while ( isModify && !aCirclesList.IsEmpty() ) | |
479 | { | |
480 | isModify = Standard_False; | |
481 | BRepMesh_ListOfInteger::Iterator aCircleIt1( aCirclesList ); | |
482 | for ( ; aCircleIt1.More(); aCircleIt1.Next() ) | |
483 | { | |
484 | Standard_Integer e[3]; | |
485 | Standard_Boolean o[3]; | |
486 | GetTriangle( aCircleIt1.Value() ).Edges( e[0], e[1], e[2], | |
487 | o[0], o[1], o[2] ); | |
488 | ||
489 | if ( aLoopEdges.IsBound( e[0] ) || | |
490 | aLoopEdges.IsBound( e[1] ) || | |
491 | aLoopEdges.IsBound( e[2] ) ) | |
492 | { | |
493 | isModify = Standard_True; | |
494 | DeleteTriangle( aCircleIt1.Value(), aLoopEdges ); | |
495 | aCirclesList.Remove( aCircleIt1 ); | |
496 | break; | |
497 | } | |
498 | } | |
2b59653e | 499 | } |
0d88155b | 500 | |
90dc2e5b | 501 | // Creation of triangles with the current node and free edges |
502 | // and removal of these edges from the list of free edges | |
503 | CreateTriangles( aVertexIdx, aLoopEdges ); | |
2b59653e | 504 | } |
0d88155b | 505 | } |
90dc2e5b | 506 | // Check that internal edges are not crossed by triangles |
507 | BRepMesh_MapOfInteger::Iterator anInernalEdgesIt( InternalEdges() ); | |
0d88155b | 508 | |
90dc2e5b | 509 | // Destruction of triancles intersecting internal edges |
510 | // and their replacement by makeshift triangles | |
511 | anInernalEdgesIt.Reset(); | |
512 | for ( ; anInernalEdgesIt.More(); anInernalEdgesIt.Next() ) | |
513 | { | |
514 | Standard_Integer aNbC; | |
515 | aNbC = myMeshData->ElemConnectedTo( anInernalEdgesIt.Key() ).Extent(); | |
516 | if ( aNbC == 0 ) | |
517 | { | |
518 | MeshLeftPolygonOf( anInernalEdgesIt.Key(), Standard_True ); | |
519 | MeshLeftPolygonOf( anInernalEdgesIt.Key(), Standard_False ); | |
0d88155b O |
520 | } |
521 | } | |
522 | ||
90dc2e5b | 523 | // Adjustment of meshes to boundary edges |
524 | FrontierAdjust(); | |
0d88155b O |
525 | } |
526 | ||
0d88155b | 527 | //======================================================================= |
90dc2e5b | 528 | //function : CleanupMesh |
529 | //purpose : Cleanup mesh from the free triangles | |
0d88155b | 530 | //======================================================================= |
90dc2e5b | 531 | void BRepMesh_Delaun::CleanupMesh() |
0d88155b | 532 | { |
90dc2e5b | 533 | BRepMesh_MapOfIntegerInteger aLoopEdges( 10, myMeshData->Allocator() ); |
534 | ListOfInteger aTrianglesList; | |
0d88155b | 535 | |
f404c5c2 | 536 | for(;;) |
90dc2e5b | 537 | { |
538 | aTrianglesList.Clear(); | |
539 | aLoopEdges.Clear(); | |
0d88155b | 540 | |
90dc2e5b | 541 | BRepMesh_MapOfInteger::Iterator aFreeEdgesIt( FreeEdges() ); |
542 | for ( ; aFreeEdgesIt.More(); aFreeEdgesIt.Next() ) | |
543 | { | |
544 | const BRepMesh_Edge& anEdge = GetEdge( aFreeEdgesIt.Key() ); | |
545 | if ( anEdge.Movability() != BRepMesh_Frontier ) | |
546 | { | |
547 | Standard_Integer aFrontierNb = 0; | |
548 | if ( myMeshData->ElemConnectedTo( aFreeEdgesIt.Key() ).IsEmpty() ) | |
549 | aLoopEdges.Bind( aFreeEdgesIt.Key(), Standard_True ); | |
550 | else | |
551 | { | |
552 | BRepMesh_ListOfInteger::Iterator aConnectedLinksIt( | |
553 | myMeshData->LinkNeighboursOf( anEdge.FirstNode() ) ); | |
554 | ||
555 | for ( ; aConnectedLinksIt.More(); aConnectedLinksIt.Next() ) | |
556 | { | |
557 | if ( GetEdge( aConnectedLinksIt.Value() ).Movability() == BRepMesh_Frontier ) | |
558 | { | |
559 | aFrontierNb++; | |
560 | if ( aFrontierNb > 1 ) | |
561 | break; | |
562 | } | |
563 | } | |
564 | ||
565 | if ( aFrontierNb == 2 ) | |
566 | { | |
567 | const BRepMesh_PairOfIndex& aPair = myMeshData->ElemConnectedTo( aFreeEdgesIt.Key() ); | |
568 | for ( Standard_Integer j = 1, jn = aPair.Extent(); j <= jn; ++j ) | |
569 | { | |
570 | const Standard_Integer anElemId = aPair.Index(j); | |
571 | if ( anElemId < 0 ) | |
572 | continue; | |
573 | ||
574 | Standard_Integer e[3]; | |
575 | Standard_Boolean o[3]; | |
576 | GetTriangle( anElemId ).Edges( e[0], e[1], e[2], | |
577 | o[0], o[1], o[2] ); | |
578 | ||
579 | Standard_Boolean isTriangleToDelete = Standard_True; | |
580 | for ( Standard_Integer k = 0; k < 3; ++k ) | |
581 | { | |
582 | if ( GetEdge( e[k] ).Movability() != BRepMesh_Free ) | |
583 | { | |
584 | isTriangleToDelete = Standard_False; | |
585 | break; | |
0d88155b O |
586 | } |
587 | } | |
588 | ||
90dc2e5b | 589 | if ( isTriangleToDelete ) |
590 | aTrianglesList.Append( anElemId ); | |
591 | } | |
0d88155b O |
592 | } |
593 | } | |
594 | } | |
595 | } | |
596 | ||
90dc2e5b | 597 | // Destruction of triangles : |
598 | Standard_Integer aDeletedTrianglesNb = 0; | |
599 | for ( ; !aTrianglesList.IsEmpty(); aTrianglesList.RemoveFirst() ) | |
600 | { | |
601 | DeleteTriangle( aTrianglesList.First(), aLoopEdges ); | |
602 | aDeletedTrianglesNb++; | |
603 | } | |
0d88155b | 604 | |
90dc2e5b | 605 | // Destruction of remaining hanging edges |
606 | BRepMesh_MapOfIntegerInteger::Iterator aLoopEdgesIt( aLoopEdges ); | |
607 | for ( ; aLoopEdgesIt.More(); aLoopEdgesIt.Next() ) | |
608 | { | |
609 | if ( myMeshData->ElemConnectedTo( aLoopEdgesIt.Key() ).IsEmpty() ) | |
610 | myMeshData->RemoveLink( aLoopEdgesIt.Key() ); | |
611 | } | |
0d88155b | 612 | |
90dc2e5b | 613 | if ( aDeletedTrianglesNb == 0 ) |
614 | break; | |
615 | } | |
616 | } | |
0d88155b | 617 | |
90dc2e5b | 618 | //======================================================================= |
619 | //function : FrontierAdjust | |
620 | //purpose : Adjust the mesh on the frontier | |
621 | //======================================================================= | |
622 | void BRepMesh_Delaun::FrontierAdjust() | |
623 | { | |
624 | BRepMesh_MapOfIntegerInteger aLoopEdges( 10, myMeshData->Allocator() ); | |
625 | ListOfInteger aTrianglesList; | |
626 | ||
627 | for ( Standard_Integer aPass = 1; aPass <= 2; ++aPass ) | |
628 | { | |
629 | // 1 pass): find external triangles on boundary edges | |
630 | // 2 pass): find external triangles on boundary edges | |
631 | // because in comlex curved boundaries external triangles can appear | |
632 | // after "mesh left aPolygonon" | |
633 | ||
634 | BRepMesh_MapOfInteger::Iterator aFrontierIt( Frontier() ); | |
635 | for ( ; aFrontierIt.More(); aFrontierIt.Next() ) | |
636 | { | |
637 | const BRepMesh_PairOfIndex& aPair = myMeshData->ElemConnectedTo( aFrontierIt.Key() ); | |
638 | for( Standard_Integer j = 1, jn = aPair.Extent(); j <= jn; ++j ) | |
639 | { | |
640 | const Standard_Integer aPriorElemId = aPair.Index(j); | |
641 | if( aPriorElemId < 0 ) | |
642 | continue; | |
643 | ||
644 | Standard_Integer e[3]; | |
645 | Standard_Boolean o[3]; | |
646 | GetTriangle( aPriorElemId ).Edges( e[0], e[1], e[2], | |
647 | o[0], o[1], o[2] ); | |
648 | ||
649 | for ( Standard_Integer n = 0; n < 3; ++n ) | |
650 | { | |
651 | if ( aFrontierIt.Key() == e[n] && !o[n] ) | |
652 | { | |
653 | aTrianglesList.Append( aPriorElemId ); | |
654 | break; | |
0d88155b O |
655 | } |
656 | } | |
657 | } | |
658 | } | |
90dc2e5b | 659 | |
660 | // destruction of external triangles on boundary edges | |
661 | for ( ; !aTrianglesList.IsEmpty(); aTrianglesList.RemoveFirst() ) | |
662 | DeleteTriangle( aTrianglesList.First(), aLoopEdges ); | |
663 | ||
664 | // destrucrion of remaining hanging edges : | |
665 | BRepMesh_MapOfIntegerInteger::Iterator aLoopEdgesIt( aLoopEdges ); | |
666 | for ( ; aLoopEdgesIt.More(); aLoopEdgesIt.Next() ) | |
667 | { | |
668 | if (myMeshData->ElemConnectedTo( aLoopEdgesIt.Key() ).IsEmpty() ) | |
669 | myMeshData->RemoveLink( aLoopEdgesIt.Key() ); | |
0d88155b | 670 | } |
90dc2e5b | 671 | |
672 | ||
673 | // destruction of triangles crossing the boundary edges and | |
674 | // their replacement by makeshift triangles | |
675 | if ( aPass == 1 ) | |
676 | aFrontierIt.Reset(); | |
677 | else | |
678 | // in some cases there remain unused boundaries check | |
679 | aFrontierIt.Initialize( Frontier() ); | |
0d88155b | 680 | |
90dc2e5b | 681 | NCollection_Vector<Bnd_Box2d> aFrontBoxes; |
682 | for ( ; aFrontierIt.More(); aFrontierIt.Next() ) | |
683 | { | |
684 | const BRepMesh_Edge& anEdge = GetEdge( aFrontierIt.Key() ); | |
685 | const BRepMesh_Vertex& aV1 = GetVertex( anEdge.FirstNode() ); | |
686 | const BRepMesh_Vertex& aV2 = GetVertex( anEdge.LastNode() ); | |
687 | fillBndBox( aFrontBoxes, aV1, aV2 ); | |
0d88155b | 688 | |
90dc2e5b | 689 | if ( myMeshData->ElemConnectedTo( aFrontierIt.Key() ).IsEmpty() ) |
690 | MeshLeftPolygonOf( aFrontierIt.Key(), Standard_True ); | |
691 | } | |
0d88155b | 692 | |
90dc2e5b | 693 | if ( aPass == 1 ) |
694 | continue; | |
0d88155b | 695 | |
90dc2e5b | 696 | CleanupMesh(); |
697 | } | |
0d88155b O |
698 | } |
699 | ||
0d88155b | 700 | //======================================================================= |
90dc2e5b | 701 | //function : KillInternalTriangles |
702 | //purpose : Removes triangles within polygon | |
0d88155b | 703 | //======================================================================= |
90dc2e5b | 704 | void BRepMesh_Delaun::KillInternalTriangles( Standard_Integer theEdgeId, |
705 | const TColStd_MapOfInteger& theIgnoredEdges, | |
706 | BRepMesh_MapOfIntegerInteger& theLoopEdges ) | |
0d88155b | 707 | { |
90dc2e5b | 708 | if ( theIgnoredEdges.Contains( theEdgeId ) ) |
709 | return; | |
0d88155b | 710 | |
90dc2e5b | 711 | const BRepMesh_PairOfIndex& aPair = myMeshData->ElemConnectedTo( theEdgeId ); |
712 | for ( Standard_Integer i = 1; i <= aPair.Extent(); ++i ) | |
713 | { | |
714 | Standard_Integer anElemId = aPair.Index(i); | |
715 | if( anElemId < 0 ) | |
716 | continue; | |
0d88155b | 717 | |
90dc2e5b | 718 | Standard_Integer e[3]; |
719 | Standard_Boolean o[3]; | |
720 | GetTriangle( anElemId ).Edges( e[0], e[1], e[2], | |
721 | o[0], o[1], o[2] ); | |
0d88155b | 722 | |
90dc2e5b | 723 | for ( Standard_Integer anIndex = 0; anIndex < 3; ++anIndex ) |
724 | { | |
725 | if ( e[anIndex] == theEdgeId ) | |
726 | { | |
727 | DeleteTriangle( anElemId, theLoopEdges ); | |
728 | for ( Standard_Integer n = 0; n < 2; ++n ) | |
729 | { | |
730 | Standard_Integer aCurEdge = e[(anIndex + n + 1) % 3]; | |
731 | KillInternalTriangles( aCurEdge, theIgnoredEdges, theLoopEdges ); | |
0d88155b O |
732 | } |
733 | } | |
734 | } | |
90dc2e5b | 735 | } |
736 | } | |
0d88155b | 737 | |
90dc2e5b | 738 | //======================================================================= |
739 | //function : RemovePivotTriangles | |
740 | //purpose : Removes triangles around the given pivot node | |
741 | //======================================================================= | |
742 | void BRepMesh_Delaun::RemovePivotTriangles( const Standard_Integer theEdgeInfo, | |
743 | const Standard_Integer thePivotNode, | |
744 | TColStd_MapOfInteger& theInfectedEdges, | |
745 | BRepMesh_MapOfIntegerInteger& theLoopEdges, | |
746 | const Standard_Boolean isFirstPass ) | |
747 | { | |
748 | Standard_Integer e[3]; | |
749 | Standard_Boolean o[3]; | |
750 | Standard_Integer aGeneralEdgeId = -1; | |
751 | ||
752 | Standard_Integer anMainEdgeId = Abs( theEdgeInfo ); | |
753 | Standard_Boolean anIsForward = theEdgeInfo > 0; | |
754 | const BRepMesh_PairOfIndex& aPair = myMeshData->ElemConnectedTo( anMainEdgeId ); | |
755 | for ( Standard_Integer j = 1, jn = aPair.Extent(); j <= jn; ++j ) | |
756 | { | |
757 | Standard_Integer anElemId = aPair.Index(j); | |
758 | if( anElemId < 0 ) | |
759 | continue; | |
760 | ||
761 | GetTriangle( anElemId ).Edges( e[0], e[1], e[2], | |
762 | o[0], o[1], o[2] ); | |
0d88155b | 763 | |
90dc2e5b | 764 | for ( Standard_Integer anIndex = 0; anIndex < 3; ++anIndex ) |
765 | { | |
766 | if ( e[anIndex] == anMainEdgeId && o[anIndex] == anIsForward ) | |
767 | { | |
768 | // triangle detected | |
769 | DeleteTriangle( anElemId, theLoopEdges ); | |
770 | aGeneralEdgeId = anIndex; | |
771 | break; | |
0d88155b | 772 | } |
90dc2e5b | 773 | } |
774 | ||
775 | if ( aGeneralEdgeId != -1 ) | |
776 | break; | |
777 | } | |
0d88155b | 778 | |
90dc2e5b | 779 | if ( aGeneralEdgeId != -1 ) |
780 | { | |
781 | // delete triangles around of aPivotNode starting from the bounding one | |
782 | // define edge connected to vertes | |
783 | Standard_Integer anEdgeId = -1; | |
784 | for ( Standard_Integer i = 0; i < 2; ++i ) | |
785 | { | |
786 | Standard_Integer aTmpEdgeId = e[(aGeneralEdgeId + i + 1) % 3]; | |
787 | const BRepMesh_Edge& anEdge = GetEdge( aTmpEdgeId ); | |
788 | if ( anEdge.FirstNode() == thePivotNode || | |
789 | anEdge.LastNode() == thePivotNode ) | |
790 | { | |
791 | anEdgeId = aTmpEdgeId; | |
0d88155b | 792 | } |
90dc2e5b | 793 | |
794 | if ( theInfectedEdges.Contains( aTmpEdgeId ) ) | |
795 | theInfectedEdges.Remove( aTmpEdgeId ); | |
796 | else | |
797 | theInfectedEdges.Add( aTmpEdgeId ); | |
0d88155b | 798 | } |
90dc2e5b | 799 | |
800 | if ( isFirstPass ) | |
801 | return; | |
802 | ||
803 | while ( anEdgeId > 0 ) | |
804 | { | |
805 | const BRepMesh_PairOfIndex& aFreePair = myMeshData->ElemConnectedTo( anEdgeId ); | |
806 | Standard_Integer anOldEdge = anEdgeId; | |
807 | anEdgeId = -1; | |
808 | ||
809 | for ( Standard_Integer aPairIndex = 1; aPairIndex <= aFreePair.Extent(); ++aPairIndex ) | |
810 | { | |
811 | Standard_Integer anElemId = aFreePair.Index( aPairIndex ); | |
812 | if( anElemId < 0 ) | |
813 | continue; | |
814 | ||
815 | Standard_Integer e1[3]; | |
816 | Standard_Boolean o1[3]; | |
817 | GetTriangle( anElemId ).Edges( e1[0], e1[1], e1[2], | |
818 | o1[0], o1[1], o1[2] ); | |
819 | ||
820 | DeleteTriangle( anElemId, theLoopEdges ); | |
821 | ||
822 | for ( Standard_Integer i = 0; i < 3; ++i ) | |
823 | { | |
824 | if ( e1[i] == anOldEdge ) | |
825 | { | |
2de84aa2 | 826 | for ( Standard_Integer j = 0; j < 2; ++j ) |
827 | { | |
828 | Standard_Integer aTmpEdgeId = e1[(j + i + 1) % 3]; | |
90dc2e5b | 829 | const BRepMesh_Edge& anEdge = GetEdge( aTmpEdgeId ); |
830 | if ( anEdge.FirstNode() == thePivotNode || | |
831 | anEdge.LastNode() == thePivotNode ) | |
832 | { | |
833 | anEdgeId = aTmpEdgeId; | |
834 | } | |
835 | ||
836 | if ( theInfectedEdges.Contains( aTmpEdgeId ) ) | |
837 | theInfectedEdges.Remove( aTmpEdgeId ); | |
838 | else | |
839 | theInfectedEdges.Add( aTmpEdgeId ); | |
840 | } | |
841 | break; | |
842 | } | |
0d88155b O |
843 | } |
844 | } | |
0d88155b O |
845 | } |
846 | } | |
847 | } | |
848 | ||
849 | //======================================================================= | |
90dc2e5b | 850 | //function : CleanupPolygon |
851 | //purpose : Remove internal triangles from the given polygon | |
0d88155b | 852 | //======================================================================= |
90dc2e5b | 853 | void BRepMesh_Delaun::CleanupPolygon( const TColStd_SequenceOfInteger& thePolygon, |
854 | TColStd_MapOfInteger& theInfectedEdges, | |
855 | BRepMesh_MapOfIntegerInteger& theLoopEdges ) | |
0d88155b | 856 | { |
90dc2e5b | 857 | Standard_Integer aPolyLen = thePolygon.Length(); |
0d88155b | 858 | |
90dc2e5b | 859 | TColStd_MapOfInteger anIgnoredEdges; |
860 | NCollection_Map<Standard_Integer> aPolyVertices; | |
861 | for ( Standard_Integer i = 1; i <= aPolyLen; ++i ) | |
862 | { | |
863 | Standard_Integer aPolyEdgeId = Abs( thePolygon(i) ); | |
864 | anIgnoredEdges.Add( aPolyEdgeId ); | |
0d88155b | 865 | |
90dc2e5b | 866 | const BRepMesh_Edge& aPolyEdge = GetEdge( aPolyEdgeId ); |
867 | aPolyVertices.Add( aPolyEdge.FirstNode() ); | |
868 | aPolyVertices.Add( aPolyEdge.LastNode() ); | |
0d88155b | 869 | |
90dc2e5b | 870 | if ( theInfectedEdges.Contains( aPolyEdgeId ) ) |
871 | theInfectedEdges.Remove( aPolyEdgeId ); | |
872 | } | |
0d88155b | 873 | |
90dc2e5b | 874 | Standard_Real aRefTotalAngle = 2 * M_PI; |
875 | TColStd_MapIteratorOfMapOfInteger anInfectedIt( theInfectedEdges ); | |
876 | for ( ; anInfectedIt.More(); anInfectedIt.Next() ) | |
877 | { | |
878 | Standard_Integer anEdgeId = anInfectedIt.Key(); | |
879 | const BRepMesh_Edge& anInfectedEdge = GetEdge( anEdgeId ); | |
880 | Standard_Integer anEdgeVertices[2] = { anInfectedEdge.FirstNode(), | |
881 | anInfectedEdge.LastNode() }; | |
0d88155b | 882 | |
90dc2e5b | 883 | Standard_Boolean isToExclude = Standard_False; |
884 | for ( Standard_Integer i = 0; i < 2; ++i ) | |
885 | { | |
886 | Standard_Integer aCurVertex = anEdgeVertices[i]; | |
887 | if ( aPolyVertices.Contains( aCurVertex ) ) | |
888 | continue; | |
0d88155b | 889 | |
90dc2e5b | 890 | gp_XY aCenterPointXY = GetVertex( aCurVertex ).Coord(); |
891 | Standard_Real aTotalAng = 0.0; | |
892 | ||
893 | for ( Standard_Integer i = 1; i <= aPolyLen; ++i ) | |
894 | { | |
895 | Standard_Integer aPolyEdgeId = thePolygon(i); | |
896 | const BRepMesh_Edge& aPolyEdge = GetEdge( Abs( aPolyEdgeId ) ); | |
897 | Standard_Integer aStartPoint, anEndPoint; | |
898 | if ( aPolyEdgeId >= 0 ) | |
899 | { | |
900 | aStartPoint = aPolyEdge.FirstNode(); | |
901 | anEndPoint = aPolyEdge.LastNode(); | |
0d88155b | 902 | } |
90dc2e5b | 903 | else |
904 | { | |
905 | aStartPoint = aPolyEdge.LastNode(); | |
906 | anEndPoint = aPolyEdge.FirstNode(); | |
907 | } | |
908 | ||
909 | gp_XY aStartV = GetVertex( aStartPoint ).Coord() - aCenterPointXY; | |
910 | gp_XY anEndV = GetVertex( anEndPoint ).Coord() - aCenterPointXY; | |
911 | ||
912 | Standard_Real anAngle = gp_Vec2d( anEndV ).Angle( gp_Vec2d( aStartV ) ); | |
913 | aTotalAng += anAngle; | |
914 | } | |
915 | ||
916 | if ( Abs( aRefTotalAngle - aTotalAng ) > Precision::Angular() ) | |
917 | isToExclude = Standard_True; | |
0d88155b | 918 | } |
90dc2e5b | 919 | |
920 | if ( isToExclude ) | |
921 | anIgnoredEdges.Add( anEdgeId ); | |
0d88155b O |
922 | } |
923 | ||
90dc2e5b | 924 | |
925 | anInfectedIt.Initialize( theInfectedEdges ); | |
926 | for ( ; anInfectedIt.More(); anInfectedIt.Next() ) | |
927 | { | |
928 | Standard_Integer anEdgeId = anInfectedIt.Key(); | |
929 | KillInternalTriangles( anEdgeId, anIgnoredEdges, theLoopEdges); | |
0d88155b O |
930 | } |
931 | ||
90dc2e5b | 932 | BRepMesh_MapOfIntegerInteger::Iterator aLoopEdgesIt( theLoopEdges ); |
933 | for ( ; aLoopEdgesIt.More(); aLoopEdgesIt.Next() ) | |
934 | { | |
935 | if ( myMeshData->ElemConnectedTo( aLoopEdgesIt.Key() ).IsEmpty() ) | |
936 | myMeshData->RemoveLink( aLoopEdgesIt.Key() ); | |
0d88155b O |
937 | } |
938 | } | |
939 | ||
940 | //======================================================================= | |
90dc2e5b | 941 | //function : MeshLeftPolygonOf |
942 | //purpose : Triangulation of the aPolygonon to the left of <theEdgeIndex>.(material side) | |
0d88155b | 943 | //======================================================================= |
90dc2e5b | 944 | void BRepMesh_Delaun::MeshLeftPolygonOf( const Standard_Integer theEdgeIndex, |
945 | const Standard_Boolean isForward ) | |
0d88155b | 946 | { |
90dc2e5b | 947 | const BRepMesh_Edge& anEdge = GetEdge( theEdgeIndex ); |
948 | NCollection_Map<Standard_Integer> aDealLinks; | |
949 | TColStd_SequenceOfInteger aPolygon; | |
950 | BRepMesh_MapOfIntegerInteger aLoopEdges( 10, myMeshData->Allocator() ); | |
951 | TColStd_MapOfInteger anUsedEdges; | |
952 | TColStd_MapOfInteger anInfectedEdges; | |
953 | ||
954 | // Find the aPolygonon | |
955 | anUsedEdges.Add( theEdgeIndex ); | |
956 | Standard_Integer aFirstNode, aStartNode, aPivotNode; | |
957 | ||
958 | if ( isForward ) | |
959 | { | |
960 | aPolygon.Append( theEdgeIndex ); | |
961 | aStartNode = anEdge.FirstNode(); | |
962 | aPivotNode = anEdge.LastNode(); | |
963 | } | |
964 | else | |
965 | { | |
966 | aPolygon.Append( -theEdgeIndex ); | |
967 | aStartNode = anEdge.LastNode(); | |
968 | aPivotNode = anEdge.FirstNode(); | |
969 | } | |
970 | aFirstNode = aStartNode; | |
0d88155b | 971 | |
90dc2e5b | 972 | const BRepMesh_Vertex& aStartVertex = GetVertex( aFirstNode ); |
973 | const BRepMesh_Vertex& anEndVertex = GetVertex( aPivotNode ); | |
0d88155b | 974 | |
90dc2e5b | 975 | Standard_Integer aRefOtherNode = 0, anOtherNode = 0; |
976 | // Check the presence of the previous edge <theEdgeIndex> : | |
977 | BRepMesh_ListOfInteger::Iterator aLinkIt( myMeshData->LinkNeighboursOf( aStartNode ) ); | |
978 | for ( ; aLinkIt.More(); aLinkIt.Next() ) | |
2b59653e | 979 | { |
90dc2e5b | 980 | if ( aLinkIt.Value() != theEdgeIndex ) |
981 | { | |
982 | const BRepMesh_Edge& aNextEdge = GetEdge( aLinkIt.Value() ); | |
983 | anOtherNode = aNextEdge.LastNode(); | |
984 | if ( anOtherNode == aStartNode ) | |
985 | anOtherNode = aNextEdge.FirstNode(); | |
986 | break; | |
987 | } | |
988 | } | |
989 | if ( anOtherNode == 0 ) | |
990 | return; | |
0d88155b | 991 | |
90dc2e5b | 992 | |
993 | gp_XY aVEdge( anEndVertex.Coord() ); | |
994 | aVEdge.Subtract( aStartVertex.Coord() ); | |
995 | gp_XY aPrevVEdge( aVEdge ); | |
996 | gp_XY aRefCurrVEdge, aCurrVEdge; | |
997 | ||
998 | Standard_Integer aCurrEdgeId = theEdgeIndex; | |
999 | Standard_Integer aNextEdgeId; | |
1000 | ||
1001 | // Find the nearest to <theEdgeIndex> closed aPolygonon : | |
1002 | Standard_Boolean isInMesh, isNotInters; | |
1003 | Standard_Real anAngle, aRefAngle; | |
1004 | ||
1005 | NCollection_Vector <Bnd_Box2d> aBoxes; | |
1006 | fillBndBox( aBoxes, aStartVertex, anEndVertex ); | |
2b59653e | 1007 | |
90dc2e5b | 1008 | while ( aPivotNode != aFirstNode ) |
1009 | { | |
1010 | aNextEdgeId = 0; | |
1011 | if ( myPositiveOrientation ) | |
1012 | aRefAngle = RealFirst(); | |
1013 | else | |
1014 | aRefAngle = RealLast(); | |
0d88155b | 1015 | |
90dc2e5b | 1016 | const BRepMesh_Vertex& aPivotVertex = GetVertex( aPivotNode ); |
1017 | ||
1018 | // Find the next edge with the greatest angle with <theEdgeIndex> | |
1019 | // and non intersecting <theEdgeIndex> : | |
1020 | ||
1021 | aLinkIt.Init( myMeshData->LinkNeighboursOf( aPivotNode ) ); | |
1022 | for ( ; aLinkIt.More(); aLinkIt.Next() ) | |
1023 | { | |
1024 | Standard_Integer aNextLink = aLinkIt.Value(); | |
1025 | Standard_Integer aNextLinkId = Abs( aNextLink ); | |
1026 | if ( aDealLinks.Contains( aNextLinkId ) ) | |
1027 | continue; | |
1028 | ||
1029 | if ( aNextLinkId != aCurrEdgeId ) | |
1030 | { | |
1031 | isNotInters = Standard_True; | |
1032 | const BRepMesh_Edge& aNextEdge = GetEdge( aNextLinkId ); | |
1033 | ||
1034 | isInMesh = Standard_True; | |
1035 | ||
1036 | //define if link exist in mesh | |
1037 | if ( aNextEdge.Movability() == BRepMesh_Free ) | |
1038 | { | |
1039 | if ( myMeshData->ElemConnectedTo( aLinkIt.Value() ).IsEmpty() ) | |
1040 | isInMesh = Standard_False; | |
2b59653e | 1041 | } |
0d88155b | 1042 | |
90dc2e5b | 1043 | if ( isInMesh ) |
1044 | { | |
1045 | anOtherNode = aNextEdge.FirstNode(); | |
1046 | if ( anOtherNode == aPivotNode ) | |
1047 | anOtherNode = aNextEdge.LastNode(); | |
1048 | ||
1049 | aCurrVEdge = GetVertex( anOtherNode ).Coord(); | |
1050 | aCurrVEdge.Subtract( aPivotVertex.Coord() ); | |
1051 | ||
1052 | if ( aCurrVEdge.Modulus() >= gp::Resolution() && | |
1053 | aPrevVEdge.Modulus() >= gp::Resolution() ) | |
1054 | { | |
1055 | anAngle = gp_Vec2d( aPrevVEdge ).Angle( gp_Vec2d( aCurrVEdge ) ); | |
1056 | ||
1057 | if ( ( myPositiveOrientation && anAngle > aRefAngle ) || | |
1058 | ( !myPositiveOrientation && anAngle < aRefAngle ) ) | |
1059 | { | |
1060 | Bnd_Box2d aBox; | |
1061 | aBox.Add( gp_Pnt2d( GetVertex( aNextEdge.FirstNode() ).Coord() ) ); | |
1062 | aBox.Add( gp_Pnt2d( GetVertex( aNextEdge.LastNode() ).Coord() ) ); | |
1063 | ||
1064 | for ( Standard_Integer k = 0, aLen = aPolygon.Length(); k < aLen; ++k ) | |
1065 | { | |
1066 | if ( !aBox.IsOut( aBoxes.Value( k ) ) ) | |
1067 | { | |
1068 | // intersection is possible... | |
1069 | if ( IntSegSeg( aNextEdge, GetEdge( Abs( aPolygon( k + 1 ) ) ) ) ) | |
1070 | { | |
1071 | isNotInters = Standard_False; | |
1072 | break; | |
1073 | } | |
1074 | } | |
1075 | } | |
1076 | ||
1077 | if( isNotInters ) | |
1078 | { | |
1079 | aRefAngle = anAngle; | |
1080 | aRefCurrVEdge = aCurrVEdge; | |
1081 | ||
1082 | if ( aNextEdge.FirstNode() == aPivotNode ) | |
1083 | aNextEdgeId = aLinkIt.Value(); | |
1084 | else | |
1085 | aNextEdgeId = -aLinkIt.Value(); | |
1086 | ||
1087 | aRefOtherNode = anOtherNode; | |
1088 | } | |
1089 | } | |
2b59653e E |
1090 | } |
1091 | } | |
0d88155b | 1092 | } |
90dc2e5b | 1093 | } |
1094 | if ( aNextEdgeId != 0 ) | |
1095 | { | |
1096 | if ( Abs( aNextEdgeId ) != theEdgeIndex && Abs( aNextEdgeId ) != aCurrEdgeId ) | |
1097 | { | |
1098 | aCurrEdgeId = Abs( aNextEdgeId ); | |
2b59653e | 1099 | |
90dc2e5b | 1100 | if ( !anUsedEdges.Add( aCurrEdgeId ) ) |
1101 | { | |
1102 | //if this edge has already been added to the aPolygon, | |
1103 | //there is a risk of looping (attention to open contours) | |
1104 | //remove last edge and continue | |
1105 | ||
1106 | aDealLinks.Add( aCurrEdgeId ); | |
1107 | ||
1108 | //roll back | |
1109 | continue; | |
1110 | } | |
1111 | ||
1112 | aPolygon.Append( aNextEdgeId ); | |
1113 | ||
1114 | const BRepMesh_Edge& aCurrEdge = GetEdge( aCurrEdgeId ); | |
1115 | Standard_Integer aVert1 = aCurrEdge.FirstNode(); | |
1116 | Standard_Integer aVert2 = aCurrEdge.LastNode(); | |
1117 | fillBndBox( aBoxes, GetVertex( aVert1 ), GetVertex( aVert2 ) ); | |
1118 | ||
1119 | RemovePivotTriangles( aNextEdgeId, aPivotNode, | |
1120 | anInfectedEdges, aLoopEdges, (aPolygon.Length() == 2) ); | |
1121 | } | |
0d88155b | 1122 | } |
90dc2e5b | 1123 | else |
1124 | { | |
1125 | //hanging end | |
1126 | if ( aPolygon.Length() == 1 ) | |
1127 | return; | |
0d88155b | 1128 | |
90dc2e5b | 1129 | Standard_Integer aDeadEdgeId = Abs( aPolygon.Last() ); |
90dc2e5b | 1130 | |
1131 | aDealLinks.Add( aDeadEdgeId ); | |
1132 | ||
1133 | anUsedEdges.Remove( aDeadEdgeId ); | |
1134 | aPolygon.Remove( aPolygon.Length() ); | |
1135 | ||
1136 | // return to previous point | |
1137 | Standard_Integer aLastValidEdge = aPolygon.Last(); | |
1138 | const BRepMesh_Edge& aLastEdge = GetEdge( Abs( aLastValidEdge ) ); | |
1139 | ||
1140 | if( aLastValidEdge > 0 ) | |
1141 | { | |
1142 | aStartNode = aLastEdge.FirstNode(); | |
1143 | aPivotNode = aLastEdge.LastNode(); | |
1144 | } | |
1145 | else | |
1146 | { | |
1147 | aStartNode = aLastEdge.LastNode(); | |
1148 | aPivotNode = aLastEdge.FirstNode(); | |
1149 | } | |
1150 | ||
1151 | const BRepMesh_Vertex& dV = GetVertex( aStartNode ); | |
1152 | const BRepMesh_Vertex& fV = GetVertex( aPivotNode ); | |
1153 | aPrevVEdge = fV.Coord() - dV.Coord(); | |
1154 | continue; | |
0d88155b | 1155 | } |
90dc2e5b | 1156 | |
1157 | aStartNode = aPivotNode; | |
1158 | aPivotNode = aRefOtherNode; | |
1159 | aPrevVEdge = aRefCurrVEdge; | |
2b59653e | 1160 | } |
0d88155b | 1161 | |
90dc2e5b | 1162 | CleanupPolygon( aPolygon, anInfectedEdges, aLoopEdges ); |
1163 | MeshPolygon( aPolygon ); | |
2b59653e | 1164 | } |
0d88155b | 1165 | |
2b59653e | 1166 | //======================================================================= |
90dc2e5b | 1167 | //function : MeshPolygon |
1168 | //purpose : Triangulatiion of a closed aPolygonon described by the list of indexes of | |
1169 | // its edges in the structure. (negative index == reversed) | |
2b59653e | 1170 | //======================================================================= |
90dc2e5b | 1171 | void BRepMesh_Delaun::MeshPolygon( TColStd_SequenceOfInteger& thePoly ) |
2b59653e | 1172 | { |
90dc2e5b | 1173 | Standard_Integer aPivotNode, aVertex3 = 0; |
1174 | Standard_Integer aFirstNode, aLastNode; | |
1175 | Standard_Integer aTriId; | |
0d88155b | 1176 | |
90dc2e5b | 1177 | if ( thePoly.Length() == 3 ) |
1178 | { | |
1179 | aTriId = myMeshData->AddElement( BRepMesh_Triangle( | |
1180 | Abs( thePoly(1) ), Abs( thePoly(2) ), Abs( thePoly(3) ), | |
1181 | thePoly(1) > 0, thePoly(2) > 0, thePoly(3) > 0, | |
1182 | BRepMesh_Free ) ); | |
1183 | ||
1184 | myCircles.MocAdd( aTriId ); | |
1185 | const BRepMesh_Edge& anEdge1 = GetEdge( Abs( thePoly(1) ) ); | |
1186 | const BRepMesh_Edge& anEdge2 = GetEdge( Abs( thePoly(2) ) ); | |
1187 | ||
1188 | if ( thePoly(1) > 0) | |
1189 | { | |
1190 | aFirstNode = anEdge1.FirstNode(); | |
1191 | aLastNode = anEdge1.LastNode(); | |
1192 | } | |
1193 | else | |
1194 | { | |
1195 | aFirstNode = anEdge1.LastNode(); | |
1196 | aLastNode = anEdge1.FirstNode(); | |
1197 | } | |
1198 | ||
1199 | if ( thePoly(2) > 0 ) | |
1200 | aVertex3 = anEdge2.LastNode(); | |
1201 | else | |
1202 | aVertex3 = anEdge2.FirstNode(); | |
0d88155b | 1203 | |
90dc2e5b | 1204 | Standard_Boolean isAdded = myCircles.Add( GetVertex( aFirstNode ).Coord(), |
1205 | GetVertex( aLastNode ).Coord(), GetVertex( aVertex3 ).Coord(), aTriId ); | |
1206 | ||
1207 | if ( !isAdded ) | |
1208 | myMeshData->RemoveElement( aTriId ); | |
1209 | } | |
1210 | else if ( thePoly.Length() > 3 ) | |
2b59653e | 1211 | { |
90dc2e5b | 1212 | NCollection_Vector <Bnd_Box2d> aBoxes; |
1213 | Standard_Integer aPolyIdx, aUsedIdx = 0; | |
1214 | Standard_Integer aPolyLen = thePoly.Length(); | |
1215 | ||
1216 | for ( aPolyIdx = 1; aPolyIdx <= aPolyLen; ++aPolyIdx ) | |
1217 | { | |
1218 | const BRepMesh_Edge& anEdge = GetEdge( Abs( thePoly( aPolyIdx ) ) ); | |
1219 | aFirstNode = anEdge.FirstNode(); | |
1220 | aLastNode = anEdge.LastNode(); | |
1221 | fillBndBox( aBoxes, GetVertex( aFirstNode ), GetVertex( aLastNode ) ); | |
1222 | } | |
1223 | ||
1224 | const BRepMesh_Edge& anEdge = GetEdge( Abs( thePoly(1) ) ); | |
1225 | Standard_Real aMinDist = RealLast(); | |
1226 | ||
1227 | if ( thePoly(1) > 0 ) | |
1228 | { | |
1229 | aFirstNode = anEdge.FirstNode(); | |
1230 | aLastNode = anEdge.LastNode(); | |
1231 | } | |
1232 | else | |
2b59653e | 1233 | { |
90dc2e5b | 1234 | aFirstNode = anEdge.LastNode(); |
1235 | aLastNode = anEdge.FirstNode(); | |
1236 | } | |
1237 | ||
1238 | gp_XY aVEdge( GetVertex( aLastNode ).Coord() - | |
1239 | GetVertex( aFirstNode ).Coord() ); | |
1240 | ||
1241 | Standard_Real aVEdgeLen = aVEdge.Modulus(); | |
1242 | if ( aVEdgeLen > 0.) | |
1243 | { | |
1244 | aVEdge.SetCoord( aVEdge.X() / aVEdgeLen, | |
1245 | aVEdge.Y() / aVEdgeLen ); | |
1246 | ||
1247 | for ( aPolyIdx = 3; aPolyIdx <= aPolyLen; ++aPolyIdx ) | |
1248 | { | |
1249 | const BRepMesh_Edge& aNextEdge = GetEdge( Abs( thePoly( aPolyIdx ) ) ); | |
1250 | if ( thePoly( aPolyIdx ) > 0) | |
1251 | aPivotNode = aNextEdge.FirstNode(); | |
1252 | else | |
1253 | aPivotNode = aNextEdge.LastNode(); | |
1254 | ||
1255 | gp_XY aVEdgePivot( GetVertex( aPivotNode ).Coord() - | |
1256 | GetVertex( aLastNode ).Coord() ); | |
1257 | ||
1258 | Standard_Real aDist = aVEdge ^ aVEdgePivot; | |
1259 | if ( Abs( aDist ) > Precision::PConfusion() ) | |
1260 | { | |
1261 | if ( ( aDist > 0. && myPositiveOrientation ) || | |
1262 | ( aDist < 0. && !myPositiveOrientation ) ) | |
1263 | { | |
1264 | if ( Abs( aDist ) < aMinDist ) | |
1265 | { | |
1266 | Bnd_Box2d aBoxFirst, aBoxLast; | |
1267 | aBoxFirst.Add( gp_Pnt2d( GetVertex( aPivotNode ).Coord() ) ); | |
1268 | aBoxFirst.Add( gp_Pnt2d( GetVertex( aLastNode ).Coord() ) ); | |
1269 | ||
1270 | aBoxLast.Add( gp_Pnt2d( GetVertex( aPivotNode ).Coord() ) ); | |
1271 | aBoxLast.Add( gp_Pnt2d( GetVertex( aFirstNode ).Coord() ) ); | |
1272 | ||
1273 | BRepMesh_Edge aCheckE1( aLastNode, aPivotNode, BRepMesh_Free ); | |
1274 | BRepMesh_Edge aCheckE2( aFirstNode, aPivotNode, BRepMesh_Free ); | |
1275 | ||
1276 | Standard_Boolean isIntersect = Standard_False; | |
1277 | for ( Standard_Integer aPolyIdx1 = 2; aPolyIdx1 <= aPolyLen; ++aPolyIdx1 ) | |
1278 | { | |
1279 | if( aPolyIdx1 == aPolyIdx ) | |
1280 | continue; | |
1281 | ||
1282 | const BRepMesh_Edge& aNextEdge1 = GetEdge( Abs( thePoly( aPolyIdx1 ) ) ); | |
1283 | if ( !aBoxFirst.IsOut( aBoxes.Value( aPolyIdx1 - 1 ) ) ) | |
1284 | { | |
1285 | // intersection is possible... | |
1286 | if( IntSegSeg( aCheckE1, aNextEdge1 ) ) | |
1287 | { | |
1288 | isIntersect = Standard_True; | |
1289 | break; | |
1290 | } | |
1291 | } | |
1292 | ||
1293 | if ( !aBoxLast.IsOut( aBoxes.Value( aPolyIdx1 - 1 ) ) && | |
1294 | !aCheckE2.IsEqual( aNextEdge1 ) ) | |
1295 | { | |
1296 | // intersection is possible... | |
1297 | if( IntSegSeg( aCheckE2, aNextEdge1 ) ) | |
1298 | { | |
1299 | isIntersect = Standard_True; | |
1300 | break; | |
1301 | } | |
1302 | } | |
1303 | } | |
1304 | ||
1305 | if( !isIntersect ) | |
1306 | { | |
1307 | aMinDist = aDist; | |
1308 | aVertex3 = aPivotNode; | |
1309 | aUsedIdx = aPolyIdx; | |
1310 | } | |
1311 | } | |
1312 | } | |
1313 | } | |
1314 | } | |
1315 | } | |
1316 | ||
1317 | Standard_Integer aNewEdge2, aNewEdge3; | |
1318 | if ( aMinDist < RealLast() ) | |
1319 | { | |
1320 | aNewEdge2 = myMeshData->AddLink( BRepMesh_Edge( aLastNode, aVertex3, BRepMesh_Free ) ); | |
1321 | aNewEdge3 = myMeshData->AddLink( BRepMesh_Edge( aVertex3, aFirstNode, BRepMesh_Free ) ); | |
1322 | aTriId = myMeshData->AddElement( BRepMesh_Triangle( | |
1323 | Abs( thePoly(1) ), Abs( aNewEdge2 ), Abs( aNewEdge3 ), | |
1324 | thePoly(1) > 0, aNewEdge2 > 0, aNewEdge3 > 0, | |
1325 | BRepMesh_Free ) ); | |
1326 | ||
1327 | Standard_Boolean isAdded = myCircles.Add( GetVertex( aFirstNode ).Coord(), | |
1328 | GetVertex( aLastNode ).Coord(), GetVertex( aVertex3 ).Coord(), aTriId ); | |
1329 | ||
1330 | if ( !isAdded ) | |
1331 | myMeshData->RemoveElement( aTriId ); | |
1332 | ||
1333 | if ( aUsedIdx < aPolyLen ) | |
1334 | { | |
1335 | TColStd_SequenceOfInteger aSuitePoly; | |
1336 | thePoly.Split( aUsedIdx, aSuitePoly ); | |
1337 | aSuitePoly.Prepend( -aNewEdge3 ); | |
1338 | MeshPolygon( aSuitePoly ); | |
1339 | } | |
1340 | else | |
1341 | thePoly.Remove( aPolyLen ); | |
1342 | ||
1343 | if ( aUsedIdx > 3 ) | |
1344 | { | |
1345 | thePoly.SetValue( 1, -aNewEdge2 ); | |
1346 | MeshPolygon( thePoly ); | |
1347 | } | |
2b59653e | 1348 | } |
0d88155b | 1349 | } |
0d88155b O |
1350 | } |
1351 | ||
1352 | //======================================================================= | |
1353 | //function : RemoveVertex | |
90dc2e5b | 1354 | //purpose : Removes a vertex from the triangulation |
0d88155b | 1355 | //======================================================================= |
90dc2e5b | 1356 | void BRepMesh_Delaun::RemoveVertex( const BRepMesh_Vertex& theVertex ) |
0d88155b | 1357 | { |
90dc2e5b | 1358 | BRepMesh_SelectorOfDataStructureOfDelaun aSelector( myMeshData ); |
1359 | aSelector.NeighboursOf( theVertex ); | |
0d88155b | 1360 | |
90dc2e5b | 1361 | BRepMesh_MapOfIntegerInteger aLoopEdges( 10, myMeshData->Allocator() ); |
0d88155b O |
1362 | |
1363 | // Loop on triangles to be destroyed : | |
90dc2e5b | 1364 | BRepMesh_MapOfInteger::Iterator aTriangleIt( aSelector.Elements() ); |
1365 | for ( ; aTriangleIt.More(); aTriangleIt.Next() ) | |
1366 | DeleteTriangle( aTriangleIt.Key(), aLoopEdges ); | |
0d88155b | 1367 | |
90dc2e5b | 1368 | TColStd_SequenceOfInteger aPolygon; |
1369 | Standard_Integer aLoopEdgesCount = aLoopEdges.Extent(); | |
1370 | BRepMesh_MapOfIntegerInteger::Iterator aLoopEdgesIt( aLoopEdges ); | |
1371 | ||
1372 | if ( aLoopEdgesIt.More() ) | |
1373 | { | |
1374 | const BRepMesh_Edge& anEdge = GetEdge( aLoopEdgesIt.Key() ); | |
1375 | Standard_Integer aFirstNode = anEdge.FirstNode(); | |
1376 | Standard_Integer aLastNode; | |
1377 | Standard_Integer aPivotNode = anEdge.LastNode(); | |
1378 | Standard_Integer anEdgeId = aLoopEdgesIt.Key(); | |
1379 | ||
1380 | Standard_Boolean isPositive = (Standard_Boolean)aLoopEdges( anEdgeId ); | |
1381 | if ( !isPositive ) | |
1382 | { | |
1383 | Standard_Integer aTmp; | |
1384 | aTmp = aFirstNode; | |
1385 | aFirstNode = aPivotNode; | |
1386 | aPivotNode = aTmp; | |
1387 | ||
1388 | aPolygon.Append( -anEdgeId ); | |
0d88155b | 1389 | } |
90dc2e5b | 1390 | else |
1391 | aPolygon.Append( anEdgeId ); | |
1392 | ||
1393 | aLoopEdges.UnBind( anEdgeId ); | |
1394 | ||
1395 | aLastNode = aFirstNode; | |
1396 | while ( aPivotNode != aLastNode ) | |
1397 | { | |
1398 | BRepMesh_ListOfInteger::Iterator aLinkIt( myMeshData->LinkNeighboursOf( aPivotNode ) ); | |
1399 | for ( ; aLinkIt.More(); aLinkIt.Next() ) | |
1400 | { | |
1401 | if ( aLinkIt.Value() != anEdgeId && | |
1402 | aLoopEdges.IsBound( aLinkIt.Value() ) ) | |
1403 | { | |
1404 | Standard_Integer aCurrentNode; | |
1405 | anEdgeId = aLinkIt.Value(); | |
1406 | const BRepMesh_Edge& anEdge1 = GetEdge( anEdgeId ); | |
1407 | ||
1408 | aCurrentNode = anEdge1.LastNode(); | |
1409 | if ( aCurrentNode != aPivotNode ) | |
1410 | { | |
1411 | aCurrentNode = anEdge1.FirstNode(); | |
1412 | aPolygon.Append( -anEdgeId ); | |
0d88155b O |
1413 | } |
1414 | else | |
90dc2e5b | 1415 | aPolygon.Append( anEdgeId ); |
1416 | ||
1417 | aPivotNode = aCurrentNode; | |
1418 | aLoopEdges.UnBind( anEdgeId ); | |
0d88155b O |
1419 | break; |
1420 | } | |
1421 | } | |
90dc2e5b | 1422 | |
1423 | if ( aLoopEdgesCount <= 0 ) | |
1424 | break; | |
1425 | --aLoopEdgesCount; | |
0d88155b | 1426 | } |
90dc2e5b | 1427 | |
1428 | MeshPolygon( aPolygon ); | |
0d88155b O |
1429 | } |
1430 | } | |
1431 | ||
1432 | ||
1433 | //======================================================================= | |
1434 | //function : AddVertices | |
90dc2e5b | 1435 | //purpose : Adds some vertices in the triangulation. |
0d88155b | 1436 | //======================================================================= |
90dc2e5b | 1437 | void BRepMesh_Delaun::AddVertices( BRepMesh_Array1OfVertexOfDelaun& theVertices ) |
0d88155b | 1438 | { |
90dc2e5b | 1439 | BRepMesh_HeapSortVertexOfDelaun::Sort( theVertices, |
1440 | BRepMesh_ComparatorOfVertexOfDelaun( SortingDirection, Precision::PConfusion() ) ); | |
0d88155b | 1441 | |
90dc2e5b | 1442 | Standard_Integer aLower = theVertices.Lower(); |
1443 | Standard_Integer anUpper = theVertices.Upper(); | |
2b59653e | 1444 | |
90dc2e5b | 1445 | TColStd_Array1OfInteger aVertexIndexes( aLower, anUpper ); |
1446 | for ( Standard_Integer i = aLower; i <= anUpper; ++i ) | |
1447 | aVertexIndexes(i) = myMeshData->AddNode( theVertices(i) ); | |
0d88155b | 1448 | |
90dc2e5b | 1449 | CreateTrianglesOnNewVertices( aVertexIndexes ); |
0d88155b O |
1450 | } |
1451 | ||
1452 | //======================================================================= | |
1453 | //function : UseEdge | |
90dc2e5b | 1454 | //purpose : Modify mesh to use the edge. Return True if done |
0d88155b | 1455 | //======================================================================= |
90dc2e5b | 1456 | Standard_Boolean BRepMesh_Delaun::UseEdge( const Standard_Integer theIndex ) |
0d88155b | 1457 | { |
90dc2e5b | 1458 | /* |
1459 | const BRepMesh_PairOfIndex& aPair = myMeshData->ElemConnectedTo( theIndex ); | |
1460 | if ( aPair.Extent() == 0 ) | |
1461 | { | |
1462 | const BRepMesh_Edge& anEdge = GetEdge( theIndex ); | |
1463 | ||
1464 | Standard_Integer aStartNode, aPivotNode, anOtherNode; | |
1465 | aStartNode = anEdge.FirstNode(); | |
1466 | aPivotNode = anEdge.LastNode(); | |
1467 | ||
1468 | const BRepMesh_ListOfInteger& aStartNodeNeighbors = myMeshData->LinkNeighboursOf( aStartNode ); | |
1469 | const BRepMesh_ListOfInteger& aPivotNodeNeighbors = myMeshData->LinkNeighboursOf( aPivotNode ); | |
1470 | ||
1471 | if ( aStartNodeNeighbors.Extent() > 0 && | |
1472 | aPivotNodeNeighbors.Extent() > 0 ) | |
1473 | { | |
1474 | const BRepMesh_Vertex& aStartVertex = GetVertex( aStartNode ); | |
1475 | const BRepMesh_Vertex& aPivotVertex = GetVertex( aPivotNode ); | |
1476 | ||
1477 | gp_XY aVEdge ( aPivotVertex.Coord() ); | |
1478 | aVEdge.Subtract( aStartVertex.Coord() ); | |
1479 | ||
1480 | Standard_Real anAngle = 0.; | |
1481 | Standard_Real anAngleMin = RealLast(); | |
1482 | Standard_Real anAngleMax = RealFirst(); | |
1483 | Standard_Integer aLeftEdge = 0, aRightEdge = 0; | |
1484 | ||
1485 | BRepMesh_ListOfInteger::Iterator aNeighborIt( aPivotNodeNeighbors ); | |
1486 | for ( ; aNeighborIt.More(); aNeighborIt.Next() ) | |
1487 | { | |
1488 | Standard_Integer anEdgeId = aNeighborIt.Value(); | |
1489 | if ( anEdgeId != theIndex ) | |
1490 | { | |
1491 | const BRepMesh_Edge& aNextEdge = GetEdge( anEdgeId ); | |
1492 | ||
1493 | Standard_Boolean isInMesh = Standard_True; | |
1494 | if ( aNextEdge.Movability() == BRepMesh_Free ) | |
1495 | { | |
1496 | if ( myMeshData->ElemConnectedTo( anEdgeId ).IsEmpty() ) | |
1497 | isInMesh = Standard_False; | |
0d88155b O |
1498 | } |
1499 | ||
90dc2e5b | 1500 | if ( isInMesh ) |
1501 | { | |
1502 | anOtherNode = aNextEdge.FirstNode(); | |
1503 | if ( anOtherNode == aPivotNode ) | |
1504 | anOtherNode = aNextEdge.LastNode(); | |
0d88155b | 1505 | |
90dc2e5b | 1506 | gp_XY aVEdgeCur = GetVertex( anOtherNode ).Coord(); |
1507 | aVEdgeCur.Subtract( aPivotVertex.Coord() ); | |
0d88155b | 1508 | |
90dc2e5b | 1509 | anAngle = gp_Vec2d( aVEdge ).Angle( gp_Vec2d( aVEdgeCur ) ); |
0d88155b | 1510 | } |
90dc2e5b | 1511 | |
1512 | if ( anAngle > anAngleMax ) | |
1513 | { | |
1514 | anAngleMax = anAngle; | |
1515 | aLeftEdge = anEdgeId; | |
0d88155b | 1516 | } |
90dc2e5b | 1517 | if ( anAngle < anAngleMin ) |
1518 | { | |
1519 | anAngleMin = anAngle; | |
1520 | aRightEdge = anEdgeId; | |
0d88155b O |
1521 | } |
1522 | } | |
1523 | } | |
90dc2e5b | 1524 | |
1525 | if ( aLeftEdge > 0 ) | |
1526 | { | |
1527 | if (aLeftEdge==aRightEdge) | |
1528 | { | |
0d88155b | 1529 | } |
90dc2e5b | 1530 | else |
1531 | { | |
0d88155b O |
1532 | } |
1533 | } | |
1534 | } | |
1535 | } | |
90dc2e5b | 1536 | */ |
0d88155b O |
1537 | return Standard_False; |
1538 | } | |
1539 | ||
0d88155b O |
1540 | //======================================================================= |
1541 | //function : Result | |
90dc2e5b | 1542 | //purpose : Gives the Mesh data structure |
0d88155b | 1543 | //======================================================================= |
90dc2e5b | 1544 | const Handle( BRepMesh_DataStructureOfDelaun )& BRepMesh_Delaun::Result() const |
0d88155b | 1545 | { |
90dc2e5b | 1546 | return myMeshData; |
0d88155b O |
1547 | } |
1548 | ||
1549 | //======================================================================= | |
1550 | //function : Frontier | |
90dc2e5b | 1551 | //purpose : Gives the list of frontier edges |
0d88155b | 1552 | //======================================================================= |
90dc2e5b | 1553 | const BRepMesh_MapOfInteger& BRepMesh_Delaun::Frontier() |
0d88155b | 1554 | { |
90dc2e5b | 1555 | BRepMesh_MapOfInteger::Iterator anEdgeIt( myMeshData->LinkOfDomain() ); |
0d88155b | 1556 | |
90dc2e5b | 1557 | myMapEdges.Clear(); |
1558 | for ( ; anEdgeIt.More(); anEdgeIt.Next() ) | |
1559 | { | |
1560 | Standard_Integer anEdge = anEdgeIt.Key(); | |
1561 | if ( GetEdge( anEdge ).Movability() == BRepMesh_Frontier ) | |
1562 | myMapEdges.Add( anEdge ); | |
0d88155b | 1563 | } |
90dc2e5b | 1564 | |
1565 | return myMapEdges; | |
0d88155b O |
1566 | } |
1567 | ||
1568 | //======================================================================= | |
1569 | //function : InternalEdges | |
90dc2e5b | 1570 | //purpose : Gives the list of internal edges |
0d88155b | 1571 | //======================================================================= |
90dc2e5b | 1572 | const BRepMesh_MapOfInteger& BRepMesh_Delaun::InternalEdges() |
0d88155b | 1573 | { |
90dc2e5b | 1574 | BRepMesh_MapOfInteger::Iterator anEdgeIt( myMeshData->LinkOfDomain() ); |
0d88155b | 1575 | |
90dc2e5b | 1576 | myMapEdges.Clear(); |
1577 | for ( ; anEdgeIt.More(); anEdgeIt.Next() ) | |
1578 | { | |
1579 | Standard_Integer anEdge = anEdgeIt.Key(); | |
1580 | if ( GetEdge( anEdge ).Movability() == BRepMesh_Fixed ) | |
1581 | myMapEdges.Add( anEdge ); | |
0d88155b | 1582 | } |
90dc2e5b | 1583 | |
1584 | return myMapEdges; | |
0d88155b O |
1585 | } |
1586 | ||
1587 | //======================================================================= | |
1588 | //function : FreeEdges | |
90dc2e5b | 1589 | //purpose : Gives the list of free edges used only one time |
0d88155b | 1590 | //======================================================================= |
90dc2e5b | 1591 | const BRepMesh_MapOfInteger& BRepMesh_Delaun::FreeEdges() |
0d88155b | 1592 | { |
90dc2e5b | 1593 | BRepMesh_MapOfInteger::Iterator anEdgeIt( myMeshData->LinkOfDomain() ); |
0d88155b | 1594 | |
90dc2e5b | 1595 | myMapEdges.Clear(); |
1596 | for ( ; anEdgeIt.More(); anEdgeIt.Next() ) | |
1597 | { | |
1598 | Standard_Integer anEdge = anEdgeIt.Key(); | |
1599 | if ( myMeshData->ElemConnectedTo( anEdge ).Extent() <= 1 ) | |
1600 | myMapEdges.Add( anEdge ); | |
0d88155b | 1601 | } |
90dc2e5b | 1602 | |
1603 | return myMapEdges; | |
0d88155b O |
1604 | } |
1605 | ||
0d88155b | 1606 | //======================================================================= |
90dc2e5b | 1607 | //function : calculateDist |
1608 | //purpose : Calculates distances between the given point and edges of | |
1609 | // triangle | |
0d88155b | 1610 | //======================================================================= |
90dc2e5b | 1611 | static Standard_Real calculateDist( const gp_XY theVEdges[3], |
1612 | const gp_XY thePoints[3], | |
1613 | const Standard_Integer theEdgesId[3], | |
1614 | const BRepMesh_Vertex& theVertex, | |
1615 | Standard_Real theDistance[3], | |
1616 | Standard_Real theSqModulus[3], | |
1617 | Standard_Integer& theEdgeOn ) | |
2b59653e | 1618 | { |
90dc2e5b | 1619 | Standard_Real aMinDist = -1; |
1620 | if ( !theVEdges || !thePoints || !theEdgesId || | |
1621 | !theDistance || !theSqModulus ) | |
1622 | return aMinDist; | |
1623 | ||
1624 | for( Standard_Integer i = 0; i < 3; ++i ) | |
2b59653e | 1625 | { |
90dc2e5b | 1626 | theSqModulus[i] = theVEdges[i].SquareModulus(); |
1627 | if ( theSqModulus[i] <= EPSEPS ) | |
1628 | return -1; | |
1629 | ||
1630 | theDistance[i] = theVEdges[i] ^ ( theVertex.Coord() - thePoints[i] ); | |
1631 | ||
1632 | Standard_Real aDist = theDistance[i] * theDistance[i]; | |
1633 | aDist /= theSqModulus[i]; | |
2b59653e | 1634 | |
90dc2e5b | 1635 | if ( aMinDist < 0 || aDist < aMinDist ) |
2b59653e | 1636 | { |
90dc2e5b | 1637 | theEdgeOn = theEdgesId[i]; |
1638 | aMinDist = aDist; | |
2b59653e E |
1639 | } |
1640 | } | |
90dc2e5b | 1641 | |
1642 | return aMinDist; | |
2b59653e E |
1643 | } |
1644 | ||
90dc2e5b | 1645 | //======================================================================= |
1646 | //function : Contains | |
1647 | //purpose : Test if triangle of index <TrianIndex> contains geometricaly | |
1648 | // <theVertex>. If <theEdgeOn> is != 0 then theVertex is on Edge | |
1649 | // of index <theEdgeOn> | |
1650 | //======================================================================= | |
1651 | Standard_Boolean BRepMesh_Delaun::Contains( const Standard_Integer theTriangleId, | |
1652 | const BRepMesh_Vertex& theVertex, | |
1653 | Standard_Integer& theEdgeOn ) const | |
0d88155b | 1654 | { |
90dc2e5b | 1655 | theEdgeOn = 0; |
1656 | ||
1657 | Standard_Integer e[3]; | |
1658 | Standard_Boolean o[3]; | |
1659 | Standard_Integer p[3]; | |
1660 | ||
1661 | GetTriangle( theTriangleId ).Edges( e[0], e[1], e[2], | |
1662 | o[0], o[1], o[2] ); | |
1663 | ||
1664 | const BRepMesh_Edge* anEdges[3] = { &GetEdge( e[0] ), | |
1665 | &GetEdge( e[1] ), | |
1666 | &GetEdge( e[2] ) }; | |
1667 | if ( o[0] ) | |
1668 | { | |
1669 | p[0] = anEdges[0]->FirstNode(); | |
1670 | p[1] = anEdges[0]->LastNode(); | |
0d88155b | 1671 | } |
90dc2e5b | 1672 | else |
1673 | { | |
1674 | p[1] = anEdges[0]->FirstNode(); | |
1675 | p[0] = anEdges[0]->LastNode(); | |
0d88155b | 1676 | } |
2b59653e | 1677 | |
90dc2e5b | 1678 | if ( o[2] ) |
1679 | p[2] = anEdges[2]->FirstNode(); | |
1680 | else | |
1681 | p[2] = anEdges[2]->LastNode(); | |
1682 | ||
1683 | gp_XY aPoints[3]; | |
1684 | aPoints[0] = GetVertex( p[0] ).Coord(); | |
1685 | aPoints[1] = GetVertex( p[1] ).Coord(); | |
1686 | aPoints[2] = GetVertex( p[2] ).Coord(); | |
1687 | ||
1688 | gp_XY aVEdges[3]; | |
1689 | aVEdges[0] = aPoints[1]; | |
1690 | aVEdges[0].Subtract( aPoints[0] ); | |
1691 | ||
1692 | aVEdges[1] = aPoints[2]; | |
1693 | aVEdges[1].Subtract( aPoints[1] ); | |
2b59653e | 1694 | |
90dc2e5b | 1695 | aVEdges[2] = aPoints[0]; |
1696 | aVEdges[2].Subtract( aPoints[2] ); | |
1697 | ||
1698 | Standard_Real aDistance[3]; | |
1699 | Standard_Real aSqModulus[3]; | |
1700 | ||
1701 | Standard_Real aMinDist; | |
1702 | aMinDist = calculateDist( aVEdges, aPoints, e, theVertex, aDistance, aSqModulus, theEdgeOn ); | |
1703 | if ( aMinDist < 0 ) | |
2b59653e E |
1704 | return Standard_False; |
1705 | ||
90dc2e5b | 1706 | if ( aMinDist > EPSEPS ) |
1707 | { | |
1708 | Standard_Integer anEdgeId = theEdgeOn; | |
1709 | theEdgeOn = 0; | |
1710 | ||
1711 | if ( anEdgeId != 0 ) | |
2b59653e | 1712 | { |
90dc2e5b | 1713 | Standard_Integer i = 0; |
1714 | for ( ; i < 3; ++i ) | |
2b59653e | 1715 | { |
90dc2e5b | 1716 | if( e[i] == anEdgeId ) |
2b59653e E |
1717 | break; |
1718 | } | |
1719 | ||
90dc2e5b | 1720 | if( anEdges[i]->Movability() != BRepMesh_Free ) |
1721 | if ( aDistance[i] < ( aSqModulus[i] / 5. ) ) | |
1722 | theEdgeOn = e[i]; | |
0d88155b O |
1723 | } |
1724 | } | |
1725 | ||
90dc2e5b | 1726 | return ( aDistance[0] + aDistance[1] + aDistance[2] != 0. && |
1727 | ( ( aDistance[0] >= 0. && aDistance[1] >= 0. && aDistance[2] >= 0. ) || | |
1728 | ( aDistance[0] <= 0. && aDistance[1] <= 0. && aDistance[2] <= 0. ) ) ); | |
0d88155b O |
1729 | } |
1730 | ||
90dc2e5b | 1731 | |
1732 | //============================================================================= | |
1733 | // Function: classifyPoint | |
1734 | // This function is used for point classifying in case of coincidence of two | |
1735 | // vectors. | |
1736 | // Returns zero value if point is out of segment and non zero value if point is | |
1737 | // between the first and the second point of segment. | |
1738 | // | |
1739 | // thePoint1 - the start point of a segment (base point) | |
1740 | // thePoint2 - the end point of a segment | |
1741 | // thePointToCheck - the point to classify | |
1742 | //============================================================================= | |
1743 | static Standard_Integer classifyPoint( const gp_XY& thePoint1, | |
1744 | const gp_XY& thePoint2, | |
1745 | const gp_XY& thePointToCheck ) | |
1746 | { | |
1747 | gp_XY aP1 = thePoint2 - thePoint1; | |
1748 | gp_XY aP2 = thePointToCheck - thePoint1; | |
1749 | ||
1750 | Standard_Real aDist = Abs( aP1 ^ aP2 ); | |
1751 | if ( aDist >= Precision::PConfusion() ) | |
1752 | { | |
1753 | aDist = ( aDist * aDist ) / aP1.SquareModulus(); | |
1754 | if ( aDist >= EPSEPS ) | |
1755 | return 0; //out | |
1756 | } | |
1757 | ||
1758 | gp_XY aMult = aP1.Multiplied( aP2 ); | |
1759 | if ( aMult.X() < 0.0 || aMult.Y() < 0.0 ) | |
1760 | return 0; //out | |
1761 | ||
1762 | if ( aP1.SquareModulus() < aP2.SquareModulus() ) | |
1763 | return 0; //out | |
1764 | ||
1765 | if ( thePointToCheck.IsEqual( thePoint1, Precision::PConfusion() ) || | |
1766 | thePointToCheck.IsEqual( thePoint2, Precision::PConfusion() ) ) | |
1767 | return -1; //end point | |
1768 | ||
1769 | return 1; | |
1770 | } | |
1771 | ||
1772 | //============================================================================= | |
1773 | // Function: IntSegSeg | |
1774 | //============================================================================= | |
1775 | Standard_Boolean BRepMesh_Delaun::IntSegSeg( const BRepMesh_Edge& theEdg1, | |
1776 | const BRepMesh_Edge& theEdg2 ) | |
1777 | { | |
1778 | gp_XY p1, p2, p3, p4; | |
1779 | p1 = GetVertex( theEdg1.FirstNode() ).Coord(); | |
1780 | p2 = GetVertex( theEdg1.LastNode() ).Coord(); | |
1781 | p3 = GetVertex( theEdg2.FirstNode() ).Coord(); | |
1782 | p4 = GetVertex( theEdg2.LastNode() ).Coord(); | |
1783 | ||
1784 | Standard_Integer aPoint1 = classifyPoint( p1, p2, p3 ); | |
1785 | Standard_Integer aPoint2 = classifyPoint( p1, p2, p4 ); | |
1786 | Standard_Integer aPoint3 = classifyPoint( p3, p4, p1 ); | |
1787 | Standard_Integer aPoint4 = classifyPoint( p3, p4, p2 ); | |
1788 | ||
1789 | if ( aPoint1 > 0 || aPoint2 > 0 || | |
1790 | aPoint3 > 0 || aPoint4 > 0 ) | |
1791 | return Standard_True; | |
1792 | ||
1793 | gp_XY aPl1 = p2 - p1; | |
1794 | gp_XY aPl2 = p4 - p3; | |
1795 | gp_XY aPl3 = p1 - p3; | |
1796 | ||
1797 | Standard_Real aCrossD1D2 = aPl1 ^ aPl2; | |
1798 | Standard_Real aCrossD1D3 = aPl1 ^ aPl3; | |
1799 | if ( Abs( aCrossD1D2 ) < Precision::PConfusion() ) | |
1800 | { | |
1801 | if( Abs( aCrossD1D3 ) < Precision::PConfusion() ) | |
1802 | { | |
1803 | Standard_Integer aPosHash = aPoint1 + aPoint2; | |
1804 | if ( ( !aPosHash && aPoint3 ) ) //|| aPosHash < -1 ) | |
1805 | return Standard_True; | |
1806 | ||
1807 | return Standard_False; | |
1808 | } | |
1809 | else | |
1810 | //parallel case | |
1811 | return Standard_False; | |
1812 | } | |
1813 | ||
1814 | Standard_Real aPar = aCrossD1D3 / aCrossD1D2; | |
1815 | // inrersects out of first segment range | |
1816 | if( aPar < Precision::Angular() || aPar > 1 - Precision::Angular() ) | |
1817 | return Standard_False; | |
1818 | ||
1819 | Standard_Real aCrossD2D3 = aPl2 ^ aPl3; | |
1820 | aPar = aCrossD2D3 / aCrossD1D2; | |
1821 | // inrersects out of second segment range | |
1822 | if( aPar < Precision::Angular() || aPar > 1 - Precision::Angular() ) | |
1823 | return Standard_False; | |
1824 | ||
1825 | return Standard_True; | |
1826 | } |