Plotting the Mandelbrot set. Very slow.

Getting Started Newbie Questions
#1

hi - I made a short program to plot the Mandelbrot set. My algorithm takes several seconds to draw the set. It iterates over every ‘pixel’ in my 320 x 480 screen and calculates what shade of grey it should be, then creates a 1 x 1 rectangle with that shade of grey. display.newRect() is called around 154,000 times. I’m wondering if there’s a faster way to draw the set. Thanks.

Here’s the code.

local MAX\_ITER = 80 local re\_start= -2 local re\_end = 1 local im\_start = -1 local im\_end = 1 local WIDTH = display.contentWidth local HEIGHT = display.contentHeight --count and return number of iterations of f(z) = z^2 + c, where c is a complex number (cr + ci), --until either MAX\_ITER is reached or z exceeds 2. local function mandelbrot(cr,ci) &nbsp;&nbsp; &nbsp;local z = 0 &nbsp;&nbsp; &nbsp;local zr = 0 &nbsp;&nbsp; &nbsp;local zi = 0 &nbsp;&nbsp; &nbsp;local zrp = 0 &nbsp;&nbsp; &nbsp;local zip = 0 &nbsp;&nbsp; &nbsp;local n = 0 &nbsp;&nbsp; &nbsp;while math.abs(z) \<= 2 and n \< MAX\_ITER do &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;zr = (zrp \* zrp) + cr - (zip \* zip) &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;zi = (2 \* (zrp \* zip)) + ci &nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp; z = math.sqrt((zr \* zr) + (zi \* zi)) &nbsp; &nbsp;&nbsp; &nbsp;&nbsp; zrp = zr &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;zip = zi &nbsp; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;n = n + 1 &nbsp;&nbsp; &nbsp;end &nbsp;&nbsp; &nbsp;return n end draw = function() &nbsp;&nbsp; &nbsp;local t = 0 &nbsp;&nbsp; &nbsp;local real = 0 &nbsp;&nbsp; &nbsp;local im = 0 &nbsp;&nbsp; &nbsp;local mag = 0 &nbsp;&nbsp; &nbsp;local col = 0 &nbsp;&nbsp; &nbsp;for x = 0, WIDTH&nbsp; do &nbsp;&nbsp; &nbsp; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;for y = 0, HEIGHT do &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;real = re\_start+ ((x/WIDTH) \* (re\_end - RE\_START)) &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;im = IM\_START + ((y/HEIGHT) \* (IM\_END - IM\_START) ) &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;t = mandelbrot(real,im) &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;col = 255 - (t \* 255 / MAX\_ITER) &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;local dot = display.newRect(x,y,1,1) &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;dot:setFillColor(col/255,col/255,col/255) &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;end &nbsp;&nbsp; &nbsp;end end draw()

 

#2

For pixel by pixel manipulation, it’s probably worth checking out

 memory bitmaps as well as impack in the Corona Marketplace

#3

At 154,000 iterations you’re grinding through a LOT of accesses to the global math followed by a lookup of its abs and sqrt keys. These will add up. For that matter, you don’t even need the absolute value, since you’re adding two squares, and you’re only doing a check, so even the root is unnecessary. Rather, you’d have something like:

repeat zr = (zrp \* zrp) + cr - (zip \* zip) zi = (2 \* (zrp \* zip)) + ci z = (zr \* zr) + (zi \* zi) zrp = zr zip = zi n = n + 1 until z \>= (2 \* 2) or n == MAX\_ITER

There is also some needless recomputation of coefficients and pointless conversion to and from integer colors:

local width\_coeff = (re\_end - re\_start) / WIDTH local height\_coeff = (im\_end - im\_start) / HEIGHT local t\_coeff = 1 / MAX\_ITER -- ^^ outside of draw() for x = 0, WIDTH do real = re\_start + x \* width\_coeff for y = 0, HEIGHT do im = im\_start + y \* height\_coeff t = mandelbrot(real,im) col = 1 - t \* t\_coeff local dot = display.newRect(x,y,1,1) dot:setFillColor(col, col, col) end end

I agree with sporkfin that memory bitmaps are a good fit here.

You might also try to break up draw() with a timer, just because of the sheer number of pixels.

#4

Also, you’re creating 154,000 display objects. You’re not creating a 4 byte pixel.

I concur. This is exactly what memory bitmap is for.

Rob

#5

ok thanks everyone, that’s really helpful. I’ll implement the suggested changes.

#6

This is some cool stuff!

#7

OK I’ve implemented the suggested changes and it is indeed much faster. It renders the set almost immediately now. However, I’m also try to implement a zoom feature, where you tap a point on the set, and it zooms in on that point x 10. This zoom seems to work, but again, it’s tremendously slow (10 or 15 seconds to render the zoom. I’m not sure why, since it’s using the same draw function as the quick first iteration, and I can tell from print statements that it’s making the calculation of the new start and end points immediately. Here’s my new code, plus the zoom listener function.

local memoryBitmap = require( "plugin.memoryBitmap" ) local MAX\_ITER = 80 local re\_start= -2 local re\_end = 1 local im\_start = -1 local im\_end = 1 local re\_difference = 0 local im\_difference = 0 local re\_zoompoint = 0 local im\_zoompoint = 0 local magnif = 0.05 -- represents a factor of 10 each zoom local WIDTH = display.contentWidth local HEIGHT = display.contentHeight -- Create bitmap texture local tex = memoryBitmap.newTexture( &nbsp;&nbsp;&nbsp; { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; width = WIDTH, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; height = HEIGHT, &nbsp;&nbsp;&nbsp; }) &nbsp; -- Create image using the bitmap texture local bitmap = display.newImageRect( tex.filename, tex.baseDir, WIDTH, HEIGHT ) bitmap.x = display.contentCenterX bitmap.y = display.contentCenterY zoomListener = function(event) &nbsp;&nbsp; &nbsp;if ( event.phase == "began" ) then &nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp;&nbsp; elseif&nbsp; ( event.phase == "ended" ) then&nbsp;&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;display.getCurrentStage():setFocus(nil) &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;re\_difference = re\_end - re\_start &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;re\_zoompoint = re\_start + ((event.x / WIDTH) \* re\_difference) &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;re\_start= re\_zoompoint - (re\_difference \* magnif) &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;re\_end = re\_zoompoint + (re\_difference \* magnif) &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;im\_difference = im\_end - im\_start &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;im\_zoompoint = im\_start + ( im\_difference - ((event.y/HEIGHT) \* im\_difference)) &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;im\_start = im\_zoompoint - (im\_difference \* magnif) &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;im\_end = im\_zoompoint + (im\_difference \* magnif) &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;draw() &nbsp;&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp;end end local bg = display.newImageRect("pics/transparency.png",WIDTH,HEIGHT) bg:addEventListener("touch",zoomListener) bg.anchorX = 0 bg.anchorY = 0 mandelbrot = function(cr,ci) &nbsp;&nbsp; &nbsp;local z = 0 &nbsp;&nbsp; &nbsp;local zr = 0 &nbsp;&nbsp; &nbsp;local zi = 0 &nbsp;&nbsp; &nbsp;local zrp = 0 &nbsp;&nbsp; &nbsp;local zip = 0 &nbsp;&nbsp; &nbsp; &nbsp;&nbsp; &nbsp;local n = 0 &nbsp;&nbsp; &nbsp;while z \<= 4 and n \< MAX\_ITER do &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;zr = (zrp \* zrp) + cr - (zip \* zip) &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;zi = (2 \* (zrp \* zip)) + ci &nbsp; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;z = (zr \* zr) + (zi \* zi) &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp; zrp = zr &nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp; zip = zi &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;n = n + 1 &nbsp;&nbsp; &nbsp;end &nbsp;&nbsp; &nbsp;return n end draw = function() &nbsp;&nbsp; &nbsp;local t = 0 &nbsp;&nbsp; &nbsp;local real = 0 &nbsp;&nbsp; &nbsp;local im = 0 &nbsp;&nbsp; &nbsp;local mag = 0 &nbsp;&nbsp; &nbsp;local col = 0 &nbsp;&nbsp; &nbsp; &nbsp;&nbsp; &nbsp;local width\_coeff = (re\_end - re\_start)/WIDTH &nbsp;&nbsp; &nbsp;local height\_coeff = (im\_end - im\_start)/HEIGHT &nbsp;&nbsp; &nbsp;local t\_coeff = 1/MAX\_ITER &nbsp;&nbsp; &nbsp; &nbsp;&nbsp; &nbsp;for x = 1,tex.width do &nbsp; &nbsp; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;for y = 1,tex.height do &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;real =&nbsp;&nbsp; &nbsp;re\_start + (x \* width\_coeff) &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;im&nbsp; = im\_start + (y \* height\_coeff) &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;t = mandelbrot(real,im) &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;col = 1 - (t \* t\_coeff) &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp; tex:setPixel( x, y, col, col, col, 0) &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;tex:invalidate() &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;end &nbsp;&nbsp; &nbsp;end &nbsp;&nbsp; &nbsp; end draw()
#8

Can’t test it myself right now, but that tex:invalidate() call should for sure only happen once after you’ve updated all the pixels and not for each pixel (I’d guess that, at the moment, you’re doing 154000 full texture updates in your draw function).

#9

I’m not sure but can you do a memory bitmap on a canvas or snapshot and then zoom in on the canvas or snapshot?

@StarCrunch - would that work?

#10

I’ve put tex:invalidate() outside the loop and it’s now much faster. Looks like that was the issue.

Is there a mistake on this page? https://docs.coronalabs.com/plugin/memoryBitmap/index.html

I copied the code from there, and tex:invalidate() is inside the loop on this page.

#11

Yeah, seems to be a very suboptimal code sample as the only reason for an explicit invalidate() call is to be able to delay the work it’s doing until all pixels have been modified.