From: Rusty Russell Date: Sun, 13 Jan 2008 11:09:57 +0000 (+1100) Subject: First cut of projector pong. X-Git-Url: https://git.ozlabs.org/?p=ponghero.git;a=commitdiff_plain;h=1774b5732984e261bf4fd68350051e7ff706c36c First cut of projector pong. --- 1774b5732984e261bf4fd68350051e7ff706c36c diff --git a/.hgignore b/.hgignore new file mode 100644 index 0000000..00b157f --- /dev/null +++ b/.hgignore @@ -0,0 +1,2 @@ +~$ +^prpong$ diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..df3ccae --- /dev/null +++ b/Makefile @@ -0,0 +1,5 @@ +#! /usr/bin/make + +CFLAGS:=-Wall -Wmissing-prototypes -Wmissing-declarations -g #-g #-O2 -g +LDFLAGS:=-lSDL +prpong: prpong.c stdrusty.h diff --git a/prpong.c b/prpong.c new file mode 100644 index 0000000..c62d0fc --- /dev/null +++ b/prpong.c @@ -0,0 +1,755 @@ +#define _GNU_SOURCE +#include +#include +#include +#include +#include +#include "stdrusty.h" +#include + +#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 || d0) { /* beta tests*/ + if(e<0 || e>f) return DONT_INTERSECT; + } else { + if(e>0 || e0 ? 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 diff --git a/stdrusty.h b/stdrusty.h new file mode 100644 index 0000000..f5b73fb --- /dev/null +++ b/stdrusty.h @@ -0,0 +1,85 @@ +#ifndef _STDRUSTY_H +#define _STDRUSTY_H +#include +#include +#include +#include + +/* Is A == B ? */ +#define streq(a,b) (strcmp((a),(b)) == 0) + +/* Does A start with B ? */ +#define strstarts(a,b) (strncmp((a),(b),strlen(b)) == 0) + +/* Does A end in B ? */ +static inline bool strends(const char *a, const char *b) +{ + if (strlen(a) < strlen(b)) + return false; + + return streq(a + strlen(a) - strlen(b), b); +} + +#define ___stringify(x) #x +#define __stringify(x) ___stringify(x) + +#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0])) + +/* Upper bound to sprintf this simple type? Each 3 bits < 1 digit. */ +#define CHAR_SIZE(type) (((sizeof(type)*CHAR_BIT + 2) / 3) + 1) + +typedef uint32_t u32; +typedef uint16_t u16; +typedef uint8_t u8; + +/* Convenient wrappers for malloc and realloc. Use them. */ +#define new(type) ((type *)malloc_nofail(sizeof(type))) +#define new_array(type, num) realloc_array((type *)0, (num)) +#define realloc_array(ptr, num) ((__typeof__(ptr))_realloc_array((ptr), sizeof((*ptr)), (num))) + +void *malloc_nofail(size_t size); +void *realloc_nofail(void *ptr, size_t size); +void *_realloc_array(void *ptr, size_t size, size_t num); + +void barf(const char *fmt, ...) __attribute__((noreturn, format(printf,1,2))); +void barf_perror(const char *fmt, ...) + __attribute__((noreturn, format(printf,1,2))); + +/* This version adds one byte (for nul term) */ +void *grab_file(const char *filename, unsigned long *size); +void release_file(void *data, unsigned long size); + +/* For writing daemons, based on Stevens. */ +void daemonize(void); + +/* Signal handling: returns fd to listen on. */ +int signal_to_fd(int signal); +void close_signal(int fd); + +/* from the Linux Kernel: + * min()/max() macros that also do + * strict type-checking.. See the + * "unnecessary" pointer comparison. + */ +#define min(x,y) ({ \ + typeof(x) _x = (x); \ + typeof(y) _y = (y); \ + (void) (&_x == &_y); \ + _x < _y ? _x : _y; }) + +#define max(x,y) ({ \ + typeof(x) _x = (x); \ + typeof(y) _y = (y); \ + (void) (&_x == &_y); \ + _x > _y ? _x : _y; }) + +/* Delete (by memmove) elements of an array */ +#define delete_arr(p, len, off, num) \ + _delete_arr((p), (len), (off), (num), sizeof(*p)) +void _delete_arr(void *p, unsigned len, unsigned off, unsigned num, size_t s); + +/* Write/read this much data. */ +bool write_all(int fd, const void *data, unsigned long size); +bool read_all(int fd, void *data, unsigned long size); + +#endif /* _STDRUSTY_H */