News for hackers. Stuff that matters.
Re:The Beauty of Bresenham's Algorithm by FredBrach on Tuesday August 07, 2012 @09:15PM (#4353343)
By the way, I had a teacher (J.P Reveilès) who had invented the theoretically fastest drawline algorithm ever: he simply figure out that, for a line, there is a pixel pattern which repeat itself (unless the variation is a transcendental number http://en.wikipedia.org/wiki/Transcendental_number) so you only have to compute that pattern once and copy/paste it. If I remember well, for example, a line which has a variation of 1/4, has a 4-pixel wide pattern only!

His discrete line equation is relatively beautiful (it is easily extractible from Bresenham's algorithm however): 0 ≤ ax − by < ω

Re:The Beauty of Bresenham's Algorithm by 6ren on Tuesday August 07, 2012 @10:40PM (#4353595)
Wouldn't the exception be for lines whose slope is irrational? (i.e. that can't be represented by a ratio of integers), so the repeating pattern is analogous to the repeating pattern in a decimal representation of a rational number.
Re:The Beauty of Bresenham's Algorithm by textminer on Tuesday August 07, 2012 @11:06PM (#4353671)
How does a computer distinguish an irrational number from a good, (necessarily rational) floating-point approximation of one?
Re:The Beauty of Bresenham's Algorithm by mjcohenw on Tuesday August 07, 2012 @11:30PM (#4353741)
The algorithm only works with points with integer coordinates, so the slope is always rational.
Re:The Beauty of Bresenham's Algorithm by FredBrach on Wednesday August 08, 2012 @12:43AM (#4353950)
I think you have the last words because line drawing algorithms become irrelevant if you use a Floating Point Unit.

just:

{ x++ and y+=slope } or { y++ and x+= 1./slope }

Then slopes are always rational in line drawing algorithms.

Re:The Beauty of Bresenham's Algorithm by ralph on Wednesday August 08, 2012 @05:26AM (#4354668)
If y and slope are floating point in the first block then might not y end at other than the desired endpoint because of accumulative error?