Working out Bresenham''s Line Drawing Algorithm as an excercise for a course I''m taking at school. Its trivial to implement it for positive slopes < 1, and pretty easy to adapt it to other quadrants/slopes. My question though is, is it better to write 1 generic line drawing algorithm, using pointers to swap X and Y if necessary (ie - step across the y axis instead of the x if the slop is > 1, etc) and extra checks to see if you should increment of decrement the dependant axis on each step (for positive or negative slopes, etc), or should I write like one "xstepLine" and another "ystepLine" for the two cases? I realize this is pretty insignificant - line drawing is probably always going to be done through openGL or DirectX but I''d like to know whats a better design approach I suppose. (this isnt an assignment BTW, just thinking about this to better understand the course material) Thanks Ratman

Recently i have been toying with line drawing algorithms as well. I was investigating Bresenham's and the even faster one by Xiaolin Wu. I wasn't too interested with lines in 2D space, but rather in 3D space for traversing voxels. (3 space simulated by 2D array with values representing height in my case). I did this for lighting calculations on clouds represented by a heightfield. I was drawing many many lines, so speed was critical. To bad HW acceration doesn't help me here, although i am trying to utilize SSE for some calculations and split line drawing into threads that run in parallel for each half of the cloud surface.

Anyways.... I have great interest in efficient line drawing code, especially when extended into 3D space. That might be a good exercise for you if you were hoping to learn about fast line algorithms. contact me at zurphco@yahoo.com or AIM samgzman if ur interested in my efforts.

[edited by - samgzman on January 13, 2004 12:39:05 AM]

it''s possible to draw line without branching inside loop at all.
Also you could use symmetry to draw 2 pixels at once.
It''s possible to spent one or less clock per pixel if you''re doing several pixels in parallel.

about other algorithms "that are faster":

other algorithms are mostly _very_ trivial "fixed point" based things
Like say for case |x2-x1| > |y2-y1| you could use constant dy/dx as fixed-point value that are in -1..1 range .

Bresentham line aren''t depend to fact that we have cheap division by power of two....

Also Bresentham line are "perfect". There''s versions that always perfectly paint pixels that line are touch ,etc,
also it''s possible to find _perfect_ intersections of line and grid...(perfect mean expressed by ratio of 2 numbers)

Bresentlam-like algorithms could be used to draw many nice things including circles,etc.