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