0024831: Make iterators of NCollection classes STL-compatible
[occt.git] / src / QANewModTopOpe / QANewModTopOpe_Tools.cxx
1 // Copyright (c) 1999-2014 OPEN CASCADE SAS
2 //
3 // This file is part of Open CASCADE Technology software library.
4 //
5 // This library is free software; you can redistribute it and/or modify it under
6 // the terms of the GNU Lesser General Public License version 2.1 as published
7 // by the Free Software Foundation, with special exception defined in the file
8 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
9 // distribution for complete text of the license and disclaimer of any warranty.
10 //
11 // Alternatively, this file may be used under the terms of Open CASCADE
12 // commercial license or contractual agreement.
13
14 #include <QANewModTopOpe_Tools.ixx>
15
16 #include <BRepAlgoAPI_Cut.hxx>
17 #include <BRepAlgoAPI_Common.hxx>
18
19 #include <TopoDS.hxx>
20 #include <TopoDS_Face.hxx>
21 #include <TopoDS_Edge.hxx>
22
23 #include <BRepTools.hxx>
24 #include <BRep_Tool.hxx>
25 #include <BRep_Builder.hxx>
26 #include <Geom_Surface.hxx>
27 #include <IntTools_Context.hxx>
28 #include <TopExp_Explorer.hxx>
29 #include <TopExp.hxx>
30 #include <GeomAPI_ProjectPointOnSurf.hxx>
31 #include <TopTools_IndexedMapOfShape.hxx>
32 #include <TopTools_DataMapOfIntegerShape.hxx>
33
34 #include <TColStd_Array1OfReal.hxx>
35 #include <TColStd_IndexedMapOfReal.hxx>
36 #include <TColStd_ListOfInteger.hxx>
37 #include <TColStd_ListIteratorOfListOfInteger.hxx>
38
39 #include <BOPAlgo_PaveFiller.hxx>
40 #include <BOPDS_DS.hxx>
41 #include <BOPAlgo_Builder.hxx>
42 #include <BOPAlgo_BOP.hxx>
43 #include <IntTools_CommonPrt.hxx>
44 #include <TopTools_ListIteratorOfListOfShape.hxx>
45 #include <BOPDS_CommonBlock.hxx>
46 #include <BOPTools_AlgoTools3D.hxx>
47
48 #include <NCollection_Array1.hxx>
49 #include <algorithm>
50
51 static Standard_Boolean AddShapeToHistoryMap(const TopoDS_Shape& theOldShape,
52                                              const TopoDS_Shape& theNewShape,
53                                              TopTools_IndexedDataMapOfShapeListOfShape& theHistoryMap);
54
55 static void FillEdgeHistoryMap(BRepAlgoAPI_BooleanOperation&              theBOP,
56                                TopTools_IndexedDataMapOfShapeListOfShape& theHistoryMap);
57
58 static void SortVertexOnEdge(const TopoDS_Edge&          theEdge,
59                              const TopTools_ListOfShape& theListOfVertex,
60                              TopTools_ListOfShape&       theListOfVertexSorted);
61
62 static TopAbs_State GetEdgeState(const BOPDS_PDS& pDS,
63                                  const Handle(BOPDS_PaveBlock)& aPB);
64
65 // ========================================================================================
66 // function: NbPoints
67 // purpose:
68 // ========================================================================================
69 Standard_Integer QANewModTopOpe_Tools::NbPoints(const BOPAlgo_PPaveFiller& theDSFiller) 
70 {
71   Standard_Integer i, anbpoints, aNb;
72   //
73   const BOPDS_PDS& pDS = theDSFiller->PDS();
74   anbpoints = 0;
75
76   //FF
77   BOPDS_VectorOfInterfFF& aFFs=pDS->InterfFF();
78   aNb=aFFs.Extent();
79   for (i = 0; i < aNb; ++i) {
80     BOPDS_InterfFF& aFF=aFFs(i);
81     const BOPDS_VectorOfPoint& aVP=aFF.Points();
82     anbpoints += aVP.Extent();
83   }
84
85   //EF
86   BOPDS_VectorOfInterfEF& aEFs=pDS->InterfEF();
87   aNb = aEFs.Extent();
88   for (i = 0; i < aNb; ++i) {
89     BOPDS_InterfEF& aEF=aEFs(i);
90     IntTools_CommonPrt aCP = aEF.CommonPart();
91     if(aCP.Type() == TopAbs_VERTEX) {
92       anbpoints++;
93     }
94   }
95        
96   //EE
97   BOPDS_VectorOfInterfEE& aEEs=pDS->InterfEE();
98   aNb = aEEs.Extent();
99   for (i = 0; i < aNb; ++i) {
100     BOPDS_InterfEE& aEE=aEEs(i);
101     IntTools_CommonPrt aCP = aEE.CommonPart();
102     if(aCP.Type() == TopAbs_VERTEX) {
103       anbpoints++;
104     }
105   }
106
107   return anbpoints;
108 }
109
110 // ========================================================================================
111 // function: NewVertex
112 // purpose:
113 // ========================================================================================
114 TopoDS_Shape QANewModTopOpe_Tools::NewVertex(const BOPAlgo_PPaveFiller& theDSFiller, 
115                                              const Standard_Integer     theIndex) 
116 {
117   TopoDS_Shape aVertex;
118   Standard_Integer i, j, anbpoints, aNb, aNbP;
119   //
120   const BOPDS_PDS& pDS = theDSFiller->PDS();
121   anbpoints = 0;
122
123   //FF
124   BOPDS_VectorOfInterfFF& aFFs=pDS->InterfFF();
125   aNb=aFFs.Extent();
126   for (i = 0; i < aNb; ++i) {
127     BOPDS_InterfFF& aFF=aFFs(i);
128     const BOPDS_VectorOfPoint& aVP=aFF.Points();
129     aNbP = aVP.Extent();
130     for(j = 0; j < aNbP; ++j) {
131       anbpoints++;
132       //
133       if (theIndex == anbpoints) {
134         const BOPDS_Point& aNP = aVP(j);
135         return pDS->Shape(aNP.Index());
136       }
137     }
138   }
139
140   //EF
141   BOPDS_VectorOfInterfEF& aEFs=pDS->InterfEF();
142   aNb = aEFs.Extent();
143   for (i = 0; i < aNb; ++i) {
144     BOPDS_InterfEF& aEF=aEFs(i);
145     IntTools_CommonPrt aCP = aEF.CommonPart();
146     if(aCP.Type() == TopAbs_VERTEX) {
147       anbpoints++;
148       //
149       if (theIndex == anbpoints) {
150         return pDS->Shape(aEF.IndexNew());
151       }
152     }
153   }
154        
155   //EE
156   BOPDS_VectorOfInterfEE& aEEs=pDS->InterfEE();
157   aNb = aEEs.Extent();
158   for (i = 0; i < aNb; ++i) {
159     BOPDS_InterfEE& aEE=aEEs(i);
160     IntTools_CommonPrt aCP = aEE.CommonPart();
161     if(aCP.Type() == TopAbs_VERTEX) {
162       anbpoints++;
163       //
164       if (theIndex == anbpoints) {
165         return pDS->Shape(aEE.IndexNew());
166       }
167     }
168   }
169
170   return aVertex;
171 }
172
173
174 // ========================================================================================
175 // function: HasDomain
176 // purpose:
177 // ========================================================================================
178 Standard_Boolean QANewModTopOpe_Tools::HasSameDomain(const BOPAlgo_PBOP& theBuilder, 
179                                                      const TopoDS_Shape& theFace) 
180 {
181   Standard_Integer bRet;
182   bRet = Standard_False;
183   //
184   if(theFace.IsNull() || (theFace.ShapeType() != TopAbs_FACE))
185     return bRet;
186
187   BOPCol_ListIteratorOfListOfShape aIt;
188   const BOPCol_DataMapOfShapeListOfShape& aImages = theBuilder->Images();
189   if (!aImages.IsBound(theFace)) {
190     return bRet;
191   }
192   const BOPCol_ListOfShape& aLF=aImages.Find(theFace);
193   
194   if (aLF.Extent() == 0) {
195     return bRet;
196   }
197   const BOPCol_DataMapOfShapeShape& aShapesSD = theBuilder->ShapesSD();
198
199   aIt.Initialize(aLF);
200   for (; aIt.More(); aIt.Next()) {
201     const TopoDS_Shape& aFsp = aIt.Value();
202     if (aShapesSD.IsBound(aFsp)) {
203       bRet = Standard_True;
204       break;
205     }
206   }
207
208   return bRet;
209 }
210
211 // ========================================================================================
212 // function: SameDomain
213 // purpose:
214 // ========================================================================================
215 void QANewModTopOpe_Tools::SameDomain(const BOPAlgo_PBOP&   theBuilder, 
216                                       const TopoDS_Shape&   theFace,
217                                       TopTools_ListOfShape& theResultList) 
218 {
219   theResultList.Clear();
220
221   if(theFace.IsNull() || (theFace.ShapeType() != TopAbs_FACE))
222     return;
223
224   BOPCol_ListIteratorOfListOfShape aIt;
225   const BOPCol_ListOfShape& aLF=theBuilder->Splits().Find(theFace);
226   
227   if (aLF.Extent() == 0) {
228     return;
229   }
230   const BOPCol_DataMapOfShapeShape& aShapesSD = theBuilder->ShapesSD();
231   const BOPCol_DataMapOfShapeShape& aOrigins = theBuilder->Origins();
232   
233   aIt.Initialize(aLF);
234   for (; aIt.More(); aIt.Next()) {
235     const TopoDS_Shape& aFSp = aIt.Value();
236     if (aShapesSD.IsBound(aFSp)) {
237       const TopoDS_Shape& aFSD = aShapesSD.Find(aFSp);
238       const TopoDS_Shape& aFOr = aOrigins.Find(aFSD);
239       if (theFace.IsEqual(aFOr)) {
240         BOPCol_DataMapIteratorOfDataMapOfShapeShape aItSD;
241         aItSD.Initialize(aShapesSD);
242         for (; aItSD.More(); aItSD.Next()) {
243           const TopoDS_Shape& aS = aItSD.Value();
244           if (aFSD.IsEqual(aS)) {
245             const TopoDS_Shape& aSK = aItSD.Key();
246             const TopoDS_Shape& aSKOr = aOrigins.Find(aSK);
247             if (!aSKOr.IsEqual(theFace)) {
248               theResultList.Append(aSKOr);
249             }
250           }
251         }
252       } else {
253         theResultList.Append(aFOr);
254       }
255     }
256   }
257 }
258
259 // ========================================================================================
260 // function: IsSplit
261 // purpose:
262 // ========================================================================================
263 Standard_Boolean QANewModTopOpe_Tools::IsSplit(const BOPAlgo_PPaveFiller& theDSFiller,
264                                           const TopoDS_Shape&       theEdge,
265                                           const TopAbs_State        theState) 
266 {
267   if(theEdge.IsNull() || (theEdge.ShapeType() != TopAbs_EDGE))
268     return Standard_False;
269
270   Standard_Integer index;
271   //
272   const BOPDS_PDS& pDS = theDSFiller->PDS();
273   index = pDS->Index(theEdge);
274   if (index == -1) {
275     return Standard_False;
276   }
277
278   const BOPDS_ListOfPaveBlock& aLPB = pDS->PaveBlocks(index);
279   BOPDS_ListIteratorOfListOfPaveBlock aPBIt;
280   aPBIt.Initialize(aLPB);
281   for (; aPBIt.More(); aPBIt.Next()) {
282     const Handle(BOPDS_PaveBlock)& aPB = aPBIt.Value();
283
284     TopAbs_State aSplitState = GetEdgeState(pDS, aPB);
285
286     if(aSplitState == theState) {
287       return Standard_True;
288     }
289   }
290
291   return Standard_False;
292 }
293
294 // ========================================================================================
295 // function: Splits
296 // purpose:
297 // ========================================================================================
298 void QANewModTopOpe_Tools::Splits(const BOPAlgo_PPaveFiller& theDSFiller,
299                              const TopoDS_Shape&       theEdge,
300                              const TopAbs_State        theState,
301                              TopTools_ListOfShape&     theResultList) 
302 {
303   theResultList.Clear();
304
305   if(theEdge.IsNull() || (theEdge.ShapeType() != TopAbs_EDGE))
306     return;
307
308   Standard_Integer index, nSp;
309   //
310   const BOPDS_PDS& pDS = theDSFiller->PDS();
311   index = pDS->Index(theEdge);
312   if (index == -1) {
313     return;
314   }
315
316   const BOPDS_ListOfPaveBlock& aLPB = pDS->PaveBlocks(index);
317   BOPDS_ListIteratorOfListOfPaveBlock aPBIt;
318   aPBIt.Initialize(aLPB);
319   for (; aPBIt.More(); aPBIt.Next()) {
320     const Handle(BOPDS_PaveBlock)& aPB = aPBIt.Value();
321     nSp = aPB->Edge();
322
323     TopAbs_State aSplitState = GetEdgeState(pDS, aPB);
324
325     if(aSplitState == theState) {
326       TopoDS_Shape aSplit = pDS->Shape(nSp);
327       theResultList.Append(aSplit);
328     }
329   }
330 }
331
332 // ========================================================================================
333 // function: SplitE
334 // purpose:
335 // ========================================================================================
336 Standard_Boolean QANewModTopOpe_Tools::SplitE(const TopoDS_Edge&    theEdge,
337                                          TopTools_ListOfShape& theSplits) 
338 {
339   // prequesitory : <Eanc> is a valid edge.
340   TopAbs_Orientation oEanc = theEdge.Orientation();
341   TopoDS_Shape aLocalShape = theEdge.Oriented(TopAbs_FORWARD);
342   TopoDS_Edge EFOR = TopoDS::Edge(aLocalShape);
343   TopTools_ListOfShape aListOfVertex;
344   TopExp_Explorer exv(EFOR,TopAbs_VERTEX);  
345
346   for (;exv.More(); exv.Next()) {
347     const TopoDS_Shape& v = exv.Current();
348     aListOfVertex.Append(v);
349   }
350   Standard_Integer nv = aListOfVertex.Extent();
351
352   if (nv <= 2) return Standard_False;
353   TopTools_ListOfShape aListOfVertexSorted;
354
355   SortVertexOnEdge(EFOR, aListOfVertex, aListOfVertexSorted);
356
357   TopoDS_Vertex v0;
358   TopTools_ListIteratorOfListOfShape anIt(aListOfVertexSorted);
359
360   if (anIt.More()) {
361     v0 = TopoDS::Vertex(anIt.Value()); 
362     anIt.Next();
363   }
364   else return Standard_False;
365
366   for (; anIt.More(); anIt.Next()) {
367     TopoDS_Vertex v = TopoDS::Vertex(anIt.Value());
368     
369     // prequesitory: par0 < par
370     Standard_Real par0 = BRep_Tool::Parameter(v0, EFOR);
371     Standard_Real par  = BRep_Tool::Parameter(v, EFOR);
372
373     // here, ed has the same geometries than Ein, but with no subshapes.
374     TopoDS_Edge ed = TopoDS::Edge(EFOR.EmptyCopied());
375     BRep_Builder BB;
376     v0.Orientation(TopAbs_FORWARD); 
377     BB.Add(ed, v0);
378     v.Orientation(TopAbs_REVERSED); 
379     BB.Add(ed, v);
380     BB.Range(ed, par0, par);
381
382     theSplits.Append(ed.Oriented(oEanc));
383     v0 = v;
384   }
385   return Standard_True;
386 }
387
388
389 // ========================================================================================
390 // function: EdgeCurveAncestors
391 // purpose:
392 // ========================================================================================
393  Standard_Boolean QANewModTopOpe_Tools::EdgeCurveAncestors(const BOPAlgo_PPaveFiller& theDSFiller,
394                                                       const TopoDS_Shape&       theEdge,
395                                                       TopoDS_Shape&             theFace1,
396                                                       TopoDS_Shape&             theFace2) 
397 {
398   theFace1.Nullify();
399   theFace2.Nullify();
400   //
401   Standard_Integer i, j, aNb, aNbC, nE, nF1, nF2;
402   BOPDS_ListIteratorOfListOfPaveBlock aIt;
403
404   const BOPDS_PDS& pDS = theDSFiller->PDS();
405   BOPDS_VectorOfInterfFF& aFFs=pDS->InterfFF();
406
407   aNb=aFFs.Extent();
408   for (i = 0; i < aNb; ++i) {
409     BOPDS_InterfFF& aFF=aFFs(i);
410     
411     const BOPDS_VectorOfCurve& aVC = aFF.Curves();
412     aNbC = aVC.Extent();
413     for (j = 0; j < aNbC; ++j) {
414       const BOPDS_Curve& aNC = aVC(j);
415       const BOPDS_ListOfPaveBlock& aLPB = aNC.PaveBlocks();
416       aIt.Initialize(aLPB);
417       for (; aIt.More(); aIt.Next()) {
418         const Handle(BOPDS_PaveBlock)& aPB = aIt.Value();
419         nE = aPB->Edge();
420         const TopoDS_Shape& aE = pDS->Shape(nE);
421         if (theEdge.IsSame(aE)) {
422           aFF.Indices(nF1, nF2);
423           theFace1 = pDS->Shape(nF1);
424           theFace2 = pDS->Shape(nF2);
425           return Standard_True;
426         }
427       }
428     }
429   }
430
431   return Standard_False;
432 }
433
434 // ========================================================================================
435 // function: EdgeSectionAncestors
436 // purpose:
437 // ========================================================================================
438 Standard_Boolean QANewModTopOpe_Tools::EdgeSectionAncestors(const BOPAlgo_PPaveFiller& theDSFiller,
439                                                             const TopoDS_Shape&       theEdge,
440                                                             TopTools_ListOfShape&     LF1,
441                                                             TopTools_ListOfShape&     LF2,
442                                                             TopTools_ListOfShape&     LE1,
443                                                             TopTools_ListOfShape&     LE2) 
444 {
445   if(theEdge.ShapeType() != TopAbs_EDGE)
446     return Standard_False;
447   
448   const BOPDS_PDS& pDS = theDSFiller->PDS();
449   Standard_Integer i = 0, nb = 0, nF, nE, nEOr;
450   BOPCol_MapOfInteger aMIF;
451   nb = pDS->NbSourceShapes();
452
453   nE = pDS->Index(theEdge);
454   const BOPDS_ListOfPaveBlock& aLPB1 = pDS->PaveBlocks(nE);
455   if (!aLPB1.Extent()) {
456     return Standard_False;
457   }
458
459   const Handle(BOPDS_PaveBlock)& aPB1 = aLPB1.First();
460   const Handle(BOPDS_CommonBlock)& aCB=pDS->CommonBlock(aPB1);
461   if (aCB.IsNull()) {
462     return Standard_False;
463   }
464   
465   const BOPCol_ListOfInteger& aLIF = aCB->Faces();
466   BOPCol_ListIteratorOfListOfInteger aItLI;
467   aItLI.Initialize(aLIF);
468   for ( ; aItLI.More(); aItLI.Next()) {
469     nF = aItLI.Value();
470     if(pDS->Rank(nF) == 0)
471       LF1.Append(pDS->Shape(nF));
472     else
473       LF2.Append(pDS->Shape(nF));
474     
475     aMIF.Add(nF);
476   }
477
478   const BOPDS_ListOfPaveBlock& aLPB = aCB->PaveBlocks();
479   BOPDS_ListIteratorOfListOfPaveBlock aItPB;
480   aItPB.Initialize(aLPB);
481   for (; aItPB.More(); aItPB.Next()) {
482     const Handle(BOPDS_PaveBlock)& aPB = aItPB.Value();
483     nEOr = aPB->OriginalEdge();
484
485     if(pDS->Rank(nEOr) == 0)
486       LE1.Append(pDS->Shape(nEOr));
487     else
488       LE2.Append(pDS->Shape(nEOr));
489
490     //find edge ancestors
491     for(i = 0; i < nb; ++i) {
492       const BOPDS_ShapeInfo& aSI = pDS->ShapeInfo(i);
493       if(aSI.ShapeType() != TopAbs_FACE) {
494         continue;
495       }
496       const BOPCol_ListOfInteger& aSubShapes = aSI.SubShapes();
497       aItLI.Initialize(aSubShapes);
498       for (; aItLI.More(); aItLI.Next()) {
499         if (nEOr == aItLI.Value()) {
500           if (aMIF.Add(i)) {
501             if(pDS->Rank(i) == 0) LF1.Append(pDS->Shape(i));
502             else LF2.Append(pDS->Shape(i));
503           }//if (aMIF.Add(i)) {
504         }//if (nEOr == aItLI.Value()) {
505       }//for (; aItLI.More(); aItLI.Next()) {
506     }//for(i = 0; i < nb; ++i) {
507   }
508
509   Standard_Boolean r = (!LF1.IsEmpty() && !LF2.IsEmpty());
510   r = r && (!LE1.IsEmpty() || !LE2.IsEmpty());
511   return r;
512 }
513
514 // ========================================================================================
515 // function: BoolOpe
516 // purpose:
517 // ========================================================================================
518 Standard_Boolean QANewModTopOpe_Tools::BoolOpe(const TopoDS_Shape& theFace1,
519                                                const TopoDS_Shape& theFace2,
520                                                Standard_Boolean&   IsCommonFound,
521                                                TopTools_IndexedDataMapOfShapeListOfShape& theHistoryMap) 
522 {
523   IsCommonFound = Standard_False;
524   theHistoryMap.Clear();
525   gp_Dir aDNF1, aDNF2;
526   Standard_Integer iSenseFlag;
527
528   BOPAlgo_PaveFiller aDSFiller;
529   BOPCol_ListOfShape aLS;
530   aLS.Append(theFace1);
531   aLS.Append(theFace2);
532   aDSFiller.SetArguments(aLS);
533   
534   aDSFiller.Perform();
535   if (aDSFiller.ErrorStatus()) {
536     return Standard_False;
537   }
538   
539   const BOPDS_PDS& pDS = aDSFiller.PDS();
540
541   Standard_Integer aNb = 0, aNbSps;
542   Standard_Integer i = 0;
543   TopTools_IndexedMapOfShape aMapV;
544
545   {
546     BRepAlgoAPI_Common aCommon(theFace1, theFace2, aDSFiller);
547
548     if(!aCommon.IsDone()) {
549       return Standard_False;
550     }
551
552     TopExp_Explorer anExp(aCommon.Shape(), TopAbs_FACE);
553     if(!anExp.More()) {
554       IsCommonFound = Standard_False;
555       return Standard_True;
556     }
557
558     IsCommonFound = Standard_True;
559     TopExp::MapShapes(aCommon.Shape(), TopAbs_VERTEX, aMapV);
560     // fill edge history.begin
561     FillEdgeHistoryMap(aCommon, theHistoryMap);
562     // fill edge history.end
563
564     // fill face history.begin
565     BOPDS_VectorOfInterfFF& aFFs = pDS->InterfFF();
566     aNb = aFFs.Extent();
567     Standard_Boolean bReverseFlag = Standard_True;
568     Standard_Boolean fillhistory = Standard_True;
569
570     for (i=0; i<aNb; ++i) {
571       BOPDS_InterfFF& aFF = aFFs(i);
572       Standard_Integer nF1, nF2;
573       aFF.Indices(nF1, nF2);
574     
575       const TopoDS_Face& aF1 = *(TopoDS_Face*)(&pDS->Shape(nF1));
576       const TopoDS_Face& aF2 = *(TopoDS_Face*)(&pDS->Shape(nF2));
577
578       BOPCol_ListOfInteger aLSE;
579       pDS->SharedEdges(nF1, nF2, aLSE, aDSFiller.Allocator());
580       aNbSps = aLSE.Extent();
581       
582       if (!aNbSps) {
583         fillhistory = Standard_False;
584         continue;
585       }
586       
587       Standard_Integer nE = aLSE.First();
588       const TopoDS_Edge& aSpE = *(TopoDS_Edge*)(&pDS->Shape(nE));
589     
590       BOPTools_AlgoTools3D::GetNormalToFaceOnEdge (aSpE, aF1, aDNF1); 
591       BOPTools_AlgoTools3D::GetNormalToFaceOnEdge (aSpE, aF2, aDNF2);
592       iSenseFlag=BOPTools_AlgoTools3D::SenseFlag (aDNF1, aDNF2);
593
594       if(iSenseFlag == 1) {
595         fillhistory = Standard_True;
596         bReverseFlag = Standard_False;
597       }
598       else if(iSenseFlag == -1) {
599         fillhistory = Standard_True;
600         bReverseFlag = Standard_True;
601       }
602       else
603         fillhistory = Standard_False;
604     }
605
606     if(fillhistory) {
607
608       for(; anExp.More(); anExp.Next()) {
609         TopoDS_Shape aResShape = anExp.Current();
610
611         if(theFace1.Orientation() == aResShape.Orientation()) {
612           AddShapeToHistoryMap(theFace1, aResShape, theHistoryMap);
613
614           if(bReverseFlag)
615             aResShape.Reverse();
616           AddShapeToHistoryMap(theFace2, aResShape, theHistoryMap);
617         }
618         else if(theFace2.Orientation() == aResShape.Orientation()) {
619           AddShapeToHistoryMap(theFace2, aResShape, theHistoryMap);
620
621           if(bReverseFlag)
622             aResShape.Reverse();
623           AddShapeToHistoryMap(theFace1, aResShape, theHistoryMap);
624         }
625         else {
626           aResShape.Orientation(theFace1.Orientation());
627           AddShapeToHistoryMap(theFace1, aResShape, theHistoryMap);
628           aResShape.Orientation(theFace2.Orientation());
629
630           if(bReverseFlag)
631             aResShape.Reverse();
632           AddShapeToHistoryMap(theFace2, aResShape, theHistoryMap);
633         }
634       }
635     }
636     // fill face history.end
637   }
638   {
639     BRepAlgoAPI_Cut aCut1(theFace1, theFace2, aDSFiller);
640
641     if(!aCut1.IsDone())
642       return Standard_False;
643     TopExp::MapShapes(aCut1.Shape(), TopAbs_VERTEX, aMapV);
644     // fill edge history.begin
645     FillEdgeHistoryMap(aCut1, theHistoryMap);
646     // fill edge history.end
647
648     // fill face history.begin
649     TopExp_Explorer anExp(aCut1.Shape(), TopAbs_FACE);
650
651     for(; anExp.More(); anExp.Next()) {
652       TopoDS_Shape aResShape = anExp.Current();
653       aResShape.Orientation(theFace1.Orientation());
654       AddShapeToHistoryMap(theFace1, aResShape, theHistoryMap);
655     }
656     // fill face history.end
657   }
658
659   {
660     BRepAlgoAPI_Cut aCut2(theFace1, theFace2, aDSFiller, Standard_False);
661
662     if(!aCut2.IsDone())
663       return Standard_False;
664     TopExp::MapShapes(aCut2.Shape(), TopAbs_VERTEX, aMapV);
665     // fill edge history.begin
666     FillEdgeHistoryMap(aCut2, theHistoryMap);
667     // fill edge history.end
668
669     // fill face history.begin
670     TopExp_Explorer anExp(aCut2.Shape(), TopAbs_FACE);
671
672     for(; anExp.More(); anExp.Next()) {
673       TopoDS_Shape aResShape = anExp.Current();
674       aResShape.Orientation(theFace2.Orientation());
675       AddShapeToHistoryMap(theFace2, aResShape, theHistoryMap);
676     }
677     // fill face history.end
678   }
679   
680   // fill vertex history.begin
681   BOPDS_VectorOfInterfVV& aVVs = pDS->InterfVV();
682   aNb = aVVs.Extent();
683
684   for (i = 0; i < aNb; ++i) {
685     BOPDS_InterfVV& aVVi = aVVs(i);
686     if (!aVVi.HasIndexNew()) {
687       continue;
688     }
689     Standard_Integer aNewShapeIndex = aVVi.IndexNew();
690
691     const TopoDS_Shape& aNewVertex = pDS->Shape(aNewShapeIndex);
692
693     if(!aMapV.Contains(aNewVertex)) {
694       continue;
695     }
696     
697     const TopoDS_Shape& aV1 = pDS->Shape(aVVi.Index1());
698     const TopoDS_Shape& aV2 = pDS->Shape(aVVi.Index2());
699     AddShapeToHistoryMap(aV1, aNewVertex, theHistoryMap);
700     AddShapeToHistoryMap(aV2, aNewVertex, theHistoryMap);
701   }
702
703   BOPDS_VectorOfInterfVE& aVEs = pDS->InterfVE();
704   aNb = aVEs.Extent();
705
706   for (i = 0; i < aNb; ++i) {
707     BOPDS_InterfVE& aVEi = aVEs(i);
708     
709     Standard_Integer anIndex = aVEi.Index1();
710     const TopoDS_Shape& aNewVertex = pDS->Shape(anIndex);
711
712     if(!aMapV.Contains(aNewVertex))
713       continue;
714
715     AddShapeToHistoryMap(aNewVertex, aNewVertex, theHistoryMap);
716   }
717
718   BOPDS_VectorOfInterfVF& aVSs = pDS->InterfVF();
719   aNb = aVSs.Extent();
720
721   for (i = 0; i < aNb; ++i) {
722     BOPDS_InterfVF& aVSi = aVSs(i);
723
724     Standard_Integer anIndex = aVSi.Index1();
725     const TopoDS_Shape& aNewVertex = pDS->Shape(anIndex);
726
727     if(!aMapV.Contains(aNewVertex))
728       continue;
729
730     AddShapeToHistoryMap(aNewVertex, aNewVertex, theHistoryMap);
731   }
732   // fill vertex history.end
733   return Standard_True;
734 }
735
736 // --------------------------------------------------------------------------------------------
737 // static function: AddShapeToHistoryMap
738 // purpose: 
739 // --------------------------------------------------------------------------------------------
740 Standard_Boolean AddShapeToHistoryMap(const TopoDS_Shape& theOldShape,
741                                       const TopoDS_Shape& theNewShape,
742                                       TopTools_IndexedDataMapOfShapeListOfShape& theHistoryMap) {
743
744   if(!theHistoryMap.Contains(theOldShape)) {
745     TopTools_ListOfShape aList;
746     aList.Append(theNewShape);
747     theHistoryMap.Add(theOldShape, aList);
748     return Standard_True;
749   }
750   
751   Standard_Boolean found = Standard_False;
752   TopTools_ListOfShape& aList = theHistoryMap.ChangeFromKey(theOldShape);
753   TopTools_ListIteratorOfListOfShape aVIt(aList);
754
755   for(; aVIt.More(); aVIt.Next()) {
756     if(theNewShape.IsSame(aVIt.Value())) {
757       found = Standard_True;
758       break;
759     }
760   }
761
762   if(!found) {
763     aList.Append(theNewShape);
764   }
765   return !found;
766 }
767
768 // --------------------------------------------------------------------------------------------
769 // static function: FillEdgeHistoryMap
770 // purpose: 
771 // --------------------------------------------------------------------------------------------
772 void FillEdgeHistoryMap(BRepAlgoAPI_BooleanOperation&              theBOP,
773                         TopTools_IndexedDataMapOfShapeListOfShape& theHistoryMap) {
774
775   TopExp_Explorer anExp;
776   anExp.Init(theBOP.Shape1(), TopAbs_EDGE);
777
778   for(; anExp.More(); anExp.Next()) {
779     const TopTools_ListOfShape& aList = theBOP.Modified(anExp.Current());
780     TopTools_ListIteratorOfListOfShape anIt(aList);
781
782     for(; anIt.More(); anIt.Next()) {
783       AddShapeToHistoryMap(anExp.Current(), anIt.Value(), theHistoryMap);
784     }
785   }
786
787   anExp.Init(theBOP.Shape2(), TopAbs_EDGE);
788
789   for(; anExp.More(); anExp.Next()) {
790     const TopTools_ListOfShape& aList = theBOP.Modified(anExp.Current());
791     TopTools_ListIteratorOfListOfShape anIt(aList);
792
793     for(; anIt.More(); anIt.Next()) {
794       AddShapeToHistoryMap(anExp.Current(), anIt.Value(), theHistoryMap);
795     }
796   }
797 }
798
799 // --------------------------------------------------------------------------------------------
800 // static function: SortVertexOnEdge
801 // purpose: 
802 // --------------------------------------------------------------------------------------------
803 void SortVertexOnEdge(const TopoDS_Edge&          theEdge,
804                       const TopTools_ListOfShape& theListOfVertex,
805                       TopTools_ListOfShape&       theListOfVertexSorted) {
806
807   TopTools_DataMapOfIntegerShape mapiv;// mapiv.Find(iV) = V
808   TColStd_IndexedMapOfReal mappar;     // mappar.FindIndex(parV) = iV
809   TopTools_ListIteratorOfListOfShape itlove(theListOfVertex);
810   
811   for (; itlove.More(); itlove.Next()){
812     const TopoDS_Vertex& v = TopoDS::Vertex(itlove.Value());
813     Standard_Real par = BRep_Tool::Parameter(v, theEdge);
814     Standard_Integer iv = mappar.Add(par);
815     mapiv.Bind(iv,v);
816   }
817   Standard_Integer nv = mapiv.Extent();
818   NCollection_Array1<Standard_Real> tabpar(1,nv);
819   Standard_Integer i = 0;
820
821   for ( i = 1; i <= nv; i++) {
822     Standard_Real p = mappar.FindKey(i);
823     tabpar.SetValue(i,p);
824   }
825   theListOfVertexSorted.Clear();
826   std::sort (tabpar.begin(), tabpar.end());
827
828   for (i = 1; i <= nv; i++) {
829     Standard_Real par = tabpar.Value(i);
830     Standard_Integer iv = mappar.FindIndex(par);
831     const TopoDS_Shape& v = mapiv.Find(iv);
832     theListOfVertexSorted.Append(v);
833   }
834 }
835
836 // --------------------------------------------------------------------------------------------
837 // static function: GetEdgeState
838 // purpose: 
839 // --------------------------------------------------------------------------------------------
840   static TopAbs_State GetEdgeState(const BOPDS_PDS& pDS,
841                                    const Handle(BOPDS_PaveBlock)& aPB) 
842 {
843   Standard_Integer j, aNbFI;
844   Standard_Boolean bIn;
845   TopAbs_State aState = TopAbs_ON;
846   //
847   const BOPDS_VectorOfFaceInfo& aVFI = pDS->FaceInfoPool();
848   aNbFI = aVFI.Extent();
849   //
850   for (j = 0; j < aNbFI; ++j) {
851     const BOPDS_FaceInfo& aFI = aVFI(j);
852     bIn = aFI.PaveBlocksIn().Contains(aPB);
853     if (bIn) {
854       aState = TopAbs_IN;
855       break;
856     }
857   }
858   return aState;
859 }