Badlogic Games

I didn’t have a lot of time today so i only got a few things done. I’m currently reworking the intersection/collision detection package to make it fit for some spatial partitioning algorithms i like to test. What i did today was implementing a lot of the methods presented in “Real-time Collision Detection” by Christer Ericson. The book features some fine, optimized intersection testing methods which might come in handy soon.

After some talks with Robert from Battery Powered Games i’m not that convinced anymore that going the BSP tree route is optimal. I just can’t figure out how to do proper swept sphere collision with a BSP tree. For an octree the situation is a bit better, even though you also have to come up with some magic to do a minimal swept sphere collision test with the nodes. Robert suggested the use of neighbor lists for each Octree node which should be easily derivable via this fine idea http://www.flipcode.com/archives/Octree_Neighbor_Nodes.shtml. However, that approach assumes a maximum movement speed and minimum size for the octree nodes which must be tuned from scene to scene. I hope i can come up with something more generic.

The BSP tree is not totally out of the window, i already wrote the compiler (not in the trunk at the moment as it is a bit to experimental ). I have yet to test it with really complex scenes.

I will write the next libgdx article tomorrow. We’re gonna talk about handling files.

All hail! Now that didn’t take long to work. I sat down tonight and implemented the approach presented in http://www.peroxide.dk/papers/collision/collision.pdf, made it a bit more generic et voila it works as expected. Here’s a screen shot of the test application:

And here’s the libgdx code:

public class CollisionTest implements RenderListener
{
	final float VERY_CLOSE_DISTANCE = 0.001f;
	final float SPEED = 1;	
	CollisionMesh cMesh;
	EllipsoidCollider collider;
	MeshRenderer mesh;
	PerspectiveCamera cam;		
	float[] lightColor = { 1, 1, 1, 0 };
	float[] lightPosition = { 2, 5, 10, 0 }; 
	float yAngle = 0;
	Matrix mat = new Matrix();	
	Vector axis = new Vector( 0, 1, 0 );
	Vector velocity = new Vector( 0, 0, 0 );	
 
	@Override
	public void surfaceCreated(Application app) 
	{			
		FloatMesh m = (FloatMesh)ModelLoader.loadObj( app.getFiles().readInternalFile( "data/scene.obj" ), true );
		mesh = new MeshRenderer( app.getGraphics().getGL10(), m, true, true );			
		cam = new PerspectiveCamera();
		cam.setFov( 45 );
		cam.setNear( 0.1f );
		cam.setFar( 1000 );
 
		cMesh = new CollisionMesh( m, false );
		collider = new EllipsoidCollider( 1, 1, 1, new SlideResponse() );			
	}
 
	@Override
	public void render(Application app) 
	{
		processInput( app.getInput(), app.getGraphics().getDeltaTime() );
 
		GL10 gl = app.getGraphics().getGL10();
		gl.glClearColor( 0, 0, 0, 0 );
		gl.glClear( GL10.GL_COLOR_BUFFER_BIT | GL10.GL_DEPTH_BUFFER_BIT );
 
		render3D( gl, app.getGraphics() );			
	}	
 
	private void render3D( GL10 gl, Graphics g )
	{
		gl.glEnable( GL10.GL_DEPTH_TEST );
		cam.setMatrices( g );
		setupLights( gl );					
		mesh.render(GL10.GL_TRIANGLES );
	}
 
	private void setupLights( GL10 gl )
	{
		gl.glEnable( GL10.GL_LIGHTING );
		gl.glEnable( GL10.GL_COLOR_MATERIAL );
		gl.glEnable( GL10.GL_LIGHT0 );				
		gl.glLightfv( GL10.GL_LIGHT0, GL10.GL_DIFFUSE, lightColor, 0 );
		gl.glLightfv( GL10.GL_LIGHT0, GL10.GL_POSITION, lightPosition, 0 );
	}
 
	private void processInput( Input input, float deltaTime )
	{
		if( input.isKeyPressed( Input.Keys.KEYCODE_DPAD_LEFT ) )
			yAngle += deltaTime * 90;
		if( input.isKeyPressed( Input.Keys.KEYCODE_DPAD_RIGHT ) )
			yAngle -= deltaTime * 90;
 
		cam.getDirection().set( 0, 0, -1 );
		mat.setToRotation( axis, yAngle );
		cam.getDirection().rot( mat );
 
		if( input.isKeyPressed( Input.Keys.KEYCODE_DPAD_UP ) )		
			velocity.add(cam.getDirection().tmp().mul( SPEED * deltaTime));
		if( input.isKeyPressed( Input.Keys.KEYCODE_DPAD_DOWN ) )
			velocity.add(cam.getDirection().tmp().mul(SPEED * -deltaTime));
 
		if( !collider.collide( cMesh, cam.getPosition(), velocity, 0.0000001f ) )
		{
			velocity.add( 0, -0.5f * deltaTime, 0 ); // gravity when we don't collide
			collider.collide( cMesh, cam.getPosition(), velocity, 0.0000001f );
		}
 
		cam.getPosition().add( velocity );
		velocity.mul( 0.95f ); // decay
 
 
		System.out.println( velocity );
	}
 
	@Override
	public void dispose(Application app) 
	{	
 
	}
 
	@Override
	public void surfaceChanged(Application app, int width, int height) 
	{	
 
	}
 
	public static void main( String[] argv )
	{
		JoglApplication app = new JoglApplication( "Collision Test", 480, 320, false );
		app.getGraphics().setRenderListener( new CollisionTest() );
	}
}

That’s 123 lines of code which loads an OBJ file, creates a renderable mesh as well as a collision mesh from the OBJ and then does simple cursor key based movement. The method processInput does the magic, it’s actually only 4 lines do perform the collision detection.

The API is designed in such a way that you can have any collision response you want, be it sliding or bouncing or what have you. Currently i only implemented sliding. I will prepare a simple demo for you to try. The fun part is that when i apply gravity i actually slide down ramps . It’s an effect which might come in handy.

As a side note: the code does not produce any intermediate objects and is thus extremely garbage collector friendly. Also, given the API design you can plug in any spatial partitioning algorithm you like to cull triangles before actually performing the collision.

You can try it out on the desktop by downloading this: collision-test.zip. Simply extract it and run the Jar. Use the arrow keys to navigate, click into the window to get focus first.

Today i started working on a continuous collision detection and response module. What’s the goal? Given a polygon soup and a position plus velocity of an object i want to determine whether the object collides with the world and if so manipulate the position and velocity of the object to respond to the collision. The continuous part comes into play it is not enough to just check the object using its current position. Instead we have to check the volume it occupies while moving between two successive frames. The movement is defined via the velocity vector giving a direction as well as a distance all in one. Here’s an illustration by Telemachos:

For collision we somehow have to represent the moving object. Usually you’ll want to use something very simple like a sphere, a bounding box or an ellipsoid. The collision module i implement uses ellipsoids. An ellipsoid is basically a sphere which has 3 radii, one for each axis (actually that’s a special case of an ellipsoid…). In the first step we collide this ellipsoid with our world geometry. We determine the nearest intersection point and triangle we intersected with and react on that collision by displacing the object and changing its velocity. How to change the velocity depends on what we want to achieve. If we want to simulate a ball for example we’ll change the velocity in such a way that the ball bounces of from the hit surface. If we want to do something like a first person shooter we let the object slide along the hit surface. This is called the collision response stage and you can implement anything here that fits your need. Once we determined the collision and response we have a new position and velocity for the object. The fun part: we use this new position/velocity pair to do another round of collision detection and response. Collision detection is a recursive process. We recurse until no more collisions occur or a certain recursion depth is reached.

The real hard part about all this is actually determining the collision. The problem is that we can’t simply intersect a stationary sphere/ellipsoid with the triangle soup of our world. Instead we have to construct a swept volume and intersect that with the triangles, one triangle at a time. There’s a lot of things to do to make that work correctly. The book “Real-time Collision Detection” does not to my surprise cover swept volume collisions against triangles, at least not as detailed as it covers other more obvious topics. There’s an article by Paul Nettle whcih describes a very simple swept ellipsoid/triangle intersection tests, however it was found that it does not work in all cases. The only source that seems to work for all cases can be found at http://www.peroxide.dk/papers/collision/collision.pdf. This article by Kasper Fauerby describes in detail what is necessary to do proper swept ellipsoid intersection testing. I re-implemented that article today but could not yet fully verify that it works. I suspect it also has problems actually. The assumption is the the ellipsoid does not intersect anything when it is at its starting position. This assumption is guaranteed in the first recursion of the collision detection method. However, when the position and velocity are changed due to a detected collision this assumption does not hold anymore making the second iteration fail. I have not tested this yet, but from the code and the algorithmic description it seems like this is the case.

Anyways, libgdx will have a nice collision detection module probably at the end of the weak. It is designed in such a way that you can plug in any spatial partitioning or bounding volume schema to cull as many triangles before actually doing the swept ellipsoid test. More to come.

I threw together a very simple Pong clone with libgdx yesterday. That’s what it looks like:

The source is fully documented and should illustrate many of the concepts of libgdx. You can find it at http://code.google.com/p/libgdx/source/browse/trunk/gdx/src/com/badlogic/gdx/tests/Pong.java. It’s approximately 200 lines of codes without comments. The AI is actually only 10 lines :p