Hi, I'm trying to develop a game in Managed DirectX with procedural textures, procedural cities and eventually full procedural planets but I'm having trouble enough as it is with doing a procedural triangle. Here's where I detail the (slow) development of the (really slow running) game.
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.
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 inearlierposts, 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.
...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:
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.
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.
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.
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...
