Pages: 1 [2]



Author

Topic: Graphics  Bresenham's Line Drawing Algorithm, in MASM (Read 10391 times)

gabor
Member
Gender:
Posts: 321
Paper, pen for programming, computer for coding.

Hi!!
First I have to admit, I didn't read all the posts here, so maybe this post is not "uptodate". I was just wondering about this: As far as I know Bresenham's method for drawing lines is a beloved one, because it can be implemented fully with integer arithmetic. So what I don't really see, why the MMX and 64bit arithmetic?
Greets, Gábor



Logged




roticv
Guest

Hi!!
First I have to admit, I didn't read all the posts here, so maybe this post is not "uptodate". I was just wondering about this: As far as I know Bresenham's method for drawing lines is a beloved one, because it can be implemented fully with integer arithmetic. So what I don't really see, why the MMX and 64bit arithmetic?
Greets, Gábor
Optimisation for speed. MMX and SSE technology allows code (integer arithmetic) to be run in parallel and this speeds up the code. For instance using mmx technology you can add 2 pairs of dwords together in one instruction as opposed to requiring 2 adds to add up the 2 pairs of dwords.



Logged




gabor
Member
Gender:
Posts: 321
Paper, pen for programming, computer for coding.

Thx!
This is a good thing to keep in mind! Well, I need to extend my knowledge about MMX and SSE...
Greets, Gábor



Logged




daydreamer

when investigating in fastest generating spheremeshes on the fly I modified bresenhams circle algo to be recursive for each extra dimension, so it can draw spheres, even superspheres etc



Logged




AeroASM
Guest




Logged




daydreamer

recursive bresenhams circle algo, well it only makes a quarter of a circle circle PROC LOCAL @@rq :DWORD LOCAL @@yq :DWORD LOCAL @@xq :DWORD LOCAL @@temp :DWORD LOCAL @@color :DWORD pushad mov edx,[zzz] mov [@@temp],edx lea edi,[buffer] xor cx,cx mov dx,ax ;eax=radius mov bx,3 sub bx,dx .WHILE cx < dx ;call symplot pushad .IF [recurf]==0 ;render a slice of a sphere inc [recurf] ;mov [recurf],eax mov eax,ecx ;recursive call to create a sphere ;change z offset from cx mov [zcentref],edx call circle ;xor eax,eax ;mov [recurf],eax dec [recurf] .ELSE ;render a pixel xor ebx,ebx xor eax,eax mov ax,cx mov [@@xq],eax mov ax,dx mov [@@yq],eax fild @@xq fimul @@temp fidiv zcentref fistp @@xq fild @@yq fimul @@temp fidiv zcentref fistp @@yq mov ecx,[@@xq] mov edx,[@@yq] .IF edx>255 popad popad ret .ENDIF .IF ecx>255 popad popad ret .ENDIF mov bh,cl ;y*256 mov bl,dl ;x ;add ebx,8080h and ebx,0ffffh ;mov eax,0ffffffffh mov eax,[zcentref] mov [edi+ebx*4],al inc ebx mov [edi+ebx*4],al inc ebx mov [edi+ebx*4],al inc ebx mov [edi+ebx*4],al
mov bh,dl mov bl,cl ;add ebx,8080h and ebx,0ffffh mov eax,[zcentref] mov [edi+ebx*4],al inc ebx mov [edi+ebx*4],al inc ebx mov [edi+ebx*4],al inc ebx mov [edi+ebx*4],al .ENDIF popad .IF bx<zero mov ax,cx shl ax,2 add ax,6
.ELSE mov ax,cx sub ax,dx shl ax,2 add ax,10 dec dx .ENDIF inc cx add bx,ax .ENDW
.IF cx==dx ;call symplot .ENDIF
popad ret circle ENDP



Logged




Farabi
Neuroscientist Student
Member
Gender:
Posts: 2409
MASM+OpenGL Fanatic

Recursive algo? IS it a 3D circle? Any screen shot?



Logged




daydreamer

Recursive algo? IS it a 3D circle? Any screen shot?
it fast generate sphere, but it looks like crap, because I dont wanna add costly two atans/pixel to texturemap it I have a slower algo for that but intention was for generate spheremeshes on the fly



Logged




bao_ho
Guest

line algorithm without circle algorithm? ...let me paste it in <head> <script language="javascript"> function circle(r) { blackcell = "<td bgcolor=#000000><table><td></table>"; redcell = "<td bgcolor=#FF0000><table><td></table>"; rr = r+r; v = r*r; dyy = 1rr; dy = 2; str = "<table cellspacing=0 cellpadding=0>"; for(c2=0; c2<rr; c2++) { dxx = 1rr; dx = 2; v += dyy; dyy += dy; str += "<tr>"; for(c=0; c<rr; c++) { v += dxx; dxx += dx; str += v<0? redcell: blackcell; } } str += "</table>"; document.write(str); }; circle(30); </script> </head>



Logged




meeku
Guest

Howdy,
Just for interests sake, a DDA routine is faster than Bresenhams these days... well pretty much since the early pentiums. It's still a good programming excercise though IMO :)
It also makes doing antialiased lines a bit more straight forward.



Logged




BogdanOntanu
Global Moderator
Member
Gender:
Posts: 1154

It is completly imposible for DDA to be in any way faster than Bresenham Algorithm for line drawing.
A variation of Bresenham that exploits the warap arround to drop any comparations is presumably the fastest ever...
but honestly any decent Bresenham will eat alive DDA at breakfast...



Logged

Ambition is a lame excuse for the ones not brave enough to be lazy. http://www.oby.ro



meeku
Guest

The original Bresenhams line algorithm was superseeded by his run length slice version. This was considerably faster. However maintaining needless accumulators with error margin is unnecessary. Using a DDA which is reversed to operate with the minor axis as the independant one and draw slices with good ol fixed point is by far the fastest algorithm. It would give perfect accuracy for lines up to about 16,000 pixels in length... which is far longer than any line you're ever going to draw to screen.
The only thing that needs to be taken into account is to ensure that the runlength is divide between the first and last run to ensure the lines is A) balanced around it's center and B) does lead to incorrect lines with a single pixel end point.
I did an implementation of this a while ago with a fairly fast clipping implementation.. I think it had a few mmx optimisations in it as well.



Logged




meeku
Guest

An additional note, there are a huge number of optimisations that you can apply to this and other line algorithms with special cases for longer runs, treating steep and shallow lines seperately so you do vertical or horizontal slices, removing the divides for gradient calculations by preclipping and using a table (which has as many entries as your screen height dx / dy etc), special cases for "runs of runs" etc.. etc..



Logged




Peter.Hurrell
Guest

I havent gone through and understood your code yet, but I would like to explain a syystem I devised many years ago (PDP11).The system I called 'Linear digital Interpolator'. With the PDP11 multiply's had to be avoided (to slow)
Imagine six registers X . PartialX Y . Partial y DeltaX DeltaY Lets suppose now you wish to move forward 7 in X and 5 in Y (we will do it in decimal so its easier to understand. Set DeltaX to 7 and DeltaY to 5. If we add Delta x to PartialX ten times carrying from PartialX to X(and the same with Y) the X will INCREMENT to 7 while Y will increment to 5. Each time we increment X or Y we plot a new pixel. Note there is an assumed decimal point between X & Partial X (also Y). This will plot a straight line, however we need to set initial 'Partials' to 0.5 otherwise 4.99 will plot as pixel 4. If you were doing this on a 16 bit machine you could argue that you woulld have to do 64k additions. However if you shift both X & Y left till one of the MSD's is one and shift the multiplier (counter) right by the same amount, then you will have an increment every addition Note that this is 2 dimensions and could be expanded to 3. Also by cross coupling you can make the interpolator circular instead of linear.



Logged





Pages: 1 [2]



