31ff3a3ac3f6998727863cbf6f1ca88037e27cc8
[occt.git] / src / BOPAlgo / BOPAlgo_Builder_3.cxx
1 // Created by: Peter KURNEV
2 // Copyright (c) 2010-2014 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
6 //
7 // This file is part of Open CASCADE Technology software library.
8 //
9 // This library is free software; you can redistribute it and/or modify it under
10 // the terms of the GNU Lesser General Public License version 2.1 as published
11 // by the Free Software Foundation, with special exception defined in the file
12 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
13 // distribution for complete text of the license and disclaimer of any warranty.
14 //
15 // Alternatively, this file may be used under the terms of Open CASCADE
16 // commercial license or contractual agreement.
17 //
18 #include <BOPAlgo_Builder.hxx>
19 //
20 #include <Precision.hxx>
21 //
22 #include <NCollection_UBTreeFiller.hxx>
23 //
24 #include <Bnd_Box.hxx>
25 #include <TopAbs_State.hxx>
26 //
27 #include <TopoDS.hxx>
28 #include <TopoDS_Iterator.hxx>
29 #include <TopoDS_Solid.hxx>
30 #include <TopoDS_Shape.hxx>
31 #include <TopoDS_Face.hxx>
32 #include <TopoDS_Edge.hxx>
33 #include <TopoDS_Solid.hxx>
34 #include <TopoDS_Iterator.hxx>
35 #include <TopoDS_Shell.hxx>
36 #include <TopoDS_Compound.hxx>
37 //
38 #include <TopExp.hxx>
39 #include <TopExp_Explorer.hxx>
40 //
41 #include <BRep_Builder.hxx>
42 #include <BRepTools.hxx>
43 #include <BRepClass3d_SolidClassifier.hxx>
44 #include <BRepBndLib.hxx>
45 //
46 #include <BOPCol_IndexedMapOfShape.hxx>
47 #include <BOPCol_MapOfShape.hxx>
48 #include <BOPCol_IndexedDataMapOfShapeListOfShape.hxx>
49 #include <BOPCol_ListOfShape.hxx>
50 #include <BOPCol_BoxBndTree.hxx>
51 #include <BOPCol_ListOfInteger.hxx>
52 #include <BOPCol_DataMapOfIntegerShape.hxx>
53 #include <BOPCol_NCVector.hxx>
54 #include <BOPCol_Parallel.hxx>
55 //
56 #include <IntTools_Context.hxx>
57 //
58 #include <BOPDS_DS.hxx>
59 #include <BOPDS_ShapeInfo.hxx>
60 //
61 #include <BOPTools.hxx>
62 #include <BOPTools_AlgoTools.hxx>
63 #include <BOPTools_MapOfSet.hxx>
64 #include <BOPTools_Set.hxx>
65 //
66 #include <BOPAlgo_BuilderSolid.hxx>
67 #include <NCollection_Array1.hxx>
68 #include <NCollection_IncAllocator.hxx>
69
70 #include <algorithm>
71 #include <BOPAlgo_Algo.hxx>
72
73 static
74   void OwnInternalShapes(const TopoDS_Shape& ,
75                          BOPCol_IndexedMapOfShape& );
76
77 static
78   void TreatCompound(const TopoDS_Shape& theS,
79                      BOPCol_MapOfShape& aMFence,
80                      BOPCol_ListOfShape& theLS);
81
82 //=======================================================================
83 // BOPAlgo_BuilderSolid
84 //
85 typedef BOPCol_NCVector
86   <BOPAlgo_BuilderSolid> BOPAlgo_VectorOfBuilderSolid;
87 //
88 typedef BOPCol_Functor 
89   <BOPAlgo_BuilderSolid,
90   BOPAlgo_VectorOfBuilderSolid> BOPAlgo_BuilderSolidFunctor;
91 //
92 typedef BOPCol_Cnt 
93   <BOPAlgo_BuilderSolidFunctor,
94   BOPAlgo_VectorOfBuilderSolid> BOPAlgo_BuilderSolidCnt;
95 //
96 //=======================================================================
97 // class:  BOPAlgo_ShapeBox
98 //
99 //=======================================================================
100 //class     : BOPAlgo_ShapeBox
101 //purpose   : Auxiliary class
102 //=======================================================================
103 class BOPAlgo_ShapeBox {
104  public:
105   BOPAlgo_ShapeBox() {
106   };
107   //
108   ~BOPAlgo_ShapeBox() {
109   };
110   //
111   void SetShape(const TopoDS_Shape& aS) {
112     myShape=aS;
113   };
114   //
115   const TopoDS_Shape& Shape()const {
116     return myShape;
117   };
118   //
119   void SetBox(const Bnd_Box& aBox) {
120     myBox=aBox;
121   };
122   //
123   const Bnd_Box& Box()const {
124     return myBox;
125   };
126   //
127  protected:
128   TopoDS_Shape myShape;
129   Bnd_Box myBox;
130 };
131 //
132 typedef BOPCol_NCVector<BOPAlgo_ShapeBox> BOPAlgo_VectorOfShapeBox;
133 //
134 //=======================================================================
135 // class:  BOPAlgo_FillIn3DParts
136 //
137 //=======================================================================
138 //class : BOPAlgo_FillIn3DParts
139 //purpose  : 
140 //=======================================================================
141 class BOPAlgo_FillIn3DParts : public BOPAlgo_Algo  {
142  public:
143   DEFINE_STANDARD_ALLOC
144   
145   BOPAlgo_FillIn3DParts(){
146     myHasImage=Standard_False;
147     myBBTree=NULL;
148     myVSB=NULL;
149   };
150   //
151   virtual ~BOPAlgo_FillIn3DParts(){
152   };
153   //
154   void SetSolid(const TopoDS_Solid& aS) {
155     mySolid=aS;
156   };
157   //
158   const TopoDS_Solid& Solid()const {
159     return mySolid;
160   };
161   //
162   void SetDraftSolid(const TopoDS_Solid& aS) {
163     myDraftSolid=aS;
164   };
165   //
166   const TopoDS_Solid& DraftSolid()const {
167     return myDraftSolid;
168   };
169   //
170   void SetHasImage(const Standard_Boolean bFlag) {
171     myHasImage=bFlag;
172   };
173   //
174   Standard_Boolean HasImage()const {
175     return myHasImage;
176   };
177   //
178   void SetBoxS(const Bnd_Box& aBox) {
179     myBoxS=aBox;
180   };
181   //
182   const Bnd_Box& BoxS()const {
183     return myBoxS;
184   };
185   //
186   void SetLIF(const BOPCol_ListOfShape& aLIF) {
187     myLIF=aLIF;
188   };
189   //
190   const BOPCol_ListOfShape& LIF()const {
191     return myLIF;
192   };
193   //
194   void SetBBTree(const BOPCol_BoxBndTree& aBBTree) {
195     myBBTree=(BOPCol_BoxBndTree*)&aBBTree;
196   };
197   //
198   void SetVSB(const BOPAlgo_VectorOfShapeBox& aVSB) {
199     myVSB=(BOPAlgo_VectorOfShapeBox*)&aVSB;
200   };
201   //
202   //
203   void SetContext(const Handle(IntTools_Context)& aContext) {
204     myContext=aContext;
205   }
206   //
207   const Handle(IntTools_Context)& Context()const {
208     return myContext;
209   }
210   //
211   virtual void Perform();
212   //
213   
214   //
215   const BOPCol_ListOfShape& LFIN()const {
216     return myLFIN;
217   };
218   
219  protected:
220   void MapEdgesAndFaces
221     (const TopoDS_Shape& ,
222      BOPCol_IndexedDataMapOfShapeListOfShape& ,
223      const Handle(NCollection_BaseAllocator)& );
224   
225   void MakeConnexityBlock 
226     (const TopoDS_Face& ,
227      const BOPCol_IndexedMapOfShape& ,
228      const BOPCol_IndexedDataMapOfShapeListOfShape& ,
229      BOPCol_MapOfShape& ,
230      BOPCol_ListOfShape& );
231   //
232  protected:
233   TopoDS_Solid mySolid;
234   TopoDS_Solid myDraftSolid;
235   Standard_Boolean myHasImage;
236   Bnd_Box myBoxS;
237   BOPCol_ListOfShape myLIF;
238   BOPCol_ListOfShape myLFIN;
239   //
240   BOPCol_BoxBndTree* myBBTree;
241   BOPAlgo_VectorOfShapeBox* myVSB;
242   //
243   TopoDS_Iterator myItF;
244   TopoDS_Iterator myItW;
245   
246   Handle(IntTools_Context) myContext;
247 };
248
249 //=======================================================================
250 //function : BOPAlgo_FillIn3DParts::Perform
251 //purpose  : 
252 //=======================================================================
253 void BOPAlgo_FillIn3DParts::Perform() 
254 {
255   BOPAlgo_Algo::UserBreak();
256
257   myLFIN.Clear();
258
259   Handle(NCollection_BaseAllocator) aAlr1 = new NCollection_IncAllocator;
260
261   BOPAlgo_VectorOfShapeBox& aVSB = *myVSB;
262
263   // 1. Fill maps of edges and faces of myDraftSolid
264   BOPCol_IndexedMapOfShape aME(1, aAlr1), aMF(1, aAlr1);
265   BOPTools::MapShapes(myDraftSolid, TopAbs_EDGE, aME);
266   BOPTools::MapShapes(myDraftSolid, TopAbs_FACE, aMF);
267   // Check if the Draft Solid contains any faces
268   Standard_Boolean bIsEmpty = aMF.IsEmpty();
269   // Add own internal faces of myDraftSolid into aMF
270   BOPCol_ListIteratorOfListOfShape aItLS(myLIF);
271   for (; aItLS.More(); aItLS.Next())
272     aMF.Add(aItLS.Value());
273
274   // 2. Select boxes of faces that are not out of aBoxS
275   BOPCol_BoxBndTreeSelector aSelector;
276   aSelector.SetBox(myBoxS);
277   //
278   myBBTree->Select(aSelector);
279   const BOPCol_ListOfInteger& aLIFP = aSelector.Indices();
280   //
281   // 3. aIVec - faces to process.
282   //    Filter the selected faces with faces of the solid.
283   BOPCol_NCVector<Standard_Integer> aIVec(256, aAlr1);
284
285   BOPCol_ListIteratorOfListOfInteger aItLI(aLIFP);
286   for (; aItLI.More(); aItLI.Next()) {
287     Standard_Integer nFP = aItLI.Value();
288     const TopoDS_Shape& aFP = aVSB(nFP).Shape();
289     if (!aMF.Contains(aFP))
290       aIVec.Append1() = nFP;
291   }
292
293   // 4. Classify faces relatively solid.
294   //    Store faces that are IN mySolid into <myLFIN>
295
296   Standard_Integer k, aNbFP = aIVec.Extent();
297   // Sort indices if necessary
298   if (aNbFP > 1)
299     std::sort(aIVec.begin(), aIVec.end());
300
301   if (bIsEmpty)
302   {
303     // The Draft solid is empty as it does not contain any faces.
304     // It could happen when the input solid consists of INTERNAL faces only.
305     // Classification of any point relatively empty solid would always give IN status.
306     // Thus, we consider all selected faces as IN without real classification.
307     for (k = 0; k < aNbFP; ++k)
308       myLFIN.Append(aVSB(aIVec(k)).Shape());
309
310     return;
311   }
312
313   // Prepare EF map of faces to process for building connexity blocks
314   BOPCol_IndexedDataMapOfShapeListOfShape aMEFP(1, aAlr1);
315   if (aNbFP > 1)
316   {
317     for (k = 0; k < aNbFP; ++k)
318       MapEdgesAndFaces(aVSB(aIVec(k)).Shape(), aMEFP, aAlr1);
319   }
320
321   // Map of Edge-Face connection, necessary for solid classification.
322   // It will be filled when first classification is performed.
323   BOPCol_IndexedDataMapOfShapeListOfShape aMEFDS(1, aAlr1);
324
325   // Fence map to avoid processing of the same faces twice
326   BOPCol_MapOfShape aMFDone(1, aAlr1);
327
328   for (k = 0; k < aNbFP; ++k)
329   {
330     Standard_Integer nFP = aIVec(k);
331     const TopoDS_Face& aFP = (*(TopoDS_Face*)&aVSB(nFP).Shape());
332     if (!aMFDone.Add(aFP))
333       continue;
334
335     // Make connexity blocks of faces, avoiding passing through the
336     // borders of the solid. It helps to reduce significantly the
337     // number of classified faces.
338     BOPCol_ListOfShape aLCBF(aAlr1);
339     MakeConnexityBlock(aFP, aME, aMEFP, aMFDone, aLCBF);
340
341     // First, try fast classification of the whole block by additional
342     // check on bounding boxes - check that bounding boxes of all vertices
343     // of the block interfere with the box of the solid.
344     // If not, the faces are out.
345     Standard_Boolean bOut = Standard_False;
346     aItLS.Initialize(aLCBF);
347     for (; aItLS.More() && !bOut; aItLS.Next())
348     {
349       TopExp_Explorer anExpV(aItLS.Value(), TopAbs_VERTEX);
350       for (; anExpV.More() && !bOut; anExpV.Next())
351       {
352         const TopoDS_Vertex& aV = TopoDS::Vertex(anExpV.Current());
353         Bnd_Box aBBV;
354         aBBV.Add(BRep_Tool::Pnt(aV));
355         aBBV.SetGap(BRep_Tool::Tolerance(aV));
356         bOut = myBoxS.IsOut(aBBV);
357       }
358     }
359
360     if (bOut)
361       continue;
362
363     if (aMEFDS.IsEmpty())
364       // Fill EF map for myDraftSolid
365       BOPTools::MapShapesAndAncestors(myDraftSolid, TopAbs_EDGE, TopAbs_FACE, aMEFDS);
366
367     // All vertices are interfere with the solids box, run classification.
368     Standard_Boolean bIsIN = BOPTools_AlgoTools::IsInternalFace
369       (aFP, myDraftSolid, aMEFDS, Precision::Confusion(), myContext);
370     if (bIsIN)
371     {
372       aItLS.Initialize(aLCBF);
373       for (; aItLS.More(); aItLS.Next())
374         myLFIN.Append(aItLS.Value());
375     }
376   }
377 }
378 //=======================================================================
379 // function: MapEdgesAndFaces
380 // purpose: 
381 //=======================================================================
382 void BOPAlgo_FillIn3DParts::MapEdgesAndFaces
383   (const TopoDS_Shape& aF,
384    BOPCol_IndexedDataMapOfShapeListOfShape& aMEF,
385    const Handle(NCollection_BaseAllocator)& theAllocator)
386 {
387   myItF.Initialize(aF);
388   for (; myItF.More(); myItF.Next()) {
389     const TopoDS_Shape& aW=myItF.Value();
390     if (aW.ShapeType()!=TopAbs_WIRE) {
391       continue;
392     }
393     //
394     myItW.Initialize(aW);
395     for (; myItW.More(); myItW.Next()) {
396       const TopoDS_Shape& aE=myItW.Value();
397       //
398       BOPCol_ListOfShape* pLF = aMEF.ChangeSeek(aE);
399       if (!pLF)
400         pLF = &aMEF(aMEF.Add(aE, BOPCol_ListOfShape(theAllocator)));
401       pLF->Append(aF);
402     }
403   }
404 }
405 //=======================================================================
406 // function: MakeConnexityBlock
407 // purpose: 
408 //=======================================================================
409 void BOPAlgo_FillIn3DParts::MakeConnexityBlock
410   (const TopoDS_Face& theFStart,
411    const BOPCol_IndexedMapOfShape& theMEAvoid,
412    const BOPCol_IndexedDataMapOfShapeListOfShape& theMEF,
413    BOPCol_MapOfShape& theMFDone,
414    BOPCol_ListOfShape& theLCB)
415 {
416   // Add start element
417   theLCB.Append(theFStart);
418   if (theMEF.IsEmpty())
419     return;
420
421   BOPCol_ListIteratorOfListOfShape aItCB(theLCB);
422   for (; aItCB.More(); aItCB.Next())
423   {
424     const TopoDS_Shape& aF = aItCB.Value();
425     myItF.Initialize(aF);
426     for (; myItF.More(); myItF.Next())
427     {
428       const TopoDS_Shape& aW = myItF.Value();
429       if (aW.ShapeType() != TopAbs_WIRE)
430         continue;
431
432       myItW.Initialize(aW);
433       for (; myItW.More(); myItW.Next())
434       {
435         const TopoDS_Shape& aE = myItW.Value();
436         if (theMEAvoid.Contains(aE))
437           continue;
438
439         const BOPCol_ListOfShape* pLF = theMEF.Seek(aE);
440         if (!pLF)
441           continue;
442         BOPCol_ListIteratorOfListOfShape aItLF(*pLF);
443         for (; aItLF.More(); aItLF.Next())
444         {
445           const TopoDS_Shape& aFx = aItLF.Value();
446           if (!aFx.IsSame(aF) && theMFDone.Add(aFx))
447             theLCB.Append(aFx);
448         }
449       }
450     }
451   }
452 }
453 //
454 typedef BOPCol_NCVector<BOPAlgo_FillIn3DParts> \
455   BOPAlgo_VectorOfFillIn3DParts;
456 //
457 typedef BOPCol_ContextFunctor 
458   <BOPAlgo_FillIn3DParts,
459   BOPAlgo_VectorOfFillIn3DParts,
460   Handle(IntTools_Context), 
461   IntTools_Context> BOPCol_FillIn3DPartsFunctor;
462 //
463 typedef BOPCol_ContextCnt 
464   <BOPCol_FillIn3DPartsFunctor,
465   BOPAlgo_VectorOfFillIn3DParts,
466   Handle(IntTools_Context)> BOPAlgo_FillIn3DPartsCnt;
467 //
468 //=======================================================================
469 // class:  BOPAlgo_Builder
470 //
471 //=======================================================================
472 //function : FillImagesSolids
473 //purpose  : 
474 //=======================================================================
475 void BOPAlgo_Builder::FillImagesSolids()
476 {
477   Standard_Boolean bHasSolids;
478   Standard_Integer i, aNbS;
479   //
480   bHasSolids=Standard_False;
481   aNbS=myDS->NbSourceShapes();
482   for (i=0; i<aNbS; ++i) {
483     const BOPDS_ShapeInfo& aSI=myDS->ShapeInfo(i);
484     if (aSI.ShapeType()==TopAbs_SOLID) {
485       bHasSolids=!bHasSolids;
486       break;
487     }
488   }
489   //
490   if (!bHasSolids) {
491     return;
492   }
493   // 
494   Handle(NCollection_BaseAllocator) aAlr;
495   //
496   aAlr=NCollection_BaseAllocator::CommonBaseAllocator();
497   //
498   BOPCol_DataMapOfShapeListOfShape theInParts(100, aAlr);
499   BOPCol_DataMapOfShapeShape theDraftSolids(100, aAlr);
500   //
501   FillIn3DParts(theInParts, theDraftSolids, aAlr); 
502   BuildSplitSolids(theInParts, theDraftSolids, aAlr);
503   FillInternalShapes();
504   //
505   theInParts.Clear();
506   theDraftSolids.Clear();
507 }
508 //=======================================================================
509 //function : FillIn3DParts
510 //purpose  : 
511 //=======================================================================
512 void BOPAlgo_Builder::FillIn3DParts
513   (BOPCol_DataMapOfShapeListOfShape& theInParts,
514    BOPCol_DataMapOfShapeShape& theDraftSolids,
515    const BOPCol_BaseAllocator& )
516 {
517   Standard_Boolean bHasImage;
518   Standard_Integer i, k, aNbS, aNbLIF, aNbFIN, aNbVSB, aNbVFIP;
519   Handle(NCollection_BaseAllocator) aAlr0;
520   TopoDS_Solid aSD;
521   TopoDS_Iterator aIt;
522   BRep_Builder aBB; 
523   //
524   BOPCol_ListIteratorOfListOfInteger aItLI, aItLI1;
525   BOPCol_ListIteratorOfListOfShape aItLS;
526   //
527   aAlr0=
528     NCollection_BaseAllocator::CommonBaseAllocator();
529   //
530   BOPCol_MapOfShape aMFence(100, aAlr0);
531   BOPAlgo_VectorOfShapeBox aVSB(256, aAlr0);
532   //
533   theDraftSolids.Clear();
534   //
535   // 1. aVSB vector Index/FaceBox 
536   aNbS=myDS->NbSourceShapes();
537   for (i=0; i<aNbS; ++i) {
538     const BOPDS_ShapeInfo& aSI=myDS->ShapeInfo(i);
539     if (aSI.ShapeType()!=TopAbs_FACE) {
540       continue;
541     }
542     //
543     const TopoDS_Shape& aS=aSI.Shape();
544     //
545     if (myImages.IsBound(aS)) {
546       const BOPCol_ListOfShape& aLS=myImages.Find(aS);
547       aItLS.Initialize(aLS);
548       for (; aItLS.More(); aItLS.Next()) {
549         const TopoDS_Shape& aSx=aItLS.Value();
550         if (!aMFence.Add(aSx)) {
551           continue;
552         }
553         Bnd_Box aBox;
554         BRepBndLib::Add(aSx, aBox);
555         aBox.SetGap(aBox.GetGap() + Precision::Confusion());
556         //
557         BOPAlgo_ShapeBox& aSB=aVSB.Append1();
558         aSB.SetShape(aSx);
559         aSB.SetBox(aBox);
560       }
561     }
562     else {
563       const Bnd_Box& aBox=aSI.Box();
564       //
565       BOPAlgo_ShapeBox& aSB=aVSB.Append1();
566       aSB.SetShape(aS);
567       aSB.SetBox(aBox);
568     }
569   }//for (i=0; i<aNbS; ++i) {
570   aMFence.Clear();
571   //
572   // 1.2. Prepare TreeFiller
573   BOPCol_BoxBndTree aBBTree;
574   NCollection_UBTreeFiller <Standard_Integer, Bnd_Box> 
575     aTreeFiller(aBBTree);
576   //
577   aNbVSB=aVSB.Extent();
578   for (k=0; k<aNbVSB; ++k) {
579     const BOPAlgo_ShapeBox& aSBk=aVSB(k);
580     const Bnd_Box& aBk=aSBk.Box();
581     //
582     aTreeFiller.Add(k, aBk);
583   }
584   //
585   // 1.3. Shake TreeFiller
586   aTreeFiller.Fill();
587   //
588   //---------------------------------------------
589   // 2. Solids
590   BOPAlgo_VectorOfFillIn3DParts aVFIP;
591   //
592   for (i=0; i<aNbS; ++i) {
593     BOPDS_ShapeInfo& aSI=myDS->ChangeShapeInfo(i);
594     if (aSI.ShapeType()!=TopAbs_SOLID) {
595       continue;
596     }
597     //
598     const TopoDS_Shape& aS=aSI.Shape();
599     const TopoDS_Solid& aSolid=(*(TopoDS_Solid*)(&aS));
600     //
601     // 2.0 Flag bHasImage
602     bHasImage=Standard_False;
603     aIt.Initialize(aS);
604     for (; aIt.More(); aIt.Next()) {
605       const TopoDS_Shape& aShell=aIt.Value();
606       bHasImage=myImages.IsBound(aShell);
607       if (bHasImage){
608         break;
609       }
610     }
611     //
612     // 2.1 Bounding box for the solid aS  [ aBoxS ]
613     Bnd_Box& aBoxS = aSI.ChangeBox();
614     if (aBoxS.IsVoid())
615       myDS->BuildBndBoxSolid(i, aBoxS, myCheckInverted);
616     //
617     // 2.2 Build Draft Solid [aSD]
618     BOPCol_ListOfShape aLIF;
619     //
620     aBB.MakeSolid(aSD);
621     BuildDraftSolid(aSolid, aSD, aLIF);
622     //
623     BOPAlgo_FillIn3DParts& aFIP=aVFIP.Append1();
624     //
625     aFIP.SetSolid(aSolid);
626     aFIP.SetDraftSolid(aSD);
627     aFIP.SetHasImage(bHasImage);
628     aFIP.SetBoxS(aBoxS);
629     aFIP.SetLIF(aLIF);
630     aFIP.SetBBTree(aBBTree);
631     aFIP.SetVSB(aVSB);
632   }//for (i=0; i<aNbS; ++i) {
633   //
634   aNbVFIP=aVFIP.Extent();
635   //================================================================
636   BOPAlgo_FillIn3DPartsCnt::Perform(myRunParallel, aVFIP, myContext);
637   //================================================================
638   for (k=0; k<aNbVFIP; ++k) {
639     BOPAlgo_FillIn3DParts& aFIP=aVFIP(k);
640     bHasImage=aFIP.HasImage();
641     const TopoDS_Solid& aSolid=aFIP.Solid();
642     const TopoDS_Solid& aSDraft =aFIP.DraftSolid();
643     const BOPCol_ListOfShape& aLFIN=aFIP.LFIN();
644     const BOPCol_ListOfShape& aLIF=aFIP.LIF();
645     //
646     aNbLIF=aLIF.Extent();
647     //
648     // Store the results in theInParts, theDraftSolids
649     BOPCol_ListOfShape aLFINx;
650     //
651     aNbFIN=aLFIN.Extent();
652     if (aNbFIN || aNbLIF) {
653       aItLS.Initialize(aLFIN);
654       for (; aItLS.More(); aItLS.Next()) {
655         const TopoDS_Shape& aFI=aItLS.Value();
656         aLFINx.Append(aFI);
657       }
658       aItLS.Initialize(aLIF);
659       for (; aItLS.More(); aItLS.Next()) {
660         const TopoDS_Shape& aFI=aItLS.Value();
661         aLFINx.Append(aFI);
662       }
663       theInParts.Bind(aSolid, aLFINx);
664     }
665     //
666     if (aNbFIN || bHasImage) {
667       theDraftSolids.Bind(aSolid, aSDraft);
668     }
669   }
670 }
671 //=======================================================================
672 //function : BuildDraftSolid
673 //purpose  : 
674 //=======================================================================
675 void BOPAlgo_Builder::BuildDraftSolid(const TopoDS_Shape& theSolid,
676                                       TopoDS_Shape& theDraftSolid,
677                                       BOPCol_ListOfShape& theLIF)
678 {
679   Standard_Boolean bToReverse;
680   Standard_Integer iFlag;
681   TopAbs_Orientation aOrF, aOrSh, aOrSd;
682   TopoDS_Iterator aIt1, aIt2;
683   TopoDS_Shell aShD;
684   TopoDS_Shape aFSDx, aFx;
685   BRep_Builder aBB;
686   BOPCol_ListIteratorOfListOfShape aItS; 
687   //
688   aOrSd=theSolid.Orientation();
689   theDraftSolid.Orientation(aOrSd);
690   //
691   aIt1.Initialize(theSolid);
692   for (; aIt1.More(); aIt1.Next()) {
693     const TopoDS_Shape& aSh=aIt1.Value();
694     if(aSh.ShapeType()!=TopAbs_SHELL) {
695       continue; // mb internal edges,vertices
696     }
697     //
698     aOrSh=aSh.Orientation();
699     aBB.MakeShell(aShD);
700     aShD.Orientation(aOrSh);
701     iFlag=0;
702     //
703     aIt2.Initialize(aSh);
704     for (; aIt2.More(); aIt2.Next()) {
705       const TopoDS_Shape& aF=aIt2.Value();
706       aOrF=aF.Orientation();
707       //
708       if (myImages.IsBound(aF)) {
709         const BOPCol_ListOfShape& aLSp=myImages.Find(aF);
710         aItS.Initialize(aLSp);
711         for (; aItS.More(); aItS.Next()) {
712           aFx=aItS.Value();
713           //
714           if (myShapesSD.IsBound(aFx)) {
715             aFSDx=myShapesSD.Find(aFx);
716             //
717             if (aOrF==TopAbs_INTERNAL) {
718               aFSDx.Orientation(aOrF);
719               theLIF.Append(aFSDx);
720             }
721             else {
722               bToReverse=BOPTools_AlgoTools::IsSplitToReverse
723                 (aFSDx, aF, myContext); 
724               if (bToReverse) {
725                 aFSDx.Reverse();
726               }
727               //
728               iFlag=1;
729               aBB.Add(aShD, aFSDx);
730             }
731           }//if (myShapesSD.IsBound(aFx)) {
732           else {
733             aFx.Orientation(aOrF);
734             if (aOrF==TopAbs_INTERNAL) {
735               theLIF.Append(aFx);
736             }
737             else{
738               iFlag=1;
739               aBB.Add(aShD, aFx);
740             }
741           }
742         }
743       } // if (myImages.IsBound(aF)) { 
744       //
745       else {
746         if (aOrF==TopAbs_INTERNAL) {
747           theLIF.Append(aF);
748         }
749         else{
750           iFlag=1;
751           aBB.Add(aShD, aF);
752         }
753       }
754     } //for (; aIt2.More(); aIt2.Next()) {
755     //
756     if (iFlag) {
757       aShD.Closed (BRep_Tool::IsClosed (aShD));
758       aBB.Add(theDraftSolid, aShD);
759     }
760   } //for (; aIt1.More(); aIt1.Next()) {
761 }
762 //=======================================================================
763 //function : BuildSplitSolids
764 //purpose  : 
765 //=======================================================================
766 void BOPAlgo_Builder::BuildSplitSolids
767   (BOPCol_DataMapOfShapeListOfShape& theInParts,
768    BOPCol_DataMapOfShapeShape& theDraftSolids,
769    const BOPCol_BaseAllocator&  )
770 {
771   Standard_Boolean bFlagSD;
772   Standard_Integer i, aNbS;
773   TopExp_Explorer aExp;
774   BOPCol_ListIteratorOfListOfShape aIt;
775   //
776   Handle(NCollection_BaseAllocator) aAlr0;
777   aAlr0=NCollection_BaseAllocator::CommonBaseAllocator();
778   //
779   BOPCol_ListOfShape aSFS(aAlr0), aLSEmpty(aAlr0);
780   BOPCol_MapOfShape aMFence(100, aAlr0);
781   BOPTools_MapOfSet aMST(100, aAlr0);
782   BOPAlgo_VectorOfBuilderSolid aVBS;
783   //
784   // 0. Find same domain solids for non-interferred solids
785   aNbS=myDS->NbSourceShapes();
786   for (i=0; i<aNbS; ++i) {
787     const BOPDS_ShapeInfo& aSI=myDS->ShapeInfo(i);
788     //
789     if (aSI.ShapeType()!=TopAbs_SOLID) {
790       continue;
791     }
792     //
793     const TopoDS_Shape& aS=aSI.Shape();
794     if (!aMFence.Add(aS)) {
795       continue;
796     }
797     if(theDraftSolids.IsBound(aS)) {
798       continue;
799     }
800     //
801     BOPTools_Set aST;
802     //
803     aST.Add(aS, TopAbs_FACE);
804     aMST.Add(aST);
805     //
806   } //for (i=1; i<=aNbS; ++i) 
807   //
808   // Build temporary map of solids images to avoid rebuilding
809   // of the solids without internal faces
810   BOPCol_IndexedDataMapOfShapeListOfShape aSolidsIm;
811   // 1. Build solids for interfered source solids
812   for (i = 0; i < aNbS; ++i) {
813     const BOPDS_ShapeInfo& aSI = myDS->ShapeInfo(i);
814     if (aSI.ShapeType() != TopAbs_SOLID)
815       continue;
816
817     const TopoDS_Shape& aS = aSI.Shape();
818     const TopoDS_Solid& aSolid=(*(TopoDS_Solid*)(&aS));
819     if (!theDraftSolids.IsBound(aS))
820       continue;
821
822     const TopoDS_Shape& aSD = theDraftSolids.Find(aS);
823     const BOPCol_ListOfShape* pLFIN = theInParts.Seek(aS);
824     if (!pLFIN)
825     {
826       aSolidsIm(aSolidsIm.Add(aS, BOPCol_ListOfShape())).Append(aSD);
827       continue;
828     }
829
830     aSFS.Clear();
831     //
832     // 1.1 Fill Shell Faces Set
833     aExp.Init(aSD, TopAbs_FACE);
834     for (; aExp.More(); aExp.Next()) {
835       const TopoDS_Shape& aF = aExp.Current();
836       aSFS.Append(aF);
837     }
838     //
839     // 1.2 Fill internal faces
840     aIt.Initialize(*pLFIN);
841     for (; aIt.More(); aIt.Next()) {
842       TopoDS_Shape aF = aIt.Value();
843       //
844       aF.Orientation(TopAbs_FORWARD);
845       aSFS.Append(aF);
846       aF.Orientation(TopAbs_REVERSED);
847       aSFS.Append(aF);
848     }
849     //
850     // 1.3 Build new solids
851     BOPAlgo_BuilderSolid& aBS=aVBS.Append1();
852     aBS.SetSolid(aSolid);
853     aBS.SetShapes(aSFS);
854     aBS.SetRunParallel(myRunParallel);
855     aBS.SetProgressIndicator(myProgressIndicator);
856   }//for (i=0; i<aNbS; ++i) {
857   //
858   Standard_Integer k, aNbBS;
859   //
860   aNbBS=aVBS.Extent();
861   //
862   //===================================================
863   BOPAlgo_BuilderSolidCnt::Perform(myRunParallel, aVBS);
864   //===================================================
865   //
866   for (k = 0; k < aNbBS; ++k)
867   {
868     BOPAlgo_BuilderSolid& aBS = aVBS(k);
869     aSolidsIm.Add(aBS.Solid(), aBS.Areas());
870   }
871   //
872   // Add new solids to images map
873   aNbBS = aSolidsIm.Extent();
874   for (k = 1; k <= aNbBS; ++k)
875   {
876     const TopoDS_Shape& aS = aSolidsIm.FindKey(k);
877     const BOPCol_ListOfShape& aLSR = aSolidsIm(k);
878     //
879     if (!myImages.IsBound(aS)) {
880       BOPCol_ListOfShape* pLSx = myImages.Bound(aS, BOPCol_ListOfShape());
881       //
882       aIt.Initialize(aLSR);
883       for (; aIt.More(); aIt.Next()) {
884         BOPTools_Set aST;
885         //
886         const TopoDS_Shape& aSR=aIt.Value();
887         aST.Add(aSR, TopAbs_FACE);
888         //
889         bFlagSD=aMST.Contains(aST);
890         //
891         const BOPTools_Set& aSTx=aMST.Added(aST);
892         const TopoDS_Shape& aSx=aSTx.Shape();
893         pLSx->Append(aSx);
894         //
895         BOPCol_ListOfShape* pLOr = myOrigins.ChangeSeek(aSx);
896         if (!pLOr) {
897           pLOr = myOrigins.Bound(aSx, BOPCol_ListOfShape());
898         }
899         pLOr->Append(aS);
900         //
901         if (bFlagSD) {
902           myShapesSD.Bind(aSR, aSx);
903         }
904       }
905     }
906   }
907 }
908 //=======================================================================
909 //function :FillInternalShapes 
910 //purpose  : 
911 //=======================================================================
912 void BOPAlgo_Builder::FillInternalShapes()
913 {
914   Standard_Integer i, j,  aNbS, aNbSI, aNbSx;
915   TopAbs_ShapeEnum aType;
916   TopAbs_State aState; 
917   TopoDS_Iterator aItS;
918   BRep_Builder aBB;
919   BOPCol_ListIteratorOfListOfShape aIt, aIt1;
920   //
921   Handle(NCollection_BaseAllocator) aAllocator;
922   //-----------------------------------------------------scope f
923   aAllocator=NCollection_BaseAllocator::CommonBaseAllocator();
924   //
925   BOPCol_IndexedDataMapOfShapeListOfShape aMSx(100, aAllocator);
926   BOPCol_IndexedMapOfShape aMx(100, aAllocator);
927   BOPCol_IndexedMapOfShape aMSI(100, aAllocator);
928   BOPCol_MapOfShape aMFence(100, aAllocator);
929   BOPCol_MapOfShape aMSOr(100, aAllocator);
930   BOPCol_ListOfShape aLSd(aAllocator);
931   BOPCol_ListOfShape aLArgs(aAllocator);
932   BOPCol_ListOfShape aLSC(aAllocator);
933   BOPCol_ListOfShape aLSI(aAllocator);
934   //
935   // 1. Shapes to process
936   //
937   // 1.1 Shapes from pure arguments aMSI 
938   // 1.1.1 vertex, edge, wire
939   //
940   const BOPCol_ListOfShape& aArguments=myDS->Arguments();
941   aIt.Initialize(aArguments);
942   for (; aIt.More(); aIt.Next()) {
943     const TopoDS_Shape& aS=aIt.Value();
944     TreatCompound(aS, aMFence, aLSC);
945   }
946   aIt.Initialize(aLSC);
947   for (; aIt.More(); aIt.Next()) {
948     const TopoDS_Shape& aS=aIt.Value();
949     aType=aS.ShapeType();
950     if (aType==TopAbs_WIRE) {
951       aItS.Initialize(aS);
952       for(; aItS.More(); aItS.Next()) {
953         const TopoDS_Shape& aE=aItS.Value();
954         if (aMFence.Add(aE)) {
955           aLArgs.Append(aE);
956         }
957       }
958     }
959     else if (aType==TopAbs_VERTEX || aType==TopAbs_EDGE){
960       aLArgs.Append(aS);
961     } 
962   }
963   aMFence.Clear();
964   //
965   aIt.Initialize(aLArgs);
966   for (; aIt.More(); aIt.Next()) {
967     const TopoDS_Shape& aS=aIt.Value();
968     aType=aS.ShapeType();
969     if (aType==TopAbs_VERTEX || 
970         aType==TopAbs_EDGE ||
971         aType==TopAbs_WIRE) {
972       if (aMFence.Add(aS)) {
973         if (myImages.IsBound(aS)) {
974           const BOPCol_ListOfShape &aLSp=myImages.Find(aS);
975           aIt1.Initialize(aLSp);
976           for (; aIt1.More(); aIt1.Next()) {
977             const TopoDS_Shape& aSp=aIt1.Value();
978             aMSI.Add(aSp);
979           }
980         }
981         else {
982           aMSI.Add(aS);
983         }
984       }
985     }
986   }
987   
988   aNbSI=aMSI.Extent();
989   //
990   // 2. Internal vertices, edges from source solids
991   aMFence.Clear();
992   aLSd.Clear();
993   //
994   aNbS=myDS->NbSourceShapes();
995   for (i=0; i<aNbS; ++i) {
996     const BOPDS_ShapeInfo& aSI=myDS->ShapeInfo(i);
997     //
998     if (aSI.ShapeType()!=TopAbs_SOLID) {
999       continue;
1000     }
1001     //
1002     UserBreak();
1003     //
1004     const TopoDS_Shape& aS=aSI.Shape();
1005     //
1006     aMx.Clear();
1007     OwnInternalShapes(aS, aMx);
1008     //
1009     aNbSx=aMx.Extent();
1010     for (j=1; j<=aNbSx; ++j) {
1011       const TopoDS_Shape& aSi=aMx(j);
1012       if (myImages.IsBound(aSi)) {
1013         const BOPCol_ListOfShape &aLSp=myImages.Find(aSi);
1014         aIt1.Initialize(aLSp);
1015         for (; aIt1.More(); aIt1.Next()) {
1016           const TopoDS_Shape& aSp=aIt1.Value();
1017           aMSI.Add(aSp);
1018         }
1019       }
1020       else {
1021         aMSI.Add(aSi);
1022       }
1023     }
1024     //
1025     // build aux map from splits of solids
1026     if (myImages.IsBound(aS)) {
1027       const BOPCol_ListOfShape &aLSp=myImages.Find(aS);
1028       aIt.Initialize(aLSp);
1029       for (; aIt.More(); aIt.Next()) {
1030         const TopoDS_Shape& aSp=aIt.Value();
1031         if (aMFence.Add(aSp)) { 
1032           BOPTools::MapShapesAndAncestors(aSp, TopAbs_VERTEX, TopAbs_EDGE, aMSx);
1033           BOPTools::MapShapesAndAncestors(aSp, TopAbs_VERTEX, TopAbs_FACE, aMSx);
1034           BOPTools::MapShapesAndAncestors(aSp, TopAbs_EDGE  , TopAbs_FACE, aMSx);
1035           aLSd.Append(aSp);
1036         }
1037       }
1038     }
1039     else {
1040       if (aMFence.Add(aS)) {
1041         BOPTools::MapShapesAndAncestors(aS, TopAbs_VERTEX, TopAbs_EDGE, aMSx);
1042         BOPTools::MapShapesAndAncestors(aS, TopAbs_VERTEX, TopAbs_FACE, aMSx);
1043         BOPTools::MapShapesAndAncestors(aS, TopAbs_EDGE  , TopAbs_FACE, aMSx);
1044         aLSd.Append(aS);
1045         aMSOr.Add(aS); 
1046       }
1047     }
1048   }// for (i=0; i<aNbS; ++i) {
1049   //
1050   // 3. Some shapes of aMSI can be already tied with faces of 
1051   //    split solids
1052   aNbSI = aMSI.Extent();
1053   for (i = 1; i <= aNbSI; ++i) {
1054     const TopoDS_Shape& aSI = aMSI(i);
1055     if (aMSx.Contains(aSI)) {
1056       const BOPCol_ListOfShape &aLSx=aMSx.FindFromKey(aSI);
1057       aNbSx = aLSx.Extent();
1058       if (!aNbSx) {
1059         aLSI.Append(aSI);
1060       }
1061     }
1062     else {
1063       aLSI.Append(aSI);
1064     }
1065   }
1066   //
1067   // 4. Just check it
1068   aNbSI = aLSI.Extent();
1069   if (!aNbSI) {
1070     return;
1071   }
1072   //
1073   // 5 Settle internal vertices and edges into solids
1074   aMx.Clear();
1075   aIt.Initialize(aLSd);
1076   for (; aIt.More(); aIt.Next()) {
1077     TopoDS_Solid aSd=TopoDS::Solid(aIt.Value());
1078     //
1079     aIt1.Initialize(aLSI);
1080     for (; aIt1.More();) {
1081       TopoDS_Shape aSI = aIt1.Value();
1082       aSI.Orientation(TopAbs_INTERNAL);
1083       //
1084       aState=BOPTools_AlgoTools::ComputeStateByOnePoint
1085         (aSI, aSd, 1.e-11, myContext);
1086       //
1087       if (aState != TopAbs_IN) {
1088         aIt1.Next();
1089         continue;
1090       }
1091       //
1092       if (aMSOr.Contains(aSd)) {
1093         // make new solid
1094         TopoDS_Solid aSdx;
1095         //
1096         aBB.MakeSolid(aSdx);
1097         aItS.Initialize(aSd);
1098         for (; aItS.More(); aItS.Next()) {
1099           const TopoDS_Shape& aSh=aItS.Value();
1100           aBB.Add(aSdx, aSh);
1101         }
1102         //
1103         aBB.Add(aSdx, aSI);
1104         //
1105         // no need to check for images of aSd as aMSOr contains only original solids
1106         BOPCol_ListOfShape* pLS = myImages.Bound(aSd, BOPCol_ListOfShape());
1107         pLS->Append(aSdx);
1108         //
1109         BOPCol_ListOfShape* pLOr = myOrigins.Bound(aSdx, BOPCol_ListOfShape());
1110         pLOr->Append(aSd);
1111         //
1112         aMSOr.Remove(aSd);
1113         aSd=aSdx;
1114       }
1115       else {
1116         aBB.Add(aSd, aSI);
1117       }
1118       //
1119       aLSI.Remove(aIt1);
1120     }//for (; aIt1.More();) {
1121   }//for (; aIt.More(); aIt.Next()) {
1122   //
1123   //-----------------------------------------------------scope t
1124   aLArgs.Clear();
1125   aLSd.Clear();
1126   aMSOr.Clear();
1127   aMFence.Clear();
1128   aMSI.Clear();
1129   aMx.Clear();
1130   aMSx.Clear();
1131 }
1132 //=======================================================================
1133 //function : OwnInternalShapes
1134 //purpose  : 
1135 //=======================================================================
1136 void OwnInternalShapes(const TopoDS_Shape& theS,
1137                        BOPCol_IndexedMapOfShape& theMx)
1138 {
1139   TopoDS_Iterator aIt;
1140   //
1141   aIt.Initialize(theS);
1142   for (; aIt.More(); aIt.Next()) {
1143     const TopoDS_Shape& aSx=aIt.Value();
1144     if (aSx.ShapeType()!=TopAbs_SHELL) {
1145       theMx.Add(aSx);
1146     }
1147   }
1148 }
1149 //=======================================================================
1150 //function : TreatCompound
1151 //purpose  : 
1152 //=======================================================================
1153 void TreatCompound(const TopoDS_Shape& theS,
1154                    BOPCol_MapOfShape& aMFence,
1155                    BOPCol_ListOfShape& theLS)
1156 {
1157   TopAbs_ShapeEnum aType;
1158   //
1159   aType = theS.ShapeType();
1160   if (aType != TopAbs_COMPOUND) {
1161     if (aMFence.Add(theS)) {
1162       theLS.Append(theS);
1163     }
1164     return;
1165   }
1166   //
1167   TopoDS_Iterator aIt;
1168   //
1169   aIt.Initialize(theS);
1170   for (; aIt.More(); aIt.Next()) {
1171     const TopoDS_Shape& aS = aIt.Value();
1172     TreatCompound(aS, aMFence, theLS);
1173   }
1174 }