Transcript Lab Lecture 5 - the GMU ECE Department

ECE 448: Spring 2016
Lab 5
Julia Set Fractal
1
Introduction to Lab5
2
Benoit Mandelbrot
• Mandelbrot was born in
Poland in 1924.
• Father of fractal
geometry.
• He showed how fractals
can occur in many
different places in both
mathematics and
elsewhere in nature.
3
What is a Fractal?
Fractals are mathematical structures defined by two
properties
– Iterative
– Self-similar
• Zooming in or out on the image reveals deep
repetition of patterns
4
The Julia Set
• Julia Set was named for the early twentieth century French
mathematician Gaston Julia
• The Julia set is a set of points in the complex plane, the
boundary of which forms a fractal.
• Mathematically, the Julia set can be generated using a
very simple iterative formula, called the quadratic
recurrence equation, applied to points in complex plane
zn+1 = zn2 + zn + c
5
The Julia Set
6
Pseudocode
In the pseudocode below, Z0=z0x+i·z0y, corresponds to one
pixel of the display region. The plotted region should have the
following limits
-2 ≤ z0x=Re[Z0] ≤ 2
-1.5 ≤ z0y=Im[Z0] ≤ 1.5
for z0y = -1.5 to 1.5, step 3/400 do
for z0x = -2 to 2, step 4/600 do
{
iteration = 0
zx = z0x
zy = z0y
7
Pseudocode Cont…
// z = z2 + z + c = (zx2 – zy2 +zx + cx) + i ·
//(2 · zx · zy + zy + cy)
while (zx2 + zy2 < 4 && iteration < MAX_ITER ){
zxtemp = zx2 – zy2 + zx + cx
zytemp = 2 · zx · zy + zy + cy
zx = zxtemp
zy = zytemp
iteration++
}
8
Pseudocode Cont…
x = x_conv(z0x)
y = y_conv(z0y)
// conversion to the x-coordinate of a pixel
// conversion to the y-coordinate of a pixel
if
zx2 + zy2 < 4
color(x,y) = fractal_color
else
color(x,y) = background_color
}
9
x_conv() and y_conv
The functions x_conv() and y_conv() are used to convert the
coordinates of the complex number Z0 into x and y coordinates
of the pixel.
x = x_conv(z0x) = 20 + (z0x-(-2))*(600/4) = 20 + 150*(z0x+2)
y = y_conv(z0y) = 440 - (z0y-(-1.5))*(400/3)= 440 – 133.33*(z0y+1.5)
10
Fixed Point Representation
• You can use Q4.28 representation
– 4 integer bits
– 28 fractional bits
• Addition/Subtraction performed as usual
• Multiplication of two Q4.28 numbers
results in a Q8.56 number, which should
be converted back to Q4.28
11
VGA Display Area
• Use a rectangular area of the size
(600 x 400) to display the Julia set fractal.
• Left and Right border = 20 pixels each
• Top and Bottom border = 40 pixels each
12
Cont..
• Top border should display
“THE JULIA SET”
in the center.
• Bottom border should display
– Percentage of the display area, increasing
every 0.5%.
– Progress bar
– Total execution time with the step 0.1 s.
13
Input/Output Scheme
• Use BTNS as the Start/Pause button to start/pause
the computations.
• The color of the fractal and background should also
change, depending on the positions of switches
14
Final VGA Display Outlook
THE JULIA SET
95.5%
33.1 s
15
Bonus Tasks
• Increase the speed of calculations, by evaluating 4 values of
Z0 in parallel.
• Determine the maximum speed-up possible by evaluating N
values of Z0 in parallel, where N is limited only by the
available FPGA resources.
• Add colors by assigning a different color to each value of Z0,
based on the number of iterations required for the
decision based on the following formula:
color = iteration mod 8
16