0024831: Make iterators of NCollection classes STL-compatible
[occt.git] / src / QANewModTopOpe / QANewModTopOpe_Glue_shell.cxx
1 // Created on: 2001-01-16
2 // Created by: Michael SAZONOV
3 // Copyright (c) 2001-2014 OPEN CASCADE SAS
4 //
5 // This file is part of Open CASCADE Technology software library.
6 //
7 // This library is free software; you can redistribute it and/or modify it under
8 // the terms of the GNU Lesser General Public License version 2.1 as published
9 // by the Free Software Foundation, with special exception defined in the file
10 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
11 // distribution for complete text of the license and disclaimer of any warranty.
12 //
13 // Alternatively, this file may be used under the terms of Open CASCADE
14 // commercial license or contractual agreement.
15
16 #include <QANewModTopOpe_Glue.ixx>
17 #include <Precision.hxx>
18 #include <Geom2d_Curve.hxx>
19 #include <Geom_Surface.hxx>
20 #include <GeomAPI_ProjectPointOnSurf.hxx>
21 #include <TopoDS.hxx>
22 #include <TopoDS_Iterator.hxx>
23 #include <BRep_Tool.hxx>
24 #include <BRepTools.hxx>
25 #include <BRepClass_FaceClassifier.hxx>
26 #include <BRepFeat_SplitShape.hxx>
27 #include <BRepLib.hxx>
28 #include <TopExp.hxx>
29 #include <TopExp_Explorer.hxx>
30 #include <TopTools_DataMapOfShapeInteger.hxx>
31 #include <TopTools_ListIteratorOfListOfShape.hxx>
32 #include <TopTools_MapIteratorOfMapOfShape.hxx>
33 #include <TopTools_DataMapIteratorOfDataMapOfShapeShape.hxx>
34 #include <BRepAlgo_EdgeConnector.hxx>
35 #include <TopTools_MapOfShape.hxx>
36 #include <BRep_Builder.hxx>
37 #include <QANewModTopOpe_Tools.hxx>
38 #include <TopTools_IndexedMapOfShape.hxx>
39
40 //=======================================================================
41 //function : SplitEdgeComplete
42 //purpose  : static
43 //=======================================================================
44
45 static void
46 SplitEdgeComplete (const TopoDS_Edge& theEdge,
47                    TopTools_ListOfShape& theListSplits)
48 {
49   struct ParVer {
50     Standard_Real myParF, myParL;
51     TopoDS_Vertex myVerF, myVerL;
52   };
53   ParVer *aParVer = new ParVer[theListSplits.Extent()+1];
54   TopTools_DataMapOfShapeInteger aMapEdgeIPV;
55   TopTools_ListOfShape aListTodo;
56   aListTodo = theListSplits;
57
58   // prepare structures aMapEdgeIPV and aParVer
59
60   aListTodo.Prepend(theEdge);
61   TopTools_ListIteratorOfListOfShape aIter(aListTodo);
62   Standard_Integer iPV;
63   for (iPV=0; aIter.More(); aIter.Next(), iPV++) {
64     const TopoDS_Edge& aEdge = TopoDS::Edge(aIter.Value());
65     TopoDS_Vertex aVer1, aVer2;
66     Standard_Real aPar1, aPar2;
67
68     // compute parameters of first and last vertices of aEdge on theEdge
69
70     TopExp::Vertices(aEdge, aVer1, aVer2);
71
72     if(aVer1.IsNull() || aVer2.IsNull()) {
73       aListTodo.Remove(aIter);
74       TopTools_ListIteratorOfListOfShape aIter1(theListSplits);
75       for (; aIter1.More(); aIter1.Next()) {
76         if(aEdge.IsSame(aIter1.Value())) {
77           theListSplits.Remove(aIter1);
78           break;
79         }
80       }
81       if(aIter.More()) continue;
82       break;
83     }
84
85     if (iPV == 0) {
86       // the vertices of theEdge
87       aPar1 = BRep_Tool::Parameter(aVer1, theEdge);
88       aPar2 = BRep_Tool::Parameter(aVer2, theEdge);
89     }
90     else {
91       Standard_Real aDist;
92       // the vertices of an edge from the source list
93       if (!QANewModTopOpe_Glue::ProjPointOnEdge (BRep_Tool::Pnt(aVer1),
94                                             theEdge, aPar1, aDist)) {
95         // the vertex is out of theEdge => take one from theEdge
96         Standard_Real aPar;
97         if (QANewModTopOpe_Glue::ProjPointOnEdge (BRep_Tool::Pnt(aParVer[0].myVerF),
98                                              aEdge, aPar, aDist)) {
99           aVer1 = aParVer[0].myVerF;
100           aPar1 = aParVer[0].myParF;
101         }
102         else {
103           aVer1 = aParVer[0].myVerL;
104           aPar1 = aParVer[0].myParL;
105         }
106       }
107       if (!QANewModTopOpe_Glue::ProjPointOnEdge (BRep_Tool::Pnt(aVer2),
108                                             theEdge, aPar2, aDist)) {
109         // the vertex is out of theEdge => take one from theEdge
110         Standard_Real aPar;
111         if (QANewModTopOpe_Glue::ProjPointOnEdge (BRep_Tool::Pnt(aParVer[0].myVerL),
112                                              aEdge, aPar, aDist)) {
113           aVer2 = aParVer[0].myVerL;
114           aPar2 = aParVer[0].myParL;
115         }
116         else {
117           aVer2 = aParVer[0].myVerF;
118           aPar2 = aParVer[0].myParF;
119         }
120       }
121     }
122     if (aPar1 < aPar2) {
123       aParVer[iPV].myParF = aPar1; aParVer[iPV].myVerF = aVer1;
124       aParVer[iPV].myParL = aPar2; aParVer[iPV].myVerL = aVer2;
125     }
126     else {
127       aParVer[iPV].myParF = aPar2; aParVer[iPV].myVerF = aVer2;
128       aParVer[iPV].myParL = aPar1; aParVer[iPV].myVerL = aVer1;
129       if(iPV != 0) {
130         TopTools_ListIteratorOfListOfShape aIterSplits(theListSplits);
131         for(; aIterSplits.More(); aIterSplits.Next()) {
132           if(aEdge.IsSame(aIterSplits.Value())) {
133             aIterSplits.Value().Reverse();
134           }
135         }
136       }
137     }
138     aMapEdgeIPV.Bind(aEdge,iPV);
139   }
140   aListTodo.RemoveFirst();
141
142   // find holes and make new edges
143
144   BRep_Builder aBld;
145   Standard_Integer iPVLast = 0;
146   iPV = -1;
147   while (iPV != 0) {
148
149     // find the most left edge
150     iPV = 0;
151     TopTools_ListIteratorOfListOfShape aIterFound;
152     Standard_Real aParF = aParVer[0].myParL;
153     TopoDS_Vertex aVerF = aParVer[0].myVerL;
154     for (aIter.Initialize(aListTodo); aIter.More(); aIter.Next()) {
155       const TopoDS_Edge& aEdge = TopoDS::Edge(aIter.Value());
156       Standard_Integer i = aMapEdgeIPV(aEdge);
157       if (aParVer[i].myParF < aParF) {
158         aParF = aParVer[i].myParF;
159         aVerF = aParVer[i].myVerF;
160         iPV = i;
161         aIterFound = aIter;
162       }
163     }
164
165     // get previous last parameter
166     Standard_Real aParPrevL;
167     TopoDS_Vertex aVerPrevL;
168     if (iPVLast == 0) {
169       aParPrevL = aParVer[0].myParF;
170       aVerPrevL = aParVer[0].myVerF;
171     }
172     else {
173       aParPrevL = aParVer[iPVLast].myParL;
174       aVerPrevL = aParVer[iPVLast].myVerL;
175     }
176
177     if (aParF > aParPrevL && !BRepTools::Compare(aVerF, aVerPrevL)) {
178       // make new edge to close the hole
179       TopoDS_Edge aNewEdge = theEdge;
180       aNewEdge.EmptyCopy();
181       aNewEdge.Orientation(TopAbs_FORWARD);
182       TopoDS_Vertex aV1 = aVerPrevL;
183       TopoDS_Vertex aV2 = aVerF;
184       aV1.Orientation(TopAbs_FORWARD);
185       aV2.Orientation(TopAbs_REVERSED);
186       aBld.Add(aNewEdge, aV1);
187       aBld.Add(aNewEdge, aV2);
188       aBld.UpdateVertex(aV1, aParPrevL, aNewEdge, BRep_Tool::Tolerance(aV1));
189       aBld.UpdateVertex(aV2, aParF, aNewEdge, BRep_Tool::Tolerance(aV2));
190       theListSplits.Append(aNewEdge);
191     }
192
193     iPVLast = iPV;
194     if (aIterFound.More()) aListTodo.Remove(aIterFound);
195   }
196
197   delete [] aParVer;
198 }
199
200 //=======================================================================
201 //function : SplitEdge
202 //purpose  : static
203 //=======================================================================
204
205 static void
206 SplitEdge (const TopoDS_Edge          &theEdge,
207            const BOPAlgo_PPaveFiller  &thePDSFiller,
208            const TopTools_MapOfShape  &theEdgesValid,
209            const Standard_Boolean      useMap,
210                  TopTools_ListOfShape &theListSplits)
211 {
212   const TopAbs_State aStates[3] = {TopAbs_ON, TopAbs_IN, TopAbs_OUT};
213
214   for (Standard_Integer i=0; i < 3; i++) {      // for each state {ON, IN, OUT}
215     if (QANewModTopOpe_Tools::IsSplit(thePDSFiller, theEdge, aStates[i])) {
216       // get splits according to this state
217       // and append them to the substitution list
218       TopTools_ListOfShape aListSplits;
219
220       QANewModTopOpe_Tools::Splits(thePDSFiller, theEdge, aStates[i], aListSplits);
221       TopTools_ListIteratorOfListOfShape aIterSplits(aListSplits);
222       for(; aIterSplits.More(); aIterSplits.Next()) {
223         const TopoDS_Shape& aEdge = aIterSplits.Value();
224         if (!useMap || theEdgesValid.Contains (aEdge))
225           theListSplits.Append(aEdge.Oriented(TopAbs_FORWARD));
226       }
227     }
228   }
229
230   if (!theListSplits.IsEmpty()) {
231     SplitEdgeComplete (theEdge, theListSplits);
232   }
233 }
234
235 //=======================================================================
236 //function : IsEdgeOut
237 //purpose  : static
238 //remark   : the edge is expected to have a pcurve on this face
239 //=======================================================================
240
241 static Standard_Boolean
242 IsEdgeOut (const TopoDS_Edge& theEdge, const TopoDS_Face& theFace)
243 {
244   Standard_Real aParF, aParL, aParM;
245   Handle(Geom2d_Curve) aCrv = BRep_Tool::CurveOnSurface(theEdge, theFace, aParF, aParL);
246   if (aCrv.IsNull()) return Standard_True;
247
248   Standard_Real aPrec = Precision::PConfusion();
249   BRepClass_FaceClassifier aClf;
250   gp_Pnt2d aPnt;
251
252   if (!Precision::IsNegativeInfinite(aParF)) {
253     //check first point
254     aPnt = aCrv->Value(aParF);
255     aClf.Perform(theFace, aPnt, aPrec);
256     if(aClf.State() == TopAbs_OUT) return Standard_True;
257   }
258
259   if (!Precision::IsPositiveInfinite(aParL)) {
260     //check last point
261     aPnt = aCrv->Value(aParL);
262     aClf.Perform(theFace, aPnt, aPrec);
263     if(aClf.State() == TopAbs_OUT) return Standard_True;
264   }
265
266   //check middle point
267   if (!Precision::IsNegativeInfinite(aParF) &&
268       !Precision::IsPositiveInfinite(aParL)) {
269     aParM = aParF + 0.618 * (aParL - aParF);
270   }
271   else {
272     if (Precision::IsNegativeInfinite(aParF) &&
273         Precision::IsPositiveInfinite(aParL))
274       aParM = 0.;
275     else if (Precision::IsNegativeInfinite(aParF))
276       aParM = aParL - 1.;
277     else
278       aParM = aParF + 1.;
279   }
280   aPnt = aCrv->Value(aParM);
281   aClf.Perform(theFace, aPnt, aPrec);
282   if(aClf.State() == TopAbs_OUT) return Standard_True;
283
284   return Standard_False;
285 }
286
287 //=======================================================================
288 //function : CorrectAncestorsList
289 //purpose  : static
290 //=======================================================================
291
292 static void
293 CorrectAncestorsList (const TopoDS_Edge& theEdge, TopTools_ListOfShape& aListF)
294 {
295   // remove duplicates from list,
296   // remove faces for which theEdge has the state "OUT"
297
298   // get a middle point on edge
299   TopTools_MapOfShape aMapF;
300   TopTools_ListIteratorOfListOfShape aIter(aListF);
301   while (aIter.More()) {
302     const TopoDS_Face& aFace = TopoDS::Face(aIter.Value());
303     if (!aMapF.Add(aFace)) {
304       // duplicate -> remove
305       aListF.Remove(aIter);
306       continue;
307     }
308     if (IsEdgeOut(theEdge, aFace)) {
309       // this face is not an ancestor -> remove
310       aListF.Remove(aIter);
311       continue;
312     }
313     aIter.Next();
314   }
315 }
316
317 //=======================================================================
318 //function : PerformShell
319 //purpose  : 
320 //=======================================================================
321
322 void
323 QANewModTopOpe_Glue::PerformShell() 
324 {
325 //  Standard_Boolean isSolidShell = (myS1.ShapeType() == TopAbs_SOLID);
326   Standard_Boolean isSolidShell = Standard_False;
327   Standard_Integer i;
328
329   TopTools_MapOfShape anEdges, aCommonEdges, anOldVertices, aGenEdges;
330   TopExp_Explorer anExp;
331
332   anExp.Init(myS1, TopAbs_EDGE);
333   for(; anExp.More(); anExp.Next()) anEdges.Add(anExp.Current());
334
335   anExp.Init(myS2, TopAbs_EDGE);
336   for(; anExp.More(); anExp.Next()) {
337     if(anEdges.Contains(anExp.Current())) aCommonEdges.Add(anExp.Current());
338   }
339
340   anExp.ReInit();
341   for(; anExp.More(); anExp.Next()) anEdges.Add(anExp.Current());
342
343   anExp.Init(myS1, TopAbs_VERTEX);
344   for(; anExp.More(); anExp.Next()) anOldVertices.Add(anExp.Current());
345
346   anExp.Init(myS2, TopAbs_VERTEX);
347   for(; anExp.More(); anExp.Next()) anOldVertices.Add(anExp.Current());
348
349
350   // initialization
351   TopoDS_Shape aS1, aS2;
352   Standard_Boolean aWire1 = Standard_False, aWire2 = Standard_False; 
353   anExp.Init(myS1, TopAbs_WIRE, TopAbs_FACE);
354   if(anExp.More()) {
355     aS1 = myS1;
356     aWire1 = Standard_True;
357   }
358   else {
359     anExp.Init(myS1, TopAbs_EDGE, TopAbs_WIRE);
360     if(anExp.More()) {
361       aS1 = myS1;
362       aWire1 = Standard_True;
363     }
364   }
365    
366   anExp.Init(myS2, TopAbs_WIRE, TopAbs_FACE);
367   if(anExp.More()) {
368     aS2 = myS2;
369     aWire2 = Standard_True;
370   }
371   else {
372     anExp.Init(myS2, TopAbs_EDGE, TopAbs_WIRE);
373     if(anExp.More()) {
374       aS2 = myS2;
375       aWire2 = Standard_True;
376     }
377   }
378  
379   if(aWire1) {
380     BRep_Builder aBld;
381     myS1.Nullify();
382     aBld.MakeCompound(TopoDS::Compound(myS1));
383     anExp.Init(aS1, TopAbs_COMPSOLID);
384     for(; anExp.More(); anExp.Next()) {
385       aBld.Add(myS1, anExp.Current());
386     }
387     
388     anExp.Init(aS1, TopAbs_SOLID, TopAbs_COMPSOLID);
389     for(; anExp.More(); anExp.Next()) {
390       aBld.Add(myS1, anExp.Current());
391     }
392     
393     anExp.Init(aS1, TopAbs_SHELL, TopAbs_SOLID);
394     for(; anExp.More(); anExp.Next()) {
395       aBld.Add(myS1, anExp.Current());
396     }
397     
398     anExp.Init(aS1, TopAbs_FACE, TopAbs_SHELL);
399     for(; anExp.More(); anExp.Next()) {
400       aBld.Add(myS1, anExp.Current());
401     }
402     
403   }
404
405   if(aWire2) {
406     BRep_Builder aBld;
407     myS2.Nullify();
408     aBld.MakeCompound(TopoDS::Compound(myS2));
409     anExp.Init(aS2, TopAbs_COMPSOLID);
410     for(; anExp.More(); anExp.Next()) {
411       aBld.Add(myS2, anExp.Current());
412     }
413     
414     anExp.Init(aS2, TopAbs_SOLID, TopAbs_COMPSOLID);
415     for(; anExp.More(); anExp.Next()) {
416       aBld.Add(myS2, anExp.Current());
417     }
418     
419     anExp.Init(aS2, TopAbs_SHELL, TopAbs_SOLID);
420     for(; anExp.More(); anExp.Next()) {
421       aBld.Add(myS2, anExp.Current());
422     }
423     
424     anExp.Init(aS2, TopAbs_FACE, TopAbs_SHELL);
425     for(; anExp.More(); anExp.Next()) {
426       aBld.Add(myS2, anExp.Current());
427     }
428     
429   }
430
431   Standard_Boolean hasSolid1 = Standard_False;
432   Standard_Boolean hasSolid2 = Standard_False;
433
434   anExp.Init(myS1, TopAbs_SOLID);
435
436   if (anExp.More())
437     hasSolid1 = Standard_True;
438
439   anExp.Init(myS2, TopAbs_SOLID);
440
441   if (anExp.More())
442     hasSolid2 = Standard_True;
443
444   if (hasSolid1 && hasSolid2)
445     myOperation = BOPAlgo_FUSE;
446   else if (hasSolid1)
447     myOperation = BOPAlgo_CUT21;
448   else if (hasSolid2)
449     myOperation = BOPAlgo_CUT;
450   else
451     myOperation = BOPAlgo_SECTION;
452
453   BRepAlgoAPI_BooleanOperation::Build();
454   if (!BuilderCanWork())
455     return;
456
457   if(aWire1) myS1 = aS1;
458   if(aWire2) myS2 = aS2;
459
460   TopTools_DataMapOfShapeListOfShape* aMapSEdgeFaces[2] =
461     {&myMapSEdgeFaces1, &myMapSEdgeFaces2};
462   TopTools_DataMapOfShapeShape* aMapSEdgeCrossFace[2] =
463     {&myMapSEdgeCrossFace1, &myMapSEdgeCrossFace2};
464   TopTools_MapOfShape aSetFaces[2];
465   TopTools_MapOfShape aSetEdges[2];
466
467   // fill myMapGener for new vertices
468   TopTools_MapIteratorOfMapOfShape aMapIter(anEdges);
469   const TopAbs_State aStates[3] = {TopAbs_ON, TopAbs_IN, TopAbs_OUT};
470   for(; aMapIter.More(); aMapIter.Next()) {
471     const TopoDS_Shape& aEdge = aMapIter.Key();
472
473     if(aCommonEdges.Contains(aEdge)) continue;
474
475     for (i=0; i < 3; i++) {     // for each state {ON, IN, OUT}
476       if (QANewModTopOpe_Tools::IsSplit(myDSFiller, aEdge, aStates[i])) {
477         TopTools_ListOfShape aListSplits;
478
479         QANewModTopOpe_Tools::Splits(myDSFiller, aEdge, aStates[i], aListSplits);
480
481         TopTools_ListIteratorOfListOfShape aIterSplits(aListSplits);
482         for(; aIterSplits.More(); aIterSplits.Next()) {
483           const TopoDS_Shape& aE = aIterSplits.Value();
484           TopoDS_Iterator aTDSIter(aE);
485           for(; aTDSIter.More(); aTDSIter.Next()) {
486             const TopoDS_Shape& aV = aTDSIter.Value();
487
488             if(!anOldVertices.Add(aV)) continue;
489
490             if(!myMapGener.IsBound(aEdge)) {
491               // for Mandrake-10 - mkv,02.06.06 - myMapGener.Bind(aEdge, TopTools_ListOfShape());
492               TopTools_ListOfShape aListOfShape1;
493               myMapGener.Bind(aEdge, aListOfShape1);
494             }
495
496             myMapGener(aEdge).Append(aV);
497           }
498         }
499       }
500     }
501   }       
502
503
504   // get list of section edges
505   const TopTools_ListOfShape& aListSE = SectionEdges();
506
507   // for each section edge remember the face crossed by the edge
508   // and the faces for which the edge coincides with a face's bound
509   TopTools_ListIteratorOfListOfShape aIterSE(aListSE);
510   Standard_Integer aNbUsedSecEdges = 0;
511   for(; aIterSE.More(); aIterSE.Next()) {
512     const TopoDS_Edge& aSecEdge = TopoDS::Edge(aIterSE.Value());
513
514     if(!aCommonEdges.Contains(aSecEdge)) {
515
516       aNbUsedSecEdges++;
517
518       TopoDS_Face aFaces[2];
519       QANewModTopOpe_Tools::EdgeCurveAncestors(myDSFiller, aSecEdge, aFaces[0],
520                                           aFaces[1]);
521
522       TopTools_ListOfShape aListF[2], aListE[2];
523       QANewModTopOpe_Tools::EdgeSectionAncestors(myDSFiller, aSecEdge, aListF[0],
524                                             aListF[1], aListE[0], aListE[1]);
525       CorrectAncestorsList (aSecEdge, aListF[0]);
526       CorrectAncestorsList (aSecEdge, aListF[1]);
527
528       Standard_Integer nbCurveAncestors = 0;
529       for (i = 0; i < 2; i++) {
530         if (!aListF[i].IsEmpty()) {
531           aMapSEdgeFaces[i]->Bind(aSecEdge, aListF[i]);
532           if (aListE[i].IsEmpty())
533             aMapSEdgeCrossFace[i]->Bind(aSecEdge, aListF[i].First());
534           TopTools_ListIteratorOfListOfShape aIter (aListF[i]);
535           for (; aIter.More(); aIter.Next())
536             aSetFaces[i].Add(aIter.Value());
537         }
538         else if (!aFaces[i].IsNull()) {
539           TopTools_ListOfShape aList;
540           aList.Append(aFaces[i]);
541           aMapSEdgeFaces[i]->Bind(aSecEdge, aList);
542           aMapSEdgeCrossFace[i]->Bind(aSecEdge, aFaces[i]);
543           aSetFaces[i].Add(aFaces[i]);
544           nbCurveAncestors++;
545         }
546         else if (!aListE[i].IsEmpty()) {
547           myEdgesToLeave.Add (aSecEdge);
548           TopTools_ListIteratorOfListOfShape aIter (aListE[i]);
549           for (; aIter.More(); aIter.Next())
550             aSetEdges[i].Add(aIter.Value());
551         }
552       }
553       if (nbCurveAncestors == 2) {
554         // the edge was computed by intersection of 2 surfaces
555         aGenEdges.Add(aSecEdge);
556         if (isSolidShell && !myAllowCutting) {
557           // Shell goes inside Solid while it is forbidden
558           return;
559         }
560         else {
561           // force same parameter
562           const Standard_Real aTol = 1.e-5;
563           BRep_Builder aBld;
564           aBld.SameRange (aSecEdge, Standard_False);
565           aBld.SameParameter (aSecEdge, Standard_False);
566           BRepLib::SameParameter (aSecEdge, aTol);
567         }
568       }
569     }
570   }
571
572   //--------------------------------------------------
573   if(aNbUsedSecEdges == 0 && aListSE.Extent() != 0) {
574     // all section edges are common edges - make compound
575     BRep_Builder aBld;
576     aBld.MakeCompound (TopoDS::Compound(myShape));
577     aBld.Add(myShape, myS1);
578     aBld.Add(myShape, myS2);
579     Done();
580     return;
581   }
582   //--------------------------------------------------
583
584   // cut faces of shell if another shape is solid
585   if (isSolidShell) {
586     // split edges of shape by section edges which are got
587     // due to coinciding of edges rather than intersecting of faces
588     TopTools_MapIteratorOfMapOfShape aIter(aSetEdges[1]);
589     for(; aIter.More(); aIter.Next()) {
590       const TopoDS_Edge aEdge = TopoDS::Edge (aIter.Key());
591       TopTools_ListOfShape aListSplitE;
592       SplitEdge (aEdge, myDSFiller, myEdgesToLeave, Standard_False, aListSplitE);
593       if (!aListSplitE.IsEmpty()) {
594         mySubst.Substitute (aEdge, aListSplitE);
595         if (mySubst.IsCopied (aEdge)) {
596           // for Mandrake-10 - mkv,02.06.06 - myMapModif.Bind(aEdge, TopTools_ListOfShape());
597           TopTools_ListOfShape aListOfShape2;
598           myMapModif.Bind(aEdge, aListOfShape2);
599           myMapModif(aEdge).Append (aListSplitE);
600         }
601       }
602     }
603
604     for(aIter.Initialize (aSetFaces[1]); aIter.More(); aIter.Next()) {
605       const TopoDS_Face aFace = TopoDS::Face (aIter.Key());
606       TopTools_ListOfShape aListSEOnFace;
607
608       // select section edges on this face
609       for (aIterSE.Initialize(aListSE); aIterSE.More(); aIterSE.Next()) {
610         const TopoDS_Edge& aSecEdge = TopoDS::Edge(aIterSE.Value());
611         // check if aFace is an ancestor of aSecEdge
612         if (aMapSEdgeFaces[1]->IsBound(aSecEdge)) {
613           TopTools_ListIteratorOfListOfShape
614             aIterF (aMapSEdgeFaces[1]->Find(aSecEdge));
615           for (; aIterF.More(); aIterF.Next())
616             if (aIterF.Value().IsSame(aFace)) {
617               aListSEOnFace.Append(aSecEdge);
618               break;
619             }
620         }
621       }
622       if (!aListSEOnFace.IsEmpty()) {
623         Standard_Boolean isCut = CutFace (aFace, aListSEOnFace);
624         if (isCut && !myAllowCutting) {
625           // Shell goes inside Solid while it is forbidden
626           return;
627         }
628       }
629     }
630
631     // remove from maps all the section edges which are not marked to leave
632     for (aIterSE.Initialize (aListSE); aIterSE.More(); aIterSE.Next()) {
633       const TopoDS_Shape& aSecEdge = aIterSE.Value();
634       if (!myEdgesToLeave.Contains (aSecEdge)) {
635         myMapSEdgeFaces1.UnBind (aSecEdge);
636         myMapSEdgeFaces2.UnBind (aSecEdge);
637         myMapSEdgeCrossFace1.UnBind (aSecEdge);
638         myMapSEdgeCrossFace2.UnBind (aSecEdge);
639       }
640     }
641   }
642   else {        // not the case Solid-Shell
643     for (aIterSE.Initialize (aListSE); aIterSE.More(); aIterSE.Next())
644       myEdgesToLeave.Add (aIterSE.Value());
645   }
646
647   // process intersected faces
648   for (i = 0; i < 2; i++) {
649     if (i == 1 && isSolidShell) continue;
650
651     // split edges of shape by section edges which are got
652     // due to coinciding of edges rather than intersecting of faces
653     TopTools_MapIteratorOfMapOfShape aIter(aSetEdges[i]);
654     for(; aIter.More(); aIter.Next()) {
655       const TopoDS_Edge aEdge = TopoDS::Edge (aIter.Key());
656       TopTools_ListOfShape aListSplitE;
657       SplitEdge (aEdge, myDSFiller, myEdgesToLeave, Standard_True, aListSplitE);
658       if (!aListSplitE.IsEmpty()) {
659         mySubst.Substitute (aEdge, aListSplitE);
660         //Substitution of vertices at the ends of aEdge.
661         TopoDS_Vertex aV1, aV2;
662         TopExp::Vertices(aEdge, aV1, aV2);
663         TopTools_ListIteratorOfListOfShape anIter(aListSplitE);
664         for(; anIter.More(); anIter.Next()) {
665           const TopoDS_Edge& aSpE = TopoDS::Edge(anIter.Value());
666           TopoDS_Vertex aSpV1, aSpV2;
667           TopExp::Vertices(aSpE, aSpV1, aSpV2);
668           aSpV1.Orientation(TopAbs_FORWARD);
669           aSpV2.Orientation(TopAbs_FORWARD);
670           TopTools_ListOfShape aL;
671           if(BRepTools::Compare(aV1, aSpV1) && (!aV1.IsSame(aSpV1))) {
672             aL.Clear();
673             aL.Append(aSpV1);
674             if(!mySubst.IsCopied (aV1)) {
675               mySubst.Substitute(aV1, aL);
676 //            if (mySubst.IsCopied (aV1)) {
677                 // for Mandrake-10 - mkv,02.06.06 - myMapModif.Bind(aV1, TopTools_ListOfShape());
678                 TopTools_ListOfShape aListOfShape3;
679                 myMapModif.Bind(aV1, aListOfShape3);
680                 myMapModif(aV1).Append (aL);
681 //            }
682             }
683           }
684           if(BRepTools::Compare(aV1, aSpV2) && (!aV1.IsSame(aSpV2))) {
685             aL.Clear();
686             aL.Append(aSpV2);
687             if(!mySubst.IsCopied (aV1)) {
688               mySubst.Substitute(aV1, aL);
689 //            if (mySubst.IsCopied (aV1)) {
690                 // for Mandrake-10 - mkv,02.06.06 - myMapModif.Bind(aV1, TopTools_ListOfShape());
691                 TopTools_ListOfShape aListOfShape4;
692                 myMapModif.Bind(aV1, aListOfShape4);
693                 myMapModif(aV1).Append (aL);
694 //            }
695             }
696           }
697           if(BRepTools::Compare(aV2, aSpV1) && (!aV2.IsSame(aSpV1))) {
698             aL.Clear();
699             aL.Append(aSpV1);
700             if (!mySubst.IsCopied (aV2)) {
701               mySubst.Substitute(aV2, aL);
702 //            if (mySubst.IsCopied (aV2)) {
703                 // for Mandrake-10 - mkv,02.06.06 - myMapModif.Bind(aV2, TopTools_ListOfShape());
704                 TopTools_ListOfShape aListOfShape5;
705                 myMapModif.Bind(aV2, aListOfShape5);
706                 myMapModif(aV2).Append (aL);
707 //            }
708             }
709           }
710           if(BRepTools::Compare(aV2, aSpV2) && (!aV2.IsSame(aSpV2))) {
711             aL.Clear();
712             aL.Append(aSpV2);
713             if (!mySubst.IsCopied (aV2)) {
714               mySubst.Substitute(aV2, aL);
715 //            if (mySubst.IsCopied (aV2)) {
716                 // for Mandrake-10 - mkv,02.06.06 - myMapModif.Bind(aV2, TopTools_ListOfShape());
717                 TopTools_ListOfShape aListOfShape6;
718                 myMapModif.Bind(aV2, aListOfShape6);
719                 myMapModif(aV2).Append (aL);
720 //            }
721             }
722           }
723         }
724
725         if (mySubst.IsCopied (aEdge)) {
726           // for Mandrake-10 - mkv,02.06.06 - myMapModif.Bind(aEdge, TopTools_ListOfShape());
727           TopTools_ListOfShape aListOfShape7;
728           myMapModif.Bind(aEdge, aListOfShape7);
729           myMapModif(aEdge).Append (aListSplitE);
730         }
731       }
732     }
733
734     for(aIter.Initialize (aSetFaces[i]); aIter.More(); aIter.Next()) {
735       const TopoDS_Face aFace = TopoDS::Face (aIter.Key());
736       TopTools_ListOfShape aListSEOnFace;
737
738       // select section edges on this face
739       for (aIterSE.Initialize(aListSE); aIterSE.More(); aIterSE.Next()) {
740         const TopoDS_Edge& aSecEdge = TopoDS::Edge(aIterSE.Value());
741         // check if aFace is an ancestor of aSecEdge
742         if (aMapSEdgeFaces[i]->IsBound(aSecEdge)) {
743           TopTools_ListIteratorOfListOfShape
744             aIterF (aMapSEdgeFaces[i]->Find(aSecEdge));
745           for (; aIterF.More(); aIterF.Next())
746             if (aIterF.Value().IsSame(aFace)) {
747               aListSEOnFace.Append(aSecEdge);
748               break;
749             }
750         }
751       }
752       if (!aListSEOnFace.IsEmpty())
753         SectionInsideFace (aFace, aListSEOnFace, i, aGenEdges);
754     }
755   }
756
757   // construct new shapes from myS1 and myS2
758   // and result compound
759   TopoDS_Shape aNewS[2];
760   Standard_Integer nbModified = 0;
761   Standard_Integer nbDeleted = 0;
762   Standard_Integer iShape = 0;
763
764   for (i = 0; i < 2; i++) {
765     const TopoDS_Shape& aOldS = (i==0 ? myS1 : myS2);
766     mySubst.Build(aOldS);
767     if (mySubst.IsCopied(aOldS)) {
768       if (!mySubst.Copy(aOldS).IsEmpty()) {
769         aNewS[i] = mySubst.Copy(aOldS).First();
770         aNewS[i].Orientation(aOldS.Orientation());
771         nbModified++;
772         iShape = i;
773       }
774       else if (!myAllowCutting) {
775         // all Shell is inside Solid while it is forbidden
776         return;
777       }
778       else
779         nbDeleted++;
780     }
781     else {
782       aNewS[i] = aOldS;
783       iShape = i;
784     }
785     
786     TopExp_Explorer aExp (aOldS, TopAbs_FACE);
787     for (; aExp.More(); aExp.Next()) {
788       const TopoDS_Shape& aFace = aExp.Current();
789       if(myMapModif.IsBound(aFace)) continue;
790       if (mySubst.IsCopied(aFace)) {
791         if (!mySubst.Copy(aFace).IsEmpty()) {   
792           myMapModif.Bind(aFace,mySubst.Copy(aFace));
793         }
794       }
795     }
796       
797   }
798
799   if (nbModified > 0 && nbDeleted == 0) {
800     // the usual case
801     isSolidShell = Standard_True; 
802     BRep_Builder aBld;
803     if(isSolidShell) {
804       aBld.MakeCompound (TopoDS::Compound(myShape));
805       aBld.Add(myShape, aNewS[0]);
806       aBld.Add(myShape, aNewS[1]);
807     }
808     else {
809       aBld.MakeShell (TopoDS::Shell(myShape));
810       for(anExp.Init(aNewS[0], TopAbs_FACE); anExp.More(); anExp.Next()) {
811         aBld.Add(myShape, anExp.Current());
812       }
813       for(anExp.Init(aNewS[1], TopAbs_FACE); anExp.More(); anExp.Next()) {
814         aBld.Add(myShape, anExp.Current());
815       }
816     }
817     Done();
818   }
819   else if (nbDeleted == 1) {
820     // all Shell is inside Solid while it is permitted
821     myShape = aNewS[iShape];
822     Done();
823   } else if (nbModified == 0) {
824     // The case if nothing is changed.
825     BRep_Builder aBld;
826
827     aBld.MakeCompound (TopoDS::Compound(myShape));
828     aBld.Add(myShape, aNewS[0]);
829     aBld.Add(myShape, aNewS[1]);
830     Done();
831   }
832
833   mySubst.Clear();
834   TopExp_Explorer aExp (myShape, TopAbs_EDGE);
835   Standard_Boolean IsSplit = Standard_False;
836   for (; aExp.More(); aExp.Next()) {
837     TopoDS_Edge aE = TopoDS::Edge(aExp.Current());
838     if(mySubst.IsCopied(aE)) continue;
839     aE.Orientation(TopAbs_FORWARD);
840     TopTools_ListOfShape aListSplits;
841     if(QANewModTopOpe_Tools::SplitE(aE, aListSplits)) {
842       if(!IsSplit) IsSplit = Standard_True;
843
844       BRep_Builder aBld;
845       Standard_Real aTol = Precision::Confusion();
846       TopTools_ListIteratorOfListOfShape anISpl(aListSplits);
847       for(; anISpl.More(); anISpl.Next()) {
848         const TopoDS_Shape& aSpE = anISpl.Value();
849         Standard_Real tol = BRep_Tool::Tolerance(TopoDS::Edge(aSpE));
850         if(tol > aTol) {
851           aBld.UpdateEdge(TopoDS::Edge(aSpE), 1.05*tol);
852         }
853       }
854           
855       mySubst.Substitute(aE, aListSplits);
856       myMapModif.Bind(aE, aListSplits);
857     }
858   }
859
860   if(IsSplit) {
861     mySubst.Build(myShape);
862     if(mySubst.IsCopied(myShape)) {
863       aExp.Init(myShape, TopAbs_FACE);
864       for(; aExp.More(); aExp.Next()) {
865         const TopoDS_Shape& aF = aExp.Current();
866         if(mySubst.IsCopied(aF)) {
867           myMapModif.Bind(aF, mySubst.Copy(aF));
868         }
869       }
870       myShape = mySubst.Copy(myShape).First();
871     }
872   }
873
874 }
875
876 //=======================================================================
877 //function : SplitFaceBoundary
878 //purpose  : static
879 //=======================================================================
880
881 static TopoDS_Face
882 SplitFaceBoundary (const TopoDS_Face& theFace,
883                    BRepTools_Substitution& theSubst,
884                    const BOPAlgo_PPaveFiller &thePDSFiller,
885                    const TopTools_MapOfShape& theEdgesValid,
886                    const Standard_Boolean useMap,
887                    TopTools_DataMapOfShapeListOfShape& theMapModif)
888 {
889   // split the face's edges by section edges lying on boundary
890   BRepTools_Substitution aLocalSubst;
891   TopExp_Explorer aExp (theFace, TopAbs_EDGE);
892   for (; aExp.More(); aExp.Next()) {
893     const TopoDS_Edge& aEdge = TopoDS::Edge (aExp.Current());
894     if (theSubst.IsCopied (aEdge)) continue;
895
896     TopTools_ListOfShape aListSplitE;
897     SplitEdge (aEdge, thePDSFiller, theEdgesValid, useMap, aListSplitE);
898     if (aListSplitE.IsEmpty()) continue;
899
900     theSubst.Substitute (aEdge, aListSplitE);
901     aLocalSubst.Substitute (aEdge, aListSplitE);
902 //-------------------------------------------------------------
903         //Substitution of vertices at the ends of aEdge.
904         TopoDS_Vertex aV1, aV2;
905         TopExp::Vertices(aEdge, aV1, aV2);
906         TopTools_ListIteratorOfListOfShape anIter(aListSplitE);
907         for(; anIter.More(); anIter.Next()) {
908           const TopoDS_Edge& aSpE = TopoDS::Edge(anIter.Value());
909           TopoDS_Vertex aSpV1, aSpV2;
910           TopExp::Vertices(aSpE, aSpV1, aSpV2);
911           aSpV1.Orientation(TopAbs_FORWARD);
912           aSpV2.Orientation(TopAbs_FORWARD);
913           TopTools_ListOfShape aL;
914           if(BRepTools::Compare(aV1, aSpV1) && (!aV1.IsSame(aSpV1))) {
915             aL.Clear();
916             aL.Append(aSpV1);
917             aLocalSubst.Substitute(aV1, aL);
918             theSubst.Substitute(aV1, aL);
919             if (aLocalSubst.IsCopied (aV1)) {
920               // for Mandrake-10 - mkv,02.06.06 - theMapModif.Bind(aV1, TopTools_ListOfShape());
921               TopTools_ListOfShape aListOfShape1;
922               theMapModif.Bind(aV1, aListOfShape1);
923               theMapModif(aV1).Append (aL);
924             }
925           }
926           if(BRepTools::Compare(aV1, aSpV2) && (!aV1.IsSame(aSpV2))) {
927             aL.Clear();
928             aL.Append(aSpV2);
929             aLocalSubst.Substitute(aV1, aL);
930             theSubst.Substitute(aV1, aL);
931             if (aLocalSubst.IsCopied (aV1)) {
932               // for Mandrake-10 - mkv,02.06.06 - theMapModif.Bind(aV1, TopTools_ListOfShape());
933               TopTools_ListOfShape aListOfShape2;
934               theMapModif.Bind(aV1, aListOfShape2);
935               theMapModif(aV1).Append (aL);
936             }
937           }
938           if(BRepTools::Compare(aV2, aSpV1) && (!aV2.IsSame(aSpV1))) {
939             aL.Clear();
940             aL.Append(aSpV1);
941             aLocalSubst.Substitute(aV2, aL);
942             theSubst.Substitute(aV2, aL);
943             if (aLocalSubst.IsCopied (aV2)) {
944               // for Mandrake-10 - mkv,02.06.06 - theMapModif.Bind(aV2, TopTools_ListOfShape());
945               TopTools_ListOfShape aListOfShape3;
946               theMapModif.Bind(aV2, aListOfShape3);
947               theMapModif(aV2).Append (aL);
948             }
949           }
950           if(BRepTools::Compare(aV2, aSpV2) && (!aV2.IsSame(aSpV2))) {
951             aL.Clear();
952             aL.Append(aSpV2);
953             aLocalSubst.Substitute(aV2, aL);
954             theSubst.Substitute(aV2, aL);
955             if (aLocalSubst.IsCopied (aV2)) {
956               // for Mandrake-10 - mkv,02.06.06 - theMapModif.Bind(aV2, TopTools_ListOfShape());
957               TopTools_ListOfShape aListOfShape4;
958               theMapModif.Bind(aV2, aListOfShape4);
959               theMapModif(aV2).Append (aL);
960             }
961           }
962         }
963 //-------------------------------------------------------------
964     if (aLocalSubst.IsCopied (aEdge)) {
965       // for Mandrake-10 - mkv,02.06.06 - theMapModif.Bind(aEdge, TopTools_ListOfShape());
966       TopTools_ListOfShape aListOfShape5;
967       theMapModif.Bind(aEdge, aListOfShape5);
968       theMapModif(aEdge).Append (aListSplitE);
969     }
970   }
971
972   aLocalSubst.Build (theFace);
973   if (aLocalSubst.IsCopied (theFace)) {
974 //    TopoDS_Iterator aIterF (theFace);
975 //    for (; aIterF.More(); aIterF.Next()) {
976 //      const TopoDS_Shape& aWire = aIterF.Value();
977 //      if (aLocalSubst.IsCopied (aWire))
978 //      theSubst.Substitute (aWire, aLocalSubst.Copy(aWire));
979 //    }
980     aExp.Init(theFace, TopAbs_EDGE);
981     for(; aExp.More(); aExp.Next()) {
982       const TopoDS_Shape& anE = aExp.Current();
983
984       if (aLocalSubst.IsCopied (anE)) {
985         if(!theSubst.IsCopied (anE)) {
986           theSubst.Substitute (anE, aLocalSubst.Copy(anE));
987           theMapModif.Bind(anE, aLocalSubst.Copy(anE));
988         }
989       }
990     }
991     return TopoDS::Face (aLocalSubst.Copy(theFace).First());
992   }
993   return theFace;
994 }
995
996 //=======================================================================
997 //function : CutFace
998 //purpose  : 
999 //=======================================================================
1000
1001 Standard_Boolean
1002 QANewModTopOpe_Glue::CutFace(const TopoDS_Face& theFace,
1003                         const TopTools_ListOfShape& theListSE)
1004 {
1005   Standard_Boolean aRetValue = Standard_False;
1006   if (mySubst.IsCopied(theFace)) return aRetValue;
1007
1008   // theFace may contain edges which need to be substituted
1009   mySubst.Build(theFace);
1010   TopoDS_Face aFace;
1011   if (mySubst.IsCopied(theFace)) {
1012     if (mySubst.Copy(theFace).IsEmpty()) return Standard_True;
1013     aFace = TopoDS::Face(mySubst.Copy(theFace).First());
1014   }
1015   else
1016     aFace = theFace;
1017
1018   // split the face's edges by section edges lying on boundary
1019   TopoDS_Face aFace1 = SplitFaceBoundary (aFace, mySubst, myDSFiller,
1020                                           myEdgesToLeave, Standard_False, myMapModif);
1021
1022   // split face on subfaces by section edges lying inside the face
1023   BRepFeat_SplitShape aSpliter (aFace1);
1024   TopTools_ListIteratorOfListOfShape aIterSE (theListSE);
1025   for (; aIterSE.More(); aIterSE.Next()) {
1026     const TopoDS_Edge& aSEdge = TopoDS::Edge (aIterSE.Value());
1027     if (myMapSEdgeCrossFace2.IsBound(aSEdge))
1028       aSpliter.Add (aSEdge, aFace1);
1029   }
1030   aSpliter.Build();
1031   const TopTools_ListOfShape& aListSplit = aSpliter.Modified(aFace1);
1032
1033   // get OUT splits and append them to the substitution list
1034   TopTools_ListOfShape aListToSubst;
1035   TopTools_ListIteratorOfListOfShape aIter(aListSplit);
1036   for(; aIter.More(); aIter.Next()) {
1037     const TopoDS_Face& aFaceNew = TopoDS::Face (aIter.Value());
1038     TopAbs_State aState = ClassifyFace (aFaceNew, theListSE);
1039     if (aState == TopAbs_OUT) {
1040       aListToSubst.Append(aFaceNew.Oriented(TopAbs_FORWARD));
1041       // remember in the map the section edges to leave
1042       TopExp_Explorer aExp (aFaceNew, TopAbs_EDGE);
1043       for (; aExp.More(); aExp.Next()) {
1044         const TopoDS_Shape& aEdge = aExp.Current();
1045         if (myMapSEdgeFaces2.IsBound (aEdge))
1046           myEdgesToLeave.Add (aEdge);
1047       }
1048     }
1049     else {
1050       aRetValue = Standard_True;
1051     }
1052   }
1053   mySubst.Substitute(aFace, aListToSubst);
1054
1055   // update history
1056   if (mySubst.IsCopied(aFace)) {
1057     // for Mandrake-10 - mkv,02.06.06 - myMapModif.Bind(theFace, TopTools_ListOfShape());
1058     TopTools_ListOfShape aListOfShape;
1059     myMapModif.Bind(theFace, aListOfShape);
1060     myMapModif(theFace).Append (aListToSubst);
1061   }
1062
1063   return aRetValue;
1064 }
1065
1066 //=======================================================================
1067 //function : GetVecIntoFace
1068 //purpose  : static
1069 //=======================================================================
1070
1071 static Standard_Boolean
1072 GetVecIntoFace (const TopoDS_Face& theFace,
1073                 const TopoDS_Edge& theEdge,
1074                 gp_Pnt& thePntOnEdge,
1075                 gp_Vec& theVecIntoFace)
1076 {
1077   TopoDS_Shape aDummy = theFace.Oriented(TopAbs_FORWARD);
1078   TopoDS_Face aFace = TopoDS::Face(aDummy);
1079   TopoDS_Edge aEdge;  // theEdge extracted from theFace (with orientation)
1080
1081   TopExp_Explorer aExp (aFace, TopAbs_EDGE);
1082   for (; aExp.More(); aExp.Next()) {
1083     aEdge = TopoDS::Edge (aExp.Current());
1084     if (aEdge.IsSame(theEdge)) break;
1085   }
1086   if (!aExp.More()) return Standard_False;
1087
1088   TopAbs_Orientation aOrient = aEdge.Orientation();
1089   if (aOrient != TopAbs_FORWARD && aOrient != TopAbs_REVERSED)
1090     return Standard_False;
1091
1092   Standard_Real aParF, aParL;
1093   Handle(Geom2d_Curve) aCrv = BRep_Tool::CurveOnSurface(aEdge, aFace, aParF, aParL);
1094   if (aCrv.IsNull()) return Standard_False;
1095   if (aCrv->Continuity() < GeomAbs_C1) return Standard_False;
1096
1097   // get middle point on edge and normal
1098   Standard_Real aParM = aParF + (aParL - aParF) * 0.618;
1099   gp_Pnt2d aPntOnCrv;
1100   gp_Vec2d aDeriv;
1101   aCrv->D1(aParM, aPntOnCrv, aDeriv);
1102   gp_Vec2d aNormal(-aDeriv.Y(), aDeriv.X());
1103   aNormal.Normalize();
1104   if (aOrient == TopAbs_REVERSED) aNormal.Reverse();
1105
1106   // translate middle point along the normal
1107   Standard_Real uMin, uMax, vMin, vMax;
1108   BRepTools::UVBounds(aFace, uMin, uMax, vMin, vMax);
1109   Standard_Real duv = Min(uMax - uMin, vMax - vMin) * 0.1;
1110   Standard_Real dtol = BRep_Tool::Tolerance(aEdge) * 100.;
1111   Standard_Real d = Min(duv, dtol);
1112   gp_Pnt2d aPntOnSurf = aPntOnCrv.Translated(aNormal * d);
1113
1114   // get 3d points
1115   Handle(Geom_Surface) aSurf = BRep_Tool::Surface(aFace);
1116   gp_Pnt aPntOnFace;
1117   aSurf->D0(aPntOnSurf.X(), aPntOnSurf.Y(), aPntOnFace);
1118   aSurf->D0(aPntOnCrv.X(), aPntOnCrv.Y(), thePntOnEdge);
1119
1120   // compute theVecIntoFace
1121   theVecIntoFace = gp_Vec(thePntOnEdge, aPntOnFace);
1122   Standard_Real aNorm = theVecIntoFace.Magnitude();
1123   if (aNorm < Precision::Confusion())
1124     return Standard_False;
1125   theVecIntoFace.Divide(aNorm);
1126
1127   return Standard_True;
1128 }
1129
1130 //=======================================================================
1131 //function : ClassifyFace
1132 //purpose  : 
1133 //=======================================================================
1134
1135 TopAbs_State
1136 QANewModTopOpe_Glue::ClassifyFace(const TopoDS_Face& theFace,
1137                              const TopTools_ListOfShape& theListSE) const
1138 {
1139   TopAbs_State aState = TopAbs_UNKNOWN;
1140
1141   TopTools_ListIteratorOfListOfShape aIterSE (theListSE);
1142   for (; aIterSE.More(); aIterSE.Next()) {
1143     const TopoDS_Edge& aEdge = TopoDS::Edge (aIterSE.Value());
1144
1145     // get a point on edge and a vector directed to inside face
1146     // relatively that point
1147     gp_Pnt aPntOnEdge;
1148     gp_Vec aVecIntoFace;
1149     if (BRep_Tool::Degenerated(aEdge) ||
1150         !GetVecIntoFace (theFace, aEdge, aPntOnEdge, aVecIntoFace))
1151       continue;
1152
1153     // get faces from solid
1154     if (!myMapSEdgeFaces1.IsBound(aEdge)) continue;
1155     TopTools_ListIteratorOfListOfShape aIterF (myMapSEdgeFaces1(aEdge));
1156     for (; aIterF.More(); aIterF.Next()) {
1157       const TopoDS_Face& aFaceSol = TopoDS::Face(aIterF.Value());
1158       TopAbs_Orientation aOrient = aFaceSol.Orientation();
1159       if (aOrient != TopAbs_FORWARD && aOrient != TopAbs_REVERSED)
1160         continue;
1161
1162       // classify theFace relatively aFaceSol
1163
1164       // get normal to the surface at the point aPntOnEdge
1165       Handle(Geom_Surface) aSurf = BRep_Tool::Surface(aFaceSol);
1166       GeomAPI_ProjectPointOnSurf aProjector(aPntOnEdge, aSurf);
1167       if (!aProjector.IsDone()) continue;
1168       Standard_Real u,v;
1169       aProjector.LowerDistanceParameters(u,v);
1170       gp_Vec d1u,d1v;
1171       gp_Pnt aPntProj;
1172       aSurf->D1(u, v, aPntProj, d1u, d1v);
1173       gp_Vec aNormal = d1u.Crossed(d1v);
1174       if (aOrient == TopAbs_REVERSED) aNormal.Reverse();
1175
1176       // compare normal and the vector "into face"
1177       Standard_Real aScalar = aVecIntoFace * aNormal;
1178       if (aScalar > Precision::Confusion()) {
1179         aState = TopAbs_OUT;
1180         break;
1181       }
1182       else if (aScalar < -Precision::Confusion())
1183         aState = TopAbs_IN;
1184       else
1185         aState = TopAbs_ON;
1186     }
1187     if (aState == TopAbs_IN || aState == TopAbs_ON)
1188       break;
1189   }
1190
1191   return aState;
1192 }
1193
1194 //=======================================================================
1195 //function : IsVertexOnFaceBound
1196 //purpose  : static
1197 //=======================================================================
1198
1199 static Standard_Boolean
1200 IsVertexOnFaceBound (const TopoDS_Vertex& theVer,
1201                      const TopoDS_Face& theFace,
1202                      TopoDS_Edge& theEdgeContacted,
1203                      TopoDS_Vertex& theVerContacted,
1204                      Standard_Real& thePar,
1205                      Standard_Real& theDist)
1206 {
1207   Standard_Real aDist, aPar, aTol2 = 0.;
1208   theDist = RealLast();
1209   gp_Pnt aPnt(BRep_Tool::Pnt(theVer));
1210   Standard_Boolean isContactByVer = Standard_False;
1211
1212   TopExp_Explorer aExp (theFace.Oriented(TopAbs_FORWARD), TopAbs_EDGE);
1213   for (; aExp.More() && theDist > Precision::Confusion(); aExp.Next()) {
1214     const TopoDS_Edge& aEdge = TopoDS::Edge (aExp.Current());
1215
1216     // first compare by vertices
1217     TopoDS_Iterator aIter (aEdge, Standard_False);
1218     for (; aIter.More(); aIter.Next()) {
1219       const TopoDS_Vertex& aVer = TopoDS::Vertex (aIter.Value());
1220       if (aVer.IsSame(theVer)) {
1221         theEdgeContacted = aEdge;
1222         theVerContacted = aVer;
1223         return Standard_True;
1224       }
1225       if (QANewModTopOpe_Glue::CompareVertices (aVer, theVer, aDist)) {
1226         if (aDist < theDist) {
1227           theEdgeContacted = aEdge;
1228           theVerContacted = aVer;
1229           theDist = aDist;
1230           thePar = BRep_Tool::Parameter (aVer, aEdge);
1231           aTol2 = BRep_Tool::Tolerance (aVer);
1232           isContactByVer = Standard_True;
1233         }
1234       }
1235     }
1236
1237     if (!isContactByVer) {
1238       // project on edge
1239       if (!BRep_Tool::Degenerated(aEdge)) {
1240         if (QANewModTopOpe_Glue::ProjPointOnEdge (aPnt, aEdge, aPar, aDist)) {
1241           if (aDist < theDist) {
1242             theEdgeContacted = aEdge;
1243             theVerContacted.Nullify();
1244             theDist = aDist;
1245             thePar = aPar;
1246             aTol2 = BRep_Tool::Tolerance(aEdge);
1247           }
1248         }
1249       }
1250     }
1251   }
1252
1253   if (theDist <= BRep_Tool::Tolerance(theVer) || theDist <= aTol2)
1254     return Standard_True;
1255
1256   return Standard_False;
1257 }
1258
1259 //=======================================================================
1260 //function : UpdateMapNewOld
1261 //purpose  : static
1262 //=======================================================================
1263
1264 static void
1265 UpdateMapNewOld (const TopoDS_Shape& theSh, const BRepTools_Substitution& theSubst,
1266                  TopTools_DataMapOfShapeShape& theMapNewOld)
1267 {
1268   TopTools_IndexedMapOfShape aMapSh;
1269   TopExp::MapShapes (theSh, aMapSh);
1270
1271   for (Standard_Integer i=1; i<=aMapSh.Extent(); i++) {
1272     const TopoDS_Shape& aSubSh = aMapSh(i);
1273     if (!aSubSh.IsSame(theSh) && theSubst.IsCopied (aSubSh)) {
1274       TopTools_ListIteratorOfListOfShape aIt (theSubst.Copy(aSubSh));
1275       for (; aIt.More(); aIt.Next()) {
1276         const TopoDS_Shape& aNewSubSh = aIt.Value();
1277         if (theMapNewOld.IsBound(aSubSh)) {
1278           TopoDS_Shape aOldSubSh = theMapNewOld(aSubSh);
1279           theMapNewOld.UnBind (aSubSh);
1280           theMapNewOld.Bind (aNewSubSh, aOldSubSh);
1281         }
1282         else {
1283           theMapNewOld.Bind (aNewSubSh, aSubSh);
1284         }
1285       }
1286     }
1287   }
1288 }
1289
1290 //=======================================================================
1291 //function : DoLocalSubstitution
1292 //purpose  : static
1293 //=======================================================================
1294
1295 static void
1296 DoLocalSubstitution (TopoDS_Shape& theSh, const TopoDS_Shape& theSubSh,
1297                      const TopoDS_Shape& theNewSubSh,
1298                      TopTools_DataMapOfShapeShape& theMapNewOld)
1299 {
1300   BRepTools_Substitution aLocalSubst;
1301   TopTools_ListOfShape aList;
1302   aList.Append (theNewSubSh.Oriented(TopAbs_FORWARD));
1303   aLocalSubst.Substitute (theSubSh, aList);
1304   aLocalSubst.Build(theSh);
1305
1306   if (aLocalSubst.IsCopied(theSh)) {
1307     UpdateMapNewOld (theSh, aLocalSubst, theMapNewOld);
1308     theSh = aLocalSubst.Copy(theSh).First();
1309   }
1310 }
1311
1312 //=======================================================================
1313 //function : SectionInsideFace
1314 //purpose  : 
1315 //=======================================================================
1316
1317 void
1318 QANewModTopOpe_Glue::SectionInsideFace(const TopoDS_Face& theFace,
1319                                   const TopTools_ListOfShape& theListSE,
1320                                   const Standard_Integer theShapeNum, 
1321                                   const TopTools_MapOfShape& theGenEdges) 
1322 {
1323   if (mySubst.IsCopied(theFace)) return;
1324
1325   // theFace may contain edges which need to be substituted
1326   mySubst.Build(theFace);
1327   TopoDS_Face aFace;
1328   if (mySubst.IsCopied(theFace)) {
1329     if (mySubst.Copy(theFace).IsEmpty()) return;
1330     aFace = TopoDS::Face(mySubst.Copy(theFace).First());
1331   }
1332   else
1333     aFace = theFace;
1334
1335   // split the face's edges by section edges lying on boundary
1336   TopoDS_Face aFace1 = SplitFaceBoundary (aFace, mySubst, myDSFiller,
1337                                           myEdgesToLeave, Standard_True, myMapModif);
1338   TopTools_DataMapOfShapeShape aMapNewOrig;
1339   UpdateMapNewOld (theFace, mySubst, aMapNewOrig);
1340
1341   // process section edges contacting the face boundary:
1342   // insert internal vertices in the boundary
1343   const TopTools_DataMapOfShapeShape& aMapEF =
1344     (theShapeNum==0 ? myMapSEdgeCrossFace1 : myMapSEdgeCrossFace2);
1345   BRep_Builder aBld;
1346   TopTools_DataMapOfShapeShape aMapNewOld;
1347   TopTools_ListIteratorOfListOfShape aIterSE (theListSE);
1348
1349   TopTools_MapOfShape aVerGener;
1350
1351   for (; aIterSE.More(); aIterSE.Next()) {
1352     const TopoDS_Edge& aSEdge = TopoDS::Edge (aIterSE.Value());
1353     // skip edges lying on the boundary
1354     if (!aMapEF.IsBound (aSEdge)) continue;
1355
1356     // check if vertices of aSEdge contacts edges of aFace
1357     TopoDS_Iterator aIter (aSEdge, Standard_False);
1358     for (; aIter.More(); aIter.Next()) {
1359       TopoDS_Vertex aSVer = TopoDS::Vertex (aIter.Value());
1360       if (aSVer.Orientation() != TopAbs_FORWARD &&
1361           aSVer.Orientation() != TopAbs_REVERSED) continue;
1362
1363       TopoDS_Edge aEdge;
1364       TopoDS_Vertex aVer;
1365       Standard_Real aPar=0.0, aDist;
1366       if (IsVertexOnFaceBound (aSVer, aFace1, aEdge, aVer, aPar, aDist)) {
1367         // aSVer contacts aFace's boundary
1368
1369         if (!aVer.IsNull()) { // vertex contacted
1370           if (!aVer.IsSame(aSVer)) {
1371             // the vertices are coincided but not the same
1372             // => substitute aVer with aSVer
1373             Standard_Real aTol = Max (BRep_Tool::Tolerance(aSVer),
1374                                       BRep_Tool::Tolerance(aVer) + aDist);
1375             TopAbs_Orientation aOri = aVer.Orientation();
1376             if (aOri != TopAbs_FORWARD && aOri != TopAbs_REVERSED) {
1377               TopoDS_Shape aDummy = aSVer.Oriented(aOri);
1378               aBld.UpdateVertex (TopoDS::Vertex (aDummy),
1379                                  aPar, aEdge, aTol);
1380             }
1381             DoLocalSubstitution (aFace1, aVer, aSVer, aMapNewOld);
1382             // update history
1383             TopoDS_Shape aOrig = aMapNewOld(aSVer);
1384             if (aMapNewOrig.IsBound(aOrig)) aOrig = aMapNewOrig(aOrig);
1385             // for Mandrake-10 - mkv,02.06.06 - myMapModif.Bind(aOrig, TopTools_ListOfShape());
1386             TopTools_ListOfShape aListOfShape1;
1387             myMapModif.Bind(aOrig, aListOfShape1);
1388             myMapModif(aOrig).Append (aSVer);
1389             aVerGener.Add(aSVer);
1390             continue;
1391           }
1392         }
1393
1394         else { // contact inside edge
1395           // add the vertex as internal to the edge of the face
1396           TopoDS_Edge aNewEdge;
1397           InsertVertexInEdge (aEdge, aSVer, aPar, aNewEdge);
1398           // substitute edge
1399           DoLocalSubstitution (aFace1, aEdge, aNewEdge, aMapNewOld);
1400           // update history
1401           const TopoDS_Shape& aOld = aMapNewOld(aNewEdge);
1402           TopoDS_Shape aOrig;
1403           if (aMapNewOrig.IsBound(aOld)) {
1404             aOrig = aMapNewOrig(aOld);
1405             TopTools_ListOfShape& aListModif = myMapModif(aOrig);
1406             TopTools_ListIteratorOfListOfShape aIt (aListModif);
1407             for (; aIt.More(); aIt.Next())
1408               if (aIt.Value().IsSame(aOld)) {
1409                 aListModif.Remove (aIt);
1410                 break;
1411               }
1412             aListModif.Append (aNewEdge);
1413           }
1414           else {
1415             aOrig = aOld;
1416             // for Mandrake-10 - mkv,02.06.06 - myMapModif.Bind(aOrig, TopTools_ListOfShape());
1417             TopTools_ListOfShape aListOfShape2;
1418             myMapModif.Bind(aOrig, aListOfShape2);
1419             myMapModif(aOrig).Append (aNewEdge);
1420           }
1421           if (!myMapGener.IsBound (aOrig)) {
1422             // for Mandrake-10 - mkv,02.06.06 - myMapGener.Bind(aOrig, TopTools_ListOfShape());
1423             TopTools_ListOfShape aListOfShape3;
1424             myMapGener.Bind(aOrig, aListOfShape3);
1425           }
1426           myMapGener(aOrig).Append (aSVer);
1427           aVerGener.Add(aSVer);
1428         }
1429       }
1430     }
1431   }
1432
1433   // add the made replacements in the global substitution list
1434   TopTools_DataMapIteratorOfDataMapOfShapeShape aDIter (aMapNewOld);
1435   for (; aDIter.More(); aDIter.Next()) {
1436     TopTools_ListOfShape aList;
1437     const TopoDS_Shape& aOld = aDIter.Value();
1438     const TopoDS_Shape& aNew = aDIter.Key();
1439     aList.Append (aNew);
1440     mySubst.Substitute (aOld, aList);
1441   }
1442
1443   // make wires from section edges
1444   Handle(BRepAlgo_EdgeConnector) aConnector = new BRepAlgo_EdgeConnector;
1445   TopTools_ListOfShape aListGener;
1446   TopoDS_Vertex aV1, aV2;
1447   for (aIterSE.Initialize (theListSE); aIterSE.More(); aIterSE.Next()) {
1448     const TopoDS_Edge& aSEdge = TopoDS::Edge (aIterSE.Value());
1449     if (aMapEF.IsBound (aSEdge)) {
1450       aConnector->Add (aSEdge);
1451       aConnector->AddStart (aSEdge);
1452       if(theGenEdges.Contains(aSEdge)) {
1453         aListGener.Append (aSEdge);
1454         TopExp::Vertices(aSEdge, aV1, aV2);
1455         if(aVerGener.Add(aV1)) aListGener.Append (aV1);
1456         if(aVerGener.Add(aV2)) aListGener.Append (aV2);
1457       }
1458     }
1459   }
1460   const TopTools_ListOfShape& aListW = aConnector->MakeBlock();
1461   if (aConnector->IsDone()) {
1462     // add new wires to face
1463     TopoDS_Face aNewFace = aFace1;
1464     aNewFace.EmptyCopy();
1465     aNewFace.Orientation(TopAbs_FORWARD);
1466     aBld.NaturalRestriction (aNewFace, BRep_Tool::NaturalRestriction(aFace1));
1467     // add old subshapes
1468     TopoDS_Iterator aIterF (aFace1, Standard_False);
1469     for (; aIterF.More(); aIterF.Next()) {
1470       aBld.Add (aNewFace, aIterF.Value());
1471     }
1472     // add new wires as internal
1473     TopTools_ListIteratorOfListOfShape aIterL (aListW);
1474     for (; aIterL.More(); aIterL.Next()) {
1475       TopoDS_Shape aWire = aIterL.Value();
1476       // check if there is a wire containing the same set of edges;
1477       // in this case use the old wire
1478       aWire = FindWireOrUpdateMap (aWire, myMapEdgeWires);
1479       aBld.Add (aNewFace, aWire.Oriented(TopAbs_INTERNAL));
1480     }
1481     // substitute face
1482     TopTools_ListOfShape aList;
1483     aList.Append(aNewFace);
1484     mySubst.Substitute(aFace, aList);
1485     // update history
1486     // for Mandrake-10 - mkv,02.06.06 - myMapModif.Bind(theFace, TopTools_ListOfShape());
1487     TopTools_ListOfShape aListOfShape4;
1488     myMapModif.Bind(theFace, aListOfShape4);
1489     myMapModif(theFace).Append (aList);
1490     if(!aListGener.IsEmpty()) {
1491       // for Mandrake-10 - mkv,02.06.06 - myMapGener.Bind(theFace, TopTools_ListOfShape());
1492       TopTools_ListOfShape aListOfShape5;
1493       myMapGener.Bind(theFace, aListOfShape5);
1494       myMapGener(theFace).Append (aListGener);
1495     }
1496   }
1497 #ifdef DEB
1498   else if (!aListW.IsEmpty()) {
1499     cout<<"QANewModTopOpe_Glue::SectionInsideFace : can't connect edges"<<endl;
1500   }
1501 #endif
1502 }