src/video/SDL_rect.c
author Sam Lantinga <slouken@libsdl.org>
Tue, 23 Dec 2008 02:23:18 +0000
changeset 2909 3da0bb421d83
parent 2859 99210400e8b9
child 2920 cdb01906cb7e
permissions -rw-r--r--
Added line clipping
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@2909
   122
SDL_IntersectRectAndLine(const SDL_Rect *rect, int *X1, int *Y1, int *X2, int *Y2)
slouken@2909
   123
{
slouken@2909
   124
    int x1, y1;
slouken@2909
   125
    int x2, y2;
slouken@2909
   126
    int rectx1;
slouken@2909
   127
    int recty1;
slouken@2909
   128
    int rectx2;
slouken@2909
   129
    int recty2;
slouken@2909
   130
slouken@2909
   131
    if (!rect || !X1 || !Y1 || !X2 || !Y2) {
slouken@2909
   132
        SDL_FALSE;
slouken@2909
   133
    }
slouken@2909
   134
slouken@2909
   135
    x1 = *X1;
slouken@2909
   136
    y1 = *Y1;
slouken@2909
   137
    x2 = *X2;
slouken@2909
   138
    y2 = *Y2;
slouken@2909
   139
    rectx1 = rect->x;
slouken@2909
   140
    recty1 = rect->y;
slouken@2909
   141
    rectx2 = rect->x + rect->w - 1;
slouken@2909
   142
    recty2 = rect->y + rect->h - 1;
slouken@2909
   143
slouken@2909
   144
    /* Check to see if entire line is inside rect */
slouken@2909
   145
    if (x1 >= rectx1 && x1 <= rectx2 && x2 >= rectx1 && x2 <= rectx2 &&
slouken@2909
   146
        y1 >= recty1 && y1 <= recty2 && y2 >= recty1 && y2 <= recty2) {
slouken@2909
   147
        return SDL_TRUE;
slouken@2909
   148
    }
slouken@2909
   149
slouken@2909
   150
    /* Check to see if entire line is outside rect */
slouken@2909
   151
    if ((x1 < rectx1 && x2 < rectx1) || (x1 > rectx2 && x2 > rectx2) ||
slouken@2909
   152
        (y1 < recty1 && y2 < recty2) || (y1 > recty2 && y2 > recty2)) {
slouken@2909
   153
        return SDL_FALSE;
slouken@2909
   154
    }
slouken@2909
   155
slouken@2909
   156
    if (y1 = y2) {
slouken@2909
   157
        /* Horizontal line, easy to clip */
slouken@2909
   158
        if (x1 < rectx1) {
slouken@2909
   159
            *X1 = rectx1;
slouken@2909
   160
        } else if (x1 > rectx2) {
slouken@2909
   161
            *X1 = rectx2;
slouken@2909
   162
        }
slouken@2909
   163
        if (x2 < rectx1) {
slouken@2909
   164
            *X2 = rectx1;
slouken@2909
   165
        } else if (x2 > rectx2) {
slouken@2909
   166
            *X2 = rectx2;
slouken@2909
   167
        }
slouken@2909
   168
        return SDL_TRUE;
slouken@2909
   169
    }
slouken@2909
   170
slouken@2909
   171
    if (x1 == x2) {
slouken@2909
   172
        /* Vertical line, easy to clip */
slouken@2909
   173
        if (y1 < recty1) {
slouken@2909
   174
            *Y1 = recty1;
slouken@2909
   175
        } else if (y1 > recty2) {
slouken@2909
   176
            *Y1 = recty2;
slouken@2909
   177
        }
slouken@2909
   178
        if (y2 < recty1) {
slouken@2909
   179
            *Y2 = recty1;
slouken@2909
   180
        } else if (y2 > recty2) {
slouken@2909
   181
            *Y2 = recty2;
slouken@2909
   182
        }
slouken@2909
   183
        return SDL_TRUE;
slouken@2909
   184
    }
slouken@2909
   185
slouken@2909
   186
    /* FIXME: need code to clip diagonal line to rect */
slouken@2909
   187
    return SDL_FALSE;
slouken@2909
   188
}
slouken@2909
   189
slouken@1895
   190
void
slouken@1895
   191
SDL_AddDirtyRect(SDL_DirtyRectList * list, const SDL_Rect * rect)
slouken@1895
   192
{
slouken@1895
   193
    SDL_DirtyRect *dirty;
slouken@2223
   194
slouken@2223
   195
    /* FIXME: At what point is this optimization too expensive? */
slouken@2223
   196
    for (dirty = list->list; dirty; dirty = dirty->next) {
slouken@2223
   197
        if (SDL_HasIntersection(&dirty->rect, rect)) {
slouken@2223
   198
            SDL_UnionRect(&dirty->rect, rect, &dirty->rect);
slouken@2223
   199
            return;
slouken@2223
   200
        }
slouken@2223
   201
    }
slouken@1895
   202
slouken@1895
   203
    if (list->free) {
slouken@1895
   204
        dirty = list->free;
slouken@1895
   205
        list->free = dirty->next;
slouken@1895
   206
    } else {
slouken@1895
   207
        dirty = (SDL_DirtyRect *) SDL_malloc(sizeof(*dirty));
slouken@1895
   208
        if (!dirty) {
slouken@1895
   209
            return;
slouken@1895
   210
        }
slouken@1895
   211
    }
slouken@1895
   212
    dirty->rect = *rect;
slouken@1895
   213
    dirty->next = list->list;
slouken@1895
   214
    list->list = dirty;
slouken@1895
   215
}
slouken@1895
   216
slouken@1895
   217
void
slouken@1895
   218
SDL_ClearDirtyRects(SDL_DirtyRectList * list)
slouken@1895
   219
{
slouken@2224
   220
    SDL_DirtyRect *prev, *curr;
slouken@2224
   221
slouken@2224
   222
    /* Skip to the end of the free list */
slouken@2224
   223
    prev = NULL;
slouken@2224
   224
    for (curr = list->free; curr; curr = curr->next) {
slouken@2224
   225
        prev = curr;
slouken@2224
   226
    }
slouken@2224
   227
slouken@2224
   228
    /* Add the list entries to the end */
slouken@2224
   229
    if (prev) {
slouken@2224
   230
        prev->next = list->list;
slouken@2224
   231
    } else {
slouken@2224
   232
        list->free = list->list;
slouken@2224
   233
    }
slouken@2223
   234
    list->list = NULL;
slouken@1895
   235
}
slouken@1895
   236
slouken@1895
   237
void
slouken@1895
   238
SDL_FreeDirtyRects(SDL_DirtyRectList * list)
slouken@1895
   239
{
slouken@1895
   240
    while (list->list) {
slouken@1895
   241
        SDL_DirtyRect *elem = list->list;
slouken@1895
   242
        list->list = elem->next;
slouken@1895
   243
        SDL_free(elem);
slouken@1895
   244
    }
slouken@1895
   245
    while (list->free) {
slouken@1895
   246
        SDL_DirtyRect *elem = list->free;
slouken@1895
   247
        list->free = elem->next;
slouken@1895
   248
        SDL_free(elem);
slouken@1895
   249
    }
slouken@1895
   250
}
slouken@1895
   251
slouken@1895
   252
/* vi: set ts=4 sw=4 expandtab: */