Clipping 2d lines on a boundry rectangle

This topic is 4911 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

if i have the starting and ending coords of a 2d line . and im trying to know if ANY part of this line pass inside the boundry of my ClientRect , to mark that line as Should Draw. but i need to do this with minimum resources. so can anyone help ?

Share on other sites
You can use a line clipping routine to get this done. The function below will return 1 if any part of the line is visible, and 0 if not. Pass in your end-points and the client rectangle.

int is_line_visible(int x0, int y0, int x1, int y1, RECT r)
{
if ( y0 > y1 ) {
x0 ^= x1; x1 ^= x0; x0 ^= x1;
y0 ^= y1; y1 ^= y0; y0 ^= y1;
}
if (y0 < r.top) {
if (y1 < r.top) return 0;
x0 += (int)floor((float)(x1 - x0) * (float)(r.top - y0) / (float)(y1 - y0));
y0 = r.top;
}
if (y1 > r.bottom) {
if (y0 > r.bottom) return 0;
x1 += (int)floor((float)(x0 - x1) * (float)(r.bottom - y1)/(float)(y0 - y1));
y1 = r.bottom;
}
if (x0 < r.left) {
if (x1 < r.left) return 0;
y0 += (int)floor((float)(y1 - y0) * (float)(r.left - x0)/(float)(x1 - x0));
x0 = r.left;
}
else
if (x1 < r.left) {
y1 += (int)floor((float)(y0 - y1) * (float)(r.left - x1)/(float)(x0 - x1));
x1 = r.left;
}
if (x1 > r.right) {
if (x0 > r.right) return 0;
y1 += (int)floor((float)(y0 - y1) * (float)(r.right - x1)/(float)(x0 - x1));
x1 = r.right;
}
else
if (x0 > r.right) {
y0 += (int)floor((float)(y1 - y0) * (float)(r.right - x0)/(float)(x1 - x0));
x0 = r.right;
}
return 1;
}

Share on other sites
Your rectangle has it upper corner at (u, v), and it dimensions are (w, h)

For each point of your line (2 points I guess :) ), you will compute the number :
mnA = magicNumber(xa, ya);
mnB = magicNumber(xb, yb);

where magicNumber(x, y, u, v, w, h) is :

int
magicNumber(x, y, u, v, w, h) {
int result = 0;

if (y < v)
result |= 1;

if (x >= u + w)
result |= 2;

if (y >= v + h)
result |= 4;

if (x < u)
result |= 8;

return result;
}

So now, if (nmA & nmB) != 0, your line is very probably in your rectangle.
Else, it's sure it is not in your rectangle. It's a very cheap and simple test.

Share on other sites

A good description of the classic Cohen Sutherland algorithm is here:
http://www.cs.brown.edu/courses/cs123/lectures/Clipping.pdf

A Java demonstration of the Cohen Sutherland algorithm:
http://graphics.lcs.mit.edu/classes/6.837/F99/assignment2/CohenSutherland.html

Documentation of 3 different algorithms:
http://www.cis.ohio-state.edu/~hwshen/681/0118.pdf

Share on other sites
thnx alot for your help guys, and Marmakoide your MagicNumber algorithm is really cheap, and very efficient. there was small syntax error though:

"if (nmA & nmB) != 0, your line is very probably in your rectangle"

that should be "(nmA & nmB) = 0" .. not '!= 0'
but ive got the point ;)

Share on other sites
Nice it helps you :)

Share on other sites
Very nice function, Marmakoide. Are you the author? I couldn't get it to conflict with my line-clipping routine, so I'm going to use this function to cull off-screen lines just before clipping. Should save some time.

Share on other sites
No, it's not mine. This idea is from Cohen and Sutherland, with their clipping algorithms. When they found this nice trick, I wasn't born ;)

It's here :
http://www.cs.brown.edu/courses/cs123/lectures/Clipping.pdf

• What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 9
• 33
• 16
• 11
• 10
• Forum Statistics

• Total Topics
634122
• Total Posts
3015636
×