a46397b7aeca90d86fe5991758307a176f31e841
[occt.git] / src / TopOpeBRep / TopOpeBRep_ShapeIntersector.cxx
1 // File:        TopOpeBRep_ShapeIntersector.cxx
2 // Created:     Fri May  7 17:36:28 1993
3 // Author:      Jean Yves LEBEY
4 //              <jyl@topsn3>
5
6 #include <TopOpeBRep_ShapeIntersector.ixx>
7
8 #include <TopAbs.hxx>
9 #include <Bnd_Box.hxx>
10 #include <TopOpeBRepTool_box.hxx>
11 #include <TopOpeBRep_define.hxx>
12
13 #ifdef DEB
14 Standard_IMPORT Standard_Boolean TopOpeBRep_GettraceSI(); 
15 Standard_IMPORT Standard_Boolean TopOpeBRep_GetcontextFFOR();
16 Standard_IMPORT Standard_Integer SAVFFi1; // FacesIntersector
17 Standard_IMPORT Standard_Integer SAVFFi2; // FacesIntersector
18 Standard_IMPORT void TopOpeBRep_SettraceEEFF(const Standard_Boolean b);
19 Standard_IMPORT Standard_Boolean TopOpeBRep_GettraceEEFF(const Standard_Integer e1,const Standard_Integer e2,const Standard_Integer f1,const Standard_Integer f2);
20 void seteeff(const Standard_Boolean b,const Standard_Integer e1,const Standard_Integer e2, const Standard_Integer f1,const Standard_Integer f2)
21 {cout<<"b,e1,e2,f1,f2 : "<<b<<" "<<e1<<","<<e2<<","<<f1<<","<<f2<<endl;TopOpeBRep_SettraceEEFF(b);}
22 void seteefft(const Standard_Integer e1,const Standard_Integer e2, const Standard_Integer f1,const Standard_Integer f2) {seteeff(Standard_True,e1,e2,f1,f2);}
23 void seteefff(const Standard_Integer e1,const Standard_Integer e2, const Standard_Integer f1,const Standard_Integer f2) {seteeff(Standard_False,e1,e2,f1,f2);}
24 #endif
25
26 // modified by NIZHNY-OFV  Thu Apr 18 17:15:38 2002 (S)
27 #include <TopoDS.hxx>
28 #include <TopoDS_Shape.hxx>
29 #include <TopoDS_Solid.hxx>
30 #include <TopoDS_Shell.hxx>
31 #include <TopoDS_Face.hxx>
32 #include <TopoDS_Wire.hxx>
33 #include <TopoDS_Edge.hxx>
34 #include <TopExp_Explorer.hxx>
35 #include <TopTools_IndexedDataMapOfShapeListOfShape.hxx>
36 #include <TopTools_ListOfShape.hxx>
37 #include <TopExp.hxx>
38 #include <gp_Pnt.hxx>
39 #include <gp_Vec.hxx>
40 #include <BRepLib_MakeEdge.hxx>
41 #include <BRepLib_MakeWire.hxx>
42 #include <BRepLib_MakeFace.hxx>
43 #include <BRep_Builder.hxx>
44 #include <BRepAdaptor_Surface.hxx>
45 static Standard_Integer OneShapeIsHalfSpace(const TopoDS_Shape& S1,const TopoDS_Shape& S2);
46 static TopoDS_Solid GetNewSolid(const TopoDS_Shape& S, TopoDS_Face& F);
47 // modified by NIZHNY-OFV  Thu Apr 18 17:16:45 2002 (F)
48
49 //=======================================================================
50 //function : TopOpeBRep_ShapeIntersector
51 //purpose  : 
52 //=======================================================================
53
54 TopOpeBRep_ShapeIntersector::TopOpeBRep_ShapeIntersector()
55 {
56   Reset();
57   myFFIntersector.GetTolerances(myTol1,myTol2);
58   myHBoxTool = FBOX_GetHBoxTool();
59   myFaceScanner.ChangeBoxSort().SetHBoxTool(myHBoxTool);
60   myEdgeScanner.ChangeBoxSort().SetHBoxTool(myHBoxTool);
61 }
62
63 //=======================================================================
64 //function : Reset
65 //purpose  : 
66 //=======================================================================
67
68 void TopOpeBRep_ShapeIntersector::Reset()
69 {
70   myIntersectionDone = Standard_False;
71
72   myFFDone = Standard_False;
73   myFFSameDomain = Standard_False;
74   myEEFFDone = Standard_False;
75   myEFDone = Standard_False;
76   myFEDone = Standard_False;
77   myEEDone = Standard_False;
78
79   myFFInit = Standard_False;
80   myEEFFInit = Standard_False;
81   myEFInit = Standard_False;
82   myFEInit = Standard_False;
83   myEEInit = Standard_False;
84 }
85
86 //=======================================================================
87 //function : Init
88 //purpose  : 
89 //=======================================================================
90
91 void TopOpeBRep_ShapeIntersector::Init
92 (const TopoDS_Shape& S1, const TopoDS_Shape& S2)
93 {
94   Reset();
95   myShape1 = S1;
96   myShape2 = S2;
97 }
98
99 //=======================================================================
100 //function : SetIntersectionDone
101 //purpose  : 
102 //=======================================================================
103
104 void TopOpeBRep_ShapeIntersector::SetIntersectionDone()
105 {
106   myIntersectionDone = (myFFDone || 
107                         myEEFFDone || 
108                         myFEDone || 
109                         myEFDone || 
110                         myEEDone);
111 }
112
113
114 //=======================================================================
115 //function : CurrentGeomShape
116 //purpose  : 
117 //=======================================================================
118
119 const TopoDS_Shape& TopOpeBRep_ShapeIntersector::CurrentGeomShape
120   (const Standard_Integer Index) const
121 {
122   if ( myIntersectionDone ) {
123     if      (myFFDone) {
124       if      ( Index == 1 ) return myFaceScanner.Current();
125       else if ( Index == 2 ) return myFaceExplorer.Current();
126     }
127     else if (myEEFFDone) {
128       if      ( Index == 1 ) return myEdgeScanner.Current();
129       else if ( Index == 2 ) return myEdgeExplorer.Current();
130     }
131     else if (myFEDone) {
132       if      ( Index == 1 ) return myFaceScanner.Current();
133       else if ( Index == 2 ) return myEdgeExplorer.Current();
134     }
135     else if (myEFDone) {
136       if      ( Index == 1 ) return myEdgeScanner.Current();
137       else if ( Index == 2 ) return myFaceExplorer.Current();
138     }
139     else if (myEEDone) {
140       if      ( Index == 1 ) return myEdgeScanner.Current();
141       else if ( Index == 2 ) return myEdgeExplorer.Current();
142     }
143   }
144
145   Standard_Failure::Raise("CurrentGeomShape : no intersection");
146   TopoDS_Shape* bid = new TopoDS_Shape();
147   return *bid;
148 }
149 //modified by NIZNHY-PKV Fri Sep 24 11:02:59 1999 from
150 //=======================================================================
151 //function : RejectedFaces
152 //purpose  : 
153 //=======================================================================
154 void TopOpeBRep_ShapeIntersector::RejectedFaces (const TopoDS_Shape& anObj,
155                                                  const TopoDS_Shape& aReference,
156                                                  TopTools_ListOfShape& aListOfShape)
157 {
158
159   Standard_Integer isHalfSpace = OneShapeIsHalfSpace( anObj, aReference );
160   if( isHalfSpace != 0 )
161     {
162       TopoDS_Face newRejectFace;
163       TopoDS_Solid newSolid;
164       aListOfShape.Clear();
165       
166       if( isHalfSpace == 1 )
167         {
168           newSolid = GetNewSolid( anObj, newRejectFace );
169           Init( newSolid, aReference );
170
171           TopAbs_ShapeEnum tscann = TopAbs_SOLID;
172           TopAbs_ShapeEnum texplo = TopAbs_FACE;
173           myFaceScanner.Clear();
174           myFaceScanner.AddBoxesMakeCOB( aReference, tscann );
175           myFaceExplorer.Init( newSolid, texplo );
176   
177           for(; myFaceExplorer.More(); myFaceExplorer.Next())
178             {
179               TopOpeBRepTool_BoxSort& aBS = myFaceScanner.ChangeBoxSort();
180               if(!aBS.Compare(myFaceExplorer.Current()).More())
181                 {
182                   const TopoDS_Shape& aS=myFaceExplorer.Current();
183                   aListOfShape.Append (aS);
184                 }
185             }
186
187           texplo = TopAbs_EDGE;
188           myFaceScanner.Clear();
189           myFaceScanner.AddBoxesMakeCOB( aReference, tscann );
190           myFaceExplorer.Init( newSolid, texplo );
191
192           for(; myFaceExplorer.More(); myFaceExplorer.Next())
193             {
194               TopOpeBRepTool_BoxSort& aBS = myFaceScanner.ChangeBoxSort();
195               if(!aBS.Compare(myFaceExplorer.Current()).More())
196                 {
197                   const TopoDS_Shape& aS=myFaceExplorer.Current();
198                   aListOfShape.Append (aS);
199                 }
200             }
201         }
202       else
203         {
204           newSolid = GetNewSolid( aReference, newRejectFace );
205           Init( anObj, newSolid );
206
207           TopAbs_ShapeEnum tscann = TopAbs_SOLID;
208           TopAbs_ShapeEnum texplo = TopAbs_FACE;
209           myFaceScanner.Clear();
210           myFaceScanner.AddBoxesMakeCOB( newSolid, tscann );
211           myFaceExplorer.Init( anObj, texplo);
212   
213           for(; myFaceExplorer.More(); myFaceExplorer.Next())
214             {
215               TopOpeBRepTool_BoxSort& aBS = myFaceScanner.ChangeBoxSort();
216               if(!aBS.Compare(myFaceExplorer.Current()).More())
217                 {
218                   const TopoDS_Shape& aS=myFaceExplorer.Current();
219                   aListOfShape.Append (aS);
220                 }
221             }
222
223           texplo = TopAbs_EDGE;
224           myFaceScanner.Clear();
225           myFaceScanner.AddBoxesMakeCOB( newSolid, tscann );
226           myFaceExplorer.Init( anObj, texplo );
227
228           for(; myFaceExplorer.More(); myFaceExplorer.Next())
229             {
230               TopOpeBRepTool_BoxSort& aBS = myFaceScanner.ChangeBoxSort();
231               if(!aBS.Compare(myFaceExplorer.Current()).More())
232                 {
233                   const TopoDS_Shape& aS=myFaceExplorer.Current();
234                   aListOfShape.Append (aS);
235                 }
236             }
237         }
238       // remove all shapes of < newRejectFace > from list
239       TopExp_Explorer ExpRF(newRejectFace, TopAbs_EDGE);
240       for(; ExpRF.More(); ExpRF.Next() )
241         {
242           const TopoDS_Edge& edgef = TopoDS::Edge( ExpRF.Current() );
243           TopTools_ListIteratorOfListOfShape it( aListOfShape );
244           for(; it.More(); it.Next() )
245             {
246               const TopoDS_Shape& shape = it.Value();
247
248               if( shape.ShapeType() != TopAbs_EDGE )
249                 continue;
250
251               const TopoDS_Edge& edgel = TopoDS::Edge( shape );
252               if( edgef.IsSame( edgel ) )
253                 {
254                   aListOfShape.Remove(it);
255                   break;
256                 }
257             }
258         }
259       TopTools_ListIteratorOfListOfShape it( aListOfShape );
260       for(; it.More(); it.Next() )
261         {
262           const TopoDS_Shape& shape = it.Value();
263
264           if( shape.ShapeType() != TopAbs_FACE )
265             continue;
266
267           const TopoDS_Face& facel = TopoDS::Face( shape );
268           if( facel.IsSame( newRejectFace ) )
269             {
270               aListOfShape.Remove(it);
271               break;
272             }
273         }
274       
275       Init(anObj, aReference);
276       return;
277     }
278
279   Init(anObj, aReference);
280
281   aListOfShape.Clear(); 
282   //find faces to reject
283   
284   TopAbs_ShapeEnum tscann = TopAbs_SOLID;
285   TopAbs_ShapeEnum texplo = TopAbs_FACE;
286   myFaceScanner.Clear();
287   myFaceScanner.AddBoxesMakeCOB(aReference,tscann);
288   myFaceExplorer.Init(anObj,texplo);
289   
290   for(; myFaceExplorer.More(); myFaceExplorer.Next()) {
291     TopOpeBRepTool_BoxSort& aBS = myFaceScanner.ChangeBoxSort();
292     if(!aBS.Compare(myFaceExplorer.Current()).More()) {
293       const TopoDS_Shape& aS=myFaceExplorer.Current();
294       aListOfShape.Append (aS);
295     }
296   }
297
298   //modified by NIZHNY-MZV  Wed Apr  5 09:45:17 2000
299   texplo = TopAbs_EDGE;
300   myFaceScanner.Clear();
301   myFaceScanner.AddBoxesMakeCOB(aReference,tscann);
302   myFaceExplorer.Init(anObj,texplo);
303
304   for(; myFaceExplorer.More(); myFaceExplorer.Next()) {
305     TopOpeBRepTool_BoxSort& aBS = myFaceScanner.ChangeBoxSort();
306     if(!aBS.Compare(myFaceExplorer.Current()).More()) {
307       const TopoDS_Shape& aS=myFaceExplorer.Current();
308       aListOfShape.Append (aS);
309     }
310   }
311
312   //modified by NIZHNY-MZV  Wed Apr  5 09:45:17 2000
313 /*  texplo = TopAbs_VERTEX;
314   myFaceScanner.Clear();
315   myFaceScanner.AddBoxesMakeCOB(aReference,tscann);
316   myFaceExplorer.Init(anObj,texplo);
317
318   for(; myFaceExplorer.More(); myFaceExplorer.Next()) {
319     TopOpeBRepTool_BoxSort& aBS = myFaceScanner.ChangeBoxSort();
320     if(!aBS.Compare(myFaceExplorer.Current()).More()) {
321       const TopoDS_Shape& aS=myFaceExplorer.Current();
322       aListOfShape.Append (aS);
323     }
324   }
325 */
326 }
327 //modified by NIZNHY-PKV Fri Sep 24 11:03:02 1999 to
328
329
330
331
332 //=======================================================================
333 //function : InitIntersection
334 //purpose  : 
335 //=======================================================================
336
337   void TopOpeBRep_ShapeIntersector::InitIntersection (const TopoDS_Shape& S1, const TopoDS_Shape& S2)
338 {
339   Init(S1,S2);
340
341   InitFFIntersection();
342   if ( MoreFFCouple() ) return;
343
344   InitFEIntersection();
345   if ( MoreFECouple() ) return;
346
347   InitEFIntersection();
348   if ( MoreEFCouple() ) return;
349 }
350
351
352 //=======================================================================
353 //function : InitIntersection
354 //purpose  : 
355 //=======================================================================
356
357 void TopOpeBRep_ShapeIntersector::InitIntersection
358   (const TopoDS_Shape& S1, const TopoDS_Shape& S2,
359    const TopoDS_Face&  F1, const TopoDS_Face&  F2)
360 {
361   Init(S1,S2);
362
363   myEEFace1 = F1;
364   myEEFace2 = F2;
365
366   InitEEIntersection();
367 }
368
369
370 //=======================================================================
371 //function : MoreIntersection
372 //purpose  : 
373 //=======================================================================
374
375 Standard_Boolean TopOpeBRep_ShapeIntersector::MoreIntersection() const
376 {
377   Standard_Boolean res = myIntersectionDone;
378
379 #ifdef DEB
380   Standard_Integer i1 = Index(1);
381   Standard_Integer i2 = Index(2);
382   if (TopOpeBRep_GettraceSI() && res) {
383     if      ( myFFDone )   cout<<"FF : ";
384     else if ( myEEFFDone ) cout<<"    EE : ";
385     DumpCurrent(1);
386     DumpCurrent(2);
387     if      ( myFFDone && myFFSameDomain ) cout<<"(FF SameDomain)";
388     else if ( myEEFFDone )                 cout<<"(EE of FF SameDomain)";
389     else if ( myEEDone )                   cout<<"EE : ";
390     cout<<endl;
391     if (myEEFFDone) {
392       Standard_Integer ie1 = myEdgeScanner.Index();
393       Standard_Integer ie2 = myEdgeExplorer.Index();
394       Standard_Integer if1 = myFaceScanner.Index();
395       Standard_Integer if2 = myFaceExplorer.Index();
396       cout<<"    trc teeff 1 "<<ie1<<" "<<ie2<<" "<<if1<<" "<<if2<<"; # ie1 ie2 if1 if2"<<endl;
397       Standard_Boolean b = TopOpeBRep_GettraceEEFF(ie1,ie2,if1,if2);
398       if (b) seteefft(ie1,ie2,if1,if2);
399       else   seteefff(ie1,ie2,if1,if2);
400     }
401   }    
402 #endif
403
404   return res;
405 }
406
407
408 //=======================================================================
409 //function : DumpCurrent
410 //purpose  : 
411 //=======================================================================
412
413 void TopOpeBRep_ShapeIntersector::DumpCurrent(const Standard_Integer K) const
414 {
415 #ifdef DEB
416   if      ( myFFDone ) {
417     if      ( K == 1 ) myFaceScanner.DumpCurrent(cout);
418     else if ( K == 2 ) myFaceExplorer.DumpCurrent(cout);
419   }
420   else if ( myEEFFDone ) {
421     if      ( K == 1 ) myEdgeScanner.DumpCurrent(cout);
422     else if ( K == 2 ) myEdgeExplorer.DumpCurrent(cout);
423   }
424   else if ( myFEDone ) {
425     if      ( K == 1 ) myFaceScanner.DumpCurrent(cout);
426     else if ( K == 2 ) myEdgeExplorer.DumpCurrent(cout);
427   }
428   else if ( myEFDone ) {
429     if      ( K == 1 ) myEdgeScanner.DumpCurrent(cout);
430     else if ( K == 2 ) myFaceExplorer.DumpCurrent(cout);
431   }
432   else if ( myEEDone ) {
433     if      ( K == 1 ) myEdgeScanner.DumpCurrent(cout);
434     else if ( K == 2 ) myEdgeExplorer.DumpCurrent(cout);
435   }
436 #endif
437 }
438
439 //=======================================================================
440 //function : Index
441 //purpose  : 
442 //=======================================================================
443
444 Standard_Integer TopOpeBRep_ShapeIntersector::Index
445 (const Standard_Integer K)const
446 {
447   Standard_Integer i = 0;
448 #ifdef DEB
449   if      ( myFFDone ) {
450     if      ( K == 1 ) i = myFaceScanner.Index();
451     else if ( K == 2 ) i = myFaceExplorer.Index();
452   }
453   else if ( myEEFFDone ) {
454     if      ( K == 1 ) i = myEdgeScanner.Index();
455     else if ( K == 2 ) i = myEdgeExplorer.Index();
456   }
457   else if ( myFEDone ) {
458     if      ( K == 1 ) i = myFaceScanner.Index();
459     else if ( K == 2 ) i = myEdgeExplorer.Index();
460   }
461   else if ( myEFDone ) {
462     if      ( K == 1 ) i = myEdgeScanner.Index();
463     else if ( K == 2 ) i = myFaceExplorer.Index();
464   }
465   else if ( myEEDone ) {
466     if      ( K == 1 ) i = myEdgeScanner.Index();
467     else if ( K == 2 ) i = myEdgeExplorer.Index();
468   }
469 #endif
470   return i;
471 }
472
473
474 //=======================================================================
475 //function : NextIntersection
476 //purpose  : 
477 //=======================================================================
478
479 void TopOpeBRep_ShapeIntersector::NextIntersection()
480 {
481   myIntersectionDone = Standard_False;
482
483   if (myFFSameDomain) {
484     // precedant etat du More() : 2 faces samedomain
485     myFFDone = Standard_False;
486     myFFSameDomain = Standard_False;
487     InitEEFFIntersection();
488     FindEEFFIntersection();
489     if ( !myIntersectionDone ) {
490       NextFFCouple();
491       FindFFIntersection();
492     }
493   }
494   else if (myFFDone) {
495     NextFFCouple();
496     FindFFIntersection();
497   }
498   else if ( myEEFFDone ) {
499     NextEEFFCouple();
500     FindEEFFIntersection();
501     if ( !myIntersectionDone ) {
502       NextFFCouple();
503       FindFFIntersection();
504     }
505   }
506   else if ( myFEDone ) {
507     NextFECouple();
508     FindFEIntersection();
509   }
510   else if ( myEFDone ) {
511     NextEFCouple();
512     FindEFIntersection();
513   }
514    else if ( myEEDone ) {
515     NextEECouple();
516     FindEEIntersection();
517   }
518
519   if ( !myIntersectionDone ) {
520     InitFFIntersection();
521   }
522     
523   if ( !myIntersectionDone ) {
524     InitFEIntersection();
525   }
526     
527   if ( !myIntersectionDone ) {
528     InitEFIntersection();
529   }
530
531   if ( !myIntersectionDone ) {
532     if ( !myEEFace1.IsNull() && !myEEFace2.IsNull() ) {
533       InitEEIntersection();
534     }
535   }
536
537 }
538
539
540 // ========
541 // FFFFFFFF
542 // ========
543
544
545 //=======================================================================
546 //function : InitFFIntersection
547 //purpose  : 
548 //=======================================================================
549
550 void TopOpeBRep_ShapeIntersector::InitFFIntersection()
551 {
552  if ( !myFFInit) { 
553    TopAbs_ShapeEnum tscann = TopAbs_FACE;
554    TopAbs_ShapeEnum texplo = TopAbs_FACE;
555    myFaceScanner.Clear();
556    myFaceScanner.AddBoxesMakeCOB(myShape1,tscann);
557    myFaceExplorer.Init(myShape2,texplo);
558    myFaceScanner.Init(myFaceExplorer);
559    FindFFIntersection();
560  }
561  myFFInit = Standard_True;
562 }
563
564
565 //=======================================================================
566 //function : FindFFIntersection
567 //purpose  : 
568 //=======================================================================
569
570 void TopOpeBRep_ShapeIntersector::FindFFIntersection()
571 {
572   myFFDone = Standard_False;
573   myFFSameDomain = Standard_False ;
574
575   while ( MoreFFCouple() ) {
576
577     // The two candidate intersecting GeomShapes GS1,GS2 and their types t1,t2
578     const TopoDS_Shape& GS1 = myFaceScanner.Current();
579     const TopoDS_Shape& GS2 = myFaceExplorer.Current();
580
581 #ifdef DEB
582     SAVFFi1 = myFaceScanner.Index(); SAVFFi2 = myFaceExplorer.Index(); 
583     if (TopOpeBRep_GettraceSI()) {
584       Standard_Integer i1 = myFaceScanner.Index();
585       Standard_Integer i2 = myFaceExplorer.Index();
586       cout<<"?? FF : ";
587       myFaceScanner.DumpCurrent(cout); myFaceExplorer.DumpCurrent(cout);
588       cout<<endl;
589     }    
590 #endif
591
592     const TopOpeBRepTool_BoxSort& BS = myFaceScanner.BoxSort();
593     const Bnd_Box& B1 = BS.Box(GS1);
594     const Bnd_Box& B2 = BS.Box(GS2);
595     myFFIntersector.Perform(GS1,GS2,B1,B2);
596     Standard_Boolean ok = myFFIntersector.IsDone(); //xpu210998
597     if (!ok) {
598       NextFFCouple();
599       continue;
600     }
601
602     myFFSameDomain = myFFIntersector.SameDomain();
603
604     if (myFFSameDomain) {
605       myFFDone = Standard_True;
606       break;
607     }
608     else {
609       myFFDone = ! (myFFIntersector.IsEmpty());
610       
611       // update face/face intersection tolerances
612       if (myFFDone) {
613         Standard_Real tol1,tol2;
614         myFFIntersector.GetTolerances(tol1,tol2);
615         myTol1 = Max(myTol1,tol1); myTol2 = Max(myTol2,tol2);
616       }
617       
618       if ( myFFDone ) {
619         break;
620       }
621     }
622
623     NextFFCouple();
624   }
625
626   SetIntersectionDone();
627 }
628
629
630 //=======================================================================
631 //function : MoreFFCouple
632 //purpose  : 
633 //=======================================================================
634
635 Standard_Boolean TopOpeBRep_ShapeIntersector::MoreFFCouple() const
636 {
637   Standard_Boolean more1 = myFaceScanner.More();
638   Standard_Boolean more2 = myFaceExplorer.More();
639   return (more1 && more2);
640 }
641
642
643 //=======================================================================
644 //function : NextFFCouple
645 //purpose  : 
646 //=======================================================================
647
648 void TopOpeBRep_ShapeIntersector::NextFFCouple()
649 {
650   myFaceScanner.Next();
651   Standard_Boolean b1,b2;
652
653   b1 = (!myFaceScanner.More());
654   b2 = (myFaceExplorer.More());
655   while ( b1 && b2 ) {
656     myFaceExplorer.Next();
657     myFaceScanner.Init(myFaceExplorer);
658     b1 = (!myFaceScanner.More());
659     b2 = (myFaceExplorer.More());
660   }
661
662 }
663
664
665 // ========
666 // EEFFEEFF
667 // ========
668
669
670 //=======================================================================
671 //function : InitEEFFIntersection
672 //purpose  : 
673 //=======================================================================
674
675 void TopOpeBRep_ShapeIntersector::InitEEFFIntersection()
676 {
677   // prepare exploration of the edges of the two current SameDomain faces 
678   TopoDS_Shape face1 = myFaceScanner.Current(); // -26-08-96
679   TopoDS_Shape face2 = myFaceExplorer.Current(); // -26-08-96
680
681 #ifdef DEB
682   if (TopOpeBRep_GetcontextFFOR()) {
683     face1.Orientation(TopAbs_FORWARD); //-05/07
684     face2.Orientation(TopAbs_FORWARD); //-05/07
685     cout<<"ctx : InitEEFFIntersection : faces FORWARD"<<endl;
686   }
687 #endif
688
689   const TopOpeBRepTool_BoxSort& BS = myFaceScanner.BoxSort();
690   const Bnd_Box& B1 = BS.Box(face1);
691   const Bnd_Box& B2 = BS.Box(face2);
692   myEEIntersector.SetFaces(face1,face2,B1,B2);
693   
694   TopAbs_ShapeEnum tscann = TopAbs_EDGE;
695   TopAbs_ShapeEnum texplo = TopAbs_EDGE;
696   myEdgeScanner.Clear();
697   myEdgeScanner.AddBoxesMakeCOB(face1,tscann);
698   myEdgeExplorer.Init(face2,texplo);
699   myEdgeScanner.Init(myEdgeExplorer);
700   
701   myEEFFInit = Standard_True;
702 }
703
704
705 //=======================================================================
706 //function : FindEEFFIntersection
707 //purpose  : 
708 //=======================================================================
709
710 void TopOpeBRep_ShapeIntersector::FindEEFFIntersection()
711 {
712   myEEFFDone = Standard_False;
713   while ( MoreEEFFCouple() ) {
714     const TopoDS_Shape& GS1 = myEdgeScanner.Current();
715     const TopoDS_Shape& GS2 = myEdgeExplorer.Current();
716     myEEIntersector.Perform(GS1,GS2);
717
718 #ifdef DEB
719     Standard_Integer i1 = Index(1);
720     Standard_Integer i2 = Index(2);
721     if (TopOpeBRep_GettraceSI() && myEEIntersector.IsEmpty()) {
722       cout<<"    EE : ";
723       myEdgeScanner.DumpCurrent(cout);
724       myEdgeExplorer.DumpCurrent(cout);
725       cout<<"(EE of FF SameDomain)";
726       cout<<" : EMPTY INTERSECTION";
727       cout<<endl;
728     }    
729 #endif
730
731     myEEFFDone = ! (myEEIntersector.IsEmpty());
732     if (myEEFFDone) break;
733     else NextEEFFCouple();
734   }
735   SetIntersectionDone();
736 }
737
738
739 //=======================================================================
740 //function : MoreEEFFCouple
741 //purpose  : 
742 //=======================================================================
743
744 Standard_Boolean TopOpeBRep_ShapeIntersector::MoreEEFFCouple() const
745 {
746   Standard_Boolean more1 = myEdgeScanner.More();
747   Standard_Boolean more2 = myEdgeExplorer.More();
748   return (more1 && more2);
749 }
750
751
752 //=======================================================================
753 //function : NextEEFFCouple
754 //purpose  : 
755 //=======================================================================
756
757 void TopOpeBRep_ShapeIntersector::NextEEFFCouple()
758 {
759   myEdgeScanner.Next();
760   while ( ! myEdgeScanner.More() && myEdgeExplorer.More() ) {
761     myEdgeExplorer.Next();
762     myEdgeScanner.Init(myEdgeExplorer);
763   }
764 }
765
766
767 // ========
768 // FEFEFEFE
769 // ========
770
771
772 //=======================================================================
773 //function : InitFEIntersection
774 //purpose  : 
775 //=======================================================================
776
777 void TopOpeBRep_ShapeIntersector::InitFEIntersection()
778 {
779  if ( !myFEInit) { 
780    TopAbs_ShapeEnum tscann = TopAbs_FACE;
781    TopAbs_ShapeEnum texplo = TopAbs_EDGE;
782    myFaceScanner.Clear(); 
783    myFaceScanner.AddBoxesMakeCOB(myShape1,tscann);
784    myEdgeExplorer.Init(myShape2,texplo,TopAbs_FACE); // NYI defaut de spec
785    myFaceScanner.Init(myEdgeExplorer);
786    FindFEIntersection();
787  }
788  myFEInit = Standard_True;
789 }
790
791
792 //=======================================================================
793 //function : FindFEIntersection
794 //purpose  : 
795 //=======================================================================
796
797 void TopOpeBRep_ShapeIntersector::FindFEIntersection()
798 {
799   myFEDone = Standard_False;
800   while ( MoreFECouple() ) {
801     const TopoDS_Shape& GS1 = myFaceScanner.Current();
802     const TopoDS_Shape& GS2 = myEdgeExplorer.Current();
803     myFEIntersector.Perform(GS1,GS2);
804     myFEDone = ! (myFEIntersector.IsEmpty());
805     if (myFEDone) break;
806     else NextFECouple();
807   }
808   SetIntersectionDone();
809 }
810
811
812 //=======================================================================
813 //function : MoreFECouple
814 //purpose  : 
815 //=======================================================================
816
817 Standard_Boolean TopOpeBRep_ShapeIntersector::MoreFECouple() const
818 {
819   Standard_Boolean more1 = myFaceScanner.More();
820   Standard_Boolean more2 = myEdgeExplorer.More();
821   return (more1 && more2);
822 }
823
824
825 //=======================================================================
826 //function : NextFECouple
827 //purpose  : 
828 //=======================================================================
829
830 void TopOpeBRep_ShapeIntersector::NextFECouple()
831 {
832   myFaceScanner.Next();
833   while ( ! myFaceScanner.More() && myEdgeExplorer.More() ) {
834     myEdgeExplorer.Next();
835     myFaceScanner.Init(myEdgeExplorer);
836   }
837 }
838
839
840 // ========
841 // EFEFEFEF
842 // ========
843
844
845 //=======================================================================
846 //function : InitEFIntersection
847 //purpose  : 
848 //=======================================================================
849
850 void TopOpeBRep_ShapeIntersector::InitEFIntersection()
851 {
852  if ( !myEFInit) { 
853    TopAbs_ShapeEnum tscann = TopAbs_EDGE;
854    TopAbs_ShapeEnum texplo = TopAbs_FACE;
855    myEdgeScanner.Clear(); 
856    myEdgeScanner.AddBoxesMakeCOB(myShape1,tscann, TopAbs_FACE); // NYI defaut de spec
857    myFaceExplorer.Init(myShape2,texplo);
858    myEdgeScanner.Init(myFaceExplorer);
859    FindEFIntersection();
860  }
861  myEFInit = Standard_True;
862
863  
864 //=======================================================================
865 //function : FindEFIntersection
866 //purpose  : 
867 //=======================================================================
868
869 void TopOpeBRep_ShapeIntersector::FindEFIntersection()
870 {
871   myEFDone = Standard_False;
872   while ( MoreEFCouple() ) {
873     const TopoDS_Shape& GS1 = myEdgeScanner.Current();
874     const TopoDS_Shape& GS2 = myFaceExplorer.Current();
875     myFEIntersector.Perform(GS2,GS1);
876     myEFDone = ! (myFEIntersector.IsEmpty());
877     if (myEFDone) break;
878     else NextEFCouple();
879   }
880   SetIntersectionDone();
881 }
882
883
884 //=======================================================================
885 //function : MoreEFCouple
886 //purpose  : 
887 //=======================================================================
888
889 Standard_Boolean TopOpeBRep_ShapeIntersector::MoreEFCouple() const
890 {
891   Standard_Boolean more1 = myEdgeScanner.More();
892   Standard_Boolean more2 = myFaceExplorer.More();
893   return (more1 && more2);
894 }
895
896
897 //=======================================================================
898 //function : NextEFCouple
899 //purpose  : 
900 //=======================================================================
901
902 void TopOpeBRep_ShapeIntersector::NextEFCouple()
903 {
904   myEdgeScanner.Next();
905   while ( ! myEdgeScanner.More() && myFaceExplorer.More() ) {
906     myFaceExplorer.Next();
907     myEdgeScanner.Init(myFaceExplorer);
908   }
909 }
910
911 // ========
912 // EEEEEEEE
913 // ========
914
915 //=======================================================================
916 //function : InitEEIntersection
917 //purpose  : 
918 //=======================================================================
919
920 void TopOpeBRep_ShapeIntersector::InitEEIntersection()
921 {
922   if ( ! myEEInit ) {
923     TopoDS_Shape face1 = myEEFace1.Oriented(TopAbs_FORWARD);
924     TopoDS_Shape face2 = myEEFace2.Oriented(TopAbs_FORWARD);
925     const TopOpeBRepTool_BoxSort& BS = myFaceScanner.BoxSort();
926     const Bnd_Box& B1 = BS.Box(face1);
927     const Bnd_Box& B2 = BS.Box(face2);
928     myEEIntersector.SetFaces(face1,face2,B1,B2);
929
930     TopAbs_ShapeEnum tscann = TopAbs_EDGE;
931     TopAbs_ShapeEnum texplo = TopAbs_EDGE;
932     myEdgeScanner.Clear();
933     myEdgeScanner.AddBoxesMakeCOB(myShape1,tscann);
934     myEdgeExplorer.Init(myShape2,texplo);
935     myEdgeScanner.Init(myEdgeExplorer);
936     FindEEIntersection();
937   }
938   myEEInit = Standard_True;
939 }
940
941
942 //=======================================================================
943 //function : FindEEIntersection
944 //purpose  : 
945 //=======================================================================
946
947 void TopOpeBRep_ShapeIntersector::FindEEIntersection()
948 {
949   myEEDone = Standard_False;
950   while ( MoreEECouple() ) {
951     const TopoDS_Shape& GS1 = myEdgeScanner.Current();
952     const TopoDS_Shape& GS2 = myEdgeExplorer.Current();
953     myEEIntersector.Perform(GS1,GS2);
954     myEEDone = ! (myEEIntersector.IsEmpty());
955     if (myEEDone) break;
956     else NextEECouple();
957   }
958   SetIntersectionDone();
959 }
960
961
962 //=======================================================================
963 //function : MoreEECouple
964 //purpose  : 
965 //=======================================================================
966
967 Standard_Boolean TopOpeBRep_ShapeIntersector::MoreEECouple() const
968 {
969   Standard_Boolean more1 = myEdgeScanner.More();
970   Standard_Boolean more2 = myEdgeExplorer.More();
971   return (more1 && more2);
972 }
973
974
975 //=======================================================================
976 //function : NextEECouple
977 //purpose  : 
978 //=======================================================================
979
980 void TopOpeBRep_ShapeIntersector::NextEECouple()
981 {
982   myEdgeScanner.Next();
983   while ( ! myEdgeScanner.More() && myEdgeExplorer.More() ) {
984     myEdgeExplorer.Next();
985     myEdgeScanner.Init(myEdgeExplorer);
986   }
987 }
988
989
990 //=======================================================================
991 //function : Shape
992 //purpose  : 
993 //=======================================================================
994
995 const TopoDS_Shape& TopOpeBRep_ShapeIntersector::Shape
996   ( const Standard_Integer Index )const
997 {
998   if      ( Index == 1 ) return myShape1;
999   else if ( Index == 2 ) return myShape2;
1000
1001   Standard_Failure::Raise("ShapeIntersector : no shape");
1002   TopoDS_Shape* bid = new TopoDS_Shape();
1003   return *bid;
1004 }
1005
1006
1007 //=======================================================================
1008 //function : ChangeFacesIntersector
1009 //purpose  : 
1010 //=======================================================================
1011
1012 TopOpeBRep_FacesIntersector& 
1013 TopOpeBRep_ShapeIntersector::ChangeFacesIntersector()
1014 { return myFFIntersector; }
1015
1016
1017 //=======================================================================
1018 //function : ChangeEdgesIntersector
1019 //purpose  : 
1020 //=======================================================================
1021
1022 TopOpeBRep_EdgesIntersector& 
1023 TopOpeBRep_ShapeIntersector::ChangeEdgesIntersector()
1024 { return myEEIntersector; }
1025
1026
1027 //=======================================================================
1028 //function : ChangeFaceEdgeIntersector
1029 //purpose  : 
1030 //=======================================================================
1031
1032 TopOpeBRep_FaceEdgeIntersector& 
1033 TopOpeBRep_ShapeIntersector::ChangeFaceEdgeIntersector()
1034 { return myFEIntersector; }
1035
1036
1037 //=======================================================================
1038 //function : GetTolerances
1039 //purpose  : 
1040 //=======================================================================
1041
1042 void TopOpeBRep_ShapeIntersector::GetTolerances(Standard_Real& tol1,
1043                                                 Standard_Real& tol2)const
1044 { tol1 = myTol1; tol2 = myTol2; }
1045
1046
1047
1048
1049 //=======================================================================
1050 //function : IsHalfSpaceShape
1051 //purpose  : tries to define if one of solids is a half space object
1052 //           returns:
1053 //                    0 - no half spaces ( default )
1054 //                    1 - half space is S1
1055 //                    2 - half space is S2
1056 //=======================================================================
1057 static Standard_Integer OneShapeIsHalfSpace(const TopoDS_Shape& S1,const TopoDS_Shape& S2)
1058 {
1059   Standard_Integer result = 0;
1060
1061   if( S1.ShapeType() == TopAbs_SOLID && S2.ShapeType() == TopAbs_SOLID )
1062     {
1063       TopExp_Explorer ExpSol1(S1, TopAbs_FACE);
1064       TopExp_Explorer ExpSol2(S2, TopAbs_FACE);
1065       Standard_Integer NbFacesSol1 = 0;
1066       Standard_Integer NbFacesSol2 = 0;
1067
1068       for(; ExpSol1.More(); ExpSol1.Next() )
1069         NbFacesSol1++;
1070
1071       for(; ExpSol2.More(); ExpSol2.Next() )
1072         NbFacesSol2++;
1073
1074       if( NbFacesSol1 == 0 || NbFacesSol2 == 0 )  // strange solids!!!
1075         return result;
1076       if( NbFacesSol1 == 1 && NbFacesSol2 == 1 )  // both shapes are half spaces ???
1077         return result;
1078
1079       if( (NbFacesSol1 == 1 && NbFacesSol2 >= 2) || (NbFacesSol2 == 1 && NbFacesSol1 >= 2) )
1080         {
1081           // if one solid has shell consisted of only a face but other one has valid closed
1082           // shell we can detect current boolean operation as operation with half space object.
1083           // if shell of second solid is not valid too we cann't detect what kind of objects
1084           // we try to perform. in this case we do nothing and just return. 
1085
1086           // but before we must avoid shperes, toruses and solids with a face biult on spherical surfaces
1087           // of revolution (SSRFS) - solids with shell of one face:
1088           // sphere (U: 0, 2PI) (V: -PI/2, PI/2),
1089           // torus  (U: 0, 2PI) (V: 0, 2PI).
1090           // SSRFS  (U period = (PI), 2PI) (V period = (PI), 2PI)
1091           // these solids are not halfspaces.
1092
1093           TopExp_Explorer SolidExplorer;
1094           TopoDS_Face testFace;
1095
1096           if( NbFacesSol1 == 1 )
1097             {
1098               for( SolidExplorer.Init(S1, TopAbs_FACE); SolidExplorer.More(); SolidExplorer.Next() )
1099                 testFace = TopoDS::Face( SolidExplorer.Current() );
1100             }
1101           else
1102             {
1103               for( SolidExplorer.Init(S2, TopAbs_FACE); SolidExplorer.More(); SolidExplorer.Next() )
1104                 testFace = TopoDS::Face( SolidExplorer.Current() );
1105             }
1106
1107           BRepAdaptor_Surface FSurf( testFace );
1108           Standard_Boolean SolidIsSphereOrTorus = Standard_False;
1109           
1110           if( FSurf.GetType() == GeomAbs_Sphere ||  FSurf.GetType() == GeomAbs_Torus )
1111             {
1112               Standard_Real minU = FSurf.FirstUParameter();
1113               Standard_Real maxU = FSurf.LastUParameter();
1114               Standard_Real minV = FSurf.FirstVParameter();
1115               Standard_Real maxV = FSurf.LastVParameter();
1116               Standard_Boolean yesU = ( Abs(minU - 0.) < 1.e-9 && Abs(maxU - 2*M_PI) < 1.e-9 );
1117               Standard_Boolean yesV = ( FSurf.GetType() == GeomAbs_Sphere ) ?
1118                 ( Abs(minV - (-M_PI/2.)) < 1.e-9 && Abs(maxV - M_PI/2.) < 1.e-9 ) :
1119                 ( Abs(minV - 0.) < 1.e-9 && Abs(maxV - 2*M_PI) < 1.e-9 );
1120               SolidIsSphereOrTorus = ( yesU && yesV );
1121             }
1122
1123           if( FSurf.GetType() == GeomAbs_SurfaceOfRevolution )
1124             {
1125               Standard_Boolean areBothPeriodic = ( FSurf.IsUPeriodic() && FSurf.IsVPeriodic() );
1126               if( areBothPeriodic )
1127                 {
1128                   Standard_Boolean yesU = ( Abs(FSurf.UPeriod() - M_PI) < 1.e-9 || Abs(FSurf.UPeriod() - 2*M_PI) < 1.e-9 );
1129                   Standard_Boolean yesV = ( Abs(FSurf.VPeriod() - M_PI) < 1.e-9 || Abs(FSurf.VPeriod() - 2*M_PI) < 1.e-9 );
1130                   SolidIsSphereOrTorus = ( yesU && yesV );
1131                 }
1132             }
1133
1134           if( SolidIsSphereOrTorus )
1135               return result;
1136
1137           Standard_Boolean SecondShellOk = Standard_True;
1138           TopTools_IndexedDataMapOfShapeListOfShape aMapEF;
1139           aMapEF.Clear();
1140           Standard_Integer NbEdges = 0, NbFaces = 0, iE = 0;
1141
1142           if( NbFacesSol1 == 1 )
1143             TopExp::MapShapesAndAncestors(S2, TopAbs_EDGE, TopAbs_FACE, aMapEF);
1144           else
1145             TopExp::MapShapesAndAncestors(S1, TopAbs_EDGE, TopAbs_FACE, aMapEF);
1146
1147           NbEdges = aMapEF.Extent();
1148           for( iE = 1; iE <= NbEdges; iE++)
1149             {
1150               const TopTools_ListOfShape& listFaces = aMapEF.FindFromIndex( iE );
1151               NbFaces = listFaces.Extent();
1152               if( NbFaces != 2 )
1153                 {
1154                   SecondShellOk = Standard_False;
1155                   break;
1156                 }
1157             }
1158           aMapEF.Clear();
1159
1160           if( SecondShellOk )
1161             result = (NbFacesSol1 == 1) ? 1 : 2;
1162         }
1163       else
1164         {
1165           // ************************** IMPORTANT !!! ************************************
1166           // both shells are of more than 2 faces. if both solids have invalid shells
1167           // we do nothing and just return. on the other hand if only one shell is valid
1168           // currently we should suppose that solid with invalid shell is a half space too,
1169           // but this is not always true.
1170           //
1171           // so this suggestion must be developed carefully. while we don't classify it!
1172           // *****************************************************************************
1173         }
1174 #ifdef DEB
1175       if( result != 0 )
1176         cout << "# one of the SOLIDs probably is a HALF SPACE" << endl;
1177 #endif
1178     }
1179
1180   return result;
1181 }
1182
1183 //=======================================================================
1184 //function : GetNewSolid
1185 //purpose  : rebuild halfspace solid adding new "face on infinity"
1186 //           to build correct bounding box to classify carefully
1187 //           "rejected shapes".
1188 //=======================================================================
1189 static TopoDS_Solid GetNewSolid(const TopoDS_Shape& S, TopoDS_Face& F)
1190 {
1191   // "new solid" is a new halfspace solid consists of two faces now: the first face is a face
1192   // used to build halfspace solid and the second face is a new "face on infinity" specially
1193   // created to constuct correct bounding box around halfspace solid with bounds more wide than
1194   // previous one.
1195
1196   // the following algorithm is used:
1197   // 1. get face used to build halfspace solid and calculate its normal, Min/Max (U,V) parameters,
1198   //    four points lying on the surface of the face inside its restrictions, surface, tolerance
1199   //    and location.
1200   // 2. define the direction into the halfspace solid and project four points along this direction
1201   //    on infinite distance. then use those points to create "face on infinity".
1202   // 3. build new shell with two new faces and new "halfspace solid".
1203   // 4. return this solid and "face on infinity" to remove it and all its subshapes from the list
1204   //    of rejected shapes.
1205
1206   TopExp_Explorer ShapeExplorer;
1207
1208   TopoDS_Face hsFace;
1209   
1210   for( ShapeExplorer.Init(S, TopAbs_FACE); ShapeExplorer.More(); ShapeExplorer.Next() )
1211     hsFace = TopoDS::Face( ShapeExplorer.Current() );
1212
1213   BRepAdaptor_Surface ASurf( hsFace );
1214   
1215   Standard_Real MinU = ASurf.FirstUParameter();
1216   Standard_Real MaxU = ASurf.LastUParameter();
1217   Standard_Real MinV = ASurf.FirstVParameter();
1218   Standard_Real MaxV = ASurf.LastUParameter();
1219
1220   Standard_Real MidU = (MaxU + MinU) * 0.5;
1221   Standard_Real MidV = (MaxV + MinV) * 0.5;
1222
1223   gp_Pnt MidP;
1224   gp_Vec SurfDU, SurfDV;
1225   ASurf.D1( MidU, MidV, MidP, SurfDU, SurfDV );
1226   
1227   gp_Vec Normal = SurfDU.Crossed( SurfDV );
1228
1229   if( hsFace.Orientation() == TopAbs_FORWARD )
1230     Normal *= -1.e+10;
1231   else
1232     Normal *= 1.e+10;
1233
1234   Standard_Real Pu1 = MinU + Abs( (MaxU - MinU) / 4. );
1235   Standard_Real Pu2 = MinU + Abs( (MaxU - MinU) / 4. * 3. );
1236   Standard_Real Pv1 = MinV + Abs( (MaxV - MinV) / 4. );
1237   Standard_Real Pv2 = MinV + Abs( (MaxV - MinV) / 4. * 3. );
1238
1239   gp_Pnt P1, P2, P3, P4;
1240   ASurf.D0( Pu1, Pv1, P1 );
1241   ASurf.D0( Pu1, Pv2, P2 );
1242   ASurf.D0( Pu2, Pv1, P3 );
1243   ASurf.D0( Pu2, Pv2, P4 ); 
1244
1245   P1.Translate( Normal );
1246   P2.Translate( Normal );
1247   P3.Translate( Normal );
1248   P4.Translate( Normal );
1249
1250   BRepLib_MakeEdge mke1( P1, P2 );
1251   BRepLib_MakeEdge mke2( P2, P4 );
1252   BRepLib_MakeEdge mke3( P4, P3 );
1253   BRepLib_MakeEdge mke4( P3, P1 );
1254
1255   TopoDS_Edge e1 = mke1.Edge();
1256   TopoDS_Edge e2 = mke2.Edge();
1257   TopoDS_Edge e3 = mke3.Edge();
1258   TopoDS_Edge e4 = mke4.Edge();
1259
1260   BRepLib_MakeWire mkw( e1, e2, e3, e4 );
1261   TopoDS_Wire w = mkw.Wire();
1262
1263   BRepLib_MakeFace mkf( w );
1264   TopoDS_Face infFace = mkf.Face();
1265   
1266   TopoDS_Shell newShell;
1267   TopoDS_Solid newSolid;
1268
1269   BRep_Builder newShellBuilder;
1270   newShellBuilder.MakeShell( newShell );
1271   newShellBuilder.Add( newShell, hsFace );
1272   newShellBuilder.Add( newShell, infFace );
1273
1274   BRep_Builder newSolidBuilder;
1275   newSolidBuilder.MakeSolid( newSolid );
1276   newSolidBuilder.Add( newSolid, newShell );
1277
1278   F = infFace;
1279   return newSolid;
1280 }