+#define _GNU_SOURCE
+#include <math.h>
+#include <err.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <stdbool.h>
+#include "stdrusty.h"
+#include <SDL/SDL.h>
+
+#define MAX_X 512
+#define MAX_Y 512
+
+/* Obtained from http://tog.acm.org/GraphicsGems/gemsiii/insectc.c */
+/* Faster Line Segment Intersection */
+/* Franklin Antonio */
+
+/* return values */
+#define DONT_INTERSECT 0
+#define DO_INTERSECT 1
+#define PARALLEL 2
+
+/* The SAME_SIGNS macro assumes arithmetic where the exclusive-or */
+/* operation will work on sign bits. This works for twos-complement,*/
+/* and most other machine arithmetic. */
+#define SAME_SIGNS( a, b ) \
+ (((long) ((unsigned long) a ^ (unsigned long) b)) >= 0 )
+
+
+/* The use of some short working variables allows this code to run */
+/* faster on 16-bit computers, but is not essential. It should not */
+/* affect operation on 32-bit computers. The short working variables*/
+/* to not restrict the range of valid input values, as these were */
+/* constrained in any case, due to algorithm restrictions. */
+static int lines_intersect(long x1, long y1, long x2, long y2, long x3, long y3,
+ long x4,long y4, long *x, long *y)
+{
+
+ long Ax,Bx,Cx,Ay,By,Cy,d,e,f,num,offset;
+ short x1lo,x1hi,y1lo,y1hi;
+
+ Ax = x2-x1;
+ Bx = x3-x4;
+
+ if(Ax<0) { /* X bound box test*/
+ x1lo=(short)x2; x1hi=(short)x1;
+ } else {
+ x1hi=(short)x2; x1lo=(short)x1;
+ }
+ if(Bx>0) {
+ if(x1hi < (short)x4 || (short)x3 < x1lo) return DONT_INTERSECT;
+ } else {
+ if(x1hi < (short)x3 || (short)x4 < x1lo) return DONT_INTERSECT;
+ }
+
+ Ay = y2-y1;
+ By = y3-y4;
+
+ if(Ay<0) { /* Y bound box test*/
+ y1lo=(short)y2; y1hi=(short)y1;
+ } else {
+ y1hi=(short)y2; y1lo=(short)y1;
+ }
+ if(By>0) {
+ if(y1hi < (short)y4 || (short)y3 < y1lo) return DONT_INTERSECT;
+ } else {
+ if(y1hi < (short)y3 || (short)y4 < y1lo) return DONT_INTERSECT;
+ }
+
+
+ Cx = x1-x3;
+ Cy = y1-y3;
+ d = By*Cx - Bx*Cy; /* alpha numerator*/
+ f = Ay*Bx - Ax*By; /* both denominator*/
+ if(f>0) { /* alpha tests*/
+ if(d<0 || d>f) return DONT_INTERSECT;
+ } else {
+ if(d>0 || d<f) return DONT_INTERSECT;
+ }
+
+ e = Ax*Cy - Ay*Cx; /* beta numerator*/
+ if(f>0) { /* beta tests*/
+ if(e<0 || e>f) return DONT_INTERSECT;
+ } else {
+ if(e>0 || e<f) return DONT_INTERSECT;
+ }
+
+/*compute intersection coordinates*/
+
+ if(f==0) return PARALLEL;
+ num = d*Ax; /* numerator */
+ offset = SAME_SIGNS(num,f) ? f/2 : -f/2; /* round direction*/
+ *x = x1 + (num+offset) / f; /* intersection x */
+
+ num = d*Ay;
+ offset = SAME_SIGNS(num,f) ? f/2 : -f/2;
+ *y = y1 + (num+offset) / f; /* intersection y */
+
+ return DO_INTERSECT;
+}
+
+// A set of very useful macros that you will find in most
+// code that I write whether I use them in a program or
+// not.
+
+#define abs(a) (((a)<0) ? -(a) : (a))
+#define sign(a) (((a)<0) ? -1 : (a)>0 ? 1 : 0)
+
+// The following code implements a Bresenham line drawing
+// algorithm. There are 4 separate routines each optimized
+// for one of the four pixel depths supported by SDL. SDL
+// support many pixel formats, but it only support 8, 16,
+// 24, and 32 bit pixels.
+
+//----------------------------------------------------------
+
+// Draw lines in 8 bit surfaces.
+
+static void line8(SDL_Surface *s,
+ int x1, int y1,
+ int x2, int y2,
+ Uint32 color)
+{
+ int d;
+ int x;
+ int y;
+ int ax;
+ int ay;
+ int sx;
+ int sy;
+ int dx;
+ int dy;
+
+ Uint8 *lineAddr;
+ Sint32 yOffset;
+
+ dx = x2 - x1;
+ ax = abs(dx) << 1;
+ sx = sign(dx);
+
+ dy = y2 - y1;
+ ay = abs(dy) << 1;
+ sy = sign(dy);
+ yOffset = sy * s->pitch;
+
+ x = x1;
+ y = y1;
+
+ lineAddr = ((Uint8 *)(s->pixels)) + (y * s->pitch);
+ if (ax>ay)
+ { /* x dominant */
+ d = ay - (ax >> 1);
+ for (;;)
+ {
+ if (y >= 0 && y < MAX_Y && x >= 0 && x < MAX_X)
+ *(lineAddr + x) = (Uint8)color;
+
+ if (x == x2)
+ {
+ return;
+ }
+ if (d>=0)
+ {
+ y += sy;
+ lineAddr += yOffset;
+ d -= ax;
+ }
+ x += sx;
+ d += ay;
+ }
+ }
+ else
+ { /* y dominant */
+ d = ax - (ay >> 1);
+ for (;;)
+ {
+ if (y >= 0 && y < MAX_Y && x >= 0 && x < MAX_X)
+ *(lineAddr + x) = (Uint8)color;
+
+ if (y == y2)
+ {
+ return;
+ }
+ if (d>=0)
+ {
+ x += sx;
+ d -= ay;
+ }
+ y += sy;
+ lineAddr += yOffset;
+ d += ax;
+ }
+ }
+}
+
+//----------------------------------------------------------
+
+// Draw lines in 16 bit surfaces. Note that this code will
+// also work on 15 bit surfaces.
+
+static void line16(SDL_Surface *s,
+ int x1, int y1,
+ int x2, int y2,
+ Uint32 color)
+{
+ int d;
+ int x;
+ int y;
+ int ax;
+ int ay;
+ int sx;
+ int sy;
+ int dx;
+ int dy;
+
+ Uint8 *lineAddr;
+ Sint32 yOffset;
+
+ dx = x2 - x1;
+ ax = abs(dx) << 1;
+ sx = sign(dx);
+
+ dy = y2 - y1;
+ ay = abs(dy) << 1;
+ sy = sign(dy);
+ yOffset = sy * s->pitch;
+
+ x = x1;
+ y = y1;
+
+ lineAddr = ((Uint8 *)s->pixels) + (y * s->pitch);
+ if (ax>ay)
+ { /* x dominant */
+ d = ay - (ax >> 1);
+ for (;;)
+ {
+ if (y >= 0 && y < MAX_Y && x >= 0 && x < MAX_X)
+ *((Uint16 *)(lineAddr + (x << 1))) = (Uint16)color;
+
+ if (x == x2)
+ {
+ return;
+ }
+ if (d>=0)
+ {
+ y += sy;
+ lineAddr += yOffset;
+ d -= ax;
+ }
+ x += sx;
+ d += ay;
+ }
+ }
+ else
+ { /* y dominant */
+ d = ax - (ay >> 1);
+ for (;;)
+ {
+ if (y >= 0 && y < MAX_Y && x >= 0 && x < MAX_X)
+ *((Uint16 *)(lineAddr + (x << 1))) = (Uint16)color;
+
+ if (y == y2)
+ {
+ return;
+ }
+ if (d>=0)
+ {
+ x += sx;
+ d -= ay;
+ }
+ y += sy;
+ lineAddr += yOffset;
+ d += ax;
+ }
+ }
+}
+
+//----------------------------------------------------------
+
+// Draw lines in 24 bit surfaces. 24 bit surfaces require
+// special handling because the pixels don't fall on even
+// address boundaries. Instead of being able to store a
+// single byte, word, or long you have to store 3
+// individual bytes. As a result 24 bit graphics is slower
+// than the other pixel sizes.
+
+static void line24(SDL_Surface *s,
+ int x1, int y1,
+ int x2, int y2,
+ Uint32 color)
+{
+ int d;
+ int x;
+ int y;
+ int ax;
+ int ay;
+ int sx;
+ int sy;
+ int dx;
+ int dy;
+
+ Uint8 *lineAddr;
+ Sint32 yOffset;
+
+#if (SDL_BYTEORDER == SDL_BIG_ENDIAN)
+ color <<= 8;
+#endif
+
+ dx = x2 - x1;
+ ax = abs(dx) << 1;
+ sx = sign(dx);
+
+ dy = y2 - y1;
+ ay = abs(dy) << 1;
+ sy = sign(dy);
+ yOffset = sy * s->pitch;
+
+ x = x1;
+ y = y1;
+
+ lineAddr = ((Uint8 *)(s->pixels)) + (y * s->pitch);
+ if (ax>ay)
+ { /* x dominant */
+ d = ay - (ax >> 1);
+ for (;;)
+ {
+ Uint8 *p = (lineAddr + (x * 3));
+ if (y >= 0 && y < MAX_Y && x >= 0 && x < MAX_X)
+ memcpy(p, &color, 3);
+
+ if (x == x2)
+ {
+ return;
+ }
+ if (d>=0)
+ {
+ y += sy;
+ lineAddr += yOffset;
+ d -= ax;
+ }
+ x += sx;
+ d += ay;
+ }
+ }
+ else
+ { /* y dominant */
+ d = ax - (ay >> 1);
+ for (;;)
+ {
+ Uint8 *p = (lineAddr + (x * 3));
+ if (y >= 0 && y < MAX_Y && x >= 0 && x < MAX_X)
+ memcpy(p, &color, 3);
+
+ if (y == y2)
+ {
+ return;
+ }
+ if (d>=0)
+ {
+ x += sx;
+ d -= ay;
+ }
+ y += sy;
+ lineAddr += yOffset;
+ d += ax;
+ }
+ }
+}
+
+//----------------------------------------------------------
+
+// Draw lines in 32 bit surfaces. Note that this routine
+// ignores alpha values. It writes them into the surface
+// if they are included in the pixel, but does nothing
+// else with them.
+
+static void line32(SDL_Surface *s,
+ int x1, int y1,
+ int x2, int y2,
+ Uint32 color)
+{
+ int d;
+ int x;
+ int y;
+ int ax;
+ int ay;
+ int sx;
+ int sy;
+ int dx;
+ int dy;
+
+ Uint8 *lineAddr;
+ Sint32 yOffset;
+
+ dx = x2 - x1;
+ ax = abs(dx) << 1;
+ sx = sign(dx);
+
+ dy = y2 - y1;
+ ay = abs(dy) << 1;
+ sy = sign(dy);
+ yOffset = sy * s->pitch;
+
+ x = x1;
+ y = y1;
+
+ lineAddr = ((Uint8 *)(s->pixels)) + (y * s->pitch);
+ if (ax>ay)
+ { /* x dominant */
+ d = ay - (ax >> 1);
+ for (;;)
+ {
+ if (y >= 0 && y < MAX_Y && x >= 0 && x < MAX_X)
+ *((Uint32 *)(lineAddr + (x << 2))) = (Uint32)color;
+
+ if (x == x2)
+ {
+ return;
+ }
+ if (d>=0)
+ {
+ y += sy;
+ lineAddr += yOffset;
+ d -= ax;
+ }
+ x += sx;
+ d += ay;
+ }
+ }
+ else
+ { /* y dominant */
+ d = ax - (ay >> 1);
+ for (;;)
+ {
+ if (y >= 0 && y < MAX_Y && x >= 0 && x < MAX_X)
+ *((Uint32 *)(lineAddr + (x << 2))) = (Uint32)color;
+
+ if (y == y2)
+ {
+ return;
+ }
+ if (d>=0)
+ {
+ x += sx;
+ d -= ay;
+ }
+ y += sy;
+ lineAddr += yOffset;
+ d += ax;
+ }
+ }
+}
+
+//----------------------------------------------------------
+
+// Examine the depth of a surface and select a line
+// drawing routine optimized for the bytes/pixel of the
+// surface.
+
+static void line(SDL_Surface *s,
+ int x1, int y1,
+ int x2, int y2,
+ Uint32 color)
+{
+ switch (s->format->BytesPerPixel)
+ {
+ case 1:
+ line8(s, x1, y1, x2, y2, color);
+ break;
+ case 2:
+ line16(s, x1, y1, x2, y2, color);
+ break;
+ case 3:
+ line24(s, x1, y1, x2, y2, color);
+ break;
+ case 4:
+ line32(s, x1, y1, x2, y2, color);
+ break;
+ }
+}
+
+#if 1
+struct coord
+{
+ long x;
+ long y;
+};
+
+struct ball
+{
+ struct coord pos;
+ struct coord move;
+};
+
+struct line_segment
+{
+ struct coord start, end;
+};
+
+static void thick_line(SDL_Surface *s, const struct line_segment *l)
+{
+ struct line_segment adj;
+ int x, y;
+
+ /* Cheap hack */
+ for (x = -1; x < 2; x++) {
+ for (y = -1; y < 2; y++) {
+ adj.start.x = l->start.x + x;
+ adj.end.x = l->end.x + x;
+ adj.start.y = l->start.y + y;
+ adj.end.y = l->end.y + y;
+
+ line(s, adj.start.x, adj.start.y, adj.end.x, adj.end.y,
+ 0);
+ }
+ }
+}
+
+static bool intersect(const struct coord *c1, const struct coord *c2,
+ const struct line_segment *seg, struct coord *intersect)
+{
+ return lines_intersect(c1->x, c1->y, c2->x, c2->y,
+ seg->start.x, seg->start.y,
+ seg->end.x, seg->end.y,
+ &intersect->x, &intersect->y) == DO_INTERSECT;
+}
+
+static double dist(const struct coord *c1, const struct coord *c2)
+{
+ long x = (c1->x - c2->x), y = (c1->y - c2->y);
+ return sqrt(x * x + y * y);
+}
+
+static unsigned rad_to_deg(double rad)
+{
+ return ((unsigned)(rad / M_PI * 180) + 360) % 360;
+}
+
+static void bounce(struct ball *ball, const struct line_segment *line,
+ struct coord *remainder)
+{
+ double len, speed, lang, iang, oang;
+ struct coord isect, new;
+
+ new.x = ball->pos.x + ball->move.x;
+ new.y = ball->pos.y + ball->move.y;
+
+ /* How far were we supposed to move ball? */
+ len = sqrt(remainder->x * remainder->x + remainder->y * remainder->y);
+
+ /* How far is it to intersection? */
+ intersect(&ball->pos, &new, line, &isect);
+ len -= dist(&ball->pos, &isect);
+
+ /* Move ball to intersection. */
+ ball->pos = isect;
+
+ /* Outgoing angle = 2 * line angle - incident angle. */
+ lang = atan2(line->end.x - line->start.x, line->end.y - line->start.y);
+ iang = atan2(ball->move.x, ball->move.y);
+ oang = 2 * lang - iang, 2*M_PI;
+ printf("lang = %u, iang = %u, oang=%u\n",
+ rad_to_deg(lang),
+ rad_to_deg(iang),
+ rad_to_deg(oang));
+
+ /* Set new direction for ball, at same speed */
+ speed = sqrt(ball->move.x * ball->move.x + ball->move.y * ball->move.y);
+ ball->move.x = round(sin(oang) * speed);
+ ball->move.y = round(cos(oang) * speed);
+
+ /* Set remainder. */
+ remainder->x = round(sin(oang) * len);
+ remainder->y = round(cos(oang) * len);
+ printf("len = %f, remainder = %li,%li\n", len, remainder->x, remainder->y);
+}
+
+static struct line_segment border[] = {
+ { { 0, 0, }, { MAX_X-1, 0 } },
+ { { MAX_X-1, 0, }, { MAX_X-1, MAX_Y-1 } },
+ { { MAX_X-1, MAX_Y-1, }, { 0, MAX_Y-1 } },
+ { { 0, MAX_Y-1, }, { 0, 0 } },
+};
+
+static inline float deg_to_rad(float degrees)
+{
+ return degrees * M_PI / 180;
+}
+
+static SDL_Surface *sub_surface(SDL_Surface *screen, int w, int h)
+{
+ return SDL_CreateRGBSurface(SDL_SWSURFACE, w, h,
+ screen->format->BitsPerPixel,
+ screen->format->Rmask,
+ screen->format->Gmask,
+ screen->format->Bmask,
+ screen->format->Amask);
+}
+
+static SDL_Surface *ball_surface(SDL_Surface *screen)
+{
+ SDL_Surface *ball;
+
+ /* Just like the screen surface. */
+ ball = sub_surface(screen, 5, 5);
+
+ /* Lock the surface */
+ SDL_LockSurface(ball);
+
+ /* Black, white corners. */
+ memset(ball->pixels, 0x00, ball->pitch * 5);
+ line(ball, 0, 0, 0, 0, 0xFFFFFFFF);
+ line(ball, 4, 0, 4, 0, 0xFFFFFFFF);
+ line(ball, 0, 4, 0, 4, 0xFFFFFFFF);
+ line(ball, 4, 4, 4, 4, 0xFFFFFFFF);
+ SDL_UnlockSurface(ball);
+
+ return ball;
+}
+
+int main(int argc, char *argv[])
+{
+ struct ball ball;
+ struct line_segment lines[ARRAY_SIZE(border) + 1];
+ static int isect_count = 0;
+ SDL_Surface *screen, *ballsur, *savesur = NULL;
+ Uint8 video_bpp;
+ Uint32 videoflags;
+ int i;
+ SDL_Event event;
+ struct line_segment *last_l = NULL;
+ SDL_Rect rect;
+
+ if (argc != 9)
+ errx(1, "Usage: %s ballx bally ballangle ballspeed linestartx linestarty lineendx linendy\n"
+ " Where ballangle is 0 for north, 90 for east, etc\n",
+ argv[0]);
+
+ ball.pos.x = atol(argv[1]);
+ ball.pos.y = atol(argv[2]);
+ ball.move.x = roundf(sin(deg_to_rad(atof(argv[3]))) * atol(argv[4]));
+ ball.move.y = roundf(cos(deg_to_rad(atof(argv[3]))) * atol(argv[4]));
+ printf("ball move = %li,%li\n", ball.move.x, ball.move.y);
+
+ memcpy(lines, border, sizeof(border));
+ lines[ARRAY_SIZE(border)].start.x = atof(argv[5]);
+ lines[ARRAY_SIZE(border)].start.y = atof(argv[6]);
+ lines[ARRAY_SIZE(border)].end.x = atof(argv[7]);
+ lines[ARRAY_SIZE(border)].end.y = atof(argv[8]);
+
+ /* Initialize SDL */
+ if ( SDL_Init(SDL_INIT_VIDEO) < 0 ) {
+ fprintf(stderr, "Couldn't initialize SDL: %s\n",SDL_GetError());
+ return(1);
+ }
+
+ video_bpp = 0;
+ videoflags = SDL_SWSURFACE;
+
+ /* Set 640x480 video mode */
+ if ( (screen=SDL_SetVideoMode(MAX_X,MAX_Y,video_bpp,videoflags)) == NULL ) {
+ errx(1, "Couldn't set %dx%dx%d video mode: %s",
+ MAX_X, MAX_Y,video_bpp, SDL_GetError());
+ }
+
+ /* Set the surface pixels and refresh! */
+ if ( SDL_LockSurface(screen) < 0 ) {
+ errx(1, "Couldn't lock the display surface: %s",
+ SDL_GetError());
+ }
+ /* White. */
+ memset(screen->pixels, 0xFF, screen->pitch * screen->h);
+
+ /* Draw lines. */
+ for (i = 0; i < ARRAY_SIZE(lines); i++)
+ thick_line(screen, &lines[i]);
+
+ SDL_UnlockSurface(screen);
+ SDL_UpdateRect(screen, 0, 0, 0, 0);
+
+ ballsur = ball_surface(screen);
+
+ do {
+ struct coord new, isect, move = ball.move;
+ struct line_segment *best_l;
+ unsigned i;
+ double best_d;
+#if 0
+ SDL_Rect rect;
+
+ rect.x = ball.pos.x - ballsur->w/2;
+ rect.y = ball.pos.y - ballsur->h/2;
+ rect.w = ballsur->w;
+ rect.h = ballsur->h;
+#endif
+
+ again:
+ best_d = MAX_X + MAX_Y;
+ best_l = NULL;
+ new.x = ball.pos.x + move.x;
+ new.y = ball.pos.y + move.y;
+
+ printf("Ball at %li,%li (%li,%li)\n", ball.pos.x, ball.pos.y,
+ move.x, move.y);
+
+ for (i = 0; i < ARRAY_SIZE(lines); i++) {
+ if (last_l == &lines[i])
+ continue;
+ if (intersect(&ball.pos, &new, &lines[i], &isect)) {
+ double d;
+ d = dist(&ball.pos, &isect);
+ if (d < best_d) {
+ best_l = &lines[i];
+ best_d = d;
+ }
+ }
+ }
+ if (best_l) {
+ printf("Ball bouncing off (%lu,%lu %lu,%lu)!\n",
+ best_l->start.x, best_l->start.y,
+ best_l->end.x, best_l->end.y);
+ bounce(&ball, best_l, &move);
+ /* Don't hit the same line twice. */
+ last_l = best_l;
+ isect_count++;
+ goto again;
+ }
+
+ /* Restore what was there before ball. */
+ if (savesur) {
+ SDL_BlitSurface(savesur, NULL, screen, &rect);
+ SDL_UpdateRect(screen, rect.x, rect.y, rect.w, rect.h);
+ } else {
+ savesur = sub_surface(screen, ballsur->w, ballsur->h);
+ }
+
+ /* Save away image under new ball. */
+ rect.w = ballsur->w;
+ rect.h = ballsur->h;
+ rect.x = new.x - ballsur->w/2;
+ rect.y = new.y - ballsur->h/2;
+ SDL_BlitSurface(screen, &rect, savesur, NULL);
+
+ /* Draw new ball */
+ SDL_BlitSurface(ballsur, NULL, screen, &rect);
+ SDL_UpdateRect(screen, rect.x, rect.y, rect.w, rect.h);
+ /* That SDL_BlitSurface can crop rect. */
+ rect.x = new.x - ballsur->w/2;
+ rect.y = new.y - ballsur->h/2;
+ ball.pos = new;
+ SDL_Delay(5);
+ } while (!SDL_PollEvent(&event) || event.type != SDL_QUIT);
+ SDL_Quit();
+ return 0;
+}
+#endif
projects / ponghero.git / commitdiff