From 879478749c2f426394d3d995ee6c079b3d9394e8 Mon Sep 17 00:00:00 2001 From: John Tsiombikas Date: Wed, 4 Mar 2020 17:06:48 +0200 Subject: [PATCH] broguht over the 3D pipeline from the demo --- GNUmakefile | 4 +- Makefile | 19 +- src/3dgfx/3dgfx.c | 748 ++++++++++++++++++++++++++++++++++++++++++++++++++ src/3dgfx/3dgfx.h | 141 ++++++++++ src/3dgfx/mesh.c | 524 +++++++++++++++++++++++++++++++++++ src/3dgfx/mesh.h | 35 +++ src/3dgfx/meshload.c | 354 ++++++++++++++++++++++++ src/3dgfx/polyclip.c | 331 ++++++++++++++++++++++ src/3dgfx/polyclip.h | 38 +++ src/3dgfx/polyfill.c | 179 ++++++++++++ src/3dgfx/polyfill.h | 62 +++++ src/3dgfx/polytmpl.h | 345 +++++++++++++++++++++++ src/dynarr.c | 140 ++++++++++ src/dynarr.h | 80 ++++++ src/rbtree.c | 503 +++++++++++++++++++++++++++++++++ src/rbtree.h | 78 ++++++ 16 files changed, 3573 insertions(+), 8 deletions(-) create mode 100644 src/3dgfx/3dgfx.c create mode 100644 src/3dgfx/3dgfx.h create mode 100644 src/3dgfx/mesh.c create mode 100644 src/3dgfx/mesh.h create mode 100644 src/3dgfx/meshload.c create mode 100644 src/3dgfx/polyclip.c create mode 100644 src/3dgfx/polyclip.h create mode 100644 src/3dgfx/polyfill.c create mode 100644 src/3dgfx/polyfill.h create mode 100644 src/3dgfx/polytmpl.h create mode 100644 src/dynarr.c create mode 100644 src/dynarr.h create mode 100644 src/rbtree.c create mode 100644 src/rbtree.h diff --git a/GNUmakefile b/GNUmakefile index 6bc3c69..ccb0eb2 100644 --- a/GNUmakefile +++ b/GNUmakefile @@ -1,10 +1,10 @@ -csrc = $(wildcard src/*.c) $(wildcard src/sdl/*.c) +csrc = $(wildcard src/*.c) $(wildcard src/sdl/*.c) $(wildcard src/3dgfx/*.c) obj = $(csrc:.c=.o) dep = $(obj:.o=.d) bin = game -inc = -Isrc -Isrc/sdl +inc = -Isrc -Isrc/sdl -Isrc/3dgfx CFLAGS = $(arch) -pedantic -Wall -g -MMD $(inc) `sdl-config --cflags` LDFLAGS = $(arch) -Llibs/imago -limago `sdl-config --libs` -lm diff --git a/Makefile b/Makefile index c8ed0d2..b7ef6e3 100644 --- a/Makefile +++ b/Makefile @@ -2,26 +2,33 @@ dosobj = src/dos/main.obj src/dos/gfx.obj src/dos/timer.obj src/dos/watdpmi.obj & src/dos/vbe.obj src/dos/vga.obj src/dos/keyb.obj src/dos/mouse.obj & src/dos/logger.obj -gameobj = src/game.obj src/util.obj src/gfxutil.obj src/menuscr.obj +gameobj = src/game.obj src/util.obj src/gfxutil.obj src/dynarr.obj src/rbtree.obj & + src/menuscr.obj +gfxobj = src/3dgfx/3dgfx.obj src/3dgfx/mesh.obj src/3dgfx/meshload.obj & + src/3dgfx/polyfill.obj src/3dgfx/polyclip.obj incpath = -Isrc -Isrc/dos -Ilibs/imago/src libpath = libpath libs/imago !else dosobj = src\dos\main.obj src\dos\gfx.obj src\dos\timer.obj src\dos\watdpmi.obj & src\dos\vbe.obj src\dos\vga.obj src\dos\keyb.obj src\dos\mouse.obj & src\dos\logger.obj -gameobj = src\game.obj src\util.obj src\gfxutil.obj src\menuscr.obj +gameobj = src\game.obj src\util.obj src\gfxutil.obj src\dynarr.obj src\rbtree.obj & + src\menuscr.obj +gfxobj = src\3dgfx\3dgfx.obj src\3dgfx\mesh.obj src\3dgfx\meshload.obj & + src\3dgfx\polyfill.obj src\3dgfx\polyclip.obj incpath = -Isrc -Isrc\dos -Ilibs\imago\src libpath = libpath libs\imago !endif -obj = $(dosobj) $(gameobj) +obj = $(dosobj) $(gameobj) $(gfxobj) bin = game.exe +def = -dM_PI=3.141592653589793 libs = imago.lib CC = wcc386 LD = wlink -CFLAGS = -d3 -5 -fp5 -otebmileran -s -zq -bt=dos $(incpath) +CFLAGS = -d3 -5 -fp5 -otebmileran $(def) -s -zq -bt=dos $(incpath) LDFLAGS = option map $(libpath) library { $(libs) } $(bin): $(obj) @@ -29,8 +36,8 @@ $(bin): $(obj) %write ldflags.lnk $(LDFLAGS) $(LD) debug all name $@ system dos4g file { @objects } @ldflags -.c: src;src/dos -.asm: src;src/dos +.c: src;src/dos;src/3dgfx +.asm: src;src/dos;src/3dgfx .c.obj: .autodepend $(CC) -fo=$@ $(CFLAGS) $[* diff --git a/src/3dgfx/3dgfx.c b/src/3dgfx/3dgfx.c new file mode 100644 index 0000000..dd6e7f8 --- /dev/null +++ b/src/3dgfx/3dgfx.c @@ -0,0 +1,748 @@ +#include +#include +#include +#include +#include +#if defined(__WATCOMC__) || defined(_MSC_VER) || defined(__DJGPP__) +#include +#else +#include +#endif +#include "3dgfx.h" +#include "gfxutil.h" +#include "polyfill.h" +#include "polyclip.h" +#include "inttypes.h" +#include "game.h" +#include "util.h" + +#define STACK_SIZE 8 +typedef float g3d_matrix[16]; + +#define MAX_LIGHTS 4 + +#define IMM_VBUF_SIZE 256 + +#define NORMALIZE(v) \ + do { \ + float len = sqrt((v)[0] * (v)[0] + (v)[1] * (v)[1] + (v)[2] * (v)[2]); \ + if(len != 0.0) { \ + float s = 1.0 / len; \ + (v)[0] *= s; \ + (v)[1] *= s; \ + (v)[2] *= s; \ + } \ + } while(0) + +enum {LT_POS, LT_DIR}; +struct light { + int type; + float x, y, z; + float r, g, b; +}; + +struct material { + float kd[3]; + float ks[3]; + float shin; +}; + +struct g3d_state { + unsigned int opt; + int frontface; + int polymode; + + g3d_matrix mat[G3D_NUM_MATRICES][STACK_SIZE]; + int mtop[G3D_NUM_MATRICES]; + int mmode; + + g3d_matrix norm_mat; + + float ambient[3]; + struct light lt[MAX_LIGHTS]; + struct material mtl; + + int width, height; + g3d_pixel *pixels; + + int vport[4]; + + /* immediate mode */ + int imm_prim; + int imm_numv, imm_pcount; + struct g3d_vertex imm_curv; + struct g3d_vertex imm_vbuf[IMM_VBUF_SIZE]; +}; + +static void imm_flush(void); +static __inline void xform4_vec3(const float *mat, float *vec); +static __inline void xform3_vec3(const float *mat, float *vec); +static void shade(struct g3d_vertex *v); + +static struct g3d_state *st; +static const float idmat[] = { + 1, 0, 0, 0, + 0, 1, 0, 0, + 0, 0, 1, 0, + 0, 0, 0, 1 +}; + +int g3d_init(void) +{ + int i; + + if(!(st = calloc(1, sizeof *st))) { + fprintf(stderr, "failed to allocate G3D context\n"); + return -1; + } + st->opt = G3D_CLIP_FRUSTUM; + st->polymode = POLYFILL_FLAT; + + for(i=0; iwidth = width; + st->height = height; + st->pixels = pixels; + + pfill_fb.pixels = pixels; + pfill_fb.width = width; + pfill_fb.height = height; + + g3d_viewport(0, 0, width, height); +} + +/* set the framebuffer pointer, without resetting the size */ +void g3d_framebuffer_addr(void *pixels) +{ + st->pixels = pixels; + pfill_fb.pixels = pixels; +} + +void g3d_viewport(int x, int y, int w, int h) +{ + st->vport[0] = x; + st->vport[1] = y; + st->vport[2] = w; + st->vport[3] = h; +} + +void g3d_enable(unsigned int opt) +{ + st->opt |= opt; +} + +void g3d_disable(unsigned int opt) +{ + st->opt &= ~opt; +} + +void g3d_setopt(unsigned int opt, unsigned int mask) +{ + st->opt = (st->opt & ~mask) | (opt & mask); +} + +unsigned int g3d_getopt(unsigned int mask) +{ + return st->opt & mask; +} + +void g3d_front_face(unsigned int order) +{ + st->frontface = order; +} + +void g3d_polygon_mode(int pmode) +{ + st->polymode = pmode; +} + +void g3d_matrix_mode(int mmode) +{ + st->mmode = mmode; +} + +void g3d_load_identity(void) +{ + int top = st->mtop[st->mmode]; + memcpy(st->mat[st->mmode][top], idmat, 16 * sizeof(float)); +} + +void g3d_load_matrix(const float *m) +{ + int top = st->mtop[st->mmode]; + memcpy(st->mat[st->mmode][top], m, 16 * sizeof(float)); +} + +#define M(i,j) (((i) << 2) + (j)) +void g3d_mult_matrix(const float *m2) +{ + int i, j, top = st->mtop[st->mmode]; + float m1[16]; + float *dest = st->mat[st->mmode][top]; + + memcpy(m1, dest, sizeof m1); + + for(i=0; i<4; i++) { + for(j=0; j<4; j++) { + *dest++ = m1[M(0,j)] * m2[M(i,0)] + + m1[M(1,j)] * m2[M(i,1)] + + m1[M(2,j)] * m2[M(i,2)] + + m1[M(3,j)] * m2[M(i,3)]; + } + } +} + +void g3d_push_matrix(void) +{ + int top = st->mtop[st->mmode]; + if(top >= G3D_NUM_MATRICES) { + fprintf(stderr, "g3d_push_matrix overflow\n"); + return; + } + memcpy(st->mat[st->mmode][top + 1], st->mat[st->mmode][top], 16 * sizeof(float)); + st->mtop[st->mmode] = top + 1; +} + +void g3d_pop_matrix(void) +{ + if(st->mtop[st->mmode] <= 0) { + fprintf(stderr, "g3d_pop_matrix underflow\n"); + return; + } + --st->mtop[st->mmode]; +} + +void g3d_translate(float x, float y, float z) +{ + float m[] = {1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1}; + m[12] = x; + m[13] = y; + m[14] = z; + g3d_mult_matrix(m); +} + +void g3d_rotate(float deg, float x, float y, float z) +{ + float m[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; + + float angle = M_PI * deg / 180.0f; + float sina = sin(angle); + float cosa = cos(angle); + float one_minus_cosa = 1.0f - cosa; + float nxsq = x * x; + float nysq = y * y; + float nzsq = z * z; + + m[0] = nxsq + (1.0f - nxsq) * cosa; + m[4] = x * y * one_minus_cosa - z * sina; + m[8] = x * z * one_minus_cosa + y * sina; + m[1] = x * y * one_minus_cosa + z * sina; + m[5] = nysq + (1.0 - nysq) * cosa; + m[9] = y * z * one_minus_cosa - x * sina; + m[2] = x * z * one_minus_cosa - y * sina; + m[6] = y * z * one_minus_cosa + x * sina; + m[10] = nzsq + (1.0 - nzsq) * cosa; + m[15] = 1.0f; + + g3d_mult_matrix(m); +} + +void g3d_scale(float x, float y, float z) +{ + float m[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; + m[0] = x; + m[5] = y; + m[10] = z; + m[15] = 1.0f; + g3d_mult_matrix(m); +} + +void g3d_ortho(float left, float right, float bottom, float top, float znear, float zfar) +{ + float m[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; + + float dx = right - left; + float dy = top - bottom; + float dz = zfar - znear; + + m[0] = 2.0 / dx; + m[5] = 2.0 / dy; + m[10] = -2.0 / dz; + m[12] = -(right + left) / dx; + m[13] = -(top + bottom) / dy; + m[14] = -(zfar + znear) / dz; + + g3d_mult_matrix(m); +} + +void g3d_frustum(float left, float right, float bottom, float top, float nr, float fr) +{ + float m[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; + + float dx = right - left; + float dy = top - bottom; + float dz = fr - nr; + + float a = (right + left) / dx; + float b = (top + bottom) / dy; + float c = -(fr + nr) / dz; + float d = -2.0 * fr * nr / dz; + + m[0] = 2.0 * nr / dx; + m[5] = 2.0 * nr / dy; + m[8] = a; + m[9] = b; + m[10] = c; + m[11] = -1.0f; + m[14] = d; + + g3d_mult_matrix(m); +} + +void g3d_perspective(float vfov_deg, float aspect, float znear, float zfar) +{ + float m[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; + + float vfov = M_PI * vfov_deg / 180.0f; + float s = 1.0f / tan(vfov * 0.5f); + float range = znear - zfar; + + m[0] = s / aspect; + m[5] = s; + m[10] = (znear + zfar) / range; + m[11] = -1.0f; + m[14] = 2.0f * znear * zfar / range; + + g3d_mult_matrix(m); +} + +const float *g3d_get_matrix(int which, float *m) +{ + int top = st->mtop[which]; + + if(m) { + memcpy(m, st->mat[which][top], 16 * sizeof(float)); + } + return st->mat[which][top]; +} + +void g3d_light_pos(int idx, float x, float y, float z) +{ + int mvtop = st->mtop[G3D_MODELVIEW]; + + st->lt[idx].type = LT_POS; + st->lt[idx].x = x; + st->lt[idx].y = y; + st->lt[idx].z = z; + + xform4_vec3(st->mat[G3D_MODELVIEW][mvtop], &st->lt[idx].x); +} + +void g3d_light_dir(int idx, float x, float y, float z) +{ + int mvtop = st->mtop[G3D_MODELVIEW]; + + st->lt[idx].type = LT_DIR; + st->lt[idx].x = x; + st->lt[idx].y = y; + st->lt[idx].z = z; + + /* calc the normal matrix */ + memcpy(st->norm_mat, st->mat[G3D_MODELVIEW][mvtop], 16 * sizeof(float)); + st->norm_mat[12] = st->norm_mat[13] = st->norm_mat[14] = 0.0f; + + xform4_vec3(st->norm_mat, &st->lt[idx].x); + + NORMALIZE(&st->lt[idx].x); +} + +void g3d_light_color(int idx, float r, float g, float b) +{ + st->lt[idx].r = r; + st->lt[idx].g = g; + st->lt[idx].b = b; +} + +void g3d_light_ambient(float r, float g, float b) +{ + st->ambient[0] = r; + st->ambient[1] = g; + st->ambient[2] = b; +} + +void g3d_mtl_diffuse(float r, float g, float b) +{ + st->mtl.kd[0] = r; + st->mtl.kd[1] = g; + st->mtl.kd[2] = b; +} + +void g3d_mtl_specular(float r, float g, float b) +{ + st->mtl.ks[0] = r; + st->mtl.ks[1] = g; + st->mtl.ks[2] = b; +} + +void g3d_mtl_shininess(float shin) +{ + st->mtl.shin = shin; +} + +static INLINE int calc_shift(unsigned int x) +{ + int res = -1; + while(x) { + x >>= 1; + ++res; + } + return res; +} + +static INLINE int calc_mask(unsigned int x) +{ + return x - 1; +} + +void g3d_set_texture(int xsz, int ysz, void *pixels) +{ + pfill_tex.pixels = pixels; + pfill_tex.width = xsz; + pfill_tex.height = ysz; + + pfill_tex.xshift = calc_shift(xsz); + pfill_tex.yshift = calc_shift(ysz); + pfill_tex.xmask = calc_mask(xsz); + pfill_tex.ymask = calc_mask(ysz); +} + +void g3d_draw(int prim, const struct g3d_vertex *varr, int varr_size) +{ + g3d_draw_indexed(prim, varr, varr_size, 0, 0); +} + +void g3d_draw_indexed(int prim, const struct g3d_vertex *varr, int varr_size, + const uint16_t *iarr, int iarr_size) +{ + int i, j, vnum, nfaces, fill_mode; + struct pvertex pv[16]; + struct g3d_vertex v[16]; + int mvtop = st->mtop[G3D_MODELVIEW]; + int ptop = st->mtop[G3D_PROJECTION]; + struct g3d_vertex *tmpv; + + tmpv = alloca(prim * 6 * sizeof *tmpv); + + /* calc the normal matrix */ + memcpy(st->norm_mat, st->mat[G3D_MODELVIEW][mvtop], 16 * sizeof(float)); + st->norm_mat[12] = st->norm_mat[13] = st->norm_mat[14] = 0.0f; + + nfaces = (iarr ? iarr_size : varr_size) / prim; + + for(j=0; jmat[G3D_MODELVIEW][mvtop], &v[i].x); + xform3_vec3(st->norm_mat, &v[i].nx); + + if(st->opt & G3D_LIGHTING) { + shade(v + i); + } + if(st->opt & G3D_TEXTURE_GEN) { + v[i].u = v[i].nx * 0.5 + 0.5; + v[i].v = v[i].ny * 0.5 + 0.5; + } + if(st->opt & G3D_TEXTURE_MAT) { + float *mat = st->mat[G3D_TEXTURE][st->mtop[G3D_TEXTURE]]; + float x = mat[0] * v[i].u + mat[4] * v[i].v + mat[12]; + float y = mat[1] * v[i].u + mat[5] * v[i].v + mat[13]; + float w = mat[3] * v[i].u + mat[7] * v[i].v + mat[15]; + v[i].u = x / w; + v[i].v = y / w; + } + xform4_vec3(st->mat[G3D_PROJECTION][ptop], &v[i].x); + } + + /* clipping */ + if(st->opt & G3D_CLIP_FRUSTUM) { + for(i=0; i<6; i++) { + memcpy(tmpv, v, vnum * sizeof *v); + + if(clip_frustum(v, &vnum, tmpv, vnum, i) < 0) { + /* polygon completely outside of view volume. discard */ + vnum = 0; + break; + } + } + + if(!vnum) continue; + } + + for(i=0; ivport[2] + st->vport[0]; + v[i].y = (0.5f - v[i].y * 0.5f) * (float)st->vport[3] + st->vport[1]; + + /* convert pos to 24.8 fixed point */ + pv[i].x = cround64(v[i].x * 256.0f); + pv[i].y = cround64(v[i].y * 256.0f); + /* convert tex coords to 16.16 fixed point */ + pv[i].u = cround64(v[i].u * 65536.0f); + pv[i].v = cround64(v[i].v * 65536.0f); + /* pass the color through as is */ + pv[i].r = v[i].r; + pv[i].g = v[i].g; + pv[i].b = v[i].b; + pv[i].a = v[i].a; + } + + /* backface culling */ + if(vnum > 2 && st->opt & G3D_CULL_FACE) { + int32_t ax = pv[1].x - pv[0].x; + int32_t ay = pv[1].y - pv[0].y; + int32_t bx = pv[2].x - pv[0].x; + int32_t by = pv[2].y - pv[0].y; + int32_t cross_z = (ax >> 4) * (by >> 4) - (ay >> 4) * (bx >> 4); + int sign = (cross_z >> 31) & 1; + + if(!(sign ^ st->frontface)) { + continue; /* back-facing */ + } + } + + switch(vnum) { + case 1: + if(st->opt & G3D_BLEND) { + int r, g, b; + int inv_alpha = 255 - pv[0].a; + g3d_pixel *dest = st->pixels + (pv[0].y >> 8) * st->width + (pv[0].x >> 8); + r = ((int)pv[0].r * pv[0].a + G3D_UNPACK_R(*dest) * inv_alpha) >> 8; + g = ((int)pv[0].g * pv[0].a + G3D_UNPACK_G(*dest) * inv_alpha) >> 8; + b = ((int)pv[0].b * pv[0].a + G3D_UNPACK_B(*dest) * inv_alpha) >> 8; + *dest++ = G3D_PACK_RGB(r, g, b); + } else { + g3d_pixel *dest = st->pixels + (pv[0].y >> 8) * st->width + (pv[0].x >> 8); + *dest = G3D_PACK_RGB(pv[0].r, pv[0].g, pv[0].b); + } + break; + + case 2: + { + g3d_pixel col = G3D_PACK_RGB(pv[0].r, pv[0].g, pv[0].b); + draw_line(pv[0].x >> 8, pv[0].y >> 8, pv[1].x >> 8, pv[1].y >> 8, col); + } + break; + + default: + fill_mode = st->polymode; + if(st->opt & G3D_TEXTURE_2D) { + fill_mode |= POLYFILL_TEX_BIT; + } + if(st->opt & G3D_BLEND) { + fill_mode |= POLYFILL_BLEND_BIT; + } + polyfill(fill_mode, pv, vnum); + } + } +} + +void g3d_begin(int prim) +{ + st->imm_prim = prim; + st->imm_pcount = prim; + st->imm_numv = 0; +} + +void g3d_end(void) +{ + imm_flush(); +} + +static void imm_flush(void) +{ + int numv = st->imm_numv; + st->imm_numv = 0; + g3d_draw_indexed(st->imm_prim, st->imm_vbuf, numv, 0, 0); +} + +void g3d_vertex(float x, float y, float z) +{ + struct g3d_vertex *vptr = st->imm_vbuf + st->imm_numv++; + *vptr = st->imm_curv; + vptr->x = x; + vptr->y = y; + vptr->z = z; + vptr->w = 1.0f; + + if(!--st->imm_pcount) { + if(st->imm_numv >= IMM_VBUF_SIZE - st->imm_prim) { + imm_flush(); + } + st->imm_pcount = st->imm_prim; + } +} + +void g3d_normal(float x, float y, float z) +{ + st->imm_curv.nx = x; + st->imm_curv.ny = y; + st->imm_curv.nz = z; +} + +#define CLAMP(x, a, b) ((x) < (a) ? (a) : ((x) > (b) ? (b) : (x))) +#define MIN(a, b) ((a) < (b) ? (a) : (b)) + +void g3d_color3b(unsigned char r, unsigned char g, unsigned char b) +{ + st->imm_curv.r = MIN(r, 255); + st->imm_curv.g = MIN(g, 255); + st->imm_curv.b = MIN(b, 255); + st->imm_curv.a = 255; +} + +void g3d_color4b(unsigned char r, unsigned char g, unsigned char b, unsigned char a) +{ + st->imm_curv.r = MIN(r, 255); + st->imm_curv.g = MIN(g, 255); + st->imm_curv.b = MIN(b, 255); + st->imm_curv.a = MIN(a, 255); +} + +void g3d_color3f(float r, float g, float b) +{ + int ir = r * 255.0f; + int ig = g * 255.0f; + int ib = b * 255.0f; + st->imm_curv.r = CLAMP(ir, 0, 255); + st->imm_curv.g = CLAMP(ig, 0, 255); + st->imm_curv.b = CLAMP(ib, 0, 255); + st->imm_curv.a = 255; +} + +void g3d_color4f(float r, float g, float b, float a) +{ + int ir = r * 255.0f; + int ig = g * 255.0f; + int ib = b * 255.0f; + int ia = a * 255.0f; + st->imm_curv.r = CLAMP(ir, 0, 255); + st->imm_curv.g = CLAMP(ig, 0, 255); + st->imm_curv.b = CLAMP(ib, 0, 255); + st->imm_curv.a = CLAMP(ia, 0, 255); +} + +void g3d_texcoord(float u, float v) +{ + st->imm_curv.u = u; + st->imm_curv.v = v; +} + +static __inline void xform4_vec3(const float *mat, float *vec) +{ + float x = mat[0] * vec[0] + mat[4] * vec[1] + mat[8] * vec[2] + mat[12]; + float y = mat[1] * vec[0] + mat[5] * vec[1] + mat[9] * vec[2] + mat[13]; + float z = mat[2] * vec[0] + mat[6] * vec[1] + mat[10] * vec[2] + mat[14]; + vec[3] = mat[3] * vec[0] + mat[7] * vec[1] + mat[11] * vec[2] + mat[15]; + vec[2] = z; + vec[1] = y; + vec[0] = x; +} + +static __inline void xform3_vec3(const float *mat, float *vec) +{ + float x = mat[0] * vec[0] + mat[4] * vec[1] + mat[8] * vec[2]; + float y = mat[1] * vec[0] + mat[5] * vec[1] + mat[9] * vec[2]; + vec[2] = mat[2] * vec[0] + mat[6] * vec[1] + mat[10] * vec[2]; + vec[1] = y; + vec[0] = x; +} + +static void shade(struct g3d_vertex *v) +{ + int i, r, g, b; + float color[3]; + + color[0] = st->ambient[0] * st->mtl.kd[0]; + color[1] = st->ambient[1] * st->mtl.kd[1]; + color[2] = st->ambient[2] * st->mtl.kd[2]; + + for(i=0; iopt & (G3D_LIGHT0 << i))) { + continue; + } + + ldir[0] = st->lt[i].x; + ldir[1] = st->lt[i].y; + ldir[2] = st->lt[i].z; + + if(st->lt[i].type != LT_DIR) { + ldir[0] -= v->x; + ldir[1] -= v->y; + ldir[2] -= v->z; + NORMALIZE(ldir); + } + + if((ndotl = v->nx * ldir[0] + v->ny * ldir[1] + v->nz * ldir[2]) < 0.0f) { + ndotl = 0.0f; + } + + color[0] += st->mtl.kd[0] * st->lt[i].r * ndotl; + color[1] += st->mtl.kd[1] * st->lt[i].g * ndotl; + color[2] += st->mtl.kd[2] * st->lt[i].b * ndotl; + + /* + if(st->opt & G3D_SPECULAR) { + float ndoth; + ldir[2] += 1.0f; + NORMALIZE(ldir); + if((ndoth = v->nx * ldir[0] + v->ny * ldir[1] + v->nz * ldir[2]) < 0.0f) { + ndoth = 0.0f; + } + ndoth = pow(ndoth, st->mtl.shin); + + color[0] += st->mtl.ks[0] * st->lt[i].r * ndoth; + color[1] += st->mtl.ks[1] * st->lt[i].g * ndoth; + color[2] += st->mtl.ks[2] * st->lt[i].b * ndoth; + } + */ + } + + r = cround64(color[0] * 255.0); + g = cround64(color[1] * 255.0); + b = cround64(color[2] * 255.0); + + v->r = r > 255 ? 255 : r; + v->g = g > 255 ? 255 : g; + v->b = b > 255 ? 255 : b; +} diff --git a/src/3dgfx/3dgfx.h b/src/3dgfx/3dgfx.h new file mode 100644 index 0000000..f6250d5 --- /dev/null +++ b/src/3dgfx/3dgfx.h @@ -0,0 +1,141 @@ +#ifndef THREEDGFX_H_ +#define THREEDGFX_H_ + +#include "inttypes.h" +#include "gfxutil.h" + +#define G3D_PIXFMT16 +typedef uint16_t g3d_pixel; + +#ifdef G3D_PIXFMT16 +#define G3D_PACK_RGB(r, g, b) PACK_RGB16(r, g, b) +#define G3D_UNPACK_R(c) UNPACK_R16(c) +#define G3D_UNPACK_G(c) UNPACK_G16(c) +#define G3D_UNPACK_B(c) UNPACK_B16(c) +#endif +#ifdef G3D_PIXFMT32 +#define G3D_PACK_RGB(r, g, b) PACK_RGB32(r, g, b) +#define G3D_UNPACK_R(c) UNPACK_R32(c) +#define G3D_UNPACK_G(c) UNPACK_G32(c) +#define G3D_UNPACK_B(c) UNPACK_B32(c) +#endif + + +struct g3d_vertex { + float x, y, z, w; + float nx, ny, nz; + float u, v; + unsigned char r, g, b, a; +}; + +enum { + G3D_POINTS = 1, + G3D_LINES = 2, + G3D_TRIANGLES = 3, + G3D_QUADS = 4 +}; + +/* g3d_enable/g3d_disable bits */ +enum { + G3D_CULL_FACE = 0x000001, + G3D_DEPTH_TEST = 0x000002, /* XXX not implemented */ + G3D_LIGHTING = 0x000004, + G3D_LIGHT0 = 0x000008, + G3D_LIGHT1 = 0x000010, + G3D_LIGHT2 = 0x000020, + G3D_LIGHT3 = 0x000040, + G3D_TEXTURE_2D = 0x000080, /* XXX doesn't affect anything, use g3d_polygon_mode */ + G3D_BLEND = 0x000100, + G3D_TEXTURE_GEN = 0x000200, + G3D_CLIP_FRUSTUM = 0x000800,/* when disabled, don't clip against the frustum */ + G3D_CLIP_PLANE0 = 0x001000, /* user-defined 3D clipping planes XXX not impl. */ + G3D_CLIP_PLANE1 = 0x002000, + G3D_CLIP_PLANE2 = 0x004000, + G3D_CLIP_PLANE3 = 0x008000, + + G3D_TEXTURE_MAT = 0x010000, + G3D_SPECULAR = 0x020000, + + G3D_ALL = 0x7fffffff +}; + +/* arg to g3d_front_face */ +enum { G3D_CCW, G3D_CW }; + +/* arg to g3d_polygon_mode */ +enum { + G3D_WIRE, + G3D_FLAT, + G3D_GOURAUD +}; + +/* matrix stacks */ +enum { + G3D_MODELVIEW, + G3D_PROJECTION, + G3D_TEXTURE, + + G3D_NUM_MATRICES +}; + +int g3d_init(void); +void g3d_destroy(void); + +void g3d_framebuffer(int width, int height, void *pixels); +void g3d_framebuffer_addr(void *pixels); +void g3d_viewport(int x, int y, int w, int h); + +void g3d_enable(unsigned int opt); +void g3d_disable(unsigned int opt); +void g3d_setopt(unsigned int opt, unsigned int mask); +unsigned int g3d_getopt(unsigned int mask); + +void g3d_front_face(unsigned int order); +void g3d_polygon_mode(int pmode); + +void g3d_matrix_mode(int mmode); + +void g3d_load_identity(void); +void g3d_load_matrix(const float *m); +void g3d_mult_matrix(const float *m); +void g3d_push_matrix(void); +void g3d_pop_matrix(void); + +void g3d_translate(float x, float y, float z); +void g3d_rotate(float angle, float x, float y, float z); +void g3d_scale(float x, float y, float z); +void g3d_ortho(float left, float right, float bottom, float top, float znear, float zfar); +void g3d_frustum(float left, float right, float bottom, float top, float znear, float zfar); +void g3d_perspective(float vfov, float aspect, float znear, float zfar); + +/* returns pointer to the *internal* matrix, and if argument m is not null, + * also copies the internal matrix there. */ +const float *g3d_get_matrix(int which, float *m); + +void g3d_light_pos(int idx, float x, float y, float z); +void g3d_light_dir(int idx, float x, float y, float z); +void g3d_light_color(int idx, float r, float g, float b); + +void g3d_light_ambient(float r, float g, float b); + +void g3d_mtl_diffuse(float r, float g, float b); +void g3d_mtl_specular(float r, float g, float b); +void g3d_mtl_shininess(float shin); + +void g3d_set_texture(int xsz, int ysz, void *pixels); + +void g3d_draw(int prim, const struct g3d_vertex *varr, int varr_size); +void g3d_draw_indexed(int prim, const struct g3d_vertex *varr, int varr_size, + const uint16_t *iarr, int iarr_size); + +void g3d_begin(int prim); +void g3d_end(void); +void g3d_vertex(float x, float y, float z); +void g3d_normal(float x, float y, float z); +void g3d_color3b(unsigned char r, unsigned char g, unsigned char b); +void g3d_color4b(unsigned char r, unsigned char g, unsigned char b, unsigned char a); +void g3d_color3f(float r, float g, float b); +void g3d_color4f(float r, float g, float b, float a); +void g3d_texcoord(float u, float v); + +#endif /* THREEDGFX_H_ */ diff --git a/src/3dgfx/mesh.c b/src/3dgfx/mesh.c new file mode 100644 index 0000000..0e8d869 --- /dev/null +++ b/src/3dgfx/mesh.c @@ -0,0 +1,524 @@ +#include +#include +#include +#include +#include "mesh.h" +#include "3dgfx.h" + +void free_mesh(struct g3d_mesh *mesh) +{ + destroy_mesh(mesh); + free(mesh); +} + +void destroy_mesh(struct g3d_mesh *mesh) +{ + free(mesh->varr); + free(mesh->iarr); +} + +int copy_mesh(struct g3d_mesh *dest, struct g3d_mesh *src) +{ + dest->prim = src->prim; + if(src->varr) { + if(!(dest->varr = malloc(src->vcount * sizeof *src->varr))) { + return -1; + } + memcpy(dest->varr, src->varr, src->vcount * sizeof *src->varr); + } + dest->vcount = src->vcount; + if(src->iarr) { + if(!(dest->iarr = malloc(src->icount * sizeof *src->iarr))) { + free(dest->varr); + dest->varr = 0; + return -1; + } + memcpy(dest->iarr, src->iarr, src->icount * sizeof *src->iarr); + } + dest->icount = src->icount; + return 0; +} + +static struct { + int prim; + struct g3d_vertex *varr; + const float *xform; +} zsort_cls; + +static int zsort_cmp(const void *aptr, const void *bptr) +{ + int i; + float za = 0.0f; + float zb = 0.0f; + const float *m = zsort_cls.xform; + const struct g3d_vertex *va = (const struct g3d_vertex*)aptr; + const struct g3d_vertex *vb = (const struct g3d_vertex*)bptr; + + for(i=0; ix + m[6] * va->y + m[10] * va->z + m[14]; + zb += m[2] * vb->x + m[6] * vb->y + m[10] * vb->z + m[14]; + ++va; + ++vb; + } + return za - zb; +} + +static int zsort_indexed_cmp(const void *aptr, const void *bptr) +{ + int i; + float za = 0.0f; + float zb = 0.0f; + const uint16_t *a = (const uint16_t*)aptr; + const uint16_t *b = (const uint16_t*)bptr; + + const float *m = zsort_cls.xform; + + for(i=0; ix + m[6] * va->y + m[10] * va->z + m[14]; + zb += m[2] * vb->x + m[6] * vb->y + m[10] * vb->z + m[14]; + } + return za - zb; +} + + +void zsort_mesh(struct g3d_mesh *m) +{ + zsort_cls.varr = m->varr; + zsort_cls.xform = g3d_get_matrix(G3D_MODELVIEW, 0); + zsort_cls.prim = m->prim; + + if(m->iarr) { + int nfaces = m->icount / m->prim; + qsort(m->iarr, nfaces, m->prim * sizeof *m->iarr, zsort_indexed_cmp); + } else { + int nfaces = m->vcount / m->prim; + qsort(m->varr, nfaces, m->prim * sizeof *m->varr, zsort_cmp); + } +} + + +void draw_mesh(struct g3d_mesh *mesh) +{ + if(mesh->iarr) { + g3d_draw_indexed(mesh->prim, mesh->varr, mesh->vcount, mesh->iarr, mesh->icount); + } else { + g3d_draw(mesh->prim, mesh->varr, mesh->vcount); + } +} + +void apply_mesh_xform(struct g3d_mesh *mesh, const float *xform) +{ + int i; + struct g3d_vertex *v = mesh->varr; + + for(i=0; ivcount; i++) { + float x = xform[0] * v->x + xform[4] * v->y + xform[8] * v->z + xform[12]; + float y = xform[1] * v->x + xform[5] * v->y + xform[9] * v->z + xform[13]; + v->z = xform[2] * v->x + xform[6] * v->y + xform[10] * v->z + xform[14]; + v->x = x; + v->y = y; + x = xform[0] * v->nx + xform[4] * v->ny + xform[8] * v->nz; + y = xform[1] * v->nx + xform[5] * v->ny + xform[9] * v->nz; + v->nz = xform[2] * v->nx + xform[6] * v->ny + xform[10] * v->nz; + v->nx = x; + v->ny = y; + ++v; + } +} + +int append_mesh(struct g3d_mesh *ma, struct g3d_mesh *mb) +{ + int i, new_vcount, new_icount; + void *tmp; + uint16_t *iptr; + + if(ma->prim != mb->prim) { + fprintf(stderr, "append_mesh failed, primitive mismatch\n"); + return -1; + } + + if(ma->iarr || mb->iarr) { + if(!ma->iarr) { + if(indexify_mesh(ma) == -1) { + return -1; + } + } else if(!mb->iarr) { + if(indexify_mesh(mb) == -1) { + return -1; + } + } + + new_icount = ma->icount + mb->icount; + if(!(iptr = realloc(ma->iarr, new_icount * sizeof *iptr))) { + fprintf(stderr, "append_mesh: failed to allocate combined index buffer (%d indices)\n", new_icount); + return -1; + } + ma->iarr = iptr; + + iptr += ma->icount; + for(i=0; iicount; i++) { + *iptr++ = mb->iarr[i] + ma->vcount; + } + ma->icount = new_icount; + } + + new_vcount = ma->vcount + mb->vcount; + if(!(tmp = realloc(ma->varr, new_vcount * sizeof *ma->varr))) { + fprintf(stderr, "append_mesh: failed to allocate combined vertex buffer (%d verts)\n", new_vcount); + return -1; + } + ma->varr = tmp; + memcpy(ma->varr + ma->vcount, mb->varr, mb->vcount * sizeof *ma->varr); + ma->vcount = new_vcount; + return 0; +} + +#define FEQ(a, b) ((a) - (b) < 1e-5 && (b) - (a) < 1e-5) +static int cmp_vertex(struct g3d_vertex *a, struct g3d_vertex *b) +{ + if(!FEQ(a->x, b->x) || !FEQ(a->y, b->y) || !FEQ(a->z, b->z) || !FEQ(a->w, b->w)) + return -1; + if(!FEQ(a->nx, b->nx) || !FEQ(a->ny, b->ny) || !FEQ(a->nz, b->nz)) + return -1; + if(!FEQ(a->u, b->u) || !FEQ(a->v, b->v)) + return -1; + if(a->r != b->r || a->g != b->g || a->b != b->b || a->a != b->a) + return -1; + return 0; +} + +static int find_existing(struct g3d_vertex *v, struct g3d_vertex *varr, int vcount) +{ + int i; + for(i=0; iiarr) { + fprintf(stderr, "indexify_mesh failed: already indexed\n"); + return -1; + } + + nfaces = mesh->vcount / mesh->prim; + max_icount = mesh->vcount; + + if(!(mesh->iarr = malloc(max_icount * sizeof *mesh->iarr))) { + fprintf(stderr, "indexify_mesh failed to allocate index buffer of %d indices\n", max_icount); + return -1; + } + + vin = vout = mesh->varr; + iout = mesh->iarr; + + for(i=0; iprim; j++) { + if((idx = find_existing(vin, mesh->varr, out_vcount)) >= 0) { + *iout++ = idx; + } else { + *iout++ = out_vcount++; + if(vin != vout) { + *vout++ = *vin; + } + } + ++vin; + } + } + + /* XXX also shrink buffers? I'll just leave them to max size for now */ + return 0; +} + +void normalize_mesh_normals(struct g3d_mesh *mesh) +{ + int i; + struct g3d_vertex *v = mesh->varr; + + for(i=0; ivcount; i++) { + float mag = sqrt(v->nx * v->nx + v->ny * v->ny + v->nz * v->nz); + float s = (mag == 0.0f) ? 1.0f : 1.0f / mag; + v->nx *= s; + v->ny *= s; + v->nz *= s; + ++v; + } +} + + +static void sphvec(float *res, float theta, float phi, float rad) +{ + theta = -theta; + res[0] = sin(theta) * sin(phi); + res[1] = cos(phi); + res[2] = cos(theta) * sin(phi); +} + +int gen_sphere_mesh(struct g3d_mesh *mesh, float rad, int usub, int vsub) +{ + int i, j; + int nfaces, uverts, vverts; + struct g3d_vertex *vptr; + uint16_t *iptr; + + mesh->prim = G3D_QUADS; + + if(usub < 4) usub = 4; + if(vsub < 2) vsub = 2; + + uverts = usub + 1; + vverts = vsub + 1; + + mesh->vcount = uverts * vverts; + nfaces = usub * vsub; + mesh->icount = nfaces * 4; + + if(!(mesh->varr = malloc(mesh->vcount * sizeof *mesh->varr))) { + fprintf(stderr, "gen_sphere_mesh: failed to allocate vertex buffer (%d vertices)\n", mesh->vcount); + return -1; + } + if(!(mesh->iarr = malloc(mesh->icount * sizeof *mesh->iarr))) { + fprintf(stderr, "gen_sphere_mesh: failed to allocate index buffer (%d indices)\n", mesh->icount); + return -1; + } + vptr = mesh->varr; + iptr = mesh->iarr; + + for(i=0; ix, theta, phi, rad); + vptr->w = 1.0f; + + vptr->nx = vptr->x / rad; + vptr->ny = vptr->y / rad; + vptr->nz = vptr->z / rad; + vptr->u = u; + vptr->v = v; + vptr->r = chess ? 255 : 64; + vptr->g = 128; + vptr->b = chess ? 64 : 255; + ++vptr; + + if(i < usub && j < vsub) { + int idx = i * vverts + j; + *iptr++ = idx; + *iptr++ = idx + 1; + *iptr++ = idx + vverts + 1; + *iptr++ = idx + vverts; + } + } + } + return 0; +} + +int gen_plane_mesh(struct g3d_mesh *m, float width, float height, int usub, int vsub) +{ + int i, j; + int nfaces, nverts, nidx, uverts, vverts; + float x, y, u, v, du, dv; + struct g3d_vertex *vptr; + uint16_t *iptr; + + if(usub < 1) usub = 1; + if(vsub < 1) vsub = 1; + + nfaces = usub * vsub; + uverts = usub + 1; + vverts = vsub + 1; + du = (float)width / (float)usub; + dv = (float)height / (float)vsub; + + nverts = uverts * vverts; + nidx = nfaces * 4; + + if(!(m->varr = malloc(nverts * sizeof *m->varr))) { + fprintf(stderr, "gen_plane_mesh: failed to allocate vertex buffer (%d vertices)\n", nverts); + return -1; + } + if(!(m->iarr = malloc(nidx * sizeof *m->iarr))) { + fprintf(stderr, "gen_plane_mesh: failed to allocate index buffer (%d indices)\n", nidx); + free(m->varr); + m->varr = 0; + return -1; + } + + m->prim = G3D_QUADS; + m->vcount = nverts; + m->icount = nidx; + + vptr = m->varr; + iptr = m->iarr; + + v = 0.0f; + for(i=0; ix = x; + vptr->y = y; + vptr->z = 0.0f; + vptr->w = 1.0f; + vptr->nx = 0.0f; + vptr->ny = 0.0f; + vptr->nz = 1.0f; + vptr->u = u; + vptr->v = v; + vptr->r = vptr->g = vptr->b = vptr->a = 255; + ++vptr; + + u += du; + } + v += dv; + } + + for(i=0; i 0 ? &tmpmesh : mesh; + if(gen_plane_mesh(m, sz, sz, sub, sub) == -1) + return -1; + g3d_load_identity(); + g3d_rotate(rotface[i][0], rotface[i][1], rotface[i][2], rotface[i][3]); + g3d_translate(0, 0, sz / 2.0f); + apply_mesh_xform(m, g3d_get_matrix(G3D_MODELVIEW, 0)); + if(i > 0) { + if(append_mesh(mesh, m) == -1) { + return -1; + } + } + } + + g3d_pop_matrix(); + return 0; +} + +static void torusvec(float *res, float theta, float phi, float mr, float rr) +{ + float rx, ry, rz; + theta = -theta; + + rx = -cos(phi) * rr + mr; + ry = sin(phi) * rr; + rz = 0.0f; + + res[0] = rx * sin(theta) + rz * cos(theta); + res[1] = ry; + res[2] = -rx * cos(theta) + rz * sin(theta); +} + +int gen_torus_mesh(struct g3d_mesh *mesh, float rad, float ringrad, int usub, int vsub) +{ + int i, j; + int nfaces, uverts, vverts; + struct g3d_vertex *vptr; + uint16_t *iptr; + + mesh->prim = G3D_QUADS; + + if(usub < 4) usub = 4; + if(vsub < 2) vsub = 2; + + uverts = usub + 1; + vverts = vsub + 1; + + mesh->vcount = uverts * vverts; + nfaces = usub * vsub; + mesh->icount = nfaces * 4; + + printf("generating torus with %d faces (%d vertices)\n", nfaces, mesh->vcount); + + if(!(mesh->varr = malloc(mesh->vcount * sizeof *mesh->varr))) { + return -1; + } + if(!(mesh->iarr = malloc(mesh->icount * sizeof *mesh->iarr))) { + return -1; + } + vptr = mesh->varr; + iptr = mesh->iarr; + + for(i=0; ix, theta, phi, rad, ringrad); + vptr->w = 1.0f; + + vptr->nx = (vptr->x - rcent[0]) / ringrad; + vptr->ny = (vptr->y - rcent[1]) / ringrad; + vptr->nz = (vptr->z - rcent[2]) / ringrad; + vptr->u = u; + vptr->v = v; + vptr->r = chess ? 255 : 64; + vptr->g = 128; + vptr->b = chess ? 64 : 255; + ++vptr; + + if(i < usub && j < vsub) { + int idx = i * vverts + j; + *iptr++ = idx; + *iptr++ = idx + 1; + *iptr++ = idx + vverts + 1; + *iptr++ = idx + vverts; + } + } + } + return 0; +} + diff --git a/src/3dgfx/mesh.h b/src/3dgfx/mesh.h new file mode 100644 index 0000000..410863a --- /dev/null +++ b/src/3dgfx/mesh.h @@ -0,0 +1,35 @@ +#ifndef MESH_H_ +#define MESH_H_ + +#include "inttypes.h" + +struct g3d_mesh { + int prim; + struct g3d_vertex *varr; + uint16_t *iarr; + int vcount, icount; +}; + +void free_mesh(struct g3d_mesh *mesh); +void destroy_mesh(struct g3d_mesh *mesh); + +int copy_mesh(struct g3d_mesh *dest, struct g3d_mesh *src); + +int load_mesh(struct g3d_mesh *mesh, const char *fname); +int save_mesh(struct g3d_mesh *mesh, const char *fname); + +void zsort_mesh(struct g3d_mesh *mesh); +void draw_mesh(struct g3d_mesh *mesh); + +void apply_mesh_xform(struct g3d_mesh *mesh, const float *xform); +int append_mesh(struct g3d_mesh *ma, struct g3d_mesh *mb); +int indexify_mesh(struct g3d_mesh *mesh); + +void normalize_mesh_normals(struct g3d_mesh *mesh); + +int gen_sphere_mesh(struct g3d_mesh *mesh, float rad, int usub, int vsub); +int gen_plane_mesh(struct g3d_mesh *mesh, float width, float height, int usub, int vsub); +int gen_cube_mesh(struct g3d_mesh *mesh, float sz, int sub); +int gen_torus_mesh(struct g3d_mesh *mesh, float rad, float ringrad, int usub, int vsub); + +#endif /* MESH_H_ */ diff --git a/src/3dgfx/meshload.c b/src/3dgfx/meshload.c new file mode 100644 index 0000000..c62d1cc --- /dev/null +++ b/src/3dgfx/meshload.c @@ -0,0 +1,354 @@ +#include +#include +#include +#include +#include "mesh.h" +#include "dynarr.h" +#include "rbtree.h" +#include "3dgfx.h" +#include "util.h" + +typedef struct { float x, y; } vec2_t; +typedef struct { float x, y, z; } vec3_t; +typedef struct { float x, y, z, w; } vec4_t; + + +struct vertex_pos_color { + float x, y, z; + float r, g, b, a; +}; + +struct facevertex { + int vidx, tidx, nidx; +}; + +static char *clean_line(char *s); +static char *parse_face_vert(char *ptr, struct facevertex *fv, int numv, int numt, int numn); +static int cmp_facevert(const void *ap, const void *bp); +static void free_rbnode_key(struct rbnode *n, void *cls); + +/* merge of different indices per attribute happens during face processing. + * + * A triplet of (vertex index/texcoord index/normal index) is used as the key + * to search in a balanced binary search tree for vertex buffer index assigned + * to the same triplet if it has been encountered before. That index is + * appended to the index buffer. + * + * If a particular triplet has not been encountered before, a new g3d_vertex is + * appended to the vertex buffer. The index of this new vertex is appended to + * the index buffer, and also inserted into the tree for future searches. + */ +int load_mesh(struct g3d_mesh *mesh, const char *fname) +{ + int i, line_num = 0, result = -1; + int found_quad = 0; + FILE *fp = 0; + char buf[256]; + struct vertex_pos_color *varr = 0; + vec3_t *narr = 0; + vec2_t *tarr = 0; + struct rbtree *rbtree = 0; + + if(!(fp = fopen(fname, "rb"))) { + fprintf(stderr, "load_mesh: failed to open file: %s\n", fname); + goto err; + } + + if(!(rbtree = rb_create(cmp_facevert))) { + fprintf(stderr, "load_mesh: failed to create facevertex binary search tree\n"); + goto err; + } + rb_set_delete_func(rbtree, free_rbnode_key, 0); + + if(!(mesh->varr = dynarr_alloc(0, sizeof *mesh->varr)) || + !(mesh->iarr = dynarr_alloc(0, sizeof *mesh->iarr))) { + fprintf(stderr, "load_mesh: failed to allocate resizable mesh arrays\n"); + goto err; + } + if(!(varr = dynarr_alloc(0, sizeof *varr)) || + !(narr = dynarr_alloc(0, sizeof *narr)) || + !(tarr = dynarr_alloc(0, sizeof *tarr))) { + fprintf(stderr, "load_mesh: failed to allocate resizable vertex array\n"); + goto err; + } + + while(fgets(buf, sizeof buf, fp)) { + char *line = clean_line(buf); + ++line_num; + + if(!*line) continue; + + switch(line[0]) { + case 'v': + if(isspace(line[1])) { + /* vertex */ + struct vertex_pos_color v; + int num; + + num = sscanf(line + 2, "%f %f %f %f %f %f %f", &v.x, &v.y, &v.z, &v.r, &v.g, &v.b, &v.a); + if(num < 3) { + fprintf(stderr, "%s:%d: invalid vertex definition: \"%s\"\n", fname, line_num, line); + goto err; + } + switch(num) { + case 3: + v.r = 1.0f; + case 4: + v.g = 1.0f; + case 5: + v.b = 1.0f; + case 6: + v.a = 1.0f; + } + if(!(varr = dynarr_push(varr, &v))) { + fprintf(stderr, "load_mesh: failed to resize vertex buffer\n"); + goto err; + } + + } else if(line[1] == 't' && isspace(line[2])) { + /* texcoord */ + vec2_t tc; + if(sscanf(line + 3, "%f %f", &tc.x, &tc.y) != 2) { + fprintf(stderr, "%s:%d: invalid texcoord definition: \"%s\"\n", fname, line_num, line); + goto err; + } + if(!(tarr = dynarr_push(tarr, &tc))) { + fprintf(stderr, "load_mesh: failed to resize texcoord buffer\n"); + goto err; + } + + } else if(line[1] == 'n' && isspace(line[2])) { + /* normal */ + vec3_t norm; + if(sscanf(line + 3, "%f %f %f", &norm.x, &norm.y, &norm.z) != 3) { + fprintf(stderr, "%s:%d: invalid normal definition: \"%s\"\n", fname, line_num, line); + goto err; + } + if(!(narr = dynarr_push(narr, &norm))) { + fprintf(stderr, "load_mesh: failed to resize normal buffer\n"); + goto err; + } + } + break; + + case 'f': + if(isspace(line[1])) { + /* face */ + char *ptr = line + 2; + struct facevertex fv; + struct rbnode *node; + int vsz = dynarr_size(varr); + int tsz = dynarr_size(tarr); + int nsz = dynarr_size(narr); + + for(i=0; i<4; i++) { + if(!(ptr = parse_face_vert(ptr, &fv, vsz, tsz, nsz))) { + if(i < 3 || found_quad) { + fprintf(stderr, "%s:%d: invalid face definition: \"%s\"\n", fname, line_num, line); + goto err; + } else { + break; + } + } + + if((node = rb_find(rbtree, &fv))) { + uint16_t idx = (int)(intptr_t)node->data; + if(!(mesh->iarr = dynarr_push(mesh->iarr, &idx))) { + fprintf(stderr, "load_mesh: failed to resize index array\n"); + goto err; + } + } else { + uint16_t newidx = dynarr_size(mesh->varr); + struct g3d_vertex v; + struct facevertex *newfv; + + v.x = varr[fv.vidx].x; + v.y = varr[fv.vidx].y; + v.z = varr[fv.vidx].z; + v.w = 1.0f; + v.r = cround64(varr[fv.vidx].r * 255.0); + v.g = cround64(varr[fv.vidx].g * 255.0); + v.b = cround64(varr[fv.vidx].b * 255.0); + v.a = cround64(varr[fv.vidx].a * 255.0); + if(fv.tidx >= 0) { + v.u = tarr[fv.tidx].x; + v.v = tarr[fv.tidx].y; + } else { + v.u = v.x; + v.v = v.y; + } + if(fv.nidx >= 0) { + v.nx = narr[fv.nidx].x; + v.ny = narr[fv.nidx].y; + v.nz = narr[fv.nidx].z; + } else { + v.nx = v.ny = 0.0f; + v.nz = 1.0f; + } + + if(!(mesh->varr = dynarr_push(mesh->varr, &v))) { + fprintf(stderr, "load_mesh: failed to resize combined vertex array\n"); + goto err; + } + if(!(mesh->iarr = dynarr_push(mesh->iarr, &newidx))) { + fprintf(stderr, "load_mesh: failed to resize index array\n"); + goto err; + } + + if((newfv = malloc(sizeof *newfv))) { + *newfv = fv; + } + if(!newfv || rb_insert(rbtree, newfv, (void*)(intptr_t)newidx) == -1) { + fprintf(stderr, "load_mesh: failed to insert facevertex to the binary search tree\n"); + goto err; + } + } + } + if(i > 3) found_quad = 1; + } + break; + + default: + break; + } + } + + mesh->prim = found_quad ? G3D_QUADS : G3D_TRIANGLES; + mesh->vcount = dynarr_size(mesh->varr); + mesh->icount = dynarr_size(mesh->iarr); + mesh->varr = dynarr_finalize(mesh->varr); + mesh->iarr = dynarr_finalize(mesh->iarr); + result = 0; /* success */ + + printf("loaded %s mesh: %s: %d vertices, %d faces\n", found_quad ? "quad" : "triangle", + fname, mesh->vcount, mesh->icount / mesh->prim); + +err: + if(fp) fclose(fp); + dynarr_free(varr); + dynarr_free(narr); + dynarr_free(tarr); + if(result == -1) { + dynarr_free(mesh->varr); + dynarr_free(mesh->iarr); + } + rb_free(rbtree); + return result; +} + +int save_mesh(struct g3d_mesh *mesh, const char *fname) +{ + int i, fvcount; + FILE *fp; + + if(!(fp = fopen(fname, "wb"))) { + fprintf(stderr, "save_mesh: failed to open %s for writing\n", fname); + return -1; + } + fprintf(fp, "# Wavefront OBJ file shoved in your FACE by Mindlapse. Deal with it\n"); + + for(i=0; ivcount; i++) { + struct g3d_vertex *v = mesh->varr + i; + fprintf(fp, "v %f %f %f %f %f %f %f\n", v->x, v->y, v->z, v->r / 255.0f, v->g / 255.0f, + v->b / 255.0f, v->a / 255.0f); + } + for(i=0; ivcount; i++) { + fprintf(fp, "vn %f %f %f\n", mesh->varr[i].nx, mesh->varr[i].ny, mesh->varr[i].nz); + } + for(i=0; ivcount; i++) { + fprintf(fp, "vt %f %f\n", mesh->varr[i].u, mesh->varr[i].v); + } + + fvcount = mesh->prim; + for(i=0; iicount; i++) { + int idx = mesh->iarr[i] + 1; + + if(fvcount == mesh->prim) { + fprintf(fp, "\nf"); + fvcount = 0; + } + fprintf(fp, " %d/%d/%d", idx, idx, idx); + ++fvcount; + } + fprintf(fp, "\n"); + + fclose(fp); + return 0; +} + +static char *clean_line(char *s) +{ + char *end; + + while(*s && isspace(*s)) ++s; + if(!*s) return 0; + + end = s; + while(*end && *end != '#') ++end; + *end = 0; + + while(end > s && isspace(*end)) --end; + *end = 0; + + return s; +} + +static char *parse_idx(char *ptr, int *idx, int arrsz) +{ + char *endp; + int val = strtol(ptr, &endp, 10); + if(endp == ptr) return 0; + + if(val < 0) { /* convert negative indices */ + *idx = arrsz + val; + } else { + *idx = val - 1; /* indices in obj are 1-based */ + } + return endp; +} + +/* possible face-vertex definitions: + * 1. vertex + * 2. vertex/texcoord + * 3. vertex//normal + * 4. vertex/texcoord/normal + */ +static char *parse_face_vert(char *ptr, struct facevertex *fv, int numv, int numt, int numn) +{ + if(!(ptr = parse_idx(ptr, &fv->vidx, numv))) + return 0; + if(*ptr != '/') return (!*ptr || isspace(*ptr)) ? ptr : 0; + + if(*++ptr == '/') { /* no texcoord */ + fv->tidx = -1; + ++ptr; + } else { + if(!(ptr = parse_idx(ptr, &fv->tidx, numt))) + return 0; + if(*ptr != '/') return (!*ptr || isspace(*ptr)) ? ptr : 0; + ++ptr; + } + + if(!(ptr = parse_idx(ptr, &fv->nidx, numn))) + return 0; + return (!*ptr || isspace(*ptr)) ? ptr : 0; +} + +static int cmp_facevert(const void *ap, const void *bp) +{ + const struct facevertex *a = ap; + const struct facevertex *b = bp; + + if(a->vidx == b->vidx) { + if(a->tidx == b->tidx) { + return a->nidx - b->nidx; + } + return a->tidx - b->tidx; + } + return a->vidx - b->vidx; +} + +static void free_rbnode_key(struct rbnode *n, void *cls) +{ + free(n->key); +} diff --git a/src/3dgfx/polyclip.c b/src/3dgfx/polyclip.c new file mode 100644 index 0000000..35e6cd6 --- /dev/null +++ b/src/3dgfx/polyclip.c @@ -0,0 +1,331 @@ +#include +#include +#include +#include "polyclip.h" + +struct ray { + float origin[3]; + float dir[3]; +}; + +static int clip_edge(struct g3d_vertex *poly, int *vnumptr, + const struct g3d_vertex *v0, const struct g3d_vertex *v1, + const struct cplane *plane); +static int check_clip_edge(const struct g3d_vertex *v0, + const struct g3d_vertex *v1, const struct cplane *plane); +static int clip_edge_frustum(struct g3d_vertex *poly, int *vnumptr, + const struct g3d_vertex *v0, const struct g3d_vertex *v1, int fplane); +static float distance_signed(float *pos, const struct cplane *plane); +static int intersect(const struct ray *ray, const struct cplane *plane, float *t); +static int inside_frustum_plane(const struct g3d_vertex *v, int fplane); + + +int clip_poly(struct g3d_vertex *vout, int *voutnum, + const struct g3d_vertex *vin, int vnum, struct cplane *plane) +{ + int i, nextidx, res; + int edges_clipped = 0; + + *voutnum = 0; + + for(i=0; i= vnum) nextidx = 0; + res = clip_edge(vout, voutnum, vin + i, vin + nextidx, plane); + if(res == 0) { + ++edges_clipped; + } + } + + if(*voutnum <= 0) { + assert(edges_clipped == 0); + return -1; + } + + return edges_clipped > 0 ? 0 : 1; +} + +int check_clip_poly(const struct g3d_vertex *v, int vnum, struct cplane *plane) +{ + int i, nextidx, res; + int edges_clipped = 0; + + for(i=0; i= vnum) nextidx = 0; + res = check_clip_edge(v + i, v + nextidx, plane); + if(res == 0) { + ++edges_clipped; + } + } + return edges_clipped ? 0 : res; +} + +int clip_frustum(struct g3d_vertex *vout, int *voutnum, + const struct g3d_vertex *vin, int vnum, int fplane) +{ + int i, nextidx, res; + int edges_clipped = 0; + + if(vnum == 1) { + /* special case: point clipping */ + return inside_frustum_plane(vin, fplane) ? 1 : -1; + } + + *voutnum = 0; + + for(i=0; i= vnum) nextidx = 0; + res = clip_edge_frustum(vout, voutnum, vin + i, vin + nextidx, fplane); + if(res == 0) { + ++edges_clipped; + } + } + + if(*voutnum <= 0) { + assert(edges_clipped == 0); + return -1; + } + + return edges_clipped > 0 ? 0 : 1; +} + +#define LERP_VATTR(res, v0, v1, t) \ + do { \ + (res)->nx = (v0)->nx + ((v1)->nx - (v0)->nx) * (t); \ + (res)->ny = (v0)->ny + ((v1)->ny - (v0)->ny) * (t); \ + (res)->nz = (v0)->nz + ((v1)->nz - (v0)->nz) * (t); \ + (res)->u = (v0)->u + ((v1)->u - (v0)->u) * (t); \ + (res)->v = (v0)->v + ((v1)->v - (v0)->v) * (t); \ + (res)->r = (v0)->r + ((v1)->r - (v0)->r) * (t); \ + (res)->g = (v0)->g + ((v1)->g - (v0)->g) * (t); \ + (res)->b = (v0)->b + ((v1)->b - (v0)->b) * (t); \ + } while(0) + + +/* returns: + * 1 -> both inside + * 0 -> straddling and clipped + * -1 -> both outside + * + * also returns the size of the polygon through vnumptr + */ +static int clip_edge(struct g3d_vertex *poly, int *vnumptr, + const struct g3d_vertex *v0, const struct g3d_vertex *v1, + const struct cplane *plane) +{ + float pos0[3], pos1[3]; + float d0, d1, t; + struct ray ray; + int i, vnum = *vnumptr; + + pos0[0] = v0->x; pos0[1] = v0->y; pos0[2] = v0->z; + pos1[0] = v1->x; pos1[1] = v1->y; pos1[2] = v1->z; + + d0 = distance_signed(pos0, plane); + d1 = distance_signed(pos1, plane); + + for(i=0; i<3; i++) { + ray.origin[i] = pos0[i]; + ray.dir[i] = pos1[i] - pos0[i]; + } + + if(d0 >= 0.0) { + /* start inside */ + if(d1 >= 0.0) { + /* all inside */ + poly[vnum++] = *v1; /* append v1 */ + *vnumptr = vnum; + return 1; + } else { + /* going out */ + struct g3d_vertex *vptr = poly + vnum; + + intersect(&ray, plane, &t); + + vptr->x = ray.origin[0] + ray.dir[0] * t; + vptr->y = ray.origin[1] + ray.dir[1] * t; + vptr->z = ray.origin[2] + ray.dir[2] * t; + vptr->w = 1.0f; + + LERP_VATTR(vptr, v0, v1, t); + vnum++; /* append new vertex on the intersection point */ + } + } else { + /* start outside */ + if(d1 >= 0) { + /* going in */ + struct g3d_vertex *vptr = poly + vnum; + + intersect(&ray, plane, &t); + + vptr->x = ray.origin[0] + ray.dir[0] * t; + vptr->y = ray.origin[1] + ray.dir[1] * t; + vptr->z = ray.origin[2] + ray.dir[2] * t; + vptr->w = 1.0f; + + LERP_VATTR(vptr, v0, v1, t); + vnum++; /* append new vertex on the intersection point */ + + /* then append v1 ... */ + poly[vnum++] = *v1; + } else { + /* all outside */ + return -1; + } + } + + *vnumptr = vnum; + return 0; +} + +/* same as above, but only checks for clipping and classifies the edge */ +static int check_clip_edge(const struct g3d_vertex *v0, + const struct g3d_vertex *v1, const struct cplane *plane) +{ + float pos0[3], pos1[3]; + float d0, d1; + + pos0[0] = v0->x; pos0[1] = v0->y; pos0[2] = v0->z; + pos1[0] = v1->x; pos1[1] = v1->y; pos1[2] = v1->z; + + d0 = distance_signed(pos0, plane); + d1 = distance_signed(pos1, plane); + + if(d0 > 0.0f && d1 > 0.0f) { + return 1; + } + if(d0 < 0.0f && d1 < 0.0f) { + return -1; + } + return 0; +} + +static float distance_signed(float *pos, const struct cplane *plane) +{ + float dx = pos[0] - plane->x; + float dy = pos[1] - plane->y; + float dz = pos[2] - plane->z; + return dx * plane->nx + dy * plane->ny + dz * plane->nz; +} + +static int intersect(const struct ray *ray, const struct cplane *plane, float *t) +{ + float orig_pt_dir[3]; + + float ndotdir = plane->nx * ray->dir[0] + plane->ny * ray->dir[1] + plane->nz * ray->dir[2]; + if(fabs(ndotdir) < 1e-6) { + *t = 0.0f; + return 0; + } + + orig_pt_dir[0] = plane->x - ray->origin[0]; + orig_pt_dir[1] = plane->y - ray->origin[1]; + orig_pt_dir[2] = plane->z - ray->origin[2]; + + *t = (plane->nx * orig_pt_dir[0] + plane->ny * orig_pt_dir[1] + plane->nz * orig_pt_dir[2]) / ndotdir; + return 1; +} + +/* homogeneous frustum clipper helpers */ + +static int inside_frustum_plane(const struct g3d_vertex *v, int fplane) +{ + switch(fplane) { + case CLIP_LEFT: + return v->x >= -v->w; + case CLIP_RIGHT: + return v->x <= v->w; + case CLIP_BOTTOM: + return v->y >= -v->w; + case CLIP_TOP: + return v->y <= v->w; + case CLIP_NEAR: + return v->z >= -v->w; + case CLIP_FAR: + return v->z <= v->w; + } + assert(0); + return 0; +} + +static float intersect_frustum(const struct g3d_vertex *a, const struct g3d_vertex *b, int fplane) +{ + switch(fplane) { + case CLIP_LEFT: + return (-a->w - a->x) / (b->x - a->x + b->w - a->w); + case CLIP_RIGHT: + return (a->w - a->x) / (b->x - a->x - b->w + a->w); + case CLIP_BOTTOM: + return (-a->w - a->y) / (b->y - a->y + b->w - a->w); + case CLIP_TOP: + return (a->w - a->y) / (b->y - a->y - b->w + a->w); + case CLIP_NEAR: + return (-a->w - a->z) / (b->z - a->z + b->w - a->w); + case CLIP_FAR: + return (a->w - a->z) / (b->z - a->z - b->w + a->w); + } + + assert(0); + return 0; +} + +static int clip_edge_frustum(struct g3d_vertex *poly, int *vnumptr, + const struct g3d_vertex *v0, const struct g3d_vertex *v1, int fplane) +{ + int vnum = *vnumptr; + int in0, in1; + float t; + + in0 = inside_frustum_plane(v0, fplane); + in1 = inside_frustum_plane(v1, fplane); + + if(in0) { + /* start inside */ + if(in1) { + /* all inside */ + poly[vnum++] = *v1; /* append v1 */ + *vnumptr = vnum; + return 1; + } else { + /* going out */ + struct g3d_vertex *vptr = poly + vnum; + + t = intersect_frustum(v0, v1, fplane); + + vptr->x = v0->x + (v1->x - v0->x) * t; + vptr->y = v0->y + (v1->y - v0->y) * t; + vptr->z = v0->z + (v1->z - v0->z) * t; + vptr->w = v0->w + (v1->w - v0->w) * t; + + LERP_VATTR(vptr, v0, v1, t); + ++vnum; /* append new vertex on the intersection point */ + } + } else { + /* start outside */ + if(in1) { + /* going in */ + struct g3d_vertex *vptr = poly + vnum; + + t = intersect_frustum(v0, v1, fplane); + + vptr->x = v0->x + (v1->x - v0->x) * t; + vptr->y = v0->y + (v1->y - v0->y) * t; + vptr->z = v0->z + (v1->z - v0->z) * t; + vptr->w = v0->w + (v1->w - v0->w) * t; + + LERP_VATTR(vptr, v0, v1, t); + ++vnum; /* append new vertex on the intersection point */ + + /* then append v1 ... */ + poly[vnum++] = *v1; + } else { + /* all outside */ + return -1; + } + } + + *vnumptr = vnum; + return 0; +} diff --git a/src/3dgfx/polyclip.h b/src/3dgfx/polyclip.h new file mode 100644 index 0000000..adee29d --- /dev/null +++ b/src/3dgfx/polyclip.h @@ -0,0 +1,38 @@ +#ifndef POLYCLIP_H_ +#define POLYCLIP_H_ + +#include "3dgfx.h" + +struct cplane { + float x, y, z; + float nx, ny, nz; +}; + +enum { + CLIP_LEFT, CLIP_RIGHT, + CLIP_BOTTOM, CLIP_TOP, + CLIP_NEAR, CLIP_FAR +}; + +/* Generic polygon clipper + * returns: + * 1 -> fully inside, not clipped + * 0 -> straddling the plane and clipped + * -1 -> fully outside, not clipped + * in all cases, vertices are copied to vout, and the vertex count is written + * to wherever voutnum is pointing + */ +int clip_poly(struct g3d_vertex *vout, int *voutnum, + const struct g3d_vertex *vin, int vnum, struct cplane *plane); + +/* only checks if the polygon would be clipped by the plane, and classifies it + * as inside/outside/straddling, without actually producing a clipped polygon. + * return values are the same as clip_poly. + */ +int check_clip_poly(const struct g3d_vertex *v, int vnum, struct cplane *plane); + +/* Special-case frustum clipper (might be slightly faster) */ +int clip_frustum(struct g3d_vertex *vout, int *voutnum, + const struct g3d_vertex *vin, int vnum, int fplane); + +#endif /* POLYCLIP_H_ */ diff --git a/src/3dgfx/polyfill.c b/src/3dgfx/polyfill.c new file mode 100644 index 0000000..3f94e25 --- /dev/null +++ b/src/3dgfx/polyfill.c @@ -0,0 +1,179 @@ +#include +#include +#include +#include +#if defined(__WATCOMC__) || defined(_MSC_VER) || defined(__DJGPP__) +#include +#else +#include +#endif +#include "polyfill.h" +#include "gfxutil.h" + +#define FILL_POLY_BITS 0x03 + +/* mode bits: 00-wire 01-flat 10-gouraud 11-reserved + * bit 2: texture + * bit 3: blend + */ +void (*fillfunc[])(struct pvertex*, int) = { + polyfill_wire, + polyfill_flat, + polyfill_gouraud, + 0, + polyfill_tex_wire, + polyfill_tex_flat, + polyfill_tex_gouraud, + 0, + polyfill_blend_wire, + polyfill_blend_flat, + polyfill_blend_gouraud, + 0, + polyfill_blend_tex_wire, + polyfill_blend_tex_flat, + polyfill_blend_tex_gouraud, + 0 +}; + +struct pimage pfill_fb, pfill_tex; + +void polyfill(int mode, struct pvertex *verts, int nverts) +{ +#ifndef NDEBUG + if(!fillfunc[mode]) { + fprintf(stderr, "polyfill mode %d not implemented\n", mode); + abort(); + } +#endif + + fillfunc[mode](verts, nverts); +} + +void polyfill_wire(struct pvertex *verts, int nverts) +{ + int i, x0, y0, x1, y1; + struct pvertex *v = verts; + unsigned short color = ((v->r << 8) & 0xf800) | + ((v->g << 3) & 0x7e0) | ((v->b >> 3) & 0x1f); + + for(i=0; ix >> 8; + y0 = v->y >> 8; + ++v; + x1 = v->x >> 8; + y1 = v->y >> 8; + if(clip_line(&x0, &y0, &x1, &y1, 0, 0, pfill_fb.width, pfill_fb.height)) { + draw_line(x0, y0, x1, y1, color); + } + } + x0 = verts[0].x >> 8; + y0 = verts[0].y >> 8; + if(clip_line(&x1, &y1, &x0, &y0, 0, 0, pfill_fb.width, pfill_fb.height)) { + draw_line(x1, y1, x0, y0, color); + } +} + +void polyfill_tex_wire(struct pvertex *verts, int nverts) +{ + polyfill_wire(verts, nverts); /* TODO */ +} + +void polyfill_blend_wire(struct pvertex *verts, int nverts) +{ + polyfill_wire(verts, nverts); /* TODO */ +} + +void polyfill_blend_tex_wire(struct pvertex *verts, int nverts) +{ + polyfill_wire(verts, nverts); /* TODO */ +} + +#define NEXTIDX(x) (((x) - 1 + nverts) % nverts) +#define PREVIDX(x) (((x) + 1) % nverts) + +/* XXX + * When HIGH_QUALITY is defined, the rasterizer calculates slopes for attribute + * interpolation on each scanline separately; otherwise the slope for each + * attribute would be calculated once for the whole polygon, which is faster, + * but produces some slight quantization artifacts, due to the limited precision + * of fixed-point calculations. + */ +#define HIGH_QUALITY + +/* extra bits of precision to use when interpolating colors. + * try tweaking this if you notice strange quantization artifacts. + */ +#define COLOR_SHIFT 12 + + +#define POLYFILL polyfill_flat +#define SCANEDGE scanedge_flat +#undef GOURAUD +#undef TEXMAP +#undef BLEND +#include "polytmpl.h" +#undef POLYFILL +#undef SCANEDGE + +#define POLYFILL polyfill_gouraud +#define SCANEDGE scanedge_gouraud +#define GOURAUD +#undef TEXMAP +#undef BLEND +#include "polytmpl.h" +#undef POLYFILL +#undef SCANEDGE + +#define POLYFILL polyfill_tex_flat +#define SCANEDGE scanedge_tex_flat +#undef GOURAUD +#define TEXMAP +#undef BLEND +#include "polytmpl.h" +#undef POLYFILL +#undef SCANEDGE + +#define POLYFILL polyfill_tex_gouraud +#define SCANEDGE scanedge_tex_gouraud +#define GOURAUD +#define TEXMAP +#undef BLEND +#include "polytmpl.h" +#undef POLYFILL +#undef SCANEDGE + +#define POLYFILL polyfill_blend_flat +#define SCANEDGE scanedge_blend_flat +#undef GOURAUD +#undef TEXMAP +#define BLEND +#include "polytmpl.h" +#undef POLYFILL +#undef SCANEDGE + +#define POLYFILL polyfill_blend_gouraud +#define SCANEDGE scanedge_blend_gouraud +#define GOURAUD +#undef TEXMAP +#define BLEND +#include "polytmpl.h" +#undef POLYFILL +#undef SCANEDGE + +#define POLYFILL polyfill_blend_tex_flat +#define SCANEDGE scanedge_blend_tex_flat +#undef GOURAUD +#define TEXMAP +#define BLEND +#include "polytmpl.h" +#undef POLYFILL +#undef SCANEDGE + +#define POLYFILL polyfill_blend_tex_gouraud +#define SCANEDGE scanedge_blend_tex_gouraud +#define GOURAUD +#define TEXMAP +#define BLEND +#include "polytmpl.h" +#undef POLYFILL +#undef SCANEDGE diff --git a/src/3dgfx/polyfill.h b/src/3dgfx/polyfill.h new file mode 100644 index 0000000..86c7947 --- /dev/null +++ b/src/3dgfx/polyfill.h @@ -0,0 +1,62 @@ +#ifndef POLYFILL_H_ +#define POLYFILL_H_ + +#include "inttypes.h" +#include "3dgfx.h" + +#define POLYFILL_MODE_MASK 0x03 +#define POLYFILL_TEX_BIT 0x04 +#define POLYFILL_BLEND_BIT 0x08 + +enum { + POLYFILL_WIRE = 0, + POLYFILL_FLAT, + POLYFILL_GOURAUD, + + POLYFILL_TEX_WIRE = 4, + POLYFILL_TEX_FLAT, + POLYFILL_TEX_GOURAUD, + + POLYFILL_BLEND_WIRE = 8, + POLYFILL_BLEND_FLAT, + POLYFILL_BLEND_GOURAUD, + + POLYFILL_BLEND_TEX_WIRE = 12, + POLYFILL_BLEND_TEX_FLAT, + POLYFILL_BLEND_TEX_GOURAUD +}; + +/* projected vertices for the rasterizer */ +struct pvertex { + int32_t x, y; /* 24.8 fixed point */ + int32_t u, v; /* 16.16 fixed point */ + int32_t r, g, b, a; /* int 0-255 */ +}; + +struct pimage { + g3d_pixel *pixels; + int width, height; + + int xshift, yshift; + unsigned int xmask, ymask; +}; + +extern struct pimage pfill_fb; +extern struct pimage pfill_tex; + +void polyfill(int mode, struct pvertex *verts, int nverts); + +void polyfill_wire(struct pvertex *verts, int nverts); +void polyfill_flat(struct pvertex *verts, int nverts); +void polyfill_gouraud(struct pvertex *verts, int nverts); +void polyfill_tex_wire(struct pvertex *verts, int nverts); +void polyfill_tex_flat(struct pvertex *verts, int nverts); +void polyfill_tex_gouraud(struct pvertex *verts, int nverts); +void polyfill_blend_wire(struct pvertex *verts, int nverts); +void polyfill_blend_flat(struct pvertex *verts, int nverts); +void polyfill_blend_gouraud(struct pvertex *verts, int nverts); +void polyfill_blend_tex_wire(struct pvertex *verts, int nverts); +void polyfill_blend_tex_flat(struct pvertex *verts, int nverts); +void polyfill_blend_tex_gouraud(struct pvertex *verts, int nverts); + +#endif /* POLYFILL_H_ */ diff --git a/src/3dgfx/polytmpl.h b/src/3dgfx/polytmpl.h new file mode 100644 index 0000000..0f50b7d --- /dev/null +++ b/src/3dgfx/polytmpl.h @@ -0,0 +1,345 @@ +static uint32_t SCANEDGE(struct pvertex *v0, struct pvertex *v1, struct pvertex *edge) +{ + int i; + int32_t x, dx, dy, slope; +#ifdef GOURAUD + int r, g, b, dr, dg, db; + int32_t rslope, gslope, bslope; +#ifdef BLEND + int32_t a, da, aslope; +#endif +#endif /* GOURAUD */ +#ifdef TEXMAP + int32_t u, v, du, dv, uslope, vslope; +#endif + int32_t start_idx, end_idx; + + if(v0->y > v1->y) { + struct pvertex *tmp = v0; + v0 = v1; + v1 = tmp; + } + + x = v0->x; + dy = v1->y - v0->y; + dx = v1->x - v0->x; + slope = (dx << 8) / dy; +#ifdef GOURAUD + r = (v0->r << COLOR_SHIFT); + g = (v0->g << COLOR_SHIFT); + b = (v0->b << COLOR_SHIFT); + dr = (v1->r << COLOR_SHIFT) - r; + dg = (v1->g << COLOR_SHIFT) - g; + db = (v1->b << COLOR_SHIFT) - b; + rslope = (dr << 8) / dy; + gslope = (dg << 8) / dy; + bslope = (db << 8) / dy; +#ifdef BLEND + a = (v0->a << COLOR_SHIFT); + da = (v1->a << COLOR_SHIFT) - a; + aslope = (da << 8) / dy; +#endif /* BLEND */ +#endif /* GOURAUD */ +#ifdef TEXMAP + u = v0->u; + v = v0->v; + du = v1->u - v0->u; + dv = v1->v - v0->v; + uslope = (du << 8) / dy; + vslope = (dv << 8) / dy; +#endif + + start_idx = v0->y >> 8; + end_idx = v1->y >> 8; + + for(i=start_idx; i pv[botidx].y) botidx = i; + } + + winding = 0; + for(i=0; i> 4) * ((pv[next].y + pv[i].y) >> 4); + } + + /* +1 to avoid crashing due to off-by-one rounding errors in the rasterization */ + left = alloca((pfill_fb.height + 1) * sizeof *left); + right = alloca((pfill_fb.height + 1) * sizeof *right); + + for(i=0; i> 8) == (y1 >> 8)) { + /*if(y0 > y1) {*/ + int i0, i1; + int idx = y0 >> 8; + if(pv[i].x < pv[next].x) { + i0 = i; + i1 = next; + } else { + i0 = next; + i1 = i; + } + left[idx].x = pv[i0].x; + right[idx].x = pv[i1].x; +#ifdef GOURAUD + left[idx].r = pv[i0].r << COLOR_SHIFT; + left[idx].g = pv[i0].g << COLOR_SHIFT; + left[idx].b = pv[i0].b << COLOR_SHIFT; + right[idx].r = pv[i1].r << COLOR_SHIFT; + right[idx].g = pv[i1].g << COLOR_SHIFT; + right[idx].b = pv[i1].b << COLOR_SHIFT; +#ifdef BLEND + left[idx].a = pv[i0].a << COLOR_SHIFT; + right[idx].a = pv[i1].a << COLOR_SHIFT; +#endif /* BLEND */ +#endif +#ifdef TEXMAP + left[idx].u = pv[i0].u; + left[idx].v = pv[i0].v; + right[idx].u = pv[i1].u; + right[idx].v = pv[i1].v; +#endif + if(idx > slbot) slbot = idx; + if(idx < sltop) sltop = idx; + /*}*/ + } else { + struct pvertex *edge; + uint32_t res, tmp; + + if(winding < 0) { + /* clockwise */ + edge = y0 > y1 ? left : right; + } else { + /* counter-clockwise */ + edge = y0 > y1 ? right : left; + } + res = SCANEDGE(pv + i, pv + next, edge); + tmp = (res >> 16) & 0xffff; + if(tmp > slbot) slbot = tmp; + if((tmp = res & 0xffff) < sltop) { + sltop = tmp; + } + } + } + + /* calculate the slopes of all attributes across the largest span out + * of the three: middle, top, or bottom. + */ +#ifndef HIGH_QUALITY +#if defined(GOURAUD) || defined(TEXMAP) + mid = (sltop + slbot) >> 1; + dx = right[mid].x - left[mid].x; + if((tmp = right[sltop].x - left[sltop].x) > dx) { + dx = tmp; + mid = sltop; + } + if((tmp = right[slbot].x - left[slbot].x) > dx) { + dx = tmp; + mid = slbot; + } + if(!dx) dx = 256; /* avoid division by zero */ +#endif +#ifdef GOURAUD + dr = right[mid].r - left[mid].r; + dg = right[mid].g - left[mid].g; + db = right[mid].b - left[mid].b; + rslope = (dr << 8) / dx; + gslope = (dg << 8) / dx; + bslope = (db << 8) / dx; +#ifdef BLEND + da = right[mid].a - left[mid].a; + aslope = (da << 8) / dx; +#endif /* BLEND */ +#endif +#ifdef TEXMAP + du = right[mid].u - left[mid].u; + dv = right[mid].v - left[mid].v; + uslope = (du << 8) / dx; + vslope = (dv << 8) / dx; +#endif +#endif /* !defined(HIGH_QUALITY) */ + + /* for each scanline ... */ + for(i=sltop; i<=slbot; i++) { + g3d_pixel *pixptr; + int32_t x; + + x = left[i].x; + pixptr = pfill_fb.pixels + i * pfill_fb.width + (x >> 8); + +#ifdef GOURAUD + r = left[i].r; + g = left[i].g; + b = left[i].b; +#ifdef BLEND + a = left[i].a; +#endif /* BLEND */ +#endif +#ifdef TEXMAP + u = left[i].u; + v = left[i].v; +#endif + +#if defined(HIGH_QUALITY) && (defined(GOURAUD) || defined(TEXMAP)) + if(!(dx = right[i].x - left[i].x)) dx = 256; + +#ifdef GOURAUD + dr = right[i].r - left[i].r; + dg = right[i].g - left[i].g; + db = right[i].b - left[i].b; + rslope = (dr << 8) / dx; + gslope = (dg << 8) / dx; + bslope = (db << 8) / dx; +#ifdef BLEND + da = right[i].a - left[i].a; + aslope = (da << 8) / dx; +#endif /* BLEND */ +#endif /* GOURAUD */ +#ifdef TEXMAP + du = right[i].u - left[i].u; + dv = right[i].v - left[i].v; + uslope = (du << 8) / dx; + vslope = (dv << 8) / dx; +#endif +#endif /* HIGH_QUALITY */ + + /* go across the scanline interpolating if necessary */ + while(x <= right[i].x) { +#if defined(GOURAUD) || defined(TEXMAP) || defined(BLEND) + int cr, cg, cb; +#endif +#ifdef BLEND + g3d_pixel fbcol; + int alpha, inv_alpha; +#endif +#ifdef GOURAUD + /* we upped the color precision to while interpolating the + * edges, now drop the extra bits before packing + */ + cr = r < 0 ? 0 : (r >> COLOR_SHIFT); + cg = g < 0 ? 0 : (g >> COLOR_SHIFT); + cb = b < 0 ? 0 : (b >> COLOR_SHIFT); + r += rslope; + g += gslope; + b += bslope; +#ifdef BLEND + a += aslope; +#else + if(cr > 255) cr = 255; + if(cg > 255) cg = 255; + if(cb > 255) cb = 255; +#endif /* BLEND */ +#endif /* GOURAUD */ +#ifdef TEXMAP + { + int tx = (u >> (16 - pfill_tex.xshift)) & pfill_tex.xmask; + int ty = (v >> (16 - pfill_tex.yshift)) & pfill_tex.ymask; + g3d_pixel texel = pfill_tex.pixels[(ty << pfill_tex.xshift) + tx]; +#ifdef GOURAUD + /* This is not correct, should be /255, but it's much faster + * to shift by 8 (/256), and won't make a huge difference + */ + cr = (cr * G3D_UNPACK_R(texel)) >> 8; + cg = (cg * G3D_UNPACK_G(texel)) >> 8; + cb = (cb * G3D_UNPACK_B(texel)) >> 8; +#else + cr = G3D_UNPACK_R(texel); + cg = G3D_UNPACK_G(texel); + cb = G3D_UNPACK_B(texel); +#endif + } + u += uslope; + v += vslope; +#endif + +#ifdef BLEND +#if !defined(GOURAUD) && !defined(TEXMAP) + /* flat version: cr,cg,cb are uninitialized so far */ + cr = pv[0].r; + cg = pv[0].g; + cb = pv[0].b; +#endif +#ifdef GOURAUD + alpha = a >> COLOR_SHIFT; +#else + alpha = pv[0].a; +#endif + fbcol = *pixptr; + inv_alpha = 255 - alpha; + cr = (cr * alpha + G3D_UNPACK_R(fbcol) * inv_alpha) >> 8; + cg = (cg * alpha + G3D_UNPACK_G(fbcol) * inv_alpha) >> 8; + cb = (cb * alpha + G3D_UNPACK_B(fbcol) * inv_alpha) >> 8; + if(cr > 255) cr = 255; + if(cg > 255) cg = 255; + if(cb > 255) cb = 255; +#endif /* BLEND */ + +#if defined(GOURAUD) || defined(TEXMAP) || defined(BLEND) + color = G3D_PACK_RGB(cr, cg, cb); +#endif + +#ifdef DEBUG_OVERDRAW + *pixptr++ += DEBUG_OVERDRAW; +#else + *pixptr++ = color; +#endif + x += 256; + } + } +} + diff --git a/src/dynarr.c b/src/dynarr.c new file mode 100644 index 0000000..09a5e45 --- /dev/null +++ b/src/dynarr.c @@ -0,0 +1,140 @@ +/* dynarr - dynamic resizable C array data structure + * author: John Tsiombikas + * license: public domain + */ +#include +#include +#include +#include "dynarr.h" + +/* The array descriptor keeps auxilliary information needed to manipulate + * the dynamic array. It's allocated adjacent to the array buffer. + */ +struct arrdesc { + int nelem, szelem; + int max_elem; + int bufsz; /* not including the descriptor */ +}; + +#define DESC(x) ((struct arrdesc*)((char*)(x) - sizeof(struct arrdesc))) + +void *dynarr_alloc(int elem, int szelem) +{ + struct arrdesc *desc; + + if(!(desc = malloc(elem * szelem + sizeof *desc))) { + return 0; + } + desc->nelem = desc->max_elem = elem; + desc->szelem = szelem; + desc->bufsz = elem * szelem; + return (char*)desc + sizeof *desc; +} + +void dynarr_free(void *da) +{ + if(da) { + free(DESC(da)); + } +} + +void *dynarr_resize(void *da, int elem) +{ + int newsz; + void *tmp; + struct arrdesc *desc; + + if(!da) return 0; + desc = DESC(da); + + newsz = desc->szelem * elem; + + if(!(tmp = realloc(desc, newsz + sizeof *desc))) { + return 0; + } + desc = tmp; + + desc->nelem = desc->max_elem = elem; + desc->bufsz = newsz; + return (char*)desc + sizeof *desc; +} + +int dynarr_empty(void *da) +{ + return DESC(da)->nelem ? 0 : 1; +} + +int dynarr_size(void *da) +{ + return DESC(da)->nelem; +} + + +void *dynarr_clear(void *da) +{ + return dynarr_resize(da, 0); +} + +/* stack semantics */ +void *dynarr_push(void *da, void *item) +{ + struct arrdesc *desc; + int nelem; + + desc = DESC(da); + nelem = desc->nelem; + + if(nelem >= desc->max_elem) { + /* need to resize */ + struct arrdesc *tmp; + int newsz = desc->max_elem ? desc->max_elem * 2 : 1; + + if(!(tmp = dynarr_resize(da, newsz))) { + fprintf(stderr, "failed to resize\n"); + return da; + } + da = tmp; + desc = DESC(da); + desc->nelem = nelem; + } + + if(item) { + memcpy((char*)da + desc->nelem++ * desc->szelem, item, desc->szelem); + } + return da; +} + +void *dynarr_pop(void *da) +{ + struct arrdesc *desc; + int nelem; + + desc = DESC(da); + nelem = desc->nelem; + + if(!nelem) return da; + + if(nelem <= desc->max_elem / 3) { + /* reclaim space */ + struct arrdesc *tmp; + int newsz = desc->max_elem / 2; + + if(!(tmp = dynarr_resize(da, newsz))) { + fprintf(stderr, "failed to resize\n"); + return da; + } + da = tmp; + desc = DESC(da); + desc->nelem = nelem; + } + desc->nelem--; + + return da; +} + +void *dynarr_finalize(void *da) +{ + struct arrdesc *desc = DESC(da); + memmove(desc, da, desc->bufsz); + return desc; +} diff --git a/src/dynarr.h b/src/dynarr.h new file mode 100644 index 0000000..8690b5a --- /dev/null +++ b/src/dynarr.h @@ -0,0 +1,80 @@ +/* dynarr - dynamic resizable C array data structure + * author: John Tsiombikas + * license: public domain + */ +#ifndef DYNARR_H_ +#define DYNARR_H_ + +/* usage example: + * ------------- + * int *arr = dynarr_alloc(0, sizeof *arr); + * + * int x = 10; + * arr = dynarr_push(arr, &x); + * x = 5; + * arr = dynarr_push(arr, &x); + * x = 42; + * arr = dynarr_push(arr, &x); + * + * for(i=0; i + +rbtree is free software, feel free to use, modify, and redistribute it, under +the terms of the 3-clause BSD license. See COPYING for details. + */ +#include +#include +#include +#include +#include "rbtree.h" + +#define INT2PTR(x) ((void*)(intptr_t)(x)) +#define PTR2INT(x) ((int)(intptr_t)(x)) + +struct rbtree { + struct rbnode *root; + + rb_alloc_func_t alloc; + rb_free_func_t free; + + rb_cmp_func_t cmp; + rb_del_func_t del; + void *del_cls; + + struct rbnode *rstack, *iter; +}; + +static int cmpaddr(const void *ap, const void *bp); +static int cmpint(const void *ap, const void *bp); + +static int count_nodes(struct rbnode *node); +static void del_tree(struct rbnode *node, void (*delfunc)(struct rbnode*, void*), void *cls); +static struct rbnode *insert(struct rbtree *rb, struct rbnode *tree, void *key, void *data); +static struct rbnode *delete(struct rbtree *rb, struct rbnode *tree, void *key); +/*static struct rbnode *find(struct rbtree *rb, struct rbnode *node, void *key);*/ +static void traverse(struct rbnode *node, void (*func)(struct rbnode*, void*), void *cls); + +struct rbtree *rb_create(rb_cmp_func_t cmp_func) +{ + struct rbtree *rb; + + if(!(rb = malloc(sizeof *rb))) { + return 0; + } + if(rb_init(rb, cmp_func) == -1) { + free(rb); + return 0; + } + return rb; +} + +void rb_free(struct rbtree *rb) +{ + rb_destroy(rb); + free(rb); +} + + +int rb_init(struct rbtree *rb, rb_cmp_func_t cmp_func) +{ + memset(rb, 0, sizeof *rb); + + if(!cmp_func) { + rb->cmp = cmpaddr; + } else if(cmp_func == RB_KEY_INT) { + rb->cmp = cmpint; + } else if(cmp_func == RB_KEY_STRING) { + rb->cmp = (rb_cmp_func_t)strcmp; + } else { + rb->cmp = cmp_func; + } + + rb->alloc = malloc; + rb->free = free; + return 0; +} + +void rb_destroy(struct rbtree *rb) +{ + del_tree(rb->root, rb->del, rb->del_cls); +} + +void rb_set_allocator(struct rbtree *rb, rb_alloc_func_t alloc, rb_free_func_t free) +{ + rb->alloc = alloc; + rb->free = free; +} + + +void rb_set_compare_func(struct rbtree *rb, rb_cmp_func_t func) +{ + rb->cmp = func; +} + +void rb_set_delete_func(struct rbtree *rb, rb_del_func_t func, void *cls) +{ + rb->del = func; + rb->del_cls = cls; +} + + +void rb_clear(struct rbtree *rb) +{ + del_tree(rb->root, rb->del, rb->del_cls); + rb->root = 0; +} + +int rb_copy(struct rbtree *dest, struct rbtree *src) +{ + struct rbnode *node; + + rb_clear(dest); + rb_begin(src); + while((node = rb_next(src))) { + if(rb_insert(dest, node->key, node->data) == -1) { + return -1; + } + } + return 0; +} + +int rb_size(struct rbtree *rb) +{ + return count_nodes(rb->root); +} + +int rb_insert(struct rbtree *rb, void *key, void *data) +{ + rb->root = insert(rb, rb->root, key, data); + rb->root->red = 0; + return 0; +} + +int rb_inserti(struct rbtree *rb, int key, void *data) +{ + rb->root = insert(rb, rb->root, INT2PTR(key), data); + rb->root->red = 0; + return 0; +} + + +int rb_delete(struct rbtree *rb, void *key) +{ + if((rb->root = delete(rb, rb->root, key))) { + rb->root->red = 0; + } + return 0; +} + +int rb_deletei(struct rbtree *rb, int key) +{ + if((rb->root = delete(rb, rb->root, INT2PTR(key)))) { + rb->root->red = 0; + } + return 0; +} + + +struct rbnode *rb_find(struct rbtree *rb, void *key) +{ + struct rbnode *node = rb->root; + + while(node) { + int cmp = rb->cmp(key, node->key); + if(cmp == 0) { + return node; + } + node = cmp < 0 ? node->left : node->right; + } + return 0; +} + +struct rbnode *rb_findi(struct rbtree *rb, int key) +{ + return rb_find(rb, INT2PTR(key)); +} + + +void rb_foreach(struct rbtree *rb, void (*func)(struct rbnode*, void*), void *cls) +{ + traverse(rb->root, func, cls); +} + + +struct rbnode *rb_root(struct rbtree *rb) +{ + return rb->root; +} + +void rb_begin(struct rbtree *rb) +{ + rb->rstack = 0; + rb->iter = rb->root; +} + +#define push(sp, x) ((x)->next = (sp), (sp) = (x)) +#define pop(sp) ((sp) = (sp)->next) +#define top(sp) (sp) + +struct rbnode *rb_next(struct rbtree *rb) +{ + struct rbnode *res = 0; + + while(rb->rstack || rb->iter) { + if(rb->iter) { + push(rb->rstack, rb->iter); + rb->iter = rb->iter->left; + } else { + rb->iter = top(rb->rstack); + pop(rb->rstack); + res = rb->iter; + rb->iter = rb->iter->right; + break; + } + } + return res; +} + +void *rb_node_key(struct rbnode *node) +{ + return node ? node->key : 0; +} + +int rb_node_keyi(struct rbnode *node) +{ + return node ? PTR2INT(node->key) : 0; +} + +void *rb_node_data(struct rbnode *node) +{ + return node ? node->data : 0; +} + +static int cmpaddr(const void *ap, const void *bp) +{ + return ap < bp ? -1 : (ap > bp ? 1 : 0); +} + +static int cmpint(const void *ap, const void *bp) +{ + return PTR2INT(ap) - PTR2INT(bp); +} + + +/* ---- left-leaning 2-3 red-black implementation ---- */ + +/* helper prototypes */ +static int is_red(struct rbnode *tree); +static void color_flip(struct rbnode *tree); +static struct rbnode *rot_left(struct rbnode *a); +static struct rbnode *rot_right(struct rbnode *a); +static struct rbnode *find_min(struct rbnode *tree); +static struct rbnode *del_min(struct rbtree *rb, struct rbnode *tree); +/*static struct rbnode *move_red_right(struct rbnode *tree);*/ +static struct rbnode *move_red_left(struct rbnode *tree); +static struct rbnode *fix_up(struct rbnode *tree); + +static int count_nodes(struct rbnode *node) +{ + if(!node) + return 0; + + return 1 + count_nodes(node->left) + count_nodes(node->right); +} + +static void del_tree(struct rbnode *node, rb_del_func_t delfunc, void *cls) +{ + if(!node) + return; + + del_tree(node->left, delfunc, cls); + del_tree(node->right, delfunc, cls); + + if(delfunc) { + delfunc(node, cls); + } + free(node); +} + +static struct rbnode *insert(struct rbtree *rb, struct rbnode *tree, void *key, void *data) +{ + int cmp; + + if(!tree) { + struct rbnode *node = rb->alloc(sizeof *node); + node->red = 1; + node->key = key; + node->data = data; + node->left = node->right = 0; + return node; + } + + cmp = rb->cmp(key, tree->key); + + if(cmp < 0) { + tree->left = insert(rb, tree->left, key, data); + } else if(cmp > 0) { + tree->right = insert(rb, tree->right, key, data); + } else { + tree->data = data; + } + + /* fix right-leaning reds */ + if(is_red(tree->right)) { + tree = rot_left(tree); + } + /* fix two reds in a row */ + if(is_red(tree->left) && is_red(tree->left->left)) { + tree = rot_right(tree); + } + + /* if 4-node, split it by color inversion */ + if(is_red(tree->left) && is_red(tree->right)) { + color_flip(tree); + } + + return tree; +} + +static struct rbnode *delete(struct rbtree *rb, struct rbnode *tree, void *key) +{ + int cmp; + + if(!tree) { + return 0; + } + + cmp = rb->cmp(key, tree->key); + + if(cmp < 0) { + if(!is_red(tree->left) && !is_red(tree->left->left)) { + tree = move_red_left(tree); + } + tree->left = delete(rb, tree->left, key); + } else { + /* need reds on the right */ + if(is_red(tree->left)) { + tree = rot_right(tree); + } + + /* found it at the bottom (XXX what certifies left is null?) */ + if(cmp == 0 && !tree->right) { + if(rb->del) { + rb->del(tree, rb->del_cls); + } + rb->free(tree); + return 0; + } + + if(!is_red(tree->right) && !is_red(tree->right->left)) { + tree = move_red_left(tree); + } + + if(key == tree->key) { + struct rbnode *rmin = find_min(tree->right); + tree->key = rmin->key; + tree->data = rmin->data; + tree->right = del_min(rb, tree->right); + } else { + tree->right = delete(rb, tree->right, key); + } + } + + return fix_up(tree); +} + +/*static struct rbnode *find(struct rbtree *rb, struct rbnode *node, void *key) +{ + int cmp; + + if(!node) + return 0; + + if((cmp = rb->cmp(key, node->key)) == 0) { + return node; + } + return find(rb, cmp < 0 ? node->left : node->right, key); +}*/ + +static void traverse(struct rbnode *node, void (*func)(struct rbnode*, void*), void *cls) +{ + if(!node) + return; + + traverse(node->left, func, cls); + func(node, cls); + traverse(node->right, func, cls); +} + +/* helpers */ + +static int is_red(struct rbnode *tree) +{ + return tree && tree->red; +} + +static void color_flip(struct rbnode *tree) +{ + tree->red = !tree->red; + tree->left->red = !tree->left->red; + tree->right->red = !tree->right->red; +} + +static struct rbnode *rot_left(struct rbnode *a) +{ + struct rbnode *b = a->right; + a->right = b->left; + b->left = a; + b->red = a->red; + a->red = 1; + return b; +} + +static struct rbnode *rot_right(struct rbnode *a) +{ + struct rbnode *b = a->left; + a->left = b->right; + b->right = a; + b->red = a->red; + a->red = 1; + return b; +} + +static struct rbnode *find_min(struct rbnode *tree) +{ + if(!tree) + return 0; + + while(tree->left) { + tree = tree->left; + } + return tree; +} + +static struct rbnode *del_min(struct rbtree *rb, struct rbnode *tree) +{ + if(!tree->left) { + if(rb->del) { + rb->del(tree->left, rb->del_cls); + } + rb->free(tree->left); + return 0; + } + + /* make sure we've got red (3/4-nodes) at the left side so we can delete at the bottom */ + if(!is_red(tree->left) && !is_red(tree->left->left)) { + tree = move_red_left(tree); + } + tree->left = del_min(rb, tree->left); + + /* fix right-reds, red-reds, and split 4-nodes on the way up */ + return fix_up(tree); +} + +#if 0 +/* push a red link on this node to the right */ +static struct rbnode *move_red_right(struct rbnode *tree) +{ + /* flipping it makes both children go red, so we have a red to the right */ + color_flip(tree); + + /* if after the flip we've got a red-red situation to the left, fix it */ + if(is_red(tree->left->left)) { + tree = rot_right(tree); + color_flip(tree); + } + return tree; +} +#endif + +/* push a red link on this node to the left */ +static struct rbnode *move_red_left(struct rbnode *tree) +{ + /* flipping it makes both children go red, so we have a red to the left */ + color_flip(tree); + + /* if after the flip we've got a red-red on the right-left, fix it */ + if(is_red(tree->right->left)) { + tree->right = rot_right(tree->right); + tree = rot_left(tree); + color_flip(tree); + } + return tree; +} + +static struct rbnode *fix_up(struct rbnode *tree) +{ + /* fix right-leaning */ + if(is_red(tree->right)) { + tree = rot_left(tree); + } + /* change invalid red-red pairs into a proper 4-node */ + if(is_red(tree->left) && is_red(tree->left->left)) { + tree = rot_right(tree); + } + /* split 4-nodes */ + if(is_red(tree->left) && is_red(tree->right)) { + color_flip(tree); + } + return tree; +} diff --git a/src/rbtree.h b/src/rbtree.h new file mode 100644 index 0000000..8688c7f --- /dev/null +++ b/src/rbtree.h @@ -0,0 +1,78 @@ +/* +rbtree - simple balanced binary search tree (red-black tree) library. +Copyright (C) 2011-2014 John Tsiombikas + +rbtree is free software, feel free to use, modify, and redistribute it, under +the terms of the 3-clause BSD license. See COPYING for details. + */ +#ifndef RBTREE_H_ +#define RBTREE_H_ + +struct rbtree; + + +struct rbnode { + void *key, *data; + int red; + struct rbnode *left, *right; + struct rbnode *next; /* for iterator stack */ +}; + + +typedef void *(*rb_alloc_func_t)(size_t); +typedef void (*rb_free_func_t)(void*); + +typedef int (*rb_cmp_func_t)(const void*, const void*); +typedef void (*rb_del_func_t)(struct rbnode*, void*); + +#define RB_KEY_ADDR (rb_cmp_func_t)(0) +#define RB_KEY_INT (rb_cmp_func_t)(1) +#define RB_KEY_STRING (rb_cmp_func_t)(3) + + +#ifdef __cplusplus +extern "C" { +#endif + +struct rbtree *rb_create(rb_cmp_func_t cmp_func); +void rb_free(struct rbtree *rb); + +int rb_init(struct rbtree *rb, rb_cmp_func_t cmp_func); +void rb_destroy(struct rbtree *rb); + +void rb_set_allocator(struct rbtree *rb, rb_alloc_func_t alloc, rb_free_func_t free); +void rb_set_compare_func(struct rbtree *rb, rb_cmp_func_t func); +void rb_set_delete_func(struct rbtree *rb, rb_del_func_t func, void *cls); +/* TODO add user deep copy function */ + +void rb_clear(struct rbtree *rb); +int rb_copy(struct rbtree *dest, struct rbtree *src); + +int rb_size(struct rbtree *rb); + +int rb_insert(struct rbtree *rb, void *key, void *data); +int rb_inserti(struct rbtree *rb, int key, void *data); + +int rb_delete(struct rbtree *rb, void *key); +int rb_deletei(struct rbtree *rb, int key); + +struct rbnode *rb_find(struct rbtree *rb, void *key); +struct rbnode *rb_findi(struct rbtree *rb, int key); + +void rb_foreach(struct rbtree *rb, void (*func)(struct rbnode*, void*), void *cls); + +struct rbnode *rb_root(struct rbtree *rb); + +void rb_begin(struct rbtree *rb); +struct rbnode *rb_next(struct rbtree *rb); + +void *rb_node_key(struct rbnode *node); +int rb_node_keyi(struct rbnode *node); +void *rb_node_data(struct rbnode *node); + +#ifdef __cplusplus +} +#endif + + +#endif /* RBTREE_H_ */ -- 1.7.10.4