Visual Computing Seminar: Support Function Parameterization of Convex Hulls for Fast Distance Queries

Abstract:
Convex hulls are ubiquitous in computational geometry, and they are particularly useful for fast distance queries and collision detection. Standard algorithms for computing distances between convex shapes (e.g., GJK) require input shapes to be represented as support functions (a dual representation of convex shapes). However, support functions are generally difficult to obtain. They are only known in closed form for a limited number of simple primitives--such as ellipsoids, cylinders, or cones--through case-by-case analysis. In general, there is no closed-form expression for the support function of an arbitrary shape. In this talk, we present a variational approach to obtain the global support function of an arbitrary shape, given only a way to sample points from the shape. By characterizing the desired support function as the minimizer of a variational problem over sublinear functions, we bypass the need to solve a typical regression problem. Beyond fast distance queries, our variational formulation also provides an easy way to parameterize continuously-deforming convex hulls.