New types of "engaging" embedded systems and devices will greatly assist future medical care, as for Petrasek's envisioned Global Virtual Hospital System. The most effective devices will need to be designed in a "parsimonious" way for their economic use of energy, digital bits, communication time, and in terms of trading more expensive physical structures for less expensive computational ones. At the technological level, each device needs a carefully selected "matched set" of technological tradeoffs between the particular medical and user ends and means. The matched set of choices would carefully make sure that the device "methods" and implementations lead reliably to the device "goals" and purposes.

In this paper we use advanced tensor visualization techniques to study 3D diffusion tensor MRI data of a heart. We use scalar and tensor glyph visualization methods to investigate the data and apply a moving least squares (MLS) fiber tracing method to recover and visualize the helical structure and the orientation of the heart muscle fibers.

In this paper we develop a new technique for tracing anatomical fibers from 3D tensor fields. The technique extracts salient tensor features using a local regularization technique that allows the algorithm to cross noisy regions and bridge gaps in the data. We applied the method to human brain DT-MRI data and recovered identifiable anatomical structures that correspond to the white matter brain-fiber pathways. The images in this paper are derived from a dataset having 121/spl times/88/spl times/60 resolution. We were able to recover fibers with less than the voxel size resolution by applying the regularization technique, i.e., using a priori assumptions about fiber smoothness. The regularization procedure is done through a moving least squares filter directly incorporated in the tracing algorithm.

We present a level set framework for implementing editing operators for surfaces. Level set models are deformable implicit surfaces where the deformation of the surface is controlled by a speed function in the level set partial differential equation. In this paper we define a collection of speed functions that produce a set of surface editing operators. The speed functions describe the velocity at each point on the evolving surface in the direction of the surface normal. All of the information needed to deform a surface is encapsulated in the speed function, providing a simple, unified computational framework. The user combines pre-defined building blocks to create the desired speed function. The surface editing operators are quickly computed and may be applied both regionally and globally. The level set framework offers several advantages. 1) By construction, self-intersection cannot occur, which guarantees the generation of physically-realizable, simple, closed surfaces. 2) Level set models easily change topological genus, and 3) are free of the edge connectivity and mesh quality problems associated with mesh models. We present five examples of surface editing operators: blending, smoothing, sharpening, openings/closings and embossing. We demonstrate their effectiveness on several scanned objects and scan-converted models.

This paper presents a robust, adaptive method for animating dynamic visco-elastic deformable objects that provides a guaranteed frame rate. Our approach uses a novel automatic space and time adaptive level of detail technique, in combination with a large-displacement (Green) strain tensor formulation. The body is partitioned in a non-nested multiresolution hierarchy of tetrahedral meshes. The local resolution is determined by a quality condition that indicates where and when the resolution is too coarse. As the object moves and deforms, the sampling is refined to concentrate the computational load into the regions that deform the most. Our model consists of a continuous differential equation that is solved using a local explicit finite element method. We demonstrate that our adaptive Green strain tensor formulation suppresses unwanted artifacts in the dynamic behavior, compared to adaptive mass-spring and other adaptive approaches. In particular, damped elastic vibration modes are shown to be nearly unchanged for several levels of refinement. Results are presented in the context of a virtual reality system. The user interacts in real-time with the dynamic object through the control of a rigid tool, attached to a haptic device driven with forces derived from the method.

We present a new algorithm for extracting adaptive multiresolution triangle meshes from volume datasets. The algorithm guarantees that the topological genus of the generated mesh is the same as the genus of the surface embedded in the volume dataset at all levels of detail. In addition to this "hard constraint" on the genus of the mesh, the user can choose to specify some number of soft geometric constraints, such as triangle aspect ratio, minimum or maximum total number of vertices, minimum and/or maximum triangle edge lengths, maximum magnitude of various error metrics per triangle or vertex, including maximum curvature (area) error, maximum distance to the surface, and others. The mesh extraction process is fully automatic and does not require manual adjusting of parameters to produce the desired results as long as the user does not specify incompatible constraints. The algorithm robustly handles special topological cases, such as trimmed surfaces (intersections of the surface with the volume boundary), and manifolds with multiple disconnected components (several closed surfaces embedded in the same volume dataset). The meshes may self-intersect at coarse resolutions. However, the self-intersections are corrected automatically as the resolution of the meshes increase. We show several examples of meshes extracted from complex volume datasets.

The paper addresses visualization issues of the Terrestrial Planet Finder Mission (C.A. Beichman et al., 1999). The goal of this mission is to search for chemical signatures of life in distant solar systems using five satellites flying in formation to simulate a large telescope. To design and visually verify such a delicate mission, one has to analyze and interact with many different 3D spacecraft trajectories, which is often difficult in 2D. We employ a novel trajectory design approach using invariant manifold theory, which is best understood and utilized in an immersive setting. The visualization also addresses multi-scale issues related to the vast differences in distance, velocity, and time at different phases of the mission. Additionally, the parameterization and coordinate frames used for numerical simulations may not be suitable for direct visualization. Relative motion presents a more serious problem where the patterns of the trajectories can only be viewed in particular rotating frames. Some of these problems are greatly relieved by using interactive, animated stereo 3D visualization in a semi-immersive environment such as a Responsive Workbench. Others were solved using standard techniques such as a stratify approach with multiple windows to address the multiscale issues, re-parameterizations of trajectories and associated 2D manifolds and relative motion of the camera to "evoke" the desired patterns.

Abstract Modeling and animation of cloth have experienced important developments in recent years. As a consequence, complex textile models can be used to realistically drape objects or human characters in a fairly efficient way. However, real‐time realistic simulation remains a major challenge, even if applications are numerous, from rapid prototyping to e‐commerce. In this paper, we present a stable, real‐time algorithm for animating cloth‐like materials. Using a hybrid explicit/implicit algorithm, we perform fast and stable time integration of a physically based model with rapid collision detection and response, as well as wind or liquid drag effects to enhance realism. We demonstrate our approach through a series of examples in virtual reality environments, proving that real‐time animation of cloth, even on low‐end computers, is now achievable. Copyright © 2001 John Wiley & Sons, Ltd.

This paper presents an adaptive technique to animate deformable bodies in real-time. Our method relies on mixed finite-volume/finite-element method applied to an arbitrary non-nested hierarchy of volumetric meshes. We achieve a guaranteed frame rate thanks to a innovative multi-resolution algorithm that locally refines of simplifies the simulated object in order to concentrate computation load where and when needed.

In this paper, we develop methods to rapidly remove rough features from irregularly triangulated data intended to portray a smooth surface.The main task is to remove undesirable noise and uneven edges while retaining desirable geometric features.The problem arises mainly when creating high-fidelity computer graphics objects using imperfectly-measured data from the real world.Our approach contains three novel features: an implicit integration method to achieve efficiency, stability, and large time-steps; a scale-dependent Laplacian operator to improve the diffusion process; and finally, a robust curvature flow operator that achieves a smoothing of the shape itself, distinct from any parameterization.Additional features of the algorithm include automatic exact volume preservation, and hard and soft constraints on the positions of the points in the mesh.We compare our method to previous operators and related algorithms, and prove that our curvature and Laplacian operators have several mathematically-desirable qualities that improve the appearance of the resulting surface.In consequence, the user can easily select the appropriate operator according to the desired type of fairing.Finally, we provide a series of examples to graphically and numerically demonstrate the quality of our results.

We present a new interaction metaphor for object-centric tasks in the form of a prototype VR system, ALCOVE. Through analytic calculations, we quantitatively demonstrate the benefits of restructuring the interaction volume offered by current systems. Our metrics show that many applications' interaction volume increases by 1.5 to 2.6 times when using the ALCOVE system. We also offer an informal user task analysis and evaluations of previous VR systems that qualitatively support this improved interaction volume as well as demonstrate the need for a shift from room and desk-sized systems to desktop units. We present some testbed applications which benefit from this object-centric design and discuss some of the advantages and shortcomings of our system.

We present a new algorithm for identifying the distribution of different material types in volumetric datasets such as those produced with magnetic resonance imaging (MRI) or computed tomography (CT). Because we allow for mixtures of materials and treat voxels as regions, our technique reduces errors that other classification techniques can create along boundaries between materials and is particularly useful for creating accurate geometric models and renderings from volume data. It also has the potential to make volume measurements more accurately and classifies noisy, low-resolution data well. There are two unusual aspects to our approach. First, we assume that, due to partial-volume effects, or blurring, voxels can contain more than one material, e.g., both muscle and fat; we compute the relative proportion of each material in the voxels. Second, we incorporate information from neighboring voxels into the classification process by reconstructing a continuous function, rho(x), from the samples and then looking at the distribution of values that rho(x) takes on within the region of a voxel. This distribution of values is represented by a histogram taken over the region of the voxel; the mixture of materials that those values measure is identified within the voxel using a probabilistic Bayesian approach that matches the histogram by finding the mixture of materials within each voxel most likely to have created the histogram. The size of regions that we classify is chosen to match the spacing of the samples because the spacing is intrinsically related to the minimum feature size that the reconstructed continuous function can represent.

In 1992, Barr et al. proposed a method for interpolating orientations with unit quaternion curves by minimizing covariant acceleration.This paper presents a simple improved method which uses cubic basis functions to achieve a speedup of up to three orders of magnitude.A new criterion for automatic refinement based on the Euler-Lagrange error functional is also introduced.

We proposean approach for modeling surface details such as scales, feathers, or thorns. These types of cellular textures require a representation with more detail than texture-mapping but are inconvenient to model with hand-crafted geometry. We generate patterns of geometric elements using a biologically -motivated cellular development simulation together with a constraint to keep the cells on a surface. The surface may be defined by an implicit function, a volume dataset, or a polygonal mesh. Our simulation combines and extends previous work in developmental models and constrained particle systems. Key Words: particle systems, developmental models, data amplification, constraints, texture mapping, bump mapping, displacement mapping 1 Introduction For several years computer graphics researchers and practitioners have been grappling with the problem of creating and displaying surfaces having an organic appearance. Texture maps, bump maps, and related methods often attain the appearanc...

We suggest an approach for correcting several types of perceived geometric distortions in computer-generated and photographic images. The approach is based on a mathematical formalization of desirable properties of pictures. \n \nFrom a small set of simple assumptions we obtain perceptually preferable viewing transformations and show that these transformations can be decomposed into a perspective or parallel projection \nfollowed by a planar transformation. The decomposition is easily implemented and provides a convenient framework for further analysis of the image mapping. \n \nWe prove that two perceptually important properties are incompatible and cannot be satisfied simultaneously. It is impossible to construct a viewing transformation such that the images of all lines are straight and the images of all spheres are exact circles. Perceptually preferable tradeoffs between these two types of distortions \ncan depend on the content of the picture. We construct parametric families of transformations with parameters representing the relative importance of the perceptual characteristics. By adjusting the \nsettings of the parameters we can minimize the overall distortion of the picture. \n \nIt turns out that a simple family of transformations produces results that are sufficiently close to optimal. We implement the proposed transformations and apply them to computer-generated and photographic perspective projection images. Our transformations can considerably reduce distortion in wide-angle motion pictures \nand computer-generated animations.

Here, the authors combine a pure phase-encoded magnetic resonance imaging (MRI) method with a new tissue-classification technique to make geometric models of a human tooth. They demonstrate the feasibility of three-dimensional imaging of solids using a conventional 11.7-T NMR spectrometer. In solid-state imaging, confounding line-broadening effects are typically eliminated using coherent averaging methods. Instead, the authors circumvent them by detecting the proton signal at a fixed phase-encode time following the radio-frequency excitation. By a judicious choice of the phase-encode time in the MRI protocol, the authors differentiate enamel and dentine sufficiently to successfully apply a new classification algorithm. This tissue-classification algorithm identifies the distribution of different material types, such as enamel and dentine, in volumetric data. In this algorithm, the authors treat a voxel as a volume, not as a single point, and assume that each voxel may contain more than one material. They use the distribution of MR image intensities within each voxel-sized volume to estimate the relative proportion of each material using a probabilistic approach. This combined approach, involving MRI and data classification, is directly applicable to bone imaging and hard-tissue contrast-based modeling of biological solids.

We describe an algorithm for continuously producing a 3x3 rotation matrix from 9 changing input values that form an approximate rotation matrix, and we describe the implementation of that constraint in analog VLSI circuits. This constraint is useful when some source (e.g., sensors, a modeling system, other analog VLSI circuits), produces a potentially "imperfect" matrix, to be used as a rotation. The9 values are continuously adjustedover time to find the "nearest" true rotation matrix, based on a leastsquares metric. The constraint solution is implemented in analog VLSI circuitry; with appropriate design methodology [Kirk 93], adaptive analog VLSI is a fast, accurate, and low-power computational medium. The implementation is potentially interesting to the graphics community because there is an opportunity to apply adaptive analog VLSI to many other graphics problems. CR Categories and Subject Descriptors: C.1.2---[Processor Architectures]: Multiprocessors - parallel processors; C.1.3...

We present an efficient and robust algorithm for finding points of collision between time-dependent parametric and implicit surfaces. The algorithm detects simultaneous collisions at multiple points of contact. When the regions of contact form curves or surfaces, it returns a finite set of points uniformly distributed over each contact region. Collisions can be computed for a very general class of surfaces: those for which inclusion functions can be constructed. Included in this set are the familiar kinds of surfaces and time behaviors encountered in computer graphics. We use a new interval approach for constrained minimization to detect collisions, and a tangency condition to reduce the dimensionality of the search space. These approaches make interval methods practical for multi-point collisions between complex surfaces. An interval Newton method based on the solution of the interval linear equation is used to speed convergence to the collision time and location. This method is mor...

In this paper we present methods to smoothly interpolate orientations, given N rotational keyframes of an object along a trajectory. The methods allow the user to impose constraints on the rotational path, such as the angular velocity at the endpoints of the trajectory. We convert the rotations to quaternions, and then spline in that non-Euclidean space. Analogous to the mathematical foundations of flat-space spline curves, we minimize the net "tangential acceleration" of the quaternion path. We replace the flat-space quantities with curved-space quantities, and numerically solve the resulting equation with finite difference and optimization methods. 1 Introduction The problem of using spline curves to smoothly interpolate mathematical quantities in flat Euclidean spaces is a well-studied problem in computer graphics [bartels et al 87], [kochanek&bartels 84]. Many quantities important to computer graphics, however, such as rotations, lie in non-Euclidean spaces. In 1985, a method to...

Abstract In this paper, we present a general, systematic and consistent treatment of time and events for computer animation. We first formalize the concepts of events and create a time primitive called an event unit. We then present a succession of organization schemes to compose event units for generating complex motion sequences. We present a directed graph representation for the organization of time and events that suggests the form of an event‐based time programming language. Details of implementation of a general event simulation system are given. Our approach provides a clean partitioning for the problem of motion design, a hierarchical scheme to compose motion behaviors from time primitives and a programming model for organizing animation. Traditional methods of kinematic controls and key frame interpolation are special cases of our general scheme. In addition, our treatment of events can be combined with kinematics, dynamics or constraint‐based systems to generate powerful motion modeling systems.

Summary form only give. Teleological modeling, a developing approach for creating abstractions and mathematical representations of physically realistic time-dependent objects, is described. In this approach, geometric constraint-properties, mechanical properties of objects, the parameters representing an object, and the control of the object are incorporated into a single conceptual framework. A teleological model incorporates time-dependent goals of behavior of purpose as the primary abstraction and representation of what the object is. A teleological implementation takes a geometrically incomplete specification of the motion, position, and shape of an object, and produces a geometrically complete description of the object's shape and behavior as a function of time. Teleological modeling techniques may be suitable for consideration in computer vision algorithms by extending the current notions about how to make mathematical representations of objects. Teleological descriptions can produce compact representations for many of the physically derivable quantities controlling the shapes, combining-operations, and constraints which govern the formation and motion of objects.>

In this paper, we describe a new kind of constraint-based figure-maker for parametrically defined curves. Figures are made by defining objects and imposing constraints on their geometric behavior. We present a formulation of constraints as three ways in which two scalar real valued functions may be compared. This lets us specify equality, optimality and inequality constraints. We also introduce the mechanism of connectors. Connectors are used to connect various geometric entities through constraints. Behavior of connectors depends only on the local properties of curves. Connectors remove the need for an object to know about the kinds of constraints or the kinds of other objects it is connected to in order to act to satisfy a constraint. This makes for a very manageable and scalable program as the number of objects and constraints grows. An objects is modified in response to deviation of its state from the desired state specified through constraints. We have implemented some general low-level methods of specifying and satisfying constraints. These basic mechanisms can be used as an assembly language and combined hierarchically to define very general constraints.

We develop an algorithm to detect geometric collisions between pairs of time-dependent parametric surfaces. The algorithm works on surfaces that are continuous and have bounded derivatives, and includes objects that move or deform as a function of time. The algorithm numerically solves for the parametric values corresponding to coincident points and near-misses between the surfaces of two parametric functions.Upper bounds on the parametric derivatives make it possible to guarantee the successful detection of collisions and near-misses; we describe a method to find the derivative bounds for many surface types. To compute collisions between new types of surfaces, the mathematical collision analysis is needed only once per surface type, rather than analyzing for each pair of surface types.The algorithm is hierarchical, first finding potential collisions over large volumes, and then refining the solution to smaller volumes. The user may specify the desired accuracy of the solution. A C-code implementation is described, with results for several non-bicubic and bicubic time-dependent parametric functions. An animation of the collision computation demonstrates collisions between complex parametric functions.

In this paper, we present a robust and mathematically sound ray-intersection algorithm for implicit surfaces. The algorithm is guaranteed to numerically find the nearest intersection of the surface with a ray, and is guaranteed not to miss fine features of the surface. It does not require fine tuning or human choice of interactive parameters. Instead, it requires two upper bounds: "L" that limits the net rate of change of the implicit surface function f(x,y,z) and "G" that limits the rate of change of the gradient. We refer to an implicit surface with these rate limits as an "LG-implicit surface."Existing schemes to intersect a ray with an implicit surface have typically been guaranteed to work only for a limited set of implicit functions, such as quadric surfaces or polynomials, or else have been ad-hoc and have not been guaranteed to work. Our technique significantly extends the ability to intersect rays with implicit surfaces in a guaranteed fashion.

We present "dynamic constraints," a physically-based technique for constraint-based control of computer graphics models. Using dynamic constraints, we build objects by specifying geometric constraints; the models assemble themselves as the elements move to satisfy the constraints. The individual elements are rigid bodies which act in accordance with the rules of physics, and can thus exhibit physically realistic behavior. To implement the constraints, a set of "constraint forces" is found, which causes the bodies to act in accordance with the constraints; finding these "constraint forces" is an inverse dynamics problem.

Simulating flexible models can create aesthetic motion for computer animation. Animators can control these motions through the use of constraints on the physical behavior of the models. This paper shows how to use mathematical constraint methods based on physics and on optimization theory to create controlled, realistic animation of physically-based flexible models. Two types of constraints are presented in this paper: reaction constraints (RCs) and augrmented Lagrangian constraints (ALCs). RCs allow the fast computation of collisions of flexible models with polygonal models. In addition, RCs allow flexible models to be pushed and pulled under the control of an animator. ALCs create animation effects such as volume-preserving squashing and the molding of taffy-like substances. ALCs are compatible with RCs. In this paper, we describe how to apply these constraint methods to a flexible model that uses finite elements.

A quadtree algorithm is developed to triangulate deformed, intersecting parametric surfaces. The biggest problem with adaptive sampling is to guarantee that the triangulation is accurate within a given tolerance. A new method guarantees the accuracy of the triangulation, given a "Lipschitz" condition on the surface definition. The method constructs a hierarchical set of bounding volumes for the surface, useful for ray tracing and solid modeling operations. The task of adaptively sampling a surface is broken into two parts: a subdivision mechanism for recursively subdividing a surface, and a set of subdivision criteria for controlling the subdivision process.An adaptive sampling technique is said to be robust if it accurately represents the surface being sampled. A new type of quadtree, called a restricted quadtree, is more robust than the traditional unrestricted quadtree at adaptive sampling of parametric surfaces. Each sub-region in the quadtree is half the width of the previous region. The restricted quadtree requires that adjacent regions be the same width within a factor of two, while the traditional quadtree makes no restriction on neighbor width. Restricted surface quadtrees are effective at recursively sampling a parametric surface. Quadtree samples are concentrated in regions of high curvature, and along intersection boundaries, using several subdivision criteria. Silhouette subdivision improves the accuracy of the silhouette boundary when a viewing transformation is available at sampling time. The adaptive sampling method is more robust than uniform sampling, and can be more efficient at rendering deformed, intersecting parametric surfaces.

An approach to ray tracing complex models containing mathematically defined surfaces is presented. Parametric and implicit surfaces, and boolean combinations of these, are first tessellated into triangles. The resulting triangles from many such surfaces are organized in a hierachy of lists and 3D grids, allowing efficient calculation of ray/model intersections.The technique has been used to ray trace models containing billions of traiangles and surfaces never before ray traced. The organizing scheme developed is also independently useful for efficiently ray tracing any complex model, whether or not it contains surface tessellations.

The theory of elasticity describes deformable materials such as rubber, cloth, paper, and flexible metals. We employ elasticity theory to construct differential equations that model the behavior of non-rigid curves, surfaces, and solids as a function of time. Elastically deformable models are active: they respond in a natural way to applied forces, constraints, ambient media, and impenetrable obstacles. The models are fundamentally dynamic and realistic animation is created by numerically solving their underlying differential equations. Thus, the description of shape and the description of motion are unified.

A simple but general approach to imposing and solving geometric constraints on parameterized models is introduced, applicable to animation as well as model construction. Constraints are expressed as energy functions, and the energy gradient followed through the model's parameter space. Intuitively, energy constraints behave like forces that pull and parametrically deform the parts of the model into place. A wide variety of geometric constraints are amenable to this formulation, and may be used to influence arbitrary model parameters. A catalogue of basic constraints is presented, and results are shown. Keywords --- Constraints, Modeling, Animation 1 Introduction A widely-used approach to modeling is to combine geometric primitives---such as cylinders, blocks, and bicubic patches---with a variety of operators---such as translations, rotations, booleans, and deformations--- to form a model hierarchy. The task of constructing a model within this framework has two parts: building the hie...

New hierarchical solid modeling operations are developed, which simulate twisting, bending, tapering, or similar transformations of geometric objects. The chief result is that the normal vector of an arbitrarily deformed smooth surface can be calculated directly from the surface normal vector of the undeformed surface and a transformation matrix. Deformations are easily combined in a hierarchical structure, creating complex objects from simpler ones. The position vectors and normal vectors in the simpler objects are used to calculate the position and normal vectors in the more complex forms; each level in the deformation hierarchy requires an additional matrix multiply for the normal vector calculation. Deformations are important and highly intuitive operations which ease the control and rendering of large families of three-dimensional geometric shapes.