src/IntWalk/IntWalk_IWalking_2.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 //-- IntWalk_IWalking_2.gxx
  20
  21 #ifndef DEB
  22 #define No_Standard_RangeError
  23 #define No_Standard_OutOfRange
  24 #endif
  25
  26
  27 // _______________________________________________
  28 //
  29 // Location of point (u, v) in the natural domain of a surface AND update
  30 // of couple (u, v) for the calculation of the next point.
  31 //
  32 Standard_Boolean IntWalk_IWalking::Cadrage
  33   (math_Vector& BornInf,
  34    math_Vector& BornSup,
  35    math_Vector& UVap,
  36    Standard_Real& Step,
  37 //   Standard_Real& StepV,
  38    const Standard_Integer StepSign) const
  39
  40 // there are always :
  41 // BorInf(1) <= UVap(1) <= BornSup(1) et BorInf(2) <= UVap(2) <= BornSup(2)
  42 // 1) check if the process point is out of the natural domain of the surface.
  43 // 2) if yes the approximated point is located on border taking the best direction
  44 // the step and a limit blocating one of the parameters during the recent call of
  45 // FunctionSetRoot are modified;
  46 // 3) couple (u, v) is recomputed by approximation for the calculation of the next point.
  47 // 4) return Standard_True if location, Standard_False if no location.
  48 {
  49   Standard_Real Duvx = previousd2d.X();
  50   Standard_Real Duvy = previousd2d.Y();
  51
  52   if (!reversed) {
  53     previousPoint.ParametersOnS2(UVap(1),UVap(2));
  54   }
  55   else {
  56     previousPoint.ParametersOnS1(UVap(1),UVap(2));
  57   }
  58
  59   Standard_Real U1 = UVap(1) + Step * Duvx * StepSign;
  60   Standard_Real V1 = UVap(2) + Step * Duvy * StepSign;
  61
  62
  63   Standard_Boolean infu = (U1 <= BornInf(1)+Precision::PConfusion());
  64   Standard_Boolean supu = (U1 >= BornSup(1)-Precision::PConfusion());
  65   Standard_Boolean infv = (V1 <= BornInf(2)+Precision::PConfusion());
  66   Standard_Boolean supv = (V1 >= BornSup(2)-Precision::PConfusion());
  67
  68   Standard_Real theStepU,theStepV;
  69
  70   if (!infu && !supu && !infv && !supv) {
  71     UVap(1) = U1;
  72     UVap(2) = V1;
  73     return Standard_False;
  74   }
  75
  76   if ((infu || supu) && (infv || supv)) {
  77     if (infu) { // jag 940616
  78       if(Duvx) {
  79         theStepU = Abs((BornInf(1) - UVap(1)) / Duvx);  // iso U =BornInf(1)
  80       }
  81       else {
  82         theStepU = Step;
  83       }
  84     }
  85     else {
  86       if(Duvx) {
  87         theStepU = Abs((BornSup(1) - UVap(1)) / Duvx);  // iso U =BornSup(1)
  88       }
  89       else {
  90         theStepU = Step;
  91       }
  92     }
  93     if (infv) { // jag 940616
  94       if(Duvy) {
  95         theStepV = Abs((BornInf(2) - UVap(2)) / Duvy);  // iso V =BornInf(2)
  96       }
  97       else {
  98         theStepV = Step;
  99       }
 100     }
 101     else {
 102       if(Duvy) {
 103         theStepV = Abs((BornSup(2) - UVap(2)) / Duvy);  // iso V =BornSup(2)
 104       }
 105       else {
 106         theStepV = Step;
 107       }
 108     }
 109
 110
 111     if (theStepU <= theStepV) {
 112       Step = theStepU;
 113       if (infu) {
 114         UVap(1) = BornInf(1);
 115         BornSup(1) = BornInf(1);
 116       }
 117       else {
 118         UVap(1) = BornSup(1);
 119         BornInf(1) = BornSup(1);
 120       }
 121       UVap(2) += Step*Duvy*StepSign;
 122     }
 123     else {
 124       Step = theStepV;
 125       if (infv) {
 126         UVap(2) = BornInf(2);
 127         BornSup(2) = BornInf(2);
 128       }
 129       else {
 130         UVap(2) = BornSup(2);
 131         BornInf(2) = BornSup(2);
 132       }
 133       UVap(1) += Step*Duvx*StepSign;
 134     }
 135     return Standard_True;
 136   }
 137
 138   else if (infu) { // jag 940616
 139     if(Duvx) {
 140       Standard_Real aStep = Abs((BornInf(1) - UVap(1)) / Duvx);  // iso U =BornInf(1)
 141       if(aStep<Step) Step=aStep;
 142     }
 143     BornSup(1) = BornInf(1);                     // limit the parameter
 144     UVap(1) = BornInf(1);
 145     UVap(2) += Step*Duvy*StepSign;;
 146     return Standard_True;
 147   }
 148   else if (supu) { // jag 940616
 149     if(Duvx) {
 150       Standard_Real aStep = Abs((BornSup(1) - UVap(1)) / Duvx);  // iso U =BornSup(1)
 151       if(aStep<Step) Step=aStep;
 152     }
 153     BornInf(1) = BornSup(1);                    // limit the parameter
 154     UVap(1) = BornSup(1);
 155     UVap(2) += Step*Duvy*StepSign;
 156     return Standard_True;
 157   }
 158   else if (infv) { // jag 940616
 159     if(Duvy) {
 160       Standard_Real aStep = Abs((BornInf(2) - UVap(2)) / Duvy);  // iso V =BornInf(2)
 161       if(aStep<Step) Step=aStep;
 162     }
 163     BornSup(2) = BornInf(2);
 164     UVap(1) += Step*Duvx*StepSign;
 165     UVap(2) = BornInf(2);
 166     return Standard_True;
 167   }
 168   else if (supv) { // jag 940616
 169     if(Duvy) {
 170       Standard_Real aStep = Abs((BornSup(2) - UVap(2)) / Duvy);  // iso V =BornSup(2)
 171       if(aStep<Step) Step=aStep;
 172     }
 173     BornInf(2) = BornSup(2);
 174     UVap(1) += Step*Duvx*StepSign;
 175     UVap(2) = BornSup(2);
 176     return Standard_True;
 177   }
 178   return Standard_True;
 179 }
 180
 181
 182 Standard_Boolean IntWalk_IWalking::TestArretPassage
 183   (const TColStd_SequenceOfReal& Umult,
 184    const TColStd_SequenceOfReal& Vmult,
 185    TheIWFunction& sp,
 186    math_Vector& UV,
 187    Standard_Integer& Irang)
 188
 189 // Umult et Vmult : table of stop (or crossing) points on border,
 190 //         here only the crossing points are taken into account.
 191 // UV     : the current point.
 192 // Irang  : at exit : give index of the stop point in uvstart1 or 0.
 193 //          consider that there is no risk of crossing only if there is one crossing point.
 194
 195
 196 // test of stop for an OPEN intersection line
 197 // 1) crossing test on all interior points
 198 // 2) stop test on all start points
 199 // if a stop is detected, the index of the stop point (Irang) is returned
 200 // in the iterator of start points and the associated parameters in UV space.
 201 {
 202   Standard_Real Up, Vp, Du, Dv, Dup, Dvp, Utest,Vtest;
 203   Standard_Integer j, N, ind;
 204   Standard_Real tolu = tolerance(1);
 205   Standard_Real tolv = tolerance(2);
 206   Standard_Real tolu2 = 10.*tolerance(1);
 207   Standard_Real tolv2 = 10.*tolerance(2);
 208
 209   Standard_Boolean Arrive = Standard_False;
 210
 211   // crossing test  on point that can start a loop; mark
 212   // as processed if passes through an open line
 213
 214   if (!reversed) {
 215     previousPoint.ParametersOnS2(Up,Vp);
 216   }
 217   else {
 218     previousPoint.ParametersOnS1(Up,Vp);
 219   }
 220
 221   for (size_t i = 1; i < wd2.size(); i++) {
 222     if (wd2[i].etat > 0) {
 223       // debug jag 05.04.94
 224
 225 //      if ((Up-wd2[i].ustart)*(UV(1)-wd2[i].ustart) +
 226 //        (Vp-wd2[i].vstart)*(UV(2)-wd2[i].vstart) <= 0)
 227       Utest = wd2[i].ustart;
 228       Vtest = wd2[i].vstart;
 229
 230       Du  = UV(1)-Utest;
 231       Dv  = UV(2)-Vtest;
 232       Dup = Up - Utest;
 233       Dvp = Vp - Vtest;
 234
 235 //-- lbr le 30 oct 97
 236
 237       //IFV for OCC20285
 238
 239       if ((Abs(Du) < tolu2 && Abs(Dv) < tolv2) ||
 240           (Abs(Dup) < tolu2 && Abs(Dvp) < tolv2)) {
 241
 242         wd2[i].etat = -wd2[i].etat;
 243       }
 244       else {
 245         Standard_Real DDu = (UV(1)-Up);
 246         Standard_Real DDv = (UV(2)-Vp);
 247         Standard_Real DDD = DDu*DDu+DDv*DDv;
 248         Standard_Real DD1 = Du*Du+Dv*Dv;
 249         if(DD1<=DDD) {
 250           Standard_Real DD2 = Dup*Dup+Dvp*Dvp;
 251           if(DD2<=DDD && ((Du*Dup) + (Dv*Dvp*tolu/tolv) <= 0.)) {
 252             wd2[i].etat = -wd2[i].etat;
 253           }
 254         }
 255       }
 256     }
 257   }
 258
 259   // stop test on point given at input and not yet processed
 260
 261 //  Modified by Sergey KHROMOV - Tue Nov 20 10:55:01 2001 Begin
 262 // Check of all path points in the following order:
 263 //   * First check all not treated points;
 264 //   * After that check of already treated ones.
 265   Standard_Integer l;
 266
 267   //// Modified by jgv, 28.07.2010 for OCC21914 ////
 268   // There are several path points between (Up,Vp) and UV
 269   // So several path points satisfy the condition
 270   // Dup*UV1mUtest + Dvp*UV2mVtest) < 0
 271   // We choose from them the path point with
 272   // minimum distance to (Up,Vp)
 273   TColStd_SequenceOfInteger i_candidates;
 274   TColStd_SequenceOfReal    SqDist_candidates;
 275
 276   for (l = 1; l <= 2 && !Arrive; l++) {
 277     Standard_Boolean isToCheck;
 278
 279     for (size_t i = 1; i < wd1.size(); i++) {
 280       if (l == 1)
 281         isToCheck = (wd1[i].etat > 0);
 282       else
 283         isToCheck = (wd1[i].etat < 0);
 284
 285       if (isToCheck) {
 286 //  Modified by Sergey KHROMOV - Tue Nov 20 11:03:16 2001 End
 287
 288         // debug jag voir avec isg
 289
 290         Utest = wd1[i].ustart;
 291         Vtest = wd1[i].vstart;
 292         Dup = Up - Utest;
 293         Dvp = Vp - Vtest;
 294         if (Abs(Dup) >= tolu || Abs(Dvp) >= tolv) {
 295           Standard_Real UV1mUtest = UV(1)-Utest;
 296           Standard_Real UV2mVtest = UV(2)-Vtest;
 297           if(( (Dup*UV1mUtest + Dvp*UV2mVtest) < 0) ||
 298              (   Abs(UV1mUtest) < tolu
 299               && Abs(UV2mVtest) < tolv)) {
 300             i_candidates.Append((Standard_Integer)i);
 301             SqDist_candidates.Append(Dup*Dup + Dvp*Dvp);
 302             /*
 303             Irang=i;
 304             Arrive = Standard_True;
 305             UV(1) = Utest;
 306             UV(2) = Vtest;
 307             */
 308           }
 309           else if (nbMultiplicities[i] > 0 && i_candidates.IsEmpty()) {
 310             N=0;
 311             for (size_t k = 1; k < i; k++) {
 312               N+=nbMultiplicities[k];
 313             }
 314             for (j = N + 1; j <= N + nbMultiplicities[i]; j++) {
 315               if (((Up-Umult(j))*(UV(1)-Umult(j)) +
 316                    (Vp-Vmult(j))*(UV(2)-Vmult(j)) < 0) ||
 317                   (Abs(UV(1)-Umult(j)) < tolu &&
 318                    Abs(UV(2)-Vmult(j)) < tolv)) {
 319                 Irang=(Standard_Integer)i;
 320                 Arrive = Standard_True;
 321                 UV(1) = Utest;
 322                 UV(2) = Vtest;
 323                 break;
 324               }
 325             }
 326           }
 327           if (Arrive) {
 328             Standard_Real abidF[1], abidD[1][2];
 329             math_Vector bidF(abidF,1,1);
 330             math_Matrix bidD(abidD,1,1,1,2);
 331         sp.Values(UV,bidF,bidD);
 332             break;
 333           }
 334         }
 335       }
 336     } //end of for (i = 1; i < wd1.size(); i++)
 337     if (!i_candidates.IsEmpty())
 338       {
 339         Standard_Real MinSqDist = RealLast();
 340         for (ind = 1; ind <= i_candidates.Length(); ind++)
 341           if (SqDist_candidates(ind) < MinSqDist)
 342             {
 343               MinSqDist = SqDist_candidates(ind);
 344               Irang = i_candidates(ind);
 345             }
 346         Arrive = Standard_True;
 347         UV(1) = wd1[Irang].ustart;
 348         UV(2) = wd1[Irang].vstart;
 349       }
 350   } //end of for (l = 1; l <= 2 && !Arrive; l++)
 351   return  Arrive;
 352 }
 353
 354 Standard_Boolean IntWalk_IWalking::TestArretPassage
 355   (const TColStd_SequenceOfReal& Umult,
 356    const TColStd_SequenceOfReal& Vmult,
 357    const math_Vector& UV,
 358    const Standard_Integer Index,
 359    Standard_Integer& Irang)
 360 {
 361 // Umult, Vmult : table of stop (or crossing) points on border, here
 362 //          only crossing points are taken into account.
 363 // UV     : the current point.
 364 // Index  : index of the start point in uvstart2 of the current line
 365 //          (this is an interior point).
 366 // Irang  : at output : gives the index of the point passing in uvstart1 or 0.
 367 //          consider that there is risk to cross only one crossing point.
 368
 369 // test of stop for a CLOSED intersection line.
 370 // 1) test of crossing on all interior points.
 371 // 2) test of crossing on all crossing points.
 372
 373   Standard_Real Up, Vp, Scal;
 374   Standard_Boolean Arrive = Standard_False;
 375   Standard_Integer N, k, i;
 376   Standard_Real Utest,Vtest;
 377   Standard_Real tolu = tolerance(1);
 378   Standard_Real tolv = tolerance(2);
 379
 380
 381   // tests of stop and of crossing on all interior points.
 382
 383   if (!reversed) {
 384     previousPoint.ParametersOnS2(Up,Vp);
 385   }
 386   else {
 387     previousPoint.ParametersOnS1(Up,Vp);
 388   }
 389
 390   Standard_Real UV1=UV(1);
 391   Standard_Real UV2=UV(2);
 392
 393
 394   //-- Put everything in one box 0 1  x 0 1
 395   //-- actually it is necessary to carry out tests in 3D
 396
 397   Standard_Real deltau=UM-Um;
 398   Standard_Real deltav=VM-Vm;
 399
 400   Up/=deltau; UV1/=deltau;
 401   Vp/=deltav; UV2/=deltav;
 402
 403   tolu/=deltau;
 404   tolv/=deltav;
 405
 406   Standard_Real tolu2=tolu+tolu;
 407   Standard_Real tolv2=tolv+tolv;
 408
 409
 410   Standard_Real dPreviousCurrent = (Up-UV1)*(Up-UV1)+(Vp-UV2)*(Vp-UV2);
 411   for (k = 1; k < (int)wd2.size(); k++) {
 412     if (wd2[k].etat > 0) {
 413       Utest = wd2[k].ustart;
 414       Vtest = wd2[k].vstart;
 415
 416       Utest/=deltau;
 417       Vtest/=deltav;
 418
 419       Standard_Real UV1mUtest=UV1-Utest;
 420       Standard_Real UV2mVtest=UV2-Vtest;
 421       if(   (UV1mUtest<tolu2 && UV1mUtest>-tolu2)
 422          && (UV2mVtest<tolv2 && UV2mVtest>-tolv2)) {
 423         if(Index!=k) {
 424           //-- cout<<"* etat2 : ("<<k<<")"<<endl;
 425           wd2[k].etat=-wd2[k].etat; //-- mark the point as a crossing point
 426         }
 427         else {  //-- Index == k
 428           //-- cout<<"* Arrive"<<endl;
 429           Arrive=Standard_True;
 430         }
 431       }
 432       else {
 433         Standard_Real UpmUtest = (Up-Utest);
 434         Standard_Real VpmVtest = (Vp-Vtest);
 435         Standard_Real dPreviousStart = (UpmUtest)*(UpmUtest)+(VpmVtest)*(VpmVtest);
 436         Standard_Real dCurrentStart  = UV1mUtest * UV1mUtest + UV2mVtest * UV2mVtest;
 437
 438         Scal=(UpmUtest)*(UV1mUtest)+(VpmVtest)*(UV2mVtest);
 439         if( (Abs(UpmUtest)<tolu && Abs(VpmVtest)<tolv)) {
 440           if(Index != k ) {
 441             //-- cout<<"** etat2 : ("<<k<<")"<<endl;
 442             wd2[k].etat = -wd2[k].etat;
 443           }
 444         }
 445         else if(Scal<0 && (dPreviousStart+dCurrentStart < dPreviousCurrent)) {
 446           if (Index == k ) { // on a boucle.
 447             Arrive = Standard_True;
 448             //-- cout<<"** Arrive  : k="<<k<<endl;
 449           }
 450           else {
 451             //-- cout<<"*** etat2 : ("<<k<<")"<<endl;
 452             wd2[k].etat = -wd2[k].etat; // mark the point as a crossing point
 453           }
 454         }
 455         else if(k!=Index) {
 456           if(dPreviousStart < dPreviousCurrent*0.25) {
 457             wd2[k].etat = -wd2[k].etat; // mark the point as a crossing point
 458             //-- cout<<"**** etat2 : ("<<k<<")"<<endl;
 459           }
 460           else {
 461             if(dCurrentStart < dPreviousCurrent*0.25) {
 462               //-- cout<<"***** etat2 : ("<<k<<")"<<endl;
 463               wd2[k].etat = -wd2[k].etat; // mark the point as a crossing point
 464             }
 465             else {
 466               Standard_Real UMidUtest = 0.5*(UV1+Up)-Utest;
 467               Standard_Real VMidVtest = 0.5*(UV2+Vp)-Vtest;
 468               Standard_Real dMiddleStart =  UMidUtest* UMidUtest+VMidVtest*VMidVtest;
 469
 470               if(dMiddleStart < dPreviousCurrent*0.5) {
 471                 //-- cout<<"*********** etat2 : ("<<k<<")"<<endl;
 472                 wd2[k].etat = -wd2[k].etat; // mark the point as a crossing point
 473               }
 474             }
 475           }
 476         }
 477       }
 478     }
 479   }
 480
 481   // crossing test on crossing points.
 482
 483   Irang =0;
 484   for (i = 1; i < (int)wd1.size(); i++) {
 485     if (wd1[i].etat > 0 && wd1[i].etat < 11) { //test of crossing points
 486       Utest = wd1[i].ustart;
 487       Vtest = wd1[i].vstart;
 488       Utest/=deltau;
 489       Vtest/=deltav;
 490
 491       if (((Up-Utest) * (UV1-Utest) + (Vp-Vtest) * (UV2-Vtest) < 0) ||
 492           (Abs(UV1-Utest) < tolu &&  Abs(UV2-Vtest) < tolv))
 493         Irang = i;
 494       else if (nbMultiplicities[i] > 0) {
 495         N=0;
 496         for (k = 1; k < i; k++) N = N + nbMultiplicities[k];
 497         for (Standard_Integer j = N + 1; j <= N + nbMultiplicities[i]; j++) {
 498           Standard_Real Umultj = Umult(j)/deltau;
 499           Standard_Real Vmultj = Vmult(j)/deltav;
 500           if (((Up-Umultj)*(UV1-Umultj) +
 501                (Vp-Vmultj)*(UV2-Vmultj) < 0) ||
 502               (Abs(UV1-Umultj) < tolu &&
 503                Abs(UV2-Vmultj) < tolv)) {
 504             Irang=i;
 505             break;
 506           }
 507         }
 508       }
 509     }
 510   }
 511   return Arrive;
 512 }
 513
 514
 515 Standard_Boolean IntWalk_IWalking::TestArretAjout
 516   (TheIWFunction& sp,
 517    math_Vector& UV,
 518    Standard_Integer& Irang,
 519    IntSurf_PntOn2S& Psol)
 520
 521 // test of stop on added points
 522 // these are the points on the natural biorder that were not given at input
 523 // return : Psol,  the added point.
 524 //          Irang, index in the iterator of added points.
 525 //          UV,    parameter of the added point.
 526 //
 527 {
 528   Standard_Boolean Arrive = Standard_False;
 529   Standard_Real U1,V1;
 530   Standard_Real Up,Vp;
 531
 532   if (!reversed) {
 533     previousPoint.ParametersOnS2(Up,Vp);
 534   }
 535   else {
 536     previousPoint.ParametersOnS1(Up,Vp);
 537   }
 538
 539   Standard_Integer nbAjout = seqAjout.Length();
 540   for (Standard_Integer i = 1; i <= nbAjout; i++) {
 541     Irang = seqAjout.Value(i);
 542
 543 // add test Abs(Irang) <= lines.Length() for the case when
 544 // a closed line is opened by adding a  1 point on this same
 545 // line. Anyway there is a huge problem as 2 points will be
 546 // added on this line...
 547
 548     if (Abs(Irang) <= lines.Length()) {
 549
 550       const Handle(IntWalk_TheIWLine)& Line = lines.Value(Abs(Irang));
 551       if (Irang>0)
 552         Psol = Line->Value(Line->NbPoints());
 553       else
 554         Psol = Line->Value(1);
 555       if (!reversed) {
 556         Psol.ParametersOnS2(U1, V1);
 557       }
 558       else {
 559         Psol.ParametersOnS1(U1, V1);
 560       }
 561       if (((Up-U1) * (UV(1)-U1) +
 562            (Vp-V1) * (UV(2)-V1)) < 0 ||
 563           (Abs(UV(1)-U1) < tolerance(1) &&
 564            Abs(UV(2)-V1) < tolerance(2))) {
 565 //jag 940615    Irang= -Abs(Irang);
 566         Arrive = Standard_True;
 567         UV(1) = U1;
 568         UV(2) = V1;
 569         Standard_Real abidF[1], abidD[1][2];
 570         math_Vector bidF(abidF,1,1);
 571         math_Matrix bidD(abidD,1,1,1,2);
 572     sp.Values(UV,bidF,bidD);
 573         break;
 574       }
 575     }
 576   }
 577   return Arrive;
 578 }
 579
 580 void IntWalk_IWalking::TestArretCadre
 581   (const TColStd_SequenceOfReal& Umult,
 582    const TColStd_SequenceOfReal& Vmult,
 583    const Handle(IntWalk_TheIWLine)& Line,
 584    TheIWFunction& sp,
 585    math_Vector& UV,
 586    Standard_Integer& Irang)
 587
 588 // test of stop when located on border.
 589 // tried all tests of stop and arrived.
 590 // test of stop on all given departure points already marked and on the entire current line.
 591 // This line can be shortened if the stop point is found.
 592 // Abs(Irang) = index in the iterator of departure points or 0
 593 //  if Irang <0 , it is necessary to add this point on the line (no Line->Cut)
 594 // UV = parameter of the departure point
 595 {
 596   Standard_Real Scal, Up, Vp, Uc, Vc;
 597   Standard_Integer N;
 598   Standard_Boolean Found = Standard_False;
 599
 600
 601   Irang =0;
 602   for (Standard_Integer i = 1; i < (int)wd1.size(); i++) {
 603     if (wd1[i].etat < 0) {
 604       N=0; // range in UVMult.
 605       if (nbMultiplicities[i] > 0) {
 606         for (Standard_Integer k = 1; k < i; k++)
 607           N+=nbMultiplicities[k];
 608       }
 609       if (!reversed) {
 610         Line->Value(1).ParametersOnS2(Up,Vp);
 611       }
 612       else {
 613         Line->Value(1).ParametersOnS1(Up,Vp);
 614       }
 615       Standard_Integer nbp= Line->NbPoints();
 616       for (Standard_Integer j = 2; j <= nbp; j++) {
 617         if (!reversed) {
 618           Line->Value(j).ParametersOnS2(Uc,Vc);
 619         }
 620         else {
 621           Line->Value(j).ParametersOnS1(Uc,Vc);
 622         }
 623
 624         Scal = (Up-wd1[i].ustart) * (Uc-wd1[i].ustart) +
 625                (Vp-wd1[i].vstart) * (Vc-wd1[i].vstart);
 626         // if a stop point is found: stop the line on this point.
 627         if (Scal < 0) {
 628           Line->Cut(j);  nbp= Line->NbPoints();
 629           Irang = i;
 630           UV(1) = wd1[Irang].ustart;
 631           UV(2) = wd1[Irang].vstart;
 632           Found = Standard_True;
 633         }
 634         else if (Abs(Uc-wd1[i].ustart) < tolerance(1) &&
 635                  Abs(Vc-wd1[i].vstart) < tolerance(2) ) {
 636           Line->Cut(j);  nbp= Line->NbPoints();
 637           Irang=i;
 638           UV(1) = wd1[Irang].ustart;
 639           UV(2) = wd1[Irang].vstart;
 640           Found = Standard_True;
 641         }
 642         else if (nbMultiplicities[i] > 0) {
 643           for (Standard_Integer k = N+1; k <= N + nbMultiplicities[i]; k++) {
 644             Scal = (Up-Umult(k)) * (Uc-Umult(k)) +
 645                    (Vp-Vmult(k)) * (Vc-Vmult(k));
 646             if (Scal < 0) {
 647               Line->Cut(j);  nbp= Line->NbPoints();
 648               Irang=i;
 649               UV(1) = wd1[Irang].ustart;
 650               UV(2) = wd1[Irang].vstart;
 651               Found = Standard_True;
 652               break;
 653             }
 654             else if (Abs(Uc-Umult(k)) < tolerance(1) &&
 655                      Abs(Vc-Vmult(k)) < tolerance(2)) {
 656               Line->Cut(j);  nbp= Line->NbPoints();
 657               Irang=i;
 658               UV(1) = wd1[Irang].ustart;
 659               UV(2) = wd1[Irang].vstart;
 660               Found = Standard_True;
 661               break;
 662             }
 663           }
 664         }
 665         if (Found) {
 666           Standard_Real abidF[1], abidD[1][2];
 667           math_Vector bidF(abidF,1,1);
 668           math_Matrix bidD(abidD,1,1,1,2);
 669       sp.Values(UV,bidF,bidD);
 670           Standard_Integer NBP =  Line->NbPoints();
 671           Standard_Integer Indextg;
 672           Line->TangentVector(Indextg);
 673           if(Indextg > NBP) {
 674             if(j>3 && j<=NBP+1) {
 675               gp_Vec Dir3d = sp.Direction3d();
 676               gp_Vec Dir3d1 = gp_Vec(Line->Value(j-2).Value(),Line->Value(j-1).Value());
 677               Standard_Real dot = Dir3d.Dot(Dir3d1);
 678               if(dot<0.0) { // Normally this Function should not be used often !!!
 679                 Dir3d.Reverse();
 680                 //-- cout<<" IntWalk_IWalking_2.gxx REVERSE "<<endl;
 681               }
 682               Line->SetTangentVector(previousd3d,j-1);
 683             }
 684 #ifdef DEB
 685             else {
 686               cout<<" IntWalk_IWalking_2.gxx : bizarrerie 30 10 97 "<<endl;
 687             }
 688 #endif
 689           }
 690
 691           return;
 692         }
 693         Up = Uc;
 694         Vp = Vc;
 695       }
 696
 697       // now the last point of the line and the last calculated point are compated.
 698       // there will be no need to "Cut"
 699
 700       Scal = (Up-wd1[i].ustart) * (UV(1)-wd1[i].ustart) +
 701         //      (Vp-wd1[i].vstart) * (UV(2)-wd1[i].vstart);
 702       // modified by NIZHNY-MKK  Fri Oct 27 12:29:41 2000
 703         (Vp-wd1[i].vstart) * (UV(2)-wd1[i].vstart);
 704
 705       if (Scal < 0) {
 706         Irang = i;
 707         UV(1) = wd1[Irang].ustart;
 708         UV(2) = wd1[Irang].vstart;
 709         Found = Standard_True;
 710       }
 711       else if (Abs(UV(1)-wd1[i].ustart) < tolerance(1) &&
 712                Abs(UV(2)-wd1[i].vstart) < tolerance(2)) {
 713         Irang=i;
 714         UV(1) = wd1[Irang].ustart;
 715         UV(2) = wd1[Irang].vstart;
 716         Found = Standard_True;
 717       }
 718       else if (nbMultiplicities[i] > 0) {
 719         for (Standard_Integer j = N+1; j <= N+nbMultiplicities[i]; j++) {
 720           Scal = (Up-Umult(j)) * (UV(1)-Umult(j)) +
 721                  (Vp-Vmult(j)) * (UV(2)-Vmult(j));
 722           if (Scal < 0) {
 723             Irang=i;
 724             UV(1) = wd1[Irang].ustart;
 725             UV(2) = wd1[Irang].vstart;
 726             Found = Standard_True;
 727             break;
 728           }
 729           else if (Abs(UV(1)-Umult(j)) < tolerance(1) &&
 730                    Abs(UV(2)-Vmult(j)) < tolerance(2)) {
 731             Irang=i;
 732             UV(1) = wd1[Irang].ustart;
 733             UV(2) = wd1[Irang].vstart;
 734             Found = Standard_True;
 735             break;
 736           }
 737         }
 738       }
 739       if (Found) {
 740         Irang = -Irang; // jag 941017
 741         Standard_Real abidF[1], abidD[1][2];
 742         math_Vector bidF(abidF,1,1);
 743         math_Matrix bidD(abidD,1,1,1,2);
 744     sp.Values(UV,bidF,bidD);
 745         return;
 746       }
 747     }
 748   }
 749 }
 750
 751