vcs.maemo.org Git - neverball/blob - share/mapc.c

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