Hi
The graphics course I took at TAU really expanded my knowledge of 3D rendering, and specifically using OpenGL to do so. The final task of the course, aside from the exam, was to write a 3D game. We were given 3 choices for types of games: worms-like, xonix-like and lightcycle-like. We chose to write our version of Worms in 3D.
I’ll try to take you through some of the problems we encountered, the decisions we made, and show as much code as possible. I’m not, however, gonna take you through the simple (yet grueling) work of actually showing meshes to the screen or moving them around, these subjects are covered extensively online.
The whole game is implemented in Java using JOGL and SWT for 3D rendering. The code is of course available entirely online.
In the begining there was mesh
Our game is a turn-based shooter, Worms-like. The players are supposed to walk on the face of a world mesh (a 3d structure), and shoot missiles at each other.
When it comes to positioning and aligning 3D objects on top of other 3D objects, I must say I was overwhelmed by the complexity. Its really not that easy to do, but once you get the idea its easy.
So you have an arbitrary 3D object, and you want another object to “walk” over it. Few things you need to know:
- the normal of the mesh at any given point, so your player can have an “up” direction (away from the mesh)
- the global orientation of your player object, so when you align it up it will actually face up
Now, to align the object you have to make it be oriented upwards from the mesh and point in the forward direction. So before drawing the player object make the model-view matrix face the right direction. For this we ported some CPP code that does exactly that:
public static void multLookAt (/*float eyex, float eyey, float eyez,
float atx, float aty, float atz,
float upx, float upy, float upz,*/
Vector3D origin,
Vector3D forward,
Vector3D up,
GL gl)
{
float m[] = new float[16];
// Compute our new look at vector, which will be
// the new negative Z axis of our transformed object.
forward = forward.getNormalized();
// Cross product of the new look at vector and the current
// up vector will produce a vector which is the new
// positive X axis of our transformed object.
Vector3D xaxis = forward.crossProduct(up).getNormalized();
m[0] = xaxis.x;
m[1] = xaxis.y;
m[2] = xaxis.z;
// Calculate the new up vector, which will be the
// positive Y axis of our transformed object. Note
// that it will lie in the same plane as the new
// look at vector and the old up vector.
up = xaxis.crossProduct(forward);
m[4] = up.x;
m[5] = up.y;
m[6] = up.z;
// Account for the fact that the geometry will be defined to
// point along the negative Z axis.
forward = forward.multiply(-1f);
m[8] = forward.x;
m[9] = forward.y;
m[10] = forward.z;
// Fill out the rest of the 4x4 matrix
m[3] = 0.f; // xaxis is m[0..2]
m[7] = 0.f; // up is m[4..6]
m[11] = 0.f; // -at is m[8..10]
m[12] = origin.x;
m[13] = origin.y;
m[14] = origin.z;
m[15] = 1.f;
// Multiply onto current matrix stack.
gl.glMultMatrixf(FloatBuffer.wrap(m));
}
Walk the mesh
Another key point in our game is making the player character walk smoothly on the mesh. The instructions for this exercise were that we have to make the player either walk from vertex to vertex, from edge to edge or the most complicated option – an arbitrary point on the mesh to another. We chose to make the player walk from edge to edge.
Say that the player object is on an edge. To make it walk to another edge we needed to know what are the possible edges that it could reach. For that we created a half-edge structure of the world mesh. Then when we query the structure we can get in constant time the neighboring edges to the player (typically the one-ring of both vertices of the current edge he’s standing on). We only have to choose from the list of edges which edge the player should go to, and where on that edge he will “land”. This is done by choosing the edge with the closest point to the approximation of the players next location.
Let me explain:
- The player has a certain speed, meaning it can cover a certain distance in a given time.
- The approximate next location of the player is the distance it should cover in minimal time. We took a constant value.
- Once you have a approximate location, find the edge (and a point on that edge) that best conforms with this location
In the image you see the player object (snail), the ring of edges around the player that we check (green), the approximate next location (yellow), and the calculated next location (purple).
To find a best location for the object we calculated the distance between the player and the approximate. We ported another piece of C code to measure distance between segments to do that:
/**
* find the distance between 2 line segments
* @param S1P1 1st point of segment 1
* @param S1P0 2nd pt of seg 1
* @param S2P1 1st pt of seg 2
* @param S2P0 2nd pt of seg 2
* @return
*/
public static Vector3D dist3D_Segment_to_Segment( Vector3D S1P1, Vector3D S1P0, Vector3D S2P1, Vector3D S2P0)
{
Vector3D u = S1P1.minus(S1P0);
Vector3D v = S2P1.minus(S2P0);
Vector3D w = S1P0.minus(S2P0);
float a = u.innerProduct(u); // always >= 0
float b = u.innerProduct(v);
float c = v.innerProduct(v); // always >= 0
float d = u.innerProduct(w);
float e = v.innerProduct(w);
float D = a*c - b*b; // always >= 0
float sc, sN, sD = D; // sc = sN / sD, default sD = D >= 0
// compute the line parameters of the two closest points
sN = (b*e - c*d);
if (sN < 0f) { // sc < 0 => the s=0 edge is visible
return null;
}
else if (sN > sD) { // sc > 1 => the s=1 edge is visible
return null;
}
// finally do the division to get sc
sc = (Math.abs(sN) < Vector3D.EPSILON ? 0f : sN / sD);
return S1P0.add(u.multiply(sc)); // return the intersection point
}
We actually check what is the intersection point of the approximate edge with the line that goes from the player and in the forward direction. This is the point the player should be if it walked from his current position to that edge.
Orchestrating:
/**
* find the location where the player should be in the next frame
* @param distanceToMoveInThisInterval the distance the player object should (try to) move
* @return
*/
public EdgeAndIntersectionPointAndDistance findNextLocation(float distanceToMoveInThisInterval) {
//find all adjacent edges using half-edge struct
Edge currentEdge = model.getCurrentEdge();
Set<Edge> allEdges = currentEdge.b.get2RingOfEdges();
allEdges.addAll(currentEdge.a.get2RingOfEdges());
//A point that lies a little bit along the line from the player and in the forward direction
Vector3D locationAndSome = location.add(dirForward.multiply(0.05f));
//find the edge that the player direction is intersecting
allEdges.remove(currentEdge);
ArrayList<EdgeAndIntersectionPointAndDistance> intersectingEdges = new ArrayList<EdgeAndIntersectionPointAndDistance>();
for (Edge e : allEdges) {
//skip the opposite edge too.
if((e.a == currentEdge.a && e.b == currentEdge.b) ||
(e.b == currentEdge.a && e.a == currentEdge.b))
continue;
Vector3D intPt = Utils.dist3D_Segment_to_Segment(e.a.getVector3D(), e.b.getVector3D(), model.getLocation(), locationAndSome);
if(intPt != null) {
float dist = intPt.minus(locationAndSome).getNorm();
intersectingEdges.add(
new EdgeAndIntersectionPointAndDistance(e,dist,intPt)
);
}
}
EdgeAndIntersectionPointAndDistance bestEdge = null;
float bestDistance = Float.MAX_VALUE;
for (EdgeAndIntersectionPointAndDistance ead : intersectingEdges) {
float absD = ead.distance;
if(absD < bestDistance) {
bestDistance = absD;
bestEdge = ead;
}
}
//find the location on that edge where the player should be
return bestEdge;
}
Of course when the player gets to his next location, he needs to get the correct up-direction and forward direction. This can be taken from the next edge’s vertices that hold normals.
There are some additional issues to traversing the mesh:
- Avoiding hitting other players. Done by not allowing 2 player to inhabit the same edge.
- Collecting bonuses that are on the ground by checking if the player had walked over (or close to) an edge that has a bonus on it
- Up keeping the half-edge structure by updating the edges if they have players/bonuses on them
Make a dent in the world
One more interesting issue is the missiles impact on the world. Naturally, we’d like the missiles that hit the ground to make a dent in the world. Our solution was to take the 1-ring of the hit vertex, and lower all the vertices on the ring in the opposite direction to their normals.
public static void makeADentInTheMesh(Vertex vtx, float amount, IWorldMeshHandler worldMeshHandler) {
//Make a dent in the mesh...
Set<Edge> es = vtx.get2RingOfEdges();
for (Edge ed : es) {
Vector3D v = new Vector3D(ed.a.x,ed.a.y,ed.a.z);
v = v.minus(ed.a.getNormal().multiply(amount));
ed.a.x = v.x; ed.a.y = v.y; ed.a.z = v.z;
v = new Vector3D(ed.b.x,ed.b.y,ed.b.z);
v = v.minus(ed.b.getNormal().multiply(amount));
ed.b.x = v.x; ed.b.y = v.y; ed.b.z = v.z;
//If there's stuff on the edge, move it accordingly
if(ed.playerOnEdge != null) {
ed.playerOnEdge.getModel().fixLocation();
}
if(ed.packageOnEdge != null) {
Utils.fixObjLocationToEdge(ed.packageOnEdge.getModel(), ed);
}
if(ed.treeOnEdge != null) {
Utils.fixObjLocationToEdge(ed.treeOnEdge.getModel(), ed);
}
}
//Recalculate normals - the positions have changed, creating new "up" directions
for (Edge ed : es) {
ed.a.calcNormal();
ed.b.calcNormal();
}
//reset the display list of the world mesh since the vertices and faces have changed
worldMeshHandler.getWorld().getRenderer().setResetList();
}
if pigs (missiles) could fly…
So far I’ve covered mesh oriented movement. Missiles, however, are not mesh-bound – they fly around “freely” above the mesh. To imitate gravity and a “steep course of flight” for the missiles, we use Bezier curves of either 3 or 4 keypoints.
To calc a point on the curve all you need to know is the current time of flight.
protected Vector3D[] mBezierMultiplyV0_V3 = null;
protected Vector3D V0;
protected Vector3D V1;
protected Vector3D V2;
protected Vector3D V3;
protected void calcExpectedFlyTime() {
float distToMove = V3.minus(V0).getNorm(); //total distance to cover
expectedFlyTime = distToMove / flySpeed; //approximate time of flight
}
protected Vector3D getCurrentCurveLocation(float u) {
Vector3D out = null;
out = mBezierMultiplyV0_V3[0].multiply(u * u * u);
out = out.add(mBezierMultiplyV0_V3[1].multiply(u * u));
out = out.add(mBezierMultiplyV0_V3[2].multiply(u));
out = out.add(mBezierMultiplyV0_V3[3]);
return out;
}
private void advanceMissile() {
float u = timeFromLaunch / expectedFlyTime;
Vector3D newLocation = this.getCurrentCurveLocation(u);
this.location = newLocation;
//calc the change of angle
this.dirForward = newLocation.minus(this.prevLocation).getNormalized();
this.dirUp = ((this.dirForward).crossProduct(this.dirLeft)).getNormalized(); //cross-product of left and forward is the new up direction
this.prevLocation = newLocation;
}
Get ready for impact!
I’ve talked about what happens when a missile hits, and about the missile’s course, but how do we know when the missile hits the ground?
We have implemented this using a KD-tree over all the vertices in the world mesh, to check what is the closest vertex to the missile. When the missile gets close enough we check the dot product of the missile’s location and the normal of the surface – when the sign flips the missile hit the ground.
protected void checkForHitWithMesh() {
Vector3D tipLocation = location.add(dirForward.multiply(distToTip));
double[] key = {tipLocation.x, tipLocation.y, tipLocation.z};
//check with KD Tree to get the nearest vertex
Vertex closestVetrex = null;
try {
closestVetrex = VertexKdTree.getVertexKdTree().nearest(key);
} catch (KeySizeException e) {
e.printStackTrace();
return;
}
//check if missile is lost in space...
Vector3D closestVertLocationWorld = aimer.getTransformToMeshLocation().transform(closestVetrex.getVector3D());
if (tipLocation.minus(closestVertLocationWorld).getNorm() > 1) {
projectileHandler.setCurrentProjectile(null);
flightFinished = true;
objNModeHandler.nextMode();
return;
}
//Check if missile is inside ground
if ((closestVetrex.getNormal()).innerProduct(tipLocation.minus(closestVertLocationWorld)) < 0) {
flightFinished = true;
hitMeshAtVertex(closestVetrex);
projectileHandler.setCurrentProjectile(null);
}
}
Particle Shmarticle
Particle systems are a decent way to simulate smoke, fire, water splashes and anything “particley”. We ripped some C code from the net (I can’t remember where, but it was GPLed), again, and ported it to Java.
The only problem is that OpenGL can’t really display particles, you need something that has some kind of surface, or a line. Other options are drawing GL_POINTs, or GLU spheres, but both options either don’t look pleasing or are very costly in terms of performance. So we used GL_TRIANGLE_STRIP to draw small rectangles of random sizes as the particles.
public void drawParticles(GL gl) {
gl.glEnable(GL.GL_BLEND);
gl.glBlendFunc(GL.GL_SRC_ALPHA, GL.GL_ONE_MINUS_SRC_ALPHA);
gl.glDisable(GL.GL_LIGHTING);
for (int i = 0; i < MAX_PARTICLES; i++) {
// Each particle is handled differently depending on whether it's
// alive or not.
Particle particle = m_aParticles[i];
if (particle.isAlive()) {
// This particular particle is alive.
handleLiveParticle(gl, particle);
} else {
// This particular particle is dead.
handleDeadParticle(gl, particle);
}
}
gl.glDisable(GL.GL_BLEND);
gl.glEnable(GL.GL_LIGHTING);
}
private void handleLiveParticle(GL gl, Particle particle) {
// The current location of the particle; Need to account for the
// zoom
// distance so user can zoom in and out the particles.
float x = particle.getXLocation();
float y = particle.getYLocation();
float z = particle.getZLocation();
// Set the color to draw this particle. The particle's life value
// will act as the alpha.
gl.glColor4f(particle.getRed(), particle.getGreen(),
particle.getBlue(), particle.getLife());
// Draw the particle using triangle strips.
gl.glBegin(GL.GL_TRIANGLE_STRIP);
// Map the texture and create the vertices for the particle.
float pSize = (float) Math.random() * particle.getLife();
float r = (float) Math.random() - pSize;
gl.glVertex3f(x + pSize, y + pSize, z + r);
gl.glVertex3f(x - pSize, y + pSize, z + r);
gl.glVertex3f(x + pSize, y - pSize, z - r);
gl.glVertex3f(x - pSize, y - pSize, z - r);
gl.glEnd();
// Update the particles' properties.
updateParticle(particle);
}
Note that we make sure the “particles” are blended into the buffer, as particles’ color is fading as they near death.
Sum up
OK, I’ve tried to share most of the interesting points in the making of the game. The code is downloadable from the Google code SVN repo. And here’s a short video explaining some aspects of playing the game:
Thanks for tuning in!
Roy.