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