This is a demo source+binary for a grid tesselator which may be a useful starting point for terrain engines or other purposes.

The TerrainPatch object creates a grid of arbitrary #quads in the XY plane (easy to change that).
Currently it uses a TriangleList, but does use an indexbuffer as a speedup.
I will leave the implementation of trianglestrips (with or without index buffer) as an exercise for the reader, but note that these create 'degenerate primitives' while the existing code does not.

Degenerates are problematic for collision detection because you must detect and handle them or trigger false positives, and detecting them is slower than not having them in the first place.

The demo vertexformat is not textured, but code for generating UV values is included , although it is commented out.

I will be using the TerrainPatch object as the basis for my next terrain demo.
Unlike my previous terrain demo, this TerrainPatch keeps vertices with absolute World values, and thus we don't have to translate each patch into place in worldspace, or worry about transforming object positions with respect to the patches or vice versa.
You get to choose:
-the absolute world minimum and maximum values for each Patch
-the granularity of each Patch (#quads on each axis)

I've also included a simple 'skeleton' D3D application framework which implements one demo terrainpatch and proves that its working.

It's really quite simple stuff in its current form, and so I've posted it for posterity.

Posted on 2006-08-15 01:52:02 by Homer
The next step toward something useful in terms of terrain is the ability to texture our terrainpatch.
Attached is an update which renders a texture over our terrainpatch.
Use the F1 and F2 keys to switch between wireframe and solid modes.

I guess now we'll want to start altering the 'height' of our vertices, so we can see hills and valleys...this means making a decision about which axis is the "world UP axis", currently "up" is "+Y"... which doesn't make a lot of sense when our terrain has been defined in the XY plane.
What do I mean? Huh?

Right now, the terrainpatch is standing "upright", and we are looking "forwards" at it.. what we really want to do is lay our terrainpatch "flat on the floor", and point the camera "down" at it.
Either that, or use the Z axis as "up" instead of the Y axis.
Make more sense?

Posted on 2006-08-15 07:46:17 by Homer
Now we're getting somewhere..
This version has a LOT of changes, some minor, and some major.

This version implements an ARRAY of TerrainPatches.
We can decide the following values:
-Size of the World, in X and Z
-number of TerrainPatches in X and Z
-number of Quads in each TerrainPatch in X and Z

NOTE : If you decide to change any of those values (EXCEPT the WorldSize), you better delete the TER files (see below)  before you execute the app, so they will be recreated with respect to the new values.

Each TerrainPatch now contains a buffer for an array of Bytes (one per Vertex) which control Height of each Vertex.
Initially, this Height data is sampled from a common bmpfile (heightmap.bmp).
I say 'initially' because once we've sampled the height data for a given TerrainPatch, it's written out to a '.TER' file so we never have to extract it again - next time we execute the app, Height data will be loaded from a TER file, rather than the Heightmap.

The TER files are named 'BLAH_X_Y.ter'
where BLAH is a common name for the terrain,
and X and Y indicate the TerrainPatch's coords in the World array.

Similarly, each TerrainPatch will attempt to load a UNIQUE texture from a file named 'BLAH_X_Y.bmp' - which probably doesn't exist.
If a texture fails to load, the default 'devil' texture is used instead.

I've hardcoded some values in this demo.
The World is defined as being from -512.0 to +512.0 in size.
It's constructed from 4x4 TerrainPatches.
Each TerrainPatch is constructed from 8x8 Quads.

These are VERY conservative values, I've tested with MUCH higher values, but if we make the geometry too fine, we can't see the wireframe clearly, and for that reason ONLY, I used 'crap resolution' values... basically, I've set the camera up to view the entire WORLD, which isn't realistic - usually, we'd be 'in the world', and we'd want our terrain tesselated more finely.

Some feedback would be nice :)
Posted on 2006-08-19 23:40:01 by Homer
In TerrainPatch.Draw, shouldn't we remember the last pTexture (and not reset to it again), remove the SetStreamSource and SetFVF?

Why not put large terrains in a quadtree, to decide which portions are to be drawn?
Posted on 2006-08-20 09:12:36 by Ultrano
Ultrano, I'm keeping this simple, although your suggestions are good ones.
I'm modelling this after the engine in Morrowind, it's meant to handle really massive worlds.
The world is defined as a large static array of TerrainCells.
Each TerrainCell is associated with a TerrainPatch, but the TerrainPatch does not necessarily have any loaded resources - the TerrainCell defines the space and its contents, but we don't keep all the TerrainPatch geometry loaded all the time..
I intend to keep enough chunks of terrain loaded as required by the farplane to nearplane distance, in a region about the player's position in worldspace.As the player crosses patch boundaries, I will load and unload terrainpatch geometry via a small cache of recently-unloaded entities to avoid the obvious.
The terrainpatch height data is typically being loaded from many small custom binary files, so terrainpatch creation isn't so expensive.
We already have a quadtree of sorts because our terrainpatches are being stored in a 2D array that has a direct association with worldspace.
IE we can perform simple culling and collision detections based on simple math formula.

Last night I generated some textures for this 4x4 patch demo really quickly using an excellent and free software called T2 Terrain Texture Generator, and here's a screenshot..
This is shown with the low-resolution values as per the previous posting.
Posted on 2006-08-20 19:52:12 by Homer
If you look really closely, you can see an artefact - the 4x4 terrainpatches are outlined with a small 'fault' !!

This is the result of my poor use of math..
I'll see if I can make that go away :)
Posted on 2006-08-20 19:55:52 by Homer
I want to use a road constructed of tiles,Mirror texture for your leftturn and its a rightturn, mirror it again and you have 4 different turns
I wanna use trianglelist for the whole road so I can use a single settexture/drawprimitive TRIANGLELIST for all visible roads in the terrain at once
you control where textures are mirrored with UV coordinates, where trianglelist leave more freedom than trianglestrips which can mess up previous and next quads UV's
Posted on 2006-08-21 06:37:19 by daydreamer
First thing to know : there is a limit to how many vertices can be addressed in a single call to DrawPrimitive.
For non-indexed trianglelist, its quite low, around 33^2 vertices.
For indexed trianglelists, its much higher, not sure exactly, but I have tested up to 256x256 QUADS which is 255*255*2 TRIANGLES.
You need to think about 'batching' the primitives you render.
For this demo, a Batch of primitives is a terrainpatch worth of indexed trianglelist.
If you need to draw more than the limit, you need to use the extra funky parameters in the DrawPrimitive call to specify 'chunks' of primitives. This technique is quite well known by anyone who's played with a particle engine, as the 'partial buffer lock and spray' method.
Effectively, we can lock part of a buffer which is not being drawn, and write to it at the SAME time as another portion is being rendered.
Thankfully, if we keep our Batch numbers below the limit, we don't have to worry about it :)

I've posted an update of the exe + resources.
Note that I fixed the 'artefact' bug at the terrainpatch borders, it was triggered by the fact that my textures are 'filtered', and caused by the texturing mode being 'Wrapped', changing it to 'Clamped' fixed the problem.
This update includes 4x4 Textures, each is 512x512.
Terrain is 4x4 Patches, tesselated to 32x32 Quads.
It sure looks nicer with textures !!

I'm using the tool I mentioned (T2 Terrain Texture Generator) to create the terrainpatch textures.
It's a quite advanced utility, we can blend in roads and other 'regional textures' by using more than one input HeightMap.
Each HeightMap has its own set of input Textures and each Texture its own blender characteristics.

I am really impressed by this free application :)

Use cursor keys and keys L and P to control camera.
Posted on 2006-08-21 06:50:09 by Homer
I've now moved all the code relating to TerrainPatch management (rendering, unloading and loading of resources) into a new class called TerrainArray.

We create a TerrainArray and initialize it to the size of our entire world.
It creates an array of TerrainPatches, but doesn't load their resources.
Consider this array as 'the entire world'.
We never actually kick TerrainPatches out of the array at runtime, but we CAN load and unload the RESOURCES of any TerrainPatch.

If you like analogies, consider the TerrainArray as an array of buckets.
The buckets can be empty, or they can be full, but they always exist.

One of the methods in the new class allows us to quickly identify whether a given World coordinate is above/below a Terrain cell.
You tell it an absolute XZ coordinate, and it will either tell you that coordinate is outside the World domain, or it will tell you the ARRAY COORDINATES of the Terrain cell in the TerrainArray.

When the program begins, I use this to determine which Cell the CAMERA is above, and then I load terrainpatch geometry for that cell, as well as the cells which immediately surround it (up to 9 cells).
What we're really describing is a SUB-ARRAY of 'renderables'.
We're saying 'just show me the stuff thats close to me'.

Unfortunately, this version does not maintain this subarray, so we don't see patches being loaded and unloaded as we travel the world.

In the next update I'll add dynamic loading :)

Note that the attached zip does *NOT* contain any Textures.
If you want to see textures, download them from here:
Posted on 2006-08-22 02:36:37 by Homer
Hey, guess what?

I've implemented dynamic loading and unloading of terrainpatches :)
We now keep a 'sub-array' of 3x3 ptrs to TerrainPatches, in which the Camera is always located within the center cell.
This so-called 'sub-array' is updated whenever we cross a 'terrainpatch boundary', new patches are enabled, and old ones are disabled.
Currently there's no caching system, but there seems to be very little need for one at the moment.. the delay caused by the loading and unloading of resources is almost negligable.

I'm not going to post it until tomorrow, since I've grown the world to 9x9 terrainpatches (with our 3x3 subset moving about within it), I want to grow it out some more, say 16x16 terrainpatches, with textures.. that means I need to generate a bunch more textures than the 4x4 I originally supplied.. we need 256 textures, and we need them now... just as well I'm not waiting around for a 2D artist to get the job done, eh?

Wow, that's going to be a whole bucketload of textures.. I'll reduce their resolution back down to 128x128 pixels for the time being, just to keep the download size reasonable.

We don't need to worry about increasing the resolution of the heightmap image just yet - evan at 16x16 patches, we have almost a one to one sampling ratio for our height data (we're only out by one pixel, it won't be noticeable).
Posted on 2006-08-22 11:34:57 by Homer
Well it looks like I'm pushing the limitations of the T2 texture generator already - or rather, it makes poor use of my lowly system resources.. I can generate a 2048x2048 texture (for splitting into 16x16 textures at 128x128 each), but it crashes before I get to generate a lightmap for blending purposes and before it slices the output texture so I had to do that with another program and manually rename all 256 files. In future, I may be forced to split the Heightmap in order to batch the texture generation and give T2 and my system a bit of a break.. at that time I'll probably stop supplying the heightmap, and instead supply the TER files which were extracted from it, since they make the heightmap seem rather redundant anyway.

Anyway, here's an update with the 3x3 subarray implemented.
We have a 16x16 array of terrainpatches, so that's 16x16 textures.
TerrainPatches are being created with 8x8 quads, in case you cared.
Remember that we can go a lot finer than that !!
Something tells me that 3x3 isn't enough - I'll probably increase the size of the subarray to 5x5.

I've doubled the size of the world, and increased the camera speed.
You can find the textures required at
Note it's about 8 megs worth of textures.

If you're reading this moments after I posted it, be aware that my ftp host is quite busy today, so uploading is taking some time.. it might pay you to check whether the size of the texture pack is changing (ie I am still uploading it) before you decide to grab it - nothing worse than downloading 7 and a half meg worth of broken archive!!

A final note : if you are disappointed with the depth of view (as I was), just remember two things : firstly, I already said I would probably increase the subarray size, and secondly, realize that (once I add a more friendly camera) we can see that far in all directions.. rotating the view is effectively cost-free.
Posted on 2006-08-22 23:18:26 by Homer
I've increased the subarray to 5x5 patches using the same mechanisms as previously.. now we can start to feel a small amount of lag as we cross the interpatch borders.
Here's a couple of screenshots of my 16x16 patch world with 32x32 quads per patch, and low-resolution (128x128) textures.. Note that the 'staircasing' is a result of the oversampling of the heightmap - the two possible cures for this are to increase the resolution (larger heightmap image), or alternatively, to implement some kind of 'filtering' in the pixel-fetching code that is hidden away in the TerrainPatch::LoadHeightData_BMP method (for example, bilinear filtering would be sufficient since we're not image-processing per se, interpolating new pixel data would be just peachy).

Posted on 2006-08-23 01:45:21 by Homer
really looks great, great work
I used before a World.class which also mapped textures on terrain+ textures on vertical walls. outside of the squares I had data for was handled with IF's for a bunch of seatiles and IF's to see terrain further away, so the World was emulated to be 4gig x 4gig squares, also many detailed areas could be placed with distance between them, checking if camera was looking inside their boundary square
could be nice to test this with a group of Islands
also a big continent is possible with check if coordinates is between two curves that define geography, if the coordinate is exactly on a curve use coastline tiles with beach boarding to grass right there

Posted on 2006-08-23 10:51:58 by daydreamer
I'm glad you're enjoying the show :)
I've just finished rewriting my Quaternion-based camera code, it's been vastly simplified by using new D3DX quaternion functions.
Also, I'm translating some very complex code for sky dome.
It supports the following features:
-Partial sphere for reduced texture warping at the horizon
-Day and night ambient color fade via interpolation
-Day and night texture crossfade via interpolation
-Multiple orbiting Bodies (Suns, Moons) with 3 kinds of Orbits
-Solar Lens Flares

It's going to take some time to implement all of it, but I do intend to implement it all, because nothing makes a 3D game better than the extra realism that such eye-candy provides.

I'm also working away on a system for vegetation such as tufts of grass, shrubs, trees and so forth.

With all of the above implemented, it should look much better, and provide the impetus for implementing a weather system and the related special effects (rain, mist, lightning, etc)

Sound good?
Posted on 2006-08-24 12:06:29 by Homer
The attached zip contains an update which features a new class called SkyDome.
It's early days, but looking good.
You can specify a lot of parameters when you create your SkyDome, such as the Radius apon which the dome is constructed, the resolution of the dome's geometry, the amount of hemisphere you want (as an angle between 0 and 90 degrees where 90 = hemisphere and with Y automatically compensated for lesser angles) , a height scaling factor to apply to Y values  to squash the dome, and an offset for translating (shifting) the entire dome in 3D space.

Some details:
SkyDome is constructed from a series of 'rings' of vertices at various 'heights' on a theoretical hemisphere, with an extra vertex at the 'top'.
The vertexbuffer contains the top point, then each ring of vertices, from the uppermost and smallest ring to the lowest and largest ring.
The indexbuffer contains indices for a TriangleFan and indices for a TriangleStrip.
The same TriangleStrip worth of Indices is drawn repeatedly for each neighbouring pair of Rings, using a trick called 'Base Vertex Manipulation'.

The posted demo creates a 60 degree partial hemisphere with no squashing or translation.
Now it just needs texture coordinates :)

Oh yeah, I almost forgot, you start underground, move up with 'P' key
Posted on 2006-09-01 04:24:25 by Homer
For those who wish to rebuild the source I posted previously, you'll need to comment out two things in the .asm file:
- the line to INCLUDE (Line 90)
- the reference to the Camera object (Line 93)

I neglected to give proper credit to the author of the article (and accompanying cpp sourcecode) apon which I've based the SkyDome, so I'd like to do so now.
The article was written by Tim Smith, and was posted at the now sadly defunct
If interested, grab it NOW before the entire site disappears like so many others.

Back to what I've done lately:
I'm trying to avoid texturing the sky itself..
I've added two params to the SkyDome::Create method, they define two colors.
I'm giving the skydome vertices a color.. I interpolate between the two new input colors based on which Ring the vertices live on.
For example, using Blue as the 'top' color, and Red as the 'bottom' color,  the sky has a really nice looking 'gradient' fade so that theres a red/purple color near the horizon in our otherwise blue sky.
This looks much nicer than just a solid color.. however, there's a big problem.
Look at some pictures of real sunrises and sunsets, and you'll note that the horizon color fade isn't in the Y axis but rather is a projection from the position of the sun, so it appears more or less circular.
I'm currently adding some code to calculate the orbits of 'Sky Bodies' such as suns and moons, ie to calculate their positions in the sky.
Having done that, I'll write a method to color the vertices according to their distance from the sun(s) and moon(s).
Sunrise and sunset will look much nicer.
The skybodies (suns, moons, clouds, whatever) will just be billboards (pointsprites) whose positions follow various orbits.

Posted on 2006-09-02 03:15:11 by Homer
We wish to calculate accurate orbits for our sky bodies.
I'm unashamedly transliterating Tim Smith's sourcecode for solving this problem.
The following image illustrates the various characteristics which describe the orbit of a SkyBody:

Each SkyBody will require the following orbital information:
-Longitude of the ascending node
-Inclination to the ecliptic
-Argument of perihelion
-Mean distance
-Eccentricity (0=circle, 0-1=ellipse, 1=parabole)
-Mean anomaly (0 at perihelion)
-Mean anomaly (adjust factor for days)
-Radius of the body

That might seem like an awful lot, but I think it's worth the effort.
We'll be able to have much more realistic planetary motions, which might very well become a key aspect of any games based apon the engine!!!
Posted on 2006-09-02 03:56:04 by Homer
This update implements an improved HeightData extraction, an orbiting Sun, a fading Sky color, a fading Ambient Light color, and the concept of GameTime (as opposed to RealTime). The sun isn't being Rendered, but I do calculate its position in the Sky based on GameTime (its orbit will vary throughout the game year realistically).

You'll need the Heightmap and 16x16 textures supplied previously.
Delete all your TER files before executing this version, and you'll notice that the staircasing artefact has been fixed.
That artefact, as mentioned previously, was due to the fact that our HeightMap image hasn't got enough pixels for our Terrain resolution, ie we are trying to 'upscale' the image so we need some way of reading values that lay 'between' actual source pixels.. the updated Pixelmap class contains a new method called GetVirtualPixel which implements BILINEAR FILTERING, ie it returns the Weighted value of the four nearest pixels to the floating coordinate we gave it... this effectively SMOOTHS our height data, meaning that we're not forced to use a larger heightmap.

The current implementation isn't really that great.
1 - I added Normals to the Terrain so that it responds to Lighting properly, but I don't calculate the Normals as I should.
2 - I calculate the color for the Sky and apply it directly to the SkyDome vertices, which means Locking and Unlocking the VB, which sucks, and then I derive the Ambient Light from the Blue component of the Sky color, which also sucks.

I really should remove the Color component from the Sky vertices and use a Material to control the color of the Sky.. this would mean we'd never need to touch the VB, but it also means that a GRADIENT is not possible.
The way things stand, it's possible to change the color of the sky in a given area, for example to make the sunrise and sunset look more appealing.

Next I'll add rendering for the Sun (probably pointsprite) and then it's time to start looking at populating the terrain with vegetation :)
Posted on 2006-09-08 09:45:12 by Homer