0025354: Intersection operation
[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
179   (const BOPAlgo_PBuilder& theBuilder, 
180    const TopoDS_Shape& theFace) 
181 {
182   Standard_Integer bRet;
183   bRet = Standard_False;
184   //
185   if(theFace.IsNull() || (theFace.ShapeType() != TopAbs_FACE))
186     return bRet;
187
188   BOPCol_ListIteratorOfListOfShape aIt;
189   const BOPCol_DataMapOfShapeListOfShape& aImages = theBuilder->Images();
190   if (!aImages.IsBound(theFace)) {
191     return bRet;
192   }
193   const BOPCol_ListOfShape& aLF=aImages.Find(theFace);
194   
195   if (aLF.Extent() == 0) {
196     return bRet;
197   }
198   const BOPCol_DataMapOfShapeShape& aShapesSD = theBuilder->ShapesSD();
199
200   aIt.Initialize(aLF);
201   for (; aIt.More(); aIt.Next()) {
202     const TopoDS_Shape& aFsp = aIt.Value();
203     if (aShapesSD.IsBound(aFsp)) {
204       bRet = Standard_True;
205       break;
206     }
207   }
208
209   return bRet;
210 }
211
212 // ========================================================================================
213 // function: SameDomain
214 // purpose:
215 // ========================================================================================
216 void QANewModTopOpe_Tools::SameDomain
217   (const BOPAlgo_PBuilder&   theBuilder, 
218    const TopoDS_Shape&   theFace,
219    TopTools_ListOfShape& theResultList) 
220 {
221   theResultList.Clear();
222
223   if(theFace.IsNull() || (theFace.ShapeType() != TopAbs_FACE))
224     return;
225
226   BOPCol_ListIteratorOfListOfShape aIt;
227   const BOPCol_ListOfShape& aLF=theBuilder->Splits().Find(theFace);
228   
229   if (aLF.Extent() == 0) {
230     return;
231   }
232   const BOPCol_DataMapOfShapeShape& aShapesSD = theBuilder->ShapesSD();
233   const BOPCol_DataMapOfShapeShape& aOrigins = theBuilder->Origins();
234   
235   aIt.Initialize(aLF);
236   for (; aIt.More(); aIt.Next()) {
237     const TopoDS_Shape& aFSp = aIt.Value();
238     if (aShapesSD.IsBound(aFSp)) {
239       const TopoDS_Shape& aFSD = aShapesSD.Find(aFSp);
240       const TopoDS_Shape& aFOr = aOrigins.Find(aFSD);
241       if (theFace.IsEqual(aFOr)) {
242         BOPCol_DataMapIteratorOfDataMapOfShapeShape aItSD;
243         aItSD.Initialize(aShapesSD);
244         for (; aItSD.More(); aItSD.Next()) {
245           const TopoDS_Shape& aS = aItSD.Value();
246           if (aFSD.IsEqual(aS)) {
247             const TopoDS_Shape& aSK = aItSD.Key();
248             const TopoDS_Shape& aSKOr = aOrigins.Find(aSK);
249             if (!aSKOr.IsEqual(theFace)) {
250               theResultList.Append(aSKOr);
251             }
252           }
253         }
254       } else {
255         theResultList.Append(aFOr);
256       }
257     }
258   }
259 }
260
261 // ========================================================================================
262 // function: IsSplit
263 // purpose:
264 // ========================================================================================
265 Standard_Boolean QANewModTopOpe_Tools::IsSplit(const BOPAlgo_PPaveFiller& theDSFiller,
266                                           const TopoDS_Shape&       theEdge,
267                                           const TopAbs_State        theState) 
268 {
269   if(theEdge.IsNull() || (theEdge.ShapeType() != TopAbs_EDGE))
270     return Standard_False;
271
272   Standard_Integer index;
273   //
274   const BOPDS_PDS& pDS = theDSFiller->PDS();
275   index = pDS->Index(theEdge);
276   if (index == -1) {
277     return Standard_False;
278   }
279
280   const BOPDS_ListOfPaveBlock& aLPB = pDS->PaveBlocks(index);
281   BOPDS_ListIteratorOfListOfPaveBlock aPBIt;
282   aPBIt.Initialize(aLPB);
283   for (; aPBIt.More(); aPBIt.Next()) {
284     const Handle(BOPDS_PaveBlock)& aPB = aPBIt.Value();
285
286     TopAbs_State aSplitState = GetEdgeState(pDS, aPB);
287
288     if(aSplitState == theState) {
289       return Standard_True;
290     }
291   }
292
293   return Standard_False;
294 }
295
296 // ========================================================================================
297 // function: Splits
298 // purpose:
299 // ========================================================================================
300 void QANewModTopOpe_Tools::Splits(const BOPAlgo_PPaveFiller& theDSFiller,
301                              const TopoDS_Shape&       theEdge,
302                              const TopAbs_State        theState,
303                              TopTools_ListOfShape&     theResultList) 
304 {
305   theResultList.Clear();
306
307   if(theEdge.IsNull() || (theEdge.ShapeType() != TopAbs_EDGE))
308     return;
309
310   Standard_Integer index, nSp;
311   //
312   const BOPDS_PDS& pDS = theDSFiller->PDS();
313   index = pDS->Index(theEdge);
314   if (index == -1) {
315     return;
316   }
317
318   const BOPDS_ListOfPaveBlock& aLPB = pDS->PaveBlocks(index);
319   BOPDS_ListIteratorOfListOfPaveBlock aPBIt;
320   aPBIt.Initialize(aLPB);
321   for (; aPBIt.More(); aPBIt.Next()) {
322     const Handle(BOPDS_PaveBlock)& aPB = aPBIt.Value();
323     nSp = aPB->Edge();
324
325     TopAbs_State aSplitState = GetEdgeState(pDS, aPB);
326
327     if(aSplitState == theState) {
328       TopoDS_Shape aSplit = pDS->Shape(nSp);
329       theResultList.Append(aSplit);
330     }
331   }
332 }
333
334 // ========================================================================================
335 // function: SplitE
336 // purpose:
337 // ========================================================================================
338 Standard_Boolean QANewModTopOpe_Tools::SplitE(const TopoDS_Edge&    theEdge,
339                                          TopTools_ListOfShape& theSplits) 
340 {
341   // prequesitory : <Eanc> is a valid edge.
342   TopAbs_Orientation oEanc = theEdge.Orientation();
343   TopoDS_Shape aLocalShape = theEdge.Oriented(TopAbs_FORWARD);
344   TopoDS_Edge EFOR = TopoDS::Edge(aLocalShape);
345   TopTools_ListOfShape aListOfVertex;
346   TopExp_Explorer exv(EFOR,TopAbs_VERTEX);  
347
348   for (;exv.More(); exv.Next()) {
349     const TopoDS_Shape& v = exv.Current();
350     aListOfVertex.Append(v);
351   }
352   Standard_Integer nv = aListOfVertex.Extent();
353
354   if (nv <= 2) return Standard_False;
355   TopTools_ListOfShape aListOfVertexSorted;
356
357   SortVertexOnEdge(EFOR, aListOfVertex, aListOfVertexSorted);
358
359   TopoDS_Vertex v0;
360   TopTools_ListIteratorOfListOfShape anIt(aListOfVertexSorted);
361
362   if (anIt.More()) {
363     v0 = TopoDS::Vertex(anIt.Value()); 
364     anIt.Next();
365   }
366   else return Standard_False;
367
368   for (; anIt.More(); anIt.Next()) {
369     TopoDS_Vertex v = TopoDS::Vertex(anIt.Value());
370     
371     // prequesitory: par0 < par
372     Standard_Real par0 = BRep_Tool::Parameter(v0, EFOR);
373     Standard_Real par  = BRep_Tool::Parameter(v, EFOR);
374
375     // here, ed has the same geometries than Ein, but with no subshapes.
376     TopoDS_Edge ed = TopoDS::Edge(EFOR.EmptyCopied());
377     BRep_Builder BB;
378     v0.Orientation(TopAbs_FORWARD); 
379     BB.Add(ed, v0);
380     v.Orientation(TopAbs_REVERSED); 
381     BB.Add(ed, v);
382     BB.Range(ed, par0, par);
383
384     theSplits.Append(ed.Oriented(oEanc));
385     v0 = v;
386   }
387   return Standard_True;
388 }
389
390
391 // ========================================================================================
392 // function: EdgeCurveAncestors
393 // purpose:
394 // ========================================================================================
395  Standard_Boolean QANewModTopOpe_Tools::EdgeCurveAncestors(const BOPAlgo_PPaveFiller& theDSFiller,
396                                                       const TopoDS_Shape&       theEdge,
397                                                       TopoDS_Shape&             theFace1,
398                                                       TopoDS_Shape&             theFace2) 
399 {
400   theFace1.Nullify();
401   theFace2.Nullify();
402   //
403   Standard_Integer i, j, aNb, aNbC, nE, nF1, nF2;
404   BOPDS_ListIteratorOfListOfPaveBlock aIt;
405
406   const BOPDS_PDS& pDS = theDSFiller->PDS();
407   BOPDS_VectorOfInterfFF& aFFs=pDS->InterfFF();
408
409   aNb=aFFs.Extent();
410   for (i = 0; i < aNb; ++i) {
411     BOPDS_InterfFF& aFF=aFFs(i);
412     
413     const BOPDS_VectorOfCurve& aVC = aFF.Curves();
414     aNbC = aVC.Extent();
415     for (j = 0; j < aNbC; ++j) {
416       const BOPDS_Curve& aNC = aVC(j);
417       const BOPDS_ListOfPaveBlock& aLPB = aNC.PaveBlocks();
418       aIt.Initialize(aLPB);
419       for (; aIt.More(); aIt.Next()) {
420         const Handle(BOPDS_PaveBlock)& aPB = aIt.Value();
421         nE = aPB->Edge();
422         const TopoDS_Shape& aE = pDS->Shape(nE);
423         if (theEdge.IsSame(aE)) {
424           aFF.Indices(nF1, nF2);
425           theFace1 = pDS->Shape(nF1);
426           theFace2 = pDS->Shape(nF2);
427           return Standard_True;
428         }
429       }
430     }
431   }
432
433   return Standard_False;
434 }
435
436 // ========================================================================================
437 // function: EdgeSectionAncestors
438 // purpose:
439 // ========================================================================================
440 Standard_Boolean QANewModTopOpe_Tools::EdgeSectionAncestors(const BOPAlgo_PPaveFiller& theDSFiller,
441                                                             const TopoDS_Shape&       theEdge,
442                                                             TopTools_ListOfShape&     LF1,
443                                                             TopTools_ListOfShape&     LF2,
444                                                             TopTools_ListOfShape&     LE1,
445                                                             TopTools_ListOfShape&     LE2) 
446 {
447   if(theEdge.ShapeType() != TopAbs_EDGE)
448     return Standard_False;
449   
450   const BOPDS_PDS& pDS = theDSFiller->PDS();
451   Standard_Integer i = 0, nb = 0, nF, nE, nEOr;
452   BOPCol_MapOfInteger aMIF;
453   nb = pDS->NbSourceShapes();
454
455   nE = pDS->Index(theEdge);
456   const BOPDS_ListOfPaveBlock& aLPB1 = pDS->PaveBlocks(nE);
457   if (!aLPB1.Extent()) {
458     return Standard_False;
459   }
460
461   const Handle(BOPDS_PaveBlock)& aPB1 = aLPB1.First();
462   const Handle(BOPDS_CommonBlock)& aCB=pDS->CommonBlock(aPB1);
463   if (aCB.IsNull()) {
464     return Standard_False;
465   }
466   
467   const BOPCol_ListOfInteger& aLIF = aCB->Faces();
468   BOPCol_ListIteratorOfListOfInteger aItLI;
469   aItLI.Initialize(aLIF);
470   for ( ; aItLI.More(); aItLI.Next()) {
471     nF = aItLI.Value();
472     if(pDS->Rank(nF) == 0)
473       LF1.Append(pDS->Shape(nF));
474     else
475       LF2.Append(pDS->Shape(nF));
476     
477     aMIF.Add(nF);
478   }
479
480   const BOPDS_ListOfPaveBlock& aLPB = aCB->PaveBlocks();
481   BOPDS_ListIteratorOfListOfPaveBlock aItPB;
482   aItPB.Initialize(aLPB);
483   for (; aItPB.More(); aItPB.Next()) {
484     const Handle(BOPDS_PaveBlock)& aPB = aItPB.Value();
485     nEOr = aPB->OriginalEdge();
486
487     if(pDS->Rank(nEOr) == 0)
488       LE1.Append(pDS->Shape(nEOr));
489     else
490       LE2.Append(pDS->Shape(nEOr));
491
492     //find edge ancestors
493     for(i = 0; i < nb; ++i) {
494       const BOPDS_ShapeInfo& aSI = pDS->ShapeInfo(i);
495       if(aSI.ShapeType() != TopAbs_FACE) {
496         continue;
497       }
498       const BOPCol_ListOfInteger& aSubShapes = aSI.SubShapes();
499       aItLI.Initialize(aSubShapes);
500       for (; aItLI.More(); aItLI.Next()) {
501         if (nEOr == aItLI.Value()) {
502           if (aMIF.Add(i)) {
503             if(pDS->Rank(i) == 0) LF1.Append(pDS->Shape(i));
504             else LF2.Append(pDS->Shape(i));
505           }//if (aMIF.Add(i)) {
506         }//if (nEOr == aItLI.Value()) {
507       }//for (; aItLI.More(); aItLI.Next()) {
508     }//for(i = 0; i < nb; ++i) {
509   }
510
511   Standard_Boolean r = (!LF1.IsEmpty() && !LF2.IsEmpty());
512   r = r && (!LE1.IsEmpty() || !LE2.IsEmpty());
513   return r;
514 }
515
516 // ========================================================================================
517 // function: BoolOpe
518 // purpose:
519 // ========================================================================================
520 Standard_Boolean QANewModTopOpe_Tools::BoolOpe(const TopoDS_Shape& theFace1,
521                                                const TopoDS_Shape& theFace2,
522                                                Standard_Boolean&   IsCommonFound,
523                                                TopTools_IndexedDataMapOfShapeListOfShape& theHistoryMap) 
524 {
525   IsCommonFound = Standard_False;
526   theHistoryMap.Clear();
527   gp_Dir aDNF1, aDNF2;
528   Standard_Integer iSenseFlag;
529
530   BOPAlgo_PaveFiller aDSFiller;
531   BOPCol_ListOfShape aLS;
532   aLS.Append(theFace1);
533   aLS.Append(theFace2);
534   aDSFiller.SetArguments(aLS);
535   
536   aDSFiller.Perform();
537   if (aDSFiller.ErrorStatus()) {
538     return Standard_False;
539   }
540   
541   const BOPDS_PDS& pDS = aDSFiller.PDS();
542
543   Standard_Integer aNb = 0, aNbSps;
544   Standard_Integer i = 0;
545   TopTools_IndexedMapOfShape aMapV;
546
547   {
548     BRepAlgoAPI_Common aCommon(theFace1, theFace2, aDSFiller);
549
550     if(!aCommon.IsDone()) {
551       return Standard_False;
552     }
553
554     TopExp_Explorer anExp(aCommon.Shape(), TopAbs_FACE);
555     if(!anExp.More()) {
556       IsCommonFound = Standard_False;
557       return Standard_True;
558     }
559
560     IsCommonFound = Standard_True;
561     TopExp::MapShapes(aCommon.Shape(), TopAbs_VERTEX, aMapV);
562     // fill edge history.begin
563     FillEdgeHistoryMap(aCommon, theHistoryMap);
564     // fill edge history.end
565
566     // fill face history.begin
567     BOPDS_VectorOfInterfFF& aFFs = pDS->InterfFF();
568     aNb = aFFs.Extent();
569     Standard_Boolean bReverseFlag = Standard_True;
570     Standard_Boolean fillhistory = Standard_True;
571
572     for (i=0; i<aNb; ++i) {
573       BOPDS_InterfFF& aFF = aFFs(i);
574       Standard_Integer nF1, nF2;
575       aFF.Indices(nF1, nF2);
576     
577       const TopoDS_Face& aF1 = *(TopoDS_Face*)(&pDS->Shape(nF1));
578       const TopoDS_Face& aF2 = *(TopoDS_Face*)(&pDS->Shape(nF2));
579
580       BOPCol_ListOfInteger aLSE;
581       pDS->SharedEdges(nF1, nF2, aLSE, aDSFiller.Allocator());
582       aNbSps = aLSE.Extent();
583       
584       if (!aNbSps) {
585         fillhistory = Standard_False;
586         continue;
587       }
588       
589       Standard_Integer nE = aLSE.First();
590       const TopoDS_Edge& aSpE = *(TopoDS_Edge*)(&pDS->Shape(nE));
591     
592       BOPTools_AlgoTools3D::GetNormalToFaceOnEdge (aSpE, aF1, aDNF1); 
593       BOPTools_AlgoTools3D::GetNormalToFaceOnEdge (aSpE, aF2, aDNF2);
594       iSenseFlag=BOPTools_AlgoTools3D::SenseFlag (aDNF1, aDNF2);
595
596       if(iSenseFlag == 1) {
597         fillhistory = Standard_True;
598         bReverseFlag = Standard_False;
599       }
600       else if(iSenseFlag == -1) {
601         fillhistory = Standard_True;
602         bReverseFlag = Standard_True;
603       }
604       else
605         fillhistory = Standard_False;
606     }
607
608     if(fillhistory) {
609
610       for(; anExp.More(); anExp.Next()) {
611         TopoDS_Shape aResShape = anExp.Current();
612
613         if(theFace1.Orientation() == aResShape.Orientation()) {
614           AddShapeToHistoryMap(theFace1, aResShape, theHistoryMap);
615
616           if(bReverseFlag)
617             aResShape.Reverse();
618           AddShapeToHistoryMap(theFace2, aResShape, theHistoryMap);
619         }
620         else if(theFace2.Orientation() == aResShape.Orientation()) {
621           AddShapeToHistoryMap(theFace2, aResShape, theHistoryMap);
622
623           if(bReverseFlag)
624             aResShape.Reverse();
625           AddShapeToHistoryMap(theFace1, aResShape, theHistoryMap);
626         }
627         else {
628           aResShape.Orientation(theFace1.Orientation());
629           AddShapeToHistoryMap(theFace1, aResShape, theHistoryMap);
630           aResShape.Orientation(theFace2.Orientation());
631
632           if(bReverseFlag)
633             aResShape.Reverse();
634           AddShapeToHistoryMap(theFace2, aResShape, theHistoryMap);
635         }
636       }
637     }
638     // fill face history.end
639   }
640   {
641     BRepAlgoAPI_Cut aCut1(theFace1, theFace2, aDSFiller);
642
643     if(!aCut1.IsDone())
644       return Standard_False;
645     TopExp::MapShapes(aCut1.Shape(), TopAbs_VERTEX, aMapV);
646     // fill edge history.begin
647     FillEdgeHistoryMap(aCut1, theHistoryMap);
648     // fill edge history.end
649
650     // fill face history.begin
651     TopExp_Explorer anExp(aCut1.Shape(), TopAbs_FACE);
652
653     for(; anExp.More(); anExp.Next()) {
654       TopoDS_Shape aResShape = anExp.Current();
655       aResShape.Orientation(theFace1.Orientation());
656       AddShapeToHistoryMap(theFace1, aResShape, theHistoryMap);
657     }
658     // fill face history.end
659   }
660
661   {
662     BRepAlgoAPI_Cut aCut2(theFace1, theFace2, aDSFiller, Standard_False);
663
664     if(!aCut2.IsDone())
665       return Standard_False;
666     TopExp::MapShapes(aCut2.Shape(), TopAbs_VERTEX, aMapV);
667     // fill edge history.begin
668     FillEdgeHistoryMap(aCut2, theHistoryMap);
669     // fill edge history.end
670
671     // fill face history.begin
672     TopExp_Explorer anExp(aCut2.Shape(), TopAbs_FACE);
673
674     for(; anExp.More(); anExp.Next()) {
675       TopoDS_Shape aResShape = anExp.Current();
676       aResShape.Orientation(theFace2.Orientation());
677       AddShapeToHistoryMap(theFace2, aResShape, theHistoryMap);
678     }
679     // fill face history.end
680   }
681   
682   // fill vertex history.begin
683   BOPDS_VectorOfInterfVV& aVVs = pDS->InterfVV();
684   aNb = aVVs.Extent();
685
686   for (i = 0; i < aNb; ++i) {
687     BOPDS_InterfVV& aVVi = aVVs(i);
688     if (!aVVi.HasIndexNew()) {
689       continue;
690     }
691     Standard_Integer aNewShapeIndex = aVVi.IndexNew();
692
693     const TopoDS_Shape& aNewVertex = pDS->Shape(aNewShapeIndex);
694
695     if(!aMapV.Contains(aNewVertex)) {
696       continue;
697     }
698     
699     const TopoDS_Shape& aV1 = pDS->Shape(aVVi.Index1());
700     const TopoDS_Shape& aV2 = pDS->Shape(aVVi.Index2());
701     AddShapeToHistoryMap(aV1, aNewVertex, theHistoryMap);
702     AddShapeToHistoryMap(aV2, aNewVertex, theHistoryMap);
703   }
704
705   BOPDS_VectorOfInterfVE& aVEs = pDS->InterfVE();
706   aNb = aVEs.Extent();
707
708   for (i = 0; i < aNb; ++i) {
709     BOPDS_InterfVE& aVEi = aVEs(i);
710     
711     Standard_Integer anIndex = aVEi.Index1();
712     const TopoDS_Shape& aNewVertex = pDS->Shape(anIndex);
713
714     if(!aMapV.Contains(aNewVertex))
715       continue;
716
717     AddShapeToHistoryMap(aNewVertex, aNewVertex, theHistoryMap);
718   }
719
720   BOPDS_VectorOfInterfVF& aVSs = pDS->InterfVF();
721   aNb = aVSs.Extent();
722
723   for (i = 0; i < aNb; ++i) {
724     BOPDS_InterfVF& aVSi = aVSs(i);
725
726     Standard_Integer anIndex = aVSi.Index1();
727     const TopoDS_Shape& aNewVertex = pDS->Shape(anIndex);
728
729     if(!aMapV.Contains(aNewVertex))
730       continue;
731
732     AddShapeToHistoryMap(aNewVertex, aNewVertex, theHistoryMap);
733   }
734   // fill vertex history.end
735   return Standard_True;
736 }
737
738 // --------------------------------------------------------------------------------------------
739 // static function: AddShapeToHistoryMap
740 // purpose: 
741 // --------------------------------------------------------------------------------------------
742 Standard_Boolean AddShapeToHistoryMap(const TopoDS_Shape& theOldShape,
743                                       const TopoDS_Shape& theNewShape,
744                                       TopTools_IndexedDataMapOfShapeListOfShape& theHistoryMap) {
745
746   if(!theHistoryMap.Contains(theOldShape)) {
747     TopTools_ListOfShape aList;
748     aList.Append(theNewShape);
749     theHistoryMap.Add(theOldShape, aList);
750     return Standard_True;
751   }
752   
753   Standard_Boolean found = Standard_False;
754   TopTools_ListOfShape& aList = theHistoryMap.ChangeFromKey(theOldShape);
755   TopTools_ListIteratorOfListOfShape aVIt(aList);
756
757   for(; aVIt.More(); aVIt.Next()) {
758     if(theNewShape.IsSame(aVIt.Value())) {
759       found = Standard_True;
760       break;
761     }
762   }
763
764   if(!found) {
765     aList.Append(theNewShape);
766   }
767   return !found;
768 }
769
770 // --------------------------------------------------------------------------------------------
771 // static function: FillEdgeHistoryMap
772 // purpose: 
773 // --------------------------------------------------------------------------------------------
774 void FillEdgeHistoryMap(BRepAlgoAPI_BooleanOperation&              theBOP,
775                         TopTools_IndexedDataMapOfShapeListOfShape& theHistoryMap) {
776
777   TopExp_Explorer anExp;
778   anExp.Init(theBOP.Shape1(), TopAbs_EDGE);
779
780   for(; anExp.More(); anExp.Next()) {
781     const TopTools_ListOfShape& aList = theBOP.Modified(anExp.Current());
782     TopTools_ListIteratorOfListOfShape anIt(aList);
783
784     for(; anIt.More(); anIt.Next()) {
785       AddShapeToHistoryMap(anExp.Current(), anIt.Value(), theHistoryMap);
786     }
787   }
788
789   anExp.Init(theBOP.Shape2(), TopAbs_EDGE);
790
791   for(; anExp.More(); anExp.Next()) {
792     const TopTools_ListOfShape& aList = theBOP.Modified(anExp.Current());
793     TopTools_ListIteratorOfListOfShape anIt(aList);
794
795     for(; anIt.More(); anIt.Next()) {
796       AddShapeToHistoryMap(anExp.Current(), anIt.Value(), theHistoryMap);
797     }
798   }
799 }
800
801 // --------------------------------------------------------------------------------------------
802 // static function: SortVertexOnEdge
803 // purpose: 
804 // --------------------------------------------------------------------------------------------
805 void SortVertexOnEdge(const TopoDS_Edge&          theEdge,
806                       const TopTools_ListOfShape& theListOfVertex,
807                       TopTools_ListOfShape&       theListOfVertexSorted) {
808
809   TopTools_DataMapOfIntegerShape mapiv;// mapiv.Find(iV) = V
810   TColStd_IndexedMapOfReal mappar;     // mappar.FindIndex(parV) = iV
811   TopTools_ListIteratorOfListOfShape itlove(theListOfVertex);
812   
813   for (; itlove.More(); itlove.Next()){
814     const TopoDS_Vertex& v = TopoDS::Vertex(itlove.Value());
815     Standard_Real par = BRep_Tool::Parameter(v, theEdge);
816     Standard_Integer iv = mappar.Add(par);
817     mapiv.Bind(iv,v);
818   }
819   Standard_Integer nv = mapiv.Extent();
820   NCollection_Array1<Standard_Real> tabpar(1,nv);
821   Standard_Integer i = 0;
822
823   for ( i = 1; i <= nv; i++) {
824     Standard_Real p = mappar.FindKey(i);
825     tabpar.SetValue(i,p);
826   }
827   theListOfVertexSorted.Clear();
828   std::sort (tabpar.begin(), tabpar.end());
829
830   for (i = 1; i <= nv; i++) {
831     Standard_Real par = tabpar.Value(i);
832     Standard_Integer iv = mappar.FindIndex(par);
833     const TopoDS_Shape& v = mapiv.Find(iv);
834     theListOfVertexSorted.Append(v);
835   }
836 }
837
838 // --------------------------------------------------------------------------------------------
839 // static function: GetEdgeState
840 // purpose: 
841 // --------------------------------------------------------------------------------------------
842   static TopAbs_State GetEdgeState(const BOPDS_PDS& pDS,
843                                    const Handle(BOPDS_PaveBlock)& aPB) 
844 {
845   Standard_Integer j, aNbFI;
846   Standard_Boolean bIn;
847   TopAbs_State aState = TopAbs_ON;
848   //
849   const BOPDS_VectorOfFaceInfo& aVFI = pDS->FaceInfoPool();
850   aNbFI = aVFI.Extent();
851   //
852   for (j = 0; j < aNbFI; ++j) {
853     const BOPDS_FaceInfo& aFI = aVFI(j);
854     bIn = aFI.PaveBlocksIn().Contains(aPB);
855     if (bIn) {
856       aState = TopAbs_IN;
857       break;
858     }
859   }
860   return aState;
861 }