src/video/SDL_rect.c
author Sam Lantinga
Sun, 09 May 2010 15:24:31 -0700
changeset 4456 0a5dbe96c3be
parent 3697 f7b03b6838cb
child 5154 fb424691cfc7
permissions -rw-r--r--
Fixed variable use before initialize warnings
     1 /*
     2     SDL - Simple DirectMedia Layer
     3     Copyright (C) 1997-2010 Sam Lantinga
     4 
     5     This library is free software; you can redistribute it and/or
     6     modify it under the terms of the GNU Lesser General Public
     7     License as published by the Free Software Foundation; either
     8     version 2.1 of the License, or (at your option) any later version.
     9 
    10     This library is distributed in the hope that it will be useful,
    11     but WITHOUT ANY WARRANTY; without even the implied warranty of
    12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    13     Lesser General Public License for more details.
    14 
    15     You should have received a copy of the GNU Lesser General Public
    16     License along with this library; if not, write to the Free Software
    17     Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
    18 
    19     Sam Lantinga
    20     slouken@libsdl.org
    21 */
    22 #include "SDL_config.h"
    23 
    24 #include "SDL_video.h"
    25 #include "SDL_rect_c.h"
    26 
    27 SDL_bool
    28 SDL_HasIntersection(const SDL_Rect * A, const SDL_Rect * B)
    29 {
    30     int Amin, Amax, Bmin, Bmax;
    31 
    32     /* Horizontal intersection */
    33     Amin = A->x;
    34     Amax = Amin + A->w;
    35     Bmin = B->x;
    36     Bmax = Bmin + B->w;
    37     if (Bmin > Amin)
    38         Amin = Bmin;
    39     if (Bmax < Amax)
    40         Amax = Bmax;
    41     if (Amax <= Amin)
    42         return SDL_FALSE;
    43 
    44     /* Vertical intersection */
    45     Amin = A->y;
    46     Amax = Amin + A->h;
    47     Bmin = B->y;
    48     Bmax = Bmin + B->h;
    49     if (Bmin > Amin)
    50         Amin = Bmin;
    51     if (Bmax < Amax)
    52         Amax = Bmax;
    53     if (Amax <= Amin)
    54         return SDL_FALSE;
    55 
    56     return SDL_TRUE;
    57 }
    58 
    59 SDL_bool
    60 SDL_IntersectRect(const SDL_Rect * A, const SDL_Rect * B, SDL_Rect * result)
    61 {
    62     int Amin, Amax, Bmin, Bmax;
    63 
    64     /* Horizontal intersection */
    65     Amin = A->x;
    66     Amax = Amin + A->w;
    67     Bmin = B->x;
    68     Bmax = Bmin + B->w;
    69     if (Bmin > Amin)
    70         Amin = Bmin;
    71     result->x = Amin;
    72     if (Bmax < Amax)
    73         Amax = Bmax;
    74     result->w = Amax - Amin;
    75 
    76     /* Vertical intersection */
    77     Amin = A->y;
    78     Amax = Amin + A->h;
    79     Bmin = B->y;
    80     Bmax = Bmin + B->h;
    81     if (Bmin > Amin)
    82         Amin = Bmin;
    83     result->y = Amin;
    84     if (Bmax < Amax)
    85         Amax = Bmax;
    86     result->h = Amax - Amin;
    87 
    88     return !SDL_RectEmpty(result);
    89 }
    90 
    91 void
    92 SDL_UnionRect(const SDL_Rect * A, const SDL_Rect * B, SDL_Rect * result)
    93 {
    94     int Amin, Amax, Bmin, Bmax;
    95 
    96     /* Horizontal union */
    97     Amin = A->x;
    98     Amax = Amin + A->w;
    99     Bmin = B->x;
   100     Bmax = Bmin + B->w;
   101     if (Bmin < Amin)
   102         Amin = Bmin;
   103     result->x = Amin;
   104     if (Bmax > Amax)
   105         Amax = Bmax;
   106     result->w = Amax - Amin;
   107 
   108     /* Vertical intersection */
   109     Amin = A->y;
   110     Amax = Amin + A->h;
   111     Bmin = B->y;
   112     Bmax = Bmin + B->h;
   113     if (Bmin < Amin)
   114         Amin = Bmin;
   115     result->y = Amin;
   116     if (Bmax > Amax)
   117         Amax = Bmax;
   118     result->h = Amax - Amin;
   119 }
   120 
   121 SDL_bool
   122 SDL_EnclosePoints(const SDL_Point * points, int count, const SDL_Rect * clip,
   123                   SDL_Rect * result)
   124 {
   125     int minx = 0;
   126     int miny = 0;
   127     int maxx = 0;
   128     int maxy = 0;
   129     int x, y, i;
   130 
   131     if (count < 1) {
   132         return SDL_FALSE;
   133     }
   134 
   135     if (clip) {
   136         SDL_bool added = SDL_FALSE;
   137         int clip_minx = clip->x;
   138         int clip_miny = clip->y;
   139         int clip_maxx = clip->x+clip->w-1;
   140         int clip_maxy = clip->y+clip->h-1;
   141 
   142         for (i = 0; i < count; ++i) {
   143             x = points[i].x;
   144             y = points[i].y;
   145 
   146             if (x < clip_minx || x > clip_maxx ||
   147                 y < clip_miny || y > clip_maxy) {
   148                 continue;
   149             }
   150             if (!added) {
   151                 minx = maxx = x;
   152                 miny = maxy = y;
   153                 added = SDL_TRUE;
   154                 continue;
   155             }
   156             if (x < minx) {
   157                 minx = x;
   158             } else if (x > maxx) {
   159                 maxx = x;
   160             }
   161             if (y < miny) {
   162                 miny = y;
   163             } else if (y > maxy) {
   164                 maxy = y;
   165             }
   166         }
   167         if (!added) {
   168             return SDL_FALSE;
   169         }
   170     } else {
   171         /* No clipping, always add the first point */
   172         minx = maxx = points[0].x;
   173         miny = maxy = points[0].y;
   174 
   175         for (i = 1; i < count; ++i) {
   176             x = points[i].x;
   177             y = points[i].y;
   178 
   179             if (x < minx) {
   180                 minx = x;
   181             } else if (x > maxx) {
   182                 maxx = x;
   183             }
   184             if (y < miny) {
   185                 miny = y;
   186             } else if (y > maxy) {
   187                 maxy = y;
   188             }
   189         }
   190     }
   191 
   192     if (result) {
   193         result->x = minx;
   194         result->y = miny;
   195         result->w = (maxx-minx)+1;
   196         result->h = (maxy-miny)+1;
   197     }
   198     return SDL_TRUE;
   199 }
   200 
   201 /* Use the Cohen-Sutherland algorithm for line clipping */
   202 #define CODE_BOTTOM 1
   203 #define CODE_TOP    2
   204 #define CODE_LEFT   4
   205 #define CODE_RIGHT  8
   206 
   207 static int ComputeOutCode(const SDL_Rect * rect, int x, int y)
   208 {
   209     int code = 0;
   210     if (y < 0) {
   211         code |= CODE_TOP;
   212     } else if (y >= rect->y + rect->h) {
   213         code |= CODE_BOTTOM;
   214     }
   215     if (x < 0) {
   216         code |= CODE_LEFT;
   217     } else if (x >= rect->x + rect->w) {
   218         code |= CODE_RIGHT;
   219     }
   220     return code;
   221 }
   222 
   223 SDL_bool
   224 SDL_IntersectRectAndLine(const SDL_Rect * rect, int *X1, int *Y1, int *X2,
   225                          int *Y2)
   226 {
   227     int x = 0;
   228     int y = 0;
   229     int x1, y1;
   230     int x2, y2;
   231     int rectx1;
   232     int recty1;
   233     int rectx2;
   234     int recty2;
   235     int outcode1, outcode2;
   236 
   237     if (!rect || !X1 || !Y1 || !X2 || !Y2) {
   238         return SDL_FALSE;
   239     }
   240 
   241     x1 = *X1;
   242     y1 = *Y1;
   243     x2 = *X2;
   244     y2 = *Y2;
   245     rectx1 = rect->x;
   246     recty1 = rect->y;
   247     rectx2 = rect->x + rect->w - 1;
   248     recty2 = rect->y + rect->h - 1;
   249 
   250     /* Check to see if entire line is inside rect */
   251     if (x1 >= rectx1 && x1 <= rectx2 && x2 >= rectx1 && x2 <= rectx2 &&
   252         y1 >= recty1 && y1 <= recty2 && y2 >= recty1 && y2 <= recty2) {
   253         return SDL_TRUE;
   254     }
   255 
   256     /* Check to see if entire line is to one side of rect */
   257     if ((x1 < rectx1 && x2 < rectx1) || (x1 > rectx2 && x2 > rectx2) ||
   258         (y1 < recty1 && y2 < recty1) || (y1 > recty2 && y2 > recty2)) {
   259         return SDL_FALSE;
   260     }
   261 
   262     if (y1 == y2) {
   263         /* Horizontal line, easy to clip */
   264         if (x1 < rectx1) {
   265             *X1 = rectx1;
   266         } else if (x1 > rectx2) {
   267             *X1 = rectx2;
   268         }
   269         if (x2 < rectx1) {
   270             *X2 = rectx1;
   271         } else if (x2 > rectx2) {
   272             *X2 = rectx2;
   273         }
   274         return SDL_TRUE;
   275     }
   276 
   277     if (x1 == x2) {
   278         /* Vertical line, easy to clip */
   279         if (y1 < recty1) {
   280             *Y1 = recty1;
   281         } else if (y1 > recty2) {
   282             *Y1 = recty2;
   283         }
   284         if (y2 < recty1) {
   285             *Y2 = recty1;
   286         } else if (y2 > recty2) {
   287             *Y2 = recty2;
   288         }
   289         return SDL_TRUE;
   290     }
   291 
   292     /* More complicated Cohen-Sutherland algorithm */
   293     outcode1 = ComputeOutCode(rect, x1, y1);
   294     outcode2 = ComputeOutCode(rect, x2, y2);
   295     while (outcode1 || outcode2) {
   296         if (outcode1 & outcode2) {
   297             return SDL_FALSE;
   298         }
   299 
   300         if (outcode1) {
   301             if (outcode1 & CODE_TOP) {
   302                 y = recty1;
   303                 x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1);
   304             } else if (outcode1 & CODE_BOTTOM) {
   305                 y = recty2;
   306                 x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1);
   307             } else if (outcode1 & CODE_LEFT) {
   308                 x = rectx1;
   309                 y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
   310             } else if (outcode1 & CODE_RIGHT) {
   311                 x = rectx2;
   312                 y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
   313             }
   314             x1 = x;
   315             y1 = y;
   316             outcode1 = ComputeOutCode(rect, x, y);
   317         } else {
   318             if (outcode2 & CODE_TOP) {
   319                 y = recty1;
   320                 x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1);
   321             } else if (outcode2 & CODE_BOTTOM) {
   322                 y = recty2;
   323                 x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1);
   324             } else if (outcode2 & CODE_LEFT) {
   325                 x = rectx1;
   326                 y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
   327             } else if (outcode2 & CODE_RIGHT) {
   328                 x = rectx2;
   329                 y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
   330             }
   331             x2 = x;
   332             y2 = y;
   333             outcode2 = ComputeOutCode(rect, x, y);
   334         }
   335     }
   336     *X1 = x1;
   337     *Y1 = y1;
   338     *X2 = x2;
   339     *Y2 = y2;
   340     return SDL_TRUE;
   341 }
   342 
   343 void
   344 SDL_AddDirtyRect(SDL_DirtyRectList * list, const SDL_Rect * rect)
   345 {
   346     SDL_DirtyRect *dirty;
   347 
   348     /* FIXME: At what point is this optimization too expensive? */
   349     for (dirty = list->list; dirty; dirty = dirty->next) {
   350         if (SDL_HasIntersection(&dirty->rect, rect)) {
   351             SDL_UnionRect(&dirty->rect, rect, &dirty->rect);
   352             return;
   353         }
   354     }
   355 
   356     if (list->free) {
   357         dirty = list->free;
   358         list->free = dirty->next;
   359     } else {
   360         dirty = (SDL_DirtyRect *) SDL_malloc(sizeof(*dirty));
   361         if (!dirty) {
   362             return;
   363         }
   364     }
   365     dirty->rect = *rect;
   366     dirty->next = list->list;
   367     list->list = dirty;
   368 }
   369 
   370 void
   371 SDL_ClearDirtyRects(SDL_DirtyRectList * list)
   372 {
   373     SDL_DirtyRect *prev, *curr;
   374 
   375     /* Skip to the end of the free list */
   376     prev = NULL;
   377     for (curr = list->free; curr; curr = curr->next) {
   378         prev = curr;
   379     }
   380 
   381     /* Add the list entries to the end */
   382     if (prev) {
   383         prev->next = list->list;
   384     } else {
   385         list->free = list->list;
   386     }
   387     list->list = NULL;
   388 }
   389 
   390 void
   391 SDL_FreeDirtyRects(SDL_DirtyRectList * list)
   392 {
   393     while (list->list) {
   394         SDL_DirtyRect *elem = list->list;
   395         list->list = elem->next;
   396         SDL_free(elem);
   397     }
   398     while (list->free) {
   399         SDL_DirtyRect *elem = list->free;
   400         list->free = elem->next;
   401         SDL_free(elem);
   402     }
   403 }
   404 
   405 /* vi: set ts=4 sw=4 expandtab: */