UC Berkeley

This thesis introduces and explores the idea of ``user-guided inverse 3D modeling'' -- an interactive approach to shape construction and redesign that extracts well-structured, parameterized, procedural descriptions from unstructured, hierarchically flat input data, such as point clouds, boundary representation meshes, or even multiple pictorial views of a given inspirational prototype. This approach combines traditional ``forward'' 3D modeling tools with a system of user-guided extraction modules and optimization routines. With a few cursor strokes users can express their preferences regarding the type of modeling primitives to be used in a particular area of the given prototype to be approximated, and they can also select the degree of parameterization associated with each modeling routine. The results are then pliable, structured descriptions that are well suited to implement the particular design modifications intended by the user.

We present research on the components that make up an inverse 3D modeling system. Our research focuses have been (1) fitting of modeling primitives to data; (2) fitting higher-level structure (CSG expressions, symmetry, and hierarchy) to data; (3) minimal user interactions that guide these fitting processes; and finally (4) shape editing using the fitted structure. We also explore what is necessary to ultimately arrive at a clean, exportable result. A key research question guiding the design of our system has been how bringing the user into the loop affects the problem: i.e., where can the user's inputs simplify, accelerate, or otherwise improve the fitting process? What simple inputs can the user provide to unambiguously extract a desired primitive fit? And how can we let the user immediately begin using their fitted primitives to edit the shape? Answering these questions leads us to many new research findings, including: (1) We identify simple, lightweight inputs that allow the system to extract primitives with a great deal of user control, and we present detailed analysis of how these inputs can be ambiguous and what additional inputs may be needed to exactly capture the user's desired primitive fit. (2) We show multiple improvements to the state of the art in fast, effective fitting methods for sweeps and quadric surfaces. These improvements include identifying and fixing a major problem with previously-standard methods for kinematic surface fitting that led to grossly wrong results for data with small noise, and a new insight into the nature of direct, algebraic fitting that leads us to more accurate type-specific quadric fitting. (3) We show how the user can guide a boundary-to-CSG reverse-engineering process: Specifically, we identify cases where the best result of such a process depends on the user's intent, and we show how simple user interactions can let users specify their intents. (4) In addition to the diverse problems faced by individual structure-fitting and shape editing modules, the combination of these modules also presents new research opportunities; we identify new interactions between these diverse modules, including transformations between primitive types and hierarchies that can be imposed across modules.