|
Tips |
home
Tip #3: Drawing Bezier curves with just enough
segments
Added: 30Aug2003
Author: Nils Haeck
Category: Graphics
Problem:
Bezier curves are parametric shapes that are built up from 4 points; the
two endpoints and two control points that determine the direction of the
curve near the endpoints.
In order to calculate any point on the Bezier curve, the 3rd order polynomial
below is used. The parameter U is always in the interval [0, 1].
The X and Y arrays are calculated from the control points in another section.
// Find the position of a bezier point based on running var U
procedure BezierPoint(U: single; var PosX, PosY: single);
var
U2, U3: single;
begin
U2 := U * U;
U3 := U2 * U;
PosX := X[3] * U3 + X[2] * U2 + X[1] * U + X[0];
PosY := Y[3] * U3 + Y[2] * U2 + Y[1] * U + Y[0];
end;
The problem at hand is that the running variable U does not give a clue about how much distance the curve "travels". Simply taking N steps may result in jagged lines and visible increments.
Solution
There is a relatively simple recursive solution to this.. called "divide
and conquer". It comes down to this logic: subdivide a section if
the section length is more than the maximum allowed. Keep on doing this
until each section is within the limits:
| 1. | Start with interval [a, b] with a = 0, b = 1. |
| 2. | Find distance D from P(a) to P(b). If this is bigger
than a predefined limit, go to step 3 otherwise go to step 4. |
| 3. | Divide the interval in two sub-intervals: [a, (a+b)/2]
and [(a+b)/2, b]. For each interval, go to step 2. |
| 4. | We draw a straight line from P(a) to P(b). |
This solution is implemented in the demo project. The demo project adds a bit of extra protection by also checking for a mid point in cases where beginpoint = endpoint.
Download
The demo project, including all source and a Windows executable can be
downloaded here.
