--- /dev/null
+#ifndef GEOM_H_
+#define GEOM_H_
+
+#include "cgmath/cgmath.h"
+
+struct sphere {
+ cgm_vec3 pos;
+ float rad;
+};
+
+struct aabox {
+ cgm_vec3 vmin, vmax;
+};
+
+#endif /* GEOM_H_ */
--- /dev/null
+#include <stdio.h>
+#include <stdlib.h>
+#include <stddef.h>
+#include <string.h>
+#include <float.h>
+#define GL_GLEXT_PROTOTYPES 1
+#include <GL/gl.h>
+#include <GL/glext.h>
+#include "mesh.h"
+
+static int update_mesh_vbo(struct mesh *m);
+static int update_meshgroup_vbo(struct meshgroup *mg);
+
+void init_mesh(struct mesh *m)
+{
+ memset(m, 0, sizeof *m);
+}
+
+void destroy_mesh(struct mesh *m)
+{
+ free(m->varr);
+ free(m->iarr);
+
+ if(m->vbo) {
+ glDeleteBuffers(1, &m->vbo);
+ }
+ if(m->ibo) {
+ glDeleteBuffers(1, &m->ibo);
+ }
+}
+
+void clear_mesh(struct mesh *m)
+{
+ free(m->varr);
+ free(m->iarr);
+
+ m->varr = 0;
+ m->iarr = 0;
+ m->num_verts = m->max_verts = m->num_idx = m->max_idx = 0;
+ m->mtl = 0;
+ m->bbvalid = m->vbovalid = 0;
+}
+
+void init_meshgroup(struct meshgroup *mg)
+{
+ memset(mg, 0, sizeof *mg);
+}
+
+void destroy_meshgroup(struct meshgroup *mg)
+{
+ free(mg->meshes);
+
+ if(mg->vbo) {
+ glDeleteBuffers(1, &mg->vbo);
+ }
+ if(mg->ibo) {
+ glDeleteBuffers(1, &mg->ibo);
+ }
+}
+
+void clear_meshgroup(struct meshgroup *mg)
+{
+ free(mg->meshes);
+
+ mg->meshes = 0;
+ mg->num_meshes = 0;
+ mg->num_verts = mg->num_idx = 0;
+
+ mg->bbvalid = mg->vbovalid = 0;
+}
+
+void calc_mesh_bounds(struct mesh *m)
+{
+ int i;
+ struct vertex *vptr = m->varr;
+
+ m->bb.vmin.x = m->bb.vmin.y = m->bb.vmin.z = FLT_MAX;
+ m->bb.vmax.x = m->bb.vmax.y = m->bb.vmax.z = -FLT_MAX;
+
+ for(i=0; i<m->num_verts; i++) {
+ if(vptr->pos.x < m->bb.vmin.x) m->bb.vmin.x = vptr->pos.x;
+ if(vptr->pos.y < m->bb.vmin.y) m->bb.vmin.y = vptr->pos.y;
+ if(vptr->pos.z < m->bb.vmin.z) m->bb.vmin.z = vptr->pos.z;
+ if(vptr->pos.x > m->bb.vmax.x) m->bb.vmax.x = vptr->pos.x;
+ if(vptr->pos.y > m->bb.vmax.y) m->bb.vmax.y = vptr->pos.y;
+ if(vptr->pos.z > m->bb.vmax.z) m->bb.vmax.z = vptr->pos.z;
+ vptr++;
+ }
+
+ m->bbvalid = 1;
+}
+
+void calc_meshgroup_bounds(struct meshgroup *mg)
+{
+ int i;
+ struct mesh *m;
+
+ mg->bb.vmin.x = mg->bb.vmin.y = mg->bb.vmin.z = FLT_MAX;
+ mg->bb.vmax.x = mg->bb.vmax.y = mg->bb.vmax.z = -FLT_MAX;
+
+ for(i=0; i<mg->num_meshes; i++) {
+ m = mg->meshes[i];
+ if(!m->bbvalid) {
+ calc_mesh_bounds(m);
+ }
+
+ if(m->bb.vmin.x < mg->bb.vmin.x) mg->bb.vmin.x = m->bb.vmin.x;
+ if(m->bb.vmin.y < mg->bb.vmin.y) mg->bb.vmin.y = m->bb.vmin.y;
+ if(m->bb.vmin.z < mg->bb.vmin.z) mg->bb.vmin.z = m->bb.vmin.z;
+ if(m->bb.vmax.x > mg->bb.vmax.x) mg->bb.vmax.x = m->bb.vmax.x;
+ if(m->bb.vmax.y > mg->bb.vmax.y) mg->bb.vmax.y = m->bb.vmax.y;
+ if(m->bb.vmax.z > mg->bb.vmax.z) mg->bb.vmax.z = m->bb.vmax.z;
+ }
+
+ mg->bbvalid = 1;
+}
+
+int add_mesh_vertex(struct mesh *m, struct vertex *v)
+{
+ void *tmp;
+ int newmax;
+
+ if(m->num_verts >= m->max_verts) {
+ newmax = m->max_verts ? m->max_verts * 2 : 16;
+ if(!(tmp = realloc(m->varr, newmax * sizeof *m->varr))) {
+ return -1;
+ }
+ m->varr = tmp;
+ m->max_verts = newmax;
+ }
+
+ m->varr[m->num_verts++] = *v;
+ return 0;
+}
+
+int add_mesh_index(struct mesh *m, int idx)
+{
+ void *tmp;
+ int newmax;
+
+ if(m->num_idx >= m->max_idx) {
+ newmax = m->max_idx ? m->max_idx * 2 : 16;
+ if(!(tmp = realloc(m->iarr, newmax * sizeof *m->iarr))) {
+ return -1;
+ }
+ m->iarr = tmp;
+ m->max_idx = newmax;
+ }
+
+ m->iarr[m->num_idx++] = idx;
+ return 0;
+}
+
+int add_mesh_face(struct mesh *m, int va, int vb, int vc)
+{
+ if(add_mesh_index(m, va) == -1) return -1;
+ if(add_mesh_index(m, vb) == -1) {
+ m->num_idx--;
+ return -1;
+ }
+ if(add_mesh_index(m, vc) == -1) {
+ m->num_idx -= 2;
+ return -1;
+ }
+ return 0;
+}
+
+int add_meshgroup_mesh(struct meshgroup *mg, struct mesh *m)
+{
+ void *tmp;
+ int newmax;
+
+ if(mg->num_meshes >= mg->max_meshes) {
+ newmax = mg->max_meshes ? mg->max_meshes * 2 : 16;
+ if(!(tmp = realloc(mg->meshes, newmax * sizeof *mg->meshes))) {
+ return -1;
+ }
+ mg->meshes = tmp;
+ mg->max_meshes = newmax;
+ }
+
+ mg->meshes[mg->num_meshes++] = m;
+ return 0;
+}
+
+void draw_mesh(struct mesh *m)
+{
+ if(!m->vbovalid) {
+ if(update_mesh_vbo(m) == -1) {
+ return;
+ }
+ }
+
+ glEnableVertexAttribArray(MESH_ATTR_VERTEX);
+ glEnableVertexAttribArray(MESH_ATTR_NORMAL);
+ glEnableVertexAttribArray(MESH_ATTR_TANGENT);
+ glEnableVertexAttribArray(MESH_ATTR_TEXCOORD);
+
+ glBindBuffer(GL_ARRAY_BUFFER, m->vbo);
+ glVertexAttribPointer(MESH_ATTR_VERTEX, 3, GL_FLOAT, 0, sizeof *m->varr, 0);
+ glVertexAttribPointer(MESH_ATTR_NORMAL, 3, GL_FLOAT, 0, sizeof *m->varr, (void*)offsetof(struct vertex, norm));
+ glVertexAttribPointer(MESH_ATTR_TANGENT, 3, GL_FLOAT, 0, sizeof *m->varr, (void*)offsetof(struct vertex, tang));
+ glVertexAttribPointer(MESH_ATTR_TEXCOORD, 2, GL_FLOAT, 0, sizeof *m->varr, (void*)offsetof(struct vertex, tex));
+ glBindBuffer(GL_ARRAY_BUFFER, 0);
+
+ if(m->ibo) {
+ glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, m->ibo);
+ glDrawElements(GL_TRIANGLES, m->num_idx, GL_UNSIGNED_INT, 0);
+ glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, 0);
+ } else {
+ glDrawArrays(GL_TRIANGLES, 0, m->num_verts);
+ }
+
+ glDisableVertexAttribArray(MESH_ATTR_VERTEX);
+ glDisableVertexAttribArray(MESH_ATTR_NORMAL);
+ glDisableVertexAttribArray(MESH_ATTR_TANGENT);
+ glDisableVertexAttribArray(MESH_ATTR_TEXCOORD);
+}
+
+void draw_meshgroup(struct meshgroup *mg)
+{
+ if(!mg->vbovalid) {
+ if(update_meshgroup_vbo(mg) == -1) {
+ return;
+ }
+ }
+
+ glEnableVertexAttribArray(MESH_ATTR_VERTEX);
+ glEnableVertexAttribArray(MESH_ATTR_NORMAL);
+ glEnableVertexAttribArray(MESH_ATTR_TANGENT);
+ glEnableVertexAttribArray(MESH_ATTR_TEXCOORD);
+
+ glBindBuffer(GL_ARRAY_BUFFER, mg->vbo);
+ glVertexAttribPointer(MESH_ATTR_VERTEX, 3, GL_FLOAT, 0, sizeof(struct vertex), 0);
+ glVertexAttribPointer(MESH_ATTR_NORMAL, 3, GL_FLOAT, 0, sizeof(struct vertex), (void*)offsetof(struct vertex, norm));
+ glVertexAttribPointer(MESH_ATTR_TANGENT, 3, GL_FLOAT, 0, sizeof(struct vertex), (void*)offsetof(struct vertex, tang));
+ glVertexAttribPointer(MESH_ATTR_TEXCOORD, 2, GL_FLOAT, 0, sizeof(struct vertex), (void*)offsetof(struct vertex, tex));
+ glBindBuffer(GL_ARRAY_BUFFER, 0);
+
+ if(mg->ibo) {
+ glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, mg->ibo);
+ glDrawElements(GL_TRIANGLES, mg->num_idx, GL_UNSIGNED_INT, 0);
+ glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, 0);
+ } else {
+ glDrawArrays(GL_TRIANGLES, 0, mg->num_verts);
+ }
+
+ glDisableVertexAttribArray(MESH_ATTR_VERTEX);
+ glDisableVertexAttribArray(MESH_ATTR_NORMAL);
+ glDisableVertexAttribArray(MESH_ATTR_TANGENT);
+ glDisableVertexAttribArray(MESH_ATTR_TEXCOORD);
+}
+
+static int update_mesh_vbo(struct mesh *m)
+{
+ if(m->num_verts <= 0) return -1;
+
+ if(!m->vbo) {
+ glGenBuffers(1, &m->vbo);
+ }
+ glBindBuffer(GL_ARRAY_BUFFER, m->vbo);
+ glBufferData(GL_ARRAY_BUFFER, m->num_verts * sizeof *m->varr, m->varr, GL_STATIC_DRAW);
+ glBindBuffer(GL_ARRAY_BUFFER, 0);
+
+ if(m->num_idx > 0) {
+ if(!m->ibo) {
+ glGenBuffers(1, &m->ibo);
+ }
+ glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, m->ibo);
+ glBufferData(GL_ELEMENT_ARRAY_BUFFER, m->num_idx * sizeof *m->iarr,
+ m->iarr, GL_STATIC_DRAW);
+ glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, 0);
+ }
+ return 0;
+}
+
+static int update_meshgroup_vbo(struct meshgroup *mg)
+{
+ int i;
+ struct vertex *varr, *vptr;
+ unsigned int *iarr = 0, *iptr;
+ struct mesh *m;
+
+ mg->num_verts = mg->num_idx = 0;
+
+ for(i=0; i<mg->num_meshes; i++) {
+ mg->num_verts += mg->meshes[i]->num_verts;
+ mg->num_idx += mg->meshes[i]->num_idx;
+ }
+
+ if(mg->num_verts <= 0) return -1;
+
+ if(!(varr = malloc(mg->num_verts * sizeof *varr))) {
+ fprintf(stderr, "update_meshgroup_vbo: failed to allocate vertex array with %d vertices\n", mg->num_verts);
+ return -1;
+ }
+ if(mg->num_idx > 0) {
+ if(!(iarr = malloc(mg->num_idx * sizeof *iarr))) {
+ fprintf(stderr, "update_meshgroup_vbo: failed to allocate index array with %d indices\n", mg->num_idx);
+ free(varr);
+ return -1;
+ }
+ }
+
+ vptr = varr;
+ iptr = iarr;
+
+ for(i=0; i<mg->num_meshes; i++) {
+ m = mg->meshes[i];
+ memcpy(vptr, m->varr, m->num_verts * sizeof *vptr);
+ vptr += m->num_verts;
+
+ if(iarr) {
+ memcpy(iptr, m->iarr, m->num_idx * sizeof *iptr);
+ iptr += m->num_idx;
+ }
+ }
+
+ if(!mg->vbo) {
+ glGenBuffers(1, &mg->vbo);
+ }
+ glBindBuffer(GL_ARRAY_BUFFER, mg->vbo);
+ glBufferData(GL_ARRAY_BUFFER, mg->num_verts * sizeof *varr, varr, GL_STATIC_DRAW);
+ glBindBuffer(GL_ARRAY_BUFFER, 0);
+ if(iarr) {
+ if(!mg->ibo) {
+ glGenBuffers(1, &mg->ibo);
+ }
+ glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, mg->ibo);
+ glBufferData(GL_ELEMENT_ARRAY_BUFFER, mg->num_idx * sizeof *iarr, iarr, GL_STATIC_DRAW);
+ glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, 0);
+ }
+
+ free(varr);
+ free(iarr);
+ return 0;
+}
--- /dev/null
+#ifndef MESH_H_
+#define MESH_H_
+
+#include "cgmath/cgmath.h"
+#include "geom.h"
+
+enum {
+ MESH_ATTR_VERTEX,
+ MESH_ATTR_NORMAL,
+ MESH_ATTR_TANGENT,
+ MESH_ATTR_TEXCOORD
+};
+
+struct vertex {
+ cgm_vec3 pos;
+ cgm_vec3 norm;
+ cgm_vec3 tang;
+ cgm_vec2 tex;
+};
+
+enum {
+ TEX_DIFFUSE,
+ TEX_SPECULAR,
+ TEX_NORMAL,
+
+ NUM_TEX_SLOTS
+};
+
+struct material {
+ char *name;
+
+ cgm_vec3 color;
+ cgm_vec3 spec;
+ float shininess;
+
+ unsigned int tex[NUM_TEX_SLOTS];
+
+ struct material *next;
+};
+
+struct mesh {
+ struct vertex *varr;
+ unsigned int *iarr;
+ int num_verts, num_idx;
+ int max_verts, max_idx;
+
+ struct material *mtl;
+
+ struct aabox bb;
+ int bbvalid;
+
+ unsigned int vbo, ibo;
+ int vbovalid;
+
+ struct mesh *next;
+};
+
+struct meshgroup {
+ struct mesh **meshes;
+ int num_meshes, max_meshes;
+
+ struct aabox bb;
+ int bbvalid;
+
+ int num_verts, num_idx;
+ unsigned int vbo, ibo;
+ int vbovalid;
+};
+
+void init_mesh(struct mesh *m);
+void destroy_mesh(struct mesh *m);
+void clear_mesh(struct mesh *m);
+
+void init_meshgroup(struct meshgroup *mg);
+void destroy_meshgroup(struct meshgroup *mg);
+void clear_meshgroup(struct meshgroup *mg);
+
+void calc_mesh_bounds(struct mesh *m);
+
+int add_mesh_vertex(struct mesh *m, struct vertex *v);
+int add_mesh_index(struct mesh *m, int idx);
+int add_mesh_face(struct mesh *m, int va, int vb, int vc);
+
+int add_meshgroup_mesh(struct meshgroup *mg, struct mesh *m);
+
+void draw_mesh(struct mesh *m);
+void draw_meshgroup(struct meshgroup *mg);
+
+#endif /* MESH_H_ */
--- /dev/null
+/*
+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 {
+ 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;
+}
--- /dev/null
+/*
+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_ */
--- /dev/null
+#include <stdio.h>
+#include <stdlib.h>
+#include <ctype.h>
+#include <assert.h>
+#include "cgmath/cgmath.h"
+#include "scenefile.h"
+#include "rbtree.h"
+
+struct facevertex {
+ int vidx, tidx, nidx;
+};
+
+struct objmtl {
+ char *name;
+ cgm_vec3 ka, kd, ks, ke;
+ float shin;
+ float alpha;
+ float ior;
+ char *map_kd, *map_ke, *map_alpha;
+ struct objmtl *next;
+};
+
+static int proc_facevert(struct mesh *mesh, struct facevertex *fv,
+ cgm_vec3 *varr, cgm_vec3 *narr, cgm_vec2 *tarr, struct rbtree *rbtree);
+
+static char *cleanline(char *s);
+static char *parse_idx(char *ptr, int *idx, int arrsz);
+static char *parse_face_vert(char *ptr, struct facevertex *fv, int numv, int numt, int numn);
+
+static int load_mtllib(struct scenefile *scn, const char *path_prefix, const char *mtlfname);
+static void free_mtllist(struct material *mtl);
+static void conv_mtl(struct material *mm, struct objmtl *om, const char *path_prefix);
+
+static int cmp_facevert(const void *ap, const void *bp);
+static void free_rbnode_key(struct rbnode *n, void *cls);
+
+#define GROW_ARRAY(arr, sz) \
+ do { \
+ int newsz = (sz) ? (sz) * 2 : 16; \
+ void *tmp = realloc(arr, newsz * sizeof *(arr)); \
+ if(!tmp) { \
+ fprintf(stderr, "failed to grow array to %d\n", newsz); \
+ goto fail; \
+ } \
+ arr = tmp; \
+ sz = newsz; \
+ } while(0)
+
+
+int load_scenefile(struct scenefile *scn, const char *fname)
+{
+ int i, nlines, res = -1;
+ FILE *fp;
+ char buf[256], *line, *ptr, *path_prefix;
+ int varr_size, varr_max, narr_size, narr_max, tarr_size, tarr_max;
+ cgm_vec3 v, *varr = 0, *narr = 0;
+ cgm_vec2 *tarr = 0;
+ struct facevertex fv[4];
+ struct mesh *mesh;
+ struct material *mtl = 0;
+ char *sep;
+ struct rbtree *rbtree = 0;
+
+
+ varr_size = varr_max = narr_size = narr_max = tarr_size = tarr_max = 0;
+ varr = narr = 0;
+ tarr = 0;
+
+ if(!(fp = fopen(fname, "rb"))) {
+ fprintf(stderr, "load_scenefile: failed to open %s\n", fname);
+ return -1;
+ }
+
+ if(!(rbtree = rb_create(cmp_facevert))) {
+ fprintf(stderr, "load_scenefile: failed to create facevertex search tree\n");
+ fclose(fp);
+ return -1;
+ }
+ rb_set_delete_func(rbtree, free_rbnode_key, 0);
+
+ strcpy(buf, fname);
+ if((sep = strrchr(buf, '/'))) {
+ sep[1] = 0;
+ } else {
+ buf[0] = 0;
+ }
+ path_prefix = alloca(strlen(buf) + 1);
+ strcpy(path_prefix, buf);
+
+ if(!(mesh = malloc(sizeof *mesh))) {
+ fprintf(stderr, "failed to allocate mesh\n");
+ fclose(fp);
+ return -1;
+ }
+ init_mesh(mesh);
+
+ scn->meshlist = 0;
+ scn->num_meshes = 0;
+
+ nlines = 0;
+ while(fgets(buf, sizeof buf, fp)) {
+ nlines++;
+ if(!(line = cleanline(buf))) {
+ continue;
+ }
+
+ switch(line[0]) {
+ case 'v':
+ v.x = v.y = v.z = 0.0f;
+ if(sscanf(line + 2, "%f %f %f", &v.x, &v.y, &v.z) < 2) {
+ break;
+ }
+ if(isspace(line[1])) {
+ if(varr_size >= varr_max) {
+ GROW_ARRAY(varr, varr_max);
+ }
+ varr[varr_size++] = v;
+ } else if(line[1] == 't' && isspace(line[2])) {
+ if(tarr_size >= tarr_max) {
+ GROW_ARRAY(tarr, tarr_max);
+ }
+ tarr[tarr_size++] = *(cgm_vec2*)&v;
+ } else if(line[1] == 'n' && isspace(line[2])) {
+ if(narr_size >= narr_max) {
+ GROW_ARRAY(narr, narr_max);
+ }
+ narr[narr_size++] = v;
+ }
+ break;
+
+ case 'f':
+ if(!isspace(line[1])) break;
+
+ ptr = line + 2;
+
+ for(i=0; i<3; i++) {
+ if(!(ptr = parse_face_vert(ptr, fv + i, varr_size, tarr_size, narr_size))) {
+ break;
+ }
+ if(proc_facevert(mesh, fv + i, varr, narr, tarr, rbtree) == -1) {
+ break;
+ }
+ }
+
+ if(parse_face_vert(ptr, fv + 3, varr_size, tarr_size, narr_size)) {
+ proc_facevert(mesh, fv, varr, narr, tarr, rbtree);
+ proc_facevert(mesh, fv + 2, varr, narr, tarr, rbtree);
+ proc_facevert(mesh, fv + 3, varr, narr, tarr, rbtree);
+ }
+ break;
+
+ case 'o':
+ case 'g':
+ if(mesh->num_verts) {
+ mesh->mtl = mtl;
+ mesh->next = scn->meshlist;
+ scn->meshlist = mesh;
+ scn->num_meshes++;
+
+ if(!(mesh = malloc(sizeof *mesh))) {
+ fprintf(stderr, "failed to allocate mesh\n");
+ goto fail;
+ }
+ init_mesh(mesh);
+ }
+ break;
+
+ case 'm':
+ if(memcmp(line, "mtllib", 6) == 0 && (line = cleanline(line + 6))) {
+ free_mtllist(scn->mtllist);
+ load_mtllib(scn, path_prefix, line);
+ }
+ break;
+
+ case 'u':
+ if(memcmp(line, "usemtl", 6) == 0 && (line = cleanline(line + 6))) {
+ mtl = scn->mtllist;
+ while(mtl) {
+ if(strcmp(mtl->name, line) == 0) {
+ break;
+ }
+ mtl = mtl->next;
+ }
+ }
+ break;
+
+ default:
+ break;
+ }
+ }
+
+ if(mesh->num_verts) {
+ mesh->mtl = mtl;
+ mesh->next = scn->meshlist;
+ scn->meshlist = mesh;
+ scn->num_meshes++;
+ } else {
+ free(mesh);
+ }
+ mesh = 0;
+
+ printf("load_scenefile: loaded %d meshes, %d vertices\n", scn->num_meshes,
+ varr_size);
+
+ res = 0;
+
+fail:
+ fclose(fp);
+ free(mesh);
+ free(varr);
+ free(narr);
+ free(tarr);
+ rb_free(rbtree);
+ return res;
+}
+
+static int proc_facevert(struct mesh *mesh, struct facevertex *fv,
+ cgm_vec3 *varr, cgm_vec3 *narr, cgm_vec2 *tarr, struct rbtree *rbtree)
+{
+ struct rbnode *node;
+ unsigned int idx, newidx;
+ struct facevertex *newfv;
+ struct vertex v;
+
+ if((node = rb_find(rbtree, &fv))) {
+ idx = (unsigned int)node->data;
+ assert(idx < mesh->num_verts);
+ } else {
+ newidx = mesh->num_verts;
+
+ v.pos = varr[fv->vidx];
+ if(fv->nidx >= 0) {
+ v.norm = narr[fv->nidx];
+ }
+ if(fv->tidx >= 0) {
+ v.tex = tarr[fv->tidx];
+ }
+ add_mesh_vertex(mesh, &v);
+ add_mesh_index(mesh, newidx);
+ }
+
+ if((newfv = malloc(sizeof *newfv))) {
+ *newfv = *fv;
+ }
+ if(!newfv || rb_insert(rbtree, newfv, (void*)newidx) == -1) {
+ fprintf(stderr, "load_scenefile: failed to insert facevertex to rbtree\n");
+ free(newfv);
+ return -1;
+ }
+ return 0;
+}
+
+void destroy_scenefile(struct scenefile *scn)
+{
+ struct mesh *m;
+ while(scn->meshlist) {
+ m = scn->meshlist;
+ scn->meshlist = scn->meshlist->next;
+ free(m);
+ }
+}
+
+static char *cleanline(char *s)
+{
+ char *ptr;
+
+ if((ptr = strchr(s, '#'))) *ptr = 0;
+
+ while(*s && isspace(*s)) s++;
+ ptr = s + strlen(s) - 1;
+ while(ptr >= s && isspace(*ptr)) *ptr-- = 0;
+
+ return *s ? s : 0;
+}
+
+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)
+{
+ fv->tidx = fv->nidx = -1;
+
+ if(!(ptr = parse_idx(ptr, &fv->vidx, numv)))
+ return 0;
+ if(*ptr != '/') return (!*ptr || isspace(*ptr)) ? ptr : 0;
+
+ if(*++ptr == '/') { /* no texcoord */
+ ++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 load_mtllib(struct scenefile *scn, const char *path_prefix, const char *mtlfname)
+{
+ FILE *fp;
+ char buf[256], *line;
+ struct objmtl om;
+ struct material *mtl;
+
+ if(path_prefix && *path_prefix) {
+ sprintf(buf, "%s/%s", path_prefix, mtlfname);
+ } else {
+ strcpy(buf, mtlfname);
+ }
+
+ if(!(fp = fopen(buf, "rb"))) {
+ return -1;
+ }
+
+ while(fgets(buf, sizeof buf, fp)) {
+ if(!(line = cleanline(buf))) {
+ continue;
+ }
+
+ if(memcmp(line, "newmtl", 6) == 0) {
+ if(mtl) {
+ mtl->next = scn->mtllist;
+ scn->mtllist = mtl;
+ }
+ if((mtl = calloc(1, sizeof *mtl))) {
+ if((line = cleanline(line + 6))) {
+ mtl->name = strdup(line);
+ }
+ }
+ } else if(memcmp(line, "Kd", 2) == 0) {
+ sscanf(line + 3, "%f %f %f", &om.kd.x, &om.kd.y, &om.kd.z);
+ } else if(memcmp(line, "Ks", 2) == 0) {
+ sscanf(line + 3, "%f %f %f", &om.ks.x, &om.ks.y, &om.ks.z);
+ } else if(memcmp(line, "Ke", 2) == 0) {
+ sscanf(line + 3, "%f %f %f", &om.ke.x, &om.ke.y, &om.ke.z);
+ } else if(memcmp(line, "Ni", 2) == 0) {
+ om.ior = atof(line + 3);
+ } else if(line[0] == 'd' && isspace(line[1])) {
+ om.alpha = atof(line + 2);
+ } else if(memcmp(line, "map_Kd", 6) == 0) {
+ if((line = cleanline(line + 6))) {
+ om.map_kd = strdup(line);
+ }
+ } else if(memcmp(line, "map_Ke", 6) == 0) {
+ if((line = cleanline(line + 6))) {
+ om.map_ke = strdup(line);
+ }
+ } else if(memcmp(line, "map_d", 5) == 0) {
+ if((line = cleanline(line + 5))) {
+ om.map_alpha = strdup(line);
+ }
+ }
+ conv_mtl(mtl, &om, path_prefix);
+ }
+
+ if(mtl) {
+ mtl->next = scn->mtllist;
+ scn->mtllist = mtl;
+ }
+
+ fclose(fp);
+ return 0;
+}
+
+static void free_mtllist(struct material *mtl)
+{
+ while(mtl) {
+ void *tmp = mtl;
+ mtl = mtl->next;
+ free(tmp);
+ }
+}
+
+static void conv_mtl(struct material *mm, struct objmtl *om, const char *path_prefix)
+{
+ char *fname = 0, *suffix = 0;
+ int len, prefix_len, maxlen = 0;
+
+ memset(mm, 0, sizeof *mm);
+ mm->name = strdup(om->name);
+ mm->color = om->kd;
+ mm->spec = om->ks;
+ mm->shininess = om->shin;
+
+ if(om->map_kd && (len = strlen(om->map_kd)) > maxlen) maxlen = len;
+ if(om->map_ke && (len = strlen(om->map_ke)) > maxlen) maxlen = len;
+ if(om->map_alpha && (len = strlen(om->map_alpha)) > maxlen) maxlen = len;
+
+ if(maxlen) {
+ prefix_len = strlen(path_prefix);
+ fname = alloca(maxlen + prefix_len + 2);
+ suffix = fname + prefix_len;
+ strcpy(fname, path_prefix);
+ }
+
+ /*
+ if(om->map_kd) {
+ strcpy(suffix, om->map_kd);
+ mm->tex[TEX_DIFFUSE] = get_image(fname);
+ }
+ */
+}
+
+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);
+}
--- /dev/null
+#ifndef SCENEFILE_H_
+#define SCENEFILE_H_
+
+#include "mesh.h"
+
+struct scenefile {
+ struct mesh *meshlist;
+ int num_meshes;
+
+ struct material *mtllist;
+ int num_mtl;
+};
+
+int load_scenefile(struct scenefile *scn, const char *fname);
+void destroy_scenefile(struct scenefile *scn);
+
+#endif /* SCENEFILE_H_ */
projects / vrlugburz / commitdiff