Blog

Have you ever heard of Speed Reading? Forget speed reading – let me introduce you to Speed Watching!

But, first a little background information: What is speed reading? From Wikipedia:

Speed reading is a collection of reading methods which attempt to increase rates of reading without greatly reducing comprehension or retention…

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.

…

Multi-monitor support in Visual Studio 2010 is great. However, there is no direct way to switch between different window layouts.

In Visual Studio 2003 and 2005 you could use the addin VSWindowManager to manage window layouts. With some minor adjustments you could also run the addin in Visual Studio 2008. But the addin is not compatible with Visual Studio 2010.

Luckily, there is a simple solution…

We have created class diagrams for the Microsoft XNA Framework 4.0 assemblies (including Content Pipeline). (If you are looking for XNA 3 class diagrams, take a look at this post: XNA 3.x Framework Class Diagrams).

A Few Notes

• The class diagrams contain all types of the Microsoft XNA Framework 4.0.
• We tried to arrange the class diagrams so that they can be viewed on a widescreen monitor.
• Large namespaces, e.g. Microsoft.Xna.Framework.Graphics, are subdivided into several diagrams.
• …

Our new physics library is nearly finished. Here is a compilation of a few tests:

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.

…