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