src/video/SDL_rect.c
changeset 3541 0c429a5fda8a
parent 3536 0267b8b1595c
child 3542 97eae5a705f9
     1.1 --- a/src/video/SDL_rect.c	Fri Dec 11 09:13:51 2009 +0000
     1.2 +++ b/src/video/SDL_rect.c	Fri Dec 11 09:22:34 2009 +0000
     1.3 @@ -196,16 +196,40 @@
     1.4      return SDL_TRUE;
     1.5  }
     1.6  
     1.7 +/* Use the Cohen-Sutherland algorithm for line clipping */
     1.8 +#define CODE_BOTTOM 1
     1.9 +#define CODE_TOP    2
    1.10 +#define CODE_LEFT   4
    1.11 +#define CODE_RIGHT  8
    1.12 +
    1.13 +static int ComputeOutCode(const SDL_Rect * rect, int x, int y)
    1.14 +{
    1.15 +    int code = 0;
    1.16 +    if (y < 0) {
    1.17 +        code |= CODE_TOP;
    1.18 +    } else if (y >= rect->y + rect->h) {
    1.19 +        code |= CODE_BOTTOM;
    1.20 +    }
    1.21 +    if (x < 0) {
    1.22 +        code |= CODE_LEFT;
    1.23 +    } else if (x >= rect->x + rect->w) {
    1.24 +        code |= CODE_RIGHT;
    1.25 +    }
    1.26 +    return code;
    1.27 +}
    1.28 +
    1.29  SDL_bool
    1.30  SDL_IntersectRectAndLine(const SDL_Rect * rect, int *X1, int *Y1, int *X2,
    1.31                           int *Y2)
    1.32  {
    1.33 +    int x, y;
    1.34      int x1, y1;
    1.35      int x2, y2;
    1.36      int rectx1;
    1.37      int recty1;
    1.38      int rectx2;
    1.39      int recty2;
    1.40 +    int outcode1, outcode2;
    1.41  
    1.42      if (!rect || !X1 || !Y1 || !X2 || !Y2) {
    1.43          return SDL_FALSE;
    1.44 @@ -262,95 +286,57 @@
    1.45          return SDL_TRUE;
    1.46      }
    1.47  
    1.48 -    else {
    1.49 -        /* The task of clipping a line with finite slope ratios in a fixed-
    1.50 -         * precision coordinate space is not as immediately simple as it is
    1.51 -         * with coordinates of arbitrary precision. If the ratio of slopes
    1.52 -         * between the input line segment and the result line segment is not
    1.53 -         * a whole number, you have in fact *moved* the line segment a bit,
    1.54 -         * and there can be no avoiding it without more precision
    1.55 -         */
    1.56 -        int *x_result_[] = { X1, X2, NULL }, **x_result = x_result_;
    1.57 -        int *y_result_[] = { Y1, Y2, NULL }, **y_result = y_result_;
    1.58 -        SDL_bool intersection = SDL_FALSE;
    1.59 -        double b, m, left, right, bottom, top;
    1.60 -        int xl, xh, yl, yh;
    1.61 -
    1.62 -        /* solve mx+b line formula */
    1.63 -        m = (double) (y1 - y2) / (double) (x1 - x2);
    1.64 -        b = y2 - m * (double) x2;
    1.65 -
    1.66 -        /* find some linear intersections */
    1.67 -        left = (m * (double) rectx1) + b;
    1.68 -        right = (m * (double) rectx2) + b;
    1.69 -        top = (recty1 - b) / m;
    1.70 -        bottom = (recty2 - b) / m;
    1.71 -
    1.72 -        /* sort end-points' x and y components individually */
    1.73 -        if (x1 < x2) {
    1.74 -            xl = x1;
    1.75 -            xh = x2;
    1.76 -        } else {
    1.77 -            xl = x2;
    1.78 -            xh = x1;
    1.79 -        }
    1.80 -        if (y1 < y2) {
    1.81 -            yl = y1;
    1.82 -            yh = y2;
    1.83 -        } else {
    1.84 -            yl = y2;
    1.85 -            yh = y1;
    1.86 +    /* More complicated Cohen-Sutherland algorithm */
    1.87 +    outcode1 = ComputeOutCode(rect, x1, y1);
    1.88 +    outcode2 = ComputeOutCode(rect, x2, y2);
    1.89 +    while (outcode1 || outcode2) {
    1.90 +        if (outcode1 & outcode2) {
    1.91 +            return SDL_FALSE;
    1.92          }
    1.93  
    1.94 -#define RISING(a, b, c) (((a)<=(b))&&((b)<=(c)))
    1.95 -
    1.96 -        /* check for a point that's entirely inside the rect */
    1.97 -        if (RISING(rectx1, x1, rectx2) && RISING(recty1, y1, recty2)) {
    1.98 -            x_result++;
    1.99 -            y_result++;
   1.100 -            intersection = SDL_TRUE;
   1.101 -        } else
   1.102 -            /* it was determined earlier that *both* end-points are not contained */
   1.103 -        if (RISING(rectx1, x2, rectx2) && RISING(recty1, y2, recty2)) {
   1.104 -            **(x_result++) = x2;
   1.105 -            **(y_result++) = y2;
   1.106 -            intersection = SDL_TRUE;
   1.107 -        }
   1.108 -
   1.109 -        if (RISING(recty1, left, recty2) && RISING(xl, rectx1, xh)) {
   1.110 -            **(x_result++) = rectx1;
   1.111 -            **(y_result++) = (int) left;
   1.112 -            intersection = SDL_TRUE;
   1.113 +        if (outcode1) {
   1.114 +            if (outcode1 & CODE_TOP) {
   1.115 +                y = recty1;
   1.116 +                x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1);
   1.117 +            } else if (outcode1 & CODE_BOTTOM) {
   1.118 +                y = recty2;
   1.119 +                x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1);
   1.120 +            } else if (outcode1 & CODE_LEFT) {
   1.121 +                x = rectx1;
   1.122 +                y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
   1.123 +            } else if (outcode1 & CODE_RIGHT) {
   1.124 +                x = rectx2;
   1.125 +                y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
   1.126 +            }
   1.127 +            x1 = x;
   1.128 +            y1 = y;
   1.129 +            outcode1 = ComputeOutCode(rect, x, y);
   1.130          }
   1.131  
   1.132 -        if (*x_result == NULL)
   1.133 -            return intersection;
   1.134 -        if (RISING(recty1, right, recty2) && RISING(xl, rectx2, xh)) {
   1.135 -            **(x_result++) = rectx2;
   1.136 -            **(y_result++) = (int) right;
   1.137 -            intersection = SDL_TRUE;
   1.138 +        if (outcode2) {
   1.139 +            if (outcode2 & CODE_TOP) {
   1.140 +                y = recty1;
   1.141 +                x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1);
   1.142 +            } else if (outcode2 & CODE_BOTTOM) {
   1.143 +                y = recty2;
   1.144 +                x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1);
   1.145 +            } else if (outcode2 & CODE_LEFT) {
   1.146 +                x = rectx1;
   1.147 +                y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
   1.148 +            } else if (outcode2 & CODE_RIGHT) {
   1.149 +                x = rectx2;
   1.150 +                y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
   1.151 +            }
   1.152 +            x2 = x;
   1.153 +            y2 = y;
   1.154 +            outcode2 = ComputeOutCode(rect, x, y);
   1.155          }
   1.156 -
   1.157 -        if (*x_result == NULL)
   1.158 -            return intersection;
   1.159 -        if (RISING(rectx1, top, rectx2) && RISING(yl, recty1, yh)) {
   1.160 -            **(x_result++) = (int) top;
   1.161 -            **(y_result++) = recty1;
   1.162 -            intersection = SDL_TRUE;
   1.163 -        }
   1.164 -
   1.165 -        if (*x_result == NULL)
   1.166 -            return intersection;
   1.167 -        if (RISING(rectx1, bottom, rectx2) && RISING(yl, recty2, yh)) {
   1.168 -            **(x_result++) = (int) bottom;
   1.169 -            **(y_result++) = recty2;
   1.170 -            intersection = SDL_TRUE;
   1.171 -        }
   1.172 -
   1.173 -        return intersection;
   1.174      }
   1.175 -
   1.176 -    return SDL_FALSE;
   1.177 +    *X1 = x1;
   1.178 +    *Y1 = y1;
   1.179 +    *X2 = x2;
   1.180 +    *Y2 = y2;
   1.181 +    return SDL_TRUE;
   1.182  }
   1.183  
   1.184  void