Add third_party libs

1 files changed, 1486 insertions, 0 deletions

diff --git a/third_party/windows/fltk-1.1.10/test/glpuzzle.cxx b/third_party/windows/fltk-1.1.10/test/glpuzzle.cxx
new file mode 100644
index 0000000..464f660
--- /dev/null
+++ b/third_party/windows/fltk-1.1.10/test/glpuzzle.cxx
@@ -0,0 +1,1486 @@
+//

+// "$Id: glpuzzle.cxx 5845 2007-05-20 00:01:06Z mike $"

+//

+// OpenGL puzzle demo for the Fast Light Tool Kit (FLTK).

+//

+// This is a GLUT demo program to demonstrate fltk's GLUT emulation.

+// Search for "fltk" to find all the changes

+//

+// Copyright 1998-2005 by Bill Spitzak and others.

+//

+// This library is free software; you can redistribute it and/or

+// modify it under the terms of the GNU Library General Public

+// License as published by the Free Software Foundation; either

+// version 2 of the License, or (at your option) any later version.

+//

+// This library is distributed in the hope that it will be useful,

+// but WITHOUT ANY WARRANTY; without even the implied warranty of

+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

+// Library General Public License for more details.

+//

+// You should have received a copy of the GNU Library General Public

+// License along with this library; if not, write to the Free Software

+// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307

+// USA.

+//

+// Please report all bugs and problems on the following page:

+//

+//     http://www.fltk.org/str.php

+//

+

+// this block added for fltk's distribtion so it will compile w/o OpenGL:

+#include "config.h"

+#if !HAVE_GL || !HAVE_GL_GLU_H

+#include <FL/Fl.H>

+#include <FL/fl_message.H>

+int main(int, char**) {

+  fl_alert("This demo does not work without GL and GLU");

+  return 1;

+}

+#else

+// end of added block

+

+#include <stdio.h>

+#include <stdlib.h>

+#include <string.h>

+#include <sys/types.h>

+#include <time.h>

+#include <math.h>

+#include <FL/glut.H>	// changed for fltk

+#include <FL/glu.h>     // added for fltk

+#include "trackball.c"	// changed from trackball.h for fltk

+

+#define WIDTH 4

+#define HEIGHT 5

+#define PIECES 10

+#define OFFSETX -2

+#define OFFSETY -2.5

+#define OFFSETZ -0.5

+

+typedef char Config[HEIGHT][WIDTH];

+

+struct puzzle {

+  struct puzzle *backptr;

+  struct puzzle *solnptr;

+  Config pieces;

+  struct puzzle *next;

+  unsigned hashvalue;

+};

+

+#define HASHSIZE 10691

+

+struct puzzlelist {

+  struct puzzle *puzzle;

+  struct puzzlelist *next;

+};

+

+static char convert[PIECES + 1] =

+{0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 4};

+

+static unsigned char colors[PIECES + 1][3] =

+{

+  {0, 0, 0},

+  {255, 255, 127},

+  {255, 255, 127},

+  {255, 255, 127},

+  {255, 255, 127},

+  {255, 127, 255},

+  {255, 127, 255},

+  {255, 127, 255},

+  {255, 127, 255},

+  {255, 127, 127},

+  {255, 255, 255},

+};

+

+void changeState(void);

+

+static struct puzzle *hashtable[HASHSIZE];

+static struct puzzle *startPuzzle;

+static struct puzzlelist *puzzles;

+static struct puzzlelist *lastentry;

+

+int curX, curY, visible;

+

+#define MOVE_SPEED 0.2

+static unsigned char movingPiece;

+static float move_x, move_y;

+static float curquat[4];

+static int doubleBuffer = 1;

+static int depth = 1;

+

+static char xsize[PIECES + 1] =

+{0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2};

+static char ysize[PIECES + 1] =

+{0, 1, 1, 1, 1, 2, 2, 2, 2, 1, 2};

+static float zsize[PIECES + 1] =

+{0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0.6};

+

+static Config startConfig =

+{

+  {8, 10, 10, 7},

+  {8, 10, 10, 7},

+  {6, 9, 9, 5},

+  {6, 4, 3, 5},

+  {2, 0, 0, 1}

+};

+

+static Config thePuzzle =

+{

+  {8, 10, 10, 7},

+  {8, 10, 10, 7},

+  {6, 9, 9, 5},

+  {6, 4, 3, 5},

+  {2, 0, 0, 1}

+};

+

+static int xadds[4] =

+{-1, 0, 1, 0};

+static int yadds[4] =

+{0, -1, 0, 1};

+

+static long W = 400, H = 300;

+static GLint viewport[4];

+

+#define srandom srand

+#define random() (rand() >> 2)

+

+unsigned

+hash(Config config)

+{

+  int i, j, value;

+

+  value = 0;

+  for (i = 0; i < HEIGHT; i++) {

+    for (j = 0; j < WIDTH; j++) {

+      value = value + convert[(int)config[i][j]];

+      value *= 6;

+    }

+  }

+  return (value);

+}

+

+int

+solution(Config config)

+{

+  if (config[4][1] == 10 && config[4][2] == 10)

+    return (1);

+  return (0);

+}

+

+float boxcoords[][3] =

+{

+  {0.2, 0.2, 0.9},

+  {0.8, 0.2, 0.9},

+  {0.8, 0.8, 0.9},

+  {0.2, 0.8, 0.9},

+  {0.2, 0.1, 0.8},

+  {0.8, 0.1, 0.8},

+  {0.9, 0.2, 0.8},

+  {0.9, 0.8, 0.8},

+  {0.8, 0.9, 0.8},

+  {0.2, 0.9, 0.8},

+  {0.1, 0.8, 0.8},

+  {0.1, 0.2, 0.8},

+  {0.2, 0.1, 0.2},

+  {0.8, 0.1, 0.2},

+  {0.9, 0.2, 0.2},

+  {0.9, 0.8, 0.2},

+  {0.8, 0.9, 0.2},

+  {0.2, 0.9, 0.2},

+  {0.1, 0.8, 0.2},

+  {0.1, 0.2, 0.2},

+  {0.2, 0.2, 0.1},

+  {0.8, 0.2, 0.1},

+  {0.8, 0.8, 0.1},

+  {0.2, 0.8, 0.1},

+};

+

+float boxnormals[][3] =

+{

+  {0, 0, 1},            /* 0 */

+  {0, 1, 0},

+  {1, 0, 0},

+  {0, 0, -1},

+  {0, -1, 0},

+  {-1, 0, 0},

+  {0.7071, 0.7071, 0.0000},  /* 6 */

+  {0.7071, -0.7071, 0.0000},

+  {-0.7071, 0.7071, 0.0000},

+  {-0.7071, -0.7071, 0.0000},

+  {0.7071, 0.0000, 0.7071},  /* 10 */

+  {0.7071, 0.0000, -0.7071},

+  {-0.7071, 0.0000, 0.7071},

+  {-0.7071, 0.0000, -0.7071},

+  {0.0000, 0.7071, 0.7071},  /* 14 */

+  {0.0000, 0.7071, -0.7071},

+  {0.0000, -0.7071, 0.7071},

+  {0.0000, -0.7071, -0.7071},

+  {0.5774, 0.5774, 0.5774},  /* 18 */

+  {0.5774, 0.5774, -0.5774},

+  {0.5774, -0.5774, 0.5774},

+  {0.5774, -0.5774, -0.5774},

+  {-0.5774, 0.5774, 0.5774},

+  {-0.5774, 0.5774, -0.5774},

+  {-0.5774, -0.5774, 0.5774},

+  {-0.5774, -0.5774, -0.5774},

+};

+

+int boxfaces[][4] =

+{

+  {0, 1, 2, 3},         /* 0 */

+  {9, 8, 16, 17},

+  {6, 14, 15, 7},

+  {20, 23, 22, 21},

+  {12, 13, 5, 4},

+  {19, 11, 10, 18},

+  {7, 15, 16, 8},       /* 6 */

+  {13, 14, 6, 5},

+  {18, 10, 9, 17},

+  {19, 12, 4, 11},

+  {1, 6, 7, 2},         /* 10 */

+  {14, 21, 22, 15},

+  {11, 0, 3, 10},

+  {20, 19, 18, 23},

+  {3, 2, 8, 9},         /* 14 */

+  {17, 16, 22, 23},

+  {4, 5, 1, 0},

+  {20, 21, 13, 12},

+  {2, 7, 8, -1},        /* 18 */

+  {16, 15, 22, -1},

+  {5, 6, 1, -1},

+  {13, 21, 14, -1},

+  {10, 3, 9, -1},

+  {18, 17, 23, -1},

+  {11, 4, 0, -1},

+  {20, 12, 19, -1},

+};

+

+#define NBOXFACES (sizeof(boxfaces)/sizeof(boxfaces[0]))

+

+/* Draw a box.  Bevel as desired. */

+void

+drawBox(int piece, float xoff, float yoff)

+{

+  int xlen, ylen;

+  int i, k;

+  float x, y, z;

+  float zlen;

+  float *v;

+

+  xlen = xsize[piece];

+  ylen = ysize[piece];

+  zlen = zsize[piece];

+

+  glColor3ubv(colors[piece]);

+  glBegin(GL_QUADS);

+  for (i = 0; i < 18; i++) {

+    glNormal3fv(boxnormals[i]);

+    for (k = 0; k < 4; k++) {

+      if (boxfaces[i][k] == -1)

+        continue;

+      v = boxcoords[boxfaces[i][k]];

+      x = v[0] + OFFSETX;

+      if (v[0] > 0.5)

+        x += xlen - 1;

+      y = v[1] + OFFSETY;

+      if (v[1] > 0.5)

+        y += ylen - 1;

+      z = v[2] + OFFSETZ;

+      if (v[2] > 0.5)

+        z += zlen - 1;

+      glVertex3f(xoff + x, yoff + y, z);

+    }

+  }

+  glEnd();

+  glBegin(GL_TRIANGLES);

+  for (i = 18; i < int(NBOXFACES); i++) {

+    glNormal3fv(boxnormals[i]);

+    for (k = 0; k < 3; k++) {

+      if (boxfaces[i][k] == -1)

+        continue;

+      v = boxcoords[boxfaces[i][k]];

+      x = v[0] + OFFSETX;

+      if (v[0] > 0.5)

+        x += xlen - 1;

+      y = v[1] + OFFSETY;

+      if (v[1] > 0.5)

+        y += ylen - 1;

+      z = v[2] + OFFSETZ;

+      if (v[2] > 0.5)

+        z += zlen - 1;

+      glVertex3f(xoff + x, yoff + y, z);

+    }

+  }

+  glEnd();

+}

+

+float containercoords[][3] =

+{

+  {-0.1, -0.1, 1.0},

+  {-0.1, -0.1, -0.1},

+  {4.1, -0.1, -0.1},

+  {4.1, -0.1, 1.0},

+  {1.0, -0.1, 0.6},     /* 4 */

+  {3.0, -0.1, 0.6},

+  {1.0, -0.1, 0.0},

+  {3.0, -0.1, 0.0},

+  {1.0, 0.0, 0.0},      /* 8 */

+  {3.0, 0.0, 0.0},

+  {3.0, 0.0, 0.6},

+  {1.0, 0.0, 0.6},

+  {0.0, 0.0, 1.0},      /* 12 */

+  {4.0, 0.0, 1.0},

+  {4.0, 0.0, 0.0},

+  {0.0, 0.0, 0.0},

+  {0.0, 5.0, 0.0},      /* 16 */

+  {0.0, 5.0, 1.0},

+  {4.0, 5.0, 1.0},

+  {4.0, 5.0, 0.0},

+  {-0.1, 5.1, -0.1},    /* 20 */

+  {4.1, 5.1, -0.1},

+  {4.1, 5.1, 1.0},

+  {-0.1, 5.1, 1.0},

+};

+

+float containernormals[][3] =

+{

+  {0, -1, 0},

+  {0, -1, 0},

+  {0, -1, 0},

+  {0, -1, 0},

+  {0, -1, 0},

+  {0, 1, 0},

+  {0, 1, 0},

+  {0, 1, 0},

+  {1, 0, 0},

+  {1, 0, 0},

+  {1, 0, 0},

+  {-1, 0, 0},

+  {-1, 0, 0},

+  {-1, 0, 0},

+  {0, 1, 0},

+  {0, 0, -1},

+  {0, 0, -1},

+  {0, 0, 1},

+  {0, 0, 1},

+  {0, 0, 1},

+  {0, 0, 1},

+  {0, 0, 1},

+  {0, 0, 1},

+  {0, 0, 1},

+};

+

+int containerfaces[][4] =

+{

+  {1, 6, 4, 0},

+  {0, 4, 5, 3},

+  {1, 2, 7, 6},

+  {7, 2, 3, 5},

+  {16, 19, 18, 17},

+

+  {23, 22, 21, 20},

+  {12, 11, 8, 15},

+  {10, 13, 14, 9},

+

+  {15, 16, 17, 12},

+  {2, 21, 22, 3},

+  {6, 8, 11, 4},

+

+  {1, 0, 23, 20},

+  {14, 13, 18, 19},

+  {9, 7, 5, 10},

+

+  {12, 13, 10, 11},

+

+  {1, 20, 21, 2},

+  {4, 11, 10, 5},

+

+  {15, 8, 19, 16},

+  {19, 8, 9, 14},

+  {8, 6, 7, 9},

+  {0, 3, 13, 12},

+  {13, 3, 22, 18},

+  {18, 22, 23, 17},

+  {17, 23, 0, 12},

+};

+

+#define NCONTFACES (sizeof(containerfaces)/sizeof(containerfaces[0]))

+

+/* Draw the container */

+void

+drawContainer(void)

+{

+  int i, k;

+  float *v;

+

+  /* Y is reversed here because the model has it reversed */

+

+  /* Arbitrary bright wood-like color */

+  glColor3ub(209, 103, 23);

+  glBegin(GL_QUADS);

+  for (i = 0; i < int(NCONTFACES); i++) {

+    v = containernormals[i];

+    glNormal3f(v[0], -v[1], v[2]);

+    for (k = 3; k >= 0; k--) {

+      v = containercoords[containerfaces[i][k]];

+      glVertex3f(v[0] + OFFSETX, -(v[1] + OFFSETY), v[2] + OFFSETZ);

+    }

+  }

+  glEnd();

+}

+

+void

+drawAll(void)

+{

+  int i, j;

+  int piece;

+  char done[PIECES + 1];

+  float m[4][4];

+

+  build_rotmatrix(m, curquat);

+  glMatrixMode(GL_MODELVIEW);

+  glLoadIdentity();

+  glTranslatef(0, 0, -10);

+  glMultMatrixf(&(m[0][0]));

+  glRotatef(180, 0, 0, 1);

+

+  if (depth) {

+    glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);

+  } else {

+    glClear(GL_COLOR_BUFFER_BIT);

+  }

+  for (i = 1; i <= PIECES; i++) {

+    done[i] = 0;

+  }

+  glLoadName(0);

+  drawContainer();

+  for (i = 0; i < HEIGHT; i++) {

+    for (j = 0; j < WIDTH; j++) {

+      piece = thePuzzle[i][j];

+      if (piece == 0)

+        continue;

+      if (done[piece])

+        continue;

+      done[piece] = 1;

+      glLoadName(piece);

+      if (piece == movingPiece) {

+        drawBox(piece, move_x, move_y);

+      } else {

+        drawBox(piece, j, i);

+      }

+    }

+  }

+}

+

+void

+redraw(void)

+{

+  glMatrixMode(GL_PROJECTION);

+  glLoadIdentity();

+  gluPerspective(45, viewport[2]*1.0/viewport[3], 0.1, 100.0);

+

+  drawAll();

+

+  if (doubleBuffer)

+    glutSwapBuffers();

+  else

+    glFinish();

+}

+

+void

+solidifyChain(struct puzzle *puzzle)

+{

+  int i;

+  char buf[256];

+

+  i = 0;

+  while (puzzle->backptr) {

+    i++;

+    puzzle->backptr->solnptr = puzzle;

+    puzzle = puzzle->backptr;

+  }

+  sprintf(buf, "%d moves to complete!", i);

+  glutSetWindowTitle(buf);

+}

+

+int

+addConfig(Config config, struct puzzle *back)

+{

+  unsigned hashvalue;

+  struct puzzle *newpiece;

+  struct puzzlelist *newlistentry;

+

+  hashvalue = hash(config);

+

+  newpiece = hashtable[hashvalue % HASHSIZE];

+  while (newpiece != NULL) {

+    if (newpiece->hashvalue == hashvalue) {

+      int i, j;

+

+      for (i = 0; i < WIDTH; i++) {

+        for (j = 0; j < HEIGHT; j++) {

+          if (convert[(int)config[j][i]] !=

+            convert[(int)newpiece->pieces[j][i]])

+            goto nomatch;

+        }

+      }

+      return 0;

+    }

+  nomatch:

+    newpiece = newpiece->next;

+  }

+

+  newpiece = (struct puzzle *) malloc(sizeof(struct puzzle));

+  newpiece->next = hashtable[hashvalue % HASHSIZE];

+  newpiece->hashvalue = hashvalue;

+  memcpy(newpiece->pieces, config, HEIGHT * WIDTH);

+  newpiece->backptr = back;

+  newpiece->solnptr = NULL;

+  hashtable[hashvalue % HASHSIZE] = newpiece;

+

+  newlistentry = (struct puzzlelist *) malloc(sizeof(struct puzzlelist));

+  newlistentry->puzzle = newpiece;

+  newlistentry->next = NULL;

+

+  if (lastentry) {

+    lastentry->next = newlistentry;

+  } else {

+    puzzles = newlistentry;

+  }

+  lastentry = newlistentry;

+

+  if (back == NULL) {

+    startPuzzle = newpiece;

+  }

+  if (solution(config)) {

+    solidifyChain(newpiece);

+    return 1;

+  }

+  return 0;

+}

+

+/* Checks if a space can move */

+int

+canmove0(Config pieces, int x, int y, int dir, Config newpieces)

+{

+  char piece;

+  int xadd, yadd;

+  int l, m;

+

+  xadd = xadds[dir];

+  yadd = yadds[dir];

+

+  if (x + xadd < 0 || x + xadd >= WIDTH ||

+    y + yadd < 0 || y + yadd >= HEIGHT)

+    return 0;

+  piece = pieces[y + yadd][x + xadd];

+  if (piece == 0)

+    return 0;

+  memcpy(newpieces, pieces, HEIGHT * WIDTH);

+  for (l = 0; l < WIDTH; l++) {

+    for (m = 0; m < HEIGHT; m++) {

+      if (newpieces[m][l] == piece)

+        newpieces[m][l] = 0;

+    }

+  }

+  xadd = -xadd;

+  yadd = -yadd;

+  for (l = 0; l < WIDTH; l++) {

+    for (m = 0; m < HEIGHT; m++) {

+      if (pieces[m][l] == piece) {

+        int newx, newy;

+

+        newx = l + xadd;

+        newy = m + yadd;

+        if (newx < 0 || newx >= WIDTH ||

+          newy < 0 || newy >= HEIGHT)

+          return 0;

+        if (newpieces[newy][newx] != 0)

+          return 0;

+        newpieces[newy][newx] = piece;

+      }

+    }

+  }

+  return 1;

+}

+

+/* Checks if a piece can move */

+int

+canmove(Config pieces, int x, int y, int dir, Config newpieces)

+{

+  int xadd, yadd;

+

+  xadd = xadds[dir];

+  yadd = yadds[dir];

+

+  if (x + xadd < 0 || x + xadd >= WIDTH ||

+    y + yadd < 0 || y + yadd >= HEIGHT)

+    return 0;

+  if (pieces[y + yadd][x + xadd] == pieces[y][x]) {

+    return canmove(pieces, x + xadd, y + yadd, dir, newpieces);

+  }

+  if (pieces[y + yadd][x + xadd] != 0)

+    return 0;

+  return canmove0(pieces, x + xadd, y + yadd, (dir + 2) % 4, newpieces);

+}

+

+int

+generateNewConfigs(struct puzzle *puzzle)

+{

+  int i, j, k;

+  Config pieces;

+  Config newpieces;

+

+  memcpy(pieces, puzzle->pieces, HEIGHT * WIDTH);

+  for (i = 0; i < WIDTH; i++) {

+    for (j = 0; j < HEIGHT; j++) {

+      if (pieces[j][i] == 0) {

+        for (k = 0; k < 4; k++) {

+          if (canmove0(pieces, i, j, k, newpieces)) {

+            if (addConfig(newpieces, puzzle))

+              return 1;

+          }

+        }

+      }

+    }

+  }

+  return 0;

+}

+

+void

+freeSolutions(void)

+{

+  struct puzzlelist *nextpuz;

+  struct puzzle *puzzle, *next;

+  int i;

+

+  while (puzzles) {

+    nextpuz = puzzles->next;

+    free((char *) puzzles);

+    puzzles = nextpuz;

+  }

+  lastentry = NULL;

+  for (i = 0; i < HASHSIZE; i++) {

+    puzzle = hashtable[i];

+    hashtable[i] = NULL;

+    while (puzzle) {

+      next = puzzle->next;

+      free((char *) puzzle);

+      puzzle = next;

+    }

+  }

+  startPuzzle = NULL;

+}

+

+int

+continueSolving(void)

+{

+  struct puzzle *nextpuz;

+  int i, j;

+  int movedPiece;

+  int movedir;

+  int fromx, fromy;

+  int tox, toy;

+

+  if (startPuzzle == NULL)

+    return 0;

+  if (startPuzzle->solnptr == NULL) {

+    freeSolutions();

+    return 0;

+  }

+  nextpuz = startPuzzle->solnptr;

+  movedPiece = 0;

+  movedir = 0;

+  for (i = 0; i < HEIGHT; i++) {

+    for (j = 0; j < WIDTH; j++) {

+      if (startPuzzle->pieces[i][j] != nextpuz->pieces[i][j]) {

+        if (startPuzzle->pieces[i][j]) {

+          movedPiece = startPuzzle->pieces[i][j];

+          fromx = j;

+          fromy = i;

+          if (i < HEIGHT - 1 && nextpuz->pieces[i + 1][j] == movedPiece) {

+            movedir = 3;

+          } else {

+            movedir = 2;

+          }

+          goto found_piece;

+        } else {

+          movedPiece = nextpuz->pieces[i][j];

+          if (i < HEIGHT - 1 &&

+            startPuzzle->pieces[i + 1][j] == movedPiece) {

+            fromx = j;

+            fromy = i + 1;

+            movedir = 1;

+          } else {

+            fromx = j + 1;

+            fromy = i;

+            movedir = 0;

+          }

+          goto found_piece;

+        }

+      }

+    }

+  }

+  glutSetWindowTitle((char *)"What!  No change?");

+  freeSolutions();

+  return 0;

+

+found_piece:

+  if (!movingPiece) {

+    movingPiece = movedPiece;

+    move_x = fromx;

+    move_y = fromy;

+  }

+  move_x += xadds[movedir] * MOVE_SPEED;

+  move_y += yadds[movedir] * MOVE_SPEED;

+

+  tox = fromx + xadds[movedir];

+  toy = fromy + yadds[movedir];

+

+  if (move_x > tox - MOVE_SPEED / 2 && move_x < tox + MOVE_SPEED / 2 &&

+    move_y > toy - MOVE_SPEED / 2 && move_y < toy + MOVE_SPEED / 2) {

+    startPuzzle = nextpuz;

+    movingPiece = 0;

+  }

+  memcpy(thePuzzle, startPuzzle->pieces, HEIGHT * WIDTH);

+  changeState();

+  return 1;

+}

+

+int

+solvePuzzle(void)

+{

+  struct puzzlelist *nextpuz;

+  char buf[256];

+  int i;

+

+  if (solution(thePuzzle)) {

+    glutSetWindowTitle((char *)"Puzzle already solved!");

+    return 0;

+  }

+  addConfig(thePuzzle, NULL);

+  i = 0;

+

+  while (puzzles) {

+    i++;

+    if (generateNewConfigs(puzzles->puzzle))

+      break;

+    nextpuz = puzzles->next;

+    free((char *) puzzles);

+    puzzles = nextpuz;

+  }

+  if (puzzles == NULL) {

+    freeSolutions();

+    sprintf(buf, "I can't solve it! (%d positions examined)", i);

+    glutSetWindowTitle(buf);

+    return 1;

+  }

+  return 1;

+}

+

+int

+selectPiece(int mousex, int mousey)

+{

+  long hits;

+  GLuint selectBuf[1024];

+  GLuint closest;

+  GLuint dist;

+

+  glSelectBuffer(1024, selectBuf);

+  (void) glRenderMode(GL_SELECT);

+  glInitNames();

+

+  /* Because LoadName() won't work with no names on the stack */

+  glPushName(0);

+

+  glMatrixMode(GL_PROJECTION);

+  glLoadIdentity();

+  gluPickMatrix(mousex, H - mousey, 4, 4, viewport);

+  gluPerspective(45, viewport[2]*1.0/viewport[3], 0.1, 100.0);

+

+  drawAll();

+

+  hits = glRenderMode(GL_RENDER);

+  if (hits <= 0) {

+    return 0;

+  }

+  closest = 0;

+  dist = 0xFFFFFFFFU; //2147483647;

+  while (hits) {

+    if (selectBuf[(hits - 1) * 4 + 1] < dist) {

+      dist = selectBuf[(hits - 1) * 4 + 1];

+      closest = selectBuf[(hits - 1) * 4 + 3];

+    }

+    hits--;

+  }

+  return closest;

+}

+

+void

+nukePiece(int piece)

+{

+  int i, j;

+

+  for (i = 0; i < HEIGHT; i++) {

+    for (j = 0; j < WIDTH; j++) {

+      if (thePuzzle[i][j] == piece) {

+        thePuzzle[i][j] = 0;

+      }

+    }

+  }

+}

+

+void

+multMatrices(const GLfloat a[16], const GLfloat b[16], GLfloat r[16])

+{

+  int i, j;

+

+  for (i = 0; i < 4; i++) {

+    for (j = 0; j < 4; j++) {

+      r[i * 4 + j] =

+        a[i * 4 + 0] * b[0 * 4 + j] +

+        a[i * 4 + 1] * b[1 * 4 + j] +

+        a[i * 4 + 2] * b[2 * 4 + j] +

+        a[i * 4 + 3] * b[3 * 4 + j];

+    }

+  }

+}

+

+void

+makeIdentity(GLfloat m[16])

+{

+  m[0 + 4 * 0] = 1;

+  m[0 + 4 * 1] = 0;

+  m[0 + 4 * 2] = 0;

+  m[0 + 4 * 3] = 0;

+  m[1 + 4 * 0] = 0;

+  m[1 + 4 * 1] = 1;

+  m[1 + 4 * 2] = 0;

+  m[1 + 4 * 3] = 0;

+  m[2 + 4 * 0] = 0;

+  m[2 + 4 * 1] = 0;

+  m[2 + 4 * 2] = 1;

+  m[2 + 4 * 3] = 0;

+  m[3 + 4 * 0] = 0;

+  m[3 + 4 * 1] = 0;

+  m[3 + 4 * 2] = 0;

+  m[3 + 4 * 3] = 1;

+}

+

+/*

+   ** inverse = invert(src)

+ */

+int

+invertMatrix(const GLfloat src[16], GLfloat inverse[16])

+{

+  int i, j, k, swap;

+  double t;

+  GLfloat temp[4][4];

+

+  for (i = 0; i < 4; i++) {

+    for (j = 0; j < 4; j++) {

+      temp[i][j] = src[i * 4 + j];

+    }

+  }

+  makeIdentity(inverse);

+

+  for (i = 0; i < 4; i++) {

+    /* 

+       ** Look for largest element in column */

+    swap = i;

+    for (j = i + 1; j < 4; j++) {

+      if (fabs(temp[j][i]) > fabs(temp[i][i])) {

+        swap = j;

+      }

+    }

+

+    if (swap != i) {

+      /* 

+         ** Swap rows. */

+      for (k = 0; k < 4; k++) {

+        t = temp[i][k];

+        temp[i][k] = temp[swap][k];

+        temp[swap][k] = t;

+

+        t = inverse[i * 4 + k];

+        inverse[i * 4 + k] = inverse[swap * 4 + k];

+        inverse[swap * 4 + k] = t;

+      }

+    }

+    if (temp[i][i] == 0) {

+      /* 

+         ** No non-zero pivot.  The matrix is singular, which

+         shouldn't ** happen.  This means the user gave us a

+         bad matrix. */

+      return 0;

+    }

+    t = temp[i][i];

+    for (k = 0; k < 4; k++) {

+      temp[i][k] /= t;

+      inverse[i * 4 + k] /= t;

+    }

+    for (j = 0; j < 4; j++) {

+      if (j != i) {

+        t = temp[j][i];

+        for (k = 0; k < 4; k++) {

+          temp[j][k] -= temp[i][k] * t;

+          inverse[j * 4 + k] -= inverse[i * 4 + k] * t;

+        }

+      }

+    }

+  }

+  return 1;

+}

+

+/*

+   ** This is a screwball function.  What it does is the following:

+   ** Given screen x and y coordinates, compute the corresponding object space 

+   **   x and y coordinates given that the object space z is 0.9 + OFFSETZ.

+   ** Since the tops of (most) pieces are at z = 0.9 + OFFSETZ, we use that 

+   **   number.

+ */

+int

+computeCoords(int piece, int mousex, int mousey,

+  GLfloat * selx, GLfloat * sely)

+{

+  GLfloat modelMatrix[16];

+  GLfloat projMatrix[16];

+  GLfloat finalMatrix[16];

+  GLfloat in[4];

+  GLfloat a, b, c, d;

+  GLfloat top, bot;

+  GLfloat z;

+  GLfloat w;

+  GLfloat height;

+

+  if (piece == 0)

+    return 0;

+  height = zsize[piece] - 0.1 + OFFSETZ;

+

+  glGetFloatv(GL_PROJECTION_MATRIX, projMatrix);

+  glGetFloatv(GL_MODELVIEW_MATRIX, modelMatrix);

+  multMatrices(modelMatrix, projMatrix, finalMatrix);

+  if (!invertMatrix(finalMatrix, finalMatrix))

+    return 0;

+

+  in[0] = (2.0 * (mousex - viewport[0]) / viewport[2]) - 1;

+  in[1] = (2.0 * ((H - mousey) - viewport[1]) / viewport[3]) - 1;

+

+  a = in[0] * finalMatrix[0 * 4 + 2] +

+    in[1] * finalMatrix[1 * 4 + 2] +

+    finalMatrix[3 * 4 + 2];

+  b = finalMatrix[2 * 4 + 2];

+  c = in[0] * finalMatrix[0 * 4 + 3] +

+    in[1] * finalMatrix[1 * 4 + 3] +

+    finalMatrix[3 * 4 + 3];

+  d = finalMatrix[2 * 4 + 3];

+

+  /* 

+     ** Ok, now we need to solve for z: **   (a + b z) / (c + d 

+

+     z) = height. ** ("height" is the height in object space we 

+

+     want to solve z for) ** ** ==>  a + b z = height c +

+     height d z **      bz - height d z = height c - a ** z =

+     (height c - a) / (b - height d) */

+  top = height * c - a;

+  bot = b - height * d;

+  if (bot == 0.0)

+    return 0;

+

+  z = top / bot;

+

+  /* 

+     ** Ok, no problem. ** Now we solve for x and y.  We know

+     that w = c + d z, so we compute it. */

+  w = c + d * z;

+

+  /* 

+     ** Now for x and y: */

+  *selx = (in[0] * finalMatrix[0 * 4 + 0] +

+    in[1] * finalMatrix[1 * 4 + 0] +

+    z * finalMatrix[2 * 4 + 0] +

+    finalMatrix[3 * 4 + 0]) / w - OFFSETX;

+  *sely = (in[0] * finalMatrix[0 * 4 + 1] +

+    in[1] * finalMatrix[1 * 4 + 1] +

+    z * finalMatrix[2 * 4 + 1] +

+    finalMatrix[3 * 4 + 1]) / w - OFFSETY;

+  return 1;

+}

+

+static int selected;

+static int selectx, selecty;

+static float selstartx, selstarty;

+

+void

+grabPiece(int piece, float selx, float sely)

+{

+  int hit;

+

+  selectx = int(selx);

+  selecty = int(sely);

+  if (selectx < 0 || selecty < 0 || selectx >= WIDTH || selecty >= HEIGHT) {

+    return;

+  }

+  hit = thePuzzle[selecty][selectx];

+  if (hit != piece)

+    return;

+  if (hit) {

+    movingPiece = hit;

+    while (selectx > 0 && thePuzzle[selecty][selectx - 1] == movingPiece) {

+      selectx--;

+    }

+    while (selecty > 0 && thePuzzle[selecty - 1][selectx] == movingPiece) {

+      selecty--;

+    }

+    move_x = selectx;

+    move_y = selecty;

+    selected = 1;

+    selstartx = selx;

+    selstarty = sely;

+  } else {

+    selected = 0;

+  }

+  changeState();

+}

+

+void

+moveSelection(float selx, float sely)

+{

+  float deltax, deltay;

+  int dir;

+  Config newpieces;

+

+  if (!selected)

+    return;

+  deltax = selx - selstartx;

+  deltay = sely - selstarty;

+

+  if (fabs(deltax) > fabs(deltay)) {

+    deltay = 0;

+    if (deltax > 0) {

+      if (deltax > 1)

+        deltax = 1;

+      dir = 2;

+    } else {

+      if (deltax < -1)

+        deltax = -1;

+      dir = 0;

+    }

+  } else {

+    deltax = 0;

+    if (deltay > 0) {

+      if (deltay > 1)

+        deltay = 1;

+      dir = 3;

+    } else {

+      if (deltay < -1)

+        deltay = -1;

+      dir = 1;

+    }

+  }

+  if (canmove(thePuzzle, selectx, selecty, dir, newpieces)) {

+    move_x = deltax + selectx;

+    move_y = deltay + selecty;

+    if (deltax > 0.5) {

+      memcpy(thePuzzle, newpieces, HEIGHT * WIDTH);

+      selectx++;

+      selstartx++;

+    } else if (deltax < -0.5) {

+      memcpy(thePuzzle, newpieces, HEIGHT * WIDTH);

+      selectx--;

+      selstartx--;

+    } else if (deltay > 0.5) {

+      memcpy(thePuzzle, newpieces, HEIGHT * WIDTH);

+      selecty++;

+      selstarty++;

+    } else if (deltay < -0.5) {

+      memcpy(thePuzzle, newpieces, HEIGHT * WIDTH);

+      selecty--;

+      selstarty--;

+    }

+  } else {

+    if (deltay > 0 && thePuzzle[selecty][selectx] == 10 &&

+      selectx == 1 && selecty == 3) {

+      /* Allow visual movement of solution piece outside of the 

+

+         box */

+      move_x = selectx;

+      move_y = sely - selstarty + selecty;

+    } else {

+      move_x = selectx;

+      move_y = selecty;

+    }

+  }

+}

+

+void

+dropSelection(void)

+{

+  if (!selected)

+    return;

+  movingPiece = 0;

+  selected = 0;

+  changeState();

+}

+

+static int left_mouse, middle_mouse;

+static int mousex, mousey;

+static int solving;

+static int spinning;

+static float lastquat[4];

+static int sel_piece;

+

+static void

+Reshape(int width, int height)

+{

+

+  W = width;

+  H = height;

+  glViewport(0, 0, W, H);

+  glGetIntegerv(GL_VIEWPORT, viewport);

+}

+

+void

+toggleSolve(void)

+{

+    if (solving) {

+      freeSolutions();

+      solving = 0;

+      glutChangeToMenuEntry(1, (char *)"Solving", 1);

+      glutSetWindowTitle((char *)"glpuzzle");

+      movingPiece = 0;

+    } else {

+      glutChangeToMenuEntry(1, (char *)"Stop solving", 1);

+      glutSetWindowTitle((char *)"Solving...");

+      if (solvePuzzle()) {

+        solving = 1;

+      }

+    }

+    changeState();

+    glutPostRedisplay();

+}

+

+void reset(void)

+{

+    if (solving) {

+      freeSolutions();

+      solving = 0;

+      glutChangeToMenuEntry(1, (char *)"Solving", 1);

+      glutSetWindowTitle((char *)"glpuzzle");

+      movingPiece = 0;

+      changeState();

+    }

+    memcpy(thePuzzle, startConfig, HEIGHT * WIDTH);

+    glutPostRedisplay();

+}

+

+void

+keyboard(unsigned char c, int x, int y)

+{

+  int piece;

+

+  switch (c) {

+  case 27:

+    exit(0);

+    break;

+  case 'D':

+  case 'd':

+    if (solving) {

+      freeSolutions();

+      solving = 0;

+      glutChangeToMenuEntry(1, (char *)"Solving", 1);

+      glutSetWindowTitle((char *)"glpuzzle");

+      movingPiece = 0;

+      changeState();

+    }

+    piece = selectPiece(x, y);

+    if (piece) {

+      nukePiece(piece);

+    }

+    glutPostRedisplay();

+    break;

+  case 'R':

+  case 'r':

+    reset();

+    break;

+  case 'S':

+  case 's':

+    toggleSolve();

+    break;

+  case 'b':

+  case 'B':

+    depth = 1 - depth;

+    if (depth) {

+      glEnable(GL_DEPTH_TEST);

+    } else {

+      glDisable(GL_DEPTH_TEST);

+    }

+    glutPostRedisplay();

+    break;

+  default:

+    break;

+  }

+}

+

+void

+motion(int x, int y)

+{

+  float selx, sely;

+

+  if (middle_mouse && !left_mouse) {

+    if (mousex != x || mousey != y) {

+      trackball(lastquat,

+        (2.0*mousex - W) / W,

+        (H - 2.0*mousey) / H,

+        (2.0*x - W) / W,

+        (H - 2.0*y) / H);

+      spinning = 1;

+    } else {

+      spinning = 0;

+    }

+    changeState();

+  } else {

+    computeCoords(sel_piece, x, y, &selx, &sely);

+    moveSelection(selx, sely);

+  }

+  mousex = x;

+  mousey = y;

+  glutPostRedisplay();

+}

+

+void

+mouse(int b, int s, int x, int y)

+{

+  float selx, sely;

+

+  mousex = x;

+  mousey = y;

+  curX = x;

+  curY = y;

+  if (s == GLUT_DOWN) {

+    switch (b) {

+    case GLUT_LEFT_BUTTON:

+      if (solving) {

+        freeSolutions();

+        solving = 0;

+      glutChangeToMenuEntry(1, (char *)"Solving", 1);

+        glutSetWindowTitle((char *)"glpuzzle");

+        movingPiece = 0;

+      }

+      left_mouse = GL_TRUE;

+      sel_piece = selectPiece(mousex, mousey);

+      if (!sel_piece) {

+      left_mouse = GL_FALSE;

+      middle_mouse = GL_TRUE; // let it rotate object

+      } else if (computeCoords(sel_piece, mousex, mousey, &selx, &sely)) {

+        grabPiece(sel_piece, selx, sely);

+      }

+      glutPostRedisplay();

+      break;

+    case GLUT_MIDDLE_BUTTON:

+      middle_mouse = GL_TRUE;

+      glutPostRedisplay();

+      break;

+    }

+  } else {

+    if (left_mouse) {

+      left_mouse = GL_FALSE;

+      dropSelection();

+      glutPostRedisplay();

+    } else if (middle_mouse) {

+      middle_mouse = GL_FALSE;

+      glutPostRedisplay();

+    }

+  }

+  motion(x, y);

+}

+

+void

+animate(void)

+{

+  if (spinning) {

+    add_quats(lastquat, curquat, curquat);

+  }

+  glutPostRedisplay();

+  if (solving) {

+    if (!continueSolving()) {

+      solving = 0;

+      glutChangeToMenuEntry(1, (char *)"Solving", 1);

+      glutSetWindowTitle((char *)"glpuzzle");

+    }

+  }

+  if ((!solving && !spinning) || !visible) {

+    glutIdleFunc(NULL);

+  }

+}

+

+void

+changeState(void)

+{

+  if (visible) {

+    if (!solving && !spinning) {

+      glutIdleFunc(NULL);

+    } else {

+      glutIdleFunc(animate);

+    }

+  } else {

+    glutIdleFunc(NULL);

+  }

+}

+

+void

+init(void)

+{

+  static float lmodel_ambient[] =

+  {0.0, 0.0, 0.0, 0.0};

+  static float lmodel_twoside[] =

+  {GL_FALSE};

+  static float lmodel_local[] =

+  {GL_FALSE};

+  static float light0_ambient[] =

+  {0.1, 0.1, 0.1, 1.0};

+  static float light0_diffuse[] =

+  {1.0, 1.0, 1.0, 0.0};

+  static float light0_position[] =

+  {0.8660254, 0.5, 1, 0};

+  static float light0_specular[] =

+  {0.0, 0.0, 0.0, 0.0};

+  static float bevel_mat_ambient[] =

+  {0.0, 0.0, 0.0, 1.0};

+  static float bevel_mat_shininess[] =

+  {40.0};

+  static float bevel_mat_specular[] =

+  {0.0, 0.0, 0.0, 0.0};

+  static float bevel_mat_diffuse[] =

+  {1.0, 0.0, 0.0, 0.0};

+

+  glEnable(GL_CULL_FACE);

+  glCullFace(GL_BACK);

+  glEnable(GL_DEPTH_TEST);

+  glClearDepth(1.0);

+

+  glClearColor(0.5, 0.5, 0.5, 0.0);

+  glLightfv(GL_LIGHT0, GL_AMBIENT, light0_ambient);

+  glLightfv(GL_LIGHT0, GL_DIFFUSE, light0_diffuse);

+  glLightfv(GL_LIGHT0, GL_SPECULAR, light0_specular);

+  glLightfv(GL_LIGHT0, GL_POSITION, light0_position);

+  glEnable(GL_LIGHT0);

+

+  glLightModelfv(GL_LIGHT_MODEL_LOCAL_VIEWER, lmodel_local);

+  glLightModelfv(GL_LIGHT_MODEL_TWO_SIDE, lmodel_twoside);

+  glLightModelfv(GL_LIGHT_MODEL_AMBIENT, lmodel_ambient);

+  glEnable(GL_LIGHTING);

+

+  glMaterialfv(GL_FRONT, GL_AMBIENT, bevel_mat_ambient);

+  glMaterialfv(GL_FRONT, GL_SHININESS, bevel_mat_shininess);

+  glMaterialfv(GL_FRONT, GL_SPECULAR, bevel_mat_specular);

+  glMaterialfv(GL_FRONT, GL_DIFFUSE, bevel_mat_diffuse);

+

+  glColorMaterial(GL_FRONT_AND_BACK, GL_DIFFUSE);

+  glEnable(GL_COLOR_MATERIAL);

+  glShadeModel(GL_FLAT);

+

+  trackball(curquat, 0.0, 0.0, 0.0, 0.0);

+  srandom(time(NULL));

+}

+

+static void

+Usage(void)

+{

+  puts("Usage: puzzle [-s]");

+  puts("   -s:  Run in single buffered mode");

+  exit(-1);

+}

+

+void

+visibility(int v)

+{

+  if (v == GLUT_VISIBLE) {

+    visible = 1;

+  } else {

+    visible = 0;

+  }

+  changeState();

+}

+

+void

+menu(int choice)

+{

+   switch(choice) {

+   case 1:

+      toggleSolve();

+      break;

+   case 2:

+      reset();

+      break;

+   case 3:

+      exit(0);

+      break;

+   }

+}

+

+int

+main(int argc, char **argv)

+{

+  long i;

+

+  glutInit(&argc, argv);

+  for (i = 1; i < argc; i++) {

+    if (argv[i][0] == '-') {

+      switch (argv[i][1]) {

+      case 's':

+        doubleBuffer = 0;

+        break;

+      default:

+        Usage();

+      }

+    } else {

+      Usage();

+    }

+  }

+

+  glutInitWindowSize(W, H);

+  if (doubleBuffer) {

+    glutInitDisplayMode(GLUT_DEPTH | GLUT_RGB | GLUT_DOUBLE | GLUT_MULTISAMPLE);

+  } else {

+    glutInitDisplayMode(GLUT_DEPTH | GLUT_RGB | GLUT_SINGLE | GLUT_MULTISAMPLE);

+  }

+

+  glutCreateWindow("glpuzzle");

+  visible = 1; // added for fltk, bug in original program?

+

+  init();

+

+  glGetIntegerv(GL_VIEWPORT, viewport);

+

+  puts("");

+  puts("r   Reset puzzle");

+  puts("s   Solve puzzle (may take a few seconds to compute)");

+  puts("d   Destroy a piece - makes the puzzle easier");

+  puts("b   Toggles the depth buffer on and off");

+  puts("");

+  puts("Left mouse moves pieces");

+  puts("Middle mouse spins the puzzle");

+  puts("Right mouse has menu");

+

+  glutReshapeFunc(Reshape);

+  glutDisplayFunc(redraw);

+  glutKeyboardFunc(keyboard);

+  glutMotionFunc(motion);

+  glutMouseFunc(mouse);

+  glutVisibilityFunc(visibility);

+  glutCreateMenu(menu);

+  glutAddMenuEntry((char *)"Solve", 1);

+  glutAddMenuEntry((char *)"Reset", 2);

+  glutAddMenuEntry((char *)"Quit", 3);

+  glutAttachMenu(GLUT_RIGHT_BUTTON);

+  glutMainLoop();

+  return 0;             /* ANSI C requires main to return int. */

+}

+

+#endif // added for fltk's distribution

+

+//

+// End of "$Id: glpuzzle.cxx 5845 2007-05-20 00:01:06Z mike $".

+//