0028259: Method MakeBlocksCnx is duplicated in two different places in BOPAlgo
[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 <gp_Pnt.hxx>
19 #include <gp_Vec.hxx>
20 #include <gp_Dir.hxx>
21 #include <gp_Pln.hxx>
22 #include <gp_Circ.hxx>
23 #include <gp_Elips.hxx>
24 #include <gp_Hypr.hxx>
25 #include <gp_Parab.hxx>
26
27 #include <Standard_ErrorHandler.hxx>
28 #include <Standard_Failure.hxx>
29
30 #include <TopoDS.hxx>
31 #include <TopoDS_Edge.hxx>
32
33 #include <BOPCol_MapOfShape.hxx>
34 #include <BOPCol_IndexedMapOfShape.hxx>
35 #include <BOPCol_IndexedMapOfInteger.hxx>
36 #include <BOPCol_IndexedDataMapOfShapeListOfShape.hxx>
37
38 #include <TopExp_Explorer.hxx>
39
40 #include <BRepAdaptor_Curve.hxx>
41
42 #include <BRepBuilderAPI_MakeFace.hxx>
43
44 #include <BRep_Tool.hxx>
45 #include <BRep_Builder.hxx>
46
47 #include <GeomAPI_ProjectPointOnCurve.hxx>
48 #include <GeomAPI_ProjectPointOnSurf.hxx>
49
50 #include <BOPAlgo_Builder.hxx>
51 #include <BOPAlgo_BuilderFace.hxx>
52
53 #include <BOPDS_CommonBlock.hxx>
54 #include <BOPDS_DataMapOfPaveBlockListOfPaveBlock.hxx>
55 #include <BOPDS_DS.hxx>
56 #include <BOPDS_IndexedMapOfPaveBlock.hxx>
57 #include <BOPDS_MapOfPaveBlock.hxx>
58 #include <BOPDS_PaveBlock.hxx>
59
60 #include <BOPTools.hxx>
61 #include <BOPTools_AlgoTools.hxx>
62 #include <BOPTools_AlgoTools2D.hxx>
63
64 #include <IntTools_Context.hxx>
65
66 typedef NCollection_IndexedDataMap
67   <TopoDS_Shape, gp_Dir, TopTools_ShapeMapHasher> BOPAlgo_IndexedDataMapOfShapeDir;
68 typedef NCollection_IndexedDataMap
69   <TopoDS_Shape, gp_Pln, TopTools_ShapeMapHasher> BOPAlgo_IndexedDataMapOfShapePln;
70
71 static
72   void MakeWires(const BOPCol_IndexedMapOfShape& theEdges,
73                  TopoDS_Compound& theWires,
74                  const Standard_Boolean theCheckUniquePlane,
75                  BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
76                  BOPCol_MapOfShape& theMEdgesNoUniquePlane);
77
78 static
79   Standard_Boolean FindPlane(const BRepAdaptor_Curve& theCurve,
80                              gp_Pln& thePlane);
81
82 static
83   Standard_Boolean FindPlane(const TopoDS_Shape& theWire,
84                              gp_Pln& thePlane,
85                              BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
86                              BOPCol_MapOfShape& theMEdgesNoUniquePlane);
87
88 static
89   Standard_Boolean FindEdgeTangent(const TopoDS_Edge& theEdge,
90                                    BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
91                                    gp_Dir& theTgt);
92
93 static
94   Standard_Boolean FindEdgeTangent(const BRepAdaptor_Curve& theCurve,
95                                    gp_Vec& theTangent);
96
97 //=======================================================================
98 //function : FillMap
99 //purpose  : 
100 //=======================================================================
101 void BOPAlgo_Tools::FillMap(const Handle(BOPDS_PaveBlock)& aPB,
102                             const Standard_Integer nF,
103                             BOPDS_IndexedDataMapOfPaveBlockListOfInteger& aMPBLI,
104                             const Handle(NCollection_BaseAllocator)& aAllocator)
105 {
106   BOPCol_ListOfInteger *pLI = aMPBLI.ChangeSeek(aPB);
107   if (!pLI) {
108     pLI = &aMPBLI(aMPBLI.Add(aPB, BOPCol_ListOfInteger(aAllocator)));
109   }
110   pLI->Append(nF);
111 }
112 //=======================================================================
113 //function : PerformCommonBlocks
114 //purpose  : 
115 //=======================================================================
116 void BOPAlgo_Tools::PerformCommonBlocks(BOPDS_IndexedDataMapOfPaveBlockListOfPaveBlock& aMPBLPB,
117                                         const Handle(NCollection_BaseAllocator)& aAllocator,
118                                         BOPDS_PDS& pDS)
119 {
120   Standard_Integer aNbCB;
121   //
122   aNbCB=aMPBLPB.Extent();
123   if (!aNbCB) {
124     return;
125   }
126   //
127   Handle(BOPDS_CommonBlock) aCB;
128   NCollection_List<BOPDS_ListOfPaveBlock> aMBlocks(aAllocator);
129   //
130   BOPAlgo_Tools::MakeBlocks<Handle(BOPDS_PaveBlock), TColStd_MapTransientHasher>(aMPBLPB, aMBlocks, aAllocator);
131   //
132   NCollection_List<BOPDS_ListOfPaveBlock>::Iterator aItB(aMBlocks);
133   for (; aItB.More(); aItB.Next()) {
134     const BOPDS_ListOfPaveBlock& aLPB = aItB.Value();
135     Standard_Integer aNbPB = aLPB.Extent();
136     if (aNbPB>1) {
137       aCB=new BOPDS_CommonBlock;
138       aCB->SetPaveBlocks(aLPB);
139       //
140       BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPB);
141       for (; aItLPB.More(); aItLPB.Next()) {
142         pDS->SetCommonBlock(aItLPB.Value(), aCB);
143       }
144     }//if (aNbPB>1) {
145   }
146 }
147 //=======================================================================
148 //function : PerformCommonBlocks
149 //purpose  : 
150 //=======================================================================
151 void BOPAlgo_Tools::PerformCommonBlocks(const BOPDS_IndexedDataMapOfPaveBlockListOfInteger& aMPBLI,
152                                         const Handle(NCollection_BaseAllocator)& ,//aAllocator
153                                         BOPDS_PDS& pDS)
154 {
155   Standard_Integer nF, i, aNb;
156   BOPCol_ListIteratorOfListOfInteger aItLI;
157   Handle(BOPDS_PaveBlock) aPB;
158   Handle(BOPDS_CommonBlock) aCB;
159   //
160   aNb=aMPBLI.Extent();
161   for (i=1; i<=aNb; ++i) {
162     aPB=aMPBLI.FindKey(i);
163     if (pDS->IsCommonBlock(aPB)) {
164       aCB=pDS->CommonBlock(aPB);
165     }
166     else {
167       aCB=new BOPDS_CommonBlock;
168       aCB->AddPaveBlock(aPB);
169     }
170     //
171     const BOPCol_ListOfInteger& aLI=aMPBLI.FindFromKey(aPB);
172     BOPCol_ListOfInteger aNewFaces;
173     const BOPCol_ListOfInteger& anOldFaces = aCB->Faces();
174     aItLI.Initialize(aLI);
175     for (; aItLI.More(); aItLI.Next()) {
176       nF=aItLI.Value();
177       // the both lists aLI and anOldFaces are expected to be short,
178       // so we can allow to run nested loop here
179       BOPCol_ListIteratorOfListOfInteger it(anOldFaces);
180       for (; it.More(); it.Next()) {
181         if (it.Value() == nF)
182           break;
183       }
184       if (!it.More()) {
185         aNewFaces.Append(nF);
186       }
187     }
188     aCB->AppendFaces(aNewFaces);
189     pDS->SetCommonBlock(aPB, aCB);
190   }
191 }
192 //=======================================================================
193 //function : ComputeToleranceOfCB
194 //purpose  : 
195 //=======================================================================
196 Standard_Real BOPAlgo_Tools::ComputeToleranceOfCB
197                    (const Handle(BOPDS_CommonBlock)& theCB,
198                     const BOPDS_PDS theDS,
199                     const Handle(IntTools_Context)& theContext)
200 {
201   Standard_Real aTolMax = 0.;
202   if (theCB.IsNull()) {
203     return aTolMax;
204   }
205   //
206   const Handle(BOPDS_PaveBlock)& aPBR = theCB->PaveBlock1();
207   Standard_Integer nE = aPBR->OriginalEdge();
208   const TopoDS_Edge& aEOr = *(TopoDS_Edge*)&theDS->Shape(nE);
209   aTolMax = BRep_Tool::Tolerance(aEOr);
210   //
211   const BOPDS_ListOfPaveBlock& aLPB = theCB->PaveBlocks();
212   const BOPCol_ListOfInteger& aLFI = theCB->Faces();
213   //
214   if ((aLPB.Extent() < 2) && aLFI.IsEmpty()) {
215     return aTolMax;
216   }
217   //
218   const Standard_Integer aNbPnt = 11;
219   Standard_Real aTol, aT, aT1, aT2, aDt;
220   gp_Pnt aP;
221   //
222   const Handle(Geom_Curve)& aC3D = BRep_Tool::Curve(aEOr, aT1, aT2);
223   //
224   aPBR->Range(aT1, aT2);
225   aDt = (aT2 - aT1) / (aNbPnt + 1);
226   //
227   // compute max tolerance for common blocks on edges
228   if (aLPB.Extent() > 1) {
229     // compute max distance between edges
230     BOPDS_ListIteratorOfListOfPaveBlock aItPB;
231     GeomAPI_ProjectPointOnCurve aProjPC;
232     //
233     aItPB.Initialize(aLPB);
234     for (; aItPB.More(); aItPB.Next()) {
235       const Handle(BOPDS_PaveBlock)& aPB = aItPB.Value();
236       if (aPB == aPBR) {
237         continue;
238       }
239       //
240       nE = aPB->OriginalEdge();
241       const TopoDS_Edge& aE = *(TopoDS_Edge*)&theDS->Shape(nE);
242       aTol = BRep_Tool::Tolerance(aE);
243       //
244       aProjPC = theContext->ProjPC(aE);
245       //
246       aT = aT1;
247       for (Standard_Integer i=1; i <= aNbPnt; i++) {
248         aT += aDt;
249         aC3D->D0(aT, aP);
250         aProjPC.Perform(aP);
251         if (aProjPC.NbPoints()) {
252           Standard_Real aTolNew = aTol + aProjPC.LowerDistance();
253           if (aTolNew > aTolMax) {
254             aTolMax = aTolNew;
255           }
256         }
257       }
258     }
259   }
260   //
261   // compute max tolerance for common blocks on faces
262   if (aLFI.Extent()) {
263     Standard_Integer nF;
264     GeomAPI_ProjectPointOnSurf aProjPS;
265     BOPCol_ListIteratorOfListOfInteger aItLI;
266     //
267     aItLI.Initialize(aLFI);
268     for (; aItLI.More(); aItLI.Next()) {
269       nF = aItLI.Value();
270       const TopoDS_Face& aF = *(TopoDS_Face*)&theDS->Shape(nF);
271       aTol = BRep_Tool::Tolerance(aF);
272       //
273       aProjPS = theContext->ProjPS(aF);
274       //
275       aT = aT1;
276       for (Standard_Integer i=1; i <= aNbPnt; i++) {
277         aT += aDt;
278         aC3D->D0(aT, aP);
279         aProjPS.Perform(aP);
280         if (aProjPS.NbPoints()) {
281           Standard_Real aTolNew = aTol + aProjPS.LowerDistance();
282           if (aTolNew > aTolMax) {
283             aTolMax = aTolNew;
284           }
285         }
286       }
287     }
288   }
289   //
290   return aTolMax;
291 }
292
293 //=======================================================================
294 //function : EdgesToWires
295 //purpose  : 
296 //=======================================================================
297 Standard_Integer BOPAlgo_Tools::EdgesToWires(const TopoDS_Shape& theEdges,
298                                              TopoDS_Shape& theWires,
299                                              const Standard_Boolean theShared,
300                                              const Standard_Real theAngTol)
301 {
302   Standard_Integer iErr = 0;
303   //
304   // 1. Check the input edges
305   //
306   // List of edges to process
307   BOPCol_ListOfShape aLE;
308   //
309   TopExp_Explorer aExp(theEdges, TopAbs_EDGE);
310   for (; aExp.More(); aExp.Next()) {
311     const TopoDS_Edge& aE = TopoDS::Edge(aExp.Current());
312     if (!BRep_Tool::Degenerated(aE) && BRep_Tool::IsGeometric(aE)) {
313       aLE.Append(aExp.Current());
314     }
315   }
316   //
317   if (aLE.IsEmpty()) {
318     // no edges to process
319     iErr = 1;
320     return iErr;
321   }
322   //
323   BRep_Builder aBB;
324   TopoDS_Compound aRWires;
325   aBB.MakeCompound(aRWires);
326   //
327   if (aLE.Extent() == 1) {
328     TopoDS_Wire aWire;
329     aBB.MakeWire(aWire);
330     aBB.Add(aWire, aLE.First());
331     aBB.Add(aRWires, aWire);
332     theWires = aRWires;
333     return iErr;
334   }
335   //
336   // 2. Make compound of shared edges
337   TopoDS_Shape aSEdges;
338   //
339   if (!theShared) {
340     // intersect the edges if necessary
341     BOPAlgo_Builder aGF;
342     aGF.SetArguments(aLE);
343     aGF.Perform();
344     if (aGF.ErrorStatus()) {
345       // unable to share the edges
346       iErr = 2;
347       return iErr;
348     }
349     //
350     aSEdges = aGF.Shape();
351   }
352   else {
353     aBB.MakeCompound(TopoDS::Compound(aSEdges));
354     BOPCol_ListIteratorOfListOfShape aItLE(aLE);
355     for (; aItLE.More(); aItLE.Next()) {
356       aBB.Add(aSEdges, aItLE.Value());
357     }
358   }
359   //
360   // 3. Find edges located in the same planes and make wires from them.
361   // If the plane cannot be found for a single edge, then it is necessary
362   // to find all pairs of connected edges with the same cross product.
363
364   // Try to compute the plane in which the edge is located
365   BOPAlgo_IndexedDataMapOfShapePln aDMEdgePln;
366   // Compute the tangent direction for the edges for which the plane is not defined
367   BOPAlgo_IndexedDataMapOfShapeDir aDMEdgeTgt;
368   //
369   // edges for which the plane is not found
370   BOPCol_MapOfShape aMEdgesNoUniquePlane;
371   //
372   // edges for which the plane cannot be found on a single edge
373   TopoDS_Compound aLEdges;
374   aBB.MakeCompound(aLEdges);
375   //
376   aExp.Init(aSEdges, TopAbs_EDGE);
377   for (; aExp.More(); aExp.Next()) {
378     const TopoDS_Edge& aE = TopoDS::Edge(aExp.Current());
379     BRepAdaptor_Curve aBAC(aE);
380     //
381     gp_Pln aPln;
382     if (FindPlane(aBAC, aPln)) {
383       aDMEdgePln.Add(aE, aPln);
384     }
385     else {
386       gp_Vec aVT;
387       if (FindEdgeTangent(aBAC, aVT)) {
388         aDMEdgeTgt.Add(aE, gp_Dir(aVT));
389         aBB.Add(aLEdges, aE);
390         aMEdgesNoUniquePlane.Add(aE);
391       }
392     }
393   }
394   //
395   typedef NCollection_List<gp_Dir> BOPAlgo_ListOfDir;
396   //
397   // to avoid processing of the same edges in the same plane store
398   // the processed planes into a list and use it as a fence map
399   BOPAlgo_ListOfDir aLPFence;
400   //
401   // used edges
402   BOPCol_MapOfShape aMEFence;
403   //
404   // look for a planes on the single edges
405   Standard_Integer i, j, aNbPlanes = aDMEdgePln.Extent(), aNbEdges = aDMEdgeTgt.Extent();
406   for (i = 1; i <= aNbPlanes; ++i) {
407     const TopoDS_Shape& aEI = aDMEdgePln.FindKey(i);
408     if (!aMEFence.Add(aEI)) {
409       continue;
410     }
411     //
412     const gp_Pln& aPlnI = aDMEdgePln(i);
413     const gp_Dir& aDI = aPlnI.Position().Direction();
414     //
415     aLPFence.Append(aDI);
416     //
417     BOPCol_IndexedMapOfShape aMEPln;
418     aMEPln.Add(aEI);
419     //
420     BOPCol_IndexedMapOfShape aMV;
421     BOPTools::MapShapes(aEI, TopAbs_VERTEX, aMV);
422     //
423     // look for other edges with the plane parallel to current one
424     for (j = i + 1; j <= aNbPlanes; ++j) {
425       const gp_Dir& aDJ = aDMEdgePln(j).Position().Direction();
426       if (aDI.IsParallel(aDJ, theAngTol)) {
427         const TopoDS_Shape& aEJ = aDMEdgePln.FindKey(j);
428         aMEPln.Add(aEJ);
429         aMEFence.Add(aEJ);
430         BOPTools::MapShapes(aEJ, TopAbs_VERTEX, aMV);
431       }
432     }
433     //
434     // look for all other edges located in the plane parallel to current one
435     TopoDS_Compound aCEPln;
436     aBB.MakeCompound(aCEPln);
437     //
438     for (j = 1; j <= aNbEdges; ++j) {
439       const gp_Dir& aDJ = aDMEdgeTgt(j);
440       if (aDI.IsNormal(aDJ, theAngTol)) {
441         aBB.Add(aCEPln, aDMEdgeTgt.FindKey(j));
442       }
443     }
444     //
445     // make blocks of these edges and check blocks to be connected
446     // to any of the already added edges or forming a wire themselves
447     BOPCol_ListOfShape aLCBE;
448     BOPTools_AlgoTools::MakeConnexityBlocks(aCEPln, TopAbs_VERTEX, TopAbs_EDGE, aLCBE);
449     //
450     // make wire from each block
451     BOPCol_ListIteratorOfListOfShape aItLCB(aLCBE);
452     for (; aItLCB.More(); aItLCB.Next()) {
453       const TopoDS_Shape& aCBE = aItLCB.Value();
454       //
455       // check connectivity
456       TopExp_Explorer aExpV(aCBE, TopAbs_VERTEX);
457       for (; aExpV.More(); aExpV.Next()) {
458         if (aMV.Contains(aExpV.Current())) {
459           break;
460         }
461       }
462       //
463       Standard_Boolean bAddBlock = aExpV.More();
464       if (!bAddBlock) {
465         // check if the edges are forming a wire
466         gp_Pln aPln;
467         bAddBlock = FindPlane(aCBE, aPln, aDMEdgeTgt, aMEdgesNoUniquePlane);
468       }
469       //
470       if (bAddBlock) {
471         // add edges
472         for (TopoDS_Iterator aItE(aCBE); aItE.More(); aItE.Next()) {
473           aMEPln.Add(aItE.Value());
474         }
475       }
476     }
477     //
478     MakeWires(aMEPln, aRWires, Standard_False, aDMEdgeTgt, aMEdgesNoUniquePlane);
479   }
480   //
481   // make connection map from vertices to edges to find the connected pairs
482   BOPCol_IndexedDataMapOfShapeListOfShape aDMVE;
483   BOPTools::MapShapesAndAncestors(aLEdges, TopAbs_VERTEX, TopAbs_EDGE, aDMVE);
484   //
485   // find planes for connected edges
486   Standard_Integer aNbV = aDMVE.Extent();
487   for (i = 1; i <= aNbV; ++i) {
488     const BOPCol_ListOfShape& aLEI = aDMVE(i);
489     if (aLEI.Extent() < 2) {
490       continue;
491     }
492     //
493     BOPCol_ListIteratorOfListOfShape aItLEI1(aLEI);
494     for (; aItLEI1.More(); aItLEI1.Next()) {
495       const TopoDS_Shape& aEI1 = aItLEI1.Value();
496       const gp_Dir& aDI1 = aDMEdgeTgt.FindFromKey(aEI1);
497       //
498       BOPCol_ListIteratorOfListOfShape aItLEI2(aLEI);
499       for (; aItLEI2.More(); aItLEI2.Next()) {
500         const TopoDS_Shape& aEI2 = aItLEI2.Value();
501         if (aEI2.IsSame(aEI1)) {
502           continue;
503         }
504         //
505         const gp_Dir& aDI2 = aDMEdgeTgt.FindFromKey(aEI2);
506         //
507         if (aDI1.IsParallel(aDI2, theAngTol)) {
508           continue;
509         }
510         //
511         gp_Dir aDNI = aDI1^aDI2;
512         //
513         // check if this normal direction has not been checked yet
514         BOPAlgo_ListOfDir::Iterator aItLPln(aLPFence);
515         for (; aItLPln.More(); aItLPln.Next()) {
516           if (aDNI.IsParallel(aItLPln.Value(), theAngTol)) {
517             break;
518           }
519         }
520         if (aItLPln.More()) {
521           continue;
522         }
523         //
524         aLPFence.Append(aDNI);
525         //
526         // find all other edges in the plane parallel to current one
527         BOPCol_IndexedMapOfShape aMEPln;
528         aMEPln.Add(aEI1);
529         aMEPln.Add(aEI2);
530         //
531         // iterate on all other edges to find all edges lying in the plane parallel to current one
532         for (j = 1; j <= aNbEdges; ++j) {
533           const gp_Dir& aDJ = aDMEdgeTgt(j);
534           if (aDNI.IsNormal(aDJ, theAngTol)) {
535             aMEPln.Add(aDMEdgeTgt.FindKey(j));
536           }
537         }
538         //
539         MakeWires(aMEPln, aRWires, Standard_True, aDMEdgeTgt, aMEdgesNoUniquePlane);
540       } // for (; aItLEI2.More(); aItLEI2.Next()) {
541     } // for (; aItLEI1.More(); aItLEI1.Next()) {
542   } // for (i = 1; i < aNb; ++i) {
543   //
544   // 4. Find unused edges and make wires from them
545   BOPCol_IndexedMapOfShape aMEAlone, aMEUsed;
546   BOPTools::MapShapes(aRWires, TopAbs_EDGE, aMEUsed);
547   //
548   for (i = 1; i <= aNbEdges; ++i) {
549     const TopoDS_Shape& aE = aDMEdgeTgt.FindKey(i);
550     if (!aMEUsed.Contains(aE)) {
551       aMEAlone.Add(aE);
552     }
553   }
554   //
555   MakeWires(aMEAlone, aRWires, Standard_False, aDMEdgeTgt, aMEdgesNoUniquePlane);
556   //
557   theWires = aRWires;
558   //
559   return iErr;
560 }
561
562 //=======================================================================
563 //function : WiresToFaces
564 //purpose  : 
565 //=======================================================================
566 Standard_Boolean BOPAlgo_Tools::WiresToFaces(const TopoDS_Shape& theWires,
567                                              TopoDS_Shape& theFaces,
568                                              const Standard_Real theAngTol)
569 {
570   BRep_Builder aBB;
571   BOPCol_MapOfShape aMFence;
572   TopoDS_Compound aRFaces;
573   aBB.MakeCompound(aRFaces);
574   //
575   const Standard_Real aMax = 1.e+8;
576   //
577   // map to store the tangent vectors for the edges
578   BOPAlgo_IndexedDataMapOfShapeDir aDMEdgeTgt;
579   // maps to store the planes found for the wires
580   BOPAlgo_IndexedDataMapOfShapePln aDMWirePln;
581   // map to store the tolerance for the wire
582   NCollection_DataMap<TopoDS_Shape, Standard_Real, TopTools_ShapeMapHasher> aDMWireTol;
583   // edges for which the plane is not found
584   BOPCol_MapOfShape aMEdgesNoUniquePlane;
585   //
586   // Find planes for the wires
587   TopExp_Explorer aExpW(theWires, TopAbs_WIRE);
588   for (; aExpW.More(); aExpW.Next()) {
589     const TopoDS_Wire& aWire = TopoDS::Wire(aExpW.Current());
590     gp_Pln aPlane;
591     if (FindPlane(aWire, aPlane, aDMEdgeTgt, aMEdgesNoUniquePlane)) {
592       aDMWirePln.Add(aWire, aPlane);
593       // find tolerance for the wire - max tolerance of its edges
594       aDMWireTol.Bind(aWire, BRep_Tool::MaxTolerance(aWire, TopAbs_EDGE));
595     }
596   }
597   //
598   Standard_Integer i, j, aNb = aDMWirePln.Extent();
599   for (i = 1; i <= aNb; ++i) {
600     const TopoDS_Shape& aWireI = aDMWirePln.FindKey(i);
601     if (aMFence.Contains(aWireI)) {
602       continue;
603     }
604     //
605     const gp_Pln& aPlnI = aDMWirePln(i);
606     //
607     BOPCol_ListOfShape aLW;
608     aLW.Append(aWireI);
609     aMFence.Add(aWireI);
610     //
611     Standard_Real aTolI = aDMWireTol.Find(aWireI);
612     //
613     // Find other wires in the same plane
614     for (j = i + 1; j <= aNb; ++j) {
615       const TopoDS_Shape& aWireJ = aDMWirePln.FindKey(j);
616       if (aMFence.Contains(aWireJ)) {
617         continue;
618       }
619       //
620       // check if the planes are the same
621       const gp_Pln& aPlnJ = aDMWirePln(j);
622       // check direction of the planes
623       if (!aPlnI.Position().Direction().IsParallel(aPlnJ.Position().Direction(), theAngTol)) {
624         continue;
625       }
626       // check distance between the planes
627       Standard_Real aDist = aPlnI.Distance(aPlnJ.Location());
628       Standard_Real aTolJ = aDMWireTol.Find(aWireJ);
629       if (aDist > (aTolI + aTolJ)) {
630         continue;
631       }
632       //
633       aLW.Append(aWireJ);
634       aMFence.Add(aWireJ);
635     }
636     //
637     // Take the edges to build the face
638     BOPCol_ListOfShape aLE;
639     BOPCol_ListIteratorOfListOfShape aItLW(aLW);
640     for (; aItLW.More(); aItLW.Next()) {
641       TopoDS_Iterator aItE(aItLW.Value());
642       for (; aItE.More(); aItE.Next()) {
643         aLE.Append(aItE.Value().Oriented(TopAbs_FORWARD));
644         aLE.Append(aItE.Value().Oriented(TopAbs_REVERSED));
645       }
646     }
647     //
648     // build planar face
649     TopoDS_Face aFF = BRepBuilderAPI_MakeFace
650       (aPlnI, -aMax, aMax, -aMax, aMax).Face();
651     aFF.Orientation(TopAbs_FORWARD);
652     //
653     try {
654       OCC_CATCH_SIGNALS
655       //
656       // build pcurves for edges on this face
657       BOPTools_AlgoTools2D::BuildPCurveForEdgesOnPlane(aLE, aFF);
658       //
659       // split the face with the edges
660       BOPAlgo_BuilderFace aBF;
661       aBF.SetShapes(aLE);
662       aBF.SetFace(aFF);
663       aBF.Perform();
664       if (aBF.ErrorStatus()) {
665         continue;
666       }
667       //
668       const BOPCol_ListOfShape& aLFSp = aBF.Areas();
669       BOPCol_ListIteratorOfListOfShape aItLF(aLFSp);
670       for (; aItLF.More(); aItLF.Next()) {
671         const TopoDS_Shape& aFSp = aItLF.ChangeValue();
672         aBB.Add(aRFaces, aFSp);
673       }
674     }
675     catch (Standard_Failure) {
676       continue;
677     }
678   }
679   //
680   // fix tolerances of the resulting faces
681   BOPCol_IndexedMapOfShape aMEmpty;
682   BOPTools_AlgoTools::CorrectTolerances(aRFaces, aMEmpty, 0.05, Standard_False);
683   BOPTools_AlgoTools::CorrectShapeTolerances(aRFaces, aMEmpty, Standard_False);
684   //
685   theFaces = aRFaces;
686   TopoDS_Iterator aItF(theFaces);
687   return aItF.More();
688 }
689
690 //=======================================================================
691 //function : MakeWires
692 //purpose  : Makes wires from the separate blocks of the given edges
693 //=======================================================================
694 void MakeWires(const BOPCol_IndexedMapOfShape& theEdges,
695                TopoDS_Compound& theWires,
696                const Standard_Boolean theCheckUniquePlane,
697                BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
698                BOPCol_MapOfShape& theMEdgesNoUniquePlane)
699 {
700   TopoDS_Compound aCE;
701   BRep_Builder().MakeCompound(aCE);
702   Standard_Integer i, aNbE = theEdges.Extent();
703   for (i = 1; i <= aNbE; ++i) {
704     BRep_Builder().Add(aCE, theEdges(i));
705   }
706   //
707   BOPCol_ListOfShape aLCBE;
708   BOPTools_AlgoTools::MakeConnexityBlocks(aCE, TopAbs_VERTEX, TopAbs_EDGE, aLCBE);
709   //
710   // make wire from each block
711   BOPCol_ListIteratorOfListOfShape aItLCB(aLCBE);
712   for (; aItLCB.More(); aItLCB.Next()) {
713     const TopoDS_Shape& aCBE = aItLCB.Value();
714     //
715     if (theCheckUniquePlane) {
716       gp_Pln aPln;
717       if (!FindPlane(aCBE, aPln, theDMEdgeTgt, theMEdgesNoUniquePlane)) {
718         continue;
719       }
720     }
721     //
722     TopoDS_Wire aWire;
723     BRep_Builder().MakeWire(aWire);
724     for (TopoDS_Iterator aItE(aCBE); aItE.More(); aItE.Next()) {
725       BRep_Builder().Add(aWire, aItE.Value());
726     }
727     //
728     BRep_Builder().Add(theWires, aWire);
729   }
730 }
731
732 //=======================================================================
733 //function : FindEdgeTangent
734 //purpose  : Finds the tangent for the edge using the map
735 //=======================================================================
736 Standard_Boolean FindEdgeTangent(const TopoDS_Edge& theEdge,
737                                  BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
738                                  gp_Dir& theTgt)
739 {
740   gp_Dir *pDTE = theDMEdgeTgt.ChangeSeek(theEdge);
741   if (!pDTE) {
742     gp_Vec aVTE;
743     BRepAdaptor_Curve aBAC(theEdge);
744     if (!FindEdgeTangent(aBAC, aVTE)) {
745       return Standard_False;
746     }
747     pDTE = &theDMEdgeTgt(theDMEdgeTgt.Add(theEdge, gp_Dir(aVTE)));
748   }
749   theTgt = *pDTE;
750   return Standard_True;
751 }
752
753 //=======================================================================
754 //function : FindEdgeTangent
755 //purpose  : Finds the tangent for the edge
756 //=======================================================================
757 Standard_Boolean FindEdgeTangent(const BRepAdaptor_Curve& theCurve,
758                                  gp_Vec& theTangent)
759 {
760   if (!theCurve.Is3DCurve()) {
761     return Standard_False;
762   }
763   // for the line the tangent is defined by the direction
764   if (theCurve.GetType() == GeomAbs_Line) {
765     theTangent = theCurve.Line().Position().Direction();
766     return Standard_True;
767   }
768   //
769   // for other curves take D1 and check for its length
770   Standard_Real aT, aT1(theCurve.FirstParameter()), aT2(theCurve.LastParameter());
771   const Standard_Integer aNbP = 11;
772   const Standard_Real aDt = (aT2 - aT1) / aNbP;
773   //
774   for (aT = aT1 + aDt; aT <= aT2; aT += aDt) {
775     gp_Pnt aP;
776     theCurve.D1(aT, aP, theTangent);
777     if (theTangent.Magnitude() > Precision::Confusion()) {
778       return Standard_True;
779     }
780   }
781   //
782   return Standard_False;
783 }
784
785 //=======================================================================
786 //function : FindPlane
787 //purpose  : Finds the plane in which the edge is located
788 //=======================================================================
789 Standard_Boolean FindPlane(const BRepAdaptor_Curve& theCurve,
790                            gp_Pln& thePlane)
791 {
792   if (!theCurve.Is3DCurve()) {
793     return Standard_False;
794   }
795   //
796   Standard_Boolean bFound = Standard_True;
797   gp_Vec aVN;
798   switch (theCurve.GetType()) {
799     case GeomAbs_Line:
800       return Standard_False;
801     case GeomAbs_Circle:
802       aVN = theCurve.Circle().Position().Direction();
803       break;
804     case GeomAbs_Ellipse:
805       aVN = theCurve.Ellipse().Position().Direction();
806       break;
807     case GeomAbs_Hyperbola:
808       aVN = theCurve.Hyperbola().Position().Direction();
809       break;
810     case GeomAbs_Parabola:
811       aVN = theCurve.Parabola().Position().Direction();
812       break;
813     default: {
814       // for all other types of curve compute two tangent vectors
815       // on the curve and cross them
816       bFound = Standard_False;
817       Standard_Real aT, aT1(theCurve.FirstParameter()), aT2(theCurve.LastParameter());
818       const Standard_Integer aNbP = 11;
819       const Standard_Real aDt = (aT2 - aT1) / aNbP;
820       //
821       aT = aT1;
822       gp_Pnt aP1;
823       gp_Vec aV1;
824       theCurve.D1(aT, aP1, aV1);
825       //
826       for (aT = aT1 + aDt; aT <= aT2; aT += aDt) {
827         gp_Pnt aP2;
828         gp_Vec aV2;
829         theCurve.D1(aT, aP2, aV2);
830         //
831         aVN = aV1^aV2;
832         if (aVN.Magnitude() > Precision::Confusion()) {
833           bFound = Standard_True;
834           break;
835         }
836       }
837       break;
838     }
839   }
840   //
841   if (bFound) {
842     thePlane = gp_Pln(theCurve.Value(theCurve.FirstParameter()), gp_Dir(aVN));
843   }
844   return bFound;
845 }
846
847 //=======================================================================
848 //function : FindPlane
849 //purpose  : Finds the plane in which the wire is located
850 //=======================================================================
851 Standard_Boolean FindPlane(const TopoDS_Shape& theWire,
852                            gp_Pln& thePlane,
853                            BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
854                            BOPCol_MapOfShape& theMEdgesNoUniquePlane)
855 {
856   TopExp_Explorer aExpE1(theWire, TopAbs_EDGE);
857   if (!aExpE1.More()) {
858     return Standard_False;
859   }
860   //
861   // try to find two not parallel edges in wire to get normal of the plane
862   for (; aExpE1.More(); aExpE1.Next()) {
863     // get the first edge in the wire
864     const TopoDS_Edge& aE1 = TopoDS::Edge(aExpE1.Current());
865     //
866     // find tangent for the first edge
867     gp_Dir aDTE1;
868     if (!FindEdgeTangent(aE1, theDMEdgeTgt, aDTE1)) {
869       continue;
870     }
871     //
872     // find the other edge not parallel to the first one
873     TopExp_Explorer aExpE2(theWire, TopAbs_EDGE);
874     for (; aExpE2.More(); aExpE2.Next()) {
875       const TopoDS_Edge& aE2 = TopoDS::Edge(aExpE2.Current());
876       if (aE1.IsSame(aE2)) {
877         continue;
878       }
879       //
880       // find tangent for the second edge
881       gp_Dir aDTE2;
882       if (!FindEdgeTangent(aE2, theDMEdgeTgt, aDTE2)) {
883         continue;
884       }
885       //
886       if (aDTE1.IsParallel(aDTE2, Precision::Angular())) {
887         continue;
888       }
889       //
890       gp_Dir aDN = aDTE1^aDTE2;
891       //
892       TopoDS_Iterator aItV(aE1);
893       thePlane = gp_Pln(BRep_Tool::Pnt(TopoDS::Vertex(aItV.Value())), aDN);
894       return Standard_True;
895     }
896   }
897   //
898   // try to compute normal on the single edge
899   aExpE1.Init(theWire, TopAbs_EDGE);
900   for (; aExpE1.More(); aExpE1.Next()) {
901     const TopoDS_Edge& aE = TopoDS::Edge(aExpE1.Current());
902     if (theMEdgesNoUniquePlane.Contains(aE)) {
903       continue;
904     }
905     BRepAdaptor_Curve aBAC(aE);
906     if (FindPlane(aBAC, thePlane)) {
907       return Standard_True;
908     }
909     theMEdgesNoUniquePlane.Add(aE);
910   }
911   return Standard_False;
912 }