Wednesday, January 27, 2010

Rendering random nebulae (part 3)

My brother, who is a hobbyist programmer himself, had the constructive comment that my nebulae were overall too dark. Real nebula have dark and bright areas, he said. And he is right, I guess. So I decided to give it a go and tweak the nebula a bit more.

Shaping up nicely
One problem was that when the shape of the nebula was determined, the cloud was pretty much flattened out. This happens because the heights of the bubbles that define the shape are all added up and clamped to 255, which is the maximum alpha value. A consequence of this is, that the nice height map that was created using a plasma renderer, is all flattened. I changed the shaping algorithm so that the inner height map in the cloud is mostly preserved (by taking averages), while still fading at the edges. This gives the cloud a fluffy, three dimensional look.

Previously, I would render a plasma, blend in colors, and finally determine the shape of the nebula. This time, each layer has its own shape. The result is that the colors are more coherent and staying together in their own little "sub cloud".

A Blurred Vision
It seemed like a good idea to blur the image to make it a vague cloud. This turned out not so well; blurring the image takes all detail out of the image. (Sounds kinda obvious, doesn't it?)

I also did some trickery with the alpha channel previously, to fade the entire image. This was totally unnecessary, as you can set the alpha factor with glColor4f() when the final texture is being drawn — so I took out this code, simplifying things. Since the background is the black void of space, this only controls the brightness of the nebula.

Blending In
Previously, I used alpha blending to blend in colors into the nebula. Alpha blending is real nice, but for rendering clouds it's better to use additive blending. The formula used is:
result = alpha * srcPixel + destPixel
In OpenGL, you would call this:
glBlendFunc(GL_SRC_ALPHA, GL_ONE);
What's cool about additive blending, is that blue and red make magenta, and blue and yellow make green. This may sound obvious, but note that this is not true for alpha blending.
I also use additive blending for making some extra bright stars. Experiments with additive blending in layers multiple times into the nebula were not exactly successful, as it looks funny when you make it super bright.

On one hand, I'm very happy with this result, while on another ... it shows the plasma algorithm. It's almost as if blobs of paint have been splatted onto the screen in a pseudo-random way. Ever heard of the Holi festival? I think it may be a good way to generate clouds too. But for now, I'll leave it at this.

Wednesday, January 20, 2010

Rendering random nebulae (part 2)

Last time, I talked about how to render a random nebula. As a final remark, I stated that the nebula had no shape; the plasma simply fills the entire image to its boundaries. The result is that you end up with a texture that is unusable; you can not have a nebula in the starry sky that is shaped perfectly like a square. So, we need to give it a random shape.

I tried fading out at the edges, and I tried a simple circular fade. It doesn't work. In the first case, you end up with a perfect square, that perfectly fades out to the edges. In the second case, you end up with a perfect circle. Both look like crap, we really need a random shape.

I decided the alpha channel of the nebula should be like a height map, with height zero around the edges. I tried out the diamond-square algorithm, which seems ideally suited for this (by the way, the plasma of the nebula is generated using a diamond-square algorithm), but it's hard to control around the edges. I thought about leveling the edges by 'pushing a pyramid' down over the image, but I'm sure it wouldn't look nice.

How do you generate random shapes? The answer: with a fractal. The word 'fractal' sounds very mathematical and difficult, but its not. See wikipedia for some info.
Algorithm used to generate a fractal shape:
  1. draw a circle;
  2. choose a random point on the edge of the circle;
  3. divide the radius by two;
  4. recurse; draw smaller circle at the newly chosen point.
Using a circle as a brush is not a bad choice, but if the edges have to fade, then the brush should be a radial gradient. I had a little trouble in drawing a radial gradient and did not find the right solution online, so I'll share my formula with you. It's actually easier than you might think:
float d = sqrt(dx * dx + dy * dy);
pixel = gradient - (int)(d / radius * gradient);

d is the distance of the pixel to the center of the circle.
gradient is the difference between the low end and the high end of the gradient; usually 255 for a full spectrum.
I work with overlapping circles in the alpha channel, so I use:
new_alpha = old_alpha + the gradient formula
When you do this, you will get a lot of high values in the alpha channel as they add up quickly, and that doesn't look good for nebulae. Therefore I chose a small value for the gradient variable, and then the results get quite nice.
Here are some small screenshots:

Sunday, January 17, 2010

Rendering random nebulae (part 1)

As I wrote in my previous post, I'm playing with a random 3D star field lately. To this star field, I like to add some nebulae to fill the black void of space. Previously, I worked with dozens of photos of existing nebulae from NASA. This time, I decided I want the scene to be entirely fictional, so there is no place for real nebulae.

Bring Out The Gimp
There is a way to draw nebulae by hand. Fire up the GIMP (or Photoshop, or alike), and select Filter : Render Clouds : Plasma. You now get a colorful mix onscreen which is probably not quite like what you had in mind. Now select Colors : Desaturate to make it look like a grayscaled image. Now select Colors : Colorize and drag the Hue slider to select the desired color for the nebula. To make the nebula look nicer than this, we probably have to mess with transparent layers, but this is the basic idea.

Programmatically speaking
A way to go would have been to use ImageMagick's library to do the described operations. Well, it seems that MagickWand (ImageMagick's C API), does not include a plasma renderer. The C++ counterpart, ImageMagick++, does, but being mostly a standard C programmer, I'm quite intimidated by its use of templates and references. And to be honest, I could not even get any decent looking nebula by trying to use ImageMagick from the command-line.

I got some neat plasma rendering code in standard C from the source code of the GIMP. Well, puting it like this makes it sound easier than it was, but I adapted it to work with an RGBA pixel buffer. I also wrote filters for desaturating (grayscaling), blurring, colorizing, alpha blending, and something that I dubbed "fadebuffer", but it's really "gray color to alpha" as it puts the gray value into the alpha channel.
All filters work an RGBA pixel buffer and all have the form:
void render_filter_name(unsigned char *pixels, int width, int height);
My Objective-C PixelBuffer class has a method named renderFilter that allows me to use any implemented filter on that image.
@implementation PixelBuffer

-(void)renderFilter:(void(*)(unsigned char *, int, int))filter_func {
filter_func(pixels, width, height);

This renderFilter method can be used as follows:
PixelBuffer *pixbuf = [[PixelBuffer alloc] initWithWidth:128 andHeight:128];

[pixbuf renderFilter:plasma];
[pixbuf renderFilter:blur];
[pixbuf renderFilter:grayscale];
[pixbuf renderFilter:fadebuffer];
colorize_color4f(r, g, b, a);
[pixbuf renderFilter:colorize];
Which is both readable and powerful code.

In pure Objective-C, you would have used a selector and maybe filter classes derived from PixelBuffer, but I like this way of doing things as it allows you to plug in quite standard code easily.

I want to share two formula's that I used. One is for computing the desaturation of a fully colored plasma cloud:
gray = (int)(0.3f * red + 0.59f * green + 0.11f * blue);
if (gray > 0xff)
gray = 0xff;
if (gray < 0)
gray = 0;
This works well if the image has lots of color. I experimented a bit with the plasma renderer and adapted it to generate only blue-tones, which results in this formula not working so well, as it takes only 11% of the blue component. So for monotone pictures, do not use this formula but simply take the active color component and put it into the new values for R, G, and B.
Note that this code is floating point and therefore relatively slow. It's easy to change this to integer only arithmetic. If you need more speed, use lookup tables (it costs only 3 x 256 bytes!). I didn't bother because this code is only used for preprocessing.

The second formula is for alpha bending. When you search the net you will find more than one formula to do this. Also, many focus on speed for doing realtime alpha blending in 16-bit pixel formats — this is all old stuff from the late 1990s when computers weren't as powerful.
Anyway, the formula I used is:
result = (alpha * (srcPixel - destPixel)) / 256 + destPixel
Do this for every R, G, B component. Note that in blending terminology you have a 'source pixel' and a 'dest pixel', but they mean to say that you combine the R, G, and B components of source image 1 with the R, G, and B components of source image 2, and that forms the result.
There are many optimizations possible here, like treating the RGBA bytes like one 32-bit integer and using bit masking to take out the components. This is faster because you do less fetching from memory.
Note: If you want to do really good and fast alpha blending, you should probably use OpenGL. The glBlendFunc() is excellent for all kinds of blending, but in this case it involves some hassle; you have to make some textures first and render them to a resulting texture. Since I'm just using this for preprocessing and I'm not interested in doing realtime blending, I decided to implement the blending 'by hand'.

The results
For making the nebula, the above procedure is repeated a few times for different colors, and these images are blended together. The pixel buffer is then turned into an OpenGL texture and textured onto a quad (made up from a triangle strip).

Although it's just a boring gas cloud, I'm quite happy with it. Not everything is well though; the plasma renders into a square and therefore, there is a square nebula in the sky. To make it perfect, the nebula must be given a random shape and fade away near the edges of the texturing square.

Saturday, January 2, 2010

(Simple) Flight Mechanics and quaternions

I've been playing with a 3D star field lately, and what it needs, of course, is a little space ship so that you can fly around. Sounds easy enough, but it's actually quite confusing.

The controls are confusing, but this is actually caused by the camera view. Our eyes and head can move independently from our bodies (well, at least for the most of us) so we can look around without having the feeling of explicitly having to turn. We are accustomed to our Earthly environment, where we think to know which way is up, down, and expect to come back down when we jump up.
Try this:
  1. stand in the center of the room and look straight ahead
  2. shuffle your feet to spin around, keep staring straight ahead
Now, do this:
  1. stand in the center of the room, and look straight up to the ceiling
  2. shuffle your to spin around again, keep staring straight up
Feeling dizzy yet? In the first experiment, you were yawing, going around the Y axis. In the second experiment, you made the exact same movement, but you were rolling, only because you were looking in another direction (down the Z axis).
Rolling happens when you see the horizon spinning in flight sims. Rolling usually isn't present in first person shooters because it's not a very natural movement for a person to make.

Now think about relativity. What if you were standing still, then the room would have moved around you in the opposite direction. People who have a film camera know that there are two ways of filming all sides of an object; one is to walk around the object, while filming it, and the other is to hold the camera steady, while spinning the object. In computer graphics, the camera is typically held in the same spot, while the world is rotated around it. This even holds true when you'd swear there was a camera hovering above and around you, as you were blasting aliens and flying corkscrew formations to avoid missiles.

I observed there are three different ways of controlling 3D movement:
  1. FPS or racing game style movement;
  2. Space sim like movement;
  3. Airplane like movement.
The natural way of things is, that the player primarily looks around in the XZ-plane and may look up and down (Y direction). There is a distinction between up and down, and there is an horizon to keep that clear. In an FPS or a racing game, when the player steers left or right, it is 'yawing' (rotating about the Y axis). The sky is up, the ground is below, and there simply is no roll.

In a space sim, it is more likely you will roll the ship on its side by steering left (rotation about the Z axis). Up and down typically adjusts the pitch. There is not really an up or down, although there are probably some other objects around like ships, space stations, and planets that give you a feeling of orientation. Yawing is probably possible, but by default it flies more like an airplane, because it feels more natural like that. Because you can steer the ship in any direction you like, this kind of control is called six degrees of freedom (6DOF).

Airplane-like movement is much like space sim movement, but there is a clear difference. Steering left will roll the airplane, and when you let go of the stick, the plane levels automatically and roll and pitch will return to zero. This is different from spaceship movement, because the airplane wants to fly 'forward', while a spaceship simply goes on into deep space in any direction you steer it.

For the typical first person shooter style game you can get away with having a vector for your heading, and a pitch vector for looking up and down. A camera is easily implemented using only two glRotatef() calls.
For 6DOF, things are totally different. You'd say that you could add a vector for rolling, but that doesn't quite work. The reason that it doesn't work, is because rotations are not commutative. If the player does a roll, pitch, roll, yaw, and pitch sequence, you can not get this orientation right using glLoadIdentity() and three glRotatef() calls. (Note: In theory, it should be possible, but it's an incredible hassle to compute the new Euler angles every step of the way). The correct way to do it, is to use an orientation matrix.
The matrix holds the directional vectors and the coordinates for this object in 3D space. This matrix can then be loaded and used directly in OpenGL by calling glLoadMatrixf() or glMultMatrixf(). Manipulating the matrix is easily done through calling glRotatef() and glTranslatef(). Behind the scenes, glRotatef() and glTranslatef() are matrix multiplications (in fact, the transformation matrices are documented in the man pages) (1).

A single 4x4 matrix multiplication consist of 64 floating point multiplications. When you do incremental rotations without resetting the matrix to identity every now and then, the many floating point multiplications will eventually cause small rounding errors to build up to big errors. This leads to an effect known as gimbal lock. When gimbal lock occurs, the errors in the matrix have become so large that the spaceship can no longer be controlled.
Microsoft Freelancer was a pretty cool game, until one day I ran into gimbal lock right after saving a game. Loading up the saved game would throw you right into gimbal lock again, completely ruining the game.
A way to prevent gimbal lock is to make the matrix orthogonal every once in a while. Orthogonalizing a matrix is such a big mathematical hassle that practically no one is using this technique. So, just forget about that and read on.

There is another way of storing orientation and computing rotations, that does not suffer from gimbal lock. This is done with quaternions. Quaternions are a neat math trick with complex numbers that allow you to do vector rotations, just like with matrices, only a bit different.
Remember from elementary math class that a * a (or a squared) is never a negative number? Well, for complex numbers someone has thought up that i squared equals -1. As a consequence, a whole new set of interesting possibilities opens up, among which quaternions, which are 4D vectors in complex space that can be mapped back into a 3D matrix for use with OpenGL.

The quaternion stuff is quite hard to grasp when you try to understand the math (I guess "complex numbers" aren't called "complex" for nothing). However, if you just go and use them you will probably find that they are not that different from working with matrices.
I'm not going to duplicate the code here, there is some excellent description and quaternion code available here: GameDev OpenGL Tutorials: Using Quaternions to represent rotation. Go read it if you want to know more, and you should know that I think this code is better than the one in NeHe's quaternion tutorial, which apparently has the sign of the rotations wrong.

  1. Note that many 3D programmers write matrix multiplication code by themselves, but this is not always necessary since you can use OpenGL's functions to do the matrix math. An advantage of rolling your own is that you can do some matrix calculations even before an OpenGL context has been created, so before OpenGL has been initialized. Your code will generate an exception/segmentation fault if you call OpenGL before having created a context.