[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [14843] branches/soc-2008-jaguarandi/ source/blender: I' m considering using bvhtree for shrinkwrap but the build was considerable slower than kdtree
André Pinto
andresusanopinto at gmail.com
Wed May 14 20:25:24 CEST 2008
Revision: 14843
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=14843
Author: jaguarandi
Date: 2008-05-14 20:25:23 +0200 (Wed, 14 May 2008)
Log Message:
-----------
I'm considering using bvhtree for shrinkwrap but the build was considerable slower than kdtree
as so i've made some improvements
So basicly theres no shrinkwrap improvements for now...
Modified Paths:
--------------
branches/soc-2008-jaguarandi/source/blender/blenkernel/intern/shrinkwrap.c
Added Paths:
-----------
branches/soc-2008-jaguarandi/source/blender/blenlib/BLI_kdopbvh.h
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-05-14 16:59:17 UTC (rev 14842)
+++ branches/soc-2008-jaguarandi/source/blender/blenkernel/intern/shrinkwrap.c 2008-05-14 18:25:23 UTC (rev 14843)
@@ -47,6 +47,7 @@
#include "BLI_arithb.h"
#include "BLI_kdtree.h"
+#include "BLI_kdopbvh.h"
#include "RE_raytrace.h"
#include "MEM_guardedalloc.h"
@@ -785,29 +786,45 @@
KDTreeNearest nearest;
float tmp_co[3];
+ BVHTree *tree = NULL;
+
BENCH_VAR(build);
BENCH_VAR(query);
int numVerts;
- MVert *vert = NULL;
+ MVert *vert = NULL, *tvert = NULL;
MDeformVert *dvert = NULL;
+ numVerts= calc->target->getNumVerts(calc->target);
+ vert = tvert = calc->target->getVertDataArray(calc->target, CD_MVERT);
+
+ BENCH_RESET(build);
+ BENCH_BEGIN(build);
+
+ tree = BLI_bvhtree_new(numVerts, 0, 8, 6);
+ if(tree == NULL) return OUT_OF_MEMORY();
+
+ for(i = 0; i < numVerts; i++)
+ BLI_bvhtree_insert(tree, i, vert[i].co, 1);
+ BLI_bvhtree_balance(tree);
+ BENCH_END(build);
+ BENCH_REPORT(build);
+
+
//Generate kd-tree with target vertexs
+ BENCH_RESET(build);
BENCH_BEGIN(build);
- target = BLI_kdtree_new(calc->target->getNumVerts(calc->target));
+ target = BLI_kdtree_new(numVerts);
if(target == NULL) return OUT_OF_MEMORY();
- numVerts= calc->target->getNumVerts(calc->target);
- vert = calc->target->getVertDataArray(calc->target, CD_MVERT);
+ for(i = 0; i < numVerts; i++)
+ BLI_kdtree_insert(target, 0, vert[i].co, NULL);
-
- for( ;numVerts--; vert++)
- BLI_kdtree_insert(target, 0, vert->co, NULL);
-
BLI_kdtree_balance(target);
BENCH_END(build);
+ BENCH_REPORT(build);
//Find the nearest vertex
@@ -815,17 +832,27 @@
vert = calc->final->getVertDataArray(calc->final, CD_MVERT);
dvert = calc->final->getVertDataArray(calc->final, CD_MDEFORMVERT);
+ BENCH_BEGIN(query);
for(i=0; i<numVerts; i++)
{
- int t;
+ int t, index;
float weight = vertexgroup_get_weight(dvert, i, vgroup);
if(weight == 0.0f) continue;
- VecMat4MulVecfl(tmp_co, calc->local2target, vert[i].co);
+/* VecMat4MulVecfl(tmp_co, calc->local2target, vert[i].co);
- BENCH_BEGIN(query);
+ index = BLI_bvhtree_find_nearest(tree, tmp_co);
+ if(index != -1)
+ {
+ float dist;
+ VecMat4MulVecfl(tmp_co, calc->target2local, tvert[index].co);
+ dist = VecLenf(vert[i].co, tmp_co);
+ if(dist > 1e-5) weight *= (dist - calc->keptDist)/dist;
+ VecLerpf(vert[i].co, vert[i].co, nearest.co, weight); //linear interpolation
+ }
+
+ */
t = BLI_kdtree_find_nearest(target, tmp_co, 0, &nearest);
- BENCH_END(query);
if(t != -1)
{
@@ -836,15 +863,13 @@
if(dist > 1e-5) weight *= (dist - calc->keptDist)/dist;
VecLerpf(vert[i].co, vert[i].co, nearest.co, weight); //linear interpolation
}
+
}
+ BENCH_END(query);
+ BENCH_REPORT(query);
- BENCH_BEGIN(build);
BLI_kdtree_free(target);
- BENCH_END(build);
-
-
- BENCH_REPORT(build);
- BENCH_REPORT(query);
+ BLI_bvhtree_free(tree);
}
/*
Copied: branches/soc-2008-jaguarandi/source/blender/blenlib/BLI_kdopbvh.h (from rev 14831, branches/cloth/blender/source/blender/blenlib/BLI_kdopbvh.h)
===================================================================
--- branches/soc-2008-jaguarandi/source/blender/blenlib/BLI_kdopbvh.h (rev 0)
+++ branches/soc-2008-jaguarandi/source/blender/blenlib/BLI_kdopbvh.h 2008-05-14 18:25:23 UTC (rev 14843)
@@ -0,0 +1,63 @@
+/**
+ *
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2006 by NaN Holding BV.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): Daniel Genrich, Andre Pinto
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+
+#ifndef BLI_KDOPBVH_H
+#define BLI_KDOPBVH_H
+
+#include <float.h>
+
+struct BVHTree;
+typedef struct BVHTree BVHTree;
+
+typedef struct BVHTreeOverlap {
+ int indexA;
+ int indexB;
+} BVHTreeOverlap;
+
+BVHTree *BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis);
+void BLI_bvhtree_free(BVHTree *tree);
+
+/* construct: first insert points, then call balance */
+int BLI_bvhtree_insert(BVHTree *tree, int index, float *co, int numpoints);
+void BLI_bvhtree_balance(BVHTree *tree);
+
+/* update: first update points/nodes, then call update_tree to refit the bounding volumes */
+int BLI_bvhtree_update_node(BVHTree *tree, int index, float *co, float *co_moving, int numpoints);
+void BLI_bvhtree_update_tree(BVHTree *tree);
+
+/* collision/overlap: check two trees if they overlap, alloc's *overlap with length of the int return value */
+BVHTreeOverlap *BLI_bvhtree_overlap(BVHTree *tree1, BVHTree *tree2, int *result);
+
+float BLI_bvhtree_getepsilon(BVHTree *tree);
+
+#endif // BLI_KDOPBVH_H
+
+
+
+
Copied: branches/soc-2008-jaguarandi/source/blender/blenlib/intern/BLI_kdopbvh.c (from rev 14831, branches/cloth/blender/source/blender/blenlib/intern/BLI_kdopbvh.c)
===================================================================
--- branches/soc-2008-jaguarandi/source/blender/blenlib/intern/BLI_kdopbvh.c (rev 0)
+++ branches/soc-2008-jaguarandi/source/blender/blenlib/intern/BLI_kdopbvh.c 2008-05-14 18:25:23 UTC (rev 14843)
@@ -0,0 +1,725 @@
+/* kdop.c
+*
+*
+* ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
+*
+* This program is free software; you can redistribute it and/or
+* modify it under the terms of the GNU General Public License
+* as published by the Free Software Foundation; either version 2
+* of the License, or (at your option) any later version. The Blender
+* Foundation also sells licenses for use in proprietary software under
+* the Blender License. See http://www.blender.org/BL/ for information
+* about this.
+*
+* This program is distributed in the hope that it will be useful,
+* but WITHOUT ANY WARRANTY; without even the implied warranty of
+* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+* GNU General Public License for more details.
+*
+* You should have received a copy of the GNU General Public License
+* along with this program; if not, write to the Free Software Foundation,
+* Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+*
+* The Original Code is Copyright (C) Blender Foundation
+* All rights reserved.
+*
+* The Original Code is: all of this file.
+*
+* Contributor(s): Daniel Genrich, Andre Pinto
+*
+* ***** END GPL/BL DUAL LICENSE BLOCK *****
+*/
+
+#include "math.h"
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "MEM_guardedalloc.h"
+
+#include "BKE_utildefines.h"
+
+#include "BLI_kdopbvh.h"
+#include "BLI_arithb.h"
+
+#ifdef _OPENMP
+#include <omp.h>
+#endif
+
+#define node_get_bv(tree, node) ((node)->bv)
+#define node_get_child(tree,node,i) ((node)->children[i])
+
+typedef struct BVHNode
+{
+ struct BVHNode **children;// max 8 children
+ struct BVHNode *parent; // needed for bottom - top update
+ float *bv; // Bounding volume of all nodes, max 13 axis
+ int index; // face, edge, vertex index
+ char totnode; // how many nodes are used, used for speedup
+ char traversed; // how many nodes already traversed until this level?
+ char main_axis; // axis that was used to split childs
+} BVHNode;
+
+struct BVHTree
+{
+ BVHNode **nodes;
+ float *nodebv; // pre-alloc bounding-volumes for nodes
+ BVHNode **nodechild; // pre-alloc childs for nodes
+ BVHNode *nodearray; // pre-alloc branchs
+ float epsilon; // epslion is used for inflation of the k-dop
+ int totleaf; // leafs
+ int totbranch;
+ char tree_type; // type of tree (4 => quadtree)
+ char axis; // kdop type (6 => OBB, 7 => AABB, ...)
+ char start_axis, stop_axis; // KDOP_AXES array indices according to axis
+};
+
+typedef struct BVHOverlapData
+{
+ BVHTree *tree1, *tree2;
+ BVHTreeOverlap *overlap;
+ int i, max_overlap; /* i is number of overlaps */
+} BVHOverlapData;
+////////////////////////////////////////
+
+
+////////////////////////////////////////////////////////////////////////
+// Bounding Volume Hierarchy Definition
+//
+// Notes: From OBB until 26-DOP --> all bounding volumes possible, just choose type below
+// Notes: You have to choose the type at compile time ITM
+// Notes: You can choose the tree type --> binary, quad, octree, choose below
+////////////////////////////////////////////////////////////////////////
+
+static float KDOP_AXES[13][3] =
+{ {1.0, 0, 0}, {0, 1.0, 0}, {0, 0, 1.0}, {1.0, 1.0, 1.0}, {1.0, -1.0, 1.0}, {1.0, 1.0, -1.0},
+{1.0, -1.0, -1.0}, {1.0, 1.0, 0}, {1.0, 0, 1.0}, {0, 1.0, 1.0}, {1.0, -1.0, 0}, {1.0, 0, -1.0},
+{0, 1.0, -1.0}
+};
+
+//////////////////////////////////////////////////////////////////////////////////////////////////////
+// Introsort
+// with permission deriven from the following Java code:
+// http://ralphunden.net/content/tutorials/a-guide-to-introsort/
+// and he derived it from the SUN STL
+//////////////////////////////////////////////////////////////////////////////////////////////////////
+
+static int bvh_partition(BVHNode **a, int lo, int hi, BVHNode * x, int axis)
+{
+ int i=lo, j=hi;
+ while (1)
+ {
+ while ((a[i])->bv[axis] < x->bv[axis]) i++;
+ j--;
+ while (x->bv[axis] < (a[j])->bv[axis]) j--;
+ if(!(i < j))
+ return i;
+ SWAP( BVHNode* , a[i], a[j]);
+ i++;
+ }
+}
+
+static BVHNode *bvh_medianof3(BVHNode **a, int lo, int mid, int hi, int axis) // returns Sortable
+{
+ if ((a[mid])->bv[axis] < (a[lo])->bv[axis])
+ {
+ if ((a[hi])->bv[axis] < (a[mid])->bv[axis])
+ return a[mid];
+ else
+ {
+ if ((a[hi])->bv[axis] < (a[lo])->bv[axis])
+ return a[hi];
+ else
+ return a[lo];
+ }
+ }
+ else
+ {
+ if ((a[hi])->bv[axis] < (a[mid])->bv[axis])
+ {
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list