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