"Amped 2" Tree Optimizations

If you've ever played "Amped" or "Amped 2," one thing you will notice is that there are a lot of trees around. They have a lot of detail, and since you can see almost the entire mountain from the top, there has to be some optimization going on here, right? Right you are. Some pretty interesting decisions were made in the interest of shaving memory and processing requirements.

Several things needed to be taken into account when working with the trees. First, we have visibility. Second, we have collision detection. Third, we have level-of-detail. Finally, we have memory minimization. All of these were solved using the same solution, but there were side effects.

Now normally, visibility and collision detection on a surface that is essentially 2D can be easily handled through use of a quadtree.

For the visibility, you check the top-level node to see if any part of that axis-aligned bounding box (AABB) is within the view frustrum. If it is, you continue to traverse the quadtree until you find an AABB that is not in the frustrum. Finally, you render what was in the frustrum.

For collision detection, you normally traverse the quadtree until you end up in the smallest node that contains your character, then detect collisions with objects inside your quadtree node.

Level of detail is not as easy, however, due to you having to check distance to each object in all visible frustrum nodes. Plus, quadtrees, while small, are not extremely memory efficient if you end up subdividing too many times.

The solution ended up being very simple. Trees on real-life ski trails are usually grouped into clusters. Why not group the trees in the engine? Trees were grouped into cylinders. Each cylinder contained between 5 and 20 trees. Plus, there was a maximum size for the cylinders. So, for visibility, simply clip the center point of each cylinder to an extended frustrum.

For collision detection, do an approximate distance calculation to each cylinder's center point on a 2D plane. (I'm not sure if they ended up doing a quadtree for the center points or not to reduce the work.) If you're close or within the cylinder, then check to see if you are below the top boundary for the cylinder. (That way, if you're flying over the trees, you won't be colliding with them.) If you are within the cylinder, then test against the collision mesh for each tree.

For level of detail, check the distance from the camera to the center point of the cylinder. Use that distance to calculate the LOD for the entire cluster.

Finally, memory optimization. The trees are instanced geometry, so only one copy of the mesh is in memory at any one time. The tree coordinates are essentially a list in memory. Your cylinders can end up taking about twenty bytes each:

(Assuming Z=Up)
4 bytes: X Coordinate, Center of Cylinder
4 bytes: Y Coordinate, Center of Cylinder
4 bytes: Z max, Top of Cylinder
4 bytes: Number of trees in cluster
4 bytes: Offset in trees list for first tree

Now for the side effects. Occasionally, we'd get a tree that wasn't contained within a cylinder. We'd get varied side effects. Occasionally, we'd see the tree, but not be able to collide with it. Other times, we would not be able to see the tree, but we'd keep running into it. What finally ended up happening if I remember right is than an extra post-processing step was taken in the level creation tools that would check each tree to ensure it was in a cylinder, and if it wasn't, a special 1-tree cylinder was created just for it.