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     up->a = 90.f;
1135
1136     for (i = 0; i < c; i++)
1137     {
1138         if (strcmp(k[i], "radius") == 0)
1139             sscanf(v[i], "%f", &up->r);
1140
1141         if (strcmp(k[i], "angle") == 0)
1142             sscanf(v[i], "%f", &up->a);
1143
1144         if (strcmp(k[i], "origin") == 0)
1145         {
1146             int x = 0, y = 0, z = 0;
1147
1148             sscanf(v[i], "%d %d %d", &x, &y, &z);
1149
1150             up->p[0] = +(float) (x)      / SCALE;
1151             up->p[1] = +(float) (z - 24) / SCALE;
1152             up->p[2] = -(float) (y)      / SCALE;
1153         }
1154     }
1155
1156     up->p[1] += up->r + SMALL;
1157 }
1158
1159 /*---------------------------------------------------------------------------*/
1160
1161 static void read_ent(struct s_file *fp, FILE *fin)
1162 {
1163     char k[MAXKEY][MAXSTR];
1164     char v[MAXKEY][MAXSTR];
1165     int t, i = 0, c = 0;
1166
1167     int l0 = fp->lc;
1168
1169     while ((t = map_token(fin, -1, k[c], v[c])))
1170     {
1171         if (t == T_KEY)
1172         {
1173             if (strcmp(k[c], "classname") == 0)
1174                 i = c;
1175             c++;
1176         }
1177         if (t == T_BEG) read_lump(fp, fin);
1178         if (t == T_END) break;
1179     }
1180
1181     if (!strcmp(v[i], "light"))                    make_coin(fp, k, v, c);
1182     if (!strcmp(v[i], "info_camp"))                make_swch(fp, k, v, c);
1183     if (!strcmp(v[i], "info_null"))                make_bill(fp, k, v, c);
1184     if (!strcmp(v[i], "path_corner"))              make_path(fp, k, v, c);
1185     if (!strcmp(v[i], "info_player_start"))        make_ball(fp, k, v, c);
1186     if (!strcmp(v[i], "info_player_intermission")) make_view(fp, k, v, c);
1187     if (!strcmp(v[i], "info_player_deathmatch"))   make_goal(fp, k, v, c);
1188     if (!strcmp(v[i], "target_teleporter"))        make_jump(fp, k, v, c);
1189     if (!strcmp(v[i], "target_position"))          make_targ(fp, k, v, c);
1190     if (!strcmp(v[i], "worldspawn"))               make_body(fp, k, v, c, l0);
1191     if (!strcmp(v[i], "func_train"))               make_body(fp, k, v, c, l0);
1192     if (!strcmp(v[i], "misc_model"))               make_body(fp, k, v, c, l0);
1193 }
1194
1195 static void read_map(struct s_file *fp, FILE *fin)
1196 {
1197     char k[MAXSTR];
1198     char v[MAXSTR];
1199     int t;
1200
1201     while ((t = map_token(fin, -1, k, v)))
1202         if (t == T_BEG)
1203             read_ent(fp, fin);
1204 }
1205
1206 /*---------------------------------------------------------------------------*/
1207
1208 /* Test the location of a point with respect to a side plane. */
1209
1210 static int fore_side(const float p[3], const struct s_side *sp)
1211 {
1212     return (v_dot(p, sp->n) - sp->d > +SMALL) ? 1 : 0;
1213 }
1214
1215 static int on_side(const float p[3], const struct s_side *sp)
1216 {
1217     float d = v_dot(p, sp->n) - sp->d;
1218
1219     return (-SMALL < d && d < +SMALL) ? 1 : 0;
1220 }
1221
1222 /*---------------------------------------------------------------------------*/
1223 /*
1224  * Confirm  that  the addition  of  a vert  would  not  result in  degenerate
1225  * geometry.
1226  */
1227
1228 static int ok_vert(const struct s_file *fp,
1229                    const struct s_lump *lp, const float p[3])
1230 {
1231     float r[3];
1232     int i;
1233
1234     for (i = 0; i < lp->vc; i++)
1235     {
1236         float *q = fp->vv[fp->iv[lp->v0 + i]].p;
1237
1238         v_sub(r, p, q);
1239
1240         if (v_len(r) < SMALL)
1241             return 0;
1242     }
1243     return 1;
1244 }
1245
1246 /*---------------------------------------------------------------------------*/
1247
1248 /*
1249  * The following functions take the  set of planes defining a lump and
1250  * find the verts, edges, and  geoms that describe its boundaries.  To
1251  * do this, they first find the verts, and then search these verts for
1252  * valid edges and  geoms.  It may be more  efficient to compute edges
1253  * and  geoms directly  by clipping  down infinite  line  segments and
1254  * planes,  but this  would be  more  complex and  prone to  numerical
1255  * error.
1256  */
1257
1258 /*
1259  * Given 3  side planes,  compute the point  of intersection,  if any.
1260  * Confirm that this point falls  within the current lump, and that it
1261  * is unique.  Add it as a vert of the solid.
1262  */
1263 static void clip_vert(struct s_file *fp,
1264                       struct s_lump *lp, int si, int sj, int sk)
1265 {
1266     float M[16], X[16], I[16];
1267     float d[3],  p[3];
1268     int i;
1269
1270     d[0] = fp->sv[si].d;
1271     d[1] = fp->sv[sj].d;
1272     d[2] = fp->sv[sk].d;
1273
1274     m_basis(M, fp->sv[si].n, fp->sv[sj].n, fp->sv[sk].n);
1275     m_xps(X, M);
1276
1277     if (m_inv(I, X))
1278     {
1279         m_vxfm(p, I, d);
1280
1281         for (i = 0; i < lp->sc; i++)
1282         {
1283             int si = fp->iv[lp->s0 + i];
1284
1285             if (fore_side(p, fp->sv + si))
1286                 return;
1287         }
1288
1289         if (ok_vert(fp, lp, p))
1290         {
1291             v_cpy(fp->vv[fp->vc].p, p);
1292
1293             fp->iv[fp->ic] = fp->vc;
1294             inci(fp);
1295             incv(fp);
1296             lp->vc++;
1297         }
1298     }
1299 }
1300
1301 /*
1302  * Given two  side planes,  find an edge  along their  intersection by
1303  * finding a pair of vertices that fall on both planes.  Add it to the
1304  * solid.
1305  */
1306 static void clip_edge(struct s_file *fp,
1307                       struct s_lump *lp, int si, int sj)
1308 {
1309     int i, j;
1310
1311     for (i = 1; i < lp->vc; i++)
1312         for (j = 0; j < i; j++)
1313         {
1314             int vi = fp->iv[lp->v0 + i];
1315             int vj = fp->iv[lp->v0 + j];
1316
1317             if (on_side(fp->vv[vi].p, fp->sv + si) &&
1318                 on_side(fp->vv[vj].p, fp->sv + si) &&
1319                 on_side(fp->vv[vi].p, fp->sv + sj) &&
1320                 on_side(fp->vv[vj].p, fp->sv + sj))
1321             {
1322                 fp->ev[fp->ec].vi = vi;
1323                 fp->ev[fp->ec].vj = vj;
1324
1325                 fp->iv[fp->ic] = fp->ec;
1326
1327                 inci(fp);
1328                 ince(fp);
1329                 lp->ec++;
1330             }
1331         }
1332 }
1333
1334 /*
1335  * Find all verts that lie on  the given side of the lump.  Sort these
1336  * verts to  have a counter-clockwise winding about  the plane normal.
1337  * Create geoms to tessalate the resulting convex polygon.
1338  */
1339 static void clip_geom(struct s_file *fp,
1340                       struct s_lump *lp, int si)
1341 {
1342     int   m[256], t[256], d, i, j, n = 0;
1343     float u[3];
1344     float v[3];
1345     float w[3];
1346
1347     struct s_side *sp = fp->sv + si;
1348
1349     /* Find em. */
1350
1351     for (i = 0; i < lp->vc; i++)
1352     {
1353         int vi = fp->iv[lp->v0 + i];
1354
1355         if (on_side(fp->vv[vi].p, sp))
1356         {
1357             m[n] = vi;
1358             t[n] = inct(fp);
1359
1360             v_add(v, fp->vv[vi].p, plane_p[si]);
1361
1362             fp->tv[t[n]].u[0] = v_dot(v, plane_u[si]);
1363             fp->tv[t[n]].u[1] = v_dot(v, plane_v[si]);
1364
1365             n++;
1366         }
1367     }
1368
1369     /* Sort em. */
1370
1371     for (i = 1; i < n; i++)
1372         for (j = i + 1; j < n; j++)
1373         {
1374             v_sub(u, fp->vv[m[i]].p, fp->vv[m[0]].p);
1375             v_sub(v, fp->vv[m[j]].p, fp->vv[m[0]].p);
1376             v_crs(w, u, v);
1377
1378             if (v_dot(w, sp->n) < 0.f)
1379             {
1380                 d     = m[i];
1381                 m[i]  = m[j];
1382                 m[j]  =    d;
1383
1384                 d     = t[i];
1385                 t[i]  = t[j];
1386                 t[j]  =    d;
1387             }
1388         }
1389
1390     /* Index em. */
1391
1392     for (i = 0; i < n - 2; i++)
1393     {
1394         fp->gv[fp->gc].mi = plane_m[si];
1395
1396         fp->gv[fp->gc].ti = t[0];
1397         fp->gv[fp->gc].tj = t[i + 1];
1398         fp->gv[fp->gc].tk = t[i + 2];
1399
1400         fp->gv[fp->gc].si = si;
1401         fp->gv[fp->gc].sj = si;
1402         fp->gv[fp->gc].sk = si;
1403
1404         fp->gv[fp->gc].vi = m[0];
1405         fp->gv[fp->gc].vj = m[i + 1];
1406         fp->gv[fp->gc].vk = m[i + 2];
1407
1408         fp->iv[fp->ic] = fp->gc;
1409         inci(fp);
1410         incg(fp);
1411         lp->gc++;
1412     }
1413 }
1414
1415 /*
1416  * Iterate the sides of the lump, attemping to generate a new vert for
1417  * each trio of planes, a new edge  for each pair of planes, and a new
1418  * set of geom for each visible plane.
1419  */
1420 static void clip_lump(struct s_file *fp, struct s_lump *lp)
1421 {
1422     int i, j, k;
1423
1424     lp->v0 = fp->ic;
1425     lp->vc = 0;
1426
1427     for (i = 2; i < lp->sc; i++)
1428         for (j = 1; j < i; j++)
1429             for (k = 0; k < j; k++)
1430                 clip_vert(fp, lp,
1431                           fp->iv[lp->s0 + i],
1432                           fp->iv[lp->s0 + j],
1433                           fp->iv[lp->s0 + k]);
1434
1435     lp->e0 = fp->ic;
1436     lp->ec = 0;
1437
1438     for (i = 1; i < lp->sc; i++)
1439         for (j = 0; j < i; j++)
1440             clip_edge(fp, lp,
1441                       fp->iv[lp->s0 + i],
1442                       fp->iv[lp->s0 + j]);
1443
1444     lp->g0 = fp->ic;
1445     lp->gc = 0;
1446
1447     for (i = 0; i < lp->sc; i++)
1448         if (fp->mv[plane_m[fp->iv[lp->s0 + i]]].d[3] > 0)
1449             clip_geom(fp, lp,
1450                       fp->iv[lp->s0 + i]);
1451
1452     for (i = 0; i < lp->sc; i++)
1453         if (plane_f[fp->iv[lp->s0 + i]])
1454             lp->fl |= L_DETAIL;
1455 }
1456
1457 static void clip_file(struct s_file *fp)
1458 {
1459     int i;
1460
1461     for (i = 0; i < fp->lc; i++)
1462         clip_lump(fp, fp->lv + i);
1463 }
1464
1465 /*---------------------------------------------------------------------------*/
1466
1467 /*
1468  * For each body element type,  determine if element 'p' is equivalent
1469  * to element  'q'.  This  is more than  a simple memory  compare.  It
1470  * effectively  snaps mtrls and  verts togather,  and may  reverse the
1471  * winding of  an edge or a geom.   This is done in  order to maximize
1472  * the number of elements that can be eliminated.
1473  */
1474
1475 static int comp_mtrl(const struct s_mtrl *mp, const struct s_mtrl *mq)
1476 {
1477     if (fabs(mp->d[0] - mq->d[0]) > SMALL) return 0;
1478     if (fabs(mp->d[1] - mq->d[1]) > SMALL) return 0;
1479     if (fabs(mp->d[2] - mq->d[2]) > SMALL) return 0;
1480     if (fabs(mp->d[3] - mq->d[3]) > SMALL) return 0;
1481
1482     if (fabs(mp->a[0] - mq->a[0]) > SMALL) return 0;
1483     if (fabs(mp->a[1] - mq->a[1]) > SMALL) return 0;
1484     if (fabs(mp->a[2] - mq->a[2]) > SMALL) return 0;
1485     if (fabs(mp->a[3] - mq->a[3]) > SMALL) return 0;
1486
1487     if (fabs(mp->s[0] - mq->s[0]) > SMALL) return 0;
1488     if (fabs(mp->s[1] - mq->s[1]) > SMALL) return 0;
1489     if (fabs(mp->s[2] - mq->s[2]) > SMALL) return 0;
1490     if (fabs(mp->s[3] - mq->s[3]) > SMALL) return 0;
1491
1492     if (fabs(mp->e[0] - mq->e[0]) > SMALL) return 0;
1493     if (fabs(mp->e[1] - mq->e[1]) > SMALL) return 0;
1494     if (fabs(mp->e[2] - mq->e[2]) > SMALL) return 0;
1495     if (fabs(mp->e[3] - mq->e[3]) > SMALL) return 0;
1496
1497     if (fabs(mp->h[0] - mq->h[0]) > SMALL) return 0;
1498
1499     if (strncmp(mp->f, mq->f, PATHMAX)) return 0;
1500
1501     return 1;
1502 }
1503
1504 static int comp_vert(const struct s_vert *vp, const struct s_vert *vq)
1505 {
1506     if (fabs(vp->p[0] - vq->p[0]) > SMALL) return 0;
1507     if (fabs(vp->p[1] - vq->p[1]) > SMALL) return 0;
1508     if (fabs(vp->p[2] - vq->p[2]) > SMALL) return 0;
1509
1510     return 1;
1511 }
1512
1513 static int comp_edge(const struct s_edge *ep, const struct s_edge *eq)
1514 {
1515     if (ep->vi != eq->vi && ep->vi != eq->vj) return 0;
1516     if (ep->vj != eq->vi && ep->vj != eq->vj) return 0;
1517
1518     return 1;
1519 }
1520
1521 static int comp_side(const struct s_side *sp, const struct s_side *sq)
1522 {
1523     if  (fabs(sp->d - sq->d) > SMALL)  return 0;
1524     if (v_dot(sp->n,  sq->n) < 0.9999) return 0;
1525
1526     return 1;
1527 }
1528
1529 static int comp_texc(const struct s_texc *tp, const struct s_texc *tq)
1530 {
1531     if (fabs(tp->u[0] - tq->u[0]) > SMALL) return 0;
1532     if (fabs(tp->u[1] - tq->u[1]) > SMALL) return 0;
1533
1534     return 1;
1535 }
1536
1537 static int comp_geom(const struct s_geom *gp, const struct s_geom *gq)
1538 {
1539     if (gp->mi != gq->mi) return 0;
1540
1541     if (gp->ti != gq->ti) return 0;
1542     if (gp->si != gq->si) return 0;
1543     if (gp->vi != gq->vi) return 0;
1544
1545     if (gp->tj != gq->tj) return 0;
1546     if (gp->sj != gq->sj) return 0;
1547     if (gp->vj != gq->vj) return 0;
1548
1549     if (gp->tk != gq->tk) return 0;
1550     if (gp->sk != gq->sk) return 0;
1551     if (gp->vk != gq->vk) return 0;
1552
1553     return 1;
1554 }
1555
1556 /*---------------------------------------------------------------------------*/
1557
1558 /*
1559  * For each file  element type, replace all references  to element 'i'
1560  * with a  reference to element  'j'.  These are used  when optimizing
1561  * and sorting the file.
1562  */
1563
1564 static void swap_mtrl(struct s_file *fp, int mi, int mj)
1565 {
1566     int i;
1567
1568     for (i = 0; i < fp->gc; i++)
1569         if (fp->gv[i].mi == mi) fp->gv[i].mi = mj;
1570     for (i = 0; i < fp->rc; i++)
1571         if (fp->rv[i].mi == mi) fp->rv[i].mi = mj;
1572 }
1573
1574 static void swap_vert(struct s_file *fp, int vi, int vj)
1575 {
1576     int i, j;
1577
1578     for (i = 0; i < fp->ec; i++)
1579     {
1580         if (fp->ev[i].vi == vi) fp->ev[i].vi = vj;
1581         if (fp->ev[i].vj == vi) fp->ev[i].vj = vj;
1582     }
1583
1584     for (i = 0; i < fp->gc; i++)
1585     {
1586         if (fp->gv[i].vi == vi) fp->gv[i].vi = vj;
1587         if (fp->gv[i].vj == vi) fp->gv[i].vj = vj;
1588         if (fp->gv[i].vk == vi) fp->gv[i].vk = vj;
1589     }
1590
1591     for (i = 0; i < fp->lc; i++)
1592         for (j = 0; j < fp->lv[i].vc; j++)
1593             if (fp->iv[fp->lv[i].v0 + j] == vi)
1594                 fp->iv[fp->lv[i].v0 + j]  = vj;
1595 }
1596
1597 static void swap_edge(struct s_file *fp, int ei, int ej)
1598 {
1599     int i, j;
1600
1601     for (i = 0; i < fp->lc; i++)
1602         for (j = 0; j < fp->lv[i].ec; j++)
1603             if (fp->iv[fp->lv[i].e0 + j] == ei)
1604                 fp->iv[fp->lv[i].e0 + j]  = ej;
1605 }
1606
1607 static void swap_side(struct s_file *fp, int si, int sj)
1608 {
1609     int i, j;
1610
1611     for (i = 0; i < fp->gc; i++)
1612     {
1613         if (fp->gv[i].si == si) fp->gv[i].si = sj;
1614         if (fp->gv[i].sj == si) fp->gv[i].sj = sj;
1615         if (fp->gv[i].sk == si) fp->gv[i].sk = sj;
1616     }
1617     for (i = 0; i < fp->nc; i++)
1618         if (fp->nv[i].si == si) fp->nv[i].si = sj;
1619
1620     for (i = 0; i < fp->lc; i++)
1621         for (j = 0; j < fp->lv[i].sc; j++)
1622             if (fp->iv[fp->lv[i].s0 + j] == si)
1623                 fp->iv[fp->lv[i].s0 + j]  = sj;
1624 }
1625
1626 static void swap_texc(struct s_file *fp, int ti, int tj)
1627 {
1628     int i;
1629
1630     for (i = 0; i < fp->gc; i++)
1631     {
1632         if (fp->gv[i].ti == ti) fp->gv[i].ti = tj;
1633         if (fp->gv[i].tj == ti) fp->gv[i].tj = tj;
1634         if (fp->gv[i].tk == ti) fp->gv[i].tk = tj;
1635     }
1636 }
1637
1638
1639 static void swap_geom(struct s_file *fp, int gi, int gj)
1640 {
1641     int i, j;
1642
1643     for (i = 0; i < fp->lc; i++)
1644         for (j = 0; j < fp->lv[i].gc; j++)
1645             if (fp->iv[fp->lv[i].g0 + j] == gi)
1646                 fp->iv[fp->lv[i].g0 + j]  = gj;
1647
1648     for (i = 0; i < fp->bc; i++)
1649         for (j = 0; j < fp->bv[i].gc; j++)
1650             if (fp->iv[fp->bv[i].g0 + j] == gi)
1651                 fp->iv[fp->bv[i].g0 + j]  = gj;
1652 }
1653
1654 /*---------------------------------------------------------------------------*/
1655
1656 static void uniq_mtrl(struct s_file *fp)
1657 {
1658     int i, j, k = 0;
1659
1660     for (i = 0; i < fp->mc; i++)
1661     {
1662         for (j = 0; j < k; j++)
1663             if (comp_mtrl(fp->mv + i, fp->mv + j))
1664             {
1665                 swap_mtrl(fp, i, j);
1666                 break;
1667             }
1668
1669         if (j == k)
1670         {
1671             if (i != k)
1672             {
1673                 fp->mv[k] = fp->mv[i];
1674                 swap_mtrl(fp, i, k);
1675             }
1676             k++;
1677         }
1678     }
1679
1680     fp->mc = k;
1681 }
1682
1683 static void uniq_vert(struct s_file *fp)
1684 {
1685     int i, j, k = 0;
1686
1687     for (i = 0; i < fp->vc; i++)
1688     {
1689         for (j = 0; j < k; j++)
1690             if (comp_vert(fp->vv + i, fp->vv + j))
1691             {
1692                 swap_vert(fp, i, j);
1693                 break;
1694             }
1695
1696         if (j == k)
1697         {
1698             if (i != k)
1699             {
1700                 fp->vv[k] = fp->vv[i];
1701                 swap_vert(fp, i, k);
1702             }
1703             k++;
1704         }
1705     }
1706
1707     fp->vc = k;
1708 }
1709
1710 static void uniq_edge(struct s_file *fp)
1711 {
1712     int i, j, k = 0;
1713
1714     for (i = 0; i < fp->ec; i++)
1715     {
1716         for (j = 0; j < k; j++)
1717             if (comp_edge(fp->ev + i, fp->ev + j))
1718             {
1719                 swap_edge(fp, i, j);
1720                 break;
1721             }
1722
1723         if (j == k)
1724         {
1725             if (i != k)
1726             {
1727                 fp->ev[k] = fp->ev[i];
1728                 swap_edge(fp, i, k);
1729             }
1730             k++;
1731         }
1732     }
1733
1734     fp->ec = k;
1735 }
1736
1737 static void uniq_geom(struct s_file *fp)
1738 {
1739     int i, j, k = 0;
1740
1741     for (i = 0; i < fp->gc; i++)
1742     {
1743         for (j = 0; j < k; j++)
1744             if (comp_geom(fp->gv + i, fp->gv + j))
1745             {
1746                 swap_geom(fp, i, j);
1747                 break;
1748             }
1749
1750         if (j == k)
1751         {
1752             if (i != k)
1753             {
1754                 fp->gv[k] = fp->gv[i];
1755                 swap_geom(fp, i, k);
1756             }
1757             k++;
1758         }
1759     }
1760
1761     fp->gc = k;
1762 }
1763
1764 static void uniq_texc(struct s_file *fp)
1765 {
1766     int i, j, k = 0;
1767
1768     for (i = 0; i < fp->tc; i++)
1769     {
1770         for (j = 0; j < k; j++)
1771             if (comp_texc(fp->tv + i, fp->tv + j))
1772             {
1773                 swap_texc(fp, i, j);
1774                 break;
1775             }
1776
1777         if (j == k)
1778         {
1779             if (i != k)
1780             {
1781                 fp->tv[k] = fp->tv[i];
1782                 swap_texc(fp, i, k);
1783             }
1784             k++;
1785         }
1786     }
1787
1788     fp->tc = k;
1789 }
1790
1791 static void uniq_side(struct s_file *fp)
1792 {
1793     int i, j, k = 0;
1794
1795     for (i = 0; i < fp->sc; i++)
1796     {
1797         for (j = 0; j < k; j++)
1798             if (comp_side(fp->sv + i, fp->sv + j))
1799             {
1800                 swap_side(fp, i, j);
1801                 break;
1802             }
1803
1804         if (j == k)
1805         {
1806             if (i != k)
1807             {
1808                 fp->sv[k] = fp->sv[i];
1809                 swap_side(fp, i, k);
1810             }
1811             k++;
1812         }
1813     }
1814
1815     fp->sc = k;
1816 }
1817
1818 static void uniq_file(struct s_file *fp)
1819 {
1820     uniq_mtrl(fp);
1821     uniq_vert(fp);
1822     uniq_edge(fp);
1823     uniq_side(fp);
1824     uniq_texc(fp);
1825     uniq_geom(fp);
1826 }
1827
1828 /*---------------------------------------------------------------------------*/
1829
1830 static void sort_file(struct s_file *fp)
1831 {
1832     int i, j;
1833
1834     /* Sort billboards farthest to nearest. */
1835
1836     for (i = 0; i < fp->rc; i++)
1837         for (j = i + 1; j < fp->rc; j++)
1838             if (fp->rv[j].d > fp->rv[i].d)
1839             {
1840                 struct s_bill t;
1841
1842                 t         = fp->rv[i];
1843                 fp->rv[i] = fp->rv[j];
1844                 fp->rv[j] =         t;
1845             }
1846
1847     /* Ensure the first vertex is the lowest. */
1848
1849     for (i = 0; i < fp->vc; i++)
1850         if (fp->vv[0].p[1] > fp->vv[i].p[1])
1851         {
1852             struct s_vert t;
1853
1854             t         = fp->vv[0];
1855             fp->vv[0] = fp->vv[i];
1856             fp->vv[i] =         t;
1857
1858             swap_vert(fp,  0, -1);
1859             swap_vert(fp,  i,  0);
1860             swap_vert(fp, -1,  i);
1861         }
1862 }
1863
1864 /*---------------------------------------------------------------------------*/
1865
1866 static int test_lump_side(const struct s_file *fp,
1867                           const struct s_lump *lp,
1868                           const struct s_side *sp)
1869 {
1870     int si;
1871     int vi;
1872
1873     int f = 0;
1874     int b = 0;
1875
1876     /* If the given side is part of the given lump, then the lump is behind. */
1877
1878     for (si = 0; si < lp->sc; si++)
1879         if (fp->sv + fp->iv[lp->s0 + si] == sp)
1880             return -1;
1881
1882     /* Check if each lump vertex is in front of, behind, on the side. */
1883
1884     for (vi = 0; vi < lp->vc; vi++)
1885     {
1886         float d = v_dot(fp->vv[fp->iv[lp->v0 + vi]].p, sp->n) - sp->d;
1887
1888         if (d > 0) f++;
1889         if (d < 0) b++;
1890     }
1891
1892     /* If no verts are behind, the lump is in front, and vice versa. */
1893
1894     if (f > 0 && b == 0) return +1;
1895     if (b > 0 && f == 0) return -1;
1896
1897     /* Else, the lump crosses the side. */
1898
1899     return 0;
1900 }
1901
1902 static int node_node(struct s_file *fp, int l0, int lc)
1903 {
1904     if (lc < 8)
1905     {
1906         /* Base case.  Dump all given lumps into a leaf node. */
1907
1908         fp->nv[fp->nc].si = -1;
1909         fp->nv[fp->nc].ni = -1;
1910         fp->nv[fp->nc].nj = -1;
1911         fp->nv[fp->nc].l0 = l0;
1912         fp->nv[fp->nc].lc = lc;
1913
1914         return incn(fp);
1915     }
1916     else
1917     {
1918         int sj  = 0;
1919         int sjd = lc;
1920         int sjo = lc;
1921         int si;
1922         int li = 0, lic = 0;
1923         int lj = 0, ljc = 0;
1924         int lk = 0, lkc = 0;
1925         int i;
1926
1927         /* Find the side that most evenly splits the given lumps. */
1928
1929         for (si = 0; si < fp->sc; si++)
1930         {
1931             int o = 0;
1932             int d = 0;
1933             int k = 0;
1934
1935             for (li = 0; li < lc; li++)
1936                 if ((k = test_lump_side(fp, fp->lv + l0 + li, fp->sv + si)))
1937                     d += k;
1938                 else
1939                     o++;
1940
1941             d = abs(d);
1942
1943             if ((d < sjd) || (d == sjd && o < sjo))
1944             {
1945                 sj  = si;
1946                 sjd = d;
1947                 sjo = o;
1948             }
1949         }
1950
1951         /* Flag each lump with its position WRT the side. */
1952
1953         for (li = 0; li < lc; li++)
1954             switch (test_lump_side(fp, fp->lv + l0 + li, fp->sv + sj))
1955             {
1956             case +1: fp->lv[l0+li].fl = (fp->lv[l0+li].fl & 1) | 0x10; break;
1957             case  0: fp->lv[l0+li].fl = (fp->lv[l0+li].fl & 1) | 0x20; break;
1958             case -1: fp->lv[l0+li].fl = (fp->lv[l0+li].fl & 1) | 0x40; break;
1959             }
1960
1961         /* Sort all lumps in the range by their flag values. */
1962
1963         for (li = 1; li < lc; li++)
1964             for (lj = 0; lj < li; lj++)
1965                 if (fp->lv[l0 + li].fl < fp->lv[l0 + lj].fl)
1966                 {
1967                     struct s_lump l;
1968
1969                     l               = fp->lv[l0 + li];
1970                     fp->lv[l0 + li] = fp->lv[l0 + lj];
1971                     fp->lv[l0 + lj] =               l;
1972                 }
1973
1974         /* Establish the in-front, on, and behind lump ranges. */
1975
1976         li = lic = 0;
1977         lj = ljc = 0;
1978         lk = lkc = 0;
1979
1980         for (i = lc - 1; i >= 0; i--)
1981             switch (fp->lv[l0 + i].fl & 0xf0)
1982             {
1983             case 0x10: li = l0 + i; lic++; break;
1984             case 0x20: lj = l0 + i; ljc++; break;
1985             case 0x40: lk = l0 + i; lkc++; break;
1986             }
1987
1988         /* Add the lumps on the side to the node. */
1989
1990         i = incn(fp);
1991
1992         fp->nv[i].si = sj;
1993         fp->nv[i].ni = node_node(fp, li, lic);
1994
1995         fp->nv[i].nj = node_node(fp, lk, lkc);
1996         fp->nv[i].l0 = lj;
1997         fp->nv[i].lc = ljc;
1998
1999         return i;
2000     }
2001 }
2002
2003 static void node_file(struct s_file *fp)
2004 {
2005     int bi;
2006
2007     /* Sort the lumps of each body into BSP nodes. */
2008
2009     for (bi = 0; bi < fp->bc; bi++)
2010         fp->bv[bi].ni = node_node(fp, fp->bv[bi].l0, fp->bv[bi].lc);
2011 }
2012
2013 /*---------------------------------------------------------------------------*/
2014
2015 static void dump_file(struct s_file *p, const char *name)
2016 {
2017     int i, j;
2018     int c = 0;
2019     int n = 0;
2020     int m = p->rc + p->cc * 128 + (p->zc * p->jc + p->xc) * 32;
2021
2022     /* Count the number of solid lumps. */
2023
2024     for (i = 0; i < p->lc; i++)
2025         if ((p->lv[i].fl & 1) == 0)
2026             n++;
2027
2028     /* Count the number of visible geoms. */
2029
2030     for (i = 0; i < p->bc; i++)
2031     {
2032         for (j = 0; j < p->bv[i].lc; j++)
2033             m += p->lv[p->bv[i].l0 + j].gc;
2034         m += p->bv[i].gc;
2035     }
2036
2037     /* Count the total value of all coins. */
2038
2039     for (i = 0; i < p->cc; i++)
2040         c += p->cv[i].n;
2041
2042     printf("%s (%d/%d/$%d)\n"
2043            "  mtrl  vert  edge  side  texc"
2044            "  geom  lump  path  node  body\n"
2045            "%6d%6d%6d%6d%6d%6d%6d%6d%6d%6d\n"
2046            "  coin  goal  view  jump  swch"
2047            "  bill  ball  char  indx\n"
2048            "%6d%6d%6d%6d%6d%6d%6d%6d%6d\n",
2049            name, n, m, c,
2050            p->mc, p->vc, p->ec, p->sc, p->tc,
2051            p->gc, p->lc, p->pc, p->nc, p->bc,
2052            p->cc, p->zc, p->wc, p->jc, p->xc,
2053            p->rc, p->uc, p->ac, p->ic);
2054 }
2055
2056 /* Skip the ugly SDL main substitution */
2057 /* Since we only need sdl_image */
2058 #ifdef main
2059 #    undef main
2060 #endif
2061
2062 int main(int argc, char *argv[])
2063 {
2064     char src[MAXSTR];
2065     char dst[MAXSTR];
2066     struct s_file f;
2067     FILE *fin;
2068
2069     if (argc > 2)
2070     {
2071         if (config_data_path(argv[2], NULL))
2072         {
2073             strncpy(src,  argv[1], MAXSTR);
2074             strncpy(dst,  argv[1], MAXSTR);
2075
2076             if (strcmp(dst + strlen(dst) - 4, ".map") == 0)
2077                 strcpy(dst + strlen(dst) - 4, ".sol");
2078             else
2079                 strcat(dst, ".sol");
2080
2081             if ((fin = fopen(src, "r")))
2082             {
2083                 init_file(&f);
2084                 read_map(&f, fin);
2085
2086                 resolve();
2087                 targets(&f);
2088
2089                 clip_file(&f);
2090                 move_file(&f);
2091                 uniq_file(&f);
2092                 sort_file(&f);
2093                 node_file(&f);
2094                 dump_file(&f, dst);
2095
2096                 sol_stor(&f, dst);
2097
2098                 fclose(fin);
2099             }
2100         }
2101         else fprintf(stderr, "Failure to establish data directory\n");
2102     }
2103     else fprintf(stderr, "Usage: %s <map> [data]\n", argv[0]);
2104
2105     return 0;
2106 }
2107