0032539: Modeling Algorithms - Parallelize BRepExtrema_DistShapeShape algorithm
[occt.git] / src / BRepExtrema / BRepExtrema_DistanceSS.cxx
1 // Created on: 1996-04-22
2 // Created by: Herve LOUESSARD 
3 // Copyright (c) 1996-1999 Matra Datavision
4 // Copyright (c) 1999-2014 OPEN CASCADE SAS
5 //
6 // This file is part of Open CASCADE Technology software library.
7 //
8 // This library is free software; you can redistribute it and/or modify it under
9 // the terms of the GNU Lesser General Public License version 2.1 as published
10 // by the Free Software Foundation, with special exception defined in the file
11 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
12 // distribution for complete text of the license and disclaimer of any warranty.
13 //
14 // Alternatively, this file may be used under the terms of Open CASCADE
15 // commercial license or contractual agreement.
16
17 // Modified: Sergey ZERCHANINOV
18
19 #include <BRepExtrema_DistanceSS.hxx>
20
21 #include <TopTools_IndexedMapOfShape.hxx>
22 #include <TopExp.hxx>
23 #include <gp_Pnt.hxx>
24 #include <gp_Pnt2d.hxx>
25 #include <BRep_Tool.hxx>
26 #include <BRepExtrema_SupportType.hxx>
27 #include <Standard_Real.hxx>
28 #include <BRepExtrema_SolutionElem.hxx>
29 #include <BRepExtrema_SeqOfSolution.hxx>
30 #include <Standard_Boolean.hxx>
31 #include <Standard_Integer.hxx> 
32 #include <TopAbs_ShapeEnum.hxx>
33 #include <TopoDS.hxx>
34 #include <Bnd_Box.hxx>
35 #include <BRepExtrema_ExtPC.hxx>
36 #include <BRepExtrema_ExtPF.hxx>
37 #include <Extrema_ExtFlag.hxx>
38 #include <BRepExtrema_ExtCC.hxx>
39 #include <BRepExtrema_ExtCF.hxx>
40 #include <BRepExtrema_ExtFF.hxx>
41 #include <BRepClass_FaceClassifier.hxx>
42 #include <TopAbs.hxx>
43 #include <Geom_Curve.hxx>
44 #include <GeomAbs_Shape.hxx>
45 #include <GeomAdaptor_Curve.hxx>
46 #include <TColStd_Array1OfReal.hxx>
47 #include <BRepBuilderAPI_MakeVertex.hxx>
48 #include <BRepBuilderAPI_MakeEdge.hxx>
49 #include <BRepBuilderAPI_MakeFace.hxx>
50 #include <Geom_Surface.hxx>
51 #include <GeomAPI_ProjectPointOnSurf.hxx>
52 #include <GeomAPI_ProjectPointOnCurve.hxx>
53 #include <Geom_RectangularTrimmedSurface.hxx>
54 #include <Geom_TrimmedCurve.hxx>
55 #include <BRepBndLib.hxx>
56 #include <BRepTools.hxx>
57 #include <TColgp_Array1OfPnt.hxx>
58
59
60 /*********************************************************************************/
61
62 //------------------------------------------------------------------------------
63 // function: TRI_SOLUTION
64 //------------------------------------------------------------------------------
65 static Standard_Boolean TRI_SOLUTION (const BRepExtrema_SeqOfSolution& SeqSol, const gp_Pnt& Pt)
66 {
67   for (BRepExtrema_SeqOfSolution::iterator anIt = SeqSol.begin(); anIt != SeqSol.end(); anIt++)
68   {
69     const Standard_Real dst = anIt->Point().Distance(Pt);
70     if (dst <= Precision::Confusion())
71     {
72       return Standard_False;
73     }
74   }
75   return Standard_True;
76 }  
77
78 //------------------------------------------------------------------------------
79 // function: MIN_SOLUTION
80 //------------------------------------------------------------------------------
81 static void MIN_SOLUTION (const BRepExtrema_SeqOfSolution& SeqSol1,
82                           const BRepExtrema_SeqOfSolution& SeqSol2,
83                           const Standard_Real DstRef,
84                           const Standard_Real Eps,
85                           BRepExtrema_SeqOfSolution& seqSol1,
86                           BRepExtrema_SeqOfSolution& seqSol2)
87 {
88   for (BRepExtrema_SeqOfSolution::iterator anIt1 = SeqSol1.begin(), anIt2 = SeqSol2.begin(); 
89        anIt1 != SeqSol1.end(); 
90        anIt1++, anIt2++)
91   {
92     const Standard_Real dst1 = anIt1->Dist();
93     if (fabs(dst1 - DstRef) < Eps)
94           {       
95       seqSol1.Append(*anIt1);
96       seqSol2.Append(*anIt2);
97           }
98   }
99 }
100
101 //------------------------------------------------------------------------------
102 // function: TRIM_INFINIT_EDGE
103 //------------------------------------------------------------------------------
104 static void TRIM_INFINIT_EDGE(const TopoDS_Edge& S1, const TopoDS_Edge& S2, TopoDS_Edge& aResEdge,
105                               Standard_Boolean& bIsTrim1, Standard_Boolean& bIsTrim2)
106 {
107   if ( BRep_Tool::Degenerated(S1) || BRep_Tool::Degenerated(S2) )
108     return;
109
110   aResEdge = S2;
111   Standard_Real aFirst1, aLast1, aFirst2, aLast2;
112   Handle(Geom_Curve) pCurv1 = BRep_Tool::Curve(S1, aFirst1, aLast1);
113   Handle(Geom_Curve) pCurv2 = BRep_Tool::Curve(S2, aFirst2, aLast2);
114
115   if (Precision::IsInfinite(aFirst1) &&
116       Precision::IsInfinite(aLast1)  &&
117       Precision::IsInfinite(aFirst2) &&
118       Precision::IsInfinite(aLast2))
119     return;
120   
121   Standard_Real Umin = 0., Umax = 0.;
122   Standard_Boolean bUmin, bUmax;
123   bUmin = bUmax = Standard_False;
124
125   Handle(Geom_Curve) pCurv;
126   if ( !pCurv1.IsNull() && (Precision::IsInfinite(aFirst1) || Precision::IsInfinite(aLast1)) )
127   {
128     pCurv = pCurv1;
129     bIsTrim1 = Standard_True;
130     if (!Precision::IsInfinite(aFirst1))
131     {
132       bUmin = Standard_True;
133       Umin = aFirst1;
134     }
135     else if (!Precision::IsInfinite(aLast1))
136     {
137       bUmax = Standard_True;
138       Umax = aLast1;
139     }
140   }
141   else if ( !pCurv2.IsNull() && (Precision::IsInfinite(aFirst2) || Precision::IsInfinite(aLast2)) )
142   {
143     pCurv = pCurv2;
144     bIsTrim2 = Standard_True;
145     if (!Precision::IsInfinite(aFirst2))
146     {
147       bUmin = Standard_True;
148       Umin = aFirst2;
149     }
150     else if (!Precision::IsInfinite(aLast2))
151     {
152       bUmax = Standard_True;
153       Umax = aLast2;
154     }
155   }
156   if (bIsTrim1 || bIsTrim2)
157   {
158     Bnd_Box aEdgeBox;
159     if (bIsTrim1)
160       BRepBndLib::Add(S2, aEdgeBox);
161     if (bIsTrim2)
162       BRepBndLib::Add(S1, aEdgeBox);
163     Standard_Real Xmin, Ymin, Zmin, Xmax, Ymax, Zmax;
164     aEdgeBox.Get(Xmin, Ymin, Zmin, Xmax, Ymax, Zmax);
165
166     const gp_Pnt aPnt0(Xmin, Ymin, Zmin);
167     const gp_Pnt aPnt1(Xmin, Ymax, Zmin);
168     const gp_Pnt aPnt2(Xmin, Ymax, Zmax);
169     const gp_Pnt aPnt3(Xmin, Ymin, Zmax);
170     const gp_Pnt aPnt4(Xmax, Ymax, Zmin);
171     const gp_Pnt aPnt5(Xmax, Ymax, Zmax);
172     const gp_Pnt aPnt6(Xmax, Ymin, Zmax);
173     const gp_Pnt aPnt7(Xmax, Ymin, Zmin);
174
175         Standard_Real arrU[8];
176     GeomAPI_ProjectPointOnCurve aProj(aPnt0, pCurv);
177     /*szv:aProj.Perform(aPnt0);*/ arrU[0] = aProj.LowerDistanceParameter();
178     aProj.Perform(aPnt1); arrU[1] = aProj.LowerDistanceParameter();
179     aProj.Perform(aPnt2); arrU[2] = aProj.LowerDistanceParameter();
180     aProj.Perform(aPnt3); arrU[3] = aProj.LowerDistanceParameter();
181     aProj.Perform(aPnt4); arrU[4] = aProj.LowerDistanceParameter();
182     aProj.Perform(aPnt5); arrU[5] = aProj.LowerDistanceParameter();
183     aProj.Perform(aPnt6); arrU[6] = aProj.LowerDistanceParameter();
184     aProj.Perform(aPnt7); arrU[7] = aProj.LowerDistanceParameter();
185     
186     if (!bUmin)
187       Umin = arrU[0];
188         
189     if (!bUmax)
190       Umax = arrU[0];
191
192     Standard_Integer i = 0;
193     while (i < 8)
194         {
195       const Standard_Real aU = arrU[i++];
196           if (aU < Umin)
197             Umin = aU;
198           else if (aU > Umax)
199             Umax = aU;
200         }
201
202     Standard_Real tol = Precision::Confusion();
203     if (bIsTrim1)
204       tol = BRep_Tool::Tolerance(S1);
205     else if (bIsTrim2)
206       tol = BRep_Tool::Tolerance(S2);
207
208     const Standard_Real EpsU = GeomAdaptor_Curve(pCurv).Resolution(3.*tol);
209     if (fabs(Umin - Umax) < EpsU)
210     {
211       Umin -= EpsU;
212       Umax += EpsU;
213     }
214
215     Handle(Geom_Curve) result = new Geom_TrimmedCurve(pCurv, Umin, Umax);
216     aResEdge = BRepBuilderAPI_MakeEdge(result);
217   }
218 }
219
220 //------------------------------------------------------------------------------
221 // function: TRIM_INFINIT_FACE
222 //------------------------------------------------------------------------------
223 static void TRIM_INFINIT_FACE(const TopoDS_Shape& S1, const TopoDS_Shape& S2,
224                               TopoDS_Face& aResFace, Standard_Boolean& bIsInfinit)
225 {
226   bIsInfinit = Standard_False;
227
228   TopAbs_ShapeEnum Type1 = S1.ShapeType();     
229   TopAbs_ShapeEnum Type2 = S2.ShapeType();
230
231   TopoDS_Edge aE;
232   TopoDS_Face aF;
233   
234   if (Type1 == TopAbs_EDGE && Type2 == TopAbs_FACE)
235   {
236     aE = TopoDS::Edge(S1);
237     if ( BRep_Tool::Degenerated(aE) )
238       return;
239     aF = TopoDS::Face(S2);
240   }
241   else if (Type2 == TopAbs_EDGE && Type1 == TopAbs_FACE)
242   {
243     aE = TopoDS::Edge(S2);
244     if ( BRep_Tool::Degenerated(aE) )
245       return;
246     aF = TopoDS::Face(S1);
247   }
248   else
249   {
250     bIsInfinit = Standard_False;
251     return;
252   }
253
254   aResFace = aF;
255   Handle(Geom_Surface) pSurf = BRep_Tool::Surface(aF);
256  
257   const Standard_Boolean bRestrict = BRep_Tool::NaturalRestriction(aF);
258
259   Standard_Real U1, V1, U2, V2;
260   Standard_Real Umin = RealLast(), Umax = RealFirst(), Vmin = RealLast(), Vmax = RealFirst();
261   Standard_Boolean bUmin, bUmax, bVmin, bVmax;
262   bUmin = bUmax = bVmin = bVmax = Standard_False;
263   Standard_Boolean bIsTrim = Standard_False;
264
265   if (bRestrict)
266   {
267     pSurf->Bounds(U1, U2, V1, V2);
268     if (Precision::IsInfinite(U1))
269       bIsTrim = Standard_True;
270     else
271     {
272       Umin = U1;
273       bUmin = Standard_True;
274     }
275
276     if (Precision::IsInfinite(U2))
277       bIsTrim = Standard_True;
278     else
279     {
280       Umax = U2;
281       bUmax = Standard_True;
282     }
283
284     if (Precision::IsInfinite(V1))
285       bIsTrim = Standard_True;
286     else
287         {
288       Vmin = V1;
289       bVmin = Standard_True;
290         }
291       
292     if (Precision::IsInfinite(V2))
293       bIsTrim = Standard_True;
294     else
295         {
296       Vmax = V2;
297       bVmax = Standard_True;
298     }
299   }
300   else
301   {
302     BRepTools::UVBounds(aF, U1, U2, V1, V2);
303     if (Precision::IsInfinite(U1) &&
304         Precision::IsInfinite(U2) &&
305         Precision::IsInfinite(V1) &&
306         Precision::IsInfinite(V2))
307       bIsTrim = Standard_True;
308   }
309
310   if (bIsTrim)
311   {      
312     Bnd_Box aEdgeBox;
313     BRepBndLib::Add(aE, aEdgeBox);
314
315     if(aEdgeBox.IsWhole())
316       return;
317
318     Standard_Real Xmin, Ymin, Zmin, Xmax, Ymax, Zmax;
319     aEdgeBox.Get(Xmin, Ymin, Zmin, Xmax, Ymax, Zmax);
320
321     const gp_Pnt aPnt0(Xmin, Ymin, Zmin);
322     const gp_Pnt aPnt1(Xmin, Ymax, Zmin);
323     const gp_Pnt aPnt2(Xmin, Ymax, Zmax);
324     const gp_Pnt aPnt3(Xmin, Ymin, Zmax);
325     const gp_Pnt aPnt4(Xmax, Ymax, Zmin);
326     const gp_Pnt aPnt5(Xmax, Ymax, Zmax);
327     const gp_Pnt aPnt6(Xmax, Ymin, Zmax);
328     const gp_Pnt aPnt7(Xmax, Ymin, Zmin);
329
330     Standard_Real arrU[8], arrV[8];
331     GeomAPI_ProjectPointOnSurf aProj(aPnt0, pSurf);
332     /*szv:aProj.Perform(aPnt0);*/ if (aProj.IsDone()) aProj.LowerDistanceParameters(arrU[0],arrV[0]);
333     aProj.Perform(aPnt1); if (aProj.IsDone()) aProj.LowerDistanceParameters(arrU[1],arrV[1]);
334     aProj.Perform(aPnt2); if (aProj.IsDone()) aProj.LowerDistanceParameters(arrU[2],arrV[2]);
335     aProj.Perform(aPnt3); if (aProj.IsDone()) aProj.LowerDistanceParameters(arrU[3],arrV[3]);
336     aProj.Perform(aPnt4); if (aProj.IsDone()) aProj.LowerDistanceParameters(arrU[4],arrV[4]);
337     aProj.Perform(aPnt5); if (aProj.IsDone()) aProj.LowerDistanceParameters(arrU[5],arrV[5]);
338     aProj.Perform(aPnt6); if (aProj.IsDone()) aProj.LowerDistanceParameters(arrU[6],arrV[6]);
339     aProj.Perform(aPnt7); if (aProj.IsDone()) aProj.LowerDistanceParameters(arrU[7],arrV[7]);
340
341     if (!bUmin)
342       Umin = arrU[0];
343     if (!bUmax)
344       Umax = arrU[0];
345     if (!bVmin)
346       Vmin = arrV[0];
347     if (!bVmax)
348       Vmax = arrV[0];
349
350     Standard_Integer i = 0;
351     while (i < 8)
352         {
353       const Standard_Real aU = arrU[i];
354           if (aU < Umin)
355             Umin = aU;
356           else if (aU > Umax)
357             Umax = aU;
358
359       const Standard_Real aV = arrV[i];
360           if (aV < Vmin)
361             Vmin = aV;
362           else if (aV > Vmax)
363             Vmax = aV;
364
365       i++;
366         }
367       
368     GeomAdaptor_Surface aGAS(pSurf);
369     const Standard_Real tol = BRep_Tool::Tolerance(aF);
370
371     const Standard_Real EpsU = aGAS.UResolution(3.*tol);
372     if (fabs(Umin - Umax) < EpsU)
373     {
374       Umin -= EpsU;
375       Umax += EpsU;
376     }
377
378     const Standard_Real EpsV = aGAS.VResolution(3.*tol);
379     if (fabs(Vmin - Vmax) < EpsV)
380     {
381       Vmin -= EpsV;
382       Vmax += EpsV;
383     }
384
385     Handle(Geom_Surface) result = new Geom_RectangularTrimmedSurface(pSurf, Umin, Umax, Vmin, Vmax);
386     aResFace = BRepBuilderAPI_MakeFace(result, Precision::Confusion());
387
388     bIsInfinit = Standard_True;
389   }
390   else
391     bIsInfinit = Standard_False;
392 }
393
394 //------------------------------------------------------------------------------
395 // static function: PERFORM_C0
396 //------------------------------------------------------------------------------
397 static void PERFORM_C0(const TopoDS_Edge &S1, const TopoDS_Edge &S2,
398                        BRepExtrema_SeqOfSolution& SeqSol1,
399                        BRepExtrema_SeqOfSolution& SeqSol2,
400                        const Standard_Real DstRef,
401                        Standard_Real& mDstRef,
402                        const Standard_Real Eps)
403 {
404   if ( BRep_Tool::Degenerated(S1) || BRep_Tool::Degenerated(S2) )
405     return;
406
407   Standard_Integer iE;
408   for (iE = 0; iE < 2; iE++)
409   {
410     TopoDS_Edge E, Eother;
411     if (iE == 0)
412         {
413           E      = S1;
414           Eother = S2;
415         }
416     else
417         {
418           E      = S2;
419           Eother = S1;
420         }
421
422     Standard_Real aFirst, aLast;
423     Handle(Geom_Curve) pCurv = BRep_Tool::Curve(E, aFirst, aLast);
424
425     Standard_Real aFOther, aLOther;
426     Handle(Geom_Curve) pCurvOther = BRep_Tool::Curve(Eother, aFOther, aLOther);
427
428     if (pCurv->Continuity() == GeomAbs_C0)
429         {
430       const Standard_Real epsP = Precision::PConfusion();
431
432       GeomAdaptor_Curve aAdaptorCurve(pCurv, aFirst, aLast);
433       const Standard_Integer nbIntervals = aAdaptorCurve.NbIntervals(GeomAbs_C1);
434
435       TColStd_Array1OfReal arrInter(1,1+nbIntervals);
436       aAdaptorCurve.Intervals(arrInter, GeomAbs_C1);
437
438       GeomAdaptor_Curve aAdaptorCurveOther(pCurvOther, aFOther, aLOther);
439       const Standard_Integer nbIntervalsOther = aAdaptorCurveOther.NbIntervals(GeomAbs_C1);
440       TColStd_Array1OfReal arrInterOther(1,1+nbIntervalsOther);
441       aAdaptorCurveOther.Intervals(arrInterOther, GeomAbs_C1);
442
443       Standard_Real Udeb,Ufin;
444       BRep_Tool::Range(Eother,Udeb,Ufin);
445
446       gp_Pnt P1,Pt;
447       Standard_Integer i, ii;  
448       BRepClass_FaceClassifier classifier;
449       for (i = 1; i <= arrInter.Length(); i++)
450       {
451         const Standard_Real aParameter = arrInter(i);
452         const gp_Pnt aPnt = aAdaptorCurve.Value(aParameter);
453         const TopoDS_Vertex V1 = BRepBuilderAPI_MakeVertex(aPnt);
454
455         BRepExtrema_ExtPC Ext(V1,Eother);
456         const Standard_Integer NbExtrema = Ext.IsDone()? Ext.NbExt() : 0;
457         if ( NbExtrema > 0 )
458                 { 
459           // Search minimum distance dstmin
460           Standard_Real Dstmin = Ext.SquareDistance(1);
461           for (ii = 2; ii <= NbExtrema; ii++)
462           {
463             const Standard_Real sDst = Ext.SquareDistance(ii);
464             if (sDst<Dstmin)
465               Dstmin=sDst;
466           }
467           Dstmin = sqrt(Dstmin);
468
469           if ((Dstmin < DstRef - Eps) || (fabs(Dstmin-DstRef) < Eps))
470             for (ii = 1; ii <= NbExtrema; ii++)
471             {
472               if (fabs(Dstmin-sqrt(Ext.SquareDistance(ii)))<Eps)
473               {
474                 Pt=Ext.Point(ii);
475                 if (TRI_SOLUTION(SeqSol2,Pt))
476                 {
477                   // Check if the parameter does not correspond to a vertex
478                   const Standard_Real t = Ext.Parameter(ii);
479                   if ((fabs(t-Udeb)>=epsP)&&(fabs(t-Ufin)>epsP))
480                   {
481                     if (mDstRef > Dstmin)
482                       mDstRef=Dstmin;
483                     const BRepExtrema_SolutionElem Sol1(Dstmin,aPnt,BRepExtrema_IsOnEdge,E,aParameter);
484                     const BRepExtrema_SolutionElem Sol2(Dstmin,Pt,BRepExtrema_IsOnEdge,Eother,t);
485                     SeqSol1.Append(iE == 0 ? Sol1 : Sol2);
486                     SeqSol2.Append(iE == 0 ? Sol2 : Sol1);
487                   }
488                 }
489               }
490             }
491         }
492         for (Standard_Integer i2 = 1; i2<=arrInterOther.Length(); i2++)
493         {
494           const Standard_Real aParameterOther = arrInterOther(i2);
495           const gp_Pnt aPntOther = aAdaptorCurveOther.Value(aParameterOther);
496           const Standard_Real Dst = aPnt.Distance(aPntOther);
497           if ((Dst < DstRef - Eps) || (fabs(Dst-DstRef) < Eps))
498           {             
499             if (mDstRef > Dst)
500               mDstRef=Dst;
501             const BRepExtrema_SolutionElem Sol1(Dst,aPnt,BRepExtrema_IsOnEdge,E,aParameter);
502             const BRepExtrema_SolutionElem Sol2(Dst,aPntOther,BRepExtrema_IsOnEdge,Eother,aParameterOther);
503             SeqSol1.Append(iE == 0 ? Sol1 : Sol2);
504             SeqSol2.Append(iE == 0 ? Sol2 : Sol1);
505           }               
506         }
507       }
508     }
509   }
510 }
511
512 /*********************************************************************************/
513
514 void BRepExtrema_DistanceSS::Perform(const TopoDS_Shape& S1, const TopoDS_Shape& S2,
515                                      const Bnd_Box& B1, const Bnd_Box& B2)
516 {
517   SeqSolShape1.Clear();
518   SeqSolShape2.Clear();
519   myModif=Standard_False;
520
521   switch (S1.ShapeType())
522   {
523     case TopAbs_VERTEX :
524     {
525       TopoDS_Vertex V1 = TopoDS::Vertex(S1);
526       switch (S2.ShapeType())
527       {
528         case TopAbs_VERTEX :
529         {
530           TopoDS_Vertex V2 = TopoDS::Vertex(S2);
531           Perform( V1, V2 );
532           break;
533         }
534         case TopAbs_EDGE :
535         {
536           TopoDS_Edge E2 = TopoDS::Edge(S2);
537           Perform( V1, E2, B1, B2 );
538           break;
539         }
540         case TopAbs_FACE :
541         {
542           TopoDS_Face F2 = TopoDS::Face(S2);
543           Perform( V1, F2, B1, B2 );
544           break;
545         }
546         default:
547           break;
548       }
549       break;
550     }
551
552     case TopAbs_EDGE :
553     {
554       TopoDS_Edge E1 = TopoDS::Edge(S1);
555       switch (S2.ShapeType())
556       {
557         case TopAbs_VERTEX :
558         {
559           TopoDS_Vertex V2 = TopoDS::Vertex(S2);
560           Perform( E1, V2, B1, B2 );
561           break;
562         }
563         case TopAbs_EDGE :
564         {
565           TopoDS_Edge E2 = TopoDS::Edge(S2);
566           TopoDS_Edge aTrimEdge;
567           Standard_Boolean bIsTrim1 = Standard_False;
568           Standard_Boolean bIsTrim2 = Standard_False;
569           TRIM_INFINIT_EDGE( E1, E2, aTrimEdge, bIsTrim1, bIsTrim2 );
570           if (bIsTrim1)
571             E1 = aTrimEdge;
572           if (bIsTrim2)
573             E2 = aTrimEdge;
574           Perform( E1, E2, B1, B2 );
575           break;
576         }
577         case TopAbs_FACE :
578         {
579           TopoDS_Face F2 = TopoDS::Face(S2);
580           TopoDS_Face aTrimFace;
581           Standard_Boolean bIsInfinit;
582           TRIM_INFINIT_FACE( E1, F2, aTrimFace, bIsInfinit );
583           if (bIsInfinit)
584             F2 = aTrimFace;
585           Perform( E1, F2, B1, B2 );
586           break;
587         }
588         default:
589           break;
590       }
591       break;
592     }
593
594     case TopAbs_FACE :
595     {
596       TopoDS_Face F1 = TopoDS::Face(S1);
597       switch (S2.ShapeType())
598       {
599         case TopAbs_VERTEX :
600         {
601           TopoDS_Vertex V2 = TopoDS::Vertex(S2);
602           Perform( F1, V2, B1, B2 );
603           break;
604         }
605         case TopAbs_EDGE :
606         {
607           TopoDS_Edge E2 = TopoDS::Edge(S2);
608           TopoDS_Face aTrimFace;
609           Standard_Boolean bIsInfinit;
610           TRIM_INFINIT_FACE( F1, E2, aTrimFace, bIsInfinit );
611           if (bIsInfinit)
612             F1 = aTrimFace;
613           Perform( F1, E2, B1, B2 );
614           break;
615         }
616         case TopAbs_FACE :
617         {
618           TopoDS_Face F2 = TopoDS::Face(S2);
619           Perform( F1, F2, B1, B2 );
620           break;
621         }
622         default:
623           break;
624       }
625       break;
626     }
627     default:
628       break;
629   }
630 }
631
632 /*********************************************************************************/
633
634 void BRepExtrema_DistanceSS::Perform(const TopoDS_Vertex& S1, const TopoDS_Vertex& S2)
635 {     
636   const gp_Pnt P1 = BRep_Tool::Pnt(S1);
637   const gp_Pnt P2 = BRep_Tool::Pnt(S2);
638
639   const Standard_Real Dst = P1.Distance(P2);
640   if ((Dst < myDstRef - myEps) || (fabs(Dst-myDstRef) < myEps))
641   { 
642     if (myDstRef > Dst)
643       myDstRef=Dst;
644     myModif=Standard_True;
645     const BRepExtrema_SolutionElem Sol1(Dst,P1,BRepExtrema_IsVertex,S1);
646     const BRepExtrema_SolutionElem Sol2(Dst,P2,BRepExtrema_IsVertex,S2);
647     SeqSolShape1.Append(Sol1);
648     SeqSolShape2.Append(Sol2);
649   }
650 }
651
652 /*********************************************************************************/
653
654 void BRepExtrema_DistanceSS::Perform(const TopoDS_Vertex& S1, const TopoDS_Edge& S2,
655                                      const Bnd_Box& B1, const Bnd_Box& B2)
656
657   if (BRep_Tool::Degenerated(S2))
658     return;
659
660   const Standard_Real Dst=B1.Distance(B2);
661   if ((Dst < myDstRef - myEps) || (fabs(Dst-myDstRef) < myEps))
662   {
663     BRepExtrema_ExtPC Ext(S1,S2);
664     const Standard_Integer NbExtrema = Ext.IsDone()? Ext.NbExt() : 0;
665     if ( NbExtrema > 0 )
666     {
667       // Search minimum distance Dstmin
668       Standard_Integer i;
669       Standard_Real Dstmin = Ext.SquareDistance(1);
670       for (i = 2; i <= NbExtrema; i++)
671       {
672         const Standard_Real sDst = Ext.SquareDistance(i);
673         if (sDst<Dstmin)
674           Dstmin=sDst;
675           }
676       Dstmin = sqrt(Dstmin);
677       if ((Dstmin < myDstRef - myEps) || (fabs(Dstmin-myDstRef) < myEps))
678       {
679         Standard_Real Udeb,Ufin;
680         BRep_Tool::Range(S2,Udeb,Ufin);
681
682         gp_Pnt Pt,P1=BRep_Tool::Pnt(S1);
683         const Standard_Real epsP=Precision::PConfusion();
684
685         for (i = 1; i <= NbExtrema; i++)
686         {
687           if (fabs(Dstmin-sqrt(Ext.SquareDistance(i)))<myEps)
688           {
689             Pt=Ext.Point(i);
690             if (TRI_SOLUTION(SeqSolShape2,Pt))
691             {
692               // Check if the parameter does not correspond to a vertex
693               const Standard_Real t = Ext.Parameter(i);
694               if ( (fabs(t-Udeb)>=epsP) && (fabs(t-Ufin)>epsP) )
695               {
696                 if (myDstRef > Dstmin)
697                   myDstRef=Dstmin;
698                 myModif=Standard_True;
699                 const BRepExtrema_SolutionElem Sol1(Dstmin,P1,BRepExtrema_IsVertex,S1);
700                 const BRepExtrema_SolutionElem Sol2(Dstmin,Pt,BRepExtrema_IsOnEdge,S2,t);
701                 SeqSolShape1.Append(Sol1);
702                 SeqSolShape2.Append(Sol2);
703               }
704             }
705           }
706         }
707       }
708     }
709   }
710 }
711
712 void BRepExtrema_DistanceSS::Perform(const TopoDS_Edge& S1,const TopoDS_Vertex& S2,
713                                      const Bnd_Box& B1,const Bnd_Box& B2)
714 {
715   if (BRep_Tool::Degenerated(S1))
716     return;
717
718   const Standard_Real Dst=B1.Distance(B2);
719   if ((Dst < myDstRef - myEps) || (fabs(Dst-myDstRef) < myEps))
720   {
721     BRepExtrema_ExtPC Ext(S2,S1);
722     const Standard_Integer NbExtrema = Ext.IsDone()? Ext.NbExt() : 0;
723     if ( NbExtrema > 0 )
724     {
725       // Search minimum distance Dstmin
726       Standard_Integer i;
727       Standard_Real Dstmin = Ext.SquareDistance(1);
728       for (i = 2; i <= NbExtrema; i++)
729       {
730         const Standard_Real sDst = Ext.SquareDistance(i);
731         if (sDst<Dstmin)
732           Dstmin=sDst;
733           }
734       Dstmin = sqrt(Dstmin);
735       if ((Dstmin < myDstRef - myEps) || (fabs(Dstmin-myDstRef) < myEps))
736       {
737         Standard_Real Udeb,Ufin;
738         BRep_Tool::Range(S1,Udeb,Ufin);
739
740         gp_Pnt Pt, P2 = BRep_Tool::Pnt(S2);
741         const Standard_Real epsP=Precision::PConfusion();
742
743         for (i = 1; i <= NbExtrema; i++)
744         {
745           if (fabs(Dstmin-sqrt(Ext.SquareDistance(i)))<myEps)
746           {
747             Pt=Ext.Point(i);
748             if (TRI_SOLUTION(SeqSolShape1,Pt))
749             {
750               // Check if the parameter does not correspond to a vertex
751               const Standard_Real t = Ext.Parameter(i);
752               if ( (fabs(t-Udeb)>=epsP) && (fabs(t-Ufin)>epsP) )
753               {
754                 if (myDstRef > Dstmin)
755                   myDstRef=Dstmin;
756                 myModif=Standard_True;
757                 const BRepExtrema_SolutionElem Sol1(Dstmin,Pt,BRepExtrema_IsOnEdge,S1,t);
758                 const BRepExtrema_SolutionElem Sol2(Dstmin,P2,BRepExtrema_IsVertex,S2);
759                 SeqSolShape1.Append(Sol1);
760                 SeqSolShape2.Append(Sol2);
761               }
762             }
763           }
764         }
765       }
766     }
767   }
768 }
769
770 /*********************************************************************************/
771
772 void BRepExtrema_DistanceSS::Perform(const TopoDS_Vertex& S1, const TopoDS_Face& S2, 
773                                      const Bnd_Box& B1, const Bnd_Box& B2)
774 {
775   const Standard_Real Dst=B1.Distance(B2);
776   if ((Dst < myDstRef - myEps) || (fabs(Dst-myDstRef) < myEps))
777   { 
778     BRepExtrema_ExtPF Ext(S1,S2,myFlag,myAlgo);
779     const Standard_Integer NbExtrema = Ext.IsDone()? Ext.NbExt() : 0;
780     if ( NbExtrema > 0 )
781     {
782       // Search minimum distance Dstmin
783       Standard_Integer i;
784       Standard_Real Dstmin = Ext.SquareDistance(1);
785       for (i = 2; i <= NbExtrema; i++)
786       {
787         const Standard_Real sDst = Ext.SquareDistance(i);
788         if (sDst<Dstmin) 
789           Dstmin=sDst;
790       }
791       Dstmin = sqrt(Dstmin);
792       if ((Dstmin < myDstRef - myEps) || (fabs(Dstmin-myDstRef) < myEps))
793       {
794         Standard_Real U,V;
795         gp_Pnt Pt,P1=BRep_Tool::Pnt(S1);
796         BRepClass_FaceClassifier classifier;
797         const Standard_Real tol = BRep_Tool::Tolerance(S2);
798  
799         for (i = 1; i <= NbExtrema; i++)
800         {
801           if (fabs(Dstmin-sqrt(Ext.SquareDistance(i)))<myEps)
802           {
803             Pt=Ext.Point(i);
804             if (TRI_SOLUTION(SeqSolShape2,Pt))
805             {
806               // Check if the parameter does not correspond to a vertex
807               Ext.Parameter(i,U,V);
808               const gp_Pnt2d PUV(U,V);
809               classifier.Perform(S2,PUV,tol);
810               if (classifier.State()==TopAbs_IN)
811               {
812                 if (myDstRef > Dstmin)
813                   myDstRef=Dstmin;
814                 myModif=Standard_True;
815                 const BRepExtrema_SolutionElem Sol1(Dstmin,P1,BRepExtrema_IsVertex,S1);
816                 const BRepExtrema_SolutionElem Sol2(Dstmin,Pt,BRepExtrema_IsInFace,S2,U,V);
817                 SeqSolShape1.Append(Sol1);
818                 SeqSolShape2.Append(Sol2);                
819               }
820             }
821           }
822         }
823       }
824     }
825   }
826 }
827
828 void BRepExtrema_DistanceSS::Perform(const TopoDS_Face& S1, const TopoDS_Vertex& S2, 
829                                      const Bnd_Box& B1, const Bnd_Box& B2)
830 {
831   const Standard_Real Dst=B1.Distance(B2);
832   if ((Dst < myDstRef - myEps) || (fabs(Dst-myDstRef) < myEps))
833   { 
834     BRepExtrema_ExtPF Ext(S2,S1,myFlag,myAlgo);
835     const Standard_Integer NbExtrema = Ext.IsDone()? Ext.NbExt() : 0;
836     if ( NbExtrema > 0 )
837     {
838       // Search minimum distance Dstmin
839       Standard_Integer i;
840       Standard_Real Dstmin = Ext.SquareDistance(1);
841       for (i = 2; i <= NbExtrema; i++)
842       {
843         const Standard_Real sDst = Ext.SquareDistance(i);
844         if (sDst<Dstmin) 
845           Dstmin=sDst;
846       }
847       Dstmin = sqrt(Dstmin);
848       if ((Dstmin < myDstRef - myEps) || (fabs(Dstmin-myDstRef) < myEps))
849       {
850         Standard_Real U,V;
851         gp_Pnt Pt,P2=BRep_Tool::Pnt(S2);
852         BRepClass_FaceClassifier classifier;
853         const Standard_Real tol = BRep_Tool::Tolerance(S1);
854  
855         for (i = 1; i <= NbExtrema; i++)
856         {
857           if (fabs(Dstmin-sqrt(Ext.SquareDistance(i)))<myEps)
858           {
859             Pt=Ext.Point(i);
860             if (TRI_SOLUTION(SeqSolShape1,Pt))
861             {
862               // Check if the parameter does not correspond to a vertex
863               Ext.Parameter(i,U,V);
864               const gp_Pnt2d PUV(U,V);
865               classifier.Perform(S1,PUV,tol);
866               if (classifier.State()==TopAbs_IN)
867               {
868                 if (myDstRef > Dstmin)
869                   myDstRef=Dstmin;
870                 myModif=Standard_True;
871                 const BRepExtrema_SolutionElem Sol1(Dstmin,Pt,BRepExtrema_IsInFace,S1,U,V);
872                 const BRepExtrema_SolutionElem Sol2(Dstmin,P2,BRepExtrema_IsVertex,S2);
873                 SeqSolShape1.Append(Sol1);
874                 SeqSolShape2.Append(Sol2);                
875               }
876             }
877           }
878         }
879       }
880     }
881   }
882 }
883
884 /*********************************************************************************/
885
886 void BRepExtrema_DistanceSS::Perform(const TopoDS_Edge& S1, const TopoDS_Edge& S2,
887                                      const Bnd_Box& B1, const Bnd_Box& B2)
888 {
889   if (BRep_Tool::Degenerated(S1) || BRep_Tool::Degenerated(S2))
890     return;
891
892   const Standard_Real Dst=B1.Distance(B2);
893   if ((Dst < myDstRef - myEps) || (fabs(Dst-myDstRef) < myEps))
894   {
895     const Standard_Real DstRef = myDstRef;
896
897     BRepExtrema_ExtCC Ext(S1,S2);
898         const Standard_Integer NbExtrema = Ext.IsDone()? (Ext.IsParallel()? 0 : Ext.NbExt()) : 0;
899     if ( NbExtrema > 0 )
900     {
901       // Search minimum distance Dstmin
902       Standard_Integer i;
903       Standard_Real Dstmin = Ext.SquareDistance(1);
904       for (i = 2; i <= NbExtrema; i++)
905       {
906         const Standard_Real sDst = Ext.SquareDistance(i);
907         if (sDst<Dstmin) 
908           Dstmin=sDst;
909           }
910       Dstmin = sqrt(Dstmin);
911       if ((Dstmin < myDstRef - myEps) || (fabs(Dstmin-myDstRef) < myEps))
912       {
913         Standard_Real Udeb1,Ufin1,Udeb2,Ufin2;
914         BRep_Tool::Range(S1,Udeb1,Ufin1);
915         BRep_Tool::Range(S2,Udeb2,Ufin2);
916
917         gp_Pnt Pt1,Pt2;
918         const Standard_Real epsP=Precision::PConfusion();
919
920         for (i=1;i<=NbExtrema;i++)
921         {
922           if (fabs(Dstmin-sqrt(Ext.SquareDistance(i)))<myEps)
923           {
924             Pt1=Ext.PointOnE1(i);
925             Pt2=Ext.PointOnE2(i);
926             if (TRI_SOLUTION(SeqSolShape1,Pt1) || TRI_SOLUTION(SeqSolShape2,Pt2))
927             {
928               // Check if the parameters do not correspond to a vertex
929               const Standard_Real t1 = Ext.ParameterOnE1(i);
930               const Standard_Real t2 = Ext.ParameterOnE2(i);
931               if ((fabs(t1-Udeb1)>=epsP)&&(fabs(t1-Ufin1)>epsP)&&(fabs(t2-Udeb2)>=epsP)&&(fabs(t2-Ufin2)>epsP))
932               {
933                 if (myDstRef > Dstmin)
934                   myDstRef=Dstmin;
935                 myModif=Standard_True;
936                 const BRepExtrema_SolutionElem Sol1(Dstmin,Pt1,BRepExtrema_IsOnEdge,S1,t1);
937                 const BRepExtrema_SolutionElem Sol2(Dstmin,Pt2,BRepExtrema_IsOnEdge,S2,t2);
938                 SeqSolShape1.Append(Sol1);
939                 SeqSolShape2.Append(Sol2);
940               }
941             }
942           }
943         }
944       }
945     }
946
947     BRepExtrema_SeqOfSolution SeqSolution1;
948     BRepExtrema_SeqOfSolution SeqSolution2;
949
950     PERFORM_C0(S1, S2, SeqSolution1, SeqSolution2, DstRef, myDstRef, myEps);
951      
952     BRepExtrema_SeqOfSolution seqSol1;
953     BRepExtrema_SeqOfSolution seqSol2;
954         
955     if (SeqSolution1.Length() > 0 && SeqSolution2.Length() > 0)
956       MIN_SOLUTION(SeqSolution1, SeqSolution2, myDstRef, myEps, seqSol1, seqSol2);
957      
958     if (!seqSol1.IsEmpty() && !seqSol2.IsEmpty())
959     {
960       SeqSolShape1.Append(seqSol1);
961       SeqSolShape2.Append(seqSol2);     
962       myModif = Standard_True;
963     }
964   }
965 }
966
967 /*********************************************************************************/
968
969 void BRepExtrema_DistanceSS::Perform(const TopoDS_Edge& S1, const TopoDS_Face& S2,
970                                      const Bnd_Box& B1, const Bnd_Box& B2)
971 {
972   if (BRep_Tool::Degenerated(S1))
973     return;
974     
975   const Standard_Real Dst=B1.Distance(B2);
976   if ((Dst < myDstRef - myEps) || (fabs(Dst-myDstRef) < myEps))
977   {
978     BRepClass_FaceClassifier classifier;
979
980     BRepExtrema_ExtCF Ext(S1,S2);
981         const Standard_Integer NbExtrema = Ext.IsDone()? (Ext.IsParallel()? 0 : Ext.NbExt()) : 0;
982     if ( NbExtrema > 0 )
983     {
984       // Search minimum distance Dstmin
985       Standard_Integer i;
986       Standard_Real Dstmin = Ext.SquareDistance(1);
987       for (i = 2; i <= NbExtrema; i++)
988       {
989         const Standard_Real sDst = Ext.SquareDistance(i);
990         if (sDst<Dstmin) 
991           Dstmin=sDst;
992       }
993       Dstmin = sqrt(Dstmin);
994       if ((Dstmin < myDstRef - myEps) || (fabs(Dstmin-myDstRef) < myEps))
995       {
996         Standard_Real Udeb,Ufin,U,V;
997         BRep_Tool::Range(S1,Udeb,Ufin);
998         const Standard_Real tol=BRep_Tool::Tolerance(S2);
999
1000         gp_Pnt Pt1,Pt2;
1001         const Standard_Real epsP=Precision::PConfusion();
1002
1003         for (i = 1; i <= NbExtrema; i++)
1004         {
1005           if (fabs(Dstmin-sqrt(Ext.SquareDistance(i)))<myEps)
1006           {
1007             Pt1=Ext.PointOnEdge(i);
1008             Pt2=Ext.PointOnFace(i);
1009             if (TRI_SOLUTION(SeqSolShape1,Pt1) || TRI_SOLUTION(SeqSolShape2,Pt2))
1010             {
1011               // Check if the parameter does not correspond to a vertex
1012               const Standard_Real t1 = Ext.ParameterOnEdge(i);
1013               if ((fabs(t1-Udeb)>=epsP)&&(fabs(t1-Ufin)>epsP))
1014               {
1015                 Ext.ParameterOnFace(i,U,V);
1016                 const gp_Pnt2d PUV(U,V);
1017                 classifier.Perform(S2,PUV,tol);
1018                 if (classifier.State()==TopAbs_IN)
1019                 {
1020                   if (myDstRef > Dstmin)
1021                     myDstRef=Dstmin;
1022                   myModif=Standard_True;
1023                   const BRepExtrema_SolutionElem Sol1(Dstmin,Pt1,BRepExtrema_IsOnEdge,S1,t1);
1024                   const BRepExtrema_SolutionElem Sol2(Dstmin,Pt2,BRepExtrema_IsInFace,S2,U,V);
1025                   SeqSolShape1.Append(Sol1);
1026                   SeqSolShape2.Append(Sol2);              
1027                 }
1028               }
1029             }
1030           }
1031         }
1032       }
1033     }
1034
1035     Standard_Real aFirst, aLast;
1036     Handle(Geom_Curve) pCurv = BRep_Tool::Curve(S1, aFirst, aLast);
1037     if (pCurv->Continuity() == GeomAbs_C0)
1038     {
1039       BRepExtrema_SeqOfSolution SeqSolution1;
1040       BRepExtrema_SeqOfSolution SeqSolution2;
1041
1042       GeomAdaptor_Curve aAdaptorCurve(pCurv, aFirst, aLast);
1043       const Standard_Integer nbIntervals = aAdaptorCurve.NbIntervals(GeomAbs_C1);
1044
1045       TColStd_Array1OfReal arrInter(1,1+nbIntervals);
1046       aAdaptorCurve.Intervals(arrInter, GeomAbs_C1);
1047
1048       gp_Pnt Pt;
1049       Standard_Real U,V;
1050       const Standard_Real tol = BRep_Tool::Tolerance(S2);
1051
1052       Standard_Integer i;
1053       for (i = 1; i <= arrInter.Length(); i++)
1054       {
1055         const Standard_Real aParameter = arrInter(i);
1056         gp_Pnt aPnt = aAdaptorCurve.Value(aParameter);
1057         TopoDS_Vertex V1 = BRepBuilderAPI_MakeVertex(aPnt);
1058
1059         BRepExtrema_ExtPF ExtPF(V1,S2);
1060         const Standard_Integer NbExtremaPF = ExtPF.IsDone()? ExtPF.NbExt() : 0;
1061         if (NbExtremaPF > 0 )
1062         {
1063           // Search minimum distance Dstmin
1064           Standard_Integer ii;
1065           Standard_Real Dstmin = ExtPF.SquareDistance(1);
1066           for (ii = 2; ii <= NbExtremaPF; ii++)
1067           {
1068             const Standard_Real sDst = ExtPF.SquareDistance(ii);
1069             if (sDst<Dstmin)
1070               Dstmin=sDst;
1071           }
1072           Dstmin = sqrt(Dstmin);
1073
1074           if ((Dstmin < myDstRef - myEps) || (fabs(Dstmin-myDstRef) < myEps))
1075           {
1076             for (ii = 1; ii <= NbExtremaPF; ii++)
1077             { 
1078               if (fabs(Dstmin-sqrt(ExtPF.SquareDistance(ii)))<myEps)
1079               { 
1080                 // Check if the parameter does not correspond to a vertex
1081                 ExtPF.Parameter(ii,U,V);
1082                 const gp_Pnt2d PUV(U,V);
1083                                 classifier.Perform(S2,PUV,tol);
1084                 if (classifier.State()==TopAbs_IN)
1085                 {
1086                   if (myDstRef > Dstmin)
1087                     myDstRef=Dstmin;
1088                   myModif=Standard_True;
1089                   const BRepExtrema_SolutionElem Sol1(Dstmin,aPnt,BRepExtrema_IsOnEdge,S1,aParameter);
1090                   const BRepExtrema_SolutionElem Sol2(Dstmin,ExtPF.Point(ii),BRepExtrema_IsInFace,S2,U,V);
1091                   SeqSolution1.Append(Sol1);
1092                   SeqSolution2.Append(Sol2);
1093                 }
1094               }
1095             }
1096           }
1097         }
1098       }
1099
1100       BRepExtrema_SeqOfSolution seqSol1;
1101       BRepExtrema_SeqOfSolution seqSol2;
1102       if (SeqSolution1.Length() > 0 && SeqSolution2.Length() > 0)
1103         MIN_SOLUTION(SeqSolution1, SeqSolution2, myDstRef, myEps, seqSol1, seqSol2);
1104             
1105       if (!seqSol1.IsEmpty() && !seqSol2.IsEmpty())
1106       {
1107         SeqSolShape1.Append(seqSol1);
1108         SeqSolShape2.Append(seqSol2);
1109       }
1110     }
1111   }
1112 }
1113
1114 void BRepExtrema_DistanceSS::Perform(const TopoDS_Face& S1, const TopoDS_Edge& S2,
1115                                      const Bnd_Box& B1, const Bnd_Box& B2)
1116 {
1117   if (BRep_Tool::Degenerated(S2))
1118     return;
1119     
1120   const Standard_Real Dst=B1.Distance(B2);
1121   if ((Dst < myDstRef - myEps) || (fabs(Dst-myDstRef) < myEps))
1122   {
1123     BRepClass_FaceClassifier classifier;
1124
1125     BRepExtrema_ExtCF Ext(S2,S1);
1126         const Standard_Integer NbExtrema = Ext.IsDone()? (Ext.IsParallel()? 0 : Ext.NbExt()) : 0;
1127     if ( NbExtrema > 0 )
1128     {
1129       // Search minimum distance Dstmin
1130       Standard_Integer i;
1131       Standard_Real Dstmin = Ext.SquareDistance(1);
1132       for (i = 2; i <= NbExtrema; i++)
1133       {
1134         const Standard_Real sDst = Ext.SquareDistance(i);
1135         if (sDst<Dstmin) 
1136           Dstmin=sDst;
1137       }
1138       Dstmin = sqrt(Dstmin);
1139       if ((Dstmin < myDstRef - myEps) || (fabs(Dstmin-myDstRef) < myEps))
1140       {
1141         Standard_Real Udeb,Ufin,U,V;
1142         BRep_Tool::Range(S2,Udeb,Ufin);
1143         const Standard_Real tol=BRep_Tool::Tolerance(S1);
1144
1145         gp_Pnt Pt1,Pt2;
1146         const Standard_Real epsP=Precision::PConfusion();
1147
1148         for (i = 1; i <= NbExtrema; i++)
1149         {
1150           if (fabs(Dstmin-sqrt(Ext.SquareDistance(i)))<myEps)
1151           {
1152             Pt1=Ext.PointOnEdge(i);
1153             Pt2=Ext.PointOnFace(i);
1154             if (TRI_SOLUTION(SeqSolShape1,Pt1) || TRI_SOLUTION(SeqSolShape2,Pt2))
1155             {
1156               // Check if the parameter does not correspond to a vertex
1157               const Standard_Real t1 = Ext.ParameterOnEdge(i);
1158               if ((fabs(t1-Udeb)>=epsP)&&(fabs(t1-Ufin)>epsP))
1159               {
1160                 Ext.ParameterOnFace(i,U,V);
1161                 const gp_Pnt2d PUV(U,V);
1162                 classifier.Perform(S1,PUV,tol);
1163                 if (classifier.State()==TopAbs_IN)
1164                 {
1165                   if (myDstRef > Dstmin)
1166                     myDstRef=Dstmin;
1167                   myModif=Standard_True;
1168                   const BRepExtrema_SolutionElem Sol2(Dstmin,Pt1,BRepExtrema_IsOnEdge,S2,t1);
1169                   const BRepExtrema_SolutionElem Sol1(Dstmin,Pt2,BRepExtrema_IsInFace,S1,U,V);
1170                   SeqSolShape1.Append(Sol1);
1171                   SeqSolShape2.Append(Sol2);              
1172                 }
1173               }
1174             }
1175           }
1176         }
1177       }
1178     }
1179
1180     Standard_Real aFirst, aLast;
1181     Handle(Geom_Curve) pCurv = BRep_Tool::Curve(S2, aFirst, aLast);
1182     if (pCurv->Continuity() == GeomAbs_C0)
1183     {
1184       BRepExtrema_SeqOfSolution SeqSolution1;
1185       BRepExtrema_SeqOfSolution SeqSolution2;
1186
1187       GeomAdaptor_Curve aAdaptorCurve(pCurv, aFirst, aLast);
1188       const Standard_Integer nbIntervals = aAdaptorCurve.NbIntervals(GeomAbs_C1);
1189
1190       TColStd_Array1OfReal arrInter(1,1+nbIntervals);
1191       aAdaptorCurve.Intervals(arrInter, GeomAbs_C1);
1192
1193       gp_Pnt Pt;
1194       Standard_Real U,V;
1195       const Standard_Real tol = BRep_Tool::Tolerance(S1);
1196
1197       Standard_Integer i;
1198       for (i = 1; i <= arrInter.Length(); i++)
1199       {
1200         const Standard_Real aParameter = arrInter(i);
1201         gp_Pnt aPnt = aAdaptorCurve.Value(aParameter);
1202         TopoDS_Vertex V1 = BRepBuilderAPI_MakeVertex(aPnt);
1203
1204         BRepExtrema_ExtPF ExtPF(V1,S1);
1205         const Standard_Integer NbExtremaPF = ExtPF.IsDone()? ExtPF.NbExt() : 0;
1206         if (NbExtremaPF > 0 )
1207         {
1208           // Search minimum distance Dstmin
1209           Standard_Integer ii;
1210           Standard_Real Dstmin = ExtPF.SquareDistance(1);
1211           for (ii = 2; ii <= NbExtremaPF; ii++)
1212           {
1213             const Standard_Real sDst = ExtPF.SquareDistance(ii);
1214             if (sDst<Dstmin)
1215               Dstmin=sDst;
1216           }
1217           Dstmin = sqrt(Dstmin);
1218
1219           if ((Dstmin < myDstRef - myEps) || (fabs(Dstmin-myDstRef) < myEps))
1220           {
1221             for (ii = 1; ii <= NbExtremaPF; ii++)
1222             { 
1223               if (fabs(Dstmin-sqrt(ExtPF.SquareDistance(ii)))<myEps)
1224               { 
1225                 // Check if the parameter does not correspond to a vertex
1226                 ExtPF.Parameter(ii,U,V);
1227                 const gp_Pnt2d PUV(U,V);
1228                                 classifier.Perform(S1,PUV,tol);
1229                 if (classifier.State()==TopAbs_IN)
1230                 {
1231                   if (myDstRef > Dstmin)
1232                     myDstRef=Dstmin;
1233                   myModif=Standard_True;
1234                   const BRepExtrema_SolutionElem Sol2(Dstmin,aPnt,BRepExtrema_IsOnEdge,S2,aParameter);
1235                   const BRepExtrema_SolutionElem Sol1(Dstmin,ExtPF.Point(ii),BRepExtrema_IsInFace,S1,U,V);
1236                   SeqSolution1.Append(Sol1);
1237                   SeqSolution2.Append(Sol2);
1238                 }
1239               }
1240             }
1241           }
1242         }
1243       }
1244
1245       BRepExtrema_SeqOfSolution seqSol1;
1246       BRepExtrema_SeqOfSolution seqSol2;
1247       if (SeqSolution1.Length() > 0 && SeqSolution2.Length() > 0)
1248         MIN_SOLUTION(SeqSolution1, SeqSolution2, myDstRef, myEps, seqSol1, seqSol2);
1249             
1250       if (!seqSol1.IsEmpty() && !seqSol2.IsEmpty())
1251       {
1252         SeqSolShape1.Append(seqSol1);
1253         SeqSolShape2.Append(seqSol2);
1254       }
1255     }
1256   }
1257 }
1258
1259 /*********************************************************************************/
1260
1261 void BRepExtrema_DistanceSS::Perform(const TopoDS_Face& S1, const TopoDS_Face& S2,
1262                                      const Bnd_Box& B1, const Bnd_Box& B2)
1263 {
1264   const Standard_Real Dst=B1.Distance(B2);
1265   if ((Dst < myDstRef - myEps) || (fabs(Dst-myDstRef) < myEps))
1266   { 
1267     BRepExtrema_ExtFF Ext(S1,S2);
1268         const Standard_Integer NbExtrema = Ext.IsDone()? (Ext.IsParallel()? 0 : Ext.NbExt()) : 0;
1269     if ( NbExtrema > 0 )
1270     {
1271       // Search minimum distance Dstmin
1272       Standard_Integer i;
1273       Standard_Real Dstmin = Ext.SquareDistance(1);
1274       for (i = 2; i <= NbExtrema; i++)
1275       {
1276         const Standard_Real sDst = Ext.SquareDistance(i);
1277         if (sDst<Dstmin)
1278           Dstmin=sDst;
1279       }
1280       Dstmin = sqrt(Dstmin);
1281       if ((Dstmin < myDstRef - myEps) || (fabs(Dstmin-myDstRef) < myEps))
1282       {
1283         const Standard_Real tol1=BRep_Tool::Tolerance(S1);
1284         const Standard_Real tol2=BRep_Tool::Tolerance(S2);
1285
1286         gp_Pnt Pt1,Pt2;
1287         gp_Pnt2d PUV;
1288         Standard_Real U1,V1,U2,V2;
1289         BRepClass_FaceClassifier classifier;
1290  
1291         for (i = 1; i <= NbExtrema; i++)
1292         {
1293           if (fabs(Dstmin-sqrt(Ext.SquareDistance(i)))<myEps)
1294           {
1295             Pt1=Ext.PointOnFace1(i);
1296             Pt2=Ext.PointOnFace2(i); 
1297             if (TRI_SOLUTION(SeqSolShape1,Pt1) || TRI_SOLUTION(SeqSolShape2,Pt2))
1298             {
1299               // Check if the parameter does not correspond to a vertex
1300               Ext.ParameterOnFace1(i,U1,V1);
1301               PUV.SetCoord(U1,V1);
1302               classifier.Perform(S1,PUV,tol1);
1303               if (classifier.State()==TopAbs_IN)
1304               {
1305                 Ext.ParameterOnFace2(i,U2,V2);
1306                 PUV.SetCoord(U2,V2);
1307                 classifier.Perform(S2,PUV,tol2);
1308                 if (classifier.State()==TopAbs_IN)
1309                 {
1310                   if (myDstRef > Dstmin)
1311                     myDstRef=Dstmin;
1312                   myModif=Standard_True;
1313                   const BRepExtrema_SolutionElem Sol1(Dstmin,Pt1,BRepExtrema_IsInFace,S1,U1,V1);
1314                   const BRepExtrema_SolutionElem Sol2(Dstmin,Pt2,BRepExtrema_IsInFace,S2,U2,V2);
1315                   SeqSolShape1.Append(Sol1);
1316                   SeqSolShape2.Append(Sol2);
1317                 }
1318               }
1319             }
1320           }
1321         }
1322       }
1323     }
1324   }
1325 }
1326
1327 /*********************************************************************************/