JellyEngine

Textured Procedural Planet

2012-01-28T17:16:00.001Z

…aka back to square one albeit the terrain is round this time, so back to round one? I added some textures to the planet, generated on the GPU, they look ok but still lots of work to do. First some outtakes, looked like a load of shite at the start…

… then a bit like an old leather ball…

… then all contoury …

… (which is actually not too bad looking) then it started to come together a bit …

The problem with this though is that the source texture is applied at the same scale for each patch so there’s a noticeable jump when changing levels, a higher level might show a rock but when it subdivides there are 4 rocks. This gif shows the gifferences when approaching, it looks like the centre patch uses a completely different texture.

So it made sense to scale them according to the level (texCoords *= pow(2, maxlevels – patchlevel)), but this introduced some pretty nasty artefacts when zoomed out due to tiling the same texture over and over. Applying mipmapping to the texture I was using helped a bit but it’s still very obvious.

The transitions looked very layered so I added a bit of noise:

All in all it’s not bad for a first go but could be a lot better. I was having fun flying about the place so I made a little video:

…then noticed a problem I had neglected from before that’s obvious in lines going through the brown pit on the right at 0:34.

I thought it was cracking at first because it only seemed to occur when creating other patches but investigating it further it wasn’t cracking, but something to do with textures. Another gif to show the gifferences…

The points are fine, it’s the texture on top that’s creating the artefact. What it ended up being was a leftover setting from creating patches. In order to get the heights from the GPU I draw the noise for each vertex in a patch to an image and read them back to reset the vertices. In order for neighbouring patches to have the same height values I draw it as a point-clamped list of lines. When this was happening a subsequent draw would use the point-clamped sampler and create the artefact. Looking for how to fix led to some good advice, don’t assume sampler states when drawing, explicitly set them every time you need them.

I’ve found a few other very impressive procedural planet projects so I might trawl their blogs to see if they mention how to do textures so well. So for next time…

Adding noise to the texture isn’t great, needs a good bit of tweaking. I could try to do a look-up table & incorporate slope as in this old post from Ysaneya (Infinity).
I need to hide tiling somehow, it occurs and is dealt with in the old post from Ysaneya above but the description is just “lighting, shadowing, other effects”.
I’ll need a better noise algo, the one I’m using is very homogenous (“samey”). This project called lithosphere might help find a good one quickly.
The FPS are struggling whenever creating patches & I’m not showing that many polys so I might need to do some optimisation. I pass data around a lot between CPU and GPU so I think these articles by Shawn Hargreaves might help find out if I’m CPU or GPU bound and try to balance both.

Lots to do!

Less Abnormal…

2012-01-17T23:43:00.001Z

This problem took me MONTHS to resolve. First I had to laze about and ignore it for about 6 months until a new year’s resolution made me look at it again. The problem is that each patch is created independently (i.e. it might not have any neighbours yet), so when calculating the normal vectors at the edges the normal calculation is biased towards itself. It’s kinda hard to explain in words so hopefully a diagram will help:

A normal is a normalised vector perpendicular to the surface at a certain point, it might help if you imagine walking on the surface, at peaks and troughs you’ll be upright but on slopes you’ll have to compensate by leaning in (or fall over whatever floats your boat). In this example, I’m trying to work out what the normals are for the green “patch” (the green V) and I don’t yet have the blue or the red patch. So I have to calculate a normal (pink arrows) for each of the 3 points in the green patch using just those 3 points.

I can work out the centre normal fully using the 2 adjacent points to the left and the right. However the left and right normals only have 2 points available (left & centre for the left normal, right & centre for the right normal) for normal calculation and so they end up perpendicular to the left and right vectors. When the red patch comes along it happens to work out well, the normal on the right indicates a slope. Unfortunately when the blue patch comes along it will look wrong. The left normal should be pointing straight up because it’s a peak, not a slope. If that wasn’t enough, to make matters worse when the blue patch works out its right normal it will look like a slope in the opposite direction so lighting will shade the slopes with a very sharp divide at the top.

In order to solve I could redo neighbouring normals whenever a new patch is generated but this would cause lots of rewriting the vertex buffer & would be visually obvious until the neighbouring patch was created. The way I opted for was to extend the patch area by one cell (equivalent to getting the middle point of the blue and red patches) and work out normals for all the inner points (same number of points as in the unextended patch). It worked out pretty well, here’s a before and after shot where latitude lines disappear:

And a close up with pink normals. On the peak in the before shot there’s divergence with normals at the same point going different directions. In the after shot the normals on the peak look like one normal but really they are 4 different normals all pointing in the same direction:

It’s a bit less obvious but on the mountain side you can see some lines caused by divergent normals where patches meet in the before shot disappear in the after. I made a gif to show gifferences but the 256 colour palette isn’t the best:

I think I’ll have a little look at texturing next, to get the planet looking like the terrain I had SEVERAL years ago… pretty shameful thinking this is progressing so slow but sure I’ll keep tapping away at it, one day at a time*.

*time may be anything from 6 months to a year or two!

Added (ab)Normals

2011-07-31T23:40:00.001+01:00

I had a go at adding normals to all the vertices on the planet and it had a pretty dramatic effect. I started off with an algorithm from … here … site seems to be down at the moment though. Anyways, I converted it to work with triangle strips and got some pretty nice results:

I threw in another planet in the background to look like a moon, textures are still non-existent.

There are some problems with this technique though, namely that the vertices at the edges (and especially the corners) of patches calculate their normal from a smaller number of connections – so there’s always seams between patches, and exaggerated peaks at corners… looks a bit like the labels are coming off…

I *think* the solution is to either share the edges between patches (but that might force me to do SetData on 4 neighbouring patches – very slow), or for each patch to generate more data than it will show, e.g. a 1-cell skirt around the existing patch.

There’s also some weird effect going on around ridges, maybe because the diagonals are longer so should be weighted differently? I’m hoping it’ll go away when I use a normal map… after I figure out how to generate it first! :)

Other than that I put normals on the trees (much easier) and implemented a recycling scheme so patches that weren’t used wouldn’t keep a hold on memory. One result of all the above work is that there are cracks in the patches again so I’ll have to revisit my LOD decision stuff… one step forward, two steps back, then get hit by a bus.

L-System Trees

2011-07-24T16:54:00.001+01:00

I continued working with the Algorithmic Beauty of Plants book and implemented parametric and context-sensitivity from chapter 1, made the trees from 3D tubes (instead of lines) and tried some of the examples from chapter 2 Modeling of trees. I had some success but couldn’t reproduce some of the models, mainly the section with tri-branching trees.

Here’s my results of the rules on page 56 varied with the parameters on page 57:

And here’s what the original ones from the book look like:

They look pretty similar, apart from (b). Note that in (b) the height of my version is the same as the other trees, but in the book it is much shorter. This is odd because the table on page 57 modifies the branch contraction rate (r₂) only, not the trunk contraction rate (r₂) which is always 0.9 so they should all be the same height.

In fact, it’s not clear what the height should be to get the above images as the axiom at the start sets the length to 1 and the width to 10, and if the length:width ratio really were 1:10, the result would be a lot more squat, like this:

And it’s still pretty squat at 10:10:

I found a ratio of 100:10 worked best to yield results similar to the book.

The experiments on page 59 looked pretty much identical to the book (again using a ratio of 100:10 so an initial axiom of A(100,10) instead of A(1,10)), here’s mine:

And here’s the books:

I had the least luck with reproducing the examples under Ternary branching. In the book (a) is shown as:

… which has a degree of irregularity… I don’t know where the model can get this as there is no stochasticity specified and the tropism applied is straight down (like the force of gravity), so why would the branch on the right bow down more than any other branch? My results show a much more regular model:

The closest of the ternary branching section I got was (b), although I had to fiddle with a few parameters (setting the width increase rate to 1.432 instead of the 1.732 given). Here’s the version in the book:

And here’s my result:

(c) and (d) were real headaches… I can’t get these to look anything like the ones in the book… I’m pretty sure something’s missing ar the parameters specified are wrong, especially the elongation rate (l_r) for (c); on page 61 it’s defined as 1.790 and all the others are 1.1 or less. Plugging this into my L-System/turtle interpreter results in a very tall tree (looking up at it in the first image and looking head on but zoomed out enough to see whole tree in the second):

I’m pretty sure my coding is right on this one, if you take the start piece from the axiom which is defined as F(200) and apply p2 (F(l) –> F(l*l_r) 8 times with l_r set to 1.790, this is the same as 200*(1.790⁸) which is about 21079. For the other trees, l_r is 1.109 and the base trunk height after 8 iterations of p2 would be 200*(1.109⁸) which is about 457. However the image in the book shows the tree as the same height and roughly the same proportion to its width as the other examples:

If I muck about with the parameters a bit I can get something that looks a bit more like it:

… but it’s not quite as nice. (d) is the same story really, can’t reproduce it from the parameters given… :(

I’m *pretty* sure I’m right but this book has been out since 1990 and there’s nothing specified in the errata. I tried to find these models in the virtual lab available from algorithmicbotany.org but no luck. So I might fire off an email and see if any one associated with the book can help me out…

Other than that I implemented horizon culling on the planet with a lot of help from an article at crappy coding, redid some of my basic rotation stuff (I had everything mirrored through the z axis), and tried to streamline how new patches are formed on the planet (it didn’t work!). I’m not sure what to do next, had a look at some demoscene programs and am now utterly depressed at how little I’ve done! I might try generating normal maps from the heightmap of a planet patch for lighting, maybe do atmospheric scattering, texturing of the planet and/or trees, adding leaves maybe? Hiring someone else to do this for me?? :)

GPU Planet Update

2011-06-14T12:18:00.001+01:00

Jeez, I can’t believe it’s been almost 2 years since I last did anything with this… I picked it up again a few weeks ago and tried to get into it again, made a little progress and thought I’d share.

A major problem getting back into it was migrating from XNA 3.1 to XNA 4 – there are lots and lots of changes, one of the worst I found was the restrictions placed on shaders and the Reach and HiDef profiles. I found an article which described how to target Reach and HiDef with the same project which was very handy, otherwise I’d have to develop 2 separate projects in parallel if I wanted to use both of my laptops for developing (one’s far more portable than the other but has to be Reach). So with a lot of help from this cheat sheet I got my project running again, and tried to learn a bit about shaders to see if I could get GPU noise back on shaders less than version 3_0_0.

In the process, I used a ping-pong technique to create Conway’s Game Of Life simulation (much better in 1080p):

The next stage then was to get back to the original goal of getting the GPU to generate all the noise as I found out doing noise in software was far too slow.

The plan was to pass the vertices to the shaders, let them calculate the noise then get back a heightmap which I can use to update the vertices. One of the problems was that the vertices form a curved surface and I need to flatten it for the pixel shader to give me back a regular heightmap. As each of my patches has texture coordinates that go from 0,0 to 1,1 I can create a flat image that the pixel shader could work with by using the texture coordinate to generate the position in clip space and storing the original position –which the shader will use to get the noise- in a texture coordinate. So for example, a point at 123, 234, 345 with texture coordinate 0.5,0.5 would end up in clip space at position 0,0 (clip space goes from –1 to 1) with the position stored as a texture coordinate. There’s a problem with halfpixel offsets as Drilian describes, in the end my shaders look something like this:

struct vertexInput {
    float4 position        : POSITION;
    float2 texcoord        : TEXCOORD;
};
 
struct vertexOutput {
   float4 hPosition        : POSITION;
   float3 wPosition        : TEXCOORD1;
};
 
float texel;
vertexOutput VS_flat(vertexInput IN) 
{
    vertexOutput OUT;
    float clipx = 2 * IN.texcoord.x - 1;
    float clipy = 2 * -IN.texcoord.y + 1;
    float4 clipPosition = float4(clipx - texel, clipy + texel, 0, 1);
    OUT.hPosition = clipPosition;
 
    OUT.wPosition = IN.position.xyz;
 
    return OUT;
}
    
float4 PS_noise(vertexOutput IN): COLOR
{
    float3 p = 0;
    p = IN.wPosition;
    return inoise(p)*0.5+0.5;
}

And this technique let me create fBm on a 2_0_0 pixel shader by adding each stage of fBm in separate ping-pong passes:

I used this in my original project and tried to update the vertices given the heightmap values generated by the shader. This didn’t work initially, I ended up with lots of cracks because of the way the pixel shader interpolates.

The upper left point (at tex coord 0,0) would have the correct noise value but I couldn’t get the lower right point to draw the correct noise value at tex coord 1,1. When 2 patches met they would have different height values for the same vertex. In the end I managed to get around it by rendering using a line-strip instead of a triangle-strip. This picture shows the same noise values along the edges of the patches:

So, although it looks like I’ve made almost no progress since about 3 years ago (yikes!), I have! … made almost no progress that is :) The main difference is that this planet can render at run time – all the other planets had to have some pre-rendering of some sort, here’s a little fly around at 17x17 vertices per patch so you can see popping and subdividing:

In the end… it might be better to generate all the noise every time, for the vertices and for the pixels, caching the vertex info and texture is very heavy on memory. Hmm what’ll I work on next for an update in 2013…

Blooming Starfields

2009-12-24T20:15:00.001Z

It took AGES to add bloom. I used an XNA tutorial for bloom and in order to do the various passes (pick the brightest spots, blur it, recombine with the original image) it called ResolveBackBuffer to copy the back buffer to a texture for the next pass. I don’t fully understand it yet but it seems this call would invalidate the back buffer and subsequent shaders would write as if they were the first. I’ll try to illustrate what I mean by showing the problems I had. My plan was to draw the stars & clusters first, bloom that, then add the nebula.

Here’s what the result was like without the bloom stage, the nebula is added to the background stars (no bloom) as expected:

And here with the bloom stage included in the middle, it seems to be overwritten by the nebula stage:

In the end, I did a ResolveBackBuffer to a ResoveTarget2D after the bloom stage and drew this to the back buffer before I call the fBm/nebula shader. This finally ended in what I was looking for.

I’m still not 100% happy with the results, I had imagined the bloomed background stars would really light up the nebula but they seem to actually be dimmer than the stars outside of the nebula. I might try to use the same fBm noise result to draw some stars so they are in place in the densest parts of the nebula.

The main thing I’m not happy with though is that the code is a total mess, I just kept hacking and hacking away until I got results. I’m sure a team of monkeys would have produced neater code in less time. It’ll be a while before I get these images into a skybox – so until then HAPPY CHRISTMAS!

Procedural Starfield Texture (First Go)

2009-12-24T00:00:00.001Z

I decided to try my hand at a procedural starfield. I figured it’d be an easy enough shader to do (I’m still a total beginner) plus I’ll need to use the same techniques to generate cached images of planet patches (previous GPU noise posts were generated per-pixel every frame). So I started off with some blue fractal Brownian motion noise for the background:

And added some code to make simple noise white if it were over a certain threshold. I thought these would appear as stars, but it was all blobby:

So then I scaled it by passing p*scale instead of p to inoise:

Not bad… but the stars (little blobs) are too generic so I added in another layer of noise but at a second scale (bigger blobs) so it looks like brighter stars or clustering:

It looks ok… a bit lame though… The problems I see are that the stars have aliasing artefacts and the scene doesn’t … impress. Zoomed in the stars look crap, like Tetris blocks or something:

I think it needs some effects like glow or bloom or MORE BLOOM! So I’ll look into that next.

Here’s the shader code so far, pretty simple stuff:

vertexOutput VS(vertexInput IN)
{
    vertexOutput OUT;
    OUT.hPosition = IN.position;
    OUT.texcoord = IN.texcoord * noiseScale;
    OUT.wPosition = IN.position.xyz * noiseScale;
    return OUT;
}

float4 PS_test(vertexOutput IN): COLOR
{
float3 p = IN.wPosition;
float res = fBm(p, oct, lac, gain);
float4 color = res;
color.rg = 0; // make it blue
color.a = 1;
float star = inoise(p * speckleScale);
if (star > speckle)
color = lerp(color, star, 0.9);

float starcluster = inoise(p * speckleScale2);
if (starcluster > speckle2 + 0.1)
color = lerp(color, starcluster, 0.9);
return color;
}

technique test
{
    pass p0
    {
        VertexShader = compile vs_3_0 VS();
        PixelShader = compile ps_3_0 PS_test();
    }
}

GPU Perlin Noise

2009-12-21T15:31:00.001Z

I updated my DirectX before starting and somehow my MDX project became all liney, like this:

Because of this, and because most of the online samples I find to ~~plagiarize~~ be inspired by are usually in XNA I decided to convert. Unfortunately there’s no automatic conversion tool so I had to open a new project, add my old files and try to fix up the errors. Some things were annoying, like the lack of absolute mouse movement and having to load a font from a file (size is fixed in the file) but overall the classes are better named and organised. Here’s my first shader on the planet in XNA, stripes:

So after a quick crash course on shaders, I found Perlin had published HLSL code for Improved Perlin noise in GPU Gems 2 – all of which is free online! I had real trouble getting it going however, every texture I generated was blank, and I didn’t know enough about HLSL to figure it out. There seemed to be a tutorial on ziggyware but it seems ziggyware’s been under attack from hackers so I couldn’t get it. I tried out some other projects like Drilian’s but again the XNA version I made the noise didn’t work. Eventually I found a post where someone had similar problems, which led me to the Google cache of the XNA GPU Perlin noise tutorial – by Patrick of recreationstudios (he’s made some amazing progress since I deserted this project 2 years ago). All I needed to do was initialise the textures all the noise functions use. Perlin had functions to do this in HLSL, but I hadn’t a clue how to call them, supposedly you can’t in XNA so I moved the HLSL code to C# then create the textures on the CPU and set the textures on the GPU. Patrick’s tutorial explains this much better (prize-winningly better apparently) so I won’t go into details.

So here are some screens of different types of Perlin noise on the planet:

In these shots the noise is being calculated per-pixel each frame based on the geometry. Surprisingly, getting closer to the planet so the level of detail is higher (the 4 child patches are drawn instead of the parent patch) didn’t change the surface visibly. This had to do with the fact that there wasn’t much geometry difference between the parents and the children, when I changed the patch size from 33x33 to 5x5 there was definite popping in the textures.

Here’s a video of flying about a bit:

Update: shading every frame means I can animate!

Procedural LOD Planet Textures

2009-12-09T18:38:00.001Z

I got a rough draft of procedural LOD planet textures working and thought I’d share some screenshots. The main difference between this and the last post is that this planet subdivides its patches and generates a new texture for each new patch as the camera gets closer and the planet in the last post was just static (it only generated vertices and textures at start up). Currently, all the textures are created in software so it’s hella slow, too slow to play really. Once a texture is generated and cached it’s very fast (capped at 60fps). On-the-fly however even with a texture size of only 17x17 pixels (same amount of vertices per patch) it’s jerky. Here are 6 levels of 256x256 textures zooming in on the one spot.

Next steps are to try to speed it up so it’s acceptable to play with, so I’ll probably do 2 things; use EQATEC to profile my app and do the image generation in hardware. But before I do that, I somehow messed up the geometry so it’s clockwise instead of anti-clockwise… or the other way around… whatever I did anyways I’ll try to undo.

Update: Here’s a video, fraps and windows movie maker seem to work well with youtube, my previous efforts at uploading video turned out horrible! I’m only running the textures at 17x17 so the video runs smoothly (i.e. I know it looks like a big steaming pile of sh!t).

Seams Like Years…

2009-12-07T21:55:00.001Z

It’s been a while since I updated this… a really long while, but I’m going to try to get back into it again. My current problem is something I never really fixed the last time: seams. Here’s an example:

Weirdly enough if I save the textures I generate for the faces they line up fine with no seam (the darkish hole should line up with the pit above):

So, having changed my texture generator around a bit I’m 100% sure it’s ~~my texture code~~ ~~some sort of floating point error~~ how MDX is texturing the faces. There must be a way to get MDX to just display the bitmap I give it & not mess up the edges…

Update 1: I had some mag & min filtering going on which was causing some (but not all of my seam problems. When I got rid of this code:

//    device.SamplerState[0].MinFilter = Direct3D.TextureFilter.Anisotropic;
//    device.SamplerState[0].MagFilter = Direct3D.TextureFilter.Anisotropic;

It looks like this now (still a problem with top and bottom patches but going from front to left to back to right and back is seamless now):

Not sure what’s causing it, but you can see from front to top to back to bottom the textures I’m generating seem to be slightly offset – the image on the right offsets them in the correct direction and they seem to match much better.

Update 2: There were some errors in how I collated the heights from sub-patches, now top to bottom match up perfectly, and I have no seams!

Next back to the adaptive planet (the one that properly changes its patches depending on LOD) and an attempt at making the textures in hardware.

Stochastic LSystems

2008-09-24T00:42:00.001+01:00

I don't have much of an excuse for not working on this poor project and it's withering blog. Work's gotten really busy but also I've gotten interested in a few other side projects (I want to build myself a monome & I want to do these Wii hacks)... I'm hoping to bring the new stuff into this project somehow so that it doesn't call social welfare on me for neglect... and if it does I hope it doesn't walk into another door or fall down the stairs again.

A very simple change to where I left off was to introduce a bit of randomness to the L-System so that not all plants look the same. The only difference between a normal L-System and a Stochastic one is that with the stochastic one there's a certain probability of each production rule being applied. So now the plants appear in all sorts of shapes and sizes but still plant-like:

In order to show the 3D-ness of them all I arranged a few plants in a grid and tried to record a fly-about. Unfortunately it wasn't smooth at all (I've only a track-pad - I'll get a mouse soon) so I put a bit of velocity into the camera movements so that the camera keeps going whatever direction I pushed in. I tried to move about randomly in time with whatever music I had on in the background. It's hard to describe but it was really really fun - I was terrible at it and messed up so many takes spinning out of control into yellowness.

I got a couple of decent takes (relatively speaking), but when I try to compress it for youtube it turns out all jerky and crappy so I might give it another bash tomorrow and update this post.

L-Systems in 3D (lines)

2008-07-25T18:55:00.001+01:00

It's been WAY too long since I updated this, I'd like to say I've been doing more important things like saving the world or something, but nope, nothing. I've spent most of my free time addicted to a game called Oblivion, it's a great game. I guess you could say I have been doing some good by saving the good citizens of Cyrodiil. Although... that's not strictly true, I murdered a good few of them. To make it seem like I wasn't just playing a game all the time let's just say I was doing research...

I'll be away from the XBox while I'm back in Ireland so I decided to pick up where I left off so I migrated the L-System stuff I had in the WPF test project over to my DirectX project. It was pretty easy, here's the fractal plant in 2D but in the DirectX app.

I then wrote a turtle-graphics class that would traverse the L-System's result and draw in 3D. The result is still pretty flat because it's just lines and a picture doesn't really do it justice, so I uploaded a video to show what it looks like:

I'm not sure what I should do next... but I think I'll have a go at making the 3D turtle graphics construct a polygon model from the L-System output instead of a line-model. It doesn't get me any closer to procedural cities but it'd be cool to have procedural trees.

L-Systems

2008-06-13T00:32:00.001+01:00

I spent some spare time today doing a first draft at an L-System. I was always intrigued by how nature is apparently governed by mathematics like the Fibonacci sequence. L-Systems are basically grammars used commonly to model growth as it occurs in nature and to develop self-similar fractals. A stochastic L-System (an L-System where each possible change has a certain probability of being selected) is what was used in this procedural cities paper for SIGGRAPH 2001. There are some other methods, but I don't think they are as realistic as what Mueller and Pascal had done. The L-System (with some add-on rules) is used to draw out the streets and also to generate buildings with different LODs. I'm not sure where to go from my basic random-blocks-on-a-plane so I decided to look into L-Systems to try and generate a realistic city. But first things first, here's a fractal plant (L-Systems in WPF):

I coded a basic L-System and turtle graphics (something that draws whatever the L-System generates by following it like a path) and got the grammar for the plant on the wiki page. It looks very like something you'd find in nature, but it all follows a strict grammar with only 2 rules and if you look for it, you can see the self-similar patterns. It does take a while to execute however, especially at high iterations. This site has a few of the common L-System grammars in a java app so you can play about with different grammars/iterations etc. and here's a gallery of other simple fractal forms. Here's one more from my little app before I hit the hay - an arty close-up of part of a Koch snowflake:

I'll be honest, it's not arty, what it is is it's too fecking late to be messing about with WPF is what it is so screw you! Goodnight.

Sharing is a bad thing

2008-06-10T13:06:00.001+01:00

I took a bit of time out to do some performance testing, partly avoiding procedural cities as I haven't a clue how to go forward but mainly to see what could cause my planet to be so slow when rendering a pretty low amount of polys. I created a new project and ran some tests to get a benchmark, here are results for one patch getting larger as time goes on:

Sharing the one vertex buffer is pretty much worse than having no vertex buffer at all! I tried to see if 50 objects each with their own buffers vs. each sharing the one buffer would make any difference, but nope:

Weirdly enough though, 75% of all pie-charts look like pac-man:

Creating and deleting buffers on the fly for the planet just won't work as I found with earlier experiments with quadtrees. Although I did find out that the garbage collector can't clean up buffers because behind the scenes a load of events are hooked up and these all have references to the buffer. Setting Device.IsUsingEventHandlers to false can turn this off.

Sharing isn't efficient either. A bunch of buffers will have to be created on startup to be exclusively used by each patch. Working out how many and what size will be another performance analysis job... is it simple enough that I can keep procrastinating procedural cities? ... probably not.

Welcome to Randomville

2008-06-05T16:37:00.001+01:00

I had a quick bash at doing a procedural city with some very basic ideas I had - it's really simple but already looks city-like. Check it out.

You can probably tell from looking at the images but all I'm doing is creating a grid of Mesh.Box(es) with random heights - biasing the height of boxes in the centre to be higher than the boxes on the outskirts. This image might show it a little more clearly.

In the next image I randomly eliminated some of the boxes (biasing the elimination more towards the edge than towards the centre). I think it looks a little more realistic.

Flying around the city really gives a better city-feeling than looking at a bunch of boxes. I tried to record a video but I couldn't get a smooth flyover using my touchpad and my *ahem* skills. It doesn't look too bad but I won't post it as I'd be worried if someone saw my flying skills they'd think I was planning another 9/11.

I've found the Bible!!

2008-05-30T16:22:00.001+01:00

No, not in that way, my head still vomits while spinning all the way around when I'm near a church. I've gotten a book which has contributions from a lot of the researchers at the top of the procedural content generation field. It's called Texturing & Modeling: A Procedural Approach. It's (expensive but) friggen awesome! I was a bit worried it would be like a scientific journal -that is, just a collation of papers- but every concept is well explained and structured (and sometimes comes with a little bit of code). I'm convinced Infinity uses this book as a basis for his engine.

I've had a rethink about how go about developing this game. Instead of getting into great detail in one area then when I'm happy move on, I'm going to get something somewhat reasonable then move on. Basically I want to quickly prototype the game and see what it's like, and afterwards spend time refining and polishing it. Getting bogged down in details often led to the demise of a few of my previous projects. I think I'd like to look at generating procedural cities next.

I've decided to use del.icio.us to bookmark and organise (with tags) all my areas of research as I come across them on the internets. My personal set of bookmarks is at http://del.icio.us/jellyedwards, keep in mind I've only started to use del.icio.us and it also will contain tags for non-game-development areas of interest I have (like WPF, wiki-projects, TED, music). Incidentally, I've started another blog (nothing in it yet) for a food-based wiki-project. I've no idea if it'll work out or not, so I might post whatever other wiki/web 2.0 (hate that name) ideas I have there.

I'm really enjoying researching a bunch of random things but nothing's actually getting done so I've got to get back into it.

Procedural Textures - Tile/Wrap

2008-05-27T00:39:00.001+01:00

I've decided to take a break from the planet geometry stuff to look into procedural textures. I've already gotten a few free pre-generated textures which I used in earlier posts, but the idea of generating everything procedurally really appeals to me for some reason. My level of knowledge in this area is - like most other areas - minimal, but from doing some research I'm starting to get a feel for it. The demoscene is where most of my procedural texturing/modelling research ended up, and the demos ... are ... absolutely ... amazing... Then you find out that they (sometimes) managed to stuff all the code into an executable less than 64KB!!! Infinity is by far closest to my aspirations for this project, his work has incredible detailed planets in real time with all sorts of fancy effects. One of my favourite images from his work compares a NASA space shot to his generated planet (Dec 14th 2005).

Back to the main topic though and for procedural textures I think the guys from the produkkt have got it nailed. They have a free tool (that is, free to use the textures it generates not the actual code behind it) called werkkzeug which demonstrates their method for creating realistic textures procedurally. If you have any interest in this stuff you should definitely try out their tutorial. I've seen other examples for procedural texture generation which are cool in principle but kinda limited. I was really amazed that realistic textures like this rusty barrel can be done with a bit of Perlin noise and layering other effects. It's just the tutorial though, the gallery has more impressive textures.

So... If you checked out the links above, reading the next section where I talk about work I've accomplished is gonna kinda be like when you walk onto a intercontinental plane... First you see the first class seats and think "sweet!!" then move on to the business class and think "sure, it's not as nice as first class but it's still pretty sweet, economy can't be that bad"... Then you finally end up behind a curtain in the economy section where there are babies screaming and chickens flapping about the place and everywhere smells of sweat and cheese.

Whilst still recoiling in shock and disgust - the stewardess moves you along to where you're really seated - the cargo section. Welcome to the update of my work!

I redid my Perlin noise app in Windows Presentation Framework (WPF) - partly to start WPF and partly because I heard it was faster than the unsafe pointer-bitmap stuff I was doing before. There was a bit of a learning curve, but I'm pretty happy with the results - as an aside I'm ecstatic that WPF will be replacing ASP AJAX and javascript as that's my main job and it's more frustrating than ~~Hugh Hefner without viagra~~ ... playing pool with a rope. Here's the app:

My main goal was to create a tileable/wrappable Perlin noise function so that I can eventually seamlessly tile my procedural texture. I followed the example at the bottom of this article by Zucker, and it took a long time to sink in.

public float GetTileableNoise(int x, int y)
{
    return (GetNoise(x, y)*(tileWidth - x)*(tileHeight - y) +
            GetNoise(x - tileWidth, y)*(x)*(tileHeight - y) +
            GetNoise(x - tileWidth, y - tileHeight)*(x)*(y) +
            GetNoise(x, y - tileHeight)*(tileWidth - x)*(y))
        / (tileWidth * tileHeight);
}

I'm convinced this code could be a lot better:

werkkzeug seems to create a tileable Perlin noise texture instantly while this code is hella slow

there are some ugly tiling effects (cross-mirror I calls it) with certain combinations of noise

becomes

I'll carry on with noise and textures for the time being, trying to speed it up in various ways (move to hardware texture creation perhaps?) and maybe think about implementing a poor-man's werkkzeug to play with texture creation.

Neighhhhbours, everybody needs...

2008-05-24T16:22:00.001+01:00

...to-know-the-orientation-of-themselves-to-their neighhhhbours, that's when non-uniformly-laid-out neighbours, become good-at-preventing-cracking-due-to-different-levels-of-detail-and-also good friends.

Just as in the soap, my geomipmapped planet needs to take care when linking a patch to one of it's neighbours. However, whereas the soap intended to create cracks between neighbours, my objective is the opposite. Each patch at any level of detail is set up to have 4 children: top-left, top-right, bottom-left and bottom-right; and 4 neighbours: north, south, east and ~~kylie~~ west. This image (which I use as a texture for debugging) should make it clearer. The text "back" at the centre is just so I know from which of the main cube faces (my sphere is really a subdivided cube) this patch comes from.

The neighbours of the main faces of the cube are set up manually at the start, but they need a way to set up the neighbours of their children when they are subdivided. The internal neighbour case is fairly trivial for when a patch subdivides:

east of the top left child is the top right child
west of the bottom right child is the bottom left child
north of the bottom left child is the top left child
south of the top right child is the bottom right child
and so on...

To get the external neighbours for its children a patch will have to look to its own neighbours, so:

east of the top right child is the top left child of the patch to the east
south of the bottom left child is the top left child of the patch to the south
and so on...

This might perhaps be more obvious in the following diagrams where the level of detail goes up by one for the patch at the back of the cube.

In the first image the top left child gets subdivided and it would set its own top right child to have the main patch's top right child's top left child as its eastern patch. Confused? Maybe this will help:

backPatch.topLeftChild.topRightChild.east = backPatch.topRightChild.topLeftChild;

This can be generalised to work recursively (assuming east is set up correctly) to:

patch.topRightChild.east = patch.east.topLeftChild;

Basically, for a child to find its external neighbour (a neighbour from outside its own family) it will have to look at its parents neighbours. If a person wanted to find out their cousins, they would have to find the children of their parent's siblings.

Ok got it now? I hope so, because I went through the same confusion only to find out it doesn't always work.

If you stand at the north pole of the earth, any direction you go in will be south. This doesn't play too well with my north, south, east & west neighbour collection. These 2 videos show the problem, if you set the main cube faces so that moving east to west is ok, moving north to south will be problematic (they look upside-down compared to each other). You could fix it so north to south worked ok, but then east to west wouldn't work.

Moving east to west matches up

Moving north to south shows up clashing patches

The video is a bit blurry, so here's an image highlighting the problem, it shows the where the front (A), right (B) and top (C) patches meet. Because the top patch only has one south, it clashes with the right patch (if I go north from the B then go south again, instead of ending up back at B where I started - I end up on the front patch A).

This can cause cracking because neighbours aren't actually neighbours. If the code for setting the top left's north was like this:

topLeft.north = north.bottomLeft;

For north neighbours, it would work for A to C but not for B to C. For the case of B, north of topLeft is actually north.bottomRight. B.topLeft should look at C.bottomRight when it's rendering otherwise it might try to fix a crack when it's not there or vice versa. The solution is to look at the orientation of the current patch to the north patch, for example if this patch (B) is to the east of this patch's north (C) then topLeft.north = north.bottomRight. I found it difficult to visualise what neighbours go where when I was writing the code to handle odd orientations so somewhat embarrassingly I cut out 2 bits of paper and used that to help.

Of course all of this is my own meandering implementation, there are much more elegant methods out there by people who know what they're doing (like Sean O'Neil's). There isn't even a bit of crack to be seen with these neighbours, if only that were true of the soap. Next I'll do some clean-up with the code, and look at generating the base textures from scratch.

Planets 0.4.1 Cracks & Holes

2008-05-21T20:38:00.001+01:00

I haven't blogged in a while, even though I've been tapping away at the code I'm afraid little progress has been made. The main function I've been concentrating on creates a triangle list for a patch with respect to cracking and also holes or partial patches created by some but not all children being drawn. I wouldn't say that I'm a neat coder but I do know when things get out of hand - I really don't know how I can make this function any simpler. Because of this, I don't have much confidence in the code being bug free. However last night it all seemed to come together:

Until I saw this bastard hole at the bottom.

The thing is there are 56 (8 choose 2) different possible index layouts taking into consideration compensating for combinations of holes and cracking. I should either (1) write an automated test for each of these combinations or (2) start over. I've decided to be lazy and go for option 3, try to fix this one and hope it's the last. But I will make a public promise here in my blog that if there's another anomaly after this one I'll write tests for each case.

Let's be honest, if that happens I'll go for option 4 and edit the blog not to have any promise of doing testing at all.

Planets 0.4 - Geomipmapping

2008-05-04T19:30:00.001+01:00

I was avoiding doing this for so long, but in the end it's a really simple solution. It's a familiar problem, quad trees are great and all but they are really slow when you're trying to render a high detail (well at least the way I implemented them). Each quad has 9 vertices and renders by drawing a fan. Previously I had given each quad its vertex and index buffer and this was a nightmare to clean up on program exit, it would just take AGES! I only found this out but it's no big hit to just share a vertex and index buffer between loads of patches just set the needed data before each render - the clean up is almost instant. So here's what a geomipmapped quad tree at level 8 looks like:

It's only about 20,000 polygons but it's rendering at only 2 FPS, so unless I include sloths in my game demographic I'll have to improve on the speed. I thought the main problem stems from the fact that I'm doing about 2,500 renders of only 8 polygons in a fan and that it would be a lot faster as a triangle strip. I tried to think of algorithmic ways of aggregating all the vertices in a quad and rendering as a triangle strip - when blood started coming out of my ears I decided there must be a simpler way. So in the end the solution was a combination of (what I call) CLOD and quad trees - basically each quad tree patch can draw way more than just the 3 x 3 vertices in a fan, let each patch draw a triangle strip of (say) 17 x 17 vertices. This way I can reduce the levels needed to render a planet in high detail. Hopefully the next images will make this obvious:

In the first image on the left I'm showing (with holes) the old way, a really low detail quad tree, and each quad patch draws a fan. With the new way shown in the image on the right, the quad tree has the same number of levels as in the previous image but each quad patch draws a 17 x 17 grid. The result is that the planet has a much higher level of detail, but the quad tree doesn't.

The trade-off is that the polys aren't culled as accurately as before but that's nothing compared to the gain in FPS (back up to 60 again) for reasonable detail. I'll need to fix holes, cracks and level of detail calculations next, all old news...

Planet Optimisation... Vertex and Index Buffers

2008-04-25T16:16:00.001+01:00

Not a very interesting post I'm afraid, all I did was optimise a bit (mainly moving all the vertices to a vertex buffer and creating one index buffer for each cube face). Now I can render the planet at a level of detail of 8 (about 750,000 polys) at a reasonable FPS of 50 - before at level 7 (about 200,000 polys) I was only getting 1 FPS!

I still have a seam problem where the 2 cube faces meet (it's most visible in the bottom right of the second image above) and I think it has to do with the fact that the base textures I have don't wrap in every direction.

I'm not looking forward to implementing CLOD on this sort of sized terrain. I've had issues with Quadtree before where it just took up a load of memory and slowed everything down. I need a good way of aggregating the vertices in the patches I render - and I'm at a loss. Also, I need to be able to dispose of patches I don't use without effecting FPS - I tried this before but with little success.

Planets 0.3 - Texture

2008-04-24T13:56:00.001+01:00

I'm not sure why I didn't think of it before, but texturing the planet isn't difficult, each face of the original cube is square so I can just apply the same texturing technique as I did before. I just have to recursively get all the noise values to a certain level of detail, normalise it and use this as a height map. The first go at this wasn't so successful.

I used parameters that would create a more asteroid-y looking planetoid just because it's easier to see where the problems are. In the above image I had set a texture coordinate wrong and this recursively led to the whole image looking really scrambled. After I got the coordinates sorted, the next problem appeared:

Basically, because I generate a height map and a texture for each patch (cube face) independently, what might have been the highest height for one patch, isn't the highest for another. So although one patch shows snow for its highest point, the neighbouring patch has higher points than that so it won't use snow for a point of the same height. I probably made that even more confusing than it actually is. Anyways, all I had to do was normalise all the patches with respect to all the other patches. The texture is starting to look like it's covering the model well - but there's a little seam to stretch over...

Now I've a textured planet! Unfortunately, I think the texture looks far too homogenous (looking the same all over) for an Earth-like planet.

However they seem like pretty good parameters for a moon or something like that, I just changed a few of the textures and got this moon.

Oh no... why did I do a full moon??? Now I've got hair growing on the backs of my hands and.... oh no... not now... I've turned into Michael J Fox in Teen Wolf!!! AWOOOOOOOOOOOOOOOOOOOOOOOOOOO!!!!!!!!!!!!!!

Planets 0.2 - 3D Noise

2008-04-23T14:21:00.001+01:00

Geekily enough I have to say adding 3D Perlin Noise to the planet was a lot of fun - it really wasn't a lot of work to move the 2D Perlin Noise code to 3D and I quickly got some visual results. It's frustrating sometimes working with graphics to toil away and have no big change to show for it. The same goes for any programming really, fixing some memory problem can often be a lot more work than creating something visual but the visual change is an obvious and immediate reward. Here's my first application of 3D noise to the procedural sphere:

Not bad eh? It turns out a lot of geography/astronomy books have totally the wrong idea on how planets look, and it took a lot of origami to make the books mimic what my code produced. Then I thought of having to do all those folds to all those already published books to conform to my model, and I caved to making my model a little more like what the books say. Here are a few different levels of detail for the planetoid - you can see that the noise is always coherent at different levels of detail and doesn't change too much from the previous/next levels.

Here are a few attempts at a less-asteroidy-more-planety model. The main changes were increasing the frequency parameter of the Perlin Noise and decreasing the height change that the noise would realise. The last one looks most realistic, but on a proper planet, you could barely see the mountains at a distance because the height-scale is so negligent compared to the scale of the planet.

Here's a higher level of detail on the surface of the last planet, next I'll need to texture that landscape...

Planets 0.1

2008-04-22T22:47:00.001+01:00

It was really simple to get a little procedural sphere going from a cube, just keep subdividing each face into 4 smaller faces. After thinking about it, I don't think I needed to do anything special to create a planet model because if I texture it with 3 dimensional Perlin noise even a sphere model with a lot of pinching would be fine - anyways, texturing a sphere is for another day. Here are some of my results, FPS doesn't seem to get affected until I get to a level of detail of 5 and then it all goes pear-shaped fast.... well egg-shaped as you'll see...

All bar the last run at 60 FPS (I have vsync on so we can safely assume that the actual FPS is more like 60,000,000 FPS). The last one runs about 30 FPS but this is all pure software, I haven't done anything yet to optimise. Level 6 runs about 7 FPS and level 7... What happened to level 7???

In my sheer brilliant-ness I must have implemented astrophysics while I wasn't really concentrating, this mass of matter is obviously collapsing on itself and probably would implode... and if it ran faster than 1 FPS I'm sure it would look fecking awesome, but I didn't stick around to find out.

So after optimising the sphere stuff a bit, next I'll try to create some textures with Perlin Noise. I get how it works, I'm just a little confused as to how to implement it efficiently. For 2D textures, I have an image that's stretched over the terrain and I give texture coordinates to each point so DirectX does the rest. I can visualise how a 3D Perlin Noise texture looks (like a solid cloud, any slice will create coherent texture and so would a sphere carved out of that material) - but I've no idea how to tell DX about it. I may have to go with colouring each vertex, and then stretching a detail map over it all, but that seems to me like it would look like all kinds of shittyness unless I go to a level of detail so high my planet turns into an egg.

Perlin Noise And Fractals

2008-04-17T12:24:00.001+01:00

I read up on Ken Perlin and wanted to try do some terrain using Fractal Brownian Motion. Ken's homepage has tons of little Java applications that each do something innovative with noise - it's good to play about with. Ken came up with a fast way of creating noise and used it to create natural looking textures. He even won an Oscar for this technique! I had a look at his code and to be honest it was very difficult to follow, sort of like it had been obfuscated. So I looked elsewhere for info but found a lot of people did a sort of hack on Perlin Noise - basically fill an array with random noise and smooth each pixel using the values of neighbouring pixels. I tried this technique out and I wasn't that impressed with the results. It doesn't look too bad but when on an actual terrain, I think it looks too artificial - like the mountains have a grid-like pattern (I tried to highlight this in red on the terrain).

So with the proper Perlin Noise/Fractal Brownian Motion implementation, I think the results are a lot better. To start I wrote a little app so I could quickly try out different combinations of the parameters, here's a screen of it, and some of the results:

Here's some terrain built with a Perlin/fBm height-map:

Another cool thing about Perlin/fBm (if you're a geek I suppose) is that it can be applied to three dimensions too, so I should be able to use it for seamless planet height-maps and textures... but haven't worked it out yet. Often when applying a 2d texture to a sphere artifacts appear, like pinching at the poles, but Perlin/fBm should be fine - we'll see!

Next I really need to do some clean up on my code and after that I'll either look at:

making a sphere by recursively splitting a cube's face or...
generating the grass, snow and rock textures with Perlin noise

Adaptive Quadtree

2008-04-16T23:08:00.001+01:00

I tried hard to optimise my code but in the end I just don't think a quadtree is suited to very large terrain. Here are some of the things I tried:

The quadtree is now adaptive meaning it only creates children if it needs them to render a more detail
I tried to Dispose() of unused resources on the fly but this really slowed down FPS
The quadtree now uses a shared vertex buffer reducing the number of calls to the device (before each patch would have its own vertex buffer and its own index buffer)
I tried using NProf to do some performance analysis on my code, but it didn't help me target anything in particular

I'm not 100% sure but I think the main problem is the number of objects needed to render a quadtree increases exponentially when the terrain size increases. With CLOD the number of objects is pretty low in comparison. For a terrain length 256, I use 16 CLOD patches but I would need over 20,000 quad patches. It's a shame, I think quad is neater in the same way that binary search trees are neat. Check out some comparison shots of a large (1024 * 1024 vertices) terrain:

They look similar enough but for the quadtree I was getting about 4 FPS and for with CLOD I was getting between 20-30 FPS. I'll stick with CLOD for planets I think.

Quadtree Holes Fixed

2008-04-10T16:33:00.001+01:00

I got the holes fixed, it really really hurt my brain. You can see the results here compared to CLOD. There's nothing that different really, just the same terrain with no holes in it. The weird thing is that the quadtree renders a LOT less polys but the FPS is lower. Also, if I try to render a large terrain, quadtree crawls. I'll have to do some optimisation on it next.

You can't see it in these pictures but sometime I have these intermittent tiny dots of yellow (so a tiny hole way smaller than a poly) on the quadtree and also tiny hairline cracks with both CLOD and the quadtree.

I think part of the problem is that I'm using my base object which allows an object hierarchy of children to be recursively attached. All this hierarchy does is move each attached child if the parent object moves, so for example, if you move your arm but don't move your hand relative to your arm, your hand should still be in a different position. This is neat for some applications but I think perhaps it's adding unnecessary overhead to the terrain: the patches are all statically fixed unlike joints in an arm. There are inevitable tiny floating point errors which with tons of children attached - like with the patches - is probably causing the hairline cracks. The matrix calculations are adding to the CPU cycles and may be why my quadtree appears to run slower than my CLOD while showing less polys.

So, reluctantly I'll have to overhaul some code and do some optimisation. I hate overhauls, there's little or no visual improvement for a lot of work, but as it stands I think it would take my engine longer to create a world scene than it took the world to be created (even in Creationist terms!) ... stupid Creationists.

Quad Tree Termites

2008-04-09T15:36:00.001+01:00

It's taking a lot longer than I thought but the quadtree implementation is finally taking some shape. Real work (stuff that pays money) took over for a bit so that slowed things down a lot - I also had a holiday around Spain and over to Morocco which was good fun. I climbed a couple of mountains there and I must say God/Buddha/Allah/String theory/Ekpyrotic theory did a good job - no cracks, high detail, no obvious texture repeat and good continuous level of detail (although I wasn't moving very fast). I'd like to see it run on my laptop though.

So anyways, here's a comparison of splitting for CLOD vs. Quadtree in wireframe mode, you can see that the Quadtree is much more precise, the camera position causes a circle of split patches:

The number of polygons rendered is much lower than CLOD, mainly because the frustum culling is much more precise due to the recursive nature of the quadtree implementation. However, I'll need to do a good bit of optimisation, despite the lower number of polygons rendered, the overall FPS is suffering because (I think) of all the recursion needed to draw all the low level polygons.

You might also be able to see all the holes around the circle - it's easier to see in this picture:

Yes, yellow is the new black. All that pink was making my eyes sore, yellow works just as well to show up problems I think.

Culling - Spot The Difference

2008-03-29T17:23:00.001Z

I've implemented frustum culling on my terrain, patches that are off-camera won't be rendered. I followed Chad Vernon's tutorial here, it was a very good straightforward tutorial (with source in C#). I'd like to have tutorials like his but I think people (like Chad) can explain things a lot better than I can so I'll leave it to the pros. Anyways, with frustum culling if you were on the terrain looking one direction, everything behind you won't be seen so don't render it. Here are the before and after images, see if you can spot the difference:

Yeah... the difficult part of showing something that's off-screen is that it's off-screen. In the next shot, I've exaggerated the frustum culling, and instead of culling I'm just rendering the patches in wire frame. So you can see the centre patch is shown and the neighbouring ones are culled.

It's a huge improvement on the number of polys rendered (and this of course increases the FPS) but I'm sure I'll have to do a few more tricks when I get around to rendering planets. Like for example, fill each solar system with a dense dense fog so you can only see 5 metres in front of you.

Popping

2008-03-29T10:18:00.001Z

I tried geo-morphing on the terrain, but it didn't seem to have any effect really, popping was still quite visible - so instead I changed the way I calculate the LOD to be non-linear. All this means that instead of changing LOD at 100, 200, 300, 400 etc., it changes in relation to how far away it is like 200, 400, 800, 1600. Popping isn't noticeable at all now.

The video is in 4 parts, with a little of the old in-out:

Linear LOD
Non-linear LOD
Linear LOD line rendering
Non-linear line rendering

The change is most visible in the last section, you can see that the LOD only changes when the vertices are about a pixel apart. The downside is that it's fairly poly intensive if you're rendering a large patch of terrain - so I might have to make a few compromises when it comes to doing planets.

It's my first time uploading a video so hopefully the above shows my terrain stuff and not some whiney emo.

Update: video quality was awful so now I know how to do it, I’ve uploaded take 2.

Cracks Painted Over

2008-03-24T22:14:00.001Z

I had to redo the algorithm for creating the index buffer for a patch again but finally the patches don't show cracks anymore. If a neighbouring patch is at a lower level of detail, I draw the edge that borders that patch a little coarser by omitting a vertex. In the image below left, the red circle indicates where a crack occurs. By omitting the vertex from the higher detailed patch, the poly on the right of the left patch and the poly on the left of the right patch - share an edge. The other image shows where this happens on my engine.

The results aren't very stunning, just the terrain with no cracks:

One bad side effect of this is that recreating the index buffer each time is a big performance hit. I might pre-calculate all the kinds of index buffers (one set for each level of detail - a set has 16 versions for every configuration that deals with every combination of neighbouring level of details) and share them between the patches. I'm not that bothered about performance at the moment though, I'll just rely on whenever quantum computing comes around to speed my engine up.

When going towards or away from the terrain, it pops a lot as it changes from one level of detail to the next - so I might look into geomorphing to minimise popping. I think I could come up with a better way of calculating the level of detail too (non-linearly). Or... go back to brute force terrain and wait for quantum computing...

CLOD - Builder's Crack

2008-03-23T16:50:00.001Z

Why put off something off until tomorrow when you can do it the day after that? I finally got around to doing Continuous Level Of Detail (CLOD), it was really frustrating trying to debug and I had a few restarts on the algorithm because it got so messed up (very handy rolling back with tortoiseSVN, SVN (best source control programs I've used) and unfuddle's free service). Check out some of the mistakes along the way:

Here's what it looked like when I finally got it working. I've exaggerated when the level of detail changes just so the difference in polygons is obvious. Patches that are close to the camera (bottom right) are more detailed (showing more polygons) than patches farther from the camera (top left)... Shouldn't it be called Non-continuous Level Of Detail?

So why did I choose a pink background? Well if you've been following fashion, you'll know that pink is the new black - this really held me up as I had to write a custom Color class which would swap colours around dependent on current trends. A handy side effect though is that it shows up the cracks that can occur using CLOD like the one on the top right:

The cracks occur when 2 patches of different detail levels are beside each other, the more detailed patch has a vertex on the patch border where the less detailed patch doesn't. I'll have to increase the level of detail on any edge of a patch that borders a higher detail neighbour in order to *patch* up the cracks - get it?? See what I did there???

Seasons

2008-03-20T14:48:00.001Z

I'm still avoiding CLOD, but the distraction I came up with was kinda cool so I thought I'd share. It occurred to me that I could create a neat seasonal effect if I play with the terrain texturing. Terrain texturing is a single texture made from a blend of base textures, the blend depends on the height of the terrain at a certain point and the height range for each base texture. Well, if we were to multiply each height by a factor when we're working out what texture to use so that the heights appeared to be bigger than usual, then we'd get a lot more snowy texture on the terrain (and vice versa for grass). I had to include a couple of extreme cases in the existing code (like if the height is higher than the max range of the snow texture, just make it snow) but it was simple to add the seasonal factor. Here's what the effect produced:

It's nice to watch the snow creep in over time, but it really slows the frame rate right down (to about 2 fps). I worked with Bitmaps in C# before and it seems to be about 100 times faster to lock the pixels and access them directly rather than use GetPixel and SetPixel. I'm also sure there are fancy hardware things you could do too.

If I keep up these distractions, the real-world season is likely to change before I get on with CLOD. Well, except here, it seems to be cold and rainy season indefinitely.

Light Mapping

2008-03-20T14:13:00.001Z

Ok, so I'm putting CLOD on hold for a bit, I'm not looking forward to be honest given I've pretty much forgotten everything to do with geometry. So instead I implemented light mapping. Light mapping is just darkening pixels on the terrain so it looks like a light is casting shadows. The simplest and most visually attractive technique in my opinion is slope lighting. Following a line of pixels in a direction from where the light source should be (in this case I chose south (which is x = 0, z = -1)), make the current pixel darker than the previous by a factor of how much higher the previous height is. If the previous pixel is lower than the current pixel, don't darken it.

shade = 1.0f - ((heightMap[x - xLightDir, z - zLightDir] - heightMap[x, z]) / softness);

As always you can play about with parameters to make the light come from a different direction, or to create a more severe (darker) shadow. Here's how the effect looks in practice on my engine (before and after):

It's not proper shadowing but I like the effect. I think it could be extended to stretch the shadows - for example a low sun would create long shadows, so you probably could choose a direction as above with a shadow range of 10 (something like x = 0, z = -10). However sections of the edges would look a bit out of place because they don't have 10 pixels before them.

For a realistic Irish effect you don't need shadows at all because there's no direct light source, just make sure to turn the colour of your ambient light to dark grey.

Adding Detail Map - Looks Fuzzy

2008-03-20T08:34:00.001Z

To counteract the blurriness of the terrain, I'll apply a detail map. A detail map is just a plain texture with some details like cracks and bumps. The detail map will be applied 32 times over the terrain, here's what the result looks like (before and after):

It looks a bit more realistic, but it seems to be really noisy and fuzzy when I fly towards it (that is when I fly using the camera controls, not in real life - I didn't take any crystal meth or anything). Here's what it looks like from far away (before and after):

It's easiest to see the fuzzy noise on the black pit to the right. It's hard to tell from the images but it's worst when you move toward the terrain; pixels on the detail map seem to move about and make it look something like there's interference on a TV channel. When I release my game I'll just include a superficial aerial with it - problem solved.

A lot of these sort of problems can be fixed with manipulating some of the parameters (like how many times the detail map is repeated over the terrain). There are already tons of parameters I've arbitrarily picked and I just run the project to see what it looks like, then change them again - which takes up a bit of time. I'm thinking of writing some sort of Reflection-based ParameterManager class so I can easily cycle through all available parameters at run-time and save/load sets. I'll put that on the back-burner though because my terrain performs horribly at the moment so I'll do some optimisation with Continuous Level Of Detail (CLOD) next time.

Terrain Texturing

2008-03-20T00:18:00.001Z

After I put in the camera rotation code from my last post, the teeth-like artifacts disappeared. I find graphical programs a real bitch to debug so I'm pretty happy to totally block from memory that they ever existed... what was I talking about? Oh yeah, texturing the terrain.

Instead of colouring the vertex based on how high it is, we'll texture it. With height-colouring it was simple to go from black to white, it's just as easy going from one texture to another - the technique is pretty much the same but the start and end colours are retrieved from a specific point on each texture. Blending is done as before, if the point is nearer the higher texture, the point will be closer in colour to the pixel from the higher texture and vice versa for the lower texture. Here's the result of applying 4 textures (earth, grass, rock and snow) to my terrain:

It looks more realistic, but a little bit blurry. The pit on the right looks black instead of earthy because I started blending off with a black colour as a base, I think it looks ok.

Proper Camera Rotation

2008-03-19T22:55:00.001Z

In order to have a better look at the weird artefacts on my terrain, I tried to add a mouse & keyboard controlled camera. Matrix.RotationYawPitchRoll doesn't seem to work for me - if I rotate my camera 90 degrees about the Y axis (yaw) looking to my left then try to rotate about the Z axis (roll) so the view spins clockwise it actually rotates around the X axis (pitch) and ends up looking up and down.

(I suppose I should've said on the first post that I'm writing the game in Managed DirectX with C#).

Anyways, I had this problem before when I was good at geometry so I was sure I could do it again. Unfortunately years of boozing have destroyed any remnants of my secondary school geometry and the results of my sin/cos calculations were that I should go get my old computer out of the shed and get the old code. Here it is if anyone has the same problem:

private void Rotate(float yaw, float pitch, float roll)
{
    // We'll create 3 matrices for the combined rotation
    Matrix yawMatrix = new Matrix ();
    Matrix pitchMatrix = new Matrix ();
    Matrix rollMatrix = new Matrix ();

    _localMatrix.Translate(_position);

    // Reset it's orientation vectors to make sure they're all
    // sqare against each other and unit length
    _look.Normalize();
    _right = Vector3.Cross(_up, _look);
    _right.Normalize();
    _up = Vector3.Cross(_look, _right);
    _up.Normalize();

    // The pitch rotation will be done about the x axis (right)
    pitchMatrix.RotateAxis(_right, pitch);
    // The yaw rotation will be done about the y axis (up)
    yawMatrix.RotateAxis(_up, yaw);
    // The roll rotation will be done about the z axis (look)
    rollMatrix.RotateAxis(_look, roll);

    // Rotate the local axis about these matrices so we can tell
    // how the object is now oriented after rotation

    // Rotate the _look and _right about the yaw rotation
    _look.TransformCoordinate(yawMatrix);
    _right.TransformCoordinate(yawMatrix);

    // Rotate the _up and _right about the roll rotation
    _up.TransformCoordinate(rollMatrix);
    _right.TransformCoordinate(rollMatrix);

    // Rotate the _look and _up about the pitch rotation
    _look.TransformCoordinate(pitchMatrix);
    _up.TransformCoordinate(pitchMatrix);

    // Store this in the local matrix for translation when rendering
    _localMatrix.M11 = _right.X;
    _localMatrix.M12 = _right.Y;
    _localMatrix.M13 = _right.Z;

    _localMatrix.M21 = _up.X;
    _localMatrix.M22 = _up.Y;
    _localMatrix.M23 = _up.Z;

    _localMatrix.M31 = _look.X;
    _localMatrix.M32 = _look.Y;
    _localMatrix.M33 = _look.Z;
}

First post!!!!!

2008-03-19T20:38:00.000Z

Hello! I'm writing this blog for purely selfish reasons - I've wanted to program games since I was a kid but have only once finished a project: a Nibbles clone with death sequences in DOS (I'll put up the exe if anyone's interested). A friend suggested that a blog can help so hopefully some sort of guilt for updating this blog will override my incredible laziness. He's got a game engine in development too and has made a lot of progress, it looks fantastic and you can see it on his blog - feel free to make me feel better and undermine him and his engine :)

So what'll my game be then? I don't know yet, but my ambitions are high - basically I'd like a procedurally created universe with super-intelligent AI with a combined RPG/FPS/Flight/Driving/Adventure gameplay that's fecking awesome. People will become addicted to my game and it will create world peace. Oh and I'll get the ride off of some hot groupies. But I've got to start somewhere, so here we go - a terrain (bit of land) generated with fault formation (raise sections of the land randomly) and lit with height lighting (the higher the whiter). These are real terrain basics so I won't go into detail (unless someone needs it).

Looks ok for a first go, but there are these weird artefacts, kinda like teeth, no idea what they are...
Until next time!