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.
The Actual Source Disk
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
A Buddha
A Mandelbrot like Dragon fractal
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.
Figure - Mandelbrot Sample generated with the software
Figure - Julia Sample generated with the software
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.
Figure - Sample generated with the software using the Blend options (FieryWater.frc in Executables.zip)
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.
Figure - Zooming in
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.
Figure - Zoom to Coordinate
Figure - Small Zoom and Continuous Small Zoom
Figure - Context sensitive menu
Figure - Grabbing Text
Figure - Drag out a text box
Drag out a picture
Choose an image file and option for a transparent color
Image is overlaid over the fractal with the given opacity
The image can be dragged around, resized, edited, and deleted. The file format only stores a shallow link to the file. In the future, the image will be embedded in the document.
Figure - Text Editor
Figure - Decorative Text
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.
Figure - Angular Decomposition based coloring
Figure - The New Fractal dialog
Figure - A fractal with a background image
Figure - The Edit Colors Dialog
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.
256 Iterations
64 Iterations in a Julia fractal
4096 Iterations
Orbit trapping - The system lets you do orbit trapping on X and Y values producing images like the following. Enable the Trap X and Y checkboxes at runtime for more information.
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 smooth menu option
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!
Before stair stepping
After stair stepping
After smoothing
Figure 5 - The class architecture has 3 main classes
CFractalBase - Base class that keeps the parameters
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
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 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
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.
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)
{
int RowBeg = (int)wParam;
int RowEnd = (int)lParam;
try
{
m_pFractal->operator()(RowBeg,RowEnd);
}
catch (...)
{
}
HANDLE & hHandle = *m_phHandle;
SetEvent(hHandle);
}
void CDriveMultiThreadedFractal::OnEndThread(WPARAM wParam,LPARAM lParam)
{
if (m_pFractal)
delete m_pFractal;
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.
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)
{
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.
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:
int MRPT = MR / nTotalThreads + 1;
for (int iThread = 0;iThread < nTotalThreads;iThread++)
{
int nBegRow = iThread * MRPT + 1;
int nEndRow = min(nBegRow + MRPT - 1,MR);
CDriveMultiThreadedFractal * pDriveMultiThreadedFractal =
ppDriveMultiThreadedFractal[iThread];
pDriveMultiThreadedFractal->PostThreadMessage(WM_DOWORK,nBegRow,nEndRow);
}
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
- 20th September, 2017 - Fixed a bug in orbit trapping
- 25th 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.
- 18th 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.
- 24th October, 2013 - Added orbit trapping (pick over stalks) to the fractal creation dialog
- 9th May, 2013 - Added a PayPal donate button
- 5th May, 2013 - Fine control over divergence testing in the equation AX2+/- BY2 < Bailout Radius.
- Mode 1 is AX2 + BY2 < R.
- Mode 2 is AX2 - BY2 < R.
- Mode 3 is BY2 - AX2 < R.
- Mode 4 is |AX2 - BY2| < R.
- 3rd May, 2013 - Full color editing either before and/or after the fractal has been rendered.
- 19th April, 2013 - Improved performance of Buddhabrots
- 18th 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!
- 14th April, 2013 - Updated source code, see below
- 13th April, 2013 - Performance enhancement
- 8th April, 2013 - Added Mandelbrot Phoenix Version 2 fractal.
- 7th 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.
- 6th April, 2013 - Added Julia Dragon fractal
- 6th 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
- 5th April, 2013 - New scheme too color based on angular decomposition which looks much more natural and mathematically pleasing
- 4th 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.
- 14th 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.
- 4th April, 2013 - Zoom in existing document bug fix. Last source code update.
- 3rd April, 2013 - Algorithmic change in the calculations and application of colors.
- 1st April, 2013 - Editing colors and text. Separation of the number of colors from the number of iterations.
- 22nd November, 2012 - Save color animation as an AVI file
- 20th November, 2012 - Change the stair step color and faster, smoother color animation
- 12th November, 2012 - Text can now be drawn without a background color
- 11th November, 2012 - Addition of adding decorative text to the fractal
- 4th November, 2012 - Fixed a bug in saving and loading documents with embedded images
- 3rd 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)
- 23rd 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. - 15th April, 2012 - 3D Effect and Image smoothing
- 12th April, 2012 - Colorization based on angular decomposition
- 10th April, 2012 - More animation options
- 8th April, 2012 - Addition of the ability to animate the color palette. See the low-res video ColorBleed.mp4.
- 7th 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.
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.