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