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