Games, 3D simulations, and cinematic pipelines depend on realistic 3D terrain for immersion. However, creating detailed 3D terrain is labour-intensive: artists sculpt elevation, iterate on mountains, rivers, lakes, and must often repeat the entire workflow when the design changes. Recent generative approaches are attempting to address this challenge, but they primarily focus on a single landform (typically mountains) and overlook structural features, such as river networks, roads, or lakes.

We present a real-time projection mapping system for visualizing information and displaying user interfaces on uneven, deformable surfaces in dynamic environments, where the surface gets partially and dynamically occluded. An important application area is the operating room, where this technology would allow for projection onto the surgical drapes. To achieve precise and adaptive geometric correction in setups with multiple projectors and overlapping, partially occluded projection regions, we adapt a point cloud rendering technique that accurately and efficiently reconstructs surface geometry in the projectors’ image space. This enables an overlap precision of 1.6 mm at a projection distance of 2 m, even on uneven surfaces. In addition, we propose two novel GPU-based blur mitigation methods that address blur caused by inevitable inaccuracies of the depth sensors and the overlapping projector images. A user study (n = 23) shows that our blur mitigation strategies significantly enhance perceived readability, reduce visual artifacts, and lower user workload compared to conventional multi-projector blending. Our system supports projection on arbitrary surfaces, without requiring explicit segmentation and is well-suited to meet the demands of sensitive environments, including those with sterility constraints or limited display access.

Abstract We present a novel approach for simulating eclipses, incorporating effects of light scattering and refraction in the occluder's atmosphere. Our approach not only simulates the eclipse shadow, but also allows for watching the Sun being eclipsed by the occluder. The latter is a spectacular sight which has never been seen by human eyes: For an observer on the lunar surface, the atmosphere around Earth turns into a glowing red ring as sunlight is refracted around the planet. To simulate this, we add three key contributions: First, we extend the Bruneton atmosphere model to simulate refraction. This allows light rays to be bent into the shadow cone. Refraction also adds realism to the atmosphere as it deforms and displaces the Sun during sunrise and sunset. Second, we show how to precompute the eclipse shadow using this extended atmosphere model. Third, we show how to efficiently visualize the glowing atmosphere ring around the occluder. Our approach produces visually accurate results suited for scientific visualizations, science communication, and video games. It is not limited to the Earth‐Moon system, but can also be used to simulate the shadow of Mars and potentially other bodies. We demonstrate the physical soundness of our approach by comparing the results to reference data. Because no data is available for eclipses beyond the Earth‐Moon system, we predict how an eclipse on a Martian moon will look like. Our implementation is available under the terms of the MIT license.

Optimal illumination of the surgical site is crucial for successful surgeries. Current lighting systems, however, suffer from significant drawbacks, particularly shadows cast by surgeons and operating room personnel. We introduce an innovative, module-based lighting system that actively prevents shadows using an array of swiveling, ceiling-mounted light modules. The intensity and orientation of these modules are autonomously controlled by novel algorithms utilizing multiple depth sensors mounted above the operating table. This article presents our complete system, detailing the algorithms for autonomous control and the initial optimization of the light module setup. Unlike prior work that was largely conceptual and based on simulations, this study introduces a real prototype featuring 56 light modules and three depth sensors. We evaluate this prototype through measurements, semi-structured interviews ( n \(=\) 4), and an extensive quantitative user study ( n \(=\) 11). The evaluation focuses on illumination quality, shadow elimination, and suitability for open surgeries compared to conventional OR lights. Our results demonstrate that the novel lighting system and optimization algorithms outperform conventional OR lights for abdominal surgeries, according to both objective measures and subjective ratings by surgeons.

Virtual reality training simulations to acquire surgical skills are important for increasing patient safety and save valuable resources, e.g., cadavers, supervision and operating room time. However, as surgery is a craft, simulators must not only provide a high degree of visual realism, but especially a realistic haptic behavior. While such simulators exist for surgeries like laparoscopy or arthroscopy, other surgical fields, especially where large forces need to be exerted, like total hip arthroplasty (THA; implantation of a hip joint protheses), lack realistic VR training simulations. In this paper we present for the first time a novel VR training simulation for the five steps of THA (from femur head resection to stem implantation) with realis-tic haptic feedback. To achieve this, a novel haptic hammering device, an upgraded version of the Virtuose 6D haptic device from Haption, novel algorithms for collision detection, haptic rendering, and material removal are introduced. In a study with 17 surgeons of diverse experience levels, we confirmed the realism, usefulness and usability of our novel methods.

The way a user is represented in virtual reality is a key element for applications ranging from entertainment to immersive communication and remote collaboration. Having realistic and expressive avatars leads to a stronger sense of embodiment and presence. However, they also lead to increased system latency, which can cause several negative effects, including cybersickness and a reduced sense of embodiment. We conducted a user study to investigate the (interaction) effects of avatar representation/quality and latency on embodiment, task efficiency, and cybersickness in VR. Specifically, we compared a high-quality, personalized point cloud avatar with a lower-quality pre-modeled mesh avatar and latency settings between 150 and 300 ms. We found that the avatar quality had a greater effect on all components of embodiment than latency, and that the perception of the latter was influenced by the avatar representation. High-quality avatars were consistently and significantly rated superior and led to a less severe perception of latency. In contrast, avatar type and latency level had little effect on task efficiency and no notable one on cybersickness. Our work has practical implications for researchers and developers as it shows that having a high-quality avatar in VR is crucial, even at the cost of higher latency, as its benefits outweigh and reduce the negative effects of latency.

Indirect vision through a mirror, while bi-manually manipulating both the mirror and another tool is a relatively common way to perform operations in various types of surgery. However, learning such psychomotor skills requires extensive training; they are difficult to teach; and they can be quite costly, for instance, for dentistry schools. In order to study the effectiveness of VR simulators for learning these kinds of skills, we developed a simulator for training dental surgery procedures, which supports tracking of eye gaze and tool trajectories (mirror and drill), as well as automated outcome scoring. We carried out a pre-/post-test study in which 30 fifth-year dental students received six training sessions in the access opening stage of the root canal procedure using the simulator. In addition, six experts performed three trials using the simulator. The outcomes of drilling performed on realistic plastic teeth showed a significant learning effect due to the training sessions. Also, students with larger improvements in the simulator tended to improve more in the real-world tests. Analysis of the tracking data revealed novel relationships between several metrics w.r.t. eye gaze and mirror use, and performance and learning effectiveness: high rates of correct mirror placement during active drilling and high continuity of fixation on the tooth are associated with increased skills and increased learning effectiveness. Larger time allocation for tooth inspections using the mirror, i.e., indirect vision, and frequency of inspection are associated with increased learning effectiveness. Our findings suggest that eye tracking can provide valuable insights into student learning gains of bi-manual psychomotor skills, particularly in indirect vision environments.

Collecting training data for pose estimation methods on images is a time-consuming task and usually involves some kind of manual labeling of the 6D pose of objects. This time could be reduced considerably by using marker-based tracking that would allow for automatic labeling of training images. However, images containing markers may reduce the accuracy of pose estimation due to a bias introduced by the markers. In this paper, we analyze the influence of markers in training images on pose estimation accuracy. We investigate the accuracy of estimated poses for three different cases: i) training on images with markers, ii) removing markers by inpainting, and iii) augmenting the dataset with randomly generated markers to reduce spatial learning of marker features. Our results demonstrate that utilizing marker-based techniques is an effective strategy for collecting large amounts of ground truth data for pose prediction. Moreover, our findings suggest that the usage of inpainting techniques do not reduce prediction accuracy. Additionally, we investigate the effect of inaccuracies of labeling in training data on prediction accuracy. We show that the precise ground truth data obtained through marker tracking proves to be superior compared to markerless datasets if labeling errors of 6D ground truth exist. Our data generation tools are available online: https://github.com/JHRosskamp/6DPoseDataGenTools

Abstract Most real‐time rendering models for atmospheric effects have been designed and optimized for Earth's atmosphere. Some authors have proposed approaches for rendering other atmospheres, but these methods still use approximations that are only valid on Earth. For instance, the iconic blue glow of Martian sunsets can not be represented properly as the complex interference effects of light scattered at dust particles can not be captured by these approximations. In this paper, we present an approach for generalizing an existing model to make it capable of rendering extraterrestrial atmospheres. This is done by replacing the approximations with a physical model based on Mie Theory. We use the particle‐size distribution, the particle‐density distribution as well as the wavelength‐dependent refractive index of atmospheric particles as input. To demonstrate the feasibility of this idea, we extend the model by Bruneton et al. [BN08] and implement it into CosmoScout VR, an open‐source visualization of our Solar System. In a first step, we use Mie Theory to precompute the scattering behaviour of a particle mixture. Then, multi‐scattering is simulated, and finally the precomputation results are used for real‐time rendering. We demonstrate that this not only improves the visualization of the Martian atmosphere, but also creates more realistic results for our own atmosphere.

Accurate and fast understanding of the patient's anatomy is crucial in surgical decision making and particularly important in visceral surgery. Sophisticated visualization techniques such as 3D Volume Rendering can aid the surgeon and potentially lead to a benefit for the patient. Recently, we proposed a novel volume rendering technique called Adaptive Volumetric Illumination Sampling (AVIS) that can generate realistic lighting in real-time, even for high resolution images and volumes but without introducing additional image noise. In order to evaluate this new technique, we conducted a randomized, three-period crossover study comparing AVIS to conventional Direct Volume Rendering (DVR) and Path Tracing (PT). CT datasets from 12 patients were evaluated by 10 visceral surgeons who were either senior physicians or experienced specialists. The time needed for answering clinically relevant questions as well as the correctness of the answers were analyzed for each visualization technique. In addition to that, the perceived workload during these tasks was assessed for each technique, respectively. The results of the study indicate that AVIS has an advantage in terms of both time efficiency and most aspects of the perceived workload, while the average correctness of the given answers was very similar for all three methods. In contrast to that, Path Tracing seems to show particularly high values for mental demand and frustration. We plan to repeat a similar study with a larger participant group to consolidate the results.

Abstract We propose a novel method to avoid stereo window violations at screen borders. These occur for objects in front of the zero parallax plane, which appear in front of the (physical) screen, and that are clipped for one eye while still being visible for the other eye. This contradicts other stereo cues, particularly disparity, potentially resulting in eye strain and simulator sickness. In interactive and dynamic virtual environments, where the user controls the camera, for example, via head tracking, it is impossible to avoid stereo window violations completely. We propose Dynparity, a novel rendering method to eliminate the conflict between clipping and negative disparity, by introducing a nonuniform stereoscopic projection. For each vertex in front of the zero parallax plane, we compute the stereoscopic projection such that the parallax approaches zero toward the edge of the screen. Our approach works entirely on the GPU in real‐time and can be easily included in modern game engines. We conducted a user study comparing our method to the standard stereo projection on a large‐screen stereo wall with head tracking. Our results show significantly reduced simulator sickness when using Dynparity compared to the standard stereo rendering.

Abstract Large high-resolution displays (LHRDs) provide an enabling technology to achieve immersive, isometrically registered, virtual environments. It has been shown that LHRDs allow better size judgments, higher collaboration performance, and shorter task completion times. This paper presents novel insights into human size perception using large-scale floor displays, in particular in-depth evaluations of size judgment accuracy, precision, and task completion time. These investigations have been performed in the context of six, novel applications in the domain of automotive production planning. In our studies, we used a 54-sqm sized LED floor and a standard tablet visualizing relatively scaled and true to scale 2D content, which users had to estimate using different aids. The study involved 22 participants and three different conditions. Results indicate that true to scale floor visualizations reduce the mean absolute percentage error of spatial estimations. In all three conditions, we did not find the typical overestimation or underestimation of size judgments.

Abstract Registration is an essential prerequisite for many applications when a multiple-camera setup is used. Due to the noise in depth images, registration procedures for depth sensors frequently rely on the detection of a target object in color or infrared images. However, this prohibits use cases where color and infrared images are not available or where there is no mapping between the pixels of different image types, e.g., due to separate sensors or different projections. We present our novel registration method that requires only the point cloud resulting from the depth image of each camera. For feature detection, we propose a combination of a custom-designed 3D registration target and an algorithm that is able to reliably detect that target and its features in noisy point clouds. Our evaluation indicates that our lattice detection is very robust (with a precision of more than 0.99) and very fast (on average about 20 ms with a single core). We have also compared our registration method with known methods: Our registration method achieves an accuracy of 1.6 mm at a distance of 2 m using only the noisy depth image, while the most accurate registration method achieves an accuracy of 0.7 mm requiring both the infrared and depth image.

Abstract We present a novel approach of redirected walking (RDW) based on step feedback sounds to redirect users in virtual reality. The main idea is to achieve path manipulation by changing step noises to deviate the users, who still believe that they are walking a straight line. Our approach can be combined with traditional visual approaches for RDW based on eye-blinking. Moreover, we have conducted a user study in a large area ( $$10\times 20$$ 10 × 20 m) using a within-subject design. We achieved a translational redirection of 1.7m in average with pure audio feedback. Moreover, our results show that visual methods can amplify the deviation of our new auditory approach by 80cm in average at the distance of 20 m.

The precise registration between multiple depth sensors is a crucial prerequisite for many applications. Previous techniques frequently rely on RGB or IR images and checkerboard targets for feature detection. However, this prohibits the usage for use-cases where neither is available or where IR and depth images have different projections. Therefore, we present a novel registration approach that uses depth data exclusively for feature detection, making it more universally applicable while still achieving robust and precise results. We propose a combination of a custom 3D registration target — a lattice with regularly-spaced holes — and a feature detection algorithm that is able to reliably extract the lattice and its features from noisy depth images. In addition, we have integrated the registration procedure to a publicly available Unreal Engine 4 plugin that allows multiple point clouds captured by several depth cameras to be registered in a virtual environment. Despite the rather noisy depth images, we are able to quickly obtain a robust registration that yields an average deviation of 3.8 mm to 4.4 mm in our test scenarios.

Recent results suggest that biometric identification based on human's eye movement characteristics can be used for authentication. In this paper, we present three new methods and benchmark them against the state-of-the-art. The best of our new methods improves the state-of-the-art performance by 5.2 percentage points. Furthermore, we investigate some of the factors that affect the robustness of the recognition rate of different classifiers on gaze trajectories, such as the type of stimulus and the tracking trajectory length. We find that the state-of-the-art method only works well when using the same stimulus for testing that was used for training. By contrast, our novel method more than doubles the identification accuracy for these transfer cases. Furthermore, we find that with only 90 seconds of eye tracking data, 86.7% accuracy can be achieved.

Abstract Advances in computer technology and increasing usage of computer graphics in a broad field of applications lead to rapidly rising demands regarding size and detail of virtual landscapes. Manually creating huge, realistic looking terrains and populating them densely with assets is an expensive and laborious task. In consequence, (semi-)automatic procedural terrain generation is a popular method to reduce the amount of manual work. However, such methods are usually highly specialized for certain terrain types and especially the procedural generation of landscapes composed of different biomes is a scarcely explored topic. We present a novel system, called AutoBiomes, which is capable of efficiently creating vast terrains with plausible biome distributions and therefore different spatial characteristics. The main idea is to combine several synthetic procedural terrain generation techniques with digital elevation models (DEMs) and a simplified climate simulation. Moreover, we include an easy-to-use asset placement component which creates complex multi-object distributions. Our system relies on a pipeline approach with a major focus on usability. Our results show that our system allows the fast creation of realistic looking terrains.

We present a novel data structure for SIMD optimized simultaneous bounding volume hierarchy (BVH) traversals like they appear for instance in collision detection tasks. In contrast to all previous approaches, we consider both the traversal algorithm and the construction of the BVH. The main idea is to increase the branching factor of the BVH according to the available SIMD registers and parallelize the simultaneous BVH traversal using SIMD operations. This requires a novel BVH construction method because traditional BVHs for collision detection usually are simple binary trees. To do that, we present a new BVH construction method based on a clustering algorithm, Batch Neural Gas, that is able to build efficient n-ary tree structures along with SIMD optimized simultaneous BVH traversal. Our results show that our new data structure outperforms binary trees significantly.

We present a study investigating the question whether and how people's intention to change their environmental behavior depends on the degrees of immersion and freedom of navigation when they experience a virtual coral reef. The most striking result is, perhaps, that the highest level of immersion combined with the highest level of navigation did not lead to the highest intentions to change behavior.

We present a novel haptic rendering approach to simulate material removal in medical simulations at haptic rates. The core of our method is a new massively-parallel continuous collision detection algorithm in combination with a stable and flexible 6-DOF collision response scheme that combines penalty-based and constraint-based force computation.

We present a novel algorithm, called AstroGen, to procedurally generate highly detailed and realistic 3D meshes of small celestial bodies automatically. AstroGen gains it's realism from learning surface details from real world asteroid data. We use a sphere packing-based metaball approach to represent the rough shape and a set of noise functions for the surface details. The main idea is to apply an optimization algorithm to adopt these representations to available highly detailed asteroid models with respect to a similarity measure. Our results show that our approach is able to generate a wide variety of different celestial bodies with very complex surface structures like caves and craters.

We present the first VR training simulator for hip replacement surgeries. We solved the main challenges of this task - high and stable forces during the milling process while simultaneously a very sensitive feedback is required - by using an industrial robot for the force output and the development of a novel massively parallel haptic rendering algorithm with support for material removal.

We present the first VR training simulator for hip replacement surgeries. We solved the main challenges of this task - high and stable forces during the milling process while simultaneously a very sensitive feedback is required - by using an industrial robot for the force output and the development of a novel massively parallel haptic rendering algorithm with support for material removal.

We present a novel statistical shape descriptor for arbitrary three-dimensional shapes as a six-dimensional feature for generic classification purposes. Our feature parameterizes the complete geo-metrical relation of the global shape and additionally considers local dissimilarities while being invariant to the shape appearance. Our approach allows the classification of large-scale shapes with only small local dissimilarities. Our feature can be easily quantized and mapped into a histogram, which can be used for efficient and effective classification. We take advantage of GPU processing in order to efficiently compute our invariant local shape descriptor feature even for large-scale shapes. Our synthetic benchmarks show that our approach outperforms state-of-the-art methods for local shape dissimilarity classification. In general, it yields robust and promising recognition rates even for noisy data.

We present a novel approach for approximating objective functions in arbitrary deterministic and stochastic multi-objective blackbox simulations. Usually, simulated-based optimization approaches require pre-defined objective functions for optimization techniques in order to find a local or global minimum of the specified simulation objectives and multi-objective constraints. Due to the increasing complexity of state-of-the-art simulations, such objective functions are not always available, leading to so-called blackbox simulations.

Many virtual and mixed reality games focus on single player experiences. In this paper, we describe the concept and prototype implementation of a mixed reality multiplayer game that can be played with a smartphone and an HMD in outdoor environments. Players can team up to fight against attacking alien drones. The relative positions between the players are tracked using GPS, and the rear camera of the smartphone is used to augment the environment and teammates with virtual objects. The combination of multiplayer, mixed reality, the use of geographical location and outdoor action together with affordable, mobile equipment enables a novel strategic and social game experience.

We define a novel geometric predicate and a class of objects that enables us to prove a linear bound on the number of intersecting polygon pairs for colliding 3D objects in that class. Our predicate is relevant both in theory and in practice: it is easy to check and it needs to consider only the geometric properties of the individual objects – it does not depend on the configuration of a given pair of objects. In addition, it characterizes a practically relevant class of objects: we checked our predicate on a large database of real-world 3D objects and the results show that it holds for all but the most pathological ones. Our proof is constructive in that it is the basis for a novel collision detection algorithm that realizes this linear complexity also in practice. Additionally, we present a parallelization of this algorithm with a worst-case running time that is independent of the number of polygons. Our algorithm is very well suited not only for rigid but also for deformable and even topology-changing objects, because it does not require any complex data structures or pre-processing. We have implemented our algorithm on the GPU and the results show that it is able to find in real-time all colliding polygons for pairs of deformable objects consisting of more than 200k triangles, including self-collisions.

We present a new graph-based approach called GraphPool for the generation, management and distribution of simulation states for 3D simulation applications. Currently, relational databases are often used for this task in simulation applications. In contrast, our approach combines novel wait-free nested hash map techniques with traditional graphs which results in a schema-less, in-memory, highly efficient data management. Our GraphPool stores static and dynamic parts of a simulation model, distributes changes caused by the simulation and logs the simulation run. Even more, the GraphPool supports sophisticated query types of traditional relational databases. As a consequence, our GraphPool overcomes the associated drawbacks of relational database technology for sophisticated 3D simulation applications. Our GraphPool has several advantages compared to other state-of-the-art decentralized methods, such as persistence for simulation state over time, object identification, standardized interfaces for software components as well as a consistent world model for the overall simulation system. We tested our approach in a synthetic benchmark scenario but also in real-world use cases. The results show that it outperforms state-of-the-art relational databases by several orders of magnitude.

We present a novel knowledge discovery approach for automatic feasible design space approximation and parameter optimization in arbitrary multiobjective blackbox simulations. Our approach does not need any supervision of simulation experts. Usually simulation experts conduct simulation experiments for a predetermined system specification by manually reducing the complexity and number of simulation runs by varying input parameters through educated assumptions and according to prior defined goals. This leads to a error-prone trial-and-error approach for determining suitable parameters for successful simulations.In contrast, our approach autonomously discovers unknown relationships in model behavior and approximates the feasible design space. Furthermore, we show how Pareto gradient information can be obtained from this design space approximation for state-of-the-art optimization algorithms. Our approach gains its efficiency from a novel spline-based sampling of the parameter space in combination within novel forest-based simulation dataflow analysis. We have applied our new method to several artificial and real-world scenarios and the results show that our approach is able to discover relationships between parameters and simulation goals. Additionally, the computed multiobjective solutions are close to the Pareto front.

Template matching is a well-proven approach in the area of articulated object tracking. Matching accuracy and computation time of template matching are essential and yet often conflicting goals. In this paper, we present a novel, adaptive template matching approach based on the silhouette area of the articulated object. With our approach, the ratio between accuracy and speed simply is a modifiable parameter, and, even at high accuracy, it is still faster than a state-of-the-art approach. We approximate the silhouette area by a small set of axis-aligned rectangles. Utilizing the integral image, we can thus compare a silhouette with an input image at an arbitrary position independently of the resolution of the input image. In addition, our rectangle covering yields a very memory efficient representation of templates. Furthermore, we present a new method to build a template hierarchy optimized for our rectangular representation of template silhouettes. With the template hierarchy, the complexity of our matching method for n templates is O(logn) and independent of the input resolution. For example, a set of 3000 templates can be matched in 2.3 ms. Overall, our novel methods are an important contribution to a complete system for tracking articulated objects.

Filling objects densely with sets of non overlapping spheres has been investigated for centuries. Once started as a pure intellectual challenge, today, sphere packings have diverse applications in a wide spectrum of scientific and engineering disciplines, for example in automated radiosurgical treatment planning, investigation of processes such as sedimentation, compaction and sintering, in powder metallurgy for three-dimensional laser cutting, in cutting different natural crystals, the discrete element method is based on them, and so forth.

We present a benchmarking suite for rigid object collision detection and collision response schemes. The proposed benchmarking suite can evaluate both the performance as well as the quality of the collision response. The former is achieved by densely sampling the configuration space of a large number of highly detailed objects; the latter is achieved by a novel methodology that comprises a number of models for certain collision scenarios. With these models, we compare the force and torque signals both in direction and magnitude.

In this paper, we present a novel approach for parallel sorting on stream processing architectures. It is based on adaptive bitonic sorting. For sorting n values utilizing p stream processor units, this approach achieves the optimal time complexity O((n log n)/p). While this makes our approach competitive with common sequential sorting algorithms not only from a theoretical viewpoint, it is also very fast from a practical viewpoint. This is achieved by using efficient linear stream memory accesses (and by combining the optimal time approach with algorithms optimized for small input sequences). We present an implementation on modern programmable graphics hardware (GPUs). On GPUs, our optimal parallel sorting approach has shown to be remarkably faster than sequential sorting on the CPU, and it is also faster than previous non-optimal sorting approaches on the GPU for sufficiently large input sequences. Because of the excellent scalability of our algorithm with the number of stream processor units p (up to n/log/sup 2/ n or even n/log n units, depending on the stream architecture), our approach profits heavily from the trend of increasing number of fragment processor units on GPUs, so that we can expect further speed improvement with upcoming GPU generations.

We present a hardware architecture for a single-chip acceleration of an efficient hierarchical collision detection algorithm as well as simulation results for collision queries using this architecture. The architecture consists of two main stages, one for traversing simultaneously a hierarchy of discretely oriented polytopes, and one for intersecting triangles. Within each stage, the architecture is deeply pipelined and parallelized. For the first stage, we compare and evaluate different traversal schemes for bounding volume hierarchies. A simulation in VHDL shows that a hardware implementation can offer a speed-up over a software implementation by orders of magnitude. Thus, real-time collision detection of complex objects at rates required by force feedback and physically based simulations can be achieved.

Collision detection is an enabling technology for many virtual environments, games, and virtual prototyping applications containing some kind of physically-based simulation (such as rigid bodies, cloth, surgery, etc.). The persistent interest in collision detection by both academia and industry is due to the large variety of applications as well as new challenges in new application domains, such as virtual clothes fitting. This tutorial will give an overview of the different classes of algorithms, and then provide attendees with in-depth knowledge of some of the important algorithms within each class, focusing in particular on recent approaches, such as stochastic methods or image-space techniques. Attendees will learn to select the one most appropriate for their application, and implement it with only very little further research. The intended audience are practitioners and students working in 3D computer graphics. Topics to be addressed - hierarchical collision detection - stochastic methods - distance fields - spatial subdivisions - image-space techniques - continuous collision detection - non-polygonal object representations (e.g., point clouds)

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.

In this paper, we propose a new method that can consistently orient all normals of any mesh (if at all possible), while ensuring that most polygons are seen with their front-faces from most viewpoints. Our algorithm combines the proximity-based with a new visibility-based approach. Thus, it virtually eliminates the problems of proximity-based approaches, while avoiding the limitations of previous solid-based approaches. Our new method builds a connectivity graph of the patches of the model, which encodes the "proximity" of neighboring patches. In addition, it augments this graph with two visibility coefficients for each patch. Based on this graph, a global consistent orientation of all patches is quickly found by a greedy optimization. We have tested our new method with a large suite of models, many of which from the automotive industry. The results show that almost all models can be oriented consistently and sensibly using our new algorithm

This work presents a novel calibration method for data-gloves with many degrees of freedom. The goal of our method is to establish a mapping from the sensor values of the glove to the joint angles of an articulated hand that is of 'high visual' fidelity. This is in contrast to previous methods that aim at determining the absolute values of the real joint angles with high accuracy. The advantage of our method is that it can be simply carried through without the need for auxiliary calibration hardware (such as cameras), while still producing visually correct mappings. To achieve this, we developed a method that explicitly models the cross-couplings of the abduction sensors with the neighboring flex sensors. The results show that our method performs superior to linear calibration in most cases.

Abstract In the past few years, many efficient rendering and surface reconstruction algorithms for point clouds have been developed. However, collision detection of point clouds has not been considered until now, although this is a prerequisite to use them for interactive or animated 3D graphics. We present a novel approach for time‐critical collision detection of point clouds. Based solely on the point representation, it can detect intersections of the underlying implicit surfaces. The surfaces do not need to be closed. We construct a point hierarchy where each node stores a sufficient sample of the points plus a sphere covering of a part of the surface. These are used to derive criteria that guide our hierarchy traversal so as to increase convergence. One of them can be used to prune pairs of nodes, the other one is used to prioritize still to be visited pairs of nodes. At the leaves we efficiently determine an intersection by estimating the smallest distance. We have tested our implementation for several large point cloud models. The results show that a very fast and precise answer to collision detection queries can always be given. Categories and Subject Descriptors (according to ACM CCS): G.1.2 [Numerical Analysis]: Approximation of surfaces and contours I.3.5 [Computer Graphics]: Computational Geometry and Object‐Modeling[Geometric algorithms, languages and systems; object hierarchy; physically‐based modeling] I.3.7 [Computer Graphics]: Three‐Dimensional Graphics and Realism[Animation; virtual reality]

We present a novel, generic framework and algorithm for hierarchical collision detection, which allows an application to balance speed and quality of the collision detection.We pursue an average-case approach that yields a numerical measure of the quality. This can either be specified by the simulation or interaction, or it can help to assess the result of the collision detection in a time-critical system.Conceptually, we consider sets of polygons during traversal and estimate probabilities that there is an intersection among these sets. This can be done efficiently by storing characteristics about the average distribution of the set of polygons with each node in a bounding volume hierarchy (BVH). Consequently, we neither need any polygon intersection tests nor access to any polygons during the collision detection process.Our approach can be applied to virtually any BVH. Therefore, we call a BVH that has been augmented in this way an average-distribution tree or ADB-tree.We have implemented our new approach with two basic BVHs and present performance measurements and comparisons with a very fast previous algorithm, namely the DOP-tree. The results show a speedup of about a factor 3 to 6 with only approximately 4% error.

We present a novel bounding volume hierarchy that allows for extremely small data structure sizes while still performing collision detection as fast as other classical hierarchical algorithms in most cases. The hierarchical data structure is a variation of axis-aligned bounding box trees. In addition to being very memory efficient, it can be constructed efficiently and very fast.We also propose a criterion to be used during the construction of the BV hierarchies is more formally established than previous heuristics. The idea of the argument is general and can be applied to other bounding volume hierarchies as well. Furthermore, we describe a general optimization technique that can be applied to most hierarchical collision detection algorithms.Finally, we describe several box overlap tests that exploit the special features of our new BV hierarchy. These are compared experimentally among each other and with the DOP tree using a benchmark suite of real-world CAD data.

Electro-magnetic tracking systems are in wide-spread use for measuring 6D positions. However, their accuracy is impaired seriously by distortions of the magnetic fields caused by many types of metal which are omnipresent at real sites. We present a fast and robust method for "equalizing" those distortions in order to yield accurate tracking. The algorithm is based on global scattered data interpolation using a "snap-shot" of the magnetic field's distortion measured once in advance. The algorithm is fast (it does not introduce any further lag in the data flow), robust, the samples of the field's "snap-shot" can be arranged in any way, and it is easy to implement. The distortion is visualized in an intuitive way to provide insight into its nature, and the correction algorithm is evaluated in terms of accuracy and performance. Finally, a qualitative comparison of the susceptibility of a Polhemus and an Ascension tracking system is carried out.

Virtual environments are created by specifying their content, which comprises geometry, interaction, properties, and behavior of the objects. Interaction and behavior can be cumbersome to specify and create, if they have to be implemented through an API.