Gradients Are the New Intervals

Summary

Gradients are the new intervals At the New England Symposium on Graphics, James Tompkin compared graphics researchers to magpies: they're easily distracted by shiny objects and pretty renderings. While this is true, the analogy also holds from a different angle: when I'm reading graphics papers, I'm constantly looking for ideas to steal bring back to my nest. Researchers at IRIT and Adobe Research recently published a paper that's full of interesting ideas, and I'd like to talk about it. This blog post assumes a vague understanding of implicit surface rasterization, and how interval arithmetic is used to both skip regions of space and simplify complex expressions. See this section of the Fidget writeup for a short introduction, or my colloquium talk for a longer explanation. Here's the key sentence from the paper's abstract: We introduce an efficient hierarchical tree pruning method based on the Lipschitz property of SDFs, which is compatible with hard and smooth CSG operators. In this case, "the Lipschitz property" means that the gradient of the distance value is bounded, e.g. $||\nabla f(x, y, z)|| \lt 1$. You'll also see it referred to as Lipschitz continuity. Lipschitz continuity provides a bound on the maximum change in the distance value between two points: if you have points $\vec{p}$ and $\vec{q}$ in 3D space, then $$|f(\vec{p}) - f(\vec{q})| \le ||\vec{p} - \vec{q}||$$ Given this requirement on the distance fields, the authors present two core tricks that can be applied to CSG-tree-flavored models: Pruning identifies primitives which are inactive within a particular region of space, and builds a simplified shape with only active primitives Far-field culling finds primitives which are far from a particular region (and therefore not relevant), and replaces them with a simpler expression. These optimizations make rendering dramatically cheaper, allowing for interactive visualizations of complex models. The first optimization also sounds familiar – I presented ...