A spatial tree for scanning and rendering complex polygons with GPU-accelerated SDF anti-aliasing.
The algorithm works by scanning complex polygons into a spatial tree (binary space partition). Each leaf node in the tree stores:
- A list of intersecting polygon edges
- A boolean indicating whether the center of the node is inside the polygon
The polygon is rendered on the GPU by rasterizing each leaf node as a quad. The fragment shader computes the signed distance of each pixel to the edges stored in the leaf node, detecting whether the pixel is inside the polygon and computing coverage-based anti-aliasing.
- Point-in-polygon: Accelerated via spatial tree traversal with winding number algorithm
- Closest point: Finds the nearest polygon edge to a query point
- Line intersection: Tests whether a line segment intersects the polygon
- Polygon-polygon testing: Tests intersection/containment between two polygons
MIT