Graphics - Bresenham's Line Drawing Algorithm, in MASM

gabor · 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

roticv · April 06, 2005, 12:11:33 PM

Quote from: gabor 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

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.

gabor · 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

daydreamer · 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

AeroASM · May 05, 2005, 01:44:47 PM

LoL 8D graphics engine using Cayley's octonions! :bg :bg :wink

daydreamer · June 22, 2005, 06:54:08 AM

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

Code Select


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

Farabi · June 23, 2005, 12:13:55 AM

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

daydreamer · June 24, 2005, 06:05:26 AM

Quote from: Farabi on June 23, 2005, 12:13:55 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

bao_ho · July 13, 2005, 07:20:43 PM

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

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

meeku · 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.

BogdanOntanu · 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...

meeku · 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.

meeku · 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..

Peter.Hurrell · 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.

News:

Graphics - Bresenham's Line Drawing Algorithm, in MASM

gabor

roticv

gabor

daydreamer

AeroASM

daydreamer

Farabi

daydreamer

bao_ho

meeku

BogdanOntanu

meeku

meeku

Peter.Hurrell