在学习 Bézier 曲线时，De Casteljau 算法是一个非常重要的算法。它的核心思想并不复杂：通过不断对相邻控制点做线性插值，最终得到曲线上的点。
它不仅可以用来计算 Bézier 曲线在某个参数 t 处的位置，还可以顺便把一条 Bézier 曲线分割成两条新的 Bézier 曲线。在计算机图形学中，它还可以用于曲线绘制和自适应细分。
本文分成三部分：
t 位置上的点假设我们有一条三次 Bézier 曲线，它有 4 个控制点：
P0, P1, P2, P3
我们想要求曲线在某个参数 t 处的点。
这里的 t 通常在 [0, 1] 之间：
t = 0 表示曲线起点
t = 1 表示曲线终点
t = 0.5 表示曲线中间某个位置
De Casteljau 算法的做法是：不断在相邻控制点之间做线性插值。
线性插值公式是：
lerp(A, B, t) = (1 - t)A + tB
lerp 是 linear interpolation 的缩写，即线性插值。意思是：在点 A 和点 B 之间，按照比例 t 取一个新点。
当：
t = 0 -> 得到 A
t = 1 -> 得到 B
t = 0.5 -> 得到 A 和 B 的中点
对于三次 Bézier：
P0, P1, P2, P3
第一层插值：
Q0 = lerp(P0, P1, t)
Q1 = lerp(P1, P2, t)
Q2 = lerp(P2, P3, t)
第二层插值：
R0 = lerp(Q0, Q1, t)
R1 = lerp(Q1, Q2, t)
第三层插值：
S0 = lerp(R0, R1, t)
最后得到的 S0，就是 Bézier 曲线在参数 t 处的点。
也就是说：
Bezier(t) = S0
整个过程可以想象成这样：
P0 -------- P1 -------- P2 -------- P3
| | |
Q0 -------- Q1 -------- Q2
| |
R0 -------- R1
|
S0
其中 S0 就是曲线上的点。
Point lerp(Point a, Point b, double t) {
return a * (1.0 - t) + b * t;
}
Point deCasteljau(std::vector<Point> points, double t) {
while (points.size() > 1) {
std::vector<Point> next;
for (int i = 0; i < points.size() - 1; ++i) {
next.push_back(lerp(points[i], points[i + 1], t));
}
points = next;
}
return points[0];
}
这个函数可以处理任意阶数的 Bézier 曲线。
如果有 2 个控制点，它就是一次 Bézier，也就是线段。
如果有 3 个控制点，它就是二次 Bézier。
如果有 4 个控制点，它就是三次 Bézier。
控制点数量和曲线次数的关系是：
曲线次数 n = 控制点数量 - 1
例如：
2 个控制点 -> 1 次 Bézier
3 个控制点 -> 2 次 Bézier
4 个控制点 -> 3 次 Bézier
De Casteljau 算法除了能求出曲线在 t 处的点，还能顺便把原曲线分成左右两段。
假设一条三次 Bézier 曲线的控制点是：
P0, P1, P2, P3
我们在参数 t 处把它切开。
De Casteljau 算法会生成这些中间点：
第一层：
Q0 = lerp(P0, P1, t)
Q1 = lerp(P1, P2, t)
Q2 = lerp(P2, P3, t)
第二层：
R0 = lerp(Q0, Q1, t)
R1 = lerp(Q1, Q2, t)
第三层：
S0 = lerp(R0, R1, t)
其中 S0 是曲线在 t 位置上的点，也就是分割点。
左半段曲线由每一层最左边的点组成：
P0, Q0, R0, S0
这 4 个点重新定义了一条三次 Bézier 曲线。
这条新曲线表示原曲线从 0 到 t 的部分。
可以理解为：
LeftCurve = Bezier(P0, Q0, R0, S0)
右半段曲线由每一层最右边的点组成，但顺序需要反过来：
S0, R1, Q2, P3
这 4 个点也重新定义了一条三次 Bézier 曲线。
它表示原曲线从 t 到 1 的部分。
可以理解为：
RightCurve = Bezier(S0, R1, Q2, P3)
这是 De Casteljau 算法非常重要的性质。
一条 Bézier 曲线在某个参数 t 处分割后，得到的左右两段仍然都是 Bézier 曲线，并且它们合起来和原曲线完全一样。
不是近似一样，而是数学上完全一致。
也就是说：
原曲线 [0, 1]
=
左曲线 [0, 1] + 右曲线 [0, 1]
其中：
左曲线 [0, 1] 对应原曲线 [0, t]
右曲线 [0, 1] 对应原曲线 [t, 1]
曲线分割在几何建模和计算机图形学中非常重要。
常见用途包括：
1. 裁剪曲线
2. 局部编辑曲线
3. 曲线绘制
4. 曲线求交
5. 曲线细分
6. 碰撞检测
7. 生成显示用折线
例如，如果我们只想保留一条 Bézier 曲线的前 40%，就可以在 t = 0.4 的位置分割，然后取左半段曲线。
如果我们只想保留中间一段，比如 [0.2, 0.7]，也可以通过多次分割得到。
struct BezierSplitResult {
std::vector<Point> left;
std::vector<Point> right;
};
BezierSplitResult splitBezier(std::vector<Point> points, double t) {
std::vector<Point> left;
std::vector<Point> right;
while (!points.empty()) {
left.push_back(points.front());
right.insert(right.begin(), points.back());
std::vector<Point> next;
for (int i = 0; i < points.size() - 1; ++i) {
next.push_back(lerp(points[i], points[i + 1], t));
}
points = next;
}
return { left, right };
}
对于三次 Bézier，这个函数返回：
left = P0, Q0, R0, S0
right = S0, R1, Q2, P3
这样我们就得到了两条新的 Bézier 曲线。
Bézier 曲线本质上是连续的数学曲线。
例如：
B(t), t ∈ [0, 1]
但是计算机屏幕最终显示的是像素，图形 API 通常也更擅长绘制点、线段和三角形。
因此，在绘制 Bézier 曲线时，通常需要把连续曲线离散化成很多小线段。
最容易理解的绘制方法是：
t = 0 到 t = 1 取很多个参数值代码大概是：
void drawBezierBySampling(int segments) {
Point prev = getBezierPoint(0.0);
for (int i = 1; i <= segments; ++i) {
double t = double(i) / segments;
Point curr = getBezierPoint(t);
drawLine(prev, curr);
prev = curr;
}
}
例如：
segments = 10 -> 用 10 条线段近似曲线
segments = 100 -> 用 100 条线段近似曲线
segments = 300 -> 用 300 条线段近似曲线
线段越多，曲线看起来越平滑。
但本质上，屏幕上显示的仍然是一条折线，只是线段足够短时，人眼会觉得它是平滑曲线。
如果写成：
double step = 0.0001;
double t = 0.0;
while (t <= 1.0) {
Point p = getBezierPoint(t);
drawPoint(p);
t += step;
}
这也能看到很多点组成的曲线。
但是实际绘制时更常用的是画线段：
drawLine(prev, curr);
而不是只画点。
因为只画点会得到一串离散点；连线后才更像连续曲线。
均匀采样虽然简单，但有两个问题。
第一个问题是：t 均匀不代表曲线长度均匀。
也就是说：
t = 0.0, 0.1, 0.2, ..., 1.0
这些点在参数上是均匀的，但在曲线上的距离不一定均匀。
有的地方点很密，有的地方点很稀。
第二个问题是：曲线不同位置的弯曲程度不同。
有些地方几乎是直线，只需要很少线段就能近似。
有些地方弯得很厉害，需要更多线段才能画得平滑。
如果固定使用 100 段，可能会出现：
直的地方浪费线段
弯的地方仍然不够平滑
更好的绘制方式是自适应细分。
基本思想是：
如果一段 Bézier 曲线足够接近直线，就直接画起点到终点的线段。
如果还不够接近直线，就把它分割成左右两段，再分别处理。
伪代码如下：
void drawBezierAdaptive(BezierCurve curve, double tolerance) {
if (isFlatEnough(curve, tolerance)) {
drawLine(curve.startPoint(), curve.endPoint());
return;
}
auto [left, right] = splitBezier(curve.controlPoints(), 0.5);
drawBezierAdaptive(left, tolerance);
drawBezierAdaptive(right, tolerance);
}
这里的 splitBezier(curve, 0.5) 就可以用 De Casteljau 算法实现。
对于三次 Bézier：
P0, P1, P2, P3
可以用一个简单标准判断：
P1 到直线 P0-P3 的距离是否足够小
P2 到直线 P0-P3 的距离是否足够小
如果中间控制点离起点终点连成的直线很近，那么这段 Bézier 曲线就很接近直线，可以直接画：
drawLine(P0, P3);
否则继续分割。
这种方法的优点是：
弯曲大的地方自动多分割
比较直的地方自动少分割
绘制效率更高
曲线显示更稳定
在 CAD 或几何建模系统中，曲线通常不是以点的形式保存的。
例如在 OCCT 中，一条曲线可能是：
Geom_BezierCurve
Geom_BSplineCurve
Geom_Circle
Geom_Line
这些都是数学对象。
几何内核里保存的是精确曲线，而不是一堆离散点。
但是当曲线要显示到屏幕上时，还是需要把它离散化成图形系统可以绘制的元素，例如折线。
所以可以这样理解：
几何内核中：曲线是精确的参数方程
显示系统中：曲线被离散成很多小线段
这也是为什么 CAD 软件可以在放大视图时重新生成更精细的显示结果。
它不是只保存了一堆固定点，而是保存了曲线本身的数学定义。
De Casteljau 算法的核心是线性插值。
它可以完成三件重要的事情：
第一，求 Bézier 曲线在参数 t 处的点：
不断对相邻控制点做 lerp，直到只剩一个点。
第二，把 Bézier 曲线分割成左右两段：
左边界点组成左曲线控制点。
右边界点组成右曲线控制点。
第三，用于曲线绘制：
通过递归分割，把曲线细分成足够接近直线的小段，
然后用线段绘制。
从学习 Bézier 曲线的角度看，De Casteljau 算法比直接背公式更重要。
因为它让我们从几何上理解 Bézier 曲线：
Bézier 曲线不是神秘公式，
而是反复线性插值得到的轨迹。
这个理解对后续学习 B-Spline、NURBS、曲线裁剪、曲线求交以及几何建模都非常有帮助。
（完）