Liang-Barsky 2D polygon clipper ; beginner problem

Liang-Barsky 2D polygon clipper ; beginner problem

Post by Paxton C. Sande » Tue, 19 Jun 2001 08:17:08



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[0];
  y[n] = y[0];

  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

 
 
 

1. 3D Liang-Barsky Polygon Clipping

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}

2. genesis VFX

3. More on Liang-Barsky Polygon Clipping

4. Am I doing this right?

5. Liang-Barsky Polygon Clipping C source posted

6. learning expressions

7. Modified Liang-Barsky Polygon Clipping

8. change the index property at run time

9. Liang-Barsky Polygon Clipping Questions

10. Liang/Barsky Polygon Clipping : Summary

11. Liang-Barsky 3D Polygon Clipping Question

12. Liang-barsky polygon clipping again!

13. Liang-Barsky Polygon Clipping Probs