6bddcec11430bce346ef7b18a5ff4e56b72d7ec3
[occt.git] / src / BOPTools / BOPTools_AlgoTools.cxx
1 // Created by: Peter KURNEV
2 // Copyright (c) 2010-2014 OPEN CASCADE SAS
3 // Copyright (c) 2007-2010 CEA/DEN, EDF R&D, OPEN CASCADE
4 // Copyright (c) 2003-2007 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN, CEDRAT,
5 //                         EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
6 //
7 // This file is part of Open CASCADE Technology software library.
8 //
9 // This library is free software; you can redistribute it and/or modify it under
10 // the terms of the GNU Lesser General Public License version 2.1 as published
11 // by the Free Software Foundation, with special exception defined in the file
12 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
13 // distribution for complete text of the license and disclaimer of any warranty.
14 //
15 // Alternatively, this file may be used under the terms of Open CASCADE
16 // commercial license or contractual agreement.
17
18
19 #include <BOPCol_IndexedMapOfShape.hxx>
20 #include <BOPCol_MapOfShape.hxx>
21 #include <BOPTools.hxx>
22 #include <BOPTools_AlgoTools.hxx>
23 #include <BOPTools_AlgoTools2D.hxx>
24 #include <BOPTools_AlgoTools3D.hxx>
25 #include <BOPTools_CoupleOfShape.hxx>
26 #include <BOPTools_ListOfCoupleOfShape.hxx>
27 #include <BRep_Builder.hxx>
28 #include <BRep_Tool.hxx>
29 #include <BRepAdaptor_Curve2d.hxx>
30 #include <BRepAdaptor_Surface.hxx>
31 #include <BRepClass3d_SolidClassifier.hxx>
32 #include <BRepLib.hxx>
33 #include <Geom2d_Curve.hxx>
34 #include <Geom2dInt_Geom2dCurveTool.hxx>
35 #include <Geom_Curve.hxx>
36 #include <Geom_Plane.hxx>
37 #include <Geom_Surface.hxx>
38 #include <Geom_TrimmedCurve.hxx>
39 #include <GeomAPI_ProjectPointOnSurf.hxx>
40 #include <gp_Cone.hxx>
41 #include <gp_Cylinder.hxx>
42 #include <gp_Lin.hxx>
43 #include <gp_Pnt.hxx>
44 #include <gp_Pnt2d.hxx>
45 #include <gp_Sphere.hxx>
46 #include <gp_Torus.hxx>
47 #include <gp_XYZ.hxx>
48 #include <IntTools_Context.hxx>
49 #include <IntTools_Curve.hxx>
50 #include <IntTools_Range.hxx>
51 #include <IntTools_ShrunkRange.hxx>
52 #include <IntTools_Tools.hxx>
53 #include <Precision.hxx>
54 #include <TopAbs_Orientation.hxx>
55 #include <TopExp.hxx>
56 #include <TopExp_Explorer.hxx>
57 #include <TopoDS_Compound.hxx>
58 #include <TopoDS_CompSolid.hxx>
59 #include <TopoDS_Edge.hxx>
60 #include <TopoDS_Face.hxx>
61 #include <TopoDS_Shape.hxx>
62 #include <TopoDS_Shell.hxx>
63 #include <TopoDS_Solid.hxx>
64 #include <TopoDS_Vertex.hxx>
65 #include <TopoDS_Wire.hxx>
66 #include <NCollection_Array1.hxx>
67 #include <algorithm>
68
69 //
70 static
71   Standard_Real AngleWithRef(const gp_Dir& theD1,
72                              const gp_Dir& theD2,
73                              const gp_Dir& theDRef);
74
75 static
76   Standard_Boolean FindFacePairs (const TopoDS_Edge& theE,
77                                   const BOPCol_ListOfShape& thLF,
78                                   BOPTools_ListOfCoupleOfShape& theLCFF,
79                                   Handle(IntTools_Context)& theContext);
80 static
81   TopAbs_Orientation Orientation(const TopoDS_Edge& anE,
82                                  const TopoDS_Face& aF);
83
84 static
85   void GetFaceDir(const TopoDS_Edge& aE,
86                   const TopoDS_Face& aF,
87                   const gp_Pnt& aP,
88                   const Standard_Real aT,
89                   const gp_Dir& aDTgt,
90                   gp_Dir& aDN,
91                   gp_Dir& aDB,
92                   Handle(IntTools_Context)& theContext,
93                   GeomAPI_ProjectPointOnSurf& aProjPL,
94                   const Standard_Real aDt);
95 static
96   Standard_Boolean FindPointInFace(const TopoDS_Face& aF,
97                                    const gp_Pnt& aP,
98                                    gp_Dir& aDB,
99                                    gp_Pnt& aPOut,
100                                    Handle(IntTools_Context)& theContext,
101                                    GeomAPI_ProjectPointOnSurf& aProjPL,
102                                    const Standard_Real aDt,
103                                    const Standard_Real aTolE);
104 static 
105   Standard_Real MinStep3D(const TopoDS_Edge& theE1,
106                           const TopoDS_Face& theF1,
107                           const BOPTools_ListOfCoupleOfShape& theLCS,
108                           const gp_Pnt& aP);
109
110
111
112 //=======================================================================
113 // function: MakeConnexityBlocks
114 // purpose: 
115 //=======================================================================
116 void BOPTools_AlgoTools::MakeConnexityBlocks 
117   (const TopoDS_Shape& theS,
118    const TopAbs_ShapeEnum theType1,
119    const TopAbs_ShapeEnum theType2,
120    BOPCol_ListOfShape& theLCB)
121 {
122   Standard_Integer  aNbF, aNbAdd, aNbAdd1, i;
123   BRep_Builder aBB;
124   TopoDS_Compound aC;
125   TopoDS_Iterator aIt;
126   TopExp_Explorer aExp;
127   BOPCol_MapOfShape aMP;
128   BOPCol_IndexedMapOfShape aMCB, aMAdd, aMAdd1;
129   BOPCol_IndexedDataMapOfShapeListOfShape aMEF;
130   BOPCol_ListIteratorOfListOfShape aItLF;
131   //
132   // 1. aMEF
133   BOPTools::MapShapesAndAncestors(theS, theType1, theType2, aMEF);
134   //
135   // 2. aMCB
136   aIt.Initialize(theS);
137   for (; aIt.More(); aIt.Next()) {
138     const TopoDS_Shape& aF1=aIt.Value();
139     if (aMP.Contains(aF1)) {
140       continue;
141     }
142     //
143     aMCB.Clear();
144     aMAdd.Clear();
145     aMAdd.Add(aF1);
146     //
147     for(;;) {
148       aMAdd1.Clear();
149       //
150       aNbAdd = aMAdd.Extent();
151       for (i=1; i<=aNbAdd; ++i) {
152         const TopoDS_Shape& aF=aMAdd(i);
153         //
154         aExp.Init(aF, theType1);
155         for (; aExp.More(); aExp.Next()) {
156           const TopoDS_Shape& aE=aExp.Current();
157           //
158           const BOPCol_ListOfShape& aLF=aMEF.FindFromKey(aE);
159           aItLF.Initialize(aLF);
160           for (; aItLF.More(); aItLF.Next()) {
161             const TopoDS_Shape& aFx=aItLF.Value();
162             if (aFx.IsSame(aF)) {
163               continue;
164             }
165             if (aMCB.Contains(aFx)) {
166               continue;
167             }
168             aMAdd1.Add(aFx);
169           }
170         }//for (; aExp.More(); aExp.Next()){
171         aMCB.Add(aF);
172       }// for (i=1; i<=aNbAdd; ++i) {
173       //
174       aNbAdd1=aMAdd1.Extent();
175       if (!aNbAdd1) {
176         break;// ->make new CB from aMCB
177       }
178       //
179       aMAdd.Clear();
180       for (i=1; i<=aNbAdd1; ++i) {
181         const TopoDS_Shape& aFAdd = aMAdd1(i);
182         aMAdd.Add(aFAdd);
183       }
184     }//while(1) {
185     //
186     aNbF=aMCB.Extent();
187     if (aNbF) {
188       aBB.MakeCompound(aC);
189       //
190       for (i=1; i<=aNbF; ++i) {
191         const TopoDS_Shape& aF=aMCB(i);
192         aBB.Add(aC, aF);  
193         aMP.Add(aF);
194       }
195       theLCB.Append(aC);
196     }
197   }// for (; aIt.More(); aIt.Next()) 
198 }
199 //=======================================================================
200 // function: OrientFacesOnShell
201 // purpose: 
202 //=======================================================================
203 void BOPTools_AlgoTools::OrientFacesOnShell (TopoDS_Shape& aShell)
204 {
205   Standard_Boolean bIsProcessed1, bIsProcessed2;
206   Standard_Integer i, aNbE, aNbF, j;
207   TopAbs_Orientation anOrE1, anOrE2;
208   TopoDS_Face aF1x, aF2x;
209   TopoDS_Shape aShellNew;
210   BOPCol_IndexedDataMapOfShapeListOfShape aEFMap;
211   BOPCol_IndexedMapOfShape aProcessedFaces;
212   BRep_Builder aBB;
213   //
214   BOPTools_AlgoTools::MakeContainer(TopAbs_SHELL, aShellNew);
215   //
216   BOPTools::MapShapesAndAncestors(aShell, 
217                                   TopAbs_EDGE, TopAbs_FACE, 
218                                   aEFMap);
219   aNbE=aEFMap.Extent();
220   // 
221   // One seam edge  in aEFMap contains  2 equivalent faces.
222   for (i=1; i<=aNbE; ++i) {
223     BOPCol_ListOfShape& aLF=aEFMap.ChangeFromIndex(i);
224     aNbF=aLF.Extent();
225     if (aNbF>1) {
226       BOPCol_ListOfShape aLFTmp;
227       BOPCol_IndexedMapOfShape aFM;
228       //
229       BOPCol_ListIteratorOfListOfShape anIt(aLF);
230       for (; anIt.More(); anIt.Next()) {
231         const TopoDS_Shape& aF=anIt.Value();
232         if (!aFM.Contains(aF)) {
233           aFM.Add(aF);
234           aLFTmp.Append(aF);
235         }
236       }
237       aLF.Clear();
238       aLF=aLFTmp;
239     }
240   }
241   //
242   // Do
243   for (i=1; i<=aNbE; ++i) {
244     const TopoDS_Edge& aE=(*(TopoDS_Edge*)(&aEFMap.FindKey(i)));
245     if (BRep_Tool::Degenerated(aE)) {
246       continue;
247     }
248     //
249     const BOPCol_ListOfShape& aLF=aEFMap.FindFromIndex(i);
250     aNbF=aLF.Extent();
251     if (aNbF!=2) {
252       continue;
253     }
254     //
255     TopoDS_Face& aF1=(*(TopoDS_Face*)(&aLF.First()));
256     TopoDS_Face& aF2=(*(TopoDS_Face*)(&aLF.Last()));
257     //    
258     bIsProcessed1=aProcessedFaces.Contains(aF1);
259     bIsProcessed2=aProcessedFaces.Contains(aF2);
260     if (bIsProcessed1 && bIsProcessed2) {
261       continue;
262     }
263     
264     if (!bIsProcessed1 && !bIsProcessed2) {
265       aProcessedFaces.Add(aF1);
266       aBB.Add(aShellNew, aF1);
267       bIsProcessed1=!bIsProcessed1;
268     }
269     //
270     aF1x=aF1;
271     if (bIsProcessed1) {
272       j=aProcessedFaces.FindIndex(aF1);
273       aF1x=(*(TopoDS_Face*)(&aProcessedFaces.FindKey(j)));
274     }
275     //
276     aF2x=aF2;
277     if (bIsProcessed2) {
278       j=aProcessedFaces.FindIndex(aF2);
279       aF2x=(*(TopoDS_Face*)(&aProcessedFaces.FindKey(j)));
280     }
281     //
282     anOrE1=Orientation(aE, aF1x); 
283     anOrE2=Orientation(aE, aF2x);
284     //
285     if (bIsProcessed1 && !bIsProcessed2) {
286       if (anOrE1==anOrE2) {
287         if (!BRep_Tool::IsClosed(aE, aF1) &&
288             !BRep_Tool::IsClosed(aE, aF2)) {
289           aF2.Reverse();
290         }
291       }
292       aProcessedFaces.Add(aF2);
293       aBB.Add(aShellNew, aF2);
294     }
295     else if (!bIsProcessed1 && bIsProcessed2) {
296       if (anOrE1==anOrE2) {
297         if (!BRep_Tool::IsClosed(aE, aF1) &&
298             !BRep_Tool::IsClosed(aE, aF2)) {
299           aF1.Reverse();
300         }
301       }
302       aProcessedFaces.Add(aF1);
303       aBB.Add(aShellNew, aF1);
304     }
305   }
306   //
307   //
308   for (i=1; i<=aNbE; ++i) {
309     const TopoDS_Edge& aE=(*(TopoDS_Edge*)(&aEFMap.FindKey(i)));
310     if (BRep_Tool::Degenerated(aE)) {
311       continue;
312     }
313     //
314     const BOPCol_ListOfShape& aLF=aEFMap.FindFromIndex(i);
315     aNbF=aLF.Extent();
316     if (aNbF!=2) {
317       BOPCol_ListIteratorOfListOfShape anIt(aLF);
318       for(; anIt.More(); anIt.Next()) {
319         const TopoDS_Face& aF=(*(TopoDS_Face*)(&anIt.Value()));
320         if (!aProcessedFaces.Contains(aF)) {
321           aProcessedFaces.Add(aF);
322           aBB.Add(aShellNew, aF);
323         }
324       }
325     }
326   }
327   aShell=aShellNew;
328 }
329 //=======================================================================
330 //function : Orientation
331 //purpose  :
332 //=======================================================================
333 TopAbs_Orientation Orientation(const TopoDS_Edge& anE,
334                                const TopoDS_Face& aF)
335 {
336   TopAbs_Orientation anOr=TopAbs_INTERNAL;
337
338   TopExp_Explorer anExp;
339   anExp.Init(aF, TopAbs_EDGE);
340   for (; anExp.More(); anExp.Next()) {
341     const TopoDS_Edge& anEF1=(*(TopoDS_Edge*)(&anExp.Current()));
342     if (anEF1.IsSame(anE)) {
343       anOr=anEF1.Orientation();
344       break;
345     }
346   }
347   return anOr;
348 }
349 //=======================================================================
350 // function: MakeConnexityBlock.
351 // purpose: 
352 //=======================================================================
353 void BOPTools_AlgoTools::MakeConnexityBlock 
354   (BOPCol_ListOfShape& theLFIn,
355    BOPCol_IndexedMapOfShape& theMEAvoid,
356    BOPCol_ListOfShape& theLCB,
357    const Handle(NCollection_BaseAllocator)& theAllocator)
358 {
359   Standard_Integer  aNbF, aNbAdd1, aNbAdd, i;
360   TopExp_Explorer aExp;
361   BOPCol_ListIteratorOfListOfShape aIt;
362   //
363   BOPCol_IndexedMapOfShape aMCB(100, theAllocator);
364   BOPCol_IndexedMapOfShape aMAdd(100, theAllocator);
365   BOPCol_IndexedMapOfShape aMAdd1(100, theAllocator);
366   BOPCol_IndexedDataMapOfShapeListOfShape aMEF(100, theAllocator);
367   //
368   // 1. aMEF
369   aNbF=theLFIn.Extent();
370   aIt.Initialize(theLFIn);
371   for (; aIt.More(); aIt.Next()) {
372     const TopoDS_Shape& aF=aIt.Value();      
373     BOPTools::MapShapesAndAncestors(aF, TopAbs_EDGE, TopAbs_FACE, aMEF);
374   }
375   //
376   // 2. aMCB
377   const TopoDS_Shape& aF1=theLFIn.First();
378   aMAdd.Add(aF1);
379   //
380   for(;;) {
381     aMAdd1.Clear();
382     aNbAdd = aMAdd.Extent();
383     for (i=1; i<=aNbAdd; ++i) {
384       const TopoDS_Shape& aF=aMAdd(i);
385       //
386       //aMAdd1.Clear();
387       aExp.Init(aF, TopAbs_EDGE);
388       for (; aExp.More(); aExp.Next()) {
389         const TopoDS_Shape& aE=aExp.Current();
390         if (theMEAvoid.Contains(aE)){
391           continue;
392         }
393         //
394         const BOPCol_ListOfShape& aLF=aMEF.FindFromKey(aE);
395         aIt.Initialize(aLF);
396         for (; aIt.More(); aIt.Next()) {
397           const TopoDS_Shape& aFx=aIt.Value();
398           if (aFx.IsSame(aF)) {
399             continue;
400           }
401           if (aMCB.Contains(aFx)) {
402             continue;
403           }
404           aMAdd1.Add(aFx);
405         }
406       }//for (; aExp.More(); aExp.Next()){
407       aMCB.Add(aF);
408     }// for (i=1; i<=aNbAdd; ++i) {
409     //
410     aNbAdd1=aMAdd1.Extent();
411     if (!aNbAdd1) {
412       break;
413     }
414     //
415     aMAdd.Clear();
416     for (i=1; i<=aNbAdd1; ++i) {
417       const TopoDS_Shape& aFAdd=aMAdd1(i);
418       aMAdd.Add(aFAdd);
419     }
420     //
421   }//while(1) {
422   
423   //
424   aNbF=aMCB.Extent();
425   for (i=1; i<=aNbF; ++i) {
426     const TopoDS_Shape& aF=aMCB(i);
427     theLCB.Append(aF);
428   }
429 }
430 //=======================================================================
431 // function:  ComputeStateByOnePoint
432 // purpose: 
433 //=======================================================================
434 TopAbs_State BOPTools_AlgoTools::ComputeStateByOnePoint
435   (const TopoDS_Shape& theS,
436    const TopoDS_Solid& theRef,
437    const Standard_Real theTol,
438    Handle(IntTools_Context)& theContext)
439 {
440   TopAbs_State aState;
441   TopAbs_ShapeEnum aType;
442   //
443   aState=TopAbs_UNKNOWN;
444   aType=theS.ShapeType();
445   if (aType==TopAbs_VERTEX) {
446     const TopoDS_Vertex& aV=(*(TopoDS_Vertex*)(&theS));
447     aState=BOPTools_AlgoTools::ComputeState(aV, theRef, theTol, theContext);
448   }
449   else if (aType==TopAbs_EDGE) {
450     const TopoDS_Edge& aE=(*(TopoDS_Edge*)(&theS));
451     aState=BOPTools_AlgoTools::ComputeState(aE, theRef, theTol, theContext);
452   }
453   return aState;
454 }
455
456 //=======================================================================
457 // function:  ComputeState
458 // purpose: 
459 //=======================================================================
460 TopAbs_State BOPTools_AlgoTools::ComputeState
461   (const TopoDS_Face& theF,
462    const TopoDS_Solid& theRef,
463    const Standard_Real theTol,
464    BOPCol_IndexedMapOfShape& theBounds,
465    Handle(IntTools_Context)& theContext)
466 {
467   TopAbs_State aState;
468   TopExp_Explorer aExp; 
469   TopoDS_Edge aE1;
470   gp_Pnt2d aP2D;
471   gp_Pnt aP3D; 
472   //
473   aState=TopAbs_UNKNOWN;
474   //
475   aExp.Init(theF, TopAbs_EDGE);
476   for (; aExp.More(); aExp.Next()) {
477     const TopoDS_Edge& aSE=(*(TopoDS_Edge*)(&aExp.Current()));
478     if (BRep_Tool::Degenerated(aSE)) {
479       continue;
480     }
481     //
482     if (!theBounds.Contains(aSE)) {
483       const TopoDS_Edge& aE=(*(TopoDS_Edge*)(&aSE));
484       aState=BOPTools_AlgoTools::ComputeState(aE, theRef, theTol, 
485                                               theContext);
486       return aState;
487     }
488     if (aE1.IsNull()) {
489       aE1=(*(TopoDS_Edge*)(&aSE));
490     }
491   }
492   // !!<- process edges that are all on theRef
493   if (!aE1.IsNull()) {
494     BOPTools_AlgoTools3D::PointNearEdge(aE1, theF, 
495                                         aP2D, aP3D, theContext);
496     aState=BOPTools_AlgoTools::ComputeState(aP3D, theRef, theTol, 
497                                             theContext);
498   }
499   //
500   return aState;
501 }
502 //=======================================================================
503 // function:  ComputeState
504 // purpose: 
505 //=======================================================================
506 TopAbs_State BOPTools_AlgoTools::ComputeState
507   (const TopoDS_Vertex& theV,
508    const TopoDS_Solid& theRef,
509    const Standard_Real theTol,
510    Handle(IntTools_Context)& theContext)
511 {
512   TopAbs_State aState;
513   gp_Pnt aP3D; 
514   //
515   aP3D=BRep_Tool::Pnt(theV);
516   aState=BOPTools_AlgoTools::ComputeState(aP3D, theRef, theTol, 
517                                           theContext);
518   return aState;
519 }
520 //=======================================================================
521 // function:  ComputeState
522 // purpose: 
523 //=======================================================================
524 TopAbs_State BOPTools_AlgoTools::ComputeState
525   (const TopoDS_Edge& theE,
526    const TopoDS_Solid& theRef,
527    const Standard_Real theTol,
528    Handle(IntTools_Context)& theContext)
529 {
530   Standard_Real aT1, aT2, aT = 0.;
531   TopAbs_State aState;
532   Handle(Geom_Curve) aC3D;
533   gp_Pnt aP3D; 
534   //
535   aC3D = BRep_Tool::Curve(theE, aT1, aT2);
536   //
537   if(aC3D.IsNull()) {
538     //it means that we are in degenerated edge
539     const TopoDS_Vertex& aV = TopExp::FirstVertex(theE);
540     if(aV.IsNull()){
541       return TopAbs_UNKNOWN;
542     }
543     aP3D=BRep_Tool::Pnt(aV);
544   }
545   else {//usual case
546     Standard_Boolean bF2Inf, bL2Inf;
547     Standard_Real dT=10.;
548     //
549     bF2Inf = Precision::IsNegativeInfinite(aT1);
550     bL2Inf = Precision::IsPositiveInfinite(aT2);
551     //
552     if (bF2Inf && !bL2Inf) {
553       aT=aT2-dT;
554     }
555     else if (!bF2Inf && bL2Inf) {
556       aT=aT1+dT;
557     }
558     else if (bF2Inf && bL2Inf) {
559       aT=0.;
560     }
561     else {
562       aT=IntTools_Tools::IntermediatePoint(aT1, aT2);
563     }
564     aC3D->D0(aT, aP3D);
565   }
566   //
567   aState=BOPTools_AlgoTools::ComputeState(aP3D, theRef, theTol, 
568                                           theContext);
569   //
570   return aState;
571 }
572 //=======================================================================
573 // function:  ComputeState
574 // purpose: 
575 //=======================================================================
576 TopAbs_State BOPTools_AlgoTools::ComputeState
577   (const gp_Pnt& theP,
578    const TopoDS_Solid& theRef,
579    const Standard_Real theTol,
580    Handle(IntTools_Context)& theContext)
581 {
582   TopAbs_State aState;
583   //
584   BRepClass3d_SolidClassifier& aSC=theContext->SolidClassifier(theRef);
585   aSC.Perform(theP, theTol);
586   //
587   aState=aSC.State();
588   //
589   return aState;
590 }
591 //=======================================================================
592 //function : IsInternalFace
593 //purpose  : 
594 //=======================================================================
595 Standard_Integer BOPTools_AlgoTools::IsInternalFace
596   (const TopoDS_Face& theFace,
597    const TopoDS_Solid& theSolid,
598    BOPCol_IndexedDataMapOfShapeListOfShape& theMEF,
599    const Standard_Real theTol,
600    Handle(IntTools_Context)& theContext)
601 {
602   Standard_Boolean bDegenerated;
603   Standard_Integer aNbF, iRet, iFound;
604   TopAbs_Orientation aOr;
605   TopoDS_Edge aE1;
606   TopExp_Explorer aExp;
607   BOPCol_ListIteratorOfListOfShape aItF;
608   //
609   // For all invoked functions: [::IsInternalFace(...)] 
610   // the returned value iRet means:
611   // iRet=0;  - state is not IN
612   // iRet=1;  - state is IN
613   // iRet=2;  - state can not be found by the method of angles
614   //
615   // For this function the returned value iRet means:
616   // iRet=0;  - state is not IN
617   // iRet=1;  - state is IN
618   //
619   iRet=0; 
620   // 1 Try to find an edge from theFace in theMEF
621   iFound=0;
622   aExp.Init(theFace, TopAbs_EDGE);
623   for(; aExp.More(); aExp.Next()) {
624     const TopoDS_Edge& aE=(*(TopoDS_Edge*)(&aExp.Current()));
625     if (!theMEF.Contains(aE)) {
626       continue;
627     }
628     //
629     ++iFound;
630     //
631     aOr=aE.Orientation();
632     if (aOr==TopAbs_INTERNAL) {
633       continue;
634     }
635     bDegenerated=BRep_Tool::Degenerated(aE);
636     if (bDegenerated){
637       continue;
638     }
639     // aE
640     BOPCol_ListOfShape& aLF=theMEF.ChangeFromKey(aE);
641     aNbF=aLF.Extent();
642     if (!aNbF) {
643       return iRet; // it can not be so
644     }
645     //
646     else if (aNbF==1) {
647       // aE is internal edge on aLF.First()
648       const TopoDS_Face& aF1=(*(TopoDS_Face*)(&aLF.First()));
649       BOPTools_AlgoTools::GetEdgeOnFace(aE, aF1, aE1);
650       if (aE1.Orientation()!=TopAbs_INTERNAL) {
651         iRet=2; 
652         break;
653       }
654       //
655       iRet=BOPTools_AlgoTools::IsInternalFace(theFace, aE, aF1, aF1, 
656                                               theContext);
657       break;
658     }
659     //
660     else if (aNbF==2) {
661       const TopoDS_Face& aF1=(*(TopoDS_Face*)(&aLF.First()));
662       const TopoDS_Face& aF2=(*(TopoDS_Face*)(&aLF.Last()));
663       //
664       if (aF2.IsSame(aF1) && BRep_Tool::IsClosed(aE, aF1)) {
665         // treat as it was for 1 face
666         iRet=BOPTools_AlgoTools::IsInternalFace(theFace, aE, aF1, aF2, 
667                                                 theContext);
668         break;
669       }
670     }
671     //
672     if (aNbF%2) {
673       iRet=0;
674       return iRet; // it can not be so
675     }
676     else { // aNbF=2,4,6,8,...
677       iRet=BOPTools_AlgoTools::IsInternalFace(theFace, aE, aLF, 
678                                               theContext);
679       break;
680     }
681   }//for(; aExp.More(); aExp.Next()) {
682   //
683   if (!iFound) {
684     // the face has no shared edges with the solid
685     iRet=2;
686   }
687   //
688   if (iRet!=2) {
689     return iRet;
690   }
691   //
692   //========================================
693   // 2. Classify face using classifier
694   //
695   TopAbs_State aState;
696   BOPCol_IndexedMapOfShape aBounds;
697   //
698   BOPTools::MapShapes(theSolid, TopAbs_EDGE, aBounds);
699   //
700   aState=BOPTools_AlgoTools::ComputeState(theFace, theSolid, 
701                                           theTol, aBounds, theContext);
702   //
703   iRet=(aState==TopAbs_IN)? 1 : 0;
704   //
705   return iRet;
706 }
707 //=======================================================================
708 //function : IsInternalFace
709 //purpose  : 
710 //=======================================================================
711 Standard_Integer BOPTools_AlgoTools::IsInternalFace
712   (const TopoDS_Face& theFace,
713    const TopoDS_Edge& theEdge,
714    BOPCol_ListOfShape& theLF,
715    Handle(IntTools_Context)& theContext)
716 {
717   Standard_Integer aNbF, iRet;
718   //
719   iRet=0;
720   //
721   aNbF=theLF.Extent();
722   if (aNbF==2) {
723     const TopoDS_Face& aF1=(*(TopoDS_Face*)(&theLF.First()));
724     const TopoDS_Face& aF2=(*(TopoDS_Face*)(&theLF.Last()));
725     iRet=BOPTools_AlgoTools::IsInternalFace(theFace, theEdge, aF1, aF2, 
726                                             theContext);
727     return iRet;
728   }
729   //
730   else {
731     BOPTools_ListOfCoupleOfShape aLCFF;
732     BOPTools_ListIteratorOfListOfCoupleOfShape aIt;
733     //
734     FindFacePairs(theEdge, theLF, aLCFF, theContext);
735     //
736     aIt.Initialize(aLCFF);
737     for (; aIt.More(); aIt.Next()) {
738       BOPTools_CoupleOfShape& aCSFF=aIt.ChangeValue();
739       //
740       const TopoDS_Face& aF1=(*(TopoDS_Face*)(&aCSFF.Shape1()));
741       const TopoDS_Face& aF2=(*(TopoDS_Face*)(&aCSFF.Shape2()));
742       iRet=BOPTools_AlgoTools::IsInternalFace(theFace, theEdge, aF1, aF2, 
743                                               theContext);
744       if (iRet) {
745         return iRet;
746       }
747     }
748   }
749   return iRet;
750 }
751 //=======================================================================
752 //function : IsInternalFace
753 //purpose  : 
754 //=======================================================================
755 Standard_Integer BOPTools_AlgoTools::IsInternalFace
756   (const TopoDS_Face& theFace,
757    const TopoDS_Edge& theEdge,
758    const TopoDS_Face& theFace1,
759    const TopoDS_Face& theFace2,
760    Handle(IntTools_Context)& theContext)
761 {
762   Standard_Boolean bRet;
763   Standard_Integer iRet;
764   TopoDS_Edge aE1, aE2;
765   TopoDS_Face aFOff;
766   BOPTools_ListOfCoupleOfShape theLCSOff;
767   BOPTools_CoupleOfShape aCS1, aCS2;
768   //
769   BOPTools_AlgoTools::GetEdgeOnFace(theEdge, theFace1, aE1);
770   if (aE1.Orientation()==TopAbs_INTERNAL) {
771     aE2=aE1;
772     aE1.Orientation(TopAbs_FORWARD);
773     aE2.Orientation(TopAbs_REVERSED);
774   }
775   else if (theFace1==theFace2) {
776     aE2=aE1;
777     aE1.Orientation(TopAbs_FORWARD);
778     aE2.Orientation(TopAbs_REVERSED);
779   }
780   else {
781     BOPTools_AlgoTools::GetEdgeOnFace(theEdge, theFace2, aE2);
782   }
783   //
784   aCS1.SetShape1(theEdge);
785   aCS1.SetShape2(theFace);
786   theLCSOff.Append(aCS1);
787   //
788   aCS2.SetShape1(aE2);
789   aCS2.SetShape2(theFace2);
790   theLCSOff.Append(aCS2);
791   //
792   bRet=GetFaceOff(aE1, theFace1, theLCSOff, aFOff, theContext);
793   //
794   iRet=0; // theFace is not internal
795   if (theFace.IsEqual(aFOff)) {
796     // theFace is internal
797     iRet=1;  
798     if (!bRet) {
799       // theFace seems to be internal  
800       iRet=2;
801     }
802   }
803   return iRet;
804 }
805 //=======================================================================
806 //function : GetFaceOff
807 //purpose  : 
808 //=======================================================================
809 Standard_Boolean BOPTools_AlgoTools::GetFaceOff
810   (const TopoDS_Edge& theE1,
811    const TopoDS_Face& theF1,
812    BOPTools_ListOfCoupleOfShape& theLCSOff,
813    TopoDS_Face& theFOff,
814    Handle(IntTools_Context)& theContext)
815 {
816   Standard_Boolean bRet;
817   Standard_Real aT, aT1, aT2, aAngle, aTwoPI, aAngleMin, aDt3D;
818   Standard_Real aUmin, aUsup, aVmin, aVsup, aPA;
819   gp_Pnt aPn1, aPn2, aPx;
820   gp_Dir aDN1, aDN2, aDBF, aDBF2, aDTF;
821   gp_Vec aVTgt;
822   TopAbs_Orientation aOr;
823   Handle(Geom_Curve)aC3D;
824   Handle(Geom_Plane) aPL;
825   BOPTools_ListIteratorOfListOfCoupleOfShape aIt;
826   GeomAPI_ProjectPointOnSurf aProjPL;
827   //
828   aPA=Precision::Angular();
829   aAngleMin=100.;
830   aTwoPI=M_PI+M_PI;
831   aC3D =BRep_Tool::Curve(theE1, aT1, aT2);
832   aT=BOPTools_AlgoTools2D::IntermediatePoint(aT1, aT2);
833   aC3D->D0(aT, aPx);
834   //
835   BOPTools_AlgoTools2D::EdgeTangent(theE1, aT, aVTgt);
836   gp_Dir aDTgt(aVTgt), aDTgt2;
837   aOr = theE1.Orientation();
838   //
839   aPL = new Geom_Plane(aPx, aDTgt);
840   aPL->Bounds(aUmin, aUsup, aVmin, aVsup);
841   aProjPL.Init(aPL, aUmin, aUsup, aVmin, aVsup);
842   //
843   aDt3D = MinStep3D(theE1, theF1, theLCSOff, aPx);
844   GetFaceDir(theE1, theF1, aPx, aT, aDTgt, aDN1, aDBF, theContext, 
845              aProjPL, aDt3D);
846   //
847   aDTF=aDN1^aDBF;
848   //
849   bRet=Standard_True;
850   aIt.Initialize(theLCSOff);
851   for (; aIt.More(); aIt.Next()) {
852     const BOPTools_CoupleOfShape& aCS=aIt.Value();
853     const TopoDS_Edge& aE2=(*(TopoDS_Edge*)(&aCS.Shape1()));
854     const TopoDS_Face& aF2=(*(TopoDS_Face*)(&aCS.Shape2()));
855     //
856     aDTgt2 = (aE2.Orientation()==aOr) ? aDTgt : aDTgt.Reversed();
857     GetFaceDir(aE2, aF2, aPx, aT, aDTgt2, aDN2, aDBF2, theContext, 
858                aProjPL, aDt3D);
859     //Angle
860     aAngle=AngleWithRef(aDBF, aDBF2, aDTF);
861     //
862     if(aAngle<0.) {
863       aAngle=aTwoPI+aAngle;
864     }
865     //
866     if (aAngle<aPA) {
867       if (aF2==theF1) {
868         aAngle=M_PI;
869       }
870       else if (aF2.IsSame(theF1)) {
871         aAngle=aTwoPI;
872       }
873     }
874     //
875     if (fabs(aAngle-aAngleMin)<aPA) {
876       // the minimal angle can not be found
877       bRet=Standard_False; 
878     }
879     //
880     if (aAngle<aAngleMin){
881       aAngleMin=aAngle;
882       theFOff=aF2;
883     }
884     else if (aAngle==aAngleMin) {
885       // the minimal angle can not be found
886       bRet=Standard_False;  
887     }
888   }
889   return bRet;
890 }
891 //=======================================================================
892 //function : GetEdgeOff
893 //purpose  : 
894 //=======================================================================
895 Standard_Boolean BOPTools_AlgoTools::GetEdgeOff(const TopoDS_Edge& theE1,
896                                                 const TopoDS_Face& theF2,
897                                                 TopoDS_Edge& theE2)
898 {
899   Standard_Boolean bFound;
900   TopAbs_Orientation aOr1, aOr1C, aOr2;
901   TopExp_Explorer anExp;
902   //
903   bFound=Standard_False;
904   aOr1=theE1.Orientation();
905   aOr1C=TopAbs::Reverse(aOr1);
906   //
907   anExp.Init(theF2, TopAbs_EDGE);
908   for (; anExp.More(); anExp.Next()) {
909     const TopoDS_Edge& aEF2=(*(TopoDS_Edge*)(&anExp.Current()));
910     if (aEF2.IsSame(theE1)) {
911       aOr2=aEF2.Orientation();
912       if (aOr2==aOr1C) {
913         theE2=aEF2;
914         bFound=!bFound;
915         return bFound;
916       }
917     }
918   }
919   return bFound;
920 }
921
922 //=======================================================================
923 //function : AreFacesSameDomain
924 //purpose  : 
925 //=======================================================================
926 Standard_Boolean BOPTools_AlgoTools::AreFacesSameDomain
927   (const TopoDS_Face& theF1,
928    const TopoDS_Face& theF2,
929    Handle(IntTools_Context)& theContext)
930 {
931   Standard_Boolean bFlag;
932   Standard_Integer iErr;
933   Standard_Real aTolF1, aTolF2, aTol;
934   gp_Pnt2d aP2D;
935   gp_Pnt aP;
936   TopoDS_Face aF1, aF2;
937   TopoDS_Edge aE1;
938   TopExp_Explorer aExp;
939   //
940   bFlag=Standard_False;
941   //
942   aF1=theF1;
943   aF1.Orientation(TopAbs_FORWARD);
944   aF2=theF2;
945   aF2.Orientation(TopAbs_FORWARD);
946   //
947   aTolF1=BRep_Tool::Tolerance(aF1);
948   // 1
949   aExp.Init(aF1, TopAbs_EDGE);
950   for (; aExp.More(); aExp.Next()) {
951     aE1=(*(TopoDS_Edge*)(&aExp.Current()));
952     if (!BRep_Tool::Degenerated(aE1)) {
953       Standard_Real aTolE = BRep_Tool::Tolerance(aE1);
954       aTolF1 = (aTolE > aTolF1) ? aTolE : aTolF1;
955     }
956   }
957   // 2
958   aTolF2=BRep_Tool::Tolerance(aF2);
959   aTol = aTolF1 + aTolF2 + Precision::Confusion();
960   //
961   iErr = BOPTools_AlgoTools3D::PointInFace(aF1, aP, aP2D,
962                                            theContext);
963   if (!iErr) {
964     bFlag=theContext->IsValidPointForFace(aP, aF2, aTol);
965   }
966   //
967   return bFlag;
968 }
969
970 //=======================================================================
971 //function : CheckSameGeom
972 //purpose  : 
973 //=======================================================================
974 Standard_Boolean BOPTools_AlgoTools::CheckSameGeom
975   (const TopoDS_Face& theF1,
976    const TopoDS_Face& theF2,
977    Handle(IntTools_Context)& theContext)
978 {
979   Standard_Boolean bRet;
980   Standard_Real aTolF1, aTolF2, aTol;
981   gp_Pnt2d aP2D;
982   gp_Pnt aP;
983   TopExp_Explorer aExp;
984   //
985   bRet=Standard_False;
986   aExp.Init(theF1, TopAbs_EDGE);
987   for (; aExp.More(); aExp.Next()) {
988     const TopoDS_Edge& aE=(*(TopoDS_Edge*)(&aExp.Current()));
989     if (!BRep_Tool::Degenerated(aE)) {
990       aTolF1=BRep_Tool::Tolerance(theF1);
991       aTolF2=BRep_Tool::Tolerance(theF2);
992       aTol=aTolF1+aTolF2;
993       BOPTools_AlgoTools3D::PointNearEdge(aE, theF1, aP2D, aP, theContext);
994       bRet=theContext->IsValidPointForFace(aP, theF2, aTol);
995       break;
996     }
997   }
998   return bRet;
999 }
1000 //=======================================================================
1001 // function: Sense
1002 // purpose: 
1003 //=======================================================================
1004 Standard_Integer BOPTools_AlgoTools::Sense (const TopoDS_Face& theF1,
1005                                             const TopoDS_Face& theF2)
1006 {
1007   Standard_Integer iSense=0;
1008   gp_Dir aDNF1, aDNF2;
1009   TopoDS_Edge aE1, aE2;
1010   TopExp_Explorer aExp;
1011   //
1012   aExp.Init(theF1, TopAbs_EDGE);
1013   for (; aExp.More(); aExp.Next()) {
1014     aE1=(*(TopoDS_Edge*)(&aExp.Current()));
1015     if (!BRep_Tool::Degenerated(aE1)) {
1016       if (!BRep_Tool::IsClosed(aE1, theF1)) {
1017         break;
1018       }
1019     }
1020   }
1021   //
1022   aExp.Init(theF2, TopAbs_EDGE);
1023   for (; aExp.More(); aExp.Next()) {
1024     aE2=(*(TopoDS_Edge*)(&aExp.Current()));
1025     if (!BRep_Tool::Degenerated(aE2)) {
1026       if (!BRep_Tool::IsClosed(aE2, theF2)) {
1027         if (aE2.IsSame(aE1)) {
1028           iSense=1;
1029           break;
1030         }
1031       }
1032     }
1033   }
1034   //
1035   if (!iSense) {
1036     return iSense;
1037   }
1038   //
1039   BOPTools_AlgoTools3D::GetNormalToFaceOnEdge(aE1, theF1, aDNF1);
1040   BOPTools_AlgoTools3D::GetNormalToFaceOnEdge(aE2, theF2, aDNF2);
1041   //
1042   iSense=BOPTools_AlgoTools3D::SenseFlag(aDNF1, aDNF2);
1043   //
1044   return iSense;
1045 }
1046 //=======================================================================
1047 // function: IsSplitToReverse
1048 // purpose: 
1049 //=======================================================================
1050 Standard_Boolean BOPTools_AlgoTools::IsSplitToReverse
1051   (const TopoDS_Shape& theSp,
1052    const TopoDS_Shape& theSr,
1053    Handle(IntTools_Context)& theContext)
1054 {
1055   Standard_Boolean bRet;
1056   TopAbs_ShapeEnum aType;
1057   //
1058   bRet=Standard_False;
1059   //
1060   aType=theSp.ShapeType();
1061   switch (aType) {
1062     case TopAbs_EDGE: {
1063       const TopoDS_Edge& aESp=(*(TopoDS_Edge*)(&theSp));
1064       const TopoDS_Edge& aESr=(*(TopoDS_Edge*)(&theSr));
1065       bRet=BOPTools_AlgoTools::IsSplitToReverse(aESp, aESr, theContext);
1066     }
1067       break;
1068       //
1069     case TopAbs_FACE: {
1070       const TopoDS_Face& aFSp=(*(TopoDS_Face*)(&theSp));
1071       const TopoDS_Face& aFSr=(*(TopoDS_Face*)(&theSr));
1072       bRet=BOPTools_AlgoTools::IsSplitToReverse(aFSp, aFSr, theContext);
1073     }
1074       break;
1075       //
1076     default:
1077       break;
1078   }
1079   return bRet;
1080 }
1081 //=======================================================================
1082 //function :IsSplitToReverse
1083 //purpose  : 
1084 //=======================================================================
1085 Standard_Boolean BOPTools_AlgoTools::IsSplitToReverse
1086   (const TopoDS_Face& theFSp,
1087    const TopoDS_Face& theFSr,
1088    Handle(IntTools_Context)& theContext)
1089 {
1090   Standard_Boolean bRet, bFound, bInFace;
1091   Standard_Real aT1, aT2, aT, aU, aV, aScPr;
1092   gp_Pnt aPFSp, aPFSr;
1093   gp_Dir aDNFSp;
1094   gp_Vec aD1U, aD1V;
1095   Handle(Geom_Surface) aSr, aSp;
1096   TopAbs_Orientation aOrSr, aOrSp;
1097   TopExp_Explorer anExp;
1098   TopoDS_Edge aESp;
1099   //
1100   bRet=Standard_False;
1101   //
1102   aSr=BRep_Tool::Surface(theFSr);
1103   aSp=BRep_Tool::Surface(theFSp);
1104   if (aSr==aSp) {
1105     aOrSr=theFSr.Orientation();
1106     aOrSp=theFSp.Orientation();
1107     bRet=(aOrSr!=aOrSp);
1108     return bRet;
1109   }
1110   //
1111   bFound=Standard_False;
1112   anExp.Init(theFSp, TopAbs_EDGE);
1113   for (; anExp.More(); anExp.Next()) {
1114     aESp=(*(TopoDS_Edge*)(&anExp.Current()));
1115     if (!BRep_Tool::Degenerated(aESp)) {
1116       if (!BRep_Tool::IsClosed(aESp, theFSp)) {
1117         bFound=!bFound;
1118         break;
1119       }
1120     }
1121   }
1122   if (!bFound) {
1123     Standard_Boolean bFlag;
1124     Standard_Integer iErr;
1125     gp_Pnt2d aP2DFSp;
1126     //
1127     iErr=BOPTools_AlgoTools3D::PointInFace(theFSp, aPFSp, aP2DFSp, 
1128                                            theContext);
1129     if (iErr) {
1130       return bRet;
1131     }
1132     //
1133     aP2DFSp.Coord(aU, aV);
1134     bFlag=BOPTools_AlgoTools3D::GetNormalToSurface(aSp, aU, aV, aDNFSp);
1135     if (!bFlag) {
1136       return bRet;
1137     }
1138     //
1139     if (theFSp.Orientation()==TopAbs_REVERSED){
1140       aDNFSp.Reverse();
1141     }
1142   }
1143   else {
1144     BRep_Tool::Range(aESp, aT1, aT2);
1145     aT=BOPTools_AlgoTools2D::IntermediatePoint(aT1, aT2);
1146     BOPTools_AlgoTools3D::GetApproxNormalToFaceOnEdge(aESp, theFSp, aT, 
1147                                                       aPFSp, aDNFSp, 
1148                                                       theContext);
1149   }
1150   //
1151   // Parts of theContext->ComputeVS(..) 
1152   GeomAPI_ProjectPointOnSurf& aProjector=theContext->ProjPS(theFSr);
1153   aProjector.Perform(aPFSp);
1154   if (!aProjector.IsDone()) {
1155     return bRet;
1156   }
1157   //
1158   aProjector.LowerDistanceParameters(aU, aV);
1159   gp_Pnt2d aP2D(aU, aV);
1160   bInFace=theContext->IsPointInOnFace (theFSr, aP2D);
1161   if (!bInFace) {
1162     return bRet;
1163   }
1164   //
1165   aSr->D1(aU, aV, aPFSr, aD1U, aD1V);
1166   gp_Dir aDD1U(aD1U); 
1167   gp_Dir aDD1V(aD1V);
1168   gp_Dir aDNFSr=aDD1U^aDD1V; 
1169   if (theFSr.Orientation()==TopAbs_REVERSED){
1170     aDNFSr.Reverse();
1171   }
1172   //
1173   aScPr=aDNFSp*aDNFSr;
1174   bRet=(aScPr<0.);
1175   //
1176   return bRet;
1177 }
1178 //=======================================================================
1179 //function :IsSplitToReverse
1180 //purpose  : 
1181 //=======================================================================
1182 Standard_Boolean BOPTools_AlgoTools::IsSplitToReverse
1183   (const TopoDS_Edge& aEF1,
1184    const TopoDS_Edge& aEF2,
1185    Handle(IntTools_Context)& theContext)
1186 {
1187   Standard_Boolean bRet, bIsDegenerated;
1188   //
1189   bRet=Standard_False;
1190   bIsDegenerated=(BRep_Tool::Degenerated(aEF1) || 
1191                   BRep_Tool::Degenerated(aEF2));
1192   if (bIsDegenerated) {
1193     return bRet;
1194   }
1195   //
1196   Standard_Real a, b;
1197   TopAbs_Orientation aOrE, aOrSp;
1198   Handle(Geom_Curve)aC1, aC2;
1199   //
1200   aC2=BRep_Tool::Curve(aEF2, a, b);
1201   aC1=BRep_Tool::Curve(aEF1, a, b);
1202   //
1203   if (aC1==aC2) {
1204     aOrE=aEF2.Orientation();
1205     aOrSp=aEF1.Orientation();
1206     bRet=(aOrE!=aOrSp);
1207     return bRet;
1208   }
1209   //
1210   Standard_Real aT1, aT2, aScPr;
1211   gp_Vec aV1, aV2;
1212   gp_Pnt aP;
1213   //
1214   aT1=BOPTools_AlgoTools2D::IntermediatePoint(a, b);
1215   aC1->D0(aT1, aP);
1216   BOPTools_AlgoTools2D::EdgeTangent(aEF1, aT1, aV1);
1217   gp_Dir aDT1(aV1);
1218   //
1219   theContext->ProjectPointOnEdge(aP, aEF2, aT2);
1220   //
1221   BOPTools_AlgoTools2D::EdgeTangent(aEF2, aT2, aV2);
1222   gp_Dir aDT2(aV2);
1223   //
1224   aScPr=aDT1*aDT2;
1225   bRet=(aScPr<0.);
1226   //
1227   return bRet;
1228 }
1229
1230 //=======================================================================
1231 //function : IsHole
1232 //purpose  : 
1233 //=======================================================================
1234 Standard_Boolean BOPTools_AlgoTools::IsHole(const TopoDS_Shape& aW,
1235                                             const TopoDS_Shape& aFace)
1236 {
1237   Standard_Boolean bIsHole;
1238   Standard_Integer i, aNbS;
1239   Standard_Real aT1, aT2, aS;
1240   Standard_Real aU1, aU, dU;
1241   Standard_Real aX1, aY1, aX0, aY0;
1242   TopAbs_Orientation aOr;
1243   
1244   gp_Pnt2d aP2D0, aP2D1;
1245   Handle(Geom2d_Curve) aC2D;
1246   TopoDS_Face aF, aFF;
1247   TopoDS_Iterator aItW;
1248   //
1249   bIsHole=Standard_False;
1250   //
1251   aF=(*(TopoDS_Face *)(&aFace));
1252   aFF=aF;
1253   aFF.Orientation(TopAbs_FORWARD);
1254   //
1255   aS=0.;
1256   aItW.Initialize(aW);
1257   for (; aItW.More(); aItW.Next()) { 
1258     const TopoDS_Edge& aE=(*(TopoDS_Edge *)(&aItW.Value()));
1259     aOr=aE.Orientation();
1260     if (!(aOr==TopAbs_FORWARD || 
1261           aOr==TopAbs_REVERSED)) {
1262       continue;
1263     }
1264     //
1265     aC2D=BRep_Tool::CurveOnSurface(aE, aFF, aT1, aT2);
1266     if (aC2D.IsNull()) {
1267       break; //xx
1268     }
1269     //
1270     BRepAdaptor_Curve2d aBAC2D(aE, aFF);
1271     aNbS=Geom2dInt_Geom2dCurveTool::NbSamples(aBAC2D);
1272     if (aNbS>2) {
1273       aNbS*=4;
1274     }
1275     //
1276     dU=(aT2-aT1)/(Standard_Real)(aNbS-1);
1277     aU =aT1;
1278     aU1=aT1;
1279     if (aOr==TopAbs_REVERSED) {
1280       aU =aT2;
1281       aU1=aT2;
1282       dU=-dU;
1283     }
1284     //
1285     aBAC2D.D0(aU, aP2D0);
1286     for(i=2; i<=aNbS; i++) {
1287       aU=aU1+(i-1)*dU;
1288       aBAC2D.D0(aU, aP2D1);
1289       aP2D0.Coord(aX0, aY0);
1290       aP2D1.Coord(aX1, aY1);
1291       //
1292       aS=aS+(aY0+aY1)*(aX1-aX0); 
1293       //
1294       aP2D0=aP2D1;
1295     }
1296   }//for (; aItW.More(); aItW.Next()) { 
1297   bIsHole=(aS>0.);
1298   return bIsHole;
1299 }
1300
1301 //=======================================================================
1302 // function: MakeContainer
1303 // purpose: 
1304 //=======================================================================
1305 void BOPTools_AlgoTools::MakeContainer(const TopAbs_ShapeEnum theType,
1306                                        TopoDS_Shape& theC)
1307 {
1308   BRep_Builder aBB;
1309   //
1310   switch(theType) {
1311     case TopAbs_COMPOUND:{
1312       TopoDS_Compound aC;
1313       aBB.MakeCompound(aC);
1314       theC=aC;
1315     }
1316       break;
1317       //
1318     case TopAbs_COMPSOLID:{
1319       TopoDS_CompSolid aCS;
1320       aBB.MakeCompSolid(aCS);
1321       theC=aCS;
1322     }
1323       break;
1324       //
1325     case TopAbs_SOLID:{
1326       TopoDS_Solid aSolid;
1327       aBB.MakeSolid(aSolid);
1328       theC=aSolid;
1329     }  
1330       break;
1331       //
1332       //
1333     case TopAbs_SHELL:{
1334       TopoDS_Shell aShell;
1335       aBB.MakeShell(aShell);
1336       theC=aShell;
1337     }  
1338       break;
1339       //
1340     case TopAbs_WIRE: {
1341       TopoDS_Wire aWire;
1342       aBB.MakeWire(aWire);
1343       theC=aWire;
1344     }
1345       break;
1346       //
1347     default:
1348       break;
1349   }
1350 }
1351 //=======================================================================
1352 // function: MakePCurve
1353 // purpose: 
1354 //=======================================================================
1355 void BOPTools_AlgoTools::MakePCurve(const TopoDS_Edge& aE,
1356                                     const TopoDS_Face& aF1,
1357                                     const TopoDS_Face& aF2,
1358                                     const IntTools_Curve& aIC,
1359                                     const Standard_Boolean bPC1,
1360                                     const Standard_Boolean bPC2)
1361
1362 {
1363   Standard_Integer i;
1364   Standard_Real aTolE, aT1, aT2, aOutFirst, aOutLast, aOutTol;
1365   Handle(Geom2d_Curve) aC2D, aC2DA, aC2Dx1;
1366   TopoDS_Face aFFWD; 
1367   BRep_Builder aBB;
1368   Standard_Boolean bPC;
1369   //
1370   aTolE=BRep_Tool::Tolerance(aE);
1371   //
1372   const Handle(Geom_Curve)& aC3DE=BRep_Tool::Curve(aE, aT1, aT2);
1373   Handle(Geom_TrimmedCurve)aC3DETrim=
1374     new Geom_TrimmedCurve(aC3DE, aT1, aT2);
1375   //
1376   for (i=0; i<2; ++i) {
1377     bPC = !i ? bPC1 : bPC2;
1378     if (!bPC) {
1379       continue;
1380     }
1381     //
1382     if (!i) {
1383       aFFWD=aF1;
1384       aC2Dx1=aIC.FirstCurve2d();
1385     }
1386     else {
1387       aFFWD=aF2;
1388       aC2Dx1=aIC.SecondCurve2d();
1389     }
1390     //
1391     aFFWD.Orientation(TopAbs_FORWARD);
1392     //
1393     aC2D=aC2Dx1;
1394     if (aC2D.IsNull()) { 
1395       BOPTools_AlgoTools2D::BuildPCurveForEdgeOnFace(aE, aFFWD);
1396       BOPTools_AlgoTools2D::CurveOnSurface(aE, aFFWD, aC2D, 
1397                                        aOutFirst, aOutLast, 
1398                                        aOutTol);
1399       }
1400     //
1401     if (aC3DE->IsPeriodic()) {
1402       BOPTools_AlgoTools2D::AdjustPCurveOnFace(aFFWD, aT1, aT2,  aC2D, 
1403                                                aC2DA); 
1404     }
1405     else {
1406       BOPTools_AlgoTools2D::AdjustPCurveOnFace(aFFWD, aC3DETrim, aC2D, 
1407                                                aC2DA); 
1408     }
1409     //
1410     aBB.UpdateEdge(aE, aC2DA, aFFWD, aTolE);
1411     //BRepLib::SameParameter(aE);
1412   }
1413   BRepLib::SameParameter(aE);
1414 }
1415 //=======================================================================
1416 // function: MakeEdge
1417 // purpose: 
1418 //=======================================================================
1419 void BOPTools_AlgoTools::MakeEdge(const IntTools_Curve& theIC,
1420                                   const TopoDS_Vertex& theV1,
1421                                   const Standard_Real theT1,
1422                                   const TopoDS_Vertex& theV2,
1423                                   const Standard_Real theT2,
1424                                   const Standard_Real theTolR3D,
1425                                   TopoDS_Edge& theE)
1426 {
1427   Standard_Real aTolV;
1428   BRep_Builder aBB;
1429   //
1430   BOPTools_AlgoTools::MakeSectEdge (theIC, theV1, theT1, theV2, theT2, 
1431                                     theE);
1432   //
1433   aBB.UpdateEdge(theE, theTolR3D);
1434   //
1435   aTolV=BRep_Tool::Tolerance(theV1);
1436   if (aTolV<theTolR3D) {
1437     aBB.UpdateVertex(theV1, theTolR3D);
1438   }
1439   //
1440   aTolV=BRep_Tool::Tolerance(theV2);
1441   if (aTolV<theTolR3D) {
1442     aBB.UpdateVertex(theV2, theTolR3D);
1443   }
1444 }
1445 //=======================================================================
1446 // function: ComputeVV
1447 // purpose: 
1448 //=======================================================================
1449 Standard_Integer BOPTools_AlgoTools::ComputeVV(const TopoDS_Vertex& aV1, 
1450                                                const gp_Pnt& aP2,
1451                                                const Standard_Real aTolP2)
1452 {
1453   Standard_Real aTolV1, aTolSum, aTolSum2, aD2;
1454   gp_Pnt aP1;
1455   //
1456   aTolV1=BRep_Tool::Tolerance(aV1);
1457   
1458   aTolSum = aTolV1 + aTolP2 + Precision::Confusion();
1459   aTolSum2=aTolSum*aTolSum;
1460   //
1461   aP1=BRep_Tool::Pnt(aV1);
1462   //
1463   aD2=aP1.SquareDistance(aP2);
1464   if (aD2>aTolSum2) {
1465     return 1;
1466   }
1467   return 0;
1468
1469 //=======================================================================
1470 // function: ComputeVV
1471 // purpose: 
1472 //=======================================================================
1473 Standard_Integer BOPTools_AlgoTools::ComputeVV(const TopoDS_Vertex& aV1, 
1474                                                const TopoDS_Vertex& aV2)
1475 {
1476   Standard_Real aTolV1, aTolV2, aTolSum, aTolSum2, aD2;
1477   gp_Pnt aP1, aP2;
1478   //
1479   aTolV1=BRep_Tool::Tolerance(aV1);
1480   aTolV2=BRep_Tool::Tolerance(aV2);
1481   aTolSum = aTolV1 + aTolV2 + Precision::Confusion();
1482   aTolSum2=aTolSum*aTolSum;
1483   //
1484   aP1=BRep_Tool::Pnt(aV1);
1485   aP2=BRep_Tool::Pnt(aV2);
1486   //
1487   aD2=aP1.SquareDistance(aP2);
1488   if (aD2>aTolSum2) {
1489     return 1;
1490   }
1491   return 0;
1492 }
1493 //=======================================================================
1494 // function: MakeVertex
1495 // purpose : 
1496 //=======================================================================
1497 void BOPTools_AlgoTools::MakeVertex(const BOPCol_ListOfShape& aLV,
1498                                     TopoDS_Vertex& aVnew)
1499 {
1500   Standard_Integer aNb = aLV.Extent();
1501   if (aNb == 1)
1502     aVnew=*((TopoDS_Vertex*)(&aLV.First()));
1503   else if (aNb > 1)
1504   {
1505     Standard_Real aNTol;
1506     gp_Pnt aNC;
1507     BRepLib::BoundingVertex(aLV, aNC, aNTol);
1508     BRep_Builder aBB;
1509     aBB.MakeVertex(aVnew, aNC, aNTol);
1510   }
1511 }
1512 //=======================================================================
1513 //function : GetEdgeOnFace
1514 //purpose  : 
1515 //=======================================================================
1516 Standard_Boolean BOPTools_AlgoTools::GetEdgeOnFace
1517 (const TopoDS_Edge& theE1,
1518  const TopoDS_Face& theF2,
1519  TopoDS_Edge& theE2)
1520 {
1521   Standard_Boolean bFound;
1522   TopoDS_Iterator aItF, aItW;
1523   //
1524   bFound=Standard_False;
1525   //
1526   aItF.Initialize(theF2);
1527   for (; aItF.More(); aItF.Next()) {
1528     const TopoDS_Shape& aW=aItF.Value();
1529     aItW.Initialize(aW);
1530     for (; aItW.More(); aItW.Next()) {
1531       const TopoDS_Shape& aE=aItW.Value();
1532       if (aE.IsSame(theE1)) {
1533         theE2=(*(TopoDS_Edge*)(&aE));
1534         bFound=!bFound;
1535         return bFound;
1536       }
1537     }
1538   }
1539   return bFound;
1540 }
1541 //=======================================================================
1542 //function : FindFacePairs
1543 //purpose  : 
1544 //=======================================================================
1545 Standard_Boolean FindFacePairs (const TopoDS_Edge& theE,
1546                                 const BOPCol_ListOfShape& thLF,
1547                                 BOPTools_ListOfCoupleOfShape& theLCFF,
1548                                 Handle(IntTools_Context)& theContext)
1549 {
1550   Standard_Boolean bFound;
1551   Standard_Integer i, aNbCEF;
1552   TopAbs_Orientation aOr, aOrC = TopAbs_FORWARD;
1553   BOPCol_MapOfShape aMFP;
1554   TopoDS_Face aF1, aF2;
1555   TopoDS_Edge aEL, aE1;
1556   BOPCol_ListIteratorOfListOfShape aItLF;
1557   BOPTools_CoupleOfShape aCEF, aCFF;
1558   BOPTools_ListOfCoupleOfShape aLCEF, aLCEFx;
1559   BOPTools_ListIteratorOfListOfCoupleOfShape aIt;
1560   //
1561   bFound=Standard_True;
1562   //
1563   // Preface aLCEF
1564   aItLF.Initialize(thLF);
1565   for (; aItLF.More(); aItLF.Next()) { 
1566     const TopoDS_Face& aFL=(*(TopoDS_Face*)(&aItLF.Value()));
1567     //
1568     bFound=BOPTools_AlgoTools::GetEdgeOnFace(theE, aFL, aEL);
1569     if (!bFound) {
1570       return bFound; // it can not be so
1571     }
1572     //
1573     aCEF.SetShape1(aEL);
1574     aCEF.SetShape2(aFL);
1575     aLCEF.Append(aCEF);
1576   }
1577   //
1578   aNbCEF=aLCEF.Extent();
1579   while(aNbCEF) {
1580     //
1581     // aLCEFx
1582     aLCEFx.Clear();
1583     aIt.Initialize(aLCEF);
1584     for (i=0; aIt.More(); aIt.Next(), ++i) {
1585       const BOPTools_CoupleOfShape& aCSx=aIt.Value();
1586       const TopoDS_Shape& aEx=aCSx.Shape1();
1587       const TopoDS_Shape& aFx=aCSx.Shape2();
1588       //
1589       aOr=aEx.Orientation();
1590       //
1591       if (!i) {
1592         aOrC=TopAbs::Reverse(aOr);
1593         aE1=(*(TopoDS_Edge*)(&aEx));
1594         aF1=(*(TopoDS_Face*)(&aFx));
1595         aMFP.Add(aFx);
1596         continue;
1597       }
1598       //
1599       if (aOr==aOrC) {
1600         aLCEFx.Append(aCSx);
1601         aMFP.Add(aFx);
1602       }
1603     }
1604     //
1605     // F2
1606     BOPTools_AlgoTools::GetFaceOff(aE1, aF1, aLCEFx, aF2, theContext);
1607     //
1608     aCFF.SetShape1(aF1);
1609     aCFF.SetShape2(aF2);
1610     theLCFF.Append(aCFF);
1611     //
1612     aMFP.Add(aF1);
1613     aMFP.Add(aF2);
1614     //
1615     // refine aLCEF
1616     aLCEFx.Clear();
1617     aLCEFx=aLCEF;
1618     aLCEF.Clear();
1619     aIt.Initialize(aLCEFx);
1620     for (; aIt.More(); aIt.Next()) {
1621       const BOPTools_CoupleOfShape& aCSx=aIt.Value();
1622       const TopoDS_Shape& aFx=aCSx.Shape2();
1623       if (!aMFP.Contains(aFx)) {
1624         aLCEF.Append(aCSx);
1625       }
1626     }
1627     //
1628     aNbCEF=aLCEF.Extent();
1629   }//while(aNbCEF) {
1630   //
1631   return bFound;
1632 }
1633 //=======================================================================
1634 //function : AngleWithRef
1635 //purpose  : 
1636 //=======================================================================
1637 Standard_Real AngleWithRef(const gp_Dir& theD1,
1638                            const gp_Dir& theD2,
1639                            const gp_Dir& theDRef)
1640 {
1641   Standard_Real aCosinus, aSinus, aBeta, aHalfPI, aScPr;
1642   gp_XYZ aXYZ;
1643   //
1644   aHalfPI=0.5*M_PI;
1645   //
1646   const gp_XYZ& aXYZ1=theD1.XYZ();
1647   const gp_XYZ& aXYZ2=theD2.XYZ();
1648   aXYZ=aXYZ1.Crossed(aXYZ2);
1649   aSinus=aXYZ.Modulus();
1650   aCosinus=theD1*theD2;
1651   //
1652   aBeta=0.;
1653   if (aSinus>=0.) {
1654     aBeta=aHalfPI*(1.-aCosinus);
1655   }
1656   else {
1657     aBeta=2.*M_PI-aHalfPI*(3.+aCosinus);
1658   }
1659   //
1660   aScPr=aXYZ.Dot(theDRef.XYZ());
1661   if (aScPr<0.) {
1662     aBeta=-aBeta;
1663   }
1664   return aBeta;
1665 }
1666 //=======================================================================
1667 // function: IsBlockInOnFace
1668 // purpose: 
1669 //=======================================================================
1670 Standard_Boolean BOPTools_AlgoTools::IsBlockInOnFace
1671   (const IntTools_Range& aShrR,
1672    const TopoDS_Face& aF,
1673    const TopoDS_Edge& aE1,
1674    Handle(IntTools_Context)& aContext)
1675 {
1676   Standard_Boolean bFlag;
1677   Standard_Real f1, l1, ULD, VLD;
1678   gp_Pnt2d aP2D;
1679   gp_Pnt aP11, aP12;
1680   //
1681   aShrR.Range(f1, l1);
1682   Standard_Real dt=0.0075,  k;//dt=0.001,  k;
1683   k=dt*(l1-f1);
1684   f1=f1+k;
1685   l1=l1-k;
1686   //
1687   // Treatment P11
1688   BOPTools_AlgoTools::PointOnEdge(aE1, f1, aP11);
1689   //
1690   GeomAPI_ProjectPointOnSurf& aProjector=aContext->ProjPS(aF);
1691   aProjector.Perform(aP11);
1692   //
1693   bFlag=aProjector.IsDone();
1694   if (!bFlag) {
1695     return bFlag;
1696   }
1697   
1698   aProjector.LowerDistanceParameters(ULD, VLD);
1699   aP2D.SetCoord(ULD, VLD);
1700   //
1701   bFlag=aContext->IsPointInOnFace (aF, aP2D);
1702   //
1703   if (!bFlag) {
1704     return bFlag;
1705   }
1706   //
1707   // Treatment P12
1708   BOPTools_AlgoTools::PointOnEdge(aE1, l1, aP12);
1709   //
1710   aProjector.Perform(aP12);
1711   //
1712   bFlag=aProjector.IsDone();
1713   if (!bFlag) {
1714     return bFlag;
1715   }
1716   
1717   aProjector.LowerDistanceParameters(ULD, VLD);
1718   aP2D.SetCoord(ULD, VLD);
1719   //
1720   bFlag=aContext->IsPointInOnFace (aF, aP2D);
1721   //
1722   if (!bFlag) {
1723     return bFlag;
1724   }
1725   //
1726   // Treatment intemediate
1727   Standard_Real m1, aTolF, aTolE, aTol, aDist;
1728   m1=IntTools_Tools::IntermediatePoint(f1, l1);
1729   BOPTools_AlgoTools::PointOnEdge(aE1, m1, aP12);
1730   //
1731   aProjector.Perform(aP12);
1732   //
1733   bFlag=aProjector.IsDone();
1734   if (!bFlag) {
1735     return bFlag;
1736   }
1737   //
1738   aTolE=BRep_Tool::Tolerance(aE1);
1739   aTolF=BRep_Tool::Tolerance(aF);
1740   aTol=aTolE+aTolF;
1741   aDist=aProjector.LowerDistance();
1742   if (aDist > aTol){
1743    return Standard_False;
1744   }
1745
1746   aProjector.LowerDistanceParameters(ULD, VLD);
1747   aP2D.SetCoord(ULD, VLD);
1748   //
1749   bFlag=aContext->IsPointInOnFace (aF, aP2D);
1750   //
1751   if (!bFlag) {
1752     return bFlag;
1753   }
1754   return bFlag;
1755 }
1756
1757 //=======================================================================
1758 //function : IsMicroEdge
1759 //purpose  : 
1760 //=======================================================================
1761 Standard_Boolean BOPTools_AlgoTools::IsMicroEdge
1762   (const TopoDS_Edge& aE,
1763    const Handle(IntTools_Context)& aCtx,
1764    const Standard_Boolean bCheckSplittable)
1765 {
1766   Standard_Boolean bRet;
1767   Standard_Real aT1, aT2, aTmp;
1768   Handle(Geom_Curve) aC3D;
1769   TopoDS_Vertex aV1, aV2;
1770   //
1771   bRet=(BRep_Tool::Degenerated(aE) ||
1772         !BRep_Tool::IsGeometric(aE));
1773   if (bRet) {
1774     return bRet;
1775   }
1776   //
1777   aC3D=BRep_Tool::Curve(aE, aT1, aT2);
1778   TopExp::Vertices(aE, aV1, aV2);
1779   aT1=BRep_Tool::Parameter(aV1, aE);
1780   aT2=BRep_Tool::Parameter(aV2, aE);
1781   if (aT2<aT1) {
1782     aTmp=aT1;
1783     aT1=aT2;
1784     aT2=aTmp;
1785   }
1786   //
1787   IntTools_ShrunkRange aSR;
1788   aSR.SetContext(aCtx);
1789   aSR.SetData(aE, aT1, aT2, aV1, aV2);
1790   aSR.Perform();
1791   bRet = !aSR.IsDone();
1792   if (!bRet && bCheckSplittable) {
1793     bRet = !aSR.IsSplittable();
1794   }
1795   //
1796   return bRet;
1797 }
1798
1799 //=======================================================================
1800 //function : GetFaceDir
1801 //purpose  : Get binormal direction for the face in the point aP
1802 //=======================================================================
1803 void GetFaceDir(const TopoDS_Edge& aE,
1804                 const TopoDS_Face& aF,
1805                 const gp_Pnt& aP,
1806                 const Standard_Real aT,
1807                 const gp_Dir& aDTgt,
1808                 gp_Dir& aDN,
1809                 gp_Dir& aDB,
1810                 Handle(IntTools_Context)& theContext,
1811                 GeomAPI_ProjectPointOnSurf& aProjPL,
1812                 const Standard_Real aDt)
1813 {
1814   Standard_Real aTolE;
1815   gp_Pnt aPx;
1816   //
1817   BOPTools_AlgoTools3D::GetNormalToFaceOnEdge(aE, aF, aT, aDN);
1818   if (aF.Orientation()==TopAbs_REVERSED){
1819     aDN.Reverse();
1820   }
1821   //
1822   aTolE=BRep_Tool::Tolerance(aE); 
1823   aDB = aDN^aDTgt;
1824   //
1825   if (!FindPointInFace(aF, aP, aDB, aPx, theContext, aProjPL, aDt, aTolE)) {
1826     BOPTools_AlgoTools3D::GetApproxNormalToFaceOnEdge(aE, aF, aT, aPx, 
1827                                                       aDN, theContext);
1828     aProjPL.Perform(aPx);
1829     aPx = aProjPL.NearestPoint();
1830     gp_Vec aVec(aP, aPx);
1831     aDB.SetXYZ(aVec.XYZ());
1832   }
1833 }
1834 //=======================================================================
1835 //function : FindPointInFace
1836 //purpose  : Find a point in the face in direction of <aDB>
1837 //=======================================================================
1838 Standard_Boolean FindPointInFace(const TopoDS_Face& aF,
1839                                  const gp_Pnt& aP,
1840                                  gp_Dir& aDB,
1841                                  gp_Pnt& aPOut,
1842                                  Handle(IntTools_Context)& theContext,
1843                                  GeomAPI_ProjectPointOnSurf& aProjPL,
1844                                  const Standard_Real aDt,
1845                                  const Standard_Real aTolE)
1846 {
1847   Standard_Integer aNbItMax;
1848   Standard_Real aDist, aDTol, aPM, anEps;
1849   Standard_Boolean bRet;
1850   gp_Pnt aP1, aPS;
1851   //
1852   aDTol = Precision::Angular();
1853   aPM = aP.XYZ().Modulus();
1854   if (aPM > 1000.) {
1855     aDTol = 5.e-16 * aPM;
1856   }
1857   bRet = Standard_False;
1858   aNbItMax = 15;
1859   anEps = Precision::SquareConfusion();
1860   //
1861   GeomAPI_ProjectPointOnSurf& aProj=theContext->ProjPS(aF);
1862   //
1863   aPS=aP;
1864   aProj.Perform(aPS);
1865   if (!aProj.IsDone()) {
1866     return bRet;
1867   }
1868   aPS=aProj.NearestPoint();
1869   aProjPL.Perform(aPS);
1870   aPS=aProjPL.NearestPoint();
1871   //
1872   aPS.SetXYZ(aPS.XYZ()+2.*aTolE*aDB.XYZ());
1873   aProj.Perform(aPS);
1874   if (!aProj.IsDone()) {
1875     return bRet;
1876   }
1877   aPS=aProj.NearestPoint();
1878   aProjPL.Perform(aPS);
1879   aPS=aProjPL.NearestPoint();
1880   //
1881   do {
1882     aP1.SetXYZ(aPS.XYZ()+aDt*aDB.XYZ());
1883     //
1884     aProj.Perform(aP1);
1885     if (!aProj.IsDone()) {
1886       return bRet;
1887     }
1888     aPOut = aProj.NearestPoint();
1889     aDist = aProj.LowerDistance();
1890     //
1891     aProjPL.Perform(aPOut);
1892     aPOut = aProjPL.NearestPoint();
1893     //
1894     gp_Vec aV(aPS, aPOut);
1895     if (aV.SquareMagnitude() < anEps) {
1896       return bRet;
1897     }
1898     aDB.SetXYZ(aV.XYZ());
1899   } while (aDist > aDTol && --aNbItMax);
1900   //
1901   bRet = aDist < aDTol;
1902   return bRet;
1903 }
1904 //=======================================================================
1905 //function : MinStep3D
1906 //purpose  : 
1907 //=======================================================================
1908 Standard_Real MinStep3D(const TopoDS_Edge& theE1,
1909                         const TopoDS_Face& theF1,
1910                         const BOPTools_ListOfCoupleOfShape& theLCS,
1911                         const gp_Pnt& aP)
1912 {
1913   Standard_Real aDt, aTolE, aTolF, aDtMax, aDtMin, aR;
1914   BOPTools_CoupleOfShape aCS1;
1915   BOPTools_ListOfCoupleOfShape aLCS;
1916   BOPTools_ListIteratorOfListOfCoupleOfShape aIt;
1917   BRepAdaptor_Surface aBAS;
1918   //
1919   aLCS = theLCS;
1920   aCS1.SetShape1(theE1);
1921   aCS1.SetShape2(theF1);
1922   aLCS.Append(aCS1);
1923   //
1924   aTolE = BRep_Tool::Tolerance(theE1);
1925   aDtMax = -1.;
1926   aDtMin = 5.e-6;
1927   //
1928   aIt.Initialize(aLCS);
1929   for (; aIt.More(); aIt.Next()) {
1930     const BOPTools_CoupleOfShape& aCS = aIt.Value();
1931     const TopoDS_Face& aF = (*(TopoDS_Face*)(&aCS.Shape2()));
1932     //
1933     aTolF = BRep_Tool::Tolerance(aF);
1934     aDt = 2*(aTolE + aTolF);
1935     //
1936     aR = 0.;
1937     aBAS.Initialize(aF, Standard_False);
1938     GeomAbs_SurfaceType aSType = aBAS.GetType();
1939     switch (aSType) {
1940     case GeomAbs_Cylinder: {
1941       aR = aBAS.Cylinder().Radius();
1942       break;
1943     }
1944     case GeomAbs_Cone: {
1945       gp_Lin aL(aBAS.Cone().Axis());
1946       aR = aL.Distance(aP);
1947       break;
1948     }
1949     case GeomAbs_Sphere: {
1950       aDtMin = Max(aDtMin, 5.e-4);
1951       aR = aBAS.Sphere().Radius();
1952       break;
1953     }
1954     case GeomAbs_Torus: {
1955       aR = aBAS.Torus().MajorRadius();
1956       break;
1957     }
1958     default:
1959       aDtMin = Max(aDtMin, 5.e-4);
1960       break;
1961     }
1962     //
1963     if (aR > 100.) {
1964       Standard_Real d = 10*Precision::PConfusion();
1965       aDtMin = Max(aDtMin, sqrt(d*d + 2*d*aR));
1966     }
1967     //
1968     if (aDt > aDtMax) {
1969       aDtMax = aDt;
1970     }
1971   }
1972   //
1973   if (aDtMax < aDtMin) {
1974     aDtMax = aDtMin;
1975   }
1976   //
1977   return aDtMax;
1978 }
1979 //=======================================================================
1980 //function : IsOpenShell
1981 //purpose  : 
1982 //=======================================================================
1983 Standard_Boolean BOPTools_AlgoTools::IsOpenShell(const TopoDS_Shell& aSh)
1984 {
1985   Standard_Boolean bRet;
1986   Standard_Integer i, aNbE, aNbF;
1987   TopAbs_Orientation aOrF;
1988   BOPCol_IndexedDataMapOfShapeListOfShape aMEF; 
1989   BOPCol_ListIteratorOfListOfShape aItLS;
1990   //
1991   bRet=Standard_False;
1992   //
1993   BOPTools::MapShapesAndAncestors(aSh, TopAbs_EDGE, TopAbs_FACE, aMEF);
1994   // 
1995   aNbE=aMEF.Extent();
1996   for (i=1; i<=aNbE; ++i) {
1997     const TopoDS_Edge& aE=*((TopoDS_Edge*)&aMEF.FindKey(i));
1998     if (BRep_Tool::Degenerated(aE)) {
1999       continue;
2000     }
2001     //
2002     aNbF=0;
2003     const BOPCol_ListOfShape& aLF=aMEF(i);
2004     aItLS.Initialize(aLF);
2005     for (; aItLS.More(); aItLS.Next()) {
2006       const TopoDS_Shape& aF=aItLS.Value();
2007       aOrF=aF.Orientation();
2008       if (aOrF==TopAbs_INTERNAL || aOrF==TopAbs_EXTERNAL) {
2009         continue;
2010       }
2011       ++aNbF;
2012     }
2013     //
2014     if (aNbF==1) {
2015       bRet=!bRet; // True
2016       break;
2017     }
2018   }
2019   //
2020   return bRet;
2021 }
2022 //=======================================================================
2023 //function : IsInvertedSolid
2024 //purpose  : 
2025 //=======================================================================
2026 Standard_Boolean BOPTools_AlgoTools::IsInvertedSolid
2027   (const TopoDS_Solid& aSolid)
2028 {
2029   Standard_Real aTolS;
2030   TopAbs_State aState;
2031   BRepClass3d_SolidClassifier aSC(aSolid);
2032   //
2033   aTolS=1.e-7;
2034   aSC.PerformInfinitePoint(aTolS);
2035   aState=aSC.State();
2036   return (aState==TopAbs_IN); 
2037 }