Visualizing Fractals

• Download Fractal_Runtime.zip - 2.6 MB
• Download source - 608.5 KB

Introduction

The book "Fractal Programming in Turbo Pascal" by Richard T. Stevens, ISBN 1-55851-106-7, formally introduced me to the wonderful and mysterious world of fractals. My only prior encounter with them was from a video game by Lucasfilm called "Rescue on Fractalus", which I still remember fondly to this day. The book came with a source disk, valued at $20 in 1994, containing the source code.

Rescue on Fractalus

Thanks to modern emulators of the Commodore 64, I am still able to play Rescue on Fractalus today, which fondly reminds me of yesteryear.

At the time, the PCX format was the prevailing format for images. When I opened the book and started reading, a whole new world was opened up for my personal investigation. The book gives a neat historical perspective about the prevailing currents in physics, philosophy, and computer systems which were brought together, kicking and screaming, to study chaos theory.

Fractals

Nevertheless, by page 19, the term fractal was defined. "Fractal - A description of all curves whose Hausdorff-Besicovitch dimension is greater than their Euclidian dimension." The introduction goes on to explain this concept with an example. "To grasp the concept, start drawing a line on a piece of paper and wind it around the sheet, never crossing itself, until you have filled the page. Euclidian geometry says that this is still a line, but our visual senses and intuition tell us this is much more, that it is two dimensional." - Stevens pg. 25

Software Implementation

The software that is being presented, along with source code, generates both the Mandelbrot and Julia fractal types. The Julia fractal type is another expression of the equation that generates the classic Mandelbrot set. "The Mandelbrot set forms a sort of map of all possible Julia sets." Stevens - 305. If you look at the Julia set points of interest and zoom the Mandelbrot into those coordinates, then with enough magnification the image of the Julia set will start to emerge. The software allows you to not only visualize the fractal, but animate the color palette and optionally record the animation as an AVI file. For the curious, see AVI.h and AVI.cpp in the source code. There is source code that wraps the creation and access of a DIBSECTION which are device independent bitmaps. AVIs record best at lower resolutions. A 320 x 200 resolution fractal will record well.

The book launched into a more practical analysis of the families of equations. Fractals have the property of self similarity. This self similarity can be understood with geometry and geometric substitution. Creating self similarity uses two parts, the generator and the initiator. The geometric shape becomes the generator. Now we replace each line segment of the generator with another set of line segments that have the exact length. These line segments are called the initiators. There can be other geometric shapes. This process is repeated an infinite number of times. This is where the definition of the Hausdorff-Besicovitch is comes into play. Having "N line segments, each of length r, where r is a fraction of the line segment being replaced... It can then be shown that the Hausdorff-Besicovitch dimension, D, of the resulting fractal curve is: D = log N / log (1/r)" - Stevens pg. 28-29.

Mandelbrot is based on the equation Zn+1 = Zn² + c. In this equation, as n approaches infinity, the value of Z will either tend to infinity or stay within the orbit of X² + Y² < 4. Z and C are complex numbers and X and Y are derived from the real and imaginary parts of this equation. The values that stay in orbit are the points that are in the set. Interestingly enough, it is the visualization of the values that are not in the set which is most commonly recognized as the Mandelbrot set, when it fact is the not-Mandelbrot set. Paraphrased from Wikipedia article on the Mandelbrot set.

This program uses the MFC classes to build the basic structure of the program. This system uses the MDI architecture. This allows each visualization of the equation to exist in its own document with its own view. The program also allows selecting rectangular regions of the view to either zoom in, place some text, or place an image over the fractal, and allowing differing levels of transparency to blend in with the fractal. Decorative text can be edited and moved about the screen by grabbing it with the mouse when the cursor changes to a hand. Background images can be incorporated into the fractal when it is rendered. There are two options: blending with the base, a coordinate that doesn't move to infinity, or in the "fractal". Zooming into the Julia set is a little more restrictive. As long as the rectangular region includes the Julia focal point, zooming can be accomplished. There is also a 2x zoom present in a context sensitive menu for Julia fractals. Further, each visualization can be saved as a document that can be reloaded or as an image in an image file format. The program doesn't restrict you to the resolution of your monitor. You can create a image of up to 28,800 x 16,200 pixels. You can scroll around the document to see the detail of such an image. You can also get the "big picture" by zooming out to see such an image in its entirety, as it is fit to the view of the document. The coordinates are echoed in the status bar and from any Mandelbrot fractal, you can generate a Julia set from the current cursor location. Right click in the Mandelbrot fractal and select Julia Set.

There are many zooming options. You can zoom directly to a dragged out rectangular region. You can fly into that region by giving the number of jumps to take while zooming in. You can also do a small zoom or a continuous small zoom. A small zoom will zoom in by the smallest increment possible. A continuous small zoom will continually zoom this way letting you fly into the fractal.

Colorization

There are colorization options which allow assigning and editing colors either before or after the fractal has been rendered. Editing color is accomplished in the new fractal dialog by pressing the edit color button and double clicking the color to change. Post-render color editing is done by right clicking on the rendered fractal and choosing edit color from the context menu. This edited color modifies the palette of the new fractal dialog that created the fractal. The basic application of color uses the escape orbit count modulo the number of colors to represent a value from 0 to the number of colors desired in the fractal. This is used as the red, green, and blue values of color. The result is a black and white gradient. Further, offsets from each color channel's value can be applied, giving the image a nice color visualization. The screens gradient bar will show you what colors will be present in your fractal. A random button generates a random scaling for each channel. The dialog also allows six colors to be chosen to represent a set of colors in the gradient. When the gradient check box is checked, the random button creates a random gradient with the optional scaling added. The orbits can be colored based on occurrence. Sorting by lesser orbits assigns the palette in the order of least occurring orbits to most occurring. Sorting by greater assigns the palette from most occurring orbits to least occurring. You can edit a color after the fractal has been rendered to change it. This color will be saved with the fractal document and reloaded next time the document is loaded. You can restrict which color channels are present by checking the red, green, and blue check-boxes. The base color, or the last color, always represents a value that is the solution of the set. The orbits never escape. You can customize this base color by checking the option and selecting the color. Further, it is possible to select a background images to blend through where the base and fractal colors would be. Nice effects can be achieved with this option. Examples are rendering a fractal on water or sky. The opacity is entered as a percentage from 0 to 100, where 0 doesn't blend at all and 100 shows only the image. Values in between will cause both the image and the portion of the fractal to be combined.

Angular Decomposition

There are colorization options which allow coloring using angular decomposition. Angular decomposition takes the X and Y value of the function and converts it to an angle. This angle is then scaled to the number of iterations, which determines the color count, and that value is used as the color. Some very interesting results can be generated using a combination of normal coloring along with angular decomposition. To make a binary decomposition, choose a 2 color palette. Try a 2 color, 16 iteration, binary decomposed fractal.

Detail of a Fractal

The detail of a fractal is largely controlled by the number of iterations of the algorithm. The number of iterations that it takes to detect that a point is not in the solution is called the escape orbit. The greater the upper bound of the escape orbit testing, the finer the detail of the fractal. In this system, as you zoom into coordinates, more iterations can produce more detail. Consequently, if you are zoomed in to a small coordinate space, less iterations will produce much less detail. Sometimes finding the right balance between iterations and coordinates is an art and produces extremely interesting pictures. See the next two pictures. The fractal document which creates them is bundled with the EXE zip download. For Julia fractals, the best images are usually generated with fewer iterations. The number of colors partitions the iterations into groups of like colors. When the number of colors is the same as the number of iterations, then each iteration has its own color.

Stair Step and Smoothing

The system lets you add a stair step effect to a fractal as well as smooth any fractal using a menu option. The smoother is a low pass filter that uses the average color of the 3 x 3 area around a pixel for the new pixel color. Stair stepping enhances the areas between colors to give a 3D like effect. On the new fractal dialogs, it can be entered as a value from 0 to 10. 0 is equivalent to not being used.

The basic working parts are a main menu that lets you create, save, print, and load documents. It lets you zoom out and see the big picture with the view menu in case you want to simulate a screen the size of Texas. In each document, you can hold down the left mouse button and draw a rectangle around an area that you want to zoom to. Those are the basic working parts of the system, so now let's look at some code!

Figure 5 - The class architecture has 3 main classes

CFractalBase - Base class that keeps the parameters

// Class for calculating the mandelbrot set
class CFractalBase
{
public:
    CFractalBase(CFractalParm FractalParm);
    virtual ~CFractalBase();
    virtual void operator() (int RowBeg,int RowEnd);

protected:
    virtual void Apply(int Iteration,int Column,int Row);

protected:
    CFractalParm m_FractalParm;
};

CFractalCanvas - Derived class that puts pixels to the DIBs

// Base derived class for holding the canvas (DIB + colors)
class CFractalCanvas : public CFractalBase
{
public:
    CFractalCanvas(CFractalParm FractalParm,CDIBFrame * pBaseDIB,
                   CDIBFrame * pFractalDIB,CDIBFrame * pDisplayDIB);
    virtual ~CFractalCanvas();
    std::vector<CIteration> GetIterations();

protected:
    virtual void Apply(int Iteration,int Column,int Row);

protected:
    CDIBFrame * m_pBaseDIB;
    CDIBFrame * m_pFractalDIB;
    CDIBFrame * m_pDisplayDIB;
    std::vector<std::vector<BYTE> > m_RGB;
    int m_nMaxIterations,m_nMaxCalc;
    bool m_bModulo;
    std::vector<CIteration> m_Iterations;
};

CRenderMandelbrotFractal - Derived class that calculates the Mandelbrot equation

// Class for rendering the mandelbrot fractal without angular decomposition (main case)
class CRenderMandelbrotFractal : public CFractalCanvas
{
public:
    CRenderMandelbrotFractal(CFractalParm FractalParm,
           CDIBFrame * pBaseDIB,CDIBFrame * pFractalDIB,CDIBFrame * pDisplayDIB);
    virtual ~CRenderMandelbrotFractal();
    virtual void operator() (int RowBeg,int RowEnd);
};

Each fractal type is derived in the above scheme. A rendering class is derived from the canvas class and the function operator is implemented. The rendering class is common to methods and the Apply() method has a common implementation.

Multithreading

Because the main corpus of the work revolves around multiple threads, and so much already exists on the MFC MDI architecture, and the math and equations of the Mandelbrot set, I will only focus on this aspect of the code. Hopefully, the reader will trace through the code during execution, setting breakpoints, so that they can "go with the flow" so to speak. There is one class that wraps the multithreading aspect of the system. This is the CDriveMultiThreadedFractal class.

This class is a CWinThread derived class that drives the work for rendering a set of points in the set. This class is the director of calculation; it drives the actual work. The thread driver is initialized with a CFractalBase class which is the base class of the polymorphic system that makes it easy to add new fractal types. (There is more work wiring it up to the UI but that is not too hard either.) The system determines how many total threads of execution are available to do work and then partitions the work based on row partitions. This follows the design pattern of a parallel for loop. This multithreading patter is surprisingly effect for mathematically based problems where the work can be split and combined. For debugging purposes, or just to make watching the flow in the debugger easier, the system is reduced to one thread of work. In release builds, the system scales up to the maximum number of threads possible.

The work is dispatched to the threads of execution. For each CPU in the system, two threads of work are created. The O/S manages which CPU gets the thread of execution. The work is divided up based on the height of the image to be rendered. For a single core system, there will be two threads of execution. Each thread gets 1/2 of the image. For a dual core system, each thread gets 1/4 of the image. This is the benefit of multithreaded design. Code reuses happen concurrently.

Figure 7 - The driver class that delegates the work

// Driver thread that carries out the function
class CDriveMultiThreadedFractal : public CWinThread
{
	DECLARE_DYNCREATE(CDriveMultiThreadedFractal)

private:
	CDriveMultiThreadedFractal() : m_phHandle(NULL) {};

public:
	CDriveMultiThreadedFractal(HANDLE * phHandle,CFractalBase * pFractal);
	virtual ~CDriveMultiThreadedFractal();
	virtual BOOL InitInstance();
	virtual BOOL PumpMessage();
	virtual int ExitInstance();

protected:
	HANDLE m_hPump;
	bool m_bPumpMessage;
	HANDLE * m_phHandle;
	CFractalBase * m_pFractal;

public:
	CFractalBase * GetFractal() {return m_pFractal;}

protected:
	DECLARE_MESSAGE_MAP()

protected:
	afx_msg void OnDoWork(WPARAM wParam,LPARAM lParam);
	afx_msg void OnEndThread(WPARAM wParam,LPARAM lParam);
};

When I first started using these kinds of threads, I would occasionally run into a problem where a message wouldn't get dispatched and the worker function would not get called. What I learned was that the thread's message pump hadn't been started and the messages I was posting to the thread was not able to be dispatched. To solve this problem, I overrode PumpMessage and had it signal when it was ready. The constructor waits for the signal before exiting. This means that once the constructor returns after defining an instance of the thread object that it can immediately have messages posted to its message pump. This is a nice way to handle separation of concerns. The thread delegates the work but it doesn't do anything but wait for the work to be done. It would have been possible to combine this class with the class that does the work but then the separation of concerns would be lost and the code would become harder to maintain and harder to build up for future design ideas. To use this object, we define custom thread messages, like WM_DOWORK, and then post these messages to the thread. See the code in Figure 7. Each function that handles a custom message is declared the same way using the form:

afx_msg void OnFunction(WPARAM wParam,LPARAM lParam);

The message map of the thread maps these messages to the function of its interest. Supplemental information can be passed using the WPARAM and LPARAM variables.

// These functions are called by PostThreadMessage
BEGIN_MESSAGE_MAP(CDriveMultiThreadedFractal, CWinThread)
    ON_THREAD_MESSAGE(WM_DOWORK,&CDriveMultiThreadedFractal::OnDoWork)
    ON_THREAD_MESSAGE(WM_ENDTHREAD,&CDriveMultiThreadedFractal::OnEndThread)
END_MESSAGE_MAP()

void CDriveMultiThreadedFractal::OnDoWork(WPARAM wParam,LPARAM lParam)
{
    // Do the work
    int RowBeg = (int)wParam;
    int RowEnd = (int)lParam;
    try
    {
        // Carry out the work for this range
        m_pFractal->operator()(RowBeg,RowEnd);
    }
    catch (...)
    {
    }

    // Signal completion
    HANDLE & hHandle = *m_phHandle;
    SetEvent(hHandle);
}

void CDriveMultiThreadedFractal::OnEndThread(WPARAM wParam,LPARAM lParam)
{
    // Delete the work object
    if (m_pFractal)
        delete m_pFractal;

    // End the thread
    PostQuitMessage(0);
}

In order to do the work, a factory must exist that can house the workers. We know in advance how many worker threads we have so we make a factory that can have this many workers.

// Construct the factory that does the work
CDriveMultiThreadedFractal ** ppDriveMultiThreadedFractal = 
                              new CDriveMultiThreadedFractal * [nTotalThreads];

Now we want to create our workers. Our workers can be any of the types of fractals we support since we are using a common base class and interface representing how we do the tasks.

for (int iHandle = 0;iHandle < nTotalThreads;++iHandle)
{
    // Construct the objects that do the work
    CFractalBase * pMultiThreadedFractal = NULL;
        if ()
            pMultiThreadedFractal = new Fractal1();
        else if ()
            pMultiThreadedFractal = new Fractal2();
        else if ()
            pMultiThreadedFractal = new Fractal3();
        etc...

Now we construct our place of work in the factory and place our workers in their workspace to get them ready to start working on their task.

// Construct the Fractal thread driver
CDriveMultiThreadedFractal * 
      & pDriveMultiThreadedFractal = ppDriveMultiThreadedFractal[iHandle];
pDriveMultiThreadedFractal = new CDriveMultiThreadedFractal
                                 (&arrReadHandle[iHandle],pMultiThreadedFractal);

Now we dispatch the work to our workers and wait for them to finish their task:

// Process the number of segments that make up the Fractal
int MRPT = MR / nTotalThreads + 1;

// Process the number of threads of work
for (int iThread = 0;iThread < nTotalThreads;iThread++)
{
	// Set the range of rows to process
	int nBegRow = iThread * MRPT + 1;
	int nEndRow = min(nBegRow + MRPT - 1,MR);

	// Perform the work for this range
	CDriveMultiThreadedFractal * pDriveMultiThreadedFractal = 
                                    ppDriveMultiThreadedFractal[iThread];
	pDriveMultiThreadedFractal->PostThreadMessage(WM_DOWORK,nBegRow,nEndRow);
}

// Wait for all the work to complete for this set of ranges, the driver signals these events
WaitForMultipleObjects(nTotalThreads,&arrReadHandle[0],TRUE,INFINITE);

The message map handles two significant thread messages. It handles the work message and the quit message. The messages themselves are declared like the following:

#define WM_DOWORK (WM_APP + 100)
#define WM_ENDTHREAD (WM_APP + 101)

It is important to declare them as values beyond WM_APP up to WM_APP + 0xBFFF.

The rest of the code is based around a generic implementation that dispatches units of work to the object that it holds. The great thing about this design pattern is that a generic multi-threaded driver class like this can be adapted to delegate work to any object that implements the function operator. For my special purpose, the function operator works on a range of value that represent portions of the equations I want to calculate. A better programmer than I could get clever and templatize this driver class to hold an arbitrary object of type T and use it as a work factory design pattern. Other ways I use this design pattern are in multi-threaded processing of image data. The CColorOp class demonstrates this pattern again.

Updates

• Uploaded to Git. https://github.com/andybantly/MFC-Fractal
• 20^th September, 2017 - Fixed a bug in orbit trapping
• 25^th June, 2016 - Added small zoom and continuous small zoom. Small change to file format for image embedding as a default for easier sharing of documents with someone who may not have the image(s) that are added to the documents.
• 18^th June, 2016 - All Fractal types included with source code. Added Picture box for images with support for a transparent color. Picture and text box resizing. Open multiple documents using a new class derived from CDocManager. Fly into works much more smoothly and is tied into the message pump. Bug fixes and file format change.
• 24^th October, 2013 - Added orbit trapping (pick over stalks) to the fractal creation dialog
• 9^th May, 2013 - Added a PayPal donate button
• 5^th May, 2013 - Fine control over divergence testing in the equation AX²+/- BY² < Bailout Radius.
  • Mode 1 is AX² + BY² < R.
  • Mode 2 is AX² - BY² < R.
  • Mode 3 is BY² - AX² < R.
  • Mode 4 is |AX² - BY²| < R.
• 3^rd May, 2013 - Full color editing either before and/or after the fractal has been rendered.
• 19^th April, 2013 - Improved performance of Buddhabrots
• 18^th April, 2013 - Added Buddhabrot and Anti-Buddhabrot fractals. Buddhabrot looks wonderful with a height of 4096 and the colors and iterations set to 8192 or more. Warning, it will take a lot of time to render!
• 14^th April, 2013 - Updated source code, see below
• 13^th April, 2013 - Performance enhancement
• 8^th April, 2013 - Added Mandelbrot Phoenix Version 2 fractal.
• 7^th April, 2013 - Added Julia Phoenix fractal. The Julia fractal dialog allows manual editing of the bounding coordinates which allow you to manually zoom into interesting coordinates.
• 6^th April, 2013 - Added Julia Dragon fractal
• 6^th April, 2013 - Bug fix on palette selection of angular decomposition when the base color was fixed to a color that shouldn't have occurred in the regular palette during rendering
• 5^th April, 2013 - New scheme too color based on angular decomposition which looks much more natural and mathematically pleasing
• 4^th April, 2013 - First binary only update of the system with Dragon and Phoenix Mandelbrot like curves. Fly in zoom when zooming in the existing document. Updates to the bundled documents including 4 interesting Dragon curves. See Dragon.frc, Dragon II.frc, Dragon III.frc and Dragon IV.frc. Note - these aren't compatible with the existing source code.
• 14^th April, 2013 - Updated source code to the enhanced version but only with Mandelbrot and Julia. Other types are only available in the binary version. Source code contains coloring bug fixes and enhanced class architecture for optimized rendering.
• 4^th April, 2013 - Zoom in existing document bug fix. Last source code update.
• 3^rd April, 2013 - Algorithmic change in the calculations and application of colors.
• 1^st April, 2013 - Editing colors and text. Separation of the number of colors from the number of iterations.
• 22^nd November, 2012 - Save color animation as an AVI file
• 20^th November, 2012 - Change the stair step color and faster, smoother color animation
• 12^th November, 2012 - Text can now be drawn without a background color
• 11^th November, 2012 - Addition of adding decorative text to the fractal
• 4^th November, 2012 - Fixed a bug in saving and loading documents with embedded images
• 3^rd November, 2012 - Improved blending so that the base color and fractal colors could be optionally blended with images at different level of opacity (alpha-blending)
• 23^rd June, 2012 - Thread stability. I discovered that not all CPUs liked the code that performed thread clean up so there are some minor adjustments to the logic after the WM_ENDTHREAD message is posted to the threads message pump.
• 15^th April, 2012 - 3D Effect and Image smoothing
• 12^th April, 2012 - Colorization based on angular decomposition
• 10^th April, 2012 - More animation options
• 8^th April, 2012 - Addition of the ability to animate the color palette. See the low-res video ColorBleed.mp4.
• 7^th April, 2012 - Addition of Julia Fractal Type and the ability to render it from a point on the Mandelbrot. Also added the ability to set a background image to show through at the base color.