## Liang-Barsky 2D polygon clipper ; beginner problem

### Liang-Barsky 2D polygon clipper ; beginner problem

I'm clipping a triangle on a rectangular clipping region.  I'm using code
that's based on the code in CGPP (Foley, Van Dam, et al) 3rd ed, p. 935 -
937.

Has anyone based code off this program listing?  Any problems?

I have all kinds of problems, but let's not talk about them.  The code I
wrote has problems too, though, and they're repeatable.  I guess I'm just
not smart enough to figure it out.

Anyone seen these type problems illustrated by the next few images?

[I draw the lines for the primitive sides in light grey.  The region
remaining after the clip is redrawn in black.]

This example works: http://www.geocities.com/pcsanders/pass1.gif
This example works: http://www.geocities.com/pcsanders/pass2.gif
This example works: http://www.geocities.com/pcsanders/pass3.gif
This example fails: http://www.geocities.com/pcsanders/fail1.gif
This example fails: http://www.geocities.com/pcsanders/fail2.gif

Here's the clip function, as I've written it (forgive the braces; I had a
mismatch and had to work through it, adding all these, to ensure I'd done it
right).  Note that n is always 3 for my needs.

// Unoptimized C++ source starts here...

void PolygonClip(int n,
std::vector<int> &x, std::vector<int> &y, // input polygon vertices
std::vector<int> &u, std::vector<int> &v, // output polygon vertices
double xMax, double xMin,                 // edges of clip window
double yMax, double yMin)
{
double xIn, xOut, yIn, yOut;      // coordinates of entry and exit points
double tOut1, tIn2, tOut2;        // parameter values of same
double tInX, tOutX, tInY, tOutY;  // parameter values for intersections
double deltaX, deltaY;            // direction of edge
int i;

x[n] = x;
y[n] = y;

for (i = 0; i < n; i++)
{
// accept line inside
if ((x[i] > xMin) && (x[i] < xMax) &&
(y[i] > yMin) && (y[i] < yMax) &&
(x[i+1] > xMin) && (x[i+1] < xMax) &&
(y[i+1] > yMin) && (y[i+1] < yMax))
{
u.push_back(x[i]);
v.push_back(y[i]);
u.push_back(x[i+1]);
v.push_back(y[i+1]);
}
else
{
int xn = x[i+1];
int xo = x[i];

deltaX = x[i+1] - x[i];
deltaY = y[i+1] - y[i];

// determine which bounding lines for the clip region
// the containing line hits first
if ((deltaX > 0)||(deltaX==0 && x[i]>xMax))
{
xIn = xMin;
xOut = xMax;
}
else
{
xIn = xMax;
xOut = xMin;
}

if ((deltaY > 0)||(deltaY==0 && y[i]>yMax))
{
yIn = yMin;
yOut = yMax;
}
else
{
yIn = yMax;
yOut = yMin;
}

// find the t values for the x and y exit points
if (deltaX != 0)
{
tOutX = (xOut - x[i])/deltaX;
}
else if (x[i] <= xMax && xMin <= x[i])
{
tOutX = INT_MAX;
}
else
{
tOutX = INT_MIN;
}

if (deltaY != 0)
{
tOutY = (yOut - y[i])/deltaY;
}
else if (y[i] <= yMax && yMin <= y[i])
{
tOutY = INT_MAX;
}
else
{
tOutY = INT_MIN;
}

// order the two exit points
if (tOutX < tOutY)
{
tOut1 = tOutX;
tOut2 = tOutY;
}
else
{
tOut1 = tOutY;
tOut2 = tOutX;
}

if (tOut2 > 0)
{
if (deltaX != 0)
{
tInX = (xIn - x[i])/deltaX;
}
else
{
tInX = INT_MIN;
}

if (deltaY != 0)
{
tInY = (yIn - y[i])/deltaY;
}
else
{
tInY = INT_MIN;
}

if (tInX < tInY)
{
tIn2 = tInY;
}
else
{
tIn2 = tInX;
}

if (tOut1 < tIn2)
{
if (0 < tOut1 && tOut1 <= 1)
{
// line crosses over intermediate corner region
if (tInX < tInY)
{
u.push_back(xOut);
v.push_back(yIn);
}
else
{
u.push_back(xIn);
v.push_back(yOut);
}
}
}
else
{
// line crosses through window
if (0 < tOut1 && tIn2 <= 1)
{
if (0 < tIn2)
{
if (tInX > tInY)
{
u.push_back(xIn);
v.push_back(y[i] + tInX*deltaY);
}
else
{
u.push_back(x[i] + tInY*deltaX);
v.push_back(yIn);
}

if (1 > tOut1)
{
if (tOutX < tOutY)
{
u.push_back(xOut);
v.push_back(y[i]+tOutX*deltaY);
}
else
{
u.push_back(x[i]+tOutY*deltaX);
v.push_back(yOut);
}
}
else
{
u.push_back(x[i+1]);
v.push_back(y[i+1]);
}
}
}
}
if (0 < tOut2 && tOut2 <= 1)
{
u.push_back(xOut);
v.push_back(yOut);
}
} // if tOut2
} // if not accepting line
} // for

} // clip

// Unoptimized C++ source ends here...

--
Paxton Sanders
pcsand...@yahoo.com

The man who does not read good books has no
advantage over the man who cannot read them.
-- Mark Twain

Does anyone have a 3D version of the Liang-Barsky Polygon (not line)
clipping algorithm they could email me?  Anything would be appreciated
(pseudocode, any language, even a description of the modifications
to the 2D - though I think I understand most of that).  I don't
want to reinvent the wheel unless I have to.

Thanks in advance!
Steve Wampler
{...!arizona!naucse!sbw}