[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [14822] branches/cloth/blender/source/ blender/blenlib: New speed imrovements by Mr.
Daniel Genrich
daniel.genrich at gmx.net
Tue May 13 02:42:51 CEST 2008
Revision: 14822
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=14822
Author: genscher
Date: 2008-05-13 02:42:51 +0200 (Tue, 13 May 2008)
Log Message:
-----------
New speed imrovements by Mr. Pinto/jaguarandi
Modified Paths:
--------------
branches/cloth/blender/source/blender/blenlib/BLI_kdopbvh.h
branches/cloth/blender/source/blender/blenlib/intern/BLI_kdopbvh.c
Modified: branches/cloth/blender/source/blender/blenlib/BLI_kdopbvh.h
===================================================================
--- branches/cloth/blender/source/blender/blenlib/BLI_kdopbvh.h 2008-05-12 21:41:00 UTC (rev 14821)
+++ branches/cloth/blender/source/blender/blenlib/BLI_kdopbvh.h 2008-05-13 00:42:51 UTC (rev 14822)
@@ -21,7 +21,7 @@
*
* The Original Code is: all of this file.
*
- * Contributor(s): Daniel Genrich, Jose Pinto
+ * Contributor(s): Daniel Genrich, Andre Pinto
*
* ***** END GPL LICENSE BLOCK *****
*/
Modified: branches/cloth/blender/source/blender/blenlib/intern/BLI_kdopbvh.c
===================================================================
--- branches/cloth/blender/source/blender/blenlib/intern/BLI_kdopbvh.c 2008-05-12 21:41:00 UTC (rev 14821)
+++ branches/cloth/blender/source/blender/blenlib/intern/BLI_kdopbvh.c 2008-05-13 00:42:51 UTC (rev 14822)
@@ -25,7 +25,7 @@
*
* The Original Code is: all of this file.
*
-* Contributor(s): Daniel Genrich, Jose Pinto
+* Contributor(s): Daniel Genrich, Andre Pinto
*
* ***** END GPL/BL DUAL LICENSE BLOCK *****
*/
@@ -40,6 +40,7 @@
#include "BKE_utildefines.h"
#include "BLI_kdopbvh.h"
+#include "BLI_arithb.h"
#ifdef _OPENMP
#include <omp.h>
@@ -101,12 +102,6 @@
/*
* Common methods for all algorithms
*/
-static void bvh_exchange(BVHNode **a, int i, int j)
-{
- BVHNode *t=a[i];
- a[i]=a[j];
- a[j]=t;
-}
static int floor_lg(int a)
{
return (int)(floor(log(a)/log(2)));
@@ -138,11 +133,11 @@
while (1)
{
while ((a[i])->bv[axis] < x->bv[axis]) i++;
- j=j-1;
- while (x->bv[axis] < (a[j])->bv[axis]) j=j-1;
+ j--;
+ while (x->bv[axis] < (a[j])->bv[axis]) j--;
if(!(i < j))
return i;
- bvh_exchange(a, i,j);
+ SWAP( BVHNode* , a[i], a[j]);
i++;
}
}
@@ -177,7 +172,7 @@
}
for (i=n; i>1; i=i-1)
{
- bvh_exchange(a, lo,lo+i-1);
+ SWAP(BVHNode*, a[lo],a[lo+i-1]);
bvh_downheap(a, 1,i-1,lo, axis);
}
}
@@ -244,6 +239,25 @@
sort(tree->nodes, start, end, axis);
}
+//after a call to this function you can expect one of:
+// every node to left of a[n] are smaller than it
+// every node to the right of a[n-1] are greater than it
+void partition_nth_element(BVHNode **a, int _begin, int _end, int n, int axis)
+{
+ int begin = _begin, end = _end;
+ while(begin < n && end >= n)
+ {
+ int mid = bvh_partition(a, begin, end, bvh_medianof3(a, begin, (begin+end-1)/2, end-1, axis), axis );
+
+ if(mid >= n)
+ end = n-1;
+ else
+ begin = n+1;
+ }
+
+}
+
+
//////////////////////////////////////////////////////////////////////////////////////////////////////
void BLI_bvhtree_free(BVHTree *tree)
@@ -359,10 +373,11 @@
}
// depends on the fact that the BVH's for each face is already build
-static void refit_kdop_hull(BVHTree *tree, int start, int end, float *bv)
+static void refit_kdop_hull(BVHTree *tree, BVHNode *node, int start, int end)
{
float newmin,newmax;
int i, j;
+ float *bv = node->bv;
for (i = tree->start_axis; i < tree->stop_axis; i++)
{
@@ -451,16 +466,14 @@
// Determine which axis to split along
laxis = get_largest_axis(node->bv);
-
- // Sort along longest axis
- if(laxis!=lastaxis)
- sort_along_axis(tree, start, end, laxis);
// split nodes along longest axis
for (i=0; start < end; start += slice, i++) //i counts the current child
{
tend = start + slice;
+ partition_nth_element(tree->nodes, start, end, tend, laxis);
+
if(tend > end) tend = end;
if(tend-start == 1) // ok, we have 1 left for this node
@@ -474,7 +487,7 @@
tree->totbranch++;
tnode->parent = node;
- refit_kdop_hull(tree, start, tend, tnode->bv);
+ partition_nth_element(tree->nodes, start, end, tend, laxis);
bvh_div_nodes(tree, tnode, start, tend, laxis);
}
node->totnode++;
@@ -533,7 +546,6 @@
void BLI_bvhtree_balance(BVHTree *tree)
{
BVHNode *node;
- int i;
if(tree->totleaf == 0)
return;
@@ -543,11 +555,11 @@
tree->totbranch++;
// refit root bvh node
- refit_kdop_hull(tree, 0, tree->totleaf, tree->nodes[tree->totleaf]->bv);
+ refit_kdop_hull(tree, tree->nodes[tree->totleaf], 0, tree->totleaf);
// create + balance tree
bvh_div_nodes(tree, tree->nodes[tree->totleaf], 0, tree->totleaf, 0);
- verify_tree(tree);
+ // verify_tree(tree);
}
// overlap - is it possbile for 2 bv's to collide ?
More information about the Bf-blender-cvs
mailing list