Abstract We present a sub-linear algorithm to compute the set of back-facing polygons in a polyhedral model. The algorithm partitions the model into hierarchical clusters based on the orientations and positions of the polygons. As a pre-processing step, the algorithm constructs spatial decompositions with respect to each cluster. For a sequence of back-face computations, the algorithm exploits the coherence in view-point movement to efficiently determine whether it is in front of or behind a cluster. Due to coherence, the algorithm's expected running time is linear in the number of clusters on average. We have applied this algorithm to speed up the rendering of polyhedral models. On average, we are able to cull about 40% of the polygons. The algorithm accounts for 5% of the total CPU time per frame on an SGI Onyx. The overall frame rate is improved by 40–75% as compared to the standard back-face culling implemented in hardware. We also present an extension of our back-face computation algorithm to determine silhouettes of polygonal models. Our technique finds true perspective silhouettes by collecting edges at the common boundaries of back-facing and front-facing clusters.

No abstract available.

Accurate registration between real and virtual objects is crucial for augmented reality applications.Existing tracking methods are individually inadequate: magnetic trackers are inaccurate, mechanical trackers are cumbersome, and vision-based trackers are computationally problematic.We present a hybrid tracking method that combines the accuracy of vision-based tracking with the robustness of magnetic tracking without compromising real-time performance or usability.We demonstrate excellent registration in three sample applications.

We present a real-time stereoscopic video-see-through augmented reality (AR) system applied to the medical procedure known as ultrasound-guided needle biopsy of the breast.The AR system was used by a physician during procedures on breast models and during non-invasive examinations of human subjects.The system merges rendered live ultrasound data and geometric elements with stereo images of the patient acquired through head-mounted video cameras and presents these merged images to the physician in a head-mounted display.The physician sees a volume visualization of the ultrasound data directly under the ultrasound probe, properly registered within the patient and with the biopsy needle.Using this system, a physician successfully guided a needle into an artificial tumor within a training phantom of a human breast.We discuss the construction of the AR system and the issues and decisions which led to the system architecture and the design of the video see-through head-mounted display.We designed methods to properly resolve occlusion of the real and synthetic image elements.We developed techniques for realtime volume visualization of time-and position-varying ultrasound data.We devised a hybrid tracking system which achieves improved registration of synthetic and real imagery and we improved on previous techniques for calibration of a magnetic tracker.

We present a method for producing real-time volume visualizations of continuously captured, arbitrarily-oriented 2D arrays (slices) of data. Our system constructs a 3D representation on-the-fly from incoming 2D ultrasound slices by modeling and rendering the slices as planar polygons with translucent surface textures. We use binary space partition (BSP) tree data structures to provide non-intersecting, visibility-ordered primitives for accurate opacity accumulation images. New in our system is a method of using parallel, time-shifted BSP trees to efficiently manage the continuously captured ultrasound data and to decrease the variability in image generation time between output frames. This technique is employed in a functioning real-time augmented reality system that a physician has used to examine human patients prior to breast biopsy procedures. We expect the technique can be used for real-time visualization of any 2D data being collected from a tracked sensor moving along an arbitrary path.