HomeGalleryDownloadHow does it work?UtilitiesImprint/Contact/Privacy |

Toetensen landscape renderingThis is a brief description of the algorithm i used to render the landscape for the toetensen-project. Data storageThe 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 meshFor 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 WhistlesSome 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 synchronisationTo 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 deathIf 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. |