src/mapc.c

   1 /*
   2  *   Copyright (C) 2003 Robert Kooima
   3  *
   4  *   SUPER EMPTY BALL is free software; you can redistribute it and/or modify
   5  *   it under the terms of the GNU General Public License as published by the
   6  *   Free Software Foundation;  either version 2 of the  License, or (at your
   7  *   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 /*
  16  * I'm not  particularly proud  of this chunk  of code.   It was not  so much
  17  * designed as it was accumulated.
  18  */
  19
  20 #include <SDL/SDL.h>
  21 #include <SDL/SDL_image.h>
  22
  23 #include <stdio.h>
  24 #include <stdlib.h>
  25 #include <string.h>
  26 #include <math.h>
  27
  28 #include "vec3.h"
  29 #include "solid.h"
  30
  31 #define MAXSTR 256
  32 #define MAXKEY 16
  33 #define SCALE  64.0
  34 #define SMALL  0.0000000005
  35
  36 /*
  37  * The overall design  of this map converter is very  stupid, but very simple
  38  * It begins by  assuming that every mtrl, vert, edge, side,  and texc in the
  39  * map is unique.   It then makes an optimizing  pass that discards redundant
  40  * information.   The  result is  optimal,  though  the  process is  terribly
  41  * inefficient.
  42  */
  43
  44 /*---------------------------------------------------------------------------*/
  45
  46 /* Arbitrary limits woo! */
  47
  48 #define MAXM    1024
  49 #define MAXV    4096
  50 #define MAXE    4096
  51 #define MAXS    2048
  52 #define MAXT    4096
  53 #define MAXG    4096
  54 #define MAXL    1024
  55 #define MAXN    1024
  56 #define MAXP    512
  57 #define MAXB    512
  58 #define MAXC    1024
  59 #define MAXU    16
  60 #define MAXI    16384
  61
  62 static void init_file(struct s_file *fp)
  63 {
  64     fp->mc = 0;
  65     fp->vc = 0;
  66     fp->ec = 0;
  67     fp->sc = 0;
  68     fp->tc = 0;
  69     fp->gc = 0;
  70     fp->lc = 0;
  71     fp->nc = 0;
  72     fp->pc = 0;
  73     fp->bc = 0;
  74     fp->cc = 0;
  75     fp->uc = 0;
  76     fp->ic = 0;
  77
  78     fp->mv = (struct s_mtrl *) calloc(MAXM, sizeof (struct s_mtrl));
  79     fp->vv = (struct s_vert *) calloc(MAXV, sizeof (struct s_vert));
  80     fp->ev = (struct s_edge *) calloc(MAXE, sizeof (struct s_edge));
  81     fp->sv = (struct s_side *) calloc(MAXS, sizeof (struct s_side));
  82     fp->tv = (struct s_texc *) calloc(MAXT, sizeof (struct s_texc));
  83     fp->gv = (struct s_geom *) calloc(MAXG, sizeof (struct s_geom));
  84     fp->lv = (struct s_lump *) calloc(MAXL, sizeof (struct s_lump));
  85     fp->nv = (struct s_node *) calloc(MAXN, sizeof (struct s_node));
  86     fp->pv = (struct s_path *) calloc(MAXP, sizeof (struct s_path));
  87     fp->bv = (struct s_body *) calloc(MAXB, sizeof (struct s_body));
  88     fp->cv = (struct s_coin *) calloc(MAXC, sizeof (struct s_coin));
  89     fp->uv = (struct s_ball *) calloc(MAXU, sizeof (struct s_ball));
  90     fp->iv = (int           *) calloc(MAXI, sizeof (int));
  91 }
  92
  93 /*---------------------------------------------------------------------------*/
  94
  95 /*
  96  * The following is  a small symbol table data  structure.  Symbols and their
  97  * integer values are collected in symv and valv.  References and pointers to
  98  * their  unsatisfied integer  values are  collected in  refv and  pntv.  The
  99  * resolve  procedure matches references  to symbols  and fills  waiting ints
 100  * with the proper values.
 101  */
 102
 103 #define MAXSYM 1024
 104
 105 static char symv[MAXSYM][MAXSTR];
 106 static int  valv[MAXSYM];
 107
 108 static char refv[MAXSYM][MAXSTR];
 109 static int *pntv[MAXSYM];
 110
 111 static int   strc = 0;
 112 static int   refc = 0;
 113
 114 static void make_sym(const char *s, int  v)
 115 {
 116     strcpy(symv[strc], s);
 117     valv[strc] = v;
 118     strc++;
 119 }
 120
 121 static void make_ref(const char *r, int *p)
 122 {
 123     strcpy(refv[refc], r);
 124     pntv[refc] = p;
 125     refc++;
 126 }
 127
 128 static void resolve(void)
 129 {
 130     int i, j;
 131
 132     for (i = 0; i < refc; i++)
 133         for (j = 0; j < strc; j++)
 134             if (strcmp(refv[i], symv[j]) == 0)
 135             {
 136                 *(pntv[i]) = valv[j];
 137                 break;
 138             }
 139 }
 140
 141 /*---------------------------------------------------------------------------*/
 142
 143 static void size_image(const char *s, int *w, int *h)
 144 {
 145     SDL_Surface *S = IMG_Load(s);
 146
 147     if (S)
 148     {
 149         *w = S->w;
 150         *h = S->h;
 151
 152         SDL_FreeSurface(S);
 153     }
 154     else
 155     {
 156         *w = 0;
 157         *h = 0;
 158     }
 159 }
 160
 161 /*---------------------------------------------------------------------------*/
 162
 163 static int path_0 = -1;
 164
 165 static double plane_d[MAXS];
 166 static double plane_n[MAXS][3];
 167 static double plane_p[MAXS][3];
 168 static double plane_u[MAXS][3];
 169 static double plane_v[MAXS][3];
 170 static int    plane_f[MAXS];
 171
 172 static void make_plane(int pi, int x0, int y0, int z0,
 173                        int x1, int y1, int z1,
 174                        int x2, int y2, int z2,
 175                        int tu, int tv, int r,
 176                        float su, float sv, int fl, const char *s)
 177 {
 178     static const double base[6][3][3] = {
 179         {{  0,  0,  1 }, {  1,  0,  0 }, {  0, -1,  0 }},
 180         {{  0,  0, -1 }, {  1,  0,  0 }, {  0, -1,  0 }},
 181         {{  1,  0,  0 }, {  0,  0, -1 }, {  0, -1,  0 }},
 182         {{ -1,  0,  0 }, {  0,  0, -1 }, {  0, -1,  0 }},
 183         {{  0,  1,  0 }, {  1,  0,  0 }, {  0,  0,  1 }},
 184         {{  0, -1,  0 }, {  1,  0,  0 }, {  0,  0,  1 }},
 185     };
 186
 187     double R[16];
 188     double p0[3], p1[3], p2[3];
 189     double  u[3],  v[3],  p[3];
 190     double k, d = 0.0;
 191     int i, w, h, n = 0;
 192     char filename[MAXSTR];
 193
 194     strcpy(filename, s);
 195     strcat(filename, ".jpg");
 196
 197     size_image(filename, &w, &h);
 198
 199     plane_f[pi] = fl;
 200
 201     p0[0] = +(double) x0 / SCALE;
 202     p0[1] = +(double) z0 / SCALE;
 203     p0[2] = -(double) y0 / SCALE;
 204
 205     p1[0]  = +(double) x1 / SCALE;
 206     p1[1]  = +(double) z1 / SCALE;
 207     p1[2]  = -(double) y1 / SCALE;
 208
 209     p2[0] = +(double) x2 / SCALE;
 210     p2[1] = +(double) z2 / SCALE;
 211     p2[2] = -(double) y2 / SCALE;
 212
 213     v_sub(u, p0, p1);
 214     v_sub(v, p2, p1);
 215
 216     v_crs(plane_n[pi], u, v);
 217     v_nrm(plane_n[pi], plane_n[pi]);
 218
 219     plane_d[pi] = v_dot(plane_n[pi], p1);
 220
 221     for (i = 0; i < 6; i++)
 222         if ((k = v_dot(plane_n[pi], base[i][0])) > d)
 223         {
 224             d = k;
 225             n = i;
 226         }
 227
 228     p[0] = 0.0;
 229     p[1] = 0.0;
 230     p[2] = 0.0;
 231
 232     m_rot(R, base[n][0], V_RAD(r));
 233
 234     v_mad(p, p, base[n][1], su * tu / SCALE);
 235     v_mad(p, p, base[n][2], sv * tv / SCALE);
 236
 237     m_vxfm(plane_u[pi], R, base[n][1]);
 238     m_vxfm(plane_v[pi], R, base[n][2]);
 239     m_vxfm(plane_p[pi], R, p);
 240
 241     v_scl(plane_u[pi], plane_u[pi], SCALE / w);
 242     v_scl(plane_v[pi], plane_v[pi], SCALE / h);
 243
 244     v_scl(plane_u[pi], plane_u[pi], 1.0 / su);
 245     v_scl(plane_v[pi], plane_v[pi], 1.0 / sv);
 246 }
 247
 248 /*---------------------------------------------------------------------------*/
 249
 250 #define T_EOF 0
 251 #define T_BEG 1
 252 #define T_CLP 2
 253 #define T_KEY 3
 254 #define T_END 4
 255 #define T_NOP 5
 256
 257 static int map_token(FILE *fin, int pi, char key[MAXSTR],
 258                      char val[MAXSTR])
 259 {
 260     char buf[MAXSTR];
 261
 262     if (fgets(buf, MAXSTR, fin))
 263     {
 264         char c;
 265         int x0, y0, z0;
 266         int x1, y1, z1;
 267         int x2, y2, z2;
 268         int tu, tv, r, fl;
 269         float su, sv;
 270
 271         /* Scan the beginning or end of a block. */
 272
 273         if (buf[0] == '{') return T_BEG;
 274         if (buf[0] == '}') return T_END;
 275
 276         /* Scan a key-value pair. */
 277
 278         if (buf[0] == '"')
 279         {
 280             strcpy(key, strtok(buf,  "\""));
 281             (void)      strtok(NULL, "\"");
 282             strcpy(val, strtok(NULL, "\""));
 283
 284             return T_KEY;
 285         }
 286
 287         /* Scan a plane. */
 288
 289         if (sscanf(buf, "%c %d %d %d %c "
 290                    "%c %d %d %d %c "
 291                    "%c %d %d %d %c "
 292                    "%s %d %d %d %f %f %d",
 293                    &c, &x0, &y0, &z0, &c,
 294                    &c, &x1, &y1, &z1, &c,
 295                    &c, &x2, &y2, &z2, &c,
 296                    key, &tu, &tv, &r, &su, &sv, &fl) == 22)
 297         {
 298             make_plane(pi, x0, y0, z0,
 299                        x1, y1, z1,
 300                        x2, y2, z2,
 301                        tu, tv, r, su, sv, fl, key);
 302             return T_CLP;
 303         }
 304
 305         /* If it's not recognized, it must be uninteresting. */
 306
 307         return T_NOP;
 308     }
 309     return T_EOF;
 310 }
 311
 312 /*---------------------------------------------------------------------------*/
 313
 314 /* Read the given material file, adding a new material to the solid.  */
 315
 316 static void read_mtrl(struct s_file *fp, const char *s)
 317 {
 318     struct s_mtrl *mp = fp->mv + fp->mc++;
 319     FILE *fin;
 320
 321     if ((fin = fopen(s, "r")))
 322     {
 323         fscanf(fin, "%f %f %f %f "
 324                "%f %f %f %f "
 325                "%f %f %f %f "
 326                "%f %f %f %f "
 327                "%f ",
 328                mp->d, mp->d + 1, mp->d + 2, mp->d + 3,
 329                mp->a, mp->a + 1, mp->a + 2, mp->a + 3,
 330                mp->s, mp->s + 1, mp->s + 2, mp->s + 3,
 331                mp->e, mp->e + 1, mp->e + 2, mp->e + 3,
 332                mp->h);
 333         fclose(fin);
 334
 335         strcpy(mp->f, "data/");
 336         strcat(mp->f, s);
 337         strcat(mp->f, ".jpg");
 338     }
 339 }
 340
 341 /*
 342  * Parse a lump  from the given file and  add it to the solid.   Note a small
 343  * hack here  in mapping  materials onto sides.   Material indices  cannot be
 344  * assigned until faces  are computed, so for now there is  assumed to be one
 345  * material  per side,  and that  a side  index equals  that  side's material
 346  * index.  See clip_lump and clip_geom.
 347  */
 348 static void read_lump(struct s_file *fp, FILE *fin)
 349 {
 350     char k[MAXSTR];
 351     char v[MAXSTR];
 352     int t;
 353
 354     struct s_lump *lp = fp->lv + fp->lc++;
 355
 356     lp->s0 = fp->ic;
 357
 358     while ((t = map_token(fin, fp->sc, k, v)))
 359     {
 360         if (t == T_CLP)
 361         {
 362             fp->sv[fp->sc].n[0] = plane_n[fp->sc][0];
 363             fp->sv[fp->sc].n[1] = plane_n[fp->sc][1];
 364             fp->sv[fp->sc].n[2] = plane_n[fp->sc][2];
 365             fp->sv[fp->sc].d    = plane_d[fp->sc];
 366
 367             read_mtrl(fp, k);
 368
 369             fp->iv[fp->ic] = fp->sc;
 370             fp->ic++;
 371             fp->sc++;
 372             lp->sc++;
 373         }
 374         if (t == T_END)
 375             break;
 376     }
 377 }
 378
 379 /*---------------------------------------------------------------------------*/
 380
 381 static void make_path(struct s_file *fp,
 382                       char k[][MAXSTR],
 383                       char v[][MAXSTR], int c)
 384 {
 385     int i, pi = fp->pc++;
 386
 387     struct s_path *pp = fp->pv + pi;
 388
 389     pp->p[0] = 0.0;
 390     pp->p[1] = 0.0;
 391     pp->p[2] = 0.0;
 392     pp->t    = 1.0;
 393     pp->pi   = pi;
 394
 395     for (i = 0; i < c; i++)
 396     {
 397         if (!strcmp(k[i], "targetname"))
 398             make_sym(v[i], pi);
 399
 400         if (!strcmp(k[i], "target"))
 401             make_ref(v[i], &pp->pi);
 402
 403         if (!strcmp(k[i], "speed"))
 404             sscanf(v[i], "%lf", &pp->t);
 405
 406         if (!strcmp(k[i], "origin"))
 407         {
 408             int x = 0, y = 0, z = 0;
 409
 410             sscanf(v[i], "%d %d %d", &x, &y, &z);
 411
 412             pp->p[0] = +(double) x / SCALE;
 413             pp->p[1] = +(double) z / SCALE;
 414             pp->p[2] = -(double) y / SCALE;
 415         }
 416     }
 417 }
 418
 419 static void make_body(struct s_file *fp,
 420                       char k[][MAXSTR],
 421                       char v[][MAXSTR], int c, int l0)
 422 {
 423     int i, bi = fp->bc++;
 424
 425     struct s_body *bp = fp->bv + bi;
 426
 427     bp->t  = 0.0;
 428     bp->pi = -1;
 429     bp->ni = -1;
 430     bp->l0 = l0;
 431     bp->lc = fp->lc - l0;
 432
 433     for (i = 0; i < c; i++)
 434         if (strcmp(k[i], "target") == 0)
 435             make_ref(v[i], &bp->pi);
 436 }
 437
 438 static void make_coin(struct s_file *fp,
 439                       char k[][MAXSTR],
 440                       char v[][MAXSTR], int c)
 441 {
 442     int i, ci = fp->cc++;
 443
 444     struct s_coin *cp = fp->cv + ci;
 445
 446     cp->p[0] = 0.0;
 447     cp->p[1] = 0.0;
 448     cp->p[2] = 0.0;
 449     cp->n    = 1;
 450
 451     for (i = 0; i < c; i++)
 452     {
 453         if (strcmp(k[i], "light") == 0)
 454             sscanf(v[i], "%d", &cp->n);
 455
 456         if (strcmp(k[i], "origin") == 0)
 457         {
 458             int x = 0, y = 0, z = 0;
 459
 460             sscanf(v[i], "%d %d %d", &x, &y, &z);
 461
 462             cp->p[0] = +(double) x / SCALE;
 463             cp->p[1] = +(double) z / SCALE;
 464             cp->p[2] = -(double) y / SCALE;
 465         }
 466     }
 467 }
 468
 469 static void make_ball(struct s_file *fp,
 470                       char k[][MAXSTR],
 471                       char v[][MAXSTR], int c)
 472 {
 473     int i, ui = fp->uc++;
 474
 475     struct s_ball *up = fp->uv + ui;
 476
 477     up->p[0] = 0.0;
 478     up->p[1] = 0.0;
 479     up->p[2] = 0.0;
 480     up->r    = 0.25;
 481
 482     up->e[0][0] = 1.0;
 483     up->e[0][1] = 0.0;
 484     up->e[0][2] = 0.0;
 485     up->e[1][0] = 0.0;
 486     up->e[1][1] = 1.0;
 487     up->e[1][2] = 0.0;
 488     up->e[2][0] = 0.0;
 489     up->e[2][1] = 0.0;
 490     up->e[2][2] = 1.0;
 491
 492     up->v[0] = 0.0;
 493     up->v[1] = 0.0;
 494     up->v[2] = 0.0;
 495     up->w[0] = 0.0;
 496     up->w[1] = 0.0;
 497     up->w[2] = 0.0;
 498
 499     for (i = 0; i < c; i++)
 500     {
 501         if (strcmp(k[i], "radius") == 0)
 502             sscanf(v[i], "%lf", &up->r);
 503
 504         if (!strcmp(k[i], "target"))
 505             make_ref(v[i], &path_0);
 506
 507         if (strcmp(k[i], "origin") == 0)
 508         {
 509             int x = 0, y = 0, z = 0;
 510
 511             sscanf(v[i], "%d %d %d", &x, &y, &z);
 512
 513             up->p[0] = +(double) (x)      / SCALE;
 514             up->p[1] = +(double) (z - 24) / SCALE;
 515             up->p[2] = -(double) (y)      / SCALE;
 516         }
 517     }
 518
 519     up->p[1] += up->r + SMALL;
 520 }
 521
 522 /*---------------------------------------------------------------------------*/
 523
 524 static void read_ent(struct s_file *fp, FILE *fin)
 525 {
 526     char k[MAXKEY][MAXSTR];
 527     char v[MAXKEY][MAXSTR];
 528     int t, i = 0, c = 0;
 529
 530     int l0 = fp->lc;
 531
 532     while ((t = map_token(fin, -1, k[c], v[c])))
 533     {
 534         if (t == T_KEY)
 535         {
 536             if (strcmp(k[c], "classname") == 0)
 537                 i = c;
 538             c++;
 539         }
 540         if (t == T_BEG)
 541             read_lump(fp, fin);
 542         if (t == T_END)
 543             break;
 544     }
 545
 546     if (!strcmp(v[i], "light"))             make_coin(fp, k, v, c);
 547     if (!strcmp(v[i], "path_corner"))       make_path(fp, k, v, c);
 548     if (!strcmp(v[i], "info_player_start")) make_ball(fp, k, v, c);
 549
 550     if (!strcmp(v[i], "worldspawn"))  make_body(fp, k, v, c, l0);
 551     if (!strcmp(v[i], "func_train"))  make_body(fp, k, v, c, l0);
 552 }
 553
 554 static void read_map(struct s_file *fp, FILE *fin)
 555 {
 556     char k[MAXSTR];
 557     char v[MAXSTR];
 558     int t;
 559
 560     while ((t = map_token(fin, -1, k, v)))
 561         if (t == T_BEG)
 562             read_ent(fp, fin);
 563 }
 564
 565 /*---------------------------------------------------------------------------*/
 566
 567 /*
 568  * All bodies  with an associated  path are assumed  to be positioned  at the
 569  * beginning of that path.  These bodies must be moved to the origin in order
 570  * for their  path transforms to behave  correctly.  This is how  we get away
 571  * with defining func_trains with no origin specification.
 572  */
 573
 574 static void move_side(struct s_side *sp, const double p[3])
 575 {
 576     sp->d -= v_dot(sp->n, p);
 577 }
 578
 579 static void move_lump(struct s_file *fp,
 580                       struct s_lump *lp, const double p[3])
 581 {
 582     int i;
 583
 584     for (i = 0; i < lp->sc; i++)
 585         move_side(fp->sv + fp->iv[lp->s0 + i], p);
 586 }
 587
 588 static void move_body(struct s_file *fp,
 589                       struct s_body *bp)
 590 {
 591     int i;
 592
 593     for (i = 0; i < bp->lc; i++)
 594         move_lump(fp, fp->lv + bp->l0 + i, fp->pv[bp->pi].p);
 595 }
 596
 597 static void move_file(struct s_file *fp)
 598 {
 599     int i;
 600
 601     for (i = 0; i < fp->bc; i++)
 602         if (fp->bv[i].pi >= 0)
 603             move_body(fp, fp->bv + i);
 604 }
 605
 606 /*---------------------------------------------------------------------------*/
 607
 608 /* Test the location of a point with respect to a side plane. */
 609
 610 static int fore_side(const double p[3], const struct s_side *sp)
 611 {
 612     return (v_dot(p, sp->n) - sp->d > +SMALL) ? 1 : 0;
 613 }
 614
 615 static int on_side(const double p[3], const struct s_side *sp)
 616 {
 617     double d = v_dot(p, sp->n) - sp->d;
 618
 619     return (-SMALL < d && d < +SMALL) ? 1 : 0;
 620 }
 621
 622 /*---------------------------------------------------------------------------*/
 623 /*
 624  * Confirm  that  the addition  of  a vert  would  not  result in  degenerate
 625  * geometry.
 626  */
 627
 628 static int ok_vert(const struct s_file *fp,
 629                    const struct s_lump *lp, const double p[3])
 630 {
 631     double r[3];
 632     int i;
 633
 634     for (i = 0; i < lp->vc; i++)
 635     {
 636         double *q = fp->vv[fp->iv[lp->v0 + i]].p;
 637
 638         v_sub(r, p, q);
 639
 640         if (v_len(r) < SMALL)
 641             return 0;
 642     }
 643     return 1;
 644 }
 645
 646 /*---------------------------------------------------------------------------*/
 647
 648 /*
 649  * The following  functions take the set  of planes defining a  lump and find
 650  * the verts,  edges, and  geoms that describe  its boundaries.  To  do this,
 651  * they first find the verts, and then search these verts for valid edges and
 652  * geoms.  It  may be more efficient  to compute edges and  geoms directly by
 653  * clipping down  infinite line segments and  planes, but this  would be more
 654  * complex and prone to numerical error.
 655  */
 656
 657 /*
 658  * Given 3 side  planes, compute the point of  intersection, if any.  Confirm
 659  * that this point falls within the current lump, and that it is unique.  Add
 660  * it as a vert of the solid.
 661  */
 662 static void clip_vert(struct s_file *fp,
 663                       struct s_lump *lp, int si, int sj, int sk)
 664 {
 665     double M[16], X[16], I[16];
 666     double d[3],  p[3];
 667     int i;
 668
 669     d[0] = fp->sv[si].d;
 670     d[1] = fp->sv[sj].d;
 671     d[2] = fp->sv[sk].d;
 672
 673     m_basis(M, fp->sv[si].n, fp->sv[sj].n, fp->sv[sk].n);
 674     m_xps(X, M);
 675
 676     if (m_inv(I, X))
 677     {
 678         m_vxfm(p, I, d);
 679
 680         for (i = 0; i < lp->sc; i++)
 681         {
 682             int si = fp->iv[lp->s0 + i];
 683
 684             if (fore_side(p, fp->sv + si))
 685                 return;
 686         }
 687
 688         if (ok_vert(fp, lp, p))
 689         {
 690             v_cpy(fp->vv[fp->vc].p, p);
 691
 692             fp->iv[fp->ic] = fp->vc;
 693             fp->ic++;
 694             fp->vc++;
 695             lp->vc++;
 696         }
 697     }
 698 }
 699
 700 /*
 701  * Given two side planes, find an  edge along their intersection by finding a
 702  * pair of vertices that fall on both planes.  Add it to the solid.
 703  */
 704 static void clip_edge(struct s_file *fp,
 705                       struct s_lump *lp, int si, int sj)
 706 {
 707     int i, j;
 708
 709     for (i = 1; i < lp->vc; i++)
 710         for (j = 0; j < i; j++)
 711         {
 712             int vi = fp->iv[lp->v0 + i];
 713             int vj = fp->iv[lp->v0 + j];
 714
 715             if (on_side(fp->vv[vi].p, fp->sv + si) &&
 716                 on_side(fp->vv[vj].p, fp->sv + si) &&
 717                 on_side(fp->vv[vi].p, fp->sv + sj) &&
 718                 on_side(fp->vv[vj].p, fp->sv + sj))
 719             {
 720                 fp->ev[fp->ec].vi = vi;
 721                 fp->ev[fp->ec].vj = vj;
 722
 723                 fp->iv[fp->ic] = fp->ec;
 724
 725                 fp->ic++;
 726                 fp->ec++;
 727                 lp->ec++;
 728             }
 729         }
 730 }
 731
 732 /*
 733  * Find all verts that  lie on the given side of the  lump.  Sort these verts
 734  * to have a counter-clockwise winding  about the plane normal.  Create geoms
 735  * to tessalate the resulting convex polygon.
 736  */
 737 static void clip_geom(struct s_file *fp,
 738                       struct s_lump *lp, int si)
 739 {
 740     int    m[16], t[16], d, i, j, n = 0;
 741     double u[3];
 742     double v[3];
 743     double w[3];
 744
 745     struct s_side *sp = fp->sv + si;
 746
 747     /* Find em. */
 748
 749     for (i = 0; i < lp->vc; i++)
 750     {
 751         int vi = fp->iv[lp->v0 + i];
 752
 753         if (on_side(fp->vv[vi].p, sp))
 754         {
 755             m[n] = vi;
 756             t[n] = fp->tc++;
 757
 758             v_add(v, fp->vv[vi].p, plane_p[si]);
 759
 760             fp->tv[t[n]].u[0] = v_dot(v, plane_u[si]);
 761             fp->tv[t[n]].u[1] = v_dot(v, plane_v[si]);
 762
 763             n++;
 764         }
 765     }
 766
 767     /* Sort em. */
 768
 769     for (i = 1; i < n; i++)
 770         for (j = i + 1; j < n; j++)
 771         {
 772             v_sub(u, fp->vv[m[i]].p, fp->vv[m[0]].p);
 773             v_sub(v, fp->vv[m[j]].p, fp->vv[m[0]].p);
 774             v_crs(w, u, v);
 775
 776             if (v_dot(w, sp->n) < 0.0)
 777             {
 778                 d     = m[i];
 779                 m[i]  = m[j];
 780                 m[j]  =    d;
 781
 782                 d     = t[i];
 783                 t[i]  = t[j];
 784                 t[j]  =    d;
 785             }
 786         }
 787
 788     /* Index em. */
 789
 790     for (i = 0; i < n - 2; i++)
 791     {
 792         fp->gv[fp->gc].si = si;
 793         fp->gv[fp->gc].mi = si;
 794
 795         fp->gv[fp->gc].ti = t[0];
 796         fp->gv[fp->gc].tj = t[i + 1];
 797         fp->gv[fp->gc].tk = t[i + 2];
 798
 799         fp->gv[fp->gc].vi = m[0];
 800         fp->gv[fp->gc].vj = m[i + 1];
 801         fp->gv[fp->gc].vk = m[i + 2];
 802
 803         fp->iv[fp->ic] = fp->gc;
 804         fp->ic++;
 805         fp->gc++;
 806         lp->gc++;
 807     }
 808 }
 809
 810 /*
 811  * Iterate the sides  of the lump, attemping to generate a  new vert for each
 812  * trio of planes, a new edge for each  pair of planes, and a new set of geom
 813  * for each visible plane.
 814  */
 815 static void clip_lump(struct s_file *fp, struct s_lump *lp)
 816 {
 817     int i, j, k;
 818
 819     lp->v0 = fp->ic;
 820     lp->vc = 0;
 821
 822     for (i = 2; i < lp->sc; i++)
 823         for (j = 1; j < i; j++)
 824             for (k = 0; k < j; k++)
 825                 clip_vert(fp, lp,
 826                           fp->iv[lp->s0 + i],
 827                           fp->iv[lp->s0 + j],
 828                           fp->iv[lp->s0 + k]);
 829
 830     lp->e0 = fp->ic;
 831     lp->ec = 0;
 832
 833     for (i = 1; i < lp->sc; i++)
 834         for (j = 0; j < i; j++)
 835             clip_edge(fp, lp,
 836                       fp->iv[lp->s0 + i],
 837                       fp->iv[lp->s0 + j]);
 838
 839     lp->g0 = fp->ic;
 840     lp->gc = 0;
 841
 842     for (i = 0; i < lp->sc; i++)
 843         if (fp->mv[fp->iv[lp->s0 + i]].d[3] > 0)
 844             clip_geom(fp, lp,
 845                       fp->iv[lp->s0 + i]);
 846
 847     for (i = 0; i < lp->sc; i++)
 848         lp->fl |= (plane_f[fp->iv[lp->s0 + i]] ? 1 : 0);
 849 }
 850
 851 static void clip_file(struct s_file *fp)
 852 {
 853     int i;
 854
 855     for (i = 0; i < fp->lc; i++)
 856         clip_lump(fp, fp->lv + i);
 857 }
 858
 859 /*---------------------------------------------------------------------------*/
 860
 861 /*
 862  * For  each body element  type, determine  if element  'p' is  equivalent to
 863  * element 'q'.  This  is more than a simple  memory compare.  It effectively
 864  * snaps mtrls and verts togather, and  may reverse the winding of an edge or
 865  * a geom.  This is done in order to maximize the number of elements that can
 866  * be eliminated.
 867  */
 868
 869 static int comp_mtrl(const struct s_mtrl *mp, const struct s_mtrl *mq)
 870 {
 871     if (fabs(mp->d[0] - mq->d[0]) > SMALL) return 0;
 872     if (fabs(mp->d[1] - mq->d[1]) > SMALL) return 0;
 873     if (fabs(mp->d[2] - mq->d[2]) > SMALL) return 0;
 874     if (fabs(mp->d[3] - mq->d[3]) > SMALL) return 0;
 875
 876     if (fabs(mp->a[0] - mq->a[0]) > SMALL) return 0;
 877     if (fabs(mp->a[1] - mq->a[1]) > SMALL) return 0;
 878     if (fabs(mp->a[2] - mq->a[2]) > SMALL) return 0;
 879     if (fabs(mp->a[3] - mq->a[3]) > SMALL) return 0;
 880
 881     if (fabs(mp->s[0] - mq->s[0]) > SMALL) return 0;
 882     if (fabs(mp->s[1] - mq->s[1]) > SMALL) return 0;
 883     if (fabs(mp->s[2] - mq->s[2]) > SMALL) return 0;
 884     if (fabs(mp->s[3] - mq->s[3]) > SMALL) return 0;
 885
 886     if (fabs(mp->e[0] - mq->e[0]) > SMALL) return 0;
 887     if (fabs(mp->e[1] - mq->e[1]) > SMALL) return 0;
 888     if (fabs(mp->e[2] - mq->e[2]) > SMALL) return 0;
 889     if (fabs(mp->e[3] - mq->e[3]) > SMALL) return 0;
 890
 891     if (fabs(mp->h[0] - mq->h[0]) > SMALL) return 0;
 892
 893     if (strcmp(mp->f, mq->f)) return 0;
 894
 895     return 1;
 896 }
 897
 898 static int comp_vert(const struct s_vert *vp, const struct s_vert *vq)
 899 {
 900     if (fabs(vp->p[0] - vq->p[0]) > SMALL) return 0;
 901     if (fabs(vp->p[1] - vq->p[1]) > SMALL) return 0;
 902     if (fabs(vp->p[2] - vq->p[2]) > SMALL) return 0;
 903
 904     return 1;
 905 }
 906
 907 static int comp_edge(const struct s_edge *ep, const struct s_edge *eq)
 908 {
 909     if (ep->vi != eq->vi && ep->vi != eq->vj) return 0;
 910     if (ep->vj != eq->vi && ep->vj != eq->vj) return 0;
 911
 912     return 1;
 913 }
 914
 915 static int comp_side(const struct s_side *sp, const struct s_side *sq)
 916 {
 917     if  (fabs(sp->d - sq->d) >       SMALL) return 0;
 918     if (v_dot(sp->n,  sq->n) < 1.0 - SMALL) return 0;
 919
 920     return 1;
 921 }
 922
 923 static int comp_texc(const struct s_texc *tp, const struct s_texc *tq)
 924 {
 925     if (fabs(tp->u[0] - tq->u[0]) > SMALL) return 0;
 926     if (fabs(tp->u[1] - tq->u[1]) > SMALL) return 0;
 927
 928     return 1;
 929 }
 930
 931 static int comp_geom(const struct s_geom *gp, const struct s_geom *gq)
 932 {
 933     if (gp->si != gq->si) return 0;
 934     if (gp->mi != gq->mi) return 0;
 935
 936     /* FIXME: buh. */
 937
 938     return 0;
 939 }
 940
 941 /*---------------------------------------------------------------------------*/
 942
 943 /*
 944  * For each file  element type, replace all references to  element 'i' with a
 945  * reference to element 'j'.  These  are used when optimizing and sorting the
 946  * file.
 947  */
 948
 949 static void swap_mtrl(struct s_file *fp, int mi, int mj)
 950 {
 951     int i;
 952
 953     for (i = 0; i < fp->gc; i++)
 954         if (fp->gv[i].mi == mi) fp->gv[i].mi = mj;
 955 }
 956
 957 static void swap_vert(struct s_file *fp, int vi, int vj)
 958 {
 959     int i, j;
 960
 961     for (i = 0; i < fp->ec; i++)
 962     {
 963         if (fp->ev[i].vi == vi) fp->ev[i].vi = vj;
 964         if (fp->ev[i].vj == vi) fp->ev[i].vj = vj;
 965     }
 966
 967     for (i = 0; i < fp->gc; i++)
 968     {
 969         if (fp->gv[i].vi == vi) fp->gv[i].vi = vj;
 970         if (fp->gv[i].vj == vi) fp->gv[i].vj = vj;
 971         if (fp->gv[i].vk == vi) fp->gv[i].vk = vj;
 972     }
 973
 974     for (i = 0; i < fp->lc; i++)
 975         for (j = 0; j < fp->lv[i].vc; j++)
 976             if (fp->iv[fp->lv[i].v0 + j] == vi)
 977                 fp->iv[fp->lv[i].v0 + j]  = vj;
 978 }
 979
 980 static void swap_edge(struct s_file *fp, int ei, int ej)
 981 {
 982     int i, j;
 983
 984     for (i = 0; i < fp->lc; i++)
 985         for (j = 0; j < fp->lv[i].ec; j++)
 986             if (fp->iv[fp->lv[i].e0 + j] == ei)
 987                 fp->iv[fp->lv[i].e0 + j]  = ej;
 988 }
 989
 990 static void swap_side(struct s_file *fp, int si, int sj)
 991 {
 992     int i, j;
 993
 994     for (i = 0; i < fp->gc; i++)
 995         if (fp->gv[i].si == si) fp->gv[i].si = sj;
 996     for (i = 0; i < fp->nc; i++)
 997         if (fp->nv[i].si == si) fp->nv[i].si = sj;
 998
 999     for (i = 0; i < fp->lc; i++)
1000         for (j = 0; j < fp->lv[i].sc; j++)
1001             if (fp->iv[fp->lv[i].s0 + j] == si)
1002                 fp->iv[fp->lv[i].s0 + j]  = sj;
1003 }
1004
1005 static void swap_texc(struct s_file *fp, int ti, int tj)
1006 {
1007     int i;
1008
1009     for (i = 0; i < fp->gc; i++)
1010     {
1011         if (fp->gv[i].ti == ti) fp->gv[i].ti = tj;
1012         if (fp->gv[i].tj == ti) fp->gv[i].tj = tj;
1013         if (fp->gv[i].tk == ti) fp->gv[i].tk = tj;
1014     }
1015 }
1016
1017 static void swap_geom(struct s_file *fp, int gi, int gj)
1018 {
1019     int i, j;
1020
1021     for (i = 0; i < fp->lc; i++)
1022         for (j = 0; j < fp->lv[i].gc; j++)
1023             if (fp->iv[fp->lv[i].g0 + j] == gi)
1024                 fp->iv[fp->lv[i].g0 + j]  = gj;
1025 }
1026
1027 static void swap_path(struct s_file *fp, int pi, int pj)
1028 {
1029     int i;
1030
1031     for (i = 0; i < fp->pc; i++)
1032         if (fp->pv[i].pi == pi) fp->pv[i].pi = pj;
1033
1034     for (i = 0; i < fp->bc; i++)
1035         if (fp->bv[i].pi == pi) fp->bv[i].pi = pj;
1036 }
1037
1038 /*---------------------------------------------------------------------------*/
1039
1040 static void uniq_mtrl(struct s_file *fp)
1041 {
1042     int i, j, k = 0;
1043
1044     for (i = 0; i < fp->mc; i++)
1045     {
1046         for (j = 0; j < i; j++)
1047             if (comp_mtrl(fp->mv + i, fp->mv + j))
1048             {
1049                 swap_mtrl(fp, i, j);
1050                 break;
1051             }
1052
1053         if (i == j)
1054         {
1055             fp->mv[k] = fp->mv[i];
1056             swap_mtrl(fp, i, k);
1057             k++;
1058         }
1059     }
1060
1061     fp->mc = k;
1062 }
1063
1064 static void uniq_vert(struct s_file *fp)
1065 {
1066     int i, j, k = 0;
1067
1068     for (i = 0; i < fp->vc; i++)
1069     {
1070         for (j = 0; j < i; j++)
1071             if (comp_vert(fp->vv + i, fp->vv + j))
1072             {
1073                 swap_vert(fp, i, j);
1074                 break;
1075             }
1076
1077         if (i == j)
1078         {
1079             fp->vv[k] = fp->vv[i];
1080             swap_vert(fp, i, k);
1081             k++;
1082         }
1083     }
1084
1085     fp->vc = k;
1086 }
1087
1088 static void uniq_edge(struct s_file *fp)
1089 {
1090     int i, j, k = 0;
1091
1092     for (i = 0; i < fp->ec; i++)
1093     {
1094         for (j = 0; j < i; j++)
1095             if (comp_edge(fp->ev + i, fp->ev + j))
1096             {
1097                 swap_edge(fp, i, j);
1098                 break;
1099             }
1100
1101         if (i == j)
1102         {
1103             fp->ev[k] = fp->ev[i];
1104             swap_edge(fp, i, k);
1105             k++;
1106         }
1107     }
1108
1109     fp->ec = k;
1110 }
1111
1112 static void uniq_geom(struct s_file *fp)
1113 {
1114     int i, j, k = 0;
1115
1116     for (i = 0; i < fp->gc; i++)
1117     {
1118         for (j = 0; j < i; j++)
1119             if (comp_geom(fp->gv + i, fp->gv + j))
1120             {
1121                 swap_geom(fp, i, j);
1122                 break;
1123             }
1124
1125         if (i == j)
1126         {
1127             fp->gv[k] = fp->gv[i];
1128             swap_geom(fp, i, k);
1129             k++;
1130         }
1131     }
1132
1133     fp->gc = k;
1134 }
1135
1136 static void uniq_texc(struct s_file *fp)
1137 {
1138     int i, j, k = 0;
1139
1140     for (i = 0; i < fp->tc; i++)
1141     {
1142         for (j = 0; j < i; j++)
1143             if (comp_texc(fp->tv + i, fp->tv + j))
1144             {
1145                 swap_texc(fp, i, j);
1146                 break;
1147             }
1148         if (i == j)
1149         {
1150             fp->tv[k] = fp->tv[i];
1151             swap_texc(fp, i, k);
1152             k++;
1153         }
1154     }
1155
1156     fp->tc = k;
1157 }
1158
1159 static void uniq_side(struct s_file *fp)
1160 {
1161     int i, j, k = 0;
1162
1163     for (i = 0; i < fp->sc; i++)
1164     {
1165         for (j = 0; j < i; j++)
1166             if (comp_side(fp->sv + i, fp->sv + j))
1167             {
1168                 swap_side(fp, i, j);
1169                 break;
1170             }
1171         if (i == j)
1172         {
1173             fp->sv[k] = fp->sv[i];
1174             swap_side(fp, i, k);
1175             k++;
1176         }
1177     }
1178
1179     fp->sc = k;
1180 }
1181
1182 static void uniq_file(struct s_file *fp)
1183 {
1184     uniq_mtrl(fp);
1185     uniq_vert(fp);
1186     uniq_edge(fp);
1187     uniq_side(fp);
1188     uniq_texc(fp);
1189     uniq_geom(fp);
1190 }
1191
1192 /*---------------------------------------------------------------------------*/
1193
1194 static void sort_file(struct s_file *fp)
1195 {
1196     int i, j;
1197
1198     struct s_geom g;
1199     struct s_side s;
1200     struct s_path p;
1201
1202     /*
1203      * Sort the  geoms in  order of material  index.  This was  originally an
1204      * important state transition reduction hack, but is now merely cute.
1205      */
1206     for (i = 1; i < fp->gc; i++)
1207         for (j = 0; j < i; j++)
1208             if (fp->gv[i].mi > fp->gv[j].mi)
1209             {
1210                 g         = fp->gv[i];
1211                 fp->gv[i] = fp->gv[j];
1212                 fp->gv[j] =         g;
1213
1214                 swap_geom(fp,  i, -1);
1215                 swap_geom(fp,  j,  i);
1216                 swap_geom(fp, -1,  j);
1217             }
1218
1219     /*
1220      * Sort the sides so that the  most "floorish" side is 0.  Then any geoms
1221      * referring to side 0 may be given special treatment as "floor" geoms.
1222      */
1223     for (j = 1; j < fp->sc; j++)
1224         if (fp->sv[j].n[1]    >= fp->sv[0].n[1] &&
1225             fabs(fp->sv[j].d) <= fabs(fp->sv[0].d))
1226         {
1227             s         = fp->sv[0];
1228             fp->sv[0] = fp->sv[j];
1229             fp->sv[j] =         s;
1230
1231             swap_side(fp,  0, -1);
1232             swap_side(fp,  j,  0);
1233             swap_side(fp, -1,  j);
1234         }
1235
1236     /*
1237      * If path_0 is not -1, ensure that the path it refers to is 0.
1238      */
1239     if (path_0 > 0 && fp->pc > 0)
1240     {
1241         j = path_0;
1242
1243         p         = fp->pv[0];
1244         fp->pv[0] = fp->pv[j];
1245         fp->pv[j] =         p;
1246
1247         swap_path(fp,  0, -2);
1248         swap_path(fp,  j,  0);
1249         swap_path(fp, -2,  j);
1250     }
1251 }
1252
1253 /*---------------------------------------------------------------------------*/
1254
1255 static void dump_head(void)
1256 {
1257     printf("  mtrl  vert  edge  side  texc  geom  lump"
1258            "  node  path  body  coin  ball  indx\n");
1259 }
1260
1261 static void dump_file(struct s_file *fp)
1262 {
1263     printf("%6d%6d%6d%6d%6d%6d%6d%6d%6d%6d%6d%6d%6d\n",
1264            fp->mc, fp->vc, fp->ec, fp->sc, fp->tc, fp->gc, fp->lc,
1265            fp->nc, fp->pc, fp->bc, fp->cc, fp->uc, fp->ic);
1266 }
1267
1268 int main(int argc, char *argv[])
1269 {
1270     struct s_file f;
1271     FILE *fin;
1272
1273     if (argc > 2)
1274     {
1275         if ((fin = fopen(argv[1], "r")))
1276         {
1277             init_file(&f);
1278             read_map(&f, fin);
1279
1280             resolve();
1281
1282             dump_head();
1283             move_file(&f);
1284             clip_file(&f);
1285             dump_file(&f);
1286             uniq_file(&f);
1287             sort_file(&f);
1288             dump_file(&f);
1289
1290             sol_stor(&f, argv[2]);
1291
1292             fclose(fin);
1293         }
1294     }
1295     return 0;
1296 }
1297