diff options
author | Matt Ebb <matt@mke3.net> | 2008-10-01 07:35:53 +0400 |
---|---|---|
committer | Matt Ebb <matt@mke3.net> | 2008-10-01 07:35:53 +0400 |
commit | 8622cbca359d77eb980250b42d0635c0dddfa48b (patch) | |
tree | 8519ed851af8a1a9295405be456a36f5c81e16f8 /source/blender/blenlib/intern/BLI_kdopbvh.c | |
parent | 3c99a0f73539e5a3c8ceeb02e6c5a21ed4985f71 (diff) |
* Point Density texture
Replaced the previous KD-tree (for caching points) with a
BVH-tree (thanks to Andre 'jaguarandi' Pinto for help here!).
The bvh is quite a bit faster and doesn't suffer some of the
artifacts that were apparent with the kd-tree.
I've also added a choice of falloff types: Standard, Smooth, and
Sharp. Standard gives a harder edge, easier to see individual
particles, and when used with a larger radius, Smooth and Sharp
falloffs make a much cloudier appearance possible. See the image
below (note the settings and render times too)
http://mke3.net/blender/devel/rendering/volumetrics/pointdensity_bvh.jpg
Diffstat (limited to 'source/blender/blenlib/intern/BLI_kdopbvh.c')
-rw-r--r-- | source/blender/blenlib/intern/BLI_kdopbvh.c | 109 |
1 files changed, 98 insertions, 11 deletions
diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c index 30472beb3e6..f82b6b7f162 100644 --- a/source/blender/blenlib/intern/BLI_kdopbvh.c +++ b/source/blender/blenlib/intern/BLI_kdopbvh.c @@ -1171,7 +1171,7 @@ static float squared_dist(const float *a, const float *b) } //Determines the nearest point of the given node BV. Returns the squared distance to that point. -static float calc_nearest_point(BVHNearestData *data, BVHNode *node, float *nearest) +static float calc_nearest_point(const float *proj, BVHNode *node, float *nearest) { int i; const float *bv = node->bv; @@ -1179,12 +1179,12 @@ static float calc_nearest_point(BVHNearestData *data, BVHNode *node, float *near //nearest on AABB hull for(i=0; i != 3; i++, bv += 2) { - if(bv[0] > data->proj[i]) + if(bv[0] > proj[i]) nearest[i] = bv[0]; - else if(bv[1] < data->proj[i]) + else if(bv[1] < proj[i]) nearest[i] = bv[1]; else - nearest[i] = data->proj[i]; + nearest[i] = proj[i]; } /* @@ -1206,7 +1206,7 @@ static float calc_nearest_point(BVHNearestData *data, BVHNode *node, float *near } } */ - return squared_dist(data->co, nearest); + return squared_dist(proj, nearest); } @@ -1229,7 +1229,7 @@ static void dfs_find_nearest_dfs(BVHNearestData *data, BVHNode *node) else { data->nearest.index = node->index; - data->nearest.dist = calc_nearest_point(data, node, data->nearest.co); + data->nearest.dist = calc_nearest_point(data->proj, node, data->nearest.co); } } else @@ -1243,7 +1243,7 @@ static void dfs_find_nearest_dfs(BVHNearestData *data, BVHNode *node) for(i=0; i != node->totnode; i++) { - if( calc_nearest_point(data, node->children[i], nearest) >= data->nearest.dist) continue; + if( calc_nearest_point(data->proj, node->children[i], nearest) >= data->nearest.dist) continue; dfs_find_nearest_dfs(data, node->children[i]); } } @@ -1251,7 +1251,7 @@ static void dfs_find_nearest_dfs(BVHNearestData *data, BVHNode *node) { for(i=node->totnode-1; i >= 0 ; i--) { - if( calc_nearest_point(data, node->children[i], nearest) >= data->nearest.dist) continue; + if( calc_nearest_point(data->proj, node->children[i], nearest) >= data->nearest.dist) continue; dfs_find_nearest_dfs(data, node->children[i]); } } @@ -1261,7 +1261,7 @@ static void dfs_find_nearest_dfs(BVHNearestData *data, BVHNode *node) static void dfs_find_nearest_begin(BVHNearestData *data, BVHNode *node) { float nearest[3], sdist; - sdist = calc_nearest_point(data, node, nearest); + sdist = calc_nearest_point(data->proj, node, nearest); if(sdist >= data->nearest.dist) return; dfs_find_nearest_dfs(data, node); } @@ -1298,7 +1298,7 @@ static void bfs_find_nearest(BVHNearestData *data, BVHNode *node) } current.node = node; - current.dist = calc_nearest_point(data, node, nearest); + current.dist = calc_nearest_point(data->proj, node, nearest); while(current.dist < data->nearest.dist) { @@ -1326,7 +1326,7 @@ static void bfs_find_nearest(BVHNearestData *data, BVHNode *node) } heap[heap_size].node = current.node->children[i]; - heap[heap_size].dist = calc_nearest_point(data, current.node->children[i], nearest); + heap[heap_size].dist = calc_nearest_point(data->proj, current.node->children[i], nearest); if(heap[heap_size].dist >= data->nearest.dist) continue; heap_size++; @@ -1524,3 +1524,90 @@ int BLI_bvhtree_ray_cast(BVHTree *tree, const float *co, const float *dir, float return data.hit.index; } +/* + * Range Query - as request by broken :P + * + * Allocs and fills an array with the indexs of node that are on the given spherical range (center, radius) + * Returns the size of the array. + */ +typedef struct RangeQueryData +{ + BVHTree *tree; + const float *center; + float radius; //squared radius + + int hits; + + BVHTree_RangeQuery callback; + void *userdata; + + +} RangeQueryData; + + +static void dfs_range_query(RangeQueryData *data, BVHNode *node) +{ + if(node->totnode == 0) + { + + //Calculate the node min-coords (if the node was a point then this is the point coordinates) + float co[3]; + co[0] = node->bv[0]; + co[1] = node->bv[2]; + co[2] = node->bv[4]; + + } + else + { + int i; + for(i=0; i != node->totnode; i++) + { + float nearest[3]; + float dist = calc_nearest_point(data->center, node->children[i], nearest); + if(dist < data->radius) + { + //Its a leaf.. call the callback + if(node->children[i]->totnode == 0) + { + data->hits++; + data->callback( data->userdata, node->children[i]->index, dist, data->radius ); + } + else + dfs_range_query( data, node->children[i] ); + } + } + } +} + +int BLI_bvhtree_range_query(BVHTree *tree, const float *co, float radius, BVHTree_RangeQuery callback, void *userdata) +{ + BVHNode * root = tree->nodes[tree->totleaf]; + + RangeQueryData data; + data.tree = tree; + data.center = co; + data.radius = radius*radius; + data.hits = 0; + + data.callback = callback; + data.userdata = userdata; + + if(root != NULL) + { + float nearest[3]; + float dist = calc_nearest_point(data.center, root, nearest); + if(dist < data.radius) + { + //Its a leaf.. call the callback + if(root->totnode == 0) + { + data.hits++; + data.callback( data.userdata, root->index, dist, data.radius ); + } + else + dfs_range_query( &data, root ); + } + } + + return data.hits; +} |