OCC22322 Improvement of Extrema performance
[occt.git] / src / BRepExtrema / BRepExtrema_DistanceSS.cxx
1 // File:    BRepExtrema_DistanceSS.cxx
2 // Created: Mon Apr 22 17:03:37 1996
3 // Author:      Maria PUMBORIOS
4 // Author:  Herve LOUESSARD 
5
6 // Modified: Sergey ZERCHANINOV
7
8 #include <BRepExtrema_DistanceSS.hxx>
9
10 #include <TopTools_IndexedMapOfShape.hxx>
11 #include <TopExp.hxx>
12 #include <gp_Pnt.hxx>
13 #include <gp_Pnt2d.hxx>
14 #include <BRep_Tool.hxx>
15 #include <BRepExtrema_SupportType.hxx>
16 #include <Standard_Real.hxx>
17 #include <BRepExtrema_SolutionElem.hxx>
18 #include <BRepExtrema_SeqOfSolution.hxx>
19 #include <Standard_Boolean.hxx>
20 #include <Standard_Integer.hxx> 
21 #include <TopAbs_ShapeEnum.hxx>
22 #include <TopoDS.hxx>
23 #include <Bnd_Box.hxx>
24 #include <BRepExtrema_ExtPC.hxx>
25 #include <BRepExtrema_ExtPF.hxx>
26 #include <Extrema_ExtFlag.hxx>
27 #include <BRepExtrema_ExtCC.hxx>
28 #include <BRepExtrema_ExtCF.hxx>
29 #include <BRepExtrema_ExtFF.hxx>
30 #include <BRepClass_FaceClassifier.hxx>
31 #include <TopAbs.hxx>
32 #include <Geom_Curve.hxx>
33 #include <GeomAbs_Shape.hxx>
34 #include <GeomAdaptor_Curve.hxx>
35 #include <TColStd_Array1OfReal.hxx>
36 #include <BRepBuilderAPI_MakeVertex.hxx>
37 #include <BRepBuilderAPI_MakeEdge.hxx>
38 #include <BRepBuilderAPI_MakeFace.hxx>
39 #include <Geom_Surface.hxx>
40 #include <GeomAPI_ProjectPointOnSurf.hxx>
41 #include <GeomAPI_ProjectPointOnCurve.hxx>
42 #include <Geom_RectangularTrimmedSurface.hxx>
43 #include <Geom_TrimmedCurve.hxx>
44 #include <BRepBndLib.hxx>
45 #include <BRepTools.hxx>
46 #include <TColgp_Array1OfPnt.hxx>
47
48
49 /*********************************************************************************/
50
51 //------------------------------------------------------------------------------
52 // function: TRI_SOLUTION
53 //------------------------------------------------------------------------------
54 static Standard_Boolean TRI_SOLUTION (const BRepExtrema_SeqOfSolution& SeqSol, const gp_Pnt& Pt)
55 {
56   const Standard_Integer Nbsol = SeqSol.Length();
57   for (Standard_Integer i = 1; i <= Nbsol; i++)
58   {
59     const Standard_Real dst = SeqSol.Value(i).Point().Distance(Pt);
60     if (dst <= Precision::Confusion()) return Standard_False;
61   }
62   return Standard_True;
63 }  
64
65 //------------------------------------------------------------------------------
66 // function: MIN_SOLUTION
67 //------------------------------------------------------------------------------
68 static void MIN_SOLUTION (const BRepExtrema_SeqOfSolution& SeqSol1,
69                           const BRepExtrema_SeqOfSolution& SeqSol2,
70                           const Standard_Real DstRef,
71                           const Standard_Real Eps,
72                           BRepExtrema_SeqOfSolution& seqSol1,
73                           BRepExtrema_SeqOfSolution& seqSol2)
74 {
75   const Standard_Integer nbSol = SeqSol1.Length();
76   for (Standard_Integer i = 1; i <= nbSol; i++)
77   {
78     const Standard_Real dst1 = SeqSol1.Value(i).Dist();
79     if (fabs(dst1 - DstRef) < Eps)
80         {         
81       seqSol1.Append(SeqSol1.Value(i));
82       seqSol2.Append(SeqSol2.Value(i));
83         }
84   }
85 }
86
87 //------------------------------------------------------------------------------
88 // function: TRIM_INFINIT_EDGE
89 //------------------------------------------------------------------------------
90 static void TRIM_INFINIT_EDGE(const TopoDS_Edge& S1, const TopoDS_Edge& S2, TopoDS_Edge& aResEdge,
91                               Standard_Boolean& bIsTrim1, Standard_Boolean& bIsTrim2)
92 {
93   if ( BRep_Tool::Degenerated(S1) || BRep_Tool::Degenerated(S2) )
94     return;
95
96   aResEdge = S2;
97   Standard_Real aFirst1, aLast1, aFirst2, aLast2;
98   Handle(Geom_Curve) pCurv1 = BRep_Tool::Curve(S1, aFirst1, aLast1);
99   Handle(Geom_Curve) pCurv2 = BRep_Tool::Curve(S2, aFirst2, aLast2);
100
101   if (Precision::IsInfinite(aFirst1) &&
102       Precision::IsInfinite(aLast1)  &&
103       Precision::IsInfinite(aFirst2) &&
104       Precision::IsInfinite(aLast2))
105     return;
106   
107   Standard_Real Umin, Umax;
108   Standard_Boolean bUmin, bUmax;
109   bUmin = bUmax = Standard_False;
110
111   Handle(Geom_Curve) pCurv;
112   if ( !pCurv1.IsNull() && (Precision::IsInfinite(aFirst1) || Precision::IsInfinite(aLast1)) )
113   {
114     pCurv = pCurv1;
115     bIsTrim1 = Standard_True;
116     if (!Precision::IsInfinite(aFirst1))
117     {
118       bUmin = Standard_True;
119       Umin = aFirst1;
120     }
121     else if (!Precision::IsInfinite(aLast1))
122     {
123       bUmax = Standard_True;
124       Umax = aLast1;
125     }
126   }
127   else if ( !pCurv2.IsNull() && (Precision::IsInfinite(aFirst2) || Precision::IsInfinite(aLast2)) )
128   {
129     pCurv = pCurv2;
130     bIsTrim2 = Standard_True;
131     if (!Precision::IsInfinite(aFirst2))
132     {
133       bUmin = Standard_True;
134       Umin = aFirst2;
135     }
136     else if (!Precision::IsInfinite(aLast2))
137     {
138       bUmax = Standard_True;
139       Umax = aLast2;
140     }
141   }
142   if (bIsTrim1 || bIsTrim2)
143   {
144     Bnd_Box aEdgeBox;
145     if (bIsTrim1)
146       BRepBndLib::Add(S2, aEdgeBox);
147     if (bIsTrim2)
148       BRepBndLib::Add(S1, aEdgeBox);
149     Standard_Real Xmin, Ymin, Zmin, Xmax, Ymax, Zmax;
150     aEdgeBox.Get(Xmin, Ymin, Zmin, Xmax, Ymax, Zmax);
151
152     const gp_Pnt aPnt0(Xmin, Ymin, Zmin);
153     const gp_Pnt aPnt1(Xmin, Ymax, Zmin);
154     const gp_Pnt aPnt2(Xmin, Ymax, Zmax);
155     const gp_Pnt aPnt3(Xmin, Ymin, Zmax);
156     const gp_Pnt aPnt4(Xmax, Ymax, Zmin);
157     const gp_Pnt aPnt5(Xmax, Ymax, Zmax);
158     const gp_Pnt aPnt6(Xmax, Ymin, Zmax);
159     const gp_Pnt aPnt7(Xmax, Ymin, Zmin);
160
161         Standard_Real arrU[8];
162     GeomAPI_ProjectPointOnCurve aProj(aPnt0, pCurv);
163     /*szv:aProj.Perform(aPnt0);*/ arrU[0] = aProj.LowerDistanceParameter();
164     aProj.Perform(aPnt1); arrU[1] = aProj.LowerDistanceParameter();
165     aProj.Perform(aPnt2); arrU[2] = aProj.LowerDistanceParameter();
166     aProj.Perform(aPnt3); arrU[3] = aProj.LowerDistanceParameter();
167     aProj.Perform(aPnt4); arrU[4] = aProj.LowerDistanceParameter();
168     aProj.Perform(aPnt5); arrU[5] = aProj.LowerDistanceParameter();
169     aProj.Perform(aPnt6); arrU[6] = aProj.LowerDistanceParameter();
170     aProj.Perform(aPnt7); arrU[7] = aProj.LowerDistanceParameter();
171     
172     if (!bUmin)
173       Umin = arrU[0];
174         
175     if (!bUmax)
176       Umax = arrU[0];
177
178     Standard_Integer i = 0;
179     while (i < 8)
180         {
181       const Standard_Real aU = arrU[i++];
182           if (aU < Umin)
183             Umin = aU;
184           else if (aU > Umax)
185             Umax = aU;
186         }
187
188     Standard_Real tol = Precision::Confusion();
189     if (bIsTrim1)
190       tol = BRep_Tool::Tolerance(S1);
191     else if (bIsTrim2)
192       tol = BRep_Tool::Tolerance(S2);
193
194     const Standard_Real EpsU = GeomAdaptor_Curve(pCurv).Resolution(3.*tol);
195     if (fabs(Umin - Umax) < EpsU)
196     {
197       Umin -= EpsU;
198       Umax += EpsU;
199     }
200
201     Handle(Geom_Curve) result = new Geom_TrimmedCurve(pCurv, Umin, Umax);
202     aResEdge = BRepBuilderAPI_MakeEdge(result);
203   }
204 }
205
206 //------------------------------------------------------------------------------
207 // function: TRIM_INFINIT_FACE
208 //------------------------------------------------------------------------------
209 static void TRIM_INFINIT_FACE(const TopoDS_Shape& S1, const TopoDS_Shape& S2,
210                               TopoDS_Face& aResFace, Standard_Boolean& bIsInfinit)
211 {
212   bIsInfinit = Standard_False;
213
214   TopAbs_ShapeEnum Type1 = S1.ShapeType();     
215   TopAbs_ShapeEnum Type2 = S2.ShapeType();
216
217   TopoDS_Edge aE;
218   TopoDS_Face aF;
219   
220   if (Type1 == TopAbs_EDGE && Type2 == TopAbs_FACE)
221   {
222     aE = TopoDS::Edge(S1);
223     if ( BRep_Tool::Degenerated(aE) )
224       return;
225     aF = TopoDS::Face(S2);
226   }
227   else if (Type2 == TopAbs_EDGE && Type1 == TopAbs_FACE)
228   {
229     aE = TopoDS::Edge(S2);
230     if ( BRep_Tool::Degenerated(aE) )
231       return;
232     aF = TopoDS::Face(S1);
233   }
234   else
235   {
236     bIsInfinit = Standard_False;
237     return;
238   }
239
240   aResFace = aF;
241   Handle(Geom_Surface) pSurf = BRep_Tool::Surface(aF);
242  
243   const Standard_Boolean bRestrict = BRep_Tool::NaturalRestriction(aF);
244
245   Standard_Real U1, V1, U2, V2;
246   Standard_Real Umin, Umax, Vmin, Vmax;
247   Standard_Boolean bUmin, bUmax, bVmin, bVmax;
248   bUmin = bUmax = bVmin = bVmax = Standard_False;
249   Standard_Boolean bIsTrim = Standard_False;
250
251   if (bRestrict)
252   {
253     pSurf->Bounds(U1, U2, V1, V2);
254     if (Precision::IsInfinite(U1))
255       bIsTrim = Standard_True;
256     else
257     {
258       Umin = U1;
259       bUmin = Standard_True;
260     }
261
262     if (Precision::IsInfinite(U2))
263       bIsTrim = Standard_True;
264     else
265     {
266       Umax = U2;
267       bUmax = Standard_True;
268     }
269
270     if (Precision::IsInfinite(V1))
271       bIsTrim = Standard_True;
272     else
273         {
274       Vmin = V1;
275       bVmin = Standard_True;
276         }
277       
278     if (Precision::IsInfinite(V2))
279       bIsTrim = Standard_True;
280     else
281         {
282       Vmax = V2;
283       bVmax = Standard_True;
284     }
285   }
286   else
287   {
288     BRepTools::UVBounds(aF, U1, U2, V1, V2);
289     if (Precision::IsInfinite(U1) &&
290         Precision::IsInfinite(U2) &&
291         Precision::IsInfinite(V1) &&
292         Precision::IsInfinite(V2))
293       bIsTrim = Standard_True;
294   }
295
296   if (bIsTrim)
297   {      
298     Bnd_Box aEdgeBox;
299     BRepBndLib::Add(aE, aEdgeBox);
300
301     if(aEdgeBox.IsWhole())
302       return;
303
304     Standard_Real Xmin, Ymin, Zmin, Xmax, Ymax, Zmax;
305     aEdgeBox.Get(Xmin, Ymin, Zmin, Xmax, Ymax, Zmax);
306
307     const gp_Pnt aPnt0(Xmin, Ymin, Zmin);
308     const gp_Pnt aPnt1(Xmin, Ymax, Zmin);
309     const gp_Pnt aPnt2(Xmin, Ymax, Zmax);
310     const gp_Pnt aPnt3(Xmin, Ymin, Zmax);
311     const gp_Pnt aPnt4(Xmax, Ymax, Zmin);
312     const gp_Pnt aPnt5(Xmax, Ymax, Zmax);
313     const gp_Pnt aPnt6(Xmax, Ymin, Zmax);
314     const gp_Pnt aPnt7(Xmax, Ymin, Zmin);
315
316     Standard_Real arrU[8], arrV[8];
317     GeomAPI_ProjectPointOnSurf aProj(aPnt0, pSurf);
318     /*szv:aProj.Perform(aPnt0);*/ if (aProj.IsDone()) aProj.LowerDistanceParameters(arrU[0],arrV[0]);
319     aProj.Perform(aPnt1); if (aProj.IsDone()) aProj.LowerDistanceParameters(arrU[1],arrV[1]);
320     aProj.Perform(aPnt2); if (aProj.IsDone()) aProj.LowerDistanceParameters(arrU[2],arrV[2]);
321     aProj.Perform(aPnt3); if (aProj.IsDone()) aProj.LowerDistanceParameters(arrU[3],arrV[3]);
322     aProj.Perform(aPnt4); if (aProj.IsDone()) aProj.LowerDistanceParameters(arrU[4],arrV[4]);
323     aProj.Perform(aPnt5); if (aProj.IsDone()) aProj.LowerDistanceParameters(arrU[5],arrV[5]);
324     aProj.Perform(aPnt6); if (aProj.IsDone()) aProj.LowerDistanceParameters(arrU[6],arrV[6]);
325     aProj.Perform(aPnt7); if (aProj.IsDone()) aProj.LowerDistanceParameters(arrU[7],arrV[7]);
326
327     if (!bUmin)
328       Umin = arrU[0];
329     if (!bUmax)
330       Umax = arrU[0];
331     if (!bVmin)
332       Vmin = arrV[0];
333     if (!bVmax)
334       Vmax = arrV[0];
335
336     Standard_Integer i = 0;
337     while (i < 8)
338         {
339       const Standard_Real aU = arrU[i];
340           if (aU < Umin)
341             Umin = aU;
342           else if (aU > Umax)
343             Umax = aU;
344
345       const Standard_Real aV = arrV[i];
346           if (aV < Vmin)
347             Vmin = aV;
348           else if (aV > Vmax)
349             Vmax = aV;
350         }
351       
352     GeomAdaptor_Surface aGAS(pSurf);
353     const Standard_Real tol = BRep_Tool::Tolerance(aF);
354
355     const Standard_Real EpsU = aGAS.UResolution(3.*tol);
356     if (fabs(Umin - Umax) < EpsU)
357     {
358       Umin -= EpsU;
359       Umax += EpsU;
360     }
361
362     const Standard_Real EpsV = aGAS.VResolution(3.*tol);
363     if (fabs(Vmin - Vmax) < EpsV)
364     {
365       Vmin -= EpsV;
366       Vmax += EpsV;
367     }
368
369     Handle(Geom_Surface) result = new Geom_RectangularTrimmedSurface(pSurf, Umin, Umax, Vmin, Vmax);
370     aResFace = BRepBuilderAPI_MakeFace(result);
371
372     bIsInfinit = Standard_True;
373   }
374   else
375     bIsInfinit = Standard_False;
376 }
377
378 //------------------------------------------------------------------------------
379 // static function: PERFORM_C0
380 //------------------------------------------------------------------------------
381 static void PERFORM_C0(const TopoDS_Edge &S1, const TopoDS_Edge &S2,
382                        BRepExtrema_SeqOfSolution& SeqSol1,
383                        BRepExtrema_SeqOfSolution& SeqSol2,
384                        const Standard_Real DstRef,
385                        Standard_Real& mDstRef,
386                        const Standard_Real Eps)
387 {
388   if ( BRep_Tool::Degenerated(S1) || BRep_Tool::Degenerated(S2) )
389     return;
390
391   Standard_Integer iE;
392   for (iE = 0; iE < 2; iE++)
393   {
394     TopoDS_Edge E, Eother;
395     if (iE == 0)
396         {
397           E      = S1;
398           Eother = S2;
399         }
400     else
401         {
402           E      = S2;
403           Eother = S1;
404         }
405
406     Standard_Real aFirst, aLast;
407     Handle(Geom_Curve) pCurv = BRep_Tool::Curve(E, aFirst, aLast);
408
409     Standard_Real aFOther, aLOther;
410     Handle(Geom_Curve) pCurvOther = BRep_Tool::Curve(Eother, aFOther, aLOther);
411
412     if (pCurv->Continuity() == GeomAbs_C0)
413         {
414       const Standard_Real epsP = Precision::PConfusion();
415
416       GeomAdaptor_Curve aAdaptorCurve(pCurv, aFirst, aLast);
417       const Standard_Integer nbIntervals = aAdaptorCurve.NbIntervals(GeomAbs_C1);
418
419       TColStd_Array1OfReal arrInter(1,1+nbIntervals);
420       aAdaptorCurve.Intervals(arrInter, GeomAbs_C1);
421
422       GeomAdaptor_Curve aAdaptorCurveOther(pCurvOther, aFOther, aLOther);
423       const Standard_Integer nbIntervalsOther = aAdaptorCurveOther.NbIntervals(GeomAbs_C1);
424       TColStd_Array1OfReal arrInterOther(1,1+nbIntervalsOther);
425       aAdaptorCurveOther.Intervals(arrInterOther, GeomAbs_C1);
426
427       Standard_Real Udeb,Ufin;
428       BRep_Tool::Range(Eother,Udeb,Ufin);
429
430       gp_Pnt P1,Pt;
431       Standard_Integer i, ii;  
432       BRepClass_FaceClassifier classifier;
433       for (i = 1; i <= arrInter.Length(); i++)
434       {
435         const Standard_Real aParameter = arrInter(i);
436         const gp_Pnt aPnt = aAdaptorCurve.Value(aParameter);
437         const TopoDS_Vertex V1 = BRepBuilderAPI_MakeVertex(aPnt);
438
439         BRepExtrema_ExtPC Ext(V1,Eother);
440         const Standard_Integer NbExtrema = Ext.IsDone()? Ext.NbExt() : 0;
441         if ( NbExtrema > 0 )
442                 { 
443           // Search minimum distance dstmin
444           Standard_Real Dstmin = Ext.SquareDistance(1);
445           for (ii = 2; ii <= NbExtrema; ii++)
446           {
447             const Standard_Real sDst = Ext.SquareDistance(ii);
448             if (sDst<Dstmin)
449               Dstmin=sDst;
450           }
451           Dstmin = sqrt(Dstmin);
452
453           if ((Dstmin < DstRef - Eps) || (fabs(Dstmin-DstRef) < Eps))
454             for (ii = 1; ii <= NbExtrema; ii++)
455             {
456               if (fabs(Dstmin-sqrt(Ext.SquareDistance(ii)))<Eps)
457               {
458                 Pt=Ext.Point(ii);
459                 if (TRI_SOLUTION(SeqSol2,Pt))
460                 {
461                   // Check if the parameter does not correspond to a vertex
462                   const Standard_Real t = Ext.Parameter(ii);
463                   if ((fabs(t-Udeb)>=epsP)&&(fabs(t-Ufin)>epsP))
464                   {
465                     if (mDstRef > Dstmin)
466                       mDstRef=Dstmin;
467                     const BRepExtrema_SolutionElem Sol1(Dstmin,aPnt,BRepExtrema_IsOnEdge,E,aParameter);
468                     const BRepExtrema_SolutionElem Sol2(Dstmin,Pt,BRepExtrema_IsOnEdge,Eother,t);
469                     SeqSol1.Append(iE == 0 ? Sol1 : Sol2);
470                     SeqSol2.Append(iE == 0 ? Sol2 : Sol1);
471                   }
472                 }
473               }
474             }
475         }
476         for (Standard_Integer i2 = 1; i2<=arrInterOther.Length(); i2++)
477         {
478           const Standard_Real aParameterOther = arrInterOther(i2);
479           const gp_Pnt aPntOther = aAdaptorCurveOther.Value(aParameterOther);
480           const Standard_Real Dst = aPnt.Distance(aPntOther);
481           if ((Dst < DstRef - Eps) || (fabs(Dst-DstRef) < Eps))
482           {             
483             if (mDstRef > Dst)
484               mDstRef=Dst;
485             const BRepExtrema_SolutionElem Sol1(Dst,aPnt,BRepExtrema_IsOnEdge,E,aParameter);
486             const BRepExtrema_SolutionElem Sol2(Dst,aPntOther,BRepExtrema_IsOnEdge,Eother,aParameterOther);
487             SeqSol1.Append(iE == 0 ? Sol1 : Sol2);
488             SeqSol2.Append(iE == 0 ? Sol2 : Sol1);
489           }               
490         }
491       }
492     }
493   }
494 }
495
496 /*********************************************************************************/
497
498 void BRepExtrema_DistanceSS::Perform(const TopoDS_Shape& S1, const TopoDS_Shape& S2,
499                                      const Bnd_Box& B1, const Bnd_Box& B2)
500 {
501   SeqSolShape1.Clear();
502   SeqSolShape2.Clear();
503   myModif=Standard_False;
504
505   switch (S1.ShapeType())
506   {
507     case TopAbs_VERTEX :
508     {
509       TopoDS_Vertex V1 = TopoDS::Vertex(S1);
510       switch (S2.ShapeType())
511       {
512         case TopAbs_VERTEX :
513         {
514           TopoDS_Vertex V2 = TopoDS::Vertex(S2);
515           Perform( V1, V2 );
516           break;
517         }
518         case TopAbs_EDGE :
519         {
520           TopoDS_Edge E2 = TopoDS::Edge(S2);
521           Perform( V1, E2, B1, B2 );
522           break;
523         }
524         case TopAbs_FACE :
525         {
526           TopoDS_Face F2 = TopoDS::Face(S2);
527           Perform( V1, F2, B1, B2 );
528           break;
529         }
530       }
531       break;
532     }
533
534     case TopAbs_EDGE :
535     {
536       TopoDS_Edge E1 = TopoDS::Edge(S1);
537       switch (S2.ShapeType())
538       {
539         case TopAbs_VERTEX :
540         {
541           TopoDS_Vertex V2 = TopoDS::Vertex(S2);
542           Perform( E1, V2, B1, B2 );
543           break;
544         }
545         case TopAbs_EDGE :
546         {
547           TopoDS_Edge E2 = TopoDS::Edge(S2);
548           TopoDS_Edge aTrimEdge;
549           Standard_Boolean bIsTrim1 = Standard_False;
550           Standard_Boolean bIsTrim2 = Standard_False;
551           TRIM_INFINIT_EDGE( E1, E2, aTrimEdge, bIsTrim1, bIsTrim2 );
552           if (bIsTrim1)
553             E1 = aTrimEdge;
554           if (bIsTrim2)
555             E2 = aTrimEdge;
556           Perform( E1, E2, B1, B2 );
557           break;
558         }
559         case TopAbs_FACE :
560         {
561           TopoDS_Face F2 = TopoDS::Face(S2);
562           TopoDS_Face aTrimFace;
563           Standard_Boolean bIsInfinit;
564           TRIM_INFINIT_FACE( E1, F2, aTrimFace, bIsInfinit );
565           if (bIsInfinit)
566             F2 = aTrimFace;
567           Perform( E1, F2, B1, B2 );
568           break;
569         }
570       }
571       break;
572     }
573
574     case TopAbs_FACE :
575     {
576       TopoDS_Face F1 = TopoDS::Face(S1);
577       switch (S2.ShapeType())
578       {
579         case TopAbs_VERTEX :
580         {
581           TopoDS_Vertex V2 = TopoDS::Vertex(S2);
582           Perform( F1, V2, B1, B2 );
583           break;
584         }
585         case TopAbs_EDGE :
586         {
587           TopoDS_Edge E2 = TopoDS::Edge(S2);
588           TopoDS_Face aTrimFace;
589           Standard_Boolean bIsInfinit;
590           TRIM_INFINIT_FACE( F1, E2, aTrimFace, bIsInfinit );
591           if (bIsInfinit)
592             F1 = aTrimFace;
593           Perform( F1, E2, B1, B2 );
594           break;
595         }
596         case TopAbs_FACE :
597         {
598           TopoDS_Face F2 = TopoDS::Face(S2);
599           Perform( F1, F2, B1, B2 );
600           break;
601         }
602       }
603       break;
604     }
605   }
606 }
607
608 /*********************************************************************************/
609
610 void BRepExtrema_DistanceSS::Perform(const TopoDS_Vertex& S1, const TopoDS_Vertex& S2)
611 {     
612   const gp_Pnt P1 = BRep_Tool::Pnt(S1);
613   const gp_Pnt P2 = BRep_Tool::Pnt(S2);
614
615   const Standard_Real Dst = P1.Distance(P2);
616   if ((Dst < myDstRef - myEps) || (fabs(Dst-myDstRef) < myEps))
617   { 
618     if (myDstRef > Dst)
619       myDstRef=Dst;
620     myModif=Standard_True;
621     const BRepExtrema_SolutionElem Sol1(Dst,P1,BRepExtrema_IsVertex,S1);
622     const BRepExtrema_SolutionElem Sol2(Dst,P2,BRepExtrema_IsVertex,S2);
623     SeqSolShape1.Append(Sol1);
624     SeqSolShape2.Append(Sol2);
625   }
626 }
627
628 /*********************************************************************************/
629
630 void BRepExtrema_DistanceSS::Perform(const TopoDS_Vertex& S1, const TopoDS_Edge& S2,
631                                      const Bnd_Box& B1, const Bnd_Box& B2)
632
633   if (BRep_Tool::Degenerated(S2))
634     return;
635
636   const Standard_Real Dst=B1.Distance(B2);
637   if ((Dst < myDstRef - myEps) || (fabs(Dst-myDstRef) < myEps))
638   {
639     BRepExtrema_ExtPC Ext(S1,S2);
640     const Standard_Integer NbExtrema = Ext.IsDone()? Ext.NbExt() : 0;
641     if ( NbExtrema > 0 )
642     {
643       // Search minimum distance Dstmin
644       Standard_Integer i;
645       Standard_Real Dstmin = Ext.SquareDistance(1);
646       for (i = 2; i <= NbExtrema; i++)
647       {
648         const Standard_Real sDst = Ext.SquareDistance(i);
649         if (sDst<Dstmin)
650           Dstmin=sDst;
651           }
652       Dstmin = sqrt(Dstmin);
653       if ((Dstmin < myDstRef - myEps) || (fabs(Dstmin-myDstRef) < myEps))
654       {
655         Standard_Real Udeb,Ufin;
656         BRep_Tool::Range(S2,Udeb,Ufin);
657
658         gp_Pnt Pt,P1=BRep_Tool::Pnt(S1);
659         const Standard_Real epsP=Precision::PConfusion();
660
661         for (i = 1; i <= NbExtrema; i++)
662         {
663           if (fabs(Dstmin-sqrt(Ext.SquareDistance(i)))<myEps)
664           {
665             Pt=Ext.Point(i);
666             if (TRI_SOLUTION(SeqSolShape2,Pt))
667             {
668               // Check if the parameter does not correspond to a vertex
669               const Standard_Real t = Ext.Parameter(i);
670               if ( (fabs(t-Udeb)>=epsP) && (fabs(t-Ufin)>epsP) )
671               {
672                 if (myDstRef > Dstmin)
673                   myDstRef=Dstmin;
674                 myModif=Standard_True;
675                 const BRepExtrema_SolutionElem Sol1(Dstmin,P1,BRepExtrema_IsVertex,S1);
676                 const BRepExtrema_SolutionElem Sol2(Dstmin,Pt,BRepExtrema_IsOnEdge,S2,t);
677                 SeqSolShape1.Append(Sol1);
678                 SeqSolShape2.Append(Sol2);
679               }
680             }
681           }
682         }
683       }
684     }
685   }
686 }
687
688 /*********************************************************************************/
689
690 void BRepExtrema_DistanceSS::Perform(const TopoDS_Vertex& S1, const TopoDS_Face& S2, 
691                                      const Bnd_Box& B1, const Bnd_Box& B2)
692 {
693   const Standard_Real Dst=B1.Distance(B2);
694   if ((Dst < myDstRef - myEps) || (fabs(Dst-myDstRef) < myEps))
695   { 
696     BRepExtrema_ExtPF Ext(S1,S2,myFlag,myAlgo);
697     const Standard_Integer NbExtrema = Ext.IsDone()? Ext.NbExt() : 0;
698     if ( NbExtrema > 0 )
699     {
700       // Search minimum distance Dstmin
701       Standard_Integer i;
702       Standard_Real Dstmin = Ext.SquareDistance(1);
703       for (i = 2; i <= NbExtrema; i++)
704       {
705         const Standard_Real sDst = Ext.SquareDistance(i);
706         if (sDst<Dstmin) 
707           Dstmin=sDst;
708       }
709       Dstmin = sqrt(Dstmin);
710       if ((Dstmin < myDstRef - myEps) || (fabs(Dstmin-myDstRef) < myEps))
711       {
712         Standard_Real U,V;
713         gp_Pnt Pt,P1=BRep_Tool::Pnt(S1);
714         BRepClass_FaceClassifier classifier;
715         const Standard_Real tol = BRep_Tool::Tolerance(S2);
716         const Standard_Real epsP = Precision::PConfusion();
717  
718         for (i = 1; i <= NbExtrema; i++)
719         {
720           if (fabs(Dstmin-sqrt(Ext.SquareDistance(i)))<myEps)
721           {
722             Pt=Ext.Point(i);
723             if (TRI_SOLUTION(SeqSolShape2,Pt))
724             {
725               // Check if the parameter does not correspond to a vertex
726               Ext.Parameter(i,U,V);
727               const gp_Pnt2d PUV(U,V);
728               classifier.Perform(S2,PUV,tol);
729               if (classifier.State()==TopAbs_IN)
730               {
731                 if (myDstRef > Dstmin)
732                   myDstRef=Dstmin;
733                 myModif=Standard_True;
734                 const BRepExtrema_SolutionElem Sol1(Dstmin,P1,BRepExtrema_IsVertex,S1);
735                 const BRepExtrema_SolutionElem Sol2(Dstmin,Pt,BRepExtrema_IsInFace,S2,U,V);
736                 SeqSolShape1.Append(Sol1);
737                 SeqSolShape2.Append(Sol2);                
738               }
739             }
740           }
741         }
742       }
743     }
744   }
745 }
746
747 /*********************************************************************************/
748
749 void BRepExtrema_DistanceSS::Perform(const TopoDS_Edge& S1, const TopoDS_Edge& S2,
750                                      const Bnd_Box& B1, const Bnd_Box& B2)
751 {
752   if (BRep_Tool::Degenerated(S1) || BRep_Tool::Degenerated(S2))
753     return;
754
755   const Standard_Real Dst=B1.Distance(B2);
756   if ((Dst < myDstRef - myEps) || (fabs(Dst-myDstRef) < myEps))
757   {
758     const Standard_Real DstRef = myDstRef;
759
760     BRepExtrema_ExtCC Ext(S1,S2);
761         const Standard_Integer NbExtrema = Ext.IsDone()? (Ext.IsParallel()? 0 : Ext.NbExt()) : 0;
762     if ( NbExtrema > 0 )
763     {
764       // Search minimum distance Dstmin
765       Standard_Integer i;
766       Standard_Real Dstmin = Ext.SquareDistance(1);
767       for (i = 2; i <= NbExtrema; i++)
768       {
769         const Standard_Real sDst = Ext.SquareDistance(i);
770         if (sDst<Dstmin) 
771           Dstmin=sDst;
772           }
773       Dstmin = sqrt(Dstmin);
774       if ((Dstmin < myDstRef - myEps) || (fabs(Dstmin-myDstRef) < myEps))
775       {
776         Standard_Real Udeb1,Ufin1,Udeb2,Ufin2;
777         BRep_Tool::Range(S1,Udeb1,Ufin1);
778         BRep_Tool::Range(S2,Udeb2,Ufin2);
779
780         gp_Pnt Pt1,Pt2;
781         const Standard_Real epsP=Precision::PConfusion();
782
783         for (i=1;i<=NbExtrema;i++)
784         {
785           if (fabs(Dstmin-sqrt(Ext.SquareDistance(i)))<myEps)
786           {
787             Pt1=Ext.PointOnE1(i);
788             Pt2=Ext.PointOnE2(i);
789             if (TRI_SOLUTION(SeqSolShape1,Pt1) || TRI_SOLUTION(SeqSolShape2,Pt2))
790             {
791               // Check if the parameters do not correspond to a vertex
792               const Standard_Real t1 = Ext.ParameterOnE1(i);
793               const Standard_Real t2 = Ext.ParameterOnE2(i);
794               if ((fabs(t1-Udeb1)>=epsP)&&(fabs(t1-Ufin1)>epsP)&&(fabs(t2-Udeb2)>=epsP)&&(fabs(t2-Ufin2)>epsP))
795               {
796                 if (myDstRef > Dstmin)
797                   myDstRef=Dstmin;
798                 myModif=Standard_True;
799                 const BRepExtrema_SolutionElem Sol1(Dstmin,Pt1,BRepExtrema_IsOnEdge,S1,t1);
800                 const BRepExtrema_SolutionElem Sol2(Dstmin,Pt2,BRepExtrema_IsOnEdge,S2,t2);
801                 SeqSolShape1.Append(Sol1);
802                 SeqSolShape2.Append(Sol2);
803               }
804             }
805           }
806         }
807       }
808     }
809
810     BRepExtrema_SeqOfSolution SeqSolution1;
811     BRepExtrema_SeqOfSolution SeqSolution2;
812
813     PERFORM_C0(S1, S2, SeqSolution1, SeqSolution2, DstRef, myDstRef, myEps);
814      
815     BRepExtrema_SeqOfSolution seqSol1;
816     BRepExtrema_SeqOfSolution seqSol2;
817         
818     if (SeqSolution1.Length() > 0 && SeqSolution2.Length() > 0)
819       MIN_SOLUTION(SeqSolution1, SeqSolution2, myDstRef, myEps, seqSol1, seqSol2);
820      
821     if (!seqSol1.IsEmpty() && !seqSol2.IsEmpty())
822     {
823       SeqSolShape1.Append(seqSol1);
824       SeqSolShape2.Append(seqSol2);     
825       myModif = Standard_True;
826     }
827   }
828 }
829
830 /*********************************************************************************/
831
832 void BRepExtrema_DistanceSS::Perform(const TopoDS_Edge& S1, const TopoDS_Face& S2,
833                                      const Bnd_Box& B1, const Bnd_Box& B2)
834 {
835   if (BRep_Tool::Degenerated(S1))
836     return;
837     
838   const Standard_Real Dst=B1.Distance(B2);
839   if ((Dst < myDstRef - myEps) || (fabs(Dst-myDstRef) < myEps))
840   {
841     BRepClass_FaceClassifier classifier;
842
843     BRepExtrema_ExtCF Ext(S1,S2);
844         const Standard_Integer NbExtrema = Ext.IsDone()? (Ext.IsParallel()? 0 : Ext.NbExt()) : 0;
845     if ( NbExtrema > 0 )
846     {
847       // Search minimum distance Dstmin
848       Standard_Integer i;
849       Standard_Real Dstmin = Ext.SquareDistance(1);
850       for (i = 2; i <= NbExtrema; i++)
851       {
852         const Standard_Real sDst = Ext.SquareDistance(i);
853         if (sDst<Dstmin) 
854           Dstmin=sDst;
855       }
856       Dstmin = sqrt(Dstmin);
857       if ((Dstmin < myDstRef - myEps) || (fabs(Dstmin-myDstRef) < myEps))
858       {
859         Standard_Real Udeb,Ufin,U,V;
860         BRep_Tool::Range(S1,Udeb,Ufin);
861         const Standard_Real tol=BRep_Tool::Tolerance(S2);
862
863         gp_Pnt Pt1,Pt2;
864         const Standard_Real epsP=Precision::PConfusion();
865
866         for (i = 1; i <= NbExtrema; i++)
867         {
868           if (fabs(Dstmin-sqrt(Ext.SquareDistance(i)))<myEps)
869           {
870             Pt1=Ext.PointOnEdge(i);
871             Pt2=Ext.PointOnFace(i);
872             if (TRI_SOLUTION(SeqSolShape1,Pt1) || TRI_SOLUTION(SeqSolShape2,Pt2))
873             {
874               // Check if the parameter does not correspond to a vertex
875               const Standard_Real t1 = Ext.ParameterOnEdge(i);
876               if ((fabs(t1-Udeb)>=epsP)&&(fabs(t1-Ufin)>epsP))
877               {
878                 Ext.ParameterOnFace(i,U,V);
879                 const gp_Pnt2d PUV(U,V);
880                 classifier.Perform(S2,PUV,tol);
881                 if (classifier.State()==TopAbs_IN)
882                 {
883                   if (myDstRef > Dstmin)
884                     myDstRef=Dstmin;
885                   myModif=Standard_True;
886                   const BRepExtrema_SolutionElem Sol1(Dstmin,Pt1,BRepExtrema_IsOnEdge,S1,t1);
887                   const BRepExtrema_SolutionElem Sol2(Dstmin,Pt2,BRepExtrema_IsInFace,S2,U,V);
888                   SeqSolShape1.Append(Sol1);
889                   SeqSolShape2.Append(Sol2);              
890                 }
891               }
892             }
893           }
894         }
895       }
896     }
897
898     Standard_Real aFirst, aLast;
899     Handle(Geom_Curve) pCurv = BRep_Tool::Curve(S1, aFirst, aLast);
900     if (pCurv->Continuity() == GeomAbs_C0)
901     {
902       BRepExtrema_SeqOfSolution SeqSolution1;
903       BRepExtrema_SeqOfSolution SeqSolution2;
904
905       GeomAdaptor_Curve aAdaptorCurve(pCurv, aFirst, aLast);
906       const Standard_Integer nbIntervals = aAdaptorCurve.NbIntervals(GeomAbs_C1);
907
908       TColStd_Array1OfReal arrInter(1,1+nbIntervals);
909       aAdaptorCurve.Intervals(arrInter, GeomAbs_C1);
910
911       gp_Pnt Pt;
912       Standard_Real U,V;
913       const Standard_Real tol = BRep_Tool::Tolerance(S2);
914
915       Standard_Integer i;
916       for (i = 1; i <= arrInter.Length(); i++)
917       {
918         const Standard_Real aParameter = arrInter(i);
919         gp_Pnt aPnt = aAdaptorCurve.Value(aParameter);
920         TopoDS_Vertex V1 = BRepBuilderAPI_MakeVertex(aPnt);
921
922         BRepExtrema_ExtPF ExtPF(V1,S2);
923         const Standard_Integer NbExtrema = ExtPF.IsDone()? ExtPF.NbExt() : 0;
924         if ( NbExtrema > 0 )
925         {
926           // Search minimum distance Dstmin
927           Standard_Integer ii;
928           Standard_Real Dstmin = ExtPF.SquareDistance(1);
929           for (ii = 2; ii <= NbExtrema; ii++)
930           {
931             const Standard_Real sDst = ExtPF.SquareDistance(ii);
932             if (sDst<Dstmin)
933               Dstmin=sDst;
934           }
935           Dstmin = sqrt(Dstmin);
936
937           if ((Dstmin < myDstRef - myEps) || (fabs(Dstmin-myDstRef) < myEps))
938           {
939             for (ii = 1; ii <= NbExtrema; ii++)
940             { 
941               if (fabs(Dstmin-sqrt(ExtPF.SquareDistance(ii)))<myEps)
942               { 
943                 // Check if the parameter does not correspond to a vertex
944                 ExtPF.Parameter(ii,U,V);
945                 const gp_Pnt2d PUV(U,V);
946                                 classifier.Perform(S2,PUV,tol);
947                 if (classifier.State()==TopAbs_IN)
948                 {
949                   if (myDstRef > Dstmin)
950                     myDstRef=Dstmin;
951                   myModif=Standard_True;
952                   const BRepExtrema_SolutionElem Sol1(Dstmin,aPnt,BRepExtrema_IsOnEdge,S1,aParameter);
953                   const BRepExtrema_SolutionElem Sol2(Dstmin,ExtPF.Point(ii),BRepExtrema_IsInFace,S2,U,V);
954                   SeqSolution1.Append(Sol1);
955                   SeqSolution2.Append(Sol2);
956                 }
957               }
958             }
959           }
960         }
961       }
962
963       BRepExtrema_SeqOfSolution seqSol1;
964       BRepExtrema_SeqOfSolution seqSol2;
965       Standard_Boolean bIsMini = Standard_False;
966       if (SeqSolution1.Length() > 0 && SeqSolution2.Length() > 0)
967         MIN_SOLUTION(SeqSolution1, SeqSolution2, myDstRef, myEps, seqSol1, seqSol2);
968             
969       if (!seqSol1.IsEmpty() && !seqSol2.IsEmpty())
970       {
971         SeqSolShape1.Append(seqSol1);
972         SeqSolShape2.Append(seqSol2);
973       }
974     }
975   }
976 }
977
978 /*********************************************************************************/
979
980 void BRepExtrema_DistanceSS::Perform(const TopoDS_Face& S1, const TopoDS_Face& S2,
981                                      const Bnd_Box& B1, const Bnd_Box& B2)
982 {
983   const Standard_Real Dst=B1.Distance(B2);
984   if ((Dst < myDstRef - myEps) || (fabs(Dst-myDstRef) < myEps))
985   { 
986     BRepExtrema_ExtFF Ext(S1,S2);
987         const Standard_Integer NbExtrema = Ext.IsDone()? (Ext.IsParallel()? 0 : Ext.NbExt()) : 0;
988     if ( NbExtrema > 0 )
989     {
990       // Search minimum distance Dstmin
991       Standard_Integer i;
992       Standard_Real Dstmin = Ext.SquareDistance(1);
993       for (i = 2; i <= NbExtrema; i++)
994       {
995         const Standard_Real sDst = Ext.SquareDistance(i);
996         if (sDst<Dstmin)
997           Dstmin=sDst;
998       }
999       Dstmin = sqrt(Dstmin);
1000       if ((Dstmin < myDstRef - myEps) || (fabs(Dstmin-myDstRef) < myEps))
1001       {
1002         const Standard_Real tol1=BRep_Tool::Tolerance(S1);
1003         const Standard_Real tol2=BRep_Tool::Tolerance(S2);
1004
1005         gp_Pnt Pt1,Pt2;
1006         gp_Pnt2d PUV;
1007         Standard_Real U1,V1,U2,V2;
1008         BRepClass_FaceClassifier classifier;
1009         const Standard_Real epsP=Precision::PConfusion();
1010  
1011         for (i = 1; i <= NbExtrema; i++)
1012         {
1013           if (fabs(Dstmin-sqrt(Ext.SquareDistance(i)))<myEps)
1014           {
1015             Pt1=Ext.PointOnFace1(i);
1016             Pt2=Ext.PointOnFace2(i); 
1017             if (TRI_SOLUTION(SeqSolShape1,Pt1) || TRI_SOLUTION(SeqSolShape2,Pt2))
1018             {
1019               // Check if the parameter does not correspond to a vertex
1020               Ext.ParameterOnFace1(i,U1,V1);
1021               PUV.SetCoord(U1,V1);
1022               classifier.Perform(S1,PUV,tol1);
1023               if (classifier.State()==TopAbs_IN)
1024               {
1025                 Ext.ParameterOnFace2(i,U2,V2);
1026                 PUV.SetCoord(U2,V2);
1027                 classifier.Perform(S2,PUV,tol2);
1028                 if (classifier.State()==TopAbs_IN)
1029                 {
1030                   if (myDstRef > Dstmin)
1031                     myDstRef=Dstmin;
1032                   myModif=Standard_True;
1033                   const BRepExtrema_SolutionElem Sol1(Dstmin,Pt1,BRepExtrema_IsInFace,S1,U1,V1);
1034                   const BRepExtrema_SolutionElem Sol2(Dstmin,Pt2,BRepExtrema_IsInFace,S2,U2,V2);
1035                   SeqSolShape1.Append(Sol1);
1036                   SeqSolShape2.Append(Sol2);
1037                 }
1038               }
1039             }
1040           }
1041         }
1042       }
1043     }
1044   }
1045 }
1046
1047 /*********************************************************************************/