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