January 31, 2017

贝塞尔曲线

致敬法国工程师 皮埃尔·贝塞尔(Pierre Bézier) (wiki上还没有他的页面,先用贝塞尔曲线的页面链接)
可以画出非常好看的曲线。(试试更改下面输入框中点的坐标 1600x450的画布哦 左上角为原点)

贝塞尔曲线可以有非常多的阶,但实际上理解起来不复杂,高阶的曲线都是由简单的线性差值形成的。

先从一阶的说起

来个数学公式 ( 不知哪个家说的文章出一个公式就少一半读者,一定要看下去啊)

$$ \mathbf{B}(t) = \mathbf{P_{2}} = \mathbf{P_{0}} + (\mathbf{P_{1}} - \mathbf{P_{0}})t, t \in [0,1] $$

仔细看!这个其实是线性差值的公式
自然他画出来就是一条线段,从$P_{0}$到$P_{1}$

一阶贝塞尔曲线

二阶

二阶中会多出来一个点,下图中$P_{1}$

二阶贝塞尔曲线

这条曲线怎么形成的呢,可以分解为下面的步骤:

  1. 先在$P_{0},P_{1}$之间用一阶差值得到一个新的点$P_{3}$
  2. 再在$P_{1},P_{2}$之间用一阶差值得到一个新的点$P_{4}$
  3. 然后在使用一阶的差值公式,在$P_{3},P_{4}$之间一阶差值得到曲线上的点$P_{5}$

所以二阶其实是三个一阶差值复合而成的,于是他的公式是
(公式太胖,可以横向滚动)

$$ \begin{align} \mathbf{B(t)} & = \mathbf{P_{5}} \\\\ & = \mathbf{P_{3}} + (\mathbf{P_{4}} - \mathbf{P_{3}})t \\\\ & = \mathbf{P_{4}}t + (1 - t)\mathbf{P_{3}} \\\\ & = (\mathbf{P_{1}} + (\mathbf{P_{2}} - \mathbf{P_{1}})t)t + ( \mathbf{P_{0}} + (\mathbf{P_{1}} - \mathbf{P_{0}})t )(1-t), t \in [0,1] \end{align} $$

三阶以上

通过上面分析可以得出

  1. 先用三个一阶插值得到三个点
  2. 再在这三个点之间用两个一阶插值得到两个点
  3. 再用一次一阶插值得到最终曲线上的点

于是n阶的曲线可以这样归纳,实际上n阶曲线有n+1个点,就如同一阶曲线有两个点

  1. 用n个一阶插值得到n个点
  2. 在这n个点用n-1个一阶插值得到n-1个点
  3. 如此类推得到曲线上的点

也给编程实现上带来了方便

实现

线性插值公式

$$ \mathbf{P} = (\mathbf{B} - \mathbf{A})t + \mathbf{A} $$

下面是并不正式的伪代码

linearInterpolate(start, end, t) {
	return (end - start) * t + start
}

// 对点的插值只是为了方便对二元组数值进行插值
// 更一般化的实现应该支持对任意维数的矩阵进行插值,甚至不同维度使用不同的t
// 当然这就有点扯远了
linearInterpolatePoint(start, end, t) {
	return {
		x: linearInterpolate(start.x, end.x, t),
		y: linearInterpolate(start.y, end.y, t),
	}
}

// points: [{x, y}, {x, y}, ...]
bezierPoint(points, t) {
	current_points = points
	next_points = []
	for (i from 0 to len(points)-1) { // 迭代n次 对应n阶
		if (len(current_points) == 1) { // 迭代结束条件
			return current_points[0]
		}
		for (n from 0 to len(current_points)-2) { // 按照顺序每两个点之间插值
			start = current_points[n]
			end = current_points[n+1]
			m = linearInterpolatePoint(start, end, t)
			next_points.append(m)
		}
		current_points = next_points
		next_points.clear()
	}
}

其实贝塞尔曲线可以用在插值上,把每个点的x和y都分开来插值,就得到了单一数值的插值器

所以也可以按照下面来实现

// 单一数值贝塞尔插值
// values: [number, number, number, ...]
bezier(values, t) -> value

bezierPoint(points, t) {
	xs = [for every point x value in points]
	ys = [for every point y value in points]
	return {
		x: bezier(xs, t),
		y: bezier(ys, t)
	}
}

PS: 这个页面全部公式都是用MathJax来写的,顺便熟悉了一把MathJax和Tex