[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [23649] trunk/blender: Merged Soc 2009 - raytrace optimization [0]
Andre Susano Pinto
andresusanopinto at gmail.com
Tue Oct 6 04:56:13 CEST 2009
Revision: 23649
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=23649
Author: jaguarandi
Date: 2009-10-06 04:56:11 +0200 (Tue, 06 Oct 2009)
Log Message:
-----------
Merged Soc 2009 - raytrace optimization [0]
from branch [1] at rev 23647
[0] - http://wiki.blender.org/index.php/User:Jaguarandi/SummerOfCode2009/
[1] - https://svn.blender.org/svnroot/bf-blender/branches/soc-2009-jaguarandi
Revision Links:
--------------
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=23647
Modified Paths:
--------------
trunk/blender/release/scripts/ui/buttons_scene.py
trunk/blender/source/blender/blenkernel/BKE_utildefines.h
trunk/blender/source/blender/blenlib/BLI_memarena.h
trunk/blender/source/blender/blenlib/intern/BLI_kdopbvh.c
trunk/blender/source/blender/blenlib/intern/BLI_memarena.c
trunk/blender/source/blender/editors/armature/meshlaplacian.c
trunk/blender/source/blender/makesdna/DNA_scene_types.h
trunk/blender/source/blender/makesrna/intern/rna_scene.c
trunk/blender/source/blender/render/SConscript
trunk/blender/source/blender/render/extern/include/RE_raytrace.h
trunk/blender/source/blender/render/extern/include/RE_shader_ext.h
trunk/blender/source/blender/render/intern/include/render_types.h
trunk/blender/source/blender/render/intern/include/rendercore.h
trunk/blender/source/blender/render/intern/source/pipeline.c
trunk/blender/source/blender/render/intern/source/rayshade.c
trunk/blender/source/blender/render/intern/source/rendercore.c
trunk/blender/source/blender/render/intern/source/renderdatabase.c
trunk/blender/source/blender/render/intern/source/shadeinput.c
trunk/blender/source/blender/render/intern/source/volume_precache.c
trunk/blender/source/blender/render/intern/source/volumetric.c
trunk/blender/source/blender/windowmanager/intern/wm_init_exit.c
Added Paths:
-----------
trunk/blender/source/blender/render/intern/include/raycounter.h
trunk/blender/source/blender/render/intern/include/rayobject.h
trunk/blender/source/blender/render/intern/raytrace/
trunk/blender/source/blender/render/intern/raytrace/bvh.h
trunk/blender/source/blender/render/intern/raytrace/rayobject.cpp
trunk/blender/source/blender/render/intern/raytrace/rayobject_hint.h
trunk/blender/source/blender/render/intern/raytrace/rayobject_qbvh.cpp
trunk/blender/source/blender/render/intern/raytrace/rayobject_rtbuild.cpp
trunk/blender/source/blender/render/intern/raytrace/rayobject_rtbuild.h
trunk/blender/source/blender/render/intern/raytrace/rayobject_svbvh.cpp
trunk/blender/source/blender/render/intern/raytrace/rayobject_vbvh.cpp
trunk/blender/source/blender/render/intern/raytrace/reorganize.h
trunk/blender/source/blender/render/intern/raytrace/svbvh.h
trunk/blender/source/blender/render/intern/raytrace/vbvh.h
trunk/blender/source/blender/render/intern/source/rayobject_blibvh.c
trunk/blender/source/blender/render/intern/source/rayobject_instance.c
trunk/blender/source/blender/render/intern/source/rayobject_octree.c
trunk/blender/source/blender/render/intern/source/rayobject_raycounter.c
Removed Paths:
-------------
trunk/blender/source/blender/render/intern/source/raytrace.c
Modified: trunk/blender/release/scripts/ui/buttons_scene.py
===================================================================
--- trunk/blender/release/scripts/ui/buttons_scene.py 2009-10-06 02:45:42 UTC (rev 23648)
+++ trunk/blender/release/scripts/ui/buttons_scene.py 2009-10-06 02:56:11 UTC (rev 23649)
@@ -179,8 +179,13 @@
sub.itemR(rd, "free_image_textures")
sub = col.column()
sub.active = rd.render_raytracing
- sub.itemL(text="Ray Tracing Octree:")
- sub.itemR(rd, "octree_resolution", text="")
+ sub.itemL(text="Acceleration structure:")
+ sub.itemR(rd, "raytrace_structure", text="")
+ if rd.raytrace_structure == "OCTREE":
+ sub.itemR(rd, "octree_resolution", text="Resolution")
+ else:
+ sub.itemR(rd, "use_instances", text="Instances")
+ sub.itemR(rd, "use_local_coords", text="Local Coordinates")
class SCENE_PT_post_processing(RenderButtonsPanel):
__label__ = "Post Processing"
Modified: trunk/blender/source/blender/blenkernel/BKE_utildefines.h
===================================================================
--- trunk/blender/source/blender/blenkernel/BKE_utildefines.h 2009-10-06 02:45:42 UTC (rev 23648)
+++ trunk/blender/source/blender/blenkernel/BKE_utildefines.h 2009-10-06 02:56:11 UTC (rev 23649)
@@ -75,6 +75,14 @@
#define INIT_MINMAX2(min, max) { (min)[0]= (min)[1]= 1.0e30f; (max)[0]= (max)[1]= -1.0e30f; }
+#define DO_MIN(vec, min) { if( (min)[0]>(vec)[0] ) (min)[0]= (vec)[0]; \
+ if( (min)[1]>(vec)[1] ) (min)[1]= (vec)[1]; \
+ if( (min)[2]>(vec)[2] ) (min)[2]= (vec)[2]; } \
+
+#define DO_MAX(vec, max) { if( (max)[0]<(vec)[0] ) (max)[0]= (vec)[0]; \
+ if( (max)[1]<(vec)[1] ) (max)[1]= (vec)[1]; \
+ if( (max)[2]<(vec)[2] ) (max)[2]= (vec)[2]; } \
+
#define DO_MINMAX(vec, min, max) { if( (min)[0]>(vec)[0] ) (min)[0]= (vec)[0]; \
if( (min)[1]>(vec)[1] ) (min)[1]= (vec)[1]; \
if( (min)[2]>(vec)[2] ) (min)[2]= (vec)[2]; \
Modified: trunk/blender/source/blender/blenlib/BLI_memarena.h
===================================================================
--- trunk/blender/source/blender/blenlib/BLI_memarena.h 2009-10-06 02:45:42 UTC (rev 23648)
+++ trunk/blender/source/blender/blenlib/BLI_memarena.h 2009-10-06 02:56:11 UTC (rev 23649)
@@ -37,6 +37,10 @@
#ifndef BLI_MEMARENA_H
#define BLI_MEMARENA_H
+#ifdef __cplusplus
+extern "C" {
+#endif
+
/* A reasonable standard buffer size, big
* enough to not cause much internal fragmentation,
* small enough not to waste resources
@@ -53,7 +57,14 @@
void BLI_memarena_use_malloc (struct MemArena *ma);
void BLI_memarena_use_calloc (struct MemArena *ma);
+void BLI_memarena_use_align(struct MemArena *ma, int align);
+
void* BLI_memarena_alloc (struct MemArena *ma, int size);
+#ifdef __cplusplus
+}
#endif
+
+#endif
+
Modified: trunk/blender/source/blender/blenlib/intern/BLI_kdopbvh.c
===================================================================
--- trunk/blender/source/blender/blenlib/intern/BLI_kdopbvh.c 2009-10-06 02:45:42 UTC (rev 23648)
+++ trunk/blender/source/blender/blenlib/intern/BLI_kdopbvh.c 2009-10-06 02:56:11 UTC (rev 23649)
@@ -52,6 +52,7 @@
{
struct BVHNode **children;
struct BVHNode *parent; // some user defined traversed need that
+ struct BVHNode *skip[2];
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
@@ -101,6 +102,8 @@
BVHTreeRay ray;
float ray_dot_axis[13];
+ float idot_axis[13];
+ int index[6];
BVHTreeRayHit hit;
} BVHRayCastData;
@@ -353,7 +356,24 @@
}
//////////////////////////////////////////////////////////////////////////////////////////////////////
+static void build_skip_links(BVHTree *tree, BVHNode *node, BVHNode *left, BVHNode *right)
+{
+ int i;
+
+ node->skip[0] = left;
+ node->skip[1] = right;
+
+ for (i = 0; i < node->totnode; i++)
+ {
+ if(i+1 < node->totnode)
+ build_skip_links(tree, node->children[i], left, node->children[i+1] );
+ else
+ build_skip_links(tree, node->children[i], left, right );
+ left = node->children[i];
+ }
+}
+
/*
* BVHTree bounding volumes functions
*/
@@ -939,6 +959,7 @@
for(i = 0; i < tree->totbranch; i++)
tree->nodes[tree->totleaf + i] = branches_array + i;
+ build_skip_links(tree, tree->nodes[tree->totleaf], NULL, NULL);
//bvhtree_info(tree);
}
@@ -1405,6 +1426,7 @@
* raycast is done by performing a DFS on the BVHTree and saving the closest hit
*/
+
//Determines the distance that the ray must travel to hit the bounding volume of the given node
static float ray_nearest_hit(BVHRayCastData *data, float *bv)
{
@@ -1443,13 +1465,40 @@
return low;
}
+//Determines the distance that the ray must travel to hit the bounding volume of the given node
+//Based on Tactical Optimization of Ray/Box Intersection, by Graham Fyffe
+//[http://tog.acm.org/resources/RTNews/html/rtnv21n1.html#art9]
+//
+//TODO this doens't has data->ray.radius in consideration
+static float fast_ray_nearest_hit(const BVHRayCastData *data, const BVHNode *node)
+{
+ const float *bv = node->bv;
+ float dist;
+
+ float t1x = (bv[data->index[0]] - data->ray.origin[0]) * data->idot_axis[0];
+ float t2x = (bv[data->index[1]] - data->ray.origin[0]) * data->idot_axis[0];
+ float t1y = (bv[data->index[2]] - data->ray.origin[1]) * data->idot_axis[1];
+ float t2y = (bv[data->index[3]] - data->ray.origin[1]) * data->idot_axis[1];
+ float t1z = (bv[data->index[4]] - data->ray.origin[2]) * data->idot_axis[2];
+ float t2z = (bv[data->index[5]] - data->ray.origin[2]) * data->idot_axis[2];
+
+ if(t1x > t2y || t2x < t1y || t1x > t2z || t2x < t1z || t1y > t2z || t2y < t1z) return FLT_MAX;
+ if(t2x < 0.0 || t2y < 0.0 || t2z < 0.0) return FLT_MAX;
+ if(t1x > data->hit.dist || t1y > data->hit.dist || t1z > data->hit.dist) return FLT_MAX;
+
+ dist = t1x;
+ if (t1y > dist) dist = t1y;
+ if (t1z > dist) dist = t1z;
+ return dist;
+}
+
static void dfs_raycast(BVHRayCastData *data, BVHNode *node)
{
int i;
//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->bv);
+ float dist = fast_ray_nearest_hit(data, node);
if(dist >= data->hit.dist) return;
if(node->totnode == 0)
@@ -1483,6 +1532,37 @@
}
}
+static void iterative_raycast(BVHRayCastData *data, BVHNode *node)
+{
+ while(node)
+ {
+ float dist = fast_ray_nearest_hit(data, node);
+ if(dist >= data->hit.dist)
+ {
+ node = node->skip[1];
+ continue;
+ }
+
+ if(node->totnode == 0)
+ {
+ if(data->callback)
+ data->callback(data->userdata, node->index, &data->ray, &data->hit);
+ else
+ {
+ data->hit.index = node->index;
+ data->hit.dist = dist;
+ VECADDFAC(data->hit.co, data->ray.origin, data->ray.direction, dist);
+ }
+
+ node = node->skip[1];
+ }
+ else
+ {
+ node = node->children[0];
+ }
+ }
+}
+
int BLI_bvhtree_ray_cast(BVHTree *tree, const float *co, const float *dir, float radius, BVHTreeRayHit *hit, BVHTree_RayCastCallback callback, void *userdata)
{
int i;
@@ -1503,9 +1583,16 @@
for(i=0; i<3; i++)
{
data.ray_dot_axis[i] = INPR( data.ray.direction, KDOP_AXES[i]);
+ data.idot_axis[i] = 1.0f / data.ray_dot_axis[i];
if(fabs(data.ray_dot_axis[i]) < FLT_EPSILON)
+ {
data.ray_dot_axis[i] = 0.0;
+ }
+ data.index[2*i] = data.idot_axis[i] < 0.0 ? 1 : 0;
+ data.index[2*i+1] = 1 - data.index[2*i];
+ data.index[2*i] += 2*i;
+ data.index[2*i+1] += 2*i;
}
@@ -1518,7 +1605,10 @@
}
if(root)
+ {
dfs_raycast(&data, root);
+// iterative_raycast(&data, root);
+ }
if(hit)
Modified: trunk/blender/source/blender/blenlib/intern/BLI_memarena.c
===================================================================
--- trunk/blender/source/blender/blenlib/intern/BLI_memarena.c 2009-10-06 02:45:42 UTC (rev 23648)
+++ trunk/blender/source/blender/blenlib/intern/BLI_memarena.c 2009-10-06 02:56:11 UTC (rev 23649)
@@ -45,6 +45,7 @@
int bufsize, cursize;
int use_calloc;
+ int align;
LinkNode *bufs;
};
@@ -52,6 +53,7 @@
MemArena *BLI_memarena_new(int bufsize) {
MemArena *ma= MEM_callocN(sizeof(*ma), "memarena");
ma->bufsize= bufsize;
+ ma->align = 8;
return ma;
}
@@ -64,6 +66,11 @@
ma->use_calloc= 0;
}
+void BLI_memarena_use_align(struct MemArena *ma, int align) {
+ /* align should be a power of two */
+ ma->align = align;
+}
+
void BLI_memarena_free(MemArena *ma) {
BLI_linklist_free(ma->bufs, (void(*)(void*)) MEM_freeN);
MEM_freeN(ma);
@@ -77,16 +84,28 @@
/* ensure proper alignment by rounding
* size up to multiple of 8 */
- size= PADUP(size, 8);
+ size= PADUP(size, ma->align);
if (size>ma->cursize) {
- ma->cursize= (size>ma->bufsize)?size:ma->bufsize;
+ unsigned char *tmp;
+
+ if(size > ma->bufsize - (ma->align - 1))
+ {
+ ma->cursize = PADUP(size+1, ma->align);
+ }
+ else ma->cursize = ma->bufsize;
+
if(ma->use_calloc)
ma->curbuf= MEM_callocN(ma->cursize, "memarena calloc");
else
ma->curbuf= MEM_mallocN(ma->cursize, "memarena malloc");
BLI_linklist_prepend(&ma->bufs, ma->curbuf);
+
+ /* align alloc'ed memory (needed if align > 8) */
+ tmp = (unsigned char*)PADUP( (intptr_t) ma->curbuf, ma->align);
+ ma->cursize -= (tmp - ma->curbuf);
+ ma->curbuf = tmp;
}
ptr= ma->curbuf;
@@ -95,3 +114,4 @@
return ptr;
}
+
Modified: trunk/blender/source/blender/editors/armature/meshlaplacian.c
===================================================================
--- trunk/blender/source/blender/editors/armature/meshlaplacian.c 2009-10-06 02:45:42 UTC (rev 23648)
+++ trunk/blender/source/blender/editors/armature/meshlaplacian.c 2009-10-06 02:56:11 UTC (rev 23649)
@@ -105,8 +105,9 @@
float *p; /* values from all p vectors */
float *mindist; /* minimum distance to a bone for all vertices */
- RayTree *raytree; /* ray tracing acceleration structure */
- MFace **vface; /* a face that the vertex belongs to */
+ RayObject *raytree; /* ray tracing acceleration structure */
+ RayFace *faces; /* faces to add to the ray tracing struture */
+ MFace **vface; /* a face that the vertex belongs to */
} heat;
#ifdef RIGID_DEFORM
@@ -394,75 +395,41 @@
#define DISTANCE_EPSILON 1e-4f
/* Raytracing for vertex to bone visibility */
-
-static LaplacianSystem *HeatSys = NULL;
-
-static void heat_ray_coords_func(RayFace *face, float **v1, float **v2, float **v3, float **v4)
-{
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list