
clipping a line segment to a triangle 
Posted 20040302 15:35:07 by
Jim Crawford
I'm working on some realtime light and shadow code to make Swarm look cool despite my mediocre artwork.
To this end, I just got a routine working to clip a line segment to a triangle. My old algorithm to do this was about twenty hairy lines, full of special cases that I had agonized over for hours, because I didn't understand at the time that the problem I was trying to solve could be stated as “clipping a line segment to a triangle.”
When I realized that it could, Google turned up the (easily extrapolatable) CohenSutherland algorithm and suddenly I had seven clean, elegant lines that did perfectly what twenty did with edge cases visibly breaking all the damn time.
I don't know whether to feel triumphant or like an idiot.
bool clip(const triangle &t, point &s, point &e)
{ for(int i=0; i<3; i++)
{ bool sout = t.lines[i].sdistance(s)>0.0,
eout = t.lines[i].sdistance(e)>0.0;
if(sout && eout) return false;
if(sout) s=t.lines[i].intersection(s, e);
if(eout) e=t.lines[i].intersection(s, e);
}
return true;
}
In case something isn't clear from the code:
clip() returns whether or not any of the line segment is left after clipping.
lines is the array of lines that bound the triangle.
line::sdistance(point p) returns the “signed distance” from the line to p (the lines face away from the interior of the triangle, so that a point with a positive sdistance will be outside of the triangle).
line::intersection(point s, point e) returns the intersection point of the line and the line segment between s and e .

re: clipping a line  Posted by Anonymous (sugigrl) on 20040302 15:18:44
I'm going with triumphant. I don't see how easily extrapolatable that CohenSutherland algorithm is and yay simple solution after all that agony 
re: clipping a line  Posted by Jim Crawford
on 20040302 18:17:23
 I'm going with triumphant 
Sounds like a plan then! 
20, triumphant leads  Posted by Anonymous on 20040304 01:08:25
Triumphant: I read the lecture notes you linked to, and still can't see how that generalises to triangular clip regions. This may be because of rum.
BTW, the conciseness fetish has got to stop.
For example: how is: bool sout = ..calc..., eout = ..calc...;
more readable than: bool sout = ..calc...; bool eout = ..calc...;
?? 
re: 20, triumphant leads  Posted by Jim Crawford
on 20040304 10:16:15
 For example: how is: bool sout = ..calc..., eout = ..calc...;
more readable than: bool sout = ..calc...; bool eout = ..calc...; 
Er, now that I think about it, I suppose it's actually less readable. Though the rum seems to have also distorted the situation a bit by removing some essential whitespace from Figure 1 :)
Or maybe that's my fault, come to think of it. This site does have some overly aggressive whitespacecompression code. 
explanation  Posted by Jim Crawford
on 20040306 02:26:48
Since both of the respondents implicitly asked how to extrapolate this algorithm, here's how I did it:
CohenSutherland consists of two components. One is the check to see whether the line segment is trivially inside or outside the bounding rectangle. The other is the way to deal with line segment that crosses one of the rect's bounding lines.
For the triviality test, Messrs. Cohen and Sutherland came up with a rather clever method of assigning one bit of a nibble to a point's insideoutside status for each of the bounding lines. They call the resulting nibble the "outcode."
So, say the start point is on the outside of the first two lines but the inside of the second. Its outcode would be 1100. The end point is on the inside of the first two but the outside of the second, its outcode nibble would be 0011. The line segment is completely outside if you bitwiseand these two values together and the result is nonzero.
For the clipping, you, uh, go through the rectangle's bounding lines and clip the line segment to them.
For my algorithm, I conflate these two processes, using arbitraryline insideoutside and intersection routines rather than ones that work with just horizontal and vertical lines (that's the extrapolation I did). CohenSutherland separates them for optimization purposes, but there's much less gain to be had by doing this when you have to do the calculations with arbitrary lines.  
