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.
no subject
Posted by Anonymous (Jonh Smith) on 2017-12-05 15:09:28
Best Quickbooks Support Number @ https://www.quickbooksaccountingsolution.com/
Quickbooks Help @ https://www.quickbooksaccountingsolution.com/
Quickbooks Support @ https://www.quickbooksaccountingsolution.com/
Quickbooks Support Number @ https://www.quickbooksaccountingsolution.com/
Quickbooks Support Phone Number @ https://www.quickbooksaccountingsolution.com/
Quickbooks Tech Support Number @ https://www.quickbooksaccountingsolution.com/
Quickbooks Tech Support Phone Number @ https://www.quickbooksaccountingsolution.com/
Quickbooks Technical Support Number @ https://www.quickbooksaccountingsolution.com/
Quickbooks Technical Support Phone Number @ https://www.quickbooksaccountingsolution.com/
Quickbooks Customer Support Number @ https://www.quickbooksaccountingsolution.com/
no subject
Posted by Anonymous (Jonh Smith) on 2017-12-05 15:16:26
Best Sage Support Number @ https://www.sageaccountingsolution.com/
Sage Help @ https://www.sageaccountingsolution.com/
Sage Support @ https://www.sageaccountingsolution.com/
Sage Support Number @ https://www.sageaccountingsolution.com/
Sage Support Phone Number @ https://www.sageaccountingsolution.com/
Sage Tech Support Number @ https://www.sageaccountingsolution.com/
Sage Tech Support Phone Number @ https://www.sageaccountingsolution.com/
Sage Technical Support Number @ https://www.sageaccountingsolution.com/
Sage Technical Support Phone Number @ https://www.sageaccountingsolution.com/
Sage Customer Support Number @ https://www.sageaccountingsolution.com/
no subject
Posted by Anonymous (Jonh Smith) on 2017-12-05 15:33:18
Best Quicken Support Number @ https://www.quickenaccountingsolution.com/
Quicken Help @ https://www.quickenaccountingsolution.com/
Quicken Support @ https://www.quickenaccountingsolution.com/
Quicken Support Number @ https://www.quickenaccountingsolution.com/
Quicken Support Phone Number @ https://www.quickenaccountingsolution.com/
Quicken Tech Support Number @ https://www.quickenaccountingsolution.com/
Quicken Tech Support Phone Number @ https://www.quickenaccountingsolution.com/
Quicken Technical Support Number @ https://www.quickenaccountingsolution.com/
Quicken Technical Support Phone Number @ https://www.quickenaccountingsolution.com/
Quicken Customer Support Number @ https://www.quickenaccountingsolution.com/
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 we give you the numbers. use the numbers!)
no subject (Anonymous on #weightedsixes
: back and with more bots than ever)
no subject (Anonymous on i didn't say it, he said it)
no subject (Anonymous on digital: a love story -- one-hour review)
no subject (Anonymous on clipping a line segment to a triangle)
no subject (Anonymous on dance dance revolution in the future)
no subject (Anonymous on the best way to eat beans)
no subject (Anonymous on gta3 for gba: the burning question)
no subject (Anonymous on duke nukem forever -- one-hour review)
no subject (Anonymous on take a key for coming in)
no subject (Anonymous on super monkey ball 2 mini-review)
no subject (Anonymous on bioshock, system shock 2, and fear)
no subject (Anonymous on tim's working on physics)
no subject (Anonymous on a review of actionbutton.n
et)
no subject (Anonymous on experts; atari 2600 display hardware)
Comments RSS