0026431: Can't cut a sphere from a cylinder
[occt.git] / src / HLRTopoBRep / HLRTopoBRep_DSFiller.cxx
1 // Created on: 1993-08-10
2 // Created by: Christophe MARION
3 // Copyright (c) 1993-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
18 #include <AppDef_BSplineCompute.hxx>
19 #include <AppDef_MultiLine.hxx>
20 #include <AppDef_MultiPointConstraint.hxx>
21 #include <AppParCurves_MultiBSpCurve.hxx>
22 #include <BRep_Builder.hxx>
23 #include <BRep_CurveRepresentation.hxx>
24 #include <BRep_ListIteratorOfListOfCurveRepresentation.hxx>
25 #include <BRep_TEdge.hxx>
26 #include <BRep_Tool.hxx>
27 #include <BRepAdaptor_Curve.hxx>
28 #include <BRepAdaptor_Curve2d.hxx>
29 #include <BRepAdaptor_HCurve2d.hxx>
30 #include <BRepApprox_Approx.hxx>
31 #include <BRepApprox_ApproxLine.hxx>
32 #include <BRepExtrema_ExtPC.hxx>
33 #include <BRepTopAdaptor_HVertex.hxx>
34 #include <BRepTopAdaptor_Tool.hxx>
35 #include <BRepTopAdaptor_TopolTool.hxx>
36 #include <Contap_Contour.hxx>
37 #include <Contap_Line.hxx>
38 #include <Contap_Point.hxx>
39 #include <Extrema_LocateExtPC.hxx>
40 #include <Geom2d_BSplineCurve.hxx>
41 #include <Geom2d_Curve.hxx>
42 #include <Geom_BSplineCurve.hxx>
43 #include <Geom_Circle.hxx>
44 #include <Geom_Line.hxx>
45 #include <Geom_Surface.hxx>
46 #include <GeomProjLib.hxx>
47 #include <HLRTopoBRep_Data.hxx>
48 #include <HLRTopoBRep_DSFiller.hxx>
49 #include <HLRTopoBRep_FaceIsoLiner.hxx>
50 #include <math_Vector.hxx>
51 #include <Precision.hxx>
52 #include <Standard_ProgramError.hxx>
53 #include <TColgp_Array1OfPnt.hxx>
54 #include <TColgp_Array1OfPnt2d.hxx>
55 #include <TColStd_Array1OfInteger.hxx>
56 #include <TColStd_Array1OfReal.hxx>
57 #include <TopExp.hxx>
58 #include <TopExp_Explorer.hxx>
59 #include <TopoDS.hxx>
60 #include <TopoDS_Edge.hxx>
61 #include <TopoDS_Face.hxx>
62 #include <TopoDS_Shape.hxx>
63 #include <TopoDS_Vertex.hxx>
64 #include <TopTools_ListIteratorOfListOfShape.hxx>
65
66 #define INTERPOLATE 0
67 #define BRISE       0
68 #define APPROX      1
69
70
71 static Standard_Boolean IntLineRisesFromRegularity(const TopoDS_Edge& anIntLine,
72                                                    const TopoDS_Edge& anEdge,
73                                                    const TopoDS_Face&,
74                                                    const TopTools_ListOfShape& aList)
75 {
76   TopoDS_Vertex Ver [2];
77   TopExp::Vertices(anIntLine, Ver[0], Ver[1]);
78
79   //find min param and max param
80   Standard_Real MinPar = RealLast(), MaxPar = RealFirst();
81   TopTools_ListIteratorOfListOfShape itl(aList);
82   for (; itl.More(); itl.Next())
83   {
84     const TopoDS_Edge& anOutLine = TopoDS::Edge(itl.Value());
85     Standard_Real aFirst, aLast;
86     BRep_Tool::Range(anOutLine, aFirst, aLast);
87     if (aFirst < MinPar)
88       MinPar = aFirst;
89     if (aLast > MaxPar)
90       MaxPar = aLast;
91   }
92   
93   Standard_Real theTol = BRep_Tool::Tolerance(anEdge);
94   Standard_Real ParamTol = Precision::Confusion();
95   
96   Standard_Integer i, j;
97   for (i = 0; i < 2; i++)
98   {
99     BRepExtrema_ExtPC anExtPC(Ver[i], anEdge);
100     if (!anExtPC.IsDone())
101       continue;
102     Standard_Integer NbExt = anExtPC.NbExt();
103     if (NbExt == 0)
104       continue;
105     Standard_Integer jmin = 1;
106     for (j = 2; j <= NbExt; j++)
107       if (anExtPC.SquareDistance(j) < anExtPC.SquareDistance(jmin))
108         jmin = j;
109     Standard_Real aDist = anExtPC.SquareDistance(jmin);
110     aDist = Sqrt(aDist);
111     if (aDist > theTol)
112       continue;
113
114     Standard_Real theParam = anExtPC.Parameter(jmin);
115     if (theParam > MinPar + ParamTol &&
116         theParam < MaxPar - ParamTol)
117       return Standard_True;
118   }
119
120   return Standard_False;
121 }
122
123
124 //=======================================================================
125 //function : Insert
126 //purpose  : explore the faces and insert them
127 //=======================================================================
128
129 void  HLRTopoBRep_DSFiller::Insert (const TopoDS_Shape& S,
130                                     Contap_Contour& FO,
131                                     HLRTopoBRep_Data& DS,
132                                     BRepTopAdaptor_MapOfShapeTool& MST,
133                                     const Standard_Integer nbIso)
134 {
135   TopTools_MapOfShape ShapeMap;
136   TopExp_Explorer ex(S,TopAbs_FACE);
137   DS.Clear();
138   Standard_Boolean withPCurve = Standard_True; // instead of nbIso != 0;
139   Standard_Integer f = 0;
140   
141   while (ex.More()) {
142     if (ShapeMap.Add(ex.Current())) {
143       f++;
144       TopoDS_Face S1 = TopoDS::Face(ex.Current());
145       S1.Orientation(TopAbs_FORWARD);
146       Handle(BRepTopAdaptor_TopolTool) Domain; 
147       Handle(Adaptor3d_HSurface)         Surface;
148       if(MST.IsBound(S1)) {  
149         BRepTopAdaptor_Tool& BRT = MST.ChangeFind(S1);
150         Domain  = BRT.GetTopolTool();
151         Surface = BRT.GetSurface();
152       }
153       else { 
154         BRepTopAdaptor_Tool BRT(S1,Precision::PConfusion());
155         MST.Bind(S1,BRT);
156         Domain  = BRT.GetTopolTool();
157         Surface = BRT.GetSurface();
158       }
159       FO.Perform(Surface, Domain);
160       if (FO.IsDone()) {
161         if (!FO.IsEmpty())
162           InsertFace(f,S1,FO,DS,withPCurve);
163       }
164       if (nbIso != 0) HLRTopoBRep_FaceIsoLiner::Perform(f,S1,DS,nbIso);
165     }
166     ex.Next();
167   }
168   ProcessEdges(DS);
169 }
170
171 //=======================================================================
172 //function : InsertFace
173 //purpose  : private, insert the outlines of a face
174 //=======================================================================
175
176 void  HLRTopoBRep_DSFiller::InsertFace (const Standard_Integer /*FI*/,
177                                         const TopoDS_Face& F,
178                                         Contap_Contour& FO,
179                                         HLRTopoBRep_Data& DS,
180                                         const Standard_Boolean withPCurve)
181 {
182   // Insert the intersections of FO in DS
183
184   const Standard_Real tol = BRep_Tool::Tolerance(F);
185   TopTools_ListOfShape& IntL = DS.AddIntL(F);
186   TopTools_ListOfShape& OutL = DS.AddOutL(F);
187
188   TopoDS_Vertex VF,VL;
189   /*
190   TopTools_MapOfShape VM;
191   TopExp_Explorer ex(F,TopAbs_EDGE);
192   while (ex.More()) {
193     const TopoDS_Edge& E = TopoDS::Edge(ex.Current());
194     if (BRep_Tool::IsClosed(E,F)) {
195       TopExp::Vertices(E,VF,VL);
196       VM.Add(VF);
197       VM.Add(VL);
198     }
199     ex.Next();
200   }
201   */
202
203   const Standard_Integer NbLines = FO.NbLines();
204   Standard_Integer CurLine;
205   for (CurLine = 1; CurLine <= NbLines; CurLine++)
206   {
207     const Contap_Line& Line = FO.Line(CurLine);
208     const Standard_Integer NbPoints = Line.NbVertex();
209     Standard_Integer CurPoint;
210     if (Line.TypeContour() == Contap_Restriction)
211     {
212       // OutLine on restriction
213       TopoDS_Edge E = (*(BRepAdaptor_Curve2d*)&(Line.Arc()->Curve2d())).Edge();
214       OutL.Append(E);
215       TopExp::Vertices(E,VF,VL);
216       // insert the Internal points.
217
218       for (CurPoint = 1; CurPoint <= NbPoints; CurPoint++) {
219         Contap_Point P = Line.Vertex(CurPoint);
220         if (P.IsInternal()) {
221           if (P.Value().IsEqual(BRep_Tool::Pnt(VF),BRep_Tool::Tolerance(VF))) {
222             if (P.Value().IsEqual(BRep_Tool::Pnt(VL),BRep_Tool::Tolerance(VL))) {
223               InsertVertex(P,tol,E,DS);
224             }
225           }
226         }
227       }
228     }
229     else
230     {
231       for (CurPoint = 1; CurPoint <= NbPoints; CurPoint++) {
232
233         const Contap_Point PF = Line.Vertex(CurPoint);
234         if (PF.IsInternal() && CurPoint != 1)
235           VF = VL;
236         else
237           VF = MakeVertex(PF,tol,DS);
238         const Standard_Real parF = PF.ParameterOnLine();
239
240         if (CurPoint < NbPoints) {
241           const Contap_Point PL = Line.Vertex(CurPoint+1);
242           VL = MakeVertex(PL,tol,DS);
243           const Standard_Real parL = PL.ParameterOnLine();
244
245           if( (parL-parF) > Precision::PConfusion() ) {
246
247             Handle(Geom_Curve) C;
248             Handle(Geom2d_Curve) C2d;
249             Standard_Real first = parF;
250             Standard_Real last  = parL;
251             Standard_Boolean InsuffisantNumberOfPoints=Standard_False;
252
253             switch (Line.TypeContour()) {
254               
255               case Contap_Lin :
256               {
257                 C = new Geom_Line(Line.Line());
258                 if (withPCurve) {
259                   Handle(Geom_Surface) S = BRep_Tool::Surface(F);
260                   Standard_Real Tol = 1e-7;
261                   C2d = GeomProjLib::Curve2d(C,first,last,S,Tol); 
262                 }
263               }
264               break;
265               
266               case Contap_Circle :
267               {
268                 C = new Geom_Circle(Line.Circle());
269                 if (withPCurve) {
270                   TopLoc_Location Loc;
271                   Handle(Geom_Surface) S = BRep_Tool::Surface(F,Loc);
272                   if (!Loc.IsIdentity()) {
273                     S = Handle(Geom_Surface)::DownCast(S->Transformed(Loc.Transformation()));
274                   }
275                   Standard_Real Tol = 1e-7;
276                   C2d = GeomProjLib::Curve2d(C,first,last,S,Tol); 
277                 }
278               }
279               break;
280               
281               case Contap_Walking :
282               {
283                 // copy the points
284                 Standard_Integer ipF = Standard_Integer(parF);
285                 Standard_Integer ipL = Standard_Integer(parL);
286                 
287                 if(ipL-ipF < 1) { 
288                   InsuffisantNumberOfPoints=Standard_True;
289                   //cout<<"\n !! Pb ds HLRTopoBRep_DSFiller.cxx (Contour App Nbp <3)"<<endl;
290                 }
291 /*
292                 else if(ipL-ipF < 6) { 
293                   // compute the tangents
294                   Contap_SurfFunction& SFunc =
295                     FO.SurfaceFunction();
296                   
297                   Standard_Boolean isTg1,isTg2;
298                   gp_Vec tg1,tg2;
299                   gp_Vec2d uv1,uv2;
300                   math_Vector UV(1,2),F(1,1);
301                   
302                   Line.Point(ipF).ParametersOnS2(UV(1),UV(2));
303                   SFunc.Value(UV,F);
304                   isTg1 = SFunc.IsTangent();
305                   if (!isTg1) {
306                     tg1 = SFunc.Direction3d();
307                     if (withPCurve) uv1 = SFunc.Direction2d();
308                   }
309                   
310                   Line.Point(ipL).ParametersOnS2(UV(1),UV(2));
311                   SFunc.Value(UV,F);
312                   isTg2 = SFunc.IsTangent();
313                   if (!isTg2) {
314                     tg2 = SFunc.Direction3d();
315                     if (withPCurve) uv2 = SFunc.Direction2d();
316                   }
317                   // interpolate
318                   Standard_Integer nbp = ipL - ipF + 1;
319                   AppDef_MultiLine MLine(nbp);
320                   Standard_Integer nb2d = 0;
321                   if (withPCurve)  nb2d = 1;
322                   
323                   for (Standard_Integer i = 1; i <= nbp; i++) {
324                     AppDef_MultiPointConstraint MP(1, nb2d);
325                     MP.SetPoint(1,Line.Point(i + ipF - 1).Value());
326                     if (withPCurve) {
327                       Line.Point(i + ipF - 1).ParametersOnS2(UV(1),UV(2));
328                       MP.SetPoint2d(2,gp_Pnt2d(UV(1),UV(2)));
329                     }
330                     
331                     if (i == 1   && !isTg1) {
332                       MP.SetTang  (1,tg1);
333                       if (withPCurve) MP.SetTang2d(2,uv1);
334                     }
335                     if (i == nbp && !isTg2) {
336                       MP.SetTang  (1,tg2);
337                       if (withPCurve) MP.SetTang2d(2,uv2);
338                     }
339                     MLine.SetValue(i,MP);
340                   }
341                   AppDef_BSplineCompute interp;
342                   interp.Interpol(MLine);
343                   AppParCurves_MultiBSpCurve TheCurve = interp.Value();
344                   Standard_Integer Degree = TheCurve.Degree();
345                   TColgp_Array1OfPnt   Poles(1,TheCurve.NbPoles());
346                   TheCurve.Curve(1,Poles);
347                   C   = new Geom_BSplineCurve(Poles, 
348                                               TheCurve.Knots(),
349                                               TheCurve.Multiplicities(),
350                                               Degree);
351                   if (withPCurve) {
352                     TColgp_Array1OfPnt2d Pol2d(1,TheCurve.NbPoles());
353                     TheCurve.Curve(2,Pol2d);
354                     C2d = new Geom2d_BSplineCurve(Pol2d, 
355                                                   TheCurve.Knots(),
356                                                   TheCurve.Multiplicities(),
357                                                   Degree);
358                   }
359                   first = 0;
360                   last = 1;
361                 }
362 */
363                 else if(ipL-ipF < 5) { 
364                   const Standard_Integer nbp = ipL - ipF + 1;
365                   TColStd_Array1OfReal knots(1,nbp);
366                   TColStd_Array1OfInteger mults(1,nbp);
367                   TColgp_Array1OfPnt Points(1,nbp);
368
369                   for(Standard_Integer i=1;i<=nbp;i++) {
370                     knots.SetValue(i,(Standard_Real)i);
371                     mults.SetValue(i,1);
372                     Points.SetValue(i,Line.Point(i+ipF-1).Value());
373                   }
374                   mults(1)=mults(nbp)=2;
375                   C = new Geom_BSplineCurve(Points,knots,mults,1);
376                   
377                   if(withPCurve) { 
378                     TColgp_Array1OfPnt2d Points2d(1,nbp);
379                     for(Standard_Integer i=1;i<=nbp;i++) {
380                       Standard_Real u,v;
381                       Line.Point(i+ipF-1).ParametersOnS2(u,v);
382                       Points2d.SetValue(i,gp_Pnt2d(u,v));
383                     }
384                     C2d = new Geom2d_BSplineCurve(Points2d,knots,mults,1);
385                   }
386                   first = 1;
387                   last = nbp;
388                 }
389                 else { 
390                   const Standard_Integer nbp = ipL - ipF + 1;
391                   TColStd_Array1OfReal knots(1,nbp);
392                   TColStd_Array1OfInteger mults(1,nbp);
393                   TColgp_Array1OfPnt Points(1,nbp);
394
395                   Standard_Real Maxx,Maxy,Maxz,Maxu,Maxv;
396                   Standard_Real Minx,Miny,Minz,Minu,Minv;
397                   Maxx=Maxy=Maxz=Maxu=Maxv=-RealLast();
398                   Minx=Miny=Minz=Minu=Minv=RealLast();
399                   
400                   for(Standard_Integer i=1;i<=nbp;i++) {
401                     knots.SetValue(i,(Standard_Real)i);
402                     mults.SetValue(i,1);
403                     const gp_Pnt& P= Line.Point(i+ipF-1).Value();
404                     if(P.X()<Minx) Minx=P.X();
405                     if(P.Y()<Miny) Miny=P.Y();
406                     if(P.Z()<Minz) Minz=P.Z();
407                     if(P.X()>Maxx) Maxx=P.X();
408                     if(P.Y()>Maxy) Maxy=P.Y();
409                     if(P.Z()>Maxz) Maxz=P.Z();              
410                     Points.SetValue(i,P);
411                   }
412                   mults(1)=mults(nbp)=2;
413                   Handle(Geom_BSplineCurve)   AppC;
414                   Handle(Geom2d_BSplineCurve) AppC2d;
415                   AppC = new Geom_BSplineCurve(Points,knots,mults,1);
416
417                   if(withPCurve) {
418                     TColgp_Array1OfPnt2d Points2d(1,nbp);
419                     for(Standard_Integer i=1;i<=nbp;i++) {
420                       Standard_Real u,v;
421                       Line.Point(i+ipF-1).ParametersOnS2(u,v);
422                       if(u<Minu) Minu=u;
423                       if(v<Minv) Minv=v;
424                       if(u>Maxu) Maxu=u;
425                       if(v>Maxv) Maxv=v;
426                       Points2d.SetValue(i,gp_Pnt2d(u,v));
427                     }
428                     AppC2d = new Geom2d_BSplineCurve(Points2d,knots,mults,1);
429                   }
430                   first = 1;
431                   last = nbp;
432                   
433                   Handle(BRepApprox_ApproxLine) AppLine;
434                   Handle(Geom2d_BSplineCurve) CNull;
435                   AppLine = new BRepApprox_ApproxLine(AppC,AppC2d,CNull);
436                   
437                   Standard_Integer dmin=4,dmax=8,niter=0;
438                   Standard_Boolean tg= Standard_False;
439                   BRepApprox_Approx Approx;
440                   Standard_Real TOL3d,TOL2d,TOL=0.0001;
441
442                   Maxx-=Minx; Maxy-=Miny; Maxz-=Minz;
443                   Maxu-=Minu; Maxv-=Minv;
444                   if(Maxy>Maxx) Maxx=Maxy;
445                   if(Maxz>Maxx) Maxx=Maxy;
446                   if(Maxv>Maxu) Maxu=Maxv;
447
448                   TOL3d=TOL*Maxx; if(TOL3d<1e-12) TOL3d=1e-12; else if(TOL3d>0.1) TOL3d=0.1;
449                   TOL2d=TOL*Maxu; if(TOL2d<1e-12) TOL2d=1e-12; else if(TOL2d>0.1) TOL2d=0.1;
450                   
451                   //-- cout<<"\nHLRTopoBRep_DSFiller : nbp="<<nbp<<"  Tol3d="<<TOL3d<<"   Tol2d="<<TOL2d<<endl;
452
453                   Approx.SetParameters(TOL3d, TOL2d, dmin, dmax, niter, 30, tg);
454                   Approx.Perform(AppLine,Standard_True,Standard_True,Standard_False,1,nbp);
455                   if (!Approx.IsDone()) {
456                     C = AppC;
457                     C2d=AppC2d; 
458                     first = 1;
459                     last = nbp;
460                   }
461                   else { 
462                     const AppParCurves_MultiBSpCurve& AppVal = Approx.Value(1); 
463                     TColgp_Array1OfPnt poles3d(1,AppVal.NbPoles());
464                     AppVal.Curve(1,poles3d);
465                     C = new Geom_BSplineCurve(poles3d,AppVal.Knots(),AppVal.Multiplicities(),AppVal.Degree());
466                     
467                     const AppParCurves_MultiBSpCurve& AppVal2 = Approx.Value(2);
468                     TColgp_Array1OfPnt2d poles2d(1,AppVal2.NbPoles());
469                     AppVal2.Curve(2,poles2d);
470                     C2d = new Geom2d_BSplineCurve(poles2d,AppVal2.Knots(),AppVal2.Multiplicities(),AppVal2.Degree());
471                     first = C2d->FirstParameter();
472                     last  = C2d->LastParameter();
473                   }
474                 }
475               }
476               break;
477               
478               case Contap_Restriction :
479               {
480                 Standard_ProgramError::Raise("HLRTopoBRep_DSFiller::InsertFace : Restriction");
481               }
482               break;
483             }
484             
485             // compute the PCurve
486             // make the edge
487             if (!InsuffisantNumberOfPoints) {
488               TopoDS_Edge E;
489               BRep_Builder B;
490               B.MakeEdge(E,C,tol);
491               VF.Orientation(TopAbs_FORWARD);
492               VL.Orientation(TopAbs_REVERSED);
493               B.Add(E,VF);
494               B.Add(E,VL);
495               B.Range(E,first,last);
496
497               if (!C2d.IsNull()) {
498                 B.UpdateEdge(E,C2d,F,BRep_Tool::Tolerance(F));
499               }
500               
501               // add the edge in the DS
502               if (!E.IsNull())
503                 IntL.Append(E);
504             }
505           }
506         }
507       }
508     }
509   }
510
511   //jgv: correction of internal outlines: remove those that rise from middle of boundary outlines
512   TopTools_ListIteratorOfListOfShape itl(IntL);
513   while (itl.More())
514   {
515     TopoDS_Edge anIntLine = TopoDS::Edge(itl.Value());
516     Standard_Real found = Standard_False;
517     TopExp_Explorer Explo(F, TopAbs_EDGE);
518     for (; Explo.More(); Explo.Next())
519     {
520       TopoDS_Edge anEdge = TopoDS::Edge(Explo.Current());
521       if (!BRep_Tool::HasContinuity(anEdge))
522         continue;
523
524       TopLoc_Location RegLoc;
525       Standard_Real fpar, lpar;
526       Handle(Geom_Curve) RegCurve = BRep_Tool::Curve(anEdge, RegLoc, fpar, lpar);
527       TopTools_ListOfShape thelist;
528       TopTools_ListIteratorOfListOfShape itoutl(OutL);
529       for (; itoutl.More(); itoutl.Next())
530       {
531         TopoDS_Edge anOutLine = TopoDS::Edge(itoutl.Value());
532         TopLoc_Location aLoc;
533         Standard_Real aFirst, aLast;
534         Handle(Geom_Curve) aCurve = BRep_Tool::Curve(anOutLine, aLoc, aFirst, aLast);
535         if (aCurve == RegCurve && aLoc == RegLoc)
536           thelist.Append(anOutLine);
537       }
538
539       if (thelist.IsEmpty())
540         continue;
541
542       if (IntLineRisesFromRegularity(anIntLine, anEdge, F, thelist))
543       {
544         IntL.Remove(itl);
545         found = Standard_True;
546         break;
547       }
548     }
549     
550     if (!found)
551       itl.Next();
552   }
553   ///////////////////////////////////////////////////
554 }
555
556 //=======================================================================
557 //function : MakeVertex
558 //purpose  : private, make a vertex from an intersection point
559 //=======================================================================
560
561 TopoDS_Vertex
562 HLRTopoBRep_DSFiller::MakeVertex (const Contap_Point& P,
563                                   const Standard_Real tol,
564                                   HLRTopoBRep_Data& DS)
565 {
566   BRep_Builder B;
567   TopoDS_Vertex V;
568   if (P.IsVertex()) {
569     V = Handle(BRepTopAdaptor_HVertex)::DownCast(P.Vertex())->Vertex();
570     DS.AddOutV(V);
571   }
572   else {
573     // if on arc, insert in the DS
574     if (P.IsOnArc()) {
575       const TopoDS_Edge& E = 
576         (*(BRepAdaptor_Curve2d*)&((P.Arc())->Curve2d())).Edge();
577       Standard_Real Par = P.ParameterOnArc();
578       const gp_Pnt& P3d = P.Value();
579
580       for (DS.InitVertex(E); DS.MoreVertex(); DS.NextVertex()) {
581         TopoDS_Vertex curV = DS.Vertex();
582         Standard_Real curP = DS.Parameter();
583         const gp_Pnt& PPP=BRep_Tool::Pnt(curV);
584         Standard_Real TTT=BRep_Tool::Tolerance(curV);
585         if (P3d.IsEqual(PPP,TTT)) { 
586           V = curV;
587           break;
588         }
589         else if (Par < curP) {
590           B.MakeVertex(V,P.Value(),tol);
591           DS.InsertBefore(V,Par);
592           break;
593         }
594       }
595       if (!DS.MoreVertex()) {
596         B.MakeVertex(V,P.Value(),tol);
597         DS.Append(V,Par);
598       } 
599       DS.AddOutV(V);
600     }
601     // if internal create a vertex and insert in the DS
602     else {
603       B.MakeVertex(V,P.Value(),tol);
604       if (P.IsInternal())
605         DS.AddIntV(V);
606       else
607         DS.AddOutV(V);
608     }
609   }
610   return V;
611 }
612
613 //=======================================================================
614 //function : InsertVertex
615 //purpose  : private, insert a vertex from an internal intersection point
616 //           on resctriction
617 //=======================================================================
618
619 void
620 HLRTopoBRep_DSFiller::InsertVertex (const Contap_Point& P,
621                                     const Standard_Real tol,
622                                     const TopoDS_Edge& E,
623                                     HLRTopoBRep_Data& DS)
624 {
625   BRep_Builder B;
626   TopoDS_Vertex V;
627
628   if (P.IsVertex()) {
629     V = Handle(BRepTopAdaptor_HVertex)::DownCast(P.Vertex())->Vertex();
630   }
631   else {
632     Standard_Real Par = P.ParameterOnLine();
633     
634     for (DS.InitVertex(E); DS.MoreVertex(); DS.NextVertex()) {
635       TopoDS_Vertex curV = DS.Vertex();
636       Standard_Real curP = DS.Parameter();
637       if (P.Value().IsEqual(BRep_Tool::Pnt(curV),
638                             BRep_Tool::Tolerance(curV))) {
639         V = curV;
640         break;
641       }
642       else if (Par < curP) {
643         B.MakeVertex(V,P.Value(),tol);
644         DS.InsertBefore(V,Par);
645         break;
646       }
647     }
648     if (!DS.MoreVertex()) {
649       B.MakeVertex(V,P.Value(),tol);
650       DS.Append(V,Par);
651     }   
652   }
653   DS.AddIntV(V);
654 }
655
656 //=======================================================================
657 //function : ProcessEdges
658 //purpose  : private, split edges with outline vertices
659 //=======================================================================
660
661 void  HLRTopoBRep_DSFiller::ProcessEdges (HLRTopoBRep_Data& DS)
662 {
663   BRep_Builder B;
664   TopoDS_Edge newE;
665   TopoDS_Vertex VF,VL,VI;
666   Standard_Real PF,PL,PI;
667
668   for (DS.InitEdge(); DS.MoreEdge(); DS.NextEdge()) {
669     TopoDS_Edge E = DS.Edge();
670     TopTools_ListOfShape& SplE = DS.AddSplE(E);
671     VF = TopExp::FirstVertex(E);
672     VL = TopExp::LastVertex(E);
673     BRep_Tool::Range(E,PF,PL);
674     VF.Orientation(TopAbs_FORWARD);
675     VL.Orientation(TopAbs_REVERSED);
676
677     for (DS.InitVertex(E); DS.MoreVertex(); DS.NextVertex()) {
678       VI = DS.Vertex();
679       PI = DS.Parameter();
680       VI.Orientation(TopAbs_REVERSED);
681       newE = E;
682       newE.EmptyCopy();
683       newE.Orientation(TopAbs_FORWARD);
684       B.Add(newE,VF);
685       B.UpdateVertex(VF,PF,newE,BRep_Tool::Tolerance(VF));
686       B.Add(newE,VI);
687       B.UpdateVertex(VI,PI,newE,BRep_Tool::Tolerance(VI));
688       newE.Orientation(E.Orientation());
689       SplE.Append(newE);
690       VF = VI;
691       PF = PI;
692       VF.Orientation(TopAbs_FORWARD);
693     }
694     newE = E;
695     newE.EmptyCopy();
696     newE.Orientation(TopAbs_FORWARD);
697     B.Add(newE,VF);
698     B.UpdateVertex(VF,PF,newE,BRep_Tool::Tolerance(VF));
699     B.Add(newE,VL);
700     B.UpdateVertex(VL,PL,newE,BRep_Tool::Tolerance(VL));
701     newE.Orientation(E.Orientation());
702     SplE.Append(newE);
703   }
704 }
705