1. Research Accomplishments

The primary goal of our Center is to build a stronger scientific foundation for computer graphics and scientific visualization and to help create the basic framework for future interactive graphical environments. Although progress has been gratifying in all aspects of computer graphics, much remains to be done. As we move to the next generation of computing systems, we continue to need to:

improve computational speeds for display

incorporate physical behavior into our models

extend our model definitions to incorporate manufacturing processes

move beyond the current generation of WIMP (windows, icons, menus, and pointing) user interfaces into post-WIMP user interfaces

scale our systems to handle more complex environments

reduce design cycle times, and

store, manage, access, and transmit larger amounts of data.

Finally, to help our field move from a craft to an engineering discipline based on a solid scientific foundation, we must guarantee the validity and accuracy of our simulations according to each application's needs, particularly in medical, scientific, and engineering areas.

To achieve these goals, our comprehensive strategic plan remains focused on four core areas of computer graphics: modeling, rendering, user interfaces and high-performance architectures. We have made significant progress in each of these domains in the past year. Two driving applications have helped direct these areas: scientific visualization and telecollaboration in virtual environments. The Center's research thus expands applications' capabilities while being focused in useful directions by application needs.

The principal characteristic of our research is improvement in the accuracy and fidelity of models used in computer graphics. This goal requires generality in our representations and simulations. As contrasted with the previous two decades of computer graphics research, we now stress experimental validation rather than simply ``looking good.'' We have built test environments and models and are comparing simulations to measured physical behavior in order to determine the accuracy of current approaches. This traditional scientific strategy of validating hypotheses with experiments is necessary to establish the fundamental bases for future improvements in computer graphics technology. But this strategy is relatively new in computer graphics, and represents a significant shift in methodology.

A second characteristic is our focus on efficiency. The field is moving inexorably towards more complex environments and their increasing demands for interactivity and time-critical computing, especially for virtual environments, in which significant lag can cause motion sickness. Time-critical computing (TCC) is the idea that an approximate result delivered on time is better that a fully accurate result too late. Procedures for improving computational speeds and computing within a known length of time depend on predictability and on the determination of error bounds. Thus, the goals of accuracy and computational efficiency are intimately related, indeed inseparable. The drive for efficiency leads to both a better scientific foundation and a stronger framework for future applications.

A third characteristic is our focus on strategic research in support of applications. The Center seeks to provide high-fidelity, high-efficiency techniques for use in applications of the next ten years. For example, the area of virtual environments has driven our research on trackers, but much of this work has been of a fundamental nature, exploring prediction techniques to prevent lag that apply to the entire graphics system. By setting our research in the context of applications, we help address the Center's goal of providing a framework for the future.

Finally, while it is helpful to organize the research of the Center by dividing it into categories, a great deal of overlap and synergy exists among the various research areas. For example, user interface technology begins to affect modeling technology when scientists developing new modeling methods look at techniques with more user-oriented parameters. Most of the high-performance architecture projects are driven by needs in scientific visualization. As discussed below, our Center-wide focus on telecollaboration is proving to be a fertile ground for intersite work.

1.1 Modeling

A fundamental goal in computer graphics and visualization is the development of adequate models to represent the complex objects that arise in mechanical design and scientific computation. Another fundamental goal is the development of methods for constructing and working with the complex behaviors necessary to simulate natural motion and growth, mechanical parts interaction and, in general, the physics of the everyday world. Today there is an even greater need than ever before to represent and control complex constrained systems of rigid, flexible and irregularly shaped objects. Unfortunately, complex model generation activity is still a major bottleneck.

1.1.1 New Design Representations

Torn B-Splines
Design and modeling are too complex ever to be performed with a single form of representation. NURBS have become an increasingly common and undeniably powerful means of expression, in part because interaction operators can be easily designed to modify the parametric tensor product (the unique association of coefficients and geometry). But the ``tensor product'' formulation is also a drawback. While this representation lends form and structure and makes computation and analysis feasible, it also restricts the regions over which the ``closed'' operators can be defined. Boolean operators (intersection, union) that lead to ``trimmed'' surface models are usually the last operation performed in creating a model. A spline model with Boolean operations is no longer subject to warping or physically based operations, since those operations have been performed only on complete spline surface models or on polygon-based models.

We have created the torn B-spline surface representation as an approach to designing with partial C-1 and C0 non-isoparametric feature curves in sculptured surfaces. We call C-1 feature curves ``tears'' and C0 curves ``creases.'' We are also developing techniques for manipulating and editing the smooth regions, tears, and creases in a homogeneous way. Finally, to make this representation useful, we must extend the results to complex models consisting of many, possibly trimmed, surfaces.

In 1996, we increased the complexity of torn surfaces to handle multiple intersecting curves, and integrated torn and trimmed surfaces into the same framework. We also demonstrated its use with new modeling operators and on applications such as mathematical data fitting, geometrical mechanical modeling, modeling manufacturing processes such as stamping, and topographical modeling.

Tensor-Product Nonrectangular G1 Surface Fitting
DeRose showed the constraint equations applicable when two Bezier patches meet with G1 continuity. However, in the past these equations have either been used to analyze whether two already existing patches meet with G1 continuity or in the cases where the patch boundary on one side was fixed and the other had to be determined, with the constraint that it meet with G1 continuity, thus reducing the problem to a linear constraint problem. We have generalized these constraints to the case of arbitrary tensor product surfaces meeting along a seam, using interior interpolation constraints and optimizing using surface curvature as a measure [SAND96]. This nonlinear constraint problem, which proved quite challenging, was used in the visualization research application that recovered and modeled vascular structures from MRA data (Section 1.5.3 below).

Construction of a C1 Interpolating Subdivision Scheme for Arbitrary Meshes
High-quality, multi-resolution surface construction is essential for time-critical level-of-detail rendering in VR and progressive image refinement on the WWW, as well as in desktop environments. Subdivision provides a powerful paradigm for the generation of surfaces of arbitrary topology. Given an initial triangular mesh, the goal is to produce a smooth and visually pleasing surface whose shape is controlled by the initial mesh. Of particular interest are interpolating schemes, since they match the original data exactly and are crucial for fast multiresolution and wavelet techniques. Dyn, Gregory, and Levin introduced the Butterfly scheme which is known to yield C1 surfaces in the topologically regular setting [ZORI96]. Unfortunately it exhibits various degeneracies in case of an irregular topology, leading to undesirable artifacts. We have examined these failures and derived an improved scheme that retains the simplicity of the Butterfly scheme, is interpolating, and yields smoother surfaces.

Theoretic Analysis of Ck-Smoothness of Subdivision on Arbitrary Meshes
Stationary subdivision is an important tool for generating smooth free-form surfaces for computer-aided geometric design and computer graphics. One of the challenges in construction of subdivision schemes for arbitrary meshes is to guarantee that the limit surface has a smooth regular parameterization in a neighborhood of any point. We have created a general mathematical framework for the analysis of subdivision that can be used for the analysis of more general types of schemes.

1.1.2 Physically Based Modeling

Linear-Complexity Articulated-Body Models
Physically accurate modeling of complex behavior such as human movement remains an unsolved problem. Motion capture can provide a geometric description but is tedious, inflexible, and conceptually limited in scope. This work contributes to the larger goal of interactively specifying such behaviors by creating a much faster and general implementation of articulated-body simulation in a structured modeling context.

We have converted Featherstone-style articulated models into a mathematical formulation that will be suitable for future addition of dynamic constraints and will let us create new equations of motion and allow the automatic selection of the most appropriate connection type for a given set of modeling circumstances. Both dynamic constraints and the Featherstone generalized-coordinate methods of articulated bodies provide a mechanism for constraining the behavior of a mechanical system. Dynamic constraints are quite general and flexible, but are computationally very expensive. Solution of n-dimensional dynamic constraint equations can require O(n3) time. Articulated body approaches using generalized coordinates are much faster and require only linear, O(n), time to solve a system involving n unconstrained degrees of freedom, but have ``loop-free'' restrictions on the topology of interactions between constraints. Thus, the two methods solve similar types of problems, but with different limitations and computational complexities.

1.2 Rendering

All five Center sites are working on various aspects of rendering, both forward and inverse. These efforts are either coordinated through formal collaborative projects funded through the Director's Pool (such as the Brown, Caltech, and Cornell collaboration in Scientific and Mathematical Foundations for Inverting the Rendering Equation) or constitute important individual pieces of the Center's long-term research vision. Future plans include collaborative work between the Cornell and UNC Center sites and the University of Pennsylvania to consider forward and inverse rendering within a single rendering framework.

1.2.1 Realistic Rendering

One of the Center's long-term goals is to develop physically based lighting models and perceptually based rendering procedures to generate synthetic images that are visually and measurably indistinguishable from real-world images. As stated in our original proposal, this research should provide the fundamental basis for the next generation of computer graphics algorithms and hardware.

Our methodology is subdivided into three stages, the light reflection and emission stage, the light transport simulation, and the tone mapping or rendering stage (Figure 1). At all stages experimental comparisons are made to verify the simulations and determine the error bounds.

It is important to note that this research, originally initiated at Cornell, has now been extended to three center sites (Caltech, Cornell, and Utah) and is fundamental to the inverse rendering portion of our collaborative project, mentioned above.

The process starts with the physical definition of the light sources and the reflection/absorption characteristics of all surfaces in the simulated scene. Of course, all of the exact geometry must also be known. The light source descriptions include the spatial and spectral characteristics of each emitting source, including its geometry, goniometric diagram, and the spectral distribution of the illuminant on a wavelength basis.

A comprehensive model of how light scatters when it strikes a surface has been developed [HE91] [HE92] that includes surface and subsurface scattering and can be extended to polarized light. The resulting bidirectional reflectance distribution function (BRDF) is a function of the wavelength, surface roughness properties, and the incoming and outgoing directions and the BRDF correctly predicts the diffuse, directional diffuse, and specular components of the reflected light.

To validate the reflection model, we have created a Light Measurement Laboratory to measure the light source characteristics and provide experimental BRDFs in absolute and relative radiometric units. Through this simulation/measurement process we have been able to verify the model's accuracy. Accurately representing the complex reflection behavior requires many mathematical terms, as spherical harmonics, wavelets, or mathematical series. We are currently investigating a variety of compact and computationally efficient representational schemes. We can predict the maximum error bounds for each scheme or level of representation chosen.

All of the components of the light measurement laboratory are now in operation. We can measure directional-hemispherical diffuse reflectance and specular reflectance as a function of wavelength and incident angle, and the isotropic bidirectional reflectance functions over a range of incidence and reflection angles and over a range of wavelengths. We can also measure spectral radiance from a point source, the spectral radiance of a scene, and surface roughness parameters for physically based reflectance models [TORR95] [FOO95] [CHEN96]. The effects of polarized light are now included in our measurements.

Once the emission, geometry, and reflection functions are known, we can then simulate the light transport. The general equations have been well known, but until recently neither the processing power nor an accurate reflection model was available to perform accurate simulations. The transport intensity equations [KAJI86] are usually used in the computer graphics community, but our theoretical investigations indicate that a radiance approach is more appropriate for two reasons: the radiance is invariant along straight-line propagation paths and the surface reflection operators can be separated from the geometric operators [ARVO96].

In real scenes, all surfaces have the capability for interacting with one another. Thus, solving the equations for the incident light distribution on each surface of a complex environment is very computationally expensive. For these reasons, most algorithms make many simplifying assumptions, yet still produce images of startling quality and realism. The two most common methods used are ray-tracing [WHIT79] and radiosity [GORA84]. However, neither of these commonly used algorithms are sufficiently exact, each neglecting various and significant mechanisms of light transport, although both methods produce photorealistic images. The more exact solutions can be obtained by finite-element techniques (radiosity), but since the simulations are really boundary-element problems with far-field interactions and fine meshes are required for high visual resolution, the resulting matrices are both large and dense. We have built on our earlier light-propagation models and implementations to develop analyses of bounds and complexity. Methods have been presented for determining bounds and estimates of local and total errors in radiosity solutions [LISC94]. We have also produced a framework for error analysis in global illumination algorithms, covering the three sources of errors (inaccurate boundary data, discretization, and computation) and describing how to bound the worst-case error from each source [ARVO94b].

We are now using statistical techniques (Monte Carlo) to obtain our solutions [WALT96]. The algorithms are quite simple and easily parallelized, but require the ``shooting'' of millions of photons to obtain satisfactory results with known error bounds. Once our simulations are calculated, a complete view-dependent description of the radiance of all surfaces is available. Note that at this stage we have not yet created a computer graphics image, but only computed the radiometry of the scene.

To validate the simulation of the light transport, we create an image plane and determine the radiant energy reaching this plane. Assuming we have accurately built and measured a physical test environment, we can then experimentally measure and compare the results of the simulation using a carefully calibrated, high-resolution, liquid-cooled CCD camera with the same image plane. As shown in Figure 1, this simulation/measurement paradigm allows us not only to tune the global illumination transport algorithm but also to provide feedback on the accuracy required for representing the light reflection model from the first phase.

This ability to measure physical environments radiometrically greatly improves the Center's capacity to carry out controlled experiments and to compare simulated efforts with the real-world environments. We have made descriptions of our ``Cornell Box'' experiments available on the Web. More reference solutions will be made available and should enable the entire graphics community to test rendering algorithms.

It should be emphasized that the first two phases of this process represent the physical simulation only, the comparisons are radiometric and not yet based on the visual comparison of two images. Producing an image implies moving to the perceptual domain. Global illumination algorithms accurately simulate scene luminances, but do not specify how to display them for realistic visual appearance. Display and printing devices are limited in dynamic range and color gamut, whereas simulations can be unbounded. Ambient lighting conditions significantly affect human perception of a scene. It is necessary to develop perceptually correct mappings from scene luminances to display luminances so that all important aspects of visual appearances are maintained. If possible, the results in the perceptual domain should also be predictive. We have just begun work in this area, initially with some simplified models of glare and adaptation [SPEN95] [FERW96].

1.2.2 Non-Realistic Rendering

Non-realistic rendering is essential in applications that deal with approximate models, where it is important not to distract the viewer with a false impression of exactness. Interest has recently been growing in alternative rendering techniques for illustration as well as for purely aesthetic reasons [SAIT90], [WINK94], [MEIE96]. In applications such as the Sketch system (discussed in Section A7 below), little detailed information is typically specified. Therefore, it is important to render these models and accentuate the overall geometry without drawing attention to missing detailed information inappropriate at the beginning stages of a design. An aesthetically pleasing, nonrealistic approach resembling pencil sketching is used in Sketch to visualize the direction in which a design is heading. Perhaps most importantly, Sketch is the only system we know that provides such nonrealistic rendering at interactive rates.

1.2.3 Image-Based Rendering

Image-based rendering uses a series of 2D images to create a 3D viewing experience, without using intermediary 3D representations. This approach to image creation is vital for building virtual environments in the Center's telecollaboration project and has applications in many areas of graphics and a number of industries, including remote medical consultation. The Center is pursuing two main methods of image-based rendering. The first necessitates acquiring images of an object from many different viewpoints and does not rely on any geometric or depth information to display a scene; the second does incorporate geometric or depth information about the object or the scene. While the first approach allows convincing photorealistic displays, the latter permits rendering of arbitrary objects or scenes from arbitrary viewpoints.

The Center's work in this area includes collaboration with Ruzena Bajcsy's computer vision group at the University of Pennsylvania.

Image-Based Rendering Without Depth Data
We gathered large data sets of images without any geometry information and displayed the images as texture maps on a single flat polygon in the user's view. The polygon swapped texture maps to use the image closest to the user's current viewpoint. In addition, the polygon moved with the user's viewpoint so as to stay nearly perpendicular to the viewer at all times. This created an impression of a three-dimensional object that could be viewed from any direction, even though only a single flat polygon was displayed. Note that the view of the object is correct only when the viewpoint of a user exactly matches the viewpoint from which the image was acquired. Thus, to ensure a convincing display, a large number of images must be acquired and the storage for so many images can be prohibitive.

In one popular implementation of image-based rendering, the source images are stitched together into complete panoramic image ``cylinders''. A user who is positioned (in software) inside one of these cylinders can then look outward to see the entire 360-degree panorama. As a step toward streamlining image acquisition and image-based rendering for this approach, we are working on a Java-based 2D-photo-to-cylinder mapping applet. As part of this development we hope to make the application available on the World Wide Web so that users can create their own image cylinders.

Image-Based Rendering With Depth Data
With Ruzena Bajcsy we have been moving forward in our efforts to facilitate scene reconstruction via remotely acquired images and depth maps. In an early experiment, we obtained a data set from Bajczy's group that included grayscale images and range data for a person's head, taken from a limited number of viewpoints. We processed the data for use with the Pixel-Planes 5 graphics supercomputer, merged the head with a synthetic model of an actual meeting room at UNC, and displayed a ``virtual conference'' in a head-mounted display. In a later experiment, we combined photographic images and range data for another real object, a small doll, but this time from 18 different viewpoints (all around the doll). We overlaid and displayed the views, again with the Pixel-Planes computer. In the final system a viewer can walk all the way around the doll because the depth has been reconstructed into a full 360-degree display. The results allowed parallax when the viewer moved and, although blank spaces were left where depth could not be determined, the user could see the full three-dimensional shape of the doll and interact with it (move it around).

1.2.4 Inverse Rendering

The challenge of inverse rendering is to extract geometry and other information from an image or series of images, based on the 2D information and other information known about the scene. A three-way collaboration is underway among the Brown, Caltech, and Cornell sites in a Director's Pool Project entitled ``Scientific and Mathematical Foundations for Inverting the Rendering Equation.'' Future plans includes a collaboration between Cornell, UNC, and the University of Pennsylvania.

Scientific and Mathematical Foundations for Inverting the Rendering Equation (Brown, Caltech, Cornell)
The purpose of this project is to explore methods by which information can be extracted from images and scene constraints for the purpose of creating new images. Both vision-based and image-based methods are being explored, which involve inversion and interpolation respectively. An important objective of this project is to discern connections between these approaches and to establish a theoretical basis for such methods. As part of this effort we are creating a better mathematical foundation for the process of radiative transfer, which has already provided some new insights into both direct and inverse problems. We have shown that some of the properties of light transport that pose challenges for global illumination are actually beneficial to inversion. For instance, this is true of interreflection which occurs near surface concavities, a fact that can be best demonstrated using analysis first presented in the context of global illumination [ARVO94a] [ARVO95d].

1.3 Interaction

Without continuously improved interaction methods for 3D graphics, many breakthroughs in key areas such as modeling, rendering, and performance will not be fully utilized. The power of next generation graphics must be made available not only to specialists in the field but to all computer users, from those in science and industry to educators, students, and home users. In particular, 3D user interface elements or widgets may make 3D graphics as integral to daily computing as the 2D graphical user interface did for 2D graphics. Three of the Center sites (Brown, Caltech, and Utah) are working on aspects of interaction that include not only ways to access and manipulate underlying model representations (Brown) but methods for working through conceptual problems in both 3D design and abstract domains such as mathematics (Brown and a Brown-Caltech collaboration). Interaction is also crucial in scientific visualization for taking advantage of ever-improving hardware performance that lets researchers view large datasets in real time.

1.3.1 Interaction for Modeling and Design

Although state-of-the-art interfaces for creating 3D models are powerful enough to create realistic effects for movies and specifications for complex engineering projects such as the Boeing 777 aircraft, they are still extraordinarily difficult to use and thus rarely used in exploratory ways. Mechanical designers still brainstorm on paper, not online, and Hollywood special effects designers typically draw every character by hand and often make physical models too before starting to build 3D models and animations on the computer.

The Sketch System

The Sketch system was designed to test a new paradigm in 3D interaction: using the natural gestural drawing idioms developed by artists over hundreds of years as a method of building 3D forms. Sketch received a great deal of attention during its debut at SIGGRAPH'96 [ZELE96] from both the corporate and academic communities. With Sketch, users can create approximate models in a fraction of the time required in more conventional systems. In addition, the system is enjoyable to use, a difficult-to-quantify but ultimately important factor.

The Sketch system uses gestures in place of the traditional WIMP graphical user interface components such as windows, menus, icons, and toolbars. Gestures allow the user to directly specify an operation, an operand, and additional parameters in a single, seamless physical action. Unlike traditional WIMP interfaces for 3D modeling in which the user must perform indirect operations like searching through the interface to change modes, our gestural interface is transparent and therefore lets users remain focused on the 3D model at all times.

Our specific approach in Sketch synthesizes features of traditional primitives-based modeling with algorithms for reconstructing 3D models from line drawings. Thus, instead of trying to recognize an entire 3D scene from a line-drawing as Lamb, et al. have done, we recognize simple line drawing fragments as they are drawn and then instantiate individual primitives or perform simple editing operations. These drawing fragments (or gestures) are based on well known line drawing idioms such as shadows to indicate height and line intersections to indicate surface occlusion. In addition, Sketch leverages context-sensitive information to perform some operations automatically (such as grouping and Boolean geometric subtraction). Sketch also uses context-sensitive gestures to allow the user to pan, zoom, and rotate the camera using a single mouse button and no explicit mode switching.

Two-Handed Interfaces
Computer interfaces have traditionally been limited to keyboard and mouse-based solutions, despite the fact that people in the real world naturally work with two hands and in three-dimensions. In our Sketch system we are exploring interfaces for 3D modeling that allow simultaneous two-handed input to make possible a wider range of gestures and let users manipulate more properties of the model simultaneously. We have found many of these operations are simpler and more efficient since they correspond more closely to how people interact with objects in the real world. [ZELE97]

Improved Selection and Manipulation in Immersive VR
A fundamental concern in immersive VR is the difficulty of selecting and manipulating objects. Existing techniques make the user perform cumbersome intermediate actions such as navigating to distant objects or using imprecise pointing techniques ill-suited to either densely packed or small objects. To address this, we have developed a novel interaction style for immersive VR that we term ``projective manipulation''.

Projective manipulation extends established cursor-based desktop 3D interaction techniques to immersive VR. For example, to select a distant object, the user positions a finger in front of his or her eye so that the fingertip appears to be on top of the distant object (see Figure 2). Ignoring stereo information, the user's fingertip is tantamount to a 2D cursor in desktop interaction [FORS96]. However, since we track the user's finger in 3D space, we can seamlessly transition to a variety of 3D manipulation techniques. An example is bringing the hand close to the body to automatically drag a selected object to the user's position. Part of this work has been done in collaboration with the User Interface Group at the University of Virginia [PIER97].

Preliminary results from pilot usability studies indicate that manipulating projections is more effective than techniques that require the user to intersect objects in 3D.

Lego Toolkit
The Lego toolkit was designed to allow rapid prototyping and customization of input hardware using Lego parts and simple electronic sensors. This toolkit can be used, for example, to let a designer rapidly iterate through a wide range of designs for a given input device. The Toolkit demonstrates that it is technologically and economically feasible to create application-specific hardware input devices quickly [AYER96].

1.3.2 Interaction for Direct Manipulation of Formal Systems (The Smartboard Project) (Brown-Caltech)

The purpose of this project is to develop new techniques for computer-assisted exploration and instruction of formal methods in mathematics and computer science. Toward this end we are experimenting with new techniques for human-computer interaction that facilitate fluid, direct manipulation of abstract objects such as diagrams and mathematical symbols. Several projects are currently under way to incorporate techniques for hand-printed character recognition in a gesture-based symbol manipulation system. Initial attempts have demonstrated the need for multiple processes and probabilistic methods since traditional representations of mathematical expressions based on parse trees are too inflexible; for example, they do not allow for syntactically incorrect intermediate expressions, which can be extremely useful to a user. To guide our efforts, we have video-taped a number of people using traditional media to demonstrate mathematical manipulations in tensor calculus, predicate logic, and control theory. This has lead to a number of ideas for gestural and diagrammatic interaction which will be investigated further using mockups and prototypes.

1.4 Performance

Throughout 1996, the Center has focused on a broad range of research related to performance issues in telecollaboration and telepresence. This research has been driven by the real problem of collaborative design of mechanical parts and assemblies (see Section 1.6 below) as well as long-term challenges such as real-time interaction in large, fully immersive scenes that include object behaviors. The Center has achieved dramatic improvements in hardware systems to display immersive and augmented virtual environments and to track an immersed user. Software systems have been designed to intelligently provide level-of-detail rendering and collision detection for complex scenes. To further increase performance of immersive and desktop systems, the Center has developed a framework for time-critical computing that ensures constant frame rates, even for multiple users telecollaborating from different machines at different locations.

1.4.1 Image Display Technologies

Compact Video-Based See-Through Head-Mounted Display (HMD)
We have designed and developed a new compact video-based see-through HMD that gives the user unprecedented visual integration of images on the display surfaces and objects in the real world. The HMD design consists of two compact, unobtrusive, high-resolution display packages, each with custom optics and miniature cameras situated to record the exact view for its eye. Each display system can be manually adjusted for both inter-pupillary distance and convergence, and the system automatically maintains the calibration between each display/camera pair. The individual displays are quite unobtrusive, and the frame mullions are very thin. This small, virtually frameless design means that users perceive maximum continuity between their view of the displays and their view of the real world as seen past or around the displays. Another unique feature is a flip-up design that allows users to easily move the display up and out of their way. Finally, a small tracker (sensor) is attached to the displays to facilitate registration of synthetic and real-world images. (See Figure 3 (152k JPEG).)

The design and fabrication of the HMD was an ultra-fast-track collaborative effort aided by our televideo infrastructure: the optics and electronics were designed at UNC in the Microelectronic Systems Laboratory (MSL), the packaging system was designed and manufactured by the University of Utah using their Alpha_1 environment, and the final integration was done at UNC in the MSL.

We realized early on that the design of the new HMD could supply the driving design challenge for our prototype telecollaboration system. While the HMD was not directly designed using the prototype, it was discussed and reviewed using the system. Now that the collaborative environment is operational, we plan to use it more fully in the next HMD revision.

1.4.2 Tracking Technology

Virtual Environment Tracking System
We have almost finished a new wide area virtual environment tracking system that uses LEDs embedded in ceiling tiles and a ``HiBall'' golfball-size tracking sensor cluster. The system is nearly complete: we expect the electronics to be tested by December of 1996 and the system to be fully operational by June of 1997. The HiBall, which was designed at UNC and whose principal mechanical component was fabricated at Utah in the Alpha_1 environment, incorporates six optical sensors into one golf-ball-sized sensing unit. The sensors are used to observe ceiling-mounted light-emitting diodes so that the system can track the position and orientation of the HiBall. This ``inside-looking-out'' approach was used in the previous UNC optoelectronic tracking system, but the previous sensing unit spanned most of the user's head and weighed over twelve pounds. In contrast, the HiBall sensing unit is the size of a golfball and weighs an amazing five ounces. (See Figure 3.)

With this new hardware, we plan to use a new mathematical method for tracking position and orientation, a method we call single-constraint-at-a-time (SCAAT) tracking. SCAAT uses an extended Kalman filter in an unusual fashion, maintaining a least-squares estimate of a target's position and orientation using a sequence of single sensor measurements as opposed to groups of measurements. Even though single sensor measurements offer incomplete information, what they provide is enough to incrementally improve the previous estimate.

From extensive simulations, we believe we can track a user's position and orientation in this fashion, using a single constraint at a time. SCAAT offers several advantages: (1) significantly improved estimate rates and latencies; (2) improved accuracy; (3) a flexible framework for heterogeneous multi-sensor data fusion; and (4) a unique opportunity to perform simultaneous source and sensor autocalibration.

1.4.3 Software Architectures

Simplification Envelopes
Automatic simplification of polygonal models is currently an important problem for interactive 3D graphics applications. By generating several levels of detail of a model, each containing fewer polygons than the previous one, we can trade off high-quality images for interactive frame rates.

Simplification envelopes is a method for automatically generating such level-of-detail hierarchies. The user specifies a single error tolerance, the maximum surface deviation of the simplified model from the original model, and a new, simplified model is generated. The method hinges on the generation of two envelope surfaces that surround the original surface; the distance between the envelope surfaces and the original surface is always less than the user-specified tolerance. The output model is generated by ensuring successive modifications to the original model, always making sure that the resulting surface lies between the two envelope surfaces [COHE96].

Interactive and Exact Collision Detection for Virtual and Simulated Environments
A virtual environment should give the user a feeling of presence, and this includes making the images of both the user and the surrounding objects feel solid. A fast, interactive collision-detection algorithm is a fundamental component of a complex virtual environment.

We have designed fast algorithms and systems for collision detection based on incremental computation. These algorithms have been applied to large-scale interactive environments and simulations. At a fundamental level, the system's algorithm takes advantage of frame-to-frame coherence to determine efficiently when a pair of objects is colliding. Our algorithm has worked very well for complex scenes such as architecture walkthrough environments and simulations consisting of hundreds of moving objects. The algorithms make no assumption about the motions of the objects; that is, their motions are not assumed to be expressible as a closed-form function of time. This is important in many applications because it can be difficult to predict a user's motion in a virtual environment or completely express the dynamic constraints for an object in a complex simulation [GOTT96].

Time-Critical Computing Frameworks
Time-critical computing is a new approach to graphics programming that enables applications to run on systems with a wide range of graphics capabilities while still maintaining an interactive frame rate. This approach is critical to projects like telecollaboration that involve the interactive sharing of graphical data from a number of different machines. Time-critical algorithms automatically reduce presentation quality to maintain interactive performance of the application. In general, time-critical computing relies on degradable algorithms for behaviors and rendering to implement these tradeoffs, as well as on scheduling algorithms to dynamically decide which tradeoff is most appropriate and performance-prediction algorithms to estimate the performance of the selected trade-off. The Center has been researching all these problem classes during the past several years.

Most recently, the Center has constructed a general framework for time-critical computing to measure overhead of a time-critical system. Previous time-critical systems typically used exactly one scheduler, but our framework employs a hierarchy of multiple schedulers. At run time, a two-pass algorithm traverses the hierarchy to schedule and execute all tasks of a time-critical application. The resulting framework is general and allows an application designer to incorporate many different degradation algorithms, each using their own specialized performance prediction. If needed, the framework can be modular, letting the application designer construct and test parts of a time-critical application independently. Finally, it is also flexible, allowing the incorporation of arbitrary scheduling algorithms.

1.4.4 Hardware Architectures

Analog VLSI
We have designed and built instances of our next generation of analog VSLI chips for representing computer graphics surfaces using floating-gate technology. These chips are now in the testing phase; after testing, we will refine and augment our design.

1.5 Scientific Visualization

The term ``scientific visualization'' can be applied to much of the Center's research, from architectural modeling and rendering to scene acquisition techniques and new model representations that aid in time-critical interaction with data. Several specific projects are selected here because their visualization component is particularly pronounced. Three sites are involved in two-way collaborations.

1.5.1 Wavelet Methods for ECG/EEG Visualization and Computational Modeling (Caltech-Utah)

Fundamental problems in electrocardiology (ECG) and electroencephalography (EEG) can be characterized by an inverse problem [JOH92e] [JOH93] [JOH94]: given a subset of electrostatic voltages measured on the surface of the torso (scalp) and the geometry and conductivity properties within the body (head), calculate the electric current vectors and voltage fields within the heart. Mathematically, the generalized ECG and EEG problems can be stated as solving Poisson's equation of electrical conduction for the primary current sources or Laplace's equation for the voltage field on the surface of the heart.

The resulting problem is mathematically ill-posed, i.e., the solution does not depend continuously on the data, so that small errors in the measurement of voltages on the scalp can yield unbounded errors in the solution and, for the general treatment of a solution of Poisson's equation, the solution is non-unique.

This collaborative project explores the use of wavelet based techniques in ECG/EEG processing, visualization, and computational modeling. Wavelets possess a number of mathematical and computational properties that make them promising candidates for enabling significant progress. We are in the initial startup phase of this project; this mostly has focused on wavelet methods that feed into the mathematical approaches needed for the project.

1.5.2 Interaction With Complex Design Operators and Computational Steering (Brown-Utah)

Continuing research in computational steering led to use of ideas from Brown's 3D widgets in a three-dimensional widget suite at the University of Utah for scientific visualization, scientific computation, and animation. These fields are computationally intensive by nature and an efficient interface is critical to reduce unnecessary computation. The goal has been to increase interactivity. The widget suite is object-oriented, implemented on a hierarchical constraint layer, and easily extensible. The widgets are fast with simple and consistent designs/interaction methods and provide direct manipulation for 3D visualization/interaction to facilitate increased interactivity and more effective data exploration. The suite is being tested in applications in computational medicine on large, real data sets.

1.5.3 Smooth Non-Rectangular Shapes Using Tensor Product Surfaces.

Volume images of the vascular structures are not considered adequate models to analyze and test theories of turbulence and blood flow and to plan treatment. Instead, surface models must be recovered from multimodality data including MRA images. We have developed segmentation techniques to recover information on vessel radius and shape, and methods to create smooth models of the whole structure, including the bifurcation regions. This approach required the development and use of nonlinear constraints with spline surface models. In addition, we were able to maintain the G1 smoothness of the shape while deforming it to fit the particular patient data, showing stenoses and aneurysms. We then used polymer-layered prototyping to create a hollow thin-walled model through which we could pass fluid, and which has the potential to be used in validating theoretical models for blood-flow turbulence.

1.5.4 San Diego Collaboratory for Microscopic Digital Anatomy (CMDA)

The CMDA project is developing a collaborative computational environment to provide biological/medical researchers remote access to unique instrumentation for data acquisition and distributed facilities for data synthesis, visualization and analysis. The Cornell site is developing a suite of volume renderers for the project, including both isosurface and direct volume rendering techniques. Research areas include how accuracy can be quantified and how it is affected by the choice of reconstruction filters, as well as investigating rendering algorithms that balance accuracy and performance through progressive refinement.

The project continues the Cornell site's research on 3D medical visualization, and though it receives no Center funds, both the Center and the CMDA project benefit from each other's research.

1.6 Telecollaboration (a collaboration by all five Center sites)

The Center's telecollaboration project is an ambitious collaborative effort by all the Center sites and ties together two-way, three-way, and four-way collaborative efforts funded from the Director's Pool. The project also serves to test interactions between single-site research projects that support the Center's overall vision. This degree of research coordination would be impossible for the individual sites without the Center mode of funding. As a driving application, the telecollaboration effort requires fundamental, long-term research in all of the Center's core areas, modeling, rendering, interaction, and performance. The challenges include methods of scene construction and acquisition, reconstruction and display, and interaction techniques for virtual environments. Responses to these challenges have been discussed throughout the Research section.

The ultimate goal of the telecollaboration project is to create a virtual mechanical design environment in which computer technology mediates complex communications necessary among distant parties so well that the technology itself seems to dissolve, leaving the designers with a feeling of presence in a common work space.

Testing Real-World Problems
The Center has a history of collaborative work on difficult design problems, from a project for designing a bracket for an HMD several years ago, to the recent collaborative work on the HiBall tracker and this year's collaborative design effort between Utah and UNC on the mechanical and manufacturing aspects of UNC's next-generation HMD (see Section 1.4.1 above). The innovative properties of the new HMD raised concerns about optics, electronics, mechanical and manufacturing design, in addition to ergonomics; tackling this complex problem was one of the motivations for the telecollaboration project. Utah and UNC held design meetings over the televideo with a live model in Alpha_1 running in collaborative mode at both sites. Three-way meetings between the mechanical designer, optics designer, and manufacturing engineer led to optical, mechanical and manufacturing changes. Multiple-phase manufacturing requirements (using molds, wire EDM, sinking EDM, and milling) were considered in the light of multiple discipline design requirements. Size, weight, and tolerance requirements had a major impact. This design project has involved multiple alternatives, multiple phases, and multiple levels, from conceptual requirements through finished assembly of a distributed, collaborative design project. A preliminary version has been assembled and is operationally complete.

The Prototype Shared Virtual Environment
Extensive experience with the Center's unique televideo infrastructure has made plain to us a number of problems with current teleconferencing technology. One drawback of our current system is that all participants cannot be visible at the same time at a given site. Present day tools make it difficult to generate a feeling of a shared common space and pointing at physical objects under discussion is difficult or impossible from remote sites. Finally, today's tools do not let us easily share a view of virtual objects, such as a mechanical part under design. We are addressing all of these issues, placing all participants in a shared environment that is created with computer graphics and networking technology.

We have completed a prototype of a shared virtual environment that was demonstrated at the June 1996 site visit at UNC. This system used conventional equipment and methods to assess current off-the-shelf technologies such as commercial trackers and display devices. The system already provides features not available in most CSCW environments. For example, responsive 3D-modeled avatars and custom live video texture mapping enable a user's avatar to move and rotate when the viewpoint is changed. Any user can move the model under review and then deduce what the other users are seeing by observing the location of their avatars in the environment. This is a marked improvement over shared CAD viewers in which the current views of other users are not known.

In our test scenario, participants worked collaboratively with Alpha_1, the University of Utah's research CAD/CAM software, to make and visualize joint modifications to a real object under design. The prototype system's software is written in Open Inventor, which allows easy incorporation of packages written at different sites, such as Alpha_1 at Utah and the video texture mapping at Brown. For example, the Alpha_1 ``node'' written for Inventor allows Alpha_1 to be represented in Open Inventor data files, lets Open Inventor automatically load the Alpha_1 libraries, and allows Open Inventor to control placement, visibility, etc. of the node. The system allowed users at various sites to view a virtual environment via the desktop or using immersive technology (in this example we used a HMD at UNC and a BOOM at Brown). We can also now can use UNC's unique Pixel-Planes facility directly from Utah's Alpha_1 design system.

The Center's research in image-based rendering (see Section 1.2.3 above) is important to the telecollaboration project, for instance using images and image-warping based on geometrical data to share real environment information between sites in a compelling fashion. Both image-based rendering and the more fundamental inverse problem (see Section 1.2.4 above) are necessary to fulfill the long-term goal of creating a strong feeling of presence in an interactive, immersive virtual space.

Mitigating Network Lag
The prototype also includes some ways of mitigating network lag. Rather than presenting a user interface with a ``lock,'' as in chalk-passing protocols, we provide a seamless experience: when a participant wishes to modify an object, she simply does so, grabbing it and making the changes as in the real world (rather than first needing to grab the ``chalk'' and then grab the object to be modified). We call this technique ``ghost locking'': the user manipulates a ghost of the object until the application learns if the ``chalk'' is available [CONN97].


Back to the Table of Contents
Forward to Research Plans