714708a5eedbfd7f53643d2f9e34ee7dc54ba4d0
[occt.git] / src / BOPAlgo / BOPAlgo_Tools.cxx
1 // Created by: Peter KURNEV
2 // Copyright (c) 1999-2014 OPEN CASCADE SAS
3 //
4 // This file is part of Open CASCADE Technology software library.
5 //
6 // This library is free software; you can redistribute it and/or modify it under
7 // the terms of the GNU Lesser General Public License version 2.1 as published
8 // by the Free Software Foundation, with special exception defined in the file
9 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
10 // distribution for complete text of the license and disclaimer of any warranty.
11 //
12 // Alternatively, this file may be used under the terms of Open CASCADE
13 // commercial license or contractual agreement.
14
15
16 #include <BOPAlgo_Tools.hxx>
17
18 #include <BOPAlgo_Builder.hxx>
19 #include <BOPAlgo_BuilderFace.hxx>
20 #include <BOPDS_CommonBlock.hxx>
21 #include <BOPDS_DataMapOfPaveBlockListOfPaveBlock.hxx>
22 #include <BOPDS_DS.hxx>
23 #include <BOPDS_IndexedMapOfPaveBlock.hxx>
24 #include <BOPDS_MapOfPaveBlock.hxx>
25 #include <BOPDS_PaveBlock.hxx>
26 #include <BOPTools_AlgoTools.hxx>
27 #include <BOPTools_AlgoTools2D.hxx>
28 #include <BOPTools_BoxTree.hxx>
29 #include <BOPTools_Parallel.hxx>
30 #include <BRep_Builder.hxx>
31 #include <BRep_Tool.hxx>
32 #include <BRepAdaptor_Curve.hxx>
33 #include <BRepBndLib.hxx>
34 #include <BRepBuilderAPI_MakeFace.hxx>
35 #include <BRepLib.hxx>
36 #include <Bnd_Tools.hxx>
37 #include <GeomAPI_ProjectPointOnCurve.hxx>
38 #include <GeomAPI_ProjectPointOnSurf.hxx>
39 #include <gp_Circ.hxx>
40 #include <gp_Dir.hxx>
41 #include <gp_Elips.hxx>
42 #include <gp_Hypr.hxx>
43 #include <gp_Parab.hxx>
44 #include <gp_Pln.hxx>
45 #include <gp_Pnt.hxx>
46 #include <gp_Vec.hxx>
47 #include <IntTools_Context.hxx>
48 #include <NCollection_IncAllocator.hxx>
49 #include <NCollection_Vector.hxx>
50 #include <Standard_ErrorHandler.hxx>
51 #include <Standard_Failure.hxx>
52 #include <TColStd_IndexedMapOfInteger.hxx>
53 #include <TopExp.hxx>
54 #include <TopExp_Explorer.hxx>
55 #include <TopoDS.hxx>
56 #include <TopoDS_Edge.hxx>
57 #include <TopTools_IndexedDataMapOfShapeListOfShape.hxx>
58 #include <TopTools_IndexedMapOfShape.hxx>
59 #include <TopTools_MapOfShape.hxx>
60
61 #include <algorithm>
62
63 typedef NCollection_IndexedDataMap
64   <TopoDS_Shape, gp_Dir, TopTools_ShapeMapHasher> BOPAlgo_IndexedDataMapOfShapeDir;
65 typedef NCollection_IndexedDataMap
66   <TopoDS_Shape, gp_Pln, TopTools_ShapeMapHasher> BOPAlgo_IndexedDataMapOfShapePln;
67
68 static
69   void MakeWires(const TopTools_IndexedMapOfShape& theEdges,
70                  TopoDS_Compound& theWires,
71                  const Standard_Boolean theCheckUniquePlane,
72                  BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
73                  TopTools_MapOfShape& theMEdgesNoUniquePlane);
74
75 static
76   Standard_Boolean FindPlane(const BRepAdaptor_Curve& theCurve,
77                              gp_Pln& thePlane);
78
79 static
80   Standard_Boolean FindPlane(const TopoDS_Shape& theWire,
81                              gp_Pln& thePlane,
82                              BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
83                              TopTools_MapOfShape& theMEdgesNoUniquePlane);
84
85 static
86   Standard_Boolean FindEdgeTangent(const TopoDS_Edge& theEdge,
87                                    BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
88                                    gp_Dir& theTgt);
89
90 static
91   Standard_Boolean FindEdgeTangent(const BRepAdaptor_Curve& theCurve,
92                                    gp_Vec& theTangent);
93
94 //=======================================================================
95 //function : FillMap
96 //purpose  : 
97 //=======================================================================
98 void BOPAlgo_Tools::FillMap(const Handle(BOPDS_PaveBlock)& aPB,
99                             const Standard_Integer nF,
100                             BOPDS_IndexedDataMapOfPaveBlockListOfInteger& aMPBLI,
101                             const Handle(NCollection_BaseAllocator)& aAllocator)
102 {
103   TColStd_ListOfInteger *pLI = aMPBLI.ChangeSeek(aPB);
104   if (!pLI) {
105     pLI = &aMPBLI(aMPBLI.Add(aPB, TColStd_ListOfInteger(aAllocator)));
106   }
107   pLI->Append(nF);
108 }
109 //=======================================================================
110 //function : PerformCommonBlocks
111 //purpose  : 
112 //=======================================================================
113 void BOPAlgo_Tools::PerformCommonBlocks(BOPDS_IndexedDataMapOfPaveBlockListOfPaveBlock& aMPBLPB,
114                                         const Handle(NCollection_BaseAllocator)& aAllocator,
115                                         BOPDS_PDS& pDS,
116                                         const Handle(IntTools_Context)& theContext)
117 {
118   Standard_Integer aNbCB;
119   //
120   aNbCB=aMPBLPB.Extent();
121   if (!aNbCB) {
122     return;
123   }
124   // Make Blocks of the pave blocks
125   NCollection_List<BOPDS_ListOfPaveBlock> aMBlocks(aAllocator);
126   BOPAlgo_Tools::MakeBlocks<Handle(BOPDS_PaveBlock), TColStd_MapTransientHasher>(aMPBLPB, aMBlocks, aAllocator);
127
128   // Use temporary allocator for the local fence map
129   Handle(NCollection_IncAllocator) anAllocTmp = new NCollection_IncAllocator;
130
131   NCollection_List<BOPDS_ListOfPaveBlock>::Iterator aItB(aMBlocks);
132   for (; aItB.More(); aItB.Next()) {
133     const BOPDS_ListOfPaveBlock& aLPB = aItB.Value();
134     Standard_Integer aNbPB = aLPB.Extent();
135     if (aNbPB < 2)
136       continue;
137
138     // Reset the allocator
139     anAllocTmp->Reset();
140     // New common block
141     Handle(BOPDS_CommonBlock) aCB;
142     // Faces of the common block
143     TColStd_ListOfInteger aLFaces;
144     // Fence map to avoid duplicates in the list of faces of the common block
145     TColStd_MapOfInteger aMFaces(1, anAllocTmp);
146
147     BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPB);
148     for (; aItLPB.More(); aItLPB.Next())
149     {
150       const Handle(BOPDS_PaveBlock)& aPB = aItLPB.Value();
151       if (pDS->IsCommonBlock(aPB))
152       {
153         const Handle(BOPDS_CommonBlock)& aCBx = pDS->CommonBlock(aPB);
154         // Move all faces to the new common block
155         TColStd_ListIteratorOfListOfInteger aItLF(aCBx->Faces());
156         for (; aItLF.More(); aItLF.Next())
157         {
158           const Standard_Integer nF = aItLF.Value();
159           // Append to common list avoiding duplicates
160           if (aMFaces.Add(nF))
161             aLFaces.Append(nF);
162         }
163         if (aCB.IsNull())
164           aCB = aCBx;
165       }
166     }
167
168     if (aCB.IsNull())
169       aCB = new BOPDS_CommonBlock;
170
171     aCB->SetPaveBlocks(aLPB);
172     aCB->SetFaces(aLFaces);
173     for (aItLPB.Initialize(aLPB); aItLPB.More(); aItLPB.Next())
174       pDS->SetCommonBlock(aItLPB.Value(), aCB);
175
176     // Compute tolerance for Common Block
177     Standard_Real aTolCB = BOPAlgo_Tools::ComputeToleranceOfCB(aCB, pDS, theContext);
178     aCB->SetTolerance(aTolCB);
179   }
180 }
181 //=======================================================================
182 //function : PerformCommonBlocks
183 //purpose  : 
184 //=======================================================================
185 void BOPAlgo_Tools::PerformCommonBlocks(const BOPDS_IndexedDataMapOfPaveBlockListOfInteger& aMPBLI,
186                                         const Handle(NCollection_BaseAllocator)& ,//aAllocator
187                                         BOPDS_PDS& pDS,
188                                         const Handle(IntTools_Context)& theContext)
189 {
190   Standard_Integer nF, i, aNb;
191   TColStd_ListIteratorOfListOfInteger aItLI;
192   Handle(BOPDS_PaveBlock) aPB;
193   Handle(BOPDS_CommonBlock) aCB;
194   //
195   aNb=aMPBLI.Extent();
196   for (i=1; i<=aNb; ++i) {
197     aPB=aMPBLI.FindKey(i);
198     if (pDS->IsCommonBlock(aPB)) {
199       aCB=pDS->CommonBlock(aPB);
200     }
201     else {
202       aCB=new BOPDS_CommonBlock;
203       aCB->AddPaveBlock(aPB);
204     }
205     //
206     const TColStd_ListOfInteger& aLI=aMPBLI.FindFromKey(aPB);
207     TColStd_ListOfInteger aNewFaces;
208     const TColStd_ListOfInteger& anOldFaces = aCB->Faces();
209     aItLI.Initialize(aLI);
210     for (; aItLI.More(); aItLI.Next()) {
211       nF=aItLI.Value();
212       // the both lists aLI and anOldFaces are expected to be short,
213       // so we can allow to run nested loop here
214       TColStd_ListIteratorOfListOfInteger it(anOldFaces);
215       for (; it.More(); it.Next()) {
216         if (it.Value() == nF)
217           break;
218       }
219       if (!it.More()) {
220         aNewFaces.Append(nF);
221       }
222     }
223     aCB->AppendFaces(aNewFaces);
224     pDS->SetCommonBlock(aPB, aCB);
225     // Compute tolerance for Common Block
226     Standard_Real aTolCB = BOPAlgo_Tools::ComputeToleranceOfCB(aCB, pDS, theContext);
227     aCB->SetTolerance(aTolCB);
228   }
229 }
230 //=======================================================================
231 //function : ComputeToleranceOfCB
232 //purpose  : 
233 //=======================================================================
234 Standard_Real BOPAlgo_Tools::ComputeToleranceOfCB
235                    (const Handle(BOPDS_CommonBlock)& theCB,
236                     const BOPDS_PDS theDS,
237                     const Handle(IntTools_Context)& theContext)
238 {
239   Standard_Real aTolMax = 0.;
240   if (theCB.IsNull()) {
241     return aTolMax;
242   }
243   //
244   const Handle(BOPDS_PaveBlock)& aPBR = theCB->PaveBlock1();
245   Standard_Integer nE = aPBR->OriginalEdge();
246   const TopoDS_Edge& aEOr = *(TopoDS_Edge*)&theDS->Shape(nE);
247   aTolMax = BRep_Tool::Tolerance(aEOr);
248   //
249   const BOPDS_ListOfPaveBlock& aLPB = theCB->PaveBlocks();
250   const TColStd_ListOfInteger& aLFI = theCB->Faces();
251   //
252   if ((aLPB.Extent() < 2) && aLFI.IsEmpty()) {
253     return aTolMax;
254   }
255   //
256   const Standard_Integer aNbPnt = 11;
257   Standard_Real aTol, aT, aT1, aT2, aDt;
258   gp_Pnt aP;
259   //
260   const Handle(Geom_Curve)& aC3D = BRep_Tool::Curve(aEOr, aT1, aT2);
261   //
262   aPBR->Range(aT1, aT2);
263   aDt = (aT2 - aT1) / (aNbPnt + 1);
264   //
265   Handle(IntTools_Context) aCtx = theContext;
266   if (aCtx.IsNull())
267     aCtx = new IntTools_Context();
268
269   // compute max tolerance for common blocks on edges
270   if (aLPB.Extent() > 1) {
271     // compute max distance between edges
272     BOPDS_ListIteratorOfListOfPaveBlock aItPB;
273     GeomAPI_ProjectPointOnCurve aProjPC;
274     //
275     aItPB.Initialize(aLPB);
276     for (; aItPB.More(); aItPB.Next()) {
277       const Handle(BOPDS_PaveBlock)& aPB = aItPB.Value();
278       if (aPB == aPBR) {
279         continue;
280       }
281       //
282       nE = aPB->OriginalEdge();
283       const TopoDS_Edge& aE = *(TopoDS_Edge*)&theDS->Shape(nE);
284       aTol = BRep_Tool::Tolerance(aE);
285       //
286       aProjPC = aCtx->ProjPC(aE);
287       //
288       aT = aT1;
289       for (Standard_Integer i=1; i <= aNbPnt; i++) {
290         aT += aDt;
291         aC3D->D0(aT, aP);
292         aProjPC.Perform(aP);
293         if (aProjPC.NbPoints()) {
294           Standard_Real aTolNew = aTol + aProjPC.LowerDistance();
295           if (aTolNew > aTolMax) {
296             aTolMax = aTolNew;
297           }
298         }
299       }
300     }
301   }
302   //
303   // compute max tolerance for common blocks on faces
304   if (aLFI.Extent()) {
305     Standard_Integer nF;
306     GeomAPI_ProjectPointOnSurf aProjPS;
307     TColStd_ListIteratorOfListOfInteger aItLI;
308     //
309     aItLI.Initialize(aLFI);
310     for (; aItLI.More(); aItLI.Next()) {
311       nF = aItLI.Value();
312       const TopoDS_Face& aF = *(TopoDS_Face*)&theDS->Shape(nF);
313       aTol = BRep_Tool::Tolerance(aF);
314       //
315       aProjPS = aCtx->ProjPS(aF);
316       //
317       aT = aT1;
318       for (Standard_Integer i=1; i <= aNbPnt; i++) {
319         aT += aDt;
320         aC3D->D0(aT, aP);
321         aProjPS.Perform(aP);
322         if (aProjPS.NbPoints()) {
323           Standard_Real aTolNew = aTol + aProjPS.LowerDistance();
324           if (aTolNew > aTolMax) {
325             aTolMax = aTolNew;
326           }
327         }
328       }
329     }
330   }
331   //
332   return aTolMax;
333 }
334
335 //=======================================================================
336 //function : EdgesToWires
337 //purpose  : 
338 //=======================================================================
339 Standard_Integer BOPAlgo_Tools::EdgesToWires(const TopoDS_Shape& theEdges,
340                                              TopoDS_Shape& theWires,
341                                              const Standard_Boolean theShared,
342                                              const Standard_Real theAngTol)
343 {
344   Standard_Integer iErr = 0;
345   //
346   // 1. Check the input edges
347   //
348   // List of edges to process
349   TopTools_ListOfShape aLE;
350   //
351   TopExp_Explorer aExp(theEdges, TopAbs_EDGE);
352   for (; aExp.More(); aExp.Next()) {
353     const TopoDS_Edge& aE = TopoDS::Edge(aExp.Current());
354     if (!BRep_Tool::Degenerated(aE) && BRep_Tool::IsGeometric(aE)) {
355       aLE.Append(aExp.Current());
356     }
357   }
358   //
359   if (aLE.IsEmpty()) {
360     // no edges to process
361     iErr = 1;
362     return iErr;
363   }
364   //
365   BRep_Builder aBB;
366   TopoDS_Compound aRWires;
367   aBB.MakeCompound(aRWires);
368   //
369   if (aLE.Extent() == 1) {
370     TopoDS_Wire aWire;
371     aBB.MakeWire(aWire);
372     aBB.Add(aWire, aLE.First());
373     aBB.Add(aRWires, aWire);
374     theWires = aRWires;
375     return iErr;
376   }
377   //
378   // 2. Make compound of shared edges
379   TopoDS_Shape aSEdges;
380   //
381   if (!theShared) {
382     // intersect the edges if necessary
383     BOPAlgo_Builder aGF;
384     aGF.SetArguments(aLE);
385     aGF.Perform();
386     if (aGF.HasErrors()) {
387       // unable to share the edges
388       iErr = 2;
389       return iErr;
390     }
391     //
392     aSEdges = aGF.Shape();
393   }
394   else {
395     aBB.MakeCompound(TopoDS::Compound(aSEdges));
396     TopTools_ListIteratorOfListOfShape aItLE(aLE);
397     for (; aItLE.More(); aItLE.Next()) {
398       aBB.Add(aSEdges, aItLE.Value());
399     }
400   }
401   //
402   // 3. Find edges located in the same planes and make wires from them.
403   // If the plane cannot be found for a single edge, then it is necessary
404   // to find all pairs of connected edges with the same cross product.
405
406   // Try to compute the plane in which the edge is located
407   BOPAlgo_IndexedDataMapOfShapePln aDMEdgePln;
408   // Compute the tangent direction for the edges for which the plane is not defined
409   BOPAlgo_IndexedDataMapOfShapeDir aDMEdgeTgt;
410   //
411   // edges for which the plane is not found
412   TopTools_MapOfShape aMEdgesNoUniquePlane;
413   //
414   // edges for which the plane cannot be found on a single edge
415   TopoDS_Compound aLEdges;
416   aBB.MakeCompound(aLEdges);
417   //
418   aExp.Init(aSEdges, TopAbs_EDGE);
419   for (; aExp.More(); aExp.Next()) {
420     const TopoDS_Edge& aE = TopoDS::Edge(aExp.Current());
421     BRepAdaptor_Curve aBAC(aE);
422     //
423     gp_Pln aPln;
424     if (FindPlane(aBAC, aPln)) {
425       aDMEdgePln.Add(aE, aPln);
426     }
427     else {
428       gp_Vec aVT;
429       if (FindEdgeTangent(aBAC, aVT)) {
430         aDMEdgeTgt.Add(aE, gp_Dir(aVT));
431         aBB.Add(aLEdges, aE);
432         aMEdgesNoUniquePlane.Add(aE);
433       }
434     }
435   }
436   //
437   typedef NCollection_List<gp_Dir> BOPAlgo_ListOfDir;
438   //
439   // to avoid processing of the same edges in the same plane store
440   // the processed planes into a list and use it as a fence map
441   BOPAlgo_ListOfDir aLPFence;
442   //
443   // used edges
444   TopTools_MapOfShape aMEFence;
445   //
446   // look for a planes on the single edges
447   Standard_Integer i, j, aNbPlanes = aDMEdgePln.Extent(), aNbEdges = aDMEdgeTgt.Extent();
448   for (i = 1; i <= aNbPlanes; ++i) {
449     const TopoDS_Shape& aEI = aDMEdgePln.FindKey(i);
450     if (!aMEFence.Add(aEI)) {
451       continue;
452     }
453     //
454     const gp_Pln& aPlnI = aDMEdgePln(i);
455     const gp_Dir& aDI = aPlnI.Position().Direction();
456     //
457     aLPFence.Append(aDI);
458     //
459     TopTools_IndexedMapOfShape aMEPln;
460     aMEPln.Add(aEI);
461     //
462     TopTools_IndexedMapOfShape aMV;
463     TopExp::MapShapes(aEI, TopAbs_VERTEX, aMV);
464     //
465     // look for other edges with the plane parallel to current one
466     for (j = i + 1; j <= aNbPlanes; ++j) {
467       const gp_Dir& aDJ = aDMEdgePln(j).Position().Direction();
468       if (aDI.IsParallel(aDJ, theAngTol)) {
469         const TopoDS_Shape& aEJ = aDMEdgePln.FindKey(j);
470         aMEPln.Add(aEJ);
471         aMEFence.Add(aEJ);
472         TopExp::MapShapes(aEJ, TopAbs_VERTEX, aMV);
473       }
474     }
475     //
476     // look for all other edges located in the plane parallel to current one
477     TopoDS_Compound aCEPln;
478     aBB.MakeCompound(aCEPln);
479     //
480     for (j = 1; j <= aNbEdges; ++j) {
481       const gp_Dir& aDJ = aDMEdgeTgt(j);
482       if (aDI.IsNormal(aDJ, theAngTol)) {
483         aBB.Add(aCEPln, aDMEdgeTgt.FindKey(j));
484       }
485     }
486     //
487     // make blocks of these edges and check blocks to be connected
488     // to any of the already added edges or forming a wire themselves
489     TopTools_ListOfShape aLCBE;
490     BOPTools_AlgoTools::MakeConnexityBlocks(aCEPln, TopAbs_VERTEX, TopAbs_EDGE, aLCBE);
491     //
492     // make wire from each block
493     TopTools_ListIteratorOfListOfShape aItLCB(aLCBE);
494     for (; aItLCB.More(); aItLCB.Next()) {
495       const TopoDS_Shape& aCBE = aItLCB.Value();
496       //
497       // check connectivity
498       TopExp_Explorer aExpV(aCBE, TopAbs_VERTEX);
499       for (; aExpV.More(); aExpV.Next()) {
500         if (aMV.Contains(aExpV.Current())) {
501           break;
502         }
503       }
504       //
505       Standard_Boolean bAddBlock = aExpV.More();
506       if (!bAddBlock) {
507         // check if the edges are forming a wire
508         gp_Pln aPln;
509         bAddBlock = FindPlane(aCBE, aPln, aDMEdgeTgt, aMEdgesNoUniquePlane);
510       }
511       //
512       if (bAddBlock) {
513         // add edges
514         for (TopoDS_Iterator aItE(aCBE); aItE.More(); aItE.Next()) {
515           aMEPln.Add(aItE.Value());
516         }
517       }
518     }
519     //
520     MakeWires(aMEPln, aRWires, Standard_False, aDMEdgeTgt, aMEdgesNoUniquePlane);
521   }
522   //
523   // make connection map from vertices to edges to find the connected pairs
524   TopTools_IndexedDataMapOfShapeListOfShape aDMVE;
525   TopExp::MapShapesAndAncestors(aLEdges, TopAbs_VERTEX, TopAbs_EDGE, aDMVE);
526   //
527   // find planes for connected edges
528   Standard_Integer aNbV = aDMVE.Extent();
529   for (i = 1; i <= aNbV; ++i) {
530     const TopTools_ListOfShape& aLEI = aDMVE(i);
531     if (aLEI.Extent() < 2) {
532       continue;
533     }
534     //
535     TopTools_ListIteratorOfListOfShape aItLEI1(aLEI);
536     for (; aItLEI1.More(); aItLEI1.Next()) {
537       const TopoDS_Shape& aEI1 = aItLEI1.Value();
538       const gp_Dir& aDI1 = aDMEdgeTgt.FindFromKey(aEI1);
539       //
540       TopTools_ListIteratorOfListOfShape aItLEI2(aLEI);
541       for (; aItLEI2.More(); aItLEI2.Next()) {
542         const TopoDS_Shape& aEI2 = aItLEI2.Value();
543         if (aEI2.IsSame(aEI1)) {
544           continue;
545         }
546         //
547         const gp_Dir& aDI2 = aDMEdgeTgt.FindFromKey(aEI2);
548         //
549         if (aDI1.IsParallel(aDI2, theAngTol)) {
550           continue;
551         }
552         //
553         gp_Dir aDNI = aDI1^aDI2;
554         //
555         // check if this normal direction has not been checked yet
556         BOPAlgo_ListOfDir::Iterator aItLPln(aLPFence);
557         for (; aItLPln.More(); aItLPln.Next()) {
558           if (aDNI.IsParallel(aItLPln.Value(), theAngTol)) {
559             break;
560           }
561         }
562         if (aItLPln.More()) {
563           continue;
564         }
565         //
566         aLPFence.Append(aDNI);
567         //
568         // find all other edges in the plane parallel to current one
569         TopTools_IndexedMapOfShape aMEPln;
570         aMEPln.Add(aEI1);
571         aMEPln.Add(aEI2);
572         //
573         // iterate on all other edges to find all edges lying in the plane parallel to current one
574         for (j = 1; j <= aNbEdges; ++j) {
575           const gp_Dir& aDJ = aDMEdgeTgt(j);
576           if (aDNI.IsNormal(aDJ, theAngTol)) {
577             aMEPln.Add(aDMEdgeTgt.FindKey(j));
578           }
579         }
580         //
581         MakeWires(aMEPln, aRWires, Standard_True, aDMEdgeTgt, aMEdgesNoUniquePlane);
582       } // for (; aItLEI2.More(); aItLEI2.Next()) {
583     } // for (; aItLEI1.More(); aItLEI1.Next()) {
584   } // for (i = 1; i < aNb; ++i) {
585   //
586   // 4. Find unused edges and make wires from them
587   TopTools_IndexedMapOfShape aMEAlone, aMEUsed;
588   TopExp::MapShapes(aRWires, TopAbs_EDGE, aMEUsed);
589   //
590   for (i = 1; i <= aNbEdges; ++i) {
591     const TopoDS_Shape& aE = aDMEdgeTgt.FindKey(i);
592     if (!aMEUsed.Contains(aE)) {
593       aMEAlone.Add(aE);
594     }
595   }
596   //
597   MakeWires(aMEAlone, aRWires, Standard_False, aDMEdgeTgt, aMEdgesNoUniquePlane);
598   //
599   theWires = aRWires;
600   //
601   return iErr;
602 }
603
604 //=======================================================================
605 //function : WiresToFaces
606 //purpose  : 
607 //=======================================================================
608 Standard_Boolean BOPAlgo_Tools::WiresToFaces(const TopoDS_Shape& theWires,
609                                              TopoDS_Shape& theFaces,
610                                              const Standard_Real theAngTol)
611 {
612   BRep_Builder aBB;
613   TopTools_MapOfShape aMFence;
614   TopoDS_Compound aRFaces;
615   aBB.MakeCompound(aRFaces);
616   //
617   const Standard_Real aMax = 1.e+8;
618   //
619   // map to store the tangent vectors for the edges
620   BOPAlgo_IndexedDataMapOfShapeDir aDMEdgeTgt;
621   // maps to store the planes found for the wires
622   BOPAlgo_IndexedDataMapOfShapePln aDMWirePln;
623   // map to store the tolerance for the wire
624   NCollection_DataMap<TopoDS_Shape, Standard_Real, TopTools_ShapeMapHasher> aDMWireTol;
625   // edges for which the plane is not found
626   TopTools_MapOfShape aMEdgesNoUniquePlane;
627   //
628   // Find planes for the wires
629   TopExp_Explorer aExpW(theWires, TopAbs_WIRE);
630   for (; aExpW.More(); aExpW.Next()) {
631     const TopoDS_Wire& aWire = TopoDS::Wire(aExpW.Current());
632     gp_Pln aPlane;
633     if (FindPlane(aWire, aPlane, aDMEdgeTgt, aMEdgesNoUniquePlane)) {
634       aDMWirePln.Add(aWire, aPlane);
635       // find tolerance for the wire - max tolerance of its edges
636       aDMWireTol.Bind(aWire, BRep_Tool::MaxTolerance(aWire, TopAbs_EDGE));
637     }
638   }
639   //
640   Standard_Integer i, j, aNb = aDMWirePln.Extent();
641   for (i = 1; i <= aNb; ++i) {
642     const TopoDS_Shape& aWireI = aDMWirePln.FindKey(i);
643     if (aMFence.Contains(aWireI)) {
644       continue;
645     }
646     //
647     const gp_Pln& aPlnI = aDMWirePln(i);
648     //
649     TopTools_ListOfShape aLW;
650     aLW.Append(aWireI);
651     aMFence.Add(aWireI);
652     //
653     Standard_Real aTolI = aDMWireTol.Find(aWireI);
654     //
655     // Find other wires in the same plane
656     for (j = i + 1; j <= aNb; ++j) {
657       const TopoDS_Shape& aWireJ = aDMWirePln.FindKey(j);
658       if (aMFence.Contains(aWireJ)) {
659         continue;
660       }
661       //
662       // check if the planes are the same
663       const gp_Pln& aPlnJ = aDMWirePln(j);
664       // check direction of the planes
665       if (!aPlnI.Position().Direction().IsParallel(aPlnJ.Position().Direction(), theAngTol)) {
666         continue;
667       }
668       // check distance between the planes
669       Standard_Real aDist = aPlnI.Distance(aPlnJ.Location());
670       Standard_Real aTolJ = aDMWireTol.Find(aWireJ);
671       if (aDist > (aTolI + aTolJ)) {
672         continue;
673       }
674       //
675       aLW.Append(aWireJ);
676       aMFence.Add(aWireJ);
677     }
678     //
679     // Take the edges to build the face
680     TopTools_ListOfShape aLE;
681     TopTools_ListIteratorOfListOfShape aItLW(aLW);
682     for (; aItLW.More(); aItLW.Next()) {
683       TopoDS_Iterator aItE(aItLW.Value());
684       for (; aItE.More(); aItE.Next()) {
685         aLE.Append(aItE.Value().Oriented(TopAbs_FORWARD));
686         aLE.Append(aItE.Value().Oriented(TopAbs_REVERSED));
687       }
688     }
689     //
690     // build planar face
691     TopoDS_Face aFF = BRepBuilderAPI_MakeFace
692       (aPlnI, -aMax, aMax, -aMax, aMax).Face();
693     aFF.Orientation(TopAbs_FORWARD);
694     //
695     try {
696       OCC_CATCH_SIGNALS
697       //
698       // build pcurves for edges on this face
699       BRepLib::BuildPCurveForEdgesOnPlane(aLE, aFF);
700       //
701       // split the face with the edges
702       BOPAlgo_BuilderFace aBF;
703       aBF.SetShapes(aLE);
704       aBF.SetFace(aFF);
705       aBF.Perform();
706       if (aBF.HasErrors()) {
707         continue;
708       }
709       //
710       const TopTools_ListOfShape& aLFSp = aBF.Areas();
711       TopTools_ListIteratorOfListOfShape aItLF(aLFSp);
712       for (; aItLF.More(); aItLF.Next()) {
713         const TopoDS_Shape& aFSp = aItLF.ChangeValue();
714         aBB.Add(aRFaces, aFSp);
715       }
716     }
717     catch (Standard_Failure const&) {
718       continue;
719     }
720   }
721   //
722   // fix tolerances of the resulting faces
723   TopTools_IndexedMapOfShape aMEmpty;
724   BOPTools_AlgoTools::CorrectTolerances(aRFaces, aMEmpty, 0.05, Standard_False);
725   BOPTools_AlgoTools::CorrectShapeTolerances(aRFaces, aMEmpty, Standard_False);
726   //
727   theFaces = aRFaces;
728   return theFaces.NbChildren() > 0;
729 }
730
731 //=======================================================================
732 //function : MakeWires
733 //purpose  : Makes wires from the separate blocks of the given edges
734 //=======================================================================
735 void MakeWires(const TopTools_IndexedMapOfShape& theEdges,
736                TopoDS_Compound& theWires,
737                const Standard_Boolean theCheckUniquePlane,
738                BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
739                TopTools_MapOfShape& theMEdgesNoUniquePlane)
740 {
741   TopoDS_Compound aCE;
742   BRep_Builder().MakeCompound(aCE);
743   Standard_Integer i, aNbE = theEdges.Extent();
744   for (i = 1; i <= aNbE; ++i) {
745     BRep_Builder().Add(aCE, theEdges(i));
746   }
747   //
748   TopTools_ListOfShape aLCBE;
749   BOPTools_AlgoTools::MakeConnexityBlocks(aCE, TopAbs_VERTEX, TopAbs_EDGE, aLCBE);
750   //
751   // make wire from each block
752   TopTools_ListIteratorOfListOfShape aItLCB(aLCBE);
753   for (; aItLCB.More(); aItLCB.Next()) {
754     const TopoDS_Shape& aCBE = aItLCB.Value();
755     //
756     if (theCheckUniquePlane) {
757       gp_Pln aPln;
758       if (!FindPlane(aCBE, aPln, theDMEdgeTgt, theMEdgesNoUniquePlane)) {
759         continue;
760       }
761     }
762     //
763     TopoDS_Wire aWire;
764     BRep_Builder().MakeWire(aWire);
765     for (TopoDS_Iterator aItE(aCBE); aItE.More(); aItE.Next()) {
766       BRep_Builder().Add(aWire, aItE.Value());
767     }
768     //
769     BRep_Builder().Add(theWires, aWire);
770   }
771 }
772
773 //=======================================================================
774 //function : FindEdgeTangent
775 //purpose  : Finds the tangent for the edge using the map
776 //=======================================================================
777 Standard_Boolean FindEdgeTangent(const TopoDS_Edge& theEdge,
778                                  BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
779                                  gp_Dir& theTgt)
780 {
781   gp_Dir *pDTE = theDMEdgeTgt.ChangeSeek(theEdge);
782   if (!pDTE) {
783     gp_Vec aVTE;
784     BRepAdaptor_Curve aBAC(theEdge);
785     if (!FindEdgeTangent(aBAC, aVTE)) {
786       return Standard_False;
787     }
788     pDTE = &theDMEdgeTgt(theDMEdgeTgt.Add(theEdge, gp_Dir(aVTE)));
789   }
790   theTgt = *pDTE;
791   return Standard_True;
792 }
793
794 //=======================================================================
795 //function : FindEdgeTangent
796 //purpose  : Finds the tangent for the edge
797 //=======================================================================
798 Standard_Boolean FindEdgeTangent(const BRepAdaptor_Curve& theCurve,
799                                  gp_Vec& theTangent)
800 {
801   if (!theCurve.Is3DCurve()) {
802     return Standard_False;
803   }
804   // for the line the tangent is defined by the direction
805   if (theCurve.GetType() == GeomAbs_Line) {
806     theTangent = theCurve.Line().Position().Direction();
807     return Standard_True;
808   }
809   //
810   // for other curves take D1 and check for its length
811   Standard_Real aT, aT1(theCurve.FirstParameter()), aT2(theCurve.LastParameter());
812   const Standard_Integer aNbP = 11;
813   const Standard_Real aDt = (aT2 - aT1) / aNbP;
814   //
815   for (aT = aT1 + aDt; aT <= aT2; aT += aDt) {
816     gp_Pnt aP;
817     theCurve.D1(aT, aP, theTangent);
818     if (theTangent.Magnitude() > Precision::Confusion()) {
819       return Standard_True;
820     }
821   }
822   //
823   return Standard_False;
824 }
825
826 //=======================================================================
827 //function : FindPlane
828 //purpose  : Finds the plane in which the edge is located
829 //=======================================================================
830 Standard_Boolean FindPlane(const BRepAdaptor_Curve& theCurve,
831                            gp_Pln& thePlane)
832 {
833   if (!theCurve.Is3DCurve()) {
834     return Standard_False;
835   }
836   //
837   Standard_Boolean bFound = Standard_True;
838   gp_Vec aVN;
839   switch (theCurve.GetType()) {
840     case GeomAbs_Line:
841       return Standard_False;
842     case GeomAbs_Circle:
843       aVN = theCurve.Circle().Position().Direction();
844       break;
845     case GeomAbs_Ellipse:
846       aVN = theCurve.Ellipse().Position().Direction();
847       break;
848     case GeomAbs_Hyperbola:
849       aVN = theCurve.Hyperbola().Position().Direction();
850       break;
851     case GeomAbs_Parabola:
852       aVN = theCurve.Parabola().Position().Direction();
853       break;
854     default: {
855       // for all other types of curve compute two tangent vectors
856       // on the curve and cross them
857       bFound = Standard_False;
858       Standard_Real aT, aT1(theCurve.FirstParameter()), aT2(theCurve.LastParameter());
859       const Standard_Integer aNbP = 11;
860       const Standard_Real aDt = (aT2 - aT1) / aNbP;
861       //
862       aT = aT1;
863       gp_Pnt aP1;
864       gp_Vec aV1;
865       theCurve.D1(aT, aP1, aV1);
866       //
867       for (aT = aT1 + aDt; aT <= aT2; aT += aDt) {
868         gp_Pnt aP2;
869         gp_Vec aV2;
870         theCurve.D1(aT, aP2, aV2);
871         //
872         aVN = aV1^aV2;
873         if (aVN.Magnitude() > Precision::Confusion()) {
874           bFound = Standard_True;
875           break;
876         }
877       }
878       break;
879     }
880   }
881   //
882   if (bFound) {
883     thePlane = gp_Pln(theCurve.Value(theCurve.FirstParameter()), gp_Dir(aVN));
884   }
885   return bFound;
886 }
887
888 //=======================================================================
889 //function : FindPlane
890 //purpose  : Finds the plane in which the wire is located
891 //=======================================================================
892 Standard_Boolean FindPlane(const TopoDS_Shape& theWire,
893                            gp_Pln& thePlane,
894                            BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
895                            TopTools_MapOfShape& theMEdgesNoUniquePlane)
896 {
897   TopExp_Explorer aExpE1(theWire, TopAbs_EDGE);
898   if (!aExpE1.More()) {
899     return Standard_False;
900   }
901   //
902   // try to find two not parallel edges in wire to get normal of the plane
903   for (; aExpE1.More(); aExpE1.Next()) {
904     // get the first edge in the wire
905     const TopoDS_Edge& aE1 = TopoDS::Edge(aExpE1.Current());
906     //
907     // find tangent for the first edge
908     gp_Dir aDTE1;
909     if (!FindEdgeTangent(aE1, theDMEdgeTgt, aDTE1)) {
910       continue;
911     }
912     //
913     // find the other edge not parallel to the first one
914     TopExp_Explorer aExpE2(theWire, TopAbs_EDGE);
915     for (; aExpE2.More(); aExpE2.Next()) {
916       const TopoDS_Edge& aE2 = TopoDS::Edge(aExpE2.Current());
917       if (aE1.IsSame(aE2)) {
918         continue;
919       }
920       //
921       // find tangent for the second edge
922       gp_Dir aDTE2;
923       if (!FindEdgeTangent(aE2, theDMEdgeTgt, aDTE2)) {
924         continue;
925       }
926       //
927       if (aDTE1.IsParallel(aDTE2, Precision::Angular())) {
928         continue;
929       }
930       //
931       gp_Dir aDN = aDTE1^aDTE2;
932       //
933       TopoDS_Iterator aItV(aE1);
934       thePlane = gp_Pln(BRep_Tool::Pnt(TopoDS::Vertex(aItV.Value())), aDN);
935       return Standard_True;
936     }
937   }
938   //
939   // try to compute normal on the single edge
940   aExpE1.Init(theWire, TopAbs_EDGE);
941   for (; aExpE1.More(); aExpE1.Next()) {
942     const TopoDS_Edge& aE = TopoDS::Edge(aExpE1.Current());
943     if (theMEdgesNoUniquePlane.Contains(aE)) {
944       continue;
945     }
946     BRepAdaptor_Curve aBAC(aE);
947     if (FindPlane(aBAC, thePlane)) {
948       return Standard_True;
949     }
950     theMEdgesNoUniquePlane.Add(aE);
951   }
952   return Standard_False;
953 }
954
955 /////////////////////////////////////////////////////////////////////////
956 //=======================================================================
957 //class    : BOPAlgo_PairVerticesSelector
958 //purpose  : 
959 //=======================================================================
960 class BOPAlgo_PairVerticesSelector : public BOPTools_BoxPairSelector
961 {
962 public:
963
964   BOPAlgo_PairVerticesSelector()
965     : myVertices(NULL),
966       myFuzzyValue(Precision::Confusion())
967   {}
968
969   //! Sets the map of vertices with tolerances
970   void SetMapOfVerticesTolerances (const TopTools_IndexedDataMapOfShapeReal& theVertices)
971   {
972     myVertices = &theVertices;
973   }
974
975   //! Sets the fuzzy value
976   void SetFuzzyValue (const Standard_Real theFuzzyValue)
977   {
978     myFuzzyValue = theFuzzyValue;
979   }
980
981   //! Checks and accepts the pair of elements.
982   virtual Standard_Boolean Accept (const Standard_Integer theID1,
983                                    const Standard_Integer theID2) Standard_OVERRIDE
984   {
985     if (!RejectElement (theID1, theID2))
986     {
987       const Standard_Integer anID1 = this->myBVHSet1->Element (theID1);
988       const TopoDS_Vertex& aV1 = TopoDS::Vertex (myVertices->FindKey (anID1));
989       Standard_Real aTolV1 = BRep_Tool::Tolerance (aV1);
990       if (aTolV1 < myVertices->FindFromIndex (anID1))
991         aTolV1 = myVertices->FindFromIndex (anID1);
992       gp_Pnt aP1 = BRep_Tool::Pnt (aV1);
993
994       const Standard_Integer anID2 = this->myBVHSet1->Element (theID2);
995       const TopoDS_Vertex& aV2 = TopoDS::Vertex (myVertices->FindKey (anID2));
996       Standard_Real aTolV2 = BRep_Tool::Tolerance (aV2);
997       if (aTolV2 < myVertices->FindFromIndex (anID2))
998         aTolV2 = myVertices->FindFromIndex (anID2);
999       gp_Pnt aP2 = BRep_Tool::Pnt (aV2);
1000
1001       Standard_Real aTolSum2 = aTolV1 + aTolV2 + myFuzzyValue;
1002       aTolSum2 *= aTolSum2;
1003
1004       Standard_Real aD2 = aP1.SquareDistance (aP2);
1005       if (aD2 < aTolSum2)
1006       {
1007         myPairs.push_back (PairIDs (anID1, anID2));
1008         return Standard_True;
1009       }
1010     }
1011     return Standard_False;
1012   }
1013
1014 protected:
1015   const TopTools_IndexedDataMapOfShapeReal * myVertices;
1016   Standard_Real myFuzzyValue;
1017 };
1018 //
1019 /////////////////////////////////////////////////////////////////////////
1020
1021 //=======================================================================
1022 //function : IntersectVertices
1023 //purpose  : Builds the chains of intersecting vertices
1024 //=======================================================================
1025 void BOPAlgo_Tools::IntersectVertices(const TopTools_IndexedDataMapOfShapeReal& theVertices,
1026                                       const Standard_Real theFuzzyValue,
1027                                       TopTools_ListOfListOfShape& theChains)
1028 {
1029   Standard_Integer aNbV = theVertices.Extent();
1030   if (aNbV <= 1) {
1031     if (aNbV == 1) {
1032       theChains.Append(TopTools_ListOfShape()).Append(theVertices.FindKey(1));
1033     }
1034     return;
1035   }
1036
1037   // Additional tolerance for intersection
1038   Standard_Real aTolAdd = theFuzzyValue / 2.;
1039
1040   // Use BVH Tree for sorting the vertices
1041   BOPTools_BoxTree aBBTree;
1042   aBBTree.SetSize (aNbV);
1043
1044   for (Standard_Integer i = 1; i <= aNbV; ++i)
1045   {
1046     const TopoDS_Vertex& aV = TopoDS::Vertex(theVertices.FindKey(i));
1047     Standard_Real aTol = BRep_Tool::Tolerance(aV);
1048     if (aTol < theVertices(i))
1049       aTol = theVertices(i);
1050
1051     // Build bnd box for vertex
1052     Bnd_Box aBox;
1053     aBox.Add(BRep_Tool::Pnt(aV));
1054     aBox.SetGap(aTol + aTolAdd);
1055     aBBTree.Add(i, Bnd_Tools::Bnd2BVH(aBox));
1056   }
1057
1058   aBBTree.Build();
1059
1060   // Perform selection of the interfering vertices
1061   BOPAlgo_PairVerticesSelector aPairSelector;
1062   aPairSelector.SetBVHSets (&aBBTree, &aBBTree);
1063   aPairSelector.SetSame (Standard_True);
1064   aPairSelector.SetMapOfVerticesTolerances (theVertices);
1065   aPairSelector.SetFuzzyValue (theFuzzyValue);
1066   aPairSelector.Select();
1067
1068   // Treat the selected pairs
1069   const std::vector<BOPTools_BoxPairSelector::PairIDs>& aPairs = aPairSelector.Pairs();
1070   const Standard_Integer aNbPairs = static_cast<Standard_Integer> (aPairs.size());
1071
1072   // Collect interfering pairs
1073   Handle(NCollection_IncAllocator) anAlloc = new NCollection_IncAllocator;
1074   NCollection_IndexedDataMap<Standard_Integer, TColStd_ListOfInteger> aMILI (1, anAlloc);
1075
1076   for (Standard_Integer iPair = 0; iPair < aNbPairs; ++iPair)
1077   {
1078     const BOPTools_BoxPairSelector::PairIDs& aPair = aPairs[iPair];
1079     BOPAlgo_Tools::FillMap<Standard_Integer, TColStd_MapIntegerHasher> (aPair.ID1, aPair.ID2, aMILI, anAlloc);
1080   }
1081
1082   NCollection_List<TColStd_ListOfInteger> aBlocks (anAlloc);
1083   BOPAlgo_Tools::MakeBlocks<Standard_Integer, TColStd_MapIntegerHasher> (aMILI, aBlocks, anAlloc);
1084
1085   NCollection_List<TColStd_ListOfInteger>::Iterator itLI (aBlocks);
1086   for (; itLI.More(); itLI.Next())
1087   {
1088     const TColStd_ListOfInteger& aLI = itLI.Value();
1089     TopTools_ListOfShape &aChain = theChains.Append (TopTools_ListOfShape());
1090     
1091     for (TColStd_ListOfInteger::Iterator itI (aLI); itI.More(); itI.Next())
1092       aChain.Append (theVertices.FindKey (itI.Value()));
1093   }
1094
1095   // Add not interfered vertices as a chain of 1 element
1096   for (Standard_Integer i = 1; i <= aNbV; ++i)
1097   {
1098     if (!aMILI.Contains (i))
1099     {
1100       TopTools_ListOfShape &aChain = theChains.Append (TopTools_ListOfShape());
1101       aChain.Append (theVertices.FindKey(i));
1102     }
1103   }
1104 }
1105
1106 //=======================================================================
1107 //function : TreatCompound
1108 //purpose  : 
1109 //=======================================================================
1110 void BOPAlgo_Tools::TreatCompound(const TopoDS_Shape& theS,
1111                                   TopTools_MapOfShape& aMFence,
1112                                   TopTools_ListOfShape& theLS)
1113 {
1114   TopAbs_ShapeEnum aType = theS.ShapeType();
1115   if (aType != TopAbs_COMPOUND)
1116   {
1117     if (aMFence.Add(theS))
1118       theLS.Append(theS);
1119     return;
1120   }
1121   TopoDS_Iterator aIt(theS);
1122   for (; aIt.More(); aIt.Next())
1123   {
1124     const TopoDS_Shape& aS = aIt.Value();
1125     TreatCompound(aS, aMFence, theLS);
1126   }
1127 }
1128
1129 //=======================================================================
1130 // Classification of the faces relatively solids
1131 //=======================================================================
1132
1133 //=======================================================================
1134 //class     : BOPAlgo_ShapeBox
1135 //purpose   : Auxiliary class defining ShapeBox structure
1136 //=======================================================================
1137 class BOPAlgo_ShapeBox
1138 {
1139 public:
1140   //! Empty constructor
1141   BOPAlgo_ShapeBox() {};
1142   //! Sets the shape
1143   void SetShape(const TopoDS_Shape& theS)
1144   {
1145     myShape = theS;
1146   };
1147   //! Returns the shape
1148   const TopoDS_Shape& Shape() const
1149   {
1150     return myShape;
1151   };
1152   //! Sets the bounding box
1153   void SetBox(const Bnd_Box& theBox)
1154   {
1155     myBox = theBox;
1156   };
1157   //! Returns the bounding box
1158   const Bnd_Box& Box() const
1159   {
1160     return myBox;
1161   };
1162 private:
1163   TopoDS_Shape myShape;
1164   Bnd_Box myBox;
1165 };
1166 // Vector of ShapeBox
1167 typedef NCollection_Vector<BOPAlgo_ShapeBox> BOPAlgo_VectorOfShapeBox;
1168
1169 //=======================================================================
1170 //class : BOPAlgo_FillIn3DParts
1171 //purpose : Auxiliary class for faces classification in parallel mode
1172 //=======================================================================
1173 class BOPAlgo_FillIn3DParts : public BOPAlgo_Algo
1174 {
1175 public:
1176   DEFINE_STANDARD_ALLOC
1177
1178   //! Constructor
1179   BOPAlgo_FillIn3DParts()
1180   {
1181     myBBTree = NULL;
1182     myVShapeBox = NULL;
1183   };
1184
1185   //! Destructor
1186   virtual ~BOPAlgo_FillIn3DParts() {};
1187
1188   //! Sets the solid
1189   void SetSolid(const TopoDS_Solid& theSolid)
1190   {
1191     mySolid = theSolid;
1192   };
1193
1194   //! Returns the solid
1195   const TopoDS_Solid& Solid() const
1196   {
1197     return mySolid;
1198   };
1199
1200   //! Sets the box for the solid
1201   void SetBoxS(const Bnd_Box& theBox)
1202   {
1203     myBoxS = theBox;
1204   };
1205
1206   //! Returns the solid's box
1207   const Bnd_Box& BoxS() const
1208   {
1209     return myBoxS;
1210   };
1211
1212   //! Sets own INTERNAL faces of the solid
1213   void SetOwnIF(const TopTools_ListOfShape& theLIF)
1214   {
1215     myOwnIF = theLIF;
1216   };
1217
1218   //! Returns own INTERNAL faces of the solid
1219   const TopTools_ListOfShape& OwnIF() const
1220   {
1221     return myOwnIF;
1222   };
1223
1224   //! Sets the Bounding Box tree
1225   void SetBBTree(BOPTools_BoxTree* theBBTree)
1226   {
1227     myBBTree = theBBTree;
1228   };
1229
1230   //! Sets the ShapeBox structure
1231   void SetShapeBoxVector(const BOPAlgo_VectorOfShapeBox& theShapeBox)
1232   {
1233     myVShapeBox = (BOPAlgo_VectorOfShapeBox*)&theShapeBox;
1234   };
1235
1236   //! Sets the context
1237   void SetContext(const Handle(IntTools_Context)& theContext)
1238   {
1239     myContext = theContext;
1240   }
1241
1242   //! Returns the context
1243   const Handle(IntTools_Context)& Context() const
1244   {
1245     return myContext;
1246   }
1247
1248   //! Performs the classification
1249   virtual void Perform();
1250
1251   //! Returns the faces classified as IN for solid
1252   const TopTools_ListOfShape& InFaces() const
1253   {
1254     return myInFaces;
1255   };
1256
1257 private:
1258
1259   //! Prepares Edge-Face connection map of the given shape
1260   void MapEdgesAndFaces(const TopoDS_Shape& theF,
1261                         TopTools_IndexedDataMapOfShapeListOfShape& theEFMap,
1262                         const Handle(NCollection_BaseAllocator)& theAlloc);
1263
1264   //! Makes the connexity block of faces using the connection map
1265   void MakeConnexityBlock(const TopoDS_Face& theF,
1266                           const TopTools_IndexedMapOfShape& theMEToAvoid,
1267                           const TopTools_IndexedDataMapOfShapeListOfShape& theEFMap,
1268                           TopTools_MapOfShape& theMFDone,
1269                           TopTools_ListOfShape& theLCB,
1270                           TopoDS_Face& theFaceToClassify);
1271
1272   TopoDS_Solid mySolid; //! Solid
1273   Bnd_Box myBoxS; // Bounding box of the solid
1274   TopTools_ListOfShape myOwnIF; //! Own INTERNAL faces of the solid
1275   TopTools_ListOfShape myInFaces; //! Faces classified as IN
1276
1277   BOPTools_BoxTree* myBBTree; //! BVH tree of bounding boxes
1278   BOPAlgo_VectorOfShapeBox* myVShapeBox; //! ShapeBoxMap
1279
1280   TopoDS_Iterator myItF; //! Iterators
1281   TopoDS_Iterator myItW;
1282
1283   Handle(IntTools_Context) myContext; //! Context
1284 };
1285
1286 //=======================================================================
1287 //function : BOPAlgo_FillIn3DParts::Perform
1288 //purpose  : 
1289 //=======================================================================
1290 void BOPAlgo_FillIn3DParts::Perform()
1291 {
1292   BOPAlgo_Algo::UserBreak();
1293
1294   myInFaces.Clear();
1295
1296   // 1. Select boxes of faces that are not out of aBoxS
1297   BOPTools_BoxTreeSelector aSelector;
1298   aSelector.SetBox(Bnd_Tools::Bnd2BVH(myBoxS));
1299   aSelector.SetBVHSet (myBBTree);
1300   //
1301   if (!aSelector.Select())
1302     return;
1303
1304   const TColStd_ListOfInteger& aLIFP = aSelector.Indices();
1305
1306   // 2. Fill maps of edges and faces of the solid
1307
1308   Handle(NCollection_BaseAllocator) anAlloc = new NCollection_IncAllocator;
1309
1310   BOPAlgo_VectorOfShapeBox& aVShapeBox = *myVShapeBox;
1311
1312   TopTools_IndexedMapOfShape aMSE(1, anAlloc), aMSF(1, anAlloc);
1313   TopExp::MapShapes(mySolid, TopAbs_EDGE, aMSE);
1314   TopExp::MapShapes(mySolid, TopAbs_FACE, aMSF);
1315
1316   // Check if the Solid contains any faces
1317   Standard_Boolean bIsEmpty = aMSF.IsEmpty();
1318
1319   // Add own internal faces of the solid into aMSF
1320   TopTools_ListIteratorOfListOfShape aItLS(myOwnIF);
1321   for (; aItLS.More(); aItLS.Next())
1322     aMSF.Add(aItLS.Value());
1323
1324   // 3. aIVec - faces to process.
1325   //    Filter the selected faces with faces of the solid.
1326   NCollection_Vector<Standard_Integer> aIVec(256, anAlloc);
1327
1328   TColStd_ListIteratorOfListOfInteger aItLI(aLIFP);
1329   for (; aItLI.More(); aItLI.Next()) {
1330     Standard_Integer nFP = aItLI.Value();
1331     const TopoDS_Shape& aFP = aVShapeBox(nFP).Shape();
1332     if (!aMSF.Contains(aFP))
1333       aIVec.Appended() = nFP;
1334   }
1335
1336   // 4. Classify faces relatively solid.
1337   //    Store faces that are IN mySolid into <myInFaces>
1338
1339   Standard_Integer k, aNbFP = aIVec.Length();
1340   // Sort indices if necessary
1341   if (aNbFP > 1)
1342     std::sort(aIVec.begin(), aIVec.end());
1343
1344   if (bIsEmpty)
1345   {
1346     // The solid is empty as it does not contain any faces.
1347     // It could happen when the input solid consists of INTERNAL faces only.
1348     // Classification of any point relatively empty solid would always give IN status.
1349     // Thus, we consider all selected faces as IN without real classification.
1350     for (k = 0; k < aNbFP; ++k)
1351       myInFaces.Append(aVShapeBox(aIVec(k)).Shape());
1352
1353     return;
1354   }
1355
1356   // Prepare EF map of faces to process for building connexity blocks
1357   TopTools_IndexedDataMapOfShapeListOfShape aMEFP(1, anAlloc);
1358   if (aNbFP > 1)
1359   {
1360     for (k = 0; k < aNbFP; ++k)
1361       MapEdgesAndFaces(aVShapeBox(aIVec(k)).Shape(), aMEFP, anAlloc);
1362   }
1363
1364   // Map of Edge-Face connection, necessary for solid classification.
1365   // It will be filled when first classification is performed.
1366   TopTools_IndexedDataMapOfShapeListOfShape aMEFDS(1, anAlloc);
1367
1368   // Fence map to avoid processing of the same faces twice
1369   TopTools_MapOfShape aMFDone(1, anAlloc);
1370
1371   for (k = 0; k < aNbFP; ++k)
1372   {
1373     Standard_Integer nFP = aIVec(k);
1374     const TopoDS_Face& aFP = (*(TopoDS_Face*)&aVShapeBox(nFP).Shape());
1375     if (!aMFDone.Add(aFP))
1376       continue;
1377
1378     // Make connexity blocks of faces, avoiding passing through the
1379     // borders of the solid. It helps to reduce significantly the
1380     // number of classified faces.
1381     TopTools_ListOfShape aLCBF(anAlloc);
1382     // The most appropriate face for classification
1383     TopoDS_Face aFaceToClassify;
1384     MakeConnexityBlock(aFP, aMSE, aMEFP, aMFDone, aLCBF, aFaceToClassify);
1385
1386     if (!myBoxS.IsWhole())
1387     {
1388       // First, try fast classification of the whole block by additional
1389       // check on bounding boxes - check that bounding boxes of all vertices
1390       // of the block interfere with the box of the solid.
1391       // If not, the faces are out.
1392       Standard_Boolean bOut = Standard_False;
1393       aItLS.Initialize(aLCBF);
1394       for (; aItLS.More() && !bOut; aItLS.Next())
1395       {
1396         TopExp_Explorer anExpV(aItLS.Value(), TopAbs_VERTEX);
1397         for (; anExpV.More() && !bOut; anExpV.Next())
1398         {
1399           const TopoDS_Vertex& aV = TopoDS::Vertex(anExpV.Current());
1400           Bnd_Box aBBV;
1401           aBBV.Add(BRep_Tool::Pnt(aV));
1402           aBBV.SetGap(BRep_Tool::Tolerance(aV));
1403           bOut = myBoxS.IsOut(aBBV);
1404         }
1405       }
1406       if (bOut)
1407         continue;
1408     }
1409
1410     if (aFaceToClassify.IsNull())
1411       aFaceToClassify = aFP;
1412
1413     if (aMEFDS.IsEmpty())
1414       // Fill EF map for Solid
1415       TopExp::MapShapesAndAncestors(mySolid, TopAbs_EDGE, TopAbs_FACE, aMEFDS);
1416
1417     // All vertices are interfere with the solids box, run classification.
1418     Standard_Boolean bIsIN = BOPTools_AlgoTools::IsInternalFace
1419       (aFaceToClassify, mySolid, aMEFDS, Precision::Confusion(), myContext);
1420     if (bIsIN)
1421     {
1422       aItLS.Initialize(aLCBF);
1423       for (; aItLS.More(); aItLS.Next())
1424         myInFaces.Append(aItLS.Value());
1425     }
1426   }
1427 }
1428 //=======================================================================
1429 // function: MapEdgesAndFaces
1430 // purpose: 
1431 //=======================================================================
1432 void BOPAlgo_FillIn3DParts::MapEdgesAndFaces(const TopoDS_Shape& theF,
1433                                              TopTools_IndexedDataMapOfShapeListOfShape& theEFMap,
1434                                              const Handle(NCollection_BaseAllocator)& theAllocator)
1435 {
1436   myItF.Initialize(theF);
1437   for (; myItF.More(); myItF.Next())
1438   {
1439     const TopoDS_Shape& aW = myItF.Value();
1440     if (aW.ShapeType() != TopAbs_WIRE)
1441       continue;
1442
1443     myItW.Initialize(aW);
1444     for (; myItW.More(); myItW.Next())
1445     {
1446       const TopoDS_Shape& aE = myItW.Value();
1447
1448       TopTools_ListOfShape* pLF = theEFMap.ChangeSeek(aE);
1449       if (!pLF)
1450         pLF = &theEFMap(theEFMap.Add(aE, TopTools_ListOfShape(theAllocator)));
1451       pLF->Append(theF);
1452     }
1453   }
1454 }
1455 //=======================================================================
1456 // function: MakeConnexityBlock
1457 // purpose: 
1458 //=======================================================================
1459 void BOPAlgo_FillIn3DParts::MakeConnexityBlock(const TopoDS_Face& theFStart,
1460                                                const TopTools_IndexedMapOfShape& theMEAvoid,
1461                                                const TopTools_IndexedDataMapOfShapeListOfShape& theEFMap,
1462                                                TopTools_MapOfShape& theMFDone,
1463                                                TopTools_ListOfShape& theLCB,
1464                                                TopoDS_Face& theFaceToClassify)
1465 {
1466   // Add start element
1467   theLCB.Append(theFStart);
1468   if (theEFMap.IsEmpty())
1469     return;
1470
1471   TopTools_ListIteratorOfListOfShape aItCB(theLCB);
1472   for (; aItCB.More(); aItCB.Next())
1473   {
1474     const TopoDS_Shape& aF = aItCB.Value();
1475     myItF.Initialize(aF);
1476     for (; myItF.More(); myItF.Next())
1477     {
1478       const TopoDS_Shape& aW = myItF.Value();
1479       if (aW.ShapeType() != TopAbs_WIRE)
1480         continue;
1481
1482       myItW.Initialize(aW);
1483       for (; myItW.More(); myItW.Next())
1484       {
1485         const TopoDS_Edge& aE = TopoDS::Edge(myItW.Value());
1486         if (theMEAvoid.Contains(aE) || BRep_Tool::Degenerated(aE))
1487         {
1488           if (theFaceToClassify.IsNull())
1489             theFaceToClassify = TopoDS::Face(aF);
1490           continue;
1491         }
1492
1493         const TopTools_ListOfShape* pLF = theEFMap.Seek(aE);
1494         if (!pLF)
1495           continue;
1496         TopTools_ListIteratorOfListOfShape aItLF(*pLF);
1497         for (; aItLF.More(); aItLF.Next())
1498         {
1499           const TopoDS_Shape& aFToAdd = aItLF.Value();
1500           if (theMFDone.Add(aFToAdd))
1501             theLCB.Append(aFToAdd);
1502         }
1503       }
1504     }
1505   }
1506 }
1507
1508 // Vector of solid classifiers
1509 typedef NCollection_Vector<BOPAlgo_FillIn3DParts> BOPAlgo_VectorOfFillIn3DParts;
1510
1511 //=======================================================================
1512 //function : ClassifyFaces
1513 //purpose  :
1514 //=======================================================================
1515 void BOPAlgo_Tools::ClassifyFaces(const TopTools_ListOfShape& theFaces,
1516                                   const TopTools_ListOfShape& theSolids,
1517                                   const Standard_Boolean theRunParallel,
1518                                   Handle(IntTools_Context)& theContext,
1519                                   TopTools_IndexedDataMapOfShapeListOfShape& theInParts,
1520                                   const TopTools_DataMapOfShapeBox& theShapeBoxMap,
1521                                   const TopTools_DataMapOfShapeListOfShape& theSolidsIF)
1522 {
1523   Handle(NCollection_BaseAllocator) anAlloc = new NCollection_IncAllocator;
1524
1525   // Fill the vector of shape box with faces and its bounding boxes
1526   BOPAlgo_VectorOfShapeBox aVSB(256, anAlloc);
1527
1528   TopTools_ListIteratorOfListOfShape aItLF(theFaces);
1529   for (; aItLF.More(); aItLF.Next())
1530   {
1531     const TopoDS_Shape& aF = aItLF.Value();
1532     // Append face to the vector of shape box
1533     BOPAlgo_ShapeBox& aSB = aVSB.Appended();
1534     aSB.SetShape(aF);
1535
1536     // Get bounding box for the face
1537     const Bnd_Box* pBox = theShapeBoxMap.Seek(aF);
1538     if (pBox)
1539       aSB.SetBox(*pBox);
1540     else
1541     {
1542       // Build the bounding box
1543       Bnd_Box aBox;
1544       BRepBndLib::Add(aF, aBox);
1545       aSB.SetBox(aBox);
1546     }
1547   }
1548
1549   // Prepare BVH tree of bounding boxes of the faces to classify
1550   // taking the bounding boxes from the just prepared vector
1551   BOPTools_BoxTree aBBTree;
1552   Standard_Integer aNbF = aVSB.Length();
1553   aBBTree.SetSize (aNbF);
1554   for (Standard_Integer i = 0; i < aNbF; ++i)
1555   {
1556     aBBTree.Add(i, Bnd_Tools::Bnd2BVH(aVSB(i).Box()));
1557   }
1558
1559   // Shake tree filler
1560   aBBTree.Build();
1561
1562   // Prepare vector of solids to classify
1563   BOPAlgo_VectorOfFillIn3DParts aVFIP;
1564
1565   TopTools_ListIteratorOfListOfShape aItLS(theSolids);
1566   for (; aItLS.More(); aItLS.Next())
1567   {
1568     const TopoDS_Solid& aSolid = TopoDS::Solid(aItLS.Value());
1569     // Append solid to the vector
1570     BOPAlgo_FillIn3DParts& aFIP = aVFIP.Appended();
1571     aFIP.SetSolid(aSolid);
1572
1573     // Get bounding box for the solid
1574     const Bnd_Box* pBox = theShapeBoxMap.Seek(aSolid);
1575     if (pBox)
1576       aFIP.SetBoxS(*pBox);
1577     else
1578     {
1579       // Build the bounding box
1580       Bnd_Box aBox;
1581       BRepBndLib::Add(aSolid, aBox);
1582       if (!aBox.IsWhole())
1583       {
1584         if (BOPTools_AlgoTools::IsInvertedSolid(aSolid))
1585           aBox.SetWhole();
1586       }
1587       aFIP.SetBoxS(aBox);
1588     }
1589
1590     const TopTools_ListOfShape* pLIF = theSolidsIF.Seek(aSolid);
1591     if (pLIF)
1592       aFIP.SetOwnIF(*pLIF);
1593
1594     aFIP.SetBBTree(&aBBTree);
1595     aFIP.SetShapeBoxVector(aVSB);
1596   }
1597
1598   // Perform classification
1599   //================================================================
1600   BOPTools_Parallel::Perform (theRunParallel, aVFIP, theContext);
1601   //================================================================
1602
1603   // Analyze the results and fill the resulting map
1604
1605   Standard_Integer aNbS = aVFIP.Length();
1606   for (Standard_Integer i = 0; i < aNbS; ++i)
1607   {
1608     BOPAlgo_FillIn3DParts& aFIP = aVFIP(i);
1609     const TopoDS_Shape& aS = aFIP.Solid();
1610     const TopTools_ListOfShape& aLFIn = aFIP.InFaces();
1611     theInParts.Add(aS, aLFIn);
1612   }
1613 }
1614
1615 //=======================================================================
1616 //function : FillInternals
1617 //purpose  :
1618 //=======================================================================
1619 void BOPAlgo_Tools::FillInternals(const TopTools_ListOfShape& theSolids,
1620                                   const TopTools_ListOfShape& theParts,
1621                                   const TopTools_DataMapOfShapeListOfShape& theImages,
1622                                   const Handle(IntTools_Context)& theContext)
1623 {
1624   if (theSolids.IsEmpty() || theParts.IsEmpty())
1625     return;
1626
1627   // Map the solids to avoid classification of the own shapes of the solids
1628   TopTools_IndexedMapOfShape aMSSolids;
1629   TopTools_ListOfShape::Iterator itLS(theSolids);
1630   for (; itLS.More(); itLS.Next())
1631   {
1632     const TopoDS_Shape& aSolid = itLS.Value();
1633     if (aSolid.ShapeType() == TopAbs_SOLID)
1634     {
1635       TopExp::MapShapes(aSolid, TopAbs_VERTEX, aMSSolids);
1636       TopExp::MapShapes(aSolid, TopAbs_EDGE,   aMSSolids);
1637       TopExp::MapShapes(aSolid, TopAbs_FACE,   aMSSolids);
1638     }
1639   }
1640
1641   // Extract BRep elements from the given parts and
1642   // check them for possible splits
1643   TopTools_ListOfShape aLPartsInput = theParts, aLParts;
1644   TopTools_ListOfShape::Iterator itLP(aLPartsInput);
1645   for (; itLP.More(); itLP.Next())
1646   {
1647     const TopoDS_Shape& aPart = itLP.Value();
1648     switch (aPart.ShapeType())
1649     {
1650       case TopAbs_VERTEX:
1651       case TopAbs_EDGE:
1652       case TopAbs_FACE:
1653       {
1654         const TopTools_ListOfShape* pIm = theImages.Seek(aPart);
1655         if (pIm)
1656         {
1657           TopTools_ListOfShape::Iterator itIm(*pIm);
1658           for (; itIm.More(); itIm.Next())
1659           {
1660             const TopoDS_Shape& aPartIm = itIm.Value();
1661             if (!aMSSolids.Contains(aPartIm))
1662               aLParts.Append(aPartIm);
1663           }
1664         }
1665         else if (!aMSSolids.Contains(aPart))
1666           aLParts.Append(aPart);
1667
1668         break;
1669       }
1670       default:
1671       {
1672         for (TopoDS_Iterator it(aPart); it.More(); it.Next())
1673           aLPartsInput.Append(it.Value());
1674         break;
1675       }
1676     }
1677   }
1678
1679   // Classify the given parts relatively solids.
1680   // Add edges and vertices classified as IN into solids instantly,
1681   // and collect faces classified as IN into a list for further shell creation
1682
1683   TopTools_DataMapOfShapeListOfShape anINFaces;
1684   itLS.Initialize(theSolids);
1685   for (; itLS.More(); itLS.Next())
1686   {
1687     const TopoDS_Shape& aSolid = itLS.Value();
1688     if (aSolid.ShapeType() != TopAbs_SOLID)
1689       continue;
1690
1691     TopoDS_Solid aSd = *(TopoDS_Solid*)&aSolid;
1692
1693     itLP.Initialize(aLParts);
1694     for (; itLP.More();)
1695     {
1696       TopoDS_Shape aPart = itLP.Value();
1697       TopAbs_State aState =
1698         BOPTools_AlgoTools::ComputeStateByOnePoint(aPart, aSd, Precision::Confusion(), theContext);
1699       if (aState == TopAbs_IN)
1700       {
1701         if (aPart.ShapeType() == TopAbs_FACE)
1702         {
1703           TopTools_ListOfShape *pFaces = anINFaces.ChangeSeek(aSd);
1704           if (!pFaces)
1705             pFaces = anINFaces.Bound(aSd, TopTools_ListOfShape());
1706           pFaces->Append(aPart);
1707         }
1708         else
1709         {
1710           aPart.Orientation(TopAbs_INTERNAL);
1711           BRep_Builder().Add(aSd, aPart);
1712         }
1713         aLParts.Remove(itLP);
1714       }
1715       else
1716         itLP.Next();
1717     }
1718   }
1719
1720   // Make shells from faces and put them into solids
1721   TopTools_DataMapOfShapeListOfShape::Iterator itM(anINFaces);
1722   for (; itM.More(); itM.Next())
1723   {
1724     TopoDS_Solid aSd = *(TopoDS_Solid*)&itM.Key();
1725     const TopTools_ListOfShape& aFaces = itM.Value();
1726
1727     TopoDS_Compound aCF;
1728     BRep_Builder().MakeCompound(aCF);
1729
1730     TopTools_ListOfShape::Iterator itLF(aFaces);
1731     for (; itLF.More(); itLF.Next())
1732       BRep_Builder().Add(aCF, itLF.Value());
1733
1734     // Build blocks from the faces
1735     TopTools_ListOfShape aLCB;
1736     BOPTools_AlgoTools::MakeConnexityBlocks(aCF, TopAbs_EDGE, TopAbs_FACE, aLCB);
1737
1738     // Build shell from each block
1739     TopTools_ListOfShape::Iterator itCB(aLCB);
1740     for (; itCB.More(); itCB.Next())
1741     {
1742       const TopoDS_Shape& aCB = itCB.Value();
1743
1744       TopoDS_Shell aShell;
1745       BRep_Builder().MakeShell(aShell);
1746       // Add faces of the block to the shell
1747       TopExp_Explorer expF(aCB, TopAbs_FACE);
1748       for (; expF.More(); expF.Next())
1749       {
1750         TopoDS_Face aFInt = TopoDS::Face(expF.Current());
1751         aFInt.Orientation(TopAbs_INTERNAL);
1752         BRep_Builder().Add(aShell, aFInt);
1753       }
1754
1755       BRep_Builder().Add(aSd, aShell);
1756     }
1757   }
1758 }
1759
1760 //=======================================================================
1761 //function : TrsfToPoint
1762 //purpose  :
1763 //=======================================================================
1764 Standard_Boolean BOPAlgo_Tools::TrsfToPoint (const Bnd_Box& theBox1,
1765                                              const Bnd_Box& theBox2,
1766                                              gp_Trsf&       theTrsf,
1767                                              const gp_Pnt&  thePoint,
1768                                              const Standard_Real theCriteria)
1769 {
1770   // Unify two boxes
1771   Bnd_Box aBox = theBox1;
1772   aBox.Add (theBox2);
1773
1774   gp_XYZ aBCenter = (aBox.CornerMin().XYZ() + aBox.CornerMax().XYZ()) / 2.;
1775   Standard_Real aPBDist = (thePoint.XYZ() - aBCenter).Modulus();
1776   if (aPBDist < theCriteria)
1777     return Standard_False;
1778   
1779   Standard_Real aBSize = Sqrt (aBox.SquareExtent());
1780   if ((aBSize / aPBDist) > (1. / theCriteria))
1781     return Standard_False;
1782
1783   theTrsf.SetTranslation (gp_Vec (aBox.CornerMin(), thePoint));
1784   return Standard_True;
1785 }