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 }
 844
 845 static void make_dict(struct s_file *fp,
 846                       const char *k,
 847                       const char *v)
 848 {
 849     int space_left, space_needed, di = incd(fp);
 850
 851     struct s_dict *dp = fp->dv + di;
 852
 853     space_left   = MAXA - fp->ac;
 854     space_needed = strlen(k) + 1 + strlen(v) + 1;
 855
 856     if (space_needed > space_left)
 857     {
 858         fp->dc--;
 859         return;
 860     }
 861
 862     dp->ai = fp->ac;
 863     dp->aj = dp->ai + strlen(k) + 1;
 864     fp->ac = dp->aj + strlen(v) + 1;
 865
 866     strncpy(fp->av + dp->ai, k, space_left);
 867     strncpy(fp->av + dp->aj, v, space_left - strlen(k) - 1);
 868 }
 869
 870 static int read_dict_entries = 0;
 871
 872 static void make_body(struct s_file *fp,
 873                       char k[][MAXSTR],
 874                       char v[][MAXSTR], int c, int l0)
 875 {
 876     int i, mi = 0, bi = incb(fp);
 877
 878     int g0 = fp->gc;
 879     int v0 = fp->vc;
 880
 881     float p[3];
 882
 883     float x = 0.f;
 884     float y = 0.f;
 885     float z = 0.f;
 886
 887     struct s_body *bp = fp->bv + bi;
 888
 889     bp->t  = 0.f;
 890     bp->pi = -1;
 891     bp->ni = -1;
 892
 893     for (i = 0; i < c; i++)
 894     {
 895         if (strcmp(k[i], "targetname") == 0)
 896             make_sym(v[i], bi);
 897
 898         else if (strcmp(k[i], "target") == 0)
 899             make_ref(v[i], &bp->pi);
 900
 901         else if (strcmp(k[i], "material") == 0)
 902             mi = read_mtrl(fp, v[i]);
 903
 904         else if (strcmp(k[i], "model") == 0)
 905             read_obj(fp, v[i], mi);
 906
 907         else if (strcmp(k[i], "origin") == 0)
 908             sscanf(v[i], "%f %f %f", &x, &y, &z);
 909
 910         else if (read_dict_entries && strcmp(k[i], "classname") != 0)
 911             make_dict(fp, k[i], v[i]);
 912     }
 913
 914     bp->l0 = l0;
 915     bp->lc = fp->lc - l0;
 916     bp->g0 = fp->ic;
 917     bp->gc = fp->gc - g0;
 918
 919     for (i = 0; i < bp->gc; i++)
 920         fp->iv[inci(fp)] = g0++;
 921
 922     p[0] = +x / SCALE;
 923     p[1] = +z / SCALE;
 924     p[2] = -y / SCALE;
 925
 926     for (i = v0; i < fp->vc; i++)
 927         v_add(fp->vv[i].p, fp->vv[i].p, p);
 928
 929     read_dict_entries = 0;
 930 }
 931
 932 static void make_item(struct s_file *fp,
 933                       char k[][MAXSTR],
 934                       char v[][MAXSTR], int c)
 935 {
 936     int i, hi = inch(fp);
 937
 938     struct s_item *hp = fp->hv + hi;
 939
 940     hp->p[0] = 0.f;
 941     hp->p[1] = 0.f;
 942     hp->p[2] = 0.f;
 943
 944     hp->t = ITEM_NONE;
 945     hp->n = 0;
 946
 947     for (i = 0; i < c; i++)
 948     {
 949         if (strcmp(k[i], "classname") == 0)
 950         {
 951             if (strcmp(v[i], "light") == 0)
 952                 hp->t = ITEM_COIN;
 953             else if (strcmp(v[i], "item_health_large") == 0)
 954                 hp->t = ITEM_GROW;
 955             else if (strcmp(v[i], "item_health_small") == 0)
 956                 hp->t = ITEM_SHRINK;
 957         }
 958
 959         if (strcmp(k[i], "light") == 0)
 960             sscanf(v[i], "%d", &hp->n);
 961
 962         if (strcmp(k[i], "origin") == 0)
 963         {
 964             float x = 0.f, y = 0.f, z = 0.f;
 965
 966             sscanf(v[i], "%f %f %f", &x, &y, &z);
 967
 968             hp->p[0] = +x / SCALE;
 969             hp->p[1] = +z / SCALE;
 970             hp->p[2] = -y / SCALE;
 971         }
 972     }
 973 }
 974
 975 static void make_bill(struct s_file *fp,
 976                       char k[][MAXSTR],
 977                       char v[][MAXSTR], int c)
 978 {
 979     int i, ri = incr(fp);
 980
 981     struct s_bill *rp = fp->rv + ri;
 982
 983     memset(rp, 0, sizeof (struct s_bill));
 984     rp->t = 1.0f;
 985
 986     for (i = 0; i < c; i++)
 987     {
 988         if (strcmp(k[i], "width") == 0)
 989             sscanf(v[i], "%f %f %f", rp->w, rp->w + 1, rp->w + 2);
 990         if (strcmp(k[i], "height") == 0)
 991             sscanf(v[i], "%f %f %f", rp->h, rp->h + 1, rp->h + 2);
 992
 993         if (strcmp(k[i], "xrot") == 0)
 994             sscanf(v[i], "%f %f %f", rp->rx, rp->rx + 1, rp->rx + 2);
 995         if (strcmp(k[i], "yrot") == 0)
 996             sscanf(v[i], "%f %f %f", rp->ry, rp->ry + 1, rp->ry + 2);
 997         if (strcmp(k[i], "zrot") == 0)
 998             sscanf(v[i], "%f %f %f", rp->rz, rp->rz + 1, rp->rz + 2);
 999
1000         if (strcmp(k[i], "time") == 0)
1001             sscanf(v[i], "%f", &rp->t);
1002         if (strcmp(k[i], "dist") == 0)
1003             sscanf(v[i], "%f", &rp->d);
1004         if (strcmp(k[i], "flag") == 0)
1005             sscanf(v[i], "%d", &rp->fl);
1006
1007         if (strcmp(k[i], "image") == 0)
1008         {
1009             rp->mi = read_mtrl(fp, v[i]);
1010             fp->mv[rp->mi].fl |= M_CLAMPED;
1011         }
1012
1013         if (strcmp(k[i], "origin") == 0)
1014         {
1015             float x = 0.f, y = 0.f, z = 0.f;
1016
1017             sscanf(v[i], "%f %f %f", &x, &y, &z);
1018
1019             rp->p[0] = +x / SCALE;
1020             rp->p[1] = +z / SCALE;
1021             rp->p[2] = -y / SCALE;
1022         }
1023     }
1024
1025     if (rp->fl & B_ADDITIVE)
1026         fp->mv[rp->mi].fl |= M_ADDITIVE;
1027 }
1028
1029 static void make_goal(struct s_file *fp,
1030                       char k[][MAXSTR],
1031                       char v[][MAXSTR], int c)
1032 {
1033     int i, zi = incz(fp);
1034
1035     struct s_goal *zp = fp->zv + zi;
1036
1037     zp->p[0] = 0.f;
1038     zp->p[1] = 0.f;
1039     zp->p[2] = 0.f;
1040     zp->r    = 0.75;
1041
1042     for (i = 0; i < c; i++)
1043     {
1044         if (strcmp(k[i], "radius") == 0)
1045             sscanf(v[i], "%f", &zp->r);
1046
1047         if (strcmp(k[i], "origin") == 0)
1048         {
1049             float x = 0.f, y = 0.f, z = 0.f;
1050
1051             sscanf(v[i], "%f %f %f", &x, &y, &z);
1052
1053             zp->p[0] = +(x)      / SCALE;
1054             zp->p[1] = +(z - 24) / SCALE;
1055             zp->p[2] = -(y)      / SCALE;
1056         }
1057     }
1058 }
1059
1060 static void make_view(struct s_file *fp,
1061                       char k[][MAXSTR],
1062                       char v[][MAXSTR], int c)
1063 {
1064     int i, wi = incw(fp);
1065
1066     struct s_view *wp = fp->wv + wi;
1067
1068     wp->p[0] = 0.f;
1069     wp->p[1] = 0.f;
1070     wp->p[2] = 0.f;
1071     wp->q[0] = 0.f;
1072     wp->q[1] = 0.f;
1073     wp->q[2] = 0.f;
1074
1075     for (i = 0; i < c; i++)
1076     {
1077         if (strcmp(k[i], "target") == 0)
1078             make_ref(v[i], targ_wi + wi);
1079
1080         if (strcmp(k[i], "origin") == 0)
1081         {
1082             float x = 0.f, y = 0.f, z = 0.f;
1083
1084             sscanf(v[i], "%f %f %f", &x, &y, &z);
1085
1086             wp->p[0] = +x / SCALE;
1087             wp->p[1] = +z / SCALE;
1088             wp->p[2] = -y / SCALE;
1089         }
1090     }
1091 }
1092
1093 static void make_jump(struct s_file *fp,
1094                       char k[][MAXSTR],
1095                       char v[][MAXSTR], int c)
1096 {
1097     int i, ji = incj(fp);
1098
1099     struct s_jump *jp = fp->jv + ji;
1100
1101     jp->p[0] = 0.f;
1102     jp->p[1] = 0.f;
1103     jp->p[2] = 0.f;
1104     jp->q[0] = 0.f;
1105     jp->q[1] = 0.f;
1106     jp->q[2] = 0.f;
1107     jp->r    = 0.5;
1108
1109     for (i = 0; i < c; i++)
1110     {
1111         if (strcmp(k[i], "radius") == 0)
1112             sscanf(v[i], "%f", &jp->r);
1113
1114         if (strcmp(k[i], "target") == 0)
1115             make_ref(v[i], targ_ji + ji);
1116
1117         if (strcmp(k[i], "origin") == 0)
1118         {
1119             float x = 0.f, y = 0.f, z = 0.f;
1120
1121             sscanf(v[i], "%f %f %f", &x, &y, &z);
1122
1123             jp->p[0] = +x / SCALE;
1124             jp->p[1] = +z / SCALE;
1125             jp->p[2] = -y / SCALE;
1126         }
1127     }
1128 }
1129
1130 static void make_swch(struct s_file *fp,
1131                       char k[][MAXSTR],
1132                       char v[][MAXSTR], int c)
1133 {
1134     int i, xi = incx(fp);
1135
1136     struct s_swch *xp = fp->xv + xi;
1137
1138     xp->p[0] = 0.f;
1139     xp->p[1] = 0.f;
1140     xp->p[2] = 0.f;
1141     xp->r    = 0.5;
1142     xp->pi   = 0;
1143     xp->t0   = 0;
1144     xp->t    = 0;
1145     xp->f0   = 0;
1146     xp->f    = 0;
1147     xp->i    = 0;
1148
1149     for (i = 0; i < c; i++)
1150     {
1151         if (strcmp(k[i], "radius") == 0)
1152             sscanf(v[i], "%f", &xp->r);
1153
1154         if (strcmp(k[i], "target") == 0)
1155             make_ref(v[i], &xp->pi);
1156
1157         if (strcmp(k[i], "timer") == 0)
1158         {
1159             sscanf(v[i], "%f", &xp->t0);
1160             xp->t = xp->t0;
1161         }
1162
1163         if (strcmp(k[i], "state") == 0)
1164         {
1165             xp->f  = atoi(v[i]);
1166             xp->f0 = atoi(v[i]);
1167         }
1168
1169         if (strcmp(k[i], "invisible") == 0)
1170             xp->i = atoi(v[i]);
1171
1172         if (strcmp(k[i], "origin") == 0)
1173         {
1174             float x = 0.f, y = 0.f, z = 0.f;
1175
1176             sscanf(v[i], "%f %f %f", &x, &y, &z);
1177
1178             xp->p[0] = +x / SCALE;
1179             xp->p[1] = +z / SCALE;
1180             xp->p[2] = -y / SCALE;
1181         }
1182     }
1183 }
1184
1185 static void make_targ(struct s_file *fp,
1186                       char k[][MAXSTR],
1187                       char v[][MAXSTR], int c)
1188 {
1189     int i;
1190
1191     targ_p[targ_n][0] = 0.f;
1192     targ_p[targ_n][1] = 0.f;
1193     targ_p[targ_n][2] = 0.f;
1194
1195     for (i = 0; i < c; i++)
1196     {
1197         if (strcmp(k[i], "targetname") == 0)
1198             make_sym(v[i], targ_n);
1199
1200         if (strcmp(k[i], "origin") == 0)
1201         {
1202             float x = 0.f, y = 0.f, z = 0.f;
1203
1204             sscanf(v[i], "%f %f %f", &x, &y, &z);
1205
1206             targ_p[targ_n][0] = +x / SCALE;
1207             targ_p[targ_n][1] = +z / SCALE;
1208             targ_p[targ_n][2] = -y / SCALE;
1209         }
1210     }
1211
1212     targ_n++;
1213 }
1214
1215 static void make_ball(struct s_file *fp,
1216                       char k[][MAXSTR],
1217                       char v[][MAXSTR], int c)
1218 {
1219     int i, ui = incu(fp);
1220
1221     struct s_ball *up = fp->uv + ui;
1222
1223     up->p[0] = 0.0f;
1224     up->p[1] = 0.0f;
1225     up->p[2] = 0.0f;
1226     up->r    = 0.25f;
1227
1228     for (i = 0; i < c; i++)
1229     {
1230         if (strcmp(k[i], "radius") == 0)
1231             sscanf(v[i], "%f", &up->r);
1232
1233         if (strcmp(k[i], "origin") == 0)
1234         {
1235             float x = 0.f, y = 0.f, z = 0.f;
1236
1237             sscanf(v[i], "%f %f %f", &x, &y, &z);
1238
1239             up->p[0] = +(x)      / SCALE;
1240             up->p[1] = +(z - 24) / SCALE;
1241             up->p[2] = -(y)      / SCALE;
1242         }
1243     }
1244
1245     up->p[1] += up->r + SMALL;
1246 }
1247
1248 /*---------------------------------------------------------------------------*/
1249
1250 static void read_ent(struct s_file *fp, fs_file fin)
1251 {
1252     char k[MAXKEY][MAXSTR];
1253     char v[MAXKEY][MAXSTR];
1254     int t, i = 0, c = 0;
1255
1256     int l0 = fp->lc;
1257
1258     while ((t = map_token(fin, -1, k[c], v[c])))
1259     {
1260         if (t == T_KEY)
1261         {
1262             if (strcmp(k[c], "classname") == 0)
1263                 i = c;
1264             c++;
1265         }
1266         if (t == T_BEG) read_lump(fp, fin);
1267         if (t == T_END) break;
1268     }
1269
1270     if (!strcmp(v[i], "light"))                    make_item(fp, k, v, c);
1271     if (!strcmp(v[i], "item_health_large"))        make_item(fp, k, v, c);
1272     if (!strcmp(v[i], "item_health_small"))        make_item(fp, k, v, c);
1273     if (!strcmp(v[i], "info_camp"))                make_swch(fp, k, v, c);
1274     if (!strcmp(v[i], "info_null"))                make_bill(fp, k, v, c);
1275     if (!strcmp(v[i], "path_corner"))              make_path(fp, k, v, c);
1276     if (!strcmp(v[i], "info_player_start"))        make_ball(fp, k, v, c);
1277     if (!strcmp(v[i], "info_player_intermission")) make_view(fp, k, v, c);
1278     if (!strcmp(v[i], "info_player_deathmatch"))   make_goal(fp, k, v, c);
1279     if (!strcmp(v[i], "target_teleporter"))        make_jump(fp, k, v, c);
1280     if (!strcmp(v[i], "target_position"))          make_targ(fp, k, v, c);
1281     if (!strcmp(v[i], "worldspawn"))
1282     {
1283         read_dict_entries = 1;
1284         make_body(fp, k, v, c, l0);
1285     }
1286     if (!strcmp(v[i], "func_train"))               make_body(fp, k, v, c, l0);
1287     if (!strcmp(v[i], "misc_model"))               make_body(fp, k, v, c, l0);
1288 }
1289
1290 static void read_map(struct s_file *fp, fs_file fin)
1291 {
1292     char k[MAXSTR];
1293     char v[MAXSTR];
1294     int t;
1295
1296     while ((t = map_token(fin, -1, k, v)))
1297         if (t == T_BEG)
1298             read_ent(fp, fin);
1299 }
1300
1301 /*---------------------------------------------------------------------------*/
1302
1303 /* Test the location of a point with respect to a side plane. */
1304
1305 static int fore_side(const float p[3], const struct s_side *sp)
1306 {
1307     return (v_dot(p, sp->n) - sp->d > +SMALL) ? 1 : 0;
1308 }
1309
1310 static int on_side(const float p[3], const struct s_side *sp)
1311 {
1312     float d = v_dot(p, sp->n) - sp->d;
1313
1314     return (-SMALL < d && d < +SMALL) ? 1 : 0;
1315 }
1316
1317 /*---------------------------------------------------------------------------*/
1318 /*
1319  * Confirm  that  the addition  of  a vert  would  not  result in  degenerate
1320  * geometry.
1321  */
1322
1323 static int ok_vert(const struct s_file *fp,
1324                    const struct s_lump *lp, const float p[3])
1325 {
1326     float r[3];
1327     int i;
1328
1329     for (i = 0; i < lp->vc; i++)
1330     {
1331         float *q = fp->vv[fp->iv[lp->v0 + i]].p;
1332
1333         v_sub(r, p, q);
1334
1335         if (v_len(r) < SMALL)
1336             return 0;
1337     }
1338     return 1;
1339 }
1340
1341 /*---------------------------------------------------------------------------*/
1342
1343 /*
1344  * The following functions take the  set of planes defining a lump and
1345  * find the verts, edges, and  geoms that describe its boundaries.  To
1346  * do this, they first find the verts, and then search these verts for
1347  * valid edges and  geoms.  It may be more  efficient to compute edges
1348  * and  geoms directly  by clipping  down infinite  line  segments and
1349  * planes,  but this  would be  more  complex and  prone to  numerical
1350  * error.
1351  */
1352
1353 /*
1354  * Given 3  side planes,  compute the point  of intersection,  if any.
1355  * Confirm that this point falls  within the current lump, and that it
1356  * is unique.  Add it as a vert of the solid.
1357  */
1358 static void clip_vert(struct s_file *fp,
1359                       struct s_lump *lp, int si, int sj, int sk)
1360 {
1361     float M[16], X[16], I[16];
1362     float d[3],  p[3];
1363     int i;
1364
1365     d[0] = fp->sv[si].d;
1366     d[1] = fp->sv[sj].d;
1367     d[2] = fp->sv[sk].d;
1368
1369     m_basis(M, fp->sv[si].n, fp->sv[sj].n, fp->sv[sk].n);
1370     m_xps(X, M);
1371
1372     if (m_inv(I, X))
1373     {
1374         m_vxfm(p, I, d);
1375
1376         for (i = 0; i < lp->sc; i++)
1377         {
1378             int si = fp->iv[lp->s0 + i];
1379
1380             if (fore_side(p, fp->sv + si))
1381                 return;
1382         }
1383
1384         if (ok_vert(fp, lp, p))
1385         {
1386             v_cpy(fp->vv[fp->vc].p, p);
1387
1388             fp->iv[fp->ic] = fp->vc;
1389             inci(fp);
1390             incv(fp);
1391             lp->vc++;
1392         }
1393     }
1394 }
1395
1396 /*
1397  * Given two  side planes,  find an edge  along their  intersection by
1398  * finding a pair of vertices that fall on both planes.  Add it to the
1399  * solid.
1400  */
1401 static void clip_edge(struct s_file *fp,
1402                       struct s_lump *lp, int si, int sj)
1403 {
1404     int i, j;
1405
1406     for (i = 1; i < lp->vc; i++)
1407     {
1408         int vi = fp->iv[lp->v0 + i];
1409
1410         if (!on_side(fp->vv[vi].p, fp->sv + si) ||
1411             !on_side(fp->vv[vi].p, fp->sv + sj))
1412             continue;
1413
1414         for (j = 0; j < i; j++)
1415         {
1416             int vj = fp->iv[lp->v0 + j];
1417
1418             if (on_side(fp->vv[vj].p, fp->sv + si) &&
1419                 on_side(fp->vv[vj].p, fp->sv + sj))
1420             {
1421                 fp->ev[fp->ec].vi = vi;
1422                 fp->ev[fp->ec].vj = vj;
1423
1424                 fp->iv[fp->ic] = fp->ec;
1425
1426                 inci(fp);
1427                 ince(fp);
1428                 lp->ec++;
1429             }
1430         }
1431     }
1432 }
1433
1434 /*
1435  * Find all verts that lie on  the given side of the lump.  Sort these
1436  * verts to  have a counter-clockwise winding about  the plane normal.
1437  * Create geoms to tessellate the resulting convex polygon.
1438  */
1439 static void clip_geom(struct s_file *fp,
1440                       struct s_lump *lp, int si)
1441 {
1442     int   m[256], t[256], d, i, j, n = 0;
1443     float u[3];
1444     float v[3];
1445     float w[3];
1446
1447     struct s_side *sp = fp->sv + si;
1448
1449     /* Find em. */
1450
1451     for (i = 0; i < lp->vc; i++)
1452     {
1453         int vi = fp->iv[lp->v0 + i];
1454
1455         if (on_side(fp->vv[vi].p, sp))
1456         {
1457             m[n] = vi;
1458             t[n] = inct(fp);
1459
1460             v_add(v, fp->vv[vi].p, plane_p[si]);
1461
1462             fp->tv[t[n]].u[0] = v_dot(v, plane_u[si]);
1463             fp->tv[t[n]].u[1] = v_dot(v, plane_v[si]);
1464
1465             n++;
1466         }
1467     }
1468
1469     /* Sort em. */
1470
1471     for (i = 1; i < n; i++)
1472         for (j = i + 1; j < n; j++)
1473         {
1474             v_sub(u, fp->vv[m[i]].p, fp->vv[m[0]].p);
1475             v_sub(v, fp->vv[m[j]].p, fp->vv[m[0]].p);
1476             v_crs(w, u, v);
1477
1478             if (v_dot(w, sp->n) < 0.f)
1479             {
1480                 d     = m[i];
1481                 m[i]  = m[j];
1482                 m[j]  =    d;
1483
1484                 d     = t[i];
1485                 t[i]  = t[j];
1486                 t[j]  =    d;
1487             }
1488         }
1489
1490     /* Index em. */
1491
1492     for (i = 0; i < n - 2; i++)
1493     {
1494         fp->gv[fp->gc].mi = plane_m[si];
1495
1496         fp->gv[fp->gc].ti = t[0];
1497         fp->gv[fp->gc].tj = t[i + 1];
1498         fp->gv[fp->gc].tk = t[i + 2];
1499
1500         fp->gv[fp->gc].si = si;
1501         fp->gv[fp->gc].sj = si;
1502         fp->gv[fp->gc].sk = si;
1503
1504         fp->gv[fp->gc].vi = m[0];
1505         fp->gv[fp->gc].vj = m[i + 1];
1506         fp->gv[fp->gc].vk = m[i + 2];
1507
1508         fp->iv[fp->ic] = fp->gc;
1509         inci(fp);
1510         incg(fp);
1511         lp->gc++;
1512     }
1513 }
1514
1515 /*
1516  * Iterate the sides of the lump, attempting to generate a new vert for
1517  * each trio of planes, a new edge  for each pair of planes, and a new
1518  * set of geom for each visible plane.
1519  */
1520 static void clip_lump(struct s_file *fp, struct s_lump *lp)
1521 {
1522     int i, j, k;
1523
1524     lp->v0 = fp->ic;
1525     lp->vc = 0;
1526
1527     for (i = 2; i < lp->sc; i++)
1528         for (j = 1; j < i; j++)
1529             for (k = 0; k < j; k++)
1530                 clip_vert(fp, lp,
1531                           fp->iv[lp->s0 + i],
1532                           fp->iv[lp->s0 + j],
1533                           fp->iv[lp->s0 + k]);
1534
1535     lp->e0 = fp->ic;
1536     lp->ec = 0;
1537
1538     for (i = 1; i < lp->sc; i++)
1539         for (j = 0; j < i; j++)
1540             clip_edge(fp, lp,
1541                       fp->iv[lp->s0 + i],
1542                       fp->iv[lp->s0 + j]);
1543
1544     lp->g0 = fp->ic;
1545     lp->gc = 0;
1546
1547     for (i = 0; i < lp->sc; i++)
1548         if (fp->mv[plane_m[fp->iv[lp->s0 + i]]].d[3] > 0.0f)
1549             clip_geom(fp, lp,
1550                       fp->iv[lp->s0 + i]);
1551
1552     for (i = 0; i < lp->sc; i++)
1553         if (plane_f[fp->iv[lp->s0 + i]])
1554             lp->fl |= L_DETAIL;
1555 }
1556
1557 static void clip_file(struct s_file *fp)
1558 {
1559     int i;
1560
1561     for (i = 0; i < fp->lc; i++)
1562         clip_lump(fp, fp->lv + i);
1563 }
1564
1565 /*---------------------------------------------------------------------------*/
1566
1567 /*
1568  * For each body element type,  determine if element 'p' is equivalent
1569  * to element  'q'.  This  is more than  a simple memory  compare.  It
1570  * effectively  snaps mtrls and  verts together,  and may  reverse the
1571  * winding of  an edge or a geom.   This is done in  order to maximize
1572  * the number of elements that can be eliminated.
1573  */
1574
1575 static int comp_mtrl(const struct s_mtrl *mp, const struct s_mtrl *mq)
1576 {
1577     if (fabs(mp->d[0] - mq->d[0]) > SMALL) return 0;
1578     if (fabs(mp->d[1] - mq->d[1]) > SMALL) return 0;
1579     if (fabs(mp->d[2] - mq->d[2]) > SMALL) return 0;
1580     if (fabs(mp->d[3] - mq->d[3]) > SMALL) return 0;
1581
1582     if (fabs(mp->a[0] - mq->a[0]) > SMALL) return 0;
1583     if (fabs(mp->a[1] - mq->a[1]) > SMALL) return 0;
1584     if (fabs(mp->a[2] - mq->a[2]) > SMALL) return 0;
1585     if (fabs(mp->a[3] - mq->a[3]) > SMALL) return 0;
1586
1587     if (fabs(mp->s[0] - mq->s[0]) > SMALL) return 0;
1588     if (fabs(mp->s[1] - mq->s[1]) > SMALL) return 0;
1589     if (fabs(mp->s[2] - mq->s[2]) > SMALL) return 0;
1590     if (fabs(mp->s[3] - mq->s[3]) > SMALL) return 0;
1591
1592     if (fabs(mp->e[0] - mq->e[0]) > SMALL) return 0;
1593     if (fabs(mp->e[1] - mq->e[1]) > SMALL) return 0;
1594     if (fabs(mp->e[2] - mq->e[2]) > SMALL) return 0;
1595     if (fabs(mp->e[3] - mq->e[3]) > SMALL) return 0;
1596
1597     if (fabs(mp->h[0] - mq->h[0]) > SMALL) return 0;
1598
1599     if (strncmp(mp->f, mq->f, PATHMAX)) return 0;
1600
1601     return 1;
1602 }
1603
1604 static int comp_vert(const struct s_vert *vp, const struct s_vert *vq)
1605 {
1606     if (fabs(vp->p[0] - vq->p[0]) > SMALL) return 0;
1607     if (fabs(vp->p[1] - vq->p[1]) > SMALL) return 0;
1608     if (fabs(vp->p[2] - vq->p[2]) > SMALL) return 0;
1609
1610     return 1;
1611 }
1612
1613 static int comp_edge(const struct s_edge *ep, const struct s_edge *eq)
1614 {
1615     if (ep->vi != eq->vi && ep->vi != eq->vj) return 0;
1616     if (ep->vj != eq->vi && ep->vj != eq->vj) return 0;
1617
1618     return 1;
1619 }
1620
1621 static int comp_side(const struct s_side *sp, const struct s_side *sq)
1622 {
1623     if  (fabs(sp->d - sq->d) > SMALL)  return 0;
1624     if (v_dot(sp->n,  sq->n) < 0.9999) return 0;
1625
1626     return 1;
1627 }
1628
1629 static int comp_texc(const struct s_texc *tp, const struct s_texc *tq)
1630 {
1631     if (fabs(tp->u[0] - tq->u[0]) > SMALL) return 0;
1632     if (fabs(tp->u[1] - tq->u[1]) > SMALL) return 0;
1633
1634     return 1;
1635 }
1636
1637 static int comp_geom(const struct s_geom *gp, const struct s_geom *gq)
1638 {
1639     if (gp->mi != gq->mi) return 0;
1640
1641     if (gp->ti != gq->ti) return 0;
1642     if (gp->si != gq->si) return 0;
1643     if (gp->vi != gq->vi) return 0;
1644
1645     if (gp->tj != gq->tj) return 0;
1646     if (gp->sj != gq->sj) return 0;
1647     if (gp->vj != gq->vj) return 0;
1648
1649     if (gp->tk != gq->tk) return 0;
1650     if (gp->sk != gq->sk) return 0;
1651     if (gp->vk != gq->vk) return 0;
1652
1653     return 1;
1654 }
1655
1656 /*---------------------------------------------------------------------------*/
1657
1658 /*
1659  * For each file  element type, replace all references  to element 'i'
1660  * with a  reference to element  'j'.  These are used  when optimizing
1661  * and sorting the file.
1662  */
1663
1664 static void swap_mtrl(struct s_file *fp, int mi, int mj)
1665 {
1666     int i;
1667
1668     for (i = 0; i < fp->gc; i++)
1669         if (fp->gv[i].mi == mi) fp->gv[i].mi = mj;
1670     for (i = 0; i < fp->rc; i++)
1671         if (fp->rv[i].mi == mi) fp->rv[i].mi = mj;
1672 }
1673
1674 static int vert_swaps[MAXV];
1675
1676 static void apply_vert_swaps(struct s_file *fp)
1677 {
1678     int i, j;
1679
1680     for (i = 0; i < fp->ec; i++)
1681     {
1682         fp->ev[i].vi = vert_swaps[fp->ev[i].vi];
1683         fp->ev[i].vj = vert_swaps[fp->ev[i].vj];
1684     }
1685
1686     for (i = 0; i < fp->gc; i++)
1687     {
1688         fp->gv[i].vi = vert_swaps[fp->gv[i].vi];
1689         fp->gv[i].vj = vert_swaps[fp->gv[i].vj];
1690         fp->gv[i].vk = vert_swaps[fp->gv[i].vk];
1691     }
1692
1693     for (i = 0; i < fp->lc; i++)
1694         for (j = 0; j < fp->lv[i].vc; j++)
1695             fp->iv[fp->lv[i].v0 + j] = vert_swaps[fp->iv[fp->lv[i].v0 + j]];
1696 }
1697
1698 static void swap_vert(struct s_file *fp, int vi, int vj)
1699 {
1700     int i, j;
1701
1702     for (i = 0; i < fp->ec; i++)
1703     {
1704         if (fp->ev[i].vi == vi) fp->ev[i].vi = vj;
1705         if (fp->ev[i].vj == vi) fp->ev[i].vj = vj;
1706     }
1707
1708     for (i = 0; i < fp->gc; i++)
1709     {
1710         if (fp->gv[i].vi == vi) fp->gv[i].vi = vj;
1711         if (fp->gv[i].vj == vi) fp->gv[i].vj = vj;
1712         if (fp->gv[i].vk == vi) fp->gv[i].vk = vj;
1713     }
1714
1715     for (i = 0; i < fp->lc; i++)
1716         for (j = 0; j < fp->lv[i].vc; j++)
1717             if (fp->iv[fp->lv[i].v0 + j] == vi)
1718                 fp->iv[fp->lv[i].v0 + j]  = vj;
1719 }
1720
1721 static int edge_swaps[MAXE];
1722
1723 static void apply_edge_swaps(struct s_file *fp)
1724 {
1725     int i, j;
1726
1727     for (i = 0; i < fp->lc; i++)
1728         for (j = 0; j < fp->lv[i].ec; j++)
1729             fp->iv[fp->lv[i].e0 + j] = edge_swaps[fp->iv[fp->lv[i].e0 + j]];
1730 }
1731
1732 static int side_swaps[MAXS];
1733
1734 static void apply_side_swaps(struct s_file *fp)
1735 {
1736     int i, j;
1737
1738     for (i = 0; i < fp->gc; i++)
1739     {
1740         fp->gv[i].si = side_swaps[fp->gv[i].si];
1741         fp->gv[i].sj = side_swaps[fp->gv[i].sj];
1742         fp->gv[i].sk = side_swaps[fp->gv[i].sk];
1743     }
1744     for (i = 0; i < fp->nc; i++)
1745         fp->nv[i].si = side_swaps[fp->nv[i].si];
1746
1747     for (i = 0; i < fp->lc; i++)
1748         for (j = 0; j < fp->lv[i].sc; j++)
1749             fp->iv[fp->lv[i].s0 + j] = side_swaps[fp->iv[fp->lv[i].s0 + j]];
1750 }
1751
1752 static int texc_swaps[MAXT];
1753
1754 static void apply_texc_swaps(struct s_file *fp)
1755 {
1756     int i;
1757
1758     for (i = 0; i < fp->gc; i++)
1759     {
1760         fp->gv[i].ti = texc_swaps[fp->gv[i].ti];
1761         fp->gv[i].tj = texc_swaps[fp->gv[i].tj];
1762         fp->gv[i].tk = texc_swaps[fp->gv[i].tk];
1763     }
1764 }
1765
1766 static int geom_swaps[MAXG];
1767
1768 static void apply_geom_swaps(struct s_file *fp)
1769 {
1770     int i, j;
1771
1772     for (i = 0; i < fp->lc; i++)
1773         for (j = 0; j < fp->lv[i].gc; j++)
1774             fp->iv[fp->lv[i].g0 + j] = geom_swaps[fp->iv[fp->lv[i].g0 + j]];
1775
1776     for (i = 0; i < fp->bc; i++)
1777         for (j = 0; j < fp->bv[i].gc; j++)
1778             fp->iv[fp->bv[i].g0 + j] = geom_swaps[fp->iv[fp->bv[i].g0 + j]];
1779 }
1780
1781 /*---------------------------------------------------------------------------*/
1782
1783 static void uniq_mtrl(struct s_file *fp)
1784 {
1785     int i, j, k = 0;
1786
1787     for (i = 0; i < fp->mc; i++)
1788     {
1789         for (j = 0; j < k; j++)
1790             if (comp_mtrl(fp->mv + i, fp->mv + j))
1791             {
1792                 swap_mtrl(fp, i, j);
1793                 break;
1794             }
1795
1796         if (j == k)
1797         {
1798             if (i != k)
1799             {
1800                 fp->mv[k] = fp->mv[i];
1801                 swap_mtrl(fp, i, k);
1802             }
1803             k++;
1804         }
1805     }
1806
1807     fp->mc = k;
1808 }
1809
1810 static void uniq_vert(struct s_file *fp)
1811 {
1812     int i, j, k = 0;
1813
1814     for (i = 0; i < fp->vc; i++)
1815     {
1816         for (j = 0; j < k; j++)
1817             if (comp_vert(fp->vv + i, fp->vv + j))
1818                 break;
1819
1820         vert_swaps[i] = j;
1821
1822         if (j == k)
1823         {
1824             if (i != k)
1825                 fp->vv[k] = fp->vv[i];
1826             k++;
1827         }
1828     }
1829
1830     apply_vert_swaps(fp);
1831
1832     fp->vc = k;
1833 }
1834
1835 static void uniq_edge(struct s_file *fp)
1836 {
1837     int i, j, k = 0;
1838
1839     for (i = 0; i < fp->ec; i++)
1840     {
1841         for (j = 0; j < k; j++)
1842             if (comp_edge(fp->ev + i, fp->ev + j))
1843                 break;
1844
1845         edge_swaps[i] = j;
1846
1847         if (j == k)
1848         {
1849             if (i != k)
1850                 fp->ev[k] = fp->ev[i];
1851             k++;
1852         }
1853     }
1854
1855     apply_edge_swaps(fp);
1856
1857     fp->ec = k;
1858 }
1859
1860 static int geomlist[MAXV];
1861 static int nextgeom[MAXG];
1862
1863 static void uniq_geom(struct s_file *fp)
1864 {
1865     int i, j, k = 0;
1866
1867     for (i = 0; i < MAXV; i++)
1868         geomlist[i] = -1;
1869
1870     for (i = 0; i < fp->gc; i++)
1871     {
1872         int key = fp->gv[i].vj;
1873
1874         for (j = geomlist[key]; j != -1; j = nextgeom[j])
1875             if (comp_geom(fp->gv + i, fp->gv + j))
1876                 goto found;
1877
1878         fp->gv[k] = fp->gv[i];
1879
1880         nextgeom[k] = geomlist[key];
1881         geomlist[key] = k;
1882
1883         j = k;
1884         k++;
1885
1886 found:
1887         geom_swaps[i] = j;
1888     }
1889
1890     apply_geom_swaps(fp);
1891
1892     fp->gc = k;
1893 }
1894
1895 static void uniq_texc(struct s_file *fp)
1896 {
1897     int i, j, k = 0;
1898
1899     for (i = 0; i < fp->tc; i++)
1900     {
1901         for (j = 0; j < k; j++)
1902             if (comp_texc(fp->tv + i, fp->tv + j))
1903                 break;
1904
1905         texc_swaps[i] = j;
1906
1907         if (j == k)
1908         {
1909             if (i != k)
1910                 fp->tv[k] = fp->tv[i];
1911             k++;
1912         }
1913     }
1914
1915     apply_texc_swaps(fp);
1916
1917     fp->tc = k;
1918 }
1919
1920 static void uniq_side(struct s_file *fp)
1921 {
1922     int i, j, k = 0;
1923
1924     for (i = 0; i < fp->sc; i++)
1925     {
1926         for (j = 0; j < k; j++)
1927             if (comp_side(fp->sv + i, fp->sv + j))
1928                 break;
1929
1930         side_swaps[i] = j;
1931
1932         if (j == k)
1933         {
1934             if (i != k)
1935                 fp->sv[k] = fp->sv[i];
1936             k++;
1937         }
1938     }
1939
1940     apply_side_swaps(fp);
1941
1942     fp->sc = k;
1943 }
1944
1945 static void uniq_file(struct s_file *fp)
1946 {
1947     /* Debug mode skips optimization, producing oversized output files. */
1948
1949     if (debug_output == 0)
1950     {
1951         uniq_mtrl(fp);
1952         uniq_vert(fp);
1953         uniq_edge(fp);
1954         uniq_side(fp);
1955         uniq_texc(fp);
1956         uniq_geom(fp);
1957     }
1958 }
1959
1960 /*---------------------------------------------------------------------------*/
1961
1962 struct s_trip
1963 {
1964     int vi;
1965     int mi;
1966     int si;
1967     int gi;
1968 };
1969
1970 static int comp_trip(const void *p, const void *q)
1971 {
1972     const struct s_trip *tp = (const struct s_trip *) p;
1973     const struct s_trip *tq = (const struct s_trip *) q;
1974
1975     if (tp->vi < tq->vi) return -1;
1976     if (tp->vi > tq->vi) return +1;
1977     if (tp->mi < tq->mi) return -1;
1978     if (tp->mi > tq->mi) return +1;
1979
1980     return 0;
1981 }
1982
1983 static void smth_file(struct s_file *fp)
1984 {
1985     struct s_trip temp, *T;
1986
1987     if (debug_output == 0)
1988     {
1989         if ((T = (struct s_trip *) malloc(fp->gc * 3 * sizeof (struct s_trip))))
1990         {
1991             int gi, i, j, k, l, c = 0;
1992
1993             /* Create a list of all non-faceted vertex triplets. */
1994
1995             for (gi = 0; gi < fp->gc; ++gi)
1996             {
1997                 struct s_geom *gp = fp->gv + gi;
1998
1999                 T[c].vi = gp->vi;
2000                 T[c].mi = gp->mi;
2001                 T[c].si = gp->si;
2002                 T[c].gi = gi;
2003                 c++;
2004
2005                 T[c].vi = gp->vj;
2006                 T[c].mi = gp->mi;
2007                 T[c].si = gp->sj;
2008                 T[c].gi = gi;
2009                 c++;
2010
2011                 T[c].vi = gp->vk;
2012                 T[c].mi = gp->mi;
2013                 T[c].si = gp->sk;
2014                 T[c].gi = gi;
2015                 c++;
2016             }
2017
2018             /* Sort all triplets by vertex index and material. */
2019
2020             qsort(T, c, sizeof (struct s_trip), comp_trip);
2021
2022             /* For each set of triplets sharing vertex index and material... */
2023
2024             for (i = 0; i < c; i = l)
2025             {
2026                 int acc = 0;
2027
2028                 float N[3], angle = fp->mv[T[i].mi].angle;
2029                 const float   *Ni = fp->sv[T[i].si].n;
2030
2031                 /* Sort the set by side similarity to the first. */
2032
2033                 for (j = i + 1; j < c && (T[j].vi == T[i].vi &&
2034                                           T[j].mi == T[i].mi); ++j)
2035                 {
2036                     for (k = j + 1; k < c && (T[k].vi == T[i].vi &&
2037                                               T[k].mi == T[i].mi); ++k)
2038                     {
2039                         const float *Nj = fp->sv[T[j].si].n;
2040                         const float *Nk = fp->sv[T[k].si].n;
2041
2042                         if (T[j].si != T[k].si && v_dot(Nk, Ni) > v_dot(Nj, Ni))
2043                         {
2044                             temp = T[k];
2045                             T[k] = T[j];
2046                             T[j] = temp;
2047                         }
2048                     }
2049                 }
2050
2051                 /* Accumulate all similar side normals. */
2052
2053                 N[0] = Ni[0];
2054                 N[1] = Ni[1];
2055                 N[2] = Ni[2];
2056
2057                 for (l = i + 1; l < c && (T[l].vi == T[i].vi &&
2058                                           T[l].mi == T[i].mi); ++l)
2059                     if (T[l].si != T[i].si)
2060                     {
2061                         const float *Nl = fp->sv[T[l].si].n;
2062
2063                         if (V_DEG(facosf(v_dot(Ni, Nl))) > angle)
2064                             break;
2065
2066                         N[0] += Nl[0];
2067                         N[1] += Nl[1];
2068                         N[2] += Nl[2];
2069
2070                         acc++;
2071                     }
2072
2073                 /* If at least two normals have been accumulated... */
2074
2075                 if (acc)
2076                 {
2077                     /* Store the accumulated normal as a new side. */
2078
2079                     int ss = incs(fp);
2080
2081                     v_nrm(fp->sv[ss].n, N);
2082                     fp->sv[ss].d = 0.0f;
2083
2084                     /* Assign the new normal to the merged triplets. */
2085
2086                     for (j = i; j < l; ++j)
2087                         T[j].si = ss;
2088                 }
2089             }
2090
2091             /* Assign the remapped normals to the original geoms. */
2092
2093             for (i = 0; i < c; ++i)
2094             {
2095                 struct s_geom *gp = fp->gv + T[i].gi;
2096
2097                 if (gp->vi == T[i].vi) gp->si = T[i].si;
2098                 if (gp->vj == T[i].vi) gp->sj = T[i].si;
2099                 if (gp->vk == T[i].vi) gp->sk = T[i].si;
2100             }
2101
2102             free(T);
2103         }
2104
2105         uniq_side(fp);
2106     }
2107 }
2108
2109
2110 /*---------------------------------------------------------------------------*/
2111
2112 static void sort_file(struct s_file *fp)
2113 {
2114     int i, j;
2115
2116     /* Sort billboards by material within distance. */
2117
2118     for (i = 0; i < fp->rc; i++)
2119         for (j = i + 1; j < fp->rc; j++)
2120             if ((fp->rv[j].d  > fp->rv[i].d) ||
2121                 (fp->rv[j].d == fp->rv[i].d &&
2122                  fp->rv[j].mi > fp->rv[i].mi))
2123             {
2124                 struct s_bill t;
2125
2126                 t         = fp->rv[i];
2127                 fp->rv[i] = fp->rv[j];
2128                 fp->rv[j] =         t;
2129             }
2130
2131     /* Ensure the first vertex is the lowest. */
2132
2133     for (i = 0; i < fp->vc; i++)
2134         if (fp->vv[0].p[1] > fp->vv[i].p[1])
2135         {
2136             struct s_vert t;
2137
2138             t         = fp->vv[0];
2139             fp->vv[0] = fp->vv[i];
2140             fp->vv[i] =         t;
2141
2142             swap_vert(fp,  0, -1);
2143             swap_vert(fp,  i,  0);
2144             swap_vert(fp, -1,  i);
2145         }
2146 }
2147
2148 /*---------------------------------------------------------------------------*/
2149
2150 static int test_lump_side(const struct s_file *fp,
2151                           const struct s_lump *lp,
2152                           const struct s_side *sp,
2153                           float bsphere[4])
2154 {
2155     int si;
2156     int vi;
2157
2158     int f = 0;
2159     int b = 0;
2160
2161     float d;
2162
2163     if (!lp->vc)
2164         return 0;
2165
2166     /* Check if the bounding sphere of the lump is completely on one side. */
2167
2168     d = v_dot(bsphere, sp->n) - sp->d;
2169
2170     if (fabs(d) > bsphere[3])
2171         return d > 0 ? 1 : -1;
2172
2173     /* If the given side is part of the given lump, then the lump is behind. */
2174
2175     for (si = 0; si < lp->sc; si++)
2176         if (fp->sv + fp->iv[lp->s0 + si] == sp)
2177             return -1;
2178
2179     /* Check if each lump vertex is in front of, behind, on the side. */
2180
2181     for (vi = 0; vi < lp->vc; vi++)
2182     {
2183         float d = v_dot(fp->vv[fp->iv[lp->v0 + vi]].p, sp->n) - sp->d;
2184
2185         if (d > 0) f++;
2186         if (d < 0) b++;
2187     }
2188
2189     /* If no verts are behind, the lump is in front, and vice versa. */
2190
2191     if (f > 0 && b == 0) return +1;
2192     if (b > 0 && f == 0) return -1;
2193
2194     /* Else, the lump crosses the side. */
2195
2196     return 0;
2197 }
2198
2199 static int node_node(struct s_file *fp, int l0, int lc, float bsphere[][4])
2200 {
2201     if (lc < 8)
2202     {
2203         /* Base case.  Dump all given lumps into a leaf node. */
2204
2205         fp->nv[fp->nc].si = -1;
2206         fp->nv[fp->nc].ni = -1;
2207         fp->nv[fp->nc].nj = -1;
2208         fp->nv[fp->nc].l0 = l0;
2209         fp->nv[fp->nc].lc = lc;
2210
2211         return incn(fp);
2212     }
2213     else
2214     {
2215         int sj  = 0;
2216         int sjd = lc;
2217         int sjo = lc;
2218         int si;
2219         int li = 0, lic = 0;
2220         int lj = 0, ljc = 0;
2221         int lk = 0, lkc = 0;
2222         int i;
2223
2224         /* Find the side that most evenly splits the given lumps. */
2225
2226         for (si = 0; si < fp->sc; si++)
2227         {
2228             int o = 0;
2229             int d = 0;
2230             int k = 0;
2231
2232             for (li = 0; li < lc; li++)
2233                 if ((k = test_lump_side(fp,
2234                                         fp->lv + l0 + li,
2235                                         fp->sv + si,
2236                                         bsphere[l0 + li])))
2237                     d += k;
2238                 else
2239                     o++;
2240
2241             d = abs(d);
2242
2243             if ((d < sjd) || (d == sjd && o < sjo))
2244             {
2245                 sj  = si;
2246                 sjd = d;
2247                 sjo = o;
2248             }
2249         }
2250
2251         /* Flag each lump with its position WRT the side. */
2252
2253         for (li = 0; li < lc; li++)
2254             if (debug_output)
2255             {
2256                 fp->lv[l0+li].fl = (fp->lv[l0+li].fl & 1) | 0x20;
2257             }
2258             else
2259             {
2260                 switch (test_lump_side(fp,
2261                                        fp->lv + l0 + li,
2262                                        fp->sv + sj,
2263                                        bsphere[l0 + li]))
2264                 {
2265                 case +1:
2266                     fp->lv[l0+li].fl = (fp->lv[l0+li].fl & 1) | 0x10;
2267                     break;
2268
2269                 case  0:
2270                     fp->lv[l0+li].fl = (fp->lv[l0+li].fl & 1) | 0x20;
2271                     break;
2272
2273                 case -1:
2274                     fp->lv[l0+li].fl = (fp->lv[l0+li].fl & 1) | 0x40;
2275                     break;
2276                 }
2277             }
2278
2279         /* Sort all lumps in the range by their flag values. */
2280
2281         for (li = 1; li < lc; li++)
2282             for (lj = 0; lj < li; lj++)
2283                 if (fp->lv[l0 + li].fl < fp->lv[l0 + lj].fl)
2284                 {
2285                     struct s_lump l;
2286                     float f;
2287                     int i;
2288
2289                     for (i = 0; i < 4; i++)
2290                     {
2291                         f                   = bsphere[l0 + li][i];
2292                         bsphere[l0 + li][i] = bsphere[l0 + lj][i];
2293                         bsphere[l0 + lj][i] =                   f;
2294                     }
2295
2296                     l               = fp->lv[l0 + li];
2297                     fp->lv[l0 + li] = fp->lv[l0 + lj];
2298                     fp->lv[l0 + lj] =               l;
2299                 }
2300
2301         /* Establish the in-front, on, and behind lump ranges. */
2302
2303         li = lic = 0;
2304         lj = ljc = 0;
2305         lk = lkc = 0;
2306
2307         for (i = lc - 1; i >= 0; i--)
2308             switch (fp->lv[l0 + i].fl & 0xf0)
2309             {
2310             case 0x10: li = l0 + i; lic++; break;
2311             case 0x20: lj = l0 + i; ljc++; break;
2312             case 0x40: lk = l0 + i; lkc++; break;
2313             }
2314
2315         /* Add the lumps on the side to the node. */
2316
2317         i = incn(fp);
2318
2319         fp->nv[i].si = sj;
2320         fp->nv[i].ni = node_node(fp, li, lic, bsphere);
2321
2322         fp->nv[i].nj = node_node(fp, lk, lkc, bsphere);
2323         fp->nv[i].l0 = lj;
2324         fp->nv[i].lc = ljc;
2325
2326         return i;
2327     }
2328 }
2329
2330 /*
2331  * Compute a bounding sphere for a lump (not optimal)
2332  */
2333 static void lump_bounding_sphere(struct s_file *fp,
2334                                  struct s_lump *lp,
2335                                  float bsphere[4])
2336 {
2337     float bbox[6];
2338     float r;
2339     int i;
2340
2341     if (!lp->vc)
2342         return;
2343
2344     bbox[0] = bbox[3] = fp->vv[fp->iv[lp->v0]].p[0];
2345     bbox[1] = bbox[4] = fp->vv[fp->iv[lp->v0]].p[1];
2346     bbox[2] = bbox[5] = fp->vv[fp->iv[lp->v0]].p[2];
2347
2348     for (i = 1; i < lp->vc; i++)
2349     {
2350         struct s_vert *vp = fp->vv + fp->iv[lp->v0 + i];
2351         int j;
2352
2353         for (j = 0; j < 3; j++)
2354             if (vp->p[j] < bbox[j])
2355                 bbox[j] = vp->p[j];
2356
2357         for (j = 0; j < 3; j++)
2358             if (vp->p[j] > bbox[j + 3])
2359                 bbox[j + 3] = vp->p[j];
2360     }
2361
2362     r = 0;
2363
2364     for (i = 0; i < 3; i++)
2365     {
2366         bsphere[i] = (bbox[i] + bbox[i + 3]) / 2;
2367         r += (bsphere[i] - bbox[i]) * (bsphere[i] - bbox[i]);
2368     }
2369
2370     bsphere[3] = fsqrtf(r);
2371 }
2372
2373 static void node_file(struct s_file *fp)
2374 {
2375     float bsphere[MAXL][4];
2376     int i;
2377
2378     /* Compute a bounding sphere for each lump. */
2379
2380     for (i = 0; i < fp->lc; i++)
2381         lump_bounding_sphere(fp, fp->lv + i, bsphere[i]);
2382
2383     /* Sort the lumps of each body into BSP nodes. */
2384
2385     for (i = 0; i < fp->bc; i++)
2386         fp->bv[i].ni = node_node(fp, fp->bv[i].l0, fp->bv[i].lc, bsphere);
2387 }
2388
2389 /*---------------------------------------------------------------------------*/
2390
2391 static void dump_file(struct s_file *p, const char *name)
2392 {
2393     /* FIXME:  Count visible geoms.
2394      *
2395      * I'm afraid items break this (not sure though) so leaving it out.
2396      */
2397
2398 #if 0
2399     int i, j;
2400 #endif
2401     int i;
2402     int c = 0;
2403     int n = 0;
2404 #if 0
2405     int m = p->rc + p->cc * 128 + (p->zc * p->jc + p->xc) * 32;
2406 #endif
2407
2408     /* Count the number of solid lumps. */
2409
2410     for (i = 0; i < p->lc; i++)
2411         if ((p->lv[i].fl & 1) == 0)
2412             n++;
2413
2414 #if 0
2415     /* Count the number of visible geoms. */
2416
2417     for (i = 0; i < p->bc; i++)
2418     {
2419         for (j = 0; j < p->bv[i].lc; j++)
2420             m += p->lv[p->bv[i].l0 + j].gc;
2421         m += p->bv[i].gc;
2422     }
2423 #endif
2424
2425     /* Count the total value of all coins. */
2426
2427     for (i = 0; i < p->hc; i++)
2428         if (p->hv[i].t == ITEM_COIN)
2429             c += p->hv[i].n;
2430
2431 #if 0
2432     printf("%s (%d/%d/$%d)\n"
2433 #endif
2434     printf("%s (%d/$%d)\n"
2435            "  mtrl  vert  edge  side  texc"
2436            "  geom  lump  path  node  body\n"
2437            "%6d%6d%6d%6d%6d%6d%6d%6d%6d%6d\n"
2438            "  item  goal  view  jump  swch"
2439            "  bill  ball  char  dict  indx\n"
2440            "%6d%6d%6d%6d%6d%6d%6d%6d%6d%6d\n",
2441 #if 0
2442            name, n, m, c,
2443 #endif
2444            name, n, c,
2445            p->mc, p->vc, p->ec, p->sc, p->tc,
2446            p->gc, p->lc, p->pc, p->nc, p->bc,
2447            p->hc, p->zc, p->wc, p->jc, p->xc,
2448            p->rc, p->uc, p->ac, p->dc, p->ic);
2449 }
2450
2451 int main(int argc, char *argv[])
2452 {
2453     char src[MAXSTR] = "";
2454     char dst[MAXSTR] = "";
2455     struct s_file f;
2456     fs_file fin;
2457
2458     if (!fs_init(argv[0]))
2459     {
2460         fprintf(stderr, "Failure to initialize virtual file system: %s\n",
2461                 fs_error());
2462         return 1;
2463     }
2464
2465     if (argc > 2)
2466     {
2467         input_file = argv[1];
2468
2469         if (argc > 3 && strcmp(argv[3], "--debug") == 0)
2470             debug_output = 1;
2471
2472         strncpy(src, argv[1], MAXSTR - 1);
2473         strncpy(dst, argv[1], MAXSTR - 1);
2474
2475         if (strcmp(dst + strlen(dst) - 4, ".map") == 0)
2476             strcpy(dst + strlen(dst) - 4, ".sol");
2477         else
2478             strcat(dst, ".sol");
2479
2480         fs_add_path     (dir_name(src));
2481         fs_set_write_dir(dir_name(dst));
2482
2483         if ((fin = fs_open(base_name(src, NULL), "r")))
2484         {
2485             if (!fs_add_path_with_archives(argv[2]))
2486             {
2487                 fprintf(stderr, "Failure to establish data directory\n");
2488                 fs_close(fin);
2489                 fs_quit();
2490                 return 1;
2491             }
2492
2493             init_file(&f);
2494             read_map(&f, fin);
2495
2496             resolve();
2497             targets(&f);
2498
2499             clip_file(&f);
2500             move_file(&f);
2501             uniq_file(&f);
2502             smth_file(&f);
2503             sort_file(&f);
2504             node_file(&f);
2505             dump_file(&f, dst);
2506
2507             sol_stor(&f, base_name(dst, NULL));
2508
2509             fs_close(fin);
2510
2511             free_imagedata();
2512         }
2513     }
2514     else fprintf(stderr, "Usage: %s <map> <data> [--debug]\n", argv[0]);
2515
2516     return 0;
2517 }
2518