--- /dev/null
+src = $(wildcard src/*.cc src/math/*.cc src/shaders/*.cc)
+csrc = $(wildcard src/*.c)
+obj = $(src:.cc=.o) $(csrc:.c=.o)
+dep = $(obj:.o=.d)
+bin = hair
+
+dbg = -g
+opt = -O0
+inc = -Isrc -Isrc/shaders -Isrc/math
+
+CXX = g++
+CXXFLAGS = -pedantic -Wall $(dbg) $(opt) $(inc)
+LDFLAGS = -lGL -lGLU -lglut -lGLEW -limago -lassimp
+
+$(bin): $(obj)
+ $(CXX) -o $@ $(obj) $(LDFLAGS)
+
+-include $(dep)
+
+%.d: %.cc
+ @$(CPP) $(CXXFLAGS) $< -MM -MT $(@:.d=.o) >$@
+
+%.d: %.c
+ @$(CPP) $(CFLAGS) $< -MM -MT $(@:.d=.o) >$@
+
+.PHONY: clean
+clean:
+ rm -f $(obj) $(bin) $(dep)
--- /dev/null
+#include <gmath/gmath.h>
+#include <stdlib.h>
+#include <string>
+
+#include "kdtree.h"
+#include "hair.h"
+
+struct Triangle {
+ Vec3 v[3];
+ Vec3 n[3];
+};
+
+Hair::Hair() {}
+Hair::~Hair() {}
+
+static Vec3 calc_rand_point(const Triangle &tr, Vec3 *bary)
+{
+ float u = (float)rand() / (float)RAND_MAX;
+ float v = (float)rand() / (float)RAND_MAX;
+
+ if(u + v > 1) {
+ u = 1 - u;
+ v = 1 - v;
+ }
+
+ float c = 1 - (u + v);
+
+ Vec3 rp = u * tr.v[0] + v * tr.v[1] + c * tr.v[3];
+
+ bary->x = u;
+ bary->y = v;
+ bary->z = c;
+
+ return rp;
+}
+
+static void get_spawn_triangles(const Mesh *m, float thresh, std::vector<Triangle> *faces)
+{
+ for(size_t i=0; i<m->indices.size() / 3; i++) {
+ bool is_spawn = true;
+ int idx[3];
+ for(int j=0; j<3; j++) {
+ idx[j] = i * 3 + j;
+ float c = (m->colors[idx[j]].x + m->colors[idx[j]].y + m->colors[idx[j]].z) / 3;
+ if (c >= thresh) {
+ is_spawn = false;
+ break;
+ }
+ }
+
+ if(is_spawn) {
+ Triangle t;
+ for(int j=0; j<3; j++) {
+ t.v[j] = m->vertices[idx[j]];
+ t.n[j] = m->normals[idx[j]];
+ }
+ faces->push_back(t);
+ }
+ }
+}
+
+bool Hair::init(const Mesh *m, int max_num_spawns, float thresh)
+{
+ std::vector<Triangle> faces;
+ kdtree *kd = kd_create(3);
+ const float min_dist = 0.05;
+
+ get_spawn_triangles(m, thresh, &faces);
+
+ for(int i = 0; i < max_num_spawns; i++) {
+ // Poisson
+ int rnum = (float)((float)rand() / (float)RAND_MAX) * faces.size();
+ Triangle rtriangle = faces[rnum];
+ Vec3 bary;
+ Vec3 rpoint = calc_rand_point(rtriangle, &bary);
+
+ kdres *res = kd_nearest3f(kd, rpoint.x, rpoint.y, rpoint.z);
+ if (!kd_res_end(res)) {
+ Vec3 nearest;
+ kd_res_item3f(res, &nearest.x, &nearest.y, &nearest.z);
+ if(distance_sq(rpoint, nearest) < min_dist * min_dist)
+ continue;
+ }
+
+ /* weighted sum of the triangle's vertex normals */
+ Vec3 spawn_dir = rtriangle.n[0] * bary.x + rtriangle.n[1] * bary.y + rtriangle.n[2] * bary.z;
+ spawn_directions.push_back(normalize(spawn_dir));
+ spawn_points.push_back(rpoint);
+ kd_insert3f(kd, rpoint.x, rpoint.y, rpoint.z, 0);
+ }
+
+ kd_free(kd);
+ return true;
+}
+
+void Hair::draw() const
+{
+}
--- /dev/null
+#ifndef PARTICLES_H_
+#define PARTICLES_H_
+
+#include <gmath/gmath.h>
+
+#include "mesh.h"
+
+class Hair {
+private:
+ std::vector<Vec3> spawn_points;
+ std::vector<Vec3> spawn_directions;
+
+public:
+ Hair();
+ ~Hair();
+
+ bool init(const Mesh *m, int num_spawns, float thresh = 0.4);
+ void draw() const;
+};
+
+#endif //PARTICLES_H_
+
--- /dev/null
+/*
+This file is part of ``kdtree'', a library for working with kd-trees.
+Copyright (C) 2007-2011 John Tsiombikas <nuclear@member.fsf.org>
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+
+1. Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+2. Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+3. The name of the author may not be used to endorse or promote products
+ derived from this software without specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
+WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
+EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
+OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
+IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY
+OF SUCH DAMAGE.
+*/
+/* single nearest neighbor search written by Tamas Nepusz <tamas@cs.rhul.ac.uk> */
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <math.h>
+#include "kdtree.h"
+
+#if defined(WIN32) || defined(__WIN32__)
+#include <malloc.h>
+#endif
+
+#ifdef USE_LIST_NODE_ALLOCATOR
+
+#ifndef NO_PTHREADS
+#include <pthread.h>
+#else
+
+#ifndef I_WANT_THREAD_BUGS
+#error "You are compiling with the fast list node allocator, with pthreads disabled! This WILL break if used from multiple threads."
+#endif /* I want thread bugs */
+
+#endif /* pthread support */
+#endif /* use list node allocator */
+
+struct kdhyperrect {
+ int dim;
+ double *min, *max; /* minimum/maximum coords */
+};
+
+struct kdnode {
+ double *pos;
+ int dir;
+ void *data;
+
+ struct kdnode *left, *right; /* negative/positive side */
+};
+
+struct res_node {
+ struct kdnode *item;
+ double dist_sq;
+ struct res_node *next;
+};
+
+struct kdtree {
+ int dim;
+ struct kdnode *root;
+ struct kdhyperrect *rect;
+ void (*destr)(void*);
+};
+
+struct kdres {
+ struct kdtree *tree;
+ struct res_node *rlist, *riter;
+ int size;
+};
+
+#define SQ(x) ((x) * (x))
+
+
+static void clear_rec(struct kdnode *node, void (*destr)(void*));
+static int insert_rec(struct kdnode **node, const double *pos, void *data, int dir, int dim);
+static int rlist_insert(struct res_node *list, struct kdnode *item, double dist_sq);
+static void clear_results(struct kdres *set);
+
+static struct kdhyperrect* hyperrect_create(int dim, const double *min, const double *max);
+static void hyperrect_free(struct kdhyperrect *rect);
+static struct kdhyperrect* hyperrect_duplicate(const struct kdhyperrect *rect);
+static void hyperrect_extend(struct kdhyperrect *rect, const double *pos);
+static double hyperrect_dist_sq(struct kdhyperrect *rect, const double *pos);
+
+#ifdef USE_LIST_NODE_ALLOCATOR
+static struct res_node *alloc_resnode(void);
+static void free_resnode(struct res_node*);
+#else
+#define alloc_resnode() malloc(sizeof(struct res_node))
+#define free_resnode(n) free(n)
+#endif
+
+
+
+struct kdtree *kd_create(int k)
+{
+ struct kdtree *tree;
+
+ if(!(tree = malloc(sizeof *tree))) {
+ return 0;
+ }
+
+ tree->dim = k;
+ tree->root = 0;
+ tree->destr = 0;
+ tree->rect = 0;
+
+ return tree;
+}
+
+void kd_free(struct kdtree *tree)
+{
+ if(tree) {
+ kd_clear(tree);
+ free(tree);
+ }
+}
+
+static void clear_rec(struct kdnode *node, void (*destr)(void*))
+{
+ if(!node) return;
+
+ clear_rec(node->left, destr);
+ clear_rec(node->right, destr);
+
+ if(destr) {
+ destr(node->data);
+ }
+ free(node->pos);
+ free(node);
+}
+
+void kd_clear(struct kdtree *tree)
+{
+ clear_rec(tree->root, tree->destr);
+ tree->root = 0;
+
+ if (tree->rect) {
+ hyperrect_free(tree->rect);
+ tree->rect = 0;
+ }
+}
+
+void kd_data_destructor(struct kdtree *tree, void (*destr)(void*))
+{
+ tree->destr = destr;
+}
+
+
+static int insert_rec(struct kdnode **nptr, const double *pos, void *data, int dir, int dim)
+{
+ int new_dir;
+ struct kdnode *node;
+
+ if(!*nptr) {
+ if(!(node = malloc(sizeof *node))) {
+ return -1;
+ }
+ if(!(node->pos = malloc(dim * sizeof *node->pos))) {
+ free(node);
+ return -1;
+ }
+ memcpy(node->pos, pos, dim * sizeof *node->pos);
+ node->data = data;
+ node->dir = dir;
+ node->left = node->right = 0;
+ *nptr = node;
+ return 0;
+ }
+
+ node = *nptr;
+ new_dir = (node->dir + 1) % dim;
+ if(pos[node->dir] < node->pos[node->dir]) {
+ return insert_rec(&(*nptr)->left, pos, data, new_dir, dim);
+ }
+ return insert_rec(&(*nptr)->right, pos, data, new_dir, dim);
+}
+
+int kd_insert(struct kdtree *tree, const double *pos, void *data)
+{
+ if (insert_rec(&tree->root, pos, data, 0, tree->dim)) {
+ return -1;
+ }
+
+ if (tree->rect == 0) {
+ tree->rect = hyperrect_create(tree->dim, pos, pos);
+ } else {
+ hyperrect_extend(tree->rect, pos);
+ }
+
+ return 0;
+}
+
+int kd_insertf(struct kdtree *tree, const float *pos, void *data)
+{
+ static double sbuf[16];
+ double *bptr, *buf = 0;
+ int res, dim = tree->dim;
+
+ if(dim > 16) {
+#ifndef NO_ALLOCA
+ if(dim <= 256)
+ bptr = buf = alloca(dim * sizeof *bptr);
+ else
+#endif
+ if(!(bptr = buf = malloc(dim * sizeof *bptr))) {
+ return -1;
+ }
+ } else {
+ bptr = buf = sbuf;
+ }
+
+ while(dim-- > 0) {
+ *bptr++ = *pos++;
+ }
+
+ res = kd_insert(tree, buf, data);
+#ifndef NO_ALLOCA
+ if(tree->dim > 256)
+#else
+ if(tree->dim > 16)
+#endif
+ free(buf);
+ return res;
+}
+
+int kd_insert3(struct kdtree *tree, double x, double y, double z, void *data)
+{
+ double buf[3];
+ buf[0] = x;
+ buf[1] = y;
+ buf[2] = z;
+ return kd_insert(tree, buf, data);
+}
+
+int kd_insert3f(struct kdtree *tree, float x, float y, float z, void *data)
+{
+ double buf[3];
+ buf[0] = x;
+ buf[1] = y;
+ buf[2] = z;
+ return kd_insert(tree, buf, data);
+}
+
+static int find_nearest(struct kdnode *node, const double *pos, double range, struct res_node *list, int ordered, int dim)
+{
+ double dist_sq, dx;
+ int i, ret, added_res = 0;
+
+ if(!node) return 0;
+
+ dist_sq = 0;
+ for(i=0; i<dim; i++) {
+ dist_sq += SQ(node->pos[i] - pos[i]);
+ }
+ if(dist_sq <= SQ(range)) {
+ if(rlist_insert(list, node, ordered ? dist_sq : -1.0) == -1) {
+ return -1;
+ }
+ added_res = 1;
+ }
+
+ dx = pos[node->dir] - node->pos[node->dir];
+
+ ret = find_nearest(dx <= 0.0 ? node->left : node->right, pos, range, list, ordered, dim);
+ if(ret >= 0 && fabs(dx) < range) {
+ added_res += ret;
+ ret = find_nearest(dx <= 0.0 ? node->right : node->left, pos, range, list, ordered, dim);
+ }
+ if(ret == -1) {
+ return -1;
+ }
+ added_res += ret;
+
+ return added_res;
+}
+
+#if 0
+static int find_nearest_n(struct kdnode *node, const double *pos, double range, int num, struct rheap *heap, int dim)
+{
+ double dist_sq, dx;
+ int i, ret, added_res = 0;
+
+ if(!node) return 0;
+
+ /* if the photon is close enough, add it to the result heap */
+ dist_sq = 0;
+ for(i=0; i<dim; i++) {
+ dist_sq += SQ(node->pos[i] - pos[i]);
+ }
+ if(dist_sq <= range_sq) {
+ if(heap->size >= num) {
+ /* get furthest element */
+ struct res_node *maxelem = rheap_get_max(heap);
+
+ /* and check if the new one is closer than that */
+ if(maxelem->dist_sq > dist_sq) {
+ rheap_remove_max(heap);
+
+ if(rheap_insert(heap, node, dist_sq) == -1) {
+ return -1;
+ }
+ added_res = 1;
+
+ range_sq = dist_sq;
+ }
+ } else {
+ if(rheap_insert(heap, node, dist_sq) == -1) {
+ return =1;
+ }
+ added_res = 1;
+ }
+ }
+
+
+ /* find signed distance from the splitting plane */
+ dx = pos[node->dir] - node->pos[node->dir];
+
+ ret = find_nearest_n(dx <= 0.0 ? node->left : node->right, pos, range, num, heap, dim);
+ if(ret >= 0 && fabs(dx) < range) {
+ added_res += ret;
+ ret = find_nearest_n(dx <= 0.0 ? node->right : node->left, pos, range, num, heap, dim);
+ }
+
+}
+#endif
+
+static void kd_nearest_i(struct kdnode *node, const double *pos, struct kdnode **result, double *result_dist_sq, struct kdhyperrect* rect)
+{
+ int dir = node->dir;
+ int i;
+ double dummy, dist_sq;
+ struct kdnode *nearer_subtree, *farther_subtree;
+ double *nearer_hyperrect_coord, *farther_hyperrect_coord;
+
+ /* Decide whether to go left or right in the tree */
+ dummy = pos[dir] - node->pos[dir];
+ if (dummy <= 0) {
+ nearer_subtree = node->left;
+ farther_subtree = node->right;
+ nearer_hyperrect_coord = rect->max + dir;
+ farther_hyperrect_coord = rect->min + dir;
+ } else {
+ nearer_subtree = node->right;
+ farther_subtree = node->left;
+ nearer_hyperrect_coord = rect->min + dir;
+ farther_hyperrect_coord = rect->max + dir;
+ }
+
+ if (nearer_subtree) {
+ /* Slice the hyperrect to get the hyperrect of the nearer subtree */
+ dummy = *nearer_hyperrect_coord;
+ *nearer_hyperrect_coord = node->pos[dir];
+ /* Recurse down into nearer subtree */
+ kd_nearest_i(nearer_subtree, pos, result, result_dist_sq, rect);
+ /* Undo the slice */
+ *nearer_hyperrect_coord = dummy;
+ }
+
+ /* Check the distance of the point at the current node, compare it
+ * with our best so far */
+ dist_sq = 0;
+ for(i=0; i < rect->dim; i++) {
+ dist_sq += SQ(node->pos[i] - pos[i]);
+ }
+ if (dist_sq < *result_dist_sq) {
+ *result = node;
+ *result_dist_sq = dist_sq;
+ }
+
+ if (farther_subtree) {
+ /* Get the hyperrect of the farther subtree */
+ dummy = *farther_hyperrect_coord;
+ *farther_hyperrect_coord = node->pos[dir];
+ /* Check if we have to recurse down by calculating the closest
+ * point of the hyperrect and see if it's closer than our
+ * minimum distance in result_dist_sq. */
+ if (hyperrect_dist_sq(rect, pos) < *result_dist_sq) {
+ /* Recurse down into farther subtree */
+ kd_nearest_i(farther_subtree, pos, result, result_dist_sq, rect);
+ }
+ /* Undo the slice on the hyperrect */
+ *farther_hyperrect_coord = dummy;
+ }
+}
+
+struct kdres *kd_nearest(struct kdtree *kd, const double *pos)
+{
+ struct kdhyperrect *rect;
+ struct kdnode *result;
+ struct kdres *rset;
+ double dist_sq;
+ int i;
+
+ if (!kd) return 0;
+ if (!kd->rect) return 0;
+
+ /* Allocate result set */
+ if(!(rset = malloc(sizeof *rset))) {
+ return 0;
+ }
+ if(!(rset->rlist = alloc_resnode())) {
+ free(rset);
+ return 0;
+ }
+ rset->rlist->next = 0;
+ rset->tree = kd;
+
+ /* Duplicate the bounding hyperrectangle, we will work on the copy */
+ if (!(rect = hyperrect_duplicate(kd->rect))) {
+ kd_res_free(rset);
+ return 0;
+ }
+
+ /* Our first guesstimate is the root node */
+ result = kd->root;
+ dist_sq = 0;
+ for (i = 0; i < kd->dim; i++)
+ dist_sq += SQ(result->pos[i] - pos[i]);
+
+ /* Search for the nearest neighbour recursively */
+ kd_nearest_i(kd->root, pos, &result, &dist_sq, rect);
+
+ /* Free the copy of the hyperrect */
+ hyperrect_free(rect);
+
+ /* Store the result */
+ if (result) {
+ if (rlist_insert(rset->rlist, result, -1.0) == -1) {
+ kd_res_free(rset);
+ return 0;
+ }
+ rset->size = 1;
+ kd_res_rewind(rset);
+ return rset;
+ } else {
+ kd_res_free(rset);
+ return 0;
+ }
+}
+
+struct kdres *kd_nearestf(struct kdtree *tree, const float *pos)
+{
+ static double sbuf[16];
+ double *bptr, *buf = 0;
+ int dim = tree->dim;
+ struct kdres *res;
+
+ if(dim > 16) {
+#ifndef NO_ALLOCA
+ if(dim <= 256)
+ bptr = buf = alloca(dim * sizeof *bptr);
+ else
+#endif
+ if(!(bptr = buf = malloc(dim * sizeof *bptr))) {
+ return 0;
+ }
+ } else {
+ bptr = buf = sbuf;
+ }
+
+ while(dim-- > 0) {
+ *bptr++ = *pos++;
+ }
+
+ res = kd_nearest(tree, buf);
+#ifndef NO_ALLOCA
+ if(tree->dim > 256)
+#else
+ if(tree->dim > 16)
+#endif
+ free(buf);
+ return res;
+}
+
+struct kdres *kd_nearest3(struct kdtree *tree, double x, double y, double z)
+{
+ double pos[3];
+ pos[0] = x;
+ pos[1] = y;
+ pos[2] = z;
+ return kd_nearest(tree, pos);
+}
+
+struct kdres *kd_nearest3f(struct kdtree *tree, float x, float y, float z)
+{
+ double pos[3];
+ pos[0] = x;
+ pos[1] = y;
+ pos[2] = z;
+ return kd_nearest(tree, pos);
+}
+
+/* ---- nearest N search ---- */
+/*
+static kdres *kd_nearest_n(struct kdtree *kd, const double *pos, int num)
+{
+ int ret;
+ struct kdres *rset;
+
+ if(!(rset = malloc(sizeof *rset))) {
+ return 0;
+ }
+ if(!(rset->rlist = alloc_resnode())) {
+ free(rset);
+ return 0;
+ }
+ rset->rlist->next = 0;
+ rset->tree = kd;
+
+ if((ret = find_nearest_n(kd->root, pos, range, num, rset->rlist, kd->dim)) == -1) {
+ kd_res_free(rset);
+ return 0;
+ }
+ rset->size = ret;
+ kd_res_rewind(rset);
+ return rset;
+}*/
+
+struct kdres *kd_nearest_range(struct kdtree *kd, const double *pos, double range)
+{
+ int ret;
+ struct kdres *rset;
+
+ if(!(rset = malloc(sizeof *rset))) {
+ return 0;
+ }
+ if(!(rset->rlist = alloc_resnode())) {
+ free(rset);
+ return 0;
+ }
+ rset->rlist->next = 0;
+ rset->tree = kd;
+
+ if((ret = find_nearest(kd->root, pos, range, rset->rlist, 0, kd->dim)) == -1) {
+ kd_res_free(rset);
+ return 0;
+ }
+ rset->size = ret;
+ kd_res_rewind(rset);
+ return rset;
+}
+
+struct kdres *kd_nearest_rangef(struct kdtree *kd, const float *pos, float range)
+{
+ static double sbuf[16];
+ double *bptr, *buf = 0;
+ int dim = kd->dim;
+ struct kdres *res;
+
+ if(dim > 16) {
+#ifndef NO_ALLOCA
+ if(dim <= 256)
+ bptr = buf = alloca(dim * sizeof *bptr);
+ else
+#endif
+ if(!(bptr = buf = malloc(dim * sizeof *bptr))) {
+ return 0;
+ }
+ } else {
+ bptr = buf = sbuf;
+ }
+
+ while(dim-- > 0) {
+ *bptr++ = *pos++;
+ }
+
+ res = kd_nearest_range(kd, buf, range);
+#ifndef NO_ALLOCA
+ if(kd->dim > 256)
+#else
+ if(kd->dim > 16)
+#endif
+ free(buf);
+ return res;
+}
+
+struct kdres *kd_nearest_range3(struct kdtree *tree, double x, double y, double z, double range)
+{
+ double buf[3];
+ buf[0] = x;
+ buf[1] = y;
+ buf[2] = z;
+ return kd_nearest_range(tree, buf, range);
+}
+
+struct kdres *kd_nearest_range3f(struct kdtree *tree, float x, float y, float z, float range)
+{
+ double buf[3];
+ buf[0] = x;
+ buf[1] = y;
+ buf[2] = z;
+ return kd_nearest_range(tree, buf, range);
+}
+
+void kd_res_free(struct kdres *rset)
+{
+ clear_results(rset);
+ free_resnode(rset->rlist);
+ free(rset);
+}
+
+int kd_res_size(struct kdres *set)
+{
+ return (set->size);
+}
+
+void kd_res_rewind(struct kdres *rset)
+{
+ rset->riter = rset->rlist->next;
+}
+
+int kd_res_end(struct kdres *rset)
+{
+ return rset->riter == 0;
+}
+
+int kd_res_next(struct kdres *rset)
+{
+ rset->riter = rset->riter->next;
+ return rset->riter != 0;
+}
+
+void *kd_res_item(struct kdres *rset, double *pos)
+{
+ if(rset->riter) {
+ if(pos) {
+ memcpy(pos, rset->riter->item->pos, rset->tree->dim * sizeof *pos);
+ }
+ return rset->riter->item->data;
+ }
+ return 0;
+}
+
+void *kd_res_itemf(struct kdres *rset, float *pos)
+{
+ if(rset->riter) {
+ if(pos) {
+ int i;
+ for(i=0; i<rset->tree->dim; i++) {
+ pos[i] = rset->riter->item->pos[i];
+ }
+ }
+ return rset->riter->item->data;
+ }
+ return 0;
+}
+
+void *kd_res_item3(struct kdres *rset, double *x, double *y, double *z)
+{
+ if(rset->riter) {
+ if(*x) *x = rset->riter->item->pos[0];
+ if(*y) *y = rset->riter->item->pos[1];
+ if(*z) *z = rset->riter->item->pos[2];
+ return rset->riter->item->data;
+ }
+ return 0;
+}
+
+void *kd_res_item3f(struct kdres *rset, float *x, float *y, float *z)
+{
+ if(rset->riter) {
+ if(*x) *x = rset->riter->item->pos[0];
+ if(*y) *y = rset->riter->item->pos[1];
+ if(*z) *z = rset->riter->item->pos[2];
+ return rset->riter->item->data;
+ }
+ return 0;
+}
+
+void *kd_res_item_data(struct kdres *set)
+{
+ return kd_res_item(set, 0);
+}
+
+/* ---- hyperrectangle helpers ---- */
+static struct kdhyperrect* hyperrect_create(int dim, const double *min, const double *max)
+{
+ size_t size = dim * sizeof(double);
+ struct kdhyperrect* rect = 0;
+
+ if (!(rect = malloc(sizeof(struct kdhyperrect)))) {
+ return 0;
+ }
+
+ rect->dim = dim;
+ if (!(rect->min = malloc(size))) {
+ free(rect);
+ return 0;
+ }
+ if (!(rect->max = malloc(size))) {
+ free(rect->min);
+ free(rect);
+ return 0;
+ }
+ memcpy(rect->min, min, size);
+ memcpy(rect->max, max, size);
+
+ return rect;
+}
+
+static void hyperrect_free(struct kdhyperrect *rect)
+{
+ free(rect->min);
+ free(rect->max);
+ free(rect);
+}
+
+static struct kdhyperrect* hyperrect_duplicate(const struct kdhyperrect *rect)
+{
+ return hyperrect_create(rect->dim, rect->min, rect->max);
+}
+
+static void hyperrect_extend(struct kdhyperrect *rect, const double *pos)
+{
+ int i;
+
+ for (i=0; i < rect->dim; i++) {
+ if (pos[i] < rect->min[i]) {
+ rect->min[i] = pos[i];
+ }
+ if (pos[i] > rect->max[i]) {
+ rect->max[i] = pos[i];
+ }
+ }
+}
+
+static double hyperrect_dist_sq(struct kdhyperrect *rect, const double *pos)
+{
+ int i;
+ double result = 0;
+
+ for (i=0; i < rect->dim; i++) {
+ if (pos[i] < rect->min[i]) {
+ result += SQ(rect->min[i] - pos[i]);
+ } else if (pos[i] > rect->max[i]) {
+ result += SQ(rect->max[i] - pos[i]);
+ }
+ }
+
+ return result;
+}
+
+/* ---- static helpers ---- */
+
+#ifdef USE_LIST_NODE_ALLOCATOR
+/* special list node allocators. */
+static struct res_node *free_nodes;
+
+#ifndef NO_PTHREADS
+static pthread_mutex_t alloc_mutex = PTHREAD_MUTEX_INITIALIZER;
+#endif
+
+static struct res_node *alloc_resnode(void)
+{
+ struct res_node *node;
+
+#ifndef NO_PTHREADS
+ pthread_mutex_lock(&alloc_mutex);
+#endif
+
+ if(!free_nodes) {
+ node = malloc(sizeof *node);
+ } else {
+ node = free_nodes;
+ free_nodes = free_nodes->next;
+ node->next = 0;
+ }
+
+#ifndef NO_PTHREADS
+ pthread_mutex_unlock(&alloc_mutex);
+#endif
+
+ return node;
+}
+
+static void free_resnode(struct res_node *node)
+{
+#ifndef NO_PTHREADS
+ pthread_mutex_lock(&alloc_mutex);
+#endif
+
+ node->next = free_nodes;
+ free_nodes = node;
+
+#ifndef NO_PTHREADS
+ pthread_mutex_unlock(&alloc_mutex);
+#endif
+}
+#endif /* list node allocator or not */
+
+
+/* inserts the item. if dist_sq is >= 0, then do an ordered insert */
+/* TODO make the ordering code use heapsort */
+static int rlist_insert(struct res_node *list, struct kdnode *item, double dist_sq)
+{
+ struct res_node *rnode;
+
+ if(!(rnode = alloc_resnode())) {
+ return -1;
+ }
+ rnode->item = item;
+ rnode->dist_sq = dist_sq;
+
+ if(dist_sq >= 0.0) {
+ while(list->next && list->next->dist_sq < dist_sq) {
+ list = list->next;
+ }
+ }
+ rnode->next = list->next;
+ list->next = rnode;
+ return 0;
+}
+
+static void clear_results(struct kdres *rset)
+{
+ struct res_node *tmp, *node = rset->rlist->next;
+
+ while(node) {
+ tmp = node;
+ node = node->next;
+ free_resnode(tmp);
+ }
+
+ rset->rlist->next = 0;
+}
--- /dev/null
+/*
+This file is part of ``kdtree'', a library for working with kd-trees.
+Copyright (C) 2007-2011 John Tsiombikas <nuclear@member.fsf.org>
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+
+1. Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+2. Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+3. The name of the author may not be used to endorse or promote products
+ derived from this software without specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
+WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
+EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
+OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
+IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY
+OF SUCH DAMAGE.
+*/
+#ifndef _KDTREE_H_
+#define _KDTREE_H_
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+struct kdtree;
+struct kdres;
+
+
+/* create a kd-tree for "k"-dimensional data */
+struct kdtree *kd_create(int k);
+
+/* free the struct kdtree */
+void kd_free(struct kdtree *tree);
+
+/* remove all the elements from the tree */
+void kd_clear(struct kdtree *tree);
+
+/* if called with non-null 2nd argument, the function provided
+ * will be called on data pointers (see kd_insert) when nodes
+ * are to be removed from the tree.
+ */
+void kd_data_destructor(struct kdtree *tree, void (*destr)(void*));
+
+/* insert a node, specifying its position, and optional data */
+int kd_insert(struct kdtree *tree, const double *pos, void *data);
+int kd_insertf(struct kdtree *tree, const float *pos, void *data);
+int kd_insert3(struct kdtree *tree, double x, double y, double z, void *data);
+int kd_insert3f(struct kdtree *tree, float x, float y, float z, void *data);
+
+/* Find the nearest node from a given point.
+ *
+ * This function returns a pointer to a result set with at most one element.
+ */
+struct kdres *kd_nearest(struct kdtree *tree, const double *pos);
+struct kdres *kd_nearestf(struct kdtree *tree, const float *pos);
+struct kdres *kd_nearest3(struct kdtree *tree, double x, double y, double z);
+struct kdres *kd_nearest3f(struct kdtree *tree, float x, float y, float z);
+
+/* Find the N nearest nodes from a given point.
+ *
+ * This function returns a pointer to a result set, with at most N elements,
+ * which can be manipulated with the kd_res_* functions.
+ * The returned pointer can be null as an indication of an error. Otherwise
+ * a valid result set is always returned which may contain 0 or more elements.
+ * The result set must be deallocated with kd_res_free after use.
+ */
+/*
+struct kdres *kd_nearest_n(struct kdtree *tree, const double *pos, int num);
+struct kdres *kd_nearest_nf(struct kdtree *tree, const float *pos, int num);
+struct kdres *kd_nearest_n3(struct kdtree *tree, double x, double y, double z);
+struct kdres *kd_nearest_n3f(struct kdtree *tree, float x, float y, float z);
+*/
+
+/* Find any nearest nodes from a given point within a range.
+ *
+ * This function returns a pointer to a result set, which can be manipulated
+ * by the kd_res_* functions.
+ * The returned pointer can be null as an indication of an error. Otherwise
+ * a valid result set is always returned which may contain 0 or more elements.
+ * The result set must be deallocated with kd_res_free after use.
+ */
+struct kdres *kd_nearest_range(struct kdtree *tree, const double *pos, double range);
+struct kdres *kd_nearest_rangef(struct kdtree *tree, const float *pos, float range);
+struct kdres *kd_nearest_range3(struct kdtree *tree, double x, double y, double z, double range);
+struct kdres *kd_nearest_range3f(struct kdtree *tree, float x, float y, float z, float range);
+
+/* frees a result set returned by kd_nearest_range() */
+void kd_res_free(struct kdres *set);
+
+/* returns the size of the result set (in elements) */
+int kd_res_size(struct kdres *set);
+
+/* rewinds the result set iterator */
+void kd_res_rewind(struct kdres *set);
+
+/* returns non-zero if the set iterator reached the end after the last element */
+int kd_res_end(struct kdres *set);
+
+/* advances the result set iterator, returns non-zero on success, zero if
+ * there are no more elements in the result set.
+ */
+int kd_res_next(struct kdres *set);
+
+/* returns the data pointer (can be null) of the current result set item
+ * and optionally sets its position to the pointers(s) if not null.
+ */
+void *kd_res_item(struct kdres *set, double *pos);
+void *kd_res_itemf(struct kdres *set, float *pos);
+void *kd_res_item3(struct kdres *set, double *x, double *y, double *z);
+void *kd_res_item3f(struct kdres *set, float *x, float *y, float *z);
+
+/* equivalent to kd_res_item(set, 0) */
+void *kd_res_item_data(struct kdres *set);
+
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _KDTREE_H_ */
--- /dev/null
+#include <GL/glew.h>
+#include <GL/glut.h>
+
+#include <assert.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <string>
+
+#include "mesh.h"
+
+static bool init();
+static void cleanup();
+static void display();
+static void reshape(int x, int y);
+static void keydown(unsigned char key, int x, int y);
+static void mouse(int bn, int st, int x, int y);
+static void motion(int x, int y);
+
+static std::vector<Mesh*> meshes;
+static Mesh *mesh_head;
+
+int win_width, win_height;
+float cam_theta, cam_phi = 25, cam_dist = 8;
+
+int main(int argc, char **argv)
+{
+ glutInit(&argc, argv);
+ glutInitWindowSize(800, 600);
+ glutInitDisplayMode(GLUT_RGB | GLUT_DEPTH | GLUT_DOUBLE);
+ glutCreateWindow("hair test");
+
+ glutDisplayFunc(display);
+ glutReshapeFunc(reshape);
+ glutKeyboardFunc(keydown);
+ glutMouseFunc(mouse);
+ glutMotionFunc(motion);
+
+ if(!init()) {
+ return 1;
+ }
+ atexit(cleanup);
+
+ glutMainLoop();
+ return 0;
+}
+
+static bool init()
+{
+ glewInit();
+
+ glEnable(GL_DEPTH_TEST);
+ glEnable(GL_CULL_FACE);
+ glEnable(GL_COLOR_MATERIAL);
+
+ glEnable(GL_LIGHTING);
+ glEnable(GL_LIGHT0);
+
+ glClearColor(1, 0.5, 0.5, 1);
+ meshes = load_meshes("data/head.fbx");
+ if (meshes.empty()) {
+ fprintf(stderr, "Failed to load mesh.\n");
+ return false;
+ }
+
+ for(size_t i=0; i<meshes.size(); i++) {
+ meshes[i]->calc_bbox();
+
+ Vec3 v0 = meshes[i]->bbox.v0;
+ Vec3 v1 = meshes[i]->bbox.v1;
+
+ printf("mesh: %s\n", meshes[i]->name.c_str());
+ printf("AABB mesh %d: v0: (%f, %f, %f) v1: (%f, %f, %f)\n",
+ (int)i, v0.x, v0.y, v0.z, v1.x, v1.y, v1.z);
+
+ meshes[i]->update_vbo(MESH_ALL);
+ printf("num vertices: %d num triangles: %d\n",
+ (int)meshes[i]->vertices.size(),
+ (int)meshes[i]->indices.size() / 3);
+
+ if(meshes[i]->name == "head") {
+ mesh_head = meshes[i];
+ }
+ }
+
+ return true;
+}
+
+static void cleanup()
+{
+}
+
+static void display()
+{
+ glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
+
+ glMatrixMode(GL_MODELVIEW);
+ glLoadIdentity();
+ glTranslatef(0, 0, -cam_dist);
+ glRotatef(cam_phi, 1, 0, 0);
+ glRotatef(cam_theta, 0, 1, 0);
+
+ glTranslatef(0, -16, 0);
+
+ for(size_t i=0; i<meshes.size(); i++) {
+ meshes[i]->draw();
+ }
+
+ glutSwapBuffers();
+ assert(glGetError() == GL_NO_ERROR);
+}
+
+static void reshape(int x, int y)
+{
+ glViewport(0, 0, x, y);
+ win_width = x;
+ win_height = y;
+
+ glMatrixMode(GL_PROJECTION);
+ glLoadIdentity();
+ gluPerspective(50.0, (float)x / (float)y, 0.5, 500.0);
+}
+
+static void keydown(unsigned char key, int /*x*/, int /*y*/)
+{
+ switch(key) {
+ case 27:
+ exit(0);
+ }
+}
+
+bool bnstate[8];
+int prev_x, prev_y;
+
+static void mouse(int bn, int st, int x, int y)
+{
+ bnstate[bn] = st == GLUT_DOWN;
+ prev_x = x;
+ prev_y = y;
+}
+
+static void motion(int x, int y)
+{
+ int dx = x - prev_x;
+ int dy = y - prev_y;
+ prev_x = x;
+ prev_y = y;
+
+ if(!dx && !dy) return;
+
+ if(bnstate[0]) {
+ cam_theta += dx * 0.5;
+ cam_phi += dy * 0.5;
+
+ if(cam_phi < -90) cam_phi = -90;
+ if(cam_phi > 90) cam_phi = 90;
+ glutPostRedisplay();
+ }
+ if(bnstate[2]) {
+ cam_dist += dy * 0.1;
+ if(cam_dist < 0) cam_dist = 0;
+ glutPostRedisplay();
+ }
+}
--- /dev/null
+#include <GL/glew.h>
+
+#include <assimp/cimport.h>
+#include <assimp/postprocess.h>
+#include <assimp/scene.h>
+#include <assimp/mesh.h>
+
+#include <float.h>
+
+#include "mesh.h"
+
+Mesh::Mesh()
+{
+ vbo_vertices = 0;
+ vbo_normals = 0;
+ vbo_colors = 0;
+ ibo = 0;
+
+ num_vertices = 0;
+ num_indices = 0;
+}
+
+Mesh::~Mesh()
+{
+ if(vbo_vertices)
+ glDeleteBuffers(1, &vbo_vertices);
+ if(vbo_normals)
+ glDeleteBuffers(1, &vbo_normals);
+ if(vbo_colors)
+ glDeleteBuffers(1, &vbo_colors);
+ if(ibo)
+ glDeleteBuffers(1, &ibo);
+
+ vertices.clear();
+ normals.clear();
+ colors.clear();
+}
+
+void Mesh::draw() const
+{
+ glBindBuffer(GL_ARRAY_BUFFER, vbo_vertices);
+ glVertexPointer(3, GL_FLOAT, 0, 0);
+
+ if(vbo_normals) {
+ glBindBuffer(GL_ARRAY_BUFFER, vbo_normals);
+ glNormalPointer(GL_FLOAT, 0, 0);
+ glEnableClientState(GL_NORMAL_ARRAY);
+ }
+
+ if(vbo_colors) {
+ glBindBuffer(GL_ARRAY_BUFFER, vbo_colors);
+ glColorPointer(3, GL_FLOAT, 0, 0);
+ glEnableClientState(GL_COLOR_ARRAY);
+ }
+
+ glBindBuffer(GL_ARRAY_BUFFER, 0);
+
+ glEnableClientState(GL_VERTEX_ARRAY);
+
+ if(ibo) {
+ glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, ibo);
+ glDrawElements(GL_TRIANGLES, indices.size(), GL_UNSIGNED_SHORT, 0);
+ glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, 0);
+ } else {
+ glDrawArrays(GL_TRIANGLES, 0, num_vertices);
+ }
+
+ glDisableClientState(GL_VERTEX_ARRAY);
+ glDisableClientState(GL_NORMAL_ARRAY);
+ glDisableClientState(GL_COLOR_ARRAY);
+}
+
+void Mesh::update_vbo(unsigned int which)
+{
+ if(which & MESH_NORMAL) {
+ if(!vbo_normals) {
+ glGenBuffers(1, &vbo_normals);
+ }
+ glBindBuffer(GL_ARRAY_BUFFER, vbo_normals);
+ if(num_vertices != (int)normals.size()) {
+ glBufferData(GL_ARRAY_BUFFER, normals.size() * 3 * sizeof(float),
+ &normals[0], GL_STATIC_DRAW);
+ }
+ else {
+ glBufferSubData(GL_ARRAY_BUFFER, 0, normals.size() * 3 * sizeof(float),
+ &normals[0]);
+ }
+ }
+
+ if(which & MESH_COLOR) {
+ if(!vbo_colors) {
+ glGenBuffers(1, &vbo_colors);
+ }
+ glBindBuffer(GL_ARRAY_BUFFER, vbo_colors);
+ if(num_vertices != (int)colors.size()) {
+ glBufferData(GL_ARRAY_BUFFER, colors.size() * 3 * sizeof(float),
+ &colors[0], GL_STATIC_DRAW);
+ }
+ else {
+ glBufferSubData(GL_ARRAY_BUFFER, 0, colors.size() * 3 * sizeof(float),
+ &colors[0]);
+ }
+ }
+
+
+ if(which & MESH_VERTEX) {
+ if(!vbo_vertices) {
+ glGenBuffers(1, &vbo_vertices);
+ }
+ glBindBuffer(GL_ARRAY_BUFFER, vbo_vertices);
+ if(num_vertices != (int)vertices.size()) {
+ glBufferData(GL_ARRAY_BUFFER, vertices.size() * 3 * sizeof(float),
+ &vertices[0], GL_STATIC_DRAW);
+ }
+ else {
+ glBufferSubData(GL_ARRAY_BUFFER, 0, vertices.size() * 3 * sizeof(float),
+ &vertices[0]);
+ }
+ num_vertices = vertices.size();
+ }
+
+ if(which & MESH_INDEX) {
+ if(!ibo) {
+ glGenBuffers(1, &ibo);
+ }
+ glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, ibo);
+ if(num_indices != (int)indices.size()) {
+ glBufferData(GL_ELEMENT_ARRAY_BUFFER, indices.size() * 2,
+ &indices[0], GL_STATIC_DRAW);
+ }
+ else {
+ glBufferSubData(GL_ELEMENT_ARRAY_BUFFER, 0, indices.size() * 2,
+ &indices[0]);
+ }
+ num_indices = indices.size();
+ }
+}
+
+std::vector<Mesh*> load_meshes(const char *fname)
+{
+ std::vector<Mesh*> meshes;
+ unsigned int ai_flags = aiProcessPreset_TargetRealtime_Quality;
+ const aiScene *scene = aiImportFile(fname, ai_flags);
+
+ for(unsigned int j=0; j<scene->mNumMeshes; j++) {
+ aiMesh *amesh = scene->mMeshes[j];
+
+ if(!amesh->HasPositions() || !amesh->mNumFaces)
+ continue;
+
+ Mesh *mesh = new Mesh;
+ mesh->name = std::string(amesh->mName.C_Str());
+
+ for(unsigned int i=0; i<amesh->mNumVertices; i++) {
+ Vec3 vertex = Vec3(amesh->mVertices[i].x,
+ amesh->mVertices[i].y,
+ amesh->mVertices[i].z);
+ mesh->vertices.push_back(vertex);
+ }
+
+ if(amesh->HasNormals()) {
+ for(unsigned int i=0; i<amesh->mNumVertices; i++) {
+ Vec3 normal = Vec3(amesh->mNormals[i].x,
+ amesh->mNormals[i].y,
+ amesh->mNormals[i].z);
+ mesh->normals.push_back(normal);
+ }
+ }
+
+ if(amesh->HasVertexColors(0)) {
+ for(unsigned int i=0; i<amesh->mNumVertices; i++) {
+ Vec3 color = Vec3(amesh->mColors[0][i].r,
+ amesh->mColors[0][i].g,
+ amesh->mColors[0][i].b);
+ mesh->colors.push_back(color);
+ }
+ }
+
+ for(unsigned int i=0; i<amesh->mNumFaces; i++) {
+ for(int j=0; j<3; j++) {
+ mesh->indices.push_back(amesh->mFaces[i].mIndices[j]);
+ }
+ }
+
+ meshes.push_back(mesh);
+ }
+
+ return meshes;
+}
+
+void Mesh::calc_bbox()
+{
+ if (vertices.empty()) {
+ bbox.v0 = Vec3(0, 0, 0);
+ bbox.v1 = Vec3(0, 0, 0);
+
+ return;
+ }
+
+ bbox.v0 = Vec3(FLT_MAX, FLT_MAX, FLT_MAX);
+ bbox.v1 = -bbox.v0;
+
+ for(size_t i=0; i<vertices.size(); i++) {
+ for(int j=0; j<3; j++) {
+ if(vertices[i][j] < bbox.v0[j])
+ bbox.v0[j] = vertices[i][j];
+ if(vertices[i][j] > bbox.v1[j])
+ bbox.v1[j] = vertices[i][j];
+ }
+ }
+}
--- /dev/null
+#ifndef MESH_H_
+#define MESH_H_
+
+#include <stdint.h>
+#include <vector>
+#include <gmath/gmath.h>
+
+#define MESH_ALL (0xffffffff)
+
+enum {
+ MESH_VERTEX = 1,
+ MESH_NORMAL = 2,
+ MESH_COLOR = 4,
+ MESH_INDEX = 8
+};
+
+struct Aabb {
+ Vec3 v0;
+ Vec3 v1;
+};
+
+class Mesh {
+private:
+ unsigned int vbo_vertices;
+ unsigned int vbo_normals;
+ unsigned int vbo_colors;
+ unsigned int ibo;
+
+ int num_vertices;
+ int num_indices;
+
+public:
+ Mesh();
+ ~Mesh();
+
+ Aabb bbox;
+
+ std::string name;
+ std::vector<uint16_t> indices;
+ std::vector<Vec3> vertices;
+ std::vector<Vec3> normals;
+ std::vector<Vec3> colors;
+
+ void draw() const;
+ void update_vbo(unsigned int which);
+
+ void calc_bbox();
+};
+
+std::vector<Mesh*> load_meshes(const char *fname);
+
+#endif // MESH_H_
projects / hair / commitdiff