三次Bézier曲线的快速求值算法

Fast Evaluation Algorithm for Cubic Bézier Curves

摘要: 三次Bézier曲线的求值算法对于曲线的处理有重要的意义，为了提高三次Bézier曲线的计算效率，本文从矩阵分解的角度解读了De Casteljau算法，并在此基础上提出了一种新的快速求值算法。该算法利用线性插值计算曲线上的点，除第一次线性插值利用两个初始控制顶点外，其余每次线性插值仅利用一个初始控制顶点与上一次线性插值产生的一个新控制顶点，将中间控制顶点数量从传统算法的6个减少至3个，其仅使用控制顶点的凸组合，计算复杂度与控制顶点数量呈线性关系，从而提高了求值算法的计算效率。新算法只涉及线性插值，具有数值稳定性且易于实现，可以更快地求出曲线在特定参数值下的点，为三次Bézier曲线的实时绘制提供了新的解决方案。

Abstract: The evaluation algorithm of cubic Bézier curves is of great significance for the processing of curves. In order to improve the computational efficiency of cubic Bézier curves, this paper interprets the De Casteljau algorithm from the perspective of matrix factorization, and proposes a new fast evaluation algorithm based on this. The algorithm uses linear interpolation to calculate the points on the curve. Except that the first linear interpolation uses two initial control vertices, the remaining linear interpolation only uses one initial control vertex and a new control vertex generated by the previous linear interpolation, which reduces the number of intermediate control vertices from 6 to 3. It only uses the convex combination of control points, and the computational complexity is linear with the number of control points, which improves the computational efficiency of the evaluation algorithm. The new algorithm only involves linear interpolation, which is numerically stable and easy to implement. It can quickly find the points of the curve under specific parameter values, and provides a new solution for real-time rendering of cubic Bézier curves.