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