Fractal Terrain Generation and Deformation
Harrison McKenzie Chapter
CPE 471 – Winter 07 -- Dr. Wood
Summary: This program is designed to generate pseudo-random, fractal terrain within a given range. Once generated, this terrain is deformable by firing projectiles at it, which changes its shape where it was struck. This deformation follows a pattern similar to the recursive subdivision in the generation, to give the deformations a smooth appearance.
Terrain Generation
These pictures show the effects that can be achieved using a relatively simple subdivision strategy, as follows:
For a square, call Subdivide on its top left and bottom right corners, specifying a variance range and a depth.
Subdivide will take this information and either compose four new squares out of this and recur, or find that it is at the lowest level and return.
Additionally, Subdivide will attempt (if the depth is not the last), to modify the middle point of each square that it is handed.
This calculation is done by multiplying a random value between zero and one by the variance range for that level of recursion.
Subdivide will use this information in future boxes by interpolating the midpoint of each line segment fo the box it is handed between each endpoint.
This allows for terrain which is random but relatively continueous with its neighbors.
Deformation
The terrain generated by the fractal generator composes a large mesh of single points. We can think of all nearby points as being connected with their neighboars, which gives a mesh that looks like this:
In this view one can easily see the relationships between each piece of the mesh.
This relationship is important because it allows us to push on one of these points and radiate the motion outward to all the points nearby.
Thus, when a projectile is detected to have touched the terrain (By being with radius length of a vertex, in this case), its energy is transferred to the point, and then to all points surrounding it, and all points surrounding them. Each step of this radiation, the energy which is passed on is divided by four, so it quickly reaches a very small value and the recursion cuts off.
This picture shows several divots, with another projectile in the air moving towards the terrain, in wireframe mode (Squint hard):
While this execution is no mean feat, at this level, it is reproduced relatively well by using a simple heighmap, rather than a vast array of true points which store all their X, Y, and Z values.
What this allows us to do, however, which a heightmap does not, is generate spaces which are concave, such as the Cave in the next pictures:
It turns out, however, that when we deform the terrain, we do so by changing the positions of the vertices. This triggers a recalculation of the normals for those vertices, which isn't a terribly intense calcation, so this approach would seem workable for a larger scale. The problem, however, lies in the continued ability to detect collisions. Once points have been deformed, they grow apart so it is easier to sneak things through them. This symptom could be solved by using real polygon-normal-extent collision detection, but even so, the number of values that one is required to check grows very fast with the complexity of the scene.
Ideally, we could use a scheme like Binary Space partitioning to greatly reduce the amount of work we had to do for collision detection. However, the dynamic nature of the point mesh foils this plan: the points are not garunteed to remain the the same partitions that they were before. Thus, one must create a sorting method to remap the points back into a canonical volume. Further, doing this would prove difficult given that concavity is permitted for the geometry.
Building / Use
This program is only tested under Linux, so your experience may vary on other setups.
Untar the source to whatever directory you want; then simply run the included Makefile; the binary will be a.out, (or) your system default.
The program is run from the shell, where from it expects 4 arguments:
A width - Of the initial box for division.
A seed – To setup the RNG.
A depth – How recursions to perform
A range – How far values can vary at Subdivision.
The user is placed at the helm of a small tank, which is controlled by WADS:
W – Go forward along terrain
S – Go backward along terrain
A – Turn treads to the left
D – Turn treads to the right
The tank's gun can be moved independently of the tank body by looking around with the mouse.
The gun can be fired by pressing the left mouse button, which generates a projectile along the viewing vector.
Additionally, there are some keyboard commands for easier diagnostic work:
o – toggles wireframe mode
p – toggle point mode
n – toggle normal drawing
f - “Fly mode”: Use this to escape the tank you you just want to play around with the terrain; in this mode, WADS moves you forward/backward along the camera, and strafes to the sides of the camera.