Clip line to screen coordinates

Question

I have line that is defined as two points. start = (xs,ys) end = (xe, ye)

Drawing function that I'm using Only accepts lines that are fully in screen coordinates. Screen size is (xSize, ySize).

Top left corner is (0,0). Bottom right corner is (xSize, ySize).

Some other funcions gives me line that that is defined for example as start(-50, -15) end(5000, 200). So it's ends are outside of screen size.

In C++

struct Vec2
{
 int x, y
};

Vec2 start, end //This is all little bit pseudo code
Vec2 screenSize;//You can access coordinates like start.x end.y

How can I calculate new start and endt that is at the screen edge, not outside screen. I know how to do it on paper. But I can't transfer it to c++. On paper I'm sershing for point that belongs to edge and line. But it is to much calculations for c++.

Can you help?

Answer 1

Here is a function I wrote. It cycles through all 4 planes (left, top, right, bottom) and clips each point by the plane.

// Clips a line segment to an axis-aligned rectangle
// Returns true if clipping is successful
// Returns false if line segment lies outside the rectangle
bool clipLineToRect(int a[2], int b[2],
                    int xmin, int ymin, int xmax, int ymax)
{
  int mins[2] = {xmin, ymin};
  int maxs[2] = {xmax, ymax};
  int normals[2] = {1, -1};
  for (int axis=0; axis<2; axis++) {
    for (int plane=0; plane<2; plane++) {
      // Check both points
      for (int pt=1; pt<=2; pt++) {
        int* pt1 = pt==1 ? a : b;
        int* pt2 = pt==1 ? b : a;

        // If both points are outside the same plane, the line is
        // outside the rectangle
        if ( (a[0]<xmin && b[0]<xmin) || (a[0]>xmax && b[0]>xmax) ||
             (a[1]<ymin && b[1]<ymin) || (a[1]>ymax && b[1]>ymax)) {
          return false;
        }

        const int n = normals[plane];
        if ( (n==1 && pt1[axis]<mins[axis]) ||   // check left/top plane
             (n==-1 && pt1[axis]>maxs[axis]) ) { // check right/bottom plane

          // Calculate interpolation factor t using ratio of signed distance
          // of each point from the plane
          const float p = (n==1) ? mins[axis] : maxs[axis];
          const float q1 = pt1[axis];
          const float q2 = pt2[axis];
          const float d1 = n * (q1-p);
          const float d2 = n * (q2-p);
          const float t = d1 / (d1-d2);

          // t should always be between 0 and 1
          if (t<0 || t >1) {
            return false;
          }

          // Interpolate to find the new point
          pt1[0] = (int)(pt1[0] +  (pt2[0] - pt1[0]) * t );
          pt1[1] = (int)(pt1[1] +  (pt2[1] - pt1[1]) * t );
        }
      }
    }
  }
  return true;
}

Example Usage:

void testClipLineToRect()
{
  int screenWidth = 320;
  int screenHeight = 240;
  int xmin=0;
  int ymin=0;
  int xmax=screenWidth-1;
  int ymax=screenHeight-1;
  int a[2] = {-10, 10};
  int b[2] = {300, 250};

  printf("Before clipping:\n\ta={%d, %d}\n\tb=[%d, %d]\n",
         a[0], a[1], b[0], b[1]);

  if (clipLineToRect(a, b, xmin, ymin, xmax, ymax)) {
    printf("After clipping:\n\ta={%d, %d}\n\tb=[%d, %d]\n",
           a[0], a[1], b[0], b[1]);
  }
  else {
    printf("clipLineToRect returned false\n");
  }
}

Output:

Before clipping:
        a={-10, 10}
        b=[300, 250]
After clipping:
        a={0, 17}
        b=[285, 239]

Answer 2

There are many line clipping algorithms like:

• Cohen–Sutherland wikipedia page with implementation
• Liang–Barsky wikipedia page
• Nicholl–Lee–Nicholl (NLN) and many more. see Line Clipping on wikipedia

[EDIT1] See below figure:

there are 3 kinds of start point:

1. sx > 0 and sy < 0 (red line)
2. sx < 0 and sy > 0 (yellow line)
3. sx < 0 and sy < 0 (green and violet lines)

In situations 1 and 2 simply find Xintersect and Yintersect respectively and choose them as new start point. As you can see, there are 2 kinds of lines in situation 3. In this situation find Xintersect and Yintersect and choose the intersect point near the end point which is the point that has minimum distance to endPoint.

min(distance(Xintersect, endPoint), distance(Yintersect, endPoint))

[EDIT2]

// Liang-Barsky function by Daniel White @ http://www.skytopia.com/project/articles/compsci/clipping.html
// This function inputs 8 numbers, and outputs 4 new numbers (plus a boolean value to say whether the clipped line is drawn at all).
//
bool LiangBarsky (double edgeLeft, double edgeRight, double edgeBottom, double edgeTop,   // Define the x/y clipping values for the border.
                  double x0src, double y0src, double x1src, double y1src,                 // Define the start and end points of the line.
                  double &x0clip, double &y0clip, double &x1clip, double &y1clip)         // The output values, so declare these outside.
{

    double t0 = 0.0;    double t1 = 1.0;
    double xdelta = x1src-x0src;
    double ydelta = y1src-y0src;
    double p,q,r;

    for(int edge=0; edge<4; edge++) {   // Traverse through left, right, bottom, top edges.
        if (edge==0) {  p = -xdelta;    q = -(edgeLeft-x0src);  }
        if (edge==1) {  p = xdelta;     q =  (edgeRight-x0src); }
        if (edge==2) {  p = -ydelta;    q = -(edgeBottom-y0src);}
        if (edge==3) {  p = ydelta;     q =  (edgeTop-y0src);   }   
        r = q/p;
        if(p==0 && q<0) return false;   // Don't draw line at all. (parallel line outside)

        if(p<0) {
            if(r>t1) return false;         // Don't draw line at all.
            else if(r>t0) t0=r;            // Line is clipped!
        } else if(p>0) {
            if(r<t0) return false;      // Don't draw line at all.
            else if(r<t1) t1=r;         // Line is clipped!
        }
    }

    x0clip = x0src + t0*xdelta;
    y0clip = y0src + t0*ydelta;
    x1clip = x0src + t1*xdelta;
    y1clip = y0src + t1*ydelta;

    return true;        // (clipped) line is drawn
}