[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [48776] trunk/blender: updating raskter to support tiles compositor.
Peter Larabell
xgl.asyliax at gmail.com
Tue Jul 10 00:57:23 CEST 2012
Revision: 48776
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=48776
Author: xglasyliax
Date: 2012-07-09 22:57:23 +0000 (Mon, 09 Jul 2012)
Log Message:
-----------
updating raskter to support tiles compositor. this commit puts in some groundwork code to support tiles's pixel processor
Modified Paths:
--------------
trunk/blender/intern/raskter/CMakeLists.txt
trunk/blender/intern/raskter/raskter.c
trunk/blender/intern/raskter/raskter.h
trunk/blender/source/blender/blenkernel/intern/mask.c
Added Paths:
-----------
trunk/blender/intern/raskter/kdtree.c
trunk/blender/intern/raskter/kdtree.h
trunk/blender/intern/raskter/raskter_mt.c
Modified: trunk/blender/intern/raskter/CMakeLists.txt
===================================================================
--- trunk/blender/intern/raskter/CMakeLists.txt 2012-07-09 22:41:44 UTC (rev 48775)
+++ trunk/blender/intern/raskter/CMakeLists.txt 2012-07-09 22:57:23 UTC (rev 48776)
@@ -33,8 +33,11 @@
set(SRC
raskter.c
+ raskter_mt.c
+ kdtree.c
raskter.h
+ kdtree.h
)
blender_add_lib(bf_intern_raskter "${SRC}" "${INC}" "${INC_SYS}")
Added: trunk/blender/intern/raskter/kdtree.c
===================================================================
--- trunk/blender/intern/raskter/kdtree.c (rev 0)
+++ trunk/blender/intern/raskter/kdtree.c 2012-07-09 22:57:23 UTC (rev 48776)
@@ -0,0 +1,836 @@
+/*
+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 */
+ dummy = *farther_hyperrect_coord;
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list