From aec5142ffb87eeef47f40ba34c2d8c9729039b57 Mon Sep 17 00:00:00 2001 From: emv Date: Mon, 19 Aug 2019 08:41:04 +0300 Subject: [PATCH] 0030892: Improve Extrema_ExtPS algorithm by unifying the GRAD and TREE methods Refactoring of the Extrema_GenExtPS class in order to improve performance and robustness of the algorithm by unifying the GRAD and TREE search methods. --- .../BRepExtrema_DistShapeShape.cxx | 17 +- .../BRepExtrema_DistShapeShape.hxx | 11 +- src/BRepExtrema/BRepExtrema_DistanceSS.cxx | 4 +- src/BRepExtrema/BRepExtrema_DistanceSS.hxx | 17 +- src/BRepExtrema/BRepExtrema_ExtPF.cxx | 7 +- src/BRepExtrema/BRepExtrema_ExtPF.hxx | 12 +- src/BRepLib/BRepLib_FindSurface.cxx | 40 +- src/BRepTest/BRepTest_ExtremaCommands.cxx | 2 +- src/BRepTest/BRepTest_SurfaceCommands.cxx | 14 +- src/BVH/BVH_BoxSet.hxx | 12 + src/BVH/BVH_IndexedBoxSet.hxx | 6 +- src/BVH/BVH_Tools.hxx | 19 +- src/Draw/Draw_Debug.cxx | 48 + src/Extrema/Extrema_ExtAlgo.hxx | 27 - src/Extrema/Extrema_ExtFlag.hxx | 12 +- src/Extrema/Extrema_ExtPExtS.cxx | 56 +- src/Extrema/Extrema_ExtPExtS.hxx | 15 +- src/Extrema/Extrema_ExtPRevS.cxx | 49 +- src/Extrema/Extrema_ExtPRevS.hxx | 16 +- src/Extrema/Extrema_ExtPS.cxx | 81 +- src/Extrema/Extrema_ExtPS.hxx | 43 +- src/Extrema/Extrema_FuncPSNorm.cxx | 98 +- src/Extrema/Extrema_FuncPSNorm.hxx | 29 +- src/Extrema/Extrema_GenExtPS.cxx | 1715 +++++++++-------- src/Extrema/Extrema_GenExtPS.hxx | 452 ++++- src/Extrema/Extrema_POnSurfParams.lxx | 4 +- src/Extrema/FILES | 1 - src/GCPnts/FILES | 2 + src/GCPnts/GCPnts.cxx | 54 + src/GCPnts/GCPnts.hxx | 35 + src/GeomAPI/GeomAPI_ProjectPointOnSurf.cxx | 81 +- src/GeomAPI/GeomAPI_ProjectPointOnSurf.hxx | 28 +- src/GeomInt/GeomInt_IntSS_1.cxx | 3 +- src/GeometryTest/GeometryTest_APICommands.cxx | 14 +- .../ProjLib_ComputeApproxOnPolarSurface.cxx | 119 +- src/TopOpeBRepTool/TopOpeBRepTool_PROJECT.cxx | 10 +- src/TopOpeBRepTool/TopOpeBRepTool_PROJECT.hxx | 7 +- tests/bugs/modalg_6/bug26356 | 34 +- tests/bugs/moddata_3/bug24068 | 6 +- tests/bugs/moddata_3/bug24134 | 20 +- tests/bugs/moddata_3/bug24138 | 2 +- tests/bugs/xde/bug22826 | 6 +- tests/perf/modalg/bug23906 | 2 +- 43 files changed, 1865 insertions(+), 1365 deletions(-) delete mode 100644 src/Extrema/Extrema_ExtAlgo.hxx create mode 100644 src/GCPnts/GCPnts.cxx create mode 100644 src/GCPnts/GCPnts.hxx diff --git a/src/BRepExtrema/BRepExtrema_DistShapeShape.cxx b/src/BRepExtrema/BRepExtrema_DistShapeShape.cxx index 13efe953dc..7273527fe5 100644 --- a/src/BRepExtrema/BRepExtrema_DistShapeShape.cxx +++ b/src/BRepExtrema/BRepExtrema_DistShapeShape.cxx @@ -154,7 +154,7 @@ void BRepExtrema_DistShapeShape::DistanceMapMap (const TopTools_IndexedMapOfShap const TopoDS_Shape& aShape1 = theMap1 (aPair.Index1); const TopoDS_Shape& aShape2 = theMap2 (aPair.Index2); - BRepExtrema_DistanceSS aDistTool (aShape1, aShape2, aBox1, aBox2, myDistRef, myEps); + BRepExtrema_DistanceSS aDistTool (aShape1, aShape2, aBox1, aBox2, myDistRef, myEps, myFlag); if (aDistTool.IsDone()) { if (aDistTool.DistValue() < myDistRef - myEps) @@ -199,8 +199,7 @@ BRepExtrema_DistShapeShape::BRepExtrema_DistShapeShape() myEps (Precision::Confusion()), myIsInitS1 (Standard_False), myIsInitS2 (Standard_False), - myFlag (Extrema_ExtFlag_MINMAX), - myAlgo (Extrema_ExtAlgo_Grad) + myFlag (Extrema_ExtFlag_MINMAX) { // } @@ -211,16 +210,14 @@ BRepExtrema_DistShapeShape::BRepExtrema_DistShapeShape() //======================================================================= BRepExtrema_DistShapeShape::BRepExtrema_DistShapeShape(const TopoDS_Shape& Shape1, const TopoDS_Shape& Shape2, - const Extrema_ExtFlag F, - const Extrema_ExtAlgo A) + const Extrema_ExtFlag F) : myDistRef (0.0), myIsDone (Standard_False), myInnerSol (Standard_False), myEps (Precision::Confusion()), myIsInitS1 (Standard_False), myIsInitS2 (Standard_False), - myFlag (F), - myAlgo (A) + myFlag (F) { LoadS1(Shape1); LoadS2(Shape2); @@ -235,16 +232,14 @@ BRepExtrema_DistShapeShape::BRepExtrema_DistShapeShape(const TopoDS_Shape& Shape BRepExtrema_DistShapeShape::BRepExtrema_DistShapeShape(const TopoDS_Shape& Shape1, const TopoDS_Shape& Shape2, const Standard_Real theDeflection, - const Extrema_ExtFlag F, - const Extrema_ExtAlgo A) + const Extrema_ExtFlag F) : myDistRef (0.0), myIsDone (Standard_False), myInnerSol (Standard_False), myEps (theDeflection), myIsInitS1 (Standard_False), myIsInitS2 (Standard_False), - myFlag (F), - myAlgo (A) + myFlag (F) { LoadS1(Shape1); LoadS2(Shape2); diff --git a/src/BRepExtrema/BRepExtrema_DistShapeShape.hxx b/src/BRepExtrema/BRepExtrema_DistShapeShape.hxx index c3040472ec..04fe2e7375 100644 --- a/src/BRepExtrema/BRepExtrema_DistShapeShape.hxx +++ b/src/BRepExtrema/BRepExtrema_DistShapeShape.hxx @@ -18,7 +18,6 @@ #include #include #include -#include #include #include #include @@ -39,9 +38,9 @@ class BRepExtrema_DistShapeShape Standard_EXPORT BRepExtrema_DistShapeShape(); //! computation of the minimum distance (value and pair of points) using default deflection
//! Default value is Precision::Confusion().
- Standard_EXPORT BRepExtrema_DistShapeShape(const TopoDS_Shape& Shape1,const TopoDS_Shape& Shape2,const Extrema_ExtFlag F = Extrema_ExtFlag_MINMAX,const Extrema_ExtAlgo A = Extrema_ExtAlgo_Grad); + Standard_EXPORT BRepExtrema_DistShapeShape(const TopoDS_Shape& Shape1,const TopoDS_Shape& Shape2,const Extrema_ExtFlag F = Extrema_ExtFlag_MIN); //! create tool and load both shapes into it
- Standard_EXPORT BRepExtrema_DistShapeShape(const TopoDS_Shape& Shape1,const TopoDS_Shape& Shape2,const Standard_Real theDeflection,const Extrema_ExtFlag F = Extrema_ExtFlag_MINMAX,const Extrema_ExtAlgo A = Extrema_ExtAlgo_Grad); + Standard_EXPORT BRepExtrema_DistShapeShape(const TopoDS_Shape& Shape1,const TopoDS_Shape& Shape2,const Standard_Real theDeflection,const Extrema_ExtFlag F = Extrema_ExtFlag_MIN); void SetDeflection(const Standard_Real theDeflection) { @@ -129,11 +128,6 @@ class BRepExtrema_DistShapeShape myFlag = F; } - void SetAlgo(const Extrema_ExtAlgo A) - { - myAlgo = A; - } - private: //! computes the minimum distance between two maps of shapes (Face,Edge,Vertex)
@@ -156,7 +150,6 @@ private: Standard_Boolean myIsInitS1; Standard_Boolean myIsInitS2; Extrema_ExtFlag myFlag; - Extrema_ExtAlgo myAlgo; Bnd_SeqOfBox myBV1; Bnd_SeqOfBox myBV2; Bnd_SeqOfBox myBE1; diff --git a/src/BRepExtrema/BRepExtrema_DistanceSS.cxx b/src/BRepExtrema/BRepExtrema_DistanceSS.cxx index 61773dd806..6ae08967d5 100644 --- a/src/BRepExtrema/BRepExtrema_DistanceSS.cxx +++ b/src/BRepExtrema/BRepExtrema_DistanceSS.cxx @@ -772,7 +772,7 @@ void BRepExtrema_DistanceSS::Perform(const TopoDS_Vertex& S1, const TopoDS_Face& const Standard_Real Dst=B1.Distance(B2); if ((Dst < myDstRef - myEps) || (fabs(Dst-myDstRef) < myEps)) { - BRepExtrema_ExtPF Ext(S1,S2,myFlag,myAlgo); + BRepExtrema_ExtPF Ext(S1,S2,myFlag); const Standard_Integer NbExtrema = Ext.IsDone()? Ext.NbExt() : 0; if ( NbExtrema > 0 ) { @@ -828,7 +828,7 @@ void BRepExtrema_DistanceSS::Perform(const TopoDS_Face& S1, const TopoDS_Vertex& const Standard_Real Dst=B1.Distance(B2); if ((Dst < myDstRef - myEps) || (fabs(Dst-myDstRef) < myEps)) { - BRepExtrema_ExtPF Ext(S2,S1,myFlag,myAlgo); + BRepExtrema_ExtPF Ext(S2,S1,myFlag); const Standard_Integer NbExtrema = Ext.IsDone()? Ext.NbExt() : 0; if ( NbExtrema > 0 ) { diff --git a/src/BRepExtrema/BRepExtrema_DistanceSS.hxx b/src/BRepExtrema/BRepExtrema_DistanceSS.hxx index 1f7e6fc9e4..b6a807bfd0 100644 --- a/src/BRepExtrema/BRepExtrema_DistanceSS.hxx +++ b/src/BRepExtrema/BRepExtrema_DistanceSS.hxx @@ -16,7 +16,6 @@ #include #include -#include #include #include @@ -39,9 +38,8 @@ class BRepExtrema_DistanceSS BRepExtrema_DistanceSS(const TopoDS_Shape& S1, const TopoDS_Shape& S2, const Bnd_Box& B1, const Bnd_Box& B2, const Standard_Real DstRef, - const Extrema_ExtFlag F = Extrema_ExtFlag_MINMAX, - const Extrema_ExtAlgo A = Extrema_ExtAlgo_Grad) - : myDstRef(DstRef), myModif(Standard_False), myEps(Precision::Confusion()), myFlag(F), myAlgo(A) + const Extrema_ExtFlag F = Extrema_ExtFlag_MINMAX) + : myDstRef(DstRef), myModif(Standard_False), myEps(Precision::Confusion()), myFlag(F) { Perform(S1, S2, B1, B2); } @@ -52,9 +50,8 @@ class BRepExtrema_DistanceSS BRepExtrema_DistanceSS(const TopoDS_Shape& S1, const TopoDS_Shape& S2, const Bnd_Box& B1, const Bnd_Box& B2, const Standard_Real DstRef, const Standard_Real aDeflection, - const Extrema_ExtFlag F = Extrema_ExtFlag_MINMAX, - const Extrema_ExtAlgo A = Extrema_ExtAlgo_Grad) - : myDstRef(DstRef), myModif(Standard_False), myEps(aDeflection), myFlag(F), myAlgo(A) + const Extrema_ExtFlag F = Extrema_ExtFlag_MINMAX) + : myDstRef(DstRef), myModif(Standard_False), myEps(aDeflection), myFlag(F) { Perform(S1, S2, B1, B2); } @@ -83,11 +80,6 @@ class BRepExtrema_DistanceSS { myFlag = F; } - //! sets the flag controlling ... - void SetAlgo(const Extrema_ExtAlgo A) - { - myAlgo = A; - } private: @@ -130,7 +122,6 @@ class BRepExtrema_DistanceSS Standard_Boolean myModif; Standard_Real myEps; Extrema_ExtFlag myFlag; - Extrema_ExtAlgo myAlgo; }; #endif diff --git a/src/BRepExtrema/BRepExtrema_ExtPF.cxx b/src/BRepExtrema/BRepExtrema_ExtPF.cxx index 41493900b9..fbe03ce07c 100644 --- a/src/BRepExtrema/BRepExtrema_ExtPF.cxx +++ b/src/BRepExtrema/BRepExtrema_ExtPF.cxx @@ -32,9 +32,9 @@ //======================================================================= BRepExtrema_ExtPF::BRepExtrema_ExtPF(const TopoDS_Vertex& TheVertex, const TopoDS_Face& TheFace, - const Extrema_ExtFlag TheFlag, const Extrema_ExtAlgo TheAlgo) + const Extrema_ExtFlag TheFlag) { - Initialize(TheFace,TheFlag,TheAlgo); + Initialize(TheFace,TheFlag); Perform(TheVertex,TheFace); } @@ -44,7 +44,7 @@ BRepExtrema_ExtPF::BRepExtrema_ExtPF(const TopoDS_Vertex& TheVertex, const TopoD //======================================================================= void BRepExtrema_ExtPF::Initialize(const TopoDS_Face& TheFace, - const Extrema_ExtFlag TheFlag, const Extrema_ExtAlgo TheAlgo) + const Extrema_ExtFlag TheFlag) { // cette surface doit etre en champ. Extrema ne fait // pas de copie et prend seulement un pointeur dessus. @@ -60,7 +60,6 @@ void BRepExtrema_ExtPF::Initialize(const TopoDS_Face& TheFace, Standard_Real U1, U2, V1, V2; BRepTools::UVBounds(TheFace, U1, U2, V1, V2); myExtPS.SetFlag(TheFlag); - myExtPS.SetAlgo(TheAlgo); myExtPS.Initialize(mySurf, U1, U2, V1, V2, aTolU, aTolV); } diff --git a/src/BRepExtrema/BRepExtrema_ExtPF.hxx b/src/BRepExtrema/BRepExtrema_ExtPF.hxx index 5a79f84579..71370f0bbd 100644 --- a/src/BRepExtrema/BRepExtrema_ExtPF.hxx +++ b/src/BRepExtrema/BRepExtrema_ExtPF.hxx @@ -21,7 +21,6 @@ #include #include #include -#include class TopoDS_Vertex; class TopoDS_Face; @@ -38,12 +37,10 @@ class BRepExtrema_ExtPF {} //! It calculates all the distances.
Standard_EXPORT BRepExtrema_ExtPF(const TopoDS_Vertex& TheVertex,const TopoDS_Face& TheFace, - const Extrema_ExtFlag TheFlag = Extrema_ExtFlag_MINMAX, - const Extrema_ExtAlgo TheAlgo = Extrema_ExtAlgo_Grad); + const Extrema_ExtFlag TheFlag = Extrema_ExtFlag_MINMAX); Standard_EXPORT void Initialize(const TopoDS_Face& TheFace, - const Extrema_ExtFlag TheFlag = Extrema_ExtFlag_MINMAX, - const Extrema_ExtAlgo TheAlgo = Extrema_ExtAlgo_Grad); + const Extrema_ExtFlag TheFlag = Extrema_ExtFlag_MINMAX); //! An exception is raised if the fields have not been initialized.
//! Be careful: this method uses the Face only for classify not for the fields.
@@ -79,11 +76,6 @@ class BRepExtrema_ExtPF myExtPS.SetFlag(F); } - void SetAlgo(const Extrema_ExtAlgo A) - { - myExtPS.SetAlgo(A); - } - private: Extrema_ExtPS myExtPS; diff --git a/src/BRepLib/BRepLib_FindSurface.cxx b/src/BRepLib/BRepLib_FindSurface.cxx index 21a85b697e..c21009e6c4 100644 --- a/src/BRepLib/BRepLib_FindSurface.cxx +++ b/src/BRepLib/BRepLib_FindSurface.cxx @@ -23,6 +23,7 @@ #include #include #include +#include #include #include #include @@ -181,39 +182,6 @@ BRepLib_FindSurface::BRepLib_FindSurface(const TopoDS_Shape& S, namespace { -static void fillParams (const TColStd_Array1OfReal& theKnots, - Standard_Integer theDegree, - Standard_Real theParMin, - Standard_Real theParMax, - NCollection_Vector& theParams) -{ - Standard_Real aPrevPar = theParMin; - theParams.Append (aPrevPar); - - Standard_Integer aNbP = Max (theDegree, 1); - - for (Standard_Integer i = 1; - (i < theKnots.Length()) && (theKnots (i) < (theParMax - Precision::PConfusion())); ++i) - { - if (theKnots (i + 1) < theParMin + Precision::PConfusion()) - continue; - - Standard_Real aStep = (theKnots (i + 1) - theKnots (i)) / aNbP; - for (Standard_Integer k = 1; k <= aNbP ; ++k) - { - Standard_Real aPar = theKnots (i) + k * aStep; - if (aPar > theParMax - Precision::PConfusion()) - break; - - if (aPar > aPrevPar + Precision::PConfusion()) - { - theParams.Append (aPar); - aPrevPar = aPar; - } - } - } - theParams.Append (theParMax); -} static void fillPoints (const BRepAdaptor_Curve& theCurve, const NCollection_Vector theParams, @@ -361,13 +329,13 @@ void BRepLib_FindSurface::Init(const TopoDS_Shape& S, aKnots.SetValue (1, GC->FirstParameter()); aKnots.SetValue (2, GC->LastParameter()); - fillParams (aKnots, GC->Degree(), dfUf, dfUl, aParams); + GCPnts::FillParams (aKnots, GC->Degree(), dfUf, dfUl, aParams); break; } case GeomAbs_BSplineCurve: { Handle(Geom_BSplineCurve) GC = c.BSpline(); - fillParams (GC->Knots(), GC->Degree(), dfUf, dfUl, aParams); + GCPnts::FillParams (GC->Knots(), GC->Degree(), dfUf, dfUl, aParams); break; } case GeomAbs_Line: @@ -394,7 +362,7 @@ void BRepLib_FindSurface::Init(const TopoDS_Shape& S, aBounds.SetValue (1, dfUf); aBounds.SetValue (2, dfUl); - fillParams (aBounds, iNbPoints - 1, dfUf, dfUl, aParams); + GCPnts::FillParams (aBounds, iNbPoints - 1, dfUf, dfUl, aParams); } } diff --git a/src/BRepTest/BRepTest_ExtremaCommands.cxx b/src/BRepTest/BRepTest_ExtremaCommands.cxx index 0ca2fa983b..ff7b0e7fc9 100644 --- a/src/BRepTest/BRepTest_ExtremaCommands.cxx +++ b/src/BRepTest/BRepTest_ExtremaCommands.cxx @@ -73,7 +73,7 @@ static Standard_Integer distmini(Draw_Interpretor& di, Standard_Integer n, const if (n == 5) aDeflection = Draw::Atof(a[4]); - BRepExtrema_DistShapeShape dst(S1 ,S2, aDeflection); + BRepExtrema_DistShapeShape dst(S1 ,S2, aDeflection, Extrema_ExtFlag_MIN); if (dst.IsDone()) { diff --git a/src/BRepTest/BRepTest_SurfaceCommands.cxx b/src/BRepTest/BRepTest_SurfaceCommands.cxx index 82eb8550ad..99bc9abd11 100644 --- a/src/BRepTest/BRepTest_SurfaceCommands.cxx +++ b/src/BRepTest/BRepTest_SurfaceCommands.cxx @@ -619,9 +619,9 @@ static Standard_Integer getedgeregul //======================================================================= static Standard_Integer projponf(Draw_Interpretor& di, Standard_Integer n, const char** a) { - if (n < 3 || n > 5) { + if (n < 3 || n > 4) { di << "Project point on the face.\n"; - di << "Usage: projponf face pnt [extrema flag: -min/-max/-minmax] [extrema algo: -g(grad)/-t(tree)]\n"; + di << "Usage: projponf face pnt [extrema flag: -min/-max/-minmax]\n"; return 1; } // get face @@ -644,7 +644,6 @@ static Standard_Integer projponf(Draw_Interpretor& di, Standard_Integer n, const // // get projection options // default values; - Extrema_ExtAlgo anExtAlgo = Extrema_ExtAlgo_Grad; Extrema_ExtFlag anExtFlag = Extrema_ExtFlag_MINMAX; // for (Standard_Integer i = 3; i < n; ++i) { @@ -657,12 +656,6 @@ static Standard_Integer projponf(Draw_Interpretor& di, Standard_Integer n, const else if (!strcasecmp(a[i], "-minmax")) { anExtFlag = Extrema_ExtFlag_MINMAX; } - else if (!strcasecmp(a[i], "-t")) { - anExtAlgo = Extrema_ExtAlgo_Tree; - } - else if (!strcasecmp(a[i], "-g")) { - anExtAlgo = Extrema_ExtAlgo_Grad; - } } // // get surface @@ -679,7 +672,6 @@ static Standard_Integer projponf(Draw_Interpretor& di, Standard_Integer n, const GeomAPI_ProjectPointOnSurf aProjPS; aProjPS.Init(aSurf, aUMin, aUMax, aVMin, aVMax); // set the options - aProjPS.SetExtremaAlgo(anExtAlgo); aProjPS.SetExtremaFlag(anExtFlag); // perform projection aProjPS.Perform(aP); @@ -768,7 +760,7 @@ void BRepTest::SurfaceCommands(Draw_Interpretor& theCommands) theCommands.Add ("getedgeregularity", "getedgeregularity edge face1 [face2]", __FILE__,getedgeregul,g); theCommands.Add ("projponf", - "projponf face pnt [extrema flag: -min/-max/-minmax] [extrema algo: -g(grad)/-t(tree)]\n" + "projponf face pnt [extrema flag: -min/-max/-minmax]\n" "\t\tProject point on the face.", __FILE__, projponf, g); } diff --git a/src/BVH/BVH_BoxSet.hxx b/src/BVH/BVH_BoxSet.hxx index 5aace9e994..c1f3e54014 100644 --- a/src/BVH/BVH_BoxSet.hxx +++ b/src/BVH/BVH_BoxSet.hxx @@ -66,6 +66,18 @@ public: //! @name Adding elements in BVH BVH_Object::myIsDirty = Standard_True; } + //! Allows to update the box of the element while the tree is not yet built + virtual void UpdateBox (const Standard_Integer theId, const BVH_Box& theNewBox) + { + if (BVH_Object::myIsDirty) + { + if (theId >= 0 && theId < Size()) + { + myBoxes[theId] = theNewBox; + } + } + } + public: //! @name BVH construction //! BVH construction diff --git a/src/BVH/BVH_IndexedBoxSet.hxx b/src/BVH/BVH_IndexedBoxSet.hxx index dd822adce0..e62020d222 100644 --- a/src/BVH/BVH_IndexedBoxSet.hxx +++ b/src/BVH/BVH_IndexedBoxSet.hxx @@ -84,7 +84,7 @@ public: //! @name Necessary overrides for BVH construction //! Returns the bounding box with the given index. virtual BVH_Box Box (const Standard_Integer theIndex) const Standard_OVERRIDE { - return myBoxes[myIndices[theIndex]]; + return this->myBoxes[myIndices[theIndex]]; } //! Swaps indices of two specified boxes. @@ -95,9 +95,9 @@ public: //! @name Necessary overrides for BVH construction } //! Returns the Element with the index theIndex. - virtual DataType Element (const Standard_Integer theIndex) const + virtual DataType Element (const Standard_Integer theIndex) const Standard_OVERRIDE { - return myElements[myIndices[theIndex]]; + return this->myElements[myIndices[theIndex]]; } protected: //! @name Fields diff --git a/src/BVH/BVH_Tools.hxx b/src/BVH/BVH_Tools.hxx index 847d904a56..885a9e3b61 100644 --- a/src/BVH/BVH_Tools.hxx +++ b/src/BVH/BVH_Tools.hxx @@ -88,6 +88,24 @@ public: //! @name Point-Box Square distance return aDist; } + //! Computes Max square distance between point and bounding box + static T PointBoxMaxSquareDistance (const BVH_VecNt& thePoint, + const BVH_VecNt& theCMin, + const BVH_VecNt& theCMax) + { + T aDist = 0; + for (int i = 0; i < N; ++i) + { + T dmin = 0, dmax = 0; + if (thePoint[i] > theCMin[i]) { dmin = thePoint[i] - theCMin[i]; } + if (thePoint[i] < theCMax[i]) { dmax = theCMax[i] - thePoint[i]; } + T d = dmin > dmax ? dmin : dmax; + d *= d; + aDist += d; + } + return aDist; + } + public: //! @name Point-Box projection //! Computes projection of point on bounding box @@ -110,7 +128,6 @@ public: //! @name Point-Box projection { return thePoint.cwiseMax (theCMin).cwiseMin (theCMax); } - public: //! @name Point-Triangle Square distance //! Computes square distance between point and triangle diff --git a/src/Draw/Draw_Debug.cxx b/src/Draw/Draw_Debug.cxx index af6d6a743d..ef5bb2a567 100644 --- a/src/Draw/Draw_Debug.cxx +++ b/src/Draw/Draw_Debug.cxx @@ -18,6 +18,10 @@ #include #include +#include +#include +#include + // This file defines global functions not declared in any public header, // intended for use from debugger prompt (Command Window in Visual Studio) @@ -40,3 +44,47 @@ Standard_EXPORT const char* Draw_Eval (const char *theCommandStr) return anException.GetMessageString(); } } + +//======================================================================= +//function : DBRep_SetOBB +//purpose : Draw OBB +//======================================================================= +Standard_EXPORT const char* Draw_SetOBB(const char* theNameStr, void* theBox) +{ + if (theNameStr == 0 || theBox == 0) + { + return "Error: name or box is null"; + } + try { + Bnd_OBB B = *(Bnd_OBB*)theBox; + Handle(Draw_Box) DB = new Draw_Box (B, Draw_orange); + Draw::Set (theNameStr, DB); + return theNameStr; + } + catch (Standard_Failure const& anException) + { + return anException.GetMessageString(); + } +} + +//======================================================================= +//function : DBRep_SetBox +//purpose : Draw Box +//======================================================================= +Standard_EXPORT const char* Draw_SetBox(const char* theNameStr, void* theBox) +{ + if (theNameStr == 0 || theBox == 0) + { + return "Error: name or box is null"; + } + try { + Bnd_Box B = *(Bnd_Box*)theBox; + Handle(Draw_Box) DB = new Draw_Box (B, Draw_orange); + Draw::Set (theNameStr, DB); + return theNameStr; + } + catch (Standard_Failure const& anException) + { + return anException.GetMessageString(); + } +} diff --git a/src/Extrema/Extrema_ExtAlgo.hxx b/src/Extrema/Extrema_ExtAlgo.hxx deleted file mode 100644 index 0609e18d7d..0000000000 --- a/src/Extrema/Extrema_ExtAlgo.hxx +++ /dev/null @@ -1,27 +0,0 @@ -// Created on: 1991-02-26 -// Created by: Isabelle GRIGNON -// Copyright (c) 1991-1999 Matra Datavision -// Copyright (c) 1999-2014 OPEN CASCADE SAS -// -// This file is part of Open CASCADE Technology software library. -// -// This library is free software; you can redistribute it and/or modify it under -// the terms of the GNU Lesser General Public License version 2.1 as published -// by the Free Software Foundation, with special exception defined in the file -// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT -// distribution for complete text of the license and disclaimer of any warranty. -// -// Alternatively, this file may be used under the terms of Open CASCADE -// commercial license or contractual agreement. - -#ifndef _Extrema_ExtAlgo_HeaderFile -#define _Extrema_ExtAlgo_HeaderFile - - -enum Extrema_ExtAlgo -{ -Extrema_ExtAlgo_Grad, -Extrema_ExtAlgo_Tree -}; - -#endif // _Extrema_ExtAlgo_HeaderFile diff --git a/src/Extrema/Extrema_ExtFlag.hxx b/src/Extrema/Extrema_ExtFlag.hxx index e4a1f649c8..6627660dad 100644 --- a/src/Extrema/Extrema_ExtFlag.hxx +++ b/src/Extrema/Extrema_ExtFlag.hxx @@ -17,12 +17,16 @@ #ifndef _Extrema_ExtFlag_HeaderFile #define _Extrema_ExtFlag_HeaderFile - +//! Enumeration describes the objective for extrema algorithms. +//! Generally: +//! - *Extrema_ExtFlag_MIN* - means that only minimal solutions are required +//! - *Extrema_ExtFlag_MAX* - means that only maximal solutions are required +//! - *Extrema_ExtFlag_MINMAX* - means that all solutions are required enum Extrema_ExtFlag { -Extrema_ExtFlag_MIN, -Extrema_ExtFlag_MAX, -Extrema_ExtFlag_MINMAX + Extrema_ExtFlag_MIN, + Extrema_ExtFlag_MAX, + Extrema_ExtFlag_MINMAX }; #endif // _Extrema_ExtFlag_HeaderFile diff --git a/src/Extrema/Extrema_ExtPExtS.cxx b/src/Extrema/Extrema_ExtPExtS.cxx index bd8a0ec159..d2ce0d3fbb 100644 --- a/src/Extrema/Extrema_ExtPExtS.cxx +++ b/src/Extrema/Extrema_ExtPExtS.cxx @@ -144,7 +144,7 @@ void Extrema_ExtPExtS::MakePreciser (Standard_Real& U, } //============================================================================= -Extrema_ExtPExtS::Extrema_ExtPExtS() +Extrema_ExtPExtS::Extrema_ExtPExtS (const Handle (Extrema_GenExtPS)& theExtPS) : myuinf(0.0), myusup(0.0), mytolu(0.0), @@ -153,7 +153,8 @@ Extrema_ExtPExtS::Extrema_ExtPExtS() mytolv(0.0), myIsAnalyticallyComputable(Standard_False), myDone(Standard_False), - myNbExt(0) + myNbExt(0), + myExtPS (theExtPS) { for (size_t anIdx = 0; anIdx < sizeof (mySqDist) / sizeof (mySqDist[0]); anIdx++) { @@ -170,7 +171,8 @@ Extrema_ExtPExtS::Extrema_ExtPExtS (const gp_Pnt& const Standard_Real theVmin, const Standard_Real theVsup, const Standard_Real theTolU, - const Standard_Real theTolV) + const Standard_Real theTolV, + const Handle(Extrema_GenExtPS)& theExtPS) : myuinf(theUmin), myusup(theUsup), mytolu(theTolU), @@ -180,7 +182,8 @@ Extrema_ExtPExtS::Extrema_ExtPExtS (const gp_Pnt& myS (theS), myIsAnalyticallyComputable(Standard_False), myDone(Standard_False), - myNbExt(0) + myNbExt(0), + myExtPS (theExtPS) { for (size_t anIdx = 0; anIdx < sizeof (mySqDist) / sizeof (mySqDist[0]); anIdx++) { @@ -201,7 +204,8 @@ Extrema_ExtPExtS::Extrema_ExtPExtS (const gp_Pnt& Extrema_ExtPExtS::Extrema_ExtPExtS (const gp_Pnt& theP, const Handle(GeomAdaptor_HSurfaceOfLinearExtrusion)& theS, const Standard_Real theTolU, - const Standard_Real theTolV) + const Standard_Real theTolV, + const Handle(Extrema_GenExtPS)& theExtPS) : myuinf(theS->FirstUParameter()), myusup(theS->LastUParameter()), mytolu(theTolU), @@ -211,7 +215,8 @@ Extrema_ExtPExtS::Extrema_ExtPExtS (const gp_Pnt& myS (theS), myIsAnalyticallyComputable(Standard_False), myDone(Standard_False), - myNbExt(0) + myNbExt(0), + myExtPS (theExtPS) { for (size_t anIdx = 0; anIdx < sizeof (mySqDist) / sizeof (mySqDist[0]); anIdx++) { @@ -265,15 +270,18 @@ void Extrema_ExtPExtS::Initialize (const Handle(GeomAdaptor_HSurfaceOfLinearExtr if (!myIsAnalyticallyComputable) { - myExtPS.Initialize (theS->ChangeSurface(), - 32, - 32, - theUinf, - theUsup, - theVinf, - theVsup, - theTolU, - theTolV); + if (myExtPS.IsNull()) + myExtPS = new Extrema_GenExtPS(); + + myExtPS->Initialize (theS->ChangeSurface(), + 32, + 32, + theUinf, + theUsup, + theVinf, + theVsup, + theTolU, + theTolV); } } @@ -292,11 +300,9 @@ void Extrema_ExtPExtS::Perform (const gp_Pnt& P) myNbExt = 0; if (!myIsAnalyticallyComputable) { - myExtPS.Perform(P); - myDone = myExtPS.IsDone(); -// modified by NIZHNY-EAP Wed Nov 17 12:59:08 1999 ___BEGIN___ - myNbExt = myExtPS.NbExt(); -// modified by NIZHNY-EAP Wed Nov 17 12:59:09 1999 ___END___ + myExtPS->Perform(P); + myDone = myExtPS->IsDone(); + myNbExt = myExtPS->NbExt(); return; } @@ -455,10 +461,8 @@ Standard_Boolean Extrema_ExtPExtS::IsDone () const { return myDone; } Standard_Integer Extrema_ExtPExtS::NbExt () const { if (!IsDone()) { throw StdFail_NotDone(); } - if (myIsAnalyticallyComputable) - return myNbExt; - else - return myExtPS.NbExt(); + + return myNbExt; } //============================================================================= @@ -474,7 +478,7 @@ Standard_Real Extrema_ExtPExtS::SquareDistance (const Standard_Integer N) const return mySqDist[N-1]; // modified by NIZHNY-MKK Thu Sep 18 14:48:42 2003.END else - return myExtPS.SquareDistance(N); + return myExtPS->SquareDistance(N); } //============================================================================= @@ -491,7 +495,7 @@ const Extrema_POnSurf& Extrema_ExtPExtS::Point (const Standard_Integer N) const } // modified by NIZHNY-MKK Thu Sep 18 14:47:43 2003.END else - return myExtPS.Point(N); + return myExtPS->Point(N); } //============================================================================= diff --git a/src/Extrema/Extrema_ExtPExtS.hxx b/src/Extrema/Extrema_ExtPExtS.hxx index 67b50a54f7..4e4db83e76 100644 --- a/src/Extrema/Extrema_ExtPExtS.hxx +++ b/src/Extrema/Extrema_ExtPExtS.hxx @@ -50,15 +50,21 @@ class Extrema_ExtPExtS : public Standard_Transient public: - Standard_EXPORT Extrema_ExtPExtS(); + //! theExtPS is used to compute the solutions in case + //! it cannot be found analytically. + Standard_EXPORT Extrema_ExtPExtS(const Handle(Extrema_GenExtPS)& theExtPS); //! It calculates all the distances between a point //! from gp and a Surface. - Standard_EXPORT Extrema_ExtPExtS(const gp_Pnt& P, const Handle(GeomAdaptor_HSurfaceOfLinearExtrusion)& S, const Standard_Real Umin, const Standard_Real Usup, const Standard_Real Vmin, const Standard_Real Vsup, const Standard_Real TolU, const Standard_Real TolV); + //! theExtPS is used to compute the solutions in case + //! it cannot be found analytically. + Standard_EXPORT Extrema_ExtPExtS(const gp_Pnt& P, const Handle(GeomAdaptor_HSurfaceOfLinearExtrusion)& S, const Standard_Real Umin, const Standard_Real Usup, const Standard_Real Vmin, const Standard_Real Vsup, const Standard_Real TolU, const Standard_Real TolV, const Handle(Extrema_GenExtPS)& theExtPS = NULL); //! It calculates all the distances between a point //! from gp and a Surface. - Standard_EXPORT Extrema_ExtPExtS(const gp_Pnt& P, const Handle(GeomAdaptor_HSurfaceOfLinearExtrusion)& S, const Standard_Real TolU, const Standard_Real TolV); + //! theExtPS is used to compute the solutions in case + //! it cannot be found analytically. + Standard_EXPORT Extrema_ExtPExtS(const gp_Pnt& P, const Handle(GeomAdaptor_HSurfaceOfLinearExtrusion)& S, const Standard_Real TolU, const Standard_Real TolV, const Handle(Extrema_GenExtPS)& theExtPS = NULL); //! Initializes the fields of the algorithm. Standard_EXPORT void Initialize (const Handle(GeomAdaptor_HSurfaceOfLinearExtrusion)& S, const Standard_Real Uinf, const Standard_Real Usup, const Standard_Real Vinf, const Standard_Real Vsup, const Standard_Real TolU, const Standard_Real TolV); @@ -103,13 +109,12 @@ private: Handle(GeomAdaptor_HSurfaceOfLinearExtrusion) myS; gp_Vec myDirection; gp_Ax2 myPosition; - Extrema_GenExtPS myExtPS; Standard_Boolean myIsAnalyticallyComputable; Standard_Boolean myDone; Standard_Integer myNbExt; Standard_Real mySqDist[4]; Extrema_POnSurf myPoint[4]; - + Handle(Extrema_GenExtPS) myExtPS; }; diff --git a/src/Extrema/Extrema_ExtPRevS.cxx b/src/Extrema/Extrema_ExtPRevS.cxx index c7388416fc..a1400c79c5 100644 --- a/src/Extrema/Extrema_ExtPRevS.cxx +++ b/src/Extrema/Extrema_ExtPRevS.cxx @@ -208,7 +208,9 @@ static Standard_Boolean IsExtremum (const Standard_Real U, const Standard_Real V //purpose : //======================================================================= -Extrema_ExtPRevS::Extrema_ExtPRevS() +Extrema_ExtPRevS::Extrema_ExtPRevS(const Handle(Extrema_GenExtPS)& theExtPS) + : + myExtPS (theExtPS) { myvinf = myvsup = 0.0; mytolv = Precision::Confusion(); @@ -233,7 +235,10 @@ Extrema_ExtPRevS::Extrema_ExtPRevS (const gp_Pnt& const Standard_Real theVmin, const Standard_Real theVsup, const Standard_Real theTolU, - const Standard_Real theTolV) + const Standard_Real theTolV, + const Handle(Extrema_GenExtPS)& theExtPS) + : + myExtPS (theExtPS) { Initialize (theS, theUmin, @@ -253,7 +258,10 @@ Extrema_ExtPRevS::Extrema_ExtPRevS (const gp_Pnt& Extrema_ExtPRevS::Extrema_ExtPRevS (const gp_Pnt& theP, const Handle(GeomAdaptor_HSurfaceOfRevolution)& theS, const Standard_Real theTolU, - const Standard_Real theTolV) + const Standard_Real theTolV, + const Handle(Extrema_GenExtPS)& theExtPS) + : + myExtPS (theExtPS) { Initialize (theS, theS->FirstUParameter(), @@ -305,15 +313,18 @@ void Extrema_ExtPRevS::Initialize (const Handle(GeomAdaptor_HSurfaceOfRevolution aNbv = 100; } - myExtPS.Initialize (theS->ChangeSurface(), - aNbu, - aNbv, - theUmin, - theUsup, - theVmin, - theVsup, - theTolU, - theTolV); + if (myExtPS.IsNull()) + myExtPS = new Extrema_GenExtPS(); + + myExtPS->Initialize (theS->ChangeSurface(), + aNbu, + aNbv, + theUmin, + theUsup, + theVmin, + theVsup, + theTolU, + theTolV); } } //======================================================================= @@ -326,11 +337,11 @@ void Extrema_ExtPRevS::Perform(const gp_Pnt& P) myDone = Standard_False; myNbExt = 0; - if (!myIsAnalyticallyComputable) { - - myExtPS.Perform(P); - myDone = myExtPS.IsDone(); - myNbExt = myExtPS.NbExt(); + if (!myIsAnalyticallyComputable) + { + myExtPS->Perform(P); + myDone = myExtPS->IsDone(); + myNbExt = myExtPS->NbExt(); return; } @@ -555,7 +566,7 @@ Standard_Real Extrema_ExtPRevS::SquareDistance(const Standard_Integer N) const if (myIsAnalyticallyComputable) return mySqDist[N-1]; else - return myExtPS.SquareDistance(N); + return myExtPS->SquareDistance(N); } //======================================================================= //function : Point @@ -571,7 +582,7 @@ const Extrema_POnSurf& Extrema_ExtPRevS::Point(const Standard_Integer N) const if (myIsAnalyticallyComputable) return myPoint[N-1]; else - return myExtPS.Point(N); + return myExtPS->Point(N); } diff --git a/src/Extrema/Extrema_ExtPRevS.hxx b/src/Extrema/Extrema_ExtPRevS.hxx index e6d069d8ac..30c1a874fa 100644 --- a/src/Extrema/Extrema_ExtPRevS.hxx +++ b/src/Extrema/Extrema_ExtPRevS.hxx @@ -45,16 +45,21 @@ class Extrema_ExtPRevS : public Standard_Transient public: - - Standard_EXPORT Extrema_ExtPRevS(); + //! theExtPS is used to compute the solutions in case + //! it cannot be found analytically. + Standard_EXPORT Extrema_ExtPRevS(const Handle(Extrema_GenExtPS)& theExtPS = NULL); //! It calculates all the distances between a point //! from gp and a SurfacePtr from Adaptor3d. - Standard_EXPORT Extrema_ExtPRevS(const gp_Pnt& P, const Handle(GeomAdaptor_HSurfaceOfRevolution)& S, const Standard_Real Umin, const Standard_Real Usup, const Standard_Real Vmin, const Standard_Real Vsup, const Standard_Real TolU, const Standard_Real TolV); + //! theExtPS is used to compute the solutions in case + //! it cannot be found analytically. + Standard_EXPORT Extrema_ExtPRevS(const gp_Pnt& P, const Handle(GeomAdaptor_HSurfaceOfRevolution)& S, const Standard_Real Umin, const Standard_Real Usup, const Standard_Real Vmin, const Standard_Real Vsup, const Standard_Real TolU, const Standard_Real TolV, const Handle(Extrema_GenExtPS)& theExtPS = NULL); //! It calculates all the distances between a point //! from gp and a SurfacePtr from Adaptor3d. - Standard_EXPORT Extrema_ExtPRevS(const gp_Pnt& P, const Handle(GeomAdaptor_HSurfaceOfRevolution)& S, const Standard_Real TolU, const Standard_Real TolV); + //! theExtPS is used to compute the solutions in case + //! it cannot be found analytically. + Standard_EXPORT Extrema_ExtPRevS(const gp_Pnt& P, const Handle(GeomAdaptor_HSurfaceOfRevolution)& S, const Standard_Real TolU, const Standard_Real TolV, const Handle(Extrema_GenExtPS)& theExtPS = NULL); Standard_EXPORT void Initialize (const Handle(GeomAdaptor_HSurfaceOfRevolution)& S, const Standard_Real Umin, const Standard_Real Usup, const Standard_Real Vmin, const Standard_Real Vsup, const Standard_Real TolU, const Standard_Real TolV); @@ -90,13 +95,12 @@ private: Standard_Real myvsup; Standard_Real mytolv; gp_Ax2 myPosition; - Extrema_GenExtPS myExtPS; Standard_Boolean myIsAnalyticallyComputable; Standard_Boolean myDone; Standard_Integer myNbExt; Standard_Real mySqDist[8]; Extrema_POnSurf myPoint[8]; - + Handle(Extrema_GenExtPS) myExtPS; }; diff --git a/src/Extrema/Extrema_ExtPS.cxx b/src/Extrema/Extrema_ExtPS.cxx index 4c5046b29f..b38ab1215d 100644 --- a/src/Extrema/Extrema_ExtPS.cxx +++ b/src/Extrema/Extrema_ExtPS.cxx @@ -112,25 +112,25 @@ void Extrema_ExtPS::TreatSolution (const Extrema_POnSurf& PS, Standard_Real U, V; PS.Parameter(U, V); if (myS->IsUPeriodic()) { - U = ElCLib::InPeriod(U, myuinf, myuinf + myS->UPeriod()); + U = ElCLib::InPeriod(U, myLocUMin, myLocUMin + myS->UPeriod()); // Handle trimmed surfaces. - if (U > myusup + mytolu) + if (U > myLocUMax + mytolu) U -= myS->UPeriod(); - if (U < myuinf - mytolu) + if (U < myLocUMin - mytolu) U += myS->UPeriod(); } if (myS->IsVPeriodic()) { - V = ElCLib::InPeriod(V, myvinf, myvinf + myS->VPeriod()); + V = ElCLib::InPeriod(V, myLocVMin, myLocVMin + myS->VPeriod()); // Handle trimmed surfaces. - if (V > myvsup + mytolv) + if (V > myLocVMax + mytolv) V -= myS->VPeriod(); - if (V < myvinf - mytolv) + if (V < myLocVMin - mytolv) V += myS->VPeriod(); } - if ((myuinf-U) <= mytolu && (U-myusup) <= mytolu && - (myvinf-V) <= mytolv && (V-myvsup) <= mytolv) { + if ((myLocUMin-U) <= mytolu && (U-myLocUMax) <= mytolu && + (myLocVMin-V) <= mytolv && (V-myLocVMax) <= mytolv) { myPoints.Append(Extrema_POnSurf (U, V, PS.Value())); mySqDist.Append(Val); } @@ -169,12 +169,8 @@ Extrema_ExtPS::Extrema_ExtPS (const gp_Pnt& theP, const Adaptor3d_Surface& theS, const Standard_Real theTolU, const Standard_Real theTolV, - const Extrema_ExtFlag theF, - const Extrema_ExtAlgo theA) + const Extrema_ExtFlag theTarget) { - myExtPS.SetFlag (theF); - myExtPS.SetAlgo (theA); - Initialize (theS, theS.FirstUParameter(), theS.LastUParameter(), @@ -183,6 +179,8 @@ Extrema_ExtPS::Extrema_ExtPS (const gp_Pnt& theP, theTolU, theTolV); + myExtPS->SetTarget (theTarget); + Perform (theP); } @@ -199,12 +197,8 @@ Extrema_ExtPS::Extrema_ExtPS (const gp_Pnt& theP, const Standard_Real theVsup, const Standard_Real theTolU, const Standard_Real theTolV, - const Extrema_ExtFlag theF, - const Extrema_ExtAlgo theA) + const Extrema_ExtFlag theTarget) { - myExtPS.SetFlag (theF); - myExtPS.SetAlgo (theA); - Initialize (theS, theUinf, theUsup, @@ -213,6 +207,8 @@ Extrema_ExtPS::Extrema_ExtPS (const gp_Pnt& theP, theTolU, theTolV); + myExtPS->SetTarget (theTarget); + Perform (theP); } @@ -241,6 +237,11 @@ void Extrema_ExtPS::Initialize (const Adaptor3d_Surface& theS, if (Precision::IsNegativeInfinite(myvinf)) myvinf = -1e10; if (Precision::IsPositiveInfinite(myvsup)) myvsup = 1e10; + myLocUMin = myuinf; + myLocUMax = myusup; + myLocVMin = myvinf; + myLocVMax = myvsup; + mytolu = theTolU; mytolv = theTolV; mytype = myS->GetType(); @@ -263,7 +264,10 @@ void Extrema_ExtPS::Initialize (const Adaptor3d_Surface& theS, if(bUIsoIsDeg) nbU = 300; if(bVIsoIsDeg) nbV = 300; - myExtPS.Initialize(*myS, nbU, nbV, myuinf, myusup, myvinf, myvsup, mytolu, mytolv); + if (myExtPS.IsNull()) + myExtPS = new Extrema_GenExtPS(); + + myExtPS->Initialize(*myS, nbU, nbV, myuinf, myusup, myvinf, myvsup, mytolu, mytolv); myExtPExtS.Nullify(); myExtPRevS.Nullify(); @@ -273,12 +277,29 @@ void Extrema_ExtPS::Initialize (const Adaptor3d_Surface& theS, //function : Perform //purpose : //======================================================================= +void Extrema_ExtPS::Perform (const gp_Pnt& thePoint) +{ + Perform (thePoint, myuinf, myusup, myvinf, myvsup); +} -void Extrema_ExtPS::Perform(const gp_Pnt& thePoint) +//======================================================================= +//function : Perform +//purpose : +//======================================================================= +void Extrema_ExtPS::Perform (const gp_Pnt& thePoint, + const Standard_Real theLocUMin, + const Standard_Real theLocUMax, + const Standard_Real theLocVMin, + const Standard_Real theLocVMax) { myPoints.Clear(); mySqDist.Clear(); + myLocUMin = Max (theLocUMin, myuinf); + myLocUMax = Min (theLocUMax, myusup); + myLocVMin = Max (theLocVMin, myvinf); + myLocVMax = Min (theLocVMax, myvsup); + switch (mytype) { case GeomAbs_Cylinder: @@ -304,7 +325,7 @@ void Extrema_ExtPS::Perform(const gp_Pnt& thePoint) Handle(GeomAdaptor_HSurfaceOfLinearExtrusion) aS (new GeomAdaptor_HSurfaceOfLinearExtrusion ( GeomAdaptor_SurfaceOfLinearExtrusion (myS->BasisCurve(), myS->Direction()))); - myExtPExtS = new Extrema_ExtPExtS (thePoint, aS, myuinf, myusup, myvinf, myvsup, mytolu, mytolv); + myExtPExtS = new Extrema_ExtPExtS (thePoint, aS, myuinf, myusup, myvinf, myvsup, mytolu, mytolv, myExtPS); } else { @@ -330,7 +351,7 @@ void Extrema_ExtPS::Perform(const gp_Pnt& thePoint) Handle(GeomAdaptor_HSurfaceOfRevolution) aS (new GeomAdaptor_HSurfaceOfRevolution ( GeomAdaptor_SurfaceOfRevolution (myS->BasisCurve(), myS->AxeOfRevolution()))); - myExtPRevS = new Extrema_ExtPRevS (thePoint, aS, myuinf, myusup, myvinf, myvsup, mytolu, mytolv); + myExtPRevS = new Extrema_ExtPRevS (thePoint, aS, myuinf, myusup, myvinf, myvsup, mytolu, mytolv, myExtPS); } else { @@ -351,13 +372,13 @@ void Extrema_ExtPS::Perform(const gp_Pnt& thePoint) default: { - myExtPS.Perform (thePoint); - myDone = myExtPS.IsDone(); + myExtPS->Perform (thePoint, myLocUMin, myLocUMax, myLocVMin, myLocVMax); + myDone = myExtPS->IsDone(); if (myDone) { - for (Standard_Integer anIdx = 1; anIdx <= myExtPS.NbExt(); ++anIdx) + for (Standard_Integer anIdx = 1; anIdx <= myExtPS->NbExt(); ++anIdx) { - TreatSolution (myExtPS.Point (anIdx), myExtPS.SquareDistance (anIdx)); + TreatSolution (myExtPS->Point (anIdx), myExtPS->SquareDistance (anIdx)); } } return; @@ -423,10 +444,8 @@ void Extrema_ExtPS::TrimmedSquareDistances(Standard_Real& dUfVf, void Extrema_ExtPS::SetFlag(const Extrema_ExtFlag F) { - myExtPS.SetFlag(F); -} + if (myExtPS.IsNull()) + myExtPS = new Extrema_GenExtPS(); -void Extrema_ExtPS::SetAlgo(const Extrema_ExtAlgo A) -{ - myExtPS.SetAlgo(A); + myExtPS->SetTarget(F); } diff --git a/src/Extrema/Extrema_ExtPS.hxx b/src/Extrema/Extrema_ExtPS.hxx index 18dada3651..41837021a0 100644 --- a/src/Extrema/Extrema_ExtPS.hxx +++ b/src/Extrema/Extrema_ExtPS.hxx @@ -31,7 +31,6 @@ #include #include #include -#include #include class Extrema_ExtPExtS; class Extrema_ExtPRevS; @@ -63,7 +62,11 @@ public: //! TolU et TolV are used to determine the conditions //! to stop the iterations; at the iteration number n: //! (Un - Un-1) < TolU and (Vn - Vn-1) < TolV . - Standard_EXPORT Extrema_ExtPS(const gp_Pnt& P, const Adaptor3d_Surface& S, const Standard_Real TolU, const Standard_Real TolV, const Extrema_ExtFlag F = Extrema_ExtFlag_MINMAX, const Extrema_ExtAlgo A = Extrema_ExtAlgo_Grad); + Standard_EXPORT Extrema_ExtPS(const gp_Pnt& P, + const Adaptor3d_Surface& S, + const Standard_Real TolU, + const Standard_Real TolV, + const Extrema_ExtFlag F = Extrema_ExtFlag_MINMAX); //! It calculates all the distances. //! NbU and NbV are used to locate the close points @@ -73,16 +76,39 @@ public: //! TolU et TolV are used to determine the conditions //! to stop the iterations; at the iteration number n: //! (Un - Un-1) < TolU and (Vn - Vn-1) < TolV . - Standard_EXPORT Extrema_ExtPS(const gp_Pnt& P, const Adaptor3d_Surface& S, const Standard_Real Uinf, const Standard_Real Usup, const Standard_Real Vinf, const Standard_Real Vsup, const Standard_Real TolU, const Standard_Real TolV, const Extrema_ExtFlag F = Extrema_ExtFlag_MINMAX, const Extrema_ExtAlgo A = Extrema_ExtAlgo_Grad); + Standard_EXPORT Extrema_ExtPS(const gp_Pnt& P, + const Adaptor3d_Surface& S, + const Standard_Real Uinf, + const Standard_Real Usup, + const Standard_Real Vinf, + const Standard_Real Vsup, + const Standard_Real TolU, + const Standard_Real TolV, + const Extrema_ExtFlag F = Extrema_ExtFlag_MINMAX); //! Initializes the fields of the algorithm. - Standard_EXPORT void Initialize (const Adaptor3d_Surface& S, const Standard_Real Uinf, const Standard_Real Usup, const Standard_Real Vinf, const Standard_Real Vsup, const Standard_Real TolU, const Standard_Real TolV); + Standard_EXPORT void Initialize (const Adaptor3d_Surface& S, + const Standard_Real Uinf, + const Standard_Real Usup, + const Standard_Real Vinf, + const Standard_Real Vsup, + const Standard_Real TolU, + const Standard_Real TolV); //! Computes the distances. //! An exception is raised if the fieds have not been //! initialized. Standard_EXPORT void Perform (const gp_Pnt& P); + //! Performs localized extrema search. + //! The solution to be found in the given parametric space, which + //! is required to be inside the initialized parametric space. + Standard_EXPORT void Perform (const gp_Pnt& P, + const Standard_Real theLocUMin, + const Standard_Real theLocUMax, + const Standard_Real theLocVMin, + const Standard_Real theLocVMax); + //! Returns True if the distances are found. Standard_EXPORT Standard_Boolean IsDone() const; @@ -107,9 +133,6 @@ public: Standard_EXPORT void TrimmedSquareDistances (Standard_Real& dUfVf, Standard_Real& dUfVl, Standard_Real& dUlVf, Standard_Real& dUlVl, gp_Pnt& PUfVf, gp_Pnt& PUfVl, gp_Pnt& PUlVf, gp_Pnt& PUlVl) const; Standard_EXPORT void SetFlag (const Extrema_ExtFlag F); - - Standard_EXPORT void SetAlgo (const Extrema_ExtAlgo A); - @@ -130,7 +153,7 @@ private: Adaptor3d_SurfacePtr myS; Standard_Boolean myDone; Extrema_ExtPElS myExtPElS; - Extrema_GenExtPS myExtPS; + Handle(Extrema_GenExtPS) myExtPS; Extrema_SequenceOfPOnSurf myPoints; Standard_Real myuinf; Standard_Real myusup; @@ -138,6 +161,10 @@ private: Standard_Real myvsup; Standard_Real mytolu; Standard_Real mytolv; + Standard_Real myLocUMin; //!< Localized parametric space boundary (required to be inside the main parametric space) + Standard_Real myLocUMax; //!< Localized parametric space boundary (required to be inside the main parametric space) + Standard_Real myLocVMin; //!< Localized parametric space boundary (required to be inside the main parametric space) + Standard_Real myLocVMax; //!< Localized parametric space boundary (required to be inside the main parametric space) Standard_Real d11; Standard_Real d12; Standard_Real d21; diff --git a/src/Extrema/Extrema_FuncPSNorm.cxx b/src/Extrema/Extrema_FuncPSNorm.cxx index d73d0b9740..023becee1d 100644 --- a/src/Extrema/Extrema_FuncPSNorm.cxx +++ b/src/Extrema/Extrema_FuncPSNorm.cxx @@ -25,25 +25,31 @@ #include #include -Extrema_FuncPSNorm::Extrema_FuncPSNorm () -: myS(NULL), +Extrema_FuncPSNorm::Extrema_FuncPSNorm() + : + myS(NULL), myU(0.0), - myV(0.0) + myV(0.0), + myPinit (Standard_False), + mySinit (Standard_False), + myTarget (Extrema_ExtFlag_MINMAX), + myBestSqDistance (-1) { - myPinit = Standard_False; - mySinit = Standard_False; } //============================================================================= Extrema_FuncPSNorm::Extrema_FuncPSNorm (const gp_Pnt& P, - const Adaptor3d_Surface& S) -: myU(0.0), - myV(0.0) + const Adaptor3d_Surface& S) + : + myP (P), + myS ((Adaptor3d_SurfacePtr)&S), + myU(0.0), + myV(0.0), + myPinit (Standard_True), + mySinit (Standard_True), + myTarget (Extrema_ExtFlag_MINMAX), + myBestSqDistance (-1) { - myP = P; - myS = (Adaptor3d_SurfacePtr)&S; - myPinit = Standard_True; - mySinit = Standard_True; } //============================================================================= @@ -51,18 +57,23 @@ void Extrema_FuncPSNorm::Initialize(const Adaptor3d_Surface& S) { myS = (Adaptor3d_SurfacePtr)&S; mySinit = Standard_True; - myPoint.Clear(); - mySqDist.Clear(); + myPoints.clear(); + mySqDistances.clear(); + myTarget = Extrema_ExtFlag_MINMAX; + myBestSqDistance = -1; } //============================================================================= -void Extrema_FuncPSNorm::SetPoint(const gp_Pnt& P) +void Extrema_FuncPSNorm::SetPoint (const gp_Pnt& P, + const Extrema_ExtFlag theTarget) { myP = P; myPinit = Standard_True; - myPoint.Clear(); - mySqDist.Clear(); + myTarget = theTarget; + myBestSqDistance = (myTarget == Extrema_ExtFlag_MIN ? RealLast() : RealFirst()); + myPoints.clear(); + mySqDistances.clear(); } //============================================================================= @@ -124,45 +135,66 @@ Standard_Boolean Extrema_FuncPSNorm::Values (const math_Vector& UV, return Standard_True; } -//============================================================================= -Standard_Integer Extrema_FuncPSNorm::GetStateNumber () +//============================================================================= +Standard_Integer Extrema_FuncPSNorm::GetStateNumber() { if (!myPinit || !mySinit) throw Standard_TypeMismatch(); - //comparison of solution with previous solutions - Standard_Integer i = 1, nbSol = mySqDist.Length(); - Standard_Real tol2d = Precision::PConfusion() * Precision::PConfusion(); - - for( ; i <= nbSol; i++) + + Standard_Real aNewSqDist = myPs.SquareDistance (myP); + if ((myTarget == Extrema_ExtFlag_MIN && aNewSqDist > myBestSqDistance) || + (myTarget == Extrema_ExtFlag_MAX && aNewSqDist < myBestSqDistance)) + return 0; + myBestSqDistance = aNewSqDist; + + // Comparison of solution with previous solutions + Standard_Real tol2d = Precision::SquarePConfusion(); + std::size_t i = 0, nbSol = mySqDistances.size(); + for (; i < nbSol; i++) { Standard_Real aU, aV; - myPoint(i).Parameter(aU, aV); - if( ((myU - aU ) * (myU - aU ) + (myV - aV ) * (myV - aV )) <= tol2d ) + Extrema_POnSurf& aPOnSurf = myPoints[i]; + aPOnSurf.Parameter (aU, aV); + if (((myU - aU) * (myU - aU) + (myV - aV) * (myV - aV)) <= tol2d) + { + // The points are almost the same in the parametric space. + if (myTarget != Extrema_ExtFlag_MINMAX) + { + // Check if new solution gives better distance than the existing solution. + Standard_Real& anOldSqDist = mySqDistances[i]; + if ((myTarget == Extrema_ExtFlag_MIN && aNewSqDist < anOldSqDist) || + (myTarget == Extrema_ExtFlag_MAX && aNewSqDist > anOldSqDist)) + { + aPOnSurf.SetParameters (myU, myV, myPs); + anOldSqDist = aNewSqDist; + } + } break; + } } - if( i <= nbSol) - return 0; - mySqDist.Append(myPs.SquareDistance(myP)); - myPoint.Append(Extrema_POnSurf(myU,myV,myPs)); + if (i < nbSol) + return 0; + mySqDistances.push_back (aNewSqDist); + myPoints.push_back (Extrema_POnSurf (myU, myV, myPs)); return 0; } //============================================================================= Standard_Integer Extrema_FuncPSNorm::NbExt () const { - return mySqDist.Length(); + return static_cast(mySqDistances.size()); } //============================================================================= Standard_Real Extrema_FuncPSNorm::SquareDistance (const Standard_Integer N) const { if (!myPinit || !mySinit) throw Standard_TypeMismatch(); - return mySqDist.Value(N); + return mySqDistances [N - 1]; } //============================================================================= const Extrema_POnSurf& Extrema_FuncPSNorm::Point (const Standard_Integer N) const { if (!myPinit || !mySinit) throw Standard_TypeMismatch(); - return myPoint.Value(N); + return myPoints [N - 1]; } diff --git a/src/Extrema/Extrema_FuncPSNorm.hxx b/src/Extrema/Extrema_FuncPSNorm.hxx index 275f0f249f..c7513fcaa1 100644 --- a/src/Extrema/Extrema_FuncPSNorm.hxx +++ b/src/Extrema/Extrema_FuncPSNorm.hxx @@ -23,12 +23,12 @@ #include #include #include -#include -#include +#include #include #include #include #include +#include class Standard_OutOfRange; class gp_Pnt; class Adaptor3d_Surface; @@ -71,8 +71,10 @@ public: //! sets the field mysurf of the function. Standard_EXPORT void Initialize (const Adaptor3d_Surface& S); - //! sets the field mysurf of the function. - Standard_EXPORT void SetPoint (const gp_Pnt& P); + //! Initializes the function with the point and + //! target (MIN, MAX or MINMAX). MINMAX is used as default target. + Standard_EXPORT void SetPoint (const gp_Pnt& P, + const Extrema_ExtFlag theTarget = Extrema_ExtFlag_MINMAX); Standard_EXPORT Standard_Integer NbVariables() const Standard_OVERRIDE; @@ -99,6 +101,19 @@ public: //! Returns the Nth extremum. Standard_EXPORT const Extrema_POnSurf& Point (const Standard_Integer N) const; + //! Returns the target (MIN, MAX or MINMAX). + Extrema_ExtFlag Target() const + { + return myTarget; + } + + //! Returns the best (min or max, depending on the mode) found + //! square distance. Does not make sense for MINMAX mode. + Standard_Real BestSquareDistance() const + { + return myBestSqDistance; + } + private: gp_Pnt myP; @@ -106,9 +121,11 @@ private: Standard_Real myU; Standard_Real myV; gp_Pnt myPs; - TColStd_SequenceOfReal mySqDist; - Extrema_SequenceOfPOnSurf myPoint; + std::vector mySqDistances; + std::vector myPoints; Standard_Boolean myPinit; Standard_Boolean mySinit; + Extrema_ExtFlag myTarget; + Standard_Real myBestSqDistance; }; #endif // _Extrema_FunctPSNorm_HeaderFile diff --git a/src/Extrema/Extrema_GenExtPS.cxx b/src/Extrema/Extrema_GenExtPS.cxx index 5114c045a3..5d764cbf1f 100644 --- a/src/Extrema/Extrema_GenExtPS.cxx +++ b/src/Extrema/Extrema_GenExtPS.cxx @@ -1,5 +1,4 @@ // Created on: 1995-07-18 -// Created by: Modelistation // Copyright (c) 1995-1999 Matra Datavision // Copyright (c) 1999-2014 OPEN CASCADE SAS // @@ -14,980 +13,1060 @@ // Alternatively, this file may be used under the terms of Open CASCADE // commercial license or contractual agreement. -// Modified by skv - Thu Sep 30 15:21:07 2004 OCC593 +#include -#include #include #include #include -#include -#include -#include -#include -#include -#include -#include -#include +#include +#include +#include +#include +#include +#include #include #include #include #include -#include -#include -#include -#include #include -#include -#include -#include #include -#include -#include -#include -#include -#include - -//IMPLEMENT_HARRAY1(Extrema_HArray1OfSphere) -class Bnd_SphereUBTreeSelector : public Extrema_UBTreeOfSphere::Selector +#include +#include + +IMPLEMENT_STANDARD_RTTIEXT (Extrema_GenExtPS, Standard_Transient) + +// Static methods definition +namespace { - public: + //======================================================================= + //function : fillParams + //purpose : + //======================================================================= + static void fillParams (const TColStd_Array1OfReal& theKnots, + const Standard_Integer theDegree, + const Standard_Real theParMin, + const Standard_Real theParMax, + Standard_Integer theNbSamples, + Handle (TColStd_HArray1OfReal)& theParams) + { + NCollection_Vector aParams; + GCPnts::FillParams (theKnots, theDegree, theParMin, theParMax, aParams); + Standard_Integer nbPar = aParams.Length(); + + // In case of an insufficient number of points the grid will be built later + if (nbPar < theNbSamples) + return; + + theParams = new TColStd_HArray1OfReal (1, nbPar); + for (Standard_Integer i = 0; i < nbPar; i++) + theParams->SetValue (i + 1, aParams (i)); + } - Bnd_SphereUBTreeSelector (const Handle(Bnd_HArray1OfSphere)& theSphereArray, -Bnd_Sphere& theSol) - : myXYZ(0,0,0), - mySphereArray(theSphereArray), - mySol(theSol) + //======================================================================= + //function : fillParams + //purpose : + //======================================================================= + static void fillParams (Standard_Real theParMin, + Standard_Real theParMax, + Handle (TColStd_HArray1OfReal)& theParams, + Standard_Integer theNbSamples) { + Standard_Real PasU = theParMax - theParMin; + Standard_Real U0 = PasU / theNbSamples / 100.; + PasU = (PasU - U0) / (theNbSamples - 1); + U0 = U0 / 2. + theParMin; + theParams = new TColStd_HArray1OfReal (1, theNbSamples); + Standard_Real U = U0; + for (int NoU = 1; NoU <= theNbSamples; NoU++, U += PasU) + theParams->SetValue (NoU, U); } +} - void DefineCheckPoint( const gp_Pnt& theXYZ ) - { myXYZ = theXYZ; } +//======================================================================= +//function : Extrema_GenExtPS +//purpose : +//======================================================================= +Extrema_GenExtPS::Extrema_GenExtPS() + : + myUMin (RealLast()), + myUMax (RealFirst()), + myVMin (RealLast()), + myVMax (RealFirst()), + myNbUSamples (0), + myNbVSamples (0), + myTolU (Precision::PConfusion()), + myTolV (Precision::PConfusion()), + myLocUMin (RealLast()), + myLocUMax (RealFirst()), + myLocVMin (RealLast()), + myLocVMax (RealFirst()), + myTarget (Extrema_ExtFlag_MINMAX), + mySqDistance (-1), + myIsDone (Standard_False) +{ +} - Bnd_Sphere& Sphere() const - { return mySol; } +//======================================================================= +//function : Extrema_GenExtPS +//purpose : +//======================================================================= +Extrema_GenExtPS::Extrema_GenExtPS (const gp_Pnt& theP, + const Adaptor3d_Surface& theS, + const Standard_Integer theNbU, + const Standard_Integer theNbV, + const Standard_Real theTolU, + const Standard_Real theTolV, + const Extrema_ExtFlag theTarget) + : + myNbUSamples (theNbU), + myNbVSamples (theNbV), + myTolU (theTolU), + myTolV (theTolV), + myTarget (theTarget), + mySqDistance (-1), + myIsDone (Standard_False) +{ + Initialize (theS, theNbU, theNbV, theTolU, theTolV); + Perform (theP); +} - virtual Standard_Boolean Reject( const Bnd_Sphere &theBnd ) const = 0; - - virtual Standard_Boolean Accept(const Standard_Integer& theObj) = 0; - protected: - gp_Pnt myXYZ; - const Handle(Bnd_HArray1OfSphere)& mySphereArray; - Bnd_Sphere& mySol; - private: - void operator= (const Bnd_SphereUBTreeSelector&); +//======================================================================= +//function : Extrema_GenExtPS +//purpose : +//======================================================================= +Extrema_GenExtPS::Extrema_GenExtPS (const gp_Pnt& theP, + const Adaptor3d_Surface& theS, + const Standard_Integer theNbU, + const Standard_Integer theNbV, + const Standard_Real theUMin, + const Standard_Real theUMax, + const Standard_Real theVMin, + const Standard_Real theVMax, + const Standard_Real theTolU, + const Standard_Real theTolV, + const Extrema_ExtFlag theTarget) + : + myUMin (theUMin), + myUMax (theUMax), + myVMin (theVMin), + myVMax (theVMax), + myNbUSamples (theNbU), + myNbVSamples (theNbV), + myTolU (theTolU), + myTolV (theTolV), + myTarget (theTarget), + mySqDistance (-1), + myIsDone (Standard_False) +{ + Initialize (theS, theNbU, theNbV, theUMin, theUMax, theVMin, theVMax, theTolU, theTolV); + Perform (theP); +} -}; +//======================================================================= +//function : Initialize +//purpose : +//======================================================================= +void Extrema_GenExtPS::Initialize (const Adaptor3d_Surface& theS, + const Standard_Integer theNbU, + const Standard_Integer theNbV, + const Standard_Real theTolU, + const Standard_Real theTolV) +{ + Initialize (theS, + theNbU, theNbV, + theS.FirstUParameter(), theS.LastUParameter(), + theS.FirstVParameter(), theS.LastVParameter(), + theTolU, theTolV); +} -class Bnd_SphereUBTreeSelectorMin : public Bnd_SphereUBTreeSelector +//======================================================================= +//function : Initialize +//purpose : +//======================================================================= +void Extrema_GenExtPS::Initialize (const Adaptor3d_Surface& theS, + const Standard_Integer theNbU, + const Standard_Integer theNbV, + const Standard_Real theUMin, + const Standard_Real theUMax, + const Standard_Real theVMin, + const Standard_Real theVMax, + const Standard_Real theTolU, + const Standard_Real theTolV) { -public: - Bnd_SphereUBTreeSelectorMin (const Handle(Bnd_HArray1OfSphere)& theSphereArray, - Bnd_Sphere& theSol) - : Bnd_SphereUBTreeSelector(theSphereArray, theSol), - myMinDist(RealLast()) - {} - - void SetMinDist( const Standard_Real theMinDist ) - { myMinDist = theMinDist; } - - Standard_Real MinDist() const - { return myMinDist; } - - Standard_Boolean Reject( const Bnd_Sphere &theBnd ) const - { - Bnd_SphereUBTreeSelectorMin* me = - const_cast(this); - // myMinDist is decreased each time a nearer object is found - return theBnd.IsOut( myXYZ.XYZ(), me->myMinDist ); + myS = (Adaptor3d_SurfacePtr)&theS; + myUMin = theUMin; + myUMax = theUMax; + myVMin = theVMin; + myVMax = theVMax; + myNbUSamples = theNbU; + myNbVSamples = theNbV; + myTolU = theTolU; + myTolV = theTolV; + + myLocUMin = myUMin; + myLocUMax = myUMax; + myLocVMin = myVMin; + myLocVMax = myVMax; + + if (myNbUSamples < 2 || myNbVSamples < 2) + { + throw Standard_OutOfRange ("Extrema_GenExtPS::Initialize - number of samples is too small"); } - Standard_Boolean Accept(const Standard_Integer&); + myF.Initialize (theS); -private: - Standard_Real myMinDist; -}; + myBVHBoxSet.Nullify(); + myUParams.Nullify(); + myVParams.Nullify(); +} -Standard_Boolean Bnd_SphereUBTreeSelectorMin::Accept(const Standard_Integer& theInd) +//======================================================================= +//function : Perform +//purpose : +//======================================================================= +void Extrema_GenExtPS::Perform (const gp_Pnt& thePoint) { - const Bnd_Sphere& aSph = mySphereArray->Value(theInd); - Standard_Real aCurDist; + Perform (thePoint, myUMin, myUMax, myVMin, myVMax); +} -// if ( (aCurDist = aSph.SquareDistance(myXYZ.XYZ())) < mySol.SquareDistance(myXYZ.XYZ()) ) - if ( (aCurDist = aSph.Distance(myXYZ.XYZ())) < mySol.Distance(myXYZ.XYZ()) ) - { - mySol = aSph; - if ( aCurDist < myMinDist ) - myMinDist = aCurDist; +//======================================================================= +//function : Perform +//purpose : +//======================================================================= +void Extrema_GenExtPS::Perform (const gp_Pnt& thePoint, + const Standard_Real theUMin, + const Standard_Real theUMax, + const Standard_Real theVMin, + const Standard_Real theVMax) +{ + myIsDone = Standard_False; + myPoint = thePoint; + myF.SetPoint (thePoint, myTarget); + mySolutions.clear(); - return Standard_True; - } + myLocUMin = Max (theUMin, myUMin); + myLocUMax = Min (theUMax, myUMax); + myLocVMin = Max (theVMin, myVMin); + myLocVMax = Min (theVMax, myVMax); - return Standard_False; -} + if (myUParams.IsNull() || myVParams.IsNull()) + { + // Prepare surface sampling + BuildGrid(); + } -class Bnd_SphereUBTreeSelectorMax : public Bnd_SphereUBTreeSelector -{ -public: - Bnd_SphereUBTreeSelectorMax (const Handle(Bnd_HArray1OfSphere)& theSphereArray, - Bnd_Sphere& theSol) - : Bnd_SphereUBTreeSelector(theSphereArray, theSol), - myMaxDist(0) - {} - - void SetMaxDist( const Standard_Real theMaxDist ) - { myMaxDist = theMaxDist; } - - Standard_Real MaxDist() const - { return myMaxDist; } - - Standard_Boolean Reject( const Bnd_Sphere &theBnd ) const - { - Bnd_SphereUBTreeSelectorMax* me = - const_cast(this); - // myMaxDist is decreased each time a nearer object is found - return theBnd.IsOut( myXYZ.XYZ(), me->myMaxDist ); + if (myBVHBoxSet.IsNull() || myBVHBoxSet->IsDirty()) + { + BuildTree(); } - Standard_Boolean Accept(const Standard_Integer&); + if (myTarget == Extrema_ExtFlag_MIN) + mySqDistance = RealLast(); + else if (myTarget == Extrema_ExtFlag_MAX) + mySqDistance = -1; -private: - Standard_Real myMaxDist; -}; + // Fill Square distances with default values + for (int iU = 0; iU <= myNbUSamples + 1; ++iU) + { + for (int iV = 0; iV <= myNbVSamples + 1; ++iV) + { + myPoints->ChangeValue (iU, iV).SetSqrDistance (-1.); -Standard_Boolean Bnd_SphereUBTreeSelectorMax::Accept(const Standard_Integer& theInd) -{ - const Bnd_Sphere& aSph = mySphereArray->Value(theInd); - Standard_Real aCurDist; + if (iU <= myNbUSamples && iV <= myNbVSamples) + myFacePntParams->ChangeValue (iU, iV).SetSqrDistance (-1.); -// if ( (aCurDist = aSph.SquareDistance(myXYZ.XYZ())) > mySol.SquareDistance(myXYZ.XYZ()) ) - if ( (aCurDist = aSph.Distance(myXYZ.XYZ())) > mySol.Distance(myXYZ.XYZ()) ) - { - mySol = aSph; - if ( aCurDist > myMaxDist ) - myMaxDist = aCurDist; + if (iU > 0 && iU <= myNbUSamples && iV > 0 && iV <= myNbVSamples) + { + if (iU < myNbUSamples) + myUEdgePntParams->ChangeValue (iU, iV).SetSqrDistance (-1.); + if (iV < myNbVSamples) + myVEdgePntParams->ChangeValue (iU, iV).SetSqrDistance (-1.); + } + } + } - return Standard_True; + if (myTarget == Extrema_ExtFlag_MIN || myTarget == Extrema_ExtFlag_MINMAX) + { + // Fill boundary with RealLast square distance. + for (int iV = 0; iV <= myNbVSamples; ++iV) + { + myFacePntParams->ChangeValue (0, iV).SetSqrDistance (RealLast()); + myFacePntParams->ChangeValue (myNbUSamples, iV).SetSqrDistance (RealLast()); } - return Standard_False; -} + for (int iU = 1; iU < myNbUSamples; ++iU) + { + myFacePntParams->ChangeValue (iU, 0).SetSqrDistance (RealLast()); + myFacePntParams->ChangeValue (iU, myNbVSamples).SetSqrDistance (RealLast()); + } + } -//============================================================================= - -/*----------------------------------------------------------------------------- -Function: - Find all extremum distances between point P and surface - S using sampling (NbU,NbV). - -Method: - The algorithm bases on the hypothesis that sampling is precise enough, - if there exist N extreme distances between the point and the surface, - so there also exist N extrema between the point and the grid. - So, the algorithm consists in starting from extrema of the grid to find the - extrema of the surface. - The extrema are calculated by the algorithm math_FunctionSetRoot with the - following arguments: - - F: Extrema_FuncExtPS created from P and S, - - UV: math_Vector the components which of are parameters of the extremum on the - grid, - - Tol: Min(TolU,TolV), (Prov.:math_FunctionSetRoot does not autorize a vector) - - UVinf: math_Vector the components which of are lower limits of u and v, - - UVsup: math_Vector the components which of are upper limits of u and v. - -Processing: - a- Creation of the table of distances (TbDist(0,NbU+1,0,NbV+1)): - The table is expanded at will; lines 0 and NbU+1 and - columns 0 and NbV+1 are initialized at RealFirst() or RealLast() - to simplify the tests carried out at stage b - (there is no need to test if the point is on border of the grid). - b- Calculation of extrema: - First the minimums and then the maximums are found. These 2 procedured - pass in a similar way: - b.a- Initialization: - - 'borders' of table TbDist (RealLast() in case of minimums - and RealLast() in case of maximums), - - table TbSel(0,NbU+1,0,NbV+1) of selection of points for - calculation of local extremum (0). When a point will selected, - it will not be selectable, as well as the ajacent points - (8 at least). The corresponding addresses will be set to 1. - b.b- Calculation of minimums (or maximums): - All distances from table TbDist are parsed in a loop: - - search minimum (or maximum) in the grid, - - calculate extremum on the surface, - - update table TbSel. ------------------------------------------------------------------------------*/ + if (myTarget == Extrema_ExtFlag_MINMAX) + { + for (int iU = 1; iU <= myNbUSamples; ++iU) + { + for (int iV = 1; iV <= myNbVSamples; ++iV) + { + Extrema_POnSurfParams& aParam = myPoints->ChangeValue (iU, iV); + aParam.SetSqrDistance (aParam.Value().SquareDistance (thePoint)); + } + } -Extrema_GenExtPS::Extrema_GenExtPS() -: myumin(0.0), - myusup(0.0), - myvmin(0.0), - myvsup(0.0), - myusample(0), - myvsample(0), - mytolu(0.0), - mytolv(0.0), - myS(NULL) -{ - myDone = Standard_False; - myInit = Standard_False; - myFlag = Extrema_ExtFlag_MINMAX; - myAlgo = Extrema_ExtAlgo_Grad; -} + // Perform standard solution search (no tree) + for (Standard_Integer iTarget = 0; iTarget < 2; ++iTarget) + { + const Extrema_ExtFlag aTarget = static_cast (iTarget); + for (Standard_Integer iU = 1; iU <= myNbUSamples; iU++) + { + for (Standard_Integer iV = 1; iV <= myNbVSamples; iV++) + { + FindSolution (iU, iV, aTarget); + } + } + } + // Copy solutions + for (Standard_Integer i = 1; i <= myF.NbExt(); ++i) + { + mySolutions.push_back (Extrema_GenExtPS_ExtPSResult (myF.Point (i), myF.SquareDistance (i))); + } + } + else + { + // Indicator for high-level BVH traverse + SetBVHSet (NULL); + Select (myBVHBoxSet->BVH()); + // Copy solutions + for (Standard_Integer i = 1; i <= myF.NbExt(); ++i) + { + if (Abs (mySqDistance - myF.SquareDistance (i)) < Precision::SquareConfusion()) + mySolutions.push_back (Extrema_GenExtPS_ExtPSResult (myF.Point (i), myF.SquareDistance (i))); + } + } -Extrema_GenExtPS::Extrema_GenExtPS (const gp_Pnt& P, - const Adaptor3d_Surface& S, - const Standard_Integer NbU, - const Standard_Integer NbV, - const Standard_Real TolU, - const Standard_Real TolV, - const Extrema_ExtFlag F, - const Extrema_ExtAlgo A) -: myF (P,S), - myFlag(F), - myAlgo(A) -{ - Initialize(S, NbU, NbV, TolU, TolV); - Perform(P); + // Sort solutions + std::sort (mySolutions.begin(), mySolutions.end()); } -Extrema_GenExtPS::Extrema_GenExtPS (const gp_Pnt& P, - const Adaptor3d_Surface& S, - const Standard_Integer NbU, - const Standard_Integer NbV, - const Standard_Real Umin, - const Standard_Real Usup, - const Standard_Real Vmin, - const Standard_Real Vsup, - const Standard_Real TolU, - const Standard_Real TolV, - const Extrema_ExtFlag F, - const Extrema_ExtAlgo A) -: myF (P,S), - myFlag(F), - myAlgo(A) +//======================================================================= +//function : BuildGrid +//purpose : +//======================================================================= +void Extrema_GenExtPS::BuildGrid() { - Initialize(S, NbU, NbV, Umin, Usup, Vmin, Vsup, TolU, TolV); - Perform(P); -} + GetGridPoints (*myS); + //build grid in other cases + if (myUParams.IsNull()) + { + fillParams (myUMin, myUMax, myUParams, myNbUSamples); + } -void Extrema_GenExtPS::Initialize(const Adaptor3d_Surface& S, - const Standard_Integer NbU, - const Standard_Integer NbV, - const Standard_Real TolU, - const Standard_Real TolV) -{ - myumin = S.FirstUParameter(); - myusup = S.LastUParameter(); - myvmin = S.FirstVParameter(); - myvsup = S.LastVParameter(); - Initialize(S,NbU,NbV,myumin,myusup,myvmin,myvsup,TolU,TolV); -} + if (myVParams.IsNull()) + { + fillParams (myVMin, myVMax, myVParams, myNbVSamples); + } + + myPoints = new Extrema_HArray2OfPOnSurfParams (0, myNbUSamples + 1, 0, myNbVSamples + 1); + for (int iU = 1; iU <= myNbUSamples; iU++) + { + Standard_Real U = myUParams->Value (iU); + for (int iV = 1; iV <= myNbVSamples; iV++) + { + Standard_Real V = myVParams->Value (iV); + gp_Pnt aP = myS->Value (U, V); + Extrema_POnSurfParams aParam (U, V, aP); + aParam.SetElementType (Extrema_Node); + aParam.SetIndices (iU, iV); + myPoints->SetValue (iU, iV, aParam); + } + } + myFacePntParams = new Extrema_HArray2OfPOnSurfParams (0, myNbUSamples, 0, myNbVSamples); -void Extrema_GenExtPS::Initialize(const Adaptor3d_Surface& S, - const Standard_Integer NbU, - const Standard_Integer NbV, - const Standard_Real Umin, - const Standard_Real Usup, - const Standard_Real Vmin, - const Standard_Real Vsup, - const Standard_Real TolU, - const Standard_Real TolV) -{ - myS = (Adaptor3d_SurfacePtr)&S; - myusample = NbU; - myvsample = NbV; - mytolu = TolU; - mytolv = TolV; - myumin = Umin; - myusup = Usup; - myvmin = Vmin; - myvsup = Vsup; - - if ((myusample < 2) || - (myvsample < 2)) { throw Standard_OutOfRange(); } - - myF.Initialize(S); - - mySphereUBTree.Nullify(); - myUParams.Nullify(); - myVParams.Nullify(); - myInit = Standard_False; + myUEdgePntParams = new Extrema_HArray2OfPOnSurfParams (1, myNbUSamples - 1, 1, myNbVSamples); + myVEdgePntParams = new Extrema_HArray2OfPOnSurfParams (1, myNbUSamples, 1, myNbVSamples - 1); } -inline static void fillParams(const TColStd_Array1OfReal& theKnots, - Standard_Integer theDegree, - Standard_Real theParMin, - Standard_Real theParMax, - Handle(TColStd_HArray1OfReal)& theParams, - Standard_Integer theSample) +//======================================================================= +//function : BuildTree +//purpose : +//======================================================================= +void Extrema_GenExtPS::BuildTree() { - NCollection_Vector aParams; - Standard_Integer i = 1; - Standard_Real aPrevPar = theParMin; - aParams.Append(aPrevPar); - //calculation the array of parametric points depending on the knots array variation and degree of given surface - for ( ; i < theKnots.Length() && theKnots(i) < (theParMax - Precision::PConfusion()); i++ ) + // The tree is not required for MINMAX mode + if (myTarget == Extrema_ExtFlag_MINMAX) + return; + + // so fill the tree with elements with empty boxes + if (myBVHBoxSet.IsNull()) { - if ( theKnots(i+1) < theParMin + Precision::PConfusion()) - continue; + // Builder for low-level BVH sets + opencascade::handle > aLBuilder = new BVH_LinearBuilder(); - Standard_Real aStep = (theKnots(i+1) - theKnots(i))/Max(theDegree,2); - Standard_Integer k =1; - for( ; k <= theDegree ; k++) + myBVHBoxSet = new BVH_IndexedBoxSet ( + new BVH_LinearBuilder (BVH_Constants_LeafNodeSizeSingle)); + + // create hierarchy of BVH trees + const Standard_Integer aCoeff = static_cast(Sqrt (Min (myNbUSamples, myNbVSamples))); + const Standard_Integer aNbUT = myNbUSamples / aCoeff; + const Standard_Integer aNbVT = myNbVSamples / aCoeff; + const Standard_Integer aNbU = myNbUSamples / aNbUT; + const Standard_Integer aNbV = myNbVSamples / aNbVT; + const Standard_Integer aSize = aNbU * aNbV; + + myBVHBoxSet->SetSize (aNbUT * aNbVT); + + Standard_Integer U1 = 1, V1 = 1, U2 = 1, V2 = 1; + for (Standard_Integer iUT = 1; iUT <= aNbUT; ++iUT) { - Standard_Real aPar = theKnots(i) + k * aStep; - if(aPar > theParMax - Precision::PConfusion()) - break; - if(aPar > aPrevPar + Precision::PConfusion() ) + U2 = (iUT == aNbUT) ? myNbUSamples : iUT * aNbU; + for (Standard_Integer iVT = 1; iVT <= aNbVT; ++iVT) { - aParams.Append(aPar); - aPrevPar = aPar; + Handle (Extrema_GenExtPS_GridCellBoxSet) aGridSet = new Extrema_GenExtPS_GridCellBoxSet (aLBuilder); + aGridSet->SetSize (aSize); + + V2 = (iVT == aNbVT) ? myNbVSamples : iVT * aNbV; + for (Standard_Integer iU = U1; iU <= U2; ++iU) + { + for (Standard_Integer iV = V1; iV <= V2; ++iV) + { + aGridSet->Add (Extrema_GenExtPS_GridCell (iU, iV), BVH_Box()); + } + } + myBVHBoxSet->Add (Extrema_GenExtPS_LocalizedGrid (U1, U2, V1, V2, aGridSet), BVH_Box()); + V1 = V2 + 1; + } + U1 = U2 + 1; + V1 = 1; + } + } + + if (myBVHBoxSet->IsDirty()) + { + // Fill the tree with the real boxes + const Standard_Integer aNbSets = myBVHBoxSet->Size(); + for (Standard_Integer iSet = 0; iSet < aNbSets; ++iSet) + { + Extrema_GenExtPS_LocalizedGrid aGridSet = myBVHBoxSet->Element (iSet); + + // Box of the set + Bnd_Box aSetBox; + const Standard_Integer aNbCells = aGridSet.CellBoxSet->Size(); + for (Standard_Integer iCell = 0; iCell < aNbCells; ++iCell) + { + const Extrema_GenExtPS_GridCell& aCell = aGridSet.CellBoxSet->Element (iCell); + Standard_Integer iU = aCell.UIndex, iV = aCell.VIndex; + + Standard_Integer aUCoeff = (iU < myNbUSamples) ? 1 : 0; + Standard_Integer aVCoeff = (iV < myNbVSamples) ? 1 : 0; + + // Build box for the cell + Bnd_Box aGridBox; + for (int i = 0; i < 2; ++i) + for (int j = 0; j < 2; ++j) + aGridBox.Add (myPoints->Value (iU + i * aUCoeff, iV + j * aVCoeff).Value()); + aGridBox.Enlarge (Precision::Confusion()); + + const Extrema_POnSurf& aPMin = myPoints->Value (iU, iV); + const Extrema_POnSurf& aPMax = myPoints->Value (iU + aUCoeff, iV + aVCoeff); + + Standard_Real U1, V1, U2, V2; + aPMin.Parameter (U1, V1); + aPMax.Parameter (U2, V2); + + // Enlarge box to make sure the whole cell is covered + if (U1 != U2 || V1 != V2) + { + gp_Pnt aPMid = myS->Value ((U1 + U2) * 0.5, (V1 + V2) * 0.5); + + gp_Vec aDir (aPMin.Value(), aPMax.Value()); + Standard_Real diag = aDir.SquareMagnitude(); + if (diag > gp::Resolution()) + { + aGridBox.Enlarge (gp_Lin (aPMin.Value(), aDir).Distance (aPMid)); + } + else + { + aGridBox.Add (aPMid); + } + } + aGridSet.CellBoxSet->UpdateBox (iCell, Bnd_Tools::Bnd2BVH (aGridBox)); + + aSetBox.Add (aGridBox); } + myBVHBoxSet->UpdateBox (iSet, Bnd_Tools::Bnd2BVH (aSetBox)); } + // Build only high level BVH tree + myBVHBoxSet->Build(); } - aParams.Append(theParMax); - Standard_Integer nbPar = aParams.Length(); - //in case of an insufficient number of points the grid will be built later - if (nbPar < theSample) - return; - theParams = new TColStd_HArray1OfReal(1, nbPar ); - for( i = 0; i < nbPar; i++) - theParams->SetValue(i+1,aParams(i)); } -void Extrema_GenExtPS::GetGridPoints( const Adaptor3d_Surface& theSurf) +//======================================================================= +//function : GetGridPoints +//purpose : +//======================================================================= +void Extrema_GenExtPS::GetGridPoints (const Adaptor3d_Surface& theSurf) { - //creation parametric points for BSpline and Bezier surfaces - //with taking into account of Degree and NbKnots of BSpline or Bezier geometry - if(theSurf.GetType() == GeomAbs_OffsetSurface) - GetGridPoints(theSurf.BasisSurface()->Surface()); - //parametric points for BSpline surfaces - else if( theSurf.GetType() == GeomAbs_BSplineSurface) + // Creation parametric points for BSpline and Bezier surfaces + // taking into account of Degree and NbKnots of BSpline or Bezier geometry + if (theSurf.GetType() == GeomAbs_OffsetSurface) + GetGridPoints (theSurf.BasisSurface()->Surface()); + + // Parametric points for BSpline surfaces + else if (theSurf.GetType() == GeomAbs_BSplineSurface) { - Handle(Geom_BSplineSurface) aBspl = theSurf.BSpline(); - if(!aBspl.IsNull()) + Handle (Geom_BSplineSurface) aBspl = theSurf.BSpline(); + if (!aBspl.IsNull()) { - TColStd_Array1OfReal aUKnots(1, aBspl->NbUKnots()); - aBspl->UKnots( aUKnots); - TColStd_Array1OfReal aVKnots(1, aBspl->NbVKnots()); - aBspl->VKnots( aVKnots); - fillParams(aUKnots,aBspl->UDegree(),myumin, myusup, myUParams, myusample); - fillParams(aVKnots,aBspl->VDegree(),myvmin, myvsup, myVParams, myvsample); + TColStd_Array1OfReal aUKnots (1, aBspl->NbUKnots()); + aBspl->UKnots (aUKnots); + TColStd_Array1OfReal aVKnots (1, aBspl->NbVKnots()); + aBspl->VKnots (aVKnots); + fillParams (aUKnots, aBspl->UDegree(), myUMin, myUMax, myNbUSamples, myUParams); + fillParams (aVKnots, aBspl->VDegree(), myVMin, myVMax, myNbVSamples, myVParams); } } - //calculation parametric points for Bezier surfaces - else if(theSurf.GetType() == GeomAbs_BezierSurface) - { - Handle(Geom_BezierSurface) aBezier = theSurf.Bezier(); - if(aBezier.IsNull()) - return; - - TColStd_Array1OfReal aUKnots(1,2); - TColStd_Array1OfReal aVKnots(1,2); - aBezier->Bounds(aUKnots(1), aUKnots(2), aVKnots(1), aVKnots(2)); - fillParams(aUKnots, aBezier->UDegree(), myumin, myusup, myUParams, myusample); - fillParams(aVKnots, aBezier->VDegree(), myvmin, myvsup, myVParams, myvsample); + // Calculation parametric points for Bezier surfaces + else if (theSurf.GetType() == GeomAbs_BezierSurface) + { + Handle (Geom_BezierSurface) aBezier = theSurf.Bezier(); + if (!aBezier.IsNull()) + { + TColStd_Array1OfReal aUKnots (1, 2); + TColStd_Array1OfReal aVKnots (1, 2); + aBezier->Bounds (aUKnots (1), aUKnots (2), aVKnots (1), aVKnots (2)); + fillParams (aUKnots, aBezier->UDegree(), myUMin, myUMax, myNbUSamples, myUParams); + fillParams (aVKnots, aBezier->VDegree(), myVMin, myVMax, myNbVSamples, myVParams); + } } - //creation points for surfaces based on BSpline or Bezier curves - else if(theSurf.GetType() == GeomAbs_SurfaceOfRevolution || - theSurf.GetType() == GeomAbs_SurfaceOfExtrusion) + + // creation points for surfaces based on BSpline or Bezier curves + else if (theSurf.GetType() == GeomAbs_SurfaceOfRevolution || + theSurf.GetType() == GeomAbs_SurfaceOfExtrusion) { - Handle(TColStd_HArray1OfReal) anArrKnots; + Handle (TColStd_HArray1OfReal) anArrKnots; Standard_Integer aDegree = 0; - if(theSurf.BasisCurve()->Curve().GetType() == GeomAbs_BSplineCurve) + if (theSurf.BasisCurve()->Curve().GetType() == GeomAbs_BSplineCurve) { - Handle(Geom_BSplineCurve) aBspl = theSurf.BasisCurve()->Curve().BSpline(); - if(!aBspl.IsNull()) + Handle (Geom_BSplineCurve) aBspl = theSurf.BasisCurve()->Curve().BSpline(); + if (!aBspl.IsNull()) { - anArrKnots = new TColStd_HArray1OfReal(1,aBspl->NbKnots()); - aBspl->Knots( anArrKnots->ChangeArray1() ); + anArrKnots = new TColStd_HArray1OfReal (1, aBspl->NbKnots()); + aBspl->Knots (anArrKnots->ChangeArray1()); aDegree = aBspl->Degree(); - } - } - if(theSurf.BasisCurve()->Curve().GetType() == GeomAbs_BezierCurve) + if (theSurf.BasisCurve()->Curve().GetType() == GeomAbs_BezierCurve) { - Handle(Geom_BezierCurve) aBez = theSurf.BasisCurve()->Curve().Bezier(); - if(!aBez.IsNull()) + Handle (Geom_BezierCurve) aBez = theSurf.BasisCurve()->Curve().Bezier(); + if (!aBez.IsNull()) { - anArrKnots = new TColStd_HArray1OfReal(1,2); - anArrKnots->SetValue(1, aBez->FirstParameter()); - anArrKnots->SetValue(2, aBez->LastParameter()); + anArrKnots = new TColStd_HArray1OfReal (1, 2); + anArrKnots->SetValue (1, aBez->FirstParameter()); + anArrKnots->SetValue (2, aBez->LastParameter()); aDegree = aBez->Degree(); - + } } - if(anArrKnots.IsNull()) + if (anArrKnots.IsNull()) return; - if( theSurf.GetType() == GeomAbs_SurfaceOfRevolution ) - fillParams( anArrKnots->Array1(), aDegree, myvmin, myvsup, myVParams, myvsample); + if (theSurf.GetType() == GeomAbs_SurfaceOfRevolution) + fillParams (anArrKnots->Array1(), aDegree, myVMin, myVMax, myNbVSamples, myVParams); else - fillParams( anArrKnots->Array1(), aDegree, myumin, myusup, myUParams, myusample); + fillParams (anArrKnots->Array1(), aDegree, myUMin, myUMax, myNbUSamples, myUParams); } - //update the number of points in sample - if(!myUParams.IsNull()) - myusample = myUParams->Length(); - if( !myVParams.IsNull()) - myvsample = myVParams->Length(); - + + // Update the number of points in sample + if (!myUParams.IsNull()) + myNbUSamples = myUParams->Length(); + if (!myVParams.IsNull()) + myNbVSamples = myVParams->Length(); } -/* - * This function computes the point on surface parameters on edge. - * if it coincides with theParam0 or theParam1, it is returned. - */ -const Extrema_POnSurfParams& Extrema_GenExtPS::ComputeEdgeParameters - (const Standard_Boolean IsUEdge, - const Extrema_POnSurfParams &theParam0, - const Extrema_POnSurfParams &theParam1, - const gp_Pnt &thePoint, - const Standard_Real theDiffTol) +//======================================================================= +//function : RejectNode +//purpose : +//======================================================================= +Standard_Boolean Extrema_GenExtPS::RejectNode (const BVH_Vec3d& theCMin, + const BVH_Vec3d& theCMax, + Standard_Real& theDistance) const { - const Standard_Real aSqrDist01 = - theParam0.Value().SquareDistance(theParam1.Value()); + if (myTarget == Extrema_ExtFlag_MINMAX) + return Standard_False; - 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()); + theDistance = (myTarget == Extrema_ExtFlag_MIN) ? + BVH_Tools::PointBoxSquareDistance (BVH_Vec3d (myPoint.X(), myPoint.Y(), myPoint.Z()), theCMin, theCMax) : + BVH_Tools::PointBoxMaxSquareDistance (BVH_Vec3d (myPoint.X(), myPoint.Y(), myPoint.Z()), theCMin, theCMax); - 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]); - } + return RejectMetric (theDistance); +} - myGridParam.SetParameters(aUPar, aVPar, myS->Value(aUPar, aVPar)); - Standard_Integer anIndices[2]; +//======================================================================= +//function : RejectMetric +//purpose : +//======================================================================= +Standard_Boolean Extrema_GenExtPS::RejectMetric (const Standard_Real& theDistance) const +{ + switch (myTarget) + { + case Extrema_ExtFlag_MIN: + return theDistance > (mySqDistance + Precision::SquareConfusion()); + case Extrema_ExtFlag_MAX: + return theDistance < (mySqDistance - Precision::SquareConfusion()); + default: + return Standard_False; + } +} - theParam0.GetIndices(anIndices[0], anIndices[1]); - myGridParam.SetElementType(IsUEdge ? Extrema_UIsoEdge : Extrema_VIsoEdge); - myGridParam.SetSqrDistance(thePoint.SquareDistance(myGridParam.Value())); - myGridParam.SetIndices(anIndices[0], anIndices[1]); - return myGridParam; - } +//======================================================================= +//function : IsMetricBetter +//purpose : +//======================================================================= +Standard_Boolean Extrema_GenExtPS::IsMetricBetter (const Standard_Real& theLeft, + const Standard_Real& theRight) const +{ + switch (myTarget) + { + case Extrema_ExtFlag_MIN: + return theLeft <= theRight; + case Extrema_ExtFlag_MAX: + return theLeft >= theRight; + default: + return Standard_True; } } -void Extrema_GenExtPS::BuildGrid(const gp_Pnt &thePoint) +//======================================================================= +//function : Accept +//purpose : +//======================================================================= +Standard_Boolean Extrema_GenExtPS::Accept (const Standard_Integer theIndex, + const Standard_Real&) { - 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_Real U = U0; - for ( NoU = 1 ; NoU <= myusample; NoU++, U += PasU) - myUParams->SetValue(NoU, U); - } - - 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_Real V = V0; - - for ( NoV = 1, V = V0; NoV <= myvsample; NoV++, V += PasV) - myVParams->SetValue(NoV, V); - } + if (myBVHSet == NULL) + { + Extrema_GenExtPS_LocalizedGrid aGridSet = myBVHBoxSet->Element (theIndex); - //If flag was changed and extrema not reinitialized Extrema would fail - myPoints = new Extrema_HArray2OfPOnSurfParams - (0, myusample + 1, 0, myvsample + 1); - // Calculation of distances - - 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); - } - } + Standard_Integer aUCoeff = (aGridSet.IdUMax < myNbUSamples) ? 1 : 0; + Standard_Integer aVCoeff = (aGridSet.IdVMax < myNbVSamples) ? 1 : 0; - myFacePntParams = - new Extrema_HArray2OfPOnSurfParams(0, myusample, 0, myvsample); + const Extrema_POnSurf& aPMin = myPoints->Value (aGridSet.IdUMin, aGridSet.IdVMin); + const Extrema_POnSurf& aPMax = myPoints->Value (aGridSet.IdUMax + aUCoeff, aGridSet.IdVMax + aVCoeff); - myUEdgePntParams = - new Extrema_HArray2OfPOnSurfParams(1, myusample - 1, 1, myvsample); - myVEdgePntParams = - new Extrema_HArray2OfPOnSurfParams(1, myusample, 1, myvsample - 1); + Standard_Real aUMin, aUMax, aVMin, aVMax; + aPMin.Parameter (aUMin, aVMin); + aPMax.Parameter (aUMax, aVMax); - // 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 ((aUMax < myLocUMin || aUMin > myLocUMax) && + (aVMax < myLocVMin || aVMin > myLocVMax)) + return 0; - for (NoU = 1; NoU <= myusample; NoU++) { - myPoints->ChangeValue(NoU, 0).SetSqrDistance(-1.); - myPoints->ChangeValue(NoU, myvsample + 1).SetSqrDistance(-1.); + Standard_Integer idUMin = Max (1, aGridSet.IdUMin - 1), idUMax = Min (myNbUSamples, aGridSet.IdUMax + 1); + Standard_Integer idVMin = Max (1, aGridSet.IdVMin - 1), idVMax = Min (myNbVSamples, aGridSet.IdVMax + 1); + for (Standard_Integer iU = idUMin; iU <= idUMax; ++iU) + { + for (Standard_Integer iV = idVMin; iV <= idVMax; ++iV) + { + Extrema_POnSurfParams& aParam = myPoints->ChangeValue (iU, iV); + aParam.SetSqrDistance (aParam.Value().SquareDistance (myPoint)); + } } - - myInit = Standard_True; + + aGridSet.CellBoxSet->Build(); + // Set low-level BVH set for inner selection + SetBVHSet (aGridSet.CellBoxSet.get()); + Standard_Integer aNb = Select(); + // Unset the inner set and continue with high level BVH traverse + SetBVHSet (NULL); + return aNb > 0; + } + else + { + Extrema_GenExtPS_GridCell aCell = myBVHSet->Element (theIndex); + return FindSolution (aCell.UIndex, aCell.VIndex, myTarget); } +} - // Compute distances to mesh. - // Step 1. Compute distances to nodes. - for ( NoU = 1 ; NoU <= myusample; NoU++ ) { - for ( NoV = 1 ; NoV <= myvsample; NoV++) { - Extrema_POnSurfParams &aParam = myPoints->ChangeValue(NoU, NoV); +//======================================================================= +//function : Accept +//purpose : +//======================================================================= +Standard_Boolean Extrema_GenExtPS::FindSolution (const Standard_Integer theNU, + const Standard_Integer theNV, + const Extrema_ExtFlag theTarget) +{ + // Fill corner points with square distance to myPoint + const Extrema_POnSurfParams& aParam00 = myPoints->Value (theNU, theNV); + const Extrema_POnSurfParams& aParam11 = myPoints->Value (theNU + 1, theNV + 1); - aParam.SetSqrDistance(thePoint.SquareDistance(aParam.Value())); - } + { + Standard_Real U1, U2, V1, V2; + aParam00.Parameter (U1, V1); + aParam11.Parameter (U2, V2); + if ((U2 < myLocUMin || U1 > myLocUMax) && + (V2 < myLocVMin || V1 > myLocVMax)) + return Standard_False; } - // For search of minimum compute distances to mesh. - if(myFlag == Extrema_ExtFlag_MIN || myFlag == Extrema_ExtFlag_MINMAX) + Standard_Boolean isFound = Standard_False; + if (theTarget == Extrema_ExtFlag_MIN && + theNU != myNbUSamples && theNV != myNbVSamples) { - // This is the tolerance of difference of squared values. - // No need to set it too small. - const Standard_Real aDiffTol = mytolu + mytolv; + // Find minimum + + const Extrema_POnSurfParams& aParam = ComputeFaceParameters (theNU, theNV); - // 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) } - for ( NoU = 1 ; NoU <= myusample; NoU++ ) + Standard_Boolean isMin = Standard_False; + Extrema_ElementType anElemType = aParam.GetElementType(); + + if (anElemType == Extrema_Face) + { + isMin = Standard_True; + } + else { - for ( NoV = 1 ; NoV <= myvsample; NoV++) + // Check if it is a boundary edge or corner vertex. + Standard_Integer iU, iV; + aParam.GetIndices (iU, iV); + + if (anElemType == Extrema_UIsoEdge) + { + isMin = (iV == 1 || iV == myNbVSamples); + } + else if (anElemType == Extrema_VIsoEdge) { - const Extrema_POnSurfParams &aParam0 = myPoints->Value(NoU, NoV); + isMin = (iU == 1 || iU == myNbUSamples); + } + else if (anElemType == Extrema_Node) + { + isMin = (iU == 1 || iU == myNbUSamples) && + (iV == 1 || iV == myNbVSamples); + } - if (NoU < myusample) + if (!isMin) + { + // This is a middle element. + if (anElemType == Extrema_UIsoEdge || + (anElemType == Extrema_Node && (iU == 1 || iU == myNbUSamples))) { - // Compute parameters to UEdge. - const Extrema_POnSurfParams &aParam1 = myPoints->Value(NoU + 1, NoV); - const Extrema_POnSurfParams &anEdgeParam = ComputeEdgeParameters(Standard_True, aParam0, aParam1, thePoint, aDiffTol); + // Check the down face. + const Extrema_POnSurfParams &aDownParam = ComputeFaceParameters (theNU, theNV - 1); - myUEdgePntParams->SetValue(NoU, NoV, anEdgeParam); + if (aDownParam.GetElementType() == anElemType) + { + Standard_Integer iU2, iV2; + aDownParam.GetIndices (iU2, iV2); + isMin = (iU == iU2 && iV == iV2); + } } - - if (NoV < myvsample) + else if (anElemType == Extrema_VIsoEdge || + (anElemType == Extrema_Node && (iV == 1 || iV == myNbVSamples))) { - // Compute parameters to VEdge. - const Extrema_POnSurfParams &aParam1 = myPoints->Value(NoU, NoV + 1); - const Extrema_POnSurfParams &anEdgeParam = ComputeEdgeParameters(Standard_False, aParam0, aParam1, thePoint, aDiffTol); + // Check the right face. + const Extrema_POnSurfParams &aRightParam = ComputeFaceParameters (theNU - 1, theNV); - myVEdgePntParams->SetValue(NoU, NoV, anEdgeParam); - } - } - } - - // 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) } - 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 = myUEdgePntParams->Value(NoU, NoV); - const Extrema_POnSurfParams &aUE1 = myUEdgePntParams->Value(NoU, NoV+1); - const Extrema_POnSurfParams &aVE0 = myVEdgePntParams->Value(NoU, NoV); - const Extrema_POnSurfParams &aVE1 = myVEdgePntParams->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 (aRightParam.GetElementType() == anElemType) + { + Standard_Integer iU2, iV2; + aRightParam.GetIndices (iU2, iV2); + isMin = (iU == iU2 && iV == iV2); } } + else if (iU == theNU && iV == theNV) + { + // Check the lower-left node. For this purpose it is necessary + // to check lower-left, lower and left faces. + isMin = 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); + const Extrema_POnSurfParams *anOtherParam[3] = { + &ComputeFaceParameters (theNU, theNV - 1), // Down + &ComputeFaceParameters (theNU - 1, theNV - 1), // Lower-left + &ComputeFaceParameters (theNU - 1, theNV) }; // Left + + for (int i = 0; i < 3 && isMin; i++) + { + if (anOtherParam[i]->GetElementType() == Extrema_Node) + { + Standard_Integer iU2, iV2; + anOtherParam[i]->GetIndices (iU2, iV2); + isMin = (iU == iU2 && iV == iV2); + } + else + { + isMin = Standard_False; + } + } } } } - // Fill boundary with RealLast square distance. - for (NoV = 0; NoV <= myvsample; NoV++) { - myFacePntParams->ChangeValue(0, NoV).SetSqrDistance(RealLast()); - myFacePntParams->ChangeValue(myusample, NoV).SetSqrDistance(RealLast()); + if (isMin) + { + if (FindSolution (aParam)) + isFound = Standard_True; } + } - for (NoU = 1; NoU < myusample; NoU++) { - myFacePntParams->ChangeValue(NoU, 0).SetSqrDistance(RealLast()); - myFacePntParams->ChangeValue(NoU, myvsample).SetSqrDistance(RealLast()); + if (theTarget == Extrema_ExtFlag_MAX) + { + // Find maximum + const Extrema_POnSurfParams &aParam1 = myPoints->Value (theNU - 1, theNV - 1); + const Extrema_POnSurfParams &aParam2 = myPoints->Value (theNU - 1, theNV); + const Extrema_POnSurfParams &aParam3 = myPoints->Value (theNU - 1, theNV + 1); + const Extrema_POnSurfParams &aParam4 = myPoints->Value (theNU, theNV - 1); + const Extrema_POnSurfParams &aParam5 = myPoints->Value (theNU, theNV + 1); + const Extrema_POnSurfParams &aParam6 = myPoints->Value (theNU + 1, theNV - 1); + const Extrema_POnSurfParams &aParam7 = myPoints->Value (theNU + 1, theNV); + const Extrema_POnSurfParams &aParam8 = myPoints->Value (theNU + 1, theNV + 1); + + Standard_Real aDist = aParam00.GetSqrDistance(); + + if ((aParam1.GetSqrDistance() <= aDist) && + (aParam2.GetSqrDistance() <= aDist) && + (aParam3.GetSqrDistance() <= aDist) && + (aParam4.GetSqrDistance() <= aDist) && + (aParam5.GetSqrDistance() <= aDist) && + (aParam6.GetSqrDistance() <= aDist) && + (aParam7.GetSqrDistance() <= aDist) && + (aParam8.GetSqrDistance() <= aDist)) + { + // Find maximum. + if (FindSolution (aParam00)) + isFound = Standard_True; } } + + return isFound; } -// Parametrization of the sample -void Extrema_GenExtPS::BuildTree() +//======================================================================= +//function : FindSolution +//purpose : +//======================================================================= +Standard_Boolean Extrema_GenExtPS::FindSolution (const Extrema_POnSurfParams &theParams) { - // if tree already exists, assume it is already correctly filled - if ( ! mySphereUBTree.IsNull() ) - return; + math_Vector Tol (1, 2); + Tol (1) = myTolU; + Tol (2) = myTolV; - if (myS->GetType() == GeomAbs_BSplineSurface) { - Handle(Geom_BSplineSurface) aBspl = myS->BSpline(); - Standard_Integer aUValue = aBspl->UDegree() * aBspl->NbUKnots(); - Standard_Integer aVValue = aBspl->VDegree() * aBspl->NbVKnots(); - if (aUValue > myusample) - myusample = aUValue; - if (aVValue > myvsample) - myvsample = aVValue; - } - - Standard_Real PasU = myusup - myumin; - Standard_Real PasV = myvsup - myvmin; - Standard_Real U0 = PasU / myusample / 100.; - Standard_Real V0 = PasV / myvsample / 100.; - gp_Pnt P1; - PasU = (PasU - U0) / (myusample - 1); - PasV = (PasV - V0) / (myvsample - 1); - U0 = U0/2. + myumin; - V0 = V0/2. + myvmin; - - //build grid of parametric points - myUParams = new TColStd_HArray1OfReal(1,myusample ); - myVParams = new TColStd_HArray1OfReal(1,myvsample ); - Standard_Integer NoU, NoV; - Standard_Real U = U0, V = V0; - for ( NoU = 1 ; NoU <= myusample; NoU++, U += PasU) - myUParams->SetValue(NoU, U); - for ( NoV = 1, V = V0; NoV <= myvsample; NoV++, V += PasV) - myVParams->SetValue(NoV, V); - - // Calculation of distances - mySphereUBTree = new Extrema_UBTreeOfSphere; - Extrema_UBTreeFillerOfSphere aFiller(*mySphereUBTree); - Standard_Integer i = 0; - - mySphereArray = new Bnd_HArray1OfSphere(0, myusample * myvsample); - - for ( NoU = 1; NoU <= myusample; NoU++ ) { - for ( NoV = 1; NoV <= myvsample; NoV++) { - P1 = myS->Value(myUParams->Value(NoU), myVParams->Value(NoV)); - Bnd_Sphere aSph(P1.XYZ(), 0/*mytolu < mytolv ? mytolu : mytolv*/, NoU, NoV); - aFiller.Add(i, aSph); - mySphereArray->SetValue( i, aSph ); - i++; - } + 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; + UVsup (1) = myUMax; + UVsup (2) = myVMax; + + Standard_Integer aNbFuncSol = myF.NbExt(); + + math_FunctionSetRoot S (myF, Tol); + S.Perform (myF, UV, UVinf, UVsup); + + myIsDone = Standard_True; + + Standard_Boolean isFound = Standard_False; + if (myTarget != Extrema_ExtFlag_MINMAX) + { + isFound = (mySqDistance != myF.BestSquareDistance()); + mySqDistance = myF.BestSquareDistance(); } - aFiller.Fill(); + else + { + isFound = myF.NbExt() > aNbFuncSol; + } + return isFound; } -void Extrema_GenExtPS::FindSolution(const gp_Pnt& /*P*/, - const Extrema_POnSurfParams &theParams) +//======================================================================= +//function : ComputeEdgeParameters +//purpose : This function computes the point on surface parameters on edge. +// if it coincides with theParam0 or theParam1, it is returned. +//======================================================================= +const Extrema_POnSurfParams& Extrema_GenExtPS:: + ComputeEdgeParameters (const Standard_Boolean IsUEdge, + const Extrema_POnSurfParams& theParam0, + const Extrema_POnSurfParams& theParam1, + const Standard_Real theDiffTol) { - math_Vector Tol(1,2); - Tol(1) = mytolu; - Tol(2) = mytolv; + const Handle (Extrema_HArray2OfPOnSurfParams)& anEdgeParamsArr = IsUEdge ? myUEdgePntParams : myVEdgePntParams; + Standard_Integer iU, iV; + theParam0.GetIndices (iU, iV); + Extrema_POnSurfParams& anEdgeParams = anEdgeParamsArr->ChangeValue (iU, iV); + if (anEdgeParams.GetSqrDistance() < 0.0) + { + const Standard_Real aSqrDist01 = + theParam0.Value().SquareDistance (theParam1.Value()); - math_Vector UV(1, 2); - theParams.Parameter(UV(1), UV(2)); + if (aSqrDist01 <= theDiffTol) + { + // The points are confused. Get the first point and change its type. + anEdgeParams = theParam0; + } + else + { + const Standard_Real aDiffDist = + Abs (theParam0.GetSqrDistance() - theParam1.GetSqrDistance()); - math_Vector UVinf(1,2), UVsup(1,2); - UVinf(1) = myumin; - UVinf(2) = myvmin; - UVsup(1) = myusup; - UVsup(2) = myvsup; + if (aDiffDist >= aSqrDist01 - theDiffTol) + { + // The shortest distance is one of the nodes. + if (theParam0.GetSqrDistance() > theParam1.GetSqrDistance()) + { + // The shortest distance is the point 1. + anEdgeParams = theParam1; + } + else + { + // The shortest distance is the point 0. + anEdgeParams = theParam0; + } + } + else + { + // The shortest distance is inside the edge. + gp_XYZ aPoP (myPoint.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]; - math_FunctionSetRoot S(myF, Tol); - S.Perform(myF, UV, UVinf, UVsup); + theParam0.Parameter (aU[0], aV[0]); + theParam1.Parameter (aU[1], aV[1]); - myDone = Standard_True; -} + Standard_Real aUPar = aU[0]; + Standard_Real aVPar = aV[0]; -void Extrema_GenExtPS::SetFlag(const Extrema_ExtFlag F) -{ - myFlag = F; -} + if (IsUEdge) + { + aUPar += aRatio*(aU[1] - aU[0]); + } + else + { + aVPar += aRatio*(aV[1] - aV[0]); + } -void Extrema_GenExtPS::SetAlgo(const Extrema_ExtAlgo A) -{ - if(myAlgo != A) - myInit = Standard_False; - myAlgo = A; - + anEdgeParams.SetParameters (aUPar, aVPar, myS->Value (aUPar, aVPar)); + anEdgeParams.SetElementType (IsUEdge ? Extrema_UIsoEdge : Extrema_VIsoEdge); + anEdgeParams.SetSqrDistance (anEdgeParams.Value().SquareDistance (myPoint)); + anEdgeParams.SetIndices (iU, iV); + } + } + } + + return anEdgeParams; } -void Extrema_GenExtPS::Perform(const gp_Pnt& P) -{ - myDone = Standard_False; - myF.SetPoint(P); - - if(myAlgo == Extrema_ExtAlgo_Grad) +//======================================================================= +//function : ComputeFaceParameters +//purpose : This function computes the point on surface parameters on cell +//======================================================================= +const Extrema_POnSurfParams& Extrema_GenExtPS:: + ComputeFaceParameters (const Standard_Integer theU, + const Standard_Integer theV) +{ + Extrema_POnSurfParams& aFaceParams = myFacePntParams->ChangeValue (theU, theV); + if (aFaceParams.GetSqrDistance() < 0.0) { - BuildGrid(P); - Standard_Integer NoU,NoV; + // This is the tolerance of difference of squared values. + // No need to set it too small. + const Standard_Real aDiffTol = myTolU + myTolV; - if(myFlag == Extrema_ExtFlag_MIN || myFlag == Extrema_ExtFlag_MINMAX) - { - 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); - } + const Extrema_POnSurfParams& aParam00 = myPoints->Value (theU, theV); + const Extrema_POnSurfParams& aParam01 = myPoints->Value (theU, theV + 1); + const Extrema_POnSurfParams& aParam10 = myPoints->Value (theU + 1, theV); + const Extrema_POnSurfParams& aParam11 = myPoints->Value (theU + 1, theV + 1); - 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; - } - } - } - } - } + const Extrema_POnSurfParams &aUE0 = + ComputeEdgeParameters (Standard_True, aParam00, aParam10, aDiffTol); + const Extrema_POnSurfParams &aUE1 = + ComputeEdgeParameters (Standard_True, aParam01, aParam11, aDiffTol); - if (isMin) { - FindSolution(P, aParam); - } - } - } + const Extrema_POnSurfParams &aVE0 = + ComputeEdgeParameters (Standard_False, aParam00, aParam01, aDiffTol); + const Extrema_POnSurfParams &aVE1 = + ComputeEdgeParameters (Standard_False, aParam10, aParam11, aDiffTol); + + Standard_Real aSqrDist01 = aUE0.Value().SquareDistance (aUE1.Value()); + Standard_Real aDiffDist = Abs (aUE0.GetSqrDistance() - aUE1.GetSqrDistance()); + Standard_Boolean isOut = Standard_False; + + if (aDiffDist >= aSqrDist01 - aDiffTol) + { + // The projection is outside the face. + isOut = Standard_True; } - - if(myFlag == Extrema_ExtFlag_MAX || myFlag == Extrema_ExtFlag_MINMAX) + else { - Standard_Real Dist; + aSqrDist01 = aVE0.Value().SquareDistance (aVE1.Value()); + aDiffDist = Abs (aVE0.GetSqrDistance() - aVE1.GetSqrDistance()); - for (NoU = 1; NoU <= myusample; NoU++) + if (aDiffDist >= aSqrDist01 - aDiffTol) { - for (NoV = 1; NoV <= myvsample; NoV++) - { - const Extrema_POnSurfParams &aParamMain = myPoints->Value(NoU, NoV); - const Extrema_POnSurfParams &aParam1 = myPoints->Value(NoU - 1, NoV - 1); - const Extrema_POnSurfParams &aParam2 = myPoints->Value(NoU - 1, NoV); - const Extrema_POnSurfParams &aParam3 = myPoints->Value(NoU - 1, NoV + 1); - const Extrema_POnSurfParams &aParam4 = myPoints->Value(NoU, NoV - 1); - const Extrema_POnSurfParams &aParam5 = myPoints->Value(NoU, NoV + 1); - const Extrema_POnSurfParams &aParam6 = myPoints->Value(NoU + 1, NoV - 1); - const Extrema_POnSurfParams &aParam7 = myPoints->Value(NoU + 1, NoV); - const Extrema_POnSurfParams &aParam8 = myPoints->Value(NoU + 1, NoV + 1); - - Dist = aParamMain.GetSqrDistance(); - - if ((aParam1.GetSqrDistance() <= Dist) && - (aParam2.GetSqrDistance() <= Dist) && - (aParam3.GetSqrDistance() <= Dist) && - (aParam4.GetSqrDistance() <= Dist) && - (aParam5.GetSqrDistance() <= Dist) && - (aParam6.GetSqrDistance() <= Dist) && - (aParam7.GetSqrDistance() <= Dist) && - (aParam8.GetSqrDistance() <= Dist)) - { - // Find maximum. - FindSolution(P, myPoints->Value(NoU, NoV)); - } - } + // The projection is outside the face. + isOut = Standard_True; } } - } - else - { - BuildTree(); - if(myFlag == Extrema_ExtFlag_MIN || myFlag == Extrema_ExtFlag_MINMAX) + + if (isOut) { - Bnd_Sphere aSol = mySphereArray->Value(0); - Bnd_SphereUBTreeSelectorMin aSelector(mySphereArray, aSol); - //aSelector.SetMaxDist( RealLast() ); - aSelector.DefineCheckPoint( P ); - 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)); - - aParams.SetSqrDistance(P.SquareDistance(aParams.Value())); - aParams.SetIndices(aSph.U(), aSph.V()); - FindSolution(P, aParams); + // 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; + + aFaceParams = aEMin; } - if(myFlag == Extrema_ExtFlag_MAX || myFlag == Extrema_ExtFlag_MINMAX) + else { - Bnd_Sphere aSol = mySphereArray->Value(0); - Bnd_SphereUBTreeSelectorMax aSelector(mySphereArray, aSol); - //aSelector.SetMaxDist( RealLast() ); - aSelector.DefineCheckPoint( P ); - 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)); - aParams.SetSqrDistance(P.SquareDistance(aParams.Value())); - aParams.SetIndices(aSph.U(), aSph.V()); - - FindSolution(P, aParams); + // 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]); + + aFaceParams.SetParameters (aUPar, aVPar, myS->Value (aUPar, aVPar)); + aFaceParams.SetElementType (Extrema_Face); + aFaceParams.SetSqrDistance (aFaceParams.Value().SquareDistance (myPoint)); + aFaceParams.SetIndices (theU, theV); } } -} -//============================================================================= -Standard_Boolean Extrema_GenExtPS::IsDone () const { return myDone; } -//============================================================================= + return aFaceParams; +} -Standard_Integer Extrema_GenExtPS::NbExt () const +//======================================================================= +//function : NbExt +//purpose : +//======================================================================= +Standard_Integer Extrema_GenExtPS::NbExt() const { - if (!IsDone()) { throw StdFail_NotDone(); } - return myF.NbExt(); + if (!IsDone()) + { + throw StdFail_NotDone(); + } + return static_cast (mySolutions.size()); } -//============================================================================= +//======================================================================= +//function : SquareDistance +//purpose : +//======================================================================= Standard_Real Extrema_GenExtPS::SquareDistance (const Standard_Integer N) const { if ((N < 1) || (N > NbExt())) @@ -995,10 +1074,13 @@ Standard_Real Extrema_GenExtPS::SquareDistance (const Standard_Integer N) const throw Standard_OutOfRange(); } - return myF.SquareDistance(N); + return mySolutions[N - 1].SqDistance; } -//============================================================================= +//======================================================================= +//function : Point +//purpose : +//======================================================================= const Extrema_POnSurf& Extrema_GenExtPS::Point (const Standard_Integer N) const { if ((N < 1) || (N > NbExt())) @@ -1006,6 +1088,5 @@ const Extrema_POnSurf& Extrema_GenExtPS::Point (const Standard_Integer N) const throw Standard_OutOfRange(); } - return myF.Point(N); + return mySolutions[N - 1].UV; } -//============================================================================= diff --git a/src/Extrema/Extrema_GenExtPS.hxx b/src/Extrema/Extrema_GenExtPS.hxx index 3ad87ef279..46f264f2cf 100644 --- a/src/Extrema/Extrema_GenExtPS.hxx +++ b/src/Extrema/Extrema_GenExtPS.hxx @@ -21,18 +21,19 @@ #include #include -#include -#include -#include +#include +#include +#include +#include #include -#include -#include #include -#include +#include #include -#include +#include +#include +#include +#include #include -#include class StdFail_NotDone; class Standard_OutOfRange; class Standard_TypeMismatch; @@ -42,130 +43,375 @@ class Extrema_POnSurf; class Extrema_POnSurfParams; -//! It calculates all the extremum distances -//! between a point and a surface. +//! Grid cell defined by (U, V) indices of the minimal +//! corner of the cell +struct Extrema_GenExtPS_GridCell +{ + Standard_Integer UIndex; //!< U index of the minimal corner + Standard_Integer VIndex; //!< V index of the minimal corner + + Extrema_GenExtPS_GridCell (Standard_Integer theUInd = -1, Standard_Integer theVInd = -1) + : UIndex (theUInd), VIndex (theVInd) + {} +}; + +//! typedef to BVH tree of the grid cells +typedef BVH_BoxSet Extrema_GenExtPS_GridCellBoxSet; + + +//! It calculates the extreme distances between a point and a surface. //! These distances can be minimum or maximum. -class Extrema_GenExtPS +//! +//! The function F(u,v) = distance (P, S(u,v)) has an extrema when +//! gradient(F) = 0. The algorithm searches all the zeros inside +//! the definition ranges of the surface. +//! +//! When defining the surface, the number of samples in U and V direction +//! should be specified. These numbers should be great enough such +//! that if there exist N extreme distances between the point and the surface, +//! so there also exist N extrema between the point and the grid. +//! +//! It is possible to look for extrema distances in the whole parametric +//! space of the surface or limit it with the specified range which can be +//! useful when it is needed to look for local extrema distances. +//! +//! Parametric tolerances are used to determine the conditions to stop the +//! iterations - at the iteration number n: +//! (Un - Un-1) < TolU and (Vn - Vn-1) < TolV +//! +//! It is possible to look for only Minimal or Maximal distances, +//! as well as for all solutions. +//! +//! The class is BVH enhanced - the grid cells are stored into BVH-organized +//! structure. Depending on the Extrema target the traverse of the BVH tree +//! is different. +class Extrema_GenExtPS: + protected BVH_Traverse , + public Standard_Transient { public: - DEFINE_STANDARD_ALLOC + DEFINE_STANDARD_RTTIEXT (Extrema_GenExtPS, Standard_Transient) +public: //! @name Constructors computing the distances - Standard_EXPORT Extrema_GenExtPS(); - - //! It calculates all the distances. - //! The function F(u,v)=distance(P,S(u,v)) has an - //! extremum when gradient(F)=0. The algorithm searchs - //! all the zeros inside the definition ranges of the - //! surface. - //! NbU and NbV are used to locate the close points - //! to find the zeros. They must be great enough - //! such that if there is N extrema, there will - //! be N extrema between P and the grid. - //! TolU et TolV are used to determine the conditions - //! to stop the iterations; at the iteration number n: - //! (Un - Un-1) < TolU and (Vn - Vn-1) < TolV . - Standard_EXPORT Extrema_GenExtPS(const gp_Pnt& P, const Adaptor3d_Surface& S, const Standard_Integer NbU, const Standard_Integer NbV, const Standard_Real TolU, const Standard_Real TolV, const Extrema_ExtFlag F = Extrema_ExtFlag_MINMAX, const Extrema_ExtAlgo A = Extrema_ExtAlgo_Grad); - - //! It calculates all the distances. - //! The function F(u,v)=distance(P,S(u,v)) has an - //! extremum when gradient(F)=0. The algorithm searchs - //! all the zeros inside the definition ranges of the - //! surface. - //! NbU and NbV are used to locate the close points - //! to find the zeros. They must be great enough - //! such that if there is N extrema, there will - //! be N extrema between P and the grid. - //! TolU et TolV are used to determine the conditions - //! to stop the iterations; at the iteration number n: - //! (Un - Un-1) < TolU and (Vn - Vn-1) < TolV . - Standard_EXPORT Extrema_GenExtPS(const gp_Pnt& P, const Adaptor3d_Surface& S, const Standard_Integer NbU, const Standard_Integer NbV, const Standard_Real Umin, const Standard_Real Usup, const Standard_Real Vmin, const Standard_Real Vsup, const Standard_Real TolU, const Standard_Real TolV, const Extrema_ExtFlag F = Extrema_ExtFlag_MINMAX, const Extrema_ExtAlgo A = Extrema_ExtAlgo_Grad); - - Standard_EXPORT void Initialize (const Adaptor3d_Surface& S, const Standard_Integer NbU, const Standard_Integer NbV, const Standard_Real TolU, const Standard_Real TolV); - - Standard_EXPORT void Initialize (const Adaptor3d_Surface& S, const Standard_Integer NbU, const Standard_Integer NbV, const Standard_Real Umin, const Standard_Real Usup, const Standard_Real Vmin, const Standard_Real Vsup, const Standard_Real TolU, const Standard_Real TolV); - - //! the algorithm is done with the point P. - //! An exception is raised if the fields have not - //! been initialized. - Standard_EXPORT void Perform (const gp_Pnt& P); + //! Constructor for computation of the distances between specified point and surface. + //! The whole parametric space of the surfaces is taken into account. + //! + //! Constructor is mostly used for one time projection of the point on the surface, + //! but still the instances of extrema can be used for projecting other points on the surface + //! with *Perform()* method. + //! + //! @param theP point + //! @param theS Surface + //! @param theNbU Number of samples in U direction + //! @param theNbV Number of samples in V direction + //! @param theTolU U Parametric tolerance + //! @param theTolV V Parametric tolerance + //! @param theTarget defines what solutions are required + Standard_EXPORT Extrema_GenExtPS (const gp_Pnt& theP, + const Adaptor3d_Surface& theS, + const Standard_Integer theNbU, + const Standard_Integer theNbV, + const Standard_Real theTolU, + const Standard_Real theTolV, + const Extrema_ExtFlag theTarget = Extrema_ExtFlag_MINMAX); - Standard_EXPORT void SetFlag (const Extrema_ExtFlag F); - - Standard_EXPORT void SetAlgo (const Extrema_ExtAlgo A); + //! Constructor for computation of the distances between specified point and surface. + //! Only the specified parametric range of the surface is taken into account. + //! + //! Constructor is mostly used for one time projection of the point on the surface, + //! but still the instances of extrema can be used for projecting other points on the surface + //! with *Perform()* method. + //! + //! @param theP point + //! @param theS Surface + //! @param theNbU Number of samples in U direction + //! @param theNbV Number of samples in V direction + //! @param theUMin Lower U bound + //! @param theUMax Upper U bound + //! @param theVMin Lower V bound + //! @param theVMax Upper V bound + //! @param theTolU U Parametric tolerance + //! @param theTolV V Parametric tolerance + //! @param theTarget defines what solutions are required + Standard_EXPORT Extrema_GenExtPS (const gp_Pnt& theP, + const Adaptor3d_Surface& theS, + const Standard_Integer theNbU, + const Standard_Integer theNbV, + const Standard_Real theUMin, + const Standard_Real theUMax, + const Standard_Real theVMin, + const Standard_Real theVMax, + const Standard_Real theTolU, + const Standard_Real theTolV, + const Extrema_ExtFlag theTarget = Extrema_ExtFlag_MINMAX); + +public: //! @name Empty constructor + Initialization step + + //! Empty constructor + Standard_EXPORT Extrema_GenExtPS(); + + //! Initializes Extrema algorithm with the surfaces. + //! Search is performed in whole parametric range of the surface. + //! @param theS Surface + //! @param theNbU Number of samples in U direction + //! @param theNbV Number of samples in V direction + //! @param theTolU U Parametric tolerance + //! @param theTolV V Parametric tolerance + Standard_EXPORT void Initialize (const Adaptor3d_Surface& theS, + const Standard_Integer theNbU, + const Standard_Integer theNbV, + const Standard_Real theTolU, + const Standard_Real theTolV); + + //! Initializes Extrema algorithm with the surfaces. + //! Search is performed in the given parametric range. + //! @param S Surface + //! @param theNbU Number of samples in U direction + //! @param theNbV Number of samples in V direction + //! @param theUMin Lower U bound + //! @param theUMax Upper U bound + //! @param theVMin Lower V bound + //! @param theVMax Upper V bound + //! @param theTolU U Parametric tolerance + //! @param theTolV V Parametric tolerance + Standard_EXPORT void Initialize (const Adaptor3d_Surface& theS, + const Standard_Integer theNbU, + const Standard_Integer theNbV, + const Standard_Real theUMin, + const Standard_Real theUMax, + const Standard_Real theVMin, + const Standard_Real theVMax, + const Standard_Real theTolU, + const Standard_Real theTolV); + +public: //! @name Specifying the search options + + //! Specifies what solutions are necessary: + //! - *Extrema_ExtFlag_MIN* - only minimal solutions + //! - *Extrema_ExtFlag_MAX* - only maximal solutions + //! - *Extrema_ExtFlag_MINMAX - all solutions (default value). + void SetTarget (const Extrema_ExtFlag theTarget) + { + myTarget = theTarget; + } + + //! Returns the Extrema target type + Extrema_ExtFlag Target() const { return myTarget; } + + //! Sets the tolerance for the search. + //! These tolerances are used for projection of the point, + //! and not used for surface initialization, so can be changed + //! from point to point. + void SetTolerance (const Standard_Real theTolU, + const Standard_Real theTolV) + { + myTolU = theTolU; + myTolV = theTolV; + } + + +public: //! @name Performing projection + + //! Performs projection of the point on the surface. + //! Extrema must already be initialized with the surface. + //! Allows multiple points be projected on the same surface. + Standard_EXPORT void Perform (const gp_Pnt& theP); + + //! Performs localized extrema search. + //! The localized boundaries are required to be inside the + //! main (initialized) surface parametric space. + Standard_EXPORT void Perform (const gp_Pnt& theP, + const Standard_Real theUMin, + const Standard_Real theUMax, + const Standard_Real theVMin, + const Standard_Real theVMax); +public: //! @name Getting the results + //! Returns True if the distances are found. - Standard_EXPORT Standard_Boolean IsDone() const; - - //! Returns the number of extremum distances. + Standard_Boolean IsDone() const { return myIsDone; } + + //! Returns the number of extrema distances found. + //! @throws StdFail_NotDone if extrema search has failed. Standard_EXPORT Standard_Integer NbExt() const; - + //! Returns the value of the Nth resulting square distance. - Standard_EXPORT Standard_Real SquareDistance (const Standard_Integer N) const; - + //! @throws StdFail_NotDone if extrema search has failed. + //! @throws Standard_OutOfRange if given index is out of range of found + //! solutions ((N < 1) || (N > NbExt()). + Standard_EXPORT Standard_Real SquareDistance (const Standard_Integer theN) const; + //! Returns the point of the Nth resulting distance. - Standard_EXPORT const Extrema_POnSurf& Point (const Standard_Integer N) const; + //! @throws StdFail_NotDone if extrema search has failed. + //! @throws Standard_OutOfRange if given index is out of range of found + //! solutions ((N < 1) || (N > NbExt()). + Standard_EXPORT const Extrema_POnSurf& Point (const Standard_Integer theN) const; +protected: //! @name Protected methods performing the job + //! Creation of grid of parametric points (sampling of the surface) + Standard_EXPORT void BuildGrid(); -protected: + //! Selection of points to build grid, depending on the type of surface + Standard_EXPORT void GetGridPoints (const Adaptor3d_Surface& theSurf); + //! Builds the BVH tree with bounding boxes of the cells of the grid + Standard_EXPORT void BuildTree(); + //! Looks for the solution starting at given point + Standard_EXPORT Standard_Boolean FindSolution (const Extrema_POnSurfParams& theParams); + //! Compute new edge parameters. + Standard_EXPORT const Extrema_POnSurfParams& + ComputeFaceParameters (const Standard_Integer theU, + const Standard_Integer theV); + //! Compute new edge parameters. + Standard_EXPORT const Extrema_POnSurfParams& + ComputeEdgeParameters (const Standard_Boolean IsUEdge, + const Extrema_POnSurfParams& theParam0, + const Extrema_POnSurfParams& theParam1, + const Standard_Real theDiffTol); -private: + //! Looks for the Min or Max Solution (depending on the given target). + Standard_EXPORT Standard_Boolean FindSolution (const Standard_Integer theUIndex, + const Standard_Integer theVIndex, + const Extrema_ExtFlag theTarget); - - Standard_EXPORT Adaptor3d_SurfacePtr Bidon() const; - - Standard_EXPORT void BuildTree(); - - Standard_EXPORT void FindSolution (const gp_Pnt& P, const Extrema_POnSurfParams& theParams); - - //! Selection of points to build grid, depending on the type of surface - Standard_EXPORT void GetGridPoints (const Adaptor3d_Surface& theSurf); - - //! Creation of grid of parametric points - Standard_EXPORT void BuildGrid (const gp_Pnt& thePoint); - - //! Compute new edge parameters. - Standard_EXPORT const Extrema_POnSurfParams& ComputeEdgeParameters (const Standard_Boolean IsUEdge, const Extrema_POnSurfParams& theParam0, const Extrema_POnSurfParams& theParam1, const gp_Pnt& thePoints, const Standard_Real theDiffTol); - - - Standard_Boolean myDone; - Standard_Boolean myInit; - Standard_Real myumin; - Standard_Real myusup; - Standard_Real myvmin; - Standard_Real myvsup; - Standard_Integer myusample; - Standard_Integer myvsample; - Standard_Real mytolu; - Standard_Real mytolv; - Handle(Extrema_HArray2OfPOnSurfParams) myPoints; - Extrema_HUBTreeOfSphere mySphereUBTree; - Handle(Bnd_HArray1OfSphere) mySphereArray; - Extrema_FuncPSNorm myF; - Adaptor3d_SurfacePtr myS; - Extrema_ExtFlag myFlag; - Extrema_ExtAlgo myAlgo; - Handle(TColStd_HArray1OfReal) myUParams; - Handle(TColStd_HArray1OfReal) myVParams; - Handle(Extrema_HArray2OfPOnSurfParams) myFacePntParams; - Handle(Extrema_HArray2OfPOnSurfParams) myUEdgePntParams; - Handle(Extrema_HArray2OfPOnSurfParams) myVEdgePntParams; - Extrema_POnSurfParams myGridParam; +protected: //! @name Rules for BVH traverse -}; + //! Rejection of the node by bounding box. + //! Metric is computed to choose the best branch. + //! Returns true if the node should be rejected, false otherwise. + Standard_EXPORT virtual Standard_Boolean + RejectNode (const BVH_Vec3d& theCornerMin, + const BVH_Vec3d& theCornerMax, + Standard_Real& theMetric) const Standard_OVERRIDE; + + //! Rejects the node by the metric + Standard_EXPORT virtual Standard_Boolean + RejectMetric (const Standard_Real& theMetric) const Standard_OVERRIDE; + + //! Compares the two metrics and chooses the best one. + //! Returns true if the first metric is better than the second, + //! false otherwise. + Standard_EXPORT virtual Standard_Boolean + IsMetricBetter (const Standard_Real& theLeft, + const Standard_Real& theRight) const Standard_OVERRIDE; + //! Leaf element acceptance. + //! Metric of the parent leaf-node is passed to avoid the check on the + //! element and accept it unconditionally. + //! Returns true if the element has been accepted, false otherwise. + Standard_EXPORT virtual Standard_Boolean + Accept (const Standard_Integer theIndex, + const Standard_Real& theMetric) Standard_OVERRIDE; +protected: //! @name Auxiliary types + //! Structure to keep and sort the results + struct Extrema_GenExtPS_ExtPSResult + { + Extrema_POnSurf UV; //! UV coordinates of extrema solution + Standard_Real SqDistance; //! Square distance to target point + Extrema_GenExtPS_ExtPSResult() + : SqDistance (-1) + {} + Extrema_GenExtPS_ExtPSResult (const Extrema_POnSurf& theUV, + const Standard_Real theSqDist) + : UV (theUV), + SqDistance (theSqDist) + {} + + //! IsLess operator + Standard_Boolean operator< (const Extrema_GenExtPS_ExtPSResult& Other) const + { + if (SqDistance != Other.SqDistance) + return SqDistance < Other.SqDistance; + + Standard_Real U1, U2, V1, V2; + UV.Parameter (U1, V1); + Other.UV.Parameter (U2, V2); + return (U1 < U2 || (U1 == U2 && V1 < V2)); + } + }; + + //! Localized parametric space of surface on which the single + //! BVH tree is built + struct Extrema_GenExtPS_LocalizedGrid + { + Standard_Integer IdUMin; + Standard_Integer IdUMax; + Standard_Integer IdVMin; + Standard_Integer IdVMax; + Handle(Extrema_GenExtPS_GridCellBoxSet) CellBoxSet; + + Extrema_GenExtPS_LocalizedGrid () + : IdUMin (0), IdUMax (0), IdVMin (0), IdVMax (0), CellBoxSet (NULL) + {} + + Extrema_GenExtPS_LocalizedGrid (const Standard_Integer theUMin, + const Standard_Integer theUMax, + const Standard_Integer theVMin, + const Standard_Integer theVMax, + const Handle(Extrema_GenExtPS_GridCellBoxSet)& theCellBoxSet) + : IdUMin (theUMin), IdUMax (theUMax), + IdVMin (theVMin), IdVMax (theVMax), + CellBoxSet (theCellBoxSet) + {} + }; + +protected: //! @name Fields + + // Inputs + gp_Pnt myPoint; //!< Point + Adaptor3d_SurfacePtr myS; //!< Surface + Extrema_FuncPSNorm myF; //!< Function + + Standard_Real myUMin; //!< Surface parametric range: UMin + Standard_Real myUMax; //!< Surface parametric range: UMax + Standard_Real myVMin; //!< Surface parametric range: VMin + Standard_Real myVMax; //!< Surface parametric range: VMax + + Standard_Integer myNbUSamples; //!< Number of samples in U parametric direction + Standard_Integer myNbVSamples; //!< Number of samples in V parametric direction + + Standard_Real myTolU; //!< U parametric tolerance + Standard_Real myTolV; //!< V parametric tolerance + + Standard_Real myLocUMin; //!< Localized surface parametric range: UMin + Standard_Real myLocUMax; //!< Localized surface parametric range: UMax + Standard_Real myLocVMin; //!< Localized surface parametric range: VMin + Standard_Real myLocVMax; //!< Localized surface parametric range: VMax + + Extrema_ExtFlag myTarget; //!< Extrema objective + + // Intermediate data + + Handle(Extrema_HArray2OfPOnSurfParams) myPoints; //!< Grid points + Handle(TColStd_HArray1OfReal) myUParams; //!< Grid parameters in U parametric direction + Handle(TColStd_HArray1OfReal) myVParams; //!< Grid parameters in V parametric direction + + Handle(Extrema_HArray2OfPOnSurfParams) myFacePntParams; + Handle(Extrema_HArray2OfPOnSurfParams) myUEdgePntParams; + Handle(Extrema_HArray2OfPOnSurfParams) myVEdgePntParams; + + Standard_Real mySqDistance; //!< Min/Max found square distance used in BVH tree traverse + opencascade::handle + > myBVHBoxSet; //!< High-level BVH of BVH organized grid cells + + // Results + std::vector mySolutions; //!< Found solutions (sorted first by distance to target point, + //! second by the ascending U,V coordinates) + Standard_Boolean myIsDone; //!< Done/Not done flag +}; +DEFINE_STANDARD_HANDLE (Extrema_GenExtPS, Standard_Transient) #endif // _Extrema_GenExtPS_HeaderFile diff --git a/src/Extrema/Extrema_POnSurfParams.lxx b/src/Extrema/Extrema_POnSurfParams.lxx index e8714453ea..014f60cc81 100644 --- a/src/Extrema/Extrema_POnSurfParams.lxx +++ b/src/Extrema/Extrema_POnSurfParams.lxx @@ -12,7 +12,7 @@ // commercial license or contractual agreement. inline Extrema_POnSurfParams::Extrema_POnSurfParams() -: mySqrDistance (0.), +: mySqrDistance (-1), myElementType (Extrema_Node), myIndexU (0), myIndexV (0) @@ -22,7 +22,7 @@ inline Extrema_POnSurfParams::Extrema_POnSurfParams() inline Extrema_POnSurfParams::Extrema_POnSurfParams (const Standard_Real theU, const Standard_Real theV, const gp_Pnt &thePnt) : Extrema_POnSurf (theU, theV, thePnt), - mySqrDistance (0.), + mySqrDistance (-1), myElementType (Extrema_Node), myIndexU (0), myIndexV (0) diff --git a/src/Extrema/FILES b/src/Extrema/FILES index 1e3d13ee43..518bf0bcc1 100644 --- a/src/Extrema/FILES +++ b/src/Extrema/FILES @@ -33,7 +33,6 @@ Extrema_EPCOfExtPC.hxx Extrema_EPCOfExtPC2d.hxx Extrema_EPCOfExtPC2d_0.cxx Extrema_EPCOfExtPC_0.cxx -Extrema_ExtAlgo.hxx Extrema_ExtCC.cxx Extrema_ExtCC.hxx Extrema_ExtCC2d.cxx diff --git a/src/GCPnts/FILES b/src/GCPnts/FILES index 29ead1dda0..c2364c641e 100755 --- a/src/GCPnts/FILES +++ b/src/GCPnts/FILES @@ -1,3 +1,5 @@ +GCPnts.cxx +GCPnts.hxx GCPnts_AbscissaPoint.cxx GCPnts_AbscissaPoint.pxx GCPnts_AbscissaPoint.hxx diff --git a/src/GCPnts/GCPnts.cxx b/src/GCPnts/GCPnts.cxx new file mode 100644 index 0000000000..de7fe42434 --- /dev/null +++ b/src/GCPnts/GCPnts.cxx @@ -0,0 +1,54 @@ +// Created on: 2020-05-18 +// Copyright (c) 1999-2020 OPEN CASCADE SAS +// +// This file is part of Open CASCADE Technology software library. +// +// This library is free software; you can redistribute it and/or modify it under +// the terms of the GNU Lesser General Public License version 2.1 as published +// by the Free Software Foundation, with special exception defined in the file +// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +// distribution for complete text of the license and disclaimer of any warranty. +// +// Alternatively, this file may be used under the terms of Open CASCADE +// commercial license or contractual agreement. + +#include + +#include +//======================================================================= +//function : FillParams +//purpose : +//======================================================================= +void GCPnts::FillParams (const TColStd_Array1OfReal& theKnots, + const Standard_Integer theDegree, + const Standard_Real theParMin, + const Standard_Real theParMax, + NCollection_Vector& theParams) +{ + Standard_Real aPrevPar = theParMin; + theParams.Append (aPrevPar); + + Standard_Integer aNbP = Max (theDegree, 1); + + for (Standard_Integer i = 1; + (i < theKnots.Length()) && (theKnots (i) < (theParMax - Precision::PConfusion())); ++i) + { + if (theKnots (i + 1) < theParMin + Precision::PConfusion()) + continue; + + Standard_Real aStep = (theKnots (i + 1) - theKnots (i)) / aNbP; + for (Standard_Integer k = 1; k <= aNbP ; ++k) + { + Standard_Real aPar = theKnots (i) + k * aStep; + if (aPar > theParMax - Precision::PConfusion()) + break; + + if (aPar > aPrevPar + Precision::PConfusion()) + { + theParams.Append (aPar); + aPrevPar = aPar; + } + } + } + theParams.Append (theParMax); +} diff --git a/src/GCPnts/GCPnts.hxx b/src/GCPnts/GCPnts.hxx new file mode 100644 index 0000000000..dbaf5857ed --- /dev/null +++ b/src/GCPnts/GCPnts.hxx @@ -0,0 +1,35 @@ +// Created on: 2020-05-18 +// Copyright (c) 1999-2020 OPEN CASCADE SAS +// +// This file is part of Open CASCADE Technology software library. +// +// This library is free software; you can redistribute it and/or modify it under +// the terms of the GNU Lesser General Public License version 2.1 as published +// by the Free Software Foundation, with special exception defined in the file +// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +// distribution for complete text of the license and disclaimer of any warranty. +// +// Alternatively, this file may be used under the terms of Open CASCADE +// commercial license or contractual agreement. + +#ifndef _GCPnts_HeaderFile +#define _GCPnts_HeaderFile + +#include +#include + +//! The GCPnts package provides general utilities for +//! Curves analysis. +class GCPnts +{ +public: + + //! Fills vector with sampling parameters on the curve + Standard_EXPORT static void FillParams (const TColStd_Array1OfReal& theKnots, + const Standard_Integer theDegree, + const Standard_Real theParMin, + const Standard_Real theParMax, + NCollection_Vector& theParams); +}; + +#endif diff --git a/src/GeomAPI/GeomAPI_ProjectPointOnSurf.cxx b/src/GeomAPI/GeomAPI_ProjectPointOnSurf.cxx index 7c1c1e343e..00b9b069ad 100644 --- a/src/GeomAPI/GeomAPI_ProjectPointOnSurf.cxx +++ b/src/GeomAPI/GeomAPI_ProjectPointOnSurf.cxx @@ -40,10 +40,9 @@ GeomAPI_ProjectPointOnSurf::GeomAPI_ProjectPointOnSurf() //purpose : //======================================================================= GeomAPI_ProjectPointOnSurf::GeomAPI_ProjectPointOnSurf (const gp_Pnt& P, - const Handle(Geom_Surface)& Surface, - const Extrema_ExtAlgo theProjAlgo) + const Handle(Geom_Surface)& Surface) { - Init (P, Surface, theProjAlgo); + Init (P, Surface); } //======================================================================= //function : GeomAPI_ProjectPointOnSurf @@ -51,10 +50,9 @@ GeomAPI_ProjectPointOnSurf::GeomAPI_ProjectPointOnSurf() //======================================================================= GeomAPI_ProjectPointOnSurf::GeomAPI_ProjectPointOnSurf (const gp_Pnt& P, const Handle(Geom_Surface)& Surface, - const Standard_Real Tolerance, - const Extrema_ExtAlgo theProjAlgo) + const Standard_Real Tolerance) { - Init (P, Surface, Tolerance, theProjAlgo); + Init (P, Surface, Tolerance); } //======================================================================= //function : GeomAPI_ProjectPointOnSurf @@ -65,11 +63,10 @@ GeomAPI_ProjectPointOnSurf::GeomAPI_ProjectPointOnSurf() const Standard_Real Umin, const Standard_Real Usup, const Standard_Real Vmin, - const Standard_Real Vsup, - const Extrema_ExtAlgo theProjAlgo) + const Standard_Real Vsup) { - Init (P, Surface, Umin, Usup, Vmin, Vsup, theProjAlgo); + Init (P, Surface, Umin, Usup, Vmin, Vsup); } //======================================================================= //function : GeomAPI_ProjectPointOnSurf @@ -81,11 +78,10 @@ GeomAPI_ProjectPointOnSurf::GeomAPI_ProjectPointOnSurf() const Standard_Real Usup, const Standard_Real Vmin, const Standard_Real Vsup, - const Standard_Real Tolerance, - const Extrema_ExtAlgo theProjAlgo) + const Standard_Real Tolerance) { - Init (P, Surface, Umin, Usup, Vmin, Vsup, Tolerance, theProjAlgo); + Init (P, Surface, Umin, Usup, Vmin, Vsup, Tolerance); } //======================================================================= //function : Init @@ -114,11 +110,10 @@ GeomAPI_ProjectPointOnSurf::GeomAPI_ProjectPointOnSurf() //purpose : //======================================================================= void GeomAPI_ProjectPointOnSurf::Init (const gp_Pnt& P, - const Handle(Geom_Surface)& Surface, - const Extrema_ExtAlgo theProjAlgo) + const Handle(Geom_Surface)& Surface) { - Init (P, Surface, Precision::Confusion(), theProjAlgo); + Init (P, Surface, Precision::Confusion()); } //======================================================================= //function : Init @@ -126,27 +121,15 @@ GeomAPI_ProjectPointOnSurf::GeomAPI_ProjectPointOnSurf() //======================================================================= void GeomAPI_ProjectPointOnSurf::Init(const gp_Pnt& P, const Handle(Geom_Surface)& Surface, - const Standard_Real Tolerance, - const Extrema_ExtAlgo theProjAlgo) + const Standard_Real Tolerance) { - //modified by NIZNHY-PKV Thu Apr 4 10:37:55 2002 f - //GeomAdaptor_Surface TheSurface (Surface); - //myExtPS = Extrema_ExtPS (P, TheSurface, Tolerance, Tolerance); - - //modified by NIZNHY-PKV Mon Apr 8 11:13:37 2002 f XXX Standard_Real Umin, Usup, Vmin, Vsup; Surface->Bounds(Umin, Usup, Vmin, Vsup); myGeomAdaptor.Load(Surface, Umin, Usup, Vmin, Vsup); // - //myExtPS = Extrema_ExtPS(); - myExtPS.SetAlgo(theProjAlgo); myExtPS.Initialize(myGeomAdaptor, Umin, Usup, Vmin, Vsup, Tolerance, Tolerance); myExtPS.Perform(P); - //XXXmyExtPS = Extrema_ExtPS (P, myGeomAdaptor, Tolerance, Tolerance); - //modified by NIZNHY-PKV Mon Apr 8 11:13:44 2002 t XXX - - //modified by NIZNHY-PKV Thu Apr 4 10:37:58 2002 t Init (); } @@ -160,20 +143,12 @@ GeomAPI_ProjectPointOnSurf::GeomAPI_ProjectPointOnSurf() const Standard_Real Umin, const Standard_Real Usup, const Standard_Real Vmin, - const Standard_Real Vsup, - const Extrema_ExtAlgo theProjAlgo) + const Standard_Real Vsup) { Standard_Real Tolerance = Precision::PConfusion(); - //modified by NIZNHY-PKV Thu Apr 4 10:38:23 2002 f - //GeomAdaptor_Surface TheSurface (Surface,Umin,Usup,Vmin,Vsup); - //myExtPS = Extrema_ExtPS (P, TheSurface, Tol, Tol); myGeomAdaptor.Load(Surface, Umin,Usup,Vmin,Vsup); - //myExtPS = Extrema_ExtPS(); - myExtPS.SetAlgo(theProjAlgo); myExtPS.Initialize(myGeomAdaptor, Umin, Usup, Vmin, Vsup, Tolerance, Tolerance); myExtPS.Perform(P); - //XXX myExtPS = Extrema_ExtPS (P, myGeomAdaptor, Tol, Tol); - //modified by NIZNHY-PKV Thu Apr 4 10:38:30 2002 t Init (); } @@ -187,19 +162,11 @@ GeomAPI_ProjectPointOnSurf::GeomAPI_ProjectPointOnSurf() const Standard_Real Usup, const Standard_Real Vmin, const Standard_Real Vsup, - const Standard_Real Tolerance, - const Extrema_ExtAlgo theProjAlgo) + const Standard_Real Tolerance) { - //modified by NIZNHY-PKV Thu Apr 4 10:39:10 2002 f - //GeomAdaptor_Surface TheSurface (Surface,Umin,Usup,Vmin,Vsup); - //myExtPS = Extrema_ExtPS (P, TheSurface, Tolerance, Tolerance); myGeomAdaptor.Load(Surface, Umin,Usup,Vmin,Vsup); - //myExtPS = Extrema_ExtPS(); - myExtPS.SetAlgo(theProjAlgo); myExtPS.Initialize(myGeomAdaptor, Umin, Usup, Vmin, Vsup, Tolerance, Tolerance); myExtPS.Perform(P); - //XXX myExtPS = Extrema_ExtPS (P, myGeomAdaptor, Tolerance, Tolerance); - //modified by NIZNHY-PKV Thu Apr 4 10:39:14 2002 t Init (); } //======================================================================= @@ -210,20 +177,11 @@ GeomAPI_ProjectPointOnSurf::GeomAPI_ProjectPointOnSurf() const Standard_Real Umin, const Standard_Real Usup, const Standard_Real Vmin, - const Standard_Real Vsup, - const Extrema_ExtAlgo theProjAlgo) + const Standard_Real Vsup) { Standard_Real Tolerance = Precision::PConfusion(); - //modified by NIZNHY-PKV Thu Apr 4 10:41:50 2002 f - //GeomAdaptor_Surface TheSurface (Surface,Umin,Usup,Vmin,Vsup); myGeomAdaptor.Load(Surface, Umin,Usup,Vmin,Vsup); - //modified by NIZNHY-PKV Thu Apr 4 10:42:29 2002 t - //myExtPS = Extrema_ExtPS(); - //modified by NIZNHY-PKV Thu Apr 4 10:42:32 2002 f - //myExtPS.Initialize(TheSurface, Umin, Usup, Vmin, Vsup, Tol, Tol); - myExtPS.SetAlgo(theProjAlgo); myExtPS.Initialize(myGeomAdaptor, Umin, Usup, Vmin, Vsup, Tolerance, Tolerance); - //modified by NIZNHY-PKV Thu Apr 4 10:42:39 2002 t myIsDone = Standard_False; } //======================================================================= @@ -235,19 +193,10 @@ GeomAPI_ProjectPointOnSurf::GeomAPI_ProjectPointOnSurf() const Standard_Real Usup, const Standard_Real Vmin, const Standard_Real Vsup, - const Standard_Real Tolerance, - const Extrema_ExtAlgo theProjAlgo) + const Standard_Real Tolerance) { - //modified by NIZNHY-PKV Thu Apr 4 10:43:00 2002 f - //GeomAdaptor_Surface TheSurface (Surface,Umin,Usup,Vmin,Vsup); myGeomAdaptor.Load(Surface, Umin,Usup,Vmin,Vsup); - //modified by NIZNHY-PKV Thu Apr 4 10:43:16 2002 t - //myExtPS = Extrema_ExtPS(); - //modified by NIZNHY-PKV Thu Apr 4 10:43:18 2002 f - //myExtPS.Initialize(TheSurface, Umin, Usup, Vmin, Vsup, Tolerance, Tolerance); - myExtPS.SetAlgo(theProjAlgo); myExtPS.Initialize(myGeomAdaptor, Umin, Usup, Vmin, Vsup, Tolerance, Tolerance); - //modified by NIZNHY-PKV Thu Apr 4 10:43:26 2002 t myIsDone = Standard_False; } //======================================================================= diff --git a/src/GeomAPI/GeomAPI_ProjectPointOnSurf.hxx b/src/GeomAPI/GeomAPI_ProjectPointOnSurf.hxx index 0d1ad5acda..d1eb6f5bad 100644 --- a/src/GeomAPI/GeomAPI_ProjectPointOnSurf.hxx +++ b/src/GeomAPI/GeomAPI_ProjectPointOnSurf.hxx @@ -25,7 +25,6 @@ #include #include #include -#include #include #include class Standard_OutOfRange; @@ -51,45 +50,38 @@ public: //! Create the projection of a point

on a surface //! - Standard_EXPORT GeomAPI_ProjectPointOnSurf(const gp_Pnt& P, const Handle(Geom_Surface)& Surface, const Extrema_ExtAlgo Algo = Extrema_ExtAlgo_Grad); + Standard_EXPORT GeomAPI_ProjectPointOnSurf(const gp_Pnt& P, const Handle(Geom_Surface)& Surface); //! Create the projection of a point

on a surface //! //! Create the projection of a point

on a surface //! . The solution are computed in the domain //! [Umin,Usup] [Vmin,Vsup] of the surface. - Standard_EXPORT GeomAPI_ProjectPointOnSurf(const gp_Pnt& P, const Handle(Geom_Surface)& Surface, const Standard_Real Tolerance, const Extrema_ExtAlgo Algo = Extrema_ExtAlgo_Grad); + Standard_EXPORT GeomAPI_ProjectPointOnSurf(const gp_Pnt& P, const Handle(Geom_Surface)& Surface, const Standard_Real Tolerance); - Standard_EXPORT GeomAPI_ProjectPointOnSurf(const gp_Pnt& P, const Handle(Geom_Surface)& Surface, const Standard_Real Umin, const Standard_Real Usup, const Standard_Real Vmin, const Standard_Real Vsup, const Standard_Real Tolerance, const Extrema_ExtAlgo Algo = Extrema_ExtAlgo_Grad); + Standard_EXPORT GeomAPI_ProjectPointOnSurf(const gp_Pnt& P, const Handle(Geom_Surface)& Surface, const Standard_Real Umin, const Standard_Real Usup, const Standard_Real Vmin, const Standard_Real Vsup, const Standard_Real Tolerance); //! Init the projection of a point

on a surface //! - Standard_EXPORT GeomAPI_ProjectPointOnSurf(const gp_Pnt& P, const Handle(Geom_Surface)& Surface, const Standard_Real Umin, const Standard_Real Usup, const Standard_Real Vmin, const Standard_Real Vsup, const Extrema_ExtAlgo Algo = Extrema_ExtAlgo_Grad); + Standard_EXPORT GeomAPI_ProjectPointOnSurf(const gp_Pnt& P, const Handle(Geom_Surface)& Surface, const Standard_Real Umin, const Standard_Real Usup, const Standard_Real Vmin, const Standard_Real Vsup); - Standard_EXPORT void Init (const gp_Pnt& P, const Handle(Geom_Surface)& Surface, const Standard_Real Tolerance, const Extrema_ExtAlgo Algo = Extrema_ExtAlgo_Grad); + Standard_EXPORT void Init (const gp_Pnt& P, const Handle(Geom_Surface)& Surface, const Standard_Real Tolerance); //! Init the projection of a point

on a surface //! . The solution are computed in the domain //! [Umin,Usup] [Vmin,Vsup] of the surface. - Standard_EXPORT void Init (const gp_Pnt& P, const Handle(Geom_Surface)& Surface, const Extrema_ExtAlgo Algo = Extrema_ExtAlgo_Grad); + Standard_EXPORT void Init (const gp_Pnt& P, const Handle(Geom_Surface)& Surface); - Standard_EXPORT void Init (const gp_Pnt& P, const Handle(Geom_Surface)& Surface, const Standard_Real Umin, const Standard_Real Usup, const Standard_Real Vmin, const Standard_Real Vsup, const Standard_Real Tolerance, const Extrema_ExtAlgo Algo = Extrema_ExtAlgo_Grad); + Standard_EXPORT void Init (const gp_Pnt& P, const Handle(Geom_Surface)& Surface, const Standard_Real Umin, const Standard_Real Usup, const Standard_Real Vmin, const Standard_Real Vsup, const Standard_Real Tolerance); //! Init the projection for many points on a surface //! . The solutions will be computed in the domain //! [Umin,Usup] [Vmin,Vsup] of the surface. - Standard_EXPORT void Init (const gp_Pnt& P, const Handle(Geom_Surface)& Surface, const Standard_Real Umin, const Standard_Real Usup, const Standard_Real Vmin, const Standard_Real Vsup, const Extrema_ExtAlgo Algo = Extrema_ExtAlgo_Grad); + Standard_EXPORT void Init (const gp_Pnt& P, const Handle(Geom_Surface)& Surface, const Standard_Real Umin, const Standard_Real Usup, const Standard_Real Vmin, const Standard_Real Vsup); - Standard_EXPORT void Init (const Handle(Geom_Surface)& Surface, const Standard_Real Umin, const Standard_Real Usup, const Standard_Real Vmin, const Standard_Real Vsup, const Standard_Real Tolerance, const Extrema_ExtAlgo Algo = Extrema_ExtAlgo_Grad); + Standard_EXPORT void Init (const Handle(Geom_Surface)& Surface, const Standard_Real Umin, const Standard_Real Usup, const Standard_Real Vmin, const Standard_Real Vsup, const Standard_Real Tolerance); - Standard_EXPORT void Init (const Handle(Geom_Surface)& Surface, const Standard_Real Umin, const Standard_Real Usup, const Standard_Real Vmin, const Standard_Real Vsup, const Extrema_ExtAlgo Algo = Extrema_ExtAlgo_Grad); - - //! Sets the Extrema search algorithm - Grad or Tree.
- //! By default the Extrema is initialized with Grad algorithm. - void SetExtremaAlgo(const Extrema_ExtAlgo theAlgo) - { - myExtPS.SetAlgo(theAlgo); - } + Standard_EXPORT void Init (const Handle(Geom_Surface)& Surface, const Standard_Real Umin, const Standard_Real Usup, const Standard_Real Vmin, const Standard_Real Vsup); //! Sets the Extrema search flag - MIN or MAX or MINMAX.
//! By default the Extrema is set to search the MinMax solutions. diff --git a/src/GeomInt/GeomInt_IntSS_1.cxx b/src/GeomInt/GeomInt_IntSS_1.cxx index 12a1dbc2d1..925ad0be1d 100644 --- a/src/GeomInt/GeomInt_IntSS_1.cxx +++ b/src/GeomInt/GeomInt_IntSS_1.cxx @@ -1112,9 +1112,8 @@ void GeomInt_IntSS::BuildPCurves (Standard_Real f, const gp_Pnt aP3d1 = C->Value(f); const gp_Pnt aP3d2 = C->Value(l); - anExtr.SetAlgo(Extrema_ExtAlgo_Grad); anExtr.Initialize(anAS, umin, umax, vmin, vmax, - Precision::Confusion(), Precision::Confusion()); + Precision::Confusion(), Precision::Confusion()); anExtr.Perform(aP3d1); if(ParametersOfNearestPointOnSurface(anExtr, aU, aV)) diff --git a/src/GeometryTest/GeometryTest_APICommands.cxx b/src/GeometryTest/GeometryTest_APICommands.cxx index 0731991c0f..65a2b79bf1 100644 --- a/src/GeometryTest/GeometryTest_APICommands.cxx +++ b/src/GeometryTest/GeometryTest_APICommands.cxx @@ -89,9 +89,9 @@ static void showProjSolution(Draw_Interpretor& di, static Standard_Integer proj (Draw_Interpretor& di, Standard_Integer n, const char** a) { - if ( n < 5) + if ( n != 5 && n != 7) { - Message::SendFail() << " Use proj curve/surf x y z [{extrema algo: g(grad)/t(tree)}|{u v}]"; + Message::SendFail() << " Use proj curve/surf x y z [{u v}]"; return 1; } @@ -99,10 +99,6 @@ static Standard_Integer proj (Draw_Interpretor& di, Standard_Integer n, const ch Handle(Geom_Curve) GC = DrawTrSurf::GetCurve(a[1]); Handle(Geom_Surface) GS; - Extrema_ExtAlgo aProjAlgo = Extrema_ExtAlgo_Grad; - - if (n == 6 && a[5][0] == 't') - aProjAlgo = Extrema_ExtAlgo_Tree; if (GC.IsNull()) { @@ -111,12 +107,12 @@ static Standard_Integer proj (Draw_Interpretor& di, Standard_Integer n, const ch if (GS.IsNull()) return 1; - if (n <= 6) + if (n == 5) { Standard_Real U1, U2, V1, V2; GS->Bounds(U1,U2,V1,V2); - GeomAPI_ProjectPointOnSurf proj(P,GS,U1,U2,V1,V2,aProjAlgo); + GeomAPI_ProjectPointOnSurf proj(P,GS,U1,U2,V1,V2); if (!proj.IsDone()) { di << "projection failed."; @@ -753,7 +749,7 @@ void GeometryTest::APICommands(Draw_Interpretor& theCommands) done = Standard_True; - theCommands.Add("proj", "proj curve/surf x y z [{extrema algo: g(grad)/t(tree)}|{u v}]\n" + theCommands.Add("proj", "proj curve/surf x y z [{u v}]\n" "\t\tOptional parameters are relevant to surf only.\n" "\t\tIf initial {u v} are given then local extrema is called",__FILE__, proj); diff --git a/src/ProjLib/ProjLib_ComputeApproxOnPolarSurface.cxx b/src/ProjLib/ProjLib_ComputeApproxOnPolarSurface.cxx index 491e88380e..bb5ec18d90 100644 --- a/src/ProjLib/ProjLib_ComputeApproxOnPolarSurface.cxx +++ b/src/ProjLib/ProjLib_ComputeApproxOnPolarSurface.cxx @@ -95,6 +95,7 @@ struct aFuncStruct Handle(Adaptor3d_HSurface) mySurf; // Surface where to project. Handle(Adaptor3d_HCurve) myCurve; // Curve to project. Handle(Adaptor2d_HCurve2d) myInitCurve2d; // Initial 2dcurve projection. + mutable Extrema_ExtPS myGlobExtPS; // Extrema initialized on whole parameter space of the surface Standard_Real mySqProjOrtTol; // Used to filter non-orthogonal projected point. Standard_Real myTolU; Standard_Real myTolV; @@ -190,6 +191,73 @@ static Standard_Real anOrthogSqValue(const gp_Pnt& aBasePnt, return (aFirstPart * aFirstPart + aSecondPart * aSecondPart); } +//======================================================================= +//function : checkSolution +//purpose : checks if the current solution is better than initial point +//======================================================================= +static Standard_Boolean checkSolution (const Extrema_POnSurf& theSol, + const Standard_Real theProjSqDist, + const Handle(Adaptor3d_HSurface)& theSurf, + const Standard_Real theUPeriod, + const Standard_Real theVPeriod, + const Standard_Integer theNbU, + const Standard_Integer theNbV, + const gp_Pnt& thePoint, + const Standard_Real theProjTol, + const Standard_Real theDist, + gp_Pnt2d& thePOnSurf) +{ + Standard_Real U, V; + theSol.Parameter (U, V); + Standard_Real Dist2Min = anOrthogSqValue (thePoint, theSurf, U, V); + if (Dist2Min < theProjTol && // Point is projection. + theProjSqDist < theDist + Precision::SquareConfusion()) // Point better than initial. + { + thePOnSurf.SetXY (gp_XY (U - theNbU * theUPeriod, V - theNbV * theVPeriod)); + return Standard_True; + } + return Standard_False; +} + +//======================================================================= +//function : checkSolution +//purpose : checks solutions found by extrema +//======================================================================= +static Standard_Boolean checkSolution (const Extrema_ExtPS& theExtrema, + const Handle(Adaptor3d_HSurface)& theSurf, + const Standard_Real theUPeriod, + const Standard_Real theVPeriod, + const Standard_Integer theNbU, + const Standard_Integer theNbV, + const gp_Pnt& thePoint, + const Standard_Real theProjTol, + const Standard_Real theDist, + gp_Pnt2d& theSolution) +{ + if (!theExtrema.IsDone() || !theExtrema.NbExt()) + return Standard_False; + + Standard_Real aDist2Min = RealLast(); + Standard_Integer iGoodValue = -1; + + for (Standard_Integer i = 1; i <= theExtrema.NbExt(); i++) + { + if (aDist2Min > theExtrema.SquareDistance(i)) + { + aDist2Min = theExtrema.SquareDistance(i); + iGoodValue = i; + } + } + + if (iGoodValue < 1) + return Standard_False; + + return checkSolution (theExtrema.Point (iGoodValue), theExtrema.SquareDistance (iGoodValue), + theSurf, theUPeriod, theVPeriod, theNbU, theNbV, + thePoint, theProjTol, theDist, theSolution); +} + + //======================================================================= //function : Value //purpose : (OCC217 - apo)- Compute Point2d that project on polar surface() 3D @@ -298,10 +366,8 @@ static gp_Pnt2d Function_Value(const Standard_Real theU, } // Non-analytical case. - Standard_Real Dist2Min = RealLast(); Standard_Real uperiod = theData.myPeriod[0], - vperiod = theData.myPeriod[1], - u, v; + vperiod = theData.myPeriod[1]; // U0 and V0 are the points within the initialized period. if(U0 < Uinf) @@ -379,36 +445,31 @@ static gp_Pnt2d Function_Value(const Standard_Real theU, locext.Perform(p, U0, V0); if (locext.IsDone()) { - locext.Point().Parameter(u, v); - Dist2Min = anOrthogSqValue(p, theData.mySurf, u, v); - if (Dist2Min < theData.mySqProjOrtTol && // Point is projection. - locext.SquareDistance() < aSurfPntDist + Precision::SquareConfusion()) // Point better than initial. + gp_Pnt2d pnt; + if (checkSolution (locext.Point(), locext.SquareDistance(), + theData.mySurf, uperiod, vperiod, decalU, decalV, + p, theData.mySqProjOrtTol, aSurfPntDist, pnt)) { - gp_Pnt2d pnt(u - decalU*uperiod,v - decalV*vperiod); return pnt; } } - // Perform whole param space search. - Extrema_ExtPS ext(p, SurfLittle, theData.myTolU, theData.myTolV); + gp_Pnt2d pnt; + // Perform search on the whole parametric space using preinitialized extrema. + theData.myGlobExtPS.Perform (p, uInfLi, uSupLi, vInfLi, vSupLi); + if (checkSolution (theData.myGlobExtPS, theData.mySurf, uperiod, vperiod, decalU, decalV, + p, theData.mySqProjOrtTol, aSurfPntDist, pnt)) + { + return pnt; + } + + // Perform search on the decreased parametric space. + Extrema_ExtPS ext(p, SurfLittle, theData.myTolU, theData.myTolV, Extrema_ExtFlag_MIN); if (ext.IsDone() && ext.NbExt() >= 1) { - Dist2Min = ext.SquareDistance(1); - Standard_Integer GoodValue = 1; - for (Standard_Integer i = 2 ; i <= ext.NbExt() ; i++ ) + if (checkSolution (ext, theData.mySurf, uperiod, vperiod, decalU, decalV, + p, theData.mySqProjOrtTol, aSurfPntDist, pnt)) { - if( Dist2Min > ext.SquareDistance(i)) - { - Dist2Min = ext.SquareDistance(i); - GoodValue = i; - } - } - ext.Point(GoodValue).Parameter(u, v); - Dist2Min = anOrthogSqValue(p, theData.mySurf, u, v); - if (Dist2Min < theData.mySqProjOrtTol && // Point is projection. - ext.SquareDistance(GoodValue) < aSurfPntDist + Precision::SquareConfusion()) // Point better than initial. - { - gp_Pnt2d pnt(u - decalU*uperiod,v - decalV*vperiod); return pnt; } } @@ -445,6 +506,14 @@ class ProjLib_PolarFunction : public AppCont_Function myStruct.mySqProjOrtTol = 10000.0 * Tol3d * Tol3d; myStruct.myTolU = Surf->UResolution(Tol3d); myStruct.myTolV = Surf->VResolution(Tol3d); + + Standard_Real Uinf, Usup, Vinf, Vsup; + Uinf = Surf->Surface().FirstUParameter(); + Usup = Surf->Surface().LastUParameter(); + Vinf = Surf->Surface().FirstVParameter(); + Vsup = Surf->Surface().LastVParameter(); + myStruct.myGlobExtPS.Initialize (Surf->Surface(), Uinf, Usup, Vinf, Vsup, myStruct.myTolU, myStruct.myTolV); + myStruct.myGlobExtPS.SetFlag (Extrema_ExtFlag_MIN); } ~ProjLib_PolarFunction() {} diff --git a/src/TopOpeBRepTool/TopOpeBRepTool_PROJECT.cxx b/src/TopOpeBRepTool/TopOpeBRepTool_PROJECT.cxx index d800c5b839..bf2702872b 100644 --- a/src/TopOpeBRepTool/TopOpeBRepTool_PROJECT.cxx +++ b/src/TopOpeBRepTool/TopOpeBRepTool_PROJECT.cxx @@ -198,14 +198,13 @@ Standard_EXPORT Standard_Boolean FUN_tool_projPonC2D(const gp_Pnt& P, Standard_EXPORT Standard_Boolean FUN_tool_projPonS(const gp_Pnt& P, const Handle(Geom_Surface)& S, gp_Pnt2d& UV,Standard_Real& dist, - const Extrema_ExtFlag anExtFlag, - const Extrema_ExtAlgo anExtAlgo) + const Extrema_ExtFlag anExtFlag) { Standard_Real UMin, UMax, VMin, VMax; GeomAPI_ProjectPointOnSurf PonS; // S->Bounds(UMin, UMax, VMin, VMax); - PonS.Init(S, UMin, UMax, VMin, VMax, anExtAlgo); + PonS.Init(S, UMin, UMax, VMin, VMax); Extrema_ExtPS& anExtPS = const_cast(PonS.Extrema()); anExtPS.SetFlag(anExtFlag); // @@ -279,11 +278,10 @@ Standard_EXPORT Standard_Boolean FUN_tool_projPonboundedF(const gp_Pnt& P,const // ---------------------------------------------------------------------- Standard_EXPORT Standard_Boolean FUN_tool_projPonF(const gp_Pnt& P,const TopoDS_Face& F, gp_Pnt2d& UV,Standard_Real& dist, - const Extrema_ExtFlag anExtFlag, - const Extrema_ExtAlgo anExtAlgo) + const Extrema_ExtFlag anExtFlag) { dist = 1.; Handle(Geom_Surface) S = BRep_Tool::Surface(F); - Standard_Boolean ok = FUN_tool_projPonS(P,S,UV,dist, anExtFlag, anExtAlgo); + Standard_Boolean ok = FUN_tool_projPonS(P,S,UV,dist, anExtFlag); return ok; } diff --git a/src/TopOpeBRepTool/TopOpeBRepTool_PROJECT.hxx b/src/TopOpeBRepTool/TopOpeBRepTool_PROJECT.hxx index 42adc2362f..6361c20678 100644 --- a/src/TopOpeBRepTool/TopOpeBRepTool_PROJECT.hxx +++ b/src/TopOpeBRepTool/TopOpeBRepTool_PROJECT.hxx @@ -27,7 +27,6 @@ #include #include #include -#include // ---------------------------------------------------------------------- // project point

on geometries (curve ,surface ) @@ -42,8 +41,7 @@ Standard_EXPORT Standard_Boolean FUN_tool_projPonC2D(const gp_Pnt& P,const Stand Standard_EXPORT Standard_Boolean FUN_tool_projPonC2D(const gp_Pnt& P,const BRepAdaptor_Curve2d& BAC2D,const Standard_Real pmin,const Standard_Real pmax,Standard_Real& param,Standard_Real& dist); Standard_EXPORT Standard_Boolean FUN_tool_projPonC2D(const gp_Pnt& P,const BRepAdaptor_Curve2d& BAC2D,Standard_Real& param,Standard_Real& dist); Standard_EXPORT Standard_Boolean FUN_tool_projPonS(const gp_Pnt& P,const Handle(Geom_Surface)& S,gp_Pnt2d& UV,Standard_Real& dist, - const Extrema_ExtFlag anExtFlag=Extrema_ExtFlag_MINMAX, - const Extrema_ExtAlgo anExtAlgo=Extrema_ExtAlgo_Grad); + const Extrema_ExtFlag anExtFlag=Extrema_ExtFlag_MINMAX); // ---------------------------------------------------------------------- // project point

on topologies (edge ,face ) @@ -52,7 +50,6 @@ Standard_EXPORT Standard_Boolean FUN_tool_projPonE(const gp_Pnt& P,const Standar Standard_EXPORT Standard_Boolean FUN_tool_projPonE(const gp_Pnt& P,const TopoDS_Edge& E,Standard_Real& param,Standard_Real& dist); Standard_EXPORT Standard_Boolean FUN_tool_projPonboundedF(const gp_Pnt& P,const TopoDS_Face& F,gp_Pnt2d& UV,Standard_Real& dist); Standard_EXPORT Standard_Boolean FUN_tool_projPonF(const gp_Pnt& P,const TopoDS_Face& F,gp_Pnt2d& UV,Standard_Real& dist, - const Extrema_ExtFlag anExtFlag=Extrema_ExtFlag_MINMAX, - const Extrema_ExtAlgo anExtAlgo=Extrema_ExtAlgo_Grad); + const Extrema_ExtFlag anExtFlag=Extrema_ExtFlag_MINMAX); #endif diff --git a/tests/bugs/modalg_6/bug26356 b/tests/bugs/modalg_6/bug26356 index 0049b2f430..67b1927d1c 100644 --- a/tests/bugs/modalg_6/bug26356 +++ b/tests/bugs/modalg_6/bug26356 @@ -7,31 +7,23 @@ puts "" ############################################# restore [locate_data_file OCC26356-f.brep] b1 -restore [locate_data_file OCC26356-w.brep] b2 - -explode b2 v point p1 31350.009765625 7100 -2.17374844144233e-013 -set bug_info_1 [projponf b1 p1 -min -g] -set bug_info_1 [string trim [string range $bug_info_1 [expr {[string first "=" $bug_info_1] + 1}] [expr {[string length $bug_info_1] - 1}]]] -set bug_info_1 [string trim [string range $bug_info_1 0 [expr {[string first " " $bug_info_1] - 1}]]] -set bug_info_2 [projponf b1 p1 -minmax -g] -set bug_info_2 [string trim [string range $bug_info_2 [expr {[string first "=" $bug_info_2] + 1}] [expr {[string length $bug_info_2] - 1}]]] -set bug_info_2 [string trim [string range $bug_info_2 0 [expr {[string first " " $bug_info_2] - 1}]]] + +regexp {proj dist = ([0-9+-.eE]*)} [projponf b1 p1 -min] full dist1_min +regexp {proj dist = ([0-9+-.eE]*)} [projponf b1 p1 -minmax] full dist1_minmax point p2 29200.099609375 7100 -2.17374753743702e-013 -set bug_info_3 [projponf b1 p2 -min -g] -set bug_info_3 [string trim [string range $bug_info_3 [expr {[string first "=" $bug_info_3] + 1}] [expr {[string length $bug_info_3] - 1}]]] -set bug_info_3 [string trim [string range $bug_info_3 0 [expr {[string first " " $bug_info_3] - 1}]]] -set bug_info_4 [projponf b1 p2 -minmax -g] -set bug_info_4 [string trim [string range $bug_info_4 [expr {[string first "=" $bug_info_4] + 1}] [expr {[string length $bug_info_4] - 1}]]] -set bug_info_4 [string trim [string range $bug_info_4 0 [expr {[string first " " $bug_info_4] - 1}]]] -if {$bug_info_1 != $bug_info_2} { - puts "ERROR: OCC26356 is reproduced." - puts "For point #1: distance min is: ${bug_info_1}, distance minmax is: ${bug_info_2}." +regexp {proj dist = ([0-9+-.eE]*)} [projponf b1 p2 -min] full dist2_min +regexp {proj dist = ([0-9+-.eE]*)} [projponf b1 p2 -minmax] full dist2_minmax + +if {[expr abs ($dist1_min - $dist1_minmax)] > 1.e-10} { + puts "ERROR: different extrema results in different modes" + puts "For point #1: distance min is: ${dist1_min}, distance minmax is: ${dist1_minmax}." } -if {$bug_info_3 != $bug_info_4} { - puts "ERROR: OCC26356 is reproduced." - puts "For point #2: distance min is: ${bug_info_3}, distance minmax is: ${bug_info_4}." + +if {[expr abs ($dist2_min - $dist2_minmax)] > 1.e-10} { + puts "ERROR: different extrema results in different modes" + puts "For point #2: distance min is: ${dist2_min}, distance minmax is: ${dist2_minmax}." } diff --git a/tests/bugs/moddata_3/bug24068 b/tests/bugs/moddata_3/bug24068 index ec6c004658..b34c6d19d8 100644 --- a/tests/bugs/moddata_3/bug24068 +++ b/tests/bugs/moddata_3/bug24068 @@ -18,7 +18,7 @@ point p_1 100 86.6025403784439 2.25000977226544 vertex v_1 100 86.6025403784439 2.25000977226544 set GOOD_DIST_1 2.0175535360778957e-14 -set log_1 [projponf f p_1 -min -t] +set log_1 [projponf f p_1 -min] regexp {proj dist = ([-0-9.+eE]+)} ${log_1} full distmax_1 if { [expr abs(${distmax_1} - ${GOOD_DIST_1})] > ${CMP_TOL} } { puts "Error: Wrong distanse (# 1)" @@ -39,7 +39,7 @@ point p_2 100 86.6025403784439 8.2500100656622 vertex v_2 100 86.6025403784439 8.2500100656622 set GOOD_DIST_2 9.9491842071163076e-14 -set log_2 [projponf f p_2 -min -t] +set log_2 [projponf f p_2 -min] regexp {proj dist = ([-0-9.+eE]+)} ${log_2} full distmax_2 if { [expr abs(${distmax_2} - ${GOOD_DIST_2})] > ${CMP_TOL} } { puts "Error: Wrong distanse (# 2)" @@ -60,7 +60,7 @@ point p_3 100 86.602540378443891 11.249990478996615 vertex v_3 100 86.602540378443891 11.249990478996615 set GOOD_DIST_3 2.8421709430404007e-14 -set log_3 [projponf f p_3 -min -t] +set log_3 [projponf f p_3 -min] regexp {proj dist = ([-0-9.+eE]+)} ${log_3} full distmax_3 if { [expr abs(${distmax_3} - ${GOOD_DIST_3})] > ${CMP_TOL} } { puts "Error: Wrong distanse (# 3)" diff --git a/tests/bugs/moddata_3/bug24134 b/tests/bugs/moddata_3/bug24134 index 3b4eb75887..9a76d1d8d7 100644 --- a/tests/bugs/moddata_3/bug24134 +++ b/tests/bugs/moddata_3/bug24134 @@ -15,20 +15,10 @@ point p 934.419505115097 1387.10553740067 8.42056376938594e-014 set GOOD_DIST 1.0481408664017105e-12 set CMP_TOL 5.0e-12 -# 1 -set log_t [projponf f p -t] -regexp {proj dist = ([-0-9.+eE]+)} ${log_t} full distmax_t -if { [expr abs(${distmax_t} - ${GOOD_DIST})] > ${CMP_TOL} } { - puts "Error: Wrong intersection point (t-option)" +set log_t [projponf f p -min] +regexp {proj dist = ([-0-9.+eE]+)} ${log_t} full distmax +if { [expr abs(${distmax} - ${GOOD_DIST})] > ${CMP_TOL} } { + puts "Error: Wrong intersection point" } else { - puts "OK: Good intersection point (t-option)" -} - -# 2 -set log_g [projponf f p -g] -regexp {proj dist = ([-0-9.+eE]+)} ${log_g} full distmax_g -if { [expr abs(${distmax_g} - ${GOOD_DIST})] > ${CMP_TOL} } { - puts "Error: Wrong intersection point (g-option)" -} else { - puts "OK: Good intersection point (g-option)" + puts "OK: Good intersection point" } diff --git a/tests/bugs/moddata_3/bug24138 b/tests/bugs/moddata_3/bug24138 index 18c0506e45..d210d76aa7 100755 --- a/tests/bugs/moddata_3/bug24138 +++ b/tests/bugs/moddata_3/bug24138 @@ -15,7 +15,7 @@ explode s f copy s_1 f point p 0.753071156928785 4.98580193823337 0 -set proj_fp [projponf f p -t] +set proj_fp [projponf f p] regexp {proj dist = ([-0-9.+eE]+)} ${proj_fp} full dist regexp {uvproj = ([-0-9.+eE]+) ([-0-9.+eE]+)} ${proj_fp} full uproj vproj regexp {pproj = ([-0-9.+eE]+) ([-0-9.+eE]+) ([-0-9.+eE]+)} ${proj_fp} full proj1 proj2 diff --git a/tests/bugs/xde/bug22826 b/tests/bugs/xde/bug22826 index c62c3316f2..9d3c6655a3 100755 --- a/tests/bugs/xde/bug22826 +++ b/tests/bugs/xde/bug22826 @@ -11,8 +11,6 @@ set BugNumber OCC22826 restore [locate_data_file bug22610_f1.brep] a mksurface s1 a -proj s1 1500 1500 500 g -renamevar ext_2 res -proj s1 1500 1500 500 t +proj s1 1500 1500 500 -checklength res -l -equal ext_1 +checklength ext_1 -l 6.8749734766305481 diff --git a/tests/perf/modalg/bug23906 b/tests/perf/modalg/bug23906 index 9df38743fc..55b76f9b00 100644 --- a/tests/perf/modalg/bug23906 +++ b/tests/perf/modalg/bug23906 @@ -12,6 +12,6 @@ point p 3.5527136788005e-015 100 100 dchrono h restart -projponf f p -min -t +projponf f p -min dchrono h stop counter projponf \ No newline at end of file -- 2.39.5