src/video/SDL_rect.c
author Andreas Schiffler <aschiffler@ferzkopp.net>
Sat, 17 Sep 2011 22:35:57 -0700
changeset 5950 36fa6d12784b
parent 5902 d3d839b15c2f
child 5953 fecf71a834ed
permissions -rw-r--r--
Add special cases for empty rectangles in 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     /* Special cases for empty rects */
    37     if (SDL_RectEmpty(A) || SDL_RectEmpty(B)) {
    38         return SDL_FALSE;
    39     }
    40 
    41     /* Horizontal intersection */
    42     Amin = A->x;
    43     Amax = Amin + A->w;
    44     Bmin = B->x;
    45     Bmax = Bmin + B->w;
    46     if (Bmin > Amin)
    47         Amin = Bmin;
    48     if (Bmax < Amax)
    49         Amax = Bmax;
    50     if (Amax <= Amin)
    51         return SDL_FALSE;
    52 
    53     /* Vertical intersection */
    54     Amin = A->y;
    55     Amax = Amin + A->h;
    56     Bmin = B->y;
    57     Bmax = Bmin + B->h;
    58     if (Bmin > Amin)
    59         Amin = Bmin;
    60     if (Bmax < Amax)
    61         Amax = Bmax;
    62     if (Amax <= Amin)
    63         return SDL_FALSE;
    64 
    65     return SDL_TRUE;
    66 }
    67 
    68 SDL_bool
    69 SDL_IntersectRect(const SDL_Rect * A, const SDL_Rect * B, SDL_Rect * result)
    70 {
    71     int Amin, Amax, Bmin, Bmax;
    72 
    73     if (!A || !B || !result) {
    74         // TODO error message
    75         return SDL_FALSE;
    76     }
    77 
    78     /* Special cases for empty rects */
    79     if (SDL_RectEmpty(A) || SDL_RectEmpty(B)) {
    80         return SDL_FALSE;
    81     }
    82     
    83     /* Horizontal intersection */
    84     Amin = A->x;
    85     Amax = Amin + A->w;
    86     Bmin = B->x;
    87     Bmax = Bmin + B->w;
    88     if (Bmin > Amin)
    89         Amin = Bmin;
    90     result->x = Amin;
    91     if (Bmax < Amax)
    92         Amax = Bmax;
    93     result->w = Amax - Amin;
    94 
    95     /* Vertical intersection */
    96     Amin = A->y;
    97     Amax = Amin + A->h;
    98     Bmin = B->y;
    99     Bmax = Bmin + B->h;
   100     if (Bmin > Amin)
   101         Amin = Bmin;
   102     result->y = Amin;
   103     if (Bmax < Amax)
   104         Amax = Bmax;
   105     result->h = Amax - Amin;
   106 
   107     return !SDL_RectEmpty(result);
   108 }
   109 
   110 void
   111 SDL_UnionRect(const SDL_Rect * A, const SDL_Rect * B, SDL_Rect * result)
   112 {
   113     int Amin, Amax, Bmin, Bmax;
   114 
   115     if (!A || !B || !result) {
   116         return;
   117     }
   118 
   119     /* Special cases for empty Rects */
   120     if (SDL_RectEmpty(A)) {
   121       if (SDL_RectEmpty(B)) {
   122        /* A and B empty */
   123        return;
   124       } else {
   125        /* A empty, B not empty */
   126        *result = *B;
   127        return;
   128       }
   129     } else {      
   130       if (SDL_RectEmpty(B)) {
   131        /* A not empty, B empty */
   132        *result = *A;
   133        return;
   134       } 
   135     }
   136     
   137     /* Horizontal union */
   138     Amin = A->x;
   139     Amax = Amin + A->w;
   140     Bmin = B->x;
   141     Bmax = Bmin + B->w;
   142     if (Bmin < Amin)
   143         Amin = Bmin;
   144     result->x = Amin;
   145     if (Bmax > Amax)
   146         Amax = Bmax;
   147     result->w = Amax - Amin;
   148 
   149     /* Vertical union */
   150     Amin = A->y;
   151     Amax = Amin + A->h;
   152     Bmin = B->y;
   153     Bmax = Bmin + B->h;
   154     if (Bmin < Amin)
   155         Amin = Bmin;
   156     result->y = Amin;
   157     if (Bmax > Amax)
   158         Amax = Bmax;
   159     result->h = Amax - Amin;
   160 }
   161 
   162 SDL_bool
   163 SDL_EnclosePoints(const SDL_Point * points, int count, const SDL_Rect * clip,
   164                   SDL_Rect * result)
   165 {
   166     int minx = 0;
   167     int miny = 0;
   168     int maxx = 0;
   169     int maxy = 0;
   170     int x, y, i;
   171 
   172     if (!points) {
   173         // TODO error message
   174         return SDL_FALSE;
   175     }
   176 
   177     if (count < 1) {
   178         // TODO error message
   179         return SDL_FALSE;
   180     }
   181 
   182     if (clip) {
   183         /* Special case for empty rectangle */
   184         if (SDL_RectEmpty(clip)) {
   185             return SDL_FALSE;
   186         }
   187         
   188         SDL_bool added = SDL_FALSE;
   189         int clip_minx = clip->x;
   190         int clip_miny = clip->y;
   191         int clip_maxx = clip->x+clip->w-1;
   192         int clip_maxy = clip->y+clip->h-1;
   193 
   194         for (i = 0; i < count; ++i) {
   195             x = points[i].x;
   196             y = points[i].y;
   197 
   198             if (x < clip_minx || x > clip_maxx ||
   199                 y < clip_miny || y > clip_maxy) {
   200                 continue;
   201             }
   202             if (!added) {
   203                 /* Special case: if no result was requested, we are done */
   204                 if (result == NULL) {
   205                     return SDL_TRUE;
   206                 }
   207 
   208                 /* First point added */
   209                 minx = maxx = x;
   210                 miny = maxy = y;
   211                 added = SDL_TRUE;
   212                 continue;
   213             }
   214             if (x < minx) {
   215                 minx = x;
   216             } else if (x > maxx) {
   217                 maxx = x;
   218             }
   219             if (y < miny) {
   220                 miny = y;
   221             } else if (y > maxy) {
   222                 maxy = y;
   223             }
   224         }
   225         if (!added) {
   226             return SDL_FALSE;
   227         }
   228     } else {
   229         /* Special case: if no result was requested, we are done */
   230         if (result == NULL) {
   231             return SDL_TRUE;
   232         }
   233         
   234         /* No clipping, always add the first point */
   235         minx = maxx = points[0].x;
   236         miny = maxy = points[0].y;
   237 
   238         for (i = 1; i < count; ++i) {
   239             x = points[i].x;
   240             y = points[i].y;
   241 
   242             if (x < minx) {
   243                 minx = x;
   244             } else if (x > maxx) {
   245                 maxx = x;
   246             }
   247             if (y < miny) {
   248                 miny = y;
   249             } else if (y > maxy) {
   250                 maxy = y;
   251             }
   252         }
   253     }
   254 
   255     if (result) {
   256         result->x = minx;
   257         result->y = miny;
   258         result->w = (maxx-minx)+1;
   259         result->h = (maxy-miny)+1;
   260     }
   261     return SDL_TRUE;
   262 }
   263 
   264 /* Use the Cohen-Sutherland algorithm for line clipping */
   265 #define CODE_BOTTOM 1
   266 #define CODE_TOP    2
   267 #define CODE_LEFT   4
   268 #define CODE_RIGHT  8
   269 
   270 static int ComputeOutCode(const SDL_Rect * rect, int x, int y)
   271 {
   272     int code = 0;
   273     if (y < 0) {
   274         code |= CODE_TOP;
   275     } else if (y >= rect->y + rect->h) {
   276         code |= CODE_BOTTOM;
   277     }
   278     if (x < 0) {
   279         code |= CODE_LEFT;
   280     } else if (x >= rect->x + rect->w) {
   281         code |= CODE_RIGHT;
   282     }
   283     return code;
   284 }
   285 
   286 SDL_bool
   287 SDL_IntersectRectAndLine(const SDL_Rect * rect, int *X1, int *Y1, int *X2,
   288                          int *Y2)
   289 {
   290     int x = 0;
   291     int y = 0;
   292     int x1, y1;
   293     int x2, y2;
   294     int rectx1;
   295     int recty1;
   296     int rectx2;
   297     int recty2;
   298     int outcode1, outcode2;
   299 
   300     if (!rect || !X1 || !Y1 || !X2 || !Y2) {
   301         // TODO error message
   302         return SDL_FALSE;
   303     }
   304 
   305     /* Special case for empty rect */
   306     if (SDL_RectEmpty(rect)) {
   307         return SDL_FALSE;
   308     }
   309     
   310     x1 = *X1;
   311     y1 = *Y1;
   312     x2 = *X2;
   313     y2 = *Y2;
   314     rectx1 = rect->x;
   315     recty1 = rect->y;
   316     rectx2 = rect->x + rect->w - 1;
   317     recty2 = rect->y + rect->h - 1;
   318 
   319     /* Check to see if entire line is inside rect */
   320     if (x1 >= rectx1 && x1 <= rectx2 && x2 >= rectx1 && x2 <= rectx2 &&
   321         y1 >= recty1 && y1 <= recty2 && y2 >= recty1 && y2 <= recty2) {
   322         return SDL_TRUE;
   323     }
   324 
   325     /* Check to see if entire line is to one side of rect */
   326     if ((x1 < rectx1 && x2 < rectx1) || (x1 > rectx2 && x2 > rectx2) ||
   327         (y1 < recty1 && y2 < recty1) || (y1 > recty2 && y2 > recty2)) {
   328         return SDL_FALSE;
   329     }
   330 
   331     if (y1 == y2) {
   332         /* Horizontal line, easy to clip */
   333         if (x1 < rectx1) {
   334             *X1 = rectx1;
   335         } else if (x1 > rectx2) {
   336             *X1 = rectx2;
   337         }
   338         if (x2 < rectx1) {
   339             *X2 = rectx1;
   340         } else if (x2 > rectx2) {
   341             *X2 = rectx2;
   342         }
   343         return SDL_TRUE;
   344     }
   345 
   346     if (x1 == x2) {
   347         /* Vertical line, easy to clip */
   348         if (y1 < recty1) {
   349             *Y1 = recty1;
   350         } else if (y1 > recty2) {
   351             *Y1 = recty2;
   352         }
   353         if (y2 < recty1) {
   354             *Y2 = recty1;
   355         } else if (y2 > recty2) {
   356             *Y2 = recty2;
   357         }
   358         return SDL_TRUE;
   359     }
   360 
   361     /* More complicated Cohen-Sutherland algorithm */
   362     outcode1 = ComputeOutCode(rect, x1, y1);
   363     outcode2 = ComputeOutCode(rect, x2, y2);
   364     while (outcode1 || outcode2) {
   365         if (outcode1 & outcode2) {
   366             return SDL_FALSE;
   367         }
   368 
   369         if (outcode1) {
   370             if (outcode1 & CODE_TOP) {
   371                 y = recty1;
   372                 x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1);
   373             } else if (outcode1 & CODE_BOTTOM) {
   374                 y = recty2;
   375                 x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1);
   376             } else if (outcode1 & CODE_LEFT) {
   377                 x = rectx1;
   378                 y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
   379             } else if (outcode1 & CODE_RIGHT) {
   380                 x = rectx2;
   381                 y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
   382             }
   383             x1 = x;
   384             y1 = y;
   385             outcode1 = ComputeOutCode(rect, x, y);
   386         } else {
   387             if (outcode2 & CODE_TOP) {
   388                 y = recty1;
   389                 x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1);
   390             } else if (outcode2 & CODE_BOTTOM) {
   391                 y = recty2;
   392                 x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1);
   393             } else if (outcode2 & CODE_LEFT) {
   394                 x = rectx1;
   395                 y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
   396             } else if (outcode2 & CODE_RIGHT) {
   397                 x = rectx2;
   398                 y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
   399             }
   400             x2 = x;
   401             y2 = y;
   402             outcode2 = ComputeOutCode(rect, x, y);
   403         }
   404     }
   405     *X1 = x1;
   406     *Y1 = y1;
   407     *X2 = x2;
   408     *Y2 = y2;
   409     return SDL_TRUE;
   410 }
   411 
   412 SDL_bool
   413 SDL_GetSpanEnclosingRect(int width, int height,
   414                          int numrects, SDL_Rect * rects, SDL_Rect *span)
   415 {
   416     int i;
   417     int span_y1, span_y2;
   418     int rect_y1, rect_y2;
   419 
   420     if (width < 1 || height < 1) {
   421         // TODO error message
   422         return SDL_FALSE;
   423     }
   424 
   425     if (!rects || !span) {
   426         // TODO error message
   427         return SDL_FALSE;
   428     }
   429 
   430     if (numrects < 1) {
   431         // TODO error message
   432         return SDL_FALSE;
   433     }
   434 
   435     /* Initialize to empty rect */
   436     span_y1 = height;
   437     span_y2 = 0;
   438 
   439     for (i = 0; i < numrects; ++i) {
   440         rect_y1 = rects[i].y;
   441         rect_y2 = rect_y1 + rects[i].h;
   442 
   443         /* Clip out of bounds rectangles, and expand span rect */
   444         if (rect_y1 < 0) {
   445             span_y1 = 0;
   446         } else if (rect_y1 < span_y1) {
   447             span_y1 = rect_y1;
   448         }
   449         if (rect_y2 > height) {
   450             span_y2 = height;
   451         } else if (rect_y2 > span_y2) {
   452             span_y2 = rect_y2;
   453         }
   454     }
   455     if (span_y2 > span_y1) {
   456         span->x = 0;
   457         span->y = span_y1;
   458         span->w = width;
   459         span->h = (span_y2 - span_y1);
   460         return SDL_TRUE;
   461     }
   462     return SDL_FALSE;
   463 }
   464 
   465 /* vi: set ts=4 sw=4 expandtab: */