b7088012a4e0c38b74a3e58b2dee37e878d59647
[occt.git] / src / BOPTools / BOPTools_PaveFiller.cxx
1 // File:        BOPTools_PaveFiller.cxx
2 // Created:     Thu Mar 7 14:20:31 2001
3 // Author:      Peter KURNEV
4 //              <pkv@irinox>
5
6
7 #include <BOPTools_PaveFiller.ixx>
8
9 #include <stdio.h>
10
11 #include <Standard_Failure.hxx>
12 #include <Precision.hxx>
13
14 #include <Geom_Curve.hxx>
15
16 #include <TColStd_MapOfInteger.hxx>
17
18 #include <BRep_Tool.hxx>
19 #include <BRep_Builder.hxx>
20
21 #include <TopoDS.hxx>
22 #include <TopoDS_Shape.hxx>
23 #include <TopoDS_Edge.hxx>
24 #include <TopoDS_Vertex.hxx>
25
26 #include <IntTools_Tools.hxx>
27 #include <IntTools_EdgeEdge.hxx>
28 #include <IntTools_Range.hxx>
29 #include <IntTools_ShrunkRange.hxx>
30 #include <IntTools_EdgeEdge.hxx>
31 #include <IntTools_SequenceOfCommonPrts.hxx>
32 #include <IntTools_CommonPrt.hxx>
33 #include <IntTools_SequenceOfRanges.hxx>
34
35 #include <BooleanOperations_ShapesDataStructure.hxx>
36 #include <BooleanOperations_AncestorsSeqAndSuccessorsSeq.hxx>
37 #include <BooleanOperations_OnceExplorer.hxx>
38
39 #include <BOPTools_InterferencePool.hxx>
40 #include <BOPTools_IteratorOfCoupleOfShape.hxx>
41 #include <BOPTools_ListIteratorOfListOfInterference.hxx>
42 #include <BOPTools_InterferenceLine.hxx>
43 #include <BOPTools_Interference.hxx>
44 #include <BOPTools_VVInterference.hxx>
45 #include <BOPTools_VEInterference.hxx>
46 #include <BOPTools_EEInterference.hxx>
47 #include <BOPTools_VSInterference.hxx>
48 #include <BOPTools_CArray1OfVEInterference.hxx>
49 #include <BOPTools_CArray1OfVVInterference.hxx>
50 #include <BOPTools_CArray1OfEEInterference.hxx>
51 #include <BOPTools_CArray1OfVSInterference.hxx>
52 #include <BOPTools_Tools.hxx>
53 #include <BOPTools_Pave.hxx>
54 #include <BOPTools_PaveSet.hxx>
55 #include <BOPTools_PaveBlockIterator.hxx>
56 #include <BOPTools_ListOfPave.hxx>
57 #include <BOPTools_ListIteratorOfListOfPave.hxx>
58 #include <BOPTools_ListOfPaveBlock.hxx>
59 #include <BOPTools_ListIteratorOfListOfPaveBlock.hxx>
60 #include <BOPTools_CommonBlock.hxx>
61 #include <BOPTools_ListOfCommonBlock.hxx>
62 #include <BOPTools_CommonBlockAPI.hxx>
63 #include <BOPTools_ListOfCoupleOfInteger.hxx>
64
65 #include <BRepExtrema_DistShapeShape.hxx>
66 #include <BOPTools_IntersectionStatus.hxx>
67 #include <BOPTools_HArray2OfIntersectionStatus.hxx>
68
69 #include <BOPTColStd_Failure.hxx>
70 #include <BOPTColStd_Dump.hxx>
71
72 //=======================================================================
73 // function: BOPTools_PavePoolFiller::BOPTools_PavePoolFiller
74 // purpose: 
75 //=======================================================================
76   BOPTools_PaveFiller::BOPTools_PaveFiller()
77 {
78   myIsDone=Standard_False;
79   myIntrPool=NULL;
80   myDS=NULL;
81   myNbSources=0;
82   myNbEdges=0;
83 }
84
85 //=======================================================================
86 // function: BOPTools_PavePoolFiller::BOPTools_PavePoolFiller
87 // purpose: 
88 //=======================================================================
89   BOPTools_PaveFiller::BOPTools_PaveFiller(const BOPTools_InterferencePool& aPool)
90 {
91   myIsDone=Standard_False;
92   void* p=(void*) &aPool;
93   myIntrPool=(BOPTools_InterferencePool*) p;
94   myDS=myIntrPool->DS();
95   myNbSources=myDS->NumberOfShapesOfTheObject()+myDS->NumberOfShapesOfTheTool();
96   myNbEdges=myDS->NbEdges();
97 }
98
99 //=======================================================================
100 // function: Constructor
101 // purpose: 
102 //=======================================================================
103   BOPTools_PaveFiller::BOPTools_PaveFiller
104       (const BOPTools_InterferencePool&        theIP,
105        const BOPTools_SSIntersectionAttribute& theSectionAttribute)
106 {
107   myIsDone=Standard_False;
108   myIntrPool = (BOPTools_PInterferencePool) &theIP;
109   myDS = myIntrPool->DS();
110   myNbSources=myDS->NumberOfShapesOfTheObject()+myDS->NumberOfShapesOfTheTool();
111   myNbEdges=myDS->NbEdges();
112   mySectionAttribute = theSectionAttribute;
113 }
114
115 //=======================================================================
116 // function: SetInterferencePool
117 // purpose: 
118 //=======================================================================
119   void BOPTools_PaveFiller::SetInterferencePool(const BOPTools_InterferencePool& aPool)
120 {
121   myIsDone=Standard_False;
122   void* p=(void*) &aPool;
123   myIntrPool=(BOPTools_InterferencePool*) p;
124   myDS=myIntrPool->DS();
125   myNbSources=myDS->NumberOfShapesOfTheObject()+myDS->NumberOfShapesOfTheTool();
126   myNbEdges=myDS->NbEdges();
127 }
128
129 //=======================================================================
130 // function: Destroy
131 // purpose: 
132 //=======================================================================
133   void BOPTools_PaveFiller::Destroy()
134 {
135 }
136
137 //=======================================================================
138 // function: SetSectionAttribute
139 // purpose: 
140 //=======================================================================
141    void BOPTools_PaveFiller::SetSectionAttribute
142     (const BOPTools_SSIntersectionAttribute& anAtt) 
143 {
144   mySectionAttribute=anAtt;
145 }
146 //=======================================================================
147 // function: SectionAttribute
148 // purpose: 
149 //=======================================================================
150   const BOPTools_SSIntersectionAttribute& BOPTools_PaveFiller::SectionAttribute() const
151 {
152   return mySectionAttribute;
153 }
154 //=======================================================================
155 // function: SetContext
156 // purpose: 
157 //=======================================================================
158 void BOPTools_PaveFiller::SetContext(const Handle(IntTools_Context)& aContext) 
159 {
160   myContext=aContext;
161 }
162 //=======================================================================
163 // function: Context
164 // purpose: 
165 //=======================================================================
166 const Handle(IntTools_Context)& BOPTools_PaveFiller::Context() const
167 {
168   return myContext;
169 }
170 /*
171 //=======================================================================
172 // function: ChangeContext
173 // purpose: 
174 //=======================================================================
175   IntTools_Context& BOPTools_PaveFiller::ChangeContext() 
176 {
177   return myContext;
178 }
179 */
180 //=======================================================================
181 // function: Perform
182 // purpose: 
183 //=======================================================================
184   void BOPTools_PaveFiller::Perform()
185 {
186   try {
187     //
188     if (myContext.IsNull()) {
189       myContext=new IntTools_Context;
190     }
191     //
192     // 0. Prepare the IteratorOfCoupleOfShape
193     myDSIt.SetDataStructure(myDS);
194     //
195     // 1.VV
196     PerformVV();
197     PerformNewVertices();
198     //
199     // 2.VE
200     myPavePool.Resize (myNbEdges);
201     PrepareEdges();
202     PerformVE();
203     //
204     // 3.VF
205     PerformVF();
206     //
207     // 4.EE
208     myCommonBlockPool.Resize (myNbEdges);
209     mySplitShapesPool.Resize (myNbEdges);
210     myPavePoolNew    .Resize (myNbEdges);
211     
212     PreparePaveBlocks(TopAbs_VERTEX, TopAbs_EDGE);
213     PreparePaveBlocks(TopAbs_EDGE, TopAbs_EDGE);
214     
215     PerformEE();
216     
217     RefinePavePool ();
218     myPavePoolNew.Destroy();
219     myPavePoolNew    .Resize (myNbEdges);
220     //
221     // 5.EF
222     PreparePaveBlocks(TopAbs_EDGE, TopAbs_FACE);
223     
224     PerformEF();
225     RefinePavePool();
226     // 
227     myPavePoolNew.Destroy();
228
229     //     MakeSplitEdges ();
230     //     DoSDEdges();
231     //
232     // 6. FF
233     PerformFF ();
234
235     PutPavesOnCurves();
236
237     MakeSplitEdges ();
238     DoSDEdges();
239     
240     MakeBlocks();
241
242     MakeSectionEdges();
243     //
244     MakeAloneVertices();
245     //
246   } // end of try block
247
248   catch (BOPTColStd_Failure& x) {
249     cout << x.Message() << endl << flush;
250   }
251
252 }
253
254 //=======================================================================
255 // function: PartialPerform
256 // purpose: 
257 //=======================================================================
258   void BOPTools_PaveFiller::PartialPerform(const TColStd_SetOfInteger& anObjSubSet,
259                                            const TColStd_SetOfInteger& aToolSubSet)
260 {
261   try {
262     //
263     if (myContext.IsNull()) {
264       myContext=new IntTools_Context;
265     }
266     //
267     //
268     // 0. Prepare the IteratorOfCoupleOfShape
269     myDSIt.SetDataStructure(myDS);
270     //Fill TableOfIntersectionStatus
271     Standard_Integer i, j;
272     Standard_Integer iObjF, iObjL, iToolF, iToolL;
273     myDS->ObjectRange(iObjF, iObjL);
274     myDS->ToolRange(iToolF, iToolL);
275     for(i = iObjF; i <= iObjL; ++i) {
276       for(j = iToolF; j <= iToolL; ++j) {
277         if(!anObjSubSet.Contains(i) || !aToolSubSet.Contains(j)) {
278           myDSIt.SetIntersectionStatus(i, j, BOPTools_NONINTERSECTED);
279         }
280       }
281     }
282     //
283     // 1.VV
284     PerformVV();
285     PerformNewVertices();
286     //
287     // 2.VE
288     myPavePool.Resize (myNbEdges);
289     PrepareEdges();
290     PerformVE();
291     //
292     // 3.VF
293     PerformVF();
294     //
295     // 4.EE
296     myCommonBlockPool.Resize (myNbEdges);
297     mySplitShapesPool.Resize (myNbEdges);
298     myPavePoolNew    .Resize (myNbEdges);
299     
300     PreparePaveBlocks(TopAbs_VERTEX, TopAbs_EDGE);
301     PreparePaveBlocks(TopAbs_EDGE, TopAbs_EDGE);
302     
303     PerformEE();
304     
305     RefinePavePool ();
306     myPavePoolNew.Destroy();
307     myPavePoolNew    .Resize (myNbEdges);
308     //
309     // 5.EF
310     PreparePaveBlocks(TopAbs_EDGE, TopAbs_FACE);
311     
312     PerformEF();
313     RefinePavePool();
314     // 
315     myPavePoolNew.Destroy();
316
317     //     MakeSplitEdges ();
318     //     DoSDEdges();
319     //
320     // 6. FF
321     PerformFF ();
322
323     //
324   } // end of try block
325
326   catch (BOPTColStd_Failure& x) {
327     cout << x.Message() << endl << flush;
328   }
329
330 }
331
332 //=======================================================================
333 // function: ToCompletePerform
334 // purpose: 
335 //=======================================================================
336   void BOPTools_PaveFiller::ToCompletePerform()
337 {
338   try {
339     //
340     if (myContext.IsNull()) {
341       myContext=new IntTools_Context;
342     }
343     //
344     PutPavesOnCurves();
345
346     MakeSplitEdges ();
347     DoSDEdges();
348
349     MakeBlocks();
350
351     MakeSectionEdges();
352     //
353     MakeAloneVertices();
354   } // end of try block
355
356   catch (BOPTColStd_Failure& x) {
357     cout << x.Message() << endl << flush;
358   }
359 }
360
361 //=======================================================================
362 // function: PerformVE
363 // purpose: 
364 //=======================================================================
365   void BOPTools_PaveFiller::PerformVE() 
366 {
367   myIsDone=Standard_False;
368   
369   Standard_Integer n1, n2, anIndexIn, aFlag, aWhat, aWith, aNbVEs, aBlockLength;
370   Standard_Real aT;
371   //
372   BOPTools_CArray1OfVEInterference& aVEs=myIntrPool->VEInterferences();
373   //
374   // V/E Interferences  [BooleanOperations_VertexEdge]
375   myDSIt.Initialize (TopAbs_VERTEX, TopAbs_EDGE);
376   //
377   //
378   // BlockLength correction
379   aNbVEs=ExpectedPoolLength();
380   aBlockLength=aVEs.BlockLength();
381   if (aNbVEs > aBlockLength) {
382     aVEs.SetBlockLength(aNbVEs);
383   }
384   //
385   for (; myDSIt.More(); myDSIt.Next()) {
386     Standard_Boolean justaddinterference = Standard_False;
387     myDSIt.Current(n1, n2, justaddinterference);
388     
389     if(justaddinterference) {
390       if (!myIntrPool->IsComputed(n1, n2) && !IsSuccesstorsComputed(n1, n2)) {
391         anIndexIn = 0;
392         aWhat = n1; // Vertex
393         aWith = n2; // Edge
394         SortTypes(aWhat, aWith);
395         myIntrPool->AddInterference(aWhat, aWith, BooleanOperations_VertexEdge, anIndexIn);
396       }
397       continue;
398     }
399     //
400     if (! myIntrPool->IsComputed(n1, n2)) {
401       if (! IsSuccesstorsComputed(n1, n2)) {
402         anIndexIn=0;
403         aWhat=n1; // Vertex
404         aWith=n2; // Edge
405         SortTypes(aWhat, aWith);
406
407         const TopoDS_Shape& aS1=myDS->GetShape(aWhat);
408         const TopoDS_Shape& aS2=myDS->GetShape(aWith);
409
410         const TopoDS_Vertex& aV1=TopoDS::Vertex(aS1);
411         const TopoDS_Edge&   aE2=TopoDS::Edge  (aS2);
412         
413         if (BRep_Tool::Degenerated(aE2)){
414           continue;
415         }
416         //
417         aFlag=myContext->ComputeVE (aV1, aE2, aT);
418         //
419         if (!aFlag) {
420           //
421           // Add Interference to the Pool
422           BOPTools_VEInterference anInterf (aWhat, aWith, aT);
423           anIndexIn=aVEs.Append(anInterf);
424           //
425           // Add Pave to the Edge's myPavePool
426           BOPTools_Pave aPave(aWhat, aT, BooleanOperations_VertexEdge);
427           aPave.SetInterference(anIndexIn);
428           BOPTools_PaveSet& aPaveSet= myPavePool(myDS->RefEdge(aWith));
429           aPaveSet.Append(aPave);
430
431           //
432           // State for the Vertex in DS;
433           myDS->SetState (aWhat, BooleanOperations_ON);
434           // Insert Vertex in Interference Object
435           BOPTools_VEInterference& aVE=aVEs(anIndexIn);
436           aVE.SetNewShape(aWhat);
437         }
438         myIntrPool->AddInterference(aWhat, aWith, BooleanOperations_VertexEdge, anIndexIn);
439         //myIntrPool->ComputeResult(n1, n2);
440       }
441     }
442   }
443   myIsDone=Standard_True;
444 }
445 //=======================================================================
446 // function: PerformVF
447 // purpose: 
448 //=======================================================================
449   void BOPTools_PaveFiller::PerformVF() 
450 {
451   myIsDone=Standard_False;
452   
453   Standard_Integer n1, n2, anIndexIn, aFlag, aWhat, aWith, aNbVSs, aBlockLength;
454   Standard_Real aU, aV;
455   //
456   BOPTools_CArray1OfVSInterference& aVSs=myIntrPool->VSInterferences();
457   //
458   // V/E Interferences  [BooleanOperations_VertexEdge]
459   myDSIt.Initialize(TopAbs_VERTEX, TopAbs_FACE);
460   //
461   // BlockLength correction
462   aNbVSs=ExpectedPoolLength();
463   aBlockLength=aVSs.BlockLength();
464   if (aNbVSs > aBlockLength) {
465     aVSs.SetBlockLength(aNbVSs);
466   }
467   //
468   for (; myDSIt.More(); myDSIt.Next()) {
469     Standard_Boolean justaddinterference = Standard_False;
470     myDSIt.Current(n1, n2, justaddinterference);
471
472     if(justaddinterference) {
473       if (!myIntrPool->IsComputed(n1, n2) && !IsSuccesstorsComputed(n1, n2)) {
474         anIndexIn = 0;
475         aWhat = n1; // Vertex
476         aWith = n2; // Face
477         SortTypes(aWhat, aWith);
478         myIntrPool->AddInterference(aWhat, aWith, BooleanOperations_VertexSurface, anIndexIn);
479       }
480       continue;
481     }
482     //
483     if (! myIntrPool->IsComputed(n1, n2)) {
484       if (! IsSuccesstorsComputed(n1, n2)) {
485         anIndexIn=0;
486         aWhat=n1; // Vertex
487         aWith=n2; // Face
488         SortTypes(aWhat, aWith);
489
490         const TopoDS_Shape& aS1=myDS->GetShape(aWhat);
491         const TopoDS_Shape& aS2=myDS->GetShape(aWith);
492
493         const TopoDS_Vertex& aV1=TopoDS::Vertex(aS1);
494         const TopoDS_Face&   aF2=TopoDS::Face  (aS2);
495         //
496         aFlag=myContext->ComputeVS (aV1, aF2, aU, aV);
497         //
498         if (!aFlag) {
499           //
500           // Add Interference to the Pool
501           BOPTools_VSInterference anInterf (aWhat, aWith, aU, aV);
502           anIndexIn=aVSs.Append(anInterf);
503           //
504           // SetState for Vertex in DS;
505           myDS->SetState (aWhat, BooleanOperations_ON);
506           // Insert Vertex in Interference Object
507           BOPTools_VSInterference& aVS=aVSs(anIndexIn);
508           aVS.SetNewShape(aWhat);
509         }
510         myIntrPool->AddInterference(aWhat, aWith, BooleanOperations_VertexSurface, anIndexIn);
511         //myIntrPool->ComputeResult(n1, n2);
512       }
513     }
514   }
515   myIsDone=Standard_True;
516 }
517
518 //=======================================================================
519 // function: PerformEE
520 // purpose: 
521 //=======================================================================
522   void BOPTools_PaveFiller::PerformEE() 
523 {
524   myIsDone=Standard_False;
525   
526   Standard_Integer n1, n2, anIndexIn=0, nE1, nE2, aNbVEs, aBlockLength;
527   Standard_Integer aTmp, aWhat, aWith;
528   //
529   BOPTools_CArray1OfEEInterference& aEEs=myIntrPool->EEInterferences();
530   //
531   // E/E Interferences  [BooleanOperations_EdgeEdge]
532   myDSIt.Initialize(TopAbs_EDGE, TopAbs_EDGE);
533   //
534   //
535   // BlockLength correction
536   aNbVEs=ExpectedPoolLength();
537   aBlockLength=aEEs.BlockLength();
538   if (aNbVEs > aBlockLength) {
539     aEEs.SetBlockLength(aNbVEs);
540   }
541   //
542   for (; myDSIt.More(); myDSIt.Next()) {
543     Standard_Boolean justaddinterference = Standard_False;
544     myDSIt.Current(n1, n2, justaddinterference);
545     
546     if(justaddinterference) {
547       if (!myIntrPool->IsComputed(n1, n2)) {
548         anIndexIn = 0;
549         nE1 = n1; 
550         nE2 = n2; 
551         SortTypes(nE1, nE2);
552         myIntrPool->AddInterference (nE1, nE2, BooleanOperations_EdgeEdge, anIndexIn);
553       }
554       continue;
555     }
556     //
557     if (myIntrPool->IsComputed(n1, n2)) {
558       continue;
559     }
560     //
561     nE1=n1; 
562     nE2=n2; 
563     SortTypes(nE1, nE2);
564     //
565     Standard_Real aTolE1, aTolE2, aDeflection=0.01;
566     Standard_Integer aDiscretize=30;
567
568     const TopoDS_Edge& aE1=TopoDS::Edge(myDS->GetShape(nE1));
569     const TopoDS_Edge& aE2=TopoDS::Edge(myDS->GetShape(nE2));
570     //
571     if (BRep_Tool::Degenerated(aE1)){
572       continue;
573     }
574     if (BRep_Tool::Degenerated(aE2)){
575       continue;
576     }
577     //
578     aTolE1=BRep_Tool::Tolerance(aE1);
579     aTolE2=BRep_Tool::Tolerance(aE2);
580     //
581     BOPTools_ListOfPaveBlock& aLPB1=mySplitShapesPool(myDS->RefEdge(nE1));
582     BOPTools_ListIteratorOfListOfPaveBlock anIt1(aLPB1);
583
584     for (; anIt1.More(); anIt1.Next()) {
585       BOPTools_PaveBlock& aPB1=anIt1.Value();
586       const IntTools_ShrunkRange& aShrunkRange1=aPB1.ShrunkRange();
587     
588       const IntTools_Range& aSR1=aShrunkRange1.ShrunkRange();
589       const Bnd_Box&        aBB1=aShrunkRange1.BndBox();
590
591       BOPTools_ListOfPaveBlock& aLPB2=mySplitShapesPool(myDS->RefEdge(nE2));
592       BOPTools_ListIteratorOfListOfPaveBlock anIt2(aLPB2);
593       
594       for (; anIt2.More(); anIt2.Next()) {
595         BOPTools_PaveBlock& aPB2=anIt2.Value();
596         const IntTools_ShrunkRange& aShrunkRange2=aPB2.ShrunkRange();
597       
598         const IntTools_Range& aSR2=aShrunkRange2.ShrunkRange();
599         const Bnd_Box&        aBB2=aShrunkRange2.BndBox();
600         
601         //////////////////////////////////////////////
602         if (aBB1.IsOut (aBB2)) {
603           continue;
604         }
605         // 
606         // EE
607         IntTools_EdgeEdge aEE;
608         aEE.SetEdge1 (aE1);
609         aEE.SetEdge2 (aE2);
610         aEE.SetTolerance1 (aTolE1);
611         aEE.SetTolerance2 (aTolE2);
612         aEE.SetDiscretize (aDiscretize);
613         aEE.SetDeflection (aDeflection);
614         //
615         IntTools_Range anewSR1 = aSR1;
616         IntTools_Range anewSR2 = aSR2;
617         //
618         aEE.SetRange1(anewSR1);
619         aEE.SetRange2(anewSR2);
620           
621         aEE.Perform();
622         //
623         anIndexIn=0;
624         //
625         if (aEE.IsDone()) {
626           //
627           // reverse order if it is necessary
628           TopoDS_Edge aEWhat, aEWith;
629           aEWhat=aE1;
630           aEWith=aE2;
631           aWhat=nE1;
632           aWith=nE2;
633           if (aEE.Order()) {
634             aTmp=aWhat;
635             aWhat=aWith;
636             aWith=aTmp;
637             aEWhat=aE2;
638             aEWith=aE1;
639           }
640           //
641           const IntTools_SequenceOfCommonPrts& aCPrts=aEE.CommonParts();
642           Standard_Integer i, aNbCPrts;
643           aNbCPrts=aCPrts.Length();
644           //
645           if(aNbCPrts != 0) {
646             char buf[512];
647
648             if(!aShrunkRange1.IsDone()) {
649               sprintf (buf, "Can not obtain ShrunkRange for Edge %d", nE1);
650               throw BOPTColStd_Failure(buf) ;
651             }
652
653             if(!aShrunkRange2.IsDone()) {
654               sprintf (buf, "Can not obtain ShrunkRange for Edge %d", nE2);
655               throw BOPTColStd_Failure(buf) ;
656             }
657           }
658           //
659           for (i=1; i<=aNbCPrts; i++) {
660             const IntTools_CommonPrt& aCPart=aCPrts(i);
661             //
662             anIndexIn=0;
663             //
664             TopAbs_ShapeEnum aType=aCPart.Type();
665             switch (aType) {
666               
667               case TopAbs_VERTEX:  {
668                 
669                 Standard_Real aT1, aT2; 
670                 Standard_Integer aNewShape;
671                 
672                 const IntTools_Range& aR1=aCPart.Range1();
673                 aT1=0.5*(aR1.First()+aR1.Last());
674
675                 if((aCPart.VertexParameter1() >= aR1.First()) &&
676                    (aCPart.VertexParameter1() <= aR1.Last())) {
677                   aT1 = aCPart.VertexParameter1();
678                 }
679
680                 const IntTools_SequenceOfRanges& aRanges2=aCPart.Ranges2();
681                 const IntTools_Range& aR2=aRanges2(1);
682                 aT2=0.5*(aR2.First()+aR2.Last());
683
684                 if((aCPart.VertexParameter2() >= aR2.First()) &&
685                    (aCPart.VertexParameter2() <= aR2.Last())) {
686                   aT2 = aCPart.VertexParameter2();
687                 }
688
689                 TopoDS_Vertex aNewVertex;
690                 BOPTools_Tools::MakeNewVertex(aEWhat, aT1, aEWith, aT2, aNewVertex);
691                 // 
692                 //decide to add pave or not
693                 Standard_Real aTolerance = Precision::PConfusion();
694                 IntTools_Range aRange = (aEE.Order()) ? anewSR2 : anewSR1;
695                 Standard_Boolean firstisonpave1  = (Abs(aRange.First() - aT1) < aTolerance);
696                 if(!firstisonpave1) firstisonpave1 = (Abs(aRange.First() - aR1.First()) < aTolerance);
697
698                 Standard_Boolean firstisonpave2  = (Abs(aRange.Last()  - aT1) < aTolerance);
699                 if(!firstisonpave2) firstisonpave2 = (Abs(aRange.Last()  - aR1.Last()) < aTolerance);
700
701                 aRange = (aEE.Order()) ? anewSR1 : anewSR2;
702                 Standard_Boolean secondisonpave1 = (Abs(aRange.First() - aT2) < aTolerance);
703                 if(!secondisonpave1) secondisonpave1 = (Abs(aRange.First() - aR2.First()) < aTolerance);
704
705                 Standard_Boolean secondisonpave2 = (Abs(aRange.Last()  - aT2) < aTolerance);
706                 if(!secondisonpave2) secondisonpave2 = (Abs(aRange.Last()  - aR2.Last()) < aTolerance);
707                 
708                 if(firstisonpave1 ||
709                    firstisonpave2 ||
710                    secondisonpave1 ||
711                    secondisonpave2) {
712                   //
713                   myIntrPool->AddInterference (aWhat, aWith, BooleanOperations_EdgeEdge, anIndexIn);
714                   continue;
715                 }
716                 // 
717                 else {
718                   Standard_Integer eit = 0;
719                   Standard_Boolean bisoldvertex = Standard_False;
720                   BOPTools_PaveBlock* aPPB1 = (aEE.Order()) ? (BOPTools_PaveBlock*)&aPB2 : (BOPTools_PaveBlock*)&aPB1;
721                   BOPTools_PaveBlock* aPPB2 = (aEE.Order()) ? (BOPTools_PaveBlock*)&aPB1 : (BOPTools_PaveBlock*)&aPB2;
722
723                   for(eit = 0; eit < 2; eit++) {
724                     if(aEE.Order())
725                       aRange = (eit == 0) ? anewSR2 : anewSR1;
726                     else
727                       aRange = (eit == 0) ? anewSR1 : anewSR2;
728                     const TopoDS_Edge& aE = (eit == 0) ? aEWhat : aEWith;
729                     
730                     BOPTools_PaveBlock* aPB = (eit == 0) ? aPPB1 : aPPB2;
731                     TopoDS_Vertex aV1;
732                     TopoDS_Vertex aV2;
733                     Standard_Boolean bisfirst = Standard_False;
734                     Standard_Real aT = (eit == 0) ? aT1 : aT2;
735                     Standard_Real adist1 = fabs(aRange.First() - aT);
736                     Standard_Real adist2 = fabs(aRange.Last() - aT);
737                     bisfirst = (adist1 < adist2);
738                     IntTools_Range aRangeCur;
739
740                     if(bisfirst) {
741                       aV2 = aNewVertex;
742                       aV1 = TopoDS::Vertex(myDS->Shape(aPB->Pave1().Index()));
743                       aRangeCur = IntTools_Range(aPB->Pave1().Param(), aT);
744                     }
745                     else {
746                       aV1 = aNewVertex;
747                       aV2 = TopoDS::Vertex(myDS->Shape(aPB->Pave2().Index()));
748                       aRangeCur = IntTools_Range(aT, aPB->Pave2().Param());
749                     }
750                     Standard_Real aroughtoler = BRep_Tool::Tolerance(aV1) + BRep_Tool::Tolerance(aV2);
751                     aroughtoler *=10.;
752
753                     if((adist1 > aroughtoler) && (adist2 > aroughtoler))
754                        continue;
755                     IntTools_ShrunkRange aSR (aE, aV1, aV2, aRangeCur, myContext);
756
757                     if (!aSR.IsDone()) {
758                       bisoldvertex = Standard_True;
759                       break;
760                     }
761                   }
762
763                   if(bisoldvertex) {
764                     myIntrPool->AddInterference (aWhat, aWith, BooleanOperations_EdgeEdge, anIndexIn);
765                     continue;
766                   }
767                 }
768                 //
769                 // Add Interference to the Pool
770                 BOPTools_EEInterference anInterf (aWhat, aWith, aCPart);
771                 anIndexIn=aEEs.Append(anInterf);
772                 myIntrPool->AddInterference (aWhat, aWith, BooleanOperations_EdgeEdge, anIndexIn);
773                 //
774                 // Insert New Vertex in DS;
775                 // aNewShape is # of DS-line, where aNewVertex is kept
776                 BooleanOperations_AncestorsSeqAndSuccessorsSeq anASSeq; 
777                 myDS->InsertShapeAndAncestorsSuccessors(aNewVertex, anASSeq);
778                 aNewShape=myDS->NumberOfInsertedShapes();
779                 // State of the new Vertex is ON
780                 myDS->SetState (aNewShape, BooleanOperations_ON);
781                 //
782                 // Insert New Vertex in EE Interference
783                 BOPTools_EEInterference& aEEInterf= aEEs(anIndexIn);
784                 aEEInterf.SetNewShape(aNewShape);
785                 //
786                 // Add Paves to the myPavePoolNew
787                 BOPTools_Pave aPave;
788                 aPave.SetInterference(anIndexIn);
789                 aPave.SetType (BooleanOperations_EdgeEdge);
790                 aPave.SetIndex(aNewShape);
791                 
792                 aPave.SetParam(aT1);
793                 BOPTools_PaveSet& aPaveSet1=myPavePoolNew(myDS->RefEdge(aWhat));
794                 aPaveSet1.Append(aPave);
795                 
796                 aPave.SetParam(aT2);
797                 BOPTools_PaveSet& aPaveSet2=myPavePoolNew(myDS->RefEdge(aWith));
798                 aPaveSet2.Append(aPave);
799               }
800               break;
801
802               case TopAbs_EDGE: {
803               
804                 const IntTools_SequenceOfRanges& aRanges2=aCPart.Ranges2();
805                 Standard_Integer aNbComPrt2=aRanges2.Length();
806                 
807                 if (aNbComPrt2>1) {
808                   //
809                   myIntrPool->AddInterference (aWhat, aWith, BooleanOperations_EdgeEdge, anIndexIn);
810                   break;
811                 }
812
813                 Standard_Boolean aCoinsideFlag;
814                 //
815                 aCoinsideFlag=IsBlocksCoinside(aPB1, aPB2);
816                 //
817                 if (!aCoinsideFlag) {
818                   //
819                   myIntrPool->AddInterference (aWhat, aWith, BooleanOperations_EdgeEdge, anIndexIn);
820                   break;
821                 }
822                 //
823                 // Add Interference to the Pool
824                 BOPTools_EEInterference anInterf (aWhat, aWith, aCPart);
825                 anIndexIn=aEEs.Append(anInterf);
826                 myIntrPool->AddInterference (aWhat, aWith, BooleanOperations_EdgeEdge, anIndexIn);
827                 //
828                 //modified by NIZNHY-PKV Fri May 26 15:48:21 2006f
829                 //BOPTools_CommonBlock aCB(aPB1, aPB2);
830                 BOPTools_CommonBlock aCB;
831                 if (aTolE1>=aTolE2) {
832                   aCB.SetPaveBlock1(aPB1);
833                   aCB.SetPaveBlock2(aPB2);
834                 }
835                 else {
836                   aCB.SetPaveBlock1(aPB2);
837                   aCB.SetPaveBlock2(aPB1);
838                 }
839                 //modified by NIZNHY-PKV Fri May 26 15:48:24 2006t
840                 BOPTools_ListOfCommonBlock& aLCB1=myCommonBlockPool(myDS->RefEdge(aWhat));
841                 aLCB1.Append(aCB);
842                 BOPTools_ListOfCommonBlock& aLCB2=myCommonBlockPool(myDS->RefEdge(aWith));
843                 aLCB2.Append(aCB);
844               }
845               break;
846
847             default:
848               break;
849             } // switch (aType) 
850           } // for (i=1; i<=aNbCPrts; i++) 
851         }// if (aEE.IsDone())
852         
853         //////////////////////////////////////////////
854       } // for (; anIt2.More(); anIt2.Next()) 
855     } // for (; anIt1.More(); anIt1.Next()) 
856   }// for (; myDSIt.More(); myDSIt.Next()) 
857   myIsDone=Standard_True;
858 }
859
860 //=======================================================================
861 // function: MakeSplitEdges
862 // purpose: 
863 //=======================================================================
864   void BOPTools_PaveFiller::MakeSplitEdges()
865 {
866   myIsDone=Standard_False;
867
868   Standard_Integer i, nV1, nV2, aNbPaveBlocks, aNewShapeIndex;;
869   Standard_Real    t1, t2;
870   TopoDS_Edge aE, aESplit;
871   TopoDS_Vertex aV1, aV2;
872
873   for (i=1; i<=myNbSources; i++) {
874
875     if (myDS->GetShapeType(i) != TopAbs_EDGE)
876       continue;
877     //
878     // Original Edge
879     aE=TopoDS::Edge(myDS->GetShape(i));
880     //
881     TopoDS_Edge anEdgeOriginal=aE;
882     TopAbs_Orientation anOrientationOriginal=anEdgeOriginal.Orientation(); 
883     //
884     if (BRep_Tool::Degenerated(aE)){
885       continue;
886     }
887     //
888     aE.Orientation(TopAbs_FORWARD);
889     //
890     // Making Split Edges
891     //
892     // Split Set for the Original Edge i
893     BOPTools_ListOfPaveBlock& aSplitEdges=mySplitShapesPool(myDS->RefEdge(i));
894     BOPTools_ListIteratorOfListOfPaveBlock aPBIt(aSplitEdges);
895
896     aNbPaveBlocks=aSplitEdges.Extent();
897     
898     if (aNbPaveBlocks==1) {
899       Standard_Boolean IsNewVertex1, IsNewVertex2;
900       // the split is equal to the original Edge
901       if (aPBIt.More()) {
902         BOPTools_PaveBlock& aPB1=aPBIt.Value();
903         
904         // 1
905         const BOPTools_Pave& aPave1=aPB1.Pave1();
906         nV1=aPave1.Index();
907         t1=aPave1.Param();
908         aV1=TopoDS::Vertex(myDS->GetShape(nV1));
909         aV1.Orientation(TopAbs_FORWARD);
910         // 2
911         const BOPTools_Pave& aPave2=aPB1.Pave2();
912         nV2=aPave2.Index();
913         t2=aPave2.Param();
914         aV2=TopoDS::Vertex(myDS->GetShape(nV2));
915         aV2.Orientation(TopAbs_REVERSED);
916         // 3
917         IsNewVertex1=myDS->IsNewShape (nV1);
918         IsNewVertex2=myDS->IsNewShape (nV2);
919         
920         if (IsNewVertex1 || IsNewVertex2) {
921           
922           BOPTools_Tools::MakeSplitEdge(aE, aV1, t1, aV2, t2, aESplit);  
923           BooleanOperations_AncestorsSeqAndSuccessorsSeq anASSeq;
924             
925           anASSeq.SetNewSuccessor(nV1);
926           anASSeq.SetNewOrientation(aV1.Orientation());
927             
928           anASSeq.SetNewSuccessor(nV2);
929           anASSeq.SetNewOrientation(aV2.Orientation());
930           //
931           if (anOrientationOriginal==TopAbs_INTERNAL) {
932             anASSeq.SetNewAncestor(i);
933             aESplit.Orientation(anOrientationOriginal);
934           }
935           //
936           myDS->InsertShapeAndAncestorsSuccessors(aESplit, anASSeq);
937           aNewShapeIndex=myDS->NumberOfInsertedShapes();
938           myDS->SetState(aNewShapeIndex, BooleanOperations_UNKNOWN);
939           //
940           // Fill Split Set for the Original Edge
941           aPB1.SetEdge(aNewShapeIndex); 
942         }
943         
944         else {
945           aPB1.SetEdge(i);
946         }
947         //
948         continue;
949       }
950     } // if (aNbPaveBlocks==1) 
951
952     for (; aPBIt.More(); aPBIt.Next()) {
953       BOPTools_PaveBlock& aPB=aPBIt.Value();
954       
955       const BOPTools_Pave& aPave1=aPB.Pave1();
956       nV1=aPave1.Index();
957       t1=aPave1.Param();
958       aV1=TopoDS::Vertex(myDS->GetShape(nV1));
959       aV1.Orientation(TopAbs_FORWARD);
960
961       const BOPTools_Pave& aPave2=aPB.Pave2();
962       nV2=aPave2.Index();
963       t2=aPave2.Param();
964       aV2=TopoDS::Vertex(myDS->GetShape(nV2));
965       aV2.Orientation(TopAbs_REVERSED);
966       
967       BOPTools_Tools::MakeSplitEdge(aE, aV1, t1, aV2, t2, aESplit);  
968       //
969       // Add Split Part of the Original Edge to the DS
970       BooleanOperations_AncestorsSeqAndSuccessorsSeq anASSeq;
971
972       anASSeq.SetNewSuccessor(nV1);
973       anASSeq.SetNewOrientation(aV1.Orientation());
974
975       anASSeq.SetNewSuccessor(nV2);
976       anASSeq.SetNewOrientation(aV2.Orientation());
977       //
978       if (anOrientationOriginal==TopAbs_INTERNAL) {
979         anASSeq.SetNewAncestor(i);
980         aESplit.Orientation(anOrientationOriginal);
981       }
982       //
983       myDS->InsertShapeAndAncestorsSuccessors(aESplit, anASSeq);
984       aNewShapeIndex=myDS->NumberOfInsertedShapes();
985       myDS->SetState(aNewShapeIndex, BooleanOperations_UNKNOWN);
986       //
987       // Fill Split Set for the Original Edge
988       aPB.SetEdge(aNewShapeIndex);
989       //
990     }
991
992   } //for (i=1; i<=myNbSources; i++) {
993   myIsDone=Standard_True;
994 }
995 //=======================================================================
996 // function: PreparePaveBlocks
997 // purpose: 
998 //=======================================================================
999   void BOPTools_PaveFiller::PreparePaveBlocks(const TopAbs_ShapeEnum aType1, 
1000                                               const TopAbs_ShapeEnum aType2)
1001 {
1002   myIsDone=Standard_False;
1003
1004   Standard_Boolean Ok1, Ok2, Ok3;
1005   Ok1= (aType1==TopAbs_VERTEX) &&  (aType2==TopAbs_EDGE) ;
1006   Ok2= (aType1==TopAbs_EDGE)   &&  (aType2==TopAbs_EDGE) ;
1007   Ok3= (aType1==TopAbs_EDGE)   &&  (aType2==TopAbs_FACE) ;
1008   if (!Ok1 && !Ok2 && !Ok3) {
1009     // error: Type mismatch
1010     return;
1011   }
1012
1013   Standard_Integer n1, n2, nE1, nE2, aNbSplits;
1014   TColStd_MapOfInteger aMap;
1015   
1016   myDSIt.Initialize(aType1, aType2);
1017
1018   for (; myDSIt.More(); myDSIt.Next()) {
1019     Standard_Boolean aFlag = Standard_False;
1020     myDSIt.Current(n1, n2, aFlag);
1021     nE1=n1; 
1022     nE2=n2; 
1023     SortTypes(nE1, nE2);
1024
1025     if (aType1==TopAbs_EDGE) {
1026       BOPTools_ListOfPaveBlock& aLPB1=mySplitShapesPool(myDS->RefEdge(nE1));
1027       aNbSplits=aLPB1.Extent();
1028       if (!aNbSplits) {
1029         if (!aMap.Contains(nE1)) { 
1030           aMap.Add(nE1);
1031           PreparePaveBlocks(nE1);
1032           
1033           if (!myIsDone) {
1034             return;
1035           }
1036         }
1037       }
1038     }
1039     
1040     if (aType2==TopAbs_EDGE) {
1041       BOPTools_ListOfPaveBlock& aLPB2=mySplitShapesPool(myDS->RefEdge(nE2));
1042       aNbSplits=aLPB2.Extent();
1043       if (!aNbSplits) {
1044         if (!aMap.Contains(nE2)) { 
1045           aMap.Add(nE2);
1046           PreparePaveBlocks(nE2);
1047         
1048           if (!myIsDone) {
1049             return;
1050           }
1051         }
1052       }
1053     }// if (aType2==TopAbs_EDGE)
1054   }// for (; myDSIt.More(); myDSIt.Next()) 
1055
1056   myIsDone=Standard_True;
1057 }
1058
1059 //=======================================================================
1060 // function: PreparePaveBlocks
1061 // purpose: 
1062 //=======================================================================
1063   void BOPTools_PaveFiller::PreparePaveBlocks(const Standard_Integer nE)
1064 {
1065   myIsDone=Standard_False;
1066   
1067   Standard_Integer nV1, nV2;
1068
1069   TopoDS_Edge aE;
1070   TopoDS_Vertex aV1, aV2;
1071     
1072   // SplitShapesPool
1073   BOPTools_ListOfPaveBlock& aLPB=mySplitShapesPool(myDS->RefEdge(nE));
1074   aLPB.Clear();
1075   // Edge 
1076   aE=TopoDS::Edge(myDS->GetShape(nE));
1077   //
1078   if (!BRep_Tool::Degenerated(aE)){
1079     //
1080     BOPTools_PaveSet& aPS=myPavePool(myDS->RefEdge(nE));
1081     
1082     BOPTools_PaveBlockIterator aPBIt(nE, aPS);
1083     for (; aPBIt.More(); aPBIt.Next()) {
1084       BOPTools_PaveBlock& aPB=aPBIt.Value();
1085       
1086       const IntTools_Range& aRange=aPB.Range();
1087       
1088       const BOPTools_Pave& aPave1=aPB.Pave1();
1089       nV1=aPave1.Index();
1090       aV1=TopoDS::Vertex(myDS->GetShape(nV1));
1091       
1092       const BOPTools_Pave& aPave2=aPB.Pave2();
1093       nV2=aPave2.Index();
1094       aV2=TopoDS::Vertex(myDS->GetShape(nV2));
1095       //
1096       // ShrunkRange
1097       IntTools_ShrunkRange aSR (aE, aV1, aV2, aRange, myContext);
1098       //
1099       Standard_Integer anErrorStatus;
1100       anErrorStatus=aSR.ErrorStatus();
1101
1102       char buf[512];
1103       if (!aSR.IsDone()) {
1104         Standard_Boolean bThrow = Standard_True;
1105         Standard_Integer iRank = myDS->Rank(nE);
1106         TopoDS_Shape aRef = (iRank == 1) ? myDS->Tool() : myDS->Object();
1107         Standard_Integer aRefIndex = (iRank == 1) ? myDS->ShapeIndex(aRef, 2) : myDS->ShapeIndex(aRef, 1);
1108
1109         Standard_Boolean bCheckDistance = Standard_True;
1110
1111         if(myDS->IsNewShape(nV1) || myDS->IsNewShape(nV2)) {
1112           bCheckDistance = Standard_False;
1113         }
1114         else {
1115           const BOPTools_CArray1OfInterferenceLine& aTable = myIntrPool->InterferenceTable();
1116           Standard_Integer tmpIt = 0;
1117
1118           for(tmpIt = 0; tmpIt < 3; tmpIt++) {
1119             Standard_Integer acurindex = (tmpIt == 0) ? nE : ((tmpIt == 1) ? nV1 : nV2);
1120             const BOPTools_InterferenceLine& anInterfLine =  aTable(acurindex);
1121
1122             if(!anInterfLine.RealList().IsEmpty())
1123               bCheckDistance = Standard_False;
1124           }
1125         }
1126
1127         if(bCheckDistance) {
1128           BRepExtrema_DistShapeShape aDist;
1129           Standard_Integer bRefLoaded = Standard_False;
1130
1131           Standard_Boolean bVertexIsOnShape = Standard_False;
1132           Standard_Integer ii = 0, jj = 0;
1133
1134           for(jj = 0; !bVertexIsOnShape && (jj < 2); jj++) {
1135             Standard_Integer currentNV = (jj == 0) ? nV1 : nV2;
1136
1137             Standard_Integer aVertexRank = myDS->Rank(currentNV);
1138
1139             if(aVertexRank != iRank) {
1140               bVertexIsOnShape = Standard_True;
1141               break;
1142             }
1143             BOPTools_IntersectionStatus aStatus = BOPTools_UNKNOWN;
1144
1145             if(aVertexRank == 1)
1146               aStatus = myDSIt.GetTableOfIntersectionStatus()->Value(currentNV, aRefIndex);
1147             else
1148               aStatus = myDSIt.GetTableOfIntersectionStatus()->Value(aRefIndex, currentNV);
1149             
1150             if(aStatus == BOPTools_NONINTERSECTED) {
1151               continue;
1152             }
1153
1154             if(jj == 0) {
1155               aDist.LoadS1(aV1);
1156
1157               if(!bRefLoaded)
1158                 aDist.LoadS2(aRef);
1159               bRefLoaded = Standard_True;
1160             }
1161             else {
1162               aDist.LoadS1(aV2);
1163
1164               if(!bRefLoaded)
1165                 aDist.LoadS2(aRef);
1166               bRefLoaded = Standard_True;
1167             }
1168             aDist.Perform();
1169
1170             if(aDist.IsDone()) {
1171
1172               for(ii = 1; ii <= aDist.NbSolution(); ii++) {
1173                 Standard_Real aTolerance = (jj == 0) ? BRep_Tool::Tolerance(aV1) : BRep_Tool::Tolerance(aV2);
1174                 TopoDS_Shape aSupportShape = aDist.SupportOnShape2(ii);
1175
1176                 switch(aSupportShape.ShapeType()) {
1177                 case TopAbs_VERTEX: {
1178                   aTolerance += BRep_Tool::Tolerance(TopoDS::Vertex(aSupportShape));
1179                   break;
1180                 }
1181                 case TopAbs_EDGE: {
1182                   aTolerance += BRep_Tool::Tolerance(TopoDS::Edge(aSupportShape));
1183                   break;
1184                 }
1185                 case TopAbs_FACE: {
1186                   aTolerance += BRep_Tool::Tolerance(TopoDS::Face(aSupportShape));
1187                   break;
1188                 }
1189                 default:
1190                   break;
1191                 }
1192
1193                 if(aDist.Value() < aTolerance) {
1194                   bVertexIsOnShape = Standard_True;
1195                   break;
1196                 }
1197               }
1198             }
1199           }
1200
1201           if(!bVertexIsOnShape) {
1202             aSR.SetShrunkRange(aRange);
1203             bThrow = Standard_False;
1204           }
1205         }
1206
1207         if(bThrow) {
1208
1209           sprintf (buf, "Can not obtain ShrunkRange for Edge %d\n", nE);
1210           BOPTColStd_Dump::PrintMessage(buf);
1211           sprintf (buf, "Can not obtain ShrunkRange for Edge %d", nE);
1212           throw 
1213             BOPTColStd_Failure(buf) ;
1214         }
1215       }
1216       //
1217       if (anErrorStatus==6) {
1218         sprintf(buf,
1219                 "Warning: [PreparePaveBlocks()] Max.Dummy Shrunk Range for Edge %d\n", nE);
1220         BOPTColStd_Dump::PrintMessage(buf);
1221       }
1222       else {
1223         // Check left paves and correct ShrunkRange if it is necessary
1224         CorrectShrunkRanges (0, aPave1, aSR);
1225         CorrectShrunkRanges (1, aPave2, aSR);
1226       }
1227       //
1228       aPB.SetShrunkRange(aSR);
1229       aLPB.Append(aPB);
1230     } //for (; aPBIt1.More(); aPBIt1.Next()) 
1231   }
1232   myIsDone=Standard_True;
1233 }
1234
1235 //=======================================================================
1236 // function: CorrectShrunkRanges
1237 // purpose: 
1238 //=======================================================================
1239   void BOPTools_PaveFiller::CorrectShrunkRanges(const Standard_Integer aSide,
1240                                                 const BOPTools_Pave& aPave,
1241                                                 IntTools_ShrunkRange& aShrunkRange)
1242 {
1243   BooleanOperations_KindOfInterference aType;
1244   
1245   aType=aPave.Type();
1246   if (aType!=BooleanOperations_EdgeEdge) {
1247     return;
1248   }
1249
1250   Standard_Integer anIndexInterf ;
1251   anIndexInterf=aPave.Interference();
1252   BOPTools_CArray1OfEEInterference& aEEs=myIntrPool->EEInterferences();
1253   const BOPTools_EEInterference& aEE=aEEs(anIndexInterf);
1254   const IntTools_CommonPrt& aCP=aEE.CommonPrt();
1255   const TopoDS_Edge& aE1=aCP.Edge1();
1256   const TopoDS_Edge& aE2=aCP.Edge2();
1257
1258   const IntTools_Range& aSR=aShrunkRange.ShrunkRange();
1259   const TopoDS_Edge& aE=aShrunkRange.Edge();
1260  
1261   IntTools_Range aNewRange;
1262   IntTools_Range aCPRange;
1263
1264   if (aE1.IsSame(aE)) {
1265     const IntTools_Range& aR1=aCP.Range1();
1266     aCPRange=aR1;
1267   }
1268   if (aE2.IsSame(aE)) {
1269     const IntTools_SequenceOfRanges& aSeqR=aCP.Ranges2();
1270     const IntTools_Range& aR2=aSeqR(1);
1271      aCPRange=aR2;
1272   }
1273   
1274
1275   Standard_Real aCoeff=1.05, tV, tNV;
1276   tV=aPave.Param();
1277   if (aSide==0) { // Left
1278     if (aCPRange.Last() > aSR.First()) {
1279       tNV=aCPRange.Last();
1280       tNV=tV+aCoeff*(tNV-tV);
1281       aNewRange.SetFirst(tNV);
1282       aNewRange.SetLast (aSR.Last());
1283
1284       if(aNewRange.First() > aNewRange.Last()) {
1285         aShrunkRange.SetShrunkRange(aNewRange);
1286       }
1287     }
1288   }
1289   else { // Right
1290     if (aCPRange.First() < aSR.Last()) {
1291       tNV=aCPRange.First();
1292       tNV=tV-aCoeff*(tV-tNV);
1293       aNewRange.SetFirst(aSR.First());
1294       aNewRange.SetLast (tNV);
1295
1296       if(aNewRange.First() < aNewRange.Last()) {
1297         aShrunkRange.SetShrunkRange(aNewRange);
1298       }
1299     }
1300   }
1301 }
1302
1303 //=======================================================================
1304 // function: RefinePavePool
1305 // purpose: 
1306 //=======================================================================
1307   void BOPTools_PaveFiller::RefinePavePool()
1308 {
1309   Standard_Integer  i, aNbNew;
1310
1311   for (i=1; i<=myNbSources; i++) {
1312
1313     if ((myDS->GetShape(i)).ShapeType()==TopAbs_EDGE) {
1314       BOPTools_PaveSet& aPS= myPavePool(myDS->RefEdge(i));
1315       //ZZ BOPTools_ListOfPave& aLP=aPS.ChangeSet();
1316       
1317       BOPTools_PaveSet& aNewPS= myPavePoolNew(myDS->RefEdge(i));
1318       BOPTools_ListOfPave& aNewLP=aNewPS.ChangeSet();
1319
1320       aNbNew=aNewLP.Extent();
1321       if (aNbNew) {
1322         BOPTools_ListIteratorOfListOfPave anIt(aNewLP);
1323         for (; anIt.More(); anIt.Next()) {
1324           const BOPTools_Pave& aPave=anIt.Value();
1325           aPS.Append(aPave);
1326         }
1327         // Clear the ListOfPaveBlock
1328         BOPTools_ListOfPaveBlock& aLPB=mySplitShapesPool(myDS->RefEdge(i));
1329         aLPB.Clear();
1330         // Prepare the paveBlocks for that egde again
1331         PreparePaveBlocks(i);
1332       }
1333       aNewLP.Clear();
1334     }
1335   }
1336 }
1337
1338 //=======================================================================
1339 // function: PrepareEdges
1340 // purpose: 
1341 //=======================================================================
1342   void BOPTools_PaveFiller::PrepareEdges() 
1343 {
1344   Standard_Integer  i, nV, ii, aNBSuc, ip;
1345   Standard_Real aT;
1346   TopAbs_Orientation anOr;
1347   TopoDS_Edge   aE;
1348   TopoDS_Vertex aV;
1349
1350   for (i=1; i<=myNbSources; i++) {
1351     if (myDS->GetShapeType(i)==TopAbs_EDGE) {
1352       aE=TopoDS::Edge(myDS->GetShape(i));
1353       //
1354       if (BRep_Tool::Degenerated(aE)){
1355         continue;
1356       }
1357       //
1358       BOPTools_PaveSet& aPaveSet= myPavePool(myDS->RefEdge(i));
1359       //
1360       //                                                   cto900/M2
1361       // Some of Edges can be [Semi] Infinite.  Such  Edges have no 
1362       // vertices on correspondant INF ends.   So we  must  provide 
1363       // these vertices formally (to obtain  Shrunk  Ranges for e.g). 
1364       // In reality this vertex(-es) does not belong to the INF Edge.
1365       // It just has reference in the DS.
1366       //                            PKV Tue Apr 23 10:21:45 2002                 
1367       {
1368         Standard_Real aT1, aT2, aTolE;
1369         Standard_Boolean bInf1, bInf2;
1370         gp_Pnt aPx;
1371         TopoDS_Vertex aVx; 
1372         BRep_Builder aBB;
1373         BooleanOperations_AncestorsSeqAndSuccessorsSeq anASSeq; 
1374         //
1375         aTolE=BRep_Tool::Tolerance(aE);
1376         Handle(Geom_Curve) aC3D=BRep_Tool::Curve (aE, aT1, aT2);
1377         bInf1=Precision::IsNegativeInfinite(aT1);
1378         bInf2=Precision::IsPositiveInfinite(aT2);
1379
1380         if (bInf1) {
1381           aC3D->D0(aT1, aPx);
1382           aBB.MakeVertex(aVx, aPx, aTolE);
1383           myDS->InsertShapeAndAncestorsSuccessors(aVx, anASSeq);
1384           nV=myDS->NumberOfInsertedShapes();
1385           BOPTools_Pave aPave(nV, aT1); 
1386           aPaveSet.Append (aPave);
1387         }
1388
1389         if (bInf2) {
1390           aC3D->D0(aT2, aPx);
1391           aBB.MakeVertex(aVx, aPx, aTolE);
1392           myDS->InsertShapeAndAncestorsSuccessors(aVx, anASSeq);
1393           nV=myDS->NumberOfInsertedShapes();
1394           BOPTools_Pave aPave(nV, aT2);
1395           aPaveSet.Append (aPave); 
1396         }
1397       }
1398       //
1399       aNBSuc=myDS->NumberOfSuccessors(i);
1400       for (ii=1; ii <= aNBSuc; ii++) {
1401         nV=myDS->GetSuccessor(i, ii);
1402         anOr=myDS->GetOrientation(i, ii);
1403
1404         aV=TopoDS::Vertex(myDS->GetShape(nV));
1405         aV.Orientation(anOr);
1406         aT=BRep_Tool::Parameter(aV, aE);
1407         //
1408         ip=FindSDVertex(nV);
1409         if (ip) {
1410           aV=TopoDS::Vertex(myDS->GetShape(ip));
1411           aV.Orientation(anOr);
1412           nV=ip;
1413         }
1414         //
1415         BOPTools_Pave aPave(nV, aT); 
1416         aPaveSet.Append (aPave);
1417       }
1418     }
1419   }
1420 }
1421 //=======================================================================
1422 // function: PerformVV
1423 // purpose: 
1424 //=======================================================================
1425   void BOPTools_PaveFiller::PerformVV() 
1426 {
1427   myIsDone=Standard_False;
1428  
1429   Standard_Integer n1, n2,anIndexIn, aFlag, aWhat, aWith, aNbVVs, aBlockLength;
1430   //
1431   BOPTools_CArray1OfVVInterference& aVVs=myIntrPool->VVInterferences();
1432   //
1433   // V/V  BooleanOperations_VertexVertex
1434   myDSIt.Initialize(TopAbs_VERTEX, TopAbs_VERTEX);
1435   //
1436   //
1437   // BlockLength correction
1438   aNbVVs=ExpectedPoolLength();
1439   aBlockLength=aVVs.BlockLength();
1440   if (aNbVVs > aBlockLength) {
1441     aVVs.SetBlockLength(aNbVVs);
1442   }
1443   //
1444   //
1445   for (; myDSIt.More(); myDSIt.Next()) {
1446     Standard_Boolean justaddinterference = Standard_False;
1447     myDSIt.Current(n1, n2, justaddinterference);
1448
1449     if(justaddinterference) {
1450       if (! myIntrPool->IsComputed(n1, n2)) {
1451         anIndexIn=0;
1452         aWhat=n1;
1453         aWith=n2;
1454         SortTypes(aWhat, aWith);
1455         myIntrPool->AddInterference(aWhat, aWith, BooleanOperations_VertexVertex, anIndexIn);
1456       }
1457       continue;
1458     }
1459     //
1460     if (! myIntrPool->IsComputed(n1, n2)) {
1461       anIndexIn=0;
1462       aWhat=n1;
1463       aWith=n2;
1464       SortTypes(aWhat, aWith);
1465       const TopoDS_Shape& aS1=myDS->GetShape(aWhat);
1466       const TopoDS_Shape& aS2=myDS->GetShape(aWith);
1467       
1468       const TopoDS_Vertex& aV1=TopoDS::Vertex(aS1);
1469       const TopoDS_Vertex& aV2=TopoDS::Vertex(aS2);
1470       aFlag=IntTools_Tools::ComputeVV (aV1, aV2);
1471     
1472       if (!aFlag) {
1473         BOPTools_VVInterference anInterf (aWhat, aWith);
1474         anIndexIn=aVVs.Append(anInterf);
1475       }
1476       myIntrPool->AddInterference(aWhat, aWith, BooleanOperations_VertexVertex, anIndexIn);
1477       //myIntrPool->ComputeResult(n1, n2);
1478     }
1479   }
1480
1481   myIsDone=Standard_True;
1482 }
1483 //=======================================================================
1484 // function: PerformNewVertices
1485 // purpose: 
1486 //=======================================================================
1487   void BOPTools_PaveFiller::PerformNewVertices() 
1488 {
1489   myIsDone=Standard_False;
1490
1491   Standard_Integer i, aNb, anIndex1, anIndex2, aNewShape;
1492   TopoDS_Vertex aV1, aV2, aNewVertex;
1493   BooleanOperations_AncestorsSeqAndSuccessorsSeq anASSeq;
1494   //
1495   // 1. VV Interferences
1496   BOPTools_CArray1OfVVInterference& VVs=myIntrPool->VVInterferences();
1497   aNb=VVs.Extent();
1498   for (i=1; i<=aNb; i++) {
1499     BOPTools_VVInterference& VV=VVs(i);
1500     anIndex1=VV.Index1();
1501     anIndex2=VV.Index2();
1502     //
1503     // Make New Vertex
1504     aV1=TopoDS::Vertex(myDS->GetShape(anIndex1));
1505     aV2=TopoDS::Vertex(myDS->GetShape(anIndex2));
1506     BOPTools_Tools::MakeNewVertex(aV1, aV2, aNewVertex);
1507     //
1508     // Insert New Vertex in DS;
1509     // aNewShape is # of DS-line, where aNewVertex is kept
1510     myDS->InsertShapeAndAncestorsSuccessors(aNewVertex, anASSeq);
1511     aNewShape=myDS->NumberOfInsertedShapes();
1512     // State of New Vertex is ON
1513     myDS->SetState (aNewShape, BooleanOperations_ON);
1514     // Insert New Vertex in Interference
1515     VV.SetNewShape(aNewShape);
1516   }
1517
1518   myIsDone=Standard_True;
1519 }
1520 //=======================================================================
1521 // function: FindSDVertex
1522 // purpose: 
1523 //=======================================================================
1524   Standard_Integer BOPTools_PaveFiller::FindSDVertex(const Standard_Integer nV)const
1525 {
1526   Standard_Integer i, aNb, anIndex1, anIndex2, aNewShape=0;
1527
1528   BOPTools_CArray1OfVVInterference& VVs=myIntrPool->VVInterferences();
1529   aNb=VVs.Extent();
1530   
1531   for (i=1; i<=aNb; i++) {
1532     const BOPTools_VVInterference& VV=VVs(i);
1533     anIndex1=VV.Index1();
1534     anIndex2=VV.Index2();
1535     if (nV==anIndex1 || nV==anIndex2) {
1536       aNewShape=VV.NewShape();
1537       return aNewShape;
1538     }
1539   }
1540   return aNewShape;
1541 }
1542
1543 //=======================================================================
1544 // function:IsSuccesstorsComputed
1545 // purpose: 
1546 //=======================================================================
1547   Standard_Boolean BOPTools_PaveFiller::IsSuccesstorsComputed(const Standard_Integer aN1,
1548                                                               const Standard_Integer aN2)const
1549 {
1550   Standard_Integer nSuc, n1, n2;
1551
1552   BooleanOperations_OnceExplorer aExp(*myDS);
1553   TopAbs_ShapeEnum aType=myDS->GetShapeType(aN1);
1554
1555   n1=aN1;
1556   n2=aN2;
1557
1558   if (aType!=TopAbs_VERTEX) {
1559     Standard_Integer ntmp=n1;
1560     n1=n2;
1561     n2=ntmp;
1562   }
1563
1564   aType=myDS->GetShapeType(n2);
1565   if (aType==TopAbs_EDGE) {
1566     aExp.Init(n2, TopAbs_VERTEX);
1567     for (; aExp.More(); aExp.Next()) {
1568       nSuc=aExp.Current();
1569       if (myIntrPool->IsComputed(n1, nSuc)) {
1570         return Standard_True;
1571       }
1572     }
1573   return Standard_False;
1574   }
1575
1576   else if (aType==TopAbs_FACE) {
1577     aExp.Init(n2, TopAbs_VERTEX);
1578     for (; aExp.More(); aExp.Next()) {
1579       nSuc=aExp.Current();
1580       if (myIntrPool->IsComputed(n1, nSuc)) {
1581         return Standard_True;
1582       }
1583     }
1584
1585     aExp.Init(n2, TopAbs_EDGE);
1586     for (; aExp.More(); aExp.Next()) {
1587       nSuc=aExp.Current();
1588       if (myIntrPool->IsComputed(n1, nSuc)) {
1589         return Standard_True;
1590       }
1591     }
1592     return Standard_False;
1593   }
1594
1595   return Standard_False;
1596 }
1597
1598 //=======================================================================
1599 //function : SortTypes
1600 //purpose  : 
1601 //=======================================================================
1602   void BOPTools_PaveFiller::SortTypes(Standard_Integer& theWhat,
1603                                       Standard_Integer& theWith)const 
1604
1605   Standard_Boolean aReverseFlag=Standard_True;
1606
1607   TopAbs_ShapeEnum aType1= myDS->GetShapeType(theWhat),
1608                    aType2= myDS->GetShapeType(theWith);
1609   
1610   if (aType1==aType2)
1611     return;
1612   
1613   if (aType1==TopAbs_EDGE && aType2==TopAbs_FACE){
1614     aReverseFlag=Standard_False;
1615   }
1616
1617   if (aType1==TopAbs_VERTEX && 
1618       (aType2==TopAbs_FACE || aType2==TopAbs_EDGE)) {
1619     aReverseFlag=Standard_False;
1620   }
1621   
1622   Standard_Integer aWhat, aWith;
1623   aWhat=(aReverseFlag) ? theWith : theWhat;
1624   aWith=(aReverseFlag) ? theWhat : theWith;
1625   
1626   theWhat=aWhat;
1627   theWith=aWith;
1628 }
1629
1630 //=======================================================================
1631 // function:IsDone
1632 // purpose: 
1633 //=======================================================================
1634   Standard_Boolean BOPTools_PaveFiller::IsDone() const
1635 {
1636   return myIsDone;
1637 }
1638
1639 //=======================================================================
1640 // function: PavePool
1641 // purpose: 
1642 //=======================================================================
1643   const BOPTools_PavePool& BOPTools_PaveFiller::PavePool() const
1644 {
1645   return myPavePool;
1646 }
1647 //=======================================================================
1648 // function: ChangePavePool
1649 // purpose: 
1650 //=======================================================================
1651   BOPTools_PavePool& BOPTools_PaveFiller::ChangePavePool()
1652 {
1653   return myPavePool;
1654 }
1655
1656 //=======================================================================
1657 // function:  CommonBlockPool
1658 // purpose: 
1659 //=======================================================================
1660   const BOPTools_CommonBlockPool& BOPTools_PaveFiller::CommonBlockPool() const
1661 {
1662   return myCommonBlockPool;
1663 }
1664 //=======================================================================
1665 // function:  ChangeCommonBlockPool
1666 // purpose: 
1667 //=======================================================================
1668   BOPTools_CommonBlockPool& BOPTools_PaveFiller::ChangeCommonBlockPool()
1669 {
1670   return myCommonBlockPool;
1671 }
1672 //=======================================================================
1673 // function:  SplitShapesPool
1674 // purpose: 
1675 //=======================================================================
1676   const BOPTools_SplitShapesPool& BOPTools_PaveFiller::SplitShapesPool() const
1677 {
1678   return mySplitShapesPool;
1679 }
1680
1681 //=======================================================================
1682 // function:  ChangeSplitShapesPool
1683 // purpose: 
1684 //=======================================================================
1685   BOPTools_SplitShapesPool& BOPTools_PaveFiller::ChangeSplitShapesPool()
1686 {
1687   return mySplitShapesPool;
1688 }
1689 //=======================================================================
1690 // function:  DS
1691 // purpose: 
1692 //=======================================================================
1693   BooleanOperations_PShapesDataStructure BOPTools_PaveFiller::DS()
1694 {
1695   return myDS;
1696 }
1697 //=======================================================================
1698 // function:  InterfPool
1699 // purpose: 
1700 //=======================================================================
1701   BOPTools_PInterferencePool BOPTools_PaveFiller::InterfPool()
1702 {
1703   return myIntrPool;
1704 }
1705
1706 //
1707 //=======================================================================
1708 // function:  IteratorOfCoupleOfShape
1709 // purpose: 
1710 //=======================================================================
1711   const BOPTools_IteratorOfCoupleOfShape& 
1712                      BOPTools_PaveFiller::IteratorOfCoupleOfShape() const
1713 {
1714   return myDSIt;
1715 }
1716 //
1717 //=======================================================================
1718 // function:  ExpectedPoolLength
1719 // purpose: 
1720 //=======================================================================
1721    Standard_Integer BOPTools_PaveFiller::ExpectedPoolLength()const
1722 {
1723   Standard_Integer aNbIIs;
1724   Standard_Real aCfPredict=.5;
1725
1726   const BOPTools_ListOfCoupleOfInteger& aLC=myDSIt.ListOfCouple();
1727   aNbIIs=aLC.Extent();
1728   //
1729   if (aNbIIs==1) {
1730     return aNbIIs;
1731   }
1732   //
1733   aNbIIs=(Standard_Integer) (aCfPredict*(Standard_Real)aNbIIs);
1734   
1735   return aNbIIs;
1736 }
1737 //
1738 //=======================================================================
1739 // function:  IsBlocksCoinside
1740 // purpose: 
1741 //=======================================================================
1742   Standard_Boolean 
1743     BOPTools_PaveFiller::IsBlocksCoinside(const BOPTools_PaveBlock& aPB1,
1744                                           const BOPTools_PaveBlock& aPB2) const
1745 {
1746   Standard_Boolean bRetFlag=Standard_True;
1747   Standard_Real aTolV11, aTolV12, aTolV21, aTolV22;
1748   Standard_Real d1121, d1122, d1222, d1221, aTolSum, aCoeff=1.05;
1749   gp_Pnt aP11, aP12, aP21, aP22;
1750
1751   const TopoDS_Vertex& aV11=TopoDS::Vertex(myDS->Shape(aPB1.Pave1().Index()));
1752   const TopoDS_Vertex& aV12=TopoDS::Vertex(myDS->Shape(aPB1.Pave2().Index()));
1753   const TopoDS_Vertex& aV21=TopoDS::Vertex(myDS->Shape(aPB2.Pave1().Index()));
1754   const TopoDS_Vertex& aV22=TopoDS::Vertex(myDS->Shape(aPB2.Pave2().Index()));
1755
1756   aTolV11=BRep_Tool::Tolerance(aV11);
1757   aTolV12=BRep_Tool::Tolerance(aV12);
1758   aTolV21=BRep_Tool::Tolerance(aV21);
1759   aTolV22=BRep_Tool::Tolerance(aV22);
1760   
1761   aP11=BRep_Tool::Pnt(aV11);
1762   aP12=BRep_Tool::Pnt(aV12);
1763   aP21=BRep_Tool::Pnt(aV21);
1764   aP22=BRep_Tool::Pnt(aV22);
1765
1766   d1121=aP11.Distance(aP21);
1767   aTolSum=aCoeff*(aTolV11+aTolV21);
1768   if (d1121<aTolSum) {
1769     d1222=aP12.Distance(aP22);
1770     aTolSum=aCoeff*(aTolV12+aTolV22);
1771     if (d1222<aTolSum) {
1772       return bRetFlag;
1773     }
1774   }
1775   //
1776   d1122=aP11.Distance(aP22);
1777   aTolSum=aCoeff*(aTolV11+aTolV22);
1778   if (d1122<aTolSum) {
1779     d1221=aP12.Distance(aP21);
1780     aTolSum=aCoeff*(aTolV12+aTolV21);
1781     if (d1221<aTolSum) {
1782       return bRetFlag;
1783     }
1784   }
1785   return !bRetFlag;
1786 }