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