0022610: The algorithm GeomAPI_ProjectPointOnSurf produces wrong results
authorskv <skv@opencascade.com>
Fri, 22 Feb 2013 10:13:06 +0000 (14:13 +0400)
committerskv <skv@opencascade.com>
Fri, 22 Feb 2013 10:13:06 +0000 (14:13 +0400)
src/Extrema/Extrema.cdl
src/Extrema/Extrema_GenExtPS.cdl
src/Extrema/Extrema_GenExtPS.cxx
src/Extrema/Extrema_POnSurfParams.cdl [new file with mode: 0755]
src/Extrema/Extrema_POnSurfParams.cxx [new file with mode: 0755]
src/Extrema/Extrema_POnSurfParams.lxx [new file with mode: 0755]

index e61c29d..395bc7e 100755 (executable)
@@ -53,12 +53,15 @@ is
     enumeration ExtFlag is ExtFlag_MIN, ExtFlag_MAX, ExtFlag_MINMAX;
 
     enumeration ExtAlgo is ExtAlgo_Grad, ExtAlgo_Tree;
+    
+    enumeration ElementType is Node, UIsoEdge, VIsoEdge, Face;
 
     class CurveTool;
     class Curve2dTool;
 
     generic class Point;
     class POnSurf;
+    class POnSurfParams;
 
     generic class ExtPSOfRev;
     
@@ -173,6 +176,9 @@ is
     class Array2OfPOnSurf     instantiates 
        Array2 from TCollection(POnSurf);
        
+    class Array2OfPOnSurfParams instantiates 
+       Array2 from TCollection(POnSurfParams);
+       
 
     class HArray1OfPOnCurv    instantiates 
        HArray1 from TCollection(POnCurv, Array1OfPOnCurv);
@@ -193,6 +199,9 @@ is
     class HArray2OfPOnSurf    instantiates 
        HArray2 from TCollection(POnSurf, Array2OfPOnSurf);
        
+    class HArray2OfPOnSurfParams instantiates 
+       HArray2 from TCollection(POnSurfParams, Array2OfPOnSurfParams);
+       
 
     class SequenceOfPOnCurv   instantiates 
        Sequence from TCollection(POnCurv);
index 30067b8..e5eaf18 100755 (executable)
@@ -36,8 +36,9 @@ uses          POnSurf       from Extrema,
        ExtAlgo from Extrema,
        HArray1OfSphere from Bnd,
        Vector        from math,
-       HArray2OfPnt from TColgp,
-       HArray1OfReal from TColStd
+       HArray1OfReal from TColStd,
+       POnSurfParams from Extrema,
+       HArray2OfPOnSurfParams from Extrema
 
 raises  NotDone      from StdFail,
        OutOfRange   from Standard,
@@ -138,15 +139,15 @@ is
     BuildTree(me : in out)
     is static private;
     
-    FindSolution(me: in out; P : Pnt from gp; UV : Vector from math; theNoU, theNoV : Integer; f : ExtFlag from Extrema)
+    FindSolution(me: in out; P : Pnt from gp;
+         theParams: POnSurfParams from Extrema)
     is static private;
     
     GetGridPoints(me: in out;  theSurf: Surface from Adaptor3d) is private;
        ---Purpose: Selection of points to build grid, depending on the type of surface
     
-    BuildGrid(me: in out) is private;
+    BuildGrid(me: in out; thePoint: Pnt from gp) is private;
        ---Purpose: Creation of grid of parametric points
-  
 
 fields
     myDone    : Boolean;
@@ -159,7 +160,7 @@ fields
     myvsample : Integer;
     mytolu    : Real;
     mytolv    : Real;
-    mypoints  : HArray2OfPnt from TColgp;
+    myPoints  : HArray2OfPOnSurfParams from Extrema;
     mySphereUBTree : HUBTreeOfSphere from Extrema;
     mySphereArray : HArray1OfSphere from Bnd;
     myF              : FuncExtPS from Extrema;
@@ -168,5 +169,6 @@ fields
     myAlgo    : ExtAlgo from Extrema;
     myUParams : HArray1OfReal from TColStd;
     myVParams : HArray1OfReal from TColStd;
+    myFacePntParams : HArray2OfPOnSurfParams from Extrema;
 
 end GenExtPS;
index 89013df..98a4fc4 100755 (executable)
@@ -172,7 +172,69 @@ Standard_Boolean Bnd_SphereUBTreeSelectorMax::Accept(const Standard_Integer& the
   return Standard_False;
 }
 
+/*
+ * This function computes the point on surface parameters on edge.
+ * if it coincides with theParam0 or theParam1, it is returned.
+ */
+static Extrema_POnSurfParams ComputeEdgeParameters
+      (const Standard_Boolean       IsUEdge,
+       const Extrema_POnSurfParams &theParam0,
+       const Extrema_POnSurfParams &theParam1,
+       const Adaptor3d_SurfacePtr  &theSurf,
+       const gp_Pnt                &thePoint,
+       const Standard_Real          theDiffTol)
+{
+  const Standard_Real aSqrDist01 =
+    theParam0.Value().SquareDistance(theParam1.Value());
+
+  if (aSqrDist01 <= theDiffTol) {
+    // The points are confused. Get the first point and change its type.
+    return theParam0;
+  } else {
+    const Standard_Real aDiffDist =
+      Abs(theParam0.GetSqrDistance() - theParam1.GetSqrDistance());
+
+    if (aDiffDist >= aSqrDist01 - theDiffTol) {
+      // The shortest distance is one of the nodes.
+      if (theParam0.GetSqrDistance() > theParam1.GetSqrDistance()) {
+        // The shortest distance is the point 1.
+        return theParam1;
+      } else {
+        // The shortest distance is the point 0.
+        return theParam0;
+      }
+    } else {
+      // The shortest distance is inside the edge.
+      gp_XYZ aPoP(thePoint.XYZ().Subtracted(theParam0.Value().XYZ()));
+      gp_XYZ aPoP1(theParam1.Value().XYZ().Subtracted(theParam0.Value().XYZ()));
+      Standard_Real aRatio = aPoP.Dot(aPoP1)/aSqrDist01;
+      Standard_Real aU[2];
+      Standard_Real aV[2];
+
+      theParam0.Parameter(aU[0], aV[0]);
+      theParam1.Parameter(aU[1], aV[1]);
+  
+      Standard_Real aUPar = aU[0];
+      Standard_Real aVPar = aV[0];
+
+      if (IsUEdge) {
+        aUPar += aRatio*(aU[1] - aU[0]);
+      } else {
+        aVPar += aRatio*(aV[1] - aV[0]);
+      }
+
+      Extrema_POnSurfParams aParam(aUPar, aVPar, theSurf->Value(aUPar, aVPar));
+      Standard_Integer anIndices[2];
 
+      theParam0.GetIndices(anIndices[0], anIndices[1]);
+      aParam.SetElementType(IsUEdge ? Extrema_UIsoEdge : Extrema_VIsoEdge);
+      aParam.SetSqrDistance(thePoint.SquareDistance(aParam.Value()));
+      aParam.SetIndices(anIndices[0], anIndices[1]);
+
+      return aParam;
+    }
+  }
+}
 
 //=============================================================================
 
@@ -474,64 +536,209 @@ void Extrema_GenExtPS::GetGridPoints( const Adaptor3d_Surface& theSurf)
   
 }
 
-void Extrema_GenExtPS::BuildGrid()
+void Extrema_GenExtPS::BuildGrid(const gp_Pnt &thePoint)
 {
-  //if grid was already built do nothing
-  if(myInit)
-    return;
+  Standard_Integer NoU, NoV;
+
+  //if grid was already built skip its creation
+  if (!myInit) {
+    //build parametric grid in case of a complex surface geometry (BSpline and Bezier surfaces)
+    GetGridPoints(*myS);
+    
+    //build grid in other cases 
+    if( myUParams.IsNull() )
+    {
+      Standard_Real PasU = myusup - myumin;
+      Standard_Real U0 = PasU / myusample / 100.;
+      PasU = (PasU - U0) / (myusample - 1);
+      U0 = U0/2. + myumin;
+      myUParams = new TColStd_HArray1OfReal(1,myusample );
+      Standard_Integer NoU;
+      Standard_Real U = U0;
+      for ( NoU = 1 ; NoU <= myusample; NoU++, U += PasU) 
+        myUParams->SetValue(NoU, U);
+    }
   
-  //build parametric grid in case of a complex surface geometry (BSpline and Bezier surfaces)
- GetGridPoints(*myS);
+    if( myVParams.IsNull())
+    {
+      Standard_Real PasV = myvsup - myvmin;
+      Standard_Real V0 = PasV / myvsample / 100.;
+      PasV = (PasV - V0) / (myvsample - 1);
+      V0 = V0/2. + myvmin;
+      
+      myVParams = new TColStd_HArray1OfReal(1,myvsample );
+      Standard_Integer  NoV;
+      Standard_Real V = V0;
+     
+      for ( NoV = 1, V = V0; NoV <= myvsample; NoV++, V += PasV)
+        myVParams->SetValue(NoV, V);
+    }
+
+    //If flag was changed and extrema not reinitialized Extrema would fail
+    myPoints = new Extrema_HArray2OfPOnSurfParams
+      (0, myusample + 1, 0, myvsample + 1);
+    // Calculation of distances
   
-  //build grid in other cases 
-  if( myUParams.IsNull() )
-  {
-    Standard_Real PasU = myusup - myumin;
-    Standard_Real U0 = PasU / myusample / 100.;
-    PasU = (PasU - U0) / (myusample - 1);
-    U0 = U0/2. + myumin;
-    myUParams = new TColStd_HArray1OfReal(1,myusample );
-    Standard_Integer NoU;
-    Standard_Real U = U0;
-    for ( NoU = 1 ; NoU <= myusample; NoU++, U += PasU) 
-      myUParams->SetValue(NoU, U);
+    for ( NoU = 1 ; NoU <= myusample; NoU++ ) {
+      for ( NoV = 1 ; NoV <= myvsample; NoV++) {
+        gp_Pnt aP1 = myS->Value(myUParams->Value(NoU), myVParams->Value(NoV));
+        Extrema_POnSurfParams aParam
+          (myUParams->Value(NoU), myVParams->Value(NoV), aP1);
+
+        aParam.SetElementType(Extrema_Node);
+        aParam.SetIndices(NoU, NoV);
+        myPoints->SetValue(NoU, NoV, aParam);
+      }
+    }
 
-  }
+    // Fill boundary with negative square distance.
+    // It is used for computation of Maximum.
+    for (NoV = 0; NoV <= myvsample + 1; NoV++) {
+      myPoints->ChangeValue(0, NoV).SetSqrDistance(-1.);
+      myPoints->ChangeValue(myusample + 1, NoV).SetSqrDistance(-1.);
+    }
 
-  if( myVParams.IsNull())
-  {
-    Standard_Real PasV = myvsup - myvmin;
-    Standard_Real V0 = PasV / myvsample / 100.;
-    PasV = (PasV - V0) / (myvsample - 1);
-    V0 = V0/2. + myvmin;
+    for (NoU = 1; NoU <= myusample; NoU++) {
+      myPoints->ChangeValue(NoU, 0).SetSqrDistance(-1.);
+      myPoints->ChangeValue(NoU, myvsample + 1).SetSqrDistance(-1.);
+    }
     
-    myVParams = new TColStd_HArray1OfReal(1,myvsample );
-    Standard_Integer  NoV;
-    Standard_Real V = V0;
-   
-    for ( NoV = 1, V = V0; NoV <= myvsample; NoV++, V += PasV)
-      myVParams->SetValue(NoV, V);
+    myInit = Standard_True;
   }
-  //If flag was changed and extrema not reinitialized Extrema would fail
-  mypoints = new TColgp_HArray2OfPnt(0,myusample+1,0,myvsample+1);
-  // Calculation of distances
 
-  Standard_Integer NoU, NoV;
+  // Compute distances to mesh.
+  // Step 1. Compute distances to nodes.
   for ( NoU = 1 ; NoU <= myusample; NoU++ ) {
     for ( NoV = 1 ; NoV <= myvsample; NoV++) {
-      gp_Pnt P1 = myS->Value(myUParams->Value(NoU), myVParams->Value(NoV));
-      mypoints->SetValue(NoU,NoV,P1);
+      Extrema_POnSurfParams &aParam = myPoints->ChangeValue(NoU, NoV);
+
+      aParam.SetSqrDistance(thePoint.SquareDistance(aParam.Value()));
     }
   }
-  
-  myInit = Standard_True;
-}
 
+  // For search of minimum compute distances to mesh.
+  if(myFlag == Extrema_ExtFlag_MIN || myFlag == Extrema_ExtFlag_MINMAX) 
+  {
+    // This is the tolerance of difference of squared values.
+    // No need to set it too small.
+    const Standard_Real aDiffTol = mytolu + mytolv;
+
+    // Step 2. Compute distances to edges.
+    // Assume UEdge(i, j) = { Point(i, j); Point(i + 1, j    ) }
+    // Assume VEdge(i, j) = { Point(i, j); Point(i,     j + 1) }
+    Handle(Extrema_HArray2OfPOnSurfParams) aUEdgePntParams =
+          new Extrema_HArray2OfPOnSurfParams(1, myusample - 1, 1, myvsample);
+    Handle(Extrema_HArray2OfPOnSurfParams) aVEdgePntParams =
+          new Extrema_HArray2OfPOnSurfParams(1, myusample, 1, myvsample - 1);
+
+    for ( NoU = 1 ; NoU <= myusample; NoU++ ) {
+      for ( NoV = 1 ; NoV <= myvsample; NoV++) {
+        const Extrema_POnSurfParams &aParam0 = myPoints->Value(NoU, NoV);
+
+        if (NoU < myusample) {
+          // Compute parameters to UEdge.
+          const Extrema_POnSurfParams &aParam1 = myPoints->Value(NoU + 1, NoV);
+          Extrema_POnSurfParams aUEdgeParam = ComputeEdgeParameters
+              (Standard_True, aParam0, aParam1, myS, thePoint, aDiffTol);
+
+          aUEdgePntParams->SetValue(NoU, NoV, aUEdgeParam);
+        }
 
+        if (NoV < myvsample) {
+          // Compute parameters to VEdge.
+          const Extrema_POnSurfParams &aParam1 = myPoints->Value(NoU, NoV + 1);
+          Extrema_POnSurfParams aVEdgeParam = ComputeEdgeParameters
+              (Standard_False, aParam0, aParam1, myS, thePoint, aDiffTol);
 
+          aVEdgePntParams->SetValue(NoU, NoV, aVEdgeParam);
+        }
+      }
+    }
+
+    // Step 3. Compute distances to faces.
+    // Assume myFacePntParams(i, j) =
+    // { Point(i, j); Point(i + 1, j); Point(i + 1, j + 1); Point(i, j + 1) }
+    //   Or
+    // { UEdge(i, j); VEdge(i + 1, j); UEdge(i, j + 1); VEdge(i, j) }
+    myFacePntParams = 
+          new Extrema_HArray2OfPOnSurfParams(0, myusample, 0, myvsample);
+    Standard_Real aSqrDist01;
+    Standard_Real aDiffDist;
+    Standard_Boolean isOut;
+
+    for ( NoU = 1 ; NoU < myusample; NoU++ ) {
+      for ( NoV = 1 ; NoV < myvsample; NoV++) {
+        const Extrema_POnSurfParams &aUE0 = aUEdgePntParams->Value(NoU, NoV);
+        const Extrema_POnSurfParams &aUE1 = aUEdgePntParams->Value(NoU, NoV+1);
+        const Extrema_POnSurfParams &aVE0 = aVEdgePntParams->Value(NoU, NoV);
+        const Extrema_POnSurfParams &aVE1 = aVEdgePntParams->Value(NoU+1, NoV);
+
+        aSqrDist01 = aUE0.Value().SquareDistance(aUE1.Value());
+        aDiffDist = Abs(aUE0.GetSqrDistance() - aUE1.GetSqrDistance());
+        isOut = Standard_False;
+
+        if (aDiffDist >= aSqrDist01 - aDiffTol) {
+          // The projection is outside the face.
+          isOut = Standard_True;
+        } else {
+          aSqrDist01 = aVE0.Value().SquareDistance(aVE1.Value());
+          aDiffDist = Abs(aVE0.GetSqrDistance() - aVE1.GetSqrDistance());
+
+          if (aDiffDist >= aSqrDist01 - aDiffTol) {
+            // The projection is outside the face.
+            isOut = Standard_True;
+          }
+        }
+
+        if (isOut) {
+          // Get the closest point on an edge.
+          const Extrema_POnSurfParams &aUEMin =
+            aUE0.GetSqrDistance() < aUE1.GetSqrDistance() ? aUE0 : aUE1;
+          const Extrema_POnSurfParams &aVEMin =
+            aVE0.GetSqrDistance() < aVE1.GetSqrDistance() ? aVE0 : aVE1;
+          const Extrema_POnSurfParams &aEMin =
+            aUEMin.GetSqrDistance() < aVEMin.GetSqrDistance() ? aUEMin : aVEMin;
+
+          myFacePntParams->SetValue(NoU, NoV, aEMin);
+        } else {
+          // Find closest point inside the face.
+          Standard_Real aU[2];
+          Standard_Real aV[2];
+          Standard_Real aUPar;
+          Standard_Real aVPar;
+
+          // Compute U parameter.
+          aUE0.Parameter(aU[0], aV[0]);
+          aUE1.Parameter(aU[1], aV[1]);
+          aUPar = 0.5*(aU[0] + aU[1]);
+          // Compute V parameter.
+          aVE0.Parameter(aU[0], aV[0]);
+          aVE1.Parameter(aU[1], aV[1]);
+          aVPar = 0.5*(aV[0] + aV[1]);
+
+          Extrema_POnSurfParams aParam(aUPar, aVPar, myS->Value(aUPar, aVPar));
+
+          aParam.SetElementType(Extrema_Face);
+          aParam.SetSqrDistance(thePoint.SquareDistance(aParam.Value()));
+          aParam.SetIndices(NoU, NoV);
+          myFacePntParams->SetValue(NoU, NoV, aParam);
+        }
+      }
+    }
+
+    // Fill boundary with RealLast square distance.
+    for (NoV = 0; NoV <= myvsample; NoV++) {
+      myFacePntParams->ChangeValue(0, NoV).SetSqrDistance(RealLast());
+      myFacePntParams->ChangeValue(myusample, NoV).SetSqrDistance(RealLast());
+    }
+
+    for (NoU = 1; NoU < myusample; NoU++) {
+      myFacePntParams->ChangeValue(NoU, 0).SetSqrDistance(RealLast());
+      myFacePntParams->ChangeValue(NoU, myvsample).SetSqrDistance(RealLast());
+    }
+  }
+}
 
-  
 /*
 a- Constitution of the table of distances (TbDist(0,myusample+1,0,myvsample+1)):
    ---------------------------------------------------------------
@@ -585,14 +792,16 @@ void Extrema_GenExtPS::BuildTree()
 }
 
 void Extrema_GenExtPS::FindSolution(const gp_Pnt& P, 
-                                    const math_Vector& UV, 
-                                    const Standard_Integer theNoU, 
-                                    const Standard_Integer theNoV, const Extrema_ExtFlag f)
+                                    const Extrema_POnSurfParams &theParams)
 {
   math_Vector Tol(1,2);
   Tol(1) = mytolu;
   Tol(2) = mytolv;
 
+  math_Vector UV(1, 2);
+
+  theParams.Parameter(UV(1), UV(2));
+
   math_Vector UVinf(1,2), UVsup(1,2);
   UVinf(1) = myumin;
   UVinf(2) = myvmin;
@@ -606,89 +815,11 @@ void Extrema_GenExtPS::FindSolution(const gp_Pnt& P,
 
   Standard_Integer aNbMaxIter = 100;
 
-  gp_Pnt PStart = myS->Value(UV(1), UV(2));
-  Standard_Real DistStart = P.SquareDistance(PStart);
+  gp_Pnt PStart = theParams.Value();
+  Standard_Real DistStart = theParams.GetSqrDistance();
   Standard_Real DistSol = DistStart;
   
   math_FunctionSetRoot S (myF,UV,Tol,UVinf,UVsup, aNbMaxIter);
-  Standard_Boolean ToResolveOnSubgrid = Standard_False;
-  Standard_Boolean NewSolution = Standard_False;
-  if (f == Extrema_ExtFlag_MIN)
-  {
-    if(S.IsDone())
-    {
-      root = S.Root();
-      myF.Value(root, errors);
-      gp_Pnt PSol = myS->Value(root(1), root(2));
-      DistSol = P.SquareDistance(PSol);
-      if(Abs(errors(1)) > eps || Abs(errors(2)) > eps || DistStart < DistSol)
-      {
-        //try to improve solution on subgrid of sample points
-        ToResolveOnSubgrid = Standard_True;
-      }
-    }
-    else
-    {
-      //keep found roots and try to find solution
-      Standard_Integer nbExt = myF.NbExt();
-      Standard_Integer k = 1;
-      for( ; k <= nbExt; k++)
-      {
-        Standard_Real aD = myF.SquareDistance(k);
-        if(aD < DistSol)
-        {
-          DistSol = aD;
-          myF.Point(k).Parameter(UV(1),UV(2));
-          NewSolution = Standard_True;
-        }
-      }
-      ToResolveOnSubgrid = Standard_True;
-    }
-    
-    if (ToResolveOnSubgrid)
-    {
-      //extension of interval to find new solution
-      Standard_Real u1 = theNoU == 1 ? myumin : myUParams->Value(theNoU-1), 
-        u2 = theNoU == myusample ? myusup : myUParams->Value(theNoU + 1);
-      Standard_Real v1 = theNoV == 1 ? myvmin : myVParams->Value(theNoV-1),
-        v2 = theNoV == myvsample ? myvsup : myVParams->Value(theNoV + 1);
-            
-      Standard_Real du = (u2 - u1)/(nbsubsample-1);
-      Standard_Real dv = (v2 - v1)/(nbsubsample-1);
-      Standard_Real u, v;
-      Standard_Real dist;
-      
-      //try to find solution on subgrid
-      Standard_Integer Nu, Nv;
-      Standard_Integer minU = 0;
-      Standard_Integer minV = 0;
-      for (Nu = 1, u = u1; Nu < nbsubsample; Nu++, u += du) {
-        for (Nv = 1, v = v1; Nv < nbsubsample; Nv++, v += dv) {
-          gp_Pnt Puv = myS->Value(u, v);
-          dist = P.SquareDistance(Puv);
-          
-          if(dist < DistSol) {
-            UV(1) = u;
-            UV(2) = v;
-            NewSolution = Standard_True;
-            DistSol = dist;
-            minU = Nu;
-            minV = Nv;
-          }
-        }
-      }
-      
-      if(NewSolution) {
-        //try to precise
-        UVinf(1) = u1 + (minU == 1 ? 0 : minU - 2) * du;
-        UVinf(2) = v1 + (minV == 1 ? 0 : minV - 2) * dv;
-        UVsup(1) = u1 + (minU == nbsubsample ? nbsubsample : minU +1) * du;;
-        UVsup(2) = v1 + (minV == nbsubsample ? nbsubsample : minV +1) * dv;
-        math_FunctionSetRoot S (myF,UV,Tol,UVinf,UVsup, aNbMaxIter);
-
-      }
-    } //end of if (ToResolveOnSubgrid)
-  } //end of if (f == Extrema_ExtFlag_MIN)
   
   myDone = Standard_True;
 }
@@ -711,84 +842,114 @@ void Extrema_GenExtPS::Perform(const gp_Pnt& P)
   myDone = Standard_False;
   myF.SetPoint(P);
   
-  math_Vector UV(1,2);
-
   if(myAlgo == Extrema_ExtAlgo_Grad)
   {
-    BuildGrid();
+    BuildGrid(P);
     Standard_Integer NoU,NoV;
 
-    TColStd_Array2OfReal TheDist(0, myusample+1, 0, myvsample+1);
-    
-    for ( NoU = 1 ; NoU <= myusample; NoU++) {
-      for ( NoV = 1; NoV <= myvsample; NoV++) {
-        TheDist(NoU, NoV) = P.SquareDistance(mypoints->Value(NoU, NoV));
-      }
-    }
-
-   
-
-    Standard_Real Dist;
-
     if(myFlag == Extrema_ExtFlag_MIN || myFlag == Extrema_ExtFlag_MINMAX) 
     {
-      for (NoV = 0; NoV <= myvsample+1; NoV++) {
-        TheDist(0,NoV) = RealLast();
-        TheDist(myusample+1,NoV) = RealLast();
-      }
-      for (NoU = 1; NoU <= myusample; NoU++) {
-        TheDist(NoU,0) = RealLast();
-        TheDist(NoU,myvsample+1) = RealLast();
-      }
-      for (NoU = 1; NoU <= myusample; NoU++) {
-        for (NoV = 1; NoV <= myvsample; NoV++) {
-            Dist = TheDist(NoU,NoV);
-            if ((TheDist(NoU-1,NoV-1) >= Dist) &&
-              (TheDist(NoU-1,NoV  ) >= Dist) &&
-              (TheDist(NoU-1,NoV+1) >= Dist) &&
-              (TheDist(NoU  ,NoV-1) >= Dist) &&
-              (TheDist(NoU  ,NoV+1) >= Dist) &&
-              (TheDist(NoU+1,NoV-1) >= Dist) &&
-              (TheDist(NoU+1,NoV  ) >= Dist) &&
-              (TheDist(NoU+1,NoV+1) >= Dist)) {
-                //Create array of UV vectors to calculate min
-                
-                UV(1) = myUParams->Value(NoU);
-                UV(2) = myVParams->Value(NoV);
-                FindSolution(P, UV, NoU, NoV, Extrema_ExtFlag_MIN);
+      Extrema_ElementType anElemType;
+      Standard_Integer iU;
+      Standard_Integer iV;
+      Standard_Integer iU2;
+      Standard_Integer iV2;
+      Standard_Boolean isMin;
+      Standard_Integer i;
+
+      for (NoU = 1; NoU < myusample; NoU++) {
+        for (NoV = 1; NoV < myvsample; NoV++) {
+          const Extrema_POnSurfParams &aParam =
+            myFacePntParams->Value(NoU, NoV);
+
+          isMin = Standard_False;
+          anElemType = aParam.GetElementType();
+
+          if (anElemType == Extrema_Face) {
+            isMin = Standard_True;
+          } else {
+            // Check if it is a boundary edge or corner vertex.
+            aParam.GetIndices(iU, iV);
+
+            if (anElemType == Extrema_UIsoEdge) {
+              isMin = (iV == 1 || iV == myvsample);
+            } else if (anElemType == Extrema_VIsoEdge) {
+              isMin = (iU == 1 || iU == myusample);
+            } else if (anElemType == Extrema_Node) {
+              isMin = (iU == 1 || iU == myusample) &&
+                      (iV == 1 || iV == myvsample);
+            }
+
+            if (!isMin) {
+              // This is a middle element.
+              if (anElemType == Extrema_UIsoEdge ||
+                (anElemType == Extrema_Node && (iU == 1 || iU == myusample))) {
+                // Check the down face.
+                const Extrema_POnSurfParams &aDownParam =
+                    myFacePntParams->Value(NoU, NoV - 1);
+
+                if (aDownParam.GetElementType() == anElemType) {
+                  aDownParam.GetIndices(iU2, iV2);
+                  isMin = (iU == iU2 && iV == iV2);
+                }
+              } else if (anElemType == Extrema_VIsoEdge ||
+                (anElemType == Extrema_Node && (iV == 1 || iV == myvsample))) {
+                // Check the right face.
+                const Extrema_POnSurfParams &aRightParam =
+                    myFacePntParams->Value(NoU - 1, NoV);
+
+                if (aRightParam.GetElementType() == anElemType) {
+                  aRightParam.GetIndices(iU2, iV2);
+                  isMin = (iU == iU2 && iV == iV2);
+                }
+              } else if (iU == NoU && iV == NoV) {
+                // Check the lower-left node. For this purpose it is necessary
+                // to check lower-left, lower and left faces.
+                isMin = Standard_True;
+
+                const Extrema_POnSurfParams *anOtherParam[3] =
+                { &myFacePntParams->Value(NoU, NoV - 1),     // Down
+                  &myFacePntParams->Value(NoU - 1, NoV - 1), // Lower-left
+                  &myFacePntParams->Value(NoU - 1, NoV) };   // Left
+
+                for (i = 0; i < 3 && isMin; i++) {
+                  if (anOtherParam[i]->GetElementType() == Extrema_Node) {
+                    anOtherParam[i]->GetIndices(iU2, iV2);
+                    isMin = (iU == iU2 && iV == iV2);
+                  } else {
+                    isMin = Standard_False;
+                  }
+                }
+              }
             }
-         
+          }
+
+          if (isMin) {
+            FindSolution(P, aParam);
+          }
         }
       }
     }
     
     if(myFlag == Extrema_ExtFlag_MAX || myFlag == Extrema_ExtFlag_MINMAX)
     {
-      for (NoV = 0; NoV <= myvsample+1; NoV++) {
-        TheDist(0,NoV) = RealFirst();
-        TheDist(myusample+1,NoV) = RealFirst();
-      }
-      for (NoU = 1; NoU <= myusample; NoU++) {
-        TheDist(NoU,0) = RealFirst();
-        TheDist(NoU,myvsample+1) = RealFirst();
-      }
+      Standard_Real Dist;
+
       for (NoU = 1; NoU <= myusample; NoU++) {
         for (NoV = 1; NoV <= myvsample; NoV++) {
-            Dist = TheDist(NoU,NoV);
-            if ((TheDist(NoU-1,NoV-1) <= Dist) &&
-              (TheDist(NoU-1,NoV  ) <= Dist) &&
-              (TheDist(NoU-1,NoV+1) <= Dist) &&
-              (TheDist(NoU  ,NoV-1) <= Dist) &&
-              (TheDist(NoU  ,NoV+1) <= Dist) &&
-              (TheDist(NoU+1,NoV-1) <= Dist) &&
-              (TheDist(NoU+1,NoV  ) <= Dist) &&
-              (TheDist(NoU+1,NoV+1) <= Dist)) {
-                //Create array of UV vectors to calculate max
-                UV(1) = myUParams->Value(NoU);
-                UV(2) = myVParams->Value(NoV);
-                FindSolution(P, UV, NoU, NoV, Extrema_ExtFlag_MAX);
-            }
-         }
+          Dist = myPoints->Value(NoU, NoV).GetSqrDistance();
+          if ((myPoints->Value(NoU-1,NoV-1).GetSqrDistance() <= Dist) &&
+              (myPoints->Value(NoU-1,NoV  ).GetSqrDistance() <= Dist) &&
+              (myPoints->Value(NoU-1,NoV+1).GetSqrDistance() <= Dist) &&
+              (myPoints->Value(NoU  ,NoV-1).GetSqrDistance() <= Dist) &&
+              (myPoints->Value(NoU  ,NoV+1).GetSqrDistance() <= Dist) &&
+              (myPoints->Value(NoU+1,NoV-1).GetSqrDistance() <= Dist) &&
+              (myPoints->Value(NoU+1,NoV  ).GetSqrDistance() <= Dist) &&
+              (myPoints->Value(NoU+1,NoV+1).GetSqrDistance() <= Dist)) {
+            // Find maximum.
+            FindSolution(P, myPoints->Value(NoU, NoV));
+          }
+        }
       }
     }
   }
@@ -804,12 +965,13 @@ void Extrema_GenExtPS::Perform(const gp_Pnt& P)
       Standard_Integer aNbSel = mySphereUBTree->Select( aSelector );
       //TODO: check if no solution in binary tree
       Bnd_Sphere& aSph = aSelector.Sphere();
+      Standard_Real aU = myUParams->Value(aSph.U());
+      Standard_Real aV = myVParams->Value(aSph.V());
+      Extrema_POnSurfParams aParams(aU, aV, myS->Value(aU, aV));
 
-      UV(1) = myUParams->Value(aSph.U());//U0 + (aSph.U() - 1) * PasU;
-      UV(2) = myVParams->Value(aSph.V());//V0 + (aSph.V() - 1) * PasV;
-
-      //FindSolution(P, UV, PasU, PasV, Extrema_ExtFlag_MIN);
-      FindSolution(P, UV, aSph.U(), aSph.V(), Extrema_ExtFlag_MIN);
+      aParams.SetSqrDistance(P.SquareDistance(aParams.Value()));
+      aParams.SetIndices(aSph.U(), aSph.V());
+      FindSolution(P, aParams);
     }
     if(myFlag == Extrema_ExtFlag_MAX || myFlag == Extrema_ExtFlag_MINMAX)
     {
@@ -820,12 +982,14 @@ void Extrema_GenExtPS::Perform(const gp_Pnt& P)
       Standard_Integer aNbSel = mySphereUBTree->Select( aSelector );
       //TODO: check if no solution in binary tree
       Bnd_Sphere& aSph = aSelector.Sphere();
-      UV(1) = myUParams->Value(aSph.U());
-      UV(2) = myVParams->Value(aSph.V());
-      //UV(1) = U0 + (aSph.U() - 1) * PasU;
-      //UV(2) = V0 + (aSph.V() - 1) * PasV;
+      Standard_Real aU = myUParams->Value(aSph.U());
+      Standard_Real aV = myVParams->Value(aSph.V());
+      Extrema_POnSurfParams aParams(aU, aV, myS->Value(aU, aV));
+
+      aParams.SetSqrDistance(P.SquareDistance(aParams.Value()));
+      aParams.SetIndices(aSph.U(), aSph.V());
 
-      FindSolution(P, UV, aSph.U(),aSph.V(), Extrema_ExtFlag_MAX);
+      FindSolution(P, aParams);
     }
   }
 }
diff --git a/src/Extrema/Extrema_POnSurfParams.cdl b/src/Extrema/Extrema_POnSurfParams.cdl
new file mode 100755 (executable)
index 0000000..b1bb820
--- /dev/null
@@ -0,0 +1,81 @@
+-- Created on: 2012-12-06
+-- Created by: Sergey KHROMOV
+-- Copyright (c) 2004-2012 OPEN CASCADE SAS
+--
+-- The content of this file is subject to the Open CASCADE Technology Public
+-- License Version 6.5 (the "License"). You may not use the content of this file
+-- except in compliance with the License. Please obtain a copy of the License
+-- at http://www.opencascade.org and read it completely before using this file.
+--
+-- The Initial Developer of the Original Code is Open CASCADE S.A.S., having its
+-- main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France.
+--
+-- The Original Code and all software distributed under the License is
+-- distributed on an "AS IS" basis, without warranty of any kind, and the
+-- Initial Developer hereby disclaims all such warranties, including without
+-- limitation, any warranties of merchantability, fitness for a particular
+-- purpose or non-infringement. Please see the License for the specific terms
+-- and conditions governing the rights and limitations under the License.
+
+
+class POnSurfParams from Extrema inherits POnSurf from Extrema
+    ---Purpose: Data container for point on surface parameters. These parameters
+    --          are required to compute an initial approximation for extrema
+    --          computation.
+    
+uses
+    
+    POnSurf     from Extrema,
+    ElementType from Extrema,
+    Pnt         from gp
+    
+is
+    Create returns POnSurfParams;
+           ---Purpose: empty constructor
+       ---C++: inline
+
+    Create (theU, theV: Real from Standard; thePnt: Pnt from gp)
+       ---Purpose: Creation of a point on surface with parameter 
+       --          values on the surface and a Pnt from gp.
+       ---C++: inline
+    returns POnSurfParams;
+
+    SetSqrDistance(me: in out; theSqrDistance: Real from Standard);
+           ---Purpose: Sets the square distance from this point to another one
+           --          (e.g. to the point to be projected).
+       ---C++: inline
+
+    GetSqrDistance(me)
+           ---Purpose: Query the square distance from this point to another one.
+       ---C++: inline
+    returns Real from Standard;
+
+    SetElementType(me: in out; theElementType: ElementType from Extrema);
+           ---Purpose: Sets the element type on which this point is situated.
+       ---C++: inline
+
+    GetElementType(me)
+           ---Purpose: Query the element type on which this point is situated.
+       ---C++: inline
+    returns ElementType from Extrema;
+    
+    SetIndices(me: in out; theIndexU: Integer from Standard;
+                           theIndexV: Integer from Standard);
+           ---Purpose: Sets the U and V indices of an element that contains
+           --          this point.
+       ---C++: inline
+
+    GetIndices(me; theIndexU: out Integer from Standard;
+                   theIndexV: out Integer from Standard);
+           ---Purpose: Query the U and V indices of an element that contains
+           --          this point.
+       ---C++: inline
+
+fields
+
+    mySqrDistance : Real        from Standard;
+    myElementType : ElementType from Extrema;
+    myIndexU      : Integer     from Standard;
+    myIndexV      : Integer     from Standard;
+    
+end POnSurfParams;
diff --git a/src/Extrema/Extrema_POnSurfParams.cxx b/src/Extrema/Extrema_POnSurfParams.cxx
new file mode 100755 (executable)
index 0000000..c0f6a8f
--- /dev/null
@@ -0,0 +1,19 @@
+// Copyright (c) 1999-2012 OPEN CASCADE SAS
+//
+// The content of this file is subject to the Open CASCADE Technology Public
+// License Version 6.5 (the "License"). You may not use the content of this file
+// except in compliance with the License. Please obtain a copy of the License
+// at http://www.opencascade.org and read it completely before using this file.
+//
+// The Initial Developer of the Original Code is Open CASCADE S.A.S., having its
+// main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France.
+//
+// The Original Code and all software distributed under the License is
+// distributed on an "AS IS" basis, without warranty of any kind, and the
+// Initial Developer hereby disclaims all such warranties, including without
+// limitation, any warranties of merchantability, fitness for a particular
+// purpose or non-infringement. Please see the License for the specific terms
+// and conditions governing the rights and limitations under the License.
+
+
+#include <Extrema_POnSurfParams.ixx>
diff --git a/src/Extrema/Extrema_POnSurfParams.lxx b/src/Extrema/Extrema_POnSurfParams.lxx
new file mode 100755 (executable)
index 0000000..58f3b2a
--- /dev/null
@@ -0,0 +1,73 @@
+// Copyright (c) 1999-2012 OPEN CASCADE SAS
+//
+// The content of this file is subject to the Open CASCADE Technology Public
+// License Version 6.5 (the "License"). You may not use the content of this file
+// except in compliance with the License. Please obtain a copy of the License
+// at http://www.opencascade.org and read it completely before using this file.
+//
+// The Initial Developer of the Original Code is Open CASCADE S.A.S., having its
+// main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France.
+//
+// The Original Code and all software distributed under the License is
+// distributed on an "AS IS" basis, without warranty of any kind, and the
+// Initial Developer hereby disclaims all such warranties, including without
+// limitation, any warranties of merchantability, fitness for a particular
+// purpose or non-infringement. Please see the License for the specific terms
+// and conditions governing the rights and limitations under the License.
+
+
+inline Extrema_POnSurfParams::Extrema_POnSurfParams()
+: mySqrDistance (0.),
+  myElementType (Extrema_Node),
+  myIndexU      (0),
+  myIndexV      (0)
+{
+}
+
+inline Extrema_POnSurfParams::Extrema_POnSurfParams
+   (const Standard_Real theU, const Standard_Real theV, const gp_Pnt &thePnt)
+: Extrema_POnSurf (theU, theV, thePnt),
+  mySqrDistance   (0.),
+  myElementType   (Extrema_Node),
+  myIndexU        (0),
+  myIndexV        (0)
+{
+}
+
+inline void Extrema_POnSurfParams::SetSqrDistance
+        (const Standard_Real theSqrDistance)
+{
+  mySqrDistance = theSqrDistance;
+}
+
+inline Standard_Real Extrema_POnSurfParams::GetSqrDistance() const
+{
+  return mySqrDistance;
+}
+
+inline void Extrema_POnSurfParams::SetElementType
+        (const Extrema_ElementType theElementType)
+{
+  myElementType = theElementType;
+}
+
+inline Extrema_ElementType Extrema_POnSurfParams::GetElementType() const
+{
+  return myElementType;
+}
+    
+inline void Extrema_POnSurfParams::SetIndices
+                          (const Standard_Integer theIndexU,
+                           const Standard_Integer theIndexV)
+{
+  myIndexU = theIndexU;
+  myIndexV = theIndexV;
+}                          
+
+inline void Extrema_POnSurfParams::GetIndices
+                  (Standard_Integer &theIndexU,
+                   Standard_Integer &theIndexV) const
+{
+  theIndexU = myIndexU;
+  theIndexV = myIndexV;
+}