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