Search for the Legendary Chalice
CSC 476
Final Project
Professor: Zoë Wood
Student: Jonathan DeKlotz
Introduction
Click on the following link
to download the program:
jdeklotz_final_proj_files\chalice.zip
Introduction
First-off I just want to
excuse the cheesy name. I had to come up with game-play aspects for my nice 3D world,
so I chose a cliché “search for the legendary item” theme. It was originally
going to be more in-depth, with an item inventory and more interaction with the
world, but there were time and man-power limitations.
It its current
manifestation, the goal of the game is simply to search the world for the
legendary chalice. You win the game when you find it. You can walk around (even
under-water), in the course of your search. The physics engine had many bugs so
it has been stripped from my released version of the game and an ultra-simple
physics model is used instead. Basically you can walk anywhere and you can’t
jump off the ground. Axis-aligned bounding box collision detection is used to
detect when you have collided with items in the world.
Technical Features
·
Dynamic level of
detail terrain with screen-distortion approximation and proximity error metric
·
Texture map for
terrain is generated based on highest level of detail and applied to all levels
of detail to increase apparent visible detail
·
Multi-texturing
to combine generated terrain texture with a finer detail texture map
·
Palm trees and
Joshua trees (loaded from 3ds files)
·
Terrain
collision detection (which does bi-linear interpolation on the most detailed
terrain level for smooth traversal of the terrain).
·
Skybox
·
Alpha-blended
ocean
·
View Frustum
Culling
Dynamic Level of Detail Terrain
The most notable feature
of “Chalice” is its dynamic level of detail terrain. My implementation uses the
main concepts of ROAM terrain (Real-time Optimally Adapting Meshes) and I’ve
added my own twists. The motivation behind dynamic level of detail terrain is
that you don’t want to have to draw every polygon in the terrain at the finest
level of detail. Drawing the entire terrain (or even the portion of it within
the view frustum) at the finest level of detail would be terribly slow. What we
want is a terrain that changes depending on the camera’s position and
orientation.
The main idea is to
triangulate the height-map data so that fewer triangles are given to farther away
regions and more triangles are given to close regions. One other metric is
used, which is hierarchical volumetric distortion (which, when combined with
the proximity metric gives you a screen-distortion metric). With hierarchical
volumetric distortion, at every node of the binary triangle tree used to
hierarchically partition the terrain, a value is stored that is computed by
finding the volume of the pyramid formed between the triangle it represents and
the represented triangles of its two children nodes. Also, the calculation of
the volumetric distortion values is recursive so that a node higher up in the
tree (closer to the root) is the sum of its own pyramid’s volume and all of the
volumes of all its children nodes’ pyramids.
The reason for the recursive
nature of the calculation is so that a potential significant feature of the
terrain that is only visible in a significantly finer level of detail (more
than 1 level of detail removed from the parent node) will not be lost during
triangulation simply because the parent node had a low volumetric distortion
value. Imagine a very smooth region of the terrain with a moderately small bump
on it. The size of the bump requires a level of detail several layers deeper
than that required to appropriately triangulate the smooth region, but if we
triangulate that region coarsely, we would lose the bump. The recursive nature
of the calculation prevents this from happening, so the bump would be
triangulated at an appropriate level of detail.
As far as implementation
goes, I use a dual-priority-queue approach to drive the splits and merges. I
follow the concepts of ROAM fairly closely. I implemented my own priority queue
utility class since I found the STL’s inadequate. My priority queue allows
priority adjustments and random logarithmic-time node removals and it’s a lot
faster than the STL priority queue.
The terrain height map was
generated using the diamond-square fractal algorithm. In order to get the
islands just right, I exported the fractal height map as a monochrome bitmap
and manually edited it in Photoshop. The result is a nice island terrain height
map. Here are some top-down views that demonstrate the effects of dynamic level
of detail terrain. You can see how both proximity and volumetric distortion
contribute to the triangulation.
Image 0 –
Triangulation of the terrain from top view; camera is located in north-west
region
Image 1 – Triangulation of the terrain from top view;
camera is located in middle region
Another difficulty in
dynamically triangulating the terrain is that there are often annoying
“popping” effects that come along with the rapid splitting and merging of
triangles in the triangulation. I employed a number of my own ideas to reduce
popping and the result was pretty pleasing.
The method that I found
works the best is to do a volumetric-distortion-only triangulation immediately
after loading the height map using about 8 times as many triangles as you would
want rendered per frame (I currently render about 16,000 triangles per frame
for the terrain). Proximity will have no effect on this triangulation since
we’re not going to render this one and we’re not using proximity in the priority
calculations for this triangulation. The result is a massive triangulation that
prioritizes detail, so more triangles are given to higher-detailed or rougher
regions of the terrain. This triangulation is now used as the base
triangulation, so the binary triangle tree is then trimmed so that nothing of
any higher-level of detail (or lower in the tree) will ever be rendered. The
leaf nodes are then marked so that we won’t attempt to traverse their children
later.
Now when we run the
frame-to-frame optimizer, no regions of the terrain can be triangulated at a
courser level than our pre-calculated base triangulation since the binary
triangle tree has been trimmed. Since we are requesting fewer triangles during
the real-time triangulation, the result is that popping is virtually eliminated
in regions of the terrain close to the camera. There is still popping in the
distance, but this is pretty much inevitable. My original idea was to “lock”
the portion of the triangulation within a certain radius around the camera, but
it didn’t work as good as trimming the binary triangle tree based on volumetric
distortion, because the region of the terrain immediately outside the “locked”
region still suffered from much popping and shuffling.
Image 2 – Wire-frame overlay; island with palm trees
Image 3 – Wire-frame overlay; dynamic level of detail
terrain
Image 4 –
Wire-frame overlay; dynamic level of detail terrain
The terrain has two texture
maps applied to it: a massive terrain color map and a small tiled detail
texture. The large texture map is a 512 by 512 image that is generated from the
terrain height map. It basically converts a 1D texture (varying color values
for height) into a 2D texture map that can be applied to the triangulation on
the fly. The advantage of doing this is to increase color detail even in
coarsely triangulated regions of the terrain. You can see this effect in the
images above where larger triangles have more detail defined by the applied
texture map.
The detail texture map is a
small tiled map to give the terrain the impression of fine details.
Screenshots
Image 5 –
Joshua trees
Image 6 – View of island from underwater
Image 7 – Underwater view
Image 8 –
Cliff and Joshua tree
Image 9 –
Island bay
Image 10 –
Underwater terrain
Image 11 –
View of island
Image 12 –
Beach
Image 13 –
Underwater crevices
Image 14 –
Palm trees on the beach
Conclusion
I had originally planned to
do a lot more (as usual, it seems), but ran out of time. Overall I am very
pleased with the dynamic level of detail terrain. There are, however, a number
of shortcomings in the ROAM approach for terrain. The most notable is the
requirement for “immediate-mode” OpenGL programming (which we have all been
doing in CSC 471 and 476 up to this point). A better way to store and display
terrain is by storing the vertex data on the GPU in vertex buffers and indexing
into that data using triangle strips. This, of course, is not possible with
ROAM-style dynamic LOD terrain implementations, but there is another approach
currently being researched by Hugues Hoppe called Geometry Clipmapping, which
borrows concepts from a 2D image-viewing algorithm called Image Clipmapping
(which works a lot like mip-mapping). With Geometry Clipmapping it is much
easier to buffer vertices on the GPU and index them using triangle strips.
References
http://research.microsoft.com/~hoppe/