• Create Account

### #ActualSyranide

Posted 24 January 2012 - 05:59 AM

http://en.wikipedia.org/wiki/Xiaolin_Wu's_line_algorithm (shows an implementation of the algorihm)

Oh believe you me, I've devoured that article tens of times, that and all the other articles that I could find on the subject, now I'm reading Michael Abrashes explanation, so far his makes the most sense to me.

Ah, I guess you could look at Bresenham's code a bit too on wikipedia, may not be directly applicable, but they do go through some short explanatations and optimizations...

Anyway, as you understand I have little knowledge of this myself, but!

"The operation D <- D + d is a module 2^n addition with the overflow recorded."
I'm pretty sure he just means D = (D + d) % (2^n) ... and he stores the overflow ... somewhere. Or it's just strangely worded?

"e = k - d*2^(-n)"
Again, just my first hand instinct, negative n seems reasonable as the error should go down as the number of bits go up. Especially as it seems that d is related to 2^n, by the above.

"I( x, ceil(k*x) ) = (2^m - 1) * (D*2^(-n) + ex) = D*2^(m-n) + ...."
I'm guessing this is just a continuation on the above to some degree, with d replaced by D (as D is in-fact d, but accumulated).

Again, I may be completely stumbling in the dark here, so if this makes no sense either, it's probably because it doesn't ;)

### #2Syranide

Posted 24 January 2012 - 05:58 AM

http://en.wikipedia.org/wiki/Xiaolin_Wu's_line_algorithm (shows an implementation of the algorihm)

Oh believe you me, I've devoured that article tens of times, that and all the other articles that I could find on the subject, now I'm reading Michael Abrashes explanation, so far his makes the most sense to me.

Ah, I guess you could look at Bresenham's code a bit too on wikipedia, may not be directly applicable, but they do go through some short explanatations and optimizations...

Anyway, as you understand I have little knowledge of this myself, but!

"The operation D <- D + d is a module 2^n addition with the overflow recorded."
I'm pretty sure he just means D = (D + d) % (2^n) ... and he stores the overflow ... somewhere. Or it's just strangely worded?

"e = k - d*2^(-n)"
Again, just my first hand instinct, negative n seems reasonable as the error should go down as the number of bits go up.

"I( x, ceil(k*x) ) = (2^m - 1) * (D*2^(-n) + ex) = D*2^(m-n) + ...."
I'm guessing this is just a continuation on the above to some degree, with d replaced by D (as D is in-fact d, but accumulated).

Again, I may be completely stumbling in the dark here, so if this makes no sense either, it's probably because it doesn't ;)

### #1Syranide

Posted 24 January 2012 - 05:56 AM

http://en.wikipedia.org/wiki/Xiaolin_Wu's_line_algorithm (shows an implementation of the algorihm)

Oh believe you me, I've devoured that article tens of times, that and all the other articles that I could find on the subject, now I'm reading Michael Abrashes explanation, so far his makes the most sense to me.

Ah, I guess you could look at Bresenham's code a bit too on wikipedia, may not be directly applicable, but they do go through some short explanatations and optimizations...

Anyway, as you understand I have little knowledge of this myself, but!

"The operation D <- D + d is a module 2^n addition with the overflow recorded."
I'm pretty sure he just means D = (D + d) % (2^n) ... and he stores the overflow (i.e, what modulo cuts away) ... somewhere.

"e = k - d*2^(-n)"
Again, just my first hand instinct, negative n seems reasonable as the error should go down as the number of bits go up.

"I( x, ceil(k*x) ) = (2^m - 1) * (D*2^(-n) + ex) = D*2^(m-n) + ...."
I'm guessing this is just a continuation on the above to some degree, with d replaced by D (as D is in-fact d, but accumulated).

Again, I may be completely stumbling in the dark here, so if this makes no sense either, it's probably because it doesn't ;)

PARTNERS