vcs.maemo.org Git - neverball/blob - share/solid.c

   1 /*
   2  * Copyright (C) 2003 Robert Kooima
   3  *
   4  * NEVERBALL is  free software; you can redistribute  it and/or modify
   5  * it under the  terms of the GNU General  Public License as published
   6  * by the Free  Software Foundation; either version 2  of the License,
   7  * or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful, but
  10  * WITHOUT  ANY  WARRANTY;  without   even  the  implied  warranty  of
  11  * MERCHANTABILITY or  FITNESS FOR A PARTICULAR PURPOSE.   See the GNU
  12  * General Public License for more details.
  13  */
  14
  15 #include <SDL.h>
  16 #include <SDL_rwops.h>
  17 #include <SDL_image.h>
  18
  19 #include <stdio.h>
  20 #include <stdlib.h>
  21 #include <string.h>
  22 #include <math.h>
  23
  24 #include "glext.h"
  25 #include "vec3.h"
  26 #include "geom.h"
  27 #include "image.h"
  28 #include "solid.h"
  29 #include "config.h"
  30 #include "binary.h"
  31
  32 #define LARGE 1.0e+5f
  33
  34 /*---------------------------------------------------------------------------*/
  35
  36 static float erp(float t)
  37 {
  38     return 3.0f * t * t - 2.0f * t * t * t;
  39 }
  40
  41 static float derp(float t)
  42 {
  43     return 6.0f * t     - 6.0f * t * t;
  44 }
  45
  46 static void sol_body_v(float v[3],
  47                        const struct s_file *fp,
  48                        const struct s_body *bp)
  49 {
  50     if (bp->pi >= 0 && fp->pv[bp->pi].f)
  51     {
  52         const struct s_path *pp = fp->pv + bp->pi;
  53         const struct s_path *pq = fp->pv + pp->pi;
  54
  55         v_sub(v, pq->p, pp->p);
  56         v_scl(v, v, 1.0f / pp->t);
  57
  58         v_scl(v, v, derp(bp->t / pp->t));
  59     }
  60     else
  61     {
  62         v[0] = 0.0f;
  63         v[1] = 0.0f;
  64         v[2] = 0.0f;
  65     }
  66 }
  67
  68 static void sol_body_p(float p[3],
  69                        const struct s_file *fp,
  70                        const struct s_body *bp)
  71 {
  72     float v[3];
  73
  74     if (bp->pi >= 0)
  75     {
  76         const struct s_path *pp = fp->pv + bp->pi;
  77         const struct s_path *pq = fp->pv + pp->pi;
  78
  79         v_sub(v, pq->p, pp->p);
  80         v_mad(p, pp->p, v, erp(bp->t / pp->t));
  81     }
  82     else
  83     {
  84         p[0] = 0.0f;
  85         p[1] = 0.0f;
  86         p[2] = 0.0f;
  87     }
  88 }
  89
  90 /*---------------------------------------------------------------------------*/
  91
  92 static int sol_enum_mtrl(const struct s_file *fp,
  93                          const struct s_body *bp, int mi)
  94 {
  95     int li, gi, c = 0;
  96
  97     /* Count all lump geoms with this material. */
  98
  99     for (li = 0; li < bp->lc; li++)
 100     {
 101         int g0 = fp->lv[bp->l0 + li].g0;
 102         int gc = fp->lv[bp->l0 + li].gc;
 103
 104         for (gi = 0; gi < gc; gi++)
 105             if (fp->gv[fp->iv[g0 + gi]].mi == mi)
 106                 c++;
 107     }
 108
 109     /* Count all body geoms with this material. */
 110
 111     for (gi = 0; gi < bp->gc; gi++)
 112         if (fp->gv[fp->iv[bp->g0 + gi]].mi == mi)
 113             c++;
 114
 115     return c;
 116 }
 117
 118 static int sol_enum_body(const struct s_file *fp,
 119                            const struct s_body *bp, int fl)
 120 {
 121     int mi, c = 0;
 122
 123     /* Count all geoms with this flag. */
 124
 125     for (mi = 0; mi < fp->mc; mi++)
 126         if (fp->mv[mi].fl & fl)
 127             c = c + sol_enum_mtrl(fp, bp, mi);
 128
 129     return c;
 130 }
 131
 132 /*---------------------------------------------------------------------------*/
 133
 134 static void sol_draw_mtrl(const struct s_file *fp, int i)
 135 {
 136     const struct s_mtrl *mp = fp->mv + i;
 137
 138     glMaterialfv(GL_FRONT_AND_BACK, GL_AMBIENT,   mp->a);
 139     glMaterialfv(GL_FRONT_AND_BACK, GL_DIFFUSE,   mp->d);
 140     glMaterialfv(GL_FRONT_AND_BACK, GL_SPECULAR,  mp->s);
 141     glMaterialfv(GL_FRONT_AND_BACK, GL_EMISSION,  mp->e);
 142     glMaterialfv(GL_FRONT_AND_BACK, GL_SHININESS, mp->h);
 143
 144     if (mp->fl & M_ENVIRONMENT)
 145     {
 146         glEnable(GL_TEXTURE_GEN_S);
 147         glEnable(GL_TEXTURE_GEN_T);
 148
 149         glBindTexture(GL_TEXTURE_2D, mp->o);
 150
 151         glTexGeni(GL_S, GL_TEXTURE_GEN_MODE, GL_SPHERE_MAP);
 152         glTexGeni(GL_T, GL_TEXTURE_GEN_MODE, GL_SPHERE_MAP);
 153     }
 154     else
 155     {
 156         glDisable(GL_TEXTURE_GEN_S);
 157         glDisable(GL_TEXTURE_GEN_T);
 158
 159         glBindTexture(GL_TEXTURE_2D, mp->o);
 160     }
 161
 162     if (mp->fl & M_ADDITIVE)
 163         glBlendFunc(GL_ONE, GL_ONE);
 164     else
 165         glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
 166
 167 }
 168
 169 static void sol_draw_bill(const struct s_file *fp,
 170                           const struct s_bill *rp, float t)
 171 {
 172     float T  = fmodf(t, rp->t) - rp->t / 2;
 173
 174     float w  = rp->w[0] + rp->w[1] * T + rp->w[2] * T * T;
 175     float h  = rp->h[0] + rp->h[1] * T + rp->h[2] * T * T;
 176
 177     if (w > 0 && h > 0)
 178     {
 179         float rx = rp->rx[0] + rp->rx[1] * T + rp->rx[2] * T * T;
 180         float ry = rp->ry[0] + rp->ry[1] * T + rp->ry[2] * T * T;
 181         float rz = rp->rz[0] + rp->rz[1] * T + rp->rz[2] * T * T;
 182
 183         glPushMatrix();
 184         {
 185             float y0 = (rp->fl & B_EDGE) ? 0 : -h / 2;
 186             float y1 = (rp->fl & B_EDGE) ? h : +h / 2;
 187
 188             glRotatef(ry, 0.0f, 1.0f, 0.0f);
 189             glRotatef(rx, 1.0f, 0.0f, 0.0f);
 190             glTranslatef(0.0f, 0.0f, -rp->d);
 191
 192             if (rp->fl & B_FLAT)
 193             {
 194                 glRotatef(-rx - 90.0f, 1.0f, 0.0f, 0.0f);
 195                 glRotatef(-ry,         0.0f, 0.0f, 1.0f);
 196             }
 197             if (rp->fl & B_EDGE)
 198                 glRotatef(-rx,         1.0f, 0.0f, 0.0f);
 199
 200             glRotatef(rz, 0.0f, 0.0f, 1.0f);
 201
 202             sol_draw_mtrl(fp, rp->mi);
 203
 204             glBegin(GL_QUADS);
 205             {
 206                 glTexCoord2f(0.0f, 1.0f); glVertex2f(-w / 2, y0);
 207                 glTexCoord2f(1.0f, 1.0f); glVertex2f(+w / 2, y0);
 208                 glTexCoord2f(1.0f, 0.0f); glVertex2f(+w / 2, y1);
 209                 glTexCoord2f(0.0f, 0.0f); glVertex2f(-w / 2, y1);
 210             }
 211             glEnd();
 212         }
 213         glPopMatrix();
 214     }
 215 }
 216
 217 void sol_back(const struct s_file *fp, float n, float f, float t)
 218 {
 219     int ri;
 220
 221     glPushAttrib(GL_LIGHTING_BIT | GL_DEPTH_BUFFER_BIT);
 222     {
 223         /* Render all billboards in the given range. */
 224
 225         glDisable(GL_LIGHTING);
 226         glDepthMask(GL_FALSE);
 227
 228         for (ri = 0; ri < fp->rc; ri++)
 229             if (n <= fp->rv[ri].d && fp->rv[ri].d < f)
 230                 sol_draw_bill(fp, fp->rv + ri, t);
 231     }
 232     glPopAttrib();
 233 }
 234
 235 /*---------------------------------------------------------------------------*/
 236 /*
 237  * The  following code  renders a  body in  a  ludicrously inefficient
 238  * manner.  It iterates the materials and scans the data structure for
 239  * geometry using each.  This  has the effect of absolutely minimizing
 240  * material  changes,  texture  bindings,  and  Begin/End  pairs,  but
 241  * maximizing trips through the data.
 242  *
 243  * However, this  is only done once  for each level.   The results are
 244  * stored in display lists.  Thus, it is well worth it.
 245  */
 246
 247 static void sol_draw_geom(const struct s_file *fp,
 248                           const struct s_geom *gp, int mi)
 249 {
 250     if (gp->mi == mi)
 251     {
 252         const float *ui = fp->tv[gp->ti].u;
 253         const float *uj = fp->tv[gp->tj].u;
 254         const float *uk = fp->tv[gp->tk].u;
 255
 256         const float *ni = fp->sv[gp->si].n;
 257         const float *nj = fp->sv[gp->sj].n;
 258         const float *nk = fp->sv[gp->sk].n;
 259
 260         const float *vi = fp->vv[gp->vi].p;
 261         const float *vj = fp->vv[gp->vj].p;
 262         const float *vk = fp->vv[gp->vk].p;
 263
 264         glTexCoord2fv(ui);
 265         glNormal3fv(ni);
 266         glVertex3fv(vi);
 267
 268         glTexCoord2fv(uj);
 269         glNormal3fv(nj);
 270         glVertex3fv(vj);
 271
 272         glTexCoord2fv(uk);
 273         glNormal3fv(nk);
 274         glVertex3fv(vk);
 275     }
 276 }
 277
 278 static void sol_draw_lump(const struct s_file *fp,
 279                           const struct s_lump *lp, int mi)
 280 {
 281     int i;
 282
 283     for (i = 0; i < lp->gc; i++)
 284         sol_draw_geom(fp, fp->gv + fp->iv[lp->g0 + i], mi);
 285 }
 286
 287 static void sol_draw_body(const struct s_file *fp,
 288                           const struct s_body *bp, int fl)
 289 {
 290     int mi, li, gi;
 291
 292     /* Iterate all materials of the correct opacity. */
 293
 294     for (mi = 0; mi < fp->mc; mi++)
 295         if (fp->mv[mi].fl & fl)
 296         {
 297             if (sol_enum_mtrl(fp, bp, mi))
 298             {
 299                 /* Set the material state. */
 300
 301                 sol_draw_mtrl(fp, mi);
 302
 303                 /* Render all geometry of that material. */
 304
 305                 glBegin(GL_TRIANGLES);
 306                 {
 307                     for (li = 0; li < bp->lc; li++)
 308                         sol_draw_lump(fp, fp->lv + bp->l0 + li, mi);
 309                     for (gi = 0; gi < bp->gc; gi++)
 310                         sol_draw_geom(fp, fp->gv + fp->iv[bp->g0 + gi], mi);
 311                 }
 312                 glEnd();
 313             }
 314         }
 315 }
 316
 317 static void sol_draw_list(const struct s_file *fp,
 318                           const struct s_body *bp, GLuint list)
 319 {
 320     float p[3];
 321
 322     sol_body_p(p, fp, bp);
 323
 324     glPushMatrix();
 325     {
 326         /* Translate a moving body. */
 327
 328         glTranslatef(p[0], p[1], p[2]);
 329
 330         /* Draw the body. */
 331
 332         glCallList(list);
 333     }
 334     glPopMatrix();
 335 }
 336
 337 void sol_draw(const struct s_file *fp)
 338 {
 339     int bi;
 340
 341     glPushAttrib(GL_TEXTURE_BIT      |
 342                  GL_LIGHTING_BIT     |
 343                  GL_COLOR_BUFFER_BIT |
 344                  GL_DEPTH_BUFFER_BIT);
 345     {
 346         /* Render all obaque geometry into the color and depth buffers. */
 347
 348         for (bi = 0; bi < fp->bc; bi++)
 349             if (fp->bv[bi].ol)
 350                 sol_draw_list(fp, fp->bv + bi, fp->bv[bi].ol);
 351
 352         /* Render all translucent geometry into only the color buffer. */
 353
 354         glDepthMask(GL_FALSE);
 355
 356         glEnable(GL_BLEND);
 357         glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
 358
 359         for (bi = 0; bi < fp->bc; bi++)
 360             if (fp->bv[bi].tl)
 361                 sol_draw_list(fp, fp->bv + bi, fp->bv[bi].tl);
 362     }
 363     glPopAttrib();
 364 }
 365
 366 void sol_refl(const struct s_file *fp)
 367 {
 368     int bi;
 369
 370     glPushAttrib(GL_LIGHTING_BIT);
 371     {
 372         /* Render all reflective geometry into the color and depth buffers. */
 373
 374         glEnable(GL_BLEND);
 375         glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
 376
 377         for (bi = 0; bi < fp->bc; bi++)
 378             if (fp->bv[bi].rl)
 379                 sol_draw_list(fp, fp->bv + bi, fp->bv[bi].rl);
 380     }
 381     glPopAttrib();
 382 }
 383
 384 /*---------------------------------------------------------------------------*/
 385
 386 static void sol_shad_geom(const struct s_file *fp,
 387                           const struct s_geom *gp, int mi)
 388 {
 389     if (gp->mi == mi)
 390     {
 391         const float *vi = fp->vv[gp->vi].p;
 392         const float *vj = fp->vv[gp->vj].p;
 393         const float *vk = fp->vv[gp->vk].p;
 394
 395         glTexCoord2f(vi[0], vi[2]);
 396         glVertex3fv(vi);
 397
 398         glTexCoord2f(vj[0], vj[2]);
 399         glVertex3fv(vj);
 400
 401         glTexCoord2f(vk[0], vk[2]);
 402         glVertex3fv(vk);
 403     }
 404 }
 405
 406 static void sol_shad_lump(const struct s_file *fp,
 407                           const struct s_lump *lp, int mi)
 408 {
 409     int i;
 410
 411     for (i = 0; i < lp->gc; i++)
 412         sol_shad_geom(fp, fp->gv + fp->iv[lp->g0 + i], mi);
 413 }
 414
 415 static void sol_shad_body(const struct s_file *fp,
 416                           const struct s_body *bp, int fl)
 417 {
 418     int mi, li, gi;
 419
 420     glBegin(GL_TRIANGLES);
 421     {
 422         for (mi = 0; mi < fp->mc; mi++)
 423             if (fp->mv[mi].fl & fl)
 424             {
 425                 for (li = 0; li < bp->lc; li++)
 426                     sol_shad_lump(fp, fp->lv + bp->l0 + li, mi);
 427                 for (gi = 0; gi < bp->gc; gi++)
 428                     sol_shad_geom(fp, fp->gv + fp->iv[bp->g0 + gi], mi);
 429             }
 430     }
 431     glEnd();
 432 }
 433
 434 static void sol_shad_list(const struct s_file *fp,
 435                           const struct s_body *bp, GLuint list)
 436 {
 437     float p[3];
 438
 439     sol_body_p(p, fp, bp);
 440
 441     glPushMatrix();
 442     {
 443         /* Translate a moving body. */
 444
 445         glTranslatef(p[0], p[1], p[2]);
 446
 447         /* Translate the shadow on a moving body. */
 448
 449         glMatrixMode(GL_TEXTURE);
 450         {
 451             glPushMatrix();
 452             glTranslatef(p[0], p[2], 0.0f);
 453         }
 454         glMatrixMode(GL_MODELVIEW);
 455
 456         /* Draw the body. */
 457
 458         glCallList(list);
 459
 460         /* Pop the shadow translation. */
 461
 462         glMatrixMode(GL_TEXTURE);
 463         {
 464             glPopMatrix();
 465         }
 466         glMatrixMode(GL_MODELVIEW);
 467     }
 468     glPopMatrix();
 469 }
 470
 471 void sol_shad(const struct s_file *fp)
 472 {
 473     int bi;
 474
 475     glPushAttrib(GL_DEPTH_BUFFER_BIT | GL_LIGHTING_BIT);
 476     {
 477         /* Render all shadowed geometry. */
 478
 479         glEnable(GL_BLEND);
 480         glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
 481
 482         glDepthFunc(GL_LEQUAL);
 483         glDepthMask(GL_FALSE);
 484
 485         for (bi = 0; bi < fp->bc; bi++)
 486             if (fp->bv[bi].sl)
 487                 sol_shad_list(fp, fp->bv + bi, fp->bv[bi].sl);
 488     }
 489     glPopAttrib();
 490 }
 491
 492 /*---------------------------------------------------------------------------*/
 493
 494 static void sol_load_objects(struct s_file *fp, int s)
 495 {
 496     int i;
 497
 498     for (i = 0; i < fp->bc; i++)
 499     {
 500         struct s_body *bp = fp->bv + i;
 501
 502         /* Draw all opaque geometry. */
 503
 504         if (sol_enum_body(fp, bp, M_OPAQUE | M_ENVIRONMENT))
 505         {
 506             fp->bv[i].ol = glGenLists(1);
 507
 508             glNewList(fp->bv[i].ol, GL_COMPILE);
 509             {
 510                 sol_draw_body(fp, fp->bv + i, M_OPAQUE | M_ENVIRONMENT);
 511             }
 512             glEndList();
 513         }
 514         else fp->bv[i].ol = 0;
 515
 516         /* Draw all translucent geometry. */
 517
 518         if (sol_enum_body(fp, bp, M_TRANSPARENT))
 519         {
 520             fp->bv[i].tl = glGenLists(1);
 521
 522             glNewList(fp->bv[i].tl, GL_COMPILE);
 523             {
 524                 sol_draw_body(fp, fp->bv + i, M_TRANSPARENT);
 525             }
 526             glEndList();
 527         }
 528         else fp->bv[i].tl = 0;
 529
 530         /* Draw all reflective geometry. */
 531
 532         if (sol_enum_body(fp, bp, M_REFLECTIVE))
 533         {
 534             fp->bv[i].rl = glGenLists(1);
 535
 536             glNewList(fp->bv[i].rl, GL_COMPILE);
 537             {
 538                 sol_draw_body(fp, fp->bv + i, M_REFLECTIVE);
 539             }
 540             glEndList();
 541         }
 542         else fp->bv[i].rl = 0;
 543
 544         /* Draw all shadowed geometry. */
 545
 546         if (s && sol_enum_body(fp, bp, M_SHADOWED))
 547         {
 548             fp->bv[i].sl = glGenLists(1);
 549
 550             glNewList(fp->bv[i].sl, GL_COMPILE);
 551             {
 552                 sol_shad_body(fp, fp->bv + i, M_SHADOWED);
 553             }
 554             glEndList();
 555         }
 556         else fp->bv[i].sl = 0;
 557     }
 558 }
 559
 560 static SDL_Surface *sol_find_texture(const char *name)
 561 {
 562     char png[MAXSTR];
 563     char tga[MAXSTR];
 564     char jpg[MAXSTR];
 565     SDL_Surface *s;
 566
 567     /* Prefer a lossless copy of the texture over a lossy compression. */
 568
 569     strncpy(png, name, PATHMAX); strcat(png, ".png");
 570     strncpy(tga, name, PATHMAX); strcat(tga, ".tga");
 571     strncpy(jpg, name, PATHMAX); strcat(jpg, ".jpg");
 572
 573     /* Check for a PNG. */
 574
 575     if ((s = IMG_Load(config_data(png))))
 576         return s;
 577
 578     /* Check for a TGA, swapping channels if found. */
 579
 580     if ((s = IMG_Load(config_data(tga))))
 581     {
 582         image_swab(s);
 583         return s;
 584     }
 585
 586     /* Check for a JPG. */
 587
 588     if ((s = IMG_Load(config_data(jpg))))
 589         return s;
 590
 591     return NULL;
 592 }
 593
 594 static void sol_load_textures(struct s_file *fp, int k)
 595 {
 596     SDL_Surface *s;
 597     SDL_Surface *d;
 598
 599     int i;
 600
 601     for (i = 0; i < fp->mc; i++)
 602         if ((s = sol_find_texture(fp->mv[i].f)))
 603         {
 604             GLenum f = (s->format->BitsPerPixel == 32) ? GL_RGBA : GL_RGB;
 605
 606             glGenTextures(1, &fp->mv[i].o);
 607             glBindTexture(GL_TEXTURE_2D, fp->mv[i].o);
 608
 609             if (k > 1)
 610             {
 611                 /* Create a new buffer and copy the scaled image to it. */
 612
 613                 if ((d = image_scale(s, k)))
 614                 {
 615                     glTexImage2D(GL_TEXTURE_2D, 0, f, d->w, d->h, 0, f,
 616                                  GL_UNSIGNED_BYTE, d->pixels);
 617                     SDL_FreeSurface(d);
 618                 }
 619             }
 620             else
 621                 glTexImage2D(GL_TEXTURE_2D, 0, f, s->w, s->h, 0, f,
 622                              GL_UNSIGNED_BYTE, s->pixels);
 623
 624             glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR);
 625             glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_LINEAR);
 626
 627             /* Set the texture to clamp or repeat based on material type. */
 628
 629             if (fp->mv[i].fl & M_CLAMPED)
 630             {
 631                 glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_CLAMP);
 632                 glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_T, GL_CLAMP);
 633             }
 634             else
 635             {
 636                 glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_REPEAT);
 637                 glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_T, GL_REPEAT);
 638             }
 639
 640             SDL_FreeSurface(s);
 641         }
 642 }
 643
 644 /*---------------------------------------------------------------------------*/
 645
 646 static void sol_load_mtrl(FILE *fin, struct s_mtrl *mp)
 647 {
 648     get_array(fin,  mp->a, 4);
 649     get_array(fin,  mp->d, 4);
 650     get_array(fin,  mp->s, 4);
 651     get_array(fin,  mp->e, 4);
 652     get_array(fin,  mp->h, 1);
 653     get_index(fin, &mp->fl);
 654
 655     fread(mp->f, 1, PATHMAX, fin);
 656 }
 657
 658 static void sol_load_vert(FILE *fin, struct s_vert *vp)
 659 {
 660     get_array(fin,  vp->p, 3);
 661 }
 662
 663 static void sol_load_edge(FILE *fin, struct s_edge *ep)
 664 {
 665     get_index(fin, &ep->vi);
 666     get_index(fin, &ep->vj);
 667 }
 668
 669 static void sol_load_side(FILE *fin, struct s_side *sp)
 670 {
 671     get_array(fin,  sp->n, 3);
 672     get_float(fin, &sp->d);
 673 }
 674
 675 static void sol_load_texc(FILE *fin, struct s_texc *tp)
 676 {
 677     get_array(fin,  tp->u, 2);
 678 }
 679
 680 static void sol_load_geom(FILE *fin, struct s_geom *gp)
 681 {
 682     get_index(fin, &gp->mi);
 683     get_index(fin, &gp->ti);
 684     get_index(fin, &gp->si);
 685     get_index(fin, &gp->vi);
 686     get_index(fin, &gp->tj);
 687     get_index(fin, &gp->sj);
 688     get_index(fin, &gp->vj);
 689     get_index(fin, &gp->tk);
 690     get_index(fin, &gp->sk);
 691     get_index(fin, &gp->vk);
 692 }
 693
 694 static void sol_load_lump(FILE *fin, struct s_lump *lp)
 695 {
 696     get_index(fin, &lp->fl);
 697     get_index(fin, &lp->v0);
 698     get_index(fin, &lp->vc);
 699     get_index(fin, &lp->e0);
 700     get_index(fin, &lp->ec);
 701     get_index(fin, &lp->g0);
 702     get_index(fin, &lp->gc);
 703     get_index(fin, &lp->s0);
 704     get_index(fin, &lp->sc);
 705 }
 706
 707 static void sol_load_node(FILE *fin, struct s_node *np)
 708 {
 709     get_index(fin, &np->si);
 710     get_index(fin, &np->ni);
 711     get_index(fin, &np->nj);
 712     get_index(fin, &np->l0);
 713     get_index(fin, &np->lc);
 714 }
 715
 716 static void sol_load_path(FILE *fin, struct s_path *pp)
 717 {
 718     get_array(fin,  pp->p, 3);
 719     get_float(fin, &pp->t);
 720     get_index(fin, &pp->pi);
 721     get_index(fin, &pp->f);
 722 }
 723
 724 static void sol_load_body(FILE *fin, struct s_body *bp)
 725 {
 726     get_index(fin, &bp->pi);
 727     get_index(fin, &bp->ni);
 728     get_index(fin, &bp->l0);
 729     get_index(fin, &bp->lc);
 730     get_index(fin, &bp->g0);
 731     get_index(fin, &bp->gc);
 732 }
 733
 734 static void sol_load_coin(FILE *fin, struct s_coin *cp)
 735 {
 736     get_array(fin,  cp->p, 3);
 737     get_index(fin, &cp->n);
 738 }
 739
 740 static void sol_load_goal(FILE *fin, struct s_goal *zp)
 741 {
 742     get_array(fin,  zp->p, 3);
 743     get_float(fin, &zp->r);
 744 }
 745
 746 static void sol_load_swch(FILE *fin, struct s_swch *xp)
 747 {
 748     get_array(fin,  xp->p, 3);
 749     get_float(fin, &xp->r);
 750     get_index(fin, &xp->pi);
 751     get_float(fin, &xp->t0);
 752     get_float(fin, &xp->t);
 753     get_index(fin, &xp->f0);
 754     get_index(fin, &xp->f);
 755 }
 756
 757 static void sol_load_bill(FILE *fin, struct s_bill *rp)
 758 {
 759     get_index(fin, &rp->fl);
 760     get_index(fin, &rp->mi);
 761     get_float(fin, &rp->t);
 762     get_float(fin, &rp->d);
 763     get_array(fin,  rp->w,  3);
 764     get_array(fin,  rp->h,  3);
 765     get_array(fin,  rp->rx, 3);
 766     get_array(fin,  rp->ry, 3);
 767     get_array(fin,  rp->rz, 3);
 768 }
 769
 770 static void sol_load_jump(FILE *fin, struct s_jump *jp)
 771 {
 772     get_array(fin,  jp->p, 3);
 773     get_array(fin,  jp->q, 3);
 774     get_float(fin, &jp->r);
 775 }
 776
 777 static void sol_load_ball(FILE *fin, struct s_ball *bp)
 778 {
 779     get_array(fin,  bp->e[0], 3);
 780     get_array(fin,  bp->e[1], 3);
 781     get_array(fin,  bp->e[2], 3);
 782     get_array(fin,  bp->p,    3);
 783     get_float(fin, &bp->r);
 784 }
 785
 786 static void sol_load_view(FILE *fin, struct s_view *wp)
 787 {
 788     get_array(fin,  wp->p, 3);
 789     get_array(fin,  wp->q, 3);
 790 }
 791
 792 static void sol_load_file(FILE *fin, struct s_file *fp)
 793 {
 794     int i;
 795
 796     get_index(fin, &fp->mc);
 797     get_index(fin, &fp->vc);
 798     get_index(fin, &fp->ec);
 799     get_index(fin, &fp->sc);
 800     get_index(fin, &fp->tc);
 801     get_index(fin, &fp->gc);
 802     get_index(fin, &fp->lc);
 803     get_index(fin, &fp->nc);
 804     get_index(fin, &fp->pc);
 805     get_index(fin, &fp->bc);
 806     get_index(fin, &fp->cc);
 807     get_index(fin, &fp->zc);
 808     get_index(fin, &fp->jc);
 809     get_index(fin, &fp->xc);
 810     get_index(fin, &fp->rc);
 811     get_index(fin, &fp->uc);
 812     get_index(fin, &fp->wc);
 813     get_index(fin, &fp->ic);
 814     get_index(fin, &fp->ac);
 815
 816     if (fp->mc)
 817         fp->mv = (struct s_mtrl *) calloc(fp->mc, sizeof (struct s_mtrl));
 818     if (fp->vc)
 819         fp->vv = (struct s_vert *) calloc(fp->vc, sizeof (struct s_vert));
 820     if (fp->ec)
 821         fp->ev = (struct s_edge *) calloc(fp->ec, sizeof (struct s_edge));
 822     if (fp->sc)
 823         fp->sv = (struct s_side *) calloc(fp->sc, sizeof (struct s_side));
 824     if (fp->tc)
 825         fp->tv = (struct s_texc *) calloc(fp->tc, sizeof (struct s_texc));
 826     if (fp->gc)
 827         fp->gv = (struct s_geom *) calloc(fp->gc, sizeof (struct s_geom));
 828     if (fp->lc)
 829         fp->lv = (struct s_lump *) calloc(fp->lc, sizeof (struct s_lump));
 830     if (fp->nc)
 831         fp->nv = (struct s_node *) calloc(fp->nc, sizeof (struct s_node));
 832     if (fp->pc)
 833         fp->pv = (struct s_path *) calloc(fp->pc, sizeof (struct s_path));
 834     if (fp->bc)
 835         fp->bv = (struct s_body *) calloc(fp->bc, sizeof (struct s_body));
 836     if (fp->cc)
 837         fp->cv = (struct s_coin *) calloc(fp->cc, sizeof (struct s_coin));
 838     if (fp->zc)
 839         fp->zv = (struct s_goal *) calloc(fp->zc, sizeof (struct s_goal));
 840     if (fp->jc)
 841         fp->jv = (struct s_jump *) calloc(fp->jc, sizeof (struct s_jump));
 842     if (fp->xc)
 843         fp->xv = (struct s_swch *) calloc(fp->xc, sizeof (struct s_swch));
 844     if (fp->rc)
 845         fp->rv = (struct s_bill *) calloc(fp->rc, sizeof (struct s_bill));
 846     if (fp->uc)
 847         fp->uv = (struct s_ball *) calloc(fp->uc, sizeof (struct s_ball));
 848     if (fp->wc)
 849         fp->wv = (struct s_view *) calloc(fp->wc, sizeof (struct s_view));
 850     if (fp->ic)
 851         fp->iv = (int           *) calloc(fp->ic, sizeof (int));
 852     if (fp->ac)
 853         fp->av = (char          *) calloc(fp->ac, sizeof (char));
 854
 855     for (i = 0; i < fp->mc; i++) sol_load_mtrl(fin, fp->mv + i);
 856     for (i = 0; i < fp->vc; i++) sol_load_vert(fin, fp->vv + i);
 857     for (i = 0; i < fp->ec; i++) sol_load_edge(fin, fp->ev + i);
 858     for (i = 0; i < fp->sc; i++) sol_load_side(fin, fp->sv + i);
 859     for (i = 0; i < fp->tc; i++) sol_load_texc(fin, fp->tv + i);
 860     for (i = 0; i < fp->gc; i++) sol_load_geom(fin, fp->gv + i);
 861     for (i = 0; i < fp->lc; i++) sol_load_lump(fin, fp->lv + i);
 862     for (i = 0; i < fp->nc; i++) sol_load_node(fin, fp->nv + i);
 863     for (i = 0; i < fp->pc; i++) sol_load_path(fin, fp->pv + i);
 864     for (i = 0; i < fp->bc; i++) sol_load_body(fin, fp->bv + i);
 865     for (i = 0; i < fp->cc; i++) sol_load_coin(fin, fp->cv + i);
 866     for (i = 0; i < fp->zc; i++) sol_load_goal(fin, fp->zv + i);
 867     for (i = 0; i < fp->jc; i++) sol_load_jump(fin, fp->jv + i);
 868     for (i = 0; i < fp->xc; i++) sol_load_swch(fin, fp->xv + i);
 869     for (i = 0; i < fp->rc; i++) sol_load_bill(fin, fp->rv + i);
 870     for (i = 0; i < fp->uc; i++) sol_load_ball(fin, fp->uv + i);
 871     for (i = 0; i < fp->wc; i++) sol_load_view(fin, fp->wv + i);
 872     for (i = 0; i < fp->ic; i++) get_index(fin, fp->iv + i);
 873
 874     if (fp->ac) fread(fp->av, 1, fp->ac, fin);
 875 }
 876
 877 int sol_load(struct s_file *fp, const char *filename, int k, int s)
 878 {
 879     FILE *fin;
 880
 881     if ((fin = fopen(filename, FMODE_RB)))
 882     {
 883         sol_load_file(fin, fp);
 884         sol_load_textures(fp, k);
 885         sol_load_objects (fp, s);
 886
 887         fclose(fin);
 888
 889         return 1;
 890     }
 891     return 0;
 892 }
 893
 894 /*---------------------------------------------------------------------------*/
 895
 896 static void sol_stor_mtrl(FILE *fout, struct s_mtrl *mp)
 897 {
 898     put_array(fout,  mp->a, 4);
 899     put_array(fout,  mp->d, 4);
 900     put_array(fout,  mp->s, 4);
 901     put_array(fout,  mp->e, 4);
 902     put_array(fout,  mp->h, 1);
 903     put_index(fout, &mp->fl);
 904
 905     fwrite(mp->f, 1, PATHMAX, fout);
 906 }
 907
 908 static void sol_stor_vert(FILE *fout, struct s_vert *vp)
 909 {
 910     put_array(fout,  vp->p, 3);
 911 }
 912
 913 static void sol_stor_edge(FILE *fout, struct s_edge *ep)
 914 {
 915     put_index(fout, &ep->vi);
 916     put_index(fout, &ep->vj);
 917 }
 918
 919 static void sol_stor_side(FILE *fout, struct s_side *sp)
 920 {
 921     put_array(fout,  sp->n, 3);
 922     put_float(fout, &sp->d);
 923 }
 924
 925 static void sol_stor_texc(FILE *fout, struct s_texc *tp)
 926 {
 927     put_array(fout,  tp->u, 2);
 928 }
 929
 930 static void sol_stor_geom(FILE *fout, struct s_geom *gp)
 931 {
 932     put_index(fout, &gp->mi);
 933     put_index(fout, &gp->ti);
 934     put_index(fout, &gp->si);
 935     put_index(fout, &gp->vi);
 936     put_index(fout, &gp->tj);
 937     put_index(fout, &gp->sj);
 938     put_index(fout, &gp->vj);
 939     put_index(fout, &gp->tk);
 940     put_index(fout, &gp->sk);
 941     put_index(fout, &gp->vk);
 942 }
 943
 944 static void sol_stor_lump(FILE *fout, struct s_lump *lp)
 945 {
 946     put_index(fout, &lp->fl);
 947     put_index(fout, &lp->v0);
 948     put_index(fout, &lp->vc);
 949     put_index(fout, &lp->e0);
 950     put_index(fout, &lp->ec);
 951     put_index(fout, &lp->g0);
 952     put_index(fout, &lp->gc);
 953     put_index(fout, &lp->s0);
 954     put_index(fout, &lp->sc);
 955 }
 956
 957 static void sol_stor_node(FILE *fout, struct s_node *np)
 958 {
 959     put_index(fout, &np->si);
 960     put_index(fout, &np->ni);
 961     put_index(fout, &np->nj);
 962     put_index(fout, &np->l0);
 963     put_index(fout, &np->lc);
 964 }
 965
 966 static void sol_stor_path(FILE *fout, struct s_path *pp)
 967 {
 968     put_array(fout,  pp->p, 3);
 969     put_float(fout, &pp->t);
 970     put_index(fout, &pp->pi);
 971     put_index(fout, &pp->f);
 972 }
 973
 974 static void sol_stor_body(FILE *fout, struct s_body *bp)
 975 {
 976     put_index(fout, &bp->pi);
 977     put_index(fout, &bp->ni);
 978     put_index(fout, &bp->l0);
 979     put_index(fout, &bp->lc);
 980     put_index(fout, &bp->g0);
 981     put_index(fout, &bp->gc);
 982 }
 983
 984 static void sol_stor_coin(FILE *fout, struct s_coin *cp)
 985 {
 986     put_array(fout,  cp->p, 3);
 987     put_index(fout, &cp->n);
 988 }
 989
 990 static void sol_stor_goal(FILE *fout, struct s_goal *zp)
 991 {
 992     put_array(fout,  zp->p, 3);
 993     put_float(fout, &zp->r);
 994 }
 995
 996 static void sol_stor_swch(FILE *fout, struct s_swch *xp)
 997 {
 998     put_array(fout,  xp->p, 3);
 999     put_float(fout, &xp->r);
1000     put_index(fout, &xp->pi);
1001     put_float(fout, &xp->t0);
1002     put_float(fout, &xp->t);
1003     put_index(fout, &xp->f0);
1004     put_index(fout, &xp->f);
1005 }
1006
1007 static void sol_stor_bill(FILE *fout, struct s_bill *rp)
1008 {
1009     put_index(fout, &rp->fl);
1010     put_index(fout, &rp->mi);
1011     put_float(fout, &rp->t);
1012     put_float(fout, &rp->d);
1013     put_array(fout,  rp->w,  3);
1014     put_array(fout,  rp->h,  3);
1015     put_array(fout,  rp->rx, 3);
1016     put_array(fout,  rp->ry, 3);
1017     put_array(fout,  rp->rz, 3);
1018 }
1019
1020 static void sol_stor_jump(FILE *fout, struct s_jump *jp)
1021 {
1022     put_array(fout,  jp->p, 3);
1023     put_array(fout,  jp->q, 3);
1024     put_float(fout, &jp->r);
1025 }
1026
1027 static void sol_stor_ball(FILE *fout, struct s_ball *bp)
1028 {
1029     put_array(fout,  bp->e[0], 3);
1030     put_array(fout,  bp->e[1], 3);
1031     put_array(fout,  bp->e[2], 3);
1032     put_array(fout,  bp->p,    3);
1033     put_float(fout, &bp->r);
1034 }
1035
1036 static void sol_stor_view(FILE *fout, struct s_view *wp)
1037 {
1038     put_array(fout,  wp->p, 3);
1039     put_array(fout,  wp->q, 3);
1040 }
1041
1042 static void sol_stor_file(FILE *fin, struct s_file *fp)
1043 {
1044     int i;
1045
1046     put_index(fin, &fp->mc);
1047     put_index(fin, &fp->vc);
1048     put_index(fin, &fp->ec);
1049     put_index(fin, &fp->sc);
1050     put_index(fin, &fp->tc);
1051     put_index(fin, &fp->gc);
1052     put_index(fin, &fp->lc);
1053     put_index(fin, &fp->nc);
1054     put_index(fin, &fp->pc);
1055     put_index(fin, &fp->bc);
1056     put_index(fin, &fp->cc);
1057     put_index(fin, &fp->zc);
1058     put_index(fin, &fp->jc);
1059     put_index(fin, &fp->xc);
1060     put_index(fin, &fp->rc);
1061     put_index(fin, &fp->uc);
1062     put_index(fin, &fp->wc);
1063     put_index(fin, &fp->ic);
1064     put_index(fin, &fp->ac);
1065
1066     for (i = 0; i < fp->mc; i++) sol_stor_mtrl(fin, fp->mv + i);
1067     for (i = 0; i < fp->vc; i++) sol_stor_vert(fin, fp->vv + i);
1068     for (i = 0; i < fp->ec; i++) sol_stor_edge(fin, fp->ev + i);
1069     for (i = 0; i < fp->sc; i++) sol_stor_side(fin, fp->sv + i);
1070     for (i = 0; i < fp->tc; i++) sol_stor_texc(fin, fp->tv + i);
1071     for (i = 0; i < fp->gc; i++) sol_stor_geom(fin, fp->gv + i);
1072     for (i = 0; i < fp->lc; i++) sol_stor_lump(fin, fp->lv + i);
1073     for (i = 0; i < fp->nc; i++) sol_stor_node(fin, fp->nv + i);
1074     for (i = 0; i < fp->pc; i++) sol_stor_path(fin, fp->pv + i);
1075     for (i = 0; i < fp->bc; i++) sol_stor_body(fin, fp->bv + i);
1076     for (i = 0; i < fp->cc; i++) sol_stor_coin(fin, fp->cv + i);
1077     for (i = 0; i < fp->zc; i++) sol_stor_goal(fin, fp->zv + i);
1078     for (i = 0; i < fp->jc; i++) sol_stor_jump(fin, fp->jv + i);
1079     for (i = 0; i < fp->xc; i++) sol_stor_swch(fin, fp->xv + i);
1080     for (i = 0; i < fp->rc; i++) sol_stor_bill(fin, fp->rv + i);
1081     for (i = 0; i < fp->uc; i++) sol_stor_ball(fin, fp->uv + i);
1082     for (i = 0; i < fp->wc; i++) sol_stor_view(fin, fp->wv + i);
1083     for (i = 0; i < fp->ic; i++) put_index(fin, fp->iv + i);
1084
1085     fwrite(fp->av, 1, fp->ac, fin);
1086 }
1087
1088 /*---------------------------------------------------------------------------*/
1089
1090 int sol_stor(struct s_file *fp, const char *filename)
1091 {
1092     FILE *fout;
1093
1094     if ((fout = fopen(filename, FMODE_WB)))
1095     {
1096         sol_stor_file(fout, fp);
1097         fclose(fout);
1098
1099         return 1;
1100     }
1101     return 0;
1102 }
1103
1104 void sol_free(struct s_file *fp)
1105 {
1106     int i;
1107
1108     for (i = 0; i < fp->mc; i++)
1109     {
1110         if (glIsTexture(fp->mv[i].o))
1111             glDeleteTextures(1, &fp->mv[i].o);
1112     }
1113
1114     for (i = 0; i < fp->bc; i++)
1115     {
1116         if (glIsList(fp->bv[i].ol))
1117             glDeleteLists(fp->bv[i].ol, 1);
1118         if (glIsList(fp->bv[i].tl))
1119             glDeleteLists(fp->bv[i].tl, 1);
1120         if (glIsList(fp->bv[i].rl))
1121             glDeleteLists(fp->bv[i].rl, 1);
1122     }
1123
1124     if (fp->mv) free(fp->mv);
1125     if (fp->vv) free(fp->vv);
1126     if (fp->ev) free(fp->ev);
1127     if (fp->sv) free(fp->sv);
1128     if (fp->tv) free(fp->tv);
1129     if (fp->gv) free(fp->gv);
1130     if (fp->lv) free(fp->lv);
1131     if (fp->nv) free(fp->nv);
1132     if (fp->pv) free(fp->pv);
1133     if (fp->bv) free(fp->bv);
1134     if (fp->cv) free(fp->cv);
1135     if (fp->zv) free(fp->zv);
1136     if (fp->jv) free(fp->jv);
1137     if (fp->xv) free(fp->xv);
1138     if (fp->rv) free(fp->rv);
1139     if (fp->uv) free(fp->uv);
1140     if (fp->wv) free(fp->wv);
1141     if (fp->av) free(fp->av);
1142     if (fp->iv) free(fp->iv);
1143
1144     memset(fp, 0, sizeof (struct s_file));
1145 }
1146
1147 /*---------------------------------------------------------------------------*/
1148 /* Solves (p + v * t) . (p + v * t) == r * r for smallest t.                 */
1149
1150 static float v_sol(const float p[3], const float v[3], float r)
1151 {
1152     float a = v_dot(v, v);
1153     float b = v_dot(v, p) * 2.0f;
1154     float c = v_dot(p, p) - r * r;
1155     float d = b * b - 4.0f * a * c;
1156
1157     if (a == 0.0f) return LARGE;
1158     if (d <  0.0f) return LARGE;
1159
1160     if (d == 0.0f)
1161         return -b * 0.5f / a;
1162     else
1163     {
1164         float t0 = 0.5f * (-b - fsqrtf(d)) / a;
1165         float t1 = 0.5f * (-b + fsqrtf(d)) / a;
1166         float t  = (t0 < t1) ? t0 : t1;
1167
1168         return (t < 0.0f) ? LARGE : t;
1169     }
1170 }
1171
1172 /*---------------------------------------------------------------------------*/
1173
1174 /*
1175  * Compute the  earliest time  and position of  the intersection  of a
1176  * sphere and a vertex.
1177  *
1178  * The sphere has radius R and moves along vector V from point P.  The
1179  * vertex moves  along vector  W from point  Q in a  coordinate system
1180  * based at O.
1181  */
1182 static float v_vert(float Q[3],
1183                     const float o[3],
1184                     const float q[3],
1185                     const float w[3],
1186                     const float p[3],
1187                     const float v[3], float r)
1188 {
1189     float O[3], P[3], V[3];
1190     float t = LARGE;
1191
1192     v_add(O, o, q);
1193     v_sub(P, p, O);
1194     v_sub(V, v, w);
1195
1196     if (v_dot(P, V) < 0.0f)
1197     {
1198         t = v_sol(P, V, r);
1199
1200         if (t < LARGE)
1201             v_mad(Q, O, w, t);
1202     }
1203     return t;
1204 }
1205
1206 /*
1207  * Compute the  earliest time  and position of  the intersection  of a
1208  * sphere and an edge.
1209  *
1210  * The sphere has radius R and moves along vector V from point P.  The
1211  * edge moves along vector W from point Q in a coordinate system based
1212  * at O.  The edge extends along the length of vector U.
1213  */
1214 static float v_edge(float Q[3],
1215                     const float o[3],
1216                     const float q[3],
1217                     const float u[3],
1218                     const float w[3],
1219                     const float p[3],
1220                     const float v[3], float r)
1221 {
1222     float d[3], e[3];
1223     float P[3], V[3];
1224     float du, eu, uu, s, t;
1225
1226     v_sub(d, p, o);
1227     v_sub(d, d, q);
1228     v_sub(e, v, w);
1229
1230     du = v_dot(d, u);
1231     eu = v_dot(e, u);
1232     uu = v_dot(u, u);
1233
1234     v_mad(P, d, u, -du / uu);
1235     v_mad(V, e, u, -eu / uu);
1236
1237     t = v_sol(P, V, r);
1238     s = (du + eu * t) / uu;
1239
1240     if (0.0f < t && t < LARGE && 0.0f < s && s < 1.0f)
1241     {
1242         v_mad(d, o, w, t);
1243         v_mad(e, q, u, s);
1244         v_add(Q, e, d);
1245     }
1246     else
1247         t = LARGE;
1248
1249     return t;
1250 }
1251
1252 /*
1253  * Compute  the earlist  time and  position of  the intersection  of a
1254  * sphere and a plane.
1255  *
1256  * The sphere has radius R and moves along vector V from point P.  The
1257  * plane  oves  along  vector  W.   The  plane has  normal  N  and  is
1258  * positioned at distance D from the origin O along that normal.
1259  */
1260 static float v_side(float Q[3],
1261                     const float o[3],
1262                     const float w[3],
1263                     const float n[3], float d,
1264                     const float p[3],
1265                     const float v[3], float r)
1266 {
1267     float vn = v_dot(v, n);
1268     float wn = v_dot(w, n);
1269     float t  = LARGE;
1270
1271     if (vn - wn <= 0.0f)
1272     {
1273         float on = v_dot(o, n);
1274         float pn = v_dot(p, n);
1275
1276         float u = (r + d + on - pn) / (vn - wn);
1277         float a = (    d + on - pn) / (vn - wn);
1278
1279         if (0.0f <= u)
1280         {
1281             t = u;
1282
1283             v_mad(Q, p, v, +t);
1284             v_mad(Q, Q, n, -r);
1285         }
1286         else if (0.0f <= a)
1287         {
1288             t = 0;
1289
1290             v_mad(Q, p, v, +t);
1291             v_mad(Q, Q, n, -r);
1292         }
1293     }
1294     return t;
1295 }
1296
1297 /*---------------------------------------------------------------------------*/
1298
1299 /*
1300  * Compute the new  linear and angular velocities of  a bouncing ball.
1301  * Q  gives the  position  of the  point  of impact  and  W gives  the
1302  * velocity of the object being impacted.
1303  */
1304 static float sol_bounce(struct s_ball *up,
1305                         const float q[3],
1306                         const float w[3], float dt)
1307 {
1308     const float kb = 1.10f;
1309     const float ke = 0.70f;
1310     const float km = 0.20f;
1311
1312     float n[3], r[3], d[3], u[3], vn, wn, xn, yn;
1313     float *p = up->p;
1314     float *v = up->v;
1315
1316     /* Find the normal of the impact. */
1317
1318     v_sub(r, p, q);
1319     v_sub(d, v, w);
1320     v_nrm(n, r);
1321
1322     /* Find the new angular velocity. */
1323
1324     v_crs(up->w, d, r);
1325     v_scl(up->w, up->w, -1.0f / (up->r * up->r));
1326
1327     /* Find the new linear velocity. */
1328
1329     vn = v_dot(v, n);
1330     wn = v_dot(w, n);
1331     xn = (vn < 0.0f) ? -vn * ke : vn;
1332     yn = (wn > 0.0f) ?  wn * kb : wn;
1333
1334     v_mad(u, w, n, -wn);
1335     v_mad(v, v, n, -vn);
1336     v_mad(v, v, u, +km * dt);
1337     v_mad(v, v, n, xn + yn);
1338
1339     v_mad(p, q, n, up->r);
1340
1341     /* Return the "energy" of the impact, to determine the sound amplitude. */
1342
1343     return fabsf(v_dot(n, d));
1344 }
1345
1346 /*---------------------------------------------------------------------------*/
1347
1348 /*
1349  * Compute the states of all switches after DT seconds have passed.
1350  */
1351 static void sol_swch_step(struct s_file *fp, float dt)
1352 {
1353     int xi;
1354
1355     for (xi = 0; xi < fp->xc; xi++)
1356     {
1357         struct s_swch *xp = fp->xv + xi;
1358
1359         if (xp->t > 0)
1360         {
1361             xp->t -= dt;
1362
1363             if (xp->t <= 0)
1364             {
1365                 int pi = xp->pi;
1366                 int pj = xp->pi;
1367
1368                 do  /* Tortoise and hare cycle traverser. */
1369                 {
1370                     fp->pv[pi].f = xp->f0;
1371                     fp->pv[pj].f = xp->f0;
1372
1373                     pi = fp->pv[pi].pi;
1374                     pj = fp->pv[pj].pi;
1375                     pj = fp->pv[pj].pi;
1376                 }
1377                 while (pi != pj);
1378
1379                 xp->f = xp->f0;
1380             }
1381         }
1382     }
1383 }
1384
1385 /*
1386  * Compute the positions of all bodies after DT seconds have passed.
1387  */
1388 static void sol_body_step(struct s_file *fp, float dt)
1389 {
1390     int i;
1391
1392     for (i = 0; i < fp->bc; i++)
1393     {
1394         struct s_body *bp = fp->bv + i;
1395         struct s_path *pp = fp->pv + bp->pi;
1396
1397         if (bp->pi >= 0 && pp->f)
1398         {
1399             bp->t += dt;
1400
1401             if (bp->t >= pp->t)
1402             {
1403                 bp->t -= pp->t;
1404                 bp->pi = pp->pi;
1405             }
1406         }
1407     }
1408 }
1409
1410 /*
1411  * Compute the positions of all balls after DT seconds have passed.
1412  */
1413 static void sol_ball_step(struct s_file *fp, float dt)
1414 {
1415     int i;
1416
1417     for (i = 0; i < fp->uc; i++)
1418     {
1419         struct s_ball *up = fp->uv + i;
1420
1421         v_mad(up->p, up->p, up->v, dt);
1422
1423         if (v_len(up->w) > 0.0f)
1424         {
1425             float M[16];
1426             float w[3];
1427             float e[3][3];
1428
1429             v_nrm(w, up->w);
1430             m_rot(M, w, v_len(up->w) * dt);
1431
1432             m_vxfm(e[0], M, up->e[0]);
1433             m_vxfm(e[1], M, up->e[1]);
1434             m_vxfm(e[2], M, up->e[2]);
1435
1436             v_crs(up->e[2], e[0], e[1]);
1437             v_crs(up->e[1], e[2], e[0]);
1438             v_crs(up->e[0], e[1], e[2]);
1439
1440             v_nrm(up->e[0], up->e[0]);
1441             v_nrm(up->e[1], up->e[1]);
1442             v_nrm(up->e[2], up->e[2]);
1443         }
1444     }
1445 }
1446
1447 /*---------------------------------------------------------------------------*/
1448
1449 static float sol_test_vert(float dt,
1450                            float T[3],
1451                            const struct s_ball *up,
1452                            const struct s_vert *vp,
1453                            const float o[3],
1454                            const float w[3])
1455 {
1456     return v_vert(T, o, vp->p, w, up->p, up->v, up->r);
1457 }
1458
1459 static float sol_test_edge(float dt,
1460                            float T[3],
1461                            const struct s_ball *up,
1462                            const struct s_file *fp,
1463                            const struct s_edge *ep,
1464                            const float o[3],
1465                            const float w[3])
1466 {
1467     float q[3];
1468     float u[3];
1469
1470     v_cpy(q, fp->vv[ep->vi].p);
1471     v_sub(u, fp->vv[ep->vj].p,
1472           fp->vv[ep->vi].p);
1473
1474     return v_edge(T, o, q, u, w, up->p, up->v, up->r);
1475 }
1476
1477 static float sol_test_side(float dt,
1478                            float T[3],
1479                            const struct s_ball *up,
1480                            const struct s_file *fp,
1481                            const struct s_lump *lp,
1482                            const struct s_side *sp,
1483                            const float o[3],
1484                            const float w[3])
1485 {
1486     float t = v_side(T, o, w, sp->n, sp->d, up->p, up->v, up->r);
1487     int i;
1488
1489     if (t < dt)
1490         for (i = 0; i < lp->sc; i++)
1491         {
1492             const struct s_side *sq = fp->sv + fp->iv[lp->s0 + i];
1493
1494             if (sp != sq &&
1495                 v_dot(T, sq->n) -
1496                 v_dot(o, sq->n) -
1497                 v_dot(w, sq->n) * t > sq->d)
1498                 return LARGE;
1499         }
1500     return t;
1501 }
1502
1503 /*---------------------------------------------------------------------------*/
1504
1505 static float sol_test_fore(float dt,
1506                            const struct s_ball *up,
1507                            const struct s_side *sp,
1508                            const float o[3],
1509                            const float w[3])
1510 {
1511     float q[3];
1512
1513     /* If the ball is not behind the plane, the test passes. */
1514
1515     v_sub(q, up->p, o);
1516
1517     if (v_dot(q, sp->n) - sp->d + up->r >= 0)
1518         return 1;
1519
1520     /* if the ball is behind the plane but will hit before dt, test passes. */
1521     /*
1522       if (v_side(q, o, w, sp->n, sp->d, up->p, up->v, up->r) < dt)
1523       return 1;
1524     */
1525     /* If the ball is behind but moving toward the plane, test passes. */
1526
1527     if (v_dot(up->v, sp->n) > 0)
1528         return 1;
1529
1530
1531     /* Else, test fails. */
1532
1533     return 0;
1534 }
1535
1536 static float sol_test_back(float dt,
1537                            const struct s_ball *up,
1538                            const struct s_side *sp,
1539                            const float o[3],
1540                            const float w[3])
1541 {
1542     float q[3];
1543
1544     /* If the ball is not in front of the plane, the test passes. */
1545
1546     v_sub(q, up->p, o);
1547
1548     if (v_dot(q, sp->n) - sp->d - up->r <= 0)
1549         return 1;
1550
1551     /* if the ball is behind the plane but will hit before dt, test passes. */
1552     /*
1553       if (v_side(q, o, w, sp->n, sp->d, up->p, up->v, up->r) < dt)
1554       return 1;
1555     */
1556     /* If the ball is in front but moving toward the plane, test passes. */
1557
1558     if (v_dot(up->v, sp->n) < 0)
1559         return 1;
1560
1561
1562     /* Else, test fails. */
1563
1564     return 0;
1565 }
1566
1567 /*---------------------------------------------------------------------------*/
1568
1569 static float sol_test_lump(float dt,
1570                            float T[3],
1571                            const struct s_ball *up,
1572                            const struct s_file *fp,
1573                            const struct s_lump *lp,
1574                            const float o[3],
1575                            const float w[3])
1576 {
1577     float U[3], u, t = dt;
1578     int i;
1579
1580     /* Short circuit a non-solid lump. */
1581
1582     if (lp->fl & L_DETAIL) return t;
1583
1584     /* Test all verts */
1585
1586     if (up->r > 0.0f)
1587         for (i = 0; i < lp->vc; i++)
1588         {
1589             const struct s_vert *vp = fp->vv + fp->iv[lp->v0 + i];
1590
1591             if ((u = sol_test_vert(t, U, up, vp, o, w)) < t)
1592             {
1593                 v_cpy(T, U);
1594                 t = u;
1595             }
1596         }
1597
1598     /* Test all edges */
1599
1600     if (up->r > 0.0f)
1601         for (i = 0; i < lp->ec; i++)
1602         {
1603             const struct s_edge *ep = fp->ev + fp->iv[lp->e0 + i];
1604
1605             if ((u = sol_test_edge(t, U, up, fp, ep, o, w)) < t)
1606             {
1607                 v_cpy(T, U);
1608                 t = u;
1609             }
1610         }
1611
1612     /* Test all sides */
1613
1614     for (i = 0; i < lp->sc; i++)
1615     {
1616         const struct s_side *sp = fp->sv + fp->iv[lp->s0 + i];
1617
1618         if ((u = sol_test_side(t, U, up, fp, lp, sp, o, w)) < t)
1619         {
1620             v_cpy(T, U);
1621             t = u;
1622         }
1623     }
1624     return t;
1625 }
1626
1627 static float sol_test_node(float dt,
1628                            float T[3],
1629                            const struct s_ball *up,
1630                            const struct s_file *fp,
1631                            const struct s_node *np,
1632                            const float o[3],
1633                            const float w[3])
1634 {
1635     float U[3], u, t = dt;
1636     int i;
1637
1638     /* Test all lumps */
1639
1640     for (i = 0; i < np->lc; i++)
1641     {
1642         const struct s_lump *lp = fp->lv + np->l0 + i;
1643
1644         if ((u = sol_test_lump(t, U, up, fp, lp, o, w)) < t)
1645         {
1646             v_cpy(T, U);
1647             t = u;
1648         }
1649     }
1650
1651     /* Test in front of this node */
1652
1653     if (np->ni >= 0 && sol_test_fore(t, up, fp->sv + np->si, o, w))
1654     {
1655         const struct s_node *nq = fp->nv + np->ni;
1656
1657         if ((u = sol_test_node(t, U, up, fp, nq, o, w)) < t)
1658         {
1659             v_cpy(T, U);
1660             t = u;
1661         }
1662     }
1663
1664     /* Test behind this node */
1665
1666     if (np->nj >= 0 && sol_test_back(t, up, fp->sv + np->si, o, w))
1667     {
1668         const struct s_node *nq = fp->nv + np->nj;
1669
1670         if ((u = sol_test_node(t, U, up, fp, nq, o, w)) < t)
1671         {
1672             v_cpy(T, U);
1673             t = u;
1674         }
1675     }
1676
1677     return t;
1678 }
1679
1680 static float sol_test_body(float dt,
1681                            float T[3], float V[3],
1682                            const struct s_ball *up,
1683                            const struct s_file *fp,
1684                            const struct s_body *bp)
1685 {
1686     float U[3], O[3], W[3], u, t = dt;
1687
1688     const struct s_node *np = fp->nv + bp->ni;
1689
1690     sol_body_p(O, fp, bp);
1691     sol_body_v(W, fp, bp);
1692
1693     if ((u = sol_test_node(t, U, up, fp, np, O, W)) < t)
1694     {
1695         v_cpy(T, U);
1696         v_cpy(V, W);
1697         t = u;
1698     }
1699     return t;
1700 }
1701
1702 static float sol_test_file(float dt,
1703                            float T[3], float V[3],
1704                            const struct s_ball *up,
1705                            const struct s_file *fp)
1706 {
1707     float U[3], W[3], u, t = dt;
1708     int i;
1709
1710     for (i = 0; i < fp->bc; i++)
1711     {
1712         const struct s_body *bp = fp->bv + i;
1713
1714         if ((u = sol_test_body(t, U, W, up, fp, bp)) < t)
1715         {
1716             v_cpy(T, U);
1717             v_cpy(V, W);
1718             t = u;
1719         }
1720     }
1721     return t;
1722 }
1723
1724 /*---------------------------------------------------------------------------*/
1725
1726 /*
1727  * Step the physics forward DT  seconds under the influence of gravity
1728  * vector G.  If the ball gets pinched between two moving solids, this
1729  * loop might not terminate.  It  is better to do something physically
1730  * impossible than  to lock up the game.   So, if we make  more than C
1731  * iterations, punt it.
1732  */
1733
1734 float sol_step(struct s_file *fp, const float *g, float dt, int ui, int *m)
1735 {
1736     float P[3], V[3], v[3], r[3], d, e, nt, b = 0.0f, tt = dt;
1737     int c = 16;
1738
1739     if (ui < fp->uc)
1740     {
1741         struct s_ball *up = fp->uv + ui;
1742
1743         /* If the ball is in contact with a surface, apply friction. */
1744
1745         v_cpy(v, up->v);
1746         v_cpy(up->v, g);
1747
1748         if (m && sol_test_file(tt, P, V, up, fp) < 0.0005f)
1749         {
1750             v_cpy(up->v, v);
1751             v_sub(r, P, up->p);
1752
1753             if ((d = v_dot(r, g) / (v_len(r) * v_len(g))) > 0.999f)
1754             {
1755                 if ((e = (v_len(up->v) - dt)) > 0.0f)
1756                 {
1757                     /* Scale the linear velocity. */
1758
1759                     v_nrm(up->v, up->v);
1760                     v_scl(up->v, up->v, e);
1761
1762                     /* Scale the angular velocity. */
1763
1764                     v_sub(v, V, up->v);
1765                     v_crs(up->w, v, r);
1766                     v_scl(up->w, up->w, -1.0f / (up->r * up->r));
1767                 }
1768                 else
1769                 {
1770                     /* Friction has brought the ball to a stop. */
1771
1772                     up->v[0] = 0.0f;
1773                     up->v[1] = 0.0f;
1774                     up->v[2] = 0.0f;
1775
1776                     (*m)++;
1777                 }
1778             }
1779             else v_mad(up->v, v, g, tt);
1780         }
1781         else v_mad(up->v, v, g, tt);
1782
1783         /* Test for collision. */
1784
1785         while (c > 0 && tt > 0 && tt > (nt = sol_test_file(tt, P, V, up, fp)))
1786         {
1787             sol_body_step(fp, nt);
1788             sol_swch_step(fp, nt);
1789             sol_ball_step(fp, nt);
1790
1791             tt -= nt;
1792
1793             if (b < (d = sol_bounce(up, P, V, nt)))
1794                 b = d;
1795
1796             c--;
1797         }
1798
1799         sol_body_step(fp, tt);
1800         sol_swch_step(fp, tt);
1801         sol_ball_step(fp, tt);
1802     }
1803     return b;
1804 }
1805
1806 /*---------------------------------------------------------------------------*/
1807
1808 int sol_coin_test(struct s_file *fp, float *p, float coin_r)
1809 {
1810     const float *ball_p = fp->uv->p;
1811     const float  ball_r = fp->uv->r;
1812     int ci, n;
1813
1814     for (ci = 0; ci < fp->cc; ci++)
1815     {
1816         float r[3];
1817
1818         r[0] = ball_p[0] - fp->cv[ci].p[0];
1819         r[1] = ball_p[1] - fp->cv[ci].p[1];
1820         r[2] = ball_p[2] - fp->cv[ci].p[2];
1821
1822         if (fp->cv[ci].n > 0 && v_len(r) < ball_r + coin_r)
1823         {
1824             p[0] = fp->cv[ci].p[0];
1825             p[1] = fp->cv[ci].p[1];
1826             p[2] = fp->cv[ci].p[2];
1827
1828             n = fp->cv[ci].n;
1829             fp->cv[ci].n = 0;
1830
1831             return n;
1832         }
1833     }
1834     return 0;
1835 }
1836
1837 int sol_goal_test(struct s_file *fp, float *p, int ui)
1838 {
1839     const float *ball_p = fp->uv[ui].p;
1840     const float  ball_r = fp->uv[ui].r;
1841     int zi;
1842
1843     for (zi = 0; zi < fp->zc; zi++)
1844     {
1845         float r[3];
1846
1847         r[0] = ball_p[0] - fp->zv[zi].p[0];
1848         r[1] = ball_p[2] - fp->zv[zi].p[2];
1849         r[2] = 0;
1850
1851         if (v_len(r) < fp->zv[zi].r * 1.1 - ball_r &&
1852             ball_p[1] > fp->zv[zi].p[1] &&
1853             ball_p[1] < fp->zv[zi].p[1] + GOAL_HEIGHT / 2)
1854         {
1855             p[0] = fp->zv[zi].p[0];
1856             p[1] = fp->zv[zi].p[1];
1857             p[2] = fp->zv[zi].p[2];
1858
1859             return 1;
1860         }
1861     }
1862     return 0;
1863 }
1864
1865 int sol_jump_test(struct s_file *fp, float *p, int ui)
1866 {
1867     const float *ball_p = fp->uv[ui].p;
1868     const float  ball_r = fp->uv[ui].r;
1869     int ji;
1870
1871     for (ji = 0; ji < fp->jc; ji++)
1872     {
1873         float r[3];
1874
1875         r[0] = ball_p[0] - fp->jv[ji].p[0];
1876         r[1] = ball_p[2] - fp->jv[ji].p[2];
1877         r[2] = 0;
1878
1879         if (v_len(r) < fp->jv[ji].r - ball_r &&
1880             ball_p[1] > fp->jv[ji].p[1] &&
1881             ball_p[1] < fp->jv[ji].p[1] + JUMP_HEIGHT / 2)
1882         {
1883             p[0] = fp->jv[ji].q[0] + (ball_p[0] - fp->jv[ji].p[0]);
1884             p[1] = fp->jv[ji].q[1] + (ball_p[1] - fp->jv[ji].p[1]);
1885             p[2] = fp->jv[ji].q[2] + (ball_p[2] - fp->jv[ji].p[2]);
1886
1887             return 1;
1888         }
1889     }
1890     return 0;
1891 }
1892
1893 int sol_swch_test(struct s_file *fp, int flag, int ui)
1894 {
1895     const float *ball_p = fp->uv[ui].p;
1896     const float  ball_r = fp->uv[ui].r;
1897     int xi;
1898     int f = 1;
1899
1900     for (xi = 0; xi < fp->xc; xi++)
1901     {
1902         struct s_swch *xp = fp->xv + xi;
1903
1904         if (xp->t0 == 0 || xp->f == xp->f0)
1905         {
1906             float r[3];
1907
1908             r[0] = ball_p[0] - xp->p[0];
1909             r[1] = ball_p[2] - xp->p[2];
1910             r[2] = 0;
1911
1912             if (v_len(r)  < xp->r - ball_r &&
1913                 ball_p[1] > xp->p[1] &&
1914                 ball_p[1] < xp->p[1] + SWCH_HEIGHT / 2)
1915             {
1916                 if (flag)
1917                 {
1918                     int pi = xp->pi;
1919                     int pj = xp->pi;
1920
1921                     /* Toggle the state, update the path. */
1922
1923                     xp->f = xp->f ? 0 : 1;
1924
1925                     do  /* Tortoise and hare cycle traverser. */
1926                     {
1927                         fp->pv[pi].f = xp->f;
1928                         fp->pv[pj].f = xp->f;
1929
1930                         pi = fp->pv[pi].pi;
1931                         pj = fp->pv[pj].pi;
1932                         pj = fp->pv[pj].pi;
1933                     }
1934                     while (pi != pj);
1935
1936                     /* It toggled to non-default state, start the timer. */
1937
1938                     if (xp->f != xp->f0)
1939                         xp->t  = xp->t0;
1940                 }
1941                 f = 0;
1942             }
1943         }
1944     }
1945     return f;
1946 }
1947
1948 /*---------------------------------------------------------------------------*/
1949
1950 void put_file_state(FILE *fout, struct s_file *fp)
1951 {
1952     /* Write the position and orientation of the ball. */
1953
1954     put_array(fout, fp->uv[0].p,    3);
1955     put_array(fout, fp->uv[0].e[0], 3);
1956     put_array(fout, fp->uv[0].e[1], 3);
1957 }
1958
1959 void get_file_state(FILE *fin, struct s_file *fp)
1960 {
1961     /* Read the position and orientation of the ball. */
1962
1963     get_array(fin, fp->uv[0].p,    3);
1964     get_array(fin, fp->uv[0].e[0], 3);
1965     get_array(fin, fp->uv[0].e[1], 3);
1966
1967     /* Compute the 3rd vector of the ball orientatian basis. */
1968
1969     v_crs(fp->uv[0].e[2], fp->uv[0].e[0], fp->uv[0].e[1]);
1970 }
1971
1972 /*---------------------------------------------------------------------------*/
1973