From c6991f13e71585d294482f6690d5aae3f8298a2f 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/BRepTest/BRepTest_ExtremaCommands.cxx | 2 +- src/BRepTest/BRepTest_SurfaceCommands.cxx | 14 +- src/BVH/BVH_BoxSet.hxx | 12 + src/BVH/BVH_Tools.hxx | 19 +- 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 | 41 +- src/Extrema/Extrema_ExtPS.hxx | 30 +- src/Extrema/Extrema_GenExtPS.cxx | 1629 +++++++++-------- src/Extrema/Extrema_GenExtPS.hxx | 398 ++-- src/Extrema/Extrema_POnSurfParams.lxx | 4 +- src/Extrema/FILES | 1 - 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 +- 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 +- 34 files changed, 1360 insertions(+), 1246 deletions(-) delete mode 100644 src/Extrema/Extrema_ExtAlgo.hxx diff --git a/src/BRepExtrema/BRepExtrema_DistShapeShape.cxx b/src/BRepExtrema/BRepExtrema_DistShapeShape.cxx index c98a2712ce..76a3d089d7 100644 --- a/src/BRepExtrema/BRepExtrema_DistShapeShape.cxx +++ b/src/BRepExtrema/BRepExtrema_DistShapeShape.cxx @@ -149,7 +149,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) @@ -194,8 +194,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) { // } @@ -206,16 +205,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); @@ -230,16 +227,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/BRepTest/BRepTest_ExtremaCommands.cxx b/src/BRepTest/BRepTest_ExtremaCommands.cxx index 135356f278..7be9053ee0 100644 --- a/src/BRepTest/BRepTest_ExtremaCommands.cxx +++ b/src/BRepTest/BRepTest_ExtremaCommands.cxx @@ -77,7 +77,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 8c925cbcbb..67854ae6eb 100644 --- a/src/BRepTest/BRepTest_SurfaceCommands.cxx +++ b/src/BRepTest/BRepTest_SurfaceCommands.cxx @@ -617,9 +617,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 @@ -642,7 +642,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) { @@ -655,12 +654,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 @@ -677,7 +670,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); @@ -766,7 +758,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_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/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 969c8b64ce..8240e95596 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) { } @@ -166,7 +167,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), @@ -176,7 +178,8 @@ Extrema_ExtPExtS::Extrema_ExtPExtS (const gp_Pnt& myS (theS), myIsAnalyticallyComputable(Standard_False), myDone(Standard_False), - myNbExt(0) + myNbExt(0), + myExtPS (theExtPS) { Initialize (theS, theUmin, @@ -193,7 +196,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), @@ -203,7 +207,8 @@ Extrema_ExtPExtS::Extrema_ExtPExtS (const gp_Pnt& myS (theS), myIsAnalyticallyComputable(Standard_False), myDone(Standard_False), - myNbExt(0) + myNbExt(0), + myExtPS (theExtPS) { Initialize (theS, theS->FirstUParameter(), @@ -253,15 +258,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); } } @@ -280,11 +288,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; } @@ -443,10 +449,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; } //============================================================================= @@ -462,7 +466,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); } //============================================================================= @@ -479,7 +483,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 b4a03c85f0..1dc3d55cf2 100644 --- a/src/Extrema/Extrema_ExtPS.cxx +++ b/src/Extrema/Extrema_ExtPS.cxx @@ -157,12 +157,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(), @@ -171,6 +167,8 @@ Extrema_ExtPS::Extrema_ExtPS (const gp_Pnt& theP, theTolU, theTolV); + myExtPS->SetTarget (theTarget); + Perform (theP); } @@ -187,12 +185,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, @@ -201,6 +195,8 @@ Extrema_ExtPS::Extrema_ExtPS (const gp_Pnt& theP, theTolU, theTolV); + myExtPS->SetTarget (theTarget); + Perform (theP); } @@ -251,7 +247,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(); @@ -292,7 +291,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 { @@ -318,7 +317,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 { @@ -339,13 +338,13 @@ void Extrema_ExtPS::Perform(const gp_Pnt& thePoint) default: { - myExtPS.Perform (thePoint); - myDone = myExtPS.IsDone(); + myExtPS->Perform (thePoint); + 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; @@ -411,10 +410,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..722938471c 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,10 +76,24 @@ 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 @@ -107,9 +124,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 +144,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; diff --git a/src/Extrema/Extrema_GenExtPS.cxx b/src/Extrema/Extrema_GenExtPS.cxx index dcd5a8f94f..b8d2e80ffd 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,971 +13,981 @@ // 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 - -//IMPLEMENT_HARRAY1(Extrema_HArray1OfSphere) -class Bnd_SphereUBTreeSelector : public Extrema_UBTreeOfSphere::Selector -{ - public: - - Bnd_SphereUBTreeSelector (const Handle(Bnd_HArray1OfSphere)& theSphereArray, -Bnd_Sphere& theSol) - : myXYZ(0,0,0), - mySphereArray(theSphereArray), - mySol(theSol) - { - } - - void DefineCheckPoint( const gp_Pnt& theXYZ ) - { myXYZ = theXYZ; } - - Bnd_Sphere& Sphere() const - { return mySol; } - - 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&); +#include +#include -}; +IMPLEMENT_STANDARD_RTTIEXT (Extrema_GenExtPS, Standard_Transient) -class Bnd_SphereUBTreeSelectorMin : public Bnd_SphereUBTreeSelector +// Static methods definition +namespace { -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 ); - } - - Standard_Boolean Accept(const Standard_Integer&); - -private: - Standard_Real myMinDist; -}; - -Standard_Boolean Bnd_SphereUBTreeSelectorMin::Accept(const Standard_Integer& theInd) +//======================================================================= +//function : fillParams +//purpose : +//======================================================================= +static void fillParams (const TColStd_Array1OfReal& theKnots, + Standard_Integer theDegree, + Standard_Real theParMin, + Standard_Real theParMax, + Handle (TColStd_HArray1OfReal)& theParams, + Standard_Integer theNbSample) { - const Bnd_Sphere& aSph = mySphereArray->Value(theInd); - Standard_Real aCurDist; + 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++) + { + if (theKnots (i + 1) < theParMin + Precision::PConfusion()) + continue; -// if ( (aCurDist = aSph.SquareDistance(myXYZ.XYZ())) < mySol.SquareDistance(myXYZ.XYZ()) ) - if ( (aCurDist = aSph.Distance(myXYZ.XYZ())) < mySol.Distance(myXYZ.XYZ()) ) + Standard_Real aStep = (theKnots (i + 1) - theKnots (i)) / Max (theDegree, 2); + Standard_Integer k = 1; + for (; k <= theDegree; k++) { - mySol = aSph; - if ( aCurDist < myMinDist ) - myMinDist = aCurDist; - - return Standard_True; + Standard_Real aPar = theKnots (i) + k * aStep; + if (aPar > theParMax - Precision::PConfusion()) + break; + if (aPar > aPrevPar + Precision::PConfusion()) + { + aParams.Append (aPar); + aPrevPar = aPar; + } } - - return Standard_False; -} - -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 ); } - Standard_Boolean Accept(const Standard_Integer&); - -private: - Standard_Real myMaxDist; -}; - -Standard_Boolean Bnd_SphereUBTreeSelectorMax::Accept(const Standard_Integer& theInd) -{ - const Bnd_Sphere& aSph = mySphereArray->Value(theInd); - Standard_Real aCurDist; + aParams.Append (theParMax); + Standard_Integer nbPar = aParams.Length(); -// 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; + // In case of an insufficient number of points the grid will be built later + if (nbPar < theNbSample) + return; - return Standard_True; - } + theParams = new TColStd_HArray1OfReal (1, nbPar); + for (i = 0; i < nbPar; i++) + theParams->SetValue (i + 1, aParams (i)); +} - return Standard_False; +//======================================================================= +//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); } -//============================================================================= - -/*----------------------------------------------------------------------------- -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. ------------------------------------------------------------------------------*/ - -Extrema_GenExtPS::Extrema_GenExtPS() +//======================================================================= +//function : fillSqDist +//purpose : +//======================================================================= +static void fillSqDist (Extrema_POnSurfParams& theParams, + const gp_Pnt& thePoint) { - myDone = Standard_False; - myInit = Standard_False; - myFlag = Extrema_ExtFlag_MINMAX; - myAlgo = Extrema_ExtAlgo_Grad; + if (theParams.GetSqrDistance() < -0.5) + theParams.SetSqrDistance (theParams.Value().SquareDistance (thePoint)); } +} -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) +//======================================================================= +//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()), + myTarget (Extrema_ExtFlag_MINMAX), + mySqDistance (-1), + myIsDone (Standard_False) { - Initialize(S, NbU, NbV, TolU, TolV); - Perform(P); } -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 : 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(S, NbU, NbV, Umin, Usup, Vmin, Vsup, TolU, TolV); - Perform(P); + Initialize (theS, theNbU, theNbV, theTolU, theTolV); + Perform (theP); } - -void Extrema_GenExtPS::Initialize(const Adaptor3d_Surface& S, - const Standard_Integer NbU, - const Standard_Integer NbV, - const Standard_Real TolU, - const Standard_Real TolV) +//======================================================================= +//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) { - myumin = S.FirstUParameter(); - myusup = S.LastUParameter(); - myvmin = S.FirstVParameter(); - myvsup = S.LastVParameter(); - Initialize(S,NbU,NbV,myumin,myusup,myvmin,myvsup,TolU,TolV); + 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); +} -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) +//======================================================================= +//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) { - 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(); + myS = (Adaptor3d_SurfacePtr)&theS; + myUMin = theUMin; + myUMax = theUMax; + myVMin = theVMin; + myVMax = theVMax; + myNbUSamples = theNbU; + myNbVSamples = theNbV; + myTolU = theTolU; + myTolV = theTolV; + + if (myNbUSamples < 2 || myNbVSamples < 2) + { + throw Standard_OutOfRange ("Extrema_GenExtPS::Initialize - number of samples is too small"); + } + + myF.Initialize (theS); + + myGridBoxSet.Nullify(); myUParams.Nullify(); myVParams.Nullify(); - myInit = Standard_False; } -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 : Perform +//purpose : +//======================================================================= +void Extrema_GenExtPS::Perform (const gp_Pnt& thePoint) { - 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++ ) + myIsDone = Standard_False; + myPoint = BVH_Vec3d (thePoint.X(), thePoint.Y(), thePoint.Z()); + myF.SetPoint (thePoint); + mySolutions.clear(); + + if (myUParams.IsNull() || myVParams.IsNull()) { - if ( theKnots(i+1) < theParMin + Precision::PConfusion()) - continue; + // Prepare surface sampling + BuildGrid(); + } + + if (myGridBoxSet.IsNull() || myGridBoxSet->IsDirty()) + { + BuildTree(); + } - Standard_Real aStep = (theKnots(i+1) - theKnots(i))/Max(theDegree,2); - Standard_Integer k =1; - for( ; k <= theDegree ; k++) + if (myTarget == Extrema_ExtFlag_MIN) + mySqDistance = RealLast(); + else if (myTarget == Extrema_ExtFlag_MAX) + mySqDistance = -1; + + // Fill Square distances with default values + for (int iU = 0; iU <= myNbUSamples + 1; ++iU) + { + for (int iV = 0; iV <= myNbVSamples + 1; ++iV) { - Standard_Real aPar = theKnots(i) + k * aStep; - if(aPar > theParMax - Precision::PConfusion()) - break; - if(aPar > aPrevPar + Precision::PConfusion() ) + myPoints->ChangeValue (iU, iV).SetSqrDistance (-1.); + + if (iU <= myNbUSamples && iV <= myNbVSamples) + myFacePntParams->ChangeValue (iU, iV).SetSqrDistance (-1.); + + if (iU > 0 && iU <= myNbUSamples && iV > 0 && iV <= myNbVSamples) { - aParams.Append(aPar); - aPrevPar = aPar; + if (iU < myNbUSamples) + myUEdgePntParams->ChangeValue (iU, iV).SetSqrDistance (-1.); + if (iV < myNbVSamples) + myVEdgePntParams->ChangeValue (iU, iV).SetSqrDistance (-1.); } } - } - 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) -{ - //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) + if (myTarget == Extrema_ExtFlag_MAX || myTarget == Extrema_ExtFlag_MINMAX) { - Handle(Geom_BSplineSurface) aBspl = theSurf.BSpline(); - if(!aBspl.IsNull()) + for (int iV = 0; iV <= myNbVSamples + 1; ++iV) { - 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); + myPoints->ChangeValue (0, iV).SetSqrDistance (-0.1); + myPoints->ChangeValue (myNbUSamples + 1, iV).SetSqrDistance (-0.1); } - } - //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); + for (int iU = 1; iU <= myNbUSamples; ++iU) + { + myPoints->ChangeValue (iU, 0).SetSqrDistance (-0.1); + myPoints->ChangeValue (iU, myNbVSamples + 1).SetSqrDistance (-0.1); + } } - //creation points for surfaces based on BSpline or Bezier curves - else if(theSurf.GetType() == GeomAbs_SurfaceOfRevolution || - theSurf.GetType() == GeomAbs_SurfaceOfExtrusion) + + if (myTarget == Extrema_ExtFlag_MIN || myTarget == Extrema_ExtFlag_MINMAX) { - Handle(TColStd_HArray1OfReal) anArrKnots; - Standard_Integer aDegree = 0; - if(theSurf.BasisCurve()->Curve().GetType() == GeomAbs_BSplineCurve) + // Fill boundary with RealLast square distance. + for (int iV = 0; iV <= myNbVSamples; ++iV) { - Handle(Geom_BSplineCurve) aBspl = theSurf.BasisCurve()->Curve().BSpline(); - if(!aBspl.IsNull()) - { - anArrKnots = new TColStd_HArray1OfReal(1,aBspl->NbKnots()); - aBspl->Knots( anArrKnots->ChangeArray1() ); - aDegree = aBspl->Degree(); - - } + myFacePntParams->ChangeValue (0, iV).SetSqrDistance (RealLast()); + myFacePntParams->ChangeValue (myNbUSamples, iV).SetSqrDistance (RealLast()); + } + + for (int iU = 1; iU < myNbUSamples; ++iU) + { + myFacePntParams->ChangeValue (iU, 0).SetSqrDistance (RealLast()); + myFacePntParams->ChangeValue (iU, myNbVSamples).SetSqrDistance (RealLast()); + } + } + if (myTarget == Extrema_ExtFlag_MINMAX) + { + // Perform standard solution search (no tree) + const Standard_Integer aNbCells = myGridBoxSet->Size(); + for (Standard_Integer i = 0; i < aNbCells; ++i) + { + Accept (i, 0.0); } - if(theSurf.BasisCurve()->Curve().GetType() == GeomAbs_BezierCurve) + + // Copy solutions + for (Standard_Integer i = 1; i <= myF.NbExt (); ++i) { - 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()); - aDegree = aBez->Degree(); - - } + mySolutions.push_back (Extrema_GenExtPS::ExtPSResult (myF.Point (i), myF.SquareDistance (i))); } - if(anArrKnots.IsNull()) - return; - if( theSurf.GetType() == GeomAbs_SurfaceOfRevolution ) - fillParams( anArrKnots->Array1(), aDegree, myvmin, myvsup, myVParams, myvsample); - else - fillParams( anArrKnots->Array1(), aDegree, myumin, myusup, myUParams, myusample); } - //update the number of points in sample - if(!myUParams.IsNull()) - myusample = myUParams->Length(); - if( !myVParams.IsNull()) - myvsample = myVParams->Length(); - + else + { + Select (myGridBoxSet->BVH()); + } + + // Sort solutions + std::sort (mySolutions.begin(), mySolutions.end()); } -/* - * 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 : BuildGrid +//purpose : +//======================================================================= +void Extrema_GenExtPS::BuildGrid() { - const Standard_Real aSqrDist01 = - theParam0.Value().SquareDistance(theParam1.Value()); + GetGridPoints (*myS); - if (aSqrDist01 <= theDiffTol) + //build grid in other cases + if (myUParams.IsNull()) { - // The points are confused. Get the first point and change its type. - return theParam0; + fillParams (myUMin, myUMax, myUParams, myNbUSamples); } - else + + if (myVParams.IsNull()) { - const Standard_Real aDiffDist = - Abs(theParam0.GetSqrDistance() - theParam1.GetSqrDistance()); + fillParams (myVMin, myVMax, myVParams, myNbVSamples); + } + + myPoints = new Extrema_HArray2OfPOnSurfParams (0, myNbUSamples + 1, 0, myNbVSamples + 1); - if (aDiffDist >= aSqrDist01 - theDiffTol) + for (int iU = 1; iU <= myNbUSamples; iU++) + { + Standard_Real U = myUParams->Value (iU); + for (int iV = 1; iV <= myNbVSamples; iV++) { - // The shortest distance is one of the nodes. - if (theParam0.GetSqrDistance() > theParam1.GetSqrDistance()) - { - // The shortest distance is the point 1. - return theParam1; - } - else + 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); + aParam.SetSqrDistance (-1.); + myPoints->SetValue (iU, iV, aParam); + } + } + + myFacePntParams = new Extrema_HArray2OfPOnSurfParams (0, myNbUSamples, 0, myNbVSamples); + + myUEdgePntParams = new Extrema_HArray2OfPOnSurfParams (1, myNbUSamples - 1, 1, myNbVSamples); + myVEdgePntParams = new Extrema_HArray2OfPOnSurfParams (1, myNbUSamples, 1, myNbVSamples - 1); +} + +//======================================================================= +//function : BuildTree +//purpose : +//======================================================================= +void Extrema_GenExtPS::BuildTree() +{ + // The tree is not required for MINMAX mode, + // so fill the tree with elements with empty boxes + if (myGridBoxSet.IsNull()) + { + myGridBoxSet = new BVH_BoxSet(new BVH_LinearBuilder()); + + myGridBoxSet->SetSize (myNbUSamples * myNbVSamples); + + for (int iU = 1; iU <= myNbUSamples; iU++) + { + for (int iV = 1; iV <= myNbVSamples; iV++) { - // The shortest distance is the point 0. - return theParam0; + myGridBoxSet->Add (GridCell (iU, iV), BVH_Box()); } } - else + } + + if (myGridBoxSet->IsDirty() && myTarget != Extrema_ExtFlag_MINMAX) + { + // Fill the tree with the real boxes + const Standard_Integer aNbCells = myGridBoxSet->Size(); + for (Standard_Integer iCell = 0; iCell < aNbCells; ++iCell) { - // 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]; + const GridCell& aCell = myGridBoxSet->Element (iCell); + Standard_Integer iU = aCell.myUInd, iV = aCell.myVInd; - theParam0.Parameter(aU[0], aV[0]); - theParam1.Parameter(aU[1], aV[1]); + Standard_Integer aUCoeff = (iU < myNbUSamples) ? 1 : 0; + Standard_Integer aVCoeff = (iV < myNbVSamples) ? 1 : 0; - Standard_Real aUPar = aU[0]; - Standard_Real aVPar = aV[0]; + // Build box for the cell + Bnd_Box aBox; - if (IsUEdge) - { - aUPar += aRatio*(aU[1] - aU[0]); - } - else - { - aVPar += aRatio*(aV[1] - aV[0]); - } + for (int i = 0; i < 2; ++i) + for (int j = 0; j < 2; ++j) + aBox.Add (myPoints->Value (iU + i * aUCoeff, iV + j * aVCoeff).Value()); + + //aBox.Add (myS->Value ((U1 + U2) * 0.5, V1)); + //aBox.Add (myS->Value ((U1 + U2) * 0.5, V2)); + //aBox.Add (myS->Value (U1, (V1 + V2) * 0.5)); + //aBox.Add (myS->Value (U2, (V1 + V2) * 0.5)); + 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); - myGridParam.SetParameters(aUPar, aVPar, myS->Value(aUPar, aVPar)); - Standard_Integer anIndices[2]; + gp_Pnt aPMid = myS->Value ((U1 + U2) * 0.5, (V1 + V2) * 0.5); + aBox.Add (aPMid); - 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; + // Enlarge box to make sure the whole cell is covered + aBox.Enlarge (Sqrt (aBox.SquareExtent())); + + //aBox.Enlarge (Precision::Confusion() + + // gp_Lin (aPMin.Value(), gp_Vec (aPMin.Value(), aPMax.Value())).Distance (aPMid)); + + myGridBoxSet->UpdateBox (iCell, Bnd_Tools::Bnd2BVH (aBox)); } + myGridBoxSet->Build(); } } -void Extrema_GenExtPS::BuildGrid(const gp_Pnt &thePoint) +//======================================================================= +//function : GetGridPoints +//purpose : +//======================================================================= +void Extrema_GenExtPS::GetGridPoints (const Adaptor3d_Surface& theSurf) { - 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() ) + // 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()) { - 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); + TColStd_Array1OfReal aUKnots (1, aBspl->NbUKnots()); + aBspl->UKnots (aUKnots); + TColStd_Array1OfReal aVKnots (1, aBspl->NbVKnots()); + aBspl->VKnots (aVKnots); + fillParams (aUKnots, aBspl->UDegree(), myUMin, myUMax, myUParams, myNbUSamples); + fillParams (aVKnots, aBspl->VDegree(), myVMin, myVMax, myVParams, myNbVSamples); } - - if( myVParams.IsNull()) + } + + // Calculation parametric points for Bezier surfaces + else if (theSurf.GetType() == GeomAbs_BezierSurface) + { + Handle (Geom_BezierSurface) aBezier = theSurf.Bezier(); + if (!aBezier.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); + 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, myUParams, myNbUSamples); + fillParams (aVKnots, aBezier->VDegree(), myVMin, myVMax, myVParams, myNbVSamples); } + } - //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); + // creation points for surfaces based on BSpline or Bezier curves + else if (theSurf.GetType() == GeomAbs_SurfaceOfRevolution || + theSurf.GetType() == GeomAbs_SurfaceOfExtrusion) + { + Handle (TColStd_HArray1OfReal) anArrKnots; + Standard_Integer aDegree = 0; + if (theSurf.BasisCurve()->Curve().GetType() == GeomAbs_BSplineCurve) + { + Handle (Geom_BSplineCurve) aBspl = theSurf.BasisCurve()->Curve().BSpline(); + if (!aBspl.IsNull()) + { + anArrKnots = new TColStd_HArray1OfReal (1, aBspl->NbKnots()); + aBspl->Knots (anArrKnots->ChangeArray1()); + aDegree = aBspl->Degree(); } } + if (theSurf.BasisCurve()->Curve().GetType() == GeomAbs_BezierCurve) + { + 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()); + aDegree = aBez->Degree(); - myFacePntParams = - new Extrema_HArray2OfPOnSurfParams(0, myusample, 0, myvsample); + } + } + if (anArrKnots.IsNull()) + return; + if (theSurf.GetType() == GeomAbs_SurfaceOfRevolution) + fillParams (anArrKnots->Array1(), aDegree, myVMin, myVMax, myVParams, myNbVSamples); + else + fillParams (anArrKnots->Array1(), aDegree, myUMin, myUMax, myUParams, myNbUSamples); + } - myUEdgePntParams = - new Extrema_HArray2OfPOnSurfParams(1, myusample - 1, 1, myvsample); - myVEdgePntParams = - new Extrema_HArray2OfPOnSurfParams(1, myusample, 1, myvsample - 1); + // Update the number of points in sample + if (!myUParams.IsNull()) + myNbUSamples = myUParams->Length(); + if (!myVParams.IsNull()) + myNbVSamples = myVParams->Length(); +} - // 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.); - } +//======================================================================= +//function : RejectNode +//purpose : +//======================================================================= +Standard_Boolean Extrema_GenExtPS::RejectNode (const BVH_Vec3d& theCMin, + const BVH_Vec3d& theCMax, + Standard_Real& theDistance) const +{ + if (myTarget == Extrema_ExtFlag_MINMAX) + return Standard_False; - for (NoU = 1; NoU <= myusample; NoU++) { - myPoints->ChangeValue(NoU, 0).SetSqrDistance(-1.); - myPoints->ChangeValue(NoU, myvsample + 1).SetSqrDistance(-1.); - } - - myInit = Standard_True; - } + theDistance = (myTarget == Extrema_ExtFlag_MIN) ? + BVH_Tools::PointBoxSquareDistance (myPoint, theCMin, theCMax) : + BVH_Tools::PointBoxMaxSquareDistance (myPoint, theCMin, theCMax); - // 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); + return RejectMetric (theDistance); +} - aParam.SetSqrDistance(thePoint.SquareDistance(aParam.Value())); - } +//======================================================================= +//function : RejectMetric +//purpose : +//======================================================================= +Standard_Boolean Extrema_GenExtPS::RejectMetric (const Standard_Real& theDistance) const +{ + switch (myTarget) + { + case Extrema_ExtFlag_MIN: + return theDistance > mySqDistance; + case Extrema_ExtFlag_MAX: + return theDistance < mySqDistance; + default: + return Standard_False; } +} - // For search of minimum compute distances to mesh. - if(myFlag == Extrema_ExtFlag_MIN || myFlag == Extrema_ExtFlag_MINMAX) +//======================================================================= +//function : IsMetricBetter +//purpose : +//======================================================================= +Standard_Boolean Extrema_GenExtPS::IsMetricBetter (const Standard_Real& theLeft, + const Standard_Real& theRight) const +{ + switch (myTarget) { - // This is the tolerance of difference of squared values. - // No need to set it too small. - const Standard_Real aDiffTol = mytolu + mytolv; + case Extrema_ExtFlag_MIN: + return theLeft <= theRight; + case Extrema_ExtFlag_MAX: + return theLeft >= theRight; + default: + return Standard_True; + } +} + +//======================================================================= +//function : Accept +//purpose : +//======================================================================= +Standard_Boolean Extrema_GenExtPS::Accept (const Standard_Integer theIndex, + const Standard_Real&) +{ + const GridCell& aCell = myGridBoxSet->Element (theIndex); + + // Fill corner points with square distance to myPoint + Standard_Integer nU = aCell.myUInd, nV = aCell.myVInd; + Extrema_POnSurfParams& aParam00 = myPoints->ChangeValue (nU, nV); + Extrema_POnSurfParams& aParam01 = myPoints->ChangeValue (nU, nV + 1); + Extrema_POnSurfParams& aParam10 = myPoints->ChangeValue (nU + 1, nV); + Extrema_POnSurfParams& aParam11 = myPoints->ChangeValue (nU + 1, nV + 1); + + gp_Pnt aPoint (myPoint.x(), myPoint.y(), myPoint.z()); + + fillSqDist (aParam00, aPoint); + fillSqDist (aParam01, aPoint); + fillSqDist (aParam10, aPoint); + fillSqDist (aParam11, aPoint); - // 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++ ) + if (nU != myNbUSamples && nV != myNbVSamples && + (myTarget == Extrema_ExtFlag_MIN || myTarget == Extrema_ExtFlag_MINMAX)) + { + // Find minimum + + const Extrema_POnSurfParams& aParam = ComputeFaceParameters (nU, nV, aPoint); + + Standard_Boolean isMin = Standard_False; + Extrema_ElementType anElemType = aParam.GetElementType (); + + if (anElemType == Extrema_Face) { - for ( NoV = 1 ; NoV <= myvsample; NoV++) + isMin = Standard_True; + } + else + { + // 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) + { + isMin = (iU == 1 || iU == myNbUSamples); + } + else if (anElemType == Extrema_Node) { - const Extrema_POnSurfParams &aParam0 = myPoints->Value(NoU, NoV); + 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 (nU, nV - 1, aPoint); - 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 (nU - 1, nV, aPoint); - 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 == nU && iV == nV) + { + // 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 (nU, nV - 1, aPoint), // Down + &ComputeFaceParameters (nU - 1, nV - 1, aPoint), // Lower-left + &ComputeFaceParameters (nU - 1, nV, aPoint) }; // 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) + { + FindSolution (aParam); } + } - for (NoU = 1; NoU < myusample; NoU++) { - myFacePntParams->ChangeValue(NoU, 0).SetSqrDistance(RealLast()); - myFacePntParams->ChangeValue(NoU, myvsample).SetSqrDistance(RealLast()); + if (myTarget == Extrema_ExtFlag_MAX || myTarget == Extrema_ExtFlag_MINMAX) + { + // Find maximum + Extrema_POnSurfParams &aParam1 = myPoints->ChangeValue (nU - 1, nV - 1); + Extrema_POnSurfParams &aParam2 = myPoints->ChangeValue (nU - 1, nV); + Extrema_POnSurfParams &aParam3 = myPoints->ChangeValue (nU - 1, nV + 1); + Extrema_POnSurfParams &aParam4 = myPoints->ChangeValue (nU, nV - 1); + Extrema_POnSurfParams &aParam5 = myPoints->ChangeValue (nU, nV + 1); + Extrema_POnSurfParams &aParam6 = myPoints->ChangeValue (nU + 1, nV - 1); + Extrema_POnSurfParams &aParam7 = myPoints->ChangeValue (nU + 1, nV); + Extrema_POnSurfParams &aParam8 = myPoints->ChangeValue (nU + 1, nV + 1); + + fillSqDist (aParam1, aPoint); + fillSqDist (aParam2, aPoint); + fillSqDist (aParam3, aPoint); + fillSqDist (aParam4, aPoint); + fillSqDist (aParam6, aPoint); + + 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. + FindSolution (aParam00); } } + + return Standard_False; } -// Parametrization of the sample -void Extrema_GenExtPS::BuildTree() +//======================================================================= +//function : FindSolution +//purpose : +//======================================================================= +void 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; + + if (myTarget != Extrema_ExtFlag_MINMAX) + { + for (Standard_Integer i = aNbFuncSol + 1; i <= myF.NbExt(); ++i) + { + Standard_Real aDist = myF.SquareDistance(i); + if ((myTarget == Extrema_ExtFlag_MIN && aDist <= mySqDistance) || + (myTarget == Extrema_ExtFlag_MAX && aDist >= mySqDistance)) + { + if (aDist != mySqDistance) + mySolutions.clear(); + mySolutions.push_back (Extrema_GenExtPS::ExtPSResult (myF.Point(i), aDist)); + mySqDistance = aDist; + } } } - aFiller.Fill(); } -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, + Extrema_POnSurfParams &theParam0, + Extrema_POnSurfParams &theParam1, + const gp_Pnt &thePoint, + const Standard_Real theDiffTol) { - math_Vector Tol(1,2); - Tol(1) = mytolu; - Tol(2) = mytolv; + const Handle(Extrema_HArray2OfPOnSurfParams)& anEdgeParams = IsUEdge ? myUEdgePntParams : myVEdgePntParams; + Standard_Integer iU, iV; + theParam0.GetIndices (iU, iV); + if (anEdgeParams->Value (iU, iV).GetSqrDistance() < 0) + { + fillSqDist (theParam0, thePoint); + fillSqDist (theParam1, thePoint); - math_Vector UV(1, 2); - theParams.Parameter(UV(1), UV(2)); + const Standard_Real aSqrDist01 = + theParam0.Value().SquareDistance (theParam1.Value()); - math_Vector UVinf(1,2), UVsup(1,2); - UVinf(1) = myumin; - UVinf(2) = myvmin; - UVsup(1) = myusup; - UVsup(2) = myvsup; + if (aSqrDist01 <= theDiffTol) + { + // The points are confused. Get the first point and change its type. + anEdgeParams->SetValue (iU, iV, theParam0); + } + else + { + const Standard_Real aDiffDist = + Abs (theParam0.GetSqrDistance() - theParam1.GetSqrDistance()); - math_FunctionSetRoot S(myF, Tol); - S.Perform(myF, UV, UVinf, UVsup); + 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->SetValue (iU, iV, theParam1); + } + else + { + // The shortest distance is the point 0. + anEdgeParams->SetValue (iU, iV, 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]; - myDone = Standard_True; -} + theParam0.Parameter (aU[0], aV[0]); + theParam1.Parameter (aU[1], aV[1]); -void Extrema_GenExtPS::SetFlag(const Extrema_ExtFlag F) -{ - myFlag = F; -} + Standard_Real aUPar = aU[0]; + Standard_Real aVPar = aV[0]; -void Extrema_GenExtPS::SetAlgo(const Extrema_ExtAlgo A) -{ - if(myAlgo != A) - myInit = Standard_False; - myAlgo = A; - + if (IsUEdge) + { + aUPar += aRatio*(aU[1] - aU[0]); + } + else + { + aVPar += aRatio*(aV[1] - aV[0]); + } + + Extrema_POnSurfParams aParams; + aParams.SetParameters (aUPar, aVPar, myS->Value (aUPar, aVPar)); + + aParams.SetElementType (IsUEdge ? Extrema_UIsoEdge : Extrema_VIsoEdge); + aParams.SetSqrDistance (thePoint.SquareDistance (aParams.Value())); + aParams.SetIndices (iU, iV); + anEdgeParams->SetValue (iU, iV, aParams); + } + } + } + + return anEdgeParams->Value (iU, iV); } -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, + const gp_Pnt& thePoint) +{ + if (myFacePntParams->Value (theU, theV).GetSqrDistance() < 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); - } + Extrema_POnSurfParams& aParam00 = myPoints->ChangeValue (theU, theV); + Extrema_POnSurfParams& aParam01 = myPoints->ChangeValue (theU, theV + 1); + Extrema_POnSurfParams& aParam10 = myPoints->ChangeValue (theU + 1, theV); + Extrema_POnSurfParams& aParam11 = myPoints->ChangeValue (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, thePoint, aDiffTol); + const Extrema_POnSurfParams &aUE1 = + ComputeEdgeParameters (Standard_True, aParam01, aParam11, thePoint, aDiffTol); - if (isMin) { - FindSolution(P, aParam); - } - } - } + const Extrema_POnSurfParams &aVE0 = + ComputeEdgeParameters (Standard_False, aParam00, aParam01, thePoint, aDiffTol); + const Extrema_POnSurfParams &aVE1 = + ComputeEdgeParameters (Standard_False, aParam10, aParam11, thePoint, 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; + + myFacePntParams->SetValue (theU, theV, 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]); + + Extrema_POnSurfParams aParam (aUPar, aVPar, myS->Value (aUPar, aVPar)); + + aParam.SetElementType (Extrema_Face); + aParam.SetSqrDistance (thePoint.SquareDistance (aParam.Value())); + aParam.SetIndices (theU, theV); + myFacePntParams->SetValue (theU, theV, aParam); } } -} -//============================================================================= -Standard_Boolean Extrema_GenExtPS::IsDone () const { return myDone; } -//============================================================================= + return myFacePntParams->Value(theU, theV); +} +//======================================================================= +//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())) @@ -986,10 +995,13 @@ Standard_Real Extrema_GenExtPS::SquareDistance (const Standard_Integer N) const throw Standard_OutOfRange(); } - return myF.SquareDistance(N); + return mySolutions[N - 1].mySqDistance; } -//============================================================================= +//======================================================================= +//function : Point +//purpose : +//======================================================================= const Extrema_POnSurf& Extrema_GenExtPS::Point (const Standard_Integer N) const { if ((N < 1) || (N > NbExt())) @@ -997,6 +1009,5 @@ const Extrema_POnSurf& Extrema_GenExtPS::Point (const Standard_Integer N) const throw Standard_OutOfRange(); } - return myF.Point(N); + return mySolutions[N - 1].myUV; } -//============================================================================= diff --git a/src/Extrema/Extrema_GenExtPS.hxx b/src/Extrema/Extrema_GenExtPS.hxx index 3ad87ef279..84ff1ec5f0 100644 --- a/src/Extrema/Extrema_GenExtPS.hxx +++ b/src/Extrema/Extrema_GenExtPS.hxx @@ -21,18 +21,18 @@ #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 +42,320 @@ class Extrema_POnSurf; class Extrema_POnSurfParams; -//! It calculates all the extremum distances -//! between a point and a surface. +//! 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 public types + + //! Grid cell is defined just by (U, V) indices of the minimal + //! corner of the cell. + struct GridCell + { + GridCell (Standard_Integer theUInd = -1, Standard_Integer theVInd = -1) + : myUInd (theUInd), myVInd (theVInd) + {} + + Standard_Integer myUInd; //!< U index of the minimal corner + Standard_Integer myVInd; //!< V index of the minimal corner + }; + + +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); - - 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. + //! 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); + //! 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. + 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); + + +public: //! @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; + + +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. 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; - + 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; + Standard_EXPORT const Extrema_POnSurf& Point (const Standard_Integer theN) const; +private: //! @name Private 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 void FindSolution (const Extrema_POnSurfParams& theParams); + //! Compute new edge parameters. + Standard_EXPORT const Extrema_POnSurfParams& + ComputeFaceParameters (const Standard_Integer theU, + const Standard_Integer theV, + const gp_Pnt& thePoint); + //! Compute new edge parameters. + Standard_EXPORT const Extrema_POnSurfParams& + ComputeEdgeParameters (const Standard_Boolean IsUEdge, + Extrema_POnSurfParams& theParam0, + Extrema_POnSurfParams& theParam1, + const gp_Pnt& thePoint, + const Standard_Real theDiffTol); -private: + //! structure to keep the results + struct ExtPSResult + { + ExtPSResult () + : mySqDistance (-1) + {} - - 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; + ExtPSResult (const Extrema_POnSurf& theUV, + const Standard_Real theSqDist) + : myUV (theUV), + mySqDistance (theSqDist) + {} + Standard_Boolean operator< (const ExtPSResult& Other) const + { + if (mySqDistance != Other.mySqDistance) + return mySqDistance < Other.mySqDistance; -}; + Standard_Real U1, U2, V1, V2; + myUV.Parameter (U1, V1); + Other.myUV.Parameter (U2, V2); + return (U1 < U2 || (U1 == U2 && V1 < V2)); + } + + Extrema_POnSurf myUV; + Standard_Real mySqDistance; + }; + +private: //! @name Fields + // Inputs + NCollection_Vec3 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 + 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 > myGridBoxSet; //!< BVH-organized grid + + // Results + std::vector mySolutions; + Standard_Boolean myIsDone; //!< IsDone 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 34ec6a72e0..db754bfbd0 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/GeomAPI/GeomAPI_ProjectPointOnSurf.cxx b/src/GeomAPI/GeomAPI_ProjectPointOnSurf.cxx index da43cb70e6..9c0274476e 100644 --- a/src/GeomAPI/GeomAPI_ProjectPointOnSurf.cxx +++ b/src/GeomAPI/GeomAPI_ProjectPointOnSurf.cxx @@ -37,10 +37,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 @@ -48,10 +47,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 @@ -62,11 +60,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 @@ -78,11 +75,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 @@ -111,11 +107,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 @@ -123,27 +118,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 (); } @@ -157,20 +140,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 (); } @@ -184,19 +159,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 (); } //======================================================================= @@ -207,20 +174,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; } //======================================================================= @@ -232,19 +190,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 012187580b..21d656407d 100644 --- a/src/GeometryTest/GeometryTest_APICommands.cxx +++ b/src/GeometryTest/GeometryTest_APICommands.cxx @@ -88,9 +88,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) { - std::cout << " Use proj curve/surf x y z [{extrema algo: g(grad)/t(tree)}|{u v}]" << std::endl; + di.PrintHelp (a[0]); return 1; } @@ -98,10 +98,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()) { @@ -110,12 +106,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."; @@ -752,7 +748,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/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