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