src/video/SDL_rect.c
author Sam Lantinga <slouken@libsdl.org>
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()
slouken@1895
     1
/*
slouken@1895
     2
    SDL - Simple DirectMedia Layer
slouken@2859
     3
    Copyright (C) 1997-2009 Sam Lantinga
slouken@1895
     4
slouken@1895
     5
    This library is free software; you can redistribute it and/or
slouken@1895
     6
    modify it under the terms of the GNU Lesser General Public
slouken@1895
     7
    License as published by the Free Software Foundation; either
slouken@1895
     8
    version 2.1 of the License, or (at your option) any later version.
slouken@1895
     9
slouken@1895
    10
    This library is distributed in the hope that it will be useful,
slouken@1895
    11
    but WITHOUT ANY WARRANTY; without even the implied warranty of
slouken@1895
    12
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
slouken@1895
    13
    Lesser General Public License for more details.
slouken@1895
    14
slouken@1895
    15
    You should have received a copy of the GNU Lesser General Public
slouken@1895
    16
    License along with this library; if not, write to the Free Software
slouken@1895
    17
    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
slouken@1895
    18
slouken@1895
    19
    Sam Lantinga
slouken@1895
    20
    slouken@libsdl.org
slouken@1895
    21
*/
slouken@1895
    22
#include "SDL_config.h"
slouken@1895
    23
slouken@1895
    24
#include "SDL_video.h"
slouken@1895
    25
#include "SDL_rect_c.h"
slouken@1895
    26
slouken@1895
    27
SDL_bool
slouken@1895
    28
SDL_HasIntersection(const SDL_Rect * A, const SDL_Rect * B)
slouken@1895
    29
{
slouken@1895
    30
    int Amin, Amax, Bmin, Bmax;
slouken@1895
    31
slouken@1895
    32
    /* Horizontal intersection */
slouken@1895
    33
    Amin = A->x;
slouken@1895
    34
    Amax = Amin + A->w;
slouken@1895
    35
    Bmin = B->x;
slouken@1895
    36
    Bmax = Bmin + B->w;
slouken@1895
    37
    if (Bmin > Amin)
slouken@1895
    38
        Amin = Bmin;
slouken@1895
    39
    if (Bmax < Amax)
slouken@1895
    40
        Amax = Bmax;
slouken@1895
    41
    if (Amax <= Amin)
slouken@1895
    42
        return SDL_FALSE;
slouken@1895
    43
slouken@1895
    44
    /* Vertical intersection */
slouken@1895
    45
    Amin = A->y;
slouken@1895
    46
    Amax = Amin + A->h;
slouken@1895
    47
    Bmin = B->y;
slouken@1895
    48
    Bmax = Bmin + B->h;
slouken@1895
    49
    if (Bmin > Amin)
slouken@1895
    50
        Amin = Bmin;
slouken@1895
    51
    if (Bmax < Amax)
slouken@1895
    52
        Amax = Bmax;
slouken@1895
    53
    if (Amax <= Amin)
slouken@1895
    54
        return SDL_FALSE;
slouken@1895
    55
slouken@1895
    56
    return SDL_TRUE;
slouken@1895
    57
}
slouken@1895
    58
slouken@1895
    59
SDL_bool
slouken@1895
    60
SDL_IntersectRect(const SDL_Rect * A, const SDL_Rect * B, SDL_Rect * result)
slouken@1895
    61
{
slouken@1895
    62
    int Amin, Amax, Bmin, Bmax;
slouken@1895
    63
slouken@1895
    64
    /* Horizontal intersection */
slouken@1895
    65
    Amin = A->x;
slouken@1895
    66
    Amax = Amin + A->w;
slouken@1895
    67
    Bmin = B->x;
slouken@1895
    68
    Bmax = Bmin + B->w;
slouken@1895
    69
    if (Bmin > Amin)
slouken@1895
    70
        Amin = Bmin;
slouken@1895
    71
    result->x = Amin;
slouken@1895
    72
    if (Bmax < Amax)
slouken@1895
    73
        Amax = Bmax;
slouken@1895
    74
    result->w = Amax - Amin;
slouken@1895
    75
slouken@1895
    76
    /* Vertical intersection */
slouken@1895
    77
    Amin = A->y;
slouken@1895
    78
    Amax = Amin + A->h;
slouken@1895
    79
    Bmin = B->y;
slouken@1895
    80
    Bmax = Bmin + B->h;
slouken@1895
    81
    if (Bmin > Amin)
slouken@1895
    82
        Amin = Bmin;
slouken@1895
    83
    result->y = Amin;
slouken@1895
    84
    if (Bmax < Amax)
slouken@1895
    85
        Amax = Bmax;
slouken@1895
    86
    result->h = Amax - Amin;
slouken@1895
    87
slouken@1895
    88
    return !SDL_RectEmpty(result);
slouken@1895
    89
}
slouken@1895
    90
slouken@1895
    91
void
slouken@1895
    92
SDL_UnionRect(const SDL_Rect * A, const SDL_Rect * B, SDL_Rect * result)
slouken@1895
    93
{
slouken@1895
    94
    int Amin, Amax, Bmin, Bmax;
slouken@1895
    95
slouken@1895
    96
    /* Horizontal union */
slouken@1895
    97
    Amin = A->x;
slouken@1895
    98
    Amax = Amin + A->w;
slouken@1895
    99
    Bmin = B->x;
slouken@1895
   100
    Bmax = Bmin + B->w;
slouken@1895
   101
    if (Bmin < Amin)
slouken@1895
   102
        Amin = Bmin;
slouken@1895
   103
    result->x = Amin;
slouken@1895
   104
    if (Bmax > Amax)
slouken@1895
   105
        Amax = Bmax;
slouken@1895
   106
    result->w = Amax - Amin;
slouken@1895
   107
slouken@1895
   108
    /* Vertical intersection */
slouken@1895
   109
    Amin = A->y;
slouken@1895
   110
    Amax = Amin + A->h;
slouken@1895
   111
    Bmin = B->y;
slouken@1895
   112
    Bmax = Bmin + B->h;
slouken@1895
   113
    if (Bmin < Amin)
slouken@1895
   114
        Amin = Bmin;
slouken@1895
   115
    result->y = Amin;
slouken@1895
   116
    if (Bmax > Amax)
slouken@1895
   117
        Amax = Bmax;
slouken@1895
   118
    result->h = Amax - Amin;
slouken@1895
   119
}
slouken@1895
   120
slouken@2909
   121
SDL_bool
slouken@3536
   122
SDL_EnclosePoints(const SDL_Point * points, int count, const SDL_Rect * clip,
slouken@3536
   123
                  SDL_Rect * result)
slouken@3536
   124
{
slouken@3536
   125
    int minx, miny;
slouken@3536
   126
    int maxx, maxy;
slouken@3536
   127
    int x, y, i;
slouken@3536
   128
slouken@3536
   129
    if (count < 1) {
slouken@3536
   130
        return SDL_FALSE;
slouken@3536
   131
    }
slouken@3536
   132
slouken@3536
   133
    if (clip) {
slouken@3536
   134
        SDL_bool added = SDL_FALSE;
slouken@3536
   135
        int clip_minx = clip->x;
slouken@3536
   136
        int clip_miny = clip->y;
slouken@3536
   137
        int clip_maxx = clip->x+clip->w-1;
slouken@3536
   138
        int clip_maxy = clip->y+clip->h-1;
slouken@3536
   139
slouken@3536
   140
        for (i = 0; i < count; ++i) {
slouken@3536
   141
            x = points[i].x;
slouken@3536
   142
            y = points[i].y;
slouken@3536
   143
slouken@3536
   144
            if (x < clip_minx || x > clip_maxx ||
slouken@3536
   145
                y < clip_miny || y > clip_maxy) {
slouken@3536
   146
                continue;
slouken@3536
   147
            }
slouken@3536
   148
            if (!added) {
slouken@3536
   149
                minx = maxx = x;
slouken@3536
   150
                miny = maxy = y;
slouken@3536
   151
                added = SDL_TRUE;
slouken@3536
   152
                continue;
slouken@3536
   153
            }
slouken@3536
   154
            if (x < minx) {
slouken@3536
   155
                minx = x;
slouken@3536
   156
            } else if (x > maxx) {
slouken@3536
   157
                maxx = x;
slouken@3536
   158
            }
slouken@3536
   159
            if (y < miny) {
slouken@3536
   160
                miny = y;
slouken@3536
   161
            } else if (y > maxy) {
slouken@3536
   162
                maxy = y;
slouken@3536
   163
            }
slouken@3536
   164
        }
slouken@3536
   165
        if (!added) {
slouken@3536
   166
            return SDL_FALSE;
slouken@3536
   167
        }
slouken@3536
   168
    } else {
slouken@3536
   169
        /* No clipping, always add the first point */
slouken@3536
   170
        minx = maxx = points[0].x;
slouken@3536
   171
        miny = maxy = points[0].y;
slouken@3536
   172
slouken@3536
   173
        for (i = 1; i < count; ++i) {
slouken@3536
   174
            x = points[i].x;
slouken@3536
   175
            y = points[i].y;
slouken@3536
   176
slouken@3536
   177
            if (x < minx) {
slouken@3536
   178
                minx = x;
slouken@3536
   179
            } else if (x > maxx) {
slouken@3536
   180
                maxx = x;
slouken@3536
   181
            }
slouken@3536
   182
            if (y < miny) {
slouken@3536
   183
                miny = y;
slouken@3536
   184
            } else if (y > maxy) {
slouken@3536
   185
                maxy = y;
slouken@3536
   186
            }
slouken@3536
   187
        }
slouken@3536
   188
    }
slouken@3536
   189
slouken@3536
   190
    if (result) {
slouken@3536
   191
        result->x = minx;
slouken@3536
   192
        result->y = miny;
slouken@3536
   193
        result->w = (maxx-minx)+1;
slouken@3536
   194
        result->h = (maxy-miny)+1;
slouken@3536
   195
    }
slouken@3536
   196
    return SDL_TRUE;
slouken@3536
   197
}
slouken@3536
   198
slouken@3536
   199
SDL_bool
slouken@2920
   200
SDL_IntersectRectAndLine(const SDL_Rect * rect, int *X1, int *Y1, int *X2,
slouken@2920
   201
                         int *Y2)
slouken@2909
   202
{
slouken@2909
   203
    int x1, y1;
slouken@2909
   204
    int x2, y2;
slouken@2909
   205
    int rectx1;
slouken@2909
   206
    int recty1;
slouken@2909
   207
    int rectx2;
slouken@2909
   208
    int recty2;
slouken@2909
   209
slouken@2909
   210
    if (!rect || !X1 || !Y1 || !X2 || !Y2) {
slouken@3046
   211
        return SDL_FALSE;
slouken@2909
   212
    }
slouken@2909
   213
slouken@2909
   214
    x1 = *X1;
slouken@2909
   215
    y1 = *Y1;
slouken@2909
   216
    x2 = *X2;
slouken@2909
   217
    y2 = *Y2;
slouken@2909
   218
    rectx1 = rect->x;
slouken@2909
   219
    recty1 = rect->y;
slouken@2909
   220
    rectx2 = rect->x + rect->w - 1;
slouken@2909
   221
    recty2 = rect->y + rect->h - 1;
slouken@2909
   222
slouken@2909
   223
    /* Check to see if entire line is inside rect */
slouken@2909
   224
    if (x1 >= rectx1 && x1 <= rectx2 && x2 >= rectx1 && x2 <= rectx2 &&
slouken@2909
   225
        y1 >= recty1 && y1 <= recty2 && y2 >= recty1 && y2 <= recty2) {
slouken@2909
   226
        return SDL_TRUE;
slouken@2909
   227
    }
slouken@2909
   228
slouken@2994
   229
    /* Check to see if entire line is to one side of rect */
slouken@2909
   230
    if ((x1 < rectx1 && x2 < rectx1) || (x1 > rectx2 && x2 > rectx2) ||
slouken@3004
   231
        (y1 < recty1 && y2 < recty1) || (y1 > recty2 && y2 > recty2)) {
slouken@2909
   232
        return SDL_FALSE;
slouken@2909
   233
    }
slouken@2909
   234
slouken@2994
   235
    if (y1 == y2) {
slouken@2909
   236
        /* Horizontal line, easy to clip */
slouken@2909
   237
        if (x1 < rectx1) {
slouken@2909
   238
            *X1 = rectx1;
slouken@2909
   239
        } else if (x1 > rectx2) {
slouken@2909
   240
            *X1 = rectx2;
slouken@2909
   241
        }
slouken@2909
   242
        if (x2 < rectx1) {
slouken@2909
   243
            *X2 = rectx1;
slouken@2909
   244
        } else if (x2 > rectx2) {
slouken@2909
   245
            *X2 = rectx2;
slouken@2909
   246
        }
slouken@2909
   247
        return SDL_TRUE;
slouken@2909
   248
    }
slouken@2909
   249
slouken@2909
   250
    if (x1 == x2) {
slouken@2909
   251
        /* Vertical line, easy to clip */
slouken@2909
   252
        if (y1 < recty1) {
slouken@2909
   253
            *Y1 = recty1;
slouken@2909
   254
        } else if (y1 > recty2) {
slouken@2909
   255
            *Y1 = recty2;
slouken@2909
   256
        }
slouken@2909
   257
        if (y2 < recty1) {
slouken@2909
   258
            *Y2 = recty1;
slouken@2909
   259
        } else if (y2 > recty2) {
slouken@2909
   260
            *Y2 = recty2;
slouken@2909
   261
        }
slouken@2909
   262
        return SDL_TRUE;
slouken@2909
   263
    }
slouken@2909
   264
slouken@2997
   265
    else {
slouken@2997
   266
        /* The task of clipping a line with finite slope ratios in a fixed-
slouken@2997
   267
         * precision coordinate space is not as immediately simple as it is
slouken@2997
   268
         * with coordinates of arbitrary precision. If the ratio of slopes
slouken@2997
   269
         * between the input line segment and the result line segment is not
slouken@2997
   270
         * a whole number, you have in fact *moved* the line segment a bit,
slouken@2997
   271
         * and there can be no avoiding it without more precision
slouken@2997
   272
         */
slouken@2997
   273
        int *x_result_[] = { X1, X2, NULL }, **x_result = x_result_;
slouken@2997
   274
        int *y_result_[] = { Y1, Y2, NULL }, **y_result = y_result_;
slouken@2994
   275
        SDL_bool intersection = SDL_FALSE;
slouken@2994
   276
        double b, m, left, right, bottom, top;
slouken@2994
   277
        int xl, xh, yl, yh;
slouken@2994
   278
slouken@2994
   279
        /* solve mx+b line formula */
slouken@2997
   280
        m = (double) (y1 - y2) / (double) (x1 - x2);
slouken@2994
   281
        b = y2 - m * (double) x2;
slouken@2994
   282
slouken@2994
   283
        /* find some linear intersections */
slouken@2994
   284
        left = (m * (double) rectx1) + b;
slouken@2994
   285
        right = (m * (double) rectx2) + b;
slouken@2994
   286
        top = (recty1 - b) / m;
slouken@2994
   287
        bottom = (recty2 - b) / m;
slouken@2994
   288
slouken@2994
   289
        /* sort end-points' x and y components individually */
slouken@2994
   290
        if (x1 < x2) {
slouken@2994
   291
            xl = x1;
slouken@2994
   292
            xh = x2;
slouken@2994
   293
        } else {
slouken@2994
   294
            xl = x2;
slouken@2994
   295
            xh = x1;
slouken@2994
   296
        }
slouken@2994
   297
        if (y1 < y2) {
slouken@2994
   298
            yl = y1;
slouken@2994
   299
            yh = y2;
slouken@2994
   300
        } else {
slouken@2994
   301
            yl = y2;
slouken@2994
   302
            yh = y1;
slouken@2994
   303
        }
slouken@2994
   304
slouken@2994
   305
#define RISING(a, b, c) (((a)<=(b))&&((b)<=(c)))
slouken@2994
   306
slouken@2994
   307
        /* check for a point that's entirely inside the rect */
slouken@2994
   308
        if (RISING(rectx1, x1, rectx2) && RISING(recty1, y1, recty2)) {
slouken@2994
   309
            x_result++;
slouken@2994
   310
            y_result++;
slouken@2994
   311
            intersection = SDL_TRUE;
slouken@2997
   312
        } else
slouken@2997
   313
            /* it was determined earlier that *both* end-points are not contained */
slouken@2994
   314
        if (RISING(rectx1, x2, rectx2) && RISING(recty1, y2, recty2)) {
slouken@2994
   315
            **(x_result++) = x2;
slouken@2994
   316
            **(y_result++) = y2;
slouken@2994
   317
            intersection = SDL_TRUE;
slouken@2994
   318
        }
slouken@2994
   319
slouken@2994
   320
        if (RISING(recty1, left, recty2) && RISING(xl, rectx1, xh)) {
slouken@2994
   321
            **(x_result++) = rectx1;
slouken@2994
   322
            **(y_result++) = (int) left;
slouken@2994
   323
            intersection = SDL_TRUE;
slouken@2994
   324
        }
slouken@2994
   325
slouken@2997
   326
        if (*x_result == NULL)
slouken@2997
   327
            return intersection;
slouken@2994
   328
        if (RISING(recty1, right, recty2) && RISING(xl, rectx2, xh)) {
slouken@2994
   329
            **(x_result++) = rectx2;
slouken@2994
   330
            **(y_result++) = (int) right;
slouken@2994
   331
            intersection = SDL_TRUE;
slouken@2994
   332
        }
slouken@2994
   333
slouken@2997
   334
        if (*x_result == NULL)
slouken@2997
   335
            return intersection;
slouken@2994
   336
        if (RISING(rectx1, top, rectx2) && RISING(yl, recty1, yh)) {
slouken@2994
   337
            **(x_result++) = (int) top;
slouken@2994
   338
            **(y_result++) = recty1;
slouken@2994
   339
            intersection = SDL_TRUE;
slouken@2994
   340
        }
slouken@2994
   341
slouken@2997
   342
        if (*x_result == NULL)
slouken@2997
   343
            return intersection;
slouken@2994
   344
        if (RISING(rectx1, bottom, rectx2) && RISING(yl, recty2, yh)) {
slouken@2994
   345
            **(x_result++) = (int) bottom;
slouken@2994
   346
            **(y_result++) = recty2;
slouken@2994
   347
            intersection = SDL_TRUE;
slouken@2994
   348
        }
slouken@2994
   349
slouken@2994
   350
        return intersection;
slouken@2994
   351
    }
slouken@2994
   352
slouken@2909
   353
    return SDL_FALSE;
slouken@2909
   354
}
slouken@2909
   355
slouken@1895
   356
void
slouken@1895
   357
SDL_AddDirtyRect(SDL_DirtyRectList * list, const SDL_Rect * rect)
slouken@1895
   358
{
slouken@1895
   359
    SDL_DirtyRect *dirty;
slouken@2223
   360
slouken@2223
   361
    /* FIXME: At what point is this optimization too expensive? */
slouken@2223
   362
    for (dirty = list->list; dirty; dirty = dirty->next) {
slouken@2223
   363
        if (SDL_HasIntersection(&dirty->rect, rect)) {
slouken@2223
   364
            SDL_UnionRect(&dirty->rect, rect, &dirty->rect);
slouken@2223
   365
            return;
slouken@2223
   366
        }
slouken@2223
   367
    }
slouken@1895
   368
slouken@1895
   369
    if (list->free) {
slouken@1895
   370
        dirty = list->free;
slouken@1895
   371
        list->free = dirty->next;
slouken@1895
   372
    } else {
slouken@1895
   373
        dirty = (SDL_DirtyRect *) SDL_malloc(sizeof(*dirty));
slouken@1895
   374
        if (!dirty) {
slouken@1895
   375
            return;
slouken@1895
   376
        }
slouken@1895
   377
    }
slouken@1895
   378
    dirty->rect = *rect;
slouken@1895
   379
    dirty->next = list->list;
slouken@1895
   380
    list->list = dirty;
slouken@1895
   381
}
slouken@1895
   382
slouken@1895
   383
void
slouken@1895
   384
SDL_ClearDirtyRects(SDL_DirtyRectList * list)
slouken@1895
   385
{
slouken@2224
   386
    SDL_DirtyRect *prev, *curr;
slouken@2224
   387
slouken@2224
   388
    /* Skip to the end of the free list */
slouken@2224
   389
    prev = NULL;
slouken@2224
   390
    for (curr = list->free; curr; curr = curr->next) {
slouken@2224
   391
        prev = curr;
slouken@2224
   392
    }
slouken@2224
   393
slouken@2224
   394
    /* Add the list entries to the end */
slouken@2224
   395
    if (prev) {
slouken@2224
   396
        prev->next = list->list;
slouken@2224
   397
    } else {
slouken@2224
   398
        list->free = list->list;
slouken@2224
   399
    }
slouken@2223
   400
    list->list = NULL;
slouken@1895
   401
}
slouken@1895
   402
slouken@1895
   403
void
slouken@1895
   404
SDL_FreeDirtyRects(SDL_DirtyRectList * list)
slouken@1895
   405
{
slouken@1895
   406
    while (list->list) {
slouken@1895
   407
        SDL_DirtyRect *elem = list->list;
slouken@1895
   408
        list->list = elem->next;
slouken@1895
   409
        SDL_free(elem);
slouken@1895
   410
    }
slouken@1895
   411
    while (list->free) {
slouken@1895
   412
        SDL_DirtyRect *elem = list->free;
slouken@1895
   413
        list->free = elem->next;
slouken@1895
   414
        SDL_free(elem);
slouken@1895
   415
    }
slouken@1895
   416
}
slouken@1895
   417
slouken@1895
   418
/* vi: set ts=4 sw=4 expandtab: */