Abstract: Sparsity is one of the most commonly relied-upon tools in geometric computing; beyond its immediate evocation of efficient linear algebraic operations, it also more geometrically applies when culling regions to accelerate spatial queries. However, I argue that there are a large class of problems for which sparsity imposes undesirable properties on the solution, and we must instead look towards dense methods. I first present some work on applying this principle to design smooth distance functions for collections of simplices, which smoothly combines all constituent distances rather than selecting the smallest one. This formulation not only offers better isosurfaces around geometrically disjoint representations like point clouds, but also provably underestimates the exact distance to the original geometry. Acceleration methods for such “kernel sums” requires adaptive methods that are ill-suited for acceleration on the GPU, so I will then discuss a stochastic reformulation of the Barnes-Hut approximation method commonly used for such problems, which provides superior GPU performance at comparable accuracy to its deterministic counterpart. Finally, I will discuss future directions to broaden the applicability and ease of use of dense adaptive methods.

Speaker Bio: Abhishek Madan is a final-year PhD student at the University of Toronto, supervised by David Levin. His research concerns methods for maximizing the use of non-mesh geometric representations for downstream applications, as well as numerical techniques to support such methods on massively parallel hardware. He has completed research internships at Adobe and NVIDIA. Previously, he did his undergraduate degree in Software Engineering at the University of Waterloo.

Sponsor: The Carnegie Mellon Graphics Seminar is generously supported by Roblox.