The Fractality Project
www.thirteenthshore.com


The Fractality Project

The Fractality Project is an Independent Study in Application Development, using Cocoa and OpenGL. Cocoa, Mac OS X's native development platform, uses a modified C language called Objective-C for it's internal structure, and includes a standard suite of development utilities for code building, interface building, and programmatic debugging. OpenGL is an open source graphics language that is an addition onto the C languages, which include C++ and Objective-C. Fractality uses the Cocoa platform and the OpenGL language to allow custom shaping and coloration of polygonal fractals on the screen. One of the primary goals of this project was to create a full version application to be submitted to the Apple Student Design Awards, during the World Wide Developers Conference, under the name Fractality created by Thirteenth Shore Productions.

The original version of Fractality was created using C++ and OpenGL on a Windows machine and Microsoft Visual Studio, and I found the transition from C++ to Objective-C quite difficult. One of the biggest obstacles I faced was learning an entirely new language -- Objective-C -- in a time frame that had to be large enough to become rather familiar with the concepts and subtleties of a new language, yet small enough to be able to finish a program by the April 15 deadline to the Apple Student Design Awards. While C++ relies heavily on custom structures and function calls, Objective-C relies on message passing -- something I have never come across before now. Custom structures in Cocoa's Objective-C are not as important given the entire library of ready-made structures, and thus harder to develop than those in C++. Since Fractality was built around a custom linked list idea, I had to determine whether or not to keep the custom structure, or morph it into something predeveloped in Cocoa. Ultimately I decided on keeping my custom structure, primarily because I enjoy working with my own structures in that I add functionality as needed, and thus am more familiar with the entire product.

Part of the difficulty in developing a Cocoa application was attending to the interface. Before, in C++, I had simply run the program as a console application, with important information begin displayed on the command line. In Cocoa Objective-C, however, the interface requires more specific information to be updated more often than not, and almost never on a command console. Consider two snippets of code: the first (example 1) from the early days of C++, the second (example 2) from the newest Cocoa Objective-C implementation. Both methods serve to change the iterant angle of the polygonal fractal.

Example 1, OpenGL Keyboard Function in C++

void myKeyboard(unsigned char theKey, int mouseX, int mouseY) {
    switch(theKey) {
        ... extraneous code removed ...
        case 'a': cfr->set_angle(cfr->get_angle() + 1); display_info(); break;
        default: break;
    } // end switch
    cslate->clear();
    cfr->plot();
    cslate->draw();
} // end myKeyboard


Example 2, Change Angle method in Cocoa Objective-C

- (IBAction)changeAngle:(id)sender {
    if (cF.angle != [sender floatValue]) { // check to see if value has changed
        cF.angle = [sender floatValue];
        if (cF.angle > 360) { cF.angle -= 360; }
        if (cF.angle < 0) { cF.angle += 360; }
        [iterationCoarseAngleField setFloatValue:cF.angle];
        [iterationCoarseAngleSlider setFloatValue:cF.angle];
        [iterationPreciseAngleField setFloatValue:cF.angle];
        [iterationPreciseAngleStepper setFloatValue:cF.angle];
        [geoFractal2DView setNeedsDisplay:YES];
    } // end if
} // end changeAngle


Because of this inherent difference between a console tool and a full application with a large user interface, the two methods that change the same value are completely different. While the C++ function is the OpenGL Keyboard Function (the only method of input), the Cocoa Objective-C method is a generic method that gets passed a message from any type of object (the generic typecast 'id'), which would contain a 'floatValue' to be saved into the current fractal. Additionally, while the console tool displays it's info on the command line (using 'display_info()'), the Fractality application must update the corresponding fields and sliders that are used to control it, which are the four message calls that get their 'setFloatValue' set to cF.angle, the current fractal's iterant angle.

Message passing, the basis of Objective-C, is in itself a peculiar and yet familiar method of transferring data. Instead of a C++ class having a function called with a certain amount of parameters taken (say, pointList.addPoint(x, y, z)), Objective-C has a method that is passed a message, whose name is always the name of the first parameter (and can be expounded upon; say, [pointList addPointWithXCoord:x, yCoord:y, zCoord:z]). Function calls are still accepted, being a part of the C language underbelly, but message passing is the primary tool for communication within the program. The reason for this is almost entirely internal; it allows for dynamic construction of a runtime environment, such that during a build, you can dynamically create new methods and alter old ones.

Another primary difference between C++ and Cocoa Objective-C is the emphasis on user interaction. Within OpenGL and C++, there is an Idle Function that is called whenever the application is idle. Within that function is an ideal place to put animation controls; the disadvantage is that the Idle Function is called almost every microsecond that the processor is not doing anything else, resulting in many lost CPU cycles. This is a result of the earlier C++ application being program-centric, or essentially having the program run itself while allowing the user to alter parameters. Objective-C, however, is the opposite, and much more user-centric. Instead of always allowing the program to run, Cocoa Objective-C rather builds itself off of waiting for the user to input data, and therefore having the application run from the user instead of from the program. For example, within C++, the animation is always represented by a global flag, always present, and merely recognized by the draw function to alter it's parameters (example 3). Cocoa Objective-C instead uses a Timer to call the draw function at a given interval, so that the program is not based on a global parameter (example 4).

Example 3, OpenGL Keyboard Function to toggle animation in C++

    ... extraneous code removed ...
    case '.': flag = (flag == ANIMATE) ? STALE : ANIMATE; rev = 0;
            display_info(); msTime1 = time(NULL); break;
    case '>': flag = (flag == ANIMATE) ? STALE : ANIMATE; rev = 1;
            display_info(); msTime1 = time(NULL); break;


Example 4, Toggle Animation method in Cocoa Objective-C

- (IBAction)toggleAnimation:(id)sender {
    animating = !animating;
    if (animating) {
        drawTimer = [[NSTimer scheduledTimerWithTimeInterval:0.001
                target:geoFractal2DView // Target is this object
                selector:@selector(refresh) // What function are we calling
                userInfo:nil repeats:YES] // No userinfo / repeat infinitely
                retain]; // No autorelease
        [animStartButton setTitle:@"Stop Animation"];
        [animStartMenuItem setTitle:@"Stop Animation"];
        [geoFractal2DView setNeedsDisplay:YES];
    } else {
        [drawTimer invalidate];
        [drawTimer dealloc];
        [animStartButton setTitle:@"Start Animation"];
        [animStartMenuItem setTitle:@"Start Animation"];
        refreshCount = 0; totalTick = 0;
    } // end else
} // end toggleAnimation


This also brings up one last major point. In using C++, rarely do you have to worry about memory management; garbage collection is decent, memory leaks are not common, and all in all you can forget about it. However, the subject is much more important in Objective-C. Almost all data elements that are created within a method are also deallocated when the method finishes. Hence, to retain an object such as our NSTimer (the object that calls our redraw function when the picture is animating), we must use messages such as 'retain', and then 'dealloc' at the end of our usage (in this case, an NSTimer must be 'invalidate'd before it can be released). However, we must be careful about how we retain our data structures, for if we carelessly retain them, then we create many opportunities for memory leaks, tying up precious memory in a processor-intensive application such as Fractality.

Polygonal Fractals

Example 5, simple triangular fractal created with Fractality

The concept behind polygonal fractals is similar to that of other fractals. There is an image that is repeated infinitely and, with each iteration, is modified in terms of size, orientation, and often color. In polygonal fractals, the image is a polygon, and for each successive iteration, polygons are placed on each of the vertices of the previous iteration's polygons, their angle slightly shifted, and their size diminished somewhat. For example, in a triangular polygonal fractal (example 5), the first iteration would be a single triangle (the root polygon) sitting in the center of the screen; the second iteration would consist of three triangles, each sitting at each vertex of the root triangle, and each slightly smaller and angled; the third iteration would consist of (3 triangles) * (3 vertices each) = 9 new triangles, again, each slightly smaller and angled. This allows for a simple repeating pattern that, through multiple combinations of rotation, decrease power, and polygon type, can yield innumerable results.



Example 6, simple pentagonal fractal created with Fractality


Example 7, complex quadrilateral fractal created with Fractality

To make things more aesthetically pleasing and mathematically interesting, however, you can implement a formula that allows you to alter each vertex's decrease power. For each iteration, if we denote the primary vertex to be that vertex which, if there is no angle of rotation, proceeds out of the root polygon in a straight line, then we can manipulate that primary vertex and the secondary vertices such that each decrease in size at a different rate. Hence, we declare such a formula to be a simple string, the length of which is exactly equal to the number of vertices in the polygon, and where each character is either the number 0 through 9 or the letter x. Each character n is the factor to which the decrease power p is multiplied, so the final decrease power for each vertex is p ^ n. The character 'x' denotes that no iteration be continued for that vertex. For example, say we begin with the general decrease power of p, and a formula '1xx5' (example 7). The primary vertex is always listed first, and the secondary vertices follow in counterclockwise order. So because the primary vertex has the largest decrease power p ^ 1, it descends in size the least, stringing out from the root in four long fingers, the most noticeable. The next two secondary vertices are nonexistent, because of the stated 'x'. The final secondary vertex has the ultimate decrease power of p ^ 5, so it's size decreases five times as fast as the primary vertex. Following this pattern creates a fractal flower with noticeable fingers. What's interesting to note, though, is that each polygon creates it's own fractal (as it should), and so each polygon is it's own fractal's root polygon. Therefore, there are primary vertices and secondary vertices that are associated with each polygon on the fractal.

This design of the polygonal fractal is not something that is widely discussed; in fact, I have not seen anything similar to it. It's a very simple concept, though, so I can only assume that someone else must have thought about it at some point. Nor is the concept hard to implement, and it took not long at all until I had the further ideas of the decrease power formula and a color adaptation formula. It seems that most of the attention fractals have gathered has been focused on the more complex series of Mandlebrot and Julia. Yet while this concept is deceptively simple, it can produce stunning results, especially when drawn with simple color controls, describe below. Further examples of these beautiful fractals are also below.

Color Schematics

Example 8, simple high-power polygonal fractal created with Fractality

The color scheme currently in use is a very simple one, hopefully to get more complex (as an option) when more time is allowed. Other than the simple background color, there is a root color and a tail color, both defined in RGBA. When computing iterations, the primary drawing algorithm determines where on the iterational chain it is (current iteration / total iterations) and changes the color to accommodate ( (current iteration / total iterations) * (tail color - root color) + root color). What is interesting about this color scheme is that it is based upon the number of iterations. Hence, if the engine is drawing 100 iterations of a fractal in which only 10 iterations are visible (defined as the minimum radius cutoff, greater than a two pixel radius), then the color would be primarily loaded on the root side, and you would not see much shift at all. This can be beneficial, however, when choosing to ignore the minimum radius cutoff (choosing to draw all iterations regardless of size). This slows down the drawing engine considerably, but also yields amazing results. Often in fractals of single chains (formulas like '1xxx') and an extremely high (close to 1) power of decrease (often as high as 0.999996), you can achieve high counts of iterations (upwards of 2000) and have the color congregate at points in the fractal. This is most impressive when the root and background color are the same, and the tail color has a low alpha percentage and large contrast with the root, because this allows the large majority of the fractal to not be seen until the iterations start congregating in these clusters. Then, the high count of iterations multiplies the colors together because of the alpha consistency, and these spikes of brightness appear, points of light in an otherwise light fractal.

The Fractality Application

To follow the philosophy of the platform this was designed for, there is a constant study of the user interface of this application. There will always be revisions, making it easier to use. But there are two main decisions that I like to follow. The first is that everything must be easy to use. You must be able to be intrigued in the first thirty seconds of using the application, you must be able to explore further in the next thirty seconds, and within three minutes you should be able to create simple masterpieces. Yet, the second thing to always adhere to is that the user must keep control of every aspect of the program, if he wishes. Small options must be available, such as antialiasing (instead of always having it on), redrawing the fractal and it's statistics (in the very small chance of a UI bug), and being able to control every aspect of the creation of the fractal. Working these two design ideas together is one of the hardest challenges of programming interfaces; merging the most powerful controls into the easiest of interfaces that a five year old child could use and understand. One of the smaller aspects of making it easy to use is the artistic design element. Even the simplest of applications must have a nice, aesthetically pleasing design, since nobody wants to work wonders with an ugly application. This also is a constantly updating process, one that cannot be upgraded until field experience returns results.

Some of the other features that are notable are the ability to save / load a PolyFractal as a human-readable xml file (since the entire fractal is merely a series of parameters) and to export the OpenGL screen to an image. The image export feature will use the QuickTime plugin to save the image in a wide variety of formats, including the standard TIFF and JPEG. Additionally, soon there will be the ability to render the fractal to a high resolution OpenGL buffer, which will then also be able to save through the QuickTime plugin in any format. This allows for generating fractals with enough resolution to print out on a high quality photo printer.

The Fractality Application was built with the standard Apple Development Tools, which include Interface Builder and Project Builder. Interface Builder is the main utility in building a user interface. This also took a good amount of time to learn how to handle; since there need to be so many specialized controls for Fractality, they all had to be made and understood, and eventually remade to be made better. Another aspect that I took a while to notice is that IB is best at reading the existing files and mapping them, instead of the way that I thought, where IB creates the structure and Project Builder is where you enter all the code. Unfortunately, it's quite hard to merge a new structure into a coded structure, and so lots of custom merging had to be used until I reworked my thinking. Memory management was tracked with tools like Malloc Debug and Sampler. Malloc Debug made sure that my program was not leaking memory anywhere; quite surprisingly, given my new experience with Cocoa development, it wasn't. Sampler was a big help in determining where all the time was spent in my program, which helped to speed up the animation. At one point, I used Sampler to track down a location in my program (which turned out to be a computation for an NSLog that I forgot to comment out), and fixing it jumped the animation speed from 18 frames per second to 120 frames per second.

The Fractality Structure

The structure of building the polygonal fractals has been optimized for it's needs and the Cocoa platform. Because each iteration of the fractal depends on the previous, there can be no shortchanging; every single polygon needs to be computed, even if not all are drawn on the screen. The only time saving that can be done is when fractal parts are off the screen, but that is merely OpenGL code, and takes so little time compared to generating the fractal. The structure deemed best for the situation was a classic linked list, because it included a simple dynamic structure with a customizable data type. The fractal is computed beginning with the root polygon being placed as the root node in this linked list. From there, a pointer is initialized to traverse the entire linked list (which at this point contains only one node). The pointer sees the first node and computes a polygon centered at the coordinates given by that node. After computing, the engine does three things: first, it adds those points in order to an OpenGL data structure which is to be sent to be drawn; second, it takes those points and creates new nodes along the linked list, each with center coordinates, an angle of orientation, and a radius; and third, it tells the pointer to traverse to the next node, killing the last node in the process, which is never needed again. This method of semi-recursion is continued until either the radius of a point is under 2 pixels (when the ignore minimum radius flag is off) or the last iteration is reached.

Because animation is one key feature of Fractality, engine computing time has always been a concern. Variations of this computational structure have been implemented and played with, while ultimately settling back on the original idea. The variations include not killing the last node after it's never needed again (which sometimes raised Fractality to using 200MBs of reserved RAM); not killing any node but rather merely overwriting it, in the hopes that decreasing numbers of memory allocation and deallocation would speed things up (which also ended up using up to 200MBs of reserved RAM); thinking about using prebuilt data structures, such as an NSArray or NSMutableArray, but since custom data structures are almost inherently built for the speed of the application, prebuilt ones were never seriously considered. The Fractality PointList linked list structure (example 9) is often drawing fractals with a million points or more, and at that complexity it uses only 15MBs of reserved RAM. It can draw common fractals of 5000 points at an average frame rate of over 50 frames per second, and currently has not been able to crash because of lack of memory. Fractality is built on a solid, custom built core, and the engine is well tuned for precision and speed.

Example 9, the PointList linked list structure used by Fractality

typedef struct point GeoFractalPoint;
struct point {
    // node GeoFractalPoint for use in GeoFractalPointList
    float xCoord, yCoord, zCoord; // xyz Coords of point
    float xyAngle, xzAngle, radius; // angle and radius of polygon centered at point
    GeoFractalPoint *prev; // pointer to prev node in the list
    GeoFractalPoint *next; // pointer to next node in the list
}; // end GeoFractalPoint

@interface GeoFractalPointList : NSObject {
    int size, maxSize; // size of linked list (for debugging)
    GeoFractalPoint *current; // current list iterator
    GeoFractalPoint *breakPoint; // current last stop for iterator
    GeoFractalPoint *root; // first element in the list
    GeoFractalPoint *last; // last element in the list
} // end GeoFractalPointList


Some of the elements (specifically, xyAngle, xzAngle) may seem odd in a 2-dimensional fractal structure, but that's because there may soon be a module created to generate 3-dimensional PolyFractals, which may use the same PointList structure. It seemed very easy to use those advanced variables, so I went ahead and implemented them. Given the method explanations (example 10), you will be able to see the simple linked list structure, the custom methods, and the small fact that the last node in the list is always empty; hence, the pointer *last always points to the node after the last node needed. Working with the construction of the fractal, I found it easiest this way, because then the method iteratorAtBreak always returns true after the last node is computed. Before, when *last pointed to the last node needed, then that node would not be computed because the iteratorAtBreak would return true before the last node was computed.

Example 10, the PointList method calls used by Fractality

@implementation GeoFractalPointList
- (int)size { return size; }
- (int)maxSize { return maxSize; }

- (void)addPointWithXCoord:(float)_xCoord yCoord:(float)_yCoord zCoord:(float)_zCoord
             xyAngle:(float)_xyAngle xzAngle:(float)_xzAngle radius:(float)_radius {
    if (root == nil) {
        root = [self newPointWithXCoord:_xCoord yCoord:_yCoord zCoord:_zCoord
                xyAngle:_xyAngle xzAngle:_xzAngle radius:_radius]; // and new point
        size++; maxSize++; // increment size
        root->prev = nil; // fix root prev
        root->next = [self newPointWithXCoord:0 yCoord:0 zCoord:0 xyAngle:0 xzAngle:0 radius:0];
        last = root->next; // fix last
        last->prev = root; // fix last prev
        last->next = nil; // fix last next
    } else {
        if (last->next == nil) {
            last->next = [self newPointWithXCoord:0 yCoord:0 zCoord:0 xyAngle:0 xzAngle:0 radius:0];
            size++; maxSize++; } // fix last
        // fix all points //
        last->xCoord = _xCoord;
        last->yCoord = _yCoord;
        last->zCoord = _zCoord;
        last->xyAngle = _xyAngle;
        last->xzAngle = _xzAngle;
        last->radius = _radius;
        last->next->prev = last; // fix new last prev
        last = last->next;
    } // end else
} // end addPoint

- (GeoFractalPoint*)newPointWithXCoord:(float)_xCoord yCoord:(float)_yCoord zCoord:(float)_zCoord
            xyAngle:(float)_xyAngle xzAngle:(float)_xzAngle radius:(float)_radius {
    GeoFractalPoint *newPoint;
    newPoint = malloc(sizeof(GeoFractalPoint));
    newPoint->xCoord = _xCoord;
    newPoint->yCoord = _yCoord;
    newPoint->zCoord = _zCoord;
    newPoint->xyAngle = _xyAngle;
    newPoint->xzAngle = _xzAngle;
    newPoint->radius = _radius;
    newPoint->next = nil;
    newPoint->prev = nil;
    return newPoint;
} // end newPoint

- (bool)killPoint:(GeoFractalPoint*)point {
    if (point == nil) { NSLog(@"WARNING: point to be deleted was null."); return NO; }
    if (point == root) { root = point->next; root->prev = nil; }
    else if (point == last) { point->prev->next = nil; }
    else { point->prev->next = point->next; point->next->prev = point->prev; }
    free(point); size--; return YES;
} // end killPoint

- (void)initIterator { current = root; }
- (void)initBreakPoint { breakPoint = last; }
- (bool)iteratorNext {
    if (current->next == nil) { return NO; }
    else { current = current->next; return YES; }
} // end iteratorNext
- (bool)iteratorAtBreak { return (current == breakPoint); }
- (bool)iteratorKillPrev { return [self killPoint:current->prev]; }
- (GeoFractalPoint*)iteratorPoint { return current; }
@end


This structure was the single hardest thing to port to Objective-C. Converting C++ data structures with functions to simple C structs with overlying classes was something that had to be learned, revised, and perfected. Nothing was known about Objective-C prior to beginning, and in fact nothing was known about the difference between C++ and C. Optimization quickly became a concern after implementation, and several small changes were made until it was realized that the original method (although enhanced) was the right one for the job. I've always preferred creating my own custom data structures, because they optimized perfectly for the application, and I personally know exactly what's going on, instead of having to constantly rely on a framework that gives me too many unnecessary items. Optimization will always be a noticeable concern, and there's a possibility that later down the project things might get entirely reworked again.

The Fractality Vision

Fractality is the project from Thirteenth Shore Productions that will be submitted into the 2003 WWDC Apple Student Design Awards. It will be constantly worked on before and after that, and in the possibility that it does not win this year, it will be worked on for another year and submitted again. I have firm faith that given enough time to this application, it has every opportunity to win. Most of the fundamental structural ideas of Objective-C and Cocoa have been understood, but there are so many subtleties and tricks that will take years to master. Development of Fractality will continue, and further implementations of technologies will be apparent. The long term goal of Fractality is to include many different types of fractal generation, including the famous Mandlebrot / Julia geometric fractal ideas, and chaotic random fractals. For this reason, the polygonal fractal engine was coded in a structure separate from the primary drawing engine, and separate from the main application, such that the 'PolyFractal' bundle can be separated and Fractality itself be modified to accept multiple bundles, and hence display multiple types of fractals. The current bundle is fully named 'PolyFractal2D' in the hopes that someday there will be a 'PolyFractal3D' implementation of these polygonal fractals, because the design would be the same and the conversion to 3D so similar.

Be sure to sign up for updates from Thirteenth Shore Productions. Fractality will someday be a large functioned application, and recent development has spurred my creativity and interest in development once more. There will be many wonderful things to come!



Example 11, simple high-power hexagonal fractal created using Fractality










www thirteenthshore com
Keep up with the times! Stay notified of major updates: Privacy?
  Donations are always welcome -- they help keep me programming and my programs free
2256 hits since August 2003
all works are © John Gale for the 21st century.
please send all comments and suggestions to johngale@smadness.com