Our goal is the real-time animation of the Mandelbrot and
Julia Sets. This experimental applet
has been developed from the ground up to incorporate fixed
point mathematics and double buffering techniques.
The Normalized Iteration Count Algorithm (NICA) is used to
provide smooth colour imaging.
The Orbits feature is offered to provide a glimpse into the dynamics of
iteration.
Premise:
M. Weldon
Doesn’t it frustrate you when you’re watching a flash movie on a computer
that you can just tell is too slow, or when your playing a 5v5 Deathmatch in
Unreal
Tournament
when the frame rate drops to 3 per second and last thing you see is a rocket
in flying towards your face, or when a financial simulation needs to be done
but
it’s going to take 4 hours and your meeting is in 1. Why can’t some of these
things work faster?
When Benoît Mandelbrot first looked at this shape that would immortalize his name, he could not have prepared himself for the never-ending complexity he would find on its edges. It was the first time a mathematician could ever call his very own creation “Indescribably Beautiful,” a privilege normally reserved for poets and artists. The image that is immediately visible in the left panel of the applet is known as the Mandelbrot Set. The Mandelbrot Set is a very famous mathematical shape that has inspired mathematicians around the world to turn their monitors into canvases and has shaped the global computer science community.
To create this object you take points on the Complex Plane, and iterate them through the feedback formula z=z2+c where c is a constant equal to the point in question, and z starts at zero. The number of iterations it takes for the value to become greater than 2 in magnitude will directly correspond to a color palette. If a point never escapes in a given number of iterations, it is colored black. For every pixel in a frame you need to map it to a complex number (with decimals), iterate it through the formula z=z2+c an uncertain number of times, calculate what color it should be based on the iterations it took to escape, then calculate it's actual color based on the NICA, and finally animate it. Due to the enormous number of calculations needed to animate even a few points on the Set, efficiency becomes necessary for reasonable speeds. The uniqueness of this applet, lies in the simplicity of its implementation and the use of what is known as fixed point mathematics. Google the word Mandelbrot and you can find fractals at a dime-a-dozen, but fixed point mathematics has never been widely used, and there is very little information about this abstract idea available, but when used, it optimizes speed by eliminating operations with heavy-duty floating point numbers, which, in assembly level programming, take significantly more time to do calculations with. There are of course limits, but consider this: Java's primitive type, int, has a range from -2,147,483,648 to 2,147,483,647. If you know you are working with numbers less then 100, you have over 2 billion possible combinations of your storage being wasted. The philosophy behind our project is this, we deal with numbers (usually) less than 16 in the Mandelbrot Set, meaning, using the int type, we have at least 20 bits at any given time to use for granularity, and using old-fashioned, grade 3 and 4 addition and multiplication, (the kind where you pop the decimal back in after the math) we can implement a clean fast mathematical structure to do our Mandelbrot calculations. As a result, we can animate the Mandelbrot in real time and improve performance at least 2-fold.
A second part of our philosophy lies in modern day computing and portability. For the last 30 years software developers have had the luxury of companies like Intel developing new and more powerful processors to handle layered, complex, and bloated software. There was little incentive to maximize software efficiency because you could rely on cheap, limitless hardware improvements. This is the exact same attitude that, as humans, has gotten us into financial and environmental trouble before; we spend/waste so much because we can and it’s convenient and we don't worry about consequences until later, but when later comes along we end up not having the capacity or resources to handle our bad habits. Well, now with the focus in the technology industry being on the portable platforms such as Android, and the Blackberry and iPhone OS’s, we no longer have desktop computer resources, so we need to go back to square one, and look at how we can improve the basics before we consider trudging on with possibly clunky software. This is the motivation for our use of fixed point mathematics; it’s clean, it’s fast, it’s efficient. It can’t be beat.
Normalized
Iteration Count Algorithm: C. Black
The Normalized Iteration
Count Algorithm (NICA) is an algorithm used in the painting
of the Mandelbrot Set. The algorithm represents a modification of the Escape
Time Algorithm (ETA), in which points are coloured based on the number of iterations
taken to reach the escape magnitude of 2. The ETA, while being
simple to implement, creates distinct bands of colour that can detract from the
overall appearance of the Set. The NICA takes the number of iterations
needed to escape, and subtracts from it the double logarithm of the magnitude
of z. This modification means that, to a large extent, the colour of a
point is still the same as it would be using the ETA, but the
point’s
growth is now factored in as well, with the double logarithm reducing the growth
of z, which is of the order of double exponential, down to a linear level. This
algorithm creates a continuous set of values for the points on the Argand Plane,
which can then be used to colour the Set and the surrounding area continuously,
as opposed to the ETA, which creates discrete coloring.
Julia
Set: R. Ng
Similar to the Mandelbrot Set, the Julia Set follows the same iterative formula
z=z2+c, where this formula can never reach a magnitude greater than
2.0. The same escape time painting method is used in the Julia set too. However,
in
this case the Julia Set is restricted by the bounds of:
-2.0 <= Re(z) <= 2.0 and -2.0 <= Im(z) <= 2.0
The formula also goes through a bit of change, in that c is a constant
value
and z is the point on the Argand plane. That is why when you mouse over
each
point in the Mandelbrot Set; it produces a unique Julia Set on the right screen.
In the Julia Set, the fractal is generated by taking every value of the screen
coordinate and converting it into a complex number. It is then run through the
formula described above except that c is a constant complex number. Like
the Mandelbrot Set, the number of times the iterative formula is called before
it
escapes out of bounds, determines the colour of the pixel in the Julia Set.
Javadoc
and Applet Development: S. Tsuji
Interested viewers are invited to review the documentation for
our Mandelbrot class. Java applets are the next step above java applications.
Applets can easily be uploaded onto the internet, thus allowing programmers to
safely share their code with the billions of other people surfing the World Wide
Web. But perhaps the greatest advantage of applets is not that they can be uploaded
onto websites but that with the creation of JApplet, GUI interfaces can be easily
added to the applets. This allows users to easily manipulate and test out the
programs and allows java application to be presented in an aesthetically pleasing
way (Instead of the boring console). Another useful feature is that java applications
can easily be converted into an applet. The only required changes in the code
are the removal of the main method to be replaced with an init method (The method
that initializes the applet) and generally the creation of a paint method (Used
to create the initial graphics in the applet). Overall, applets are one of the
main ways for java programmers to share their code with the world and to create
applications that require user input.
Orbits:
M. Weldon
Visualizing the behavior of complex points on the Mandelbrot and Julia sets
is incredibly difficult. There is too much math involved to appreciate how
the points move across the Argand plane. This is why we implemented orbits
in our applet. The orbits of a complex point show how a point will struggle
to escape the set, and will either ultimately fail, and get included in the
set of black points, or succeed and add to the infinite spectrum beyond the
coastline of the Mandelbrot Set. The very interesting orbits lie close
to the edges of the set, as they are the points who will be very close in escaping
but will miss the mark.
Julia
orbits are also fascinating to look at, in a Julia set with a high-magnitude
c-value, the orbits are huge and random, because most points will escape.
But, on the simpler sets with more black, orbits will be intricate and snake-like
it almost appears like a worm trying to escape an apple. The orbits are one
of the best ways to appreciate the Mandelbrot and Julia Sets, because they
really reveal the dynamic of feedback mathematics, the real time implementation
also allows one to see the subtle difference between side-by-side points, that
normally
get
lost in a sea of black, when really they have the most interesting orbits.