Following the construction of a Bézier curve, the next important task is to find the point C(u) on the curve for a particular u. A simple way is to plug u into every basis function, compute the product of each basis function and its corresponding control point, and finally add them together. While this works fine, it is not numerically stable (i.e., could introduce numerical errors during the course of evaluating the Bernstein polynomials).
In what follows, we shall only write down the control point numbers. That is, the control points are 00 for P0, 01 for P1, ..., 0i for Pi, ..., 0n for Pn. The 0s in these numbers indicate the initial or the 0-th iteration. Later on, it will be replaced with 1, 2, 3 and so on.
The fundamental concept of de Casteljau's algorithm is to choose a point C in line segment AB such that C divides the line segment AB in a ratio of u:1-u (i.e., the ratio of the distance between A and C and the distance between A and B is u). Let us find a way to determine the point C.
The vector from A to B is B - A. Since u is a ratio in the range of 0 and 1, point C is located at u(B - A). Taking the position of A into consideration, point C is A + u(B - A) = (1 - u)A + uB. Therefore, given a u, (1 - u)A + uB is the point C between A and B that divides AB in a ratio of u:1-u.
The idea of de Casteljau's algorithm goes as follows. Suppose we want to find C(u), where u is in [0,1]. Starting with the first polyline, 00-01-02-03...-0n, use the above formula to find a point 1i on the leg (i.e. line segment) from 0i to0(i+1) that divides the line segment 0i and 0(i+1) in a ratio of u:1-u. In this way, we will obtain n points 10, 11, 12, ...., 1(n-1). They define a new polyline of n - 1 legs.
In the figure above, u is 0.4. 10 is in the leg of 00 and 01, 11 is in the leg of 01 and 02, ..., and 14 is in the leg of04 and 05. All of these new points are in blue.
The new points are numbered as 1i's. Apply the procedure to this new polyline and we shall get a second polyline of n - 1 points 20, 21, ..., 2(n-2) and n - 2 legs. Starting with this polyline, we can construct a third one of n - 2 points 30,31, ..., 3(n-3) and n - 3 legs. Repeating this process n times yields a single point n0. De Casteljau proved that this is the point C(u) on the curve that corresponds to u.
Let us continue with the above figure. Let 20 be the point in the leg of 10 and 11 that divides the line segment 10 and 11in a ratio of u:1-u. Similarly, choose 21 on the leg of 11 and 12, 22 on the leg of 12 and 13, and 23 on the leg of 13and 14. This gives a third polyline defined by 20, 21, 22 and 23. This third polyline has 4 points and 3 legs. Keep doing this and we shall obtain a new polyline of three points 30, 31 and 32. From this fourth polyline, we have the fifth one of two points 40 and 41. Do it once more, and we have 50, the point C(0.4) on the curve.
This is the geometric interpretation of de Casteljau's algorithm, one of the most elegant result in curve design.
Actual Computation
Given the above geometric interpretation of de Casteljau's algorithm, we shall present a computation method, which is shown in the following figure.
First, all given control points are arranged into a column, which is the left-most one in the figure. For each pair of adjacent control points, draw a south-east bound arrow and a north-east bound arrow, and write down a new point at the intersection of the two adjacent arrows. For example, if the two adjacent points are ij and i(j+1), the new point is(i+1)j. The south-east (resp., north-east) bound arrow means multiplying 1 - u (resp., u) to the point at its tail, ij(resp., i(j+1)), and the new point is the sum.
Thus, from the initial column, column 0, we compute column 1; from column 1 we obtain column 2 and so on. Eventually, aftern applications we shall arrive at a single point n0 and this is the point on the curve. The following algorithm summarizes what we have discussed. It takes an array P of n+1 points and a u in the range of 0 and 1, and returns a point on the Bézier curve C(u).
-
-
Q[i] := P[i]; // save input
-
Q[i] := (1 - u)Q[i] + u Q[i + 1];
for i := 0 to n - k do
Input: array P[0:n] of n+1 points and real number u in [0,1]
Output: point on curve, C(u)
Working: point array Q[0:n]
for i := 0 to n do
for k := 1 to n do
return Q[0];
A Recurrence Relation
The above computation can be expressed recursively. Initially, let P0,j be Pj for j = 0, 1, ..., n. That is, P0,j is the j-th entry on column 0. The computation of entry j on column i is the following:
More precisely, entry Pi,j is the sum of (1-u)Pi-1,j (upper-left corner) and uPi-1,j+1 (lower-left corner). The final result (i.e., the point on the curve) is Pn,0. Based on this idea, one may immediately come up with the following recursive procedure:
-
-
-
return (1-u)* deCasteljau(i-1,j) + u* deCasteljau(i-1,j+1)
if i = 0 then
else
function deCasteljau(i,j)
begin
end
This procedure looks simple and short; however, it is extremely inefficient. Here is why. We start with a call todeCasteljau(n,0) for computing Pn,0. The else part splits this call into two more calls, deCasteljau(n-1,0) for computing Pn-1,0 and deCasteljau(n-1,1) for computing Pn-1,1.
Consider the call to deCasteljau(n-1,0). It splits into two more calls, deCasteljau(n-2,0) for computing Pn-2,0 anddeCasteljau(n-2,1) for computing Pn-2,1. The call to deCasteljau(n-1,1) splits into two calls, deCasteljau(n-2,1) for computing Pn-2,1 and deCasteljau(n-2,2) for computing Pn-2,2. Thus, deCasteljau(n-2,1) is called twice. If we keep expanding these function calls, we should discover that almost all function calls for computing Pi,j are repeated, not once but many times. How bad is this? In fact, the above computation scheme is identical to the following way of computing then-th Fibonacci number:
-
-
-
return Fibonacci (n-1) + Fibonacci (n-2)
if n = 0 or n = 1 then
else
function Fibonacci(n)
beginend
This program takes an exponential number of function calls (an exercise) to compute Fibonacci(n). Therefore, the above recursive version of de Casteljau's algorithm is not suitable for direct implementation, although it looks simple and elegant!
An Interesting Observation
The triangular computation scheme of de Casteljau's algorithm offers an interesting observation. Take a look at the following computation on a Bézier curve of degree 7 defined by 8 control points 00, 01, ..., 07. Let us consider a set of consecutive points on the same column as the control points of a Bézier curve. Then, given a u in [0,1], how do we compute the corresponding point on this Bézier curve? If de Casteljau's algorithm is applied to these control points, the point on the curve is the opposite vertex of the equilateral's base formed by the selected points!
For example, if the selected points are 02, 03, 04 and 05, the point on the curve defined by these four control points that corresponds to u is 32. See the blue triangle. If the selected points are 11, 12 and 13, the point on the curve is31. See the yellow triangle. If the selected points are 30, 31, 32, 33 and 34, the point on the curve is 70.
By the same reason, 70 is the point on the Bézier curve defined by control points 60 and 61. It is also the point on the curve defined by 50, 51 and 52, and on the curve defined by 40, 41, 42 and 43. In general, if we select a point and draw an equilateral as shown above, the base of this equilateral consists of the control points from which the selected point is computed.
相关推荐
例如贝塞尔曲线的 API: QPainterPath 的 quadTo() 和 cubicTo() 然后使用 QPainter::drawPath()。 然而,美中不足的是,Qt 的贝塞尔曲线只支持二次和三次,对于更高阶的似乎就无能为力了。 即便多个 quadTo() 或...
这是一份C语言版本的bezier曲线(贝塞尔曲线)绘制代码,实现了二次和三次bezier曲线的绘制,可用于一系列给定的离散点的曲线平滑。此代码封装成函数,可以直接调用。脚本里边有参数和代码的注释,可供使用者学习和...
贝塞尔曲线(Bézier curve),又称贝兹曲线或贝济埃曲线,是应用于二维图形应用程序的数学曲线。一般的矢量图形软件通过它来精确画出曲线,贝兹曲线由线段与节点组成,节点是可拖动的支点,线段像可伸缩的皮筋,我们...
HTML实现贝塞尔曲线
用TC生存二次贝塞尔曲线,其实稍微改一下就可以实现三次贝塞尔曲线的了。
EXCELVBA贝塞尔曲线及插值:根据其中采用的算法, 进一步增添根据 X坐标求 Y坐标, 或根据 Y坐标求X坐标,更切合实际需求
本方讲述了二次贝塞尔曲线算法,并给出了实例程序的讲解
贝塞尔曲线做一个曲线动画框架
安卓 签名 笔迹 平滑 贝塞尔曲线 一种用于 模拟真实 手写笔迹签名 的算法, 要求能够保持原笔迹平滑,并有笔锋的效果. 在网上看了一些资料, 资料很多, 能够达到用于正式产品中的效果的一个都没有找到. 我看到最靠谱...
贝塞尔曲线实现直播点赞效果
有关三次贝塞尔曲线拟合,拟合效果可控!本资源是来源于外国作者,所以资料的质量非常好,matlab解释很详细明了!
Android 贝塞尔曲线动画 拿去直接用
贝塞尔曲线 反算控制点 偏移 镜像 旋转 缩放 拖动 裁剪 计算封闭面积 判断点是否在封闭曲线内部
考虑曲率连续性和最大曲率约束,一种新颖的路径平滑算法是根据三次贝塞尔曲线提出的。 在算法中,贝塞尔转弯和贝塞尔路径分别为发达。 Bezier 转弯首先设计用于连接两个任意配置。 然后可以通过以下方式获得贝塞尔...
本项目为vs2013工程项目,贝塞尔曲线计算,控制点可以多个,支持二维数据,三维数据,使用c++语言编写,直接打开即可运行。
2次贝塞尔曲线算法 用三次Bezier逼近圆弧:圆弧要等分成多少段 用三次Bezier逼近圆弧: 得到控制顶点数组 用三次Bezier逼近圆弧片段
unity 贝塞尔曲线和Dotween配合的具体应用,可以配合你
QT绘制贝塞尔曲线及控制点
主要讲述了圆弧与贝塞尔曲线互相转换 贝塞尔曲线拆分多边形处理中,曲线与圆弧几乎拟合,可以不用分解为线段