Mandelbrot

Beautiful graphics from simple math – Mandelbrot set on FPGA, Part 1

Introduction to the Mandelbrot set

Like I mentioned in the previous post, I wanted to familiarize myself with the HDMI output on the DE10-nano FPGA board, and there is no harm in getting some pretty graphics along the way, so I decided to implement a Mandelbrot set viewer on FPGA.

If you are not familiar with the Mandelbrot set, it is a type of a fractal, which is simply put an infinitely – repeating recursive pattern. That means that you can zoom into the set and discover ever repeating, self-mirroring patterns. They are also a little weird ;). You can read more about them on the linked Wikipedia article.

The familiar look of the Mandelbrot set is depicted in this picture:

Mandelbrot set

Mandelbrot set

For the formal definition of the Mandelbrot set, I’ll just quote the Wikipedia article:

The Mandelbrot set is the set of values of c in the complex plane for which the orbit of critical point z= 0 under iteration of the quadratic map  remains bounded. Thus, a complex number c is a member of the Mandelbrot set if, when starting with z0 = 0 and applying the iteration repeatedly, the absolute value of zn remains bounded for all n > 0.

For example, for c = 1, the sequence is 0, 1, 2, 5, 26, …, which tends to infinity, so 1 is not an element of the Mandelbrot set. On the other hand, for c = −1, the sequence is 0, −1, 0, −1, 0, …, which is bounded, so −1 does belong to the set.

Which put in simple terms means that the Mandelbrot set can be calculated simply by iteratively calculating the equation for all “interesting” complex numbers , and starting the iteration with . The complex number is expressed as x + iy, where x and y can be mapped to the horizontal and vertical position on the screen. If the iteration doesn’t escape to infinity, then is part of the set.

That handles the “black&white” part. You can then decide how to color the image. A popular (and simple) algorithm you can use is the Escape time algorithm, which selects the color of each individual pixel based on whether the pixel is part of the set or not, and if not, how many iterations it took to “escape”.

The simplified Escape time algorithm can be represented in pseudocode like this:

x2 := 0
y2 := 0

while (x2 + y2 ≤ 4 and iteration < max_iteration) do
  y := 2 × x × y + y0
  x := x2 - y2 + x0
  x2 := x × x
  y2 := y × y
  iteration := iteration + 1

The Mandelbrot set colored with the Escape time algorithm has some properties that are very helpful if you want to calculate it on an FPGA:

  • the set is closed and contained in a closed disk of radius 2 – if the distance from the origin (starting point) is bigger than 2 for the current iteration, then that origin is not part of the set, and you can stop iterating
  • since the set has a limited radius, that means that the range of numbers we need to work with is also limited – important if you want to use integer only math
  • the pixel values are independent of one another – you can calculate all pixels in parallel
  • not a lot of iterations are needed for each pixel
  • the equation to calculate it is simple, probably the simplest of all fractals that I know of

 

So, to implement the algorithm on an FPGA, you can already see the requirements:

  • memory to hold the calculated pixel values – how much depends on the FPGA resources, and the amount of available memory will determine the maximum resolution
  • the maximum number of iterations will be also limited by the memory – using 8, 9 or 10 bit memory width will provide the best resource utilization
  • as can be seen from the pseudocode above, a lot of multipliers will be needed, ideally, you would use all the FPGA DSP elements available
  • the multipliers will need to be quite wide, at least 27 bits, since you’d want to zoom deep into the Mandelbrot set

 

This covers the introduction to the Mandelbrot set. I’ll go deeper into the implementation in the next post. Cheers!

 

The BoingBall, Part 2

So, we have rendered frames of our BoingBall, as described in Part 1. What you want to do next is check if the animation is seamless – that is, if it loops without glitches. Best way is to convert the frames into a .gif or .avi animation (in my experience GIF works better) with your favorite photo / video editor. You will also need to reduce the number of colors of your frames, I used just two colors (white & red) + background. I needed a few tries to get this right:

BoingBall animation

Once the animation looks good, you need to first decide on what kind of Amiga resolution the animation will be shown – either hires or lores. The difference is that on hires the pixels are not square, but are twice as high as they are long, so you need to ‘squash’ the ball vertically:

BoingBall_128x64

Now you need to somehow convert the animation data to be used on the Amiga. You have to remember that contrary to PCs of today which use so called ‘chunky‘ pixels, Amiga uses a planar graphics display, which splits each bit of the pixel data into a separate plane – that allows it to save memory & bandwidth, if for example you only needed two colors you would only require one bit per pixel instead of 8 (or even 16 or 32!).

For the conversion, I wrote a simple Python script which takes a GIF animation, splits it into frames, splits the frames into bitplanes and writes the result into a source file that can be used in AsmOne assembler on the Amiga. The script is attached bellow.

I also made a minimig logo, which you can see below:

Minimig logo

Now comes the fun part – writing a program that will show this animation on the Amiga – or in this case, the Minimig board. We want this animation to work very early in the Minimig bootup, when no operating system is available, actually even the CPU is not available as it is in reset.

Luckily, hitting the hardware registers directly is nothing special on the Amiga as everyone was (is!) doing it, from demo coders (check out the Amiga Demoscene Archive for some amazing demos) to games. The Amiga chipset is quite complex, so I won’t go into too much details about how to set it up. If you want some great tutorials about writing hardware-hitting Amiga software, you might want to check out Photon’s great coding page and Youtube channel, it was certainly a great help for me to freshen up my Amiga coding 😉

So, we have no OS and no CPU, how can we play an animation? Well, the custom chips of the Amiga will help here. Amiga has some very interesting hardware, but for this animation we are interested in two particularly: the Blitter and the Copper. The Blitter’s name comes from Blit, which is short for block image transfer. Simply put, the Blitter is a configurable DMA engine that can transfer images in memory (it is much more capable, but let’s leave it at that). The Copper, short for co-processor, is a very basic processor that only has three commands: MOVE, WAIT and SKIP, but it is also tied to the video beam. Since the Copper can write Blitter’s registers, they together form a sort of a Turing-complete system, certainly capable enough to play back this animation.

Since you don’t want to write this ‘blind’, you need a way to test that everything works while you’re working on it. I used ASMOne, which is a great assembler for the Amiga, and WinUAE, a windows Amiga emulator. Our program is using the CPU to set up the custom chipset, and once set up, the chipset runs by itself. The CPU part will be replaced with custom code on the minimig, since on minimig the control CPU can write custom registers when the CPU is in reset. For the test program, we need a little more setup than is required for minimig, especially saving enabled interrupts and DMAs, which are restored on exit. The CPU must also copy the minimig logo and the boingball animation data to the proper place in chipram, then it enters a loop waiting for the mouse button press, cleans up and exits. The required part is setting up bitplane DMAs, copper, screen, blitter and the color values:

SysSetup:
 move.w #$0000,$dff1fc ; FMODE, slow fetch mode for AGA compatibility
 move.w #$0002,$dff02e ; COPCON, enable danger mode
 move.l #Copper1,$dff080 ; COP1LCH, copper 1 pointer
 move.l #Copper2,$dff084 ; CPO2LCH, copper 2 pointer
 move.w #$0000,$dff088 ; COPJMP1, restart copper at location 1
 move.w #$2c81,$dff08e ; DIWSTRT, screen upper left corner
 move.w #$f4c1,$dff090 ; DIWSTOP, screen lower right corner
 move.w #$003c,$dff092 ; DDFSTRT, display data fetch start
 move.w #$00d4,$dff094 ; DDFSTOP, display data fetch stop
 ;move.w #$7fff,$dff096 ; DMACON, disable all DMAs
 move.w #$87c0,$dff096 ; DMACON, enable important bits
 move.w #$0000,$dff098 ; CLXCON, TODO
 move.w #$7fff,$dff09a ; INTENA, disable all interrupts
 move.w #$7fff,$dff09c ; INTREQ, disable all interrupts
 move.w #$0000,$dff09e ; ADKCON, TODO
 move.w #$a200,$dff100 ; BPLCON0, two bitplanes & colorburst enabled
 move.w #$0000,$dff102 ; BPLCON1, bitplane control scroll value
 move.w #$0000,$dff104 ; BPLCON2, misc bitplane bits
 move.w #$0000,$dff106 ; BPLCON3, TODO
 move.w #$0000,$dff108 ; BPL1MOD, bitplane modulo for odd planes
 move.w #$0000,$dff10a ; BPL2MOD, bitplane modulo for even planes
 move.w #$09f0,$dff040 ; BLTCON0
 move.w #$0000,$dff042 ; BLTCON1
 move.w #$ffff,$dff044 ; BLTAFWM, blitter first word mask for srcA
 move.w #$ffff,$dff046 ; BLTALWM, blitter last word mask for srcA
 move.w #$0000,$dff064 ; BLTAMOD
 move.w #BLITS,$dff066 ; BLTDMOD
 move.w #$0000,$dff180 ; COLOR00
 move.w #$0aaa,$dff182 ; COLOR01
 move.w #$0a00,$dff184 ; COLOR02
 move.w #$0000,$dff186 ; COLOR03
 move.w #(bpl1>>16)&$ffff,$dff0e0 ; BPL1PTH
 move.w #bpl1&$ffff,$dff0e2 ; BPL1PTL
 move.w #(bpl2>>16)&$ffff,$dff0e4 ; BPL2PTH
 move.w #bpl2&$ffff,$dff0e6 ; BPL2PTL

We set up the space for the bitplanes at $80000:

 ORG $80000
 EVEN
Screen:
bpl1:
 dcb.b BPLSIZE
bpl1E:
bpl2:
 dcb.b BPLSIZE
bpl2E:

Most of the work is done with the copper and blitter. Since the minimig logo is fixed in place, it only needs moving to the proper position in the bitplanes. The rotating ball is also not moving around, so there is no need to clear the bitplanes, we just write new data over the old one. If we want to show the boingball animation with the correct speed, one frame of the animation must be shown for 5 minimig frames (minimig has a refresh rate of 50Hz for PAL). That means quite a long copper list, moving the copper pointer around each frame and the blitter pointer every five frames, since we don’t have a CPU to do any of that. Below is copper code for a single frame of animation, spanning 5 Amiga screen refreshes:

 EVEN
Copper2:
c2f00:
 dc.w $0050,(f0p0>>16)&$ffff
 dc.w $0052,(f0p0)&$ffff
 dc.w $0054,((bpl1+BALLOFF)>>16)&$ffff
 dc.w $0056,((bpl1+BALLOFF))&$ffff
 dc.w $0058,(BLITH<<6+BLITW)
 dc.w $0107,$7ffe
 dc.w $0050,(f0p1>>16)&$ffff
 dc.w $0052,(f0p1)&$ffff
 dc.w $0054,((bpl2+BALLOFF)>>16)&$ffff
 dc.w $0056,((bpl2+BALLOFF))&$ffff
 dc.w $0058,(BLITH<<6+BLITW)
 dc.w $0084,(c2f01>>16)&$ffff
 dc.w $0086,(c2f01)&$ffff
 dc.w $ffff,$fffe
c2f01:
 dc.w $0084,(c2f02>>16)&$ffff
 dc.w $0086,(c2f02)&$ffff
 dc.w $ffff,$fffe
c2f02:
 dc.w $0084,(c2f03>>16)&$ffff
 dc.w $0086,(c2f03)&$ffff
 dc.w $ffff,$fffe
c2f03:
 dc.w $0084,(c2f04>>16)&$ffff
 dc.w $0086,(c2f04)&$ffff
 dc.w $ffff,$fffe
c2f04:
 dc.w $0084,(c2f10>>16)&$ffff
 dc.w $0086,(c2f10)&$ffff
 dc.w $ffff,$fffe

This code is repeated eight times for each frame of the animation.

So, after these two long posts, does it work at all? It sure does:

Whole AsmOne source code is here:

The BoingBall, Part 1

I’ve received some questions about how I made the new minimig logo with the rotating checkered ball, so I thought I’d write something about it for my first post.

The BoingBall is quite famous in the Amiga land, as it was featured in one of the first demos made for the Amiga computer to demonstrate its capabilities at the Consumer Electronics Show in January 1984. It was later used as an official logo of the Amiga. Its roots go even further back, but enough with history. You can watch this video describing how the BoingBall demo came about:


At the time I was replacing the boot code in minimig, and I thought ‘why not add something more dynamic to the boot screen?’ So the idea to use the iconic BoingBall animation was born.

When I was younger, I played around with 3D animation and modeling a lot, mostly with Lightwave on the Amiga and later with 3D Studio running in DOS on a PC. But for this task, a much simpler renderer was used, one that is probably best suited for this task, also one of my favourites – the freely-available POV-Ray. POV-Ray doesn’t have a modeler, you describe the scene in a text file, but for such a simple scene, you wouldn’t need a full-featured modeler anyway.

I won’t go into all the features of POV-Ray language, I’ll just describe the basics needed for the BoingBall animaton. You need three things in a basic scene like this:

  • an object to render
  • a camera, preferably looking at your object
  • lights

You place the camera with a location and a direction statement :

camera
{
  location <0,0,-6>
  look_at <0,0,0>
}

Next, lights – I used both ambient and omni lights around the ball:

global_settings { ambient_light color White }
light_source { <+0, +0, -6> color White }
light_source { <+0, +0, +6> color White }
light_source { <+0, -6, +0> color White }
light_source { <+0, +6, +0> color White }
light_source { <-6, +0, +0> color White }
light_source { <+6, +0, +0> color White }

And then comes the object of interest – a sphere with a red-white checkered pattern:

sphere {
  // placement and size
  <0, 0, 0>, 2
  // texture
  texture {
    pigment {
      // red / white checker pattern
      checker color Red, color White
    }
  }
}

The sphere’s texture needed some fixing of the scale and a warp pattern modifier that wraps the checkered pattern around a sphere:

      // the x-y scaling is a bit off, fixing it together with size
      scale <1.5/pi, 1.0/pi, 1>*0.25
      warp { spherical orientation y dist_exp 1 }

All that is needed now is the animation:

  // rotate (rotate after texture!)
  // 1/8th of full rotation so the texture aligns for a nice animation
  rotate<0,360/8*(clock+0.00),0>
  // adding a slight tilt (after animation rotation!)
  rotate <0,0,-15>

The order of these steps is important in this case – first you apply the texture, than the rotation and the slight tilt the last, otherwise the result will not be what you desired. The clock in the last code snippet is the animation parameter (for a repeating animation you need to calculate how much the ball must rotate in a desired number of frames).

To render this scene, you give POV-Ray some parameters, preferably in an .ini file:

[boingball]
Input_File_Name=boingball.pov
Width=800
Height=600
Antialias=On
Antialias_Threshold=0.3
Initial_Frame=1
Final_Frame=8
Cyclic_Animation = on

And the result:

boingball1

Once you have all of the frames of the animation, you need to parse the image data, transfer it to the Amiga and write a copper list to animate it (yes, the boot logo doesn’t use the CPU, the animation runs using blitter and copper only). But that is a story for another post.

 

Continued in BoingBall, Part 2