hacker@nucleus.UUCP (Thomas Hacker) (01/01/88)
I'm working on a project that requires a very "quick" line drawing
algorithm (i.e. Draw (x1, y1, x2, y2)). The fastest I know of is
Bresenham's algorithm, which is a DDA using integer arithmatic
instead of float. If anyone knows of a superior algorithm, please
let me know.
Thank You
Thomas Hacker
Academic Computer Services
Oakland Universitygmg@yendor.UUCP (Gary Godfrey) (01/02/88)
in article <174@nucleus.UUCP>, hacker@nucleus.UUCP (Thomas Hacker) says: > > > I'm working on a project that requires a very "quick" line drawing > algorithm (i.e. Draw (x1, y1, x2, y2)). The fastest I know of is > Bresenham's algorithm, which is a DDA using integer arithmatic > instead of float. If anyone knows of a superior algorithm, please > let me know. > > Thank You > > Thomas Hacker > Academic Computer Services > Oakland University
gmg@yendor.UUCP (Gary Godfrey) (01/02/88)
in article <174@nucleus.UUCP>, hacker@nucleus.UUCP (Thomas Hacker) says: > > > I'm working on a project that requires a very "quick" line drawing > algorithm (i.e. Draw (x1, y1, x2, y2)). The fastest I know of is > Bresenham's algorithm, which is a DDA using integer arithmatic > instead of float. If anyone knows of a superior algorithm, please > let me know. > > Thank You > > Thomas Hacker > Academic Computer Services > Oakland University I'm not sure what DDA stands for, but the following is a short 'C' fragment that will draw a line. To make it easier to write, I'm going to assume that x1<x2, y1<y2, and (x2-x1) > (y2-y1). If you want to be fast but code inefficient, you can write eight different routines for the eight different types. I usually use two: one for dx > dy, and another for dy > dx. draw (x1, y1, x2, y2) int x1,y1,x2,y2; { int tmp,dy,dx; dy = y2 - y1; /* change in y */ dx = x2 - x1; /* change in x */ tmp = dy / 2; /* kind of a running total. the "/2" should make the line symmetrical */ for (; x2 > x1 ; x1++) { plot(x1,y1); /* standard plot */ tmp+=dy; if (tmp >= dx) { tmp-=dx; y1++; } } } I'm writing this off the top of my head. If it doesn't work, it's at least fairly close. I think. Another thing you might want to consider if you're working close to the hardware, is to mix the plot calculation routines into the line drawing routine. For instance, if your screen has 1024 pixels across, and one bit/pixel, the calculation for the memory location/plotting is: mem = VIDEO_RAM_OFFSET + y * 128 + (x / 8); bit = 2 ^ (x & 3); *mem |= bit; /* assume set bit = pixel on */ Kind of a bad way of doing things. However, instead of doing this calculation every time for every pixel, you can initialize mem and bit before entering the line drawing loop. Then, inside the loop, you replace the y++ with mem+=128, and the x++ with: bit/=2; /* shift right -- assume highest bit is leftmost */ if (! bit) { /* if the bit disappeared */ bit = 128; /* set back to leftmost */ mem++; /* and move memory over... */ } I NEEDED to do this on my old TRS-80 to get any speed at all. It required a division by three and two multiplys for every pixel! More fun this way anyway. ============================================================================= You know, if I had a dime for every time I heard the word "the", I would have an awful lot of dimes. Gary Godfrey - ACT, Reston, VA Phone: (703)471-9433 UUCP: ..!mimsy!{prometheus,hqda-ai}!yendor!gmg
ksbooth@watcgl.waterloo.edu (Kelly Booth) (01/03/88)
In article <51@yendor.UUCP> gmg@yendor.UUCP (Gary Godfrey) writes: . . . >I'm not sure what DDA stands for, but the following is a short 'C' fragment . . . >I'm writing this off the top of my head. If it doesn't work, it's at >least fairly close. I think. Another thing you might want to consider . . . Do we need stuff like this posted to the world? This was a follow-up posting to an article that cited Bresenham's algorithm and Foley and Van Dam's book as references. Anyone reading F&VD can find out what DDA means. This seems the minimal effort one should make before posting an article that purports to have technical information.
cm26+@andrew.cmu.edu (Curt McDowell) (01/11/88)
>Do we need stuff like this posted to the world? This was a follow-up posting >to an article that cited Bresenham's algorithm and Foley and Van Dam's book >as references. Anyone reading F&VD can find out what DDA means. This seems >the minimal effort one should make before posting an article that purports >to have technical information. Actually, I think it's responses such as yours that the world does not need. They're SUCH a pain, especially when they're wrong. The post you are maligning happened to contain an important point not to be found in Foley (and certainly not in your so enlightening post). It's the idea of building the point-plot routine into the line drawing routine. I have 68000 routines for Suns that uses this technique, besides splitting the algorithm into 8 cases, yielding a speedup factor of at least 50 or 60 times over the bare one mentioned in Foley. The exact algorithm may be found in Foley, but details such as this may not. I'd just hate to see people stop posting useful stuff on account of people with your negative outlook. Curt McDowell Carnegie-Mellon U. P.S. I also owned a TRS-80 and I agree with Gary. P.P.S. DDA stands for differential something or other, right?
andrey@arizona.edu (Andrey K. Yeatts) (01/12/88)
A DDA is a "Digital Differential Analyzer". They come in any number
of flavors for your favorite parametrized curve (or object).
--
Andrey Yeatts
andrey@arizona.edu
{allegra,cmcl2,ihnp4,noao}!arizona!andreygfs@abvax.UUCP (Greg F. Shay) (01/12/88)
I believe DDA stands for Digital Difference Analyzer. I agree with the defense of all sincere contributions to the net. The span of readership is from expert to novice. There is no expert who was once not a novice, and so should be tolerant of whatever level discussions he/she may observe. Greg
blob@calgary.UUCP (Brian Wyvill) (01/13/88)
In article <gVu4-3y00WEDslk09=@andrew.cmu.edu>, cm26+@andrew.cmu.edu (Curt McDowell) writes: > > > I have 68000 routines for Suns that uses this technique, besides splitting the > algorithm into 8 cases, yielding a speedup factor of at least 50 or 60 times > over > the bare one mentioned in Foley. > > The exact algorithm may be found in Foley, but details such as this may not. > > Curt McDowell > Carnegie-Mellon U. This sounds like a fairly ambitious claim. There was a recent article in Grapics and Image Processing by Rokne and Wu which produced a factor of two over Bresenham's and I have implemented a variation on this which gives a speed up close to 4. One of our students is close to producing a speed of between 7 and 8. I would be interested to hear details of your algorithm. -- Brian Wyvill ..!{ubc-vision,ihnp4}!alberta!calgary!blob
840493n@aucs.UUCP (Bill Nickerson) (01/14/88)
dda - digital differential analysis.