0028577: Get rid of the TopOpeBRep* algorithms in TKOffset toolkit
[occt.git] / src / BRepLib / BRepLib_FuseEdges.cxx
1 // Created on: 1998-11-26
2 // Created by: Jean-Michel BOULCOURT
3 // Copyright (c) 1998-1999 Matra Datavision
4 // Copyright (c) 1999-2014 OPEN CASCADE SAS
5 //
6 // This file is part of Open CASCADE Technology software library.
7 //
8 // This library is free software; you can redistribute it and/or modify it under
9 // the terms of the GNU Lesser General Public License version 2.1 as published
10 // by the Free Software Foundation, with special exception defined in the file
11 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
12 // distribution for complete text of the license and disclaimer of any warranty.
13 //
14 // Alternatively, this file may be used under the terms of Open CASCADE
15 // commercial license or contractual agreement.
16
17 // Modif : Wed Jan 20 15:40:50 1999. In BuildListResultEdges, we 
18 // in UpdatePcurve, problem with location of pcurve (mix between loc and locbid)
19 // Modif : Thu Jan 21 11:40:20 1999. Add trace context #if DEB
20 //           add test to avoid loop while in NextConnexEdge (in case of a closed connex wire)
21
22 #include <BRep_Builder.hxx>
23 #include <BRep_Tool.hxx>
24 #include <BRepLib.hxx>
25 #include <BRepLib_FuseEdges.hxx>
26 #include <BRepLib_MakeEdge.hxx>
27 #include <BRepTools_Substitution.hxx>
28 #include <BSplCLib.hxx>
29 #include <ElCLib.hxx>
30 #include <ElSLib.hxx>
31 #include <Extrema_LocateExtPC.hxx>
32 #include <Geom2d_BoundedCurve.hxx>
33 #include <Geom2d_BSplineCurve.hxx>
34 #include <Geom2d_Curve.hxx>
35 #include <Geom2d_TrimmedCurve.hxx>
36 #include <Geom2dConvert_CompCurveToBSplineCurve.hxx>
37 #include <Geom_BezierCurve.hxx>
38 #include <Geom_BoundedCurve.hxx>
39 #include <Geom_BSplineCurve.hxx>
40 #include <Geom_Circle.hxx>
41 #include <Geom_Curve.hxx>
42 #include <Geom_Ellipse.hxx>
43 #include <Geom_Line.hxx>
44 #include <Geom_Plane.hxx>
45 #include <Geom_TrimmedCurve.hxx>
46 #include <GeomAdaptor_Curve.hxx>
47 #include <GeomConvert.hxx>
48 #include <GeomConvert_CompCurveToBSplineCurve.hxx>
49 #include <GeomLib.hxx>
50 #include <gp_Dir2d.hxx>
51 #include <gp_Pnt2d.hxx>
52 #include <gp_Trsf2d.hxx>
53 #include <gp_Vec2d.hxx>
54 #include <Precision.hxx>
55 #include <Standard_ConstructionError.hxx>
56 #include <Standard_NullObject.hxx>
57 #include <TColgp_Array1OfPnt.hxx>
58 #include <TColStd_Array1OfInteger.hxx>
59 #include <TColStd_Array1OfReal.hxx>
60 #include <TopExp.hxx>
61 #include <TopExp_Explorer.hxx>
62 #include <TopoDS.hxx>
63 #include <TopoDS_Edge.hxx>
64 #include <TopoDS_Face.hxx>
65 #include <TopoDS_Shape.hxx>
66 #include <TopoDS_Vertex.hxx>
67 #include <TopoDS_Wire.hxx>
68 #include <TopTools_DataMapIteratorOfDataMapOfIntegerListOfShape.hxx>
69 #include <TopTools_DataMapOfIntegerListOfShape.hxx>
70 #include <TopTools_ListIteratorOfListOfShape.hxx>
71 #include <TopTools_ListOfShape.hxx>
72 #include <TopTools_MapOfShape.hxx>
73
74 static void BCSmoothing(Handle(Geom_BSplineCurve)& theC,
75                         const Standard_Integer theCont,
76                         const Standard_Real theTol)
77 {
78
79   Standard_Integer aNbIter = 5;
80   Standard_Boolean bContinue = Standard_True;
81   Standard_Integer iter = 1;
82   TColStd_SequenceOfInteger aKnotIndex;
83   TColStd_SequenceOfReal aKnotIns;
84
85   while (bContinue && iter <= aNbIter) {
86
87     Standard_Integer aNbKnots = theC->NbKnots();
88     TColStd_Array1OfInteger aMults(1, aNbKnots);
89     TColStd_Array1OfReal aKnots(1, aNbKnots);
90
91     theC->Multiplicities(aMults);
92     theC->Knots(aKnots);
93     Standard_Integer i, m = theC->Degree();
94     m = m - theCont;
95
96     if(m < 1) return;
97
98     aKnotIndex.Clear();
99
100     for(i = 2; i < aNbKnots; i++) {
101       if(aMults(i) > m) {
102         if(!(theC->RemoveKnot(i, m, theTol))) {
103           aKnotIndex.Append(i);
104         }
105       }
106     }
107
108     //Prepare knots for inserting;
109
110     Standard_Integer aNbAdd = aKnotIndex.Length();
111
112     if(aNbAdd == 0) return;
113
114     aKnotIns.Clear();
115
116     Standard_Real aLastKnot = aKnots(1);
117     for(i = 1; i <= aNbAdd; i++) {
118
119       Standard_Integer anInd = aKnotIndex(i);
120
121       Standard_Real aK1 = 0.5*(aKnots(anInd) + aKnots(anInd-1));
122       if(Abs(aK1 - aLastKnot) > 1.e-3) {
123         aKnotIns.Append(aK1);
124         aLastKnot = aK1;
125       }
126       
127       Standard_Real aK2 = 0.5*(aKnots(anInd+1) + aKnots(anInd));
128
129       if(Abs(aK2 - aLastKnot) > 1.e-3) {
130         aKnotIns.Append(aK2);
131         aLastKnot = aK2;
132       }
133  
134     }
135
136     aNbAdd = aKnotIns.Length();
137     
138     for(i = 1; i <= aNbAdd; i++) {
139       theC->InsertKnot(aKnotIns(i), m, 1.e-3);
140     }
141
142     iter++;
143
144   }
145
146   if(iter > aNbIter) BCSmoothing(theC, theCont, 1.e10);
147
148   return;
149 }
150
151 static void MakeClosedCurve(Handle(Geom_Curve)& C, const gp_Pnt& PF, 
152                             Standard_Real& f, Standard_Real& l)
153 {
154   Handle(Geom_BSplineCurve) aBC = Handle(Geom_BSplineCurve)::DownCast (C);
155   GeomAbs_Shape aCont = aBC->Continuity();
156   //Find new origin
157   aBC->SetPeriodic();
158   Standard_Integer fk = aBC->FirstUKnotIndex();
159   Standard_Integer lk = aBC->LastUKnotIndex();
160   Standard_Integer k;
161   Standard_Real eps = Precision::Confusion();
162   eps *= eps;
163   Standard_Real porig = 2.*l;
164   Standard_Real dmin = 1.e100, pmin = f;
165   for(k = fk; k <= lk; k++) {
166     gp_Pnt aP = aBC->Value(aBC->Knot(k));
167     Standard_Real d = PF.SquareDistance(aP);
168     if(PF.SquareDistance(aP) > eps) {
169       if(d < dmin) {
170         pmin = aBC->Knot(k);
171         dmin = d;
172       }
173       continue;
174     }
175
176     porig = aBC->Knot(k);
177     break;
178   }
179   if(porig > l) {
180     //try to project
181     GeomAdaptor_Curve aGAC(aBC);
182     Extrema_LocateExtPC aPrj(PF, aGAC, pmin, Precision::PConfusion());
183     if(aPrj.IsDone()) {
184       porig = aPrj.Point().Parameter();
185     }
186     else {
187       throw Standard_ConstructionError("FuseEdges : Projection failed for closed curve");
188     }
189   }
190             
191   aBC->SetOrigin(porig, Precision::PConfusion());
192   f = aBC->FirstParameter();
193   l = aBC->LastParameter();
194   aBC->Segment(f, l);
195   if(aCont > GeomAbs_C0 && aBC->Continuity() == GeomAbs_C0) {
196     BCSmoothing(aBC, 1, Precision::Confusion());
197   }
198   C = aBC;
199   f = C->FirstParameter();
200   l = C->LastParameter();
201 }
202
203
204
205 //=======================================================================
206 //function : BRepLib_FuseEdges
207 //purpose  : 
208 //=======================================================================
209
210 BRepLib_FuseEdges::BRepLib_FuseEdges(const TopoDS_Shape& theShape,
211 //                                                   const Standard_Boolean PerformNow)
212                                                    const Standard_Boolean )
213 :myShape(theShape),myShapeDone(Standard_False),myEdgesDone(Standard_False),
214  myResultEdgesDone(Standard_False),myNbConnexEdge(0), myConcatBSpl(Standard_False)
215 {
216 //  if (theShape.ShapeType() != TopAbs_SHELL && theShape.ShapeType() != TopAbs_SOLID)
217 //    throw Standard_ConstructionError("FuseEdges");
218   Standard_NullObject_Raise_if(theShape.IsNull(),"FuseEdges");
219   myMapFaces.Clear();
220
221 }
222
223 //=======================================================================
224 //function : AvoidEdges
225 //purpose  : set edges to avoid being fused
226 //=======================================================================
227
228 void BRepLib_FuseEdges::AvoidEdges(const TopTools_IndexedMapOfShape& theMapEdg)
229 {
230   myAvoidEdg = theMapEdg;
231 }
232
233 //=======================================================================
234 //function : SetConcatBSpl
235 //purpose  : 
236 //=======================================================================
237
238 void BRepLib_FuseEdges::SetConcatBSpl(const Standard_Boolean theConcatBSpl)
239 {
240   myConcatBSpl = theConcatBSpl;
241 }
242
243 //=======================================================================
244 //function : Edges
245 //purpose  : returns  all the list of edges to be fused each list of the 
246 //           map represent a set of connex edges that can be fused.
247 //=======================================================================
248
249 void BRepLib_FuseEdges::Edges(TopTools_DataMapOfIntegerListOfShape& theMapLstEdg)
250 {
251
252   if (!myEdgesDone) {
253     BuildListEdges();
254   }
255
256   theMapLstEdg = myMapLstEdg;
257 }
258
259
260 //=======================================================================
261 //function : ResultEdges
262 //purpose  : returns  all the fused edges
263 //=======================================================================
264
265 void BRepLib_FuseEdges::ResultEdges(TopTools_DataMapOfIntegerShape& theMapEdg)
266 {
267
268   if (!myEdgesDone) {
269     BuildListEdges();
270   }
271
272   if (!myResultEdgesDone) {
273     BuildListResultEdges();
274   }
275
276   theMapEdg = myMapEdg;
277 }
278
279 //=======================================================================
280 //function : Faces
281 //purpose  : returns  all the faces that have been modified after perform
282 //=======================================================================
283
284 void BRepLib_FuseEdges::Faces(TopTools_DataMapOfShapeShape& theMapFac)
285 {
286
287   if (!myEdgesDone) {
288     BuildListEdges();
289   }
290
291   if (!myResultEdgesDone) {
292     BuildListResultEdges();
293   }
294
295   if (!myShapeDone) {
296     Perform();
297   }
298
299   theMapFac = myMapFaces;
300 }
301
302
303 //=======================================================================
304 //function : NbVertices
305 //purpose  : 
306 //=======================================================================
307
308 Standard_Integer BRepLib_FuseEdges::NbVertices()
309 {
310
311   Standard_NullObject_Raise_if(myShape.IsNull(),"FuseEdges : No Shape");
312   Standard_Integer nbedges, nbvertices = 0;
313
314   if (!myEdgesDone) {
315     BuildListEdges();
316   }
317
318   if ((nbedges = myMapLstEdg.Extent()) > 0) {
319
320     TopTools_DataMapIteratorOfDataMapOfIntegerListOfShape itEdg;
321     for (itEdg.Initialize(myMapLstEdg); itEdg.More(); itEdg.Next()) {
322       const Standard_Integer& iLst = itEdg.Key();
323       const TopTools_ListOfShape& LmapEdg = myMapLstEdg.Find(iLst);
324       nbvertices += LmapEdg.Extent() - 1;
325     }    
326   }
327
328   return nbvertices;
329
330 }
331
332
333 //=======================================================================
334 //function : Shape
335 //purpose  : 
336 //=======================================================================
337
338 TopoDS_Shape& BRepLib_FuseEdges::Shape()
339 {
340   Standard_NullObject_Raise_if(myShape.IsNull(),"FuseEdges : No Shape");
341
342   if (!myEdgesDone) {
343     BuildListEdges();
344   }
345
346   if (!myResultEdgesDone) {
347     BuildListResultEdges();
348   }
349
350   if (!myShapeDone) {
351     Perform();
352   }
353
354   return myShape;
355 }
356
357
358
359 //=======================================================================
360 //function : BuildListEdges
361 //purpose  : Build the all the lists of edges that are to be fused
362 //=======================================================================
363
364 void BRepLib_FuseEdges::BuildListEdges()
365 {
366   //--------------------------------------------------------
367   // Step One : Build the map ancestors
368   //--------------------------------------------------------
369   
370   // Clear the maps
371   myMapLstEdg.Clear();
372   myMapVerLstEdg.Clear();
373   myMapEdgLstFac.Clear();
374   
375   TopExp::MapShapesAndUniqueAncestors(myShape,TopAbs_VERTEX,TopAbs_EDGE,myMapVerLstEdg);
376   TopExp::MapShapesAndAncestors(myShape,TopAbs_EDGE,TopAbs_FACE,myMapEdgLstFac);
377
378   Standard_Integer iEdg;
379   TopTools_MapOfShape mapUniqEdg;
380
381   // for each edge of myMapEdgLstFac
382   for (iEdg = 1; iEdg <= myMapEdgLstFac.Extent(); iEdg++) {
383     const TopoDS_Shape& edgecur = myMapEdgLstFac.FindKey(iEdg);
384     TopTools_ListOfShape LstEdg;
385
386     // if edge not already treated
387     if (!mapUniqEdg.Contains(edgecur) 
388         && (edgecur.Orientation() == TopAbs_FORWARD ||edgecur.Orientation() == TopAbs_REVERSED) ) {
389       if (myAvoidEdg.Contains(edgecur))
390         continue;       // edge is not allowed to be fused
391       BuildListConnexEdge(edgecur, mapUniqEdg, LstEdg);
392       if (LstEdg.Extent() > 1) {
393         myNbConnexEdge++;
394         myMapLstEdg.Bind(myNbConnexEdge,LstEdg);
395       }
396     }
397   }
398
399   myEdgesDone = Standard_True;
400   myResultEdgesDone = Standard_False;
401 }
402
403
404 //=======================================================================
405 //function : BuildListResultEdges
406 //purpose  : Build the result fused edges
407 //=======================================================================
408
409 void BRepLib_FuseEdges::BuildListResultEdges()
410 {
411   // if we have edges to fuse
412   if (myMapLstEdg.Extent() > 0) {
413     TopTools_DataMapIteratorOfDataMapOfIntegerListOfShape itLstEdg;
414     TopoDS_Vertex VF,VL;
415     Handle(Geom_Curve) C;
416     TopLoc_Location loc;
417     Standard_Real f,l;
418     TopoDS_Edge NewEdge;
419
420     myMapEdg.Clear();
421
422     for (itLstEdg.Initialize(myMapLstEdg); itLstEdg.More(); itLstEdg.Next()) {
423       const Standard_Integer& iLst = itLstEdg.Key();
424       const TopTools_ListOfShape& LmapEdg = myMapLstEdg.Find(iLst);
425
426       TopoDS_Edge OldEdge = TopoDS::Edge(LmapEdg.First());
427
428       // the first edge of the list will be replaced by the result fusion edge
429       if (OldEdge.Orientation()==TopAbs_REVERSED) {
430         VL = TopExp::FirstVertex(TopoDS::Edge(LmapEdg.First()),Standard_True);
431         VF = TopExp::LastVertex(TopoDS::Edge(LmapEdg.Last()),Standard_True);
432       }
433       else {
434         VF = TopExp::FirstVertex(TopoDS::Edge(LmapEdg.First()),Standard_True);
435         VL = TopExp::LastVertex(TopoDS::Edge(LmapEdg.Last()),Standard_True);
436       }
437       C = BRep_Tool::Curve(OldEdge,loc,f,l);
438
439       if (!loc.IsIdentity()) {
440         C = Handle(Geom_Curve)::DownCast(C->Transformed(loc.Transformation()));
441       }
442       // if the curve is trimmed we get the basis curve to fit the new vertices
443       // otherwise the makeedge will fail.
444       if (C->DynamicType() == STANDARD_TYPE(Geom_TrimmedCurve)) {
445         C = Handle(Geom_TrimmedCurve)::DownCast (C)->BasisCurve();
446       }
447
448       if(myConcatBSpl) {
449         //Prepare common BSpline curve
450         if(C->DynamicType() == STANDARD_TYPE(Geom_BSplineCurve)) {
451           TopTools_ListIteratorOfListOfShape anEdgIter(LmapEdg);
452           Handle(Geom_TrimmedCurve) aTC = new Geom_TrimmedCurve(C, f, l);
453           GeomConvert_CompCurveToBSplineCurve Concat( aTC );
454
455           anEdgIter.Next();
456           for(; anEdgIter.More(); anEdgIter.Next()) {
457             Handle(Geom_Curve) aC = BRep_Tool::Curve(TopoDS::Edge(anEdgIter.Value()), f, l);
458             aTC = new Geom_TrimmedCurve(aC, f, l);
459             if (!Concat.Add(aTC, Precision::Confusion())) {
460                   // cannot merge curves
461               throw Standard_ConstructionError("FuseEdges : Concatenation failed");
462             }
463           }
464           C = Concat.BSplineCurve();                    
465         }
466       }
467
468   
469       BRepLib_MakeEdge ME;
470       
471       Standard_Boolean isBSpline = C->DynamicType() == STANDARD_TYPE(Geom_BSplineCurve); 
472
473       if(VF.IsSame(VL) && isBSpline) {
474         //closed edge
475         f = C->FirstParameter();
476         l = C->LastParameter();
477         gp_Pnt aPf = C->Value(f);
478         gp_Pnt aPl = C->Value(l);
479         if(aPf.Distance(aPl) > Precision::Confusion()) {
480             throw Standard_ConstructionError("FuseEdges : Curve must be closed");
481         }
482         gp_Pnt PF = BRep_Tool::Pnt(VF);
483         if(PF.Distance(aPf) > Precision::Confusion()) {
484           MakeClosedCurve(C, PF, f, l);
485         }
486         //
487         ME.Init(C, VF, VL, f, l);
488         if (!ME.IsDone()) {
489           throw Standard_ConstructionError("FuseEdges : MakeEdge failed for closed curve");
490         }
491       }
492       else {
493         ME.Init(C,VF,VL);
494       }
495 //      BRepLib_MakeEdge ME(C,VF,VL);
496
497       if (!ME.IsDone()) {
498         // the MakeEdge has fails, one reason could be that the new Vertices are outside
499         // the curve which is not infinite and limited to old vertices
500         // we try to use ExtendCurveToPoint, then rebuild the NewEdge
501
502         Handle(Geom_BoundedCurve) ExtC = Handle(Geom_BoundedCurve)::DownCast(C->Copy());
503         if (!ExtC.IsNull()) {
504           gp_Pnt PF = BRep_Tool::Pnt(VF);
505           gp_Pnt PL = BRep_Tool::Pnt(VL);
506           GeomLib::ExtendCurveToPoint(ExtC,PF,1,0);
507           GeomLib::ExtendCurveToPoint(ExtC,PL,1,1); 
508
509           ME.Init(ExtC,VF,VL);
510           if (!ME.IsDone()) 
511             throw Standard_ConstructionError("FuseEdges : Fusion failed");
512         }
513         else
514           throw Standard_ConstructionError("FuseEdges : Fusion failed");
515       }
516
517       NewEdge = ME.Edge();
518
519       if (UpdatePCurve(OldEdge,NewEdge,LmapEdg))
520         myMapEdg.Bind(iLst,NewEdge);
521     }
522
523     myResultEdgesDone = Standard_True;
524
525   }
526 }
527
528 //=======================================================================
529 //function : Perform
530 //purpose  : 
531 //=======================================================================
532
533 void BRepLib_FuseEdges::Perform()
534 {
535   if (!myResultEdgesDone) {
536     BuildListResultEdges();
537   }
538
539   // if we have fused edges
540   if (myMapEdg.Extent() > 0) {
541     TopTools_DataMapIteratorOfDataMapOfIntegerListOfShape itLstEdg;
542     TopTools_ListOfShape EmptyList,EdgeToSubs;
543     BRepTools_Substitution Bsub;
544
545     for (itLstEdg.Initialize(myMapLstEdg); itLstEdg.More(); itLstEdg.Next()) {
546       const Standard_Integer& iLst = itLstEdg.Key();
547       if (!myMapEdg.IsBound(iLst))
548         continue;
549       const TopTools_ListOfShape& LmapEdg = myMapLstEdg.Find(iLst);
550       TopTools_ListIteratorOfListOfShape itEdg; 
551
552       EdgeToSubs.Clear();
553       TopoDS_Edge OldEdge = TopoDS::Edge(LmapEdg.First());
554
555       EdgeToSubs.Append(myMapEdg(iLst));
556       Bsub.Substitute(OldEdge,EdgeToSubs);
557
558       itEdg.Initialize(LmapEdg);
559
560       // the other edges of the list will be removed
561       while (itEdg.More() ) {
562         if (!OldEdge.IsSame(TopoDS::Edge(itEdg.Value()))) {
563           Bsub.Substitute(itEdg.Value(),EmptyList);
564         }
565         itEdg.Next();
566       }      
567     }
568
569     // perform the effective substitution
570     Bsub.Build(myShape);
571
572     // before copying the resulting shape, map the modified faces into myMapFaces
573     TopExp_Explorer exp(myShape,TopAbs_FACE);
574     
575     for (; exp.More(); exp.Next()) {
576       const TopoDS_Shape& facecur = exp.Current();
577       if (Bsub.IsCopied(facecur)) {
578         myMapFaces.Bind(facecur,(Bsub.Copy(facecur)).First());
579       }
580     }
581     
582     if (Bsub.IsCopied(myShape)) {
583       myShape=(Bsub.Copy(myShape)).First();
584     }
585
586   }
587
588
589   myShapeDone = Standard_True;
590 }
591
592
593
594 //=======================================================================
595 //function : BuildListConnexEdge
596 //purpose  : giving one edge, build the list of connex edges which have
597 // vertices that have only two connex edges. All the edges that are addes
598 // to the list must be added also to the mapUniq, in order for the caller
599 // to not treat again theses edges.
600 // This list is always oriented in the "Forward" direction.
601 //=======================================================================
602
603 void BRepLib_FuseEdges::BuildListConnexEdge(const TopoDS_Shape& theEdge, 
604                                                    TopTools_MapOfShape& theMapUniq, 
605                                                    TopTools_ListOfShape& theLstEdg)
606 {
607
608   TopoDS_Vertex VF,VL;
609
610
611   VL = TopExp::LastVertex(TopoDS::Edge(theEdge),Standard_True);
612   TopoDS_Shape edgeconnex;
613   TopoDS_Shape edgecur = theEdge;
614   theLstEdg.Clear();
615   theLstEdg.Append(edgecur);
616   theMapUniq.Add(edgecur);
617   TopAbs_Orientation ori2;
618
619   // we first build the list of edges connex to edgecur by looking from the last Vertex VL
620   while (NextConnexEdge(VL,edgecur,edgeconnex)) {
621     if (theMapUniq.Contains(edgeconnex)) {
622       break;
623     }
624     theLstEdg.Append(edgeconnex);
625     edgecur = edgeconnex;
626     // here take care about internal or external edges. It is non-sense to build
627     // the connex list with such edges.
628     ori2 = edgecur.Orientation();
629     if (ori2 == TopAbs_EXTERNAL || ori2 == TopAbs_INTERNAL) {
630       break;
631     }
632     VL = TopExp::LastVertex(TopoDS::Edge(edgecur),Standard_True);
633     theMapUniq.Add(edgecur);
634   }
635
636   edgecur = theEdge;
637   VF = TopExp::FirstVertex(TopoDS::Edge(theEdge),Standard_True);
638
639   // then we build the list of edges connex to edgecur by looking from the first Vertex VF
640   while (NextConnexEdge(VF,edgecur,edgeconnex)) {
641     if (theMapUniq.Contains(edgeconnex)) {
642       break;
643     }
644     theLstEdg.Prepend(edgeconnex);
645     edgecur = edgeconnex;
646     // here take care about internal or external edges. It is non-sense to build
647     // the connex list with such edges.
648     ori2 = edgecur.Orientation();
649     if (ori2 == TopAbs_EXTERNAL || ori2 == TopAbs_INTERNAL) {
650       break;
651     }
652     VF = TopExp::FirstVertex(TopoDS::Edge(edgecur),Standard_True);
653     theMapUniq.Add(edgecur);
654   }
655
656 }
657
658
659 //=======================================================================
660 //function : NextConnexEdge
661 //purpose  : Look for an edge connex to theEdge at theVertex.
662 // the connex edge must satisfies the following criteria :
663 //   * theVertex must have exactly 2 connex edges.
664 //   * the 2 connex edges must have exactly the 2 same connex faces 
665 //   * the 2 connex edges must lie on the same support.
666 //=======================================================================
667
668 Standard_Boolean BRepLib_FuseEdges::NextConnexEdge(const TopoDS_Vertex& theVertex, 
669                                                           const TopoDS_Shape& theEdge,          
670                                                           TopoDS_Shape& theEdgeConnex) const
671 {
672
673   const TopTools_ListOfShape& LmapEdg = myMapVerLstEdg.FindFromKey(theVertex);
674   Standard_Boolean HasConnex = Standard_True;
675   TopTools_ListIteratorOfListOfShape itEdg,itFac1,itFac2;
676
677   // 1st condition 
678   if (LmapEdg.Extent() == 2) {
679     itEdg.Initialize(LmapEdg);
680     theEdgeConnex = itEdg.Value();
681     if (theEdge.IsSame(theEdgeConnex) ) {
682       itEdg.Next();
683       theEdgeConnex = itEdg.Value();
684     }
685
686     if (myAvoidEdg.Contains(theEdgeConnex))
687       HasConnex = Standard_False;  // edge is not allowed to be fused
688
689     // 2nd condition
690     if (HasConnex) {
691       const TopTools_ListOfShape& LmapFac1 = myMapEdgLstFac.FindFromKey(theEdge);
692       const TopTools_ListOfShape& LmapFac2 = myMapEdgLstFac.FindFromKey(theEdgeConnex);
693       
694       if (LmapFac1.Extent() ==  LmapFac2.Extent() && LmapFac1.Extent() < 3) {
695         itFac1.Initialize(LmapFac1); 
696
697         // for each face in LmapFac1 we look in LmapFac2 if it exists
698         while (itFac1.More() && HasConnex) {
699           const TopoDS_Shape& face1 = itFac1.Value();
700           for (itFac2.Initialize(LmapFac2); itFac2.More(); itFac2.Next()) {
701             const TopoDS_Shape& face2 = itFac2.Value();
702             HasConnex = Standard_False;
703             if (face1.IsSame(face2)) {
704               HasConnex = Standard_True;
705               break;
706             }
707           }
708           itFac1.Next();
709         }
710         
711         // 3rd condition : same suport
712         if (HasConnex) {
713           HasConnex = SameSupport(TopoDS::Edge(theEdge),TopoDS::Edge(theEdgeConnex));
714         }
715       }
716       else
717         HasConnex = Standard_False;
718     }
719   }
720   else
721     HasConnex = Standard_False;
722
723   return HasConnex;
724 }
725
726
727
728 //=======================================================================
729 //function : SameSupport
730 //purpose  : Edges SameSupport ou pas
731 //=======================================================================
732
733 Standard_Boolean BRepLib_FuseEdges::SameSupport(const TopoDS_Edge& E1,
734                                                        const TopoDS_Edge& E2) const
735 {
736
737   if (E1.IsNull() || E2.IsNull()) {
738     return Standard_False;
739   }
740
741
742   Handle(Geom_Curve) C1,C2;
743   TopLoc_Location loc;
744   Standard_Real f1,l1,f2,l2;
745   Handle(Standard_Type) typC1,typC2;
746   
747   C1 = BRep_Tool::Curve(E1,loc,f1,l1);
748   //modified by NIZNHY-PKV Mon Nov 15 16:24:10 1999
749   //degenerated edges has no 3D curve
750   if(C1.IsNull()) return Standard_False;
751
752   if (!loc.IsIdentity()) {
753     Handle(Geom_Geometry) GG1 = C1->Transformed(loc.Transformation());
754     C1 = Handle(Geom_Curve)::DownCast (GG1);
755   }
756   C2 = BRep_Tool::Curve(E2,loc,f2,l2);
757   //modified by NIZNHY-PKV Mon Nov 15 16:24:38 1999
758   //degenerated edges has no 3D curve
759   if(C2.IsNull()) return Standard_False;
760
761   if (!loc.IsIdentity()) {
762     Handle(Geom_Geometry) GG2 = C2->Transformed(loc.Transformation());
763     C2 = Handle(Geom_Curve)::DownCast (GG2);
764   }
765   
766   typC1 = C1->DynamicType();
767   typC2 = C2->DynamicType();
768   
769   if (typC1 == STANDARD_TYPE(Geom_TrimmedCurve)) {
770     C1 =  Handle(Geom_TrimmedCurve)::DownCast (C1)->BasisCurve();
771     typC1 = C1->DynamicType();
772   }
773   
774   if (typC2 == STANDARD_TYPE(Geom_TrimmedCurve)) {
775     C2 =  Handle(Geom_TrimmedCurve)::DownCast (C2)->BasisCurve();
776     typC2 = C2->DynamicType();
777   }
778   
779   if (typC1 != typC2) {
780     return Standard_False;
781   }
782   
783   if (typC1 != STANDARD_TYPE(Geom_Line) &&
784       typC1 != STANDARD_TYPE(Geom_Circle) &&
785       typC1 != STANDARD_TYPE(Geom_Ellipse) &&
786       typC1 != STANDARD_TYPE(Geom_BSplineCurve) && 
787       typC1 != STANDARD_TYPE(Geom_BezierCurve)) {
788     return Standard_False;
789   }
790
791   // On a presomption de confusion
792   const Standard_Real tollin = Precision::Confusion();
793   const Standard_Real tolang = Precision::Angular();
794   if (typC1 == STANDARD_TYPE(Geom_Line)) {
795     gp_Lin li1( Handle(Geom_Line)::DownCast (C1)->Lin());
796     gp_Lin li2( Handle(Geom_Line)::DownCast (C2)->Lin());
797     gp_Dir dir1(li1.Direction());
798     gp_Dir dir2(li2.Direction());
799
800     if ( dir1.IsParallel(dir2,tolang) ) {
801       // on verifie que l'on n'a pas de cas degenere. Par exemple E1 et E2 connexes
802       // mais bouclant l'un sur l'autre (cas tres rare)
803       gp_Pnt pf1 = BRep_Tool::Pnt(TopExp::FirstVertex(E1,Standard_True));
804       gp_Pnt pl1 = BRep_Tool::Pnt(TopExp::LastVertex(E1,Standard_True));
805       gp_Pnt pf2 = BRep_Tool::Pnt(TopExp::FirstVertex(E2,Standard_True));
806       gp_Pnt pl2 = BRep_Tool::Pnt(TopExp::LastVertex(E2,Standard_True));
807       if ( pl1.Distance(pf2) < tollin && pl2.Distance(pf1) < tollin)
808         return Standard_False;
809       else
810         return Standard_True;
811     }
812     return Standard_False;
813   } 
814   else if (typC1 == STANDARD_TYPE(Geom_Circle)) {
815     gp_Circ ci1 = Handle(Geom_Circle)::DownCast (C1)->Circ();
816     gp_Circ ci2 = Handle(Geom_Circle)::DownCast (C2)->Circ();
817     if (Abs(ci1.Radius()-ci2.Radius()) <= tollin &&
818         ci1.Location().SquareDistance(ci2.Location()) <= tollin*tollin &&
819         ci1.Axis().IsParallel(ci2.Axis(),tolang) ) {
820       // Point debut, calage dans periode, et detection meme sens
821       return Standard_True;
822     }
823     return Standard_False;
824   }
825   else if (typC1 == STANDARD_TYPE(Geom_Ellipse)) {
826     gp_Elips ci1 = Handle(Geom_Ellipse)::DownCast (C1)->Elips();
827     gp_Elips ci2 = Handle(Geom_Ellipse)::DownCast (C2)->Elips();
828     
829     if (Abs(ci1.MajorRadius()-ci2.MajorRadius()) <= tollin &&
830         Abs(ci1.MinorRadius()-ci2.MinorRadius()) <= tollin &&
831         ci1.Location().SquareDistance(ci2.Location()) <= tollin*tollin &&
832         ci1.Axis().IsParallel(ci2.Axis(),tolang) ) {
833       // Point debut, calage dans periode, et detection meme sens
834       return Standard_True;
835     }
836     return Standard_False;
837   }
838   else if (typC1 == STANDARD_TYPE(Geom_BSplineCurve)) {
839
840     if(myConcatBSpl) {
841       //Check G1 continuity 
842       gp_Pnt aPf1, aPl1, aPf2, aPl2;
843       gp_Vec aDf1, aDl1, aDf2, aDl2;
844
845       C1->D1(f1, aPf1, aDf1);
846       C1->D1(l1, aPl1, aDl1);
847
848       C2->D1(f2, aPf2, aDf2);
849       C2->D1(l2, aPl2, aDl2);
850
851       if(aPl1.Distance(aPf2) <= tollin && aDl1.IsParallel(aDf2, tolang)) return Standard_True;
852       if(aPl2.Distance(aPf1) <= tollin && aDl2.IsParallel(aDf1, tolang)) return Standard_True;
853       if(aPf1.Distance(aPf2) <= tollin && aDf1.IsParallel(aDf2, tolang)) return Standard_True;
854       if(aPl1.Distance(aPl2) <= tollin && aDl1.IsParallel(aDl2, tolang)) return Standard_True;
855
856     }
857     // we must ensure that before fuse two bsplines, the end of one curve does not
858     // corresponds to the beginning of the second.
859     // we could add a special treatment for periodic bspline. This is not done for the moment.
860     if (Abs(f2-l1) > tollin && Abs(f1-l2) > tollin ) {
861       return Standard_False;
862     }
863
864     Handle(Geom_BSplineCurve) B1 = Handle(Geom_BSplineCurve)::DownCast (C1);
865     Handle(Geom_BSplineCurve) B2 = Handle(Geom_BSplineCurve)::DownCast (C2);
866    
867     Standard_Integer nbpoles = B1->NbPoles();
868     if (nbpoles != B2->NbPoles()) {
869       return Standard_False;
870     }
871    
872     Standard_Integer nbknots = B1->NbKnots();
873     if (nbknots != B2->NbKnots()) {
874       return Standard_False;
875     }
876    
877     TColgp_Array1OfPnt P1(1, nbpoles), P2(1, nbpoles);
878     B1->Poles(P1);
879     B2->Poles(P2);
880    
881     Standard_Real tol3d = BRep_Tool::Tolerance(E1);
882     for (Standard_Integer p = 1; p <= nbpoles; p++) {
883       if ( (P1(p)).Distance(P2(p)) > tol3d) {
884         return Standard_False;
885       }
886     }
887    
888     TColStd_Array1OfReal K1(1, nbknots), K2(1, nbknots);
889     B1->Knots(K1);
890     B2->Knots(K2);
891    
892     TColStd_Array1OfInteger M1(1, nbknots), M2(1, nbknots);
893     B1->Multiplicities(M1);
894     B2->Multiplicities(M2);
895    
896     for (Standard_Integer k = 1; k <= nbknots; k++) {
897       if ((K1(k)-K2(k)) > tollin) {
898         return Standard_False;
899       }
900       if (Abs(M1(k)-M2(k)) > tollin) {
901         return Standard_False;
902       }
903     }
904    
905     if (!B1->IsRational()) {
906       if (B2->IsRational()) {
907         return Standard_False;
908       }
909     }
910     else {
911       if (!B2->IsRational()) {
912         return Standard_False;
913       }
914     }
915     
916     if (B1->IsRational()) {
917       TColStd_Array1OfReal W1(1, nbpoles), W2(1, nbpoles);
918       B1->Weights(W1);
919       B2->Weights(W2);
920    
921       for (Standard_Integer w = 1; w <= nbpoles; w++) {
922         if (Abs(W1(w)-W2(w)) > tollin) {
923           return Standard_False;
924         }
925       }
926     }
927     return Standard_True;
928   }
929   else if (typC1 == STANDARD_TYPE(Geom_BezierCurve)) {
930
931     // we must ensure that before fuse two bezier, the end of one curve does not
932     // corresponds to the beginning of the second.
933     if (Abs(f2-l1) > tollin && Abs(f1-l2) > tollin ) {
934       return Standard_False;
935     }
936
937     Handle(Geom_BezierCurve) B1 = Handle(Geom_BezierCurve)::DownCast (C1);
938     Handle(Geom_BezierCurve) B2 = Handle(Geom_BezierCurve)::DownCast (C2);
939     
940     Standard_Integer nbpoles = B1->NbPoles();
941     if (nbpoles != B2->NbPoles()) {
942       return Standard_False;
943     }
944     
945     TColgp_Array1OfPnt P1(1, nbpoles), P2(1, nbpoles);
946     B1->Poles(P1);
947     B2->Poles(P2);
948     
949     for (Standard_Integer p = 1; p <= nbpoles; p++) {
950       if ( (P1(p)).Distance(P2(p)) > tollin) {
951         return Standard_False;
952       }
953     }
954     
955     if (!B1->IsRational()) {
956       if (B2->IsRational()) {
957         return Standard_False;
958       }
959     }
960     else {
961       if (!B2->IsRational()) {
962         return Standard_False;
963       }
964     }
965     
966     if (B1->IsRational()) {
967       TColStd_Array1OfReal W1(1, nbpoles), W2(1, nbpoles);
968       B1->Weights(W1);
969       B2->Weights(W2);
970       
971       for (Standard_Integer w = 1; w <= nbpoles; w++) {
972         if (Abs(W1(w)-W2(w)) > tollin) {
973           return Standard_False;
974         }
975       }
976     }
977     return Standard_True;
978   }
979   return Standard_False;
980 }
981
982 //=======================================================================
983 //function : UpdatePCurve
984 //purpose  : 
985 //=======================================================================
986
987 Standard_Boolean BRepLib_FuseEdges::UpdatePCurve(const TopoDS_Edge& theOldEdge,
988                                             TopoDS_Edge& theNewEdge,
989                                             const TopTools_ListOfShape& theLstEdg) const
990 {
991
992
993 // get the pcurve of edge to substitute (theOldEdge) 
994 // using CurveOnSurface with Index syntax, so we can update the pcurve
995 // on all the faces
996   BRep_Builder B;
997   Handle(Geom2d_Curve) Curv2d;
998   Handle(Geom_Surface) Surf;
999   TopLoc_Location loc,locbid;
1000   Standard_Real ef,el,cf,cl;
1001   Standard_Integer iedg = 1;
1002
1003   // take care that we want only Pcurve that maps on the surface where the 3D edges lies.
1004   const TopTools_ListOfShape& LmapFac = myMapEdgLstFac.FindFromKey(theOldEdge);
1005
1006
1007   BRep_Tool::CurveOnSurface(theOldEdge,Curv2d,Surf,loc,cf,cl,iedg);
1008
1009   Standard_Boolean pcurveRebuilt = Standard_False;
1010   
1011   while (!Curv2d.IsNull()) {
1012     
1013     // we look for a face that contains the same surface as the one that cames
1014     // from CurveOnSurface
1015     Standard_Boolean SameSurf = Standard_False;
1016     TopTools_ListIteratorOfListOfShape itFac;
1017
1018     for (itFac.Initialize(LmapFac); itFac.More(); itFac.Next() ) {
1019       const TopoDS_Shape& face = itFac.Value();
1020       Handle (Geom_Surface) S = BRep_Tool::Surface(TopoDS::Face(face),locbid);
1021       if (S == Surf) {
1022         SameSurf = Standard_True;
1023         break;
1024       }
1025     }
1026
1027     if (SameSurf) {
1028
1029       BRep_Tool::Range(theNewEdge,ef,el);
1030
1031         //modified by NIZNHY-PKV Mon Nov 15 14:59:48 1999 _from
1032       TopoDS_Edge aFEdge = theOldEdge;
1033       aFEdge.Orientation(TopAbs_FORWARD);
1034
1035       // take care if the edge is on the closing curve of a closed surface. In that case
1036       // we get the second pcurve by reversing the edge and calling again CurveOnSurface method
1037       
1038       BRep_Tool::CurveOnSurface(aFEdge,Curv2d,Surf,loc,cf,cl,iedg);
1039       if (BRep_Tool::IsClosed(theOldEdge,Surf,loc))  {
1040         aFEdge.Reverse();
1041         TopoDS_Face aFFace = TopoDS::Face(itFac.Value());
1042         aFFace.Orientation(TopAbs_FORWARD);
1043         Handle(Geom2d_Curve) Curv2dR = BRep_Tool::CurveOnSurface(aFEdge,
1044                                                                  aFFace,cf,cl);
1045         if (Curv2d->DynamicType() == STANDARD_TYPE(Geom2d_TrimmedCurve))
1046           Curv2d = Handle(Geom2d_TrimmedCurve)::DownCast (Curv2d)->BasisCurve();
1047         if (Curv2dR->DynamicType() == STANDARD_TYPE(Geom2d_TrimmedCurve))
1048           Curv2dR = Handle(Geom2d_TrimmedCurve)::DownCast (Curv2dR)->BasisCurve();
1049
1050         B.UpdateEdge (theNewEdge,Curv2d,Curv2dR,Surf,loc,BRep_Tool::Tolerance(theNewEdge));
1051       }
1052       else {
1053         // update the new edge 
1054         if (Curv2d->DynamicType() == STANDARD_TYPE(Geom2d_TrimmedCurve))
1055           Curv2d = Handle(Geom2d_TrimmedCurve)::DownCast (Curv2d)->BasisCurve();
1056         Standard_Real f, l;
1057         f = Curv2d->FirstParameter();
1058         l = Curv2d->LastParameter();
1059         if (l-f + 2.* Epsilon(l-f) < el-ef)
1060           {
1061             Handle(Geom2d_BoundedCurve) bcurve = Handle(Geom2d_BoundedCurve)::DownCast(Curv2d);
1062             if (bcurve.IsNull())
1063               bcurve = new Geom2d_TrimmedCurve( Curv2d, cf, cl );
1064             Geom2dConvert_CompCurveToBSplineCurve Concat( bcurve );
1065             TopTools_ListIteratorOfListOfShape iter( theLstEdg );
1066             iter.Next();
1067             for (; iter.More(); iter.Next())
1068               {
1069                 TopoDS_Edge& E = TopoDS::Edge(iter.Value());
1070                 Standard_Real first, last;
1071                 Handle(Geom2d_Curve) C = BRep_Tool::CurveOnSurface( E, Surf, loc, first, last );
1072                 Handle(Geom2d_BoundedCurve) BC = Handle(Geom2d_BoundedCurve)::DownCast(C);
1073                 if (BC.IsNull())
1074                   BC = new Geom2d_TrimmedCurve( C, first, last );
1075                 if (!Concat.Add( BC, Precision::PConfusion() ))
1076                   // cannot merge pcurves
1077                   return Standard_False;
1078               }
1079             Curv2d = Concat.BSplineCurve();
1080
1081             // check that new curve 2d is same range 
1082             Standard_Real first = Curv2d->FirstParameter();
1083             Standard_Real last = Curv2d->LastParameter();
1084             if (Abs (first - ef) > Precision::PConfusion() ||
1085                 Abs (last - el) > Precision::PConfusion())
1086             {
1087               Handle(Geom2d_BSplineCurve) bc = Handle(Geom2d_BSplineCurve)::DownCast(Curv2d);
1088               TColStd_Array1OfReal Knots (1, bc->NbKnots());
1089               bc->Knots(Knots);
1090               BSplCLib::Reparametrize (ef, el, Knots);
1091               bc->SetKnots(Knots);
1092             }
1093             pcurveRebuilt = Standard_True;
1094           }
1095
1096         B.UpdateEdge (theNewEdge,Curv2d,Surf,loc,BRep_Tool::Tolerance(theNewEdge));
1097       }
1098
1099       // the old pcurve range is cf,cl. The new 3d edge range is ef,el. if we want
1100       // the pcurve to be samerange we must adapt the parameter of the edge. In general
1101       // cases cf=ef and cl=el expect for periodic curve if the new edge is going over
1102       // the value 0.
1103       if(!pcurveRebuilt) {
1104         if (theOldEdge.Orientation()== TopAbs_REVERSED) {
1105           B.Range(theNewEdge,cl-el+ef,cl);
1106         }
1107         else {
1108           B.Range(theNewEdge,cf,cf+el-ef);
1109         }
1110       }
1111      } 
1112
1113     // get next pcurve
1114     iedg++;
1115     BRep_Tool::CurveOnSurface(theOldEdge,Curv2d,Surf,loc,cf,cl,iedg);
1116   }
1117
1118   if (pcurveRebuilt)
1119   {
1120     // force same parameter
1121     B.SameParameter (theNewEdge, Standard_False);
1122     BRepLib::SameParameter (theNewEdge, BRep_Tool::Tolerance(theNewEdge));
1123   }
1124
1125   return Standard_True;
1126 }
1127
1128