[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [15572] branches/soc-2008-jaguarandi/ source/blender: Improved build time on BLI_kdopbvh
André Pinto
andresusanopinto at gmail.com
Mon Jul 14 20:42:54 CEST 2008
Revision: 15572
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=15572
Author: jaguarandi
Date: 2008-07-14 20:42:53 +0200 (Mon, 14 Jul 2008)
Log Message:
-----------
Improved build time on BLI_kdopbvh
Its now faster than raytree (both on build and query)
Things tryed:
X=>Y=>Z=>X split (reduces build time.. but increases query time)
bucket sorts
(initial sorts for fast usage of bucket take a long time)
(nth is linear.. so its quite fast already)
Best times archieve with:
*usage of 4-ary trees.. reduces build time and tree size but didnt decreased query time
*quads are on the same node instead of splitting in 2 tris..
(this actually turned on speedup on query time.. since tree size is reduced by a factor of 2)
*test ray-bb before ray-primitive gives better times on both tris and quads
Notes:
measures where made projecting a sphere from inside the head of suzanne.
Modified Paths:
--------------
branches/soc-2008-jaguarandi/source/blender/blenkernel/intern/shrinkwrap.c
branches/soc-2008-jaguarandi/source/blender/blenlib/intern/BLI_kdopbvh.c
Modified: branches/soc-2008-jaguarandi/source/blender/blenkernel/intern/shrinkwrap.c
===================================================================
--- branches/soc-2008-jaguarandi/source/blender/blenkernel/intern/shrinkwrap.c 2008-07-14 18:34:42 UTC (rev 15571)
+++ branches/soc-2008-jaguarandi/source/blender/blenkernel/intern/shrinkwrap.c 2008-07-14 18:42:53 UTC (rev 15572)
@@ -149,13 +149,13 @@
/*
* Builds a bvh tree.. where nodes are the vertexs of the given mesh
*/
-static BVHTree* bvhtree_from_mesh_verts(DerivedMesh *mesh, float epsilon)
+static BVHTree* bvhtree_from_mesh_verts(DerivedMesh *mesh, float epsilon, int tree_type, int axis)
{
int i;
int numVerts= mesh->getNumVerts(mesh);
MVert *vert = mesh->getVertDataArray(mesh, CD_MVERT);
- BVHTree *tree = BLI_bvhtree_new(numVerts, 0, 2, 6);
+ BVHTree *tree = BLI_bvhtree_new(numVerts, epsilon, tree_type, axis);
if(tree != NULL)
{
for(i = 0; i < numVerts; i++)
@@ -170,7 +170,7 @@
/*
* Builds a bvh tree.. where nodes are the faces of the given mesh. Quads are splitted in 2 triangles
*/
-static BVHTree* bvhtree_from_mesh_tri(DerivedMesh *mesh, float epsilon)
+static BVHTree* bvhtree_from_mesh_tri(DerivedMesh *mesh, float epsilon, int tree_type, int axis)
{
int i;
int numFaces= mesh->getNumFaces(mesh), totFaces;
@@ -183,7 +183,7 @@
if(face[i].v4) totFaces++;
/* Create a bvh-tree of the given target */
- tree = BLI_bvhtree_new(totFaces, epsilon, 2, 6);
+ tree = BLI_bvhtree_new(totFaces, epsilon, tree_type, axis);
if(tree != NULL)
{
for(i = 0; i < numFaces; i++)
@@ -210,6 +210,42 @@
}
/*
+ * Builds a bvh tree.. where nodes are the faces of the given mesh.
+ */
+static BVHTree* bvhtree_from_mesh_faces(DerivedMesh *mesh, float epsilon, int tree_type, int axis)
+{
+ int i;
+ int numFaces= mesh->getNumFaces(mesh);
+ MVert *vert = mesh->getVertDataArray(mesh, CD_MVERT);
+ MFace *face = mesh->getFaceDataArray(mesh, CD_MFACE);
+ BVHTree *tree= NULL;
+
+ /* Count needed faces */
+
+ /* Create a bvh-tree of the given target */
+ tree = BLI_bvhtree_new(numFaces, epsilon, tree_type, axis);
+ if(tree != NULL)
+ {
+ for(i = 0; i < numFaces; i++)
+ {
+ float co[4][3];
+
+ VECCOPY(co[0], vert[ face[i].v1 ].co);
+ VECCOPY(co[1], vert[ face[i].v2 ].co);
+ VECCOPY(co[2], vert[ face[i].v3 ].co);
+ if(face[i].v4)
+ VECCOPY(co[3], vert[ face[i].v4 ].co);
+
+ BLI_bvhtree_insert(tree, i, co[0], face[i].v4 ? 4 : 3);
+ }
+
+ BLI_bvhtree_balance(tree);
+ }
+
+ return tree;
+}
+
+/*
* Loads the coordinates of the requested tri
*/
static void bvhtree_from_mesh_get_tri(BVHMeshCallbackUserdata* userdata, int index, float **v0, float **v1, float **v2)
@@ -248,7 +284,11 @@
bvhtree_from_mesh_get_tri( (BVHMeshCallbackUserdata*)userdata, index, &t0, &t1, &t2);
- dist = sphereray_tri_intersection(ray, ((BVHMeshCallbackUserdata*)userdata)->sphere_radius, hit->dist, t0, t1, t2);
+ if(((BVHMeshCallbackUserdata*)userdata)->sphere_radius == 0.0f)
+ dist = ray_tri_intersection(ray, hit->dist, t0, t1, t2);
+ else
+ dist = sphereray_tri_intersection(ray, ((BVHMeshCallbackUserdata*)userdata)->sphere_radius, hit->dist, t0, t1, t2);
+
if(dist >= 0 && dist < hit->dist)
{
hit->index = index;
@@ -259,28 +299,46 @@
}
/*
- * Callback to bvh tree raycast. The tree must bust have been built using bvhtree_from_mesh_tri.
- * Rays are projected as a sphere with the radius configured on userdata.
+ * Callback to bvh tree raycast. The tree must bust have been built using bvhtree_from_mesh_faces.
* userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree.
*/
-static float mesh_tri_raycast(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
+static float mesh_faces_spherecast(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
{
- float dist;
- float *t0, *t1, *t2;
+ const BVHMeshCallbackUserdata *data = (BVHMeshCallbackUserdata*) userdata;
+ MVert *vert = data->vert;
+ MFace *face = data->face + index;
- bvhtree_from_mesh_get_tri( (BVHMeshCallbackUserdata*)userdata, index, &t0, &t1, &t2);
+ float *t0, *t1, *t2, *t3;
+ t0 = vert[ face->v1 ].co;
+ t1 = vert[ face->v2 ].co;
+ t2 = vert[ face->v3 ].co;
+ t3 = face->v4 ? vert[ face->v4].co : NULL;
+
- dist = ray_tri_intersection(ray, hit->dist, t0, t1, t2);
- if(dist >= 0 && dist < hit->dist)
- {
- hit->index = index;
- hit->dist = dist;
- VECADDFAC(hit->co, ray->origin, ray->direction, dist);
- }
- return dist;
+ do
+ {
+ float dist;
+ if(data->sphere_radius == 0.0f)
+ dist = ray_tri_intersection(ray, hit->dist, t0, t1, t2);
+ else
+ dist = sphereray_tri_intersection(ray, data->sphere_radius, hit->dist, t0, t1, t2);
+
+ if(dist >= 0 && dist < hit->dist)
+ {
+ hit->index = index;
+ hit->dist = dist;
+ VECADDFAC(hit->co, ray->origin, ray->direction, dist);
+ }
+
+ t1 = t2;
+ t2 = t3;
+ t3 = NULL;
+
+ } while(t2);
+
+ return hit->dist;
}
-
/*
* Raytree from mesh
*/
@@ -1145,11 +1203,11 @@
if(calc.smd->shrinkOpts & MOD_SHRINKWRAP_REMOVE_UNPROJECTED_FACES)
calc.moved = bitset_new( calc.final->getNumVerts(calc.final), "shrinkwrap bitset data");
-/*
- BENCH(shrinkwrap_calc_normal_projection_raytree(&calc));
- calc.final->release( calc.final );
-*/
+
+// BENCH(shrinkwrap_calc_normal_projection_raytree(&calc));
+// calc.final->release( calc.final );
// calc.final = CDDM_copy(calc.original);
+
BENCH(shrinkwrap_calc_normal_projection(&calc));
// BENCH(shrinkwrap_calc_foreach_vertex(&calc, bruteforce_shrinkwrap_calc_normal_projection));
@@ -1204,7 +1262,7 @@
BENCH_VAR(query);
- BENCH(tree = bvhtree_from_mesh_verts(calc->target, 0.0));
+ BENCH(tree = bvhtree_from_mesh_verts(calc->target, 0.0, 2, 6));
if(tree == NULL) return OUT_OF_MEMORY();
//Setup nearest
@@ -1366,10 +1424,10 @@
if( (use_normal & (MOD_SHRINKWRAP_ALLOW_INVERTED_NORMAL | MOD_SHRINKWRAP_ALLOW_DEFAULT_NORMAL)) == 0)
return; //Nothing todo
- BENCH(tree = bvhtree_from_mesh_tri(calc->target, calc->keptDist));
+ BENCH(tree = bvhtree_from_mesh_faces(calc->target, calc->keptDist, 4, 6));
if(tree == NULL) return OUT_OF_MEMORY();
bvhtree_meshcallbackdata_init(&userdata, calc->target, calc->keptDist);
- callback = calc->keptDist > 0 ? mesh_tri_spherecast : mesh_tri_raycast;
+ callback = mesh_faces_spherecast;
//Project each vertex along normal
numVerts= calc->final->getNumVerts(calc->final);
@@ -1473,7 +1531,7 @@
//Create a bvh-tree of the given target
- tree = bvhtree_from_mesh_tri(calc->target, 0.0);
+ tree = bvhtree_from_mesh_tri(calc->target, 0.0, 2, 6);
if(tree == NULL) return OUT_OF_MEMORY();
bvhtree_meshcallbackdata_init(&userdata, calc->target, 0.0);
Modified: branches/soc-2008-jaguarandi/source/blender/blenlib/intern/BLI_kdopbvh.c
===================================================================
--- branches/soc-2008-jaguarandi/source/blender/blenlib/intern/BLI_kdopbvh.c 2008-07-14 18:34:42 UTC (rev 15571)
+++ branches/soc-2008-jaguarandi/source/blender/blenlib/intern/BLI_kdopbvh.c 2008-07-14 18:42:53 UTC (rev 15572)
@@ -520,6 +520,8 @@
// Determine which axis to split along
laxis = get_largest_axis(node->bv);
+ //laxis = (lastaxis + 2) % tree->axis; // XYZ split
+
node->main_axis = laxis/2;
// split nodes along longest axis
@@ -543,7 +545,7 @@
if(tend != end)
partition_nth_element(tree->nodes, start, end, tend, laxis);
refit_kdop_hull(tree, tnode, start, tend);
- bvh_div_nodes(tree, tnode, start, tend, laxis);
+ bvh_div_nodes(tree, tnode, start, tend, laxis); // not called on XYZ split
}
node->totnode++;
}
@@ -613,9 +615,10 @@
tree->totbranch++;
// refit root bvh node
- refit_kdop_hull(tree, tree->nodes[tree->totleaf], 0, tree->totleaf);
+ refit_kdop_hull(tree, tree->nodes[tree->totleaf], 0, tree->totleaf); // not called on XYZ split
// create + balance tree
bvh_div_nodes(tree, tree->nodes[tree->totleaf], 0, tree->totleaf, 0);
+ //BLI_bvhtree_update_tree(tree); // XYZ split
// verify_tree(tree);
}
@@ -1009,16 +1012,16 @@
static void dfs_raycast(BVHRayCastData *data, BVHNode *node)
{
int i;
- float dist;
- dist = ray_nearest_hit(data, node);
-
+ //ray-bv is really fast.. and simple tests revealed its worth to test it
+ //before calling the ray-primitive functions
+ float dist = ray_nearest_hit(data, node);
if(dist >= data->hit.dist) return;
if(node->totnode == 0)
{
if(data->callback)
- dist = data->callback(data->userdata, node->index, &data->ray, &data->hit);
+ data->callback(data->userdata, node->index, &data->ray, &data->hit);
else
{
data->hit.index = node->index;
More information about the Bf-blender-cvs
mailing list