PhD Defence • Computer Graphics • Closest Point Geometry Processing: Extensions and Applications of the Closest Point Method for Geometric Problems in Computer Graphics

Please note: This PhD defence will take place in DC 3317 and online.

Nathan King, PhD candidate
David R. Cheriton School of Computer Science

Supervisors: Professors Christopher Batty, Steven Ruuth

This thesis develops theoretical aspects and numerical methods for solving partial differential equations (PDEs) posed on any object for which closest point queries can be evaluated. In geometry processing (and computer graphics in general), objects are represented on a computer in many different ways. Requiring only closest point queries allows the methods we develop to be used with nearly any representation. Objects can be manifold or nonmanifold, open or closed, orientable or not, and of any codimension or even mixed codimension. Our work focuses on solving PDEs on manifolds using the closest point method (CPM), although some nonmanifold examples are also included.

We develop fundamental extensions of CPM to enable its use for the first time with many applications in geometry processing. Two major impediments stood in our way: the complexity of manifolds commonly found in geometry processing and the inability to impose interior boundary conditions (IBCs) with CPM. We first develop a runtime and memory-efficient implementation of the grid-based CPM that allows the treatment of highly complex manifolds (involving tens of millions of degrees of freedom) and avoids the need for GPU or distributed memory hardware. We develop a linear system solver that can improve both memory and runtime efficiency by up to 2× and 41×, respectively. We further improve runtime by up to 17× with a novel spatial adaptivity framework. We then develop a general framework for IBC enforcement that also only requires closest point queries, which finally allows for many geometry processing applications to be performed with CPM. We implicitly partition the embedding space across (extended) interior boundaries. CPM’s finite difference and interpolation stencils are adapted to respect this partition while preserving up to second-order accuracy. We show that our IBC treatment provides superior accuracy and handles more general BCs than the only existing method [Auer et al. 2012].

We deviate from the common grid-based CPM and further develop a discretization-free CPM by extending a Monte Carlo method to surface PDEs. This enables CPM to enjoy common benefits of Monte Carlo methods, e.g., localized solutions, which are useful for view-dependent applications. Finally, we introduce an algorithm to compute geodesic paths that does not even require a manifold PDE; only heat flow on a 1D line and closest point queries are required. Our method is more general, robust, and always faster (up to 1000×) than the state-of-the-art for general representations [Yuan et al. 2021]. Our method can be up to 100,000× faster (with high-resolution meshes) or slower (with low-resolution meshes) than the state-of-the-art in terms of runtime [Sharp and Crane 2020]. Convergence studies on example PDEs with analytical solutions are given throughout. We further demonstrate the effectiveness of our work for applications from geometry processing, including diffusion curves, vector field design, geodesic distance and paths, harmonic maps, and reaction-diffusion textures.