Vectorize Cubic Bezier for 2D WebGL

Question

I am building a 2D cad-like application in Javascript using WebGL and need to allow users to draw cubic bezier curves. My problem is that, as far as I know, WebGL doesn't have any easy way to draw anything but lines and filled triangles.

What makes it more complicated is that I want 'X' number of pixels per segment, and thus will not be able to just iterate through every 1% along the line.

I imagine that this would go something like:

1. Calculate the total length of the bezier curve
2. Divide that number by the segments per pixel
3. Iterate through the bezier curve by the previous number

This is an extremely high performance situation (hundreds of curves at a time), so I can't afford to use a constant number of segments for every curve.

So, my questions are:

Is there any native way to draw a cubic bezier in WebGL?

If not, can anyone help me with the calculations mentioned above, particularly the total length of a cubic bezier curve?

Answer 1

There's no direct way to tell WebGL to "draw a Curve". Just triangles (and lines).

So I think your general approach (Estimate length, divide for desired smoothness, walk the curve) will be good.

You could use a Vertex Shader to do some of the calculations, though. Depending on your data set, and how much it changes, it might be a win.

In WebGL, the vertex shader takes a list of points as input, and produces a same-sized list of points as output, after some transformation. The list cannot change size, so you'll need to figure out the number of subdivisions up in JS land.

The vertex shader could calculate the curve positions, if you assigned each point an attribute "t" between 0 and 1 for the parametric version of the Bezier. Might be handy.

From wikipedia,

As for Bezier length, if we describe it as (p0, p1, p2, p3) where p0 and p3 are the end points and p1 and p2 are the control points, we can quickly say that the Bezier length is at least dist(p0,p3), and at most dist(p0,p1)+dist(p1,p2)+dist(p2,p3).

Could make a fast-guess based on that.

A more thorough discussion for numerical solution is at https://math.stackexchange.com/questions/338463/length-of-bezier-curve-with-simpsons-rule.

There's no closed form solution.

Possibly of interest, I rendered a little Bezier animation for a blog post

Answer 2

I just wanted to add that clearly, we've been rasterizing Bézier curves for a long time, so in addition to the steve.hollasch.net link (http://steve.hollasch.net/cgindex/curves/cbezarclen.html) I pulled from a linked page in @davidvanbrink's answer, I figured there ought to be other resources for this...obviously WebGL/OpenGL adds another dimensional component into finding the appropriate resolution, but this cannot be something that hasn't been attempted before. I think the following links might prove useful.

http://en.wikipedia.org/wiki/NURBS (Non-uniform rational B-spline) http://antigrain.com/research/adaptive_bezier/index.html (Adaptive Subdivision of Bezier Curves: An attempt to achieve perfect result in Bezier curve approximation) http://www.neuroproductions.be/experiments/nurbs/ http://threejs.org/examples/webgl_geometry_nurbs.html