Blog

In the previous post I have introduced the concept of a Pose. A Pose is a new type defined in DigitalRune Geometry. It defines the position and orientation of an object in 3D space.

In this post I will describe how a Pose can be used to define a World or View transformation matrix…

The task of positioning an object in space is so important in a game that we have introduced a type called Pose in DigitalRune Geometry. A Pose describes a position (a Vector3F) and an orientation (a Matrix33F or a QuaternionF) in 3D space. It is very similar to a transformation matrix…

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:

…

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.
• …