We present a framework that allows for localization based on very low resolution omnidirectional image data using regression techniques. Previous related methods are constrained to image data labeled with exact position information acquired in the training phase. We relax this constraint and propose to learn local heteroscedastic Gaussian processes by accumulating odometry data which can easily be acquired. The processes are used as a probabilistic map to predict recording positions of newly acquired images by a fusion of the uncertain training data. In contrast to many feature-based approaches, our framework does not rely on any explicit correspondences over images as well as over positions and only imposes very weak assumptions on the type and quality of the image representations.

We investigate the application of particle filters to estimate the orientation of a mobile agent based on an omnidirectional video stream. By applying spherical signal analysis to sequences of low resolution input images we perform a real-time estimation of the relative camera rotation. We use normalized cross-correlation computed with a fast frequency domain approach that yields unbiased estimates which can be further processed by a particle filter. We discuss the quaternion representation of the rotational state space and evaluate methods for meaningful averaging. A prototype system is presented and experiments with real image sequences show that robust estimation of the rotational motion is achievable even when the input images are corrupted, e.g. due to occlusions.

We present a probabilistic localization and orientation estimation method for mobile agents equipped with omnidirectional vision. In our appearance-based framework, a scene is learned in an offline step by modeling the variation of the image energy in the frequency domain via Gaussian process regression. The metric localization of novel views is then solved by maximizing the joint predictive probability of the Gaussian processes using a particle filter which allows to incorporate a motion model in the prediction step. Based on the position estimate, a synthetic view is generated and used as a reference for the orientation estimation which is also performed in the Fourier space. Using real as well as virtual data, we show that this framework allows for robust localization in 2D and 3D scenes based on very low resolution images and with competitive computational load.

We present a parallel conjugate gradient solver for the Poisson problem optimized for multi-GPU platforms. Our approach includes a novel heuristic Poisson preconditioner well suited for massively-parallel SIMD processing. Furthermore, we address the problem of limited transfer rates over typical data channels such as the PCI-express bus relative to the bandwidth requirements of powerful GPUs. Specifically, naive communication schemes can severely reduce the achievable speedup in such communication-intense algorithms. For this reason, we employ overlapping memory transfers to establish a high level of concurrency and to improve scalability. We have implemented our model on a high-performance workstation with multiple hardware accelerators. We discuss the mathematical principles, give implementation details, and present the performance and the scalability of the system.

Abstract We present a new hybrid CPU/GPU collision detection technique for rigid and deformable objects based on spatial subdivision. Our approach efficiently exploits the massive computational capabilities of modern CPUs and GPUs commonly found in off‐the‐shelf computer systems. The algorithm is specifically tailored to be highly scalable on both the CPU and the GPU sides. We can compute discrete and continuous external and self‐collisions of non‐penetrating rigid and deformable objects consisting of many tens of thousands of triangles in a few milliseconds on a modern PC. Our approach is orders of magnitude faster than earlier CPU‐based approaches and up to twice as fast as the most recent GPU‐based techniques.

Procedural methods for terrain synthesis are capable of creating realistic depictions of heightfield terrains with little user intervention. However, users often do wish to intervene in controlling the placement and shape of landforms, but without sacrificing realism. In this paper, we present a sketching interface to procedural terrain generation. This system enables users to draw the silhouette, spine and bounding curves of both extruding (hills and mountains) and embedding landforms (river courses and canyons).

Abstract We present Continuum‐based Strain Limiting (CSL) – a new method for limiting deformations in physically‐based cloth simulations. Despite recent developments for nearly inextensible materials, the efficient simulation of general biphasic textiles and their anisotropic behavior remains challenging. Many approaches use soft materials and enforce limits on edge elongations, leading to discretization‐dependent behavior. Moreover, they offer no explicit control over shearing and stretching unless specifically aligned meshes are used. Based on a continuum deformation measure, our method allows accurate control over all strain components using individual thresholds. We impose deformation limits element‐wise and cast the problem as a 6×6 system of linear equations. CSL can be combined with any cloth simulator and, as a velocity filter, integrates seamlessly into standard collision handling.

We present a new algorithm for scan registration of colored 3D point data which is an extension to the Normal Distributions Transform (NDT). The probabilistic approach of NDT is extended to a color-aware registration algorithm by modeling the point distributions as Gaussian mixture-models in color space. We discuss different point cloud registration techniques, as well as alternative variants of the proposed algorithm. Results showing improved robustness of the proposed method using real-world data acquired with a mobile robot and a time-of-flight camera are presented.

We present an alternative approach to standard geometric shape editing using physically-based simulation. With our technique, the user can deform complex objects in real-time. The basis of our method is formed by a fast and accurate finite element implementation of an elasto-plastic material model, specifically designed for interactive shape manipulation. Using quadratic shape functions, we reduce approximation errors inherent to methods based on linear finite elements. The physical simulation uses a volume mesh comprised of quadratic tetrahedra, which are constructed from a coarser approximation of the detailed surface. In order to guarantee stability and real-time frame rates during the simulation, we cast the elasto-plastic problem into a linear formulation. For this purpose, we present a corotational formulation for quadratic finite elements. We demonstrate the versatility of our approach in interactive manipulation sessions and show that our animation system can be coupled with further physics-based animations like, e.g. fluids and cloth, in a bi-directional way.

Abstract Common practice in brain research and brain surgery involves the multi‐modal acquisition of brain anatomy and brain activation data. These highly complex three‐dimensional data have to be displayed simultaneously in order to convey spatial relationships. Unique challenges in information and interaction design have to be solved in order to keep the visualization sufficiently complete and uncluttered at the same time. The visualization method presented in this paper addresses these issues by using a hybrid combination of polygonal rendering of brain structures and direct volume rendering of activation data. Advanced rendering techniques including illustrative display styles and ambient occlusion calculations enhance the clarity of the visual output. The presented rendering pipeline produces real‐time frame rates and offers a high degree of configurability. Newly designed interaction and measurement tools are provided, which enable the user to explore the data at large, but also to inspect specific features closely. We demonstrate the system in the context of a cognitive neurosciences dataset. An initial informal evaluation shows that our visualization method is deemed useful for clinical research.

Western societies are aging rapidly. An automated 24/7 surveillance to ensure safety of the elderly while respecting privacy becomes a major challenge. At the same time this is representative of novel and emerging video surveillance applications discovered lately besides the classic surveillance protection applications in airports, government buildings, and industrial plants. Three problems of current surveillance systems are identified. A distributed and automated smart camera based approach is proposed that addresses these problems. The proposed system's goal set is to analyze the real world and reflect all relevant—and only relevant—information live in an integrated virtual counterpart for visualization. It covers georeferenced person tracking and activity recognition (falling person detection). A prototype system installed in a home for assisted living has been running 24/7 for several months now and shows quite promising performance.

We introduce magnetic interaction for rigid body simulation. Our approach is based on an equivalent dipole method and as such it is discrete from the ground up. Our approach is symmetric as we base both field and force computations on dipole interactions. Enriching rigid body simulation with magnetism allows for many new and interesting possibilities in computer animation and special effects. Our method also allows the accurate computation of magnetic fields for arbitrarily shaped objects, which is especially interesting for pedagogy as it allows the user to visually discover properties of magnetism which would otherwise be difficult to grasp. We demonstrate our method on a variety of problems and our results reflect intuitive as well as surprising effects. Our method is fast and can be coupled with any rigid body solver to simulate dozens of magnetic objects at interactive rates.

For various 3D Animation processing, representing mesh geometry in local rather the world coordinate systems is very useful. One can investigate the representation of vertex locations relative to a local coordinate frame (LCF) in the compression of dynamic 3D meshes. Unlike the world coordinates, which scatter in a wide range and show non linear behavior of the vertices, the local coordinates exhibit a large clustering behavior of the vertex over time. This property is very useful for exploiting a large coherence over the vertex trajectory and between neighboring vertices. In this paper, we discuss the use of the LCF in mesh encoding and we introduce a new and simple predictive scheme for single-rate compression for animated meshes. Our geometry encoding strategy is based on a region growing encoding order and only the delta vectors between original and predicted locations are encoded in a local coordinate system, which splits into two tangential and one normal components. Our approach is simple, efficient and well suited for real time applications.

Future 3D television critically relies on mechanisms for automatically acquiring and visualizing high quality 3D content of both indoor and outdoor scenes. The envisioned goal is that a photo-realistic 3D real-time rendering from the actual and potentially arbitrary viewpoint of the beholder who is watching 3DTV becomes possible. Such scenes include movie sets in studios, e.g., for talk shows, TV series and blockbuster movies, but also outdoor scenes, e.g., buildings in a neighborhood for a car chase or cultural heritage sites for a documentary. The goal of 3D model acquisition is to provide the 3D background models where potential 3D actors can be embedded. We present both the 3D acquisition and semi-immersive 3D visualization to give an impression how a future 3D television system could be like.

Scan matching is a popular way of recovering a mobile robot's motion and constitutes the basis of many localization and mapping approaches. Consequently, a variety of scan matching algorithms have been proposed in the past. All these algorithms share one common attribute: They match pairs of scans to obtain spatial relations between two robot poses. In this paper we present a method for matching multiple scans simultaneously. We discuss the need for such a method and describe how the result of such a multi-scan matching can be incorporated into relation-based SLAM in the Lu and Milios style

In video see-through augmented reality (AR), virtual objects are overlaid over digital video images. One particular problem of this image mixing process is that the visual appearance of the computer graphics differs strongly from the real background image. The reason for this is that typical AR systems use fast but simple real-time rendering techniques for displaying virtual objects. In this paper, methods for reducing the impact of three effects which make virtual and real objects easily distinguishable are presented. The first effect is camera image noise, which is contained in the data delivered by the image sensor used for capturing the real scene. The second effect considered is edge aliasing, which makes distinguishing virtual objects from real objects simple. Finally, we consider motion blur, which is caused by the temporal integration of color intensities in the image sensor during fast movements of the camera or observed objects. In this paper, we present a system for generating a realistic simulation of image noise based on a new camera calibration step. Additionally, a rendering algorithm is introduced, which performs a smooth blending between the camera image and virtual objects at their boundary in order to reduce aliasing. Lastly, a rendering method is presented, which produces motion blur according to the current camera movement. The implementation of the new rendering techniques utilizes the programmability of modern graphics processing units (GPUs) and delivers real-time frame rates.

Abstract In this paper, we propose a novel surface reconstruction technique based on Bayesian statistics: The measurement process as well as prior assumptions on the measured objects are modeled as probability distributions and Bayes’ rule is used to infer a reconstruction of maximum probability. The key idea of this paper is to define both measurements and reconstructions as point clouds and describe all statistical assumptions in terms of this finite dimensional representation. This yields a discretization of the problem that can be solved using numerical optimization techniques. The resulting algorithm reconstructs both topology and geometry in form of a well‐sampled point cloud with noise removed. In a final step, this representation is then converted into a triangle mesh. The proposed approach is conceptually simple and easy to extend. We apply the approach to reconstruct piecewise‐smooth surfaces with sharp features and examine the performance of the algorithm on different synthetic and real‐world data sets. Categories and Subject Descriptors (according to ACM CCS): I.5.1 [Models]: Statistical; I.3.5 [Computer Graphics]: Curve, surface, solid and object representations

Abstract Image space occlusion culling is a powerful approach to reduce the rendering load of large polygonal models. However, occlusion culling is not for free; it trades overhead costs with the rendering costs of the possibly occluded geometry. Meanwhile, occlusion queries based on image space occlusion culling are supported on modern graphics hardware. However, a significant consumption of fillrate bandwidth and latency costs are associated with these queries. In this paper, we propose new techniques to reduce redundant occlusion queries. Our approach uses several "Occupancy Maps" to organize scene traversal. The respective information is accumulated efficiently by hardware‐supported asynchronous occlusion queries. To avoid redundant requests, we arrange these multiple occlusion queries according to the information of the Occupancy Maps. Our presented technique is conservative and benefits from a partial depth order of the geometry.

Ray casting, a real-life application for the visualization of 3D scientific and medical data, demands both high performance and high flexibility, and is likely to be used in future mobile devices, where low power is an important issue. In this paper, we show that implementing ray casting on coarse-grained, highly reconfigurable architectures satisfies these conflicting requirements much better than traditional architectures.

For a mobile robot it is a natural task to build a 3D model of its environment. Such a model is not only useful for planning robot actions but also to provide a remote human surveillant a realistic visualization of the robot’s state with respect to the environment. Acquiring 3D models of environments is also an important task on its own with many possible applications like creating virtual interactive walkthroughs or as basis for 3D-TV. In this paper we present our method to acquire a 3D model using a mobile robot that is equipped with a laser scanner and a panoramic camera. The method is based on calculating dense depth maps for panoramic images using pairs of panoramic images taken from different positions using stereo matching. Traditional 2D-SLAM using laser-scan-matching is used to determine the needed camera poses. To receive high-quality results we use a high-quality stereo matching algorithm – the graph cut method. We describe the necessary modifications to handle panoramic images and specialized post-processing methods.

Recently, we have proposed a novel approach to generating augmented video streams. The output images are a non-photorealistic reproduction of the augmented environment. Special stylization methods are applied to both the background camera image and the virtual objects. This way, the graphical foreground and the real background images are rendered in a similar style, so that they are less distinguishable from each other. Here, we present a new algorithm for the cartoon-like stylization of augmented reality images, which uses a novel post-processing filter for cartoon-like color segmentation and high-contrast silhouettes. In order to make a fast post-processing of rendered images possible, the programmability of modern graphics hardware is exploited. The system is capable of generating a stylized augmented video stream of high visual quality at real-time frame rates.

Indirect volume rendering is a widespread method for the display of volume datasets. It is based on the extraction of polygonal iso-surfaces from volumetric data, which are then rendered using conventional rasterization methods. Whereas this rendering approach is fast and relatively easy to implement, it cannot easily provide an understandable display of structures occluded by the directly visible iso-surface. Simple approaches like alpha-blending for transparency when drawing the iso-surface often generate a visually complex output, which is difficult to interpret. Moreover, such methods can significantly increase the computational complexity of the rendering process. In this paper, we therefore propose a new approach for the illustrative indirect rendering of volume data in real-time. This algorithm emphasizes the silhouette of objects represented by the iso-surface. Additionally, shading intensities on objects are reproduced with a monochrome hatching technique. Using a specially designed two-pass rendering process, structures behind the front layer of the iso-surface are automatically extracted with a depth peeling method. The shapes of these hidden structures are also displayed as silhouette outlines. As an additional option, the geometry of explicitly specified inner objects can be displayed with constant translucency. Although these inner objects always remain visible, a specific shading and depth attenuation method is used to convey the depth relationships. We describe the implementation of the algorithm, which exploits the programmability of state-of-the-art graphics processing units (GPUs). The algorithm described in this paper does not require any preprocessing of the input data or a manual definition of inner structures. Since the presented method works on iso-surfaces, which are stored as polygonal datasets, it can also be applied to other types of polygonal models.

The ultimate goal of augmented reality is to provide the user with a view of the surroundings enriched by virtual objects. Practically all augmented reality systems rely on standard real-time rendering methods for generating the images of virtual scene elements. Although such conventional computer graphics algorithms are fast, they often fail to produce sufficiently realistic renderings. The use of simple lighting and shading methods, as well as the lack of knowledge about actual lighting conditions in the real surroundings, cause virtual objects to appear artificial. In this paper, we propose an entirely novel approach for generating augmented reality images in video see-through systems. Our method is based on the idea of applying stylization techniques for reducing the visual realism of both the camera image and the virtual graphical objects. A special painterly image filter is applied to the camera video stream. The virtual scene elements are generated using a non-photorealistic rendering method. Since both the camera image and the virtual objects are stylized in a corresponding cartoon-like or sketch-like way, they appear very similar. As a result, the graphical objects seem to be an actual part of the real surroundings. We describe both the new painterly filter for the camera image and the non-photorealistic rendering method for virtual scene elements, which has been adapted for this purpose. Both are fast enough for generating augmented reality images in real-time and are highly customizable. The results obtained using our method, are very promising and show that it improves immersion in augmented reality.

The goal of augmented reality is to provide the user with a view of the surroundings enriched by virtual objects. Practically all augmented reality systems rely on standard real-time rendering methods for displaying graphical objects. Although such conventional computer graphics algorithms are fast, they often fail to produce sufficiently realistic renderings. Therefore, virtual models can easily be distinguished from the real environment. We have recently proposed a novel approach for generating augmented reality images [4]. Our method is based on the idea of applying stylization techniques for adapting the visual realism of both the camera image and the virtual graphical objects. Since both the camera image and the virtual objects are stylized in a corresponding way, they appear very similar. Here, we present a new method for the stylization of augmented reality images. This approach generates a painterly brush stroke rendering. The resulting stylized augmented reality video frames look similar to paintings created in the pointillism style. We describe the implementation of the camera image filter and the non-photorealistic rendererfor virtual objects. These components have been newly designed or adapted for this purpose. They are fast enough for generating augmented reality images in near real-time (more than 14 frames per second).

Abstract Interactive environments for dynamically deforming objects play an important role in surgery simulation and entertainment technology. These environments require fast deformable models and very efficient collision handling techniques. While collision detection for rigid bodies is well investigated, collision detection for deformable objects introduces additional challenging problems. This paper focuses on these aspects and summarizes recent research in the area of deformable collision detection. Various approaches based on bounding volume hierarchies, distance fields and spatial partitioning are discussed. In addition, image‐space techniques and stochastic methods are considered. Applications in cloth modeling and surgical simulation are presented.

The support of surgical interventions has long been in the focus of application-oriented augmented reality research. Modern methods of surgery, like minimally-invasive procedures, can benefit from the additional information visualization provided by augmented reality. The usability of medical augmented reality depends on a rendering scheme for virtual objects designed to generate easily and quickly understandable augmented views. One important factor for providing such an accessible reality augmentation is the correct handling of the occlusion of virtual objects by real scene elements. The usually large volumetric datasets used in medicine are ill-suited for use as phantom models for static occlusion handling. We present a simple and fast preprocessing pipeline for medical volume datasets which extracts their visual hull volume. The resulting, significantly simplified visual hull iso-surface is used for real-time static occlusion handling in our AR system, which is based on off-the-shelf medical equipment.

Point based rendering techniques have recently become a promising alternative for high quality rendering of complex scenes. In order to handle a high number of points, the current graphics cards structure has to be analyzed for efficient exploitation of the hardware resources available. In this context, the real time perspective projections become a challenge because of the reduced number of dividers available in the graphics cards and their recursive structure. In this paper, we present a point projection algorithm that avoids the division operations. The technique we propose is based on the identification of the candidate pixels on the screen, and the selection of the correct one through simple comparison operations. The simplicity of the algorithm we propose permits the utilization of different projection units operating in parallel. We also present a scheduling that permits the introduction and efficient exploitation of a pipelined system. The algorithm is regular, simple, and characterized by efficient data management so that the processing rate is directly associated with the number of projection units employed. As a result, real time performance for the projection operations, even for critical scenes, can be achieved.

Matching 2D range scans is a basic component of many localization and mapping algorithms. Most scan match algorithms require finding correspondences between the used features, i.e. points or lines. We propose an alternative representation for a range scan, the normal distributions transform. Similar to an occupancy grid, we subdivide the 2D plane into cells. To each cell, we assign a normal distribution, which locally models the probability of measuring a point. The result of the transform is a piecewise continuous and differentiable probability density, that can be used to match another scan using Newton's algorithm. Thereby, no explicit correspondences have to be established. We present the algorithm in detail and show the application to relative position tracking and simultaneous localization and map building (SLAM). First results on real data demonstrate, that the algorithm is capable to map unmodified indoor environments reliable and in real time, even without using odometry data.

We present an efficient model based on finite elements for viscoelastic, highly flexible surfaces. It is particularly designed for numerically stiff materials such as textiles because it yields linear equations in each time step and allows fast time stepping in an implicit integration method. This is achieved by reducing the nonlinear elasticity problem to a planar, linear one in each step. We apply this model to a garment simulation in which we assemble garments from CAD cloth patterns, seam these together, and animate the cloth in dynamic scenes with any chosen material properties. This results in a physically accurate but also fast simulation.

Segmentation of the tracheo-bronchial tree of the lungs is notoriously difficult. This is due to the fact that the small size of some of the anatomical structures is subject to partial volume effects. Furthermore, the limited intensity contrast between the participating materials (air, blood, and tissue) increases the segmentation of difficulties. In this paper, we propose a hybrid segmentation method which is based on a pipeline of three segmentation stages to extract the lower airways down to the seventh generation of the bronchi. User interaction is limited to the specification of a seed point inside the easily detectable trachea at the upper end of the lower airways. Similarly, the complementary vascular tree of the lungs can be segmented. Furthermore, we modified our virtual endoscopy system to visualize the vascular and airway system of the lungs along with other features, such as lung tumors.

Current cloth simulation systems have become powerful enough to be used interactively, and applications relevant to textile industries like virtually tailoring real garments seem to be possible in the near future. We show that interactive cloth simulation can be improved by virtual reality techniques. We present the Virtual Dressmaker, an application for interactive assembly and physically based interactive simulation of cloth. In particular, the system allows us to select and drag parts of the clothes during the simulation. The proposed application consists of a VR-interface client that provides nearly live-size stereo projection combined with 6DOF interaction and a server for physically based cloth simulation. In order to verify the usability of our approach, we elaborate on usability studies, which show that our application allows fast, easy, and precise interaction compared to interaction with a traditional 3D-desktop application based on 2D input devices.

We report on a user study, investigating the efficiency of user interaction in a Virtual Reality application compared to 3D desktop applications.The Virtual Dressmaker is a Virtual Reality application for virtual cloth design, assembly, and simulation that supports advanced 6DoF interaction techniques. We conjecture that these interaction techniques are more natural for the users and lead to faster and more precise results than common desktop applications.In our user study we investigate interaction tools for positioning garment patterns in VR and compare the results to interaction with common 3D desktop applications. We measure completion time and precision of the positioned patterns and evaluate the subjective impressions of the users.The results show that Virtual Environments, and the presented interaction tools in particular, provide a valuable method for cloth design and assembly. Moreover, certain features of current 3D desktop design tools can be exploited for further improvements of VR interaction.

Abstract We present a new algorithm to render caustics. The algorithm discretizes the specular surfaces into samplepoints. Each of the sample points is treated as a pinhole camera that projects an image of the incoming lightonto the diffuse receiver surfaces. Anti‐aliasing is performed by considering the local surface curvature at thesample points to filter the projected images. The algorithm can be implemented using programmable texturemapping hardware. It allows to render caustics in fully dynamic scenes in real‐time on current PC hardware. Categories and Subject Descriptors: I.3.3 [Computer Graphics]: Picture/Image Generation — Display Algorithms;I.3.7 [Computer Graphics]: Three‐Dimensional Graphics and Realism

Mass-spring and particle systems have been widely employed in computer graphics to model deformable objects because they allow fast numerical solutions. In this work, we establish a link between these discrete models and classical mathematical elasticity. It turns out that discrete systems can be derived from a continuum model by a finite difference formulation and approximate classical continuum models unless the deformations are large. In this work, we present the derivation of a particle system from a continuum model, compare it to the models of classical elasticity theory, and assess its accuracy. In this way, we gain insight into the way discrete systems work and we are able to specify the correct scaling when the discretization is changed. Physical material parameters that describe materials in continuum mechanics are also used in the derived particle system.

We present a new algorithm for rendering very large volume data sets at interactive frame rates on standard PC hardware. The algorithm accepts scalar data sampled on a regular grid as input. The input data is converted into a compressed hierarchical wavelet representation in a preprocessing step. During rendering, the wavelet representation is decompressed on-the-fly and rendered using hardware texture mapping. The level of detail used for rendering is adapted to the local frequency spectrum of the data and its position relative to the viewer. Using a prototype implementation of the algorithm we were able to perform an interactive walkthrough of large data sets such as the visible human on a single off-the-shelf PC.

In this paper, we address the problem of automatic camera positioning and automatic camera path generation in the context of historical data visualization. After short description of the given data, we elaborate on the constraints for the positioning of a virtual camera in such a way that not only the projected area is maximized, but also the depth of the displayed scene. This is especially important when displaying terrain models, which do not provide good 3D impression when only the projected area is maximized. Based on this concept, we present a method for computing an optimal camera position for each instant of time. Since the explored data are not static, but change depending on the explored scene time, we also discuss a method for animation generation. In order to avoid sudden changes of the camera position, when the previous method is applied for each frame (point in time), we introduce pseudo-events in time, which expand the bounding box defined by the currently active events of interest. In particular, this technique allows events happening in a future point in time to be taken into account such that when this time becomes current, all events of interest are already within the current viewing frustum of the camera.

We present a set of tools based on the through-the-lens metaphor. This metaphor enables simultaneous exploration of a virtual world from two different viewpoints. The one is used to display the surrounding environment and represents the user, the other is interactively adjusted and the resulting images are displayed in a dedicated window.

We present a novel multi-resolution point sample rendering algorithm for keyframe animations. The algorithm accepts triangle meshes of arbitrary topology as input which are animated by specifying different sets of vertices at keyframe positions. A multi-resolution representation consisting of prefiltered point samples and triangles is built to represent the animated mesh at different levels of detail. We introduce a novel sampling and stratification algorithm to efficiently generate suitable point sample sets for moving triangle meshes. Experimental results demonstrate that the new data structure can be used to render highly complex keyframe animations like crowd scenes in real-time. Categories and Subject Descriptors: I.3.3 [Computer Graphics]: Picture / Image Generation — Display Algorithms; I.3.6 [Computer Graphics]: Methodology and Techniques — Graphics data structures and data types; G.3 [Mathematics of Computing]: Probability and Statistics — Probabilistic algorithms.

We present a new output-sensitive rendering algorithm, the randomized z-buffer algorithm. It renders an image of an arbitrary three-dimensional scene consisting of triangular primitives by reconstruction from a dynamically chosen set of random surface sample points. This approach is independent of mesh connectivity and topology. The resulting rendering time grows only logarithmically with the numbers of triangles in the scene. We were able to render walkthroughs of scenes of up to 1014 triangles at interactive frame rates. Automatic identification of low detail scene components ensures that the rendering speed of the randomized z-buffer cannot drop below that of conventional z-buffer rendering. Experimental and analytical evidence is given that the image quality is comparable to that of common approaches like z-buffer rendering. The precomputed data structures employed by the randomized z-buffer allow for interactive dynamic updates of the scene. Their memory requirements grow only linearly with the number of triangles and allow for a scene graph based instantiation scheme to further reduce memory consumption.

Interactive exploration of animated volume data is required by many application, but the huge amount of computational time and storage space needed for rendering does not yet allow the visualization of animated volumes. In this paper, we introduce an algorithm running at interactive frame rates using 3D wavelet transforms that allows for any wavelet, motion compensation techniques and various encoding schemes of the resulting wavelet coefficients to be used. We analyze different families and orders of wavelets for compression ratio and the introduced error. We use a quantization that has been optimized for the visual impression of the reconstructed volume, independent of the viewing algorithm. This enables us to achieve very high compression ratios while still being able to reconstruct the volume with as few visual artifacts as possible. A further improvement of the compression ratio has been achieved by applying a motion compensation scheme to exploit temporal coherency. Using these schemes, we are able to decompress each volume of our animation at interactive frame rates, while visualizing these decompressed volumes on a single PC. We also present a number of improved visualization algorithms for high-quality display using OpenGL hardware running at interactive frame rates on a standard PC.

In this paper, we address the problem of historical data visualization. We describe the data acquisition, preparation, and visualization. Since the data contain four dimensions, the standard 3D exploration techniques have to be extended or appropriately adapted in order to enable interactive exploration. We discuss in detail two interaction concepts: (1) navigation with one fixed dimension, and (2) quasi 4D navigation allowing to simultaneously explore the four-dimensional space. In addition, we also present a picture-in-picture display mode, enabling the user to interactively view the data, while "flying with" a particular event, tracking its motion in time and space. Finally, we present a technique for guided exploration and animation generation, allowing for a vivid gain of insight into the historical data.

Present an image-based technique for accelerated rendering of world-in-miniature (WIM)-based and multiple-viewpoint-based props. The WIM technique offers an intuitive and useful tool for navigation and manipulation within virtual environments. The multiple-viewpoint technique is often applied for enhancing visualization and navigation. Unfortunately, both approaches require multiple rendering of the viewed data. This can significantly deteriorate the frame rate and negatively influence the interaction. The proposed approach circumvents this drawback, while still providing the features of these tools.

In this paper, we present a set of tools and techniques for visualization of and interaction with historical data. First, we briefly describe the data acquisition and preparation. Afterwards, we discuss in detail the interaction approaches for exploration of historical data, containing a time dimension. In particular, we propose (1) a continuous time increment approach for visualizing 3D slices continuously moving in the 4D space; (2) a fly-with mode for viewing the scene from the perspective of the participants in the migration, we are visualizing; (3) a time lens, as an extension of the traditional magic lens for viewing arbitrary event times; (4) a time-space exploration tool for simultaneous viewing more than one event time and location of interest; (5) a guided exploration tool, which allows for viewing events on an interactively defined or pre-defined path in space. Finally, we conclude the paper with a discussion and comparison of the proposed tools.

This paper presents a novel algorithm and architectures for perspective correct displacement of the surface geometry of a polygonal model using a displacement map. This new displaced surface geometry is passed onto a traditional rendering pipeline. The algorithm uses a multiple pass approach in which the geometry is displaced in the first pass and then the displaced geometry is rendered. The significant features of the algorithm are that the surface is displaced after its triangle mesh is transformed into screen space and that it uses only bi‐linear interpolation for calculating the displaced geometry allowing a cheap incremental scan‐line implementation. A hardware architecture based on this algorithm is presented along with possible alternative implementations. The technique presented here allows greater photorealism by using increased detail without an increase in bandwidth for geometry or calculation time for transformation.

We present a new visibility driven rasterization scheme that significantly increases the rendering performance of modern graphic subsystems. Instead of rasterizing, texturing, lighting, and depth‐testing each individual pixel, we introduce a two‐level visibility mask within the rasterization stage which facilitates the removal of groups of pixels and triangles from rasterization and subsequent pipeline stages. Local visibility information is stored within the visibility mask that is updated several times during the generation of a frame. The update can easily be accomplished by extending already available (in hardware) occlusion culling mechanisms (i.e. those of HP and SGI), where it is possible to integrate the additional functionality without any additional delay cycles. In addition to these existing hardware based occlusion culling approaches—which cull only geometry contained in bounding volumes determined as occluded—we are able to significantly accelerate the rendering of the geometry determined as visible. However, our approach does not specifically rely on such occlusion culling hardware.The proposed new rasterization scheme is well suited for hardware implementation, can easily be integrated into low‐cost rasterizers, and its scalability can vary upon available chip real estate. Only incremental modifications of modern graphics subsystems are required to achieve a significant improvement in rendering performance.

Particle systems have been widely employed to simulate deformable objects, most prominently virtual textiles. We introduce particle systems that adaptively generate new particles wherever this is required to model collisions correctly. When coarse meshes collide with an object they are automatically refined. Therefore this model allows physically accurate simulations that require a much smaller number of particles than regular particle systems. This allows for fast simulations with coarse meshes.

We present a new technique for extracting regions of interest (ROI) applying a local watershed transformation. The proposed strategy for computing catchment basins in a given region of interest is based on a rain-falling simulation. Unlike the standard watershed algorithms, which flood the complete (gradient magnitude of an) image, the proposed approach allows us to perform this task locally. Thus, a controlled region growth is performed, saving time and reducing the memory requirement especially when applied on volume data. A second problem arising from the standard watershed transformation is the over-segmented result and the lack of sound criteria for merging the computed basins. For overcoming this drawback, we present a basin-merging strategy introducing four criteria for merging adjacent basins. The threshold values applied in this strategy are derived from the user input and match rather the attributes of the selected object than of all objects in the image. In doing so, the user is not required to adjust abstract numbers, but to simply select a coarse region of interest. Moreover, the proposed algorithm is not limited to the 2D case. As we show in this work, it is suitable for volume data processing as well. Finally, we present the results of applying the proposed approach on several example images and volume data sets.

In this paper we consider the problem of reconstructing triangular surfaces from given contours. An algorithm solving this problem has to decide which contours of two successive slices should be connected by the surface (branching problem), and, given that, which vertices of the assigned contours should be connected for the triangular mesh (correspondence problem). We present a new approach that solves both tasks in an elegant way. The main idea is to employ discrete distance fields enhanced with correspondence information. This allows us not only to connect vertices from successive slices in a reasonable way but also to solve the branching problem by creating intermediate contours where adjacent contours differ too much. Last but not least we show how the 2D-distance fields used in the reconstruction step can be converted to a 3D-distance field that can be advantageously exploited for distance calculations during a subsequent simplification step.

We present a system for interactive explorations of extra- and intracranial blood vessels. Starting with a stack of images from 3D angiography, we use virtual clips to limit the segmentation of the vessel tree to the parts the neuroradiologists are interested in. Furthermore, methods of interactive virtual endoscopy are applied in order to provide an interior view of the blood vessels.

In recent years, substantial progress has been achieved in the area of volume visualization on irregular grids, which is mainly based on tetrahedral meshes. Even moderately fine tetrahedral meshes consume several mega-bytes of storage. For archivation and transmission compression algorithms are essential. In scientific applications lossless compression schemes are of primary interest. This paper introduces a new lossless compression scheme for the connectivity of tetrahedral meshes. Our technique can handle all tetrahedral meshes in three dimensional euclidean space even with non manifold border. We present compression and decompression algorithms which consume for reasonable meshes linear time in the number of tetrahedra. The connectivity is compressed to less than 2.4 bits per tetrahedron for all measured meshes. Thus a tetrahedral mesh can almost be reduced to the vertex coordinates, which consume in a common representation about one quarter of the total storage space. We complete our work with solutions for the compression of vertex coordinates and additional attributes, which might be attached to the mesh.

We present a new technique which enables direct volume rendering based on 3D texture mapping hardware, enabling shading as well as classification of the interpolated data. Our technique supports accurate lighting for a one directional light source, semi-transparent classification, and correct blending. To circumvent the limitations of one general classification, we introduce multiple classification spaces which are very valuable to understand the visualized data, and even mandatory to comprehensively grasp the 3D relationship of different materials present in the volumetric data. Furthermore, we illustrate how multiple classification spaces can be realized using existing graphics hardware. In contrast to previously reported algorithms, our technique is capable of performing all the above mentioned tasks within the graphics pipeline. Therefore, it is very efficient: The three dimensional texture needs to be stored only once and no load is put onto the CPU. Besides using standard OpenGL functionality, we exploit advanced per pixel operations and make use of available OpenGL extensions.

State of the art multiresolution modeling allows to selectively refine a coarse mesh of an object on the visually important parts. In this way it is possible to render the geometry of a given object accurately with a minimum number of triangles. There are also approaches that use cones of normal vectors to perform illumination dependent selective refinement. This includes the correct rendering of highlights and transitions between lit and unlit areas of an object. The drawback of these approaches is that using only the normal cone for the detection gives only a very poor criteria to detect the problematic cases. Therefore, too much refinement has to be performed which in most cases prevents real time update rates between successive frames. The authors describe a new approach for better estimation of normal deviations between different levels of detail. This allows for accurate lighting with a minimum number of triangles.

In this paper we introduce a new compressed representation for the connectivity of a triangle mesh. We present local compression and decompression algorithms which are fast enough for real time applications. The achieved space compression rates keep pace with the best rates reported for any known global compression algorithm. These nice properties have great benefits for several important applications. Naturally, the technique can be used to compress triangle meshes without significant delay before they are stored on external devices or transmitted over a network. The presented decompression algorithm is very simple allowing a possible hardware realization of the decompression algorithm which could significantly increase the rendering speed of pipelined graphics hardware. CR Categories: I.3.1 [Computer Graphics]: Hardware Architecture; I.3.3 [Computer Graphics]: Picture/Image Generation--- Display algorithms Keywords: Mesh Compression, Algorithms, 3D Graphics Hardware, Graphics 1 In...

In many cases the surfaces of geometric models consist of a large number of triangles. Several algorithms were developed to reduce the number of triangles required to approximate such objects. Algorithms that measure the deviation between the approximated object and the original object are only available for special cases. We use the Hausdorff distance between the original and the simplified mesh as a geometrically meaningful error value which can be applied to arbitrary triangle meshes. We present a new algorithm to reduce the number of triangles of a mesh without exceeding a user defined Hausdorff distance between the original and simplified mesh. As this distance is parameterization independent, its use as error measure is superior to the use of the L/sup /spl infin//-Norm between parameterized surfaces. Furthermore the Hausdorff distance is always less than the distance induced by the L/sup /spl infin//-Norm. This results in higher reduction rates. Excellent results were achieved by the new decimation algorithm for triangle meshes that has been used in different application areas such as volume rendering, terrain modeling and the approximations of parameterized surfaces. The key advantages of the new algorithm are: it guarantees a user defined position dependent approximation error; it allows one to generate a hierarchical geometric representation in a canonical way; it automatically preserves sharp edges.

Abstract The discussion on the advantages and disadvantages of 2D, 3D, and VR interfaces and their applicability to different types of systems, users, and information led to a series of stand‐alone implementations that lack the possibility of realizing an integrated approach. The acceptance of the different interaction techniques will depend on their success in practical applications, i.e. with systems that are used by different users for different purposes. Since this acceptance is especially hard to achieve in computer‐critical environments, such as medicine, we developed a software environment that allows for the development, integration, and user‐centered evaluation of existing and new interaction techniques for their use in medical applications. This environment is equipped with an innovative message‐passing functionality that provides the communication to and among application objects in 2D, 3D, and VR. Furthermore, the environment contains a component for user‐adapted interaction and system support at runtime.

Abstract Volume rendering is a key technique in scientific visualization that lends itself to significant exploitable parallelism. The high computational demands of real‐time volume rendering and continued technological advances in the area of VLSl give impetus to the development of special‐purpose volume rendering architectures. This paper presents and characterizes three recently developed volume rendering engines which are based on the ray‐casting method. A taxonomy of the algorithmic variants of ray‐casting and details of each ray‐casting architecture are discussed. The paper then compares the machinefeatures and provides an outlook onfuture developments in the area of volume rendering hardware.

Visualization and modeling of textile materials has already been investigated in detail in the computer graphics literature. Most of the work, however, concentrates on woven fabrics. We present a novel approach to the modeling and rendering of knitwear. After the topological specification of a knitting pattern a subdivision into basic elements is done. The yarn microstructure within basic elements is approximated by volume data sets. The repetitive structure of knitted fabrics allows an efficient rendering technique. Resulting images are given that demonstrate the feasibility of our approach.

The EXACT (EXact Area Coverage calculaTion) algorithm presented in this paper solves the Hidden Surface Elimination (HSE) problem on the subpixel level.The use of subpixel masks for anti-aliasing causes some problems with the HSE on the pixel level that are difficult to overcome.The approximations of the well known A-buffer algorithm are replaced by an exact solution that avoids erratic pixels along intersecting or touching surfaces.With EXACT the HSE problem on the subpixel level is solved with the help of p-masks.P-masks (priority masks) are subpixel masks that indicate for each subpixel which one of two given planes is closer to the viewer.An algorithm to produce the p-masks in an efficient way and its hardware implementation are presented.The p-mask generator is used in a hardware implementation of an A-buffer algorithm in the form of a rendering pipeline.Of course the algorithm can also be used in software to enhance an existing A-buffer implementation.The paper ends with the description of the list processing architecture for which the EXACT A-buffer has been built 1 CR Categories and Subject Descriptors: I.3.

In this work we focus on one of the key problems of scientific visualization, the object recognition dilemma. The necessity to pre-interpret application data in order to classify object surface voxels prior to rendering has prevented many visualization methods from becoming practical. We propose the concept of vision by visualization which integrates computer vision methods into the visualization process. Based on this, we present the vision camera, a new tool allowing for interactive object recognition during volume data walkthroughs. This camera model is characterized by a flexible front-plane which, under the control of user-specified parameters and image features elastically matches to object surfaces, while shifted through a data volume. Thus, objects are interactively carved out and can be visualized by standard volume visualization methods. Implementation and application of the model are described. Our results suggest that by the integration of human and machine vision new perspectives for data exploration are opened up.>

No abstract available.

Abstract The main advantage when using a standardized graphics system is quite obvious: the application programs become portable. Integrating such a system ‐ and GKS (Graphical Kernel System) is the only one being standardized internationally ‐ into VLSI (Very Large Scale Integration) chips, this graphics system may become an integral part of graphical devices. This guarantees a uniform interface of such devices to GKS applications. Devices of many different kinds will become compatible not only with respect to plugging but even in their logical behaviour, eliminating all device dependencies from the host software. We have started to design the GKS‐chip which will be able to be used in a great variety of devices (vector and raster type). The GKS‐chip will bring the computational power to support real time picture updates, limited only by the maximally attainable output data rate.