Function Set in OPEN CASCADE
eryar@163.com
Abstract. The common math algorithms library provides a C++ implementation of the most frequently used mathematical algorithms. These include: algorithms to solve a set of linear algebraic equations, algorithms to find the minimum of a function of one or more independent variables, algorithms to find roots of one, or of a set of non-linear equations, algorithm to find the eigenvalues and eigenvectors of a square matrix. The solver for function set is used widely in extrema value evaluation, point project on to curve and surface, also used to solve the point inverse for geometry curve and surface. The paper focus on the function set concept and its solver in OPEN CASCADE.
Key Words. Function Set, Non-Linear Equation Solver, Equations Root,
1. Introduction
OPEN CASCADE的math包中提供了常見的數(shù)值計(jì)算的功能，如矩陣的加減乘除，轉(zhuǎn)置及方陣的特征值和特征向量的計(jì)算，求解線性方程組；一元函數(shù)或多元函數(shù)的微分、積分及極值的計(jì)算；線性和非線性（Non-Linear Equations）方程組(Function Set)的計(jì)算等等。大部分功能和另一個(gè)開源科學(xué)計(jì)算庫(kù)gsl類似，只是采用面向?qū)ο蟮姆绞剑阌谑褂谩７匠探M（Function Set）的相關(guān)計(jì)算與多元函數(shù)（MultiVarFunction）一樣地在OPEN CASCADE庫(kù)廣泛地應(yīng)用，如一些極值計(jì)算算法，擬合算法、點(diǎn)在曲線曲面上投影的相關(guān)問題等等，都會(huì)涉及到方程組求解的計(jì)算。如下類圖所示。
下面的類圖為方程組類Math_FunctionSet的類圖，由類圖可知，從其派生的類數(shù)量很多，由此可見其在OPEN CASCADE中的重要性。本文主要對(duì)其用法進(jìn)行說明，理解其用法后，便于對(duì)其他相關(guān)算法的理解。
在理解math包中大部分算法后，也是掌握了一個(gè)數(shù)學(xué)計(jì)算工具，以后遇到相關(guān)的問題，可以盡量地用數(shù)學(xué)的方式進(jìn)行解決，提高數(shù)學(xué)的應(yīng)用水平。
Figure 1.1 math_FunctionSet class diagram in OPENCASCADE
2. Function Set
很多科學(xué)理論和工程技術(shù)問題都最終轉(zhuǎn)化成非線性方程或方程組的求解，如對(duì)理論數(shù)據(jù)或?qū)嶒?yàn)觀察的數(shù)據(jù)進(jìn)行擬合用到的最小二乘法，就是一個(gè)典型的非線性方程組求解的問題。而在幾何中的應(yīng)用就更廣泛了，像計(jì)算直線與平面的交點(diǎn)問題，點(diǎn)到自由曲線曲面的投影問題等等。鑒于方程組的廣泛應(yīng)用，OPEN CASCADE的數(shù)學(xué)包中提供了一個(gè)抽象類math_FunctionSet來與之對(duì)應(yīng)，方便方程組在程序中的計(jì)算。
對(duì)于普通的方程組，主要設(shè)置了三個(gè)抽象函數(shù)：
v NbVariables()：方程組中變量的個(gè)數(shù)；
v NbEquations()：方程組中方程的個(gè)數(shù)；
v Value()：計(jì)算指定變量的方程組的值；
帶微分的方程組類比普通方程組多兩個(gè)抽象函數(shù)：
v Derivatives()：計(jì)算指定變量的方程組的微分值；
v Values()：計(jì)算指定變量的方程組的值和微分值；
因?yàn)槎际浅橄箢悾圆荒苤苯邮褂谩Ｏ旅娼Y(jié)合《計(jì)算方法》書中的題目，來說明方程組在OPENCASCADE中的計(jì)算方法。下面的題目來自《計(jì)算方法》第二版P213頁(yè)例17：設(shè)有非線性方程組：
從幾何上看其解就是圓和曲線的交點(diǎn)。下面給出OPENCASCADE中的計(jì)算代碼：
/*
* Copyright (c) 2016 Shing Liu All Rights Reserved.
*
* File : main.cpp
* Author : Shing Liu(eryar@163.com)
* Date : 2016-01-12 21:00
* Version : OpenCASCADE6.9.0
*
* Description : test function set.
*/
#define WNT
#include <math_FunctionSetRoot.hxx>
#include <math_FunctionSetWithDerivatives.hxx>
#pragma comment(lib, "TKernel.lib")
#pragma comment(lib, "TKMath.lib")
/**
* @brief test function for a circle and a curve:
*
* F1(x1,x2) = (x1)^2 + (x2)^2 -4
* F2(x1,x2) = e^(x1) + x2 - 1
*
* The derivatives of the function set are:
* Dx1f1(x1,x2) = 2.0 * x1
* Dx2f1(x1,x2) = 2.0 * x2
* Dx1f2(x1,x2) = e^(x1)
* Dx2f2(x1,x2) = 1.0
*/
class test_FunctionSet: public math_FunctionSetWithDerivatives
{
public:
virtual Standard_Integer NbVariables() const
{
return 2;
}
virtual Standard_Integer NbEquations() const
{
return 2;
}
virtual Standard_Boolean Value(const math_Vector& X, math_Vector& F)
{
F(1) = X(1) * X(1) + X(2) * X(2) - 4.0;
F(2) = exp(X(1)) + X(2) - 1.0;
return Standard_True;
}
virtual Standard_Boolean Derivatives(const math_Vector& X, math_Matrix& D)
{
D(1,1) = 2.0 * X(1);
D(1,2) = 2.0 * X(2);
D(2,1) = exp(X(1));
D(2,2) = 1.0;
return Standard_True;
}
virtual Standard_Boolean Values(const math_Vector& X, math_Vector& F, math_Matrix& D)
{
Value(X, F);
Derivatives(X, D);
return Standard_True;
}
};
void testFunctionSet(void)
{
test_FunctionSet aTestFunctionSet;
math_FunctionSetRoot aSolver(aTestFunctionSet);
math_Vector aStartPoint(1, 2, 0.0);
// initial guess point(-2.0, 0.0)
aStartPoint(1) = -2.0;
aStartPoint(2) = 0.0;
aSolver.Perform(aTestFunctionSet, aStartPoint);
std::cout << aSolver << std::endl;
// initial guess point(0.0, -2.0)
aStartPoint(1) = 0.0;
aStartPoint(2) = -2.0;
aSolver.Perform(aTestFunctionSet, aStartPoint);
std::cout << aSolver << std::endl;
}
int main(int argc, char* argv[])
{
testFunctionSet();
return 0;
}
計(jì)算結(jié)果如下圖所示：
Figure 2.1 Evaluate result
3. Application
在曲線和曲面的極值計(jì)算、曲面和曲面的極值計(jì)算及點(diǎn)和曲面的極值計(jì)算中都用到了求解方程組的算法，如下類圖所示：
Figure 3.1 Extrema algorithms implemented by Function Set
其中點(diǎn)和曲面極值的計(jì)算也適用于曲面上點(diǎn)的參數(shù)的反求。與曲線上點(diǎn)的參數(shù)反求類似，曲線上點(diǎn)的參數(shù)反求是計(jì)算非線性方程的根；曲面上點(diǎn)的參數(shù)反求則擴(kuò)展到了非線性方程組。問題求解的關(guān)鍵還是建立數(shù)學(xué)模型，如點(diǎn)到曲線上的投影由下圖可知：
Figure 3.2 Point project on curve
構(gòu)造的函數(shù)為：
上式表示曲線上過參數(shù)u的切線與曲線上參數(shù)u的點(diǎn)到指定點(diǎn)的向量的數(shù)量積，當(dāng)f(u)=0時(shí)數(shù)量積為0，即為點(diǎn)垂直于曲線上過參數(shù)u的切線，對(duì)此非線性方程求解，即得到了點(diǎn)到曲線的投影。同理，點(diǎn)到曲面的投影也可以建立類似的方程組：
其中曲面對(duì)參數(shù)u,v的偏導(dǎo)數(shù)表示在曲面在u,v方向上的切線，兩個(gè)函數(shù)意義和一個(gè)方程的意義類似，即點(diǎn)到曲面上某一點(diǎn)的向量與切線的數(shù)量積。當(dāng)向量與兩個(gè)切線方向的數(shù)量積為0的時(shí)候，即此向量與這兩個(gè)切線都垂直，就是點(diǎn)到曲面的投影。這也是OPEN CASCADE中計(jì)算點(diǎn)與曲面極值的實(shí)現(xiàn)原是，其類為Extrema_FuncExtPS，為了使用類math_FunctionSetRoot對(duì)方程組進(jìn)行求解，Extrema_FuncExtPS也是由類math_FunctionSetWithDerivatives派生，類定義代碼如下：
//! Functional for search of extremum of the distance between point P and
//! surface S, starting from approximate solution (u0, v0).
//!
//! The class inherits math_FunctionSetWithDerivatives and thus is intended
//! for use in math_FunctionSetRoot algorithm .
//!
//! Denoting derivatives of the surface S(u,v) by u and v, respectively, as
//! Su and Sv, the two functions to be nullified are:
//!
//! F1(u,v) = (S - P) * Su
//! F2(u,v) = (S - P) * Sv
//!
//! The derivatives of the functional are:
//!
//! Duf1(u,v) = Su^2 + (S-P) * Suu;
//! Dvf1(u,v) = Su * Sv + (S-P) * Suv
//! Duf2(u,v) = Sv * Su + (S-P) * Suv = Dvf1
//! Dvf2(u,v) = Sv^2 + (S-P) * Svv
//!
//! Here * denotes scalar product, and ^2 is square power.
class Extrema_FuncExtPS : public math_FunctionSetWithDerivatives
{
public:
DEFINE_STANDARD_ALLOC
Standard_EXPORT Extrema_FuncExtPS();
Standard_EXPORT Extrema_FuncExtPS(const gp_Pnt& P, const Adaptor3d_Surface& S);
//! sets the field mysurf of the function.
Standard_EXPORT void Initialize (const Adaptor3d_Surface& S);
//! sets the field mysurf of the function.
Standard_EXPORT void SetPoint (const gp_Pnt& P);
Standard_EXPORT Standard_Integer NbVariables() const Standard_OVERRIDE;
Standard_EXPORT Standard_Integer NbEquations() const Standard_OVERRIDE;
//! Calculate Fi(U,V).
Standard_EXPORT Standard_Boolean Value (const math_Vector& UV, math_Vector& F) Standard_OVERRIDE;
//! Calculate Fi'(U,V).
Standard_EXPORT Standard_Boolean Derivatives (const math_Vector& UV, math_Matrix& DF) Standard_OVERRIDE;
//! Calculate Fi(U,V) and Fi'(U,V).
Standard_EXPORT Standard_Boolean Values (const math_Vector& UV, math_Vector& F, math_Matrix& DF) Standard_OVERRIDE;
//! Save the found extremum.
Standard_EXPORT virtual Standard_Integer GetStateNumber() Standard_OVERRIDE;
//! Return the number of found extrema.
Standard_EXPORT Standard_Integer NbExt() const;
//! Return the value of the Nth distance.
Standard_EXPORT Standard_Real SquareDistance (const Standard_Integer N) const;
//! Returns the Nth extremum.
Standard_EXPORT const Extrema_POnSurf& Point (const Standard_Integer N) const;
protected:
private:
gp_Pnt myP;
Adaptor3d_SurfacePtr myS;
Standard_Real myU;
Standard_Real myV;
gp_Pnt myPs;
TColStd_SequenceOfReal mySqDist;
Extrema_SequenceOfPOnSurf myPoint;
Standard_Boolean myPinit;
Standard_Boolean mySinit;
};
根據(jù)其注釋可知，建立的方程組和上述方程組相同，并且還計(jì)算了方程組的一階偏導(dǎo)數(shù)如下：
通過類math_FunctionSetRoot對(duì)上述方程組進(jìn)行求解，即可得到點(diǎn)到曲面的極值。
4. Conclusion
線性和非線性方程組的求解在幾何中也有大量的應(yīng)用。線性方程組可以利用矩陣的概念進(jìn)行求解，如Gauss消元法。而非線性方程組的求解也是有相關(guān)的算法，如Newton法等，具體理論可參考《計(jì)算方法》等相關(guān)書籍。掌握這些數(shù)學(xué)工具之后，關(guān)鍵是將幾何問題抽象成數(shù)學(xué)問題，然后利用這些數(shù)學(xué)工具來解決實(shí)際問題。從而可以將《高等數(shù)學(xué)》、《線性代數(shù)》等理論知識(shí)，通過《計(jì)算方法》在計(jì)算機(jī)中的實(shí)現(xiàn)，來用理論指導(dǎo)實(shí)踐，通過實(shí)踐加深理論的理解。也讓枯燥的理論更生動(dòng)、有趣。
與OPEN CASCADE數(shù)學(xué)包中其他概念如一元函數(shù)，多元函數(shù)等概念一樣，非線性方程組及其求解也是一個(gè)重要概念。理解這些類的原理之后，便于對(duì)其他幾何造型算法的實(shí)現(xiàn)原理進(jìn)行理解。
5. References
1. 趙罡, 穆國(guó)旺, 王拉柱譯. 非均勻有理B樣條. 清華大學(xué)出版社. 1995
2. 易大義, 陳道琦. 數(shù)值分析引論. 浙江大學(xué)出版社. 1998
3. 易大義,沈云寶,李有法. 計(jì)算方法. 浙江大學(xué)出版社. 2002
4. 蔣爾雄,趙風(fēng)光,蘇仰鋒. 數(shù)值逼近. 復(fù)旦大學(xué)出版社. 2012
5. 王仁宏,李崇君,朱春鋼. 計(jì)算幾何教程. 科學(xué)出版社. 2008
6. 同濟(jì)大學(xué)數(shù)學(xué)教研室. 高等數(shù)學(xué). 高等教育出版社. 1996
7. 同濟(jì)大學(xué)應(yīng)用數(shù)學(xué)系. 線性代數(shù). 高等教育出版社. 2003