src/IntPatch/IntPatch_PrmPrmIntersection.cxx

   1 // Created on: 1993-02-02
   2 // Created by: Laurent BUCHARD
   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 // modified by Edward AGAPOV (eap) Tue Jan 22 12:29:55 2002
  18 // modified by Oleg FEDYAED  (ofv) Fri Nov 29 16:08:02 2002
  19
  20 #include <Adaptor3d_Surface.hxx>
  21 #include <Adaptor3d_TopolTool.hxx>
  22 #include <gp_Dir.hxx>
  23 #include <gp_Pnt.hxx>
  24 #include <Intf_PIType.hxx>
  25 #include <Intf_SectionLine.hxx>
  26 #include <Intf_SectionPoint.hxx>
  27 #include <Intf_TangentZone.hxx>
  28 #include <IntPatch_InterferencePolyhedron.hxx>
  29 #include <IntPatch_Line.hxx>
  30 #include <IntPatch_Polyhedron.hxx>
  31 #include <IntPatch_PrmPrmIntersection.hxx>
  32 #include <IntPatch_PrmPrmIntersection_T3Bits.hxx>
  33 #include <IntPatch_RstInt.hxx>
  34 #include <IntPatch_WLine.hxx>
  35 #include <IntPolyh_Intersection.hxx>
  36 #include <IntSurf_LineOn2S.hxx>
  37 #include <IntSurf_ListIteratorOfListOfPntOn2S.hxx>
  38 #include <IntSurf_PntOn2S.hxx>
  39 #include <IntWalk_PWalking.hxx>
  40 #include <Standard_OutOfRange.hxx>
  41 #include <StdFail_NotDone.hxx>
  42 #include <TColStd_Array1OfReal.hxx>
  43 #include <TColStd_HArray1OfReal.hxx>
  44 #include <TColStd_SequenceOfInteger.hxx>
  45
  46 static void SectionPointToParameters(const Intf_SectionPoint& Sp,
  47                                      const IntPatch_Polyhedron& Surf1,
  48                                      const IntPatch_Polyhedron& Surf2,
  49                                      Standard_Real& u1,
  50                                      Standard_Real& v1,
  51                                      Standard_Real& u2,
  52                                      Standard_Real& v2);
  53
  54
  55 static
  56 void AdjustOnPeriodic(const Handle(Adaptor3d_Surface)& Surf1,
  57                       const Handle(Adaptor3d_Surface)& Surf2,
  58                       IntPatch_SequenceOfLine& aSLin);
  59
  60 static
  61 IntSurf_PntOn2S MakeNewPoint(const IntSurf_PntOn2S& replacePnt,
  62                              const IntSurf_PntOn2S& oldPnt,
  63                              const Standard_Real* Periods);
  64
  65 static Standard_Boolean IsPointOnLine(const IntSurf_PntOn2S        &thePOn2S,
  66                                       const Handle(IntPatch_WLine) &theWLine,
  67                                       const Standard_Real           Deflection);
  68
  69 static void AddWLine(IntPatch_SequenceOfLine      &theLines,
  70                      const Handle(IntPatch_WLine) &theWLine,
  71                      const Standard_Real           Deflection);
  72
  73 static void SeveralWlinesProcessing(const Handle(Adaptor3d_Surface)& theSurf1,
  74                                     const Handle(Adaptor3d_Surface)& theSurf2,
  75                                     const IntPatch_SequenceOfLine& theSLin,
  76                                     const Standard_Real* const thePeriodsArr,
  77                                     const IntSurf_TypeTrans theTrans1,
  78                                     const IntSurf_TypeTrans theTrans2,
  79                                     const Standard_Real theTol,
  80                                     const Standard_Real theMaxStepS1,
  81                                     const Standard_Real theMaxStepS2,
  82                                     Handle(IntPatch_WLine)& theWLline)
  83 {
  84   if(theSLin.Length() == 0)
  85     return;
  86
  87   Standard_Real aU1 = 0.0, aV1 = 0.0, aU2 = 0.0, aV2 = 0.0;
  88
  89   Standard_Integer cnbV = theWLline->NbVertex();
  90   Standard_Integer ciV;
  91   for( ciV = 1; ciV <= cnbV; ciV++ )
  92   {
  93     Standard_Real pntDMin = 1.e+100;
  94     Standard_Integer VDMin = 0;
  95     Standard_Integer WLDMin = 0;
  96     gp_Pnt cPV = theWLline->Vertex(ciV).Value();
  97     theWLline->Vertex(ciV).Parameters(aU1, aV1, aU2, aV2);
  98     const gp_Pnt2d aPCS1(aU1, aV1), aPCS2(aU2, aV2);
  99     Standard_Integer iL;
 100     for( iL = 1; iL <= theSLin.Length(); iL++)
 101     {
 102       const Handle(IntPatch_Line)& aSLine = theSLin.Value(iL);
 103       IntPatch_IType aType = aSLine->ArcType();
 104       if( aType != IntPatch_Walking)
 105         continue;
 106       const Handle(IntPatch_WLine) aWLine = Handle(IntPatch_WLine)::DownCast(aSLine);
 107       Standard_Integer tnbV = aWLine->NbVertex();
 108       Standard_Integer tiV;
 109       for( tiV = 1; tiV <= tnbV; tiV++ )
 110       {
 111         gp_Pnt tPV = aWLine->Vertex(tiV).Value();
 112
 113         aWLine->Vertex(tiV).Parameters(aU1, aV1, aU2, aV2);
 114         const gp_Pnt2d aPTS1(aU1, aV1), aPTS2(aU2, aV2);
 115
 116         Standard_Real tDistance = cPV.Distance(tPV);
 117         Standard_Real uRs1 = theSurf1->UResolution(tDistance);
 118         Standard_Real vRs1 = theSurf1->VResolution(tDistance);
 119         Standard_Real uRs2 = theSurf2->UResolution(tDistance);
 120         Standard_Real vRs2 = theSurf2->VResolution(tDistance);
 121         Standard_Real RmaxS1 = Max(uRs1,vRs1);
 122         Standard_Real RmaxS2 = Max(uRs2,vRs2);
 123
 124         if(RmaxS1 < theMaxStepS1 && RmaxS2 < theMaxStepS2)
 125         {
 126           if( pntDMin > tDistance && tDistance > Precision::PConfusion())
 127           {
 128             const Standard_Real aSqDist1 = aPCS1.SquareDistance(aPTS1),
 129                                 aSqDist2 = aPCS2.SquareDistance(aPTS2);
 130             if((aSqDist1 < RmaxS1*RmaxS1) && (aSqDist2 < RmaxS2*RmaxS2))
 131             {
 132               pntDMin = tDistance;
 133               VDMin = tiV;
 134               WLDMin = iL;
 135             }
 136           }
 137         }
 138       }
 139     }
 140
 141     if( VDMin != 0 )
 142     {
 143       const Handle(IntPatch_Line)& aSLine = theSLin.Value(WLDMin);
 144       const Handle(IntPatch_WLine) aWLine = Handle(IntPatch_WLine)::DownCast(aSLine);
 145       Standard_Integer tiVpar = (Standard_Integer)aWLine->Vertex(VDMin).ParameterOnLine();
 146       Standard_Integer ciVpar = (Standard_Integer)theWLline->Vertex(ciV).ParameterOnLine();
 147       Standard_Real u11 = 0., u12 = 0., v11 = 0., v12 = 0.;
 148       Standard_Real u21 = 0., u22 = 0., v21 = 0., v22 = 0.;
 149       theWLline->Point(ciVpar).Parameters(u11,v11,u12,v12);
 150       aWLine->Point(tiVpar).Parameters(u21,v21,u22,v22);
 151
 152       Handle(IntSurf_LineOn2S) newL2s = new IntSurf_LineOn2S();
 153       IntSurf_PntOn2S replacePnt = aWLine->Point(tiVpar);
 154       Standard_Integer cNbP = theWLline->NbPnts();
 155
 156       TColStd_SequenceOfInteger VPold;
 157       Standard_Integer iPo;
 158       for( iPo = 1; iPo <= cnbV; iPo++ )
 159       {
 160         Standard_Real Po = theWLline->Vertex(iPo).ParameterOnLine();
 161         Standard_Integer IPo = (Standard_Integer) Po;
 162         VPold.Append(IPo);
 163       }
 164
 165       Standard_Boolean removeNext = Standard_False;
 166       Standard_Boolean removePrev = Standard_False;
 167       if( ciV == 1)
 168       {
 169         Standard_Integer dPar = Abs( VPold.Value(ciV) - VPold.Value(ciV+1));
 170         if(dPar > 10)
 171         {
 172           removeNext = Standard_True;
 173           for( iPo = (ciV+1); iPo <= cnbV; iPo++ )
 174             VPold.SetValue(iPo, VPold.Value(iPo) - 1 );
 175         }
 176       }
 177       else if( ciV == cnbV)
 178       {
 179         Standard_Integer dPar = Abs( VPold.Value(ciV) - VPold.Value(ciV-1));
 180         if(dPar > 10)
 181         {
 182           removePrev = Standard_True;
 183           VPold.SetValue(ciV, VPold.Value(ciV) - 1 );
 184         }
 185       }
 186       else
 187       {
 188         Standard_Integer dParMi = Abs( VPold.Value(ciV) - VPold.Value(ciV-1));
 189         Standard_Integer dParMa = Abs( VPold.Value(ciV) - VPold.Value(ciV+1));
 190         if(dParMi > 10)
 191         {
 192           removePrev = Standard_True;
 193           VPold.SetValue(ciV, VPold.Value(ciV) - 1 );
 194         }
 195
 196         if(dParMa > 10)
 197         {
 198           removeNext = Standard_True;
 199           for( iPo = (ciV+1); iPo <= cnbV; iPo++ )
 200           {
 201             if(dParMi > 10)
 202               VPold.SetValue(iPo, VPold.Value(iPo) - 2 );
 203             else
 204               VPold.SetValue(iPo, VPold.Value(iPo) - 1 );
 205           }
 206         }
 207         else
 208         {
 209           if(dParMi > 10)
 210             for( iPo = (ciV+1); iPo <= cnbV; iPo++ )
 211               VPold.SetValue(iPo, VPold.Value(iPo) - 1 );
 212         }
 213       }
 214
 215       Standard_Integer pI = ciVpar;
 216
 217       Standard_Integer iP;
 218       for( iP = 1; iP <= cNbP; iP++)
 219       {
 220         if( pI == iP )
 221         {
 222           IntSurf_PntOn2S newPnt = MakeNewPoint(replacePnt, theWLline->Point(iP), thePeriodsArr);
 223           newL2s->Add(newPnt);
 224         }
 225         else if(removeNext && iP == (pI + 1))
 226           continue;
 227         else if(removePrev && iP == (pI - 1))
 228           continue;
 229         else
 230           newL2s->Add(theWLline->Point(iP));
 231       }
 232
 233       IntPatch_Point newVtx;
 234       gp_Pnt Pnt3dV = aWLine->Vertex(VDMin).Value();
 235       newVtx.SetValue(Pnt3dV,theTol,Standard_False);
 236       newVtx.SetParameters(u21,v21,u22,v22);
 237       newVtx.SetParameter(VPold.Value(ciV));
 238
 239       Handle(IntPatch_WLine) NWLine = new IntPatch_WLine(newL2s,Standard_False,theTrans1,theTrans2);
 240       NWLine->SetCreatingWayInfo(IntPatch_WLine::IntPatch_WLPrmPrm);
 241
 242       Standard_Integer iV;
 243       for( iV = 1; iV <= cnbV; iV++ )
 244       {
 245         if( iV == ciV )
 246           NWLine->AddVertex(newVtx);
 247         else
 248         {
 249           IntPatch_Point theVtx = theWLline->Vertex(iV);
 250           theVtx.SetParameter(VPold.Value(iV));
 251           NWLine->AddVertex(theVtx);
 252         }
 253       }
 254
 255       theWLline = NWLine;
 256     }//if( VDMin != 0 )
 257   }//for( ciV = 1; ciV <= cnbV; ciV++ )
 258 }
 259
 260 //=======================================================================
 261 //function : DublicateOfLinesProcessing
 262 //purpose  : Decides, if rejecting current line is necessary
 263 //=======================================================================
 264 static void DublicateOfLinesProcessing( const IntWalk_PWalking& thePW,
 265                                         const Standard_Integer theWLID,
 266                                         IntPatch_SequenceOfLine& theLines,
 267                                         Standard_Boolean& theIsRejectReq)
 268 {
 269   const Handle(IntPatch_WLine)& anExistWL =
 270                       *((Handle(IntPatch_WLine)*)&theLines.Value(theWLID));
 271   const Standard_Integer aNbPrevPoints = anExistWL->NbPnts();
 272   const Standard_Integer aNbCurrPoints = thePW.NbPoints();
 273
 274   if(aNbPrevPoints < aNbCurrPoints)
 275   {//Remove preview line
 276     theLines.Remove(theWLID);
 277     theIsRejectReq = Standard_False;
 278   }
 279   else if(aNbPrevPoints == aNbCurrPoints)
 280   {
 281     Standard_Real aLPrev = 0.0, aLCurr = 0.0;
 282     for(Standard_Integer aNbPP = 1; aNbPP < aNbPrevPoints; aNbPP++)
 283     {
 284       const gp_Pnt  aP1prev(anExistWL->Point(aNbPP).Value()),
 285         aP2prev(anExistWL->Point(aNbPP+1).Value());
 286       const gp_Pnt  aP1curr(thePW.Value(aNbPP).Value()),
 287         aP2curr(thePW.Value(aNbPP+1).Value());
 288
 289       aLPrev += aP1prev.Distance(aP2prev);
 290       aLCurr += aP1curr.Distance(aP2curr);
 291     }
 292
 293     if(aLPrev < aLCurr)
 294     {//Remove preview line
 295       theLines.Remove(theWLID);
 296       theIsRejectReq = Standard_False;
 297     }
 298   }
 299 }
 300
 301 //==================================================================================
 302 // function :
 303 // purpose  :
 304 //==================================================================================
 305 IntPatch_PrmPrmIntersection::IntPatch_PrmPrmIntersection()
 306 : done(Standard_False),
 307   empt(Standard_True)
 308 {
 309 }
 310
 311 //==================================================================================
 312 // function : Perform
 313 // purpose  :
 314 //==================================================================================
 315 void IntPatch_PrmPrmIntersection::Perform (const Handle(Adaptor3d_Surface)&   Surf1,
 316                                            const Handle(Adaptor3d_TopolTool)& D1,
 317                                            const Standard_Real  TolTangency,
 318                                            const Standard_Real  Epsilon,
 319                                            const Standard_Real  Deflection,
 320                                            const Standard_Real  Increment)
 321 {
 322   IntPatch_Polyhedron Poly1( Surf1, D1->NbSamplesU(), D1->NbSamplesV() );
 323   Perform( Surf1, Poly1, D1, TolTangency, Epsilon, Deflection, Increment );
 324 }
 325
 326 //==================================================================================
 327 // function : Perform
 328 // purpose  :
 329 //==================================================================================
 330 void IntPatch_PrmPrmIntersection::Perform (const Handle(Adaptor3d_Surface)&   Surf1,
 331                                            const IntPatch_Polyhedron& Poly1,
 332                                            const Handle(Adaptor3d_TopolTool)& D1,
 333                                            const Handle(Adaptor3d_Surface)&   Surf2,
 334                                            const Handle(Adaptor3d_TopolTool)& D2,
 335                                            const Standard_Real  TolTangency,
 336                                            const Standard_Real  Epsilon,
 337                                            const Standard_Real  Deflection,
 338                                            const Standard_Real  Increment)
 339 {
 340   IntPatch_Polyhedron Poly2( Surf2 );
 341   Perform( Surf1, Poly1, D1, Surf2, Poly2, D2, TolTangency, Epsilon, Deflection, Increment);
 342 }
 343
 344 //==================================================================================
 345 // function : Perform
 346 // purpose  :
 347 //==================================================================================
 348 void IntPatch_PrmPrmIntersection::Perform (const Handle(Adaptor3d_Surface)&   Surf1,
 349                                            const Handle(Adaptor3d_TopolTool)& D1,
 350                                            const Handle(Adaptor3d_Surface)&   Surf2,
 351                                            const IntPatch_Polyhedron& Poly2,
 352                                            const Handle(Adaptor3d_TopolTool)& D2,
 353                                            const Standard_Real  TolTangency,
 354                                            const Standard_Real  Epsilon,
 355                                            const Standard_Real  Deflection,
 356                                            const Standard_Real  Increment)
 357 {
 358   IntPatch_Polyhedron Poly1( Surf1 );
 359   Perform( Surf1, Poly1, D1, Surf2, Poly2, D2, TolTangency, Epsilon, Deflection, Increment );
 360 }
 361
 362 //==================================================================================
 363 // function : Perform
 364 // purpose  :
 365 //==================================================================================
 366 void IntPatch_PrmPrmIntersection::Perform (const Handle(Adaptor3d_Surface)&    Surf1,
 367                                            const IntPatch_Polyhedron&  Poly1,
 368                                            const Handle(Adaptor3d_TopolTool)& D1,
 369                                            const Handle(Adaptor3d_Surface)&    Surf2,
 370                                            const IntPatch_Polyhedron&  Poly2,
 371                                            const Handle(Adaptor3d_TopolTool)& D2,
 372                                            const Standard_Real   TolTangency,
 373                                            const Standard_Real   Epsilon,
 374                                            const Standard_Real   Deflection,
 375                                            const Standard_Real   Increment)
 376 {
 377   IntPatch_InterferencePolyhedron Interference(Poly1,Poly2);
 378   empt = Standard_True;
 379   done = Standard_True;
 380   SLin.Clear();
 381
 382   Standard_Integer nbLigSec = Interference.NbSectionLines();
 383   Standard_Integer nbTanZon = Interference.NbTangentZones();
 384
 385   Standard_Integer NbLigCalculee = 0;
 386
 387   Standard_Real U1,U2,V1,V2;
 388   Standard_Real pu1,pu2,pv1,pv2;
 389
 390   TColStd_Array1OfReal StartParams(1,4);
 391
 392   IntWalk_PWalking PW( Surf1, Surf2, TolTangency, Epsilon, Deflection, Increment );
 393
 394   Standard_Real    SeuildPointLigne = 15.0 * Increment * Increment; //-- 10 est insuffisant
 395   Standard_Real    incidence;
 396   Standard_Real    dminiPointLigne;
 397
 398   Standard_Boolean HasStartPoint,RejetLigne;
 399
 400   IntSurf_PntOn2S StartPOn2S;
 401
 402   Standard_Integer ver;
 403
 404   gp_Pnt Point3dDebut,Point3dFin;
 405
 406   if( nbLigSec >= 1 ) {
 407     Standard_Integer *TabL = new Standard_Integer [nbLigSec+1];
 408     Standard_Integer ls;
 409     for( ls = 1; ls <= nbLigSec; ls++ )
 410       TabL[ls]=ls;
 411
 412     Standard_Boolean triok;
 413     do {
 414       triok=Standard_True;
 415       for(Standard_Integer b=2; b<=nbLigSec; b++) {
 416         Standard_Integer nb_B = Interference.LineValue(TabL[b]).NumberOfPoints();
 417         Standard_Integer nb_A = Interference.LineValue(TabL[b-1]).NumberOfPoints();
 418         if( nb_B > nb_A ) {
 419           Standard_Integer tyu=TabL[b];
 420           TabL[b]=TabL[b-1];
 421           TabL[b-1]=tyu;
 422           triok=Standard_False;
 423         }
 424       }
 425     } while( triok==Standard_False );
 426
 427     for( ls = 1; ls <= nbLigSec; ls++) {
 428       const Intf_SectionLine& LineSec=Interference.LineValue(TabL[ls]);
 429       Standard_Integer nbp = LineSec.NumberOfPoints();
 430
 431       Standard_Integer *TabPtDep = new Standard_Integer [nbp+1];
 432       Standard_Integer ilig;
 433       for( ilig = 1; ilig <= nbp; ilig++)
 434         TabPtDep[ilig]=0;
 435
 436       Standard_Real UminLig1,VminLig1,UmaxLig1,VmaxLig1;
 437       Standard_Real UminLig2,VminLig2,UmaxLig2,VmaxLig2;
 438
 439       SectionPointToParameters(LineSec.GetPoint(1),Poly1,Poly2,UminLig1,VminLig1,UminLig2,VminLig2);
 440
 441       UmaxLig1=UminLig1;
 442       VmaxLig1=VminLig1;
 443       UmaxLig2=UminLig2;
 444       VmaxLig2=VminLig2;
 445
 446       for( ilig = 2; ilig <= nbp; ilig++ ) {
 447         SectionPointToParameters(LineSec.GetPoint(ilig),Poly1,Poly2,U1,V1,U2,V2);
 448
 449         if(U1>UmaxLig1) UmaxLig1=U1;
 450         if(V1>VmaxLig1) VmaxLig1=V1;
 451         if(U2>UmaxLig2) UmaxLig2=U2;
 452         if(V2>VmaxLig2) VmaxLig2=V2;
 453
 454         if(U1<UminLig1) UminLig1=U1;
 455         if(V1<VminLig1) VminLig1=V1;
 456         if(U2<UminLig2) UminLig2=U2;
 457         if(V2<VminLig2) VminLig2=V2;
 458       }
 459
 460       Standard_Integer nbps2 = (nbp>3)? (nbp/2) :  1;
 461       Standard_Integer NombreDePointsDeDepartDuCheminement = 0;
 462       Standard_Integer IndicePointdeDepart1 = 0,IndicePointdeDepart2 = 0;
 463       Standard_Boolean lignetrouvee=Standard_False;
 464
 465       do {
 466         NombreDePointsDeDepartDuCheminement++;
 467         if(NombreDePointsDeDepartDuCheminement == 1) {
 468           incidence=3.0;
 469           Standard_Integer nbp1_4=nbp/4;
 470           Standard_Integer nbp3_4=nbp-nbp1_4;
 471
 472           Standard_Integer nsp;
 473           for(nsp=nbp/2; nsp<nbp3_4; nsp++) {
 474             Standard_Real CurrentIncidence =  LineSec.GetPoint(nsp).Incidence();
 475             if(CurrentIncidence < incidence) {
 476               nbps2 = nsp;
 477               incidence = 0.9*CurrentIncidence;
 478             }
 479           }
 480
 481           for(nsp=nbp/2; nsp>nbp1_4; nsp--) {
 482             Standard_Real CurrentIncidence =  LineSec.GetPoint(nsp).Incidence();
 483             if(CurrentIncidence < incidence) {
 484               nbps2 = nsp;
 485               incidence = 0.9*CurrentIncidence;
 486             }
 487           }
 488
 489           if(nbp<3)
 490             NombreDePointsDeDepartDuCheminement=3;
 491
 492           IndicePointdeDepart1 = nbps2;
 493         }
 494         else if(NombreDePointsDeDepartDuCheminement == 2) {
 495           if(IndicePointdeDepart1 == 1) {
 496             nbps2 = nbp/2;
 497             IndicePointdeDepart2 = nbps2;
 498           }
 499           else {
 500             nbps2 = 1;
 501             IndicePointdeDepart2 = 1;
 502           }
 503         }
 504         else if(NombreDePointsDeDepartDuCheminement == 3) {
 505           if(IndicePointdeDepart1 == nbp)
 506             nbps2 = (IndicePointdeDepart1+IndicePointdeDepart2)/2;
 507           else
 508             nbps2 = nbp;
 509         }
 510         else {
 511           nbps2 = NombreDePointsDeDepartDuCheminement-3;
 512           NombreDePointsDeDepartDuCheminement++;
 513         }
 514
 515         if(TabPtDep[nbps2]==0) {
 516           TabPtDep[nbps2]=1;
 517           SectionPointToParameters(LineSec.GetPoint(nbps2),Poly1,Poly2,U1,V1,U2,V2);
 518
 519           StartParams(1) = U1;
 520           StartParams(2) = V1;
 521           StartParams(3) = U2;
 522           StartParams(4) = V2;
 523
 524           HasStartPoint = PW.PerformFirstPoint(StartParams,StartPOn2S);
 525           dminiPointLigne = SeuildPointLigne + SeuildPointLigne;
 526
 527           if(HasStartPoint) {
 528             StartPOn2S.Parameters(pu1,pv1,pu2,pv2);
 529             NbLigCalculee = SLin.Length();
 530             Standard_Integer l;
 531             for( l=1; (l <= NbLigCalculee) && (dminiPointLigne >= SeuildPointLigne); l++) {
 532               const Handle(IntPatch_WLine)& testwline = *((Handle(IntPatch_WLine)*)&SLin.Value(l));
 533
 534               if (IsPointOnLine(StartPOn2S, testwline, Deflection)) {
 535                 dminiPointLigne = 0.0;
 536               }
 537             } // for ( l ...
 538
 539             if(dminiPointLigne > SeuildPointLigne) {
 540               PW.Perform(StartParams,UminLig1,VminLig1,UminLig2,VminLig2,UmaxLig1,VmaxLig1,UmaxLig2,VmaxLig2);
 541               if(PW.IsDone()) {
 542                 if(PW.NbPoints()>2) {
 543                   RejetLigne = Standard_False;
 544                   Point3dDebut = PW.Value(1).Value();
 545                   const IntSurf_PntOn2S& PointFin = PW.Value(PW.NbPoints());
 546                   Point3dFin   = PointFin.Value();
 547                   for( ver = 1 ; ver<= NbLigCalculee ; ver++) {
 548                     const Handle(IntPatch_WLine)& verwline = *((Handle(IntPatch_WLine)*)&SLin.Value(ver));
 549
 550                     // Check end point if it is on existing line.
 551                     // Start point is checked before.
 552                     if (IsPointOnLine(PointFin, verwline, Deflection)) {
 553                       RejetLigne = Standard_True;
 554                       break;
 555                     }
 556
 557                     const IntSurf_PntOn2S& verPointDebut = verwline->Point(1);
 558                     const IntSurf_PntOn2S& verPointFin = verwline->Point(verwline->NbPnts());
 559                     if( (Point3dDebut.Distance(verPointDebut.Value()) <= TolTangency) &&
 560                         (Point3dFin.Distance(verPointFin.Value()) <= TolTangency))
 561                     {
 562                       RejetLigne = Standard_True;
 563                       break;
 564                     }
 565                   }
 566
 567                   if(RejetLigne)
 568                   {
 569                     DublicateOfLinesProcessing(PW, ver, SLin, RejetLigne);
 570                   }
 571
 572                   if(!RejetLigne) {
 573                     // Calculation transition
 574                     IntSurf_TypeTrans trans1,trans2;
 575                     Standard_Real locu,locv;
 576                     gp_Vec norm1,norm2,d1u,d1v;
 577                     gp_Pnt ptbid;
 578                     Standard_Integer indextg;
 579                     gp_Vec tgline(PW.TangentAtLine(indextg));
 580                     PW.Line()->Value(indextg).ParametersOnS1(locu,locv);
 581                     Surf1->D1(locu,locv,ptbid,d1u,d1v);
 582                     norm1 = d1u.Crossed(d1v);
 583                     PW.Line()->Value(indextg).ParametersOnS2(locu,locv);
 584                     Surf2->D1(locu,locv,ptbid,d1u,d1v);
 585                     norm2 = d1u.Crossed(d1v);
 586                     if(tgline.DotCross(norm2,norm1)>0.) {
 587                       trans1 = IntSurf_Out;
 588                       trans2 = IntSurf_In;
 589                     }
 590                     else {
 591                       trans1 = IntSurf_In;
 592                       trans2 = IntSurf_Out;
 593                     }
 594
 595                     Standard_Real TolTang = TolTangency;
 596                     Handle(IntPatch_WLine) wline = new IntPatch_WLine(PW.Line(),Standard_False,trans1,trans2);
 597                     wline->SetCreatingWayInfo(IntPatch_WLine::IntPatch_WLPrmPrm);
 598
 599                     //the method PutVertexOnLine can reduce the number of points in <wline>
 600                     IntPatch_RstInt::PutVertexOnLine(wline,Surf1,D1,Surf2,Standard_True,TolTang);
 601                     if (wline->NbPnts() < 2)
 602                       continue;
 603                     IntPatch_RstInt::PutVertexOnLine(wline,Surf2,D2,Surf1,Standard_False,TolTang);
 604                     if (wline->NbPnts() < 2)
 605                       continue;
 606
 607                     if(wline->NbVertex() == 0) {
 608                       IntPatch_Point vtx;
 609                       IntSurf_PntOn2S POn2S = PW.Line()->Value(1);
 610                       POn2S.Parameters(pu1,pv1,pu2,pv2);
 611                       vtx.SetValue(Point3dDebut,TolTang,Standard_False);
 612                       vtx.SetParameters(pu1,pv1,pu2,pv2);
 613                       vtx.SetParameter(1);
 614                       wline->AddVertex(vtx);
 615
 616                       POn2S = PW.Line()->Value(wline->NbPnts());
 617                       POn2S.Parameters(pu1,pv1,pu2,pv2);
 618                       vtx.SetValue(Point3dFin,TolTang,Standard_False);
 619                       vtx.SetParameters(pu1,pv1,pu2,pv2);
 620                       vtx.SetParameter(wline->NbPnts());
 621                       wline->AddVertex(vtx);
 622                     }
 623
 624                     lignetrouvee = Standard_True;
 625                     AddWLine(SLin, wline, Deflection);
 626                     empt = Standard_False;
 627                   }// !RejetLigne
 628                 }// PW.NbPoints()>2
 629               }// done is True
 630             }// dminiPointLigne > SeuildPointLigne
 631           }// HasStartPoint
 632         }// TabPtDep[nbps2]==0
 633       } while( nbp>5 && ( !( ( (NombreDePointsDeDepartDuCheminement >= 3) && lignetrouvee ) ||
 634         ( (NombreDePointsDeDepartDuCheminement-3>=nbp) && !lignetrouvee ) ) ) );
 635
 636       delete [] TabPtDep;
 637     }// for( ls ...
 638
 639     delete [] TabL;
 640   }// nbLigSec >= 1
 641
 642   Standard_Real UminLig1,VminLig1,UmaxLig1,VmaxLig1;
 643   Standard_Real UminLig2,VminLig2,UmaxLig2,VmaxLig2;
 644
 645   UminLig1=VminLig1=UminLig2=VminLig2=RealLast();
 646   UmaxLig1=VmaxLig1=UmaxLig2=VmaxLig2=-UminLig1;
 647
 648   Standard_Integer z;
 649   for(z=1; z <= nbTanZon; z++) {
 650     const Intf_TangentZone& TangentZone=Interference.ZoneValue(z);
 651     for(Standard_Integer pz=1; pz<=TangentZone.NumberOfPoints(); pz++) {
 652       SectionPointToParameters(TangentZone.GetPoint(pz),Poly1,Poly2,U1,V1,U2,V2);
 653
 654       if(U1>UmaxLig1) UmaxLig1=U1;
 655       if(V1>VmaxLig1) VmaxLig1=V1;
 656       if(U2>UmaxLig2) UmaxLig2=U2;
 657       if(V2>VmaxLig2) VmaxLig2=V2;
 658
 659       if(U1<UminLig1) UminLig1=U1;
 660       if(V1<VminLig1) VminLig1=V1;
 661       if(U2<UminLig2) UminLig2=U2;
 662       if(V2<VminLig2) VminLig2=V2;
 663     }
 664   }
 665
 666   for(z=1; z <= nbTanZon; z++) {
 667     const Intf_TangentZone& TangentZone=Interference.ZoneValue(z);
 668     Standard_Integer pz;
 669     for( pz=1; pz<=TangentZone.NumberOfPoints(); pz++) {
 670       SectionPointToParameters(TangentZone.GetPoint(pz),Poly1,Poly2,U1,V1,U2,V2);
 671
 672       StartParams(1) = U1;
 673       StartParams(2) = V1;
 674       StartParams(3) = U2;
 675       StartParams(4) = V2;
 676
 677       HasStartPoint = PW.PerformFirstPoint(StartParams,StartPOn2S);
 678       if(HasStartPoint) {
 679         StartPOn2S.Parameters(pu1,pv1,pu2,pv2);
 680         NbLigCalculee = SLin.Length();
 681         dminiPointLigne = SeuildPointLigne + SeuildPointLigne;
 682         Standard_Integer l;
 683         for( l = 1; (l <= NbLigCalculee) && (dminiPointLigne >= SeuildPointLigne); l++) {
 684           const Handle(IntPatch_WLine)& testwline = *((Handle(IntPatch_WLine)*)&SLin.Value(l));
 685
 686           if (IsPointOnLine(StartPOn2S, testwline, Deflection)) {
 687             dminiPointLigne = 0.0;
 688           }
 689         }// for( l ...
 690
 691         if(dminiPointLigne > SeuildPointLigne) {
 692           PW.Perform(StartParams,UminLig1,VminLig1,UminLig2,VminLig2,UmaxLig1,VmaxLig1,UmaxLig2,VmaxLig2);
 693           if(PW.IsDone()) {
 694             if(PW.NbPoints()>2) {
 695               RejetLigne = Standard_False;
 696               Point3dDebut = PW.Value(1).Value();
 697               const IntSurf_PntOn2S& PointFin = PW.Value(PW.NbPoints());
 698               Point3dFin   = PointFin.Value();
 699               for(ver=1 ; ver<= NbLigCalculee ; ver++) {
 700                 const Handle(IntPatch_WLine)& verwline = *((Handle(IntPatch_WLine)*)&SLin.Value(ver));
 701
 702                 // Check end point if it is on existing line.
 703                 // Start point is checked before.
 704                 if (IsPointOnLine(PointFin, verwline, Deflection)) {
 705                   RejetLigne = Standard_True;
 706                   break;
 707                 }
 708
 709                 const IntSurf_PntOn2S& verPointDebut = verwline->Point(1);
 710                 const IntSurf_PntOn2S& verPointFin   = verwline->Point(verwline->NbPnts());
 711                 if( (Point3dDebut.Distance(verPointDebut.Value()) < TolTangency) ||
 712                     (Point3dFin.Distance(verPointFin.Value()) < TolTangency))
 713                 {
 714                   RejetLigne = Standard_True;
 715                   break;
 716                 }
 717               }
 718
 719               if(RejetLigne)
 720               {
 721                 DublicateOfLinesProcessing(PW, ver, SLin, RejetLigne);
 722               }
 723
 724               if(!RejetLigne) {
 725                 IntSurf_TypeTrans trans1,trans2;
 726                 Standard_Real locu,locv;
 727                 gp_Vec norm1,norm2,d1u,d1v;
 728                 gp_Pnt ptbid;
 729                 Standard_Integer indextg;
 730                 gp_Vec tgline(PW.TangentAtLine(indextg));
 731                 PW.Line()->Value(indextg).ParametersOnS1(locu,locv);
 732                 Surf1->D1(locu,locv,ptbid,d1u,d1v);
 733                 norm1 = d1u.Crossed(d1v);
 734                 PW.Line()->Value(indextg).ParametersOnS2(locu,locv);
 735                 Surf2->D1(locu,locv,ptbid,d1u,d1v);
 736                 norm2 = d1u.Crossed(d1v);
 737                 if(tgline.DotCross(norm2,norm1)>0.) {
 738                   trans1 = IntSurf_Out;
 739                   trans2 = IntSurf_In;
 740                 }
 741                 else {
 742                   trans1 = IntSurf_In;
 743                   trans2 = IntSurf_Out;
 744                 }
 745
 746                 Standard_Real TolTang = TolTangency;
 747                 Handle(IntPatch_WLine) wline = new IntPatch_WLine(PW.Line(),Standard_False,trans1,trans2);
 748                 wline->SetCreatingWayInfo(IntPatch_WLine::IntPatch_WLPrmPrm);
 749
 750                 //the method PutVertexOnLine can reduce the number of points in <wline>
 751                 IntPatch_RstInt::PutVertexOnLine(wline,Surf1,D1,Surf2,Standard_True,TolTang);
 752                 if (wline->NbPnts() < 2)
 753                   continue;
 754                 IntPatch_RstInt::PutVertexOnLine(wline,Surf2,D2,Surf1,Standard_False,TolTang);
 755                 if (wline->NbPnts() < 2)
 756                   continue;
 757
 758                 if(wline->NbVertex() == 0) {
 759                   IntPatch_Point vtx;
 760                   IntSurf_PntOn2S POn2S = PW.Line()->Value(1);
 761                   POn2S.Parameters(pu1,pv1,pu2,pv2);
 762                   vtx.SetValue(Point3dDebut,TolTang,Standard_False);
 763                   vtx.SetParameters(pu1,pv1,pu2,pv2);
 764                   vtx.SetParameter(1);
 765                   wline->AddVertex(vtx);
 766
 767                   POn2S = PW.Line()->Value(wline->NbPnts());
 768                   POn2S.Parameters(pu1,pv1,pu2,pv2);
 769                   vtx.SetValue(Point3dFin,TolTang,Standard_False);
 770                   vtx.SetParameters(pu1,pv1,pu2,pv2);
 771                   vtx.SetParameter(wline->NbPnts());
 772                   wline->AddVertex(vtx);
 773                 }
 774
 775                 AddWLine(SLin, wline, Deflection);
 776                 empt = Standard_False;
 777               }// if !RejetLigne
 778             }// PW.NbPoints()>2
 779           }// done is True
 780         }// dminiPointLigne > SeuildPointLigne
 781       }// HasStartPoint
 782     }// for( pz ...
 783   }// for( z ...
 784 }
 785
 786 //==================================================================================
 787 // function : Perform
 788 // purpose  :
 789 //==================================================================================
 790 void IntPatch_PrmPrmIntersection::Perform (const Handle(Adaptor3d_Surface)&    Surf1,
 791                                            const IntPatch_Polyhedron&  Poly1,
 792                                            const Handle(Adaptor3d_TopolTool)& D1,
 793                                            const Standard_Real   TolTangency,
 794                                            const Standard_Real   Epsilon,
 795                                            const Standard_Real   Deflection,
 796                                            const Standard_Real   Increment)
 797 {
 798   IntPatch_InterferencePolyhedron Interference(Poly1);
 799   empt = Standard_True;
 800   done = Standard_True;
 801   SLin.Clear();
 802
 803   Standard_Integer nbLigSec = Interference.NbSectionLines();
 804   Standard_Integer nbTanZon = Interference.NbTangentZones();
 805
 806   Standard_Integer NbPntOn2SOnLine;
 807   Standard_Integer NbLigCalculee = 0;
 808
 809   Standard_Real U1,U2,V1,V2;
 810   Standard_Real pu1,pu2,pv1,pv2;
 811
 812   TColStd_Array1OfReal StartParams(1,4);
 813   IntWalk_PWalking PW(Surf1,Surf1,TolTangency,Epsilon,Deflection,Increment);
 814
 815   Standard_Real    SeuildPointLigne = 15.0 * Increment * Increment; //-- 10 est insuffisant
 816   Standard_Real    incidence;
 817   Standard_Real    dminiPointLigne;
 818
 819   Standard_Boolean HasStartPoint,RejetLigne;
 820
 821   IntSurf_PntOn2S StartPOn2S;
 822
 823   Standard_Integer ver;
 824
 825   gp_Pnt Point3dDebut,Point3dFin;
 826
 827   if(nbLigSec>=1) {
 828     Standard_Integer ls;
 829     for( ls = 1; ls <= nbLigSec; ls++) {
 830       const Intf_SectionLine& LineSec=Interference.LineValue(ls);
 831       Standard_Integer nbp = LineSec.NumberOfPoints();
 832       Standard_Integer nbps2 = (nbp>3)? (nbp/2) :  1;
 833       Standard_Integer NombreDePointsDeDepartDuCheminement = 0;
 834       Standard_Integer IndicePointdeDepart1 = 0, IndicePointdeDepart2 = 0;
 835       do {
 836         NombreDePointsDeDepartDuCheminement++;
 837         if(NombreDePointsDeDepartDuCheminement == 1) {
 838           incidence = 0.0;
 839           Standard_Integer nsp1;
 840           for( nsp1= nbp/2; nsp1 >= 1; nsp1--) {
 841             SectionPointToParameters(LineSec.GetPoint(nsp1),Poly1,Poly1,U1,V1,U2,V2);
 842             Standard_Real CurrentIncidence =  Abs(U1-U2)+Abs(V1-V2);
 843             if(CurrentIncidence > incidence) {
 844               nbps2 = nsp1;
 845               incidence = CurrentIncidence;
 846             }
 847           }
 848           for( nsp1 = nbp/2; nsp1 <= nbp; nsp1++) {
 849             SectionPointToParameters(LineSec.GetPoint(nsp1),Poly1,Poly1,U1,V1,U2,V2);
 850             Standard_Real CurrentIncidence =  Abs(U1-U2)+Abs(V1-V2);
 851             if(CurrentIncidence > incidence) {
 852               nbps2 = nsp1;
 853               incidence = CurrentIncidence;
 854             }
 855           }
 856
 857           if(nbp<3)
 858             NombreDePointsDeDepartDuCheminement=3;
 859
 860           IndicePointdeDepart1 = nbps2;
 861         }
 862         else if(NombreDePointsDeDepartDuCheminement == 2) {
 863           if(IndicePointdeDepart1 == 1) {
 864             nbps2 = nbp/2;
 865             IndicePointdeDepart2 = nbps2;
 866           }
 867           else {
 868             nbps2 = 1;
 869             IndicePointdeDepart2 = 1;
 870           }
 871         }
 872         else {
 873           if(IndicePointdeDepart1 == nbp)
 874             nbps2 = (IndicePointdeDepart1+IndicePointdeDepart2)/2;
 875           else
 876             nbps2 = nbp;
 877         }
 878
 879         SectionPointToParameters(LineSec.GetPoint(nbps2),Poly1,Poly1,U1,V1,U2,V2);
 880
 881         StartParams(1) = U1;
 882         StartParams(2) = V1;
 883         StartParams(3) = U2;
 884         StartParams(4) = V2;
 885
 886         HasStartPoint = PW.PerformFirstPoint(StartParams,StartPOn2S);
 887         dminiPointLigne = SeuildPointLigne + SeuildPointLigne;
 888         if(HasStartPoint) {
 889           StartPOn2S.Parameters(pu1,pv1,pu2,pv2);
 890           if(Abs(pu1-pu2)>1e-7 || Abs(pv1-pv2)>1e-7) {
 891             NbLigCalculee = SLin.Length();
 892             Standard_Integer l;
 893             for( l = 1; (l <= NbLigCalculee) && (dminiPointLigne >= SeuildPointLigne); l++) {
 894               const Handle(IntPatch_WLine)& testwline = *((Handle(IntPatch_WLine)*)&SLin.Value(l));
 895               if( (testwline->IsOutSurf1Box(gp_Pnt2d(pu1,pv1))==Standard_False) &&
 896                 (testwline->IsOutSurf2Box(gp_Pnt2d(pu2,pv2))==Standard_False) &&
 897                 (testwline->IsOutBox(StartPOn2S.Value())==Standard_False) ) {
 898                   NbPntOn2SOnLine = testwline->NbPnts();
 899                   Standard_Integer ll;
 900                   for( ll=1; (ll < NbPntOn2SOnLine) && (dminiPointLigne >= SeuildPointLigne); ll++) {
 901                     Standard_Real t,Au1,Av1,Au2,Av2,Bu1,Bv1,Bu2,Bv2;
 902                     testwline->Point(ll).Parameters(Au1,Av1,Au2,Av2);
 903                     testwline->Point(ll+1).Parameters(Bu1,Bv1,Bu2,Bv2);
 904                     if(Au1>Bu1) {
 905                       t=Au1;
 906                       Au1=Bu1;
 907                       Bu1=t;
 908                     }
 909                     if(Av1>Bv1) {
 910                       t=Av1;
 911                       Av1=Bv1;
 912                       Bv1=t;
 913                     }
 914                     Au1-=1.0e-7;
 915                     Av1-=1.0e-7;
 916                     Bu1+=1.0e-7;
 917                     Bv1+=1.0e-7;
 918
 919                     if((pu1>=Au1) && (pu1<=Bu1) && (pv1>=Av1) && (pv1<=Bv1))
 920                       dminiPointLigne = 0.0;
 921                     else {
 922                       if((pu2>=Au1) && (pu2<=Bu1) && (pv2>=Av1) && (pv2<=Bv1))
 923                         dminiPointLigne = 0.0;
 924                     }
 925                   }// for( ll ...
 926               }// if ...
 927             }// for( l ...
 928
 929             if(dminiPointLigne > SeuildPointLigne) {
 930               PW.Perform(StartParams);
 931               if(PW.IsDone()) {
 932                 if(PW.NbPoints()>2) {
 933                   RejetLigne = Standard_False;
 934                   Point3dDebut = PW.Value(1).Value();
 935                   Point3dFin   = PW.Value(PW.NbPoints()).Value();
 936                   for(ver=1 ; ver<= NbLigCalculee ; ver++) {
 937                     const Handle(IntPatch_WLine)& verwline = *((Handle(IntPatch_WLine)*)&SLin.Value(ver));
 938                     const IntSurf_PntOn2S& verPointDebut = verwline->Point(1);
 939                     const IntSurf_PntOn2S& verPointFin = verwline->Point(verwline->NbPnts());
 940                     if( (Point3dDebut.Distance(verPointDebut.Value()) < TolTangency) ||
 941                         (Point3dFin.Distance(verPointFin.Value()) < TolTangency))
 942                     {
 943                       RejetLigne = Standard_True;
 944                       break;
 945                     }
 946                   }
 947
 948                   if(RejetLigne)
 949                   {
 950                     DublicateOfLinesProcessing(PW, ver, SLin, RejetLigne);
 951                   }
 952
 953                   if(!RejetLigne) {
 954                     IntSurf_TypeTrans trans1,trans2;
 955                     Standard_Real locu,locv;
 956                     gp_Vec norm1,norm2,d1u,d1v;
 957                     gp_Pnt ptbid;
 958                     Standard_Integer indextg;
 959                     gp_Vec tgline(PW.TangentAtLine(indextg));
 960                     PW.Line()->Value(indextg).ParametersOnS1(locu,locv);
 961                     Surf1->D1(locu,locv,ptbid,d1u,d1v);
 962                     norm1 = d1u.Crossed(d1v);
 963                     PW.Line()->Value(indextg).ParametersOnS2(locu,locv);
 964                     Surf1->D1(locu,locv,ptbid,d1u,d1v);
 965                     norm2 = d1u.Crossed(d1v);
 966                     if (tgline.DotCross(norm2,norm1)>0.) {
 967                       trans1 = IntSurf_Out;
 968                       trans2 = IntSurf_In;
 969                     }
 970                     else {
 971                       trans1 = IntSurf_In;
 972                       trans2 = IntSurf_Out;
 973                     }
 974
 975                     IntSurf_LineOn2S LineOn2S;
 976                     Standard_Integer nbpw,imin,imax,i;
 977                     nbpw = PW.Line()->NbPoints();
 978                     Standard_Real u1,v1,u2,v2;
 979                     i=0;
 980                     do {
 981                       i++;
 982                       imin=i;
 983                       const IntSurf_PntOn2S& Pi   = PW.Line()->Value(i);
 984                       Pi.Parameters(u1,v1,u2,v2);
 985                     } while((i<nbpw)&&(Abs(u1-u2)<=1e-6 && Abs(v1-v2)<=1e-6));
 986
 987                     if(imin>2)
 988                       imin--;
 989
 990                     i=nbpw+1;
 991                     do {
 992                       i--;
 993                       imax=i;
 994                       const IntSurf_PntOn2S& Pi   = PW.Line()->Value(i);
 995                       Pi.Parameters(u1,v1,u2,v2);
 996                     } while((i>2)&&(Abs(u1-u2)<=1e-6 && Abs(v1-v2)<=1e-6));
 997
 998                     if(imax<nbpw)
 999                       imax++;
1000
1001                     if(imin<imax) {
1002                       Handle(IntSurf_LineOn2S) PWLine = new IntSurf_LineOn2S();
1003                       for(i=imin;i<=imax;i++)
1004                         PWLine->Add(PW.Line()->Value(i));
1005
1006                       Standard_Real TolTang = TolTangency;
1007                       Handle(IntPatch_WLine) wline = new IntPatch_WLine(PWLine,Standard_False,trans1,trans2);
1008                       wline->SetCreatingWayInfo(IntPatch_WLine::IntPatch_WLPrmPrm);
1009
1010                       const IntSurf_PntOn2S& POn2SDeb = wline->Point(1);
1011                       const IntSurf_PntOn2S& POn2SFin = wline->Point(wline->NbPnts());
1012                       if((POn2SDeb.Value()).Distance(POn2SFin.Value()) <= TolTangency) {
1013                         Standard_Real u1t,v1t,u2t,v2t;
1014                         POn2SDeb.Parameters(u1t,v1t,u2t,v2t);
1015                         IntPatch_Point vtx;
1016                         vtx.SetValue(POn2SDeb.Value(),TolTang,Standard_False);
1017                         vtx.SetParameters(u2t,v2t,u1t,v1t);
1018                         vtx.SetParameter(wline->NbPnts());
1019                         wline->SetPoint(wline->NbPnts(),vtx);
1020                       }
1021                       //the method PutVertexOnLine can reduce the number of points in <wline>
1022                       IntPatch_RstInt::PutVertexOnLine(wline,Surf1,D1,Surf1,Standard_True,TolTang);
1023                       if (wline->NbPnts() < 2)
1024                         continue;
1025                       if(wline->NbVertex() == 0) {
1026                         IntPatch_Point vtx;
1027                         IntSurf_PntOn2S POn2S = PW.Line()->Value(1);
1028                         POn2S.Parameters(pu1,pv1,pu2,pv2);
1029                         vtx.SetValue(Point3dDebut,TolTang,Standard_False);
1030                         vtx.SetParameters(pu1,pv1,pu2,pv2);
1031                         vtx.SetParameter(1);
1032                         wline->AddVertex(vtx);
1033
1034                         POn2S = PW.Line()->Value(wline->NbPnts());
1035                         POn2S.Parameters(pu1,pv1,pu2,pv2);
1036                         vtx.SetValue(Point3dFin,TolTang,Standard_False);
1037                         vtx.SetParameters(pu1,pv1,pu2,pv2);
1038                         vtx.SetParameter(wline->NbPnts());
1039                         wline->AddVertex(vtx);
1040                       }
1041                       SLin.Append(wline);
1042                       empt = Standard_False;
1043                     }// imin<imax
1044                   }// !RejetLigne
1045                 }// PW.NbPoints()>2
1046               }// done is True
1047             }// dminiPointLigne > SeuildPointLigne
1048           }// Abs || Abs
1049         }// HasStartPoint
1050       } while(nbp>5 && NombreDePointsDeDepartDuCheminement<3);
1051     }// for( ls ...
1052   }// nbLigSec>=1
1053
1054   Standard_Integer z;
1055   for( z = 1; z <= nbTanZon; z++) {
1056     const Intf_TangentZone& TangentZone=Interference.ZoneValue(z);
1057     for(Standard_Integer pz=1; pz<=TangentZone.NumberOfPoints(); pz++) {
1058       SectionPointToParameters(TangentZone.GetPoint(pz),Poly1,Poly1,U1,V1,U2,V2);
1059
1060       StartParams(1) = U1;
1061       StartParams(2) = V1;
1062       StartParams(3) = U2;
1063       StartParams(4) = V2;
1064
1065       HasStartPoint = PW.PerformFirstPoint(StartParams,StartPOn2S);
1066       if(HasStartPoint) {
1067         StartPOn2S.Parameters(pu1,pv1,pu2,pv2);
1068         if(Abs(pu1-pu2)>1e-7 || Abs(pv1-pv2)>1e-7) {
1069           NbLigCalculee = SLin.Length();
1070           dminiPointLigne = SeuildPointLigne + SeuildPointLigne;
1071           Standard_Integer l;
1072           for( l = 1; (l <= NbLigCalculee) && (dminiPointLigne >= SeuildPointLigne); l++) {
1073             const Handle(IntPatch_WLine)& testwline = *((Handle(IntPatch_WLine)*)&SLin.Value(l));
1074             if( (testwline->IsOutSurf1Box(gp_Pnt2d(pu1,pv1))==Standard_False) &&
1075               (testwline->IsOutSurf2Box(gp_Pnt2d(pu2,pv2))==Standard_False) &&
1076               (testwline->IsOutBox(StartPOn2S.Value())==Standard_False) ) {
1077                 NbPntOn2SOnLine = testwline->NbPnts();
1078                 Standard_Integer ll;
1079                 for( ll = 1; (ll < NbPntOn2SOnLine) && (dminiPointLigne >= SeuildPointLigne); ll++) {
1080                   Standard_Real t,Au1,Av1,Au2,Av2,Bu1,Bv1,Bu2,Bv2;
1081                   testwline->Point(ll).Parameters(Au1,Av1,Au2,Av2);
1082                   testwline->Point(ll+1).Parameters(Bu1,Bv1,Bu2,Bv2);
1083                   if(Au1>Bu1) {
1084                     t=Au1;
1085                     Au1=Bu1;
1086                     Bu1=t;
1087                   }
1088                   if(Av1>Bv1) {
1089                     t=Av1;
1090                     Av1=Bv1;
1091                     Bv1=t;
1092                   }
1093                   Au1-=1.0e-7;
1094                   Av1-=1.0e-7;
1095                   Bu1+=1.0e-7;
1096                   Bv1+=1.0e-7;
1097                   if((pu1>=Au1) && (pu1<=Bu1) && (pv1>=Av1) && (pv1<=Bv1))
1098                     dminiPointLigne = 0.0;
1099                   else {
1100                     if((pu2>=Au1) && (pu2<=Bu1) && (pv2>=Av1) && (pv2<=Bv1))
1101                       dminiPointLigne = 0.0;
1102                   }
1103                 }// for( ll ...
1104             }// if ...
1105           }// for( l ...
1106
1107           if(dminiPointLigne > SeuildPointLigne) {
1108             PW.Perform(StartParams);
1109             if(PW.IsDone()) {
1110               if(PW.NbPoints()>2) {
1111                 RejetLigne = Standard_False;
1112                 Point3dDebut = PW.Value(1).Value();
1113                 Point3dFin   = PW.Value(PW.NbPoints()).Value();
1114                 for( ver = 1 ; ver<= NbLigCalculee ; ver++) {
1115                   const Handle(IntPatch_WLine)& verwline = *((Handle(IntPatch_WLine)*)&SLin.Value(ver));
1116                   const IntSurf_PntOn2S& verPointDebut = verwline->Point(1);
1117                   const IntSurf_PntOn2S& verPointFin = verwline->Point(verwline->NbPnts());
1118                   if( (Point3dDebut.Distance(verPointDebut.Value()) < TolTangency) ||
1119                       (Point3dFin.Distance(verPointFin.Value()) < TolTangency))
1120                   {
1121                     RejetLigne = Standard_True;
1122                     break;
1123                   }
1124                 }
1125
1126                 if(RejetLigne)
1127                 {
1128                   DublicateOfLinesProcessing(PW, ver, SLin, RejetLigne);
1129                 }
1130
1131                 if(!RejetLigne) {
1132                   IntSurf_TypeTrans trans1,trans2;
1133                   Standard_Real locu,locv;
1134                   gp_Vec norm1,norm2,d1u,d1v;
1135                   gp_Pnt ptbid;
1136                   Standard_Integer indextg;
1137                   gp_Vec tgline(PW.TangentAtLine(indextg));
1138                   PW.Line()->Value(indextg).ParametersOnS1(locu,locv);
1139                   Surf1->D1(locu,locv,ptbid,d1u,d1v);
1140                   norm1 = d1u.Crossed(d1v);
1141                   PW.Line()->Value(indextg).ParametersOnS2(locu,locv);
1142                   Surf1->D1(locu,locv,ptbid,d1u,d1v);
1143                   norm2 = d1u.Crossed(d1v);
1144                   if(tgline.DotCross(norm2,norm1)>0.) {
1145                     trans1 = IntSurf_Out;
1146                     trans2 = IntSurf_In;
1147                   }
1148                   else {
1149                     trans1 = IntSurf_In;
1150                     trans2 = IntSurf_Out;
1151                   }
1152
1153                   IntSurf_LineOn2S LineOn2S;
1154                   Standard_Integer nbp,imin,imax,i;
1155                   nbp = PW.Line()->NbPoints();
1156                   Standard_Real u1,v1,u2,v2;
1157                   i=0;
1158                   do {
1159                     i++;
1160                     imin=i;
1161                     const IntSurf_PntOn2S& Pi   = PW.Line()->Value(i);
1162                     Pi.Parameters(u1,v1,u2,v2);
1163                   } while((i<nbp)&&(Abs(u1-u2)<=1e-6 && Abs(v1-v2)<=1e-6));
1164
1165                   if(imin>2)
1166                     imin--;
1167
1168                   i=nbp+1;
1169                   do {
1170                     i--;
1171                     imax=i;
1172                     const IntSurf_PntOn2S& Pi   = PW.Line()->Value(i);
1173                     Pi.Parameters(u1,v1,u2,v2);
1174                   } while((i>2)&&(Abs(u1-u2)<=1e-6 && Abs(v1-v2)<=1e-6));
1175
1176                   if(imax<nbp)
1177                     imax++;
1178
1179                   if(imin<imax) {
1180                     Handle(IntSurf_LineOn2S) PWLine = new IntSurf_LineOn2S();
1181                     for(i=imin;i<=imax;i++)
1182                       PWLine->Add(PW.Line()->Value(i));
1183
1184                     Standard_Real TolTang = TolTangency;
1185                     Handle(IntPatch_WLine) wline = new IntPatch_WLine(PWLine,Standard_False,trans1,trans2);
1186                     wline->SetCreatingWayInfo(IntPatch_WLine::IntPatch_WLPrmPrm);
1187
1188                     const IntSurf_PntOn2S& POn2SDeb = wline->Point(1);
1189                     const IntSurf_PntOn2S& POn2SFin = wline->Point(wline->NbPnts());
1190                     if((POn2SDeb.Value()).Distance(POn2SFin.Value()) <= TolTangency) {
1191                       Standard_Real u1t,v1t,u2t,v2t;
1192                       POn2SDeb.Parameters(u1t,v1t,u2t,v2t);
1193                       IntPatch_Point vtx;
1194                       vtx.SetValue(POn2SDeb.Value(),TolTang,Standard_False);
1195                       vtx.SetParameters(u2t,v2t,u1t,v1t);
1196                       vtx.SetParameter(wline->NbPnts());
1197                       wline->SetPoint(wline->NbPnts(),vtx);
1198                     }
1199
1200                     //the method PutVertexOnLine can reduce the number of points in <wline>
1201                     IntPatch_RstInt::PutVertexOnLine(wline,Surf1,D1,Surf1,Standard_True,TolTang);
1202                     if (wline->NbPnts() < 2)
1203                       continue;
1204
1205                     if(wline->NbVertex() == 0) {
1206                       IntPatch_Point vtx;
1207                       IntSurf_PntOn2S POn2S = PW.Line()->Value(1);
1208                       POn2S.Parameters(pu1,pv1,pu2,pv2);
1209                       vtx.SetValue(Point3dDebut,TolTang,Standard_False);
1210                       vtx.SetParameters(pu1,pv1,pu2,pv2);
1211                       vtx.SetParameter(1);
1212                       wline->AddVertex(vtx);
1213
1214                       POn2S = PW.Line()->Value(wline->NbPnts());
1215                       POn2S.Parameters(pu1,pv1,pu2,pv2);
1216                       vtx.SetValue(Point3dFin,TolTang,Standard_False);
1217                       vtx.SetParameters(pu1,pv1,pu2,pv2);
1218                       vtx.SetParameter(wline->NbPnts());
1219                       wline->AddVertex(vtx);
1220                     }
1221
1222                     SLin.Append(wline);
1223                     empt = Standard_False;
1224                   }// imin<imax
1225                 }// !RejetLigne
1226               }// PW.NbPoints()>2
1227             }// done a True
1228           }// dminiPointLigne > SeuildPointLigne
1229         }// Abs || Abs
1230       }// HasStartPoint
1231     }// for ( pz ...
1232   }// for( z ...
1233 }
1234
1235 //==================================================================================
1236 // function : NewLine
1237 // purpose  :
1238 //==================================================================================
1239 Handle(IntPatch_Line) IntPatch_PrmPrmIntersection::NewLine (const Handle(Adaptor3d_Surface)&    Surf1,
1240                                                            const Handle(Adaptor3d_Surface)&    Surf2,
1241                                                            const Standard_Integer NumLine,
1242                                                            const Standard_Integer Low,
1243                                                            const Standard_Integer High,
1244                                                            const Standard_Integer NbPntsToInsert) const
1245 {
1246   Standard_Integer NbPnts = NbPntsToInsert + High - Low;
1247   if(NumLine>NbLines() || NumLine<1  || Low>=High )
1248     throw Standard_OutOfRange(" IntPatch_PrmPrmIntersection NewLine ");
1249   //------------------------------------------------------------------
1250   //--  Indice     :   Low       Low+1     I    I+1         High    --
1251   //--                                                              --
1252   //--  Abs.Curv.  :  S(Low)              S(I)  S(I+1)      S(High) --
1253   //--                                                              --
1254   //--                On echantillonne a abcisse curviligne         --
1255   //--                constante.                                    --
1256   //--                L abcisse est calculee sur les params U1,V1   --
1257   //------------------------------------------------------------------
1258   TColStd_Array1OfReal U1(Low,High);
1259   TColStd_Array1OfReal V1(Low,High);
1260   TColStd_Array1OfReal U2(Low,High);
1261   TColStd_Array1OfReal V2(Low,High);
1262   TColStd_Array1OfReal AC(Low,High);
1263
1264   Standard_Real s,ds;
1265   Handle(IntPatch_WLine) TheLine = Handle(IntPatch_WLine)::DownCast(Line(NumLine));
1266   const IntSurf_PntOn2S& Point=TheLine->Point(Low);
1267   Standard_Real u1,v1,u2,v2;
1268   Point.Parameters(u1,v1,u2,v2);
1269   U1(Low) = u1;
1270   V1(Low) = v1;
1271   U2(Low) = u2;
1272   V2(Low) = v2;
1273   AC(Low) =0.0;
1274
1275   IntWalk_PWalking PW(Surf1,Surf2,0.000001,0.000001,0.001,0.001);
1276
1277   Standard_Integer i;
1278   for(i=Low+1; i<=High; i++)
1279   {
1280     const IntSurf_PntOn2S& Pointi=TheLine->Point(i);
1281     Pointi.Parameters(u1,v1,u2,v2);
1282     U1(i) = u1;
1283     V1(i) = v1;
1284     U2(i) = u2;
1285     V2(i) = v2;
1286
1287     Standard_Real du1=u1-U1(i-1);
1288     Standard_Real dv1=v1-V1(i-1);
1289
1290     AC(i) = AC(i-1) + Sqrt((du1*du1)+(dv1*dv1));
1291   }
1292
1293   Handle(IntSurf_LineOn2S) ResultPntOn2SLine = new IntSurf_LineOn2S();
1294
1295   IntSurf_PntOn2S StartPOn2S;
1296   TColStd_Array1OfReal StartParams(1,4);
1297
1298   ResultPntOn2SLine->Add(TheLine->Point(Low));
1299
1300   ds = AC(High) / (NbPnts-1);
1301   Standard_Integer Indice = Low;
1302
1303   Standard_Real dsmin = ds*0.3;
1304   Standard_Real smax  = AC(High);
1305
1306   for(i=2,s=ds; (i<NbPnts)&&(s<smax); i++,s+=ds)
1307   {
1308     while(AC(Indice+1) <= s)
1309     {
1310       ResultPntOn2SLine->Add(TheLine->Point(Indice));
1311       Indice++;
1312     }
1313     Standard_Real a = s - AC(Indice);
1314     Standard_Real b = AC(Indice+1) - s;
1315     Standard_Real nab = 1.0/(a+b);
1316     //----------------------------------------------------------
1317     //-- Verification :  Si Dist au prochain  point < dsmin   --
1318     //--                 Si Dist au precedent point < dsmin   --
1319     //--                                                      --
1320     //----------------------------------------------------------
1321     if((nab > ds)&&(a>dsmin)&&(b>dsmin))
1322     {
1323       StartParams(1) = (U1(Indice) * b   +  U1(Indice+1) * a) * nab;
1324       StartParams(2) = (V1(Indice) * b   +  V1(Indice+1) * a) * nab;
1325       StartParams(3) = (U2(Indice) * b   +  U2(Indice+1) * a) * nab;
1326       StartParams(4) = (V2(Indice) * b   +  V2(Indice+1) * a) * nab;
1327
1328       Standard_Boolean HasStartPoint = PW.PerformFirstPoint(StartParams,StartPOn2S);
1329       if(HasStartPoint)
1330         ResultPntOn2SLine->Add(StartPOn2S);
1331     }
1332     else
1333       s+=dsmin;
1334   }
1335
1336   ResultPntOn2SLine->Add(TheLine->Point(High));
1337
1338   Handle(IntPatch_WLine) aRWL = new IntPatch_WLine(ResultPntOn2SLine, Standard_False);
1339   aRWL->SetCreatingWayInfo(IntPatch_WLine::IntPatch_WLPrmPrm);
1340
1341   return(aRWL);
1342 }
1343
1344 //==================================================================================
1345 // function : SectionPointToParameters
1346 // purpose  :
1347 //==================================================================================
1348 void SectionPointToParameters(const Intf_SectionPoint& Sp,
1349                               const IntPatch_Polyhedron& Poly1,
1350                               const IntPatch_Polyhedron& Poly2,
1351                               Standard_Real& u1,
1352                               Standard_Real& v1,
1353                               Standard_Real& u2,
1354                               Standard_Real& v2)
1355 {
1356   Intf_PIType       typ;
1357   Standard_Integer  Adr1,Adr2;
1358   Standard_Real     Param,u,v;
1359   gp_Pnt P(Sp.Pnt());
1360
1361   Standard_Integer Pt1,Pt2,Pt3;
1362
1363   Sp.InfoFirst(typ,Adr1,Adr2,Param);
1364   switch(typ) {
1365   case Intf_VERTEX:   //-- Adr1 est le numero du vertex
1366     {
1367       Poly1.Parameters(Adr1,u1,v1);
1368       break;
1369     }
1370   case Intf_EDGE:
1371     {
1372       Poly1.Parameters(Adr1,u1,v1);
1373       Poly1.Parameters(Adr2,u,v);
1374       u1+= Param * (u-u1);
1375       v1+= Param * (v-v1);
1376       break;
1377     }
1378   case Intf_FACE:
1379     {
1380       Standard_Real ua,va,ub,vb,uc,vc,ca,cb,cc,cabc;
1381       Poly1.Triangle(Adr1,Pt1,Pt2,Pt3);
1382       gp_Pnt PA(Poly1.Point(Pt1));
1383       gp_Pnt PB(Poly1.Point(Pt2));
1384       gp_Pnt PC(Poly1.Point(Pt3));
1385       Poly1.Parameters(Pt1,ua,va);
1386       Poly1.Parameters(Pt2,ub,vb);
1387       Poly1.Parameters(Pt3,uc,vc);
1388       gp_Vec Normale(gp_Vec(PA,PB).Crossed(gp_Vec(PA,PC)));
1389       cc = (gp_Vec(PA,PB).Crossed(gp_Vec(PA,P))).Dot(Normale);
1390       ca = (gp_Vec(PB,PC).Crossed(gp_Vec(PB,P))).Dot(Normale);
1391       cb = (gp_Vec(PC,PA).Crossed(gp_Vec(PC,P))).Dot(Normale);
1392       cabc = ca + cb + cc;
1393
1394       ca/=cabc;     cb/=cabc;       cc/=cabc;
1395
1396       u1 = ca * ua + cb * ub + cc * uc;
1397       v1 = ca * va + cb * vb + cc * vc;
1398       break;
1399     }
1400   default:
1401     {
1402       //-- std::cout<<" Default dans SectionPointToParameters "<<std::endl;
1403       break;
1404     }
1405   }
1406
1407
1408   Sp.InfoSecond(typ,Adr1,Adr2,Param);
1409   switch(typ) {
1410   case Intf_VERTEX:   //-- Adr1 est le numero du vertex
1411     {
1412       Poly2.Parameters(Adr1,u2,v2);
1413       break;
1414     }
1415   case Intf_EDGE:
1416     {
1417       Poly2.Parameters(Adr1,u2,v2);
1418       Poly2.Parameters(Adr2,u,v);
1419       u2+= Param * (u-u2);
1420       v2+= Param * (v-v2);
1421       break;
1422     }
1423   case Intf_FACE:
1424     {
1425       Standard_Real ua,va,ub,vb,uc,vc,ca,cb,cc,cabc;
1426       Poly2.Triangle(Adr1,Pt1,Pt2,Pt3);
1427       gp_Pnt PA(Poly2.Point(Pt1));
1428       gp_Pnt PB(Poly2.Point(Pt2));
1429       gp_Pnt PC(Poly2.Point(Pt3));
1430       Poly2.Parameters(Pt1,ua,va);
1431       Poly2.Parameters(Pt2,ub,vb);
1432       Poly2.Parameters(Pt3,uc,vc);
1433       gp_Vec Normale(gp_Vec(PA,PB).Crossed(gp_Vec(PA,PC)));
1434       cc = (gp_Vec(PA,PB).Crossed(gp_Vec(PA,P))).Dot(Normale);
1435       ca = (gp_Vec(PB,PC).Crossed(gp_Vec(PB,P))).Dot(Normale);
1436       cb = (gp_Vec(PC,PA).Crossed(gp_Vec(PC,P))).Dot(Normale);
1437       cabc = ca + cb + cc;
1438
1439       ca/=cabc;     cb/=cabc;       cc/=cabc;
1440
1441       u2 = ca * ua + cb * ub + cc * uc;
1442       v2 = ca * va + cb * vb + cc * vc;
1443       break;
1444     }
1445   default:
1446     {
1447       //-- std::cout<<" Default dans SectionPointToParameters "<<std::endl;
1448       break;
1449     }
1450   }
1451 }
1452
1453 //==================================================================================
1454 // function : RemplitLin
1455 // purpose  :
1456 //==================================================================================
1457 void IntPatch_PrmPrmIntersection::RemplitLin(const Standard_Integer x1,
1458                                              const Standard_Integer y1,
1459                                              const Standard_Integer z1,
1460                                              const Standard_Integer x2,
1461                                              const Standard_Integer y2,
1462                                              const Standard_Integer z2,
1463                                              IntPatch_PrmPrmIntersection_T3Bits& Map) const
1464 {
1465   int xg,yg,zg;
1466   xg=x1-x2; if(xg<0) xg=-xg;
1467   yg=y1-y2; if(yg<0) yg=-yg;
1468   zg=z1-z2; if(zg<0) zg=-zg;
1469   if(DansGrille(x1) && DansGrille(y1) && DansGrille(z1)) {
1470     Standard_Integer t = GrilleInteger(x1,y1,z1);
1471     Map.Add(t);
1472   }
1473   if(xg<=1 && yg<=1 && zg<=1) return;
1474   xg = (x1+x2)>>1;
1475   yg = (y1+y2)>>1;
1476   zg = (z1+z2)>>1;
1477   RemplitLin(x1,y1,z1,xg,yg,zg,Map);
1478   RemplitLin(x2,y2,z2,xg,yg,zg,Map);
1479 }
1480
1481 //==================================================================================
1482 // function : RemplitTri
1483 // purpose  :
1484 //==================================================================================
1485 void IntPatch_PrmPrmIntersection::RemplitTri(const Standard_Integer x1,
1486                                              const Standard_Integer y1,
1487                                              const Standard_Integer z1,
1488                                              const Standard_Integer x2,
1489                                              const Standard_Integer y2,
1490                                              const Standard_Integer z2,
1491                                              const Standard_Integer x3,
1492                                              const Standard_Integer y3,
1493                                              const Standard_Integer z3,
1494                                              IntPatch_PrmPrmIntersection_T3Bits& Map) const
1495 {
1496   if(x1==x2 && x1==x3 && y1==y2 && y1==y3 && z1==z2 && z1==z3) {
1497     if(DansGrille(x1) && DansGrille(y1) && DansGrille(z1)) {
1498       Standard_Integer t = GrilleInteger(x1,y1,z1);
1499       Map.Add(t);
1500     }
1501     return;
1502   }
1503   else {
1504     Standard_Integer xg=(x1+x2+x3)/3;
1505     Standard_Integer yg=(y1+y2+y3)/3;
1506     Standard_Integer zg=(z1+z2+z3)/3;
1507     if(xg==x1 && yg==y1 && zg==z1) {
1508       RemplitLin(x1,y1,z1,x2,y2,z2,Map);
1509       RemplitLin(x1,y1,z1,x3,y3,z3,Map);
1510       return;
1511     }
1512     if(xg==x2 && yg==y2 && zg==z2) {
1513       RemplitLin(x2,y2,z2,x1,y1,z1,Map);
1514       RemplitLin(x2,y2,z2,x3,y3,z3,Map);
1515       return;
1516     }
1517     if(xg==x3 && yg==y3 && zg==z3) {
1518       RemplitLin(x3,y3,z3,x2,y2,z2,Map);
1519       RemplitLin(x3,y3,z3,x1,y1,z1,Map);
1520       return;
1521     }
1522     if(DansGrille(xg) && DansGrille(yg) && DansGrille(zg)) {
1523       Standard_Integer t = GrilleInteger(xg,yg,zg);
1524       Map.Add(t);
1525     }
1526     if(xg!=x3 || yg!=y3 || zg!=z3) RemplitTri(x1,y1,z1, x2,y2,z2, xg,yg,zg, Map);
1527     if(xg!=x1 || yg!=y1 || zg!=z1) RemplitTri(xg,yg,zg, x2,y2,z2, x3,y3,z3, Map);
1528     if(xg!=x2 || yg!=y2 || zg!=z2) RemplitTri(x1,y1,z1, xg,yg,zg, x3,y3,z3, Map);
1529   }
1530 }
1531
1532 //==================================================================================
1533 // function : Remplit
1534 // purpose  :
1535 //==================================================================================
1536 void IntPatch_PrmPrmIntersection::Remplit(const Standard_Integer a,
1537                                           const Standard_Integer b,
1538                                           const Standard_Integer c,
1539                                           IntPatch_PrmPrmIntersection_T3Bits& Map) const
1540 {
1541   int iax,iay,iaz,ibx,iby,ibz,icx,icy,icz;
1542   if(a!=-1) Map.Add(a);
1543   if(b!=-1) Map.Add(b);
1544   if(c!=-1) Map.Add(c);
1545
1546   if(a!=-1 && b!=-1 && c!=-1 ) {
1547     IntegerGrille(a,iax,iay,iaz);
1548     IntegerGrille(b,ibx,iby,ibz);
1549     IntegerGrille(c,icx,icy,icz);
1550     RemplitTri(iax,iay,iaz,ibx,iby,ibz,icx,icy,icz,Map);
1551   }
1552 }
1553
1554
1555
1556 //=======================================================================
1557 //function : Perform
1558 //purpose  :
1559 //=======================================================================
1560 void IntPatch_PrmPrmIntersection::Perform (const Handle(Adaptor3d_Surface)&    Surf1,
1561                                            const Handle(Adaptor3d_TopolTool)& D1,
1562                                            const Handle(Adaptor3d_Surface)&    Surf2,
1563                                            const Handle(Adaptor3d_TopolTool)& D2,
1564                                            const Standard_Real   TolTangency,
1565                                            const Standard_Real   Epsilon,
1566                                            const Standard_Real   Deflection,
1567                                            const Standard_Real   Increment,
1568                                            IntSurf_ListOfPntOn2S& LOfPnts)
1569 {
1570   if (LOfPnts.IsEmpty()){
1571     done = Standard_True;
1572     return;
1573   }
1574
1575   empt = Standard_True;
1576   SLin.Clear();
1577
1578   Standard_Real UminLig1,VminLig1,UmaxLig1,VmaxLig1;
1579   Standard_Real UminLig2,VminLig2,UmaxLig2,VmaxLig2;
1580   Standard_Real U1,U2,V1,V2;
1581
1582   UminLig1 = Surf1->FirstUParameter();
1583   VminLig1 = Surf1->FirstVParameter();
1584   UmaxLig1 = Surf1->LastUParameter();
1585   VmaxLig1 = Surf1->LastVParameter();
1586   UminLig2 = Surf2->FirstUParameter();
1587   VminLig2 = Surf2->FirstVParameter();
1588   UmaxLig2 = Surf2->LastUParameter();
1589   VmaxLig2 = Surf2->LastVParameter();
1590
1591   Standard_Real Periods [4];
1592   Periods[0] = (Surf1->IsUPeriodic())? Surf1->UPeriod() : 0.;
1593   Periods[1] = (Surf1->IsVPeriodic())? Surf1->VPeriod() : 0.;
1594   Periods[2] = (Surf2->IsUPeriodic())? Surf2->UPeriod() : 0.;
1595   Periods[3] = (Surf2->IsVPeriodic())? Surf2->VPeriod() : 0.;
1596
1597   IntSurf_ListIteratorOfListOfPntOn2S IterLOP1(LOfPnts);
1598   if (Surf1->IsUClosed() || Surf1->IsVClosed() ||
1599       Surf2->IsUClosed() || Surf2->IsVClosed())
1600   {
1601     Standard_Real TolPar = Precision::PConfusion();
1602     IntSurf_ListOfPntOn2S AdditionalPnts;
1603     Standard_Real NewU1, NewV1, NewU2, NewV2;
1604     for(; IterLOP1.More(); IterLOP1.Next())
1605     {
1606       IntSurf_PntOn2S Pnt = IterLOP1.Value();
1607       Pnt.Parameters(U1, V1, U2, V2);
1608       IntSurf_PntOn2S NewPnt;
1609       if (Surf1->IsUClosed())
1610       {
1611         if (Abs(U1 - Surf1->FirstUParameter()) <= TolPar)
1612         {
1613           NewU1 = Surf1->LastUParameter();
1614           NewPnt.SetValue( NewU1, V1, U2, V2 );
1615           AdditionalPnts.Append(NewPnt);
1616         }
1617         else if (Abs(U1 - Surf1->LastUParameter()) <= TolPar)
1618         {
1619           NewU1 = Surf1->FirstUParameter();
1620           NewPnt.SetValue( NewU1, V1, U2, V2 );
1621           AdditionalPnts.Append(NewPnt);
1622         }
1623       }
1624       if (Surf1->IsVClosed())
1625       {
1626         if (Abs(V1 - Surf1->FirstVParameter()) <= TolPar)
1627         {
1628           NewV1 = Surf1->LastVParameter();
1629           NewPnt.SetValue( U1, NewV1, U2, V2 );
1630           AdditionalPnts.Append(NewPnt);
1631         }
1632         else if (Abs(V1 - Surf1->LastVParameter()) <= TolPar)
1633         {
1634           NewV1 = Surf1->FirstVParameter();
1635           NewPnt.SetValue( U1, NewV1, U2, V2 );
1636           AdditionalPnts.Append(NewPnt);
1637         }
1638       }
1639       if (Surf2->IsUClosed())
1640       {
1641         if (Abs(U2 - Surf2->FirstUParameter()) <= TolPar)
1642         {
1643           NewU2 = Surf2->LastUParameter();
1644           NewPnt.SetValue( U1, V1, NewU2, V2);
1645           AdditionalPnts.Append(NewPnt);
1646         }
1647         else if (Abs(U2 - Surf2->LastUParameter()) <= TolPar)
1648         {
1649           NewU2 = Surf2->FirstUParameter();
1650           NewPnt.SetValue( U1, V1, NewU2, V2);
1651           AdditionalPnts.Append(NewPnt);
1652         }
1653       }
1654       if (Surf2->IsVClosed())
1655       {
1656         if (Abs(V2 - Surf2->FirstVParameter()) <= TolPar)
1657         {
1658           NewV2 = Surf2->LastVParameter();
1659           NewPnt.SetValue( U1, V1, U2, NewV2 );
1660           AdditionalPnts.Append(NewPnt);
1661         }
1662         else if (Abs(V2 - Surf2->LastVParameter()) <= TolPar)
1663         {
1664           NewV2 = Surf2->FirstVParameter();
1665           NewPnt.SetValue( U1, V1, U2, NewV2 );
1666           AdditionalPnts.Append(NewPnt);
1667         }
1668       }
1669     }
1670     //Cut repeated points
1671     for (IterLOP1.Initialize(LOfPnts); IterLOP1.More(); IterLOP1.Next())
1672     {
1673       IntSurf_PntOn2S aPnt = IterLOP1.Value();
1674       aPnt.Parameters(U1, V1, U2, V2);
1675       IntSurf_ListIteratorOfListOfPntOn2S iter2(AdditionalPnts);
1676       while (iter2.More())
1677       {
1678         IntSurf_PntOn2S aNewPnt = iter2.Value();
1679         aNewPnt.Parameters(NewU1, NewV1, NewU2, NewV2);
1680         if (Abs(U1 - NewU1) <= TolPar &&
1681             Abs(V1 - NewV1) <= TolPar &&
1682             Abs(U2 - NewU2) <= TolPar &&
1683             Abs(V2 - NewV2) <= TolPar)
1684           AdditionalPnts.Remove(iter2);
1685         else
1686           iter2.Next();
1687       }
1688     }
1689
1690     LOfPnts.Append(AdditionalPnts);
1691   }
1692
1693   for(IterLOP1.Initialize(LOfPnts); IterLOP1.More(); IterLOP1.Next()){
1694     IntSurf_PntOn2S Pnt = IterLOP1.Value();
1695     Pnt.Parameters(U1, V1, U2, V2);
1696     if(U1>UmaxLig1) UmaxLig1=U1;
1697     if(V1>VmaxLig1) VmaxLig1=V1;
1698     if(U2>UmaxLig2) UmaxLig2=U2;
1699     if(V2>VmaxLig2) VmaxLig2=V2;
1700
1701     if(U1<UminLig1) UminLig1=U1;
1702     if(V1<VminLig1) VminLig1=V1;
1703     if(U2<UminLig2) UminLig2=U2;
1704     if(V2<VminLig2) VminLig2=V2;
1705   }
1706
1707   Standard_Real SeuildPointLigne = 15.0 * Increment * Increment;
1708
1709   Standard_Integer NbLigCalculee = 0, ver;
1710   Standard_Real pu1,pu2,pv1,pv2, dminiPointLigne;
1711   Standard_Boolean HasStartPoint,RejetLigne;
1712   IntSurf_PntOn2S StartPOn2S;
1713   gp_Pnt Point3dDebut,Point3dFin;
1714
1715   TColStd_Array1OfReal StartParams(1,4);
1716   IntWalk_PWalking PW(Surf1,Surf2,TolTangency,Epsilon,Deflection,Increment);
1717
1718   IntSurf_ListIteratorOfListOfPntOn2S IterLOP2(LOfPnts);
1719   for(; IterLOP2.More(); IterLOP2.Next() ){
1720
1721     IntSurf_PntOn2S cPnt = IterLOP2.Value();
1722     cPnt.Parameters(U1, V1, U2, V2);
1723
1724     StartParams(1) = U1;
1725     StartParams(2) = V1;
1726     StartParams(3) = U2;
1727     StartParams(4) = V2;
1728
1729     HasStartPoint = PW.PerformFirstPoint(StartParams,StartPOn2S);
1730     dminiPointLigne = SeuildPointLigne + SeuildPointLigne;
1731     if(HasStartPoint) {
1732       StartPOn2S.Parameters(pu1,pv1,pu2,pv2);
1733       NbLigCalculee = SLin.Length();
1734       Standard_Integer l;
1735       for( l = 1; (l <= NbLigCalculee) && (dminiPointLigne >= SeuildPointLigne); l++) {
1736         const Handle(IntPatch_WLine)& testwline = *((Handle(IntPatch_WLine)*)&SLin.Value(l));
1737
1738         if (IsPointOnLine(StartPOn2S, testwline, Deflection)) {
1739           dminiPointLigne = 0.0;
1740         }
1741       }// for( l ...
1742
1743       if(dminiPointLigne > SeuildPointLigne) {
1744         PW.Perform(StartParams,UminLig1,VminLig1,UminLig2,VminLig2,UmaxLig1,VmaxLig1,UmaxLig2,VmaxLig2);
1745         if(PW.IsDone()) {
1746           if(PW.NbPoints()>2)
1747           {
1748             //Try to extend the intersection line to boundary, if it is possible.
1749             PW.PutToBoundary(Surf1, Surf2);
1750
1751             RejetLigne = Standard_False;
1752             Point3dDebut = PW.Value(1).Value();
1753             const IntSurf_PntOn2S& PointFin = PW.Value(PW.NbPoints());
1754             Point3dFin   = PointFin.Value();
1755             for( ver = 1 ; ver<= NbLigCalculee ; ver++) {
1756               const Handle(IntPatch_WLine)& verwline = *((Handle(IntPatch_WLine)*)&SLin.Value(ver));
1757
1758               // Check end point if it is on existing line.
1759               // Start point is checked before.
1760               if (IsPointOnLine(PointFin, verwline, Deflection)) {
1761                 RejetLigne = Standard_True;
1762                 break;
1763               }
1764
1765               const IntSurf_PntOn2S& verPointDebut = verwline->Point(1);
1766               const IntSurf_PntOn2S& verPointFin = verwline->Point(verwline->NbPnts());
1767               if( (Point3dDebut.Distance(verPointDebut.Value()) <= TolTangency) &&
1768                   (Point3dFin.Distance(verPointFin.Value()) <= TolTangency))
1769               {
1770                 RejetLigne = Standard_True;
1771                 break;
1772               }
1773             }
1774
1775             if(RejetLigne)
1776             {
1777               DublicateOfLinesProcessing(PW, ver, SLin, RejetLigne);
1778             }
1779
1780             if(!RejetLigne) {
1781               IntSurf_TypeTrans trans1,trans2;
1782               Standard_Real locu,locv;
1783               gp_Vec norm1,norm2,d1u,d1v;
1784               gp_Pnt ptbid;
1785               Standard_Integer indextg;
1786               gp_Vec tgline(PW.TangentAtLine(indextg));
1787               PW.Line()->Value(indextg).ParametersOnS1(locu,locv);
1788               Surf1->D1(locu,locv,ptbid,d1u,d1v);
1789               norm1 = d1u.Crossed(d1v);
1790               PW.Line()->Value(indextg).ParametersOnS2(locu,locv);
1791               Surf2->D1(locu,locv,ptbid,d1u,d1v);
1792               norm2 = d1u.Crossed(d1v);
1793               if( tgline.DotCross(norm2,norm1) >= 0. ) {
1794                 trans1 = IntSurf_Out;
1795                 trans2 = IntSurf_In;
1796               }
1797               else {
1798                 trans1 = IntSurf_In;
1799                 trans2 = IntSurf_Out;
1800               }
1801
1802               Standard_Real TolTang = TolTangency;
1803               Handle(IntPatch_WLine) wline = new IntPatch_WLine(PW.Line(),Standard_False,trans1,trans2);
1804               wline->SetCreatingWayInfo(IntPatch_WLine::IntPatch_WLPrmPrm);
1805
1806               //the method PutVertexOnLine can reduce the number of points in <wline>
1807               IntPatch_RstInt::PutVertexOnLine(wline, Surf1, D1, Surf2, Standard_True, TolTang);
1808               if (wline->NbPnts() < 2)
1809                 continue;
1810               IntPatch_RstInt::PutVertexOnLine(wline, Surf2, D2, Surf1, Standard_False, TolTang);
1811               if (wline->NbPnts() < 2)
1812                 continue;
1813
1814               if(wline->NbVertex() == 0) {
1815                 IntPatch_Point vtx;
1816                 IntSurf_PntOn2S POn2S = PW.Line()->Value(1);
1817                 POn2S.Parameters(pu1,pv1,pu2,pv2);
1818                 vtx.SetValue(Point3dDebut,TolTang,Standard_False);
1819                 vtx.SetParameters(pu1,pv1,pu2,pv2);
1820                 vtx.SetParameter(1);
1821                 wline->AddVertex(vtx);
1822
1823                 POn2S = PW.Line()->Value(wline->NbPnts());
1824                 POn2S.Parameters(pu1,pv1,pu2,pv2);
1825                 vtx.SetValue(Point3dFin,TolTang,Standard_False);
1826                 vtx.SetParameters(pu1,pv1,pu2,pv2);
1827                 vtx.SetParameter(wline->NbPnts());
1828                 wline->AddVertex(vtx);
1829               }
1830
1831               SeveralWlinesProcessing(Surf1, Surf2, SLin, Periods, trans1, trans2,
1832                                       TolTang, Max(PW.MaxStep(0), PW.MaxStep(1)),
1833                                       Max(PW.MaxStep(2), PW.MaxStep(3)), wline);
1834
1835               AddWLine(SLin, wline, Deflection);
1836               empt = Standard_False;
1837             }// !RejetLigne
1838           }// PW points > 2
1839         }// done is True
1840       }// dminiPointLigne > SeuildPointLigne
1841     }// HasStartPoint
1842   }// for( IterLOP ...
1843   done = Standard_True;
1844   return;
1845 }
1846 //=======================================================================
1847 //function : Perform
1848 //purpose  :
1849 //=======================================================================
1850 void IntPatch_PrmPrmIntersection::Perform(const Handle(Adaptor3d_Surface)&    Surf1,
1851                                           const Handle(Adaptor3d_TopolTool)& D1,
1852                                           const Handle(Adaptor3d_Surface)&    Surf2,
1853                                           const Handle(Adaptor3d_TopolTool)& D2,
1854                                           const Standard_Real   U1Depart,
1855                                           const Standard_Real   V1Depart,
1856                                           const Standard_Real   U2Depart,
1857                                           const Standard_Real   V2Depart,
1858                                           const Standard_Real   TolTangency,
1859                                           const Standard_Real   Epsilon,
1860                                           const Standard_Real   Deflection,
1861                                           const Standard_Real   Increment)
1862 {
1863   //    Standard_Integer NbU1 = D1->NbSamplesU();
1864   //    Standard_Integer NbV1 = D1->NbSamplesV();
1865   //    Standard_Integer NbU2 = D2->NbSamplesU();
1866   //    Standard_Integer NbV2 = D2->NbSamplesV();
1867
1868   //-- Traitement des Lignes de sections
1869   empt = Standard_True;
1870   done = Standard_True;
1871   SLin.Clear();
1872
1873   //------------------------------------------------------------
1874
1875   Standard_Real pu1,pu2,pv1,pv2;
1876
1877   TColStd_Array1OfReal StartParams(1,4);
1878
1879   //    Standard_Integer MaxOscill = NbU1;
1880   //    if(MaxOscill < NbU2) MaxOscill=NbU2;
1881   //    if(MaxOscill < NbV1) MaxOscill=NbV1;
1882   //    if(MaxOscill < NbV2) MaxOscill=NbV2;
1883
1884   //    Standard_Real nIncrement=Increment;
1885   //    if(MaxOscill>10) {
1886   //  #ifdef OCCT_DEBUG
1887   //      std::cout<<"\n IntPatch_PrmPrmIntersection.gxx : Increment:"<<Increment<<" -> "<<Increment/(0.5*MaxOscill)<<std::endl;
1888   //  #endif
1889   //      nIncrement/=0.5*MaxOscill;
1890   //    }
1891
1892   IntWalk_PWalking PW(Surf1,Surf2,
1893     TolTangency,
1894     Epsilon,
1895     Deflection,
1896     Increment); //nIncrement);
1897
1898
1899   //Standard_Real    SeuildPointLigne = 15.0 * Increment * Increment; //-- 10 est insuffisant
1900   //Standard_Real    incidence;
1901   //Standard_Real    dminiPointLigne;
1902
1903   Standard_Boolean HasStartPoint;//,RejetLigne;
1904
1905   IntSurf_PntOn2S StartPOn2S;
1906
1907   //Standard_Integer ver;
1908
1909   gp_Pnt Point3dDebut,Point3dFin;
1910
1911   //------------------------------------------------------------
1912
1913   StartParams(1) = U1Depart;
1914   StartParams(2) = V1Depart;
1915   StartParams(3) = U2Depart;
1916   StartParams(4) = V2Depart;
1917
1918   //-----------------------------------------------------------------------
1919   //-- Calcul du premier point de cheminement a partir du point approche --
1920   //-----------------------------------------------------------------------
1921   HasStartPoint = PW.PerformFirstPoint(StartParams,StartPOn2S);
1922   if(HasStartPoint) {
1923     //-------------------------------------------------
1924     //-- Un point a ete trouve                       --
1925     //-- On verifie qu il n appartient pas           --
1926     //--  a une ligne de cheminement deja calculee.  --
1927     //-------------------------------------------------
1928
1929     PW.Perform(StartParams);
1930     if(PW.IsDone()) {
1931       if(PW.NbPoints()>2) {
1932         Point3dDebut = PW.Value(1).Value();
1933         Point3dFin   = PW.Value(PW.NbPoints()).Value();
1934
1935         IntSurf_TypeTrans trans1,trans2;
1936         Standard_Real locu,locv;
1937         gp_Vec norm1,norm2,d1u,d1v;
1938         gp_Pnt ptbid;
1939         Standard_Integer indextg;
1940         gp_Vec tgline(PW.TangentAtLine(indextg));
1941         PW.Line()->Value(indextg).ParametersOnS1(locu,locv);
1942         Surf1->D1(locu,locv,ptbid,d1u,d1v);
1943         norm1 = d1u.Crossed(d1v);
1944         PW.Line()->Value(indextg).ParametersOnS2(locu,locv);
1945         Surf2->D1(locu,locv,ptbid,d1u,d1v);
1946         norm2 = d1u.Crossed(d1v);
1947         if (tgline.DotCross(norm2,norm1)>0.) {
1948           trans1 = IntSurf_Out;
1949           trans2 = IntSurf_In;
1950         }
1951         else {
1952           trans1 = IntSurf_In;
1953           trans2 = IntSurf_Out;
1954         }
1955
1956         Standard_Real TolTang = TolTangency;
1957         Handle(IntPatch_WLine) wline = new IntPatch_WLine(PW.Line(),Standard_False,trans1,trans2);
1958         wline->SetCreatingWayInfo(IntPatch_WLine::IntPatch_WLPrmPrm);
1959
1960         //the method PutVertexOnLine can reduce the number of points in <wline>
1961         IntPatch_RstInt::PutVertexOnLine(wline,Surf1,D1,Surf2,Standard_True,TolTang);
1962         if (wline->NbPnts() < 2)
1963           return;
1964         IntPatch_RstInt::PutVertexOnLine(wline,Surf2,D2,Surf1,Standard_False,TolTang);
1965         if (wline->NbPnts() < 2)
1966           return;
1967
1968         //---------------
1969         if(wline->NbVertex() == 0) {
1970           IntPatch_Point vtx;
1971           IntSurf_PntOn2S POn2S = PW.Line()->Value(1);
1972           POn2S.Parameters(pu1,pv1,pu2,pv2);
1973           vtx.SetValue(Point3dDebut,TolTang,Standard_False);
1974           vtx.SetParameters(pu1,pv1,pu2,pv2);
1975           vtx.SetParameter(1);
1976           wline->AddVertex(vtx);
1977
1978           POn2S = PW.Line()->Value(wline->NbPnts());
1979           POn2S.Parameters(pu1,pv1,pu2,pv2);
1980           vtx.SetValue(Point3dFin,TolTang,Standard_False);
1981           vtx.SetParameters(pu1,pv1,pu2,pv2);
1982           vtx.SetParameter(wline->NbPnts());
1983           wline->AddVertex(vtx);
1984         }
1985
1986         //---------------
1987         SLin.Append(wline);
1988         empt = Standard_False;
1989       } //if(PW.NbPoints()>2)
1990     } //if(PW.IsDone())
1991   } //if(HasStartPoint)
1992 }
1993 //==================================================================================
1994 // function : AdjustOnPeriodic
1995 // purpose  :
1996 //==================================================================================
1997 void AdjustOnPeriodic(const Handle(Adaptor3d_Surface)& Surf1,
1998                       const Handle(Adaptor3d_Surface)& Surf2,
1999                       IntPatch_SequenceOfLine& aSLin)
2000 {
2001   Standard_Boolean bIsPeriodic[4], bModified, bIsNull, bIsPeriod;
2002   Standard_Integer i, j, k, aNbLines, aNbPx, aIndx, aIndq;
2003   Standard_Real aPeriod[4], dPeriod[4], ux[4], uq[4], aEps, du;
2004   //
2005   aEps=Precision::Confusion();
2006   //
2007   for (k=0; k<4; ++k) {
2008     aPeriod[k]=0.;
2009   }
2010   //
2011   bIsPeriodic[0]=Surf1->IsUPeriodic();
2012   bIsPeriodic[1]=Surf1->IsVPeriodic();
2013   bIsPeriodic[2]=Surf2->IsUPeriodic();
2014   bIsPeriodic[3]=Surf2->IsVPeriodic();
2015   //
2016   if (bIsPeriodic[0]){
2017     aPeriod[0]=Surf1->UPeriod();
2018   }
2019   if (bIsPeriodic[1]){
2020     aPeriod[1]=Surf1->VPeriod();
2021   }
2022   if (bIsPeriodic[2]){
2023     aPeriod[2]=Surf2->UPeriod();
2024   }
2025   if (bIsPeriodic[3]){
2026     aPeriod[3]=Surf2->VPeriod();
2027   }
2028   //
2029   for (k=0; k<4; ++k) {
2030     dPeriod[k]=0.25*aPeriod[k];
2031   }
2032   //
2033   aNbLines=aSLin.Length();
2034   for (i=1; i<=aNbLines; ++i) {
2035     Handle(IntPatch_WLine) aIL=Handle(IntPatch_WLine)::DownCast(aSLin.Value(i));
2036     Handle(IntSurf_LineOn2S) aL=aIL->Curve();
2037
2038     aNbPx=aL->NbPoints();
2039     if (aNbPx<10) {
2040       continue;
2041     }
2042     //
2043     for (j=0; j<2; ++j) {
2044       bModified=Standard_False;
2045       aIndx=1;
2046       aIndq=2;
2047       if (j) {
2048         aIndx=aNbPx;
2049         aIndq=aNbPx-1;
2050       }
2051       //
2052       const IntSurf_PntOn2S& aPSx=aL->Value(aIndx);
2053       const IntSurf_PntOn2S& aPSq=aL->Value(aIndq);
2054       //
2055       aPSx.Parameters(ux[0], ux[1], ux[2], ux[3]);
2056       aPSq.Parameters(uq[0], uq[1], uq[2], uq[3]);
2057       //
2058       for (k=0; k<4; ++k) {
2059         bIsNull=Standard_False;
2060         bIsPeriod=Standard_False;
2061         //
2062         if (!bIsPeriodic[k]) {
2063           continue;
2064         }
2065         //
2066         if (fabs(ux[k])<aEps) {
2067           bModified=Standard_True;
2068           bIsNull=Standard_True;
2069         }
2070         //
2071         else if (fabs(ux[k]-aPeriod[k])<aEps) {
2072           bModified=Standard_True;
2073           bIsPeriod=Standard_True;
2074         }
2075         //
2076         if (bModified) {
2077           du=fabs(ux[k]-uq[k]);
2078           if (du > dPeriod[k]) {
2079             if(bIsNull){
2080               ux[k]=aPeriod[k];
2081             }
2082             if(bIsPeriod) {
2083               ux[k]=0.;
2084             }
2085           }
2086         }
2087       }//for (k=0; k<4; ++k)
2088       if (bModified) {
2089         IntSurf_PntOn2S aPntOn2S;
2090         //
2091         aPntOn2S=aPSx;
2092         aPntOn2S.SetValue(ux[0], ux[1], ux[2], ux[3]);
2093         aL->Value(aIndx, aPntOn2S);
2094       }
2095     }//for (j=0; j<1; ++j) {
2096   }//for (i=1; i<=aNbLines; ++i)
2097 }
2098
2099 //==================================================================================
2100 // function : MakeNewPoint
2101 // purpose  :
2102 //==================================================================================
2103 IntSurf_PntOn2S MakeNewPoint(const IntSurf_PntOn2S& replacePnt,
2104                              const IntSurf_PntOn2S& oldPnt,
2105                              const Standard_Real* Periods)
2106 {
2107   IntSurf_PntOn2S NewPoint;
2108   NewPoint.SetValue(replacePnt.Value());
2109
2110   Standard_Real OldParams[4], NewParams[4];
2111   oldPnt.Parameters(OldParams[0], OldParams[1], OldParams[2], OldParams[3]);
2112   replacePnt.Parameters(NewParams[0], NewParams[1], NewParams[2], NewParams[3]);
2113
2114   Standard_Integer i;
2115   for (i = 0; i < 4; i++)
2116   {
2117     if (Periods[i] != 0.)
2118     {
2119       if (Abs(NewParams[i] - OldParams[i]) >= 0.5*Periods[i])
2120       {
2121         if (NewParams[i] < OldParams[i])
2122           NewParams[i] += Periods[i];
2123         else
2124           NewParams[i] -= Periods[i];
2125       }
2126     }
2127   }
2128
2129   NewPoint.SetValue(NewParams[0], NewParams[1], NewParams[2], NewParams[3]);
2130   return NewPoint;
2131 }
2132
2133 //==================================================================================
2134 // function : Perform
2135 // purpose  : base SS Int. function
2136 //==================================================================================
2137 void IntPatch_PrmPrmIntersection::Perform (const Handle(Adaptor3d_Surface)& Surf1,
2138                                            const Handle(Adaptor3d_TopolTool)& D1,
2139                                            const Handle(Adaptor3d_Surface)& Surf2,
2140                                            const Handle(Adaptor3d_TopolTool)& D2,
2141                                            const Standard_Real   TolTangency,
2142                                            const Standard_Real   Epsilon,
2143                                            const Standard_Real   Deflection,
2144                                            const Standard_Real   Increment,
2145                                            const Standard_Boolean ClearFlag)
2146 {
2147   Standard_Integer Limit = 2500;
2148   Standard_Integer NbU1 = 10, NbV1 = 10, NbU2 = 10, NbV2 = 10;
2149   //
2150   D1->SamplePnts(Deflection, NbU1, NbV1);
2151   D2->SamplePnts(Deflection, NbU2, NbV2);
2152   //
2153   NbU1 = D1->NbSamplesU();
2154   NbV1 = D1->NbSamplesV();
2155   NbU2 = D2->NbSamplesU();
2156   NbV2 = D2->NbSamplesV();
2157
2158   TColStd_Array1OfReal anUpars1(1, NbU1), aVpars1(1, NbV1);
2159   TColStd_Array1OfReal anUpars2(1, NbU2), aVpars2(1, NbV2);
2160   //
2161   D1->UParameters(anUpars1);
2162   D1->VParameters(aVpars1);
2163   D2->UParameters(anUpars2);
2164   D2->VParameters(aVpars2);
2165
2166   Standard_Real Periods [4];
2167   Periods[0] = (Surf1->IsUPeriodic())? Surf1->UPeriod() : 0.;
2168   Periods[1] = (Surf1->IsVPeriodic())? Surf1->VPeriod() : 0.;
2169   Periods[2] = (Surf2->IsUPeriodic())? Surf2->UPeriod() : 0.;
2170   Periods[3] = (Surf2->IsVPeriodic())? Surf2->VPeriod() : 0.;
2171
2172   //---------------------------------------------
2173   if((NbU1*NbV1<=Limit && NbV2*NbU2<=Limit))
2174   {
2175     empt = Standard_True;
2176     if (ClearFlag)
2177     {
2178       SLin.Clear();
2179     }
2180     //
2181     IntPolyh_Intersection* pInterference = NULL;
2182
2183     if ( D1->IsUniformSampling() || D2->IsUniformSampling() )
2184     {
2185       pInterference = new IntPolyh_Intersection(Surf1,NbU1,NbV1,Surf2,NbU2,NbV2);
2186     }
2187     else
2188     {
2189       pInterference = new IntPolyh_Intersection(Surf1, anUpars1, aVpars1,
2190         Surf2, anUpars2, aVpars2 );
2191     }
2192
2193     if ( !pInterference )
2194     {
2195       done = Standard_False;
2196       return;
2197     }
2198     //
2199     IntPolyh_Intersection& Interference = *pInterference;
2200     //
2201     done = Interference.IsDone();
2202     if( !done )
2203     {
2204       if (pInterference)
2205       {
2206         delete pInterference;
2207         pInterference = NULL;
2208       }
2209
2210       return;
2211     }
2212
2213     Standard_Integer nbLigSec = Interference.NbSectionLines();
2214     Standard_Integer nbTanZon = Interference.NbTangentZones();
2215     Standard_Real SeuildPointLigne = 15.0 * Increment * Increment;
2216
2217     Standard_Integer NbLigCalculee = 0, ver;
2218     Standard_Real pu1,pu2,pv1,pv2, incidence, dminiPointLigne;
2219     Standard_Boolean HasStartPoint = Standard_False, RejectLine = Standard_False;
2220     IntSurf_PntOn2S StartPOn2S;
2221     gp_Pnt Point3dDebut,Point3dFin;
2222
2223     TColStd_Array1OfReal StartParams(1,4);
2224     IntWalk_PWalking PW(Surf1,Surf2,TolTangency,Epsilon,Deflection,Increment);
2225
2226     if(nbLigSec>=1)
2227     {
2228       Standard_Integer *TabL = new Standard_Integer [nbLigSec+1];
2229       for(Standard_Integer ls=1; ls<=nbLigSec; ++ls)
2230       {
2231         TabL[ls]=ls;
2232       }
2233       //----------------------------------------1.1
2234       {
2235         Standard_Boolean triok;
2236         Standard_Integer nb_A, nb_B, tyu;
2237         do
2238         {
2239           triok=Standard_True;
2240           for(Standard_Integer b = 2; b <= nbLigSec; ++b )
2241           {
2242             nb_B = Interference.NbPointsInLine(TabL[b]);
2243             nb_A = Interference.NbPointsInLine(TabL[b-1]);
2244
2245             if( nb_B > nb_A )
2246             {
2247               tyu=TabL[b];
2248               TabL[b]=TabL[b-1];
2249               TabL[b-1]=tyu;
2250               triok=Standard_False;
2251             }
2252           }
2253         }
2254         while(triok==Standard_False);
2255       }
2256
2257       //----------------------------------------
2258       // 1.2 For the line "ls" get 2D-bounds U,V for surfaces 1,2
2259       //
2260       for(Standard_Integer ls = 1; ls <= nbLigSec; ++ls)
2261       {
2262         Standard_Integer nbp = Interference.NbPointsInLine(TabL[ls]);
2263         if (!nbp)
2264         {
2265           continue;
2266         }
2267         //
2268         Standard_Integer *TabPtDep = new Standard_Integer [nbp+1];
2269         for(Standard_Integer ilig = 1; ilig <= nbp; ++ilig )
2270         {
2271           TabPtDep[ilig]=0;
2272         }
2273         //
2274         Standard_Real UminLig1,VminLig1,UmaxLig1,VmaxLig1;
2275         Standard_Real UminLig2,VminLig2,UmaxLig2,VmaxLig2;
2276         Standard_Real _x,_y,_z;
2277         //
2278         Interference.GetLinePoint(TabL[ls], 1, _x, _y, _z,
2279           UminLig1, VminLig1, UminLig2, VminLig2,
2280           incidence);
2281
2282         UmaxLig1=UminLig1;
2283         VmaxLig1=VminLig1;
2284         UmaxLig2=UminLig2;
2285         VmaxLig2=VminLig2;
2286         //
2287         for(Standard_Integer ilig = 2; ilig <= nbp; ilig++ )
2288         {
2289           Standard_Real U1, U2, V1, V2;
2290           Interference.GetLinePoint(TabL[ls],ilig,_x,_y,_z,U1,V1,U2,V2,incidence);
2291           //
2292           if(U1>UmaxLig1) UmaxLig1=U1;
2293           if(V1>VmaxLig1) VmaxLig1=V1;
2294           if(U2>UmaxLig2) UmaxLig2=U2;
2295           if(V2>VmaxLig2) VmaxLig2=V2;
2296           //
2297           if(U1<UminLig1) UminLig1=U1;
2298           if(V1<VminLig1) VminLig1=V1;
2299           if(U2<UminLig2) UminLig2=U2;
2300           if(V2<VminLig2) VminLig2=V2;
2301         }//for( ilig = 2; ilig <= nbp; ilig++ ) {
2302         //
2303         //----------------------------------------
2304         // 1.3
2305         Standard_Integer nbps2 = (nbp>3)? (nbp/2) :  1;
2306         Standard_Integer NombreDePointsDeDepartDuCheminement = 0;
2307         Standard_Boolean lignetrouvee=Standard_False;
2308         const Standard_Integer NbDePointsDeDepartDuChmLimit = 5;
2309         //
2310         do
2311         {
2312           NombreDePointsDeDepartDuCheminement++;
2313           switch (NombreDePointsDeDepartDuCheminement)
2314           {
2315           case 1:
2316             nbps2 = (nbp > 1) ? nbp/2 : 1;
2317             if(nbp<3)
2318               NombreDePointsDeDepartDuCheminement = NbDePointsDeDepartDuChmLimit;
2319
2320             break;
2321           case 2:
2322             nbps2 = 1;
2323             break;
2324           case 3:
2325             nbps2 = nbp-1;
2326             break;
2327
2328           case 4:
2329             nbps2 = 3 * nbp / 4;
2330             break;
2331
2332           case 5:
2333             nbps2 = nbp / 4;
2334             break;
2335           default:
2336             nbps2 = NombreDePointsDeDepartDuCheminement-3;
2337             NombreDePointsDeDepartDuCheminement++;
2338           }
2339
2340           //
2341           if(TabPtDep[nbps2] == 0)
2342           {
2343             Standard_Real U1, U2, V1, V2;
2344
2345             TabPtDep[nbps2] = 1;
2346             Interference.GetLinePoint(TabL[ls],nbps2,_x,_y,_z,U1,V1,U2,V2,incidence);
2347
2348             StartParams(1) = U1;
2349             StartParams(2) = V1;
2350             StartParams(3) = U2;
2351             StartParams(4) = V2;
2352
2353             HasStartPoint = PW.PerformFirstPoint(StartParams,StartPOn2S);
2354             dminiPointLigne = SeuildPointLigne + SeuildPointLigne;
2355             if(HasStartPoint)
2356             {
2357               StartPOn2S.Parameters(pu1,pv1,pu2,pv2);
2358               NbLigCalculee = SLin.Length();
2359               Standard_Integer l;
2360               for( l = 1; (l <= NbLigCalculee) && (dminiPointLigne >= SeuildPointLigne); l++)
2361               {
2362                 const Handle(IntPatch_WLine)& testwline = *((Handle(IntPatch_WLine)*)&SLin.Value(l));
2363
2364                 if (IsPointOnLine(StartPOn2S, testwline, Deflection))
2365                 {
2366                   dminiPointLigne = 0.0;
2367                 }
2368               }// for( l ...
2369
2370               if(dminiPointLigne > SeuildPointLigne)
2371               {
2372                 PW.Perform(StartParams, UminLig1, VminLig1, UminLig2, VminLig2,
2373                   UmaxLig1, VmaxLig1, UmaxLig2, VmaxLig2);
2374
2375                 //
2376                 Standard_Boolean bPWIsDone;
2377                 Standard_Real aD11, aD12, aD21, aD22, aDx;
2378                 //
2379                 bPWIsDone=PW.IsDone();
2380
2381                 if(bPWIsDone)
2382                 {
2383                   Standard_Boolean hasBeenAdded = Standard_False;
2384                   if(PW.NbPoints() > 2 )
2385                   {
2386                     //Try to extend the intersection line to the boundary,
2387                     //if it is possibly
2388                     PW.PutToBoundary(Surf1, Surf2);
2389
2390                     const Standard_Integer aMinNbPoints = 40;
2391                     if(PW.NbPoints() < aMinNbPoints)
2392                     {
2393                       hasBeenAdded = PW.SeekAdditionalPoints(Surf1, Surf2, aMinNbPoints);
2394                     }
2395
2396                     Standard_Integer iPWNbPoints = PW.NbPoints(), aNbPointsVer = 0;
2397                     RejectLine = Standard_False;
2398                     Point3dDebut = PW.Value(1).Value();
2399                     Point3dFin = PW.Value(iPWNbPoints).Value();
2400                     for( ver = 1; (!RejectLine) && (ver<= NbLigCalculee); ++ver)
2401                     {
2402                       const Handle(IntPatch_WLine)& verwline = *((Handle(IntPatch_WLine)*)&SLin.Value(ver));
2403                       //
2404                       aNbPointsVer=verwline->NbPnts();
2405                       if (aNbPointsVer<3)
2406                       {
2407                         continue;
2408                       }
2409                       //
2410                       const IntSurf_PntOn2S& verPointDebut = verwline->Point(1);
2411                       const IntSurf_PntOn2S& verPointFin = verwline->Point(verwline->NbPnts());
2412                       //xf
2413                       const gp_Pnt& aP21=verPointDebut.Value();
2414                       const gp_Pnt& aP22=verPointFin.Value();
2415                       //
2416                       aD11=Point3dDebut.Distance(aP21);
2417                       aD12=Point3dDebut.Distance(aP22);
2418                       aD21=Point3dFin.Distance(aP21);
2419                       aD22=Point3dFin.Distance(aP22);
2420                       //
2421                       if((aD11<=TolTangency && aD22<=TolTangency) ||
2422                         (aD12<=TolTangency && aD21<=TolTangency))
2423                       {
2424                         Standard_Integer m, mx;
2425                         //
2426                         mx=aNbPointsVer/2;
2427                         if (aNbPointsVer%2)
2428                         {
2429                           ++mx;
2430                         }
2431                         //
2432                         const gp_Pnt& aPx=verwline->Point(mx).Value();
2433                         for(m=1; m<iPWNbPoints; ++m)
2434                         {
2435                           const gp_Pnt& aP1=PW.Value(m).Value();
2436                           const gp_Pnt& aP2=PW.Value(m+1).Value();
2437                           gp_Vec aVec12(aP1, aP2);
2438                           if (aVec12.SquareMagnitude()<1.e-20)
2439                           {
2440                             continue;
2441                           }
2442
2443                           //
2444                           gp_Dir aDir12(aVec12);
2445                           gp_Lin aLin12(aP1, aDir12);
2446                           aDx=aLin12.Distance(aPx);
2447
2448                           //modified by NIZNHY-PKV Tue May 10 11:08:07 2011f
2449                           if (aDx<=2.*Epsilon)
2450                           {
2451                             //if (aDx<=TolTangency) {
2452                             //modified by NIZNHY-PKV Tue May 10 11:08:13 2011t
2453
2454                             RejectLine = Standard_True;
2455                             ver--;
2456                             break;
2457                           }
2458                         }//for(m=1; m<iPWNbPoints; ++m){
2459                       }//if((aD11<=TolTangency && aD22<=TolTangency) ||...
2460                     }// for( ver = 1 ; (!RejetLigne) && (ver<= NbLigCalculee) ; ver++) {
2461                     //
2462
2463                     if(RejectLine)
2464                     {
2465                       DublicateOfLinesProcessing(PW, ver, SLin, RejectLine);
2466                     }
2467
2468                     if(!RejectLine)
2469                     {
2470                       IntSurf_TypeTrans trans1,trans2;
2471                       Standard_Real locu,locv;
2472                       gp_Vec norm1,norm2,d1u,d1v;
2473                       gp_Pnt ptbid;
2474                       Standard_Integer indextg;
2475                       gp_Vec tgline(PW.TangentAtLine(indextg));
2476                       PW.Line()->Value(indextg).ParametersOnS1(locu,locv);
2477                       Surf1->D1(locu,locv,ptbid,d1u,d1v);
2478                       norm1 = d1u.Crossed(d1v);
2479                       PW.Line()->Value(indextg).ParametersOnS2(locu,locv);
2480                       Surf2->D1(locu,locv,ptbid,d1u,d1v);
2481                       norm2 = d1u.Crossed(d1v);
2482                       if( tgline.DotCross(norm2,norm1) >= 0. )
2483                       {
2484                         trans1 = IntSurf_Out;
2485                         trans2 = IntSurf_In;
2486                       }
2487                       else
2488                       {
2489                         trans1 = IntSurf_In;
2490                         trans2 = IntSurf_Out;
2491                       }
2492
2493                       Standard_Real TolTang = TolTangency;
2494                       Handle(IntPatch_WLine) wline = new IntPatch_WLine(PW.Line(),Standard_False,trans1,trans2);
2495                       wline->SetCreatingWayInfo(IntPatch_WLine::IntPatch_WLPrmPrm);
2496                       wline->EnablePurging(!hasBeenAdded);
2497                       //the method PutVertexOnLine can reduce the number of points in <wline>
2498                       IntPatch_RstInt::PutVertexOnLine(wline,Surf1,D1,Surf2,Standard_True,TolTang);
2499                       if (wline->NbPnts() < 2)
2500                         continue;
2501                       IntPatch_RstInt::PutVertexOnLine(wline,Surf2,D2,Surf1,Standard_False,TolTang);
2502                       if (wline->NbPnts() < 2)
2503                         continue;
2504                       if(wline->NbVertex() == 0)
2505                       {
2506                         IntPatch_Point vtx;
2507                         IntSurf_PntOn2S POn2S = PW.Line()->Value(1);
2508                         POn2S.Parameters(pu1,pv1,pu2,pv2);
2509                         vtx.SetValue(Point3dDebut,TolTang,Standard_False);
2510                         vtx.SetParameters(pu1,pv1,pu2,pv2);
2511                         vtx.SetParameter(1);
2512                         wline->AddVertex(vtx);
2513
2514                         POn2S = PW.Line()->Value(wline->NbPnts());
2515                         POn2S.Parameters(pu1,pv1,pu2,pv2);
2516                         vtx.SetValue(Point3dFin,TolTang,Standard_False);
2517                         vtx.SetParameters(pu1,pv1,pu2,pv2);
2518                         vtx.SetParameter(wline->NbPnts());
2519                         wline->AddVertex(vtx);
2520                       }
2521
2522                       lignetrouvee = Standard_True;
2523
2524                       SeveralWlinesProcessing(Surf1, Surf2, SLin, Periods, trans1, trans2,
2525                                               TolTang, Max(PW.MaxStep(0), PW.MaxStep(1)),
2526                                               Max(PW.MaxStep(2), PW.MaxStep(3)), wline);
2527
2528                       AddWLine(SLin, wline, Deflection);
2529                       empt = Standard_False;
2530                     }// !RejetLigne
2531                   }// PW points > 2
2532                 }// done is True
2533               }// dminiPointLigne > SeuildPointLigne
2534             }// HasStartPoint
2535           }// if TabPtDep[nbps2] == 0
2536         } while(nbp>5 && !( (NombreDePointsDeDepartDuCheminement >= NbDePointsDeDepartDuChmLimit && lignetrouvee) ||
2537           (NombreDePointsDeDepartDuCheminement-3 >= nbp && (!lignetrouvee))));
2538         delete [] TabPtDep;
2539       }// for( ls ...
2540
2541       delete [] TabL;
2542
2543     }// if nbLigSec >= 1
2544     //
2545     AdjustOnPeriodic(Surf1, Surf2, SLin);
2546     //
2547
2548     //--------------------------------------------------------------------
2549     //-- Calcul des parametres approches a partir des Zones De Tangence --
2550     //--------------------------------------------------------------------
2551     Standard_Real UminLig1,VminLig1,UmaxLig1,VmaxLig1;
2552     Standard_Real UminLig2,VminLig2,UmaxLig2,VmaxLig2;
2553
2554     UminLig1=VminLig1=UminLig2=VminLig2=RealLast();
2555     UmaxLig1=VmaxLig1=UmaxLig2=VmaxLig2=-UminLig1;
2556
2557     // NbPointsInTangentZone always == 1 (eap)
2558
2559     Standard_Integer z;
2560     for( z=1; z <= nbTanZon; z++)
2561     {
2562       //Standard_Integer NbPointsInTangentZone=Interference.NbPointsInTangentZone(z);
2563       //for(Standard_Integer pz=1; pz<=NbPointsInTangentZone; pz++) {
2564       Standard_Integer pz=1;
2565       Standard_Real _x,_y,_z;
2566       Standard_Real U1, U2, V1, V2;
2567       Interference.GetTangentZonePoint(z,pz,_x,_y,_z,U1,V1,U2,V2);
2568
2569       if(U1>UmaxLig1) UmaxLig1=U1;
2570       if(V1>VmaxLig1) VmaxLig1=V1;
2571       if(U2>UmaxLig2) UmaxLig2=U2;
2572       if(V2>VmaxLig2) VmaxLig2=V2;
2573
2574       if(U1<UminLig1) UminLig1=U1;
2575       if(V1<VminLig1) VminLig1=V1;
2576       if(U2<UminLig2) UminLig2=U2;
2577       if(V2<VminLig2) VminLig2=V2;
2578       //}
2579     }
2580
2581     for(z=1; z <= nbTanZon; z++)
2582     {
2583       //Standard_Integer NbPointsInTangentZone=Interference.NbPointsInTangentZone(z);
2584       //for(Standard_Integer pz=1; pz<=NbPointsInTangentZone; pz++) {
2585       Standard_Integer pz=1;
2586       Standard_Real _x,_y,_z;
2587       Standard_Real U1, U2, V1, V2;
2588       Interference.GetTangentZonePoint(z,pz,_x,_y,_z,U1,V1,U2,V2);
2589
2590       StartParams(1) = U1;
2591       StartParams(2) = V1;
2592       StartParams(3) = U2;
2593       StartParams(4) = V2;
2594
2595       //-----------------------------------------------------------------------
2596       //-- Calcul du premier point de cheminement a partir du point approche --
2597       //-----------------------------------------------------------------------
2598       HasStartPoint = PW.PerformFirstPoint(StartParams,StartPOn2S);
2599       if(HasStartPoint)
2600       {
2601         //-------------------------------------------------
2602         //-- Un point a ete trouve                       --
2603         //-- On verifie qu il n appartient pas           --
2604         //--  a une ligne de cheminement deja calculee.  --
2605         //-------------------------------------------------
2606         StartPOn2S.Parameters(pu1,pv1,pu2,pv2);
2607
2608         NbLigCalculee = SLin.Length();
2609         dminiPointLigne = SeuildPointLigne + SeuildPointLigne;
2610
2611         for(Standard_Integer l=1;
2612           (l <= NbLigCalculee) && (dminiPointLigne >= SeuildPointLigne);
2613           l++)
2614         {
2615           const Handle(IntPatch_WLine)& testwline = *((Handle(IntPatch_WLine)*)&SLin.Value(l));
2616
2617           if (IsPointOnLine(StartPOn2S, testwline, Deflection))
2618           {
2619             dminiPointLigne = 0.0;
2620           }
2621         }
2622
2623         //-- Fin d exploration des lignes
2624         if(dminiPointLigne > SeuildPointLigne)
2625         {
2626           //---------------------------------------------------
2627           //-- Le point de depart du nouveau cheminement     --
2628           //-- n est present dans aucune ligne deja calculee.--
2629           //---------------------------------------------------
2630           PW.Perform(StartParams,UminLig1,VminLig1,UminLig2,VminLig2,
2631             UmaxLig1,VmaxLig1,UmaxLig2,VmaxLig2);
2632
2633           if(PW.IsDone())
2634           {
2635             Standard_Boolean hasBeenAdded = Standard_False;
2636             if(PW.NbPoints()>2)
2637             {
2638               const Standard_Integer aMinNbPoints = 40;
2639               if(PW.NbPoints() < aMinNbPoints)
2640               {
2641                 hasBeenAdded = PW.SeekAdditionalPoints(Surf1, Surf2, aMinNbPoints);
2642               }
2643
2644               //-----------------------------------------------
2645               //-- Verification a posteriori :
2646               //-- On teste si le point de depart et de fin de
2647               //-- la ligne de cheminement est present dans une
2648               //-- autre ligne .
2649               //-----------------------------------------------
2650               RejectLine = Standard_False;
2651               Point3dDebut = PW.Value(1).Value();
2652               const IntSurf_PntOn2S& PointFin = PW.Value(PW.NbPoints());
2653               Point3dFin   = PointFin.Value();
2654
2655               for(ver=1 ; (!RejectLine) && (ver<= NbLigCalculee) ; ver++)
2656               {
2657                 const Handle(IntPatch_WLine)& verwline = *((Handle(IntPatch_WLine)*)&SLin.Value(ver));
2658                 //-- Handle(IntPatch_WLine) verwline=Handle(IntPatch_WLine)::DownCast(SLin.Value(ver));
2659
2660                 // Check end point if it is on existing line.
2661                 // Start point is checked before.
2662                 if (IsPointOnLine(PointFin, verwline, Deflection))
2663                 {
2664                   RejectLine = Standard_True;
2665                   break;
2666                 }
2667
2668                 const IntSurf_PntOn2S& verPointDebut = verwline->Point(1);
2669                 const IntSurf_PntOn2S& verPointFin   = verwline->Point(verwline->NbPnts());
2670                 if(Point3dDebut.Distance(verPointDebut.Value()) < TolTangency)
2671                 {
2672                   RejectLine = Standard_True;
2673                 }
2674                 else
2675                 {
2676                   if(Point3dFin.Distance(verPointFin.Value()) < TolTangency)
2677                   {
2678                     RejectLine = Standard_True;
2679                   }
2680                 }
2681               }
2682
2683               if(!RejectLine)
2684               {
2685                 IntSurf_TypeTrans trans1,trans2;
2686                 Standard_Real locu,locv;
2687                 gp_Vec norm1,norm2,d1u,d1v;
2688                 gp_Pnt ptbid;
2689                 Standard_Integer indextg;
2690                 gp_Vec tgline(PW.TangentAtLine(indextg));
2691                 PW.Line()->Value(indextg).ParametersOnS1(locu,locv);
2692                 Surf1->D1(locu,locv,ptbid,d1u,d1v);
2693                 norm1 = d1u.Crossed(d1v);
2694                 PW.Line()->Value(indextg).ParametersOnS2(locu,locv);
2695                 Surf2->D1(locu,locv,ptbid,d1u,d1v);
2696                 norm2 = d1u.Crossed(d1v);
2697                 if (tgline.DotCross(norm2,norm1)>0.)
2698                 {
2699                   trans1 = IntSurf_Out;
2700                   trans2 = IntSurf_In;
2701                 }
2702                 else
2703                 {
2704                   trans1 = IntSurf_In;
2705                   trans2 = IntSurf_Out;
2706                 }
2707
2708                 Standard_Real TolTang = TolTangency;
2709                 Handle(IntPatch_WLine) wline = new IntPatch_WLine(PW.Line(),Standard_False,trans1,trans2);
2710                 wline->SetCreatingWayInfo(IntPatch_WLine::IntPatch_WLPrmPrm);
2711                 wline->EnablePurging(!hasBeenAdded);
2712                 //the method PutVertexOnLine can reduce the number of points in <wline>
2713                 IntPatch_RstInt::PutVertexOnLine(wline,Surf1,D1,Surf2,Standard_True,TolTang);
2714                 if (wline->NbPnts() < 2)
2715                   continue;
2716                 IntPatch_RstInt::PutVertexOnLine(wline,Surf2,D2,Surf1,Standard_False,TolTang);
2717                 if (wline->NbPnts() < 2)
2718                   continue;
2719
2720                 //---------------
2721                 if(wline->NbVertex() == 0)
2722                 {
2723                   IntPatch_Point vtx;
2724                   IntSurf_PntOn2S POn2S = PW.Line()->Value(1);
2725                   POn2S.Parameters(pu1,pv1,pu2,pv2);
2726                   vtx.SetValue(Point3dDebut,TolTang,Standard_False);
2727                   vtx.SetParameters(pu1,pv1,pu2,pv2);
2728                   vtx.SetParameter(1);
2729                   wline->AddVertex(vtx);
2730
2731                   POn2S = PW.Line()->Value(wline->NbPnts());
2732                   POn2S.Parameters(pu1,pv1,pu2,pv2);
2733                   vtx.SetValue(Point3dFin,TolTang,Standard_False);
2734                   vtx.SetParameters(pu1,pv1,pu2,pv2);
2735                   vtx.SetParameter(wline->NbPnts());
2736                   wline->AddVertex(vtx);
2737                 }
2738
2739                 //---------------
2740                 AddWLine(SLin, wline, Deflection);
2741                 empt = Standard_False;
2742               }
2743               else
2744               {
2745                 //-- std::cout<<" ----- REJET DE LIGNE (POINT DE DEPART) ----- "<<std::endl;
2746               }
2747               //------------------------------------------------------------
2748             }
2749           }  //--  le cheminement a reussi (done a True)
2750         }  //--  le point approche ne renvoie pas sur une ligne existante
2751       } //-- Si HasStartPoint
2752       //} //-- Boucle Sur les Points de la Tangent Zone
2753     } //-- Boucle sur Les Tangent Zones
2754
2755     if ( pInterference )
2756     {
2757       delete pInterference;
2758       pInterference = NULL;
2759     }
2760
2761     return;
2762   }// if((NbU1*NbV1<=Limit && NbV2*NbU2<=Limit)) {
2763
2764   Handle(IntSurf_LineOn2S) LOn2S = new IntSurf_LineOn2S();
2765   PointDepart( LOn2S, Surf1, NbU1, NbV1, Surf2, NbU2, NbV2 );
2766   empt = Standard_True;
2767   done = Standard_True;
2768
2769   Standard_Integer NbLigCalculee = 0;
2770   Standard_Real U1,U2,V1,V2;
2771   Standard_Real pu1,pu2,pv1,pv2;
2772
2773   TColStd_Array1OfReal StartParams(1,4);
2774   Standard_Integer MaxOscill = NbU1;
2775   if(MaxOscill < NbU2) MaxOscill=NbU2;
2776   if(MaxOscill < NbV1) MaxOscill=NbV1;
2777   if(MaxOscill < NbV2) MaxOscill=NbV2;
2778
2779   Standard_Real nIncrement=Increment;
2780   //if(MaxOscill>10)
2781   //nIncrement/=0.5*MaxOscill;
2782
2783   IntWalk_PWalking PW(Surf1,Surf2,TolTangency,Epsilon,Deflection,nIncrement);
2784   Standard_Real    SeuildPointLigne = 15.0 * Increment * Increment; //-- 10 est insuffisant
2785   Standard_Real    dminiPointLigne;
2786   Standard_Boolean HasStartPoint,RejetLigne;
2787   IntSurf_PntOn2S StartPOn2S;
2788   Standard_Integer ver;
2789   gp_Pnt Point3dDebut,Point3dFin;
2790
2791   //------------------------------------------------------------
2792   //-- Calcul des parametres approches a partir des Zones De Tangence --
2793   //--------------------------------------------------------------------
2794   Standard_Integer nbTanZon = LOn2S->NbPoints();
2795   for(Standard_Integer z=1; z <= nbTanZon; z++) {
2796     const IntSurf_PntOn2S& POn2S = LOn2S->Value(z);
2797     POn2S.Parameters(U1,V1,U2,V2);
2798     StartParams(1) = U1;
2799     StartParams(2) = V1;
2800     StartParams(3) = U2;
2801     StartParams(4) = V2;
2802
2803     //-----------------------------------------------------------------------
2804     //-- Calcul du premier point de cheminement a partir du point approche --
2805     //-----------------------------------------------------------------------
2806     HasStartPoint = PW.PerformFirstPoint(StartParams,StartPOn2S);
2807     if(HasStartPoint)
2808     {
2809       //-------------------------------------------------
2810       //-- Un point a ete trouve                       --
2811       //-- On verifie qu il n appartient pas           --
2812       //--  a une ligne de cheminement deja calculee.  --
2813       //-------------------------------------------------
2814       StartPOn2S.Parameters(pu1,pv1,pu2,pv2);
2815
2816       NbLigCalculee = SLin.Length();
2817       dminiPointLigne = SeuildPointLigne + SeuildPointLigne;
2818
2819       for(Standard_Integer l=1;
2820         (l <= NbLigCalculee) && (dminiPointLigne >= SeuildPointLigne);
2821         l++)
2822       {
2823         const Handle(IntPatch_WLine)& testwline = *((Handle(IntPatch_WLine)*)&SLin.Value(l));
2824
2825         if (IsPointOnLine(StartPOn2S, testwline, Deflection))
2826         {
2827           dminiPointLigne = 0.0;
2828         }
2829       }
2830
2831       //-- Fin d exploration des lignes
2832       if(dminiPointLigne > SeuildPointLigne)
2833       {
2834         //---------------------------------------------------
2835         //-- Le point de depart du nouveau cheminement     --
2836         //-- n est present dans aucune ligne deja calculee.--
2837         //---------------------------------------------------
2838         PW.Perform(StartParams);
2839         if(PW.IsDone())
2840         {
2841           if(PW.NbPoints()>2)
2842           {
2843             //-----------------------------------------------
2844             //-- Verification a posteriori :
2845             //-- On teste si le point de depart et de fin de
2846             //-- la ligne de cheminement est present dans une
2847             //-- autre ligne .
2848             //-----------------------------------------------
2849             RejetLigne = Standard_False;
2850             Point3dDebut = PW.Value(1).Value();
2851             const IntSurf_PntOn2S& PointFin = PW.Value(PW.NbPoints());
2852             Point3dFin   = PointFin.Value();
2853
2854             for(ver=1 ; ver<= NbLigCalculee ; ver++)
2855             {
2856               const Handle(IntPatch_WLine)& verwline = *((Handle(IntPatch_WLine)*)&SLin.Value(ver));
2857               //-- Handle(IntPatch_WLine) verwline=Handle(IntPatch_WLine)::DownCast(SLin.Value(ver));
2858
2859               // Check end point if it is on existing line.
2860               // Start point is checked before.
2861               if (IsPointOnLine(PointFin, verwline, Deflection))
2862               {
2863                 RejetLigne = Standard_True;
2864                 break;
2865               }
2866
2867               const IntSurf_PntOn2S& verPointDebut = verwline->Point(1);
2868               const IntSurf_PntOn2S& verPointFin   = verwline->Point(verwline->NbPnts());
2869               if( (Point3dDebut.Distance(verPointDebut.Value()) < TolTangency) ||
2870                   (Point3dFin.Distance(verPointFin.Value()) < TolTangency))
2871               {
2872                 RejetLigne = Standard_True;
2873                 break;
2874               }
2875             }
2876
2877             if(RejetLigne)
2878             {
2879               DublicateOfLinesProcessing(PW, ver, SLin, RejetLigne);
2880             }
2881
2882             if(!RejetLigne)
2883             {
2884               IntSurf_TypeTrans trans1,trans2;
2885               Standard_Real locu,locv;
2886               gp_Vec norm1,norm2,d1u,d1v;
2887               gp_Pnt ptbid;
2888               Standard_Integer indextg;
2889               gp_Vec tgline(PW.TangentAtLine(indextg));
2890               PW.Line()->Value(indextg).ParametersOnS1(locu,locv);
2891               Surf1->D1(locu,locv,ptbid,d1u,d1v);
2892               norm1 = d1u.Crossed(d1v);
2893               PW.Line()->Value(indextg).ParametersOnS2(locu,locv);
2894               Surf2->D1(locu,locv,ptbid,d1u,d1v);
2895               norm2 = d1u.Crossed(d1v);
2896               if (tgline.DotCross(norm2,norm1)>0.)
2897               {
2898                 trans1 = IntSurf_Out;
2899                 trans2 = IntSurf_In;
2900               }
2901               else {
2902                 trans1 = IntSurf_In;
2903                 trans2 = IntSurf_Out;
2904               }
2905
2906               Standard_Real TolTang = TolTangency;
2907               Handle(IntPatch_WLine) wline = new IntPatch_WLine(PW.Line(),Standard_False,trans1,trans2);
2908               wline->SetCreatingWayInfo(IntPatch_WLine::IntPatch_WLPrmPrm);
2909
2910               //the method PutVertexOnLine can reduce the number of points in <wline>
2911               IntPatch_RstInt::PutVertexOnLine(wline,Surf1,D1,Surf2,Standard_True,TolTang);
2912               if (wline->NbPnts() < 2)
2913                 continue;
2914               IntPatch_RstInt::PutVertexOnLine(wline,Surf2,D2,Surf1,Standard_False,TolTang);
2915               if (wline->NbPnts() < 2)
2916                 continue;
2917
2918               //---------------
2919               if(wline->NbVertex() == 0)
2920               {
2921                 IntPatch_Point vtx;
2922                 const IntSurf_PntOn2S& POn2Sf = PW.Line()->Value(1);
2923                 POn2Sf.Parameters(pu1,pv1,pu2,pv2);
2924                 vtx.SetValue(Point3dDebut,TolTang,Standard_False);
2925                 vtx.SetParameters(pu1,pv1,pu2,pv2);
2926                 vtx.SetParameter(1);
2927                 wline->AddVertex(vtx);
2928
2929                 const IntSurf_PntOn2S& POn2Sl = PW.Line()->Value(wline->NbPnts());
2930                 POn2Sl.Parameters(pu1,pv1,pu2,pv2);
2931                 vtx.SetValue(Point3dFin,TolTang,Standard_False);
2932                 vtx.SetParameters(pu1,pv1,pu2,pv2);
2933                 vtx.SetParameter(wline->NbPnts());
2934                 wline->AddVertex(vtx);
2935               }
2936
2937               //---------------
2938               AddWLine(SLin, wline, Deflection);
2939               empt = Standard_False;
2940             }
2941             else
2942             {
2943               //-- std::cout<<" ----- REJET DE LIGNE (POINT DE DEPART) ----- "<<std::endl;
2944             }
2945             //------------------------------------------------------------
2946           }
2947         }  //--  le cheminement a reussi (done a True)
2948       }  //--  le point approche ne renvoie pas sur une ligne existante
2949     } //-- Si HasStartPoint
2950   } //-- Boucle sur Les Tangent Zones
2951 }
2952 //modified by NIZNHY-PKV Wed May 25 09:39:07 2011f
2953 //=======================================================================
2954 //class : IntPatch_InfoPD
2955 //purpose  :
2956 //=======================================================================
2957 class IntPatch_InfoPD {
2958 public:
2959   //----------------------------------------C-tor
2960   IntPatch_InfoPD(const Standard_Integer aNBI) {
2961     Standard_Integer aNBI2, i, j;
2962     myNBI=aNBI;
2963     //
2964     aNBI2=aNBI*aNBI;
2965     myP1DS2=new char[aNBI2];
2966     myP2DS1=new char[aNBI2];
2967     myIP1=new Standard_Integer[aNBI2];
2968     myIP2=new Standard_Integer[aNBI2];
2969     myP1=new gp_Pnt[aNBI2];
2970     myP2=new gp_Pnt[aNBI2];
2971     //
2972     for (i=0; i<myNBI; ++i) {
2973       for (j=0; j<myNBI; ++j) {
2974         xP1DS2(i, j)=0;
2975         xP2DS1(i, j)=0;
2976         xIP1(i, j)=0;
2977         xIP2(i, j)=0;
2978         xP1(i, j).SetCoord(0., 0., 0.);
2979         xP2(i, j).SetCoord(0., 0., 0.);
2980       }
2981     }
2982   };
2983   //---------------------------------------- D-tor
2984   ~IntPatch_InfoPD() {
2985     delete [] (char*) myP1DS2;
2986     delete [] (char*) myP2DS1;
2987     delete [] (Standard_Integer*) myIP1;
2988     delete [] (Standard_Integer*) myIP2;
2989     delete [] (gp_Pnt*)myP1;
2990     delete [] (gp_Pnt*)myP2;
2991   };
2992   //---------------------------------------- Index
2993   Standard_Integer Index(const Standard_Integer i,
2994     const Standard_Integer j) const {
2995       return i*myNBI+j;
2996   };
2997   //---------------------------------------- NBI
2998   Standard_Integer NBI() const {
2999     return myNBI;
3000   };
3001   //----------------------------------------xP1DS2
3002   char& xP1DS2(const Standard_Integer i,
3003     const Standard_Integer j) {
3004       return myP1DS2[Index(i,j)];
3005   };
3006   //----------------------------------------xP2DS1
3007   char& xP2DS1(const Standard_Integer i,
3008     const Standard_Integer j) {
3009       return myP2DS1[Index(i,j)];
3010   };
3011   //----------------------------------------xIP1
3012   Standard_Integer& xIP1(const Standard_Integer i,
3013     const Standard_Integer j) {
3014       return myIP1[Index(i,j)];
3015   };
3016   //----------------------------------------xIP2
3017   Standard_Integer& xIP2(const Standard_Integer i,
3018     const Standard_Integer j) {
3019       return myIP2[Index(i,j)];
3020   };
3021   //----------------------------------------xP1
3022   gp_Pnt& xP1(const Standard_Integer i,
3023     const Standard_Integer j) {
3024       return myP1[Index(i,j)];
3025   };
3026   //----------------------------------------xP1
3027   gp_Pnt& xP2(const Standard_Integer i,
3028     const Standard_Integer j) {
3029       return myP2[Index(i,j)];
3030   };
3031
3032 private:
3033
3034   IntPatch_InfoPD (const IntPatch_InfoPD&);
3035   IntPatch_InfoPD& operator=(const IntPatch_InfoPD&);
3036
3037 private:
3038
3039   Standard_Integer myNBI;
3040   char *myP1DS2;
3041   char *myP2DS1;
3042   Standard_Integer *myIP1;
3043   Standard_Integer *myIP2;
3044   gp_Pnt *myP1;
3045   gp_Pnt *myP2;
3046 };
3047 //modified by NIZNHY-PKV Tue May 24 11:38:55 2011t
3048 //==================================================================================
3049 // function : PointDepart
3050 // purpose  :
3051 //==================================================================================
3052 void IntPatch_PrmPrmIntersection::PointDepart(Handle(IntSurf_LineOn2S)& LineOn2S,
3053                                               const Handle(Adaptor3d_Surface)& S1,
3054                                               const Standard_Integer SU_1,
3055                                               const Standard_Integer SV_1,
3056                                               const Handle(Adaptor3d_Surface)& S2,
3057                                               const Standard_Integer SU_2,
3058                                               const Standard_Integer SV_2) const
3059 {
3060   Standard_Integer i, j, xNBI;
3061   //modified by NIZNHY-PKV Tue May 24 11:37:38 2011f
3062   xNBI=200;
3063   IntPatch_InfoPD aIPD(xNBI);
3064   //modified by NIZNHY-PKV Wed May 25 06:47:12 2011t
3065   Standard_Integer iC15, SU1, SV1, SU2, SV2;
3066   Standard_Real U0, U1, V0, V1, U, V;
3067   Standard_Real resu0,resv0;
3068   Standard_Real  du1,du2,dv1,dv2, dmaxOn1, dmaxOn2;
3069   Standard_Real x0,y0,z0, x1,y1,z1,d;
3070   Bnd_Box Box1, Box2;
3071   //
3072   iC15=15;
3073   SU1 =iC15*SU_1 ;
3074   SV1 =iC15*SV_1 ;
3075   SU2 =iC15*SU_2 ;
3076   SV2 =iC15*SV_2 ;
3077   //
3078   if(xNBI<SU1) {
3079     SU1 = xNBI;
3080   }
3081   if(xNBI<SV1){
3082     SV1 = xNBI;
3083   }
3084   if(xNBI<SU2){
3085     SU2 = xNBI;
3086   }
3087   if(xNBI<SV2){
3088     SV2 = xNBI;
3089   }
3090   //
3091   U0 = S1->FirstUParameter();
3092   U1 = S1->LastUParameter();
3093   V0 = S1->FirstVParameter();
3094   V1 = S1->LastVParameter();
3095   //
3096   resu0=U0;
3097   resv0=V0;
3098   //
3099   dmaxOn1 = 0.0;
3100   dmaxOn2 = 0.0;
3101   //-----
3102   du1 = (U1-U0)/(SU1-1);
3103   dv1 = (V1-V0)/(SV1-1);
3104   for(U=U0,i=0; i<SU1; i++,U+=du1) {
3105     for(V=V0,j=0; j<SV1; V+=dv1,j++) {
3106       aIPD.xP1(i, j)= S1->Value(U,V);
3107       Box1.Add(aIPD.xP1(i, j));
3108       if(i>0 && j>0) {
3109         aIPD.xP1(i, j)    .Coord(x0,y0,z0);
3110         aIPD.xP1(i-1, j-1).Coord(x1,y1,z1);
3111         //
3112         d=Abs(x1-x0)+Abs(y1-y0)+Abs(z1-z0);
3113         if(d>dmaxOn1) {
3114           dmaxOn1 = d;
3115         }
3116       }
3117     }
3118   }
3119   Box1.Enlarge(1.e-8);
3120   //
3121   U0 = S2->FirstUParameter();
3122   U1 = S2->LastUParameter();
3123   V0 = S2->FirstVParameter();
3124   V1 = S2->LastVParameter();
3125   //
3126   du2 = (U1-U0)/(SU2-1);
3127   dv2 = (V1-V0)/(SV2-1);
3128   for(U=U0,i=0; i<SU2; i++,U+=du2) {
3129     for(V=V0,j=0; j<SV2; V+=dv2,j++) {
3130       aIPD.xP2(i, j) = S2->Value(U,V);
3131       Box2.Add(aIPD.xP2(i, j));
3132       if(i>0 && j>0) {
3133         aIPD.xP2(i, j)    .Coord(x0,y0,z0);
3134         aIPD.xP2(i-1, j-1).Coord(x1,y1,z1);
3135         d =  Abs(x1-x0)+Abs(y1-y0)+Abs(z1-z0);
3136         if(d>dmaxOn2) {
3137           dmaxOn2 = d;
3138         }
3139       }
3140     }
3141   }
3142   Box2.Enlarge(1.e-8);
3143   //--------
3144   //
3145   if(Box1.IsOut(Box2)) {
3146
3147     return;
3148   }
3149   //
3150   Standard_Integer aNbPG;
3151   Standard_Real x10,y10,z10,x11,y11,z11;
3152   Standard_Real x20,y20,z20,x21,y21,z21;
3153   Standard_Real dx, dy, dz, dmax;
3154   Standard_Real dx2, dy2, dz2;
3155   //
3156   Box1.Get(x10,y10,z10,x11,y11,z11);
3157   Box2.Get(x20,y20,z20,x21,y21,z21);
3158   //
3159   x0 = (x10>x20)? x10 : x20;
3160   y0 = (y10>y20)? y10 : y20;
3161   z0 = (z10>z20)? z10 : z20;
3162   //
3163   x1 = (x11<x21)? x11 : x21;
3164   y1 = (y11<y21)? y11 : y21;
3165   z1 = (z11<z21)? z11 : z21;
3166   //
3167   if(dmaxOn2 > dmaxOn1) {
3168     dmaxOn1 = dmaxOn2;
3169   }
3170   //
3171   dmaxOn1+=dmaxOn1;
3172   x0-=dmaxOn1;
3173   y0-=dmaxOn1;
3174   z0-=dmaxOn1;
3175   x1+=dmaxOn1;
3176   y1+=dmaxOn1;
3177   z1+=dmaxOn1;
3178   //
3179   x10-=dmaxOn1;   y10-=dmaxOn1;   z10-=dmaxOn1;
3180   x11+=dmaxOn1;   y11+=dmaxOn1;   z11+=dmaxOn1;
3181
3182   x20-=dmaxOn1;   y20-=dmaxOn1;   z20-=dmaxOn1;
3183   x21+=dmaxOn1;   y21+=dmaxOn1;   z21+=dmaxOn1;
3184
3185   aNbPG=NbPointsGrille();
3186   dx = (x1-x0)/aNbPG;
3187   dy = (y1-y0)/aNbPG;
3188   dz = (z1-z0)/aNbPG;
3189   //
3190   dmax = dx;
3191   if(dy>dmax) {
3192     dmax = dy;
3193   }
3194   if(dz>dmax){
3195     dmax = dz;
3196   }
3197   //
3198   if(dx<dmax*0.01) {
3199     dx = dmax*0.01;
3200   }
3201   if(dy<dmax*0.01) {
3202     dy = dmax*0.01;
3203   }
3204   if(dz<dmax*0.01) {
3205     dz = dmax*0.01;
3206   }
3207   //
3208   dx2 = dx*0.5;
3209   dy2 = dy*0.5;
3210   dz2 = dz*0.5 ;
3211   //
3212   IntPatch_PrmPrmIntersection_T3Bits M1(_BASE);
3213   IntPatch_PrmPrmIntersection_T3Bits M2(_BASE);
3214   //
3215   for(i=0;i<SU1;i++) {
3216     for(j=0;j<SV1;j++) {
3217       aIPD.xIP1(i, j)=-1;
3218       const gp_Pnt& P=aIPD.xP1(i, j);
3219       aIPD.xP1DS2(i, j) = (char)CodeReject(x20,y20,z20,x21,y21,z21,P.X(),P.Y(),P.Z());
3220       int ix = (int)((P.X()-x0  + dx2 )/dx);
3221       if(DansGrille(ix)) {
3222         int iy = (int)((P.Y()-y0 + dy2)/dy);
3223         if(DansGrille(iy)) {
3224           int iz = (int)((P.Z()-z0 + dz2)/dz);
3225           if(DansGrille(iz)) {
3226             aIPD.xIP1(i, j) = GrilleInteger(ix,iy,iz);
3227           }
3228         }
3229       }
3230     }
3231   }
3232   //-- std::cout<<" Grille  du 1 fini "<<std::endl;
3233   for(i=0;i<SU2;i++) {
3234     for(j=0;j<SV2;j++) {
3235       aIPD.xIP2(i, j)=-1;
3236       const gp_Pnt& P=aIPD.xP2(i, j);
3237       aIPD.xP2DS1(i, j) = (char)CodeReject(x10,y10,z10,x11,y11,z11,P.X(),P.Y(),P.Z());
3238       int ix = (int)((P.X()-x0 + dx2)/dx);
3239       if(DansGrille(ix)) {
3240         int iy = (int)((P.Y()-y0 + dy2)/dy);
3241         if(DansGrille(iy)) {
3242           int iz = (int)((P.Z()-z0 + dz2)/dz);
3243           if(DansGrille(iz)) {
3244             aIPD.xIP2(i, j) =  GrilleInteger(ix,iy,iz);
3245           }
3246         }
3247       }
3248     }
3249   }
3250   //
3251   for(i=0;i<SU1-1;i+=1) {
3252     for(j=0;j<SV1-1;j+=1) {
3253       if(!((aIPD.xP1DS2(i, j) & aIPD.xP1DS2(i+1, j)) ||
3254         (aIPD.xP1DS2(i, j) & aIPD.xP1DS2(i+1, j+1)))){
3255           Remplit(aIPD.xIP1(i, j),
3256             aIPD.xIP1(i+1, j),
3257             aIPD.xIP1(i+1, j+1),
3258             M1);
3259       }
3260       if(!((aIPD.xP1DS2(i, j) & aIPD.xP1DS2(i, j+1)) ||
3261         (aIPD.xP1DS2(i, j) & aIPD.xP1DS2(i+1, j+1)))) {
3262           Remplit(aIPD.xIP1(i, j),
3263             aIPD.xIP1(i, j+1),
3264             aIPD.xIP1(i+1, j+1),
3265             M1);
3266       }
3267     }
3268   }
3269   //
3270   for(i=0;i<SU2-1;i+=1) {
3271     for(j=0;j<SV2-1;j+=1) {
3272       if(!((aIPD.xP2DS1(i, j) & aIPD.xP2DS1(i+1, j)) ||
3273         (aIPD.xP2DS1(i, j) & aIPD.xP2DS1(i+1, j+1)))){
3274           Remplit(aIPD.xIP2(i, j),
3275             aIPD.xIP2(i+1, j),
3276             aIPD.xIP2(i+1, j+1),
3277             M2);
3278       }
3279       if(!((aIPD.xP2DS1(i, j) & aIPD.xP2DS1(i, j+1)) ||
3280         (aIPD.xP2DS1(i, j) & aIPD.xP2DS1(i+1, j+1)))){
3281           Remplit(aIPD.xIP2(i, j),
3282             aIPD.xIP2(i, j+1),
3283             aIPD.xIP2(i+1, j+1),
3284             M2);
3285       }
3286     }
3287   }
3288   //
3289   M1.ResetAnd();
3290   M2.ResetAnd();
3291   //
3292   int newind=0;
3293   long unsigned Compt=0;
3294   int ok=0;
3295   int indicepointtraite = 0;
3296   Standard_Integer k,nu,nv;
3297   //
3298   do {
3299     indicepointtraite--;
3300     ok = M1.And(M2,newind);
3301     if(ok) {
3302       IntegerGrille(newind,i,j,k);
3303       int nb=0;
3304       int LIM=3;
3305       if(   DansGrille(i-1) && DansGrille(j-1) && DansGrille(k-1)
3306         && DansGrille(i+1) && DansGrille(j+1) && DansGrille(k+1)) {
3307           int si,sj,sk;
3308           for(si=-1; si<= 1 && nb<LIM; si++) {
3309             for(sj=-1; sj<= 1 && nb<LIM; sj++) {
3310               for(sk=-1; sk<= 1 && nb<LIM; sk++) {
3311                 long unsigned lu=GrilleInteger(i+si,j+sj,k+sk);
3312                 if(M1.Val(lu) && M2.Val(lu)) {
3313                   nb++;
3314                 }
3315               }
3316             }
3317           }
3318           if(nb>=LIM) {
3319             for(si=-1; si<= 1; si++) {
3320               for(sj=-1; sj<= 1; sj++) {
3321                 for(sk=-1; sk<= 1; sk++) {
3322                   if(si || sj || sk) {
3323                     long unsigned lu=GrilleInteger(i+si,j+sj,k+sk);
3324                     M1.Raz(lu);
3325                   }
3326                 }
3327               }
3328             }
3329           }
3330       }
3331       //
3332       gp_Pnt P(dx*i + x0, dy*j + y0, dz*k+z0);
3333       //
3334       Standard_Integer nu1=-1,nu2=-1;
3335       Standard_Integer nv1=0, nv2=0;
3336       int nbsur1 = 0;
3337       for(nu=0;nu1<0 && nu<SU1;nu++) {
3338         for(nv=0;nu1<0 && nv<SV1;nv++) {
3339           if( aIPD.xIP1(nu, nv) ==(Standard_Integer) newind )  {
3340             nbsur1++;
3341             aIPD.xIP1(nu, nv)=indicepointtraite;
3342             nu1=nu; nv1=nv;
3343           }
3344         }
3345       }
3346       if(nu1>=0) {
3347         int nbsur2 = 0;
3348         for(nu=0;nu2<0 && nu<SU2;nu++) {
3349           for(nv=0;nu2<0 && nv<SV2;nv++) {
3350             if( aIPD.xIP2(nu, nv)==(Standard_Integer) newind )  {
3351               nbsur2++;
3352               aIPD.xIP2(nu, nv)=indicepointtraite;
3353               nu2=nu; nv2=nv;
3354             }
3355           }
3356         }
3357       }
3358       if(nu1>=0 && nu2>=0) {
3359         IntSurf_PntOn2S POn2S;
3360         POn2S.SetValue(P,
3361           S1->FirstUParameter()+nu1*du1,
3362           S1->FirstVParameter()+nv1*dv1,
3363           S2->FirstUParameter()+nu2*du2,
3364           S2->FirstVParameter()+nv2*dv2);
3365         LineOn2S->Add(POn2S);
3366         Compt++;
3367       }
3368       else {
3369         //-- aucun point du triangle n a ete trouve assez proche
3370         //-- on recherche les 3 points les plus proches de P
3371         //-- dans chacun des tableaux
3372         Standard_Real Dist3[3],u3[3] = { 0.0, 0.0, 0.0 },v3[3] = { 0.0, 0.0, 0.0 };
3373         Dist3[0]=Dist3[1]=Dist3[2]=RealLast();
3374         for(U=resu0,i=0; i<SU1; i++,U+=du1) {
3375           for(V=resv0,j=0; j<SV1; V+=dv1,j++) {
3376             //-- On place les 3 meilleures valeurs dans Dist1,Dist2,Dist3
3377             Standard_Real t = aIPD.xP1(i, j).SquareDistance(P);
3378             //-- On remplace la plus grande valeur ds Dist[.] par la val courante
3379             if(Dist3[0]<Dist3[1]) {
3380               Standard_Real z;
3381               z=Dist3[0]; Dist3[0]=Dist3[1]; Dist3[1]=z;
3382               z=u3[0]; u3[0]=u3[1]; u3[1]=z;
3383               z=v3[0]; v3[0]=v3[1]; v3[1]=z;
3384             }
3385             if(Dist3[1]<Dist3[2]) {
3386               Standard_Real z;
3387               z=Dist3[1]; Dist3[1]=Dist3[2]; Dist3[2]=z;
3388               z=u3[1]; u3[1]=u3[2]; u3[2]=z;
3389               z=v3[1]; v3[1]=v3[2]; v3[2]=z;
3390             }
3391             if(Dist3[0]<Dist3[1]) {
3392               Standard_Real z;
3393               z=Dist3[0]; Dist3[0]=Dist3[1]; Dist3[1]=z;
3394               z=u3[0]; u3[0]=u3[1]; u3[1]=z;
3395               z=v3[0]; v3[0]=v3[1]; v3[1]=z;
3396             }
3397             //-- la plus grande valeur est dans Dist3[0]
3398             if(t<Dist3[0]) {
3399               Dist3[0]=t; u3[0]=U; v3[0]=V;
3400             }
3401           }
3402         }
3403         //
3404         Standard_Real U1_3 = (u3[0]+u3[1]+u3[2])/3.0;
3405         Standard_Real V1_3 = (v3[0]+v3[1]+v3[2])/3.0;
3406
3407         Dist3[0]=Dist3[1]=Dist3[2]=RealLast();
3408         for(U=U0,i=0; i<SU2; i++,U+=du2) {
3409           for(V=V0,j=0; j<SV2; V+=dv2,j++) {
3410             //-- On place les 3 meilleures valeurs dans Dist1,Dist2,Dist3
3411             Standard_Real t = aIPD.xP2(i, j).SquareDistance(P);
3412             //-- On remplace la plus grande valeur ds Dist3[.] par la val courante
3413             if(Dist3[0]<Dist3[1]) {
3414               Standard_Real z;
3415               z=Dist3[0]; Dist3[0]=Dist3[1]; Dist3[1]=z;
3416               z=u3[0]; u3[0]=u3[1]; u3[1]=z;
3417               z=v3[0]; v3[0]=v3[1]; v3[1]=z;
3418             }
3419             if(Dist3[1]<Dist3[2]) {
3420               Standard_Real z;
3421               z=Dist3[1]; Dist3[1]=Dist3[2]; Dist3[2]=z;
3422               z=u3[1]; u3[1]=u3[2]; u3[2]=z;
3423               z=v3[1]; v3[1]=v3[2]; v3[2]=z;
3424             }
3425             if(Dist3[0]<Dist3[1]) {
3426               Standard_Real z;
3427               z=Dist3[0]; Dist3[0]=Dist3[1]; Dist3[1]=z;
3428               z=u3[0]; u3[0]=u3[1]; u3[1]=z;
3429               z=v3[0]; v3[0]=v3[1]; v3[1]=z;
3430             }
3431             //-- la plus grande valeur est dans Dist3[0]
3432             if(t<Dist3[0]) {
3433               Dist3[0]=t; u3[0]=U; v3[0]=V;
3434             }
3435           }
3436         }
3437         //
3438         Standard_Real U2_3 = (u3[0]+u3[1]+u3[2])/3.0;
3439         Standard_Real V2_3 = (v3[0]+v3[1]+v3[2])/3.0;
3440         //
3441         IntSurf_PntOn2S POn2S;
3442         POn2S.SetValue(P,U1_3,V1_3,U2_3,V2_3);
3443         LineOn2S->Add(POn2S);
3444         Compt++;
3445       }
3446     }
3447   }
3448   while(ok);
3449 }
3450
3451 //==================================================================================
3452 // function : IsPointOnLine
3453 // purpose  :
3454 //==================================================================================
3455
3456 Standard_Boolean IsPointOnLine(const IntSurf_PntOn2S        &thePOn2S,
3457                                const Handle(IntPatch_WLine) &theWLine,
3458                                const Standard_Real           Deflection)
3459 {
3460   Standard_Boolean isOnLine = Standard_False;
3461   Standard_Real Deflection2 = Deflection*Deflection;
3462   Standard_Real pu1, pu2, pv1, pv2;
3463
3464   thePOn2S.Parameters(pu1, pv1, pu2, pv2);
3465
3466   if ((theWLine->IsOutSurf1Box(gp_Pnt2d(pu1, pv1)) == Standard_False) &&
3467     (theWLine->IsOutSurf2Box(gp_Pnt2d(pu2, pv2)) == Standard_False) &&
3468     (theWLine->IsOutBox(thePOn2S.Value())        == Standard_False)) {
3469       const Standard_Integer NbPntOn2SOnLine = theWLine->NbPnts();
3470       Standard_Integer ll;
3471
3472       for (ll=1; ll < NbPntOn2SOnLine && !isOnLine; ll++) {
3473         const gp_Pnt &Pa     = theWLine->Point(ll).Value();
3474         const gp_Pnt &Pb     = theWLine->Point(ll+1).Value();
3475         const gp_Pnt &PStart = thePOn2S.Value();
3476         const gp_Vec  AM(Pa, PStart);
3477         const gp_Vec  MB(PStart,Pb);
3478         const Standard_Real AMMB = AM.Dot(MB);
3479
3480         if(AMMB > 0.0) {
3481           gp_Dir ABN(Pb.X() - Pa.X(), Pb.Y() - Pa.Y(), Pb.Z() - Pa.Z());
3482           Standard_Real lan =  ABN.X()*AM.X() + ABN.Y()*AM.Y() + ABN.Z()*AM.Z();
3483           gp_Vec AH(lan*ABN.X(), lan*ABN.Y(), lan*ABN.Z());
3484           gp_Vec HM(AM.X() - AH.X(), AM.Y() - AH.Y(), AM.Z() - AH.Z());
3485           Standard_Real d = 0.0;
3486
3487           if(HM.X() < Deflection) {
3488             d += HM.X()*HM.X();
3489
3490             if(HM.Y() < Deflection) {
3491               d += HM.Y()*HM.Y();
3492
3493               if(HM.Z() < Deflection) {
3494                 d += HM.Z()*HM.Z();
3495               } else {
3496                 d = Deflection2;
3497               }
3498             } else {
3499               d = Deflection2;
3500             }
3501           } else {
3502             d = Deflection2;
3503           }
3504
3505           if(d < Deflection2) {
3506             isOnLine = Standard_True;
3507           }
3508         } else {
3509           Standard_Real dab = Pa.SquareDistance(Pb);
3510           Standard_Real dap = Pa.SquareDistance(PStart);
3511
3512           if(dap < dab) {
3513             isOnLine = Standard_True;
3514           } else {
3515             Standard_Real dbp = Pb.SquareDistance(PStart);
3516
3517             if(dbp < dab) {
3518               isOnLine = Standard_True;
3519             }
3520           }
3521         }
3522       }
3523   }
3524
3525   return isOnLine;
3526 }
3527
3528 //==================================================================================
3529 // function : AddWLine
3530 // purpose  :
3531 //==================================================================================
3532
3533 void AddWLine(IntPatch_SequenceOfLine      &theLines,
3534               const Handle(IntPatch_WLine) &theWLine,
3535               const Standard_Real           Deflection)
3536 {
3537   Standard_Integer i = 1;
3538   Standard_Integer aNbLines = theLines.Length();
3539   Standard_Boolean isToRemove;
3540
3541   // Check each line of theLines if it is on theWLine.
3542   while (i <= aNbLines) {
3543     Handle(IntPatch_WLine) aWLine =
3544       Handle(IntPatch_WLine)::DownCast(theLines.Value(i));
3545
3546     isToRemove = Standard_False;
3547
3548     if (aWLine.IsNull() == Standard_False) {
3549       // Check the middle point.
3550       Standard_Integer aMidIndex = (aWLine->NbPnts() + 1)/2;
3551
3552       if (aMidIndex > 0) {
3553         const IntSurf_PntOn2S &aPnt = aWLine->Point(aMidIndex);
3554
3555         if (IsPointOnLine(aPnt, theWLine, Deflection)) {
3556           // Middle point is on theWLine. Check vertices.
3557           isToRemove = Standard_True;
3558
3559           Standard_Integer j;
3560           const Standard_Integer aNbVtx = aWLine->NbVertex();
3561
3562           for (j = 1; j <= aNbVtx; j++) {
3563             const IntPatch_Point &aPoint = aWLine->Vertex(j);
3564
3565             if (!IsPointOnLine(aPoint.PntOn2S(), theWLine, Deflection)) {
3566               isToRemove = Standard_False;
3567               break;
3568             }
3569           }
3570         }
3571       }
3572     }
3573
3574     if (isToRemove) {
3575       theLines.Remove(i);
3576       aNbLines--;
3577     } else {
3578       i++;
3579     }
3580   }
3581
3582   // Add theWLine to the sequence of lines.
3583   theLines.Append(theWLine);
3584 }