I don’t know why, tumbling asteroids just seem cool. Also, they are useful in games, and I have a brand new star destroyer that needs something to play with. Also, the last time I tried to make them, they looked more like giant teeth….

This project (and post) was a lot of fun for me because as happens so often, it brings in lots of other topics – some of which I’ve blogged about before – and there is a lot to learn, if you want to know about 3D. Anyway, this is the result.

This post is very long and contains a lot of different techniques, all just to throw some oversized rocks at the camera, but I’m not trying to impress or frighten you.

On the one hand, I’m trying to show how much is involved in 3D graphics, but if you look at any of the many references I have included, you should find that each technique is not scary if you take it on its own. So while learning 3D is not something you learn in a morning, most people can master it with some effort, and the more techniques you learn, one by one, the easier and better it will get.

I have no doubt that what I’ve done can be improved, because I’m no expert, and I’d never done graphics programming before starting Codea, two years ago. But I’ve never had so much fun as with 3D, even on the many occasions when I’m staring at a black screen because it’s drawing behind me or not at all, for some reason I can’t understand.

So I suggest reading as much of this as you can, skipping anything you just don’t understand, and looking for things that interest you.

### Getting started

I started afresh with this project. Naturally, the first thing I did was to see if Uncle Google could help me.

I found some complicated algorithms, eg something called (I think) tumbling boxes. No, I don’t want someone’s PhD math thesis – I want to keep it simple so I can understand it.

Then I saw a suggestion to build a sphere, and deform (pull or push) individual vertices up or down to create a bumpy surface. I can visualise this, so how hard can it be?

### Building a sphere

Building a sphere is a bit tricky, but luckily I have some sphere code tucked away, thanks to my friend Jmv38 on the Codea forum, also code from LoopSpace, which is part of a shapes library. Sometimes, the best way to write code is not to have to write it!

However, they both give you a sphere that looks like this

I’m going to be distorting vertices, and you can see they are bunched up around the top and bottom, which is going to look odd. It would be better if the vertices were evenly spaced, as shown below (I’ll explain why there are three images in a minute, just look at the one on the left). This is called an icosphere.

I had to write the code for this, but of course I cheated and converted some C++ code I found. It starts by creating a very rough sphere with just 12 triangles, then subdividing each triangle into 4, then doing it again, which gives you the effect in the three images above. Each subdivision makes the sphere smoother, but multiplies the number of vertices by 5.

Creating an icosphere seems to be faster than creating a “normal” sphere, with the code I have, but there is one big downside – I don’t know how to set texture coordinates for an icosphere, so I can’t apply an image texture. In this case, it doesn’t matter too much because the asteroids are flashing past at high speed.

### Deforming the sphere

This is where it gets tricky.

If I just randomly change vertex positions, I’ll got a mess. Time to think logically. I got a hint from something I read, which is to move the vertices up or down their normal. Luckily I know what this is.

### Normals

I’ve written about normals before, but this is a special case, so I need to explain. If you look at the sphere below, and look at any triangle, you’ll see it has a flat face. It has a blue line sticking out of it, at right angles to the flat surface.

The line is the normal, ie the line at right angles to the triangle face.

• Why is it called “normal”? From the Latin word normalis, meaning “at right angles”.
• Normals are used for several things, one being lighting, because if you shine a light on a surface, the brightness (=reflection) is greatest if the light is at right angles to the surface, and reduces as the light is at a greater angle.
• How do we measure how close the angle of the light is to the normal? Using a dot product, as explained here.

So if I pull each vertex up (or down) along that blue line, I will get sensible looking distortions.

Hold on Houston, we have a problem. If I push and pull whole triangles up and down, it’s going to get very blocky. Also, each vertex is used in several triangles, and it can’t be pulled several different ways at once.

So I need to distort (push and pull) individual vertices, not faces (of three vertices each). But how do I solve the problem that each vertex belongs to several triangles, each with different “normal” vectors?

One solution would be to loop through all the triangle faces for each vertex, and average their “normal” vectors. That would work, but there’s a simpler way to calculate each vertex normal. Imagine a line starting at the middle of the sphere and running through the vertex. This line will be at right angles to that point on the surface, and is the normal of the vertex, as shown below (I apologise for the different graphic styles, I’m just borrowing images where I can find them, for this post).

So the normal direction = [vertex position] – [sphere centre position]

Now, when I built the sphere, I cunningly made (0,0,0) the centre (actually, I needed to do that so I could rotate it round its centre). So I don’t need to subtract anything, and the normal of any vertex is simply the vertex itself!

### Distorting vertices

So now I have a sphere with lots of vertices, each of them with an imaginary line running from the centre, out through the vertex, and I’m going to push the vertex up or down that line, like this.

vertex = vertex * (1+ [some random percentage])

Sounds pretty easy, just make a loop with some random changes to randomly chosen vectors, right?

Well, if you don’t mind a lot of spikes, maybe. I don’t know if you’ve seen pictures of real asteroids, but they look a bit like lumpy potatoes, and while they are odd shaped, their surfaces are fairly rounded and definitely not spiky.

The answer is that if (say) I push a vertex up, it should drag the nearby vertices up with it, to make a kind of hill. If I do this a few times, I’ll get a lumpy blob that looks realistic.

So how do I drag nearby vertices up? I can think of two ways.

Noise

Noise functions are used to make random patterns that change relatively smoothly, as discussed here. So if one point is large, the point next to it will be similarly large. You can use noise to make rolling hills, which is pretty much what we want.

I would have used this method if I was working with a flat surface, but wrapping a noise image round a 3D sphere – especially an icosphere – and avoiding a mess is difficult. I could have tried using 3D noise and fed it vertex positions, I suppose, but I didn’t.

“Lighting” approach

Remember I said that when light falls on a surface, it reflects most at right angles to the surface (along the normal) and less as the angle moves away from that? We can use the same idea here.

Suppose I choose a direction at random, and a random percentage of 10%, then I adjust all the vertices by an amount which depends on how close they are to this vertex, based on how similar their normal is to this vertex’s normal. We can do that with the dot product, which measures exactly this, and gives an answer -1 to 1. I need to ignore the negative values, because those mean a vertex is round the other side of the sphere. So if the dot product is d, then

vertex = vertex * 1.1 * d, but only where d is positive.

If I do this 20 or 30 times, I get good results. Below is a nice potato.

### Centring and sizing

Once I have my asteroid shape, I need to make it the right size, which I can do by multiplying all the vertices by the size I want.

However, when I draw the asteroids and rotate them, some of them seem to rotate round the wrong point. This is because when I distorted the vertices, I stretched the shape, and the original centre is no longer in the middle. So I need to loop through and calculate the average vertex position as my new centre, then loop through again and subtract it from the current vertex position (it’s a good idea to do all this before multiplying by the size).

None of this is complicated, but it’s surprising how many things you need to do, to make this work.

### Placing the asteroids in space

I want the asteroids to appear far off in space and come towards me. I know from trying this previously, that there are at least two more problems I have to solve.

One is that if you start the asteroids off at what seems to be a suitable distance and have them move towards you, they tend to jump out of nowhere, not as dots, but quite large, which looks odd. To make them start off very small, I have to either make them small in size, or start them a lo-o-ong way away, which means they have to move very fast if they’re going to reach me any time before tomorrow. So that needs a bit of fiddling about to get it looking right.

The second problem is where to put them on the screen, because the further away they start, the bigger is the area you can see, just as in real life, when you look at something very far away, you can see whole mountains. So what are the visible limits of the screen, at different distances? Fortunately, I’ve already solved that here.

That helps me solve another problem, which is that if I make the asteroids move straight ahead, ie towards +z, a lot of them will pass to the left, right, above and below me. In fact, many of them will disappear from the screen long before their z position is the same as mine. How do I know when to delete them? Well, the answer from the previous paragraph can be used to figure out at what distance the asteroids will disappear off the screen, so when I’m creating them, I calculate this distance, then each time I draw, I simply check if they’ve reached that point (and then delete them), very simple indeed.

We’re not done yet, though.

If I solve the first problem above by adding asteroids at very long distance (so they appear small to start with), and they move forwards, very very few will end up coming anywhere near me when they get close. This is probably what asteroids are like in real life, but it’s not much of a game if you only have to dodge an asteroid every 5 minutes! I could deal with this by adding lots more asteroids, but I only have an iPad3.

I could cheat by not drawing the actual 3D shape for each asteroid while it is very small, because an image 1-2 pixels acorss is just a dot. I could just draw a dot, until it becomes large enough for the shape to become clear. This would mean I could handle lots and lots of small asteroids, as long as I didn’t have too many up close.

But there is a much simpler solution that I was stupid not to see earlier. Instead of adding asteroids at a fixed distance regardless of size, I can first create a random size, then use the formula above to figure out at what distance they will become visible (eg at least 4 pixels across), and add them at that distance. So small asteroids get added closer than large asteroids.

I still have the problem that if I add them randomly anywhere on the screen, most of them will disappear off it before they get anywhere close, which is a waste, so I started adding them just in the middle 50% of the screen. This looks ok, because as they get closer, they fill up the screen, and the far away asteroids are small anyway.

### Building asteroids in real time

Unfortunately, I am limited in how many asteroids I can show, because Codea is not just having to draw them, but to build them (using the distortion method I described above). In fact, each time it builds one, there is a noticeable pause in the drawing.

There are solutions. One is to recognise that many asteroids disappear off the screen before they get very big, and I could just use a standard sphere for those. A simpler alternative (commonly used in video games) is to build a set of different asteroid shapes at the very beginning, and randomly choose one each time we add an asteroid. This causes a delay of a few seconds at the beginning, but after that, I can add asteroids quickly. And by rotating the asteroids randomly so the shapes look different, I can make my set of asteroids look bigger than it is. This, I think, is the best solution, and it’s what I’ve used. I created 10 different shapes, which took about 3 seconds at the start, and then I could have 50 or more asteroids on screen at once with no problems.

### Including a splash screen

One problem is that if you do the asteroid creation in setup, then nothing gets drawn on screen until they are done.  So here is a simple technique for getting a message on screen while the asteroids are created.

What I did was create a special function that will show a “splash screen” message while the asteroids are loading, and then let the normal draw function run, after everything is ready.

First I store the draw function in a variable, eg drawTemp = draw. It may sound crazy to store a function in a variable until you realise that the draw function itself is actually just a variable called draw, holding the memory address (a number) of the function that I named draw.

So we can copy that address to a variable called drawTemp. And notice I didn’t put brackets on the end of draw – this tells Codea not to run draw, but to give me the address stored in it. So now I have the address of my draw function stored safely.

Next I put a different function address in draw – the function I want to run at the beginning, eg draw = LoadingScreen. Now, when Codea runs draw, it will find the address of LoadingScreen and run that instead.

Inside the LoadingScreen function, I start by showing the message, and increasing a counter, so I know how many frames we’ve drawn. The first time it runs, we just let it draw the message. The next time, we run the function that creates asteroids, which takes a few seconds. The message stays on the screen, though. Then, when the function runs a third time, we know the asteroids are done, and we can put the address of the original draw function back where it blongs, with draw = drawTemp.

It may help you to know that when you create a function with

```function draw()
--some code
end
```

this is exactly the same as writing

```draw = function()
--the same code
end
```

In other words, every time you define a function, Codea creates it in memory, and then stores its address in the name of the function. In other words, the function name is really just a variable, that stores a number (the function address). Because it can be confusing to write functions as draw = function(), Codea gives us the alternative function draw(), and this kind of user friendly alternative is sometimes called syntactic sugar.

### Lighting

I left lighting to last because it involves shaders (ebook). If you don’t know shaders, just skip this bit.

There is a neat trick we can use for lighting, since the vertex positions are also the normals. We can pass the vertex positions (converted from object space to world space via model matrix) through to the fragment shader, and dot them with the light direction to calculate the diffuse light. The advantage of this is that it essentially means that instead of just having normals at vertex positions, we have them for every single pixel, so you get no flat surfaces, and everything is rounded. (Of course, you can’t round the outline of the object, just the interior).

In doing this (see the code below) I had to make one adjustment on the way from the vertex shader to the fragment shader. I had to undo the effect of translation, which I did by applying model matrix to the shape’s centre (which is always 0,0,0) and subtracting this from each vertex position.

It is a great way of getting perfectly rounded shapes from low res meshes (although as I said above, you can’t change the outline of the shape, just the interior).

The video below shows the effect. The first part shows the sphere as it would normally be drawn, with flat triangles, while the second part shows what happens when each pixel has its own “normal”, giving a rounded effect. The faint red lines are the normals for the vertices of the sphere, so the more similar they are to the light direction (which is from over your left shoulder), the brighter the light.

### Code

All of the above why I enjoy programming so much, because the more you think about problems, and the more you learn about whatever it is you are programming, the more solutions you find. There always seems to be a better way.