93502ce8c83eca1d76c9d6762a6e3965172313b7
[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   if (TopOpeBRep_GettraceSI() && res) {
381     if      ( myFFDone )   cout<<"FF : ";
382     else if ( myEEFFDone ) cout<<"    EE : ";
383     DumpCurrent(1);
384     DumpCurrent(2);
385     if      ( myFFDone && myFFSameDomain ) cout<<"(FF SameDomain)";
386     else if ( myEEFFDone )                 cout<<"(EE of FF SameDomain)";
387     else if ( myEEDone )                   cout<<"EE : ";
388     cout<<endl;
389     if (myEEFFDone) {
390       Standard_Integer ie1 = myEdgeScanner.Index();
391       Standard_Integer ie2 = myEdgeExplorer.Index();
392       Standard_Integer if1 = myFaceScanner.Index();
393       Standard_Integer if2 = myFaceExplorer.Index();
394       cout<<"    trc teeff 1 "<<ie1<<" "<<ie2<<" "<<if1<<" "<<if2<<"; # ie1 ie2 if1 if2"<<endl;
395       Standard_Boolean b = TopOpeBRep_GettraceEEFF(ie1,ie2,if1,if2);
396       if (b) seteefft(ie1,ie2,if1,if2);
397       else   seteefff(ie1,ie2,if1,if2);
398     }
399   }    
400 #endif
401
402   return res;
403 }
404
405
406 //=======================================================================
407 //function : DumpCurrent
408 //purpose  : 
409 //=======================================================================
410
411 void TopOpeBRep_ShapeIntersector::DumpCurrent(const Standard_Integer K) const
412 {
413 #ifdef DEB
414   if      ( myFFDone ) {
415     if      ( K == 1 ) myFaceScanner.DumpCurrent(cout);
416     else if ( K == 2 ) myFaceExplorer.DumpCurrent(cout);
417   }
418   else if ( myEEFFDone ) {
419     if      ( K == 1 ) myEdgeScanner.DumpCurrent(cout);
420     else if ( K == 2 ) myEdgeExplorer.DumpCurrent(cout);
421   }
422   else if ( myFEDone ) {
423     if      ( K == 1 ) myFaceScanner.DumpCurrent(cout);
424     else if ( K == 2 ) myEdgeExplorer.DumpCurrent(cout);
425   }
426   else if ( myEFDone ) {
427     if      ( K == 1 ) myEdgeScanner.DumpCurrent(cout);
428     else if ( K == 2 ) myFaceExplorer.DumpCurrent(cout);
429   }
430   else if ( myEEDone ) {
431     if      ( K == 1 ) myEdgeScanner.DumpCurrent(cout);
432     else if ( K == 2 ) myEdgeExplorer.DumpCurrent(cout);
433   }
434 #endif
435 }
436
437 //=======================================================================
438 //function : Index
439 //purpose  : 
440 //=======================================================================
441
442 Standard_Integer TopOpeBRep_ShapeIntersector::Index
443 (const Standard_Integer K)const
444 {
445   Standard_Integer i = 0;
446 #ifdef DEB
447   if      ( myFFDone ) {
448     if      ( K == 1 ) i = myFaceScanner.Index();
449     else if ( K == 2 ) i = myFaceExplorer.Index();
450   }
451   else if ( myEEFFDone ) {
452     if      ( K == 1 ) i = myEdgeScanner.Index();
453     else if ( K == 2 ) i = myEdgeExplorer.Index();
454   }
455   else if ( myFEDone ) {
456     if      ( K == 1 ) i = myFaceScanner.Index();
457     else if ( K == 2 ) i = myEdgeExplorer.Index();
458   }
459   else if ( myEFDone ) {
460     if      ( K == 1 ) i = myEdgeScanner.Index();
461     else if ( K == 2 ) i = myFaceExplorer.Index();
462   }
463   else if ( myEEDone ) {
464     if      ( K == 1 ) i = myEdgeScanner.Index();
465     else if ( K == 2 ) i = myEdgeExplorer.Index();
466   }
467 #endif
468   return i;
469 }
470
471
472 //=======================================================================
473 //function : NextIntersection
474 //purpose  : 
475 //=======================================================================
476
477 void TopOpeBRep_ShapeIntersector::NextIntersection()
478 {
479   myIntersectionDone = Standard_False;
480
481   if (myFFSameDomain) {
482     // precedant etat du More() : 2 faces samedomain
483     myFFDone = Standard_False;
484     myFFSameDomain = Standard_False;
485     InitEEFFIntersection();
486     FindEEFFIntersection();
487     if ( !myIntersectionDone ) {
488       NextFFCouple();
489       FindFFIntersection();
490     }
491   }
492   else if (myFFDone) {
493     NextFFCouple();
494     FindFFIntersection();
495   }
496   else if ( myEEFFDone ) {
497     NextEEFFCouple();
498     FindEEFFIntersection();
499     if ( !myIntersectionDone ) {
500       NextFFCouple();
501       FindFFIntersection();
502     }
503   }
504   else if ( myFEDone ) {
505     NextFECouple();
506     FindFEIntersection();
507   }
508   else if ( myEFDone ) {
509     NextEFCouple();
510     FindEFIntersection();
511   }
512    else if ( myEEDone ) {
513     NextEECouple();
514     FindEEIntersection();
515   }
516
517   if ( !myIntersectionDone ) {
518     InitFFIntersection();
519   }
520     
521   if ( !myIntersectionDone ) {
522     InitFEIntersection();
523   }
524     
525   if ( !myIntersectionDone ) {
526     InitEFIntersection();
527   }
528
529   if ( !myIntersectionDone ) {
530     if ( !myEEFace1.IsNull() && !myEEFace2.IsNull() ) {
531       InitEEIntersection();
532     }
533   }
534
535 }
536
537
538 // ========
539 // FFFFFFFF
540 // ========
541
542
543 //=======================================================================
544 //function : InitFFIntersection
545 //purpose  : 
546 //=======================================================================
547
548 void TopOpeBRep_ShapeIntersector::InitFFIntersection()
549 {
550  if ( !myFFInit) { 
551    TopAbs_ShapeEnum tscann = TopAbs_FACE;
552    TopAbs_ShapeEnum texplo = TopAbs_FACE;
553    myFaceScanner.Clear();
554    myFaceScanner.AddBoxesMakeCOB(myShape1,tscann);
555    myFaceExplorer.Init(myShape2,texplo);
556    myFaceScanner.Init(myFaceExplorer);
557    FindFFIntersection();
558  }
559  myFFInit = Standard_True;
560 }
561
562
563 //=======================================================================
564 //function : FindFFIntersection
565 //purpose  : 
566 //=======================================================================
567
568 void TopOpeBRep_ShapeIntersector::FindFFIntersection()
569 {
570   myFFDone = Standard_False;
571   myFFSameDomain = Standard_False ;
572
573   while ( MoreFFCouple() ) {
574
575     // The two candidate intersecting GeomShapes GS1,GS2 and their types t1,t2
576     const TopoDS_Shape& GS1 = myFaceScanner.Current();
577     const TopoDS_Shape& GS2 = myFaceExplorer.Current();
578
579 #ifdef DEB
580     SAVFFi1 = myFaceScanner.Index(); SAVFFi2 = myFaceExplorer.Index(); 
581     if (TopOpeBRep_GettraceSI()) {
582       cout<<"?? FF : ";
583       myFaceScanner.DumpCurrent(cout); myFaceExplorer.DumpCurrent(cout);
584       cout<<endl;
585     }    
586 #endif
587
588     const TopOpeBRepTool_BoxSort& BS = myFaceScanner.BoxSort();
589     const Bnd_Box& B1 = BS.Box(GS1);
590     const Bnd_Box& B2 = BS.Box(GS2);
591     myFFIntersector.Perform(GS1,GS2,B1,B2);
592     Standard_Boolean ok = myFFIntersector.IsDone(); //xpu210998
593     if (!ok) {
594       NextFFCouple();
595       continue;
596     }
597
598     myFFSameDomain = myFFIntersector.SameDomain();
599
600     if (myFFSameDomain) {
601       myFFDone = Standard_True;
602       break;
603     }
604     else {
605       myFFDone = ! (myFFIntersector.IsEmpty());
606       
607       // update face/face intersection tolerances
608       if (myFFDone) {
609         Standard_Real tol1,tol2;
610         myFFIntersector.GetTolerances(tol1,tol2);
611         myTol1 = Max(myTol1,tol1); myTol2 = Max(myTol2,tol2);
612       }
613       
614       if ( myFFDone ) {
615         break;
616       }
617     }
618
619     NextFFCouple();
620   }
621
622   SetIntersectionDone();
623 }
624
625
626 //=======================================================================
627 //function : MoreFFCouple
628 //purpose  : 
629 //=======================================================================
630
631 Standard_Boolean TopOpeBRep_ShapeIntersector::MoreFFCouple() const
632 {
633   Standard_Boolean more1 = myFaceScanner.More();
634   Standard_Boolean more2 = myFaceExplorer.More();
635   return (more1 && more2);
636 }
637
638
639 //=======================================================================
640 //function : NextFFCouple
641 //purpose  : 
642 //=======================================================================
643
644 void TopOpeBRep_ShapeIntersector::NextFFCouple()
645 {
646   myFaceScanner.Next();
647   Standard_Boolean b1,b2;
648
649   b1 = (!myFaceScanner.More());
650   b2 = (myFaceExplorer.More());
651   while ( b1 && b2 ) {
652     myFaceExplorer.Next();
653     myFaceScanner.Init(myFaceExplorer);
654     b1 = (!myFaceScanner.More());
655     b2 = (myFaceExplorer.More());
656   }
657
658 }
659
660
661 // ========
662 // EEFFEEFF
663 // ========
664
665
666 //=======================================================================
667 //function : InitEEFFIntersection
668 //purpose  : 
669 //=======================================================================
670
671 void TopOpeBRep_ShapeIntersector::InitEEFFIntersection()
672 {
673   // prepare exploration of the edges of the two current SameDomain faces 
674   TopoDS_Shape face1 = myFaceScanner.Current(); // -26-08-96
675   TopoDS_Shape face2 = myFaceExplorer.Current(); // -26-08-96
676
677 #ifdef DEB
678   if (TopOpeBRep_GetcontextFFOR()) {
679     face1.Orientation(TopAbs_FORWARD); //-05/07
680     face2.Orientation(TopAbs_FORWARD); //-05/07
681     cout<<"ctx : InitEEFFIntersection : faces FORWARD"<<endl;
682   }
683 #endif
684
685   const TopOpeBRepTool_BoxSort& BS = myFaceScanner.BoxSort();
686   const Bnd_Box& B1 = BS.Box(face1);
687   const Bnd_Box& B2 = BS.Box(face2);
688   myEEIntersector.SetFaces(face1,face2,B1,B2);
689   
690   TopAbs_ShapeEnum tscann = TopAbs_EDGE;
691   TopAbs_ShapeEnum texplo = TopAbs_EDGE;
692   myEdgeScanner.Clear();
693   myEdgeScanner.AddBoxesMakeCOB(face1,tscann);
694   myEdgeExplorer.Init(face2,texplo);
695   myEdgeScanner.Init(myEdgeExplorer);
696   
697   myEEFFInit = Standard_True;
698 }
699
700
701 //=======================================================================
702 //function : FindEEFFIntersection
703 //purpose  : 
704 //=======================================================================
705
706 void TopOpeBRep_ShapeIntersector::FindEEFFIntersection()
707 {
708   myEEFFDone = Standard_False;
709   while ( MoreEEFFCouple() ) {
710     const TopoDS_Shape& GS1 = myEdgeScanner.Current();
711     const TopoDS_Shape& GS2 = myEdgeExplorer.Current();
712     myEEIntersector.Perform(GS1,GS2);
713
714 #ifdef DEB
715     if (TopOpeBRep_GettraceSI() && myEEIntersector.IsEmpty()) {
716       cout<<"    EE : ";
717       myEdgeScanner.DumpCurrent(cout);
718       myEdgeExplorer.DumpCurrent(cout);
719       cout<<"(EE of FF SameDomain)";
720       cout<<" : EMPTY INTERSECTION";
721       cout<<endl;
722     }    
723 #endif
724
725     myEEFFDone = ! (myEEIntersector.IsEmpty());
726     if (myEEFFDone) break;
727     else NextEEFFCouple();
728   }
729   SetIntersectionDone();
730 }
731
732
733 //=======================================================================
734 //function : MoreEEFFCouple
735 //purpose  : 
736 //=======================================================================
737
738 Standard_Boolean TopOpeBRep_ShapeIntersector::MoreEEFFCouple() const
739 {
740   Standard_Boolean more1 = myEdgeScanner.More();
741   Standard_Boolean more2 = myEdgeExplorer.More();
742   return (more1 && more2);
743 }
744
745
746 //=======================================================================
747 //function : NextEEFFCouple
748 //purpose  : 
749 //=======================================================================
750
751 void TopOpeBRep_ShapeIntersector::NextEEFFCouple()
752 {
753   myEdgeScanner.Next();
754   while ( ! myEdgeScanner.More() && myEdgeExplorer.More() ) {
755     myEdgeExplorer.Next();
756     myEdgeScanner.Init(myEdgeExplorer);
757   }
758 }
759
760
761 // ========
762 // FEFEFEFE
763 // ========
764
765
766 //=======================================================================
767 //function : InitFEIntersection
768 //purpose  : 
769 //=======================================================================
770
771 void TopOpeBRep_ShapeIntersector::InitFEIntersection()
772 {
773  if ( !myFEInit) { 
774    TopAbs_ShapeEnum tscann = TopAbs_FACE;
775    TopAbs_ShapeEnum texplo = TopAbs_EDGE;
776    myFaceScanner.Clear(); 
777    myFaceScanner.AddBoxesMakeCOB(myShape1,tscann);
778    myEdgeExplorer.Init(myShape2,texplo,TopAbs_FACE); // NYI defaut de spec
779    myFaceScanner.Init(myEdgeExplorer);
780    FindFEIntersection();
781  }
782  myFEInit = Standard_True;
783 }
784
785
786 //=======================================================================
787 //function : FindFEIntersection
788 //purpose  : 
789 //=======================================================================
790
791 void TopOpeBRep_ShapeIntersector::FindFEIntersection()
792 {
793   myFEDone = Standard_False;
794   while ( MoreFECouple() ) {
795     const TopoDS_Shape& GS1 = myFaceScanner.Current();
796     const TopoDS_Shape& GS2 = myEdgeExplorer.Current();
797     myFEIntersector.Perform(GS1,GS2);
798     myFEDone = ! (myFEIntersector.IsEmpty());
799     if (myFEDone) break;
800     else NextFECouple();
801   }
802   SetIntersectionDone();
803 }
804
805
806 //=======================================================================
807 //function : MoreFECouple
808 //purpose  : 
809 //=======================================================================
810
811 Standard_Boolean TopOpeBRep_ShapeIntersector::MoreFECouple() const
812 {
813   Standard_Boolean more1 = myFaceScanner.More();
814   Standard_Boolean more2 = myEdgeExplorer.More();
815   return (more1 && more2);
816 }
817
818
819 //=======================================================================
820 //function : NextFECouple
821 //purpose  : 
822 //=======================================================================
823
824 void TopOpeBRep_ShapeIntersector::NextFECouple()
825 {
826   myFaceScanner.Next();
827   while ( ! myFaceScanner.More() && myEdgeExplorer.More() ) {
828     myEdgeExplorer.Next();
829     myFaceScanner.Init(myEdgeExplorer);
830   }
831 }
832
833
834 // ========
835 // EFEFEFEF
836 // ========
837
838
839 //=======================================================================
840 //function : InitEFIntersection
841 //purpose  : 
842 //=======================================================================
843
844 void TopOpeBRep_ShapeIntersector::InitEFIntersection()
845 {
846  if ( !myEFInit) { 
847    TopAbs_ShapeEnum tscann = TopAbs_EDGE;
848    TopAbs_ShapeEnum texplo = TopAbs_FACE;
849    myEdgeScanner.Clear(); 
850    myEdgeScanner.AddBoxesMakeCOB(myShape1,tscann, TopAbs_FACE); // NYI defaut de spec
851    myFaceExplorer.Init(myShape2,texplo);
852    myEdgeScanner.Init(myFaceExplorer);
853    FindEFIntersection();
854  }
855  myEFInit = Standard_True;
856
857  
858 //=======================================================================
859 //function : FindEFIntersection
860 //purpose  : 
861 //=======================================================================
862
863 void TopOpeBRep_ShapeIntersector::FindEFIntersection()
864 {
865   myEFDone = Standard_False;
866   while ( MoreEFCouple() ) {
867     const TopoDS_Shape& GS1 = myEdgeScanner.Current();
868     const TopoDS_Shape& GS2 = myFaceExplorer.Current();
869     myFEIntersector.Perform(GS2,GS1);
870     myEFDone = ! (myFEIntersector.IsEmpty());
871     if (myEFDone) break;
872     else NextEFCouple();
873   }
874   SetIntersectionDone();
875 }
876
877
878 //=======================================================================
879 //function : MoreEFCouple
880 //purpose  : 
881 //=======================================================================
882
883 Standard_Boolean TopOpeBRep_ShapeIntersector::MoreEFCouple() const
884 {
885   Standard_Boolean more1 = myEdgeScanner.More();
886   Standard_Boolean more2 = myFaceExplorer.More();
887   return (more1 && more2);
888 }
889
890
891 //=======================================================================
892 //function : NextEFCouple
893 //purpose  : 
894 //=======================================================================
895
896 void TopOpeBRep_ShapeIntersector::NextEFCouple()
897 {
898   myEdgeScanner.Next();
899   while ( ! myEdgeScanner.More() && myFaceExplorer.More() ) {
900     myFaceExplorer.Next();
901     myEdgeScanner.Init(myFaceExplorer);
902   }
903 }
904
905 // ========
906 // EEEEEEEE
907 // ========
908
909 //=======================================================================
910 //function : InitEEIntersection
911 //purpose  : 
912 //=======================================================================
913
914 void TopOpeBRep_ShapeIntersector::InitEEIntersection()
915 {
916   if ( ! myEEInit ) {
917     TopoDS_Shape face1 = myEEFace1.Oriented(TopAbs_FORWARD);
918     TopoDS_Shape face2 = myEEFace2.Oriented(TopAbs_FORWARD);
919     const TopOpeBRepTool_BoxSort& BS = myFaceScanner.BoxSort();
920     const Bnd_Box& B1 = BS.Box(face1);
921     const Bnd_Box& B2 = BS.Box(face2);
922     myEEIntersector.SetFaces(face1,face2,B1,B2);
923
924     TopAbs_ShapeEnum tscann = TopAbs_EDGE;
925     TopAbs_ShapeEnum texplo = TopAbs_EDGE;
926     myEdgeScanner.Clear();
927     myEdgeScanner.AddBoxesMakeCOB(myShape1,tscann);
928     myEdgeExplorer.Init(myShape2,texplo);
929     myEdgeScanner.Init(myEdgeExplorer);
930     FindEEIntersection();
931   }
932   myEEInit = Standard_True;
933 }
934
935
936 //=======================================================================
937 //function : FindEEIntersection
938 //purpose  : 
939 //=======================================================================
940
941 void TopOpeBRep_ShapeIntersector::FindEEIntersection()
942 {
943   myEEDone = Standard_False;
944   while ( MoreEECouple() ) {
945     const TopoDS_Shape& GS1 = myEdgeScanner.Current();
946     const TopoDS_Shape& GS2 = myEdgeExplorer.Current();
947     myEEIntersector.Perform(GS1,GS2);
948     myEEDone = ! (myEEIntersector.IsEmpty());
949     if (myEEDone) break;
950     else NextEECouple();
951   }
952   SetIntersectionDone();
953 }
954
955
956 //=======================================================================
957 //function : MoreEECouple
958 //purpose  : 
959 //=======================================================================
960
961 Standard_Boolean TopOpeBRep_ShapeIntersector::MoreEECouple() const
962 {
963   Standard_Boolean more1 = myEdgeScanner.More();
964   Standard_Boolean more2 = myEdgeExplorer.More();
965   return (more1 && more2);
966 }
967
968
969 //=======================================================================
970 //function : NextEECouple
971 //purpose  : 
972 //=======================================================================
973
974 void TopOpeBRep_ShapeIntersector::NextEECouple()
975 {
976   myEdgeScanner.Next();
977   while ( ! myEdgeScanner.More() && myEdgeExplorer.More() ) {
978     myEdgeExplorer.Next();
979     myEdgeScanner.Init(myEdgeExplorer);
980   }
981 }
982
983
984 //=======================================================================
985 //function : Shape
986 //purpose  : 
987 //=======================================================================
988
989 const TopoDS_Shape& TopOpeBRep_ShapeIntersector::Shape
990   ( const Standard_Integer Index )const
991 {
992   if      ( Index == 1 ) return myShape1;
993   else if ( Index == 2 ) return myShape2;
994
995   Standard_Failure::Raise("ShapeIntersector : no shape");
996   TopoDS_Shape* bid = new TopoDS_Shape();
997   return *bid;
998 }
999
1000
1001 //=======================================================================
1002 //function : ChangeFacesIntersector
1003 //purpose  : 
1004 //=======================================================================
1005
1006 TopOpeBRep_FacesIntersector& 
1007 TopOpeBRep_ShapeIntersector::ChangeFacesIntersector()
1008 { return myFFIntersector; }
1009
1010
1011 //=======================================================================
1012 //function : ChangeEdgesIntersector
1013 //purpose  : 
1014 //=======================================================================
1015
1016 TopOpeBRep_EdgesIntersector& 
1017 TopOpeBRep_ShapeIntersector::ChangeEdgesIntersector()
1018 { return myEEIntersector; }
1019
1020
1021 //=======================================================================
1022 //function : ChangeFaceEdgeIntersector
1023 //purpose  : 
1024 //=======================================================================
1025
1026 TopOpeBRep_FaceEdgeIntersector& 
1027 TopOpeBRep_ShapeIntersector::ChangeFaceEdgeIntersector()
1028 { return myFEIntersector; }
1029
1030
1031 //=======================================================================
1032 //function : GetTolerances
1033 //purpose  : 
1034 //=======================================================================
1035
1036 void TopOpeBRep_ShapeIntersector::GetTolerances(Standard_Real& tol1,
1037                                                 Standard_Real& tol2)const
1038 { tol1 = myTol1; tol2 = myTol2; }
1039
1040
1041
1042
1043 //=======================================================================
1044 //function : IsHalfSpaceShape
1045 //purpose  : tries to define if one of solids is a half space object
1046 //           returns:
1047 //                    0 - no half spaces ( default )
1048 //                    1 - half space is S1
1049 //                    2 - half space is S2
1050 //=======================================================================
1051 static Standard_Integer OneShapeIsHalfSpace(const TopoDS_Shape& S1,const TopoDS_Shape& S2)
1052 {
1053   Standard_Integer result = 0;
1054
1055   if( S1.ShapeType() == TopAbs_SOLID && S2.ShapeType() == TopAbs_SOLID )
1056     {
1057       TopExp_Explorer ExpSol1(S1, TopAbs_FACE);
1058       TopExp_Explorer ExpSol2(S2, TopAbs_FACE);
1059       Standard_Integer NbFacesSol1 = 0;
1060       Standard_Integer NbFacesSol2 = 0;
1061
1062       for(; ExpSol1.More(); ExpSol1.Next() )
1063         NbFacesSol1++;
1064
1065       for(; ExpSol2.More(); ExpSol2.Next() )
1066         NbFacesSol2++;
1067
1068       if( NbFacesSol1 == 0 || NbFacesSol2 == 0 )  // strange solids!!!
1069         return result;
1070       if( NbFacesSol1 == 1 && NbFacesSol2 == 1 )  // both shapes are half spaces ???
1071         return result;
1072
1073       if( (NbFacesSol1 == 1 && NbFacesSol2 >= 2) || (NbFacesSol2 == 1 && NbFacesSol1 >= 2) )
1074         {
1075           // if one solid has shell consisted of only a face but other one has valid closed
1076           // shell we can detect current boolean operation as operation with half space object.
1077           // if shell of second solid is not valid too we cann't detect what kind of objects
1078           // we try to perform. in this case we do nothing and just return. 
1079
1080           // but before we must avoid shperes, toruses and solids with a face biult on spherical surfaces
1081           // of revolution (SSRFS) - solids with shell of one face:
1082           // sphere (U: 0, 2PI) (V: -PI/2, PI/2),
1083           // torus  (U: 0, 2PI) (V: 0, 2PI).
1084           // SSRFS  (U period = (PI), 2PI) (V period = (PI), 2PI)
1085           // these solids are not halfspaces.
1086
1087           TopExp_Explorer SolidExplorer;
1088           TopoDS_Face testFace;
1089
1090           if( NbFacesSol1 == 1 )
1091             {
1092               for( SolidExplorer.Init(S1, TopAbs_FACE); SolidExplorer.More(); SolidExplorer.Next() )
1093                 testFace = TopoDS::Face( SolidExplorer.Current() );
1094             }
1095           else
1096             {
1097               for( SolidExplorer.Init(S2, TopAbs_FACE); SolidExplorer.More(); SolidExplorer.Next() )
1098                 testFace = TopoDS::Face( SolidExplorer.Current() );
1099             }
1100
1101           BRepAdaptor_Surface FSurf( testFace );
1102           Standard_Boolean SolidIsSphereOrTorus = Standard_False;
1103           
1104           if( FSurf.GetType() == GeomAbs_Sphere ||  FSurf.GetType() == GeomAbs_Torus )
1105             {
1106               Standard_Real minU = FSurf.FirstUParameter();
1107               Standard_Real maxU = FSurf.LastUParameter();
1108               Standard_Real minV = FSurf.FirstVParameter();
1109               Standard_Real maxV = FSurf.LastVParameter();
1110               Standard_Boolean yesU = ( Abs(minU - 0.) < 1.e-9 && Abs(maxU - 2*M_PI) < 1.e-9 );
1111               Standard_Boolean yesV = ( FSurf.GetType() == GeomAbs_Sphere ) ?
1112                 ( Abs(minV - (-M_PI/2.)) < 1.e-9 && Abs(maxV - M_PI/2.) < 1.e-9 ) :
1113                 ( Abs(minV - 0.) < 1.e-9 && Abs(maxV - 2*M_PI) < 1.e-9 );
1114               SolidIsSphereOrTorus = ( yesU && yesV );
1115             }
1116
1117           if( FSurf.GetType() == GeomAbs_SurfaceOfRevolution )
1118             {
1119               Standard_Boolean areBothPeriodic = ( FSurf.IsUPeriodic() && FSurf.IsVPeriodic() );
1120               if( areBothPeriodic )
1121                 {
1122                   Standard_Boolean yesU = ( Abs(FSurf.UPeriod() - M_PI) < 1.e-9 || Abs(FSurf.UPeriod() - 2*M_PI) < 1.e-9 );
1123                   Standard_Boolean yesV = ( Abs(FSurf.VPeriod() - M_PI) < 1.e-9 || Abs(FSurf.VPeriod() - 2*M_PI) < 1.e-9 );
1124                   SolidIsSphereOrTorus = ( yesU && yesV );
1125                 }
1126             }
1127
1128           if( SolidIsSphereOrTorus )
1129               return result;
1130
1131           Standard_Boolean SecondShellOk = Standard_True;
1132           TopTools_IndexedDataMapOfShapeListOfShape aMapEF;
1133           aMapEF.Clear();
1134           Standard_Integer NbEdges = 0, NbFaces = 0, iE = 0;
1135
1136           if( NbFacesSol1 == 1 )
1137             TopExp::MapShapesAndAncestors(S2, TopAbs_EDGE, TopAbs_FACE, aMapEF);
1138           else
1139             TopExp::MapShapesAndAncestors(S1, TopAbs_EDGE, TopAbs_FACE, aMapEF);
1140
1141           NbEdges = aMapEF.Extent();
1142           for( iE = 1; iE <= NbEdges; iE++)
1143             {
1144               const TopTools_ListOfShape& listFaces = aMapEF.FindFromIndex( iE );
1145               NbFaces = listFaces.Extent();
1146               if( NbFaces != 2 )
1147                 {
1148                   SecondShellOk = Standard_False;
1149                   break;
1150                 }
1151             }
1152           aMapEF.Clear();
1153
1154           if( SecondShellOk )
1155             result = (NbFacesSol1 == 1) ? 1 : 2;
1156         }
1157       else
1158         {
1159           // ************************** IMPORTANT !!! ************************************
1160           // both shells are of more than 2 faces. if both solids have invalid shells
1161           // we do nothing and just return. on the other hand if only one shell is valid
1162           // currently we should suppose that solid with invalid shell is a half space too,
1163           // but this is not always true.
1164           //
1165           // so this suggestion must be developed carefully. while we don't classify it!
1166           // *****************************************************************************
1167         }
1168 #ifdef DEB
1169       if( result != 0 )
1170         cout << "# one of the SOLIDs probably is a HALF SPACE" << endl;
1171 #endif
1172     }
1173
1174   return result;
1175 }
1176
1177 //=======================================================================
1178 //function : GetNewSolid
1179 //purpose  : rebuild halfspace solid adding new "face on infinity"
1180 //           to build correct bounding box to classify carefully
1181 //           "rejected shapes".
1182 //=======================================================================
1183 static TopoDS_Solid GetNewSolid(const TopoDS_Shape& S, TopoDS_Face& F)
1184 {
1185   // "new solid" is a new halfspace solid consists of two faces now: the first face is a face
1186   // used to build halfspace solid and the second face is a new "face on infinity" specially
1187   // created to constuct correct bounding box around halfspace solid with bounds more wide than
1188   // previous one.
1189
1190   // the following algorithm is used:
1191   // 1. get face used to build halfspace solid and calculate its normal, Min/Max (U,V) parameters,
1192   //    four points lying on the surface of the face inside its restrictions, surface, tolerance
1193   //    and location.
1194   // 2. define the direction into the halfspace solid and project four points along this direction
1195   //    on infinite distance. then use those points to create "face on infinity".
1196   // 3. build new shell with two new faces and new "halfspace solid".
1197   // 4. return this solid and "face on infinity" to remove it and all its subshapes from the list
1198   //    of rejected shapes.
1199
1200   TopExp_Explorer ShapeExplorer;
1201
1202   TopoDS_Face hsFace;
1203   
1204   for( ShapeExplorer.Init(S, TopAbs_FACE); ShapeExplorer.More(); ShapeExplorer.Next() )
1205     hsFace = TopoDS::Face( ShapeExplorer.Current() );
1206
1207   BRepAdaptor_Surface ASurf( hsFace );
1208   
1209   Standard_Real MinU = ASurf.FirstUParameter();
1210   Standard_Real MaxU = ASurf.LastUParameter();
1211   Standard_Real MinV = ASurf.FirstVParameter();
1212   Standard_Real MaxV = ASurf.LastUParameter();
1213
1214   Standard_Real MidU = (MaxU + MinU) * 0.5;
1215   Standard_Real MidV = (MaxV + MinV) * 0.5;
1216
1217   gp_Pnt MidP;
1218   gp_Vec SurfDU, SurfDV;
1219   ASurf.D1( MidU, MidV, MidP, SurfDU, SurfDV );
1220   
1221   gp_Vec Normal = SurfDU.Crossed( SurfDV );
1222
1223   if( hsFace.Orientation() == TopAbs_FORWARD )
1224     Normal *= -1.e+10;
1225   else
1226     Normal *= 1.e+10;
1227
1228   Standard_Real Pu1 = MinU + Abs( (MaxU - MinU) / 4. );
1229   Standard_Real Pu2 = MinU + Abs( (MaxU - MinU) / 4. * 3. );
1230   Standard_Real Pv1 = MinV + Abs( (MaxV - MinV) / 4. );
1231   Standard_Real Pv2 = MinV + Abs( (MaxV - MinV) / 4. * 3. );
1232
1233   gp_Pnt P1, P2, P3, P4;
1234   ASurf.D0( Pu1, Pv1, P1 );
1235   ASurf.D0( Pu1, Pv2, P2 );
1236   ASurf.D0( Pu2, Pv1, P3 );
1237   ASurf.D0( Pu2, Pv2, P4 ); 
1238
1239   P1.Translate( Normal );
1240   P2.Translate( Normal );
1241   P3.Translate( Normal );
1242   P4.Translate( Normal );
1243
1244   BRepLib_MakeEdge mke1( P1, P2 );
1245   BRepLib_MakeEdge mke2( P2, P4 );
1246   BRepLib_MakeEdge mke3( P4, P3 );
1247   BRepLib_MakeEdge mke4( P3, P1 );
1248
1249   TopoDS_Edge e1 = mke1.Edge();
1250   TopoDS_Edge e2 = mke2.Edge();
1251   TopoDS_Edge e3 = mke3.Edge();
1252   TopoDS_Edge e4 = mke4.Edge();
1253
1254   BRepLib_MakeWire mkw( e1, e2, e3, e4 );
1255   TopoDS_Wire w = mkw.Wire();
1256
1257   BRepLib_MakeFace mkf( w );
1258   TopoDS_Face infFace = mkf.Face();
1259   
1260   TopoDS_Shell newShell;
1261   TopoDS_Solid newSolid;
1262
1263   BRep_Builder newShellBuilder;
1264   newShellBuilder.MakeShell( newShell );
1265   newShellBuilder.Add( newShell, hsFace );
1266   newShellBuilder.Add( newShell, infFace );
1267
1268   BRep_Builder newSolidBuilder;
1269   newSolidBuilder.MakeSolid( newSolid );
1270   newSolidBuilder.Add( newSolid, newShell );
1271
1272   F = infFace;
1273   return newSolid;
1274 }