goombas.org
menu
main
links
all items
rss feed

Topics:
coding
games
goombas.org
horror
judgement
life
minutiae
music
rants
software
fool.
 _-
 oO
 |/
/|
/ \
Ugh, stop twitching
clipping a line segment to a triangle
coding Posted 2004-03-02 15:35:07 by Jim Crawford
I'm working on some real-time 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) Cohen-Sutherland 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.
[link to this] [See more on “coding”]

comments
re: clipping a line
Posted by Anonymous (sugigrl) on 2004-03-02 15:18:44
I'm going with triumphant. I don't see how easily extrapolatable that Cohen-Sutherland algorithm is and yay simple solution after all that agony
re: clipping a line
Posted by Jim Crawford on 2004-03-02 18:17:23
 I'm going with triumphant


Sounds like a plan then!
2-0, triumphant leads
Posted by Anonymous on 2004-03-04 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: 2-0, triumphant leads
Posted by Jim Crawford on 2004-03-04 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 whitespace-compression code.
explanation
Posted by Jim Crawford on 2004-03-06 02:26:48
Since both of the respondents implicitly asked how to extrapolate this algorithm, here's how I did it:

Cohen-Sutherland 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 inside-outside 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 bitwise-and 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 arbitrary-line inside-outside and intersection routines rather than ones that work with just horizontal and vertical lines (that's the extrapolation I did). Cohen-Sutherland 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.
add a comment
Only anonymous comments are available for now until I get the user system up and running again. Not many people were logging in anyway, so enh.
Permitted HTML tags: <b>, <i>, <u>, <tt>. Also permitted is the <q> pseudo-tag which is meant to delimit quotes from other messages.
name:
email:
subject:
body:
Preview
To prove you are sentient, please type "sentient" into this box

what's this?
This is Jim Crawford's blog. Details and contact information.

On Twitter: @mogwai_poet

recent comments
no subject (Anonymous on may 2013 microblog digest)
no subject (Anonymous on boxing: a history)
QuickBooks Technical Support Phone Number @1844-640-1482
(Anonymous on may 2013 microblog digest)
phone number for quickbooks support (Anonymous on may 2013 microblog digest)
no subject (Anonymous on boxing: a history)
Accountancy (Anonymous on may 2013 microblog digest)
QuickBooks Technician (Anonymous on may 2013 microblog digest)
no subject (Anonymous on boxing: a history)
quickbooks support (Anonymous on may 2013 microblog digest)
Loved the game (Anonymous on boxing: a history)
no subject (Anonymous on may 2013 microblog digest)
no subject (Anonymous on may 2013 microblog digest)
Aol Tech Support Number (Anonymous on may 2013 microblog digest)
Time Mushyn (Anonymous on foolish 2)
Packers and Movers Bangalore (Anonymous on may 2013 microblog digest)
Comments RSS