0028259: Method MakeBlocksCnx is duplicated in two different places in BOPAlgo
[occt.git] / src / BOPDS / BOPDS_DS.cxx
1 // Created by: Peter KURNEV
2 // Copyright (c) 1999-2014 OPEN CASCADE SAS
3 //
4 // This file is part of Open CASCADE Technology software library.
5 //
6 // This library is free software; you can redistribute it and/or modify it under
7 // the terms of the GNU Lesser General Public License version 2.1 as published
8 // by the Free Software Foundation, with special exception defined in the file
9 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
10 // distribution for complete text of the license and disclaimer of any warranty.
11 //
12 // Alternatively, this file may be used under the terms of Open CASCADE
13 // commercial license or contractual agreement.
14
15
16 #include <Bnd_Box.hxx>
17 #include <BOPCol_DataMapOfIntegerMapOfInteger.hxx>
18 #include <BOPCol_DataMapOfShapeInteger.hxx>
19 #include <BOPCol_ListOfInteger.hxx>
20 #include <BOPCol_MapOfInteger.hxx>
21 #include <BOPDS_CommonBlock.hxx>
22 #include <BOPDS_DS.hxx>
23 #include <BOPDS_FaceInfo.hxx>
24 #include <BOPDS_IndexRange.hxx>
25 #include <BOPDS_MapOfPave.hxx>
26 #include <BOPDS_MapOfPaveBlock.hxx>
27 #include <BOPDS_Pair.hxx>
28 #include <BOPDS_PaveBlock.hxx>
29 #include <BOPDS_ShapeInfo.hxx>
30 #include <BOPDS_VectorOfPave.hxx>
31 #include <BOPTools_AlgoTools.hxx>
32 #include <BRep_Builder.hxx>
33 #include <BRep_TEdge.hxx>
34 #include <BRep_TFace.hxx>
35 #include <BRep_Tool.hxx>
36 #include <BRep_TVertex.hxx>
37 #include <BRepBndLib.hxx>
38 #include <Geom_Curve.hxx>
39 #include <GeomAPI_ProjectPointOnCurve.hxx>
40 #include <gp_Pnt.hxx>
41 #include <IntTools_Tools.hxx>
42 #include <NCollection_BaseAllocator.hxx>
43 #include <Precision.hxx>
44 #include <Standard_Assert.hxx>
45 #include <TopoDS_Edge.hxx>
46 #include <TopoDS_Face.hxx>
47 #include <TopoDS_Iterator.hxx>
48 #include <TopoDS_Shape.hxx>
49 #include <TopoDS_Vertex.hxx>
50 #include <BOPCol_MapOfShape.hxx>
51 #include <BOPCol_DataMapOfIntegerListOfInteger.hxx>
52
53 #include <algorithm>
54 //
55
56 static
57   void TotalShapes(const TopoDS_Shape& aS, 
58                    Standard_Integer& aNbS,
59                    BOPCol_MapOfShape& aMS);
60
61 static
62   Standard_Real ComputeParameter(const TopoDS_Vertex& aV,
63                                  const TopoDS_Edge& aE);
64
65 //=======================================================================
66 //function : 
67 //purpose  : 
68 //=======================================================================
69 BOPDS_DS::BOPDS_DS()
70 :
71   myAllocator(NCollection_BaseAllocator::CommonBaseAllocator()),
72   myArguments(myAllocator),
73   myRanges(0,myAllocator),
74   myLines(0, myAllocator), 
75   myMapShapeIndex(100, myAllocator),
76   myPaveBlocksPool(0,myAllocator),
77   myMapPBCB(100, myAllocator),
78   myFaceInfoPool(0, myAllocator),
79   myShapesSD(100, myAllocator),
80   myMapVE(100, myAllocator),
81   myInterfTB(100, myAllocator),
82   myInterfVV(0, myAllocator),
83   myInterfVE(0, myAllocator),
84   myInterfVF(0, myAllocator),
85   myInterfEE(0, myAllocator),
86   myInterfEF(0, myAllocator),
87   myInterfFF(0, myAllocator),
88   myInterfVZ(0, myAllocator),
89   myInterfEZ(0, myAllocator),
90   myInterfFZ(0, myAllocator),
91   myInterfZZ(0, myAllocator)
92 {
93   myNbShapes=0;
94   myNbSourceShapes=0;
95 }
96 //=======================================================================
97 //function : 
98 //purpose  : 
99 //=======================================================================
100 BOPDS_DS::BOPDS_DS(const Handle(NCollection_BaseAllocator)& theAllocator)
101 :
102   myAllocator(theAllocator),
103   myArguments(myAllocator),
104   myRanges(0, myAllocator),
105   myLines(0, myAllocator),
106   myMapShapeIndex(100, myAllocator),
107   myPaveBlocksPool(0, myAllocator),
108   myMapPBCB(100, myAllocator),
109   myFaceInfoPool(0, myAllocator),
110   myShapesSD(100, myAllocator),
111   myMapVE(100, myAllocator),
112   myInterfTB(100, myAllocator),
113   myInterfVV(0, myAllocator),
114   myInterfVE(0, myAllocator),
115   myInterfVF(0, myAllocator),
116   myInterfEE(0, myAllocator),
117   myInterfEF(0, myAllocator),
118   myInterfFF(0, myAllocator),
119   myInterfVZ(0, myAllocator),
120   myInterfEZ(0, myAllocator),
121   myInterfFZ(0, myAllocator),
122   myInterfZZ(0, myAllocator)
123 {
124   myNbShapes=0;
125   myNbSourceShapes=0;
126 }
127 //=======================================================================
128 //function : ~
129 //purpose  : 
130 //=======================================================================
131 BOPDS_DS::~BOPDS_DS()
132 {
133   Clear();
134 }
135 //=======================================================================
136 //function : Clear
137 //purpose  : 
138 //=======================================================================
139 void BOPDS_DS::Clear()
140 {
141   myNbShapes=0;
142   myNbSourceShapes=0;
143   //
144   myArguments.Clear();
145   myRanges.Clear();
146   myLines.Clear();
147   myMapShapeIndex.Clear();
148   myPaveBlocksPool.Clear();
149   myFaceInfoPool.Clear();
150   myShapesSD.Clear();
151   myMapVE.Clear();
152   myMapPBCB.Clear();
153   myInterfTB.Clear();
154   myInterfVV.Clear();
155   myInterfVE.Clear();
156   myInterfVF.Clear();
157   myInterfEE.Clear();
158   myInterfEF.Clear();
159   myInterfFF.Clear();
160   myInterfVZ.Clear();
161   myInterfEZ.Clear();
162   myInterfFZ.Clear();
163   myInterfZZ.Clear();
164 }
165 //=======================================================================
166 //function : SetArguments
167 //purpose  : 
168 //=======================================================================
169 void BOPDS_DS::SetArguments(const BOPCol_ListOfShape& theLS)
170 {
171   myArguments=theLS;
172 }
173 //=======================================================================
174 //function : Arguments
175 //purpose  : 
176 //=======================================================================
177 const BOPCol_ListOfShape& BOPDS_DS::Arguments()const
178 {
179   return myArguments;
180 }
181 //=======================================================================
182 //function : Allocator
183 //purpose  : 
184 //=======================================================================
185 const Handle(NCollection_BaseAllocator)& BOPDS_DS::Allocator()const
186 {
187   return myAllocator;
188 }
189
190 //=======================================================================
191 //function : NbShapes
192 //purpose  : 
193 //=======================================================================
194 Standard_Integer BOPDS_DS::NbShapes()const
195 {
196   return myLines.Size();
197 }
198 //=======================================================================
199 //function : NbSourceShapes
200 //purpose  : 
201 //=======================================================================
202 Standard_Integer BOPDS_DS::NbSourceShapes()const
203 {
204   return myNbSourceShapes;
205 }
206 //=======================================================================
207 //function : NbRanges
208 //purpose  : 
209 //=======================================================================
210 Standard_Integer BOPDS_DS::NbRanges()const
211 {
212   return myRanges.Size();
213 }
214 //=======================================================================
215 //function : Range
216 //purpose  : 
217 //=======================================================================
218 const BOPDS_IndexRange& BOPDS_DS::Range(const Standard_Integer theI)const
219 {
220   return myRanges(theI);
221 }
222 //=======================================================================
223 //function : Rank
224 //purpose  : 
225 //=======================================================================
226 Standard_Integer BOPDS_DS::Rank(const Standard_Integer theI)const
227 {
228   Standard_Integer i, aNb, iErr;
229   //
230   iErr=-1;
231   aNb=NbRanges();
232   for(i=0; i<aNb; ++i) {
233     const BOPDS_IndexRange& aR=Range(i);
234     if (aR.Contains(theI)) {
235       return i;
236     }
237   }
238   return iErr;
239 }
240 //=======================================================================
241 //function : IsNewShape
242 //purpose  : 
243 //=======================================================================
244 Standard_Boolean BOPDS_DS::IsNewShape(const Standard_Integer theI)const
245 {
246   return theI>=NbSourceShapes();
247 }
248 //=======================================================================
249 //function : Append
250 //purpose  : 
251 //=======================================================================
252 Standard_Integer BOPDS_DS::Append(const BOPDS_ShapeInfo& theSI)
253 {
254   Standard_Integer iX;
255   //
256   myLines.Append1()=theSI;
257   iX=myLines.Extent()-1;
258   myMapShapeIndex.Bind(theSI.Shape(), iX);
259   //
260   return iX;
261 }
262 //=======================================================================
263 //function : Append
264 //purpose  : 
265 //=======================================================================
266 Standard_Integer BOPDS_DS::Append(const TopoDS_Shape& theS)
267 {
268   Standard_Integer iX;
269   //
270   myLines.Append1().SetShape(theS);
271   iX=myLines.Extent()-1;
272   myMapShapeIndex.Bind(theS, iX);
273   return iX;
274 }
275 //=======================================================================
276 //function : ShapeInfo
277 //purpose  : 
278 //=======================================================================
279 const BOPDS_ShapeInfo& BOPDS_DS::ShapeInfo
280   (const Standard_Integer theI)const
281 {
282   return myLines(theI);
283 }
284 //=======================================================================
285 //function : ChangeShapeInfo
286 //purpose  : 
287 //=======================================================================
288 BOPDS_ShapeInfo& BOPDS_DS::ChangeShapeInfo(const Standard_Integer theI)
289 {
290   BOPDS_ShapeInfo *pSI;
291   //
292   const BOPDS_ShapeInfo& aSI=ShapeInfo(theI);
293   pSI=(BOPDS_ShapeInfo *)&aSI;
294   return *pSI;
295 }
296 //=======================================================================
297 //function : Shape
298 //purpose  : 
299 //=======================================================================
300 const TopoDS_Shape& BOPDS_DS::Shape(const Standard_Integer theI)const
301 {
302   
303   const TopoDS_Shape& aS=ShapeInfo(theI).Shape();
304   return aS;
305 }
306 //=======================================================================
307 //function : Index
308 //purpose  : 
309 //=======================================================================
310 Standard_Integer BOPDS_DS::Index(const TopoDS_Shape& theS)const
311 {
312   Standard_Integer iRet;
313   //
314   iRet=-1;
315   if (myMapShapeIndex.IsBound(theS)) {
316     iRet=myMapShapeIndex.Find(theS);
317   }
318   return iRet;
319 }
320 //=======================================================================
321 //function : Init
322 //purpose  : 
323 //=======================================================================
324 void BOPDS_DS::Init(const Standard_Real theFuzz)
325 {
326   Standard_Integer i1, i2, j, aI, aNb, aNbS, aNbE, aNbSx;
327   Standard_Integer n1, n2, n3, nV, nW, nE, aNbF;
328   Standard_Real aTol, aTolAdd;
329   TopAbs_ShapeEnum aTS;
330   TopoDS_Iterator aItS;
331   BOPCol_ListIteratorOfListOfInteger aIt1, aIt2, aIt3;
332   BOPCol_ListIteratorOfListOfShape aIt;
333   BOPDS_IndexRange aR;
334   Handle(NCollection_BaseAllocator) aAllocator;
335   BOPCol_MapOfShape aMS;
336   //
337   // 1 Append Source Shapes
338   aNb=myArguments.Extent();
339   if (!aNb) {
340     return;
341   }
342   //
343   myRanges.SetIncrement(aNb);
344   //
345   aNbS=0;
346   aIt.Initialize(myArguments);
347   for (; aIt.More(); aIt.Next()) {
348     const TopoDS_Shape& aSx=aIt.Value();
349     //
350     aNbSx=0;
351     TotalShapes(aSx, aNbSx, aMS);
352     //
353     aNbS=aNbS+aNbSx;
354   }
355   aMS.Clear();
356   //
357   myLines.SetIncrement(2*aNbS);
358   //-----------------------------------------------------scope_1 f
359   aAllocator=
360     NCollection_BaseAllocator::CommonBaseAllocator();
361   //
362   //
363   i1=0; 
364   i2=0;
365   aIt.Initialize(myArguments);
366   for (; aIt.More(); aIt.Next()) {
367     const TopoDS_Shape& aS=aIt.Value();
368     if (myMapShapeIndex.IsBound(aS)) {
369       continue;
370     }
371     aI=Append(aS);
372     //
373     InitShape(aI, aS);
374     //
375     i2=NbShapes()-1;
376     aR.SetIndices(i1, i2);
377     myRanges.Append(aR);
378     i1=i2+1;
379   }
380   //
381   aTolAdd = Max(theFuzz, Precision::Confusion()) * 0.5;
382   myNbSourceShapes = NbShapes();
383   //
384   // 2 Bounding Boxes
385   //
386   // 2.1 Vertex
387   for (j=0; j<myNbSourceShapes; ++j) {
388     BOPDS_ShapeInfo& aSI=ChangeShapeInfo(j);
389     //
390     const TopoDS_Shape& aS=aSI.Shape();
391     //
392     aTS=aSI.ShapeType();
393     //
394     if (aTS==TopAbs_VERTEX) {
395       Bnd_Box& aBox=aSI.ChangeBox();
396       const TopoDS_Vertex& aV=*((TopoDS_Vertex*)&aS);
397       const gp_Pnt& aP=BRep_Tool::Pnt(aV);
398       aTol = BRep_Tool::Tolerance(aV);
399       aBox.SetGap(aTol + aTolAdd);
400       aBox.Add(aP);
401     }
402   }
403   // 2.2 Edge
404   aNbE=0;
405   for (j=0; j<myNbSourceShapes; ++j) {
406     BOPDS_ShapeInfo& aSI=ChangeShapeInfo(j);
407     //
408     aTS=aSI.ShapeType();
409     if (aTS==TopAbs_EDGE) {
410       const TopoDS_Shape& aS=aSI.Shape();
411       const TopoDS_Edge& aE=*((TopoDS_Edge*)&aS);
412       aTol = BRep_Tool::Tolerance(aE);
413       //
414       if (!BRep_Tool::Degenerated(aE)) {
415         Standard_Boolean bInf1, bInf2;
416         Standard_Integer aIx;
417         Standard_Real aT1, aT2;
418         gp_Pnt aPx;
419         Handle(Geom_Curve) aC3D;
420         TopoDS_Vertex aVx; 
421         TopoDS_Edge aEx;
422         BRep_Builder aBB;
423         BOPDS_ShapeInfo aSIx;
424         //
425         BOPCol_ListOfInteger& aLI=aSI.ChangeSubShapes();
426         //
427         aEx=aE;
428         aEx.Orientation(TopAbs_FORWARD);
429         //
430         aC3D=BRep_Tool::Curve (aEx, aT1, aT2);
431         bInf1=Precision::IsNegativeInfinite(aT1);
432         bInf2=Precision::IsPositiveInfinite(aT2);
433         //
434         if (bInf1) {
435           aC3D->D0(aT1, aPx);
436           aBB.MakeVertex(aVx, aPx, aTol);
437           aVx.Orientation(TopAbs_FORWARD);
438           //
439           aSIx.SetShape(aVx);
440           aSIx.SetShapeType(TopAbs_VERTEX);
441           aSIx.SetFlag(1); //infinite flag
442           //
443           aIx=Append(aSIx);
444           aLI.Append(aIx);
445         }
446         if (bInf2) {
447           aC3D->D0(aT2, aPx);
448           aBB.MakeVertex(aVx, aPx, aTol);
449           aVx.Orientation(TopAbs_REVERSED);
450           //
451           aSIx.SetShape(aVx);
452           aSIx.SetShapeType(TopAbs_VERTEX);
453           aSIx.SetFlag(1);//infinite flag
454           //
455           aIx=Append(aSIx);
456           aLI.Append(aIx);
457         }
458       } 
459       else {
460         aSI.SetFlag(j);
461       }
462       //
463       Bnd_Box& aBox=aSI.ChangeBox();
464       BRepBndLib::Add(aE, aBox);
465       //
466       const BOPCol_ListOfInteger& aLV=aSI.SubShapes(); 
467       aIt1.Initialize(aLV);
468       for (; aIt1.More(); aIt1.Next()) {
469         nV=aIt1.Value();
470         BOPDS_ShapeInfo& aSIV=ChangeShapeInfo(nV);
471         Bnd_Box& aBx=aSIV.ChangeBox();
472         aBox.Add(aBx);
473       }
474       aBox.SetGap(aBox.GetGap() + aTolAdd);
475       ++aNbE;
476     }
477   }
478   // 2.3 Face
479   BOPCol_MapOfInteger aMI(100, aAllocator);
480   BOPCol_MapIteratorOfMapOfInteger aItMI;
481   //
482   aNbF=0;
483   for (j=0; j<myNbSourceShapes; ++j) {
484     BOPDS_ShapeInfo& aSI=ChangeShapeInfo(j);
485     //
486     aTS=aSI.ShapeType();
487     if (aTS==TopAbs_FACE) {
488       const TopoDS_Shape& aS=aSI.Shape();
489       //
490       Bnd_Box& aBox=aSI.ChangeBox();
491       BRepBndLib::Add(aS, aBox);
492       //
493       BOPCol_ListOfInteger& aLW=aSI.ChangeSubShapes(); 
494       aIt1.Initialize(aLW);
495       for (; aIt1.More(); aIt1.Next()) {
496         nW=aIt1.Value();
497         BOPDS_ShapeInfo& aSIW=ChangeShapeInfo(nW);
498         //
499         const BOPCol_ListOfInteger& aLE=aSIW.SubShapes(); 
500         aIt2.Initialize(aLE);
501         for (; aIt2.More(); aIt2.Next()) {
502           nE=aIt2.Value();
503           BOPDS_ShapeInfo& aSIE=ChangeShapeInfo(nE);
504           Bnd_Box& aBx=aSIE.ChangeBox();
505           aBox.Add(aBx);
506           aMI.Add(nE);
507           //
508           const TopoDS_Edge& aE=*(TopoDS_Edge*)(&aSIE.Shape());
509           if (BRep_Tool::Degenerated(aE)) {
510             aSIE.SetFlag(j);
511           }
512           //
513           const BOPCol_ListOfInteger& aLV=aSIE.SubShapes(); 
514           aIt3.Initialize(aLV);
515           for (; aIt3.More(); aIt3.Next()) {
516             nV=aIt3.Value();
517             aMI.Add(nV);
518           }
519         }
520       }//for (; aIt1.More(); aIt1.Next()) {
521       //
522       // pure internal vertices on the face
523       aItS.Initialize(aS);
524       for (; aItS.More(); aItS.Next()) {
525         const TopoDS_Shape& aSx=aItS.Value();
526         if (aSx.ShapeType()==TopAbs_VERTEX){
527           nV=Index(aSx);
528           aMI.Add(nV);
529         }
530       }
531       //
532       //
533       // For a Face: change wires for BRep sub-shapes
534       aLW.Clear();
535       aItMI.Initialize(aMI);
536       for (; aItMI.More(); aItMI.Next()) {
537         nV=aItMI.Value();
538         aLW.Append(nV);
539       }
540       aMI.Clear();
541       aBox.SetGap(aBox.GetGap() + aTolAdd);
542       ++aNbF;
543     }//if (aTS==TopAbs_FACE) {
544   }//for (j=0; j<myNbSourceShapes; ++j) {
545   //
546   // 2.4 Solids
547   for (j=0; j<myNbSourceShapes; ++j) {
548     BOPDS_ShapeInfo& aSI=ChangeShapeInfo(j);
549     //
550     aTS=aSI.ShapeType();
551     if (aTS!=TopAbs_SOLID) {
552       continue;
553     }
554     Bnd_Box& aBox=aSI.ChangeBox();
555     BuildBndBoxSolid(j, aBox); 
556     //
557     //
558     // update sub-shapes by BRep comprising ones
559     aMI.Clear();
560     BOPCol_ListOfInteger& aLI1=aSI.ChangeSubShapes();
561     //
562     aIt1.Initialize(aLI1);
563     for (; aIt1.More(); aIt1.Next()) {
564       n1=aIt1.Value();
565       BOPDS_ShapeInfo& aSI1=ChangeShapeInfo(n1);
566       if (aSI1.ShapeType()!=TopAbs_SHELL) {
567         continue;
568       }
569       //
570       const BOPCol_ListOfInteger& aLI2=aSI1.SubShapes(); 
571       aIt2.Initialize(aLI2);
572       for (; aIt2.More(); aIt2.Next()) {
573         n2=aIt2.Value();
574         BOPDS_ShapeInfo& aSI2=ChangeShapeInfo(n2);
575         if (aSI2.ShapeType()!=TopAbs_FACE) {
576           continue;
577         }
578         //
579         aMI.Add(n2);
580         //
581         const BOPCol_ListOfInteger& aLI3=aSI2.SubShapes(); 
582         aIt3.Initialize(aLI3);
583         for (; aIt3.More(); aIt3.Next()) {
584           n3=aIt3.Value();
585           aMI.Add(n3);
586         }
587       }
588     }
589     //
590     aLI1.Clear();
591     aItMI.Initialize(aMI);
592     for (; aItMI.More(); aItMI.Next()) {
593       n1=aItMI.Value();
594       aLI1.Append(n1);
595     }
596     aMI.Clear();
597   }//for (j=0; j<myNbSourceShapes; ++j) {
598   //
599   aMI.Clear();
600   //-----------------------------------------------------
601   //
602   for (nE=0; nE<myNbSourceShapes; ++nE) {
603     BOPDS_ShapeInfo& aSI=ChangeShapeInfo(nE);
604     if (aSI.ShapeType()!=TopAbs_EDGE) {
605       continue;
606     }
607     //
608     const BOPCol_ListOfInteger& aLV=aSI.SubShapes(); 
609     aIt1.Initialize(aLV);
610     for (; aIt1.More(); aIt1.Next()) {
611       nV=aIt1.Value();
612       if (myMapVE.IsBound(nV)) {
613         BOPCol_ListOfInteger& aLE=myMapVE.ChangeFind(nV);
614         aLE.Append(nE);
615       }
616       else {
617         BOPCol_ListOfInteger aLE(myAllocator);
618         //
619         aLE.Append(nE);
620         myMapVE.Bind(nV, aLE);
621       }
622     }
623   }
624   //
625   BOPCol_DataMapIteratorOfDataMapOfIntegerListOfInteger aItDMILI; 
626   aItDMILI.Initialize(myMapVE);
627   for(; aItDMILI.More(); aItDMILI.Next()) { 
628     BOPCol_MapOfInteger aMFence;
629     BOPCol_ListOfInteger aLEx;
630     //
631     nV=aItDMILI.Key();
632     BOPCol_ListOfInteger& aLE=aItDMILI.ChangeValue();
633     aIt1.Initialize(aLE);
634     for (; aIt1.More(); aIt1.Next()) {
635       nE=aIt1.Value();
636       if(aMFence.Add(nE)) {
637         aLEx.Append(nE);
638       }
639     }
640     //
641     aLE.Clear();
642     aIt1.Initialize(aLEx);
643     for (; aIt1.More(); aIt1.Next()) {
644       nE=aIt1.Value();
645       aLE.Append(nE);
646     }
647   }
648   //-----------------------------------------------------scope_1 t
649   // 3 myPaveBlocksPool
650   // 4. myFaceInfoPool
651   myPaveBlocksPool.SetIncrement(aNbE);
652   myFaceInfoPool.SetIncrement(aNbF);
653 }
654 //=======================================================================
655 //function : InitShape
656 //purpose  : 
657 //=======================================================================
658 void BOPDS_DS::InitShape
659   (const Standard_Integer aI,
660    const TopoDS_Shape& aS)
661 {
662   Standard_Integer aIx;
663   TopoDS_Iterator aIt;
664   BOPCol_ListIteratorOfListOfInteger aIt1;
665   //
666   BOPDS_ShapeInfo& aSI=ChangeShapeInfo(aI);
667   aSI.SetShapeType(aS.ShapeType());
668   BOPCol_ListOfInteger& aLI=aSI.ChangeSubShapes();
669   //
670   BOPCol_MapOfInteger aM;
671   //
672   aIt1.Initialize(aLI);
673   for (; aIt1.More(); aIt1.Next()) {
674     aM.Add(aIt1.Value());
675   }
676   //
677   aIt.Initialize(aS);
678   for (; aIt.More(); aIt.Next()) {
679     const TopoDS_Shape& aSx=aIt.Value();
680     const Standard_Integer* pIx = myMapShapeIndex.Seek(aSx);
681     aIx = (pIx ? *pIx : Append(aSx));
682     //
683     InitShape(aIx, aSx);
684     //
685     if (aM.Add(aIx)) {
686       aLI.Append(aIx);
687     }
688   }
689 }
690
691 //=======================================================================
692 //function : HasInterf
693 //purpose  : 
694 //=======================================================================
695 Standard_Boolean BOPDS_DS::HasInterf(const Standard_Integer theI) const
696 {
697   Standard_Integer n1, n2;
698   Standard_Boolean bRet;
699   BOPDS_MapIteratorOfMapOfPair aIt;
700   //
701   bRet = Standard_False;
702   //
703   aIt.Initialize(myInterfTB);
704   for (; aIt.More(); aIt.Next()) {
705     const BOPDS_Pair& aPK = aIt.Value();
706     aPK.Indices(n1, n2);
707     if (n1 == theI || n2 == theI) {
708       bRet = Standard_True;
709       break;
710     }
711   }
712   //
713   return bRet;
714 }
715 //=======================================================================
716 //function : HasInterfShapeSubShapes
717 //purpose  : 
718 //=======================================================================
719 Standard_Boolean BOPDS_DS::HasInterfShapeSubShapes
720   (const Standard_Integer theI1,
721    const Standard_Integer theI2,
722    const Standard_Boolean theFlag)const
723 {
724   Standard_Boolean bRet;
725   Standard_Integer n2;
726   BOPCol_ListIteratorOfListOfInteger aIt;
727   bRet = Standard_False;
728   //
729   const BOPDS_ShapeInfo& aSI=ShapeInfo(theI2);
730   const BOPCol_ListOfInteger& aLI=aSI.SubShapes(); 
731   aIt.Initialize(aLI);
732   for (; aIt.More(); aIt.Next()) {
733     n2=aIt.Value();
734     bRet=HasInterf(theI1, n2);
735     if (theFlag) {
736       if(bRet) {
737         break;
738       }
739     }
740     else {
741       if(!bRet) {
742         break;
743       }
744     }
745   }
746   return bRet;
747 }
748 //=======================================================================
749 //function : HasInterfSubShapes
750 //purpose  : 
751 //=======================================================================
752 Standard_Boolean BOPDS_DS::HasInterfSubShapes
753   (const Standard_Integer theI1,
754    const Standard_Integer theI2)const
755 {
756   Standard_Boolean bRet;
757   Standard_Integer n1;
758   BOPCol_ListIteratorOfListOfInteger aIt;
759   bRet = Standard_False;
760   //
761   const BOPDS_ShapeInfo& aSI=ShapeInfo(theI1);
762   const BOPCol_ListOfInteger& aLI=aSI.SubShapes(); 
763   aIt.Initialize(aLI);
764   for (; aIt.More(); aIt.Next()) {
765     n1=aIt.Value();
766     bRet=HasInterfShapeSubShapes(n1, theI2);
767     if(bRet) {
768       break;
769     }
770   }
771   return bRet;
772 }
773 //
774 // PaveBlocks
775 //=======================================================================
776 //function : PaveBlocksPool
777 //purpose  : 
778 //=======================================================================
779 const BOPDS_VectorOfListOfPaveBlock& BOPDS_DS::PaveBlocksPool()const
780 {
781   return myPaveBlocksPool;
782 }
783 //=======================================================================
784 //function : ChangePaveBlocksPool
785 //purpose  : 
786 //=======================================================================
787 BOPDS_VectorOfListOfPaveBlock& BOPDS_DS::ChangePaveBlocksPool()
788 {
789   return myPaveBlocksPool;
790 }
791 //=======================================================================
792 //function : HasPaveBlocks
793 //purpose  : 
794 //=======================================================================
795 Standard_Boolean BOPDS_DS::HasPaveBlocks(const Standard_Integer theI)const
796 {
797   return ShapeInfo(theI).HasReference();
798 }
799 //=======================================================================
800 //function : PaveBlocks
801 //purpose  : 
802 //=======================================================================
803 const BOPDS_ListOfPaveBlock& BOPDS_DS::PaveBlocks
804   (const Standard_Integer theI)const
805 {
806   static BOPDS_ListOfPaveBlock sLPB;
807   Standard_Integer aRef;
808   //
809   if (HasPaveBlocks(theI)) { 
810     aRef=ShapeInfo(theI).Reference();
811     const BOPDS_ListOfPaveBlock& aLPB=myPaveBlocksPool(aRef);
812     return aLPB;
813   }
814   return sLPB;
815 }
816
817 //=======================================================================
818 //function : ChangePaveBlocks
819 //purpose  : 
820 //=======================================================================
821 BOPDS_ListOfPaveBlock& BOPDS_DS::ChangePaveBlocks
822   (const Standard_Integer theI)
823 {
824   Standard_Boolean bHasReference;
825   Standard_Integer aRef;
826   //
827   BOPDS_ShapeInfo& aSI=ChangeShapeInfo(theI);
828   bHasReference=aSI.HasReference();
829   if (!bHasReference) {
830     InitPaveBlocks(theI);
831   }
832   //
833   aRef=aSI.Reference();
834   return myPaveBlocksPool(aRef);
835 }
836 //=======================================================================
837 //function : InitPaveBlocks
838 //purpose  : 
839 //=======================================================================
840 void BOPDS_DS::InitPaveBlocks(const Standard_Integer theI)
841 {
842   Standard_Integer nV=0, iRef, aNbV, nVSD;
843   Standard_Real aT;
844   TopAbs_Orientation aOrE;
845   TopoDS_Vertex aV;
846   BOPCol_ListIteratorOfListOfInteger aIt;
847   BOPDS_Pave aPave;
848   Handle(BOPDS_PaveBlock) aPB;
849   //
850   BOPDS_ShapeInfo& aSI=ChangeShapeInfo(theI);
851   const TopoDS_Edge& aE=*(TopoDS_Edge*)(&aSI.Shape());
852   aOrE=aE.Orientation();
853   //
854   const BOPCol_ListOfInteger& aLV=aSI.SubShapes();
855   aNbV=aLV.Extent();
856   if (!aNbV) {
857     return;
858   }
859   //
860   aPB=new BOPDS_PaveBlock; 
861   aPB->SetOriginalEdge(theI);
862   //
863   if (aOrE!=TopAbs_INTERNAL) {
864     aIt.Initialize(aLV);
865     for (; aIt.More(); aIt.Next()) {
866       nV=aIt.Value();
867       //
868       const BOPDS_ShapeInfo& aSIV=ShapeInfo(nV);
869       aV=*(TopoDS_Vertex*)(&aSIV.Shape());
870       if (aSIV.HasFlag()) {
871         aT=ComputeParameter(aV, aE); 
872       }
873       else {
874         aT=BRep_Tool::Parameter(aV, aE);
875       } 
876       //
877       if (HasShapeSD(nV, nVSD)) {
878         nV=nVSD;
879       }
880       aPave.SetIndex(nV);
881       aPave.SetParameter(aT);
882       if (aSI.HasFlag())
883         // for a degenerated edge append pave unconditionally
884         aPB->AppendExtPave1(aPave);
885       else
886         aPB->AppendExtPave(aPave);
887     }
888     //
889     if (aNbV==1) {
890       aV.Reverse();
891       aT=BRep_Tool::Parameter(aV, aE);
892       aPave.SetIndex(nV);
893       aPave.SetParameter(aT);
894       aPB->AppendExtPave1(aPave);
895     }
896   }
897   //
898   else {
899     TopoDS_Iterator aItE;
900     //
901     aItE.Initialize(aE, Standard_False, Standard_True);
902     for (; aItE.More(); aItE.Next()) {
903       aV=*((TopoDS_Vertex*)&aItE.Value());
904       nV=Index(aV);
905       //
906       const BOPDS_ShapeInfo& aSIV=ShapeInfo(nV);
907       if (aSIV.HasFlag()) {
908         aT=ComputeParameter(aV, aE); 
909       }
910       else {
911         aT=BRep_Tool::Parameter(aV, aE);
912       }
913       //
914       if (HasShapeSD(nV, nVSD)) {
915         nV=nVSD;
916       }
917       aPave.SetIndex(nV);
918       aPave.SetParameter(aT);
919       aPB->AppendExtPave1(aPave);
920     }
921   }
922   //
923   BOPDS_ListOfPaveBlock &aLPB=myPaveBlocksPool.Append1();
924   iRef=myPaveBlocksPool.Extent()-1;
925   //
926   aPB->Update(aLPB, Standard_False);
927   aSI.SetReference(iRef);
928 }
929 //=======================================================================
930 //function : UpdatePaveBlocks
931 //purpose  : 
932 //=======================================================================
933 void BOPDS_DS::UpdatePaveBlocks()
934 {
935   Standard_Boolean bIsToUpdate;
936   Standard_Integer i, aNbPBP;
937   BOPDS_ListOfPaveBlock aLPBN(myAllocator);
938   BOPDS_ListIteratorOfListOfPaveBlock aItPB, aItPBN;
939   //
940   BOPDS_VectorOfListOfPaveBlock& aPBP=myPaveBlocksPool;
941   //
942   aNbPBP=aPBP.Size();
943   for (i=0; i<aNbPBP; ++i) {
944     BOPDS_ListOfPaveBlock& aLPB=aPBP(i); 
945     //
946     aItPB.Initialize(aLPB);
947     for (; aItPB.More(); aItPB.Next()) {
948       Handle(BOPDS_PaveBlock)& aPB=aItPB.ChangeValue();
949       //
950       bIsToUpdate=aPB->IsToUpdate();
951       if (bIsToUpdate){
952         aLPBN.Clear();
953         aPB->Update(aLPBN);
954         
955         aItPBN.Initialize(aLPBN);
956         for (; aItPBN.More(); aItPBN.Next()) {
957           Handle(BOPDS_PaveBlock)& aPBN=aItPBN.ChangeValue();
958           aLPB.Append(aPBN);
959         }
960         aLPB.Remove(aItPB);
961       }
962     }// for (; aItPB.More(); aItPB.Next()) {
963   }// for (i=0; i<aNbPBP; ++i) {
964 }
965 //=======================================================================
966 //function : UpdatePaveBlock
967 //purpose  : 
968 //=======================================================================
969 void BOPDS_DS::UpdatePaveBlock(const Handle(BOPDS_PaveBlock)& thePB)
970 {
971   if (!thePB->IsToUpdate()){
972     return;
973   }
974   //
975   Standard_Integer nE, iRef;
976   BOPDS_ListIteratorOfListOfPaveBlock aItPB, aItPBN;
977   BOPDS_ListOfPaveBlock aLPBN(myAllocator);
978   Handle(BOPDS_PaveBlock) aPB;
979   //
980   BOPDS_VectorOfListOfPaveBlock& aPBP=myPaveBlocksPool;
981   //
982   nE=thePB->OriginalEdge();
983   BOPDS_ShapeInfo& aSI=ChangeShapeInfo(nE);
984   iRef=aSI.Reference();
985   BOPDS_ListOfPaveBlock& aLPB=aPBP(iRef); 
986   //
987   aItPB.Initialize(aLPB);
988   for (; aItPB.More(); aItPB.Next()) {
989     aPB=aItPB.ChangeValue();
990     if (aPB==thePB) {
991       aPB->Update(aLPBN);
992       aLPB.Append(aLPBN);
993       aLPB.Remove(aItPB);
994       break;
995     }
996   }
997 }
998 //=======================================================================
999 //function : UpdateCommonBlock
1000 //purpose  : 
1001 //=======================================================================
1002 void BOPDS_DS::UpdateCommonBlock(const Handle(BOPDS_CommonBlock)& theCB,
1003                                  const Standard_Real theFuzz)
1004 {
1005   Standard_Integer nE, iRef, n1, n2;
1006   BOPDS_ListIteratorOfListOfPaveBlock aItPB, aItPBCB, aItPBN;
1007   BOPDS_ListOfPaveBlock aLPBN;
1008   NCollection_DataMap<BOPDS_Pair, BOPDS_ListOfPaveBlock, BOPDS_PairMapHasher> aMPKLPB;
1009   NCollection_DataMap<BOPDS_Pair, BOPDS_ListOfPaveBlock, BOPDS_PairMapHasher>::Iterator aItMPKLPB;
1010   Handle(BOPDS_PaveBlock) aPB;
1011   Handle(BOPDS_CommonBlock) aCBx;
1012   BOPDS_Pair aPK;
1013   //
1014   const BOPDS_ListOfPaveBlock& aLPBCB=theCB->PaveBlocks();
1015   if (!aLPBCB.First()->IsToUpdate()){
1016     return;
1017   }
1018   //
1019   const BOPCol_ListOfInteger& aLF=theCB->Faces();
1020   //
1021   BOPDS_VectorOfListOfPaveBlock& aPBP=myPaveBlocksPool;
1022   //
1023   aItPBCB.Initialize(aLPBCB);
1024   for (; aItPBCB.More(); aItPBCB.Next()) {
1025     const Handle(BOPDS_PaveBlock)& aPBCB=aItPBCB.ChangeValue();
1026     //
1027     nE=aPBCB->OriginalEdge();
1028     iRef=ChangeShapeInfo(nE).Reference();
1029     BOPDS_ListOfPaveBlock& aLPB=aPBP(iRef); 
1030     //
1031     aItPB.Initialize(aLPB);
1032     for (; aItPB.More(); aItPB.Next()) {
1033       aPB=aItPB.ChangeValue();
1034       if (aPB==aPBCB) {
1035         //
1036         aLPBN.Clear();
1037         aPB->Update(aLPBN);
1038         //
1039         aItPBN.Initialize(aLPBN);
1040         for (; aItPBN.More(); aItPBN.Next()) {
1041           Handle(BOPDS_PaveBlock)& aPBN=aItPBN.ChangeValue();
1042           aLPB.Append(aPBN);
1043           //
1044           aPBN->Indices(n1, n2);
1045           aPK.SetIndices(n1, n2);
1046           if (aMPKLPB.IsBound(aPK)) {
1047             BOPDS_ListOfPaveBlock& aLPBx=aMPKLPB.ChangeFind(aPK);
1048             aLPBx.Append(aPBN);
1049           }
1050           else {
1051             BOPDS_ListOfPaveBlock aLPBx;
1052             aLPBx.Append(aPBN);
1053             aMPKLPB.Bind(aPK, aLPBx);
1054           }
1055         }
1056         aLPB.Remove(aItPB);
1057         break;
1058       }
1059     }
1060   }
1061   //
1062   aItMPKLPB.Initialize(aMPKLPB);
1063   for (; aItMPKLPB.More(); aItMPKLPB.Next()) {
1064     BOPDS_ListOfPaveBlock& aLPBx=aItMPKLPB.ChangeValue();
1065     //
1066     while (aLPBx.Extent()) {
1067       Standard_Boolean bCoinside;
1068       BOPDS_ListOfPaveBlock aLPBxN;
1069       //
1070       aItPB.Initialize(aLPBx);
1071       for(; aItPB.More(); ) {
1072         const Handle(BOPDS_PaveBlock)& aPBx=aItPB.Value();
1073         if (aLPBxN.Extent()) {
1074           const Handle(BOPDS_PaveBlock)& aPBCx = aLPBxN.First();
1075           bCoinside = CheckCoincidence(aPBx, aPBCx, theFuzz);
1076           if (bCoinside) {
1077             aLPBxN.Append(aPBx);
1078             aLPBx.Remove(aItPB);
1079             continue;
1080           }//if (bCoinside) {
1081         }//if (aLPBxN.Extent()) {
1082         else {
1083           aLPBxN.Append(aPBx);
1084           aLPBx.Remove(aItPB);
1085           continue;
1086         }
1087         aItPB.Next();
1088       }//for(; aItPB.More(); ) {
1089       //
1090       aCBx=new BOPDS_CommonBlock;
1091       aCBx->SetPaveBlocks(aLPBxN);
1092       aCBx->SetFaces(aLF);
1093       //
1094       aItPB.Initialize(aLPBxN);
1095       for (; aItPB.More(); aItPB.Next()) {
1096         aPB=aItPB.ChangeValue();
1097         SetCommonBlock(aPB, aCBx);
1098       }
1099     }
1100   }
1101 }
1102
1103 //=======================================================================
1104 // function: RealPaveBlock
1105 // purpose: 
1106 //=======================================================================
1107 Handle(BOPDS_PaveBlock) BOPDS_DS::RealPaveBlock
1108     (const Handle(BOPDS_PaveBlock)& thePB) const
1109 {
1110   if (IsCommonBlock(thePB)) {
1111     const Handle(BOPDS_CommonBlock)& aCB = CommonBlock(thePB);
1112     const Handle(BOPDS_PaveBlock)& aPB = aCB->PaveBlock1();
1113     return aPB;
1114   }
1115   return thePB;
1116 }
1117
1118 //=======================================================================
1119 // function: IsCommonBlockOnEdge
1120 // purpose: 
1121 //=======================================================================
1122 Standard_Boolean BOPDS_DS::IsCommonBlockOnEdge
1123     (const Handle(BOPDS_PaveBlock)& thePB) const
1124 {
1125   if (IsCommonBlock(thePB)) {
1126     const Handle(BOPDS_CommonBlock)& aCB = CommonBlock(thePB);
1127     return aCB->PaveBlocks().Extent()>1;
1128   } 
1129   return Standard_False;
1130 }
1131
1132 //=======================================================================
1133 //function : IsCommonBlock
1134 //purpose  : 
1135 //=======================================================================
1136 Standard_Boolean BOPDS_DS::IsCommonBlock
1137     (const Handle(BOPDS_PaveBlock)& thePB) const
1138 {
1139   return myMapPBCB.IsBound(thePB);
1140 }
1141
1142 //=======================================================================
1143 //function : CommonBlock
1144 //purpose  : 
1145 //=======================================================================
1146 Handle(BOPDS_CommonBlock) BOPDS_DS::CommonBlock
1147     (const Handle(BOPDS_PaveBlock)& thePB) const
1148 {
1149   return (IsCommonBlock(thePB) ? myMapPBCB.Find(thePB) : NULL);
1150 }
1151
1152 //=======================================================================
1153 //function : SetCommonBlock
1154 //purpose  : 
1155 //=======================================================================
1156 void BOPDS_DS::SetCommonBlock(const Handle(BOPDS_PaveBlock)& thePB,
1157                               const Handle(BOPDS_CommonBlock)& theCB)
1158 {
1159   if (IsCommonBlock(thePB)) {
1160     Handle(BOPDS_CommonBlock)& aCB = myMapPBCB.ChangeFind(thePB);
1161     aCB=theCB;
1162   }
1163   else {
1164     myMapPBCB.Bind(thePB, theCB);
1165   }
1166 }
1167
1168 //
1169 // FaceInfo
1170 //
1171
1172 //=======================================================================
1173 //function : FaceInfoPool
1174 //purpose  : 
1175 //=======================================================================
1176 const BOPDS_VectorOfFaceInfo& BOPDS_DS::FaceInfoPool()const
1177 {
1178   return myFaceInfoPool;
1179 }
1180 //=======================================================================
1181 //function : HasFaceInfo
1182 //purpose  : 
1183 //=======================================================================
1184 Standard_Boolean BOPDS_DS::HasFaceInfo(const Standard_Integer theI)const
1185 {
1186   return ShapeInfo(theI).HasReference();
1187 }
1188 //=======================================================================
1189 //function : FaceInfo
1190 //purpose  : 
1191 //=======================================================================
1192 const BOPDS_FaceInfo& BOPDS_DS::FaceInfo(const Standard_Integer theI)const
1193 {
1194   static BOPDS_FaceInfo sFI;
1195   Standard_Integer aRef;
1196   //
1197   if (HasFaceInfo(theI)) { 
1198     aRef=ShapeInfo(theI).Reference();
1199     const BOPDS_FaceInfo& aFI=myFaceInfoPool(aRef);
1200     return aFI;
1201   }
1202   return sFI;
1203 }
1204 //=======================================================================
1205 //function : ChangeFaceInfo
1206 //purpose  : 
1207 //=======================================================================
1208 BOPDS_FaceInfo& BOPDS_DS::ChangeFaceInfo(const Standard_Integer theI)
1209 {
1210   Standard_Boolean bHasReference;
1211   Standard_Integer aRef;
1212   BOPDS_FaceInfo* pFI;
1213   //
1214   BOPDS_ShapeInfo& aSI=ChangeShapeInfo(theI);
1215   bHasReference=aSI.HasReference();
1216   if (!bHasReference) {
1217     InitFaceInfo(theI);
1218   }
1219   //
1220   aRef=aSI.Reference();
1221   const BOPDS_FaceInfo& aFI=myFaceInfoPool(aRef);
1222   pFI=(BOPDS_FaceInfo*)&aFI;
1223   return *pFI;
1224 }
1225 //=======================================================================
1226 //function : InitFaceInfo
1227 //purpose  : 
1228 //=======================================================================
1229 void BOPDS_DS::InitFaceInfo(const Standard_Integer theI)
1230 {
1231   Standard_Integer iRef;
1232   //
1233   BOPDS_ShapeInfo& aSI=ChangeShapeInfo(theI);
1234   BOPDS_FaceInfo &aFI=myFaceInfoPool.Append1();
1235   iRef=myFaceInfoPool.Extent()-1;
1236   aSI.SetReference(iRef);
1237   //
1238   aFI.SetIndex(theI);
1239   UpdateFaceInfoIn(theI);
1240   UpdateFaceInfoOn(theI);
1241 }
1242 //=======================================================================
1243 //function : UpdateFaceInfoIn
1244 //purpose  : 
1245 //=======================================================================
1246 void BOPDS_DS::UpdateFaceInfoIn(const Standard_Integer theI)
1247 {
1248   Standard_Integer iRef;
1249   //
1250   BOPDS_ShapeInfo& aSI=ChangeShapeInfo(theI);
1251   if (aSI.HasReference()) {
1252     iRef=aSI.Reference();
1253     BOPDS_FaceInfo &aFI=myFaceInfoPool(iRef);
1254     //
1255     BOPDS_IndexedMapOfPaveBlock& aMPBIn=aFI.ChangePaveBlocksIn();
1256     BOPCol_MapOfInteger& aMVIn=aFI.ChangeVerticesIn();
1257     aMPBIn.Clear();
1258     aMVIn.Clear();
1259     FaceInfoIn(theI, aMPBIn, aMVIn);
1260   }
1261 }
1262 //=======================================================================
1263 //function : UpdateFaceInfoOn
1264 //purpose  : 
1265 //=======================================================================
1266 void BOPDS_DS::UpdateFaceInfoOn(const Standard_Integer theI)
1267 {
1268   Standard_Integer iRef;
1269   //
1270   BOPDS_ShapeInfo& aSI=ChangeShapeInfo(theI);
1271   if (aSI.HasReference()) {
1272     iRef=aSI.Reference();
1273     BOPDS_FaceInfo &aFI=myFaceInfoPool(iRef);
1274     //
1275     BOPDS_IndexedMapOfPaveBlock& aMPBOn=aFI.ChangePaveBlocksOn();
1276     BOPCol_MapOfInteger& aMVOn=aFI.ChangeVerticesOn();
1277     aMPBOn.Clear();
1278     aMVOn.Clear();
1279     FaceInfoOn(theI, aMPBOn, aMVOn);
1280   }
1281 }
1282 //=======================================================================
1283 //function : FaceInfoOn
1284 //purpose  : 
1285 //=======================================================================
1286 void BOPDS_DS::FaceInfoOn(const Standard_Integer theF,
1287                           BOPDS_IndexedMapOfPaveBlock& theMPB,
1288                           BOPCol_MapOfInteger& theMI)
1289 {
1290   Standard_Integer nS, nSD, nV1, nV2;
1291   BOPCol_ListIteratorOfListOfInteger aIt;
1292   BOPDS_ListIteratorOfListOfPaveBlock aItPB;
1293   //
1294   const BOPDS_ShapeInfo& aSI=ShapeInfo(theF);
1295   const BOPCol_ListOfInteger& aLI=aSI.SubShapes();
1296   aIt.Initialize(aLI);
1297   for (; aIt.More(); aIt.Next()) {
1298     nS=aIt.Value();
1299     const BOPDS_ShapeInfo& aSIE=ShapeInfo(nS);
1300     if (aSIE.ShapeType()==TopAbs_EDGE) {
1301       const BOPDS_ListOfPaveBlock& aLPB=PaveBlocks(nS);
1302       aItPB.Initialize(aLPB);
1303       for (; aItPB.More(); aItPB.Next()) {
1304         const Handle(BOPDS_PaveBlock)& aPB=aItPB.Value();
1305         aPB->Indices(nV1, nV2);
1306         theMI.Add(nV1);
1307         theMI.Add(nV2);
1308         Handle(BOPDS_PaveBlock) aPBR=RealPaveBlock(aPB);
1309         theMPB.Add(aPBR);
1310       }
1311     }//if (aSIE.ShapeType()==TopAbs_EDGE) 
1312     else {
1313       // nE is TopAbs_VERTEX
1314       if (HasShapeSD(nS, nSD)) {
1315         nS=nSD;
1316       }
1317       theMI.Add(nS);
1318     }
1319   }
1320 }
1321 //=======================================================================
1322 //function : FaceInfoIn
1323 //purpose  : 
1324 //=======================================================================
1325 void BOPDS_DS::FaceInfoIn(const Standard_Integer theF,
1326                           BOPDS_IndexedMapOfPaveBlock& theMPB,
1327                           BOPCol_MapOfInteger& theMI)
1328 {
1329   Standard_Integer i, aNbVF, aNbEF, nV, nE, nVSD;
1330   TopoDS_Iterator aItS;
1331   BOPDS_ListIteratorOfListOfPaveBlock aItPB;
1332   //
1333   // 1. Pure internal vertices on the face
1334   const TopoDS_Shape& aF=Shape(theF);
1335   aItS.Initialize(aF);
1336   for (; aItS.More(); aItS.Next()) {
1337     const TopoDS_Shape& aSx=aItS.Value();
1338     if (aSx.ShapeType()==TopAbs_VERTEX){
1339       nV=Index(aSx);
1340       if (HasShapeSD(nV, nVSD)) {
1341         nV=nVSD;
1342       }
1343       theMI.Add(nV);
1344     }
1345   }
1346   //
1347   // 2. aVFs
1348   BOPDS_VectorOfInterfVF& aVFs=InterfVF();
1349   aNbVF=aVFs.Extent();
1350   for (i=0; i<aNbVF; ++i) {
1351     BOPDS_InterfVF& aVF=aVFs(i);
1352     if(aVF.Contains(theF)) {
1353       nV=aVF.OppositeIndex(theF);
1354       if (HasShapeSD(nV, nVSD)) {
1355         nV=nVSD;
1356       }
1357       theMI.Add(nV);
1358     }
1359   }
1360   //
1361   // 3. aEFs
1362   BOPDS_VectorOfInterfEF& aEFs=InterfEF();
1363   aNbEF=aEFs.Extent();
1364   for (i=0; i<aNbEF; ++i) {
1365     BOPDS_InterfEF& aEF=aEFs(i);
1366     if(aEF.Contains(theF)) {
1367       if(aEF.HasIndexNew(nV)) {
1368         theMI.Add(nV);
1369       }
1370       else {
1371         nE=aEF.OppositeIndex(theF);
1372         const BOPDS_ListOfPaveBlock& aLPB=PaveBlocks(nE);
1373         aItPB.Initialize(aLPB);
1374         for (; aItPB.More(); aItPB.Next()) {
1375           const Handle(BOPDS_PaveBlock)& aPB=aItPB.Value();
1376           if (IsCommonBlock(aPB)) {
1377             const Handle(BOPDS_CommonBlock)& aCB=CommonBlock(aPB);
1378             if (aCB->Contains(theF)) {
1379               const Handle(BOPDS_PaveBlock)& aPB1=aCB->PaveBlock1();
1380               theMPB.Add(aPB1);
1381             }
1382           }
1383         }// for (; aItPB.More(); aItPB.Next()) {
1384       }// else {
1385     }// if(aEF.Contains(theF)) {
1386   }// for (i=0; i<aNbEF; ++i) {
1387 }
1388
1389 //=======================================================================
1390 //function : RefineFaceInfoOn
1391 //purpose  : 
1392 //=======================================================================
1393 void BOPDS_DS::RefineFaceInfoOn()
1394 {
1395   Standard_Integer i, aNb, nF, aNbPB, j;
1396   BOPDS_IndexedMapOfPaveBlock aMPB;
1397   //
1398   aNb=myFaceInfoPool.Extent();
1399   for (i=0; i<aNb; ++i) {
1400     BOPDS_FaceInfo &aFI=myFaceInfoPool(i);
1401     nF=aFI.Index();
1402     UpdateFaceInfoOn(nF);
1403     BOPDS_IndexedMapOfPaveBlock& aMPBOn=aFI.ChangePaveBlocksOn();
1404     //
1405     aMPB.Clear();
1406     aMPB.Assign(aMPBOn);
1407     aMPBOn.Clear();
1408     //
1409     aNbPB=aMPB.Extent();
1410     for (j=1; j<=aNbPB; ++j) {
1411       const Handle(BOPDS_PaveBlock)& aPB=aMPB(j);
1412       if (aPB->HasEdge()) {
1413         aMPBOn.Add(aPB);
1414       }
1415     }
1416   }
1417 }
1418 //=======================================================================
1419 //function : AloneVertices
1420 //purpose  : 
1421 //=======================================================================
1422 void BOPDS_DS::AloneVertices(const Standard_Integer theI,
1423                              BOPCol_ListOfInteger& theLI)const
1424 {
1425   if (HasFaceInfo(theI)) {
1426     //
1427     Standard_Integer i, j, nV1, nV2, nV, aNbPB;
1428     BOPCol_MapIteratorOfMapOfInteger aItMI;
1429     //
1430     BOPCol_MapOfInteger aMI(100, myAllocator);
1431     //
1432     const BOPDS_FaceInfo& aFI=FaceInfo(theI);
1433     //
1434     for (i = 0; i < 2; ++i) {
1435       const BOPDS_IndexedMapOfPaveBlock& aMPB=
1436         (!i) ? aFI.PaveBlocksIn() : aFI.PaveBlocksSc();
1437       aNbPB = aMPB.Extent();
1438       for (j = 1; j <= aNbPB; ++j) {
1439         const Handle(BOPDS_PaveBlock)& aPB = aMPB(j);
1440         aPB->Indices(nV1, nV2);
1441         aMI.Add(nV1);
1442         aMI.Add(nV2);
1443       }
1444     }
1445     //
1446     for (i=0; i<2; ++i) {
1447       const BOPCol_MapOfInteger& aMIV=
1448         (!i) ? aFI.VerticesIn() : aFI.VerticesSc();
1449       aItMI.Initialize(aMIV);
1450       for (; aItMI.More(); aItMI.Next()) {
1451         nV=aItMI.Value();
1452         if (nV>=0) {
1453           if (aMI.Add(nV)) {
1454             theLI.Append(nV);
1455           }
1456         }
1457       }
1458     }
1459   }
1460 }
1461 //=======================================================================
1462 //function : VerticesOnIn
1463 //purpose  : 
1464 //=======================================================================
1465 void BOPDS_DS::SubShapesOnIn
1466   (const Standard_Integer nF1,
1467    const Standard_Integer nF2,
1468    BOPCol_MapOfInteger& theMVOnIn,
1469    BOPDS_IndexedMapOfPaveBlock& thePBOnIn,
1470    BOPDS_MapOfPaveBlock& theCommonPB)const
1471 {
1472   Standard_Integer i, j, nV, nV1, nV2, aNbPB;
1473   BOPCol_MapIteratorOfMapOfInteger aIt;
1474   BOPDS_IndexedMapOfPaveBlock pMPB[4];
1475   //
1476   const BOPDS_FaceInfo& aFI1=FaceInfo(nF1);
1477   const BOPDS_FaceInfo& aFI2=FaceInfo(nF2);
1478   //
1479   pMPB[0]=aFI1.PaveBlocksOn();
1480   pMPB[1]=aFI1.PaveBlocksIn();
1481   pMPB[2]=aFI2.PaveBlocksOn();
1482   pMPB[3]=aFI2.PaveBlocksIn();
1483   //
1484   for (i=0; i<4; ++i) {
1485     aNbPB = pMPB[i].Extent();
1486     for (j = 1; j <= aNbPB; ++j) {
1487       const Handle(BOPDS_PaveBlock)& aPB = pMPB[i](j);
1488       thePBOnIn.Add(aPB);
1489       aPB->Indices(nV1, nV2);
1490       theMVOnIn.Add(nV1);
1491       theMVOnIn.Add(nV2);
1492       if (i < 2) {
1493         if (pMPB[2].Contains(aPB) || pMPB[3].Contains(aPB))
1494           theCommonPB.Add(aPB);
1495       }
1496     }
1497   }
1498   //
1499   const BOPCol_MapOfInteger& aMVOn1=aFI1.VerticesOn();
1500   const BOPCol_MapOfInteger& aMVIn1=aFI1.VerticesIn();
1501   const BOPCol_MapOfInteger& aMVOn2=aFI2.VerticesOn();
1502   const BOPCol_MapOfInteger& aMVIn2=aFI2.VerticesIn();
1503   //
1504   for (i=0; i<2; ++i) {
1505     const BOPCol_MapOfInteger& aMV1=(!i) ? aMVOn1 : aMVIn1;
1506     aIt.Initialize(aMV1);
1507     for (; aIt.More(); aIt.Next()) {
1508       nV=aIt.Value();
1509       if (aMVOn2.Contains(nV) || aMVIn2.Contains(nV)) {
1510         theMVOnIn.Add(nV);
1511       }
1512     }
1513   }
1514
1515 //=======================================================================
1516 //function : SharedEdges
1517 //purpose  : 
1518 //=======================================================================
1519 void BOPDS_DS::SharedEdges(const Standard_Integer nF1,
1520       const Standard_Integer nF2,
1521       BOPCol_ListOfInteger& theLI,
1522       const Handle(NCollection_BaseAllocator)& aAllocator)
1523 {
1524   Standard_Integer nE, nSp;
1525   BOPCol_ListIteratorOfListOfInteger aItLI;
1526   BOPDS_ListIteratorOfListOfPaveBlock aItLPB;
1527   BOPCol_MapOfInteger aMI(100, aAllocator);
1528   //
1529   const BOPDS_ShapeInfo& aSI1=ShapeInfo(nF1);
1530   const BOPCol_ListOfInteger& aLI1=aSI1.SubShapes();
1531   aItLI.Initialize(aLI1);
1532   for (; aItLI.More(); aItLI.Next()) {
1533     nE=aItLI.Value();
1534     const BOPDS_ShapeInfo& aSIE=ChangeShapeInfo(nE);
1535     if(aSIE.ShapeType()==TopAbs_EDGE) {
1536       const BOPDS_ListOfPaveBlock& aLPB=PaveBlocks(nE);
1537       if (aLPB.IsEmpty()) {
1538         aMI.Add(nE);
1539       }
1540       else {
1541         aItLPB.Initialize(aLPB);
1542         for (; aItLPB.More(); aItLPB.Next()) {
1543           const Handle(BOPDS_PaveBlock) aPB=RealPaveBlock(aItLPB.Value());
1544           nSp=aPB->Edge();
1545           aMI.Add(nSp);
1546         }
1547       }
1548     }
1549   }
1550   // 
1551   const BOPDS_ShapeInfo& aSI2=ShapeInfo(nF2);
1552   const BOPCol_ListOfInteger& aLI2=aSI2.SubShapes();
1553   aItLI.Initialize(aLI2);
1554   for (; aItLI.More(); aItLI.Next()) {
1555     nE=aItLI.Value();
1556     const BOPDS_ShapeInfo& aSIE=ChangeShapeInfo(nE);
1557     if(aSIE.ShapeType()==TopAbs_EDGE) {
1558       const BOPDS_ListOfPaveBlock& aLPB=PaveBlocks(nE);
1559       if (aLPB.IsEmpty()) {
1560         if (aMI.Contains(nE)) {
1561           theLI.Append(nE);
1562         }
1563       }
1564       else {
1565         aItLPB.Initialize(aLPB);
1566         for (; aItLPB.More(); aItLPB.Next()) {
1567           const Handle(BOPDS_PaveBlock) aPB=RealPaveBlock(aItLPB.Value());
1568           nSp=aPB->Edge();
1569           if (aMI.Contains(nSp)) {
1570             theLI.Append(nSp);
1571           }
1572         }
1573       }
1574     }
1575   }
1576 }
1577
1578 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1579 //
1580 // same domain shapes
1581 //
1582 //=======================================================================
1583 //function : ShapesSD
1584 //purpose  : 
1585 //=======================================================================
1586 BOPCol_DataMapOfIntegerInteger& BOPDS_DS::ShapesSD()
1587 {
1588   return myShapesSD;
1589 }
1590 //=======================================================================
1591 //function : AddShapeSD
1592 //purpose  : 
1593 //=======================================================================
1594 void BOPDS_DS::AddShapeSD(const Standard_Integer theIndex,
1595                           const Standard_Integer theIndexSD)
1596 {
1597   myShapesSD.Bind(theIndex, theIndexSD);
1598 }
1599 //=======================================================================
1600 //function : HasShapeSD
1601 //purpose  : 
1602 //=======================================================================
1603 Standard_Boolean BOPDS_DS::HasShapeSD
1604   (const Standard_Integer theIndex,
1605    Standard_Integer& theIndexSD)const
1606 {
1607   Standard_Boolean bRet;
1608   //
1609   bRet=myShapesSD.IsBound(theIndex);
1610   if (bRet) {
1611    theIndexSD=myShapesSD.Find(theIndex);
1612   }
1613   return bRet;
1614 }
1615 //=======================================================================
1616 //function : Dump
1617 //purpose  : 
1618 //=======================================================================
1619 void BOPDS_DS::Dump()const
1620 {
1621   Standard_Integer i, aNb, aNbSS;
1622   //
1623   printf(" *** DS ***\n");
1624   aNb=NbRanges();
1625   printf(" Ranges:%d\n", aNb);
1626   for (i=0; i<aNb; ++i) {
1627     const BOPDS_IndexRange& aR=Range(i);
1628     aR.Dump();
1629     printf("\n");
1630   }
1631   //
1632   aNbSS=NbSourceShapes();
1633   printf(" Shapes:%d\n", aNbSS);
1634   aNb=NbShapes();
1635   for (i=0; i<aNb; ++i) {
1636     const BOPDS_ShapeInfo& aSI=ShapeInfo(i);
1637     printf(" %d :", i);
1638     aSI.Dump();
1639     printf("\n");
1640     if (i==aNbSS-1) {
1641       printf(" ****** adds\n");
1642     }
1643   }
1644   printf(" ******\n");
1645 }
1646
1647 //=======================================================================
1648 // function: CheckCoincidence
1649 // purpose:
1650 //=======================================================================
1651 Standard_Boolean BOPDS_DS::CheckCoincidence
1652   (const Handle(BOPDS_PaveBlock)& aPB1,
1653    const Handle(BOPDS_PaveBlock)& aPB2,
1654    const Standard_Real theFuzz)
1655 {
1656   Standard_Boolean bRet;
1657   Standard_Integer nE1, nE2, aNbPoints;
1658   Standard_Real aT11, aT12, aT21, aT22, aT1m, aD, aTol, aT2x;
1659   gp_Pnt aP1m;
1660   //
1661   bRet=Standard_False;
1662   //
1663   aPB1->Range(aT11, aT12);
1664   aT1m=IntTools_Tools::IntermediatePoint (aT11, aT12);
1665   nE1=aPB1->OriginalEdge();
1666   const TopoDS_Edge& aE1=(*(TopoDS_Edge*)(&Shape(nE1)));
1667   BOPTools_AlgoTools::PointOnEdge(aE1, aT1m, aP1m);
1668   //
1669   aPB2->Range(aT21, aT22);
1670   nE2=aPB2->OriginalEdge();
1671   const TopoDS_Edge& aE2=(*(TopoDS_Edge*)(&Shape(nE2)));
1672   //
1673   Standard_Real f, l;
1674   Handle(Geom_Curve)aC2 = BRep_Tool::Curve (aE2, f, l);
1675   GeomAPI_ProjectPointOnCurve aPPC;
1676   aPPC.Init(aC2, f, l);
1677   aPPC.Perform(aP1m);
1678   aNbPoints=aPPC.NbPoints();
1679   if (aNbPoints) {
1680     aD=aPPC.LowerDistance();
1681     //
1682     aTol = BRep_Tool::MaxTolerance(aE1, TopAbs_VERTEX);
1683     aTol = aTol + BRep_Tool::MaxTolerance(aE2, TopAbs_VERTEX) + Max(theFuzz, Precision::Confusion());
1684     if (aD<aTol) {
1685       aT2x=aPPC.LowerDistanceParameter();
1686       if (aT2x>aT21 && aT2x<aT22) {
1687         return !bRet;
1688       }
1689     }
1690   }
1691   return bRet;
1692 }
1693 //=======================================================================
1694 // function: IsSubShape
1695 // purpose:
1696 //=======================================================================
1697 Standard_Boolean BOPDS_DS::IsSubShape
1698   (const Standard_Integer theI1,
1699    const Standard_Integer theI2)
1700 {
1701   Standard_Boolean bRet;
1702   Standard_Integer nS;
1703   bRet = Standard_False;
1704   //
1705   BOPCol_ListIteratorOfListOfInteger aItLI;
1706   //
1707   const BOPDS_ShapeInfo& aSI = ShapeInfo(theI2);
1708   const BOPCol_ListOfInteger& aLI = aSI.SubShapes();
1709   aItLI.Initialize(aLI);
1710   for(;aItLI.More(); aItLI.Next()) {
1711     nS = aItLI.Value();
1712     if (nS == theI1) {
1713       bRet = Standard_True;
1714       break;
1715     }
1716   }
1717
1718   return bRet;
1719 }
1720 //=======================================================================
1721 // function: Paves
1722 // purpose:
1723 //=======================================================================
1724 void BOPDS_DS::Paves(const Standard_Integer theEdge,
1725                      BOPDS_ListOfPave& theLP)
1726 {
1727   Standard_Integer aNb, i;
1728   BOPDS_ListIteratorOfListOfPaveBlock aIt;
1729   BOPDS_MapOfPave aMP;
1730   //
1731   const BOPDS_ListOfPaveBlock& aLPB = PaveBlocks(theEdge);
1732   aNb = aLPB.Extent() + 1;
1733   if (aNb == 1) {
1734     return;
1735   }
1736   //
1737   BOPDS_VectorOfPave pPaves(1, aNb);
1738   //
1739   i = 1;
1740   aIt.Initialize(aLPB);
1741   for (; aIt.More(); aIt.Next()) {
1742     const Handle(BOPDS_PaveBlock)& aPB = aIt.Value();
1743     const BOPDS_Pave& aPave1 = aPB->Pave1();
1744     const BOPDS_Pave& aPave2 = aPB->Pave2();
1745     //
1746     if (aMP.Add(aPave1)){
1747       pPaves(i) = aPave1;
1748       ++i;
1749     }
1750     //
1751     if (aMP.Add(aPave2)){
1752       pPaves(i) = aPave2;
1753       ++i;
1754     }
1755   }
1756   //
1757   Standard_ASSERT_VOID(aNb == aMP.Extent(), "Abnormal number of paves");
1758   //
1759   std::sort(pPaves.begin(), pPaves.end());
1760   //
1761   for (i = 1; i <= aNb; ++i) {
1762     theLP.Append(pPaves(i));
1763   }
1764 }
1765 //=======================================================================
1766 // function: UpdateTolerance
1767 // purpose:
1768 //=======================================================================
1769 void BOPDS_DS::UpdateEdgeTolerance(const Standard_Integer nE,
1770                                    const Standard_Real aTol,
1771                                    const Standard_Real theFuzz)
1772 {
1773   Standard_Integer nV;
1774   Standard_Real aTolV;
1775   BRep_Builder aBB;
1776   BOPCol_ListIteratorOfListOfInteger aIt;
1777   //
1778   Standard_Real aTolAdd = Max(theFuzz, Precision::Confusion()) * 0.5;
1779
1780   const TopoDS_Edge& aE = *(TopoDS_Edge*)&Shape(nE);
1781   aBB.UpdateEdge(aE, aTol);
1782   BOPDS_ShapeInfo& aSIE=ChangeShapeInfo(nE);
1783   Bnd_Box& aBoxE=aSIE.ChangeBox();
1784   BRepBndLib::Add(aE, aBoxE);
1785   aBoxE.SetGap(aBoxE.GetGap() + aTolAdd);
1786   //
1787   const BOPCol_ListOfInteger& aLI = aSIE.SubShapes();
1788   aIt.Initialize(aLI);
1789   for (; aIt.More(); aIt.Next()) {
1790     nV = aIt.Value();
1791     const TopoDS_Vertex& aV = *(TopoDS_Vertex*)&Shape(nV);
1792     aTolV = BRep_Tool::Tolerance(aV);
1793     if (aTolV < aTol) {
1794       aBB.UpdateVertex(aV, aTol);
1795       BOPDS_ShapeInfo& aSIV = ChangeShapeInfo(nV);
1796       Bnd_Box& aBoxV = aSIV.ChangeBox();
1797       BRepBndLib::Add(aV, aBoxV);
1798       aBoxV.SetGap(aBoxV.GetGap() + aTolAdd);
1799     }
1800   }
1801 }
1802 //=======================================================================
1803 //function : TotalShapes
1804 //purpose  : 
1805 //=======================================================================
1806 void TotalShapes(const TopoDS_Shape& aS, 
1807                  Standard_Integer& aNbS,
1808                  BOPCol_MapOfShape& aMS)
1809 {
1810   if (aMS.Add(aS)) {
1811     TopoDS_Iterator aIt;
1812     ++aNbS;
1813     aIt.Initialize(aS);
1814     for (; aIt.More(); aIt.Next()) {
1815       const TopoDS_Shape& aSx=aIt.Value();
1816       TotalShapes(aSx, aNbS, aMS);
1817     }
1818   }
1819 }
1820
1821 //=======================================================================
1822 //function : ComputeParameter
1823 //purpose  : 
1824 //=======================================================================
1825 Standard_Real ComputeParameter(const TopoDS_Vertex& aV,
1826                                const TopoDS_Edge& aE)
1827 {
1828   Standard_Real aT1, aT2, aTRet, aTolE2, aD2;
1829   gp_Pnt aPC, aPV;
1830   Handle(Geom_Curve) aC3D;
1831   TopoDS_Edge aEE;
1832   //
1833   aEE=aE;
1834   aEE.Orientation(TopAbs_FORWARD);
1835   //
1836   aTRet=0.;
1837   //
1838   aTolE2=BRep_Tool::Tolerance(aE);
1839   aTolE2=aTolE2*aTolE2;
1840   //
1841   aPV=BRep_Tool::Pnt(aV);
1842   //
1843   aC3D=BRep_Tool::Curve (aEE, aT1, aT2);
1844   //
1845   aC3D->D0(aT1, aPC);
1846   aD2=aPC.SquareDistance(aPV);
1847   if (aD2<aTolE2) {
1848     aTRet=aT1;
1849   }
1850   //
1851   aC3D->D0(aT2, aPC);
1852   aD2=aPC.SquareDistance(aPV);
1853   if (aD2<aTolE2) {
1854     aTRet=aT2;
1855   }
1856   //
1857   return aTRet;
1858 }
1859 //=======================================================================
1860 //function : BuildBndBoxSolid
1861 //purpose  : 
1862 //=======================================================================
1863 void BOPDS_DS::BuildBndBoxSolid(const Standard_Integer theIndex,
1864                                 Bnd_Box& aBoxS)
1865 {
1866   Standard_Boolean bIsOpenBox, bIsInverted;
1867   Standard_Integer nSh, nFc;
1868   Standard_Real aTolS, aTolFc;
1869   BOPCol_ListIteratorOfListOfInteger aItLI, aItLI1;
1870   //
1871   const BOPDS_ShapeInfo& aSI=ShapeInfo(theIndex);
1872   const TopoDS_Shape& aS=aSI.Shape();
1873   const TopoDS_Solid& aSolid=(*(TopoDS_Solid*)(&aS));
1874   //
1875   bIsOpenBox=Standard_False;
1876   //
1877   aTolS=0.;
1878   const BOPCol_ListOfInteger& aLISh=aSI.SubShapes();
1879   aItLI.Initialize(aLISh);
1880   for (; aItLI.More(); aItLI.Next()) {
1881     nSh=aItLI.Value();
1882     const BOPDS_ShapeInfo& aSISh=ShapeInfo(nSh);
1883     if (aSISh.ShapeType()!=TopAbs_SHELL) {
1884       continue;
1885     }
1886     //
1887     const BOPCol_ListOfInteger& aLIFc=aSISh.SubShapes();
1888     aItLI1.Initialize(aLIFc);
1889     for (; aItLI1.More(); aItLI1.Next()) {
1890       nFc=aItLI1.Value();
1891       const BOPDS_ShapeInfo& aSIFc=ShapeInfo(nFc);
1892       if (aSIFc.ShapeType()!=TopAbs_FACE) {
1893         continue;
1894       }
1895       //
1896       const Bnd_Box& aBFc=aSIFc.Box();
1897       aBoxS.Add(aBFc);
1898       //
1899       if (!bIsOpenBox) {
1900         bIsOpenBox=(aBFc.IsOpenXmin() || aBFc.IsOpenXmax() ||
1901                     aBFc.IsOpenYmin() || aBFc.IsOpenYmax() ||
1902                     aBFc.IsOpenZmin() || aBFc.IsOpenZmax()); 
1903         if (bIsOpenBox) {
1904           break;
1905         }
1906       }
1907       //
1908       const TopoDS_Face& aFc=*((TopoDS_Face*)&aSIFc.Shape());
1909       aTolFc=BRep_Tool::Tolerance(aFc);
1910       if (aTolFc>aTolS) {
1911         aTolS=aTolFc;
1912       }
1913     }//for (; aItLI1.More(); aItLI1.Next()) {
1914     if (bIsOpenBox) {
1915       break;
1916     }
1917     //
1918     const TopoDS_Shell& aSh=*((TopoDS_Shell*)&aSISh.Shape());
1919     bIsOpenBox=BOPTools_AlgoTools::IsOpenShell(aSh);
1920     if (bIsOpenBox) {
1921       break;
1922     }
1923   }//for (; aItLI.More(); aItLI.Next()) {
1924   //
1925   if (bIsOpenBox) {
1926     aBoxS.SetWhole();
1927   }
1928   else {
1929     bIsInverted=BOPTools_AlgoTools::IsInvertedSolid(aSolid);
1930     if (bIsInverted) {
1931       aBoxS.SetWhole(); 
1932     }
1933   }
1934 }
1935
1936 //=======================================================================
1937 //function : UpdatePaveBlocksWithSDVertices
1938 //purpose  : 
1939 //=======================================================================
1940 void BOPDS_DS::UpdatePaveBlocksWithSDVertices()
1941 {
1942   Standard_Integer i, aNbPBP;
1943   BOPDS_ListIteratorOfListOfPaveBlock aItPB;
1944   //
1945   BOPDS_VectorOfListOfPaveBlock& aPBP=myPaveBlocksPool;
1946   //
1947   aNbPBP=aPBP.Size();
1948   for (i = 0; i < aNbPBP; ++i) {
1949     BOPDS_ListOfPaveBlock& aLPB = aPBP(i); 
1950     //
1951     aItPB.Initialize(aLPB);
1952     for (; aItPB.More(); aItPB.Next()) {
1953       Handle(BOPDS_PaveBlock)& aPB = aItPB.ChangeValue();
1954       UpdatePaveBlockWithSDVertices(aPB);
1955     }// for (; aItPB.More(); aItPB.Next()) {
1956   }// for (i = 0; i < aNbPBP; ++i) {
1957 }
1958 //=======================================================================
1959 //function : UpdatePaveBlockWithSDVertices
1960 //purpose  : 
1961 //=======================================================================
1962 void BOPDS_DS::UpdatePaveBlockWithSDVertices
1963   (const Handle(BOPDS_PaveBlock)& thePB)
1964 {
1965   Standard_Integer nV1, nV2;
1966   BOPDS_Pave aPave1, aPave2;
1967   //
1968   aPave1 = thePB->Pave1();
1969   aPave2 = thePB->Pave2();
1970   //
1971   nV1 = aPave1.Index();
1972   nV2 = aPave2.Index();
1973   //
1974   if (HasShapeSD(nV1, nV1)) {
1975     aPave1.SetIndex(nV1);
1976     thePB->SetPave1(aPave1);
1977   }
1978   //
1979   if (HasShapeSD(nV2, nV2)) {
1980     aPave2.SetIndex(nV2);
1981     thePB->SetPave2(aPave2);
1982   }
1983 }
1984 //=======================================================================
1985 //function : UpdateCommonBlockWithSDVertices
1986 //purpose  : 
1987 //=======================================================================
1988 void BOPDS_DS::UpdateCommonBlockWithSDVertices
1989   (const Handle(BOPDS_CommonBlock)& theCB)
1990 {
1991   const BOPDS_ListOfPaveBlock& aLPB = theCB->PaveBlocks();
1992   BOPDS_ListIteratorOfListOfPaveBlock aItPB(aLPB);
1993   for (; aItPB.More(); aItPB.Next()) {
1994     const Handle(BOPDS_PaveBlock)& aPB = aItPB.Value();
1995     UpdatePaveBlockWithSDVertices(aPB);
1996   }
1997 }
1998 //=======================================================================
1999 //function : InitPaveBlocksForVertex
2000 //purpose  : 
2001 //=======================================================================
2002 void BOPDS_DS::InitPaveBlocksForVertex(const Standard_Integer theNV)
2003 {
2004   Standard_Integer nE;
2005   BOPCol_ListIteratorOfListOfInteger aItLE;
2006   //
2007   if (myMapVE.IsBound(theNV)) {
2008     const BOPCol_ListOfInteger& aLE=myMapVE.Find(theNV);
2009     aItLE.Initialize(aLE);
2010     for (; aItLE.More(); aItLE.Next()) {
2011       nE=aItLE.Value();
2012       ChangePaveBlocks(nE);
2013     }
2014   }
2015 }
2016
2017 //=======================================================================
2018 //function : ReleasePaveBlocks
2019 //purpose  :
2020 //=======================================================================
2021 void BOPDS_DS::ReleasePaveBlocks()
2022 {
2023   // It is necessary to remove the reference to PaveBlocks for the untouched
2024   // edges to avoid creation of the same images for them.
2025   // Pave blocks for this reference should be cleared.
2026   // This will allow to differ the small edges, for which it is
2027   // impossible to even build a pave block from the normal edges for which the
2028   // pave block have been created, but stayed untouched.
2029   // The small edge, for which no pave blocks have been created,
2030   // should be avoided in the result, thus the reference to empty list
2031   // of pave blocks will stay to mark the edge as Deleted.
2032
2033   BOPDS_VectorOfListOfPaveBlock& aPBP = ChangePaveBlocksPool();
2034   Standard_Integer aNbPBP = aPBP.Extent();
2035   if (!aNbPBP) {
2036     return;
2037   }
2038   //
2039   for (Standard_Integer i = 0; i < aNbPBP; ++i) {
2040     BOPDS_ListOfPaveBlock& aLPB = aPBP(i);
2041     if (aLPB.Extent() == 1) {
2042       const Handle(BOPDS_PaveBlock)& aPB = aLPB.First();
2043       if (!IsCommonBlock(aPB)) {
2044         Standard_Integer nV1, nV2;
2045         aPB->Indices(nV1, nV2);
2046         if (!IsNewShape(nV1) && !IsNewShape(nV2)) {
2047           // Both vertices are original, thus the PB is untouched.
2048           // Remove reference for the original edge
2049           Standard_Integer nE = aPB->OriginalEdge();
2050           if (nE >= 0) {
2051             ChangeShapeInfo(nE).SetReference(-1);
2052           }
2053           // Clear contents of the list
2054           aLPB.Clear();
2055         }
2056       }
2057     }
2058   }
2059 }