git.hungrycats.org Git - xscreensaver/blob - hacks/glx/jigsaw.c

   1 /* xscreensaver, Copyright (c) 1997-2008 Jamie Zawinski <jwz@jwz.org>
   2  *
   3  * Permission to use, copy, modify, distribute, and sell this software and its
   4  * documentation for any purpose is hereby granted without fee, provided that
   5  * the above copyright notice appear in all copies and that both that
   6  * copyright notice and this permission notice appear in supporting
   7  * documentation.  No representations are made about the suitability of this
   8  * software for any purpose.  It is provided "as is" without express or
   9  * implied warranty.
  10  *
  11  * Written as an Xlib program some time in 1997.
  12  * Rewritten as an OpenGL program 24-Aug-2008.
  13  */
  14
  15 /*
  16   Currently, we do this:
  17
  18     - start pieces off screen and move them in.
  19     - when they land, they fill the puzzle grid with a shuffled
  20       puzzle (pieces are rotated, too).
  21     - swap random pairs of pieces until the puzzle is solved.
  22     - scatter the pieces off screen (resulting in black).
  23     - load new image and repeat.
  24
  25   Another idea would be to show the puzzle being solved the way
  26   a person would do it:
  27
  28     - start off with black screen.
  29     - assume knowledge of size of grid (position of corners).
  30     - find a corner piece, and place it.
  31     - while puzzle unsolved:
  32       - pick a random piece;
  33       - if it is the correct piece for any open edge, place it;
  34       - if it fits physically in any rotation at any open edge,
  35         place it, then toss it back (show the fake-out).
  36       - if it doesn't fit at all, don't animate it at all.
  37
  38    This would take a long time to solve, I think...
  39
  40    An even harder idea would involve building up completed "clumps"
  41    and sliding them around (a coral growth / accretion approach)
  42  */
  43
  44 #define DEF_SPEED        "1.0"
  45 #define DEF_COMPLEXITY   "1.0"
  46 #define DEF_RESOLUTION   "100"
  47 #define DEF_THICKNESS    "0.06"
  48 #define DEF_WOBBLE       "True"
  49 #define DEF_DEBUG        "False"
  50
  51 #define DEFAULTS  "*delay:              20000   \n" \
  52                   "*showFPS:            False   \n" \
  53                   "*wireframe:          False   \n" \
  54                   "*desktopGrabber:   xscreensaver-getimage -no-desktop %s\n" \
  55                   "*grabDesktopImages:  False   \n" \
  56                   "*chooseRandomImages: True    \n"
  57
  58
  59 # define refresh_jigsaw 0
  60 # define release_jigsaw 0
  61 #undef countof
  62 #define countof(x) (sizeof((x))/sizeof((*x)))
  63
  64 #include "xlockmore.h"
  65 #include "rotator.h"
  66 #include "gltrackball.h"
  67 #include "spline.h"
  68 #include "normals.h"
  69 #include "grab-ximage.h"
  70
  71 #undef BELLRAND
  72 #define BELLRAND(n) ((frand((n)) + frand((n)) + frand((n))) / 3)
  73
  74 #ifdef USE_GL /* whole file */
  75
  76 #define TOP    0
  77 #define RIGHT  1
  78 #define BOTTOM 2
  79 #define LEFT   3
  80
  81 #define IN    -1
  82 #define FLAT   0
  83 #define OUT    1
  84
  85 typedef struct jigsaw_configuration jigsaw_configuration;
  86
  87 typedef struct {
  88   double x,y,z,r;       /* position and Z rotation (in degrees) */
  89 } XYZR;
  90
  91
  92 typedef struct {
  93   jigsaw_configuration *jc;
  94   int edge[4];
  95   GLuint dlist;
  96   int polys;
  97
  98   XYZR home;            /* correct position in puzzle */
  99   XYZR current;         /* where it is right now */
 100   XYZR from, to;        /* in transit from A to B */
 101   double tick;          /* 0-1.0, how far from A to B */
 102   double arc_height;    /* height of apex of curved path from A to B */
 103   double tilt, max_tilt;
 104
 105 } puzzle_piece;
 106
 107
 108 struct jigsaw_configuration {
 109   GLXContext *glx_context;
 110   trackball_state *trackball;
 111   rotator *rot;
 112   Bool button_down_p;
 113
 114   int puzzle_width;
 115   int puzzle_height;
 116   puzzle_piece *puzzle;
 117
 118   enum { PUZZLE_LOADING,
 119          PUZZLE_UNSCATTER,
 120          PUZZLE_SOLVE,
 121          PUZZLE_SCATTER } state;
 122   double pausing;
 123   double tick_speed;
 124
 125   GLuint texid;
 126   GLfloat tex_x, tex_y, tex_width, tex_height, aspect;
 127
 128   GLuint line_thickness;
 129 };
 130
 131 static jigsaw_configuration *sps = NULL;
 132
 133 static GLfloat speed;
 134 static GLfloat complexity_arg;
 135 static int resolution_arg;
 136 static GLfloat thickness_arg;
 137 static Bool wobble_p;
 138 static Bool debug_p;
 139
 140 static XrmOptionDescRec opts[] = {
 141   { "-speed",      ".speed",       XrmoptionSepArg, 0 },
 142   { "-complexity", ".complexity",  XrmoptionSepArg, 0 },
 143   { "-resolution", ".resolution",  XrmoptionSepArg, 0 },
 144   { "-thickness",  ".thickness",   XrmoptionSepArg, 0 },
 145   { "-wobble",     ".wobble",      XrmoptionNoArg, "True" },
 146   { "+wobble",     ".wobble",      XrmoptionNoArg, "False" },
 147   { "-debug",      ".debug",       XrmoptionNoArg, "True" },
 148 };
 149
 150 static argtype vars[] = {
 151   {&speed,          "speed",       "Speed",       DEF_SPEED,      t_Float},
 152   {&complexity_arg, "complexity",  "Complexity",  DEF_COMPLEXITY, t_Float},
 153   {&resolution_arg, "resolution",  "Resolution",  DEF_RESOLUTION, t_Int},
 154   {&thickness_arg,  "thickness",   "Thickness",   DEF_THICKNESS,  t_Float},
 155   {&wobble_p,       "wobble",      "Wobble",      DEF_WOBBLE,     t_Bool},
 156   {&debug_p,        "debug",       "Debug",       DEF_DEBUG,      t_Bool},
 157 };
 158
 159 ENTRYPOINT ModeSpecOpt jigsaw_opts = {countof(opts), opts, countof(vars), vars, NULL};
 160
 161
 162 /* Returns a spline describing one edge of a puzzle piece of the given length.
 163  */
 164 static spline *
 165 make_puzzle_curve (int pixels)
 166 {
 167   double x0 = 0.0000, y0 =  0.0000;
 168   double x1 = 0.3333, y1 =  0.1000;
 169   double x2 = 0.4333, y2 =  0.0333;
 170   double x3 = 0.4666, y3 = -0.0666;
 171   double x4 = 0.3333, y4 = -0.1666;
 172   double x5 = 0.3666, y5 = -0.2900;
 173   double x6 = 0.5000, y6 = -0.3333;
 174
 175   spline *s = make_spline(20);
 176   s->n_controls = 0;
 177
 178 # define PT(x,y) \
 179     s->control_x[s->n_controls] = pixels * (x); \
 180     s->control_y[s->n_controls] = pixels * (y); \
 181     s->n_controls++
 182   PT (  x0, y0);
 183   PT (  x1, y1);
 184   PT (  x2, y2);
 185   PT (  x3, y3);
 186   PT (  x4, y4);
 187   PT (  x5, y5);
 188   PT (  x6, y6);
 189   PT (1-x5, y5);
 190   PT (1-x4, y4);
 191   PT (1-x3, y3);
 192   PT (1-x2, y2);
 193   PT (1-x1, y1);
 194   PT (1-x0, y0);
 195 # undef PT
 196
 197   compute_spline (s);
 198   return s;
 199 }
 200
 201
 202 static void
 203 tess_error_cb (GLenum errorCode)
 204 {
 205   fprintf (stderr, "%s: tesselation error: %s\n",
 206            progname, gluErrorString(errorCode));
 207   exit (0);
 208 }
 209
 210
 211 static void
 212 tess_combine_cb (GLdouble coords[3], GLdouble *d[4], GLfloat w[4],
 213                  GLdouble **dataOut)
 214 {
 215   GLdouble *new = (GLdouble *) malloc (3 * sizeof(*new));
 216   new[0] = coords[0];
 217   new[1] = coords[1];
 218   new[2] = coords[2];
 219   *dataOut = new;
 220 }
 221
 222
 223 static void
 224 tess_vertex_cb (void *vertex_data, void *closure)
 225 {
 226   puzzle_piece *p = (puzzle_piece *) closure;
 227   GLdouble *v = (GLdouble *) vertex_data;
 228   GLdouble x = v[0];
 229   GLdouble y = v[1];
 230   GLdouble z = v[2];
 231
 232   if (p)
 233     {
 234       GLfloat pw = p->jc->puzzle_width;
 235       GLfloat ph = p->jc->puzzle_height;
 236
 237       GLfloat xx = x / (GLfloat) resolution_arg;  /* 0-1 from piece origin */
 238       GLfloat yy = y / (GLfloat) resolution_arg;
 239       GLdouble tx = (p->home.x + xx)      / pw;   /* 0-1 from puzzle origin */
 240       GLdouble ty = (ph - p->home.y - yy) / ph;
 241
 242       tx = p->jc->tex_x + (tx * p->jc->tex_width);
 243       ty = p->jc->tex_y + (ty * p->jc->tex_height);
 244
 245       glTexCoord2d (tx, ty);
 246     }
 247
 248   glVertex3d (x, y, z);
 249 }
 250
 251
 252
 253 /* Draws a puzzle piece.  The top/right/bottom/left_type args
 254    indicate the direction the tabs point: 1 for out, -1 for in, 0 for flat.
 255  */
 256 static int
 257 draw_piece (jigsaw_configuration *jc, puzzle_piece *p,
 258             int resolution, GLfloat thickness,
 259             int top_type, int right_type,
 260             int bottom_type, int left_type,
 261             Bool wire)
 262 {
 263   spline *s = make_puzzle_curve (resolution);
 264   GLdouble *pts = (GLdouble *) malloc (s->n_points * 4 * 3 * sizeof(*pts));
 265   int polys = 0;
 266   int i, o;
 267   GLdouble z = resolution * thickness;
 268
 269   o = 0;
 270   if (top_type == 0) {
 271     pts[o++] = 0;
 272     pts[o++] = 0;
 273     pts[o++] = z;
 274
 275     pts[o++] = resolution;
 276     pts[o++] = 0;
 277     pts[o++] = z;
 278   } else {
 279     for (i = 0; i < s->n_points; i++) {
 280       pts[o++] = s->points[i].x;
 281       pts[o++] = s->points[i].y * top_type;
 282       pts[o++] = z;
 283     }
 284   }
 285
 286   if (right_type == 0) {
 287     pts[o++] = resolution;
 288     pts[o++] = resolution;
 289     pts[o++] = z;
 290   } else {
 291     for (i = 1; i < s->n_points; i++) {
 292       pts[o++] = resolution + s->points[i].y * (-right_type);
 293       pts[o++] = s->points[i].x;
 294       pts[o++] = z;
 295     }
 296   }
 297
 298   if (bottom_type == 0) {
 299     pts[o++] = 0;
 300     pts[o++] = resolution;
 301     pts[o++] = z;
 302   } else {
 303     for (i = 1; i < s->n_points; i++) {
 304       pts[o++] = s->points[s->n_points-i-1].x;
 305       pts[o++] = resolution + s->points[s->n_points-i-1].y * (-bottom_type);
 306       pts[o++] = z;
 307     }
 308   }
 309
 310   if (left_type == 0) {
 311     pts[o++] = 0;
 312     pts[o++] = 0;
 313     pts[o++] = z;
 314   } else {
 315     for (i = 1; i < s->n_points; i++) {
 316       pts[o++] = s->points[s->n_points-i-1].y * left_type;
 317       pts[o++] = s->points[s->n_points-i-1].x;
 318       pts[o++] = z;
 319     }
 320   }
 321
 322   free_spline (s);
 323
 324   { GLfloat s = 1.0 / resolution; glScalef (s, s, s); }
 325
 326   glPolygonMode (GL_FRONT_AND_BACK, wire ? GL_LINE : GL_FILL);
 327
 328   if (wire)
 329     {
 330       glDisable (GL_TEXTURE_2D);
 331       glDisable (GL_BLEND);
 332       glDisable (GL_LIGHTING);
 333     }
 334   else
 335     {
 336 # ifndef  _GLUfuncptr
 337 #  define _GLUfuncptr void(*)(void)
 338 # endif
 339       GLUtesselator *tess = gluNewTess();
 340       gluTessCallback(tess, GLU_TESS_BEGIN,      (_GLUfuncptr)glBegin);
 341       gluTessCallback(tess, GLU_TESS_VERTEX_DATA,(_GLUfuncptr)tess_vertex_cb);
 342       gluTessCallback(tess, GLU_TESS_END,        (_GLUfuncptr)glEnd);
 343       gluTessCallback(tess, GLU_TESS_COMBINE,    (_GLUfuncptr)tess_combine_cb);
 344       gluTessCallback(tess, GLU_TESS_ERROR,      (_GLUfuncptr)tess_error_cb);
 345
 346       /* front face */
 347       glEnable (GL_TEXTURE_2D);
 348       glEnable (GL_BLEND);
 349       glEnable (GL_LIGHTING);
 350       glBindTexture(GL_TEXTURE_2D, jc->texid);
 351       glFrontFace (GL_CCW);
 352       glNormal3f (0, 0, 1);
 353       gluTessBeginPolygon (tess, p);
 354       gluTessBeginContour (tess);
 355       for (i = 0; i < o; i += 3)
 356         {
 357           GLdouble *p = pts + i;
 358           gluTessVertex (tess, p, p);
 359           polys++;  /* not quite right but close */
 360         }
 361       gluTessEndContour(tess);
 362       gluTessEndPolygon(tess);
 363
 364       /* back face */
 365       glDisable (GL_TEXTURE_2D);
 366       glFrontFace (GL_CW);
 367       glNormal3f (0, 0, -1);
 368       gluTessBeginPolygon (tess, 0);
 369       gluTessBeginContour (tess);
 370       for (i = 0; i < o; i += 3)
 371         {
 372           GLdouble *p = pts + i;
 373           p[2] = -p[2];
 374           gluTessVertex (tess, p, p);
 375           polys++;  /* not quite right but close */
 376         }
 377       gluTessEndContour(tess);
 378       gluTessEndPolygon(tess);
 379       gluDeleteTess(tess);
 380     }
 381
 382   /* side faces */
 383   glFrontFace (GL_CCW);
 384   glBegin (wire ? GL_LINES : GL_QUAD_STRIP);
 385   for (i = 0; i < o; i += 3)
 386     {
 387       int j = (i+o-3) % o;
 388       int k = (i+3)   % o;
 389       GLdouble *p  = pts + i;
 390       GLdouble *pj = pts + j;
 391       GLdouble *pk = pts + k;
 392
 393       do_normal  (pj[0], pj[1], -pj[2],
 394                   pj[0], pj[1],  pj[2],
 395                   pk[0], pk[1],  pk[2]);
 396
 397       glVertex3f (p[0], p[1], -p[2]);
 398       glVertex3f (p[0], p[1],  p[2]);
 399       polys++;
 400     }
 401   glEnd();
 402
 403   if (! wire)
 404     glColor3f (0.3, 0.3, 0.3);
 405
 406   glDisable (GL_TEXTURE_2D);
 407   glDisable (GL_LIGHTING);
 408   glLineWidth (jc->line_thickness);
 409
 410   glBegin (GL_LINE_LOOP);
 411   for (i = 0; i < o; i += 3)
 412     glVertex3f (pts[i], pts[i+1], pts[i+2]);
 413   glEnd();
 414   polys += o/3;
 415
 416   glBegin (GL_LINE_LOOP);
 417   for (i = 0; i < o; i += 3)
 418     glVertex3f (pts[i], pts[i+1], -pts[i+2]);
 419   glEnd();
 420   polys += o/3;
 421
 422   free (pts);
 423
 424   return polys;
 425 }
 426
 427
 428 static void
 429 free_puzzle_grid (jigsaw_configuration *jc)
 430 {
 431   int i;
 432   for (i = 0; i < jc->puzzle_width * jc->puzzle_height; i++)
 433     glDeleteLists (jc->puzzle[i].dlist,  1);
 434   free (jc->puzzle);
 435   jc->puzzle = 0;
 436   jc->puzzle_width = 0;
 437   jc->puzzle_height = 0;
 438 }
 439
 440
 441 static void
 442 make_puzzle_grid (ModeInfo *mi)
 443 {
 444   jigsaw_configuration *jc = &sps[MI_SCREEN(mi)];
 445   int wire = MI_IS_WIREFRAME(mi);
 446   int x, y;
 447   GLfloat size = (8 + (random() % 8)) * complexity_arg;
 448
 449   if (jc->puzzle)
 450     free_puzzle_grid (jc);
 451
 452   if (wire)
 453     jc->aspect = MI_WIDTH(mi) / (float) MI_HEIGHT(mi);
 454
 455   if (jc->aspect >= 1.0)
 456     {
 457       jc->puzzle_width  = size;
 458       jc->puzzle_height = (size + 0.5) / jc->aspect;
 459     }
 460   else
 461     {
 462       jc->puzzle_width  = (size + 0.5) * jc->aspect;
 463       jc->puzzle_height = size;
 464     }
 465
 466   if (jc->puzzle_width  < 1) jc->puzzle_width  = 1;
 467   if (jc->puzzle_height < 1) jc->puzzle_height = 1;
 468
 469   if (debug_p)
 470     fprintf (stderr, "%s: grid  %4d x %-4d               (%.2f)\n", progname,
 471              jc->puzzle_width, jc->puzzle_height,
 472              ((float) jc->puzzle_width / jc->puzzle_height));
 473
 474   jc->puzzle = (puzzle_piece *)
 475     calloc (jc->puzzle_width * (jc->puzzle_height+1), sizeof(*jc->puzzle));
 476
 477   /* Randomize the right and bottom edge of each piece.
 478      Match the left edge of the piece to the right to our right edge.
 479      Match the top edge of the piece to the bottom to our bottom edge.
 480    */
 481   for (y = 0; y < jc->puzzle_height; y++)
 482     for (x = 0; x < jc->puzzle_width; x++)
 483       {
 484         puzzle_piece *p = &jc->puzzle [y     * jc->puzzle_width + x];
 485         puzzle_piece *r = &jc->puzzle [y     * jc->puzzle_width + x+1];
 486         puzzle_piece *b = &jc->puzzle [(y+1) * jc->puzzle_width + x];
 487         p->edge[RIGHT]  = (random() & 1) ? IN : OUT;
 488         p->edge[BOTTOM] = (random() & 1) ? IN : OUT;
 489         r->edge[LEFT]   = p->edge[RIGHT]  == IN ? OUT : IN;
 490         b->edge[TOP]    = p->edge[BOTTOM] == IN ? OUT : IN;
 491       }
 492
 493   /* tell each piece where it belongs. */
 494   for (y = 0; y < jc->puzzle_height; y++)
 495     for (x = 0; x < jc->puzzle_width; x++)
 496       {
 497         puzzle_piece *p = &jc->puzzle [y * jc->puzzle_width + x];
 498         p->jc = jc;
 499         p->home.x = x;
 500         p->home.y = y;
 501         p->current = p->home;
 502
 503         /* make sure the outer border is flat */
 504         if (p->home.x == 0)  p->edge[LEFT] = FLAT;
 505         if (p->home.y == 0)  p->edge[TOP]  = FLAT;
 506         if (p->home.x == jc->puzzle_width-1)  p->edge[RIGHT]  = FLAT;
 507         if (p->home.y == jc->puzzle_height-1) p->edge[BOTTOM] = FLAT;
 508
 509         /* generate the polygons */
 510         p->dlist = glGenLists (1);
 511         check_gl_error ("generating lists");
 512         if (p->dlist <= 0) abort();
 513
 514         glNewList (p->dlist, GL_COMPILE);
 515         p->polys += draw_piece (jc, p,
 516                                 resolution_arg, thickness_arg,
 517                                 p->edge[TOP], p->edge[RIGHT],
 518                                 p->edge[BOTTOM], p->edge[LEFT],
 519                                 wire);
 520         glEndList();
 521       }
 522 }
 523
 524
 525 static void shuffle_grid (ModeInfo *mi);
 526
 527
 528 static void
 529 image_loaded_cb (const char *filename, XRectangle *geometry,
 530                  int image_width, int image_height,
 531                  int texture_width, int texture_height,
 532                  void *closure)
 533 {
 534   ModeInfo *mi = (ModeInfo *) closure;
 535   jigsaw_configuration *jc = &sps[MI_SCREEN(mi)];
 536
 537   jc->tex_x      = geometry->x      / (float) texture_width;
 538   jc->tex_y      = geometry->y      / (float) texture_height;
 539   jc->tex_width  = geometry->width  / (float) texture_width;
 540   jc->tex_height = geometry->height / (float) texture_height;
 541   jc->aspect     = geometry->width  / (float) geometry->height;
 542
 543   if (debug_p)
 544     {
 545       fprintf (stderr, "%s: image %s\n", progname,
 546                (filename ? filename : "(null)"));
 547       fprintf (stderr, "%s: image %4d x %-4d + %4d + %-4d (%.2f)\n", progname,
 548                geometry->width, geometry->height, geometry->x, geometry->y,
 549                (float) geometry->width / geometry->height);
 550       fprintf (stderr, "%s: tex   %4d x %-4d\n", progname,
 551                texture_width, texture_height);
 552       fprintf (stderr, "%s: tex   %4.2f x %4.2f + %4.2f + %4.2f (%.2f)\n",
 553                progname,
 554                jc->tex_width, jc->tex_height, jc->tex_x, jc->tex_y,
 555                (jc->tex_width / jc->tex_height) *
 556                (texture_width / texture_height));
 557     }
 558
 559   glTexParameteri (GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_LINEAR);
 560   glTexParameteri (GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR);
 561   glTexParameteri (GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_CLAMP);
 562   glTexParameteri (GL_TEXTURE_2D, GL_TEXTURE_WRAP_T, GL_CLAMP);
 563
 564   make_puzzle_grid (mi);
 565 }
 566
 567
 568 static void
 569 load_image (ModeInfo *mi)
 570 {
 571   jigsaw_configuration *jc = &sps[MI_SCREEN(mi)];
 572   load_texture_async (mi->xgwa.screen, mi->window,
 573                       *jc->glx_context, 0, 0,
 574                       False, jc->texid,
 575                       image_loaded_cb, mi);
 576 }
 577
 578
 579 /* Whether the two pieces are the same shape, when the second piece
 580    is rotated by the given degrees.
 581  */
 582 static Bool
 583 same_shape (puzzle_piece *p0, puzzle_piece *p1, int rotated_by)
 584 {
 585   switch (rotated_by)
 586     {
 587     case 0:
 588       return (p0->edge[0] == p1->edge[0] &&
 589               p0->edge[1] == p1->edge[1] &&
 590               p0->edge[2] == p1->edge[2] &&
 591               p0->edge[3] == p1->edge[3]);
 592     case 90:
 593       return (p0->edge[0] == p1->edge[1] &&
 594               p0->edge[1] == p1->edge[2] &&
 595               p0->edge[2] == p1->edge[3] &&
 596               p0->edge[3] == p1->edge[0]);
 597     case 180:
 598       return (p0->edge[0] == p1->edge[2] &&
 599               p0->edge[1] == p1->edge[3] &&
 600               p0->edge[2] == p1->edge[0] &&
 601               p0->edge[3] == p1->edge[1]);
 602     case 270:
 603       return (p0->edge[0] == p1->edge[3] &&
 604               p0->edge[1] == p1->edge[0] &&
 605               p0->edge[2] == p1->edge[1] &&
 606               p0->edge[3] == p1->edge[2]);
 607     default:
 608       abort();
 609     }
 610 }
 611
 612
 613 /* Returns the proper rotation for the piece at the given position.
 614  */
 615 static int
 616 proper_rotation (jigsaw_configuration *jc, puzzle_piece *p,
 617                  double x, double y)
 618 {
 619   puzzle_piece *p1;
 620   int cx = x;
 621   int cy = y;
 622   if (cx != x) abort();  /* must be in integral position! */
 623   if (cy != y) abort();
 624   p1 = &jc->puzzle [cy * jc->puzzle_width + cx];
 625   if (same_shape (p, p1, 0))   return 0;
 626   if (same_shape (p, p1, 90))  return 90;
 627   if (same_shape (p, p1, 180)) return 180;
 628   if (same_shape (p, p1, 270)) return 270;
 629   abort();              /* these two pieces don't match in any rotation! */
 630 }
 631
 632
 633 /* Returns the piece currently at the given position.
 634  */
 635 static puzzle_piece *
 636 piece_at (jigsaw_configuration *jc, double x, double y)
 637 {
 638   int npieces = jc->puzzle_width * jc->puzzle_height;
 639   int i;
 640   int cx = x;
 641   int cy = y;
 642   if (cx != x) abort();  /* must be in integral position! */
 643   if (cy != y) abort();
 644
 645   for (i = 0; i < npieces; i++)
 646     {
 647       puzzle_piece *p = &jc->puzzle [i];
 648       if (p->current.x == cx &&
 649           p->current.y == cy)
 650         return p;
 651     }
 652   abort();   /* no piece at that position? */
 653 }
 654
 655
 656 static void
 657 shuffle_grid (ModeInfo *mi)
 658 {
 659   jigsaw_configuration *jc = &sps[MI_SCREEN(mi)];
 660   int max_tries = jc->puzzle_width * jc->puzzle_height;
 661   int npieces = jc->puzzle_width * jc->puzzle_height;
 662   int i;
 663
 664   for (i = 0; i < npieces; i++)
 665     {
 666       puzzle_piece *p0 = &jc->puzzle [i];
 667       puzzle_piece *p1 = 0;
 668       int k;
 669
 670       for (k = 0; k < max_tries; k++)
 671         {
 672           p1 = &jc->puzzle [random() % npieces];
 673           if (same_shape (p0, p1, 0))   break;
 674           if (same_shape (p0, p1, 90))  break;
 675           if (same_shape (p0, p1, 180)) break;
 676           if (same_shape (p0, p1, 270)) break;
 677           p1 = 0;  /* mismatch */
 678         }
 679       if (p1 && p0 != p1)
 680         {
 681           XYZR s;
 682           s = p0->current; p0->current = p1->current; p1->current = s;
 683           p0->current.r =
 684             proper_rotation (jc, p0, p0->current.x, p0->current.y);
 685           p1->current.r =
 686             proper_rotation (jc, p1, p1->current.x, p1->current.y);
 687         }
 688     }
 689 }
 690
 691
 692 /* We tend to accumulate floating point errors, e.g., z being 0.000001
 693    after a move.  This makes sure float values that should be integral are.
 694  */
 695 static void
 696 smooth_grid (ModeInfo *mi)
 697 {
 698   jigsaw_configuration *jc = &sps[MI_SCREEN(mi)];
 699   int npieces = jc->puzzle_width * jc->puzzle_height;
 700   int i;
 701
 702   for (i = 0; i < npieces; i++)
 703     {
 704       puzzle_piece *p = &jc->puzzle [i];
 705 # define SMOOTH(P) \
 706         P.x = (int) (P.x + 0.5);                  \
 707         P.y = (int) (P.y + 0.5);                  \
 708         P.z = (int) (P.z + 0.5);                  \
 709         P.r = (int) (P.r + 0.5)
 710       SMOOTH(p->home);
 711       SMOOTH(p->current);
 712       SMOOTH(p->from);
 713       SMOOTH(p->to);
 714       if (p->tick <= 0.0001) p->tick = 0.0;
 715       if (p->tick >= 0.9999) p->tick = 1.0;
 716     }
 717 }
 718
 719
 720 static void
 721 begin_scatter (ModeInfo *mi, Bool unscatter_p)
 722 {
 723   jigsaw_configuration *jc = &sps[MI_SCREEN(mi)];
 724   int npieces = jc->puzzle_width * jc->puzzle_height;
 725   int i;
 726   XYZR ctr = { 0, };
 727   ctr.x = jc->puzzle_width  / 2;
 728   ctr.y = jc->puzzle_height / 2;
 729
 730   for (i = 0; i < npieces; i++)
 731     {
 732       puzzle_piece *p = &jc->puzzle [i];
 733       XYZ a;
 734       double d, r, th;
 735       p->tick = -frand(1.0);
 736       p->from = p->current;
 737
 738       a.x = p->from.x - ctr.x;  /* position relative to center */
 739       a.y = p->from.y - ctr.y;
 740
 741       r = sqrt (a.x*a.x + a.y*a.y);
 742       th = atan2 (a.x, a.y);
 743
 744       d = MAX (jc->puzzle_width, jc->puzzle_height) * 2;
 745       r = r*r + d;
 746
 747       p->to.x = ctr.x + (r * sin (th));
 748       p->to.y = ctr.y + (r * cos (th));
 749       p->to.z = p->from.z;
 750       p->to.r = ((int) p->from.r + (random() % 180)) % 360;
 751       p->arc_height = frand(10.0);
 752
 753       if (unscatter_p)
 754         {
 755           XYZR s = p->to; p->to = p->from; p->from = s;
 756           p->current = p->from;
 757         }
 758     }
 759 }
 760
 761
 762 static Bool
 763 solved_p (ModeInfo *mi)
 764 {
 765   jigsaw_configuration *jc = &sps[MI_SCREEN(mi)];
 766   int npieces = jc->puzzle_width * jc->puzzle_height;
 767   int i;
 768
 769   for (i = 0; i < npieces; i++)
 770     {
 771       puzzle_piece *p = &jc->puzzle [i];
 772       if (p->current.x != p->home.x ||
 773           p->current.y != p->home.y ||
 774           p->current.z != p->home.z)
 775         return False;
 776     }
 777   return True;
 778 }
 779
 780
 781 static void
 782 move_one_piece (ModeInfo *mi)
 783 {
 784   jigsaw_configuration *jc = &sps[MI_SCREEN(mi)];
 785   int npieces = jc->puzzle_width * jc->puzzle_height;
 786   int i;
 787
 788   for (i = 0; i < npieces * 100; i++)  /* shouldn't take that long */
 789     {
 790       int i = random() % npieces;
 791       puzzle_piece *p0 = &jc->puzzle [i];
 792       puzzle_piece *p1;
 793
 794       if (p0->current.x == p0->home.x &&
 795           p0->current.y == p0->home.y &&
 796           p0->current.z == p0->home.z)
 797         continue;               /* piece already solved - try again */
 798
 799       /* swap with the piece occupying p0's home cell. */
 800       p1 = piece_at (jc, p0->home.x, p0->home.y);
 801
 802       if (p0 == p1) abort();    /* should have caught this above */
 803
 804       p0->tick = 0;
 805       p0->from = p0->current;
 806       p0->to   = p1->current;
 807       p0->to.r = proper_rotation (jc, p0, p0->to.x, p0->to.y);
 808
 809       p1->tick = 0;
 810       p1->from = p1->current;
 811       p1->to   = p0->current;
 812       p1->to.r = proper_rotation (jc, p1, p1->to.x, p1->to.y);
 813
 814       p0->arc_height = 0.5 + frand(3.0);
 815       p1->arc_height = 1.0 + frand(3.0);
 816
 817 # define RTILT(V) \
 818          V = 90 - BELLRAND(180);       \
 819          if (! (random() % 5)) V *= 2; \
 820          if (! (random() % 5)) V *= 2; \
 821          if (! (random() % 5)) V *= 2
 822       RTILT (p0->max_tilt);
 823       RTILT (p1->max_tilt);
 824 # undef RTILT
 825
 826       if (debug_p)
 827         fprintf (stderr, "%s: swapping %2d,%-2d with %2d,%d\n", progname,
 828                  (int) p0->from.x, (int) p0->from.y,
 829                  (int) p1->from.x, (int) p1->from.y);
 830       return;
 831     }
 832
 833   abort();  /* infinite loop! */
 834 }
 835
 836
 837 static Bool
 838 anim_tick (ModeInfo *mi)
 839 {
 840   jigsaw_configuration *jc = &sps[MI_SCREEN(mi)];
 841   int npieces = jc->puzzle_width * jc->puzzle_height;
 842   int i;
 843   Bool finished_p = True;
 844
 845   if (jc->pausing > 0)
 846     {
 847       jc->pausing -= jc->tick_speed * speed;
 848       if (debug_p && jc->pausing <= 0)
 849         fprintf (stderr, "%s:   (done pausing)\n", progname);
 850       return False;
 851     }
 852
 853   for (i = 0; i < npieces; i++)
 854     {
 855       puzzle_piece *p = &jc->puzzle [i];
 856       double tt;
 857
 858       if (p->tick >= 1.0) continue;     /* this piece is done */
 859       finished_p = False;               /* not done */
 860
 861       p->tick += jc->tick_speed * speed;
 862       if (p->tick > 1.0) p->tick = 1.0;
 863
 864       if (p->tick < 0.0) continue;      /* not yet started */
 865
 866       tt = 1 - sin (M_PI/2 - p->tick * M_PI/2);
 867
 868       p->current.x = p->from.x + ((p->to.x - p->from.x) * tt);
 869       p->current.y = p->from.y + ((p->to.y - p->from.y) * tt);
 870       p->current.z = p->from.z + ((p->to.z - p->from.z) * tt);
 871       p->current.r = p->from.r + ((p->to.r - p->from.r) * tt);
 872
 873       p->current.z += p->arc_height * sin (p->tick * M_PI);
 874
 875       p->tilt = p->max_tilt * sin (p->tick * M_PI);
 876
 877     }
 878
 879   return finished_p;
 880 }
 881
 882
 883 static void
 884 animate (ModeInfo *mi)
 885 {
 886   jigsaw_configuration *jc = &sps[MI_SCREEN(mi)];
 887   double slow = 0.01;
 888   double fast = 0.04;
 889
 890   if (jc->button_down_p) return;
 891
 892   switch (jc->state)
 893     {
 894     case PUZZLE_LOADING:
 895       if (!jc->puzzle) break;   /* still loading */
 896       jc->tick_speed = slow;
 897       shuffle_grid (mi);
 898       smooth_grid (mi);
 899       begin_scatter (mi, True);
 900       jc->pausing = 0;
 901       jc->state = PUZZLE_UNSCATTER;
 902       if (debug_p) fprintf (stderr, "%s: unscattering\n", progname);
 903       break;
 904
 905     case PUZZLE_UNSCATTER:
 906       jc->tick_speed = slow;
 907       if (anim_tick (mi))
 908         {
 909           smooth_grid (mi);
 910           jc->pausing = 1.0;
 911           jc->state = PUZZLE_SOLVE;
 912           if (debug_p) fprintf (stderr, "%s: solving\n", progname);
 913         }
 914       break;
 915
 916     case PUZZLE_SOLVE:
 917       jc->tick_speed = fast;
 918       if (anim_tick (mi))
 919         {
 920           smooth_grid (mi);
 921           if (solved_p (mi))
 922             {
 923               if (debug_p) fprintf (stderr, "%s: solved!\n", progname);
 924               begin_scatter (mi, False);
 925               jc->state = PUZZLE_SCATTER;
 926               jc->pausing = 3.0;
 927               if (debug_p) fprintf (stderr, "%s: scattering\n", progname);
 928             }
 929           else
 930             {
 931               move_one_piece (mi);
 932               jc->pausing = 0.3;
 933             }
 934         }
 935       break;
 936
 937     case PUZZLE_SCATTER:
 938       jc->tick_speed = slow;
 939       if (anim_tick (mi))
 940         {
 941           free_puzzle_grid (jc);
 942           load_image (mi);
 943           jc->state = PUZZLE_LOADING;
 944           jc->pausing = 1.0;
 945           if (debug_p) fprintf (stderr, "%s: loading\n", progname);
 946         }
 947       break;
 948
 949     default:
 950       abort();
 951     }
 952 }
 953
 954
 955 /* Window management, etc
 956  */
 957 ENTRYPOINT void
 958 reshape_jigsaw (ModeInfo *mi, int width, int height)
 959 {
 960   jigsaw_configuration *jc = &sps[MI_SCREEN(mi)];
 961   GLfloat h = (GLfloat) height / (GLfloat) width;
 962
 963   glViewport (0, 0, (GLint) width, (GLint) height);
 964
 965   glMatrixMode(GL_PROJECTION);
 966   glLoadIdentity();
 967   gluPerspective (30.0, 1/h, 1.0, 100.0);
 968
 969   glMatrixMode(GL_MODELVIEW);
 970   glLoadIdentity();
 971   gluLookAt( 0.0, 0.0, 30.0,
 972              0.0, 0.0, 0.0,
 973              0.0, 1.0, 0.0);
 974
 975   glClear(GL_COLOR_BUFFER_BIT);
 976
 977   jc->line_thickness = (MI_IS_WIREFRAME (mi) ? 1 : MAX (1, height / 300.0));
 978 }
 979
 980
 981 ENTRYPOINT Bool
 982 jigsaw_handle_event (ModeInfo *mi, XEvent *event)
 983 {
 984   jigsaw_configuration *jc = &sps[MI_SCREEN(mi)];
 985
 986   if (event->xany.type == ButtonPress &&
 987       event->xbutton.button == Button1)
 988     {
 989       jc->button_down_p = True;
 990       gltrackball_start (jc->trackball,
 991                          event->xbutton.x, event->xbutton.y,
 992                          MI_WIDTH (mi), MI_HEIGHT (mi));
 993       return True;
 994     }
 995   else if (event->xany.type == ButtonRelease &&
 996            event->xbutton.button == Button1)
 997     {
 998       jc->button_down_p = False;
 999       return True;
1000     }
1001   else if (event->xany.type == ButtonPress &&
1002            (event->xbutton.button == Button4 ||
1003             event->xbutton.button == Button5 ||
1004             event->xbutton.button == Button6 ||
1005             event->xbutton.button == Button7))
1006     {
1007       gltrackball_mousewheel (jc->trackball, event->xbutton.button, 10,
1008                               !!event->xbutton.state);
1009       return True;
1010     }
1011   else if (event->xany.type == MotionNotify &&
1012            jc->button_down_p)
1013     {
1014       gltrackball_track (jc->trackball,
1015                          event->xmotion.x, event->xmotion.y,
1016                          MI_WIDTH (mi), MI_HEIGHT (mi));
1017       return True;
1018     }
1019   else if (event->xany.type == KeyPress)
1020     {
1021       KeySym keysym;
1022       char c = 0;
1023       XLookupString (&event->xkey, &c, 1, &keysym, 0);
1024
1025       if (c == ' ' || c == '\t' || c == '\r' || c == '\n')
1026         {
1027           begin_scatter (mi, False);
1028           jc->state = PUZZLE_SCATTER;
1029           return True;
1030         }
1031     }
1032
1033
1034   return False;
1035 }
1036
1037
1038 ENTRYPOINT void
1039 init_jigsaw (ModeInfo *mi)
1040 {
1041   jigsaw_configuration *jc;
1042   int wire = MI_IS_WIREFRAME(mi);
1043
1044   if (!sps) {
1045     sps = (jigsaw_configuration *)
1046       calloc (MI_NUM_SCREENS(mi), sizeof (jigsaw_configuration));
1047     if (!sps) {
1048       fprintf(stderr, "%s: out of memory\n", progname);
1049       exit(1);
1050     }
1051   }
1052   jc = &sps[MI_SCREEN(mi)];
1053   jc->glx_context = init_GL(mi);
1054
1055   reshape_jigsaw (mi, MI_WIDTH(mi), MI_HEIGHT(mi));
1056
1057   if (!wire)
1058     {
1059       GLfloat pos[4] = {0.05, 0.07, 1.00, 0.0};
1060       GLfloat amb[4] = {0.2, 0.2, 0.2, 1.0};
1061       GLfloat dif[4] = {1.0, 1.0, 1.0, 1.0};
1062       GLfloat spc[4] = {0.0, 1.0, 1.0, 1.0};
1063
1064       glLightfv(GL_LIGHT0, GL_POSITION, pos);
1065       glLightfv(GL_LIGHT0, GL_AMBIENT,  amb);
1066       glLightfv(GL_LIGHT0, GL_DIFFUSE,  dif);
1067       glLightfv(GL_LIGHT0, GL_SPECULAR, spc);
1068     }
1069
1070   jc->trackball = gltrackball_init ();
1071   jc->rot = make_rotator (0, 0, 0, 0, speed * 0.002, True);
1072
1073   jc->state = PUZZLE_LOADING;
1074
1075   resolution_arg /= complexity_arg;
1076
1077   if (wire)
1078     make_puzzle_grid (mi);
1079   else
1080     load_image (mi);
1081 }
1082
1083
1084 ENTRYPOINT void
1085 draw_jigsaw (ModeInfo *mi)
1086 {
1087   jigsaw_configuration *jc = &sps[MI_SCREEN(mi)];
1088   Display *dpy = MI_DISPLAY(mi);
1089   Window window = MI_WINDOW(mi);
1090   int wire = MI_IS_WIREFRAME(mi);
1091
1092   if (!jc->glx_context)
1093     return;
1094
1095   animate (mi);
1096
1097   glXMakeCurrent(MI_DISPLAY(mi), MI_WINDOW(mi), *(jc->glx_context));
1098
1099   glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
1100
1101   glPushMatrix ();
1102
1103   gltrackball_rotate (jc->trackball);
1104
1105   if (wobble_p && jc->puzzle)
1106     {
1107       double x, y, z;
1108       double max = 60;
1109       get_position (jc->rot, &x, &y, &z, !jc->button_down_p);
1110       x = 1; /* always lean back */
1111       glRotatef (max/2 - x*max, 1, 0, 0);
1112       glRotatef (max/2 - z*max, 0, 1, 0);
1113     }
1114
1115   mi->polygon_count = 0;
1116
1117   glEnable(GL_CULL_FACE);
1118   glEnable(GL_DEPTH_TEST);
1119   glEnable(GL_NORMALIZE);
1120   glEnable(GL_LINE_SMOOTH);
1121
1122   if (jc->puzzle)
1123     {
1124       GLfloat s = 14.0 / jc->puzzle_height;
1125       int x, y;
1126
1127       glScalef (s, s, s);
1128       glTranslatef (-jc->puzzle_width / 2.0, -jc->puzzle_height / 2.0, 0);
1129
1130       if (! wire)
1131         {
1132           glEnable (GL_TEXTURE_2D);
1133           glEnable (GL_BLEND);
1134           glEnable (GL_LIGHTING);
1135           glEnable (GL_LIGHT0);
1136           glBlendFunc (GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
1137         }
1138
1139       for (y = 0; y < jc->puzzle_height; y++)
1140         for (x = 0; x < jc->puzzle_width; x++)
1141           {
1142             puzzle_piece *p = &jc->puzzle [y * jc->puzzle_width + x];
1143             glPushMatrix();
1144             glTranslatef (p->current.x, p->current.y, p->current.z);
1145             glTranslatef (0.5, 0.5, 0);
1146             glRotatef (p->current.r, 0, 0, 1);
1147             glRotatef (p->tilt, 0, 1, 0);
1148             glTranslatef (-0.5, -0.5, 0);
1149             glCallList(p->dlist);
1150             mi->polygon_count += p->polys;
1151             glPopMatrix();
1152           }
1153     }
1154
1155   glPopMatrix ();
1156
1157   if (mi->fps_p) do_fps (mi);
1158   glFinish();
1159
1160   glXSwapBuffers(dpy, window);
1161 }
1162
1163 XSCREENSAVER_MODULE ("Jigsaw", jigsaw)
1164
1165 #endif /* USE_GL */