home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / alt / sys / amiga / demos / 1153 < prev    next >
Encoding:
Internet Message Format  |  1992-09-15  |  2.5 KB
  1. Path: sparky!uunet!haven.umd.edu!darwin.sura.net!spool.mu.edu!uwm.edu!rutgers!cbmvax!cbmehq!cbmger!peterk
  2. From: peterk@cbmger.de.so.commodore.com (Dr Peter Kittel Germany)
  3. Newsgroups: alt.sys.amiga.demos
  4. Subject: Re: Drawing lines
  5. Message-ID: <9588@cbmger.de.so.commodore.com>
  6. Date: 15 Sep 92 07:52:02 GMT
  7. References: <umage.715709408@mcl>
  8. Reply-To: peterk@cbmger.de.so.commodore.com (Dr Peter Kittel Germany)
  9. Organization: Commodore Germany
  10. Lines: 34
  11.  
  12. In article <umage.715709408@mcl> umage@mcl.ucsb.edu (androgyny) writes:
  13. >Yea me, the novitiate programmer again.
  14. >OK, i know the blitter will draw lines, but i wanted to try my hand at
  15. >writing a straight lin edrawer myself.  And now i want to compare with
  16. >folks here.  Keep in mind i've never had any teaching or theory in this,
  17. >and i've got a routine which requires 2 divides at the beginning of each
  18. >line, and from then on is simple adds and checks. (about 2 to 5 per pixel,
  19. >excluding actually drawing the pixel in ram)  How does this measure up?
  20. >Should i think some more ? ( Of course i should! )
  21.  
  22. Yes, go ahead, there are better solutions to find. I myself needed two
  23. or three years to reach the ultimate algorithm, only to find afterwards
  24. that it had already been invented in the 50's by some Mr. Bresenham at
  25. IBM. It's today known with his name, and it's also implemented in hardware
  26. in the blitter. Shall I really tell you? No. Just a hint: You can avoid
  27. any division by something that I called back then (before learning about
  28. Bresenham) "cross adding/subtracting". You investigate single-pixel steps
  29. on the longer axis of your line. Only once a while you also have to do a
  30. step in the other direction. Now the division is replaced by a continous
  31. subtraction: How often does the denominator fit into the nominator (sp?)?
  32. If you subtracted below zero, another step in the second direction is due.
  33. And to make up for the next interval, you add the dy=y2-y1 (positive!)
  34. to this *error* term, making it positive again, ready for the next
  35. subtractions of *dx* each. Then the only remainng question is how to
  36. initialize this error term: I just give it dy/2.
  37.  
  38. Sigh, now I told you nearly all of Bresenham's algorithm. But there are
  39. differences: He always doubles some terms, where I do it much simpler,
  40. and I swear my lines look as decent as his ones!
  41.  
  42. -- 
  43. Best regards, Dr. Peter Kittel  // E-Mail to \\  Only my personal opinions...
  44. Commodore Frankfurt, Germany  \X/ {uunet|pyramid|rutgers}!cbmvax!cbmger!peterk
  45. Back from vacation, anything happened?
  46.