Sign in to follow this  
benryves

Integer-only line clipping to y=0, y=x and y=-x

Recommended Posts

benryves    1999
I need to clip line segments to y>0, y>x and y>-x.

My current prototype uses floating point arithmetic. For y>0 I check if each end of the line's y component is negative and if so use linear interpolation to bring it up to y=0. For y>x and y>-x I substituted y=x or y=-x into y=mx+c to produce a simple calculation to clip the line.

Here's an early version for Evaldraw.
// Stores the line position.
static x1=-50,y1=100,x2=50,y2=100;

// Are we holding either end?
static end_held = 0;

()

cls(0);

// Get the screen centre and maximum dimension.
cx=xres/2;
cy=yres/2;
mres=max(xres,yres);

// Draw the unclipped line.
setcol(0x111111);
moveto(cx+x1,cy+y1);lineto(cx+x2,cy+y2);

// Draw the axes and clipping regions.
setcol(0x333333);
moveto(cx-mres,cy);lineto(cx+mres,cy);
moveto(cx-mres,cy-mres);lineto(cx+mres,cy+mres);
moveto(cx-mres,cy+mres);lineto(cx+mres,cy-mres);
setcol(0xFFFFFF);
moveto(cx,cy);lineto(cx+mres,cy+mres);
moveto(cx,cy);lineto(cx-mres,cy+mres);

// Order so x1<=x2
x1c=x1;y1c=y1;
x2c=x2;y2c=y2;

// Set this to non-zero if the line has been culled.
culled=0;

if (y1 < 0 && y2 < 0) {
culled = 1;
} else {
// Clip against Y=0.
if (y1c < 0) {
x1c = x1c - (x2c - x1c) * (y1c / (y2c - y1c));
y1c = 0;
}
if (y2c < 0) {
x2c = x2c - (x2c - x1c) * (y2c / (y2c - y1c));
y2c = 0;
}

// "Out of right bounds" (Y=+X).
or1 = x1c > y1c;
or2 = x2c > y2c;

// "Out of left bounds" (Y=-X).
ol1 = x1c < -y1c;
ol2 = x2c < -y2c;

if (or1 && or2 || ol1 && ol2) {
culled = 1;
} else {
if (ol1) {
// Clip 1 to Y=-X.
c = x1c - (x2c - x1c) * (y1c / (y2c - y1c));
m = (x2 - x1) / (y2 - y1);
x1c = c / (m + 1);
y1c = -x1c;
}
if (ol2) {
// Clip 2 to Y=-X.
c = x2c - (x2c - x1c) * (y2c / (y2c - y1c));
m = (x2 - x1) / (y2 - y1);
x2c = c / (m + 1);
y2c = -x2c;
}
if (or1) {
// Clip 1 to Y=+X
c = x1c - (x2c - x1c) * (y1c / (y2c - y1c));
m = (x2 - x1) / (y2 - y1);
x1c = -c / (m - 1);
y1c = x1c;
}
if (or2) {
// Clip 2 to Y=+X
c = x2c - (x2c - x1c) * (y2c / (y2c - y1c));
m = (x2 - x1) / (y2 - y1);
x2c = -c / (m - 1);
y2c = x2c;
}
}
}

// Draw the clipped line.
if (culled == 0) {
setcol(0x00FF00);
moveto(cx+x1c,cy+y1c);lineto(cx+x2c,cy+y2c);
}

// Update the line position using the mouse.
setcol(0xFF0000);
mx = mousx - cx;
my = mousy - cy;
p1 = (x1-mx)*(x1-mx)+(y1-my)*(y1-my);
p2 = (x2-mx)*(x2-mx)+(y2-my)*(y2-my);

if (end_held == 1) {
p1 = 0;
} else if (end_held == 2) {
p2 = 0;
}

if (p1 < p2) {
if (p1 < 64) {
drawsph(x1+cx, y1+cy, -10);
if (bstatus) {
end_held = 1;
x1 = mx;
y1 = my;
} else {
end_held = 0;
}
}
} else {
if (p2 < 64) {
drawsph(x2+cx, y2+cy, -10);
if (bstatus) {
end_held = 2;
x2 = mx;
y2 = my;
} else {
end_held = 0;
}
}
}

Unfortunately, I intend to transfer this code to a machine that does not support hardware multiplication, division or floating-point arithmetic. I am currently converting it to use fixed-point arithmetic with a variety of workarounds, such as different code paths if the line is steep or shallow. In the interest of improving performance I'd be interested to hear if anyone had any suggestions for an integer-only technique, preferably one that minimises the number of multiplication or division operations.

Share this post


Link to post
Share on other sites
Endurion    5411
Shouldn't mostly any old Bresenham algo do at least the line? You "just" need to add the clipping, maybe it's easier to clip at the set pixel level.

Please ignore ugly old warts:

int dy = slYEnd - slYStart;
int dx = slXEnd - slXStart;
int stepx, stepy;

if ( dy < 0 )
{
dy = -dy;
stepy = -1;
}
else
{
stepy = 1;
}
if ( dx < 0 )
{
dx = -dx;
stepx = -1;
}
else
{
stepx = 1;
}

dy <<= 1;
dx <<= 1;

PutPixel( slXStart, slYStart, ulColor );
if ( dx > dy )
{
int fraction = dy - ( dx >> 1 );

while ( slXStart != slXEnd )
{
if ( fraction >= 0 )
{
slYStart += stepy;
fraction -= dx;
}
slXStart += stepx;
fraction += dy;
PutPixel( slXStart, slYStart, ulColor );
}
}
else
{
int fraction = dx - ( dy >> 1 );

while ( slYStart != slYEnd )
{
if ( fraction >= 0 )
{
slXStart += stepx;
fraction -= dy;
}
slYStart += stepy;
fraction += dx;
PutPixel( slXStart, slYStart, ulColor );
}
}

Share this post


Link to post
Share on other sites
benryves    1999
It could be worth a shot, thank you. I hadn't really thought of Bresenham as the lines that need clipping are likely to be quite long (short lines are more likely to either be completely in range or completely out of range, not requiring clipping). I suppose I should implement both, benchmark, and possibly use one method for long lines, the other for short ones.

Share this post


Link to post
Share on other sites
benryves    1999
Quote:
Original post by Rubicon
You should be googling for "Cohen-Sutherland"
I'm familiar with the algorithm when used to clip a line to a rectangle, but I'm trying clip the line to y>0, y>+x and y>-x:

Line clipping

(The green segment is the clipped line, the white lines indicate the clipping region). I'm not sure how Cohen-Sutherland would help me in this instance, sorry.

Share this post


Link to post
Share on other sites
nmi    978
Just a thought, but what about a bisection method to find the intersection point. That should work well even for long lines. If the two endpoints of a line segment are on different sides of a line (for instance y=-x), the line segment must intersect the line somewhere. So just compute the point in the middle of the line segment (division by two is simple even for integer arithmetic) and check if it is inside. If so, repeat bisection with the line segment made up by that point and the endpoint that was outside, otherwise that point and the endpoint that was inside. Repeat this until converged. So for each condition you can find an intersection point. The intersection points found this way are the endpoints of the clipped line, unless one or both of the endpoints of the line segments were already inside the region. Also note that in your conditions y>0, y>+x and y>-x the y>0 implicitly holds because of y>+x and y>-x, so y>0 is not needed.

Share this post


Link to post
Share on other sites
Erik Rufelt    5901
How large can the numbers be?
A normal ray intersection with a line ax + by + c = 0 should work fine in integers too, and with these special cases it's slightly simplified.

Bresenham is something like:

int deltax = 0;
for(x = x0, y = y0; y < y1; ++y) {
point(x, y);
deltax += (x1 - x0);
if(deltax >= (y1 - y0)) {
deltax -= (y1 - y0);
++x;
}
}



The x coordinate of the intersection point with y = 0 is:
x = x0 + (x1 - x0) * (0 - y0) / (y1 - y0)

If the remainder ((x1 - x0) * (0 - y0)) % (y1 - y0) is zero, then continue with Bresenham as normal. If it is not zero, use the remainder as the start-value of deltax.

I think all cases will work like this for any ray and any line, as all numbers will always be rational for rational points. I haven't thought it through entirely and there might be several cases to handle separately, but I think this method should work.

[Edited by - Erik Rufelt on October 18, 2010 10:25:49 AM]

Share this post


Link to post
Share on other sites
benryves    1999
Thank you all for your ideas! I think that a combination of techniques may work quite well (for example, using the bisection method first to reduce the length of the line first to avoid integer overflow when performing the more direct clipping calculation).
Quote:
Original post by Erik Rufelt
How large can the numbers be?
Say around 4,000 units long. This is why I have avoided iterative methods so far. Rather than stepping along the line using 16-bit integers it may work better to step through the most significant bytes using 8-bit integers and then home in on the least significant byte also using 8-bit integers.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this