From 6efae250dfdc2635a0b3c7d9afd64671f2a916a5 Mon Sep 17 00:00:00 2001
From: Sam Lantinga <slouken@libsdl.org>
Date: Sun, 4 Jan 2009 19:33:21 +0000
Subject: [PATCH] Date: Sat, 3 Jan 2009 22:11:18 -0500 From: "Donny Viszneki"
 Subject: Re: [SDL] Want to help with SDL 1.3?

>> > For example, here's a good quick project for someone from the TODO list:
>> > * Add diagonal line clipping to SDL_IntersectRectAndLine()

Just wanted to point out that the patch is available at
http://codebad.com/rect-line-ix.patch

I hereby grant Sam Lantinga an irrevocable non-exclusive distribution
license to this patch to do with as he wishes.
---
 src/video/SDL_rect.c     |  91 ++++++++++-
 test/Makefile.in         |   5 +-
 test/testintersections.c | 342 +++++++++++++++++++++++++++++++++++++++
 3 files changed, 434 insertions(+), 4 deletions(-)
 create mode 100644 test/testintersections.c

diff --git a/src/video/SDL_rect.c b/src/video/SDL_rect.c
index 26c4deee5..17fd80bc5 100644
--- a/src/video/SDL_rect.c
+++ b/src/video/SDL_rect.c
@@ -148,13 +148,13 @@ SDL_IntersectRectAndLine(const SDL_Rect * rect, int *X1, int *Y1, int *X2,
         return SDL_TRUE;
     }
 
-    /* Check to see if entire line is outside rect */
+    /* Check to see if entire line is to one side of rect */
     if ((x1 < rectx1 && x2 < rectx1) || (x1 > rectx2 && x2 > rectx2) ||
         (y1 < recty1 && y2 < recty2) || (y1 > recty2 && y2 > recty2)) {
         return SDL_FALSE;
     }
 
-    if (y1 = y2) {
+    if (y1 == y2) {
         /* Horizontal line, easy to clip */
         if (x1 < rectx1) {
             *X1 = rectx1;
@@ -184,7 +184,92 @@ SDL_IntersectRectAndLine(const SDL_Rect * rect, int *X1, int *Y1, int *X2,
         return SDL_TRUE;
     }
 
-    /* FIXME: need code to clip diagonal line to rect */
+    else
+    {
+    /* The task of clipping a line with finite slope ratios in a fixed-
+     * precision coordinate space is not as immediately simple as it is
+     * with coordinates of arbitrary precision. If the ratio of slopes
+     * between the input line segment and the result line segment is not
+     * a whole number, you have in fact *moved* the line segment a bit,
+     * and there can be no avoiding it without more precision
+     */
+        int *x_result_[] = {X1, X2, NULL}, **x_result = x_result_;
+        int *y_result_[] = {Y1, Y2, NULL}, **y_result = y_result_;
+        SDL_bool intersection = SDL_FALSE;
+        double b, m, left, right, bottom, top;
+        int xl, xh, yl, yh;
+
+        /* solve mx+b line formula */
+        m = (double)(y1-y2) / (double)(x1-x2);
+        b = y2 - m * (double) x2;
+
+        /* find some linear intersections */
+        left = (m * (double) rectx1) + b;
+        right = (m * (double) rectx2) + b;
+        top = (recty1 - b) / m;
+        bottom = (recty2 - b) / m;
+
+        /* sort end-points' x and y components individually */
+        if (x1 < x2) {
+            xl = x1;
+            xh = x2;
+        } else {
+            xl = x2;
+            xh = x1;
+        }
+        if (y1 < y2) {
+            yl = y1;
+            yh = y2;
+        } else {
+            yl = y2;
+            yh = y1;
+        }
+
+#define RISING(a, b, c) (((a)<=(b))&&((b)<=(c)))
+
+        /* check for a point that's entirely inside the rect */
+        if (RISING(rectx1, x1, rectx2) && RISING(recty1, y1, recty2)) {
+            x_result++;
+            y_result++;
+            intersection = SDL_TRUE;
+        } else /* it was determined earlier that *both* end-points are not contained */
+
+        if (RISING(rectx1, x2, rectx2) && RISING(recty1, y2, recty2)) {
+            **(x_result++) = x2;
+            **(y_result++) = y2;
+            intersection = SDL_TRUE;
+        }
+
+        if (RISING(recty1, left, recty2) && RISING(xl, rectx1, xh)) {
+            **(x_result++) = rectx1;
+            **(y_result++) = (int) left;
+            intersection = SDL_TRUE;
+        }
+
+        if (*x_result == NULL) return intersection;
+        if (RISING(recty1, right, recty2) && RISING(xl, rectx2, xh)) {
+            **(x_result++) = rectx2;
+            **(y_result++) = (int) right;
+            intersection = SDL_TRUE;
+        }
+
+        if (*x_result == NULL) return intersection;
+        if (RISING(rectx1, top, rectx2) && RISING(yl, recty1, yh)) {
+            **(x_result++) = (int) top;
+            **(y_result++) = recty1;
+            intersection = SDL_TRUE;
+        }
+
+        if (*x_result == NULL) return intersection;
+        if (RISING(rectx1, bottom, rectx2) && RISING(yl, recty2, yh)) {
+            **(x_result++) = (int) bottom;
+            **(y_result++) = recty2;
+            intersection = SDL_TRUE;
+        }
+
+        return intersection;
+    }
+
     return SDL_FALSE;
 }
 
diff --git a/test/Makefile.in b/test/Makefile.in
index 7ba82fb8c..15bdb0520 100644
--- a/test/Makefile.in
+++ b/test/Makefile.in
@@ -7,7 +7,7 @@ EXE	= @EXE@
 CFLAGS  = @CFLAGS@
 LIBS	= @LIBS@
 
-TARGETS = checkkeys$(EXE) graywin$(EXE) loopwave$(EXE) testaudioinfo$(EXE) testmultiaudio$(EXE) testalpha$(EXE) testbitmap$(EXE) testblitspeed$(EXE) testcdrom$(EXE) testcursor$(EXE) testdraw2$(EXE) testdyngl$(EXE) testerror$(EXE) testfile$(EXE) testgamma$(EXE) testgl$(EXE) testgl2$(EXE) testhread$(EXE) testiconv$(EXE) testjoystick$(EXE) testkeys$(EXE) testlock$(EXE) testoverlay2$(EXE) testoverlay$(EXE) testpalette$(EXE) testplatform$(EXE) testsem$(EXE) testsprite$(EXE) testsprite2$(EXE) testtimer$(EXE) testver$(EXE) testvidinfo$(EXE) testwin$(EXE) testwm$(EXE) testwm2$(EXE) threadwin$(EXE) torturethread$(EXE) testloadso$(EXE) testhaptic$(EXE) testmmousetablet$(EXE) 
+TARGETS = checkkeys$(EXE) graywin$(EXE) loopwave$(EXE) testaudioinfo$(EXE) testmultiaudio$(EXE) testalpha$(EXE) testbitmap$(EXE) testblitspeed$(EXE) testcdrom$(EXE) testcursor$(EXE) testintersections$(EXE) testdraw2$(EXE) testdyngl$(EXE) testerror$(EXE) testfile$(EXE) testgamma$(EXE) testgl$(EXE) testgl2$(EXE) testhread$(EXE) testiconv$(EXE) testjoystick$(EXE) testkeys$(EXE) testlock$(EXE) testoverlay2$(EXE) testoverlay$(EXE) testpalette$(EXE) testplatform$(EXE) testsem$(EXE) testsprite$(EXE) testsprite2$(EXE) testtimer$(EXE) testver$(EXE) testvidinfo$(EXE) testwin$(EXE) testwm$(EXE) testwm2$(EXE) threadwin$(EXE) torturethread$(EXE) testloadso$(EXE) testhaptic$(EXE) testmmousetablet$(EXE)
 
 all: Makefile $(TARGETS)
 
@@ -44,6 +44,9 @@ testcdrom$(EXE): $(srcdir)/testcdrom.c
 testcursor$(EXE): $(srcdir)/testcursor.c
 	$(CC) -o $@ $? $(CFLAGS) $(LIBS)
 
+testintersections$(EXE): $(srcdir)/testintersections.c $(srcdir)/common.c
+	$(CC) -o $@ $(srcdir)/testintersections.c $(srcdir)/common.c $(CFLAGS) $(LIBS)
+
 testdraw2$(EXE): $(srcdir)/testdraw2.c $(srcdir)/common.c
 	$(CC) -o $@ $(srcdir)/testdraw2.c $(srcdir)/common.c $(CFLAGS) $(LIBS)
 
diff --git a/test/testintersections.c b/test/testintersections.c
new file mode 100644
index 000000000..bd48c0172
--- /dev/null
+++ b/test/testintersections.c
@@ -0,0 +1,342 @@
+
+/* Simple program:  draw as many random objects on the screen as possible */
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <time.h>
+
+#include "common.h"
+
+#define SWAP(typ,a,b) do{typ t=a;a=b;b=t;}while(0)
+#define NUM_OBJECTS	100
+
+static CommonState *state;
+static int num_objects;
+static SDL_bool cycle_color;
+static SDL_bool cycle_alpha;
+static int cycle_direction = 1;
+static int current_alpha = 255;
+static int current_color = 255;
+static SDL_BlendMode blendMode = SDL_BLENDMODE_NONE;
+
+void
+DrawPoints(SDL_WindowID window)
+{
+    int i;
+    int x, y;
+    int window_w, window_h;
+
+    /* Query the sizes */
+    SDL_GetWindowSize(window, &window_w, &window_h);
+
+    SDL_SetRenderDrawBlendMode(blendMode);
+    for (i = 0; i < num_objects * 4; ++i) {
+        /* Cycle the color and alpha, if desired */
+        if (cycle_color) {
+            current_color += cycle_direction;
+            if (current_color < 0) {
+                current_color = 0;
+                cycle_direction = -cycle_direction;
+            }
+            if (current_color > 255) {
+                current_color = 255;
+                cycle_direction = -cycle_direction;
+            }
+        }
+        if (cycle_alpha) {
+            current_alpha += cycle_direction;
+            if (current_alpha < 0) {
+                current_alpha = 0;
+                cycle_direction = -cycle_direction;
+            }
+            if (current_alpha > 255) {
+                current_alpha = 255;
+                cycle_direction = -cycle_direction;
+            }
+        }
+        SDL_SetRenderDrawColor(255, (Uint8) current_color,
+                               (Uint8) current_color, (Uint8) current_alpha);
+
+        x = rand() % window_w;
+        y = rand() % window_h;
+        SDL_RenderPoint(x, y);
+    }
+    SDL_SetRenderDrawBlendMode(SDL_BLENDMODE_NONE);
+}
+
+#define MAX_LINES 16
+int num_lines = 0;
+SDL_Rect lines[MAX_LINES];
+static int add_line(int x1, int y1, int x2, int y2) {
+    if (num_lines >= MAX_LINES) return 0;
+    if ((x1 == x2) && (y1 == y2)) return 0;
+
+    printf("adding line (%d, %d), (%d, %d)\n", x1, y1, x2, y2);
+    lines[num_lines].x = x1;
+    lines[num_lines].y = y1;
+    lines[num_lines].w = x2;
+    lines[num_lines].h = y2;
+
+    return ++num_lines;
+}
+
+
+void
+DrawLines(SDL_WindowID window)
+{
+    int i;
+    int x1, y1, x2, y2;
+    int window_w, window_h;
+
+    /* Query the sizes */
+    SDL_GetWindowSize(window, &window_w, &window_h);
+
+    SDL_SetRenderDrawBlendMode(blendMode);
+    for (i = 0; i < num_lines; ++i) {
+        SDL_SetRenderDrawColor(255, 255, 255, 255);
+
+        if (i == -1) {
+            SDL_RenderLine(0, 0, window_w - 1, window_h - 1);
+            SDL_RenderLine(0, window_h - 1, window_w - 1, 0);
+            SDL_RenderLine(0, window_h / 2, window_w - 1, window_h / 2);
+            SDL_RenderLine(window_w / 2, 0, window_w / 2, window_h - 1);
+        } else {
+            SDL_RenderLine(lines[i].x, lines[i].y, lines[i].w, lines[i].h);
+        }
+    }
+    SDL_SetRenderDrawBlendMode(SDL_BLENDMODE_NONE);
+}
+
+#define MAX_RECTS 16
+int num_rects = 0;
+SDL_Rect rects[MAX_RECTS];
+static int add_rect(int x1, int y1, int x2, int y2) {
+    if (num_rects >= MAX_RECTS) return 0;
+    if ((x1 == x2) || (y1 == y2)) return 0;
+
+    if (x1 > x2) SWAP(int, x1, x2);
+    if (y1 > y2) SWAP(int, y1, y2);
+
+    printf("adding rect (%d, %d), (%d, %d) [%dx%d]\n", x1, y1, x2, y2, x2-x1, y2-y1);
+
+    rects[num_rects].x = x1;
+    rects[num_rects].y = y1;
+    rects[num_rects].w = x2 - x1;
+    rects[num_rects].h = y2 - y1;
+
+    return ++num_rects;
+}
+
+static void
+DrawRects(SDL_WindowID window)
+{
+    int i;
+    int window_w, window_h;
+
+    /* Query the sizes */
+    SDL_GetWindowSize(window, &window_w, &window_h);
+
+    SDL_SetRenderDrawBlendMode(SDL_BLENDMODE_NONE);
+    for (i = 0; i < num_rects; ++i) {
+        SDL_SetRenderDrawColor(255, 127, 0, 255);
+        SDL_RenderFill(&rects[i]);
+    }
+    SDL_SetRenderDrawBlendMode(SDL_BLENDMODE_NONE);
+}
+
+static void
+DrawRectLineIntersections(SDL_WindowID window)
+{
+    int i, j, window_w, window_h;
+
+    /* Query the sizes */
+    SDL_GetWindowSize(window, &window_w, &window_h);
+
+    SDL_SetRenderDrawBlendMode(SDL_BLENDMODE_NONE);
+
+    for (i = 0; i < num_rects; i++)
+    for (j = 0; j < num_lines; j++) {
+        int x1, y1, x2, y2;
+        SDL_Rect r;
+        
+        r = rects[i];
+        x1 = lines[j].x;
+        y1 = lines[j].y;
+        x2 = lines[j].w;
+        y2 = lines[j].h;
+
+        if (SDL_IntersectRectAndLine(&r, &x1, &y1, &x2, &y2)) {
+            SDL_SetRenderDrawColor(0, 255, 55, 255);
+            SDL_RenderLine(x1, y1, x2, y2);
+        }
+    }
+
+    SDL_SetRenderDrawBlendMode(SDL_BLENDMODE_NONE);
+}
+
+static void
+DrawRectRectIntersections(SDL_WindowID window)
+{
+    int i, j;
+
+    SDL_SetRenderDrawBlendMode(SDL_BLENDMODE_NONE);
+
+    for (i = 0; i < num_rects; i++)
+    for (j = i+1; j < num_rects; j++) {
+        SDL_Rect r;
+        if (SDL_IntersectRect(&rects[i], &rects[j], &r)) {
+            SDL_SetRenderDrawColor(255, 200, 0, 255);
+            SDL_RenderFill(&r);
+        }
+    }
+
+    SDL_SetRenderDrawBlendMode(SDL_BLENDMODE_NONE);
+}
+
+int
+main(int argc, char *argv[])
+{
+    int mouse_begin_x = -1, mouse_begin_y = -1;
+    int i, done;
+    SDL_Event event;
+    Uint32 then, now, frames;
+
+    /* Initialize parameters */
+    num_objects = NUM_OBJECTS;
+
+    /* Initialize test framework */
+    state = CommonCreateState(argv, SDL_INIT_VIDEO);
+    if (!state) {
+        return 1;
+    }
+    for (i = 1; i < argc;) {
+        int consumed;
+
+        consumed = CommonArg(state, i);
+        if (consumed == 0) {
+            consumed = -1;
+            if (SDL_strcasecmp(argv[i], "--blend") == 0) {
+                if (argv[i + 1]) {
+                    if (SDL_strcasecmp(argv[i + 1], "none") == 0) {
+                        blendMode = SDL_BLENDMODE_NONE;
+                        consumed = 2;
+                    } else if (SDL_strcasecmp(argv[i + 1], "mask") == 0) {
+                        blendMode = SDL_BLENDMODE_MASK;
+                        consumed = 2;
+                    } else if (SDL_strcasecmp(argv[i + 1], "blend") == 0) {
+                        blendMode = SDL_BLENDMODE_BLEND;
+                        consumed = 2;
+                    } else if (SDL_strcasecmp(argv[i + 1], "add") == 0) {
+                        blendMode = SDL_BLENDMODE_ADD;
+                        consumed = 2;
+                    } else if (SDL_strcasecmp(argv[i + 1], "mod") == 0) {
+                        blendMode = SDL_BLENDMODE_MOD;
+                        consumed = 2;
+                    }
+                }
+            } else if (SDL_strcasecmp(argv[i], "--cyclecolor") == 0) {
+                cycle_color = SDL_TRUE;
+                consumed = 1;
+            } else if (SDL_strcasecmp(argv[i], "--cyclealpha") == 0) {
+                cycle_alpha = SDL_TRUE;
+                consumed = 1;
+            } else if (SDL_isdigit(*argv[i])) {
+                num_objects = SDL_atoi(argv[i]);
+                consumed = 1;
+            }
+        }
+        if (consumed < 0) {
+            fprintf(stderr,
+                    "Usage: %s %s [--blend none|mask|blend|add|mod] [--cyclecolor] [--cyclealpha]\n",
+                    argv[0], CommonUsage(state));
+            return 1;
+        }
+        i += consumed;
+    }
+    if (!CommonInit(state)) {
+        return 2;
+    }
+
+    /* Create the windows and initialize the renderers */
+    for (i = 0; i < state->num_windows; ++i) {
+        SDL_SelectRenderer(state->windows[i]);
+        SDL_SetRenderDrawColor(0xA0, 0xA0, 0xA0, 0xFF);
+        SDL_RenderFill(NULL);
+    }
+
+    srand(time(NULL));
+
+    /* Main render loop */
+    frames = 0;
+    then = SDL_GetTicks();
+    done = 0;
+    while (!done) {
+        /* Check for events */
+        ++frames;
+        while (SDL_PollEvent(&event)) {
+            CommonEvent(state, &event, &done);
+            switch (event.type) {
+            case SDL_MOUSEBUTTONDOWN:
+                if (event.button.which == 0) {
+                    mouse_begin_x = event.button.x;
+                    mouse_begin_y = event.button.y;
+                }
+                break;
+            case SDL_MOUSEBUTTONUP:
+                if (event.button.which == 0) {
+                    if (event.button.button == 3)
+                        add_line(mouse_begin_x, mouse_begin_y, event.button.x, event.button.y);
+                    if (event.button.button == 1)
+                        add_rect(mouse_begin_x, mouse_begin_y, event.button.x, event.button.y);
+                }
+                break;
+            case SDL_KEYDOWN:
+                switch (event.key.keysym.sym) {
+                    case 'l':
+                        if (event.key.keysym.mod & KMOD_SHIFT) num_lines = 0;
+                        else add_line(rand()%640, rand()%480, rand()%640, rand()%480);
+                        break;
+                    case 'r':
+                        if (event.key.keysym.mod & KMOD_SHIFT) num_rects = 0;
+                        else add_rect(rand()%640, rand()%480, rand()%640, rand()%480);
+                        break;
+                }
+                break;
+            case SDL_WINDOWEVENT:
+                switch (event.window.event) {
+                case SDL_WINDOWEVENT_EXPOSED:
+                    SDL_SelectRenderer(event.window.windowID);
+                    SDL_SetRenderDrawColor(0xA0, 0xA0, 0xA0, 0xFF);
+                    SDL_RenderFill(NULL);
+                    break;
+                }
+                break;
+            default:
+                break;
+            }
+        }
+        for (i = 0; i < state->num_windows; ++i) {
+            SDL_SelectRenderer(state->windows[i]);
+            SDL_SetRenderDrawColor(0xA0, 0xA0, 0xA0, 0xFF);
+            SDL_RenderFill(NULL);
+
+            DrawRects(state->windows[i]);
+            DrawPoints(state->windows[i]);
+            DrawRectRectIntersections(state->windows[i]);
+            DrawLines(state->windows[i]);
+            DrawRectLineIntersections(state->windows[i]);
+
+            SDL_RenderPresent();
+        }
+    }
+
+    /* Print out some timing information */
+    now = SDL_GetTicks();
+    if (now > then) {
+        double fps = ((double) frames * 1000) / (now - then);
+        printf("%2.2f frames per second\n", fps);
+    }
+    return 0;
+}
+
+/* vi: set ts=4 sw=4 expandtab: */