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