2 * Copyright (C) 2003 Robert Kooima
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.
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.
15 /*---------------------------------------------------------------------------*/
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")
26 /*---------------------------------------------------------------------------*/
29 #include <SDL_image.h>
38 #include "base_config.h"
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.
53 /*---------------------------------------------------------------------------*/
55 /* Ohhhh... arbitrary! */
78 static int overflow(const char *s)
80 printf("%s overflow\n", s);
85 static int incm(struct s_file *fp)
87 return (fp->mc < MAXM) ? fp->mc++ : overflow("mtrl");
90 static int incv(struct s_file *fp)
92 return (fp->vc < MAXV) ? fp->vc++ : overflow("vert");
95 static int ince(struct s_file *fp)
97 return (fp->ec < MAXE) ? fp->ec++ : overflow("edge");
100 static int incs(struct s_file *fp)
102 return (fp->sc < MAXS) ? fp->sc++ : overflow("side");
105 static int inct(struct s_file *fp)
107 return (fp->tc < MAXT) ? fp->tc++ : overflow("texc");
110 static int incg(struct s_file *fp)
112 return (fp->gc < MAXG) ? fp->gc++ : overflow("geom");
115 static int incl(struct s_file *fp)
117 return (fp->lc < MAXL) ? fp->lc++ : overflow("lump");
120 static int incn(struct s_file *fp)
122 return (fp->nc < MAXN) ? fp->nc++ : overflow("node");
125 static int incp(struct s_file *fp)
127 return (fp->pc < MAXP) ? fp->pc++ : overflow("path");
130 static int incb(struct s_file *fp)
132 return (fp->bc < MAXB) ? fp->bc++ : overflow("body");
135 static int incc(struct s_file *fp)
137 return (fp->cc < MAXC) ? fp->cc++ : overflow("coin");
140 static int incz(struct s_file *fp)
142 return (fp->zc < MAXZ) ? fp->zc++ : overflow("geol");
145 static int incj(struct s_file *fp)
147 return (fp->jc < MAXJ) ? fp->jc++ : overflow("jump");
150 static int incx(struct s_file *fp)
152 return (fp->xc < MAXX) ? fp->xc++ : overflow("swch");
155 static int incr(struct s_file *fp)
157 return (fp->rc < MAXR) ? fp->rc++ : overflow("bill");
160 static int incu(struct s_file *fp)
162 return (fp->uc < MAXU) ? fp->uc++ : overflow("ball");
165 static int incw(struct s_file *fp)
167 return (fp->wc < MAXW) ? fp->wc++ : overflow("view");
170 static int inci(struct s_file *fp)
172 return (fp->ic < MAXI) ? fp->ic++ : overflow("indx");
175 static void init_file(struct s_file *fp)
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));
218 /*---------------------------------------------------------------------------*/
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.
230 static char symv[MAXSYM][MAXSTR];
231 static int valv[MAXSYM];
233 static char refv[MAXSYM][MAXSTR];
234 static int *pntv[MAXSYM];
239 static void make_sym(const char *s, int v)
241 strncpy(symv[strc], s, MAXSTR - 1);
246 static void make_ref(const char *r, int *p)
248 strncpy(refv[refc], r, MAXSTR - 1);
253 static void resolve(void)
257 for (i = 0; i < refc; i++)
258 for (j = 0; j < strc; j++)
259 if (strncmp(refv[i], symv[j], MAXSTR) == 0)
261 *(pntv[i]) = valv[j];
266 /*---------------------------------------------------------------------------*/
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.
273 static float targ_p [MAXW][3];
274 static int targ_wi[MAXW];
275 static int targ_ji[MAXW];
278 static void targets(struct s_file *fp)
282 for (i = 0; i < fp->wc; i++)
283 v_cpy(fp->wv[i].q, targ_p[targ_wi[i]]);
285 for (i = 0; i < fp->jc; i++)
286 v_cpy(fp->jv[i].q, targ_p[targ_ji[i]]);
289 /*---------------------------------------------------------------------------*/
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.
298 static char *image_s[MAXM];
299 static int image_w[MAXM];
300 static int image_h[MAXM];
303 static int size_load(const char *file, int *w, int *h)
307 if ((S = IMG_Load(file)))
319 static void size_image(const char *name, int *w, int *h)
326 for (i = 0; i < image_n; i++)
327 if (strncmp(image_s[i], name, MAXSTR) == 0)
338 strcpy(jpg, name); strcat(jpg, ".jpg");
339 strcpy(tga, name); strcat(tga, ".tga");
340 strcpy(png, name); strcat(png, ".png");
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))
346 image_s[image_n] = (char *) calloc(strlen(name) + 1, 1);
347 image_w[image_n] = *w;
348 image_h[image_n] = *h;
350 strcpy(image_s[image_n], name);
355 /*---------------------------------------------------------------------------*/
357 /* Read the given material file, adding a new material to the solid. */
359 static int read_mtrl(struct s_file *fp, const char *name)
365 for (mi = 0; mi < fp->mc; mi++)
366 if (strncmp(name, fp->mv[mi].f, MAXSTR) == 0)
369 mp = fp->mv + incm(fp);
371 strncpy(mp->f, name, PATHMAX - 1);
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;
380 if ((fin = fopen(config_data(name), "r")))
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,
399 /*---------------------------------------------------------------------------*/
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
409 static void move_side(struct s_side *sp, const float p[3])
411 sp->d -= v_dot(sp->n, p);
414 static void move_vert(struct s_vert *vp, const float p[3])
416 v_sub(vp->p, vp->p, p);
419 static void move_lump(struct s_file *fp,
420 struct s_lump *lp, const float p[3])
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);
430 static void move_body(struct s_file *fp,
435 for (i = 0; i < bp->lc; i++)
436 move_lump(fp, fp->lv + bp->l0 + i, fp->pv[bp->pi].p);
439 static void move_file(struct s_file *fp)
443 for (i = 0; i < fp->bc; i++)
444 if (fp->bv[i].pi >= 0)
445 move_body(fp, fp->bv + i);
448 /*---------------------------------------------------------------------------*/
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.
458 static void read_vt(struct s_file *fp, const char *line)
460 struct s_texc *tp = fp->tv + inct(fp);
462 sscanf(line, "%f %f", tp->u, tp->u + 1);
465 static void read_vn(struct s_file *fp, const char *line)
467 struct s_side *sp = fp->sv + incs(fp);
469 sscanf(line, "%f %f %f", sp->n, sp->n + 1, sp->n + 2);
472 static void read_v(struct s_file *fp, const char *line)
474 struct s_vert *vp = fp->vv + incv(fp);
476 sscanf(line, "%f %f %f", vp->p, vp->p + 1, vp->p + 2);
479 static void read_f(struct s_file *fp, const char *line,
480 int v0, int t0, int s0, int mi)
482 struct s_geom *gp = fp->gv + incg(fp);
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);
505 static void read_obj(struct s_file *fp, const char *name)
516 if ((fin = fopen(config_data(name), "r")))
518 while (fgets(line, MAXSTR, fin))
520 if (strncmp(line, "usemtl", 6) == 0)
522 sscanf(line + 6, "%s", mtrl);
523 mi = read_mtrl(fp, mtrl);
526 else if (strncmp(line, "f", 1) == 0)
528 if (fp->mv[mi].d[3] > 0)
529 read_f(fp, line + 1, v0, t0, s0, mi);
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);
540 /*---------------------------------------------------------------------------*/
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];
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)
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 }},
566 float p0[3], p1[3], p2[3];
567 float u[3], v[3], p[3];
572 size_image(s, &w, &h);
574 plane_f[pi] = fl ? L_DETAIL : 0;
576 p0[0] = +(float) x0 / SCALE;
577 p0[1] = +(float) z0 / SCALE;
578 p0[2] = -(float) y0 / SCALE;
580 p1[0] = +(float) x1 / SCALE;
581 p1[1] = +(float) z1 / SCALE;
582 p1[2] = -(float) y1 / SCALE;
584 p2[0] = +(float) x2 / SCALE;
585 p2[1] = +(float) z2 / SCALE;
586 p2[2] = -(float) y2 / SCALE;
591 v_crs(plane_n[pi], u, v);
592 v_nrm(plane_n[pi], plane_n[pi]);
594 plane_d[pi] = v_dot(plane_n[pi], p1);
596 for (i = 0; i < 6; i++)
597 if ((k = v_dot(plane_n[pi], base[i][0])) >= d)
607 m_rot(R, base[n][0], V_RAD(r));
609 v_mad(p, p, base[n][1], su * tu / SCALE);
610 v_mad(p, p, base[n][2], sv * tv / SCALE);
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);
616 v_scl(plane_u[pi], plane_u[pi], 64.f / w);
617 v_scl(plane_v[pi], plane_v[pi], 64.f / h);
619 v_scl(plane_u[pi], plane_u[pi], 1.f / su);
620 v_scl(plane_v[pi], plane_v[pi], 1.f / sv);
623 /*---------------------------------------------------------------------------*/
632 static int map_token(FILE *fin, int pi, char key[MAXSTR], char val[MAXSTR])
636 if (fgets(buf, MAXSTR, fin))
646 /* Scan the beginning or end of a block. */
648 if (buf[0] == '{') return T_BEG;
649 if (buf[0] == '}') return T_END;
651 /* Scan a key-value pair. */
655 strcpy(key, strtok(buf, "\""));
656 (void) strtok(NULL, "\"");
657 strcpy(val, strtok(NULL, "\""));
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)
674 make_plane(pi, x0, y0, z0,
677 tu, tv, r, su, sv, fl, key);
681 /* If it's not recognized, it must be uninteresting. */
688 /*---------------------------------------------------------------------------*/
690 /* Parse a lump from the given file and add it to the solid. */
692 static void read_lump(struct s_file *fp, FILE *fin)
698 struct s_lump *lp = fp->lv + incl(fp);
702 while ((t = map_token(fin, fp->sc, k, v)))
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];
711 plane_m[fp->sc] = read_mtrl(fp, k);
713 fp->iv[fp->ic] = fp->sc;
723 /*---------------------------------------------------------------------------*/
725 static void make_path(struct s_file *fp,
727 char v[][MAXSTR], int c)
729 int i, pi = incp(fp);
731 struct s_path *pp = fp->pv + pi;
740 for (i = 0; i < c; i++)
742 if (strcmp(k[i], "targetname") == 0)
745 if (strcmp(k[i], "target") == 0)
746 make_ref(v[i], &pp->pi);
748 if (strcmp(k[i], "state") == 0)
751 if (strcmp(k[i], "speed") == 0)
752 sscanf(v[i], "%f", &pp->t);
754 if (strcmp(k[i], "origin") == 0)
756 int x = 0, y = 0, z = 0;
758 sscanf(v[i], "%d %d %d", &x, &y, &z);
760 pp->p[0] = +(float) x / SCALE;
761 pp->p[1] = +(float) z / SCALE;
762 pp->p[2] = -(float) y / SCALE;
767 static void make_body(struct s_file *fp,
769 char v[][MAXSTR], int c, int l0)
771 int i, bi = incb(fp);
782 struct s_body *bp = fp->bv + bi;
788 for (i = 0; i < c; i++)
790 if (strcmp(k[i], "targetname") == 0)
793 if (strcmp(k[i], "target") == 0)
794 make_ref(v[i], &bp->pi);
796 if (strcmp(k[i], "model") == 0)
799 if (strcmp(k[i], "origin") == 0)
800 sscanf(v[i], "%d %d %d", &x, &y, &z);
802 if (strcmp(k[i], "message") == 0)
804 strcpy(fp->av, v[i]);
805 fp->ac = (int) (strlen(v[i]) + 1);
810 bp->lc = fp->lc - l0;
812 bp->gc = fp->gc - g0;
814 for (i = 0; i < bp->gc; i++)
815 fp->iv[inci(fp)] = g0++;
817 p[0] = +(float) x / SCALE;
818 p[1] = +(float) z / SCALE;
819 p[2] = -(float) y / SCALE;
821 for (i = v0; i < fp->vc; i++)
822 v_add(fp->vv[i].p, fp->vv[i].p, p);
825 static void make_coin(struct s_file *fp,
827 char v[][MAXSTR], int c)
829 int i, ci = incc(fp);
831 struct s_coin *cp = fp->cv + ci;
838 for (i = 0; i < c; i++)
840 if (strcmp(k[i], "light") == 0)
841 sscanf(v[i], "%d", &cp->n);
843 if (strcmp(k[i], "origin") == 0)
845 int x = 0, y = 0, z = 0;
847 sscanf(v[i], "%d %d %d", &x, &y, &z);
849 cp->p[0] = +(float) x / SCALE;
850 cp->p[1] = +(float) z / SCALE;
851 cp->p[2] = -(float) y / SCALE;
856 static void make_bill(struct s_file *fp,
858 char v[][MAXSTR], int c)
860 int i, ri = incr(fp);
862 struct s_bill *rp = fp->rv + ri;
864 memset(rp, 0, sizeof (struct s_bill));
867 for (i = 0; i < c; i++)
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);
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);
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);
888 if (strcmp(k[i], "image") == 0)
890 rp->mi = read_mtrl(fp, v[i]);
891 fp->mv[rp->mi].fl |= M_CLAMPED;
894 if (strcmp(k[i], "origin") == 0)
896 int x = 0, y = 0, z = 0;
899 sscanf(v[i], "%d %d %d", &x, &y, &z);
901 p[0] = +(float) x / SCALE;
902 p[1] = +(float) z / SCALE;
903 p[2] = -(float) y / SCALE;
906 rp->rx[0] = V_DEG(fatan2f(+p[1], rp->d));
907 rp->ry[0] = V_DEG(fatan2f(+p[0], -p[2]));
911 if (rp->fl & B_ADDITIVE)
912 fp->mv[rp->mi].fl |= M_ADDITIVE;
915 static void make_goal(struct s_file *fp,
917 char v[][MAXSTR], int c)
919 int i, zi = incz(fp);
921 struct s_goal *zp = fp->zv + zi;
928 for (i = 0; i < c; i++)
930 if (strcmp(k[i], "radius") == 0)
931 sscanf(v[i], "%f", &zp->r);
933 if (strcmp(k[i], "origin") == 0)
935 int x = 0, y = 0, z = 0;
937 sscanf(v[i], "%d %d %d", &x, &y, &z);
939 zp->p[0] = +(float) (x) / SCALE;
940 zp->p[1] = +(float) (z - 24) / SCALE;
941 zp->p[2] = -(float) (y) / SCALE;
946 static void make_view(struct s_file *fp,
948 char v[][MAXSTR], int c)
950 int i, wi = incw(fp);
952 struct s_view *wp = fp->wv + wi;
961 for (i = 0; i < c; i++)
963 if (strcmp(k[i], "target") == 0)
964 make_ref(v[i], targ_wi + wi);
966 if (strcmp(k[i], "origin") == 0)
968 int x = 0, y = 0, z = 0;
970 sscanf(v[i], "%d %d %d", &x, &y, &z);
972 wp->p[0] = +(float) x / SCALE;
973 wp->p[1] = +(float) z / SCALE;
974 wp->p[2] = -(float) y / SCALE;
979 static void make_jump(struct s_file *fp,
981 char v[][MAXSTR], int c)
983 int i, ji = incj(fp);
985 struct s_jump *jp = fp->jv + ji;
995 for (i = 0; i < c; i++)
997 if (strcmp(k[i], "radius") == 0)
998 sscanf(v[i], "%f", &jp->r);
1000 if (strcmp(k[i], "target") == 0)
1001 make_ref(v[i], targ_ji + ji);
1003 if (strcmp(k[i], "origin") == 0)
1005 int x = 0, y = 0, z = 0;
1007 sscanf(v[i], "%d %d %d", &x, &y, &z);
1009 jp->p[0] = +(float) x / SCALE;
1010 jp->p[1] = +(float) z / SCALE;
1011 jp->p[2] = -(float) y / SCALE;
1016 static void make_swch(struct s_file *fp,
1018 char v[][MAXSTR], int c)
1020 int i, xi = incx(fp);
1022 struct s_swch *xp = fp->xv + xi;
1034 for (i = 0; i < c; i++)
1036 if (strcmp(k[i], "radius") == 0)
1037 sscanf(v[i], "%f", &xp->r);
1039 if (strcmp(k[i], "target") == 0)
1040 make_ref(v[i], &xp->pi);
1042 if (strcmp(k[i], "timer") == 0)
1043 sscanf(v[i], "%f", &xp->t0);
1045 if (strcmp(k[i], "state") == 0)
1048 if (strcmp(k[i], "origin") == 0)
1050 int x = 0, y = 0, z = 0;
1052 sscanf(v[i], "%d %d %d", &x, &y, &z);
1054 xp->p[0] = +(float) x / SCALE;
1055 xp->p[1] = +(float) z / SCALE;
1056 xp->p[2] = -(float) y / SCALE;
1061 static void make_targ(struct s_file *fp,
1063 char v[][MAXSTR], int c)
1067 targ_p[targ_n][0] = 0.f;
1068 targ_p[targ_n][1] = 0.f;
1069 targ_p[targ_n][3] = 0.f;
1071 for (i = 0; i < c; i++)
1073 if (strcmp(k[i], "targetname") == 0)
1074 make_sym(v[i], targ_n);
1076 if (strcmp(k[i], "origin") == 0)
1078 int x = 0, y = 0, z = 0;
1080 sscanf(v[i], "%d %d %d", &x, &y, &z);
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;
1091 static void make_ball(struct s_file *fp,
1093 char v[][MAXSTR], int c)
1095 int i, ui = incu(fp);
1097 struct s_ball *up = fp->uv + ui;
1121 for (i = 0; i < c; i++)
1123 if (strcmp(k[i], "radius") == 0)
1124 sscanf(v[i], "%f", &up->r);
1126 if (strcmp(k[i], "origin") == 0)
1128 int x = 0, y = 0, z = 0;
1130 sscanf(v[i], "%d %d %d", &x, &y, &z);
1132 up->p[0] = +(float) (x) / SCALE;
1133 up->p[1] = +(float) (z - 24) / SCALE;
1134 up->p[2] = -(float) (y) / SCALE;
1138 up->p[1] += up->r + SMALL;
1141 /*---------------------------------------------------------------------------*/
1143 static void read_ent(struct s_file *fp, FILE *fin)
1145 char k[MAXKEY][MAXSTR];
1146 char v[MAXKEY][MAXSTR];
1147 int t, i = 0, c = 0;
1151 while ((t = map_token(fin, -1, k[c], v[c])))
1155 if (strcmp(k[c], "classname") == 0)
1159 if (t == T_BEG) read_lump(fp, fin);
1160 if (t == T_END) break;
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);
1177 static void read_map(struct s_file *fp, FILE *fin)
1183 while ((t = map_token(fin, -1, k, v)))
1188 /*---------------------------------------------------------------------------*/
1190 /* Test the location of a point with respect to a side plane. */
1192 static int fore_side(const float p[3], const struct s_side *sp)
1194 return (v_dot(p, sp->n) - sp->d > +SMALL) ? 1 : 0;
1197 static int on_side(const float p[3], const struct s_side *sp)
1199 float d = v_dot(p, sp->n) - sp->d;
1201 return (-SMALL < d && d < +SMALL) ? 1 : 0;
1204 /*---------------------------------------------------------------------------*/
1206 * Confirm that the addition of a vert would not result in degenerate
1210 static int ok_vert(const struct s_file *fp,
1211 const struct s_lump *lp, const float p[3])
1216 for (i = 0; i < lp->vc; i++)
1218 float *q = fp->vv[fp->iv[lp->v0 + i]].p;
1222 if (v_len(r) < SMALL)
1228 /*---------------------------------------------------------------------------*/
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
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.
1245 static void clip_vert(struct s_file *fp,
1246 struct s_lump *lp, int si, int sj, int sk)
1248 float M[16], X[16], I[16];
1252 d[0] = fp->sv[si].d;
1253 d[1] = fp->sv[sj].d;
1254 d[2] = fp->sv[sk].d;
1256 m_basis(M, fp->sv[si].n, fp->sv[sj].n, fp->sv[sk].n);
1263 for (i = 0; i < lp->sc; i++)
1265 int si = fp->iv[lp->s0 + i];
1267 if (fore_side(p, fp->sv + si))
1271 if (ok_vert(fp, lp, p))
1273 v_cpy(fp->vv[fp->vc].p, p);
1275 fp->iv[fp->ic] = fp->vc;
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
1288 static void clip_edge(struct s_file *fp,
1289 struct s_lump *lp, int si, int sj)
1293 for (i = 1; i < lp->vc; i++)
1294 for (j = 0; j < i; j++)
1296 int vi = fp->iv[lp->v0 + i];
1297 int vj = fp->iv[lp->v0 + j];
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))
1304 fp->ev[fp->ec].vi = vi;
1305 fp->ev[fp->ec].vj = vj;
1307 fp->iv[fp->ic] = fp->ec;
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.
1321 static void clip_geom(struct s_file *fp,
1322 struct s_lump *lp, int si)
1324 int m[256], t[256], d, i, j, n = 0;
1329 struct s_side *sp = fp->sv + si;
1333 for (i = 0; i < lp->vc; i++)
1335 int vi = fp->iv[lp->v0 + i];
1337 if (on_side(fp->vv[vi].p, sp))
1342 v_add(v, fp->vv[vi].p, plane_p[si]);
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]);
1353 for (i = 1; i < n; i++)
1354 for (j = i + 1; j < n; j++)
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);
1360 if (v_dot(w, sp->n) < 0.f)
1374 for (i = 0; i < n - 2; i++)
1376 fp->gv[fp->gc].mi = plane_m[si];
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];
1382 fp->gv[fp->gc].si = si;
1383 fp->gv[fp->gc].sj = si;
1384 fp->gv[fp->gc].sk = si;
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];
1390 fp->iv[fp->ic] = fp->gc;
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.
1402 static void clip_lump(struct s_file *fp, struct s_lump *lp)
1409 for (i = 2; i < lp->sc; i++)
1410 for (j = 1; j < i; j++)
1411 for (k = 0; k < j; k++)
1415 fp->iv[lp->s0 + k]);
1420 for (i = 1; i < lp->sc; i++)
1421 for (j = 0; j < i; j++)
1424 fp->iv[lp->s0 + j]);
1429 for (i = 0; i < lp->sc; i++)
1430 if (fp->mv[plane_m[fp->iv[lp->s0 + i]]].d[3] > 0)
1432 fp->iv[lp->s0 + i]);
1434 for (i = 0; i < lp->sc; i++)
1435 if (plane_f[fp->iv[lp->s0 + i]])
1439 static void clip_file(struct s_file *fp)
1443 for (i = 0; i < fp->lc; i++)
1444 clip_lump(fp, fp->lv + i);
1447 /*---------------------------------------------------------------------------*/
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.
1457 static int comp_mtrl(const struct s_mtrl *mp, const struct s_mtrl *mq)
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;
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;
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;
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;
1479 if (fabs(mp->h[0] - mq->h[0]) > SMALL) return 0;
1481 if (strncmp(mp->f, mq->f, PATHMAX)) return 0;
1486 static int comp_vert(const struct s_vert *vp, const struct s_vert *vq)
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;
1495 static int comp_edge(const struct s_edge *ep, const struct s_edge *eq)
1497 if (ep->vi != eq->vi && ep->vi != eq->vj) return 0;
1498 if (ep->vj != eq->vi && ep->vj != eq->vj) return 0;
1503 static int comp_side(const struct s_side *sp, const struct s_side *sq)
1505 if (fabs(sp->d - sq->d) > SMALL) return 0;
1506 if (v_dot(sp->n, sq->n) < 0.9999) return 0;
1511 static int comp_texc(const struct s_texc *tp, const struct s_texc *tq)
1513 if (fabs(tp->u[0] - tq->u[0]) > SMALL) return 0;
1514 if (fabs(tp->u[1] - tq->u[1]) > SMALL) return 0;
1519 static int comp_geom(const struct s_geom *gp, const struct s_geom *gq)
1521 if (gp->mi != gq->mi) return 0;
1523 if (gp->ti != gq->ti) return 0;
1524 if (gp->si != gq->si) return 0;
1525 if (gp->vi != gq->vi) return 0;
1527 if (gp->tj != gq->tj) return 0;
1528 if (gp->sj != gq->sj) return 0;
1529 if (gp->vj != gq->vj) return 0;
1531 if (gp->tk != gq->tk) return 0;
1532 if (gp->sk != gq->sk) return 0;
1533 if (gp->vk != gq->vk) return 0;
1538 /*---------------------------------------------------------------------------*/
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.
1546 static void swap_mtrl(struct s_file *fp, int mi, int mj)
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;
1556 static void swap_vert(struct s_file *fp, int vi, int vj)
1560 for (i = 0; i < fp->ec; i++)
1562 if (fp->ev[i].vi == vi) fp->ev[i].vi = vj;
1563 if (fp->ev[i].vj == vi) fp->ev[i].vj = vj;
1566 for (i = 0; i < fp->gc; i++)
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;
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;
1579 static void swap_edge(struct s_file *fp, int ei, int ej)
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;
1589 static void swap_side(struct s_file *fp, int si, int sj)
1593 for (i = 0; i < fp->gc; i++)
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;
1599 for (i = 0; i < fp->nc; i++)
1600 if (fp->nv[i].si == si) fp->nv[i].si = sj;
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;
1608 static void swap_texc(struct s_file *fp, int ti, int tj)
1612 for (i = 0; i < fp->gc; i++)
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;
1621 static void swap_geom(struct s_file *fp, int gi, int gj)
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;
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;
1636 /*---------------------------------------------------------------------------*/
1638 static void uniq_mtrl(struct s_file *fp)
1642 for (i = 0; i < fp->mc; i++)
1644 for (j = 0; j < k; j++)
1645 if (comp_mtrl(fp->mv + i, fp->mv + j))
1647 swap_mtrl(fp, i, j);
1655 fp->mv[k] = fp->mv[i];
1656 swap_mtrl(fp, i, k);
1665 static void uniq_vert(struct s_file *fp)
1669 for (i = 0; i < fp->vc; i++)
1671 for (j = 0; j < k; j++)
1672 if (comp_vert(fp->vv + i, fp->vv + j))
1674 swap_vert(fp, i, j);
1682 fp->vv[k] = fp->vv[i];
1683 swap_vert(fp, i, k);
1692 static void uniq_edge(struct s_file *fp)
1696 for (i = 0; i < fp->ec; i++)
1698 for (j = 0; j < k; j++)
1699 if (comp_edge(fp->ev + i, fp->ev + j))
1701 swap_edge(fp, i, j);
1709 fp->ev[k] = fp->ev[i];
1710 swap_edge(fp, i, k);
1719 static void uniq_geom(struct s_file *fp)
1723 for (i = 0; i < fp->gc; i++)
1725 for (j = 0; j < k; j++)
1726 if (comp_geom(fp->gv + i, fp->gv + j))
1728 swap_geom(fp, i, j);
1736 fp->gv[k] = fp->gv[i];
1737 swap_geom(fp, i, k);
1746 static void uniq_texc(struct s_file *fp)
1750 for (i = 0; i < fp->tc; i++)
1752 for (j = 0; j < k; j++)
1753 if (comp_texc(fp->tv + i, fp->tv + j))
1755 swap_texc(fp, i, j);
1763 fp->tv[k] = fp->tv[i];
1764 swap_texc(fp, i, k);
1773 static void uniq_side(struct s_file *fp)
1777 for (i = 0; i < fp->sc; i++)
1779 for (j = 0; j < k; j++)
1780 if (comp_side(fp->sv + i, fp->sv + j))
1782 swap_side(fp, i, j);
1790 fp->sv[k] = fp->sv[i];
1791 swap_side(fp, i, k);
1800 static void uniq_file(struct s_file *fp)
1810 /*---------------------------------------------------------------------------*/
1812 static void sort_file(struct s_file *fp)
1816 /* Sort billboards farthest to nearest. */
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)
1825 fp->rv[i] = fp->rv[j];
1829 /* Ensure the first vertex is the lowest. */
1831 for (i = 0; i < fp->vc; i++)
1832 if (fp->vv[0].p[1] > fp->vv[i].p[1])
1837 fp->vv[0] = fp->vv[i];
1840 swap_vert(fp, 0, -1);
1841 swap_vert(fp, i, 0);
1842 swap_vert(fp, -1, i);
1846 /*---------------------------------------------------------------------------*/
1848 static int test_lump_side(const struct s_file *fp,
1849 const struct s_lump *lp,
1850 const struct s_side *sp)
1858 /* If the given side is part of the given lump, then the lump is behind. */
1860 for (si = 0; si < lp->sc; si++)
1861 if (fp->sv + fp->iv[lp->s0 + si] == sp)
1864 /* Check if each lump vertex is in front of, behind, on the side. */
1866 for (vi = 0; vi < lp->vc; vi++)
1868 float d = v_dot(fp->vv[fp->iv[lp->v0 + vi]].p, sp->n) - sp->d;
1874 /* If no verts are behind, the lump is in front, and vice versa. */
1876 if (f > 0 && b == 0) return +1;
1877 if (b > 0 && f == 0) return -1;
1879 /* Else, the lump crosses the side. */
1884 static int node_node(struct s_file *fp, int l0, int lc)
1888 /* Base case. Dump all given lumps into a leaf node. */
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;
1904 int li = 0, lic = 0;
1905 int lj = 0, ljc = 0;
1906 int lk = 0, lkc = 0;
1909 /* Find the side that most evenly splits the given lumps. */
1911 for (si = 0; si < fp->sc; si++)
1917 for (li = 0; li < lc; li++)
1918 if ((k = test_lump_side(fp, fp->lv + l0 + li, fp->sv + si)))
1925 if ((d < sjd) || (d == sjd && o < sjo))
1933 /* Flag each lump with its position WRT the side. */
1935 for (li = 0; li < lc; li++)
1936 switch (test_lump_side(fp, fp->lv + l0 + li, fp->sv + sj))
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;
1943 /* Sort all lumps in the range by their flag values. */
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)
1951 l = fp->lv[l0 + li];
1952 fp->lv[l0 + li] = fp->lv[l0 + lj];
1953 fp->lv[l0 + lj] = l;
1956 /* Establish the in-front, on, and behind lump ranges. */
1962 for (i = lc - 1; i >= 0; i--)
1963 switch (fp->lv[l0 + i].fl & 0xf0)
1965 case 0x10: li = l0 + i; lic++; break;
1966 case 0x20: lj = l0 + i; ljc++; break;
1967 case 0x40: lk = l0 + i; lkc++; break;
1970 /* Add the lumps on the side to the node. */
1975 fp->nv[i].ni = node_node(fp, li, lic);
1977 fp->nv[i].nj = node_node(fp, lk, lkc);
1985 static void node_file(struct s_file *fp)
1989 /* Sort the lumps of each body into BSP nodes. */
1991 for (bi = 0; bi < fp->bc; bi++)
1992 fp->bv[bi].ni = node_node(fp, fp->bv[bi].l0, fp->bv[bi].lc);
1995 /*---------------------------------------------------------------------------*/
1997 static void dump_file(struct s_file *p, const char *name)
2002 int m = p->rc + p->cc * 128 + (p->zc * p->jc + p->xc) * 32;
2004 /* Count the number of solid lumps. */
2006 for (i = 0; i < p->lc; i++)
2007 if ((p->lv[i].fl & 1) == 0)
2010 /* Count the number of visible geoms. */
2012 for (i = 0; i < p->bc; i++)
2014 for (j = 0; j < p->bv[i].lc; j++)
2015 m += p->lv[p->bv[i].l0 + j].gc;
2019 /* Count the total value of all coins. */
2021 for (i = 0; i < p->cc; i++)
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",
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);
2038 int main(int argc, char *argv[])
2047 if (config_data_path(argv[2], NULL))
2049 strncpy(src, argv[1], MAXSTR);
2050 strncpy(dst, argv[1], MAXSTR);
2052 if (strcmp(dst + strlen(dst) - 4, ".map") == 0)
2053 strcpy(dst + strlen(dst) - 4, ".sol");
2055 strcat(dst, ".sol");
2057 if ((fin = fopen(src, "r")))
2077 else fprintf(stderr, "Failure to establish data directory\n");
2079 else fprintf(stderr, "Usage: %s <map> [data]\n", argv[0]);