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