Line drawing algorithms.
category: code [glöplog]
Hey dudes. What line drawing algorithms are you people using on limited hardware platforms? is there any faster stable algorithm than the optimized Bresenham algorithm?
use fixed point without no branching inside the loop at all. works best if there´s a carry-add, partial register access or multi-register add operation provided by the instruction set
wu line algorithm. You don't have to actually do the anti-aliasing, you can just use it as a nicely unrollable line algorithm (no compares needed apart from the termination-condition).
Try these two | examples. this one talks about branching
The speed of each version may depend on the target platform. For example: CPU favors subtraction over subtraction.
other ideas
The speed of each version may depend on the target platform. For example: CPU favors subtraction over subtraction.
other ideas
- skip some steps and make dotted lines. alternate the spaces with and even|odd approach between frames for ultimate illusion at high FPS
- Use 8-bit maths and restrict line drawing to a 256x256 grid. I suppose this only benefits 8-bit CPUs.
- Throw hardware at it. The Amiga blitter had a line drawing function to offload line work from the CPU. Maybe something like that exists for you. I imagine a C64 could off-load that work to a disk drive which had a separate CPU. Not sure if the data transferring would negate the benefits.
- avoid calculations when doing perfectly horizontal or vertical lines (third link)
on the original pentium (and probably also 060 or similar) a super-simple floating point DDA was actually faster than bresenham. and you could do some nifty fake anti-aliasing as well this way (by using the the fractional parts as shades of grey)..
Bresenham was once fast, when CPUs could branch efficiently.
These days, a mispredicted branch is very costly, and Bresenham is not simple to predict for a CPU, so usually it ends up slower (then again, you could replace the branch with some bitmasking instructions, ie do the compare, convert carry to bitmask, then and with bitmask (turning the operands to 0 if carry was not set) and add).
Another downside is that subpixel-correction is more expensive for Bresenham than for a DDA.
One thing that Bresenham still has going for it however is that it does not perform any type of rounding (for a DDA, you will need to calculate deltas, and the result of the division will be rounded). This is interesting because you have no accumulation-of-error issues to worry about, regardless of the resolution you're using.
These days, a mispredicted branch is very costly, and Bresenham is not simple to predict for a CPU, so usually it ends up slower (then again, you could replace the branch with some bitmasking instructions, ie do the compare, convert carry to bitmask, then and with bitmask (turning the operands to 0 if carry was not set) and add).
Another downside is that subpixel-correction is more expensive for Bresenham than for a DDA.
One thing that Bresenham still has going for it however is that it does not perform any type of rounding (for a DDA, you will need to calculate deltas, and the result of the division will be rounded). This is interesting because you have no accumulation-of-error issues to worry about, regardless of the resolution you're using.
If you have a bit of ram and working in planar mode (or maybe not) you could use Kalms' blit-line-segments-from-a-precalc-table routine.
Yes, take special note of Kalms' comment there: 'Swap endpoints if necessary, so line always goes left->right'.
With any kind of approximation (which line-drawing certainly is, you are mapping the line onto a discrete grid of pixels), it is important that you always calculate things the same way, so that your approximations/rounding errors are always the same.
That is, if you were to draw a line (even with Bresenham) from A to B, and then draw the same line from B to A, you will not always end up on exactly the same pixels (easy to test by drawing pixels with xor: every pixel that is shared by both lines, will cancel itself out, whatever pixels remain on screen are your errors).
So, the solution is to sort your endpoints (which most of the example sources do not seem to do, at a quick glance). That way, whether you pass a line as (A, B) or (B, A), the drawing routine will always draw it in the same direction (eg left-to-right and/or top-to-bottom).
This ensures that all calculations are approximated/rounded the same way, resulting in stable and robust rasterizing, rather than jittery lines when moving, or lines next to eachother that don't match up nicely when they should.
With any kind of approximation (which line-drawing certainly is, you are mapping the line onto a discrete grid of pixels), it is important that you always calculate things the same way, so that your approximations/rounding errors are always the same.
That is, if you were to draw a line (even with Bresenham) from A to B, and then draw the same line from B to A, you will not always end up on exactly the same pixels (easy to test by drawing pixels with xor: every pixel that is shared by both lines, will cancel itself out, whatever pixels remain on screen are your errors).
So, the solution is to sort your endpoints (which most of the example sources do not seem to do, at a quick glance). That way, whether you pass a line as (A, B) or (B, A), the drawing routine will always draw it in the same direction (eg left-to-right and/or top-to-bottom).
This ensures that all calculations are approximated/rounded the same way, resulting in stable and robust rasterizing, rather than jittery lines when moving, or lines next to eachother that don't match up nicely when they should.
On my crap platform, I perform branching to handle special-case 100% vertical, 100% horizontal, and 45-degree angle lines, and do branchless fixed-point for all others.
