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