Greetings. I am trying to work out the fastest way to draw a line. I''m not worried about actual pixel drawing - just where they go. So far, i am considering a form of bresenham''s strip algorithm (i think). With normal bresenham you step through the longer of the differences (dx or dy), keeping a count of the error in the other difference. When the errors add up to more than the long difference, you increment the short difference an extra step (not explaining very well). It is possible to work out how many steps there will be before the error accumulates enough - saving an ''if'' each cycle. eg, if the slope is 1/4 then there''ll be 4 steps along one axis before the error accumulates enough to step along the other axis. Bresenhams standard line algo checks the error every step - which isn''t necessary ! what i want to know is - is there a faster way of working out how often the error is large enough - currently i am thinking of using a division (as in quotiant(dy/dx) = number of cycles to accumulate error. and remainder(dy/dx) = error). i havent really explained the problem very well. basically, i want a faster divide.

Maybe try Wu''s line algorithm? I found one example at:

http://freespace.virgin.net/hugo.elias/graphics/x_wuline.htm

but I don''t know the performance characteristics vs Breshenham''s.


---- --- -- -
Blue programmer needs food badly. Blue programmer is about to die!

Hmm. perhaps i should give more details.
I am after a way of speeding up a routine for interpolating between two sets of two values.

Ie (x1,y1)-(x2,y2)

it doesn''t have to necessarily be a line. for instance, i can interpolate the intensity of red over the length of a line.
then the coords i am interested in are (start,red1)-(end,red2)

does that make it clearer ?

quote:Original post by Wyzfen

Hmm. perhaps i should give more details.
I am after a way of speeding up a routine for interpolating between two sets of two values.

Ie (x1,y1)-(x2,y2)

it doesn''t have to necessarily be a line. for instance, i can interpolate the intensity of red over the length of a line.
then the coords i am interested in are (start,red1)-(end,red2)

does that make it clearer ?

Bresenham''s and Wu''s line algorithms are TYPICALLY used for line drawing but not LIMITED to that. They are integer solutions for linear interpolation which can be applied to any N-tuple (examples: screen space (line drawing), RGBA values, 3d vectors, etc, etc, etc).

Offhand, IIRC, Wu does only one division for the whole line, so it might be faster than Bresenham''s if you''re doing quotient() and remainder() every step. But I don''t know how you''ve coded your function, and I''ve not tested Bresenham vs Wu myself, so I couldn''t tell you for sure.





---- --- -- -
Blue programmer needs food badly. Blue programmer is about to die!

Bresenhams standard line doesnt use any divides.
I can''t work out how to do the span-form without (where you don''t check the error accumulation each pixel).
Even with the span-form, only one divide is used.
The applications i am working on don''t need anti-aliasing.
Basically, i am trying to work out an interpolator that doesn''t use any divides, with fewer cycles than bresenhams (ie, less if''s).

It''s kind of a moot point now - i realise that i''m not going to be able to interpolate 5 things simultaneously if i use the spans - so i''ll just use a fast version of bresnham.

I''m still after an answer for my oriniginal question, just as an exercise.

Have you tried Bresenham''s run slice algorithm?
It''s similar to Bresenham but faster. It takes the largest possible run and always draws that many pixels.
i.e. You have a line with horizantal run 8 and vertical run 3. Your slope is 3/8 so it is somewhere between 2 pixels and 3 pixels long. This algorithm always does the 2 pixels and then tests for when the third should be drawn as well.

Hope that helps!

Cat

Thanks - I was using the ''run slice'' algorithm, but i couldn''t recall the name - so i was calling it span/ slice.
Anyway, it''s the working out that span that i forsee using a divide in cat''s example of 3:8, it would do 8/3 = 2 remainder 2
i am trying to work out the fastest way of drawing a line without the necessity of this divide.

in the meantime, i''m interpolating 4 variables wrt to a 5th, so the run slice isn''t appropriate - still, as a theoretical exercise ...

Wyzfen