Starfield simulator - Part two: Starfield calculations, movement vectors and integer rounding
Material covered in this part
Starfield calculations
Initial random placement and movement vectors
Analysing the output - integer rounding artifacts
Partial success - our first reasonable starfield implementation
Summary so far and possible improvements
Starfield calculations
Now that we've got a way to plot pixels and write frames to disk as ppm files, let's turn our attention to calculating the positions of each star.
The particular way that we decide to simulate something from the real world in a mathematical sense is known as a model. A complex model will create a more accurate simulation, but will also likely be several orders of magnitude more complicated to program, and use more computing resources when run. We need to choose an appropriate level of complexity for the requirements of the task in hand.
For our purposes, we're obviously not even trying to simulate accurate star movements from the real world. We're only trying to create an implementation of a common video effect, so we can basically write it however we like.
The simplest model would be to set the initial co-ordinates of each star randomly, and then move them closer to the edge of the screen at a constant speed. Not surprisingly, this looks fairly awful, but it is quite trivial to program.
First, we need a function to clear the framebuffer, and set every pixel to black:
for (i=0; i < (32 + FRAME_WIDTH * FRAME_HEIGHT * 3); i++) { *(framebuffer+i)=0; }
return;
}
We could also have used one of the library functions bzero or memset to do this.
RGBvalues and color gamuts
As this is a programming exercise, and we're only going to be viewing the output on an RGB computer monitor, we can use the whole 0 - 255 range for each of the RGB channels, and in this case black is indeed represented by zero in each channel.
However, be aware that most video formats don't use RGB for color representation, but instead use a luminance channel and two chrominance difference channels, commonly but not entirely correctly referred to as YUV colorspace. If you intend to create RGB ppm files for later import into and conversion by a video editing program, be aware that there may be constraints on the RGB values that you can use. Of note here is that the RGB value 0, 0, 0, that we are using to represent pure black, may fall outside of the required color gamut, and the correct value may be higher, such as 16, 16, 16.
Consumer software and video equipment will likely not care, and just automatically round values to the acceptable range. Professional video equipment will likely throw an error.
We'll call this framebuffer_clear function before each frame, and draw all of the stars afresh. Next we need to place the stars at random locations, so we'll define a structure to hold the X and Y co-ordinate information, and fill it with random values:
struct starinfo {int x; int y;} ;
/* Set initial random co-ordinates for all stars. Call with struct starinfo pre-allocated. */
void init_stars(struct starinfo * star)
{
int i;
for (i=STARS_TOTAL; i--;) {
star[i].x=arc4random_uniform(FRAME_WIDTH);
star[i].y=arc4random_uniform(FRAME_HEIGHT);
}
return ;
}
We've used the two argument form for the for loop here, because this is a very simple function with an obvious purpose. There is no calculation going on within the loop, and it's fairly obvious that we are going to want to iterate over the values 0 - STARS_TOTAL-1, so there is very little chance that future modifications to the code would inadvertently introduce an off-by-one error.
The memory for the structure will be allocated in the main program before calling this function, so we don't need to do it here. Note that the data elements for each star will be stored together in memory. This doesn't matter at all here, as the dataset is tiny, and we will be processing the data for each star in turn anyway. However, when dealing with large datasets, it makes sense to consider the likely access patterns to the data, and organise it in such a way that data items which are likely to be accessed together are stored in adjacent memory locations.
If we were processing data for a million stars, possibly with more information than simple co-ordinates, we might want to process or iterate over all of the stored values for one particular data item to find an average, upper and lower bound, or do some other sort of calculation. In these cases, performance can often be increased by storing the values of each data item for each star sequentially in memory. So in our simple example, we could store all of the X co-ordinates in one array, and all of the Y co-ordinates in another.
If we then want to read back all of those values, we can do so and only need to access about half as many pages of memory, because we won't be reading interleaved Y co-ordinates at the same time. This potentially allows the CPU to more efficiently pre-fetch data from ram into the cache, and avoids filling the CPU caches with data that we are not going to use.
However, for our current purposes, using the obvious structure defined above makes perfect sense.
Random functions, (and the choice thereof!)
For the time being, we're using arc4random_uniform from the arc4random family of random number generator functions to generate the initial star positions. On BSD systems this function is usually included as part of stdlib.h, but on Linux systems it often isn't. If you're following these examples using a Linux system, you would probably either want to install and include bsdlib.h, or substitute an alternative random function.
Arc4random provides good quality random data, and in almost all cases this is a desirable thing to have. Patterns or non-randomness in values that are expected to be truly random can have all sorts of unexpected side-effects, including introducing non-obvious and hard to find security vulnerabilities into your code. Shortly we'll return to this point, and see a genuine use-case for the deterministic rand function, use of which is discouraged in almost all cases. For now, though, we'll use good quality random from arc4random_uniform.
Our new main function just needs to allocate storage for the star data, initialize it by calling init_stars, and then loop around repeatedly clearing the framebuffer, plotting the pixels that correspond to the current star positions, updating those positions, and writing the completed frame as a sequentially numbered ppm file.
First we define some new integer variables; vx and vy will be used to store the motion vectors for each star processed, i is a general purpose counter, and current_frame holds the sequential number of the animation frame that we are currently working on, which we need to create the output filename. We also define three pointers, filename will obviously be used to build the output filename for the current frame, framebuffer is the same as before, and we also have a pointer to an instance of the starinfo structure we defined earlier, to hold the sets of co-ordinates.
We allocate sufficient memory space for STARS_TOTAL entries, again using malloc with a multiplication which is perfectly safe as the values are known to be within acceptable limits in our use case.
Next, we call init_stars to set up our initial random co-ordinates, then begin the main loop. This is where things finally get more interesting, as the following code is where we actually implement the model of the star movement.
First, we set the framebuffer to black with a call to framebuffer_clear, and enter another loop that iterates over the co-ordinates for each star. We immediately plot the co-ordinates we read as a single white pixel, RGB values 255, 255, 255, then calculate the X velocity vector, in other words, how quickly this star is moving ‘horizontally’. We do this by subtracting the X co-ordinate from half of the width of the framebuffer, in other words, the middle horizontally. Further from the middle, the star is ‘closer’ to us, and so moves more quickly. Since typical values for a 1920 × 1080 framebuffer might be in the low hundreds, either positive or negative, we divide this value by 32, to avoid the star movements being too rapid and jerky. 32 is an arbitrary number, although as we are dealing with integer arithmetic here, it makes sense to choose a number which is a power of 2, that is, a round number in binary.
We subtract this value from the current X co-ordinate, which obviously turns into an addition for stars on the right hand side of the screen, as the vx number itself would be negative. At this point, we have our new X co-ordinate, ready to draw on the next animation frame.
We repeat the whole process for the Y value, and then do a quick check to see if the new position still lies within the co-ordinate range of the framebuffer. If it does, everything is fine. If the new co-ordinate lies outside the bounds of the framebuffer, then the star has moved off-screen, and we simply reposition it at a random location just as we did for all of the stars in init_stars.
Note that we don't have to ensure that the new random co-ordinates fall near the centre of the screen for a good visual effect. Although all of our stars are currently going to be plotted as the same brightness, in reality stars vary in brightness, and it seems logical that some might not come into view until they are closer to us. So an entirely random placement should work just fine.
After this we end the stars loop, and write an appropriate filename into the buffer filename using asprintf, which will allocate memory for us automatically. We then call output_ppm to write the ppm file to disk, and loop for the remaining frames after freeing the filename buffer that asprintf allocated.
Lets compile it, and have a look at the output...
Analysis of the output
Well, the code compiles and runs. It does indeed produce a vaguely recognisable starfield simulation. So far, so good.
But there is obviously a lot of room for improvement.
To start with, the stars being a single white pixel makes them quite difficult to see if your monitor doesn't have good contrast or you're in a bright room. This can easily be overcome by plotting a square of four white pixels.
We also need to adjust the bounds for the initial random co-ordinates, and the check for stars that have moved off-screen, as well as the new random co-ordinates for any that have, all to make sure that our extra pixels don't fall outside of the framebuffer. This makes three sections of code to update:
if (star[i].x<0 || 1+star[i].x>=FRAME_WIDTH || star[i].y<0 || 1+star[i].y>=FRAME_HEIGHT) {
star[i].x=arc4random_uniform(FRAME_WIDTH);
star[i].y=arc4random_uniform(FRAME_HEIGHT);
Re-compiling and re-running the code, the stars are definitely more distinct. However, look more carefully at the generated display. There are other problems apparent.
If we run the code repeatedly, each invocation will give us a different starfield, as we're using non-deterministic random numbers. This is a good thing during testing, as the erroneous effects are more pronouned with some initial co-ordinate values than with others.
The most obvious problem is that stars near the centre of the screen remain fixed in place. In reality, this might not be considered an error, because if the star is a comparatively far away, it might take some time to visibly change position. But for our purposes of generating a ‘speeding through space’ video effect, it just doesn't look right.
The reason for this undesired effect becomes immediately obvious if we look at the movement vector equations again:
vx=FRAME_WIDTH/2-star[i].x; vx=vx/32;
Since we're using integer arithmetic, values of vx less than 32 will evaluate to zero. The star won't move at all, and so vx will also evaluate to zero on the next frame, and so on. The star will remain fixed in place forever.
The simplest way to fix this would be to simply add a value of +/- 1 to vx, to ensure movement of at least one pixel. Let's see what happens if we make this change, but first let's temporarily remove the call to framebuffer_clear. This will cause the program to plot the movement of the stars as a continuous trail, as the data from previous frames will still be in the framebuffer when we write the data for the current frame:
Most of the output is fine, but near the middle the star trails are obviously ragged.
This is another integer rounding artifact. A star at the very centre, with co-ordinates 960, 540, will start by moving a single pixel, and will do this for 32 frames. For the next 16 frames, it will move two pixels, followed by 11 frames of three pixels, 8 frames of four pixels, and so on. The numbers involved might seem too small to make a visible difference, but clearly they do. You can even see the problem with the call to framebuffer_clear in place, if you look carefully. Every so often, the starts appear to be shifting into a higher gear, and jump forward.
Luckily, this problem is easily solved without resorting to using floating-point maths. We can simply scale all of the co-ordinates and movement vectors up by a fixed amount to do our calculations, and then divide the value back down again to get the co-ordinates to plot on the framebuffer:
This is how the changed parts of the code look with a scaling factor of 32 added.
We've used a define for the scaling factor here, as it's quite possible that the value 32 could occur in a completely unrelated context elsewhere in the code, and cause confusion at a later date. It also allows for easy adjustment and tweaking of the exact scaling value throughout the code.
Looking at the output, we can clearly see the improvement. The ragged star trails have disappeared completely. You might have also noticed that we removed the code to add or subtract 1 from the movement vectors. It's no longer necessary, because movement of less than one pixel is now possible, so even a star at position 959, 539 would move 1 ⁄ 32 of a pixel
Summary so far and possible improvements
We've arrived at a passable, although admittedly very basic, implementation of a starfield simulator fairly quickly. Excluding comments, it's only about 80 lines of C, and it compiles to an executable of about 10 kilobytes.
In the final part of this project, we'll look at some interesting improvements that we can add without much further effort, including variable star size, trails, and color. Flexibility that we probably wouldn't have if we'd just used a function built into an off-the-shelf video editor.