Buddhabrot Renderer, Part 1

For the next three labs we will write a program to render the very well-known Mandelbrot set using a less well-known, and very computationally intensive, approach. Along the way, you will get to explore a number of useful C++ language features, and tools used by many C/C++ programs.

The Mandelbrot Set

The Mandelbrot set is one of the most well-known fractals; virtually everyone recognizes its iconic shape:

Mandelbrot Set

The Mandelbrot set is generated by iterating a specific function zn+1 = zn2 + c, where all values are complex numbers.

Initially, z0 = 0 + 0i. The point c is taken somewhere from the region (-2 - 1.5i) to (1 + 1.5i). The above operation is iterated until the series either diverges, or if it remains bounded. This is approximated by the following conditions:

Of course, this is an approximation. With large enough compute power, and high enough precision in your arithmetic, you can explore the endless detail in the Mandelbrot set. But, this approximation is certainly fine enough to draw pictures like the one above. In that picture, all black pixels are part of the Mandelbrot set. All colored pixels are not part of the Mandelbrot set, and the pixels are colored based on how many iterations were necessary before the |zn| > 2 condition was encountered.

OPTIONAL: The Mandelbrot Set and the Logistic Map

If you have 20 minutes to spare, check out this great Veritasium video about the Mandelbrot set, another remarkable mathematical phenomenon called the logistic map, and many physical processes.

Buddhabrot Rendering

The Mandelbrot set is very fun to explore just using the above simple rendering technique, but there are numerous other ways to render and explore this fascinating mathematical construct. One of the more interesting and compute-intensive approaches is called Buddhabrot, which works like this:

This process is repeated many many times, for many random starting points. (One million random starting locations is at the low end of what is required.) Once this has been completed, the image is normalized, and the result looks something like this:

Buddhabrot Set

In other words, for points c that escape (and are therefore not in the Mandelbrot set), we record the entire escape trajectory, and then we use these points to draw a density map.

Program Overview

For this assignment you will start creating a Buddhabrot renderer called bbrot that is able to generate pictures like the above. We are going to create this as a command-line tool that takes its parameters from the command line, and generates its result to standard output. Errors and progress information will be generated to standard error. For example, the above image was generated with an invocation like this:

./bbrot 600 50000000 5000 > image.pgm

You can see that if errors or progress information were output to standard output, that would mess up the image data.

The arguments are as follows:

The following sections will describe how to implement the various parts of this program. Note that we are providing some initial files to help constrain the architecture of your solution, so that it's easier to extend the program over the next few assignments.

Computing the Mandelbrot Function

A C++ header file mbrot.h is being provided for you this week, to guide your implementation. In a file mbrot.cpp, you will need to provide an implementation of the compute_mandelbrot() function that operates as described above. Here are some more details.

The compute_mandelbrot() function takes the point c as an argument, and then iterates the Mandelbrot computation up to a maximum of maxiters_ times. The inputs and results of the calculation are stored into a MandelbrotPointInfo struct, which your implementation must return. (Note that this struct is not heap-allocated; you are not returning a pointer to the struct. Because of modern's C++ move operations and copy elision, it is not expensive to return a struct like this.)

These details will be unsurprising, but just to be very specific:

Generating the Buddhabrot Image

Once you have the Mandelbrot calculation implemented, it's time to build the Buddhabrot rendering program around this engine.

The rest of your work for this week will go into a file bbrot.cpp. Specifically, you will put your main() implementation into this file, along with a number of important helper functions. Again, declarations of these functions are provided in the file bbrot.h. (You will need to add various #include statements to bbrot.h to get it working.)

Command-Line Arguments

You have undoubtedly seen many C/C++ programs with this function:

int main(int argc, char **argv)

When you invoke your function, argc is the number of entries in the array argv. The first value, argv[0], is always set to the name used to invoke your program, and the remaining values in argv are the arguments passed to the program. For example, with the above invocation, argc = 4, and argv is {"./bbrot", "600", "50000000", "5000", NULL}. (Note that argv[argc] = NULL; this is set up by the OS when your program starts.)

You will need to convert these arguments to integer values. For now, you can use the atoi() function to convert strings to numbers. This means your program won't catch invalid inputs, but we will fix that limitation in a future assignment.

Your program should parse the following arguments:

All of these values can be of type int.

If the program doesn't get the correct number of arguments, report an error to cerr, and return an exit code of 1. (In other words, main() should return 1 in this situation.) Most importantly, don't crash!

Correspondingly, if your program runs successfully, return an exit code of 0.

Buddhabrot Rendering

Besides parsing arguments, your main() function can also implement the main loop of the Buddhabrot calculation:

You will need a class to represent an image with one value per pixel. Since this is a boring thing to implement, an Image class is provided to you in the file image.h. (You should not need to make any changes to this file.) You can initialize an image of whatever size is needed.

Progress Information

As your program computes, it should output something to tell the user that it is making progress. To this end, your main loop should output a "." (period) after every 100,000 points. You can do this easily if you have a loop variable e.g. i, and output a dot if i % 100000 == 0.

This progress output should go to standard error, not standard output, so that you don't mess up the image data your program will output.

We will make this output much more sophisticated in a future lab.

Generating Random Complex Numbers

The C Standard Library has provided a number of random number generators over the years: rand(), random(), drand48(), and so forth. These generators have various limitations, and the use of some are even discouraged. (The man page for rand() even has this title: "rand, rand_r, srand, sranddev -- bad random number generator".) The C++ Standard Library finally addressed this issue in C++11, providing a set of abstractions for implementing sources of pseudo-randomness and true randomness, and also for generating random values with different distributions. It is finally useful for doing scientific and mathematical computing.

All of this great functionality is provided in the C++ <random> header. You are encouraged to read the documentation about the C++ <random> library so you can learn about all of the great features it contains, but so many features also makes it difficult to figure out what to use in our program. So, we'll make it easy:

All of these variables should live outside the main loop that generates random complex numbers and does the Mandelbrot calculations, so that you get good random results, and also so that you don't incur the overhead of initializing them every iteration through the loop.

Note: You will notice these ranges [-2, 1] and [-1.5, 1.5] showing up regularly in your implementation. Define C++-style typed constants for these values. Don't use the C-style #define to define typed constants in C++ programs.

Updating the Image

Once you have generated a random complex number c, and you've used the compute_mandelbrot() function to determine that it isn't in the Mandelbrot set, you will need to update the image with the point's escape-path. There are two helper functions you will implement to do this.

Outputting the Image

You might think that outputting an image from a program is complicated, but there is a family of simple image formats named Netpbm that makes this task very easy. In particular, Netpbm includes several ASCII plaintext image formats, for color images, grayscale images, and bitmap images. ASCII plaintext images are huge, but they are also easy for a program to output, most OSes support them, and you can always convert them into a better format like PNG or JPEG using simple command-line tools.

Since our Buddhabrot rendering technique generates monochrome grayscale images, we will use the Portable GrayMap (PGM) format. The image is an ASCII text file, as follows:

P2 width height max_value
v1 v2 v3 ...

...and that's it! The P2 value is a "magic number" indicating the grayscale image format. The width, height and maxvalue_ values are all integers; maxvalue_ is simply the largest pixel value in the image, and must be less than 65536. After that, the vi values are simply the grayscale values for the pixels in the image.

(If you ever want to output an RGB image easily, you can use the P3 magic number, and then the only change is that you output 3 values per pixel, instead of just one value per pixel. This is the Portable PixMap format.)

The Netpbm format specifies that no line in the output image should be longer than 70 characters, but you can safely ignore this constraint. Just make sure to emit a newline after the max_value, and also after every row of the image is output. This will help with debugging your program.

In bbrot.cpp you will need to implement the output_image_to_pgm() function to encode the generated image data in ASCII PGM format, and write it out to the specified output-stream. The function needs to work as follows:

1) Find the maximum pixel value in the entire image. In all likelihood, this value will be much larger than 65536.

2) Output the image data in the format above, using a "maximum value" of 255. This means you will need to scale each pixel's value to the range [0..255], using the maximum value you found in step 1 to scale the values appropriately. (You may again find the normalize() function to be very helpful in this calculation.)

As stated before, make sure to emit a newline after the first line with the
magic number and image dimensions, and emit a newline after each line of
image data.

Make sure you only output integer values; ASCII Netpbm doesn't understand
floating-point values.

Finally, make sure that all values are separated with whitespace; failure to
do this can lead to very confusing errors.

Commenting

Make sure to document your code, focusing specifically on writing a reasonably detailed header comment for every function you implemented this week. Use the Doxygen commenting format. (You don't have to provide a Doxyfile or anything like that, unless you really want to.)

Makefile

As usual, create a Makefile for your project that builds a bbrot binary. Your Makefile should include an all target and a clean target, as usual.

Testing

Once you have completed the above steps, it's time to start testing and debugging your program. While all tasks are straightforward, it's easy to be tripped up by the vagaries of C++ floating-point and integer math, and other irritating issues you might encounter. You should stick with low-resolution outputs until you have gotten everything working properly. Then, if you want, you can crank up the settings!

This kind of program will greatly benefit from turning on compiler optimizations, either the -O2 or -O3 setting. If you do this, you will notice a significant performance improvement. Just be aware that this will hinder debugging your program, so you may not want to try this until your code is working well.

Here are some example outputs for you to compare against:

./bbrot 200 1000000 100 > img_100.pgm

200x200 image, 100-iteration limit, 1M points

./bbrot 200 1000000 500 > img_500.pgm

200x200 image, 500-iteration limit, 1M points

./bbrot 200 1000000 1000 > img_1000.pgm

200x200 image, 1000-iteration limit, 1M points

You will notice that as you increase the iteration limit, more and more detail will appear in the Buddhabrot output. Also, as you increase the total number of points generated, the image will become less noisy as more detail is filled in. However, it's very easy to sink a lot of time into generating results, so you may want to avoid being too ambitious in your computations.

As a simple example, here is another version of the first image above, with 10M points instead of 1M points:

./bbrot 200 10000000 100 > img_100.pgm

200x200 image, 100-iteration limit, 10M points

Finally, if you accidentally use the points that don't escape, your plot will look more like this, showing the many lobes of the Mandelbrot set:

200x200 image, 1000-iteration limit, 10M points, plot non-escaping points

All Done!

Once you have finished testing and debugging your program, submit these files to codePost.io:

We will use a fresh copy of image.h, so you don't need to submit this file.