Giving shape to the world

I finally have an interesting playground to experiment in, so it's about time I focused on what I wanted to do in the first place. The main drive behind this project was procedural content, making use of algorithms to populate the world with variety instead of a fixed number of precomputed models. I've already been doing that, in fact. The distribution of spheres in the demo, for example, and their size, is all deterministically decided by the program at run time.

All I do is decide how many spheres I want, what the range of sizes should be, and the volume of space to use. The program then fills the space. Because the starting conditions are always the same, the program always builds the same scene. I could easily create a different distribution by changing the seed or any of the parameters. I want to go further, though. Right now, all these spheres are kind of boring. And not very asteroid like. To change this, I'll deform the spheres to create more interesting shapes.

My initial plan is to assign each sphere a height map. I'll then use the height map to raise or lower away from the center of the sphere each vertex. One difficulty I expect is how to adjust the normals as the terrain is reshaped, but I'll figure something out. On the height map end, I'll use the simplex noise algorithms I've talked about before to give each asteroid a distinct look. By seeding each asteroid with a distinct value, I ensure they'll all be unique.

A sample of simplex noise

For the height map, I only need it to match one pixel to a vertex. This way I can send the value to the vertex shader as an attribute. I already created the spheres using a gridlike pattern, so I can use the uv coordinates of each pixel for this purpose. This does mean that there will be more detail near the poles that along the equator, but because my source is going to be a 3d density function it should not result in any obvious distortions. The output will go into a Vertex Buffer Object, which will be fed to the video card and called when drawing.

Normally, height maps add a height to points on a grid, which is level with either the XZ or XY planes, meaning Z or Y is treated as height, and that value is replaced with the value of the height map. However, I have a sphere. On a sphere, height is defined as the distance from the center. To apply the height map to a sphere, I have to work a bit more.

The values I have will fall between -1 and 1. If I do straight multiplication of the surface point by the value, I'd have a mess. Instead, what I do is decide what I want the range of heights to be. If I want the highest points to jut out three times the radius of the sphere, for example, and the deepest valleys to reach half way to the center of the sphere, that gives me a range of (3 - 0.5 ) = 2.5 radius. The half point (where the height map is 0) would be 1.25 radius, so I could get the position of every point as ( (1+height)*1.25 + 0.5) * position.

The other complex bit is recalculating the normals. By changing the shape of the sphere, the surface normals all change as well and that impacts the light on each point. If I don't get them right, the lighting will look decidedly odd.

That's getting ahead of me a bit. First I need to be sure I can produce the information and get it into the shader. I had to add an extra attribute to the Model class to do it, but after a few short tweaks I got it up and running. What I'm doing right now is using the height value of each point as a color value, with -1 being black and 1 being white. So higher areas will look brighter.

Looks nicer than blue with red and green dots.

It's working, and I'm pretty happy about that. I'm now struggling with an odd problem; when running the project from a pendrive it works, but copying the project to the hard drive and running it there doesn't. Fixing that is probably going to give me enough for another post itself.

Looking good. Looking real good.

Well, that was quite a bit of wait between updates, but lighting is done. Sort of.

It's helpful for me to see what I need to do to flesh the shaders out. Later on I'll need to add textures, and shadows, and multiple sources of light. The nice thing about space shooters, though, is that you generally only have one big source of light to worry about. Certainly, there is plenty of room for lighting effects all over, but what's going to be illuminating the planets, asteroids and ships for the most part is the big star in the middle.

A concern I'm having is that as I add features, the code is getting a more unwieldy. For the most part I've avoided a serious case of spaghetification, but I really should spend some time consolidating certain pieces of code. Before I do that, however, I want to have a better feel for what works and what doesn't in my design.

I've already identified some decisions that weren't the best. For example, my use of inheritance would in many cases be better suited to templates. I wanted to avoid templates, because they are somewhat arcane in their workings, but already my use of the standard and boost libraries has me working with them. I feel more confident now about using them, and it would simplify some things.

This means I'm going to have to do a bit of a rewrite of several big chunks. Rewrites aren't fun, but on the positive side I'm not going to be starting from zero. That seems like a good opportunity to reassess and redesign, so I want to get a bit more experience in before I undertake that particular task. It's a fragile balance I have to manage between having enough features in there that I know how to design it better and having so much that redesigning it is too daunting to do.

It doesn't help that work has picked up and I'm generally too burned out to focus on this when I get home. That's also part of why I've let the update schedule slip, for which I apologize.

In the interest of making things easier for everyone, I've switched back from 7z to zip files to share the program. 7z was a necessity when I was sharing the program through gmail. Mail programs don't like zipped executable files, and having people rename a file from .jpg to .exe to get around it was more trouble than convincing them to use 7zip. But with the files now hosted in Google Docs, I can go use zip files again.

As always, the folder is Framework Releases, and the project itself is Framework-0.0.8.

Let there be light!

Now that I have a little playground with some basic physics, controls and the like, we can worry a little more about the downright dreadful appearance of the place. Everything looks flat, because I'm slapping solid colors with no shading at all.

What a solid red sphere would look like in the program

Shading helps give a sense of depth, and even the most basic techniques would result in a much improved look and feel. Naturally then, we need to start thinking about lighting. What I'll be implementing for the following stretch is something called the ADS lighting model, which stands for Ambient, Diffuse and Specular.

According to this model, the color that we see an object have is the result of adding three contributions from the light that's lighting it up. These are the ambient light, the diffuse light and the specular light.

Ambient light is the result of light that has bounced several times between objects, with the result that there is no identifiable source. It results in a general brightening of an object, essentially a flat color boost to everything. If we only had ambient light, we'd get a picture much like what I already have.

Ambient light illuminating a red sphere

 Diffuse light is what produces the natural shading we are used to. This light comes from a source, and the angle between the source and the surface normal determines how brightly lit it is. A surface placed perpendicular to a light source will be illuminated more brightly than one placed at an angle, and as a result will have a brighter color. Surfaces parallel or looking away from the light source, on the other hand, are not illuminated at all.

Diffuse light. Paint doesn't have a gradient tool. Use your imagination.

Finally, specular light describes how shiny a surface is, creating the highlights caused by the light source. While Ambient and Difuse lighting depend solely on the position of the light source, Specular light also depends on the position of the observer.

Specular lighting is highly focused. As the observer moves, the apparent position of the highlight can also move.

Adding all these together would give the result we want. In order to add it I don't really have to mess much with the program code, which is fortunate. The heavy lifting is going to be done in the shader program. The actual program is just going to have to provide the necessary information.

Next week I should have a first implementation of it running.

It's full of stars!

I've gotten a few new features into the framework, such as a first implementation on 'shooting', but that's not what I want to talk about today.

So far, I've focused solely on functional details. Making models, making sure the models are displayed, movement, views and such. The result is... well, it's functional. Of course I want to have something good before I start polishing. A polished turd is still a turd, so I have to turn it into something else first.

The traditional way of making a background is making use of a skybox. This is basically a cube you draw around the scene. With the aid of something called cubemapping, you can slap the sky on the inside and the textures used fool the eye into thinking it's looking at a dome, rather than a cube. No seams or anything, if done correctly.

Of course, I didn't have the textures to make it look good handy.while there are plenty of images of space around, there's very few of a look at the complete sky, and those that are have fish eye effects. I could have slapped a few images, merged them together or something and called it a day, but I wanted something special.

So, I started a little side project. The idea being, I'd create the background out of a real galaxy I made up on the spot. This would mean create all the stars, jump into an appropriate position inside the galaxy and take pictures of what is visible in each direction. That way I would have the textures I needed for the cube map. I could scale the definition as much as I want, or move to a different spot and have the constelations in the background actually shift properly.

How to do it, though? A galaxy like our milky way has on the order of a hundred billion stars. Can't really draw them one at a time. Instead, my plan is to split the space the galaxy occupies into as many blocks as I can manage, and give it shape with the use of two functions.

One of the functions will give the galaxy a shape. The second will add some higher frequency noise to make it look more interesting.

I will represent the blocks with points, and once I have it all working try to improve the appearance. I really want the GPU to do the heavy lifting here. I can make a shader program that checks the position of each point and assigns it a value for each function, then multiplies them together. But if I tell the GPU to draw a million points one at a time, the overhead on the calls will slow things to a crawl. So what I do instead is make use of instanced drawing.

Instanced drawing means I tell the gpu to draw a singlemodel (in my case, as ingle point) as many times as I want. It's helpful for drawing many identical objects. The result, after setting the color to solid red, is not very impressive:

4096 points, all drawn on top of each other.

Of course, drawing several identical points means they get drawn in the same spot. In order to add variation, the gpu gives me an extra variable, an instance id, which I can manipulate for some interesting effects.

For my first test, I'm sending 0x1000 points to the gpu. That's 4096 in decimal, but you'll see why I work in hex in a bit. This means the instance ids range from 0x0 to 0xFFF (4095). What I can do is treat each of the hex digits as a coordinate in one of the axis, x, y and z, and move the point by that amount. So for example, the point 0x123 maps to position (1, 2, 3). I use bit masks and some bitwise arithmetic to work out the positions, which is why I do it this way. Computers, as you know, like binary and powers of 2 better than decimal.

Adding the instance id into the mix then, the result is a cube made of red dots. Not very impressinve right now, but it's a start.

I'm moving the points a bit, as well, so they appear centered.

I can play around with color too. For example, if I treat x as Red, y as Green and z as Blue, I get a colorful cube:

Ok, so back to the galaxy. First, I'll give it a proper shape. A cube is hardly the proper shape, so let's ignore points outside of a central sphere. For that, I'll give points further than 1 unit from the center a color of 0.1. There may be a few stragglers around the galaxy, but they're few and far between.

Much better. Now, galaxies tend to be shaped as disks, more than spheres, so we want to squash the sphere as well. What we want is to decrease the intensity with regards to the height from the plane. I'll use y to measure height from the plane, and to avoid the break being so obvious I'll also diminish the intensity along the diskthe farther you are from the center. The result:

Not so bad. Still need to add more features, though. For example, our galaxy has spiral arms. These will require a bit more thinking.

I didn't get quite as far as I meant to, mostly due to Deus Ex. Still, I don't want to leave you without an update so check out Framework-0.0.6r. You can do everything you could do before, and now shoot too! The space key now fires instead of accelerating, you accelerate with Left Shift. Fun* game to play: see how much you can shoot before it starts slowing down the game. TODO: delete the bullets when they're no longer relevant.

I've also made the folder with all the releases public, so anyone can look up the history without digging through the archives. Framework releases.

* It's fun for me, but then I had fun with the first release too.

Back to square one again!

Well, I spent a lot of time scratching my head over a problem that turned out to be a simple dumb issue.

As I detailed in my last post, my models consists of pointers to video memory where the actual information is stored. In a fit of genius, I realized that if I deleted the model but forgot to clean up the information, I'd be leaking video memory. That would be bad. So I made sure that, before a model is destroyed, the information is cleaned up.

This seemed like a clever solution, and the subtle problem didn't become obvious to me until I spent two weeks wondering what I was doing wrong.

The problem happened with copying the model. I created the model in one part of the program, and copied it to the cache that would store it. This preserved the pointers, but when the original model was cleaned up it cleaned up the video memory. Just as I told it to. The copy was then left with pointers that were no longer valid. So when I then asked the program to render the model, it couldn't.

Thankfully the problem wasn't hard to solve. I instead created the model in a space in memory where I have more control of when it gets destroyed, and copy instead a pointer to it. This way the model object itself is never copied or destroyed and I can store it directly. In the process I learned a bit, so I call it a success.

I also had to add a shader to the program, which I should have probably worked into the framework before I did the work on the models. Thankfully I had a ready made function that handles all the aspects of reading the shader from file, loading it to video memory, compiling, linking and binding attributes.

So now, after a couple of months, I'm able to render a red triangle to the screen. Which is about what I was at before the rewrite. So, yay?

Well, to be honest I have a lot more than before. I can read input, and configure it (just need to add more input to be read). My storage is a lot more organized and extensible. I need to do some adjustments to my design to account for lessons learned, but I'm very happy with what I have.

Next up, I'll be adding some actual interactivity. Well, first deal with matrices, then interactivity.