nach oben

2013 | Buch

Kapitel lesen Erstes Kapitel lesen

New Geometric Data Structures for Collision Detection and Haptics

verfasst von: René Weller

Verlag: Springer International Publishing

Buchreihe : Springer Series on Touch and Haptic Systems

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

Starting with novel algorithms for optimally updating bounding volume hierarchies of objects undergoing arbitrary deformations, the author presents a new data structure that allows, for the first time, the computation of the penetration volume. The penetration volume is related to the water displacement of the overlapping region, and thus corresponds to a physically motivated and continuous force. The practicability of the approaches used is shown by realizing new applications in the field of robotics and haptics, including a user study that evaluates the influence of the degrees of freedom in complex haptic interactions. New Geometric Data Structures for Collision Detection and Haptics closes by proposing an open source benchmarking suite that evaluates both the performance and the quality of the collision response in order to guarantee a fair comparison of different collision detection algorithms.

Required in the fields of computer graphics, physically-based simulations, computer animations, robotics and haptics, collision detection is a fundamental problem that arises every time we interact with virtual objects. Some of the open challenges associated with collision detection include the handling of deformable objects, the stable computation of physically-plausible contact information, and the extremely high frequencies that are required for haptic rendering. New Geometric Data Structures for Collision Detection and Haptics presents new solutions to all of these challenges, and will prove to be a valuable resource for researchers and practitioners of collision detection in the haptics, robotics and computer graphics and animation domains.

Inhaltsverzeichnis

Frontmatter

That Was Then, This Is Now

Frontmatter

Chapter 1. Introduction

Abstract

Collision detection is a fundamental technique in each situation where we interact with virtual objects, including computer graphics, robotics and haptics. In many of these applications, the collision detection process is the computational bottleneck. In this chapter, we explain what makes the detection of collisions so complicated and we draft the current open challenges in this field. Moreover, we define the scope of this book and we outline our contributions.

René Weller

Chapter 2. A Brief Overview of Collision Detection

Abstract

Collision detection algorithms has been investigated since decades. Consequently, there already exist a wide spectrum of different approaches. In this chapter, we give a broad overview of classical and recent developments in this field. Moreover, we introduce the typical terminology for collision detection problems and we develop a classification of collision detection algorithms by outlining different parameters.

René Weller

Algorithms and Data Structures

Frontmatter

Chapter 3. Kinetic Data Structures for Collision Detection

Abstract

Deformable objects cause special problems to collision detection algorithms; first, pre-computed data structures like bounding volume hierarchies that are widely used for rigid objects become invalid if the geometry changes. Second, it is possible that parts of one object intersect other parts of the same object, the so-called self-collisions. In this chapter, we present several new algorithms that detect collisions between deformable objects more efficiently than previous approaches. For instance, we prove that our new kinetic AABB-Tree is optimal in the number of updates that is required to restore a bounding volume hierarchy after deformations. Moreover, our kinetic Separation-List can perform both, continuous collision and self-collision queries at interactive rates. Our new methods gain their efficiency from an event-based approach that relies on the framework of kinetic data structures.

René Weller

Chapter 4. Sphere Packings for Arbitrary Objects

Abstract

In this chapter, we present a new algorithm that is able to compute space-filling polydisperse sphere-packings for arbitrary objects. Originally, we developed our algorithms as a means to an end in order to realize our Inner Sphere Trees data structure that is described in the next chapter. Surprisingly, it turns out that the efficient computation of sphere packings for arbitrary objects, but also the algorithm itself, open interesting new ways to solve fundamental problems of computer graphics and beyond. Some ideas for future use are outlined at the end of this chapter.

René Weller

Chapter 5. Inner Sphere Trees

Abstract

In this chapter, we present our novel geometric data structure, the Inner Sphere Trees. It is the first data structure that is able to compute the penetration volume between a pair of colliding objects at haptic rates. This new contact information guarantees physically-plausible and continuous forces and torques for a stable collision response that is essential for stable haptic rendering. Moreover, we propose a new clustering-based algorithm for creating bounding volume hierarchies and a time-critical traversal scheme for time-budgeted collision detection scenarios.

René Weller

Evaluation and Application

Frontmatter

Chapter 6. Evaluation and Analysis of Collision Detection Algorithms

Abstract

A fair comparison of different collision detection approaches is highly non-trivial. Simply stressing the algorithms with worst case scenarios does not reveal their behaviour in real-world applications. For instance, all polygon-based collision detection algorithms show a quadratic running-time for some artificial objects. In this chapter we provide a theoretical average-case analysis for algorithms that are based on axis-aligned bounding boxes. This enables us to prove an almost logarithmic performance for most real-world objects. Moreover, we have developed the first standardized benchmarking suite that includes a broad spectrum of different and interesting contact scenarios. It is able to evaluate both, the performance of different collision detection implementations as well as the quality of the collision response methods.

René Weller

Chapter 7. Applications

Abstract

In this chapter, we present three new applications that we realized using our new data structures from the previous chapters. First, we adopted our sphere packings to define a new volume preserving deformation scheme, the sphere-spring system, that extends the classical mass-spring systems. Second, we show an application of our Inner Sphere Trees to real-time obstacle avoidance in dynamic environments for autonomous robots. Finally, 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.

René Weller

Every End Is Just a New Beginning

Frontmatter

Chapter 8. Epilogue

Abstract

This chapter concludes this book by shortly summarizing the main contributions of this work. Finally, we outline avenues for future research in the field of collision detection in particular and to geometric acceleration structures in general.

René Weller

Titel: New Geometric Data Structures for Collision Detection and Haptics
verfasst von: René Weller
Verlag: Springer International Publishing
Electronic ISBN: 978-3-319-01020-5
Print ISBN: 978-3-319-01019-9
DOI: https://doi.org/10.1007/978-3-319-01020-5