vcs.maemo.org Git - neverball/blob - share/mapc.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 /*---------------------------------------------------------------------------*/
  16
  17 #include <stdio.h>
  18 #include <stdlib.h>
  19 #include <string.h>
  20 #include <math.h>
  21
  22 #include "vec3.h"
  23 #include "solid.h"
  24 #include "base_image.h"
  25 #include "base_config.h"
  26 #include "fs.h"
  27 #include "common.h"
  28
  29 #define MAXSTR 256
  30 #define MAXKEY 16
  31 #define SCALE  64.f
  32 #define SMALL  0.0005f
  33
  34 /*
  35  * The overall design  of this map converter is  very stupid, but very
  36  * simple. It  begins by assuming  that every mtrl, vert,  edge, side,
  37  * and texc  in the map is  unique.  It then makes  an optimizing pass
  38  * that discards redundant information.  The result is optimal, though
  39  * the process is terribly inefficient.
  40  */
  41
  42 /*---------------------------------------------------------------------------*/
  43
  44 static const char *input_file;
  45 static int         debug_output = 0;
  46
  47 /*---------------------------------------------------------------------------*/
  48
  49 /* Ohhhh... arbitrary! */
  50
  51 #define MAXM    1024
  52 #define MAXV    65536
  53 #define MAXE    65536
  54 #define MAXS    65536
  55 #define MAXT    131072
  56 #define MAXG    65536
  57 #define MAXL    4096
  58 #define MAXN    2048
  59 #define MAXP    2048
  60 #define MAXB    1024
  61 #define MAXH    2048
  62 #define MAXZ    1024
  63 #define MAXJ    1024
  64 #define MAXX    1024
  65 #define MAXR    2048
  66 #define MAXU    1024
  67 #define MAXW    1024
  68 #define MAXD    1024
  69 #define MAXA    16384
  70 #define MAXI    262144
  71
  72 static int overflow(const char *s)
  73 {
  74     printf("%s overflow\n", s);
  75     exit(1);
  76     return 0;
  77 }
  78
  79 static int incm(struct s_file *fp)
  80 {
  81     return (fp->mc < MAXM) ? fp->mc++ : overflow("mtrl");
  82 }
  83
  84 static int incv(struct s_file *fp)
  85 {
  86     return (fp->vc < MAXV) ? fp->vc++ : overflow("vert");
  87 }
  88
  89 static int ince(struct s_file *fp)
  90 {
  91     return (fp->ec < MAXE) ? fp->ec++ : overflow("edge");
  92 }
  93
  94 static int incs(struct s_file *fp)
  95 {
  96     return (fp->sc < MAXS) ? fp->sc++ : overflow("side");
  97 }
  98
  99 static int inct(struct s_file *fp)
 100 {
 101     return (fp->tc < MAXT) ? fp->tc++ : overflow("texc");
 102 }
 103
 104 static int incg(struct s_file *fp)
 105 {
 106     return (fp->gc < MAXG) ? fp->gc++ : overflow("geom");
 107 }
 108
 109 static int incl(struct s_file *fp)
 110 {
 111     return (fp->lc < MAXL) ? fp->lc++ : overflow("lump");
 112 }
 113
 114 static int incn(struct s_file *fp)
 115 {
 116     return (fp->nc < MAXN) ? fp->nc++ : overflow("node");
 117 }
 118
 119 static int incp(struct s_file *fp)
 120 {
 121     return (fp->pc < MAXP) ? fp->pc++ : overflow("path");
 122 }
 123
 124 static int incb(struct s_file *fp)
 125 {
 126     return (fp->bc < MAXB) ? fp->bc++ : overflow("body");
 127 }
 128
 129 static int inch(struct s_file *fp)
 130 {
 131     return (fp->hc < MAXH) ? fp->hc++ : overflow("item");
 132 }
 133
 134 static int incz(struct s_file *fp)
 135 {
 136     return (fp->zc < MAXZ) ? fp->zc++ : overflow("goal");
 137 }
 138
 139 static int incj(struct s_file *fp)
 140 {
 141     return (fp->jc < MAXJ) ? fp->jc++ : overflow("jump");
 142 }
 143
 144 static int incx(struct s_file *fp)
 145 {
 146     return (fp->xc < MAXX) ? fp->xc++ : overflow("swch");
 147 }
 148
 149 static int incr(struct s_file *fp)
 150 {
 151     return (fp->rc < MAXR) ? fp->rc++ : overflow("bill");
 152 }
 153
 154 static int incu(struct s_file *fp)
 155 {
 156     return (fp->uc < MAXU) ? fp->uc++ : overflow("ball");
 157 }
 158
 159 static int incw(struct s_file *fp)
 160 {
 161     return (fp->wc < MAXW) ? fp->wc++ : overflow("view");
 162 }
 163
 164 static int incd(struct s_file *fp)
 165 {
 166     return (fp->dc < MAXD) ? fp->dc++ : overflow("dict");
 167 }
 168
 169 static int inci(struct s_file *fp)
 170 {
 171     return (fp->ic < MAXI) ? fp->ic++ : overflow("indx");
 172 }
 173
 174 static void init_file(struct s_file *fp)
 175 {
 176     fp->mc = 0;
 177     fp->vc = 0;
 178     fp->ec = 0;
 179     fp->sc = 0;
 180     fp->tc = 0;
 181     fp->gc = 0;
 182     fp->lc = 0;
 183     fp->nc = 0;
 184     fp->pc = 0;
 185     fp->bc = 0;
 186     fp->hc = 0;
 187     fp->zc = 0;
 188     fp->jc = 0;
 189     fp->xc = 0;
 190     fp->rc = 0;
 191     fp->uc = 0;
 192     fp->wc = 0;
 193     fp->dc = 0;
 194     fp->ac = 0;
 195     fp->ic = 0;
 196
 197     fp->mv = (struct s_mtrl *) calloc(MAXM, sizeof (struct s_mtrl));
 198     fp->vv = (struct s_vert *) calloc(MAXV, sizeof (struct s_vert));
 199     fp->ev = (struct s_edge *) calloc(MAXE, sizeof (struct s_edge));
 200     fp->sv = (struct s_side *) calloc(MAXS, sizeof (struct s_side));
 201     fp->tv = (struct s_texc *) calloc(MAXT, sizeof (struct s_texc));
 202     fp->gv = (struct s_geom *) calloc(MAXG, sizeof (struct s_geom));
 203     fp->lv = (struct s_lump *) calloc(MAXL, sizeof (struct s_lump));
 204     fp->nv = (struct s_node *) calloc(MAXN, sizeof (struct s_node));
 205     fp->pv = (struct s_path *) calloc(MAXP, sizeof (struct s_path));
 206     fp->bv = (struct s_body *) calloc(MAXB, sizeof (struct s_body));
 207     fp->hv = (struct s_item *) calloc(MAXH, sizeof (struct s_item));
 208     fp->zv = (struct s_goal *) calloc(MAXZ, sizeof (struct s_goal));
 209     fp->jv = (struct s_jump *) calloc(MAXJ, sizeof (struct s_jump));
 210     fp->xv = (struct s_swch *) calloc(MAXX, sizeof (struct s_swch));
 211     fp->rv = (struct s_bill *) calloc(MAXR, sizeof (struct s_bill));
 212     fp->uv = (struct s_ball *) calloc(MAXU, sizeof (struct s_ball));
 213     fp->wv = (struct s_view *) calloc(MAXW, sizeof (struct s_view));
 214     fp->dv = (struct s_dict *) calloc(MAXD, sizeof (struct s_dict));
 215     fp->av = (char          *) calloc(MAXA, sizeof (char));
 216     fp->iv = (int           *) calloc(MAXI, sizeof (int));
 217 }
 218
 219 /*---------------------------------------------------------------------------*/
 220
 221 /*
 222  * The following is a small  symbol table data structure.  Symbols and
 223  * their integer  values are collected  in symv and  valv.  References
 224  * and pointers  to their unsatisfied integer values  are collected in
 225  * refv and pntv.  The resolve procedure matches references to symbols
 226  * and fills waiting ints with the proper values.
 227  */
 228
 229 #define MAXSYM 2048
 230
 231 static char symv[MAXSYM][MAXSTR];
 232 static int  valv[MAXSYM];
 233
 234 static char refv[MAXSYM][MAXSTR];
 235 static int *pntv[MAXSYM];
 236
 237 static int  strc;
 238 static int  refc;
 239
 240 static void make_sym(const char *s, int  v)
 241 {
 242     strncpy(symv[strc], s, MAXSTR - 1);
 243     valv[strc] = v;
 244     strc++;
 245 }
 246
 247 static void make_ref(const char *r, int *p)
 248 {
 249     strncpy(refv[refc], r, MAXSTR - 1);
 250     pntv[refc] = p;
 251     refc++;
 252 }
 253
 254 static void resolve(void)
 255 {
 256     int i, j;
 257
 258     for (i = 0; i < refc; i++)
 259         for (j = 0; j < strc; j++)
 260             if (strncmp(refv[i], symv[j], MAXSTR) == 0)
 261             {
 262                 *(pntv[i]) = valv[j];
 263                 break;
 264             }
 265 }
 266
 267 /*---------------------------------------------------------------------------*/
 268
 269 /*
 270  * The following globals are used to cache target_positions.  They are
 271  * targeted by various entities and must be resolved in a second pass.
 272  */
 273
 274 static float targ_p [MAXW][3];
 275 static int   targ_wi[MAXW];
 276 static int   targ_ji[MAXW];
 277 static int   targ_n;
 278
 279 static void targets(struct s_file *fp)
 280 {
 281     int i;
 282
 283     for (i = 0; i < fp->wc; i++)
 284         v_cpy(fp->wv[i].q, targ_p[targ_wi[i]]);
 285
 286     for (i = 0; i < fp->jc; i++)
 287         v_cpy(fp->jv[i].q, targ_p[targ_ji[i]]);
 288 }
 289
 290 /*---------------------------------------------------------------------------*/
 291
 292 /*
 293  * The following code caches  image sizes.  Textures are referenced by
 294  * name,  but  their  sizes   are  necessary  when  computing  texture
 295  * coordinates.  This code  allows each file to be  accessed only once
 296  * regardless of the number of surfaces referring to it.
 297  */
 298
 299 struct _imagedata
 300 {
 301     char *s;
 302     int w, h;
 303 };
 304
 305 static struct _imagedata *imagedata = NULL;
 306 static int image_n = 0;
 307 static int image_alloc = 0;
 308
 309 #define IMAGE_REALLOC 32
 310
 311 static void free_imagedata()
 312 {
 313     int i;
 314
 315     if (imagedata)
 316     {
 317         for (i = 0; i < image_n; i++)
 318             free(imagedata[i].s);
 319         free(imagedata);
 320     }
 321
 322     image_n = image_alloc = 0;
 323 }
 324
 325 static int size_load(const char *file, int *w, int *h)
 326 {
 327     void *p;
 328
 329     if ((p = image_load(file, w, h, NULL)))
 330     {
 331         free(p);
 332         return 1;
 333     }
 334     return 0;
 335 }
 336
 337 static void size_image(const char *name, int *w, int *h)
 338 {
 339     char jpg[MAXSTR];
 340     char png[MAXSTR];
 341     int i;
 342
 343     if (imagedata)
 344         for (i = 0; i < image_n; i++)
 345             if (strncmp(imagedata[i].s, name, MAXSTR) == 0)
 346             {
 347                 *w = imagedata[i].w;
 348                 *h = imagedata[i].h;
 349
 350                 return;
 351             }
 352
 353     *w = 0;
 354     *h = 0;
 355
 356     strcpy(jpg, name); strcat(jpg, ".jpg");
 357     strcpy(png, name); strcat(png, ".png");
 358
 359     if (size_load(png, w, h) ||
 360         size_load(jpg, w, h))
 361     {
 362
 363         if (image_n + 1 >= image_alloc)
 364         {
 365             struct _imagedata *tmp =
 366                 (struct _imagedata *) malloc(sizeof(struct _imagedata) * (image_alloc + IMAGE_REALLOC));
 367             if (!tmp)
 368             {
 369                 printf("malloc error\n");
 370                 exit(1);
 371             }
 372             if (imagedata)
 373             {
 374                 (void) memcpy(tmp, imagedata, sizeof(struct _imagedata) * image_alloc);
 375                 free(imagedata);
 376             }
 377             imagedata = tmp;
 378             image_alloc += IMAGE_REALLOC;
 379         }
 380
 381         imagedata[image_n].s = (char *) calloc(strlen(name) + 1, 1);
 382         imagedata[image_n].w = *w;
 383         imagedata[image_n].h = *h;
 384         strcpy(imagedata[image_n].s, name);
 385
 386         image_n++;
 387     }
 388 }
 389
 390 /*---------------------------------------------------------------------------*/
 391
 392 /* Read the given material file, adding a new material to the solid.  */
 393
 394 #define scan_vec4(f, s, v)                                              \
 395     if (fs_gets((s), sizeof (s), (f)))                                  \
 396         sscanf((s), "%f %f %f %f", (v), (v) + 1, (v) + 2, (v) + 3)
 397
 398 static int read_mtrl(struct s_file *fp, const char *name)
 399 {
 400     static char line[MAXSTR];
 401     struct s_mtrl *mp;
 402     fs_file fin;
 403     int mi;
 404
 405     for (mi = 0; mi < fp->mc; mi++)
 406         if (strncmp(name, fp->mv[mi].f, MAXSTR) == 0)
 407             return mi;
 408
 409     mp = fp->mv + incm(fp);
 410
 411     strncpy(mp->f, name, PATHMAX - 1);
 412
 413     mp->a[0] = mp->a[1] = mp->a[2] = 0.2f;
 414     mp->d[0] = mp->d[1] = mp->d[2] = 0.8f;
 415     mp->s[0] = mp->s[1] = mp->s[2] = 0.0f;
 416     mp->e[0] = mp->e[1] = mp->e[2] = 0.0f;
 417     mp->a[3] = mp->d[3] = mp->s[3] = mp->e[3] = 1.0f;
 418     mp->h[0] = 0.0f;
 419     mp->fl   = 0;
 420     mp->angle = 45.0f;
 421
 422     if ((fin = fs_open(name, "r")))
 423     {
 424         scan_vec4(fin, line, mp->d);
 425         scan_vec4(fin, line, mp->a);
 426         scan_vec4(fin, line, mp->s);
 427         scan_vec4(fin, line, mp->e);
 428
 429         if (fs_gets(line, sizeof (line), fin))
 430             mp->h[0] = strtod(line, NULL);
 431
 432         if (fs_gets(line, sizeof (line), fin))
 433             mp->fl = strtol(line, NULL, 10);
 434
 435         if (fs_gets(line, sizeof (line), fin))
 436             mp->angle = strtod(line, NULL);
 437
 438         fs_close(fin);
 439     }
 440     else
 441         fprintf(stderr, "%s: unknown material \"%s\"\n", input_file, name);
 442
 443     return mi;
 444 }
 445
 446 #undef scan_vec4
 447
 448 /*---------------------------------------------------------------------------*/
 449
 450 /*
 451  * All bodies with an associated  path are assumed to be positioned at
 452  * the  beginning of that  path.  These  bodies must  be moved  to the
 453  * origin  in order  for their  path transforms  to  behave correctly.
 454  * This is  how we get away  with defining func_trains  with no origin
 455  * specification.
 456  */
 457
 458 static void move_side(struct s_side *sp, const float p[3])
 459 {
 460     sp->d -= v_dot(sp->n, p);
 461 }
 462
 463 static void move_vert(struct s_vert *vp, const float p[3])
 464 {
 465     v_sub(vp->p, vp->p, p);
 466 }
 467
 468 static void move_lump(struct s_file *fp,
 469                       struct s_lump *lp, const float p[3])
 470 {
 471     int i;
 472
 473     for (i = 0; i < lp->sc; i++)
 474         move_side(fp->sv + fp->iv[lp->s0 + i], p);
 475     for (i = 0; i < lp->vc; i++)
 476         move_vert(fp->vv + fp->iv[lp->v0 + i], p);
 477 }
 478
 479 static void move_body(struct s_file *fp,
 480                       struct s_body *bp)
 481 {
 482     int i, *b;
 483
 484     /* Move the lumps. */
 485
 486     for (i = 0; i < bp->lc; i++)
 487         move_lump(fp, fp->lv + bp->l0 + i, fp->pv[bp->pi].p);
 488
 489     /* Create an array to mark any verts referenced by moved geoms. */
 490
 491     if (bp->gc > 0 && (b = (int *) calloc(fp->vc, sizeof (int))))
 492     {
 493         /* Mark the verts. */
 494
 495         for (i = 0; i < bp->gc; i++)
 496         {
 497             b[fp->gv[fp->iv[bp->g0 + i]].vi] = 1;
 498             b[fp->gv[fp->iv[bp->g0 + i]].vj] = 1;
 499             b[fp->gv[fp->iv[bp->g0 + i]].vk] = 1;
 500         }
 501
 502         /* Apply the motion to the marked vertices. */
 503
 504         for (i = 0; i < fp->vc; ++i)
 505             if (b[i])
 506                 move_vert(fp->vv + i, fp->pv[bp->pi].p);
 507
 508         free(b);
 509     }
 510 }
 511
 512 static void move_file(struct s_file *fp)
 513 {
 514     int i;
 515
 516     for (i = 0; i < fp->bc; i++)
 517         if (fp->bv[i].pi >= 0)
 518             move_body(fp, fp->bv + i);
 519 }
 520
 521 /*---------------------------------------------------------------------------*/
 522
 523 /*
 524  * This is a basic OBJ loader.  It is by no means fully compliant with
 525  * the  OBJ  specification, but  it  works  well  with the  output  of
 526  * Wings3D.  All faces must be triangles and all vertices must include
 527  * normals and  texture coordinates.  Material  names are taken  to be
 528  * references to Neverball materials, rather than MTL definitions.
 529  */
 530
 531 static void read_vt(struct s_file *fp, const char *line)
 532 {
 533     struct s_texc *tp = fp->tv + inct(fp);
 534
 535     sscanf(line, "%f %f", tp->u, tp->u + 1);
 536 }
 537
 538 static void read_vn(struct s_file *fp, const char *line)
 539 {
 540     struct s_side *sp = fp->sv + incs(fp);
 541
 542     sscanf(line, "%f %f %f", sp->n, sp->n + 1, sp->n + 2);
 543 }
 544
 545 static void read_v(struct s_file *fp, const char *line)
 546 {
 547     struct s_vert *vp = fp->vv + incv(fp);
 548
 549     sscanf(line, "%f %f %f", vp->p, vp->p + 1, vp->p + 2);
 550 }
 551
 552 static void read_f(struct s_file *fp, const char *line,
 553                    int v0, int t0, int s0, int mi)
 554 {
 555     struct s_geom *gp = fp->gv + incg(fp);
 556
 557     char c1;
 558     char c2;
 559
 560     sscanf(line, "%d%c%d%c%d %d%c%d%c%d %d%c%d%c%d",
 561            &gp->vi, &c1, &gp->ti, &c2, &gp->si,
 562            &gp->vj, &c1, &gp->tj, &c2, &gp->sj,
 563            &gp->vk, &c1, &gp->tk, &c2, &gp->sk);
 564
 565     gp->vi += (v0 - 1);
 566     gp->vj += (v0 - 1);
 567     gp->vk += (v0 - 1);
 568     gp->ti += (t0 - 1);
 569     gp->tj += (t0 - 1);
 570     gp->tk += (t0 - 1);
 571     gp->si += (s0 - 1);
 572     gp->sj += (s0 - 1);
 573     gp->sk += (s0 - 1);
 574
 575     gp->mi  = mi;
 576 }
 577
 578 static void read_obj(struct s_file *fp, const char *name, int mi)
 579 {
 580     char line[MAXSTR];
 581     char mtrl[MAXSTR];
 582     fs_file fin;
 583
 584     int v0 = fp->vc;
 585     int t0 = fp->tc;
 586     int s0 = fp->sc;
 587
 588     if ((fin = fs_open(name, "r")))
 589     {
 590         while (fs_gets(line, MAXSTR, fin))
 591         {
 592             if (strncmp(line, "usemtl", 6) == 0)
 593             {
 594                 sscanf(line + 6, "%s", mtrl);
 595                 mi = read_mtrl(fp, mtrl);
 596             }
 597
 598             else if (strncmp(line, "f", 1) == 0)
 599             {
 600                 if (fp->mv[mi].d[3] > 0.0f)
 601                     read_f(fp, line + 1, v0, t0, s0, mi);
 602             }
 603
 604             else if (strncmp(line, "vt", 2) == 0) read_vt(fp, line + 2);
 605             else if (strncmp(line, "vn", 2) == 0) read_vn(fp, line + 2);
 606             else if (strncmp(line, "v",  1) == 0) read_v (fp, line + 1);
 607         }
 608         fs_close(fin);
 609     }
 610 }
 611
 612 /*---------------------------------------------------------------------------*/
 613
 614 static float plane_d[MAXS];
 615 static float plane_n[MAXS][3];
 616 static float plane_p[MAXS][3];
 617 static float plane_u[MAXS][3];
 618 static float plane_v[MAXS][3];
 619 static int   plane_f[MAXS];
 620 static int   plane_m[MAXS];
 621
 622 static void make_plane(int   pi, float x0, float y0, float      z0,
 623                        float x1, float y1, float z1,
 624                        float x2, float y2, float z2,
 625                        float tu, float tv, float r,
 626                        float su, float sv, int   fl, const char *s)
 627 {
 628     static const float base[6][3][3] = {
 629         {{  0,  0,  1 }, {  1,  0,  0 }, {  0,  1,  0 }},
 630         {{  0,  0, -1 }, {  1,  0,  0 }, {  0,  1,  0 }},
 631         {{  1,  0,  0 }, {  0,  0, -1 }, {  0,  1,  0 }},
 632         {{ -1,  0,  0 }, {  0,  0, -1 }, {  0,  1,  0 }},
 633         {{  0,  1,  0 }, {  1,  0,  0 }, {  0,  0, -1 }},
 634         {{  0, -1,  0 }, {  1,  0,  0 }, {  0,  0, -1 }},
 635     };
 636
 637     float R[16];
 638     float p0[3], p1[3], p2[3];
 639     float u[3],  v[3],  p[3];
 640     float k, d = 0.0f;
 641     int   i, n = 0;
 642     int   w, h;
 643
 644     size_image(s, &w, &h);
 645
 646     plane_f[pi] = fl ? L_DETAIL : 0;
 647
 648     p0[0] = +x0 / SCALE;
 649     p0[1] = +z0 / SCALE;
 650     p0[2] = -y0 / SCALE;
 651
 652     p1[0] = +x1 / SCALE;
 653     p1[1] = +z1 / SCALE;
 654     p1[2] = -y1 / SCALE;
 655
 656     p2[0] = +x2 / SCALE;
 657     p2[1] = +z2 / SCALE;
 658     p2[2] = -y2 / SCALE;
 659
 660     v_sub(u, p0, p1);
 661     v_sub(v, p2, p1);
 662
 663     v_crs(plane_n[pi], u, v);
 664     v_nrm(plane_n[pi], plane_n[pi]);
 665
 666     plane_d[pi] = v_dot(plane_n[pi], p1);
 667
 668     for (i = 0; i < 6; i++)
 669         if ((k = v_dot(plane_n[pi], base[i][0])) >= d)
 670         {
 671             d = k;
 672             n = i;
 673         }
 674
 675     p[0] = 0.f;
 676     p[1] = 0.f;
 677     p[2] = 0.f;
 678
 679     /* Always rotate around the positive axis */
 680
 681     m_rot(R, base[n - (n % 2)][0], V_RAD(r));
 682
 683     v_mad(p, p, base[n][1], +su * tu / SCALE);
 684     v_mad(p, p, base[n][2], -sv * tv / SCALE);
 685
 686     m_vxfm(plane_u[pi], R, base[n][1]);
 687     m_vxfm(plane_v[pi], R, base[n][2]);
 688     m_vxfm(plane_p[pi], R, p);
 689
 690     v_scl(plane_u[pi], plane_u[pi], 64.f / w);
 691     v_scl(plane_v[pi], plane_v[pi], 64.f / h);
 692
 693     v_scl(plane_u[pi], plane_u[pi], 1.f / su);
 694     v_scl(plane_v[pi], plane_v[pi], 1.f / sv);
 695 }
 696
 697 /*---------------------------------------------------------------------------*/
 698
 699 #define T_EOF 0
 700 #define T_BEG 1
 701 #define T_CLP 2
 702 #define T_KEY 3
 703 #define T_END 4
 704 #define T_NOP 5
 705
 706 static int map_token(fs_file fin, int pi, char key[MAXSTR], char val[MAXSTR])
 707 {
 708     char buf[MAXSTR];
 709
 710     if (fs_gets(buf, MAXSTR, fin))
 711     {
 712         char c;
 713         float x0, y0, z0;
 714         float x1, y1, z1;
 715         float x2, y2, z2;
 716         float tu, tv, r;
 717         float su, sv;
 718         int fl;
 719
 720         /* Scan the beginning or end of a block. */
 721
 722         if (buf[0] == '{') return T_BEG;
 723         if (buf[0] == '}') return T_END;
 724
 725         /* Scan a key-value pair. */
 726
 727         if (buf[0] == '\"')
 728         {
 729             strcpy(key, strtok(buf,  "\""));
 730             (void)      strtok(NULL, "\"");
 731             strcpy(val, strtok(NULL, "\""));
 732
 733             return T_KEY;
 734         }
 735
 736         /* Scan a plane. */
 737
 738         if (sscanf(buf,
 739                    "%c %f %f %f %c "
 740                    "%c %f %f %f %c "
 741                    "%c %f %f %f %c "
 742                    "%s %f %f %f %f %f %d",
 743                    &c, &x0, &y0, &z0, &c,
 744                    &c, &x1, &y1, &z1, &c,
 745                    &c, &x2, &y2, &z2, &c,
 746                    key, &tu, &tv, &r, &su, &sv, &fl) == 22)
 747         {
 748             make_plane(pi, x0, y0, z0,
 749                        x1, y1, z1,
 750                        x2, y2, z2,
 751                        tu, tv, r, su, sv, fl, key);
 752             return T_CLP;
 753         }
 754
 755         /* If it's not recognized, it must be uninteresting. */
 756
 757         return T_NOP;
 758     }
 759     return T_EOF;
 760 }
 761
 762 /*---------------------------------------------------------------------------*/
 763
 764 /* Parse a lump from the given file and add it to the solid. */
 765
 766 static void read_lump(struct s_file *fp, fs_file fin)
 767 {
 768     char k[MAXSTR];
 769     char v[MAXSTR];
 770     int t;
 771
 772     struct s_lump *lp = fp->lv + incl(fp);
 773
 774     lp->s0 = fp->ic;
 775
 776     while ((t = map_token(fin, fp->sc, k, v)))
 777     {
 778         if (t == T_CLP)
 779         {
 780             fp->sv[fp->sc].n[0] = plane_n[fp->sc][0];
 781             fp->sv[fp->sc].n[1] = plane_n[fp->sc][1];
 782             fp->sv[fp->sc].n[2] = plane_n[fp->sc][2];
 783             fp->sv[fp->sc].d    = plane_d[fp->sc];
 784
 785             plane_m[fp->sc] = read_mtrl(fp, k);
 786
 787             fp->iv[fp->ic] = fp->sc;
 788             inci(fp);
 789             incs(fp);
 790             lp->sc++;
 791         }
 792         if (t == T_END)
 793             break;
 794     }
 795 }
 796
 797 /*---------------------------------------------------------------------------*/
 798
 799 static void make_path(struct s_file *fp,
 800                       char k[][MAXSTR],
 801                       char v[][MAXSTR], int c)
 802 {
 803     int i, pi = incp(fp);
 804
 805     struct s_path *pp = fp->pv + pi;
 806
 807     pp->p[0] = 0.f;
 808     pp->p[1] = 0.f;
 809     pp->p[2] = 0.f;
 810     pp->t    = 1.f;
 811     pp->pi   = pi;
 812     pp->f    = 1;
 813     pp->s    = 1;
 814
 815     for (i = 0; i < c; i++)
 816     {
 817         if (strcmp(k[i], "targetname") == 0)
 818             make_sym(v[i], pi);
 819
 820         if (strcmp(k[i], "target") == 0)
 821             make_ref(v[i], &pp->pi);
 822
 823         if (strcmp(k[i], "state") == 0)
 824             pp->f = atoi(v[i]);
 825
 826         if (strcmp(k[i], "speed") == 0)
 827             sscanf(v[i], "%f", &pp->t);
 828
 829         if (strcmp(k[i], "smooth") == 0)
 830             pp->s = atoi(v[i]);
 831
 832         if (strcmp(k[i], "origin") == 0)
 833         {
 834             float x = 0.f, y = 0.f, z = 0.f;
 835
 836             sscanf(v[i], "%f %f %f", &x, &y, &z);
 837
 838             pp->p[0] = +x / SCALE;
 839             pp->p[1] = +z / SCALE;
 840             pp->p[2] = -y / SCALE;
 841         }
 842
 843         if (strcmp(k[i], "angles") == 0)
 844         {
 845             float x = 0.0f, y = 0.0f, z = 0.0f;
 846
 847             /* Pitch, yaw and roll. */
 848
 849             sscanf(v[i], "%f %f %f", &x, &y, &z);
 850
 851             /*
 852              * Find the direction vector from pitch and yaw, use it as
 853              * the rotation axis.
 854              */
 855
 856             x = V_RAD(-x);
 857             y = V_RAD(+y);
 858
 859             pp->e[1] =  fcosf(y) * fcosf(x);
 860             pp->e[2] =  fsinf(x);
 861             pp->e[3] = -fsinf(y) * fcosf(x);
 862
 863             /* Use roll as the rotation angle. */
 864
 865             z = V_RAD(+z) * 0.5f;
 866
 867             pp->e[0] = fcosf(z);
 868             v_scl(pp->e + 1, pp->e + 1, fsinf(z));
 869
 870             pp->fl |= P_ORIENTED;
 871         }
 872     }
 873 }
 874
 875 static void make_dict(struct s_file *fp,
 876                       const char *k,
 877                       const char *v)
 878 {
 879     int space_left, space_needed, di = incd(fp);
 880
 881     struct s_dict *dp = fp->dv + di;
 882
 883     space_left   = MAXA - fp->ac;
 884     space_needed = strlen(k) + 1 + strlen(v) + 1;
 885
 886     if (space_needed > space_left)
 887     {
 888         fp->dc--;
 889         return;
 890     }
 891
 892     dp->ai = fp->ac;
 893     dp->aj = dp->ai + strlen(k) + 1;
 894     fp->ac = dp->aj + strlen(v) + 1;
 895
 896     strncpy(fp->av + dp->ai, k, space_left);
 897     strncpy(fp->av + dp->aj, v, space_left - strlen(k) - 1);
 898 }
 899
 900 static int read_dict_entries = 0;
 901
 902 static void make_body(struct s_file *fp,
 903                       char k[][MAXSTR],
 904                       char v[][MAXSTR], int c, int l0)
 905 {
 906     int i, mi = 0, bi = incb(fp);
 907
 908     int g0 = fp->gc;
 909     int v0 = fp->vc;
 910
 911     float p[3];
 912
 913     float x = 0.f;
 914     float y = 0.f;
 915     float z = 0.f;
 916
 917     struct s_body *bp = fp->bv + bi;
 918
 919     bp->t  = 0.f;
 920     bp->pi = -1;
 921     bp->ni = -1;
 922
 923     for (i = 0; i < c; i++)
 924     {
 925         if (strcmp(k[i], "targetname") == 0)
 926             make_sym(v[i], bi);
 927
 928         else if (strcmp(k[i], "target") == 0)
 929             make_ref(v[i], &bp->pi);
 930
 931         else if (strcmp(k[i], "material") == 0)
 932             mi = read_mtrl(fp, v[i]);
 933
 934         else if (strcmp(k[i], "model") == 0)
 935             read_obj(fp, v[i], mi);
 936
 937         else if (strcmp(k[i], "origin") == 0)
 938             sscanf(v[i], "%f %f %f", &x, &y, &z);
 939
 940         else if (read_dict_entries && strcmp(k[i], "classname") != 0)
 941             make_dict(fp, k[i], v[i]);
 942     }
 943
 944     bp->l0 = l0;
 945     bp->lc = fp->lc - l0;
 946     bp->g0 = fp->ic;
 947     bp->gc = fp->gc - g0;
 948
 949     for (i = 0; i < bp->gc; i++)
 950         fp->iv[inci(fp)] = g0++;
 951
 952     p[0] = +x / SCALE;
 953     p[1] = +z / SCALE;
 954     p[2] = -y / SCALE;
 955
 956     for (i = v0; i < fp->vc; i++)
 957         v_add(fp->vv[i].p, fp->vv[i].p, p);
 958
 959     read_dict_entries = 0;
 960 }
 961
 962 static void make_item(struct s_file *fp,
 963                       char k[][MAXSTR],
 964                       char v[][MAXSTR], int c)
 965 {
 966     int i, hi = inch(fp);
 967
 968     struct s_item *hp = fp->hv + hi;
 969
 970     hp->p[0] = 0.f;
 971     hp->p[1] = 0.f;
 972     hp->p[2] = 0.f;
 973
 974     hp->t = ITEM_NONE;
 975     hp->n = 0;
 976
 977     for (i = 0; i < c; i++)
 978     {
 979         if (strcmp(k[i], "classname") == 0)
 980         {
 981             if (strcmp(v[i], "light") == 0)
 982                 hp->t = ITEM_COIN;
 983             else if (strcmp(v[i], "item_health_large") == 0)
 984                 hp->t = ITEM_GROW;
 985             else if (strcmp(v[i], "item_health_small") == 0)
 986                 hp->t = ITEM_SHRINK;
 987         }
 988
 989         if (strcmp(k[i], "light") == 0)
 990             sscanf(v[i], "%d", &hp->n);
 991
 992         if (strcmp(k[i], "origin") == 0)
 993         {
 994             float x = 0.f, y = 0.f, z = 0.f;
 995
 996             sscanf(v[i], "%f %f %f", &x, &y, &z);
 997
 998             hp->p[0] = +x / SCALE;
 999             hp->p[1] = +z / SCALE;
1000             hp->p[2] = -y / SCALE;
1001         }
1002     }
1003 }
1004
1005 static void make_bill(struct s_file *fp,
1006                       char k[][MAXSTR],
1007                       char v[][MAXSTR], int c)
1008 {
1009     int i, ri = incr(fp);
1010
1011     struct s_bill *rp = fp->rv + ri;
1012
1013     memset(rp, 0, sizeof (struct s_bill));
1014     rp->t = 1.0f;
1015
1016     for (i = 0; i < c; i++)
1017     {
1018         if (strcmp(k[i], "width") == 0)
1019             sscanf(v[i], "%f %f %f", rp->w, rp->w + 1, rp->w + 2);
1020         if (strcmp(k[i], "height") == 0)
1021             sscanf(v[i], "%f %f %f", rp->h, rp->h + 1, rp->h + 2);
1022
1023         if (strcmp(k[i], "xrot") == 0)
1024             sscanf(v[i], "%f %f %f", rp->rx, rp->rx + 1, rp->rx + 2);
1025         if (strcmp(k[i], "yrot") == 0)
1026             sscanf(v[i], "%f %f %f", rp->ry, rp->ry + 1, rp->ry + 2);
1027         if (strcmp(k[i], "zrot") == 0)
1028             sscanf(v[i], "%f %f %f", rp->rz, rp->rz + 1, rp->rz + 2);
1029
1030         if (strcmp(k[i], "time") == 0)
1031             sscanf(v[i], "%f", &rp->t);
1032         if (strcmp(k[i], "dist") == 0)
1033             sscanf(v[i], "%f", &rp->d);
1034         if (strcmp(k[i], "flag") == 0)
1035             sscanf(v[i], "%d", &rp->fl);
1036
1037         if (strcmp(k[i], "image") == 0)
1038         {
1039             rp->mi = read_mtrl(fp, v[i]);
1040             fp->mv[rp->mi].fl |= M_CLAMPED;
1041         }
1042
1043         if (strcmp(k[i], "origin") == 0)
1044         {
1045             float x = 0.f, y = 0.f, z = 0.f;
1046
1047             sscanf(v[i], "%f %f %f", &x, &y, &z);
1048
1049             rp->p[0] = +x / SCALE;
1050             rp->p[1] = +z / SCALE;
1051             rp->p[2] = -y / SCALE;
1052         }
1053     }
1054
1055     if (rp->fl & B_ADDITIVE)
1056         fp->mv[rp->mi].fl |= M_ADDITIVE;
1057 }
1058
1059 static void make_goal(struct s_file *fp,
1060                       char k[][MAXSTR],
1061                       char v[][MAXSTR], int c)
1062 {
1063     int i, zi = incz(fp);
1064
1065     struct s_goal *zp = fp->zv + zi;
1066
1067     zp->p[0] = 0.f;
1068     zp->p[1] = 0.f;
1069     zp->p[2] = 0.f;
1070     zp->r    = 0.75;
1071
1072     for (i = 0; i < c; i++)
1073     {
1074         if (strcmp(k[i], "radius") == 0)
1075             sscanf(v[i], "%f", &zp->r);
1076
1077         if (strcmp(k[i], "origin") == 0)
1078         {
1079             float x = 0.f, y = 0.f, z = 0.f;
1080
1081             sscanf(v[i], "%f %f %f", &x, &y, &z);
1082
1083             zp->p[0] = +(x)      / SCALE;
1084             zp->p[1] = +(z - 24) / SCALE;
1085             zp->p[2] = -(y)      / SCALE;
1086         }
1087     }
1088 }
1089
1090 static void make_view(struct s_file *fp,
1091                       char k[][MAXSTR],
1092                       char v[][MAXSTR], int c)
1093 {
1094     int i, wi = incw(fp);
1095
1096     struct s_view *wp = fp->wv + wi;
1097
1098     wp->p[0] = 0.f;
1099     wp->p[1] = 0.f;
1100     wp->p[2] = 0.f;
1101     wp->q[0] = 0.f;
1102     wp->q[1] = 0.f;
1103     wp->q[2] = 0.f;
1104
1105     for (i = 0; i < c; i++)
1106     {
1107         if (strcmp(k[i], "target") == 0)
1108             make_ref(v[i], targ_wi + wi);
1109
1110         if (strcmp(k[i], "origin") == 0)
1111         {
1112             float x = 0.f, y = 0.f, z = 0.f;
1113
1114             sscanf(v[i], "%f %f %f", &x, &y, &z);
1115
1116             wp->p[0] = +x / SCALE;
1117             wp->p[1] = +z / SCALE;
1118             wp->p[2] = -y / SCALE;
1119         }
1120     }
1121 }
1122
1123 static void make_jump(struct s_file *fp,
1124                       char k[][MAXSTR],
1125                       char v[][MAXSTR], int c)
1126 {
1127     int i, ji = incj(fp);
1128
1129     struct s_jump *jp = fp->jv + ji;
1130
1131     jp->p[0] = 0.f;
1132     jp->p[1] = 0.f;
1133     jp->p[2] = 0.f;
1134     jp->q[0] = 0.f;
1135     jp->q[1] = 0.f;
1136     jp->q[2] = 0.f;
1137     jp->r    = 0.5;
1138
1139     for (i = 0; i < c; i++)
1140     {
1141         if (strcmp(k[i], "radius") == 0)
1142             sscanf(v[i], "%f", &jp->r);
1143
1144         if (strcmp(k[i], "target") == 0)
1145             make_ref(v[i], targ_ji + ji);
1146
1147         if (strcmp(k[i], "origin") == 0)
1148         {
1149             float x = 0.f, y = 0.f, z = 0.f;
1150
1151             sscanf(v[i], "%f %f %f", &x, &y, &z);
1152
1153             jp->p[0] = +x / SCALE;
1154             jp->p[1] = +z / SCALE;
1155             jp->p[2] = -y / SCALE;
1156         }
1157     }
1158 }
1159
1160 static void make_swch(struct s_file *fp,
1161                       char k[][MAXSTR],
1162                       char v[][MAXSTR], int c)
1163 {
1164     int i, xi = incx(fp);
1165
1166     struct s_swch *xp = fp->xv + xi;
1167
1168     xp->p[0] = 0.f;
1169     xp->p[1] = 0.f;
1170     xp->p[2] = 0.f;
1171     xp->r    = 0.5;
1172     xp->pi   = 0;
1173     xp->t0   = 0;
1174     xp->t    = 0;
1175     xp->f0   = 0;
1176     xp->f    = 0;
1177     xp->i    = 0;
1178
1179     for (i = 0; i < c; i++)
1180     {
1181         if (strcmp(k[i], "radius") == 0)
1182             sscanf(v[i], "%f", &xp->r);
1183
1184         if (strcmp(k[i], "target") == 0)
1185             make_ref(v[i], &xp->pi);
1186
1187         if (strcmp(k[i], "timer") == 0)
1188         {
1189             sscanf(v[i], "%f", &xp->t0);
1190             xp->t = xp->t0;
1191         }
1192
1193         if (strcmp(k[i], "state") == 0)
1194         {
1195             xp->f  = atoi(v[i]);
1196             xp->f0 = atoi(v[i]);
1197         }
1198
1199         if (strcmp(k[i], "invisible") == 0)
1200             xp->i = atoi(v[i]);
1201
1202         if (strcmp(k[i], "origin") == 0)
1203         {
1204             float x = 0.f, y = 0.f, z = 0.f;
1205
1206             sscanf(v[i], "%f %f %f", &x, &y, &z);
1207
1208             xp->p[0] = +x / SCALE;
1209             xp->p[1] = +z / SCALE;
1210             xp->p[2] = -y / SCALE;
1211         }
1212     }
1213 }
1214
1215 static void make_targ(struct s_file *fp,
1216                       char k[][MAXSTR],
1217                       char v[][MAXSTR], int c)
1218 {
1219     int i;
1220
1221     targ_p[targ_n][0] = 0.f;
1222     targ_p[targ_n][1] = 0.f;
1223     targ_p[targ_n][2] = 0.f;
1224
1225     for (i = 0; i < c; i++)
1226     {
1227         if (strcmp(k[i], "targetname") == 0)
1228             make_sym(v[i], targ_n);
1229
1230         if (strcmp(k[i], "origin") == 0)
1231         {
1232             float x = 0.f, y = 0.f, z = 0.f;
1233
1234             sscanf(v[i], "%f %f %f", &x, &y, &z);
1235
1236             targ_p[targ_n][0] = +x / SCALE;
1237             targ_p[targ_n][1] = +z / SCALE;
1238             targ_p[targ_n][2] = -y / SCALE;
1239         }
1240     }
1241
1242     targ_n++;
1243 }
1244
1245 static void make_ball(struct s_file *fp,
1246                       char k[][MAXSTR],
1247                       char v[][MAXSTR], int c)
1248 {
1249     int i, ui = incu(fp);
1250
1251     struct s_ball *up = fp->uv + ui;
1252
1253     up->p[0] = 0.0f;
1254     up->p[1] = 0.0f;
1255     up->p[2] = 0.0f;
1256     up->r    = 0.25f;
1257
1258     for (i = 0; i < c; i++)
1259     {
1260         if (strcmp(k[i], "radius") == 0)
1261             sscanf(v[i], "%f", &up->r);
1262
1263         if (strcmp(k[i], "origin") == 0)
1264         {
1265             float x = 0.f, y = 0.f, z = 0.f;
1266
1267             sscanf(v[i], "%f %f %f", &x, &y, &z);
1268
1269             up->p[0] = +(x)      / SCALE;
1270             up->p[1] = +(z - 24) / SCALE;
1271             up->p[2] = -(y)      / SCALE;
1272         }
1273     }
1274
1275     up->p[1] += up->r + SMALL;
1276 }
1277
1278 /*---------------------------------------------------------------------------*/
1279
1280 static void read_ent(struct s_file *fp, fs_file fin)
1281 {
1282     char k[MAXKEY][MAXSTR];
1283     char v[MAXKEY][MAXSTR];
1284     int t, i = 0, c = 0;
1285
1286     int l0 = fp->lc;
1287
1288     while ((t = map_token(fin, -1, k[c], v[c])))
1289     {
1290         if (t == T_KEY)
1291         {
1292             if (strcmp(k[c], "classname") == 0)
1293                 i = c;
1294             c++;
1295         }
1296         if (t == T_BEG) read_lump(fp, fin);
1297         if (t == T_END) break;
1298     }
1299
1300     if (!strcmp(v[i], "light"))                    make_item(fp, k, v, c);
1301     if (!strcmp(v[i], "item_health_large"))        make_item(fp, k, v, c);
1302     if (!strcmp(v[i], "item_health_small"))        make_item(fp, k, v, c);
1303     if (!strcmp(v[i], "info_camp"))                make_swch(fp, k, v, c);
1304     if (!strcmp(v[i], "info_null"))                make_bill(fp, k, v, c);
1305     if (!strcmp(v[i], "path_corner"))              make_path(fp, k, v, c);
1306     if (!strcmp(v[i], "info_player_start"))        make_ball(fp, k, v, c);
1307     if (!strcmp(v[i], "info_player_intermission")) make_view(fp, k, v, c);
1308     if (!strcmp(v[i], "info_player_deathmatch"))   make_goal(fp, k, v, c);
1309     if (!strcmp(v[i], "target_teleporter"))        make_jump(fp, k, v, c);
1310     if (!strcmp(v[i], "target_position"))          make_targ(fp, k, v, c);
1311     if (!strcmp(v[i], "worldspawn"))
1312     {
1313         read_dict_entries = 1;
1314         make_body(fp, k, v, c, l0);
1315     }
1316     if (!strcmp(v[i], "func_train"))               make_body(fp, k, v, c, l0);
1317     if (!strcmp(v[i], "misc_model"))               make_body(fp, k, v, c, l0);
1318 }
1319
1320 static void read_map(struct s_file *fp, fs_file fin)
1321 {
1322     char k[MAXSTR];
1323     char v[MAXSTR];
1324     int t;
1325
1326     while ((t = map_token(fin, -1, k, v)))
1327         if (t == T_BEG)
1328             read_ent(fp, fin);
1329 }
1330
1331 /*---------------------------------------------------------------------------*/
1332
1333 /* Test the location of a point with respect to a side plane. */
1334
1335 static int fore_side(const float p[3], const struct s_side *sp)
1336 {
1337     return (v_dot(p, sp->n) - sp->d > +SMALL) ? 1 : 0;
1338 }
1339
1340 static int on_side(const float p[3], const struct s_side *sp)
1341 {
1342     float d = v_dot(p, sp->n) - sp->d;
1343
1344     return (-SMALL < d && d < +SMALL) ? 1 : 0;
1345 }
1346
1347 /*---------------------------------------------------------------------------*/
1348 /*
1349  * Confirm  that  the addition  of  a vert  would  not  result in  degenerate
1350  * geometry.
1351  */
1352
1353 static int ok_vert(const struct s_file *fp,
1354                    const struct s_lump *lp, const float p[3])
1355 {
1356     float r[3];
1357     int i;
1358
1359     for (i = 0; i < lp->vc; i++)
1360     {
1361         float *q = fp->vv[fp->iv[lp->v0 + i]].p;
1362
1363         v_sub(r, p, q);
1364
1365         if (v_len(r) < SMALL)
1366             return 0;
1367     }
1368     return 1;
1369 }
1370
1371 /*---------------------------------------------------------------------------*/
1372
1373 /*
1374  * The following functions take the  set of planes defining a lump and
1375  * find the verts, edges, and  geoms that describe its boundaries.  To
1376  * do this, they first find the verts, and then search these verts for
1377  * valid edges and  geoms.  It may be more  efficient to compute edges
1378  * and  geoms directly  by clipping  down infinite  line  segments and
1379  * planes,  but this  would be  more  complex and  prone to  numerical
1380  * error.
1381  */
1382
1383 /*
1384  * Given 3  side planes,  compute the point  of intersection,  if any.
1385  * Confirm that this point falls  within the current lump, and that it
1386  * is unique.  Add it as a vert of the solid.
1387  */
1388 static void clip_vert(struct s_file *fp,
1389                       struct s_lump *lp, int si, int sj, int sk)
1390 {
1391     float M[16], X[16], I[16];
1392     float d[3],  p[3];
1393     int i;
1394
1395     d[0] = fp->sv[si].d;
1396     d[1] = fp->sv[sj].d;
1397     d[2] = fp->sv[sk].d;
1398
1399     m_basis(M, fp->sv[si].n, fp->sv[sj].n, fp->sv[sk].n);
1400     m_xps(X, M);
1401
1402     if (m_inv(I, X))
1403     {
1404         m_vxfm(p, I, d);
1405
1406         for (i = 0; i < lp->sc; i++)
1407         {
1408             int si = fp->iv[lp->s0 + i];
1409
1410             if (fore_side(p, fp->sv + si))
1411                 return;
1412         }
1413
1414         if (ok_vert(fp, lp, p))
1415         {
1416             v_cpy(fp->vv[fp->vc].p, p);
1417
1418             fp->iv[fp->ic] = fp->vc;
1419             inci(fp);
1420             incv(fp);
1421             lp->vc++;
1422         }
1423     }
1424 }
1425
1426 /*
1427  * Given two  side planes,  find an edge  along their  intersection by
1428  * finding a pair of vertices that fall on both planes.  Add it to the
1429  * solid.
1430  */
1431 static void clip_edge(struct s_file *fp,
1432                       struct s_lump *lp, int si, int sj)
1433 {
1434     int i, j;
1435
1436     for (i = 1; i < lp->vc; i++)
1437     {
1438         int vi = fp->iv[lp->v0 + i];
1439
1440         if (!on_side(fp->vv[vi].p, fp->sv + si) ||
1441             !on_side(fp->vv[vi].p, fp->sv + sj))
1442             continue;
1443
1444         for (j = 0; j < i; j++)
1445         {
1446             int vj = fp->iv[lp->v0 + j];
1447
1448             if (on_side(fp->vv[vj].p, fp->sv + si) &&
1449                 on_side(fp->vv[vj].p, fp->sv + sj))
1450             {
1451                 fp->ev[fp->ec].vi = vi;
1452                 fp->ev[fp->ec].vj = vj;
1453
1454                 fp->iv[fp->ic] = fp->ec;
1455
1456                 inci(fp);
1457                 ince(fp);
1458                 lp->ec++;
1459             }
1460         }
1461     }
1462 }
1463
1464 /*
1465  * Find all verts that lie on  the given side of the lump.  Sort these
1466  * verts to  have a counter-clockwise winding about  the plane normal.
1467  * Create geoms to tessellate the resulting convex polygon.
1468  */
1469 static void clip_geom(struct s_file *fp,
1470                       struct s_lump *lp, int si)
1471 {
1472     int   m[256], t[256], d, i, j, n = 0;
1473     float u[3];
1474     float v[3];
1475     float w[3];
1476
1477     struct s_side *sp = fp->sv + si;
1478
1479     /* Find em. */
1480
1481     for (i = 0; i < lp->vc; i++)
1482     {
1483         int vi = fp->iv[lp->v0 + i];
1484
1485         if (on_side(fp->vv[vi].p, sp))
1486         {
1487             m[n] = vi;
1488             t[n] = inct(fp);
1489
1490             v_add(v, fp->vv[vi].p, plane_p[si]);
1491
1492             fp->tv[t[n]].u[0] = v_dot(v, plane_u[si]);
1493             fp->tv[t[n]].u[1] = v_dot(v, plane_v[si]);
1494
1495             n++;
1496         }
1497     }
1498
1499     /* Sort em. */
1500
1501     for (i = 1; i < n; i++)
1502         for (j = i + 1; j < n; j++)
1503         {
1504             v_sub(u, fp->vv[m[i]].p, fp->vv[m[0]].p);
1505             v_sub(v, fp->vv[m[j]].p, fp->vv[m[0]].p);
1506             v_crs(w, u, v);
1507
1508             if (v_dot(w, sp->n) < 0.f)
1509             {
1510                 d     = m[i];
1511                 m[i]  = m[j];
1512                 m[j]  =    d;
1513
1514                 d     = t[i];
1515                 t[i]  = t[j];
1516                 t[j]  =    d;
1517             }
1518         }
1519
1520     /* Index em. */
1521
1522     for (i = 0; i < n - 2; i++)
1523     {
1524         fp->gv[fp->gc].mi = plane_m[si];
1525
1526         fp->gv[fp->gc].ti = t[0];
1527         fp->gv[fp->gc].tj = t[i + 1];
1528         fp->gv[fp->gc].tk = t[i + 2];
1529
1530         fp->gv[fp->gc].si = si;
1531         fp->gv[fp->gc].sj = si;
1532         fp->gv[fp->gc].sk = si;
1533
1534         fp->gv[fp->gc].vi = m[0];
1535         fp->gv[fp->gc].vj = m[i + 1];
1536         fp->gv[fp->gc].vk = m[i + 2];
1537
1538         fp->iv[fp->ic] = fp->gc;
1539         inci(fp);
1540         incg(fp);
1541         lp->gc++;
1542     }
1543 }
1544
1545 /*
1546  * Iterate the sides of the lump, attempting to generate a new vert for
1547  * each trio of planes, a new edge  for each pair of planes, and a new
1548  * set of geom for each visible plane.
1549  */
1550 static void clip_lump(struct s_file *fp, struct s_lump *lp)
1551 {
1552     int i, j, k;
1553
1554     lp->v0 = fp->ic;
1555     lp->vc = 0;
1556
1557     for (i = 2; i < lp->sc; i++)
1558         for (j = 1; j < i; j++)
1559             for (k = 0; k < j; k++)
1560                 clip_vert(fp, lp,
1561                           fp->iv[lp->s0 + i],
1562                           fp->iv[lp->s0 + j],
1563                           fp->iv[lp->s0 + k]);
1564
1565     lp->e0 = fp->ic;
1566     lp->ec = 0;
1567
1568     for (i = 1; i < lp->sc; i++)
1569         for (j = 0; j < i; j++)
1570             clip_edge(fp, lp,
1571                       fp->iv[lp->s0 + i],
1572                       fp->iv[lp->s0 + j]);
1573
1574     lp->g0 = fp->ic;
1575     lp->gc = 0;
1576
1577     for (i = 0; i < lp->sc; i++)
1578         if (fp->mv[plane_m[fp->iv[lp->s0 + i]]].d[3] > 0.0f)
1579             clip_geom(fp, lp,
1580                       fp->iv[lp->s0 + i]);
1581
1582     for (i = 0; i < lp->sc; i++)
1583         if (plane_f[fp->iv[lp->s0 + i]])
1584             lp->fl |= L_DETAIL;
1585 }
1586
1587 static void clip_file(struct s_file *fp)
1588 {
1589     int i;
1590
1591     for (i = 0; i < fp->lc; i++)
1592         clip_lump(fp, fp->lv + i);
1593 }
1594
1595 /*---------------------------------------------------------------------------*/
1596
1597 /*
1598  * For each body element type,  determine if element 'p' is equivalent
1599  * to element  'q'.  This  is more than  a simple memory  compare.  It
1600  * effectively  snaps mtrls and  verts together,  and may  reverse the
1601  * winding of  an edge or a geom.   This is done in  order to maximize
1602  * the number of elements that can be eliminated.
1603  */
1604
1605 static int comp_mtrl(const struct s_mtrl *mp, const struct s_mtrl *mq)
1606 {
1607     if (fabs(mp->d[0] - mq->d[0]) > SMALL) return 0;
1608     if (fabs(mp->d[1] - mq->d[1]) > SMALL) return 0;
1609     if (fabs(mp->d[2] - mq->d[2]) > SMALL) return 0;
1610     if (fabs(mp->d[3] - mq->d[3]) > SMALL) return 0;
1611
1612     if (fabs(mp->a[0] - mq->a[0]) > SMALL) return 0;
1613     if (fabs(mp->a[1] - mq->a[1]) > SMALL) return 0;
1614     if (fabs(mp->a[2] - mq->a[2]) > SMALL) return 0;
1615     if (fabs(mp->a[3] - mq->a[3]) > SMALL) return 0;
1616
1617     if (fabs(mp->s[0] - mq->s[0]) > SMALL) return 0;
1618     if (fabs(mp->s[1] - mq->s[1]) > SMALL) return 0;
1619     if (fabs(mp->s[2] - mq->s[2]) > SMALL) return 0;
1620     if (fabs(mp->s[3] - mq->s[3]) > SMALL) return 0;
1621
1622     if (fabs(mp->e[0] - mq->e[0]) > SMALL) return 0;
1623     if (fabs(mp->e[1] - mq->e[1]) > SMALL) return 0;
1624     if (fabs(mp->e[2] - mq->e[2]) > SMALL) return 0;
1625     if (fabs(mp->e[3] - mq->e[3]) > SMALL) return 0;
1626
1627     if (fabs(mp->h[0] - mq->h[0]) > SMALL) return 0;
1628
1629     if (strncmp(mp->f, mq->f, PATHMAX)) return 0;
1630
1631     return 1;
1632 }
1633
1634 static int comp_vert(const struct s_vert *vp, const struct s_vert *vq)
1635 {
1636     if (fabs(vp->p[0] - vq->p[0]) > SMALL) return 0;
1637     if (fabs(vp->p[1] - vq->p[1]) > SMALL) return 0;
1638     if (fabs(vp->p[2] - vq->p[2]) > SMALL) return 0;
1639
1640     return 1;
1641 }
1642
1643 static int comp_edge(const struct s_edge *ep, const struct s_edge *eq)
1644 {
1645     if (ep->vi != eq->vi && ep->vi != eq->vj) return 0;
1646     if (ep->vj != eq->vi && ep->vj != eq->vj) return 0;
1647
1648     return 1;
1649 }
1650
1651 static int comp_side(const struct s_side *sp, const struct s_side *sq)
1652 {
1653     if  (fabs(sp->d - sq->d) > SMALL)  return 0;
1654     if (v_dot(sp->n,  sq->n) < 0.9999) return 0;
1655
1656     return 1;
1657 }
1658
1659 static int comp_texc(const struct s_texc *tp, const struct s_texc *tq)
1660 {
1661     if (fabs(tp->u[0] - tq->u[0]) > SMALL) return 0;
1662     if (fabs(tp->u[1] - tq->u[1]) > SMALL) return 0;
1663
1664     return 1;
1665 }
1666
1667 static int comp_geom(const struct s_geom *gp, const struct s_geom *gq)
1668 {
1669     if (gp->mi != gq->mi) return 0;
1670
1671     if (gp->ti != gq->ti) return 0;
1672     if (gp->si != gq->si) return 0;
1673     if (gp->vi != gq->vi) return 0;
1674
1675     if (gp->tj != gq->tj) return 0;
1676     if (gp->sj != gq->sj) return 0;
1677     if (gp->vj != gq->vj) return 0;
1678
1679     if (gp->tk != gq->tk) return 0;
1680     if (gp->sk != gq->sk) return 0;
1681     if (gp->vk != gq->vk) return 0;
1682
1683     return 1;
1684 }
1685
1686 /*---------------------------------------------------------------------------*/
1687
1688 /*
1689  * For each file  element type, replace all references  to element 'i'
1690  * with a  reference to element  'j'.  These are used  when optimizing
1691  * and sorting the file.
1692  */
1693
1694 static void swap_mtrl(struct s_file *fp, int mi, int mj)
1695 {
1696     int i;
1697
1698     for (i = 0; i < fp->gc; i++)
1699         if (fp->gv[i].mi == mi) fp->gv[i].mi = mj;
1700     for (i = 0; i < fp->rc; i++)
1701         if (fp->rv[i].mi == mi) fp->rv[i].mi = mj;
1702 }
1703
1704 static int vert_swaps[MAXV];
1705
1706 static void apply_vert_swaps(struct s_file *fp)
1707 {
1708     int i, j;
1709
1710     for (i = 0; i < fp->ec; i++)
1711     {
1712         fp->ev[i].vi = vert_swaps[fp->ev[i].vi];
1713         fp->ev[i].vj = vert_swaps[fp->ev[i].vj];
1714     }
1715
1716     for (i = 0; i < fp->gc; i++)
1717     {
1718         fp->gv[i].vi = vert_swaps[fp->gv[i].vi];
1719         fp->gv[i].vj = vert_swaps[fp->gv[i].vj];
1720         fp->gv[i].vk = vert_swaps[fp->gv[i].vk];
1721     }
1722
1723     for (i = 0; i < fp->lc; i++)
1724         for (j = 0; j < fp->lv[i].vc; j++)
1725             fp->iv[fp->lv[i].v0 + j] = vert_swaps[fp->iv[fp->lv[i].v0 + j]];
1726 }
1727
1728 static void swap_vert(struct s_file *fp, int vi, int vj)
1729 {
1730     int i, j;
1731
1732     for (i = 0; i < fp->ec; i++)
1733     {
1734         if (fp->ev[i].vi == vi) fp->ev[i].vi = vj;
1735         if (fp->ev[i].vj == vi) fp->ev[i].vj = vj;
1736     }
1737
1738     for (i = 0; i < fp->gc; i++)
1739     {
1740         if (fp->gv[i].vi == vi) fp->gv[i].vi = vj;
1741         if (fp->gv[i].vj == vi) fp->gv[i].vj = vj;
1742         if (fp->gv[i].vk == vi) fp->gv[i].vk = vj;
1743     }
1744
1745     for (i = 0; i < fp->lc; i++)
1746         for (j = 0; j < fp->lv[i].vc; j++)
1747             if (fp->iv[fp->lv[i].v0 + j] == vi)
1748                 fp->iv[fp->lv[i].v0 + j]  = vj;
1749 }
1750
1751 static int edge_swaps[MAXE];
1752
1753 static void apply_edge_swaps(struct s_file *fp)
1754 {
1755     int i, j;
1756
1757     for (i = 0; i < fp->lc; i++)
1758         for (j = 0; j < fp->lv[i].ec; j++)
1759             fp->iv[fp->lv[i].e0 + j] = edge_swaps[fp->iv[fp->lv[i].e0 + j]];
1760 }
1761
1762 static int side_swaps[MAXS];
1763
1764 static void apply_side_swaps(struct s_file *fp)
1765 {
1766     int i, j;
1767
1768     for (i = 0; i < fp->gc; i++)
1769     {
1770         fp->gv[i].si = side_swaps[fp->gv[i].si];
1771         fp->gv[i].sj = side_swaps[fp->gv[i].sj];
1772         fp->gv[i].sk = side_swaps[fp->gv[i].sk];
1773     }
1774     for (i = 0; i < fp->nc; i++)
1775         fp->nv[i].si = side_swaps[fp->nv[i].si];
1776
1777     for (i = 0; i < fp->lc; i++)
1778         for (j = 0; j < fp->lv[i].sc; j++)
1779             fp->iv[fp->lv[i].s0 + j] = side_swaps[fp->iv[fp->lv[i].s0 + j]];
1780 }
1781
1782 static int texc_swaps[MAXT];
1783
1784 static void apply_texc_swaps(struct s_file *fp)
1785 {
1786     int i;
1787
1788     for (i = 0; i < fp->gc; i++)
1789     {
1790         fp->gv[i].ti = texc_swaps[fp->gv[i].ti];
1791         fp->gv[i].tj = texc_swaps[fp->gv[i].tj];
1792         fp->gv[i].tk = texc_swaps[fp->gv[i].tk];
1793     }
1794 }
1795
1796 static int geom_swaps[MAXG];
1797
1798 static void apply_geom_swaps(struct s_file *fp)
1799 {
1800     int i, j;
1801
1802     for (i = 0; i < fp->lc; i++)
1803         for (j = 0; j < fp->lv[i].gc; j++)
1804             fp->iv[fp->lv[i].g0 + j] = geom_swaps[fp->iv[fp->lv[i].g0 + j]];
1805
1806     for (i = 0; i < fp->bc; i++)
1807         for (j = 0; j < fp->bv[i].gc; j++)
1808             fp->iv[fp->bv[i].g0 + j] = geom_swaps[fp->iv[fp->bv[i].g0 + j]];
1809 }
1810
1811 /*---------------------------------------------------------------------------*/
1812
1813 static void uniq_mtrl(struct s_file *fp)
1814 {
1815     int i, j, k = 0;
1816
1817     for (i = 0; i < fp->mc; i++)
1818     {
1819         for (j = 0; j < k; j++)
1820             if (comp_mtrl(fp->mv + i, fp->mv + j))
1821             {
1822                 swap_mtrl(fp, i, j);
1823                 break;
1824             }
1825
1826         if (j == k)
1827         {
1828             if (i != k)
1829             {
1830                 fp->mv[k] = fp->mv[i];
1831                 swap_mtrl(fp, i, k);
1832             }
1833             k++;
1834         }
1835     }
1836
1837     fp->mc = k;
1838 }
1839
1840 static void uniq_vert(struct s_file *fp)
1841 {
1842     int i, j, k = 0;
1843
1844     for (i = 0; i < fp->vc; i++)
1845     {
1846         for (j = 0; j < k; j++)
1847             if (comp_vert(fp->vv + i, fp->vv + j))
1848                 break;
1849
1850         vert_swaps[i] = j;
1851
1852         if (j == k)
1853         {
1854             if (i != k)
1855                 fp->vv[k] = fp->vv[i];
1856             k++;
1857         }
1858     }
1859
1860     apply_vert_swaps(fp);
1861
1862     fp->vc = k;
1863 }
1864
1865 static void uniq_edge(struct s_file *fp)
1866 {
1867     int i, j, k = 0;
1868
1869     for (i = 0; i < fp->ec; i++)
1870     {
1871         for (j = 0; j < k; j++)
1872             if (comp_edge(fp->ev + i, fp->ev + j))
1873                 break;
1874
1875         edge_swaps[i] = j;
1876
1877         if (j == k)
1878         {
1879             if (i != k)
1880                 fp->ev[k] = fp->ev[i];
1881             k++;
1882         }
1883     }
1884
1885     apply_edge_swaps(fp);
1886
1887     fp->ec = k;
1888 }
1889
1890 static int geomlist[MAXV];
1891 static int nextgeom[MAXG];
1892
1893 static void uniq_geom(struct s_file *fp)
1894 {
1895     int i, j, k = 0;
1896
1897     for (i = 0; i < MAXV; i++)
1898         geomlist[i] = -1;
1899
1900     for (i = 0; i < fp->gc; i++)
1901     {
1902         int key = fp->gv[i].vj;
1903
1904         for (j = geomlist[key]; j != -1; j = nextgeom[j])
1905             if (comp_geom(fp->gv + i, fp->gv + j))
1906                 goto found;
1907
1908         fp->gv[k] = fp->gv[i];
1909
1910         nextgeom[k] = geomlist[key];
1911         geomlist[key] = k;
1912
1913         j = k;
1914         k++;
1915
1916 found:
1917         geom_swaps[i] = j;
1918     }
1919
1920     apply_geom_swaps(fp);
1921
1922     fp->gc = k;
1923 }
1924
1925 static void uniq_texc(struct s_file *fp)
1926 {
1927     int i, j, k = 0;
1928
1929     for (i = 0; i < fp->tc; i++)
1930     {
1931         for (j = 0; j < k; j++)
1932             if (comp_texc(fp->tv + i, fp->tv + j))
1933                 break;
1934
1935         texc_swaps[i] = j;
1936
1937         if (j == k)
1938         {
1939             if (i != k)
1940                 fp->tv[k] = fp->tv[i];
1941             k++;
1942         }
1943     }
1944
1945     apply_texc_swaps(fp);
1946
1947     fp->tc = k;
1948 }
1949
1950 static void uniq_side(struct s_file *fp)
1951 {
1952     int i, j, k = 0;
1953
1954     for (i = 0; i < fp->sc; i++)
1955     {
1956         for (j = 0; j < k; j++)
1957             if (comp_side(fp->sv + i, fp->sv + j))
1958                 break;
1959
1960         side_swaps[i] = j;
1961
1962         if (j == k)
1963         {
1964             if (i != k)
1965                 fp->sv[k] = fp->sv[i];
1966             k++;
1967         }
1968     }
1969
1970     apply_side_swaps(fp);
1971
1972     fp->sc = k;
1973 }
1974
1975 static void uniq_file(struct s_file *fp)
1976 {
1977     /* Debug mode skips optimization, producing oversized output files. */
1978
1979     if (debug_output == 0)
1980     {
1981         uniq_mtrl(fp);
1982         uniq_vert(fp);
1983         uniq_edge(fp);
1984         uniq_side(fp);
1985         uniq_texc(fp);
1986         uniq_geom(fp);
1987     }
1988 }
1989
1990 /*---------------------------------------------------------------------------*/
1991
1992 struct s_trip
1993 {
1994     int vi;
1995     int mi;
1996     int si;
1997     int gi;
1998 };
1999
2000 static int comp_trip(const void *p, const void *q)
2001 {
2002     const struct s_trip *tp = (const struct s_trip *) p;
2003     const struct s_trip *tq = (const struct s_trip *) q;
2004
2005     if (tp->vi < tq->vi) return -1;
2006     if (tp->vi > tq->vi) return +1;
2007     if (tp->mi < tq->mi) return -1;
2008     if (tp->mi > tq->mi) return +1;
2009
2010     return 0;
2011 }
2012
2013 static void smth_file(struct s_file *fp)
2014 {
2015     struct s_trip temp, *T;
2016
2017     if (debug_output == 0)
2018     {
2019         if ((T = (struct s_trip *) malloc(fp->gc * 3 * sizeof (struct s_trip))))
2020         {
2021             int gi, i, j, k, l, c = 0;
2022
2023             /* Create a list of all non-faceted vertex triplets. */
2024
2025             for (gi = 0; gi < fp->gc; ++gi)
2026             {
2027                 struct s_geom *gp = fp->gv + gi;
2028
2029                 T[c].vi = gp->vi;
2030                 T[c].mi = gp->mi;
2031                 T[c].si = gp->si;
2032                 T[c].gi = gi;
2033                 c++;
2034
2035                 T[c].vi = gp->vj;
2036                 T[c].mi = gp->mi;
2037                 T[c].si = gp->sj;
2038                 T[c].gi = gi;
2039                 c++;
2040
2041                 T[c].vi = gp->vk;
2042                 T[c].mi = gp->mi;
2043                 T[c].si = gp->sk;
2044                 T[c].gi = gi;
2045                 c++;
2046             }
2047
2048             /* Sort all triplets by vertex index and material. */
2049
2050             qsort(T, c, sizeof (struct s_trip), comp_trip);
2051
2052             /* For each set of triplets sharing vertex index and material... */
2053
2054             for (i = 0; i < c; i = l)
2055             {
2056                 int acc = 0;
2057
2058                 float N[3], angle = fp->mv[T[i].mi].angle;
2059                 const float   *Ni = fp->sv[T[i].si].n;
2060
2061                 /* Sort the set by side similarity to the first. */
2062
2063                 for (j = i + 1; j < c && (T[j].vi == T[i].vi &&
2064                                           T[j].mi == T[i].mi); ++j)
2065                 {
2066                     for (k = j + 1; k < c && (T[k].vi == T[i].vi &&
2067                                               T[k].mi == T[i].mi); ++k)
2068                     {
2069                         const float *Nj = fp->sv[T[j].si].n;
2070                         const float *Nk = fp->sv[T[k].si].n;
2071
2072                         if (T[j].si != T[k].si && v_dot(Nk, Ni) > v_dot(Nj, Ni))
2073                         {
2074                             temp = T[k];
2075                             T[k] = T[j];
2076                             T[j] = temp;
2077                         }
2078                     }
2079                 }
2080
2081                 /* Accumulate all similar side normals. */
2082
2083                 N[0] = Ni[0];
2084                 N[1] = Ni[1];
2085                 N[2] = Ni[2];
2086
2087                 for (l = i + 1; l < c && (T[l].vi == T[i].vi &&
2088                                           T[l].mi == T[i].mi); ++l)
2089                     if (T[l].si != T[i].si)
2090                     {
2091                         const float *Nl = fp->sv[T[l].si].n;
2092
2093                         if (V_DEG(facosf(v_dot(Ni, Nl))) > angle)
2094                             break;
2095
2096                         N[0] += Nl[0];
2097                         N[1] += Nl[1];
2098                         N[2] += Nl[2];
2099
2100                         acc++;
2101                     }
2102
2103                 /* If at least two normals have been accumulated... */
2104
2105                 if (acc)
2106                 {
2107                     /* Store the accumulated normal as a new side. */
2108
2109                     int ss = incs(fp);
2110
2111                     v_nrm(fp->sv[ss].n, N);
2112                     fp->sv[ss].d = 0.0f;
2113
2114                     /* Assign the new normal to the merged triplets. */
2115
2116                     for (j = i; j < l; ++j)
2117                         T[j].si = ss;
2118                 }
2119             }
2120
2121             /* Assign the remapped normals to the original geoms. */
2122
2123             for (i = 0; i < c; ++i)
2124             {
2125                 struct s_geom *gp = fp->gv + T[i].gi;
2126
2127                 if (gp->vi == T[i].vi) gp->si = T[i].si;
2128                 if (gp->vj == T[i].vi) gp->sj = T[i].si;
2129                 if (gp->vk == T[i].vi) gp->sk = T[i].si;
2130             }
2131
2132             free(T);
2133         }
2134
2135         uniq_side(fp);
2136     }
2137 }
2138
2139
2140 /*---------------------------------------------------------------------------*/
2141
2142 static void sort_file(struct s_file *fp)
2143 {
2144     int i, j;
2145
2146     /* Sort billboards by material within distance. */
2147
2148     for (i = 0; i < fp->rc; i++)
2149         for (j = i + 1; j < fp->rc; j++)
2150             if ((fp->rv[j].d  > fp->rv[i].d) ||
2151                 (fp->rv[j].d == fp->rv[i].d &&
2152                  fp->rv[j].mi > fp->rv[i].mi))
2153             {
2154                 struct s_bill t;
2155
2156                 t         = fp->rv[i];
2157                 fp->rv[i] = fp->rv[j];
2158                 fp->rv[j] =         t;
2159             }
2160
2161     /* Ensure the first vertex is the lowest. */
2162
2163     for (i = 0; i < fp->vc; i++)
2164         if (fp->vv[0].p[1] > fp->vv[i].p[1])
2165         {
2166             struct s_vert t;
2167
2168             t         = fp->vv[0];
2169             fp->vv[0] = fp->vv[i];
2170             fp->vv[i] =         t;
2171
2172             swap_vert(fp,  0, -1);
2173             swap_vert(fp,  i,  0);
2174             swap_vert(fp, -1,  i);
2175         }
2176 }
2177
2178 /*---------------------------------------------------------------------------*/
2179
2180 static int test_lump_side(const struct s_file *fp,
2181                           const struct s_lump *lp,
2182                           const struct s_side *sp,
2183                           float bsphere[4])
2184 {
2185     int si;
2186     int vi;
2187
2188     int f = 0;
2189     int b = 0;
2190
2191     float d;
2192
2193     if (!lp->vc)
2194         return 0;
2195
2196     /* Check if the bounding sphere of the lump is completely on one side. */
2197
2198     d = v_dot(bsphere, sp->n) - sp->d;
2199
2200     if (fabs(d) > bsphere[3])
2201         return d > 0 ? 1 : -1;
2202
2203     /* If the given side is part of the given lump, then the lump is behind. */
2204
2205     for (si = 0; si < lp->sc; si++)
2206         if (fp->sv + fp->iv[lp->s0 + si] == sp)
2207             return -1;
2208
2209     /* Check if each lump vertex is in front of, behind, on the side. */
2210
2211     for (vi = 0; vi < lp->vc; vi++)
2212     {
2213         float d = v_dot(fp->vv[fp->iv[lp->v0 + vi]].p, sp->n) - sp->d;
2214
2215         if (d > 0) f++;
2216         if (d < 0) b++;
2217     }
2218
2219     /* If no verts are behind, the lump is in front, and vice versa. */
2220
2221     if (f > 0 && b == 0) return +1;
2222     if (b > 0 && f == 0) return -1;
2223
2224     /* Else, the lump crosses the side. */
2225
2226     return 0;
2227 }
2228
2229 static int node_node(struct s_file *fp, int l0, int lc, float bsphere[][4])
2230 {
2231     if (lc < 8)
2232     {
2233         /* Base case.  Dump all given lumps into a leaf node. */
2234
2235         fp->nv[fp->nc].si = -1;
2236         fp->nv[fp->nc].ni = -1;
2237         fp->nv[fp->nc].nj = -1;
2238         fp->nv[fp->nc].l0 = l0;
2239         fp->nv[fp->nc].lc = lc;
2240
2241         return incn(fp);
2242     }
2243     else
2244     {
2245         int sj  = 0;
2246         int sjd = lc;
2247         int sjo = lc;
2248         int si;
2249         int li = 0, lic = 0;
2250         int lj = 0, ljc = 0;
2251         int lk = 0, lkc = 0;
2252         int i;
2253
2254         /* Find the side that most evenly splits the given lumps. */
2255
2256         for (si = 0; si < fp->sc; si++)
2257         {
2258             int o = 0;
2259             int d = 0;
2260             int k = 0;
2261
2262             for (li = 0; li < lc; li++)
2263                 if ((k = test_lump_side(fp,
2264                                         fp->lv + l0 + li,
2265                                         fp->sv + si,
2266                                         bsphere[l0 + li])))
2267                     d += k;
2268                 else
2269                     o++;
2270
2271             d = abs(d);
2272
2273             if ((d < sjd) || (d == sjd && o < sjo))
2274             {
2275                 sj  = si;
2276                 sjd = d;
2277                 sjo = o;
2278             }
2279         }
2280
2281         /* Flag each lump with its position WRT the side. */
2282
2283         for (li = 0; li < lc; li++)
2284             if (debug_output)
2285             {
2286                 fp->lv[l0+li].fl = (fp->lv[l0+li].fl & 1) | 0x20;
2287             }
2288             else
2289             {
2290                 switch (test_lump_side(fp,
2291                                        fp->lv + l0 + li,
2292                                        fp->sv + sj,
2293                                        bsphere[l0 + li]))
2294                 {
2295                 case +1:
2296                     fp->lv[l0+li].fl = (fp->lv[l0+li].fl & 1) | 0x10;
2297                     break;
2298
2299                 case  0:
2300                     fp->lv[l0+li].fl = (fp->lv[l0+li].fl & 1) | 0x20;
2301                     break;
2302
2303                 case -1:
2304                     fp->lv[l0+li].fl = (fp->lv[l0+li].fl & 1) | 0x40;
2305                     break;
2306                 }
2307             }
2308
2309         /* Sort all lumps in the range by their flag values. */
2310
2311         for (li = 1; li < lc; li++)
2312             for (lj = 0; lj < li; lj++)
2313                 if (fp->lv[l0 + li].fl < fp->lv[l0 + lj].fl)
2314                 {
2315                     struct s_lump l;
2316                     float f;
2317                     int i;
2318
2319                     for (i = 0; i < 4; i++)
2320                     {
2321                         f                   = bsphere[l0 + li][i];
2322                         bsphere[l0 + li][i] = bsphere[l0 + lj][i];
2323                         bsphere[l0 + lj][i] =                   f;
2324                     }
2325
2326                     l               = fp->lv[l0 + li];
2327                     fp->lv[l0 + li] = fp->lv[l0 + lj];
2328                     fp->lv[l0 + lj] =               l;
2329                 }
2330
2331         /* Establish the in-front, on, and behind lump ranges. */
2332
2333         li = lic = 0;
2334         lj = ljc = 0;
2335         lk = lkc = 0;
2336
2337         for (i = lc - 1; i >= 0; i--)
2338             switch (fp->lv[l0 + i].fl & 0xf0)
2339             {
2340             case 0x10: li = l0 + i; lic++; break;
2341             case 0x20: lj = l0 + i; ljc++; break;
2342             case 0x40: lk = l0 + i; lkc++; break;
2343             }
2344
2345         /* Add the lumps on the side to the node. */
2346
2347         i = incn(fp);
2348
2349         fp->nv[i].si = sj;
2350         fp->nv[i].ni = node_node(fp, li, lic, bsphere);
2351
2352         fp->nv[i].nj = node_node(fp, lk, lkc, bsphere);
2353         fp->nv[i].l0 = lj;
2354         fp->nv[i].lc = ljc;
2355
2356         return i;
2357     }
2358 }
2359
2360 /*
2361  * Compute a bounding sphere for a lump (not optimal)
2362  */
2363 static void lump_bounding_sphere(struct s_file *fp,
2364                                  struct s_lump *lp,
2365                                  float bsphere[4])
2366 {
2367     float bbox[6];
2368     float r;
2369     int i;
2370
2371     if (!lp->vc)
2372         return;
2373
2374     bbox[0] = bbox[3] = fp->vv[fp->iv[lp->v0]].p[0];
2375     bbox[1] = bbox[4] = fp->vv[fp->iv[lp->v0]].p[1];
2376     bbox[2] = bbox[5] = fp->vv[fp->iv[lp->v0]].p[2];
2377
2378     for (i = 1; i < lp->vc; i++)
2379     {
2380         struct s_vert *vp = fp->vv + fp->iv[lp->v0 + i];
2381         int j;
2382
2383         for (j = 0; j < 3; j++)
2384             if (vp->p[j] < bbox[j])
2385                 bbox[j] = vp->p[j];
2386
2387         for (j = 0; j < 3; j++)
2388             if (vp->p[j] > bbox[j + 3])
2389                 bbox[j + 3] = vp->p[j];
2390     }
2391
2392     r = 0;
2393
2394     for (i = 0; i < 3; i++)
2395     {
2396         bsphere[i] = (bbox[i] + bbox[i + 3]) / 2;
2397         r += (bsphere[i] - bbox[i]) * (bsphere[i] - bbox[i]);
2398     }
2399
2400     bsphere[3] = fsqrtf(r);
2401 }
2402
2403 static void node_file(struct s_file *fp)
2404 {
2405     float bsphere[MAXL][4];
2406     int i;
2407
2408     /* Compute a bounding sphere for each lump. */
2409
2410     for (i = 0; i < fp->lc; i++)
2411         lump_bounding_sphere(fp, fp->lv + i, bsphere[i]);
2412
2413     /* Sort the lumps of each body into BSP nodes. */
2414
2415     for (i = 0; i < fp->bc; i++)
2416         fp->bv[i].ni = node_node(fp, fp->bv[i].l0, fp->bv[i].lc, bsphere);
2417 }
2418
2419 /*---------------------------------------------------------------------------*/
2420
2421 static void dump_file(struct s_file *p, const char *name)
2422 {
2423     int i, j;
2424     int c = 0;
2425     int n = 0;
2426     int m;
2427
2428     /* Count the number of solid lumps. */
2429
2430     for (i = 0; i < p->lc; i++)
2431         if ((p->lv[i].fl & 1) == 0)
2432             n++;
2433
2434     /* Count the number of visible geoms. */
2435
2436     m = p->rc + (p->zc + p->jc + p->xc) * 32;
2437
2438     for (i = 0; i < p->hc; i++)
2439         if (p->hv[i].t == ITEM_COIN)
2440             m += 124;
2441         else
2442             m += 304;
2443
2444     for (i = 0; i < p->bc; i++)
2445     {
2446         for (j = 0; j < p->bv[i].lc; j++)
2447             m += p->lv[p->bv[i].l0 + j].gc;
2448         m += p->bv[i].gc;
2449     }
2450
2451     /* Count the total value of all coins. */
2452
2453     for (i = 0; i < p->hc; i++)
2454         if (p->hv[i].t == ITEM_COIN)
2455             c += p->hv[i].n;
2456
2457     printf("%s (%d/%d/$%d)\n"
2458            "  mtrl  vert  edge  side  texc"
2459            "  geom  lump  path  node  body\n"
2460            "%6d%6d%6d%6d%6d%6d%6d%6d%6d%6d\n"
2461            "  item  goal  view  jump  swch"
2462            "  bill  ball  char  dict  indx\n"
2463            "%6d%6d%6d%6d%6d%6d%6d%6d%6d%6d\n",
2464            name, n, m, c,
2465            p->mc, p->vc, p->ec, p->sc, p->tc,
2466            p->gc, p->lc, p->pc, p->nc, p->bc,
2467            p->hc, p->zc, p->wc, p->jc, p->xc,
2468            p->rc, p->uc, p->ac, p->dc, p->ic);
2469 }
2470
2471 int main(int argc, char *argv[])
2472 {
2473     char src[MAXSTR] = "";
2474     char dst[MAXSTR] = "";
2475     struct s_file f;
2476     fs_file fin;
2477
2478     if (!fs_init(argv[0]))
2479     {
2480         fprintf(stderr, "Failure to initialize virtual file system: %s\n",
2481                 fs_error());
2482         return 1;
2483     }
2484
2485     if (argc > 2)
2486     {
2487         input_file = argv[1];
2488
2489         if (argc > 3 && strcmp(argv[3], "--debug") == 0)
2490             debug_output = 1;
2491
2492         strncpy(src, argv[1], MAXSTR - 1);
2493         strncpy(dst, argv[1], MAXSTR - 1);
2494
2495         if (strcmp(dst + strlen(dst) - 4, ".map") == 0)
2496             strcpy(dst + strlen(dst) - 4, ".sol");
2497         else
2498             strcat(dst, ".sol");
2499
2500         fs_add_path     (dir_name(src));
2501         fs_set_write_dir(dir_name(dst));
2502
2503         if ((fin = fs_open(base_name(src, NULL), "r")))
2504         {
2505             if (!fs_add_path_with_archives(argv[2]))
2506             {
2507                 fprintf(stderr, "Failure to establish data directory\n");
2508                 fs_close(fin);
2509                 fs_quit();
2510                 return 1;
2511             }
2512
2513             init_file(&f);
2514             read_map(&f, fin);
2515
2516             resolve();
2517             targets(&f);
2518
2519             clip_file(&f);
2520             move_file(&f);
2521             uniq_file(&f);
2522             smth_file(&f);
2523             sort_file(&f);
2524             node_file(&f);
2525             dump_file(&f, dst);
2526
2527             sol_stor(&f, base_name(dst, NULL));
2528
2529             fs_close(fin);
2530
2531             free_imagedata();
2532         }
2533     }
2534     else fprintf(stderr, "Usage: %s <map> <data> [--debug]\n", argv[0]);
2535
2536     return 0;
2537 }
2538