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_IndexedDataMap
132 TColStd_MapIntegerHasher> BOPAlgo_IndexedDataMapOfIntegerShapeBox2D;
134 typedef NCollection_IndexedDataMap
137 TopTools_ShapeMapHasher> BOPCol_IndexedDataMapOfShapeShape;
139 //=======================================================================
142 //=======================================================================
143 BOPAlgo_BuilderFace::BOPAlgo_BuilderFace()
145 BOPAlgo_BuilderArea()
147 myOrientation=TopAbs_EXTERNAL;
149 //=======================================================================
152 //=======================================================================
153 BOPAlgo_BuilderFace::BOPAlgo_BuilderFace
154 (const Handle(NCollection_BaseAllocator)& theAllocator)
156 BOPAlgo_BuilderArea(theAllocator)
158 myOrientation=TopAbs_EXTERNAL;
160 //=======================================================================
163 //=======================================================================
164 BOPAlgo_BuilderFace::~BOPAlgo_BuilderFace()
167 //=======================================================================
170 //=======================================================================
171 void BOPAlgo_BuilderFace::SetFace(const TopoDS_Face& theFace)
173 myOrientation=theFace.Orientation();
175 myFace.Orientation(TopAbs_FORWARD);
177 //=======================================================================
178 //function : Orientation
180 //=======================================================================
181 TopAbs_Orientation BOPAlgo_BuilderFace::Orientation()const
183 return myOrientation;
185 //=======================================================================
188 //=======================================================================
189 const TopoDS_Face& BOPAlgo_BuilderFace::Face()const
193 //=======================================================================
194 //function : CheckData
196 //=======================================================================
197 void BOPAlgo_BuilderFace::CheckData()
201 if (myFace.IsNull()) {
202 myErrorStatus=12;// Null face generix
205 if (myContext.IsNull()) {
206 myContext = new IntTools_Context;
209 //=======================================================================
212 //=======================================================================
213 void BOPAlgo_BuilderFace::Perform()
224 PerformShapesToAvoid();
245 PerformInternalShapes();
250 //=======================================================================
251 //function :PerformShapesToAvoid
253 //=======================================================================
254 void BOPAlgo_BuilderFace::PerformShapesToAvoid()
256 Standard_Boolean bFound;
257 Standard_Integer i, iCnt, aNbV, aNbE;
258 BOPCol_IndexedDataMapOfShapeListOfShape aMVE;
259 BOPCol_ListIteratorOfListOfShape aIt;
261 myShapesToAvoid.Clear();
266 bFound=Standard_False;
270 aIt.Initialize (myShapes);
271 for (; aIt.More(); aIt.Next()) {
272 const TopoDS_Shape& aE=aIt.Value();
273 if (!myShapesToAvoid.Contains(aE)) {
274 BOPTools::MapShapesAndAncestors(aE, TopAbs_VERTEX, TopAbs_EDGE, aMVE);
280 for (i=1; i<=aNbV; ++i) {
281 const TopoDS_Vertex& aV=(*(TopoDS_Vertex *)(&aMVE.FindKey(i)));
283 BOPCol_ListOfShape& aLE=aMVE.ChangeFromKey(aV);
289 const TopoDS_Edge& aE1=(*(TopoDS_Edge *)(&aLE.First()));
291 if (BRep_Tool::Degenerated(aE1)) {
294 if (aV.Orientation()==TopAbs_INTERNAL) {
297 bFound=Standard_True;
298 myShapesToAvoid.Add(aE1);
301 const TopoDS_Edge& aE2=(*(TopoDS_Edge *)(&aLE.Last()));
302 if (aE2.IsSame(aE1)) {
303 TopoDS_Vertex aV1x, aV2x;
305 TopExp::Vertices(aE1, aV1x, aV2x);
306 if (aV1x.IsSame(aV2x)) {
309 bFound=Standard_True;
310 myShapesToAvoid.Add(aE1);
311 myShapesToAvoid.Add(aE2);
314 }// for (i=1; i<=aNbE; ++i) {
321 //printf(" EdgesToAvoid=%d, iCnt=%d\n", EdgesToAvoid.Extent(), iCnt);
323 //=======================================================================
324 //function : PerformLoops
326 //=======================================================================
327 void BOPAlgo_BuilderFace::PerformLoops()
331 Standard_Boolean bFlag;
332 Standard_Integer iErr, aNbEA;
333 BOPCol_ListIteratorOfListOfShape aIt;
334 BOPCol_MapIteratorOfMapOfOrientedShape aItM;
335 BOPCol_IndexedDataMapOfShapeListOfShape aVEMap;
336 BOPCol_MapOfOrientedShape aMAdded;
337 TopoDS_Iterator aItW;
339 BOPAlgo_WireEdgeSet aWES(myAllocator);
340 BOPAlgo_WireSplitter aWSp(myAllocator);
344 aWES.SetFace(myFace);
346 aIt.Initialize(myShapes);
347 for (; aIt.More(); aIt.Next()) {
348 const TopoDS_Shape& aE=aIt.Value();
349 if (!myShapesToAvoid.Contains(aE)) {
350 aWES.AddStartElement(aE);
355 aWSp.SetRunParallel(myRunParallel);
357 iErr=aWSp.ErrorStatus();
362 const BOPCol_ListOfShape& aLW=aWES.Shapes();
363 aIt.Initialize (aLW);
364 for (; aIt.More(); aIt.Next()) {
365 const TopoDS_Shape& aW=aIt.Value();
369 BOPCol_MapOfOrientedShape aMEP;
371 // a. collect all edges that are in loops
372 aIt.Initialize (myLoops);
373 for (; aIt.More(); aIt.Next()) {
374 const TopoDS_Shape& aW=aIt.Value();
376 for (; aItW.More(); aItW.Next()) {
377 const TopoDS_Shape& aE=aItW.Value();
382 // b. collect all edges that are to avoid
383 aItM.Initialize(myShapesToAvoid);
384 for (; aItM.More(); aItM.Next()) {
385 const TopoDS_Shape& aE=aItM.Key();
389 // c. add all edges that are not processed to myShapesToAvoid
390 aIt.Initialize (myShapes);
391 for (; aIt.More(); aIt.Next()) {
392 const TopoDS_Shape& aE=aIt.Value();
393 if (!aMEP.Contains(aE)) {
394 myShapesToAvoid.Add(aE);
399 myLoopsInternal.Clear();
401 aNbEA=myShapesToAvoid.Extent();
402 aItM.Initialize(myShapesToAvoid);
403 for (; aItM.More(); aItM.Next()) {
404 const TopoDS_Shape& aEE=aItM.Key();
405 BOPTools::MapShapesAndAncestors(aEE,
412 aItM.Initialize(myShapesToAvoid);
413 for (; aItM.More()&&bFlag; aItM.Next()) {
414 const TopoDS_Shape& aEE=aItM.Key();
415 if (!aMAdded.Add(aEE)) {
425 for (; aItW.More()&&bFlag; aItW.Next()) {
426 const TopoDS_Edge& aE=(*(TopoDS_Edge *)(&aItW.Value()));
428 TopoDS_Iterator aItE(aE);
429 for (; aItE.More()&&bFlag; aItE.Next()) {
430 const TopoDS_Vertex& aV = (*(TopoDS_Vertex *)(&aItE.Value()));
431 const BOPCol_ListOfShape& aLE=aVEMap.FindFromKey(aV);
433 for (; aIt.More()&&bFlag; aIt.Next()) {
434 const TopoDS_Shape& aEx=aIt.Value();
435 if (aMAdded.Add(aEx)) {
437 if(aMAdded.Extent()==aNbEA) {
441 }//for (; aIt.More(); aIt.Next()) {
442 }//for (; aItE.More(); aItE.Next()) {
443 }//for (; aItW.More(); aItW.Next()) {
444 myLoopsInternal.Append(aW);
445 }//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, aNbDMISB, m, aNbMSH, aNbInOutMap;;
456 TopLoc_Location aLoc;
457 Handle(Geom_Surface) aS;
460 BOPCol_ListIteratorOfListOfInteger aItLI;
461 BOPCol_IndexedMapOfShape aMHE;
462 BOPCol_ListIteratorOfListOfShape aIt1;
463 BOPCol_IndexedDataMapOfShapeListOfShape aMSH;
464 BOPCol_IndexedDataMapOfShapeShape aInOutMap;
465 BOPAlgo_IndexedDataMapOfIntegerShapeBox2D aDMISB(100);
467 BOPCol_Box2DBndTreeSelector aSelector;
468 BOPCol_Box2DBndTree aBBTree;
469 NCollection_UBTreeFiller <Standard_Integer, Bnd_Box2d> aTreeFiller(aBBTree);
473 aTol=BRep_Tool::Tolerance(myFace);
474 aS=BRep_Tool::Surface(myFace, aLoc);
478 // 1. Growthes and Holes -> aDMISB: [Index/ShapeBox2D]
479 aIt1.Initialize(myLoops);
480 for (k=0 ; aIt1.More(); aIt1.Next(), ++k) {
483 const TopoDS_Shape& aWire=aIt1.Value();
485 aBB.MakeFace(aFace, aS, aLoc, aTol);
486 aBB.Add (aFace, aWire);
487 BRepTools::AddUVBounds(aFace, aBox2D);
489 bIsGrowth=IsGrowthWire(aWire, aMHE);
491 bIsHole=Standard_False;
494 // check if a wire is a hole
495 IntTools_FClass2d& aClsf=myContext->FClass2d(aFace);
496 aClsf.Init(aFace, aTol);
498 bIsHole=aClsf.IsHole();
500 BOPTools::MapShapes(aWire, TopAbs_EDGE, aMHE);
502 bIsHole=Standard_True;
505 bIsHole=Standard_False;
509 BOPAlgo_ShapeBox2D aSB2D;
511 aSB2D.SetShape(aFace);
512 aSB2D.SetBox2D(aBox2D);
513 aSB2D.SetIsHole(bIsHole);
515 aDMISB.Add(k, aSB2D);
516 }// for (k=0 ; aIt1.More(); aIt1.Next(), ++k) {
518 // 2. Prepare TreeFiller
519 aNbDMISB=aDMISB.Extent();
520 for (m=1; m<=aNbDMISB; ++m) {
522 const BOPAlgo_ShapeBox2D& aSB2D=aDMISB.FindFromIndex(m);
524 bIsHole=aSB2D.IsHole();
526 const Bnd_Box2d& aBox2D=aSB2D.Box2D();
527 aTreeFiller.Add(k, aBox2D);
531 // 3. Shake TreeFiller
534 // 4. Find outer growth shell that is most close
535 // to each hole shell
536 for (m=1; m<=aNbDMISB; ++m) {
537 const BOPAlgo_ShapeBox2D& aSB2D=aDMISB.FindFromIndex(m);
538 bIsHole=aSB2D.IsHole();
543 const Bnd_Box2d& aBox2DF=aSB2D.Box2D();
544 const TopoDS_Shape aF=aSB2D.Shape();
547 aSelector.SetBox(aBox2DF);
549 aNbHoles=aBBTree.Select(aSelector);
551 const BOPCol_ListOfInteger& aLI=aSelector.Indices();
553 aItLI.Initialize(aLI);
554 for (; aItLI.More(); aItLI.Next()) {
556 const BOPAlgo_ShapeBox2D& aSB2Dk=aDMISB.FindFromKey(k);
557 const TopoDS_Shape& aHole=aSB2Dk.Shape();
559 if (!IsInside(aHole, aF, myContext)){
563 if (aInOutMap.Contains(aHole)){
564 TopoDS_Shape& aF2=aInOutMap.ChangeFromKey(aHole);
565 if (IsInside(aF, aF2, myContext)) {
570 aInOutMap.Add(aHole, aF);
573 }// for (m=1; m<=aNbDMISB; ++m)
575 // 5. Map [Face/Holes] -> aMSH
576 aNbInOutMap=aInOutMap.Extent();
577 for (m=1; m<=aNbInOutMap; ++m) {
578 const TopoDS_Shape& aHole=aInOutMap.FindKey(m);
579 const TopoDS_Shape& aF=aInOutMap.FindFromIndex(m);
581 if (aMSH.Contains(aF)) {
582 BOPCol_ListOfShape& aLH=aMSH.ChangeFromKey(aF);
586 BOPCol_ListOfShape aLH;
592 // 6. Add aHoles to Faces
593 aNbMSH=aMSH.Extent();
594 for (m=1; m<=aNbMSH; ++m) {
595 TopoDS_Face aF=(*(TopoDS_Face *)(&aMSH.FindKey(m)));
596 const BOPCol_ListOfShape& aLH=aMSH.FindFromIndex(m);
598 aIt1.Initialize(aLH);
599 for (; aIt1.More(); aIt1.Next()) {
602 const TopoDS_Shape& aFHole=aIt1.Value();
603 GetWire(aFHole, aWHole);
604 aBB.Add (aF, aWHole);
608 aTol=BRep_Tool::Tolerance(aF);
609 IntTools_FClass2d& aClsf=myContext->FClass2d(aF);
610 aClsf.Init(aF, aTol);
614 // NB:These aNewFaces are draft faces that
615 // do not contain any internal shapes
616 for (m=1; m<=aNbDMISB; ++m) {
617 const BOPAlgo_ShapeBox2D& aSB2D=aDMISB.FindFromIndex(m);
618 bIsHole=aSB2D.IsHole();
620 const TopoDS_Shape aF=aSB2D.Shape();
625 //=======================================================================
628 //=======================================================================
629 void GetWire(const TopoDS_Shape& aF, TopoDS_Shape& aW)
635 for (; aIt.More(); aIt.Next()) {
639 //=======================================================================
640 //function : PerformInternalShapes
642 //=======================================================================
643 void BOPAlgo_BuilderFace::PerformInternalShapes()
647 Standard_Integer aNbWI=myLoopsInternal.Extent();
648 if (!aNbWI) {// nothing to do
652 //Standard_Real aTol;
654 BOPCol_ListIteratorOfListOfShape aIt1, aIt2;
656 BOPCol_MapOfShape aME, aMEP;
657 BOPCol_MapIteratorOfMapOfShape aItME;
658 BOPCol_IndexedDataMapOfShapeListOfShape aMVE;
659 BOPCol_ListOfShape aLSI;
661 // 1. All internal edges
662 aIt1.Initialize(myLoopsInternal);
663 for (; aIt1.More(); aIt1.Next()) {
664 const TopoDS_Shape& aWire=aIt1.Value();
665 aIt.Initialize(aWire);
666 for (; aIt.More(); aIt.Next()) {
667 const TopoDS_Shape& aE=aIt.Value();
674 aIt2.Initialize(myAreas);
675 for ( ; aIt2.More(); aIt2.Next()) {
676 TopoDS_Face& aF=(*(TopoDS_Face *)(&aIt2.Value()));
679 BOPTools::MapShapesAndAncestors(aF, TopAbs_VERTEX, TopAbs_EDGE, aMVE);
681 // 2.1 Separate faces to process aMEP
683 aItME.Initialize(aME);
684 for (; aItME.More(); aItME.Next()) {
685 const TopoDS_Edge& aE=(*(TopoDS_Edge *)(&aItME.Key()));
686 if (IsInside(aE, aF, myContext)) {
691 // 2.2 Make Internal Wires
693 MakeInternalWires(aMEP, aLSI);
695 // 2.3 Add them to aF
696 aIt1.Initialize(aLSI);
697 for (; aIt1.More(); aIt1.Next()) {
698 const TopoDS_Shape& aSI=aIt1.Value();
702 // 2.4 Remove faces aMFP from aMF
703 aItME.Initialize(aMEP);
704 for (; aItME.More(); aItME.Next()) {
705 const TopoDS_Shape& aE=aItME.Key();
713 } //for ( ; aIt2.More(); aIt2.Next()) {
715 //=======================================================================
716 //function : MakeInternalWires
718 //=======================================================================
719 void MakeInternalWires(const BOPCol_MapOfShape& theME,
720 BOPCol_ListOfShape& theWires)
722 BOPCol_MapIteratorOfMapOfShape aItM;
723 BOPCol_MapOfShape aAddedMap;
724 BOPCol_ListIteratorOfListOfShape aItE;
725 BOPCol_IndexedDataMapOfShapeListOfShape aMVE;
728 aItM.Initialize(theME);
729 for (; aItM.More(); aItM.Next()) {
730 const TopoDS_Shape& aE=aItM.Key();
731 BOPTools::MapShapesAndAncestors(aE, TopAbs_VERTEX, TopAbs_EDGE, aMVE);
734 aItM.Initialize(theME);
735 for (; aItM.More(); aItM.Next()) {
736 TopoDS_Shape aEE=aItM.Key();
737 if (!aAddedMap.Add(aEE)) {
744 aEE.Orientation(TopAbs_INTERNAL);
747 TopoDS_Iterator aItAdded (aW);
748 for (; aItAdded.More(); aItAdded.Next()) {
749 const TopoDS_Shape& aE =aItAdded.Value();
751 TopExp_Explorer aExp(aE, TopAbs_VERTEX);
752 for (; aExp.More(); aExp.Next()) {
753 const TopoDS_Shape& aV =aExp.Current();
754 const BOPCol_ListOfShape& aLE=aMVE.FindFromKey(aV);
755 aItE.Initialize(aLE);
756 for (; aItE.More(); aItE.Next()) {
757 TopoDS_Shape aEL=aItE.Value();
758 if (aAddedMap.Add(aEL)){
759 aEL.Orientation(TopAbs_INTERNAL);
768 //=======================================================================
769 //function : IsInside
771 //=======================================================================
772 Standard_Boolean IsInside(const TopoDS_Shape& theHole,
773 const TopoDS_Shape& theF2,
774 Handle(IntTools_Context)& theContext)
776 Standard_Boolean bRet;
777 Standard_Real aT, aU, aV;
780 TopExp_Explorer aExp;
781 BOPCol_IndexedMapOfShape aME2;
785 aState=TopAbs_UNKNOWN;
786 const TopoDS_Face& aF2=(*(TopoDS_Face *)(&theF2));
788 BOPTools::MapShapes(aF2, TopAbs_EDGE, aME2);//AA
790 aExp.Init(theHole, TopAbs_EDGE);
792 const TopoDS_Edge& aE =(*(TopoDS_Edge *)(&aExp.Current()));
793 if (aME2.Contains(aE)) {
796 if (!BRep_Tool::Degenerated(aE)) {
798 aT=BOPTools_AlgoTools2D::IntermediatePoint(aE);
799 BOPTools_AlgoTools2D::PointOnSurface(aE, aF2, aT, aU, aV);
800 aP2D.SetCoord(aU, aV);
802 IntTools_FClass2d& aClsf=theContext->FClass2d(aF2);
803 aState=aClsf.Perform(aP2D);
804 bRet=(aState==TopAbs_IN);
811 //=======================================================================
812 //function : IsGrowthWire
814 //=======================================================================
815 Standard_Boolean IsGrowthWire(const TopoDS_Shape& theWire,
816 const BOPCol_IndexedMapOfShape& theMHE)
818 Standard_Boolean bRet;
822 if (theMHE.Extent()) {
823 aIt.Initialize(theWire);
824 for(; aIt.More(); aIt.Next()) {
825 const TopoDS_Shape& aE=aIt.Value();
826 if (theMHE.Contains(aE)) {
834 //BRepTools::Write(aFF, "ff");
838 // 12 - Null face generix