News

Oct, 2017: EUROVR association is co-financing an important initiative: the VR Tour. Organized by Laval Virtual, the tour is scheduled to visit the various actors operating in the fields of Virtual and Augmented Reality in all Europe.

Jun 17, 2017: Haptic and hand tracking demos at the Open Campus 2017.

Feb-Apr 2017: David Vilela (Mechanical Engineering Laboratory, University of Coruna, Spain) visited our lab. He is working on benchmarks to compare different intersection calculation methods in collisions, and also different force models.

Feb 2017: G. Zachmann and J. Teuber visited the Mahidol University in Bangkok, Thailand as part of a delegation from the University of Bremen. The goal of the visit was to foster the cooperation between the two universities and lay ground-work for future colaborations.

Jun 2016: Radio Bremen visited our lab to film the works of the Creative Unit "Intra-Operative Information" for a news magazine on the local TV station. Click here for the film at Radio Bremen. And Click here for the same film on our Website.

May 16, 2016: Patrick Lange was honored with the SIGSIM Best PhD Award at the ACM SIGSIM PADS Conference 2016.

Jun 19-21, 2015: G. Zachmann gives invited talk at the DAAD-Stipendiatentreffen in Bremen, Germany.

Jun 2015: Haptic and hand tracking demos at the Open Campus 2015.

Dec 08-10, 2014: ICAT-EGVE 2014 and EuroVR 2014 conferences at the University of Bremen organized by G. Zachmann.

Sep 25-26, 2014: GI VR/AR 2014 conference at the University of Bremen organized by G. Zachmann.

Sep 24-25, 2014: VRIPHYS 2014 conference at the University of Bremen organized by G. Zachmann .

Feb 4, 2014: G. Zachmann gives invited talk on Interaction Metaphors for Collaborative 3D Environments at Learntec.

Jan 2014: G. Zachmann got invited to be a Member of the Review Panel in the Human Brain Project for the Competitive Call for additional project partners

Nov 2013: Invited Talk at the "Cheffrühstück 2013"

Oct 2013: PhD thesis of Rene Weller published in the Springer Series on Touch and Haptic Systems.

Jun 2013: G. Zachmann participated in the Dagstuhl Seminar Virtual Realities (13241)

Jun 2013: Haptic and hand tracking demos at the Open Campus 2013.

Jun 2013: Invited talk at Symposium für Virtualität und Interaktion 2013 in Heidelberg by Rene Weller.

Apr 2013: Rene Weller was honored with the EuroHaptics Ph.D Award at the IEEE World Haptics Conference 2013.

Jan 2013: Talk at the graduation ceremony of the University of Bremen by Rene Weller.

Oct 2012: Invited Talk by G. Zachmann at the DLR VROOS Workshop Servicing im Weltraum -- Interaktive VR-Technologien zum On-Orbit Servicing in Oberpfaffenhofen, Munich, Germany.

Oct 2012: Daniel Mohr earned his doctorate in the field of vision-based pose estimation.

Sept 2012: G. Zachmann: Keynote Talk at ICEC 2012, 11th International Conference on Entertainment Computing.

Sep 2012: "Best Paper Award" at GI VR/AR Workshop in Düsseldorf.

Sep 2012: Rene Weller earned his doctorate in the field of collision detection.

Aug 2012: GI-VRAR-Calendar 2013 is available!

Publications

[Complete list of all entries in BibTex format]


Augmented Invaders: A Mixed Reality Multiplayer Outdoor Game

Michael Bonfert, Inga Lehne, Ralf Morawe, Melina Cahnbley, Gabriel Zachmann, Johannes Schöning

Many virtual and mixed reality games focus on single player ex- periences. 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 ght 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 envi- ronment and teammates with virtual objects. The combination of multiplayer, mixed reality, the use of geographical location and outdoor action together with a ordable, mobile equipment enables a novel strategic and social game experience.

Published in:

VRST 2017, Gothenburg, Sweden, November 8-10, 2017. [BibTex]

Files:

     Paper


Invariant Local Shape Descriptors: Classification of Large-Scale Shapes with Local Dissimilarities

Xizhi Li, Patrick Lange, Rene Weller, Gabriel Zachmann

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 geometrical 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.

Published in:

Computer Graphics International 2017, Yokohoma, Japan, June 27 - 30, 2017. [BibTex]

Files:

     Paper
     Presentation
     Talk


A Volumetric Penetration Measure for 6-DOF Haptic Rendering of Streaming Point Clouds

Maximilian Kaluschke, Rene Weller and Gabriel Zachmann

We present a novel method to define the penetration volume between a surface point cloud and arbitrary 3D CAD objects. Moreover, we have developed a massively-parallel algorithm to compute this penetration measure efficiently on the GPU. The main idea is to represent the CAD object's volume by an inner bounding volume hierarchy while the point cloud does not require any additional data structures. Consequently, our algorithm is perfectly suited for streaming point clouds that can be gathered online via depth sensors like the Kinect. We have tested our algorithm in several demanding scenarios and our results show that our algorithm is fast enough to be applied to 6-DOF haptic rendering while computing continuous forces and torques.

Published in:

IEEE World Haptics Conference 2017, Fürstenfeldbruck, Germany, June 6 - 9, 2017. [BibTex]

Files:

     Paper
     Poster
     Teaser


GDS: Gradient based Density Spline Surfaces for Multiobjective Optimization in Arbitrary Simulations

Patrick Lange, Rene Weller and Gabriel Zachmann

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. In contrast to existing approaches, we approximate the objective functions and design space for deterministic and stochastic blackbox simulations, even for convex and concave Pareto fronts, thus enabling optimization for arbitrary simulations. Additionally, Pareto gradient information can be obtained from our design space approximation. Our approach gains its efficiency from a novel gradient-based sampling of the parameter space in combination with a density-based clustering of sampled objective function values, resulting in a B-spline surface approximation of the feasible design space.

Published in:

ACM SIGSIM PADS Conference 2017, Singapore, May 24 - 26, 2017. [BibTex]

Files:

     Paper
     Slides


kDet: Parallel Constant Time Collision Detection for Polygonal Objects

Rene Weller, Nicole Debowski and Gabriel Zachmann

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.

Published in:

Eurographics 2017, Lyon, France, April 24 - 28, 2017. [BibTex]

Files:

     Paper
     Talk


Virtual Reality for User-Centered Design and Evaluation of Touch-free Interaction Techniques for Navigating Medical Images in the Operating Room

Anke Reinschlüssel, Jörn Teuber, Marc Herrlich, Jeffrey Bissel, Melanie van Eikeren, Johannes Ganser, Felicia Köller, Fenja Kollasch, Thomas Mildner, Luca Raimondo, Lars Reisig, Marc Rüdel, Danny Thieme, Tobias Vahl, Gabriel Zachmann, Rainer Malaka

Computer-assisted surgery has pervaded the operating room (OR). While display and imaging technologies advance rapidly, keyboard and mouse are still the dominant input devices, even though they cause sterility problems. We present an interactive virtual operating room (IVOR), intended as a tool to develop and study interaction methods for the OR, and two novel touch-free interaction techniques using hand and foot gestures. All was developed and evaluated with 20 surgeons. The results show that our techniques can be used with minimal learning time and no significant differences regarding completion time and usability compared to the control condition relying on verbal instruction of an assistant. Furthermore, IVOR as a tool was well received by the surgeons, although they had no prior experience with virtual reality. This confirms IVOR is an effective tool for user-centered design and evaluation, providing a portable, yet realistic substitution for a real OR for early evaluations.

Published in:

CHI 2017 - Late-Breaking Work, Colorado Convention Center, Denver, CO, May 6 - 11, 2017.

Files:

     Paper


Optimized Positioning of Autonomous Surgical Lamps

Jörn Teuber, Rene Weller, Ron Kikinis, Karl-Jürgen Oldhafer, Michael J. Lipp, Gabriel Zachmann

We consider the problem of finding automatically optimal positions of surgical lamps throughout the whole surgical procedure, where we assume that future lamps could be robotized. We propose a two-tiered optimization technique for the real-time autonomous positioning of those robotized surgical lamps. Typically, finding optimal positions for surgical lamps is a multi-dimensional problem with several, in part conflicting, objectives, such as optimal lighting conditions at every point in time while minimizing the movement of the lamps in order to avoid distractions of the surgeon. Consequently, we use multi-objective optimization (MOO) to find optimal positions in real-time during the entire surgery.
Due to the conflicting objectives, there is usually not a single optimal solution for such kinds of problems, but a set of solutions that realizes a Pareto-front. When our algorithm selects a solution from this set it additionally has to consider the individual preferences of the surgeon. This is a highly non-trivial task because the relationship between the solution and the parameters is not obvious. We have developed a novel meta-optimization that considers exactly this challenge. It delivers an easy to understand set of presets for the parameters and allows a balance between the lamp movement and lamp obstruction. This meta-optimization can be pre-computed for different kinds of operations and it then used by our online optimization for the selection of the appropriate Pareto solution.
Both optimization approaches use data obtained by a depth camera that captures the surgical site but also the environment around the operating table. We have evaluated our algorithms with data recorded during a real open abdominal surgery. It is available for use for scientific purposes. The results show that our meta-optimization produces viable parameter sets for different parts of an intervention even when trained on a small portion of it.

Published in:

SPIE Medical Imaging Orlando, FL, USA, February 11 - 16, 2017. [BibTex]

Copyright 2017 Society of Photo Optical Instrumentation Engineers. One print or electronic copy may be made for personal use only. Systematic electronic or print reproduction and distribution, duplication of any material in this paper for a fee or for commercial purposes, or modification of the content of the paper are prohibited.

http://dx.doi.org/10.1117/12.2256029

Files:

     Paper
     Talk


Intelligent Realtime 3D Simulations

Patrick Lange, Gabriel Zachmann

This thesis focuses on techniques to improve performance, scalability as well as multi-objective optimization of interactive 3D simulation-based optimization applications. The approaches developed in this work contribute to the area of simulation-based optimization, high performance computing, simulation and modelling, multi-objective optimization, and realtime interactive systems.

Published in:

ACM SIGSIM PADS Phd Colloquium, Banff, AB, Canada, May 15-18, 2016, Best Phd Award [BibTex]

Files:

     Poster
     Talk


Knowledge Discovery for Pareto based Multiobjective Optimization in Simulation

Patrick Lange, Rene Weller, Gabriel Zachmann

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.

Published in:

ACM SIGSIM PADS , Banff, AB, Canada, May 15 - 18, 2016 [BibTex]

Files:

     Paper
     Talk


GraphPool: A High Performance Data Management for 3D Simulations

Patrick Lange, Rene Weller, Gabriel Zachmann

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.

Published in:

ACM SIGSIM PADS , Banff, AB, Canada, May 15 - 18, 2016 [BibTex]

Files:

     Paper
     Talk


Wait-Free Hash Maps in the Entity-Component-System Pattern for Realtime Interactive Systems

Patrick Lange, Rene Weller, Gabriel Zachmann

In the past, the Entity-Component-System (ECS) pattern has become a major design pattern used in modern architectures for Realtime Interactive Systems (RIS). In this paper we introduce high performance wait-free hash maps for the System access of Components within the ECS pattern. This allows non-locking read and write operations, leading to a highly responsive low-latency data access while maintaining a consistent data state. Furthermore, we present centralized as well as decentralized approaches for reducing the memory demand of these memory-intensive wait-free hash maps for diverse RIS applications. Our approaches gain their efficiency by Component-wise queues which use atomic markup operations for fast memory deletion. We have implemented our new method in a current RIS and the results show that our approach is able to efficiently reduce the memory usage of wait-free hash maps very effectively by more than a factor of ten while still maintaining their high performance. Furthermore, we derive best practices from our numerical results for different use cases of wait-free hash map memory management in diverse RIS applications.

Published in:

IEEE VR: 9th Workshop on Software Engineering and Architectures for Realtime Interactive Systems SEARIS 2016 , Greenville, SC, USA, March 19 - 23, 2016 [BibTex]

Files:

     Paper
     Talk


Kinaptic — Techniques and Insights for Creating Competitive Accessible 3D Games for Sighted and Visually Impaired Users

Andreas Grabski, Toni Toni, Tom Zigrand, Rene Weller, Gabriel Zachmann

We present the first accessible game that allows a fair competition between sighted and blind people in a shared virtual 3D environment.We use an asymmetric setup that allows touchless interaction via Kinect, for the sighted player, and haptic, wind, and surround audio feedback, for the blind player. We evaluated our game in an in-the-wild study. The results show that our setup is able to provide a mutually fun game experience while maintaining a fair winning chance for both players. Based on our study, we also suggest guidelines for future developments of games for visually impaired people that could help to further include blind people into society.

Published in:

Haptics Symposium 2016, Philadelphia, PA, USA, April 8 - 11, 2016 [BibTex]

Files:

     Paper
     Talk


PhD thesis: New Geometric Algorithms and Data Structures for collision detection of dynamically deforming objects

David Mainzer

This thesis presents a collision detection approach, which works entirely without an acceleration data structure and supports rigid and soft bodies. Furthermore, we can compute inter-object and intra-object collisions of rigid and deformable objects consisting of many tens of thousands of triangles in a few milliseconds. To realize this, a subdivision of the scene into parts using a fuzzy clustering approach is applied. Based on that all further steps for each cluster can be performed in parallel and if desired, distributed to different GPUs. Tests have been performed to judge the performance of our approach against other state-of-the-art collision detection algorithms. Additionally, we integrated our approach into Bullet, a commonly used physics engine, to evaluate our algorithm.

Published in:

Universitätsbibliothek Clausthal Clausthal, 2015, [BibTex]

Files:

     PhD thesis


Time-efficient and Accurate Spatial Localization of Automotive Function Architectures with Function-oriented 3D Visualization

Moritz Cohrs, Valeri Kremer, Stefan Klimke, Gabriel Zachmann

A primary challenge in the automotive industry is the continued increasing complexity of modern cars caused by the ever increasing amount of complex vehicle functions. These functions are implemented as mechatronic systems consisting of multiple individual components. A promising, relatively new approach to manage the increasing complexity in the development process is the function-oriented design that focuses on the interdisciplinary, holistic development of such functions. A frequent and important task in function-oriented design is the identification of the spatial distribution of the components and their connections of a specific function. In this paper, we present a very time-efficient and accurate solution to this task. Our solution uses virtual reality 3D visualization methods, based on consistent integration of function-oriented data with CAD data. We evaluated our method in several user studies and the results show that it is capable of fulfilling the task in a much more a time-efficient and more accurate way than the traditional method.

Published in:

Computer-Aided Design and Applications 2015, Taylor & Francis CAD'15 Journal [BibTex]

Files:

     Paper


A Framework for Transparent Execution of Massively-Parallel Applications on CUDA and OpenCL

Jörn Teuber, Rene Weller, Gabriel Zachmann

We present a novel framework for the simultaneous development for different massively parallel platforms. Currently, our framework supports CUDA and OpenCL but it can be easily adapted to other programming languages. The main idea is to provide an easy-to-use abstraction layer that encapsulates the calls of own parallel device code as well as library functions. With our framework the code has to be written only once and can then be used transparently for CUDA and OpenCL. The output is a single binary file and the application can decide during run-time which particular GPU-method it will use. This enables us to support new features of specific platforms while maintaining compatibility. We have applied our framework to a typical project using CUDA and ported it easily to OpenCL. Furthermore we present a comparison of the running times of the ported library on the different supported platforms.

Published in:

EuroVR Conference 2015, Lecco, Italy, October 15 - 16, 2015.

Files:

     Paper


Kanaria: Identifying the Challenges for Cognitive Autonomous Navigation and Guidance for Missions to Small Planetary Bodies

Alena Probst, Graciela Gonzales Peytavi, David Nakath, Anne Schattel, Carsten Rachuy, Patrick Lange, Joachimg Clemens, Mitja Echim, Verena Schwarting, Abhishek Srinivas, Konrad Gadzicki, Roger Förster, Bernd Eissfeller, Kerstin Schill, Christof Büskens, Gabriel Zachmann

With the rapid evolution of space technologies and increasing thirst for knowledge about the origin of life and the universe, the need for deep space missions as well as for autonomous solutions for complex, time-critical mission operations becomes urgent. Within this context, the project KaNaRiA aims at technology development tailored to the ambitious task of space resource mining on small planetary bodies using increased autonomy for on-board mission planning, navigation and guidance. With the aim to validate and test our methods, we create a virtual environment in which humans can interact with the simulation of the mission. In order to achieve real-time performance, we propose a massively-parallel software system architecture, which enables very efficient and easily adaptable communication between concurrent software modules within KaNaRiA.

Published in:

International Astronautical Congress (IAC) 2015, Jerusalem, Isreal, October 12 - 16, 2015.

Files:

     Paper


Autonomous Surgical Lamps

Jörn Teuber, Rene Weller, Ron Kikinis, Karl-Jürgen Oldhafer, Michael J. Lipp, Gabriel Zachmann

We present a novel method for the autonomous positioning of surgical lamps in open surgeries. The basic idea is to use an inexpensive depth camera to track all objects and the surgical staff and also generate a dynamic online model of the operation situs. Based on this information, our algorithms continuously compute the optimal positions for all surgical lamps. These positions can then be communicated to robotic arms so that the lamps mounted on their end effectors will move autonomously. This will ensure optimal lighting of the operation situs at all times, while avoiding occlusions and shadows from obstacles. We tested our algorithm in a VR simulation using real-world depth camera data that was recorded during a real abdominal operation. Our results show that our method is robust and can ensure close-to-optimal lighting conditions in real-world surgeries with an update rate of 20 Hz.

Published in:

Jahrestagung der Deutschen Gesellschaft für Computer- und Roboterassistierte Chirurgie (CURAC) 2015, Bremen, Germany, September 17 - 19, 2015. [BibTex]

Files:

     Paper
     Video


Multi Agent System Optimization in Virtual Vehicle Testbeds

Patrick Lange, Rene Weller, Gabriel Zachmann

Modelling, simulation, and optimization play a crucial role in the development and testing of autonomous vehicles. The ability to compute, test, assess, and debug suitable configurations reduces the time and cost of vehicle development. Until now, engineers are forced to manually change vehicle configurations in virtual testbeds in order to react to inappropriate simulated vehicle performance. Such manual adjustments are very time consuming and are also often made ad-hoc, which decreases the overall quality of the vehicle engineering process. In order to avoid this manual adjustment as well as to improve the overall quality of these adjustments, we present a novel comprehensive approach to modelling, simulation, and optimization of such vehicles. Instead of manually adjusting vehicle configurations, engineers can specify simulation goals in a domain specific modelling language. The simulated vehicle performance is then mapped to these simulation goals and our multi-agent system computes for optimized vehicle configuration parameters in order to satisfy these goals. Consequently, our approach does not need any supervision and gives engineers visual feedback of their vehicle configuration expectations. Our evaluation shows that we are able to optimize vehicle configuration sets to meet simulation goals while maintaining real-time performance of the overall simulation.

Published in:

EAI SIMUtools 2015, Athens, Greece, Portland, August 24 - 26, 2015.

Files:

     Paper
     Slides


Innovative and Contact-free Natural User Interaction with Cars

Mohammad Razavi, Saber Adavi, Muhammed Zaid Alam, Daniel Mohr and Gabriel Zachmann

Within the last two decades, the vehicle industry has majorly changed the way humans interact with cars and their embedded systems that provide aid and convenience for the passengers. Today, instead of using the ordinary physical button for each function, cars have multifunctional control devices with hierarchical menus, which demands the visual attention of the driver and also, they are getting progressively complex. In our approach, we introduce a contact-free, multimodal interaction system for automobiles to make interactions more natural, attractive, and intuitive. We designed an interactive car driving simulation in which various car functions such as radio, windows, mirror, and cabin lights were integrated. They are controlled by a combination of speech, natural gestures, and exploiting the visibility of objects in the car. This yields a heavily decrease in visual demand and improves robustness and user experience.

Published in:

GI VRAR Workshop 2014, Bremen, Germany [BibTex]

Files:

     Paper

Links:

     Project Homepage


Hand Pose Recognition — Overview and Current Research

Daniel Mohr and Gabriel Zachmann

Vision-based markerless hand tracking has many applica- tions, for instance in virtual prototyping, navigation in virtual environ- ments, tele- and robot-surgery and video games. It is a very challenging task, due to the real-time requirements, 26 degrees-of-freedom, high ap- pearance variability, and frequent self-occlusions. Because of that, and because of the many desirable applications, it has received increasing attention in the computer vision community of the past years. A lot of approaches have been proposed to (partially) solve the problem, but no system has been presented yet that can solve the full-DOF hand pose estimation problem robustly in real-time.
The purpose of this article is to present an overview of the approaches that have been presented so far and where future research of hand track- ing probably will go.
First, we will explain the challenges in more detail. Second, we will classify the approaches; third, we will describe the most important ap- proaches, and finally we will show the future directions and give a short overview of our current work.

Published in:

In Brunnett, G., Coquillart, S., van Liere, R., Welch, G., Váša, L. (Eds.): Virtual Realities, Springer, ISBN 978-3-319-17042-8; Revised Selected Papers of the International Dagstuhl Seminar 13241, Germany, June 9-14, 2013. [BibTex]

Files:

     Paper


Scalable Concurrency Control for Massively Collaborative Virtual Environments

Patrick Lange, Rene Weller, Gabriel Zachmann

We present a novel concurrency control mechanism for collaborative massively parallel virtual environments that allows an arbitrary amount of components to exchange data with very little synchronisation overhead. The approach taken here is to maintain the shared world state of the complete virtual environment in a global key-value pool. Our novel method does not use any locking mechanism. Instead it allows wait-free data access for all concurrent components for both, reading and writing operations. This guarantees a highly responsive low-latency data access while keeping a consistent system state for all users and system components. Nevertheless, our approach is perfectly scalable even for massive multi-user scenarios. We provide a number of benchmarks in this paper, and the results show an almost constant running time, independent of the number of concurrent users. Moreover, our approach outperforms previous concurrency control systems significantly by more than an order of magnitude.

Published in:

ACM Multimedia Systems, Massively Multiuser Virtual Environments (MMVE) 2015 , Portland, United States, March 18 - 20, 2015. [BibTex]

Files:

     Paper
     Slides


Virtual Reality for Simulating Autonomous Deep-Space Navigation and Mining

P. Lange, A. Probst, A. Srinivas, G. Gonzalez Peytavi, C. Rachuy, A. Schattel, V. Schwarting, J. Clemens, D. Nakath, M. Echim, and G. Zachmann

In accordance with the space exploration goals declared by the National Aeronautics and Space Administration (NASA) in 2010 and 2013, the investigation of the deeper solar system becomes a central objective for upcoming space missions. Within this scheme, technologies and capabilities are developed that enable manned missions beyond low-Earth orbit - to lunar orbit, lunar surface, or even Mars and beyond. Particularly interesting targets are asteroids. They can serve as test beds for hardware and technology demonstration, which is needed prior to those aspired long-term missions. Asteroids can frequently be reached with smaller energy demands than those required for a mission to Moon or Mars. Furthermore, they are assumed to contain significant amounts of water and valuable metallic volatiles, which could serve as in-situ supplies for life support systems or spacecraft maintenance. Despite these technical facts, asteroids are also very interesting targets from a scientific point of view: They are remainders of the early formation phase of the solar system and are hold responsible for bringing life to Earth [DFJ90]. As the trend in future space exploration tends to focus on objects in deep space, the importance of autonomy increases on-board of spacecraft.With augmenting signal travel time due to great distances to Earth, it is difficult or even impossible to be able to react from ground on unexpected events for which time is a crucial factor. Up to this date, spacecraft in orbit follow specific timeline procedures during time-critical mission phases or pre-designed protocols in case unknown failures occur. The most common reaction on faults is the safe mode, during which the spacecraft shuts down every on-board module except the vital systems and awaits further (recovery) instructions from Earth ground stations. Hence, the demand for closed loop decision-making processes that are independent of the tele-commanding from ground. This includes not only the handling of errors but also navigation, guidance, and attitude/orbit control tasks. Therefore, the focus of this project is to make the spacecraft independent from the ground station as much as possible. This shall be achieved by autonomous navigation and autonomous decision making, so that it can determine optimal trajectories during flight and potential target asteroids autonomously for mining. The autonomy of the spacecraft is based on cognitive and biology-inspired algorithms. Assessment of these algorithms is necessary before they are applied in real scenarios. Therefore, algorithms have to be tested in a virtual environment with different virtual scenarios. This virtual environment should simulate motion of planets and asteroids, gravity, solar pressure, sensors of spacecraft, features of the asteroid, collision detection between asteroid and spacecraft for landing, etc. in real-time. In order to interact with this virtual environment, different 3D interaction metaphors have to be defined so that the user can change physical parameters, visualize different data, create different mission scenarios, change the spacecraft parameters, and even create new asteroid clusters and shapes (generated via 3D procedural modelling), which is necessary as the spacecraft might encounter new unknown asteroids.

Published in:

24th International Conference on Artificial Reality and Telexistence (ICAT-EGVE 2014), Bremen, Germany, December 8 - 10, 2014. [BibTex]

Files:

     Paper
     Poster


Massively-Parallel Proximity Queries for Point Clouds

Max Kaluschke, Uwe Zimmermann, Marinus Danzer, Gabriel Zachmann and Rene Weller

We present a novel massively-parallel algorithm that allows real-time distance computations between arbitrary 3D objects and unstructured point cloud data. Our main application scenario is collision avoidance for robots in highly dynamic environments that are recorded via a Kinect, but our algorithm can be easily generalized for other applications such as virtual reality. Basically, we represent the 3D object by a bounding volume hierarchy, therefore we adopted the Inner Sphere Trees data structure, and we process all points of the point cloud in parallel using GPU optimized traversal algorithms. Additionally, all parallel threads share a common upper bound in the minimum distance, this leads to a very high culling efficiency. We implemented our algorithm using CUDA and the results show a real-time performance for online captured point clouds. Our algorithm outperforms previous CPU-based approaches by more than an order of magnitude.

Published in:

11th Workshop on Virtual Reality Interaction and Physical Simulation VRIPHYS (2014), Bremen, Germany, September 24 - 25, 2014. [BibTex]

Files:

     Paper
     Slides


Massively Parallel Batch Neural Gas for Bounding Volume Hierarchy Construction

Rene Weller, David Mainzer, Abhishek Srinivas, Matthias Teschner and Gabriel Zachmann

Ordinary bounding volume hierarchy (BVH) construction algorithms create BVHs that approximate the boundary of the objects. In this paper, we present a BVH construction that instead approximates the volume of the objects with successively finer levels. It is based on Batch Neural Gas (BNG), a clustering algorithm that is known from machine learning. Additionally, we present a novel massively parallel version of this BNG-based hierarchy construction that runs completely on the GPU. It reduces the theoretical complexity of the sequential algorithm from O(nlogn) to O(log2 n) and also our CUDA implementation outperforms the CPU version significantly in practice.

Published in:

11th Workshop on Virtual Reality Interaction and Physical Simulation VRIPHYS (2014), Bremen, Germany, September 24 - 25, 2014. [BibTex]

Files:

     Paper
     Slides


A Framework for Wait-Free Data Exchange in Massively Threaded VR Systems

Patrick Lange, Rene Weller, Gabriel Zachmann

A central part of virtual reality systems and game engines is the generation, management and distribution of all relevant world states. In modern interactive graphic software systems usually many independent software components need to communicate and exchange data. Standard approaches suffer the n2 problem because the number of interfaces grows quadratically with the number of component functionalities. Such many-to-many architectures quickly become unmaintainable, not to mention latencies of standard concurrency control mechanisms. We present a novel method to manage concurrent multithreaded access to shared data in virtual environments. Our highly efficient low-latency and lightweight architecture is based on a new wait-free hash map using key-value pairs. This allows us to reduce the traditional many-to-many problem to a simple many-to-one approach. Our results show that our framework outperforms by more than two orders of magnitude standard lock-based but also modern lock-free methods significantly.

Published in:

International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision (WSCG)), Plzen, Czech Republic, June 2 - 5, 2014. ISBN 978-80-86943-71-8 [BibTex]

Files:

     Paper
     Slides


Collision Detection Based on Fuzzy Scene Subdivision

David Mainzer, Gabriel Zachmann

We present a novel approach to perform collision detection queries between rigid and/or deformable models. Our method can handle arbitrary de- formations and even discontinuous ones. For this, we subdivide the whole scene with all objects into connected but totally independent parts by a fuzzy clustering algorithm. Following, for every part our algorithm performs a Principal Com- ponent Analyses to achieve the best sweep direction for the Sweep-Plane step, which reduces the number of false positives greatly. Our collision detection algo- rithm processes all computations without the need of a bounding volume hierar- chy or any other acceleration data structure. One great advantage of this is that our method can handle the broad phase as well as the narrow phase within one single framework. Our collision detection algorithm works directly on all prim- itives of the whole scene, which results in a simpler implementation and can be integrated much more easily by other applications. We can compute inter-object and intra-object collisions of rigid and deformable objects consisting of many tens of thousands of triangles in a few milliseconds on a modern computer. We have evaluated its performance by common benchmarks.

Published in:

GPU Computing and Applications, Singapore, 9 Oct 2013, ISBN-13 978-981-287-133-6 [BibTex]

Files:

     Paper
     Slides


Poster: Collision Detection Based on Fuzzy Clustering for Deformable Objects on GPUs (CDFC)

David Mainzer, Gabriel Zachmann

We present a novel Collision Detection Based on Fuzzy Clustering for Deformable Objects on GPUs (CDFC) technique to perform collision queries between rigid and/or deformable models. Our method can handle arbitrary deformations and even discontinuous ones. With our approach, we subdivide the scene into connected but totally independent parts by fuzzy clustering, and therefore, the algorithm is especially well-suited to GPU's. Our collision detection algorithm processes all computations without the need of a bounding volume hierarchy or any other acceleration data structure. One great advantage of this is that our method can handle the broad phase as well as the narrow phase within one single framework. We can compute inter-object and intra-object collisions of rigid and deformable objects consisting of many tens of thousands of triangles in a few milliseconds on a modern computer. We have evaluated its performance by common benchmarks. In practice, our approach is faster than earlier CPU- and/or GPU-based approaches and as fast as state-of-the-art techniques but even more scalable.

Published in:

International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision (WSCG) - POSTER Proceedings, Plzen, Czech Republic, June 24 - 27, 2013. ISBN 978-80-86943-76-3 [BibTex]

Files:

     Paper
     Poster


Fast Sphere Packings with Adaptive Grids on the GPU

Jörn Teuber, Rene Weller, Gabriel Zachmann, Stefan Guthe

Polydisperse sphere packings are a new and very promising data representation for several fundamental problems in computer graphics and VR such as collision detection and deformable object simulation. In this paper we present acceleration techniques to compute such sphere packings for arbitrary 3D objects efficiently on the GPU. To do that, we apply different refinement methods for adaptive grids. Our results show a significant speed-up compared to existing approaches.

Published in:

GI VR/AR 2013 (X. Workshop der GI-Fachgruppe VR/AR) Second Place for Best Paper Award [BibTex]

Files:

     Paper
     Slides
     Video


A Methodology for Interactive Spatial Visualization of Automotive Function Architectures for Development and Maintenance

Moritz Cohrs, Stefan Klimke, Gabriel Zachmann

In this paper, we utilize spatial visualization of automotive function architectures to enable novel, improved methodologies and workflows for the development, validation and service of vehicle functions. We build upon our prior approach for consistent data integration of automotive function architectures with CAD models. We show the benefits of the proposed novel methodologies by applying them to the scenario of developing an auto-motive signal light system. This demonstrates the capabilities of our new methodology in making a function-oriented development much more efficient as well as supporting testing and service of vehicle functions.

Published in:

9th International Symposium, ISVC 2013 (International Symposium on Visual Computing), Rethymnon, Crete, Greece, July 29-31, 2013. Proceedings, Part II, George Bebis et al. in: Advances in Visual Computing, Springer, ISBN 978-3-642-41938-6 [BibTex]

Files:

     Paper
     Slides


Streamlining Function-oriented Development by Consistent Integration of Automotive Function Architectures with CAD Models

Moritz Cohrs, Stefan Klimke, Gabriel Zachmann

A primary challenge in the automotive industry is the increasing complexity of modern cars caused by the high amount of vehicle electronics respectively vehicle functions which are implemented as mechatronic systems. A promising solution is the relatively new function-oriented development approach that focuses on the interdisciplinary development of such functions and which helps to handle the high complexity in automotive development. At this stage, however, a function-oriented development does not fully exploit the capabilities of virtual technologies which are fairly well-established technologies in the automotive product development. One reason in particular is that function-oriented data is not yet integrated with geometric CAD data. Our main contributions begin with an analysis of the data structures of function architecture data and CAD data and they provide a definition of the requirements for a consistent mapping of named data structures. Moreover, we develop a meta-format that enables a system-independent description and exchange of function architectures. In addition, we carry out a prototypical implementation that shows the applicability of the proposed data integration approach and we derive new methods that can assist a function-oriented development. Finally, we evaluate these methods by means of actual use cases. Summarizing, our research focuses on the interdisciplinary integration of function architectures with CAD models to create synergies and to enable new, beneficial methods for the spatial visualization and utilization of such data.

Published in:

Computer-Aided Design and Applications, CAD 2013, 2014 [BibTex]

Files:

     Paper


PhD thesis: Model-Based High-Dimensional Pose Estimation with Application to Hand Tracking

Daniel Mohr

This thesis presents several novel techniques for computer vision based full-DOF human hand motion estimation. The most important contributions are a novel resolution-independent and memory efficient representation of hand pose silhouettes that allows to match a hypothesis in near-constant time, a new class of similarity measures that work for nearly arbitrary input modalities, and a novel matching approach that naturally combines a novel template hierarchy with a new image space search method.

Published in:

Staats- und Universitätsbibliothek Bremen, Bremen, 2012, [BibTex]

Files:

     PhD thesis


New Geometric Data Structures for Collision Detection

Rene Weller

The PhD thesis of Rene Weller, including kinetic collision detection, Protosphere, Inner Sphere Trees, Sphere-Spring-Systems, benchmarking of collision detection algorithms and applications to haptics and robotics.

Published in:

Extended Version: Springer Series on Touch and Haptic Systems , 2013, ISBN 978-3-319-01020-5, [BibTex]
Original Version: Staats- und Universitätsbibliothek Bremen
, 2012, [BibTex]

Files:

     Flyer
     Paper


User Performance in Complex Bi-manual Haptic Manipulation with 3 DOFs vs. 6 DOFs

Rene Weller, Gabriel Zachmann

We present the results of a comprehensive user study that evaluates the influence of the degrees of freedom on the users' performance in complex bi-manual haptic interaction tasks. To do that, we have developed a novel multi-player game that allows the qualitative as well as the quantitative evaluation of different force-feedback devices simultaneously. The game closely resembles typical tasks arising in tele-operation scenarios or virtual assembly simulations; thus, the results of our user study apply directly to real-world industrial applications. The game is based on our new haptic workspace that supports high fidelity, two-handed multi-user interactions in scenarios containing a large number of dynamically simulated rigid objects; moreover, it works independent of the objects' polygon count. The results of our user study show that 6 DOF forcefeedback devices outperform 3 DOF devices significantly, both in user perception and in user performance.

Published in:

Haptics Symposium 2012 , Vancouver, Canada, March 2012, [BibTex]

Files:

     Paper
     Poster
     Eyecatcher
     Teaser Best Teaser Award

Links:

     Project Homepage


A Comparative Evaluation of Three Skin Color Detection Approaches

Dennis Jensch, Daniel Mohr and Gabriel Zachmann

Skin segmentation is a challenging task due to several influences such as, for example, unknown lighting conditions, skin colored background, and camera limitations. A lot of skin segmentation approaches were proposed in the past including adaptive (in the sense of updating the skin color online) and non-adaptive approaches. In this paper, we compare three different skin segmentation approaches. The first is a well-known non- adaptive approach. It is based on a simple, pre-computed skin color distribution. Methods two and three adaptively estimate the skin color in each frame utilizing clustering algorithms. The second approach uses a hierarchical clustering for a simultaneous image and color space segmentation, while the third approach is a pure color space clustering, but with a more sophisticated clustering approach.

For evaluation, we compared the segmentation results of the approaches against a ground truth dataset. To obtain the ground truth dataset, we labeled about 500 images captured under various conditions.

Published in:

GI AR/VR Workshop 2012 , Germany, Düsseldorf, [BibTex]

Extended vesion in Journal of Virtual Reality and Broadcasting, vol 12, no 1, 2015. [BibTex]

Files:

     Paper
     Slides [pptx] Slides [pdf]

Links:

     Project Homepage


Segmentation-Free, Area-Based Articulated Object Tracking

Daniel Mohr, Gabriel Zachmann

We propose a novel, model-based approach for articulated object detection and pose estimation that does not need any low-level feature extraction or foreground segmentation and thus eliminates this error-prone step. Our approach works directly on the input color image and is based on a new kind of divergence of the color distribution between an object hypothesis and its background. Consequently, we get a color distribution of the target object for free.

We further propose a coarse-to-fine and hierarchical algorithm for fast object localization and pose estimation. Our approach works significantly better than segmentation-based approaches in cases where the segmen- tation is noisy or fails, e.g. scenes with skin-colored backgrounds or bad illumination that distorts the skin color.

We also present results by applying our novel approach to markerless hand tracking.

Published in:

7th International Symposium on Visual Computing (ISVC) 2011 , Las Vegas, NV, USA, [BibTex]

Files:

     Paper
     Slides [pptx] Slides [pdf]
     Example Video: avi, mov

Links:

     Project Homepage


Adaptive Bitonic Sorting

Gabriel Zachmann

Adaptive bitonic sorting is a sorting algorithm suitable for implementation on EREW parallel architectures. Similar to bitonic sorting, it is based on merging, which is recursively applied to obtain a sorted sequence. In contrast to bitonic sorting, it is data-dependent. Adaptive bitonic merging can be performed in O(n/p) parallel time, p being the number of processors, and executes only O(n) operations in total. Consequently, adaptive bitonic sorting can be performed in O(n log n / p) time, which is optimal. So, one of its advantages is that it executes a factor of O(log n) less operations than bitonic sorting. Another advantage is that it can be implemented efficiently on modern GPUs.

Published in:

Encyclopedia of Parallel Computing, Springer, 2011, pages 146-157; Padua, David (ed.), ISBN 978-0-387-09765-7 [BibTex]


3-DOF vs. 6-DOF - Playful Evaluation of Complex Haptic Interactions

Rene Weller, Gabriel Zachmann

We present a haptic workspace that allows high fidelity two-handed multi-user interactions in scenarios containing a large number of dynamically simulated rigid objects and a polygon count that is only limited by the capabilities of the graphics card. Based in this workspace we present a novel multiplayer game that supports qualitative as well as quantitative evaluation of different haptic devices in demanding haptic interaction tasks.

Published in:

IEEE International Conference on Consumer Electronics (ICCE) 2011 , Las Vegas, NV, USA, [BibTex]

Files:

     Paper
     Slides [pptx]
     Video from Talk: wmv, mov

Links:

     Project Homepage


Inner Sphere Trees and Their Application to Collision Detection

Rene Weller, Gabriel Zachmann

Collision detection between rigid objects plays an important role in many fields of robotics and computer graphics, e.g. for path-planning, haptics, physically-based simulations, and medical applications.

This chapter contributes the following novel ideas to the area of collision detection:

Published in:

Virtual Realities, Springer, 2011, pages 181-202, Sabine Coquillart and Guido Brunnett and Greg Welch, (ed.) ISBN 978-3-211-99177-0 (Dagstuhl Seminar) [BibTex]

Links:

     Project Homepage


ProtoSphere: A GPU-Assisted Prototype Guided Sphere Packing Algorithm for Arbitrary Objects

Rene Weller, Gabriel Zachmann

We present a new algorithm that is able to efficiently compute a space filling sphere packing for arbitrary objects. It is independent of the object's representation (polygonal, NURBS, CSG,...); the only precondition is that it must be possible to compute the distance from any point to the surface of the object. Moreover, our algorithm is not restricted to 3D but can be easily extended to higher dimensions.

The basic idea is very simple and related to prototype based approaches known from machine learning. This approach directly leads to a parallel algorithm that we have implemented using CUDA. As a byproduct, our algorithm yields an approximation of the object's medial axis that has applications ranging from path-planning to surface reconstruction.

Published in:

Siggraph Asia, Technical Sketches, 2010, Seoul, Republic of Korea [BibTex]

Files:

     Paper
     Slides [pptx]
     Video 1 from Talk: wmv, mov
     Video 2 from Talk: wmv, mov
     Video 3 from Talk: wmv, mov
     Video 4 from Talk: wmv, mov
     Video 5 from Talk: wmv, mov
     Video 6 from Talk: wmv, mov

Links:

     Project Homepage


A Benchmarking Suite for 6-DOF Real Time Collision Response Algorithms

Rene Weller, David Mainzer, Gabriel Zachmann, Mikel Sagardia, Thomas Hulin, Carsten Preusche

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.

Our device-independent approach allows objective predictions for physically-based simulations as well as 6-DOF haptic rendering scenarios. In the results, we show a comprehensive example application of our benchmarks comparing two quite different algorithms utilizing our proposed benchmarking suite. This proves empirically that our methodology can become a standard evaluation framework.

Published in:

Proceedings of the 17th ACM Symposium on Virtual Reality Software and Technology 2010 (VRST' 2010), Hong Kong, November 2010. [BibTex]

Files:

     Paper
     Slides

Links:

     Project Homepage


FAST: Fast Adaptive Silhouette Area based Template Matching

Daniel Mohr, Gabriel Zachmann

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. %This is a consistent continuation of our adaptive approach.

With the template hierarchy, the complexity of our matching method for n templates is O(log n) 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.

Published in:

British Machine Vision Conference 2010 [BibTex]

Files:

     Paper
     Poster
     Example Video avi, mov

Links:

     Project Homepage


Silhouette Area Based Similarity Measure for Template Matching in Constant Time

Daniel Mohr, Gabriel Zachmann

We present a novel, fast, resolution-independent silhouette area-based matching approach. We approximate the silhouette area by a small set of axis-aligned rectangles. This yields a very memory efficient representation of templates. In addition, utilizing the integral image, we can thus compare a silhouette with an input image at an arbitrary position in constant time.

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(log n). For example, we can match a hierarchy consisting of 1000 templates in 1.5 ms. Overall, our contribution constitutes an important piece in the initialization stage of any tracker of (articulated) objects.

Published in:

6th International Conference of Articulated Motion and Deformable Objects , 2010 [BibTex]

The original publication is available at Springer Verlag

Files:

     Paper Erratum: Eq. 5 does not take into account all rectangle configurations, i.e. we do not obtain the minimum number of rectangles for all areas.
     Slides
     Example Video avi, mov

Links:

     Project Homepage


Collision Detection: A Fundamental Technology for Virtual Prototyping

in: Virtual Technologies for Business and Industrial Applications, by N. Raghavendra Rao (ed.); IGI Global, 2010, ch. 3, pp. 36-67.

Published in:

Collision Detection: A Fundamental Technology for Virtual Prototyping, 2010 [BibTex]


Stable 6-DOF Haptic Rendering with Inner Sphere Trees

Rene Weller, Gabriel Zachmann

Based on our new geometric data structure, the inner sphere trees, we present a fast and stable uniform algorithm for proximity and penetration volume queries between watertight objects at haptic rates.

Moreover, we present a multi-threaded version of the penetration volume computation for time-critical haptic rendering that is based on separation lists and the novel notion of expected overlapping volumes. Finally, we show how to use the penetration volume to compute continuous contact forces and torques that enable a stable rendering of 6-DOF penalty-based distributed contacts.

Published in:

Proceedings of International Design Engineering Technical Conferences & Computers and Information in Engineering Conference (IDETC/CIE) , San Diego, USA, 30 August - 02 September 2009. Virtual Environments and Systems - 2009 Best Paper Award. [BibTex]

Files:

     Slides
     Simulation Video wmv, mov
     Interaction Video wmv, mov
     Bones Video wmv, mov
     758 Video wmv, mov
     Pin in Hole Benchmark Video wmv, mov

Links:

     Project Homepage


Visual Computing for Medical Diagnosis and Treatment

Jan Klein, Ola Friman, Markus Hadwiger, Bernhard Preim, Felix Ritter, Anna Vilanova, Gabriel Zachmann, Dirk Bartz

Diagnostic algorithms and efficient visualization techniques are of major importance for pre-operative decisions, intra-operative imaging and image-guided surgery. Complex diagnostic decisions are characterized by a high information flow and fast decisions, requiring efficient and intuitive presentation of complex medical data and precision in the visualization. For intra-operative medical treatment, the pre-operative visualization results of the diagnostic systems have to be transferred to the patient on the operation room table. Via augmented reality, additional information of the hidden regions can be displayed virtually. This state-of-the-art report summarizes visual computing algorithms for medical diagnosis and treatment. After starting with direct volume rendering and tagged volume rendering as general techniques for visualizing anatomical structures, we go into more detail by focusing on the visualization of tissue and vessel structures. Afterwards, algorithms and techniques that are used for medical treatment in the context of image-guided surgery, intra-operative imaging and augmented reality, are discussed and reviewed.

Published in:

Computers & Graphics, Vol. 33, Issue 4, August 2009, pp. 554 -- 565. [BibTex]

Files:

      Preliminary version of the paper


A Unified Approach for Physically-Based Simulations and Haptic Rendering

Rene Weller, Gabriel Zachmann

Since the visual feedback and effects of today's games have become extremely mature, it will be more and more important for games to provide realistic feedback to other senses, such as our haptic sense. On the hardware side, this has become possible in recent years by the advent of first inexpensive haptic devices on the consumer market, such as the Falcon from Novint. Research on force-feedback devices and algorithms has been done over 10 years, and has only fairly recently been introduced to games.

However, while there is a large body of research on how to render forces given a collision and its contact information, the computation of the latter for massive models is still a challenge. First of all, this is due to the much higher effort to compute contact information. Second, this is due to the update rates that are necessary for haptic rendering, which need to be much higher than for visual rendering, i.e., 250-1000 Hz. And third, defining the contact information such that continuous contact forces can be derived is not always obvious.

Therefore, one of the major challenges in haptic rendering for games is the computation of continuous forces at haptic rates. A solution to this challenge can also be utilized to do physically-based simulation of rigid bodies, which has become increasingly popular in games over the past few years.

In this paper, we take advantage of the fact that in rendering haptic forces, as well as in most real-time applications that involve physically-based simulation, an absolutely correct determination of the forces acting on the virtual objects is not necessary.

Published in:

ACM SIGGRAPH Video Game Proceedings , New Orleans, USA, August 2009. [BibTex]

Files:

     Paper
     Slides
     Simulation Video wmv, mov
     Interaction Video wmv, mov
     Armadillo Video wmv, mov
     Screwdriver Video wmv, mov
     Bozzle Video wmv, mov

Links:

     Project Homepage


Inner Sphere Trees for Proximity and Penetration Queries

Rene Weller, Gabriel Zachmann

We present a novel geometric data structure for approximate collision detection at haptic rates between rigid objects. Our data structure, which we call inner sphere trees, supports different kinds of queries, namely, proximity queries and a new method for interpenetration computation, the penetration volume, which is related to the water displacement of the overlapping region and, thus, corresponds to a physically motivated force. The main idea is to bound objects from the inside with a set of non-overlapping spheres. Based on such sphere packings, a "inner bounding volume hierarchy" can be constructed. In order to do so, we propose to use an AI clustering algorithm, which we extend and adapt here. The results show performance at haptic rates both for proximity and penetration volume queries for models consisting of hundreds of thousands of polygons.

Published in:

2009 Robotics: Science and Systems Conference (RSS) , Seattle, USA, 28 June - 01 July 2009. [BibTex]

Files:

     Paper
     Poster
     Technical Report, [BibTex]

Links:

     Project Homepage


Continuous Edge Gradient-Based Template Matching for Articulated Objects

Gabriel Zachmann, Daniel Mohr

In this paper, we propose a novel edge gradient based template matching method for object detection. In contrast to other methods, ours does not perform any binarization or discretization during the online matching. This is facilitated by a new continuous edge gradient similarity measure. Its main components are a novel edge gradient operator, which is applied to query and template images, and the formulation as a convolution, which can be computed very efficiently in Fourier space.

Published

International Conference on Computer Vision Theory and Applications (VISAPP) , Lisbon, Portugal, 05-09 February 2009. [BibTex]

Files:

     Paper
     Slides
     Technical Report
     Video 1divx,   Video 2divx,  Video 3divx

Links:

     Project Homepage


Segmentation of Distinct Homogeneous Color Regions in Images

Gabriel Zachmann, Daniel Mohr

In this paper, we present a novel algorithm to detect homogeneous color regions in images with application to skin segmentation.

Published

The 12th International Conference on Computer Analysis of Images and Patterns (CAIP), Vienna, Austria, 27-29 August 2007. [BibTex]

Files:

     Paper
     Slides
     Video (divx)
     Video (mov)

Links:

     Project Homepage


IEEE VR2007 Workshop on "Trends and Issues in Tracking for Virtual Environments"

Gabriel Zachmann (ed.)

The goal of this half-day workshop is to bring together researchers and industry working in the area of tracking and to talk about making tracking actually work. To that end, the workshop is to provide a broad picture of what is the current state of the art, what are the various technologies available, and what are issues for further research and development

Published

February 2007, Shaker Verlag, Aachen, Germany, ISBN 978-3-8322-5967-9 [BibTeX]

Files:

     Home page of the Workshop
     Buy a copy of the the workshop proceedings online (hard-copy for 25€; electronic version for 3€) from the publisher
     You can also ask me at zach at informatik.uni-bremen.de -- I've still got some copies for sale, left over from the conference ;-)


A Benchmarking Suite for Static Collision Detection Algorithms

Sven Trenkel, René Weller, Gabriel Zachmann

In this paper, we present a benchmarking suite that allows a systematic comparison of pairwise static collision detection algorithms for rigid objects. The pdf-file contains a slightly extended version of the original published paper.

Published

International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision (WSCG), Plzen, Czech Republic, January 29 - February 1, 2007. [BibTex]

Files:

     Paper
     Slides
     Video of configuration generation avi, mov

For further information please visit our project homepage.


Kinetic Separation Lists for Continuous Collision Detection of Deformable Objects

Gabriel Zachmann, René Weller

In this paper, we present a new acceleration scheme for continuous inter- and intra-collision detection of deformable objects. The pdf-file contains a slightly extended version of the original published paper (Section 6.2).

Published

Third Workshop in Virtual Reality Interactions and Physical Simulation (Vriphys), Madrid, Spain, 6/7 November 2006. [BibTex]

Files:

     Paper
     Slides


Kinetic Bounding Volume Hierarchies for Collision Detection of Deformable Objects

Gabriel Zachmann, René Weller

In this paper, we present novel algorithms for updating bounding volume hierarchies of objects undergoing arbitrary deformations.

Published

ACM Int'l Conf. on Virtual Reality Continuum and Its Applications (VRCIA), Hong Kong, China, 14-17 June 2006. [BibTex]

Files:

     Paper
     Slides
     Technical Report


A Model for the Expected Running Time of Collision Detection using AABB Trees

René Weller, Jan Klein, Gabriel Zachmann

In this paper, we propose a model to estimate the expected running time of hierarchical collision detection that utilizes AABB trees, which are a frequently used type of bounding volume (BV).

Published

12th Eurographics Symposium on Virtual Environments (EGVE), Lisbon, Portugal, 8-10 May 2006. [BibTex]

Files:

     Paper (on-screen version)
     Paper (print version)
     Slides


Book: Geometric Data Structures for Computer Graphics

Elmar Langetepe, Gabriel Zachmann, AK Peters, 2006

Links

Buy from the publisher or from Amazon [BibTex]


GPU-ABiSort: Optimal Parallel Sorting on Stream Architectures

Alexander Greß, Gabriel Zachmann

In this paper, we present a novel approach for parallel sorting on stream processing architectures.

Published

Proc. 20th IEEE International Parallel and Distributed Processing Symposium (IPDPS), Rhodes Island, Greece, 25-29 April 2006. [BibTex]

Files:

     Paper
     Technical Report


Space-Efficient FPGA-Accelerated Collision Detection for Virtual Prototyping

Andreas Raabe, Stefan Hochgürtel, Gabriel Zachmann, Joachim K. Anlauf

In this paper, we present a space-efficient, FPGA-optimized architecture to detect collisions among virtual objects, as well as simulation results for collision queries using this architecture.

Published

Design Automation and Test in Europe (DATE), Munich, Germany, 6-10 March 2006. [BibTex]

Files:

     Paper
     Slides


Hardware-Accelerated Collision Detection using Bounded-Error Fixed-Point Arithmetic

Andreas Raabe, Stefan Hochgürtel, Gabriel Zachmann, Joachim K. Anlauf

In this paper, we present a novel approach for highly space-efficient hardware-accelerated collision detection.

Published

Hardware-Accelerated Collision Detection using Bounded-Error Fixed-Point Arithmetic, 2006 [BibTex]

Files:

     Paper
     Slides


Patent on Collision Detection

Gabriel Zachmann

The present invention relates to a process and a device for the collision detection of objects by traversal of hierarchical binary bounding BoxTrees, in which each bounding box pair of a hierarchically lower level is derived from a bounding box from the immediately above level by means of cutting off two sub-volumes by means of two parallel cut-planes. For the collision detection of a first and second object, for each second bounding box of the bounding BoxTree of the second object to be checked for overlapping with a first bounding box of the bounding BoxTree of the first object, an auxiliary bounding box is computed which is axis-aligned in the object coordinate system of the first object and encloses the second bounding box with minimal volume, and with which the overlap check is conducted instead of with the second bounding box, and the computation results from the level immediately above are utilized for computation of auxiliary bounding boxes of lower levels. The process makes quick collision detection possible with low memory requirements.

Published

Patent for "Process and Device for Collision Detection of Objects", 2005 [BibTex]

Links:

     first page
     US Patent


The Expected Running Time of Hierarchical Collision Detection

Jan Klein, Gabriel Zachmann

We propose a theoretical approach to analyze the average-case running time of hierarchical collision detection that utilizes bounding volume hierarchies.

Published

SIGGRAPH 2005, Poster, Los Angeles, CA, USA, August 2005. [BibTex]

Files:

     Poster
     One-Page Summary.
     Supplemental Material
     Slides


Hardware Accelerated Collision Detection --- An Architecture and Simulation Results

Andreas Raabe and Stefan Hochgärtel and Gabriel Zachmann and Joachim K. Anlauf

A novel approach for highly space-efficient hardware-accelerated collision detection is presented. This paper focuses on the architecture to traverse bounding volume hierarchies in hardware. It is based on a novel algorithm for testing discretely oriented polytopes (DOPs) for overlap, tilizing only fixed-point (i.e., integer) arithmetic. We derive a bound on the deviation from the mathematically correct result and give formal proof that no false negatives are produced. Simulation results show that real-time collision detection of complex objects at rates required by force-feedback and physically-based simulations can be obtained. In addition, synthesis results prove the architecture to be highly space efficient. We compare our FPGA-optimized design with a fully parallelized ASIC-targeted architecture and a software implementation.

Published

Hardware-Accelerated Collision Detection using Bounded-Error Fixed-Point Arithmetic, 2006 [BibTex]

Files:

     Paper
     Slides


Collision Detection for Deformable Objects

M. Teschner, S. Kimmerle, B. Heidelberger, G. Zachmann, L. Raghupathi, A. Fuhrmann, M.-P. Cani, F. Faure, N. Magnenat-Thalmann, W. Strasser, P. Volino

This paper focusses on collision detection for deformable objects 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. Further, image-space techniques and stochastic methods are considered. Applications in cloth modeling and surgical simulation are presented.

Published

Collision Detection for Deformable Objects [BibTex]

Files:

     Paper
     Paper
     Slides


Interpolation Search for Point Cloud Intersection

Jan Klein, Gabriel Zachmann

We present a novel algorithm to compute intersections of two point clouds. It can be used to detect collisions between implicit surfaces defined by two point sets, or to construct their intersection curves. Our approach utilizes a proximity graph that allows for quick interpolation search of a common zero of the two implicit functions. First, pairs of points from one point set are constructed, bracketing the intersection with the other surface. Second, an inter- polation search along shortest paths in the graph is performed. Third, the solutions are refined. For the first and third step, randomized sampling is utilized.
We show that the number of evaluations of the implicit function and the overall runtime is in O(loglogN) in the average case, where N is the point cloud size. The storage is bounded by O(N).
Our measurements show that we achieve a speedup by an order of magnitude compared to a recently proposed randomized sampling technique for point cloud collision detection.

Published

Interpolation Search for Point Cloud Intersection [BibTex]

Files:

     Paper (print-version)
     Paper (onscreen-version)
     Slides


Shader Maker

Markus Kramer, Rene Weller, Gabriel Zachmann

Actually, this is not a regular publication, but a software release.

Shader Maker is a simple, cross-platform GLSL editor. It works on Windows, Linux, and Mac OS X.

It provides the basics of a shader editor, such that students can get started with writing their own shaders as quickly as possible. This includes: syntax highlighting in the GLSL editors; geometry shader editor (as well as vertex and fragment shader editors, of course); interactive editing of the uniform variables; light source parameters; pre-defined simple shapes (e.g., torus et al.) and a simple OBJ loader; and a few more.

For download and further information please visit our project website


Hardware-Accelerated Ambient Occlusion Computation

M. Sattler and R. Sarlette and G. Zachmann and R. Klein

In this paper, we present a novel, hardware-accelerated approach to compute the visibility between surface points and directional light sources.
Thus, our method provides a first-order approximation of the rendering equation in graphics hardware. This is done by accumulating depth tests of vertex fragments as seen from a number of light directions. Our method does not need any preprocessing of the scene elements and introduces no memory overhead.
Besides of the handling of large polygonal models, it is suitable for deformable or animated objects under time-varying high-dynamic range illumination at interactive frame rates.

Published in:

Hardware-Accelerated Ambient Occlusion Computation [BibTex]

Files:

     Paper
     Video


Collision Detection for Deformable Objects

M. Teschner and S. Kimmerle and B. Heidelberger and G. Zachmann and L. Raghupathi and A. Fuhrmann and M.-P. Cani and F. Faure and N. Magnenat-Thalmann and W. Strasser and P. Volino

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 focusses 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. Further, image-space techniques and stochastic methods are considered. Applications in cloth modeling and surgical simulation are presented.

Published in:

Collision Detection for Deformable Objects [BibTex]

Files:

     Paper
     Paper
     Slides


Point Cloud Surfaces using Geometric Proximity Graphs

Jan Klein and Gabriel Zachmann

We present a new definition of an implicit surface over a noisy point cloud, based on the weighted least squares approach. It can be evaluated very fast, but artifacts are significantly reduced.
We propose to use a different kernel function that approximates geodesic distances on the surface by utilizing a geometric proximity graph. From a variety of possibilities, we have examined the Delaunay graph and the sphere-of-influence graph (SIG), for which we propose several extensions.
The proximity graph also allows us to estimate the local sampling density, which we utilize to automatically adapt the bandwidth of the kernel and to detect boundaries. Consequently, our method is able to handle point clouds of varying sampling density without manual tuning.
Our method can be integrated into other surface definitions, such as moving least squares, so that these benefits carry over.

Published in:

Point Cloud Surfaces using Geometric Proximity Graphs [BibTex]

Files:

     Paper


Point Cloud Collision Detection

Jan Klein and Gabriel Zachmann

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.

Published in:

Point Cloud Collision Detection [BibTex]

Files:

     Paper
     Slides


Nice and Fast Implicit Surfaces over Noisy Point Clouds

Jan Klein and Gabriel Zachmann

We propose a new definition of the implicit surface for a noisy point cloud that allows for high-quality reconstruction of the surface in all cases. It is based on proximity graphs that provide a more topology-based measure for p roximity of points. The new definition can be evaluated very fast, but, unlike other definitions based on the weighted least squares approach, it does not suffer from artifacts.

Published in:

Nice and Fast Implicit Surfaces over Noisy Point Clouds [BibTex]

Files:

     Paper
     Slides


Object-Space Interference Detection on Programmable Graphics Hardware

Alexander Gress and Gabriel Zachmann

We present a novel method for checking the intersection of polygonal models on graphics hardware utilizing its SIMD, occlusion query, and floating point texture capabilities. It consists of two stages: traversal of bounding volume hierarchies, thus quickly determining potentially intersecting sets of polygons, and the actual intersection tests, resulting in lists of intersecting polygons. Unlike previous methods, our method does all computations in object space and does not make any requirements on connectivity or topology.

Published in:

Object-Space Interference Detection on Programmable Graphics Hardware [BibTex]

Files:

     Paper

Link:

     Paper and Slides from the GD'03 conference.


Proximity Graphs for Defining Surfaces over Point Clouds

Jan Klein and Gabriel Zachmann

We present a new definition of an implicit surface over a noisy point cloud. It can be evaluated very fast, but, unlike other definitions based on the moving least squares approach, it does not suffer from artifacts. In order to achieve robustness, we propose to use a different kernel function that approximates geodesic distances on the surface by utilizing a geometric proximity graph. The starting point in the graph is determined by approximate nearest neighbor search. From a variety of possibilities, we have examined the Delaunay graph and the sphere-of-influence graph (SIG). For both, we propose to use modifications, the r-SIG and the pruned Delaunay graph. We have implemented our new surface definition as well as a test environment which allows to visualize and to evaluate the quality of the surfaces. We have evaluated the different surfaces induced by different proximity graphs. The results show that artifacts and the root mean square error are significantly reduced.

Published in:

Proximity Graphs for Defining Surfaces over Point Clouds [BibTex]

Files:

     Paper
     Slides


Visual-fidelity dataglove calibration

Ferenc Kahlesz and Gabriel Zachmann and Reinhard Klein

This paper presents a novel calibration method for datagloves with many degrees of freedom (Gloves that measure at least 2 flexes per finger plus abduction/adduction, eg. Immersion's Cyberglove). 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.

Published in:

Visual-fidelity dataglove calibration [BibTex]

Files:

     Paper
     Slides


Consistent Normal Orientation for Polygonal Meshes

Pavel Borodin and Gabriel Zachmann and Reinhard Klein

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.

Published in:

Consistent Normal Orientation for Polygonal Meshes [BibTex]

Files:

     Paper
     Slides


ADB-Trees: Controlling the Error of Time-Critical Collision Detection

Jan Klein and Gabriel Zachmann

We present a novel framework for hierarchical collision detection that can be applied to virtually all bounding volume (BV) hierarchies. It allows an application to trade quality for speed. Our algorithm yields an estimation of the quality, so that applications can specify the desired quality. In a time-critical system, applications can specify the maximum time budget instead, and quantitatively assess the quality of the results returned by the collision detection afterwards.
Our framework stores various characteristics about the average distribution of the set of polygons with each node in a BV hierarchy, taking only minimal additional memory footprint and construction time. We call such augmented BV hierarchies average-distribution tree or ADB-trees.
We have implemented our new approach by augmenting AABB trees 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.

Published in:

ADB-Trees: Controlling the Error of Time-Critical Collision Detection [BibTex]

Files:

     Paper
     Slides
     Movie
     Movie (another version)


Object-Space Interference Detection on Programmable Graphics Hardware

Alexander Gress and Gabriel Zachmann

We present a novel method for checking the intersection of polygonal models on current graphics accelerator boards (GPU). All SIMD computations are performed on the GPU using vertex and fragment programs. The result is either the list of intersecting polygons, or just its length; the former can be read back to the CPU by a texture, while the latter is fed back using the occlusion counter.
Our approach consists of two stages: simultaneous traversal of bounding volume hierarchies in order to quickly determine potentially intersecting sets of polygons, and the actual polygon intersection tests in object space. Both stages are mapped on the graphics hardware using floating point textures extensively.
Unlike previous methods, our method does all computations in object space and does not make any requirements on connectivity or topology.

Published in:

Object-Space Interference Detection on Programmable Graphics Hardware [BibTex]

Files:

     Paper
     Slides


Time-Critical Collision Detection Using an Average-Case Approach

Jan Klein and Gabriel Zachmann

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.

Published in:

Time-Critical Collision Detection Using an Average-Case Approach [BibTex]

Files:

     Paper
     Slides
     Movie
The movie shows those bounding volume pairs that have at least one collision cell with probability larger than the predefined threshold. The different colors of the BVs just denote which object they belong to.


High-Performance Collision Detection Hardware

Gabriel Zachmann and Günter Knittel

We present a novel hardware architecture for a single-chip collision detection accelerator and algorithms for efficient hierarchical collision. We use a hierarchy of k-DOPs for maximum performance. A new hierarchy traversal algorithm and an optimized triangle-triangle intersection test reduce bandwidth and computational costs. The resulting hardware architecture can process two object hierarchies and identify intersecting triangles autonomously at high speed. Real-time collision detection of complex objects at rates required by force-feedback and physically-based simulations can be achieved even in worst-case configurations.

Published in:

High-Performance Collision Detection Hardware [BibTex]

Files:

     Paper


An Architecture for Hierarchical Collision Detection

Gabriel Zachmann and Günter Knittel

We present novel algorithms for efficient hierarchical collision detection and propose a hardware architecture for a single-chip accelerator. We use a hierarchy of bounding volumes defined by k-DOPs for maximum performance. A new hierarchy traversal algorithm and an optimized triangle-triangle intersection test reduce bandwidth and computation costs. The resulting hardware architecture can process two object hierarchies and identify intersecting triangles autonomously at high speed. Real-time collision detection of complex objects at rates required by force-feedback and physically-based simulations can be achieved.

Published in:

An Architecture for Hierarchical Collision Detection [BibTex]

Files:

     Paper
     Paper (Extended)
     Slides
     Additional Material


Minimal Hierarchical Collision Detection

Gabriel Zachmann

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 CAD data.

Published in:

Minimal Hierarchical Collision Detection [BibTex]

Files:

     Paper
     Paper (Extended)
     Slides


Natural Interaction in Virtual Environments

Gabriel Zachmann

This paper presents a number of algorithms necessary to achieve natural interaction in virtual environments; by "natural" we understand the use of a virtual hand as naturally as we are used to manipulate our real environment with our real hand. We present algorithms for very fast collision detection, which is a necessary prerequisite for natural interaction. In addition, we describe a framework for preventing object penetrations while still allowing the object's motion in a physically plausible way. Finally, we explain a model for naturally grasping virtual objects without resorting to gesture recognition.

Published

Natural Interaction in Virtual Environments [BibTex]

Files:

     Paper


Natural and Robust Interaction in Virtual Assembly Simulation

Gabriel Zachmann and Alexander Rettig

Virtual assembly simulation is one of the most challenging applications of virtual reality.
Robust and natural interaction techniques to perform the assembly tasks under investigation are essential as well as efficient methods for choosing from a large number of functionalities from inside the virtual environment.
In this paper we present such techniques and methods, in particular multimodal input techniques including speech input and gesture recognition for controlling the system. We address precise positioning by novel approaches for constraining interactive motion of parts and tools, while a new natural grasping algorithm provides intuitive interaction. Finally, sliding contact simulation allows the user to create collision-free assembly paths efficiently.
Preliminary results show that the array of functionality and techniques described in this paper is sufficiently mature so that virtual assembly simulation can be applied in the field.

Published

Natural and Robust Interaction in Virtual Assembly Simulation, California, July, 2001. [BibTex]

Files:

     Paper


Optimizing the Collision Detection Pipeline

Gabriel Zachmann

A general framework for collision detection is presented. Then, we look at each stage and compare different approaches by extensive benchmarks. The results suggest a way to optimize the performance of the overall framework. A benchmarking procedure for comparing algorithms checking a pair of objects is presented and applied to three different hierarchical algorithms. A new convex algorithm is evaluated and compared with other approaches to the neighbor-finding problem.

Published

Optimizing the Collision Detection Pipeline, January, 2001. [BibTex]

Files:

     Paper


Virtual Reality in Assembly Simulation - Collision Detection, Simulation Algorithms, and Interaction Techniques

Gabriel Zachmann (PhD thesis)

This thesis presents frameworks, algorithms, and techniques in order to make the application of virtual reality for virtual prototyping feasible. Virtual assembly simulation is focused on in particular.
The contributions are in the following areas: high-level specification of virtual environments, efficient interaction metaphors and frameworks, real-time collision detection and response, physically-based simulation, tracking, and virtual prototyping application development.
A framework for authoring virtual environments is proposed. The main premise for the proposed framework is that it should be easy for non-computer scientists to author virtual environments. Therefore, the concept of actions, events, inputs, and objects is introduced. These entities can be combined to virtual environments by the event-based approach.
Collision detection is one of the enabling technologies for all kinds of physically-based simulation and for virtual prototyping. This book proposes a collision detection pipeline as a framework for collision detection modules. Subsequently, several algorithms for all stages of the collision detection pipeline are developed and evaluated.
Interaction in virtual environments comprises many different aspects: device handling, processing input data, navigation, interaction paradigms, and physically-based object behavior. For all of them, techniques, frameworks, or algorithms are presented in this book, with a particular emphasis on their application to virtual prototyping.
Finally, virtual prototyping is discussed in general, while the virtual assembly simulation application is described in more detail.
All frameworks and algorithms have been implemented in Fraunhofer-IGD's VR system Virtual Design II, now available from VRCom.

Published

Virtual Reality in Assembly Simulation - Collision Detection, Simulation Algorithms, and Interaction Techniques, Darmstadt, May, 2000. [BibTex]

Files:

     Paper
     Paper (printed book)


Virtual Reality as a Tool for Verification of Assembly and Maintenance Processes

Antonino Gomes de Sá and Gabriel Zachmann

Business process re-engineering is becoming a main focus in today's efforts to overcome problems and deficits in the automotive and aerospace industries (e.g., integration in international markets, product complexity, increasing number of product variants, reduction in product development time and cost). In this paper, we investigate the steps needed to apply virtual reality (VR) for virtual prototyping (VP) to verify assembly and maintenance processes. After a review of today's business process in vehicle prototyping, we discuss CAD-VR data integration and identify new requirements for design quality. We present several new interaction paradigms so that engineers and designers can experiment naturally with the prototype. Finally, a user survey evaluates some of the paradigms and the acceptance and feasibility of virtual prototyping for our key process. The results show that VR will play an important role for VP in the near future.

Published in:

Virtual Reality as a Tool for Verification of Assembly and Maintenance Processes, 1999 [BibTex]

Files:

     Paper


Integrating Virtual Reality for Virtual Prototyping

Antonino Gomes de Sá and Gabriel Zachmann

In order to stay competitive, companies must deliver new products with higher quality in a shorter time. Business process re-engineering is becoming a main focus in today's efforts to overcome problems and deficits in the automotive and aerospace industries (e.g., integration in international markets, product complexity, increasing number of product variants, reduction in product development time and cost). There is some evidence indicating that the assembly process often drives the majority of the cost of a product, and that up to 70% of the total life cycle costs of a product are committed by decisions made in the early stages of the design process. The use of virtual reality for virtual prototyping is still in its infancy. In this paper, we investigate the steps needed to apply virtual reality (VR) for virtual prototyping (VP) to verify assembly and maintenance processes. The final goal of assembly/disassembly verification is the assertion that a part or component can be assembled by a human worker, and that it can be disassembled later-on for service and maintenance. Other questions need to be adressed, too: is it "difficult" to assemble/disassemble a part? How long does it take? How stressful is it in terms of ergonomics? Is there enough room for tools? After a review of today's business process in vehicle prototyping, we discuss CAD-VR data integration and identify new requirements for design data quality. We present several new interaction paradigms so that engineers, designers and skilled mechanical workers can experiment naturally with the virtual prototype. Finally, some results of a user survey performed at BMW are presented, showing the acceptance and potential of VP and the paradigms implemented for this key process. The results show that VR will play an important role for VP in the near future.

Published in:

Integrating Virtual Reality for Virtual Prototyping, Atlanta, Georgia, September, 1998. [BibTex]

Files:

     Paper


Rapid Collision Detection by Dynamically Aligned DOP-Trees

Gabriel Zachmann

Based on a general hierarchical data structure, we present a fast algorithm for exact collision detection of arbitrary polygonal rigid objects. Objects consisting of hundreds of thousands of polygons can be checked for collision at interactive rates. The pre-computed hierarchy is a tree of discrete oriented polytopes (DOPs). An efficient way of re-aligning DOPs during traversal of such trees allows to use simple interval tests for determining overlap between OPs. The data structure is very efficient in terms of memory and construction time. Extensive experiments with synthetic and real-world CAD data have been carried out to analyze the performance and memory usage of the data structure. A comparison with OBB-trees indicates that DOP-trees as efficient in terms of collision query time, and more efficient in memory usage and construction time.

Published in:

Rapid Collision Detection by Dynamically Aligned {DOP}-Trees, Atlanta, Georgia, March, 1998. [BibTex]

Files:

     Paper


VR-Techniques for Industrial Applications

Gabriel Zachmann

This chapter provides some classifications and characterizations of virtual environments, followed by a description of basic and advanced interaction techniques. A framework for describing and authoring virtual environments is proposed, as well as a brief description of the architecture of VR systems. Finally, a solution to magnetic field distortion is given, which is needed for precise interaction and positioning in virtual environments.

Files:

     Paper


Real-time and Exact Collision Detection for Interactive Virtual Prototyping

Gabriel Zachmann

Many companies have started to investigate Virtual Reality as a tool for evaluating digital mock-ups. One of the key functions needed for interactive evaluation is real-time collision detection. An algorithm for exact collision detection is presented which can handle arbitrary non-convex polyhedra efficiently. The approach attains its speed by a hierarchical adaptive space subdivision scheme, the BoxTree, and an associated divide-and-conquer traversal algorithm, which exploits the very special geometry of boxes. The traversal algorithm is generic, so it can be endowed with other semantics operating on polyhedra, e.g., distance computations. The algorithm is fairly simple to implement and it is described in great detail in an ``ftp-able'' appendix to facilitate easy implementation. Pre-com\-pu\-ta\-tion of auxiliary data structures is very simple and fast. The efficiency of the approach is shown by timing results and two real-world digital mock-up scenarios.

Published

Real-time and Exact Collision Detection for Interactive Virtual Prototyping, Sacramento, California, September 1997. [BibTex]

Files:

     Paper


Distortion Correction of Magnetic Fields for Position Tracking

Gabriel Zachmann

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 win 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 suceptibility of a Polhemus and an Ascension tracking system is carried out.

Published

Distortion Correction of Magnetic Fields for Position Tracking, Hasselt/Diepenbeek, Belgium, June, 1997. [BibTex]

Files:

     Paper


A Language for Describing Behavior of and Interaction with Virtual Worlds

Gabriel Zachmann

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.
In this paper, we take the {\em script} based approach to describing virtual environments. We try to identify a generic and complete, yet simple set of functionality, so that non-programmers can readily build their own virtual worlds.

We extend the common object behavior paradigm by the notion of an Action-Event-Object triad.

Published

A Language for Describing Behavior of and Interaction with Virtual Worlds, Hongkong, July, 1996. [BibTex]

Files:

     Paper
     Color Plates


Virtual Prototyping Examples for Automotive Industries

Fan Dai􏰀, Wolfgang Felger􏰀, Thomas Frü􏰁hauf, Martin G􏰁öbel􏰀, Dirk Reiners􏰀, Gabriel Zachmann

The vision of virtual prototyping is to use virtual reality techniques for design evaluations and presentations based on a digital model instead of physical prototypes. In the automotive industries, CAD and CAE systems are widely used. This provides a good basis for virtual prototyping. This vision is therefore extremely interesting for automotive industries. Many companies have started to evaluate existing tools and technologies, and think about, or begin to develop virtual prototyping systems for their own needs.

In this paper, we present some examples from our recent projects with automotive campanies. Based on these examples, we discuss problems, solutions and future directions of R&D to achieve the vision of virtual prototyping.

Published

Virtual Prototyping Examples for Automotive Industries, February, 1996, Stuttgart. [BibTex]

Files:

     Paper


The BoxTree: Exact and Fast Collision Detection of Arbitrary Polyhedra, SIVE95 (First Workshop on Simulation and Interaction in Virtual Environments), University of Iowa, July 1995.

Gabriel Zachmann

An algorithm for exact collision detection is presented which can handle arbitrary non-convex polyhedra efficiently. Despite the wealth of literature, there are not many fast algorithms for this class of objects.

The approach attains its speed by a hierarchical data structure, the BoxTree, and an associated divide-and-conquer traversal algorithm, which exploits the very special geometry of boxes. Boxes were chosen, because they offer much tighter space partitioning than spheres.

The method is generic, so it can be endowed with other semantics operating on polyhedra.

The algorithm is fairly simple to implement and it is described in great detail in an appendix to facilitate easy implementation. The construction of the data structure is very simple and very fast. Timing results show the efficiency of this approach.

Files:

     Paper
     Appendix


Exact and Fast Collision Detection

Gabriel Zachmann (Diploma Thesis)

Collision detection has many di􏰖erent applications􏰞 for example􏰀 in physically based simulation􏰀 where moving objects are simulated􏰒. In order to determine their behav􏰎ior over time􏰀 the most basic information needed is the time and position of collision together with the exact point of collision.􏰒 Only if this information is known exactly􏰀 the collision response can determine how objects will react􏰀 according to their mass􏰀 mass distribution􏰀 velocities,􏰀 etc.

Files:

     Paper