1 // Created on: 1993-05-12
2 // Created by: Didier PIFFAULT
3 // Copyright (c) 1993-1999 Matra Datavision
4 // Copyright (c) 1999-2014 OPEN CASCADE SAS
6 // This file is part of Open CASCADE Technology software library.
8 // This library is free software; you can redistribute it and/or modify it under
9 // the terms of the GNU Lesser General Public License version 2.1 as published
10 // by the Free Software Foundation, with special exception defined in the file
11 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
12 // distribution for complete text of the license and disclaimer of any warranty.
14 // Alternatively, this file may be used under the terms of Open CASCADE
15 // commercial license or contractual agreement.
17 #include <BRepMesh_Delaun.hxx>
21 #include <gp_Pnt2d.hxx>
22 #include <gp_Vec2d.hxx>
24 #include <Precision.hxx>
25 #include <Bnd_Box2d.hxx>
26 #include <Bnd_B2d.hxx>
28 #include <TColStd_MapOfInteger.hxx>
29 #include <TColStd_MapIteratorOfMapOfInteger.hxx>
30 #include <TColStd_Array1OfBoolean.hxx>
31 #include <TColStd_ListIteratorOfListOfInteger.hxx>
32 #include <TColStd_ListOfInteger.hxx>
33 #include <TColStd_Array1OfReal.hxx>
34 #include <TColStd_Array1OfInteger.hxx>
35 #include <TColStd_SequenceOfInteger.hxx>
37 #include <BRepMesh_MapOfIntegerInteger.hxx>
38 #include <BRepMesh_HeapSortIndexedVertexOfDelaun.hxx>
39 #include <BRepMesh_ComparatorOfIndexedVertexOfDelaun.hxx>
40 #include <BRepMesh_HeapSortIndexedVertexOfDelaun.hxx>
41 #include <BRepMesh_SelectorOfDataStructureOfDelaun.hxx>
42 #include <BRepMesh_HeapSortVertexOfDelaun.hxx>
43 #include <BRepMesh_ComparatorOfVertexOfDelaun.hxx>
44 #include <BRepMesh_Array1OfVertexOfDelaun.hxx>
46 #include <BRepMesh_Edge.hxx>
47 #include <BRepMesh_Vertex.hxx>
48 #include <BRepMesh_Triangle.hxx>
50 #include <NCollection_Vector.hxx>
52 typedef TColStd_ListIteratorOfListOfInteger IteratorOnListOfInteger;
53 typedef TColStd_ListOfInteger ListOfInteger;
55 const Standard_Real AngDeviation1Deg = M_PI/180.;
56 const Standard_Real AngDeviation90Deg = 90 * AngDeviation1Deg;
57 const Standard_Real Angle2PI = 2 * M_PI;
59 const Standard_Real Precision = Precision::PConfusion();
60 const Standard_Real Precision2 = Precision * Precision;
61 const gp_XY SortingDirection(M_SQRT1_2, M_SQRT1_2);
63 //=======================================================================
64 //function : BRepMesh_Delaun
65 //purpose : Creates the triangulation with an empty Mesh data structure
66 //=======================================================================
67 BRepMesh_Delaun::BRepMesh_Delaun( BRepMesh_Array1OfVertexOfDelaun& theVertices,
68 const Standard_Boolean isPositive )
69 : myIsPositiveOrientation( isPositive ),
70 myCircles( theVertices.Length(), new NCollection_IncAllocator() )
72 if ( theVertices.Length() > 2 )
74 myMeshData = new BRepMesh_DataStructureOfDelaun( new NCollection_IncAllocator(),
75 theVertices.Length() );
80 //=======================================================================
81 //function : BRepMesh_Delaun
82 //purpose : Creates the triangulation with and existent Mesh data structure
83 //=======================================================================
84 BRepMesh_Delaun::BRepMesh_Delaun( const Handle( BRepMesh_DataStructureOfDelaun )& theOldMesh,
85 BRepMesh_Array1OfVertexOfDelaun& theVertices,
86 const Standard_Boolean isPositive )
87 : myIsPositiveOrientation( isPositive ),
88 myCircles( theVertices.Length(), theOldMesh->Allocator() )
90 myMeshData = theOldMesh;
91 if ( theVertices.Length() > 2 )
95 //=======================================================================
96 //function : BRepMesh_Delaun
97 //purpose : Creates the triangulation with and existent Mesh data structure
98 //=======================================================================
99 BRepMesh_Delaun::BRepMesh_Delaun( const Handle( BRepMesh_DataStructureOfDelaun )& theOldMesh,
100 TColStd_Array1OfInteger& theVertexIndices,
101 const Standard_Boolean isPositive )
102 : myIsPositiveOrientation( isPositive ),
103 myCircles( theVertexIndices.Length(), theOldMesh->Allocator() )
105 myMeshData = theOldMesh;
106 if ( theVertexIndices.Length() > 2 )
109 Standard_Integer anIndex = theVertexIndices.Lower();
110 Standard_Integer anUpper = theVertexIndices.Upper();
111 for ( ; anIndex <= anUpper; ++anIndex )
112 aBox.Add( gp_Pnt2d( GetVertex( theVertexIndices( anIndex) ).Coord() ) );
114 perform( aBox, theVertexIndices );
118 //=======================================================================
120 //purpose : Initializes the triangulation with an Array of Vertex
121 //=======================================================================
122 void BRepMesh_Delaun::Init( BRepMesh_Array1OfVertexOfDelaun& theVertices )
125 Standard_Integer aLowerIdx = theVertices.Lower();
126 Standard_Integer anUpperIdx = theVertices.Upper();
127 TColStd_Array1OfInteger aVertexIndexes( aLowerIdx, anUpperIdx );
129 Standard_Integer anIndex = aLowerIdx;
130 for ( ; anIndex <= anUpperIdx; ++anIndex )
132 aBox.Add( gp_Pnt2d( theVertices( anIndex ).Coord() ) );
133 aVertexIndexes( anIndex ) = myMeshData->AddNode( theVertices( anIndex ) );
136 perform( aBox, aVertexIndexes );
139 //=======================================================================
141 //purpose : Create super mesh and run triangulation procedure
142 //=======================================================================
143 void BRepMesh_Delaun::perform( Bnd_Box2d& theBndBox,
144 TColStd_Array1OfInteger& theVertexIndexes )
146 theBndBox.Enlarge( Precision );
147 superMesh( theBndBox );
149 BRepMesh_HeapSortIndexedVertexOfDelaun::Sort( theVertexIndexes,
150 BRepMesh_ComparatorOfIndexedVertexOfDelaun( SortingDirection,
151 Precision, myMeshData ) );
153 compute( theVertexIndexes );
156 //=======================================================================
157 //function : superMesh
158 //purpose : Build the super mesh
159 //=======================================================================
160 void BRepMesh_Delaun::superMesh( const Bnd_Box2d& theBox )
162 Standard_Real aMinX, aMinY, aMaxX, aMaxY;
163 theBox.Get( aMinX, aMinY, aMaxX, aMaxY );
164 Standard_Real aDeltaX = aMaxX - aMinX;
165 Standard_Real aDeltaY = aMaxY - aMinY;
167 Standard_Real aDeltaMin = Min( aDeltaX, aDeltaY );
168 Standard_Real aDeltaMax = Max( aDeltaX, aDeltaY );
169 Standard_Real aDelta = aDeltaX + aDeltaY;
171 myCircles.SetMinMaxSize( gp_XY( aMinX, aMinY ), gp_XY( aMaxX, aMaxY ) );
173 Standard_Integer aScaler = 2;
174 if ( myMeshData->NbNodes() > 100 )
176 else if( myMeshData->NbNodes() > 1000 )
179 myCircles.SetCellSize( aDeltaX / aScaler,
182 mySupVert[0] = myMeshData->AddNode(
183 BRepMesh_Vertex( ( aMinX + aMaxX ) / 2, aMaxY + aDeltaMax, BRepMesh_Free ) );
185 mySupVert[1] = myMeshData->AddNode(
186 BRepMesh_Vertex( aMinX - aDelta, aMinY - aDeltaMin, BRepMesh_Free ) );
188 mySupVert[2] = myMeshData->AddNode(
189 BRepMesh_Vertex( aMaxX + aDelta, aMinY - aDeltaMin, BRepMesh_Free ) );
191 if ( !myIsPositiveOrientation )
193 Standard_Integer aTmp;
195 mySupVert[1] = mySupVert[2];
199 Standard_Integer anEdgeId[3];
201 for (Standard_Integer aNodeId = 0; aNodeId < 3; ++aNodeId)
203 Standard_Integer aFirstNode = aNodeId;
204 Standard_Integer aLastNode = (aNodeId + 1) % 3;
205 anEdgeId[aNodeId] = myMeshData->AddLink( BRepMesh_Edge(
206 mySupVert[aFirstNode], mySupVert[aLastNode], BRepMesh_Free ) );
209 mySupTrian = BRepMesh_Triangle(
210 Abs( anEdgeId[0] ), Abs( anEdgeId[1] ), Abs( anEdgeId[2] ),
211 ( anEdgeId[0] > 0 ), ( anEdgeId[1] > 0 ), ( anEdgeId[2] > 0),
215 //=======================================================================
216 //function : deleteTriangle
217 //purpose : Deletes the triangle with the given index and adds the free
218 // edges into the map.
219 // When an edge is suppressed more than one time it is destroyed.
220 //=======================================================================
221 void BRepMesh_Delaun::deleteTriangle( const Standard_Integer theIndex,
222 BRepMesh_MapOfIntegerInteger& theLoopEdges )
224 myCircles.Delete( theIndex );
226 Standard_Integer e[3];
227 Standard_Boolean o[3];
228 GetTriangle( theIndex ).Edges( e[0], e[1], e[2],
231 myMeshData->RemoveElement( theIndex );
233 for ( Standard_Integer i = 0; i < 3; ++i )
235 if ( !theLoopEdges.Bind( e[i], o[i] ) )
237 theLoopEdges.UnBind( e[i] );
238 myMeshData->RemoveLink( e[i] );
243 //=======================================================================
245 //purpose : Computes the triangulation and add the vertices edges and
246 // triangles to the Mesh data structure
247 //=======================================================================
248 void BRepMesh_Delaun::compute( TColStd_Array1OfInteger& theVertexIndexes )
250 // Insertion of edges of super triangles in the list of free edges:
251 BRepMesh_MapOfIntegerInteger aLoopEdges( 10, myMeshData->Allocator() );
252 Standard_Integer e[3];
253 Standard_Boolean o[3];
254 mySupTrian.Edges( e[0], e[1], e[2],
257 aLoopEdges.Bind( e[0], Standard_True );
258 aLoopEdges.Bind( e[1], Standard_True );
259 aLoopEdges.Bind( e[2], Standard_True );
261 if ( theVertexIndexes.Length() > 0 )
263 // Creation of 3 trianglers with the first node and the edges of the super triangle:
264 Standard_Integer anVertexIdx = theVertexIndexes.Lower();
265 createTriangles( theVertexIndexes( anVertexIdx ), aLoopEdges );
267 // Add other nodes to the mesh
268 createTrianglesOnNewVertices( theVertexIndexes );
271 // Destruction of triangles containing a top of the super triangle
272 BRepMesh_SelectorOfDataStructureOfDelaun aSelector( myMeshData );
273 for (Standard_Integer aSupVertId = 0; aSupVertId < 3; ++aSupVertId)
274 aSelector.NeighboursOfNode( mySupVert[aSupVertId] );
277 BRepMesh_MapOfInteger::Iterator aFreeTriangles( aSelector.Elements() );
278 for ( ; aFreeTriangles.More(); aFreeTriangles.Next() )
279 deleteTriangle( aFreeTriangles.Key(), aLoopEdges );
281 // All edges that remain free are removed from aLoopEdges;
282 // only the boundary edges of the triangulation remain there
283 BRepMesh_MapOfIntegerInteger::Iterator aFreeEdges( aLoopEdges );
284 for ( ; aFreeEdges.More(); aFreeEdges.Next() )
286 if ( myMeshData->ElemConnectedTo( aFreeEdges.Key() ).IsEmpty() )
287 myMeshData->RemoveLink( aFreeEdges.Key() );
290 // The tops of the super triangle are destroyed
291 for (Standard_Integer aSupVertId = 0; aSupVertId < 3; ++aSupVertId)
292 myMeshData->RemoveNode( mySupVert[aSupVertId] );
295 //=======================================================================
296 //function : createTriangles
297 //purpose : Creates the triangles beetween the node and the polyline.
298 //=======================================================================
299 void BRepMesh_Delaun::createTriangles ( const Standard_Integer theVertexIndex,
300 BRepMesh_MapOfIntegerInteger& thePoly )
302 ListOfInteger aLoopEdges, anExternalEdges;
303 const gp_XY& aVertexCoord = myMeshData->GetNode( theVertexIndex ).Coord();
305 BRepMesh_MapOfIntegerInteger::Iterator anEdges( thePoly );
306 for ( ; anEdges.More(); anEdges.Next() )
308 Standard_Integer anEdgeId = anEdges.Key();
309 const BRepMesh_Edge& anEdge = GetEdge( anEdgeId );
311 Standard_Boolean isPositive = (Standard_Boolean)thePoly( anEdgeId );
313 Standard_Integer aNodes[3];
316 aNodes[0] = anEdge.FirstNode();
317 aNodes[2] = anEdge.LastNode();
321 aNodes[0] = anEdge.LastNode();
322 aNodes[2] = anEdge.FirstNode();
324 aNodes[1] = theVertexIndex;
326 const BRepMesh_Vertex& aFirstVertex = GetVertex( aNodes[0] );
327 const BRepMesh_Vertex& aLastVertex = GetVertex( aNodes[2] );
329 gp_XY anEdgeDir( aLastVertex.Coord() - aFirstVertex.Coord() );
330 Standard_Real anEdgeLen = anEdgeDir.Modulus();
331 if ( anEdgeLen < Precision )
334 anEdgeDir.SetCoord( anEdgeDir.X() / anEdgeLen,
335 anEdgeDir.Y() / anEdgeLen );
337 gp_XY aFirstLinkDir( aFirstVertex.Coord() - aVertexCoord );
338 gp_XY aLastLinkDir ( aVertexCoord - aLastVertex.Coord() );
340 Standard_Real aDist12 = aFirstLinkDir ^ anEdgeDir;
341 Standard_Real aDist23 = anEdgeDir ^ aLastLinkDir;
342 if ( Abs( aDist12 ) < Precision ||
343 Abs( aDist23 ) < Precision )
348 Standard_Boolean isSensOK;
349 if ( myIsPositiveOrientation )
350 isSensOK = ( aDist12 > 0. && aDist23 > 0.);
352 isSensOK = ( aDist12 < 0. && aDist23 < 0.);
355 BRepMesh_Edge aFirstLink( aNodes[1], aNodes[0], BRepMesh_Free );
356 BRepMesh_Edge aLastLink ( aNodes[2], aNodes[1], BRepMesh_Free );
358 Standard_Integer anEdgesInfo[3] = {
359 myMeshData->AddLink( aFirstLink ),
360 isPositive ? anEdgeId : -anEdgeId,
361 myMeshData->AddLink( aLastLink ) };
365 Standard_Integer anEdges[3];
366 Standard_Boolean anEdgesOri[3];
367 for ( Standard_Integer aTriLinkIt = 0; aTriLinkIt < 3; ++aTriLinkIt )
369 const Standard_Integer& anEdgeInfo = anEdgesInfo[aTriLinkIt];
370 anEdges[aTriLinkIt] = Abs( anEdgeInfo );
371 anEdgesOri[aTriLinkIt] = anEdgeInfo > 0;
374 addTriangle( anEdges, anEdgesOri, aNodes );
379 aLoopEdges.Append( anEdges.Key() );
381 aLoopEdges.Append( -anEdges.Key() );
383 if ( aFirstLinkDir.SquareModulus() > aLastLinkDir.SquareModulus() )
384 anExternalEdges.Append( Abs( anEdgesInfo[0] ) );
386 anExternalEdges.Append( Abs( anEdgesInfo[2] ) );
391 while ( !anExternalEdges.IsEmpty() )
393 const BRepMesh_PairOfIndex& aPair =
394 myMeshData->ElemConnectedTo( Abs( anExternalEdges.First() ) );
397 if ( !aPair.IsEmpty() )
398 deleteTriangle( aPair.FirstIndex(), thePoly );
400 anExternalEdges.RemoveFirst();
403 for ( anEdges.Initialize( thePoly ); anEdges.More(); anEdges.Next() )
405 if ( myMeshData->ElemConnectedTo( anEdges.Key() ).IsEmpty() )
406 myMeshData->RemoveLink( anEdges.Key() );
409 while ( !aLoopEdges.IsEmpty() )
411 const BRepMesh_Edge& anEdge = GetEdge( Abs( aLoopEdges.First() ) );
412 if ( anEdge.Movability() != BRepMesh_Deleted )
414 Standard_Integer anEdgeIdx = aLoopEdges.First();
415 meshLeftPolygonOf( Abs( anEdgeIdx ), ( anEdgeIdx > 0 ) );
418 aLoopEdges.RemoveFirst();
422 //=======================================================================
423 //function : createTrianglesOnNewVertices
424 //purpose : Creation of triangles from the new nodes
425 //=======================================================================
426 void BRepMesh_Delaun::createTrianglesOnNewVertices( TColStd_Array1OfInteger& theVertexIndexes )
428 BRepMesh_MapOfIntegerInteger aLoopEdges( 10, myMeshData->Allocator() );
430 // Insertion of nodes :
431 Standard_Boolean isModify = Standard_True;
433 Standard_Integer anIndex = theVertexIndexes.Lower();
434 Standard_Integer anUpper = theVertexIndexes.Upper();
435 for( ; anIndex <= anUpper; ++anIndex )
439 Standard_Integer aVertexIdx = theVertexIndexes( anIndex );
440 const BRepMesh_Vertex& aVertex = GetVertex( aVertexIdx );
442 // Iterator in the list of indexes of circles containing the node
443 BRepMesh_ListOfInteger& aCirclesList = myCircles.Select( aVertex.Coord() );
445 Standard_Integer onEgdeId = 0, aTriangleId = 0;
446 BRepMesh_ListOfInteger::Iterator aCircleIt( aCirclesList );
447 for ( ; aCircleIt.More(); aCircleIt.Next() )
449 // To add a node in the mesh it is necessary to check conditions:
450 // - the node should be within the boundaries of the mesh and so in an existing triangle
451 // - all adjacent triangles should belong to a component connected with this triangle
452 if ( Contains( aCircleIt.Value(), aVertex, onEgdeId ) )
456 aTriangleId = aCircleIt.Value();
457 aCirclesList.Remove( aCircleIt );
460 else if ( GetEdge( onEgdeId ).Movability() == BRepMesh_Free )
462 aTriangleId = aCircleIt.Value();
463 aCirclesList.Remove( aCircleIt );
469 if ( aTriangleId > 0 )
471 deleteTriangle( aTriangleId, aLoopEdges );
473 isModify = Standard_True;
474 while ( isModify && !aCirclesList.IsEmpty() )
476 isModify = Standard_False;
477 BRepMesh_ListOfInteger::Iterator aCircleIt1( aCirclesList );
478 for ( ; aCircleIt1.More(); aCircleIt1.Next() )
480 Standard_Integer e[3];
481 Standard_Boolean o[3];
482 GetTriangle( aCircleIt1.Value() ).Edges( e[0], e[1], e[2],
485 if ( aLoopEdges.IsBound( e[0] ) ||
486 aLoopEdges.IsBound( e[1] ) ||
487 aLoopEdges.IsBound( e[2] ) )
489 isModify = Standard_True;
490 deleteTriangle( aCircleIt1.Value(), aLoopEdges );
491 aCirclesList.Remove( aCircleIt1 );
497 // Creation of triangles with the current node and free edges
498 // and removal of these edges from the list of free edges
499 createTriangles( aVertexIdx, aLoopEdges );
502 // Check that internal edges are not crossed by triangles
503 Handle(BRepMesh_MapOfInteger) anInternalEdges = InternalEdges();
505 // Destruction of triancles intersecting internal edges
506 // and their replacement by makeshift triangles
507 BRepMesh_MapOfInteger::Iterator anInernalEdgesIt( *anInternalEdges );
508 for ( ; anInernalEdgesIt.More(); anInernalEdgesIt.Next() )
510 Standard_Integer aNbC;
511 aNbC = myMeshData->ElemConnectedTo( anInernalEdgesIt.Key() ).Extent();
514 meshLeftPolygonOf( anInernalEdgesIt.Key(), Standard_True );
515 meshLeftPolygonOf( anInernalEdgesIt.Key(), Standard_False );
519 // Adjustment of meshes to boundary edges
523 //=======================================================================
524 //function : isBoundToFrontier
525 //purpose : Goes through the neighbour triangles around the given node
526 // started from the given link, returns TRUE if some triangle
527 // has a bounding frontier edge or FALSE elsewhere.
528 // Stop link is used to prevent cycles.
529 // Previous element Id is used to identify next neighbor element.
530 //=======================================================================
531 Standard_Boolean BRepMesh_Delaun::isBoundToFrontier(
532 const Standard_Integer theRefNodeId,
533 const Standard_Integer theRefLinkId,
534 const Standard_Integer theStopLinkId,
535 const Standard_Integer thePrevElementId)
537 const BRepMesh_PairOfIndex& aPair =
538 myMeshData->ElemConnectedTo( theRefLinkId );
539 if ( aPair.IsEmpty() )
540 return Standard_False;
542 Standard_Integer aNbElements = aPair.Extent();
543 for ( Standard_Integer anElemIt = 1; anElemIt <= aNbElements; ++anElemIt )
545 const Standard_Integer aTriId = aPair.Index(anElemIt);
546 if ( aTriId < 0 || aTriId == thePrevElementId )
549 Standard_Integer anEdges[3];
550 Standard_Boolean anEdgesOri[3];
551 GetTriangle( aTriId ).Edges( anEdges[0], anEdges[1], anEdges[2],
552 anEdgesOri[0], anEdgesOri[1], anEdgesOri[2] );
554 for ( Standard_Integer anEdgeIt = 0; anEdgeIt < 3; ++anEdgeIt )
556 const Standard_Integer anEdgeId = anEdges[anEdgeIt];
557 if ( anEdgeId == theRefLinkId )
560 if ( anEdgeId == theStopLinkId )
561 return Standard_False;
563 const BRepMesh_Edge& anEdge = GetEdge( anEdgeId );
564 if ( anEdge.FirstNode() != theRefNodeId &&
565 anEdge.LastNode() != theRefNodeId )
570 if ( anEdge.Movability() != BRepMesh_Free )
571 return Standard_True;
573 return isBoundToFrontier( theRefNodeId, anEdgeId, theStopLinkId, aTriId );
577 return Standard_False;
580 //=======================================================================
581 //function : cleanupMesh
582 //purpose : Cleanup mesh from the free triangles
583 //=======================================================================
584 void BRepMesh_Delaun::cleanupMesh()
588 BRepMesh_MapOfIntegerInteger aLoopEdges( 10, myMeshData->Allocator() );
589 NCollection_Map<Standard_Integer> aDelTriangles;
591 Handle(BRepMesh_MapOfInteger) aFreeEdges = FreeEdges();
592 BRepMesh_MapOfInteger::Iterator aFreeEdgesIt( *aFreeEdges );
593 for ( ; aFreeEdgesIt.More(); aFreeEdgesIt.Next() )
595 const Standard_Integer& aFreeEdgeId = aFreeEdgesIt.Key();
596 const BRepMesh_Edge& anEdge = GetEdge( aFreeEdgeId );
597 if ( anEdge.Movability() == BRepMesh_Frontier )
600 const BRepMesh_PairOfIndex& aPair =
601 myMeshData->ElemConnectedTo( aFreeEdgeId );
602 if ( aPair.IsEmpty() )
604 aLoopEdges.Bind( aFreeEdgeId, Standard_True );
608 Standard_Integer aTriId = aPair.FirstIndex();
610 // Check that the connected triangle is not surrounded by another triangles
611 Standard_Integer anEdges[3];
612 Standard_Boolean anEdgesOri[3];
613 GetTriangle( aTriId ).Edges( anEdges[0], anEdges[1], anEdges[2],
614 anEdgesOri[0], anEdgesOri[1], anEdgesOri[2] );
616 Standard_Boolean isCanNotBeRemoved = Standard_True;
617 for ( Standard_Integer aCurEdgeIdx = 0; aCurEdgeIdx < 3; ++aCurEdgeIdx )
619 if ( anEdges[aCurEdgeIdx] != aFreeEdgeId )
622 for ( Standard_Integer anOtherEdgeIt = 1; anOtherEdgeIt <= 2; ++anOtherEdgeIt )
624 Standard_Integer anOtherEdgeId = ( aCurEdgeIdx + anOtherEdgeIt ) % 3;
625 const BRepMesh_PairOfIndex& anOtherEdgePair =
626 myMeshData->ElemConnectedTo( anEdges[anOtherEdgeId] );
628 if ( anOtherEdgePair.Extent() < 2 )
630 isCanNotBeRemoved = Standard_False;
638 if ( isCanNotBeRemoved )
641 Standard_Boolean isConnected[2] = { Standard_False, Standard_False };
642 for ( Standard_Integer aLinkNodeIt = 0; aLinkNodeIt < 2; ++aLinkNodeIt )
644 isConnected[aLinkNodeIt] = isBoundToFrontier( ( aLinkNodeIt == 0 ) ?
645 anEdge.FirstNode() : anEdge.LastNode(),
646 aFreeEdgeId, aFreeEdgeId, -1);
649 if ( !isConnected[0] || !isConnected[1] )
650 aDelTriangles.Add( aTriId );
653 // Destruction of triangles :
654 Standard_Integer aDeletedTrianglesNb = 0;
655 NCollection_Map<Standard_Integer>::Iterator aDelTrianglesIt( aDelTriangles );
656 for ( ; aDelTrianglesIt.More(); aDelTrianglesIt.Next() )
658 deleteTriangle( aDelTrianglesIt.Key(), aLoopEdges );
659 aDeletedTrianglesNb++;
662 // Destruction of remaining hanging edges
663 BRepMesh_MapOfIntegerInteger::Iterator aLoopEdgesIt( aLoopEdges );
664 for ( ; aLoopEdgesIt.More(); aLoopEdgesIt.Next() )
666 if ( myMeshData->ElemConnectedTo( aLoopEdgesIt.Key() ).IsEmpty() )
667 myMeshData->RemoveLink( aLoopEdgesIt.Key() );
670 if ( aDeletedTrianglesNb == 0 )
675 //=======================================================================
676 //function : frontierAdjust
677 //purpose : Adjust the mesh on the frontier
678 //=======================================================================
679 void BRepMesh_Delaun::frontierAdjust()
681 Handle(BRepMesh_MapOfInteger) aFrontier = Frontier();
682 NCollection_Vector<Standard_Integer> aFailedFrontiers;
683 BRepMesh_MapOfIntegerInteger aLoopEdges( 10, myMeshData->Allocator() );
684 BRepMesh_Delaun::HandleOfMapOfInteger aIntFrontierEdges = new NCollection_Map<Standard_Integer>();
685 for ( Standard_Integer aPass = 1; aPass <= 2; ++aPass )
687 // 1 pass): find external triangles on boundary edges;
688 // 2 pass): find external triangles on boundary edges appeared
689 // during triangles replacement.
691 BRepMesh_MapOfInteger::Iterator aFrontierIt( *aFrontier );
692 for ( ; aFrontierIt.More(); aFrontierIt.Next() )
694 Standard_Integer aFrontierId = aFrontierIt.Key();
695 const BRepMesh_PairOfIndex& aPair = myMeshData->ElemConnectedTo( aFrontierId );
696 Standard_Integer aNbElem = aPair.Extent();
697 for( Standard_Integer aElemIt = 1; aElemIt <= aNbElem; ++aElemIt )
699 const Standard_Integer aPriorElemId = aPair.Index( aElemIt );
700 if( aPriorElemId < 0 )
703 Standard_Integer e[3];
704 Standard_Boolean o[3];
705 GetTriangle( aPriorElemId ).Edges( e[0], e[1], e[2],
708 Standard_Boolean isTriangleFound = Standard_False;
709 for ( Standard_Integer n = 0; n < 3; ++n )
711 if ( aFrontierId == e[n] && !o[n] )
713 // Destruction of external triangles on boundary edges
714 isTriangleFound = Standard_True;
715 deleteTriangle( aPriorElemId, aLoopEdges );
720 if ( isTriangleFound )
725 // destrucrion of remaining hanging edges :
726 BRepMesh_MapOfIntegerInteger::Iterator aLoopEdgesIt( aLoopEdges );
727 for ( ; aLoopEdgesIt.More(); aLoopEdgesIt.Next() )
729 Standard_Integer aLoopEdgeId = aLoopEdgesIt.Key();
730 if (myMeshData->ElemConnectedTo( aLoopEdgeId ).IsEmpty() )
731 myMeshData->RemoveLink( aLoopEdgeId );
734 // destruction of triangles crossing the boundary edges and
735 // their replacement by makeshift triangles
736 for ( aFrontierIt.Reset(); aFrontierIt.More(); aFrontierIt.Next() )
738 Standard_Integer aFrontierId = aFrontierIt.Key();
739 if ( !myMeshData->ElemConnectedTo( aFrontierId ).IsEmpty() )
742 Standard_Boolean isSuccess =
743 meshLeftPolygonOf( aFrontierId, Standard_True, aIntFrontierEdges );
745 if ( aPass == 2 && !isSuccess )
746 aFailedFrontiers.Append( aFrontierId );
752 // When the mesh has been cleaned up, try to process frontier edges
753 // once again to fill the possible gaps that might be occured in case of "saw" -
754 // situation when frontier edge has a triangle at a right side, but its free
755 // links cross another frontieres and meshLeftPolygonOf itself can't collect
757 NCollection_Vector<Standard_Integer>::Iterator aFailedFrontiersIt( aFailedFrontiers );
758 for ( ; aFailedFrontiersIt.More(); aFailedFrontiersIt.Next() )
760 Standard_Integer aFrontierId = aFailedFrontiersIt.Value();
761 if ( !myMeshData->ElemConnectedTo( aFrontierId ).IsEmpty() )
764 meshLeftPolygonOf( aFrontierId, Standard_True, aIntFrontierEdges );
768 //=======================================================================
769 //function : fillBndBox
770 //purpose : Add boundig box for edge defined by start & end point to
771 // the given vector of bounding boxes for triangulation edges
772 //=======================================================================
773 void BRepMesh_Delaun::fillBndBox( NCollection_Sequence<Bnd_B2d>& theBoxes,
774 const BRepMesh_Vertex& theV1,
775 const BRepMesh_Vertex& theV2 )
778 aBox.Add( theV1.Coord() );
779 aBox.Add( theV2.Coord() );
780 theBoxes.Append( aBox );
783 //=======================================================================
784 //function : meshLeftPolygonOf
785 //purpose : Collect the polygon at the left of the given edge (material side)
786 //=======================================================================
787 Standard_Boolean BRepMesh_Delaun::meshLeftPolygonOf(
788 const Standard_Integer theStartEdgeId,
789 const Standard_Boolean isForward,
790 BRepMesh_Delaun::HandleOfMapOfInteger theSkipped )
792 if ( !theSkipped.IsNull() && theSkipped->Contains( theStartEdgeId ) )
793 return Standard_True;
795 const BRepMesh_Edge& aRefEdge = GetEdge( theStartEdgeId );
797 TColStd_SequenceOfInteger aPolygon;
798 Standard_Integer aStartNode, aPivotNode;
801 aPolygon.Append( theStartEdgeId );
802 aStartNode = aRefEdge.FirstNode();
803 aPivotNode = aRefEdge.LastNode();
807 aPolygon.Append( -theStartEdgeId );
808 aStartNode = aRefEdge.LastNode();
809 aPivotNode = aRefEdge.FirstNode();
813 const BRepMesh_Vertex& aStartEdgeVertexS = GetVertex( aStartNode );
814 BRepMesh_Vertex aPivotVertex = GetVertex( aPivotNode );
816 gp_Vec2d aRefLinkDir( aPivotVertex.Coord() -
817 aStartEdgeVertexS.Coord() );
819 if ( aRefLinkDir.SquareMagnitude() < Precision2 )
820 return Standard_True;
822 // Auxilary structures.
823 // Bounding boxes of polygon links to be used for preliminary
824 // analysis of intersections
825 NCollection_Sequence<Bnd_B2d> aBoxes;
826 fillBndBox( aBoxes, aStartEdgeVertexS, aPivotVertex );
829 NCollection_Map<Standard_Integer> aDeadLinks;
831 // Links are temporarily excluded from consideration
832 NCollection_Map<Standard_Integer> aLeprousLinks;
833 aLeprousLinks.Add( theStartEdgeId );
835 Standard_Boolean isSkipLeprous = Standard_True;
836 Standard_Integer aFirstNode = aStartNode;
837 while ( aPivotNode != aFirstNode )
839 Bnd_B2d aNextLinkBndBox;
840 gp_Vec2d aNextLinkDir;
841 Standard_Integer aNextPivotNode = 0;
843 Standard_Integer aNextLinkId = findNextPolygonLink(
845 aPivotNode, aPivotVertex, aRefLinkDir,
846 aBoxes, aPolygon, theSkipped,
847 isSkipLeprous, aLeprousLinks, aDeadLinks,
848 aNextPivotNode, aNextLinkDir, aNextLinkBndBox );
850 if ( aNextLinkId != 0 )
852 aStartNode = aPivotNode;
853 aRefLinkDir = aNextLinkDir;
855 aPivotNode = aNextPivotNode;
856 aPivotVertex = GetVertex( aNextPivotNode );
858 aBoxes.Append ( aNextLinkBndBox );
859 aPolygon.Append( aNextLinkId );
861 isSkipLeprous = Standard_True;
866 if ( aPolygon.Length() == 1 )
867 return Standard_False;
869 // Return to the previous point
870 Standard_Integer aDeadLinkId = Abs( aPolygon.Last() );
871 aDeadLinks.Add ( aDeadLinkId );
873 aLeprousLinks.Remove( aDeadLinkId );
874 aPolygon.Remove ( aPolygon.Length() );
875 aBoxes.Remove ( aBoxes.Length() );
877 Standard_Integer aPrevLinkInfo = aPolygon.Last();
878 const BRepMesh_Edge& aPrevLink = GetEdge( Abs( aPrevLinkInfo ) );
880 if( aPrevLinkInfo > 0 )
882 aStartNode = aPrevLink.FirstNode();
883 aPivotNode = aPrevLink.LastNode();
887 aStartNode = aPrevLink.LastNode();
888 aPivotNode = aPrevLink.FirstNode();
891 aPivotVertex = GetVertex( aPivotNode );
893 aPivotVertex.Coord() - GetVertex( aStartNode ).Coord();
895 isSkipLeprous = Standard_False;
899 if ( aPolygon.Length() < 3 )
900 return Standard_False;
902 cleanupPolygon( aPolygon, aBoxes );
903 meshPolygon ( aPolygon, aBoxes, theSkipped );
905 return Standard_True;
908 //=======================================================================
909 //function : findNextPolygonLink
910 //purpose : Find next link starting from the given node and has maximum
911 // angle respect the given reference link.
912 // Each time the next link is found other neighbor links at the
913 // pivot node are marked as leprous and will be excluded from
914 // consideration next time until a hanging end is occured.
915 //=======================================================================
916 Standard_Integer BRepMesh_Delaun::findNextPolygonLink(
917 const Standard_Integer& theFirstNode,
918 const Standard_Integer& thePivotNode,
919 const BRepMesh_Vertex& thePivotVertex,
920 const gp_Vec2d& theRefLinkDir,
921 const NCollection_Sequence<Bnd_B2d>& theBoxes,
922 const TColStd_SequenceOfInteger& thePolygon,
923 const BRepMesh_Delaun::HandleOfMapOfInteger theSkipped,
924 const Standard_Boolean& isSkipLeprous,
925 NCollection_Map<Standard_Integer>& theLeprousLinks,
926 NCollection_Map<Standard_Integer>& theDeadLinks,
927 Standard_Integer& theNextPivotNode,
928 gp_Vec2d& theNextLinkDir,
929 Bnd_B2d& theNextLinkBndBox )
931 // Find the next link having the greatest angle
932 // respect to a direction of a reference one
933 Standard_Real aMaxAngle = myIsPositiveOrientation ?
934 RealFirst() : RealLast();
936 Standard_Integer aNextLinkId = 0;
937 BRepMesh_ListOfInteger::Iterator aLinkIt( myMeshData->LinkNeighboursOf( thePivotNode ) );
938 for ( ; aLinkIt.More(); aLinkIt.Next() )
940 const Standard_Integer& aNeighbourLinkInfo = aLinkIt.Value();
941 Standard_Integer aNeighbourLinkId = Abs( aNeighbourLinkInfo );
943 if ( theDeadLinks.Contains( aNeighbourLinkId ) ||
944 ( !theSkipped.IsNull() && theSkipped->Contains( aNeighbourLinkId ) ) )
949 Standard_Boolean isLeprous = theLeprousLinks.Contains( aNeighbourLinkId );
950 if ( isSkipLeprous && isLeprous )
953 const BRepMesh_Edge& aNeighbourLink = GetEdge( aNeighbourLinkId );
955 // Determine whether the link belongs to the mesh
956 if ( aNeighbourLink.Movability() == BRepMesh_Free &&
957 myMeshData->ElemConnectedTo( aNeighbourLinkInfo ).IsEmpty() )
959 theDeadLinks.Add( aNeighbourLinkId );
963 Standard_Integer anOtherNode = aNeighbourLink.FirstNode();
964 if ( anOtherNode == thePivotNode )
965 anOtherNode = aNeighbourLink.LastNode();
967 gp_Vec2d aCurLinkDir( GetVertex( anOtherNode ).Coord() -
968 thePivotVertex.Coord() );
970 if ( aCurLinkDir.SquareMagnitude() < Precision2 )
972 theDeadLinks.Add( aNeighbourLinkId );
977 theLeprousLinks.Add( aNeighbourLinkId );
979 Standard_Real anAngle = theRefLinkDir.Angle( aCurLinkDir );
980 Standard_Boolean isFrontier =
981 ( aNeighbourLink.Movability() == BRepMesh_Frontier );
983 Standard_Boolean isCheckPointOnEdge = Standard_True;
986 if ( Abs( Abs(anAngle) - M_PI ) < Precision::Angular() )
988 // Glued constrains - don't check intersection
989 isCheckPointOnEdge = Standard_False;
990 anAngle = Abs( anAngle );
994 if ( ( myIsPositiveOrientation && anAngle <= aMaxAngle ) ||
995 (!myIsPositiveOrientation && anAngle >= aMaxAngle ) )
1000 Standard_Boolean isCheckEndPoints = ( anOtherNode != theFirstNode );
1003 Standard_Boolean isNotIntersect =
1004 checkIntersection( aNeighbourLink, thePolygon, theBoxes,
1005 isCheckEndPoints, isCheckPointOnEdge, Standard_True, aBox );
1007 if( isNotIntersect )
1009 aMaxAngle = anAngle;
1011 theNextLinkDir = aCurLinkDir;
1012 theNextPivotNode = anOtherNode;
1013 theNextLinkBndBox = aBox;
1015 aNextLinkId = ( aNeighbourLink.FirstNode() == thePivotNode ) ?
1016 aNeighbourLinkId : -aNeighbourLinkId;
1023 //=======================================================================
1024 //function : checkIntersection
1025 //purpose : Check is the given link intersects the polygon boundaries.
1026 // Returns bounding box for the given link trough the
1027 // <theLinkBndBox> parameter.
1028 //=======================================================================
1029 Standard_Boolean BRepMesh_Delaun::checkIntersection(
1030 const BRepMesh_Edge& theLink,
1031 const TColStd_SequenceOfInteger& thePolygon,
1032 const NCollection_Sequence<Bnd_B2d>& thePolyBoxes,
1033 const Standard_Boolean isConsiderEndPointTouch,
1034 const Standard_Boolean isConsiderPointOnEdge,
1035 const Standard_Boolean isSkipLastEdge,
1036 Bnd_B2d& theLinkBndBox ) const
1038 theLinkBndBox.Add( GetVertex( theLink.FirstNode() ).Coord() );
1039 theLinkBndBox.Add( GetVertex( theLink.LastNode() ).Coord() );
1041 Standard_Integer aPolyLen = thePolygon.Length();
1042 // Don't check intersection with the last link
1043 if ( isSkipLastEdge )
1046 Standard_Boolean isFrontier =
1047 ( theLink.Movability() == BRepMesh_Frontier );
1049 for ( Standard_Integer aPolyIt = 1; aPolyIt <= aPolyLen; ++aPolyIt )
1051 if ( !theLinkBndBox.IsOut( thePolyBoxes.Value( aPolyIt ) ) )
1053 // intersection is possible...
1054 Standard_Integer aPolyLinkId = Abs( thePolygon( aPolyIt ) );
1055 const BRepMesh_Edge& aPolyLink = GetEdge( aPolyLinkId );
1057 // skip intersections between frontier edges
1058 if ( aPolyLink.Movability() == BRepMesh_Frontier && isFrontier )
1062 BRepMesh_WireInterferenceChecker::IntFlag aIntFlag =
1063 intSegSeg( theLink, aPolyLink, isConsiderEndPointTouch,
1064 isConsiderPointOnEdge, anIntPnt );
1066 if ( aIntFlag != BRepMesh_WireInterferenceChecker::NoIntersection )
1067 return Standard_False;
1071 // Ok, no intersection
1072 return Standard_True;
1075 //=======================================================================
1076 //function : addTriangle
1077 //purpose : Add a triangle based on the given oriented edges into mesh
1078 //=======================================================================
1079 inline void BRepMesh_Delaun::addTriangle( const Standard_Integer (&theEdgesId)[3],
1080 const Standard_Boolean (&theEdgesOri)[3],
1081 const Standard_Integer (&theNodesId)[3] )
1083 Standard_Integer aNewTriangleId =
1084 myMeshData->AddElement( BRepMesh_Triangle(
1085 theEdgesId[0], theEdgesId[1], theEdgesId[2],
1086 theEdgesOri[0], theEdgesOri[1], theEdgesOri[2],
1089 Standard_Boolean isAdded = myCircles.Add(
1090 GetVertex( theNodesId[0] ).Coord(),
1091 GetVertex( theNodesId[1] ).Coord(),
1092 GetVertex( theNodesId[2] ).Coord(),
1096 myMeshData->RemoveElement( aNewTriangleId );
1099 //=======================================================================
1100 //function : cleanupPolygon
1101 //purpose : Remove internal triangles from the given polygon
1102 //=======================================================================
1103 void BRepMesh_Delaun::cleanupPolygon( const TColStd_SequenceOfInteger& thePolygon,
1104 const NCollection_Sequence<Bnd_B2d>& thePolyBoxes )
1106 Standard_Integer aPolyLen = thePolygon.Length();
1110 BRepMesh_MapOfIntegerInteger aLoopEdges( 10, myMeshData->Allocator() );
1111 NCollection_Map<Standard_Integer> anIgnoredEdges;
1112 NCollection_Map<Standard_Integer> aPolyVerticesFindMap;
1113 NCollection_Vector<Standard_Integer> aPolyVertices;
1114 // Collect boundary vertices of the polygon
1115 for ( Standard_Integer aPolyIt = 1; aPolyIt <= aPolyLen; ++aPolyIt )
1117 Standard_Integer aPolyEdgeInfo = thePolygon( aPolyIt );
1118 Standard_Integer aPolyEdgeId = Abs( aPolyEdgeInfo );
1119 anIgnoredEdges.Add( aPolyEdgeId );
1121 Standard_Boolean isForward = ( aPolyEdgeInfo > 0 );
1122 const BRepMesh_PairOfIndex& aPair =
1123 myMeshData->ElemConnectedTo( aPolyEdgeId );
1125 Standard_Integer anElemIt = 1;
1126 for ( ; anElemIt <= aPair.Extent(); ++anElemIt )
1128 Standard_Integer anElemId = aPair.Index( anElemIt );
1132 Standard_Integer anEdges[3];
1133 Standard_Boolean anEdgesOri[3];
1134 GetTriangle( anElemId ).Edges( anEdges[0], anEdges[1], anEdges[2],
1135 anEdgesOri[0], anEdgesOri[1], anEdgesOri[2] );
1137 Standard_Integer isTriangleFound = Standard_False;
1138 for ( Standard_Integer anEdgeIt = 0; anEdgeIt < 3; ++anEdgeIt )
1140 if ( anEdges[anEdgeIt] == aPolyEdgeId &&
1141 anEdgesOri[anEdgeIt] == isForward )
1143 isTriangleFound = Standard_True;
1144 deleteTriangle( anElemId, aLoopEdges );
1149 if ( isTriangleFound )
1153 // Skip a neighbor link to extract unique vertices each time
1156 const BRepMesh_Edge& aPolyEdge = GetEdge( aPolyEdgeId );
1157 Standard_Integer aFirstVertex = aPolyEdge.FirstNode();
1158 Standard_Integer aLastVertex = aPolyEdge.LastNode();
1160 aPolyVerticesFindMap.Add( aFirstVertex );
1161 aPolyVerticesFindMap.Add( aLastVertex );
1163 if ( aPolyEdgeInfo > 0 )
1165 aPolyVertices.Append( aFirstVertex );
1166 aPolyVertices.Append( aLastVertex );
1170 aPolyVertices.Append( aLastVertex );
1171 aPolyVertices.Append( aFirstVertex );
1176 // Make closed sequence
1177 if ( aPolyVertices.First() != aPolyVertices.Last() )
1178 aPolyVertices.Append( aPolyVertices.First() );
1180 NCollection_Map<Standard_Integer> aSurvivedLinks( anIgnoredEdges );
1182 Standard_Integer aPolyVertIt = 0;
1183 Standard_Integer anUniqueVerticesNum = aPolyVertices.Length() - 1;
1184 for ( ; aPolyVertIt < anUniqueVerticesNum; ++aPolyVertIt )
1186 killTrianglesAroundVertex( aPolyVertices( aPolyVertIt ),
1187 aPolyVertices, aPolyVerticesFindMap, thePolygon,
1188 thePolyBoxes, aSurvivedLinks, aLoopEdges );
1191 BRepMesh_MapOfIntegerInteger::Iterator aLoopEdgesIt( aLoopEdges );
1192 for ( ; aLoopEdgesIt.More(); aLoopEdgesIt.Next() )
1194 const Standard_Integer& aLoopEdgeId = aLoopEdgesIt.Key();
1195 if ( anIgnoredEdges.Contains( aLoopEdgeId ) )
1198 if ( myMeshData->ElemConnectedTo( aLoopEdgeId ).IsEmpty() )
1199 myMeshData->RemoveLink( aLoopEdgesIt.Key() );
1203 //=======================================================================
1204 //function : killTrianglesAroundVertex
1205 //purpose : Remove all triangles and edges that are placed
1206 // inside the polygon or crossed it.
1207 //=======================================================================
1208 void BRepMesh_Delaun::killTrianglesAroundVertex(
1209 const Standard_Integer theZombieNodeId,
1210 const NCollection_Vector<Standard_Integer>& thePolyVertices,
1211 const NCollection_Map<Standard_Integer>& thePolyVerticesFindMap,
1212 const TColStd_SequenceOfInteger& thePolygon,
1213 const NCollection_Sequence<Bnd_B2d>& thePolyBoxes,
1214 NCollection_Map<Standard_Integer>& theSurvivedLinks,
1215 BRepMesh_MapOfIntegerInteger& theLoopEdges )
1217 BRepMesh_ListOfInteger::Iterator aNeighborsIt =
1218 myMeshData->LinkNeighboursOf( theZombieNodeId );
1220 // Try to infect neighbor nodes
1221 NCollection_Vector<Standard_Integer> aVictimNodes;
1222 for ( ; aNeighborsIt.More(); aNeighborsIt.Next() )
1224 const Standard_Integer& aNeighborLinkId = aNeighborsIt.Value();
1225 if ( theSurvivedLinks.Contains( aNeighborLinkId ) )
1228 const BRepMesh_Edge& aNeighborLink = GetEdge( aNeighborLinkId );
1229 if ( aNeighborLink.Movability() == BRepMesh_Frontier )
1231 // Though, if it lies onto the polygon boundary -
1232 // take its triangles
1234 Standard_Boolean isNotIntersect =
1235 checkIntersection( aNeighborLink, thePolygon,
1236 thePolyBoxes, Standard_False, Standard_True,
1237 Standard_False, aBox );
1239 if ( isNotIntersect )
1242 theSurvivedLinks.Add( aNeighborLinkId );
1248 Standard_Integer anOtherNode = aNeighborLink.FirstNode();
1249 if ( anOtherNode == theZombieNodeId )
1250 anOtherNode = aNeighborLink.LastNode();
1252 // Possible sacrifice
1253 if ( !thePolyVerticesFindMap.Contains( anOtherNode ) )
1255 if ( isVertexInsidePolygon( anOtherNode, thePolyVertices ) )
1258 aVictimNodes.Append( anOtherNode );
1262 // Lucky. But it may intersect the polygon boundary.
1264 killTrianglesOnIntersectingLinks( aNeighborLinkId,
1265 aNeighborLink, anOtherNode, thePolygon,
1266 thePolyBoxes, theSurvivedLinks, theLoopEdges );
1273 // Add link to the survivers to avoid cycling
1274 theSurvivedLinks.Add( aNeighborLinkId );
1275 killLinkTriangles( aNeighborLinkId, theLoopEdges );
1278 // Go and do your job!
1279 NCollection_Vector<Standard_Integer>::Iterator aVictimIt( aVictimNodes );
1280 for ( ; aVictimIt.More(); aVictimIt.Next() )
1282 killTrianglesAroundVertex( aVictimIt.Value(), thePolyVertices,
1283 thePolyVerticesFindMap, thePolygon, thePolyBoxes,
1284 theSurvivedLinks, theLoopEdges );
1288 //=======================================================================
1289 //function : isVertexInsidePolygon
1290 //purpose : Checks is the given vertex lies inside the polygon
1291 //=======================================================================
1292 Standard_Boolean BRepMesh_Delaun::isVertexInsidePolygon(
1293 const Standard_Integer& theVertexId,
1294 const NCollection_Vector<Standard_Integer>& thePolygonVertices ) const
1296 Standard_Integer aPolyLen = thePolygonVertices.Length();
1298 return Standard_False;
1301 const gp_XY aCenterPointXY = GetVertex( theVertexId ).Coord();
1303 const BRepMesh_Vertex& aFirstVertex = GetVertex( thePolygonVertices( 0 ) );
1304 gp_Vec2d aPrevVertexDir( aFirstVertex.Coord() - aCenterPointXY );
1305 if ( aPrevVertexDir.SquareMagnitude() < Precision2 )
1306 return Standard_True;
1308 Standard_Real aTotalAng = 0.0;
1309 for ( Standard_Integer aPolyIt = 1; aPolyIt < aPolyLen; ++aPolyIt )
1311 const BRepMesh_Vertex& aPolyVertex = GetVertex( thePolygonVertices( aPolyIt ) );
1313 gp_Vec2d aCurVertexDir( aPolyVertex.Coord() - aCenterPointXY );
1314 if ( aCurVertexDir.SquareMagnitude() < Precision2 )
1315 return Standard_True;
1317 aTotalAng += aCurVertexDir.Angle( aPrevVertexDir );
1318 aPrevVertexDir = aCurVertexDir;
1321 if ( Abs( Angle2PI - aTotalAng ) > Precision::Angular() )
1322 return Standard_False;
1324 return Standard_True;
1327 //=======================================================================
1328 //function : killTrianglesOnIntersectingLinks
1329 //purpose : Checks is the given link crosses the polygon boundary.
1330 // If yes, kills its triangles and checks neighbor links on
1331 // boundary intersection. Does nothing elsewhere.
1332 //=======================================================================
1333 void BRepMesh_Delaun::killTrianglesOnIntersectingLinks(
1334 const Standard_Integer& theLinkToCheckId,
1335 const BRepMesh_Edge& theLinkToCheck,
1336 const Standard_Integer& theEndPoint,
1337 const TColStd_SequenceOfInteger& thePolygon,
1338 const NCollection_Sequence<Bnd_B2d>& thePolyBoxes,
1339 NCollection_Map<Standard_Integer>& theSurvivedLinks,
1340 BRepMesh_MapOfIntegerInteger& theLoopEdges )
1342 if ( theSurvivedLinks.Contains( theLinkToCheckId ) )
1346 Standard_Boolean isNotIntersect =
1347 checkIntersection( theLinkToCheck, thePolygon,
1348 thePolyBoxes, Standard_False, Standard_False,
1349 Standard_False, aBox );
1351 theSurvivedLinks.Add( theLinkToCheckId );
1353 if ( isNotIntersect )
1356 killLinkTriangles( theLinkToCheckId, theLoopEdges );
1358 BRepMesh_ListOfInteger::Iterator aNeighborsIt =
1359 myMeshData->LinkNeighboursOf( theEndPoint );
1361 for ( ; aNeighborsIt.More(); aNeighborsIt.Next() )
1363 const Standard_Integer& aNeighborLinkId = aNeighborsIt.Value();
1364 const BRepMesh_Edge& aNeighborLink = GetEdge( aNeighborLinkId );
1365 Standard_Integer anOtherNode = aNeighborLink.FirstNode();
1366 if ( anOtherNode == theEndPoint )
1367 anOtherNode = aNeighborLink.LastNode();
1369 killTrianglesOnIntersectingLinks( aNeighborLinkId,
1370 aNeighborLink, anOtherNode, thePolygon,
1371 thePolyBoxes, theSurvivedLinks, theLoopEdges );
1375 //=======================================================================
1376 //function : killLinkTriangles
1377 //purpose : Kill triangles bound to the given link.
1378 //=======================================================================
1379 void BRepMesh_Delaun::killLinkTriangles(
1380 const Standard_Integer& theLinkId,
1381 BRepMesh_MapOfIntegerInteger& theLoopEdges )
1383 const BRepMesh_PairOfIndex& aPair =
1384 myMeshData->ElemConnectedTo( theLinkId );
1386 Standard_Integer anElemNb = aPair.Extent();
1387 for ( Standard_Integer aPairIt = 1; aPairIt <= anElemNb; ++aPairIt )
1389 Standard_Integer anElemId = aPair.FirstIndex();
1393 deleteTriangle( anElemId, theLoopEdges );
1397 //=======================================================================
1398 //function : getOrientedNodes
1399 //purpose : Returns start and end nodes of the given edge in respect to
1401 //=======================================================================
1402 void BRepMesh_Delaun::getOrientedNodes(const BRepMesh_Edge& theEdge,
1403 const Standard_Boolean isForward,
1404 Standard_Integer *theNodes) const
1408 theNodes[0] = theEdge.FirstNode();
1409 theNodes[1] = theEdge.LastNode();
1413 theNodes[0] = theEdge.LastNode();
1414 theNodes[1] = theEdge.FirstNode();
1418 //=======================================================================
1419 //function : processLoop
1420 //purpose : Processes loop within the given polygon formed by range of
1421 // its links specified by start and end link indices.
1422 //=======================================================================
1423 void BRepMesh_Delaun::processLoop(const Standard_Integer theLinkFrom,
1424 const Standard_Integer theLinkTo,
1425 const TColStd_SequenceOfInteger& thePolygon,
1426 const NCollection_Sequence<Bnd_B2d>& thePolyBoxes)
1428 Standard_Integer aNbOfLinksInLoop = theLinkTo - theLinkFrom - 1;
1429 if ( aNbOfLinksInLoop < 3 )
1432 TColStd_SequenceOfInteger aPolygon;
1433 NCollection_Sequence<Bnd_B2d> aPolyBoxes;
1434 for ( ; aNbOfLinksInLoop > 0; --aNbOfLinksInLoop )
1436 Standard_Integer aLoopLinkIndex = theLinkFrom + aNbOfLinksInLoop;
1437 aPolygon .Prepend( thePolygon ( aLoopLinkIndex ) );
1438 aPolyBoxes.Prepend( thePolyBoxes( aLoopLinkIndex ) );
1440 meshPolygon( aPolygon, aPolyBoxes );
1443 //=======================================================================
1444 //function : createAndReplacePolygonLink
1445 //purpose : Creates new link based on the given nodes and updates the
1447 //=======================================================================
1448 Standard_Integer BRepMesh_Delaun::createAndReplacePolygonLink(
1449 const Standard_Integer *theNodes,
1450 const gp_Pnt2d *thePnts,
1451 const Standard_Integer theRootIndex,
1452 const ReplaceFlag theReplaceFlag,
1453 TColStd_SequenceOfInteger& thePolygon,
1454 NCollection_Sequence<Bnd_B2d>& thePolyBoxes )
1456 Standard_Integer aNewEdgeId =
1457 myMeshData->AddLink( BRepMesh_Edge(
1458 theNodes[0], theNodes[1], BRepMesh_Free ) );
1461 aNewBox.Add( thePnts[0] );
1462 aNewBox.Add( thePnts[1] );
1464 switch ( theReplaceFlag )
1466 case BRepMesh_Delaun::Replace:
1467 thePolygon .SetValue( theRootIndex, aNewEdgeId );
1468 thePolyBoxes.SetValue( theRootIndex, aNewBox );
1471 case BRepMesh_Delaun::InsertAfter:
1472 thePolygon .InsertAfter( theRootIndex, aNewEdgeId );
1473 thePolyBoxes.InsertAfter( theRootIndex, aNewBox );
1476 case BRepMesh_Delaun::InsertBefore:
1477 thePolygon .InsertBefore( theRootIndex, aNewEdgeId );
1478 thePolyBoxes.InsertBefore( theRootIndex, aNewBox );
1485 //=======================================================================
1486 //function : meshPolygon
1488 //=======================================================================
1489 void BRepMesh_Delaun::meshPolygon( TColStd_SequenceOfInteger& thePolygon,
1490 NCollection_Sequence<Bnd_B2d>& thePolyBoxes,
1491 BRepMesh_Delaun::HandleOfMapOfInteger theSkipped )
1493 // Check is the source polygon elementary
1494 if ( meshElementaryPolygon( thePolygon ) )
1497 // Check and correct boundary edges
1498 Standard_Integer aPolyLen = thePolygon.Length();
1499 const Standard_Real aPolyArea = Abs( polyArea( thePolygon, 1, aPolyLen ) );
1500 const Standard_Real aSmallLoopArea = 0.001 * aPolyArea;
1501 for ( Standard_Integer aPolyIt = 1; aPolyIt < aPolyLen; ++aPolyIt )
1503 Standard_Integer aCurEdgeInfo = thePolygon( aPolyIt );
1504 Standard_Integer aCurEdgeId = Abs( aCurEdgeInfo );
1505 const BRepMesh_Edge* aCurEdge = &GetEdge( aCurEdgeId );
1506 if ( aCurEdge->Movability() != BRepMesh_Frontier )
1509 Standard_Integer aCurNodes[2];
1510 getOrientedNodes( *aCurEdge, aCurEdgeInfo > 0, aCurNodes );
1512 gp_Pnt2d aCurPnts[2] = {
1513 GetVertex(aCurNodes[0]).Coord(),
1514 GetVertex(aCurNodes[1]).Coord()
1517 gp_Vec2d aCurVec( aCurPnts[0], aCurPnts[1] );
1519 // check further links
1520 Standard_Integer aNextPolyIt = aPolyIt + 1;
1521 for ( ; aNextPolyIt <= aPolyLen; ++aNextPolyIt )
1523 Standard_Integer aNextEdgeInfo = thePolygon( aNextPolyIt );
1524 Standard_Integer aNextEdgeId = Abs( aNextEdgeInfo );
1525 const BRepMesh_Edge* aNextEdge = &GetEdge( aNextEdgeId );
1526 if ( aNextEdge->Movability() != BRepMesh_Frontier )
1529 Standard_Integer aNextNodes[2];
1530 getOrientedNodes( *aNextEdge, aNextEdgeInfo > 0, aNextNodes );
1532 gp_Pnt2d aNextPnts[2] = {
1533 GetVertex(aNextNodes[0]).Coord(),
1534 GetVertex(aNextNodes[1]).Coord()
1538 BRepMesh_WireInterferenceChecker::IntFlag aIntFlag = intSegSeg( *aCurEdge,
1539 *aNextEdge, Standard_False, Standard_True, anIntPnt );
1541 if ( aIntFlag == BRepMesh_WireInterferenceChecker::NoIntersection )
1544 Standard_Boolean isRemoveFromFirst = Standard_False;
1545 Standard_Boolean isAddReplacingEdge = Standard_True;
1546 Standard_Integer aIndexToRemoveTo = aNextPolyIt;
1547 if ( aIntFlag == BRepMesh_WireInterferenceChecker::Cross )
1549 Standard_Real aLoopArea = polyArea( thePolygon, aPolyIt + 1, aNextPolyIt );
1550 gp_Vec2d aVec1( anIntPnt, aCurPnts [1] );
1551 gp_Vec2d aVec2( anIntPnt, aNextPnts[0] );
1553 aLoopArea += ( aVec1 ^ aVec2 ) / 2.;
1554 if ( Abs( aLoopArea ) > aSmallLoopArea )
1556 aNextNodes[1] = aCurNodes[0];
1557 aNextPnts [1] = aCurPnts [0];
1559 aNextEdgeId = Abs( createAndReplacePolygonLink( aNextNodes, aNextPnts,
1560 aNextPolyIt, BRepMesh_Delaun::Replace, thePolygon, thePolyBoxes ) );
1562 processLoop( aPolyIt, aNextPolyIt, thePolygon, thePolyBoxes );
1566 Standard_Real aDist1 = anIntPnt.SquareDistance(aNextPnts[0]);
1567 Standard_Real aDist2 = anIntPnt.SquareDistance(aNextPnts[1]);
1569 // Choose node with lower distance
1570 const Standard_Boolean isCloseToStart = ( aDist1 < aDist2 );
1571 const Standard_Integer aEndPointIndex = isCloseToStart ? 0 : 1;
1572 aCurNodes[1] = aNextNodes[aEndPointIndex];
1573 aCurPnts [1] = aNextPnts [aEndPointIndex];
1575 if ( isCloseToStart )
1578 // In this context only intersections between frontier edges
1579 // are possible. If intersection between edges of different
1580 // types occured - treat this case as invalid (i.e. result
1581 // might not reflect the expectations).
1582 if ( !theSkipped.IsNull() )
1584 Standard_Integer aSkippedLinkIt = aPolyIt;
1585 for ( ; aSkippedLinkIt <= aIndexToRemoveTo; ++aSkippedLinkIt )
1586 theSkipped->Add( Abs( thePolygon( aSkippedLinkIt ) ) );
1589 else if ( aIntFlag == BRepMesh_WireInterferenceChecker::PointOnSegment )
1591 // Indentify chopping link
1592 Standard_Boolean isFirstChopping = Standard_False;
1593 Standard_Integer aCheckPointIt = 0;
1594 for ( ; aCheckPointIt < 2; ++aCheckPointIt )
1596 gp_Pnt2d& aRefPoint = aCurPnts[aCheckPointIt];
1597 // Check is second link touches the first one
1598 gp_Vec2d aVec1( aRefPoint, aNextPnts[0] );
1599 gp_Vec2d aVec2( aRefPoint, aNextPnts[1] );
1600 if ( Abs( aVec1 ^ aVec2 ) < Precision )
1602 isFirstChopping = Standard_True;
1607 if ( isFirstChopping )
1609 // Split second link
1610 isAddReplacingEdge = Standard_False;
1611 isRemoveFromFirst = ( aCheckPointIt == 0 );
1613 Standard_Integer aSplitLink[3] = {
1615 aCurNodes [aCheckPointIt],
1619 gp_Pnt2d aSplitPnts[3] = {
1621 aCurPnts [aCheckPointIt],
1625 Standard_Integer aSplitLinkIt = 0;
1626 for ( ; aSplitLinkIt < 2; ++aSplitLinkIt )
1628 createAndReplacePolygonLink( &aSplitLink[aSplitLinkIt],
1629 &aSplitPnts[aSplitLinkIt], aNextPolyIt, ( aSplitLinkIt == 0 ) ?
1630 BRepMesh_Delaun::Replace : BRepMesh_Delaun::InsertAfter,
1631 thePolygon, thePolyBoxes );
1634 processLoop( aPolyIt + aCheckPointIt, aIndexToRemoveTo,
1635 thePolygon, thePolyBoxes );
1640 Standard_Integer aSplitLinkNodes[2] = {
1645 gp_Pnt2d aSplitLinkPnts[2] = {
1649 createAndReplacePolygonLink( aSplitLinkNodes, aSplitLinkPnts,
1650 aPolyIt, BRepMesh_Delaun::InsertAfter, thePolygon, thePolyBoxes );
1652 aCurNodes[1] = aNextNodes[1];
1653 aCurPnts [1] = aNextPnts [1];
1656 processLoop( aPolyIt + 1, aIndexToRemoveTo,
1657 thePolygon, thePolyBoxes );
1660 else if ( aIntFlag == BRepMesh_WireInterferenceChecker::Glued )
1662 if ( aCurNodes[1] == aNextNodes[0] )
1664 aCurNodes[1] = aNextNodes[1];
1665 aCurPnts [1] = aNextPnts [1];
1667 // TODO: Non-adjacent glued links within the polygon
1669 else if ( aIntFlag == BRepMesh_WireInterferenceChecker::Same )
1671 processLoop( aPolyIt, aNextPolyIt, thePolygon, thePolyBoxes );
1673 isRemoveFromFirst = Standard_True;
1674 isAddReplacingEdge = Standard_False;
1677 continue; // Not supported type
1679 if ( isAddReplacingEdge )
1681 aCurEdgeId = Abs( createAndReplacePolygonLink( aCurNodes, aCurPnts,
1682 aPolyIt, BRepMesh_Delaun::Replace, thePolygon, thePolyBoxes ) );
1684 aCurEdge = &GetEdge( aCurEdgeId );
1685 aCurVec = gp_Vec2d( aCurPnts[0], aCurPnts[1] );
1688 Standard_Integer aIndexToRemoveFrom =
1689 isRemoveFromFirst ? aPolyIt : aPolyIt + 1;
1691 thePolygon .Remove( aIndexToRemoveFrom, aIndexToRemoveTo );
1692 thePolyBoxes.Remove( aIndexToRemoveFrom, aIndexToRemoveTo );
1694 aPolyLen = thePolygon.Length();
1695 if ( isRemoveFromFirst )
1701 aNextPolyIt = aPolyIt;
1705 meshSimplePolygon( thePolygon, thePolyBoxes );
1708 //=======================================================================
1709 //function : meshElementaryPolygon
1710 //purpose : Triangulation of closed polygon containing only three edges.
1711 //=======================================================================
1712 inline Standard_Boolean BRepMesh_Delaun::meshElementaryPolygon(
1713 const TColStd_SequenceOfInteger& thePolygon )
1715 Standard_Integer aPolyLen = thePolygon.Length();
1717 return Standard_True;
1718 else if ( aPolyLen > 3 )
1719 return Standard_False;
1721 // Just create a triangle
1722 Standard_Integer anEdges[3];
1723 Standard_Boolean anEdgesOri[3];
1725 for ( Standard_Integer anEdgeIt = 0; anEdgeIt < 3; ++anEdgeIt )
1727 Standard_Integer anEdgeInfo = thePolygon( anEdgeIt + 1 );
1728 anEdges[anEdgeIt] = Abs( anEdgeInfo );
1729 anEdgesOri[anEdgeIt] = ( anEdgeInfo > 0 );
1732 const BRepMesh_Edge& anEdge1 = GetEdge( anEdges[0] );
1733 const BRepMesh_Edge& anEdge2 = GetEdge( anEdges[1] );
1735 Standard_Integer aNodes[3] = { anEdge1.FirstNode(),
1737 anEdge2.FirstNode() };
1738 if ( aNodes[2] == aNodes[0] ||
1739 aNodes[2] == aNodes[1] )
1741 aNodes[2] = anEdge2.LastNode();
1744 addTriangle( anEdges, anEdgesOri, aNodes );
1745 return Standard_True;
1748 //=======================================================================
1749 //function : meshSimplePolygon
1750 //purpose : Triangulatiion of a closed simple polygon (polygon without
1751 // glued edges and loops) described by the list of indexes of
1752 // its edges in the structure.
1753 // (negative index means reversed edge)
1754 //=======================================================================
1755 void BRepMesh_Delaun::meshSimplePolygon( TColStd_SequenceOfInteger& thePolygon,
1756 NCollection_Sequence<Bnd_B2d>& thePolyBoxes )
1758 // Check is the given polygon elementary
1759 if ( meshElementaryPolygon( thePolygon ) )
1763 // Polygon contains more than 3 links
1764 Standard_Integer aFirstEdgeInfo = thePolygon(1);
1765 const BRepMesh_Edge& aFirstEdge = GetEdge( Abs( aFirstEdgeInfo ) );
1767 Standard_Integer aNodes[3];
1768 getOrientedNodes( aFirstEdge, aFirstEdgeInfo > 0, aNodes );
1770 gp_Pnt2d aRefVertices[3];
1771 aRefVertices[0] = GetVertex( aNodes[0] ).Coord();
1772 aRefVertices[1] = GetVertex( aNodes[1] ).Coord();
1774 gp_Vec2d aRefEdgeDir( aRefVertices[0], aRefVertices[1] );
1776 Standard_Real aRefEdgeLen = aRefEdgeDir.Magnitude();
1777 if ( aRefEdgeLen < Precision )
1780 aRefEdgeDir /= aRefEdgeLen;
1782 // Find a point with minimum distance respect
1783 // the end of reference link
1784 Standard_Integer aUsedLinkId = 0;
1785 Standard_Real aOptAngle = 0.0;
1786 Standard_Real aMinDist = RealLast();
1787 Standard_Integer aPivotNode = aNodes[1];
1788 Standard_Integer aPolyLen = thePolygon.Length();
1789 for ( Standard_Integer aLinkIt = 3; aLinkIt <= aPolyLen; ++aLinkIt )
1791 Standard_Integer aLinkInfo = thePolygon( aLinkIt );
1792 const BRepMesh_Edge& aNextEdge = GetEdge( Abs( aLinkInfo ) );
1794 aPivotNode = aLinkInfo > 0 ?
1795 aNextEdge.FirstNode() :
1796 aNextEdge.LastNode();
1798 gp_Pnt2d aPivotVertex = GetVertex( aPivotNode ).Coord();
1799 gp_Vec2d aDistanceDir( aRefVertices[1], aPivotVertex );
1801 Standard_Real aDist = aRefEdgeDir ^ aDistanceDir;
1802 Standard_Real aAngle = Abs( aRefEdgeDir.Angle(aDistanceDir) );
1803 Standard_Real anAbsDist = Abs( aDist );
1804 if ( ( anAbsDist < Precision ) ||
1805 ( myIsPositiveOrientation && aDist < 0. ) ||
1806 (!myIsPositiveOrientation && aDist > 0. ) )
1811 if ( ( anAbsDist >= aMinDist ) &&
1812 ( aAngle <= aOptAngle || aAngle > AngDeviation90Deg ) )
1817 // Check is the test link crosses the polygon boudaries
1818 Standard_Boolean isIntersect = Standard_False;
1819 for ( Standard_Integer aRefLinkNodeIt = 0; aRefLinkNodeIt < 2; ++aRefLinkNodeIt )
1821 const Standard_Integer& aLinkFirstNode = aNodes[aRefLinkNodeIt];
1822 const gp_Pnt2d& aLinkFirstVertex = aRefVertices[aRefLinkNodeIt];
1825 aBox.Add( aLinkFirstVertex );
1826 aBox.Add( aPivotVertex );
1828 BRepMesh_Edge aCheckLink( aLinkFirstNode, aPivotNode, BRepMesh_Free );
1830 Standard_Integer aCheckLinkIt = 2;
1831 for ( ; aCheckLinkIt <= aPolyLen; ++aCheckLinkIt )
1833 if( aCheckLinkIt == aLinkIt )
1836 if ( !aBox.IsOut( thePolyBoxes.Value( aCheckLinkIt ) ) )
1838 const BRepMesh_Edge& aPolyLink =
1839 GetEdge( Abs( thePolygon( aCheckLinkIt ) ) );
1841 if ( aCheckLink.IsEqual( aPolyLink ) )
1844 // intersection is possible...
1846 BRepMesh_WireInterferenceChecker::IntFlag aIntFlag =
1847 intSegSeg( aCheckLink, aPolyLink, Standard_False,
1848 Standard_False, anIntPnt );
1850 if( aIntFlag != BRepMesh_WireInterferenceChecker::NoIntersection )
1852 isIntersect = Standard_True;
1867 aMinDist = anAbsDist;
1868 aNodes[2] = aPivotNode;
1869 aRefVertices[2] = aPivotVertex;
1870 aUsedLinkId = aLinkIt;
1873 if ( aUsedLinkId == 0 )
1877 BRepMesh_Edge aNewEdges[2] = {
1878 BRepMesh_Edge( aNodes[1], aNodes[2], BRepMesh_Free ),
1879 BRepMesh_Edge( aNodes[2], aNodes[0], BRepMesh_Free ) };
1881 Standard_Integer aNewEdgesInfo[3] = {
1883 myMeshData->AddLink( aNewEdges[0] ),
1884 myMeshData->AddLink( aNewEdges[1] ) };
1887 Standard_Integer anEdges[3];
1888 Standard_Boolean anEdgesOri[3];
1889 for ( Standard_Integer aTriEdgeIt = 0; aTriEdgeIt < 3; ++aTriEdgeIt )
1891 const Standard_Integer& anEdgeInfo = aNewEdgesInfo[aTriEdgeIt];
1892 anEdges[aTriEdgeIt] = Abs( anEdgeInfo );
1893 anEdgesOri[aTriEdgeIt] = anEdgeInfo > 0;
1895 addTriangle( anEdges, anEdgesOri, aNodes );
1897 // Create triangle and split the source polygon on two
1898 // parts (if possible) and mesh each part as independent
1900 if ( aUsedLinkId < aPolyLen )
1902 TColStd_SequenceOfInteger aRightPolygon;
1903 thePolygon.Split( aUsedLinkId, aRightPolygon );
1904 aRightPolygon.Prepend( -aNewEdgesInfo[2] );
1906 NCollection_Sequence<Bnd_B2d> aRightPolyBoxes;
1907 thePolyBoxes.Split( aUsedLinkId, aRightPolyBoxes );
1910 aBox.Add( aRefVertices[0] );
1911 aBox.Add( aRefVertices[2] );
1912 aRightPolyBoxes.Prepend( aBox );
1914 meshSimplePolygon( aRightPolygon, aRightPolyBoxes );
1918 thePolygon.Remove ( aPolyLen );
1919 thePolyBoxes.Remove( aPolyLen );
1922 if ( aUsedLinkId > 3 )
1924 thePolygon.SetValue( 1, -aNewEdgesInfo[1] );
1927 aBox.Add( aRefVertices[1] );
1928 aBox.Add( aRefVertices[2] );
1930 thePolyBoxes.SetValue( 1, aBox );
1932 meshSimplePolygon( thePolygon, thePolyBoxes );
1936 //=======================================================================
1937 //function : RemoveVertex
1938 //purpose : Removes a vertex from the triangulation
1939 //=======================================================================
1940 void BRepMesh_Delaun::RemoveVertex( const BRepMesh_Vertex& theVertex )
1942 BRepMesh_SelectorOfDataStructureOfDelaun aSelector( myMeshData );
1943 aSelector.NeighboursOf( theVertex );
1945 BRepMesh_MapOfIntegerInteger aLoopEdges( 10, myMeshData->Allocator() );
1947 // Loop on triangles to be destroyed :
1948 BRepMesh_MapOfInteger::Iterator aTriangleIt( aSelector.Elements() );
1949 for ( ; aTriangleIt.More(); aTriangleIt.Next() )
1950 deleteTriangle( aTriangleIt.Key(), aLoopEdges );
1952 NCollection_Sequence<Bnd_B2d> aBoxes;
1953 TColStd_SequenceOfInteger aPolygon;
1954 Standard_Integer aLoopEdgesCount = aLoopEdges.Extent();
1955 BRepMesh_MapOfIntegerInteger::Iterator aLoopEdgesIt( aLoopEdges );
1957 if ( aLoopEdgesIt.More() )
1959 const BRepMesh_Edge& anEdge = GetEdge( aLoopEdgesIt.Key() );
1960 Standard_Integer aFirstNode = anEdge.FirstNode();
1961 Standard_Integer aLastNode;
1962 Standard_Integer aPivotNode = anEdge.LastNode();
1963 Standard_Integer anEdgeId = aLoopEdgesIt.Key();
1965 Standard_Boolean isPositive = (Standard_Boolean)aLoopEdges( anEdgeId );
1968 Standard_Integer aTmp;
1970 aFirstNode = aPivotNode;
1973 aPolygon.Append( -anEdgeId );
1976 aPolygon.Append( anEdgeId );
1978 fillBndBox( aBoxes, GetVertex( aFirstNode ), GetVertex( aPivotNode ) );
1980 aLoopEdges.UnBind( anEdgeId );
1982 aLastNode = aFirstNode;
1983 while ( aPivotNode != aLastNode )
1985 BRepMesh_ListOfInteger::Iterator aLinkIt( myMeshData->LinkNeighboursOf( aPivotNode ) );
1986 for ( ; aLinkIt.More(); aLinkIt.Next() )
1988 if ( aLinkIt.Value() != anEdgeId &&
1989 aLoopEdges.IsBound( aLinkIt.Value() ) )
1991 Standard_Integer aCurrentNode;
1992 anEdgeId = aLinkIt.Value();
1993 const BRepMesh_Edge& anEdge1 = GetEdge( anEdgeId );
1995 aCurrentNode = anEdge1.LastNode();
1996 if ( aCurrentNode != aPivotNode )
1998 aCurrentNode = anEdge1.FirstNode();
1999 aPolygon.Append( -anEdgeId );
2002 aPolygon.Append( anEdgeId );
2004 fillBndBox( aBoxes, GetVertex( aCurrentNode ), GetVertex( aPivotNode ) );
2006 aPivotNode = aCurrentNode;
2007 aLoopEdges.UnBind( anEdgeId );
2012 if ( aLoopEdgesCount <= 0 )
2017 meshPolygon( aPolygon, aBoxes );
2022 //=======================================================================
2023 //function : AddVertices
2024 //purpose : Adds some vertices in the triangulation.
2025 //=======================================================================
2026 void BRepMesh_Delaun::AddVertices( BRepMesh_Array1OfVertexOfDelaun& theVertices )
2028 BRepMesh_HeapSortVertexOfDelaun::Sort( theVertices,
2029 BRepMesh_ComparatorOfVertexOfDelaun( SortingDirection ) );
2031 Standard_Integer aLower = theVertices.Lower();
2032 Standard_Integer anUpper = theVertices.Upper();
2034 TColStd_Array1OfInteger aVertexIndexes( aLower, anUpper );
2035 for ( Standard_Integer i = aLower; i <= anUpper; ++i )
2036 aVertexIndexes(i) = myMeshData->AddNode( theVertices(i) );
2038 createTrianglesOnNewVertices( aVertexIndexes );
2041 //=======================================================================
2042 //function : UseEdge
2043 //purpose : Modify mesh to use the edge. Return True if done
2044 //=======================================================================
2045 Standard_Boolean BRepMesh_Delaun::UseEdge( const Standard_Integer /*theIndex*/ )
2048 const BRepMesh_PairOfIndex& aPair = myMeshData->ElemConnectedTo( theIndex );
2049 if ( aPair.Extent() == 0 )
2051 const BRepMesh_Edge& anEdge = GetEdge( theIndex );
2053 Standard_Integer aStartNode, aPivotNode, anOtherNode;
2054 aStartNode = anEdge.FirstNode();
2055 aPivotNode = anEdge.LastNode();
2057 const BRepMesh_ListOfInteger& aStartNodeNeighbors = myMeshData->LinkNeighboursOf( aStartNode );
2058 const BRepMesh_ListOfInteger& aPivotNodeNeighbors = myMeshData->LinkNeighboursOf( aPivotNode );
2060 if ( aStartNodeNeighbors.Extent() > 0 &&
2061 aPivotNodeNeighbors.Extent() > 0 )
2063 const BRepMesh_Vertex& aStartVertex = GetVertex( aStartNode );
2064 const BRepMesh_Vertex& aPivotVertex = GetVertex( aPivotNode );
2066 gp_XY aVEdge ( aPivotVertex.Coord() );
2067 aVEdge.Subtract( aStartVertex.Coord() );
2069 Standard_Real anAngle = 0.;
2070 Standard_Real anAngleMin = RealLast();
2071 Standard_Real anAngleMax = RealFirst();
2072 Standard_Integer aLeftEdge = 0, aRightEdge = 0;
2074 BRepMesh_ListOfInteger::Iterator aNeighborIt( aPivotNodeNeighbors );
2075 for ( ; aNeighborIt.More(); aNeighborIt.Next() )
2077 Standard_Integer anEdgeId = aNeighborIt.Value();
2078 if ( anEdgeId != theIndex )
2080 const BRepMesh_Edge& aNextEdge = GetEdge( anEdgeId );
2082 Standard_Boolean isInMesh = Standard_True;
2083 if ( aNextEdge.Movability() == BRepMesh_Free )
2085 if ( myMeshData->ElemConnectedTo( anEdgeId ).IsEmpty() )
2086 isInMesh = Standard_False;
2091 anOtherNode = aNextEdge.FirstNode();
2092 if ( anOtherNode == aPivotNode )
2093 anOtherNode = aNextEdge.LastNode();
2095 gp_XY aVEdgeCur = GetVertex( anOtherNode ).Coord();
2096 aVEdgeCur.Subtract( aPivotVertex.Coord() );
2098 anAngle = gp_Vec2d( aVEdge ).Angle( gp_Vec2d( aVEdgeCur ) );
2101 if ( anAngle > anAngleMax )
2103 anAngleMax = anAngle;
2104 aLeftEdge = anEdgeId;
2106 if ( anAngle < anAngleMin )
2108 anAngleMin = anAngle;
2109 aRightEdge = anEdgeId;
2114 if ( aLeftEdge > 0 )
2116 if (aLeftEdge==aRightEdge)
2126 return Standard_False;
2129 //=======================================================================
2130 //function : getEdgesByType
2131 //purpose : Gives the list of edges with type defined by input parameter
2132 //=======================================================================
2133 Handle(BRepMesh_MapOfInteger) BRepMesh_Delaun::getEdgesByType(
2134 const BRepMesh_DegreeOfFreedom theEdgeType ) const
2136 Handle(BRepMesh_MapOfInteger) aResult = new BRepMesh_MapOfInteger;
2137 BRepMesh_MapOfInteger::Iterator anEdgeIt( myMeshData->LinkOfDomain() );
2139 for ( ; anEdgeIt.More(); anEdgeIt.Next() )
2141 Standard_Integer anEdge = anEdgeIt.Key();
2142 Standard_Boolean isToAdd = (theEdgeType == BRepMesh_Free) ?
2143 (myMeshData->ElemConnectedTo( anEdge ).Extent() <= 1) :
2144 (GetEdge( anEdge ).Movability() == theEdgeType);
2147 aResult->Add( anEdge );
2153 //=======================================================================
2154 //function : calculateDist
2155 //purpose : Calculates distances between the given point and edges of
2157 //=======================================================================
2158 Standard_Real BRepMesh_Delaun::calculateDist( const gp_XY theVEdges[3],
2159 const gp_XY thePoints[3],
2160 const Standard_Integer theEdgesId[3],
2161 const BRepMesh_Vertex& theVertex,
2162 Standard_Real theDistance[3],
2163 Standard_Real theSqModulus[3],
2164 Standard_Integer& theEdgeOn ) const
2166 Standard_Real aMinDist = -1;
2167 if ( !theVEdges || !thePoints || !theEdgesId ||
2168 !theDistance || !theSqModulus )
2171 for( Standard_Integer i = 0; i < 3; ++i )
2173 theSqModulus[i] = theVEdges[i].SquareModulus();
2174 if ( theSqModulus[i] <= Precision2 )
2177 theDistance[i] = theVEdges[i] ^ ( theVertex.Coord() - thePoints[i] );
2179 Standard_Real aDist = theDistance[i] * theDistance[i];
2180 aDist /= theSqModulus[i];
2182 if ( aMinDist < 0 || aDist < aMinDist )
2184 theEdgeOn = theEdgesId[i];
2192 //=======================================================================
2193 //function : Contains
2194 //purpose : Test if triangle of index <TrianIndex> contains geometricaly
2195 // <theVertex>. If <theEdgeOn> is != 0 then theVertex is on Edge
2196 // of index <theEdgeOn>
2197 //=======================================================================
2198 Standard_Boolean BRepMesh_Delaun::Contains( const Standard_Integer theTriangleId,
2199 const BRepMesh_Vertex& theVertex,
2200 Standard_Integer& theEdgeOn ) const
2204 Standard_Integer e[3];
2205 Standard_Boolean o[3];
2206 Standard_Integer p[3];
2208 GetTriangle( theTriangleId ).Edges( e[0], e[1], e[2],
2211 const BRepMesh_Edge* anEdges[3] = { &GetEdge( e[0] ),
2216 p[0] = anEdges[0]->FirstNode();
2217 p[1] = anEdges[0]->LastNode();
2221 p[1] = anEdges[0]->FirstNode();
2222 p[0] = anEdges[0]->LastNode();
2226 p[2] = anEdges[2]->FirstNode();
2228 p[2] = anEdges[2]->LastNode();
2231 aPoints[0] = GetVertex( p[0] ).Coord();
2232 aPoints[1] = GetVertex( p[1] ).Coord();
2233 aPoints[2] = GetVertex( p[2] ).Coord();
2236 aVEdges[0] = aPoints[1];
2237 aVEdges[0].Subtract( aPoints[0] );
2239 aVEdges[1] = aPoints[2];
2240 aVEdges[1].Subtract( aPoints[1] );
2242 aVEdges[2] = aPoints[0];
2243 aVEdges[2].Subtract( aPoints[2] );
2245 Standard_Real aDistance[3];
2246 Standard_Real aSqModulus[3];
2248 Standard_Real aMinDist;
2249 aMinDist = calculateDist( aVEdges, aPoints, e, theVertex, aDistance, aSqModulus, theEdgeOn );
2251 return Standard_False;
2253 if ( aMinDist > Precision2 )
2255 Standard_Integer anEdgeId = theEdgeOn;
2258 if ( anEdgeId != 0 )
2260 Standard_Integer i = 0;
2261 for ( ; i < 3; ++i )
2263 if( e[i] == anEdgeId )
2267 if( anEdges[i]->Movability() != BRepMesh_Free )
2268 if ( aDistance[i] < ( aSqModulus[i] / 5. ) )
2273 return ( aDistance[0] + aDistance[1] + aDistance[2] != 0. &&
2274 ( ( aDistance[0] >= 0. && aDistance[1] >= 0. && aDistance[2] >= 0. ) ||
2275 ( aDistance[0] <= 0. && aDistance[1] <= 0. && aDistance[2] <= 0. ) ) );
2278 //=============================================================================
2279 //function : intSegSeg
2280 //purpose : Checks intersection between the two segments.
2281 //=============================================================================
2282 BRepMesh_WireInterferenceChecker::IntFlag BRepMesh_Delaun::intSegSeg(
2283 const BRepMesh_Edge& theEdg1,
2284 const BRepMesh_Edge& theEdg2,
2285 const Standard_Boolean isConsiderEndPointTouch,
2286 const Standard_Boolean isConsiderPointOnEdge,
2287 gp_Pnt2d& theIntPnt) const
2289 gp_XY p1, p2, p3, p4;
2290 p1 = GetVertex( theEdg1.FirstNode() ).Coord();
2291 p2 = GetVertex( theEdg1.LastNode() ).Coord();
2292 p3 = GetVertex( theEdg2.FirstNode() ).Coord();
2293 p4 = GetVertex( theEdg2.LastNode() ).Coord();
2295 return BRepMesh_WireInterferenceChecker::Intersect(p1, p2, p3, p4,
2296 isConsiderEndPointTouch, isConsiderPointOnEdge, theIntPnt);
2299 //=============================================================================
2300 //function : polyArea
2301 //purpose : Returns area of the loop of the given polygon defined by indices
2302 // of its start and end links.
2303 //=============================================================================
2304 Standard_Real BRepMesh_Delaun::polyArea( const TColStd_SequenceOfInteger& thePolygon,
2305 const Standard_Integer theStartIndex,
2306 const Standard_Integer theEndIndex ) const
2308 Standard_Real aArea = 0.0;
2309 Standard_Integer aPolyLen = thePolygon.Length();
2310 if ( theStartIndex >= theEndIndex ||
2311 theStartIndex > aPolyLen )
2315 Standard_Integer aCurEdgeInfo = thePolygon( theStartIndex );
2316 Standard_Integer aCurEdgeId = Abs( aCurEdgeInfo );
2317 const BRepMesh_Edge* aCurEdge = &GetEdge( aCurEdgeId );
2319 Standard_Integer aNodes[2];
2320 getOrientedNodes( *aCurEdge, aCurEdgeInfo > 0, aNodes );
2322 gp_Pnt2d aRefPnt = GetVertex( aNodes[0] ).Coord();
2323 Standard_Integer aPolyIt = theStartIndex + 1;
2324 for ( ; aPolyIt <= theEndIndex; ++aPolyIt )
2326 aCurEdgeInfo = thePolygon( aPolyIt );
2327 aCurEdgeId = Abs( aCurEdgeInfo );
2328 aCurEdge = &GetEdge( aCurEdgeId );
2330 getOrientedNodes( *aCurEdge, aCurEdgeInfo > 0, aNodes );
2331 gp_Vec2d aVec1( aRefPnt, GetVertex( aNodes[0] ).Coord() );
2332 gp_Vec2d aVec2( aRefPnt, GetVertex( aNodes[1] ).Coord() );
2334 aArea += aVec1 ^ aVec2;