The Ablative Air debris-removing weapons are all derived from scientific proposals for how to remove orbital debris: lasers, aerogel, and physical collection via automated satellites. (Electrical tethers are another proposal, but they seemed too boring from a gameplay standpoint. Sorry tether fans.)

In my original game design, I had always planned on implementing the big three: lasers, aerogel, and satellites. Lasers were easy–I did that first, and was the only weapon for a while. Hunter/Seeker – a little satellite that goes around collecting up debris – was written almost completely on a particularly long layover in the Frankfurt airport. But Aerogel I left to the bitter end, only implementing it about two weeks before my gold candidate. Why?

Because the math sucks. Or should I say, I wasn’t thinking about things properly. You see, I was still thinking in ordinary 3D cartesian coordinates. Pooh on that! My breakthrough came by thinking like a quaternion.

If you’re not familiar with quaternions, they’re 4 dimensional complex numbers, and they’re extraordinarily good for representing rotations. Plenty of other 3D game authoring sites talk about them in length. All my orbital mechanics, view manipulation, and tracking is done with quaternion math, and I’ve needed them from the very beginning of the game so I had to learn about them pretty early on.

Quaternions are not terrifically natural to my mind, so I don’t always think of them even when they’re the perfect tool for the problem at hand. What problem was I was trying to solve?

Quite simply, I needed circular decals placed on the atmospheric surface. They spread and become more diffuse until they evaporate. The screen shot shows two blobs of it: a younger one near the center, and an older, bigger (and dimmer) one to the left of the station.

Simple, no?

Seemed so–all I needed to do was calculate all the points on a sphere that were a certain radius from a given point. So I got out paper & pencil, and started drawing out the math. And realized that my simple 2D circle calculations wouldn’t quite cut it. So then I figured–ah hah! It’s as simple as having a plane intersecting a sphere! So I looked up great (and lesser) circle calculations, and implemented some of those equations. But I still didn’t get it quite right. So then I thought–wait! I know–it’s just a cylinder intersecting a sphere!

You see the pattern here. I couldn’t find exactly the formula I needed on the Internet, and although I could create a system of equations to represent the problem, I realized I was too lazy (or too rusty, or both) to do all the math.

Maybe I could have slogged through all the math eventually, but stepping away from the problem gave me the solution. I was already using quaternions for spherical rotations, can’t I use them here?

Most certainly I could.

What was a page full of intimidating coordinate transforms and trig boiled down to two very simple quaternion operations:

1) Rotate a point from the center of the decal to the edge.

2) Rotate the edge point completely around, tracing the outline of the circle (like you would with a drafting compass).

That’s it. Easy peasy!

After having that Eureka moment, I almost jumped naked out of my bath and ran through the streets of Athens. (Well, not actually, but I was pretty stoked to have solved a bugger of a problem with no real “math” to speak of.)

The actual function is almost as simple; after that mental breakthrough it took me all of 5 minutes to get working. You’ll note that I save the center point and the first edge point twice since I’m creating a GL FAN to draw the graphic. With my Aerogel implmentation I don’t bother with an spherical 3D patch that conforms to the surface of the sphere. It’s good enough for my purposes that I create just a circle. Since the decal sits on top of the transparent atmosphere, it won’t ever intersect the earth surface. Creating a spherical patch with quaternions should be almost as simple–you just need to trace out each ray as well as the outer edge. I leave that as an exercise for the reader.

void Aerogel::setVerticesFromRadius(float radius) {
    // Save the center point as the first point of the fan
    vertexArray[0] = location;

    // Create the normal to the location, based 
    // on any arbitrary vector (here we use "up")
    Vector3 norm = crossProduct(location, Vector3(1,0,0));

    // Create a quaternion that can rotate our 
    // center point to the edge of the circle
    Quaternion q;
    q.setToRotateAboutAxis(norm, radius);

    // Rotate our center point out to the edge: 
    // this is the start of tracing our circle
    Vector3 p = rotate(location, q);

    // Create a new rotation that rotates around 
    // the axis (the original point), scribing a circle
    q.setToRotateAboutAxis(location, (2.0*M_PI)/AerogelSegments);

    // Now it's easy: Save our points by tracing 
    // around the edge and rotating to next point
    for (int i=0; i<AerogelSegments; i++) {
        vertexArray[i+1] = p;
        p = rotate(p,q);
    }
    // Save the first edge point again to close the circle
    vertexArray[AerogelVertices-1] = vertexArray[1];
}

Long title, agreed. If you have a short attention span, I’ll save you right here and give you the goods.

(1)Don’t use this:

float rand(vec2 co)
{
   return fract(sin(dot(co.xy,vec2(12.9898,78.233))) * 43758.5453);
}

(2)Do use this:

highp float rand(vec2 co)
{
    highp float a = 12.9898;
    highp float b = 78.233;
    highp float c = 43758.5453;
    highp float dt= dot(co.xy ,vec2(a,b));
    highp float sn= mod(dt,3.14);
    return fract(sin(sn) * c);
}

Version 1 is found in dozens of places on the internet. Try doing a search for “GLSL rand”, and among all the Perlin noise routines you’ll find the little gem in (1) tossed out many times. I don’t know the person who first wrote it, but hats off to him/her. It’s reliant on the fact that sin(x) modulates slowly, but sin(<huge multiplier>*x) modulates extremely quickly. So quickly that sampling the sin function at every fragment location effectively gives you “random” numbers.

Of course, this is all dependent on the GPU implementation and the quality of the sin calculation. On the BlackBerry Z10 (model STL100-2 using a Qualcomm Adreno 225) version 1 of the code works perfectly fine. I use this function to introduce background roughness into my Milkyway rendering for Ablative Air. The Milky Way image is rendered on the inside of a sphere. Without the noise, the texturing of the background looks crudely pixelated. With the noise, it almost looks like a Hubble photo. Here are two examples–not the exact same region, but you can get the idea of the difference.

Fig 1. Milky Way with noise

Fig 2. Milkyway without noise.

So, what’s the problem? I ported this renderer onto the Z30 which uses a slightly different GPU. The GPU in both cases is an Adreno (225 vs 320), but I suspect that this problem could occur on many different GPUs, as the random function relies on “problematic” behaviour.

And guess what? On the Adreno 320, my noise function completely disappeared. It became mostly all white (rand() returning 1.0) with black lines running through the noise at periodic intervals.  The effect is somewhat difficult to see underneath the Milky Way texture unless you magnify the image a lot. I saw it initially by hooking my game up to an HDMI equipped TV. In the samples below, I’ve removed the Milkyway texture to make it incredibly easy to spot. I’m just showing a texture built exclusively with the noise function.

Fig 3. Pure noise texture – Adreno 225 GPU

Fig 4. Pure noise texture – Adreno 320 GPU

As you can see, figure 4 is a little less random than you might like for noise. That is, it’s not random by any stretch of the imagination.

How has our trusty little GLSL random function failed us?

I had encountered a similar issue before in one of my other GLSL ports. My shader for Ablative Air’s laser “scattering” effect also relies on sin(), so I immediately suspected the sin function was overflowing on the Adreno 320 GPU. This is purely guesswork, but I think the implementation for that GPU does not precondition the sin() input to a reasonable 2PI range first. It just applies a Taylor series (or some other approximation) to the input value without any range check. The Adreno 320 implementation is likely a scooch faster, but it’s definitely less accurate than the earlier Adreno 225, certainly for this purpose.

My fix may be a little bit overkill, but it’s safe: force all constants to high precision and use mod to get the sin input value within a reasonable range first. My version is much safer, and shouldn’t rely on any particular quirks of the GPU’s sin function implementation.  Here’s the result of my fix running on the Adreno 320: perfectly acceptable noise, just like we wanted.

Fig 5. Adreno 320 GPU with improved noise function

In fact, my tweaks to this beautiful little algorithm is probably a little cleaner than the original function, even when running on the original Adreno 225. If you look closely at the noise in Figure 3, you can see tiny stripes of regular looking data peeking out. Squint up your eyes “snake eye” style, and look near the bottom centre of the image and you’ll see three vertically stacked diagonal slashes. It’s a little bit more apparent when the texture is in motion, but those patterns aren’t visible in figure 5 using the improved noise function. I suspect that the Adreno 225 GPU, while it provides a more robust sin() implementation, is still subject to floating point inaccuracies from the lack of high precision. Hence why I’ve kept the “highp” in there, just in case.

This blog is so I can share things that I’ve learned while writing my game. If you might be interested in what I’ve learned about OpenGL ES or quaternions or BB10 development, you’re in the right place. If you either don’t know what those things are, don’t care, or those terms make you dry heave, I’d recommend going over to my FaceBook page instead. That page is for fans of the game, where I put hints or tips about gameplay–generally items of broad interest.

Just finished posting my application submission this morning…  Let’s see how long it takes to get approved!