0030092: Modeling Algorithms - Invalid result of Section operation
[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_Tools.hxx>
22 #include <BOPAlgo_Alerts.hxx>
23 #include <BOPDS_CommonBlock.hxx>
24 #include <BOPDS_CoupleOfPaveBlocks.hxx>
25 #include <BOPDS_DS.hxx>
26 #include <BOPDS_Interf.hxx>
27 #include <BOPDS_Iterator.hxx>
28 #include <BOPDS_MapOfPaveBlock.hxx>
29 #include <BOPDS_Pave.hxx>
30 #include <BOPDS_PaveBlock.hxx>
31 #include <BOPDS_VectorOfInterfEE.hxx>
32 #include <BOPTools_AlgoTools.hxx>
33 #include <BOPTools_AlgoTools2D.hxx>
34 #include <BOPTools_Parallel.hxx>
35 #include <BndLib_Add3dCurve.hxx>
36 #include <BRep_Tool.hxx>
37 #include <BRep_Builder.hxx>
38 #include <BRepAdaptor_Curve.hxx>
39 #include <GeomAPI_ProjectPointOnCurve.hxx>
40 #include <gp_Pnt.hxx>
41 #include <IntTools_CommonPrt.hxx>
42 #include <IntTools_Context.hxx>
43 #include <IntTools_EdgeEdge.hxx>
44 #include <IntTools_Range.hxx>
45 #include <IntTools_SequenceOfCommonPrts.hxx>
46 #include <IntTools_SequenceOfRanges.hxx>
47 #include <IntTools_ShrunkRange.hxx>
48 #include <IntTools_Tools.hxx>
49 #include <NCollection_IncAllocator.hxx>
50 #include <NCollection_Vector.hxx>
51 #include <Precision.hxx>
52 #include <TopoDS.hxx>
53 #include <TopoDS_Edge.hxx>
54 #include <TopoDS_Vertex.hxx>
55
56 /////////////////////////////////////////////////////////////////////////
57 //=======================================================================
58 //class    : BOPAlgo_EdgeEdge
59 //purpose  : 
60 //=======================================================================
61 class BOPAlgo_EdgeEdge : 
62   public IntTools_EdgeEdge,
63   public BOPAlgo_Algo {
64  
65  public:
66
67   DEFINE_STANDARD_ALLOC
68   //
69   BOPAlgo_EdgeEdge(): 
70     IntTools_EdgeEdge(),
71     BOPAlgo_Algo() {
72   };
73   //
74   virtual ~BOPAlgo_EdgeEdge(){
75   };
76   //
77   void SetPaveBlock1(const Handle(BOPDS_PaveBlock)& aPB) {
78     myPB1=aPB;
79   }
80   //
81   Handle(BOPDS_PaveBlock)& PaveBlock1() {
82     return myPB1;
83   }
84   //
85   void SetPaveBlock2(const Handle(BOPDS_PaveBlock)& aPB) {
86     myPB2=aPB;
87   }
88   //
89   Handle(BOPDS_PaveBlock)& PaveBlock2() {
90     return myPB2;
91   }
92   // 
93   void SetFuzzyValue(const Standard_Real theFuzz) {
94     IntTools_EdgeEdge::SetFuzzyValue(theFuzz);
95   }
96   //
97   virtual void Perform() {
98     BOPAlgo_Algo::UserBreak();
99     try
100     {
101       OCC_CATCH_SIGNALS
102
103       IntTools_EdgeEdge::Perform();
104     }
105     catch (Standard_Failure)
106     {
107       AddError(new BOPAlgo_AlertIntersectionFailed);
108     }
109   }
110   //
111  protected:
112   Handle(BOPDS_PaveBlock) myPB1;
113   Handle(BOPDS_PaveBlock) myPB2;
114 };
115 //
116 //=======================================================================
117 typedef NCollection_Vector
118   <BOPAlgo_EdgeEdge> BOPAlgo_VectorOfEdgeEdge; 
119 //
120 typedef BOPTools_Functor 
121   <BOPAlgo_EdgeEdge,
122   BOPAlgo_VectorOfEdgeEdge> BOPAlgo_EdgeEdgeFunctor;
123 //
124 typedef BOPTools_Cnt 
125   <BOPAlgo_EdgeEdgeFunctor,
126   BOPAlgo_VectorOfEdgeEdge> BOPAlgo_EdgeEdgeCnt;
127 //
128 /////////////////////////////////////////////////////////////////////////
129 //=======================================================================
130 // function: PerformEE
131 // purpose: 
132 //=======================================================================
133 void BOPAlgo_PaveFiller::PerformEE()
134 {
135   FillShrunkData(TopAbs_EDGE, TopAbs_EDGE);
136   //
137   myIterator->Initialize(TopAbs_EDGE, TopAbs_EDGE);
138   Standard_Integer iSize = myIterator->ExpectedLength();
139   if (!iSize) {
140     return; 
141   }
142   //
143   Standard_Boolean bExpressCompute, bIsPBSplittable1, bIsPBSplittable2;
144   Standard_Integer i, iX, nE1, nE2, aNbCPrts, k, aNbEdgeEdge;
145   Standard_Integer nV11, nV12, nV21, nV22;
146   Standard_Real aTS11, aTS12, aTS21, aTS22, aT11, aT12, aT21, aT22;
147   TopAbs_ShapeEnum aType;
148   BOPDS_ListIteratorOfListOfPaveBlock aIt1, aIt2;
149   Handle(NCollection_BaseAllocator) aAllocator;
150   BOPAlgo_VectorOfEdgeEdge aVEdgeEdge;
151   BOPDS_MapIteratorOfMapOfPaveBlock aItPB; 
152   // keep modified edges for further update
153   TColStd_MapOfInteger aMEdges;
154   //
155   aAllocator=NCollection_BaseAllocator::CommonBaseAllocator();
156   //-----------------------------------------------------scope f
157   BOPDS_IndexedDataMapOfPaveBlockListOfPaveBlock aMPBLPB(100, aAllocator);
158   BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks aMVCPB(100, aAllocator);
159   BOPAlgo_DataMapOfPaveBlockBndBox aDMPBBox(100, aAllocator);
160   //
161   BOPDS_VectorOfInterfEE& aEEs=myDS->InterfEE();
162   aEEs.SetIncrement(iSize);
163   //
164   for (; myIterator->More(); myIterator->Next()) {
165     myIterator->Value(nE1, nE2);
166     //
167     const BOPDS_ShapeInfo& aSIE1=myDS->ShapeInfo(nE1);
168     if (aSIE1.HasFlag()){
169       continue;
170     }
171     const BOPDS_ShapeInfo& aSIE2=myDS->ShapeInfo(nE2);
172     if (aSIE2.HasFlag()){
173       continue;
174     }
175     //
176     BOPDS_ListOfPaveBlock& aLPB1 = myDS->ChangePaveBlocks(nE1);
177     if (aLPB1.IsEmpty()) {
178       continue;
179     }
180     //
181     BOPDS_ListOfPaveBlock& aLPB2 = myDS->ChangePaveBlocks(nE2);
182     if (aLPB2.IsEmpty()) {
183       continue;
184     }
185     //
186     const TopoDS_Edge& aE1=(*(TopoDS_Edge *)(&aSIE1.Shape()));
187     const TopoDS_Edge& aE2=(*(TopoDS_Edge *)(&aSIE2.Shape()));
188     //
189     aIt1.Initialize(aLPB1);
190     for (; aIt1.More(); aIt1.Next()) {
191       Bnd_Box aBB1;
192       //
193       Handle(BOPDS_PaveBlock)& aPB1=aIt1.ChangeValue();
194       //
195       if (!GetPBBox(aE1, aPB1, aDMPBBox, aT11, aT12, aTS11, aTS12, aBB1)) {
196         continue;
197       }
198       //
199       aPB1->Indices(nV11, nV12);
200       //
201       aIt2.Initialize(aLPB2);
202       for (; aIt2.More(); aIt2.Next()) {
203         Bnd_Box aBB2;
204         //
205         Handle(BOPDS_PaveBlock)& aPB2=aIt2.ChangeValue();
206         //
207         if (!GetPBBox(aE2, aPB2, aDMPBBox, aT21, aT22, aTS21, aTS22, aBB2)) {
208           continue;
209         }
210         //
211         if (aBB1.IsOut(aBB2)) {
212           continue;
213         }
214         //
215         aPB2->Indices(nV21, nV22);
216         //
217         bExpressCompute=((nV11==nV21 && nV12==nV22) ||
218                          (nV12==nV21 && nV11==nV22));
219         //
220         BOPAlgo_EdgeEdge& anEdgeEdge=aVEdgeEdge.Appended();
221         //
222         anEdgeEdge.UseQuickCoincidenceCheck(bExpressCompute);
223         //
224         anEdgeEdge.SetPaveBlock1(aPB1);
225         anEdgeEdge.SetPaveBlock2(aPB2);
226         //
227         anEdgeEdge.SetEdge1(aE1, aT11, aT12);
228         anEdgeEdge.SetEdge2(aE2, aT21, aT22);
229         anEdgeEdge.SetFuzzyValue(myFuzzyValue);
230         anEdgeEdge.SetProgressIndicator(myProgressIndicator);
231       }//for (; aIt2.More(); aIt2.Next()) {
232     }//for (; aIt1.More(); aIt1.Next()) {
233   }//for (; myIterator->More(); myIterator->Next()) {
234   //
235   aNbEdgeEdge=aVEdgeEdge.Length();
236   //======================================================
237   BOPAlgo_EdgeEdgeCnt::Perform(myRunParallel, aVEdgeEdge);
238   //======================================================
239   //
240   for (k = 0; k < aNbEdgeEdge; ++k) {
241     Bnd_Box aBB1, aBB2;
242     //
243     BOPAlgo_EdgeEdge& anEdgeEdge=aVEdgeEdge(k);
244     if (!anEdgeEdge.IsDone() || anEdgeEdge.HasErrors()) {
245       // Warn about failed intersection of sub-shapes
246       const TopoDS_Shape& aE1 = myDS->Shape(anEdgeEdge.PaveBlock1()->OriginalEdge());
247       const TopoDS_Shape& aE2 = myDS->Shape(anEdgeEdge.PaveBlock2()->OriginalEdge());
248       AddIntersectionFailedWarning(aE1, aE2);
249       continue;
250     }
251     //
252     const IntTools_SequenceOfCommonPrts& aCPrts = anEdgeEdge.CommonParts();
253     aNbCPrts = aCPrts.Length();
254     if (!aNbCPrts) {
255       continue;
256     }
257     //--------------------------------------------
258     Handle(BOPDS_PaveBlock)& aPB1=anEdgeEdge.PaveBlock1();
259     nE1=aPB1->OriginalEdge();
260     aPB1->Range(aT11, aT12);
261     if (!aPB1->HasShrunkData()) {
262       aTS11 = aT11;
263       aTS12 = aT12;
264       bIsPBSplittable1 = Standard_False;
265     }
266     else {
267       aPB1->ShrunkData(aTS11, aTS12, aBB1, bIsPBSplittable1);
268     }
269     //
270     Handle(BOPDS_PaveBlock)& aPB2=anEdgeEdge.PaveBlock2();
271     nE2=aPB2->OriginalEdge();
272     aPB2->Range(aT21, aT22);
273     if (!aPB2->HasShrunkData()) {
274       aTS21 = aT21;
275       aTS22 = aT22;
276       bIsPBSplittable2 = Standard_False;
277     }
278     else {
279       aPB2->ShrunkData(aTS21, aTS22, aBB2, bIsPBSplittable2);
280     }
281     //
282     //--------------------------------------------
283     IntTools_Range aR11(aT11, aTS11), aR12(aTS12, aT12),
284                    aR21(aT21, aTS21), aR22(aTS22, aT22);
285     //
286     Standard_Boolean bAnalytical = Standard_False;
287     {
288       const TopoDS_Edge& aOE1 = *(TopoDS_Edge*)&myDS->Shape(nE1);
289       const TopoDS_Edge& aOE2 = *(TopoDS_Edge*)&myDS->Shape(nE2);
290       //
291       BRepAdaptor_Curve aBAC1(aOE1), aBAC2(aOE2);
292       //
293       GeomAbs_CurveType aType1 = aBAC1.GetType();
294       GeomAbs_CurveType aType2 = aBAC2.GetType();
295       //
296       bAnalytical = (((aType1 == GeomAbs_Line) &&
297                       (aType2 == GeomAbs_Line ||
298                        aType2 == GeomAbs_Circle)) ||
299                      ((aType2 == GeomAbs_Line) &&
300                       (aType1 == GeomAbs_Line ||
301                        aType1 == GeomAbs_Circle)));
302     }
303     //
304     for (i=1; i<=aNbCPrts; ++i) {
305       const IntTools_CommonPrt& aCPart=aCPrts(i);
306       //
307       const TopoDS_Edge& aE1=aCPart.Edge1();
308       const TopoDS_Edge& aE2=aCPart.Edge2();
309       //
310       aType=aCPart.Type();
311       switch (aType) {
312         case TopAbs_VERTEX:  { 
313           if (!bIsPBSplittable1 || !bIsPBSplittable2) {
314             continue;
315           }
316           //
317           Standard_Boolean bIsOnPave[4];
318           Standard_Integer nV[4], j;
319           Standard_Real aT1, aT2, aTol;
320           TopoDS_Vertex aVnew;
321           IntTools_Range aCR1, aCR2;
322           //
323           IntTools_Tools::VertexParameters(aCPart, aT1, aT2);
324           aTol = Precision::Confusion();
325           aCR1 = aCPart.Range1();
326           aCR2 = aCPart.Ranges2()(1);
327           // 
328           //decide to keep the pave or not
329           bIsOnPave[0] = IntTools_Tools::IsOnPave1(aT1, aR11, aTol) ||
330             IntTools_Tools::IsOnPave1(aR11.First(), aCR1, aTol);
331           bIsOnPave[1] = IntTools_Tools::IsOnPave1(aT1, aR12, aTol) || 
332             IntTools_Tools::IsOnPave1(aR12.Last(), aCR1, aTol);
333           bIsOnPave[2] = IntTools_Tools::IsOnPave1(aT2, aR21, aTol) ||
334             IntTools_Tools::IsOnPave1(aR21.First(), aCR2, aTol);
335           bIsOnPave[3] = IntTools_Tools::IsOnPave1(aT2, aR22, aTol) ||
336             IntTools_Tools::IsOnPave1(aR22.Last(), aCR2, aTol);
337           //
338           aPB1->Indices(nV[0], nV[1]);
339           aPB2->Indices(nV[2], nV[3]);
340           //
341           if((bIsOnPave[0] && bIsOnPave[2]) || 
342              (bIsOnPave[0] && bIsOnPave[3]) ||
343              (bIsOnPave[1] && bIsOnPave[2]) || 
344              (bIsOnPave[1] && bIsOnPave[3])) {
345             continue;
346           }
347           //
348           Standard_Boolean isVExists = Standard_False;
349           for (j = 0; j < 4; ++j)
350           {
351             if (bIsOnPave[j])
352             {
353               Handle(BOPDS_PaveBlock)& aPB = (j < 2) ? aPB2 : aPB1;
354               bIsOnPave[j] = ForceInterfVE(nV[j], aPB, aMEdges);
355               if (bIsOnPave[j]) isVExists = Standard_True;
356             }
357           }
358
359           BOPTools_AlgoTools::MakeNewVertex(aE1, aT1, aE2, aT2, aVnew);
360           const gp_Pnt aPnew = BRep_Tool::Pnt(aVnew);
361
362           if (isVExists)
363           {
364             // The found intersection point is located closely to one of the
365             // pave blocks bounds. So, do not create the new vertex in this point.
366             // Check if this point is a real intersection point or just a touching point.
367             // If it is a touching point, do nothing.
368             // If it is an intersection point, update the existing vertex to cover the
369             // intersection point.
370             const gp_Pnt aPOnE1 = BRepAdaptor_Curve(aE1).Value(aT1);
371             const gp_Pnt aPOnE2 = BRepAdaptor_Curve(aE2).Value(aT2);
372             if (aPOnE1.Distance(aPOnE2) > Precision::Intersection())
373               // No intersection point
374               continue;
375
376             // Real intersection is present.
377             // Update the existing vertex to cover the intersection point.
378             for (j = 0; j < 4; ++j)
379             {
380               if (bIsOnPave[j])
381               {
382                 const TopoDS_Vertex& aV = TopoDS::Vertex(myDS->Shape(nV[j]));
383                 const gp_Pnt aP = BRep_Tool::Pnt(aV);
384                 Standard_Real aDistPP = aP.Distance(aPnew);
385                 // Just update the vertex
386                 UpdateVertex(nV[j], aDistPP);
387                 myVertsToAvoidExtension.Add(nV[j]);
388               }
389             }
390           }
391
392           Standard_Real aTolVnew = BRep_Tool::Tolerance(aVnew);
393           if (bAnalytical) {
394             // increase tolerance for Line/Line intersection, but do not update 
395             // the vertex till its intersection with some other shape
396             Standard_Real aTolMin = (BRepAdaptor_Curve(aE1).GetType() == GeomAbs_Line) ?
397               (aCR1.Last() - aCR1.First()) / 2. : (aCR2.Last() - aCR2.First()) / 2.;
398             if (aTolMin > aTolVnew) {
399               aTolVnew = aTolMin;
400             }
401           }
402           // <-LXBR
403           {
404             Standard_Integer nVS[2], iFound;
405             Standard_Real aTolVx, aD2, aDT2;
406             TColStd_MapOfInteger aMV;
407             gp_Pnt aPx;
408             //
409             iFound=0;
410             j=-1;
411             aMV.Add(nV[0]);
412             aMV.Add(nV[1]);
413             //
414             if (aMV.Contains(nV[2])) {
415               ++j;
416               nVS[j]=nV[2];
417             }
418             if (aMV.Contains(nV[3])) {
419               ++j;
420               nVS[j]=nV[3];
421             }
422             //
423             for (Standard_Integer k1=0; k1<=j; ++k1) {
424               const TopoDS_Vertex& aVx= *(TopoDS_Vertex*)&(myDS->Shape(nVS[k1]));
425               aTolVx=BRep_Tool::Tolerance(aVx);
426               aPx=BRep_Tool::Pnt(aVx);
427               aD2=aPnew.SquareDistance(aPx);
428               //
429               aDT2=100.*(aTolVnew+aTolVx)*(aTolVnew+aTolVx);
430               //
431               if (aD2<aDT2) {
432                 iFound=1;
433                 break;
434               }
435             }
436             //
437             if (iFound) {
438               continue;
439             }
440           }
441           //
442           // 1
443           BOPDS_InterfEE& aEE=aEEs.Appended();
444           iX=aEEs.Length()-1;
445           aEE.SetIndices(nE1, nE2);
446           aEE.SetCommonPart(aCPart);
447           // 2
448           myDS->AddInterf(nE1, nE2);
449           //
450           BOPDS_CoupleOfPaveBlocks aCPB;
451           //
452           aCPB.SetPaveBlocks(aPB1, aPB2);
453           aCPB.SetIndexInterf(iX);
454           aCPB.SetTolerance(aTolVnew);
455           aMVCPB.Add(aVnew, aCPB);
456         }//case TopAbs_VERTEX: 
457           break;
458             //
459         case TopAbs_EDGE: {
460           if (aNbCPrts > 1) {
461             break;
462           }
463           //
464           Standard_Boolean bHasSameBounds;
465           bHasSameBounds=aPB1->HasSameBounds(aPB2);
466           if (!bHasSameBounds) {
467             break;
468           }
469           // 1
470           BOPDS_InterfEE& aEE=aEEs.Appended();
471           iX=aEEs.Length()-1;
472           aEE.SetIndices(nE1, nE2);
473           aEE.SetCommonPart(aCPart);
474           // 2
475           myDS->AddInterf(nE1, nE2);
476           //
477           BOPAlgo_Tools::FillMap<Handle(BOPDS_PaveBlock), TColStd_MapTransientHasher>(aPB1, aPB2, aMPBLPB, aAllocator);
478         }//case TopAbs_EDGE
479           break;
480         default:
481           break;
482       }//switch (aType) {
483     }//for (i=1; i<=aNbCPrts; i++) {
484   }//for (k=0; k < aNbFdgeEdge; ++k) {
485   // 
486   //=========================================
487   // post treatment
488   //=========================================
489   BOPAlgo_Tools::PerformCommonBlocks(aMPBLPB, aAllocator, myDS, myContext);
490   // Update vertices of common blocks with real CB tolerances
491   UpdateVerticesOfCB();
492
493   PerformNewVertices(aMVCPB, aAllocator);
494   //
495   if (aMEdges.Extent()) {
496     Standard_Integer aNbV = aMVCPB.Extent();
497     for (i = 1; i <= aNbV; ++i) {
498       Handle(BOPDS_PaveBlock) aPB1, aPB2;
499       const BOPDS_CoupleOfPaveBlocks& aCPB = aMVCPB.FindFromIndex(i);
500       aCPB.PaveBlocks(aPB1, aPB2);
501       //
502       aMEdges.Remove(aPB1->OriginalEdge());
503       aMEdges.Remove(aPB2->OriginalEdge());
504     }
505     //
506     SplitPaveBlocks(aMEdges, Standard_False);
507   }
508   //
509   //-----------------------------------------------------scope t
510   aMPBLPB.Clear();
511   aMVCPB.Clear();
512 }
513 //=======================================================================
514 //function : PerformVerticesEE
515 //purpose  : 
516 //=======================================================================
517 void BOPAlgo_PaveFiller::PerformNewVertices
518   (BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks& theMVCPB,
519    const Handle(NCollection_BaseAllocator)& theAllocator,
520    const Standard_Boolean bIsEEIntersection)
521 {
522   Standard_Integer aNbV = theMVCPB.Extent();
523   if (!aNbV) {
524     return;
525   }
526   //
527   Standard_Real aTolAdd = myFuzzyValue / 2.;
528   //
529   // 1. Fuse the new vertices
530   TopTools_IndexedDataMapOfShapeListOfShape aImages;
531   TreatNewVertices(theMVCPB, aImages);
532   //
533   // 2. Add new vertices to myDS and connect indices to CPB structure
534   BOPDS_VectorOfInterfEE& aEEs = myDS->InterfEE();
535   BOPDS_VectorOfInterfEF& aEFs = myDS->InterfEF();
536   //
537   Standard_Integer i, aNb = aImages.Extent();
538   for (i = 1; i <= aNb; ++i) {
539     const TopoDS_Vertex& aV = TopoDS::Vertex(aImages.FindKey(i));
540     const TopTools_ListOfShape& aLVSD = aImages.FindFromIndex(i);
541     //
542     BOPDS_ShapeInfo aSI;
543     aSI.SetShapeType(TopAbs_VERTEX);
544     aSI.SetShape(aV);
545     Standard_Integer iV = myDS->Append(aSI);
546     //
547     BOPDS_ShapeInfo& aSIDS = myDS->ChangeShapeInfo(iV);
548     Bnd_Box& aBox = aSIDS.ChangeBox();
549     aBox.Add(BRep_Tool::Pnt(aV));
550     aBox.SetGap(BRep_Tool::Tolerance(aV) + aTolAdd);
551     //
552     TopTools_ListIteratorOfListOfShape aItLS(aLVSD);
553     for (; aItLS.More(); aItLS.Next()) {
554       const TopoDS_Shape& aVx = aItLS.Value();
555       BOPDS_CoupleOfPaveBlocks &aCPB = theMVCPB.ChangeFromKey(aVx);
556       aCPB.SetIndex(iV);
557       // update interference
558       Standard_Integer iX = aCPB.IndexInterf();
559       BOPDS_Interf *aInt = bIsEEIntersection ? (BOPDS_Interf*)(&aEEs(iX)) : (BOPDS_Interf*) (&aEFs(iX));
560       aInt->SetIndexNew(iV);
561     }
562   }
563   //
564   // 3. Map PaveBlock/ListOfVertices to add to this PaveBlock ->aMPBLI
565   BOPDS_IndexedDataMapOfPaveBlockListOfInteger aMPBLI(100, theAllocator);
566   for (i = 1; i <= aNbV; ++i) {
567     const BOPDS_CoupleOfPaveBlocks& aCPB = theMVCPB.FindFromIndex(i);
568     Standard_Integer iV = aCPB.Index();
569     //
570     Handle(BOPDS_PaveBlock) aPB[2];
571     aCPB.PaveBlocks(aPB[0], aPB[1]);
572     for (Standard_Integer j = 0; j < 2; ++j) {
573       TColStd_ListOfInteger *pLI = aMPBLI.ChangeSeek(aPB[j]);
574       if (!pLI) {
575         pLI = &aMPBLI(aMPBLI.Add(aPB[j], TColStd_ListOfInteger(theAllocator)));
576       }
577       pLI->Append(iV);
578       //
579       if (aPB[0] == aPB[1]) {
580         break;
581       }
582     }
583   }
584   //
585   // 4. Compute Extra Paves and split Pave blocks by the Extra paves
586   IntersectVE(aMPBLI, Standard_False);
587 }
588 //=======================================================================
589 //function : TreatNewVertices
590 //purpose  : 
591 //=======================================================================
592 void BOPAlgo_PaveFiller::TreatNewVertices
593   (const BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks& theMVCPB,
594    TopTools_IndexedDataMapOfShapeListOfShape& myImages)
595 {
596   //
597   // Prepare for intersection
598   TopTools_IndexedDataMapOfShapeReal aVerts;
599   Standard_Integer i, aNbV = theMVCPB.Extent();
600   for (i = 1; i <= aNbV; ++i) {
601     const TopoDS_Shape& aV = theMVCPB.FindKey(i);
602     Standard_Real aTol = theMVCPB.FindFromIndex(i).Tolerance();
603     aVerts.Add(aV, aTol);
604   }
605   //
606   // Perform intersection
607   TopTools_ListOfListOfShape aChains;
608   BOPAlgo_Tools::IntersectVertices(aVerts, myRunParallel, myFuzzyValue, aChains);
609   //
610   // Treat the results - make new vertices for each chain
611   TopTools_ListOfListOfShape::Iterator aItC(aChains);
612   for (; aItC.More(); aItC.Next()) {
613     const TopTools_ListOfShape& aLVSD = aItC.Value();
614     //
615     TopoDS_Vertex aVNew;
616     BOPTools_AlgoTools::MakeVertex(aLVSD, aVNew);
617     myImages.Add(aVNew, aLVSD);
618   }
619 }
620 //=======================================================================
621 //function : FillShrunkData
622 //purpose  : 
623 //=======================================================================
624 void BOPAlgo_PaveFiller::FillShrunkData(Handle(BOPDS_PaveBlock)& thePB)
625 {
626   // Vertices
627   Standard_Integer nV1, nV2;
628   thePB->Indices(nV1, nV2);
629   const TopoDS_Vertex& aV1=(*(TopoDS_Vertex *)(&myDS->Shape(nV1))); 
630   const TopoDS_Vertex& aV2=(*(TopoDS_Vertex *)(&myDS->Shape(nV2))); 
631   // Get the edge
632   Standard_Integer nE = -1;
633   if (!thePB->HasEdge(nE))
634   {
635     nE = thePB->OriginalEdge();
636     if (nE < 0)
637       return;
638   }
639
640   const TopoDS_Edge& aE=(*(TopoDS_Edge *)(&myDS->Shape(nE))); 
641   // Range
642   Standard_Real aT1, aT2;
643   thePB->Range(aT1, aT2);
644   //
645   IntTools_ShrunkRange aSR;
646   aSR.SetContext(myContext);
647   aSR.SetData(aE, aT1, aT2, aV1, aV2);
648   aSR.Perform();
649   // Analyze the results of computations
650   AnalyzeShrunkData(thePB, aSR);
651 }
652 //=======================================================================
653 // function: AnalyzeShrunkData
654 // purpose: 
655 //=======================================================================
656 void BOPAlgo_PaveFiller::AnalyzeShrunkData(const Handle(BOPDS_PaveBlock)& thePB,
657                                            const IntTools_ShrunkRange& theSR)
658 {
659   // in case of error treat the warning status
660   Standard_Boolean bWholeEdge = Standard_False;
661   TopoDS_Shape aWarnShape;
662   //
663   if (!theSR.IsDone() || !theSR.IsSplittable()) {
664     Standard_Real aEFirst, aELast, aPBFirst, aPBLast;
665     BRep_Tool::Range(theSR.Edge(), aEFirst, aELast);
666     thePB->Range(aPBFirst, aPBLast);
667     bWholeEdge = !(aPBFirst > aEFirst || aPBLast < aELast);
668     if (bWholeEdge && thePB->OriginalEdge() >= 0) {
669       aWarnShape = theSR.Edge();
670     }
671     else {
672       const TopoDS_Shape& aV1 = myDS->Shape(thePB->Pave1().Index());
673       const TopoDS_Shape& aV2 = myDS->Shape(thePB->Pave2().Index());
674       BRep_Builder().MakeCompound(TopoDS::Compound(aWarnShape));
675       BRep_Builder().Add(aWarnShape, theSR.Edge());
676       BRep_Builder().Add(aWarnShape, aV1);
677       BRep_Builder().Add(aWarnShape, aV2);
678     }
679     //
680     if (!theSR.IsDone()) {
681       if (bWholeEdge)
682         AddWarning (new BOPAlgo_AlertTooSmallEdge (aWarnShape));
683       else
684         AddWarning (new BOPAlgo_AlertBadPositioning (aWarnShape));
685       Standard_Real aTS1, aTS2;
686       theSR.ShrunkRange(aTS1, aTS2);
687       thePB->SetShrunkData(aTS1, aTS2, Bnd_Box(), Standard_False);
688       return;
689     }
690     //
691     if (bWholeEdge)
692       AddWarning (new BOPAlgo_AlertNotSplittableEdge (aWarnShape));
693     else
694       AddWarning (new BOPAlgo_AlertBadPositioning (aWarnShape));
695   }
696   //
697   Standard_Real aTS1, aTS2;
698   theSR.ShrunkRange(aTS1, aTS2);
699   Bnd_Box aBox = theSR.BndBox();
700   aBox.SetGap(aBox.GetGap() + myFuzzyValue / 2.);
701   thePB->SetShrunkData(aTS1, aTS2, aBox, theSR.IsSplittable());
702 }
703 //=======================================================================
704 //function : ForceInterfVE
705 //purpose  : 
706 //=======================================================================
707 Standard_Boolean BOPAlgo_PaveFiller::ForceInterfVE(const Standard_Integer nV,
708                                                    Handle(BOPDS_PaveBlock)& aPB,
709                                                    TColStd_MapOfInteger& theMEdges)
710 {
711   Standard_Integer nE, nVx, nVSD, iFlag;
712   Standard_Real aT, aTolVNew;
713   //
714   nE = aPB->OriginalEdge();
715   //
716   const BOPDS_ShapeInfo& aSIE=myDS->ShapeInfo(nE);
717   if (aSIE.HasSubShape(nV)) {
718     return Standard_True;
719   }
720   //
721   if (myDS->HasInterf(nV, nE)) {
722     return Standard_True;
723   }
724   //
725   if (myDS->HasInterfShapeSubShapes(nV, nE)) {
726     return Standard_True;
727   }
728   //
729   if (aPB->Pave1().Index() == nV || 
730       aPB->Pave2().Index() == nV) {
731     return Standard_True;
732   }
733   //
734   nVx = nV;
735   if (myDS->HasShapeSD(nV, nVSD)) {
736     nVx = nVSD;
737   }
738   //
739   const TopoDS_Vertex& aV = *(TopoDS_Vertex*)&myDS->Shape(nVx);
740   const TopoDS_Edge&   aE = *(TopoDS_Edge*)  &myDS->Shape(nE);
741   //
742   iFlag = myContext->ComputeVE(aV, aE, aT, aTolVNew, myFuzzyValue);
743   if (iFlag == 0 || iFlag == -4) {
744     BOPDS_Pave aPave;
745     //
746     //
747     BOPDS_VectorOfInterfVE& aVEs=myDS->InterfVE();
748     aVEs.SetIncrement(10);
749     // 1
750     BOPDS_InterfVE& aVE=aVEs.Appended();
751     aVE.SetIndices(nV, nE);
752     aVE.SetParameter(aT);
753     // 2
754     myDS->AddInterf(nV, nE);
755     //
756     // 3 update vertex V/E if necessary
757     nVx=UpdateVertex(nV, aTolVNew);
758     // 4
759     if (myDS->IsNewShape(nVx)) {
760       aVE.SetIndexNew(nVx);
761     }
762     // 5 append ext pave to pave block
763     aPave.SetIndex(nVx);
764     aPave.SetParameter(aT);
765     aPB->AppendExtPave(aPave);
766     //
767     theMEdges.Add(nE);
768     //
769     // check for self-interference
770     Standard_Integer iRV = myDS->Rank(nV);
771     if (iRV >= 0 && iRV == myDS->Rank(nE)) {
772       // add warning status
773       TopoDS_Compound aWC;
774       BRep_Builder().MakeCompound(aWC);
775       BRep_Builder().Add(aWC, aV);
776       BRep_Builder().Add(aWC, aE);
777       AddWarning (new BOPAlgo_AlertSelfInterferingShape (aWC));
778     }
779     return Standard_True;
780   }
781   return Standard_False;
782 }
783
784 //=======================================================================
785 //function : GetPBBox
786 //purpose  : 
787 //=======================================================================
788 Standard_Boolean BOPAlgo_PaveFiller::GetPBBox(const TopoDS_Edge& theE,
789                                               const Handle(BOPDS_PaveBlock)& thePB,
790                                               BOPAlgo_DataMapOfPaveBlockBndBox& thePBBox,
791                                               Standard_Real& theFirst,
792                                               Standard_Real& theLast,
793                                               Standard_Real& theSFirst,
794                                               Standard_Real& theSLast,
795                                               Bnd_Box& theBox)
796 {
797   thePB->Range(theFirst, theLast);
798   // check the validity of PB's range
799   Standard_Boolean bValid = theLast - theFirst > Precision::PConfusion();
800   if (!bValid) {
801     return bValid;
802   }
803   //
804   // check shrunk data
805   if (thePB->HasShrunkData()) {
806     Standard_Boolean bIsSplittable;
807     thePB->ShrunkData(theSFirst, theSLast, theBox, bIsSplittable);
808     return bValid;
809   }
810   //
811   theSFirst = theFirst;
812   theSLast = theLast;
813   // check the map
814   if (thePBBox.IsBound(thePB)) {
815     theBox = thePBBox.Find(thePB);
816   }
817   else {
818     // build bounding box
819     BRepAdaptor_Curve aBAC(theE);
820     Standard_Real aTol = BRep_Tool::Tolerance(theE) + Precision::Confusion();
821     BndLib_Add3dCurve::Add(aBAC, theSFirst, theSLast, aTol, theBox);
822     thePBBox.Bind(thePB, theBox);
823   }
824   return bValid;
825 }
826
827 //=======================================================================
828 //function : UpdateVerticesOfCB
829 //purpose  : 
830 //=======================================================================
831 void BOPAlgo_PaveFiller::UpdateVerticesOfCB()
832 {
833   // Fence map to avoid checking same Common block twice
834   BOPDS_MapOfPaveBlock aMPBFence;
835
836   BOPDS_VectorOfListOfPaveBlock& aPBP = myDS->ChangePaveBlocksPool();
837   const Standard_Integer aNbPBP = aPBP.Length();
838   for (Standard_Integer i = 0; i < aNbPBP; ++i)
839   {
840     const BOPDS_ListOfPaveBlock& aLPB = aPBP(i);
841     BOPDS_ListIteratorOfListOfPaveBlock itPB(aLPB);
842     for (; itPB.More(); itPB.Next())
843     {
844       const Handle(BOPDS_CommonBlock)& aCB = myDS->CommonBlock(itPB.Value());
845       if (aCB.IsNull())
846         continue;
847
848       const Handle(BOPDS_PaveBlock)& aPBR = aCB->PaveBlock1();
849       if (!aMPBFence.Add(aPBR))
850         continue;
851
852       Standard_Real aTolCB = aCB->Tolerance();
853       if (aTolCB > 0.)
854       {
855         UpdateVertex(aPBR->Pave1().Index(), aTolCB);
856         UpdateVertex(aPBR->Pave2().Index(), aTolCB);
857       }
858     }
859   }
860 }
861
862 //=======================================================================
863 //function : ForceInterfEE
864 //purpose  : 
865 //=======================================================================
866 void BOPAlgo_PaveFiller::ForceInterfEE()
867 {
868   // Now that we have vertices increased and unified, try to find additional
869   // common blocks among the pairs of edges.
870   // Since all real intersections should have already happened, here we
871   // are interested in common blocks only, thus we need to check only
872   // those pairs of pave blocks with the same bounding vertices.
873
874   Handle(NCollection_IncAllocator) anAlloc = new NCollection_IncAllocator;
875
876   // Initialize pave blocks for all vertices which participated in intersections
877   const Standard_Integer aNbS = myDS->NbSourceShapes();
878   for (Standard_Integer i = 0; i < aNbS; ++i)
879   {
880     const BOPDS_ShapeInfo& aSI = myDS->ShapeInfo(i);
881     if (aSI.ShapeType() == TopAbs_VERTEX)
882     {
883       if (myDS->HasInterf(i))
884         myDS->InitPaveBlocksForVertex(i);
885     }
886   }
887
888   // Fill the connection map from bounding vertices to pave blocks
889   // having those bounding vertices
890   NCollection_IndexedDataMap<BOPDS_Pair,
891                              BOPDS_ListOfPaveBlock,
892                              BOPDS_PairMapHasher> aPBMap(1, anAlloc);
893   // Fence map of pave blocks
894   BOPDS_MapOfPaveBlock aMPBFence(1, anAlloc);
895
896   for (Standard_Integer i = 0; i < aNbS; ++i)
897   {
898     const BOPDS_ShapeInfo& aSI = myDS->ShapeInfo(i);
899     if (aSI.ShapeType() != TopAbs_EDGE)
900       // Not an edge
901       continue;
902
903     if (!aSI.HasReference())
904       // Edge has no pave blocks
905       continue;
906
907     if (aSI.HasFlag())
908       // Degenerated edge
909       continue;
910
911     const BOPDS_ListOfPaveBlock& aLPB = myDS->PaveBlocks(i);
912     BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPB);
913     for (; aItLPB.More(); aItLPB.Next())
914     {
915       const Handle(BOPDS_PaveBlock)& aPB = aItLPB.Value();
916       const Handle(BOPDS_PaveBlock)& aPBR = myDS->RealPaveBlock(aPB);
917       if (!aMPBFence.Add(aPBR))
918         continue;
919
920       // Get indices
921       Standard_Integer nV1, nV2;
922       aPBR->Indices(nV1, nV2);
923
924       // Add pave block to a map
925       BOPDS_Pair aPair(nV1, nV2);
926       BOPDS_ListOfPaveBlock *pList = aPBMap.ChangeSeek(aPair);
927       if (!pList)
928         pList = &aPBMap(aPBMap.Add(aPair, BOPDS_ListOfPaveBlock(anAlloc)));
929       pList->Append(aPBR);
930     }
931   }
932
933   Standard_Integer aNbPB = aPBMap.Extent();
934   if (!aNbPB)
935     return;
936
937   // Prepare pave blocks with the same vertices for intersection.
938   BOPAlgo_VectorOfEdgeEdge aVEdgeEdge;
939
940   for (Standard_Integer i = 1; i <= aNbPB; ++i)
941   {
942     const BOPDS_ListOfPaveBlock& aLPB = aPBMap(i);
943     if (aLPB.Extent() < 2)
944       continue;
945
946     const BOPDS_Pair& aPair = aPBMap.FindKey(i);
947     Standard_Integer nV1, nV2;
948     aPair.Indices(nV1, nV2);
949
950     const TopoDS_Vertex& aV1 = TopoDS::Vertex(myDS->Shape(nV1));
951     const TopoDS_Vertex& aV2 = TopoDS::Vertex(myDS->Shape(nV2));
952
953     // Use the max tolerance of vertices as Fuzzy value for intersection
954     // of edges
955     Standard_Real aTolAdd = 2 * Max(BRep_Tool::Tolerance(aV1),
956                                     BRep_Tool::Tolerance(aV2));
957
958     // All possible pairs combined from the list <aLPB> should be checked
959     BOPDS_ListIteratorOfListOfPaveBlock aItLPB1(aLPB);
960     for (; aItLPB1.More(); aItLPB1.Next())
961     {
962       const Handle(BOPDS_PaveBlock)& aPB1 = aItLPB1.Value();
963       const Handle(BOPDS_CommonBlock)& aCB1 = myDS->CommonBlock(aPB1);
964       const Standard_Integer nE1 = aPB1->OriginalEdge();
965       const Standard_Integer iR1 = myDS->Rank(nE1);
966       const TopoDS_Edge& aE1 = TopoDS::Edge(myDS->Shape(nE1));
967       Standard_Real aT11, aT12;
968       aPB1->Range(aT11, aT12);
969       BRepAdaptor_Curve aBAC1(aE1);
970       gp_Pnt aPm;
971       gp_Vec aVTgt1;
972       aBAC1.D1((aT11 + aT12) * 0.5, aPm, aVTgt1);
973       if (aVTgt1.SquareMagnitude() < gp::Resolution())
974         continue;
975
976       BOPDS_ListIteratorOfListOfPaveBlock aItLPB2 = aItLPB1;
977       for (aItLPB2.Next(); aItLPB2.More(); aItLPB2.Next())
978       {
979         const Handle(BOPDS_PaveBlock)& aPB2 = aItLPB2.Value();
980         const Handle(BOPDS_CommonBlock)& aCB2 = myDS->CommonBlock(aPB2);
981         const Standard_Integer nE2 = aPB2->OriginalEdge();
982         const Standard_Integer iR2 = myDS->Rank(nE2);
983
984         // Check that the edges came from different arguments
985         if (iR1 == iR2)
986         {
987           // If the sharing of the vertices is not original, but has been acquired
988           // during the operation, check the coincidence of the edges even if
989           // they came from the same argument
990           if ((!myDS->IsNewShape(nV1) && (myDS->Rank(nV1) == iR1)) ||
991               (!myDS->IsNewShape(nV2) && (myDS->Rank(nV2) == iR2)))
992             continue;
993         }
994
995         // Check that the Pave blocks do not form the Common block already
996         if (!aCB1.IsNull() && !aCB2.IsNull())
997         {
998           if (aCB1 == aCB2)
999             continue;
1000         }
1001
1002         const TopoDS_Edge& aE2 = TopoDS::Edge(myDS->Shape(nE2));
1003         Standard_Real aT21, aT22;
1004         aPB2->Range(aT21, aT22);
1005
1006         // Check the angle between edges in the middle point.
1007         // If the angle is more than 10 degrees, do not use the additional
1008         // tolerance, as it may lead to undesired unification of edges
1009         Standard_Boolean bUseAddTol = Standard_True;
1010         {
1011           GeomAPI_ProjectPointOnCurve& aProjPC = myContext->ProjPC(aE2);
1012           aProjPC.Perform(aPm);
1013           if (!aProjPC.NbPoints())
1014             continue;
1015
1016           BRepAdaptor_Curve aBAC2(aE2);
1017           gp_Pnt aPm2;
1018           gp_Vec aVTgt2;
1019           aBAC2.D1(aProjPC.LowerDistanceParameter(), aPm2, aVTgt2);
1020           if (aVTgt2.SquareMagnitude() < gp::Resolution())
1021             continue;
1022           // The angle should be close to zero
1023           Standard_Real aCos = aVTgt1.Dot(aVTgt2);
1024           if (Abs(aCos) < 0.984)
1025             bUseAddTol = Standard_False;
1026         }
1027
1028         // Add pair for intersection
1029         BOPAlgo_EdgeEdge& anEdgeEdge = aVEdgeEdge.Appended();
1030         anEdgeEdge.UseQuickCoincidenceCheck(Standard_True);
1031         anEdgeEdge.SetPaveBlock1(aPB1);
1032         anEdgeEdge.SetPaveBlock2(aPB2);
1033         anEdgeEdge.SetEdge1(aE1, aT11, aT12);
1034         anEdgeEdge.SetEdge2(aE2, aT21, aT22);
1035         if (bUseAddTol)
1036           anEdgeEdge.SetFuzzyValue(myFuzzyValue + aTolAdd);
1037         else
1038           anEdgeEdge.SetFuzzyValue(myFuzzyValue);
1039         anEdgeEdge.SetProgressIndicator(myProgressIndicator);
1040       }
1041     }
1042   }
1043
1044   Standard_Integer aNbPairs = aVEdgeEdge.Length();
1045   if (!aNbPairs)
1046     return;
1047
1048   aPBMap.Clear();
1049   aMPBFence.Clear();
1050   anAlloc->Reset();
1051
1052   // Perform intersection of the found pairs
1053   BOPAlgo_EdgeEdgeCnt::Perform(myRunParallel, aVEdgeEdge);
1054
1055   BOPDS_VectorOfInterfEE& aEEs = myDS->InterfEE();
1056   if (aEEs.IsEmpty())
1057     aEEs.SetIncrement(10);
1058
1059   // Analyze the results of intersection looking for TopAbs_EDGE
1060   // intersection type only.
1061
1062   BOPDS_IndexedDataMapOfPaveBlockListOfPaveBlock aMPBLPB(1, anAlloc);
1063
1064   for (Standard_Integer i = 0; i < aNbPairs; ++i)
1065   {
1066     BOPAlgo_EdgeEdge& anEdgeEdge = aVEdgeEdge(i);
1067     if (!anEdgeEdge.IsDone() || anEdgeEdge.HasErrors())
1068     {
1069       // Warn about failed intersection of sub-shapes
1070       const TopoDS_Shape& aE1 = myDS->Shape(anEdgeEdge.PaveBlock1()->OriginalEdge());
1071       const TopoDS_Shape& aE2 = myDS->Shape(anEdgeEdge.PaveBlock2()->OriginalEdge());
1072       AddIntersectionFailedWarning(aE1, aE2);
1073       continue;
1074     }
1075
1076     const IntTools_SequenceOfCommonPrts& aCParts = anEdgeEdge.CommonParts();
1077     if (aCParts.Length() != 1)
1078       continue;
1079
1080     const IntTools_CommonPrt& aCP = aCParts(1);
1081     if (aCP.Type() != TopAbs_EDGE)
1082       continue;
1083
1084     Handle(BOPDS_PaveBlock) aPB[] = {anEdgeEdge.PaveBlock1(), anEdgeEdge.PaveBlock2()};
1085     const Standard_Integer nE1 = aPB[0]->OriginalEdge();
1086     const Standard_Integer nE2 = aPB[1]->OriginalEdge();
1087
1088     if (myDS->Rank(nE1) == myDS->Rank(nE2))
1089     {
1090       // Add acquired self-interference warning
1091       TopoDS_Compound aWC;
1092       BRep_Builder().MakeCompound(aWC);
1093       BRep_Builder().Add(aWC, myDS->Shape(nE1));
1094       BRep_Builder().Add(aWC, myDS->Shape(nE2));
1095       AddWarning(new BOPAlgo_AlertAcquiredSelfIntersection(aWC));
1096     }
1097
1098     BOPDS_InterfEE& aEE = aEEs.Appended();
1099     aEE.SetIndices(nE1, nE2);
1100     aEE.SetCommonPart(aCP);
1101     myDS->AddInterf(nE1, nE2);
1102
1103     // Fill map for common blocks creation
1104     for (Standard_Integer j = 0; j < 2; ++j)
1105     {
1106       if (myDS->IsCommonBlock(aPB[j]))
1107       {
1108         const BOPDS_ListOfPaveBlock& aLPBCB = myDS->CommonBlock(aPB[j])->PaveBlocks();
1109         BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPBCB);
1110         for (; aItLPB.More(); aItLPB.Next())
1111           BOPAlgo_Tools::FillMap<Handle(BOPDS_PaveBlock),
1112                            TColStd_MapTransientHasher>(aPB[j], aItLPB.Value(), aMPBLPB, anAlloc);
1113       }
1114     }
1115     BOPAlgo_Tools::FillMap<Handle(BOPDS_PaveBlock),
1116                            TColStd_MapTransientHasher>(aPB[0], aPB[1], aMPBLPB, anAlloc);
1117   }
1118
1119   // Create new common blocks of coinciding pairs.
1120   BOPAlgo_Tools::PerformCommonBlocks(aMPBLPB, anAlloc, myDS);
1121 }