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