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