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.
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
Construction of a C1 Interpolating Subdivision Scheme for Arbitrary Meshes
Theoretic Analysis of Ck-Smoothness of Subdivision on Arbitrary Meshes
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.
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.
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.
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.
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.
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.
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]
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''.
Preliminary results from pilot usability studies indicate that manipulating projections is more effective than techniques that require the user to intersect objects in 3D.
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.
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.)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.
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.
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.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. 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.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 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.
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.
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].