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