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