🔒 Locked

Project: fractal generating program

Started by Robin S Sep 7, 2006 at 8:17 PM 17 replies 1.5k views

Original Post

Sep 7, 2006 at 8:17 PM

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]

LessBread

Sep 7, 2006 at 8:29 PM

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.

Robin S

Sep 7, 2006 at 8:42 PM

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.

Ryan_001

Sep 7, 2006 at 8:50 PM

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.

Robin S

Sep 7, 2006 at 9:11 PM

Thanks very much! I'll make a start as soon as I have a free day or two.

Moe

Sep 7, 2006 at 9:11 PM

Quote:
Original post by Robin S
I would like to learn C++, but don't have a compiler for it...

Now you do. Unless you are on dial up or something).

Ravyne

Sep 7, 2006 at 9:35 PM

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.

Robin S

Sep 8, 2006 at 12:26 PM

Thanks for the advice. I'll definitely have a go at writing the program up in C++ first, when I get the time.

Robin S

Sep 23, 2006 at 5:56 PM

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 ThenColor 0,0,0ElseIf u<256 ThenColor 255,u,0ElseIf u<511 ThenColor 510-u,255,0ElseIf u<766 ThenColor 0,255,u-510ElseIf u<1021 ThenColor 0,1020-u,255ElseIf u<1276 ThenColor u-1020,0,255ElseColor 255,0,1530-uEndIf

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]

dbzprogrammer

Sep 23, 2006 at 7:52 PM

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 statementselse if(u < 256)  color = {255,u,0};else if(u < 511)  color = {510-u,255,0};//etc...

Robin S

Sep 24, 2006 at 7:49 AM

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;}

Robin S

Sep 24, 2006 at 8:22 AM

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?

Robin S

Sep 24, 2006 at 9:25 AM

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;}

Robin S

Sep 24, 2006 at 9:50 AM

Ah, thanks. Can't believe I missed that!

Now, to continue with debugging...

Robin S

Sep 24, 2006 at 10:22 AM

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?

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.