0028259: Method MakeBlocksCnx is duplicated in two different places in BOPAlgo
[occt.git] / src / BOPAlgo / BOPAlgo_PaveFiller_3.cxx
1 // Created by: Peter KURNEV
2 // Copyright (c) 2010-2014 OPEN CASCADE SAS
3 // Copyright (c) 2007-2010 CEA/DEN, EDF R&D, OPEN CASCADE
4 // Copyright (c) 2003-2007 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN, CEDRAT,
5 //                         EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
6 //
7 // This file is part of Open CASCADE Technology software library.
8 //
9 // This library is free software; you can redistribute it and/or modify it under
10 // the terms of the GNU Lesser General Public License version 2.1 as published
11 // by the Free Software Foundation, with special exception defined in the file
12 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
13 // distribution for complete text of the license and disclaimer of any warranty.
14 //
15 // Alternatively, this file may be used under the terms of Open CASCADE
16 // commercial license or contractual agreement.
17
18
19 #include <Bnd_Box.hxx>
20 #include <BOPAlgo_PaveFiller.hxx>
21 #include <BOPAlgo_SectionAttribute.hxx>
22 #include <BOPAlgo_Tools.hxx>
23 #include <BOPCol_BoxBndTree.hxx>
24 #include <BOPCol_DataMapOfIntegerShape.hxx>
25 #include <BOPCol_DataMapOfShapeInteger.hxx>
26 #include <BOPCol_DataMapOfShapeListOfShape.hxx>
27 #include <BOPCol_IndexedDataMapOfShapeBox.hxx>
28 #include <BOPCol_NCVector.hxx>
29 #include <BOPCol_Parallel.hxx>
30 #include <BOPDS_CommonBlock.hxx>
31 #include <BOPDS_CoupleOfPaveBlocks.hxx>
32 #include <BOPDS_Curve.hxx>
33 #include <BOPDS_DataMapOfPaveBlockListOfInteger.hxx>
34 #include <BOPDS_DataMapOfPaveBlockListOfPaveBlock.hxx>
35 #include <BOPDS_DS.hxx>
36 #include <BOPDS_Interf.hxx>
37 #include <BOPDS_Iterator.hxx>
38 #include <BOPDS_MapOfPaveBlock.hxx>
39 #include <BOPDS_Pave.hxx>
40 #include <BOPDS_PaveBlock.hxx>
41 #include <BOPDS_VectorOfInterfEE.hxx>
42 #include <BOPTools_AlgoTools.hxx>
43 #include <BndLib_Add3dCurve.hxx>
44 #include <BRep_Tool.hxx>
45 #include <BRepBndLib.hxx>
46 #include <BRepTools.hxx>
47 #include <BRepAdaptor_Curve.hxx>
48 #include <gp_Pnt.hxx>
49 #include <IntTools_CommonPrt.hxx>
50 #include <IntTools_Context.hxx>
51 #include <IntTools_EdgeEdge.hxx>
52 #include <IntTools_Range.hxx>
53 #include <IntTools_SequenceOfCommonPrts.hxx>
54 #include <IntTools_SequenceOfRanges.hxx>
55 #include <IntTools_ShrunkRange.hxx>
56 #include <IntTools_Tools.hxx>
57 #include <NCollection_UBTreeFiller.hxx>
58 #include <Precision.hxx>
59 #include <TopoDS_Compound.hxx>
60 #include <TopoDS_Edge.hxx>
61 #include <TopoDS_Face.hxx>
62 #include <TopoDS_Vertex.hxx>
63
64 /////////////////////////////////////////////////////////////////////////
65 //=======================================================================
66 //class    : BOPAlgo_EdgeEdge
67 //purpose  : 
68 //=======================================================================
69 class BOPAlgo_EdgeEdge : 
70   public IntTools_EdgeEdge,
71   public BOPAlgo_Algo {
72  
73  public:
74
75   DEFINE_STANDARD_ALLOC
76   //
77   BOPAlgo_EdgeEdge(): 
78     IntTools_EdgeEdge(),
79     BOPAlgo_Algo() {
80   };
81   //
82   virtual ~BOPAlgo_EdgeEdge(){
83   };
84   //
85   void SetPaveBlock1(const Handle(BOPDS_PaveBlock)& aPB) {
86     myPB1=aPB;
87   }
88   //
89   Handle(BOPDS_PaveBlock)& PaveBlock1() {
90     return myPB1;
91   }
92   //
93   void SetPaveBlock2(const Handle(BOPDS_PaveBlock)& aPB) {
94     myPB2=aPB;
95   }
96   //
97   Handle(BOPDS_PaveBlock)& PaveBlock2() {
98     return myPB2;
99   }
100   // 
101   void SetFuzzyValue(const Standard_Real theFuzz) {
102     IntTools_EdgeEdge::SetFuzzyValue(theFuzz);
103   }
104   //
105   virtual void Perform() {
106     BOPAlgo_Algo::UserBreak();
107     IntTools_EdgeEdge::Perform();
108   }
109   //
110  protected:
111   Handle(BOPDS_PaveBlock) myPB1;
112   Handle(BOPDS_PaveBlock) myPB2;
113 };
114 //
115 //=======================================================================
116 typedef BOPCol_NCVector
117   <BOPAlgo_EdgeEdge> BOPAlgo_VectorOfEdgeEdge; 
118 //
119 typedef BOPCol_Functor 
120   <BOPAlgo_EdgeEdge,
121   BOPAlgo_VectorOfEdgeEdge> BOPAlgo_EdgeEdgeFunctor;
122 //
123 typedef BOPCol_Cnt 
124   <BOPAlgo_EdgeEdgeFunctor,
125   BOPAlgo_VectorOfEdgeEdge> BOPAlgo_EdgeEdgeCnt;
126 //
127 /////////////////////////////////////////////////////////////////////////
128 //=======================================================================
129 //class    : BOPAlgo_TNV
130 //purpose  : 
131 //=======================================================================
132 class BOPAlgo_TNV;
133 typedef BOPCol_NCVector
134   <BOPAlgo_TNV> BOPAlgo_VectorOfTNV;
135 //
136 typedef BOPCol_Functor
137   <BOPAlgo_TNV,
138   BOPAlgo_VectorOfTNV> BOPAlgo_TNVFunctor;
139 //
140 typedef BOPCol_Cnt
141   <BOPAlgo_TNVFunctor,
142   BOPAlgo_VectorOfTNV> BOPAlgo_TNVCnt;
143 //=======================================================================
144 class BOPAlgo_TNV : public BOPCol_BoxBndTreeSelector{
145  public:
146   BOPAlgo_TNV() 
147     : BOPCol_BoxBndTreeSelector(),
148       myTol (0.), myFuzzyValue(0.), myTree(NULL), myVecTNV(NULL) {
149   };
150   //
151   ~BOPAlgo_TNV(){
152   };
153   //
154   void SetVertex(const TopoDS_Vertex& aV) {
155     myV=aV;
156     myPnt = BRep_Tool::Pnt(myV);
157   }
158   //
159   const TopoDS_Vertex& Vertex()const {
160     return myV;
161   }
162   //
163   void SetTree(BOPCol_BoxBndTree& aTree) {
164     myTree=&aTree;
165   }
166   //
167   void SetTolerance(const Standard_Real theTol) {
168     myTol = theTol;
169   }
170   //
171   Standard_Real Tolerance() const {
172     return myTol;
173   }
174   //
175   const gp_Pnt& Pnt() const {
176     return myPnt;
177   }
178   //
179   void SetFuzzyValue(const Standard_Real theFuzzyValue) {
180     myFuzzyValue = theFuzzyValue;
181   }
182   //
183   void SetVectorOfTNV(const BOPAlgo_VectorOfTNV& theVec) {
184     myVecTNV = &theVec;
185   }
186   //
187   virtual Standard_Boolean Accept(const Standard_Integer& theIndex)
188   {
189     const BOPAlgo_TNV& aTNV = myVecTNV->Value(theIndex - 1);
190     Standard_Real aTolSum2 = myTol + aTNV.Tolerance() + myFuzzyValue;
191     aTolSum2 *= aTolSum2;
192     Standard_Real aD2 = myPnt.SquareDistance(aTNV.Pnt());
193     if (aD2 < aTolSum2)
194       return BOPCol_BoxBndTreeSelector::Accept(theIndex);
195     return Standard_False;
196   }
197   //
198   void Perform() {
199     myTree->Select(*this);
200   }
201   //
202  protected:
203   Standard_Real myTol;
204   Standard_Real myFuzzyValue;
205   gp_Pnt        myPnt;
206   TopoDS_Vertex myV;
207   BOPCol_BoxBndTree *myTree;
208   const BOPAlgo_VectorOfTNV *myVecTNV;
209 };
210 //
211 /////////////////////////////////////////////////////////////////////////
212 //=======================================================================
213 //class    : BOPAlgo_PVE
214 //purpose  : 
215 //=======================================================================
216 class BOPAlgo_PVE {
217  public:
218   BOPAlgo_PVE()
219     : myIV(-1), myIE(-1), myFlag(-1), myT(-1.) {
220   };
221   //
222   ~BOPAlgo_PVE(){
223   };
224   //
225   void SetIndices(const Standard_Integer nV,
226                   const Standard_Integer nE){
227     myIV=nV;
228     myIE=nE;
229   }
230   //
231   void Indices(Standard_Integer& nV,
232                Standard_Integer& nE) const {
233     nV=myIV;
234     nE=myIE;
235   }
236   //
237   void SetVertex(const TopoDS_Vertex& aV) {
238     myV=aV;
239   }
240   //
241   const TopoDS_Vertex& Vertex()const {
242     return myV;
243   }
244   //
245   void SetEdge(const TopoDS_Edge& aE) {
246     myE=aE;
247   }
248   //
249   const TopoDS_Edge& Edge()const {
250     return myE;
251   }
252   //
253   void SetPaveBlock(const Handle(BOPDS_PaveBlock)& aPB) {
254     myPB=aPB;
255   }
256   //
257   Handle(BOPDS_PaveBlock)& PaveBlock() {
258     return myPB;
259   }
260   //
261   Standard_Integer Flag()const {
262     return myFlag;
263   }
264   //
265   Standard_Real Parameter()const {
266     return myT;
267   }
268   //
269   void SetContext(const Handle(IntTools_Context)& aContext) {
270     myContext=aContext;
271   }
272   //
273   const Handle(IntTools_Context)& Context()const {
274     return myContext;
275   }
276   //
277   void SetFuzzyValue(const Standard_Real theValue) {
278     myFuzzyValue = theValue;
279   }
280   //
281   void Perform() {
282     Standard_Real dummy;
283     myFlag = myContext->ComputeVE(myV, myE, myT, dummy, myFuzzyValue);
284   };
285   //
286  protected:
287   Standard_Integer myIV;
288   Standard_Integer myIE;
289   Standard_Integer myFlag;
290   Standard_Real myT;
291   Standard_Real myFuzzyValue;
292   TopoDS_Vertex myV;
293   TopoDS_Edge myE;
294   Handle(BOPDS_PaveBlock) myPB;
295   Handle(IntTools_Context) myContext;
296 };
297 //=======================================================================
298 typedef BOPCol_NCVector
299   <BOPAlgo_PVE> BOPAlgo_VectorOfPVE; 
300 //
301 typedef BOPCol_ContextFunctor 
302   <BOPAlgo_PVE,
303   BOPAlgo_VectorOfPVE,
304   Handle(IntTools_Context), 
305   IntTools_Context> BOPAlgo_PVEFunctor;
306 //
307 typedef BOPCol_ContextCnt 
308   <BOPAlgo_PVEFunctor,
309   BOPAlgo_VectorOfPVE,
310   Handle(IntTools_Context)> BOPAlgo_PVECnt;
311 /////////////////////////////////////////////////////////////////////////
312 //=======================================================================
313 // function: PerformEE
314 // purpose: 
315 //=======================================================================
316 void BOPAlgo_PaveFiller::PerformEE()
317 {
318   Standard_Integer iSize;
319   //
320   myErrorStatus=0;
321   //
322   FillShrunkData(TopAbs_EDGE, TopAbs_EDGE);
323   //
324   myIterator->Initialize(TopAbs_EDGE, TopAbs_EDGE);
325   iSize=myIterator->ExpectedLength();
326   if (!iSize) {
327     return; 
328   }
329   //
330   Standard_Boolean bExpressCompute, bIsPBSplittable1, bIsPBSplittable2;
331   Standard_Integer i, iX, nE1, nE2, aNbCPrts, k, aNbEdgeEdge;
332   Standard_Integer nV11, nV12, nV21, nV22;
333   Standard_Real aTS11, aTS12, aTS21, aTS22, aT11, aT12, aT21, aT22;
334   TopAbs_ShapeEnum aType;
335   BOPDS_ListIteratorOfListOfPaveBlock aIt1, aIt2;
336   Handle(NCollection_BaseAllocator) aAllocator;
337   BOPDS_MapOfPaveBlock aMPBToUpdate;
338   BOPAlgo_VectorOfEdgeEdge aVEdgeEdge;
339   BOPDS_MapIteratorOfMapOfPaveBlock aItPB; 
340   //
341   aAllocator=NCollection_BaseAllocator::CommonBaseAllocator();
342   //-----------------------------------------------------scope f
343   BOPDS_IndexedDataMapOfPaveBlockListOfPaveBlock aMPBLPB(100, aAllocator);
344   BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks aMVCPB(100, aAllocator);
345   BOPAlgo_DataMapOfPaveBlockBndBox aDMPBBox(100, aAllocator);
346   //
347   BOPDS_VectorOfInterfEE& aEEs=myDS->InterfEE();
348   aEEs.SetIncrement(iSize);
349   //
350   for (; myIterator->More(); myIterator->Next()) {
351     myIterator->Value(nE1, nE2);
352     //
353     const BOPDS_ShapeInfo& aSIE1=myDS->ShapeInfo(nE1);
354     if (aSIE1.HasFlag()){
355       continue;
356     }
357     const BOPDS_ShapeInfo& aSIE2=myDS->ShapeInfo(nE2);
358     if (aSIE2.HasFlag()){
359       continue;
360     }
361     //
362     BOPDS_ListOfPaveBlock& aLPB1 = myDS->ChangePaveBlocks(nE1);
363     if (aLPB1.IsEmpty()) {
364       continue;
365     }
366     //
367     BOPDS_ListOfPaveBlock& aLPB2 = myDS->ChangePaveBlocks(nE2);
368     if (aLPB2.IsEmpty()) {
369       continue;
370     }
371     //
372     const TopoDS_Edge& aE1=(*(TopoDS_Edge *)(&aSIE1.Shape()));
373     const TopoDS_Edge& aE2=(*(TopoDS_Edge *)(&aSIE2.Shape()));
374     //
375     aIt1.Initialize(aLPB1);
376     for (; aIt1.More(); aIt1.Next()) {
377       Bnd_Box aBB1;
378       //
379       Handle(BOPDS_PaveBlock)& aPB1=aIt1.ChangeValue();
380       //
381       if (!GetPBBox(aE1, aPB1, aDMPBBox, aT11, aT12, aTS11, aTS12, aBB1)) {
382         continue;
383       }
384       //
385       aPB1->Indices(nV11, nV12);
386       //
387       aIt2.Initialize(aLPB2);
388       for (; aIt2.More(); aIt2.Next()) {
389         Bnd_Box aBB2;
390         //
391         Handle(BOPDS_PaveBlock)& aPB2=aIt2.ChangeValue();
392         //
393         if (!GetPBBox(aE2, aPB2, aDMPBBox, aT21, aT22, aTS21, aTS22, aBB2)) {
394           continue;
395         }
396         //
397         if (aBB1.IsOut(aBB2)) {
398           continue;
399         }
400         //
401         aPB2->Indices(nV21, nV22);
402         //
403         bExpressCompute=((nV11==nV21 && nV12==nV22) ||
404                          (nV12==nV21 && nV11==nV22));
405         //
406         BOPAlgo_EdgeEdge& anEdgeEdge=aVEdgeEdge.Append1();
407         //
408         anEdgeEdge.UseQuickCoincidenceCheck(bExpressCompute);
409         //
410         anEdgeEdge.SetPaveBlock1(aPB1);
411         anEdgeEdge.SetPaveBlock2(aPB2);
412         //
413         anEdgeEdge.SetEdge1(aE1, aT11, aT12);
414         anEdgeEdge.SetEdge2(aE2, aT21, aT22);
415         anEdgeEdge.SetFuzzyValue(myFuzzyValue);
416         anEdgeEdge.SetProgressIndicator(myProgressIndicator);
417       }//for (; aIt2.More(); aIt2.Next()) {
418     }//for (; aIt1.More(); aIt1.Next()) {
419   }//for (; myIterator->More(); myIterator->Next()) {
420   //
421   aNbEdgeEdge=aVEdgeEdge.Extent();
422   //======================================================
423   BOPAlgo_EdgeEdgeCnt::Perform(myRunParallel, aVEdgeEdge);
424   //======================================================
425   //
426   for (k = 0; k < aNbEdgeEdge; ++k) {
427     Bnd_Box aBB1, aBB2;
428     //
429     BOPAlgo_EdgeEdge& anEdgeEdge=aVEdgeEdge(k);
430     if (!anEdgeEdge.IsDone()) {
431       continue;
432     }
433     //
434     const IntTools_SequenceOfCommonPrts& aCPrts = anEdgeEdge.CommonParts();
435     aNbCPrts = aCPrts.Length();
436     if (!aNbCPrts) {
437       continue;
438     }
439     //--------------------------------------------
440     Handle(BOPDS_PaveBlock)& aPB1=anEdgeEdge.PaveBlock1();
441     nE1=aPB1->OriginalEdge();
442     aPB1->Range(aT11, aT12);
443     if (!aPB1->HasShrunkData()) {
444       aTS11 = aT11;
445       aTS12 = aT12;
446       bIsPBSplittable1 = Standard_False;
447     }
448     else {
449       aPB1->ShrunkData(aTS11, aTS12, aBB1, bIsPBSplittable1);
450     }
451     //
452     Handle(BOPDS_PaveBlock)& aPB2=anEdgeEdge.PaveBlock2();
453     nE2=aPB2->OriginalEdge();
454     aPB2->Range(aT21, aT22);
455     if (!aPB2->HasShrunkData()) {
456       aTS21 = aT21;
457       aTS22 = aT22;
458       bIsPBSplittable2 = Standard_False;
459     }
460     else {
461       aPB2->ShrunkData(aTS21, aTS22, aBB2, bIsPBSplittable2);
462     }
463     //
464     //--------------------------------------------
465     IntTools_Range aR11(aT11, aTS11), aR12(aTS12, aT12),
466                    aR21(aT21, aTS21), aR22(aTS22, aT22);
467     //
468     Standard_Boolean bAnalytical = Standard_False;
469     {
470       const TopoDS_Edge& aOE1 = *(TopoDS_Edge*)&myDS->Shape(nE1);
471       const TopoDS_Edge& aOE2 = *(TopoDS_Edge*)&myDS->Shape(nE2);
472       //
473       BRepAdaptor_Curve aBAC1(aOE1), aBAC2(aOE2);
474       //
475       GeomAbs_CurveType aType1 = aBAC1.GetType();
476       GeomAbs_CurveType aType2 = aBAC2.GetType();
477       //
478       bAnalytical = (((aType1 == GeomAbs_Line) &&
479                       (aType2 == GeomAbs_Line ||
480                        aType2 == GeomAbs_Circle)) ||
481                      ((aType2 == GeomAbs_Line) &&
482                       (aType1 == GeomAbs_Line ||
483                        aType1 == GeomAbs_Circle)));
484     }
485     //
486     for (i=1; i<=aNbCPrts; ++i) {
487       const IntTools_CommonPrt& aCPart=aCPrts(i);
488       //
489       const TopoDS_Edge& aE1=aCPart.Edge1();
490       const TopoDS_Edge& aE2=aCPart.Edge2();
491       //
492       aType=aCPart.Type();
493       switch (aType) {
494         case TopAbs_VERTEX:  { 
495           if (!bIsPBSplittable1 || !bIsPBSplittable2) {
496             continue;
497           }
498           //
499           Standard_Boolean bIsOnPave[4], bFlag;
500           Standard_Integer nV[4], j;
501           Standard_Real aT1, aT2, aTol;
502           TopoDS_Vertex aVnew;
503           IntTools_Range aCR1, aCR2;
504           //
505           IntTools_Tools::VertexParameters(aCPart, aT1, aT2);
506           aTol = Precision::Confusion();
507           aCR1 = aCPart.Range1();
508           aCR2 = aCPart.Ranges2()(1);
509           // 
510           //decide to keep the pave or not
511           bIsOnPave[0] = IntTools_Tools::IsOnPave1(aT1, aR11, aTol) ||
512             IntTools_Tools::IsOnPave1(aR11.First(), aCR1, aTol);
513           bIsOnPave[1] = IntTools_Tools::IsOnPave1(aT1, aR12, aTol) || 
514             IntTools_Tools::IsOnPave1(aR12.Last(), aCR1, aTol);
515           bIsOnPave[2] = IntTools_Tools::IsOnPave1(aT2, aR21, aTol) ||
516             IntTools_Tools::IsOnPave1(aR21.First(), aCR2, aTol);
517           bIsOnPave[3] = IntTools_Tools::IsOnPave1(aT2, aR22, aTol) ||
518             IntTools_Tools::IsOnPave1(aR22.Last(), aCR2, aTol);
519           //
520           aPB1->Indices(nV[0], nV[1]);
521           aPB2->Indices(nV[2], nV[3]);
522           //
523           if((bIsOnPave[0] && bIsOnPave[2]) || 
524              (bIsOnPave[0] && bIsOnPave[3]) ||
525              (bIsOnPave[1] && bIsOnPave[2]) || 
526              (bIsOnPave[1] && bIsOnPave[3])) {
527             continue;
528           }
529           //
530           bFlag = Standard_False;
531           for (j = 0; j < 4; ++j) {
532             if (bIsOnPave[j]) {
533               //add interf VE(nV[j], nE)
534               Handle(BOPDS_PaveBlock)& aPB = (j < 2) ? aPB2 : aPB1;
535               ForceInterfVE(nV[j], aPB, aMPBToUpdate);
536               bFlag = Standard_True;
537               break;
538             }
539           }
540           if (bFlag) {
541             BOPDS_InterfEE& aEE = aEEs.Append1();
542             aEE.SetIndices(nE1, nE2);
543             aEE.SetCommonPart(aCPart);
544             continue;
545           }
546           //
547           BOPTools_AlgoTools::MakeNewVertex(aE1, aT1, aE2, aT2, aVnew);
548           Standard_Real aTolVnew = BRep_Tool::Tolerance(aVnew);
549           if (bAnalytical) {
550             // increase tolerance for Line/Line intersection, but do not update 
551             // the vertex till its intersection with some other shape
552             Standard_Real aTolMin = (BRepAdaptor_Curve(aE1).GetType() == GeomAbs_Line) ?
553               (aCR1.Last() - aCR1.First()) / 2. : (aCR2.Last() - aCR2.First()) / 2.;
554             if (aTolMin > aTolVnew) {
555               aTolVnew = aTolMin;
556             }
557           }
558           // <-LXBR
559           {
560             Standard_Integer nVS[2], iFound;
561             Standard_Real aTolVx, aD2, aDT2;
562             BOPCol_MapOfInteger aMV;
563             gp_Pnt aPnew, aPx;
564             //
565             iFound=0;
566             j=-1;
567             aMV.Add(nV[0]);
568             aMV.Add(nV[1]);
569             //
570             if (aMV.Contains(nV[2])) {
571               ++j;
572               nVS[j]=nV[2];
573             }
574             if (aMV.Contains(nV[3])) {
575               ++j;
576               nVS[j]=nV[3];
577             }
578             //
579             aPnew=BRep_Tool::Pnt(aVnew);
580             //
581             for (Standard_Integer k1=0; k1<=j; ++k1) {
582               const TopoDS_Vertex& aVx= *(TopoDS_Vertex*)&(myDS->Shape(nVS[k1]));
583               aTolVx=BRep_Tool::Tolerance(aVx);
584               aPx=BRep_Tool::Pnt(aVx);
585               aD2=aPnew.SquareDistance(aPx);
586               //
587               aDT2=100.*(aTolVnew+aTolVx)*(aTolVnew+aTolVx);
588               //
589               if (aD2<aDT2) {
590                 iFound=1;
591                 break;
592               }
593             }
594             //
595             if (iFound) {
596               continue;
597             }
598           }
599           //
600           // 1
601           BOPDS_InterfEE& aEE=aEEs.Append1();
602           iX=aEEs.Extent()-1;
603           aEE.SetIndices(nE1, nE2);
604           aEE.SetCommonPart(aCPart);
605           // 2
606           myDS->AddInterf(nE1, nE2);
607           //
608           BOPDS_CoupleOfPaveBlocks aCPB;
609           //
610           aCPB.SetPaveBlocks(aPB1, aPB2);
611           aCPB.SetIndexInterf(iX);
612           aCPB.SetTolerance(aTolVnew);
613           aMVCPB.Add(aVnew, aCPB);
614         }//case TopAbs_VERTEX: 
615           break;
616             //
617         case TopAbs_EDGE: {
618           if (aNbCPrts > 1) {
619             break;
620           }
621           //
622           Standard_Boolean bHasSameBounds;
623           bHasSameBounds=aPB1->HasSameBounds(aPB2);
624           if (!bHasSameBounds) {
625             break;
626           }
627           // 1
628           BOPDS_InterfEE& aEE=aEEs.Append1();
629           iX=aEEs.Extent()-1;
630           aEE.SetIndices(nE1, nE2);
631           aEE.SetCommonPart(aCPart);
632           // 2
633           myDS->AddInterf(nE1, nE2);
634           //
635           BOPAlgo_Tools::FillMap<Handle(BOPDS_PaveBlock), TColStd_MapTransientHasher>(aPB1, aPB2, aMPBLPB, aAllocator);
636         }//case TopAbs_EDGE
637           break;
638         default:
639           break;
640       }//switch (aType) {
641     }//for (i=1; i<=aNbCPrts; i++) {
642   }//for (k=0; k < aNbFdgeEdge; ++k) {
643   // 
644   //=========================================
645   // post treatment
646   //=========================================
647   {
648     Standard_Integer aNbV;
649     Handle(BOPDS_PaveBlock) aPB1, aPB2;
650     //
651     aNbV=aMVCPB.Extent();
652     for (i=1; i<=aNbV; ++i) {
653       const BOPDS_CoupleOfPaveBlocks& aCPB=aMVCPB.FindFromIndex(i);
654       aCPB.PaveBlocks(aPB1, aPB2); 
655       //
656       aMPBToUpdate.Remove(aPB1);
657       aMPBToUpdate.Remove(aPB2);
658     }
659   }
660   //
661   aItPB.Initialize(aMPBToUpdate);
662   for (; aItPB.More(); aItPB.Next()) {
663     Handle(BOPDS_PaveBlock) aPB=aItPB.Value();
664     if (!myDS->IsCommonBlock(aPB)) {
665       myDS->UpdatePaveBlock(aPB);
666     }
667     else {
668       const Handle(BOPDS_CommonBlock)& aCB=myDS->CommonBlock(aPB);
669       myDS->UpdateCommonBlock(aCB, myFuzzyValue);
670     }
671   }
672   //
673   BOPAlgo_Tools::PerformCommonBlocks(aMPBLPB, aAllocator, myDS);
674   PerformVerticesEE(aMVCPB, aAllocator);
675   //-----------------------------------------------------scope t
676   aMPBLPB.Clear();
677   aMVCPB.Clear();
678   aMPBToUpdate.Clear();
679 }
680 //=======================================================================
681 //function : PerformVerticesEE
682 //purpose  : 
683 //=======================================================================
684 Standard_Integer BOPAlgo_PaveFiller::PerformVerticesEE
685   (BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks& theMVCPB,
686    const Handle(NCollection_BaseAllocator)& theAllocator)
687 {
688   Standard_Integer aNbV, iRet;
689   //
690   iRet=0;
691   aNbV=theMVCPB.Extent();
692   if (!aNbV) {
693     return iRet;
694   }
695   //
696   Standard_Integer nVx, iV, j, nE, iFlag, iX, i, aNb; 
697   Standard_Real aT;
698   BOPCol_ListIteratorOfListOfShape aItLS;
699   BOPCol_ListIteratorOfListOfInteger aItLI;
700   BOPDS_ListIteratorOfListOfPaveBlock aItLPB;
701   BOPDS_ShapeInfo aSI;
702   BOPDS_Pave aPave;
703   //
704   BOPDS_IndexedDataMapOfPaveBlockListOfInteger aMPBLI(100, theAllocator);
705   BOPCol_ListOfShape aLS(theAllocator);
706   BOPCol_IndexedDataMapOfShapeInteger aMVI(100, theAllocator);
707   BOPCol_IndexedDataMapOfShapeListOfShape aImages;
708   //
709   aSI.SetShapeType(TopAbs_VERTEX);
710   BOPDS_VectorOfInterfEE& aEEs=myDS->InterfEE();
711   //
712   // 1 prepare arguments
713   // 2 Fuse vertices
714   TreatNewVertices(theMVCPB, aImages);
715   //
716   // 3 Add new vertices to myDS; 
717   //   connect indices to CPB structure
718   aNb = aImages.Extent();
719   for (i=1; i<=aNb; ++i) {
720     const TopoDS_Vertex& aV=(*(TopoDS_Vertex*)(&aImages.FindKey(i)));
721     const BOPCol_ListOfShape& aLVSD=aImages.FindFromIndex(i);
722     //
723     aSI.SetShape(aV);
724     iV=myDS->Append(aSI);
725     //
726     BOPDS_ShapeInfo& aSIDS=myDS->ChangeShapeInfo(iV);
727     Bnd_Box& aBox=aSIDS.ChangeBox();
728     BRepBndLib::Add(aV, aBox);
729     aBox.SetGap(aBox.GetGap() + Precision::Confusion());
730     //
731     aItLS.Initialize(aLVSD);
732     for (; aItLS.More(); aItLS.Next()) {
733       const TopoDS_Shape& aVx = aItLS.Value();
734       BOPDS_CoupleOfPaveBlocks &aCPB=theMVCPB.ChangeFromKey(aVx);
735       aCPB.SetIndex(iV);
736       // update EE interference
737       iX=aCPB.IndexInterf();
738       BOPDS_InterfEE& aEE=aEEs(iX);
739       aEE.SetIndexNew(iV);
740     }
741   }
742   //
743   // 4 Map PaveBlock/ListOfVertices to add to this PaveBlock ->aMPBLI
744   {
745     Handle(BOPDS_PaveBlock) aPB[2];
746     //
747     for (i=1; i<=aNbV; ++i) {
748       const BOPDS_CoupleOfPaveBlocks& aCPB=theMVCPB.FindFromIndex(i);
749       iV=aCPB.Index();
750       aCPB.PaveBlocks(aPB[0], aPB[1]);
751       for (j=0; j<2; ++j) {
752         if (aMPBLI.Contains(aPB[j])) {
753           BOPCol_ListOfInteger& aLI=aMPBLI.ChangeFromKey(aPB[j]);
754           aLI.Append(iV);
755         }
756         else {
757           BOPCol_ListOfInteger aLI(theAllocator);
758           aLI.Append(iV);
759           aMPBLI.Add(aPB[j], aLI);
760         }
761       }
762     }
763   }
764   // 5 
765   // 5.1  Compute Extra Paves and 
766   // 5.2. Add Extra Paves to the PaveBlocks
767   //-------------------------------------------------------------
768   Standard_Integer k, aNbVPVE;
769   BOPAlgo_VectorOfPVE aVPVE;
770   //
771   aNb=aMPBLI.Extent();
772   for(i=1; i<=aNb; ++i) {
773     Handle(BOPDS_PaveBlock) aPB=aMPBLI.FindKey(i);
774     nE=aPB->OriginalEdge();
775     const TopoDS_Edge& aE=(*(TopoDS_Edge *)(&myDS->Shape(nE)));
776     // 1,2
777     const BOPCol_ListOfInteger& aLI=aMPBLI.FindFromIndex(i);
778     aItLI.Initialize(aLI);
779     for (; aItLI.More(); aItLI.Next()) {
780       nVx=aItLI.Value();
781       const TopoDS_Vertex& aVx=(*(TopoDS_Vertex *)(&myDS->Shape(nVx)));
782       //
783       BOPAlgo_PVE& aPVE=aVPVE.Append1();
784       aPVE.SetIndices(nVx, nE);
785       aPVE.SetVertex(aVx);
786       aPVE.SetEdge(aE);
787       aPVE.SetFuzzyValue(myFuzzyValue);
788       aPVE.SetPaveBlock(aPB);
789     }
790   }
791   //
792   aNbVPVE=aVPVE.Extent();
793   //=============================================================
794   BOPAlgo_PVECnt::Perform(myRunParallel, aVPVE, myContext);
795   //=============================================================
796   //
797   for (k=0; k < aNbVPVE; ++k) {
798     BOPAlgo_PVE& aPVE=aVPVE(k);
799     iFlag=aPVE.Flag();
800     if (!iFlag) {
801       aPVE.Indices(nVx, nE);
802       aT=aPVE.Parameter();
803       Handle(BOPDS_PaveBlock)& aPB=aPVE.PaveBlock();
804       //
805       aPave.SetIndex(nVx);
806       aPave.SetParameter(aT);
807       aPB->AppendExtPave(aPave);
808     }
809   }
810   // 6  Split PaveBlocksa
811   aNb=aMPBLI.Extent();
812   for(i=1; i<=aNb; ++i) {
813     Handle(BOPDS_PaveBlock) aPB=aMPBLI.FindKey(i);
814     nE=aPB->OriginalEdge();
815     // 3
816     if (!myDS->IsCommonBlock(aPB)) {
817       myDS->UpdatePaveBlock(aPB);
818     }
819     else {
820       const Handle(BOPDS_CommonBlock)& aCB=myDS->CommonBlock(aPB);
821       myDS->UpdateCommonBlock(aCB, myFuzzyValue);
822     }    
823   }//for (; aItMPBLI.More(); aItMPBLI.Next()) {
824   //
825   return iRet;
826 }
827 //=======================================================================
828 //function : TreatNewVertices
829 //purpose  : 
830 //=======================================================================
831 void BOPAlgo_PaveFiller::TreatNewVertices
832 (const BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks& theMVCPB,
833    BOPCol_IndexedDataMapOfShapeListOfShape& myImages)
834 {
835   Standard_Integer  i, aNbV;//, aNbVSD;
836   Standard_Real aTol;
837   TopoDS_Vertex aVnew;
838   BOPCol_IndexedMapOfShape aMVProcessed;
839   BOPCol_MapOfInteger aMFence;
840   BOPCol_ListIteratorOfListOfInteger aIt;
841   NCollection_Vector<BOPCol_ListOfShape> aVecOfLVSD;
842   //
843   BOPCol_BoxBndTree aBBTree;
844   NCollection_UBTreeFiller <Standard_Integer, 
845                             Bnd_Box> aTreeFiller(aBBTree);
846   BOPAlgo_VectorOfTNV aVTNV;
847   //
848   Standard_Real aTolAdd = myFuzzyValue / 2.;
849   aNbV = theMVCPB.Extent();
850   for (i=1; i<=aNbV; ++i) {
851     const TopoDS_Vertex& aV = *((TopoDS_Vertex*)&theMVCPB.FindKey(i));
852     Bnd_Box aBox;
853     //
854     aTol = theMVCPB.FindFromIndex(i).Tolerance();
855     aBox.Add(BRep_Tool::Pnt(aV));
856     aBox.SetGap(aTol + aTolAdd);
857     //
858     aTreeFiller.Add(i, aBox);
859     //
860     BOPAlgo_TNV& aTNV=aVTNV.Append1();
861     aTNV.SetTree(aBBTree);
862     aTNV.SetBox(aBox);
863     aTNV.SetVertex(aV);
864     aTNV.SetTolerance(aTol);
865     aTNV.SetFuzzyValue(myFuzzyValue);
866     aTNV.SetVectorOfTNV(aVTNV);
867   }
868   //
869   aTreeFiller.Fill();
870   //
871   //===========================================
872   BOPAlgo_TNVCnt::Perform(myRunParallel, aVTNV);
873   //===========================================
874   //
875   // Chains
876   for (i=1; i<=aNbV; ++i) {
877     if (!aMFence.Add(i)) {
878       continue;
879     }
880     //
881     Standard_Integer aIP, aNbIP1, aIP1;
882     BOPCol_ListOfShape aLVSD;
883     BOPCol_ListOfInteger aLIP, aLIP1, aLIPC;
884     BOPCol_ListIteratorOfListOfInteger aItLIP;
885     //
886     aLIPC.Append(i);
887     aLIP.Append(i);
888     for(;;) {
889       aItLIP.Initialize(aLIP);
890       for(; aItLIP.More(); aItLIP.Next()) {
891         aIP=aItLIP.Value();
892         //
893         BOPAlgo_TNV& aTNV=aVTNV(aIP-1);
894         const BOPCol_ListOfInteger& aLI=aTNV.Indices();
895         aIt.Initialize(aLI);
896         for (; aIt.More(); aIt.Next()) {
897           aIP1=aIt.Value();
898           if (!aMFence.Add(aIP1)) {
899             continue;
900           }
901           aLIP1.Append(aIP1);
902         } //for (; aIt.More(); aIt.Next()) {
903       }//for(; aIt1.More(); aIt1.Next()) {
904       //
905       aNbIP1=aLIP1.Extent();
906       if (!aNbIP1) {
907         break; // from for(;;) 
908       }
909       //
910       aLIP = aLIP1;
911       aLIPC.Append(aLIP1); // items of aLIP1 are moved to aLIPC
912     }// for(;;) {
913     //
914     aItLIP.Initialize(aLIPC);
915     for(; aItLIP.More(); aItLIP.Next()) {
916       aIP=aItLIP.Value();
917       const TopoDS_Vertex& aVP=aVTNV(aIP-1).Vertex(); 
918       aLVSD.Append(aVP);
919     }
920     aVecOfLVSD.Append(aLVSD);
921   }// for (i=1; i<=aNbV; ++i) {
922
923   // Make new vertices
924   aNbV = aVecOfLVSD.Size();
925   for (i = 0; i < aNbV; ++i) {
926     const BOPCol_ListOfShape& aLVSD = aVecOfLVSD(i);
927     BOPTools_AlgoTools::MakeVertex(aLVSD, aVnew);
928     myImages.Add(aVnew, aLVSD);
929   }
930 }
931 //=======================================================================
932 //function : FillShrunkData
933 //purpose  : 
934 //=======================================================================
935 void BOPAlgo_PaveFiller::FillShrunkData(Handle(BOPDS_PaveBlock)& thePB)
936 {
937   Standard_Integer nE, nV1, nV2;
938   Standard_Real aT1, aT2, aTS1, aTS2;
939   IntTools_ShrunkRange aSR;
940   //
941   myErrorStatus=0;
942   myWarningStatus = 0;
943   //
944   const BOPDS_Pave& aPave1=thePB->Pave1();
945   nV1=aPave1.Index();
946   aT1=aPave1.Parameter();
947   const TopoDS_Vertex& aV1=(*(TopoDS_Vertex *)(&myDS->Shape(nV1))); 
948   //
949   const BOPDS_Pave& aPave2=thePB->Pave2();
950   nV2=aPave2.Index();
951   aT2=aPave2.Parameter();
952   const TopoDS_Vertex& aV2=(*(TopoDS_Vertex *)(&myDS->Shape(nV2))); 
953   //
954   nE=thePB->OriginalEdge();
955   const TopoDS_Edge& aE=(*(TopoDS_Edge *)(&myDS->Shape(nE))); 
956   //
957   aSR.SetContext(myContext);
958   aSR.SetData(aE, aT1, aT2, aV1, aV2);
959   //
960   aSR.Perform();
961   if (!aSR.IsDone()) {
962     myWarningStatus = 1;
963     return;
964   }
965   //
966   aSR.ShrunkRange(aTS1, aTS2);
967   const Bnd_Box& aBox=aSR.BndBox();
968   Standard_Boolean bIsSplittable = aSR.IsSplittable();
969   //
970   thePB->SetShrunkData(aTS1, aTS2, aBox, bIsSplittable);
971 }
972 //=======================================================================
973 //function : ForceInterfVE
974 //purpose  : 
975 //=======================================================================
976 void BOPAlgo_PaveFiller::ForceInterfVE(const Standard_Integer nV,
977                                        Handle(BOPDS_PaveBlock)& aPB,
978                                        BOPDS_MapOfPaveBlock& aMPBToUpdate)
979 {
980   Standard_Integer nE, nVx, nVSD, iFlag;
981   Standard_Real aT, aTolVNew;
982   //
983   nE = aPB->OriginalEdge();
984   //
985   const BOPDS_ShapeInfo& aSIE=myDS->ShapeInfo(nE);
986   if (aSIE.HasSubShape(nV)) {
987     return;
988   }
989   //
990   if (myDS->HasInterf(nV, nE)) {
991     return;
992   }   
993   //
994   if (myDS->HasInterfShapeSubShapes(nV, nE)) {
995     return;
996   }
997   //
998   if (aPB->Pave1().Index() == nV || 
999       aPB->Pave2().Index() == nV) {
1000     return;
1001   }
1002   //
1003   nVx = nV;
1004   if (myDS->HasShapeSD(nV, nVSD)) {
1005     nVx = nVSD;
1006   }
1007   //
1008   const TopoDS_Vertex& aV = *(TopoDS_Vertex*)&myDS->Shape(nVx);
1009   const TopoDS_Edge&   aE = *(TopoDS_Edge*)  &myDS->Shape(nE);
1010   //
1011   iFlag = myContext->ComputeVE(aV, aE, aT, aTolVNew, myFuzzyValue);
1012   if (iFlag == 0 || iFlag == -4) {
1013     BOPDS_Pave aPave;
1014     //
1015     //
1016     BOPDS_VectorOfInterfVE& aVEs=myDS->InterfVE();
1017     aVEs.SetIncrement(10);
1018     // 1
1019     BOPDS_InterfVE& aVE=aVEs.Append1();
1020     aVE.SetIndices(nV, nE);
1021     aVE.SetParameter(aT);
1022     // 2
1023     myDS->AddInterf(nV, nE);
1024     //
1025     // 3 update vertex V/E if necessary
1026     nVx=UpdateVertex(nV, aTolVNew);
1027     // 4
1028     if (myDS->IsNewShape(nVx)) {
1029       aVE.SetIndexNew(nVx);
1030     }
1031     // 5 append ext pave to pave block
1032     aPave.SetIndex(nVx);
1033     aPave.SetParameter(aT);
1034     aPB->AppendExtPave(aPave);
1035     //
1036     aMPBToUpdate.Add(aPB);
1037   }
1038 }
1039
1040 //=======================================================================
1041 //function : GetPBBox
1042 //purpose  : 
1043 //=======================================================================
1044 Standard_Boolean BOPAlgo_PaveFiller::GetPBBox(const TopoDS_Edge& theE,
1045                                               const Handle(BOPDS_PaveBlock)& thePB,
1046                                               BOPAlgo_DataMapOfPaveBlockBndBox& thePBBox,
1047                                               Standard_Real& theFirst,
1048                                               Standard_Real& theLast,
1049                                               Standard_Real& theSFirst,
1050                                               Standard_Real& theSLast,
1051                                               Bnd_Box& theBox)
1052 {
1053   thePB->Range(theFirst, theLast);
1054   // check the validity of PB's range
1055   Standard_Boolean bValid = theLast - theFirst > Precision::PConfusion();
1056   if (!bValid) {
1057     return bValid;
1058   }
1059   //
1060   // check shrunk data
1061   if (thePB->HasShrunkData()) {
1062     Standard_Boolean bIsSplittable;
1063     thePB->ShrunkData(theSFirst, theSLast, theBox, bIsSplittable);
1064     return bValid;
1065   }
1066   //
1067   theSFirst = theFirst;
1068   theSLast = theLast;
1069   // check the map
1070   if (thePBBox.IsBound(thePB)) {
1071     theBox = thePBBox.Find(thePB);
1072   }
1073   else {
1074     // build bounding box
1075     BRepAdaptor_Curve aBAC(theE);
1076     Standard_Real aTol = BRep_Tool::Tolerance(theE) + Precision::Confusion();
1077     BndLib_Add3dCurve::Add(aBAC, theSFirst, theSLast, aTol, theBox);
1078     thePBBox.Bind(thePB, theBox);
1079   }
1080   return bValid;
1081 }