]> SALOME platform Git repositories - modules/geom.git/blob - src/NMTTools/NMTTools_PaveFiller_4.cxx
Salome HOME
Additional fix for bug NPAL19028 (see remarks from Olivier Giorgis).
[modules/geom.git] / src / NMTTools / NMTTools_PaveFiller_4.cxx
1 // Copyright (C) 2005  OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN,
2 // CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
3 // 
4 // This library is free software; you can redistribute it and/or
5 // modify it under the terms of the GNU Lesser General Public
6 // License as published by the Free Software Foundation; either 
7 // version 2.1 of the License.
8 // 
9 // This library is distributed in the hope that it will be useful 
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of 
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU 
12 // Lesser General Public License for more details.
13 //
14 // You should have received a copy of the GNU Lesser General Public  
15 // License along with this library; if not, write to the Free Software 
16 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
17 //
18 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
19 //
20 // File:        NMTTools_PaveFiller_4.cxx
21 // Created:     Mon Dec  8 17:08:58 2003
22 // Author:      Peter KURNEV
23 //              <pkv@irinox>
24
25
26 #include <NMTTools_PaveFiller.ixx>
27 //
28 #include <stdio.h>
29 #include <Precision.hxx>
30
31 #include <gp_XYZ.hxx>
32 #include <gp_Pnt.hxx>
33 #include <Bnd_Box.hxx>
34
35 #include <TColStd_MapOfInteger.hxx>
36 #include <TColStd_IndexedMapOfInteger.hxx>
37 #include <TColStd_ListIteratorOfListOfInteger.hxx>
38 #include <TColStd_MapIteratorOfMapOfInteger.hxx>
39
40 #include <TopoDS.hxx>
41 #include <TopoDS_Edge.hxx>
42 #include <TopoDS_Vertex.hxx>
43 #include <TopoDS_Compound.hxx>
44
45 #include <TopTools_IndexedMapOfShape.hxx>
46 #include <TopTools_ListIteratorOfListOfShape.hxx>
47 #include <TopTools_DataMapIteratorOfDataMapOfShapeListOfShape.hxx>
48 #include <TopTools_DataMapOfShapeListOfShape.hxx>
49 #include <TopTools_ListOfShape.hxx>
50 #include <TopTools_DataMapOfShapeShape.hxx>
51
52 #include <BRep_Tool.hxx>
53 #include <BRep_Builder.hxx>
54 #include <BRepBndLib.hxx>
55
56 #include <BOPTColStd_Dump.hxx>
57 #include <BOPTColStd_Failure.hxx>
58
59 #include <IntTools_ShrunkRange.hxx>
60 #include <IntTools_Range.hxx>
61 #include <IntTools_CommonPrt.hxx>
62 #include <IntTools_SequenceOfRanges.hxx>
63 #include <IntTools_EdgeEdge.hxx>
64 #include <IntTools_SequenceOfCommonPrts.hxx>
65
66 #include <BOPTools_Pave.hxx>
67 #include <BOPTools_PaveSet.hxx>
68 #include <BOPTools_PaveBlockIterator.hxx>
69 #include <BOPTools_PaveBlock.hxx>
70 #include <BOPTools_CArray1OfEEInterference.hxx>
71 #include <BOPTools_EEInterference.hxx>
72 #include <BOPTools_ListOfPaveBlock.hxx>
73 #include <BOPTools_ListIteratorOfListOfPaveBlock.hxx>
74 #include <BOPTools_CArray1OfVVInterference.hxx>
75 #include <BOPTools_VVInterference.hxx>
76 #include <BOPTools_CArray1OfEEInterference.hxx>
77 #include <BOPTools_Tools.hxx>
78 #include <BOPTools_IDMapOfPaveBlockIMapOfPaveBlock.hxx>
79 #include <BOPTools_IMapOfPaveBlock.hxx>
80 #include <BOPTools_ListIteratorOfListOfPave.hxx>
81 #include <BOPTools_SequenceOfPaveBlock.hxx>
82
83 #include <BooleanOperations_AncestorsSeqAndSuccessorsSeq.hxx>
84 #include <BooleanOperations_IndexedDataMapOfShapeInteger.hxx>
85 #include <BooleanOperations_KindOfInterference.hxx>
86
87 #include <NMTDS_Iterator.hxx>
88 #include <NMTDS_ShapesDataStructure.hxx>
89 #include <NMTDS_IndexedDataMapOfIntegerShape.hxx>
90 #include <NMTDS_IndexedDataMapOfShapeBox.hxx>
91 #include <NMTDS_BoxBndTree.hxx>
92 #include <NCollection_UBTreeFiller.hxx>
93 #include <NMTDS_InterfPool.hxx>
94
95 #include <NMTTools_IndexedDataMapOfIndexedMapOfInteger.hxx>
96 #include <NMTTools_ListOfCommonBlock.hxx>
97 #include <NMTTools_CommonBlock.hxx>
98 #include <NMTTools_ListIteratorOfListOfCommonBlock.hxx>
99
100 // Modified  Thu Sep 14 14:35:18 2006 
101 // Contribution of Samtech www.samcef.com BEGIN
102 #include <TColStd_ListOfInteger.hxx>
103 #include <TColStd_ListIteratorOfListOfInteger.hxx>
104 #include <BRepBndLib.hxx>
105 #include <BOPTools_CArray1OfVSInterference.hxx>
106 #include <BOPTools_VSInterference.hxx>
107 // Contribution of Samtech www.samcef.com END
108 //
109 //
110
111
112 static
113   void TreatNewVertices(const BooleanOperations_IndexedDataMapOfShapeInteger& aMapVI,
114                         TopTools_DataMapOfShapeListOfShape& myImages,
115                         TopTools_DataMapOfShapeShape& myOrigins);
116
117 static
118   void MakeNewVertex(const TopTools_ListOfShape& aLV, 
119                      TopoDS_Vertex& aNewVertex);
120
121
122 static 
123   void VertexParameters(const IntTools_CommonPrt& aCPart,
124                         Standard_Real& aT1, 
125                         Standard_Real& aT2);
126 static
127   Standard_Boolean IsOnPave(const Standard_Real& aT1,
128                             const IntTools_Range& aRange,
129                             const Standard_Real& aTolerance);
130 static
131   void EECommonBlocks(const BOPTools_IDMapOfPaveBlockIMapOfPaveBlock& aMapCB);
132
133 static
134   void ProcessBlock(const BOPTools_PaveBlock& aPB,
135                     const BOPTools_IDMapOfPaveBlockIMapOfPaveBlock& aMapCB,
136                     BOPTools_IMapOfPaveBlock& aProcessedBlocks,
137                     BOPTools_IMapOfPaveBlock& aChain);
138 static
139   void FindChains(const BOPTools_IDMapOfPaveBlockIMapOfPaveBlock& aMapCB,
140                   NMTTools_ListOfCommonBlock& aLCB);
141
142 //=======================================================================
143 // function: PerformEE
144 // purpose: 
145 //=======================================================================
146   void NMTTools_PaveFiller::PerformEE() 
147 {
148   myIsDone=Standard_False;
149   //
150   Standard_Boolean bJustAdd;
151   Standard_Integer n1, n2, anIndexIn, nE1, nE2, aNbVEs, aBlockLength;
152   Standard_Integer aTmp, aWhat, aWith, i, aNbCPrts, aDiscretize=30;
153   Standard_Integer aNbLPB1, aNbLPB2;
154   Standard_Real aTolE1, aTolE2, aDeflection=0.01;
155   BOPTools_ListIteratorOfListOfPaveBlock anIt1, anIt2;
156   TopoDS_Edge aEWhat, aEWith; 
157   TopoDS_Vertex aNewVertex;
158   BooleanOperations_IndexedDataMapOfShapeInteger aMapVI;
159   BOPTools_IDMapOfPaveBlockIMapOfPaveBlock aMapCB;
160   //
161   BOPTools_CArray1OfEEInterference& aEEs=myIP->EEInterferences();
162   //
163   myDSIt->Initialize(TopAbs_EDGE, TopAbs_EDGE);
164   //
165   // BlockLength correction
166   aNbVEs=myDSIt->BlockLength();
167   aBlockLength=aEEs.BlockLength();
168   if (aNbVEs > aBlockLength) {
169     aEEs.SetBlockLength(aNbVEs);
170   }
171   //
172   for (; myDSIt->More(); myDSIt->Next()) {
173     myDSIt->Current(n1, n2, bJustAdd);
174     anIndexIn = 0;
175     //
176     //if (myIntrPool->IsComputed(n1, n2)) {
177     //  continue;
178     //}
179     //
180     nE1=n1; 
181     nE2=n2; 
182     //
183     if(bJustAdd) {
184       //myIntrPool->AddInterference (nE1, nE2, BooleanOperations_EdgeEdge, anIndexIn);
185       continue;
186     }
187     //
188     const TopoDS_Edge aE1=TopoDS::Edge(myDS->Shape(nE1));//mpv
189     const TopoDS_Edge aE2=TopoDS::Edge(myDS->Shape(nE2));//mpv
190     
191     //
192     if (BRep_Tool::Degenerated(aE1) || BRep_Tool::Degenerated(aE2)){
193       continue;
194     }
195     //
196     aTolE1=BRep_Tool::Tolerance(aE1);
197     aTolE2=BRep_Tool::Tolerance(aE2);
198     //
199     BOPTools_ListOfPaveBlock& aLPB1=mySplitShapesPool(myDS->RefEdge(nE1));
200     BOPTools_ListOfPaveBlock& aLPB2=mySplitShapesPool(myDS->RefEdge(nE2));
201     //
202     // Modified  Thu Sep 14 14:35:18 2006 
203     // Contribution of Samtech www.samcef.com BEGIN
204     aNbLPB1=aLPB1.Extent();
205     aNbLPB2=aLPB2.Extent();
206     
207     //if (aE1.IsSame(aE2) && aNbLPB1==1 && aNbLPB2==1) { 
208     //  continue;
209     //}
210     // Contribution of Samtech www.samcef.com END
211     //
212     for (anIt1.Initialize(aLPB1); anIt1.More(); anIt1.Next()) {
213       BOPTools_PaveBlock& aPB1=anIt1.Value();
214       const IntTools_ShrunkRange& aShrunkRange1=aPB1.ShrunkRange();
215       //
216       const IntTools_Range& aSR1=aShrunkRange1.ShrunkRange();
217       const Bnd_Box&        aBB1=aShrunkRange1.BndBox();
218       //
219       for (anIt2.Initialize(aLPB2); anIt2.More(); anIt2.Next()) {
220         BOPTools_PaveBlock& aPB2=anIt2.Value();
221         const IntTools_ShrunkRange& aShrunkRange2=aPB2.ShrunkRange();
222       
223         const IntTools_Range& aSR2=aShrunkRange2.ShrunkRange();
224         const Bnd_Box&        aBB2=aShrunkRange2.BndBox();
225         //
226         if (aBB1.IsOut (aBB2)) {
227           continue;
228         }
229         // 
230         // EE
231         IntTools_EdgeEdge aEE;
232         aEE.SetEdge1 (aE1);
233         aEE.SetEdge2 (aE2);
234         aEE.SetTolerance1 (aTolE1);
235         aEE.SetTolerance2 (aTolE2);
236         aEE.SetDiscretize (aDiscretize);
237         aEE.SetDeflection (aDeflection);
238         //
239         IntTools_Range anewSR1 = aSR1;
240         IntTools_Range anewSR2 = aSR2;
241         //
242         BOPTools_Tools::CorrectRange (aE1, aE2, aSR1, anewSR1);
243         BOPTools_Tools::CorrectRange (aE2, aE1, aSR2, anewSR2);
244         //
245         aEE.SetRange1(anewSR1);
246         aEE.SetRange2(anewSR2);
247           
248         aEE.Perform();
249         //
250         anIndexIn=0;
251         //
252         if (aEE.IsDone()) {
253           // reverse order if it is necessary
254           aEWhat=aE1;
255           aEWith=aE2;
256           aWhat=nE1;
257           aWith=nE2;
258           if (aEE.Order()) {
259             aTmp=aWhat;
260             aWhat=aWith;
261             aWith=aTmp;
262             aEWhat=aE2;
263             aEWith=aE1;
264           }
265           //
266           const IntTools_SequenceOfCommonPrts& aCPrts=aEE.CommonParts();
267           aNbCPrts=aCPrts.Length();
268           for (i=1; i<=aNbCPrts; i++) {
269             const IntTools_CommonPrt& aCPart=aCPrts(i);
270             const IntTools_SequenceOfRanges& aRanges2=aCPart.Ranges2();
271             //
272             anIndexIn=0;
273             //
274             TopAbs_ShapeEnum aType=aCPart.Type();
275             switch (aType) {
276               case TopAbs_VERTEX:  {
277                 Standard_Real aT1, aT2, aTol=Precision::PConfusion();
278                 Standard_Boolean bIsOnPave1, bIsOnPave2;
279                 IntTools_Range aR1, aR2;
280                 //
281                 VertexParameters(aCPart, aT1, aT2);
282                 // 
283                 //decide to keep the pave or not
284                 aR1 = (aEE.Order()) ? anewSR2 : anewSR1;
285                 aR2 = (aEE.Order()) ? anewSR1 : anewSR2;
286                 //
287                 bIsOnPave1=IsOnPave(aT1, aR1, aTol);
288                 bIsOnPave2=IsOnPave(aT2, aR2, aTol);
289                 //
290                 if(bIsOnPave1 || bIsOnPave2) {
291                    continue;
292                 }
293                 //
294                 BOPTools_Tools::MakeNewVertex(aEWhat, aT1, aEWith, aT2, aNewVertex);
295                 //
296                 //modified by NIZNHY-PKV Mon Jun 19 11:40:09 2007f
297                 {
298                   Standard_Integer nV11, nV12, nV21, nV22, nVS[2], k, j, iFound;
299                   Standard_Real aTolVx, aTolVnew, aD2, aDT2;
300                   TColStd_MapOfInteger aMV;
301                   gp_Pnt aPnew, aPx;
302                   //
303                   iFound=0;
304                   j=-1;
305                   nV11=aPB1.Pave1().Index();
306                   nV12=aPB1.Pave2().Index();
307                   nV21=aPB2.Pave1().Index();
308                   nV22=aPB2.Pave2().Index();
309                   aMV.Add(nV11);
310                   aMV.Add(nV12);
311                   //
312                   if (aMV.Contains(nV21)) {
313                     ++j;
314                     nVS[j]=nV21;
315                   }
316                   if (aMV.Contains(nV22)) {
317                     ++j;
318                     nVS[j]=nV22;
319                   }
320                   //
321                   aTolVnew=BRep_Tool::Tolerance(aNewVertex);
322                   aPnew=BRep_Tool::Pnt(aNewVertex);
323                   //
324                   for (k=0; k<=j; ++k) {
325                     const TopoDS_Vertex& aVx=TopoDS::Vertex(myDS->Shape(nVS[k]));
326                     aTolVx=BRep_Tool::Tolerance(aVx);
327                     aPx=BRep_Tool::Pnt(aVx);
328                     aD2=aPnew.SquareDistance(aPx);
329                     //
330                     aDT2=100.*(aTolVnew+aTolVx)*(aTolVnew+aTolVx);
331                     //
332                     if (aD2<aDT2) {
333                       iFound=1;
334                       break;
335                     }
336                   }
337                   //
338                   if (iFound) {
339                     continue;
340                   }
341                 }
342                 //modified by NIZNHY-PKV Mon Jun 19 11:40:16 2007t
343                 //
344                 // Add Interference to the Pool
345                 BOPTools_EEInterference anInterf (aWhat, aWith, aCPart);
346                 //
347                 anIndexIn=aEEs.Append(anInterf);
348                 // qqf
349                 {
350                   myIP->Add(aWhat, aWith, Standard_True, NMTDS_TI_EE);
351                 }
352                 // qqt
353                 //
354                 // Collect
355                 aMapVI.Add(aNewVertex, anIndexIn);
356               }
357                 break;
358                 
359               case TopAbs_EDGE: {
360                 Standard_Integer aNbComPrt2;
361                 Standard_Boolean aCoinsideFlag;
362                 //
363                 aNbComPrt2=aRanges2.Length();
364                 aCoinsideFlag=IsBlocksCoinside(aPB1, aPB2);
365                 //
366                 if (aNbComPrt2>1 || !aCoinsideFlag) {
367                   //myIntrPool->AddInterference (aWhat, aWith, BooleanOperations_EdgeEdge, anIndexIn);
368                   break;
369                 }
370                 //
371                 // Fill aMapCB
372                 if (aMapCB.Contains(aPB1)) {
373                   BOPTools_IMapOfPaveBlock& aMapPB=aMapCB.ChangeFromKey(aPB1);
374                   aMapPB.Add(aPB1); 
375                   aMapPB.Add(aPB2); 
376                 }
377                 else {
378                   BOPTools_IMapOfPaveBlock aMapPB;
379                   aMapPB.Add(aPB1); 
380                   aMapPB.Add(aPB2); 
381                   aMapCB.Add(aPB1, aMapPB);
382                 }
383                 //
384                 if (aMapCB.Contains(aPB2)) {
385                   BOPTools_IMapOfPaveBlock& aMapPB=aMapCB.ChangeFromKey(aPB2);
386                   aMapPB.Add(aPB1); 
387                   aMapPB.Add(aPB2); 
388                 }
389                 else {
390                   BOPTools_IMapOfPaveBlock aMapPB;
391                   aMapPB.Add(aPB1); 
392                   aMapPB.Add(aPB2); 
393                   aMapCB.Add(aPB2, aMapPB);
394                 }
395                 // qqf
396                 {
397                   myIP->Add(aWhat, aWith, Standard_True, NMTDS_TI_EE);
398                 }
399                 // qqt
400               }
401                 break;
402             default:
403               break;
404             } // switch (aType) 
405           } // for (i=1; i<=aNbCPrts; i++) 
406         }// if (aEE.IsDone())
407       } // for (; anIt2.More(); anIt2.Next()) 
408     } // for (; anIt1.More(); anIt1.Next()) 
409   }// for (; myDSIt.More(); myDSIt.Next()) 
410   //
411   EENewVertices (aMapVI);
412   EECommonBlocks(aMapCB);
413   // Modified to invoke new nethod Thu Sep 14 14:35:18 2006 
414   // Contribution of Samtech www.samcef.com BEGIN
415   PerformVF1();
416   // Contribution of Samtech www.samcef.com BEGIN
417   myIsDone=Standard_True;
418 }
419 //=======================================================================
420 // function:EECommonBlocks
421 // purpose: 
422 //=======================================================================
423   void NMTTools_PaveFiller::EECommonBlocks(const BOPTools_IDMapOfPaveBlockIMapOfPaveBlock& aMapCB)
424 {
425   NMTTools_ListOfCommonBlock aLCB;
426   //
427   FindChains(aMapCB, aLCB);
428   ReplaceCommonBlocks(aLCB);
429 }
430 //=======================================================================
431 // function:EENewVertices
432 // purpose: 
433 //=======================================================================
434   void NMTTools_PaveFiller::EENewVertices (const BooleanOperations_IndexedDataMapOfShapeInteger& aMapVI) 
435 {
436   Standard_Integer aNb, aNbVSD, nVnew, nIEE, nE[2], j, iFlag;
437   Standard_Real aT;
438   TopoDS_Edge aE; 
439   TopTools_DataMapOfShapeListOfShape myImages;
440   TopTools_DataMapOfShapeShape myOrigins;
441   TopTools_DataMapIteratorOfDataMapOfShapeListOfShape aItIm;
442   TopTools_ListIteratorOfListOfShape aIt;
443   BooleanOperations_AncestorsSeqAndSuccessorsSeq anASSeq;
444   TColStd_MapOfInteger aMFence;
445   BOPTools_Pave aPave;
446   //
447   BOPTools_CArray1OfEEInterference& aEEs=myIP->EEInterferences();
448   //
449   aNb=aMapVI.Extent();
450   if (!aNb) { // no new vertices, no new problems 
451     return;
452   }
453   //
454   // 0. 
455   if (aNb==1) {
456     TopoDS_Vertex aV1=TopoDS::Vertex(aMapVI.FindKey(1));
457     EENewVertices(aV1, aMapVI);
458     return;
459   }
460   //
461   // 1.
462   TreatNewVertices(aMapVI, myImages, myOrigins);
463   //
464   aItIm.Initialize(myImages);
465   for (; aItIm.More(); aItIm.Next()) {
466     const TopoDS_Vertex& aVnew=TopoDS::Vertex(aItIm.Key());
467     const TopTools_ListOfShape& aLVSD=aItIm.Value();
468     //
469     aNbVSD=aLVSD.Extent();
470     if (aNbVSD==1) {// simple case aVnew=aVold
471       EENewVertices(aVnew, aMapVI);
472       continue;
473     }
474     //
475     // aNbVSD>1
476     myDS->InsertShapeAndAncestorsSuccessors(aVnew, anASSeq);
477     nVnew=myDS->NumberOfInsertedShapes();
478     myDS->SetState(nVnew, BooleanOperations_ON);
479     //
480     aMFence.Clear();
481     aIt.Initialize(aLVSD);
482     for (; aIt.More(); aIt.Next()) {
483       const TopoDS_Vertex& aVold=TopoDS::Vertex(aIt.Value());
484       nIEE=aMapVI.FindFromKey(aVold);
485       BOPTools_EEInterference& aEE=aEEs(nIEE);
486       aEE.Indices(nE[0], nE[1]);
487       aEE.SetNewShape(nVnew);
488       //
489       for (j=0; j<2; ++j) {
490         if (aMFence.Add(nE[j])) {
491           aE=TopoDS::Edge(myDS->Shape(nE[j]));
492           iFlag=myContext.ComputeVE (aVnew, aE, aT);
493           if (!iFlag) {
494             aPave.SetInterference(-1);
495             aPave.SetType (BooleanOperations_EdgeEdge);
496             aPave.SetIndex(nVnew);
497             aPave.SetParam(aT);
498             //
499             BOPTools_PaveSet& aPaveSet=myPavePoolNew(myDS->RefEdge(nE[j]));
500             aPaveSet.Append(aPave);
501           }
502         }// if (aMFence.Add(nE[j])) {
503       }// for (j=0; j<2; ++j) {
504     }//for (; aIt.More(); aIt.Next()) {
505   }// for (; aItIm.More(); aItIm.Next())
506 }
507 //
508 // case: use_02
509 // completely rewritten
510 //=======================================================================
511 //function : TreatNewVertices
512 //purpose  : 
513 //=======================================================================
514 void TreatNewVertices(const BooleanOperations_IndexedDataMapOfShapeInteger& aMapVI,
515                    TopTools_DataMapOfShapeListOfShape& myImages,
516                    TopTools_DataMapOfShapeShape& myOrigins)
517 {
518   Standard_Integer j, i, aNbV, aNbVSD;
519   Standard_Real aTol;
520   TColStd_ListIteratorOfListOfInteger aIt;
521   TopoDS_Shape aSTmp, aVF;
522   TopoDS_Vertex aVnew;
523   TopTools_IndexedMapOfShape aMV, aMVProcessed;
524   TopTools_ListIteratorOfListOfShape aItS;
525   TopTools_DataMapIteratorOfDataMapOfShapeListOfShape aItIm;
526   TopTools_DataMapOfShapeListOfShape aMVV;
527   NMTDS_IndexedDataMapOfIntegerShape aMIS;
528   NMTDS_IndexedDataMapOfShapeBox aMSB;
529   //
530   NMTDS_BoxBndTreeSelector aSelector;
531   NMTDS_BoxBndTree aBBTree;
532   NCollection_UBTreeFiller <Standard_Integer, Bnd_Box> aTreeFiller(aBBTree);
533   //
534   myImages.Clear();
535   myOrigins.Clear();
536   //
537   aNbV=aMapVI.Extent();
538   for (i=1; i<=aNbV; ++i) {
539     const TopoDS_Shape& aV=aMapVI.FindKey(i);
540     aMV.Add(aV);
541   }
542   //
543   for (i=1; i<=aNbV; ++i) {
544     const TopoDS_Shape& aV=aMV(i);
545     Bnd_Box aBox;
546     //
547     aTol=BRep_Tool::Tolerance(TopoDS::Vertex(aV));
548     aBox.SetGap(aTol); 
549     BRepBndLib::Add(aV, aBox);
550     //
551     aTreeFiller.Add(i, aBox);
552     //
553     aMIS.Add(i, aV);
554     aMSB.Add(aV, aBox); 
555   }
556   //
557   aTreeFiller.Fill();
558   //
559   // Chains
560   for (i=1; i<=aNbV; ++i) {
561     const TopoDS_Shape& aV=aMV(i);
562     //
563     if (aMVProcessed.Contains(aV)) {
564       continue;
565     }
566     //
567     Standard_Integer aNbIP, aIP, aNbIP1, aIP1;
568     TopTools_ListOfShape aLVSD;
569     TColStd_MapOfInteger aMIP, aMIP1, aMIPC;
570     TColStd_MapIteratorOfMapOfInteger aIt1;
571     //
572     aMIP.Add(i);
573     while(1) {
574       aNbIP=aMIP.Extent();
575       aIt1.Initialize(aMIP);
576       for(; aIt1.More(); aIt1.Next()) {
577         aIP=aIt1.Key();
578         if (aMIPC.Contains(aIP)) {
579           continue;
580         }
581         //
582         const TopoDS_Shape& aVP=aMIS.FindFromKey(aIP);
583         const Bnd_Box& aBoxVP=aMSB.FindFromKey(aVP);
584         //
585         aSelector.Clear();
586         aSelector.SetBox(aBoxVP);
587         //
588         aNbVSD=aBBTree.Select(aSelector);
589         if (!aNbVSD) {
590           continue;  // it must not be 
591         }
592         //
593         const TColStd_ListOfInteger& aLI=aSelector.Indices();
594         aIt.Initialize(aLI);
595         for (; aIt.More(); aIt.Next()) {
596           aIP1=aIt.Value();
597           if (aMIP.Contains(aIP1)) {
598             continue;
599           }
600           aMIP1.Add(aIP1);
601         } //for (; aIt.More(); aIt.Next()) {
602       }//for(; aIt1.More(); aIt1.Next()) {
603       //
604       aNbIP1=aMIP1.Extent();
605       if (!aNbIP1) {
606         break; // from while(1)
607       }
608       //
609       aIt1.Initialize(aMIP);
610       for(; aIt1.More(); aIt1.Next()) {
611         aIP=aIt1.Key();
612         aMIPC.Add(aIP);
613       }
614       //
615       aMIP.Clear();
616       aIt1.Initialize(aMIP1);
617       for(; aIt1.More(); aIt1.Next()) {
618         aIP=aIt1.Key();
619         aMIP.Add(aIP);
620       }
621       aMIP1.Clear();
622     }// while(1)
623     //...
624     aNbIP=aMIPC.Extent();
625     if (!aNbIP) {
626       aMIPC.Add(i);
627     }
628     //
629     aIt1.Initialize(aMIPC);
630     for(j=0; aIt1.More(); aIt1.Next(), ++j) {
631       aIP=aIt1.Key();
632       const TopoDS_Shape& aVP=aMIS.FindFromKey(aIP);
633       if (!j) {
634         aVF=aVP;
635       }
636       aLVSD.Append(aVP);
637       aMVProcessed.Add(aVP);
638     }
639     myImages.Bind(aVF, aLVSD);
640   }// for (i=1; i<=aNbV; ++i) {
641   //------------------------------
642   //
643   // Make new vertices
644   aMV.Clear();
645   aItIm.Initialize(myImages);
646   for (; aItIm.More(); aItIm.Next()) {
647     const TopoDS_Shape& aV=aItIm.Key();
648     const TopTools_ListOfShape& aLVSD=aItIm.Value();
649     aNbVSD=aLVSD.Extent();
650     if (aNbVSD>1) {
651       aMV.Add(aV);
652       MakeNewVertex(aLVSD, aVnew);
653       aMVV.Bind(aVnew, aLVSD);
654     }
655   }
656   //
657   // UnBind old vertices
658   aNbV=aMV.Extent();
659   for (i=1; i<=aNbV; ++i) {
660     const TopoDS_Shape& aV=aMV(i);
661     myImages.UnBind(aV);
662   }
663   //
664   // Bind new vertices
665   aItIm.Initialize(aMVV);
666   for (; aItIm.More(); aItIm.Next()) {
667     const TopoDS_Shape& aV=aItIm.Key();
668     const TopTools_ListOfShape& aLVSD=aItIm.Value();
669     myImages.Bind(aV, aLVSD);
670   }
671   //
672   // Origins
673   aItIm.Initialize(myImages);
674   for (; aItIm.More(); aItIm.Next()) {
675     const TopoDS_Shape& aV=aItIm.Key();
676     const TopTools_ListOfShape& aLVSD=aItIm.Value();
677     //
678     aItS.Initialize(aLVSD);
679     for (; aItS.More(); aItS.Next()) {
680       const TopoDS_Shape& aVSD=aItS.Value();
681       if (!myOrigins.IsBound(aVSD)) {
682         myOrigins.Bind(aVSD, aV);
683       }
684     }
685   }
686 }
687 //
688 //=======================================================================
689 //function : MakeNewVertex
690 //purpose  : 
691 //=======================================================================
692 void MakeNewVertex(const TopTools_ListOfShape& aLV, 
693                    TopoDS_Vertex& aNewVertex)
694 {
695   Standard_Integer aNbV;
696   Standard_Real aTolV, aD, aDmax;
697   gp_XYZ aGC;
698   gp_Pnt aP3D, aPGC;
699   TopoDS_Vertex aVx;
700   BRep_Builder aBB;
701   TopTools_ListIteratorOfListOfShape aIt;
702   //
703   aNbV=aLV.Extent();
704   if (!aNbV) {
705     return;
706   }
707   //
708   // center of gravity
709   aGC.SetCoord(0.,0.,0.);
710   aIt.Initialize(aLV);
711   for (; aIt.More(); aIt.Next()) {
712     aVx=TopoDS::Vertex(aIt.Value());
713     aP3D=BRep_Tool::Pnt(aVx);
714     aGC+=aP3D.XYZ();
715   }
716   aGC/=(Standard_Real)aNbV;
717   aPGC.SetXYZ(aGC);
718   //
719   // tolerance value
720   aDmax=-1.;
721   aIt.Initialize(aLV);
722   for (; aIt.More(); aIt.Next()) {
723     aVx=TopoDS::Vertex(aIt.Value());
724     aP3D=BRep_Tool::Pnt(aVx);
725     aTolV=BRep_Tool::Tolerance(aVx);
726     aD=aPGC.Distance(aP3D)+aTolV;
727     if (aD>aDmax) {
728       aDmax=aD;
729     }
730   }
731   //
732   aBB.MakeVertex (aNewVertex, aPGC, aDmax);
733 }
734 //=======================================================================
735 // function:EENewVertices
736 // purpose: 
737 //=======================================================================
738   void NMTTools_PaveFiller::EENewVertices (const TopoDS_Vertex& aNewVertex,
739                                            const BooleanOperations_IndexedDataMapOfShapeInteger& aMapVI) 
740 {
741   Standard_Integer  i, aNewShape, nE1, nE2;
742   Standard_Real  aT1, aT2;
743   BooleanOperations_AncestorsSeqAndSuccessorsSeq anASSeq;       
744   BOPTools_Pave aPave;
745   //
746   BOPTools_CArray1OfEEInterference& aEEs=myIP->EEInterferences();
747   //
748   // one new vertex case is treated in usual way
749   //
750   // Insert New Vertex in DS;
751   myDS->InsertShapeAndAncestorsSuccessors(aNewVertex, anASSeq);
752   aNewShape=myDS->NumberOfInsertedShapes();
753   myDS->SetState (aNewShape, BooleanOperations_ON);
754   // Insert New Vertex in EE Interference
755   i=aMapVI.FindFromKey(aNewVertex);
756   BOPTools_EEInterference& aEEInterf= aEEs(i);
757   aEEInterf.SetNewShape(aNewShape);
758   // Extact interference info
759   aEEInterf.Indices(nE1, nE2);
760   const IntTools_CommonPrt& aCPart=aEEInterf.CommonPrt();
761   VertexParameters(aCPart, aT1, aT2);
762   //
763   // Add Paves to the myPavePoolNew
764   aPave.SetInterference(i);
765   aPave.SetType (BooleanOperations_EdgeEdge);
766   aPave.SetIndex(aNewShape);
767   // Pave for edge nE1
768   aPave.SetParam(aT1);
769   BOPTools_PaveSet& aPaveSet1=myPavePoolNew(myDS->RefEdge(nE1));
770   aPaveSet1.Append(aPave);
771   // Pave for edge nE2
772   aPave.SetParam(aT2);
773   BOPTools_PaveSet& aPaveSet2=myPavePoolNew(myDS->RefEdge(nE2));
774   aPaveSet2.Append(aPave);
775 }
776 //=======================================================================
777 // function: RefinePavePool
778 // purpose: 
779 //=======================================================================
780   void NMTTools_PaveFiller::RefinePavePool()
781 {
782   Standard_Integer  i, aNbNew;
783
784   for (i=1; i<=myNbSources; i++) {
785
786     if ((myDS->GetShape(i)).ShapeType()==TopAbs_EDGE) {
787       BOPTools_PaveSet& aPS= myPavePool(myDS->RefEdge(i));
788       //
789       BOPTools_PaveSet& aNewPS= myPavePoolNew(myDS->RefEdge(i));
790       BOPTools_ListOfPave& aNewLP=aNewPS.ChangeSet();
791       //
792       aNbNew=aNewLP.Extent();
793       if (aNbNew) {
794         BOPTools_ListIteratorOfListOfPave anIt(aNewLP);
795         for (; anIt.More(); anIt.Next()) {
796           const BOPTools_Pave& aPave=anIt.Value();
797           aPS.Append(aPave);
798         }
799         // Clear the ListOfPaveBlock
800         BOPTools_ListOfPaveBlock& aLPB=mySplitShapesPool(myDS->RefEdge(i));
801         aLPB.Clear();
802         // Prepare the paveBlocks for that egde again
803         PreparePaveBlocks(i);
804       }
805       aNewLP.Clear();
806     }
807   }
808 }
809 //=======================================================================
810 // function: PreparePaveBlocks
811 // purpose: 
812 //=======================================================================
813   void NMTTools_PaveFiller::PreparePaveBlocks(const TopAbs_ShapeEnum aType1, 
814                                               const TopAbs_ShapeEnum aType2)
815 {
816   myIsDone=Standard_False;
817   //
818   Standard_Boolean bOk1, bOk2, bOk3, bFlag;
819   Standard_Integer i, aNb, nE[2], n1, n2, aNbSplits;
820   TColStd_MapOfInteger aMap;
821   
822   bOk1= (aType1==TopAbs_VERTEX) &&  (aType2==TopAbs_EDGE) ;
823   bOk2= (aType1==TopAbs_EDGE)   &&  (aType2==TopAbs_EDGE) ;
824   bOk3= (aType1==TopAbs_EDGE)   &&  (aType2==TopAbs_FACE) ;
825   if (!bOk1 && !bOk2 && !bOk3) {// error: Type mismatch
826     return;
827   }
828   //
829   aNb=bOk2 ? 2 : 1;
830   //
831   myDSIt->Initialize(aType1, aType2);
832   for (; myDSIt->More(); myDSIt->Next()) {
833     myDSIt->Current(n1, n2, bFlag);
834     //
835     nE[0]=n1; 
836     nE[1]=n2; 
837     if (myDS->GetShapeType(n1)!=TopAbs_EDGE) {
838       nE[0]=n2; 
839       nE[1]=n1;
840     }
841     //
842     for (i=0; i<aNb; ++i) {
843       BOPTools_ListOfPaveBlock& aLPB=mySplitShapesPool(myDS->RefEdge(nE[i]));
844       aNbSplits=aLPB.Extent();
845       if (!aNbSplits) {
846         if (aMap.Add(nE[i])) { 
847           PreparePaveBlocks(nE[i]);
848           if (!myIsDone) {
849             return;
850           }
851         }
852       }
853     }
854   }// for (; myDSIt.More(); myDSIt.Next()) 
855   myIsDone=Standard_True;
856 }
857 //=======================================================================
858 // function: PreparePaveBlocks
859 // purpose: 
860 //=======================================================================
861   void NMTTools_PaveFiller::PreparePaveBlocks(const Standard_Integer nE)
862 {
863   myIsDone=Standard_False;
864   //
865   char buf[512];
866   Standard_Integer nV1, nV2, iErr;
867   TopoDS_Edge aE;
868   TopoDS_Vertex aV1, aV2;
869   //
870   BOPTools_ListOfPaveBlock& aLPB=mySplitShapesPool(myDS->RefEdge(nE));
871   // Edge 
872   aE=TopoDS::Edge(myDS->Shape(nE));
873   if (BRep_Tool::Degenerated(aE)) {
874     myIsDone=Standard_True;
875     return;
876   }
877   //
878   BOPTools_PaveSet& aPS=myPavePool(myDS->RefEdge(nE));
879   
880   BOPTools_PaveBlockIterator aPBIt(nE, aPS);
881   for (; aPBIt.More(); aPBIt.Next()) {
882     BOPTools_PaveBlock& aPB=aPBIt.Value();
883     const IntTools_Range& aRange=aPB.Range();
884     //
885     const BOPTools_Pave& aPave1=aPB.Pave1();
886     nV1=aPave1.Index();
887     aV1=TopoDS::Vertex(myDS->GetShape(nV1));
888     //
889     const BOPTools_Pave& aPave2=aPB.Pave2();
890     nV2=aPave2.Index();
891     aV2=TopoDS::Vertex(myDS->GetShape(nV2));
892     //
893     // ShrunkRange
894     IntTools_ShrunkRange aSR (aE, aV1, aV2, aRange, myContext);
895     iErr=aSR.ErrorStatus();
896     if (!aSR.IsDone()) {
897       sprintf (buf, "Can not obtain ShrunkRange for Edge %d\n", nE);
898       BOPTColStd_Dump::PrintMessage(buf);
899       sprintf (buf, "Can not obtain ShrunkRange for Edge %d", nE);
900       throw 
901         BOPTColStd_Failure(buf) ;
902     }
903     //
904     if (iErr==6) {
905       sprintf(buf,
906               "Warning: [PreparePaveBlocks()] Max.Dummy Shrunk Range for Edge %d\n", nE);
907       BOPTColStd_Dump::PrintMessage(buf);
908     }
909     else {
910       // Check left paves and correct ShrunkRange if it is necessary
911       CorrectShrunkRanges (0, aPave1, aSR);
912       CorrectShrunkRanges (1, aPave2, aSR);
913     }
914     //
915     aPB.SetShrunkRange(aSR);
916     aLPB.Append(aPB);
917   } //for (; aPBIt.More(); aPBIt.Next()) 
918   myIsDone=Standard_True;
919 }
920 //=======================================================================
921 // function: CorrectShrunkRanges
922 // purpose: 
923 //=======================================================================
924   void NMTTools_PaveFiller::CorrectShrunkRanges(const Standard_Integer aSide,
925                                                 const BOPTools_Pave& aPave,
926                                                 IntTools_ShrunkRange& aShrunkRange)
927 {
928   BooleanOperations_KindOfInterference aType;
929   Standard_Integer anIndexInterf ;
930   //
931   aType=aPave.Type();
932   if (aType!=BooleanOperations_EdgeEdge) {
933     return;
934   }
935   //
936   anIndexInterf=aPave.Interference();
937   if (anIndexInterf<0) {
938     // it can be EE interf between E and (e1,e2,..en) -> vertex
939     // so we can't decide which aEE.CommonPrt() we should take.
940     return;
941   }
942
943   BOPTools_CArray1OfEEInterference& aEEs=myIP->EEInterferences();
944   const BOPTools_EEInterference& aEE=aEEs(anIndexInterf);
945   const IntTools_CommonPrt& aCP=aEE.CommonPrt();
946   const TopoDS_Edge& aE1=aCP.Edge1();
947   const TopoDS_Edge& aE2=aCP.Edge2();
948
949   const IntTools_Range& aSR=aShrunkRange.ShrunkRange();
950   const TopoDS_Edge& aE=aShrunkRange.Edge();
951  
952   IntTools_Range aNewRange;
953   IntTools_Range aCPRange;
954
955   if (aE1.IsSame(aE)) {
956     const IntTools_Range& aR1=aCP.Range1();
957     aCPRange=aR1;
958   }
959   if (aE2.IsSame(aE)) {
960     const IntTools_SequenceOfRanges& aSeqR=aCP.Ranges2();
961     const IntTools_Range& aR2=aSeqR(1);
962      aCPRange=aR2;
963   }
964   //
965   Standard_Real aCoeff=1.05, tV, tNV;
966   tV=aPave.Param();
967   if (aSide==0) { // Left
968     if (aCPRange.Last() > aSR.First()) {
969       tNV=aCPRange.Last();
970       tNV=tV+aCoeff*(tNV-tV);
971       aNewRange.SetFirst(tNV);
972       aNewRange.SetLast (aSR.Last());
973       //modified by NIZNHY-PKV Tue Jan 23 14:07:55 2007f
974       //if(aNewRange.First() > aNewRange.Last()) {
975       if(aNewRange.First() < aNewRange.Last()) {
976       //modified by NIZNHY-PKV Tue Jan 23 14:08:02 2007t
977         aShrunkRange.SetShrunkRange(aNewRange);
978       }
979     }
980   }
981   else { // Right
982     if (aCPRange.First() < aSR.Last()) {
983       tNV=aCPRange.First();
984       tNV=tV-aCoeff*(tV-tNV);
985       aNewRange.SetFirst(aSR.First());
986       aNewRange.SetLast (tNV);
987
988       if(aNewRange.First() < aNewRange.Last()) {
989         aShrunkRange.SetShrunkRange(aNewRange);
990       }
991     }
992   }
993 }
994 //=======================================================================
995 // function:  IsBlocksCoinside
996 // purpose: 
997 //=======================================================================
998   Standard_Boolean 
999     NMTTools_PaveFiller::IsBlocksCoinside(const BOPTools_PaveBlock& aPB1,
1000                                           const BOPTools_PaveBlock& aPB2) const
1001 {
1002   Standard_Boolean bRetFlag=Standard_True;
1003   Standard_Real aTolV11, aTolV12, aTolV21, aTolV22;
1004   Standard_Real d1121, d1122, d1222, d1221, aTolSum, aCoeff=1.05;
1005   gp_Pnt aP11, aP12, aP21, aP22;
1006
1007   const TopoDS_Vertex aV11=TopoDS::Vertex(myDS->Shape(aPB1.Pave1().Index()));//mpv
1008   const TopoDS_Vertex aV12=TopoDS::Vertex(myDS->Shape(aPB1.Pave2().Index()));//mpv
1009   const TopoDS_Vertex aV21=TopoDS::Vertex(myDS->Shape(aPB2.Pave1().Index()));//mpv
1010   const TopoDS_Vertex aV22=TopoDS::Vertex(myDS->Shape(aPB2.Pave2().Index()));//mpv
1011
1012   aTolV11=BRep_Tool::Tolerance(aV11);
1013   aTolV12=BRep_Tool::Tolerance(aV12);
1014   aTolV21=BRep_Tool::Tolerance(aV21);
1015   aTolV22=BRep_Tool::Tolerance(aV22);
1016   
1017   aP11=BRep_Tool::Pnt(aV11);
1018   aP12=BRep_Tool::Pnt(aV12);
1019   aP21=BRep_Tool::Pnt(aV21);
1020   aP22=BRep_Tool::Pnt(aV22);
1021
1022   d1121=aP11.Distance(aP21);
1023   aTolSum=aCoeff*(aTolV11+aTolV21);
1024   if (d1121<aTolSum) {
1025     d1222=aP12.Distance(aP22);
1026     aTolSum=aCoeff*(aTolV12+aTolV22);
1027     if (d1222<aTolSum) {
1028       return bRetFlag;
1029     }
1030   }
1031   //
1032   d1122=aP11.Distance(aP22);
1033   aTolSum=aCoeff*(aTolV11+aTolV22);
1034   if (d1122<aTolSum) {
1035     d1221=aP12.Distance(aP21);
1036     aTolSum=aCoeff*(aTolV12+aTolV21);
1037     if (d1221<aTolSum) {
1038       return bRetFlag;
1039     }
1040   }
1041   return !bRetFlag;
1042 }
1043 //=======================================================================
1044 // function: ReplaceCommonBlocks
1045 // purpose: 
1046 //=======================================================================
1047   void NMTTools_PaveFiller::ReplaceCommonBlocks(const NMTTools_ListOfCommonBlock& aLCB)
1048 {
1049   RemoveCommonBlocks(aLCB);
1050   SplitCommonBlocks(aLCB);
1051 }
1052 //=======================================================================
1053 // function: SplitCommonBlocks
1054 // purpose: 
1055 //=======================================================================
1056   void NMTTools_PaveFiller::SplitCommonBlocks(const NMTTools_ListOfCommonBlock& aLCB)
1057 {
1058   Standard_Integer nE;
1059   NMTTools_ListOfCommonBlock aLCBx;
1060   NMTTools_ListIteratorOfListOfCommonBlock anIt, anItCBx;
1061   BOPTools_ListIteratorOfListOfPaveBlock anItLPE;
1062   //
1063   anIt.Initialize(aLCB);
1064   for (; anIt.More(); anIt.Next()) {
1065     const NMTTools_CommonBlock& aCB=anIt.Value();
1066     //
1067     //XXX
1068     aLCBx.Clear();
1069     //XXX
1070     SplitCommonBlock(aCB, aLCBx);
1071     //
1072     anItCBx.Initialize(aLCBx);
1073     for (; anItCBx.More(); anItCBx.Next()) {
1074       const NMTTools_CommonBlock& aCBx=anItCBx.Value();
1075       const BOPTools_ListOfPaveBlock& aLPBx=aCBx.PaveBlocks();
1076       //
1077       anItLPE.Initialize(aLPBx);
1078       for (; anItLPE.More(); anItLPE.Next()) {
1079         const BOPTools_PaveBlock& aPBx=anItLPE.Value();
1080         nE=aPBx.OriginalEdge();
1081         NMTTools_ListOfCommonBlock& aLCBE=myCommonBlockPool(myDS->RefEdge(nE));
1082         aLCBE.Append(aCBx);
1083       }
1084     }
1085   }
1086   // Modified to provide the order of edges 
1087   // in common block where the edge with max 
1088   // tolerance value will be the first
1089   //  Thu Sep 14 14:35:18 2006 
1090   // Contribution of Samtech www.samcef.com BEGIN
1091   Standard_Integer i, iMax, aNb, aNbCB, nSp;
1092   Standard_Real aTolSp, aTolMax;
1093   BOPTools_ListOfPaveBlock *pLPBE;
1094   //
1095   aNb=myDS->NumberOfShapesOfTheObject();
1096   for (nE=1; nE<=aNb; ++nE) {
1097     const TopoDS_Shape& aE=myDS->Shape(nE);
1098     if (aE.ShapeType()!=TopAbs_EDGE) {
1099       continue;
1100     }
1101     //
1102     NMTTools_ListOfCommonBlock& aLCBE=myCommonBlockPool(myDS->RefEdge(nE));
1103     aNbCB=aLCBE.Extent();
1104     if (!aNbCB) {
1105       continue;
1106     }
1107     //
1108     anIt.Initialize(aLCBE);
1109     for (; anIt.More(); anIt.Next()) {
1110       NMTTools_CommonBlock& aCBE=anIt.Value();
1111       const BOPTools_ListOfPaveBlock& aLPBE=aCBE.PaveBlocks();
1112       //
1113       aTolMax=-1.;
1114       anItLPE.Initialize(aLPBE);
1115       for (i=0; anItLPE.More(); anItLPE.Next(), ++i) {
1116         const BOPTools_PaveBlock& aPB=anItLPE.Value();
1117         nSp=aPB.OriginalEdge();
1118         const TopoDS_Edge& aSp=TopoDS::Edge(myDS->Shape(nSp));
1119         aTolSp=BRep_Tool::Tolerance(aSp);
1120         if (aTolSp>aTolMax) {
1121           iMax=i;
1122           aTolSp=aTolMax;
1123         }
1124       }
1125       //
1126       BOPTools_ListOfPaveBlock aLPBx;
1127       //
1128       anItLPE.Initialize(aLPBE);
1129       for (i=0; anItLPE.More(); anItLPE.Next(), ++i) {
1130         const BOPTools_PaveBlock& aPB=anItLPE.Value();
1131         if (i==iMax) {
1132           aLPBx.Prepend(aPB);
1133         }
1134         else {
1135           aLPBx.Append(aPB);
1136         }
1137       }
1138       //
1139       pLPBE=(BOPTools_ListOfPaveBlock *)&aLPBE;
1140       pLPBE->Clear();
1141       pLPBE->Append(aLPBx);
1142     }//for (; anIt.More(); anIt.Next()) {
1143   }//for (nE=1; nE<=aNb; ++nE) {
1144   // Contribution of Samtech www.samcef.com END
1145 }
1146 //=======================================================================
1147 // function: RemoveCommonBlocks
1148 // purpose: 
1149 //=======================================================================
1150   void NMTTools_PaveFiller::RemoveCommonBlocks(const NMTTools_ListOfCommonBlock& aLCB)
1151 {
1152   Standard_Integer nE;
1153   NMTTools_ListOfCommonBlock aLCBx;
1154   NMTTools_ListIteratorOfListOfCommonBlock anItCB, anItCBE;
1155   BOPTools_ListIteratorOfListOfPaveBlock anItLPB;
1156   //
1157   anItCB.Initialize(aLCB);
1158   for (; anItCB.More(); anItCB.Next()) {
1159     const NMTTools_CommonBlock& aCB=anItCB.Value();
1160     const BOPTools_ListOfPaveBlock& aLPB=aCB.PaveBlocks();
1161     //
1162     // Remove aCB from each edge 
1163     anItLPB.Initialize(aLPB);
1164     for (; anItLPB.More(); anItLPB.Next()) {
1165       const BOPTools_PaveBlock& aPB=anItLPB.Value();
1166       nE=aPB.OriginalEdge();
1167       //
1168       NMTTools_ListOfCommonBlock& aLCBE=myCommonBlockPool(myDS->RefEdge(nE));
1169       anItCBE.Initialize(aLCBE);
1170       for (; anItCBE.More(); anItCBE.Next()) {
1171         const NMTTools_CommonBlock& aCBE=anItCBE.Value();
1172         if (aCBE.IsEqual(aCB)) {
1173           aLCBE.Remove(anItCBE);
1174           break;
1175         }
1176       }
1177     }
1178   }
1179 }
1180 //=======================================================================
1181 // function: SplitCommonBlock
1182 // purpose: 
1183 //=======================================================================
1184   void NMTTools_PaveFiller::SplitCommonBlock(const NMTTools_CommonBlock& aCB,
1185                                              NMTTools_ListOfCommonBlock& aLCBx)
1186 {
1187   Standard_Integer i, j, k, nE, aNbE, aNbSPBx, aNbPB; 
1188   BOPTools_SequenceOfPaveBlock aSPBx;
1189   BOPTools_ListIteratorOfListOfPaveBlock anItLPB;
1190   BOPTools_ListIteratorOfListOfPave anIt;
1191   
1192   BOPTools_PaveBlockIterator anPBIt; 
1193   //
1194   const BOPTools_ListOfPaveBlock& aLPB=aCB.PaveBlocks();
1195   aNbE=aLPB.Extent();
1196   //
1197   // 1. Whether we realy need to split the common block ?
1198   anItLPB.Initialize(aLPB);
1199   for (; anItLPB.More(); anItLPB.Next()) {
1200     const BOPTools_PaveBlock& aPB=anItLPB.Value();
1201     nE=aPB.OriginalEdge();
1202     BOPTools_PaveSet& aPSE=myPavePoolNew(myDS->RefEdge(nE));
1203     aPSE.SortSet();
1204     //
1205     BOPTools_PaveSet aPSx;
1206     //
1207     const BOPTools_ListOfPave& aLPE=aPSE.Set();
1208     anIt.Initialize(aLPE);
1209     for (; anIt.More(); anIt.Next()) {
1210       const BOPTools_Pave& aPx=anIt.Value();
1211       if (aPB.IsInBlock(aPx)) {
1212         aPSx.Append(aPx);
1213       }
1214     }
1215     aNbPB=aPSx.Set().Extent();
1216     break;
1217   }
1218   //
1219   if (!aNbPB) {
1220     // we need not split it
1221     aLCBx.Append(aCB);
1222     return;
1223   }
1224   //
1225   // 2. Get sequence of pave Blocks containing all new pave blocks
1226   // for each edges's source pave Block
1227   anItLPB.Initialize(aLPB);
1228   for (; anItLPB.More(); anItLPB.Next()) {
1229     const BOPTools_PaveBlock& aPB=anItLPB.Value();
1230     const BOPTools_Pave& aPave1=aPB.Pave1();
1231     const BOPTools_Pave& aPave2=aPB.Pave2();
1232     nE=aPB.OriginalEdge();
1233     //
1234     BOPTools_PaveSet aPSx;
1235     //
1236     // the set aPsx will contain bounadry paves aPave1, aPave2 and
1237     // all paves of the edge nE that are inside block aPB
1238     aPSx.Append(aPave1);
1239     aPSx.Append(aPave2);
1240     //
1241     BOPTools_PaveSet& aPSE=myPavePoolNew(myDS->RefEdge(nE));
1242     aPSE.SortSet();
1243     //
1244     const BOPTools_ListOfPave& aLPE=aPSE.Set();
1245     anIt.Initialize(aLPE);
1246     for (; anIt.More(); anIt.Next()) {
1247       const BOPTools_Pave& aPx=anIt.Value();
1248       if (aPB.IsInBlock(aPx)) {
1249         aPSx.Append(aPx);
1250       }
1251     }
1252     //
1253     // Form pave blocks from aPSx and collect them in aSPBx
1254     anPBIt.Initialize(nE, aPSx);
1255     for (; anPBIt.More(); anPBIt.Next()) {
1256       const BOPTools_PaveBlock& aPBx=anPBIt.Value();
1257       aSPBx.Append(aPBx);
1258     }
1259   }
1260   //
1261   // 3. Do new common blocks 
1262   //
1263   const TColStd_ListOfInteger& aLF=aCB.Faces();
1264   aNbSPBx=aSPBx.Length();
1265   aNbPB=aNbSPBx/aNbE;
1266   //
1267   for (i=1; i<=aNbPB; ++i) {
1268     NMTTools_CommonBlock aCBx;
1269     //
1270     aCBx.AddFaces(aLF);
1271     //
1272     for (j=1; j<=aNbE; ++j) {
1273       k=i+(j-1)*aNbPB;
1274       const BOPTools_PaveBlock& aPB=aSPBx(k);
1275       aCBx.AddPaveBlock(aPB);
1276     }
1277     aLCBx.Append(aCBx);
1278   }
1279 }
1280
1281 //=======================================================================
1282 // function: VertexParameters
1283 // purpose: 
1284 //=======================================================================
1285 void VertexParameters(const IntTools_CommonPrt& aCPart,
1286                       Standard_Real& aT1, 
1287                       Standard_Real& aT2)
1288 {
1289   const IntTools_Range& aR1=aCPart.Range1();
1290   aT1=0.5*(aR1.First()+aR1.Last());
1291   //
1292   if((aCPart.VertexParameter1() >= aR1.First()) &&
1293      (aCPart.VertexParameter1() <= aR1.Last())) {
1294     aT1 = aCPart.VertexParameter1();
1295   }
1296   //
1297   const IntTools_SequenceOfRanges& aRanges2=aCPart.Ranges2();
1298   const IntTools_Range& aR2=aRanges2(1);
1299   aT2=0.5*(aR2.First()+aR2.Last());
1300   //
1301   if((aCPart.VertexParameter2() >= aR2.First()) &&
1302      (aCPart.VertexParameter2() <= aR2.Last())) {
1303     aT2 = aCPart.VertexParameter2();
1304   }
1305 }
1306 //=======================================================================
1307 // function: KeepPave
1308 // purpose: 
1309 //=======================================================================
1310 Standard_Boolean IsOnPave(const Standard_Real& aT1,
1311                           const IntTools_Range& aRange,
1312                           const Standard_Real& aTolerance)
1313 {
1314   Standard_Boolean firstisonpave1, firstisonpave2, bIsOnPave;
1315   //
1316   firstisonpave1  = (Abs(aRange.First() - aT1) < aTolerance);
1317   firstisonpave2  = (Abs(aRange.Last()  - aT1) < aTolerance);
1318   bIsOnPave=(firstisonpave1 || firstisonpave2);
1319   return bIsOnPave;
1320 }
1321
1322 //=======================================================================
1323 // function:FindChains
1324 // purpose: 
1325 //=======================================================================
1326 void FindChains(const BOPTools_IDMapOfPaveBlockIMapOfPaveBlock& aMapCB,
1327                 NMTTools_ListOfCommonBlock& aLCB)
1328 {
1329   Standard_Integer  i, j, aNbCB, aNbPB;
1330   BOPTools_IMapOfPaveBlock aProcessedBlocks, aChain;
1331   //
1332   aNbCB=aMapCB.Extent();
1333   for (i=1; i<=aNbCB; ++i) {
1334     const BOPTools_PaveBlock& aPB=aMapCB.FindKey(i);
1335     if (aProcessedBlocks.Contains(aPB)) {
1336       continue;
1337     }
1338     //
1339     aProcessedBlocks.Add(aPB);
1340     aChain.Add(aPB);
1341     //
1342     const BOPTools_IMapOfPaveBlock& aMapPB=aMapCB(i);
1343     aNbPB=aMapPB.Extent();
1344     for (j=1; j<=aNbPB; ++j) {
1345       const BOPTools_PaveBlock& aPBx=aMapPB(j);
1346       ProcessBlock(aPBx, aMapCB, aProcessedBlocks, aChain);
1347     }
1348     //
1349     NMTTools_CommonBlock aCB;
1350     //
1351     aNbPB=aChain.Extent();
1352     for (j=1; j<=aNbPB; ++j) {
1353       const BOPTools_PaveBlock& aPBx=aChain(j);
1354       aCB.AddPaveBlock(aPBx);
1355     }
1356     aLCB.Append(aCB);
1357     aChain.Clear();
1358   }
1359 }
1360 //=======================================================================
1361 // function:ProcessBlock
1362 // purpose: 
1363 //=======================================================================
1364 void ProcessBlock(const BOPTools_PaveBlock& aPB,
1365                   const BOPTools_IDMapOfPaveBlockIMapOfPaveBlock& aMapCB,
1366                   BOPTools_IMapOfPaveBlock& aProcessedBlocks,
1367                   BOPTools_IMapOfPaveBlock& aChain)
1368 {
1369   Standard_Integer j, aNbPB;
1370   //
1371   if (aProcessedBlocks.Contains(aPB)) {
1372     return;
1373   }
1374   aProcessedBlocks.Add(aPB);
1375   aChain.Add(aPB);
1376   //
1377   const BOPTools_IMapOfPaveBlock& aMapPB=aMapCB.FindFromKey(aPB);
1378   aNbPB=aMapPB.Extent();
1379   for (j=1; j<=aNbPB; ++j) {
1380     const BOPTools_PaveBlock& aPBx=aMapPB(j);
1381     ProcessBlock(aPBx, aMapCB, aProcessedBlocks, aChain);
1382   }
1383 }
1384 // Modified  to provide VS interference between
1385 // vertex as result of EE and a Face of argument
1386 // Thu Sep 14 14:35:18 2006 
1387 // Contribution of Samtech www.samcef.com BEGIN
1388 //=======================================================================
1389 // function: PerformVF1  
1390 // purpose: 
1391 //=======================================================================
1392   void NMTTools_PaveFiller::PerformVF1()
1393 {
1394   Standard_Integer i, aNbEE, n1, n2, nNewShape, aNbS, nF;
1395   Standard_Integer anIndexIn, aFlag;
1396   Standard_Real aU, aV;
1397   TColStd_ListOfInteger aLFI;
1398   TColStd_ListIteratorOfListOfInteger aItLFI;
1399   //
1400   BOPTools_CArray1OfVSInterference& aVSs=myIP->VSInterferences();
1401   BOPTools_CArray1OfEEInterference& aEEs=myIP->EEInterferences();
1402   //
1403   aNbS=myDS->NumberOfShapesOfTheObject();
1404   for (i=1; i<=aNbS; ++i) {
1405     const TopoDS_Shape& aF=myDS->Shape(i);
1406     if (aF.ShapeType()==TopAbs_FACE) {
1407       aLFI.Append(i);
1408     }
1409   }
1410   if (!aLFI.Extent()) {
1411     return;
1412   }
1413   //
1414   aNbEE=aEEs.Extent();
1415   for (i=1; i<=aNbEE; ++i) {
1416     BOPTools_EEInterference& aEE=aEEs(i);
1417     aEE.Indices(n1, n2);
1418     nNewShape=aEE.NewShape();
1419     if (!nNewShape) {
1420       continue;
1421     }
1422     //
1423     const TopoDS_Shape& aSnew=myDS->Shape(nNewShape);
1424     if (aSnew.ShapeType()!=TopAbs_VERTEX) {
1425       continue;
1426     } 
1427     //
1428     const TopoDS_Vertex& aVnew=TopoDS::Vertex(aSnew);
1429     //
1430     Bnd_Box aBV;
1431     //
1432     BRepBndLib::Add(aVnew, aBV);
1433     //
1434     aItLFI.Initialize(aLFI);
1435     for (; aItLFI.More(); aItLFI.Next()) {
1436       nF=aItLFI.Value();
1437       //
1438       const TopoDS_Face& aF=TopoDS::Face(myDS->Shape(nF));
1439       const Bnd_Box& aBF=myDS->GetBoundingBox(nF);
1440       if (aBF.IsOut(aBV)) {
1441         continue;
1442       }
1443       //
1444       anIndexIn=0;
1445       aFlag=myContext.ComputeVS (aVnew, aF, aU, aV);
1446       if (!aFlag) {
1447         BOPTools_VSInterference anInterf (nNewShape, nF, aU, aV);
1448         //
1449         anIndexIn=aVSs.Append(anInterf);
1450         BOPTools_VSInterference& aVS=aVSs(anIndexIn);
1451         aVS.SetNewShape(nNewShape);//->
1452       }
1453     }
1454   }
1455
1456 // Contribution of Samtech www.samcef.com END