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;
73 inline void UpdateBndBox(const gp_XY& thePnt1, const gp_XY& thePnt2, Bnd_B2d& theBox)
75 theBox.Add( thePnt1 );
76 theBox.Add( thePnt2 );
77 theBox.Enlarge(Precision);
79 } // anonymous namespace
81 //=======================================================================
82 //function : BRepMesh_Delaun
84 //=======================================================================
85 BRepMesh_Delaun::BRepMesh_Delaun (
86 const Handle(BRepMesh_DataStructureOfDelaun)& theOldMesh,
87 const Standard_Integer theCellsCountU,
88 const Standard_Integer theCellsCountV,
89 const Standard_Boolean isFillCircles)
90 : myMeshData ( theOldMesh ),
91 myCircles (new NCollection_IncAllocator(
92 IMeshData::MEMORY_BLOCK_SIZE_HUGE))
96 InitCirclesTool (theCellsCountU, theCellsCountV);
100 //=======================================================================
101 //function : BRepMesh_Delaun
102 //purpose : Creates the triangulation with an empty Mesh data structure
103 //=======================================================================
104 BRepMesh_Delaun::BRepMesh_Delaun(IMeshData::Array1OfVertexOfDelaun& theVertices)
105 : myCircles (theVertices.Length(), new NCollection_IncAllocator(
106 IMeshData::MEMORY_BLOCK_SIZE_HUGE))
108 if ( theVertices.Length() > 2 )
110 myMeshData = new BRepMesh_DataStructureOfDelaun(
111 new NCollection_IncAllocator(IMeshData::MEMORY_BLOCK_SIZE_HUGE),
112 theVertices.Length() );
117 //=======================================================================
118 //function : BRepMesh_Delaun
119 //purpose : Creates the triangulation with and existent Mesh data structure
120 //=======================================================================
121 BRepMesh_Delaun::BRepMesh_Delaun(
122 const Handle(BRepMesh_DataStructureOfDelaun)& theOldMesh,
123 IMeshData::Array1OfVertexOfDelaun& theVertices)
124 : myMeshData( theOldMesh ),
125 myCircles ( theVertices.Length(), new NCollection_IncAllocator(
126 IMeshData::MEMORY_BLOCK_SIZE_HUGE))
128 if ( theVertices.Length() > 2 )
134 //=======================================================================
135 //function : BRepMesh_Delaun
136 //purpose : Creates the triangulation with and existent Mesh data structure
137 //=======================================================================
138 BRepMesh_Delaun::BRepMesh_Delaun(
139 const Handle(BRepMesh_DataStructureOfDelaun)& theOldMesh,
140 IMeshData::VectorOfInteger& theVertexIndices)
141 : myMeshData( theOldMesh ),
142 myCircles ( theVertexIndices.Length(), new NCollection_IncAllocator(
143 IMeshData::MEMORY_BLOCK_SIZE_HUGE))
145 perform(theVertexIndices);
148 //=======================================================================
149 //function : BRepMesh_Delaun
150 //purpose : Creates the triangulation with and existent Mesh data structure
151 //=======================================================================
152 BRepMesh_Delaun::BRepMesh_Delaun (const Handle (BRepMesh_DataStructureOfDelaun)& theOldMesh,
153 IMeshData::VectorOfInteger& theVertexIndices,
154 const Standard_Integer theCellsCountU,
155 const Standard_Integer theCellsCountV)
156 : myMeshData (theOldMesh),
157 myCircles (theVertexIndices.Length (), new NCollection_IncAllocator(
158 IMeshData::MEMORY_BLOCK_SIZE_HUGE))
160 perform (theVertexIndices, theCellsCountU, theCellsCountV);
163 //=======================================================================
165 //purpose : Initializes the triangulation with an Array of Vertex
166 //=======================================================================
167 void BRepMesh_Delaun::Init(IMeshData::Array1OfVertexOfDelaun& theVertices)
169 Standard_Integer aLowerIdx = theVertices.Lower();
170 Standard_Integer anUpperIdx = theVertices.Upper();
171 IMeshData::VectorOfInteger aVertexIndexes(theVertices.Size());
173 Standard_Integer anIndex = aLowerIdx;
174 for ( ; anIndex <= anUpperIdx; ++anIndex )
176 aVertexIndexes.Append(myMeshData->AddNode( theVertices( anIndex ) ));
179 perform( aVertexIndexes );
182 //=======================================================================
183 //function : InitCirclesTool
185 //=======================================================================
186 void BRepMesh_Delaun::InitCirclesTool (const Standard_Integer theCellsCountU,
187 const Standard_Integer theCellsCountV)
190 for (Standard_Integer aNodeIt = 1; aNodeIt <= myMeshData->NbNodes(); ++aNodeIt)
192 aBox.Add (gp_Pnt2d (GetVertex (aNodeIt).Coord ()));
194 aBox.Enlarge (Precision);
196 initCirclesTool (aBox, theCellsCountU, theCellsCountV);
198 IMeshData::IteratorOfMapOfInteger aTriangleIt (myMeshData->ElementsOfDomain());
199 for (; aTriangleIt.More(); aTriangleIt.Next())
201 Standard_Integer aNodesIndices[3];
202 const BRepMesh_Triangle& aTriangle = myMeshData->GetElement (aTriangleIt.Key());
203 myMeshData->ElementNodes (aTriangle, aNodesIndices);
204 myCircles.Bind (aTriangleIt.Key(),
205 GetVertex( aNodesIndices[0] ).Coord(),
206 GetVertex( aNodesIndices[1] ).Coord(),
207 GetVertex( aNodesIndices[2] ).Coord());
211 //=======================================================================
212 //function : initCirclesTool
214 //=======================================================================
215 void BRepMesh_Delaun::initCirclesTool (const Bnd_Box2d& theBox,
216 const Standard_Integer theCellsCountU,
217 const Standard_Integer theCellsCountV)
219 Standard_Real aMinX, aMinY, aMaxX, aMaxY;
220 theBox.Get ( aMinX, aMinY, aMaxX, aMaxY );
221 const Standard_Real aDeltaX = aMaxX - aMinX;
222 const Standard_Real aDeltaY = aMaxY - aMinY;
224 Standard_Integer aScaler = 2;
225 if ( myMeshData->NbNodes() > 100 )
229 else if( myMeshData->NbNodes() > 1000 )
234 myCircles.SetMinMaxSize( gp_XY( aMinX, aMinY ), gp_XY( aMaxX, aMaxY ) );
235 myCircles.SetCellSize ( aDeltaX / Max (theCellsCountU, aScaler),
236 aDeltaY / Max (theCellsCountV, aScaler));
239 //=======================================================================
241 //purpose : Create super mesh and run triangulation procedure
242 //=======================================================================
243 void BRepMesh_Delaun::perform(IMeshData::VectorOfInteger& theVertexIndices,
244 const Standard_Integer theCellsCountU /* = -1 */,
245 const Standard_Integer theCellsCountV /* = -1 */)
247 if (theVertexIndices.Length () <= 2)
253 Standard_Integer anIndex = theVertexIndices.Lower ();
254 Standard_Integer anUpper = theVertexIndices.Upper ();
255 for (; anIndex <= anUpper; ++anIndex)
257 aBox.Add (gp_Pnt2d (GetVertex (theVertexIndices (anIndex)).Coord ()));
260 aBox.Enlarge (Precision);
262 initCirclesTool (aBox, theCellsCountU, theCellsCountV);
265 ComparatorOfIndexedVertexOfDelaun aCmp(myMeshData);
266 std::make_heap(theVertexIndices.begin(), theVertexIndices.end(), aCmp);
267 std::sort_heap(theVertexIndices.begin(), theVertexIndices.end(), aCmp);
269 compute( theVertexIndices );
272 //=======================================================================
273 //function : superMesh
274 //purpose : Build the super mesh
275 //=======================================================================
276 void BRepMesh_Delaun::superMesh(const Bnd_Box2d& theBox)
278 Standard_Real aMinX, aMinY, aMaxX, aMaxY;
279 theBox.Get ( aMinX, aMinY, aMaxX, aMaxY );
280 Standard_Real aDeltaX = aMaxX - aMinX;
281 Standard_Real aDeltaY = aMaxY - aMinY;
283 Standard_Real aDeltaMin = Min( aDeltaX, aDeltaY );
284 Standard_Real aDeltaMax = Max( aDeltaX, aDeltaY );
285 Standard_Real aDelta = aDeltaX + aDeltaY;
287 mySupVert[0] = myMeshData->AddNode(
288 BRepMesh_Vertex( ( aMinX + aMaxX ) / 2, aMaxY + aDeltaMax, BRepMesh_Free ) );
290 mySupVert[1] = myMeshData->AddNode(
291 BRepMesh_Vertex( aMinX - aDelta, aMinY - aDeltaMin, BRepMesh_Free ) );
293 mySupVert[2] = myMeshData->AddNode(
294 BRepMesh_Vertex( aMaxX + aDelta, aMinY - aDeltaMin, BRepMesh_Free ) );
296 Standard_Integer e[3];
297 Standard_Boolean o[3];
298 for (Standard_Integer aNodeId = 0; aNodeId < 3; ++aNodeId)
300 Standard_Integer aFirstNode = aNodeId;
301 Standard_Integer aLastNode = (aNodeId + 1) % 3;
302 Standard_Integer aLinkIndex = myMeshData->AddLink( BRepMesh_Edge(
303 mySupVert[aFirstNode], mySupVert[aLastNode], BRepMesh_Free ) );
305 e[aNodeId] = Abs(aLinkIndex);
306 o[aNodeId] = (aLinkIndex > 0);
309 mySupTrian = BRepMesh_Triangle(e, o, BRepMesh_Free);
312 //=======================================================================
313 //function : deleteTriangle
314 //purpose : Deletes the triangle with the given index and adds the free
315 // edges into the map.
316 // When an edge is suppressed more than one time it is destroyed.
317 //=======================================================================
318 void BRepMesh_Delaun::deleteTriangle(const Standard_Integer theIndex,
319 IMeshData::MapOfIntegerInteger& theLoopEdges )
321 if (!myCircles.IsEmpty())
323 myCircles.Delete (theIndex);
326 const BRepMesh_Triangle& aElement = GetTriangle(theIndex);
327 const Standard_Integer(&e)[3] = aElement.myEdges;
328 const Standard_Boolean(&o)[3] = aElement.myOrientations;
330 myMeshData->RemoveElement( theIndex );
332 for ( Standard_Integer i = 0; i < 3; ++i )
334 if ( !theLoopEdges.Bind( e[i], o[i] ) )
336 theLoopEdges.UnBind( e[i] );
337 myMeshData->RemoveLink( e[i] );
342 //=======================================================================
344 //purpose : Computes the triangulation and add the vertices edges and
345 // triangles to the Mesh data structure
346 //=======================================================================
347 void BRepMesh_Delaun::compute(IMeshData::VectorOfInteger& theVertexIndexes)
349 // Insertion of edges of super triangles in the list of free edges:
350 Handle(NCollection_IncAllocator) aAllocator = new NCollection_IncAllocator(
351 IMeshData::MEMORY_BLOCK_SIZE_HUGE);
353 IMeshData::MapOfIntegerInteger aLoopEdges(10, aAllocator);
354 const Standard_Integer(&e)[3] = mySupTrian.myEdges;
356 aLoopEdges.Bind( e[0], Standard_True );
357 aLoopEdges.Bind( e[1], Standard_True );
358 aLoopEdges.Bind( e[2], Standard_True );
360 if ( theVertexIndexes.Length() > 0 )
362 // Creation of 3 trianglers with the first node and the edges of the super triangle:
363 Standard_Integer anVertexIdx = theVertexIndexes.Lower();
364 createTriangles( theVertexIndexes( anVertexIdx ), aLoopEdges );
366 // Add other nodes to the mesh
367 createTrianglesOnNewVertices( theVertexIndexes );
370 // Destruction of triangles containing a top of the super triangle
371 BRepMesh_SelectorOfDataStructureOfDelaun aSelector( myMeshData );
372 for (Standard_Integer aSupVertId = 0; aSupVertId < 3; ++aSupVertId)
373 aSelector.NeighboursOfNode( mySupVert[aSupVertId] );
376 IMeshData::IteratorOfMapOfInteger aFreeTriangles( aSelector.Elements() );
377 for ( ; aFreeTriangles.More(); aFreeTriangles.Next() )
378 deleteTriangle( aFreeTriangles.Key(), aLoopEdges );
380 // All edges that remain free are removed from aLoopEdges;
381 // only the boundary edges of the triangulation remain there
382 IMeshData::MapOfIntegerInteger::Iterator aFreeEdges( aLoopEdges );
383 for ( ; aFreeEdges.More(); aFreeEdges.Next() )
385 if ( myMeshData->ElementsConnectedTo( aFreeEdges.Key() ).IsEmpty() )
386 myMeshData->RemoveLink( aFreeEdges.Key() );
389 // The tops of the super triangle are destroyed
390 for (Standard_Integer aSupVertId = 0; aSupVertId < 3; ++aSupVertId)
391 myMeshData->RemoveNode( mySupVert[aSupVertId] );
394 //=======================================================================
395 //function : createTriangles
396 //purpose : Creates the triangles beetween the node and the polyline.
397 //=======================================================================
398 void BRepMesh_Delaun::createTriangles(const Standard_Integer theVertexIndex,
399 IMeshData::MapOfIntegerInteger& thePoly)
401 IMeshData::ListOfInteger aLoopEdges, anExternalEdges;
402 const gp_XY& aVertexCoord = myMeshData->GetNode( theVertexIndex ).Coord();
404 IMeshData::MapOfIntegerInteger::Iterator anEdges( thePoly );
405 for ( ; anEdges.More(); anEdges.Next() )
407 Standard_Integer anEdgeId = anEdges.Key();
408 const BRepMesh_Edge& anEdge = GetEdge( anEdgeId );
410 Standard_Boolean isPositive = thePoly( anEdgeId ) != 0;
412 Standard_Integer aNodes[3];
415 aNodes[0] = anEdge.FirstNode();
416 aNodes[2] = anEdge.LastNode();
420 aNodes[0] = anEdge.LastNode();
421 aNodes[2] = anEdge.FirstNode();
423 aNodes[1] = theVertexIndex;
425 const BRepMesh_Vertex& aFirstVertex = GetVertex( aNodes[0] );
426 const BRepMesh_Vertex& aLastVertex = GetVertex( aNodes[2] );
428 gp_XY anEdgeDir( aLastVertex.Coord() - aFirstVertex.Coord() );
429 Standard_Real anEdgeLen = anEdgeDir.Modulus();
430 if ( anEdgeLen < Precision )
433 anEdgeDir.SetCoord( anEdgeDir.X() / anEdgeLen,
434 anEdgeDir.Y() / anEdgeLen );
436 gp_XY aFirstLinkDir( aFirstVertex.Coord() - aVertexCoord );
437 gp_XY aLastLinkDir ( aVertexCoord - aLastVertex.Coord() );
439 Standard_Real aDist12 = aFirstLinkDir ^ anEdgeDir;
440 Standard_Real aDist23 = anEdgeDir ^ aLastLinkDir;
441 if ( Abs( aDist12 ) < Precision ||
442 Abs( aDist23 ) < Precision )
447 BRepMesh_Edge aFirstLink( aNodes[1], aNodes[0], BRepMesh_Free );
448 BRepMesh_Edge aLastLink ( aNodes[2], aNodes[1], BRepMesh_Free );
450 Standard_Integer anEdgesInfo[3] = {
451 myMeshData->AddLink( aFirstLink ),
452 isPositive ? anEdgeId : -anEdgeId,
453 myMeshData->AddLink( aLastLink ) };
455 Standard_Boolean isSensOK = (aDist12 > 0. && aDist23 > 0.);
458 Standard_Integer anEdgeIds[3];
459 Standard_Boolean anEdgesOri[3];
460 for ( Standard_Integer aTriLinkIt = 0; aTriLinkIt < 3; ++aTriLinkIt )
462 const Standard_Integer& anEdgeInfo = anEdgesInfo[aTriLinkIt];
463 anEdgeIds[aTriLinkIt] = Abs( anEdgeInfo );
464 anEdgesOri[aTriLinkIt] = anEdgeInfo > 0;
467 addTriangle(anEdgeIds, anEdgesOri, aNodes );
472 aLoopEdges.Append( anEdges.Key() );
474 aLoopEdges.Append( -anEdges.Key() );
476 if ( aFirstLinkDir.SquareModulus() > aLastLinkDir.SquareModulus() )
477 anExternalEdges.Append( Abs( anEdgesInfo[0] ) );
479 anExternalEdges.Append( Abs( anEdgesInfo[2] ) );
484 while ( !anExternalEdges.IsEmpty() )
486 const BRepMesh_PairOfIndex& aPair =
487 myMeshData->ElementsConnectedTo( Abs( anExternalEdges.First() ) );
490 if ( !aPair.IsEmpty() )
491 deleteTriangle( aPair.FirstIndex(), thePoly );
493 anExternalEdges.RemoveFirst();
496 for ( anEdges.Initialize( thePoly ); anEdges.More(); anEdges.Next() )
498 if ( myMeshData->ElementsConnectedTo( anEdges.Key() ).IsEmpty() )
499 myMeshData->RemoveLink( anEdges.Key() );
502 while ( !aLoopEdges.IsEmpty() )
504 const BRepMesh_Edge& anEdge = GetEdge( Abs( aLoopEdges.First() ) );
505 if ( anEdge.Movability() != BRepMesh_Deleted )
507 Standard_Integer anEdgeIdx = aLoopEdges.First();
508 meshLeftPolygonOf( Abs( anEdgeIdx ), ( anEdgeIdx > 0 ) );
511 aLoopEdges.RemoveFirst();
515 //=======================================================================
516 //function : createTrianglesOnNewVertices
517 //purpose : Creation of triangles from the new nodes
518 //=======================================================================
519 void BRepMesh_Delaun::createTrianglesOnNewVertices(
520 IMeshData::VectorOfInteger& theVertexIndexes)
522 Handle(NCollection_IncAllocator) aAllocator =
523 new NCollection_IncAllocator(IMeshData::MEMORY_BLOCK_SIZE_HUGE);
525 Standard_Real aTolU, aTolV;
526 myMeshData->Data()->GetTolerance(aTolU, aTolV);
527 const Standard_Real aSqTol = aTolU * aTolU + aTolV * aTolV;
529 // Insertion of nodes :
530 Standard_Boolean isModify = Standard_True;
532 Standard_Integer anIndex = theVertexIndexes.Lower();
533 Standard_Integer anUpper = theVertexIndexes.Upper();
534 for( ; anIndex <= anUpper; ++anIndex )
536 aAllocator->Reset(Standard_False);
537 IMeshData::MapOfIntegerInteger aLoopEdges(10, aAllocator);
539 Standard_Integer aVertexIdx = theVertexIndexes( anIndex );
540 const BRepMesh_Vertex& aVertex = GetVertex( aVertexIdx );
542 // Iterator in the list of indexes of circles containing the node
543 IMeshData::ListOfInteger& aCirclesList = myCircles.Select( aVertex.Coord() );
545 Standard_Integer onEgdeId = 0, aTriangleId = 0;
546 IMeshData::ListOfInteger::Iterator aCircleIt( aCirclesList );
547 for ( ; aCircleIt.More(); aCircleIt.Next() )
549 // To add a node in the mesh it is necessary to check conditions:
550 // - the node should be within the boundaries of the mesh and so in an existing triangle
551 // - all adjacent triangles should belong to a component connected with this triangle
552 if ( Contains( aCircleIt.Value(), aVertex, aSqTol, onEgdeId ) )
554 if (onEgdeId != 0 && GetEdge(onEgdeId).Movability() != BRepMesh_Free)
556 // We can skip free vertex too close to the frontier edge.
557 if (aVertex.Movability() == BRepMesh_Free)
560 // However, we should add vertex that have neighboring frontier edges.
563 // Remove triangle even if it contains frontier edge in order
564 // to prevent appearance of incorrect configurations like free
565 // edge glued with frontier #26407
566 aTriangleId = aCircleIt.Value();
567 aCirclesList.Remove( aCircleIt );
572 if ( aTriangleId > 0 )
574 deleteTriangle( aTriangleId, aLoopEdges );
576 isModify = Standard_True;
577 while ( isModify && !aCirclesList.IsEmpty() )
579 isModify = Standard_False;
580 IMeshData::ListOfInteger::Iterator aCircleIt1( aCirclesList );
581 for ( ; aCircleIt1.More(); aCircleIt1.Next() )
583 const BRepMesh_Triangle& aElement = GetTriangle(aCircleIt1.Value());
584 const Standard_Integer(&e)[3] = aElement.myEdges;
586 if ( aLoopEdges.IsBound( e[0] ) ||
587 aLoopEdges.IsBound( e[1] ) ||
588 aLoopEdges.IsBound( e[2] ) )
590 isModify = Standard_True;
591 deleteTriangle( aCircleIt1.Value(), aLoopEdges );
592 aCirclesList.Remove( aCircleIt1 );
598 // Creation of triangles with the current node and free edges
599 // and removal of these edges from the list of free edges
600 createTriangles( aVertexIdx, aLoopEdges );
604 ProcessConstraints();
607 //=======================================================================
608 //function : insertInternalEdges
610 //=======================================================================
611 void BRepMesh_Delaun::insertInternalEdges()
613 Handle(IMeshData::MapOfInteger) anInternalEdges = InternalEdges();;
615 // Destruction of triancles intersecting internal edges
616 // and their replacement by makeshift triangles
617 IMeshData::IteratorOfMapOfInteger anInernalEdgesIt( *anInternalEdges );
618 for ( ; anInernalEdgesIt.More(); anInernalEdgesIt.Next() )
620 const Standard_Integer aLinkIndex = anInernalEdgesIt.Key();
621 const BRepMesh_PairOfIndex& aPair = myMeshData->ElementsConnectedTo(aLinkIndex);
623 // Check both sides of link for adjusted triangle.
624 Standard_Boolean isGo[2] = { Standard_True, Standard_True };
625 for (Standard_Integer aTriangleIt = 1; aTriangleIt <= aPair.Extent(); ++aTriangleIt)
627 const BRepMesh_Triangle& aElement = GetTriangle(aPair.Index(aTriangleIt));
628 const Standard_Integer(&e)[3] = aElement.myEdges;
629 const Standard_Boolean(&o)[3] = aElement.myOrientations;
631 for (Standard_Integer i = 0; i < 3; ++i)
633 if (e[i] == aLinkIndex)
635 isGo[o[i] ? 0 : 1] = Standard_False;
643 meshLeftPolygonOf(aLinkIndex, Standard_True);
648 meshLeftPolygonOf(aLinkIndex, Standard_False);
653 //=======================================================================
654 //function : isBoundToFrontier
655 //purpose : Goes through the neighbour triangles around the given node
656 // started from the given link, returns TRUE if some triangle
657 // has a bounding frontier edge or FALSE elsewhere.
658 // Stop link is used to prevent cycles.
659 // Previous element Id is used to identify next neighbor element.
660 //=======================================================================
661 Standard_Boolean BRepMesh_Delaun::isBoundToFrontier(
662 const Standard_Integer theRefNodeId,
663 const Standard_Integer theRefLinkId,
664 const Standard_Integer theStopLinkId,
665 const Standard_Integer thePrevElementId)
667 const BRepMesh_PairOfIndex& aPair =
668 myMeshData->ElementsConnectedTo( theRefLinkId );
669 if ( aPair.IsEmpty() )
670 return Standard_False;
672 Standard_Integer aNbElements = aPair.Extent();
673 for ( Standard_Integer anElemIt = 1; anElemIt <= aNbElements; ++anElemIt )
675 const Standard_Integer aTriId = aPair.Index(anElemIt);
676 if ( aTriId < 0 || aTriId == thePrevElementId )
679 const BRepMesh_Triangle& aElement = GetTriangle(aTriId);
680 const Standard_Integer(&anEdges)[3] = aElement.myEdges;
682 for ( Standard_Integer anEdgeIt = 0; anEdgeIt < 3; ++anEdgeIt )
684 const Standard_Integer anEdgeId = anEdges[anEdgeIt];
685 if ( anEdgeId == theRefLinkId )
688 if ( anEdgeId == theStopLinkId )
689 return Standard_False;
691 const BRepMesh_Edge& anEdge = GetEdge( anEdgeId );
692 if ( anEdge.FirstNode() != theRefNodeId &&
693 anEdge.LastNode() != theRefNodeId )
698 if ( anEdge.Movability() != BRepMesh_Free )
699 return Standard_True;
701 return isBoundToFrontier( theRefNodeId, anEdgeId, theStopLinkId, aTriId );
705 return Standard_False;
708 //=======================================================================
709 //function : cleanupMesh
710 //purpose : Cleanup mesh from the free triangles
711 //=======================================================================
712 void BRepMesh_Delaun::cleanupMesh()
714 Handle(NCollection_IncAllocator) aAllocator =
715 new NCollection_IncAllocator(IMeshData::MEMORY_BLOCK_SIZE_HUGE);
719 aAllocator->Reset(Standard_False);
720 IMeshData::MapOfIntegerInteger aLoopEdges(10, aAllocator);
721 IMeshData::MapOfInteger aDelTriangles;
723 Handle(IMeshData::MapOfInteger) aFreeEdges = FreeEdges();
724 IMeshData::IteratorOfMapOfInteger aFreeEdgesIt( *aFreeEdges );
725 for ( ; aFreeEdgesIt.More(); aFreeEdgesIt.Next() )
727 const Standard_Integer& aFreeEdgeId = aFreeEdgesIt.Key();
728 const BRepMesh_Edge& anEdge = GetEdge( aFreeEdgeId );
729 if ( anEdge.Movability() == BRepMesh_Frontier )
732 const BRepMesh_PairOfIndex& aPair =
733 myMeshData->ElementsConnectedTo( aFreeEdgeId );
734 if ( aPair.IsEmpty() )
736 aLoopEdges.Bind( aFreeEdgeId, Standard_True );
740 Standard_Integer aTriId = aPair.FirstIndex();
742 // Check that the connected triangle is not surrounded by another triangles
743 const BRepMesh_Triangle& aElement = GetTriangle(aTriId);
744 const Standard_Integer(&anEdges)[3] = aElement.myEdges;
746 Standard_Boolean isCanNotBeRemoved = Standard_True;
747 for ( Standard_Integer aCurEdgeIdx = 0; aCurEdgeIdx < 3; ++aCurEdgeIdx )
749 if ( anEdges[aCurEdgeIdx] != aFreeEdgeId )
752 for ( Standard_Integer anOtherEdgeIt = 1; anOtherEdgeIt <= 2 && isCanNotBeRemoved; ++anOtherEdgeIt )
754 Standard_Integer anOtherEdgeId = ( aCurEdgeIdx + anOtherEdgeIt ) % 3;
755 const BRepMesh_PairOfIndex& anOtherEdgePair =
756 myMeshData->ElementsConnectedTo( anEdges[anOtherEdgeId] );
758 if ( anOtherEdgePair.Extent() < 2 )
760 isCanNotBeRemoved = Standard_False;
764 for (int aTriIdx = 1; aTriIdx <= anOtherEdgePair.Extent () && isCanNotBeRemoved; ++aTriIdx)
766 if (anOtherEdgePair.Index (aTriIdx) == aTriId)
769 Standard_Integer v[3];
770 const BRepMesh_Triangle& aCurTriangle = GetTriangle (anOtherEdgePair.Index (aTriIdx));
771 myMeshData->ElementNodes (aCurTriangle, v);
772 for (int aNodeIdx = 0; aNodeIdx < 3 && isCanNotBeRemoved; ++aNodeIdx)
774 if (v[aNodeIdx] == mySupVert[0] ||
775 v[aNodeIdx] == mySupVert[1] ||
776 v[aNodeIdx] == mySupVert[2])
778 isCanNotBeRemoved = Standard_False;
788 if ( isCanNotBeRemoved )
791 Standard_Boolean isConnected[2] = { Standard_False, Standard_False };
792 for ( Standard_Integer aLinkNodeIt = 0; aLinkNodeIt < 2; ++aLinkNodeIt )
794 isConnected[aLinkNodeIt] = isBoundToFrontier( ( aLinkNodeIt == 0 ) ?
795 anEdge.FirstNode() : anEdge.LastNode(),
796 aFreeEdgeId, aFreeEdgeId, -1);
799 if ( !isConnected[0] || !isConnected[1] )
800 aDelTriangles.Add( aTriId );
803 // Destruction of triangles :
804 Standard_Integer aDeletedTrianglesNb = 0;
805 IMeshData::IteratorOfMapOfInteger aDelTrianglesIt( aDelTriangles );
806 for ( ; aDelTrianglesIt.More(); aDelTrianglesIt.Next() )
808 deleteTriangle( aDelTrianglesIt.Key(), aLoopEdges );
809 aDeletedTrianglesNb++;
812 // Destruction of remaining hanging edges
813 IMeshData::MapOfIntegerInteger::Iterator aLoopEdgesIt( aLoopEdges );
814 for ( ; aLoopEdgesIt.More(); aLoopEdgesIt.Next() )
816 if ( myMeshData->ElementsConnectedTo( aLoopEdgesIt.Key() ).IsEmpty() )
817 myMeshData->RemoveLink( aLoopEdgesIt.Key() );
820 if ( aDeletedTrianglesNb == 0 )
825 //=======================================================================
826 //function : frontierAdjust
827 //purpose : Adjust the mesh on the frontier
828 //=======================================================================
829 void BRepMesh_Delaun::frontierAdjust()
831 Handle(IMeshData::MapOfInteger) aFrontier = Frontier();
833 Handle(NCollection_IncAllocator) aAllocator =
834 new NCollection_IncAllocator(IMeshData::MEMORY_BLOCK_SIZE_HUGE);
836 IMeshData::VectorOfInteger aFailedFrontiers(256, aAllocator);
837 IMeshData::MapOfIntegerInteger aLoopEdges(10, aAllocator);
838 Handle(IMeshData::MapOfInteger) aIntFrontierEdges = new IMeshData::MapOfInteger;
840 for ( Standard_Integer aPass = 1; aPass <= 2; ++aPass )
842 // 1 pass): find external triangles on boundary edges;
843 // 2 pass): find external triangles on boundary edges appeared
844 // during triangles replacement.
846 IMeshData::IteratorOfMapOfInteger aFrontierIt( *aFrontier );
847 for ( ; aFrontierIt.More(); aFrontierIt.Next() )
849 Standard_Integer aFrontierId = aFrontierIt.Key();
850 const BRepMesh_PairOfIndex& aPair = myMeshData->ElementsConnectedTo( aFrontierId );
851 Standard_Integer aNbElem = aPair.Extent();
852 for( Standard_Integer aElemIt = 1; aElemIt <= aNbElem; ++aElemIt )
854 const Standard_Integer aPriorElemId = aPair.Index( aElemIt );
855 if( aPriorElemId < 0 )
858 const BRepMesh_Triangle& aElement = GetTriangle(aPriorElemId);
859 const Standard_Integer(&e)[3] = aElement.myEdges;
860 const Standard_Boolean(&o)[3] = aElement.myOrientations;
862 Standard_Boolean isTriangleFound = Standard_False;
863 for ( Standard_Integer n = 0; n < 3; ++n )
865 if ( aFrontierId == e[n] && !o[n] )
867 // Destruction of external triangles on boundary edges
868 isTriangleFound = Standard_True;
869 deleteTriangle( aPriorElemId, aLoopEdges );
874 if ( isTriangleFound )
879 // destrucrion of remaining hanging edges :
880 IMeshData::MapOfIntegerInteger::Iterator aLoopEdgesIt( aLoopEdges );
881 for ( ; aLoopEdgesIt.More(); aLoopEdgesIt.Next() )
883 Standard_Integer aLoopEdgeId = aLoopEdgesIt.Key();
884 if (myMeshData->ElementsConnectedTo( aLoopEdgeId ).IsEmpty() )
885 myMeshData->RemoveLink( aLoopEdgeId );
888 // destruction of triangles crossing the boundary edges and
889 // their replacement by makeshift triangles
890 for ( aFrontierIt.Reset(); aFrontierIt.More(); aFrontierIt.Next() )
892 Standard_Integer aFrontierId = aFrontierIt.Key();
893 if ( !myMeshData->ElementsConnectedTo( aFrontierId ).IsEmpty() )
896 Standard_Boolean isSuccess =
897 meshLeftPolygonOf( aFrontierId, Standard_True, aIntFrontierEdges );
899 if ( aPass == 2 && !isSuccess )
900 aFailedFrontiers.Append( aFrontierId );
906 // When the mesh has been cleaned up, try to process frontier edges
907 // once again to fill the possible gaps that might be occured in case of "saw" -
908 // situation when frontier edge has a triangle at a right side, but its free
909 // links cross another frontieres and meshLeftPolygonOf itself can't collect
911 IMeshData::VectorOfInteger::Iterator aFailedFrontiersIt( aFailedFrontiers );
912 for ( ; aFailedFrontiersIt.More(); aFailedFrontiersIt.Next() )
914 Standard_Integer aFrontierId = aFailedFrontiersIt.Value();
915 if ( !myMeshData->ElementsConnectedTo( aFrontierId ).IsEmpty() )
918 meshLeftPolygonOf( aFrontierId, Standard_True, aIntFrontierEdges );
922 //=======================================================================
923 //function : fillBndBox
924 //purpose : Add boundig box for edge defined by start & end point to
925 // the given vector of bounding boxes for triangulation edges
926 //=======================================================================
927 void BRepMesh_Delaun::fillBndBox(IMeshData::SequenceOfBndB2d& theBoxes,
928 const BRepMesh_Vertex& theV1,
929 const BRepMesh_Vertex& theV2)
932 UpdateBndBox(theV1.Coord(), theV2.Coord(), aBox);
933 theBoxes.Append( aBox );
936 //=======================================================================
937 //function : meshLeftPolygonOf
938 //purpose : Collect the polygon at the left of the given edge (material side)
939 //=======================================================================
940 Standard_Boolean BRepMesh_Delaun::meshLeftPolygonOf(
941 const Standard_Integer theStartEdgeId,
942 const Standard_Boolean isForward,
943 Handle(IMeshData::MapOfInteger) theSkipped)
945 if ( !theSkipped.IsNull() && theSkipped->Contains( theStartEdgeId ) )
946 return Standard_True;
948 const BRepMesh_Edge& aRefEdge = GetEdge( theStartEdgeId );
950 IMeshData::SequenceOfInteger aPolygon;
951 Standard_Integer aStartNode, aPivotNode;
954 aPolygon.Append( theStartEdgeId );
955 aStartNode = aRefEdge.FirstNode();
956 aPivotNode = aRefEdge.LastNode();
960 aPolygon.Append( -theStartEdgeId );
961 aStartNode = aRefEdge.LastNode();
962 aPivotNode = aRefEdge.FirstNode();
966 const BRepMesh_Vertex& aStartEdgeVertexS = GetVertex( aStartNode );
967 BRepMesh_Vertex aPivotVertex = GetVertex( aPivotNode );
969 gp_Vec2d aRefLinkDir( aPivotVertex.Coord() -
970 aStartEdgeVertexS.Coord() );
972 if ( aRefLinkDir.SquareMagnitude() < Precision2 )
973 return Standard_True;
975 // Auxilary structures.
976 // Bounding boxes of polygon links to be used for preliminary
977 // analysis of intersections
978 IMeshData::SequenceOfBndB2d aBoxes;
979 fillBndBox( aBoxes, aStartEdgeVertexS, aPivotVertex );
982 IMeshData::MapOfInteger aDeadLinks;
984 // Links are temporarily excluded from consideration
985 IMeshData::MapOfInteger aLeprousLinks;
986 aLeprousLinks.Add( theStartEdgeId );
988 Standard_Boolean isSkipLeprous = Standard_True;
989 Standard_Integer aFirstNode = aStartNode;
990 while ( aPivotNode != aFirstNode )
992 Bnd_B2d aNextLinkBndBox;
993 gp_Vec2d aNextLinkDir;
994 Standard_Integer aNextPivotNode = 0;
996 Standard_Integer aNextLinkId = findNextPolygonLink(
998 aPivotNode, aPivotVertex, aRefLinkDir,
999 aBoxes, aPolygon, theSkipped,
1000 isSkipLeprous, aLeprousLinks, aDeadLinks,
1001 aNextPivotNode, aNextLinkDir, aNextLinkBndBox );
1003 if ( aNextLinkId != 0 )
1005 aStartNode = aPivotNode;
1006 aRefLinkDir = aNextLinkDir;
1008 aPivotNode = aNextPivotNode;
1009 aPivotVertex = GetVertex( aNextPivotNode );
1011 aBoxes.Append ( aNextLinkBndBox );
1012 aPolygon.Append( aNextLinkId );
1014 isSkipLeprous = Standard_True;
1019 if ( aPolygon.Length() == 1 )
1020 return Standard_False;
1022 // Return to the previous point
1023 Standard_Integer aDeadLinkId = Abs( aPolygon.Last() );
1024 aDeadLinks.Add ( aDeadLinkId );
1026 aLeprousLinks.Remove( aDeadLinkId );
1027 aPolygon.Remove ( aPolygon.Length() );
1028 aBoxes.Remove ( aBoxes.Length() );
1030 Standard_Integer aPrevLinkInfo = aPolygon.Last();
1031 const BRepMesh_Edge& aPrevLink = GetEdge( Abs( aPrevLinkInfo ) );
1033 if( aPrevLinkInfo > 0 )
1035 aStartNode = aPrevLink.FirstNode();
1036 aPivotNode = aPrevLink.LastNode();
1040 aStartNode = aPrevLink.LastNode();
1041 aPivotNode = aPrevLink.FirstNode();
1044 aPivotVertex = GetVertex( aPivotNode );
1046 aPivotVertex.Coord() - GetVertex( aStartNode ).Coord();
1048 isSkipLeprous = Standard_False;
1052 if ( aPolygon.Length() < 3 )
1053 return Standard_False;
1055 cleanupPolygon( aPolygon, aBoxes );
1056 meshPolygon ( aPolygon, aBoxes, theSkipped );
1058 return Standard_True;
1061 //=======================================================================
1062 //function : findNextPolygonLink
1063 //purpose : Find next link starting from the given node and has maximum
1064 // angle respect the given reference link.
1065 // Each time the next link is found other neighbor links at the
1066 // pivot node are marked as leprous and will be excluded from
1067 // consideration next time until a hanging end is occured.
1068 //=======================================================================
1069 Standard_Integer BRepMesh_Delaun::findNextPolygonLink(
1070 const Standard_Integer& theFirstNode,
1071 const Standard_Integer& thePivotNode,
1072 const BRepMesh_Vertex& thePivotVertex,
1073 const gp_Vec2d& theRefLinkDir,
1074 const IMeshData::SequenceOfBndB2d& theBoxes,
1075 const IMeshData::SequenceOfInteger& thePolygon,
1076 const Handle(IMeshData::MapOfInteger) theSkipped,
1077 const Standard_Boolean& isSkipLeprous,
1078 IMeshData::MapOfInteger& theLeprousLinks,
1079 IMeshData::MapOfInteger& theDeadLinks,
1080 Standard_Integer& theNextPivotNode,
1081 gp_Vec2d& theNextLinkDir,
1082 Bnd_B2d& theNextLinkBndBox )
1084 // Find the next link having the greatest angle
1085 // respect to a direction of a reference one
1086 Standard_Real aMaxAngle = RealFirst();
1088 Standard_Integer aNextLinkId = 0;
1089 IMeshData::ListOfInteger::Iterator aLinkIt( myMeshData->LinksConnectedTo( thePivotNode ) );
1090 for ( ; aLinkIt.More(); aLinkIt.Next() )
1092 const Standard_Integer& aNeighbourLinkInfo = aLinkIt.Value();
1093 Standard_Integer aNeighbourLinkId = Abs( aNeighbourLinkInfo );
1095 if ( theDeadLinks.Contains( aNeighbourLinkId ) ||
1096 ( !theSkipped.IsNull() && theSkipped->Contains( aNeighbourLinkId ) ) )
1101 Standard_Boolean isLeprous = theLeprousLinks.Contains( aNeighbourLinkId );
1102 if ( isSkipLeprous && isLeprous )
1105 const BRepMesh_Edge& aNeighbourLink = GetEdge( aNeighbourLinkId );
1107 // Determine whether the link belongs to the mesh
1108 if ( aNeighbourLink.Movability() == BRepMesh_Free &&
1109 myMeshData->ElementsConnectedTo( aNeighbourLinkInfo ).IsEmpty() )
1111 theDeadLinks.Add( aNeighbourLinkId );
1115 Standard_Integer anOtherNode = aNeighbourLink.FirstNode();
1116 if ( anOtherNode == thePivotNode )
1117 anOtherNode = aNeighbourLink.LastNode();
1119 gp_Vec2d aCurLinkDir( GetVertex( anOtherNode ).Coord() -
1120 thePivotVertex.Coord() );
1122 if ( aCurLinkDir.SquareMagnitude() < Precision2 )
1124 theDeadLinks.Add( aNeighbourLinkId );
1129 theLeprousLinks.Add( aNeighbourLinkId );
1131 Standard_Real anAngle = theRefLinkDir.Angle( aCurLinkDir );
1132 Standard_Boolean isFrontier =
1133 ( aNeighbourLink.Movability() == BRepMesh_Frontier );
1135 Standard_Boolean isCheckPointOnEdge = Standard_True;
1138 if ( Abs( Abs(anAngle) - M_PI ) < Precision::Angular() )
1140 // Glued constrains - don't check intersection
1141 isCheckPointOnEdge = Standard_False;
1142 anAngle = Abs( anAngle );
1146 if (anAngle <= aMaxAngle)
1149 Standard_Boolean isCheckEndPoints = ( anOtherNode != theFirstNode );
1152 Standard_Boolean isNotIntersect =
1153 checkIntersection( aNeighbourLink, thePolygon, theBoxes,
1154 isCheckEndPoints, isCheckPointOnEdge, Standard_True, aBox );
1156 if( isNotIntersect )
1158 aMaxAngle = anAngle;
1160 theNextLinkDir = aCurLinkDir;
1161 theNextPivotNode = anOtherNode;
1162 theNextLinkBndBox = aBox;
1164 aNextLinkId = ( aNeighbourLink.FirstNode() == thePivotNode ) ?
1165 aNeighbourLinkId : -aNeighbourLinkId;
1172 //=======================================================================
1173 //function : checkIntersection
1174 //purpose : Check is the given link intersects the polygon boundaries.
1175 // Returns bounding box for the given link trough the
1176 // <theLinkBndBox> parameter.
1177 //=======================================================================
1178 Standard_Boolean BRepMesh_Delaun::checkIntersection(
1179 const BRepMesh_Edge& theLink,
1180 const IMeshData::SequenceOfInteger& thePolygon,
1181 const IMeshData::SequenceOfBndB2d& thePolyBoxes,
1182 const Standard_Boolean isConsiderEndPointTouch,
1183 const Standard_Boolean isConsiderPointOnEdge,
1184 const Standard_Boolean isSkipLastEdge,
1185 Bnd_B2d& theLinkBndBox ) const
1187 UpdateBndBox(GetVertex(theLink.FirstNode()).Coord(),
1188 GetVertex(theLink.LastNode()).Coord(), theLinkBndBox);
1190 Standard_Integer aPolyLen = thePolygon.Length();
1191 // Don't check intersection with the last link
1192 if ( isSkipLastEdge )
1195 Standard_Boolean isFrontier =
1196 ( theLink.Movability() == BRepMesh_Frontier );
1198 for ( Standard_Integer aPolyIt = 1; aPolyIt <= aPolyLen; ++aPolyIt )
1200 if ( !theLinkBndBox.IsOut( thePolyBoxes.Value( aPolyIt ) ) )
1202 // intersection is possible...
1203 Standard_Integer aPolyLinkId = Abs( thePolygon( aPolyIt ) );
1204 const BRepMesh_Edge& aPolyLink = GetEdge( aPolyLinkId );
1206 // skip intersections between frontier edges
1207 if ( aPolyLink.Movability() == BRepMesh_Frontier && isFrontier )
1211 BRepMesh_GeomTool::IntFlag aIntFlag = intSegSeg( theLink, aPolyLink,
1212 isConsiderEndPointTouch, isConsiderPointOnEdge, anIntPnt );
1214 if ( aIntFlag != BRepMesh_GeomTool::NoIntersection )
1215 return Standard_False;
1219 // Ok, no intersection
1220 return Standard_True;
1223 //=======================================================================
1224 //function : addTriangle
1225 //purpose : Add a triangle based on the given oriented edges into mesh
1226 //=======================================================================
1227 void BRepMesh_Delaun::addTriangle( const Standard_Integer (&theEdgesId)[3],
1228 const Standard_Boolean (&theEdgesOri)[3],
1229 const Standard_Integer (&theNodesId)[3] )
1231 Standard_Integer aNewTriangleId =
1232 myMeshData->AddElement(BRepMesh_Triangle(theEdgesId,
1233 theEdgesOri, BRepMesh_Free));
1235 Standard_Boolean isAdded = myCircles.Bind(
1237 GetVertex( theNodesId[0] ).Coord(),
1238 GetVertex( theNodesId[1] ).Coord(),
1239 GetVertex( theNodesId[2] ).Coord() );
1242 myMeshData->RemoveElement( aNewTriangleId );
1245 //=======================================================================
1246 //function : cleanupPolygon
1247 //purpose : Remove internal triangles from the given polygon
1248 //=======================================================================
1249 void BRepMesh_Delaun::cleanupPolygon(const IMeshData::SequenceOfInteger& thePolygon,
1250 const IMeshData::SequenceOfBndB2d& thePolyBoxes )
1252 Standard_Integer aPolyLen = thePolygon.Length();
1256 Handle(NCollection_IncAllocator) aAllocator =
1257 new NCollection_IncAllocator(IMeshData::MEMORY_BLOCK_SIZE_HUGE);
1259 IMeshData::MapOfIntegerInteger aLoopEdges(10, aAllocator);
1260 IMeshData::MapOfInteger anIgnoredEdges;
1261 IMeshData::MapOfInteger aPolyVerticesFindMap;
1262 IMeshData::VectorOfInteger aPolyVertices(256, aAllocator);
1263 // Collect boundary vertices of the polygon
1264 for ( Standard_Integer aPolyIt = 1; aPolyIt <= aPolyLen; ++aPolyIt )
1266 Standard_Integer aPolyEdgeInfo = thePolygon( aPolyIt );
1267 Standard_Integer aPolyEdgeId = Abs( aPolyEdgeInfo );
1268 anIgnoredEdges.Add( aPolyEdgeId );
1270 Standard_Boolean isForward = ( aPolyEdgeInfo > 0 );
1271 const BRepMesh_PairOfIndex& aPair =
1272 myMeshData->ElementsConnectedTo( aPolyEdgeId );
1274 Standard_Integer anElemIt = 1;
1275 for ( ; anElemIt <= aPair.Extent(); ++anElemIt )
1277 Standard_Integer anElemId = aPair.Index( anElemIt );
1281 const BRepMesh_Triangle& aElement = GetTriangle(anElemId);
1282 const Standard_Integer(&anEdges)[3] = aElement.myEdges;
1283 const Standard_Boolean(&anEdgesOri)[3] = aElement.myOrientations;
1285 Standard_Integer isTriangleFound = Standard_False;
1286 for ( Standard_Integer anEdgeIt = 0; anEdgeIt < 3; ++anEdgeIt )
1288 if ( anEdges[anEdgeIt] == aPolyEdgeId &&
1289 anEdgesOri[anEdgeIt] == isForward )
1291 isTriangleFound = Standard_True;
1292 deleteTriangle( anElemId, aLoopEdges );
1297 if ( isTriangleFound )
1301 // Skip a neighbor link to extract unique vertices each time
1304 const BRepMesh_Edge& aPolyEdge = GetEdge( aPolyEdgeId );
1305 Standard_Integer aFirstVertex = aPolyEdge.FirstNode();
1306 Standard_Integer aLastVertex = aPolyEdge.LastNode();
1308 aPolyVerticesFindMap.Add( aFirstVertex );
1309 aPolyVerticesFindMap.Add( aLastVertex );
1311 if ( aPolyEdgeInfo > 0 )
1313 aPolyVertices.Append( aFirstVertex );
1314 aPolyVertices.Append( aLastVertex );
1318 aPolyVertices.Append( aLastVertex );
1319 aPolyVertices.Append( aFirstVertex );
1324 // Make closed sequence
1325 if ( aPolyVertices.First() != aPolyVertices.Last() )
1326 aPolyVertices.Append( aPolyVertices.First() );
1328 IMeshData::MapOfInteger aSurvivedLinks( anIgnoredEdges );
1330 Standard_Integer aPolyVertIt = 0;
1331 Standard_Integer anUniqueVerticesNum = aPolyVertices.Length() - 1;
1332 for ( ; aPolyVertIt < anUniqueVerticesNum; ++aPolyVertIt )
1334 killTrianglesAroundVertex( aPolyVertices( aPolyVertIt ),
1335 aPolyVertices, aPolyVerticesFindMap, thePolygon,
1336 thePolyBoxes, aSurvivedLinks, aLoopEdges );
1339 IMeshData::MapOfIntegerInteger::Iterator aLoopEdgesIt( aLoopEdges );
1340 for ( ; aLoopEdgesIt.More(); aLoopEdgesIt.Next() )
1342 const Standard_Integer& aLoopEdgeId = aLoopEdgesIt.Key();
1343 if ( anIgnoredEdges.Contains( aLoopEdgeId ) )
1346 if ( myMeshData->ElementsConnectedTo( aLoopEdgeId ).IsEmpty() )
1347 myMeshData->RemoveLink( aLoopEdgesIt.Key() );
1351 //=======================================================================
1352 //function : killTrianglesAroundVertex
1353 //purpose : Remove all triangles and edges that are placed
1354 // inside the polygon or crossed it.
1355 //=======================================================================
1356 void BRepMesh_Delaun::killTrianglesAroundVertex(
1357 const Standard_Integer theZombieNodeId,
1358 const IMeshData::VectorOfInteger& thePolyVertices,
1359 const IMeshData::MapOfInteger& thePolyVerticesFindMap,
1360 const IMeshData::SequenceOfInteger& thePolygon,
1361 const IMeshData::SequenceOfBndB2d& thePolyBoxes,
1362 IMeshData::MapOfInteger& theSurvivedLinks,
1363 IMeshData::MapOfIntegerInteger& theLoopEdges )
1365 IMeshData::ListOfInteger::Iterator aNeighborsIt =
1366 myMeshData->LinksConnectedTo( theZombieNodeId );
1368 // Try to infect neighbor nodes
1369 IMeshData::VectorOfInteger aVictimNodes;
1370 for ( ; aNeighborsIt.More(); aNeighborsIt.Next() )
1372 const Standard_Integer& aNeighborLinkId = aNeighborsIt.Value();
1373 if ( theSurvivedLinks.Contains( aNeighborLinkId ) )
1376 const BRepMesh_Edge& aNeighborLink = GetEdge( aNeighborLinkId );
1377 if ( aNeighborLink.Movability() == BRepMesh_Frontier )
1379 // Though, if it lies onto the polygon boundary -
1380 // take its triangles
1382 Standard_Boolean isNotIntersect =
1383 checkIntersection( aNeighborLink, thePolygon,
1384 thePolyBoxes, Standard_False, Standard_True,
1385 Standard_False, aBox );
1387 if ( isNotIntersect )
1390 theSurvivedLinks.Add( aNeighborLinkId );
1396 Standard_Integer anOtherNode = aNeighborLink.FirstNode();
1397 if ( anOtherNode == theZombieNodeId )
1398 anOtherNode = aNeighborLink.LastNode();
1400 // Possible sacrifice
1401 if ( !thePolyVerticesFindMap.Contains( anOtherNode ) )
1403 if ( isVertexInsidePolygon( anOtherNode, thePolyVertices ) )
1406 aVictimNodes.Append( anOtherNode );
1410 // Lucky. But it may intersect the polygon boundary.
1412 killTrianglesOnIntersectingLinks( aNeighborLinkId,
1413 aNeighborLink, anOtherNode, thePolygon,
1414 thePolyBoxes, theSurvivedLinks, theLoopEdges );
1421 // Add link to the survivers to avoid cycling
1422 theSurvivedLinks.Add( aNeighborLinkId );
1423 killLinkTriangles( aNeighborLinkId, theLoopEdges );
1426 // Go and do your job!
1427 IMeshData::VectorOfInteger::Iterator aVictimIt( aVictimNodes );
1428 for ( ; aVictimIt.More(); aVictimIt.Next() )
1430 killTrianglesAroundVertex( aVictimIt.Value(), thePolyVertices,
1431 thePolyVerticesFindMap, thePolygon, thePolyBoxes,
1432 theSurvivedLinks, theLoopEdges );
1436 //=======================================================================
1437 //function : isVertexInsidePolygon
1438 //purpose : Checks is the given vertex lies inside the polygon
1439 //=======================================================================
1440 Standard_Boolean BRepMesh_Delaun::isVertexInsidePolygon(
1441 const Standard_Integer& theVertexId,
1442 const IMeshData::VectorOfInteger& thePolygonVertices ) const
1444 Standard_Integer aPolyLen = thePolygonVertices.Length();
1446 return Standard_False;
1449 const gp_XY aCenterPointXY = GetVertex( theVertexId ).Coord();
1451 const BRepMesh_Vertex& aFirstVertex = GetVertex( thePolygonVertices( 0 ) );
1452 gp_Vec2d aPrevVertexDir( aFirstVertex.Coord() - aCenterPointXY );
1453 if ( aPrevVertexDir.SquareMagnitude() < Precision2 )
1454 return Standard_True;
1456 Standard_Real aTotalAng = 0.0;
1457 for ( Standard_Integer aPolyIt = 1; aPolyIt < aPolyLen; ++aPolyIt )
1459 const BRepMesh_Vertex& aPolyVertex = GetVertex( thePolygonVertices( aPolyIt ) );
1461 gp_Vec2d aCurVertexDir( aPolyVertex.Coord() - aCenterPointXY );
1462 if ( aCurVertexDir.SquareMagnitude() < Precision2 )
1463 return Standard_True;
1465 aTotalAng += aCurVertexDir.Angle( aPrevVertexDir );
1466 aPrevVertexDir = aCurVertexDir;
1469 if ( Abs( Angle2PI - aTotalAng ) > Precision::Angular() )
1470 return Standard_False;
1472 return Standard_True;
1475 //=======================================================================
1476 //function : killTrianglesOnIntersectingLinks
1477 //purpose : Checks is the given link crosses the polygon boundary.
1478 // If yes, kills its triangles and checks neighbor links on
1479 // boundary intersection. Does nothing elsewhere.
1480 //=======================================================================
1481 void BRepMesh_Delaun::killTrianglesOnIntersectingLinks(
1482 const Standard_Integer& theLinkToCheckId,
1483 const BRepMesh_Edge& theLinkToCheck,
1484 const Standard_Integer& theEndPoint,
1485 const IMeshData::SequenceOfInteger& thePolygon,
1486 const IMeshData::SequenceOfBndB2d& thePolyBoxes,
1487 IMeshData::MapOfInteger& theSurvivedLinks,
1488 IMeshData::MapOfIntegerInteger& theLoopEdges )
1490 if ( theSurvivedLinks.Contains( theLinkToCheckId ) )
1494 Standard_Boolean isNotIntersect =
1495 checkIntersection( theLinkToCheck, thePolygon,
1496 thePolyBoxes, Standard_False, Standard_False,
1497 Standard_False, aBox );
1499 theSurvivedLinks.Add( theLinkToCheckId );
1501 if ( isNotIntersect )
1504 killLinkTriangles( theLinkToCheckId, theLoopEdges );
1506 IMeshData::ListOfInteger::Iterator aNeighborsIt(
1507 myMeshData->LinksConnectedTo(theEndPoint));
1509 for ( ; aNeighborsIt.More(); aNeighborsIt.Next() )
1511 const Standard_Integer& aNeighborLinkId = aNeighborsIt.Value();
1512 const BRepMesh_Edge& aNeighborLink = GetEdge( aNeighborLinkId );
1513 Standard_Integer anOtherNode = aNeighborLink.FirstNode();
1514 if ( anOtherNode == theEndPoint )
1515 anOtherNode = aNeighborLink.LastNode();
1517 killTrianglesOnIntersectingLinks( aNeighborLinkId,
1518 aNeighborLink, anOtherNode, thePolygon,
1519 thePolyBoxes, theSurvivedLinks, theLoopEdges );
1523 //=======================================================================
1524 //function : killLinkTriangles
1525 //purpose : Kill triangles bound to the given link.
1526 //=======================================================================
1527 void BRepMesh_Delaun::killLinkTriangles(
1528 const Standard_Integer& theLinkId,
1529 IMeshData::MapOfIntegerInteger& theLoopEdges )
1531 const BRepMesh_PairOfIndex& aPair =
1532 myMeshData->ElementsConnectedTo( theLinkId );
1534 Standard_Integer anElemNb = aPair.Extent();
1535 for ( Standard_Integer aPairIt = 1; aPairIt <= anElemNb; ++aPairIt )
1537 Standard_Integer anElemId = aPair.FirstIndex();
1541 deleteTriangle( anElemId, theLoopEdges );
1545 //=======================================================================
1546 //function : getOrientedNodes
1547 //purpose : Returns start and end nodes of the given edge in respect to
1549 //=======================================================================
1550 void BRepMesh_Delaun::getOrientedNodes(const BRepMesh_Edge& theEdge,
1551 const Standard_Boolean isForward,
1552 Standard_Integer *theNodes) const
1556 theNodes[0] = theEdge.FirstNode();
1557 theNodes[1] = theEdge.LastNode();
1561 theNodes[0] = theEdge.LastNode();
1562 theNodes[1] = theEdge.FirstNode();
1566 //=======================================================================
1567 //function : processLoop
1568 //purpose : Processes loop within the given polygon formed by range of
1569 // its links specified by start and end link indices.
1570 //=======================================================================
1571 void BRepMesh_Delaun::processLoop(const Standard_Integer theLinkFrom,
1572 const Standard_Integer theLinkTo,
1573 const IMeshData::SequenceOfInteger& thePolygon,
1574 const IMeshData::SequenceOfBndB2d& thePolyBoxes)
1576 Standard_Integer aNbOfLinksInLoop = theLinkTo - theLinkFrom - 1;
1577 if ( aNbOfLinksInLoop < 3 )
1580 IMeshData::SequenceOfInteger aPolygon;
1581 IMeshData::SequenceOfBndB2d aPolyBoxes;
1582 for ( ; aNbOfLinksInLoop > 0; --aNbOfLinksInLoop )
1584 Standard_Integer aLoopLinkIndex = theLinkFrom + aNbOfLinksInLoop;
1585 aPolygon .Prepend( thePolygon ( aLoopLinkIndex ) );
1586 aPolyBoxes.Prepend( thePolyBoxes( aLoopLinkIndex ) );
1588 meshPolygon( aPolygon, aPolyBoxes );
1591 //=======================================================================
1592 //function : createAndReplacePolygonLink
1593 //purpose : Creates new link based on the given nodes and updates the
1595 //=======================================================================
1596 Standard_Integer BRepMesh_Delaun::createAndReplacePolygonLink(
1597 const Standard_Integer *theNodes,
1598 const gp_Pnt2d *thePnts,
1599 const Standard_Integer theRootIndex,
1600 const ReplaceFlag theReplaceFlag,
1601 IMeshData::SequenceOfInteger& thePolygon,
1602 IMeshData::SequenceOfBndB2d& thePolyBoxes )
1604 Standard_Integer aNewEdgeId =
1605 myMeshData->AddLink( BRepMesh_Edge(
1606 theNodes[0], theNodes[1], BRepMesh_Free ) );
1609 UpdateBndBox(thePnts[0].Coord(), thePnts[1].Coord(), aNewBox);
1611 switch ( theReplaceFlag )
1613 case BRepMesh_Delaun::Replace:
1614 thePolygon .SetValue( theRootIndex, aNewEdgeId );
1615 thePolyBoxes.SetValue( theRootIndex, aNewBox );
1618 case BRepMesh_Delaun::InsertAfter:
1619 thePolygon .InsertAfter( theRootIndex, aNewEdgeId );
1620 thePolyBoxes.InsertAfter( theRootIndex, aNewBox );
1623 case BRepMesh_Delaun::InsertBefore:
1624 thePolygon .InsertBefore( theRootIndex, aNewEdgeId );
1625 thePolyBoxes.InsertBefore( theRootIndex, aNewBox );
1632 //=======================================================================
1633 //function : meshPolygon
1635 //=======================================================================
1636 void BRepMesh_Delaun::meshPolygon(IMeshData::SequenceOfInteger& thePolygon,
1637 IMeshData::SequenceOfBndB2d& thePolyBoxes,
1638 Handle(IMeshData::MapOfInteger) theSkipped)
1640 // Check is the source polygon elementary
1641 if ( meshElementaryPolygon( thePolygon ) )
1644 // Check and correct boundary edges
1645 Standard_Integer aPolyLen = thePolygon.Length();
1646 const Standard_Real aPolyArea = Abs( polyArea( thePolygon, 1, aPolyLen ) );
1647 const Standard_Real aSmallLoopArea = 0.001 * aPolyArea;
1648 for ( Standard_Integer aPolyIt = 1; aPolyIt < aPolyLen; ++aPolyIt )
1650 Standard_Integer aCurEdgeInfo = thePolygon( aPolyIt );
1651 Standard_Integer aCurEdgeId = Abs( aCurEdgeInfo );
1652 const BRepMesh_Edge* aCurEdge = &GetEdge( aCurEdgeId );
1653 if ( aCurEdge->Movability() != BRepMesh_Frontier )
1656 Standard_Integer aCurNodes[2];
1657 getOrientedNodes( *aCurEdge, aCurEdgeInfo > 0, aCurNodes );
1659 gp_Pnt2d aCurPnts[2] = {
1660 GetVertex(aCurNodes[0]).Coord(),
1661 GetVertex(aCurNodes[1]).Coord()
1664 gp_Vec2d aCurVec( aCurPnts[0], aCurPnts[1] );
1666 // check further links
1667 Standard_Integer aNextPolyIt = aPolyIt + 1;
1668 for ( ; aNextPolyIt <= aPolyLen; ++aNextPolyIt )
1670 Standard_Integer aNextEdgeInfo = thePolygon( aNextPolyIt );
1671 Standard_Integer aNextEdgeId = Abs( aNextEdgeInfo );
1672 const BRepMesh_Edge* aNextEdge = &GetEdge( aNextEdgeId );
1673 if ( aNextEdge->Movability() != BRepMesh_Frontier )
1676 Standard_Integer aNextNodes[2];
1677 getOrientedNodes( *aNextEdge, aNextEdgeInfo > 0, aNextNodes );
1679 gp_Pnt2d aNextPnts[2] = {
1680 GetVertex(aNextNodes[0]).Coord(),
1681 GetVertex(aNextNodes[1]).Coord()
1685 BRepMesh_GeomTool::IntFlag aIntFlag = intSegSeg( *aCurEdge, *aNextEdge,
1686 Standard_False, Standard_True, anIntPnt );
1688 if ( aIntFlag == BRepMesh_GeomTool::NoIntersection )
1691 Standard_Boolean isRemoveFromFirst = Standard_False;
1692 Standard_Boolean isAddReplacingEdge = Standard_True;
1693 Standard_Integer aIndexToRemoveTo = aNextPolyIt;
1694 if ( aIntFlag == BRepMesh_GeomTool::Cross )
1696 Standard_Real aLoopArea = polyArea( thePolygon, aPolyIt + 1, aNextPolyIt );
1697 gp_Vec2d aVec1( anIntPnt, aCurPnts [1] );
1698 gp_Vec2d aVec2( anIntPnt, aNextPnts[0] );
1700 aLoopArea += ( aVec1 ^ aVec2 ) / 2.;
1701 if ( Abs( aLoopArea ) > aSmallLoopArea )
1703 aNextNodes[1] = aCurNodes[0];
1704 aNextPnts [1] = aCurPnts [0];
1706 aNextEdgeId = Abs( createAndReplacePolygonLink( aNextNodes, aNextPnts,
1707 aNextPolyIt, BRepMesh_Delaun::Replace, thePolygon, thePolyBoxes ) );
1709 processLoop( aPolyIt, aNextPolyIt, thePolygon, thePolyBoxes );
1713 Standard_Real aDist1 = anIntPnt.SquareDistance(aNextPnts[0]);
1714 Standard_Real aDist2 = anIntPnt.SquareDistance(aNextPnts[1]);
1716 // Choose node with lower distance
1717 const Standard_Boolean isCloseToStart = ( aDist1 < aDist2 );
1718 const Standard_Integer aEndPointIndex = isCloseToStart ? 0 : 1;
1719 aCurNodes[1] = aNextNodes[aEndPointIndex];
1720 aCurPnts [1] = aNextPnts [aEndPointIndex];
1722 if ( isCloseToStart )
1725 // In this context only intersections between frontier edges
1726 // are possible. If intersection between edges of different
1727 // types occured - treat this case as invalid (i.e. result
1728 // might not reflect the expectations).
1729 if ( !theSkipped.IsNull() )
1731 Standard_Integer aSkippedLinkIt = aPolyIt;
1732 for ( ; aSkippedLinkIt <= aIndexToRemoveTo; ++aSkippedLinkIt )
1733 theSkipped->Add( Abs( thePolygon( aSkippedLinkIt ) ) );
1736 else if ( aIntFlag == BRepMesh_GeomTool::PointOnSegment )
1738 // Indentify chopping link
1739 Standard_Boolean isFirstChopping = Standard_False;
1740 Standard_Integer aCheckPointIt = 0;
1741 for ( ; aCheckPointIt < 2; ++aCheckPointIt )
1743 gp_Pnt2d& aRefPoint = aCurPnts[aCheckPointIt];
1744 // Check is second link touches the first one
1745 gp_Vec2d aVec1( aRefPoint, aNextPnts[0] );
1746 gp_Vec2d aVec2( aRefPoint, aNextPnts[1] );
1747 if ( Abs( aVec1 ^ aVec2 ) < Precision )
1749 isFirstChopping = Standard_True;
1754 if ( isFirstChopping )
1756 // Split second link
1757 isAddReplacingEdge = Standard_False;
1758 isRemoveFromFirst = ( aCheckPointIt == 0 );
1760 Standard_Integer aSplitLink[3] = {
1762 aCurNodes [aCheckPointIt],
1766 gp_Pnt2d aSplitPnts[3] = {
1768 aCurPnts [aCheckPointIt],
1772 Standard_Integer aSplitLinkIt = 0;
1773 for ( ; aSplitLinkIt < 2; ++aSplitLinkIt )
1775 createAndReplacePolygonLink( &aSplitLink[aSplitLinkIt],
1776 &aSplitPnts[aSplitLinkIt], aNextPolyIt, ( aSplitLinkIt == 0 ) ?
1777 BRepMesh_Delaun::Replace : BRepMesh_Delaun::InsertAfter,
1778 thePolygon, thePolyBoxes );
1781 processLoop( aPolyIt + aCheckPointIt, aIndexToRemoveTo,
1782 thePolygon, thePolyBoxes );
1787 Standard_Integer aSplitLinkNodes[2] = {
1792 gp_Pnt2d aSplitLinkPnts[2] = {
1796 createAndReplacePolygonLink( aSplitLinkNodes, aSplitLinkPnts,
1797 aPolyIt, BRepMesh_Delaun::InsertAfter, thePolygon, thePolyBoxes );
1799 aCurNodes[1] = aNextNodes[1];
1800 aCurPnts [1] = aNextPnts [1];
1803 processLoop( aPolyIt + 1, aIndexToRemoveTo,
1804 thePolygon, thePolyBoxes );
1807 else if ( aIntFlag == BRepMesh_GeomTool::Glued )
1809 if ( aCurNodes[1] == aNextNodes[0] )
1811 aCurNodes[1] = aNextNodes[1];
1812 aCurPnts [1] = aNextPnts [1];
1814 // TODO: Non-adjacent glued links within the polygon
1816 else if ( aIntFlag == BRepMesh_GeomTool::Same )
1818 processLoop( aPolyIt, aNextPolyIt, thePolygon, thePolyBoxes );
1820 isRemoveFromFirst = Standard_True;
1821 isAddReplacingEdge = Standard_False;
1824 continue; // Not supported type
1826 if ( isAddReplacingEdge )
1828 aCurEdgeId = Abs( createAndReplacePolygonLink( aCurNodes, aCurPnts,
1829 aPolyIt, BRepMesh_Delaun::Replace, thePolygon, thePolyBoxes ) );
1831 aCurEdge = &GetEdge( aCurEdgeId );
1832 aCurVec = gp_Vec2d( aCurPnts[0], aCurPnts[1] );
1835 Standard_Integer aIndexToRemoveFrom =
1836 isRemoveFromFirst ? aPolyIt : aPolyIt + 1;
1838 thePolygon .Remove( aIndexToRemoveFrom, aIndexToRemoveTo );
1839 thePolyBoxes.Remove( aIndexToRemoveFrom, aIndexToRemoveTo );
1841 aPolyLen = thePolygon.Length();
1842 if ( isRemoveFromFirst )
1848 aNextPolyIt = aPolyIt;
1852 IMeshData::SequenceOfInteger* aPolygon1 = &thePolygon;
1853 IMeshData::SequenceOfBndB2d* aPolyBoxes1 = &thePolyBoxes;
1855 Handle(IMeshData::SequenceOfInteger) aPolygon2 = new IMeshData::SequenceOfInteger;
1856 Handle(IMeshData::SequenceOfBndB2d) aPolyBoxes2 = new IMeshData::SequenceOfBndB2d;
1858 NCollection_Sequence<Handle(IMeshData::SequenceOfInteger)> aPolyStack;
1859 NCollection_Sequence<Handle(IMeshData::SequenceOfBndB2d)> aPolyBoxStack;
1862 decomposeSimplePolygon(*aPolygon1, *aPolyBoxes1, *aPolygon2, *aPolyBoxes2);
1863 if (!aPolygon2->IsEmpty())
1865 aPolyStack.Append(aPolygon2);
1866 aPolyBoxStack.Append(aPolyBoxes2);
1868 aPolygon2 = new IMeshData::SequenceOfInteger;
1869 aPolyBoxes2 = new IMeshData::SequenceOfBndB2d;
1872 if (aPolygon1->IsEmpty())
1874 if (!aPolyStack.IsEmpty() && aPolygon1 == &(*aPolyStack.First()))
1876 aPolyStack.Remove(1);
1877 aPolyBoxStack.Remove(1);
1880 if (aPolyStack.IsEmpty())
1883 aPolygon1 = &(*aPolyStack.ChangeFirst());
1884 aPolyBoxes1 = &(*aPolyBoxStack.ChangeFirst());
1889 //=======================================================================
1890 //function : meshElementaryPolygon
1891 //purpose : Triangulation of closed polygon containing only three edges.
1892 //=======================================================================
1893 Standard_Boolean BRepMesh_Delaun::meshElementaryPolygon(
1894 const IMeshData::SequenceOfInteger& thePolygon)
1896 Standard_Integer aPolyLen = thePolygon.Length();
1898 return Standard_True;
1899 else if ( aPolyLen > 3 )
1900 return Standard_False;
1902 // Just create a triangle
1903 Standard_Integer anEdges[3];
1904 Standard_Boolean anEdgesOri[3];
1906 for ( Standard_Integer anEdgeIt = 0; anEdgeIt < 3; ++anEdgeIt )
1908 Standard_Integer anEdgeInfo = thePolygon( anEdgeIt + 1 );
1909 anEdges[anEdgeIt] = Abs( anEdgeInfo );
1910 anEdgesOri[anEdgeIt] = ( anEdgeInfo > 0 );
1913 const BRepMesh_Edge& anEdge1 = GetEdge( anEdges[0] );
1914 const BRepMesh_Edge& anEdge2 = GetEdge( anEdges[1] );
1916 Standard_Integer aNodes[3] = { anEdge1.FirstNode(),
1918 anEdge2.FirstNode() };
1919 if ( aNodes[2] == aNodes[0] ||
1920 aNodes[2] == aNodes[1] )
1922 aNodes[2] = anEdge2.LastNode();
1925 addTriangle( anEdges, anEdgesOri, aNodes );
1926 return Standard_True;
1929 //=======================================================================
1930 //function : meshSimplePolygon
1932 //=======================================================================
1933 void BRepMesh_Delaun::decomposeSimplePolygon(
1934 IMeshData::SequenceOfInteger& thePolygon,
1935 IMeshData::SequenceOfBndB2d& thePolyBoxes,
1936 IMeshData::SequenceOfInteger& thePolygonCut,
1937 IMeshData::SequenceOfBndB2d& thePolyBoxesCut)
1939 // Check is the given polygon elementary
1940 if ( meshElementaryPolygon( thePolygon ) )
1943 thePolyBoxes.Clear();
1947 // Polygon contains more than 3 links
1948 Standard_Integer aFirstEdgeInfo = thePolygon(1);
1949 const BRepMesh_Edge& aFirstEdge = GetEdge( Abs( aFirstEdgeInfo ) );
1951 Standard_Integer aNodes[3];
1952 getOrientedNodes( aFirstEdge, aFirstEdgeInfo > 0, aNodes );
1954 gp_Pnt2d aRefVertices[3];
1955 aRefVertices[0] = GetVertex( aNodes[0] ).Coord();
1956 aRefVertices[1] = GetVertex( aNodes[1] ).Coord();
1958 gp_Vec2d aRefEdgeDir( aRefVertices[0], aRefVertices[1] );
1960 Standard_Real aRefEdgeLen = aRefEdgeDir.Magnitude();
1961 if ( aRefEdgeLen < Precision )
1964 thePolyBoxes.Clear();
1968 aRefEdgeDir /= aRefEdgeLen;
1970 // Find a point with minimum distance respect
1971 // the end of reference link
1972 Standard_Integer aUsedLinkId = 0;
1973 Standard_Real aOptAngle = 0.0;
1974 Standard_Real aMinDist = RealLast();
1975 Standard_Integer aPivotNode = aNodes[1];
1976 Standard_Integer aPolyLen = thePolygon.Length();
1977 for ( Standard_Integer aLinkIt = 3; aLinkIt <= aPolyLen; ++aLinkIt )
1979 Standard_Integer aLinkInfo = thePolygon( aLinkIt );
1980 const BRepMesh_Edge& aNextEdge = GetEdge( Abs( aLinkInfo ) );
1982 aPivotNode = aLinkInfo > 0 ?
1983 aNextEdge.FirstNode() :
1984 aNextEdge.LastNode();
1986 gp_Pnt2d aPivotVertex = GetVertex( aPivotNode ).Coord();
1987 gp_Vec2d aDistanceDir( aRefVertices[1], aPivotVertex );
1989 Standard_Real aDist = aRefEdgeDir ^ aDistanceDir;
1990 Standard_Real aAngle = Abs( aRefEdgeDir.Angle(aDistanceDir) );
1991 Standard_Real anAbsDist = Abs( aDist );
1992 if (anAbsDist < Precision || aDist < 0.)
1995 if ( ( anAbsDist >= aMinDist ) &&
1996 ( aAngle <= aOptAngle || aAngle > AngDeviation90Deg ) )
2001 // Check is the test link crosses the polygon boudaries
2002 Standard_Boolean isIntersect = Standard_False;
2003 for ( Standard_Integer aRefLinkNodeIt = 0; aRefLinkNodeIt < 2; ++aRefLinkNodeIt )
2005 const Standard_Integer& aLinkFirstNode = aNodes[aRefLinkNodeIt];
2006 const gp_Pnt2d& aLinkFirstVertex = aRefVertices[aRefLinkNodeIt];
2009 UpdateBndBox(aLinkFirstVertex.Coord(), aPivotVertex.Coord(), aBox);
2011 BRepMesh_Edge aCheckLink( aLinkFirstNode, aPivotNode, BRepMesh_Free );
2013 Standard_Integer aCheckLinkIt = 2;
2014 for ( ; aCheckLinkIt <= aPolyLen; ++aCheckLinkIt )
2016 if( aCheckLinkIt == aLinkIt )
2019 if ( !aBox.IsOut( thePolyBoxes.Value( aCheckLinkIt ) ) )
2021 const BRepMesh_Edge& aPolyLink =
2022 GetEdge( Abs( thePolygon( aCheckLinkIt ) ) );
2024 if ( aCheckLink.IsEqual( aPolyLink ) )
2027 // intersection is possible...
2029 BRepMesh_GeomTool::IntFlag aIntFlag = intSegSeg( aCheckLink, aPolyLink,
2030 Standard_False, Standard_False, anIntPnt );
2032 if( aIntFlag != BRepMesh_GeomTool::NoIntersection )
2034 isIntersect = Standard_True;
2049 aMinDist = anAbsDist;
2050 aNodes[2] = aPivotNode;
2051 aRefVertices[2] = aPivotVertex;
2052 aUsedLinkId = aLinkIt;
2055 if ( aUsedLinkId == 0 )
2058 thePolyBoxes.Clear();
2063 BRepMesh_Edge aNewEdges[2] = {
2064 BRepMesh_Edge( aNodes[1], aNodes[2], BRepMesh_Free ),
2065 BRepMesh_Edge( aNodes[2], aNodes[0], BRepMesh_Free ) };
2067 Standard_Integer aNewEdgesInfo[3] = {
2069 myMeshData->AddLink( aNewEdges[0] ),
2070 myMeshData->AddLink( aNewEdges[1] ) };
2073 Standard_Integer anEdges[3];
2074 Standard_Boolean anEdgesOri[3];
2075 for ( Standard_Integer aTriEdgeIt = 0; aTriEdgeIt < 3; ++aTriEdgeIt )
2077 const Standard_Integer& anEdgeInfo = aNewEdgesInfo[aTriEdgeIt];
2078 anEdges[aTriEdgeIt] = Abs( anEdgeInfo );
2079 anEdgesOri[aTriEdgeIt] = anEdgeInfo > 0;
2081 addTriangle( anEdges, anEdgesOri, aNodes );
2083 // Create triangle and split the source polygon on two
2084 // parts (if possible) and mesh each part as independent
2086 if ( aUsedLinkId < aPolyLen )
2088 thePolygon.Split(aUsedLinkId, thePolygonCut);
2089 thePolygonCut.Prepend( -aNewEdgesInfo[2] );
2090 thePolyBoxes.Split(aUsedLinkId, thePolyBoxesCut);
2093 UpdateBndBox(aRefVertices[0].Coord(), aRefVertices[2].Coord(), aBox);
2094 thePolyBoxesCut.Prepend( aBox );
2098 thePolygon.Remove ( aPolyLen );
2099 thePolyBoxes.Remove( aPolyLen );
2102 if ( aUsedLinkId > 3 )
2104 thePolygon.SetValue( 1, -aNewEdgesInfo[1] );
2107 UpdateBndBox(aRefVertices[1].Coord(), aRefVertices[2].Coord(), aBox);
2108 thePolyBoxes.SetValue( 1, aBox );
2112 //=======================================================================
2113 //function : RemoveVertex
2114 //purpose : Removes a vertex from the triangulation
2115 //=======================================================================
2116 void BRepMesh_Delaun::RemoveVertex( const BRepMesh_Vertex& theVertex )
2118 BRepMesh_SelectorOfDataStructureOfDelaun aSelector( myMeshData );
2119 aSelector.NeighboursOf( theVertex );
2121 IMeshData::MapOfIntegerInteger aLoopEdges;//( 10, myMeshData->Allocator() );
2123 // Loop on triangles to be destroyed :
2124 IMeshData::IteratorOfMapOfInteger aTriangleIt( aSelector.Elements() );
2125 for ( ; aTriangleIt.More(); aTriangleIt.Next() )
2126 deleteTriangle( aTriangleIt.Key(), aLoopEdges );
2128 IMeshData::SequenceOfBndB2d aBoxes;
2129 IMeshData::SequenceOfInteger aPolygon;
2130 Standard_Integer aLoopEdgesCount = aLoopEdges.Extent();
2131 IMeshData::MapOfIntegerInteger::Iterator aLoopEdgesIt( aLoopEdges );
2133 if ( aLoopEdgesIt.More() )
2135 const BRepMesh_Edge& anEdge = GetEdge( aLoopEdgesIt.Key() );
2136 Standard_Integer aFirstNode = anEdge.FirstNode();
2137 Standard_Integer aLastNode;
2138 Standard_Integer aPivotNode = anEdge.LastNode();
2139 Standard_Integer anEdgeId = aLoopEdgesIt.Key();
2141 Standard_Boolean isPositive = aLoopEdges( anEdgeId ) != 0;
2144 Standard_Integer aTmp;
2146 aFirstNode = aPivotNode;
2149 aPolygon.Append( -anEdgeId );
2152 aPolygon.Append( anEdgeId );
2154 fillBndBox( aBoxes, GetVertex( aFirstNode ), GetVertex( aPivotNode ) );
2156 aLoopEdges.UnBind( anEdgeId );
2158 aLastNode = aFirstNode;
2159 while ( aPivotNode != aLastNode )
2161 IMeshData::ListOfInteger::Iterator aLinkIt( myMeshData->LinksConnectedTo( aPivotNode ) );
2162 for ( ; aLinkIt.More(); aLinkIt.Next() )
2164 if ( aLinkIt.Value() != anEdgeId &&
2165 aLoopEdges.IsBound( aLinkIt.Value() ) )
2167 Standard_Integer aCurrentNode;
2168 anEdgeId = aLinkIt.Value();
2169 const BRepMesh_Edge& anEdge1 = GetEdge( anEdgeId );
2171 aCurrentNode = anEdge1.LastNode();
2172 if ( aCurrentNode != aPivotNode )
2174 aCurrentNode = anEdge1.FirstNode();
2175 aPolygon.Append( -anEdgeId );
2178 aPolygon.Append( anEdgeId );
2180 fillBndBox( aBoxes, GetVertex( aCurrentNode ), GetVertex( aPivotNode ) );
2182 aPivotNode = aCurrentNode;
2183 aLoopEdges.UnBind( anEdgeId );
2188 if ( aLoopEdgesCount <= 0 )
2193 meshPolygon( aPolygon, aBoxes );
2198 //=======================================================================
2199 //function : AddVertices
2200 //purpose : Adds some vertices in the triangulation.
2201 //=======================================================================
2202 void BRepMesh_Delaun::AddVertices(IMeshData::VectorOfInteger& theVertices)
2204 ComparatorOfIndexedVertexOfDelaun aCmp(myMeshData);
2205 std::make_heap(theVertices.begin(), theVertices.end(), aCmp);
2206 std::sort_heap(theVertices.begin(), theVertices.end(), aCmp);
2208 createTrianglesOnNewVertices(theVertices);
2211 //=======================================================================
2212 //function : UseEdge
2213 //purpose : Modify mesh to use the edge. Return True if done
2214 //=======================================================================
2215 Standard_Boolean BRepMesh_Delaun::UseEdge( const Standard_Integer /*theIndex*/ )
2218 const BRepMesh_PairOfIndex& aPair = myMeshData->ElemConnectedTo( theIndex );
2219 if ( aPair.Extent() == 0 )
2221 const BRepMesh_Edge& anEdge = GetEdge( theIndex );
2223 Standard_Integer aStartNode, aPivotNode, anOtherNode;
2224 aStartNode = anEdge.FirstNode();
2225 aPivotNode = anEdge.LastNode();
2227 const BRepMesh_ListOfInteger& aStartNodeNeighbors = myMeshData->LinkNeighboursOf( aStartNode );
2228 const BRepMesh_ListOfInteger& aPivotNodeNeighbors = myMeshData->LinkNeighboursOf( aPivotNode );
2230 if ( aStartNodeNeighbors.Extent() > 0 &&
2231 aPivotNodeNeighbors.Extent() > 0 )
2233 const BRepMesh_Vertex& aStartVertex = GetVertex( aStartNode );
2234 const BRepMesh_Vertex& aPivotVertex = GetVertex( aPivotNode );
2236 gp_XY aVEdge ( aPivotVertex.Coord() );
2237 aVEdge.Subtract( aStartVertex.Coord() );
2239 Standard_Real anAngle = 0.;
2240 Standard_Real anAngleMin = RealLast();
2241 Standard_Real anAngleMax = RealFirst();
2242 Standard_Integer aLeftEdge = 0, aRightEdge = 0;
2244 BRepMesh_ListOfInteger::Iterator aNeighborIt( aPivotNodeNeighbors );
2245 for ( ; aNeighborIt.More(); aNeighborIt.Next() )
2247 Standard_Integer anEdgeId = aNeighborIt.Value();
2248 if ( anEdgeId != theIndex )
2250 const BRepMesh_Edge& aNextEdge = GetEdge( anEdgeId );
2252 Standard_Boolean isInMesh = Standard_True;
2253 if ( aNextEdge.Movability() == BRepMesh_Free )
2255 if ( myMeshData->ElemConnectedTo( anEdgeId ).IsEmpty() )
2256 isInMesh = Standard_False;
2261 anOtherNode = aNextEdge.FirstNode();
2262 if ( anOtherNode == aPivotNode )
2263 anOtherNode = aNextEdge.LastNode();
2265 gp_XY aVEdgeCur = GetVertex( anOtherNode ).Coord();
2266 aVEdgeCur.Subtract( aPivotVertex.Coord() );
2268 anAngle = gp_Vec2d( aVEdge ).Angle( gp_Vec2d( aVEdgeCur ) );
2271 if ( anAngle > anAngleMax )
2273 anAngleMax = anAngle;
2274 aLeftEdge = anEdgeId;
2276 if ( anAngle < anAngleMin )
2278 anAngleMin = anAngle;
2279 aRightEdge = anEdgeId;
2284 if ( aLeftEdge > 0 )
2286 if (aLeftEdge==aRightEdge)
2296 return Standard_False;
2299 //=======================================================================
2300 //function : getEdgesByType
2301 //purpose : Gives the list of edges with type defined by input parameter
2302 //=======================================================================
2303 Handle(IMeshData::MapOfInteger) BRepMesh_Delaun::getEdgesByType(
2304 const BRepMesh_DegreeOfFreedom theEdgeType ) const
2306 Handle(NCollection_IncAllocator) anAlloc = new NCollection_IncAllocator;
2307 Handle(IMeshData::MapOfInteger) aResult = new IMeshData::MapOfInteger;
2308 IMeshData::IteratorOfMapOfInteger anEdgeIt( myMeshData->LinksOfDomain() );
2310 for ( ; anEdgeIt.More(); anEdgeIt.Next() )
2312 Standard_Integer anEdge = anEdgeIt.Key();
2313 Standard_Boolean isToAdd = (theEdgeType == BRepMesh_Free) ?
2314 (myMeshData->ElementsConnectedTo( anEdge ).Extent() <= 1) :
2315 (GetEdge( anEdge ).Movability() == theEdgeType);
2318 aResult->Add( anEdge );
2324 //=======================================================================
2325 //function : calculateDist
2326 //purpose : Calculates distances between the given point and edges of
2328 //=======================================================================
2329 Standard_Real BRepMesh_Delaun::calculateDist( const gp_XY theVEdges[3],
2330 const gp_XY thePoints[3],
2331 const BRepMesh_Vertex& theVertex,
2332 Standard_Real theDistance[3],
2333 Standard_Real theSqModulus[3],
2334 Standard_Integer& theEdgeOn ) const
2336 Standard_Real aMinDist = RealLast();
2337 for( Standard_Integer i = 0; i < 3; ++i )
2339 theSqModulus[i] = theVEdges[i].SquareModulus();
2340 if ( theSqModulus[i] <= Precision2 )
2343 theDistance[i] = theVEdges[i] ^ ( theVertex.Coord() - thePoints[i] );
2345 Standard_Real aDist = theDistance[i] * theDistance[i];
2346 aDist /= theSqModulus[i];
2348 if ( aDist < aMinDist )
2358 //=======================================================================
2359 //function : Contains
2360 //purpose : Test if triangle of index <TrianIndex> contains geometricaly
2361 // <theVertex>. If <theEdgeOn> is != 0 then theVertex is on Edge
2362 // of index <theEdgeOn>
2363 //=======================================================================
2364 Standard_Boolean BRepMesh_Delaun::Contains( const Standard_Integer theTriangleId,
2365 const BRepMesh_Vertex& theVertex,
2366 const Standard_Real theSqTolerance,
2367 Standard_Integer& theEdgeOn) const
2371 Standard_Integer p[3];
2373 const BRepMesh_Triangle& aElement = GetTriangle( theTriangleId );
2374 const Standard_Integer(&e)[3] = aElement.myEdges;
2376 const BRepMesh_Edge* anEdges[3] = { &GetEdge( e[0] ),
2380 myMeshData->ElementNodes(aElement, p);
2383 aPoints[0] = GetVertex( p[0] ).Coord();
2384 aPoints[1] = GetVertex( p[1] ).Coord();
2385 aPoints[2] = GetVertex( p[2] ).Coord();
2388 aVEdges[0] = aPoints[1];
2389 aVEdges[0].Subtract( aPoints[0] );
2391 aVEdges[1] = aPoints[2];
2392 aVEdges[1].Subtract( aPoints[1] );
2394 aVEdges[2] = aPoints[0];
2395 aVEdges[2].Subtract( aPoints[2] );
2397 Standard_Real aDistance[3];
2398 Standard_Real aSqModulus[3];
2400 Standard_Real aSqMinDist;
2401 Standard_Integer aEdgeOnId;
2402 aSqMinDist = calculateDist( aVEdges, aPoints, theVertex, aDistance, aSqModulus, aEdgeOnId );
2403 if ( aSqMinDist < 0 )
2404 return Standard_False;
2406 const Standard_Boolean isNotFree = (anEdges[aEdgeOnId]->Movability() != BRepMesh_Free);
2407 if ( aSqMinDist > theSqTolerance )
2409 if (isNotFree && aDistance[aEdgeOnId] < ( aSqModulus[aEdgeOnId] / 5. ))
2410 theEdgeOn = e[aEdgeOnId];
2413 return Standard_False;
2415 theEdgeOn = e[aEdgeOnId];
2417 return (aDistance[0] >= 0. && aDistance[1] >= 0. && aDistance[2] >= 0.);
2420 //=============================================================================
2421 //function : intSegSeg
2422 //purpose : Checks intersection between the two segments.
2423 //=============================================================================
2424 BRepMesh_GeomTool::IntFlag BRepMesh_Delaun::intSegSeg(
2425 const BRepMesh_Edge& theEdg1,
2426 const BRepMesh_Edge& theEdg2,
2427 const Standard_Boolean isConsiderEndPointTouch,
2428 const Standard_Boolean isConsiderPointOnEdge,
2429 gp_Pnt2d& theIntPnt) const
2431 gp_XY p1, p2, p3, p4;
2432 p1 = GetVertex( theEdg1.FirstNode() ).Coord();
2433 p2 = GetVertex( theEdg1.LastNode() ).Coord();
2434 p3 = GetVertex( theEdg2.FirstNode() ).Coord();
2435 p4 = GetVertex( theEdg2.LastNode() ).Coord();
2437 return BRepMesh_GeomTool::IntSegSeg(p1, p2, p3, p4,
2438 isConsiderEndPointTouch, isConsiderPointOnEdge, theIntPnt);
2441 //=============================================================================
2442 //function : polyArea
2443 //purpose : Returns area of the loop of the given polygon defined by indices
2444 // of its start and end links.
2445 //=============================================================================
2446 Standard_Real BRepMesh_Delaun::polyArea(const IMeshData::SequenceOfInteger& thePolygon,
2447 const Standard_Integer theStartIndex,
2448 const Standard_Integer theEndIndex) const
2450 Standard_Real aArea = 0.0;
2451 Standard_Integer aPolyLen = thePolygon.Length();
2452 if ( theStartIndex >= theEndIndex ||
2453 theStartIndex > aPolyLen )
2457 Standard_Integer aCurEdgeInfo = thePolygon( theStartIndex );
2458 Standard_Integer aCurEdgeId = Abs( aCurEdgeInfo );
2459 const BRepMesh_Edge* aCurEdge = &GetEdge( aCurEdgeId );
2461 Standard_Integer aNodes[2];
2462 getOrientedNodes( *aCurEdge, aCurEdgeInfo > 0, aNodes );
2464 gp_Pnt2d aRefPnt = GetVertex( aNodes[0] ).Coord();
2465 Standard_Integer aPolyIt = theStartIndex + 1;
2466 for ( ; aPolyIt <= theEndIndex; ++aPolyIt )
2468 aCurEdgeInfo = thePolygon( aPolyIt );
2469 aCurEdgeId = Abs( aCurEdgeInfo );
2470 aCurEdge = &GetEdge( aCurEdgeId );
2472 getOrientedNodes( *aCurEdge, aCurEdgeInfo > 0, aNodes );
2473 gp_Vec2d aVec1( aRefPnt, GetVertex( aNodes[0] ).Coord() );
2474 gp_Vec2d aVec2( aRefPnt, GetVertex( aNodes[1] ).Coord() );
2476 aArea += aVec1 ^ aVec2;
2483 //=======================================================================
2484 //function : BRepMesh_DumpPoly
2486 //=======================================================================
2487 #include <TopoDS_Compound.hxx>
2488 #include <BRep_Builder.hxx>
2489 #include <Standard_ErrorHandler.hxx>
2490 #include <BRepBuilderAPI_MakeEdge.hxx>
2491 #include <BRepTools.hxx>
2492 Standard_CString BRepMesh_DumpPoly(void* thePolygon,
2493 void* theMeshHandlePtr,
2494 Standard_CString theFileNameStr)
2496 if (thePolygon == 0 || theFileNameStr == 0)
2498 return "Error: file name or polygon data is null";
2501 IMeshData::SequenceOfInteger& aPolygon = *(IMeshData::SequenceOfInteger*)thePolygon;
2503 Handle(BRepMesh_DataStructureOfDelaun) aMeshData =
2504 *(Handle(BRepMesh_DataStructureOfDelaun)*)theMeshHandlePtr;
2506 if (aMeshData.IsNull())
2507 return "Error: mesh data is empty";
2509 TopoDS_Compound aMesh;
2510 BRep_Builder aBuilder;
2511 aBuilder.MakeCompound(aMesh);
2517 IMeshData::SequenceOfInteger::Iterator aLinksIt(aPolygon);
2518 for (; aLinksIt.More(); aLinksIt.Next())
2520 const BRepMesh_Edge& aLink = aMeshData->GetLink(Abs(aLinksIt.Value()));
2523 for (Standard_Integer i = 0; i < 2; ++i)
2525 const Standard_Integer aNodeId =
2526 (i == 0) ? aLink.FirstNode() : aLink.LastNode();
2528 const gp_XY& aNode = aMeshData->GetNode(aNodeId).Coord();
2529 aPnt[i] = gp_Pnt(aNode.X(), aNode.Y(), 0.);
2532 if (aPnt[0].SquareDistance(aPnt[1]) < Precision::SquareConfusion())
2535 aBuilder.Add(aMesh, BRepBuilderAPI_MakeEdge(aPnt[0], aPnt[1]));
2538 if (!BRepTools::Write(aMesh, theFileNameStr))
2539 return "Error: write failed";
2541 catch (Standard_Failure const& anException)
2543 return anException.GetMessageString();
2546 return theFileNameStr;