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 | ||
352 | Standard_Integer aNewEdge1, aNewEdge3, aNewTriangle; | |
353 | if ( isSensOK ) | |
354 | { | |
355 | aNewEdge1 = myMeshData->AddLink( | |
356 | BRepMesh_Edge( theVertexIndex, aFirstNode, BRepMesh_Free ) ); | |
357 | ||
358 | aNewEdge3 = myMeshData->AddLink( | |
359 | BRepMesh_Edge( aLastNode, theVertexIndex, BRepMesh_Free ) ); | |
360 | ||
361 | aNewTriangle = myMeshData->AddElement( | |
362 | BRepMesh_Triangle( Abs( aNewEdge1 ), anEdges.Key(), Abs( aNewEdge3 ), | |
363 | ( aNewEdge1 > 0 ), isPositive, ( aNewEdge3 > 0 ), | |
364 | BRepMesh_Free) ); | |
365 | ||
366 | Standard_Boolean isCircleCreated = | |
367 | myCircles.Add( aVertexCoord, aFirstVertex.Coord(), aLastVertex.Coord(), | |
368 | aNewTriangle ); | |
369 | ||
370 | if ( !isCircleCreated ) | |
371 | myMeshData->RemoveElement( aNewTriangle ); | |
372 | } | |
373 | else | |
374 | { | |
375 | if ( isPositive ) | |
376 | aLoopEdges.Append( anEdges.Key() ); | |
377 | else | |
378 | aLoopEdges.Append( -anEdges.Key() ); | |
379 | ||
380 | if ( aVEdge1.SquareModulus() > aVEdge3.SquareModulus() ) | |
381 | { | |
382 | aNewEdge1 = myMeshData->AddLink( | |
383 | BRepMesh_Edge( theVertexIndex, aFirstNode, BRepMesh_Free ) ); | |
384 | ||
385 | anExternalEdges.Append( Abs( aNewEdge1) ); | |
386 | } | |
387 | else | |
388 | { | |
389 | aNewEdge1 = myMeshData->AddLink( | |
390 | BRepMesh_Edge( aLastNode, theVertexIndex, BRepMesh_Free ) ); | |
391 | ||
392 | anExternalEdges.Append( Abs( aNewEdge3 ) ); | |
393 | } | |
394 | } | |
2b59653e | 395 | } |
90dc2e5b | 396 | } |
397 | ||
398 | thePoly.Clear(); | |
399 | while ( !anExternalEdges.IsEmpty() ) | |
400 | { | |
401 | const BRepMesh_PairOfIndex& aPair = | |
402 | myMeshData->ElemConnectedTo( Abs( anExternalEdges.First() ) ); | |
403 | ||
404 | ||
405 | if ( !aPair.IsEmpty() ) | |
406 | DeleteTriangle( aPair.FirstIndex(), thePoly ); | |
407 | ||
408 | anExternalEdges.RemoveFirst(); | |
409 | } | |
410 | ||
411 | for ( anEdges.Initialize( thePoly ); anEdges.More(); anEdges.Next() ) | |
412 | { | |
413 | if ( myMeshData->ElemConnectedTo( anEdges.Key() ).IsEmpty() ) | |
414 | myMeshData->RemoveLink( anEdges.Key() ); | |
415 | } | |
416 | ||
417 | while ( !aLoopEdges.IsEmpty() ) | |
418 | { | |
419 | const BRepMesh_Edge& anEdge = GetEdge( Abs( aLoopEdges.First() ) ); | |
420 | if ( anEdge.Movability() != BRepMesh_Deleted ) | |
2b59653e | 421 | { |
90dc2e5b | 422 | Standard_Integer anEdgeIdx = aLoopEdges.First(); |
423 | MeshLeftPolygonOf( Abs( anEdgeIdx ), ( anEdgeIdx > 0 ) ); | |
2b59653e | 424 | } |
90dc2e5b | 425 | |
426 | aLoopEdges.RemoveFirst(); | |
427 | } | |
428 | } | |
429 | ||
430 | //======================================================================= | |
431 | //function : CreateTrianglesOnNewVertices | |
432 | //purpose : Creation of triangles from the new nodes | |
433 | //======================================================================= | |
434 | void BRepMesh_Delaun::CreateTrianglesOnNewVertices( TColStd_Array1OfInteger& theVertexIndexes ) | |
435 | { | |
436 | BRepMesh_MapOfIntegerInteger aLoopEdges( 10, myMeshData->Allocator() ); | |
437 | ||
438 | // Insertion of nodes : | |
439 | Standard_Boolean isModify = Standard_True; | |
440 | ||
441 | Standard_Integer anIndex = theVertexIndexes.Lower(); | |
442 | Standard_Integer anUpper = theVertexIndexes.Upper(); | |
443 | for( ; anIndex <= anUpper; ++anIndex ) | |
444 | { | |
445 | aLoopEdges.Clear(); | |
2b59653e | 446 | |
90dc2e5b | 447 | Standard_Integer aVertexIdx = theVertexIndexes( anIndex ); |
448 | const BRepMesh_Vertex& aVertex = GetVertex( aVertexIdx ); | |
0d88155b | 449 | |
90dc2e5b | 450 | // Iterator in the list of indexes of circles containing the node |
451 | BRepMesh_ListOfInteger& aCirclesList = myCircles.Select( aVertex.Coord() ); | |
452 | ||
453 | Standard_Integer onEgdeId = 0, aTriangleId = 0; | |
454 | BRepMesh_ListOfInteger::Iterator aCircleIt( aCirclesList ); | |
455 | for ( ; aCircleIt.More(); aCircleIt.Next() ) | |
456 | { | |
457 | // To add a node in the mesh it is necessary to check conditions: | |
458 | // - the node should be within the boundaries of the mesh and so in an existing triangle | |
459 | // - all adjacent triangles should belong to a component connected with this triangle | |
460 | if ( Contains( aCircleIt.Value(), aVertex, onEgdeId ) ) | |
461 | { | |
462 | if ( onEgdeId == 0 ) | |
463 | { | |
464 | aTriangleId = aCircleIt.Value(); | |
465 | aCirclesList.Remove( aCircleIt ); | |
466 | break; | |
467 | } | |
468 | else if ( GetEdge( onEgdeId ).Movability() == BRepMesh_Free ) | |
469 | { | |
470 | aTriangleId = aCircleIt.Value(); | |
471 | aCirclesList.Remove( aCircleIt ); | |
472 | break; | |
0d88155b O |
473 | } |
474 | } | |
90dc2e5b | 475 | } |
0d88155b | 476 | |
90dc2e5b | 477 | if ( aTriangleId > 0 ) |
478 | { | |
479 | DeleteTriangle( aTriangleId, aLoopEdges ); | |
0d88155b | 480 | |
90dc2e5b | 481 | isModify = Standard_True; |
482 | while ( isModify && !aCirclesList.IsEmpty() ) | |
483 | { | |
484 | isModify = Standard_False; | |
485 | BRepMesh_ListOfInteger::Iterator aCircleIt1( aCirclesList ); | |
486 | for ( ; aCircleIt1.More(); aCircleIt1.Next() ) | |
487 | { | |
488 | Standard_Integer e[3]; | |
489 | Standard_Boolean o[3]; | |
490 | GetTriangle( aCircleIt1.Value() ).Edges( e[0], e[1], e[2], | |
491 | o[0], o[1], o[2] ); | |
492 | ||
493 | if ( aLoopEdges.IsBound( e[0] ) || | |
494 | aLoopEdges.IsBound( e[1] ) || | |
495 | aLoopEdges.IsBound( e[2] ) ) | |
496 | { | |
497 | isModify = Standard_True; | |
498 | DeleteTriangle( aCircleIt1.Value(), aLoopEdges ); | |
499 | aCirclesList.Remove( aCircleIt1 ); | |
500 | break; | |
501 | } | |
502 | } | |
2b59653e | 503 | } |
0d88155b | 504 | |
90dc2e5b | 505 | // Creation of triangles with the current node and free edges |
506 | // and removal of these edges from the list of free edges | |
507 | CreateTriangles( aVertexIdx, aLoopEdges ); | |
2b59653e | 508 | } |
0d88155b | 509 | } |
90dc2e5b | 510 | // Check that internal edges are not crossed by triangles |
511 | BRepMesh_MapOfInteger::Iterator anInernalEdgesIt( InternalEdges() ); | |
0d88155b | 512 | |
90dc2e5b | 513 | // Destruction of triancles intersecting internal edges |
514 | // and their replacement by makeshift triangles | |
515 | anInernalEdgesIt.Reset(); | |
516 | for ( ; anInernalEdgesIt.More(); anInernalEdgesIt.Next() ) | |
517 | { | |
518 | Standard_Integer aNbC; | |
519 | aNbC = myMeshData->ElemConnectedTo( anInernalEdgesIt.Key() ).Extent(); | |
520 | if ( aNbC == 0 ) | |
521 | { | |
522 | MeshLeftPolygonOf( anInernalEdgesIt.Key(), Standard_True ); | |
523 | MeshLeftPolygonOf( anInernalEdgesIt.Key(), Standard_False ); | |
0d88155b O |
524 | } |
525 | } | |
526 | ||
90dc2e5b | 527 | // Adjustment of meshes to boundary edges |
528 | FrontierAdjust(); | |
0d88155b O |
529 | } |
530 | ||
0d88155b | 531 | //======================================================================= |
90dc2e5b | 532 | //function : CleanupMesh |
533 | //purpose : Cleanup mesh from the free triangles | |
0d88155b | 534 | //======================================================================= |
90dc2e5b | 535 | void BRepMesh_Delaun::CleanupMesh() |
0d88155b | 536 | { |
90dc2e5b | 537 | BRepMesh_MapOfIntegerInteger aLoopEdges( 10, myMeshData->Allocator() ); |
538 | ListOfInteger aTrianglesList; | |
0d88155b | 539 | |
90dc2e5b | 540 | while ( Standard_True ) |
541 | { | |
542 | aTrianglesList.Clear(); | |
543 | aLoopEdges.Clear(); | |
0d88155b | 544 | |
90dc2e5b | 545 | BRepMesh_MapOfInteger::Iterator aFreeEdgesIt( FreeEdges() ); |
546 | for ( ; aFreeEdgesIt.More(); aFreeEdgesIt.Next() ) | |
547 | { | |
548 | const BRepMesh_Edge& anEdge = GetEdge( aFreeEdgesIt.Key() ); | |
549 | if ( anEdge.Movability() != BRepMesh_Frontier ) | |
550 | { | |
551 | Standard_Integer aFrontierNb = 0; | |
552 | if ( myMeshData->ElemConnectedTo( aFreeEdgesIt.Key() ).IsEmpty() ) | |
553 | aLoopEdges.Bind( aFreeEdgesIt.Key(), Standard_True ); | |
554 | else | |
555 | { | |
556 | BRepMesh_ListOfInteger::Iterator aConnectedLinksIt( | |
557 | myMeshData->LinkNeighboursOf( anEdge.FirstNode() ) ); | |
558 | ||
559 | for ( ; aConnectedLinksIt.More(); aConnectedLinksIt.Next() ) | |
560 | { | |
561 | if ( GetEdge( aConnectedLinksIt.Value() ).Movability() == BRepMesh_Frontier ) | |
562 | { | |
563 | aFrontierNb++; | |
564 | if ( aFrontierNb > 1 ) | |
565 | break; | |
566 | } | |
567 | } | |
568 | ||
569 | if ( aFrontierNb == 2 ) | |
570 | { | |
571 | const BRepMesh_PairOfIndex& aPair = myMeshData->ElemConnectedTo( aFreeEdgesIt.Key() ); | |
572 | for ( Standard_Integer j = 1, jn = aPair.Extent(); j <= jn; ++j ) | |
573 | { | |
574 | const Standard_Integer anElemId = aPair.Index(j); | |
575 | if ( anElemId < 0 ) | |
576 | continue; | |
577 | ||
578 | Standard_Integer e[3]; | |
579 | Standard_Boolean o[3]; | |
580 | GetTriangle( anElemId ).Edges( e[0], e[1], e[2], | |
581 | o[0], o[1], o[2] ); | |
582 | ||
583 | Standard_Boolean isTriangleToDelete = Standard_True; | |
584 | for ( Standard_Integer k = 0; k < 3; ++k ) | |
585 | { | |
586 | if ( GetEdge( e[k] ).Movability() != BRepMesh_Free ) | |
587 | { | |
588 | isTriangleToDelete = Standard_False; | |
589 | break; | |
0d88155b O |
590 | } |
591 | } | |
592 | ||
90dc2e5b | 593 | if ( isTriangleToDelete ) |
594 | aTrianglesList.Append( anElemId ); | |
595 | } | |
0d88155b O |
596 | } |
597 | } | |
598 | } | |
599 | } | |
600 | ||
90dc2e5b | 601 | // Destruction of triangles : |
602 | Standard_Integer aDeletedTrianglesNb = 0; | |
603 | for ( ; !aTrianglesList.IsEmpty(); aTrianglesList.RemoveFirst() ) | |
604 | { | |
605 | DeleteTriangle( aTrianglesList.First(), aLoopEdges ); | |
606 | aDeletedTrianglesNb++; | |
607 | } | |
0d88155b | 608 | |
90dc2e5b | 609 | // Destruction of remaining hanging edges |
610 | BRepMesh_MapOfIntegerInteger::Iterator aLoopEdgesIt( aLoopEdges ); | |
611 | for ( ; aLoopEdgesIt.More(); aLoopEdgesIt.Next() ) | |
612 | { | |
613 | if ( myMeshData->ElemConnectedTo( aLoopEdgesIt.Key() ).IsEmpty() ) | |
614 | myMeshData->RemoveLink( aLoopEdgesIt.Key() ); | |
615 | } | |
0d88155b | 616 | |
90dc2e5b | 617 | if ( aDeletedTrianglesNb == 0 ) |
618 | break; | |
619 | } | |
620 | } | |
0d88155b | 621 | |
90dc2e5b | 622 | //======================================================================= |
623 | //function : FrontierAdjust | |
624 | //purpose : Adjust the mesh on the frontier | |
625 | //======================================================================= | |
626 | void BRepMesh_Delaun::FrontierAdjust() | |
627 | { | |
628 | BRepMesh_MapOfIntegerInteger aLoopEdges( 10, myMeshData->Allocator() ); | |
629 | ListOfInteger aTrianglesList; | |
630 | ||
631 | for ( Standard_Integer aPass = 1; aPass <= 2; ++aPass ) | |
632 | { | |
633 | // 1 pass): find external triangles on boundary edges | |
634 | // 2 pass): find external triangles on boundary edges | |
635 | // because in comlex curved boundaries external triangles can appear | |
636 | // after "mesh left aPolygonon" | |
637 | ||
638 | BRepMesh_MapOfInteger::Iterator aFrontierIt( Frontier() ); | |
639 | for ( ; aFrontierIt.More(); aFrontierIt.Next() ) | |
640 | { | |
641 | const BRepMesh_PairOfIndex& aPair = myMeshData->ElemConnectedTo( aFrontierIt.Key() ); | |
642 | for( Standard_Integer j = 1, jn = aPair.Extent(); j <= jn; ++j ) | |
643 | { | |
644 | const Standard_Integer aPriorElemId = aPair.Index(j); | |
645 | if( aPriorElemId < 0 ) | |
646 | continue; | |
647 | ||
648 | Standard_Integer e[3]; | |
649 | Standard_Boolean o[3]; | |
650 | GetTriangle( aPriorElemId ).Edges( e[0], e[1], e[2], | |
651 | o[0], o[1], o[2] ); | |
652 | ||
653 | for ( Standard_Integer n = 0; n < 3; ++n ) | |
654 | { | |
655 | if ( aFrontierIt.Key() == e[n] && !o[n] ) | |
656 | { | |
657 | aTrianglesList.Append( aPriorElemId ); | |
658 | break; | |
0d88155b O |
659 | } |
660 | } | |
661 | } | |
662 | } | |
90dc2e5b | 663 | |
664 | // destruction of external triangles on boundary edges | |
665 | for ( ; !aTrianglesList.IsEmpty(); aTrianglesList.RemoveFirst() ) | |
666 | DeleteTriangle( aTrianglesList.First(), aLoopEdges ); | |
667 | ||
668 | // destrucrion of remaining hanging edges : | |
669 | BRepMesh_MapOfIntegerInteger::Iterator aLoopEdgesIt( aLoopEdges ); | |
670 | for ( ; aLoopEdgesIt.More(); aLoopEdgesIt.Next() ) | |
671 | { | |
672 | if (myMeshData->ElemConnectedTo( aLoopEdgesIt.Key() ).IsEmpty() ) | |
673 | myMeshData->RemoveLink( aLoopEdgesIt.Key() ); | |
0d88155b | 674 | } |
90dc2e5b | 675 | |
676 | ||
677 | // destruction of triangles crossing the boundary edges and | |
678 | // their replacement by makeshift triangles | |
679 | if ( aPass == 1 ) | |
680 | aFrontierIt.Reset(); | |
681 | else | |
682 | // in some cases there remain unused boundaries check | |
683 | aFrontierIt.Initialize( Frontier() ); | |
0d88155b | 684 | |
90dc2e5b | 685 | NCollection_Vector<Bnd_Box2d> aFrontBoxes; |
686 | for ( ; aFrontierIt.More(); aFrontierIt.Next() ) | |
687 | { | |
688 | const BRepMesh_Edge& anEdge = GetEdge( aFrontierIt.Key() ); | |
689 | const BRepMesh_Vertex& aV1 = GetVertex( anEdge.FirstNode() ); | |
690 | const BRepMesh_Vertex& aV2 = GetVertex( anEdge.LastNode() ); | |
691 | fillBndBox( aFrontBoxes, aV1, aV2 ); | |
0d88155b | 692 | |
90dc2e5b | 693 | if ( myMeshData->ElemConnectedTo( aFrontierIt.Key() ).IsEmpty() ) |
694 | MeshLeftPolygonOf( aFrontierIt.Key(), Standard_True ); | |
695 | } | |
0d88155b | 696 | |
90dc2e5b | 697 | if ( aPass == 1 ) |
698 | continue; | |
0d88155b | 699 | |
90dc2e5b | 700 | CleanupMesh(); |
701 | } | |
0d88155b O |
702 | } |
703 | ||
0d88155b | 704 | //======================================================================= |
90dc2e5b | 705 | //function : KillInternalTriangles |
706 | //purpose : Removes triangles within polygon | |
0d88155b | 707 | //======================================================================= |
90dc2e5b | 708 | void BRepMesh_Delaun::KillInternalTriangles( Standard_Integer theEdgeId, |
709 | const TColStd_MapOfInteger& theIgnoredEdges, | |
710 | BRepMesh_MapOfIntegerInteger& theLoopEdges ) | |
0d88155b | 711 | { |
90dc2e5b | 712 | if ( theIgnoredEdges.Contains( theEdgeId ) ) |
713 | return; | |
0d88155b | 714 | |
90dc2e5b | 715 | const BRepMesh_PairOfIndex& aPair = myMeshData->ElemConnectedTo( theEdgeId ); |
716 | for ( Standard_Integer i = 1; i <= aPair.Extent(); ++i ) | |
717 | { | |
718 | Standard_Integer anElemId = aPair.Index(i); | |
719 | if( anElemId < 0 ) | |
720 | continue; | |
0d88155b | 721 | |
90dc2e5b | 722 | Standard_Integer e[3]; |
723 | Standard_Boolean o[3]; | |
724 | GetTriangle( anElemId ).Edges( e[0], e[1], e[2], | |
725 | o[0], o[1], o[2] ); | |
0d88155b | 726 | |
90dc2e5b | 727 | for ( Standard_Integer anIndex = 0; anIndex < 3; ++anIndex ) |
728 | { | |
729 | if ( e[anIndex] == theEdgeId ) | |
730 | { | |
731 | DeleteTriangle( anElemId, theLoopEdges ); | |
732 | for ( Standard_Integer n = 0; n < 2; ++n ) | |
733 | { | |
734 | Standard_Integer aCurEdge = e[(anIndex + n + 1) % 3]; | |
735 | KillInternalTriangles( aCurEdge, theIgnoredEdges, theLoopEdges ); | |
0d88155b O |
736 | } |
737 | } | |
738 | } | |
90dc2e5b | 739 | } |
740 | } | |
0d88155b | 741 | |
90dc2e5b | 742 | //======================================================================= |
743 | //function : RemovePivotTriangles | |
744 | //purpose : Removes triangles around the given pivot node | |
745 | //======================================================================= | |
746 | void BRepMesh_Delaun::RemovePivotTriangles( const Standard_Integer theEdgeInfo, | |
747 | const Standard_Integer thePivotNode, | |
748 | TColStd_MapOfInteger& theInfectedEdges, | |
749 | BRepMesh_MapOfIntegerInteger& theLoopEdges, | |
750 | const Standard_Boolean isFirstPass ) | |
751 | { | |
752 | Standard_Integer e[3]; | |
753 | Standard_Boolean o[3]; | |
754 | Standard_Integer aGeneralEdgeId = -1; | |
755 | ||
756 | Standard_Integer anMainEdgeId = Abs( theEdgeInfo ); | |
757 | Standard_Boolean anIsForward = theEdgeInfo > 0; | |
758 | const BRepMesh_PairOfIndex& aPair = myMeshData->ElemConnectedTo( anMainEdgeId ); | |
759 | for ( Standard_Integer j = 1, jn = aPair.Extent(); j <= jn; ++j ) | |
760 | { | |
761 | Standard_Integer anElemId = aPair.Index(j); | |
762 | if( anElemId < 0 ) | |
763 | continue; | |
764 | ||
765 | GetTriangle( anElemId ).Edges( e[0], e[1], e[2], | |
766 | o[0], o[1], o[2] ); | |
0d88155b | 767 | |
90dc2e5b | 768 | Standard_Boolean isFind = Standard_False; |
769 | for ( Standard_Integer anIndex = 0; anIndex < 3; ++anIndex ) | |
770 | { | |
771 | if ( e[anIndex] == anMainEdgeId && o[anIndex] == anIsForward ) | |
772 | { | |
773 | // triangle detected | |
774 | DeleteTriangle( anElemId, theLoopEdges ); | |
775 | aGeneralEdgeId = anIndex; | |
776 | break; | |
0d88155b | 777 | } |
90dc2e5b | 778 | } |
779 | ||
780 | if ( aGeneralEdgeId != -1 ) | |
781 | break; | |
782 | } | |
0d88155b | 783 | |
90dc2e5b | 784 | if ( aGeneralEdgeId != -1 ) |
785 | { | |
786 | // delete triangles around of aPivotNode starting from the bounding one | |
787 | // define edge connected to vertes | |
788 | Standard_Integer anEdgeId = -1; | |
789 | for ( Standard_Integer i = 0; i < 2; ++i ) | |
790 | { | |
791 | Standard_Integer aTmpEdgeId = e[(aGeneralEdgeId + i + 1) % 3]; | |
792 | const BRepMesh_Edge& anEdge = GetEdge( aTmpEdgeId ); | |
793 | if ( anEdge.FirstNode() == thePivotNode || | |
794 | anEdge.LastNode() == thePivotNode ) | |
795 | { | |
796 | anEdgeId = aTmpEdgeId; | |
0d88155b | 797 | } |
90dc2e5b | 798 | |
799 | if ( theInfectedEdges.Contains( aTmpEdgeId ) ) | |
800 | theInfectedEdges.Remove( aTmpEdgeId ); | |
801 | else | |
802 | theInfectedEdges.Add( aTmpEdgeId ); | |
0d88155b | 803 | } |
90dc2e5b | 804 | |
805 | if ( isFirstPass ) | |
806 | return; | |
807 | ||
808 | while ( anEdgeId > 0 ) | |
809 | { | |
810 | const BRepMesh_PairOfIndex& aFreePair = myMeshData->ElemConnectedTo( anEdgeId ); | |
811 | Standard_Integer anOldEdge = anEdgeId; | |
812 | anEdgeId = -1; | |
813 | ||
814 | for ( Standard_Integer aPairIndex = 1; aPairIndex <= aFreePair.Extent(); ++aPairIndex ) | |
815 | { | |
816 | Standard_Integer anElemId = aFreePair.Index( aPairIndex ); | |
817 | if( anElemId < 0 ) | |
818 | continue; | |
819 | ||
820 | Standard_Integer e1[3]; | |
821 | Standard_Boolean o1[3]; | |
822 | GetTriangle( anElemId ).Edges( e1[0], e1[1], e1[2], | |
823 | o1[0], o1[1], o1[2] ); | |
824 | ||
825 | DeleteTriangle( anElemId, theLoopEdges ); | |
826 | ||
827 | for ( Standard_Integer i = 0; i < 3; ++i ) | |
828 | { | |
829 | if ( e1[i] == anOldEdge ) | |
830 | { | |
831 | for ( Standard_Integer i = 0; i < 2; ++i ) | |
832 | { | |
833 | Standard_Integer aTmpEdgeId = e1[(i + 1) % 3]; | |
834 | const BRepMesh_Edge& anEdge = GetEdge( aTmpEdgeId ); | |
835 | if ( anEdge.FirstNode() == thePivotNode || | |
836 | anEdge.LastNode() == thePivotNode ) | |
837 | { | |
838 | anEdgeId = aTmpEdgeId; | |
839 | } | |
840 | ||
841 | if ( theInfectedEdges.Contains( aTmpEdgeId ) ) | |
842 | theInfectedEdges.Remove( aTmpEdgeId ); | |
843 | else | |
844 | theInfectedEdges.Add( aTmpEdgeId ); | |
845 | } | |
846 | break; | |
847 | } | |
0d88155b O |
848 | } |
849 | } | |
0d88155b O |
850 | } |
851 | } | |
852 | } | |
853 | ||
854 | //======================================================================= | |
90dc2e5b | 855 | //function : CleanupPolygon |
856 | //purpose : Remove internal triangles from the given polygon | |
0d88155b | 857 | //======================================================================= |
90dc2e5b | 858 | void BRepMesh_Delaun::CleanupPolygon( const TColStd_SequenceOfInteger& thePolygon, |
859 | TColStd_MapOfInteger& theInfectedEdges, | |
860 | BRepMesh_MapOfIntegerInteger& theLoopEdges ) | |
0d88155b | 861 | { |
90dc2e5b | 862 | Standard_Integer aPolyLen = thePolygon.Length(); |
0d88155b | 863 | |
90dc2e5b | 864 | TColStd_MapOfInteger anIgnoredEdges; |
865 | NCollection_Map<Standard_Integer> aPolyVertices; | |
866 | for ( Standard_Integer i = 1; i <= aPolyLen; ++i ) | |
867 | { | |
868 | Standard_Integer aPolyEdgeId = Abs( thePolygon(i) ); | |
869 | anIgnoredEdges.Add( aPolyEdgeId ); | |
0d88155b | 870 | |
90dc2e5b | 871 | const BRepMesh_Edge& aPolyEdge = GetEdge( aPolyEdgeId ); |
872 | aPolyVertices.Add( aPolyEdge.FirstNode() ); | |
873 | aPolyVertices.Add( aPolyEdge.LastNode() ); | |
0d88155b | 874 | |
90dc2e5b | 875 | if ( theInfectedEdges.Contains( aPolyEdgeId ) ) |
876 | theInfectedEdges.Remove( aPolyEdgeId ); | |
877 | } | |
0d88155b | 878 | |
90dc2e5b | 879 | Standard_Real aRefTotalAngle = 2 * M_PI; |
880 | TColStd_MapIteratorOfMapOfInteger anInfectedIt( theInfectedEdges ); | |
881 | for ( ; anInfectedIt.More(); anInfectedIt.Next() ) | |
882 | { | |
883 | Standard_Integer anEdgeId = anInfectedIt.Key(); | |
884 | const BRepMesh_Edge& anInfectedEdge = GetEdge( anEdgeId ); | |
885 | Standard_Integer anEdgeVertices[2] = { anInfectedEdge.FirstNode(), | |
886 | anInfectedEdge.LastNode() }; | |
0d88155b | 887 | |
90dc2e5b | 888 | Standard_Boolean isToExclude = Standard_False; |
889 | for ( Standard_Integer i = 0; i < 2; ++i ) | |
890 | { | |
891 | Standard_Integer aCurVertex = anEdgeVertices[i]; | |
892 | if ( aPolyVertices.Contains( aCurVertex ) ) | |
893 | continue; | |
0d88155b | 894 | |
90dc2e5b | 895 | gp_XY aCenterPointXY = GetVertex( aCurVertex ).Coord(); |
896 | Standard_Real aTotalAng = 0.0; | |
897 | ||
898 | for ( Standard_Integer i = 1; i <= aPolyLen; ++i ) | |
899 | { | |
900 | Standard_Integer aPolyEdgeId = thePolygon(i); | |
901 | const BRepMesh_Edge& aPolyEdge = GetEdge( Abs( aPolyEdgeId ) ); | |
902 | Standard_Integer aStartPoint, anEndPoint; | |
903 | if ( aPolyEdgeId >= 0 ) | |
904 | { | |
905 | aStartPoint = aPolyEdge.FirstNode(); | |
906 | anEndPoint = aPolyEdge.LastNode(); | |
0d88155b | 907 | } |
90dc2e5b | 908 | else |
909 | { | |
910 | aStartPoint = aPolyEdge.LastNode(); | |
911 | anEndPoint = aPolyEdge.FirstNode(); | |
912 | } | |
913 | ||
914 | gp_XY aStartV = GetVertex( aStartPoint ).Coord() - aCenterPointXY; | |
915 | gp_XY anEndV = GetVertex( anEndPoint ).Coord() - aCenterPointXY; | |
916 | ||
917 | Standard_Real anAngle = gp_Vec2d( anEndV ).Angle( gp_Vec2d( aStartV ) ); | |
918 | aTotalAng += anAngle; | |
919 | } | |
920 | ||
921 | if ( Abs( aRefTotalAngle - aTotalAng ) > Precision::Angular() ) | |
922 | isToExclude = Standard_True; | |
0d88155b | 923 | } |
90dc2e5b | 924 | |
925 | if ( isToExclude ) | |
926 | anIgnoredEdges.Add( anEdgeId ); | |
0d88155b O |
927 | } |
928 | ||
90dc2e5b | 929 | |
930 | anInfectedIt.Initialize( theInfectedEdges ); | |
931 | for ( ; anInfectedIt.More(); anInfectedIt.Next() ) | |
932 | { | |
933 | Standard_Integer anEdgeId = anInfectedIt.Key(); | |
934 | KillInternalTriangles( anEdgeId, anIgnoredEdges, theLoopEdges); | |
0d88155b O |
935 | } |
936 | ||
90dc2e5b | 937 | BRepMesh_MapOfIntegerInteger::Iterator aLoopEdgesIt( theLoopEdges ); |
938 | for ( ; aLoopEdgesIt.More(); aLoopEdgesIt.Next() ) | |
939 | { | |
940 | if ( myMeshData->ElemConnectedTo( aLoopEdgesIt.Key() ).IsEmpty() ) | |
941 | myMeshData->RemoveLink( aLoopEdgesIt.Key() ); | |
0d88155b O |
942 | } |
943 | } | |
944 | ||
945 | //======================================================================= | |
90dc2e5b | 946 | //function : MeshLeftPolygonOf |
947 | //purpose : Triangulation of the aPolygonon to the left of <theEdgeIndex>.(material side) | |
0d88155b | 948 | //======================================================================= |
90dc2e5b | 949 | void BRepMesh_Delaun::MeshLeftPolygonOf( const Standard_Integer theEdgeIndex, |
950 | const Standard_Boolean isForward ) | |
0d88155b | 951 | { |
90dc2e5b | 952 | const BRepMesh_Edge& anEdge = GetEdge( theEdgeIndex ); |
953 | NCollection_Map<Standard_Integer> aDealLinks; | |
954 | TColStd_SequenceOfInteger aPolygon; | |
955 | BRepMesh_MapOfIntegerInteger aLoopEdges( 10, myMeshData->Allocator() ); | |
956 | TColStd_MapOfInteger anUsedEdges; | |
957 | TColStd_MapOfInteger anInfectedEdges; | |
958 | ||
959 | // Find the aPolygonon | |
960 | anUsedEdges.Add( theEdgeIndex ); | |
961 | Standard_Integer aFirstNode, aStartNode, aPivotNode; | |
962 | ||
963 | if ( isForward ) | |
964 | { | |
965 | aPolygon.Append( theEdgeIndex ); | |
966 | aStartNode = anEdge.FirstNode(); | |
967 | aPivotNode = anEdge.LastNode(); | |
968 | } | |
969 | else | |
970 | { | |
971 | aPolygon.Append( -theEdgeIndex ); | |
972 | aStartNode = anEdge.LastNode(); | |
973 | aPivotNode = anEdge.FirstNode(); | |
974 | } | |
975 | aFirstNode = aStartNode; | |
0d88155b | 976 | |
90dc2e5b | 977 | const BRepMesh_Vertex& aStartVertex = GetVertex( aFirstNode ); |
978 | const BRepMesh_Vertex& anEndVertex = GetVertex( aPivotNode ); | |
0d88155b | 979 | |
90dc2e5b | 980 | Standard_Integer aRefOtherNode = 0, anOtherNode = 0; |
981 | // Check the presence of the previous edge <theEdgeIndex> : | |
982 | BRepMesh_ListOfInteger::Iterator aLinkIt( myMeshData->LinkNeighboursOf( aStartNode ) ); | |
983 | for ( ; aLinkIt.More(); aLinkIt.Next() ) | |
2b59653e | 984 | { |
90dc2e5b | 985 | if ( aLinkIt.Value() != theEdgeIndex ) |
986 | { | |
987 | const BRepMesh_Edge& aNextEdge = GetEdge( aLinkIt.Value() ); | |
988 | anOtherNode = aNextEdge.LastNode(); | |
989 | if ( anOtherNode == aStartNode ) | |
990 | anOtherNode = aNextEdge.FirstNode(); | |
991 | break; | |
992 | } | |
993 | } | |
994 | if ( anOtherNode == 0 ) | |
995 | return; | |
0d88155b | 996 | |
90dc2e5b | 997 | |
998 | gp_XY aVEdge( anEndVertex.Coord() ); | |
999 | aVEdge.Subtract( aStartVertex.Coord() ); | |
1000 | gp_XY aPrevVEdge( aVEdge ); | |
1001 | gp_XY aRefCurrVEdge, aCurrVEdge; | |
1002 | ||
1003 | Standard_Integer aCurrEdgeId = theEdgeIndex; | |
1004 | Standard_Integer aNextEdgeId; | |
1005 | ||
1006 | // Find the nearest to <theEdgeIndex> closed aPolygonon : | |
1007 | Standard_Boolean isInMesh, isNotInters; | |
1008 | Standard_Real anAngle, aRefAngle; | |
1009 | ||
1010 | NCollection_Vector <Bnd_Box2d> aBoxes; | |
1011 | fillBndBox( aBoxes, aStartVertex, anEndVertex ); | |
2b59653e | 1012 | |
90dc2e5b | 1013 | while ( aPivotNode != aFirstNode ) |
1014 | { | |
1015 | aNextEdgeId = 0; | |
1016 | if ( myPositiveOrientation ) | |
1017 | aRefAngle = RealFirst(); | |
1018 | else | |
1019 | aRefAngle = RealLast(); | |
0d88155b | 1020 | |
90dc2e5b | 1021 | const BRepMesh_Vertex& aPivotVertex = GetVertex( aPivotNode ); |
1022 | ||
1023 | // Find the next edge with the greatest angle with <theEdgeIndex> | |
1024 | // and non intersecting <theEdgeIndex> : | |
1025 | ||
1026 | aLinkIt.Init( myMeshData->LinkNeighboursOf( aPivotNode ) ); | |
1027 | for ( ; aLinkIt.More(); aLinkIt.Next() ) | |
1028 | { | |
1029 | Standard_Integer aNextLink = aLinkIt.Value(); | |
1030 | Standard_Integer aNextLinkId = Abs( aNextLink ); | |
1031 | if ( aDealLinks.Contains( aNextLinkId ) ) | |
1032 | continue; | |
1033 | ||
1034 | if ( aNextLinkId != aCurrEdgeId ) | |
1035 | { | |
1036 | isNotInters = Standard_True; | |
1037 | const BRepMesh_Edge& aNextEdge = GetEdge( aNextLinkId ); | |
1038 | ||
1039 | isInMesh = Standard_True; | |
1040 | ||
1041 | //define if link exist in mesh | |
1042 | if ( aNextEdge.Movability() == BRepMesh_Free ) | |
1043 | { | |
1044 | if ( myMeshData->ElemConnectedTo( aLinkIt.Value() ).IsEmpty() ) | |
1045 | isInMesh = Standard_False; | |
2b59653e | 1046 | } |
0d88155b | 1047 | |
90dc2e5b | 1048 | if ( isInMesh ) |
1049 | { | |
1050 | anOtherNode = aNextEdge.FirstNode(); | |
1051 | if ( anOtherNode == aPivotNode ) | |
1052 | anOtherNode = aNextEdge.LastNode(); | |
1053 | ||
1054 | aCurrVEdge = GetVertex( anOtherNode ).Coord(); | |
1055 | aCurrVEdge.Subtract( aPivotVertex.Coord() ); | |
1056 | ||
1057 | if ( aCurrVEdge.Modulus() >= gp::Resolution() && | |
1058 | aPrevVEdge.Modulus() >= gp::Resolution() ) | |
1059 | { | |
1060 | anAngle = gp_Vec2d( aPrevVEdge ).Angle( gp_Vec2d( aCurrVEdge ) ); | |
1061 | ||
1062 | if ( ( myPositiveOrientation && anAngle > aRefAngle ) || | |
1063 | ( !myPositiveOrientation && anAngle < aRefAngle ) ) | |
1064 | { | |
1065 | Bnd_Box2d aBox; | |
1066 | aBox.Add( gp_Pnt2d( GetVertex( aNextEdge.FirstNode() ).Coord() ) ); | |
1067 | aBox.Add( gp_Pnt2d( GetVertex( aNextEdge.LastNode() ).Coord() ) ); | |
1068 | ||
1069 | for ( Standard_Integer k = 0, aLen = aPolygon.Length(); k < aLen; ++k ) | |
1070 | { | |
1071 | if ( !aBox.IsOut( aBoxes.Value( k ) ) ) | |
1072 | { | |
1073 | // intersection is possible... | |
1074 | if ( IntSegSeg( aNextEdge, GetEdge( Abs( aPolygon( k + 1 ) ) ) ) ) | |
1075 | { | |
1076 | isNotInters = Standard_False; | |
1077 | break; | |
1078 | } | |
1079 | } | |
1080 | } | |
1081 | ||
1082 | if( isNotInters ) | |
1083 | { | |
1084 | aRefAngle = anAngle; | |
1085 | aRefCurrVEdge = aCurrVEdge; | |
1086 | ||
1087 | if ( aNextEdge.FirstNode() == aPivotNode ) | |
1088 | aNextEdgeId = aLinkIt.Value(); | |
1089 | else | |
1090 | aNextEdgeId = -aLinkIt.Value(); | |
1091 | ||
1092 | aRefOtherNode = anOtherNode; | |
1093 | } | |
1094 | } | |
2b59653e E |
1095 | } |
1096 | } | |
0d88155b | 1097 | } |
90dc2e5b | 1098 | } |
1099 | if ( aNextEdgeId != 0 ) | |
1100 | { | |
1101 | if ( Abs( aNextEdgeId ) != theEdgeIndex && Abs( aNextEdgeId ) != aCurrEdgeId ) | |
1102 | { | |
1103 | aCurrEdgeId = Abs( aNextEdgeId ); | |
2b59653e | 1104 | |
90dc2e5b | 1105 | if ( !anUsedEdges.Add( aCurrEdgeId ) ) |
1106 | { | |
1107 | //if this edge has already been added to the aPolygon, | |
1108 | //there is a risk of looping (attention to open contours) | |
1109 | //remove last edge and continue | |
1110 | ||
1111 | aDealLinks.Add( aCurrEdgeId ); | |
1112 | ||
1113 | //roll back | |
1114 | continue; | |
1115 | } | |
1116 | ||
1117 | aPolygon.Append( aNextEdgeId ); | |
1118 | ||
1119 | const BRepMesh_Edge& aCurrEdge = GetEdge( aCurrEdgeId ); | |
1120 | Standard_Integer aVert1 = aCurrEdge.FirstNode(); | |
1121 | Standard_Integer aVert2 = aCurrEdge.LastNode(); | |
1122 | fillBndBox( aBoxes, GetVertex( aVert1 ), GetVertex( aVert2 ) ); | |
1123 | ||
1124 | RemovePivotTriangles( aNextEdgeId, aPivotNode, | |
1125 | anInfectedEdges, aLoopEdges, (aPolygon.Length() == 2) ); | |
1126 | } | |
0d88155b | 1127 | } |
90dc2e5b | 1128 | else |
1129 | { | |
1130 | //hanging end | |
1131 | if ( aPolygon.Length() == 1 ) | |
1132 | return; | |
0d88155b | 1133 | |
90dc2e5b | 1134 | Standard_Integer aDeadEdgeId = Abs( aPolygon.Last() ); |
1135 | const BRepMesh_Edge& aDeadEdge = GetEdge( aDeadEdgeId ); | |
1136 | ||
1137 | aDealLinks.Add( aDeadEdgeId ); | |
1138 | ||
1139 | anUsedEdges.Remove( aDeadEdgeId ); | |
1140 | aPolygon.Remove( aPolygon.Length() ); | |
1141 | ||
1142 | // return to previous point | |
1143 | Standard_Integer aLastValidEdge = aPolygon.Last(); | |
1144 | const BRepMesh_Edge& aLastEdge = GetEdge( Abs( aLastValidEdge ) ); | |
1145 | ||
1146 | if( aLastValidEdge > 0 ) | |
1147 | { | |
1148 | aStartNode = aLastEdge.FirstNode(); | |
1149 | aPivotNode = aLastEdge.LastNode(); | |
1150 | } | |
1151 | else | |
1152 | { | |
1153 | aStartNode = aLastEdge.LastNode(); | |
1154 | aPivotNode = aLastEdge.FirstNode(); | |
1155 | } | |
1156 | ||
1157 | const BRepMesh_Vertex& dV = GetVertex( aStartNode ); | |
1158 | const BRepMesh_Vertex& fV = GetVertex( aPivotNode ); | |
1159 | aPrevVEdge = fV.Coord() - dV.Coord(); | |
1160 | continue; | |
0d88155b | 1161 | } |
90dc2e5b | 1162 | |
1163 | aStartNode = aPivotNode; | |
1164 | aPivotNode = aRefOtherNode; | |
1165 | aPrevVEdge = aRefCurrVEdge; | |
2b59653e | 1166 | } |
0d88155b | 1167 | |
90dc2e5b | 1168 | CleanupPolygon( aPolygon, anInfectedEdges, aLoopEdges ); |
1169 | MeshPolygon( aPolygon ); | |
2b59653e | 1170 | } |
0d88155b | 1171 | |
2b59653e | 1172 | //======================================================================= |
90dc2e5b | 1173 | //function : MeshPolygon |
1174 | //purpose : Triangulatiion of a closed aPolygonon described by the list of indexes of | |
1175 | // its edges in the structure. (negative index == reversed) | |
2b59653e | 1176 | //======================================================================= |
90dc2e5b | 1177 | void BRepMesh_Delaun::MeshPolygon( TColStd_SequenceOfInteger& thePoly ) |
2b59653e | 1178 | { |
90dc2e5b | 1179 | Standard_Integer aPivotNode, aVertex3 = 0; |
1180 | Standard_Integer aFirstNode, aLastNode; | |
1181 | Standard_Integer aTriId; | |
0d88155b | 1182 | |
90dc2e5b | 1183 | if ( thePoly.Length() == 3 ) |
1184 | { | |
1185 | aTriId = myMeshData->AddElement( BRepMesh_Triangle( | |
1186 | Abs( thePoly(1) ), Abs( thePoly(2) ), Abs( thePoly(3) ), | |
1187 | thePoly(1) > 0, thePoly(2) > 0, thePoly(3) > 0, | |
1188 | BRepMesh_Free ) ); | |
1189 | ||
1190 | myCircles.MocAdd( aTriId ); | |
1191 | const BRepMesh_Edge& anEdge1 = GetEdge( Abs( thePoly(1) ) ); | |
1192 | const BRepMesh_Edge& anEdge2 = GetEdge( Abs( thePoly(2) ) ); | |
1193 | ||
1194 | if ( thePoly(1) > 0) | |
1195 | { | |
1196 | aFirstNode = anEdge1.FirstNode(); | |
1197 | aLastNode = anEdge1.LastNode(); | |
1198 | } | |
1199 | else | |
1200 | { | |
1201 | aFirstNode = anEdge1.LastNode(); | |
1202 | aLastNode = anEdge1.FirstNode(); | |
1203 | } | |
1204 | ||
1205 | if ( thePoly(2) > 0 ) | |
1206 | aVertex3 = anEdge2.LastNode(); | |
1207 | else | |
1208 | aVertex3 = anEdge2.FirstNode(); | |
0d88155b | 1209 | |
90dc2e5b | 1210 | Standard_Boolean isAdded = myCircles.Add( GetVertex( aFirstNode ).Coord(), |
1211 | GetVertex( aLastNode ).Coord(), GetVertex( aVertex3 ).Coord(), aTriId ); | |
1212 | ||
1213 | if ( !isAdded ) | |
1214 | myMeshData->RemoveElement( aTriId ); | |
1215 | } | |
1216 | else if ( thePoly.Length() > 3 ) | |
2b59653e | 1217 | { |
90dc2e5b | 1218 | NCollection_Vector <Bnd_Box2d> aBoxes; |
1219 | Standard_Integer aPolyIdx, aUsedIdx = 0; | |
1220 | Standard_Integer aPolyLen = thePoly.Length(); | |
1221 | ||
1222 | for ( aPolyIdx = 1; aPolyIdx <= aPolyLen; ++aPolyIdx ) | |
1223 | { | |
1224 | const BRepMesh_Edge& anEdge = GetEdge( Abs( thePoly( aPolyIdx ) ) ); | |
1225 | aFirstNode = anEdge.FirstNode(); | |
1226 | aLastNode = anEdge.LastNode(); | |
1227 | fillBndBox( aBoxes, GetVertex( aFirstNode ), GetVertex( aLastNode ) ); | |
1228 | } | |
1229 | ||
1230 | const BRepMesh_Edge& anEdge = GetEdge( Abs( thePoly(1) ) ); | |
1231 | Standard_Real aMinDist = RealLast(); | |
1232 | ||
1233 | if ( thePoly(1) > 0 ) | |
1234 | { | |
1235 | aFirstNode = anEdge.FirstNode(); | |
1236 | aLastNode = anEdge.LastNode(); | |
1237 | } | |
1238 | else | |
2b59653e | 1239 | { |
90dc2e5b | 1240 | aFirstNode = anEdge.LastNode(); |
1241 | aLastNode = anEdge.FirstNode(); | |
1242 | } | |
1243 | ||
1244 | gp_XY aVEdge( GetVertex( aLastNode ).Coord() - | |
1245 | GetVertex( aFirstNode ).Coord() ); | |
1246 | ||
1247 | Standard_Real aVEdgeLen = aVEdge.Modulus(); | |
1248 | if ( aVEdgeLen > 0.) | |
1249 | { | |
1250 | aVEdge.SetCoord( aVEdge.X() / aVEdgeLen, | |
1251 | aVEdge.Y() / aVEdgeLen ); | |
1252 | ||
1253 | for ( aPolyIdx = 3; aPolyIdx <= aPolyLen; ++aPolyIdx ) | |
1254 | { | |
1255 | const BRepMesh_Edge& aNextEdge = GetEdge( Abs( thePoly( aPolyIdx ) ) ); | |
1256 | if ( thePoly( aPolyIdx ) > 0) | |
1257 | aPivotNode = aNextEdge.FirstNode(); | |
1258 | else | |
1259 | aPivotNode = aNextEdge.LastNode(); | |
1260 | ||
1261 | gp_XY aVEdgePivot( GetVertex( aPivotNode ).Coord() - | |
1262 | GetVertex( aLastNode ).Coord() ); | |
1263 | ||
1264 | Standard_Real aDist = aVEdge ^ aVEdgePivot; | |
1265 | if ( Abs( aDist ) > Precision::PConfusion() ) | |
1266 | { | |
1267 | if ( ( aDist > 0. && myPositiveOrientation ) || | |
1268 | ( aDist < 0. && !myPositiveOrientation ) ) | |
1269 | { | |
1270 | if ( Abs( aDist ) < aMinDist ) | |
1271 | { | |
1272 | Bnd_Box2d aBoxFirst, aBoxLast; | |
1273 | aBoxFirst.Add( gp_Pnt2d( GetVertex( aPivotNode ).Coord() ) ); | |
1274 | aBoxFirst.Add( gp_Pnt2d( GetVertex( aLastNode ).Coord() ) ); | |
1275 | ||
1276 | aBoxLast.Add( gp_Pnt2d( GetVertex( aPivotNode ).Coord() ) ); | |
1277 | aBoxLast.Add( gp_Pnt2d( GetVertex( aFirstNode ).Coord() ) ); | |
1278 | ||
1279 | BRepMesh_Edge aCheckE1( aLastNode, aPivotNode, BRepMesh_Free ); | |
1280 | BRepMesh_Edge aCheckE2( aFirstNode, aPivotNode, BRepMesh_Free ); | |
1281 | ||
1282 | Standard_Boolean isIntersect = Standard_False; | |
1283 | for ( Standard_Integer aPolyIdx1 = 2; aPolyIdx1 <= aPolyLen; ++aPolyIdx1 ) | |
1284 | { | |
1285 | if( aPolyIdx1 == aPolyIdx ) | |
1286 | continue; | |
1287 | ||
1288 | const BRepMesh_Edge& aNextEdge1 = GetEdge( Abs( thePoly( aPolyIdx1 ) ) ); | |
1289 | if ( !aBoxFirst.IsOut( aBoxes.Value( aPolyIdx1 - 1 ) ) ) | |
1290 | { | |
1291 | // intersection is possible... | |
1292 | if( IntSegSeg( aCheckE1, aNextEdge1 ) ) | |
1293 | { | |
1294 | isIntersect = Standard_True; | |
1295 | break; | |
1296 | } | |
1297 | } | |
1298 | ||
1299 | if ( !aBoxLast.IsOut( aBoxes.Value( aPolyIdx1 - 1 ) ) && | |
1300 | !aCheckE2.IsEqual( aNextEdge1 ) ) | |
1301 | { | |
1302 | // intersection is possible... | |
1303 | if( IntSegSeg( aCheckE2, aNextEdge1 ) ) | |
1304 | { | |
1305 | isIntersect = Standard_True; | |
1306 | break; | |
1307 | } | |
1308 | } | |
1309 | } | |
1310 | ||
1311 | if( !isIntersect ) | |
1312 | { | |
1313 | aMinDist = aDist; | |
1314 | aVertex3 = aPivotNode; | |
1315 | aUsedIdx = aPolyIdx; | |
1316 | } | |
1317 | } | |
1318 | } | |
1319 | } | |
1320 | } | |
1321 | } | |
1322 | ||
1323 | Standard_Integer aNewEdge2, aNewEdge3; | |
1324 | if ( aMinDist < RealLast() ) | |
1325 | { | |
1326 | aNewEdge2 = myMeshData->AddLink( BRepMesh_Edge( aLastNode, aVertex3, BRepMesh_Free ) ); | |
1327 | aNewEdge3 = myMeshData->AddLink( BRepMesh_Edge( aVertex3, aFirstNode, BRepMesh_Free ) ); | |
1328 | aTriId = myMeshData->AddElement( BRepMesh_Triangle( | |
1329 | Abs( thePoly(1) ), Abs( aNewEdge2 ), Abs( aNewEdge3 ), | |
1330 | thePoly(1) > 0, aNewEdge2 > 0, aNewEdge3 > 0, | |
1331 | BRepMesh_Free ) ); | |
1332 | ||
1333 | Standard_Boolean isAdded = myCircles.Add( GetVertex( aFirstNode ).Coord(), | |
1334 | GetVertex( aLastNode ).Coord(), GetVertex( aVertex3 ).Coord(), aTriId ); | |
1335 | ||
1336 | if ( !isAdded ) | |
1337 | myMeshData->RemoveElement( aTriId ); | |
1338 | ||
1339 | if ( aUsedIdx < aPolyLen ) | |
1340 | { | |
1341 | TColStd_SequenceOfInteger aSuitePoly; | |
1342 | thePoly.Split( aUsedIdx, aSuitePoly ); | |
1343 | aSuitePoly.Prepend( -aNewEdge3 ); | |
1344 | MeshPolygon( aSuitePoly ); | |
1345 | } | |
1346 | else | |
1347 | thePoly.Remove( aPolyLen ); | |
1348 | ||
1349 | if ( aUsedIdx > 3 ) | |
1350 | { | |
1351 | thePoly.SetValue( 1, -aNewEdge2 ); | |
1352 | MeshPolygon( thePoly ); | |
1353 | } | |
2b59653e | 1354 | } |
0d88155b | 1355 | } |
0d88155b O |
1356 | } |
1357 | ||
1358 | //======================================================================= | |
1359 | //function : RemoveVertex | |
90dc2e5b | 1360 | //purpose : Removes a vertex from the triangulation |
0d88155b | 1361 | //======================================================================= |
90dc2e5b | 1362 | void BRepMesh_Delaun::RemoveVertex( const BRepMesh_Vertex& theVertex ) |
0d88155b | 1363 | { |
90dc2e5b | 1364 | BRepMesh_SelectorOfDataStructureOfDelaun aSelector( myMeshData ); |
1365 | aSelector.NeighboursOf( theVertex ); | |
0d88155b | 1366 | |
90dc2e5b | 1367 | BRepMesh_MapOfIntegerInteger aLoopEdges( 10, myMeshData->Allocator() ); |
0d88155b O |
1368 | |
1369 | // Loop on triangles to be destroyed : | |
90dc2e5b | 1370 | BRepMesh_MapOfInteger::Iterator aTriangleIt( aSelector.Elements() ); |
1371 | for ( ; aTriangleIt.More(); aTriangleIt.Next() ) | |
1372 | DeleteTriangle( aTriangleIt.Key(), aLoopEdges ); | |
0d88155b | 1373 | |
90dc2e5b | 1374 | TColStd_SequenceOfInteger aPolygon; |
1375 | Standard_Integer aLoopEdgesCount = aLoopEdges.Extent(); | |
1376 | BRepMesh_MapOfIntegerInteger::Iterator aLoopEdgesIt( aLoopEdges ); | |
1377 | ||
1378 | if ( aLoopEdgesIt.More() ) | |
1379 | { | |
1380 | const BRepMesh_Edge& anEdge = GetEdge( aLoopEdgesIt.Key() ); | |
1381 | Standard_Integer aFirstNode = anEdge.FirstNode(); | |
1382 | Standard_Integer aLastNode; | |
1383 | Standard_Integer aPivotNode = anEdge.LastNode(); | |
1384 | Standard_Integer anEdgeId = aLoopEdgesIt.Key(); | |
1385 | ||
1386 | Standard_Boolean isPositive = (Standard_Boolean)aLoopEdges( anEdgeId ); | |
1387 | if ( !isPositive ) | |
1388 | { | |
1389 | Standard_Integer aTmp; | |
1390 | aTmp = aFirstNode; | |
1391 | aFirstNode = aPivotNode; | |
1392 | aPivotNode = aTmp; | |
1393 | ||
1394 | aPolygon.Append( -anEdgeId ); | |
0d88155b | 1395 | } |
90dc2e5b | 1396 | else |
1397 | aPolygon.Append( anEdgeId ); | |
1398 | ||
1399 | aLoopEdges.UnBind( anEdgeId ); | |
1400 | ||
1401 | aLastNode = aFirstNode; | |
1402 | while ( aPivotNode != aLastNode ) | |
1403 | { | |
1404 | BRepMesh_ListOfInteger::Iterator aLinkIt( myMeshData->LinkNeighboursOf( aPivotNode ) ); | |
1405 | for ( ; aLinkIt.More(); aLinkIt.Next() ) | |
1406 | { | |
1407 | if ( aLinkIt.Value() != anEdgeId && | |
1408 | aLoopEdges.IsBound( aLinkIt.Value() ) ) | |
1409 | { | |
1410 | Standard_Integer aCurrentNode; | |
1411 | anEdgeId = aLinkIt.Value(); | |
1412 | const BRepMesh_Edge& anEdge1 = GetEdge( anEdgeId ); | |
1413 | ||
1414 | aCurrentNode = anEdge1.LastNode(); | |
1415 | if ( aCurrentNode != aPivotNode ) | |
1416 | { | |
1417 | aCurrentNode = anEdge1.FirstNode(); | |
1418 | aPolygon.Append( -anEdgeId ); | |
0d88155b O |
1419 | } |
1420 | else | |
90dc2e5b | 1421 | aPolygon.Append( anEdgeId ); |
1422 | ||
1423 | aPivotNode = aCurrentNode; | |
1424 | aLoopEdges.UnBind( anEdgeId ); | |
0d88155b O |
1425 | break; |
1426 | } | |
1427 | } | |
90dc2e5b | 1428 | |
1429 | if ( aLoopEdgesCount <= 0 ) | |
1430 | break; | |
1431 | --aLoopEdgesCount; | |
0d88155b | 1432 | } |
90dc2e5b | 1433 | |
1434 | MeshPolygon( aPolygon ); | |
0d88155b O |
1435 | } |
1436 | } | |
1437 | ||
1438 | ||
1439 | //======================================================================= | |
1440 | //function : AddVertices | |
90dc2e5b | 1441 | //purpose : Adds some vertices in the triangulation. |
0d88155b | 1442 | //======================================================================= |
90dc2e5b | 1443 | void BRepMesh_Delaun::AddVertices( BRepMesh_Array1OfVertexOfDelaun& theVertices ) |
0d88155b | 1444 | { |
90dc2e5b | 1445 | BRepMesh_HeapSortVertexOfDelaun::Sort( theVertices, |
1446 | BRepMesh_ComparatorOfVertexOfDelaun( SortingDirection, Precision::PConfusion() ) ); | |
0d88155b | 1447 | |
90dc2e5b | 1448 | Standard_Integer aLower = theVertices.Lower(); |
1449 | Standard_Integer anUpper = theVertices.Upper(); | |
2b59653e | 1450 | |
90dc2e5b | 1451 | TColStd_Array1OfInteger aVertexIndexes( aLower, anUpper ); |
1452 | for ( Standard_Integer i = aLower; i <= anUpper; ++i ) | |
1453 | aVertexIndexes(i) = myMeshData->AddNode( theVertices(i) ); | |
0d88155b | 1454 | |
90dc2e5b | 1455 | CreateTrianglesOnNewVertices( aVertexIndexes ); |
0d88155b O |
1456 | } |
1457 | ||
1458 | //======================================================================= | |
1459 | //function : UseEdge | |
90dc2e5b | 1460 | //purpose : Modify mesh to use the edge. Return True if done |
0d88155b | 1461 | //======================================================================= |
90dc2e5b | 1462 | Standard_Boolean BRepMesh_Delaun::UseEdge( const Standard_Integer theIndex ) |
0d88155b | 1463 | { |
90dc2e5b | 1464 | /* |
1465 | const BRepMesh_PairOfIndex& aPair = myMeshData->ElemConnectedTo( theIndex ); | |
1466 | if ( aPair.Extent() == 0 ) | |
1467 | { | |
1468 | const BRepMesh_Edge& anEdge = GetEdge( theIndex ); | |
1469 | ||
1470 | Standard_Integer aStartNode, aPivotNode, anOtherNode; | |
1471 | aStartNode = anEdge.FirstNode(); | |
1472 | aPivotNode = anEdge.LastNode(); | |
1473 | ||
1474 | const BRepMesh_ListOfInteger& aStartNodeNeighbors = myMeshData->LinkNeighboursOf( aStartNode ); | |
1475 | const BRepMesh_ListOfInteger& aPivotNodeNeighbors = myMeshData->LinkNeighboursOf( aPivotNode ); | |
1476 | ||
1477 | if ( aStartNodeNeighbors.Extent() > 0 && | |
1478 | aPivotNodeNeighbors.Extent() > 0 ) | |
1479 | { | |
1480 | const BRepMesh_Vertex& aStartVertex = GetVertex( aStartNode ); | |
1481 | const BRepMesh_Vertex& aPivotVertex = GetVertex( aPivotNode ); | |
1482 | ||
1483 | gp_XY aVEdge ( aPivotVertex.Coord() ); | |
1484 | aVEdge.Subtract( aStartVertex.Coord() ); | |
1485 | ||
1486 | Standard_Real anAngle = 0.; | |
1487 | Standard_Real anAngleMin = RealLast(); | |
1488 | Standard_Real anAngleMax = RealFirst(); | |
1489 | Standard_Integer aLeftEdge = 0, aRightEdge = 0; | |
1490 | ||
1491 | BRepMesh_ListOfInteger::Iterator aNeighborIt( aPivotNodeNeighbors ); | |
1492 | for ( ; aNeighborIt.More(); aNeighborIt.Next() ) | |
1493 | { | |
1494 | Standard_Integer anEdgeId = aNeighborIt.Value(); | |
1495 | if ( anEdgeId != theIndex ) | |
1496 | { | |
1497 | const BRepMesh_Edge& aNextEdge = GetEdge( anEdgeId ); | |
1498 | ||
1499 | Standard_Boolean isInMesh = Standard_True; | |
1500 | if ( aNextEdge.Movability() == BRepMesh_Free ) | |
1501 | { | |
1502 | if ( myMeshData->ElemConnectedTo( anEdgeId ).IsEmpty() ) | |
1503 | isInMesh = Standard_False; | |
0d88155b O |
1504 | } |
1505 | ||
90dc2e5b | 1506 | if ( isInMesh ) |
1507 | { | |
1508 | anOtherNode = aNextEdge.FirstNode(); | |
1509 | if ( anOtherNode == aPivotNode ) | |
1510 | anOtherNode = aNextEdge.LastNode(); | |
0d88155b | 1511 | |
90dc2e5b | 1512 | gp_XY aVEdgeCur = GetVertex( anOtherNode ).Coord(); |
1513 | aVEdgeCur.Subtract( aPivotVertex.Coord() ); | |
0d88155b | 1514 | |
90dc2e5b | 1515 | anAngle = gp_Vec2d( aVEdge ).Angle( gp_Vec2d( aVEdgeCur ) ); |
0d88155b | 1516 | } |
90dc2e5b | 1517 | |
1518 | if ( anAngle > anAngleMax ) | |
1519 | { | |
1520 | anAngleMax = anAngle; | |
1521 | aLeftEdge = anEdgeId; | |
0d88155b | 1522 | } |
90dc2e5b | 1523 | if ( anAngle < anAngleMin ) |
1524 | { | |
1525 | anAngleMin = anAngle; | |
1526 | aRightEdge = anEdgeId; | |
0d88155b O |
1527 | } |
1528 | } | |
1529 | } | |
90dc2e5b | 1530 | |
1531 | if ( aLeftEdge > 0 ) | |
1532 | { | |
1533 | if (aLeftEdge==aRightEdge) | |
1534 | { | |
0d88155b | 1535 | } |
90dc2e5b | 1536 | else |
1537 | { | |
0d88155b O |
1538 | } |
1539 | } | |
1540 | } | |
1541 | } | |
90dc2e5b | 1542 | */ |
0d88155b O |
1543 | return Standard_False; |
1544 | } | |
1545 | ||
0d88155b O |
1546 | //======================================================================= |
1547 | //function : Result | |
90dc2e5b | 1548 | //purpose : Gives the Mesh data structure |
0d88155b | 1549 | //======================================================================= |
90dc2e5b | 1550 | const Handle( BRepMesh_DataStructureOfDelaun )& BRepMesh_Delaun::Result() const |
0d88155b | 1551 | { |
90dc2e5b | 1552 | return myMeshData; |
0d88155b O |
1553 | } |
1554 | ||
1555 | //======================================================================= | |
1556 | //function : Frontier | |
90dc2e5b | 1557 | //purpose : Gives the list of frontier edges |
0d88155b | 1558 | //======================================================================= |
90dc2e5b | 1559 | const BRepMesh_MapOfInteger& BRepMesh_Delaun::Frontier() |
0d88155b | 1560 | { |
90dc2e5b | 1561 | BRepMesh_MapOfInteger::Iterator anEdgeIt( myMeshData->LinkOfDomain() ); |
0d88155b | 1562 | |
90dc2e5b | 1563 | myMapEdges.Clear(); |
1564 | for ( ; anEdgeIt.More(); anEdgeIt.Next() ) | |
1565 | { | |
1566 | Standard_Integer anEdge = anEdgeIt.Key(); | |
1567 | if ( GetEdge( anEdge ).Movability() == BRepMesh_Frontier ) | |
1568 | myMapEdges.Add( anEdge ); | |
0d88155b | 1569 | } |
90dc2e5b | 1570 | |
1571 | return myMapEdges; | |
0d88155b O |
1572 | } |
1573 | ||
1574 | //======================================================================= | |
1575 | //function : InternalEdges | |
90dc2e5b | 1576 | //purpose : Gives the list of internal edges |
0d88155b | 1577 | //======================================================================= |
90dc2e5b | 1578 | const BRepMesh_MapOfInteger& BRepMesh_Delaun::InternalEdges() |
0d88155b | 1579 | { |
90dc2e5b | 1580 | BRepMesh_MapOfInteger::Iterator anEdgeIt( myMeshData->LinkOfDomain() ); |
0d88155b | 1581 | |
90dc2e5b | 1582 | myMapEdges.Clear(); |
1583 | for ( ; anEdgeIt.More(); anEdgeIt.Next() ) | |
1584 | { | |
1585 | Standard_Integer anEdge = anEdgeIt.Key(); | |
1586 | if ( GetEdge( anEdge ).Movability() == BRepMesh_Fixed ) | |
1587 | myMapEdges.Add( anEdge ); | |
0d88155b | 1588 | } |
90dc2e5b | 1589 | |
1590 | return myMapEdges; | |
0d88155b O |
1591 | } |
1592 | ||
1593 | //======================================================================= | |
1594 | //function : FreeEdges | |
90dc2e5b | 1595 | //purpose : Gives the list of free edges used only one time |
0d88155b | 1596 | //======================================================================= |
90dc2e5b | 1597 | const BRepMesh_MapOfInteger& BRepMesh_Delaun::FreeEdges() |
0d88155b | 1598 | { |
90dc2e5b | 1599 | BRepMesh_MapOfInteger::Iterator anEdgeIt( myMeshData->LinkOfDomain() ); |
0d88155b | 1600 | |
90dc2e5b | 1601 | myMapEdges.Clear(); |
1602 | for ( ; anEdgeIt.More(); anEdgeIt.Next() ) | |
1603 | { | |
1604 | Standard_Integer anEdge = anEdgeIt.Key(); | |
1605 | if ( myMeshData->ElemConnectedTo( anEdge ).Extent() <= 1 ) | |
1606 | myMapEdges.Add( anEdge ); | |
0d88155b | 1607 | } |
90dc2e5b | 1608 | |
1609 | return myMapEdges; | |
0d88155b O |
1610 | } |
1611 | ||
0d88155b | 1612 | //======================================================================= |
90dc2e5b | 1613 | //function : calculateDist |
1614 | //purpose : Calculates distances between the given point and edges of | |
1615 | // triangle | |
0d88155b | 1616 | //======================================================================= |
90dc2e5b | 1617 | static Standard_Real calculateDist( const gp_XY theVEdges[3], |
1618 | const gp_XY thePoints[3], | |
1619 | const Standard_Integer theEdgesId[3], | |
1620 | const BRepMesh_Vertex& theVertex, | |
1621 | Standard_Real theDistance[3], | |
1622 | Standard_Real theSqModulus[3], | |
1623 | Standard_Integer& theEdgeOn ) | |
2b59653e | 1624 | { |
90dc2e5b | 1625 | Standard_Real aMinDist = -1; |
1626 | if ( !theVEdges || !thePoints || !theEdgesId || | |
1627 | !theDistance || !theSqModulus ) | |
1628 | return aMinDist; | |
1629 | ||
1630 | for( Standard_Integer i = 0; i < 3; ++i ) | |
2b59653e | 1631 | { |
90dc2e5b | 1632 | theSqModulus[i] = theVEdges[i].SquareModulus(); |
1633 | if ( theSqModulus[i] <= EPSEPS ) | |
1634 | return -1; | |
1635 | ||
1636 | theDistance[i] = theVEdges[i] ^ ( theVertex.Coord() - thePoints[i] ); | |
1637 | ||
1638 | Standard_Real aDist = theDistance[i] * theDistance[i]; | |
1639 | aDist /= theSqModulus[i]; | |
2b59653e | 1640 | |
90dc2e5b | 1641 | if ( aMinDist < 0 || aDist < aMinDist ) |
2b59653e | 1642 | { |
90dc2e5b | 1643 | theEdgeOn = theEdgesId[i]; |
1644 | aMinDist = aDist; | |
2b59653e E |
1645 | } |
1646 | } | |
90dc2e5b | 1647 | |
1648 | return aMinDist; | |
2b59653e E |
1649 | } |
1650 | ||
90dc2e5b | 1651 | //======================================================================= |
1652 | //function : Contains | |
1653 | //purpose : Test if triangle of index <TrianIndex> contains geometricaly | |
1654 | // <theVertex>. If <theEdgeOn> is != 0 then theVertex is on Edge | |
1655 | // of index <theEdgeOn> | |
1656 | //======================================================================= | |
1657 | Standard_Boolean BRepMesh_Delaun::Contains( const Standard_Integer theTriangleId, | |
1658 | const BRepMesh_Vertex& theVertex, | |
1659 | Standard_Integer& theEdgeOn ) const | |
0d88155b | 1660 | { |
90dc2e5b | 1661 | theEdgeOn = 0; |
1662 | ||
1663 | Standard_Integer e[3]; | |
1664 | Standard_Boolean o[3]; | |
1665 | Standard_Integer p[3]; | |
1666 | ||
1667 | GetTriangle( theTriangleId ).Edges( e[0], e[1], e[2], | |
1668 | o[0], o[1], o[2] ); | |
1669 | ||
1670 | const BRepMesh_Edge* anEdges[3] = { &GetEdge( e[0] ), | |
1671 | &GetEdge( e[1] ), | |
1672 | &GetEdge( e[2] ) }; | |
1673 | if ( o[0] ) | |
1674 | { | |
1675 | p[0] = anEdges[0]->FirstNode(); | |
1676 | p[1] = anEdges[0]->LastNode(); | |
0d88155b | 1677 | } |
90dc2e5b | 1678 | else |
1679 | { | |
1680 | p[1] = anEdges[0]->FirstNode(); | |
1681 | p[0] = anEdges[0]->LastNode(); | |
0d88155b | 1682 | } |
2b59653e | 1683 | |
90dc2e5b | 1684 | if ( o[2] ) |
1685 | p[2] = anEdges[2]->FirstNode(); | |
1686 | else | |
1687 | p[2] = anEdges[2]->LastNode(); | |
1688 | ||
1689 | gp_XY aPoints[3]; | |
1690 | aPoints[0] = GetVertex( p[0] ).Coord(); | |
1691 | aPoints[1] = GetVertex( p[1] ).Coord(); | |
1692 | aPoints[2] = GetVertex( p[2] ).Coord(); | |
1693 | ||
1694 | gp_XY aVEdges[3]; | |
1695 | aVEdges[0] = aPoints[1]; | |
1696 | aVEdges[0].Subtract( aPoints[0] ); | |
1697 | ||
1698 | aVEdges[1] = aPoints[2]; | |
1699 | aVEdges[1].Subtract( aPoints[1] ); | |
2b59653e | 1700 | |
90dc2e5b | 1701 | aVEdges[2] = aPoints[0]; |
1702 | aVEdges[2].Subtract( aPoints[2] ); | |
1703 | ||
1704 | Standard_Real aDistance[3]; | |
1705 | Standard_Real aSqModulus[3]; | |
1706 | ||
1707 | Standard_Real aMinDist; | |
1708 | aMinDist = calculateDist( aVEdges, aPoints, e, theVertex, aDistance, aSqModulus, theEdgeOn ); | |
1709 | if ( aMinDist < 0 ) | |
2b59653e E |
1710 | return Standard_False; |
1711 | ||
90dc2e5b | 1712 | if ( aMinDist > EPSEPS ) |
1713 | { | |
1714 | Standard_Integer anEdgeId = theEdgeOn; | |
1715 | theEdgeOn = 0; | |
1716 | ||
1717 | if ( anEdgeId != 0 ) | |
2b59653e | 1718 | { |
90dc2e5b | 1719 | Standard_Integer i = 0; |
1720 | for ( ; i < 3; ++i ) | |
2b59653e | 1721 | { |
90dc2e5b | 1722 | if( e[i] == anEdgeId ) |
2b59653e E |
1723 | break; |
1724 | } | |
1725 | ||
90dc2e5b | 1726 | if( anEdges[i]->Movability() != BRepMesh_Free ) |
1727 | if ( aDistance[i] < ( aSqModulus[i] / 5. ) ) | |
1728 | theEdgeOn = e[i]; | |
0d88155b O |
1729 | } |
1730 | } | |
1731 | ||
90dc2e5b | 1732 | return ( aDistance[0] + aDistance[1] + aDistance[2] != 0. && |
1733 | ( ( aDistance[0] >= 0. && aDistance[1] >= 0. && aDistance[2] >= 0. ) || | |
1734 | ( aDistance[0] <= 0. && aDistance[1] <= 0. && aDistance[2] <= 0. ) ) ); | |
0d88155b O |
1735 | } |
1736 | ||
90dc2e5b | 1737 | |
1738 | //============================================================================= | |
1739 | // Function: classifyPoint | |
1740 | // This function is used for point classifying in case of coincidence of two | |
1741 | // vectors. | |
1742 | // Returns zero value if point is out of segment and non zero value if point is | |
1743 | // between the first and the second point of segment. | |
1744 | // | |
1745 | // thePoint1 - the start point of a segment (base point) | |
1746 | // thePoint2 - the end point of a segment | |
1747 | // thePointToCheck - the point to classify | |
1748 | //============================================================================= | |
1749 | static Standard_Integer classifyPoint( const gp_XY& thePoint1, | |
1750 | const gp_XY& thePoint2, | |
1751 | const gp_XY& thePointToCheck ) | |
1752 | { | |
1753 | gp_XY aP1 = thePoint2 - thePoint1; | |
1754 | gp_XY aP2 = thePointToCheck - thePoint1; | |
1755 | ||
1756 | Standard_Real aDist = Abs( aP1 ^ aP2 ); | |
1757 | if ( aDist >= Precision::PConfusion() ) | |
1758 | { | |
1759 | aDist = ( aDist * aDist ) / aP1.SquareModulus(); | |
1760 | if ( aDist >= EPSEPS ) | |
1761 | return 0; //out | |
1762 | } | |
1763 | ||
1764 | gp_XY aMult = aP1.Multiplied( aP2 ); | |
1765 | if ( aMult.X() < 0.0 || aMult.Y() < 0.0 ) | |
1766 | return 0; //out | |
1767 | ||
1768 | if ( aP1.SquareModulus() < aP2.SquareModulus() ) | |
1769 | return 0; //out | |
1770 | ||
1771 | if ( thePointToCheck.IsEqual( thePoint1, Precision::PConfusion() ) || | |
1772 | thePointToCheck.IsEqual( thePoint2, Precision::PConfusion() ) ) | |
1773 | return -1; //end point | |
1774 | ||
1775 | return 1; | |
1776 | } | |
1777 | ||
1778 | //============================================================================= | |
1779 | // Function: IntSegSeg | |
1780 | //============================================================================= | |
1781 | Standard_Boolean BRepMesh_Delaun::IntSegSeg( const BRepMesh_Edge& theEdg1, | |
1782 | const BRepMesh_Edge& theEdg2 ) | |
1783 | { | |
1784 | gp_XY p1, p2, p3, p4; | |
1785 | p1 = GetVertex( theEdg1.FirstNode() ).Coord(); | |
1786 | p2 = GetVertex( theEdg1.LastNode() ).Coord(); | |
1787 | p3 = GetVertex( theEdg2.FirstNode() ).Coord(); | |
1788 | p4 = GetVertex( theEdg2.LastNode() ).Coord(); | |
1789 | ||
1790 | Standard_Integer aPoint1 = classifyPoint( p1, p2, p3 ); | |
1791 | Standard_Integer aPoint2 = classifyPoint( p1, p2, p4 ); | |
1792 | Standard_Integer aPoint3 = classifyPoint( p3, p4, p1 ); | |
1793 | Standard_Integer aPoint4 = classifyPoint( p3, p4, p2 ); | |
1794 | ||
1795 | if ( aPoint1 > 0 || aPoint2 > 0 || | |
1796 | aPoint3 > 0 || aPoint4 > 0 ) | |
1797 | return Standard_True; | |
1798 | ||
1799 | gp_XY aPl1 = p2 - p1; | |
1800 | gp_XY aPl2 = p4 - p3; | |
1801 | gp_XY aPl3 = p1 - p3; | |
1802 | ||
1803 | Standard_Real aCrossD1D2 = aPl1 ^ aPl2; | |
1804 | Standard_Real aCrossD1D3 = aPl1 ^ aPl3; | |
1805 | if ( Abs( aCrossD1D2 ) < Precision::PConfusion() ) | |
1806 | { | |
1807 | if( Abs( aCrossD1D3 ) < Precision::PConfusion() ) | |
1808 | { | |
1809 | Standard_Integer aPosHash = aPoint1 + aPoint2; | |
1810 | if ( ( !aPosHash && aPoint3 ) ) //|| aPosHash < -1 ) | |
1811 | return Standard_True; | |
1812 | ||
1813 | return Standard_False; | |
1814 | } | |
1815 | else | |
1816 | //parallel case | |
1817 | return Standard_False; | |
1818 | } | |
1819 | ||
1820 | Standard_Real aPar = aCrossD1D3 / aCrossD1D2; | |
1821 | // inrersects out of first segment range | |
1822 | if( aPar < Precision::Angular() || aPar > 1 - Precision::Angular() ) | |
1823 | return Standard_False; | |
1824 | ||
1825 | Standard_Real aCrossD2D3 = aPl2 ^ aPl3; | |
1826 | aPar = aCrossD2D3 / aCrossD1D2; | |
1827 | // inrersects out of second segment range | |
1828 | if( aPar < Precision::Angular() || aPar > 1 - Precision::Angular() ) | |
1829 | return Standard_False; | |
1830 | ||
1831 | return Standard_True; | |
1832 | } |