Estimation of tissue stiffness is an important means of noninvasive cancer detection. Existing elasticity reconstruction methods usually depend on a dense displacement field (inferred from ultrasound orMR images) and known external forces.Many imaging modalities, however, cannot provide details within an organ and therefore cannot provide such a displacement field. Furthermore, force exertion and measurement can be difficult for some internal organs, making boundary forces another missing parameter. We propose a general method for estimating elasticity and boundary forces automatically using an iterative optimization framework, given the desired (target) output surface. During the optimization, the input model is deformed by the simulator, and an objective function based on the distance between the deformed surface and the target surface is minimized numerically. The optimization framework does not depend on a particular simulation method and is therefore suitable for different physical models. We show a positive correlation between clinical prostate cancer stage (a clinical measure of severity) and the recovered elasticity of the organ. Since the surface correspondence is established, our method also provides a non-rigid image registration, where the quality of the deformation fields is guaranteed, as they are computed using a physics-based simulation.

We present a novel algorithm to compute a simplified medial axis of a polyhedron. Our simplification algorithm tends to remove unstable features of Blum's medial axis. Moreover, our algorithm preserves the topological structure of the original medial axis and ensures that the simplified medial axis has the same homotopy type as Blum's medial axis. We use the separation angle formed by connecting a point on the medial axis to closest points on the boundary as a measure of the stability of the medial axis at the point. The medial axis is decomposed into its parts that are the sheets, seams and junctions. We present a stability measure of each part of the medial axis based on separation angles and examine the relation between the stability measures of adjacent parts. Our simplification algorithm uses iterative pruning of the parts based on efficient local tests. We have applied the algorithm to compute a simplified medial axis of complex models with tens of thousands of triangles and complex topologies.

We present a survey of our recent research on the development of haptic interfaces for simulating creative processes with digital media, including 3D multiresolution modeling and 2D and 3D painting. We discuss the design issues involved and lessons learned. Based on the preliminary user studies, we observe that haptic interfaces can improve the level of usability of digital design systems and assist in capturing the feel of creative processes.

We present a system, ArtNova, for 3D model design with a haptic interface. ArtNova offers the novel capability of interactively applying textures onto 3D surfaces directly by brush strokes, with the orientation of the texture determined the stroke. Building upon the framework of inTouch (Gregory et al., 2000), it further provides an intuitive physically-based force response when deforming a model. This system also uses a user-centric viewing technique that seamlessly integrates the haptic and visual presentation, by taking into account the user's haptic manipulation in dynamically determining the new viewpoint locations. Our algorithm permits automatic placement of the user viewpoint to navigate about the object. ArtNova has been tested by several users and they were able to start modeling and painting with just a few minutes of training. Preliminary user feedback indicates promising potential for 3D texture painting and modeling.

Many geometric problems like generalized Voronoi diagrams, medial axis computations and boundary evaluation involve computation and manipulation of non-linear algebraic primitives like curves and surfaces. The algorithms designed for these problems make decisions based on signs of geometric predicates or on the roots of polynomials characterizing the problem. The reliability of the algorithm depends on the accurate evaluation of these signs and roots. In this paper, we present a {\em naive precision-driven computational model} to perform these computations reliably and demonstrate its effectiveness on a certain class of problems like sign of determinants with rational entries, boundary evaluation and curve arrangements. We also present a novel algorithm to compute all the roots of a univariate polynomial to any desired accuracy. The computational model along with the underlying number representation, precision-driven arithmetic and all the algorithms are implemented as part of a stand-alone software library, PRECISE.

We present a hybrid path planning algorithm for rigid and articulated bodies translating and rotating in a 3D workspace. Our approach generates a Voronoi roadmap in the workspace and combines it with "bridges" computed by a randomized path planner with Voronoi-biased sampling. The Voronoi roadmap is computed from a discrete approximation to the generalized Voronoi diagram (GVD) of the workspace, which is generated using graphics hardware. By using this GVD, portions of the path can be generated without random sampling, substantially reducing the number of random samples needed for the full query. The planner has been implemented and tested on a number of benchmarks. Some preliminary comparisons with a randomized motion planner indicate that our planner performs more than an order of magnitude faster in several challenging scenarios.