|
![](/i/fill.gif) |
>> Invisible is invisibly building a complicated graphics library...
>
> Elaborate, please....
Bezier splines, my friend.
You can plot them using de Casteljau's algorithm. It's really quite
delightfully simple:
deCasteljau t [p] = [[p]]
deCasteljau t ps = ps : deCasteljau t (zipWith (vlinear t) ps (tail ps))
That's the whole algorithm. However, not only can you plot a Bezier
spline, but you can also split it into two halves (which are not
necessarily of equal size):
split_at t ps =
let qss = deCasteljau t ps
in (map head qss, map last qss)
On top of that, you can transform a degree-N Bezier spline into a
degree-(N+1) Bezier spline. Each new control point is a linear
combination of two existing control points.
Now, it follows that this procedure ought to be invertable, and indeed
it is. Since we have
Hi[0] = Lo[0]
Hi[1] = (1 - 1/N) Lo[0] + 1/n Lo[1]
Hi[2] = (1 - 2/N) Lo[1] + 2/n Lo[2]
...
we can reverse the procedure with
Lo[0] = Hi[0]
Lo[1] = Lo[0] + N/1 (Hi[1] - Lo[0])
Lo[2] = Lo[1] + N/2 (Hi[2] - Lo[1])
...
Of course, not every degree-N Bezier spline can be transformed into a
degree-(N-1) spline. As far as I can tell, the acid test is whether the
last of the lower-degree control points matches the last of the
higher-degree control points. If they match, the conversion was
successful. If they don't match, the spline is not representable in the
lower degree.
In addition to all this, you can have "rational" Bezier splines, which
is where the control points are weighted. What you do is you project all
the control points into 3D space using an inverse-perspective
projection. (In other words, a perspective projecting back to 2D takes
them to their original locations.) The control point weight is the
Z-distance. Now you draw the Bezier spline in 3D, and then
perspective-project the whole thing back down to 2D again.
Of course, all the algorithms thus far deal only with /splines/. Usually
what you want is /spline patches/ - that is, a series of connected
splines. Each segment can be connected to the next either smoothly or
with a "corner". A smooth connection requires that the control points
obey certain relationships; you can write software to enforce this
automatically.
On top of all that, it's sometimes useful to have a data structure which
is guaranteed to contain a degree-N spline, so that you can enforce the
spline degree at compile-time using the type system. (For example,
PostScript can only handle *cubic* Bezier splines, and not any other
degree.) So there's some machinery for that.
In fact, this part of the code is so repetative that I actually wrote a
program to write the program. This way I can auto-generate spline types
for degrees 2 to 5 and still have the codebase stay maintainable. Plus I
can do it the least abstract way, so it's quite efficient at run-time.
I still need to go implement B-splines. (In particular, if you have a
rational B-spline with user-defined knots, what you have is NURBS.) Plus
I want to see if I can come up with a way to make a spline that actually
passes through all of the control points. Plus many kinds of curve can
be represented in more than one way, and I want to be able to convert
representations easily.
In short, my "graphics library" so far consists of data structures for
representing various kinds of curves, and manipulating them. You could
use that for graphics, but you could just as well use it for controlling
the parameters on a sound synthesizer. They're just parametric curves.
My plan, eventually, after having constructed a library that can handle
any possible representation of anything you could possibly want to work
on, is to write a series of backends that allow you to draw this stuff
as PNG, JPEG, PPM, SVG, PDF, PostScript...
It might take a while.
Post a reply to this message
|
![](/i/fill.gif) |