0024952: Possibility to break Boolean operations algorithm by user request
[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 #include <BOPAlgo_PaveFiller.ixx>
19
20 #include <Precision.hxx>
21 #include <NCollection_IncAllocator.hxx>
22 #include <NCollection_UBTreeFiller.hxx>
23
24 #include <Bnd_Box.hxx>
25
26 #include <GeomAPI_ProjectPointOnCurve.hxx>
27
28 #include <TopoDS_Edge.hxx>
29 #include <TopoDS_Vertex.hxx>
30 #include <TopoDS_Compound.hxx>
31 #include <BRep_Tool.hxx>
32 #include <BRep_Builder.hxx>
33 #include <BRepTools.hxx>
34 #include <BRepBndLib.hxx>
35 //
36 #include <IntTools_EdgeEdge.hxx>
37 #include <IntTools_Range.hxx>
38 #include <IntTools_SequenceOfCommonPrts.hxx>
39 #include <IntTools_CommonPrt.hxx>
40 #include <IntTools_SequenceOfRanges.hxx>
41 //
42 #include <BOPTools_AlgoTools.hxx>
43 //
44 #include <BOPCol_DataMapOfShapeInteger.hxx>
45 #include <BOPCol_DataMapOfShapeListOfShape.hxx>
46 #include <BOPCol_DataMapOfIntegerShape.hxx>
47 #include <BOPCol_IndexedDataMapOfShapeBox.hxx>
48 #include <BOPCol_BoxBndTree.hxx>
49 #include <BOPCol_NCVector.hxx>
50 #include <BOPCol_TBB.hxx>
51 //
52 #include <IntTools_Context.hxx>
53 #include <IntTools_ShrunkRange.hxx>
54 #include <IntTools_Tools.hxx>
55 //
56 #include <BOPDS_DataMapOfPaveBlockListOfPaveBlock.hxx>
57 #include <BOPDS_MapOfPaveBlock.hxx>
58 #include <BOPDS_CommonBlock.hxx>
59 #include <BOPDS_CoupleOfPaveBlocks.hxx>
60 #include <BOPDS_DataMapOfPaveBlockListOfInteger.hxx>
61 #include <BOPDS_Iterator.hxx>
62 #include <BOPDS_VectorOfInterfEE.hxx>
63 #include <BOPDS_Interf.hxx>
64 #include <BOPDS_Pave.hxx>
65 //
66 #include <BOPAlgo_Tools.hxx>
67
68 /////////////////////////////////////////////////////////////////////////
69 //=======================================================================
70 //class    : BOPAlgo_EdgeEdge
71 //purpose  : 
72 //=======================================================================
73 class BOPAlgo_EdgeEdge : 
74   public IntTools_EdgeEdge,
75   public BOPAlgo_Algo {
76  
77  public:
78
79   DEFINE_STANDARD_ALLOC
80   //
81   BOPAlgo_EdgeEdge(): 
82     IntTools_EdgeEdge(),
83     BOPAlgo_Algo() {
84   };
85   //
86   virtual ~BOPAlgo_EdgeEdge(){
87   };
88   //
89   void SetPaveBlock1(const Handle(BOPDS_PaveBlock)& aPB) {
90     myPB1=aPB;
91   }
92   //
93   Handle(BOPDS_PaveBlock)& PaveBlock1() {
94     return myPB1;
95   }
96   //
97   void SetPaveBlock2(const Handle(BOPDS_PaveBlock)& aPB) {
98     myPB2=aPB;
99   }
100   //
101   Handle(BOPDS_PaveBlock)& PaveBlock2() {
102     return myPB2;
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_TBBFunctor 
120   <BOPAlgo_EdgeEdge,
121   BOPAlgo_VectorOfEdgeEdge> BOPAlgo_EdgeEdgeFunctor;
122 //
123 typedef BOPCol_TBBCnt 
124   <BOPAlgo_EdgeEdgeFunctor,
125   BOPAlgo_VectorOfEdgeEdge> BOPAlgo_EdgeEdgeCnt;
126 //
127 /////////////////////////////////////////////////////////////////////////
128 //=======================================================================
129 //class    : BOPAlgo_TNV
130 //purpose  : 
131 //=======================================================================
132 class BOPAlgo_TNV : public BOPCol_BoxBndTreeSelector{
133  public:
134   BOPAlgo_TNV() 
135     : BOPCol_BoxBndTreeSelector(), myTree(NULL) {
136   };
137   //
138   ~BOPAlgo_TNV(){
139   };
140   //
141   void SetVertex(const TopoDS_Vertex& aV) {
142     myV=aV;
143   }
144   //
145   const TopoDS_Vertex& Vertex()const {
146     return myV;
147   }
148   //
149   void SetTree(BOPCol_BoxBndTree& aTree) {
150     myTree=&aTree;
151   }
152   //
153   void Perform() {
154     myTree->Select(*this);
155   }
156   //
157  protected:
158   TopoDS_Vertex myV;
159   BOPCol_BoxBndTree *myTree;
160 };
161 //
162 //=======================================================================
163 typedef BOPCol_NCVector
164   <BOPAlgo_TNV> BOPAlgo_VectorOfTNV; 
165 //
166 typedef BOPCol_TBBFunctor 
167   <BOPAlgo_TNV,
168   BOPAlgo_VectorOfTNV> BOPAlgo_TNVFunctor;
169 //
170 typedef BOPCol_TBBCnt 
171   <BOPAlgo_TNVFunctor,
172   BOPAlgo_VectorOfTNV> BOPAlgo_TNVCnt;
173 /////////////////////////////////////////////////////////////////////////
174 //=======================================================================
175 //class    : BOPAlgo_PVE
176 //purpose  : 
177 //=======================================================================
178 class BOPAlgo_PVE {
179  public:
180   BOPAlgo_PVE()
181     : myIV(-1), myIE(-1), myFlag(-1), myT(-1.) {
182   };
183   //
184   ~BOPAlgo_PVE(){
185   };
186   //
187   void SetIndices(const Standard_Integer nV,
188                   const Standard_Integer nE){
189     myIV=nV;
190     myIE=nE;
191   }
192   //
193   void Indices(Standard_Integer& nV,
194                Standard_Integer& nE) const {
195     nV=myIV;
196     nE=myIE;
197   }
198   //
199   void SetVertex(const TopoDS_Vertex& aV) {
200     myV=aV;
201   }
202   //
203   const TopoDS_Vertex& Vertex()const {
204     return myV;
205   }
206   //
207   void SetEdge(const TopoDS_Edge& aE) {
208     myE=aE;
209   }
210   //
211   const TopoDS_Edge& Edge()const {
212     return myE;
213   }
214   //
215   void SetPaveBlock(const Handle(BOPDS_PaveBlock)& aPB) {
216     myPB=aPB;
217   }
218   //
219   Handle(BOPDS_PaveBlock)& PaveBlock() {
220     return myPB;
221   }
222   //
223   Standard_Integer Flag()const {
224     return myFlag;
225   }
226   //
227   Standard_Real Parameter()const {
228     return myT;
229   }
230   //
231   void SetContext(const Handle(IntTools_Context)& aContext) {
232     myContext=aContext;
233   }
234   //
235   const Handle(IntTools_Context)& Context()const {
236     return myContext;
237   }
238   //
239   void Perform() {
240     myFlag=myContext->ComputeVE (myV, myE, myT);
241   };
242   //
243  protected:
244   Standard_Integer myIV;
245   Standard_Integer myIE;
246   Standard_Integer myFlag;
247   Standard_Real myT;
248   TopoDS_Vertex myV;
249   TopoDS_Edge myE;
250   Handle(BOPDS_PaveBlock) myPB;
251   Handle(IntTools_Context) myContext;
252 };
253 //=======================================================================
254 typedef BOPCol_NCVector
255   <BOPAlgo_PVE> BOPAlgo_VectorOfPVE; 
256 //
257 typedef BOPCol_TBBContextFunctor 
258   <BOPAlgo_PVE,
259   BOPAlgo_VectorOfPVE,
260   Handle(IntTools_Context), 
261   IntTools_Context> BOPAlgo_PVEFunctor;
262 //
263 typedef BOPCol_TBBContextCnt 
264   <BOPAlgo_PVEFunctor,
265   BOPAlgo_VectorOfPVE,
266   Handle(IntTools_Context)> BOPAlgo_PVECnt;
267 /////////////////////////////////////////////////////////////////////////
268 //=======================================================================
269 // function: PerformEE
270 // purpose: 
271 //=======================================================================
272 void BOPAlgo_PaveFiller::PerformEE()
273 {
274   Standard_Integer iSize;
275   //
276   myErrorStatus=0;
277   //
278   FillShrunkData(TopAbs_EDGE, TopAbs_EDGE);
279   //
280   myIterator->Initialize(TopAbs_EDGE, TopAbs_EDGE);
281   iSize=myIterator->ExpectedLength();
282   if (!iSize) {
283     return; 
284   }
285   //
286   Standard_Boolean bJustAdd;
287   Standard_Integer i, iX, nE1, nE2, aNbCPrts, k, aNbFdgeEdge;
288   Standard_Real aTS11, aTS12, aTS21, aTS22, aT11, aT12, aT21, aT22;
289   TopAbs_ShapeEnum aType;
290   BOPDS_ListIteratorOfListOfPaveBlock aIt1, aIt2;
291   Handle(NCollection_IncAllocator) aAllocator;
292   BOPDS_MapOfPaveBlock aMPBToUpdate;
293   BOPAlgo_VectorOfEdgeEdge aVEdgeEdge;
294   BOPDS_MapIteratorOfMapOfPaveBlock aItPB; 
295   //
296   //-----------------------------------------------------scope f
297   BOPDS_IndexedDataMapOfPaveBlockListOfPaveBlock aMPBLPB(100, aAllocator);
298   BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks aMVCPB(100, aAllocator);
299   //
300   BOPDS_VectorOfInterfEE& aEEs=myDS->InterfEE();
301   aEEs.SetStartSize(iSize);
302   aEEs.SetIncrement(iSize);
303   aEEs.Init();
304   //
305   for (; myIterator->More(); myIterator->Next()) {
306     myIterator->Value(nE1, nE2, bJustAdd);
307     if(bJustAdd) {
308       continue;
309     }
310     //
311     const BOPDS_ShapeInfo& aSIE1=myDS->ShapeInfo(nE1);
312     if (aSIE1.HasFlag()){
313       continue;
314     }
315     const BOPDS_ShapeInfo& aSIE2=myDS->ShapeInfo(nE2);
316     if (aSIE2.HasFlag()){
317       continue;
318     }
319     //
320     const TopoDS_Edge& aE1=(*(TopoDS_Edge *)(&aSIE1.Shape()));
321     const TopoDS_Edge& aE2=(*(TopoDS_Edge *)(&aSIE2.Shape()));  
322     //
323     BOPDS_ListOfPaveBlock& aLPB1=myDS->ChangePaveBlocks(nE1);
324     BOPDS_ListOfPaveBlock& aLPB2=myDS->ChangePaveBlocks(nE2);
325     //
326     aIt1.Initialize(aLPB1);
327     for (; aIt1.More(); aIt1.Next()) {
328       Bnd_Box aBB1;
329       //
330       Handle(BOPDS_PaveBlock)& aPB1=aIt1.ChangeValue();
331       if (!aPB1->HasShrunkData()) {
332         continue;
333       }
334       aPB1->ShrunkData(aTS11, aTS12, aBB1);
335       //
336       aIt2.Initialize(aLPB2);
337       for (; aIt2.More(); aIt2.Next()) {
338         Bnd_Box aBB2;
339         //
340         Handle(BOPDS_PaveBlock)& aPB2=aIt2.ChangeValue();
341         if (!aPB2->HasShrunkData()) {
342           continue;
343         }
344         aPB2->ShrunkData(aTS21, aTS22, aBB2);
345         //
346         if (aBB1.IsOut(aBB2)) {
347           continue;
348         }
349         //
350         aPB1->Range(aT11, aT12);
351         aPB2->Range(aT21, aT22);
352         //
353         BOPAlgo_EdgeEdge& anEdgeEdge=aVEdgeEdge.Append1();
354         // 
355         anEdgeEdge.SetPaveBlock1(aPB1);
356         anEdgeEdge.SetPaveBlock2(aPB2);
357         //
358         anEdgeEdge.SetEdge1(aE1, aT11, aT12);
359         anEdgeEdge.SetEdge2(aE2, aT21, aT22);
360         anEdgeEdge.SetProgressIndicator(myProgressIndicator);
361       }//for (; aIt2.More(); aIt2.Next()) {
362     }//for (; aIt1.More(); aIt1.Next()) {
363   }//for (; myIterator->More(); myIterator->Next()) {
364   //
365   aNbFdgeEdge=aVEdgeEdge.Extent();
366   //======================================================
367   BOPAlgo_EdgeEdgeCnt::Perform(myRunParallel, aVEdgeEdge);
368   //======================================================
369   //
370   for (k=0; k < aNbFdgeEdge; ++k) {
371     Bnd_Box aBB1, aBB2;
372     //
373     BOPAlgo_EdgeEdge& anEdgeEdge=aVEdgeEdge(k);
374     if (!anEdgeEdge.IsDone()) {
375       continue;
376     }
377     //
378     //--------------------------------------------
379     Handle(BOPDS_PaveBlock)& aPB1=anEdgeEdge.PaveBlock1();
380     nE1=aPB1->OriginalEdge();
381     aPB1->Range(aT11, aT12);
382     aPB1->ShrunkData(aTS11, aTS12, aBB1);
383     //
384     Handle(BOPDS_PaveBlock)& aPB2=anEdgeEdge.PaveBlock2();
385     nE2=aPB2->OriginalEdge();
386     aPB2->Range(aT21, aT22);
387     aPB2->ShrunkData(aTS21, aTS22, aBB2);
388     //
389     //--------------------------------------------
390     IntTools_Range aR11(aT11, aTS11), aR12(aTS12, aT12),
391                    aR21(aT21, aTS21), aR22(aTS22, aT22);
392     //
393     const IntTools_SequenceOfCommonPrts& aCPrts = anEdgeEdge.CommonParts();
394     aNbCPrts=aCPrts.Length();
395     for (i=1; i<=aNbCPrts; ++i) {
396       const IntTools_CommonPrt& aCPart=aCPrts(i);
397       //
398       const TopoDS_Edge& aE1=aCPart.Edge1();
399       const TopoDS_Edge& aE2=aCPart.Edge2();
400       //
401       aType=aCPart.Type();
402       switch (aType) {
403         case TopAbs_VERTEX:  { 
404           Standard_Boolean bIsOnPave[4], bFlag;
405           Standard_Integer nV[4], j;
406           Standard_Real aT1, aT2, aTol;
407           TopoDS_Vertex aVnew;
408           IntTools_Range aCR1, aCR2;
409           //
410           IntTools_Tools::VertexParameters(aCPart, aT1, aT2);
411           aTol = Precision::Confusion();
412           aCR1 = aCPart.Range1();
413           aCR2 = aCPart.Ranges2()(1);
414           // 
415           //decide to keep the pave or not
416           bIsOnPave[0] = IntTools_Tools::IsOnPave1(aT1, aR11, aTol) ||
417             IntTools_Tools::IsOnPave1(aR11.First(), aCR1, aTol);
418           bIsOnPave[1] = IntTools_Tools::IsOnPave1(aT1, aR12, aTol) || 
419             IntTools_Tools::IsOnPave1(aR12.Last(), aCR1, aTol);
420           bIsOnPave[2] = IntTools_Tools::IsOnPave1(aT2, aR21, aTol) ||
421             IntTools_Tools::IsOnPave1(aR21.First(), aCR2, aTol);
422           bIsOnPave[3] = IntTools_Tools::IsOnPave1(aT2, aR22, aTol) ||
423             IntTools_Tools::IsOnPave1(aR22.Last(), aCR2, aTol);
424           //
425           aPB1->Indices(nV[0], nV[1]);
426           aPB2->Indices(nV[2], nV[3]);
427           //
428           if((bIsOnPave[0] && bIsOnPave[2]) || 
429              (bIsOnPave[0] && bIsOnPave[3]) ||
430              (bIsOnPave[1] && bIsOnPave[2]) || 
431              (bIsOnPave[1] && bIsOnPave[3])) {
432             continue;
433           }
434           //
435           bFlag = Standard_False;
436           for (j = 0; j < 4; ++j) {
437             if (bIsOnPave[j]) {
438               //add interf VE(nV[j], nE)
439               Handle(BOPDS_PaveBlock)& aPB = (j < 2) ? aPB2 : aPB1;
440               ForceInterfVE(nV[j], aPB, aMPBToUpdate);
441               bFlag = Standard_True;
442               break;
443             }
444           }
445           if (bFlag) {
446             continue;
447           }
448           //
449           BOPTools_AlgoTools::MakeNewVertex(aE1, aT1, aE2, aT2, aVnew);
450           // <-LXBR
451           {
452             Standard_Integer nVS[2], iFound, k;
453             Standard_Real aTolVx, aTolVnew, aD2, aDT2;
454             BOPCol_MapOfInteger aMV;
455             gp_Pnt aPnew, aPx;
456             //
457             iFound=0;
458             j=-1;
459             aMV.Add(nV[0]);
460             aMV.Add(nV[1]);
461             //
462             if (aMV.Contains(nV[2])) {
463               ++j;
464               nVS[j]=nV[2];
465             }
466             if (aMV.Contains(nV[3])) {
467               ++j;
468               nVS[j]=nV[3];
469             }
470             //
471             aTolVnew=BRep_Tool::Tolerance(aVnew);
472             aPnew=BRep_Tool::Pnt(aVnew);
473             //
474             for (k=0; k<=j; ++k) {
475               const TopoDS_Vertex& aVx= *(TopoDS_Vertex*)&(myDS->Shape(nVS[k]));
476               aTolVx=BRep_Tool::Tolerance(aVx);
477               aPx=BRep_Tool::Pnt(aVx);
478               aD2=aPnew.SquareDistance(aPx);
479               //
480               aDT2=100.*(aTolVnew+aTolVx)*(aTolVnew+aTolVx);
481               //
482               if (aD2<aDT2) {
483                 iFound=1;
484                 break;
485               }
486             }
487             //
488             if (iFound) {
489               continue;
490             }
491           }
492           
493           // 1
494           iX=aEEs.Append()-1;
495           BOPDS_InterfEE& aEE=aEEs(iX);
496           aEE.SetIndices(nE1, nE2);
497           aEE.SetCommonPart(aCPart);
498           // 2
499           myDS->AddInterf(nE1, nE2);
500           //
501           BOPDS_CoupleOfPaveBlocks aCPB;
502           //
503           aCPB.SetPaveBlocks(aPB1, aPB2);
504           aCPB.SetIndexInterf(iX);
505           aMVCPB.Add(aVnew, aCPB);
506         }//case TopAbs_VERTEX: 
507           break;
508             //
509         case TopAbs_EDGE: {
510           if (aNbCPrts > 1) {
511             break;
512           }
513           //
514           Standard_Boolean bHasSameBounds;
515           bHasSameBounds=aPB1->HasSameBounds(aPB2);
516           if (!bHasSameBounds) {
517             break;
518           }
519           // 1
520           iX=aEEs.Append()-1;
521           BOPDS_InterfEE& aEE=aEEs(iX);
522           aEE.SetIndices(nE1, nE2);
523           aEE.SetCommonPart(aCPart);
524           // 2
525           myDS->AddInterf(nE1, nE2);
526           //
527           BOPAlgo_Tools::FillMap(aPB1, aPB2, aMPBLPB, aAllocator);
528         }//case TopAbs_EDGE
529           break;
530         default:
531           break;
532       }//switch (aType) {
533     }//for (i=1; i<=aNbCPrts; i++) {
534   }//for (k=0; k < aNbFdgeEdge; ++k) {
535   // 
536   //=========================================
537   // post treatment
538   //=========================================
539   aItPB.Initialize(aMPBToUpdate);
540   for (; aItPB.More(); aItPB.Next()) {
541     Handle(BOPDS_PaveBlock) aPB=aItPB.Value();
542     if (!myDS->IsCommonBlock(aPB)) {
543       myDS->UpdatePaveBlock(aPB);
544     }
545     else {
546       const Handle(BOPDS_CommonBlock)& aCB=myDS->CommonBlock(aPB);
547       myDS->UpdateCommonBlock(aCB);
548     }
549   }
550   //
551   BOPAlgo_Tools::PerformCommonBlocks(aMPBLPB, aAllocator, myDS);
552   PerformVerticesEE(aMVCPB, aAllocator);
553   //-----------------------------------------------------scope t
554   aMPBLPB.Clear();
555   aMVCPB.Clear();
556   aMPBToUpdate.Clear();
557 }
558 //=======================================================================
559 //function : PerformVertices
560 //purpose  : 
561 //=======================================================================
562 Standard_Integer BOPAlgo_PaveFiller::PerformVerticesEE
563   (BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks& theMVCPB,
564    Handle(NCollection_BaseAllocator)& theAllocator)
565 {
566   Standard_Integer aNbV, iRet;
567   //
568   iRet=0;
569   aNbV=theMVCPB.Extent();
570   if (!aNbV) {
571     return iRet;
572   }
573   //
574   Standard_Integer nVx, iV, j, nE, iFlag, iX, i, aNb; 
575   Standard_Real aT;
576   TopoDS_Shape aV;
577   BOPCol_ListIteratorOfListOfShape aItLS;
578   BOPCol_ListIteratorOfListOfInteger aItLI;
579   BOPDS_ListIteratorOfListOfPaveBlock aItLPB;
580   BOPDS_ShapeInfo aSI;
581   BOPDS_Pave aPave;
582   //
583   BOPDS_IndexedDataMapOfPaveBlockListOfInteger aMPBLI(100, theAllocator);
584   BOPCol_ListOfShape aLS(theAllocator);
585   BOPCol_IndexedDataMapOfShapeInteger aMVI(100, theAllocator);
586   BOPCol_IndexedDataMapOfShapeListOfShape aImages;
587   //
588   aSI.SetShapeType(TopAbs_VERTEX);
589   BOPDS_VectorOfInterfEE& aEEs=myDS->InterfEE();
590   //
591   // 1 prepare arguments
592   //
593   // <- DEB
594   for (i=1; i<=aNbV; ++i) {
595     const TopoDS_Shape& aS=theMVCPB.FindKey(i);
596     const BOPDS_CoupleOfPaveBlocks& aCPB=theMVCPB.FindFromIndex(i);
597     iV=aCPB.IndexInterf();
598     aMVI.Add(aS, iV);
599   }
600   //
601   // 2 Fuse vertices
602   TreatNewVertices(aMVI, aImages);
603   //
604   // 3 Add new vertices to myDS; 
605   //   connect indices to CPB structure
606   aNb = aImages.Extent();
607   for (i=1; i<=aNb; ++i) {
608     const TopoDS_Vertex& aV=(*(TopoDS_Vertex*)(&aImages.FindKey(i)));
609     const BOPCol_ListOfShape& aLVSD=aImages.FindFromIndex(i);
610     //
611     aSI.SetShape(aV);
612     iV=myDS->Append(aSI);
613     //
614     BOPDS_ShapeInfo& aSIDS=myDS->ChangeShapeInfo(iV);
615     Bnd_Box& aBox=aSIDS.ChangeBox();
616     BRepBndLib::Add(aV, aBox);
617     //
618     aItLS.Initialize(aLVSD);
619     for (; aItLS.More(); aItLS.Next()) {
620       const TopoDS_Shape& aVx = aItLS.Value();
621       BOPDS_CoupleOfPaveBlocks &aCPB=theMVCPB.ChangeFromKey(aVx);
622       aCPB.SetIndex(iV);
623       // update EE interference
624       iX=aCPB.IndexInterf();
625       BOPDS_InterfEE& aEE=aEEs(iX);
626       aEE.SetIndexNew(iV);
627     }
628   }
629   //
630   // 4 Map PaveBlock/ListOfVertices to add to this PaveBlock ->aMPBLI
631   {
632     Handle(BOPDS_PaveBlock) aPB[2];
633     //
634     for (i=1; i<=aNbV; ++i) {
635       const BOPDS_CoupleOfPaveBlocks& aCPB=theMVCPB.FindFromIndex(i);
636       iV=aCPB.Index();
637       aCPB.PaveBlocks(aPB[0], aPB[1]);
638       for (j=0; j<2; ++j) {
639         if (aMPBLI.Contains(aPB[j])) {
640           BOPCol_ListOfInteger& aLI=aMPBLI.ChangeFromKey(aPB[j]);
641           aLI.Append(iV);
642         }
643         else {
644           BOPCol_ListOfInteger aLI(theAllocator);
645           aLI.Append(iV);
646           aMPBLI.Add(aPB[j], aLI);
647         }
648       }
649     }
650   }
651   // 5 
652   // 5.1  Compute Extra Paves and 
653   // 5.2. Add Extra Paves to the PaveBlocks
654   //-------------------------------------------------------------
655   Standard_Integer k, aNbVPVE;
656   BOPAlgo_VectorOfPVE aVPVE;
657   //
658   aNb=aMPBLI.Extent();
659   for(i=1; i<=aNb; ++i) {
660     Handle(BOPDS_PaveBlock) aPB=aMPBLI.FindKey(i);
661     nE=aPB->OriginalEdge();
662     const TopoDS_Edge& aE=(*(TopoDS_Edge *)(&myDS->Shape(nE)));
663     // 1,2
664     const BOPCol_ListOfInteger& aLI=aMPBLI.FindFromIndex(i);
665     aItLI.Initialize(aLI);
666     for (; aItLI.More(); aItLI.Next()) {
667       nVx=aItLI.Value();
668       const TopoDS_Vertex& aVx=(*(TopoDS_Vertex *)(&myDS->Shape(nVx)));
669       //
670       BOPAlgo_PVE& aPVE=aVPVE.Append1();
671       aPVE.SetIndices(nVx, nE);
672       aPVE.SetVertex(aVx);
673       aPVE.SetEdge(aE);
674       aPVE.SetPaveBlock(aPB);
675     }
676   }
677   //
678   aNbVPVE=aVPVE.Extent();
679   //=============================================================
680   BOPAlgo_PVECnt::Perform(myRunParallel, aVPVE, myContext);
681   //=============================================================
682   //
683   for (k=0; k < aNbVPVE; ++k) {
684     BOPAlgo_PVE& aPVE=aVPVE(k);
685     iFlag=aPVE.Flag();
686     if (!iFlag) {
687       aPVE.Indices(nVx, nE);
688       aT=aPVE.Parameter();
689       Handle(BOPDS_PaveBlock)& aPB=aPVE.PaveBlock();
690       //
691       aPave.SetIndex(nVx);
692       aPave.SetParameter(aT);
693       aPB->AppendExtPave(aPave);
694     }
695   }
696   // 6  Split PaveBlocksa
697   aNb=aMPBLI.Extent();
698   for(i=1; i<=aNb; ++i) {
699     Handle(BOPDS_PaveBlock) aPB=aMPBLI.FindKey(i);
700     nE=aPB->OriginalEdge();
701     // 3
702     if (!myDS->IsCommonBlock(aPB)) {
703       myDS->UpdatePaveBlock(aPB);
704     }
705     else {
706       const Handle(BOPDS_CommonBlock)& aCB=myDS->CommonBlock(aPB);
707       myDS->UpdateCommonBlock(aCB);
708     }    
709   }//for (; aItMPBLI.More(); aItMPBLI.Next()) {
710   //
711   return iRet;
712 }
713 //=======================================================================
714 //function : TreatNewVertices
715 //purpose  : 
716 //=======================================================================
717 void BOPAlgo_PaveFiller::TreatNewVertices
718   (const BOPCol_IndexedDataMapOfShapeInteger& aMapVI,
719    BOPCol_IndexedDataMapOfShapeListOfShape& myImages)
720 {
721   Standard_Integer  i, aNbV;//, aNbVSD;
722   Standard_Real aTol;
723   TopoDS_Vertex aVnew;
724   TopoDS_Shape aVF;
725   BOPCol_IndexedMapOfShape aMVProcessed;
726   BOPCol_MapOfInteger aMFence;
727   BOPCol_ListIteratorOfListOfInteger aIt;
728   BOPCol_DataMapOfShapeListOfShape aDMVLV;
729   BOPCol_DataMapIteratorOfDataMapOfShapeListOfShape aItDMVLV;
730   //
731   BOPCol_BoxBndTreeSelector aSelector;
732   BOPCol_BoxBndTree aBBTree;
733   NCollection_UBTreeFiller <Standard_Integer, 
734                             Bnd_Box> aTreeFiller(aBBTree);
735   BOPAlgo_VectorOfTNV aVTNV;
736   //
737   aNbV = aMapVI.Extent();
738   for (i=1; i<=aNbV; ++i) {
739     const TopoDS_Vertex& aV=*((TopoDS_Vertex*)&aMapVI.FindKey(i));
740     Bnd_Box aBox;
741     //
742     aTol=BRep_Tool::Tolerance(aV);
743     aBox.SetGap(aTol);
744     aBox.Add(BRep_Tool::Pnt(aV));
745     aBox.Enlarge(aTol);
746     //
747     aTreeFiller.Add(i, aBox);
748     //
749     BOPAlgo_TNV& aTNV=aVTNV.Append1();
750     aTNV.SetTree(aBBTree);
751     aTNV.SetBox(aBox);
752     aTNV.SetVertex(aV);
753   }
754   //
755   aTreeFiller.Fill();
756   //
757   //===========================================
758   BOPAlgo_TNVCnt::Perform(myRunParallel, aVTNV);
759   //===========================================
760   //
761   // Chains
762   for (i=1; i<=aNbV; ++i) {
763     if (!aMFence.Add(i)) {
764       continue;
765     }
766     //
767     Standard_Integer aIP, aNbIP1, aIP1;
768     BOPCol_ListOfShape aLVSD;
769     BOPCol_MapIteratorOfMapOfInteger aItMI;
770     BOPCol_ListOfInteger aLIP, aLIP1, aLIPC;
771     BOPCol_ListIteratorOfListOfInteger aItLIP;
772     //
773     aLIPC.Append(i);
774     aLIP.Append(i);
775     for(;;) {
776       aItLIP.Initialize(aLIP);
777       for(; aItLIP.More(); aItLIP.Next()) {
778         aIP=aItLIP.Value();
779         //
780         BOPAlgo_TNV& aTNV=aVTNV(aIP-1);
781         const BOPCol_ListOfInteger& aLI=aTNV.Indices();
782         aIt.Initialize(aLI);
783         for (; aIt.More(); aIt.Next()) {
784           aIP1=aIt.Value();
785           if (!aMFence.Add(aIP1)) {
786             continue;
787           }
788           aLIP1.Append(aIP1);
789         } //for (; aIt.More(); aIt.Next()) {
790       }//for(; aIt1.More(); aIt1.Next()) {
791       //
792       aNbIP1=aLIP1.Extent();
793       if (!aNbIP1) {
794         break; // from for(;;) 
795       }
796       //
797       aLIP.Clear();
798       aItLIP.Initialize(aLIP1);
799       for(; aItLIP.More(); aItLIP.Next()) {
800         aIP=aItLIP.Value();
801         aLIP.Append(aIP);
802         aLIPC.Append(aIP);
803       }
804       aLIP1.Clear();
805     }// for(;;) {
806     //
807     aItLIP.Initialize(aLIPC);
808     for(; aItLIP.More(); aItLIP.Next()) {
809       aIP=aItLIP.Value();
810       const TopoDS_Vertex& aVP=aVTNV(aIP-1).Vertex(); 
811       aLVSD.Append(aVP);
812     }
813     aVF=aLVSD.First();
814     aDMVLV.Bind(aVF, aLVSD);
815   }// for (i=1; i<=aNbV; ++i) {
816
817   // Make new vertices
818   aItDMVLV.Initialize(aDMVLV);
819   for(; aItDMVLV.More(); aItDMVLV.Next()) {
820     const TopoDS_Shape& aV=aItDMVLV.Key();
821     const BOPCol_ListOfShape& aLVSD=aItDMVLV.Value();
822     if (aLVSD.IsEmpty()) {
823       myImages.Add(aV, aLVSD);
824     }
825     else {
826       BOPCol_ListOfShape* pLVSD=(BOPCol_ListOfShape*)&aLVSD;
827       BOPTools_AlgoTools::MakeVertex(*pLVSD, aVnew);
828       myImages.Add(aVnew, aLVSD);
829     } 
830   }
831 }
832 //=======================================================================
833 //function : FillShrunkData
834 //purpose  : 
835 //=======================================================================
836 void BOPAlgo_PaveFiller::FillShrunkData(Handle(BOPDS_PaveBlock)& thePB)
837 {
838   Standard_Integer nE, nV1, nV2, iErr;
839   Standard_Real aT1, aT2, aTS1, aTS2;
840   IntTools_ShrunkRange aSR;
841   //
842   myErrorStatus=0;
843   myWarningStatus = 0;
844   //
845   const BOPDS_Pave& aPave1=thePB->Pave1();
846   nV1=aPave1.Index();
847   aT1=aPave1.Parameter();
848   const TopoDS_Vertex& aV1=(*(TopoDS_Vertex *)(&myDS->Shape(nV1))); 
849   //
850   const BOPDS_Pave& aPave2=thePB->Pave2();
851   nV2=aPave2.Index();
852   aT2=aPave2.Parameter();
853   const TopoDS_Vertex& aV2=(*(TopoDS_Vertex *)(&myDS->Shape(nV2))); 
854   //
855   nE=thePB->OriginalEdge();
856   const TopoDS_Edge& aE=(*(TopoDS_Edge *)(&myDS->Shape(nE))); 
857   //
858   aSR.SetContext(myContext);
859   aSR.SetData(aE, aT1, aT2, aV1, aV2);
860   //
861   aSR.Perform();
862   iErr=aSR.ErrorStatus();
863   if (iErr) {
864     myWarningStatus = 1;
865     //myErrorStatus=40;
866     return;
867   }
868   //
869   aSR.ShrunkRange(aTS1, aTS2);
870   const Bnd_Box& aBox=aSR.BndBox();
871   //
872   thePB->SetShrunkData(aTS1, aTS2, aBox);
873 }
874 //=======================================================================
875 //function : ForceInterfVE
876 //purpose  : 
877 //=======================================================================
878 void BOPAlgo_PaveFiller::ForceInterfVE(const Standard_Integer nV,
879                                        Handle(BOPDS_PaveBlock)& aPB,
880                                        BOPDS_MapOfPaveBlock& aMPBToUpdate)
881 {
882   Standard_Integer aNbPnt, nE;
883   gp_Pnt aP;
884   //
885   nE = aPB->OriginalEdge();
886   //
887   const BOPDS_ShapeInfo& aSIE=myDS->ShapeInfo(nE);
888   if (aSIE.HasSubShape(nV)) {
889     return;
890   }
891   //
892   if (myDS->HasInterf(nV, nE)) {
893     return;
894   }   
895   //
896   if (myDS->HasInterfShapeSubShapes(nV, nE)) {
897     return;
898   }
899   //
900   if (aPB->Pave1().Index() == nV || aPB->Pave2().Index() == nV) {
901     return;
902   }
903   //
904   const TopoDS_Vertex& aV = *(TopoDS_Vertex*)&myDS->Shape(nV);
905   const TopoDS_Edge&   aE = *(TopoDS_Edge*)  &myDS->Shape(nE);
906   aP=BRep_Tool::Pnt(aV);
907   //
908   GeomAPI_ProjectPointOnCurve& aProjector=myContext->ProjPC(aE);
909   aProjector.Perform(aP);
910   //
911   aNbPnt = aProjector.NbPoints();
912   if (aNbPnt) {
913     Standard_Real aT, aDist;
914     Standard_Integer i;
915     BRep_Builder aBB;
916     BOPDS_Pave aPave;
917     //
918     aDist=aProjector.LowerDistance();
919     aT=aProjector.LowerDistanceParameter();
920     //
921     BOPDS_VectorOfInterfVE& aVEs=myDS->InterfVE();
922     if (aVEs.Extent() == 0) {
923       aVEs.Init();
924     }
925     //
926     i=aVEs.Append()-1;
927     BOPDS_InterfVE& aVE=aVEs(i);
928     aVE.SetIndices(nV, nE);
929     aVE.SetParameter(aT);
930     //
931     myDS->AddInterf(nV, nE);
932     //
933     aBB.UpdateVertex(aV, aDist);
934     BOPDS_ShapeInfo& aSIDS=myDS->ChangeShapeInfo(nV);
935     Bnd_Box& aBox=aSIDS.ChangeBox();
936     BRepBndLib::Add(aV, aBox);
937     //
938     aPave.SetIndex(nV);
939     aPave.SetParameter(aT);
940     aPB->AppendExtPave(aPave);
941     //
942     aMPBToUpdate.Add(aPB);
943   }
944 }
945
946  /*
947   // DEBf
948   { 
949     TopoDS_Compound aCx;
950     BRep_Builder aBBx;
951     aBBx.MakeCompound(aCx);
952     aItMVCPB.Initialize(theMVCPB);
953     for (; aItMVCPB.More(); aItMVCPB.Next()) {
954       const TopoDS_Shape& aS=aItMVCPB.Key();
955       aBBx.Add(aCx, aS);
956     }
957     BRepTools::Write(aCx, "cx");
958   }
959   // DEBt
960   */