Revision: 16857
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=16857
Author: broken
Date: 2008-10-01 05:35:53 +0200 (Wed, 01 Oct 2008)
Log Message:
-----------
* 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
Modified Paths:
--------------
branches/sim_physics/source/blender/blenkernel/intern/texture.c
branches/sim_physics/source/blender/blenlib/BLI_kdopbvh.h
branches/sim_physics/source/blender/blenlib/intern/BLI_kdopbvh.c
branches/sim_physics/source/blender/makesdna/DNA_texture_types.h
branches/sim_physics/source/blender/render/intern/source/pointdensity.c
branches/sim_physics/source/blender/src/buttons_shading.c
Modified: branches/sim_physics/source/blender/blenkernel/intern/texture.c
===================================================================
--- branches/sim_physics/source/blender/blenkernel/intern/texture.c
2008-10-01 00:14:28 UTC (rev 16856)
+++ branches/sim_physics/source/blender/blenkernel/intern/texture.c
2008-10-01 03:35:53 UTC (rev 16857)
@@ -43,7 +43,7 @@
#include "BLI_blenlib.h"
#include "BLI_arithb.h"
#include "BLI_rand.h"
-#include "BLI_kdtree.h"
+#include "BLI_kdopbvh.h"
#include "DNA_texture_types.h"
#include "DNA_key_types.h"
@@ -474,7 +474,7 @@
if (tex->pd) {
tex->pd->radius = 0.3f;
- tex->pd->nearest = 5;
+ tex->pd->falloff_type = TEX_PD_FALLOFF_STD;
}
pit = tex->plugin;
@@ -874,9 +874,10 @@
pd= MEM_callocN(sizeof(PointDensity), "pointdensity");
pd->radius = 0.3f;
- pd->nearest = 5;
+ pd->falloff_type = TEX_PD_FALLOFF_STD;
pd->source = TEX_PD_PSYS;
pd->point_tree = NULL;
+ //pd->point_data = NULL;
return pd;
}
@@ -887,6 +888,7 @@
pdn= MEM_dupallocN(pd);
pdn->point_tree = NULL;
+ //pdn->point_data = NULL;
return pd;
}
@@ -894,9 +896,15 @@
void BKE_free_pointdensitydata(PointDensity *pd)
{
if (pd->point_tree) {
- BLI_kdtree_free(pd->point_tree);
+ BLI_bvhtree_free(pd->point_tree);
pd->point_tree = NULL;
}
+ /*
+ if (pd->point_data) {
+ MEM_freeN(pd->point_data);
+ pd->point_data = NULL;
+ }
+ */
}
void BKE_free_pointdensity(PointDensity *pd)
Modified: branches/sim_physics/source/blender/blenlib/BLI_kdopbvh.h
===================================================================
--- branches/sim_physics/source/blender/blenlib/BLI_kdopbvh.h 2008-10-01
00:14:28 UTC (rev 16856)
+++ branches/sim_physics/source/blender/blenlib/BLI_kdopbvh.h 2008-10-01
03:35:53 UTC (rev 16857)
@@ -71,7 +71,10 @@
/* callback must update hit in case it finds a nearest successful hit */
typedef void (*BVHTree_RayCastCallback) (void *userdata, int index, const
BVHTreeRay *ray, BVHTreeRayHit *hit);
+/* callback to range search query */
+typedef void (*BVHTree_RangeQuery) (void *userdata, int index, float
squared_dist, float radius);
+
BVHTree *BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char
axis);
void BLI_bvhtree_free(BVHTree *tree);
@@ -93,5 +96,9 @@
int BLI_bvhtree_ray_cast(BVHTree *tree, const float *co, const float *dir,
float radius, BVHTreeRayHit *hit, BVHTree_RayCastCallback callback, void
*userdata);
+/* range query */
+int BLI_bvhtree_range_query(BVHTree *tree, const float *co, float radius,
BVHTree_RangeQuery callback, void *userdata);
+
+
#endif // BLI_KDOPBVH_H
Modified: branches/sim_physics/source/blender/blenlib/intern/BLI_kdopbvh.c
===================================================================
--- branches/sim_physics/source/blender/blenlib/intern/BLI_kdopbvh.c
2008-10-01 00:14:28 UTC (rev 16856)
+++ branches/sim_physics/source/blender/blenlib/intern/BLI_kdopbvh.c
2008-10-01 03:35:53 UTC (rev 16857)
@@ -1171,7 +1171,7 @@
}
//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 @@
//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 @@
}
}
*/
- return squared_dist(data->co, nearest);
+ return squared_dist(proj, nearest);
}
@@ -1229,7 +1229,7 @@
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 @@
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 @@
{
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_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 @@
}
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 @@
}
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 @@
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;
+}
Modified: branches/sim_physics/source/blender/makesdna/DNA_texture_types.h
===================================================================
--- branches/sim_physics/source/blender/makesdna/DNA_texture_types.h
2008-10-01 00:14:28 UTC (rev 16856)
+++ branches/sim_physics/source/blender/makesdna/DNA_texture_types.h
2008-10-01 03:35:53 UTC (rev 16857)
@@ -130,7 +130,7 @@
typedef struct PointDensity {
short flag;
- short nearest;
+ short falloff_type;
float radius;
short source;
@@ -144,7 +144,10 @@
short pdpad2;
- void *point_tree; /* the kd-tree containing points */
+ void *point_tree; /* the acceleration tree containing
points */
+ //void *point_data; /* dynamically allocated extra for
extra information, like particle age */
+ //int pdpad3;
+
} PointDensity;
typedef struct Tex {
@@ -415,10 +418,16 @@
#define TEX_PD_OBJECT 1
#define TEX_PD_FILE 2
+/* falloff_type */
+#define TEX_PD_FALLOFF_STD 0
+#define TEX_PD_FALLOFF_SMOOTH 1
+#define TEX_PD_FALLOFF_SHARP 2
+
/* psys_cache_space */
#define TEX_PD_OBJECTLOC 0
#define TEX_PD_OBJECTSPACE 1
#define TEX_PD_WORLDSPACE 2
+
#endif
Modified:
branches/sim_physics/source/blender/render/intern/source/pointdensity.c
===================================================================
--- branches/sim_physics/source/blender/render/intern/source/pointdensity.c
2008-10-01 00:14:28 UTC (rev 16856)
+++ branches/sim_physics/source/blender/render/intern/source/pointdensity.c
2008-10-01 03:35:53 UTC (rev 16857)
@@ -27,7 +27,7 @@
#include <stdio.h>
#include "BLI_arithb.h"
-#include "BLI_kdtree.h"
+#include "BLI_kdopbvh.h"
#include "BKE_DerivedMesh.h"
#include "BKE_global.h"
@@ -71,7 +71,7 @@
/* in case ob->imat isn't up-to-date */
Mat4Invert(ob->imat, ob->obmat);
- pd->point_tree = BLI_kdtree_new(psys->totpart+psys->totchild);
+ pd->point_tree = BLI_bvhtree_new(psys->totpart+psys->totchild, 0.0, 2,
6);
if (psys->totchild > 0 && !(psys->part->draw & PART_DRAW_PARENT))
childexists = 1;
@@ -93,11 +93,12 @@
/* TEX_PD_WORLDSPACE */
}
- BLI_kdtree_insert(pd->point_tree, i, partco, NULL);
+ BLI_bvhtree_insert(pd->point_tree, i, partco, 1);
}
}
- BLI_kdtree_balance(pd->point_tree);
+ BLI_bvhtree_balance(pd->point_tree);
+
psys_render_restore(ob, psys);
}
@@ -112,7 +113,7 @@
/* in case ob->imat isn't up-to-date */
Mat4Invert(obr->ob->imat, obr->ob->obmat);
- pd->point_tree = BLI_kdtree_new(obr->totvert);
+ pd->point_tree = BLI_bvhtree_new(obr->totvert, 0.0, 2, 6);
for(i=0; i<obr->totvert; i++) {
float ver_co[3];
@@ -128,10 +129,10 @@
Mat4MulVecfl(re->viewinv, ver_co);
}
- BLI_kdtree_insert(pd->point_tree, i, ver_co, NULL);
+ BLI_bvhtree_insert(pd->point_tree, i, ver_co, 1);
}
- BLI_kdtree_balance(pd->point_tree);
+ BLI_bvhtree_balance(pd->point_tree);
}
static void cache_pointdensity(Render *re, Tex *tex)
@@ -139,7 +140,7 @@
PointDensity *pd = tex->pd;
if (pd->point_tree) {
- BLI_kdtree_free(pd->point_tree);
+ BLI_bvhtree_free(pd->point_tree);
pd->point_tree = NULL;
}
@@ -178,9 +179,16 @@
@@ Diff output truncated at 10240 characters. @@
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
http://lists.blender.org/mailman/listinfo/bf-blender-cvs
