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