4 ms·

Very cool stuff, text rendering is a really hairy problem. I also got nerd sniped by Sebastian Lague's recent video on text rendering [0] (also linked to in t

by exDM69 1y ago

Very cool stuff, text rendering is a really hairy problem. I also got nerd sniped by Sebastian Lague's recent video on text rendering [0] (also linked to in the article) and started writing my own GPU glyph rasterizer. In the video, Lague makes a key observation: most curves in fonts (at least for Latin alphabet) are monotonic. Monotonic Bezier curves are contained within the bounding box of its end points (applies to any monotonic curve, not just Bezier). The curves that are not monotonic are very easy to split by solving the zeros of the derivative (linear equation) and then split the curve at that point. This is also where Lague went astray and attempted a complex procedure using geometric invariants, when it's trivially easy to split Beziers using de Casteljau's algorithm as described in [1]. It made for entertaining video content but I was yelling at the screen for him to open Pomax's Bezier curve primer [1] and just get on with it. For monotonic curves, it is computationally easy to solve the winding number for any pixel outside the bounding box of the curve. It's +1 if the pixel is to the right or below the bounding box, -1 if left or above and 0 if outside of the "plus sign" shaped region off to the diagonals. Further more, this can be expanded to solving the winding number for an entire axis aligned box. This can be done for an entire GPU warp (32 to 64 threads): each thread in a warp looks at one curve and checks if the winding number is the same for the whole warp and accumulate, if not, set a a bit that this curve needs to be evaluated per thread. In this way, very few pixels actually need to solve the quadratic equation for a curve in the contour. There's still one optimization I haven't done: solving the quadratic equation in for 2x2 pixel quads. I solve both vertical and horizontal winding number for good robustness of horizontal and vertical lines. But the solution for the horizontal quadratic for a pixel and the pixel below it is the same +/- 1, and ditto for vertical. So you can solve the quadratic for two curves (a square root and a division, expensive arithmetic ops) for the price of one if you do it for 2x2 quads and use warp level swap to exchange the results and add or subtract 1. This can only be done in orthographic projection without rotation, but the rest of the method also works in with perspective, rotation and skew. For a bit of added robustness, Jim Blinn's "How to solve a quadratic equation?" [2] can be used to get rid of some pesky numerical instability. I'm not quite done yet, and I've only got a rasterizer, not the other parts you need for a text rendering system (font file i/o, text shaping etc). But the results are promising: I started at 250 ms per frame at a 4k rendering of a '@' character with 80 quadratic Bezier curves, evaluating each curve at each pixel, but I got down to 15 ms per frame by applying the warp vs. monotonic bounding box optimizations. These numbers are not very impressive because they are measured on a 10 year old integrated laptop GPU. It's so much faster on a discrete gaming GPU that I could stop optimizing here if it was my target HW. But it's already fast enough for real time in practical use on the laptop because I was drawing an entire screen sized glyphs for the benchmark. [0] https://www.youtube.com/watch?v=SO83KQuuZvg https://www.youtube.com/watch?v=SO83KQuuZvg [1] https://pomax.github.io/bezierinfo/#splitting https://pomax.github.io/bezierinfo/#splitting [2] https://ieeexplore.ieee.org/document/1528437 https://ieeexplore.ieee.org/document/1528437

meindnoch 1y ago
>Monotonic Bezier curves are contained within the bounding box of its end points What's a "monotonic Bezier curve"? Btw, every Bezier curve is contained within its control points' convex hull. It follows from the fact that all points on a Bezier curve are some convex combination of the control points. In other words, the Bezier basis functions sum to 1, and are nonnegative everywhere.
- exDM69 1y ago
  > What's a "monotonic Bezier curve"? Good question! It's a Bezier curve that has a non-zero derivative for t=0..1 (exclusive). Just your high school calculus definition of monotonic. To get from a general quadratic Bezier to monotonic sections, you solve the derivative for zeros in x and y direction (a linear equation). If the zeros are between 0 and 1 (exclusive), split the Bezier curve using de Casteljau's at t=t_0x and t=t_0y. For each quadratic Bezier you get one to three monotonic sections. > every Bezier curve is contained within its control points' convex hull. This is true, but only monotonic Bezier curves are contained between the AABB formed by the two end points (so control points in the middle don't need to be considered outside the AABB). For a quadratic Bezier this means that it is monotonic iff the middle control point is inside the AABB of the two end points. The monotonicity is a requirement for all the GPU warp level AABB magic to happen (which is a nice 10x to 20x perf increase in my benchmarks). At worst you'd have to deal with 3x the number of curves after splitting (still a win), but because most curves in fonts are monotonic the splitting doesn't increase the the number of curves a lot in practice. Monotonicity also implies that the quadratic equations have only one unique solution for any horizontal or vertical line. No need to classify the roots as in Lengyel's method.
purplesyringa 1y ago
This sounds amazing, personally I'd love to take a look at the project or read a blog post when you're done.
- exDM69 1y ago
  Thanks for the words of encouragement. I need more time to turn this prototype into a practical piece of software and/or a publication (blog post or research paper). Unfortunately there are only so many hours in a day. To actually render text I would still need to add text shaping to get from strings of text to pixels on the screen. But a bigger problem is how to integrate it into someone else's software project. I have the rasterizer GPU shader and some CPU preprocessing code and the required 3d API code (I'm using Vulkan). I'm not sure how people usually integrate this kind of components to their software, do they just want the shader and preprocessor or do they expect the 3d API code too. Packaging it into a library that has the Vulkan code too has its own problems with interoperability. You need to hope that it rains during my summer vacation, maybe this project will see some progress :)

by exDM69 1y ago

meindnoch 1y ago

>Monotonic Bezier curves are contained within the bounding box of its end points What's a "monotonic Bezier curve"? Btw, every Bezier curve is contained within its control points' convex hull. It follows from the fact that all points on a Bezier curve are some convex combination of the control points. In other words, the Bezier basis functions sum to 1, and are nonnegative everywhere.

exDM69 1y ago
> What's a "monotonic Bezier curve"? Good question! It's a Bezier curve that has a non-zero derivative for t=0..1 (exclusive). Just your high school calculus definition of monotonic. To get from a general quadratic Bezier to monotonic sections, you solve the derivative for zeros in x and y direction (a linear equation). If the zeros are between 0 and 1 (exclusive), split the Bezier curve using de Casteljau's at t=t_0x and t=t_0y. For each quadratic Bezier you get one to three monotonic sections. > every Bezier curve is contained within its control points' convex hull. This is true, but only monotonic Bezier curves are contained between the AABB formed by the two end points (so control points in the middle don't need to be considered outside the AABB). For a quadratic Bezier this means that it is monotonic iff the middle control point is inside the AABB of the two end points. The monotonicity is a requirement for all the GPU warp level AABB magic to happen (which is a nice 10x to 20x perf increase in my benchmarks). At worst you'd have to deal with 3x the number of curves after splitting (still a win), but because most curves in fonts are monotonic the splitting doesn't increase the the number of curves a lot in practice. Monotonicity also implies that the quadratic equations have only one unique solution for any horizontal or vertical line. No need to classify the roots as in Lengyel's method.

purplesyringa 1y ago

This sounds amazing, personally I'd love to take a look at the project or read a blog post when you're done.

exDM69 1y ago
Thanks for the words of encouragement. I need more time to turn this prototype into a practical piece of software and/or a publication (blog post or research paper). Unfortunately there are only so many hours in a day. To actually render text I would still need to add text shaping to get from strings of text to pixels on the screen. But a bigger problem is how to integrate it into someone else's software project. I have the rasterizer GPU shader and some CPU preprocessing code and the required 3d API code (I'm using Vulkan). I'm not sure how people usually integrate this kind of components to their software, do they just want the shader and preprocessor or do they expect the 3d API code too. Packaging it into a library that has the Vulkan code too has its own problems with interoperability. You need to hope that it rains during my summer vacation, maybe this project will see some progress :)