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 postdoctoral associate JunKyung Seong, our research has
applied a new class of Bspline solvers to distance problems. By
casting the problem into a higherdimensional space of all possible
queries, individual queries can be efficiently solved. The image at
left shows one example of this higherdimensional solution space.
Some drawbacks to the Bspline constraint solver are the
computationtime and memory required to explicitly build these
highdimensional equations, as well as only applying to Bspline 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
celldecomposition 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, JoonKyung, 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., "6DOF 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
readapted 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 1921,
2001. pp. 129134.
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, DSCVol. 64,
Anaheim, CA, Nov. 1520, 1998, pp. 243248.

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 highdimensional urban design space.
A selection of papers in this area are:
Matthew Frey, David Johnson, and John Hollerbach, "FullArm 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
degreesoffreedom 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 realworld 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 ligandprotein 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.
