From: Eleni Maria Stea Date: Wed, 14 Nov 2018 12:19:10 +0000 (+0200) Subject: Added head mesh, points/directions for hair that follow the Poisson X-Git-Url: http://git.mutantstargoat.com?p=hair;a=commitdiff_plain;h=da5cbacf755273da510c37c819a59c7fe9894c4e Added head mesh, points/directions for hair that follow the Poisson distribution, used a kd-tree to store them --- da5cbacf755273da510c37c819a59c7fe9894c4e diff --git a/Makefile b/Makefile new file mode 100755 index 0000000..517443a --- /dev/null +++ b/Makefile @@ -0,0 +1,28 @@ +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) diff --git a/data/head.fbx b/data/head.fbx new file mode 100644 index 0000000..c4dd1ff Binary files /dev/null and b/data/head.fbx differ diff --git a/src/hair.cc b/src/hair.cc new file mode 100644 index 0000000..e4843fb --- /dev/null +++ b/src/hair.cc @@ -0,0 +1,98 @@ +#include +#include +#include + +#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 *faces) +{ + for(size_t i=0; iindices.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 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 +{ +} diff --git a/src/hair.h b/src/hair.h new file mode 100644 index 0000000..19fa82e --- /dev/null +++ b/src/hair.h @@ -0,0 +1,22 @@ +#ifndef PARTICLES_H_ +#define PARTICLES_H_ + +#include + +#include "mesh.h" + +class Hair { +private: + std::vector spawn_points; + std::vector spawn_directions; + +public: + Hair(); + ~Hair(); + + bool init(const Mesh *m, int num_spawns, float thresh = 0.4); + void draw() const; +}; + +#endif //PARTICLES_H_ + diff --git a/src/kdtree.c b/src/kdtree.c new file mode 100644 index 0000000..2fdee28 --- /dev/null +++ b/src/kdtree.c @@ -0,0 +1,843 @@ +/* +This file is part of ``kdtree'', a library for working with kd-trees. +Copyright (C) 2007-2011 John Tsiombikas + +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 */ + +#ifdef HAVE_CONFIG_H +#include +#endif + +#include +#include +#include +#include +#include "kdtree.h" + +#if defined(WIN32) || defined(__WIN32__) +#include +#endif + +#ifdef USE_LIST_NODE_ALLOCATOR + +#ifndef NO_PTHREADS +#include +#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; ipos[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; ipos[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; itree->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; +} diff --git a/src/kdtree.h b/src/kdtree.h new file mode 100644 index 0000000..92d43e4 --- /dev/null +++ b/src/kdtree.h @@ -0,0 +1,129 @@ +/* +This file is part of ``kdtree'', a library for working with kd-trees. +Copyright (C) 2007-2011 John Tsiombikas + +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_ */ diff --git a/src/main.cc b/src/main.cc new file mode 100644 index 0000000..8b0fe13 --- /dev/null +++ b/src/main.cc @@ -0,0 +1,163 @@ +#include +#include + +#include +#include +#include +#include + +#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 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; icalc_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; idraw(); + } + + 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(); + } +} diff --git a/src/mesh.cc b/src/mesh.cc new file mode 100644 index 0000000..c852258 --- /dev/null +++ b/src/mesh.cc @@ -0,0 +1,211 @@ +#include + +#include +#include +#include +#include + +#include + +#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 load_meshes(const char *fname) +{ + std::vector meshes; + unsigned int ai_flags = aiProcessPreset_TargetRealtime_Quality; + const aiScene *scene = aiImportFile(fname, ai_flags); + + for(unsigned int j=0; jmNumMeshes; 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; imNumVertices; 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; imNumVertices; 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; imNumVertices; 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; imNumFaces; 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 bbox.v1[j]) + bbox.v1[j] = vertices[i][j]; + } + } +} diff --git a/src/mesh.h b/src/mesh.h new file mode 100644 index 0000000..7ca25c2 --- /dev/null +++ b/src/mesh.h @@ -0,0 +1,52 @@ +#ifndef MESH_H_ +#define MESH_H_ + +#include +#include +#include + +#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 indices; + std::vector vertices; + std::vector normals; + std::vector colors; + + void draw() const; + void update_vbo(unsigned int which); + + void calc_bbox(); +}; + +std::vector load_meshes(const char *fname); + +#endif // MESH_H_