Manelbrot Generator ...

BackupUser · Post by **BackupUser** » Mon Nov 25, 2002 6:11 am

Restored from previous forum. Originally posted by WolfgangS.

HI !
this should be a Mandelbrot Generator ...
Who can improve it ?

MFG
:)WolfgangS

Code: Select all

xmax=640
ymax=400

maxcolor=15

leftside.f  =-2
top.f       =1.25
xside.f     =2.5
yside.f     =-2.5
xscale.f    =xside/xmax          
yscale.f    =yside/ymax

If InitSprite()=0 Or InitKeyboard()=0
  beep_(300,300):End:EndIf

OpenScreen(640,400,32,"")

For y=1 To ymax
  For x=1 To xmax
    cx.f=x*xscale+leftside
    cy.f=y*yscale+top
    zx.f=0
    zy.f=0
    colorcounter=0
    
    While (Pow(zx,2)+Pow(zy,2)<4 And colorcounter<maxcolor)
      tempx.f =Pow(zx,2)-Pow(zy,2)+cx
      zy      =2*Pow(zx,2)+cy
      zx      =tempx
      colorcounter+1
    Wend
    
    StartDrawing(ScreenOutput()) 
      Plot(x,y,colorcounter*$111111)
    StopDrawing()
  Next
  FlipBuffers()
Next

Repeat
  ExamineKeyboard()
Until KeyboardPushed(#PB_Key_Escape)
End

BackupUser · Post by **BackupUser** » Mon Nov 25, 2002 7:51 am

Restored from previous forum. Originally posted by fweil.

WolfgangS,

I will take a look but I can tell you a first point : by drawing (StartDrawing / StopDrawing) each pixel it is slow ... The first way to improve it should be to draw in another way than pixel by pixel.

Rgrds

Francois Weil
14, rue Douer
F64100 Bayonne

BackupUser · Post by **BackupUser** » Mon Nov 25, 2002 8:33 am

Restored from previous forum. Originally posted by WolfgangS.

Hi !
i know, it just should be simple.
I thought more about the form of the Mandelbrot grafik

MFG
WolfgangS

BackupUser · Post by **BackupUser** » Mon Nov 25, 2002 8:35 am

Restored from previous forum. Originally posted by Danilo.

I added a timing routine to your loop:

Code: Select all

xmax=640
ymax=400

maxcolor=15

leftside.f  =-2
top.f       =1.25
xside.f     =2.5
yside.f     =-2.5
xscale.f    = xside / xmax          
yscale.f    = yside / ymax

temp1.f = xscale+leftside

If InitSprite()=0 Or InitKeyboard()=0
  beep_(300,300):End:EndIf

OpenScreen(640,400,32,"")

begin = GetTickCount_()
For y=1 To ymax
  For x=1 To xmax
    cx.f=x*xscale+leftside
    cy.f=y*yscale+top
    zx.f=0
    zy.f=0
    colorcounter=0
    
    While (Pow(zx,2)+Pow(zy,2)<4 And colorcounter<maxcolor)
      tempx.f =Pow(zx,2)-Pow(zy,2)+cx
      zy      =2*Pow(zx,2)+cy
      zx      =tempx
      colorcounter+1
    Wend
    
    StartDrawing(ScreenOutput()) 
      Plot(x,y,colorcounter*$111111)
    StopDrawing()
  Next
  FlipBuffers()
Next
final = GetTickCount_()-begin

Repeat
  ExamineKeyboard()
Until KeyboardPushed(#PB_Key_Escape)
CloseScreen()

MessageRequester("TIME",StrU(final,2)+" ms",0)

and changed the code a bit after that:

Code: Select all

#xmax=640
#ymax=400

#maxcolor=15

leftside.f  =-2
top.f       =1.25
xside.f     =2.5
yside.f     =-2.5
xscale.f    =xside/#xmax          
yscale.f    =yside/#ymax

Dim ColorBuffer(#xmax,#ymax)

Structure LONG
  l.l
EndStructure

If InitSprite()=0 Or InitKeyboard()=0
  beep_(300,300):End:EndIf

OpenScreen(#xmax,#ymax,32,"")

StartDrawing(ScreenOutput())
  Buffer      = DrawingBuffer()
  Pitch       = DrawingBufferPitch()
  PixelFormat = DrawingBufferPixelFormat()

begin = GetTickCount_()
For y=0 To #ymax-1
  *Line.LONG = Buffer+y*Pitch
  For x=0 To #xmax-1
    cx.f = x * xscale + leftside
    cy.f = y * yscale + top
    zx.f = 0
    zy.f = 0
    colorcounter = 0
    
    PowZX.f = zx*zx;Pow(zx,2)
    PowZY.f = zy*zy;Pow(zy,2)
    While (PowZX+PowZY)<4 And colorcounter<#maxcolor
      tempx.f = PowZX - PowZY + cx
      zy      = 2 * PowZX + cy
      zx      = tempx
      colorcounter + 1
      PowZX = zx*zx;Pow(zx,2)
      PowZY = zy*zy;Pow(zy,2)
    Wend

    *Line\l = colorcounter*$111111
    *Line+4

  Next
  FlipBuffers()
Next
StopDrawing()
FlipBuffers()
final = GetTickCount_()-begin

Repeat
  ExamineKeyboard()
Until KeyboardPushed(#PB_Key_Escape)
CloseScreen()

MessageRequester("TIME",StrU(final,2)+" ms",0)

I didnt change anything in your algorithm
or in the general structure.

Times:
18.667 - your version
05.318 - my version

3.5 times faster, but i think there could be
a problem on some cards with the PixelFormat.
I think Fred can tell us more about this problem...

The speed would be much better if you calculate all
and display it at the end - so no FlipBuffers() is
needed in every loop.

Well, lets try it:

Code: Select all

#xmax=640
#ymax=400

#maxcolor=15

leftside.f  =-2
top.f       =1.25
xside.f     =2.5
yside.f     =-2.5
xscale.f    =xside/#xmax          
yscale.f    =yside/#ymax

Dim ColorBuffer(#xmax,#ymax)

Structure LONG
  l.l
EndStructure

If InitSprite()=0 Or InitKeyboard()=0
  beep_(300,300):End:EndIf

OpenScreen(#xmax,#ymax,32,"")

begin = GetTickCount_()
For y=0 To #ymax-1
  For x=0 To #xmax-1
    cx.f = x * xscale + leftside
    cy.f = y * yscale + top
    zx.f = 0
    zy.f = 0
    colorcounter = 0
    
    PowZX.f = zx*zx;Pow(zx,2)
    PowZY.f = zy*zy;Pow(zy,2)
    While (PowZX+PowZY)<4 And colorcounter<#maxcolor
      tempx.f = PowZX - PowZY + cx
      zy      = 2 * PowZX + cy
      zx      = tempx
      colorcounter + 1
      PowZX = zx*zx;Pow(zx,2)
      PowZY = zy*zy;Pow(zy,2)
    Wend
    ColorBuffer(x,y) = colorcounter*$111111
  Next
Next

StartDrawing(ScreenOutput())
  Buffer      = DrawingBuffer()
  Pitch       = DrawingBufferPitch()
  PixelFormat = DrawingBufferPixelFormat()
  For y=0 To #ymax-1
    *Line.LONG = Buffer+y*Pitch
    For x=0 To #xmax-1
      *Line\l = ColorBuffer(x,y)
      *Line+4
    Next
  Next
StopDrawing()
FlipBuffers()
final = GetTickCount_()-begin

Repeat
  ExamineKeyboard()
Until KeyboardPushed(#PB_Key_Escape)
CloseScreen()

MessageRequester("TIME",StrU(final,2)+" ms",0)

Much better, IMHO.

Result:
18.667 - your version
05.318 - my 1st version ( 3.5 times faster )
00.120 - my 2nd version ( 155 times faster )

Maybe it helps a bit... but like i said,
there could be a problem with PixelFormat
on some graphics cards.

My rules for measurement:
- Start is before the loop
- End is after the image is generated _and_ displayed

You told me on IRC you like to see the image
while its generated, but with the fast version
this is not needed anymore - IMO.
120ms should be OK... and of course its much better on
faster CPUs (tested with my old PIII-600 internet PC only).

cya,
...Danilo

(registered PureBasic user)

BackupUser · Post by **BackupUser** » Mon Nov 25, 2002 9:17 am

Restored from previous forum. Originally posted by Froggerprogger.

Hi!
WolfgangS, you have two use the expression

Code: Select all

zy = 2 * zx * zy + cy

instead of

Code: Select all

zy      =2*Pow(zx,2)+cy

because of the following multiplikation-definition for complex numbers:
(a,b)*(c,d) = (a+b*i) * (c+d*i) = (a*c-b*d , a*d+b*c)

so here:
(zx, zy)Â² = (zxÂ²-zyÂ², 2*zx*zy)

THEN you'll get the REAL Mandelbrot Set - the german called 'ApfelmÃ¤nnchen'. BTW: Is 'ApfelmÃ¤nnchen' translated to 'Appleman' ?

To improve the performance a bit, I took the StartDrawing(), the StopDrawing() and the FlipBuffers() out of the For/Next.
Further there's now a time-counter and the OpenScreen-command uses xmax and ymax, and maxcolor os set to 25, and so the colorcounter-factor is set to $0A0A0A (use $0A0A10 for a cool blue&pink

:))

Okay, here's the modified code:

Code: Select all

xmax=1024ymax=768

maxcolor=25

leftside.f  =-2
top.f       =1.25
xside.f     =2.5
yside.f     =-2.5
xscale.f    =xside/xmax          
yscale.f    =yside/ymax

If InitSprite()=0 Or InitKeyboard()=0
  beep_(300,300):End:EndIf

OpenScreen(xmax,ymax,32,"")

time = GetTickCount_()

StartDrawing(ScreenOutput())
For y=1 To ymax
  For x=1 To xmax
    cx.f=x*xscale+leftside
    cy.f=y*yscale+top
    zx.f=0
    zy.f=0
    colorcounter=0
    
    While (Pow(zx,2)+Pow(zy,2)<4 And colorcounter<maxcolor)
      tempx.f =Pow(zx,2)-Pow(zy,2)+cx
      zy = 2 * zx * zy + cy
      zx      =tempx
      colorcounter+1
    Wend
    Plot(x,y,colorcounter*$0A0A10)
  Next
Next
StopDrawing()
FlipBuffers()

time = GetTickCount_() - time

Repeat
  ExamineKeyboard()
Until KeyboardPushed(#PB_Key_Escape)

Debug time
End

The calculation time lasts with this settings about 12 seconds on a 1,6 GHz-PC.

@fweil
It's not possible to avoid pixel-by-pixel-calculation, cause in a nonlinear function you cannot conclude from one result to another.
But you could calculate the symmetrie of the fractal - so here it is symmetric to the x-axis - and then draw two pixels with one calculation.

Oooops, I see, that some more people have posted, till I started, okay, I am with you::::)

Purebasic - what a nice name for a girl-friend

BackupUser · Post by **BackupUser** » Mon Nov 25, 2002 9:41 am

Restored from previous forum. Originally posted by Danilo.

Here my latest version:

Code: Select all

#xmax=640
#ymax=400

#maxcolor=15

#leftside.f  =-2
#top.f       =1.25
xside.f     =2.5
yside.f     =-2.5
xscale.f    =xside/#xmax          
yscale.f    =yside/#ymax

Dim ColorBuffer(#xmax,#ymax)

Structure LONG
  l.l
EndStructure

If InitSprite()=0 Or InitKeyboard()=0
  beep_(300,300):End:EndIf

OpenScreen(#xmax,#ymax,32,"")

begin = GetTickCount_()

StartDrawing(ScreenOutput())
  Buffer      = DrawingBuffer()
  Pitch       = DrawingBufferPitch()
  ;PixelFormat = DrawingBufferPixelFormat()

For y=0 To #ymax-1
  *Line.LONG = Buffer+y*Pitch
  For x=0 To #xmax-1
    cx.f = x * xscale + #leftside
    cy.f = y * yscale + #top
    zx.f = 0
    zy.f = 0
    colorcounter = 0
    
    PowZX.f = 0;zx*zx;Pow(zx,2)
    PowZY.f = 0;zy*zy;Pow(zy,2)
    While (PowZX+PowZY)<4 And colorcounter<#maxcolor
      tempx.f = PowZX - PowZY + cx
      zy      = 2 * PowZX + cy
      zx      = tempx
      colorcounter + 1
      PowZX = zx*zx;Pow(zx,2)
      PowZY = zy*zy;Pow(zy,2)
    Wend
      *Line\l = colorcounter * $111111
      *Line+4
  Next
Next

StopDrawing()
FlipBuffers()
final = GetTickCount_()-begin

Repeat
  ExamineKeyboard()
Until KeyboardPushed(#PB_Key_Escape)
CloseScreen()

MessageRequester("TIME",StrU(final,2)+" ms",0)

Now the drawing is directly in the loop and the
2 POWÂ´s before the While..Wend are changed to 0
because zx and zy are 0 at this time.
So we write better PowZX = 0 instead PowZX = 0 * 0

Because your code uses grayscale colors only,
there shouldnt be a problem on different video cards.
R, G and B have always the same value.

Latest results:
18.667 - your version
05.318 - my 1st version ( 3.5 times faster )
00.120 - my 2nd version ( 155 times faster )
00.100 - my 3rd version ( 186 times faster )

Optimized from 18 seconds to 100 milliseconds here,
and all without ASM - plain PureBasic.

Hope some guys here can optimize more, so
you get the fastest result.
Speed is very, very important for such algos.

cya,
...Danilo

(registered PureBasic user)

BackupUser · Post by **BackupUser** » Mon Nov 25, 2002 10:05 am

Restored from previous forum. Originally posted by Danilo.

Froggerprogger:
You can optimize your real ApfelmÃ¤nnchen too...

My Results:
0640x400 = 160 ms (Wolfgangs original screenmode)
0800x600 = 300 ms
1024x768 = 480 ms

But its grayscale now, like Wolfgangs original code...

Code: Select all

#xmax=1024
#ymax=768

#maxcolor=15

#leftside.f  =-2
#top.f       =1.25
xside.f     =2.5
yside.f     =-2.5
xscale.f    =xside/#xmax          
yscale.f    =yside/#ymax

Structure LONG
  l.l
EndStructure

If InitSprite()=0 Or InitKeyboard()=0
  beep_(300,300):End:EndIf

OpenScreen(#xmax,#ymax,32,"")

begin = GetTickCount_()

StartDrawing(ScreenOutput())
  Buffer = DrawingBuffer()
  Pitch  = DrawingBufferPitch()

For y= 0 To #ymax-1
  *Line.LONG = Buffer+y*Pitch
  For x= 0 To #xmax-1
    cx.f=x*xscale+#leftside
    cy.f=y*yscale+#top
    zx.f=0
    zy.f=0
    colorcounter=0
    
    PowZX.f = 0
    PowZY.f = 0
    While (PowZX+PowZYOf course Debugger OFF!

cya,
...Danilo
(registered PureBasic user)

BackupUser · Post by **BackupUser** » Mon Nov 25, 2002 10:29 am

Restored from previous forum. Originally posted by Froggerprogger.

12 seconds? 12 seconds?
220 ms!

(now )

Purebasic - what a nice name for a girl-friend

BackupUser · Post by **BackupUser** » Mon Nov 25, 2002 10:57 am

Restored from previous forum. Originally posted by Fangbeast.

Danilo your code crashes my compiler with some complex error and "memory could not be read"

Fangles woz ear orright den?

BackupUser · Post by **BackupUser** » Mon Nov 25, 2002 11:40 am

Restored from previous forum. Originally posted by WolfgangS.

HI!
>zy = 2 * zx * zy + cy
>instead of
>zy =2*Pow(zx,2)+cy
This is the wrong part. Thank you for the hint ...

>Danilo your code crashes my compiler with some complex error and "memory could not be read"
No problems here ...

What did you folx think, should we start a first round in a compilation with an other Basic Compiler ?

MFG
WolfgangS

BackupUser · Post by **BackupUser** » Mon Nov 25, 2002 5:51 pm

Restored from previous forum. Originally posted by pusztry.

Danilo your code crashes my compiler also. I am currently using Win2k and PB 3.4

- Ryan

WinXP, PIII 800 MHz, 512MB RAM, SB Live 5.1, NVidia TNT 2 Ultra

BackupUser · Post by **BackupUser** » Mon Nov 25, 2002 6:22 pm

Restored from previous forum. Originally posted by Pupil.

Originally posted by pusztry

Danilo your code crashes my compiler also. I am currently using Win2k and PB 3.4

Maybe your GFX card doesn't support the screen mode that Danilo is using? Try to change the line:

Code: Select all

OpenScreen(#xmax,#ymax,32,"")

to something like this to find out if this is the problem:

Code: Select all

If OpenScreen(#xmax,#ymax,32,"") = 0  debug "Screen mode not supported"
  End
EndIf

BackupUser · Post by **BackupUser** » Mon Nov 25, 2002 6:33 pm

Restored from previous forum. Originally posted by pusztry.

Yeh that is the problem.

- Ryan

WinXP, PIII 800 MHz, 512MB RAM, SB Live 5.1, NVidia TNT 2 Ultra

BackupUser · Post by **BackupUser** » Tue Nov 26, 2002 4:00 am

Restored from previous forum. Originally posted by pusztry.

Is there a way to get the systems max color Depth (OpenScreen(#xmax,#ymax,----32---,""))so that this works on all systems. I use the Intel 815 graphics at work all the time. this would make the program very dynamic. Just wondering.

PS. Is there a way to make it color?

- Ryan

WinXP, PIII 800 MHz, 512MB RAM, SB Live 5.1, NVidia TNT 2 Ultra

BackupUser · Post by **BackupUser** » Tue Nov 26, 2002 7:06 am

Restored from previous forum. Originally posted by fweil.

...,

by replacing the *Line\l = command with ie :

floatvalue.f = colorcounter / #maxcolor * $ff
*Line\l = RGB(floatvalue, floatvalue / 2, floatvalue / 4)

it makes some colors.

Play with it and also change the #maxcolor constant to different value to see effects.

The formula you have here may be changed to any complex other calculation to make nice effects.

You will also see that the computation time changes fast if you use higher #maxcolor (the fractal limit for computing each pixel).

Also the way to know the best color dpeth you can use is easy using a conditional OpenScreen command.

If OpenScreen(xsize, ysize, 32 ...
elseif OpenScreen(xsize, ysize, 24 ...
elseif OpenScreen(xsize, ysize, 16, ...
EndIf

should be the right way.

KRgrds

Francois Weil
14, rue Douer
F64100 Bayonne