Recommended resources

[nla33]

Hi,

I'm really interested in learning about software rasterization techniques and algorithms for vector graphics specifically, like the ones used in this project.

However, I'm having a really hard time finding solid resources, probably because these techniques are somewhat niche these days I guess. I was wondering if you could maybe recommend any comprehensive materials (books, papers, presentations etc.) that really dive into this tipic.

In the few books I've come across that even mention these kinds of algorithms, the discussion is usually limited to a single chapter and doesn’t go into much detail at all.

Thank you!

[a-e-k]

Hi there! I just wanted to mention that I haven't forgotten your question. I think it's a great one and I just haven't had time lately to pull together the kind of proper answer that I think it deserves. But know that it's coming.

[nla33]

Hi there! I just wanted to mention that I haven't forgotten your question. I think it's a great one and I just haven't had time lately to pull together the kind of proper answer that I think it deserves. But know that it's coming.

Awesome, thank you! 😄

[a-e-k]

Alright, now that I'm home from my travels, I've pulled together a list of resources and papers that I consulted while writing this library, along with some general knowledge. I've tried to put these roughly in order of the vector graphics rendering "pipeline" in my library.

• Euclidean Vector - Properties and Operations - I assume you know all this already since it's pretty fundamental, but just in case, you'll want to be really comfortable with 2D vector math, and the dot product especially. In 2D graphics, I also find uses for the "perp dot" product all the time. (I maintain that in graphics, if you're calling trig functions too much, you're probably doing it wrong!)
• W3C HTML5 2D canvas specification - Obviously, this provides the basis that I was trying to adapt closely to a C++ API. There's a lot of detail in here, including some abstract descriptions of how the implementations are supposed to work.
• ISO Open Font Format spec, Apple TrueType Reference Manual, Microsoft OpenType Spec - These are the references that I consulted when it came to adding font and text support. In particular, the descriptions of the internal tables where useful when I was writing the code to parse TrueType font files.
• Circles in Angles - This was a blog post that I wrote after working out the math for how to calculate where to put the center of a circle of a given radius that is inscribed in an angle. This is needed for the arc_to() method, but also for computing miter joins for lines.
• Drawing an Elliptical Arc Using Polylines, Quadratic or Cubic Bezier Curves - In my implementation, all shapes get lowered to a series of cubic Bezier splines. In most cases the conversion is exact, but in the case of circular arcs it's approximate. I used this reference for the original implementation for arc(). I later changed to a slightly simpler home-grown solution that was more accurate for my needs, but this was a good start.
• Converting Stroked Primitives to Filled Primitives, Polar Stroking: New Theory and Methods for Stroking Paths - This pair of papers dealing with modern stroke expansion were published concurrently at SIGGRAPH 2020 and were very useful background when I was writing the stroke expansion code. They both have some great examples of how naive methods can fail in high-curvature cases, and how it can be done correctly. I didn't use the full-fat version of these, but I did borrow some ideas (especially from Fig. 10 of the first) without trying to be clever about simplify the path. I also borrowed some of the nice test cases to make sure my code handled them correctly. (It's surprising how many browser canvas implementations don't.) It's also worth learning something about Gaussian curvature, if you don't know it already; both papers give some background on that.
• De Casteljau's Algorithm - I use recursive tesselation for flattening cubic Bezier splines to a series of line segments (forming polygons). De Casteljau's algorithm is the basis of this, where it recursively splits Bezier splines in half by computing series of midpoints.
• Adaptive Subdivision of Bezier Curves - This is a nice writeup by the late author of Anti-Grain Geometry that goes into more details of the recursion, with some ideas about choosing where to split. Adaptive subdivision methods choose whether to recurse or stop based on some estimate of error. I don't use the exact approach here, but a conservative estimate of the maximum distance from the curve, plus a maximum angular turn (determined by solving for the sagitta so that stroke expansion from the tessellated line segments is of sufficient quality).
• Reentrant Polygon Clipping - While I could just rasterize the entire set of polygons and skip over any pixels outside the screen window (and I did exactly this for a large part of the development), it's a lot more efficient to clip the polygons to the screen window first. Then rasterizing only worries about what's visible. I used the classic Sutherland-Hodgman algorithm for this.
• How the stb_truetype Anti-Aliased Software Rasterizer v2 Works - I drew inspiration for this for rasterization with signed trapezoidal areas, but implemented the trapezoidal area idea rather differently than this. Still, this should give you an idea for at least one way of doing it.
• Physically Based Rendering (4th Ed), Chapter 8, Sampling and Reconstruction - This is stuff I already knew very well from my day job at the time writing 3D renderers, but the stuff here, especially Section 8.1, is useful background on how to resample an image correctly. I used this kind of approach to do high quality resampling images for pattern fills and for the draw_image() method.
• Cubic Convolution Interpolation for Digital Image Processing - When you hear of "bicubic interpolation" in an image processing or picture editing program, it's usually the kernel from this paper. This is the specific kernel that I used for the resampling code. It smoothly interpolates with less blockiness that bilinear interpolation when magnifying, and it's a piece-wise polynomial approximation to the sinc function so it antialiases well to when minifying.
• Theoretical Foundations of Gaussian Convolution by Extended Box Filtering - Naive Gaussian blurring (for soft drop shadows here) can be slow when the blur radius is large, since each pixel will need to be convolved with a large Gaussian kernel. It's separable, so instead of doing full 2D convolutions, you can do a pass of 1D convolutions on all the rows, then all the columns or vice versa. But that's still slow. However, iterated convolution of a box kernel is a very good approximation (think of summing dice approaching a Gaussian distribution). And box blurring is very fast, regardless of the kernel size since everything has the same weight - you just add to and subtract from a running sum. This paper is about quickly approximating Gaussian blurs with iterated box-like blurs.
• Compositing Digital Images - Porter-Duff forms the basis for the core compositing and blend modes in vector graphics, and is referenced directly by the Canvas spec. For my implementation, I break down the choices of the parameters to use into four bits and encode them directly into the enum of the operation. That way I can implement all the Porter-Duff operations in just 7 lines of code. (I'm pretty proud of that!)
• sRGB - The Canvas spec - transitively, via reference to the CSS color spec - defines that input colors are in sRGB. While many vector graphics implementations compute in sRGB directly, operating in linearized RGB is a hill I'll die on. (I don't go crazy about color spaces beyond that, though.) If you don't you'll end up with odd looking gradients, inconsistent appearance of antialiased thin line widths and text weights, different text weights for light-on-dark vs. dark-on-light, color shifts when resizing. Here are some examples. I do all my processing and storage in linear RGB internally and convert to and from sRGB on input and output.
• GPUs prefer premultiplication - Premultiplied alpha is also important for correct-looking blending. The Canvas spec actually dictates non-premultiplied alpha, so this is another case where I convert to premultiplied alpha on input, do everything with premultiplied alpha internally, and then un-premultiply on output.
• Dithering - I use floating point RGB color internally and convert and quantize to 8-bit sRGB on output. That means that the internal image buffer can easily represent subtle gradients, but the output may easily end up banded if there are too few steps in the 8-bit sRGB space. My library applies ordered dithering to its output to prevent the banding.

Okay, that covers everything that I'd jotted down in my list of things to mention. By all means, please feel free to follow up if you have any questions, or have things you'd like to know more about.