I have been playing around with distance field rendering, inspired by some of Iñigo Quílez’s work. Along the way I needed to define analytic distance functions for a number of fairly esoteric geometric primitives, among them the logarithmic spiral:
I just posted a quick youtube video to demonstrate the current state of the planet renderer. This is early development stuff, and the eye candy is minimal, but it should give you some idea of the scope.
I will follow up with a more technical blog post in the next few days, explaining all that is going on behind the scenes, and can’t be seen in a video.
Part of the rationale behind this video is to stremline the whole video capture and posting process. Unfortunately, it hasn’t been entirely straightforward so far. I went through a number of video capture tools before settling on FRAPS, which works well enough (though I would have prefered a free tool).
I also have had a terrible time converting the video for youtube – ATI’s Avivo video converter is blazingly fast, but apparently produces an incompatibe audio codec in any of the high-quality settings. I was forced to fall back to the CPU-based Auto Gordian Knot, which both does a worse job, is very slow on my little Athalon 64 x2.
I am now experimenting with ffmpeg, but the command line options are confusing to say the least. If anyone has any clues/tips/tricks for getting FRAPS encoded video (and audio) into a suitable format for youtube HD, please let me know.
The semester is over at last, and my grades should be in by Monday. It has been a tiring semester, but not a bad one, with interesting courses in database implementation and parallel architectures, not to mention philosophy.
With the end of the semester comes a little more free time, and I have spent a chunk of it recreating my old procedural planet demo in Python/Pyglet.
The first big plus is that whereas my previous implementation was over 5,000 lines of C++ code, the python version is under 1,000 loc, plus a few hundred lines of tightly optimised C for the tile generation back end.
The other plus is that this version actually works. I finally found the time to fully implement the crack fixing algorithm, and the results are very good (although there are still a couple of unresolved edge cases).
I also implemented normal map generation in GLSL, to offload the computation to the GPU. This more than doubles the performance of tile generation, to the point where several tiles can be subdivided or combined each frame.
From a technical standpoint, the planet starts as a cube, and each face is subdivided to form a quad tree. For each tile at the deepest level of the quad tree, a small heightmap is generated using 32 octaves of 3-dimensional simplex noise. This heightmap is used to generate the vertices for the tile, and passed as a texture to the GPU in order to generate the normal map.
Because applying tangent-space normal maps to a sphere is an absolute nightmare, I take the unusual approach of generating object-space normal maps. These are considerably more expensive to generate, but avoid the tangent-space mismatch at cube edges, and look fairly decent in practice.
Interestingly, this version allows one to fly right down to the planet surface, and maintains interactive framerates even on my Intel integrated X3100 (complete with the awful Mac drivers). By the time I add atmosphere shaders and detail textures, I expect that I will have to switch over to my desktop, but for now, I am very happy with the performance.
Of course, there are still several challenges to overcome, in particular the issue of depth buffer precision. The planet you see above does not suffer from a lack of depth buffer precision, but it is only 1/10 scale of the Earth, and ideally I would like to be able to render gas giants on the order of Jupiter as well. This requires some clever on-the-fly adjustment of the camera frustum, and I don’t quite have a handle on the best way to accomplish it.
If you haven’t already, go watch Eskil Steenberg’s GDC videos of his game Love, and the tools he uses to build it. The game itself is fresh and beautiful, but as an programmer, it is his tools that have blown me away.
The last game development tool to really catch my fancy was Carmack’s co-operative world and megatexture editor for ID Tech 5, which was demoed back in 2007, but I can honestly say that it pales by comparison to Eskil’s tools.
And the best part? All of Eskil’s tools are open-source.
Spending a little time on the visualisation side of things at the moment. At right you can see the result of rendering the previous images as a height map. A simple colour map is applied based on elevation, and the terrain is lit.
The terrain is fairly low resolution, only 128×128 vertices, while the height map is 1024×1024 pixels. To increase the quality of the lighting, a normal map is generated from the height map, also at 1024×1024 pixels. This yields 8:1 vertex to texel ratio, giving very decent performance while still rendering at a high quality.
The terrain is actually split into 4 equal sized patches, 64×64 vertices each, in order to aid culling. At some point I will improve this system into an adaptive quadtree, which should provide far better performance.
I am rendering this all on an Intel integrated X3100 graphics processor, and so far I have been very impressed with the performance. Despite running commercial games extremely badly, this card seems to take no performance hit when using shaders instead of fixed function rendering, and in fact, the current shader-based normal mapping is faster than the previous fixed-function lighting.
After using a mixture of voronoi and simplex noise to generate a height map, I realised that it doesn’t look very good – in particular the noise generation creates hard edges and jagged formations everywhere.
The solution to this is, or course, erosion. At right you can see the results of applying a very simple approximation of thermal erosion to generated height map.
This implementation is an image space post process. For each pixel, a fixed height is subtracted, and the algorithm then travels downhill, until it either reaches a maximum distance, or finds no adjacent pixel lower than the current pixel, at which point it deposits (adds) the same fixed height.
The images at right were generated by applying ten repetitions of this filter, for various values of the distance parameter. As you can see, larger distances tend to preserve detail on slopes, and result in large flat areas. Smaller values smooth out slopes as well, but don’t greatly affect the overall shape of the terrain.
This looks pretty good for a first stab at erosion, and is very fast, but I expect that a full implementation of thermal and hydraulic erosion will look substantially better.
Yesterday I set about generating 3D noise, in particular, texture maps for 3D planets. It sounds like a relatively straightforward extension of 2D noise, but unfortunately it didn’t turn out that way.
First up, a SphereMapper generator. This handy little class takes a 2D coordinate, and transforms it into a 3D coordinate on the surface of a sphere, just basic Polar to Cartesian conversion. Of course, this generates 3D coordinates on a unit sphere, and while the front looked all right, the back looked absolutely terrible.
Turns out my Voronoi implementation didn’t work correctly with negative coordinates. This required only a simple fix, but unfortunately that fix required axing the optional tiling qualities I had added in the day before.
Then it also turned out that my Simplex implementation didn’t work with negative coordinates either. I haven’t figured out a fix for this yet, so in the meantime, I have implemented a version of Value Noise (as described by Hugo Elias). This is a fairly decent approximation of Perlin/Simplex noise, and does work with negative coordinates, but the quality is a little worse, and the high quality version is considerably more expensive than simplex noise.
I will have to fix the simplex noise at some point, but in the meantime, value noise is a good generator to have, and it makes for pretty decent looking planets.
I also notice that my OpenGL sphere class has a lot of texture distortion in the polar regions – far more than mould be expected. Apparently generating a sphere out of stacks and slices isn’t as straight forward as one would imagine…
Shortly after my last post, I realised my Voronoi basis had a problem: only the distance was taken into account for each cell. This has been corrected, with each cell now assigned a random base value, to which the distance is added.
At the same time, I noticed that the voronoi basis wasn’t much use on its own – polygons are an unusual shape in nature. This lead to the addition of a Turbulence module, which perturbs the input coordinates according to another generator.
Together these additions allow for some striking images, and adding these to a few octaves of simplex noise lends itself well to terrain – the bottom image makes for a quite convincing height map, though improvements can obviously still be made.
I am also testing the inclusion of an additional diamond-square generation technique, but it doesn’t play very well with other approaches. Unfortunately, diamond-square generation can only be used for square images with power-of-two dimensions, must be generated an entire image at a time (which pretty much precludes mixing it with other noise types), and only works with basis generators which have a gaussian distribution (i.e. not voronoi). Diamond-square does however offer very fast generation, so I think it will be included in the library – specifically for those applications that need extremely fast generation of fBm-like textures.
I recently moved all my graphics and games development over to Python, using Pyglet. Overall this has been a very good change, with a great increase in productivity, but unfortunately it has caused a few problems.
Previously, I had been using libnoise for all procedural generation, but it turns out that Pyglet is implemented using ctypes, while the only available python bindings for libnoise were generated using SWIG.
Naturally, the developer’s of ctypes and SWIG never made basic pointers compatible (nor with boost::python), so it turns out that there is no way to load a libnoise generated image into a Pyglet/OpenGL texture.
I haven’t been entirely happy with libnoise for sometime (primarily because of difficulties tiling voronoi noise), so this gives me the perfect excuse to dive in and implement my own noise library.
The library is developed in C++ (for efficiency), and has an external interface written in C, to easily interface with Python (using ctypes). At this stage the entire library is contained in a single source file, and weighs in at just under 500 lines of code.
The code itself is flexible and extensible: You create one or more Generators (which can each combine other Generators), and a Renderer, and feed both to a Generate function.
The image above was generated by a python script, and shows off all the current features of the library. Two generators are provided (simplex noise and voronoi), which can be combined into octaves (fractal-brownian motion), and blended together (weighted addition). The image can then be rendered in greyscale (such as for a heightmap), or rendered with a colour palette (as in the lower left image), and in either unsigned byte or float precision.
I hope to add several generators, in particular more blending functions, in the coming weeks. After that, with a little code cleanup, I think an open-source google code release is likely.