0023946: Uninitialized variable aNewEdge3 used
[occt.git] / src / BRepMesh / BRepMesh_Delaun.cxx
CommitLineData
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
44typedef TColStd_ListIteratorOfListOfInteger IteratorOnListOfInteger;
45typedef TColStd_ListOfInteger ListOfInteger;
46
90dc2e5b 47const Standard_Real EPSEPS = Precision::PConfusion() * Precision::PConfusion();
0d88155b
O
48const 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//=======================================================================
55static 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 69BRepMesh_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 86BRepMesh_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//=======================================================================
101BRepMesh_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 124void 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//=======================================================================
145void 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 162void 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 218void 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 245void 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
294//=======================================================================
90dc2e5b 295//function : CreateTriangles
296//purpose : Creates the triangles beetween the node and the polyline.
0d88155b 297//=======================================================================
90dc2e5b 298void 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//=======================================================================
430void 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 531void 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//=======================================================================
622void 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 704void 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//=======================================================================
742void 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 Standard_Boolean isFind = Standard_False;
765 for ( Standard_Integer anIndex = 0; anIndex < 3; ++anIndex )
766 {
767 if ( e[anIndex] == anMainEdgeId && o[anIndex] == anIsForward )
768 {
769 // triangle detected
770 DeleteTriangle( anElemId, theLoopEdges );
771 aGeneralEdgeId = anIndex;
772 break;
0d88155b 773 }
90dc2e5b 774 }
775
776 if ( aGeneralEdgeId != -1 )
777 break;
778 }
0d88155b 779
90dc2e5b 780 if ( aGeneralEdgeId != -1 )
781 {
782 // delete triangles around of aPivotNode starting from the bounding one
783 // define edge connected to vertes
784 Standard_Integer anEdgeId = -1;
785 for ( Standard_Integer i = 0; i < 2; ++i )
786 {
787 Standard_Integer aTmpEdgeId = e[(aGeneralEdgeId + i + 1) % 3];
788 const BRepMesh_Edge& anEdge = GetEdge( aTmpEdgeId );
789 if ( anEdge.FirstNode() == thePivotNode ||
790 anEdge.LastNode() == thePivotNode )
791 {
792 anEdgeId = aTmpEdgeId;
0d88155b 793 }
90dc2e5b 794
795 if ( theInfectedEdges.Contains( aTmpEdgeId ) )
796 theInfectedEdges.Remove( aTmpEdgeId );
797 else
798 theInfectedEdges.Add( aTmpEdgeId );
0d88155b 799 }
90dc2e5b 800
801 if ( isFirstPass )
802 return;
803
804 while ( anEdgeId > 0 )
805 {
806 const BRepMesh_PairOfIndex& aFreePair = myMeshData->ElemConnectedTo( anEdgeId );
807 Standard_Integer anOldEdge = anEdgeId;
808 anEdgeId = -1;
809
810 for ( Standard_Integer aPairIndex = 1; aPairIndex <= aFreePair.Extent(); ++aPairIndex )
811 {
812 Standard_Integer anElemId = aFreePair.Index( aPairIndex );
813 if( anElemId < 0 )
814 continue;
815
816 Standard_Integer e1[3];
817 Standard_Boolean o1[3];
818 GetTriangle( anElemId ).Edges( e1[0], e1[1], e1[2],
819 o1[0], o1[1], o1[2] );
820
821 DeleteTriangle( anElemId, theLoopEdges );
822
823 for ( Standard_Integer i = 0; i < 3; ++i )
824 {
825 if ( e1[i] == anOldEdge )
826 {
2de84aa2 827 for ( Standard_Integer j = 0; j < 2; ++j )
828 {
829 Standard_Integer aTmpEdgeId = e1[(j + i + 1) % 3];
90dc2e5b 830 const BRepMesh_Edge& anEdge = GetEdge( aTmpEdgeId );
831 if ( anEdge.FirstNode() == thePivotNode ||
832 anEdge.LastNode() == thePivotNode )
833 {
834 anEdgeId = aTmpEdgeId;
835 }
836
837 if ( theInfectedEdges.Contains( aTmpEdgeId ) )
838 theInfectedEdges.Remove( aTmpEdgeId );
839 else
840 theInfectedEdges.Add( aTmpEdgeId );
841 }
842 break;
843 }
0d88155b
O
844 }
845 }
0d88155b
O
846 }
847 }
848}
849
850//=======================================================================
90dc2e5b 851//function : CleanupPolygon
852//purpose : Remove internal triangles from the given polygon
0d88155b 853//=======================================================================
90dc2e5b 854void BRepMesh_Delaun::CleanupPolygon( const TColStd_SequenceOfInteger& thePolygon,
855 TColStd_MapOfInteger& theInfectedEdges,
856 BRepMesh_MapOfIntegerInteger& theLoopEdges )
0d88155b 857{
90dc2e5b 858 Standard_Integer aPolyLen = thePolygon.Length();
0d88155b 859
90dc2e5b 860 TColStd_MapOfInteger anIgnoredEdges;
861 NCollection_Map<Standard_Integer> aPolyVertices;
862 for ( Standard_Integer i = 1; i <= aPolyLen; ++i )
863 {
864 Standard_Integer aPolyEdgeId = Abs( thePolygon(i) );
865 anIgnoredEdges.Add( aPolyEdgeId );
0d88155b 866
90dc2e5b 867 const BRepMesh_Edge& aPolyEdge = GetEdge( aPolyEdgeId );
868 aPolyVertices.Add( aPolyEdge.FirstNode() );
869 aPolyVertices.Add( aPolyEdge.LastNode() );
0d88155b 870
90dc2e5b 871 if ( theInfectedEdges.Contains( aPolyEdgeId ) )
872 theInfectedEdges.Remove( aPolyEdgeId );
873 }
0d88155b 874
90dc2e5b 875 Standard_Real aRefTotalAngle = 2 * M_PI;
876 TColStd_MapIteratorOfMapOfInteger anInfectedIt( theInfectedEdges );
877 for ( ; anInfectedIt.More(); anInfectedIt.Next() )
878 {
879 Standard_Integer anEdgeId = anInfectedIt.Key();
880 const BRepMesh_Edge& anInfectedEdge = GetEdge( anEdgeId );
881 Standard_Integer anEdgeVertices[2] = { anInfectedEdge.FirstNode(),
882 anInfectedEdge.LastNode() };
0d88155b 883
90dc2e5b 884 Standard_Boolean isToExclude = Standard_False;
885 for ( Standard_Integer i = 0; i < 2; ++i )
886 {
887 Standard_Integer aCurVertex = anEdgeVertices[i];
888 if ( aPolyVertices.Contains( aCurVertex ) )
889 continue;
0d88155b 890
90dc2e5b 891 gp_XY aCenterPointXY = GetVertex( aCurVertex ).Coord();
892 Standard_Real aTotalAng = 0.0;
893
894 for ( Standard_Integer i = 1; i <= aPolyLen; ++i )
895 {
896 Standard_Integer aPolyEdgeId = thePolygon(i);
897 const BRepMesh_Edge& aPolyEdge = GetEdge( Abs( aPolyEdgeId ) );
898 Standard_Integer aStartPoint, anEndPoint;
899 if ( aPolyEdgeId >= 0 )
900 {
901 aStartPoint = aPolyEdge.FirstNode();
902 anEndPoint = aPolyEdge.LastNode();
0d88155b 903 }
90dc2e5b 904 else
905 {
906 aStartPoint = aPolyEdge.LastNode();
907 anEndPoint = aPolyEdge.FirstNode();
908 }
909
910 gp_XY aStartV = GetVertex( aStartPoint ).Coord() - aCenterPointXY;
911 gp_XY anEndV = GetVertex( anEndPoint ).Coord() - aCenterPointXY;
912
913 Standard_Real anAngle = gp_Vec2d( anEndV ).Angle( gp_Vec2d( aStartV ) );
914 aTotalAng += anAngle;
915 }
916
917 if ( Abs( aRefTotalAngle - aTotalAng ) > Precision::Angular() )
918 isToExclude = Standard_True;
0d88155b 919 }
90dc2e5b 920
921 if ( isToExclude )
922 anIgnoredEdges.Add( anEdgeId );
0d88155b
O
923 }
924
90dc2e5b 925
926 anInfectedIt.Initialize( theInfectedEdges );
927 for ( ; anInfectedIt.More(); anInfectedIt.Next() )
928 {
929 Standard_Integer anEdgeId = anInfectedIt.Key();
930 KillInternalTriangles( anEdgeId, anIgnoredEdges, theLoopEdges);
0d88155b
O
931 }
932
90dc2e5b 933 BRepMesh_MapOfIntegerInteger::Iterator aLoopEdgesIt( theLoopEdges );
934 for ( ; aLoopEdgesIt.More(); aLoopEdgesIt.Next() )
935 {
936 if ( myMeshData->ElemConnectedTo( aLoopEdgesIt.Key() ).IsEmpty() )
937 myMeshData->RemoveLink( aLoopEdgesIt.Key() );
0d88155b
O
938 }
939}
940
941//=======================================================================
90dc2e5b 942//function : MeshLeftPolygonOf
943//purpose : Triangulation of the aPolygonon to the left of <theEdgeIndex>.(material side)
0d88155b 944//=======================================================================
90dc2e5b 945void BRepMesh_Delaun::MeshLeftPolygonOf( const Standard_Integer theEdgeIndex,
946 const Standard_Boolean isForward )
0d88155b 947{
90dc2e5b 948 const BRepMesh_Edge& anEdge = GetEdge( theEdgeIndex );
949 NCollection_Map<Standard_Integer> aDealLinks;
950 TColStd_SequenceOfInteger aPolygon;
951 BRepMesh_MapOfIntegerInteger aLoopEdges( 10, myMeshData->Allocator() );
952 TColStd_MapOfInteger anUsedEdges;
953 TColStd_MapOfInteger anInfectedEdges;
954
955 // Find the aPolygonon
956 anUsedEdges.Add( theEdgeIndex );
957 Standard_Integer aFirstNode, aStartNode, aPivotNode;
958
959 if ( isForward )
960 {
961 aPolygon.Append( theEdgeIndex );
962 aStartNode = anEdge.FirstNode();
963 aPivotNode = anEdge.LastNode();
964 }
965 else
966 {
967 aPolygon.Append( -theEdgeIndex );
968 aStartNode = anEdge.LastNode();
969 aPivotNode = anEdge.FirstNode();
970 }
971 aFirstNode = aStartNode;
0d88155b 972
90dc2e5b 973 const BRepMesh_Vertex& aStartVertex = GetVertex( aFirstNode );
974 const BRepMesh_Vertex& anEndVertex = GetVertex( aPivotNode );
0d88155b 975
90dc2e5b 976 Standard_Integer aRefOtherNode = 0, anOtherNode = 0;
977 // Check the presence of the previous edge <theEdgeIndex> :
978 BRepMesh_ListOfInteger::Iterator aLinkIt( myMeshData->LinkNeighboursOf( aStartNode ) );
979 for ( ; aLinkIt.More(); aLinkIt.Next() )
2b59653e 980 {
90dc2e5b 981 if ( aLinkIt.Value() != theEdgeIndex )
982 {
983 const BRepMesh_Edge& aNextEdge = GetEdge( aLinkIt.Value() );
984 anOtherNode = aNextEdge.LastNode();
985 if ( anOtherNode == aStartNode )
986 anOtherNode = aNextEdge.FirstNode();
987 break;
988 }
989 }
990 if ( anOtherNode == 0 )
991 return;
0d88155b 992
90dc2e5b 993
994 gp_XY aVEdge( anEndVertex.Coord() );
995 aVEdge.Subtract( aStartVertex.Coord() );
996 gp_XY aPrevVEdge( aVEdge );
997 gp_XY aRefCurrVEdge, aCurrVEdge;
998
999 Standard_Integer aCurrEdgeId = theEdgeIndex;
1000 Standard_Integer aNextEdgeId;
1001
1002 // Find the nearest to <theEdgeIndex> closed aPolygonon :
1003 Standard_Boolean isInMesh, isNotInters;
1004 Standard_Real anAngle, aRefAngle;
1005
1006 NCollection_Vector <Bnd_Box2d> aBoxes;
1007 fillBndBox( aBoxes, aStartVertex, anEndVertex );
2b59653e 1008
90dc2e5b 1009 while ( aPivotNode != aFirstNode )
1010 {
1011 aNextEdgeId = 0;
1012 if ( myPositiveOrientation )
1013 aRefAngle = RealFirst();
1014 else
1015 aRefAngle = RealLast();
0d88155b 1016
90dc2e5b 1017 const BRepMesh_Vertex& aPivotVertex = GetVertex( aPivotNode );
1018
1019 // Find the next edge with the greatest angle with <theEdgeIndex>
1020 // and non intersecting <theEdgeIndex> :
1021
1022 aLinkIt.Init( myMeshData->LinkNeighboursOf( aPivotNode ) );
1023 for ( ; aLinkIt.More(); aLinkIt.Next() )
1024 {
1025 Standard_Integer aNextLink = aLinkIt.Value();
1026 Standard_Integer aNextLinkId = Abs( aNextLink );
1027 if ( aDealLinks.Contains( aNextLinkId ) )
1028 continue;
1029
1030 if ( aNextLinkId != aCurrEdgeId )
1031 {
1032 isNotInters = Standard_True;
1033 const BRepMesh_Edge& aNextEdge = GetEdge( aNextLinkId );
1034
1035 isInMesh = Standard_True;
1036
1037 //define if link exist in mesh
1038 if ( aNextEdge.Movability() == BRepMesh_Free )
1039 {
1040 if ( myMeshData->ElemConnectedTo( aLinkIt.Value() ).IsEmpty() )
1041 isInMesh = Standard_False;
2b59653e 1042 }
0d88155b 1043
90dc2e5b 1044 if ( isInMesh )
1045 {
1046 anOtherNode = aNextEdge.FirstNode();
1047 if ( anOtherNode == aPivotNode )
1048 anOtherNode = aNextEdge.LastNode();
1049
1050 aCurrVEdge = GetVertex( anOtherNode ).Coord();
1051 aCurrVEdge.Subtract( aPivotVertex.Coord() );
1052
1053 if ( aCurrVEdge.Modulus() >= gp::Resolution() &&
1054 aPrevVEdge.Modulus() >= gp::Resolution() )
1055 {
1056 anAngle = gp_Vec2d( aPrevVEdge ).Angle( gp_Vec2d( aCurrVEdge ) );
1057
1058 if ( ( myPositiveOrientation && anAngle > aRefAngle ) ||
1059 ( !myPositiveOrientation && anAngle < aRefAngle ) )
1060 {
1061 Bnd_Box2d aBox;
1062 aBox.Add( gp_Pnt2d( GetVertex( aNextEdge.FirstNode() ).Coord() ) );
1063 aBox.Add( gp_Pnt2d( GetVertex( aNextEdge.LastNode() ).Coord() ) );
1064
1065 for ( Standard_Integer k = 0, aLen = aPolygon.Length(); k < aLen; ++k )
1066 {
1067 if ( !aBox.IsOut( aBoxes.Value( k ) ) )
1068 {
1069 // intersection is possible...
1070 if ( IntSegSeg( aNextEdge, GetEdge( Abs( aPolygon( k + 1 ) ) ) ) )
1071 {
1072 isNotInters = Standard_False;
1073 break;
1074 }
1075 }
1076 }
1077
1078 if( isNotInters )
1079 {
1080 aRefAngle = anAngle;
1081 aRefCurrVEdge = aCurrVEdge;
1082
1083 if ( aNextEdge.FirstNode() == aPivotNode )
1084 aNextEdgeId = aLinkIt.Value();
1085 else
1086 aNextEdgeId = -aLinkIt.Value();
1087
1088 aRefOtherNode = anOtherNode;
1089 }
1090 }
2b59653e
E
1091 }
1092 }
0d88155b 1093 }
90dc2e5b 1094 }
1095 if ( aNextEdgeId != 0 )
1096 {
1097 if ( Abs( aNextEdgeId ) != theEdgeIndex && Abs( aNextEdgeId ) != aCurrEdgeId )
1098 {
1099 aCurrEdgeId = Abs( aNextEdgeId );
2b59653e 1100
90dc2e5b 1101 if ( !anUsedEdges.Add( aCurrEdgeId ) )
1102 {
1103 //if this edge has already been added to the aPolygon,
1104 //there is a risk of looping (attention to open contours)
1105 //remove last edge and continue
1106
1107 aDealLinks.Add( aCurrEdgeId );
1108
1109 //roll back
1110 continue;
1111 }
1112
1113 aPolygon.Append( aNextEdgeId );
1114
1115 const BRepMesh_Edge& aCurrEdge = GetEdge( aCurrEdgeId );
1116 Standard_Integer aVert1 = aCurrEdge.FirstNode();
1117 Standard_Integer aVert2 = aCurrEdge.LastNode();
1118 fillBndBox( aBoxes, GetVertex( aVert1 ), GetVertex( aVert2 ) );
1119
1120 RemovePivotTriangles( aNextEdgeId, aPivotNode,
1121 anInfectedEdges, aLoopEdges, (aPolygon.Length() == 2) );
1122 }
0d88155b 1123 }
90dc2e5b 1124 else
1125 {
1126 //hanging end
1127 if ( aPolygon.Length() == 1 )
1128 return;
0d88155b 1129
90dc2e5b 1130 Standard_Integer aDeadEdgeId = Abs( aPolygon.Last() );
1131 const BRepMesh_Edge& aDeadEdge = GetEdge( aDeadEdgeId );
1132
1133 aDealLinks.Add( aDeadEdgeId );
1134
1135 anUsedEdges.Remove( aDeadEdgeId );
1136 aPolygon.Remove( aPolygon.Length() );
1137
1138 // return to previous point
1139 Standard_Integer aLastValidEdge = aPolygon.Last();
1140 const BRepMesh_Edge& aLastEdge = GetEdge( Abs( aLastValidEdge ) );
1141
1142 if( aLastValidEdge > 0 )
1143 {
1144 aStartNode = aLastEdge.FirstNode();
1145 aPivotNode = aLastEdge.LastNode();
1146 }
1147 else
1148 {
1149 aStartNode = aLastEdge.LastNode();
1150 aPivotNode = aLastEdge.FirstNode();
1151 }
1152
1153 const BRepMesh_Vertex& dV = GetVertex( aStartNode );
1154 const BRepMesh_Vertex& fV = GetVertex( aPivotNode );
1155 aPrevVEdge = fV.Coord() - dV.Coord();
1156 continue;
0d88155b 1157 }
90dc2e5b 1158
1159 aStartNode = aPivotNode;
1160 aPivotNode = aRefOtherNode;
1161 aPrevVEdge = aRefCurrVEdge;
2b59653e 1162 }
0d88155b 1163
90dc2e5b 1164 CleanupPolygon( aPolygon, anInfectedEdges, aLoopEdges );
1165 MeshPolygon( aPolygon );
2b59653e 1166}
0d88155b 1167
2b59653e 1168//=======================================================================
90dc2e5b 1169//function : MeshPolygon
1170//purpose : Triangulatiion of a closed aPolygonon described by the list of indexes of
1171// its edges in the structure. (negative index == reversed)
2b59653e 1172//=======================================================================
90dc2e5b 1173void BRepMesh_Delaun::MeshPolygon( TColStd_SequenceOfInteger& thePoly )
2b59653e 1174{
90dc2e5b 1175 Standard_Integer aPivotNode, aVertex3 = 0;
1176 Standard_Integer aFirstNode, aLastNode;
1177 Standard_Integer aTriId;
0d88155b 1178
90dc2e5b 1179 if ( thePoly.Length() == 3 )
1180 {
1181 aTriId = myMeshData->AddElement( BRepMesh_Triangle(
1182 Abs( thePoly(1) ), Abs( thePoly(2) ), Abs( thePoly(3) ),
1183 thePoly(1) > 0, thePoly(2) > 0, thePoly(3) > 0,
1184 BRepMesh_Free ) );
1185
1186 myCircles.MocAdd( aTriId );
1187 const BRepMesh_Edge& anEdge1 = GetEdge( Abs( thePoly(1) ) );
1188 const BRepMesh_Edge& anEdge2 = GetEdge( Abs( thePoly(2) ) );
1189
1190 if ( thePoly(1) > 0)
1191 {
1192 aFirstNode = anEdge1.FirstNode();
1193 aLastNode = anEdge1.LastNode();
1194 }
1195 else
1196 {
1197 aFirstNode = anEdge1.LastNode();
1198 aLastNode = anEdge1.FirstNode();
1199 }
1200
1201 if ( thePoly(2) > 0 )
1202 aVertex3 = anEdge2.LastNode();
1203 else
1204 aVertex3 = anEdge2.FirstNode();
0d88155b 1205
90dc2e5b 1206 Standard_Boolean isAdded = myCircles.Add( GetVertex( aFirstNode ).Coord(),
1207 GetVertex( aLastNode ).Coord(), GetVertex( aVertex3 ).Coord(), aTriId );
1208
1209 if ( !isAdded )
1210 myMeshData->RemoveElement( aTriId );
1211 }
1212 else if ( thePoly.Length() > 3 )
2b59653e 1213 {
90dc2e5b 1214 NCollection_Vector <Bnd_Box2d> aBoxes;
1215 Standard_Integer aPolyIdx, aUsedIdx = 0;
1216 Standard_Integer aPolyLen = thePoly.Length();
1217
1218 for ( aPolyIdx = 1; aPolyIdx <= aPolyLen; ++aPolyIdx )
1219 {
1220 const BRepMesh_Edge& anEdge = GetEdge( Abs( thePoly( aPolyIdx ) ) );
1221 aFirstNode = anEdge.FirstNode();
1222 aLastNode = anEdge.LastNode();
1223 fillBndBox( aBoxes, GetVertex( aFirstNode ), GetVertex( aLastNode ) );
1224 }
1225
1226 const BRepMesh_Edge& anEdge = GetEdge( Abs( thePoly(1) ) );
1227 Standard_Real aMinDist = RealLast();
1228
1229 if ( thePoly(1) > 0 )
1230 {
1231 aFirstNode = anEdge.FirstNode();
1232 aLastNode = anEdge.LastNode();
1233 }
1234 else
2b59653e 1235 {
90dc2e5b 1236 aFirstNode = anEdge.LastNode();
1237 aLastNode = anEdge.FirstNode();
1238 }
1239
1240 gp_XY aVEdge( GetVertex( aLastNode ).Coord() -
1241 GetVertex( aFirstNode ).Coord() );
1242
1243 Standard_Real aVEdgeLen = aVEdge.Modulus();
1244 if ( aVEdgeLen > 0.)
1245 {
1246 aVEdge.SetCoord( aVEdge.X() / aVEdgeLen,
1247 aVEdge.Y() / aVEdgeLen );
1248
1249 for ( aPolyIdx = 3; aPolyIdx <= aPolyLen; ++aPolyIdx )
1250 {
1251 const BRepMesh_Edge& aNextEdge = GetEdge( Abs( thePoly( aPolyIdx ) ) );
1252 if ( thePoly( aPolyIdx ) > 0)
1253 aPivotNode = aNextEdge.FirstNode();
1254 else
1255 aPivotNode = aNextEdge.LastNode();
1256
1257 gp_XY aVEdgePivot( GetVertex( aPivotNode ).Coord() -
1258 GetVertex( aLastNode ).Coord() );
1259
1260 Standard_Real aDist = aVEdge ^ aVEdgePivot;
1261 if ( Abs( aDist ) > Precision::PConfusion() )
1262 {
1263 if ( ( aDist > 0. && myPositiveOrientation ) ||
1264 ( aDist < 0. && !myPositiveOrientation ) )
1265 {
1266 if ( Abs( aDist ) < aMinDist )
1267 {
1268 Bnd_Box2d aBoxFirst, aBoxLast;
1269 aBoxFirst.Add( gp_Pnt2d( GetVertex( aPivotNode ).Coord() ) );
1270 aBoxFirst.Add( gp_Pnt2d( GetVertex( aLastNode ).Coord() ) );
1271
1272 aBoxLast.Add( gp_Pnt2d( GetVertex( aPivotNode ).Coord() ) );
1273 aBoxLast.Add( gp_Pnt2d( GetVertex( aFirstNode ).Coord() ) );
1274
1275 BRepMesh_Edge aCheckE1( aLastNode, aPivotNode, BRepMesh_Free );
1276 BRepMesh_Edge aCheckE2( aFirstNode, aPivotNode, BRepMesh_Free );
1277
1278 Standard_Boolean isIntersect = Standard_False;
1279 for ( Standard_Integer aPolyIdx1 = 2; aPolyIdx1 <= aPolyLen; ++aPolyIdx1 )
1280 {
1281 if( aPolyIdx1 == aPolyIdx )
1282 continue;
1283
1284 const BRepMesh_Edge& aNextEdge1 = GetEdge( Abs( thePoly( aPolyIdx1 ) ) );
1285 if ( !aBoxFirst.IsOut( aBoxes.Value( aPolyIdx1 - 1 ) ) )
1286 {
1287 // intersection is possible...
1288 if( IntSegSeg( aCheckE1, aNextEdge1 ) )
1289 {
1290 isIntersect = Standard_True;
1291 break;
1292 }
1293 }
1294
1295 if ( !aBoxLast.IsOut( aBoxes.Value( aPolyIdx1 - 1 ) ) &&
1296 !aCheckE2.IsEqual( aNextEdge1 ) )
1297 {
1298 // intersection is possible...
1299 if( IntSegSeg( aCheckE2, aNextEdge1 ) )
1300 {
1301 isIntersect = Standard_True;
1302 break;
1303 }
1304 }
1305 }
1306
1307 if( !isIntersect )
1308 {
1309 aMinDist = aDist;
1310 aVertex3 = aPivotNode;
1311 aUsedIdx = aPolyIdx;
1312 }
1313 }
1314 }
1315 }
1316 }
1317 }
1318
1319 Standard_Integer aNewEdge2, aNewEdge3;
1320 if ( aMinDist < RealLast() )
1321 {
1322 aNewEdge2 = myMeshData->AddLink( BRepMesh_Edge( aLastNode, aVertex3, BRepMesh_Free ) );
1323 aNewEdge3 = myMeshData->AddLink( BRepMesh_Edge( aVertex3, aFirstNode, BRepMesh_Free ) );
1324 aTriId = myMeshData->AddElement( BRepMesh_Triangle(
1325 Abs( thePoly(1) ), Abs( aNewEdge2 ), Abs( aNewEdge3 ),
1326 thePoly(1) > 0, aNewEdge2 > 0, aNewEdge3 > 0,
1327 BRepMesh_Free ) );
1328
1329 Standard_Boolean isAdded = myCircles.Add( GetVertex( aFirstNode ).Coord(),
1330 GetVertex( aLastNode ).Coord(), GetVertex( aVertex3 ).Coord(), aTriId );
1331
1332 if ( !isAdded )
1333 myMeshData->RemoveElement( aTriId );
1334
1335 if ( aUsedIdx < aPolyLen )
1336 {
1337 TColStd_SequenceOfInteger aSuitePoly;
1338 thePoly.Split( aUsedIdx, aSuitePoly );
1339 aSuitePoly.Prepend( -aNewEdge3 );
1340 MeshPolygon( aSuitePoly );
1341 }
1342 else
1343 thePoly.Remove( aPolyLen );
1344
1345 if ( aUsedIdx > 3 )
1346 {
1347 thePoly.SetValue( 1, -aNewEdge2 );
1348 MeshPolygon( thePoly );
1349 }
2b59653e 1350 }
0d88155b 1351 }
0d88155b
O
1352}
1353
1354//=======================================================================
1355//function : RemoveVertex
90dc2e5b 1356//purpose : Removes a vertex from the triangulation
0d88155b 1357//=======================================================================
90dc2e5b 1358void BRepMesh_Delaun::RemoveVertex( const BRepMesh_Vertex& theVertex )
0d88155b 1359{
90dc2e5b 1360 BRepMesh_SelectorOfDataStructureOfDelaun aSelector( myMeshData );
1361 aSelector.NeighboursOf( theVertex );
0d88155b 1362
90dc2e5b 1363 BRepMesh_MapOfIntegerInteger aLoopEdges( 10, myMeshData->Allocator() );
0d88155b
O
1364
1365 // Loop on triangles to be destroyed :
90dc2e5b 1366 BRepMesh_MapOfInteger::Iterator aTriangleIt( aSelector.Elements() );
1367 for ( ; aTriangleIt.More(); aTriangleIt.Next() )
1368 DeleteTriangle( aTriangleIt.Key(), aLoopEdges );
0d88155b 1369
90dc2e5b 1370 TColStd_SequenceOfInteger aPolygon;
1371 Standard_Integer aLoopEdgesCount = aLoopEdges.Extent();
1372 BRepMesh_MapOfIntegerInteger::Iterator aLoopEdgesIt( aLoopEdges );
1373
1374 if ( aLoopEdgesIt.More() )
1375 {
1376 const BRepMesh_Edge& anEdge = GetEdge( aLoopEdgesIt.Key() );
1377 Standard_Integer aFirstNode = anEdge.FirstNode();
1378 Standard_Integer aLastNode;
1379 Standard_Integer aPivotNode = anEdge.LastNode();
1380 Standard_Integer anEdgeId = aLoopEdgesIt.Key();
1381
1382 Standard_Boolean isPositive = (Standard_Boolean)aLoopEdges( anEdgeId );
1383 if ( !isPositive )
1384 {
1385 Standard_Integer aTmp;
1386 aTmp = aFirstNode;
1387 aFirstNode = aPivotNode;
1388 aPivotNode = aTmp;
1389
1390 aPolygon.Append( -anEdgeId );
0d88155b 1391 }
90dc2e5b 1392 else
1393 aPolygon.Append( anEdgeId );
1394
1395 aLoopEdges.UnBind( anEdgeId );
1396
1397 aLastNode = aFirstNode;
1398 while ( aPivotNode != aLastNode )
1399 {
1400 BRepMesh_ListOfInteger::Iterator aLinkIt( myMeshData->LinkNeighboursOf( aPivotNode ) );
1401 for ( ; aLinkIt.More(); aLinkIt.Next() )
1402 {
1403 if ( aLinkIt.Value() != anEdgeId &&
1404 aLoopEdges.IsBound( aLinkIt.Value() ) )
1405 {
1406 Standard_Integer aCurrentNode;
1407 anEdgeId = aLinkIt.Value();
1408 const BRepMesh_Edge& anEdge1 = GetEdge( anEdgeId );
1409
1410 aCurrentNode = anEdge1.LastNode();
1411 if ( aCurrentNode != aPivotNode )
1412 {
1413 aCurrentNode = anEdge1.FirstNode();
1414 aPolygon.Append( -anEdgeId );
0d88155b
O
1415 }
1416 else
90dc2e5b 1417 aPolygon.Append( anEdgeId );
1418
1419 aPivotNode = aCurrentNode;
1420 aLoopEdges.UnBind( anEdgeId );
0d88155b
O
1421 break;
1422 }
1423 }
90dc2e5b 1424
1425 if ( aLoopEdgesCount <= 0 )
1426 break;
1427 --aLoopEdgesCount;
0d88155b 1428 }
90dc2e5b 1429
1430 MeshPolygon( aPolygon );
0d88155b
O
1431 }
1432}
1433
1434
1435//=======================================================================
1436//function : AddVertices
90dc2e5b 1437//purpose : Adds some vertices in the triangulation.
0d88155b 1438//=======================================================================
90dc2e5b 1439void BRepMesh_Delaun::AddVertices( BRepMesh_Array1OfVertexOfDelaun& theVertices )
0d88155b 1440{
90dc2e5b 1441 BRepMesh_HeapSortVertexOfDelaun::Sort( theVertices,
1442 BRepMesh_ComparatorOfVertexOfDelaun( SortingDirection, Precision::PConfusion() ) );
0d88155b 1443
90dc2e5b 1444 Standard_Integer aLower = theVertices.Lower();
1445 Standard_Integer anUpper = theVertices.Upper();
2b59653e 1446
90dc2e5b 1447 TColStd_Array1OfInteger aVertexIndexes( aLower, anUpper );
1448 for ( Standard_Integer i = aLower; i <= anUpper; ++i )
1449 aVertexIndexes(i) = myMeshData->AddNode( theVertices(i) );
0d88155b 1450
90dc2e5b 1451 CreateTrianglesOnNewVertices( aVertexIndexes );
0d88155b
O
1452}
1453
1454//=======================================================================
1455//function : UseEdge
90dc2e5b 1456//purpose : Modify mesh to use the edge. Return True if done
0d88155b 1457//=======================================================================
90dc2e5b 1458Standard_Boolean BRepMesh_Delaun::UseEdge( const Standard_Integer theIndex )
0d88155b 1459{
90dc2e5b 1460 /*
1461 const BRepMesh_PairOfIndex& aPair = myMeshData->ElemConnectedTo( theIndex );
1462 if ( aPair.Extent() == 0 )
1463 {
1464 const BRepMesh_Edge& anEdge = GetEdge( theIndex );
1465
1466 Standard_Integer aStartNode, aPivotNode, anOtherNode;
1467 aStartNode = anEdge.FirstNode();
1468 aPivotNode = anEdge.LastNode();
1469
1470 const BRepMesh_ListOfInteger& aStartNodeNeighbors = myMeshData->LinkNeighboursOf( aStartNode );
1471 const BRepMesh_ListOfInteger& aPivotNodeNeighbors = myMeshData->LinkNeighboursOf( aPivotNode );
1472
1473 if ( aStartNodeNeighbors.Extent() > 0 &&
1474 aPivotNodeNeighbors.Extent() > 0 )
1475 {
1476 const BRepMesh_Vertex& aStartVertex = GetVertex( aStartNode );
1477 const BRepMesh_Vertex& aPivotVertex = GetVertex( aPivotNode );
1478
1479 gp_XY aVEdge ( aPivotVertex.Coord() );
1480 aVEdge.Subtract( aStartVertex.Coord() );
1481
1482 Standard_Real anAngle = 0.;
1483 Standard_Real anAngleMin = RealLast();
1484 Standard_Real anAngleMax = RealFirst();
1485 Standard_Integer aLeftEdge = 0, aRightEdge = 0;
1486
1487 BRepMesh_ListOfInteger::Iterator aNeighborIt( aPivotNodeNeighbors );
1488 for ( ; aNeighborIt.More(); aNeighborIt.Next() )
1489 {
1490 Standard_Integer anEdgeId = aNeighborIt.Value();
1491 if ( anEdgeId != theIndex )
1492 {
1493 const BRepMesh_Edge& aNextEdge = GetEdge( anEdgeId );
1494
1495 Standard_Boolean isInMesh = Standard_True;
1496 if ( aNextEdge.Movability() == BRepMesh_Free )
1497 {
1498 if ( myMeshData->ElemConnectedTo( anEdgeId ).IsEmpty() )
1499 isInMesh = Standard_False;
0d88155b
O
1500 }
1501
90dc2e5b 1502 if ( isInMesh )
1503 {
1504 anOtherNode = aNextEdge.FirstNode();
1505 if ( anOtherNode == aPivotNode )
1506 anOtherNode = aNextEdge.LastNode();
0d88155b 1507
90dc2e5b 1508 gp_XY aVEdgeCur = GetVertex( anOtherNode ).Coord();
1509 aVEdgeCur.Subtract( aPivotVertex.Coord() );
0d88155b 1510
90dc2e5b 1511 anAngle = gp_Vec2d( aVEdge ).Angle( gp_Vec2d( aVEdgeCur ) );
0d88155b 1512 }
90dc2e5b 1513
1514 if ( anAngle > anAngleMax )
1515 {
1516 anAngleMax = anAngle;
1517 aLeftEdge = anEdgeId;
0d88155b 1518 }
90dc2e5b 1519 if ( anAngle < anAngleMin )
1520 {
1521 anAngleMin = anAngle;
1522 aRightEdge = anEdgeId;
0d88155b
O
1523 }
1524 }
1525 }
90dc2e5b 1526
1527 if ( aLeftEdge > 0 )
1528 {
1529 if (aLeftEdge==aRightEdge)
1530 {
0d88155b 1531 }
90dc2e5b 1532 else
1533 {
0d88155b
O
1534 }
1535 }
1536 }
1537 }
90dc2e5b 1538 */
0d88155b
O
1539 return Standard_False;
1540}
1541
1542//=======================================================================
0d88155b 1543//function : Result
90dc2e5b 1544//purpose : Gives the Mesh data structure
0d88155b 1545//=======================================================================
90dc2e5b 1546const Handle( BRepMesh_DataStructureOfDelaun )& BRepMesh_Delaun::Result() const
0d88155b 1547{
90dc2e5b 1548 return myMeshData;
0d88155b
O
1549}
1550
1551//=======================================================================
1552//function : Frontier
90dc2e5b 1553//purpose : Gives the list of frontier edges
0d88155b 1554//=======================================================================
90dc2e5b 1555const BRepMesh_MapOfInteger& BRepMesh_Delaun::Frontier()
0d88155b 1556{
90dc2e5b 1557 BRepMesh_MapOfInteger::Iterator anEdgeIt( myMeshData->LinkOfDomain() );
0d88155b 1558
90dc2e5b 1559 myMapEdges.Clear();
1560 for ( ; anEdgeIt.More(); anEdgeIt.Next() )
1561 {
1562 Standard_Integer anEdge = anEdgeIt.Key();
1563 if ( GetEdge( anEdge ).Movability() == BRepMesh_Frontier )
1564 myMapEdges.Add( anEdge );
0d88155b 1565 }
90dc2e5b 1566
1567 return myMapEdges;
0d88155b
O
1568}
1569
1570//=======================================================================
1571//function : InternalEdges
90dc2e5b 1572//purpose : Gives the list of internal edges
0d88155b 1573//=======================================================================
90dc2e5b 1574const BRepMesh_MapOfInteger& BRepMesh_Delaun::InternalEdges()
0d88155b 1575{
90dc2e5b 1576 BRepMesh_MapOfInteger::Iterator anEdgeIt( myMeshData->LinkOfDomain() );
0d88155b 1577
90dc2e5b 1578 myMapEdges.Clear();
1579 for ( ; anEdgeIt.More(); anEdgeIt.Next() )
1580 {
1581 Standard_Integer anEdge = anEdgeIt.Key();
1582 if ( GetEdge( anEdge ).Movability() == BRepMesh_Fixed )
1583 myMapEdges.Add( anEdge );
0d88155b 1584 }
90dc2e5b 1585
1586 return myMapEdges;
0d88155b
O
1587}
1588
1589//=======================================================================
1590//function : FreeEdges
90dc2e5b 1591//purpose : Gives the list of free edges used only one time
0d88155b 1592//=======================================================================
90dc2e5b 1593const BRepMesh_MapOfInteger& BRepMesh_Delaun::FreeEdges()
0d88155b 1594{
90dc2e5b 1595 BRepMesh_MapOfInteger::Iterator anEdgeIt( myMeshData->LinkOfDomain() );
0d88155b 1596
90dc2e5b 1597 myMapEdges.Clear();
1598 for ( ; anEdgeIt.More(); anEdgeIt.Next() )
1599 {
1600 Standard_Integer anEdge = anEdgeIt.Key();
1601 if ( myMeshData->ElemConnectedTo( anEdge ).Extent() <= 1 )
1602 myMapEdges.Add( anEdge );
0d88155b 1603 }
90dc2e5b 1604
1605 return myMapEdges;
0d88155b
O
1606}
1607
0d88155b 1608//=======================================================================
90dc2e5b 1609//function : calculateDist
1610//purpose : Calculates distances between the given point and edges of
1611// triangle
0d88155b 1612//=======================================================================
90dc2e5b 1613static Standard_Real calculateDist( const gp_XY theVEdges[3],
1614 const gp_XY thePoints[3],
1615 const Standard_Integer theEdgesId[3],
1616 const BRepMesh_Vertex& theVertex,
1617 Standard_Real theDistance[3],
1618 Standard_Real theSqModulus[3],
1619 Standard_Integer& theEdgeOn )
2b59653e 1620{
90dc2e5b 1621 Standard_Real aMinDist = -1;
1622 if ( !theVEdges || !thePoints || !theEdgesId ||
1623 !theDistance || !theSqModulus )
1624 return aMinDist;
1625
1626 for( Standard_Integer i = 0; i < 3; ++i )
2b59653e 1627 {
90dc2e5b 1628 theSqModulus[i] = theVEdges[i].SquareModulus();
1629 if ( theSqModulus[i] <= EPSEPS )
1630 return -1;
1631
1632 theDistance[i] = theVEdges[i] ^ ( theVertex.Coord() - thePoints[i] );
1633
1634 Standard_Real aDist = theDistance[i] * theDistance[i];
1635 aDist /= theSqModulus[i];
2b59653e 1636
90dc2e5b 1637 if ( aMinDist < 0 || aDist < aMinDist )
2b59653e 1638 {
90dc2e5b 1639 theEdgeOn = theEdgesId[i];
1640 aMinDist = aDist;
2b59653e
E
1641 }
1642 }
90dc2e5b 1643
1644 return aMinDist;
2b59653e
E
1645}
1646
90dc2e5b 1647//=======================================================================
1648//function : Contains
1649//purpose : Test if triangle of index <TrianIndex> contains geometricaly
1650// <theVertex>. If <theEdgeOn> is != 0 then theVertex is on Edge
1651// of index <theEdgeOn>
1652//=======================================================================
1653Standard_Boolean BRepMesh_Delaun::Contains( const Standard_Integer theTriangleId,
1654 const BRepMesh_Vertex& theVertex,
1655 Standard_Integer& theEdgeOn ) const
0d88155b 1656{
90dc2e5b 1657 theEdgeOn = 0;
1658
1659 Standard_Integer e[3];
1660 Standard_Boolean o[3];
1661 Standard_Integer p[3];
1662
1663 GetTriangle( theTriangleId ).Edges( e[0], e[1], e[2],
1664 o[0], o[1], o[2] );
1665
1666 const BRepMesh_Edge* anEdges[3] = { &GetEdge( e[0] ),
1667 &GetEdge( e[1] ),
1668 &GetEdge( e[2] ) };
1669 if ( o[0] )
1670 {
1671 p[0] = anEdges[0]->FirstNode();
1672 p[1] = anEdges[0]->LastNode();
0d88155b 1673 }
90dc2e5b 1674 else
1675 {
1676 p[1] = anEdges[0]->FirstNode();
1677 p[0] = anEdges[0]->LastNode();
0d88155b 1678 }
2b59653e 1679
90dc2e5b 1680 if ( o[2] )
1681 p[2] = anEdges[2]->FirstNode();
1682 else
1683 p[2] = anEdges[2]->LastNode();
1684
1685 gp_XY aPoints[3];
1686 aPoints[0] = GetVertex( p[0] ).Coord();
1687 aPoints[1] = GetVertex( p[1] ).Coord();
1688 aPoints[2] = GetVertex( p[2] ).Coord();
1689
1690 gp_XY aVEdges[3];
1691 aVEdges[0] = aPoints[1];
1692 aVEdges[0].Subtract( aPoints[0] );
1693
1694 aVEdges[1] = aPoints[2];
1695 aVEdges[1].Subtract( aPoints[1] );
2b59653e 1696
90dc2e5b 1697 aVEdges[2] = aPoints[0];
1698 aVEdges[2].Subtract( aPoints[2] );
1699
1700 Standard_Real aDistance[3];
1701 Standard_Real aSqModulus[3];
1702
1703 Standard_Real aMinDist;
1704 aMinDist = calculateDist( aVEdges, aPoints, e, theVertex, aDistance, aSqModulus, theEdgeOn );
1705 if ( aMinDist < 0 )
2b59653e
E
1706 return Standard_False;
1707
90dc2e5b 1708 if ( aMinDist > EPSEPS )
1709 {
1710 Standard_Integer anEdgeId = theEdgeOn;
1711 theEdgeOn = 0;
1712
1713 if ( anEdgeId != 0 )
2b59653e 1714 {
90dc2e5b 1715 Standard_Integer i = 0;
1716 for ( ; i < 3; ++i )
2b59653e 1717 {
90dc2e5b 1718 if( e[i] == anEdgeId )
2b59653e
E
1719 break;
1720 }
1721
90dc2e5b 1722 if( anEdges[i]->Movability() != BRepMesh_Free )
1723 if ( aDistance[i] < ( aSqModulus[i] / 5. ) )
1724 theEdgeOn = e[i];
0d88155b
O
1725 }
1726 }
1727
90dc2e5b 1728 return ( aDistance[0] + aDistance[1] + aDistance[2] != 0. &&
1729 ( ( aDistance[0] >= 0. && aDistance[1] >= 0. && aDistance[2] >= 0. ) ||
1730 ( aDistance[0] <= 0. && aDistance[1] <= 0. && aDistance[2] <= 0. ) ) );
0d88155b
O
1731}
1732
90dc2e5b 1733
1734//=============================================================================
1735// Function: classifyPoint
1736// This function is used for point classifying in case of coincidence of two
1737// vectors.
1738// Returns zero value if point is out of segment and non zero value if point is
1739// between the first and the second point of segment.
1740//
1741// thePoint1 - the start point of a segment (base point)
1742// thePoint2 - the end point of a segment
1743// thePointToCheck - the point to classify
1744//=============================================================================
1745static Standard_Integer classifyPoint( const gp_XY& thePoint1,
1746 const gp_XY& thePoint2,
1747 const gp_XY& thePointToCheck )
1748{
1749 gp_XY aP1 = thePoint2 - thePoint1;
1750 gp_XY aP2 = thePointToCheck - thePoint1;
1751
1752 Standard_Real aDist = Abs( aP1 ^ aP2 );
1753 if ( aDist >= Precision::PConfusion() )
1754 {
1755 aDist = ( aDist * aDist ) / aP1.SquareModulus();
1756 if ( aDist >= EPSEPS )
1757 return 0; //out
1758 }
1759
1760 gp_XY aMult = aP1.Multiplied( aP2 );
1761 if ( aMult.X() < 0.0 || aMult.Y() < 0.0 )
1762 return 0; //out
1763
1764 if ( aP1.SquareModulus() < aP2.SquareModulus() )
1765 return 0; //out
1766
1767 if ( thePointToCheck.IsEqual( thePoint1, Precision::PConfusion() ) ||
1768 thePointToCheck.IsEqual( thePoint2, Precision::PConfusion() ) )
1769 return -1; //end point
1770
1771 return 1;
1772}
1773
1774//=============================================================================
1775// Function: IntSegSeg
1776//=============================================================================
1777Standard_Boolean BRepMesh_Delaun::IntSegSeg( const BRepMesh_Edge& theEdg1,
1778 const BRepMesh_Edge& theEdg2 )
1779{
1780 gp_XY p1, p2, p3, p4;
1781 p1 = GetVertex( theEdg1.FirstNode() ).Coord();
1782 p2 = GetVertex( theEdg1.LastNode() ).Coord();
1783 p3 = GetVertex( theEdg2.FirstNode() ).Coord();
1784 p4 = GetVertex( theEdg2.LastNode() ).Coord();
1785
1786 Standard_Integer aPoint1 = classifyPoint( p1, p2, p3 );
1787 Standard_Integer aPoint2 = classifyPoint( p1, p2, p4 );
1788 Standard_Integer aPoint3 = classifyPoint( p3, p4, p1 );
1789 Standard_Integer aPoint4 = classifyPoint( p3, p4, p2 );
1790
1791 if ( aPoint1 > 0 || aPoint2 > 0 ||
1792 aPoint3 > 0 || aPoint4 > 0 )
1793 return Standard_True;
1794
1795 gp_XY aPl1 = p2 - p1;
1796 gp_XY aPl2 = p4 - p3;
1797 gp_XY aPl3 = p1 - p3;
1798
1799 Standard_Real aCrossD1D2 = aPl1 ^ aPl2;
1800 Standard_Real aCrossD1D3 = aPl1 ^ aPl3;
1801 if ( Abs( aCrossD1D2 ) < Precision::PConfusion() )
1802 {
1803 if( Abs( aCrossD1D3 ) < Precision::PConfusion() )
1804 {
1805 Standard_Integer aPosHash = aPoint1 + aPoint2;
1806 if ( ( !aPosHash && aPoint3 ) ) //|| aPosHash < -1 )
1807 return Standard_True;
1808
1809 return Standard_False;
1810 }
1811 else
1812 //parallel case
1813 return Standard_False;
1814 }
1815
1816 Standard_Real aPar = aCrossD1D3 / aCrossD1D2;
1817 // inrersects out of first segment range
1818 if( aPar < Precision::Angular() || aPar > 1 - Precision::Angular() )
1819 return Standard_False;
1820
1821 Standard_Real aCrossD2D3 = aPl2 ^ aPl3;
1822 aPar = aCrossD2D3 / aCrossD1D2;
1823 // inrersects out of second segment range
1824 if( aPar < Precision::Angular() || aPar > 1 - Precision::Angular() )
1825 return Standard_False;
1826
1827 return Standard_True;
1828}