Re^3: Split range 0 to M into N non-overlapping (roughly equal) ranges.

The problem with Bresenham is that it requires you to iterate the entire range (segment) one at a time.

For 360 degrees (or just 45 if you use the 1/8th mirroring optimisation), that isn't a problem, but for ranges above 100,000 or so (and many of mine are in the 10s or 100s of millions), it would be horribly slow.

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

Comment on Re^3: Split range 0 to M into N non-overlapping (roughly equal) ranges.

Replies are listed 'Best First'.
Re^4: Split range 0 to M into N non-overlapping (roughly equal) ranges. by Corion (Patriarch) on Mar 12, 2011 at 23:21 UTC
I knew that all those days looking at assembly language line drawing algorithms would some day pay off. I'm almost certain there is an "improved" Bresenham algorithm that does not require you to paint the line pixel-by-pixel - but unfortunately, I can't find it. Most likely, it is discussed in the "Mode X" articles published around 1990. The "Mode X" was a graphics mode where you could write up to four bytes of (8 bit) graphics memory, by writing one byte to the graphics bus. This greatly improved (non-OpenGL) rasterizers, as long as they could tell when the next error overflow was bound to happen. And yay, Google Gives! Michael Abrash's book, "Graphics Programming", is online, and it has the discussion of how to turn Bresenham's Algorithm 90 degrees sideways, so you get to know how long a run (=range) is without iterating it. I'm not convinced that this solution is any better than your original approach, as the algorithm plus setup is best stuffed away in a subroutine, and it certainly is not really self-explaining to the casual onlooker. But at least this made me revisit ideas of the olden times and find an application for a somewhat unrelated topic.	[reply]
Re^5: Split range 0 to M into N non-overlapping (roughly equal) ranges. by BrowserUk (Patriarch) on Mar 13, 2011 at 00:22 UTC
Neat. I've written Bresenham routines several times in C and various assemblers, but I'd never encountered that variation. The interesting thing is that once you whittle away the details irrelevant to my problem, you end up with the realisation that this is exactly what both javafan and mr_mischief came up with. The significant thing in both implementations is that they defer the inting when calculating the step value, retaining it as a real, with the result that the residual get distributed evenly and automatically as they iterate the N partitions. Simple once it is in front of you, but it was the trick I was missing. Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice.	[reply]