Jump to content
  • Advertisement
Sign in to follow this  
DrainedBrain

Clipping 2d lines on a boundry rectangle

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
Share on other sites
If you want more about this question (taken from the FAQ of this thread) :

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!