Jump to content

[TOPIC: topicViewTemplate]
[GLOBAL: userSmallPhoto]
Photo

Plotting the Mandelbrot set. Very slow.
Started by d2gp Dec 06 2019 01:57 PM

10 replies to this topic
[TOPIC CONTROLS]
[/TOPIC CONTROLS]
[modOptionsDropdown]
[/modOptionsDropdown]
[reputationFilter]
[TOPIC: post.html]
#1

d2gp

[GLOBAL: userInfoPane.html]
d2gp
  • Contributor

  • 269 posts
  • Corona SDK

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)

    local z = 0
    local zr = 0
    local zi = 0
    local zrp = 0
    local zip = 0

    local n = 0

    while math.abs(z) <= 2 and n < MAX_ITER do

        zr = (zrp * zrp) + cr - (zip * zip)
        zi = (2 * (zrp * zip)) + ci
        z = math.sqrt((zr * zr) + (zi * zi))
        zrp = zr
        zip = zi
 
        n = n + 1
    end
    return n
end


draw = function()

    local t = 0
    local real = 0
    local im = 0
    local mag = 0
    local col = 0

    for x = 0, WIDTH  do
    
        for y = 0, HEIGHT do

            real = re_start+ ((x/WIDTH) * (re_end - RE_START))
            im = IM_START + ((y/HEIGHT) * (IM_END - IM_START) )

            t = mandelbrot(real,im)

            col = 255 - (t * 255 / MAX_ITER)

            local dot = display.newRect(x,y,1,1)
            dot:setFillColor(col/255,col/255,col/255)

        end
    end
end

draw()


 



[TOPIC: post.html]
#2

sporkfin

[GLOBAL: userInfoPane.html]
sporkfin
  • Contributor

  • 720 posts
  • Corona SDK

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

 

 memory bitmaps as well as impack in the Corona Marketplace



[TOPIC: post.html]
#3

StarCrunch

[GLOBAL: userInfoPane.html]
StarCrunch
  • Contributor

  • 842 posts
  • Corona SDK

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.


  • roaminggamer and pixec like this

[TOPIC: post.html]
#4

Rob Miracle

[GLOBAL: userInfoPane.html]
Rob Miracle
  • Moderator

  • 26,544 posts
  • Enterprise

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



[TOPIC: post.html]
#5

d2gp

[GLOBAL: userInfoPane.html]
d2gp
  • Contributor

  • 269 posts
  • Corona SDK

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



[TOPIC: post.html]
#6

pixec

[GLOBAL: userInfoPane.html]
pixec
  • Contributor

  • 106 posts
  • Corona SDK

This is some cool stuff!
  • d2gp likes this

[TOPIC: post.html]
#7

d2gp

[GLOBAL: userInfoPane.html]
d2gp
  • Contributor

  • 269 posts
  • Corona SDK

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(
    {
        width = WIDTH,
        height = HEIGHT,
    })
 
-- 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)

    if ( event.phase == "began" ) then  
         
   elseif  ( event.phase == "ended" ) then    
           
        display.getCurrentStage():setFocus(nil)
        
        re_difference = re_end - re_start
        re_zoompoint = re_start + ((event.x / WIDTH) * re_difference)
        re_start= re_zoompoint - (re_difference * magnif)
        re_end = re_zoompoint + (re_difference * magnif)

        im_difference = im_end - im_start
        im_zoompoint = im_start + ( im_difference - ((event.y/HEIGHT) * im_difference))
        im_start = im_zoompoint - (im_difference * magnif)
        im_end = im_zoompoint + (im_difference * magnif)

        draw()
    
       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)
    local z = 0
    local zr = 0
    local zi = 0
    local zrp = 0
    local zip = 0
    
    local n = 0

    while z <= 4 and n < MAX_ITER do

        zr = (zrp * zrp) + cr - (zip * zip)
        zi = (2 * (zrp * zip)) + ci  
        z = (zr * zr) + (zi * zi)
        
        zrp = zr
        zip = zi
        
        n = n + 1
    end

    return n
end

draw = function()

    local t = 0
    local real = 0
    local im = 0
    local mag = 0
    local col = 0
    
    local width_coeff = (re_end - re_start)/WIDTH
    local height_coeff = (im_end - im_start)/HEIGHT
    local t_coeff = 1/MAX_ITER
    
    for x = 1,tex.width do
 
          for y = 1,tex.height do

            real =    re_start + (x * width_coeff)
            im  = im_start + (y * height_coeff)
                 
            t = mandelbrot(real,im)
            
            col = 1 - (t * t_coeff)
            tex:setPixel( x, y, col, col, col, 0)
            tex:invalidate()
        end
    end
    
end

draw()


[TOPIC: post.html]
#8

Michael Flad

[GLOBAL: userInfoPane.html]
Michael Flad
  • Contributor

  • 248 posts
  • Corona SDK

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).



[TOPIC: post.html]
#9

sporkfin

[GLOBAL: userInfoPane.html]
sporkfin
  • Contributor

  • 720 posts
  • Corona SDK

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?



[TOPIC: post.html]
#10

d2gp

[GLOBAL: userInfoPane.html]
d2gp
  • Contributor

  • 269 posts
  • Corona SDK

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.



[TOPIC: post.html]
#11

Michael Flad

[GLOBAL: userInfoPane.html]
Michael Flad
  • Contributor

  • 248 posts
  • Corona SDK

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.

 

 

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.




[topic_controls]
[/topic_controls]