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>
39 const Standard_Real AngDeviation1Deg = M_PI/180.;
40 const Standard_Real AngDeviation90Deg = 90 * AngDeviation1Deg;
41 const Standard_Real Angle2PI = 2 * M_PI;
43 const Standard_Real Precision = Precision::PConfusion();
44 const Standard_Real Precision2 = Precision * Precision;
47 //! Sort two points in projection on vector (1,1)
48 struct ComparatorOfVertexOfDelaun
50 bool operator() (const BRepMesh_Vertex& theLeft, const BRepMesh_Vertex& theRight)
52 return theLeft.Coord().X() + theLeft.Coord().Y() < theRight.Coord().X() + theRight.Coord().Y();
56 //! Sort two points in projection on vector (1,1)
57 struct ComparatorOfIndexedVertexOfDelaun
60 ComparatorOfIndexedVertexOfDelaun (const Handle(BRepMesh_DataStructureOfDelaun)& theDS)
61 : myStructure(theDS) {}
63 bool operator() (Standard_Integer theLeft, Standard_Integer theRight)
65 const BRepMesh_Vertex& aLeft = myStructure->GetNode(theLeft);
66 const BRepMesh_Vertex& aRight = myStructure->GetNode(theRight);
67 return ComparatorOfVertexOfDelaun() (aLeft, aRight);
71 Handle(BRepMesh_DataStructureOfDelaun) myStructure;
74 void UpdateBndBox(const gp_XY& thePnt1, const gp_XY& thePnt2, Bnd_B2d& theBox)
76 theBox.Add( thePnt1 );
77 theBox.Add( thePnt2 );
78 theBox.Enlarge(Precision);
80 } // anonymous namespace
82 //=======================================================================
83 //function : BRepMesh_Delaun
85 //=======================================================================
86 BRepMesh_Delaun::BRepMesh_Delaun (
87 const Handle(BRepMesh_DataStructureOfDelaun)& theOldMesh,
88 const Standard_Integer theCellsCountU,
89 const Standard_Integer theCellsCountV,
90 const Standard_Boolean isFillCircles)
91 : myMeshData ( theOldMesh ),
92 myCircles (new NCollection_IncAllocator(
93 IMeshData::MEMORY_BLOCK_SIZE_HUGE)),
95 myInitCircles (Standard_False)
99 InitCirclesTool (theCellsCountU, theCellsCountV);
103 //=======================================================================
104 //function : BRepMesh_Delaun
105 //purpose : Creates the triangulation with an empty Mesh data structure
106 //=======================================================================
107 BRepMesh_Delaun::BRepMesh_Delaun(IMeshData::Array1OfVertexOfDelaun& theVertices)
108 : myCircles (theVertices.Length(), new NCollection_IncAllocator(
109 IMeshData::MEMORY_BLOCK_SIZE_HUGE)),
111 myInitCircles (Standard_False)
113 if ( theVertices.Length() > 2 )
115 myMeshData = new BRepMesh_DataStructureOfDelaun(
116 new NCollection_IncAllocator(IMeshData::MEMORY_BLOCK_SIZE_HUGE),
117 theVertices.Length() );
122 //=======================================================================
123 //function : BRepMesh_Delaun
124 //purpose : Creates the triangulation with and existent Mesh data structure
125 //=======================================================================
126 BRepMesh_Delaun::BRepMesh_Delaun(
127 const Handle(BRepMesh_DataStructureOfDelaun)& theOldMesh,
128 IMeshData::Array1OfVertexOfDelaun& theVertices)
129 : myMeshData( theOldMesh ),
130 myCircles ( theVertices.Length(), new NCollection_IncAllocator(
131 IMeshData::MEMORY_BLOCK_SIZE_HUGE)),
133 myInitCircles (Standard_False)
135 if ( theVertices.Length() > 2 )
141 //=======================================================================
142 //function : BRepMesh_Delaun
143 //purpose : Creates the triangulation with and existent Mesh data structure
144 //=======================================================================
145 BRepMesh_Delaun::BRepMesh_Delaun(
146 const Handle(BRepMesh_DataStructureOfDelaun)& theOldMesh,
147 IMeshData::VectorOfInteger& theVertexIndices)
148 : myMeshData( theOldMesh ),
149 myCircles ( theVertexIndices.Length(), new NCollection_IncAllocator(
150 IMeshData::MEMORY_BLOCK_SIZE_HUGE)),
152 myInitCircles (Standard_False)
154 perform(theVertexIndices);
157 //=======================================================================
158 //function : BRepMesh_Delaun
159 //purpose : Creates the triangulation with and existent Mesh data structure
160 //=======================================================================
161 BRepMesh_Delaun::BRepMesh_Delaun (const Handle (BRepMesh_DataStructureOfDelaun)& theOldMesh,
162 IMeshData::VectorOfInteger& theVertexIndices,
163 const Standard_Integer theCellsCountU,
164 const Standard_Integer theCellsCountV)
165 : myMeshData (theOldMesh),
166 myCircles (theVertexIndices.Length (), new NCollection_IncAllocator(
167 IMeshData::MEMORY_BLOCK_SIZE_HUGE)),
169 myInitCircles (Standard_False)
171 perform (theVertexIndices, theCellsCountU, theCellsCountV);
174 //=======================================================================
176 //purpose : Initializes the triangulation with an Array of Vertex
177 //=======================================================================
178 void BRepMesh_Delaun::Init(IMeshData::Array1OfVertexOfDelaun& theVertices)
180 Standard_Integer aLowerIdx = theVertices.Lower();
181 Standard_Integer anUpperIdx = theVertices.Upper();
182 IMeshData::VectorOfInteger aVertexIndexes(theVertices.Size());
184 Standard_Integer anIndex = aLowerIdx;
185 for ( ; anIndex <= anUpperIdx; ++anIndex )
187 aVertexIndexes.Append(myMeshData->AddNode( theVertices( anIndex ) ));
190 perform( aVertexIndexes );
193 //=======================================================================
194 //function : InitCirclesTool
196 //=======================================================================
197 void BRepMesh_Delaun::InitCirclesTool (const Standard_Integer theCellsCountU,
198 const Standard_Integer theCellsCountV)
201 for (Standard_Integer aNodeIt = 1; aNodeIt <= myMeshData->NbNodes(); ++aNodeIt)
203 aBox.Add (gp_Pnt2d (GetVertex (aNodeIt).Coord ()));
205 aBox.Enlarge (Precision);
207 initCirclesTool (aBox, theCellsCountU, theCellsCountV);
209 IMeshData::IteratorOfMapOfInteger aTriangleIt (myMeshData->ElementsOfDomain());
210 for (; aTriangleIt.More(); aTriangleIt.Next())
212 Standard_Integer aNodesIndices[3];
213 const BRepMesh_Triangle& aTriangle = myMeshData->GetElement (aTriangleIt.Key());
214 myMeshData->ElementNodes (aTriangle, aNodesIndices);
215 myCircles.Bind (aTriangleIt.Key(),
216 GetVertex( aNodesIndices[0] ).Coord(),
217 GetVertex( aNodesIndices[1] ).Coord(),
218 GetVertex( aNodesIndices[2] ).Coord());
222 //=======================================================================
223 //function : initCirclesTool
225 //=======================================================================
226 void BRepMesh_Delaun::initCirclesTool (const Bnd_Box2d& theBox,
227 const Standard_Integer theCellsCountU,
228 const Standard_Integer theCellsCountV)
230 Standard_Real aMinX, aMinY, aMaxX, aMaxY;
231 theBox.Get ( aMinX, aMinY, aMaxX, aMaxY );
232 const Standard_Real aDeltaX = aMaxX - aMinX;
233 const Standard_Real aDeltaY = aMaxY - aMinY;
235 Standard_Integer aScaler = 2;
236 if ( myMeshData->NbNodes() > 100 )
240 else if( myMeshData->NbNodes() > 1000 )
245 myCircles.SetMinMaxSize( gp_XY( aMinX, aMinY ), gp_XY( aMaxX, aMaxY ) );
246 myCircles.SetCellSize ( aDeltaX / Max (theCellsCountU, aScaler),
247 aDeltaY / Max (theCellsCountV, aScaler));
249 myInitCircles = Standard_True;
252 //=======================================================================
254 //purpose : Create super mesh and run triangulation procedure
255 //=======================================================================
256 void BRepMesh_Delaun::perform(IMeshData::VectorOfInteger& theVertexIndices,
257 const Standard_Integer theCellsCountU /* = -1 */,
258 const Standard_Integer theCellsCountV /* = -1 */)
260 if (theVertexIndices.Length () <= 2)
266 Standard_Integer anIndex = theVertexIndices.Lower ();
267 Standard_Integer anUpper = theVertexIndices.Upper ();
268 for (; anIndex <= anUpper; ++anIndex)
270 aBox.Add (gp_Pnt2d (GetVertex (theVertexIndices (anIndex)).Coord ()));
273 aBox.Enlarge (Precision);
275 initCirclesTool (aBox, theCellsCountU, theCellsCountV);
278 ComparatorOfIndexedVertexOfDelaun aCmp(myMeshData);
279 std::make_heap(theVertexIndices.begin(), theVertexIndices.end(), aCmp);
280 std::sort_heap(theVertexIndices.begin(), theVertexIndices.end(), aCmp);
282 compute( theVertexIndices );
285 //=======================================================================
286 //function : superMesh
287 //purpose : Build the super mesh
288 //=======================================================================
289 void BRepMesh_Delaun::superMesh(const Bnd_Box2d& theBox)
291 Standard_Real aMinX, aMinY, aMaxX, aMaxY;
292 theBox.Get ( aMinX, aMinY, aMaxX, aMaxY );
293 Standard_Real aDeltaX = aMaxX - aMinX;
294 Standard_Real aDeltaY = aMaxY - aMinY;
296 Standard_Real aDeltaMin = Min( aDeltaX, aDeltaY );
297 Standard_Real aDeltaMax = Max( aDeltaX, aDeltaY );
298 Standard_Real aDelta = aDeltaX + aDeltaY;
300 mySupVert.Append (myMeshData->AddNode(
301 BRepMesh_Vertex( ( aMinX + aMaxX ) / 2, aMaxY + aDeltaMax, BRepMesh_Free ) ) );
303 mySupVert.Append (myMeshData->AddNode(
304 BRepMesh_Vertex( aMinX - aDelta, aMinY - aDeltaMin, BRepMesh_Free ) ) );
306 mySupVert.Append (myMeshData->AddNode(
307 BRepMesh_Vertex( aMaxX + aDelta, aMinY - aDeltaMin, BRepMesh_Free ) ) );
309 Standard_Integer e[3];
310 Standard_Boolean o[3];
311 for (Standard_Integer aNodeId = 0; aNodeId < 3; ++aNodeId)
313 Standard_Integer aFirstNode = aNodeId;
314 Standard_Integer aLastNode = (aNodeId + 1) % 3;
315 Standard_Integer aLinkIndex = myMeshData->AddLink( BRepMesh_Edge(
316 mySupVert[aFirstNode], mySupVert[aLastNode], BRepMesh_Free ) );
318 e[aNodeId] = Abs(aLinkIndex);
319 o[aNodeId] = (aLinkIndex > 0);
322 mySupTrian = BRepMesh_Triangle(e, o, BRepMesh_Free);
325 //=======================================================================
326 //function : deleteTriangle
327 //purpose : Deletes the triangle with the given index and adds the free
328 // edges into the map.
329 // When an edge is suppressed more than one time it is destroyed.
330 //=======================================================================
331 void BRepMesh_Delaun::deleteTriangle(const Standard_Integer theIndex,
332 IMeshData::MapOfIntegerInteger& theLoopEdges )
336 myCircles.Delete (theIndex);
339 const BRepMesh_Triangle& aElement = GetTriangle(theIndex);
340 const Standard_Integer(&e)[3] = aElement.myEdges;
341 const Standard_Boolean(&o)[3] = aElement.myOrientations;
343 myMeshData->RemoveElement( theIndex );
345 for ( Standard_Integer i = 0; i < 3; ++i )
347 if ( !theLoopEdges.Bind( e[i], o[i] ) )
349 theLoopEdges.UnBind( e[i] );
350 myMeshData->RemoveLink( e[i] );
355 //=======================================================================
357 //purpose : Computes the triangulation and add the vertices edges and
358 // triangles to the Mesh data structure
359 //=======================================================================
360 void BRepMesh_Delaun::compute(IMeshData::VectorOfInteger& theVertexIndexes)
362 // Insertion of edges of super triangles in the list of free edges:
363 Handle(NCollection_IncAllocator) aAllocator = new NCollection_IncAllocator(
364 IMeshData::MEMORY_BLOCK_SIZE_HUGE);
366 IMeshData::MapOfIntegerInteger aLoopEdges(10, aAllocator);
367 const Standard_Integer(&e)[3] = mySupTrian.myEdges;
369 aLoopEdges.Bind( e[0], Standard_True );
370 aLoopEdges.Bind( e[1], Standard_True );
371 aLoopEdges.Bind( e[2], Standard_True );
373 if ( theVertexIndexes.Length() > 0 )
375 // Creation of 3 trianglers with the first node and the edges of the super triangle:
376 Standard_Integer anVertexIdx = theVertexIndexes.Lower();
377 createTriangles( theVertexIndexes( anVertexIdx ), aLoopEdges );
379 // Add other nodes to the mesh
380 createTrianglesOnNewVertices (theVertexIndexes, Message_ProgressRange());
383 RemoveAuxElements ();
386 //=======================================================================
387 //function : RemoveAuxElements
389 //=======================================================================
390 void BRepMesh_Delaun::RemoveAuxElements ()
392 Handle (NCollection_IncAllocator) aAllocator = new NCollection_IncAllocator (
393 IMeshData::MEMORY_BLOCK_SIZE_HUGE);
395 IMeshData::MapOfIntegerInteger aLoopEdges (10, aAllocator);
397 // Destruction of triangles containing a top of the super triangle
398 BRepMesh_SelectorOfDataStructureOfDelaun aSelector (myMeshData);
399 for (Standard_Integer aSupVertId = 0; aSupVertId < mySupVert.Size(); ++aSupVertId)
400 aSelector.NeighboursOfNode( mySupVert[aSupVertId] );
402 IMeshData::IteratorOfMapOfInteger aFreeTriangles( aSelector.Elements() );
403 for ( ; aFreeTriangles.More(); aFreeTriangles.Next() )
404 deleteTriangle( aFreeTriangles.Key(), aLoopEdges );
406 // All edges that remain free are removed from aLoopEdges;
407 // only the boundary edges of the triangulation remain there
408 IMeshData::MapOfIntegerInteger::Iterator aFreeEdges( aLoopEdges );
409 for ( ; aFreeEdges.More(); aFreeEdges.Next() )
411 if ( myMeshData->ElementsConnectedTo( aFreeEdges.Key() ).IsEmpty() )
412 myMeshData->RemoveLink( aFreeEdges.Key() );
415 // The tops of the super triangle are destroyed
416 for (Standard_Integer aSupVertId = 0; aSupVertId < mySupVert.Size (); ++aSupVertId)
417 myMeshData->RemoveNode( mySupVert[aSupVertId] );
420 //=======================================================================
421 //function : createTriangles
422 //purpose : Creates the triangles beetween the node and the polyline.
423 //=======================================================================
424 void BRepMesh_Delaun::createTriangles(const Standard_Integer theVertexIndex,
425 IMeshData::MapOfIntegerInteger& thePoly)
427 IMeshData::ListOfInteger aLoopEdges, anExternalEdges;
428 const gp_XY& aVertexCoord = myMeshData->GetNode( theVertexIndex ).Coord();
430 IMeshData::MapOfIntegerInteger::Iterator anEdges( thePoly );
431 for ( ; anEdges.More(); anEdges.Next() )
433 Standard_Integer anEdgeId = anEdges.Key();
434 const BRepMesh_Edge& anEdge = GetEdge( anEdgeId );
436 Standard_Boolean isPositive = thePoly( anEdgeId ) != 0;
438 Standard_Integer aNodes[3];
441 aNodes[0] = anEdge.FirstNode();
442 aNodes[2] = anEdge.LastNode();
446 aNodes[0] = anEdge.LastNode();
447 aNodes[2] = anEdge.FirstNode();
449 aNodes[1] = theVertexIndex;
451 const BRepMesh_Vertex& aFirstVertex = GetVertex( aNodes[0] );
452 const BRepMesh_Vertex& aLastVertex = GetVertex( aNodes[2] );
454 gp_XY anEdgeDir( aLastVertex.Coord() - aFirstVertex.Coord() );
455 Standard_Real anEdgeLen = anEdgeDir.Modulus();
456 if ( anEdgeLen < Precision )
459 anEdgeDir.SetCoord( anEdgeDir.X() / anEdgeLen,
460 anEdgeDir.Y() / anEdgeLen );
462 gp_XY aFirstLinkDir( aFirstVertex.Coord() - aVertexCoord );
463 gp_XY aLastLinkDir ( aVertexCoord - aLastVertex.Coord() );
465 Standard_Real aDist12 = aFirstLinkDir ^ anEdgeDir;
466 Standard_Real aDist23 = anEdgeDir ^ aLastLinkDir;
467 if ( Abs( aDist12 ) < Precision ||
468 Abs( aDist23 ) < Precision )
473 BRepMesh_Edge aFirstLink( aNodes[1], aNodes[0], BRepMesh_Free );
474 BRepMesh_Edge aLastLink ( aNodes[2], aNodes[1], BRepMesh_Free );
476 Standard_Integer anEdgesInfo[3] = {
477 myMeshData->AddLink( aFirstLink ),
478 isPositive ? anEdgeId : -anEdgeId,
479 myMeshData->AddLink( aLastLink ) };
481 Standard_Boolean isSensOK = (aDist12 > 0. && aDist23 > 0.);
484 Standard_Integer anEdgeIds[3];
485 Standard_Boolean anEdgesOri[3];
486 for ( Standard_Integer aTriLinkIt = 0; aTriLinkIt < 3; ++aTriLinkIt )
488 const Standard_Integer& anEdgeInfo = anEdgesInfo[aTriLinkIt];
489 anEdgeIds[aTriLinkIt] = Abs( anEdgeInfo );
490 anEdgesOri[aTriLinkIt] = anEdgeInfo > 0;
493 addTriangle(anEdgeIds, anEdgesOri, aNodes );
498 aLoopEdges.Append( anEdges.Key() );
500 aLoopEdges.Append( -anEdges.Key() );
502 if ( aFirstLinkDir.SquareModulus() > aLastLinkDir.SquareModulus() )
503 anExternalEdges.Append( Abs( anEdgesInfo[0] ) );
505 anExternalEdges.Append( Abs( anEdgesInfo[2] ) );
510 while ( !anExternalEdges.IsEmpty() )
512 const BRepMesh_PairOfIndex& aPair =
513 myMeshData->ElementsConnectedTo( Abs( anExternalEdges.First() ) );
516 if ( !aPair.IsEmpty() )
517 deleteTriangle( aPair.FirstIndex(), thePoly );
519 anExternalEdges.RemoveFirst();
522 for ( anEdges.Initialize( thePoly ); anEdges.More(); anEdges.Next() )
524 if ( myMeshData->ElementsConnectedTo( anEdges.Key() ).IsEmpty() )
525 myMeshData->RemoveLink( anEdges.Key() );
528 while ( !aLoopEdges.IsEmpty() )
530 const BRepMesh_Edge& anEdge = GetEdge( Abs( aLoopEdges.First() ) );
531 if ( anEdge.Movability() != BRepMesh_Deleted )
533 Standard_Integer anEdgeIdx = aLoopEdges.First();
534 meshLeftPolygonOf( Abs( anEdgeIdx ), ( anEdgeIdx > 0 ) );
537 aLoopEdges.RemoveFirst();
541 //=======================================================================
542 //function : createTrianglesOnNewVertices
543 //purpose : Creation of triangles from the new nodes
544 //=======================================================================
545 void BRepMesh_Delaun::createTrianglesOnNewVertices(
546 IMeshData::VectorOfInteger& theVertexIndexes,
547 const Message_ProgressRange& theRange)
549 Handle(NCollection_IncAllocator) aAllocator =
550 new NCollection_IncAllocator(IMeshData::MEMORY_BLOCK_SIZE_HUGE);
552 Standard_Real aTolU, aTolV;
553 myMeshData->Data()->GetTolerance(aTolU, aTolV);
554 const Standard_Real aSqTol = aTolU * aTolU + aTolV * aTolV;
556 // Insertion of nodes :
557 Standard_Boolean isModify = Standard_True;
559 Standard_Integer anIndex = theVertexIndexes.Lower();
560 Standard_Integer anUpper = theVertexIndexes.Upper();
561 Message_ProgressScope aPS(theRange, "Create triangles on new vertices", anUpper);
562 for (; anIndex <= anUpper; ++anIndex, aPS.Next())
568 aAllocator->Reset(Standard_False);
569 IMeshData::MapOfIntegerInteger aLoopEdges(10, aAllocator);
571 Standard_Integer aVertexIdx = theVertexIndexes( anIndex );
572 const BRepMesh_Vertex& aVertex = GetVertex( aVertexIdx );
574 // Iterator in the list of indexes of circles containing the node
575 IMeshData::ListOfInteger& aCirclesList = myCircles.Select( aVertex.Coord() );
577 Standard_Integer onEgdeId = 0, aTriangleId = 0;
578 IMeshData::ListOfInteger::Iterator aCircleIt( aCirclesList );
579 for ( ; aCircleIt.More(); aCircleIt.Next() )
581 // To add a node in the mesh it is necessary to check conditions:
582 // - the node should be within the boundaries of the mesh and so in an existing triangle
583 // - all adjacent triangles should belong to a component connected with this triangle
584 if ( Contains( aCircleIt.Value(), aVertex, aSqTol, onEgdeId ) )
586 if (onEgdeId != 0 && GetEdge(onEgdeId).Movability() != BRepMesh_Free)
588 // We can skip free vertex too close to the frontier edge.
589 if (aVertex.Movability() == BRepMesh_Free)
592 // However, we should add vertex that have neighboring frontier edges.
595 // Remove triangle even if it contains frontier edge in order
596 // to prevent appearance of incorrect configurations like free
597 // edge glued with frontier #26407
598 aTriangleId = aCircleIt.Value();
599 aCirclesList.Remove( aCircleIt );
604 if ( aTriangleId > 0 )
606 deleteTriangle( aTriangleId, aLoopEdges );
608 isModify = Standard_True;
609 while ( isModify && !aCirclesList.IsEmpty() )
611 isModify = Standard_False;
612 IMeshData::ListOfInteger::Iterator aCircleIt1( aCirclesList );
613 for ( ; aCircleIt1.More(); aCircleIt1.Next() )
615 const BRepMesh_Triangle& aElement = GetTriangle(aCircleIt1.Value());
616 const Standard_Integer(&e)[3] = aElement.myEdges;
618 if ( aLoopEdges.IsBound( e[0] ) ||
619 aLoopEdges.IsBound( e[1] ) ||
620 aLoopEdges.IsBound( e[2] ) )
622 isModify = Standard_True;
623 deleteTriangle( aCircleIt1.Value(), aLoopEdges );
624 aCirclesList.Remove( aCircleIt1 );
630 // Creation of triangles with the current node and free edges
631 // and removal of these edges from the list of free edges
632 createTriangles( aVertexIdx, aLoopEdges );
636 ProcessConstraints();
639 //=======================================================================
640 //function : insertInternalEdges
642 //=======================================================================
643 void BRepMesh_Delaun::insertInternalEdges()
645 Handle(IMeshData::MapOfInteger) anInternalEdges = InternalEdges();
647 // Destruction of triancles intersecting internal edges
648 // and their replacement by makeshift triangles
649 IMeshData::IteratorOfMapOfInteger anInernalEdgesIt( *anInternalEdges );
650 for ( ; anInernalEdgesIt.More(); anInernalEdgesIt.Next() )
652 const Standard_Integer aLinkIndex = anInernalEdgesIt.Key();
653 const BRepMesh_PairOfIndex& aPair = myMeshData->ElementsConnectedTo(aLinkIndex);
655 // Check both sides of link for adjusted triangle.
656 Standard_Boolean isGo[2] = { Standard_True, Standard_True };
657 for (Standard_Integer aTriangleIt = 1; aTriangleIt <= aPair.Extent(); ++aTriangleIt)
659 const BRepMesh_Triangle& aElement = GetTriangle(aPair.Index(aTriangleIt));
660 const Standard_Integer(&e)[3] = aElement.myEdges;
661 const Standard_Boolean(&o)[3] = aElement.myOrientations;
663 for (Standard_Integer i = 0; i < 3; ++i)
665 if (e[i] == aLinkIndex)
667 isGo[o[i] ? 0 : 1] = Standard_False;
675 meshLeftPolygonOf(aLinkIndex, Standard_True);
680 meshLeftPolygonOf(aLinkIndex, Standard_False);
685 //=======================================================================
686 //function : isBoundToFrontier
688 //=======================================================================
689 Standard_Boolean BRepMesh_Delaun::isBoundToFrontier(
690 const Standard_Integer theRefNodeId,
691 const Standard_Integer theRefLinkId)
693 std::stack<Standard_Integer> aLinkStack;
694 TColStd_PackedMapOfInteger aVisitedLinks;
696 aLinkStack.push (theRefLinkId);
697 while (!aLinkStack.empty ())
699 const Standard_Integer aCurrentLinkId = aLinkStack.top ();
702 const BRepMesh_PairOfIndex& aPair = myMeshData->ElementsConnectedTo (aCurrentLinkId);
703 if (aPair.IsEmpty ())
704 return Standard_False;
706 const Standard_Integer aNbElements = aPair.Extent ();
707 for (Standard_Integer anElemIt = 1; anElemIt <= aNbElements; ++anElemIt)
709 const Standard_Integer aTriId = aPair.Index (anElemIt);
713 const BRepMesh_Triangle& aElement = GetTriangle (aTriId);
714 const Standard_Integer (&anEdges)[3] = aElement.myEdges;
716 for (Standard_Integer anEdgeIt = 0; anEdgeIt < 3; ++anEdgeIt)
718 const Standard_Integer anEdgeId = anEdges[anEdgeIt];
719 if (anEdgeId == aCurrentLinkId)
722 const BRepMesh_Edge& anEdge = GetEdge (anEdgeId);
723 if (anEdge.FirstNode () != theRefNodeId &&
724 anEdge.LastNode () != theRefNodeId)
729 if (anEdge.Movability () != BRepMesh_Free)
730 return Standard_True;
732 if (aVisitedLinks.Add (anEdgeId))
734 aLinkStack.push (anEdgeId);
740 return Standard_False;
743 //=======================================================================
744 //function : cleanupMesh
745 //purpose : Cleanup mesh from the free triangles
746 //=======================================================================
747 void BRepMesh_Delaun::cleanupMesh()
749 Handle(NCollection_IncAllocator) aAllocator =
750 new NCollection_IncAllocator(IMeshData::MEMORY_BLOCK_SIZE_HUGE);
754 aAllocator->Reset(Standard_False);
755 IMeshData::MapOfIntegerInteger aLoopEdges(10, aAllocator);
756 IMeshData::MapOfInteger aDelTriangles;
758 Handle(IMeshData::MapOfInteger) aFreeEdges = FreeEdges();
759 IMeshData::IteratorOfMapOfInteger aFreeEdgesIt( *aFreeEdges );
760 for ( ; aFreeEdgesIt.More(); aFreeEdgesIt.Next() )
762 const Standard_Integer& aFreeEdgeId = aFreeEdgesIt.Key();
763 const BRepMesh_Edge& anEdge = GetEdge( aFreeEdgeId );
764 if ( anEdge.Movability() == BRepMesh_Frontier )
767 const BRepMesh_PairOfIndex& aPair =
768 myMeshData->ElementsConnectedTo( aFreeEdgeId );
769 if ( aPair.IsEmpty() )
771 aLoopEdges.Bind( aFreeEdgeId, Standard_True );
775 Standard_Integer aTriId = aPair.FirstIndex();
777 // Check that the connected triangle is not surrounded by another triangles
778 const BRepMesh_Triangle& aElement = GetTriangle(aTriId);
779 const Standard_Integer(&anEdges)[3] = aElement.myEdges;
781 Standard_Boolean isCanNotBeRemoved = Standard_True;
782 for ( Standard_Integer aCurEdgeIdx = 0; aCurEdgeIdx < 3; ++aCurEdgeIdx )
784 if ( anEdges[aCurEdgeIdx] != aFreeEdgeId )
787 for ( Standard_Integer anOtherEdgeIt = 1; anOtherEdgeIt <= 2 && isCanNotBeRemoved; ++anOtherEdgeIt )
789 Standard_Integer anOtherEdgeId = ( aCurEdgeIdx + anOtherEdgeIt ) % 3;
790 const BRepMesh_PairOfIndex& anOtherEdgePair =
791 myMeshData->ElementsConnectedTo( anEdges[anOtherEdgeId] );
793 if ( anOtherEdgePair.Extent() < 2 )
795 isCanNotBeRemoved = Standard_False;
799 for (int aTriIdx = 1; aTriIdx <= anOtherEdgePair.Extent () && isCanNotBeRemoved; ++aTriIdx)
801 if (anOtherEdgePair.Index (aTriIdx) == aTriId)
804 Standard_Integer v[3];
805 const BRepMesh_Triangle& aCurTriangle = GetTriangle (anOtherEdgePair.Index (aTriIdx));
806 myMeshData->ElementNodes (aCurTriangle, v);
807 for (int aNodeIdx = 0; aNodeIdx < 3 && isCanNotBeRemoved; ++aNodeIdx)
809 if (isSupVertex (v[aNodeIdx]))
811 isCanNotBeRemoved = Standard_False;
821 if ( isCanNotBeRemoved )
824 Standard_Boolean isConnected[2] = { Standard_False, Standard_False };
825 for ( Standard_Integer aLinkNodeIt = 0; aLinkNodeIt < 2; ++aLinkNodeIt )
827 isConnected[aLinkNodeIt] = isBoundToFrontier( ( aLinkNodeIt == 0 ) ?
828 anEdge.FirstNode() : anEdge.LastNode(), aFreeEdgeId);
831 if ( !isConnected[0] || !isConnected[1] )
832 aDelTriangles.Add( aTriId );
835 // Destruction of triangles :
836 Standard_Integer aDeletedTrianglesNb = 0;
837 IMeshData::IteratorOfMapOfInteger aDelTrianglesIt( aDelTriangles );
838 for ( ; aDelTrianglesIt.More(); aDelTrianglesIt.Next() )
840 deleteTriangle( aDelTrianglesIt.Key(), aLoopEdges );
841 aDeletedTrianglesNb++;
844 // Destruction of remaining hanging edges
845 IMeshData::MapOfIntegerInteger::Iterator aLoopEdgesIt( aLoopEdges );
846 for ( ; aLoopEdgesIt.More(); aLoopEdgesIt.Next() )
848 if ( myMeshData->ElementsConnectedTo( aLoopEdgesIt.Key() ).IsEmpty() )
849 myMeshData->RemoveLink( aLoopEdgesIt.Key() );
852 if ( aDeletedTrianglesNb == 0 )
857 //=======================================================================
858 //function : frontierAdjust
859 //purpose : Adjust the mesh on the frontier
860 //=======================================================================
861 void BRepMesh_Delaun::frontierAdjust()
863 Handle(IMeshData::MapOfInteger) aFrontier = Frontier();
865 Handle(NCollection_IncAllocator) aAllocator =
866 new NCollection_IncAllocator(IMeshData::MEMORY_BLOCK_SIZE_HUGE);
868 IMeshData::VectorOfInteger aFailedFrontiers(256, aAllocator);
869 IMeshData::MapOfIntegerInteger aLoopEdges(10, aAllocator);
870 Handle(IMeshData::MapOfInteger) aIntFrontierEdges = new IMeshData::MapOfInteger;
872 for ( Standard_Integer aPass = 1; aPass <= 2; ++aPass )
874 // 1 pass): find external triangles on boundary edges;
875 // 2 pass): find external triangles on boundary edges appeared
876 // during triangles replacement.
878 IMeshData::IteratorOfMapOfInteger aFrontierIt( *aFrontier );
879 for ( ; aFrontierIt.More(); aFrontierIt.Next() )
881 Standard_Integer aFrontierId = aFrontierIt.Key();
882 const BRepMesh_PairOfIndex& aPair = myMeshData->ElementsConnectedTo( aFrontierId );
883 Standard_Integer aNbElem = aPair.Extent();
884 for( Standard_Integer aElemIt = 1; aElemIt <= aNbElem; ++aElemIt )
886 const Standard_Integer aPriorElemId = aPair.Index( aElemIt );
887 if( aPriorElemId < 0 )
890 const BRepMesh_Triangle& aElement = GetTriangle(aPriorElemId);
891 const Standard_Integer(&e)[3] = aElement.myEdges;
892 const Standard_Boolean(&o)[3] = aElement.myOrientations;
894 Standard_Boolean isTriangleFound = Standard_False;
895 for ( Standard_Integer n = 0; n < 3; ++n )
897 if ( aFrontierId == e[n] && !o[n] )
899 // Destruction of external triangles on boundary edges
900 isTriangleFound = Standard_True;
901 deleteTriangle( aPriorElemId, aLoopEdges );
906 if ( isTriangleFound )
911 // destrucrion of remaining hanging edges :
912 IMeshData::MapOfIntegerInteger::Iterator aLoopEdgesIt( aLoopEdges );
913 for ( ; aLoopEdgesIt.More(); aLoopEdgesIt.Next() )
915 Standard_Integer aLoopEdgeId = aLoopEdgesIt.Key();
916 if (myMeshData->ElementsConnectedTo( aLoopEdgeId ).IsEmpty() )
917 myMeshData->RemoveLink( aLoopEdgeId );
920 // destruction of triangles crossing the boundary edges and
921 // their replacement by makeshift triangles
922 for ( aFrontierIt.Reset(); aFrontierIt.More(); aFrontierIt.Next() )
924 Standard_Integer aFrontierId = aFrontierIt.Key();
925 if ( !myMeshData->ElementsConnectedTo( aFrontierId ).IsEmpty() )
928 Standard_Boolean isSuccess =
929 meshLeftPolygonOf( aFrontierId, Standard_True, aIntFrontierEdges );
931 if ( aPass == 2 && !isSuccess )
932 aFailedFrontiers.Append( aFrontierId );
938 // When the mesh has been cleaned up, try to process frontier edges
939 // once again to fill the possible gaps that might be occured in case of "saw" -
940 // situation when frontier edge has a triangle at a right side, but its free
941 // links cross another frontieres and meshLeftPolygonOf itself can't collect
943 IMeshData::VectorOfInteger::Iterator aFailedFrontiersIt( aFailedFrontiers );
944 for ( ; aFailedFrontiersIt.More(); aFailedFrontiersIt.Next() )
946 Standard_Integer aFrontierId = aFailedFrontiersIt.Value();
947 if ( !myMeshData->ElementsConnectedTo( aFrontierId ).IsEmpty() )
950 meshLeftPolygonOf( aFrontierId, Standard_True, aIntFrontierEdges );
954 //=======================================================================
955 //function : fillBndBox
956 //purpose : Add boundig box for edge defined by start & end point to
957 // the given vector of bounding boxes for triangulation edges
958 //=======================================================================
959 void BRepMesh_Delaun::fillBndBox(IMeshData::SequenceOfBndB2d& theBoxes,
960 const BRepMesh_Vertex& theV1,
961 const BRepMesh_Vertex& theV2)
964 UpdateBndBox(theV1.Coord(), theV2.Coord(), aBox);
965 theBoxes.Append( aBox );
968 //=======================================================================
969 //function : meshLeftPolygonOf
970 //purpose : Collect the polygon at the left of the given edge (material side)
971 //=======================================================================
972 Standard_Boolean BRepMesh_Delaun::meshLeftPolygonOf(
973 const Standard_Integer theStartEdgeId,
974 const Standard_Boolean isForward,
975 Handle(IMeshData::MapOfInteger) theSkipped)
977 if ( !theSkipped.IsNull() && theSkipped->Contains( theStartEdgeId ) )
978 return Standard_True;
980 const BRepMesh_Edge& aRefEdge = GetEdge( theStartEdgeId );
982 IMeshData::SequenceOfInteger aPolygon;
983 Standard_Integer aStartNode, aPivotNode;
986 aPolygon.Append( theStartEdgeId );
987 aStartNode = aRefEdge.FirstNode();
988 aPivotNode = aRefEdge.LastNode();
992 aPolygon.Append( -theStartEdgeId );
993 aStartNode = aRefEdge.LastNode();
994 aPivotNode = aRefEdge.FirstNode();
998 const BRepMesh_Vertex& aStartEdgeVertexS = GetVertex( aStartNode );
999 BRepMesh_Vertex aPivotVertex = GetVertex( aPivotNode );
1001 gp_Vec2d aRefLinkDir( aPivotVertex.Coord() -
1002 aStartEdgeVertexS.Coord() );
1004 if ( aRefLinkDir.SquareMagnitude() < Precision2 )
1005 return Standard_True;
1007 // Auxilary structures.
1008 // Bounding boxes of polygon links to be used for preliminary
1009 // analysis of intersections
1010 IMeshData::SequenceOfBndB2d aBoxes;
1011 fillBndBox( aBoxes, aStartEdgeVertexS, aPivotVertex );
1014 IMeshData::MapOfInteger aDeadLinks;
1016 // Links are temporarily excluded from consideration
1017 IMeshData::MapOfInteger aLeprousLinks;
1018 aLeprousLinks.Add( theStartEdgeId );
1020 Standard_Boolean isSkipLeprous = Standard_True;
1021 Standard_Integer aFirstNode = aStartNode;
1022 while ( aPivotNode != aFirstNode )
1024 Bnd_B2d aNextLinkBndBox;
1025 gp_Vec2d aNextLinkDir;
1026 Standard_Integer aNextPivotNode = 0;
1028 Standard_Integer aNextLinkId = findNextPolygonLink(
1030 aPivotNode, aPivotVertex, aRefLinkDir,
1031 aBoxes, aPolygon, theSkipped,
1032 isSkipLeprous, aLeprousLinks, aDeadLinks,
1033 aNextPivotNode, aNextLinkDir, aNextLinkBndBox );
1035 if ( aNextLinkId != 0 )
1037 aStartNode = aPivotNode;
1038 aRefLinkDir = aNextLinkDir;
1040 aPivotNode = aNextPivotNode;
1041 aPivotVertex = GetVertex( aNextPivotNode );
1043 aBoxes.Append ( aNextLinkBndBox );
1044 aPolygon.Append( aNextLinkId );
1046 isSkipLeprous = Standard_True;
1051 if ( aPolygon.Length() == 1 )
1052 return Standard_False;
1054 // Return to the previous point
1055 Standard_Integer aDeadLinkId = Abs( aPolygon.Last() );
1056 aDeadLinks.Add ( aDeadLinkId );
1058 aLeprousLinks.Remove( aDeadLinkId );
1059 aPolygon.Remove ( aPolygon.Length() );
1060 aBoxes.Remove ( aBoxes.Length() );
1062 Standard_Integer aPrevLinkInfo = aPolygon.Last();
1063 const BRepMesh_Edge& aPrevLink = GetEdge( Abs( aPrevLinkInfo ) );
1065 if( aPrevLinkInfo > 0 )
1067 aStartNode = aPrevLink.FirstNode();
1068 aPivotNode = aPrevLink.LastNode();
1072 aStartNode = aPrevLink.LastNode();
1073 aPivotNode = aPrevLink.FirstNode();
1076 aPivotVertex = GetVertex( aPivotNode );
1078 aPivotVertex.Coord() - GetVertex( aStartNode ).Coord();
1080 isSkipLeprous = Standard_False;
1084 if ( aPolygon.Length() < 3 )
1085 return Standard_False;
1087 cleanupPolygon( aPolygon, aBoxes );
1088 meshPolygon ( aPolygon, aBoxes, theSkipped );
1090 return Standard_True;
1093 //=======================================================================
1094 //function : findNextPolygonLink
1095 //purpose : Find next link starting from the given node and has maximum
1096 // angle respect the given reference link.
1097 // Each time the next link is found other neighbor links at the
1098 // pivot node are marked as leprous and will be excluded from
1099 // consideration next time until a hanging end is occured.
1100 //=======================================================================
1101 Standard_Integer BRepMesh_Delaun::findNextPolygonLink(
1102 const Standard_Integer& theFirstNode,
1103 const Standard_Integer& thePivotNode,
1104 const BRepMesh_Vertex& thePivotVertex,
1105 const gp_Vec2d& theRefLinkDir,
1106 const IMeshData::SequenceOfBndB2d& theBoxes,
1107 const IMeshData::SequenceOfInteger& thePolygon,
1108 const Handle(IMeshData::MapOfInteger) theSkipped,
1109 const Standard_Boolean& isSkipLeprous,
1110 IMeshData::MapOfInteger& theLeprousLinks,
1111 IMeshData::MapOfInteger& theDeadLinks,
1112 Standard_Integer& theNextPivotNode,
1113 gp_Vec2d& theNextLinkDir,
1114 Bnd_B2d& theNextLinkBndBox )
1116 // Find the next link having the greatest angle
1117 // respect to a direction of a reference one
1118 Standard_Real aMaxAngle = RealFirst();
1120 Standard_Integer aNextLinkId = 0;
1121 IMeshData::ListOfInteger::Iterator aLinkIt( myMeshData->LinksConnectedTo( thePivotNode ) );
1122 for ( ; aLinkIt.More(); aLinkIt.Next() )
1124 const Standard_Integer& aNeighbourLinkInfo = aLinkIt.Value();
1125 Standard_Integer aNeighbourLinkId = Abs( aNeighbourLinkInfo );
1127 if ( theDeadLinks.Contains( aNeighbourLinkId ) ||
1128 ( !theSkipped.IsNull() && theSkipped->Contains( aNeighbourLinkId ) ) )
1133 Standard_Boolean isLeprous = theLeprousLinks.Contains( aNeighbourLinkId );
1134 if ( isSkipLeprous && isLeprous )
1137 const BRepMesh_Edge& aNeighbourLink = GetEdge( aNeighbourLinkId );
1139 // Determine whether the link belongs to the mesh
1140 if ( aNeighbourLink.Movability() == BRepMesh_Free &&
1141 myMeshData->ElementsConnectedTo( aNeighbourLinkInfo ).IsEmpty() )
1143 theDeadLinks.Add( aNeighbourLinkId );
1147 Standard_Integer anOtherNode = aNeighbourLink.FirstNode();
1148 if ( anOtherNode == thePivotNode )
1149 anOtherNode = aNeighbourLink.LastNode();
1151 gp_Vec2d aCurLinkDir( GetVertex( anOtherNode ).Coord() -
1152 thePivotVertex.Coord() );
1154 if ( aCurLinkDir.SquareMagnitude() < Precision2 )
1156 theDeadLinks.Add( aNeighbourLinkId );
1161 theLeprousLinks.Add( aNeighbourLinkId );
1163 Standard_Real anAngle = theRefLinkDir.Angle( aCurLinkDir );
1164 Standard_Boolean isFrontier =
1165 ( aNeighbourLink.Movability() == BRepMesh_Frontier );
1167 Standard_Boolean isCheckPointOnEdge = Standard_True;
1170 if ( Abs( Abs(anAngle) - M_PI ) < Precision::Angular() )
1172 // Glued constrains - don't check intersection
1173 isCheckPointOnEdge = Standard_False;
1174 anAngle = Abs( anAngle );
1178 if (anAngle <= aMaxAngle)
1181 Standard_Boolean isCheckEndPoints = ( anOtherNode != theFirstNode );
1184 Standard_Boolean isNotIntersect =
1185 checkIntersection( aNeighbourLink, thePolygon, theBoxes,
1186 isCheckEndPoints, isCheckPointOnEdge, Standard_True, aBox );
1188 if( isNotIntersect )
1190 aMaxAngle = anAngle;
1192 theNextLinkDir = aCurLinkDir;
1193 theNextPivotNode = anOtherNode;
1194 theNextLinkBndBox = aBox;
1196 aNextLinkId = ( aNeighbourLink.FirstNode() == thePivotNode ) ?
1197 aNeighbourLinkId : -aNeighbourLinkId;
1204 //=======================================================================
1205 //function : checkIntersection
1206 //purpose : Check is the given link intersects the polygon boundaries.
1207 // Returns bounding box for the given link trough the
1208 // <theLinkBndBox> parameter.
1209 //=======================================================================
1210 Standard_Boolean BRepMesh_Delaun::checkIntersection(
1211 const BRepMesh_Edge& theLink,
1212 const IMeshData::SequenceOfInteger& thePolygon,
1213 const IMeshData::SequenceOfBndB2d& thePolyBoxes,
1214 const Standard_Boolean isConsiderEndPointTouch,
1215 const Standard_Boolean isConsiderPointOnEdge,
1216 const Standard_Boolean isSkipLastEdge,
1217 Bnd_B2d& theLinkBndBox ) const
1219 UpdateBndBox(GetVertex(theLink.FirstNode()).Coord(),
1220 GetVertex(theLink.LastNode()).Coord(), theLinkBndBox);
1222 Standard_Integer aPolyLen = thePolygon.Length();
1223 // Don't check intersection with the last link
1224 if ( isSkipLastEdge )
1227 Standard_Boolean isFrontier =
1228 ( theLink.Movability() == BRepMesh_Frontier );
1230 for ( Standard_Integer aPolyIt = 1; aPolyIt <= aPolyLen; ++aPolyIt )
1232 if ( !theLinkBndBox.IsOut( thePolyBoxes.Value( aPolyIt ) ) )
1234 // intersection is possible...
1235 Standard_Integer aPolyLinkId = Abs( thePolygon( aPolyIt ) );
1236 const BRepMesh_Edge& aPolyLink = GetEdge( aPolyLinkId );
1238 // skip intersections between frontier edges
1239 if ( aPolyLink.Movability() == BRepMesh_Frontier && isFrontier )
1243 BRepMesh_GeomTool::IntFlag aIntFlag = intSegSeg( theLink, aPolyLink,
1244 isConsiderEndPointTouch, isConsiderPointOnEdge, anIntPnt );
1246 if ( aIntFlag != BRepMesh_GeomTool::NoIntersection )
1247 return Standard_False;
1251 // Ok, no intersection
1252 return Standard_True;
1255 //=======================================================================
1256 //function : addTriangle
1257 //purpose : Add a triangle based on the given oriented edges into mesh
1258 //=======================================================================
1259 void BRepMesh_Delaun::addTriangle( const Standard_Integer (&theEdgesId)[3],
1260 const Standard_Boolean (&theEdgesOri)[3],
1261 const Standard_Integer (&theNodesId)[3] )
1263 Standard_Integer aNewTriangleId =
1264 myMeshData->AddElement(BRepMesh_Triangle(theEdgesId,
1265 theEdgesOri, BRepMesh_Free));
1267 Standard_Boolean isAdded = Standard_True;
1270 isAdded = myCircles.Bind(
1272 GetVertex( theNodesId[0] ).Coord(),
1273 GetVertex( theNodesId[1] ).Coord(),
1274 GetVertex( theNodesId[2] ).Coord() );
1278 myMeshData->RemoveElement( aNewTriangleId );
1281 //=======================================================================
1282 //function : cleanupPolygon
1283 //purpose : Remove internal triangles from the given polygon
1284 //=======================================================================
1285 void BRepMesh_Delaun::cleanupPolygon(const IMeshData::SequenceOfInteger& thePolygon,
1286 const IMeshData::SequenceOfBndB2d& thePolyBoxes )
1288 Standard_Integer aPolyLen = thePolygon.Length();
1292 Handle(NCollection_IncAllocator) aAllocator =
1293 new NCollection_IncAllocator(IMeshData::MEMORY_BLOCK_SIZE_HUGE);
1295 IMeshData::MapOfIntegerInteger aLoopEdges(10, aAllocator);
1296 IMeshData::MapOfInteger anIgnoredEdges;
1297 IMeshData::MapOfInteger aPolyVerticesFindMap;
1298 IMeshData::VectorOfInteger aPolyVertices(256, aAllocator);
1299 // Collect boundary vertices of the polygon
1300 for ( Standard_Integer aPolyIt = 1; aPolyIt <= aPolyLen; ++aPolyIt )
1302 Standard_Integer aPolyEdgeInfo = thePolygon( aPolyIt );
1303 Standard_Integer aPolyEdgeId = Abs( aPolyEdgeInfo );
1304 anIgnoredEdges.Add( aPolyEdgeId );
1306 Standard_Boolean isForward = ( aPolyEdgeInfo > 0 );
1307 const BRepMesh_PairOfIndex& aPair =
1308 myMeshData->ElementsConnectedTo( aPolyEdgeId );
1310 Standard_Integer anElemIt = 1;
1311 for ( ; anElemIt <= aPair.Extent(); ++anElemIt )
1313 Standard_Integer anElemId = aPair.Index( anElemIt );
1317 const BRepMesh_Triangle& aElement = GetTriangle(anElemId);
1318 const Standard_Integer(&anEdges)[3] = aElement.myEdges;
1319 const Standard_Boolean(&anEdgesOri)[3] = aElement.myOrientations;
1321 Standard_Integer isTriangleFound = Standard_False;
1322 for ( Standard_Integer anEdgeIt = 0; anEdgeIt < 3; ++anEdgeIt )
1324 if ( anEdges[anEdgeIt] == aPolyEdgeId &&
1325 anEdgesOri[anEdgeIt] == isForward )
1327 isTriangleFound = Standard_True;
1328 deleteTriangle( anElemId, aLoopEdges );
1333 if ( isTriangleFound )
1337 // Skip a neighbor link to extract unique vertices each time
1340 const BRepMesh_Edge& aPolyEdge = GetEdge( aPolyEdgeId );
1341 Standard_Integer aFirstVertex = aPolyEdge.FirstNode();
1342 Standard_Integer aLastVertex = aPolyEdge.LastNode();
1344 aPolyVerticesFindMap.Add( aFirstVertex );
1345 aPolyVerticesFindMap.Add( aLastVertex );
1347 if ( aPolyEdgeInfo > 0 )
1349 aPolyVertices.Append( aFirstVertex );
1350 aPolyVertices.Append( aLastVertex );
1354 aPolyVertices.Append( aLastVertex );
1355 aPolyVertices.Append( aFirstVertex );
1360 // Make closed sequence
1361 if ( aPolyVertices.First() != aPolyVertices.Last() )
1362 aPolyVertices.Append( aPolyVertices.First() );
1364 IMeshData::MapOfInteger aSurvivedLinks( anIgnoredEdges );
1366 Standard_Integer aPolyVertIt = 0;
1367 Standard_Integer anUniqueVerticesNum = aPolyVertices.Length() - 1;
1368 for ( ; aPolyVertIt < anUniqueVerticesNum; ++aPolyVertIt )
1370 killTrianglesAroundVertex( aPolyVertices( aPolyVertIt ),
1371 aPolyVertices, aPolyVerticesFindMap, thePolygon,
1372 thePolyBoxes, aSurvivedLinks, aLoopEdges );
1375 IMeshData::MapOfIntegerInteger::Iterator aLoopEdgesIt( aLoopEdges );
1376 for ( ; aLoopEdgesIt.More(); aLoopEdgesIt.Next() )
1378 const Standard_Integer& aLoopEdgeId = aLoopEdgesIt.Key();
1379 if ( anIgnoredEdges.Contains( aLoopEdgeId ) )
1382 if ( myMeshData->ElementsConnectedTo( aLoopEdgeId ).IsEmpty() )
1383 myMeshData->RemoveLink( aLoopEdgesIt.Key() );
1387 //=======================================================================
1388 //function : killTrianglesAroundVertex
1389 //purpose : Remove all triangles and edges that are placed
1390 // inside the polygon or crossed it.
1391 //=======================================================================
1392 void BRepMesh_Delaun::killTrianglesAroundVertex(
1393 const Standard_Integer theZombieNodeId,
1394 const IMeshData::VectorOfInteger& thePolyVertices,
1395 const IMeshData::MapOfInteger& thePolyVerticesFindMap,
1396 const IMeshData::SequenceOfInteger& thePolygon,
1397 const IMeshData::SequenceOfBndB2d& thePolyBoxes,
1398 IMeshData::MapOfInteger& theSurvivedLinks,
1399 IMeshData::MapOfIntegerInteger& theLoopEdges )
1401 IMeshData::ListOfInteger::Iterator aNeighborsIt =
1402 myMeshData->LinksConnectedTo( theZombieNodeId );
1404 // Try to infect neighbor nodes
1405 IMeshData::VectorOfInteger aVictimNodes;
1406 for ( ; aNeighborsIt.More(); aNeighborsIt.Next() )
1408 const Standard_Integer& aNeighborLinkId = aNeighborsIt.Value();
1409 if ( theSurvivedLinks.Contains( aNeighborLinkId ) )
1412 const BRepMesh_Edge& aNeighborLink = GetEdge( aNeighborLinkId );
1413 if ( aNeighborLink.Movability() == BRepMesh_Frontier )
1415 // Though, if it lies onto the polygon boundary -
1416 // take its triangles
1418 Standard_Boolean isNotIntersect =
1419 checkIntersection( aNeighborLink, thePolygon,
1420 thePolyBoxes, Standard_False, Standard_True,
1421 Standard_False, aBox );
1423 if ( isNotIntersect )
1426 theSurvivedLinks.Add( aNeighborLinkId );
1432 Standard_Integer anOtherNode = aNeighborLink.FirstNode();
1433 if ( anOtherNode == theZombieNodeId )
1434 anOtherNode = aNeighborLink.LastNode();
1436 // Possible sacrifice
1437 if ( !thePolyVerticesFindMap.Contains( anOtherNode ) )
1439 if ( isVertexInsidePolygon( anOtherNode, thePolyVertices ) )
1442 aVictimNodes.Append( anOtherNode );
1446 // Lucky. But it may intersect the polygon boundary.
1448 killTrianglesOnIntersectingLinks( aNeighborLinkId,
1449 aNeighborLink, anOtherNode, thePolygon,
1450 thePolyBoxes, theSurvivedLinks, theLoopEdges );
1457 // Add link to the survivers to avoid cycling
1458 theSurvivedLinks.Add( aNeighborLinkId );
1459 killLinkTriangles( aNeighborLinkId, theLoopEdges );
1462 // Go and do your job!
1463 IMeshData::VectorOfInteger::Iterator aVictimIt( aVictimNodes );
1464 for ( ; aVictimIt.More(); aVictimIt.Next() )
1466 killTrianglesAroundVertex( aVictimIt.Value(), thePolyVertices,
1467 thePolyVerticesFindMap, thePolygon, thePolyBoxes,
1468 theSurvivedLinks, theLoopEdges );
1472 //=======================================================================
1473 //function : isVertexInsidePolygon
1474 //purpose : Checks is the given vertex lies inside the polygon
1475 //=======================================================================
1476 Standard_Boolean BRepMesh_Delaun::isVertexInsidePolygon(
1477 const Standard_Integer& theVertexId,
1478 const IMeshData::VectorOfInteger& thePolygonVertices ) const
1480 Standard_Integer aPolyLen = thePolygonVertices.Length();
1482 return Standard_False;
1485 const gp_XY aCenterPointXY = GetVertex( theVertexId ).Coord();
1487 const BRepMesh_Vertex& aFirstVertex = GetVertex( thePolygonVertices( 0 ) );
1488 gp_Vec2d aPrevVertexDir( aFirstVertex.Coord() - aCenterPointXY );
1489 if ( aPrevVertexDir.SquareMagnitude() < Precision2 )
1490 return Standard_True;
1492 Standard_Real aTotalAng = 0.0;
1493 for ( Standard_Integer aPolyIt = 1; aPolyIt < aPolyLen; ++aPolyIt )
1495 const BRepMesh_Vertex& aPolyVertex = GetVertex( thePolygonVertices( aPolyIt ) );
1497 gp_Vec2d aCurVertexDir( aPolyVertex.Coord() - aCenterPointXY );
1498 if ( aCurVertexDir.SquareMagnitude() < Precision2 )
1499 return Standard_True;
1501 aTotalAng += aCurVertexDir.Angle( aPrevVertexDir );
1502 aPrevVertexDir = aCurVertexDir;
1505 if ( Abs( Angle2PI - aTotalAng ) > Precision::Angular() )
1506 return Standard_False;
1508 return Standard_True;
1511 //=======================================================================
1512 //function : killTrianglesOnIntersectingLinks
1513 //purpose : Checks is the given link crosses the polygon boundary.
1514 // If yes, kills its triangles and checks neighbor links on
1515 // boundary intersection. Does nothing elsewhere.
1516 //=======================================================================
1517 void BRepMesh_Delaun::killTrianglesOnIntersectingLinks(
1518 const Standard_Integer& theLinkToCheckId,
1519 const BRepMesh_Edge& theLinkToCheck,
1520 const Standard_Integer& theEndPoint,
1521 const IMeshData::SequenceOfInteger& thePolygon,
1522 const IMeshData::SequenceOfBndB2d& thePolyBoxes,
1523 IMeshData::MapOfInteger& theSurvivedLinks,
1524 IMeshData::MapOfIntegerInteger& theLoopEdges )
1526 if ( theSurvivedLinks.Contains( theLinkToCheckId ) )
1530 Standard_Boolean isNotIntersect =
1531 checkIntersection( theLinkToCheck, thePolygon,
1532 thePolyBoxes, Standard_False, Standard_False,
1533 Standard_False, aBox );
1535 theSurvivedLinks.Add( theLinkToCheckId );
1537 if ( isNotIntersect )
1540 killLinkTriangles( theLinkToCheckId, theLoopEdges );
1542 IMeshData::ListOfInteger::Iterator aNeighborsIt(
1543 myMeshData->LinksConnectedTo(theEndPoint));
1545 for ( ; aNeighborsIt.More(); aNeighborsIt.Next() )
1547 const Standard_Integer& aNeighborLinkId = aNeighborsIt.Value();
1548 const BRepMesh_Edge& aNeighborLink = GetEdge( aNeighborLinkId );
1549 Standard_Integer anOtherNode = aNeighborLink.FirstNode();
1550 if ( anOtherNode == theEndPoint )
1551 anOtherNode = aNeighborLink.LastNode();
1553 killTrianglesOnIntersectingLinks( aNeighborLinkId,
1554 aNeighborLink, anOtherNode, thePolygon,
1555 thePolyBoxes, theSurvivedLinks, theLoopEdges );
1559 //=======================================================================
1560 //function : killLinkTriangles
1561 //purpose : Kill triangles bound to the given link.
1562 //=======================================================================
1563 void BRepMesh_Delaun::killLinkTriangles(
1564 const Standard_Integer& theLinkId,
1565 IMeshData::MapOfIntegerInteger& theLoopEdges )
1567 const BRepMesh_PairOfIndex& aPair =
1568 myMeshData->ElementsConnectedTo( theLinkId );
1570 Standard_Integer anElemNb = aPair.Extent();
1571 for ( Standard_Integer aPairIt = 1; aPairIt <= anElemNb; ++aPairIt )
1573 Standard_Integer anElemId = aPair.FirstIndex();
1577 deleteTriangle( anElemId, theLoopEdges );
1581 //=======================================================================
1582 //function : getOrientedNodes
1583 //purpose : Returns start and end nodes of the given edge in respect to
1585 //=======================================================================
1586 void BRepMesh_Delaun::getOrientedNodes(const BRepMesh_Edge& theEdge,
1587 const Standard_Boolean isForward,
1588 Standard_Integer *theNodes) const
1592 theNodes[0] = theEdge.FirstNode();
1593 theNodes[1] = theEdge.LastNode();
1597 theNodes[0] = theEdge.LastNode();
1598 theNodes[1] = theEdge.FirstNode();
1602 //=======================================================================
1603 //function : processLoop
1604 //purpose : Processes loop within the given polygon formed by range of
1605 // its links specified by start and end link indices.
1606 //=======================================================================
1607 void BRepMesh_Delaun::processLoop(const Standard_Integer theLinkFrom,
1608 const Standard_Integer theLinkTo,
1609 const IMeshData::SequenceOfInteger& thePolygon,
1610 const IMeshData::SequenceOfBndB2d& thePolyBoxes)
1612 Standard_Integer aNbOfLinksInLoop = theLinkTo - theLinkFrom - 1;
1613 if ( aNbOfLinksInLoop < 3 )
1616 IMeshData::SequenceOfInteger aPolygon;
1617 IMeshData::SequenceOfBndB2d aPolyBoxes;
1618 for ( ; aNbOfLinksInLoop > 0; --aNbOfLinksInLoop )
1620 Standard_Integer aLoopLinkIndex = theLinkFrom + aNbOfLinksInLoop;
1621 aPolygon .Prepend( thePolygon ( aLoopLinkIndex ) );
1622 aPolyBoxes.Prepend( thePolyBoxes( aLoopLinkIndex ) );
1624 meshPolygon( aPolygon, aPolyBoxes );
1627 //=======================================================================
1628 //function : createAndReplacePolygonLink
1629 //purpose : Creates new link based on the given nodes and updates the
1631 //=======================================================================
1632 Standard_Integer BRepMesh_Delaun::createAndReplacePolygonLink(
1633 const Standard_Integer *theNodes,
1634 const gp_Pnt2d *thePnts,
1635 const Standard_Integer theRootIndex,
1636 const ReplaceFlag theReplaceFlag,
1637 IMeshData::SequenceOfInteger& thePolygon,
1638 IMeshData::SequenceOfBndB2d& thePolyBoxes )
1640 Standard_Integer aNewEdgeId =
1641 myMeshData->AddLink( BRepMesh_Edge(
1642 theNodes[0], theNodes[1], BRepMesh_Free ) );
1645 UpdateBndBox(thePnts[0].Coord(), thePnts[1].Coord(), aNewBox);
1647 switch ( theReplaceFlag )
1649 case BRepMesh_Delaun::Replace:
1650 thePolygon .SetValue( theRootIndex, aNewEdgeId );
1651 thePolyBoxes.SetValue( theRootIndex, aNewBox );
1654 case BRepMesh_Delaun::InsertAfter:
1655 thePolygon .InsertAfter( theRootIndex, aNewEdgeId );
1656 thePolyBoxes.InsertAfter( theRootIndex, aNewBox );
1659 case BRepMesh_Delaun::InsertBefore:
1660 thePolygon .InsertBefore( theRootIndex, aNewEdgeId );
1661 thePolyBoxes.InsertBefore( theRootIndex, aNewBox );
1668 //=======================================================================
1669 //function : meshPolygon
1671 //=======================================================================
1672 void BRepMesh_Delaun::meshPolygon(IMeshData::SequenceOfInteger& thePolygon,
1673 IMeshData::SequenceOfBndB2d& thePolyBoxes,
1674 Handle(IMeshData::MapOfInteger) theSkipped)
1676 // Check is the source polygon elementary
1677 if ( meshElementaryPolygon( thePolygon ) )
1680 // Check and correct boundary edges
1681 Standard_Integer aPolyLen = thePolygon.Length();
1682 const Standard_Real aPolyArea = Abs( polyArea( thePolygon, 1, aPolyLen ) );
1683 const Standard_Real aSmallLoopArea = 0.001 * aPolyArea;
1684 for ( Standard_Integer aPolyIt = 1; aPolyIt < aPolyLen; ++aPolyIt )
1686 Standard_Integer aCurEdgeInfo = thePolygon( aPolyIt );
1687 Standard_Integer aCurEdgeId = Abs( aCurEdgeInfo );
1688 const BRepMesh_Edge* aCurEdge = &GetEdge( aCurEdgeId );
1689 if ( aCurEdge->Movability() != BRepMesh_Frontier )
1692 Standard_Integer aCurNodes[2];
1693 getOrientedNodes( *aCurEdge, aCurEdgeInfo > 0, aCurNodes );
1695 gp_Pnt2d aCurPnts[2] = {
1696 GetVertex(aCurNodes[0]).Coord(),
1697 GetVertex(aCurNodes[1]).Coord()
1700 gp_Vec2d aCurVec( aCurPnts[0], aCurPnts[1] );
1702 // check further links
1703 Standard_Integer aNextPolyIt = aPolyIt + 1;
1704 for ( ; aNextPolyIt <= aPolyLen; ++aNextPolyIt )
1706 Standard_Integer aNextEdgeInfo = thePolygon( aNextPolyIt );
1707 Standard_Integer aNextEdgeId = Abs( aNextEdgeInfo );
1708 const BRepMesh_Edge* aNextEdge = &GetEdge( aNextEdgeId );
1709 if ( aNextEdge->Movability() != BRepMesh_Frontier )
1712 Standard_Integer aNextNodes[2];
1713 getOrientedNodes( *aNextEdge, aNextEdgeInfo > 0, aNextNodes );
1715 gp_Pnt2d aNextPnts[2] = {
1716 GetVertex(aNextNodes[0]).Coord(),
1717 GetVertex(aNextNodes[1]).Coord()
1721 BRepMesh_GeomTool::IntFlag aIntFlag = intSegSeg( *aCurEdge, *aNextEdge,
1722 Standard_False, Standard_True, anIntPnt );
1724 if ( aIntFlag == BRepMesh_GeomTool::NoIntersection )
1727 Standard_Boolean isRemoveFromFirst = Standard_False;
1728 Standard_Boolean isAddReplacingEdge = Standard_True;
1729 Standard_Integer aIndexToRemoveTo = aNextPolyIt;
1730 if ( aIntFlag == BRepMesh_GeomTool::Cross )
1732 Standard_Real aLoopArea = polyArea( thePolygon, aPolyIt + 1, aNextPolyIt );
1733 gp_Vec2d aVec1( anIntPnt, aCurPnts [1] );
1734 gp_Vec2d aVec2( anIntPnt, aNextPnts[0] );
1736 aLoopArea += ( aVec1 ^ aVec2 ) / 2.;
1737 if ( Abs( aLoopArea ) > aSmallLoopArea )
1739 aNextNodes[1] = aCurNodes[0];
1740 aNextPnts [1] = aCurPnts [0];
1742 aNextEdgeId = Abs( createAndReplacePolygonLink( aNextNodes, aNextPnts,
1743 aNextPolyIt, BRepMesh_Delaun::Replace, thePolygon, thePolyBoxes ) );
1745 processLoop( aPolyIt, aNextPolyIt, thePolygon, thePolyBoxes );
1749 Standard_Real aDist1 = anIntPnt.SquareDistance(aNextPnts[0]);
1750 Standard_Real aDist2 = anIntPnt.SquareDistance(aNextPnts[1]);
1752 // Choose node with lower distance
1753 const Standard_Boolean isCloseToStart = ( aDist1 < aDist2 );
1754 const Standard_Integer aEndPointIndex = isCloseToStart ? 0 : 1;
1755 aCurNodes[1] = aNextNodes[aEndPointIndex];
1756 aCurPnts [1] = aNextPnts [aEndPointIndex];
1758 if ( isCloseToStart )
1761 // In this context only intersections between frontier edges
1762 // are possible. If intersection between edges of different
1763 // types occured - treat this case as invalid (i.e. result
1764 // might not reflect the expectations).
1765 if ( !theSkipped.IsNull() )
1767 Standard_Integer aSkippedLinkIt = aPolyIt;
1768 for ( ; aSkippedLinkIt <= aIndexToRemoveTo; ++aSkippedLinkIt )
1769 theSkipped->Add( Abs( thePolygon( aSkippedLinkIt ) ) );
1772 else if ( aIntFlag == BRepMesh_GeomTool::PointOnSegment )
1774 // Indentify chopping link
1775 Standard_Boolean isFirstChopping = Standard_False;
1776 Standard_Integer aCheckPointIt = 0;
1777 for ( ; aCheckPointIt < 2; ++aCheckPointIt )
1779 gp_Pnt2d& aRefPoint = aCurPnts[aCheckPointIt];
1780 // Check is second link touches the first one
1781 gp_Vec2d aVec1( aRefPoint, aNextPnts[0] );
1782 gp_Vec2d aVec2( aRefPoint, aNextPnts[1] );
1783 if ( Abs( aVec1 ^ aVec2 ) < Precision )
1785 isFirstChopping = Standard_True;
1790 if ( isFirstChopping )
1792 // Split second link
1793 isAddReplacingEdge = Standard_False;
1794 isRemoveFromFirst = ( aCheckPointIt == 0 );
1796 Standard_Integer aSplitLink[3] = {
1798 aCurNodes [aCheckPointIt],
1802 gp_Pnt2d aSplitPnts[3] = {
1804 aCurPnts [aCheckPointIt],
1808 Standard_Integer aSplitLinkIt = 0;
1809 for ( ; aSplitLinkIt < 2; ++aSplitLinkIt )
1811 createAndReplacePolygonLink( &aSplitLink[aSplitLinkIt],
1812 &aSplitPnts[aSplitLinkIt], aNextPolyIt, ( aSplitLinkIt == 0 ) ?
1813 BRepMesh_Delaun::Replace : BRepMesh_Delaun::InsertAfter,
1814 thePolygon, thePolyBoxes );
1817 processLoop( aPolyIt + aCheckPointIt, aIndexToRemoveTo,
1818 thePolygon, thePolyBoxes );
1823 Standard_Integer aSplitLinkNodes[2] = {
1828 gp_Pnt2d aSplitLinkPnts[2] = {
1832 createAndReplacePolygonLink( aSplitLinkNodes, aSplitLinkPnts,
1833 aPolyIt, BRepMesh_Delaun::InsertAfter, thePolygon, thePolyBoxes );
1835 aCurNodes[1] = aNextNodes[1];
1836 aCurPnts [1] = aNextPnts [1];
1839 processLoop( aPolyIt + 1, aIndexToRemoveTo,
1840 thePolygon, thePolyBoxes );
1843 else if ( aIntFlag == BRepMesh_GeomTool::Glued )
1845 if ( aCurNodes[1] == aNextNodes[0] )
1847 aCurNodes[1] = aNextNodes[1];
1848 aCurPnts [1] = aNextPnts [1];
1850 // TODO: Non-adjacent glued links within the polygon
1852 else if ( aIntFlag == BRepMesh_GeomTool::Same )
1854 processLoop( aPolyIt, aNextPolyIt, thePolygon, thePolyBoxes );
1856 isRemoveFromFirst = Standard_True;
1857 isAddReplacingEdge = Standard_False;
1860 continue; // Not supported type
1862 if ( isAddReplacingEdge )
1864 aCurEdgeId = Abs( createAndReplacePolygonLink( aCurNodes, aCurPnts,
1865 aPolyIt, BRepMesh_Delaun::Replace, thePolygon, thePolyBoxes ) );
1867 aCurEdge = &GetEdge( aCurEdgeId );
1868 aCurVec = gp_Vec2d( aCurPnts[0], aCurPnts[1] );
1871 Standard_Integer aIndexToRemoveFrom =
1872 isRemoveFromFirst ? aPolyIt : aPolyIt + 1;
1874 thePolygon .Remove( aIndexToRemoveFrom, aIndexToRemoveTo );
1875 thePolyBoxes.Remove( aIndexToRemoveFrom, aIndexToRemoveTo );
1877 aPolyLen = thePolygon.Length();
1878 if ( isRemoveFromFirst )
1884 aNextPolyIt = aPolyIt;
1888 IMeshData::SequenceOfInteger* aPolygon1 = &thePolygon;
1889 IMeshData::SequenceOfBndB2d* aPolyBoxes1 = &thePolyBoxes;
1891 Handle(IMeshData::SequenceOfInteger) aPolygon2 = new IMeshData::SequenceOfInteger;
1892 Handle(IMeshData::SequenceOfBndB2d) aPolyBoxes2 = new IMeshData::SequenceOfBndB2d;
1894 NCollection_Sequence<Handle(IMeshData::SequenceOfInteger)> aPolyStack;
1895 NCollection_Sequence<Handle(IMeshData::SequenceOfBndB2d)> aPolyBoxStack;
1898 decomposeSimplePolygon(*aPolygon1, *aPolyBoxes1, *aPolygon2, *aPolyBoxes2);
1899 if (!aPolygon2->IsEmpty())
1901 aPolyStack.Append(aPolygon2);
1902 aPolyBoxStack.Append(aPolyBoxes2);
1904 aPolygon2 = new IMeshData::SequenceOfInteger;
1905 aPolyBoxes2 = new IMeshData::SequenceOfBndB2d;
1908 if (aPolygon1->IsEmpty())
1910 if (!aPolyStack.IsEmpty() && aPolygon1 == &(*aPolyStack.First()))
1912 aPolyStack.Remove(1);
1913 aPolyBoxStack.Remove(1);
1916 if (aPolyStack.IsEmpty())
1919 aPolygon1 = &(*aPolyStack.ChangeFirst());
1920 aPolyBoxes1 = &(*aPolyBoxStack.ChangeFirst());
1925 //=======================================================================
1926 //function : meshElementaryPolygon
1927 //purpose : Triangulation of closed polygon containing only three edges.
1928 //=======================================================================
1929 Standard_Boolean BRepMesh_Delaun::meshElementaryPolygon(
1930 const IMeshData::SequenceOfInteger& thePolygon)
1932 Standard_Integer aPolyLen = thePolygon.Length();
1934 return Standard_True;
1935 else if ( aPolyLen > 3 )
1936 return Standard_False;
1938 // Just create a triangle
1939 Standard_Integer anEdges[3];
1940 Standard_Boolean anEdgesOri[3];
1942 for ( Standard_Integer anEdgeIt = 0; anEdgeIt < 3; ++anEdgeIt )
1944 Standard_Integer anEdgeInfo = thePolygon( anEdgeIt + 1 );
1945 anEdges[anEdgeIt] = Abs( anEdgeInfo );
1946 anEdgesOri[anEdgeIt] = ( anEdgeInfo > 0 );
1949 const BRepMesh_Edge& anEdge1 = GetEdge( anEdges[0] );
1950 const BRepMesh_Edge& anEdge2 = GetEdge( anEdges[1] );
1952 Standard_Integer aNodes[3] = { anEdge1.FirstNode(),
1954 anEdge2.FirstNode() };
1955 if ( aNodes[2] == aNodes[0] ||
1956 aNodes[2] == aNodes[1] )
1958 aNodes[2] = anEdge2.LastNode();
1961 addTriangle( anEdges, anEdgesOri, aNodes );
1962 return Standard_True;
1965 //=======================================================================
1966 //function : meshSimplePolygon
1968 //=======================================================================
1969 void BRepMesh_Delaun::decomposeSimplePolygon(
1970 IMeshData::SequenceOfInteger& thePolygon,
1971 IMeshData::SequenceOfBndB2d& thePolyBoxes,
1972 IMeshData::SequenceOfInteger& thePolygonCut,
1973 IMeshData::SequenceOfBndB2d& thePolyBoxesCut)
1975 // Check is the given polygon elementary
1976 if ( meshElementaryPolygon( thePolygon ) )
1979 thePolyBoxes.Clear();
1983 // Polygon contains more than 3 links
1984 Standard_Integer aFirstEdgeInfo = thePolygon(1);
1985 const BRepMesh_Edge& aFirstEdge = GetEdge( Abs( aFirstEdgeInfo ) );
1987 Standard_Integer aNodes[3];
1988 getOrientedNodes( aFirstEdge, aFirstEdgeInfo > 0, aNodes );
1990 gp_Pnt2d aRefVertices[3];
1991 aRefVertices[0] = GetVertex( aNodes[0] ).Coord();
1992 aRefVertices[1] = GetVertex( aNodes[1] ).Coord();
1994 gp_Vec2d aRefEdgeDir( aRefVertices[0], aRefVertices[1] );
1996 Standard_Real aRefEdgeLen = aRefEdgeDir.Magnitude();
1997 if ( aRefEdgeLen < Precision )
2000 thePolyBoxes.Clear();
2004 aRefEdgeDir /= aRefEdgeLen;
2006 // Find a point with minimum distance respect
2007 // the end of reference link
2008 Standard_Integer aUsedLinkId = 0;
2009 Standard_Real aOptAngle = 0.0;
2010 Standard_Real aMinDist = RealLast();
2011 Standard_Integer aPivotNode = aNodes[1];
2012 Standard_Integer aPolyLen = thePolygon.Length();
2013 for ( Standard_Integer aLinkIt = 3; aLinkIt <= aPolyLen; ++aLinkIt )
2015 Standard_Integer aLinkInfo = thePolygon( aLinkIt );
2016 const BRepMesh_Edge& aNextEdge = GetEdge( Abs( aLinkInfo ) );
2018 aPivotNode = aLinkInfo > 0 ?
2019 aNextEdge.FirstNode() :
2020 aNextEdge.LastNode();
2022 gp_Pnt2d aPivotVertex = GetVertex( aPivotNode ).Coord();
2023 gp_Vec2d aDistanceDir( aRefVertices[1], aPivotVertex );
2025 Standard_Real aDist = aRefEdgeDir ^ aDistanceDir;
2026 Standard_Real aAngle = Abs( aRefEdgeDir.Angle(aDistanceDir) );
2027 Standard_Real anAbsDist = Abs( aDist );
2028 if (anAbsDist < Precision || aDist < 0.)
2031 if ( ( anAbsDist >= aMinDist ) &&
2032 ( aAngle <= aOptAngle || aAngle > AngDeviation90Deg ) )
2037 // Check is the test link crosses the polygon boudaries
2038 Standard_Boolean isIntersect = Standard_False;
2039 for ( Standard_Integer aRefLinkNodeIt = 0; aRefLinkNodeIt < 2; ++aRefLinkNodeIt )
2041 const Standard_Integer& aLinkFirstNode = aNodes[aRefLinkNodeIt];
2042 const gp_Pnt2d& aLinkFirstVertex = aRefVertices[aRefLinkNodeIt];
2045 UpdateBndBox(aLinkFirstVertex.Coord(), aPivotVertex.Coord(), aBox);
2047 BRepMesh_Edge aCheckLink( aLinkFirstNode, aPivotNode, BRepMesh_Free );
2049 Standard_Integer aCheckLinkIt = 2;
2050 for ( ; aCheckLinkIt <= aPolyLen; ++aCheckLinkIt )
2052 if( aCheckLinkIt == aLinkIt )
2055 if ( !aBox.IsOut( thePolyBoxes.Value( aCheckLinkIt ) ) )
2057 const BRepMesh_Edge& aPolyLink =
2058 GetEdge( Abs( thePolygon( aCheckLinkIt ) ) );
2060 if ( aCheckLink.IsEqual( aPolyLink ) )
2063 // intersection is possible...
2065 BRepMesh_GeomTool::IntFlag aIntFlag = intSegSeg( aCheckLink, aPolyLink,
2066 Standard_False, Standard_False, anIntPnt );
2068 if( aIntFlag != BRepMesh_GeomTool::NoIntersection )
2070 isIntersect = Standard_True;
2085 aMinDist = anAbsDist;
2086 aNodes[2] = aPivotNode;
2087 aRefVertices[2] = aPivotVertex;
2088 aUsedLinkId = aLinkIt;
2091 if ( aUsedLinkId == 0 )
2094 thePolyBoxes.Clear();
2099 BRepMesh_Edge aNewEdges[2] = {
2100 BRepMesh_Edge( aNodes[1], aNodes[2], BRepMesh_Free ),
2101 BRepMesh_Edge( aNodes[2], aNodes[0], BRepMesh_Free ) };
2103 Standard_Integer aNewEdgesInfo[3] = {
2105 myMeshData->AddLink( aNewEdges[0] ),
2106 myMeshData->AddLink( aNewEdges[1] ) };
2109 Standard_Integer anEdges[3];
2110 Standard_Boolean anEdgesOri[3];
2111 for ( Standard_Integer aTriEdgeIt = 0; aTriEdgeIt < 3; ++aTriEdgeIt )
2113 const Standard_Integer& anEdgeInfo = aNewEdgesInfo[aTriEdgeIt];
2114 anEdges[aTriEdgeIt] = Abs( anEdgeInfo );
2115 anEdgesOri[aTriEdgeIt] = anEdgeInfo > 0;
2117 addTriangle( anEdges, anEdgesOri, aNodes );
2119 // Create triangle and split the source polygon on two
2120 // parts (if possible) and mesh each part as independent
2122 if ( aUsedLinkId < aPolyLen )
2124 thePolygon.Split(aUsedLinkId, thePolygonCut);
2125 thePolygonCut.Prepend( -aNewEdgesInfo[2] );
2126 thePolyBoxes.Split(aUsedLinkId, thePolyBoxesCut);
2129 UpdateBndBox(aRefVertices[0].Coord(), aRefVertices[2].Coord(), aBox);
2130 thePolyBoxesCut.Prepend( aBox );
2134 thePolygon.Remove ( aPolyLen );
2135 thePolyBoxes.Remove( aPolyLen );
2138 if ( aUsedLinkId > 3 )
2140 thePolygon.SetValue( 1, -aNewEdgesInfo[1] );
2143 UpdateBndBox(aRefVertices[1].Coord(), aRefVertices[2].Coord(), aBox);
2144 thePolyBoxes.SetValue( 1, aBox );
2148 //=======================================================================
2149 //function : RemoveVertex
2150 //purpose : Removes a vertex from the triangulation
2151 //=======================================================================
2152 void BRepMesh_Delaun::RemoveVertex( const BRepMesh_Vertex& theVertex )
2154 BRepMesh_SelectorOfDataStructureOfDelaun aSelector( myMeshData );
2155 aSelector.NeighboursOf( theVertex );
2157 IMeshData::MapOfIntegerInteger aLoopEdges;//( 10, myMeshData->Allocator() );
2159 // Loop on triangles to be destroyed :
2160 IMeshData::IteratorOfMapOfInteger aTriangleIt( aSelector.Elements() );
2161 for ( ; aTriangleIt.More(); aTriangleIt.Next() )
2162 deleteTriangle( aTriangleIt.Key(), aLoopEdges );
2164 IMeshData::SequenceOfBndB2d aBoxes;
2165 IMeshData::SequenceOfInteger aPolygon;
2166 Standard_Integer aLoopEdgesCount = aLoopEdges.Extent();
2167 IMeshData::MapOfIntegerInteger::Iterator aLoopEdgesIt( aLoopEdges );
2169 if ( aLoopEdgesIt.More() )
2171 const BRepMesh_Edge& anEdge = GetEdge( aLoopEdgesIt.Key() );
2172 Standard_Integer aFirstNode = anEdge.FirstNode();
2173 Standard_Integer aLastNode;
2174 Standard_Integer aPivotNode = anEdge.LastNode();
2175 Standard_Integer anEdgeId = aLoopEdgesIt.Key();
2177 Standard_Boolean isPositive = aLoopEdges( anEdgeId ) != 0;
2180 Standard_Integer aTmp;
2182 aFirstNode = aPivotNode;
2185 aPolygon.Append( -anEdgeId );
2188 aPolygon.Append( anEdgeId );
2190 fillBndBox( aBoxes, GetVertex( aFirstNode ), GetVertex( aPivotNode ) );
2192 aLoopEdges.UnBind( anEdgeId );
2194 aLastNode = aFirstNode;
2195 while ( aPivotNode != aLastNode )
2197 IMeshData::ListOfInteger::Iterator aLinkIt( myMeshData->LinksConnectedTo( aPivotNode ) );
2198 for ( ; aLinkIt.More(); aLinkIt.Next() )
2200 if ( aLinkIt.Value() != anEdgeId &&
2201 aLoopEdges.IsBound( aLinkIt.Value() ) )
2203 Standard_Integer aCurrentNode;
2204 anEdgeId = aLinkIt.Value();
2205 const BRepMesh_Edge& anEdge1 = GetEdge( anEdgeId );
2207 aCurrentNode = anEdge1.LastNode();
2208 if ( aCurrentNode != aPivotNode )
2210 aCurrentNode = anEdge1.FirstNode();
2211 aPolygon.Append( -anEdgeId );
2214 aPolygon.Append( anEdgeId );
2216 fillBndBox( aBoxes, GetVertex( aCurrentNode ), GetVertex( aPivotNode ) );
2218 aPivotNode = aCurrentNode;
2219 aLoopEdges.UnBind( anEdgeId );
2224 if ( aLoopEdgesCount <= 0 )
2229 meshPolygon( aPolygon, aBoxes );
2234 //=======================================================================
2235 //function : AddVertices
2236 //purpose : Adds some vertices in the triangulation.
2237 //=======================================================================
2238 void BRepMesh_Delaun::AddVertices(IMeshData::VectorOfInteger& theVertices,
2239 const Message_ProgressRange& theRange)
2241 ComparatorOfIndexedVertexOfDelaun aCmp(myMeshData);
2242 std::make_heap(theVertices.begin(), theVertices.end(), aCmp);
2243 std::sort_heap(theVertices.begin(), theVertices.end(), aCmp);
2245 createTrianglesOnNewVertices(theVertices, theRange);
2248 //=======================================================================
2249 //function : UseEdge
2250 //purpose : Modify mesh to use the edge. Return True if done
2251 //=======================================================================
2252 Standard_Boolean BRepMesh_Delaun::UseEdge( const Standard_Integer /*theIndex*/ )
2255 const BRepMesh_PairOfIndex& aPair = myMeshData->ElemConnectedTo( theIndex );
2256 if ( aPair.Extent() == 0 )
2258 const BRepMesh_Edge& anEdge = GetEdge( theIndex );
2260 Standard_Integer aStartNode, aPivotNode, anOtherNode;
2261 aStartNode = anEdge.FirstNode();
2262 aPivotNode = anEdge.LastNode();
2264 const BRepMesh_ListOfInteger& aStartNodeNeighbors = myMeshData->LinkNeighboursOf( aStartNode );
2265 const BRepMesh_ListOfInteger& aPivotNodeNeighbors = myMeshData->LinkNeighboursOf( aPivotNode );
2267 if ( aStartNodeNeighbors.Extent() > 0 &&
2268 aPivotNodeNeighbors.Extent() > 0 )
2270 const BRepMesh_Vertex& aStartVertex = GetVertex( aStartNode );
2271 const BRepMesh_Vertex& aPivotVertex = GetVertex( aPivotNode );
2273 gp_XY aVEdge ( aPivotVertex.Coord() );
2274 aVEdge.Subtract( aStartVertex.Coord() );
2276 Standard_Real anAngle = 0.;
2277 Standard_Real anAngleMin = RealLast();
2278 Standard_Real anAngleMax = RealFirst();
2279 Standard_Integer aLeftEdge = 0, aRightEdge = 0;
2281 BRepMesh_ListOfInteger::Iterator aNeighborIt( aPivotNodeNeighbors );
2282 for ( ; aNeighborIt.More(); aNeighborIt.Next() )
2284 Standard_Integer anEdgeId = aNeighborIt.Value();
2285 if ( anEdgeId != theIndex )
2287 const BRepMesh_Edge& aNextEdge = GetEdge( anEdgeId );
2289 Standard_Boolean isInMesh = Standard_True;
2290 if ( aNextEdge.Movability() == BRepMesh_Free )
2292 if ( myMeshData->ElemConnectedTo( anEdgeId ).IsEmpty() )
2293 isInMesh = Standard_False;
2298 anOtherNode = aNextEdge.FirstNode();
2299 if ( anOtherNode == aPivotNode )
2300 anOtherNode = aNextEdge.LastNode();
2302 gp_XY aVEdgeCur = GetVertex( anOtherNode ).Coord();
2303 aVEdgeCur.Subtract( aPivotVertex.Coord() );
2305 anAngle = gp_Vec2d( aVEdge ).Angle( gp_Vec2d( aVEdgeCur ) );
2308 if ( anAngle > anAngleMax )
2310 anAngleMax = anAngle;
2311 aLeftEdge = anEdgeId;
2313 if ( anAngle < anAngleMin )
2315 anAngleMin = anAngle;
2316 aRightEdge = anEdgeId;
2321 if ( aLeftEdge > 0 )
2323 if (aLeftEdge==aRightEdge)
2333 return Standard_False;
2336 //=======================================================================
2337 //function : getEdgesByType
2338 //purpose : Gives the list of edges with type defined by input parameter
2339 //=======================================================================
2340 Handle(IMeshData::MapOfInteger) BRepMesh_Delaun::getEdgesByType(
2341 const BRepMesh_DegreeOfFreedom theEdgeType ) const
2343 Handle(NCollection_IncAllocator) anAlloc = new NCollection_IncAllocator;
2344 Handle(IMeshData::MapOfInteger) aResult = new IMeshData::MapOfInteger;
2345 IMeshData::IteratorOfMapOfInteger anEdgeIt( myMeshData->LinksOfDomain() );
2347 for ( ; anEdgeIt.More(); anEdgeIt.Next() )
2349 Standard_Integer anEdge = anEdgeIt.Key();
2350 Standard_Boolean isToAdd = (theEdgeType == BRepMesh_Free) ?
2351 (myMeshData->ElementsConnectedTo( anEdge ).Extent() <= 1) :
2352 (GetEdge( anEdge ).Movability() == theEdgeType);
2355 aResult->Add( anEdge );
2361 //=======================================================================
2362 //function : calculateDist
2363 //purpose : Calculates distances between the given point and edges of
2365 //=======================================================================
2366 Standard_Real BRepMesh_Delaun::calculateDist( const gp_XY theVEdges[3],
2367 const gp_XY thePoints[3],
2368 const BRepMesh_Vertex& theVertex,
2369 Standard_Real theDistance[3],
2370 Standard_Real theSqModulus[3],
2371 Standard_Integer& theEdgeOn ) const
2373 Standard_Real aMinDist = RealLast();
2374 for( Standard_Integer i = 0; i < 3; ++i )
2376 theSqModulus[i] = theVEdges[i].SquareModulus();
2377 if ( theSqModulus[i] <= Precision2 )
2380 theDistance[i] = theVEdges[i] ^ ( theVertex.Coord() - thePoints[i] );
2382 Standard_Real aDist = theDistance[i] * theDistance[i];
2383 aDist /= theSqModulus[i];
2385 if ( aDist < aMinDist )
2395 //=======================================================================
2396 //function : Contains
2397 //purpose : Test if triangle of index <TrianIndex> contains geometricaly
2398 // <theVertex>. If <theEdgeOn> is != 0 then theVertex is on Edge
2399 // of index <theEdgeOn>
2400 //=======================================================================
2401 Standard_Boolean BRepMesh_Delaun::Contains( const Standard_Integer theTriangleId,
2402 const BRepMesh_Vertex& theVertex,
2403 const Standard_Real theSqTolerance,
2404 Standard_Integer& theEdgeOn) const
2408 Standard_Integer p[3];
2410 const BRepMesh_Triangle& aElement = GetTriangle( theTriangleId );
2411 const Standard_Integer(&e)[3] = aElement.myEdges;
2413 const BRepMesh_Edge* anEdges[3] = { &GetEdge( e[0] ),
2417 myMeshData->ElementNodes(aElement, p);
2420 aPoints[0] = GetVertex( p[0] ).Coord();
2421 aPoints[1] = GetVertex( p[1] ).Coord();
2422 aPoints[2] = GetVertex( p[2] ).Coord();
2425 aVEdges[0] = aPoints[1];
2426 aVEdges[0].Subtract( aPoints[0] );
2428 aVEdges[1] = aPoints[2];
2429 aVEdges[1].Subtract( aPoints[1] );
2431 aVEdges[2] = aPoints[0];
2432 aVEdges[2].Subtract( aPoints[2] );
2434 Standard_Real aDistance[3];
2435 Standard_Real aSqModulus[3];
2437 Standard_Real aSqMinDist;
2438 Standard_Integer aEdgeOnId;
2439 aSqMinDist = calculateDist( aVEdges, aPoints, theVertex, aDistance, aSqModulus, aEdgeOnId );
2440 if ( aSqMinDist < 0 )
2441 return Standard_False;
2443 const Standard_Boolean isNotFree = (anEdges[aEdgeOnId]->Movability() != BRepMesh_Free);
2444 if ( aSqMinDist > theSqTolerance )
2446 if (isNotFree && aDistance[aEdgeOnId] < ( aSqModulus[aEdgeOnId] / 5. ))
2447 theEdgeOn = e[aEdgeOnId];
2450 return Standard_False;
2452 theEdgeOn = e[aEdgeOnId];
2454 return (aDistance[0] >= 0. && aDistance[1] >= 0. && aDistance[2] >= 0.);
2457 //=============================================================================
2458 //function : intSegSeg
2459 //purpose : Checks intersection between the two segments.
2460 //=============================================================================
2461 BRepMesh_GeomTool::IntFlag BRepMesh_Delaun::intSegSeg(
2462 const BRepMesh_Edge& theEdg1,
2463 const BRepMesh_Edge& theEdg2,
2464 const Standard_Boolean isConsiderEndPointTouch,
2465 const Standard_Boolean isConsiderPointOnEdge,
2466 gp_Pnt2d& theIntPnt) const
2468 gp_XY p1, p2, p3, p4;
2469 p1 = GetVertex( theEdg1.FirstNode() ).Coord();
2470 p2 = GetVertex( theEdg1.LastNode() ).Coord();
2471 p3 = GetVertex( theEdg2.FirstNode() ).Coord();
2472 p4 = GetVertex( theEdg2.LastNode() ).Coord();
2474 return BRepMesh_GeomTool::IntSegSeg(p1, p2, p3, p4,
2475 isConsiderEndPointTouch, isConsiderPointOnEdge, theIntPnt);
2478 //=============================================================================
2479 //function : polyArea
2480 //purpose : Returns area of the loop of the given polygon defined by indices
2481 // of its start and end links.
2482 //=============================================================================
2483 Standard_Real BRepMesh_Delaun::polyArea(const IMeshData::SequenceOfInteger& thePolygon,
2484 const Standard_Integer theStartIndex,
2485 const Standard_Integer theEndIndex) const
2487 Standard_Real aArea = 0.0;
2488 Standard_Integer aPolyLen = thePolygon.Length();
2489 if ( theStartIndex >= theEndIndex ||
2490 theStartIndex > aPolyLen )
2494 Standard_Integer aCurEdgeInfo = thePolygon( theStartIndex );
2495 Standard_Integer aCurEdgeId = Abs( aCurEdgeInfo );
2496 const BRepMesh_Edge* aCurEdge = &GetEdge( aCurEdgeId );
2498 Standard_Integer aNodes[2];
2499 getOrientedNodes( *aCurEdge, aCurEdgeInfo > 0, aNodes );
2501 gp_Pnt2d aRefPnt = GetVertex( aNodes[0] ).Coord();
2502 Standard_Integer aPolyIt = theStartIndex + 1;
2503 for ( ; aPolyIt <= theEndIndex; ++aPolyIt )
2505 aCurEdgeInfo = thePolygon( aPolyIt );
2506 aCurEdgeId = Abs( aCurEdgeInfo );
2507 aCurEdge = &GetEdge( aCurEdgeId );
2509 getOrientedNodes( *aCurEdge, aCurEdgeInfo > 0, aNodes );
2510 gp_Vec2d aVec1( aRefPnt, GetVertex( aNodes[0] ).Coord() );
2511 gp_Vec2d aVec2( aRefPnt, GetVertex( aNodes[1] ).Coord() );
2513 aArea += aVec1 ^ aVec2;
2520 //=======================================================================
2521 //function : BRepMesh_DumpPoly
2523 //=======================================================================
2524 #include <TopoDS_Compound.hxx>
2525 #include <BRep_Builder.hxx>
2526 #include <Standard_ErrorHandler.hxx>
2527 #include <BRepBuilderAPI_MakeEdge.hxx>
2528 #include <BRepTools.hxx>
2529 Standard_CString BRepMesh_DumpPoly(void* thePolygon,
2530 void* theMeshHandlePtr,
2531 Standard_CString theFileNameStr)
2533 if (thePolygon == 0 || theFileNameStr == 0)
2535 return "Error: file name or polygon data is null";
2538 IMeshData::SequenceOfInteger& aPolygon = *(IMeshData::SequenceOfInteger*)thePolygon;
2540 Handle(BRepMesh_DataStructureOfDelaun) aMeshData =
2541 *(Handle(BRepMesh_DataStructureOfDelaun)*)theMeshHandlePtr;
2543 if (aMeshData.IsNull())
2544 return "Error: mesh data is empty";
2546 TopoDS_Compound aMesh;
2547 BRep_Builder aBuilder;
2548 aBuilder.MakeCompound(aMesh);
2554 IMeshData::SequenceOfInteger::Iterator aLinksIt(aPolygon);
2555 for (; aLinksIt.More(); aLinksIt.Next())
2557 const BRepMesh_Edge& aLink = aMeshData->GetLink(Abs(aLinksIt.Value()));
2560 for (Standard_Integer i = 0; i < 2; ++i)
2562 const Standard_Integer aNodeId =
2563 (i == 0) ? aLink.FirstNode() : aLink.LastNode();
2565 const gp_XY& aNode = aMeshData->GetNode(aNodeId).Coord();
2566 aPnt[i] = gp_Pnt(aNode.X(), aNode.Y(), 0.);
2569 if (aPnt[0].SquareDistance(aPnt[1]) < Precision::SquareConfusion())
2572 aBuilder.Add(aMesh, BRepBuilderAPI_MakeEdge(aPnt[0], aPnt[1]));
2575 if (!BRepTools::Write(aMesh, theFileNameStr))
2576 return "Error: write failed";
2578 catch (Standard_Failure const& anException)
2580 return anException.GetMessageString();
2583 return theFileNameStr;