|
| |
|
|
|
|
Publications
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:
- A novel geometric data structure, the Inner Sphere Trees (IST), that provides
hierarchical bounding volumes from the inside of an object.
- A method to compute a dense sphere packing inside a polygonal object.
- We propose to utilize a clustering algorithm to construct a sphere hierarchy.
- A unified algorithm that can compute for a pair of objects, based on their ISTs,
both an approximate minimal distance and the approximate penetration volume;
the application does not need to know in advance which situation currently exists
between the pair of objects.
- A method to compute forces from the penetration volume that are continuous,
both in direction and value.
Published:
Virtual Realities, Springer, 2011
[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:
Siggraph Asia, Technical Sketches, 2010
[BibTex]
Files:
Paper (pdf, 6MB)
Slides (pptx, 25MB)
Video 1 from Talk (wmv, 30MB)
Video 2 from Talk (wmv, 8MB)
Video 3 from Talk (wmv, 2MB)
Video 4 from Talk (wmv, 5MB)
Video 5 from Talk (wmv, 4MB)
Video 6 from Talk (wmv, 28MB)
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:
Proceedings of the 17th ACM Symposium on Virtual Reality Software and Technology 2010 (VRST' 2010), Hong Kong, November 2010.
[BibTex]
Files:
Paper (pdf, 2.2MB)
Presentation Slides (pdf, 1.2MB)
Links:
Project Homepage
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:
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:
IDETC/CIE Presentation (ppt, 15MB)
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
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:
ACM SIGGRAPH Video Game Proceedings ,
New Orleans, USA, August 2009. [BibTex]
Files:
Siggraph Paper (pdf, 4MB)
Siggraph Presentation (ppt, 25MB)
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:
2009 Robotics: Science and Systems Conference (RSS),
Seattle, USA, 28 June - 01 July 2009. [BibTex]
Files:
RSS paper (pdf, 6MB),
RSS poster (pdf, 2MB)
Technical Report (pdf, 6MB), [BibTex]
Links:
Project Homepage
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 (pdf, 1.0MB)
Slides (pdf, 5.4MB)
Video of configuration generation (avi, 16.6MB)
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 (pdf, 0.7MB)
Slides (pdf, 4.9MB)
Kinetic Bounding Volume Hierarchies for 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 (pdf, 1MB)
Slides (pdf, 6.0 MB)
Technical Report (pdf, 1.2MB)
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 (pdf, 1.6 MB)
Paper, print version (pdf, 1.6 MB)
Slides (pdf, 2.5 MB)
[Complete list of all entries in BibTex
format]
|
|
Rene Weller
Am Ludwiger Graben 5
38678 Clausthal-Zellerfeld
Germany
Tel: +49 5323 983005
|
|
