From: andreasa@dhhalden.no (ANDREAS ARFF)
Newsgroups: alt.lang.asm
Subject: Re: Line drawing algorithm
Keywords: C, asm, graphics, line
Date: 5 Nov 92 16:30:38 GMT
Organization: Ostfold College

In article <Bx4741.1p6@mach1.wlu.ca> sava4711@mach1.wlu.ca (ken savage u) writes:
>From: sava4711@mach1.wlu.ca (ken savage u)
>Subject: Line drawing algorithm
>Date: Tue, 3 Nov 1992 00:38:25 GMT
>Keywords: C, asm, graphics, line
>Re   : Line drawing algorithm
>
>I've posted this is comp.lang.c (or tried to), but a solution in .ASM is
>just as good with me!!  ...
>
>  Here's my problem:  I'm trying to find a fast line-drawing algorithm (in C)
>for VGA graphics mode.  The problem is not placing the pixel on the screen,
>but rather deciding WHERE to put it.  I've thought up of several ideas, given
>
>void line( int x1, int y1, int x2, int y2 )
>
>1) recursively call line( x1, y1, (x1+x2) / 2, (y1+y2) / 2 ) until the line
>   is drawn, and line( (x1+x2) / 2, (y1+y2) / 2, x2, y2 )
>
>2) use the linear function y = mx+b and trace the line that way
>
>3) starting at x1,y1   find the "best pixel" to plot and plot it.  From this
>   best pixel, do the same, finding the next best pixel, until x2,y2 is it.
>
>The problems:
>
>1)  The line is not very accurate - lotsa jaggies due to rounding errors
>
>2)  The line is not always solid, and making it solid slows the drawing down
>
>3)  SLOOOOOOOOWWWWWW  when speed is crucial
>
>  Does anyone have source code for a line drawing algorithm that does not have
>floating point calculations, and is THE best line one can get with no jaggies?
>The source code can be in 80x86 assembler (68000 if the ALGORITHM is spelled
>out), BASIC, Pascal or C, with (of course) a preference for ASM or C.  You
>can post the answer or mail me directly at the address above.
>
>  Thanks for any responses!!
>                                            ]<en /-
>                                                 \avage
>                                                _/


1) Recursive calls aren't very fast. Don't do it.

2) A better approach, but not good enough.

3) Slow

I don't have any asm code to give you, but a proposal on how to do it.

1) There are 8 directions a line could go.
   Horizontal (from left to right and vice versa).
   Vertical (from top to bottom -------"--------).
   Diagonaly in any direction from any side to any side.

   1/2) Check if line is horisontal.
        If it is, just decrement/increment the x counter.
   3/4) Check if line is vertical.
        Do same as under 1, except use the y counter.

   n = x/y
   For each increment/decrement of x, draw n pixels upward/downward.
   You can use 4 different algorithms to speed it up.

   5) Upward. Increment x, draw n pixles upward, increment y

   6) Upward. Decrement x, draw n pixles upward, increment y

   7) Downward. Increment x, draw n pixels downward, decrement y

   8) Downward. Decrement x, draw n pixels downward, decrement y

       
                     3/4
                7 \   |   /8
                   \  |  /
                    \ | /
              1/2____\|/____
                     /|\
                    / | \
                   /  |  \
                  /   |   \ 
                 5         6

This should be quite fast.
If anybody else has got another way of doing it, I'd 
really like to see it. Cause I'm also looking for a very 
fast line-drawing algorithm.
But test it out.

Arff

"Also for the not religous confessor, there is a mystery of higher values,
who's birth mankind - to the last - builds upon. They are indisputible. And 
often disregarded. Seldom you hear them beeing prized, as seldom as you hear 
a seeing man prizeing what he sees." Per Lagerkvist, The Fist 
(Free translation from Swedish)
              --Andreas Arff  andreasa@dhhalden.no--
Newsgroups: alt.lang.asm