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