src/video/SDL_rect.c
author Sam Lantinga
Wed, 09 Dec 2009 15:56:56 +0000
changeset 3536 0267b8b1595c
parent 3046 47965eacde88
child 3541 0c429a5fda8a
permissions -rw-r--r--
Added interfaces for batch drawing of points, lines and rects:
SDL_DrawPoints()
SDL_BlendPoints()
SDL_BlendLines()
SDL_DrawLines()
SDL_FillRects()
SDL_BlendRects()
SDL_RenderPoints()
SDL_RenderLines()
SDL_RenderRects()
Renamed SDL_RenderFill() to SDL_RenderRect()
     1 /*
     2     SDL - Simple DirectMedia Layer
     3     Copyright (C) 1997-2009 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, miny;
   126     int maxx, maxy;
   127     int x, y, i;
   128 
   129     if (count < 1) {
   130         return SDL_FALSE;
   131     }
   132 
   133     if (clip) {
   134         SDL_bool added = SDL_FALSE;
   135         int clip_minx = clip->x;
   136         int clip_miny = clip->y;
   137         int clip_maxx = clip->x+clip->w-1;
   138         int clip_maxy = clip->y+clip->h-1;
   139 
   140         for (i = 0; i < count; ++i) {
   141             x = points[i].x;
   142             y = points[i].y;
   143 
   144             if (x < clip_minx || x > clip_maxx ||
   145                 y < clip_miny || y > clip_maxy) {
   146                 continue;
   147             }
   148             if (!added) {
   149                 minx = maxx = x;
   150                 miny = maxy = y;
   151                 added = SDL_TRUE;
   152                 continue;
   153             }
   154             if (x < minx) {
   155                 minx = x;
   156             } else if (x > maxx) {
   157                 maxx = x;
   158             }
   159             if (y < miny) {
   160                 miny = y;
   161             } else if (y > maxy) {
   162                 maxy = y;
   163             }
   164         }
   165         if (!added) {
   166             return SDL_FALSE;
   167         }
   168     } else {
   169         /* No clipping, always add the first point */
   170         minx = maxx = points[0].x;
   171         miny = maxy = points[0].y;
   172 
   173         for (i = 1; i < count; ++i) {
   174             x = points[i].x;
   175             y = points[i].y;
   176 
   177             if (x < minx) {
   178                 minx = x;
   179             } else if (x > maxx) {
   180                 maxx = x;
   181             }
   182             if (y < miny) {
   183                 miny = y;
   184             } else if (y > maxy) {
   185                 maxy = y;
   186             }
   187         }
   188     }
   189 
   190     if (result) {
   191         result->x = minx;
   192         result->y = miny;
   193         result->w = (maxx-minx)+1;
   194         result->h = (maxy-miny)+1;
   195     }
   196     return SDL_TRUE;
   197 }
   198 
   199 SDL_bool
   200 SDL_IntersectRectAndLine(const SDL_Rect * rect, int *X1, int *Y1, int *X2,
   201                          int *Y2)
   202 {
   203     int x1, y1;
   204     int x2, y2;
   205     int rectx1;
   206     int recty1;
   207     int rectx2;
   208     int recty2;
   209 
   210     if (!rect || !X1 || !Y1 || !X2 || !Y2) {
   211         return SDL_FALSE;
   212     }
   213 
   214     x1 = *X1;
   215     y1 = *Y1;
   216     x2 = *X2;
   217     y2 = *Y2;
   218     rectx1 = rect->x;
   219     recty1 = rect->y;
   220     rectx2 = rect->x + rect->w - 1;
   221     recty2 = rect->y + rect->h - 1;
   222 
   223     /* Check to see if entire line is inside rect */
   224     if (x1 >= rectx1 && x1 <= rectx2 && x2 >= rectx1 && x2 <= rectx2 &&
   225         y1 >= recty1 && y1 <= recty2 && y2 >= recty1 && y2 <= recty2) {
   226         return SDL_TRUE;
   227     }
   228 
   229     /* Check to see if entire line is to one side of rect */
   230     if ((x1 < rectx1 && x2 < rectx1) || (x1 > rectx2 && x2 > rectx2) ||
   231         (y1 < recty1 && y2 < recty1) || (y1 > recty2 && y2 > recty2)) {
   232         return SDL_FALSE;
   233     }
   234 
   235     if (y1 == y2) {
   236         /* Horizontal line, easy to clip */
   237         if (x1 < rectx1) {
   238             *X1 = rectx1;
   239         } else if (x1 > rectx2) {
   240             *X1 = rectx2;
   241         }
   242         if (x2 < rectx1) {
   243             *X2 = rectx1;
   244         } else if (x2 > rectx2) {
   245             *X2 = rectx2;
   246         }
   247         return SDL_TRUE;
   248     }
   249 
   250     if (x1 == x2) {
   251         /* Vertical line, easy to clip */
   252         if (y1 < recty1) {
   253             *Y1 = recty1;
   254         } else if (y1 > recty2) {
   255             *Y1 = recty2;
   256         }
   257         if (y2 < recty1) {
   258             *Y2 = recty1;
   259         } else if (y2 > recty2) {
   260             *Y2 = recty2;
   261         }
   262         return SDL_TRUE;
   263     }
   264 
   265     else {
   266         /* The task of clipping a line with finite slope ratios in a fixed-
   267          * precision coordinate space is not as immediately simple as it is
   268          * with coordinates of arbitrary precision. If the ratio of slopes
   269          * between the input line segment and the result line segment is not
   270          * a whole number, you have in fact *moved* the line segment a bit,
   271          * and there can be no avoiding it without more precision
   272          */
   273         int *x_result_[] = { X1, X2, NULL }, **x_result = x_result_;
   274         int *y_result_[] = { Y1, Y2, NULL }, **y_result = y_result_;
   275         SDL_bool intersection = SDL_FALSE;
   276         double b, m, left, right, bottom, top;
   277         int xl, xh, yl, yh;
   278 
   279         /* solve mx+b line formula */
   280         m = (double) (y1 - y2) / (double) (x1 - x2);
   281         b = y2 - m * (double) x2;
   282 
   283         /* find some linear intersections */
   284         left = (m * (double) rectx1) + b;
   285         right = (m * (double) rectx2) + b;
   286         top = (recty1 - b) / m;
   287         bottom = (recty2 - b) / m;
   288 
   289         /* sort end-points' x and y components individually */
   290         if (x1 < x2) {
   291             xl = x1;
   292             xh = x2;
   293         } else {
   294             xl = x2;
   295             xh = x1;
   296         }
   297         if (y1 < y2) {
   298             yl = y1;
   299             yh = y2;
   300         } else {
   301             yl = y2;
   302             yh = y1;
   303         }
   304 
   305 #define RISING(a, b, c) (((a)<=(b))&&((b)<=(c)))
   306 
   307         /* check for a point that's entirely inside the rect */
   308         if (RISING(rectx1, x1, rectx2) && RISING(recty1, y1, recty2)) {
   309             x_result++;
   310             y_result++;
   311             intersection = SDL_TRUE;
   312         } else
   313             /* it was determined earlier that *both* end-points are not contained */
   314         if (RISING(rectx1, x2, rectx2) && RISING(recty1, y2, recty2)) {
   315             **(x_result++) = x2;
   316             **(y_result++) = y2;
   317             intersection = SDL_TRUE;
   318         }
   319 
   320         if (RISING(recty1, left, recty2) && RISING(xl, rectx1, xh)) {
   321             **(x_result++) = rectx1;
   322             **(y_result++) = (int) left;
   323             intersection = SDL_TRUE;
   324         }
   325 
   326         if (*x_result == NULL)
   327             return intersection;
   328         if (RISING(recty1, right, recty2) && RISING(xl, rectx2, xh)) {
   329             **(x_result++) = rectx2;
   330             **(y_result++) = (int) right;
   331             intersection = SDL_TRUE;
   332         }
   333 
   334         if (*x_result == NULL)
   335             return intersection;
   336         if (RISING(rectx1, top, rectx2) && RISING(yl, recty1, yh)) {
   337             **(x_result++) = (int) top;
   338             **(y_result++) = recty1;
   339             intersection = SDL_TRUE;
   340         }
   341 
   342         if (*x_result == NULL)
   343             return intersection;
   344         if (RISING(rectx1, bottom, rectx2) && RISING(yl, recty2, yh)) {
   345             **(x_result++) = (int) bottom;
   346             **(y_result++) = recty2;
   347             intersection = SDL_TRUE;
   348         }
   349 
   350         return intersection;
   351     }
   352 
   353     return SDL_FALSE;
   354 }
   355 
   356 void
   357 SDL_AddDirtyRect(SDL_DirtyRectList * list, const SDL_Rect * rect)
   358 {
   359     SDL_DirtyRect *dirty;
   360 
   361     /* FIXME: At what point is this optimization too expensive? */
   362     for (dirty = list->list; dirty; dirty = dirty->next) {
   363         if (SDL_HasIntersection(&dirty->rect, rect)) {
   364             SDL_UnionRect(&dirty->rect, rect, &dirty->rect);
   365             return;
   366         }
   367     }
   368 
   369     if (list->free) {
   370         dirty = list->free;
   371         list->free = dirty->next;
   372     } else {
   373         dirty = (SDL_DirtyRect *) SDL_malloc(sizeof(*dirty));
   374         if (!dirty) {
   375             return;
   376         }
   377     }
   378     dirty->rect = *rect;
   379     dirty->next = list->list;
   380     list->list = dirty;
   381 }
   382 
   383 void
   384 SDL_ClearDirtyRects(SDL_DirtyRectList * list)
   385 {
   386     SDL_DirtyRect *prev, *curr;
   387 
   388     /* Skip to the end of the free list */
   389     prev = NULL;
   390     for (curr = list->free; curr; curr = curr->next) {
   391         prev = curr;
   392     }
   393 
   394     /* Add the list entries to the end */
   395     if (prev) {
   396         prev->next = list->list;
   397     } else {
   398         list->free = list->list;
   399     }
   400     list->list = NULL;
   401 }
   402 
   403 void
   404 SDL_FreeDirtyRects(SDL_DirtyRectList * list)
   405 {
   406     while (list->list) {
   407         SDL_DirtyRect *elem = list->list;
   408         list->list = elem->next;
   409         SDL_free(elem);
   410     }
   411     while (list->free) {
   412         SDL_DirtyRect *elem = list->free;
   413         list->free = elem->next;
   414         SDL_free(elem);
   415     }
   416 }
   417 
   418 /* vi: set ts=4 sw=4 expandtab: */