David E. Breen: Research Interests - Geometric Modeling

My work in geometric modeling began with my Master's project, which involved the development of algorithms for the fitting and smooth-shading of Steiner surfaces (See Breen 1986). I also developed an algorithm for CSG evaluation (Constructive Cubes) based on spatial enumeration and the Marching Cubes algorithm (See Breen 1991). The Constructive Cubes (CC) Algorithm was later extended to become a major component of a 3-D scan conversion algorithm. (See Breen et al. 1998). This algorithm may be used to generate a distance volume from a CSG model consisting of superquadric primitives. A distance volume is a volume dataset where each voxel stores the shortest distance to the object embedded in the volume. The extended CC algorithm is used to calculate shortest distance/closest point information in a narrow band around the evaluated surface of the CSG model. A Fast Marching Method is then employed to propagate the shortest distance/closest point information to the remaining voxels in the volume. Distance volumes provide the initial input for a 3-D morphing algorithm. They may also be used to generate offset surfaces from the original CSG model. The scan conversion method has been extended to also create color and closest-point volumes, which may be used to color-shade the surface models extracted from the distance volume. (See Breen et al. 1999, 2000).

I have been involved in two projects investigating algorithms for extracting adaptive, multiresolution meshes from volume datasets. (See Wood et al. 2000, and Gavriliu et al. 2001). These approaches are useful for extracting high-quality meshes directly from volumes, rather than first generating Marching Cubes meshes, which are then cleaned up as a post-process. The Gavriliu et al. technique was patented in 2004.

I contributed to the development of a procedural method for generating stochastic microgeometry for displacement mapping. Here, stochastic geometry contact distributions are used to describe non-deterministic features on surface models. The technique is useful for producing many different kinds of irregular surface detail with a single mathematically- and physically-sound computational approach; thus providing a powerful model processing tool for transforming smooth, "ideal" geometric models into convincing representations of natural or hand-made objects. (See Schroeder et al. 2005). A poster that summarizes the technique is available here.

I have been involved in several contour-based surface reconstruction projects. This work involves creating 3D surfaces from sets of contours that have been manually or automatically extracted from 2D images produced by some kind of scanning process. In the first project 2D level set morphing is used to transform one contour into the next in order to sweep out a smooth 3D surface that interpolates the input contours. (See Nilsson et al. 2005). In the second project MPU implicit models are used to smooth the input binary contours. A 2D distance field is calculated around the MPU curve and then is filtered to remove the medial axis discontinuities. The 2D fields are interpolated with monotonicity-constrained splines to produce a 3D field. The reconstructed surface is the zero level set of the 3D field. (See Marker et al. 2006). A poster that summarizes the technique is available here. The third method utilizes Multi-level Partition of Unity (MPU) implicit models to reconstruct surfaces from noisy input contours. Almost all contour-based surface reconstruction techniques exactly interpolate the input contours. MPU implicit surfaces are a type of point set surface that approximates input data within user-specified error bounds. Thus they offer an approach that inherently copes with noisy data in a controllable fashion. The MPU-based reconstruction technique interprets the contour data (pixels in individual images) as points in 3-space. Since MPU implicits also require normal information, it was necessary to develop an algorithm to estimate surface normals from the stacked contours. (See Braude et al. 2007).

In collaboration with Kurt Swanson and Dr. Ken Brakke, we developed techniques for geometric modeling using the minimal surfaces of soap films. (See Swanson et al. 2008, 2009).

As imaging and simulation technology continues to be rapidly deployed and utilized in medicine, engineering and science, an increasing number of volume datasets are generated, producing an overwhelming flood of raw 3D data that must be processed, viewed and analyzed. Given the multiple sources of volumetric datasets, there is a great need for powerful implicit model editing capabilities. In response to this need a project to develop techniques and algorithms for interactive freeform editing of large-scale, multiresolution level set models was conducted. Level set models combine a low-level volumetric representation, the mathematics of deformable implicit surfaces, and robust numerical techniques to produce a powerful approach to geometric modeling.

I led an effort to develop a set of editing operators for modifying level set models. These operators provide a powerful approach to creating complex objects from volumetric models. They were implemented in a modeling framework and the initial set of operators included CSG operators with localized blending, localized smoothing for model repair, as well as morphological operators (See Museth et al. 2002, 2003, 2005). These technique were patented in 2007.
Next a suite of freeform surface editing operators that allow a user to interactively manipulate level set surfaces via a direct click-and-pull paradigm. (See Eyiyurekli and Breen 2010 and associated poster). Additional indirect sketch-based editing techniques for level set models have been developed (See Eyiyurekli et al. 2009), based on localized Catmull-Rom splines (See Eyiyurekli and Breen 2009), Our work has shown that spatial hash tables are an effective data structure for storing and interactively modifying large-scale unbounded level set models (See Eyiyurekli and Breen 2011 and associated poster). We have extracted surface details from level set models using particle systems, and then used these particles to restore smoothed-out details resulting from the editing operators. Additionally the particles may be used to transer surface details from one level set model to another (See Eyiyurekli and Breen 2017). The framework for extracting surface details may also be used for multiresolution level set modeling (See Eyiyurekli 2012).

The initial work in this area investigated the effectiveness of tensor voting tokens as geometric modeling constructs (See Beltowska et al. 2008 and associated poster).