My research is based on the development of efficient operations for geometric models and the useful application of these methods. A useful view of this work is that geometric operations can solve symbolic constraint equations describing a wide variety of problems. My dissertation work examined this approach in the context of force-feedback interfaces in virtual worlds, while recent work has expanded on the theme of solving constraint equations efficiently and applying these results to areas such as robot motion planning and geometric modeling operations.

Geometric Constraint Solvers

 Geometric constraint solvers build representations of symbolic equations and search for solutions. Constraint solvers have the potential to become standard "black box" solvers that can solve a wide variety of problems. The research challenge lies in making these solvers powerful enough to address problems of practical importance.

Working with post-doctoral associate Jun-Kyung Seong, our research has applied a new class of B-spline solvers to distance problems. By casting the problem into a higher-dimensional space of all possible queries, individual queries can be efficiently solved. The image at left shows one example of this higher-dimensional solution space.

Some drawbacks to the B-spline constraint solver are the computation-time and memory required to explicitly build these high-dimensional equations, as well as only applying to B-spline data as input. To address this, we have been developing a new class of constraint solvers that work by sampling the equations and pruning the parameter space based on conservative bounds. Thus far, this approach has been applied to geometric computations such as model offset, bisectors of two models (see image at left), and some cell-decomposition based robot path planners. A selection of papers in this area are:

David E. Johnson and Elaine Cohen, "Computing Surface Offsets and Bisectors Using a Sampled Constraint Solver", submitted to Graphics Interface 2009, December 19, 2008.

Seong, Joon-Kyung, Johnson, David E., and Cohen, Elaine, "A Higher Dimensional Formulation for Robust and Interactive Distance Queries," in ACM Solid and Physical Modeling 2006, 2006.

Haptic Interfaces and Haptic Rendering

 Haptic interfaces use robotic devices to apply forces to a human operator. These interfaces can create a sense of contact with a virtual environment. Since humans possess natural skills at manipulation and exploration, we would like to use these skills in complex 3D environments.

A key component of a haptic interface is the software that generates the forces needed to simulate contact. This software relies on fast computation of distance, collision, and penetration between virtual models. We have developed many of the basic algorithms used in haptic rendering of spline and polygonal models.

A selection of papers in this area are:

Johnson, D. E., Willemsen, P., and Cohen, E., "6-DOF Haptic Rendering Using Spatialized Normal Cone Search," Transactions on Visualization and Computer Graphics, 2005.

David E. Johnson and Elaine Cohen, "Haptic Rendering of Sculptured Models", in Haptic Rendering: Foundations, Algorithms, and Applications (Ming Lin and Miguel Otaduy, eds.), AK Peters, 2008.

Minimum Distance Queries


(click for a fairly old short video)

 Minimum distance queries are a basic operation on computer models, useful in areas such as haptics, simulation, and robot path planning. Research for methods on continuous models tend towards numerical methods solution of a symbolic equation describing the distance. Some of my dissertation results gave new techniques for reliable converge of numerical methods under certain conditions. More recently, constraint solvers have proven to be robust and efficient at finding distance minima.

Insights from these approachs provided the basis for new techniques on polygonal models which solve for local as well as global minima in distance. This polygonal approach has been applied to haptic rendering of polygonal models, where the local minima enhance the stability of the simulation.

Interestingly, some of the ideas from the polygonal domain have been re-adapted back into the continuous domain, where geometric operations have robustly captured some aspects of the symbolic constraint solution.

A selection of papers in this area are:

Johnson, David and Cohen, Elaine, "Spatialized Normal Cone Hierarchies," in Proc. 2001 ACM Symposium on Interactive 3D Graphics, Research Triangle Park, NC, March 19-21, 2001. pp. 129-134.

Johnson, D. and Cohen, E., "Distance Extrema for Spline Models Using Tangent Cones," in Graphics Interface 2005, 2005.

Johnson, David E., and Cohen, Elaine, "An improved method for haptic tracing of sculptured surfaces," Symp. Haptic Interfaces, Proc. ASME Dynamic Systems and Control Division, DSC-Vol. 64, Anaheim, CA, Nov. 15-20, 1998, pp. 243-248.

Virtual Environments and Applications

 Haptic interfaces are a natural component of virtual environments. One application of haptics in VR is virtual prototyping, where mechanical designs are tested on a computer, rather than with physical mockups. Recent work in collaboration with John Hollerbach has been to demonstrate the value of haptic feedback in virtual prototyping tasks where contact forces can provide an ergonomic advantage, thus a purely visual simulation might be inadequate.

A more general VR application has grown out of joint work with Arizona State University and Hampton Unversity for an Army Research Office project. Here, the complexity of assessing multiple data sources during reverse engineering of a mechanical system is alleviated by merging them into a single immersive environment.

Most recently, a VR space is being used to evaluate building design and placement in urban environments relative to pollution dispersal and concentrations. This is joint work with Pete Willemsen at Univ. Minn, Duluth, and Eric Pardyjak of Mechanical Engineering here at the University of Utah. My role in this project primarily has been to adapt some optimization concepts from probabilistic robot planning to search of the high-dimensional urban design space.

A selection of papers in this area are:

Matthew Frey, David Johnson, and John Hollerbach, "Full-Arm Haptics in an Accessibility Task," in Proceedings of the 16th Symposium on Haptic Interfaces for Virtual Environments and Teleoperator Systems (2008 Haptics Symposium), March, 2008.

Musuvathy, S., Johnson, D. de St. Germain, H., Cohen, E., Xu, C., Riesenfeld, R., and Henderson, T. "Integrating Mulitple Engineering Resources in a Virtual Environment for Reverse Engineering Legacy Mechanical Parts,", in ASME IDETC/CIE 2005, 2005.

Eric Pardyjak, Pete Willemsen, and David Johnson, "Optimization of Urban Designs for Air Quality and Energy Efficiency", American Meteorological Society Annual Meeting.

Robot Motion Planning

 Constraint solvers work in a potentially high dimensional parameter space of the problem. This has a strong correspondence to the configuration space of robot path planners, where the degrees-of-freedom of a robot becomes the parameters of the search space. The motion planning community has developed a number of powerful techniques for dealing with these spaces, and we are exploring ways to apply concepts from constraint solvers to path planning and vice versa.

The top image at left shows an adaptive decomposition of a robot configuration space. The red cells represent real-world obstacles translated into the configuration space and the white line is a free path for the robot.

The second image is from work done with a M.S. student, Danny Perry, who used stochastic techniques in conjunction with adaptive decomposition to search for critical points within the configuration space.

I am pursuing a number of other projects with faculty in Mechanical Engineering, Chemistry, and Pharmacology to adapt the configuration space abstraction to problems in different domains.

Collaborative Biomolecular Projects

 The study of biomolecular systems provides an enriching and challenging application for geometric computations. We are currently pursuing projects in ligand-protein binding as well as structural studies of proteins. Some prior work with the Molecular Graphics Lab at the Scripps Research Institute provided background in this area. With the MGL, we produced tangible molecular models for exploration of such things as protein structure and folding. Our research converted atomic descriptions of proteins into articulated models, with such things as magnets to macroscopically simulate atomic level behaviors. This work also inspired some research on converting from polygonal representations of molecular shape to smooth continuous models.