+\f
+/* Computing normal vectors (thanks to Nat Friedman <ndf@mit.edu>)
+ */
+
+typedef struct vector {
+ GLfloat x, y, z;
+} vector;
+
+typedef struct plane {
+ vector p1, p2, p3;
+} plane;
+
+static void
+vector_set(vector *v, GLfloat x, GLfloat y, GLfloat z)
+{
+ v->x = x;
+ v->y = y;
+ v->z = z;
+}
+
+static void
+vector_cross(vector v1, vector v2, vector *v3)
+{
+ v3->x = (v1.y * v2.z) - (v1.z * v2.y);
+ v3->y = (v1.z * v2.x) - (v1.x * v2.z);
+ v3->z = (v1.x * v2.y) - (v1.y * v2.x);
+}
+
+static void
+vector_subtract(vector v1, vector v2, vector *res)
+{
+ res->x = v1.x - v2.x;
+ res->y = v1.y - v2.y;
+ res->z = v1.z - v2.z;
+}
+
+static void
+plane_normal(plane p, vector *n)
+{
+ vector v1, v2;
+ vector_subtract(p.p1, p.p2, &v1);
+ vector_subtract(p.p1, p.p3, &v2);
+ vector_cross(v2, v1, n);
+}
+
+static void
+do_normal(GLfloat x1, GLfloat y1, GLfloat z1,
+ GLfloat x2, GLfloat y2, GLfloat z2,
+ GLfloat x3, GLfloat y3, GLfloat z3)
+{
+ plane plane;
+ vector n;
+ vector_set(&plane.p1, x1, y1, z1);
+ vector_set(&plane.p2, x2, y2, z2);
+ vector_set(&plane.p3, x3, y3, z3);
+ plane_normal(plane, &n);
+ n.x = -n.x; n.y = -n.y; n.z = -n.z;
+
+ glNormal3f(n.x, n.y, n.z);
+
+#ifdef DEBUG
+ /* Draw a line in the direction of this face's normal. */
+ {
+ GLfloat ax = n.x > 0 ? n.x : -n.x;
+ GLfloat ay = n.y > 0 ? n.y : -n.y;
+ GLfloat az = n.z > 0 ? n.z : -n.z;
+ GLfloat mx = (x1 + x2 + x3) / 3;
+ GLfloat my = (y1 + y2 + y3) / 3;
+ GLfloat mz = (z1 + z2 + z3) / 3;
+ GLfloat xx, yy, zz;
+
+ GLfloat max = ax > ay ? ax : ay;
+ if (az > max) max = az;
+ max *= 2;
+ xx = n.x / max;
+ yy = n.y / max;
+ zz = n.z / max;
+
+ glBegin(GL_LINE_LOOP);
+ glVertex3f(mx, my, mz);
+ glVertex3f(mx+xx, my+yy, mz+zz);
+ glEnd();
+ }
+#endif /* DEBUG */
+}
+
+\f
+
+static void
+triangle (GLfloat x1, GLfloat y1, GLfloat z1,
+ GLfloat x2, GLfloat y2, GLfloat z2,
+ GLfloat x3, GLfloat y3, GLfloat z3,
+ Bool wireframe_p)
+{
+ if (wireframe_p)
+ glBegin (GL_LINE_LOOP);
+ else
+ {
+ do_normal (x1, y1, z1, x2, y2, z2, x3, y3, z3);
+ glBegin (GL_TRIANGLES);
+ }
+ glVertex3f (x1, y1, z1);
+ glVertex3f (x2, y2, z2);
+ glVertex3f (x3, y3, z3);
+ glEnd();
+}
+
+static void
+four_tetras (GL_VECTOR *outer, Bool wireframe_p, int countdown)
+{
+ if (countdown <= 0)
+ {
+ triangle (outer[0].x, outer[0].y, outer[0].z,
+ outer[1].x, outer[1].y, outer[1].z,
+ outer[2].x, outer[2].y, outer[2].z,
+ wireframe_p);
+ triangle (outer[0].x, outer[0].y, outer[0].z,
+ outer[3].x, outer[3].y, outer[3].z,
+ outer[1].x, outer[1].y, outer[1].z,
+ wireframe_p);
+ triangle (outer[0].x, outer[0].y, outer[0].z,
+ outer[2].x, outer[2].y, outer[2].z,
+ outer[3].x, outer[3].y, outer[3].z,
+ wireframe_p);
+ triangle (outer[1].x, outer[1].y, outer[1].z,
+ outer[3].x, outer[3].y, outer[3].z,
+ outer[2].x, outer[2].y, outer[2].z,
+ wireframe_p);
+ }
+ else
+ {
+# define M01 0
+# define M02 1
+# define M03 2
+# define M12 3
+# define M13 4
+# define M23 5
+ GL_VECTOR inner[M23+1];
+ GL_VECTOR corner[4];
+
+ inner[M01].x = (outer[0].x + outer[1].x) / 2.0;
+ inner[M01].y = (outer[0].y + outer[1].y) / 2.0;
+ inner[M01].z = (outer[0].z + outer[1].z) / 2.0;
+
+ inner[M02].x = (outer[0].x + outer[2].x) / 2.0;
+ inner[M02].y = (outer[0].y + outer[2].y) / 2.0;
+ inner[M02].z = (outer[0].z + outer[2].z) / 2.0;
+
+ inner[M03].x = (outer[0].x + outer[3].x) / 2.0;
+ inner[M03].y = (outer[0].y + outer[3].y) / 2.0;
+ inner[M03].z = (outer[0].z + outer[3].z) / 2.0;
+
+ inner[M12].x = (outer[1].x + outer[2].x) / 2.0;
+ inner[M12].y = (outer[1].y + outer[2].y) / 2.0;
+ inner[M12].z = (outer[1].z + outer[2].z) / 2.0;
+
+ inner[M13].x = (outer[1].x + outer[3].x) / 2.0;
+ inner[M13].y = (outer[1].y + outer[3].y) / 2.0;
+ inner[M13].z = (outer[1].z + outer[3].z) / 2.0;
+
+ inner[M23].x = (outer[2].x + outer[3].x) / 2.0;
+ inner[M23].y = (outer[2].y + outer[3].y) / 2.0;
+ inner[M23].z = (outer[2].z + outer[3].z) / 2.0;
+
+ countdown--;
+
+ corner[0] = outer[0];
+ corner[1] = inner[M01];
+ corner[2] = inner[M02];
+ corner[3] = inner[M03];
+ four_tetras (corner, wireframe_p, countdown);
+
+ corner[0] = inner[M01];
+ corner[1] = outer[1];
+ corner[2] = inner[M12];
+ corner[3] = inner[M13];
+ four_tetras (corner, wireframe_p, countdown);
+
+ corner[0] = inner[M02];
+ corner[1] = inner[M12];
+ corner[2] = outer[2];
+ corner[3] = inner[M23];
+ four_tetras (corner, wireframe_p, countdown);
+
+ corner[0] = inner[M03];
+ corner[1] = inner[M13];
+ corner[2] = inner[M23];
+ corner[3] = outer[3];
+ four_tetras (corner, wireframe_p, countdown);
+ }
+}
+
+