This thesis presents algorithms for generalized inside/outside computation (via winding numbers) and signed distance computation. By "generalized", we mean that these algorithms make geometric inferences from imperfect data comprising incomplete, inaccurate, or ambiguous observations or representations of shapes. In other words, these algorithms generalize from imperfect data and implicitly approximate the true underlying curve or surface. A theme is that generalization can often be achieved by processing globally-defined functions encoding the geometry of interest, rather than the original, defective curve or surface. For both inside/outside and signed distance computation we can unlock further control over geometry and topology by processing higher-order derivatives of these functions. In many cases, we can also re-cast our algorithms, formulated in terms of smooth functions, onto different discretizations and geometric data structures. Another theme is that inside/outside and signed distance computation are closely related problems; towards this end, we provide a formalization of their relationship that justifies the design of our algorithms.

122 pages

Thesis Committee:
Keenan Crane (Chair)
Ioannis Gkioulekas
Nancy Pollard
Christopher Wojtan (Institute of Science and Technology Austria)

Jignesh Patel, Interim Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Creative Commons: CC-BY (Attribution)

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu