]> git.ozlabs.org Git - ponghero.git/blob - prpong.c
First cut of projector pong.
[ponghero.git] / prpong.c
1 #define _GNU_SOURCE
2 #include <math.h>
3 #include <err.h>
4 #include <stdlib.h>
5 #include <stdio.h>
6 #include <stdbool.h>
7 #include "stdrusty.h"
8 #include <SDL/SDL.h>
9
10 #define MAX_X 512
11 #define MAX_Y 512
12
13 /* Obtained from http://tog.acm.org/GraphicsGems/gemsiii/insectc.c */
14 /* Faster Line Segment Intersection   */
15 /* Franklin Antonio                   */
16
17 /* return values */
18 #define DONT_INTERSECT 0
19 #define DO_INTERSECT   1
20 #define PARALLEL       2
21
22 /* The SAME_SIGNS macro assumes arithmetic where the exclusive-or    */
23 /* operation will work on sign bits.  This works for twos-complement,*/
24 /* and most other machine arithmetic.                                */
25 #define SAME_SIGNS( a, b )                                              \
26         (((long) ((unsigned long) a ^ (unsigned long) b)) >= 0 )
27
28
29 /* The use of some short working variables allows this code to run   */
30 /* faster on 16-bit computers, but is not essential.  It should not  */
31 /* affect operation on 32-bit computers.  The short working variables*/
32 /* to not restrict the range of valid input values, as these were    */
33 /* constrained in any case, due to algorithm restrictions.           */
34 static int lines_intersect(long x1, long y1, long x2, long y2, long x3, long y3,
35                            long x4,long y4, long *x, long *y) 
36 {
37
38         long Ax,Bx,Cx,Ay,By,Cy,d,e,f,num,offset;
39         short x1lo,x1hi,y1lo,y1hi;
40
41         Ax = x2-x1;
42         Bx = x3-x4;
43
44         if(Ax<0) {                                              /* X bound box test*/
45                 x1lo=(short)x2; x1hi=(short)x1;
46         } else {
47                 x1hi=(short)x2; x1lo=(short)x1;
48         }
49         if(Bx>0) {
50                 if(x1hi < (short)x4 || (short)x3 < x1lo) return DONT_INTERSECT;
51         } else {
52                 if(x1hi < (short)x3 || (short)x4 < x1lo) return DONT_INTERSECT;
53         }
54
55         Ay = y2-y1;
56         By = y3-y4;
57
58         if(Ay<0) {                                              /* Y bound box test*/
59                 y1lo=(short)y2; y1hi=(short)y1;
60         } else {
61                 y1hi=(short)y2; y1lo=(short)y1;
62         }
63         if(By>0) {
64                 if(y1hi < (short)y4 || (short)y3 < y1lo) return DONT_INTERSECT;
65         } else {
66                 if(y1hi < (short)y3 || (short)y4 < y1lo) return DONT_INTERSECT;
67         }
68
69
70         Cx = x1-x3;
71         Cy = y1-y3;
72         d = By*Cx - Bx*Cy;                                      /* alpha numerator*/
73         f = Ay*Bx - Ax*By;                                      /* both denominator*/
74         if(f>0) {                                               /* alpha tests*/
75                 if(d<0 || d>f) return DONT_INTERSECT;
76         } else {
77                 if(d>0 || d<f) return DONT_INTERSECT;
78         }
79
80         e = Ax*Cy - Ay*Cx;                                      /* beta numerator*/
81         if(f>0) {                                               /* beta tests*/
82                 if(e<0 || e>f) return DONT_INTERSECT;
83         } else {
84                 if(e>0 || e<f) return DONT_INTERSECT;
85         }
86
87 /*compute intersection coordinates*/
88
89         if(f==0) return PARALLEL;
90         num = d*Ax;                                             /* numerator */
91         offset = SAME_SIGNS(num,f) ? f/2 : -f/2;                /* round direction*/
92         *x = x1 + (num+offset) / f;                             /* intersection x */
93
94         num = d*Ay;
95         offset = SAME_SIGNS(num,f) ? f/2 : -f/2;
96         *y = y1 + (num+offset) / f;                             /* intersection y */
97
98         return DO_INTERSECT;
99 }
100         
101 // A set of very useful macros that you will find in most
102 // code that I write whether I use them in a program or
103 // not.
104
105 #define abs(a) (((a)<0) ? -(a) : (a))
106 #define sign(a) (((a)<0) ? -1 : (a)>0 ? 1 : 0)
107
108 // The following code implements a Bresenham line drawing
109 // algorithm. There are 4 separate routines each optimized
110 // for one of the four pixel depths supported by SDL. SDL
111 // support many pixel formats, but it only support 8, 16,
112 // 24, and 32 bit pixels.
113
114 //----------------------------------------------------------
115
116 // Draw lines in 8 bit surfaces.
117
118 static void line8(SDL_Surface *s, 
119                   int x1, int y1, 
120                   int x2, int y2, 
121                   Uint32 color)
122 {
123   int d;
124   int x;
125   int y;
126   int ax;
127   int ay;
128   int sx;
129   int sy;
130   int dx;
131   int dy;
132
133   Uint8 *lineAddr;
134   Sint32 yOffset;
135
136   dx = x2 - x1;  
137   ax = abs(dx) << 1;  
138   sx = sign(dx);
139
140   dy = y2 - y1;  
141   ay = abs(dy) << 1;  
142   sy = sign(dy);
143   yOffset = sy * s->pitch;
144
145   x = x1;
146   y = y1;
147
148   lineAddr = ((Uint8 *)(s->pixels)) + (y * s->pitch);
149   if (ax>ay)
150   {                      /* x dominant */
151     d = ay - (ax >> 1);
152     for (;;)
153     {
154       if (y >= 0 && y < MAX_Y && x >= 0 && x < MAX_X)
155         *(lineAddr + x) = (Uint8)color;
156
157       if (x == x2)
158       {
159         return;
160       }
161       if (d>=0)
162       {
163         y += sy;
164         lineAddr += yOffset;
165         d -= ax;
166       }
167       x += sx;
168       d += ay;
169     }
170   }
171   else
172   {                      /* y dominant */
173     d = ax - (ay >> 1);
174     for (;;)
175     {
176       if (y >= 0 && y < MAX_Y && x >= 0 && x < MAX_X)
177         *(lineAddr + x) = (Uint8)color;
178
179       if (y == y2)
180       {
181         return;
182       }
183       if (d>=0) 
184       {
185         x += sx;
186         d -= ay;
187       }
188       y += sy;
189       lineAddr += yOffset;
190       d += ax;
191     }
192   }
193 }
194
195 //----------------------------------------------------------
196
197 // Draw lines in 16 bit surfaces. Note that this code will
198 // also work on 15 bit surfaces.
199
200 static void line16(SDL_Surface *s, 
201                    int x1, int y1, 
202                    int x2, int y2, 
203                    Uint32 color)
204 {
205   int d;
206   int x;
207   int y;
208   int ax;
209   int ay;
210   int sx;
211   int sy;
212   int dx;
213   int dy;
214
215   Uint8 *lineAddr;
216   Sint32 yOffset;
217
218   dx = x2 - x1;  
219   ax = abs(dx) << 1;  
220   sx = sign(dx);
221
222   dy = y2 - y1;  
223   ay = abs(dy) << 1;  
224   sy = sign(dy);
225   yOffset = sy * s->pitch;
226
227   x = x1;
228   y = y1;
229
230   lineAddr = ((Uint8 *)s->pixels) + (y * s->pitch);
231   if (ax>ay)
232   {                      /* x dominant */
233     d = ay - (ax >> 1);
234     for (;;)
235     {
236       if (y >= 0 && y < MAX_Y && x >= 0 && x < MAX_X)
237         *((Uint16 *)(lineAddr + (x << 1))) = (Uint16)color;
238
239       if (x == x2)
240       {
241         return;
242       }
243       if (d>=0)
244       {
245         y += sy;
246         lineAddr += yOffset;
247         d -= ax;
248       }
249       x += sx;
250       d += ay;
251     }
252   }
253   else
254   {                      /* y dominant */
255     d = ax - (ay >> 1);
256     for (;;)
257     {
258       if (y >= 0 && y < MAX_Y && x >= 0 && x < MAX_X)
259         *((Uint16 *)(lineAddr + (x << 1))) = (Uint16)color;
260
261       if (y == y2)
262       {
263         return;
264       }
265       if (d>=0) 
266       {
267         x += sx;
268         d -= ay;
269       }
270       y += sy;
271       lineAddr += yOffset;
272       d += ax;
273     }
274   }
275 }
276
277 //----------------------------------------------------------
278
279 // Draw lines in 24 bit surfaces. 24 bit surfaces require
280 // special handling because the pixels don't fall on even
281 // address boundaries. Instead of being able to store a
282 // single byte, word, or long you have to store 3
283 // individual bytes. As a result 24 bit graphics is slower
284 // than the other pixel sizes.
285
286 static void line24(SDL_Surface *s, 
287                    int x1, int y1, 
288                    int x2, int y2, 
289                    Uint32 color)
290 {
291   int d;
292   int x;
293   int y;
294   int ax;
295   int ay;
296   int sx;
297   int sy;
298   int dx;
299   int dy;
300
301   Uint8 *lineAddr;
302   Sint32 yOffset;
303
304 #if (SDL_BYTEORDER == SDL_BIG_ENDIAN)
305   color <<= 8;
306 #endif
307
308   dx = x2 - x1;  
309   ax = abs(dx) << 1;  
310   sx = sign(dx);
311
312   dy = y2 - y1;  
313   ay = abs(dy) << 1;  
314   sy = sign(dy);
315   yOffset = sy * s->pitch;
316
317   x = x1;
318   y = y1;
319
320   lineAddr = ((Uint8 *)(s->pixels)) + (y * s->pitch);
321   if (ax>ay)
322   {                      /* x dominant */
323     d = ay - (ax >> 1);
324     for (;;)
325     {
326       Uint8 *p = (lineAddr + (x * 3));
327       if (y >= 0 && y < MAX_Y && x >= 0 && x < MAX_X)
328         memcpy(p, &color, 3);
329
330       if (x == x2)
331       {
332         return;
333       }
334       if (d>=0)
335       {
336         y += sy;
337         lineAddr += yOffset;
338         d -= ax;
339       }
340       x += sx;
341       d += ay;
342     }
343   }
344   else
345   {                      /* y dominant */
346     d = ax - (ay >> 1);
347     for (;;)
348     {
349       Uint8 *p = (lineAddr + (x * 3));
350       if (y >= 0 && y < MAX_Y && x >= 0 && x < MAX_X)
351         memcpy(p, &color, 3);
352
353       if (y == y2)
354       {
355         return;
356       }
357       if (d>=0) 
358       {
359         x += sx;
360         d -= ay;
361       }
362       y += sy;
363       lineAddr += yOffset;
364       d += ax;
365     }
366   }
367 }
368
369 //----------------------------------------------------------
370
371 // Draw lines in 32 bit surfaces. Note that this routine
372 // ignores alpha values. It writes them into the surface
373 // if they are included in the pixel, but does nothing
374 // else with them.
375
376 static void line32(SDL_Surface *s, 
377                    int x1, int y1, 
378                    int x2, int y2, 
379                    Uint32 color)
380 {
381   int d;
382   int x;
383   int y;
384   int ax;
385   int ay;
386   int sx;
387   int sy;
388   int dx;
389   int dy;
390
391   Uint8 *lineAddr;
392   Sint32 yOffset;
393
394   dx = x2 - x1;  
395   ax = abs(dx) << 1;  
396   sx = sign(dx);
397
398   dy = y2 - y1;  
399   ay = abs(dy) << 1;  
400   sy = sign(dy);
401   yOffset = sy * s->pitch;
402
403   x = x1;
404   y = y1;
405
406   lineAddr = ((Uint8 *)(s->pixels)) + (y * s->pitch);
407   if (ax>ay)
408   {                      /* x dominant */
409     d = ay - (ax >> 1);
410     for (;;)
411     {
412       if (y >= 0 && y < MAX_Y && x >= 0 && x < MAX_X)
413         *((Uint32 *)(lineAddr + (x << 2))) = (Uint32)color;
414
415       if (x == x2)
416       {
417         return;
418       }
419       if (d>=0)
420       {
421         y += sy;
422         lineAddr += yOffset;
423         d -= ax;
424       }
425       x += sx;
426       d += ay;
427     }
428   }
429   else
430   {                      /* y dominant */
431     d = ax - (ay >> 1);
432     for (;;)
433     {
434       if (y >= 0 && y < MAX_Y && x >= 0 && x < MAX_X)
435         *((Uint32 *)(lineAddr + (x << 2))) = (Uint32)color;
436
437       if (y == y2)
438       {
439         return;
440       }
441       if (d>=0) 
442       {
443         x += sx;
444         d -= ay;
445       }
446       y += sy;
447       lineAddr += yOffset;
448       d += ax;
449     }
450   }
451 }
452
453 //----------------------------------------------------------
454
455 // Examine the depth of a surface and select a line
456 // drawing routine optimized for the bytes/pixel of the
457 // surface.
458
459 static void line(SDL_Surface *s, 
460                  int x1, int y1, 
461                  int x2, int y2, 
462                  Uint32 color)
463 {
464   switch (s->format->BytesPerPixel)
465   {
466   case 1:
467     line8(s, x1, y1, x2, y2, color);
468     break;
469   case 2:
470     line16(s, x1, y1, x2, y2, color);
471     break;
472   case 3:
473     line24(s, x1, y1, x2, y2, color);
474     break;
475   case 4:
476     line32(s, x1, y1, x2, y2, color);
477     break;
478   }
479 }
480
481 #if 1
482 struct coord
483 {
484         long x;
485         long y;
486 };
487
488 struct ball
489 {
490         struct coord pos;
491         struct coord move;
492 };
493
494 struct line_segment
495 {
496         struct coord start, end;
497 };
498
499 static void thick_line(SDL_Surface *s, const struct line_segment *l)
500 {
501         struct line_segment adj;
502         int x, y;
503
504         /* Cheap hack */
505         for (x = -1; x < 2; x++) {
506                 for (y = -1; y < 2; y++) {
507                         adj.start.x = l->start.x + x;
508                         adj.end.x = l->end.x + x;
509                         adj.start.y = l->start.y + y;
510                         adj.end.y = l->end.y + y;
511
512                         line(s, adj.start.x, adj.start.y, adj.end.x, adj.end.y,
513                              0);
514                 }
515         }
516 }
517
518 static bool intersect(const struct coord *c1, const struct coord *c2,
519                       const struct line_segment *seg, struct coord *intersect)
520 {
521         return lines_intersect(c1->x, c1->y, c2->x, c2->y,
522                                seg->start.x, seg->start.y,
523                                seg->end.x, seg->end.y,
524                                &intersect->x, &intersect->y) == DO_INTERSECT;
525 }
526
527 static double dist(const struct coord *c1, const struct coord *c2)
528 {
529         long x = (c1->x - c2->x), y = (c1->y - c2->y);
530         return sqrt(x * x + y * y);
531 }
532
533 static unsigned rad_to_deg(double rad)
534 {
535         return ((unsigned)(rad / M_PI * 180) + 360) % 360;
536 }
537
538 static void bounce(struct ball *ball, const struct line_segment *line,
539                    struct coord *remainder)
540 {
541         double len, speed, lang, iang, oang;
542         struct coord isect, new;
543
544         new.x = ball->pos.x + ball->move.x;
545         new.y = ball->pos.y + ball->move.y;
546
547         /* How far were we supposed to move ball? */
548         len = sqrt(remainder->x * remainder->x + remainder->y * remainder->y);
549
550         /* How far is it to intersection? */
551         intersect(&ball->pos, &new, line, &isect);
552         len -= dist(&ball->pos, &isect);
553
554         /* Move ball to intersection. */
555         ball->pos = isect;
556
557         /* Outgoing angle = 2 * line angle - incident angle. */
558         lang = atan2(line->end.x - line->start.x, line->end.y - line->start.y);
559         iang = atan2(ball->move.x, ball->move.y);
560         oang = 2 * lang - iang, 2*M_PI;
561         printf("lang = %u, iang = %u, oang=%u\n", 
562                rad_to_deg(lang),
563                rad_to_deg(iang),
564                rad_to_deg(oang));
565
566         /* Set new direction for ball, at same speed */
567         speed = sqrt(ball->move.x * ball->move.x + ball->move.y * ball->move.y);
568         ball->move.x = round(sin(oang) * speed);
569         ball->move.y = round(cos(oang) * speed);
570
571         /* Set remainder. */
572         remainder->x = round(sin(oang) * len);
573         remainder->y = round(cos(oang) * len);
574         printf("len = %f, remainder = %li,%li\n", len, remainder->x, remainder->y);
575 }
576
577 static struct line_segment border[] = {
578         { { 0, 0, }, { MAX_X-1, 0 } },
579         { { MAX_X-1, 0, }, { MAX_X-1, MAX_Y-1 } },
580         { { MAX_X-1, MAX_Y-1, }, { 0, MAX_Y-1 } },
581         { { 0, MAX_Y-1, }, { 0, 0 } },
582 };
583
584 static inline float deg_to_rad(float degrees)
585 {
586         return degrees * M_PI / 180;
587 }
588
589 static SDL_Surface *sub_surface(SDL_Surface *screen, int w, int h)
590 {
591         return SDL_CreateRGBSurface(SDL_SWSURFACE, w, h,
592                                     screen->format->BitsPerPixel,
593                                     screen->format->Rmask,
594                                     screen->format->Gmask,
595                                     screen->format->Bmask,
596                                     screen->format->Amask);
597 }
598
599 static SDL_Surface *ball_surface(SDL_Surface *screen)
600 {
601         SDL_Surface *ball;
602
603         /* Just like the screen surface. */
604         ball = sub_surface(screen, 5, 5);
605
606         /* Lock the surface */
607         SDL_LockSurface(ball);
608
609         /* Black, white corners. */
610         memset(ball->pixels, 0x00, ball->pitch * 5);
611         line(ball, 0, 0, 0, 0, 0xFFFFFFFF);
612         line(ball, 4, 0, 4, 0, 0xFFFFFFFF);
613         line(ball, 0, 4, 0, 4, 0xFFFFFFFF);
614         line(ball, 4, 4, 4, 4, 0xFFFFFFFF);
615         SDL_UnlockSurface(ball);
616
617         return ball;
618 }
619
620 int main(int argc, char *argv[])
621 {
622         struct ball ball;
623         struct line_segment lines[ARRAY_SIZE(border) + 1];
624         static int isect_count = 0;
625         SDL_Surface *screen, *ballsur, *savesur = NULL;
626         Uint8  video_bpp;
627         Uint32 videoflags;
628         int i;
629         SDL_Event event;
630         struct line_segment *last_l = NULL;
631         SDL_Rect rect;
632
633         if (argc != 9)
634                 errx(1, "Usage: %s ballx bally ballangle ballspeed linestartx linestarty lineendx linendy\n"
635                      "   Where ballangle is 0 for north, 90 for east, etc\n",
636                         argv[0]);
637
638         ball.pos.x = atol(argv[1]);
639         ball.pos.y = atol(argv[2]);
640         ball.move.x = roundf(sin(deg_to_rad(atof(argv[3]))) * atol(argv[4]));
641         ball.move.y = roundf(cos(deg_to_rad(atof(argv[3]))) * atol(argv[4]));
642         printf("ball move = %li,%li\n", ball.move.x, ball.move.y);
643
644         memcpy(lines, border, sizeof(border));
645         lines[ARRAY_SIZE(border)].start.x = atof(argv[5]);
646         lines[ARRAY_SIZE(border)].start.y = atof(argv[6]);
647         lines[ARRAY_SIZE(border)].end.x = atof(argv[7]);
648         lines[ARRAY_SIZE(border)].end.y = atof(argv[8]);
649
650         /* Initialize SDL */
651         if ( SDL_Init(SDL_INIT_VIDEO) < 0 ) {
652                 fprintf(stderr, "Couldn't initialize SDL: %s\n",SDL_GetError());
653                 return(1);
654         }
655
656         video_bpp = 0;
657         videoflags = SDL_SWSURFACE;
658
659         /* Set 640x480 video mode */
660         if ( (screen=SDL_SetVideoMode(MAX_X,MAX_Y,video_bpp,videoflags)) == NULL ) {
661                 errx(1, "Couldn't set %dx%dx%d video mode: %s",
662                      MAX_X, MAX_Y,video_bpp, SDL_GetError());
663         }
664
665         /* Set the surface pixels and refresh! */
666         if ( SDL_LockSurface(screen) < 0 ) {
667                 errx(1, "Couldn't lock the display surface: %s",
668                      SDL_GetError());
669         }
670         /* White. */
671         memset(screen->pixels, 0xFF, screen->pitch * screen->h);
672
673         /* Draw lines. */
674         for (i = 0; i < ARRAY_SIZE(lines); i++)
675                 thick_line(screen, &lines[i]);
676
677         SDL_UnlockSurface(screen);
678         SDL_UpdateRect(screen, 0, 0, 0, 0);
679
680         ballsur = ball_surface(screen);
681
682         do {
683                 struct coord new, isect, move = ball.move;
684                 struct line_segment *best_l;
685                 unsigned i;
686                 double best_d;
687 #if 0
688                 SDL_Rect rect;
689
690                 rect.x = ball.pos.x - ballsur->w/2;
691                 rect.y = ball.pos.y - ballsur->h/2;
692                 rect.w = ballsur->w;
693                 rect.h = ballsur->h;
694 #endif
695
696         again:
697                 best_d = MAX_X + MAX_Y;
698                 best_l = NULL;
699                 new.x = ball.pos.x + move.x;
700                 new.y = ball.pos.y + move.y;
701
702                 printf("Ball at %li,%li (%li,%li)\n", ball.pos.x, ball.pos.y,
703                        move.x, move.y);
704
705                 for (i = 0; i < ARRAY_SIZE(lines); i++) {
706                         if (last_l == &lines[i])
707                                 continue;
708                         if (intersect(&ball.pos, &new, &lines[i], &isect)) {
709                                 double d;
710                                 d = dist(&ball.pos, &isect);
711                                 if (d < best_d) {
712                                         best_l = &lines[i];
713                                         best_d = d;
714                                 }
715                         }
716                 }
717                 if (best_l) {
718                         printf("Ball bouncing off (%lu,%lu %lu,%lu)!\n",
719                                best_l->start.x, best_l->start.y,
720                                best_l->end.x, best_l->end.y);
721                         bounce(&ball, best_l, &move);
722                         /* Don't hit the same line twice. */
723                         last_l = best_l;
724                         isect_count++;
725                         goto again;
726                 }
727
728                 /* Restore what was there before ball. */
729                 if (savesur) {
730                         SDL_BlitSurface(savesur, NULL, screen, &rect);
731                         SDL_UpdateRect(screen, rect.x, rect.y, rect.w, rect.h);
732                 } else {
733                         savesur = sub_surface(screen, ballsur->w, ballsur->h);
734                 }
735
736                 /* Save away image under new ball. */
737                 rect.w = ballsur->w;
738                 rect.h = ballsur->h;
739                 rect.x = new.x - ballsur->w/2;
740                 rect.y = new.y - ballsur->h/2;
741                 SDL_BlitSurface(screen, &rect, savesur, NULL);
742
743                 /* Draw new ball */
744                 SDL_BlitSurface(ballsur, NULL, screen, &rect);
745                 SDL_UpdateRect(screen, rect.x, rect.y, rect.w, rect.h);
746                 /* That SDL_BlitSurface can crop rect. */
747                 rect.x = new.x - ballsur->w/2;
748                 rect.y = new.y - ballsur->h/2;
749                 ball.pos = new;
750                 SDL_Delay(5);
751         } while (!SDL_PollEvent(&event) || event.type != SDL_QUIT);
752         SDL_Quit();
753         return 0;
754 }
755 #endif