Friday, 22 August 2014

Shaded Island

After writing the last article I have continued to perfect my island generator. I reimplemented the Gaussian blur to use separated kernels, which resulted in a huge speedup in the generation step, but rendering was still slow when the terrain resolution was big, so I wanted to improve on it.

I spent a long time on looking for the best rendering solution. First I checked out Ogre, which seemed to be a decent rendering engine. Unfortunately the configuration is very complicated and it's hard to find reliable, current documentation. I couldn't get anything get rendered on Linux with OpenGL after several hours of trying, so in the end I just gave up sadly.

Next I tried the bgfx rendering library, which also looked nice and much simpler than Ogre. This time my problem was that I could not get it to cooperate with SFML, and I did not intend to ditch that library.

The next choice was OGLplus, a C++ wrapper around OpenGL, looking good at first glance, but a bit complicated and bloated when I tried to use it. So after looking at options for weeks I kinda gave up. I considered using the vertex buffer and shader facilities provided by OpenGL, but was too lazy for it.

Then one day I accidentally discovered that the 2nd version of SFML, in contrast with the 1st version, has support for shaders. It's easy to load and use them, and the shader language is GLSL. It also supports vertex arrays, but unfortunately only with 2D coordinates for position, while I needed 3D. Luckily the SFML sources are easily readable, so I could figure out what's going on behind the scenes and learn how to use vertex arrays in OpenGL.

Switching to vertex arrays had a huge speed improvement, which is what I expected, since now there are no calls to glTexCoord2f and glVertex3f for every single vertex, only one call per frame to glVertexPointer, glNormalPointer, glTexCoordPointer and then glDrawArrays.

Using shaders enabled me to change from flat shading to Phong shading. It required calculating the vertex normals (which get interpolated in the shader for every pixel), not just the face normals for the triangles. The result is pretty nice:

Flat shading

Phong shading

Playing with shaders is fun, it opens up a lot of possibilities, for example I can modulate the colour of the terrain based on the height value (= z coordinate), e.g. set the lower parts to sandy colour and the higher parts to grassy green. It still needs tweaking, but the basics are done.

Another feature I have is the day night cycle. It was already present in the old renderer, but was very slow. For every frame the colour of every triangle was recalculated, based on the dot product between the sunlight direction and the triangle normal. In the new renderer the light direction is passed in to the shaders, and all the calculation is done on the GPU instead of the CPU.

Next I plan to implement vegetation generation to add trees, bushes, etc., and other features needed to make it into a game.

Monday, 7 April 2014

Journey to the Perfect Island

I took a two-day break from work to have a long weekend and some rest, and rest included working on a small project: island generation. My goals were simple, I wanted to make a procedural terrain generator that would create nice looking islands, and a triangle based isometric renderer in OpenGL.
First I calculated on paper the view transformation matrix to render a 2d heightmap as triangles, and wrote a wireframe renderer to check my calculations.

The view transformation was alright, so I added a noise texture and green colour to the triangles. First I also tried adding Gouraud shading, but it was ugly and the exact geometry couldn't be seen, so I switched to flat shading.

So rendering was sufficient, it was time to start generating the terrain. My plan was to generate a fractal heightmap, and then multiply the height values with a scaled 2d Gaussian function to have some land in the middle and quickly reach zero, that is, sea, as getting further away from the centre. After checking out a few methods (e.g. perlin noise, simplex noise, midpoint displacement) I chose the diamond-square method to generate the terrain, because it seemed to result in nice looking terrain quite fast.

It was not hard to implement it, and I was satisfied with the result. I also changed the viewing transformation from the skewed triangles to a more traditional isometric view. As the next step I have added the multiplication step with the 2d Gaussian bell curve, and also created the sea (and I saw that it was good) which is just a semi-transparent blueish plane slightly above the zero height level.

Looks good, right? Nope. It's the most boring island ever, a single pointy mount in the middle, an almost perfect circle shoreline, and most of the features from the fractal terrain are smoothed out.  I refined my expectations: interesting mountains, nice beaches and complex shoreline. As a fix I tried to add the Gaussian function to the noise heightmap instead of multiplying with it.

Now it's not terribly awful, just relatively bad. The features of the original fractal terrain are somewhat kept, but it is still just a single mount and a circular shore, no nice flat beach... far from perfect. I went back to reading articles and in the end found this one, which described a method similar to mine, but used another function instead of the Gaussian. It looked good, so I gave it a try.

Somewhat better, but still boring. I wanted something like this, with the constraint that it should be an island. The problem with that method was that it was based on Diffusion-limited aggregation which seems to be a looong process to me, and also the result is not always an island. After a good night of sleep I came up with a new and simple method: I would generate a random walk with Brownian motion to define the skeleton of the mountains, and apply Gaussian blur (you can't escape Gauss) a few times with different radii to smooth it into hills and shores. It took a while to code the Brownian noise generator and the Gaussian blur, but it was worth it. When I finally saw the first generated island I immediately knew that this was what I wanted.

This method seems to satisfy all my criteria: complex mountain structures, wide flat beaches, interesting shoreline. The shape of the island is mostly defined by the result of the Brownian noise, and the size is somewhat related to the steps used to generate the noise, though it can be stuck in a small place and result in a small island even with many steps. The implementation needs some tweaking (resample the terrain for higher resolution, rewrite the Gaussian blur to use a separated kernel instead of the O(N^2) slow naive 2d convolution, and fine tune the number of steps for the random walk and the radii of the blurs), but otherwise I'm very satisfied with the method. Now I can play with decorating the island, and soon I will have my own island with palm trees and beaches.