1 // Copyright (C) 2005 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN,
2 // CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
4 // This library is free software; you can redistribute it and/or
5 // modify it under the terms of the GNU Lesser General Public
6 // License as published by the Free Software Foundation; either
7 // version 2.1 of the License.
9 // This library is distributed in the hope that it will be useful
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 // Lesser General Public License for more details.
14 // You should have received a copy of the GNU Lesser General Public
15 // License along with this library; if not, write to the Free Software
16 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
20 // GEOM PARTITION : partition algorithm
22 // File : Partition_Loop2d.cxx
23 // Author : Benedicte MARTIN
27 #include "Partition_Loop2d.ixx"
29 #include "utilities.h"
32 #include <BRepAdaptor_Curve2d.hxx>
33 #include <BRepAdaptor_Surface.hxx>
34 #include <BRepAlgo_AsDes.hxx>
35 #include <BRepAlgo_FaceRestrictor.hxx>
36 #include <BRepOffset_DataMapOfShapeReal.hxx>
37 #include <BRepTopAdaptor_FClass2d.hxx>
38 #include <BRep_Builder.hxx>
39 #include <BRep_Tool.hxx>
40 #include <Geom2dInt_GInter.hxx>
41 #include <Geom2d_Curve.hxx>
42 #include <IntRes2d_IntersectionPoint.hxx>
43 #include <Precision.hxx>
44 #include <TColStd_MapOfInteger.hxx>
45 #include <TColStd_SequenceOfReal.hxx>
47 #include <TopExp_Explorer.hxx>
48 #include <TopTools_DataMapIteratorOfDataMapOfShapeListOfShape.hxx>
49 #include <TopTools_DataMapIteratorOfDataMapOfShapeShape.hxx>
50 #include <TopTools_DataMapOfShapeInteger.hxx>
51 #include <TopTools_DataMapOfShapeShape.hxx>
52 #include <TopTools_IndexedMapOfShape.hxx>
53 #include <TopTools_ListIteratorOfListOfShape.hxx>
54 #include <TopTools_MapIteratorOfMapOfShape.hxx>
55 #include <TopTools_MapOfOrientedShape.hxx>
56 #include <TopTools_MapOfShape.hxx>
57 #include <TopTools_SequenceOfShape.hxx>
59 #include <TopoDS_Iterator.hxx>
60 #include <TopoDS_Vertex.hxx>
61 #include <TopoDS_Wire.hxx>
63 #include <gp_Pnt2d.hxx>
67 //=======================================================================
68 //function : Partition_Loop2d
70 //=======================================================================
72 Partition_Loop2d::Partition_Loop2d()
76 //=======================================================================
78 //purpose : Init with <F> the set of edges must have
80 //=======================================================================
82 void Partition_Loop2d::Init(const TopoDS_Face& F)
88 myFaceOri = myFace.Orientation();
89 myFace.Orientation( TopAbs_FORWARD );
92 //=======================================================================
93 //function : AddConstEdge
94 //purpose : Add <E> as unique edge in the result.
95 //=======================================================================
97 void Partition_Loop2d::AddConstEdge (const TopoDS_Edge& E)
101 Handle(Geom2d_Curve) pc = BRep_Tool::CurveOnSurface( E, myFace, f,l);
103 INFOS( "AddConstEdge(): EDGE W/O PCURVE on FACE");
107 myConstEdges.Append(E);
111 void Partition_Loop2d::AddSectionEdge (const TopoDS_Edge& E)
115 Handle(Geom2d_Curve) pc = BRep_Tool::CurveOnSurface( E, myFace, f,l);
117 pc = BRep_Tool::CurveOnSurface( E, myFace, f,l);
120 pc->D1(0.5*(f+l), PC, Tg1);
121 if (Tg1.Magnitude() <= gp::Resolution()) {
125 INFOS( "AddConstEdge(): EDGE W/O PCURVE on FACE");
129 myConstEdges.Append(E);
130 myConstEdges.Append(E.Reversed());
131 mySectionEdges.Add( E );
135 //=======================================================================
136 //function : preciseU
137 //purpose : find u such that the 3D point on theE is just out of tolerance
139 //=======================================================================
141 static Standard_Real preciseU (const BRepAdaptor_Surface& theSurf,
142 const TopoDS_Edge& theE,
143 const TopoDS_Vertex& theV,
144 const Handle(Geom2d_Curve)& theC,
145 const Standard_Boolean theFirstEnd)
147 Standard_Boolean isForward = ( theE.Orientation () == TopAbs_FORWARD );
148 if (theFirstEnd) isForward = !isForward;
150 // find the first point in 2d and 3d
152 BRep_Tool::Range( theE, f, l );
153 Standard_Real u0 = isForward ? l : f;
154 gp_Pnt2d aP2d0 = theC->Value( u0 );
155 gp_Pnt aPnt0 = theSurf.Value( aP2d0.X(), aP2d0.Y() );
157 // shift in 2d and 3d
158 Standard_Real du = ( l - f ) / 100, du3d = 0;
165 while (du3d < ::RealSmall())
169 du *= 10; // for the next iteration: increase du untill du3d is large enough
171 // find out how u is far from u0 in 3D
172 gp_Pnt2d aP2d = theC->Value( u );
173 gp_Pnt aPnt = theSurf.Value( aP2d.X(), aP2d.Y() );
174 du3d = aPnt0.Distance( aPnt );
177 // find u such that the 3D point is just out of tolerance of theV
178 Standard_Real tolV = BRep_Tool::Tolerance( theV ) + Precision::Confusion();
179 u = u0 + du * tolV / du3d;
181 // check that u is within the range
182 if ( isForward ? (u < f) : (u > l) )
188 //=======================================================================
189 //function : SelectEdge
190 //purpose : Find in the list <LE> the edge <NE> connected with <CE> by
192 // <NE> is removed from the list. If <CE> is in <LE>
193 // with the same orientation, it's removed from the list
194 //=======================================================================
196 static Standard_Boolean SelectEdge(const BRepAdaptor_Surface& Surf,
197 const TopoDS_Edge& CE,
198 const TopoDS_Vertex& CV,
200 const TopTools_ListOfShape& LE)
204 if (LE.Extent() > 1) {
205 //--------------------------------------------------------------
206 // Several possible edges.
207 // - Test the edges differents of CE
208 //--------------------------------------------------------------
209 TopoDS_Face FForward = Surf.Face();
212 gp_Vec2d CTg1, Tg1, CTg2, Tg2;
216 Handle(Geom2d_Curve) Cc, C;
217 Cc = BRep_Tool::CurveOnSurface(CE,FForward,f,l);
219 Standard_Boolean isForward = ( CE.Orientation () == TopAbs_FORWARD );
220 Standard_Real uc, u, du = Precision::PConfusion();
221 uc = isForward ? ( l - du ) : ( f + du );
222 Cc->D1(uc, PC, CTg1);
223 if (!isForward) CTg1.Reverse();
225 Standard_Real anglemin = 3 * PI, tolAng = 1.e-8;
227 // select an edge whose first derivative is most left of CTg1
228 // ie an angle between Tg1 and CTg1 is least
229 TopTools_ListIteratorOfListOfShape itl;
230 for ( itl.Initialize(LE); itl.More(); itl.Next()) {
231 const TopoDS_Edge& E = TopoDS::Edge(itl.Value());
234 if (! CV.IsSame( TopExp::FirstVertex( E, Standard_True )))
237 isForward = ( E.Orientation () == TopAbs_FORWARD );
240 C = BRep_Tool::CurveOnSurface(E,FForward,f,l);
241 // get the first derivative Tg1
242 u = isForward ? ( f + du ) : ( l - du );
244 if (!isForward) Tg1.Reverse();
247 Standard_Real angle = Tg1.Angle(CTg1);
249 if (PI - Abs(angle) <= tolAng)
251 // an angle is too close to PI; assure that an angle sign really
252 // reflects an edge position: +PI - an edge is worst,
253 // -PI - an edge is best.
254 u = preciseU( Surf, CE, CV, Cc, Standard_False);
257 if (CE.Orientation() == TopAbs_REVERSED) CTg.Reverse();
259 u = preciseU( Surf, E, CV, C, Standard_True);
261 if (!isForward) Tg1.Reverse();
263 angle = Tg1.Angle(CTg);
266 Standard_Boolean isClose = ( Abs( angle - anglemin ) <= tolAng );
267 if (angle <= anglemin) {
280 if (!aPrevNE.IsNull()) {
281 // select one of close edges, the most left one.
282 Cc = BRep_Tool::CurveOnSurface( NE, FForward, f, l );
283 uc = preciseU( Surf, NE, CV, Cc, Standard_True);
284 Cc->D1(uc, PC, CTg1);
285 if (NE.Orientation() != TopAbs_FORWARD) CTg1.Reverse();
287 u = preciseU( Surf, aPrevNE, CV, C, Standard_True);
289 if (aPrevNE.Orientation() != TopAbs_FORWARD) Tg1.Reverse();
291 if ( Tg1.Angle(CTg1) < 0)
295 else if (LE.Extent() == 1) {
296 NE = TopoDS::Edge(LE.First());
299 return Standard_False;
304 //=======================================================================
305 //function : SamePnt2d
307 //=======================================================================
309 static Standard_Boolean SamePnt2d(const TopoDS_Vertex& V1,
310 const TopoDS_Edge& E1,
311 const TopoDS_Vertex& V2,
312 const TopoDS_Edge& E2,
313 const TopoDS_Face& F)
315 Standard_Real f1,f2,l1,l2;
316 Handle(Geom2d_Curve) C1 = BRep_Tool::CurveOnSurface(E1,F,f1,l1);
317 Handle(Geom2d_Curve) C2 = BRep_Tool::CurveOnSurface(E2,F,f2,l2);
319 gp_Pnt2d P1 = C1->Value( BRep_Tool::Parameter(V1,E1));
320 gp_Pnt2d P2 = C2->Value( BRep_Tool::Parameter(V2,E2));
322 Standard_Real Tol = 100 * BRep_Tool::Tolerance(V1);
323 Standard_Real Dist = P1.Distance(P2);
328 //=======================================================================
329 //function : StoreInMVE
331 //=======================================================================
333 static void StoreInMVE (const TopoDS_Face& /*F*/,
335 TopTools_DataMapOfShapeListOfShape& MVE )
338 TopoDS_Vertex V1, V2;
339 TopTools_ListOfShape Empty;
341 TopExp::Vertices(E,V1,V2);
342 if (!MVE.IsBound(V1)) {
347 if (!MVE.IsBound(V2)) {
353 //=======================================================================
354 //function : RemoveFromMVE
356 //=======================================================================
358 static void RemoveFromMVE(const TopoDS_Edge& E,
359 TopTools_DataMapOfShapeListOfShape& MVE)
361 TopTools_ListIteratorOfListOfShape itl;
363 TopExp::Vertices (E,V1,V2);
365 for ( itl.Initialize(MVE(V1)); itl.More(); itl.Next()) {
366 if (itl.Value().IsEqual(E)) {
372 for ( itl.Initialize(MVE(V2)); itl.More(); itl.Next()) {
373 if (itl.Value().IsEqual(E)) {
379 //=======================================================================
380 //function : addConnected
381 //purpose : add to <EM> all edges reachable from <E>
382 //=======================================================================
384 static void addConnected(const TopoDS_Shape& E,
385 TopTools_MapOfShape& EM,
386 TopTools_MapOfShape& VM,
387 const TopTools_DataMapOfShapeListOfShape& MVE)
389 // Loop on vertices of E
390 TopoDS_Iterator itV ( E );
391 for ( ; itV.More(); itV.Next()) {
393 if ( ! VM.Add ( itV.Value() )) continue;
395 // Loop on edges sharing V
396 TopTools_ListIteratorOfListOfShape itE( MVE( itV.Value() ) );
397 for (; itE.More(); itE.Next()) {
398 if ( EM.Add( itE.Value() ))
399 addConnected ( itE.Value(), EM, VM, MVE );
403 //=======================================================================
404 //function : canPassToOld
406 //=======================================================================
408 // static Standard_Boolean canPassToOld (const TopoDS_Shape& V,
409 // TopTools_MapOfShape& UsedShapesMap,
410 // const TopTools_DataMapOfShapeListOfShape& MVE,
411 // const TopTools_MapOfShape& SectionEdgesMap)
413 // TopTools_ListIteratorOfListOfShape itE( MVE(V) );
414 // // Loop on edges sharing V
415 // for (; itE.More(); itE.Next()) {
416 // if ( !UsedShapesMap.Add( itE.Value() ))
417 // continue; // already checked
419 // if ( !SectionEdgesMap.Contains( itE.Value() ))
420 // return Standard_True; // WE PASSED
422 // TopoDS_Iterator itV( itE.Value() );
423 // // Loop on vertices of an edge
424 // for (; itV.More(); itV.Next()) {
425 // if ( !UsedShapesMap.Add( itV.Value() ))
426 // continue; // already checked
428 // return canPassToOld( itV.Value(), UsedShapesMap, MVE, SectionEdgesMap);
431 // return Standard_False;
434 //=======================================================================
435 //function : MakeDegenAndSelect
436 //purpose : Find parameter of intersection of <CE> with <DE> and
437 // select an edge with its parameter closest to found one.
438 // Return new degenerated edge trimming <DE> by found parameters
439 //=======================================================================
441 static TopoDS_Edge MakeDegenAndSelect(const TopoDS_Edge& CE,
442 const TopoDS_Vertex& CV,
444 TopTools_SequenceOfShape& EdgesSeq,
445 TColStd_SequenceOfReal& USeq,
446 const TopoDS_Edge& DE)
448 if (EdgesSeq.Length() < 3) {
449 if (CE == EdgesSeq.First())
450 NE = TopoDS::Edge( EdgesSeq.Last() );
452 NE = TopoDS::Edge( EdgesSeq.First() );
456 // find parameter on DE where it intersects CE
459 Standard_Integer i, nb = EdgesSeq.Length();
460 for (i=1; i<= nb; ++i) {
461 if (CE == EdgesSeq(i)) {
467 // select NE with param closest to U1 thus finding U2 for a new degen edge
469 Standard_Real U2, dU, dUmin = 1.e100;
470 Standard_Boolean isReversed = ( DE.Orientation() == TopAbs_REVERSED );
471 for (i=1; i<= nb; ++i) {
473 if (isReversed ? (dU > 0) : (dU < 0))
476 if ( dU > dUmin || IsEqual( dU, 0.))
478 const TopoDS_Edge& E = TopoDS::Edge ( EdgesSeq(i) );
479 if ( ! CV.IsSame( TopExp::FirstVertex( E , Standard_True )))
482 dUmin = dU + Epsilon(dU);
486 // make a new degenerated edge
487 TopoDS_Edge NewDegen = TopoDS::Edge ( DE.EmptyCopied() );
489 Standard_Real Tol = BRep_Tool::Tolerance( CV );
490 TopoDS_Vertex V = CV;
493 V.Orientation( NewDegen.Orientation() );
494 B.UpdateVertex( V, U1, NewDegen, Tol);
495 B.Add ( NewDegen , V );
498 B.UpdateVertex( V, U2, NewDegen, Tol);
499 B.Add ( NewDegen , V );
504 //=======================================================================
505 //function : prepareDegen
506 //purpose : Intersect <DegEdge> with edges bound to its vertex in <MVE>
507 // and store intersection parameter on <DegEdge> in
508 // <USeq> as well as the edges them-self in <EdgesSeq>.
509 // Bind <DegEdgeIndex> to vertex of <DegEdge> in <MVDEI>
510 //=======================================================================
512 static void prepareDegen (const TopoDS_Edge& DegEdge,
513 const TopoDS_Face& F,
514 const TopTools_DataMapOfShapeListOfShape& MVE,
515 TopTools_SequenceOfShape& EdgesSeq,
516 TColStd_SequenceOfReal& USeq,
517 TopTools_DataMapOfShapeInteger& MVDEI,
518 const Standard_Integer DegEdgeIndex)
520 const TopoDS_Vertex& V = TopExp::FirstVertex ( DegEdge );
521 MVDEI.Bind ( V, DegEdgeIndex );
523 const TopTools_ListOfShape& EdgesList = MVE ( V );
524 // if only 2 edges come to degenerated one, no pb in selection and
525 // no need to intersect them, just simulate asked data
526 Standard_Boolean doIntersect = ( EdgesList.Extent() > 2 );
528 BRepAdaptor_Curve2d DC, C;
529 Geom2dInt_GInter InterCC;
530 Standard_Real Tol = Precision::PConfusion();
532 DC.Initialize( DegEdge, F );
534 // avoid intersecting twice the same edge
535 BRepOffset_DataMapOfShapeReal EUMap ( EdgesList.Extent() );
537 Standard_Real U, f, l;
538 BRep_Tool::Range (DegEdge, f, l);
540 TopTools_ListIteratorOfListOfShape itE (EdgesList);
541 for (; itE.More(); itE.Next()) {
543 const TopoDS_Edge& E = TopoDS::Edge ( itE.Value() );
546 U = 0.; // it won't be used
548 else if ( BRep_Tool::IsClosed( E, F )) {
549 // seam edge: select U among f and l
550 Standard_Boolean first = Standard_True;
551 if ( V.IsSame ( TopExp::FirstVertex( E, Standard_True ) ))
552 first = Standard_False;
553 if ( DegEdge.Orientation() == TopAbs_REVERSED )
557 else if ( EUMap.IsBound( E ) ) {
558 // same edge already bound
562 // intersect 2d curves
563 C.Initialize( E, F );
564 InterCC.Perform ( DC, C , Tol, Tol );
565 if (! InterCC.IsDone() || InterCC.NbPoints() == 0) {
566 MESSAGE ( "NO 2d INTERSECTION ON DEGENERATED EDGE" );
569 // hope there is only one point of intersection
570 U = InterCC.Point( 1 ).ParamOnFirst();
573 EdgesSeq.Append ( E );
576 //=======================================================================
578 //purpose : Make loops.
579 //=======================================================================
581 void Partition_Loop2d::Perform()
584 Standard_Integer NbConstEdges = myConstEdges.Extent();
585 TopTools_DataMapOfShapeListOfShape MVE(NbConstEdges) , MVE2(NbConstEdges);
586 TopTools_DataMapIteratorOfDataMapOfShapeListOfShape Mapit;
587 TopTools_ListIteratorOfListOfShape itl;
589 BRepAdaptor_Surface Surface ( myFace, Standard_False );
591 // degenerated edges and parameters of their 2d intersection with other edges
593 TopTools_SequenceOfShape SEID [2]; // seq of edges intersecting degenerated
594 TColStd_SequenceOfReal SeqU [2]; // n-th U corresponds to n-th edge in SEID
595 TopTools_DataMapOfShapeInteger MVDEI(2); // map vertex - degenerated edge index
596 Standard_Integer iDeg = 0; // index of degenerated edge [0,1]
598 //---------------------------------------------------------
599 // Construction map vertex => edges, find degenerated edges
600 //---------------------------------------------------------
601 for (itl.Initialize(myConstEdges); itl.More(); itl.Next()) {
602 TopoDS_Edge& E = TopoDS::Edge(itl.Value());
603 if ( BRep_Tool::Degenerated( E )) {
604 if (DE[0].IsNull()) DE[0] = E;
608 StoreInMVE(myFace,E,MVE);
611 // fill data for degenerated edges
612 if ( ! DE[0].IsNull() )
613 prepareDegen ( DE[0], myFace, MVE, SEID[0], SeqU[0], MVDEI, 0);
614 if ( ! DE[1].IsNull() )
615 prepareDegen ( DE[1], myFace, MVE, SEID[1], SeqU[1], MVDEI, 1);
618 // to detect internal wires
619 Standard_Boolean isInternCW = 0;
623 //------------------------------
624 // Construction of all the wires
625 //------------------------------
626 // first, we collect wire edges in WEL list looking for same edges that
627 // will be then removed possibly exploding a wire into parts;
628 // second, build wire(s)
630 while (!MVE.IsEmpty()) {
633 TopoDS_Edge CE,NE,EF;
636 Standard_Boolean End = Standard_False;
637 TopTools_ListOfShape WEL;
639 Mapit.Initialize(MVE);
640 if (Mapit.Value().IsEmpty()) {
641 MVE.UnBind(Mapit.Key());
646 EF = CE = TopoDS::Edge(Mapit.Value().First());
648 VF = TopExp::FirstVertex( CE, Standard_True);
650 isInternCW = Standard_True;
652 TopTools_MapOfShape addedEM (NbConstEdges); // map of edges added to WEL
653 TopTools_MapOfShape doubleEM (NbConstEdges); // edges encountered twice in WEL
655 //-------------------------------
656 // Construction of a wire.
657 //-------------------------------
660 // only a seam is allowed twice in a wire, the others should be removed
661 if (addedEM.Add ( CE ) || BRep_Tool::IsClosed( CE, myFace ) )
665 RemoveFromMVE (CE,MVE2);
666 TopoDS_Edge CERev = CE;
668 RemoveFromMVE (CERev,MVE2);
671 RemoveFromMVE (CE,MVE);
673 CV = TopExp::LastVertex( CE, Standard_True);
675 if (isInternCW && !mySectionEdges.Contains(CE))
676 // wire is internal if all edges are section ones
677 isInternCW = Standard_False;
679 if (MVDEI.IsBound( CV )) { // CE comes to the degeneration
681 TopoDS_Edge NewDegen;
682 NewDegen = MakeDegenAndSelect( CE, CV, NE, SEID[iDeg], SeqU[iDeg], DE[iDeg]);
683 WEL.Append( NewDegen );
685 End = CV.IsSame( VF );
692 if (MVE(CV).IsEmpty()) {
696 else if (CV.IsSame(VF) && SamePnt2d(CV,CE, VF,EF, myFace) ) {
700 //----------------------------
701 // select new current edge
702 //----------------------------
703 if (! SelectEdge (Surface,CE,CV,NE,MVE(CV))) {
704 MESSAGE ( " NOT CLOSED WIRE " );
713 // WEL is built, built wire(s)
716 itl.Initialize( WEL );
717 if ( doubleEM.IsEmpty()) { // no double edges
719 for (; itl.More(); itl.Next())
720 B.Add ( NW, itl.Value());
721 if (isInternCW) myInternalWL.Append(NW);
722 else myNewWires.Append (NW);
726 // remove double and degenerated edges from WEL
728 const TopoDS_Edge& E = TopoDS::Edge ( itl.Value() );
729 if ( doubleEM.Contains( E ) || BRep_Tool::Degenerated( E ))
736 // remove double edges from SEID and SeqU
737 Standard_Integer i,j;
738 for (j=0; j<2; ++j) {
739 for (i=1; i<=SEID[j].Length(); ++i) {
740 if (doubleEM.Contains( SEID[j].Value(i))) {
742 SeqU[j].Remove( i-- );
746 // removal of doulbe edges can explode a wire into parts,
747 // make new wires of them.
748 // A Loop like previous one but without 2d check
749 while ( !WEL.IsEmpty() ) {
750 CE = TopoDS::Edge( WEL.First() );
753 VF = TopExp::FirstVertex ( CE, Standard_True);
755 End = Standard_False;
758 CV = TopExp::LastVertex ( CE, Standard_True);
760 if (MVDEI.IsBound( CV )) { // CE comes to the degeneration
762 TopoDS_Edge NewDegen;
763 NewDegen = MakeDegenAndSelect( CE, CV, NE, SEID[iDeg], SeqU[iDeg], DE[iDeg]);
764 B.Add( NW, NewDegen );
765 End = CV.IsSame( VF );
767 if (!NE.IsNull()) { // remove NE from WEL
768 for (itl.Initialize( WEL ); itl.More(); itl.Next())
769 if ( NE == itl.Value()) {
774 } // end degeneration
777 if (CV.IsSame( VF )) {
781 // edges in WEL most often are well ordered
782 // so try to iterate until the End
783 Standard_Boolean add = Standard_False;
785 while ( itl.More() && !End) {
786 NE = TopoDS::Edge( itl.Value() );
787 if ( CV.IsSame( TopExp::FirstVertex( NE, Standard_True ))) {
793 CV = TopExp::LastVertex( CE, Standard_True);
794 if (MVDEI.IsBound( CV ) || CV.IsSame( VF ))
805 myInternalWL.Append( NW );
807 } // end building new wire(s) from WEL
811 // all wires are built
814 // ============================================================
815 // select really internal wires i.e. those from which we can`t
816 // pass to an old (not section) edge
817 // ============================================================
819 Standard_Integer nbIW = myInternalWL.Extent();
823 if ( myNewWires.Extent() != 1 && nbIW > 1) {
824 TopTools_MapOfShape outerEM (NbConstEdges); // edges connected to non-section ones
825 TopTools_MapOfShape visitedVM (NbConstEdges);
826 for ( itl.Initialize( myConstEdges ); itl.More(); itl.Next()) {
827 if ( ! mySectionEdges.Contains( itl.Value() ))
828 addConnected (itl.Value(), outerEM, visitedVM, MVE2);
830 // if an edge of a wire is in <outerEM>, the wire is not internal
831 TopExp_Explorer expIWE;
832 TopTools_ListIteratorOfListOfShape itIW ( myInternalWL );
833 while (itIW.More()) {
834 expIWE.Init ( itIW.Value() , TopAbs_EDGE );
835 if ( outerEM.Contains( expIWE.Current() )) {
836 myNewWires.Append ( itIW.Value() );
837 myInternalWL.Remove( itIW ); // == itIW.Next()
844 //=======================================================================
847 //=======================================================================
849 static Standard_Boolean isHole (const TopoDS_Wire& W,
850 const TopoDS_Face& F)
853 TopoDS_Shape newFace = F.EmptyCopied();
854 B.Add(newFace,W.Oriented(TopAbs_FORWARD));
855 BRepTopAdaptor_FClass2d classif (TopoDS::Face(newFace),
856 Precision::PConfusion());
857 return (classif.PerformInfinitePoint() == TopAbs_IN);
860 //=======================================================================
861 //function : IsInside
862 //purpose : check if W1 is inside W2. Suppose W2 is not a hole !!!!
863 //=======================================================================
865 static Standard_Boolean isInside(const TopoDS_Face& F,
866 const TopoDS_Wire& W1,
867 const TopoDS_Wire& W2)
869 // make a face with wire W2
871 TopoDS_Shape aLocalShape = F.EmptyCopied();
872 TopoDS_Face newFace = TopoDS::Face(aLocalShape);
875 // get any 2d point of W1
876 TopExp_Explorer exp(W1,TopAbs_EDGE);
877 if (BRep_Tool::Degenerated( TopoDS::Edge( exp.Current() )))
879 const TopoDS_Edge& e = TopoDS::Edge(exp.Current());
881 Handle(Geom2d_Curve) C2d = BRep_Tool::CurveOnSurface(e,F,f,l);
882 gp_Pnt2d pt2d(C2d->Value( 0.5 * ( f + l )));
884 BRepTopAdaptor_FClass2d classif(newFace,Precision::PConfusion());
885 return (classif.Perform(pt2d) == TopAbs_IN);
888 //=======================================================================
889 //function : NewWires
890 //purpose : Returns the list of wires performed.
891 // can be an empty list.
892 //=======================================================================
894 const TopTools_ListOfShape& Partition_Loop2d::NewWires() const
899 //=======================================================================
900 //function : NewFaces
901 //purpose : Returns the list of faces.
902 //Warning : The method <WiresToFaces> as to be called before.
903 // can be an empty list.
904 //=======================================================================
906 const TopTools_ListOfShape& Partition_Loop2d::NewFaces() const
911 //=======================================================================
912 //function : findEqual
913 //purpose : move wires form <WL> to <EqWL> pairs of wires build of the same edges
914 //=======================================================================
916 static void findEqual (TopTools_ListOfShape& WL,
917 TopTools_DataMapOfShapeShape& EqWM,
918 const TopoDS_Face& F)
920 TopTools_ListIteratorOfListOfShape it1, it2;
921 Standard_Integer i,j;
922 TColStd_MapOfInteger IndMap;
923 for (it1.Initialize(WL), i=1; it1.More(); it1.Next(), i++) {
925 if (IndMap.Contains(i)) continue;
926 const TopoDS_Wire& Wire1 = TopoDS::Wire( it1.Value());
928 for (it2.Initialize(WL), j=1; it2.More(); it2.Next(), j++) {
930 if (j <= i || IndMap.Contains(j)) continue;
932 TopTools_IndexedMapOfShape EdgesMap;
933 TopExp::MapShapes (Wire1, TopAbs_EDGE, EdgesMap);
935 const TopoDS_Shape& Wire2 = it2.Value();
936 TopoDS_Iterator itE ( Wire2);
937 for (; itE.More(); itE.Next()) {
938 if ( !EdgesMap.Contains( itE.Value()) )
941 if (!itE.More()) { // all edges are same
942 if (isHole( Wire1, F)) {
943 EqWM.Bind ( Wire1, Wire2 );
946 EqWM.Bind ( Wire2, Wire1 );
958 if (IndMap.Contains(i))
959 WL.Remove(it1); // next node becomes current and with Next() we would miss it
966 //=======================================================================
967 //function : classify
968 //purpose : bind to a wire a list of internal wires
969 //=======================================================================
971 static void classify(const TopTools_DataMapOfShapeShape& EqWM,
972 BRepAlgo_AsDes& OuterInner,
973 const TopoDS_Face& F)
975 TopTools_DataMapIteratorOfDataMapOfShapeShape it1, it2;
977 for (it1.Initialize(EqWM); it1.More(); it1.Next()) {
978 // find next after it1.Value()
979 for (it2.Initialize(EqWM); it2.More(); it2.Next())
980 if (it1.Value().IsSame( it2.Value() ))
985 for ( ; it2.More(); it2.Next()) {
986 const TopoDS_Wire& Wire1 = TopoDS::Wire( it1.Value() );
987 const TopoDS_Wire& Wire2 = TopoDS::Wire( it2.Value() );
988 if (isInside(F, Wire1, Wire2))
989 OuterInner.Add (Wire2, Wire1);
990 else if (isInside(F, Wire2, Wire1))
991 OuterInner.Add (Wire1, Wire2);
995 //=======================================================================
996 //function : WiresToFaces
997 //purpose : Build faces from the wires result.
998 // <EdgeImage> serves to find original edge by new
999 // one. <Section> contains edges resulting from face
1001 //=======================================================================
1003 void Partition_Loop2d::WiresToFaces(const BRepAlgo_Image& )
1005 Standard_Integer nbW = myNewWires.Extent() + myInternalWL.Extent();
1009 BRepAlgo_FaceRestrictor FR;
1010 FR.Init (myFace,Standard_False);
1012 // FaceRestrictor is instable in rather simple cases
1013 // (ex. a single face of bellecoque.brep splited by 10 planes:
1014 // sometimes 1-2 faces are missing ).
1015 // So we use it as less as possible: no holes -> make faces by hands
1018 // are there holes in myFace ?
1019 Standard_Boolean hasOldHoles = Standard_False;
1020 TopoDS_Iterator itOldW (myFace);
1021 if ( itOldW.More()) {
1022 const TopoDS_Wire& FirstOldWire = TopoDS::Wire( itOldW.Value() );
1024 hasOldHoles = itOldW.More() || isHole( FirstOldWire, myFace);
1026 if (myInternalWL.IsEmpty() && !hasOldHoles) {
1027 // each wire bounds one face
1029 TopTools_ListIteratorOfListOfShape itNW (myNewWires);
1030 for (; itNW.More(); itNW.Next()) {
1031 TopoDS_Face NF = TopoDS::Face ( myFace.EmptyCopied() );
1032 B.Add ( NF, itNW.Value() );
1033 NF.Orientation( myFaceOri);
1034 myNewFaces.Append ( NF );
1039 // FaceRestrictor can't classify wires build on all the same edges
1040 // and gives incorrect result in such cases (ex. a plane cut into 2 parts by cylinder)
1041 // We must make faces of equal wires separately. One of equal wires makes a
1042 // hole in a face and should come together with outer wires of face.
1043 // The other of a wires pair bounds a face that may have holes in turn.
1045 // Find equal wires among internal wires
1046 TopTools_DataMapOfShapeShape EqWM; // key is a hole part of a pair of equal wires
1047 findEqual (myInternalWL, EqWM, myFace);
1049 if (!EqWM.IsEmpty()) { // there are equal wires
1052 myInternalWL.Append( myNewWires ); // an old wire can be inside an equal wire
1054 // classify equal wire pairs
1055 BRepAlgo_AsDes OuterInner;
1056 classify (EqWM,OuterInner,myFace);
1058 // make face of most internal of equal wires and its inner wires
1059 while ( !EqWM.IsEmpty()) {
1061 TopTools_ListOfShape prevHolesL; // list of hole-part of previous most internal equal wires
1063 // find most internal wires among pairs (key - hole, value - outer part)
1064 TopTools_DataMapIteratorOfDataMapOfShapeShape it(EqWM);
1065 Standard_Integer nbEqW = EqWM.Extent(); // protection against infinite loop
1066 for ( ; it.More(); it.Next()) {
1068 TopoDS_Wire outerW = TopoDS::Wire ( it.Value() );
1069 if ( OuterInner.HasDescendant( outerW ) && // has internal
1070 ! OuterInner.Descendant( outerW ).IsEmpty() )
1075 // add internal wires that are inside of outerW
1076 TopTools_ListIteratorOfListOfShape itIW (myInternalWL);
1077 while ( itIW.More()) {
1078 TopoDS_Wire IW = TopoDS::Wire ( itIW.Value() );
1079 if ( isInside (myFace, IW, outerW)) {
1081 myInternalWL.Remove( itIW ); // == itIW.Next() !!!
1087 // the hole-part of current pair of equal wires will be in the next new face
1088 prevHolesL.Append ( it.Key() );
1090 } // Loop on map of equal pairs searching for innermost wires
1095 for (; FR.More(); FR.Next())
1096 myNewFaces.Append(FR.Current());
1101 // add hole-parts to FaceRestrictor,
1102 // remove them from the EqWM,
1103 // remove found wires as internal of resting classified wires
1104 Standard_Boolean clearOuterInner = ( prevHolesL.Extent() < EqWM.Extent() );
1105 TopTools_ListIteratorOfListOfShape itPrev (prevHolesL);
1106 for (; itPrev.More(); itPrev.Next()) {
1107 TopoDS_Wire& Hole = TopoDS::Wire ( itPrev.Value() );
1109 if (clearOuterInner) {
1110 const TopoDS_Wire& outerW = TopoDS::Wire ( EqWM.Find( Hole ) );
1111 // Loop on wires including outerW
1112 TopTools_ListIteratorOfListOfShape itO( OuterInner.Ascendant( outerW ));
1113 for (; itO.More(); itO.Next()) {
1114 TopTools_ListOfShape& innerL = OuterInner.ChangeDescendant( itO.Value() );
1115 TopTools_ListIteratorOfListOfShape itI (innerL);
1116 // Loop on internal wires of current including wire
1117 for (; itI.More(); itI.Next())
1118 if ( outerW.IsSame( itI.Value() )) {
1119 innerL.Remove( itI ); break;
1123 EqWM.UnBind ( Hole );
1126 if (nbEqW == EqWM.Extent())
1128 // error: pb with wires classification
1130 MESSAGE("Partition_Loop2d::WiresToFaces(), pb with wires classification");
1135 } // while (!EqWM.IsEmpty)
1137 } // if !EqWM.IsEmpty()
1139 myNewWires.Append ( myInternalWL );
1141 TopTools_ListIteratorOfListOfShape itW (myNewWires);
1142 for (; itW.More(); itW.Next()) {
1143 TopoDS_Wire& W = TopoDS::Wire ( itW.Value() );
1147 for (; FR.IsDone() && FR.More(); FR.Next())
1148 myNewFaces.Append(FR.Current());
1151 TopTools_ListIteratorOfListOfShape itNF (myNewFaces);
1152 for (; itNF.More(); itNF.Next())
1153 itNF.Value().Orientation( myFaceOri );