Monthly Archives: June 2013

Collision Detection Basics

The basis for all collision detections is analytical geometry. Math can answer the question where two primitives intersect or give the distance between two objects. This post will only cover such basic functions. So it is a collection of primitive - primitive relation functions. There are two functions given. The first only returns collision or not. The second variant returns a resolvement vector. This is a translation vector which have to be applied to object 1 to move the two objects out of each other.


Object Properties
Sphere center , radius
Line start and end , implicit direction
Triangle The 3 vertices in counter clock wise order , implicit normal

Sphere - Sphere

For a detection the distance has to be less or equal to the sum of the radi.

For resolvement just take the connection between the midpoints and the intersection length.

Sphere - Line

First the nearest point on a straight must be computed. If this point does not lie between the start and the end point choose the start or end point respectively.


The resolvement vector is the connection between sphere center and the nearest point on the line.

Sphere - Triangle

The usual way to do this is to project the sphere center to the triangle's plane. Afterwards the barycentric coordinates of the point would be calculated to test if it is inside. If not we still have to test whether the circle from the plane-sphere cut intersects with a triangle or not. Therefore it is sufficient to test the 3 line-sphere cuts because the center is definitely outside. I changed the middle part to hopefully increase the speed. Instead of calculating the barycentric coordinates I compute the closest points on all three sides which I would need in the last step non the less. Then the following condition must be true if the point is inside: the opposite vertex to a side (and therefore a point on that side) must lie on two different "sides" of the projected center. So the dot product of the vectors from the center to a closest point on a triangle-side and to the related triangle-vertex has to be at least 0.

There was one problem when using a full triangle collision in the game Pathfinder. Imagine a box made of triangles. Then the sphere is placed on top near to an edge. The simulation will first push the sphere down. Afterwards the collision detection would report two triangles. The one on the top and one of a side where the sphere collides with a back face. This has the effect that the sphere is pushed away from the edge to the box center on the upper side. To avoid that I use the condition if( fDist < 0.0f || fDist > _S.fRadius ) in lines 10 and 46 instead of if( abs(fDist) > _S.fRadius ) .

The MST Distance Field

Distance field of a convex polygon

Distance field of a convex polygon

First of all: what is the gain of using distance fields for terrain generation? A distance field is the image of a distance function where black is very close to some object and white is far away. The results differ for different shaped objects as points or lines.
Well, using a 2D distance field as a 2D height map will create mountains or bubbles or cells depending on the objects' shape and the distance function to the objects. Everything in this post is using the euclidean distance .
As I had seen a picture like the one on the right side first I had thought "It looks like a mountain".

The second thing I observed was that minimal spanning trees (MST) of point sets where all points are connected to each other looks very much like a maintain ridge chain.

Alps height map (reality)

Alps height map (reality)

Distance to MST of 100 uniform distributed points

Distance to MST of 100 uniform distributed points

The nice thing you can see on the right picture is that the distance field is "height" where much space is available. So there are height and small mountains mixed and the result is a nice base shape for a terrain.

One problem of using a distance function is that outside (not on the image) the distance will increase further and further. So the mountains do end in a plane but in a limited high plateau around the MST region. This leads to the idea of using the inverse: .

Inverse distance of the same MST as in the previous picture

Inverse distance of the same MST as in the previous picture

An advantage of the inverse function is that our initial points are now the highest points = summits. On the other hand the whole MST has the same height! All ridges and summits are on the same level now. Before all valleys had a height of 0 which was less visible.

Consider the nice property that the points are the summits. It is now very intuitive to give each point an individual height and somehow change the distance function.

All test to change the distance function itself produced artifacts. It will always make problems because the result is a global property which may depend on all vertices and edges of the MST graph.

To solve that issue I took a global interpolation scheme to compute the local height and multiplied the results with the pure distance field which works great!

Computation of the distance field

There are lots of papers related to this issue. Assuming point objects everywere and make a straight forward convolution of a map would take time. There are better ways to do that with a point map, but I thought about using the graph itself. Then the computation takes where is the number of edges in the MST which I assumed to be relatively small. It is not possible to go beyond because we have to write each pixel at least once. For an implementation example of a point-line distance function see my collection of functions (TODO).

To compute the parametrised height I used a weighted mean:

where is a radial basis function. The farther the point is away the less it contributes to the current height. I found the Gaussian RBF and the Inverse Quadric RBF to be useful.


About the automaton behind Voxel Seeds

Cellular automaton rule with 6-neighbourhood

Cellular automaton rule with 6-neighbourhood

For a regular grid it is easy to do a simulation based on rules. Each rule should be applied to each grid cell to change the state of the cell. In our case the grid is a 3D voxel array. If there is a single output of which state the cell should have this whole thing would be called cellular automaton.

We changed this to multiple input multiple output rules to be faster and more flexible.

Automaton rule with multiple output

Automaton rule with multiple output

Why faster? In a normal cellular automation on each cell each rule has to be applied, because e.g. an empty cell could get anything in the next step. For 300 x 60 x 300 world with 10 species this causes 54,000,000 rule computations per simulation step. We decided to simulate 4 steps per second...
So we changed the point of view: Only a few living cells of a known type are simulated. These canĀ  change their neighbourhoods too. Therefore an empty cell could be filled and the automaton can basically do the same thing as before. Now we are just simulating at most 5,000 cells and apply exactly one rule depending on the voxel type. This is less than before by a factor of >10,000.

Why should the multiple output structure be more flexible? In a standard automaton it would be necessary to create rules for any possible neighbourhood of different voxel types. For a 3 x 3 x 3 area this means to write rules for 27^10 different settings. Of course we could group them but it is stell not feasible. The new view allows to write rules per species. To fill the gab of the remaining 26^10 rules per species rules can be written generic and are allowed to return don't cares.

Example for a simple beetle rule: Iterate over all neighbours and count the empty cells. If there is at least one empty cell choose one of them randomly. Return EMPTY for the current cell and BEETLE for the chosen cell.

Rule for a flying beetle (most boxes on the right side are don't cares)

Rule for a flying beetle (most boxes on the right side are don't cares)

From a local rule to a more global decion

Until now a rule sees only a 3 x 3 x 3 region and has to make decisions on that. Using larger regions would only make things much more complicated. So we added more information as "resources" and "generation" to the living voxels. It is therefore possible to now the distance to the last branch in a tree or things like that. The usage and maintenance of these information depends on the type specific rules.


The Voxel Seeds automaton implementation maintains a 3D voxel grid with one byte type information per cell. Additionally it holds a list of living voxels with further information. Four times in a second all living voxels are simulated in parallel to the rendering, input handling, .... So a simulation could take 0.25s before the game would be slowed done. After each step an incremental update of all changed voxels is pushed to the GPU synchronously.

We are very happy with the performance and behavior of our small rule sets. Remember: all this was designed and implemented in 48 h on one weekend.