[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [48789] trunk/blender/intern/raskter: rename raskter kdtree files to be less generic
Campbell Barton
ideasman42 at gmail.com
Tue Jul 10 08:47:21 CEST 2012
Revision: 48789
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=48789
Author: campbellbarton
Date: 2012-07-10 06:47:21 +0000 (Tue, 10 Jul 2012)
Log Message:
-----------
rename raskter kdtree files to be less generic
Modified Paths:
--------------
trunk/blender/intern/raskter/CMakeLists.txt
Added Paths:
-----------
trunk/blender/intern/raskter/raskter_kdtree.c
trunk/blender/intern/raskter/raskter_kdtree.h
Removed Paths:
-------------
trunk/blender/intern/raskter/kdtree.c
trunk/blender/intern/raskter/kdtree.h
Modified: trunk/blender/intern/raskter/CMakeLists.txt
===================================================================
--- trunk/blender/intern/raskter/CMakeLists.txt 2012-07-10 06:31:16 UTC (rev 48788)
+++ trunk/blender/intern/raskter/CMakeLists.txt 2012-07-10 06:47:21 UTC (rev 48789)
@@ -34,10 +34,10 @@
set(SRC
raskter.c
raskter_mt.c
- kdtree.c
+ raskter_kdtree.c
raskter.h
- kdtree.h
+ raskter_kdtree.h
)
blender_add_lib(bf_intern_raskter "${SRC}" "${INC}" "${INC_SYS}")
Deleted: trunk/blender/intern/raskter/kdtree.c
===================================================================
--- trunk/blender/intern/raskter/kdtree.c 2012-07-10 06:31:16 UTC (rev 48788)
+++ trunk/blender/intern/raskter/kdtree.c 2012-07-10 06:47:21 UTC (rev 48789)
@@ -1,836 +0,0 @@
-/*
-This file is part of ``kdtree'', a library for working with kd-trees.
-Copyright (C) 2007-2011 John Tsiombikas <nuclear at 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 at cs.rhul.ac.uk> */
-#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 */
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list