[WF-General] Terrain Update sec: unclassified

McGinnes, Damien Damien.McGinnes at defence.gov.au
Thu Apr 10 13:13:15 PDT 2003

Heres a (not so) short report on recent Mercator and Stage changes, and a
proposed way forward.

The original Mercator algorithm was prototyped by Munin, and implemented in
Mercator by Alriddoch.

I implemented a small change to the mercator algorithm so that tiles are now
generated in isolation to neighbouring tiles. This method means that
generation a least an order of magnitude faster (maybe two!!). This is not
due to optimising etc, merely an algorithm change.

for an overview of the approach, see

for a pic of the result, see
This pic by Alridddoch shows a 2x2 patch of terrain generated from 9 control
points and two global parameters (roughness and falloff)  11 floats => 16384
floats. Not bad ;)

The algorithm still has some issues:
* Identical neighbouring heightpoints will result a flat terrain seam
but this is only noticable when the tile is steep
* tiles with wildly varying slopes may have a noticable edge (change in
gradient) at the seam.
* roughness/falloff are global parameters

Some additional work can be done to improve these things (in fact a demo of
variable roughness is implemented in cvs:forge/scratchpad/damien, and using
neighbouring control points would sort out the other issues)  
but until further use is made of mercator, there is little point in further
tweaking the algorithm.

Some additional work has been put into stage to support terrain. (not all
checked in yet)
* Stage limits the view of terrain to a grid immediately surrounding the
* Stage passes new control points to the client when they come into view,
and notifies when points go out of view.
* Stage uses hysteresis to ensure that the view doesnt toggle rapidly
between points that are in and out of view 
(http://ourworld.compuserve.com/homepages/g_knott/elect344.htm is a kind of
example of hysteresis)

* replace the fake terrain object with a real one that is persisted to the
* a way of editing (create, delete, remove) control points. => in a RIM
* collision with terrain - initially, this could assume each object is a
point at its origin and collide the point with the terrain. (for a moving
object this effectively breaks down to an intersection of a ray with the
* a cache mechanism so that the whole map doesnt have to be in RAM. Generate
tiles on the fly as needed, expire them in an LRU fashion. (this should be a
function of mercator)
* rework of collision to use real shapes, instead of points.

Mercator TODO
* LRU tile cache
* variable roughness
* allow for variable tile resolution
harder - apply modifiers to terrain
* terrain addition/subtraction to allow for terrain morphing
* transparent patches to allow for tunnels/caves (not sure on this one)
* allow for non fractal tiles (hand drawn ones inserted into the landscape)

* support reveal/conceal (or obscure, whatever it is called)

Clients TODO:
* support mercator terrain
* accept control points from the server

Any comments?


More information about the General mailing list