Custom Bezier Tool for Pixel Art
Try it here.
In my pursuit to render a well-aliased bezier curve for a pixel art tool, I came upon a paper on rasterizing curves by Alois Zingl. The paper covers many types of curves, but I’m just going to focus on quadratic bezier curves. The code in the paper is written in C++, so I translated the code into JavaScript for my purposes. I highly recommend reading the paper, as it explains the concepts very thoroughly.
A bezier curve is defined parametrically, so it can’t be defined with y as a function of x. Instead, you define x and y separately as a function of t. t represents time, or the progress along the curve, and is limited to a value between 0 and 1. The general idea of this algorithm is to subdivide a bezier curve into segments that don’t change gradient (In other words, the slope of the curve remains in a single quadrant). Then, we can use Bresenham’s algorithm to plot each curve segment.
P1 represents the control point, whereas P0 and P2 are the endpoints. The references to P4 to P8 can be understood by following the diagram in the paper where the curve is subdivided into up to 3 separate curves. Thus, there are 9 points in total, from P0 to P8.
Keep in mind that when t is defined here, it is only partially defined for use in other variables, and it’s used to check which segment to draw first. The reason to check is that the code is set up to draw the segment that requires a horizontal cut first. On line 1133 t gets fully defined. On line 1132, r is the y coordinate where t is at P4, and on line 1135, r is the y coordinate of p3, since the x of P3 and P4 are identical, by definition. P3 is the control point of the first segment. Line 1137 and 1138 reset the coordinates to run the algorithm on the rest of the curve.
The vertical cut section works much the same as the first part, but x and y are swapped. And for the last segment, all that’s left is a bezier segment with no gradient, so there’s no extra code except to plot that segment.
There’s no built in assert function for js, so I just wrote a small function that throws an error if the condition is false.
We use the derivatives of the x and y components to the curve, and use that to calculate an error deviation of the curve. We can use that error to choose the next pixel to be drawn. If the curve only barely enters a pixel, for example at a corner, it won’t be drawn and will result in a nice pixel perfect curve, without staircasing.