Blog

This is a guest post by Kairat Aitpayev.

Augmented Reality (AR) technology allows adding virtual object to the real world using special markers. By merging it with Microsoft Kinect I have created new approach which allows users to use their own body as a collision object in the 3D world and interact with augmented objects.

Video

Here the presentation of the demo application which by itself is a part of bigger project related with online sport education:

(Full video of entire project: See https://vimeo.com/41136278)

The project was created in the MultiMedia Lab of Kazakh-British Technical University (Kazakhstan) in collaboration with University of Technology of Belfort-Montbeliard (France).

DigitalRune libraries are used to improve the interaction between the real and the virtual world.

In almost all 3D games collisions between complex shaped objects must be detected. For collision detection the triangle meshes can be used directly but this is a lot slower than using boxes, spheres or convex shapes. Therefore, for each model a collision model should be created that consists only of simple primitives. This collection of shapes approximates the shape of the detailed 3D graphics model. This blog posts discusses how we can use the XNA content pipeline to load shapes from a collision model created in a 3D modeling tool. The example source code can be downloaded.

The last posts (Continuous Collision Detection – The Problem and Continuous Collision Detection – Solutions) covered Continuous Collision Detection (CCD). Here are a few more notes related to CCD.

Notes

• CCD is more expensive than discrete collision detection.
• Use CCD only for objects that move with a velocity that is high (relative to the object’s extent).
• …

In the last post we talked about the shortcomings of discrete collision detection and why we need continuous collision detection (CCD). Now it is time to discuss ways to implement CCD to avoid tunneling of objects (missed collisions) and find the time of impact.

…

Collision detection in 3d games detects whether objects are intersecting. The normal discrete collision detection does so by checking the objects at their current position. Then the game moves the objects and the collision detection checks the objects at their new positions.

This method works for slow moving objects, but for fast moving objects critical collisions can be missed. To detect all collisions we need “Continuous Collision Detection” (CCD), which we will discuss in this and the next blog posts.

…

When writing a 3D collision detection system you will most likely run into the following problem: Given a convex polygon (in 2D) or a convex polyhedron (in 3D), which of its vertices is the extreme point in a given direction. The problem is known as Support Mapping or Extremal Query. (The resulting vertex is called Support Point or Extreme Point.) Algorithms like GJK, EPA (Expanding Polytope Algorithm) or MPR (Minkowski Portal Refinement) rely heavily on extremal queries.

For simple polyhedra (small number of vertices) you can simply do an exhaustive search to find the extreme point in a given direction. However, for complex polyhedra you want to find a way to accelerate the query…

In the last post we computed convex hulls for the XNA dude. Convex hulls are useful approximations for collision detection because many algorithms like GJK, EPA (Expanding Polytope Algorithm) or MPR (Minkowski Portal Refinement) can handle arbitrary convex objects. We also used simplified convex hulls. In this post we describe how we have implemented convex hull generation, convex hull simplification and skin width.

Convex Hull Computation

Actually, there are many convex hull algorithms. Here is a java applet showing different algorithms: http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html

We started with incremental construction as described in this book:

…

DigitalRune Geometry supports automatic generation of bounding shapes and convex hulls. Using simple bounding shapes or convex hulls is more efficient than using arbitrary triangle meshes in game physics. In this post we will investigate different kinds of bounding shapes.

What's up dude?

Let's look at a practical example. Here is the Dude from the XNA Skinned Model Example:

The model has 13132 vertices and the skeleton has 60 bones.

Bounding Spheres

Here is the same model where a bounding sphere is computed for the vertices of each bone.

…

This blog post contains our collection of references for Collision Detection: website links, a list of collision detection libraries, list of books. This post will be updated from time to time.

If you know other useful links, please let us know and we will include them in this blog post.

Collision Detection Websites

This is a collection of various links about collision detection and related topics. 

• Collision Detection on Wikipedia
• GAMMA research group
  Website contains a brief description of several libraries.
• Geometry Algorithms
  Collection of geometry algorithms: clipping, intersections, etc.
• …

For the new DigitalRune Geometry library we have created a simple 3D character controller example (including source code).

A character controller, as understood in this context, is a game engine module that computes the movement of an avatar in a game. The input for the character controller is the desired movement (e.g. “move forward with 5 m/s speed”, or “jump”) and the output is the new corrected avatar position in the 3D game world. The character controller has to apply gravity, avoid penetration of walls and other solid objects, handle stepping up/down slopes and stairs, and more.