¶Line clipping
One of the primitives I always dread when writing a 2D library is a line drawing routine. You might ask, why write your own line drawing routine, but there are lots of reasons to do so. Perhaps you need an off-screen renderer in a private buffer, or you're working with a matrix that's something other than an image, such as doing line of sight raycasting. In any case, ask anyone what algorithm to use for drawing a line, and they're likely to say "Bresenham" -- a well-known and simple line drawing algorithm.
The next thing that happens is that someone gives you coordinates outside of your grid, and your line routine happily crashes.
This means, of course, that you need to clip the lines. The cheesy way is to use a PutPixel() routine that rejects outside points. This works, and is more formally known as guard band clipping when done in moderation, but it has the downside that if someone hands you a billion pixel long line your line drawing routine might take an awfully long time to complete. What you need is a clipping algorithm that gives the section of the line within the clipping bounds without actually stepping through the whole thing.
Now, ask or search for a line clipping algorithm, and you'll invariably get an answer like Cohen-Sutherland... which unfortunately is wrong. Okay, it's not actually wrong -- it's a valid algorithm, your routine won't scribble outside of the grid and crash anymore, and it'll draw something that looks like a clipped line. Take a closer look, however, and you'll find that it doesn't clip lines quite right. Here's why:
- The standard Bresenham line algorithm draws a line between two endpoints with integer coordinates. More precisely, it gives you the pixels closest to a line segment between the centers of the start and end points.
- A line clipping algorithm like Cohen-Sutherland gives a fractional coordinate when it intersects the line against the clipping boundary.
- In order to use the clipped result with the line drawing routine, the fractional clipped coordinate has to be rounded off.
- The rounded coordinates mean that if the line is sloped, the clipped line doesn't quite match the unclipped line.
If you're just clipping against a relatively big rectangle and are doing something non-critical like visualization, you might be fine living with the error. If you're doing something like clipping against a region that's been tesselated into rects, though, this is disastrous as the resulting line doesn't look straight. Bonus points are awarded if the line clipping routine doesn't round results properly and adds extra jitter when the clipped line is animated.
The problem isn't that the clipping algorithm is wrong, it's that it's inappropriate for the line drawing algorithm. It bothers me that this type of line clipping seems to be so frequently suggested without noting the caveats. Furthermore, it turns out that doing precise clipping is a lot harder. These are the choices that I know of:
- Use a line drawing algorithm that takes fractional coordinates. This is what 3D hardware actually does, and it has the additional benefit that you can smoothly animate lines without jitter. The downside is that modifying a standard Bresenham to use fractional coordinates is a bit of work, starting with getting the end conditions right (look up "diamond-exit rule" in the OpenGL specification). Clipped lines still aren't guaranteed to match exactly, but if you've got something like 8-bit fractional fixed point it'll be very, very close.
- Integrate clipping into the Bresenham line drawing algorithm itself. The major axis can be clipped either by prestepping the starting position and error accumulator or changing the length, both of which are easy enough. The nasty part is clipping along the minor axis: computing the point at which the line juuuuust enters or exits the clipping rect is tricky to get right. Foley & van Dam has a trick to do this involving clipping at a boundary a half pixel inside of the clip rect.
I've done it both ways, and generally it takes me several tries, a buttload of asserts, and a random line scribbling test to get it right.