SDL_rect.c - sdl - FORK: Simple Directmedia Layer

SDL_rect.c (13119B)
      1 /*
      2   Simple DirectMedia Layer
      3   Copyright (C) 1997-2020 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_internal.h"
     22 
     23 #include "SDL_rect.h"
     24 #include "SDL_rect_c.h"
     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) {
     32         SDL_InvalidParamError("A");
     33         return SDL_FALSE;
     34     }
     35 
     36     if (!B) {
     37         SDL_InvalidParamError("B");
     38         return SDL_FALSE;
     39     }
     40 
     41     /* Special cases for empty rects */
     42     if (SDL_RectEmpty(A) || SDL_RectEmpty(B)) {
     43         return SDL_FALSE;
     44     }
     45 
     46     /* Horizontal intersection */
     47     Amin = A->x;
     48     Amax = Amin + A->w;
     49     Bmin = B->x;
     50     Bmax = Bmin + B->w;
     51     if (Bmin > Amin)
     52         Amin = Bmin;
     53     if (Bmax < Amax)
     54         Amax = Bmax;
     55     if (Amax <= Amin)
     56         return SDL_FALSE;
     57 
     58     /* Vertical intersection */
     59     Amin = A->y;
     60     Amax = Amin + A->h;
     61     Bmin = B->y;
     62     Bmax = Bmin + B->h;
     63     if (Bmin > Amin)
     64         Amin = Bmin;
     65     if (Bmax < Amax)
     66         Amax = Bmax;
     67     if (Amax <= Amin)
     68         return SDL_FALSE;
     69 
     70     return SDL_TRUE;
     71 }
     72 
     73 SDL_bool
     74 SDL_IntersectRect(const SDL_Rect * A, const SDL_Rect * B, SDL_Rect * result)
     75 {
     76     int Amin, Amax, Bmin, Bmax;
     77 
     78     if (!A) {
     79         SDL_InvalidParamError("A");
     80         return SDL_FALSE;
     81     }
     82 
     83     if (!B) {
     84         SDL_InvalidParamError("B");
     85         return SDL_FALSE;
     86     }
     87 
     88     if (!result) {
     89         SDL_InvalidParamError("result");
     90         return SDL_FALSE;
     91     }
     92 
     93     /* Special cases for empty rects */
     94     if (SDL_RectEmpty(A) || SDL_RectEmpty(B)) {
     95         result->w = 0;
     96         result->h = 0;
     97         return SDL_FALSE;
     98     }
     99 
    100     /* Horizontal intersection */
    101     Amin = A->x;
    102     Amax = Amin + A->w;
    103     Bmin = B->x;
    104     Bmax = Bmin + B->w;
    105     if (Bmin > Amin)
    106         Amin = Bmin;
    107     result->x = Amin;
    108     if (Bmax < Amax)
    109         Amax = Bmax;
    110     result->w = Amax - Amin;
    111 
    112     /* Vertical intersection */
    113     Amin = A->y;
    114     Amax = Amin + A->h;
    115     Bmin = B->y;
    116     Bmax = Bmin + B->h;
    117     if (Bmin > Amin)
    118         Amin = Bmin;
    119     result->y = Amin;
    120     if (Bmax < Amax)
    121         Amax = Bmax;
    122     result->h = Amax - Amin;
    123 
    124     return !SDL_RectEmpty(result);
    125 }
    126 
    127 void
    128 SDL_UnionRect(const SDL_Rect * A, const SDL_Rect * B, SDL_Rect * result)
    129 {
    130     int Amin, Amax, Bmin, Bmax;
    131 
    132     if (!A) {
    133         SDL_InvalidParamError("A");
    134         return;
    135     }
    136 
    137     if (!B) {
    138         SDL_InvalidParamError("B");
    139         return;
    140     }
    141 
    142     if (!result) {
    143         SDL_InvalidParamError("result");
    144         return;
    145     }
    146 
    147     /* Special cases for empty Rects */
    148     if (SDL_RectEmpty(A)) {
    149       if (SDL_RectEmpty(B)) {
    150        /* A and B empty */
    151        return;
    152       } else {
    153        /* A empty, B not empty */
    154        *result = *B;
    155        return;
    156       }
    157     } else {
    158       if (SDL_RectEmpty(B)) {
    159        /* A not empty, B empty */
    160        *result = *A;
    161        return;
    162       }
    163     }
    164 
    165     /* Horizontal union */
    166     Amin = A->x;
    167     Amax = Amin + A->w;
    168     Bmin = B->x;
    169     Bmax = Bmin + B->w;
    170     if (Bmin < Amin)
    171         Amin = Bmin;
    172     result->x = Amin;
    173     if (Bmax > Amax)
    174         Amax = Bmax;
    175     result->w = Amax - Amin;
    176 
    177     /* Vertical union */
    178     Amin = A->y;
    179     Amax = Amin + A->h;
    180     Bmin = B->y;
    181     Bmax = Bmin + B->h;
    182     if (Bmin < Amin)
    183         Amin = Bmin;
    184     result->y = Amin;
    185     if (Bmax > Amax)
    186         Amax = Bmax;
    187     result->h = Amax - Amin;
    188 }
    189 
    190 SDL_bool
    191 SDL_EnclosePoints(const SDL_Point * points, int count, const SDL_Rect * clip,
    192                   SDL_Rect * result)
    193 {
    194     int minx = 0;
    195     int miny = 0;
    196     int maxx = 0;
    197     int maxy = 0;
    198     int x, y, i;
    199 
    200     if (!points) {
    201         SDL_InvalidParamError("points");
    202         return SDL_FALSE;
    203     }
    204 
    205     if (count < 1) {
    206         SDL_InvalidParamError("count");
    207         return SDL_FALSE;
    208     }
    209 
    210     if (clip) {
    211         SDL_bool added = SDL_FALSE;
    212         const int clip_minx = clip->x;
    213         const int clip_miny = clip->y;
    214         const int clip_maxx = clip->x+clip->w-1;
    215         const int clip_maxy = clip->y+clip->h-1;
    216 
    217         /* Special case for empty rectangle */
    218         if (SDL_RectEmpty(clip)) {
    219             return SDL_FALSE;
    220         }
    221 
    222         for (i = 0; i < count; ++i) {
    223             x = points[i].x;
    224             y = points[i].y;
    225 
    226             if (x < clip_minx || x > clip_maxx ||
    227                 y < clip_miny || y > clip_maxy) {
    228                 continue;
    229             }
    230             if (!added) {
    231                 /* Special case: if no result was requested, we are done */
    232                 if (result == NULL) {
    233                     return SDL_TRUE;
    234                 }
    235 
    236                 /* First point added */
    237                 minx = maxx = x;
    238                 miny = maxy = y;
    239                 added = SDL_TRUE;
    240                 continue;
    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         if (!added) {
    254             return SDL_FALSE;
    255         }
    256     } else {
    257         /* Special case: if no result was requested, we are done */
    258         if (result == NULL) {
    259             return SDL_TRUE;
    260         }
    261 
    262         /* No clipping, always add the first point */
    263         minx = maxx = points[0].x;
    264         miny = maxy = points[0].y;
    265 
    266         for (i = 1; i < count; ++i) {
    267             x = points[i].x;
    268             y = points[i].y;
    269 
    270             if (x < minx) {
    271                 minx = x;
    272             } else if (x > maxx) {
    273                 maxx = x;
    274             }
    275             if (y < miny) {
    276                 miny = y;
    277             } else if (y > maxy) {
    278                 maxy = y;
    279             }
    280         }
    281     }
    282 
    283     if (result) {
    284         result->x = minx;
    285         result->y = miny;
    286         result->w = (maxx-minx)+1;
    287         result->h = (maxy-miny)+1;
    288     }
    289     return SDL_TRUE;
    290 }
    291 
    292 /* Use the Cohen-Sutherland algorithm for line clipping */
    293 #define CODE_BOTTOM 1
    294 #define CODE_TOP    2
    295 #define CODE_LEFT   4
    296 #define CODE_RIGHT  8
    297 
    298 static int
    299 ComputeOutCode(const SDL_Rect * rect, int x, int y)
    300 {
    301     int code = 0;
    302     if (y < rect->y) {
    303         code |= CODE_TOP;
    304     } else if (y >= rect->y + rect->h) {
    305         code |= CODE_BOTTOM;
    306     }
    307     if (x < rect->x) {
    308         code |= CODE_LEFT;
    309     } else if (x >= rect->x + rect->w) {
    310         code |= CODE_RIGHT;
    311     }
    312     return code;
    313 }
    314 
    315 SDL_bool
    316 SDL_IntersectRectAndLine(const SDL_Rect * rect, int *X1, int *Y1, int *X2,
    317                          int *Y2)
    318 {
    319     int x = 0;
    320     int y = 0;
    321     int x1, y1;
    322     int x2, y2;
    323     int rectx1;
    324     int recty1;
    325     int rectx2;
    326     int recty2;
    327     int outcode1, outcode2;
    328 
    329     if (!rect) {
    330         SDL_InvalidParamError("rect");
    331         return SDL_FALSE;
    332     }
    333 
    334     if (!X1) {
    335         SDL_InvalidParamError("X1");
    336         return SDL_FALSE;
    337     }
    338 
    339     if (!Y1) {
    340         SDL_InvalidParamError("Y1");
    341         return SDL_FALSE;
    342     }
    343 
    344     if (!X2) {
    345         SDL_InvalidParamError("X2");
    346         return SDL_FALSE;
    347     }
    348 
    349     if (!Y2) {
    350         SDL_InvalidParamError("Y2");
    351         return SDL_FALSE;
    352     }
    353 
    354     /* Special case for empty rect */
    355     if (SDL_RectEmpty(rect)) {
    356         return SDL_FALSE;
    357     }
    358 
    359     x1 = *X1;
    360     y1 = *Y1;
    361     x2 = *X2;
    362     y2 = *Y2;
    363     rectx1 = rect->x;
    364     recty1 = rect->y;
    365     rectx2 = rect->x + rect->w - 1;
    366     recty2 = rect->y + rect->h - 1;
    367 
    368     /* Check to see if entire line is inside rect */
    369     if (x1 >= rectx1 && x1 <= rectx2 && x2 >= rectx1 && x2 <= rectx2 &&
    370         y1 >= recty1 && y1 <= recty2 && y2 >= recty1 && y2 <= recty2) {
    371         return SDL_TRUE;
    372     }
    373 
    374     /* Check to see if entire line is to one side of rect */
    375     if ((x1 < rectx1 && x2 < rectx1) || (x1 > rectx2 && x2 > rectx2) ||
    376         (y1 < recty1 && y2 < recty1) || (y1 > recty2 && y2 > recty2)) {
    377         return SDL_FALSE;
    378     }
    379 
    380     if (y1 == y2) {
    381         /* Horizontal line, easy to clip */
    382         if (x1 < rectx1) {
    383             *X1 = rectx1;
    384         } else if (x1 > rectx2) {
    385             *X1 = rectx2;
    386         }
    387         if (x2 < rectx1) {
    388             *X2 = rectx1;
    389         } else if (x2 > rectx2) {
    390             *X2 = rectx2;
    391         }
    392         return SDL_TRUE;
    393     }
    394 
    395     if (x1 == x2) {
    396         /* Vertical line, easy to clip */
    397         if (y1 < recty1) {
    398             *Y1 = recty1;
    399         } else if (y1 > recty2) {
    400             *Y1 = recty2;
    401         }
    402         if (y2 < recty1) {
    403             *Y2 = recty1;
    404         } else if (y2 > recty2) {
    405             *Y2 = recty2;
    406         }
    407         return SDL_TRUE;
    408     }
    409 
    410     /* More complicated Cohen-Sutherland algorithm */
    411     outcode1 = ComputeOutCode(rect, x1, y1);
    412     outcode2 = ComputeOutCode(rect, x2, y2);
    413     while (outcode1 || outcode2) {
    414         if (outcode1 & outcode2) {
    415             return SDL_FALSE;
    416         }
    417 
    418         if (outcode1) {
    419             if (outcode1 & CODE_TOP) {
    420                 y = recty1;
    421                 x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1);
    422             } else if (outcode1 & CODE_BOTTOM) {
    423                 y = recty2;
    424                 x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1);
    425             } else if (outcode1 & CODE_LEFT) {
    426                 x = rectx1;
    427                 y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
    428             } else if (outcode1 & CODE_RIGHT) {
    429                 x = rectx2;
    430                 y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
    431             }
    432             x1 = x;
    433             y1 = y;
    434             outcode1 = ComputeOutCode(rect, x, y);
    435         } else {
    436             if (outcode2 & CODE_TOP) {
    437                 y = recty1;
    438                 x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1);
    439             } else if (outcode2 & CODE_BOTTOM) {
    440                 y = recty2;
    441                 x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1);
    442             } else if (outcode2 & CODE_LEFT) {
    443                 /* If this assertion ever fires, here's the static analysis that warned about it:
    444                    http://buildbot.libsdl.org/sdl-static-analysis/sdl-macosx-static-analysis/sdl-macosx-static-analysis-1101/report-b0d01a.html#EndPath */
    445                 SDL_assert(x2 != x1);  /* if equal: division by zero. */
    446                 x = rectx1;
    447                 y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
    448             } else if (outcode2 & CODE_RIGHT) {
    449                 /* If this assertion ever fires, here's the static analysis that warned about it:
    450                    http://buildbot.libsdl.org/sdl-static-analysis/sdl-macosx-static-analysis/sdl-macosx-static-analysis-1101/report-39b114.html#EndPath */
    451                 SDL_assert(x2 != x1);  /* if equal: division by zero. */
    452                 x = rectx2;
    453                 y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
    454             }
    455             x2 = x;
    456             y2 = y;
    457             outcode2 = ComputeOutCode(rect, x, y);
    458         }
    459     }
    460     *X1 = x1;
    461     *Y1 = y1;
    462     *X2 = x2;
    463     *Y2 = y2;
    464     return SDL_TRUE;
    465 }
    466 
    467 SDL_bool
    468 SDL_GetSpanEnclosingRect(int width, int height,
    469                          int numrects, const SDL_Rect * rects, SDL_Rect *span)
    470 {
    471     int i;
    472     int span_y1, span_y2;
    473     int rect_y1, rect_y2;
    474 
    475     if (width < 1) {
    476         SDL_InvalidParamError("width");
    477         return SDL_FALSE;
    478     }
    479 
    480     if (height < 1) {
    481         SDL_InvalidParamError("height");
    482         return SDL_FALSE;
    483     }
    484 
    485     if (!rects) {
    486         SDL_InvalidParamError("rects");
    487         return SDL_FALSE;
    488     }
    489 
    490     if (!span) {
    491         SDL_InvalidParamError("span");
    492         return SDL_FALSE;
    493     }
    494 
    495     if (numrects < 1) {
    496         SDL_InvalidParamError("numrects");
    497         return SDL_FALSE;
    498     }
    499 
    500     /* Initialize to empty rect */
    501     span_y1 = height;
    502     span_y2 = 0;
    503 
    504     for (i = 0; i < numrects; ++i) {
    505         rect_y1 = rects[i].y;
    506         rect_y2 = rect_y1 + rects[i].h;
    507 
    508         /* Clip out of bounds rectangles, and expand span rect */
    509         if (rect_y1 < 0) {
    510             span_y1 = 0;
    511         } else if (rect_y1 < span_y1) {
    512             span_y1 = rect_y1;
    513         }
    514         if (rect_y2 > height) {
    515             span_y2 = height;
    516         } else if (rect_y2 > span_y2) {
    517             span_y2 = rect_y2;
    518         }
    519     }
    520     if (span_y2 > span_y1) {
    521         span->x = 0;
    522         span->y = span_y1;
    523         span->w = width;
    524         span->h = (span_y2 - span_y1);
    525         return SDL_TRUE;
    526     }
    527     return SDL_FALSE;
    528 }
    529 
    530 /* vi: set ts=4 sw=4 expandtab: */
	sdl FORK: Simple Directmedia Layer
	git clone https://git.neptards.moe/neptards/sdl.git
	Log \| Files \| Refs