张量积de Casteljau算法的效率分析

ON COMPUTATIONAL EFFICIENCY OF TENSOR PRODUCT DE CASTELJAU ALGORITHM

在几何造型中 ,张量积 Bernstein多项式具有非常重要的地位 .在几何系统中主要应用 de Casteljau算法逐个方向地计算张量积 Bernstein多项式上的点 ,例如首先计算 u-方向 ,然后是 v-方向、w -方向等 .分析了张量积形式的 de Casteljau算法的效率 ,证明了对于不同的参数方向的计算顺序会导致不同的计算效率 ,并且当按照参数方向的次数递增的顺序应用 de Casteljau算法时 ,计算量是最小的 .除了理论分析之外 ,我们还给出了实验结果 。

Tensor product Bernstein polynomials are basic elements in geometric modeling. To evaluate a point defined by tensor product Bernstein polynomials, de Casteljau algorithm is commonly implemented one direction by one direction, e. g. , first u direction, then v direction, w direction, etc. . In this paper, it is shown that different processing order of parametric directions may result in different computational cost, and for the tensor product de Casteljau algorithm, it is more efficient if we process the directions in the order of increasing degrees of their parametric variables. Experimental results for the tensor product Bernstein polynomials with two and three variables are provided, which are consistent with the theoretical analysis.