Since my previous post, I discovered, partly to my delight and partly in disappointment that once again I was not the first to do something original. A subdivision method for bezier calculation has already been well documented. It’s call the De Casteljau’s algorithm. This Castle-head guy apparently was the first to discover (and publish ;-P) the idea of finding locations along a cubic bezier curve by simple division of the sides of the curve, and subsequent division of lines drawn between those points, until arriving finally at a point on the curve. It’s a simple and fast method and in addition you can very easily compute the line segments of a curve `in order` rather than recursively, by simply dividing or multiplying the line lengths by some other value consistently.
There is a pleasant and fairly straightforward description of the method at this GamaSutra page (page 2 of an article).
Also on my journey I found this rather nice document which overviews pretty much all types of splines and their features – there are a few more esoteric ones missing, of course, but it talks clearly and understandably most of the way through, covering beziers and b-splines and NURBS and hermite splines and catmull rom and natural splines etc, all good stuff.
Now, I will still use a subdivision kind of system in order to add local alterations to cubic beziers, plus the other features that let it emulate other spline types with bias/tension etc, as mentioned in my previous post. But I’m also reading about b-splines using bezier curves and `weights` for control points, or `knots` – all fancy spline terminology. So I have wondered to myself if, by way of some simple scale factors applied to the lengths of the lines between the control points, if I could simply add a `weight` to each point. That said, this might be exactly the same effect as adding bias or tension. Something I’ll experiment with.
So with that decided, I’ve been looking into how to turn cubic bezier curves into the kind of triangles that computer graphics hardware can draw – remember at the moment that most hardware can’t draw curves (although newer hardware is getting there with geometry shaders and tesselator shaders etc). So we have to turn our nice curves into triangles. How to do that? And fast?
Well, in addition to the links added to the end of my last post, I also found a technique originally mentioned in the OpenGL Red Book, I think it was around Chapter 14, here: Drawing Filled, Concave Polygons Using the Stencil Buffer – you’ll have to scroll down to the section. Basically, you use the stencil buffer to create an image of the overlapping areas of a triangle fan, which you draw starting at the first control point of your bezier, and visiting every other point along the curve as desired. It does quite a bit of `overdraw`, but coupled with an inverting stencil mode it ends up with an image of just the inside of the closed shape (ie your last control point joined to the first, with a straight line or otherwise). Then there is an optional antialiasing pass by drawing antialiased lines where the stencil is absent. And finally you can just draw a quad over the area, only where the stencil shows points, to fill it. It’s realtime, and doesn’t require any sofware tesselation other than calculating points along the bezier. Pretty fast too, hopefully. This will be the basis for my `realtime` beziers.
The technique is also mentioned here.
Then I will further look into precalculated shapes based on simple meshes. So this is what I am working on programming now.
0 Responses to “More on Splines”