1 // Created by: Peter KURNEV
2 // Copyright (c) 2010-2012 OPEN CASCADE SAS
3 // Copyright (c) 2007-2010 CEA/DEN, EDF R&D, OPEN CASCADE
4 // Copyright (c) 2003-2007 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN, CEDRAT,
5 // EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
8 // This file is part of Open CASCADE Technology software library.
10 // This library is free software; you can redistribute it and/or modify it under
11 // the terms of the GNU Lesser General Public License version 2.1 as published
12 // by the Free Software Foundation, with special exception defined in the file
13 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
14 // distribution for complete text of the license and disclaimer of any warranty.
16 // Alternatively, this file may be used under the terms of Open CASCADE
17 // commercial license or contractual agreement.
19 #include <BOPAlgo_BuilderFace.ixx>
21 #include <NCollection_UBTreeFiller.hxx>
22 #include <NCollection_DataMap.hxx>
24 #include <TColStd_MapIntegerHasher.hxx>
26 #include <gp_Pnt2d.hxx>
32 #include <Geom_Surface.hxx>
35 #include <TopLoc_Location.hxx>
37 #include <TopoDS_Iterator.hxx>
38 #include <TopoDS_Face.hxx>
39 #include <TopoDS_Shape.hxx>
40 #include <TopoDS_Wire.hxx>
41 #include <TopoDS_Edge.hxx>
42 #include <TopoDS_Vertex.hxx>
44 #include <BRep_Builder.hxx>
45 #include <BRep_Tool.hxx>
46 #include <BRepTools.hxx>
49 #include <TopExp_Explorer.hxx>
51 #include <IntTools_FClass2d.hxx>
52 #include <IntTools_Context.hxx>
54 #include <BOPTools_AlgoTools.hxx>
55 #include <BOPTools_AlgoTools2D.hxx>
56 #include <BOPAlgo_WireEdgeSet.hxx>
58 #include <BOPCol_IndexedDataMapOfShapeListOfShape.hxx>
59 #include <BOPTools.hxx>
60 #include <BOPCol_ListOfShape.hxx>
62 #include <BOPCol_DataMapOfShapeShape.hxx>
63 #include <BOPCol_DataMapOfShapeListOfShape.hxx>
64 #include <BOPCol_MapOfShape.hxx>
65 #include <BOPCol_Box2DBndTree.hxx>
67 #include <BOPAlgo_WireSplitter.hxx>
70 Standard_Boolean IsGrowthWire(const TopoDS_Shape& ,
71 const BOPCol_IndexedMapOfShape& );
74 Standard_Boolean IsInside(const TopoDS_Shape& ,
76 Handle(IntTools_Context)& );
78 void MakeInternalWires(const BOPCol_MapOfShape& ,
79 BOPCol_ListOfShape& );
81 void GetWire(const TopoDS_Shape& ,
86 //=======================================================================
87 //class : BOPAlgo_ShapeBox2D
88 //purpose : Auxiliary class
89 //=======================================================================
90 class BOPAlgo_ShapeBox2D {
92 BOPAlgo_ShapeBox2D() {
93 myIsHole=Standard_False;
96 ~BOPAlgo_ShapeBox2D() {
99 void SetShape(const TopoDS_Shape& aS) {
103 const TopoDS_Shape& Shape()const {
107 void SetBox2D(const Bnd_Box2d& aBox2D) {
111 const Bnd_Box2d& Box2D()const {
115 void SetIsHole(const Standard_Boolean bFlag) {
119 Standard_Boolean IsHole()const {
124 Standard_Boolean myIsHole;
125 TopoDS_Shape myShape;
129 typedef NCollection_DataMap\
130 <Standard_Integer, BOPAlgo_ShapeBox2D, TColStd_MapIntegerHasher> \
131 BOPAlgo_DataMapOfIntegerShapeBox2D;
133 typedef BOPAlgo_DataMapOfIntegerShapeBox2D::Iterator \
134 BOPAlgo_DataMapIteratorOfDataMapOfIntegerShapeBox2D;
137 //=======================================================================
140 //=======================================================================
141 BOPAlgo_BuilderFace::BOPAlgo_BuilderFace()
143 BOPAlgo_BuilderArea()
145 myOrientation=TopAbs_EXTERNAL;
147 //=======================================================================
150 //=======================================================================
151 BOPAlgo_BuilderFace::BOPAlgo_BuilderFace
152 (const Handle(NCollection_BaseAllocator)& theAllocator)
154 BOPAlgo_BuilderArea(theAllocator)
156 myOrientation=TopAbs_EXTERNAL;
158 //=======================================================================
161 //=======================================================================
162 BOPAlgo_BuilderFace::~BOPAlgo_BuilderFace()
165 //=======================================================================
168 //=======================================================================
169 void BOPAlgo_BuilderFace::SetFace(const TopoDS_Face& theFace)
171 myOrientation=theFace.Orientation();
173 myFace.Orientation(TopAbs_FORWARD);
175 //=======================================================================
176 //function : Orientation
178 //=======================================================================
179 TopAbs_Orientation BOPAlgo_BuilderFace::Orientation()const
181 return myOrientation;
183 //=======================================================================
186 //=======================================================================
187 const TopoDS_Face& BOPAlgo_BuilderFace::Face()const
191 //=======================================================================
192 //function : CheckData
194 //=======================================================================
195 void BOPAlgo_BuilderFace::CheckData()
199 if (myFace.IsNull()) {
200 myErrorStatus=12;// Null face generix
203 if (myContext.IsNull()) {
204 myContext = new IntTools_Context;
207 //=======================================================================
210 //=======================================================================
211 void BOPAlgo_BuilderFace::Perform()
222 PerformShapesToAvoid();
243 PerformInternalShapes();
248 //=======================================================================
249 //function :PerformShapesToAvoid
251 //=======================================================================
252 void BOPAlgo_BuilderFace::PerformShapesToAvoid()
254 Standard_Boolean bFound;
255 Standard_Integer i, iCnt, aNbV, aNbE;
256 BOPCol_IndexedDataMapOfShapeListOfShape aMVE;
257 BOPCol_ListIteratorOfListOfShape aIt;
259 myShapesToAvoid.Clear();
264 bFound=Standard_False;
268 aIt.Initialize (myShapes);
269 for (; aIt.More(); aIt.Next()) {
270 const TopoDS_Shape& aE=aIt.Value();
271 if (!myShapesToAvoid.Contains(aE)) {
272 BOPTools::MapShapesAndAncestors(aE, TopAbs_VERTEX, TopAbs_EDGE, aMVE);
278 for (i=1; i<=aNbV; ++i) {
279 const TopoDS_Vertex& aV=(*(TopoDS_Vertex *)(&aMVE.FindKey(i)));
281 BOPCol_ListOfShape& aLE=aMVE.ChangeFromKey(aV);
287 const TopoDS_Edge& aE1=(*(TopoDS_Edge *)(&aLE.First()));
289 if (BRep_Tool::Degenerated(aE1)) {
292 if (aV.Orientation()==TopAbs_INTERNAL) {
295 bFound=Standard_True;
296 myShapesToAvoid.Add(aE1);
299 const TopoDS_Edge& aE2=(*(TopoDS_Edge *)(&aLE.Last()));
300 if (aE2.IsSame(aE1)) {
301 TopoDS_Vertex aV1x, aV2x;
303 TopExp::Vertices(aE1, aV1x, aV2x);
304 if (aV1x.IsSame(aV2x)) {
307 bFound=Standard_True;
308 myShapesToAvoid.Add(aE1);
309 myShapesToAvoid.Add(aE2);
312 }// for (i=1; i<=aNbE; ++i) {
319 //printf(" EdgesToAvoid=%d, iCnt=%d\n", EdgesToAvoid.Extent(), iCnt);
321 //=======================================================================
322 //function : PerformLoops
324 //=======================================================================
325 void BOPAlgo_BuilderFace::PerformLoops()
329 Standard_Boolean bFlag;
330 Standard_Integer iErr, aNbEA;
331 BOPCol_ListIteratorOfListOfShape aIt;
332 BOPCol_MapIteratorOfMapOfOrientedShape aItM;
333 BOPCol_IndexedDataMapOfShapeListOfShape aVEMap;
334 BOPCol_MapOfOrientedShape aMAdded;
335 TopoDS_Iterator aItW;
337 BOPAlgo_WireEdgeSet aWES(myAllocator);
338 BOPAlgo_WireSplitter aWSp(myAllocator);
342 aWES.SetFace(myFace);
344 aIt.Initialize(myShapes);
345 for (; aIt.More(); aIt.Next()) {
346 const TopoDS_Shape& aE=aIt.Value();
347 if (!myShapesToAvoid.Contains(aE)) {
348 aWES.AddStartElement(aE);
353 aWSp.SetRunParallel(myRunParallel);
355 iErr=aWSp.ErrorStatus();
360 const BOPCol_ListOfShape& aLW=aWES.Shapes();
361 aIt.Initialize (aLW);
362 for (; aIt.More(); aIt.Next()) {
363 const TopoDS_Shape& aW=aIt.Value();
367 BOPCol_MapOfOrientedShape aMEP;
369 // a. collect all edges that are in loops
370 aIt.Initialize (myLoops);
371 for (; aIt.More(); aIt.Next()) {
372 const TopoDS_Shape& aW=aIt.Value();
374 for (; aItW.More(); aItW.Next()) {
375 const TopoDS_Shape& aE=aItW.Value();
380 // b. collect all edges that are to avoid
381 aItM.Initialize(myShapesToAvoid);
382 for (; aItM.More(); aItM.Next()) {
383 const TopoDS_Shape& aE=aItM.Key();
387 // c. add all edges that are not processed to myShapesToAvoid
388 aIt.Initialize (myShapes);
389 for (; aIt.More(); aIt.Next()) {
390 const TopoDS_Shape& aE=aIt.Value();
391 if (!aMEP.Contains(aE)) {
392 myShapesToAvoid.Add(aE);
397 myLoopsInternal.Clear();
399 aNbEA=myShapesToAvoid.Extent();
400 aItM.Initialize(myShapesToAvoid);
401 for (; aItM.More(); aItM.Next()) {
402 const TopoDS_Shape& aEE=aItM.Key();
403 BOPTools::MapShapesAndAncestors(aEE,
410 aItM.Initialize(myShapesToAvoid);
411 for (; aItM.More()&&bFlag; aItM.Next()) {
412 const TopoDS_Shape& aEE=aItM.Key();
413 if (!aMAdded.Add(aEE)) {
423 for (; aItW.More()&&bFlag; aItW.Next()) {
424 const TopoDS_Edge& aE=(*(TopoDS_Edge *)(&aItW.Value()));
426 TopoDS_Iterator aItE(aE);
427 for (; aItE.More()&&bFlag; aItE.Next()) {
428 const TopoDS_Vertex& aV = (*(TopoDS_Vertex *)(&aItE.Value()));
429 const BOPCol_ListOfShape& aLE=aVEMap.FindFromKey(aV);
431 for (; aIt.More()&&bFlag; aIt.Next()) {
432 const TopoDS_Shape& aEx=aIt.Value();
433 if (aMAdded.Add(aEx)) {
435 if(aMAdded.Extent()==aNbEA) {
439 }//for (; aIt.More(); aIt.Next()) {
440 }//for (; aItE.More(); aItE.Next()) {
441 }//for (; aItW.More(); aItW.Next()) {
442 myLoopsInternal.Append(aW);
443 }//for (; aItM.More(); aItM.Next()) {
447 //=======================================================================
448 //function : PerformAreas
450 //=======================================================================
451 void BOPAlgo_BuilderFace::PerformAreas()
453 Standard_Boolean bIsGrowth, bIsHole;
454 Standard_Integer k,aNbHoles;
456 TopLoc_Location aLoc;
457 Handle(Geom_Surface) aS;
461 BOPCol_ListIteratorOfListOfInteger aItLI;
462 BOPCol_IndexedMapOfShape aMHE;
463 BOPCol_DataMapOfShapeShape aInOutMap;
464 BOPCol_DataMapIteratorOfDataMapOfShapeShape aItDMSS;
465 BOPCol_DataMapOfShapeListOfShape aMSH;
466 BOPCol_DataMapIteratorOfDataMapOfShapeListOfShape aItMSH;
467 BOPCol_ListIteratorOfListOfShape aIt1;
468 BOPAlgo_DataMapOfIntegerShapeBox2D aDMISB(100);
469 BOPAlgo_DataMapIteratorOfDataMapOfIntegerShapeBox2D aItDMISB;
471 BOPCol_Box2DBndTreeSelector aSelector;
472 BOPCol_Box2DBndTree aBBTree;
473 NCollection_UBTreeFiller <Standard_Integer, Bnd_Box2d> aTreeFiller(aBBTree);
477 aTol=BRep_Tool::Tolerance(myFace);
478 aS=BRep_Tool::Surface(myFace, aLoc);
482 // 1. Growthes and Holes -> aDMISB: [Index/ShapeBox2D]
483 aIt1.Initialize(myLoops);
484 for (k=0 ; aIt1.More(); aIt1.Next(), ++k) {
487 const TopoDS_Shape& aWire=aIt1.Value();
489 aBB.MakeFace(aFace, aS, aLoc, aTol);
490 aBB.Add (aFace, aWire);
491 BRepTools::AddUVBounds(aFace, aBox2D);
493 bIsGrowth=IsGrowthWire(aWire, aMHE);
495 bIsHole=Standard_False;
498 // check if a wire is a hole
499 IntTools_FClass2d& aClsf=myContext->FClass2d(aFace);
500 aClsf.Init(aFace, aTol);
502 bIsHole=aClsf.IsHole();
504 BOPTools::MapShapes(aWire, TopAbs_EDGE, aMHE);
506 bIsHole=Standard_True;
509 bIsHole=Standard_False;
513 BOPAlgo_ShapeBox2D aSB2D;
515 aSB2D.SetShape(aFace);
516 aSB2D.SetBox2D(aBox2D);
517 aSB2D.SetIsHole(bIsHole);
519 aDMISB.Bind(k, aSB2D);
522 // 2. Prepare TreeFiller
523 aItDMISB.Initialize(aDMISB);
524 for (; aItDMISB.More(); aItDMISB.Next()) {
526 const BOPAlgo_ShapeBox2D& aSB2D=aItDMISB.Value();
528 bIsHole=aSB2D.IsHole();
530 const Bnd_Box2d& aBox2D=aSB2D.Box2D();
531 aTreeFiller.Add(k, aBox2D);
535 // 3. Shake TreeFiller
538 // 4. Find outer growth shell that is most close
539 // to each hole shell
540 aItDMISB.Initialize(aDMISB);
541 for (; aItDMISB.More(); aItDMISB.Next()) {
543 const BOPAlgo_ShapeBox2D& aSB2D=aItDMISB.Value();
544 bIsHole=aSB2D.IsHole();
549 const Bnd_Box2d& aBox2DF=aSB2D.Box2D();
550 const TopoDS_Shape aF=aSB2D.Shape();
553 aSelector.SetBox(aBox2DF);
555 aNbHoles=aBBTree.Select(aSelector);
557 const BOPCol_ListOfInteger& aLI=aSelector.Indices();
559 aItLI.Initialize(aLI);
560 for (; aItLI.More(); aItLI.Next()) {
562 const BOPAlgo_ShapeBox2D& aSB2Dk=aDMISB.Find(k);
563 const TopoDS_Shape& aHole=aSB2Dk.Shape();
565 if (!IsInside(aHole, aF, myContext)){
569 if (aInOutMap.IsBound (aHole)){
570 const TopoDS_Shape& aF2=aInOutMap(aHole);
571 if (IsInside(aF, aF2, myContext)) {
572 aInOutMap.UnBind(aHole);
573 aInOutMap.Bind (aHole, aF);
577 aInOutMap.Bind(aHole, aF);
582 // 5. Map [Face/Holes] -> aMSH
583 aItDMSS.Initialize(aInOutMap);
584 for (; aItDMSS.More(); aItDMSS.Next()) {
585 const TopoDS_Shape& aHole=aItDMSS.Key();
586 const TopoDS_Shape& aF=aItDMSS.Value();
588 if (aMSH.IsBound(aF)) {
589 BOPCol_ListOfShape& aLH=aMSH.ChangeFind(aF);
593 BOPCol_ListOfShape aLH;
599 // 6. Add aHoles to Faces,
600 aItMSH.Initialize(aMSH);
601 for (; aItMSH.More(); aItMSH.Next()) {
602 TopoDS_Face aF=(*(TopoDS_Face *)(&aItMSH.Key()));
604 const BOPCol_ListOfShape& aLH=aItMSH.Value();
605 aIt1.Initialize(aLH);
606 for (; aIt1.More(); aIt1.Next()) {
609 const TopoDS_Shape& aFHole=aIt1.Value();
610 GetWire(aFHole, aWHole);
611 aBB.Add (aF, aWHole);
615 aTol=BRep_Tool::Tolerance(aF);
616 IntTools_FClass2d& aClsf=myContext->FClass2d(aF);
617 aClsf.Init(aF, aTol);
621 // NB:These aNewFaces are draft faces that
622 // do not contain any internal shapes
623 aItDMISB.Initialize(aDMISB);
624 for (; aItDMISB.More(); aItDMISB.Next()) {
625 const BOPAlgo_ShapeBox2D& aSB2D=aItDMISB.Value();
626 bIsHole=aSB2D.IsHole();
628 const TopoDS_Shape aF=aSB2D.Shape();
633 //=======================================================================
636 //=======================================================================
637 void GetWire(const TopoDS_Shape& aF, TopoDS_Shape& aW)
643 for (; aIt.More(); aIt.Next()) {
647 //=======================================================================
648 //function : PerformInternalShapes
650 //=======================================================================
651 void BOPAlgo_BuilderFace::PerformInternalShapes()
655 Standard_Integer aNbWI=myLoopsInternal.Extent();
656 if (!aNbWI) {// nothing to do
660 //Standard_Real aTol;
662 BOPCol_ListIteratorOfListOfShape aIt1, aIt2;
664 BOPCol_MapOfShape aME, aMEP;
665 BOPCol_MapIteratorOfMapOfShape aItME;
666 BOPCol_IndexedDataMapOfShapeListOfShape aMVE;
667 BOPCol_ListOfShape aLSI;
669 // 1. All internal edges
670 aIt1.Initialize(myLoopsInternal);
671 for (; aIt1.More(); aIt1.Next()) {
672 const TopoDS_Shape& aWire=aIt1.Value();
673 aIt.Initialize(aWire);
674 for (; aIt.More(); aIt.Next()) {
675 const TopoDS_Shape& aE=aIt.Value();
682 aIt2.Initialize(myAreas);
683 for ( ; aIt2.More(); aIt2.Next()) {
684 TopoDS_Face& aF=(*(TopoDS_Face *)(&aIt2.Value()));
687 BOPTools::MapShapesAndAncestors(aF, TopAbs_VERTEX, TopAbs_EDGE, aMVE);
689 // 2.1 Separate faces to process aMEP
691 aItME.Initialize(aME);
692 for (; aItME.More(); aItME.Next()) {
693 const TopoDS_Edge& aE=(*(TopoDS_Edge *)(&aItME.Key()));
694 if (IsInside(aE, aF, myContext)) {
699 // 2.2 Make Internal Wires
701 MakeInternalWires(aMEP, aLSI);
703 // 2.3 Add them to aF
704 aIt1.Initialize(aLSI);
705 for (; aIt1.More(); aIt1.Next()) {
706 const TopoDS_Shape& aSI=aIt1.Value();
710 // 2.4 Remove faces aMFP from aMF
711 aItME.Initialize(aMEP);
712 for (; aItME.More(); aItME.Next()) {
713 const TopoDS_Shape& aE=aItME.Key();
721 } //for ( ; aIt2.More(); aIt2.Next()) {
723 //=======================================================================
724 //function : MakeInternalWires
726 //=======================================================================
727 void MakeInternalWires(const BOPCol_MapOfShape& theME,
728 BOPCol_ListOfShape& theWires)
730 BOPCol_MapIteratorOfMapOfShape aItM;
731 BOPCol_MapOfShape aAddedMap;
732 BOPCol_ListIteratorOfListOfShape aItE;
733 BOPCol_IndexedDataMapOfShapeListOfShape aMVE;
736 aItM.Initialize(theME);
737 for (; aItM.More(); aItM.Next()) {
738 const TopoDS_Shape& aE=aItM.Key();
739 BOPTools::MapShapesAndAncestors(aE, TopAbs_VERTEX, TopAbs_EDGE, aMVE);
742 aItM.Initialize(theME);
743 for (; aItM.More(); aItM.Next()) {
744 TopoDS_Shape aEE=aItM.Key();
745 if (!aAddedMap.Add(aEE)) {
752 aEE.Orientation(TopAbs_INTERNAL);
755 TopoDS_Iterator aItAdded (aW);
756 for (; aItAdded.More(); aItAdded.Next()) {
757 const TopoDS_Shape& aE =aItAdded.Value();
759 TopExp_Explorer aExp(aE, TopAbs_VERTEX);
760 for (; aExp.More(); aExp.Next()) {
761 const TopoDS_Shape& aV =aExp.Current();
762 const BOPCol_ListOfShape& aLE=aMVE.FindFromKey(aV);
763 aItE.Initialize(aLE);
764 for (; aItE.More(); aItE.Next()) {
765 TopoDS_Shape aEL=aItE.Value();
766 if (aAddedMap.Add(aEL)){
767 aEL.Orientation(TopAbs_INTERNAL);
776 //=======================================================================
777 //function : IsInside
779 //=======================================================================
780 Standard_Boolean IsInside(const TopoDS_Shape& theHole,
781 const TopoDS_Shape& theF2,
782 Handle(IntTools_Context)& theContext)
784 Standard_Boolean bRet;
785 Standard_Real aT, aU, aV;
788 TopExp_Explorer aExp;
789 BOPCol_IndexedMapOfShape aME2;
793 aState=TopAbs_UNKNOWN;
794 const TopoDS_Face& aF2=(*(TopoDS_Face *)(&theF2));
796 BOPTools::MapShapes(aF2, TopAbs_EDGE, aME2);//AA
798 aExp.Init(theHole, TopAbs_EDGE);
800 const TopoDS_Edge& aE =(*(TopoDS_Edge *)(&aExp.Current()));
801 if (aME2.Contains(aE)) {
804 if (!BRep_Tool::Degenerated(aE)) {
806 aT=BOPTools_AlgoTools2D::IntermediatePoint(aE);
807 BOPTools_AlgoTools2D::PointOnSurface(aE, aF2, aT, aU, aV);
808 aP2D.SetCoord(aU, aV);
810 IntTools_FClass2d& aClsf=theContext->FClass2d(aF2);
811 aState=aClsf.Perform(aP2D);
812 bRet=(aState==TopAbs_IN);
819 //=======================================================================
820 //function : IsGrowthWire
822 //=======================================================================
823 Standard_Boolean IsGrowthWire(const TopoDS_Shape& theWire,
824 const BOPCol_IndexedMapOfShape& theMHE)
826 Standard_Boolean bRet;
830 if (theMHE.Extent()) {
831 aIt.Initialize(theWire);
832 for(; aIt.More(); aIt.Next()) {
833 const TopoDS_Shape& aE=aIt.Value();
834 if (theMHE.Contains(aE)) {
842 //BRepTools::Write(aFF, "ff");
846 // 12 - Null face generix