Sign in to follow this  
Robin S

Project: fractal generating program

Recommended Posts

The first language I learnt was Blitz Basic, which is all very well for writing simple 2d games but, for a mathematically-orientated application such as the first program I wrote, it's next to useless; because of all the unneccessary operations listed in its compiler, it takes anywhere up to an hour to render a desktop-resolution image. I thought I'd overcome the problem by rewriting the program in assembler but, being something of a novice at programming, wasn't really prepared for the sudden change in level required. I am certain that assembler is ideal for my purposes, but issues such as the fact that almost all the numbers I have to deal with are 2 words long and that I have no idea how to even read from a file mean that I am somewhat at a loss. For those of you who know Blitz, the program in its current form is as follows:
a=Input$("order?")
Dim b#(a-1)
Dim c#(a-1)
Dim d#(a)
Dim e#(a)
Dim f#(a)
Dim g#(a)
Dim h#(a)
Dim i#(a)
For j=0 To a-1
b#(j)=Input$("Real index #"+(j+1)+"?")
c#(j)=Input$("Imaginary index #"+(j+1)+"?")
Next
d#(a)=Input$("Real starting value for A?")
e#(a)=Input$("Imaginary starting value for A?")
For j=0 To a-1
d#(j)=Input$("Real coefficient of z^"+b#(j)+"+"+c#(j)+"i For A?")
e#(j)=Input$("Imaginary coefficient of z^"+b#(j)+"+"+c#(j)+"i for A?")
Next
f#(a)=Input$("Real starting value for O?")
g#(a)=Input$("Imaginary starting value for O?")
For j=0 To a-1
f#(j)=Input$("Real coefficient of z^"+b#(j)+"+"+c#(j)+"i for O?")
g#(j)=Input$("Imaginary coefficient of z^"+b#(j)+"+"+c#(j)+"i for O?")
Next
h#(a)=Input$("Real starting value for P?")
i#(a)=Input$("Imaginary starting value for P?")
For j=0 To a-1
h#(j)=Input$("Real coefficient of z^"+b#(j)+"+"+c#(j)+"i for P?")
i#(j)=Input$("Imaginary coefficient of z^"+b#(j)+"+"+c#(j)+"i for P?")
Next
k#=Input$("width?")
l#=Input$("height?")
m=Input$("iterations?")
n=Input$("starthue?")
o=Input$("huegap?")
For j=0 To a
p#=p#+(f#(j)-d#(j))^2+(g#(j)-e#(j))^2
q#=q#+(h#(j)-f#(j))^2+(i#(j)-g#(j))^2
Next
p#=Sqr(p#/q#)
For j=0 To a
h#(j)=p#*(h#(j)-f#(j))+f#(j)
i#(j)=p#*(i#(j)-g#(j))+g#(j)
f#(j)=2*f#(j)-h#(j)-d#(j)
g#(j)=2*g#(j)-i#(j)-e#(j)
h#(j)=(h#(j)-d#(j))/k#-f#(j)
i#(j)=(i#(j)-e#(j))/k#-g#(j)
f#(j)=f#(j)/l#
g#(j)=g#(j)/l#
Next
Graphics k, l
For r=0 To k-1
For s=0 To l-1
p#=d#(a)
q#=e#(a)
t=-1
While t<m-1 And p#^2+q#^2<=4
u#=p#^2+q#^2
v=Sgn(u#)
w#=Log(u#)/2
u#=ACos(p#/Sqr(u#))*Sgn(q#)
p#=0
q#=0
For j=0 To a-1
If b#(j)=0 And c#(j)=0 Then
p#=p#+d#(j)
q#=q#+e#(j)
ElseIf v=1 Then
x#=Exp(b#(j)*w#-c#(j)*u#)
y#=b#(j)*u#+c#(j)*w#
z#=x#*Cos(y#)
x#=x#*Sin(y#)
p#=p#+d#(j)*z#-e#(j)*x#
q#=q#+e#(j)*z#+d#(j)*x#
EndIf
Next
t=t+1
Wend
u=-1
If p#^2+q#^2>4 Then
u=(n+t*o)Mod 1530
EndIf
If u=-1 Then
Color 0,0,0
ElseIf u<256 Then
Color 255,u,0
ElseIf u<511 Then
Color 510-u,255,0
ElseIf u<766 Then
Color 0,255,u-510
ElseIf u<1021 Then
Color 0,1020-u,255
ElseIf u<1276 Then
Color u-1020,0,255
Else
Color 255,0,1530-u
EndIf
Plot r,s
For j=0 To a
d#(j)=d#(j)+f#(j)
e#(j)=e#(j)+g#(j)
Next
Next
For j=0 To a
d#(j)=d#(j)+h#(j)
e#(j)=e#(j)+i#(j)
Next
Next
SaveBuffer(FrontBuffer(),"fractal.bmp")
To test it, type in the following inputs: 2 0 0 2 0 0 0 -2.25 1.25 1 0 0 0 -0.6875 0 1 0 0 0 0.875 1.25 1 0 1024 768 0 1500 The computer should enter full-screen graphics mode, generate a coloured image of the Mandelbrot set in about 10 seconds (depending on your computer's specifications) and then save it as fractal.bmp in the same directory as the compiled program. This is more or less what I want it to do, although it would be nice if it could render the image in the background or, better still, write straight to a bitmap file pixel by pixel. Also, I would prefer it to read the inputs from a csv file rather than needing an input dialog; this way, you would be able to run the program in a directory with the appropriate csv file, and generate a bitmap image file without anything actually appearing on the screen. The main problem, though, is this: the program, as it currently stands, runs ridiculously slowly. That's why I wanted to rewrite it in some form of assembler, of course, but I'm at a bit of a loss as to where to begin, never having written in any sort of low-level language before. Any tips or suggestions would be very much appreciated. Thanks, Robin :) [Edited by - Robin S on September 23, 2006 6:45:06 PM]

Share this post


Link to post
Share on other sites
Jumping from Blitz Basic to Assembler is quite a leap. You might want to try a higher level language instead, like C or C++, Pascal or Java. Mandlebrot sets tend to take a while to render, but an hour seems quite excessive (unless your PC is 10 years old).

Here are a few links to code for Mandlebrot sets. In pascal, in java, and in several different languages.

Share this post


Link to post
Share on other sites
1 hour was the length of time needed for more complicated fractals (which required tens of thousands of iterations per pixel); the Mandelbrot set took about 10 seconds to render, but this is still quite excessive compared with some applets I have seen which can generate it more or less instantly.

I would like to learn C++, but don't have a compiler for it, and I understand manuals for it tend to be huge, which is a bit daunting. Thanks for the advice, though - I'll see what I can do.

Share this post


Link to post
Share on other sites
Here's a link the the Microsoft Visual Studio Express page:

http://msdn.microsoft.com/vstudio/express/

They have 4 different compilers for download, C++, C#, VB, and J#. They are all free, easy to install, and the Visual Studio IDE is one of the best IDE's around. If you're more of an open source kinda guy u can pick up DJGPP (a GNU C/C++ compiler) at:

http://www.delorie.com/

Just follow the DJGPP link to the zip picker link.

There's also a ton of other C++ compilers out there for free, if those two aren't to your liking. As far as learning C++, well GameDev is a good place to start.

Share this post


Link to post
Share on other sites
I'd avoid trying to do this in straight-up assembly. In fact, its much more trouble than its worth to write a windows application entirely in ASM. I would recomend C or C++, the Visual C++ Express Edition already mentioned is an excelent compiler and is only second to Intel's own compiler in respect to its optimization technology. After you get a working version in straight C/C++, you can optimize the inner workings with inline assembly if you still find it to be to slow.

Truth be told, however, its unlikely you will be able to beat the compiler at optimizing your code since you're an ASM rookie. Compilers really are that good these days, as they will beat 90% of programmers 90% of the time. For someone not skilled in assembly, attempting to optimize code by converting it to assembly yourself will likely result in two things 1) much learned about assembly and 2) slower program execution. The 10% of programmers that DO beat the assembler, most often do so by exploiting knowlege of the algorithm that the compiler does not have, such as exploiting parallelism to compute multiple results at once. An example of this would be to convert a parallelizable algorithm to make use of the SSE instruction set. A smart programmer is better able to exploit parallelism than most compilers.


To make a long story short:

1) C/C++, get this working and evaluate the speed.
2) Optimize the algorithm, then evaluate the speed again.
3) Only then, if you're still unhappy with the speed, should you consider ASM.

Share this post


Link to post
Share on other sites
Ok, so I've started writing up the program in C. It hasn't taken long, but I've got stuck on the subject of output. Before I develop the program further, I want to be able to do in C what I did in Blitz: that is, output to a bitmap file. Here is the program so far (compiled using GCC):

#include <math.h>
#include <stdio.h>
int main(void)
{
unsigned short a;
printf("order? ");
scanf("%i",&a);
{
double b[a-1],c[a-1],d[a],e[a],f[a],g[a],h[a],i[a],p,q,u,x,w,y,z;
unsigned short j,k,l,n,o,r,s,v;
unsigned m,t;
for(j=0;j<a;j++)
{
printf("real index #%i",j+1);
printf("? ");
scanf("%lf",&b[j]);
printf("imaginary index #%i",j+1);
printf("? ");
scanf("%lf",&c[j]);
}
printf("real starting value for A? ");
scanf("%lf",&d[a]);
printf("imaginary starting value for A? ");
scanf("%lf",&e[a]);
for(j=0;j<a;j++)
{
printf("real coefficient of z^%lf",b[j]);
printf("+%lf",c[j]);
printf("i for A? ");
scanf("%lf",&d[j]);
printf("imgainary coefficient of z^%lf",b[j]);
printf("+%lf",c[j]);
printf("i for A? ");
scanf("%lf",&e[j]);
}
printf("real starting value for O? ");
scanf("%lf",&f[a]);
printf("imaginary starting value for O? ");
scanf("%lf",&g[a]);
for(j=0;j<a;j++)
{
printf("real coefficient of z^%lf",b[j]);
printf("+%lf",c[j]);
printf("i for O? ");
scanf("%lf",&f[j]);
printf("imgainary coefficient of z^%lf",b[j]);
printf("+%lf",c[j]);
printf("i for O? ");
scanf("%lf",&g[j]);
}
printf("real starting value for P? ");
scanf("%lf",&h[a]);
printf("imaginary starting value for P? ");
scanf("%lf",&i[a]);
for(j=0;j<a;j++)
{
printf("real coefficient of z^%lf",b[j]);
printf("+%lf",c[j]);
printf("i for P? ");
scanf("%lf",&h[j]);
printf("imgainary coefficient of z^%lf",b[j]);
printf("+%lf",c[j]);
printf("i for P? ");
scanf("%lf",&i[j]);
}
printf("width? ");
scanf("%i",&k);
printf("height? ");
scanf("%i",&l);
printf("iterations? ");
scanf("%i",&m);
printf("starthue? ");
scanf("%i",&n);
printf("huegap? ");
scanf("%i",&o);
p=q=0;
for(j=0;j<=a;j++);
{
p=p+(f[j]-d[j])*(f[j]-d[j])+(g[j]-e[j])*(g[j]-e[j]);
q=q+(h[j]-f[j])*(h[j]-f[j])+(i[j]-g[j])*(i[j]-g[j]);
}
p=sqrt(p/q);
for(j=0;j<=a;j++)
{
h[j]=p*(h[j]-f[j])+f[j];
i[j]=p*(i[j]-g[j])+g[j];
f[j]=2*f[j]-h[j]-d[j];
g[j]=2*g[j]-i[j]-e[j];
h[j]=(h[j]-d[j])/k-f[j];
i[j]=(i[j]-e[j])/k-g[j];
f[j]=f[j]/l;
g[j]=g[j]/l;
}
/**************************
*CREATE BITMAP HEADER HERE*
**************************/
for(r=0;r<k;r++)
{
for(s=0;s<l;s++)
{
p=d[a];
q=e[a];
for(t=0;t<m;t++)
{
u=p*p+q*q;
v=0;
if(u>0)
{
v=1;
w=log(u)/2;
u=atan2(q,p);
}
p=q=0;
for(j=0;j<a;j++)
{
if(b[j]==0&&c[j]==0)
{
p=p+d[j];
q=q+e[j];
}
else if(v==1)
{
x=exp(b[j]*w-c[j]*u);
y=b[j]*u+c[j]*w;
z=x*cos(y);
x=x*sin(y);
p=p+d[j]*z-e[j]*x;
q=q+e[j]*z+d[j]*x;
}
}
if(p*p+q*q>4)
{
v=n+j*o%1530;
break;
}
v=-1;
}
/****************
*MAKE PIXEL HERE*
****************/
for(j=0;j<=a;j++)
{
d[j]=d[j]+f[j];
e[j]=e[j]+g[j];
}
}
for(j=0;j<=a;j++)
{
d[j]=d[j]+h[j];
e[j]=e[j]+i[j];
}
}
}
return 0;
}


The pixel's properties are determined by the values of r, s and v: r is the x co-ordinate, s is the inverse of the y co-ordinate i.e. it is 0 at the top of the image, and v determines the colour according to the following code from the Blitz program:

If u=-1 Then
Color 0,0,0
ElseIf u<256 Then
Color 255,u,0
ElseIf u<511 Then
Color 510-u,255,0
ElseIf u<766 Then
Color 0,255,u-510
ElseIf u<1021 Then
Color 0,1020-u,255
ElseIf u<1276 Then
Color u-1020,0,255
Else
Color 255,0,1530-u
EndIf


where the numbers represent r,g,b in that order.

Unfortunately, I have no idea how to do this in C. Could anyone help, please?

[Edited by - Robin S on September 24, 2006 7:56:04 AM]

Share this post


Link to post
Share on other sites
First, I didn't read too deeply into it because I'm a bit confused, as you're variables aren't too descriptive...

Anyways, are you looking for if/else if statements?

if(u == -1)
{ color = {0,0,0}; } //You can leave brackets in or out for 1 line statements
else if(u < 256)
color = {255,u,0};
else if(u < 511)
color = {510-u,255,0};
//etc...

Share this post


Link to post
Share on other sites
The inputs are nondescriptive because some of them (particularly the arrays) are used for multiple purposes in order to save on memory. It's not so much how to use if/else statements that I'm looking for - I want to know how to write to a bitmap file. In the Blitz version of the program I did this by choosing a colour, then drawing that pixel on the screen, then finally when all pixels were drawn the program saved the buffer on which the image had been drawn. However, I'd prefer to be able to write to an image file without having to display the image on the screen.

Even more ideal would be to write straight to a PNG, but I'll stick with simple things first.

To give a rough idea of what the program does:

//take inputs;
//do some maths;
//create and set up 24-bit bitmap file, dimensions k by l, ready to write (not yet done);
for(r=0;r<k;r++)
{
for(s=0;s<l;s++)
{
//do some more maths;
//create pixel at r,l-s-1 coloured using v as in above post (not yet done);
//do some more maths;
}
//do some more maths;
}

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:

The inputs are nondescriptive because some of them (particularly the arrays) are used for multiple purposes in order to save on memory.


Welcome to the nineties: don't optimize at the expense of clarity unless you know it's slowing your program down. :)

Quote:
I want to know how to write to a bitmap file.
Standard C++ is pretty bare bones: you need a library that handles the tedium of writing bmp's for you. Take a look at this, maybe it's adequate for your needs:

http://sourceforge.net/projects/easybmp/

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Sorry, I thought you were using C++ instead of C.

I'd strongly reccommend going (at least) the C++ route: it provides the STL which is immensely more convenient than straight C arrays for doing numerical work (it handles dynamic resizing for you, gives you nice abilities for iterating, + loads of other nice containers).

Share this post


Link to post
Share on other sites
I probably will rewrite it in C++ once I have a working version in C. I'll need to so that things like the GUI are easier to write. For now, though, I just want a version that works faster than the one in Basic. Thanks for the advice, though. I'll keep what you said in mind.

Meanwhile, could anyone possibly help me towards getting the C version finished?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Look at the link I provided!

just compile your C program as C++ (it's mostly backward compatible) and use the BMP library to spit it out. There's even an example mandelbrot generator on the site that does EXACTLY what you want to do:

http://easybmp.sourceforge.net/samples.html

Share this post


Link to post
Share on other sites
Thanks - although what I want to do involves more than just Mandelbrot sets.

Meanwhile, I seem to be having problems with loops. The following code prints the number "3", when from what I understand it should print 012. Can anyone explain?

int main(void)
{
unsigned short j;
for(j=0;j<=2;j++);
{
printf("%i",j);
}
return 0;
}

Share this post


Link to post
Share on other sites
I've encountered another problem: scanf appears to reset the values of some of my variables to 0, for a reason that I don't understand. For example:

		printf("width? ");
scanf("%i",&k);
printf("height? ");
printf("%i",k); // prints fine
scanf("%i",&l);
printf("%i",k); // comes out as 0

Can anyone explain why, or how to rectify this problem?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this