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 <BRepMesh_SelectorOfDataStructureOfDelaun.hxx>
30 #include <BRepMesh_Edge.hxx>
31 #include <BRepMesh_Vertex.hxx>
32 #include <BRepMesh_Triangle.hxx>
34 #include <NCollection_Vector.hxx>
38 const Standard_Real AngDeviation1Deg = M_PI/180.;
39 const Standard_Real AngDeviation90Deg = 90 * AngDeviation1Deg;
40 const Standard_Real Angle2PI = 2 * M_PI;
42 const Standard_Real Precision = Precision::PConfusion();
43 const Standard_Real Precision2 = Precision * Precision;
46 //! Sort two points in projection on vector (1,1)
47 struct ComparatorOfVertexOfDelaun
49 bool operator() (const BRepMesh_Vertex& theLeft, const BRepMesh_Vertex& theRight)
51 return theLeft.Coord().X() + theLeft.Coord().Y() < theRight.Coord().X() + theRight.Coord().Y();
55 //! Sort two points in projection on vector (1,1)
56 struct ComparatorOfIndexedVertexOfDelaun
59 ComparatorOfIndexedVertexOfDelaun (const Handle(BRepMesh_DataStructureOfDelaun)& theDS)
60 : myStructure(theDS) {}
62 bool operator() (Standard_Integer theLeft, Standard_Integer theRight)
64 const BRepMesh_Vertex& aLeft = myStructure->GetNode(theLeft);
65 const BRepMesh_Vertex& aRight = myStructure->GetNode(theRight);
66 return ComparatorOfVertexOfDelaun() (aLeft, aRight);
70 Handle(BRepMesh_DataStructureOfDelaun) myStructure;
72 } // anonymous namespace
74 //=======================================================================
75 //function : BRepMesh_Delaun
76 //purpose : Creates the triangulation with an empty Mesh data structure
77 //=======================================================================
78 BRepMesh_Delaun::BRepMesh_Delaun(
79 BRepMesh::Array1OfVertexOfDelaun& theVertices)
80 : myCircles(theVertices.Length(), new NCollection_IncAllocator(
81 BRepMesh::MEMORY_BLOCK_SIZE_HUGE))
83 if ( theVertices.Length() > 2 )
85 myMeshData = new BRepMesh_DataStructureOfDelaun(
86 new NCollection_IncAllocator(BRepMesh::MEMORY_BLOCK_SIZE_HUGE),
87 theVertices.Length() );
92 //=======================================================================
93 //function : BRepMesh_Delaun
94 //purpose : Creates the triangulation with and existent Mesh data structure
95 //=======================================================================
96 BRepMesh_Delaun::BRepMesh_Delaun(
97 const Handle( BRepMesh_DataStructureOfDelaun )& theOldMesh,
98 BRepMesh::Array1OfVertexOfDelaun& theVertices)
99 : myCircles( theVertices.Length(), theOldMesh->Allocator() )
101 myMeshData = theOldMesh;
102 if ( theVertices.Length() > 2 )
106 //=======================================================================
107 //function : BRepMesh_Delaun
108 //purpose : Creates the triangulation with and existent Mesh data structure
109 //=======================================================================
110 BRepMesh_Delaun::BRepMesh_Delaun(
111 const Handle( BRepMesh_DataStructureOfDelaun )& theOldMesh,
112 BRepMesh::Array1OfInteger& theVertexIndices)
113 : myCircles( theVertexIndices.Length(), theOldMesh->Allocator() )
115 myMeshData = theOldMesh;
116 if ( theVertexIndices.Length() > 2 )
119 Standard_Integer anIndex = theVertexIndices.Lower();
120 Standard_Integer anUpper = theVertexIndices.Upper();
121 for ( ; anIndex <= anUpper; ++anIndex )
122 aBox.Add( gp_Pnt2d( GetVertex( theVertexIndices( anIndex) ).Coord() ) );
124 perform( aBox, theVertexIndices );
128 //=======================================================================
130 //purpose : Initializes the triangulation with an Array of Vertex
131 //=======================================================================
132 void BRepMesh_Delaun::Init(BRepMesh::Array1OfVertexOfDelaun& theVertices)
135 Standard_Integer aLowerIdx = theVertices.Lower();
136 Standard_Integer anUpperIdx = theVertices.Upper();
137 BRepMesh::Array1OfInteger aVertexIndexes( aLowerIdx, anUpperIdx );
139 Standard_Integer anIndex = aLowerIdx;
140 for ( ; anIndex <= anUpperIdx; ++anIndex )
142 aBox.Add( gp_Pnt2d( theVertices( anIndex ).Coord() ) );
143 aVertexIndexes( anIndex ) = myMeshData->AddNode( theVertices( anIndex ) );
146 perform( aBox, aVertexIndexes );
149 //=======================================================================
151 //purpose : Create super mesh and run triangulation procedure
152 //=======================================================================
153 void BRepMesh_Delaun::perform(Bnd_Box2d& theBndBox,
154 BRepMesh::Array1OfInteger& theVertexIndexes)
156 theBndBox.Enlarge( Precision );
157 superMesh( theBndBox );
159 ComparatorOfIndexedVertexOfDelaun aCmp(myMeshData);
160 std::make_heap(theVertexIndexes.begin(), theVertexIndexes.end(), aCmp);
161 std::sort_heap(theVertexIndexes.begin(), theVertexIndexes.end(), aCmp);
163 compute( theVertexIndexes );
166 //=======================================================================
167 //function : superMesh
168 //purpose : Build the super mesh
169 //=======================================================================
170 void BRepMesh_Delaun::superMesh( const Bnd_Box2d& theBox )
172 Standard_Real aMinX, aMinY, aMaxX, aMaxY;
173 theBox.Get( aMinX, aMinY, aMaxX, aMaxY );
174 Standard_Real aDeltaX = aMaxX - aMinX;
175 Standard_Real aDeltaY = aMaxY - aMinY;
177 Standard_Real aDeltaMin = Min( aDeltaX, aDeltaY );
178 Standard_Real aDeltaMax = Max( aDeltaX, aDeltaY );
179 Standard_Real aDelta = aDeltaX + aDeltaY;
181 myCircles.SetMinMaxSize( gp_XY( aMinX, aMinY ), gp_XY( aMaxX, aMaxY ) );
183 Standard_Integer aScaler = 2;
184 if ( myMeshData->NbNodes() > 100 )
186 else if( myMeshData->NbNodes() > 1000 )
189 myCircles.SetCellSize( aDeltaX / aScaler,
192 mySupVert[0] = myMeshData->AddNode(
193 BRepMesh_Vertex( ( aMinX + aMaxX ) / 2, aMaxY + aDeltaMax, BRepMesh_Free ) );
195 mySupVert[1] = myMeshData->AddNode(
196 BRepMesh_Vertex( aMinX - aDelta, aMinY - aDeltaMin, BRepMesh_Free ) );
198 mySupVert[2] = myMeshData->AddNode(
199 BRepMesh_Vertex( aMaxX + aDelta, aMinY - aDeltaMin, BRepMesh_Free ) );
201 Standard_Integer e[3];
202 Standard_Boolean o[3];
203 for (Standard_Integer aNodeId = 0; aNodeId < 3; ++aNodeId)
205 Standard_Integer aFirstNode = aNodeId;
206 Standard_Integer aLastNode = (aNodeId + 1) % 3;
207 Standard_Integer aLinkIndex = myMeshData->AddLink( BRepMesh_Edge(
208 mySupVert[aFirstNode], mySupVert[aLastNode], BRepMesh_Free ) );
210 e[aNodeId] = Abs(aLinkIndex);
211 o[aNodeId] = (aLinkIndex > 0);
214 mySupTrian = BRepMesh_Triangle(e, o, BRepMesh_Free);
217 //=======================================================================
218 //function : deleteTriangle
219 //purpose : Deletes the triangle with the given index and adds the free
220 // edges into the map.
221 // When an edge is suppressed more than one time it is destroyed.
222 //=======================================================================
223 void BRepMesh_Delaun::deleteTriangle(const Standard_Integer theIndex,
224 BRepMesh::MapOfIntegerInteger& theLoopEdges )
226 myCircles.Delete( theIndex );
228 Standard_Integer e[3];
229 Standard_Boolean o[3];
230 GetTriangle( theIndex ).Edges( e, o );
232 myMeshData->RemoveElement( theIndex );
234 for ( Standard_Integer i = 0; i < 3; ++i )
236 if ( !theLoopEdges.Bind( e[i], o[i] ) )
238 theLoopEdges.UnBind( e[i] );
239 myMeshData->RemoveLink( e[i] );
244 //=======================================================================
246 //purpose : Computes the triangulation and add the vertices edges and
247 // triangles to the Mesh data structure
248 //=======================================================================
249 void BRepMesh_Delaun::compute(BRepMesh::Array1OfInteger& theVertexIndexes)
251 // Insertion of edges of super triangles in the list of free edges:
252 BRepMesh::MapOfIntegerInteger aLoopEdges(10, myMeshData->Allocator());
253 Standard_Integer e[3];
254 Standard_Boolean o[3];
255 mySupTrian.Edges( e, o );
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->ElementsConnectedTo( 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 BRepMesh::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 BRepMesh_Edge aFirstLink( aNodes[1], aNodes[0], BRepMesh_Free );
349 BRepMesh_Edge aLastLink ( aNodes[2], aNodes[1], BRepMesh_Free );
351 Standard_Integer anEdgesInfo[3] = {
352 myMeshData->AddLink( aFirstLink ),
353 isPositive ? anEdgeId : -anEdgeId,
354 myMeshData->AddLink( aLastLink ) };
356 Standard_Boolean isSensOK = (aDist12 > 0. && aDist23 > 0.);
359 Standard_Integer anEdges[3];
360 Standard_Boolean anEdgesOri[3];
361 for ( Standard_Integer aTriLinkIt = 0; aTriLinkIt < 3; ++aTriLinkIt )
363 const Standard_Integer& anEdgeInfo = anEdgesInfo[aTriLinkIt];
364 anEdges[aTriLinkIt] = Abs( anEdgeInfo );
365 anEdgesOri[aTriLinkIt] = anEdgeInfo > 0;
368 addTriangle( anEdges, anEdgesOri, aNodes );
373 aLoopEdges.Append( anEdges.Key() );
375 aLoopEdges.Append( -anEdges.Key() );
377 if ( aFirstLinkDir.SquareModulus() > aLastLinkDir.SquareModulus() )
378 anExternalEdges.Append( Abs( anEdgesInfo[0] ) );
380 anExternalEdges.Append( Abs( anEdgesInfo[2] ) );
385 while ( !anExternalEdges.IsEmpty() )
387 const BRepMesh_PairOfIndex& aPair =
388 myMeshData->ElementsConnectedTo( Abs( anExternalEdges.First() ) );
391 if ( !aPair.IsEmpty() )
392 deleteTriangle( aPair.FirstIndex(), thePoly );
394 anExternalEdges.RemoveFirst();
397 for ( anEdges.Initialize( thePoly ); anEdges.More(); anEdges.Next() )
399 if ( myMeshData->ElementsConnectedTo( anEdges.Key() ).IsEmpty() )
400 myMeshData->RemoveLink( anEdges.Key() );
403 while ( !aLoopEdges.IsEmpty() )
405 const BRepMesh_Edge& anEdge = GetEdge( Abs( aLoopEdges.First() ) );
406 if ( anEdge.Movability() != BRepMesh_Deleted )
408 Standard_Integer anEdgeIdx = aLoopEdges.First();
409 meshLeftPolygonOf( Abs( anEdgeIdx ), ( anEdgeIdx > 0 ) );
412 aLoopEdges.RemoveFirst();
416 //=======================================================================
417 //function : createTrianglesOnNewVertices
418 //purpose : Creation of triangles from the new nodes
419 //=======================================================================
420 void BRepMesh_Delaun::createTrianglesOnNewVertices(
421 BRepMesh::Array1OfInteger& theVertexIndexes)
423 Handle(NCollection_IncAllocator) aAllocator =
424 new NCollection_IncAllocator(BRepMesh::MEMORY_BLOCK_SIZE_HUGE);
426 BRepMesh::MapOfIntegerInteger aLoopEdges(10, aAllocator);
428 // Insertion of nodes :
429 Standard_Boolean isModify = Standard_True;
431 Standard_Integer anIndex = theVertexIndexes.Lower();
432 Standard_Integer anUpper = theVertexIndexes.Upper();
433 for( ; anIndex <= anUpper; ++anIndex )
436 aAllocator->Reset(Standard_False);
438 Standard_Integer aVertexIdx = theVertexIndexes( anIndex );
439 const BRepMesh_Vertex& aVertex = GetVertex( aVertexIdx );
441 // Iterator in the list of indexes of circles containing the node
442 BRepMesh::ListOfInteger& aCirclesList = myCircles.Select( aVertex.Coord() );
444 Standard_Integer onEgdeId = 0, aTriangleId = 0;
445 BRepMesh::ListOfInteger::Iterator aCircleIt( aCirclesList );
446 for ( ; aCircleIt.More(); aCircleIt.Next() )
448 // To add a node in the mesh it is necessary to check conditions:
449 // - the node should be within the boundaries of the mesh and so in an existing triangle
450 // - all adjacent triangles should belong to a component connected with this triangle
451 if ( Contains( aCircleIt.Value(), aVertex, onEgdeId ) )
455 aTriangleId = aCircleIt.Value();
456 aCirclesList.Remove( aCircleIt );
459 else if ( GetEdge( onEgdeId ).Movability() == BRepMesh_Free )
461 aTriangleId = aCircleIt.Value();
462 aCirclesList.Remove( aCircleIt );
468 if ( aTriangleId > 0 )
470 deleteTriangle( aTriangleId, aLoopEdges );
472 isModify = Standard_True;
473 while ( isModify && !aCirclesList.IsEmpty() )
475 isModify = Standard_False;
476 BRepMesh::ListOfInteger::Iterator aCircleIt1( aCirclesList );
477 for ( ; aCircleIt1.More(); aCircleIt1.Next() )
479 Standard_Integer e[3];
480 Standard_Boolean o[3];
481 GetTriangle( aCircleIt1.Value() ).Edges( e, o );
483 if ( aLoopEdges.IsBound( e[0] ) ||
484 aLoopEdges.IsBound( e[1] ) ||
485 aLoopEdges.IsBound( e[2] ) )
487 isModify = Standard_True;
488 deleteTriangle( aCircleIt1.Value(), aLoopEdges );
489 aCirclesList.Remove( aCircleIt1 );
495 // Creation of triangles with the current node and free edges
496 // and removal of these edges from the list of free edges
497 createTriangles( aVertexIdx, aLoopEdges );
500 // Check that internal edges are not crossed by triangles
501 BRepMesh::HMapOfInteger anInternalEdges = InternalEdges();
503 // Destruction of triancles intersecting internal edges
504 // and their replacement by makeshift triangles
505 BRepMesh::MapOfInteger::Iterator anInernalEdgesIt( *anInternalEdges );
506 for ( ; anInernalEdgesIt.More(); anInernalEdgesIt.Next() )
508 Standard_Integer aNbC;
509 aNbC = myMeshData->ElementsConnectedTo( anInernalEdgesIt.Key() ).Extent();
512 meshLeftPolygonOf( anInernalEdgesIt.Key(), Standard_True );
513 meshLeftPolygonOf( anInernalEdgesIt.Key(), Standard_False );
517 // Adjustment of meshes to boundary edges
521 //=======================================================================
522 //function : isBoundToFrontier
523 //purpose : Goes through the neighbour triangles around the given node
524 // started from the given link, returns TRUE if some triangle
525 // has a bounding frontier edge or FALSE elsewhere.
526 // Stop link is used to prevent cycles.
527 // Previous element Id is used to identify next neighbor element.
528 //=======================================================================
529 Standard_Boolean BRepMesh_Delaun::isBoundToFrontier(
530 const Standard_Integer theRefNodeId,
531 const Standard_Integer theRefLinkId,
532 const Standard_Integer theStopLinkId,
533 const Standard_Integer thePrevElementId)
535 const BRepMesh_PairOfIndex& aPair =
536 myMeshData->ElementsConnectedTo( theRefLinkId );
537 if ( aPair.IsEmpty() )
538 return Standard_False;
540 Standard_Integer aNbElements = aPair.Extent();
541 for ( Standard_Integer anElemIt = 1; anElemIt <= aNbElements; ++anElemIt )
543 const Standard_Integer aTriId = aPair.Index(anElemIt);
544 if ( aTriId < 0 || aTriId == thePrevElementId )
547 Standard_Integer anEdges[3];
548 Standard_Boolean anEdgesOri[3];
549 GetTriangle( aTriId ).Edges( anEdges, anEdgesOri );
551 for ( Standard_Integer anEdgeIt = 0; anEdgeIt < 3; ++anEdgeIt )
553 const Standard_Integer anEdgeId = anEdges[anEdgeIt];
554 if ( anEdgeId == theRefLinkId )
557 if ( anEdgeId == theStopLinkId )
558 return Standard_False;
560 const BRepMesh_Edge& anEdge = GetEdge( anEdgeId );
561 if ( anEdge.FirstNode() != theRefNodeId &&
562 anEdge.LastNode() != theRefNodeId )
567 if ( anEdge.Movability() != BRepMesh_Free )
568 return Standard_True;
570 return isBoundToFrontier( theRefNodeId, anEdgeId, theStopLinkId, aTriId );
574 return Standard_False;
577 //=======================================================================
578 //function : cleanupMesh
579 //purpose : Cleanup mesh from the free triangles
580 //=======================================================================
581 void BRepMesh_Delaun::cleanupMesh()
583 Handle(NCollection_IncAllocator) aAllocator =
584 new NCollection_IncAllocator(BRepMesh::MEMORY_BLOCK_SIZE_HUGE);
588 BRepMesh::MapOfIntegerInteger aLoopEdges(10, aAllocator);
589 BRepMesh::MapOfInteger aDelTriangles(10, aAllocator);
591 BRepMesh::HMapOfInteger 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->ElementsConnectedTo( 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, anEdgesOri );
615 Standard_Boolean isCanNotBeRemoved = Standard_True;
616 for ( Standard_Integer aCurEdgeIdx = 0; aCurEdgeIdx < 3; ++aCurEdgeIdx )
618 if ( anEdges[aCurEdgeIdx] != aFreeEdgeId )
621 for ( Standard_Integer anOtherEdgeIt = 1; anOtherEdgeIt <= 2; ++anOtherEdgeIt )
623 Standard_Integer anOtherEdgeId = ( aCurEdgeIdx + anOtherEdgeIt ) % 3;
624 const BRepMesh_PairOfIndex& anOtherEdgePair =
625 myMeshData->ElementsConnectedTo( anEdges[anOtherEdgeId] );
627 if ( anOtherEdgePair.Extent() < 2 )
629 isCanNotBeRemoved = Standard_False;
637 if ( isCanNotBeRemoved )
640 Standard_Boolean isConnected[2] = { Standard_False, Standard_False };
641 for ( Standard_Integer aLinkNodeIt = 0; aLinkNodeIt < 2; ++aLinkNodeIt )
643 isConnected[aLinkNodeIt] = isBoundToFrontier( ( aLinkNodeIt == 0 ) ?
644 anEdge.FirstNode() : anEdge.LastNode(),
645 aFreeEdgeId, aFreeEdgeId, -1);
648 if ( !isConnected[0] || !isConnected[1] )
649 aDelTriangles.Add( aTriId );
652 // Destruction of triangles :
653 Standard_Integer aDeletedTrianglesNb = 0;
654 BRepMesh::MapOfInteger::Iterator aDelTrianglesIt( aDelTriangles );
655 for ( ; aDelTrianglesIt.More(); aDelTrianglesIt.Next() )
657 deleteTriangle( aDelTrianglesIt.Key(), aLoopEdges );
658 aDeletedTrianglesNb++;
661 // Destruction of remaining hanging edges
662 BRepMesh::MapOfIntegerInteger::Iterator aLoopEdgesIt( aLoopEdges );
663 for ( ; aLoopEdgesIt.More(); aLoopEdgesIt.Next() )
665 if ( myMeshData->ElementsConnectedTo( aLoopEdgesIt.Key() ).IsEmpty() )
666 myMeshData->RemoveLink( aLoopEdgesIt.Key() );
669 aAllocator->Reset(Standard_False);
670 if ( aDeletedTrianglesNb == 0 )
675 //=======================================================================
676 //function : frontierAdjust
677 //purpose : Adjust the mesh on the frontier
678 //=======================================================================
679 void BRepMesh_Delaun::frontierAdjust()
681 BRepMesh::HMapOfInteger aFrontier = Frontier();
683 Handle(NCollection_IncAllocator) aAllocator =
684 new NCollection_IncAllocator(BRepMesh::MEMORY_BLOCK_SIZE_HUGE);
686 BRepMesh::VectorOfInteger aFailedFrontiers(256, aAllocator);
687 BRepMesh::MapOfIntegerInteger aLoopEdges(10, aAllocator);
688 BRepMesh::HMapOfInteger aIntFrontierEdges =
689 new BRepMesh::MapOfInteger(10, aAllocator);
691 for ( Standard_Integer aPass = 1; aPass <= 2; ++aPass )
693 // 1 pass): find external triangles on boundary edges;
694 // 2 pass): find external triangles on boundary edges appeared
695 // during triangles replacement.
697 BRepMesh::MapOfInteger::Iterator aFrontierIt( *aFrontier );
698 for ( ; aFrontierIt.More(); aFrontierIt.Next() )
700 Standard_Integer aFrontierId = aFrontierIt.Key();
701 const BRepMesh_PairOfIndex& aPair = myMeshData->ElementsConnectedTo( aFrontierId );
702 Standard_Integer aNbElem = aPair.Extent();
703 for( Standard_Integer aElemIt = 1; aElemIt <= aNbElem; ++aElemIt )
705 const Standard_Integer aPriorElemId = aPair.Index( aElemIt );
706 if( aPriorElemId < 0 )
709 Standard_Integer e[3];
710 Standard_Boolean o[3];
711 GetTriangle( aPriorElemId ).Edges( e, o );
713 Standard_Boolean isTriangleFound = Standard_False;
714 for ( Standard_Integer n = 0; n < 3; ++n )
716 if ( aFrontierId == e[n] && !o[n] )
718 // Destruction of external triangles on boundary edges
719 isTriangleFound = Standard_True;
720 deleteTriangle( aPriorElemId, aLoopEdges );
725 if ( isTriangleFound )
730 // destrucrion of remaining hanging edges :
731 BRepMesh::MapOfIntegerInteger::Iterator aLoopEdgesIt( aLoopEdges );
732 for ( ; aLoopEdgesIt.More(); aLoopEdgesIt.Next() )
734 Standard_Integer aLoopEdgeId = aLoopEdgesIt.Key();
735 if (myMeshData->ElementsConnectedTo( aLoopEdgeId ).IsEmpty() )
736 myMeshData->RemoveLink( aLoopEdgeId );
739 // destruction of triangles crossing the boundary edges and
740 // their replacement by makeshift triangles
741 for ( aFrontierIt.Reset(); aFrontierIt.More(); aFrontierIt.Next() )
743 Standard_Integer aFrontierId = aFrontierIt.Key();
744 if ( !myMeshData->ElementsConnectedTo( aFrontierId ).IsEmpty() )
747 Standard_Boolean isSuccess =
748 meshLeftPolygonOf( aFrontierId, Standard_True, aIntFrontierEdges );
750 if ( aPass == 2 && !isSuccess )
751 aFailedFrontiers.Append( aFrontierId );
757 // When the mesh has been cleaned up, try to process frontier edges
758 // once again to fill the possible gaps that might be occured in case of "saw" -
759 // situation when frontier edge has a triangle at a right side, but its free
760 // links cross another frontieres and meshLeftPolygonOf itself can't collect
762 BRepMesh::VectorOfInteger::Iterator aFailedFrontiersIt( aFailedFrontiers );
763 for ( ; aFailedFrontiersIt.More(); aFailedFrontiersIt.Next() )
765 Standard_Integer aFrontierId = aFailedFrontiersIt.Value();
766 if ( !myMeshData->ElementsConnectedTo( aFrontierId ).IsEmpty() )
769 meshLeftPolygonOf( aFrontierId, Standard_True, aIntFrontierEdges );
773 //=======================================================================
774 //function : fillBndBox
775 //purpose : Add boundig box for edge defined by start & end point to
776 // the given vector of bounding boxes for triangulation edges
777 //=======================================================================
778 void BRepMesh_Delaun::fillBndBox(BRepMesh::SequenceOfBndB2d& theBoxes,
779 const BRepMesh_Vertex& theV1,
780 const BRepMesh_Vertex& theV2)
783 aBox.Add( theV1.Coord() );
784 aBox.Add( theV2.Coord() );
785 theBoxes.Append( aBox );
788 //=======================================================================
789 //function : meshLeftPolygonOf
790 //purpose : Collect the polygon at the left of the given edge (material side)
791 //=======================================================================
792 Standard_Boolean BRepMesh_Delaun::meshLeftPolygonOf(
793 const Standard_Integer theStartEdgeId,
794 const Standard_Boolean isForward,
795 BRepMesh::HMapOfInteger theSkipped )
797 if ( !theSkipped.IsNull() && theSkipped->Contains( theStartEdgeId ) )
798 return Standard_True;
800 const BRepMesh_Edge& aRefEdge = GetEdge( theStartEdgeId );
802 BRepMesh::SequenceOfInteger aPolygon;
803 Standard_Integer aStartNode, aPivotNode;
806 aPolygon.Append( theStartEdgeId );
807 aStartNode = aRefEdge.FirstNode();
808 aPivotNode = aRefEdge.LastNode();
812 aPolygon.Append( -theStartEdgeId );
813 aStartNode = aRefEdge.LastNode();
814 aPivotNode = aRefEdge.FirstNode();
818 const BRepMesh_Vertex& aStartEdgeVertexS = GetVertex( aStartNode );
819 BRepMesh_Vertex aPivotVertex = GetVertex( aPivotNode );
821 gp_Vec2d aRefLinkDir( aPivotVertex.Coord() -
822 aStartEdgeVertexS.Coord() );
824 if ( aRefLinkDir.SquareMagnitude() < Precision2 )
825 return Standard_True;
827 // Auxilary structures.
828 // Bounding boxes of polygon links to be used for preliminary
829 // analysis of intersections
830 BRepMesh::SequenceOfBndB2d aBoxes;
831 fillBndBox( aBoxes, aStartEdgeVertexS, aPivotVertex );
834 BRepMesh::MapOfInteger aDeadLinks;
836 // Links are temporarily excluded from consideration
837 BRepMesh::MapOfInteger aLeprousLinks;
838 aLeprousLinks.Add( theStartEdgeId );
840 Standard_Boolean isSkipLeprous = Standard_True;
841 Standard_Integer aFirstNode = aStartNode;
842 while ( aPivotNode != aFirstNode )
844 Bnd_B2d aNextLinkBndBox;
845 gp_Vec2d aNextLinkDir;
846 Standard_Integer aNextPivotNode = 0;
848 Standard_Integer aNextLinkId = findNextPolygonLink(
850 aPivotNode, aPivotVertex, aRefLinkDir,
851 aBoxes, aPolygon, theSkipped,
852 isSkipLeprous, aLeprousLinks, aDeadLinks,
853 aNextPivotNode, aNextLinkDir, aNextLinkBndBox );
855 if ( aNextLinkId != 0 )
857 aStartNode = aPivotNode;
858 aRefLinkDir = aNextLinkDir;
860 aPivotNode = aNextPivotNode;
861 aPivotVertex = GetVertex( aNextPivotNode );
863 aBoxes.Append ( aNextLinkBndBox );
864 aPolygon.Append( aNextLinkId );
866 isSkipLeprous = Standard_True;
871 if ( aPolygon.Length() == 1 )
872 return Standard_False;
874 // Return to the previous point
875 Standard_Integer aDeadLinkId = Abs( aPolygon.Last() );
876 aDeadLinks.Add ( aDeadLinkId );
878 aLeprousLinks.Remove( aDeadLinkId );
879 aPolygon.Remove ( aPolygon.Length() );
880 aBoxes.Remove ( aBoxes.Length() );
882 Standard_Integer aPrevLinkInfo = aPolygon.Last();
883 const BRepMesh_Edge& aPrevLink = GetEdge( Abs( aPrevLinkInfo ) );
885 if( aPrevLinkInfo > 0 )
887 aStartNode = aPrevLink.FirstNode();
888 aPivotNode = aPrevLink.LastNode();
892 aStartNode = aPrevLink.LastNode();
893 aPivotNode = aPrevLink.FirstNode();
896 aPivotVertex = GetVertex( aPivotNode );
898 aPivotVertex.Coord() - GetVertex( aStartNode ).Coord();
900 isSkipLeprous = Standard_False;
904 if ( aPolygon.Length() < 3 )
905 return Standard_False;
907 cleanupPolygon( aPolygon, aBoxes );
908 meshPolygon ( aPolygon, aBoxes, theSkipped );
910 return Standard_True;
913 //=======================================================================
914 //function : findNextPolygonLink
915 //purpose : Find next link starting from the given node and has maximum
916 // angle respect the given reference link.
917 // Each time the next link is found other neighbor links at the
918 // pivot node are marked as leprous and will be excluded from
919 // consideration next time until a hanging end is occured.
920 //=======================================================================
921 Standard_Integer BRepMesh_Delaun::findNextPolygonLink(
922 const Standard_Integer& theFirstNode,
923 const Standard_Integer& thePivotNode,
924 const BRepMesh_Vertex& thePivotVertex,
925 const gp_Vec2d& theRefLinkDir,
926 const BRepMesh::SequenceOfBndB2d& theBoxes,
927 const BRepMesh::SequenceOfInteger& thePolygon,
928 const BRepMesh::HMapOfInteger theSkipped,
929 const Standard_Boolean& isSkipLeprous,
930 BRepMesh::MapOfInteger& theLeprousLinks,
931 BRepMesh::MapOfInteger& theDeadLinks,
932 Standard_Integer& theNextPivotNode,
933 gp_Vec2d& theNextLinkDir,
934 Bnd_B2d& theNextLinkBndBox )
936 // Find the next link having the greatest angle
937 // respect to a direction of a reference one
938 Standard_Real aMaxAngle = RealFirst();
940 Standard_Integer aNextLinkId = 0;
941 BRepMesh::ListOfInteger::Iterator aLinkIt( myMeshData->LinksConnectedTo( thePivotNode ) );
942 for ( ; aLinkIt.More(); aLinkIt.Next() )
944 const Standard_Integer& aNeighbourLinkInfo = aLinkIt.Value();
945 Standard_Integer aNeighbourLinkId = Abs( aNeighbourLinkInfo );
947 if ( theDeadLinks.Contains( aNeighbourLinkId ) ||
948 ( !theSkipped.IsNull() && theSkipped->Contains( aNeighbourLinkId ) ) )
953 Standard_Boolean isLeprous = theLeprousLinks.Contains( aNeighbourLinkId );
954 if ( isSkipLeprous && isLeprous )
957 const BRepMesh_Edge& aNeighbourLink = GetEdge( aNeighbourLinkId );
959 // Determine whether the link belongs to the mesh
960 if ( aNeighbourLink.Movability() == BRepMesh_Free &&
961 myMeshData->ElementsConnectedTo( aNeighbourLinkInfo ).IsEmpty() )
963 theDeadLinks.Add( aNeighbourLinkId );
967 Standard_Integer anOtherNode = aNeighbourLink.FirstNode();
968 if ( anOtherNode == thePivotNode )
969 anOtherNode = aNeighbourLink.LastNode();
971 gp_Vec2d aCurLinkDir( GetVertex( anOtherNode ).Coord() -
972 thePivotVertex.Coord() );
974 if ( aCurLinkDir.SquareMagnitude() < Precision2 )
976 theDeadLinks.Add( aNeighbourLinkId );
981 theLeprousLinks.Add( aNeighbourLinkId );
983 Standard_Real anAngle = theRefLinkDir.Angle( aCurLinkDir );
984 Standard_Boolean isFrontier =
985 ( aNeighbourLink.Movability() == BRepMesh_Frontier );
987 Standard_Boolean isCheckPointOnEdge = Standard_True;
990 if ( Abs( Abs(anAngle) - M_PI ) < Precision::Angular() )
992 // Glued constrains - don't check intersection
993 isCheckPointOnEdge = Standard_False;
994 anAngle = Abs( anAngle );
998 if (anAngle <= aMaxAngle)
1001 Standard_Boolean isCheckEndPoints = ( anOtherNode != theFirstNode );
1004 Standard_Boolean isNotIntersect =
1005 checkIntersection( aNeighbourLink, thePolygon, theBoxes,
1006 isCheckEndPoints, isCheckPointOnEdge, Standard_True, aBox );
1008 if( isNotIntersect )
1010 aMaxAngle = anAngle;
1012 theNextLinkDir = aCurLinkDir;
1013 theNextPivotNode = anOtherNode;
1014 theNextLinkBndBox = aBox;
1016 aNextLinkId = ( aNeighbourLink.FirstNode() == thePivotNode ) ?
1017 aNeighbourLinkId : -aNeighbourLinkId;
1024 //=======================================================================
1025 //function : checkIntersection
1026 //purpose : Check is the given link intersects the polygon boundaries.
1027 // Returns bounding box for the given link trough the
1028 // <theLinkBndBox> parameter.
1029 //=======================================================================
1030 Standard_Boolean BRepMesh_Delaun::checkIntersection(
1031 const BRepMesh_Edge& theLink,
1032 const BRepMesh::SequenceOfInteger& thePolygon,
1033 const BRepMesh::SequenceOfBndB2d& thePolyBoxes,
1034 const Standard_Boolean isConsiderEndPointTouch,
1035 const Standard_Boolean isConsiderPointOnEdge,
1036 const Standard_Boolean isSkipLastEdge,
1037 Bnd_B2d& theLinkBndBox ) const
1039 theLinkBndBox.Add( GetVertex( theLink.FirstNode() ).Coord() );
1040 theLinkBndBox.Add( GetVertex( theLink.LastNode() ).Coord() );
1042 Standard_Integer aPolyLen = thePolygon.Length();
1043 // Don't check intersection with the last link
1044 if ( isSkipLastEdge )
1047 Standard_Boolean isFrontier =
1048 ( theLink.Movability() == BRepMesh_Frontier );
1050 for ( Standard_Integer aPolyIt = 1; aPolyIt <= aPolyLen; ++aPolyIt )
1052 if ( !theLinkBndBox.IsOut( thePolyBoxes.Value( aPolyIt ) ) )
1054 // intersection is possible...
1055 Standard_Integer aPolyLinkId = Abs( thePolygon( aPolyIt ) );
1056 const BRepMesh_Edge& aPolyLink = GetEdge( aPolyLinkId );
1058 // skip intersections between frontier edges
1059 if ( aPolyLink.Movability() == BRepMesh_Frontier && isFrontier )
1063 BRepMesh_GeomTool::IntFlag aIntFlag = intSegSeg( theLink, aPolyLink,
1064 isConsiderEndPointTouch, isConsiderPointOnEdge, anIntPnt );
1066 if ( aIntFlag != BRepMesh_GeomTool::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(theEdgesId,
1085 theEdgesOri, BRepMesh_Free));
1087 Standard_Boolean isAdded = myCircles.Bind(
1089 GetVertex( theNodesId[0] ).Coord(),
1090 GetVertex( theNodesId[1] ).Coord(),
1091 GetVertex( theNodesId[2] ).Coord() );
1094 myMeshData->RemoveElement( aNewTriangleId );
1097 //=======================================================================
1098 //function : cleanupPolygon
1099 //purpose : Remove internal triangles from the given polygon
1100 //=======================================================================
1101 void BRepMesh_Delaun::cleanupPolygon(const BRepMesh::SequenceOfInteger& thePolygon,
1102 const BRepMesh::SequenceOfBndB2d& thePolyBoxes )
1104 Standard_Integer aPolyLen = thePolygon.Length();
1108 Handle(NCollection_IncAllocator) aAllocator =
1109 new NCollection_IncAllocator(BRepMesh::MEMORY_BLOCK_SIZE_HUGE);
1111 BRepMesh::MapOfIntegerInteger aLoopEdges(10, aAllocator);
1112 BRepMesh::MapOfInteger anIgnoredEdges(10, aAllocator);
1113 BRepMesh::MapOfInteger aPolyVerticesFindMap(10, aAllocator);
1114 BRepMesh::VectorOfInteger aPolyVertices(256, aAllocator);
1115 // Collect boundary vertices of the polygon
1116 for ( Standard_Integer aPolyIt = 1; aPolyIt <= aPolyLen; ++aPolyIt )
1118 Standard_Integer aPolyEdgeInfo = thePolygon( aPolyIt );
1119 Standard_Integer aPolyEdgeId = Abs( aPolyEdgeInfo );
1120 anIgnoredEdges.Add( aPolyEdgeId );
1122 Standard_Boolean isForward = ( aPolyEdgeInfo > 0 );
1123 const BRepMesh_PairOfIndex& aPair =
1124 myMeshData->ElementsConnectedTo( aPolyEdgeId );
1126 Standard_Integer anElemIt = 1;
1127 for ( ; anElemIt <= aPair.Extent(); ++anElemIt )
1129 Standard_Integer anElemId = aPair.Index( anElemIt );
1133 Standard_Integer anEdges[3];
1134 Standard_Boolean anEdgesOri[3];
1135 GetTriangle( anElemId ).Edges(anEdges, anEdgesOri);
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 BRepMesh::MapOfInteger 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->ElementsConnectedTo( 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 BRepMesh::VectorOfInteger& thePolyVertices,
1211 const BRepMesh::MapOfInteger& thePolyVerticesFindMap,
1212 const BRepMesh::SequenceOfInteger& thePolygon,
1213 const BRepMesh::SequenceOfBndB2d& thePolyBoxes,
1214 BRepMesh::MapOfInteger& theSurvivedLinks,
1215 BRepMesh::MapOfIntegerInteger& theLoopEdges )
1217 BRepMesh::ListOfInteger::Iterator aNeighborsIt =
1218 myMeshData->LinksConnectedTo( theZombieNodeId );
1220 // Try to infect neighbor nodes
1221 BRepMesh::VectorOfInteger 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 BRepMesh::VectorOfInteger::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 BRepMesh::VectorOfInteger& 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 BRepMesh::SequenceOfInteger& thePolygon,
1338 const BRepMesh::SequenceOfBndB2d& thePolyBoxes,
1339 BRepMesh::MapOfInteger& 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->LinksConnectedTo(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->ElementsConnectedTo( 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 BRepMesh::SequenceOfInteger& thePolygon,
1426 const BRepMesh::SequenceOfBndB2d& thePolyBoxes)
1428 Standard_Integer aNbOfLinksInLoop = theLinkTo - theLinkFrom - 1;
1429 if ( aNbOfLinksInLoop < 3 )
1432 BRepMesh::SequenceOfInteger aPolygon;
1433 BRepMesh::SequenceOfBndB2d 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 BRepMesh::SequenceOfInteger& thePolygon,
1454 BRepMesh::SequenceOfBndB2d& 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(BRepMesh::SequenceOfInteger& thePolygon,
1490 BRepMesh::SequenceOfBndB2d& thePolyBoxes,
1491 BRepMesh::HMapOfInteger 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_GeomTool::IntFlag aIntFlag = intSegSeg( *aCurEdge, *aNextEdge,
1539 Standard_False, Standard_True, anIntPnt );
1541 if ( aIntFlag == BRepMesh_GeomTool::NoIntersection )
1544 Standard_Boolean isRemoveFromFirst = Standard_False;
1545 Standard_Boolean isAddReplacingEdge = Standard_True;
1546 Standard_Integer aIndexToRemoveTo = aNextPolyIt;
1547 if ( aIntFlag == BRepMesh_GeomTool::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_GeomTool::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_GeomTool::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_GeomTool::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 BRepMesh::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(BRepMesh::SequenceOfInteger& thePolygon,
1756 BRepMesh::SequenceOfBndB2d& 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 || aDist < 0.)
1807 if ( ( anAbsDist >= aMinDist ) &&
1808 ( aAngle <= aOptAngle || aAngle > AngDeviation90Deg ) )
1813 // Check is the test link crosses the polygon boudaries
1814 Standard_Boolean isIntersect = Standard_False;
1815 for ( Standard_Integer aRefLinkNodeIt = 0; aRefLinkNodeIt < 2; ++aRefLinkNodeIt )
1817 const Standard_Integer& aLinkFirstNode = aNodes[aRefLinkNodeIt];
1818 const gp_Pnt2d& aLinkFirstVertex = aRefVertices[aRefLinkNodeIt];
1821 aBox.Add( aLinkFirstVertex );
1822 aBox.Add( aPivotVertex );
1824 BRepMesh_Edge aCheckLink( aLinkFirstNode, aPivotNode, BRepMesh_Free );
1826 Standard_Integer aCheckLinkIt = 2;
1827 for ( ; aCheckLinkIt <= aPolyLen; ++aCheckLinkIt )
1829 if( aCheckLinkIt == aLinkIt )
1832 if ( !aBox.IsOut( thePolyBoxes.Value( aCheckLinkIt ) ) )
1834 const BRepMesh_Edge& aPolyLink =
1835 GetEdge( Abs( thePolygon( aCheckLinkIt ) ) );
1837 if ( aCheckLink.IsEqual( aPolyLink ) )
1840 // intersection is possible...
1842 BRepMesh_GeomTool::IntFlag aIntFlag = intSegSeg( aCheckLink, aPolyLink,
1843 Standard_False, Standard_False, anIntPnt );
1845 if( aIntFlag != BRepMesh_GeomTool::NoIntersection )
1847 isIntersect = Standard_True;
1862 aMinDist = anAbsDist;
1863 aNodes[2] = aPivotNode;
1864 aRefVertices[2] = aPivotVertex;
1865 aUsedLinkId = aLinkIt;
1868 if ( aUsedLinkId == 0 )
1872 BRepMesh_Edge aNewEdges[2] = {
1873 BRepMesh_Edge( aNodes[1], aNodes[2], BRepMesh_Free ),
1874 BRepMesh_Edge( aNodes[2], aNodes[0], BRepMesh_Free ) };
1876 Standard_Integer aNewEdgesInfo[3] = {
1878 myMeshData->AddLink( aNewEdges[0] ),
1879 myMeshData->AddLink( aNewEdges[1] ) };
1882 Standard_Integer anEdges[3];
1883 Standard_Boolean anEdgesOri[3];
1884 for ( Standard_Integer aTriEdgeIt = 0; aTriEdgeIt < 3; ++aTriEdgeIt )
1886 const Standard_Integer& anEdgeInfo = aNewEdgesInfo[aTriEdgeIt];
1887 anEdges[aTriEdgeIt] = Abs( anEdgeInfo );
1888 anEdgesOri[aTriEdgeIt] = anEdgeInfo > 0;
1890 addTriangle( anEdges, anEdgesOri, aNodes );
1892 // Create triangle and split the source polygon on two
1893 // parts (if possible) and mesh each part as independent
1895 if ( aUsedLinkId < aPolyLen )
1897 BRepMesh::SequenceOfInteger aRightPolygon;
1898 thePolygon.Split( aUsedLinkId, aRightPolygon );
1899 aRightPolygon.Prepend( -aNewEdgesInfo[2] );
1901 BRepMesh::SequenceOfBndB2d aRightPolyBoxes;
1902 thePolyBoxes.Split( aUsedLinkId, aRightPolyBoxes );
1905 aBox.Add( aRefVertices[0] );
1906 aBox.Add( aRefVertices[2] );
1907 aRightPolyBoxes.Prepend( aBox );
1909 meshSimplePolygon( aRightPolygon, aRightPolyBoxes );
1913 thePolygon.Remove ( aPolyLen );
1914 thePolyBoxes.Remove( aPolyLen );
1917 if ( aUsedLinkId > 3 )
1919 thePolygon.SetValue( 1, -aNewEdgesInfo[1] );
1922 aBox.Add( aRefVertices[1] );
1923 aBox.Add( aRefVertices[2] );
1925 thePolyBoxes.SetValue( 1, aBox );
1927 meshSimplePolygon( thePolygon, thePolyBoxes );
1931 //=======================================================================
1932 //function : RemoveVertex
1933 //purpose : Removes a vertex from the triangulation
1934 //=======================================================================
1935 void BRepMesh_Delaun::RemoveVertex( const BRepMesh_Vertex& theVertex )
1937 BRepMesh_SelectorOfDataStructureOfDelaun aSelector( myMeshData );
1938 aSelector.NeighboursOf( theVertex );
1940 BRepMesh::MapOfIntegerInteger aLoopEdges;//( 10, myMeshData->Allocator() );
1942 // Loop on triangles to be destroyed :
1943 BRepMesh::MapOfInteger::Iterator aTriangleIt( aSelector.Elements() );
1944 for ( ; aTriangleIt.More(); aTriangleIt.Next() )
1945 deleteTriangle( aTriangleIt.Key(), aLoopEdges );
1947 BRepMesh::SequenceOfBndB2d aBoxes;
1948 BRepMesh::SequenceOfInteger aPolygon;
1949 Standard_Integer aLoopEdgesCount = aLoopEdges.Extent();
1950 BRepMesh::MapOfIntegerInteger::Iterator aLoopEdgesIt( aLoopEdges );
1952 if ( aLoopEdgesIt.More() )
1954 const BRepMesh_Edge& anEdge = GetEdge( aLoopEdgesIt.Key() );
1955 Standard_Integer aFirstNode = anEdge.FirstNode();
1956 Standard_Integer aLastNode;
1957 Standard_Integer aPivotNode = anEdge.LastNode();
1958 Standard_Integer anEdgeId = aLoopEdgesIt.Key();
1960 Standard_Boolean isPositive = (Standard_Boolean)aLoopEdges( anEdgeId );
1963 Standard_Integer aTmp;
1965 aFirstNode = aPivotNode;
1968 aPolygon.Append( -anEdgeId );
1971 aPolygon.Append( anEdgeId );
1973 fillBndBox( aBoxes, GetVertex( aFirstNode ), GetVertex( aPivotNode ) );
1975 aLoopEdges.UnBind( anEdgeId );
1977 aLastNode = aFirstNode;
1978 while ( aPivotNode != aLastNode )
1980 BRepMesh::ListOfInteger::Iterator aLinkIt( myMeshData->LinksConnectedTo( aPivotNode ) );
1981 for ( ; aLinkIt.More(); aLinkIt.Next() )
1983 if ( aLinkIt.Value() != anEdgeId &&
1984 aLoopEdges.IsBound( aLinkIt.Value() ) )
1986 Standard_Integer aCurrentNode;
1987 anEdgeId = aLinkIt.Value();
1988 const BRepMesh_Edge& anEdge1 = GetEdge( anEdgeId );
1990 aCurrentNode = anEdge1.LastNode();
1991 if ( aCurrentNode != aPivotNode )
1993 aCurrentNode = anEdge1.FirstNode();
1994 aPolygon.Append( -anEdgeId );
1997 aPolygon.Append( anEdgeId );
1999 fillBndBox( aBoxes, GetVertex( aCurrentNode ), GetVertex( aPivotNode ) );
2001 aPivotNode = aCurrentNode;
2002 aLoopEdges.UnBind( anEdgeId );
2007 if ( aLoopEdgesCount <= 0 )
2012 meshPolygon( aPolygon, aBoxes );
2017 //=======================================================================
2018 //function : AddVertices
2019 //purpose : Adds some vertices in the triangulation.
2020 //=======================================================================
2021 void BRepMesh_Delaun::AddVertices(BRepMesh::Array1OfVertexOfDelaun& theVertices)
2023 std::make_heap(theVertices.begin(), theVertices.end(), ComparatorOfVertexOfDelaun());
2024 std::sort_heap(theVertices.begin(), theVertices.end(), ComparatorOfVertexOfDelaun());
2026 Standard_Integer aLower = theVertices.Lower();
2027 Standard_Integer anUpper = theVertices.Upper();
2029 BRepMesh::Array1OfInteger aVertexIndexes( aLower, anUpper );
2030 for ( Standard_Integer i = aLower; i <= anUpper; ++i )
2031 aVertexIndexes(i) = myMeshData->AddNode( theVertices(i) );
2033 createTrianglesOnNewVertices( aVertexIndexes );
2036 //=======================================================================
2037 //function : UseEdge
2038 //purpose : Modify mesh to use the edge. Return True if done
2039 //=======================================================================
2040 Standard_Boolean BRepMesh_Delaun::UseEdge( const Standard_Integer /*theIndex*/ )
2043 const BRepMesh_PairOfIndex& aPair = myMeshData->ElemConnectedTo( theIndex );
2044 if ( aPair.Extent() == 0 )
2046 const BRepMesh_Edge& anEdge = GetEdge( theIndex );
2048 Standard_Integer aStartNode, aPivotNode, anOtherNode;
2049 aStartNode = anEdge.FirstNode();
2050 aPivotNode = anEdge.LastNode();
2052 const BRepMesh_ListOfInteger& aStartNodeNeighbors = myMeshData->LinkNeighboursOf( aStartNode );
2053 const BRepMesh_ListOfInteger& aPivotNodeNeighbors = myMeshData->LinkNeighboursOf( aPivotNode );
2055 if ( aStartNodeNeighbors.Extent() > 0 &&
2056 aPivotNodeNeighbors.Extent() > 0 )
2058 const BRepMesh_Vertex& aStartVertex = GetVertex( aStartNode );
2059 const BRepMesh_Vertex& aPivotVertex = GetVertex( aPivotNode );
2061 gp_XY aVEdge ( aPivotVertex.Coord() );
2062 aVEdge.Subtract( aStartVertex.Coord() );
2064 Standard_Real anAngle = 0.;
2065 Standard_Real anAngleMin = RealLast();
2066 Standard_Real anAngleMax = RealFirst();
2067 Standard_Integer aLeftEdge = 0, aRightEdge = 0;
2069 BRepMesh_ListOfInteger::Iterator aNeighborIt( aPivotNodeNeighbors );
2070 for ( ; aNeighborIt.More(); aNeighborIt.Next() )
2072 Standard_Integer anEdgeId = aNeighborIt.Value();
2073 if ( anEdgeId != theIndex )
2075 const BRepMesh_Edge& aNextEdge = GetEdge( anEdgeId );
2077 Standard_Boolean isInMesh = Standard_True;
2078 if ( aNextEdge.Movability() == BRepMesh_Free )
2080 if ( myMeshData->ElemConnectedTo( anEdgeId ).IsEmpty() )
2081 isInMesh = Standard_False;
2086 anOtherNode = aNextEdge.FirstNode();
2087 if ( anOtherNode == aPivotNode )
2088 anOtherNode = aNextEdge.LastNode();
2090 gp_XY aVEdgeCur = GetVertex( anOtherNode ).Coord();
2091 aVEdgeCur.Subtract( aPivotVertex.Coord() );
2093 anAngle = gp_Vec2d( aVEdge ).Angle( gp_Vec2d( aVEdgeCur ) );
2096 if ( anAngle > anAngleMax )
2098 anAngleMax = anAngle;
2099 aLeftEdge = anEdgeId;
2101 if ( anAngle < anAngleMin )
2103 anAngleMin = anAngle;
2104 aRightEdge = anEdgeId;
2109 if ( aLeftEdge > 0 )
2111 if (aLeftEdge==aRightEdge)
2121 return Standard_False;
2124 //=======================================================================
2125 //function : getEdgesByType
2126 //purpose : Gives the list of edges with type defined by input parameter
2127 //=======================================================================
2128 BRepMesh::HMapOfInteger BRepMesh_Delaun::getEdgesByType(
2129 const BRepMesh_DegreeOfFreedom theEdgeType ) const
2131 BRepMesh::HMapOfInteger aResult = new BRepMesh::MapOfInteger;
2132 BRepMesh::MapOfInteger::Iterator anEdgeIt( myMeshData->LinksOfDomain() );
2134 for ( ; anEdgeIt.More(); anEdgeIt.Next() )
2136 Standard_Integer anEdge = anEdgeIt.Key();
2137 Standard_Boolean isToAdd = (theEdgeType == BRepMesh_Free) ?
2138 (myMeshData->ElementsConnectedTo( anEdge ).Extent() <= 1) :
2139 (GetEdge( anEdge ).Movability() == theEdgeType);
2142 aResult->Add( anEdge );
2148 //=======================================================================
2149 //function : calculateDist
2150 //purpose : Calculates distances between the given point and edges of
2152 //=======================================================================
2153 Standard_Real BRepMesh_Delaun::calculateDist( const gp_XY theVEdges[3],
2154 const gp_XY thePoints[3],
2155 const Standard_Integer theEdgesId[3],
2156 const BRepMesh_Vertex& theVertex,
2157 Standard_Real theDistance[3],
2158 Standard_Real theSqModulus[3],
2159 Standard_Integer& theEdgeOn ) const
2161 Standard_Real aMinDist = -1;
2162 if ( !theVEdges || !thePoints || !theEdgesId ||
2163 !theDistance || !theSqModulus )
2166 for( Standard_Integer i = 0; i < 3; ++i )
2168 theSqModulus[i] = theVEdges[i].SquareModulus();
2169 if ( theSqModulus[i] <= Precision2 )
2172 theDistance[i] = theVEdges[i] ^ ( theVertex.Coord() - thePoints[i] );
2174 Standard_Real aDist = theDistance[i] * theDistance[i];
2175 aDist /= theSqModulus[i];
2177 if ( aMinDist < 0 || aDist < aMinDist )
2179 theEdgeOn = theEdgesId[i];
2187 //=======================================================================
2188 //function : Contains
2189 //purpose : Test if triangle of index <TrianIndex> contains geometricaly
2190 // <theVertex>. If <theEdgeOn> is != 0 then theVertex is on Edge
2191 // of index <theEdgeOn>
2192 //=======================================================================
2193 Standard_Boolean BRepMesh_Delaun::Contains( const Standard_Integer theTriangleId,
2194 const BRepMesh_Vertex& theVertex,
2195 Standard_Integer& theEdgeOn ) const
2199 Standard_Integer e[3];
2200 Standard_Boolean o[3];
2201 Standard_Integer p[3];
2203 const BRepMesh_Triangle& aElement = GetTriangle( theTriangleId );
2204 aElement.Edges(e, o);
2206 const BRepMesh_Edge* anEdges[3] = { &GetEdge( e[0] ),
2210 myMeshData->ElementNodes(aElement, p);
2213 aPoints[0] = GetVertex( p[0] ).Coord();
2214 aPoints[1] = GetVertex( p[1] ).Coord();
2215 aPoints[2] = GetVertex( p[2] ).Coord();
2218 aVEdges[0] = aPoints[1];
2219 aVEdges[0].Subtract( aPoints[0] );
2221 aVEdges[1] = aPoints[2];
2222 aVEdges[1].Subtract( aPoints[1] );
2224 aVEdges[2] = aPoints[0];
2225 aVEdges[2].Subtract( aPoints[2] );
2227 Standard_Real aDistance[3];
2228 Standard_Real aSqModulus[3];
2230 Standard_Real aMinDist;
2231 aMinDist = calculateDist( aVEdges, aPoints, e, theVertex, aDistance, aSqModulus, theEdgeOn );
2233 return Standard_False;
2235 if ( aMinDist > Precision2 )
2237 Standard_Integer anEdgeId = theEdgeOn;
2240 if ( anEdgeId != 0 )
2242 Standard_Integer i = 0;
2243 for ( ; i < 3; ++i )
2245 if( e[i] == anEdgeId )
2249 if( anEdges[i]->Movability() != BRepMesh_Free )
2250 if ( aDistance[i] < ( aSqModulus[i] / 5. ) )
2255 return ( aDistance[0] + aDistance[1] + aDistance[2] != 0. &&
2256 ( ( aDistance[0] >= 0. && aDistance[1] >= 0. && aDistance[2] >= 0. ) ||
2257 ( aDistance[0] <= 0. && aDistance[1] <= 0. && aDistance[2] <= 0. ) ) );
2260 //=============================================================================
2261 //function : intSegSeg
2262 //purpose : Checks intersection between the two segments.
2263 //=============================================================================
2264 BRepMesh_GeomTool::IntFlag BRepMesh_Delaun::intSegSeg(
2265 const BRepMesh_Edge& theEdg1,
2266 const BRepMesh_Edge& theEdg2,
2267 const Standard_Boolean isConsiderEndPointTouch,
2268 const Standard_Boolean isConsiderPointOnEdge,
2269 gp_Pnt2d& theIntPnt) const
2271 gp_XY p1, p2, p3, p4;
2272 p1 = GetVertex( theEdg1.FirstNode() ).Coord();
2273 p2 = GetVertex( theEdg1.LastNode() ).Coord();
2274 p3 = GetVertex( theEdg2.FirstNode() ).Coord();
2275 p4 = GetVertex( theEdg2.LastNode() ).Coord();
2277 return BRepMesh_GeomTool::IntSegSeg(p1, p2, p3, p4,
2278 isConsiderEndPointTouch, isConsiderPointOnEdge, theIntPnt);
2281 //=============================================================================
2282 //function : polyArea
2283 //purpose : Returns area of the loop of the given polygon defined by indices
2284 // of its start and end links.
2285 //=============================================================================
2286 Standard_Real BRepMesh_Delaun::polyArea(const BRepMesh::SequenceOfInteger& thePolygon,
2287 const Standard_Integer theStartIndex,
2288 const Standard_Integer theEndIndex) const
2290 Standard_Real aArea = 0.0;
2291 Standard_Integer aPolyLen = thePolygon.Length();
2292 if ( theStartIndex >= theEndIndex ||
2293 theStartIndex > aPolyLen )
2297 Standard_Integer aCurEdgeInfo = thePolygon( theStartIndex );
2298 Standard_Integer aCurEdgeId = Abs( aCurEdgeInfo );
2299 const BRepMesh_Edge* aCurEdge = &GetEdge( aCurEdgeId );
2301 Standard_Integer aNodes[2];
2302 getOrientedNodes( *aCurEdge, aCurEdgeInfo > 0, aNodes );
2304 gp_Pnt2d aRefPnt = GetVertex( aNodes[0] ).Coord();
2305 Standard_Integer aPolyIt = theStartIndex + 1;
2306 for ( ; aPolyIt <= theEndIndex; ++aPolyIt )
2308 aCurEdgeInfo = thePolygon( aPolyIt );
2309 aCurEdgeId = Abs( aCurEdgeInfo );
2310 aCurEdge = &GetEdge( aCurEdgeId );
2312 getOrientedNodes( *aCurEdge, aCurEdgeInfo > 0, aNodes );
2313 gp_Vec2d aVec1( aRefPnt, GetVertex( aNodes[0] ).Coord() );
2314 gp_Vec2d aVec2( aRefPnt, GetVertex( aNodes[1] ).Coord() );
2316 aArea += aVec1 ^ aVec2;