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包中提供了常見的數值計算的功能，如矩陣的加減乘除，轉置及方陣的特征值和特征向量的計算，求解線性方程組；一元函數或多元函數的微分、積分及極值的計算；線性和非線性（Non-Linear Equations）方程組(Function Set)的計算等等。大部分功能和另一個開源科學計算庫gsl類似，只是采用面向對象的方式，更便于使用。方程組（Function Set）的相關計算與多元函數（MultiVarFunction）一樣地在OPEN CASCADE庫廣泛地應用，如一些極值計算算法，擬合算法、點在曲線曲面上投影的相關問題等等，都會涉及到方程組求解的計算。如下類圖所示。
下面的類圖為方程組類Math_FunctionSet的類圖，由類圖可知，從其派生的類數量很多，由此可見其在OPEN CASCADE中的重要性。本文主要對其用法進行說明，理解其用法后，便于對其他相關算法的理解。
在理解math包中大部分算法后，也是掌握了一個數學計算工具，以后遇到相關的問題，可以盡量地用數學的方式進行解決，提高數學的應用水平。
Figure 1.1 math_FunctionSet class diagram in OPENCASCADE
2. Function Set
很多科學理論和工程技術問題都最終轉化成非線性方程或方程組的求解，如對理論數據或實驗觀察的數據進行擬合用到的最小二乘法，就是一個典型的非線性方程組求解的問題。而在幾何中的應用就更廣泛了，像計算直線與平面的交點問題，點到自由曲線曲面的投影問題等等。鑒于方程組的廣泛應用，OPEN CASCADE的數學包中提供了一個抽象類math_FunctionSet來與之對應，方便方程組在程序中的計算。
對于普通的方程組，主要設置了三個抽象函數：
v NbVariables()：方程組中變量的個數；
v NbEquations()：方程組中方程的個數；
v Value()：計算指定變量的方程組的值；
帶微分的方程組類比普通方程組多兩個抽象函數：
v Derivatives()：計算指定變量的方程組的微分值；
v Values()：計算指定變量的方程組的值和微分值；
因為都是抽象類，所以不能直接使用。下面結合《計算方法》書中的題目，來說明方程組在OPENCASCADE中的計算方法。下面的題目來自《計算方法》第二版P213頁例17：設有非線性方程組：
從幾何上看其解就是圓和曲線的交點。下面給出OPENCASCADE中的計算代碼：
/*
* 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;
}
計算結果如下圖所示：
Figure 2.1 Evaluate result
3. Application
在曲線和曲面的極值計算、曲面和曲面的極值計算及點和曲面的極值計算中都用到了求解方程組的算法，如下類圖所示：
Figure 3.1 Extrema algorithms implemented by Function Set
其中點和曲面極值的計算也適用于曲面上點的參數的反求。與曲線上點的參數反求類似，曲線上點的參數反求是計算非線性方程的根；曲面上點的參數反求則擴展到了非線性方程組。問題求解的關鍵還是建立數學模型，如點到曲線上的投影由下圖可知：
Figure 3.2 Point project on curve
構造的函數為：
上式表示曲線上過參數u的切線與曲線上參數u的點到指定點的向量的數量積，當f(u)=0時數量積為0，即為點垂直于曲線上過參數u的切線，對此非線性方程求解，即得到了點到曲線的投影。同理，點到曲面的投影也可以建立類似的方程組：
其中曲面對參數u,v的偏導數表示在曲面在u,v方向上的切線，兩個函數意義和一個方程的意義類似，即點到曲面上某一點的向量與切線的數量積。當向量與兩個切線方向的數量積為0的時候，即此向量與這兩個切線都垂直，就是點到曲面的投影。這也是OPEN CASCADE中計算點與曲面極值的實現原是，其類為Extrema_FuncExtPS，為了使用類math_FunctionSetRoot對方程組進行求解，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;
};
根據其注釋可知，建立的方程組和上述方程組相同，并且還計算了方程組的一階偏導數如下：
通過類math_FunctionSetRoot對上述方程組進行求解，即可得到點到曲面的極值。
4. Conclusion
線性和非線性方程組的求解在幾何中也有大量的應用。線性方程組可以利用矩陣的概念進行求解，如Gauss消元法。而非線性方程組的求解也是有相關的算法，如Newton法等，具體理論可參考《計算方法》等相關書籍。掌握這些數學工具之后，關鍵是將幾何問題抽象成數學問題，然后利用這些數學工具來解決實際問題。從而可以將《高等數學》、《線性代數》等理論知識，通過《計算方法》在計算機中的實現，來用理論指導實踐，通過實踐加深理論的理解。也讓枯燥的理論更生動、有趣。
與OPEN CASCADE數學包中其他概念如一元函數，多元函數等概念一樣，非線性方程組及其求解也是一個重要概念。理解這些類的原理之后，便于對其他幾何造型算法的實現原理進行理解。
5. References
1. 趙罡, 穆國旺, 王拉柱譯. 非均勻有理B樣條. 清華大學出版社. 1995
2. 易大義, 陳道琦. 數值分析引論. 浙江大學出版社. 1998
3. 易大義,沈云寶,李有法. 計算方法. 浙江大學出版社. 2002
4. 蔣爾雄,趙風光,蘇仰鋒. 數值逼近. 復旦大學出版社. 2012
5. 王仁宏,李崇君,朱春鋼. 計算幾何教程. 科學出版社. 2008
6. 同濟大學數學教研室. 高等數學. 高等教育出版社. 1996
7. 同濟大學應用數學系. 線性代數. 高等教育出版社. 2003