src/IntStart/IntStart_SearchOnBoundaries.gxx

   1 // Copyright (c) 1995-1999 Matra Datavision
   2 // Copyright (c) 1999-2012 OPEN CASCADE SAS
   3 //
   4 // The content of this file is subject to the Open CASCADE Technology Public
   5 // License Version 6.5 (the "License"). You may not use the content of this file
   6 // except in compliance with the License. Please obtain a copy of the License
   7 // at http://www.opencascade.org and read it completely before using this file.
   8 //
   9 // The Initial Developer of the Original Code is Open CASCADE S.A.S., having its
  10 // main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France.
  11 //
  12 // The Original Code and all software distributed under the License is
  13 // distributed on an "AS IS" basis, without warranty of any kind, and the
  14 // Initial Developer hereby disclaims all such warranties, including without
  15 // limitation, any warranties of merchantability, fitness for a particular
  16 // purpose or non-infringement. Please see the License for the specific terms
  17 // and conditions governing the rights and limitations under the License.
  18
  19
  20 #include <TopoDS_Edge.hxx>
  21 #include <Geom_Curve.hxx>
  22 #include <BRepAdaptor_Curve.hxx>
  23 #include <Adaptor3d_HSurface.hxx>
  24 #include <GeomAbs_SurfaceType.hxx>
  25 #include <BRep_Tool.hxx>
  26 #include <Geom_Line.hxx>
  27 #include <gp_Lin.hxx>
  28 #include <gp_Vec.hxx>
  29 #include <gp_Dir.hxx>
  30 #include <gp_Cylinder.hxx>
  31 #include <gp_Ax1.hxx>
  32 #include <gp_Lin.hxx>
  33
  34 #include <GeomAdaptor_Curve.hxx>
  35 #include <Precision.hxx>
  36 #include <Extrema_ExtCC.hxx>
  37 #include <Extrema_POnCurv.hxx>
  38
  39 #include <math_FunctionSample.hxx>
  40 #include <math_FunctionAllRoots.hxx>
  41 #include <TColgp_SequenceOfPnt.hxx>
  42
  43 //  Modified by skv - Tue Aug 31 12:13:51 2004 OCC569
  44
  45 #include <Precision.hxx>
  46 #include <IntSurf_Quadric.hxx>
  47
  48 static void FindVertex (const TheArc&,
  49                         const Handle(TheTopolTool)&,
  50                         TheFunction&,
  51                         IntStart_SequenceOfPathPoint&,
  52                         const Standard_Real);
  53
  54
  55 static void BoundedArc (const TheArc& A,
  56                         const Handle(TheTopolTool)& Domain,
  57                         const Standard_Real Pdeb,
  58                         const Standard_Real Pfin,
  59                         TheFunction& Func,
  60                         IntStart_SequenceOfPathPoint& pnt,
  61                         IntStart_SequenceOfSegment& seg,
  62                         const Standard_Real TolBoundary,
  63                         const Standard_Real TolTangency,
  64                         Standard_Boolean& Arcsol,
  65                         const Standard_Boolean RecheckOnRegularity);
  66
  67 static void PointProcess (const gp_Pnt&,
  68                           const Standard_Real,
  69                           const TheArc&,
  70                           const Handle(TheTopolTool)&,
  71                           IntStart_SequenceOfPathPoint&,
  72                           const Standard_Real,
  73                           Standard_Integer&);
  74
  75 static Standard_Integer TreatLC (const TheArc& A,
  76                                  const Handle(TheTopolTool)& aDomain,
  77                                  const IntSurf_Quadric& aQuadric,
  78                                  const Standard_Real TolBoundary,
  79                                  IntStart_SequenceOfPathPoint& pnt);
  80
  81 static Standard_Boolean IsRegularity(const TheArc& A,
  82                                      const Handle(TheTopolTool)& aDomain);
  83
  84
  85 //=======================================================================
  86 //function : FindVertex
  87 //purpose  :
  88 //=======================================================================
  89 void FindVertex (const TheArc& A,
  90                  const Handle(TheTopolTool)& Domain,
  91                  TheFunction& Func,
  92                  IntStart_SequenceOfPathPoint& pnt,
  93                  const Standard_Real Toler)
  94 {
  95
  96 // Find the vertex of the arc A restriction solutions. It stores
  97 // Vertex in the list solutions pnt.
  98
  99
 100   TheVertex vtx;
 101   Standard_Real param,valf;
 102   Standard_Integer itemp;
 103
 104   Domain->Initialize(A);
 105   Domain->InitVertexIterator();
 106   while (Domain->MoreVertex()) {
 107     vtx = Domain->Vertex();
 108     param = TheSOBTool::Parameter(vtx,A);
 109
 110     // Evaluate the function and look compared to tolerance of the
 111     // Vertex. If distance <= tolerance then add a vertex to the list of solutions.
 112     // The arc is already assumed in the load function.
 113
 114     Func.Value(param,valf);
 115     if (Abs(valf) <= Toler) {
 116       itemp = Func.GetStateNumber();
 117       pnt.Append(IntStart_ThePathPoint(Func.Valpoint(itemp),Toler, vtx,A,param));
 118       // Solution is added
 119     }
 120     Domain->NextVertex();
 121   }
 122 }
 123
 124 static
 125 void BoundedArc (const TheArc& A,
 126                  const Handle(TheTopolTool)& Domain,
 127                  const Standard_Real Pdeb,
 128                  const Standard_Real Pfin,
 129                  TheFunction& Func,
 130                  IntStart_SequenceOfPathPoint& pnt,
 131                  IntStart_SequenceOfSegment& seg,
 132                  const Standard_Real TolBoundary,
 133                  const Standard_Real TolTangency,
 134                  Standard_Boolean& Arcsol,
 135                  const Standard_Boolean RecheckOnRegularity)
 136 {
 137
 138 // Recherche des points solutions et des bouts d arc solution sur un arc donne.
 139 // On utilise la fonction math_FunctionAllRoots. Ne convient donc que pour
 140 // des arcs ayant un point debut et un point de fin (intervalle ferme de
 141 // parametrage).
 142
 143   Standard_Integer i,Nbi,Nbp;
 144
 145   gp_Pnt ptdeb,ptfin;
 146   Standard_Real pardeb = 0., parfin = 0.;
 147   Standard_Integer ideb,ifin,range,ranged,rangef;
 148
 149
 150   // Creer l echantillonage (math_FunctionSample ou classe heritant)
 151   // Appel a math_FunctionAllRoots
 152
 153   Standard_Real EpsX = TheArcTool::Resolution(A,Precision::Confusion());
 154   //@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 155   //@@@ La Tolerance est asociee a l arc  ( Incoherence avec le cheminement )
 156   //@@@   ( EpsX ~ 1e-5   et ResolutionU et V ~ 1e-9 )
 157   //@@@   le vertex trouve ici n'est pas retrouve comme point d arret d une
 158   //@@@   ligne de cheminement
 159   //@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 160   EpsX = 0.0000000001;
 161   //@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 162   //@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 163   //@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 164
 165 //  Standard_Integer NbEchant = TheSOBTool::NbSamplesOnArc(A);
 166   Standard_Integer NbEchant = Func.NbSamples();
 167
 168   //-- Modif 24  Aout 93 -----------------------------
 169   Standard_Real nTolTangency = TolTangency;
 170   if((Pfin - Pdeb) < (TolTangency*10.0)) {
 171     nTolTangency=(Pfin-Pdeb)*0.1;
 172   }
 173   if(EpsX>(nTolTangency+nTolTangency)) {
 174     EpsX = nTolTangency * 0.1;
 175   }
 176   //--------------------------------------------------
 177   //-- Plante avec un edge avec 2 Samples
 178   //-- dont les extremites son solutions (f=0)
 179   //-- et ou la derivee est nulle
 180   //-- Exemple : un segment diametre d une sphere
 181   //-- if(NbEchant<3) NbEchant = 3; //-- lbr le 19 Avril 95
 182   //--------------------------------------------------
 183   Standard_Real para=0,dist,maxdist;
 184 /*  if(NbEchant<20) NbEchant = 20; //-- lbr le 22 Avril 96
 185                                  //-- Toujours des pbs
 186 */
 187    if(NbEchant<100) NbEchant = 100; //-- lbr le 22 Avril 96
 188                                   //-- Toujours des pbs
 189
 190
 191   //-------------------------------------------------------------- REJECTIONS le 15 oct 98
 192   Standard_Boolean Rejection=Standard_True;
 193   Standard_Real maxdr,maxr,minr,ur,dur;
 194   minr=RealLast();
 195   maxr=-minr;
 196   maxdr=-minr;
 197   dur=(Pfin-Pdeb)*0.2;
 198   for(i=1,ur=Pdeb;i<=6;i++) {
 199     Standard_Real F,D;
 200     if(Func.Values(ur,F,D)) {
 201       Standard_Real lminr,lmaxr;
 202       if(D<0.0) D=-D;
 203       D*=dur+dur;
 204       if(D>maxdr) maxdr=D;
 205       lminr=F-D;
 206       lmaxr=F+D;
 207       if(lminr<minr) minr=lminr;
 208       if(lmaxr>maxr) maxr=lmaxr;
 209       if(minr<0.0 && maxr>0.0)  {
 210         Rejection=Standard_False;
 211         break;
 212       }
 213     }
 214     ur+=dur;
 215   }
 216   if(Rejection)
 217   {
 218     dur=0.001+maxdr+(maxr-minr)*0.1;
 219     minr-=dur;
 220     maxr+=dur;
 221     if(minr<0.0 && maxr>0.0)  {
 222       Rejection=Standard_False;
 223     }
 224   }
 225
 226   Arcsol=Standard_False;
 227
 228   if(Rejection==Standard_False) {
 229     math_FunctionSample Echant(Pdeb,Pfin,NbEchant);
 230
 231     Standard_Boolean aelargir=Standard_True;
 232     //modified by NIZNHY-PKV Thu Apr 12 09:25:19 2001 f
 233     //
 234     //maxdist = 100.0*TolBoundary;
 235     maxdist = TolBoundary+TolTangency;
 236     //
 237     //modified by NIZNHY-PKV Thu Apr 12 09:25:23 2001 t
 238     for(i=1; i<=NbEchant && aelargir;i++) {
 239       Standard_Real u = Echant.GetParameter(i);
 240       if(Func.Value(u,dist)) {
 241         if(dist>maxdist || -dist>maxdist) {
 242           aelargir=Standard_False;
 243         }
 244       }
 245     }
 246     if(!(aelargir && maxdist<0.01)) {
 247       maxdist = TolBoundary;
 248     }
 249
 250     math_FunctionAllRoots Sol(Func,Echant,EpsX,maxdist,maxdist); //-- TolBoundary,nTolTangency);
 251
 252     if (!Sol.IsDone()) {Standard_Failure::Raise();}
 253
 254     Nbp=Sol.NbPoints();
 255
 256     //jgv: build solution on the whole boundary
 257     if (RecheckOnRegularity && Nbp > 0 && IsRegularity(A, Domain))
 258     {
 259       //Standard_Real theTol = Domain->MaxTolerance(A);
 260       //theTol += theTol;
 261       Standard_Real theTol = 5.e-4;
 262       math_FunctionAllRoots SolAgain(Func,Echant,EpsX,theTol,theTol); //-- TolBoundary,nTolTangency);
 263
 264       if (!SolAgain.IsDone()) {Standard_Failure::Raise();}
 265
 266       Standard_Integer Nbi_again = SolAgain.NbIntervals();
 267
 268       if (Nbi_again > 0)
 269       {
 270         Standard_Integer NbSamples = 10;
 271         Standard_Real delta = (Pfin - Pdeb)/NbSamples;
 272         Standard_Real GlobalTol = theTol*10;
 273         Standard_Boolean SolOnBoundary = Standard_True;
 274         for (i = 0; i <= NbSamples; i++)
 275         {
 276           Standard_Real aParam = Pdeb + i*delta;
 277           Standard_Real aValue;
 278           Func.Value(aParam, aValue);
 279           if (Abs(aValue) > GlobalTol)
 280           {
 281             SolOnBoundary = Standard_False;
 282             break;
 283           }
 284         }
 285
 286         if (SolOnBoundary)
 287         {
 288           for (i = 1; i <= Nbi_again; i++)
 289           {
 290             IntStart_TheSegment newseg;
 291             newseg.SetValue(A);
 292             // Recuperer point debut et fin, et leur parametre.
 293             SolAgain.GetInterval(i,pardeb,parfin);
 294
 295             if (Abs(pardeb - Pdeb) <= Precision::PConfusion())
 296               pardeb = Pdeb;
 297             if (Abs(parfin - Pfin) <= Precision::PConfusion())
 298               parfin = Pfin;
 299
 300             SolAgain.GetIntervalState(i,ideb,ifin);
 301
 302             //-- cout<<" Debug : IntStart_SearchOnBoundaries_1.gxx : i= "<<i<<" ParDeb:"<<pardeb<<"  ParFin:"<<parfin<<endl;
 303
 304             ptdeb=Func.Valpoint(ideb);
 305             ptfin=Func.Valpoint(ifin);
 306
 307             PointProcess(ptdeb,pardeb,A,Domain,pnt,theTol,ranged);
 308             newseg.SetLimitPoint(pnt.Value(ranged),Standard_True);
 309             PointProcess(ptfin,parfin,A,Domain,pnt,theTol,rangef);
 310             newseg.SetLimitPoint(pnt.Value(rangef),Standard_False);
 311             seg.Append(newseg);
 312           }
 313           Arcsol=Standard_True;
 314           return;
 315         }
 316       }
 317     }
 318     ////////////////////////////////////////////
 319
 320     //-- detection du cas ou la fonction est quasi tangente et que les
 321     //-- zeros sont quasi confondus.
 322     //-- Dans ce cas on prend le point "milieu"
 323     //-- On suppose que les solutions sont triees.
 324
 325     Standard_Real *TabSol=NULL;
 326     if(Nbp) {
 327       TabSol = new Standard_Real [Nbp+2];
 328       for(i=1;i<=Nbp;i++) {
 329         TabSol[i]=Sol.GetPoint(i);
 330       }
 331       Standard_Boolean ok;
 332       do {
 333         ok=Standard_True;
 334         for(i=1;i<Nbp;i++) {
 335           if(TabSol[i]>TabSol[i+1]) {
 336             ok=Standard_False;
 337             para=TabSol[i]; TabSol[i]=TabSol[i+1]; TabSol[i+1]=para;
 338           }
 339         }
 340       }
 341
 342       while(ok==Standard_False);
 343       //modified by NIZNHY-PKV Wed Mar 21 18:34:18 2001 f
 344       //////////////////////////////////////////////////////////
 345       // The treatment of the situation when line(arc) that is
 346       // tangent to cylinder(domain).
 347       // We should have only one solution i.e Nbp=1. Ok?
 348       // But we have 2,3,.. solutions.     That is wrong ersult.
 349       // The TreatLC(...) function is dedicated to solve the pb.
 350       //                           PKV Fri Mar 23 12:17:29 2001
 351       Standard_Integer ip;
 352       const IntSurf_Quadric& aQuadric=Func.Quadric();
 353
 354       ip=TreatLC (A, Domain, aQuadric, TolBoundary, pnt);
 355       if (ip) {
 356       //////////////////////////////////////////////////////////
 357       //modified by NIZNHY-PKV Wed Mar 21 18:34:23 2001 t
 358       //
 359       // Using of old usual way proposed by Laurent
 360       //
 361       for(i=1;i<Nbp;i++) {
 362         Standard_Real parap1=TabSol[i+1];
 363         para=TabSol[i];
 364         Standard_Real param=(para+parap1)*0.5;
 365         Standard_Real ym;
 366         if(Func.Value(param,ym)) {
 367           if(Abs(ym)<maxdist) {
 368             //  Modified by skv - Tue Aug 31 12:13:51 2004 OCC569 Begin
 369             // Consider this interval as tangent one. Treat it to find
 370             // parameter with the lowest function value.
 371
 372             // Compute the number of nodes.
 373             Standard_Real    aTol = TolBoundary*1000.0;
 374             if(aTol > 0.001)
 375         aTol = 0.001;
 376
 377             // fix floating point exception 569, chl-922-e9
 378             parap1 = (Abs(parap1) < 1.e9) ? parap1 : ((parap1 >= 0.) ? 1.e9 : -1.e9);
 379             para   = (Abs(para) < 1.e9) ? para : ((para >= 0.) ? 1.e9 : -1.e9);
 380
 381             Standard_Integer aNbNodes = RealToInt(Ceiling((parap1 - para)/aTol));
 382
 383             Standard_Real    aVal     = RealLast();
 384             //Standard_Integer aNbNodes = 23;
 385             Standard_Real    aDelta   = (parap1 - para)/(aNbNodes + 1.);
 386             Standard_Integer ii;
 387             Standard_Real    aCurPar;
 388             Standard_Real    aCurVal;
 389
 390             for (ii = 0; ii <= aNbNodes + 1; ii++) {
 391         aCurPar = (ii < aNbNodes + 1) ? para + ii*aDelta : parap1;
 392
 393         if (Func.Value(aCurPar, aCurVal)) {
 394           //if (aCurVal < aVal) {
 395           if (Abs(aCurVal) < aVal) {
 396             //aVal  = aCurVal;
 397             aVal  = Abs(aCurVal);
 398             param = aCurPar;
 399           }
 400         }
 401             }
 402             //  Modified by skv - Tue Aug 31 12:13:51 2004 OCC569 End
 403             TabSol[i]=Pdeb-1;
 404             TabSol[i+1]=param;
 405           }
 406         }
 407       }
 408
 409       for (i=1; i<=Nbp; i++) {
 410         para=TabSol[i];
 411         if((para-Pdeb)<EpsX || (Pfin-para)<EpsX) {
 412         }
 413         else {
 414           if(Func.Value(para,dist)) {
 415             //modified by jgv 5.07.01 for the bug buc60927
 416             Standard_Integer anIndx;
 417             Standard_Real aParam;
 418             if (Abs(dist) < maxdist)
 419         {
 420           aParam = Sol.GetPoint(i);
 421           if (Abs(aParam-Pdeb)<=Precision::PConfusion() || Abs(aParam-Pfin)<=Precision::PConfusion())
 422             anIndx = Sol.GetPointState(i);
 423           else
 424             {
 425               anIndx = Func.GetStateNumber(); //take the middle point
 426               aParam = para;
 427             }
 428         }
 429             else
 430         {
 431           anIndx = Sol.GetPointState(i);
 432           aParam = Sol.GetPoint(i);
 433         }
 434             const gp_Pnt& aPnt = Func.Valpoint(anIndx);
 435             //////////////////////////////////////////////
 436
 437             PointProcess(aPnt, aParam, A, Domain, pnt, TolBoundary, range);
 438           }
 439         }
 440       }
 441
 442       if(TabSol) {
 443         delete [] TabSol;
 444       }
 445       }// end ofif (ip)
 446     } // end of if(Nbp)
 447
 448     // Pour chaque intervalle trouve faire
 449     //   Traiter les extremites comme des points
 450     //   Ajouter intervalle dans la liste des segments
 451
 452     Nbi=Sol.NbIntervals();
 453
 454
 455     if (!RecheckOnRegularity && Nbp) {
 456       //--cout<<" Debug : IntStart_SearchOnBoundaries_1.gxx :Nbp>0  0 <- Nbi "<<Nbi<<endl;
 457       Nbi=0;
 458     }
 459
 460     //-- cout<<" Debug : IntStart_SearchOnBoundaries_1.gxx : Nbi : "<<Nbi<<endl;
 461
 462     for (i=1; i<=Nbi; i++) {
 463       IntStart_TheSegment newseg;
 464       newseg.SetValue(A);
 465       // Recuperer point debut et fin, et leur parametre.
 466       Sol.GetInterval(i,pardeb,parfin);
 467       Sol.GetIntervalState(i,ideb,ifin);
 468
 469
 470       //-- cout<<" Debug : IntStart_SearchOnBoundaries_1.gxx : i= "<<i<<" ParDeb:"<<pardeb<<"  ParFin:"<<parfin<<endl;
 471
 472       ptdeb=Func.Valpoint(ideb);
 473       ptfin=Func.Valpoint(ifin);
 474
 475       PointProcess(ptdeb,pardeb,A,Domain,pnt,TolBoundary,ranged);
 476       newseg.SetLimitPoint(pnt.Value(ranged),Standard_True);
 477       PointProcess(ptfin,parfin,A,Domain,pnt,TolBoundary,rangef);
 478       newseg.SetLimitPoint(pnt.Value(rangef),Standard_False);
 479       seg.Append(newseg);
 480     }
 481
 482     if (Nbi==1) {
 483       if (pardeb == Pdeb && parfin == Pfin) {
 484         Arcsol=Standard_True;
 485       }
 486     }
 487   }
 488 }
 489
 490 //=======================================================================
 491 //function : ComputeBoundsfromInfinite
 492 //purpose  :
 493 //=======================================================================
 494 // - PROVISIONAL - TEMPORARY - NOT GOOD - NYI - TO DO
 495 // - Temporary - temporary - not good - nyi - to do
 496 void ComputeBoundsfromInfinite(TheFunction& Func,
 497                                Standard_Real& PDeb,
 498                                Standard_Real& PFin,
 499                                Standard_Integer& NbEchant)
 500 {
 501
 502   // - We are looking for parameters for start and end of the arc (2d curve)
 503   // - Infinity, a way to intersect the quadric with a portion of arc
 504   // - Finished.
 505   //
 506   // - The quadric is a plane, a cylinder, a cone and a sphere.
 507   // - Idea: We take any point on the arc and the fact grow
 508   // - Terminals to the signed distance function values or is likely
 509   // - S cancel.
 510   //
 511   // - WARNING: The following calculations provide a very estimated coarse parameters.
 512   // - This avoids the raises and allows a case of Boxes
 513   // - Inifinies walk. It will take this code
 514   // - With curve surface intersections.
 515
 516   NbEchant = 100;
 517
 518   Standard_Real U0    = 0.0;
 519   Standard_Real dU    = 0.001;
 520   Standard_Real Dist0,Dist1;
 521
 522   Func.Value(U0   , Dist0);
 523   Func.Value(U0+dU, Dist1);
 524   Standard_Real dDist = Dist1 - Dist0;
 525   if(dDist) {
 526     U0  -=  dU*Dist0 / dDist;
 527     PDeb = PFin = U0;
 528     Standard_Real Umin = U0 - 1e5;
 529     Func.Value(Umin   , Dist0);
 530     Func.Value(Umin+dU, Dist1);
 531     dDist = Dist1-Dist0;
 532     if(dDist) {
 533       Umin  -=  dU*Dist0 / dDist;
 534     }
 535     else {
 536       Umin-=10.0;
 537     }
 538     Standard_Real Umax = U0 + 1e8;
 539     Func.Value(Umax   , Dist0);
 540     Func.Value(Umax+dU, Dist1);
 541     dDist = Dist1-Dist0;
 542     if(dDist) {
 543       Umax  -=  dU*Dist0 / dDist;
 544     }
 545     else {
 546       Umax+=10.0;
 547     }
 548     if(Umin>U0) { Umin=U0-10.0; }
 549     if(Umax<U0) { Umax=U0+10.0; }
 550
 551     PFin = Umax + 10. * (Umax - Umin);
 552     PDeb = Umin - 10. * (Umax - Umin);
 553   }
 554   else {
 555     //-- Possibilite de Arc totalement inclu ds Quad
 556     PDeb = 1e10;
 557     PFin = -1e10;
 558   }
 559 }
 560
 561 //=======================================================================
 562 //function : PointProcess
 563 //purpose  :
 564 //=======================================================================
 565 void PointProcess (const gp_Pnt& Pt,
 566                    const Standard_Real Para,
 567                    const TheArc& A,
 568                    const Handle(TheTopolTool)& Domain,
 569                    IntStart_SequenceOfPathPoint& pnt,
 570                    const Standard_Real Tol,
 571                    Standard_Integer& Range)
 572 {
 573
 574 // Check to see if a solution point is coincident with a vertex.
 575 // If confused, you should find this vertex in the list of
 576 // Start. It then returns the position of this point in the list pnt.
 577 // Otherwise, add the point in the list.
 578
 579   Standard_Integer k;
 580   Standard_Boolean found,goon;
 581   Standard_Real dist,toler;
 582
 583   Standard_Integer Nbsol = pnt.Length();
 584   TheVertex vtx;
 585   IntStart_ThePathPoint ptsol;
 586
 587   Domain->Initialize(A);
 588   Domain->InitVertexIterator();
 589   found = Standard_False;
 590   goon = Domain->MoreVertex();
 591   while (goon) {
 592     vtx = Domain->Vertex();
 593     dist= Abs(Para-TheSOBTool::Parameter(vtx,A));
 594     toler = TheSOBTool::Tolerance(vtx,A);
 595 #ifdef DEB
 596     if(toler>0.1) {
 597       cout<<"IntStart_SearchOnBoundaries_1.gxx  : ** WARNING ** Tol Vertex="<<toler<<endl;
 598       cout<<"                                     Ou Edge degenere Ou Kro pointu"<<endl;
 599       if(toler>10000) toler=1e-7;
 600     }
 601 #endif
 602
 603     if (dist <= toler) {
 604       // Locate the vertex in the list of solutions
 605       k=1;
 606       found = (k>Nbsol);
 607       while (!found) {
 608         ptsol = pnt.Value(k);
 609         if (!ptsol.IsNew()) {
 610         //jag 940608  if (ptsol.Vertex() == vtx && ptsol.Arc()    == A) {
 611           if (Domain->Identical(ptsol.Vertex(),vtx) &&
 612                     ptsol.Arc()    == A &&
 613                     Abs(ptsol.Parameter()-Para) <= toler) {
 614             found=Standard_True;
 615           }
 616           else {
 617             k=k+1;
 618             found=(k>Nbsol);
 619           }
 620         }
 621         else {
 622           k=k+1;
 623           found=(k>Nbsol);
 624         }
 625       }
 626       if (k<=Nbsol) {     // We find the vertex
 627         Range = k;
 628       }
 629       else {              // Otherwise
 630         ptsol.SetValue(Pt,Tol,vtx,A,Para);
 631         pnt.Append(ptsol);
 632         Range = pnt.Length();
 633       }
 634       found = Standard_True;
 635       goon = Standard_False;
 636     }
 637     else {
 638       Domain->NextVertex();
 639       goon = Domain->MoreVertex();
 640     }
 641   }
 642
 643   if (!found) {   // No one is falling on a vertex
 644     //jgv: do not add segment's extremities if they already exist
 645     Standard_Boolean found_internal = Standard_False;
 646     for (k = 1; k <= pnt.Length(); k++)
 647     {
 648       ptsol = pnt.Value(k);
 649       if (ptsol.Arc() != A ||
 650           !ptsol.IsNew()) //vertex
 651         continue;
 652       if (Abs(ptsol.Parameter()-Para) <= Precision::PConfusion())
 653       {
 654         found_internal = Standard_True;
 655         Range = k;
 656       }
 657     }
 658     /////////////////////////////////////////////////////////////
 659
 660     if (!found_internal)
 661     {
 662       Standard_Real TOL=Tol;
 663       TOL*=1000.0;
 664       if(TOL>0.001) TOL=0.001;
 665
 666       ptsol.SetValue(Pt,TOL,A,Para);
 667       pnt.Append(ptsol);
 668       Range = pnt.Length();
 669     }
 670   }
 671 }
 672
 673 //=======================================================================
 674 //function : IsRegularity
 675 //purpose  :
 676 //=======================================================================
 677 Standard_Boolean IsRegularity(const TheArc& /*A*/,
 678                               const Handle(TheTopolTool)& aDomain)
 679 {
 680   Standard_Address anEAddress=aDomain->Edge();
 681   if (anEAddress==NULL) {
 682     return Standard_False;
 683   }
 684
 685   TopoDS_Edge* anE=(TopoDS_Edge*)anEAddress;
 686
 687   return (BRep_Tool::HasContinuity(*anE));
 688 }
 689
 690 //=======================================================================
 691 //function : TreatLC
 692 //purpose  :
 693 //=======================================================================
 694 Standard_Integer TreatLC (const TheArc& A,
 695                           const Handle(TheTopolTool)& aDomain,
 696                           const IntSurf_Quadric& aQuadric,
 697                           const Standard_Real TolBoundary,
 698                           IntStart_SequenceOfPathPoint& pnt)
 699 {
 700   Standard_Integer anExitCode=1, aNbExt;
 701
 702   Standard_Address anEAddress=aDomain->Edge();
 703   if (anEAddress==NULL) {
 704     return anExitCode;
 705   }
 706
 707   TopoDS_Edge* anE=(TopoDS_Edge*)anEAddress;
 708
 709   if (BRep_Tool::Degenerated(*anE)) {
 710     return anExitCode;
 711   }
 712
 713   GeomAbs_CurveType   aTypeE;
 714   BRepAdaptor_Curve aBAC(*anE);
 715   aTypeE=aBAC.GetType();
 716
 717   if (aTypeE!=GeomAbs_Line) {
 718     return anExitCode;
 719   }
 720
 721   GeomAbs_SurfaceType aTypeS;
 722   aTypeS=aQuadric.TypeQuadric();
 723
 724   if (aTypeS!=GeomAbs_Cylinder) {
 725     return anExitCode;
 726   }
 727
 728   Standard_Real f, l, U1f, U1l, U2f, U2l, U1, UEgde, TOL, aDist, aR, aRRel, Tol;
 729   Handle(Geom_Curve) aCEdge=BRep_Tool::Curve(*anE, f, l);
 730
 731   gp_Cylinder aCyl=aQuadric.Cylinder();
 732   const gp_Ax1& anAx1=aCyl.Axis();
 733   gp_Lin aLin(anAx1);
 734   Handle(Geom_Line) aCAxis=new Geom_Line (aLin);
 735   aR=aCyl.Radius();
 736
 737   U1f = aCAxis->FirstParameter();
 738   U1l = aCAxis->LastParameter();
 739
 740   U2f = aCEdge->FirstParameter();
 741   U2l = aCEdge->LastParameter();
 742
 743
 744   GeomAdaptor_Curve C1, C2;
 745
 746   C1.Load(aCAxis);
 747   C2.Load(aCEdge);
 748
 749   Tol = Precision::PConfusion();
 750
 751   Extrema_ExtCC anExtCC(C1, C2, U1f, U1l, U2f, U2l, Tol, Tol);
 752
 753   aNbExt=anExtCC.NbExt();
 754   if (aNbExt!=1) {
 755     return anExitCode;
 756   }
 757
 758   gp_Pnt P1,PEdge;
 759   Extrema_POnCurv PC1, PC2;
 760
 761   anExtCC.Points(1, PC1, PC2);
 762
 763   P1   =PC1.Value();
 764   PEdge=PC2.Value();
 765
 766   U1=PC1.Parameter();
 767   UEgde=PC2.Parameter();
 768
 769   aDist=PEdge.Distance(P1);
 770   aRRel=fabs(aDist-aR)/aR;
 771   if (aRRel > TolBoundary) {
 772     return anExitCode;
 773   }
 774
 775   if (UEgde < (f+TolBoundary) || UEgde > (l-TolBoundary)) {
 776     return anExitCode;
 777   }
 778   //
 779   // Do not wonder !
 780   // It was done as into PointProcess(...) function
 781   //printf("TreatLC()=> tangent line is found\n");
 782   TOL=1000.*TolBoundary;
 783   if(TOL>0.001) TOL=0.001;
 784
 785   IntStart_ThePathPoint ptsol;
 786   ptsol.SetValue(PEdge, TOL, A, UEgde);
 787   pnt.Append(ptsol);
 788
 789   anExitCode=0;
 790   return anExitCode;
 791
 792 }
 793
 794
 795 //=======================================================================
 796 //function : IntStart_SearchOnBoundaries::IntStart_SearchOnBoundaries
 797 //purpose  :
 798 //=======================================================================
 799 IntStart_SearchOnBoundaries::IntStart_SearchOnBoundaries ()
 800 :  done(Standard_False)
 801 {
 802 }
 803
 804 //=======================================================================
 805 //function : Perform
 806 //purpose  :
 807 //=======================================================================
 808   void IntStart_SearchOnBoundaries::Perform (TheFunction& Func,
 809                                              const Handle(TheTopolTool)& Domain,
 810                                              const Standard_Real TolBoundary,
 811                                              const Standard_Real TolTangency,
 812                                              const Standard_Boolean RecheckOnRegularity)
 813 {
 814
 815   done = Standard_False;
 816   spnt.Clear();
 817   sseg.Clear();
 818
 819   Standard_Boolean Arcsol;
 820   Standard_Real PDeb,PFin, prm, tol;
 821   Standard_Integer i, nbknown, nbfound,index;
 822   gp_Pnt pt;
 823
 824   Domain->Init();
 825
 826   if (Domain->More()) {
 827     all  = Standard_True;
 828   }
 829   else {
 830     all = Standard_False;
 831   }
 832
 833   while (Domain->More()) {
 834     TheArc A = Domain->Value();
 835     if (!TheSOBTool::HasBeenSeen(A)) {
 836       Func.Set(A);
 837       FindVertex(A,Domain,Func,spnt,TolBoundary);
 838       TheSOBTool::Bounds(A,PDeb,PFin);
 839       if(Precision::IsNegativeInfinite(PDeb) ||
 840          Precision::IsPositiveInfinite(PFin)) {
 841         Standard_Integer NbEchant;
 842         ComputeBoundsfromInfinite(Func,PDeb,PFin,NbEchant);
 843       }
 844       BoundedArc(A,Domain,PDeb,PFin,Func,spnt,sseg,TolBoundary,TolTangency,Arcsol,RecheckOnRegularity);
 845       all = (all && Arcsol);
 846     }
 847
 848     else {
 849       // as it seems we'll never be here, because
 850       // TheSOBTool::HasBeenSeen(A) always returns FALSE
 851       nbfound = spnt.Length();
 852
 853       // On recupere les points connus
 854       nbknown = TheSOBTool::NbPoints(A);
 855       for (i=1; i<=nbknown; i++) {
 856         TheSOBTool::Value(A,i,pt,tol,prm);
 857         if (TheSOBTool::IsVertex(A,i)) {
 858           TheVertex vtx;
 859           TheSOBTool::Vertex(A,i,vtx);
 860           spnt.Append(IntStart_ThePathPoint(pt,tol,vtx,A,prm));
 861         }
 862         else {
 863           spnt.Append(IntStart_ThePathPoint(pt,tol,A,prm));
 864         }
 865       }
 866       // On recupere les arcs solutions
 867       nbknown = TheSOBTool::NbSegments(A);
 868       for (i=1; i<=nbknown; i++) {
 869         IntStart_TheSegment newseg;
 870         newseg.SetValue(A);
 871         if (TheSOBTool::HasFirstPoint(A,i,index)) {
 872           newseg.SetLimitPoint(spnt.Value(nbfound+index),Standard_True);
 873         }
 874         if (TheSOBTool::HasLastPoint(A,i,index)) {
 875           newseg.SetLimitPoint(spnt.Value(nbfound+index),Standard_False);
 876         }
 877         sseg.Append(newseg);
 878       }
 879       all = (all& TheSOBTool::IsAllSolution(A));
 880     }
 881     Domain->Next();
 882   }
 883   done = Standard_True;
 884 }