This is a brief description of the algorithm
i used to render the landscape for the toetensen-project.Data storage
The world is arranged in a triangular map (displayed by the triangles on the bottom of the sketch). Through this intersection space is divided into triangular columns. the nodes of the triangluar grid represent the possible horizontal (x/z) coordinate for sticks (and for the vertices for the mesh) and are called corners. As the boolean volume representation is horizontally quantized by the resolution of the triangular grid, for representing the alternating filled and empty intervals to the top a run-length-encoding like compression scheme is used. the filled volume (depicted as thick red lines) is represented by "sticks" which are arranged in a linked list for each corner. while this method is quite memory intense (4 bytes needed to point to the successor for each stick + 4 bytes minimum consumption for each corner (pointer to the list head) - it has the advantage that sticks can be added and removed dynamically without the need to move blocks of memory. The red lines are called sticks and the gray lines (=the empty space between two sticks in the linked list) are called gaps.
Building the mesh
For building the mesh, every triangular Column of volume is processed seperatly. In the first step, the edges of the mesh are determined. Note that each of the two tips of a stick will result in one vertex which is shared throughout neighbour columns. For determining the edges, the left- an right corners of each of the three sides of the volume column are processed in a down- up manner as you see. two neighbour sticks that intersect vertically are candidates for connection. Note that the lower-end vertex of a stick can only be used for "ceiling"-edges (shown pink) while the upper-end vertex can only be used for a "floor"-edges (shown blue). Some vertices will remain without a "partner" for building an edge. This will happen on floor-ceiling transitions and ceiling-floor transitions. in this case an extra vertex has to be introduced, its y-coordinate is put in the middle of the currently processed stick or gap. a resulting double-edge for a gap is shown in light green on the sketch, for a stick in dark-green. In most cases the edges will construct simple, unambiguous triangles. In some cases complex spiral-staircase shapes can occur. The edges always will be arranged in closed, non intersecting loops so the most easy algorithm can be used for triangulation: for each loop build a triangle strip. start with the lowest vertex and go up.
Bells 'n Whistles
Some extras of the implementation are:
-Shadow (Stick has successor yes/no)
-Backface culling
-Frustrum culling and geometric level of detail for good fps
-Some unrecoverable bugs (=sometimes wrong vertex normals) in the lod neating :)
Network synchronisation
To have all players using the same map, the history of map-modifying events is stored and distributed to the clients. If someone connects after the game has already started, he has to download the complete history first, which luckily should not be too much in a regular game.
Avoiding entropy death
If the mesh is getting too complicated in a specific region, it can be simplified in a funny way by a vertical collapse transformation covering the problematic area - shown to the player as earthquake or nuke event.