src/video/SDL_rect.c
author Andreas Schiffler <aschiffler@ferzkopp.net>
Sun, 04 Sep 2011 20:34:48 -0700
changeset 5869 065c76282d68
parent 5535 96594ac5fd1a
child 5902 d3d839b15c2f
permissions -rw-r--r--
Added input parameter validation to some SDL_rect functions
slouken@1895
     1
/*
slouken@5535
     2
  Simple DirectMedia Layer
slouken@5535
     3
  Copyright (C) 1997-2011 Sam Lantinga <slouken@libsdl.org>
slouken@1895
     4
slouken@5535
     5
  This software is provided 'as-is', without any express or implied
slouken@5535
     6
  warranty.  In no event will the authors be held liable for any damages
slouken@5535
     7
  arising from the use of this software.
slouken@1895
     8
slouken@5535
     9
  Permission is granted to anyone to use this software for any purpose,
slouken@5535
    10
  including commercial applications, and to alter it and redistribute it
slouken@5535
    11
  freely, subject to the following restrictions:
slouken@1895
    12
slouken@5535
    13
  1. The origin of this software must not be misrepresented; you must not
slouken@5535
    14
     claim that you wrote the original software. If you use this software
slouken@5535
    15
     in a product, an acknowledgment in the product documentation would be
slouken@5535
    16
     appreciated but is not required.
slouken@5535
    17
  2. Altered source versions must be plainly marked as such, and must not be
slouken@5535
    18
     misrepresented as being the original software.
slouken@5535
    19
  3. This notice may not be removed or altered from any source distribution.
slouken@1895
    20
*/
slouken@1895
    21
#include "SDL_config.h"
slouken@1895
    22
slouken@5154
    23
#include "SDL_rect.h"
slouken@1895
    24
slouken@5294
    25
slouken@1895
    26
SDL_bool
slouken@1895
    27
SDL_HasIntersection(const SDL_Rect * A, const SDL_Rect * B)
slouken@1895
    28
{
slouken@1895
    29
    int Amin, Amax, Bmin, Bmax;
slouken@1895
    30
aschiffler@5869
    31
    if (!A || !B) {
aschiffler@5869
    32
        // TODO error message
aschiffler@5869
    33
        return SDL_FALSE;
aschiffler@5869
    34
    }
aschiffler@5869
    35
slouken@1895
    36
    /* Horizontal intersection */
slouken@1895
    37
    Amin = A->x;
slouken@1895
    38
    Amax = Amin + A->w;
slouken@1895
    39
    Bmin = B->x;
slouken@1895
    40
    Bmax = Bmin + B->w;
slouken@1895
    41
    if (Bmin > Amin)
slouken@1895
    42
        Amin = Bmin;
slouken@1895
    43
    if (Bmax < Amax)
slouken@1895
    44
        Amax = Bmax;
slouken@1895
    45
    if (Amax <= Amin)
slouken@1895
    46
        return SDL_FALSE;
slouken@1895
    47
slouken@1895
    48
    /* Vertical intersection */
slouken@1895
    49
    Amin = A->y;
slouken@1895
    50
    Amax = Amin + A->h;
slouken@1895
    51
    Bmin = B->y;
slouken@1895
    52
    Bmax = Bmin + B->h;
slouken@1895
    53
    if (Bmin > Amin)
slouken@1895
    54
        Amin = Bmin;
slouken@1895
    55
    if (Bmax < Amax)
slouken@1895
    56
        Amax = Bmax;
slouken@1895
    57
    if (Amax <= Amin)
slouken@1895
    58
        return SDL_FALSE;
slouken@1895
    59
slouken@1895
    60
    return SDL_TRUE;
slouken@1895
    61
}
slouken@1895
    62
slouken@1895
    63
SDL_bool
slouken@1895
    64
SDL_IntersectRect(const SDL_Rect * A, const SDL_Rect * B, SDL_Rect * result)
slouken@1895
    65
{
slouken@1895
    66
    int Amin, Amax, Bmin, Bmax;
slouken@1895
    67
aschiffler@5869
    68
    if (!A || !B || !result) {
aschiffler@5869
    69
        // TODO error message
aschiffler@5869
    70
        return SDL_FALSE;
aschiffler@5869
    71
    }
aschiffler@5869
    72
slouken@1895
    73
    /* Horizontal intersection */
slouken@1895
    74
    Amin = A->x;
slouken@1895
    75
    Amax = Amin + A->w;
slouken@1895
    76
    Bmin = B->x;
slouken@1895
    77
    Bmax = Bmin + B->w;
slouken@1895
    78
    if (Bmin > Amin)
slouken@1895
    79
        Amin = Bmin;
slouken@1895
    80
    result->x = Amin;
slouken@1895
    81
    if (Bmax < Amax)
slouken@1895
    82
        Amax = Bmax;
slouken@1895
    83
    result->w = Amax - Amin;
slouken@1895
    84
slouken@1895
    85
    /* Vertical intersection */
slouken@1895
    86
    Amin = A->y;
slouken@1895
    87
    Amax = Amin + A->h;
slouken@1895
    88
    Bmin = B->y;
slouken@1895
    89
    Bmax = Bmin + B->h;
slouken@1895
    90
    if (Bmin > Amin)
slouken@1895
    91
        Amin = Bmin;
slouken@1895
    92
    result->y = Amin;
slouken@1895
    93
    if (Bmax < Amax)
slouken@1895
    94
        Amax = Bmax;
slouken@1895
    95
    result->h = Amax - Amin;
slouken@1895
    96
slouken@1895
    97
    return !SDL_RectEmpty(result);
slouken@1895
    98
}
slouken@1895
    99
slouken@1895
   100
void
slouken@1895
   101
SDL_UnionRect(const SDL_Rect * A, const SDL_Rect * B, SDL_Rect * result)
slouken@1895
   102
{
slouken@1895
   103
    int Amin, Amax, Bmin, Bmax;
slouken@1895
   104
aschiffler@5869
   105
    if (!A || !B || !result) {
aschiffler@5869
   106
        return;
aschiffler@5869
   107
    }
aschiffler@5869
   108
slouken@1895
   109
    /* Horizontal union */
slouken@1895
   110
    Amin = A->x;
slouken@1895
   111
    Amax = Amin + A->w;
slouken@1895
   112
    Bmin = B->x;
slouken@1895
   113
    Bmax = Bmin + B->w;
slouken@1895
   114
    if (Bmin < Amin)
slouken@1895
   115
        Amin = Bmin;
slouken@1895
   116
    result->x = Amin;
slouken@1895
   117
    if (Bmax > Amax)
slouken@1895
   118
        Amax = Bmax;
slouken@1895
   119
    result->w = Amax - Amin;
slouken@1895
   120
slouken@1895
   121
    /* Vertical intersection */
slouken@1895
   122
    Amin = A->y;
slouken@1895
   123
    Amax = Amin + A->h;
slouken@1895
   124
    Bmin = B->y;
slouken@1895
   125
    Bmax = Bmin + B->h;
slouken@1895
   126
    if (Bmin < Amin)
slouken@1895
   127
        Amin = Bmin;
slouken@1895
   128
    result->y = Amin;
slouken@1895
   129
    if (Bmax > Amax)
slouken@1895
   130
        Amax = Bmax;
slouken@1895
   131
    result->h = Amax - Amin;
slouken@1895
   132
}
slouken@1895
   133
slouken@2909
   134
SDL_bool
slouken@3536
   135
SDL_EnclosePoints(const SDL_Point * points, int count, const SDL_Rect * clip,
slouken@3536
   136
                  SDL_Rect * result)
slouken@3536
   137
{
slouken@4456
   138
    int minx = 0;
slouken@4456
   139
    int miny = 0;
slouken@4456
   140
    int maxx = 0;
slouken@4456
   141
    int maxy = 0;
slouken@3536
   142
    int x, y, i;
slouken@3536
   143
aschiffler@5869
   144
    if (!points || !clip) {
aschiffler@5869
   145
        // TODO error message
aschiffler@5869
   146
        return SDL_FALSE;
aschiffler@5869
   147
    }
aschiffler@5869
   148
slouken@3536
   149
    if (count < 1) {
aschiffler@5869
   150
        // TODO error message
slouken@3536
   151
        return SDL_FALSE;
slouken@3536
   152
    }
slouken@3536
   153
slouken@3536
   154
    if (clip) {
slouken@3536
   155
        SDL_bool added = SDL_FALSE;
slouken@3536
   156
        int clip_minx = clip->x;
slouken@3536
   157
        int clip_miny = clip->y;
slouken@3536
   158
        int clip_maxx = clip->x+clip->w-1;
slouken@3536
   159
        int clip_maxy = clip->y+clip->h-1;
slouken@3536
   160
slouken@3536
   161
        for (i = 0; i < count; ++i) {
slouken@3536
   162
            x = points[i].x;
slouken@3536
   163
            y = points[i].y;
slouken@3536
   164
slouken@3536
   165
            if (x < clip_minx || x > clip_maxx ||
slouken@3536
   166
                y < clip_miny || y > clip_maxy) {
slouken@3536
   167
                continue;
slouken@3536
   168
            }
slouken@3536
   169
            if (!added) {
slouken@3536
   170
                minx = maxx = x;
slouken@3536
   171
                miny = maxy = y;
slouken@3536
   172
                added = SDL_TRUE;
slouken@3536
   173
                continue;
slouken@3536
   174
            }
slouken@3536
   175
            if (x < minx) {
slouken@3536
   176
                minx = x;
slouken@3536
   177
            } else if (x > maxx) {
slouken@3536
   178
                maxx = x;
slouken@3536
   179
            }
slouken@3536
   180
            if (y < miny) {
slouken@3536
   181
                miny = y;
slouken@3536
   182
            } else if (y > maxy) {
slouken@3536
   183
                maxy = y;
slouken@3536
   184
            }
slouken@3536
   185
        }
slouken@3536
   186
        if (!added) {
slouken@3536
   187
            return SDL_FALSE;
slouken@3536
   188
        }
slouken@3536
   189
    } else {
slouken@3536
   190
        /* No clipping, always add the first point */
slouken@3536
   191
        minx = maxx = points[0].x;
slouken@3536
   192
        miny = maxy = points[0].y;
slouken@3536
   193
slouken@3536
   194
        for (i = 1; i < count; ++i) {
slouken@3536
   195
            x = points[i].x;
slouken@3536
   196
            y = points[i].y;
slouken@3536
   197
slouken@3536
   198
            if (x < minx) {
slouken@3536
   199
                minx = x;
slouken@3536
   200
            } else if (x > maxx) {
slouken@3536
   201
                maxx = x;
slouken@3536
   202
            }
slouken@3536
   203
            if (y < miny) {
slouken@3536
   204
                miny = y;
slouken@3536
   205
            } else if (y > maxy) {
slouken@3536
   206
                maxy = y;
slouken@3536
   207
            }
slouken@3536
   208
        }
slouken@3536
   209
    }
slouken@3536
   210
slouken@3536
   211
    if (result) {
slouken@3536
   212
        result->x = minx;
slouken@3536
   213
        result->y = miny;
slouken@3536
   214
        result->w = (maxx-minx)+1;
slouken@3536
   215
        result->h = (maxy-miny)+1;
slouken@3536
   216
    }
slouken@3536
   217
    return SDL_TRUE;
slouken@3536
   218
}
slouken@3536
   219
slouken@3541
   220
/* Use the Cohen-Sutherland algorithm for line clipping */
slouken@3541
   221
#define CODE_BOTTOM 1
slouken@3541
   222
#define CODE_TOP    2
slouken@3541
   223
#define CODE_LEFT   4
slouken@3541
   224
#define CODE_RIGHT  8
slouken@3541
   225
slouken@3541
   226
static int ComputeOutCode(const SDL_Rect * rect, int x, int y)
slouken@3541
   227
{
slouken@3541
   228
    int code = 0;
slouken@3541
   229
    if (y < 0) {
slouken@3541
   230
        code |= CODE_TOP;
slouken@3541
   231
    } else if (y >= rect->y + rect->h) {
slouken@3541
   232
        code |= CODE_BOTTOM;
slouken@3541
   233
    }
slouken@3541
   234
    if (x < 0) {
slouken@3541
   235
        code |= CODE_LEFT;
slouken@3541
   236
    } else if (x >= rect->x + rect->w) {
slouken@3541
   237
        code |= CODE_RIGHT;
slouken@3541
   238
    }
slouken@3541
   239
    return code;
slouken@3541
   240
}
slouken@3541
   241
slouken@3536
   242
SDL_bool
slouken@2920
   243
SDL_IntersectRectAndLine(const SDL_Rect * rect, int *X1, int *Y1, int *X2,
slouken@2920
   244
                         int *Y2)
slouken@2909
   245
{
slouken@4456
   246
    int x = 0;
slouken@4456
   247
    int y = 0;
slouken@2909
   248
    int x1, y1;
slouken@2909
   249
    int x2, y2;
slouken@2909
   250
    int rectx1;
slouken@2909
   251
    int recty1;
slouken@2909
   252
    int rectx2;
slouken@2909
   253
    int recty2;
slouken@3541
   254
    int outcode1, outcode2;
slouken@2909
   255
slouken@2909
   256
    if (!rect || !X1 || !Y1 || !X2 || !Y2) {
aschiffler@5869
   257
        // TODO error message
slouken@3046
   258
        return SDL_FALSE;
slouken@2909
   259
    }
slouken@2909
   260
slouken@2909
   261
    x1 = *X1;
slouken@2909
   262
    y1 = *Y1;
slouken@2909
   263
    x2 = *X2;
slouken@2909
   264
    y2 = *Y2;
slouken@2909
   265
    rectx1 = rect->x;
slouken@2909
   266
    recty1 = rect->y;
slouken@2909
   267
    rectx2 = rect->x + rect->w - 1;
slouken@2909
   268
    recty2 = rect->y + rect->h - 1;
slouken@2909
   269
slouken@2909
   270
    /* Check to see if entire line is inside rect */
slouken@2909
   271
    if (x1 >= rectx1 && x1 <= rectx2 && x2 >= rectx1 && x2 <= rectx2 &&
slouken@2909
   272
        y1 >= recty1 && y1 <= recty2 && y2 >= recty1 && y2 <= recty2) {
slouken@2909
   273
        return SDL_TRUE;
slouken@2909
   274
    }
slouken@2909
   275
slouken@2994
   276
    /* Check to see if entire line is to one side of rect */
slouken@2909
   277
    if ((x1 < rectx1 && x2 < rectx1) || (x1 > rectx2 && x2 > rectx2) ||
slouken@3004
   278
        (y1 < recty1 && y2 < recty1) || (y1 > recty2 && y2 > recty2)) {
slouken@2909
   279
        return SDL_FALSE;
slouken@2909
   280
    }
slouken@2909
   281
slouken@2994
   282
    if (y1 == y2) {
slouken@2909
   283
        /* Horizontal line, easy to clip */
slouken@2909
   284
        if (x1 < rectx1) {
slouken@2909
   285
            *X1 = rectx1;
slouken@2909
   286
        } else if (x1 > rectx2) {
slouken@2909
   287
            *X1 = rectx2;
slouken@2909
   288
        }
slouken@2909
   289
        if (x2 < rectx1) {
slouken@2909
   290
            *X2 = rectx1;
slouken@2909
   291
        } else if (x2 > rectx2) {
slouken@2909
   292
            *X2 = rectx2;
slouken@2909
   293
        }
slouken@2909
   294
        return SDL_TRUE;
slouken@2909
   295
    }
slouken@2909
   296
slouken@2909
   297
    if (x1 == x2) {
slouken@2909
   298
        /* Vertical line, easy to clip */
slouken@2909
   299
        if (y1 < recty1) {
slouken@2909
   300
            *Y1 = recty1;
slouken@2909
   301
        } else if (y1 > recty2) {
slouken@2909
   302
            *Y1 = recty2;
slouken@2909
   303
        }
slouken@2909
   304
        if (y2 < recty1) {
slouken@2909
   305
            *Y2 = recty1;
slouken@2909
   306
        } else if (y2 > recty2) {
slouken@2909
   307
            *Y2 = recty2;
slouken@2909
   308
        }
slouken@2909
   309
        return SDL_TRUE;
slouken@2909
   310
    }
slouken@2909
   311
slouken@3541
   312
    /* More complicated Cohen-Sutherland algorithm */
slouken@3541
   313
    outcode1 = ComputeOutCode(rect, x1, y1);
slouken@3541
   314
    outcode2 = ComputeOutCode(rect, x2, y2);
slouken@3541
   315
    while (outcode1 || outcode2) {
slouken@3541
   316
        if (outcode1 & outcode2) {
slouken@3541
   317
            return SDL_FALSE;
slouken@2994
   318
        }
slouken@2994
   319
slouken@3541
   320
        if (outcode1) {
slouken@3541
   321
            if (outcode1 & CODE_TOP) {
slouken@3541
   322
                y = recty1;
slouken@3541
   323
                x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1);
slouken@3541
   324
            } else if (outcode1 & CODE_BOTTOM) {
slouken@3541
   325
                y = recty2;
slouken@3541
   326
                x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1);
slouken@3541
   327
            } else if (outcode1 & CODE_LEFT) {
slouken@3541
   328
                x = rectx1;
slouken@3541
   329
                y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
slouken@3541
   330
            } else if (outcode1 & CODE_RIGHT) {
slouken@3541
   331
                x = rectx2;
slouken@3541
   332
                y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
slouken@3541
   333
            }
slouken@3541
   334
            x1 = x;
slouken@3541
   335
            y1 = y;
slouken@3541
   336
            outcode1 = ComputeOutCode(rect, x, y);
slouken@3542
   337
        } else {
slouken@3541
   338
            if (outcode2 & CODE_TOP) {
slouken@3541
   339
                y = recty1;
slouken@3541
   340
                x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1);
slouken@3541
   341
            } else if (outcode2 & CODE_BOTTOM) {
slouken@3541
   342
                y = recty2;
slouken@3541
   343
                x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1);
slouken@3541
   344
            } else if (outcode2 & CODE_LEFT) {
slouken@3541
   345
                x = rectx1;
slouken@3541
   346
                y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
slouken@3541
   347
            } else if (outcode2 & CODE_RIGHT) {
slouken@3541
   348
                x = rectx2;
slouken@3541
   349
                y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
slouken@3541
   350
            }
slouken@3541
   351
            x2 = x;
slouken@3541
   352
            y2 = y;
slouken@3541
   353
            outcode2 = ComputeOutCode(rect, x, y);
slouken@2994
   354
        }
slouken@2994
   355
    }
slouken@3541
   356
    *X1 = x1;
slouken@3541
   357
    *Y1 = y1;
slouken@3541
   358
    *X2 = x2;
slouken@3541
   359
    *Y2 = y2;
slouken@3541
   360
    return SDL_TRUE;
slouken@2909
   361
}
slouken@2909
   362
slouken@5294
   363
SDL_bool
slouken@5294
   364
SDL_GetSpanEnclosingRect(int width, int height,
slouken@5294
   365
                         int numrects, SDL_Rect * rects, SDL_Rect *span)
slouken@5294
   366
{
slouken@5294
   367
    int i;
slouken@5294
   368
    int span_y1, span_y2;
slouken@5294
   369
    int rect_y1, rect_y2;
slouken@5294
   370
aschiffler@5869
   371
    if (width < 1 || height < 1) {
aschiffler@5869
   372
        // TODO error message
aschiffler@5869
   373
        return SDL_FALSE;
aschiffler@5869
   374
    }
aschiffler@5869
   375
aschiffler@5869
   376
    if (!rects || !span) {
aschiffler@5869
   377
        // TODO error message
aschiffler@5869
   378
        return SDL_FALSE;
aschiffler@5869
   379
    }
aschiffler@5869
   380
aschiffler@5869
   381
    if (numrects < 1) {
aschiffler@5869
   382
        // TODO error message
aschiffler@5869
   383
        return SDL_FALSE;
aschiffler@5869
   384
    }
aschiffler@5869
   385
slouken@5294
   386
    /* Initialize to empty rect */
slouken@5294
   387
    span_y1 = height;
slouken@5294
   388
    span_y2 = 0;
slouken@5294
   389
slouken@5294
   390
    for (i = 0; i < numrects; ++i) {
slouken@5294
   391
        rect_y1 = rects[i].y;
slouken@5294
   392
        rect_y2 = rect_y1 + rects[i].h;
slouken@5294
   393
slouken@5294
   394
        /* Clip out of bounds rectangles, and expand span rect */
slouken@5294
   395
        if (rect_y1 < 0) {
slouken@5294
   396
            span_y1 = 0;
slouken@5294
   397
        } else if (rect_y1 < span_y1) {
slouken@5294
   398
            span_y1 = rect_y1;
slouken@5294
   399
        }
slouken@5294
   400
        if (rect_y2 > height) {
slouken@5294
   401
            span_y2 = height;
slouken@5294
   402
        } else if (rect_y2 > span_y2) {
slouken@5294
   403
            span_y2 = rect_y2;
slouken@5294
   404
        }
slouken@5294
   405
    }
slouken@5294
   406
    if (span_y2 > span_y1) {
slouken@5294
   407
        span->x = 0;
slouken@5294
   408
        span->y = span_y1;
slouken@5294
   409
        span->w = width;
slouken@5294
   410
        span->h = (span_y2 - span_y1);
slouken@5294
   411
        return SDL_TRUE;
slouken@5294
   412
    }
slouken@5294
   413
    return SDL_FALSE;
slouken@5294
   414
}
slouken@5294
   415
slouken@1895
   416
/* vi: set ts=4 sw=4 expandtab: */