I’ve been porting my old terrain system to my new code base, and
from OpenGL to D3D11. As of today it is rendering at more
or less visual parity with the OpenGL version. It still lacks any form
of culling and has no shadows, but overall a major upgrade from a few
days ago when it looked like a couple of broken triangles.

While porting it, one system I ditched was my old threaded job
system–which was used heavily during terrain generation.

Instead I’ve decided to use Intel’s thread building blocks. Initially I
was using Microsoft’s concurrency runtime, but a few problems compared to
TBB drove me away. One major annoyance is that MCRT won’t compile
in C++/cli(while TBB will); amusing considering C++/cli is
a MS product.

It took abit but eventually I had TBB performing on par with my
old job system, and TBB should be a win in the end since it is
much more flexible.

Files

One useful feature I added recently was a file monitoring system–
mostly intended to make development easier–it notes any files that
my program opens, and if and when any of them change while the program
is running it sends out a message so that any interested system can
reload the file.

So far just using this with lua files and shader files, but it is very nice
to be able to modify a shader, hit save, and have it immediately reflected
in the game.

To make this work generically for all D3D resources I had to add an
extra level of indirection, I did wrap it up in a way that just changing
a typedef will allow me to toggle between the two– though on a modern
PC it probably makes little to no difference.

Haven’t updated this website in far too long, took a break from this project(moved/new job).
Back on track now; purchased a new computer, primarily intended for development purposes,
it has an i7 920 quad core so I can really stress test my threading.

i7 Results:
Chunk generation on this processor makes my old Pentium D look like a slug,
I have hyper threading enabled, which currently results in 7 job threads being created.
Didn’t measure it scientifically or anything, but eye balling the printout(prints out every
512 chunks), it appears to creating 1k-1.5k chunks per second(old Pentium-D gave
100-200/sec).

Also have a new monitor which supports up to 1920×1200 so I can finally run this at
something higher then 1280×1024. I was surprised to find that maxing the settings for
the terrain(uses horizontal screen width) actually ran relatively smoothly.

Occlusion Culling:
Last weekend I implemented occlusion culling for the terrain system, this has given a
really nice boost to rendering speed, and has also helped out the generation process,
as I can use occlusion information when assigning a priority to chunks that need to be
generated(as in, if parent is occluded, reduce score, if grandparent is also occluded,
reduce it even more etc).

My implementation works like this(using a 3 frame delay):
-Initially we have no OC’ing info, so render terrain front to back, issuing an occlusion
query for each chunk.
-If a chunk fails OC, switch to rendering its bounding box(AABB are rendered after all
actual terrain chunks, and with depth/color writes disabled).
-Newly created chunks take OC’ing state of parent.
-If all children of a parent have failed OC test, fall back to parent(this will result in a
chain reaction of fall backs in portions of scene that are deeply occluded – and more
importantly, less objects to render), once parent becomes visible again, fall forward to
children. This results in an interesting deblurring effect; when you pop your head
around a corner, the world very rapidly comes into focus.

Few issues I ran into with occlusion culling:

-Fast movement over the ledge of a cliff will result in the sudden appearance of new
chunks, but since they occlusion results are delayed three frames, they still think they
are occluded and don’t show up immediately.

-Another problem was with chunks whose AABB test indicated they were the frustum,
but upon rendering, none of the actual triangles are truly within the frustum, resulting in
a failed query. These chunks then promptly disappear(switch to invisible AABB test).
The result of this, is that as the screen pans around, small holes appear on the side of
the screen nearest the direction of movement.

Turns out there is a really simple solution, NV_conditional_render. Just issue the
occlusion queries like normal, then in a later stage attempt to render those
objects you think are occluded with a conditional render and the GPU handles
the rest. I still read back the occlusion results a few frames later, since it
is useful for LOD and chunk generation.

Overall I’m very satisfied with the speedup(not exactly sure what it was, I’ll measure
it at some point, but it was quite noticeable).

Noise code to SSE:
Awhile back(couple months ago) I also rewrote the majority of the noise code
in SSE2. Used AMD CodeAnalyst to find the hotspots and focused on reducing
whichever part it indicated as being the slowest. Another nice performance boost
was noticed. At some point I think I will go back and add 64 bit double support
to the entire pipeline since I would really like to be able to use more then 20 octaves
before running into the damn stair step affect from precision loss, so I’ll
have to write another SSE version using doubles, eventually.

I’ve added PSSM(Parallel-Split shadow maps) based shadows, this technique uses
multiple shadow maps each one progressively closer to the viewer. I went with PSSM
because of the size of my terrain, even so, using 4 splits I have to limit how far away
objects can be and still receive shadows.

Having the render the scene an extra four times is pretty unpleasant, hopefully
once I add some more optimizations things will won’t be so slow.

It still has some kinks, I need to eventually take into account the visible
objects when constructing the matrices for the shadow map, and add
some much better filtering. There is also some perspective aliasing that
needs fixing. ShaderX6 apparently has an article covering some of these
things but I don’t have a copy of the book.

Eventually I would like to use some sort of deferred rendering technique since
it would allow for a cleaner shadow system, but not until I can get AA with deferred..
though the light pre-pass method might work.

Some screens with shadows: this made my 6800 cry

Comments:

It seems the comment system was broken, this theme didn’t want to show comments
so I just copied another themes comment.php over it, and now things seem to work…

Dennis/devfreak thanks for the link, I’ll have to look into it, I didn’t notice your
post earlier because this thing thought it was spam.

Performance:

Instead of focusing on texturing I decided to refine the system and improve
the performance. Using the default size for each chunk of 32^3, generation time
varied(depending on the # of octaves and # of triangles produced) from 2-20
milliseconds. On average I was getting around 100 chunks per second,
per core.

Fairly fast all things considered but not sufficient to really allow my system,
with only a single core to spare, to keep up when the camera was near the ground,
assuming I had the settings at 1 triangle/per pixel on the max resolution of my
monitor(1280×1024). At these settings, when near the surface, as many as 10k-20k
chunks can exists, as crazy as that may sound. A cold start on the surface
would take two minutes or so to completely generate, thankfully once generated
the camera’s movement isn’t so fast so it doesn’t need to be able to do them all at
once or anything.

To improve the speed I am storing a bitfield for each chunk, that marks for each
8^3 sub chunk whether any vertices were placed within or near its position in the
parent chunk. This allowed for easy culling when generating the noise volume, but
made MC’s a headache since I had to rewrite much it to handle a volume that contains
many gaps. I have so far seen a safe cull rate of 65% for the sub chunks which has given me
about a 3x speedup.

Once I rewrite the primary bottleneck of the noise algorithm in SSE(which I have delayed
because I am unsure if I can get away with floats, or will have to resort to doubles),
I should see another 2x improvement. Hopefully.

With all these optimizations in I expect systems like mine(pendium D, 2 cores;
with one used for generation) should be able to fully generate the terrain from
ground level in 20 seconds or so. One of the newer quad cores could probably
do it in 5 sec if not faster since it would have 3 cores to spare and those cores
are superior to mine.

Cleanup:

All the problems with precision, and the lines that appeared
between chunks are now gone. The lines were caused by the inability to map
exactly the positions of vertices in neighboring chunks using only an unsigned char.
255/29(default chunks are 29 ‘spaces wide’) is a fraction, so instead I am using
only values from 0-232(232/29 = 8), this way the last position in one chunk, matches the first
in the next chunk exactly.

The only possible lines left now are those between different LOD’s.
There is also very rarely a hole caused by overly aggressive chunk culling.

Normals:

I tested out various ways of compressing the normals. I need a full
3 component normal since I cannot assume Z is positive, so I was originally
just storing all 3 as uchars. I saw a post on gamedev mentioning
spherical/polar coordinates so I tried that and was able to shrink it down
to just 2 bytes. The sin/cos functions on the GPU are surprisingly fast it seems.

Since I still had the 3rd byte sitting around empty I packed the lower 4 bites of
two 12 bit polar coordinates into it, and then unpacked it all on the GPU.
Using 12bit vs. 8 bit polar seemed to have little actual visual affect though, so I took a
couple identically positioned screen grabs and used ATI’s compressonator to see
what actual difference is. The values varied, but not by much, about 2 on
average and the highest was only around 6.

Some screens, nothing really new visually except a few minor fixes. Taken
with anti-aliasing enabled this time at least.

Plastic looking terrain ..

I prefer this light model(ON) but it has no specular term, I’d like to use something like this
but with a least some specular.

I’m now using an improved method for placing the vertices in the marching cubes algorithm,
and it produces noticeably better looking edges. It’s still not perfect, but good enough for
now.

I need to start working on texturing the terrain which will be fairly complicated since
I can’t just stretch a texture over it like in heightmap system..

Here is my quick attempt to create a terrain that looks a little more like here on earth;
blue sky, and white colored terrain to simulate snow.

Today I’m going to do a brief visual tour to show some of the interesting locations
I have found in my volumetric procedural world.

My terrain is not yet textured, everything has only one color, and that color
is pink, so you may have to actually click on some of the pictures and make them fullscreen
to really tell what you’re looking at.

There are still LOTS of image quality issues such as the lack of blending between LOD’s,
the ugly jagged edges caused by marching cubes, and the green lines where the
background is showing through. Anti-aliasing was also off since my 6800 can’t handle it.

Also this is not a realistically proportioned planet right now, the mountains are huge
and stick out into space, so the horizon doesn’t look much like here on earth.

I’ve also posted a short clip taken with Fraps at the end.

My system specs aren’t too impressive so the FPS with Fraps activated is
only about 15fps.

GPU: Nvidia 6800
CPU: Pendium D

Here I’ve found some sort of gully, it almost looks like a landslide or cave-in.

Some cave like holes can be seen in the nearby terrain, look in the top right
corner for the tall spire, it is the subject of the next shot.

The spire up close, a little on the bright side…

And this is the back side of the spire, I moved the light and it looks much better IMO.

Moving on I’ve discovered a huge archway towering over the landscape..

This was taken from underneath the arch.

One last look look back at the arch, it really stands out against
my lame green backdrop(I really need to add some kind of atmosphere..).

Climbing in altitude I took this shot from high above.

I have found an odd formation on steep cliffside, hard to tell in this still pic,
but it is a very long way down.

One last look, taken while “standing” on the formation seen in the previous shot.

NOTE: videos require recent flash player.

Get the Flash Player to see this player.
Short clip passing over the rough region from the 2nd picture

Get the Flash Player to see this player.
Another short clip, this time along the side of the cliff.

Dealing with precision loss:

GPU precision:
In order to actually display a large scale terrain system I had to address the issue of precision loss, originally I was translating the camera around like it is done in most games, but when the camera was very near the surface the more detailed chunks would start to jitter about.

To combat this I am now subtracting the camera’s position from each object’s position prior to rendering said object. In the shader I only need to rotate the object, and now everything is relative to the origin of (0,0,0) and precision loss is minimized. On the CPU side I could use doubles, but as of yet it has not been necessary, and the jitter is completely gone.

Noise precision:
Another place where precision has become an issue is in the generation of the noise data.
Essentially noise assigns random values to points in space and then interpolate between them
to create a smooth signal. By adding these octaves/signals together you can create something
that looks like a mountain range etc. I am using many octaves for my noise, each using a
higher frequency and lower amplitude then the previous.

In order to create a spherical planet I am running a short post process algorithm on the
noise results which alters the signal based on its distance from the surface of a
perfect sphere, points under the surface have their density increased and points above
have their density decreased. I was using SSE to process 32bitx4 floats, since the
process involves a square root(I could use distance squared, and may switch to it at
some point, but it was less stable when I tested it out; the drop off from solid->air
was exponential instead of linear).

SSE, unlike x86, which has 80 bits internally, really only has 32 bits of precision so
as the camera descended toward the planets surface some visible stair step effects
could eventually been seen.

I have switched to using SSE2 64bitx2 doubles during the “make spherical” step,
and happily the stair step effect is gone.

Here is the inner loop in SSE2, this gives me chance to test out posting of source
code…(sorry the syntax highlighting is terrible.. and the spacing..this thing
fails at understanding tabs..)

NOTE: All the input(position/radius) was scaled down prior to running this code in order
to increase the range from 100% solid to 100% air.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

for(int i = 0;i<8;++i)
{
   for(int j =0;j<8;++j)
   {
	zyPosSqrDist = (zSqrBuf[i] + ySqrBuf[j]);   //Sum square Z and Y positions
	SquareDistZY = _mm_set1_pd((zyPosSqrDist));
 
	for(int m = 0;m<4;m+=2,bufOffset+=4)
	{
 
		CurBufferValue = _mm_load_ps(&buffer[bufOffset]); //Load the 4 32bit noise values
 
		SurfaceVal =_mm_sub_pd(Radius,	        //Subtract distance from planets radius
				 _mm_sqrt_pd(			//sqrt to get real distance
				 _mm_add_pd(SquareDistZY,	//Add ZY square to X square to get distance squared
			           xSqrBufSSE[m]))) ;	        //X square distance for this row
 
		LowerBuf = _mm_cvtpd_ps(SurfaceVal); //Set lower 2 spherical offsets
 
		SurfaceVal =_mm_sub_pd(Radius,	                //Subtract distance from planets radius
				_mm_sqrt_pd(				//sqrt to get real distance
				_mm_add_pd(SquareDistZY,	        //Add ZY square to X square to get distance squared
				xSqrBufSSE[m+1]))) ;	                //X square distance for this row
 
		UpperBuf = _mm_cvtpd_ps(SurfaceVal); //Set upper  2 spherical offsets
 
		OutBuffer = _mm_movelh_ps(LowerBuf,UpperBuf);	//pack them together
 
		//Add the 4 spherical offsets to the 4 noise values
		CurBufferValue = _mm_add_ps(CurBufferValue,OutBuffer); 
 
		//Now write back to buffer
		_mm_store_ps(&buffer[bufOffset],CurBufferValue);
 
	}
   }
}

There is still a very faint darkened line that appears when the camera is extremely
close to the surface, basically when the near plane is intersecting with it.
I need to investigate further but I suspect it may caused by the extremely
small intervals which are being interpolated in the noise once ~15 octaves has
been reached.

The terrain normals are currently just 3x8bit normals, which so far has
worked surprisingly well, but I may switch to something along the lines of 10/11bits
for X/Y and packing the sign of Z into the leftover bits. More work in the shader
to decompress it but possibly worth the processing time.

Terrain Improvements:

Sliver removal: Marching cubes tends to generate many small triangles,
some so small they contribute nothing to the overall model, and in truth make it look
worse as they create shimmering when the camera moves. So I am now processing
the chunks to remove all sliver triangles. The process is controlled by a float
specifying the relative minimum allowed distance between vertices from 0.0-1.0.
At a moderate setting it removes around 20%-30% of the triangles and I cannot
really see any reduction in the quality of the terrain.

And finally..

Balancing the amplitude of each octave so that it doesn’t introduce more information to the signal than the visuals can support is turning out to be very important. This greatly reduces the amount of “floaters” and other unsightly looking problems found in the image.

In the following screens I’ve found a much better balance then in any of the previous screens
I have posted, though a few small floaters are visible and the sharp edge issue is still present.

Again, after the light has been moved.

This shot was taken prior to the precision fix(actually they all were), if you zoom in
on the lower right corner you can see some ugly tearing/stair step starting to show.

I’ve worked on various aspects of the terrain system since last time.

Level of Detail:

The LOD system determines when a chunk should split, but I can’t just let every chunk split just because it is close enough to the camera to do so, as this would result in a whole lot of chunks trying to generate at once, and create a massive stall. Instead I assign a score to each chunk that wishes to split-the score is based its depth in the quad tree, how close it is to the split point, and if it is visible-and send off only the best scoring chunks to be split. This generation runs in a threaded job system so it scales to however many cores are available.

Here is a screenshot of the terrain, with each LOD colored differently.

Performance

Performance wise I also discovered that the data type I had been using in the vertex format for my terrain normals was quite slow, apparently using signed uchars/ushorts with normalize set to true (using glVertexAttribPointer() ) is not the fast path, instead I’ve switched to using unsigned uchars/ushorts and just subtracting 0.5 in the vertex shader. This one change basically doubled my FPS. It would be really great if the drivers would actually give some indication of this instead of having to resort to trial and error(and for all I know this is just a problem found only on my 6800..).

Randomness

I was originally using 256 element look up table for the random gradient, as is used in perlin 3D noise(except I used 3 of them, one for each axis), and although I couldn’t really visible see the repetition, it still seemed prudent to try and reduce the repetition as much as possible so I fiddled around with some various integer hash functions.
Integer Hash: this site had some nice integer hashes.
At the moment I’m using a mix of integer hash and perlin LUT by offsetting the hash by the value in the LUT. I probably need to go over this again at some point, but believe the terrain does look more “random”.

Lighting & Marching Cubes Issue

Another thing I’ve been playing with is the lighting of the terrain; I’ve tested out a whole bunch of ways to generate the terrain normals, and in general it seems to be a tradeoff between smoothness and detail. Using sobel filter type methods I can get extremely smooth normals, but they lack fine details, while using central difference the detail is better but some sharp edges on the terrain appear jagged. This jagged edge effect is a result of my current implementation of marching cubes, which is based on marching cubes 33. MC33 solves the ambiguity problems in MC but does not allow for sharp edges(it creates rather ugly zigzags where sharp edges exist). Since I’m largely using ridged noise which is all about sharp edges to generate my terrain, the result is plenty of zigzags are visible on the terrain.

Thankfully there are a couple of newer, improved marching cubes algorithms which solve the
sharp edge problem. Unfortunately they are quite abit more complex then standard MC.

Cubical Marching Squares: This one apparently solves the sharp edge problem by further subdivision, not sure that is what I want..

Dual Marching Cubes: This is a much nicer paper, the algorithm is explained well enough and I think I will try and implement it at some point. As a bonus it would drastically reduce my triangle count since it removes triangles in flat areas.

I’ve implemented a few different lighting models, originally I was just using Blinn, but I was curious how some of the other models would look for terrain. So far I’ve only tried OrenNayar & CookTorrance, since I don’t currently have tangent information available in the shader (I’ll eventually add it for normal maps I expect) as is require by some of the models. The two screen posted below use Oren & Cook respectively.

Terrain Formation:

I also fiddled around with some alternative algorithms for generating the terrain to try and create some different looking shapes. So far I’ve found methods for creating…

Blockworld: Looks like a bunch of chipped stone slabs all stacked on each other. This could possibly be used to create a cracked/slab like appearance for some stone shapes near the surface.

Mounds&Craters: One of the algorithms I made creates irregular shaped mounds mixed in with craters/lakes. I’ve mixed this in with some ridged noise and it seems to work fairly well, although not terribly realistic it does add some variety to the terrain. I’m not really focused on creating realistic terrain, I just want something that looks interesting, so I’m alright with the lakes not having rivers leading into them…and rivers are close to impossible with procedural methods.

Here is a screenshot showing a Mound like shape mixed in with multi-fractal ridged noise. This is also using OrenNayar lighting so supposedly it should look clay-like. I have the normals set to detailed as apposed to smooth so some zigzags are visible.

And here is a shot taken using the CookTorrance model, supposed to be nice and glossy which obviously doesn’t suit terrain but whatever. Also very jagged as the normals are set to detailed & this shot has many would-be sharp edges.

I’m going to try and keep a short dev journal here, hopefully it should help to keep my motivation up and serve as a nice method of keeping track of my own progress. My current project, which is just one part of larger game, is a volumetric terrain system, and I’ve been working on it on and off throughout the summer.

By volumetric I mean that unlike most terrain systems which use heightfields, and are essentially just 2D, thought they have been extruded to appear 3D, mine is actually 3D. The advantage of being volumetric is you can have features you don’t normally find in a terrain system, such as overhangs, caves, and tunnels. Additionally shear cliff walls are not stretched as is common in heightfield based methods.

There are some pretty sever disadvantages though; the implementation complexity is increased, and the time required to generate the terrain is much higher. Many heightfield methods use 2D images as a source to guide the terrain, alternatively noise can be used, or even mixed in, to add detail to the terrain.

Storing a 3D image, as would be required for volumetric terrain is very impractical(would quickly exceed available storage), so I use noise to generate 3D volumes at run time. I do this on the CPU using a highly optimized version of 3D noise I wrote specifically for this task(implementations of noise available on the net are far to slow). Once the volume is generated I use a marching cubes derivative to create the mesh.

Now obviously if I want to create an entire planet or even something small like a valley I cannot afford to process every point in space for the volume, so I use a system very similar to ChunkedLOD, based on a octree, which hierarchically creates nodes, determines if they contain anything visible within them, and if so(once the camera is near enough) generates each child of the parent node dependent upon whether any triangles were contained in that quadrant(octant?) of the parent. The same octree is also used to frustum culling(though I can shrink the bounding box to match the actual verts found within the nodes volume for greater accuracy).

I’m going to have to cover some basics of the system in more detail, but I’ll leave that for later post.

Here are some early screens of the volumetric terrain.

NOTE:
-I have not yet added skirts(to hide the gaps between the different LOD’s) so some “green lines” are visible(green because my background is set to green).
-The terrain is currently not textured at all and is only using vertex normals.
- I’ve noticed it is hard to gauge depth in these still pictures, though it is quite easy when the camera is moving, I believe this is a result of there being no visible atmosphere(fogging/horizon fading) or textures to disguise the self similar nature of the noise.
-The terrain pictured here is using very simple noise algorithms(Fmb | Ridged), eventually I will make it much more complex and varied.

Looking through an arch down into a valley

This is the same planet that the above “Arch” picture was taken from.