src/video/SDL_rect.c
author Sam Lantinga
Sun, 04 Jan 2009 19:33:21 +0000
changeset 2994 7563b99e9a49
parent 2920 cdb01906cb7e
child 2997 e4f025078c1c
permissions -rw-r--r--
Date: Sat, 3 Jan 2009 22:11:18 -0500
From: "Donny Viszneki"
Subject: Re: [SDL] Want to help with SDL 1.3?

>> > For example, here's a good quick project for someone from the TODO list:
>> > * Add diagonal line clipping to SDL_IntersectRectAndLine()

Just wanted to point out that the patch is available at
http://codebad.com/rect-line-ix.patch

I hereby grant Sam Lantinga an irrevocable non-exclusive distribution
license to this patch to do with as he wishes.
     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_IntersectRectAndLine(const SDL_Rect * rect, int *X1, int *Y1, int *X2,
   123                          int *Y2)
   124 {
   125     int x1, y1;
   126     int x2, y2;
   127     int rectx1;
   128     int recty1;
   129     int rectx2;
   130     int recty2;
   131 
   132     if (!rect || !X1 || !Y1 || !X2 || !Y2) {
   133         SDL_FALSE;
   134     }
   135 
   136     x1 = *X1;
   137     y1 = *Y1;
   138     x2 = *X2;
   139     y2 = *Y2;
   140     rectx1 = rect->x;
   141     recty1 = rect->y;
   142     rectx2 = rect->x + rect->w - 1;
   143     recty2 = rect->y + rect->h - 1;
   144 
   145     /* Check to see if entire line is inside rect */
   146     if (x1 >= rectx1 && x1 <= rectx2 && x2 >= rectx1 && x2 <= rectx2 &&
   147         y1 >= recty1 && y1 <= recty2 && y2 >= recty1 && y2 <= recty2) {
   148         return SDL_TRUE;
   149     }
   150 
   151     /* Check to see if entire line is to one side of rect */
   152     if ((x1 < rectx1 && x2 < rectx1) || (x1 > rectx2 && x2 > rectx2) ||
   153         (y1 < recty1 && y2 < recty2) || (y1 > recty2 && y2 > recty2)) {
   154         return SDL_FALSE;
   155     }
   156 
   157     if (y1 == y2) {
   158         /* Horizontal line, easy to clip */
   159         if (x1 < rectx1) {
   160             *X1 = rectx1;
   161         } else if (x1 > rectx2) {
   162             *X1 = rectx2;
   163         }
   164         if (x2 < rectx1) {
   165             *X2 = rectx1;
   166         } else if (x2 > rectx2) {
   167             *X2 = rectx2;
   168         }
   169         return SDL_TRUE;
   170     }
   171 
   172     if (x1 == x2) {
   173         /* Vertical line, easy to clip */
   174         if (y1 < recty1) {
   175             *Y1 = recty1;
   176         } else if (y1 > recty2) {
   177             *Y1 = recty2;
   178         }
   179         if (y2 < recty1) {
   180             *Y2 = recty1;
   181         } else if (y2 > recty2) {
   182             *Y2 = recty2;
   183         }
   184         return SDL_TRUE;
   185     }
   186 
   187     else
   188     {
   189     /* The task of clipping a line with finite slope ratios in a fixed-
   190      * precision coordinate space is not as immediately simple as it is
   191      * with coordinates of arbitrary precision. If the ratio of slopes
   192      * between the input line segment and the result line segment is not
   193      * a whole number, you have in fact *moved* the line segment a bit,
   194      * and there can be no avoiding it without more precision
   195      */
   196         int *x_result_[] = {X1, X2, NULL}, **x_result = x_result_;
   197         int *y_result_[] = {Y1, Y2, NULL}, **y_result = y_result_;
   198         SDL_bool intersection = SDL_FALSE;
   199         double b, m, left, right, bottom, top;
   200         int xl, xh, yl, yh;
   201 
   202         /* solve mx+b line formula */
   203         m = (double)(y1-y2) / (double)(x1-x2);
   204         b = y2 - m * (double) x2;
   205 
   206         /* find some linear intersections */
   207         left = (m * (double) rectx1) + b;
   208         right = (m * (double) rectx2) + b;
   209         top = (recty1 - b) / m;
   210         bottom = (recty2 - b) / m;
   211 
   212         /* sort end-points' x and y components individually */
   213         if (x1 < x2) {
   214             xl = x1;
   215             xh = x2;
   216         } else {
   217             xl = x2;
   218             xh = x1;
   219         }
   220         if (y1 < y2) {
   221             yl = y1;
   222             yh = y2;
   223         } else {
   224             yl = y2;
   225             yh = y1;
   226         }
   227 
   228 #define RISING(a, b, c) (((a)<=(b))&&((b)<=(c)))
   229 
   230         /* check for a point that's entirely inside the rect */
   231         if (RISING(rectx1, x1, rectx2) && RISING(recty1, y1, recty2)) {
   232             x_result++;
   233             y_result++;
   234             intersection = SDL_TRUE;
   235         } else /* it was determined earlier that *both* end-points are not contained */
   236 
   237         if (RISING(rectx1, x2, rectx2) && RISING(recty1, y2, recty2)) {
   238             **(x_result++) = x2;
   239             **(y_result++) = y2;
   240             intersection = SDL_TRUE;
   241         }
   242 
   243         if (RISING(recty1, left, recty2) && RISING(xl, rectx1, xh)) {
   244             **(x_result++) = rectx1;
   245             **(y_result++) = (int) left;
   246             intersection = SDL_TRUE;
   247         }
   248 
   249         if (*x_result == NULL) return intersection;
   250         if (RISING(recty1, right, recty2) && RISING(xl, rectx2, xh)) {
   251             **(x_result++) = rectx2;
   252             **(y_result++) = (int) right;
   253             intersection = SDL_TRUE;
   254         }
   255 
   256         if (*x_result == NULL) return intersection;
   257         if (RISING(rectx1, top, rectx2) && RISING(yl, recty1, yh)) {
   258             **(x_result++) = (int) top;
   259             **(y_result++) = recty1;
   260             intersection = SDL_TRUE;
   261         }
   262 
   263         if (*x_result == NULL) return intersection;
   264         if (RISING(rectx1, bottom, rectx2) && RISING(yl, recty2, yh)) {
   265             **(x_result++) = (int) bottom;
   266             **(y_result++) = recty2;
   267             intersection = SDL_TRUE;
   268         }
   269 
   270         return intersection;
   271     }
   272 
   273     return SDL_FALSE;
   274 }
   275 
   276 void
   277 SDL_AddDirtyRect(SDL_DirtyRectList * list, const SDL_Rect * rect)
   278 {
   279     SDL_DirtyRect *dirty;
   280 
   281     /* FIXME: At what point is this optimization too expensive? */
   282     for (dirty = list->list; dirty; dirty = dirty->next) {
   283         if (SDL_HasIntersection(&dirty->rect, rect)) {
   284             SDL_UnionRect(&dirty->rect, rect, &dirty->rect);
   285             return;
   286         }
   287     }
   288 
   289     if (list->free) {
   290         dirty = list->free;
   291         list->free = dirty->next;
   292     } else {
   293         dirty = (SDL_DirtyRect *) SDL_malloc(sizeof(*dirty));
   294         if (!dirty) {
   295             return;
   296         }
   297     }
   298     dirty->rect = *rect;
   299     dirty->next = list->list;
   300     list->list = dirty;
   301 }
   302 
   303 void
   304 SDL_ClearDirtyRects(SDL_DirtyRectList * list)
   305 {
   306     SDL_DirtyRect *prev, *curr;
   307 
   308     /* Skip to the end of the free list */
   309     prev = NULL;
   310     for (curr = list->free; curr; curr = curr->next) {
   311         prev = curr;
   312     }
   313 
   314     /* Add the list entries to the end */
   315     if (prev) {
   316         prev->next = list->list;
   317     } else {
   318         list->free = list->list;
   319     }
   320     list->list = NULL;
   321 }
   322 
   323 void
   324 SDL_FreeDirtyRects(SDL_DirtyRectList * list)
   325 {
   326     while (list->list) {
   327         SDL_DirtyRect *elem = list->list;
   328         list->list = elem->next;
   329         SDL_free(elem);
   330     }
   331     while (list->free) {
   332         SDL_DirtyRect *elem = list->free;
   333         list->free = elem->next;
   334         SDL_free(elem);
   335     }
   336 }
   337 
   338 /* vi: set ts=4 sw=4 expandtab: */