覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧
Title - Terrain Engine 2.0 - a new beginning.
Dated - Jan. 6, 2006
Author- EvilHomer

This document describes a proposed system for storing
terrain tile data suitable for dynamic loading with respect
to the 2D implementation of SuperFrustum Algorithm.

Refer to the following URL:
http://www.gamedev.net/reference/articles/article2012.asp

覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧
DESCRIPTION OF RESOURCES
覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧
The bitmap data for our terrains is originally sourced from
several 512x512x8 images. Each of these can be imagined
as a grid of 16x16 Tiles, each Tile being 32x32 Pixels.

A PAGE OF TERRAIN TILES IS SOURCED FROM A BITMAP.

As a preprocessing step, we parcel these bitmaps on a per-Tile
basis, creating 256 small bitmaps, which are saved to disk
in raw format (without bitmap headers).
The filenames given to a Tile's bitmap indicates which Page
it belongs to, and its array coordinates on that Page.

TERRAIN TILES ARE STORED ON DISK WITH MEANINGFUL NAMES.

The reason we do this is to enable us to load ONLY the
bitmap data required for a particular Tile, rather than being
forced to load and unload entire Pages unnecessarily.
Furthermore, this enables us to INSTANCE terrain tiles.

There exists a MASTER TILEMAP which describes the entire
terrain. It is a large 2D array of TILE REFERENCES,
which include Tile Identifiers and Material/Texture info.
This array of data is stored permanently on disk.
The extents of the Master TileMap are predetermined
for a given "game level", and are Wrapped in order to
create an illusion of continuity within the game.

There also exists a RUNTIME TILELIST which stores a list
of data objects from the Master map in memory at runtime.
This list includes ONLY those Tiles which are either
partially or totally within the Camera View Frustum.
This list is dynamically updated during runtime.

覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧
DESCRIPTION OF REQUIREMENTS
覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧
Everything hinges on the ability to determine the View Frustum.
We simply MUST be able to extract a Frustum from the Camera's
current View Matrix.
Note that the SuperFrustum is created by first finding
the absolute extents of the Frustum on the XZ plane
(view from above) and then extending them slightly.
This should always yield a large 2D Triangle (please
refer to the bottom image at the URL previously given).

We generate from the Frustum a list of Tile Identifiers for
those Tiles which are within the Frustum.
This list is then applied as an inclusive filter to
the RunTime TileList in order to identify:
-which Tiles need to be dynamically Loaded
-which Tiles need to be dynamically UnLoaded

We now dynamically update the RunTime TileList.
Are we now ready to Render the list?
That depends on one more design consideration:
Do we tesselate the terrain tiles dynamically when loaded,
or do we store geometry data within each Tile datafile?

This is really a tradeoff between size and speed.
The former requires more cpu time, while the latter
requires more disk storage.

We must note that if we intend to store geometry within
each Tile datafile, that geometry does not use Absolute
(World-Relative) coordinates, they are relative to
the Origin of that Tile, so that Tiles retain the ability
to be Instanced at various locations.

This way, a vast grassy plain can be created by simply
instancing ONE tile in SEVERAL locations.

At runtime, each Tile is transformed into position
via a translation matrix, and then rendered in situ.

The cost of doing this is that collision detections
must be performed relative to each Tile being rendered.
That is to say, each IntersectionTest Ray must be
tranformed into "tile model space" prior to testing.

覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧覧
I am keen to hear feedback regarding this proposal.
Do you foresee problems?
Can you suggest improvements?


Posted on 2006-01-06 00:54:12 by Homer
SPLINE TESSELATION OF TERRAIN TILES

I have an extension of this proposal to describe.
It is possible to implement runtime (but not quite realtime) tesselation of the terrain tiles which support Dynamic Level of Density (DLOD) and based on catmull-rom splines.
Catmull-Rom splines create smoother curves than any other algo I know of, and require far fewer control-points than for example a cubic bezier spline.

Before I go into detail, let's step back outside of the terrain for a moment.
We effectively have a large 2D array of heightmap values which correspond directly to pixels sourced from a large bitmap (or a number of smaller bitmaps, stitched together).
Furthermore, each heightmap value corresponds to a terrain vertex.
Finally, each four terrain vertices correspond to a terrain tile.

Terrain tiles are NOT simply geometric quads.
They are larger, each terrain tile describes four control points between which we would normally interpolate to create a mesh of quads whose level of densite (LOD) is 1/N

EG for LOD=1, no interpolation takes place, the Tile describes a geometric quad.
But for LOD=2, we interpolate such that the Tile describes FOUR geometric quads.
And for LOD=3, we interpolate such that the Tile describes NINE geometric quads.

Simply interpolating quadmeshes ourselves is fine, but we can create a much smoother terrain if we use Catmull-Rom splines to interpolate the mesh.

CatmullRom splines each require AT LEAST four control points.
This means that we can't create geometry using the outermost pixels on the heightmap (unless we wrap the heightmap, which I already stated that we will).
We can consider that each Edge of a Tile represents two controlpoints of a Spline, with the other ControlPoints belonging to the neighbouring Tiles.
With that in mind, we can imagine a 3D surface which is defined by interpolating between these Edge Splines.

The following crap ascii art describes how eight heighmap values are required to create four edge splines. The Tile we are interested in is the middle one.

#=Vertex defining the corners of our Tile
@=Vertex belonging to a Neighbour Tile
O=Vertex we don't care about

O-------@-------@-------O
|        |        |        |
|        |        |        |
@-------#--------#-------@
|        |        |        |
|        |        |        |
@-------#--------#-------@
|        |        |        |
|        |        |        |
O-------@-------@-------O

In order to reduce cpu overhead, we only tesselate Tiles if their LOD changes (and logically, this will occur when they are created/loaded).
As the player's camera moves about the world, we can increase and decrease the LOD of each Tile based on the distance from the Camera's origin.

Having determined that we can quite easily describe the Edge Splines of each Tile, it should also be obvious that we can generate a mesh of any LOD we choose by interpolating along the Edge Splines. Typically, the LOD will be 1, and we can totally ignore everything relating to splines and tesselating, and just describe the geometry for a Tile as two triangles. But when we are closer to a particular Tile, we can increase the LOD dynamically and at relatively low cost.
There will be no splitting and joining of triangles as found in the ROAM and some other DLOD algorithms.. and there is little if no incentive in supporting adjacency information.
We generate a mesh for each Tile when it is loaded/created, and regenerate it (from its own and the nearest neighbouring controlpoints) ONLY if its LOD is changed.



Posted on 2006-01-06 06:53:23 by Homer
Lets discuss what happens when the user moves or rotates the Camera (changes the view).
This should be called "How to dynamically resample a HeightMap based on the Camera View".

When we detect that the view has changed, we rebuild the Frustum (code provided in another thread on this forum). As far as the Terrain is concerned, we are particularly interested in the Vertices which form the corners of the Frustum, rather than its Planes.

Having determined the eight 3D vertices of the Frustum, our first mission is to find an imaginary 2D rectangle which encompasses the Frustum on the XZ plane (the top view).

This is actually very easy - we find the lowest and highest values in X and Z from all the eight vertices. The resulting 2D vectors are the "topleft" and "bottomright" corners of the imaginary 2D rectangle.

Now we have found the region of Terrain we are interested in - right? Wrong.
We have eliminated a lot of the world, but we can eliminate more, since we only really care about whats inside the 2D SuperFrustum...
Let's just disregard that fact for now.

We are really trying to determine which Terrain ControlPoints are inside our SuperFrustum.
In order to do that, we need to know what Scaling factor is being applied to the Terrain.
Remember that the ControlPoints are sourced from a bitmap, and multiplied by some scaling factor in order to make the terrain larger in X and Z.
We must now do the opposite - if we take our 2D rectangle and divide its 2D coordinates by the scaling factor, we have in fact mapped the viewable Terrain back onto the source bitmap - ie, our rectangle then has a one to one scale against the bitmap, and represents XY pixel coordinates - right? Almost. Assuming that the Terrain was originally centralized so that the World origin is in the middle of the Terrain (by centering the origin of the 2D bitmap), we must again do the opposite - that is, make the 2D coordinates relative to the topleft corner of the bitmap.
We've done it - our rectangle now encompasses all the pixels on the source bitmap which represent all the ControlPoints in the viewable terrain.
We need to make a list of them.
Except for the first time we do it, we will have an existing list of them too (here's one I prepared earlier).
We need to compare these lists - we want to identify which controlpoints are no longer viewable, and which are new.
For new ones, we must tesselate between them as described in the previous posting, in order to generate renderable geometry.
For old ones, we can either toss them out immediately, or via a counter, cache them for a while, until they are well and truly redundant (we also tag them as being offscreen).
While we are doing this list filtering, we might also like to compare the distances of each controlpoint to the camera origin. We might decide to modify the level of density of some geometry by re-tesselating it when it becomes close or distant from the camera.

Well guys, what do you think?

Posted on 2006-01-07 09:25:23 by Homer
sounds good

use precomputed cos scaled to fit between x-x2 and y-y2 ?

question is, shouldnt that look better with lower-resolution map, with more LOD smoothing?
and less data to readfromdisk, better performance?
Posted on 2006-01-08 05:48:45 by daydreamer
No cos is too simplistic, splines are much more hyperbolic - they are curves, not arcs.
You have realized that much of the geometry can be generated via the splines - far more than we can describe if we only used the original heightmap (bitmap) data.
The size of the entire world is dependant apon the amount of bitmap information we have, and the aim is to handle massive worlds without needing to worry about how much we can store in memory.
Rather than stitch together smaller bitmaps and load and unload them dynamically, we can support one extremely large bitmap, and sample it directly from disk on demand - we don't need to keep it in memory, so we don't need to split it up, and the load times are more constant - there is no "pause" while we move from one section of world to another, as there is no need to load and unload resources (I am speaking purely about the terrain here).

Posted on 2006-01-08 07:41:47 by Homer

No cos is too simplistic, splines are much more hyperbolic - they are curves, not arcs.
You have realized that much of the geometry can be generated via the splines - far more than we can describe if we only used the original heightmap (bitmap) data.
The size of the entire world is dependant apon the amount of bitmap information we have, and the aim is to handle massive worlds without needing to worry about how much we can store in memory.
Rather than stitch together smaller bitmaps and load and unload them dynamically, we can support one extremely large bitmap, and sample it directly from disk on demand - we don't need to keep it in memory, so we don't need to split it up, and the load times are more constant - there is no "pause" while we move from one section of world to another, as there is no need to load and unload resources (I am speaking purely about the terrain here).



I just had my sea-animation almost finished and now I must redo it setting my goal higher, offcourse get rid of cos and create a nice surfwave look


Posted on 2006-01-08 11:31:24 by daydreamer
I've recently been working with dx9, helping with a vc++ 3d engine, it's been a challenge since I have zero prior knowledge about game/3d/directx developement.

I have some questions,

What kind of vertex format and texturing for your terrain engine are you thinking about? How will rendering work, index buffered or not?

Resampling a heightmap every view change wouldn't you also have to recalc any detailing texture coordinates as well? I'd think this would be too cpu intensive. Unless you used a large terrain texture (in which case the texture coordinates would be static) and then some sort of vertex shadar for detail?

While your culling using the frustum, would the camera orientation affect the efficiency of the implementation? For instance the camera moving along the ground's rectangle would be different vertices then if the camera was on top of a hill looking downward. This type of situation would force you to interpolate using all the vertices.

Would you be able to implement collision detection or physics (simple gravity even) with this (load as you go) type of terrain engine. For instance if geometry was moving from out of the view into view since out of view vertices may not be loaded yet.

I ask only because these questions will most likely come up with I'm asked to 'hack' together a terrain engine for the project I'm working on.
Posted on 2006-01-08 18:31:10 by r22
What kind of vertex format and texturing for your terrain engine are you thinking about? How will rendering work, index buffered or not?


I intend to use an fvf which incorporates pervertex normals for better lighting, and several sets of uv values for texture layering. The geometry is stored as trianglestrips but as for indexing, it will likely be unnecessary since we don't have copious amounts of vertex data to contend with (unless we are moving very fast).

Resampling a heightmap every view change wouldn't you also have to recalc any detailing texture coordinates as well? I'd think this would be too cpu intensive. Unless you used a large terrain texture (in which case the texture coordinates would be static) and then some sort of vertex shadar for detail?


The uv values for terrain detail textures are to be precalculated and stored in a separate file, and streamed similarly to the heightfield data. They are static, and only the uv values at the controlpoints need to be recalled, all other uv values are calculated at runtime, but only when the LOD of a given terrain tile changes (if DLOD is enabled). "Splat" textures are another story.

While your culling using the frustum, would the camera orientation affect the efficiency of the implementation? For instance the camera moving along the ground's rectangle would be different vertices then if the camera was on top of a hill looking downward. This type of situation would force you to interpolate using all the vertices.


We are not culling using the frustum, we are using the frustum as a boundary for dynamic resampling. We only need to sample the controlpoints which are new to the current frame, and we are only interpolating geometry associated with new controlpoints. Frustum culling implies that we have loads of geometry in memory at any given time, this is what we are trying to avoid!!!
Changing the camera orientation quickly would pose a problem for this method if there was no caching of controlpoints (and geometry) which has recently become old, ie, moved offscreen.

Would you be able to implement collision detection or physics (simple gravity even) with this (load as you go) type of terrain engine. For instance if geometry was moving from out of the view into view since out of view vertices may not be loaded yet.


Setting the threshold for caching of geometry relative to the maximum angular and linear velocities of the camera solves this problem. If we allow the camera to move about too quickly, we are forced to cache more, and could soon find ourselves running out of memory. On the other hand, if we slow the player down too much, the game will not "feel right". Tweaking the caching threshold thus becomes a matter of high importance.

I'm pretty braindead at the moment, I hope I answered at least some of your questions.
The most important message I'm trying to convey is that we only tesselate terrain which has just become visible (or has changed lod), and we cache geometry which has just gone offscreen.. we don't want game enemies disappearing when we turn our back on them because the terrain they were "standing on" has disappeared!! We're not streaming actual geometric data, just controlpoints. We're not tesselating anything that is already or was recently visible and that has not changed its lod.

When I say we are streaming controlpoints, specifically we are streaming height values and uv values.
The X and Z values of controlpoints are implicit.

This schema has not been applied before to my knowledge, except in regards to medical imaging, where huge amounts of data must be visualized in realtime. I'm yet to code much of it, so all of this is theory, open to interpretation and suggestion.We are simply trying to get away from the chessboard mentality of quadtrees and the static nature of bsp and do something new.


Posted on 2006-01-08 19:54:01 by Homer
collision detection: scan a ray in the vector you move
heightmap data reworked from ymap to ydeltamap could result in smaller data?
anyway you stand on one tile, while surrounding tiles are already coded in relative height to that
ybuffer for culling terrain behind hills
textureorganizing:
settexture uses pointer as input for each texture
an array 0-255 of these
and terrains texturedata=byte that is offset in this array
which also works with alternative textureorganizing of different material in same texture, just using different UV coordinates
how does it look if outdoor lightmaps are using paletteanimation and fades between daylight, sunset colors, nighttime moonlight?


Posted on 2006-01-14 04:23:47 by daydreamer
In order to implement "daylight", just modify the AMBIENT lighting.
Ambient light affects the appearance of everything, and therefore this will affect the appearance of your lightmap texturing.
For example, at night, make the ambient lighting a more BLUE colour, and at sunset and sunrise, make it a warmer orange/red colour.
Now write a simple procedure to interpolate the "daytime" colour according to the time of day, and just call it once every few "hours in gametime" to update the ambient lighting.

If the virtual lightsource associated with a lightmap is switched off, don't render the lightmap.
Posted on 2006-01-14 21:36:58 by Homer

In order to implement "daylight", just modify the AMBIENT lighting.
Ambient light affects the appearance of everything, and therefore this will affect the appearance of your lightmap texturing.
For example, at night, make the ambient lighting a more BLUE colour, and at sunset and sunrise, make it a warmer orange/red colour.
Now write a simple procedure to interpolate the "daytime" colour according to the time of day, and just call it once every few "hours in gametime" to update the ambient lighting.

If the virtual lightsource associated with a lightmap is switched off, don't render the lightmap.


I have experimented earlier in C++ with those dx light examples, general ambient lighting look so dull, I wanted to experiment to turn greyscale on lightmaps to some yellow/orange/red spectrum

played oblivion, wonder if you have tons of animated grass in some part of the terrain, cant you turn down LOD below that if you dont see much of it anyway and a plain grass area dont need so many polys
Posted on 2006-04-14 03:30:08 by daydreamer