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