src/video/SDL_rect.c
author Andreas Schiffler <aschiffler@ferzkopp.net>
Sun, 04 Sep 2011 20:34:48 -0700
changeset 5869 065c76282d68
parent 5535 96594ac5fd1a
child 5902 d3d839b15c2f
permissions -rw-r--r--
Added input parameter validation to some SDL_rect functions
     1 /*
     2   Simple DirectMedia Layer
     3   Copyright (C) 1997-2011 Sam Lantinga <slouken@libsdl.org>
     4 
     5   This software is provided 'as-is', without any express or implied
     6   warranty.  In no event will the authors be held liable for any damages
     7   arising from the use of this software.
     8 
     9   Permission is granted to anyone to use this software for any purpose,
    10   including commercial applications, and to alter it and redistribute it
    11   freely, subject to the following restrictions:
    12 
    13   1. The origin of this software must not be misrepresented; you must not
    14      claim that you wrote the original software. If you use this software
    15      in a product, an acknowledgment in the product documentation would be
    16      appreciated but is not required.
    17   2. Altered source versions must be plainly marked as such, and must not be
    18      misrepresented as being the original software.
    19   3. This notice may not be removed or altered from any source distribution.
    20 */
    21 #include "SDL_config.h"
    22 
    23 #include "SDL_rect.h"
    24 
    25 
    26 SDL_bool
    27 SDL_HasIntersection(const SDL_Rect * A, const SDL_Rect * B)
    28 {
    29     int Amin, Amax, Bmin, Bmax;
    30 
    31     if (!A || !B) {
    32         // TODO error message
    33         return SDL_FALSE;
    34     }
    35 
    36     /* Horizontal intersection */
    37     Amin = A->x;
    38     Amax = Amin + A->w;
    39     Bmin = B->x;
    40     Bmax = Bmin + B->w;
    41     if (Bmin > Amin)
    42         Amin = Bmin;
    43     if (Bmax < Amax)
    44         Amax = Bmax;
    45     if (Amax <= Amin)
    46         return SDL_FALSE;
    47 
    48     /* Vertical intersection */
    49     Amin = A->y;
    50     Amax = Amin + A->h;
    51     Bmin = B->y;
    52     Bmax = Bmin + B->h;
    53     if (Bmin > Amin)
    54         Amin = Bmin;
    55     if (Bmax < Amax)
    56         Amax = Bmax;
    57     if (Amax <= Amin)
    58         return SDL_FALSE;
    59 
    60     return SDL_TRUE;
    61 }
    62 
    63 SDL_bool
    64 SDL_IntersectRect(const SDL_Rect * A, const SDL_Rect * B, SDL_Rect * result)
    65 {
    66     int Amin, Amax, Bmin, Bmax;
    67 
    68     if (!A || !B || !result) {
    69         // TODO error message
    70         return SDL_FALSE;
    71     }
    72 
    73     /* Horizontal intersection */
    74     Amin = A->x;
    75     Amax = Amin + A->w;
    76     Bmin = B->x;
    77     Bmax = Bmin + B->w;
    78     if (Bmin > Amin)
    79         Amin = Bmin;
    80     result->x = Amin;
    81     if (Bmax < Amax)
    82         Amax = Bmax;
    83     result->w = Amax - Amin;
    84 
    85     /* Vertical intersection */
    86     Amin = A->y;
    87     Amax = Amin + A->h;
    88     Bmin = B->y;
    89     Bmax = Bmin + B->h;
    90     if (Bmin > Amin)
    91         Amin = Bmin;
    92     result->y = Amin;
    93     if (Bmax < Amax)
    94         Amax = Bmax;
    95     result->h = Amax - Amin;
    96 
    97     return !SDL_RectEmpty(result);
    98 }
    99 
   100 void
   101 SDL_UnionRect(const SDL_Rect * A, const SDL_Rect * B, SDL_Rect * result)
   102 {
   103     int Amin, Amax, Bmin, Bmax;
   104 
   105     if (!A || !B || !result) {
   106         return;
   107     }
   108 
   109     /* Horizontal union */
   110     Amin = A->x;
   111     Amax = Amin + A->w;
   112     Bmin = B->x;
   113     Bmax = Bmin + B->w;
   114     if (Bmin < Amin)
   115         Amin = Bmin;
   116     result->x = Amin;
   117     if (Bmax > Amax)
   118         Amax = Bmax;
   119     result->w = Amax - Amin;
   120 
   121     /* Vertical intersection */
   122     Amin = A->y;
   123     Amax = Amin + A->h;
   124     Bmin = B->y;
   125     Bmax = Bmin + B->h;
   126     if (Bmin < Amin)
   127         Amin = Bmin;
   128     result->y = Amin;
   129     if (Bmax > Amax)
   130         Amax = Bmax;
   131     result->h = Amax - Amin;
   132 }
   133 
   134 SDL_bool
   135 SDL_EnclosePoints(const SDL_Point * points, int count, const SDL_Rect * clip,
   136                   SDL_Rect * result)
   137 {
   138     int minx = 0;
   139     int miny = 0;
   140     int maxx = 0;
   141     int maxy = 0;
   142     int x, y, i;
   143 
   144     if (!points || !clip) {
   145         // TODO error message
   146         return SDL_FALSE;
   147     }
   148 
   149     if (count < 1) {
   150         // TODO error message
   151         return SDL_FALSE;
   152     }
   153 
   154     if (clip) {
   155         SDL_bool added = SDL_FALSE;
   156         int clip_minx = clip->x;
   157         int clip_miny = clip->y;
   158         int clip_maxx = clip->x+clip->w-1;
   159         int clip_maxy = clip->y+clip->h-1;
   160 
   161         for (i = 0; i < count; ++i) {
   162             x = points[i].x;
   163             y = points[i].y;
   164 
   165             if (x < clip_minx || x > clip_maxx ||
   166                 y < clip_miny || y > clip_maxy) {
   167                 continue;
   168             }
   169             if (!added) {
   170                 minx = maxx = x;
   171                 miny = maxy = y;
   172                 added = SDL_TRUE;
   173                 continue;
   174             }
   175             if (x < minx) {
   176                 minx = x;
   177             } else if (x > maxx) {
   178                 maxx = x;
   179             }
   180             if (y < miny) {
   181                 miny = y;
   182             } else if (y > maxy) {
   183                 maxy = y;
   184             }
   185         }
   186         if (!added) {
   187             return SDL_FALSE;
   188         }
   189     } else {
   190         /* No clipping, always add the first point */
   191         minx = maxx = points[0].x;
   192         miny = maxy = points[0].y;
   193 
   194         for (i = 1; i < count; ++i) {
   195             x = points[i].x;
   196             y = points[i].y;
   197 
   198             if (x < minx) {
   199                 minx = x;
   200             } else if (x > maxx) {
   201                 maxx = x;
   202             }
   203             if (y < miny) {
   204                 miny = y;
   205             } else if (y > maxy) {
   206                 maxy = y;
   207             }
   208         }
   209     }
   210 
   211     if (result) {
   212         result->x = minx;
   213         result->y = miny;
   214         result->w = (maxx-minx)+1;
   215         result->h = (maxy-miny)+1;
   216     }
   217     return SDL_TRUE;
   218 }
   219 
   220 /* Use the Cohen-Sutherland algorithm for line clipping */
   221 #define CODE_BOTTOM 1
   222 #define CODE_TOP    2
   223 #define CODE_LEFT   4
   224 #define CODE_RIGHT  8
   225 
   226 static int ComputeOutCode(const SDL_Rect * rect, int x, int y)
   227 {
   228     int code = 0;
   229     if (y < 0) {
   230         code |= CODE_TOP;
   231     } else if (y >= rect->y + rect->h) {
   232         code |= CODE_BOTTOM;
   233     }
   234     if (x < 0) {
   235         code |= CODE_LEFT;
   236     } else if (x >= rect->x + rect->w) {
   237         code |= CODE_RIGHT;
   238     }
   239     return code;
   240 }
   241 
   242 SDL_bool
   243 SDL_IntersectRectAndLine(const SDL_Rect * rect, int *X1, int *Y1, int *X2,
   244                          int *Y2)
   245 {
   246     int x = 0;
   247     int y = 0;
   248     int x1, y1;
   249     int x2, y2;
   250     int rectx1;
   251     int recty1;
   252     int rectx2;
   253     int recty2;
   254     int outcode1, outcode2;
   255 
   256     if (!rect || !X1 || !Y1 || !X2 || !Y2) {
   257         // TODO error message
   258         return SDL_FALSE;
   259     }
   260 
   261     x1 = *X1;
   262     y1 = *Y1;
   263     x2 = *X2;
   264     y2 = *Y2;
   265     rectx1 = rect->x;
   266     recty1 = rect->y;
   267     rectx2 = rect->x + rect->w - 1;
   268     recty2 = rect->y + rect->h - 1;
   269 
   270     /* Check to see if entire line is inside rect */
   271     if (x1 >= rectx1 && x1 <= rectx2 && x2 >= rectx1 && x2 <= rectx2 &&
   272         y1 >= recty1 && y1 <= recty2 && y2 >= recty1 && y2 <= recty2) {
   273         return SDL_TRUE;
   274     }
   275 
   276     /* Check to see if entire line is to one side of rect */
   277     if ((x1 < rectx1 && x2 < rectx1) || (x1 > rectx2 && x2 > rectx2) ||
   278         (y1 < recty1 && y2 < recty1) || (y1 > recty2 && y2 > recty2)) {
   279         return SDL_FALSE;
   280     }
   281 
   282     if (y1 == y2) {
   283         /* Horizontal line, easy to clip */
   284         if (x1 < rectx1) {
   285             *X1 = rectx1;
   286         } else if (x1 > rectx2) {
   287             *X1 = rectx2;
   288         }
   289         if (x2 < rectx1) {
   290             *X2 = rectx1;
   291         } else if (x2 > rectx2) {
   292             *X2 = rectx2;
   293         }
   294         return SDL_TRUE;
   295     }
   296 
   297     if (x1 == x2) {
   298         /* Vertical line, easy to clip */
   299         if (y1 < recty1) {
   300             *Y1 = recty1;
   301         } else if (y1 > recty2) {
   302             *Y1 = recty2;
   303         }
   304         if (y2 < recty1) {
   305             *Y2 = recty1;
   306         } else if (y2 > recty2) {
   307             *Y2 = recty2;
   308         }
   309         return SDL_TRUE;
   310     }
   311 
   312     /* More complicated Cohen-Sutherland algorithm */
   313     outcode1 = ComputeOutCode(rect, x1, y1);
   314     outcode2 = ComputeOutCode(rect, x2, y2);
   315     while (outcode1 || outcode2) {
   316         if (outcode1 & outcode2) {
   317             return SDL_FALSE;
   318         }
   319 
   320         if (outcode1) {
   321             if (outcode1 & CODE_TOP) {
   322                 y = recty1;
   323                 x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1);
   324             } else if (outcode1 & CODE_BOTTOM) {
   325                 y = recty2;
   326                 x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1);
   327             } else if (outcode1 & CODE_LEFT) {
   328                 x = rectx1;
   329                 y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
   330             } else if (outcode1 & CODE_RIGHT) {
   331                 x = rectx2;
   332                 y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
   333             }
   334             x1 = x;
   335             y1 = y;
   336             outcode1 = ComputeOutCode(rect, x, y);
   337         } else {
   338             if (outcode2 & CODE_TOP) {
   339                 y = recty1;
   340                 x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1);
   341             } else if (outcode2 & CODE_BOTTOM) {
   342                 y = recty2;
   343                 x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1);
   344             } else if (outcode2 & CODE_LEFT) {
   345                 x = rectx1;
   346                 y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
   347             } else if (outcode2 & CODE_RIGHT) {
   348                 x = rectx2;
   349                 y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
   350             }
   351             x2 = x;
   352             y2 = y;
   353             outcode2 = ComputeOutCode(rect, x, y);
   354         }
   355     }
   356     *X1 = x1;
   357     *Y1 = y1;
   358     *X2 = x2;
   359     *Y2 = y2;
   360     return SDL_TRUE;
   361 }
   362 
   363 SDL_bool
   364 SDL_GetSpanEnclosingRect(int width, int height,
   365                          int numrects, SDL_Rect * rects, SDL_Rect *span)
   366 {
   367     int i;
   368     int span_y1, span_y2;
   369     int rect_y1, rect_y2;
   370 
   371     if (width < 1 || height < 1) {
   372         // TODO error message
   373         return SDL_FALSE;
   374     }
   375 
   376     if (!rects || !span) {
   377         // TODO error message
   378         return SDL_FALSE;
   379     }
   380 
   381     if (numrects < 1) {
   382         // TODO error message
   383         return SDL_FALSE;
   384     }
   385 
   386     /* Initialize to empty rect */
   387     span_y1 = height;
   388     span_y2 = 0;
   389 
   390     for (i = 0; i < numrects; ++i) {
   391         rect_y1 = rects[i].y;
   392         rect_y2 = rect_y1 + rects[i].h;
   393 
   394         /* Clip out of bounds rectangles, and expand span rect */
   395         if (rect_y1 < 0) {
   396             span_y1 = 0;
   397         } else if (rect_y1 < span_y1) {
   398             span_y1 = rect_y1;
   399         }
   400         if (rect_y2 > height) {
   401             span_y2 = height;
   402         } else if (rect_y2 > span_y2) {
   403             span_y2 = rect_y2;
   404         }
   405     }
   406     if (span_y2 > span_y1) {
   407         span->x = 0;
   408         span->y = span_y1;
   409         span->w = width;
   410         span->h = (span_y2 - span_y1);
   411         return SDL_TRUE;
   412     }
   413     return SDL_FALSE;
   414 }
   415 
   416 /* vi: set ts=4 sw=4 expandtab: */