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  4    /* 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     get_index(fin, &zp->s);
 748     get_index(fin, &zp->c);
 749 }
 750
 751 static void sol_load_swch(FILE *fin, struct s_swch *xp)
 752 {
 753     get_array(fin,  xp->p, 3);
 754     get_float(fin, &xp->r);
 755     get_index(fin, &xp->pi);
 756     get_float(fin, &xp->t0);
 757     get_float(fin, &xp->t);
 758     get_index(fin, &xp->f0);
 759     get_index(fin, &xp->f);
 760     get_index(fin, &xp->i);
 761 }
 762
 763 static void sol_load_bill(FILE *fin, struct s_bill *rp)
 764 {
 765     get_index(fin, &rp->fl);
 766     get_index(fin, &rp->mi);
 767     get_float(fin, &rp->t);
 768     get_float(fin, &rp->d);
 769     get_array(fin,  rp->w,  3);
 770     get_array(fin,  rp->h,  3);
 771     get_array(fin,  rp->rx, 3);
 772     get_array(fin,  rp->ry, 3);
 773     get_array(fin,  rp->rz, 3);
 774 }
 775
 776 static void sol_load_jump(FILE *fin, struct s_jump *jp)
 777 {
 778     get_array(fin,  jp->p, 3);
 779     get_array(fin,  jp->q, 3);
 780     get_float(fin, &jp->r);
 781 }
 782
 783 static void sol_load_ball(FILE *fin, struct s_ball *bp)
 784 {
 785     get_array(fin,  bp->e[0], 3);
 786     get_array(fin,  bp->e[1], 3);
 787     get_array(fin,  bp->e[2], 3);
 788     get_array(fin,  bp->p,    3);
 789     get_float(fin, &bp->r);
 790 }
 791
 792 static void sol_load_view(FILE *fin, struct s_view *wp)
 793 {
 794     get_array(fin,  wp->p, 3);
 795     get_array(fin,  wp->q, 3);
 796 }
 797
 798 static int sol_load_file(FILE *fin, struct s_file *fp)
 799 {
 800     int i;
 801     int magic;
 802     int version;
 803
 804     get_index(fin, &magic);
 805     get_index(fin, &version);
 806     if (magic != MAGIC || version != SOL_VERSION)
 807         return 0;
 808
 809     get_index(fin, &fp->mc);
 810     get_index(fin, &fp->vc);
 811     get_index(fin, &fp->ec);
 812     get_index(fin, &fp->sc);
 813     get_index(fin, &fp->tc);
 814     get_index(fin, &fp->gc);
 815     get_index(fin, &fp->lc);
 816     get_index(fin, &fp->nc);
 817     get_index(fin, &fp->pc);
 818     get_index(fin, &fp->bc);
 819     get_index(fin, &fp->cc);
 820     get_index(fin, &fp->zc);
 821     get_index(fin, &fp->jc);
 822     get_index(fin, &fp->xc);
 823     get_index(fin, &fp->rc);
 824     get_index(fin, &fp->uc);
 825     get_index(fin, &fp->wc);
 826     get_index(fin, &fp->ic);
 827     get_index(fin, &fp->ac);
 828
 829     if (fp->mc)
 830         fp->mv = (struct s_mtrl *) calloc(fp->mc, sizeof (struct s_mtrl));
 831     if (fp->vc)
 832         fp->vv = (struct s_vert *) calloc(fp->vc, sizeof (struct s_vert));
 833     if (fp->ec)
 834         fp->ev = (struct s_edge *) calloc(fp->ec, sizeof (struct s_edge));
 835     if (fp->sc)
 836         fp->sv = (struct s_side *) calloc(fp->sc, sizeof (struct s_side));
 837     if (fp->tc)
 838         fp->tv = (struct s_texc *) calloc(fp->tc, sizeof (struct s_texc));
 839     if (fp->gc)
 840         fp->gv = (struct s_geom *) calloc(fp->gc, sizeof (struct s_geom));
 841     if (fp->lc)
 842         fp->lv = (struct s_lump *) calloc(fp->lc, sizeof (struct s_lump));
 843     if (fp->nc)
 844         fp->nv = (struct s_node *) calloc(fp->nc, sizeof (struct s_node));
 845     if (fp->pc)
 846         fp->pv = (struct s_path *) calloc(fp->pc, sizeof (struct s_path));
 847     if (fp->bc)
 848         fp->bv = (struct s_body *) calloc(fp->bc, sizeof (struct s_body));
 849     if (fp->cc)
 850         fp->cv = (struct s_coin *) calloc(fp->cc, sizeof (struct s_coin));
 851     if (fp->zc)
 852         fp->zv = (struct s_goal *) calloc(fp->zc, sizeof (struct s_goal));
 853     if (fp->jc)
 854         fp->jv = (struct s_jump *) calloc(fp->jc, sizeof (struct s_jump));
 855     if (fp->xc)
 856         fp->xv = (struct s_swch *) calloc(fp->xc, sizeof (struct s_swch));
 857     if (fp->rc)
 858         fp->rv = (struct s_bill *) calloc(fp->rc, sizeof (struct s_bill));
 859     if (fp->uc)
 860         fp->uv = (struct s_ball *) calloc(fp->uc, sizeof (struct s_ball));
 861     if (fp->wc)
 862         fp->wv = (struct s_view *) calloc(fp->wc, sizeof (struct s_view));
 863     if (fp->ic)
 864         fp->iv = (int           *) calloc(fp->ic, sizeof (int));
 865     if (fp->ac)
 866         fp->av = (char          *) calloc(fp->ac, sizeof (char));
 867
 868     for (i = 0; i < fp->mc; i++) sol_load_mtrl(fin, fp->mv + i);
 869     for (i = 0; i < fp->vc; i++) sol_load_vert(fin, fp->vv + i);
 870     for (i = 0; i < fp->ec; i++) sol_load_edge(fin, fp->ev + i);
 871     for (i = 0; i < fp->sc; i++) sol_load_side(fin, fp->sv + i);
 872     for (i = 0; i < fp->tc; i++) sol_load_texc(fin, fp->tv + i);
 873     for (i = 0; i < fp->gc; i++) sol_load_geom(fin, fp->gv + i);
 874     for (i = 0; i < fp->lc; i++) sol_load_lump(fin, fp->lv + i);
 875     for (i = 0; i < fp->nc; i++) sol_load_node(fin, fp->nv + i);
 876     for (i = 0; i < fp->pc; i++) sol_load_path(fin, fp->pv + i);
 877     for (i = 0; i < fp->bc; i++) sol_load_body(fin, fp->bv + i);
 878     for (i = 0; i < fp->cc; i++) sol_load_coin(fin, fp->cv + i);
 879     for (i = 0; i < fp->zc; i++) sol_load_goal(fin, fp->zv + i);
 880     for (i = 0; i < fp->jc; i++) sol_load_jump(fin, fp->jv + i);
 881     for (i = 0; i < fp->xc; i++) sol_load_swch(fin, fp->xv + i);
 882     for (i = 0; i < fp->rc; i++) sol_load_bill(fin, fp->rv + i);
 883     for (i = 0; i < fp->uc; i++) sol_load_ball(fin, fp->uv + i);
 884     for (i = 0; i < fp->wc; i++) sol_load_view(fin, fp->wv + i);
 885     for (i = 0; i < fp->ic; i++) get_index(fin, fp->iv + i);
 886
 887     if (fp->ac) fread(fp->av, 1, fp->ac, fin);
 888
 889     return 1;
 890 }
 891
 892 int sol_load_only_file(struct s_file *fp, const char *filename)
 893 {
 894     FILE *fin;
 895     int res = 0;
 896
 897     if ((fin = fopen(filename, FMODE_RB)))
 898     {
 899         res = sol_load_file(fin, fp);
 900         fclose(fin);
 901     }
 902     return res;
 903 }
 904
 905 int sol_load(struct s_file *fp, const char *filename, int k, int s)
 906 {
 907     FILE *fin;
 908     int res = 0;
 909
 910     if ((fin = fopen(filename, FMODE_RB)))
 911     {
 912         if (sol_load_file(fin, fp))
 913         {
 914             res = 1;
 915             sol_load_textures(fp, k);
 916             sol_load_objects (fp, s);
 917         }
 918
 919         fclose(fin);
 920     }
 921     return res;
 922 }
 923
 924 /*---------------------------------------------------------------------------*/
 925
 926 static void sol_stor_mtrl(FILE *fout, struct s_mtrl *mp)
 927 {
 928     put_array(fout,  mp->a, 4);
 929     put_array(fout,  mp->d, 4);
 930     put_array(fout,  mp->s, 4);
 931     put_array(fout,  mp->e, 4);
 932     put_array(fout,  mp->h, 1);
 933     put_index(fout, &mp->fl);
 934
 935     fwrite(mp->f, 1, PATHMAX, fout);
 936 }
 937
 938 static void sol_stor_vert(FILE *fout, struct s_vert *vp)
 939 {
 940     put_array(fout,  vp->p, 3);
 941 }
 942
 943 static void sol_stor_edge(FILE *fout, struct s_edge *ep)
 944 {
 945     put_index(fout, &ep->vi);
 946     put_index(fout, &ep->vj);
 947 }
 948
 949 static void sol_stor_side(FILE *fout, struct s_side *sp)
 950 {
 951     put_array(fout,  sp->n, 3);
 952     put_float(fout, &sp->d);
 953 }
 954
 955 static void sol_stor_texc(FILE *fout, struct s_texc *tp)
 956 {
 957     put_array(fout,  tp->u, 2);
 958 }
 959
 960 static void sol_stor_geom(FILE *fout, struct s_geom *gp)
 961 {
 962     put_index(fout, &gp->mi);
 963     put_index(fout, &gp->ti);
 964     put_index(fout, &gp->si);
 965     put_index(fout, &gp->vi);
 966     put_index(fout, &gp->tj);
 967     put_index(fout, &gp->sj);
 968     put_index(fout, &gp->vj);
 969     put_index(fout, &gp->tk);
 970     put_index(fout, &gp->sk);
 971     put_index(fout, &gp->vk);
 972 }
 973
 974 static void sol_stor_lump(FILE *fout, struct s_lump *lp)
 975 {
 976     put_index(fout, &lp->fl);
 977     put_index(fout, &lp->v0);
 978     put_index(fout, &lp->vc);
 979     put_index(fout, &lp->e0);
 980     put_index(fout, &lp->ec);
 981     put_index(fout, &lp->g0);
 982     put_index(fout, &lp->gc);
 983     put_index(fout, &lp->s0);
 984     put_index(fout, &lp->sc);
 985 }
 986
 987 static void sol_stor_node(FILE *fout, struct s_node *np)
 988 {
 989     put_index(fout, &np->si);
 990     put_index(fout, &np->ni);
 991     put_index(fout, &np->nj);
 992     put_index(fout, &np->l0);
 993     put_index(fout, &np->lc);
 994 }
 995
 996 static void sol_stor_path(FILE *fout, struct s_path *pp)
 997 {
 998     put_array(fout,  pp->p, 3);
 999     put_float(fout, &pp->t);
1000     put_index(fout, &pp->pi);
1001     put_index(fout, &pp->f);
1002 }
1003
1004 static void sol_stor_body(FILE *fout, struct s_body *bp)
1005 {
1006     put_index(fout, &bp->pi);
1007     put_index(fout, &bp->ni);
1008     put_index(fout, &bp->l0);
1009     put_index(fout, &bp->lc);
1010     put_index(fout, &bp->g0);
1011     put_index(fout, &bp->gc);
1012 }
1013
1014 static void sol_stor_coin(FILE *fout, struct s_coin *cp)
1015 {
1016     put_array(fout,  cp->p, 3);
1017     put_index(fout, &cp->n);
1018 }
1019
1020 static void sol_stor_goal(FILE *fout, struct s_goal *zp)
1021 {
1022     put_array(fout,  zp->p, 3);
1023     put_float(fout, &zp->r);
1024     put_index(fout, &zp->s);
1025     put_index(fout, &zp->c);
1026 }
1027
1028 static void sol_stor_swch(FILE *fout, struct s_swch *xp)
1029 {
1030     put_array(fout,  xp->p, 3);
1031     put_float(fout, &xp->r);
1032     put_index(fout, &xp->pi);
1033     put_float(fout, &xp->t0);
1034     put_float(fout, &xp->t);
1035     put_index(fout, &xp->f0);
1036     put_index(fout, &xp->f);
1037     put_index(fout, &xp->i);
1038 }
1039
1040 static void sol_stor_bill(FILE *fout, struct s_bill *rp)
1041 {
1042     put_index(fout, &rp->fl);
1043     put_index(fout, &rp->mi);
1044     put_float(fout, &rp->t);
1045     put_float(fout, &rp->d);
1046     put_array(fout,  rp->w,  3);
1047     put_array(fout,  rp->h,  3);
1048     put_array(fout,  rp->rx, 3);
1049     put_array(fout,  rp->ry, 3);
1050     put_array(fout,  rp->rz, 3);
1051 }
1052
1053 static void sol_stor_jump(FILE *fout, struct s_jump *jp)
1054 {
1055     put_array(fout,  jp->p, 3);
1056     put_array(fout,  jp->q, 3);
1057     put_float(fout, &jp->r);
1058 }
1059
1060 static void sol_stor_ball(FILE *fout, struct s_ball *bp)
1061 {
1062     put_array(fout,  bp->e[0], 3);
1063     put_array(fout,  bp->e[1], 3);
1064     put_array(fout,  bp->e[2], 3);
1065     put_array(fout,  bp->p,    3);
1066     put_float(fout, &bp->r);
1067 }
1068
1069 static void sol_stor_view(FILE *fout, struct s_view *wp)
1070 {
1071     put_array(fout,  wp->p, 3);
1072     put_array(fout,  wp->q, 3);
1073 }
1074
1075 static void sol_stor_file(FILE *fin, struct s_file *fp)
1076 {
1077     int i;
1078     int magic   = MAGIC;
1079     int version = SOL_VERSION;
1080
1081     put_index(fin, &magic);
1082     put_index(fin, &version);
1083
1084     put_index(fin, &fp->mc);
1085     put_index(fin, &fp->vc);
1086     put_index(fin, &fp->ec);
1087     put_index(fin, &fp->sc);
1088     put_index(fin, &fp->tc);
1089     put_index(fin, &fp->gc);
1090     put_index(fin, &fp->lc);
1091     put_index(fin, &fp->nc);
1092     put_index(fin, &fp->pc);
1093     put_index(fin, &fp->bc);
1094     put_index(fin, &fp->cc);
1095     put_index(fin, &fp->zc);
1096     put_index(fin, &fp->jc);
1097     put_index(fin, &fp->xc);
1098     put_index(fin, &fp->rc);
1099     put_index(fin, &fp->uc);
1100     put_index(fin, &fp->wc);
1101     put_index(fin, &fp->ic);
1102     put_index(fin, &fp->ac);
1103
1104     for (i = 0; i < fp->mc; i++) sol_stor_mtrl(fin, fp->mv + i);
1105     for (i = 0; i < fp->vc; i++) sol_stor_vert(fin, fp->vv + i);
1106     for (i = 0; i < fp->ec; i++) sol_stor_edge(fin, fp->ev + i);
1107     for (i = 0; i < fp->sc; i++) sol_stor_side(fin, fp->sv + i);
1108     for (i = 0; i < fp->tc; i++) sol_stor_texc(fin, fp->tv + i);
1109     for (i = 0; i < fp->gc; i++) sol_stor_geom(fin, fp->gv + i);
1110     for (i = 0; i < fp->lc; i++) sol_stor_lump(fin, fp->lv + i);
1111     for (i = 0; i < fp->nc; i++) sol_stor_node(fin, fp->nv + i);
1112     for (i = 0; i < fp->pc; i++) sol_stor_path(fin, fp->pv + i);
1113     for (i = 0; i < fp->bc; i++) sol_stor_body(fin, fp->bv + i);
1114     for (i = 0; i < fp->cc; i++) sol_stor_coin(fin, fp->cv + i);
1115     for (i = 0; i < fp->zc; i++) sol_stor_goal(fin, fp->zv + i);
1116     for (i = 0; i < fp->jc; i++) sol_stor_jump(fin, fp->jv + i);
1117     for (i = 0; i < fp->xc; i++) sol_stor_swch(fin, fp->xv + i);
1118     for (i = 0; i < fp->rc; i++) sol_stor_bill(fin, fp->rv + i);
1119     for (i = 0; i < fp->uc; i++) sol_stor_ball(fin, fp->uv + i);
1120     for (i = 0; i < fp->wc; i++) sol_stor_view(fin, fp->wv + i);
1121     for (i = 0; i < fp->ic; i++) put_index(fin, fp->iv + i);
1122
1123     fwrite(fp->av, 1, fp->ac, fin);
1124 }
1125
1126 /*---------------------------------------------------------------------------*/
1127
1128 int sol_stor(struct s_file *fp, const char *filename)
1129 {
1130     FILE *fout;
1131
1132     if ((fout = fopen(filename, FMODE_WB)))
1133     {
1134         sol_stor_file(fout, fp);
1135         fclose(fout);
1136
1137         return 1;
1138     }
1139     return 0;
1140 }
1141
1142 void sol_free(struct s_file *fp)
1143 {
1144     int i;
1145
1146     for (i = 0; i < fp->mc; i++)
1147     {
1148         if (glIsTexture(fp->mv[i].o))
1149             glDeleteTextures(1, &fp->mv[i].o);
1150     }
1151
1152     for (i = 0; i < fp->bc; i++)
1153     {
1154         if (glIsList(fp->bv[i].ol))
1155             glDeleteLists(fp->bv[i].ol, 1);
1156         if (glIsList(fp->bv[i].tl))
1157             glDeleteLists(fp->bv[i].tl, 1);
1158         if (glIsList(fp->bv[i].rl))
1159             glDeleteLists(fp->bv[i].rl, 1);
1160     }
1161
1162     if (fp->mv) free(fp->mv);
1163     if (fp->vv) free(fp->vv);
1164     if (fp->ev) free(fp->ev);
1165     if (fp->sv) free(fp->sv);
1166     if (fp->tv) free(fp->tv);
1167     if (fp->gv) free(fp->gv);
1168     if (fp->lv) free(fp->lv);
1169     if (fp->nv) free(fp->nv);
1170     if (fp->pv) free(fp->pv);
1171     if (fp->bv) free(fp->bv);
1172     if (fp->cv) free(fp->cv);
1173     if (fp->zv) free(fp->zv);
1174     if (fp->jv) free(fp->jv);
1175     if (fp->xv) free(fp->xv);
1176     if (fp->rv) free(fp->rv);
1177     if (fp->uv) free(fp->uv);
1178     if (fp->wv) free(fp->wv);
1179     if (fp->av) free(fp->av);
1180     if (fp->iv) free(fp->iv);
1181
1182     memset(fp, 0, sizeof (struct s_file));
1183 }
1184
1185 /*---------------------------------------------------------------------------*/
1186 /* Solves (p + v * t) . (p + v * t) == r * r for smallest t.                 */
1187
1188 static float v_sol(const float p[3], const float v[3], float r)
1189 {
1190     float a = v_dot(v, v);
1191     float b = v_dot(v, p) * 2.0f;
1192     float c = v_dot(p, p) - r * r;
1193     float d = b * b - 4.0f * a * c;
1194
1195     if (a == 0.0f) return LARGE;
1196     if (d <  0.0f) return LARGE;
1197
1198     if (d == 0.0f)
1199         return -b * 0.5f / a;
1200     else
1201     {
1202         float t0 = 0.5f * (-b - fsqrtf(d)) / a;
1203         float t1 = 0.5f * (-b + fsqrtf(d)) / a;
1204         float t  = (t0 < t1) ? t0 : t1;
1205
1206         return (t < 0.0f) ? LARGE : t;
1207     }
1208 }
1209
1210 /*---------------------------------------------------------------------------*/
1211
1212 /*
1213  * Compute the  earliest time  and position of  the intersection  of a
1214  * sphere and a vertex.
1215  *
1216  * The sphere has radius R and moves along vector V from point P.  The
1217  * vertex moves  along vector  W from point  Q in a  coordinate system
1218  * based at O.
1219  */
1220 static float v_vert(float Q[3],
1221                     const float o[3],
1222                     const float q[3],
1223                     const float w[3],
1224                     const float p[3],
1225                     const float v[3], float r)
1226 {
1227     float O[3], P[3], V[3];
1228     float t = LARGE;
1229
1230     v_add(O, o, q);
1231     v_sub(P, p, O);
1232     v_sub(V, v, w);
1233
1234     if (v_dot(P, V) < 0.0f)
1235     {
1236         t = v_sol(P, V, r);
1237
1238         if (t < LARGE)
1239             v_mad(Q, O, w, t);
1240     }
1241     return t;
1242 }
1243
1244 /*
1245  * Compute the  earliest time  and position of  the intersection  of a
1246  * sphere and an edge.
1247  *
1248  * The sphere has radius R and moves along vector V from point P.  The
1249  * edge moves along vector W from point Q in a coordinate system based
1250  * at O.  The edge extends along the length of vector U.
1251  */
1252 static float v_edge(float Q[3],
1253                     const float o[3],
1254                     const float q[3],
1255                     const float u[3],
1256                     const float w[3],
1257                     const float p[3],
1258                     const float v[3], float r)
1259 {
1260     float d[3], e[3];
1261     float P[3], V[3];
1262     float du, eu, uu, s, t;
1263
1264     v_sub(d, p, o);
1265     v_sub(d, d, q);
1266     v_sub(e, v, w);
1267
1268     du = v_dot(d, u);
1269     eu = v_dot(e, u);
1270     uu = v_dot(u, u);
1271
1272     v_mad(P, d, u, -du / uu);
1273     v_mad(V, e, u, -eu / uu);
1274
1275     t = v_sol(P, V, r);
1276     s = (du + eu * t) / uu;
1277
1278     if (0.0f < t && t < LARGE && 0.0f < s && s < 1.0f)
1279     {
1280         v_mad(d, o, w, t);
1281         v_mad(e, q, u, s);
1282         v_add(Q, e, d);
1283     }
1284     else
1285         t = LARGE;
1286
1287     return t;
1288 }
1289
1290 /*
1291  * Compute  the earlist  time and  position of  the intersection  of a
1292  * sphere and a plane.
1293  *
1294  * The sphere has radius R and moves along vector V from point P.  The
1295  * plane  oves  along  vector  W.   The  plane has  normal  N  and  is
1296  * positioned at distance D from the origin O along that normal.
1297  */
1298 static float v_side(float Q[3],
1299                     const float o[3],
1300                     const float w[3],
1301                     const float n[3], float d,
1302                     const float p[3],
1303                     const float v[3], float r)
1304 {
1305     float vn = v_dot(v, n);
1306     float wn = v_dot(w, n);
1307     float t  = LARGE;
1308
1309     if (vn - wn <= 0.0f)
1310     {
1311         float on = v_dot(o, n);
1312         float pn = v_dot(p, n);
1313
1314         float u = (r + d + on - pn) / (vn - wn);
1315         float a = (    d + on - pn) / (vn - wn);
1316
1317         if (0.0f <= u)
1318         {
1319             t = u;
1320
1321             v_mad(Q, p, v, +t);
1322             v_mad(Q, Q, n, -r);
1323         }
1324         else if (0.0f <= a)
1325         {
1326             t = 0;
1327
1328             v_mad(Q, p, v, +t);
1329             v_mad(Q, Q, n, -r);
1330         }
1331     }
1332     return t;
1333 }
1334
1335 /*---------------------------------------------------------------------------*/
1336
1337 /*
1338  * Compute the new  linear and angular velocities of  a bouncing ball.
1339  * Q  gives the  position  of the  point  of impact  and  W gives  the
1340  * velocity of the object being impacted.
1341  */
1342 static float sol_bounce(struct s_ball *up,
1343                         const float q[3],
1344                         const float w[3], float dt)
1345 {
1346     const float kb = 1.10f;
1347     const float ke = 0.70f;
1348     const float km = 0.20f;
1349
1350     float n[3], r[3], d[3], u[3], vn, wn, xn, yn;
1351     float *p = up->p;
1352     float *v = up->v;
1353
1354     /* Find the normal of the impact. */
1355
1356     v_sub(r, p, q);
1357     v_sub(d, v, w);
1358     v_nrm(n, r);
1359
1360     /* Find the new angular velocity. */
1361
1362     v_crs(up->w, d, r);
1363     v_scl(up->w, up->w, -1.0f / (up->r * up->r));
1364
1365     /* Find the new linear velocity. */
1366
1367     vn = v_dot(v, n);
1368     wn = v_dot(w, n);
1369     xn = (vn < 0.0f) ? -vn * ke : vn;
1370     yn = (wn > 0.0f) ?  wn * kb : wn;
1371
1372     v_mad(u, w, n, -wn);
1373     v_mad(v, v, n, -vn);
1374     v_mad(v, v, u, +km * dt);
1375     v_mad(v, v, n, xn + yn);
1376
1377     v_mad(p, q, n, up->r);
1378
1379     /* Return the "energy" of the impact, to determine the sound amplitude. */
1380
1381     return fabsf(v_dot(n, d));
1382 }
1383
1384 /*---------------------------------------------------------------------------*/
1385
1386 /*
1387  * Compute the states of all switches after DT seconds have passed.
1388  */
1389 static void sol_swch_step(struct s_file *fp, float dt)
1390 {
1391     int xi;
1392
1393     for (xi = 0; xi < fp->xc; xi++)
1394     {
1395         struct s_swch *xp = fp->xv + xi;
1396
1397         if (xp->t > 0)
1398         {
1399             xp->t -= dt;
1400
1401             if (xp->t <= 0)
1402             {
1403                 int pi = xp->pi;
1404                 int pj = xp->pi;
1405
1406                 do  /* Tortoise and hare cycle traverser. */
1407                 {
1408                     fp->pv[pi].f = xp->f0;
1409                     fp->pv[pj].f = xp->f0;
1410
1411                     pi = fp->pv[pi].pi;
1412                     pj = fp->pv[pj].pi;
1413                     pj = fp->pv[pj].pi;
1414                 }
1415                 while (pi != pj);
1416
1417                 xp->f = xp->f0;
1418             }
1419         }
1420     }
1421 }
1422
1423 /*
1424  * Compute the positions of all bodies after DT seconds have passed.
1425  */
1426 static void sol_body_step(struct s_file *fp, float dt)
1427 {
1428     int i;
1429
1430     for (i = 0; i < fp->bc; i++)
1431     {
1432         struct s_body *bp = fp->bv + i;
1433         struct s_path *pp = fp->pv + bp->pi;
1434
1435         if (bp->pi >= 0 && pp->f)
1436         {
1437             bp->t += dt;
1438
1439             if (bp->t >= pp->t)
1440             {
1441                 bp->t -= pp->t;
1442                 bp->pi = pp->pi;
1443             }
1444         }
1445     }
1446 }
1447
1448 /*
1449  * Compute the positions of all balls after DT seconds have passed.
1450  */
1451 static void sol_ball_step(struct s_file *fp, float dt)
1452 {
1453     int i;
1454
1455     for (i = 0; i < fp->uc; i++)
1456     {
1457         struct s_ball *up = fp->uv + i;
1458
1459         v_mad(up->p, up->p, up->v, dt);
1460
1461         if (v_len(up->w) > 0.0f)
1462         {
1463             float M[16];
1464             float w[3];
1465             float e[3][3];
1466
1467             v_nrm(w, up->w);
1468             m_rot(M, w, v_len(up->w) * dt);
1469
1470             m_vxfm(e[0], M, up->e[0]);
1471             m_vxfm(e[1], M, up->e[1]);
1472             m_vxfm(e[2], M, up->e[2]);
1473
1474             v_crs(up->e[2], e[0], e[1]);
1475             v_crs(up->e[1], e[2], e[0]);
1476             v_crs(up->e[0], e[1], e[2]);
1477
1478             v_nrm(up->e[0], up->e[0]);
1479             v_nrm(up->e[1], up->e[1]);
1480             v_nrm(up->e[2], up->e[2]);
1481         }
1482     }
1483 }
1484
1485 /*---------------------------------------------------------------------------*/
1486
1487 static float sol_test_vert(float dt,
1488                            float T[3],
1489                            const struct s_ball *up,
1490                            const struct s_vert *vp,
1491                            const float o[3],
1492                            const float w[3])
1493 {
1494     return v_vert(T, o, vp->p, w, up->p, up->v, up->r);
1495 }
1496
1497 static float sol_test_edge(float dt,
1498                            float T[3],
1499                            const struct s_ball *up,
1500                            const struct s_file *fp,
1501                            const struct s_edge *ep,
1502                            const float o[3],
1503                            const float w[3])
1504 {
1505     float q[3];
1506     float u[3];
1507
1508     v_cpy(q, fp->vv[ep->vi].p);
1509     v_sub(u, fp->vv[ep->vj].p,
1510           fp->vv[ep->vi].p);
1511
1512     return v_edge(T, o, q, u, w, up->p, up->v, up->r);
1513 }
1514
1515 static float sol_test_side(float dt,
1516                            float T[3],
1517                            const struct s_ball *up,
1518                            const struct s_file *fp,
1519                            const struct s_lump *lp,
1520                            const struct s_side *sp,
1521                            const float o[3],
1522                            const float w[3])
1523 {
1524     float t = v_side(T, o, w, sp->n, sp->d, up->p, up->v, up->r);
1525     int i;
1526
1527     if (t < dt)
1528         for (i = 0; i < lp->sc; i++)
1529         {
1530             const struct s_side *sq = fp->sv + fp->iv[lp->s0 + i];
1531
1532             if (sp != sq &&
1533                 v_dot(T, sq->n) -
1534                 v_dot(o, sq->n) -
1535                 v_dot(w, sq->n) * t > sq->d)
1536                 return LARGE;
1537         }
1538     return t;
1539 }
1540
1541 /*---------------------------------------------------------------------------*/
1542
1543 static float sol_test_fore(float dt,
1544                            const struct s_ball *up,
1545                            const struct s_side *sp,
1546                            const float o[3],
1547                            const float w[3])
1548 {
1549     float q[3];
1550
1551     /* If the ball is not behind the plane, the test passes. */
1552
1553     v_sub(q, up->p, o);
1554
1555     if (v_dot(q, sp->n) - sp->d + up->r >= 0)
1556         return 1;
1557
1558     /* if the ball is behind the plane but will hit before dt, test passes. */
1559     /*
1560       if (v_side(q, o, w, sp->n, sp->d, up->p, up->v, up->r) < dt)
1561       return 1;
1562     */
1563     /* If the ball is behind but moving toward the plane, test passes. */
1564
1565     if (v_dot(up->v, sp->n) > 0)
1566         return 1;
1567
1568
1569     /* Else, test fails. */
1570
1571     return 0;
1572 }
1573
1574 static float sol_test_back(float dt,
1575                            const struct s_ball *up,
1576                            const struct s_side *sp,
1577                            const float o[3],
1578                            const float w[3])
1579 {
1580     float q[3];
1581
1582     /* If the ball is not in front of the plane, the test passes. */
1583
1584     v_sub(q, up->p, o);
1585
1586     if (v_dot(q, sp->n) - sp->d - up->r <= 0)
1587         return 1;
1588
1589     /* if the ball is behind the plane but will hit before dt, test passes. */
1590     /*
1591       if (v_side(q, o, w, sp->n, sp->d, up->p, up->v, up->r) < dt)
1592       return 1;
1593     */
1594     /* If the ball is in front but moving toward the plane, test passes. */
1595
1596     if (v_dot(up->v, sp->n) < 0)
1597         return 1;
1598
1599
1600     /* Else, test fails. */
1601
1602     return 0;
1603 }
1604
1605 /*---------------------------------------------------------------------------*/
1606
1607 static float sol_test_lump(float dt,
1608                            float T[3],
1609                            const struct s_ball *up,
1610                            const struct s_file *fp,
1611                            const struct s_lump *lp,
1612                            const float o[3],
1613                            const float w[3])
1614 {
1615     float U[3], u, t = dt;
1616     int i;
1617
1618     /* Short circuit a non-solid lump. */
1619
1620     if (lp->fl & L_DETAIL) return t;
1621
1622     /* Test all verts */
1623
1624     if (up->r > 0.0f)
1625         for (i = 0; i < lp->vc; i++)
1626         {
1627             const struct s_vert *vp = fp->vv + fp->iv[lp->v0 + i];
1628
1629             if ((u = sol_test_vert(t, U, up, vp, o, w)) < t)
1630             {
1631                 v_cpy(T, U);
1632                 t = u;
1633             }
1634         }
1635
1636     /* Test all edges */
1637
1638     if (up->r > 0.0f)
1639         for (i = 0; i < lp->ec; i++)
1640         {
1641             const struct s_edge *ep = fp->ev + fp->iv[lp->e0 + i];
1642
1643             if ((u = sol_test_edge(t, U, up, fp, ep, o, w)) < t)
1644             {
1645                 v_cpy(T, U);
1646                 t = u;
1647             }
1648         }
1649
1650     /* Test all sides */
1651
1652     for (i = 0; i < lp->sc; i++)
1653     {
1654         const struct s_side *sp = fp->sv + fp->iv[lp->s0 + i];
1655
1656         if ((u = sol_test_side(t, U, up, fp, lp, sp, o, w)) < t)
1657         {
1658             v_cpy(T, U);
1659             t = u;
1660         }
1661     }
1662     return t;
1663 }
1664
1665 static float sol_test_node(float dt,
1666                            float T[3],
1667                            const struct s_ball *up,
1668                            const struct s_file *fp,
1669                            const struct s_node *np,
1670                            const float o[3],
1671                            const float w[3])
1672 {
1673     float U[3], u, t = dt;
1674     int i;
1675
1676     /* Test all lumps */
1677
1678     for (i = 0; i < np->lc; i++)
1679     {
1680         const struct s_lump *lp = fp->lv + np->l0 + i;
1681
1682         if ((u = sol_test_lump(t, U, up, fp, lp, o, w)) < t)
1683         {
1684             v_cpy(T, U);
1685             t = u;
1686         }
1687     }
1688
1689     /* Test in front of this node */
1690
1691     if (np->ni >= 0 && sol_test_fore(t, up, fp->sv + np->si, o, w))
1692     {
1693         const struct s_node *nq = fp->nv + np->ni;
1694
1695         if ((u = sol_test_node(t, U, up, fp, nq, o, w)) < t)
1696         {
1697             v_cpy(T, U);
1698             t = u;
1699         }
1700     }
1701
1702     /* Test behind this node */
1703
1704     if (np->nj >= 0 && sol_test_back(t, up, fp->sv + np->si, o, w))
1705     {
1706         const struct s_node *nq = fp->nv + np->nj;
1707
1708         if ((u = sol_test_node(t, U, up, fp, nq, o, w)) < t)
1709         {
1710             v_cpy(T, U);
1711             t = u;
1712         }
1713     }
1714
1715     return t;
1716 }
1717
1718 static float sol_test_body(float dt,
1719                            float T[3], float V[3],
1720                            const struct s_ball *up,
1721                            const struct s_file *fp,
1722                            const struct s_body *bp)
1723 {
1724     float U[3], O[3], W[3], u, t = dt;
1725
1726     const struct s_node *np = fp->nv + bp->ni;
1727
1728     sol_body_p(O, fp, bp);
1729     sol_body_v(W, fp, bp);
1730
1731     if ((u = sol_test_node(t, U, up, fp, np, O, W)) < t)
1732     {
1733         v_cpy(T, U);
1734         v_cpy(V, W);
1735         t = u;
1736     }
1737     return t;
1738 }
1739
1740 static float sol_test_file(float dt,
1741                            float T[3], float V[3],
1742                            const struct s_ball *up,
1743                            const struct s_file *fp)
1744 {
1745     float U[3], W[3], u, t = dt;
1746     int i;
1747
1748     for (i = 0; i < fp->bc; i++)
1749     {
1750         const struct s_body *bp = fp->bv + i;
1751
1752         if ((u = sol_test_body(t, U, W, up, fp, bp)) < t)
1753         {
1754             v_cpy(T, U);
1755             v_cpy(V, W);
1756             t = u;
1757         }
1758     }
1759     return t;
1760 }
1761
1762 /*---------------------------------------------------------------------------*/
1763
1764 /*
1765  * Step the physics forward DT  seconds under the influence of gravity
1766  * vector G.  If the ball gets pinched between two moving solids, this
1767  * loop might not terminate.  It  is better to do something physically
1768  * impossible than  to lock up the game.   So, if we make  more than C
1769  * iterations, punt it.
1770  */
1771
1772 float sol_step(struct s_file *fp, const float *g, float dt, int ui, int *m)
1773 {
1774     float P[3], V[3], v[3], r[3], d, e, nt, b = 0.0f, tt = dt;
1775     int c = 16;
1776
1777     if (ui < fp->uc)
1778     {
1779         struct s_ball *up = fp->uv + ui;
1780
1781         /* If the ball is in contact with a surface, apply friction. */
1782
1783         v_cpy(v, up->v);
1784         v_cpy(up->v, g);
1785
1786         if (m && sol_test_file(tt, P, V, up, fp) < 0.0005f)
1787         {
1788             v_cpy(up->v, v);
1789             v_sub(r, P, up->p);
1790
1791             if ((d = v_dot(r, g) / (v_len(r) * v_len(g))) > 0.999f)
1792             {
1793                 if ((e = (v_len(up->v) - dt)) > 0.0f)
1794                 {
1795                     /* Scale the linear velocity. */
1796
1797                     v_nrm(up->v, up->v);
1798                     v_scl(up->v, up->v, e);
1799
1800                     /* Scale the angular velocity. */
1801
1802                     v_sub(v, V, up->v);
1803                     v_crs(up->w, v, r);
1804                     v_scl(up->w, up->w, -1.0f / (up->r * up->r));
1805                 }
1806                 else
1807                 {
1808                     /* Friction has brought the ball to a stop. */
1809
1810                     up->v[0] = 0.0f;
1811                     up->v[1] = 0.0f;
1812                     up->v[2] = 0.0f;
1813
1814                     (*m)++;
1815                 }
1816             }
1817             else v_mad(up->v, v, g, tt);
1818         }
1819         else v_mad(up->v, v, g, tt);
1820
1821         /* Test for collision. */
1822
1823         while (c > 0 && tt > 0 && tt > (nt = sol_test_file(tt, P, V, up, fp)))
1824         {
1825             sol_body_step(fp, nt);
1826             sol_swch_step(fp, nt);
1827             sol_ball_step(fp, nt);
1828
1829             tt -= nt;
1830
1831             if (b < (d = sol_bounce(up, P, V, nt)))
1832                 b = d;
1833
1834             c--;
1835         }
1836
1837         sol_body_step(fp, tt);
1838         sol_swch_step(fp, tt);
1839         sol_ball_step(fp, tt);
1840     }
1841     return b;
1842 }
1843
1844 /*---------------------------------------------------------------------------*/
1845
1846 int sol_coin_test(struct s_file *fp, float *p, float coin_r)
1847 {
1848     const float *ball_p = fp->uv->p;
1849     const float  ball_r = fp->uv->r;
1850     int ci, n;
1851
1852     for (ci = 0; ci < fp->cc; ci++)
1853     {
1854         float r[3];
1855
1856         r[0] = ball_p[0] - fp->cv[ci].p[0];
1857         r[1] = ball_p[1] - fp->cv[ci].p[1];
1858         r[2] = ball_p[2] - fp->cv[ci].p[2];
1859
1860         if (fp->cv[ci].n > 0 && v_len(r) < ball_r + coin_r)
1861         {
1862             p[0] = fp->cv[ci].p[0];
1863             p[1] = fp->cv[ci].p[1];
1864             p[2] = fp->cv[ci].p[2];
1865
1866             n = fp->cv[ci].n;
1867             fp->cv[ci].n = 0;
1868
1869             return n;
1870         }
1871     }
1872     return 0;
1873 }
1874
1875 int sol_goal_test(struct s_file *fp, float *p, int ui)
1876 {
1877     const float *ball_p = fp->uv[ui].p;
1878     const float  ball_r = fp->uv[ui].r;
1879     int zi;
1880
1881     for (zi = 0; zi < fp->zc; zi++)
1882     {
1883         float r[3];
1884
1885         r[0] = ball_p[0] - fp->zv[zi].p[0];
1886         r[1] = ball_p[2] - fp->zv[zi].p[2];
1887         r[2] = 0;
1888
1889         if (v_len(r) < fp->zv[zi].r * 1.1 - ball_r &&
1890             ball_p[1] > fp->zv[zi].p[1] &&
1891             ball_p[1] < fp->zv[zi].p[1] + GOAL_HEIGHT / 2)
1892         {
1893             p[0] = fp->zv[zi].p[0];
1894             p[1] = fp->zv[zi].p[1];
1895             p[2] = fp->zv[zi].p[2];
1896
1897             return 1 + fp->zv[zi].s;
1898         }
1899     }
1900     return 0;
1901 }
1902
1903 int sol_jump_test(struct s_file *fp, float *p, int ui)
1904 /* Test if the ball ui in inside a jump */
1905 /* Return 1 if yes and fill p with the destination position */
1906 /* Return 0 if no */
1907 /* Return 2 if the ball is on the border of a jump */
1908 {
1909     const float *ball_p = fp->uv[ui].p;
1910     const float  ball_r = fp->uv[ui].r;
1911     int ji;
1912     float l;
1913     int res = 0;
1914
1915     for (ji = 0; ji < fp->jc; ji++)
1916     {
1917         float r[3];
1918
1919         r[0] = ball_p[0] - fp->jv[ji].p[0];
1920         r[1] = ball_p[2] - fp->jv[ji].p[2];
1921         r[2] = 0;
1922
1923         l = v_len(r) - fp->jv[ji].r;
1924         if (l < 0 &&
1925             ball_p[1] > fp->jv[ji].p[1] &&
1926             ball_p[1] < fp->jv[ji].p[1] + JUMP_HEIGHT / 2)
1927         {
1928             if (l < - ball_r )
1929             {
1930                 p[0] = fp->jv[ji].q[0] + (ball_p[0] - fp->jv[ji].p[0]);
1931                 p[1] = fp->jv[ji].q[1] + (ball_p[1] - fp->jv[ji].p[1]);
1932                 p[2] = fp->jv[ji].q[2] + (ball_p[2] - fp->jv[ji].p[2]);
1933
1934                 return 1;
1935             }
1936             else
1937                 res = 2;
1938         }
1939     }
1940     return res;
1941 }
1942
1943 int sol_swch_test(struct s_file *fp, int ui)
1944 /* In the sol fp, test and process the event the ball ui enters a switch
1945  * return 1 if a visibla switch is activated
1946  * return 0 else (no switch is activated or only invisible switchs) */
1947 {
1948     const float *ball_p = fp->uv[ui].p;
1949     const float  ball_r = fp->uv[ui].r;
1950     int xi;
1951     float l;
1952     int res = 0; /* result */
1953
1954     for (xi = 0; xi < fp->xc; xi++)
1955     {
1956         struct s_swch *xp = fp->xv + xi;
1957
1958         if (xp->t0 == 0 || xp->f == xp->f0)
1959         {
1960             float r[3];
1961
1962             r[0] = ball_p[0] - xp->p[0];
1963             r[1] = ball_p[2] - xp->p[2];
1964             r[2] = 0;
1965
1966             l = v_len(r) - xp->r;
1967             if (l < ball_r &&
1968                 ball_p[1] > xp->p[1] &&
1969                 ball_p[1] < xp->p[1] + SWCH_HEIGHT / 2)
1970             {
1971                 if (!xp->e && l < - ball_r)
1972                 {
1973                     int pi = xp->pi;
1974                     int pj = xp->pi;
1975
1976                     /* The ball enter */
1977                     if (xp->t0 == 0)
1978                         xp->e = 1;
1979
1980                     /* Toggle the state, update the path. */
1981
1982                     xp->f = xp->f ? 0 : 1;
1983
1984                     do  /* Tortoise and hare cycle traverser. */
1985                     {
1986                         fp->pv[pi].f = xp->f;
1987                         fp->pv[pj].f = xp->f;
1988
1989                         pi = fp->pv[pi].pi;
1990                         pj = fp->pv[pj].pi;
1991                         pj = fp->pv[pj].pi;
1992                     }
1993                     while (pi != pj);
1994
1995                     /* It toggled to non-default state, start the timer. */
1996
1997                     if (xp->f != xp->f0)
1998                         xp->t  = xp->t0;
1999
2000                     /* If visible, set the result */
2001                     if (!xp->i)
2002                         res = 1;
2003                 }
2004             }
2005             else if (xp->e)
2006                 /* A ball go out */
2007                 xp->e = 0;
2008         }
2009     }
2010     return res;
2011 }
2012
2013 /*---------------------------------------------------------------------------*/
2014
2015 void put_file_state(FILE *fout, struct s_file *fp)
2016 {
2017     /* Write the position and orientation of the ball. */
2018
2019     put_array(fout, fp->uv[0].p,    3);
2020     put_array(fout, fp->uv[0].e[0], 3);
2021     put_array(fout, fp->uv[0].e[1], 3);
2022 }
2023
2024 void get_file_state(FILE *fin, struct s_file *fp)
2025 {
2026     /* Read the position and orientation of the ball. */
2027
2028     get_array(fin, fp->uv[0].p,    3);
2029     get_array(fin, fp->uv[0].e[0], 3);
2030     get_array(fin, fp->uv[0].e[1], 3);
2031
2032     /* Compute the 3rd vector of the ball orientatian basis. */
2033
2034     v_crs(fp->uv[0].e[2], fp->uv[0].e[0], fp->uv[0].e[1]);
2035 }
2036
2037 /*---------------------------------------------------------------------------*/
2038