1 // Copyright (C) 2007-2008 CEA/DEN, EDF R&D, OPEN CASCADE
3 // Copyright (C) 2003-2007 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN,
4 // CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
6 // This library is free software; you can redistribute it and/or
7 // modify it under the terms of the GNU Lesser General Public
8 // License as published by the Free Software Foundation; either
9 // version 2.1 of the License.
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // Lesser General Public License for more details.
16 // You should have received a copy of the GNU Lesser General Public
17 // License along with this library; if not, write to the Free Software
18 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
22 // GEOM PARTITION : partition algorithm
23 // File : Partition_Loop2d.cxx
24 // Author : Benedicte MARTIN
28 #include "Partition_Loop2d.ixx"
30 #include "utilities.h"
33 #include <BRepAdaptor_Curve2d.hxx>
34 #include <BRepAdaptor_Surface.hxx>
35 #include <BRepAlgo_AsDes.hxx>
36 #include <BRepAlgo_FaceRestrictor.hxx>
37 #include <BRepOffset_DataMapOfShapeReal.hxx>
38 #include <BRepTopAdaptor_FClass2d.hxx>
39 #include <BRep_Builder.hxx>
40 #include <BRep_Tool.hxx>
41 #include <Geom2dInt_GInter.hxx>
42 #include <Geom2d_Curve.hxx>
43 #include <IntRes2d_IntersectionPoint.hxx>
44 #include <Precision.hxx>
45 #include <TColStd_MapOfInteger.hxx>
46 #include <TColStd_SequenceOfReal.hxx>
48 #include <TopExp_Explorer.hxx>
49 #include <TopTools_DataMapIteratorOfDataMapOfShapeListOfShape.hxx>
50 #include <TopTools_DataMapIteratorOfDataMapOfShapeShape.hxx>
51 #include <TopTools_DataMapOfShapeInteger.hxx>
52 #include <TopTools_DataMapOfShapeShape.hxx>
53 #include <TopTools_IndexedMapOfShape.hxx>
54 #include <TopTools_ListIteratorOfListOfShape.hxx>
55 #include <TopTools_MapIteratorOfMapOfShape.hxx>
56 #include <TopTools_MapOfOrientedShape.hxx>
57 #include <TopTools_MapOfShape.hxx>
58 #include <TopTools_SequenceOfShape.hxx>
60 #include <TopoDS_Iterator.hxx>
61 #include <TopoDS_Vertex.hxx>
62 #include <TopoDS_Wire.hxx>
64 #include <gp_Pnt2d.hxx>
68 //=======================================================================
69 //function : Partition_Loop2d
71 //=======================================================================
73 Partition_Loop2d::Partition_Loop2d()
77 //=======================================================================
79 //purpose : Init with <F> the set of edges must have
81 //=======================================================================
83 void Partition_Loop2d::Init(const TopoDS_Face& F)
89 myFaceOri = myFace.Orientation();
90 myFace.Orientation( TopAbs_FORWARD );
93 //=======================================================================
94 //function : AddConstEdge
95 //purpose : Add <E> as unique edge in the result.
96 //=======================================================================
98 void Partition_Loop2d::AddConstEdge (const TopoDS_Edge& E)
102 Handle(Geom2d_Curve) pc = BRep_Tool::CurveOnSurface( E, myFace, f,l);
104 INFOS( "AddConstEdge(): EDGE W/O PCURVE on FACE");
108 myConstEdges.Append(E);
112 void Partition_Loop2d::AddSectionEdge (const TopoDS_Edge& E)
116 Handle(Geom2d_Curve) pc = BRep_Tool::CurveOnSurface( E, myFace, f,l);
118 pc = BRep_Tool::CurveOnSurface( E, myFace, f,l);
121 pc->D1(0.5*(f+l), PC, Tg1);
122 if (Tg1.Magnitude() <= gp::Resolution()) {
126 INFOS( "AddConstEdge(): EDGE W/O PCURVE on FACE");
130 myConstEdges.Append(E);
131 myConstEdges.Append(E.Reversed());
132 mySectionEdges.Add( E );
136 //=======================================================================
137 //function : preciseU
138 //purpose : find u such that the 3D point on theE is just out of tolerance
140 //=======================================================================
142 static Standard_Real preciseU (const BRepAdaptor_Surface& theSurf,
143 const TopoDS_Edge& theE,
144 const TopoDS_Vertex& theV,
145 const Handle(Geom2d_Curve)& theC,
146 const Standard_Boolean theFirstEnd)
148 Standard_Boolean isForward = ( theE.Orientation () == TopAbs_FORWARD );
149 if (theFirstEnd) isForward = !isForward;
151 // find the first point in 2d and 3d
153 BRep_Tool::Range( theE, f, l );
154 Standard_Real u0 = isForward ? l : f;
155 gp_Pnt2d aP2d0 = theC->Value( u0 );
156 gp_Pnt aPnt0 = theSurf.Value( aP2d0.X(), aP2d0.Y() );
158 // shift in 2d and 3d
159 Standard_Real du = ( l - f ) / 100, du3d = 0;
166 while (du3d < ::RealSmall())
170 du *= 10; // for the next iteration: increase du untill du3d is large enough
172 // find out how u is far from u0 in 3D
173 gp_Pnt2d aP2d = theC->Value( u );
174 gp_Pnt aPnt = theSurf.Value( aP2d.X(), aP2d.Y() );
175 du3d = aPnt0.Distance( aPnt );
178 // find u such that the 3D point is just out of tolerance of theV
179 Standard_Real tolV = BRep_Tool::Tolerance( theV ) + Precision::Confusion();
180 u = u0 + du * tolV / du3d;
182 // check that u is within the range
183 if ( isForward ? (u < f) : (u > l) )
189 //=======================================================================
190 //function : SelectEdge
191 //purpose : Find in the list <LE> the edge <NE> connected with <CE> by
193 // <NE> is removed from the list. If <CE> is in <LE>
194 // with the same orientation, it's removed from the list
195 //=======================================================================
197 static Standard_Boolean SelectEdge(const BRepAdaptor_Surface& Surf,
198 const TopoDS_Edge& CE,
199 const TopoDS_Vertex& CV,
201 const TopTools_ListOfShape& LE)
205 if (LE.Extent() > 1) {
206 //--------------------------------------------------------------
207 // Several possible edges.
208 // - Test the edges differents of CE
209 //--------------------------------------------------------------
210 TopoDS_Face FForward = Surf.Face();
213 gp_Vec2d CTg1, Tg1, CTg2, Tg2;
217 Handle(Geom2d_Curve) Cc, C;
218 Cc = BRep_Tool::CurveOnSurface(CE,FForward,f,l);
220 Standard_Boolean isForward = ( CE.Orientation () == TopAbs_FORWARD );
221 Standard_Real uc, u, du = Precision::PConfusion();
222 uc = isForward ? ( l - du ) : ( f + du );
223 Cc->D1(uc, PC, CTg1);
224 if (!isForward) CTg1.Reverse();
226 Standard_Real anglemin = 3 * PI, tolAng = 1.e-8;
228 // select an edge whose first derivative is most left of CTg1
229 // ie an angle between Tg1 and CTg1 is least
230 TopTools_ListIteratorOfListOfShape itl;
231 for ( itl.Initialize(LE); itl.More(); itl.Next()) {
232 const TopoDS_Edge& E = TopoDS::Edge(itl.Value());
235 if (! CV.IsSame( TopExp::FirstVertex( E, Standard_True )))
238 isForward = ( E.Orientation () == TopAbs_FORWARD );
241 C = BRep_Tool::CurveOnSurface(E,FForward,f,l);
242 // get the first derivative Tg1
243 u = isForward ? ( f + du ) : ( l - du );
245 if (!isForward) Tg1.Reverse();
248 Standard_Real angle = Tg1.Angle(CTg1);
250 if (PI - Abs(angle) <= tolAng)
252 // an angle is too close to PI; assure that an angle sign really
253 // reflects an edge position: +PI - an edge is worst,
254 // -PI - an edge is best.
255 u = preciseU( Surf, CE, CV, Cc, Standard_False);
258 if (CE.Orientation() == TopAbs_REVERSED) CTg.Reverse();
260 u = preciseU( Surf, E, CV, C, Standard_True);
262 if (!isForward) Tg1.Reverse();
264 angle = Tg1.Angle(CTg);
267 Standard_Boolean isClose = ( Abs( angle - anglemin ) <= tolAng );
268 if (angle <= anglemin) {
281 if (!aPrevNE.IsNull()) {
282 // select one of close edges, the most left one.
283 Cc = BRep_Tool::CurveOnSurface( NE, FForward, f, l );
284 uc = preciseU( Surf, NE, CV, Cc, Standard_True);
285 Cc->D1(uc, PC, CTg1);
286 if (NE.Orientation() != TopAbs_FORWARD) CTg1.Reverse();
288 u = preciseU( Surf, aPrevNE, CV, C, Standard_True);
290 if (aPrevNE.Orientation() != TopAbs_FORWARD) Tg1.Reverse();
292 if ( Tg1.Angle(CTg1) < 0)
296 else if (LE.Extent() == 1) {
297 NE = TopoDS::Edge(LE.First());
300 return Standard_False;
305 //=======================================================================
306 //function : SamePnt2d
308 //=======================================================================
310 static Standard_Boolean SamePnt2d(const TopoDS_Vertex& V1,
311 const TopoDS_Edge& E1,
312 const TopoDS_Vertex& V2,
313 const TopoDS_Edge& E2,
314 const TopoDS_Face& F)
316 Standard_Real f1,f2,l1,l2;
317 Handle(Geom2d_Curve) C1 = BRep_Tool::CurveOnSurface(E1,F,f1,l1);
318 Handle(Geom2d_Curve) C2 = BRep_Tool::CurveOnSurface(E2,F,f2,l2);
320 gp_Pnt2d P1 = C1->Value( BRep_Tool::Parameter(V1,E1));
321 gp_Pnt2d P2 = C2->Value( BRep_Tool::Parameter(V2,E2));
323 Standard_Real Tol = 100 * BRep_Tool::Tolerance(V1);
324 Standard_Real Dist = P1.Distance(P2);
329 //=======================================================================
330 //function : StoreInMVE
332 //=======================================================================
334 static void StoreInMVE (const TopoDS_Face& /*F*/,
336 TopTools_DataMapOfShapeListOfShape& MVE )
339 TopoDS_Vertex V1, V2;
340 TopTools_ListOfShape Empty;
342 TopExp::Vertices(E,V1,V2);
343 if (!MVE.IsBound(V1)) {
348 if (!MVE.IsBound(V2)) {
354 //=======================================================================
355 //function : RemoveFromMVE
357 //=======================================================================
359 static void RemoveFromMVE(const TopoDS_Edge& E,
360 TopTools_DataMapOfShapeListOfShape& MVE)
362 TopTools_ListIteratorOfListOfShape itl;
364 TopExp::Vertices (E,V1,V2);
366 for ( itl.Initialize(MVE(V1)); itl.More(); itl.Next()) {
367 if (itl.Value().IsEqual(E)) {
373 for ( itl.Initialize(MVE(V2)); itl.More(); itl.Next()) {
374 if (itl.Value().IsEqual(E)) {
380 //=======================================================================
381 //function : addConnected
382 //purpose : add to <EM> all edges reachable from <E>
383 //=======================================================================
385 static void addConnected(const TopoDS_Shape& E,
386 TopTools_MapOfShape& EM,
387 TopTools_MapOfShape& VM,
388 const TopTools_DataMapOfShapeListOfShape& MVE)
390 // Loop on vertices of E
391 TopoDS_Iterator itV ( E );
392 for ( ; itV.More(); itV.Next()) {
394 if ( ! VM.Add ( itV.Value() )) continue;
396 // Loop on edges sharing V
397 TopTools_ListIteratorOfListOfShape itE( MVE( itV.Value() ) );
398 for (; itE.More(); itE.Next()) {
399 if ( EM.Add( itE.Value() ))
400 addConnected ( itE.Value(), EM, VM, MVE );
404 //=======================================================================
405 //function : canPassToOld
407 //=======================================================================
409 // static Standard_Boolean canPassToOld (const TopoDS_Shape& V,
410 // TopTools_MapOfShape& UsedShapesMap,
411 // const TopTools_DataMapOfShapeListOfShape& MVE,
412 // const TopTools_MapOfShape& SectionEdgesMap)
414 // TopTools_ListIteratorOfListOfShape itE( MVE(V) );
415 // // Loop on edges sharing V
416 // for (; itE.More(); itE.Next()) {
417 // if ( !UsedShapesMap.Add( itE.Value() ))
418 // continue; // already checked
420 // if ( !SectionEdgesMap.Contains( itE.Value() ))
421 // return Standard_True; // WE PASSED
423 // TopoDS_Iterator itV( itE.Value() );
424 // // Loop on vertices of an edge
425 // for (; itV.More(); itV.Next()) {
426 // if ( !UsedShapesMap.Add( itV.Value() ))
427 // continue; // already checked
429 // return canPassToOld( itV.Value(), UsedShapesMap, MVE, SectionEdgesMap);
432 // return Standard_False;
435 //=======================================================================
436 //function : MakeDegenAndSelect
437 //purpose : Find parameter of intersection of <CE> with <DE> and
438 // select an edge with its parameter closest to found one.
439 // Return new degenerated edge trimming <DE> by found parameters
440 //=======================================================================
442 static TopoDS_Edge MakeDegenAndSelect(const TopoDS_Edge& CE,
443 const TopoDS_Vertex& CV,
445 TopTools_SequenceOfShape& EdgesSeq,
446 TColStd_SequenceOfReal& USeq,
447 const TopoDS_Edge& DE)
449 if (EdgesSeq.Length() < 3) {
450 if (CE == EdgesSeq.First())
451 NE = TopoDS::Edge( EdgesSeq.Last() );
453 NE = TopoDS::Edge( EdgesSeq.First() );
457 // find parameter on DE where it intersects CE
460 Standard_Integer i, nb = EdgesSeq.Length();
461 for (i=1; i<= nb; ++i) {
462 if (CE == EdgesSeq(i)) {
468 // select NE with param closest to U1 thus finding U2 for a new degen edge
470 Standard_Real U2, dU, dUmin = 1.e100;
471 Standard_Boolean isReversed = ( DE.Orientation() == TopAbs_REVERSED );
472 for (i=1; i<= nb; ++i) {
474 if (isReversed ? (dU > 0) : (dU < 0))
477 if ( dU > dUmin || IsEqual( dU, 0.))
479 const TopoDS_Edge& E = TopoDS::Edge ( EdgesSeq(i) );
480 if ( ! CV.IsSame( TopExp::FirstVertex( E , Standard_True )))
483 dUmin = dU + Epsilon(dU);
487 // make a new degenerated edge
488 TopoDS_Edge NewDegen = TopoDS::Edge ( DE.EmptyCopied() );
490 Standard_Real Tol = BRep_Tool::Tolerance( CV );
491 TopoDS_Vertex V = CV;
494 V.Orientation( NewDegen.Orientation() );
495 B.UpdateVertex( V, U1, NewDegen, Tol);
496 B.Add ( NewDegen , V );
499 B.UpdateVertex( V, U2, NewDegen, Tol);
500 B.Add ( NewDegen , V );
505 //=======================================================================
506 //function : prepareDegen
507 //purpose : Intersect <DegEdge> with edges bound to its vertex in <MVE>
508 // and store intersection parameter on <DegEdge> in
509 // <USeq> as well as the edges them-self in <EdgesSeq>.
510 // Bind <DegEdgeIndex> to vertex of <DegEdge> in <MVDEI>
511 //=======================================================================
513 static void prepareDegen (const TopoDS_Edge& DegEdge,
514 const TopoDS_Face& F,
515 const TopTools_DataMapOfShapeListOfShape& MVE,
516 TopTools_SequenceOfShape& EdgesSeq,
517 TColStd_SequenceOfReal& USeq,
518 TopTools_DataMapOfShapeInteger& MVDEI,
519 const Standard_Integer DegEdgeIndex)
521 const TopoDS_Vertex& V = TopExp::FirstVertex ( DegEdge );
522 MVDEI.Bind ( V, DegEdgeIndex );
524 const TopTools_ListOfShape& EdgesList = MVE ( V );
525 // if only 2 edges come to degenerated one, no pb in selection and
526 // no need to intersect them, just simulate asked data
527 Standard_Boolean doIntersect = ( EdgesList.Extent() > 2 );
529 BRepAdaptor_Curve2d DC, C;
530 Geom2dInt_GInter InterCC;
531 Standard_Real Tol = Precision::PConfusion();
533 DC.Initialize( DegEdge, F );
535 // avoid intersecting twice the same edge
536 BRepOffset_DataMapOfShapeReal EUMap ( EdgesList.Extent() );
538 Standard_Real U, f, l;
539 BRep_Tool::Range (DegEdge, f, l);
541 TopTools_ListIteratorOfListOfShape itE (EdgesList);
542 for (; itE.More(); itE.Next()) {
544 const TopoDS_Edge& E = TopoDS::Edge ( itE.Value() );
547 U = 0.; // it won't be used
549 else if ( BRep_Tool::IsClosed( E, F )) {
550 // seam edge: select U among f and l
551 Standard_Boolean first = Standard_True;
552 if ( V.IsSame ( TopExp::FirstVertex( E, Standard_True ) ))
553 first = Standard_False;
554 if ( DegEdge.Orientation() == TopAbs_REVERSED )
558 else if ( EUMap.IsBound( E ) ) {
559 // same edge already bound
563 // intersect 2d curves
564 C.Initialize( E, F );
565 InterCC.Perform ( DC, C , Tol, Tol );
566 if (! InterCC.IsDone() || InterCC.NbPoints() == 0) {
567 MESSAGE ( "NO 2d INTERSECTION ON DEGENERATED EDGE" );
570 // hope there is only one point of intersection
571 U = InterCC.Point( 1 ).ParamOnFirst();
574 EdgesSeq.Append ( E );
577 //=======================================================================
579 //purpose : Make loops.
580 //=======================================================================
582 void Partition_Loop2d::Perform()
585 Standard_Integer NbConstEdges = myConstEdges.Extent();
586 TopTools_DataMapOfShapeListOfShape MVE(NbConstEdges) , MVE2(NbConstEdges);
587 TopTools_DataMapIteratorOfDataMapOfShapeListOfShape Mapit;
588 TopTools_ListIteratorOfListOfShape itl;
590 BRepAdaptor_Surface Surface ( myFace, Standard_False );
592 // degenerated edges and parameters of their 2d intersection with other edges
594 TopTools_SequenceOfShape SEID [2]; // seq of edges intersecting degenerated
595 TColStd_SequenceOfReal SeqU [2]; // n-th U corresponds to n-th edge in SEID
596 TopTools_DataMapOfShapeInteger MVDEI(2); // map vertex - degenerated edge index
597 Standard_Integer iDeg = 0; // index of degenerated edge [0,1]
599 //---------------------------------------------------------
600 // Construction map vertex => edges, find degenerated edges
601 //---------------------------------------------------------
602 for (itl.Initialize(myConstEdges); itl.More(); itl.Next()) {
603 TopoDS_Edge& E = TopoDS::Edge(itl.Value());
604 if ( BRep_Tool::Degenerated( E )) {
605 if (DE[0].IsNull()) DE[0] = E;
609 StoreInMVE(myFace,E,MVE);
612 // fill data for degenerated edges
613 if ( ! DE[0].IsNull() )
614 prepareDegen ( DE[0], myFace, MVE, SEID[0], SeqU[0], MVDEI, 0);
615 if ( ! DE[1].IsNull() )
616 prepareDegen ( DE[1], myFace, MVE, SEID[1], SeqU[1], MVDEI, 1);
619 // to detect internal wires
620 Standard_Boolean isInternCW = 0;
624 //------------------------------
625 // Construction of all the wires
626 //------------------------------
627 // first, we collect wire edges in WEL list looking for same edges that
628 // will be then removed possibly exploding a wire into parts;
629 // second, build wire(s)
631 while (!MVE.IsEmpty()) {
634 TopoDS_Edge CE,NE,EF;
637 Standard_Boolean End = Standard_False;
638 TopTools_ListOfShape WEL;
640 Mapit.Initialize(MVE);
641 if (Mapit.Value().IsEmpty()) {
642 MVE.UnBind(Mapit.Key());
647 EF = CE = TopoDS::Edge(Mapit.Value().First());
649 VF = TopExp::FirstVertex( CE, Standard_True);
651 isInternCW = Standard_True;
653 TopTools_MapOfShape addedEM (NbConstEdges); // map of edges added to WEL
654 TopTools_MapOfShape doubleEM (NbConstEdges); // edges encountered twice in WEL
656 //-------------------------------
657 // Construction of a wire.
658 //-------------------------------
661 // only a seam is allowed twice in a wire, the others should be removed
662 if (addedEM.Add ( CE ) || BRep_Tool::IsClosed( CE, myFace ) )
666 RemoveFromMVE (CE,MVE2);
667 TopoDS_Edge CERev = CE;
669 RemoveFromMVE (CERev,MVE2);
672 RemoveFromMVE (CE,MVE);
674 CV = TopExp::LastVertex( CE, Standard_True);
676 if (isInternCW && !mySectionEdges.Contains(CE))
677 // wire is internal if all edges are section ones
678 isInternCW = Standard_False;
680 if (MVDEI.IsBound( CV )) { // CE comes to the degeneration
682 TopoDS_Edge NewDegen;
683 NewDegen = MakeDegenAndSelect( CE, CV, NE, SEID[iDeg], SeqU[iDeg], DE[iDeg]);
684 WEL.Append( NewDegen );
686 End = CV.IsSame( VF );
693 if (MVE(CV).IsEmpty()) {
697 else if (CV.IsSame(VF) && SamePnt2d(CV,CE, VF,EF, myFace) ) {
701 //----------------------------
702 // select new current edge
703 //----------------------------
704 if (! SelectEdge (Surface,CE,CV,NE,MVE(CV))) {
705 MESSAGE ( " NOT CLOSED WIRE " );
714 // WEL is built, built wire(s)
717 itl.Initialize( WEL );
718 if ( doubleEM.IsEmpty()) { // no double edges
720 for (; itl.More(); itl.Next())
721 B.Add ( NW, itl.Value());
722 if (isInternCW) myInternalWL.Append(NW);
723 else myNewWires.Append (NW);
727 // remove double and degenerated edges from WEL
729 const TopoDS_Edge& E = TopoDS::Edge ( itl.Value() );
730 if ( doubleEM.Contains( E ) || BRep_Tool::Degenerated( E ))
737 // remove double edges from SEID and SeqU
738 Standard_Integer i,j;
739 for (j=0; j<2; ++j) {
740 for (i=1; i<=SEID[j].Length(); ++i) {
741 if (doubleEM.Contains( SEID[j].Value(i))) {
743 SeqU[j].Remove( i-- );
747 // removal of doulbe edges can explode a wire into parts,
748 // make new wires of them.
749 // A Loop like previous one but without 2d check
750 while ( !WEL.IsEmpty() ) {
751 CE = TopoDS::Edge( WEL.First() );
754 VF = TopExp::FirstVertex ( CE, Standard_True);
756 End = Standard_False;
759 CV = TopExp::LastVertex ( CE, Standard_True);
761 if (MVDEI.IsBound( CV )) { // CE comes to the degeneration
763 TopoDS_Edge NewDegen;
764 NewDegen = MakeDegenAndSelect( CE, CV, NE, SEID[iDeg], SeqU[iDeg], DE[iDeg]);
765 B.Add( NW, NewDegen );
766 End = CV.IsSame( VF );
768 if (!NE.IsNull()) { // remove NE from WEL
769 for (itl.Initialize( WEL ); itl.More(); itl.Next())
770 if ( NE == itl.Value()) {
775 } // end degeneration
778 if (CV.IsSame( VF )) {
782 // edges in WEL most often are well ordered
783 // so try to iterate until the End
784 Standard_Boolean add = Standard_False;
786 while ( itl.More() && !End) {
787 NE = TopoDS::Edge( itl.Value() );
788 if ( CV.IsSame( TopExp::FirstVertex( NE, Standard_True ))) {
794 CV = TopExp::LastVertex( CE, Standard_True);
795 if (MVDEI.IsBound( CV ) || CV.IsSame( VF ))
806 myInternalWL.Append( NW );
808 } // end building new wire(s) from WEL
812 // all wires are built
815 // ============================================================
816 // select really internal wires i.e. those from which we can`t
817 // pass to an old (not section) edge
818 // ============================================================
820 Standard_Integer nbIW = myInternalWL.Extent();
824 if ( myNewWires.Extent() != 1 && nbIW > 1) {
825 TopTools_MapOfShape outerEM (NbConstEdges); // edges connected to non-section ones
826 TopTools_MapOfShape visitedVM (NbConstEdges);
827 for ( itl.Initialize( myConstEdges ); itl.More(); itl.Next()) {
828 if ( ! mySectionEdges.Contains( itl.Value() ))
829 addConnected (itl.Value(), outerEM, visitedVM, MVE2);
831 // if an edge of a wire is in <outerEM>, the wire is not internal
832 TopExp_Explorer expIWE;
833 TopTools_ListIteratorOfListOfShape itIW ( myInternalWL );
834 while (itIW.More()) {
835 expIWE.Init ( itIW.Value() , TopAbs_EDGE );
836 if ( outerEM.Contains( expIWE.Current() )) {
837 myNewWires.Append ( itIW.Value() );
838 myInternalWL.Remove( itIW ); // == itIW.Next()
845 //=======================================================================
848 //=======================================================================
850 static Standard_Boolean isHole (const TopoDS_Wire& W,
851 const TopoDS_Face& F)
854 TopoDS_Shape newFace = F.EmptyCopied();
855 B.Add(newFace,W.Oriented(TopAbs_FORWARD));
856 BRepTopAdaptor_FClass2d classif (TopoDS::Face(newFace),
857 Precision::PConfusion());
858 return (classif.PerformInfinitePoint() == TopAbs_IN);
861 //=======================================================================
862 //function : IsInside
863 //purpose : check if W1 is inside W2. Suppose W2 is not a hole !!!!
864 //=======================================================================
866 static Standard_Boolean isInside(const TopoDS_Face& F,
867 const TopoDS_Wire& W1,
868 const TopoDS_Wire& W2)
870 // make a face with wire W2
872 TopoDS_Shape aLocalShape = F.EmptyCopied();
873 TopoDS_Face newFace = TopoDS::Face(aLocalShape);
876 // get any 2d point of W1
877 TopExp_Explorer exp(W1,TopAbs_EDGE);
878 if (BRep_Tool::Degenerated( TopoDS::Edge( exp.Current() )))
880 const TopoDS_Edge& e = TopoDS::Edge(exp.Current());
882 Handle(Geom2d_Curve) C2d = BRep_Tool::CurveOnSurface(e,F,f,l);
883 gp_Pnt2d pt2d(C2d->Value( 0.5 * ( f + l )));
885 BRepTopAdaptor_FClass2d classif(newFace,Precision::PConfusion());
886 return (classif.Perform(pt2d) == TopAbs_IN);
889 //=======================================================================
890 //function : NewWires
891 //purpose : Returns the list of wires performed.
892 // can be an empty list.
893 //=======================================================================
895 const TopTools_ListOfShape& Partition_Loop2d::NewWires() const
900 //=======================================================================
901 //function : NewFaces
902 //purpose : Returns the list of faces.
903 //Warning : The method <WiresToFaces> as to be called before.
904 // can be an empty list.
905 //=======================================================================
907 const TopTools_ListOfShape& Partition_Loop2d::NewFaces() const
912 //=======================================================================
913 //function : findEqual
914 //purpose : move wires form <WL> to <EqWL> pairs of wires build of the same edges
915 //=======================================================================
917 static void findEqual (TopTools_ListOfShape& WL,
918 TopTools_DataMapOfShapeShape& EqWM,
919 const TopoDS_Face& F)
921 TopTools_ListIteratorOfListOfShape it1, it2;
922 Standard_Integer i,j;
923 TColStd_MapOfInteger IndMap;
924 for (it1.Initialize(WL), i=1; it1.More(); it1.Next(), i++) {
926 if (IndMap.Contains(i)) continue;
927 const TopoDS_Wire& Wire1 = TopoDS::Wire( it1.Value());
929 for (it2.Initialize(WL), j=1; it2.More(); it2.Next(), j++) {
931 if (j <= i || IndMap.Contains(j)) continue;
933 TopTools_IndexedMapOfShape EdgesMap;
934 TopExp::MapShapes (Wire1, TopAbs_EDGE, EdgesMap);
936 const TopoDS_Shape& Wire2 = it2.Value();
937 TopoDS_Iterator itE ( Wire2);
938 for (; itE.More(); itE.Next()) {
939 if ( !EdgesMap.Contains( itE.Value()) )
942 if (!itE.More()) { // all edges are same
943 if (isHole( Wire1, F)) {
944 EqWM.Bind ( Wire1, Wire2 );
947 EqWM.Bind ( Wire2, Wire1 );
959 if (IndMap.Contains(i))
960 WL.Remove(it1); // next node becomes current and with Next() we would miss it
967 //=======================================================================
968 //function : classify
969 //purpose : bind to a wire a list of internal wires
970 //=======================================================================
972 static void classify(const TopTools_DataMapOfShapeShape& EqWM,
973 BRepAlgo_AsDes& OuterInner,
974 const TopoDS_Face& F)
976 TopTools_DataMapIteratorOfDataMapOfShapeShape it1, it2;
978 for (it1.Initialize(EqWM); it1.More(); it1.Next()) {
979 // find next after it1.Value()
980 for (it2.Initialize(EqWM); it2.More(); it2.Next())
981 if (it1.Value().IsSame( it2.Value() ))
986 for ( ; it2.More(); it2.Next()) {
987 const TopoDS_Wire& Wire1 = TopoDS::Wire( it1.Value() );
988 const TopoDS_Wire& Wire2 = TopoDS::Wire( it2.Value() );
989 if (isInside(F, Wire1, Wire2))
990 OuterInner.Add (Wire2, Wire1);
991 else if (isInside(F, Wire2, Wire1))
992 OuterInner.Add (Wire1, Wire2);
996 //=======================================================================
997 //function : WiresToFaces
998 //purpose : Build faces from the wires result.
999 // <EdgeImage> serves to find original edge by new
1000 // one. <Section> contains edges resulting from face
1002 //=======================================================================
1004 void Partition_Loop2d::WiresToFaces(const BRepAlgo_Image& )
1006 Standard_Integer nbW = myNewWires.Extent() + myInternalWL.Extent();
1010 BRepAlgo_FaceRestrictor FR;
1011 FR.Init (myFace,Standard_False);
1013 // FaceRestrictor is instable in rather simple cases
1014 // (ex. a single face of bellecoque.brep splited by 10 planes:
1015 // sometimes 1-2 faces are missing ).
1016 // So we use it as less as possible: no holes -> make faces by hands
1019 // are there holes in myFace ?
1020 Standard_Boolean hasOldHoles = Standard_False;
1021 TopoDS_Iterator itOldW (myFace);
1022 if ( itOldW.More()) {
1023 const TopoDS_Wire& FirstOldWire = TopoDS::Wire( itOldW.Value() );
1025 hasOldHoles = itOldW.More() || isHole( FirstOldWire, myFace);
1027 if (myInternalWL.IsEmpty() && !hasOldHoles) {
1028 // each wire bounds one face
1030 TopTools_ListIteratorOfListOfShape itNW (myNewWires);
1031 for (; itNW.More(); itNW.Next()) {
1032 TopoDS_Face NF = TopoDS::Face ( myFace.EmptyCopied() );
1033 B.Add ( NF, itNW.Value() );
1034 NF.Orientation( myFaceOri);
1035 myNewFaces.Append ( NF );
1040 // FaceRestrictor can't classify wires build on all the same edges
1041 // and gives incorrect result in such cases (ex. a plane cut into 2 parts by cylinder)
1042 // We must make faces of equal wires separately. One of equal wires makes a
1043 // hole in a face and should come together with outer wires of face.
1044 // The other of a wires pair bounds a face that may have holes in turn.
1046 // Find equal wires among internal wires
1047 TopTools_DataMapOfShapeShape EqWM; // key is a hole part of a pair of equal wires
1048 findEqual (myInternalWL, EqWM, myFace);
1050 if (!EqWM.IsEmpty()) { // there are equal wires
1053 myInternalWL.Append( myNewWires ); // an old wire can be inside an equal wire
1055 // classify equal wire pairs
1056 BRepAlgo_AsDes OuterInner;
1057 classify (EqWM,OuterInner,myFace);
1059 // make face of most internal of equal wires and its inner wires
1060 while ( !EqWM.IsEmpty()) {
1062 TopTools_ListOfShape prevHolesL; // list of hole-part of previous most internal equal wires
1064 // find most internal wires among pairs (key - hole, value - outer part)
1065 TopTools_DataMapIteratorOfDataMapOfShapeShape it(EqWM);
1066 Standard_Integer nbEqW = EqWM.Extent(); // protection against infinite loop
1067 for ( ; it.More(); it.Next()) {
1069 TopoDS_Wire outerW = TopoDS::Wire ( it.Value() );
1070 if ( OuterInner.HasDescendant( outerW ) && // has internal
1071 ! OuterInner.Descendant( outerW ).IsEmpty() )
1076 // add internal wires that are inside of outerW
1077 TopTools_ListIteratorOfListOfShape itIW (myInternalWL);
1078 while ( itIW.More()) {
1079 TopoDS_Wire IW = TopoDS::Wire ( itIW.Value() );
1080 if ( isInside (myFace, IW, outerW)) {
1082 myInternalWL.Remove( itIW ); // == itIW.Next() !!!
1088 // the hole-part of current pair of equal wires will be in the next new face
1089 prevHolesL.Append ( it.Key() );
1091 } // Loop on map of equal pairs searching for innermost wires
1096 for (; FR.More(); FR.Next())
1097 myNewFaces.Append(FR.Current());
1102 // add hole-parts to FaceRestrictor,
1103 // remove them from the EqWM,
1104 // remove found wires as internal of resting classified wires
1105 Standard_Boolean clearOuterInner = ( prevHolesL.Extent() < EqWM.Extent() );
1106 TopTools_ListIteratorOfListOfShape itPrev (prevHolesL);
1107 for (; itPrev.More(); itPrev.Next()) {
1108 TopoDS_Wire& Hole = TopoDS::Wire ( itPrev.Value() );
1110 if (clearOuterInner) {
1111 const TopoDS_Wire& outerW = TopoDS::Wire ( EqWM.Find( Hole ) );
1112 // Loop on wires including outerW
1113 TopTools_ListIteratorOfListOfShape itO( OuterInner.Ascendant( outerW ));
1114 for (; itO.More(); itO.Next()) {
1115 TopTools_ListOfShape& innerL = OuterInner.ChangeDescendant( itO.Value() );
1116 TopTools_ListIteratorOfListOfShape itI (innerL);
1117 // Loop on internal wires of current including wire
1118 for (; itI.More(); itI.Next())
1119 if ( outerW.IsSame( itI.Value() )) {
1120 innerL.Remove( itI ); break;
1124 EqWM.UnBind ( Hole );
1127 if (nbEqW == EqWM.Extent())
1129 // error: pb with wires classification
1131 MESSAGE("Partition_Loop2d::WiresToFaces(), pb with wires classification");
1136 } // while (!EqWM.IsEmpty)
1138 } // if !EqWM.IsEmpty()
1140 myNewWires.Append ( myInternalWL );
1142 TopTools_ListIteratorOfListOfShape itW (myNewWires);
1143 for (; itW.More(); itW.Next()) {
1144 TopoDS_Wire& W = TopoDS::Wire ( itW.Value() );
1148 for (; FR.IsDone() && FR.More(); FR.Next())
1149 myNewFaces.Append(FR.Current());
1152 TopTools_ListIteratorOfListOfShape itNF (myNewFaces);
1153 for (; itNF.More(); itNF.Next())
1154 itNF.Value().Orientation( myFaceOri );