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.

3D

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.

bool SphereSphereCollision( const Sphere& _S1, const Sphere& _S2 )
{
	float fLen = lensq( _S1.vCenter - _S2.vCenter );
	float fr   = _S1.fRadius + _S2.fRadius;
	return fLen <= fr*fr;
}

bool SphereSphereCollision( const Sphere& _S1, const Sphere& _S2, Vec3& _vResolve )
{
	_vResolve = _S1.vCenter - _S2.vCenter;
	float fLen = len( _vResolve );
	if( fLen > _S1.fRadius + _S2.fRadius ) return false;

	fLen = (fLen - (_S1.fRadius + _S2.fRadius)) / fLen;
	_vResolve *= fLen;
	return true;
}

bool SphereSphereCollision( const Sphere& _S1, const Sphere& _S2 )

{

float fLen = lensq( _S1.vCenter - _S2.vCenter );

float fr = _S1.fRadius + _S2.fRadius;

return fLen <= fr*fr;

}

bool SphereSphereCollision( const Sphere& _S1, const Sphere& _S2, Vec3& _vResolve )

{

_vResolve = _S1.vCenter - _S2.vCenter;

float fLen = len( _vResolve );

if( fLen > _S1.fRadius + _S2.fRadius ) return false;

fLen = (fLen - (_S1.fRadius + _S2.fRadius)) / fLen;

_vResolve *= fLen;

return true;

}

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.

Vec3 ClosestPointOnLine( const Vec3& _vPoint,
			 const Vec3& _vLineS,
			 const Vec3& _vLineE )
{
	Vec3 d(_vLineE - _vLineS);
	Vec3 w(_vPoint - _vLineS);

	float fR = (dot(w, d) / lensq(d));

	// Nearest point to _vPoint is _vLineS
	if(fR <= 0.0f) return _vLineS;
	// Nearest point is on the line
	else if(fR < 1.0f) return _vLineS + d * fR;
	// Nearest point to _vPoint is _vLineE
	else return _vLineE;
}

bool SphereLineCollision( const Sphere& _S, const Line& _L )
{
    return lensq(_S.vCenter - ClosestPointOnLine( _S.vCenter, _L.vStart, _L.vEnd )) <= _S.fRadius*_S.fRadius;
}

bool SphereLineCollision( const Sphere& _S, const Line& _L, Vec3& _vResolve )
{
    _vResolve = _S.vCenter - ClosestPointOnLine( _S.vCenter, _L.vStart, _L.vEnd );
    return lensq(_vResolve) <= _S.fRadius*_S.fRadius;
}

Vec3 ClosestPointOnLine( const Vec3& _vPoint,

const Vec3& _vLineS,

const Vec3& _vLineE )

{

Vec3 d(_vLineE - _vLineS);

Vec3 w(_vPoint - _vLineS);

float fR = (dot(w, d) / lensq(d));

// Nearest point to _vPoint is _vLineS

if(fR <= 0.0f) return _vLineS;

// Nearest point is on the line

else if(fR < 1.0f) return _vLineS + d * fR;

// Nearest point to _vPoint is _vLineE

else return _vLineE;

}

bool SphereLineCollision( const Sphere& _S, const Line& _L )

{

return lensq(_S.vCenter - ClosestPointOnLine( _S.vCenter, _L.vStart, _L.vEnd )) <= _S.fRadius*_S.fRadius;

}

bool SphereLineCollision( const Sphere& _S, const Line& _L, Vec3& _vResolve )

{

_vResolve = _S.vCenter - ClosestPointOnLine( _S.vCenter, _L.vStart, _L.vEnd );

return lensq(_vResolve) <= _S.fRadius*_S.fRadius;

}

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 ) .

bool SphereTriangleCollision( const Sphere& _S,
			const Triangle& _T )
{
	Vec3 A = _T.v1-_T.v0;
	Vec3 B = _T.v2-_T.v1;
	Vec3 C = _T.v2-_T.v0;

	// Distance sphere plane - do not collide with back faces
	float fDist = dot( _T.n, _S.vCenter-_T.v0 );
	if( abs(fDist) > _S.fRadius )
		return false;

	// Circle point one the plane
	Vec3 P = _S.vCenter - _T.n * fDist;

	// Closest point on all edges
	Vec3 P_v0 = P-_T.v0;
	Vec3 P_v1 = P-_T.v1;
	Vec3 CoE1 = _T.v0 + A * saturate( dot( P_v0, A) / lensq(A) );
	Vec3 CoE2 = _T.v0 + C * saturate( dot( P_v0, C) / lensq(C) );
	Vec3 CoE3 = _T.v1 + B * saturate( dot( P_v1, B) / lensq(B) );

	// The vertex on the opposite side of the edge cannot lie in the same
	// direction as the nearest point if P lies inside the triangle.
	bool bInside = dot( CoE1-P, _T.v2-P ) < 0.0f;
	bInside &= dot( CoE2-P, P_v1 ) > 0.0f;	// Inverse sign because of use from P-v1
	bInside &= dot( CoE3-P, P_v0 ) > 0.0f;	// Inverse sign because of use from P-v0
	if( bInside ) return true;

	// Search for a collision on a edge or vertex
	if( lensq(CoE1-_S.vCenter) < _S.fRadius * _S.fRadius ) return true;
	if( lensq(CoE2-_S.vCenter) < _S.fRadius * _S.fRadius ) return true;
	return ( lensq(CoE3-_S.vCenter) < _S.fRadius * _S.fRadius );
}

bool SphereTriangleCollision( const Sphere& _S,
			const Triangle& _T,
			Vec3& _vResolve )
{
	Vec3 A = _T.v1-_T.v0;
	Vec3 B = _T.v2-_T.v1;
	Vec3 C = _T.v2-_T.v0;

 	// Distance sphere plane
	float fDist = dot( _T.n, _S.vCenter-_T.v0 );
	if( abs(fDist) > _S.fRadius )
		return false;

	// Circle point one the plane
	Vec3 P = _S.vCenter - _T.n * fDist;

	// Closest point on all edges
	Vec3 P_v0 = P-_T.v0;
	Vec3 P_v1 = P-_T.v1;
	Vec3 CoE1 = _T.v0 + A * saturate( dot( P_v0, A) / lensq(A) );
	Vec3 CoE2 = _T.v0 + C * saturate( dot( P_v0, C) / lensq(C) );
	Vec3 CoE3 = _T.v1 + B * saturate( dot( P_v1, B) / lensq(B) );

	// The vertex on the opposite side of the edge cannot lie in the same
	// direction as the nearest point if P lies inside the triangle.
	bool bInside = dot( CoE1-P, _T.v2-P ) < 0.0f;
	bInside &= dot( CoE2-P, P_v1 ) > 0.0f;	// Inverse sign because of use from P-v1
	bInside &= dot( CoE3-P, P_v0 ) > 0.0f;	// Inverse sign because of use from P-v0
	if( bInside )
	{
		// COLLISION inside the triangle
		_vResolve = _T.n * max( 0.0f, _S.fRadius - abs(fDist) ) * sgn(fDist);
		return true;
	}

	// Search for a collision on a edge or vertex
	Vec3 vShortest(CoE1-_S.vCenter);	float fLenShortest = lensq(vShortest);
	fDist = lensq(CoE2-_S.vCenter);	if( fDist < fLenShortest ) { fLenShortest = fDist; vShortest = CoE2-_S.vCenter; }
	fDist = lensq(CoE3-_S.vCenter);	if( fDist < fLenShortest ) { fLenShortest = fDist; vShortest = CoE3-_S.vCenter; }

	// Collision on edge or vertex
	if( fLenShortest < _S.fRadius * _S.fRadius )
	{
		fLenShortest = sqrt(fLenShortest);
		 _vResolve = vShortest * (( fLenShortest - _S.fRadius ) / fLenShortest);
		return true;
	}

	return false;
}

bool SphereTriangleCollision( const Sphere& _S,

const Triangle& _T )

{

Vec3 A = _T.v1-_T.v0;

Vec3 B = _T.v2-_T.v1;

Vec3 C = _T.v2-_T.v0;

// Distance sphere plane - do not collide with back faces

float fDist = dot( _T.n, _S.vCenter-_T.v0 );

if( abs(fDist) > _S.fRadius )

return false;

// Circle point one the plane

Vec3 P = _S.vCenter - _T.n * fDist;

// Closest point on all edges

Vec3 P_v0 = P-_T.v0;

Vec3 P_v1 = P-_T.v1;

Vec3 CoE1 = _T.v0 + A * saturate( dot( P_v0, A) / lensq(A) );

Vec3 CoE2 = _T.v0 + C * saturate( dot( P_v0, C) / lensq(C) );

Vec3 CoE3 = _T.v1 + B * saturate( dot( P_v1, B) / lensq(B) );

// The vertex on the opposite side of the edge cannot lie in the same

// direction as the nearest point if P lies inside the triangle.

bool bInside = dot( CoE1-P, _T.v2-P ) < 0.0f;

bInside &= dot( CoE2-P, P_v1 ) > 0.0f; // Inverse sign because of use from P-v1

bInside &= dot( CoE3-P, P_v0 ) > 0.0f; // Inverse sign because of use from P-v0

if( bInside ) return true;

// Search for a collision on a edge or vertex

if( lensq(CoE1-_S.vCenter) < _S.fRadius * _S.fRadius ) return true;

if( lensq(CoE2-_S.vCenter) < _S.fRadius * _S.fRadius ) return true;

return ( lensq(CoE3-_S.vCenter) < _S.fRadius * _S.fRadius );

}

bool SphereTriangleCollision( const Sphere& _S,

const Triangle& _T,

Vec3& _vResolve )

{

Vec3 A = _T.v1-_T.v0;

Vec3 B = _T.v2-_T.v1;

Vec3 C = _T.v2-_T.v0;

// Distance sphere plane

float fDist = dot( _T.n, _S.vCenter-_T.v0 );

if( abs(fDist) > _S.fRadius )

return false;

// Circle point one the plane

Vec3 P = _S.vCenter - _T.n * fDist;

// Closest point on all edges

Vec3 P_v0 = P-_T.v0;

Vec3 P_v1 = P-_T.v1;

Vec3 CoE1 = _T.v0 + A * saturate( dot( P_v0, A) / lensq(A) );

Vec3 CoE2 = _T.v0 + C * saturate( dot( P_v0, C) / lensq(C) );

Vec3 CoE3 = _T.v1 + B * saturate( dot( P_v1, B) / lensq(B) );

// The vertex on the opposite side of the edge cannot lie in the same

// direction as the nearest point if P lies inside the triangle.

bool bInside = dot( CoE1-P, _T.v2-P ) < 0.0f;

bInside &= dot( CoE2-P, P_v1 ) > 0.0f; // Inverse sign because of use from P-v1

bInside &= dot( CoE3-P, P_v0 ) > 0.0f; // Inverse sign because of use from P-v0

if( bInside )

{

// COLLISION inside the triangle

_vResolve = _T.n * max( 0.0f, _S.fRadius - abs(fDist) ) * sgn(fDist);

return true;

}

// Search for a collision on a edge or vertex

Vec3 vShortest(CoE1-_S.vCenter); float fLenShortest = lensq(vShortest);

fDist = lensq(CoE2-_S.vCenter); if( fDist < fLenShortest ) { fLenShortest = fDist; vShortest = CoE2-_S.vCenter; }

fDist = lensq(CoE3-_S.vCenter); if( fDist < fLenShortest ) { fLenShortest = fDist; vShortest = CoE3-_S.vCenter; }

// Collision on edge or vertex

if( fLenShortest < _S.fRadius * _S.fRadius )

{

fLenShortest = sqrt(fLenShortest);

_vResolve = vShortest * (( fLenShortest - _S.fRadius ) / fLenShortest);

return true;

}

return false;

}

The MST Distance Field

2 Replies

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)

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

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.

// Use a global interpolation to generate a height for a certain point
static float computeHeight(const OrE::ADT::Mesh* mst, float x, float y)
{
	// Calculate a weighted sum of all heights where the weight is the radial basis function.
	auto it = mst->GetNodeIterator();
	float height = 0;
	float weightSum = 0;
	while( ++it ) {
		const Vec3& vPos = ((PNode*)&it)->GetPos();
		//float distance = 1.0f/(1.0f + 2.0f*(sqr(vPos.y-y) + sqr(vPos.x-x)));	// Inverse quadric RBF
		float distance = exp(-0.0006f*(sqr(vPos.y-y) + sqr(vPos.x-x)));		// Gaussian
		height += distance * vPos.z;
		weightSum += distance;
	}
	return height / weightSum;
}

// Use a global interpolation to generate a height for a certain point

static float computeHeight(const OrE::ADT::Mesh* mst, float x, float y)

{

// Calculate a weighted sum of all heights where the weight is the radial basis function.

auto it = mst->GetNodeIterator();

float height = 0;

float weightSum = 0;

while( ++it ) {

const Vec3& vPos = ((PNode*)&it)->GetPos();

//float distance = 1.0f/(1.0f + 2.0f*(sqr(vPos.y-y) + sqr(vPos.x-x))); // Inverse quadric RBF

float distance = exp(-0.0006f*(sqr(vPos.y-y) + sqr(vPos.x-x))); // Gaussian

height += distance * vPos.z;

weightSum += distance;

}

return height / weightSum;

}

About the automaton behind Voxel Seeds

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.

Summary

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.

Developerblog – Johannes Jendersie

Content Generators & Demos

Monthly Archives: June 2013

Collision Detection Basics

3D

Sphere - Sphere

Sphere - Line

Sphere - Triangle

The MST Distance Field

Computation of the distance field

About the automaton behind Voxel Seeds

From a local rule to a more global decion

Summary