>> 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