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