论文标题
用于计算b-Spline基函数的Bernstein-Bézier系数的线性时间算法
Linear-time algorithm for computing the Bernstein-Bézier coefficients of B-spline basis functions
论文作者
论文摘要
证明了同一程度的B型单频函数的新差异性关系。从这种关系中，得出了计算Bernstein-Bézier形式中B-Spline函数的系数的递归方法。在重合边界结的情况下，其复杂性与系数数量成正比。这意味着渐近算法是最佳的。在其他情况下，复杂性最多增加$ O（m^3）$。当已知B-Spline基函数的Bernstein-Bézier系数时，可以通过执行作者最近提出的几何算法来计算线性时间中的任何B-Spline函数。当在多个点评估b-spline曲线时，该算法会很好地缩放，例如，为了渲染它，因为只需要一次找到每个结跨度的系数即可。在评估多个点的许多B型曲线曲线时（就像呈张量产品B-Spline表面一样）时，这种方法的计算复杂性低于使用DE Boor-Cox算法。数值测试表明新方法是有效的。在功率基础上找到B-Spline函数的系数的问题可以类似地解决。
A new differential-recurrence relation for the B-spline functions of the same degree is proved. From this relation, a recursive method of computing the coefficients of B-spline functions of degree $m$ in the Bernstein-Bézier form is derived. Its complexity is proportional to the number of coefficients in the case of coincident boundary knots. This means that, asymptotically, the algorithm is optimal. In other cases, the complexity is increased by at most $O(m^3)$. When the Bernstein-Bézier coefficients of B-spline basis functions are known, it is possible to compute any B-spline function in linear time with respect to its degree by performing the geometric algorithm proposed recently by the authors. This algorithm scales well when evaluating the B-spline curve at multiple points, e.g., in order to render it, since one only needs to find the coefficients for each knot span once. When evaluating many B-spline curves at multiple points (as is the case when rendering tensor product B-spline surfaces), such approach has lower computational complexity than using the de Boor-Cox algorithm. The numerical tests show that the new method is efficient. The problem of finding the coefficients of the B-spline functions in the power basis can be solved similarly.
