crude metaballs

diff --git a/src/3dgfx/3dgfx.c b/src/3dgfx/3dgfx.c
index ac50929..64b7c0e 100644 (file)
--- a/src/3dgfx/3dgfx.c
+++ b/src/3dgfx/3dgfx.c
@@ -628,69 +628,33 @@ void g3d_draw_indexed(int prim, const struct g3d_vertex *varr, int varr_size,
                }
 #endif
 
-               switch(vnum) {
-               case 1:
-                       /*
-                       if(st->opt & (G3D_ALPHA_BLEND | G3D_ADD_BLEND)) {
-                               int r, g, b, inv_alpha;
-                               g3d_pixel *dest = pfill_fb.pixels + (pv[0].y >> 8) * st->width + (pv[0].x >> 8);
-                               if(st->opt & G3D_ALPHA_BLEND) {
-                                       inv_alpha = 255 - pv[0].a;
-                                       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;
-                               } else {
-                                       r = (int)pv[0].r + G3D_UNPACK_R(*dest);
-                                       g = (int)pv[0].g + G3D_UNPACK_G(*dest);
-                                       b = (int)pv[0].b + G3D_UNPACK_B(*dest);
-                                       if(r > 255) r = 255;
-                                       if(g > 255) g = 255;
-                                       if(b > 255) b = 255;
-                               }
-                               *dest++ = G3D_PACK_RGB(r, g, b);
-                       } else {
-                               g3d_pixel *dest = pfill_fb.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 = pv[0].l;
-                               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_ALPHA_BLEND) {
-                               fill_mode |= POLYFILL_ALPHA_BIT;
-                       } else if(st->opt & G3D_ADD_BLEND) {
-                               fill_mode |= POLYFILL_ADD_BIT;
-                       }
-                       */
+               fill_mode = st->polymode;
+               if(st->opt & G3D_TEXTURE_2D) {
+                       fill_mode |= POLYFILL_TEX_BIT;
+               }
+               /*
+               if(st->opt & G3D_ALPHA_BLEND) {
+                  fill_mode |= POLYFILL_ALPHA_BIT;
+               } else if(st->opt & G3D_ADD_BLEND) {
+                  fill_mode |= POLYFILL_ADD_BIT;
+               }
+               */
 #ifdef ENABLE_ZBUFFER
-                       if(st->opt & G3D_DEPTH_TEST) {
-                               fill_mode |= POLYFILL_ZBUF_BIT;
-                       }
+               if(st->opt & G3D_DEPTH_TEST) {
+                       fill_mode |= POLYFILL_ZBUF_BIT;
+               }
 #endif
-                       num_tri = vnum - 2;
-                       vtri = v;
-                       pvtri = pv;
-                       for(;;) {
-                               calc_grad(vtri);
-                               polyfill(fill_mode, pvtri);
-                               if(--num_tri == 0) break;
-                               vtri[1] = vtri[0];
-                               pvtri[1] = pvtri[0];
-                               vtri++;
-                               pvtri++;
-                       }
+               num_tri = vnum - 2;
+               vtri = v;
+               pvtri = pv;
+               for(;;) {
+                       calc_grad(vtri);
+                       polyfill(fill_mode, pvtri);
+                       if(--num_tri == 0) break;
+                       vtri[1] = vtri[0];
+                       pvtri[1] = pvtri[0];
+                       vtri++;
+                       pvtri++;
                }
        }
 }

diff --git a/src/3dgfx/3dgfx.h b/src/3dgfx/3dgfx.h
index 7bed815..db590ab 100644 (file)
--- a/src/3dgfx/3dgfx.h
+++ b/src/3dgfx/3dgfx.h
@@ -51,7 +51,6 @@ enum { G3D_CCW, G3D_CW };
 
 /* arg to g3d_polygon_mode */
 enum {
-       G3D_WIRE,
        G3D_FLAT,
        G3D_GOURAUD
 };

diff --git a/src/3dgfx/polyfill.c b/src/3dgfx/polyfill.c
index 9d12351..5cedf11 100644 (file)
--- a/src/3dgfx/polyfill.c
+++ b/src/3dgfx/polyfill.c
@@ -9,31 +9,20 @@
 
 /*#define DEBUG_OVERDRAW       G3D_PACK_RGB(10, 10, 10)*/
 
-#define FILL_POLY_BITS 0x03
-
-/*void polyfill_tex_flat_new(struct pvertex *varr);*/
-
-/* mode bits: 00-wire 01-flat 10-gouraud 11-reserved
- *     bit 2: texture
- *     bit 3: zbuffering
+/* mode bits:
+ *     bit 0: gouraud
+ *     bit 1: texture
+ *     bit 2: zbuffering
  */
 void (*fillfunc[])(struct pvertex*) = {
-       polyfill_wire,
        polyfill_flat,
        polyfill_gouraud,
-       0,
-       polyfill_tex_wire,
        polyfill_tex_flat,
        polyfill_tex_gouraud,
-       0,
-       polyfill_wire,
        polyfill_flat_zbuf,
        polyfill_gouraud_zbuf,
-       0,
-       polyfill_tex_wire,
        polyfill_tex_flat_zbuf,
-       polyfill_tex_gouraud_zbuf,
-       0,
+       polyfill_tex_gouraud_zbuf
 };
 
 struct pimage pfill_fb, pfill_tex;
@@ -92,54 +81,6 @@ void polyfill(int mode, struct pvertex *verts)
        fillfunc[mode](verts);
 }
 
-void polyfill_wire(struct pvertex *verts)
-{
-       int i, x0, y0, x1, y1;
-       struct pvertex *v = verts;
-       int color = find_color(v->l, v->l, v->l);
-
-       for(i=0; i<2; i++) {
-               x0 = v->x >> 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)
-{
-       polyfill_wire(verts);   /* TODO */
-}
-
-void polyfill_alpha_wire(struct pvertex *verts)
-{
-       polyfill_wire(verts);   /* TODO */
-}
-
-void polyfill_alpha_tex_wire(struct pvertex *verts)
-{
-       polyfill_wire(verts);   /* TODO */
-}
-
-void polyfill_add_wire(struct pvertex *verts)
-{
-       polyfill_wire(verts);   /* TODO */
-}
-
-void polyfill_add_tex_wire(struct pvertex *verts)
-{
-       polyfill_wire(verts);   /* TODO */
-}
-
 #define VNEXT(p)       (((p) == varr + 2) ? varr : (p) + 1)
 #define VPREV(p)       ((p) == varr ? varr + 2 : (p) - 1)
 #define VSUCC(p, side) ((side) == 0 ? VNEXT(p) : VPREV(p))
@@ -207,125 +148,3 @@ void polyfill_add_tex_wire(struct pvertex *verts)
 #define ZBUF
 #include "polytmpl.h"
 #undef POLYFILL
-
-#if 0
-void polyfill_tex_flat_new(struct pvertex *varr)
-{
-       int i, line, top, bot;
-       struct pvertex *v, *vn, *tab;
-       int32_t x, y0, y1, dx, dy, slope, fx, fy;
-       int start, len;
-       g3d_pixel *fbptr, *pptr, color;
-       int32_t tu, tv, du, dv, uslope, vslope;
-       int tx, ty;
-       g3d_pixel texel;
-
-       top = pfill_fb.height;
-       bot = 0;
-
-       for(i=0; i<3; i++) {
-               /* scan the edge between the current and next vertex */
-               v = varr + i;
-               vn = VNEXT(v);
-
-               if(vn->y == v->y) continue;     /* XXX ??? */
-
-               if(vn->y >= v->y) {
-                       /* inrementing Y: left side */
-                       tab = left;
-               } else {
-                       /* decrementing Y: right side, flip vertices to trace bottom->up */
-                       tab = right;
-                       v = vn;
-                       vn = varr + i;
-               }
-
-               /* calculate edge slope */
-               dx = vn->x - v->x;
-               dy = vn->y - v->y;
-               slope = (dx << 8) / dy;
-
-               tu = v->u;
-               tv = v->v;
-               du = vn->u - tu;
-               dv = vn->v - tv;
-               uslope = (du << 8) / dy;
-               vslope = (dv << 8) / dy;
-
-               y0 = (v->y + 0x100) & 0xffffff00;       /* start from the next scanline */
-               fy = y0 - v->y;                                         /* fractional part before the next scanline */
-               fx = (fy * slope) >> 8;                         /* X adjust for the step to the next scanline */
-               x = v->x + fx;                                          /* adjust X */
-               y1 = vn->y & 0xffffff00;                        /* last scanline of the edge <= vn->y */
-
-               /* also adjust other interpolated attributes */
-               tu += (fy * uslope) >> 8;
-               tv += (fy * vslope) >> 8;
-
-               line = y0 >> 8;
-               if(line < top) top = line;
-               if((y1 >> 8) > bot) bot = y1 >> 8;
-
-               if(line > 0) tab += line;
-
-               while(line <= (y1 >> 8) && line < pfill_fb.height) {
-                       if(line >= 0) {
-                               int val = x < 0 ? 0 : x >> 8;
-                               tab->x = val < pfill_fb.width ? val : pfill_fb.width - 1;
-                               tab->u = tu;
-                               tab->v = tv;
-                               tab++;
-                       }
-                       x += slope;
-                       tu += uslope;
-                       tv += vslope;
-                       line++;
-               }
-       }
-
-       if(top < 0) top = 0;
-       if(bot >= pfill_fb.height) bot = pfill_fb.height - 1;
-
-       fbptr = pfill_fb.pixels + top * pfill_fb.width;
-       for(i=top; i<=bot; i++) {
-               start = left[i].x;
-               len = right[i].x - start;
-               /* XXX we probably need more precision in left/right.x */
-
-               dx = len == 0 ? 256 : (len << 8);
-
-               tu = left[i].u;
-               tv = left[i].v;
-
-               pptr = fbptr + start;
-               while(len-- > 0) {
-                       int cr, cg, cb;
-
-                       tx = (tu >> (16 - pfill_tex.xshift)) & pfill_tex.xmask;
-                       ty = (tv >> (16 - pfill_tex.yshift)) & pfill_tex.ymask;
-                       texel = pfill_tex.pixels[(ty << pfill_tex.xshift) + tx];
-
-                       tu += pgrad.dudx;
-                       tv += pgrad.dvdx;
-
-                       cr = varr[0].r;
-                       cg = varr[0].g;
-                       cb = varr[0].b;
-
-                       /* 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;
-
-                       if(cr >= 255) cr = 255;
-                       if(cg >= 255) cg = 255;
-                       if(cb >= 255) cb = 255;
-                       color = G3D_PACK_RGB(cr, cg, cb);
-                       *pptr++ = color;
-               }
-               fbptr += pfill_fb.width;
-       }
-}
-#endif

diff --git a/src/3dgfx/polyfill.h b/src/3dgfx/polyfill.h
index 5a4515c..26c65f3 100644 (file)
--- a/src/3dgfx/polyfill.h
+++ b/src/3dgfx/polyfill.h
@@ -4,24 +4,17 @@
 #include "inttypes.h"
 #include "3dgfx.h"
 
-#define POLYFILL_MODE_MASK     0x03
-#define POLYFILL_TEX_BIT       0x04
-#define POLYFILL_ZBUF_BIT      0x08
+#define POLYFILL_MODE_MASK     0x01
+#define POLYFILL_TEX_BIT       0x02
+#define POLYFILL_ZBUF_BIT      0x04
 
 enum {
-       POLYFILL_WIRE                   = 0,
        POLYFILL_FLAT,
        POLYFILL_GOURAUD,
-
-       POLYFILL_TEX_WIRE               = 4,
        POLYFILL_TEX_FLAT,
        POLYFILL_TEX_GOURAUD,
-
-       POLYFILL_WIRE_ZBUF                      = 8,
        POLYFILL_FLAT_ZBUF,
        POLYFILL_GOURAUD_ZBUF,
-
-       POLYFILL_TEX_WIRE_ZBUF          = 12,
        POLYFILL_TEX_FLAT_ZBUF,
        POLYFILL_TEX_GOURAUD_ZBUF
 };
@@ -57,10 +50,8 @@ void polyfill_fbheight(int height);
 
 void polyfill(int mode, struct pvertex *verts);
 
-void polyfill_wire(struct pvertex *verts);
 void polyfill_flat(struct pvertex *verts);
 void polyfill_gouraud(struct pvertex *verts);
-void polyfill_tex_wire(struct pvertex *verts);
 void polyfill_tex_flat(struct pvertex *verts);
 void polyfill_tex_gouraud(struct pvertex *verts);
 void polyfill_flat_zbuf(struct pvertex *verts);

diff --git a/src/game.c b/src/game.c
index c22135c..d474993 100644 (file)
--- a/src/game.c
+++ b/src/game.c
@@ -1,13 +1,39 @@
+#include <stdio.h>
 #include <string.h>
+#include <math.h>
 #include "game.h"
 #include "colormgr.h"
 #include "3dgfx.h"
 #include "mesh.h"
+#include "metasurf.h"
+#include "util.h"
+
+#define BBOX_SIZE              10.0f
+#define BBOX_HSZ               (BBOX_SIZE / 2.0f)
+#define VOX_RES                        30
+#define VOX_STEP               (BBOX_SIZE / (float)VOX_RES)
+
+#define VBUF_MAX_TRIS  256
+#define VBUF_SIZE              (VBUF_MAX_TRIS * 3)
+
+struct mball {
+       float energy;
+       float x, y, z;
+};
 
 static struct g3d_mesh mesh;
+static struct g3d_vertex *vbuf;
+static struct metasurface *msurf;
+static struct mball *balls;
+static int num_balls;
+
+static void update(float tsec);
+static void draw_metaballs(void);
 
 int game_init(void)
 {
+       int i;
+
        init_colormgr();
 
        g3d_init();
@@ -28,6 +54,24 @@ int game_init(void)
        g3d_polygon_mode(G3D_GOURAUD);
 
        gen_torus_mesh(&mesh, 2.0, 0.7, 24, 12);
+
+       if(!(msurf = msurf_create())) {
+               return -1;
+       }
+       msurf_set_threshold(msurf, 8);
+       msurf_set_inside(msurf, MSURF_GREATER);
+       msurf_set_bounds(msurf, -BBOX_HSZ, -BBOX_HSZ, -BBOX_HSZ, BBOX_HSZ, BBOX_HSZ, BBOX_HSZ);
+       msurf_set_resolution(msurf, VOX_RES, VOX_RES, VOX_RES);
+       msurf_enable(msurf, MSURF_NORMALIZE);
+
+       vbuf = malloc_nf(VBUF_SIZE * sizeof *vbuf);
+
+       num_balls = 1;
+       balls = calloc_nf(num_balls, sizeof *balls);
+
+       for(i=0; i<num_balls; i++) {
+               balls[i].energy = 20;
+       }
        return 0;
 }
 
@@ -35,24 +79,103 @@ void game_shutdown(void)
 {
 }
 
+static void update(float tsec)
+{
+       int i, j, k, n;
+       float x, y, z, dx, dy, dz, dsq, energy;
+       float *vox = msurf_voxels(msurf);
+
+       for(i=0; i<num_balls; i++) {
+               balls[i].y = sin(tsec) * 5.0f;
+       }
+
+       for(i=0; i<VOX_RES; i++) {
+               z = -BBOX_HSZ + i * VOX_STEP;
+               for(j=0; j<VOX_RES; j++) {
+                       y = -BBOX_HSZ + j * VOX_STEP;
+                       for(k=0; k<VOX_RES; k++) {
+                               x = -BBOX_HSZ + k * VOX_STEP;
+
+                               /* initialize with the vertical distance for the pool */
+                               energy = BBOX_HSZ * 0.8 - y;
+
+                               /* add the contribution of the balls */
+                               for(n=0; n<num_balls; n++) {
+                                       dx = x - balls[n].x;
+                                       dy = y - balls[n].y;
+                                       dz = z - balls[n].z;
+                                       dsq = dx * dx + dy * dy + dz * dz;
+
+                                       energy += balls[n].energy / dsq;
+                               }
+                               *vox++ = energy;
+                       }
+               }
+       }
+
+       msurf_polygonize(msurf);
+}
+
 void game_draw(void)
 {
        unsigned long msec = game_getmsec();
        float tsec = (float)msec / 1000.0f;
 
+       update(tsec);
+
        g3d_clear(G3D_COLOR_BUFFER_BIT | G3D_DEPTH_BUFFER_BIT);
 
        g3d_matrix_mode(G3D_MODELVIEW);
        g3d_load_identity();
-       g3d_translate(0, 0, -8);
-       g3d_rotate(tsec * 50.0f, 1, 0, 0);
+       g3d_translate(0, 0, -15);
+       /*g3d_rotate(tsec * 50.0f, 1, 0, 0);
        g3d_rotate(tsec * 30.0f, 0, 0, 1);
 
-       draw_mesh(&mesh);
+       draw_mesh(&mesh);*/
+       draw_metaballs();
 
        game_swap_buffers();
 }
 
+static void draw_metaballs(void)
+{
+       int i, nverts, vbuf_count;
+       float *varr, *narr;
+       struct g3d_vertex *vbptr;
+       static int nfrm;
+
+       nverts = msurf_vertex_count(msurf);
+       varr = msurf_vertices(msurf);
+       narr = msurf_normals(msurf);
+
+       vbptr = vbuf;
+       for(i=0; i<nverts; i++) {
+               vbuf_count = vbptr - vbuf;
+               if(vbuf_count >= VBUF_SIZE) {
+                       g3d_draw(G3D_TRIANGLES, vbuf, vbuf_count);
+                       vbptr = vbuf;
+               }
+               vbptr->x = varr[0];
+               vbptr->y = varr[1];
+               vbptr->z = varr[2];
+               vbptr->w = 1.0f;
+               vbptr->nx = narr[0];
+               vbptr->ny = narr[1];
+               vbptr->nz = narr[2];
+               vbptr->w = 1.0f;
+               vbptr->l = 255;
+               vbptr++;
+               varr += 3;
+               narr += 3;
+       }
+
+       if(vbptr > vbuf) {
+               g3d_draw(G3D_TRIANGLES, vbuf, vbptr - vbuf);
+       }
+
+       nfrm++;
+}
+
 void game_keyboard(int key, int press)
 {
        if(key == 27) game_quit();

diff --git a/src/gfxutil.c b/src/gfxutil.c
index a472192..ff9df6f 100644 (file)
--- a/src/gfxutil.c
+++ b/src/gfxutil.c
@@ -4,6 +4,7 @@
 #include "gfxutil.h"
 #include "3dgfx/3dgfx.h"
 
+#if 0
 enum {
        IN              = 0,
        LEFT    = 1,
@@ -145,6 +146,7 @@ void draw_line(int x0, int y0, int x1, int y1, unsigned char color)
                }
        }
 }
+#endif
 
 void draw_billboard(float x, float y, float z, float size, int lum, int a)
 {

diff --git a/src/loader.asm b/src/loader.asm
index 9f0ca30..f1ef659 100644 (file)
--- a/src/loader.asm
+++ b/src/loader.asm
@@ -17,10 +17,12 @@ _start:
        mov ds, ax
        mov es, ax
        mov fs, ax      ; this will store the original real mode segment
-       mov ss, ax
        ; modify the return to real mode jump segment
        mov [.jmpcs16 + 3], ax
 
+       ; put the stack on the next segment, should be free 
+       add ax, 1000h
+       mov ss, ax
        mov ax, 0xfffe
        mov sp, ax
 
@@ -111,6 +113,7 @@ _start:
        mov ax, 13h
        int 10h
 
+       cli     ; paranoid
        lgdt [gdt_lim]
 
        mov eax, cr0

diff --git a/src/mcubes.h b/src/mcubes.h
new file mode 100644 (file)
index 0000000..2a9034d
--- /dev/null
+++ b/src/mcubes.h
@@ -0,0 +1,294 @@
+static int mc_edge_table[256] = {
+       0x0  , 0x109, 0x203, 0x30a, 0x406, 0x50f, 0x605, 0x70c,
+       0x80c, 0x905, 0xa0f, 0xb06, 0xc0a, 0xd03, 0xe09, 0xf00,
+       0x190, 0x99 , 0x393, 0x29a, 0x596, 0x49f, 0x795, 0x69c,
+       0x99c, 0x895, 0xb9f, 0xa96, 0xd9a, 0xc93, 0xf99, 0xe90,
+       0x230, 0x339, 0x33 , 0x13a, 0x636, 0x73f, 0x435, 0x53c,
+       0xa3c, 0xb35, 0x83f, 0x936, 0xe3a, 0xf33, 0xc39, 0xd30,
+       0x3a0, 0x2a9, 0x1a3, 0xaa , 0x7a6, 0x6af, 0x5a5, 0x4ac,
+       0xbac, 0xaa5, 0x9af, 0x8a6, 0xfaa, 0xea3, 0xda9, 0xca0,
+       0x460, 0x569, 0x663, 0x76a, 0x66 , 0x16f, 0x265, 0x36c,
+       0xc6c, 0xd65, 0xe6f, 0xf66, 0x86a, 0x963, 0xa69, 0xb60,
+       0x5f0, 0x4f9, 0x7f3, 0x6fa, 0x1f6, 0xff , 0x3f5, 0x2fc,
+       0xdfc, 0xcf5, 0xfff, 0xef6, 0x9fa, 0x8f3, 0xbf9, 0xaf0,
+       0x650, 0x759, 0x453, 0x55a, 0x256, 0x35f, 0x55 , 0x15c,
+       0xe5c, 0xf55, 0xc5f, 0xd56, 0xa5a, 0xb53, 0x859, 0x950,
+       0x7c0, 0x6c9, 0x5c3, 0x4ca, 0x3c6, 0x2cf, 0x1c5, 0xcc ,
+       0xfcc, 0xec5, 0xdcf, 0xcc6, 0xbca, 0xac3, 0x9c9, 0x8c0,
+       0x8c0, 0x9c9, 0xac3, 0xbca, 0xcc6, 0xdcf, 0xec5, 0xfcc,
+       0xcc , 0x1c5, 0x2cf, 0x3c6, 0x4ca, 0x5c3, 0x6c9, 0x7c0,
+       0x950, 0x859, 0xb53, 0xa5a, 0xd56, 0xc5f, 0xf55, 0xe5c,
+       0x15c, 0x55 , 0x35f, 0x256, 0x55a, 0x453, 0x759, 0x650,
+       0xaf0, 0xbf9, 0x8f3, 0x9fa, 0xef6, 0xfff, 0xcf5, 0xdfc,
+       0x2fc, 0x3f5, 0xff , 0x1f6, 0x6fa, 0x7f3, 0x4f9, 0x5f0,
+       0xb60, 0xa69, 0x963, 0x86a, 0xf66, 0xe6f, 0xd65, 0xc6c,
+       0x36c, 0x265, 0x16f, 0x66 , 0x76a, 0x663, 0x569, 0x460,
+       0xca0, 0xda9, 0xea3, 0xfaa, 0x8a6, 0x9af, 0xaa5, 0xbac,
+       0x4ac, 0x5a5, 0x6af, 0x7a6, 0xaa , 0x1a3, 0x2a9, 0x3a0,
+       0xd30, 0xc39, 0xf33, 0xe3a, 0x936, 0x83f, 0xb35, 0xa3c,
+       0x53c, 0x435, 0x73f, 0x636, 0x13a, 0x33 , 0x339, 0x230,
+       0xe90, 0xf99, 0xc93, 0xd9a, 0xa96, 0xb9f, 0x895, 0x99c,
+       0x69c, 0x795, 0x49f, 0x596, 0x29a, 0x393, 0x99 , 0x190,
+       0xf00, 0xe09, 0xd03, 0xc0a, 0xb06, 0xa0f, 0x905, 0x80c,
+       0x70c, 0x605, 0x50f, 0x406, 0x30a, 0x203, 0x109, 0x0
+};
+
+
+static int mc_tri_table[256][16] = {
+       {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {0, 8, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {0, 1, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {1, 8, 3, 9, 8, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {1, 2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {0, 8, 3, 1, 2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {9, 2, 10, 0, 2, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {2, 8, 3, 2, 10, 8, 10, 9, 8, -1, -1, -1, -1, -1, -1, -1},
+       {3, 11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {0, 11, 2, 8, 11, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {1, 9, 0, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {1, 11, 2, 1, 9, 11, 9, 8, 11, -1, -1, -1, -1, -1, -1, -1},
+       {3, 10, 1, 11, 10, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {0, 10, 1, 0, 8, 10, 8, 11, 10, -1, -1, -1, -1, -1, -1, -1},
+       {3, 9, 0, 3, 11, 9, 11, 10, 9, -1, -1, -1, -1, -1, -1, -1},
+       {9, 8, 10, 10, 8, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {4, 7, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {4, 3, 0, 7, 3, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {0, 1, 9, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {4, 1, 9, 4, 7, 1, 7, 3, 1, -1, -1, -1, -1, -1, -1, -1},
+       {1, 2, 10, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {3, 4, 7, 3, 0, 4, 1, 2, 10, -1, -1, -1, -1, -1, -1, -1},
+       {9, 2, 10, 9, 0, 2, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1},
+       {2, 10, 9, 2, 9, 7, 2, 7, 3, 7, 9, 4, -1, -1, -1, -1},
+       {8, 4, 7, 3, 11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {11, 4, 7, 11, 2, 4, 2, 0, 4, -1, -1, -1, -1, -1, -1, -1},
+       {9, 0, 1, 8, 4, 7, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1},
+       {4, 7, 11, 9, 4, 11, 9, 11, 2, 9, 2, 1, -1, -1, -1, -1},
+       {3, 10, 1, 3, 11, 10, 7, 8, 4, -1, -1, -1, -1, -1, -1, -1},
+       {1, 11, 10, 1, 4, 11, 1, 0, 4, 7, 11, 4, -1, -1, -1, -1},
+       {4, 7, 8, 9, 0, 11, 9, 11, 10, 11, 0, 3, -1, -1, -1, -1},
+       {4, 7, 11, 4, 11, 9, 9, 11, 10, -1, -1, -1, -1, -1, -1, -1},
+       {9, 5, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {9, 5, 4, 0, 8, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {0, 5, 4, 1, 5, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {8, 5, 4, 8, 3, 5, 3, 1, 5, -1, -1, -1, -1, -1, -1, -1},
+       {1, 2, 10, 9, 5, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {3, 0, 8, 1, 2, 10, 4, 9, 5, -1, -1, -1, -1, -1, -1, -1},
+       {5, 2, 10, 5, 4, 2, 4, 0, 2, -1, -1, -1, -1, -1, -1, -1},
+       {2, 10, 5, 3, 2, 5, 3, 5, 4, 3, 4, 8, -1, -1, -1, -1},
+       {9, 5, 4, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {0, 11, 2, 0, 8, 11, 4, 9, 5, -1, -1, -1, -1, -1, -1, -1},
+       {0, 5, 4, 0, 1, 5, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1},
+       {2, 1, 5, 2, 5, 8, 2, 8, 11, 4, 8, 5, -1, -1, -1, -1},
+       {10, 3, 11, 10, 1, 3, 9, 5, 4, -1, -1, -1, -1, -1, -1, -1},
+       {4, 9, 5, 0, 8, 1, 8, 10, 1, 8, 11, 10, -1, -1, -1, -1},
+       {5, 4, 0, 5, 0, 11, 5, 11, 10, 11, 0, 3, -1, -1, -1, -1},
+       {5, 4, 8, 5, 8, 10, 10, 8, 11, -1, -1, -1, -1, -1, -1, -1},
+       {9, 7, 8, 5, 7, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {9, 3, 0, 9, 5, 3, 5, 7, 3, -1, -1, -1, -1, -1, -1, -1},
+       {0, 7, 8, 0, 1, 7, 1, 5, 7, -1, -1, -1, -1, -1, -1, -1},
+       {1, 5, 3, 3, 5, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {9, 7, 8, 9, 5, 7, 10, 1, 2, -1, -1, -1, -1, -1, -1, -1},
+       {10, 1, 2, 9, 5, 0, 5, 3, 0, 5, 7, 3, -1, -1, -1, -1},
+       {8, 0, 2, 8, 2, 5, 8, 5, 7, 10, 5, 2, -1, -1, -1, -1},
+       {2, 10, 5, 2, 5, 3, 3, 5, 7, -1, -1, -1, -1, -1, -1, -1},
+       {7, 9, 5, 7, 8, 9, 3, 11, 2, -1, -1, -1, -1, -1, -1, -1},
+       {9, 5, 7, 9, 7, 2, 9, 2, 0, 2, 7, 11, -1, -1, -1, -1},
+       {2, 3, 11, 0, 1, 8, 1, 7, 8, 1, 5, 7, -1, -1, -1, -1},
+       {11, 2, 1, 11, 1, 7, 7, 1, 5, -1, -1, -1, -1, -1, -1, -1},
+       {9, 5, 8, 8, 5, 7, 10, 1, 3, 10, 3, 11, -1, -1, -1, -1},
+       {5, 7, 0, 5, 0, 9, 7, 11, 0, 1, 0, 10, 11, 10, 0, -1},
+       {11, 10, 0, 11, 0, 3, 10, 5, 0, 8, 0, 7, 5, 7, 0, -1},
+       {11, 10, 5, 7, 11, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {10, 6, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {0, 8, 3, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {9, 0, 1, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {1, 8, 3, 1, 9, 8, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1},
+       {1, 6, 5, 2, 6, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {1, 6, 5, 1, 2, 6, 3, 0, 8, -1, -1, -1, -1, -1, -1, -1},
+       {9, 6, 5, 9, 0, 6, 0, 2, 6, -1, -1, -1, -1, -1, -1, -1},
+       {5, 9, 8, 5, 8, 2, 5, 2, 6, 3, 2, 8, -1, -1, -1, -1},
+       {2, 3, 11, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {11, 0, 8, 11, 2, 0, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1},
+       {0, 1, 9, 2, 3, 11, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1},
+       {5, 10, 6, 1, 9, 2, 9, 11, 2, 9, 8, 11, -1, -1, -1, -1},
+       {6, 3, 11, 6, 5, 3, 5, 1, 3, -1, -1, -1, -1, -1, -1, -1},
+       {0, 8, 11, 0, 11, 5, 0, 5, 1, 5, 11, 6, -1, -1, -1, -1},
+       {3, 11, 6, 0, 3, 6, 0, 6, 5, 0, 5, 9, -1, -1, -1, -1},
+       {6, 5, 9, 6, 9, 11, 11, 9, 8, -1, -1, -1, -1, -1, -1, -1},
+       {5, 10, 6, 4, 7, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {4, 3, 0, 4, 7, 3, 6, 5, 10, -1, -1, -1, -1, -1, -1, -1},
+       {1, 9, 0, 5, 10, 6, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1},
+       {10, 6, 5, 1, 9, 7, 1, 7, 3, 7, 9, 4, -1, -1, -1, -1},
+       {6, 1, 2, 6, 5, 1, 4, 7, 8, -1, -1, -1, -1, -1, -1, -1},
+       {1, 2, 5, 5, 2, 6, 3, 0, 4, 3, 4, 7, -1, -1, -1, -1},
+       {8, 4, 7, 9, 0, 5, 0, 6, 5, 0, 2, 6, -1, -1, -1, -1},
+       {7, 3, 9, 7, 9, 4, 3, 2, 9, 5, 9, 6, 2, 6, 9, -1},
+       {3, 11, 2, 7, 8, 4, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1},
+       {5, 10, 6, 4, 7, 2, 4, 2, 0, 2, 7, 11, -1, -1, -1, -1},
+       {0, 1, 9, 4, 7, 8, 2, 3, 11, 5, 10, 6, -1, -1, -1, -1},
+       {9, 2, 1, 9, 11, 2, 9, 4, 11, 7, 11, 4, 5, 10, 6, -1},
+       {8, 4, 7, 3, 11, 5, 3, 5, 1, 5, 11, 6, -1, -1, -1, -1},
+       {5, 1, 11, 5, 11, 6, 1, 0, 11, 7, 11, 4, 0, 4, 11, -1},
+       {0, 5, 9, 0, 6, 5, 0, 3, 6, 11, 6, 3, 8, 4, 7, -1},
+       {6, 5, 9, 6, 9, 11, 4, 7, 9, 7, 11, 9, -1, -1, -1, -1},
+       {10, 4, 9, 6, 4, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {4, 10, 6, 4, 9, 10, 0, 8, 3, -1, -1, -1, -1, -1, -1, -1},
+       {10, 0, 1, 10, 6, 0, 6, 4, 0, -1, -1, -1, -1, -1, -1, -1},
+       {8, 3, 1, 8, 1, 6, 8, 6, 4, 6, 1, 10, -1, -1, -1, -1},
+       {1, 4, 9, 1, 2, 4, 2, 6, 4, -1, -1, -1, -1, -1, -1, -1},
+       {3, 0, 8, 1, 2, 9, 2, 4, 9, 2, 6, 4, -1, -1, -1, -1},
+       {0, 2, 4, 4, 2, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {8, 3, 2, 8, 2, 4, 4, 2, 6, -1, -1, -1, -1, -1, -1, -1},
+       {10, 4, 9, 10, 6, 4, 11, 2, 3, -1, -1, -1, -1, -1, -1, -1},
+       {0, 8, 2, 2, 8, 11, 4, 9, 10, 4, 10, 6, -1, -1, -1, -1},
+       {3, 11, 2, 0, 1, 6, 0, 6, 4, 6, 1, 10, -1, -1, -1, -1},
+       {6, 4, 1, 6, 1, 10, 4, 8, 1, 2, 1, 11, 8, 11, 1, -1},
+       {9, 6, 4, 9, 3, 6, 9, 1, 3, 11, 6, 3, -1, -1, -1, -1},
+       {8, 11, 1, 8, 1, 0, 11, 6, 1, 9, 1, 4, 6, 4, 1, -1},
+       {3, 11, 6, 3, 6, 0, 0, 6, 4, -1, -1, -1, -1, -1, -1, -1},
+       {6, 4, 8, 11, 6, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {7, 10, 6, 7, 8, 10, 8, 9, 10, -1, -1, -1, -1, -1, -1, -1},
+       {0, 7, 3, 0, 10, 7, 0, 9, 10, 6, 7, 10, -1, -1, -1, -1},
+       {10, 6, 7, 1, 10, 7, 1, 7, 8, 1, 8, 0, -1, -1, -1, -1},
+       {10, 6, 7, 10, 7, 1, 1, 7, 3, -1, -1, -1, -1, -1, -1, -1},
+       {1, 2, 6, 1, 6, 8, 1, 8, 9, 8, 6, 7, -1, -1, -1, -1},
+       {2, 6, 9, 2, 9, 1, 6, 7, 9, 0, 9, 3, 7, 3, 9, -1},
+       {7, 8, 0, 7, 0, 6, 6, 0, 2, -1, -1, -1, -1, -1, -1, -1},
+       {7, 3, 2, 6, 7, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {2, 3, 11, 10, 6, 8, 10, 8, 9, 8, 6, 7, -1, -1, -1, -1},
+       {2, 0, 7, 2, 7, 11, 0, 9, 7, 6, 7, 10, 9, 10, 7, -1},
+       {1, 8, 0, 1, 7, 8, 1, 10, 7, 6, 7, 10, 2, 3, 11, -1},
+       {11, 2, 1, 11, 1, 7, 10, 6, 1, 6, 7, 1, -1, -1, -1, -1},
+       {8, 9, 6, 8, 6, 7, 9, 1, 6, 11, 6, 3, 1, 3, 6, -1},
+       {0, 9, 1, 11, 6, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {7, 8, 0, 7, 0, 6, 3, 11, 0, 11, 6, 0, -1, -1, -1, -1},
+       {7, 11, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {7, 6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {3, 0, 8, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {0, 1, 9, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {8, 1, 9, 8, 3, 1, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1},
+       {10, 1, 2, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {1, 2, 10, 3, 0, 8, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1},
+       {2, 9, 0, 2, 10, 9, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1},
+       {6, 11, 7, 2, 10, 3, 10, 8, 3, 10, 9, 8, -1, -1, -1, -1},
+       {7, 2, 3, 6, 2, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {7, 0, 8, 7, 6, 0, 6, 2, 0, -1, -1, -1, -1, -1, -1, -1},
+       {2, 7, 6, 2, 3, 7, 0, 1, 9, -1, -1, -1, -1, -1, -1, -1},
+       {1, 6, 2, 1, 8, 6, 1, 9, 8, 8, 7, 6, -1, -1, -1, -1},
+       {10, 7, 6, 10, 1, 7, 1, 3, 7, -1, -1, -1, -1, -1, -1, -1},
+       {10, 7, 6, 1, 7, 10, 1, 8, 7, 1, 0, 8, -1, -1, -1, -1},
+       {0, 3, 7, 0, 7, 10, 0, 10, 9, 6, 10, 7, -1, -1, -1, -1},
+       {7, 6, 10, 7, 10, 8, 8, 10, 9, -1, -1, -1, -1, -1, -1, -1},
+       {6, 8, 4, 11, 8, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {3, 6, 11, 3, 0, 6, 0, 4, 6, -1, -1, -1, -1, -1, -1, -1},
+       {8, 6, 11, 8, 4, 6, 9, 0, 1, -1, -1, -1, -1, -1, -1, -1},
+       {9, 4, 6, 9, 6, 3, 9, 3, 1, 11, 3, 6, -1, -1, -1, -1},
+       {6, 8, 4, 6, 11, 8, 2, 10, 1, -1, -1, -1, -1, -1, -1, -1},
+       {1, 2, 10, 3, 0, 11, 0, 6, 11, 0, 4, 6, -1, -1, -1, -1},
+       {4, 11, 8, 4, 6, 11, 0, 2, 9, 2, 10, 9, -1, -1, -1, -1},
+       {10, 9, 3, 10, 3, 2, 9, 4, 3, 11, 3, 6, 4, 6, 3, -1},
+       {8, 2, 3, 8, 4, 2, 4, 6, 2, -1, -1, -1, -1, -1, -1, -1},
+       {0, 4, 2, 4, 6, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {1, 9, 0, 2, 3, 4, 2, 4, 6, 4, 3, 8, -1, -1, -1, -1},
+       {1, 9, 4, 1, 4, 2, 2, 4, 6, -1, -1, -1, -1, -1, -1, -1},
+       {8, 1, 3, 8, 6, 1, 8, 4, 6, 6, 10, 1, -1, -1, -1, -1},
+       {10, 1, 0, 10, 0, 6, 6, 0, 4, -1, -1, -1, -1, -1, -1, -1},
+       {4, 6, 3, 4, 3, 8, 6, 10, 3, 0, 3, 9, 10, 9, 3, -1},
+       {10, 9, 4, 6, 10, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {4, 9, 5, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {0, 8, 3, 4, 9, 5, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1},
+       {5, 0, 1, 5, 4, 0, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1},
+       {11, 7, 6, 8, 3, 4, 3, 5, 4, 3, 1, 5, -1, -1, -1, -1},
+       {9, 5, 4, 10, 1, 2, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1},
+       {6, 11, 7, 1, 2, 10, 0, 8, 3, 4, 9, 5, -1, -1, -1, -1},
+       {7, 6, 11, 5, 4, 10, 4, 2, 10, 4, 0, 2, -1, -1, -1, -1},
+       {3, 4, 8, 3, 5, 4, 3, 2, 5, 10, 5, 2, 11, 7, 6, -1},
+       {7, 2, 3, 7, 6, 2, 5, 4, 9, -1, -1, -1, -1, -1, -1, -1},
+       {9, 5, 4, 0, 8, 6, 0, 6, 2, 6, 8, 7, -1, -1, -1, -1},
+       {3, 6, 2, 3, 7, 6, 1, 5, 0, 5, 4, 0, -1, -1, -1, -1},
+       {6, 2, 8, 6, 8, 7, 2, 1, 8, 4, 8, 5, 1, 5, 8, -1},
+       {9, 5, 4, 10, 1, 6, 1, 7, 6, 1, 3, 7, -1, -1, -1, -1},
+       {1, 6, 10, 1, 7, 6, 1, 0, 7, 8, 7, 0, 9, 5, 4, -1},
+       {4, 0, 10, 4, 10, 5, 0, 3, 10, 6, 10, 7, 3, 7, 10, -1},
+       {7, 6, 10, 7, 10, 8, 5, 4, 10, 4, 8, 10, -1, -1, -1, -1},
+       {6, 9, 5, 6, 11, 9, 11, 8, 9, -1, -1, -1, -1, -1, -1, -1},
+       {3, 6, 11, 0, 6, 3, 0, 5, 6, 0, 9, 5, -1, -1, -1, -1},
+       {0, 11, 8, 0, 5, 11, 0, 1, 5, 5, 6, 11, -1, -1, -1, -1},
+       {6, 11, 3, 6, 3, 5, 5, 3, 1, -1, -1, -1, -1, -1, -1, -1},
+       {1, 2, 10, 9, 5, 11, 9, 11, 8, 11, 5, 6, -1, -1, -1, -1},
+       {0, 11, 3, 0, 6, 11, 0, 9, 6, 5, 6, 9, 1, 2, 10, -1},
+       {11, 8, 5, 11, 5, 6, 8, 0, 5, 10, 5, 2, 0, 2, 5, -1},
+       {6, 11, 3, 6, 3, 5, 2, 10, 3, 10, 5, 3, -1, -1, -1, -1},
+       {5, 8, 9, 5, 2, 8, 5, 6, 2, 3, 8, 2, -1, -1, -1, -1},
+       {9, 5, 6, 9, 6, 0, 0, 6, 2, -1, -1, -1, -1, -1, -1, -1},
+       {1, 5, 8, 1, 8, 0, 5, 6, 8, 3, 8, 2, 6, 2, 8, -1},
+       {1, 5, 6, 2, 1, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {1, 3, 6, 1, 6, 10, 3, 8, 6, 5, 6, 9, 8, 9, 6, -1},
+       {10, 1, 0, 10, 0, 6, 9, 5, 0, 5, 6, 0, -1, -1, -1, -1},
+       {0, 3, 8, 5, 6, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {10, 5, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {11, 5, 10, 7, 5, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {11, 5, 10, 11, 7, 5, 8, 3, 0, -1, -1, -1, -1, -1, -1, -1},
+       {5, 11, 7, 5, 10, 11, 1, 9, 0, -1, -1, -1, -1, -1, -1, -1},
+       {10, 7, 5, 10, 11, 7, 9, 8, 1, 8, 3, 1, -1, -1, -1, -1},
+       {11, 1, 2, 11, 7, 1, 7, 5, 1, -1, -1, -1, -1, -1, -1, -1},
+       {0, 8, 3, 1, 2, 7, 1, 7, 5, 7, 2, 11, -1, -1, -1, -1},
+       {9, 7, 5, 9, 2, 7, 9, 0, 2, 2, 11, 7, -1, -1, -1, -1},
+       {7, 5, 2, 7, 2, 11, 5, 9, 2, 3, 2, 8, 9, 8, 2, -1},
+       {2, 5, 10, 2, 3, 5, 3, 7, 5, -1, -1, -1, -1, -1, -1, -1},
+       {8, 2, 0, 8, 5, 2, 8, 7, 5, 10, 2, 5, -1, -1, -1, -1},
+       {9, 0, 1, 5, 10, 3, 5, 3, 7, 3, 10, 2, -1, -1, -1, -1},
+       {9, 8, 2, 9, 2, 1, 8, 7, 2, 10, 2, 5, 7, 5, 2, -1},
+       {1, 3, 5, 3, 7, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {0, 8, 7, 0, 7, 1, 1, 7, 5, -1, -1, -1, -1, -1, -1, -1},
+       {9, 0, 3, 9, 3, 5, 5, 3, 7, -1, -1, -1, -1, -1, -1, -1},
+       {9, 8, 7, 5, 9, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {5, 8, 4, 5, 10, 8, 10, 11, 8, -1, -1, -1, -1, -1, -1, -1},
+       {5, 0, 4, 5, 11, 0, 5, 10, 11, 11, 3, 0, -1, -1, -1, -1},
+       {0, 1, 9, 8, 4, 10, 8, 10, 11, 10, 4, 5, -1, -1, -1, -1},
+       {10, 11, 4, 10, 4, 5, 11, 3, 4, 9, 4, 1, 3, 1, 4, -1},
+       {2, 5, 1, 2, 8, 5, 2, 11, 8, 4, 5, 8, -1, -1, -1, -1},
+       {0, 4, 11, 0, 11, 3, 4, 5, 11, 2, 11, 1, 5, 1, 11, -1},
+       {0, 2, 5, 0, 5, 9, 2, 11, 5, 4, 5, 8, 11, 8, 5, -1},
+       {9, 4, 5, 2, 11, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {2, 5, 10, 3, 5, 2, 3, 4, 5, 3, 8, 4, -1, -1, -1, -1},
+       {5, 10, 2, 5, 2, 4, 4, 2, 0, -1, -1, -1, -1, -1, -1, -1},
+       {3, 10, 2, 3, 5, 10, 3, 8, 5, 4, 5, 8, 0, 1, 9, -1},
+       {5, 10, 2, 5, 2, 4, 1, 9, 2, 9, 4, 2, -1, -1, -1, -1},
+       {8, 4, 5, 8, 5, 3, 3, 5, 1, -1, -1, -1, -1, -1, -1, -1},
+       {0, 4, 5, 1, 0, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {8, 4, 5, 8, 5, 3, 9, 0, 5, 0, 3, 5, -1, -1, -1, -1},
+       {9, 4, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {4, 11, 7, 4, 9, 11, 9, 10, 11, -1, -1, -1, -1, -1, -1, -1},
+       {0, 8, 3, 4, 9, 7, 9, 11, 7, 9, 10, 11, -1, -1, -1, -1},
+       {1, 10, 11, 1, 11, 4, 1, 4, 0, 7, 4, 11, -1, -1, -1, -1},
+       {3, 1, 4, 3, 4, 8, 1, 10, 4, 7, 4, 11, 10, 11, 4, -1},
+       {4, 11, 7, 9, 11, 4, 9, 2, 11, 9, 1, 2, -1, -1, -1, -1},
+       {9, 7, 4, 9, 11, 7, 9, 1, 11, 2, 11, 1, 0, 8, 3, -1},
+       {11, 7, 4, 11, 4, 2, 2, 4, 0, -1, -1, -1, -1, -1, -1, -1},
+       {11, 7, 4, 11, 4, 2, 8, 3, 4, 3, 2, 4, -1, -1, -1, -1},
+       {2, 9, 10, 2, 7, 9, 2, 3, 7, 7, 4, 9, -1, -1, -1, -1},
+       {9, 10, 7, 9, 7, 4, 10, 2, 7, 8, 7, 0, 2, 0, 7, -1},
+       {3, 7, 10, 3, 10, 2, 7, 4, 10, 1, 10, 0, 4, 0, 10, -1},
+       {1, 10, 2, 8, 7, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {4, 9, 1, 4, 1, 7, 7, 1, 3, -1, -1, -1, -1, -1, -1, -1},
+       {4, 9, 1, 4, 1, 7, 0, 8, 1, 8, 7, 1, -1, -1, -1, -1},
+       {4, 0, 3, 7, 4, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {4, 8, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {9, 10, 8, 10, 11, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {3, 0, 9, 3, 9, 11, 11, 9, 10, -1, -1, -1, -1, -1, -1, -1},
+       {0, 1, 10, 0, 10, 8, 8, 10, 11, -1, -1, -1, -1, -1, -1, -1},
+       {3, 1, 10, 11, 3, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {1, 2, 11, 1, 11, 9, 9, 11, 8, -1, -1, -1, -1, -1, -1, -1},
+       {3, 0, 9, 3, 9, 11, 1, 2, 9, 2, 11, 9, -1, -1, -1, -1},
+       {0, 2, 11, 8, 0, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {3, 2, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {2, 3, 8, 2, 8, 10, 10, 8, 9, -1, -1, -1, -1, -1, -1, -1},
+       {9, 10, 2, 0, 9, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {2, 3, 8, 2, 8, 10, 0, 1, 8, 1, 10, 8, -1, -1, -1, -1},
+       {1, 10, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {1, 3, 8, 9, 1, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {0, 9, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {0, 3, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
+       {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}
+};

diff --git a/src/metasurf.c b/src/metasurf.c
new file mode 100644 (file)
index 0000000..7f77ec3
--- /dev/null
+++ b/src/metasurf.c
@@ -0,0 +1,369 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <math.h>
+#include "metasurf.h"
+#include "mcubes.h"
+
+typedef float vec3[3];
+
+struct metasurface {
+       vec3 min, max;
+       int res[3], newres[3];
+       float thres;
+
+       float dx, dy, dz;
+       unsigned int flags;
+
+       float *voxels;
+
+       int varr_size, varr_alloc_size;
+       float *varr, *narr;
+};
+
+static int msurf_init(struct metasurface *ms);
+static void process_cell(struct metasurface *ms, int xcell, int ycell, int zcell, vec3 pos, vec3 sz);
+
+
+struct metasurface *msurf_create(void)
+{
+       struct metasurface *ms;
+
+       if(!(ms = malloc(sizeof *ms))) {
+               return 0;
+       }
+       if(msurf_init(ms) == -1) {
+               free(ms);
+       }
+       return ms;
+}
+
+void msurf_free(struct metasurface *ms)
+{
+       if(ms) {
+               free(ms->voxels);
+               free(ms->varr);
+               free(ms->narr);
+               free(ms);
+       }
+}
+
+static int msurf_init(struct metasurface *ms)
+{
+       ms->voxels = 0;
+       ms->thres = 0.0;
+       ms->min[0] = ms->min[1] = ms->min[2] = -1.0;
+       ms->max[0] = ms->max[1] = ms->max[2] = 1.0;
+       ms->res[0] = ms->res[1] = ms->res[2] = 0;
+       ms->newres[0] = ms->newres[1] = ms->newres[2] = 40;
+
+       ms->varr_alloc_size = ms->varr_size = 0;
+       ms->varr = ms->narr = 0;
+
+       ms->dx = ms->dy = ms->dz = 0.001;
+       ms->flags = 0;
+
+       return 0;
+}
+
+void msurf_enable(struct metasurface *ms, unsigned int opt)
+{
+       ms->flags |= opt;
+}
+
+void msurf_disable(struct metasurface *ms, unsigned int opt)
+{
+       ms->flags &= ~opt;
+}
+
+int msurf_is_enabled(struct metasurface *ms, unsigned int opt)
+{
+       return ms->flags & opt;
+}
+
+void msurf_set_inside(struct metasurface *ms, int inside)
+{
+       switch(inside) {
+       case MSURF_GREATER:
+               msurf_enable(ms, MSURF_FLIP);
+               break;
+
+       case MSURF_LESS:
+               msurf_disable(ms, MSURF_FLIP);
+               break;
+
+       default:
+               fprintf(stderr, "msurf_inside expects MSURF_GREATER or MSURF_LESS\n");
+       }
+}
+
+int msurf_get_inside(struct metasurface *ms)
+{
+       return msurf_is_enabled(ms, MSURF_FLIP) ? MSURF_LESS : MSURF_GREATER;
+}
+
+void msurf_set_bounds(struct metasurface *ms, float xmin, float ymin, float zmin, float xmax, float ymax, float zmax)
+{
+       ms->min[0] = xmin;
+       ms->min[1] = ymin;
+       ms->min[2] = zmin;
+       ms->max[0] = xmax;
+       ms->max[1] = ymax;
+       ms->max[2] = zmax;
+}
+
+void msurf_get_bounds(struct metasurface *ms, float *xmin, float *ymin, float *zmin, float *xmax, float *ymax, float *zmax)
+{
+       *xmin = ms->min[0];
+       *ymin = ms->min[1];
+       *zmin = ms->min[2];
+       *xmax = ms->max[0];
+       *ymax = ms->max[1];
+       *zmax = ms->max[2];
+}
+
+void msurf_set_resolution(struct metasurface *ms, int xres, int yres, int zres)
+{
+       ms->newres[0] = xres;
+       ms->newres[1] = yres;
+       ms->newres[2] = zres;
+}
+
+void msurf_get_resolution(struct metasurface *ms, int *xres, int *yres, int *zres)
+{
+       *xres = ms->res[0];
+       *yres = ms->res[1];
+       *zres = ms->res[2];
+}
+
+void msurf_set_threshold(struct metasurface *ms, float thres)
+{
+       ms->thres = thres;
+}
+
+float msurf_get_threshold(struct metasurface *ms)
+{
+       return ms->thres;
+}
+
+
+float *msurf_voxels(struct metasurface *ms)
+{
+       if(ms->res[0] != ms->newres[0] || ms->res[1] != ms->newres[1] || ms->res[2] != ms->newres[2]) {
+               int count;
+               ms->res[0] = ms->newres[0];
+               ms->res[1] = ms->newres[1];
+               ms->res[2] = ms->newres[2];
+               count = ms->res[0] * ms->res[1] * ms->res[2];
+               free(ms->voxels);
+               if(!(ms->voxels = malloc(count * sizeof *ms->voxels))) {
+                       return 0;
+               }
+       }
+       return ms->voxels;
+}
+
+float *msurf_slice(struct metasurface *ms, int idx)
+{
+       float *vox = msurf_voxels(ms);
+       if(!vox) return 0;
+
+       return vox + ms->res[0] * ms->res[1] * idx;
+}
+
+int msurf_polygonize(struct metasurface *ms)
+{
+       int i, j, k;
+       vec3 pos, delta;
+
+       if(!ms->voxels) return -1;
+
+       ms->varr_size = 0;
+
+       for(i=0; i<3; i++) {
+               delta[i] = (ms->max[i] - ms->min[i]) / (float)ms->res[i];
+       }
+
+       for(i=0; i<ms->res[0] - 1; i++) {
+               for(j=0; j<ms->res[1] - 1; j++) {
+                       for(k=0; k<ms->res[2] - 1; k++) {
+
+                               pos[0] = ms->min[0] + i * delta[0];
+                               pos[1] = ms->min[1] + j * delta[1];
+                               pos[2] = ms->min[2] + k * delta[2];
+
+                               process_cell(ms, i, j, k, pos, delta);
+                       }
+               }
+       }
+       return 0;
+}
+
+int msurf_vertex_count(struct metasurface *ms)
+{
+       return ms->varr_size / 3;
+}
+
+float *msurf_vertices(struct metasurface *ms)
+{
+       return ms->varr;
+}
+
+float *msurf_normals(struct metasurface *ms)
+{
+       return ms->narr;
+}
+
+static unsigned int mc_bitcode(float *val, float thres);
+
+static void process_cell(struct metasurface *ms, int xcell, int ycell, int zcell, vec3 cellpos, vec3 cellsz)
+{
+       int i, j, k, slice_size;
+       vec3 pos[8];
+       float dfdx[8], dfdy[8], dfdz[8];
+       vec3 vert[12], norm[12];
+       float val[8];
+       float *cellptr;
+       unsigned int code;
+
+       static const int offs[][3] = {
+               {0, 0, 0},
+               {1, 0, 0},
+               {1, 1, 0},
+               {0, 1, 0},
+               {0, 0, 1},
+               {1, 0, 1},
+               {1, 1, 1},
+               {0, 1, 1}
+       };
+
+       static const int pidx[12][2] = {
+               {0, 1}, {1, 2}, {2, 3}, {3, 0}, {4, 5}, {5, 6},
+               {6, 7}, {7, 4}, {0, 4}, {1, 5}, {2, 6}, {3, 7}
+       };
+
+       slice_size = ms->res[0] * ms->res[1];
+       cellptr = ms->voxels + slice_size * zcell + ms->res[0] * ycell + xcell;
+
+#define GRIDOFFS(x, y, z)      ((z) * slice_size + (y) * ms->res[0] + (x))
+
+       for(i=0; i<8; i++) {
+               val[i] = cellptr[GRIDOFFS(offs[i][0], offs[i][1], offs[i][2])];
+       }
+
+       code = mc_bitcode(val, ms->thres);
+       if(ms->flags & MSURF_FLIP) {
+               code = ~code & 0xff;
+       }
+       if(mc_edge_table[code] == 0) {
+               return;
+       }
+
+       /* calculate normals at the 8 corners */
+       for(i=0; i<8; i++) {
+               float *ptr = cellptr + GRIDOFFS(offs[i][0], offs[i][1], offs[i][2]);
+
+               if(xcell < ms->res[0] - 1) {
+                       dfdx[i] = ptr[GRIDOFFS(1, 0, 0)] - *ptr;
+               } else {
+                       dfdx[i] = *ptr - ptr[GRIDOFFS(-1, 0, 0)];
+               }
+               if(ycell < ms->res[1] - 1) {
+                       dfdy[i] = ptr[GRIDOFFS(0, 1, 0)] - *ptr;
+               } else {
+                       dfdy[i] = *ptr - ptr[GRIDOFFS(0, -1, 0)];
+               }
+               if(zcell < ms->res[2] - 1) {
+                       dfdz[i] = ptr[GRIDOFFS(0, 0, 1)] - *ptr;
+               } else {
+                       dfdz[i] = *ptr - ptr[GRIDOFFS(0, 0, -1)];
+               }
+       }
+
+       /* calculate the world-space position of each corner */
+       for(i=0; i<8; i++) {
+               pos[i][0] = cellpos[0] + cellsz[0] * offs[i][0];
+               pos[i][1] = cellpos[1] + cellsz[1] * offs[i][1];
+               pos[i][2] = cellpos[2] + cellsz[2] * offs[i][2];
+       }
+
+       /* generate up to a max of 12 vertices per cube. interpolate positions and normals for each one */
+       for(i=0; i<12; i++) {
+               if(mc_edge_table[code] & (1 << i)) {
+                       float nx, ny, nz;
+                       int p0 = pidx[i][0];
+                       int p1 = pidx[i][1];
+
+                       float t = (ms->thres - val[p0]) / (val[p1] - val[p0]);
+                       vert[i][0] = pos[p0][0] + (pos[p1][0] - pos[p0][0]) * t;
+                       vert[i][1] = pos[p0][1] + (pos[p1][1] - pos[p0][1]) * t;
+                       vert[i][2] = pos[p0][2] + (pos[p1][2] - pos[p0][2]) * t;
+
+                       nx = dfdx[p0] + (dfdx[p1] - dfdx[p0]) * t;
+                       ny = dfdy[p0] + (dfdy[p1] - dfdy[p0]) * t;
+                       nz = dfdz[p0] + (dfdz[p1] - dfdz[p0]) * t;
+
+                       if(ms->flags & MSURF_FLIP) {
+                               nx = -nx;
+                               ny = -ny;
+                               nz = -nz;
+                       }
+
+                       if(ms->flags & MSURF_NORMALIZE) {
+                               float len = sqrt(nx * nx + ny * ny + nz * nz);
+                               if(len != 0.0) {
+                                       float s = 1.0f / len;
+                                       nx *= s;
+                                       ny *= s;
+                                       nz *= s;
+                               }
+                       }
+
+                       norm[i][0] = nx;
+                       norm[i][1] = ny;
+                       norm[i][2] = nz;
+               }
+       }
+
+       /* for each triangle of the cube add the appropriate vertices to the vertex buffer */
+       for(i=0; mc_tri_table[code][i] != -1; i+=3) {
+               for(j=0; j<3; j++) {
+                       int idx = mc_tri_table[code][i + j];
+                       float *v = vert[idx];
+                       float *n = norm[idx];
+
+                       /* TODO multithreadied polygon emit */
+                       if(ms->varr_size + 3 > ms->varr_alloc_size) {
+                               int newsz = ms->varr_alloc_size ? ms->varr_alloc_size * 2 : 1024;
+                               float *new_varr, *new_narr;
+
+                               if(!(new_varr = realloc(ms->varr, newsz * sizeof *new_varr)) ||
+                                               !(new_narr = realloc(ms->narr, newsz * sizeof *new_narr))) {
+                                       free(new_varr);
+                                       fprintf(stderr, "msurf_polygonize: failed to grow vertex buffers to %d elements\n", newsz);
+                                       return;
+                               }
+                               ms->varr = new_varr;
+                               ms->narr = new_narr;
+                               ms->varr_alloc_size = newsz;
+                       }
+
+                       for(k=0; k<3; k++) {
+                               ms->varr[ms->varr_size] = v[k];
+                               ms->narr[ms->varr_size] = n[k];
+                               ++ms->varr_size;
+                       }
+               }
+       }
+}
+
+static unsigned int mc_bitcode(float *val, float thres)
+{
+       unsigned int i, res = 0;
+
+       for(i=0; i<8; i++) {
+               if(val[i] > thres) {
+                       res |= 1 << i;
+               }
+       }
+       return res;
+}

diff --git a/src/metasurf.h b/src/metasurf.h
new file mode 100644 (file)
index 0000000..3f7ed6e
--- /dev/null
+++ b/src/metasurf.h
@@ -0,0 +1,58 @@
+#ifndef METASURF_H_
+#define METASURF_H_
+
+#define MSURF_GREATER  1
+#define MSURF_LESS             0
+
+#define MSURF_FLIP                     1
+#define MSURF_NORMALIZE                2
+
+struct metasurface;
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+struct metasurface *msurf_create(void);
+void msurf_free(struct metasurface *ms);
+
+void msurf_enable(struct metasurface *ms, unsigned int opt);
+void msurf_disable(struct metasurface *ms, unsigned int opt);
+int msurf_is_enabled(struct metasurface *ms, unsigned int opt);
+
+/* which is inside above or below the threshold */
+void msurf_set_inside(struct metasurface *ms, int inside);
+int msurf_get_inside(struct metasurface *ms);
+
+/* set the bounding box (default: -1, -1, -1, 1, 1, 1)
+ * keep this as tight as possible to avoid wasting grid resolution
+ */
+void msurf_set_bounds(struct metasurface *ms, float xmin, float ymin, float zmin, float xmax, float ymax, float zmax);
+void msurf_get_bounds(struct metasurface *ms, float *xmin, float *ymin, float *zmin, float *xmax, float *ymax, float *zmax);
+
+/* resolution of the 3D evaluation grid, the bigger, the better, the slower
+ * (default: 40, 40, 40)
+ */
+void msurf_set_resolution(struct metasurface *ms, int xres, int yres, int zres);
+void msurf_get_resolution(struct metasurface *ms, int *xres, int *yres, int *zres);
+
+/* isosurface threshold value (default: 0) */
+void msurf_set_threshold(struct metasurface *ms, float thres);
+float msurf_get_threshold(struct metasurface *ms);
+
+/* get pointer to the scalar field */
+float *msurf_voxels(struct metasurface *ms);
+float *msurf_slice(struct metasurface *ms, int idx);
+
+/* finally call this to perform the polygonization */
+int msurf_polygonize(struct metasurface *ms);
+
+int msurf_vertex_count(struct metasurface *ms);
+float *msurf_vertices(struct metasurface *ms);
+float *msurf_normals(struct metasurface *ms);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* METASURF_H_ */

diff --git a/src/rbtree.c b/src/rbtree.c
deleted file mode 100644 (file)
index 765e542..0000000
--- a/src/rbtree.c
+++ /dev/null
@@ -1,518 +0,0 @@
-/*
-rbtree - simple balanced binary search tree (red-black tree) library.
-Copyright (C) 2011-2014  John Tsiombikas <nuclear@member.fsf.org>
-
-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 <stdio.h>
-#include <stdlib.h>
-#include <stdint.h>
-#include <string.h>
-#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;
-}
-
-void rb_node_setdata(struct rbnode *node, void *data)
-{
-       node->data = data;
-}
-
-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 {
-               if(rb->del) {
-                       /* The key passed in was allocated in a way that would be cleaned by the
-                        * user-supplied delete function. We can't just assign the data and ignore
-                        * key in this case, or we'll leak memory. But we also can't make a dummy
-                        * node and pass that to rb->del, because it might also expect to free data.
-                        * So we must instead delete the existing node's contents, and use the new ones.
-                        */
-                       rb->del(tree, rb->del_cls);
-                       tree->key = key;
-               }
-               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
deleted file mode 100644 (file)
index dada0dc..0000000
--- a/src/rbtree.h
+++ /dev/null
@@ -1,79 +0,0 @@
-/*
-rbtree - simple balanced binary search tree (red-black tree) library.
-Copyright (C) 2011-2014  John Tsiombikas <nuclear@member.fsf.org>
-
-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);
-void rb_node_setdata(struct rbnode *node, void *data);
-
-#ifdef __cplusplus
-}
-#endif
-
-
-#endif /* RBTREE_H_ */