§ ¶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.
This might be naive, but wouldn't it be possible to use fast Bresenham in an area that is a few pixels away from the clipping borders and then use a much slower but easy algorithm to fill in the missing (small) segment? That latter algorithm could be Bresenham with bounds checking for every PutPixel.
tobi - 07 07 11 - 04:41
Use Cohen-Sutherland with a slightly expanded clipping region and then use the cheesy PutPixel() routine to reject points outside the actual clipping area?
xar - 07 07 11 - 09:47
Neither of those will work, because both still require a way to sample the line at an arbitrary intersection point -- in the first case, the couple-of-pixels-inset screen edge, and in the second case, the outer edge of your guard band. This problem has the exact same challenges as the original clipping problem. (Realize that, if you pick the wrong starting coordinate, it doesn't just affect the first few pixels -- it affects the entire line.)
Damian - 07 07 11 - 10:50
how about deriving new coordinates? find the intersection between the desired line and the boundary edge - derive an x,y coordinate for that intersection - and make that the end point of the line. that should just be trigonometry right?
jin - 07 07 11 - 13:55
> This might be naive, but wouldn't it be possible to use fast Bresenham in an area that is a few pixels away from the clipping borders and then use a much slower but easy algorithm to fill in the missing (small) segment? That latter algorithm could be Bresenham with bounds checking for every PutPixel.
Yup, you can do that. I'm not sure it's faster than just computing the precise intersection, though. I shied away from talking about performance; there are lots of ways to speed up line drawing beyond a standard Bresenham, and for a lot of use cases it may be fine just to detect whether clipping is needed and switch between guarded and unguarded routines. The worry is if you've got a case where you can get extremely far out coordinates for a line that intersects the clipping space, and if your guarded line routine can take forever stepping through the whole line. It's a bit embarrassing if your graph drawing routine on the server locks up for an hour because some guy enters in 1000000000 as one of the values on a web form. Of course, you can just chuck those lines on the basis that you're probably being asked to draw garbage anyway, but that's a bit lame.
> Use Cohen-Sutherland with a slightly expanded clipping region and then use the cheesy PutPixel() routine to reject points outside the actual clipping area?
If you have a rounding problem between the line drawing routine and the clipper, the error affects the whole line, not just the portion near the clipping boundary: it manifests as a slight slope error. I don't think clipping to a widened boundary would help.
> how about deriving new coordinates? find the intersection between the desired line and the boundary edge - derive an x,y coordinate for that intersection - and make that the end point of the line. that should just be trigonometry right?
Yes, this is effectively what the line clipper does, precise or not. The tricky part is making sure you don't have an off by one error. An example of where you can get burnt is that there is an inherent ambiguity in the Bresenham line algorithm for lines that exactly cross between pixels: whether you use less-than or less-equal in the routine determines which exact line you get. As such, you have to make sure that the clipper is clipping the actual line that would be drawn and not the ideal line. If the two don't match, the line drawing routine may choose to step the minor axis one pixel later or earlier than the clipper predicts, possibly resulting in a fatal off by one error. This is even more fun if the line drawing routine sometimes flips the endpoints in order to reduce the number of directions it has to handle, in which case the flip should either be moved above the clipper or the clipper needs to predict the flip the same way. Finally, if the line routine is following particular rules for inclusion of the start and end points, such as either omitting the end point in a integer coordinate routine or the diamond-exit rule for a fractional coordinate routine, you have to make sure that the clipper doesn't cause violations of that rule.
Phaeron - 07 07 11 - 15:18
I guess this problem is related to the fact that when you draw a square with two triangles, no single pixel on the diagonal is not drawn or drawn twice. I always wondered how this works even when the square is perspectively transformed.
tobi - 07 07 11 - 20:45
I had to go through this some 20 years ago so I'm surprised someone still needs to solve such problems. What I used by then was the Bresenham algorithm (I did not know it under that name by then... I was uneducated) with a bit of pre-calculation of how many steps it has to fast-forward in the beginning and how many steps to perform. It involved a lot of typing while enumerating all cases but nothing that I would call hard or tricky. The only thing I had problem with was running into arithmetic overflow when calculating the fast-forward step.
Kasuha - 07 07 11 - 21:12
I've always used a recursive line plotting algorithm. Find the mid point, plot it, then call with the two sublines. It can be tweaked to ignore sublines outside the plot area.
John (link) - 07 07 11 - 23:07
Ahhh.. Brings back memories. Just dug up my old line clipping for 16.16 fixedpoint from my old demos - horrible stuff, but even though it probably could have been faster, the alternative was checking x&y for every pixel plotted. Also the line clipping is one of the only code I commented.
Still remember joking with some of my friends, who implemented line clipping as "if (x
Klaus Post (link) - 08 07 11 - 01:11
ffs... clipped off after less than ;)
Still remember joking with some of my friends, who implemented line clipping as "if (x < 0) x = 0". Here is a good example: http://youtu.be/Dw7p5YAohL0?t=3m05s
- notice how the white lines at the border moves around. The polygon flickering wasn't in the original.
Oh here second time watching , just noticed I was in the greetings - awesome :D
Klaus Post (link) - 08 07 11 - 01:32
DDA with 16:16 fixed point is good enough in most cases.
MaxSt - 08 07 11 - 04:35
I'd say that line rasterization/clipping only somewhat resembles polygon rasterization in that you have similar challenges in making sure that all boundary conditions are handled just right in order to make a robust renderer. In some ways, the polygon situation is even easier as you can be sloppier with the precise clipping as long as you're consistent, i.e. don't produce cracks. (See also: Playstation 1). But yes, getting the fill rules right is important. I once had to fix a graphics plugin that was showing artifacts due to both a bad fill rule -- some rasterizers used less-equal instead of less for the row loop, which resulted in overlap artifacts with alpha blending -- but also didn't prestep UVs, leading to jittery textures. Thing is, I work with 3D rendering so much that polygon rasterization issues are second nature to me compared to line rasterization issues!
As for DDA, yeah, that's a good alternative. The most recent line renderer I wrote was in C, so it was easier to do Bresenham, but in asm I'd probably use a DDA and abuse the carry flag. The downside is that you have to eat a divide in setup even for unclipped lines. You also may not have this option if your line rasterization algorithm is chiseled in hardware, though, like the Amiga blitter. It makes me wonder how graphics.library or layers.library handled this.
Phaeron - 08 07 11 - 16:43
It's too early in the morning to read the entire post, but I understood the problem you're facing the second I read it. I've dealt with this before a few times.
First of all, stay with bresenham, it's good, it's fast and it's elegant. I like your second approach and assume that you did something similar to what I've done.
Bresenham has a certain amount of setup where the start and end points are swapped if necessary so as to allow the increment to work in a positive direction. Additionally, based on whether the slope of the line is less greater than 1 or not, it is decided whether to draw following the X or the Y's path.
A clipping algorithm doesn't need to be complex for rectangular clipping regions. Once you've calculated the slope and error of the line, take the number of steps and adjust the starting x, y and error to compensate for the clipping before the start of the line. Then alter the length of the loop in order to end at or before the bounds (depending on which method of rectangular region definition you choose to use). What's great about this method is that it CAN be accomplished with just integers (though it's a crap load of work to sort out the math just right). Additionally, it fits into bresenham beautifully as it can be entirely sorted out in the setup phase.
If you want an example of the algorithm, I imagine I can alter my wiki with one after I sort out several of the other projects I'm working on. On the other hand, from what I've seen you accomplish in the past, this should be relatively trivial for you to sort out on your own.
I have a great theory on mathematically clipping the midpoint ellipse and circle algorithms. I'll try to write that up sometime. Working on a spline related one as well.
P.S. - If you formally document what I've said with your implementation details, name it Bressenham, Avery, Starr Clipped Line Drawing Alorithm :) hehe
SubMux (link) - 04 08 11 - 19:32
Thanks -- I already have the line clipping routine written. I actually tend to write these posts after I've already gotten the code working, because that helps ensure that I've covered everything. The actual clipping code is pretty small and can be done in integer math as you say... in fact, I'd say it must be done in integer, unless you want to risk an off by one with really big 32-bit coordinates.
I'm not sure I would bother with coming up with a clipping algorithm for circles and ellipses. For starters, I can count the number of times I've needed an aliased ellipse drawing routine on one hand. The second issue is that those algorithms become unwieldy the moment you need to support rotated ellipses. (I think there's a general conic section algorithm, but it has a lot of forward differences to step.) At that point I'd just say screw it and implement it on top of a cubic curve routine, which has other uses and can be bolted on top of an existing line drawing routine.
Phaeron - 04 08 11 - 19:51
There is an excellent free C++ template library called AGG, which does all that and much more, very efficiently and very elegantly.
Alex - 07 08 11 - 02:12
I've been trying to do this for weeks. I knew roughly what I needed to do and this page confirmed it. But still it's been driving me around the twist because I cannot get it exactly correct. This page is the top result on Google for this topic, and unfortunately, it's about the only page that has anything substantiative to say about it.
The claimed "Foley & van Dam" trick, if it exists, can't be found online.
I can't find it in the VirtualDub source, if it's in there.
It's not in AGG.
"Phaeron" and "SubMux" clearly know their stuff, but haven't provided detail.
"Kasuha" is an asshole, having apparently done it 20 years ago by accident in his sleep and now considers it beneath him. Piss off.
There is a promising article "Bresenham' Line Generation Algorithm with Built-in Clipping" by Yevgeny Kuzmin. Unfortunately it's a formal paper, which means the people who have it aren't sharing it.
I found a C++ file of graphics functions for students of a particular computer science course here: http://www.csd.uwo.ca/~adelong3/cs3388-2..
One of them is a clipped Bresenham line drawing function which says it is based directly on the Kuzmin paper. I ported it to Java with minimal effort and it does work, but the code is not very clean or understandable. I can't use it as-is without knowing its copyright status and can't rewrite it because the mathematics of it are indecipherable.
There is a forum thread here: http://www.developpez.net/forums/d718873..
(in French) which seems to vaguely suggest the same idea as mentioned by whoever the author of the blog post on this page is: clipping half a pixel inside the boundary of the clip rect. Well, it's not worded that way, but it amounted to exactly the same code when I tried to implement it. It didn't work, anyway.
If anyone else in existence understands the secret they're not shouting it from the online roof tops.
So, I'm still stuck. Whatever I try, it always crashes, or goes into an infinite loop, or draws the wrong line, or clips slightly too much or too little, and I'm sick of it. Perhaps a brute force search or genetic algorithm could eventually discover the correct formulae to calculate the clipped coordinates and error value by accident, but I haven't the patience for it.
It seems like such a simple problem. I need only 1-pixel lines. Solid-colored. No anti-aliasing. I just need to clip them correctly. But trying to do that opens the doors of hell.
To anyone else who finds this, my advice is: Give up. I did.
Michael - 31 01 14 - 21:39