home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / pc / FAQSYS18.ZIP / FAQS.DAT / MANDEL~1.TXT < prev    next >
Encoding:
Text File  |  1996-08-18  |  8.9 KB  |  245 lines
  1.  
  2. Even if the Mandelbrot-Set is perhaps the bestknown fractal in the world,
  3. there is not much information on what it is and how to make it. In this
  4. page I will try to make you understand the simple theory behind the
  5. Mandelbrot-Set, and even show you a simple Pascal-program that calculates
  6. the fractal. Hope you enjoy it!
  7. ---------------------------------------------------------------------------
  8. The Mandelbrot-Set is made by the simple mathematical expression
  9.  
  10. Z(n) = Z(n-1)^2 + C
  11.  
  12. The problem is that the constant C and the function Z are complex numbers..
  13. (That is, they have a 'real' part (The numbers we normally use) and an
  14. imaginary part (Numbers multiplied by the squareroot of -1, represented by
  15. an 'i' after it) ). We use to say that C = a + bi
  16. ---------------------------------------------------------------------------
  17. When calculating the Mandelbrot-Set, you use the x-axis as the 'real'
  18. value, and the y-axis as the 'imaginary' value.
  19. ---------------------------------------------------------------------------
  20. It is easy to prove that nothing of the Mandelbrot-Set is located outside a
  21. circle with origin (0,0) and radius 2. (Check out fig-1.1)
  22.  
  23. [Image]fig-1.1
  24.  
  25. What you do when calculating the Mandelbrot-Set, is to iterate the function
  26. (calculate the function several times) for every pixel on screen, and set
  27. the color of the pixel according to how many times you had to iterate.
  28. The Mandelbrot-Set is actually the big, one-colored thing in the middle of
  29. the figure. When iterating the function there, you can see that the value
  30. increases and decreases chaotic, and never will increase to infinity. To
  31. get out of the calculating-loop, you have to set a maximum number of
  32. iterations. The routine will be something like this:
  33.  
  34. FOR EACH pixel:
  35.   REPEAT
  36.     CALCULATE Z(n) = Z(n-1)^2 + C
  37.     iterations = iterations + 1
  38.   UNTIL value = infinite  OR iterations > max_iterations
  39. SET COLOR = iterations
  40.  
  41. The only problem above should be the calculation.. How do we calculate the
  42. values ? How is this 'Z(n)'-function ???
  43. As I said, Z(n) = Z(n-1) + C. In Mandelbrot-Set, Z(0) = 0. That means:
  44. Z(1) = C
  45. Z(2) = C^2 + C
  46. Z(3) = (C^2 + c)^2 + C and so on..
  47.  
  48. I also said that C = a + bi. You then get:
  49. Z(0) = 0
  50. Z(1) = a + bi
  51. Z(2) = (a + bi)^2 + a + bi
  52. Z(3) = ((a + bi)^2 + a + bi)^2 + a + bi .....
  53.  
  54. ---------------------------------------------------------------------------
  55.  
  56. So, what is (a + bi)^2 ? Everyone should know that (x+y)^2 = x^2 +2xy + y^2
  57. We get the same thing: (a + bi)^2 = a^2 + 2abi + bi^2
  58.  
  59. Now the strange thing: I told you i=sqrt(-1), that means i^2= -1, and bi^2
  60. = -b^2 (note: the 'i' disappears, so bi^2 becomes -b^2 (!)
  61.  
  62. Conclusion:
  63.  
  64. Z(n).real = Z(n-1).real^2 - Z(n-1).imaginary^2 + C.real
  65. Z(n).imaginary = 2 * Z(n-1).real * Z(n-1).imaginary + C.imaginary
  66.  
  67. ---------------------------------------------------------------------------
  68.  
  69. Now, all we have to do is test when Z(n) is infinite :-)
  70. The value of Z(n) is the length of the vector given by it's real and
  71. imaginary parts. To calculate the length of a vector, we use the formula
  72. Length = Square-root of the value |a|^2 + the value |bi|^2, or simply
  73. Length = SQRT(a^2 + b^2) (Note: We can use the real value 'b' and not the
  74. imaginary value 'bi' here. We are just interested in the value, not if it
  75. is real or imaginary)
  76.  
  77. So, when is the length infinite ? The bad news: You can't test if it is
  78. infinite..
  79. The good news: Whenever the length exceeds 2, you know that it (some day)
  80. -will- be infinite !
  81.  
  82. To improve our 'program':
  83.  
  84. FOR EACH pixel:
  85.   REPEAT
  86.     CALCULATE Z(n) = Z(n-1)^2 + C
  87.     Length = Z(n).real^2 + Z(n).imaginary^2
  88.     iterations = iterations + 1
  89.   UNTIL Length > 4  OR iterations > max_iterations
  90. SET COLOR = iterations
  91.  
  92. You might see that I test if the length exceeds 4, not 2, and that I don't
  93. take the squareroot when calculating the length. As you all might know,
  94. calculating the squareroot takes quite a lot of time, and when
  95. SQRT('length') > 2, why not just test if 'length' > 4 ?!?
  96.  
  97. ---------------------------------------------------------------------------
  98.  
  99. To make life easy, we can make a function that has C as input-variable, and
  100. returns the number of iterations the program had to compute for that point
  101. : (In Pascal)
  102.  
  103. FUNCTION CALC_PIXEL(CA,CBi:REAL):INTEGER;  {CA = real value, CBi = imaginary}
  104. CONST MAX_ITERATION=128;  {higher value -> better quality}
  105. VAR
  106.  OLD_A          :REAL;    {just a variable to keep 'a' from being destroyed}
  107.  ITERATION      :INTEGER; {the iteration-counter}
  108.  A,Bi           :REAL;    {function Z divided in real and imaginary parts}
  109.  LENGTH_Z       :REAL;    {length of Z, sqrt(length_z)>2 => Z->infinity}
  110. BEGIN
  111.  A:=0;                    {initialize Z(0) = 0}
  112.  Bi:=0;
  113.  
  114.  ITERATION:=0;            {initialize iteration}
  115.  
  116.  REPEAT
  117.   OLD_A:=A;               {saves the 'a'  (Will be destroyed in next line}
  118.  
  119.   A:= A*A - B*B + CA;
  120.   B:= 2*OLD_A*B + CBi;
  121.  
  122.   length_z:= a*a + b*b;   {note: We do not perform the squareroot here}
  123.  UNTIL (length_z > 4) OR (iteration > max_iteration);
  124.  Calc_Pixel:=iteration;
  125. END;
  126.  
  127. ---------------------------------------------------------------------------
  128.  
  129. To compute the Mandelbrot-Set, you would have a program like:
  130.  
  131.   FOR y:= -1.25 TO 1.25 DO
  132.     FOR x:= -2 TO 1.25 DO
  133.       color:=CALC_PIXEL(x,y);
  134.  
  135. This 'program' would calculate the whole set, but you wouldn't be able to
  136. plot the Mandelbrot-set on the screen. That's why we use
  137. screen-coordinates, and calculate the C-value for each pixel: (assumes
  138. 640*480 VGA)
  139.  
  140.   FOR y:= 0 TO 480-1 DO
  141.     FOR x:= 0 TO 640-1 DO
  142.       BEGIN
  143.         color:=CALC_PIXEL(real(x),imaginary(y));
  144.         PUTPIXEL(x,y,color);
  145.       END;
  146.  
  147. This 'program' would be able to plot the set, but it has to compute the
  148. real and imaginary value for each pixel. How do we do that ???
  149. ---------------------------------------------------------------------------
  150.  
  151. First of all, we have to define the area to compute.
  152.  
  153. To compute the whole set, the area would be (-2, -1.25) - (1.25, 1.25)
  154. When coding a program, it is a good idea to have this values as constants
  155. somewhere in the code. Pascal has all constant values in the top of the
  156. source code:
  157.  
  158. PROGRAM Mandelbrot;
  159.  
  160. CONST MinX = -2;
  161.       MaxX = 1.25;
  162.  
  163.       MinY = -1.25;
  164.       MaxY = 1.25;
  165.  
  166. [rest of program..]
  167.  
  168. When the upper left corner is supposed to be (MinX, MinY) , and the lower
  169. right corner is supposed to be (MaxX, MaxY), we get this formula:
  170.  
  171.   real      = MinX + x*(MaxX-MinX)/screenwidth;
  172.   imaginary = MinY + y*(MaxY-MinY)/screenheight;
  173.  
  174. Or, to save a lot of divisions (wich takes a lot of time..) :
  175.  
  176.   dx = (MaxX-MinX)/screenwidth;   {only needed to be done once !}
  177.   dy = (MaxY-MinY)/screenheight;  {----------- "" --------------}
  178.  
  179.   real      = MinX + x*dx;
  180.   imaginary = MinY + y*dy;
  181.  
  182. Now we should be able to make a 'almost working' program :-)
  183. ---------------------------------------------------------------------------
  184.  
  185. PROGRAM Mandelbrot;
  186.  
  187. CONST MinX = -2;
  188.       MaxX = 1.25;
  189.  
  190.       MinY = -1.25;
  191.       MaxY = 1.25;
  192.  
  193. VAR dx, dy:REAL;    {Don't confuse with 'real' numbers. This is the
  194.                      Pascal Datatype REAL}
  195.     x, y  :INTEGERS;
  196.  
  197. BEGIN
  198.   dx = (MaxX-MinX)/640;
  199.   dy = (Maxy-MinY)/480;
  200.  
  201.   FOR y:=0 TO 480-1 DO
  202.     FOR x:=0 TO 640-1 DO
  203.       BEGIN
  204.         color:=CALC_PIXEL(MinX+x*dx, MinY+y*dy);
  205.         PUTPIXEL(x,y,color);
  206.       END;
  207. END.
  208.  
  209. Because of the difference in initializing and using graphics on different
  210. platforms, I can give you the complete Pascal source or complete C source
  211. for IBM-Compatible machines with VGA-Cards, and people with UNIX-machines
  212. or those lovely Amiga's have to make their own graphics-routines..
  213.  
  214. ---------------------------------------------------------------------------
  215.  
  216. Now the 'c00l' thing about fractals; You can zoom into them !
  217.  
  218. Above, we calculated the area (-2, -1.25) - (1.25, 1.25). If you look at
  219. the image below (and I hope you can read those small numbers on the axis!),
  220. you'll see that the whole Mandelbrot-set is withing that area.
  221. BUT, if you calculate the area (0.1, 0.4) - (0.5, 0.6) {as framed in figure
  222. 2}, you'll get the image shown in figure 3 !!!
  223. And if you calculate the area (0.37, 0.52) - (0.41, 0.54) {as framed in
  224. figure 3}, you'll get the image shown in figure 4 !!!
  225.  
  226. (Well, perhaps not. I can't remember the numbers I used to generate the
  227. images, so I just made a good guess above *smile* , but you understand the
  228. idea ?!?)
  229.  
  230. [Image]The whole Mandelbrot-Set
  231.  
  232. [Image]Figure 2
  233.  
  234. [Image]Figure 3
  235.  
  236. [Image]Figure 4
  237. ---------------------------------------------------------------------------
  238. Are there anything I have left out ?!? Of the elementary, don't think so,
  239. but if you have any questions or comments, PLEASE MAIL ME, and I'll update
  240. this document to suit your needs !
  241.  
  242.                                   [Image]
  243.                      visitors sice 18th November 1995.
  244. Back to homepage
  245.