The MASM Forum Archive 2004 to 2012
Welcome, Guest. Please login or register.
September 03, 2014, 04:31:01 AM

Login with username, password and session length
Search:     Advanced search
128553 Posts in 15254 Topics by 684 Members
Latest Member: mottt
* Home Help Search Login Register
+  The MASM Forum Archive 2004 to 2012
|-+  General Forums
| |-+  The Laboratory (Moderator: Mark_Larson)
| | |-+  Graphics - Bresenham's Line Drawing Algorithm, in MASM
« previous next »
Pages: 1 [2] Print
Author Topic: Graphics - Bresenham's Line Drawing Algorithm, in MASM  (Read 5849 times)
gabor
Member
*****
Gender: Male
Posts: 321


Paper, pen for programming, computer for coding.


Re: Graphics - Bresenham's Line Drawing Algorithm, in MASM
« Reply #15 on: April 06, 2005, 10:19:31 AM »

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


Email
Re: Graphics - Bresenham's Line Drawing Algorithm, in MASM
« Reply #16 on: April 06, 2005, 12:11:33 PM »

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: Male
Posts: 321


Paper, pen for programming, computer for coding.


Re: Graphics - Bresenham's Line Drawing Algorithm, in MASM
« Reply #17 on: April 07, 2005, 07:53:12 AM »

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
Member
*****
Posts: 616


Re: Graphics - Bresenham's Line Drawing Algorithm, in MASM
« Reply #18 on: May 05, 2005, 12:03:54 PM »

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


Email
Re: Graphics - Bresenham's Line Drawing Algorithm, in MASM
« Reply #19 on: May 05, 2005, 01:44:47 PM »

LoL 8D graphics engine using Cayley's octonions!  BigGrin BigGrin wink
Logged
daydreamer
Member
*****
Posts: 616


Re: Graphics - Bresenham's Line Drawing Algorithm, in MASM
« Reply #20 on: June 22, 2005, 06:54:08 AM »

recursive bresenhams circle algo, well it only makes a quarter of a circle

Code:
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: Male
Posts: 2409


MASM+OpenGL Fanatic


Re: Graphics - Bresenham's Line Drawing Algorithm, in MASM
« Reply #21 on: June 23, 2005, 12:13:55 AM »

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

Those who had universe knowledges can control the world by a micro processor.
http://www.wix.com/farabio/firstpage

"Etos siperi elegi"
daydreamer
Member
*****
Posts: 616


Re: Graphics - Bresenham's Line Drawing Algorithm, in MASM
« Reply #22 on: June 24, 2005, 06:05:26 AM »

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


Email
Re: Graphics - Bresenham's Line Drawing Algorithm, in MASM
« Reply #23 on: July 13, 2005, 07:20:43 PM »

line algorithm without circle algorithm?  wink ...let me paste it in  ThumbsUp


<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 = 1-rr;
   dy = 2;

   str = "<table cellspacing=0 cellpadding=0>";
   for(c2=0; c2<rr; c2++)
   {
      dxx = 1-rr;
      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


Email
Re: Graphics - Bresenham's Line Drawing Algorithm, in MASM
« Reply #24 on: July 19, 2005, 01:34:23 PM »

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 anti-aliased lines a bit more straight forward.
Logged
BogdanOntanu
Global Moderator
Member
*****
Gender: Male
Posts: 1154


Re: Graphics - Bresenham's Line Drawing Algorithm, in MASM
« Reply #25 on: July 19, 2005, 05:34:15 PM »

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


Email
Re: Graphics - Bresenham's Line Drawing Algorithm, in MASM
« Reply #26 on: July 20, 2005, 08:52:30 AM »

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 run-length 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


Email
Re: Graphics - Bresenham's Line Drawing Algorithm, in MASM
« Reply #27 on: July 20, 2005, 08:57:35 AM »

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 pre-clipping 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


Email
Re: Graphics - Bresenham's Line Drawing Algorithm, in MASM
« Reply #28 on: July 27, 2005, 05:50:11 PM »

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] Print 
« previous next »
Jump to:  

Powered by MySQL Powered by PHP The MASM Forum Archive 2004 to 2012 | Powered by SMF 1.0.12.
© 2001-2005, Lewis Media. All Rights Reserved.
Valid XHTML 1.0! Valid CSS!