Warnock: Harnessing GPU Geometry Amplification for Vector Graphics
Warnock: Harnessing GPU Geometry Amplification for Vector Graphics Mark J. Kilgard and Brian Barran HPG'26 We live in a strange world where the primary use case for GPUs is LLMs, the secondary use case is 3D graphics, and one has to perform contortions to accelerate 2D graphics with a GPU. This paper presents a technique to use modern GPU hardware features to offload a portion of 2D graphics rendering that is typically performed on a CPU. There are three hard problems associated with high-quality vector graphics: winding rules, curves, and antialiasing. Say you have given a polygon like so: and you would like to know if a particular point is contained within the polygon. The orthodox definition of the odd-even winding rule is: Draw a ray starting at and pointing in any direction. Count the number of polygon edges that the ray intersects. If the number of intersections is odd, then is inside of the polygon. For example, the ray in the diagram below intersects with the polygon 3 times, and so the ray origin is considered to be inside of the polygon. The flexibility to cast rays in any direction allows for a variety of vector graphics rasterization algorithms. CPU-based iterative algorithms typically cast rays horizontally. The idea is that the algorithms steps vertically one scan line at a time and incrementally tracks the set of edges which intersect the scan line. Data parallel approaches on GPUs can cast rays in a different direction. Here is a common way to do it (also used by this paper): Pick an arbitrary point (somewhere near the center of the polygon) and draw a triangle fan emanating from that point. A triangle fan is like those collapsible hand-held fans with ridges. Here is a triangle fan for the running example, with each triangle in a unique (partially transparent) color: Here is the key: to determine if is covered by the triangle, we will logically cast a ray with an origin of , and a direction that points directly away from the center of the triangle fan, like so: Putting it all together, the way to do this on a GPU is to use an intermediate 2D buffer (i.e., a stencil buffer) which holds an integer for every pixel. This buffer starts out with a value of 0 at each pixel. Then instruct the GPU to rasterize each triangle in the triangle fan. For each pixel that is covered by a triangle, increment the associated integer. When all triangles in a fan have been rendered, then a pixel is considered to be covered if the stencil buffer contains an odd value at that pixel. GPUs are extremely fast at rasterizing triangles (i.e., determining which pixels are covered by a triangle), so this technique works well. Most interesting vector graphics contains curves in addition to lines. A curve can be approximated by a series of lines, but this approximation is necessarily resolution dependent. If you zoom in on a curve, then more line segments are required to accurately represent it. The Warnock paper proposes to use geometry amplification hardware to decompose curves into sequences of line segments in real time. Somewhat older GPUs support a feature called tessellation , while newer GPUs support mesh shading . The idea is that the CPU can generate an abstract representation of an object, along with a program that that runs on the GPU each frame to convert from that representation to a variable number of triangles. The variable number part is the key, this GPU-side program can determine how finely to approximate a curve based on runtime parameters like how large the curve will be on screen. This paper uses polar filling on the GPU. The idea is that each triangle in the triangle fan is separated a maximum angle. Fig. 5. illustrates polar filling for a specific shape. Note how some areas of the light green shape are represented with few lines, while curvy areas are represented with many lines. Source: https://dl.acm.org/doi/10.1145/3820012 Section 3 of the paper goes into the nitty gritty of the math behind polar filling. In the domain of vector graphics antialiasing means to not make a binary decision about each pixel: “is the pixel covered by the shape or not?”. Rather some pixels on the edge of a shape can be considered to be partially covered. This is a hard problem for 2D vector graphics because the entire shape must be considered. Antialiasing cannot be resolved on a per-triangle basis. For example, if a given pixel is 50% covered by one triangle and 50% covered by another, should that pixel be considered to be 100% covered? It depends on the relative overlap of the two triangles. This paper doesn’t present any advances in this space, and instead relies on hardware antialiasing features to evaluate the stencil buffer at multiple locations per pixel. Table two contains performance results against industrial strength 2D graphics libraries, and against a prior NVIDIA implementation: Source: https://dl.acm.org/doi/10.1145/3820012 Warnock does well against industrial libraries… but Direct2D doesn’t get beat too badly. I’m particularly proud of this as I spent a few years of my life optimizing the Direct2D implementation. Modern GPUs have ray tracing support, which can be hijacked for some interesting purposes. Since 2D vector graphics rasterization is fundamentally defined in terms of rays, I wonder if ray tracing hardware could be another approach to 2D vector graphics rendering. Thanks for reading Dangling Pointers! Subscribe for free to receive new posts.
Programming
Web
DevOps
Hardware
Performance
Sql
C++
Data Analysis
Open Source
Cloud
C
Rust
Docker