Projects

WebGL Demos
PHP Data Pivot
PHP Data Subtotals
HTML5 Graph
Java NW3D2
JS Code Formatter
HTML5 Clock
Silverlight Gauge
Java NW3D
Java Fireworks
Java Early 3D
Java Snow
Java Dogfight
Java Water Simulation
Java Bump Mapping
Java Elite Ships

NW3D - Collision detection

The previous work on NW3D was aimed at getting the basic rendering and object creation working. In order to move forward with more complex scenes that may represent a virtual world it is necessary to incorporate collision detection so that there can be interaction with objects within the world. I like demo's, so let's begin with one.

No Java Support.

Use cursor keys and 'a' to jump.

In building a solution that works well within the architecture of NW3D I read many superb articles, both online and printed material, which I credit at the foot of the page. I won't describe all of the theory and mathematics here as those articles do such a great job already. Instead, I'll outline the algorithm that I used, which differs from many other approaches but incorporates the basics of collision detection and response. I'll tidy up the full Java code at some point, but for now the following pseudo-code (which is very close to the actual Java code anyway) should give a good overview of the process.

Demo applet main loop

  drawframe() {
	if (!onGround) {
		verticalVelocity -= 0.2f;  //accumulate gravity
		movePlayer(verticalVelocity,1);   
	}
	
	if (turnleft) scene.RotateYAxis(-3);
	
	if (turnright) scene.RotateYAxis(3);
	
	if (walkfwd) scene.moveplayer(forwardVelocity,0);
	
	if (walkbwd) scene.moveplayer(-forwardVelocity,0);
	
	if (jump && onGround) {
		onGround = false;
		verticalVelocity = 2.0f;  //jump velocity
	}

	scene.Render();
  }

Gravity is applied when the player is no longer on the ground. The player can only jump when on the ground.

Note that the second parameter of 'movePlayer' with a value of '1' denotes that this is gravitational movement rather than player initiated movement.

Scene object 'movePlayer' routine

  public void movePlayer(nw3d_vector3D vel, byte type) {
	//Type 0=Player initiated movement, 1=Gravity
	double ang;
	onGround = false;    //assume player no longer on ground
		
	do {
		vel = checkWorldCollisions(vel);
	} while(colOccurred && vel.length() > colEpsilon);
 

	//If there a resulting move calculate the angle of pitch
	//i.e. are we going uphill or downhill and by how much?
	if (vel.length()>0) {
		double slidedot = vel-yComponent.dot(vel);
		if (slidedot < -1 || slidedot > 1) {
		    ang=0;
		} else {
		    ang = Math.acos(slidedot) * radtodeg;
		}
	} else {
		ang=0;
	}

	//Perform move if we are heading uphill at less than maximum slope
	//angle, or we are heading downhill beyond the slip angle
	if (vel.length() > colEpsilon && vel.y >= -colEpsilon && ang < 60 ||
	   vel.length() > colEpsilon && vel.y < 0 && ang > 60) {
		vel=vel.negate();
		Translate(vel);
	} else {
		if (type == 1) {
		  onGround = true;
		  vertVel = 0;
		}
	}
  }

The 'checkWorldCollisions' routine is repeatedly called until either there are no more collisions or the resulting movement is sufficiently small to ignore.

If there is a resulting movement then the pitch angle (relative to horizontal) is calculated. This is used in conjunction with maximum climb and slip angles.

We then decide whether the movement should be allowed or not. Firstly, if the player is trying to climb a slope greater than 60 degrees or is standing on a downward slope of less than 60 degrees then don't bother moving. Secondly, if we've decided not to move and this has happened while applying gravity (type 1) then we'll assume that the player is back on terra firma and set the onGround flag.

Scene object 'checkWorldCollisions' routine

  public nw3d_vector3D  checkWorldCollisions(nw3d_vector3D vel) {
   colOccurred = false;  //assume no collision
   colTime = 1;
   move_dist = vel.length();

   pos_before = new nw3d_vector3D(0,0,0);  //camera origin
   pos_after = pos_before.add(vel);
   
   Loop through all world objects..............
     
      Loop through all triangles within each object.........
		  
	//Create plane from triangle points
	plane p = new plane(t[v1],t[v2],t[v3]);

	//Only process triangles that are facing toward
	//the direction of travel.
	if (p.normal.dot(vel)<=0) {
	 
	    //Calculate before and after relationship to plane
	    plane_before = p.pointlocation(pos_before);
	    plane_after = p.pointlocation(pos_after);
	     
	    //Calculate point of possible collision on bounding
	    //sphere/ellipsoid, which will be the reversed unit
	    //vector of the plane normal multiplied by the
	    //bounding sphere/ellipsoid radius.
	    col_before = p.normal.negate().mul(bsr);
	    col_after = col_before.add(vel);
		
	    //Check if either of the following conditions are true:-
	    //1) The before and after positions are on different sides
	    //    of the plane,
	    //2) The point of collision on the bounding sphere either before
	    //    or after is on the far side of the plane
	    if (plane_before != plane_after || 
		(p.distance(col_before)<0 || 
		 p.distance(col_after)<0)) {
		 
		//But did we collide with the triangle on the plane?
		//Project a ray between before/after
		//potential collision points.
		ray = col_after.sub(col_before);
		newTime = this.timeToCollision(col_before, ray, p);
		//Point of collision
		tempPoint = col_before.add(ray.mul(newTime));

		//Is the point of intersection within the surface
		//of the triangle?
		if (tempPoint.insideTriangle(v1,v2,v3)) {
		    if (newTime >=0 && newTime < colTime) {
			colOccurred = true;
			colPoint = tempPoint;
			colTime = newTime;
			colPointN = p.normal;
		    }
		} else {
		  //Otherwise, sweep the bounding volume against each
		  //vertex and edge. In each case use a quadratic equation
		  //to check for the nearest solution i.e. where the distance
		  //between vertex/edge equals the bounding radius (contact!)
							
		  //Vertex 1
		  newTime = getTimeOfCollisionWith(t[v1]);
		  if (newTime>0 && newTime<colTime) {
			colTime = newTime;
			colOccurred = true;
			colPoint = t[v1];
			colPointN = pos_before.sub(colPoint);
			colPointN.normalise();
		    }

		  Repeat for V2 & V3.......
					
		  //First edge - V1 to V2
		  edge = v2.sub(v1);
		  newTime = getTimeOfCollisionWith(edge);
		  if (newTime>0 && newTime<colTime) {
		      Calculate exact point of collision
		      If collision point within bounds of the edge {
			    colTime = newTime;
			    colOccurred = true;
			    colPoint = (calcualted collision point on edge);
			    colPointN = pos_before.sub(colPoint);
			    colPointN.normalise();
		      }
		  }
							
		  Repeat for edge V2->V3 and edge V3->V1.......
							
            }  //Point inside triangle?
          }  //Passed through plane?
        }  //Triangle facing direction of travel?
      }  //All triangles
    }//All objects
  
  //Was there a collision?
  //If so we should have a record of the time to impact, 
  //point of collision, and surface normal at point of collision.
  if (colOccurred) {
	//Calculate vectors representing movement to point of collision
	//and remaining slide velocity.
	vel.normalise();
	colDist = colTime * move_dist;
	slideDist = move_dist-colDist;
			
	slidePlane = new plane(colPoint, colPointN);
	plannedDest = colPoint.add(vel.mul(slideDist));
	finalDest = plannedDest.sub(slidePlane.normal.mul(
		slidePlane.distance(plannedDest)));
	slideVel = finalDest.sub(colPoint);
			
	//Move to point of collision
	move = vel.mul(colDist * (1-colEpsilon));   
	if (move.length() > colEpsilon) {
		move = move.negate();
		Translate(move);
	}
			
	//Return remaining slide as the new velocity
	vel = slideVel;
  } 
		
  return vel;
}

The purpose of the above routine is to establish whether the requested movement will result in a collision and if so with what and when. If a collision has occurred then any resulting 'slide' will also be calculated.

Nested loops consider all triangles within all world objects. Triangles are ignored if the plane they lie on is facing away from the direction of travel. We then check to see if we either cross the plane during the proposed movement or move to within the radius of the bounding sphere. If so, we firstly test whether the point on the bounding sphere that first crosses the plane is within the surface of the triangle. It it is then we remember the 'time' of the collision, the point of collision and the surface normal (for sliding), and move on to the next triangle.

Otherwise we need to perform more computationally expensive tests for possible collisions with any one of the three vertices or one of the three triangle edges. This is accomplished using a sweep test, solved using a quadratic equation. As with the previous test for collision with the triangle surface, each of these tests will initially check for a collision and if found to happen at a time sooner than any previous collision, remember the details for later use.

After processing all objects/triangles we will either have had a collision or not. If not, simply return the original movement velocity unchanged. Otherwise, we firstly move to a point almost at the point of collision. Then we calculate a direction in which to slide using any left over velocity. This is returned as a new movement at which point the process starts over.

Additional

I use an 'onGround' flag so that the collision detection routine isn't needlessly called to add gravity every frame. Notice how the 'onGround' flag is cleared as soon as the player initiates movement. This is because the player could have stepped off a cliff and is therefore potentially no longer on the ground. The 'onGround' flag is only set once no movement is found to be possible when gravity is applied. This is why I differentiate the type of movement between player-initiated and gravity via a parameter.

Imagine a scenario where the player is trying to leap across a chasm and unfortunately doesn't make it. The forward motion of the player is halted by the cliff/wall on the far side because the collision detection routine is checking for collisions in the direction of travel. However, it's not until gravity is applied that we understand what is under the player's feet. The 'onGround' flag also serves a useful, secondary purpose - that of preventing the player from jumping when already in the air!

Future improvements

Bounding elipsoid

The use of a bounding sphere for the player isn't ideal although it does make the maths a bit easier and the code a bit shorter. A sphere doesn't really approximate the shape of a person very well. If the bounding sphere radius is set so that the height from the floor feels fairly realistic then collisions moving fore/aft happen at a distance that seems too large.

Many engines, including some referenced below, use a bounding elipsoid, which better suits a humanoid shape in that the relative dimensions can be tailored. An additional, initial step is required to transform 3D world space dimensions into 'elipsoid space' dimensions using the radius vector of the bounding elipsoid (see Paul Nettle's article).

Multiple colliders

In its current state the code assumes that only the player is moving and that all other world objects are static. It would be desireable to consider multiple colliders and incorporate a means of dynamic world objects affecting the player, e.g. a lift, moving vehicle, etc.

Crash landing

At the moment the player returns to being 'onGround' the vertical velocity is known. Depending on the type of application this could be used to deplete the health of the player if too fast, damage the landing craft, etc.

Collision object

A collision event may be useful if we wanted contact with certain objects to trigger actions, e.g. touching a door causes it to open, colliding with a gemstone adds it to our inventory, passing through a transparent plane causes a scripted scene to begin, etc.


References:

Sweeping a sphere against a point (David Black)
sweep sphere vs triangle edge 3D intersect (gamedev forum, various)
General Collision Detection for Games Using Ellipsoids (Paul Nettle)
Moving Sphere vs Triangle Collision (Igor Kravtchenko)
Collision detection & Response (Kasper Fauerby)

Back to NW3D index