Milestone 1 Wednesday, Apr 21st by 11:59 PM

Milestone 2 Tuesday, May 4th by 11:59 PM

Getting Started

Getting Started

Download CS201_Assign04_Gradle.zip. Extract the zip file and import it into Eclipse

File→Import…→Gradle→Existing Gradle Project

You should see a project called CS201_Assign04_Gradle in the Package Explorer window.

This is a substantial project. Do not wait until the last minute to start it!

The Mandelbrot Set

The Mandelbrot set is a fractal: a mathematical object that is self-similar at all scales. It is defined as follows:

Note that the magnitude of a complex number is the square root of the sum of the squares of its real and imaginary components. See the Wikipedia article linked above for an explanation of how to add and multiply complex numbers.

Your Task

Your task is to implement a renderer for the Mandelbrot Set, using parallel computation to speed up the rendering process.

You can see a demo (which also allows zooming by selecting a region with the mouse): Simple Mandelbrot or ColorChooser Mandelbrot.

For example, using the default values produces the following generated output file (click to see larger version):

As a second example, (user input in bold):

Please enter coordinates of region to render:
  x1: -1.286667
  y1: -0.413333
  x2: -1.066667
  y2: -0.193333
Output filename: output.png
Choose a color chooser:
   1 - Simple Gradient
   2 - Color Mapping
1
Enter the number of threads to use: 1
Working...
Output file written successfully!

Should generate an output file that looks something like this (click to see larger version):

Complex class

Because the core computation is based on complex numbers, having a class to represent complex numbers will make implementing the computation much easier. Your task is to implement the add(), multiply(), and getMagnitude() methods for complex numbers as described in the comments.

Mandelbrot class

The program has commented code to prompt the user for a pair of x,y coordinates specifying corners of a rectangle in the x/y plane, the default coordinates are (-2,-2) to (2,2). The program also has commented code to prompt the user to enter the name of a file ending with the “.png” file extension, the default filename is output.png. Next, the program has commented code to prompt the user to select a color palette, the default is the provided SimpleGradientColorChooser. Lastly, the program has commented code to prompt the user for the number of parallel threads to use, the default is 1. The program will render an 800 pixel by 800 pixel image which visualizes the specified region of the Mandelbrot set.

Your task is to implement the computeIterations() method which will create a set of MandelbrotTask objects and assign them to separate threads for execution. Code has been provided to generate the output image once all the threads have completed.

Exploit all the cores!
Apologies to Allie Brosh

MandelbrotTask class

You will also need to implement the MandelbrotTask class by

ColorMappingColorChooser class

The ColorMappingColorChooser class has been supplied. It implements the ColorChooser interface, which has a single method: getColor(). After you have completed the following tasks, getColor() will return colors based on the frequency of occurrence of each iterCount.

Your task is to finish implementing the three methods that create the following maps

JUnit test cases have been provided for the createIterSpectrumMap() and createIterColorMap() methods.

Using this class (you’ll need to uncomment the selection code in the main method in the Mandelbrot class) should produce something similar to the following output file (click to see larger version):

Hints

Creating the MandelbrotTask class

Here is a suggested skeleton:

public class MandelbrotTask implements Runnable {
    private double x1, y1, x2, y2;
    private int startCol, endCol, startRow, endRow;
    private int[][] iterCounts;

    public MandelbrotTask(double x1, double y1, double x2, double y2,
                          int startCol, int endCol, int startRow, int endRow,
                          int[][] iterCounts) {
        this.x1 = x1;
        this.y1 = y1;
        this.x2 = x2;
        this.y2 = y2;
        this.startCol = startCol;
        this.endCol = endCol;
        this.startRow = startRow;
        this.endRow = endRow;
        this.iterCounts = iterCounts;
    }

    public void run() {
        for (int i = startRow; i < endRow; i++) {
            for (int j = startCol; j < endCol; j++) {
                Complex c = getComplex(i, j);
                int iterCount = computeIterCount(c);
                iterCounts[i][j] = iterCount;
            }
        }
    }

    // TODO: implement getComplex and computeIterCount methods
}

The idea is that a MandelbrotTask object will compute iteration counts for the region of the image with rows from startRow (inclusive) to endRow (exclusive) and columns from startCol (inclusive) to endCol (exclusive). The region of the complex plane is specified by x1, y1, x2, and y2. The iterCounts array is the single global array used to store the iteration counts for the overall image (where the first dimension is rows and the second dimension is columns).

From the main method, computeIterations() can then be called to create MandelbrotTasks. For example,

MandelbrotTask task = MandelbrotTask(x1, y1, x2, y2, 0, WIDTH, 0, HEIGHT, iterCounts);
task.run();

would compute the entire image using a single process without threads.

Rendering the Mandelbrot Set

Rendering the Mandelbrot set is done by assigning a color to sampled points in a region of the x/y plane.

Code is provided in SimpleGradientColorChooser to render points that are in the Mandelbrot set as black. Points that are outside the Mandelbrot set will be rendered using a color that indicates how many times the equation was iterated before the magnitude of Z reached 2.0. In this implementation, the g and b channels will scale logarithmically with the number of iterations.

The renderer will convert each of the iteration array values in the 800 by 800 array into a BufferedImage object based on whether or not the point is in the set, and if not, how many iterations were required to show that it is not in the set using the selected colorChooser palette.

Once the image has been rendered into the BufferedImage object, code has been provided to write it to a file as follows:

OutputStream os = new BufferedOutputStream(new FileOutputStream(fileName));
try {
    ImageIO.write(bufferedImage, "PNG", os);
} finally {
    os.close();
}

Parallelism

The computation performed by the program can take a fair amount of CPU time. However, the computation of the number of iterations for each point is independent of the computations for all other points. Therefore, you can speed the program up by using multiple threads to compute the number of iterations in different parts of the overall region.

For example, you might divide the overall region into quadrants or horizontal/vertical strips, and use a separate thread to compute the points in each part. Then if, for example, you use four threads, if you run the program on a computer with 4 CPU cores there could be up to a 4 times speedup.

Suggestion: Create multiple MandelbrotTask objects, and execute each one in a separate thread within the computeIterations() method in the Mandelbrot class.

ColorMappingColorChooser class

Since the iterCount values do not distribute uniformly across all possible values, many of the iterCount values tend to bunch up into tight groups.

The ColorMappingColorChooser class addresses the issue of the non-uniform distribution of the iterCount values by mapping colors to iterCount values based on their frequency of occurrence, rather than strictly on their value. The frequency of occurence of each iterCount value determines the width of the color spectrum that applies to that iterCount. The spectrum width determines the distance between the colors assigned to the distinct iterCount values.

Creating an instance of ColorMappingColorChooser requires the creation of three separate maps:

There are getter methods provided in the class to return references to these three maps.

Creating the iterCountMap

The createIterCountMap() method accepts a reference to the iterCounts array and populates the iterCountMap field from the iterCounts array contents. The iterCountMap correlates each distinct iterCount with the number of times it occurs in the iterCounts array.

The method must iterates through the iterCounts array, and it will either encounter a new entry (and initialize the occurrence count for that entry) or update the occurrence count for an existing entry.

Creating the iterSpectrumMap

The createIterSpectrumMap() method uses the iterCountMap field and populates the iterSpectrumMap. The iterSpectrumMap correlates each distinct iterCount value key in the iterSpectrumMap with its location in the color spectrum. createIterColorMap will then store a distinct color for each iterCount into the iterSpectrumMap.

The method must iterate through the keys of the iterCountMap (in ascending order) and accumulate the location of each iterCount from the beginning of the color spectrum. The occurrence count for each iterCountMap key determines the width of the spectrum band that the iterCount occupies. The sum of the prior occurence counts (widths or spectrum bands) determines the location of the leading edge of the next iterCount spectrum band. Each iterCount is then centered in its spectrum band:

   centered location = leading edge location + (width / 2) + 1

The above result is then stored as the value in the iterSpectrumMap with its respective iterCount key.

At the end of iteration, the width of the entire spectrum (the sum of all the values in the iterSpectrumMap) is stored in the class field maxLocation.

Creating the iterColorMap

The createIterColorMap() method utilizes the iterSpectrumMap field to populate the iterColorMap from the iterSpectrumMap contents. The iterColorMap correlates each distinct iterCount key in the iterSpectrumMap with its corresponding RGB color value.

The method must iterate through the iterSpectrumMap to get the spectrum location for each distinct iterCount. The spectrum location is then used to determine the red, green, and blue color components for that iterCount. Each iterCount key and its respective color value are then stored in the iterColorMap. The getColor() method then returns the color associated with each iterCount by looking up the color in the iterColorMap.

The calculations for the red, green, and blue color components for each iterCount use its relative spectrum location:

    relative spectrum location = spectrum location / maxLocation

combined with the sine and cosine trig functions to generate smooth transitions between the composite RGB spectrum colors. The color component calculations are:

red = sin(spectrum location / maxLocation * PI/2) * 255

green = sin(spectrum location / maxLocation * PI) * 255

blue = cos(spectrum location / maxLocation * PI/2) * 255

The color value is then created from:

    color = new Color(red, green, blue)

and is assigned to the iterColorMap with its respective iterCount key.

The RGB color generation graph for the above scheme is shown below:

Grading Criteria

Milestone 1:

Milestone 2:

Running the Test Cases

In src/test/java/(default package) right-click on ComplexTest.java or ColorMappingColorChooserTest.java and choose Run As…→JUnit Test. If you have correctly implemented the classes, you will see a green bar, indicating that all tests have succeeded.

Running the program

To run the program, right-click on Mandelbrot.java and choose Run as→Java Application. Refresh the project to see the generated image file output.png. If you open this file up in Eclipse, be sure to close it before re-running the program to see the updated version.

Submitting

When you are done with each milestone, submit the project to the Marmoset server using the SimpleMarmosetUploader Eclipse plugin (see Importing and Submitting Projects for details).

From Eclipse

Use the Simple Marmoset Uploader Plugin, by selecting the project (CS201_Assign04_Gradle) in the package explorer and then clicking the blue up arrow button in the toolbar (or right click and choose Submit project…). Enter your Marmoset username and password when prompted. Make sure your choose assign04_ms1 or assign04_ms2 as the inbox:

Choosing the inbox for assignment 4

After you submit

Very important: After you submit the assignment, please log into the Marmoset server and check the files you submitted to make sure that they are correct.

It is your responsibility to make sure that you have submitted your work correctly.