Technical Details

I haven't updated this file recently. Most notably, I haven't added any VBO information here, so it still is about display lists. I'll update it when I get a chance.

This page will eventually give the technical details to how Crown and Cutlass works. I'm not doing anything unusual or special, but I thought details might be worthwhile. There isn't much here for now, but I'll keep adding more. If you have a specific question that I don't cover in the readme, email me and I'll put up the details.


The water is really simple. It is far from "realistic" but it was easy to do and gives a fairly good effect. It is basically just a heightmap. I generate a 2-dimensional sine wave for the heights. Each frame I pass the water draw function two values, which are a sine and a cosine so they range from -1 to 1. Each frame, I multiply the height of each point in the water heightmap by the sine, which results in sort of wave-like motion. I also use both the sine and the cosine to move the texture in a circle. The moving texture really adds a lot to the effect. It's simple and cheesy, but it conveys the idea that it is water. I have profiled the game several times, and drawing the water is by far the slowest thing to draw. I need to improve it when I get a chance.


My terrain is done with heightmapping. The heightmap is 826x512. No LOD is done, which is ok since the view is locked at a high angle. If you could look parallel to the ground, you would be able to see much more distance (ie more triangles). However since you can only see a small chunk of the terrain at a time, LOD is not needed.

I implemented a frustum culled quad-tree for my terrain. I figured that an oct-tree would be overkill for a heightmap. I'm not sure if that is true, but the quad-tree works fine for my purposes. I don't claim that this is perfect, but this is the idea of how I go about it.

I have several classes which help out here: Point (just a point in 3D space), QuadNode (a node in the quad-tree), QuadBox (the bounding box for a QuadNode), Frustum (a class for frustum culling) and Terrain (main terrain object, contains a pointer to the root QuadNode). The frustum code is all based off of Mark Morley's frustum culling tutorial.

The Point class is basically just a way to hold an x, y, z coordinate, so that I can pass one value instead of three. Nothing really fancy is going on.

The QuadBox is basically just 8 pointers to points. I made the pointers public, so other classes just modify them directly. I should probably go back and change this at some point to make it more "object-oriented". I probably also should just make an array of 8 pointers to Points, instead of 8 separate variables. Oh well.

The QuadNode is sort of where the magic happens. As far as data structures go, it contains four pointers to it's child QuadNodes, a pointer to it's QuadBox (basically, the boundaries of this node), and a variable to hold a display list. It is important to remember that the children pointers may or may not be set and the display list may or may not be created, depending on whether the node is a leaf or not. A leaf node's children are all NULL, and it's display list is valid (ie it gets created). A non-leaf node's children are non-NULL (ie they get created) and the display list is invalid.

When a QuadNode is created, the constructor is passed a pointer to the Terrain class, and a pointer to it's QuadBox. The Terrain pointer is used to generated the display list if necessary, and to calculate the height of the box. The constructor calculates the size of the QuadBox, and if it is smaller then a certain size it is a leaf node, and it calls a function in the Terrain class which generates the display list for a certain QuadBox. If the node's QuadBox is too big (so it is not a leaf), then it divides the box into 4 pieces and creates a new child QuadNode with each of the 4 new boxes.

The QuadNode also includes a draw function which is passed a pointer to the Frustum class. When it is called, it checks to see if it's QuadBox is visible in the current frustum. For details on this, read Mark Morley's frustum culling tutorial I linked to above or below. If it is, then it calls all 4 of it's children's draw function. If is not visible, there is no reason to check it's children (since they are just parts of the parent's box), so it just returns. This works out when you call draw on the root. It sees that a least some of the parent is visible, and continues on down the tree. If the player is in one corner of the map, you can see how 3/4 of the terrain can get eliminated really quickly.

The Terrain class is pretty much just to manage the actual heightmap, although it also contains a pointer to the root of the quad-tree. In the Terrain constructor, after the terrain has been loaded, the normals calculated, etc., it just creates a QuadBox around the entire terrain, and then creates a new QuadNode with that box. The root QuadNode's constructor then takes care of generating the rest of the tree, like I described in the QuadNode constructor section.

The Terrain class is also used by the quad-tree to generate the display list for a leaf box. That is pretty simple. You pretty much use the same code that you would use to diplay the entire terrain, but give the loops different starting values and end conditions (ie start at a corner of the QuadBox instead of 0, and end at the other side of the QuadBox instead of the width of the terrain). I also use it to determine what the minimum and maximum height of a box should be. I just step through the height values of the quad box and return the highest and the lowest found. Note that if you can do this almost for free when you are generating the display list.

Anyway, this is brief and thrown together. I will try to flush it out, add some code, and add some helpful figures. Let me know if something doesn't make sense and I will try to improve it.

Mark Morley's frustum culling tutorial
I used this tutorial (and modified some of the code) for the frustum culling of the terrain's quadtree nodes. I'd just link straight to his page, but his server seems to be down.
Explanation of calculating the planes of the frustum
This is a very informative document that explains most of the stuff Mark Morley said "you don't really need to understand" to do frustum culling. I found this document helpful.

Game States

All of the tutorials and books that I read about OpenGL were just demos to show how to do one thing. They didn't cover how to switch from the game to a menu, or from the main game to a different section of the game. After some thinking and a slightly helpful forum post, I decided to implement a "Game State" class. I wrote a base class which other classes extend. I'll explain all of these individually, but the base class includes a pointer to the previous state, a pointer to the main menu state, a pointer to the main current pointer, and pointers to the window width and height. The previous pointer is used to return to the previous (big suprise, huh?) state once the current state has finished or is aborted. Although I haven't made really made use of this yet, it will be helpful, for example, for going from a naval battle, back to the normal sailing state. The main menu pointer is there just so the user can hit escape (or whatever) at any point and get to the main menu. The pointer to the current pointer is a little bit harder to explain. The primary purpose of the main function is to initialize the game (SDL, OpenGL, etc), and then loop until the user quits. To do this, I made a pointer to a state called current. Every time through the main game loop, all that happens is current->loop() is called. Each derived state class must implement that loop function to do what it needs to, perhaps display the frame and handle user input. The pointer to the main current pointer allows states to basically hand control over to another state. I'll re-write this and make it clearer (as well as more complete) later.


These are game/graphics programming related sites which I have found particularly helpful or interesting: