sub.active = rd.render_raytracing
sub.itemL(text="Ray Tracing Octree:")
sub.itemR(rd, "octree_resolution", text="")
+ sub.itemR(rd, "raytrace_structure", text="Structure")
+ sub.itemR(rd, "raytrace_tree_type", text="Tree Type")
class SCENE_PT_post_processing(RenderButtonsPanel):
__label__ = "Post Processing"
#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]; \
#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
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
{
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
BVHTreeRay ray;
float ray_dot_axis[13];
+ float idot_axis[13];
+ int index[6];
BVHTreeRayHit hit;
} BVHRayCastData;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////
+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
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);
}
* 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)
{
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)
}
}
+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;
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;
}
}
if(root)
+ {
dfs_raycast(&data, root);
+// iterative_raycast(&data, root);
+ }
if(hit)
int bufsize, cursize;
int use_calloc;
+ int align;
LinkNode *bufs;
};
MemArena *BLI_memarena_new(int bufsize) {
MemArena *ma= MEM_callocN(sizeof(*ma), "memarena");
ma->bufsize= bufsize;
+ ma->align = 8;
return ma;
}
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);
/* 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;
return ptr;
}
+
#include <math.h>
#include <string.h>
+#include <assert.h>
#include "MEM_guardedalloc.h"
float *p; /* values from all p vectors */
float *mindist; /* minimum distance to a bone for all vertices */
- RayTree *raytree; /* ray tracing acceleration structure */
+ RayObject *raytree; /* ray tracing acceleration structure */
MFace **vface; /* a face that the vertex belongs to */
} heat;
#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)
-{
- MFace *mface= (MFace*)face;
- float (*verts)[3]= HeatSys->heat.verts;
-
- *v1= verts[mface->v1];
- *v2= verts[mface->v2];
- *v3= verts[mface->v3];
- *v4= (mface->v4)? verts[mface->v4]: NULL;
-}
-
-static int heat_ray_check_func(Isect *is, int ob, RayFace *face)
-{
- float *v1, *v2, *v3, *v4, nor[3];
-
- /* don't intersect if the ray faces along the face normal */
- heat_ray_coords_func(face, &v1, &v2, &v3, &v4);
-
- if(v4) CalcNormFloat4(v1, v2, v3, v4, nor);
- else CalcNormFloat(v1, v2, v3, nor);
-
- return (INPR(nor, is->vec) < 0);
-}
-
static void heat_ray_tree_create(LaplacianSystem *sys)
{
Mesh *me = sys->heat.mesh;
- RayTree *tree;
MFace *mface;
- float min[3], max[3];
int a;
- /* create a raytrace tree from the mesh */
- INIT_MINMAX(min, max);
-
- for(a=0; a<me->totvert; a++)
- DO_MINMAX(sys->heat.verts[a], min, max);
-
- tree= RE_ray_tree_create(64, me->totface, min, max,
- heat_ray_coords_func, heat_ray_check_func, NULL, NULL);
-
- sys->heat.vface= MEM_callocN(sizeof(MFace*)*me->totvert, "HeatVFaces");
-
- HeatSys= sys;
+ assert(0); //TODO
+ //sys->heat.raytree = RE_rayobject_mesh_create(me, me);
+ sys->heat.vface = MEM_callocN(sizeof(MFace*)*me->totvert, "HeatVFaces");
for(a=0, mface=me->mface; a<me->totface; a++, mface++) {
- RE_ray_tree_add_face(tree, 0, mface);
-
sys->heat.vface[mface->v1]= mface;
sys->heat.vface[mface->v2]= mface;
sys->heat.vface[mface->v3]= mface;
if(mface->v4) sys->heat.vface[mface->v4]= mface;
}
-
- HeatSys= NULL;
-
- RE_ray_tree_done(tree);
-
- sys->heat.raytree= tree;
}
static int heat_ray_bone_visible(LaplacianSystem *sys, int vertex, int bone)
{
Isect isec;
MFace *mface;
- float dir[3];
+ float end[3];
int visible;
+ assert( 0 );
mface= sys->heat.vface[vertex];
if(!mface)
return 1;
memset(&isec, 0, sizeof(isec));
isec.mode= RE_RAY_SHADOW;
isec.lay= -1;
- isec.face_last= NULL;
- isec.faceorig= mface;
+ isec.orig.face = mface;
+ isec.skip = RE_SKIP_CULLFACE;
VECCOPY(isec.start, sys->heat.verts[vertex]);
- PclosestVL3Dfl(isec.end, isec.start,
- sys->heat.root[bone], sys->heat.tip[bone]);
+ PclosestVL3Dfl(end, isec.start, sys->heat.root[bone], sys->heat.tip[bone]);
+
+ VECSUB(isec.vec, end, isec.start);
+ isec.labda = 1.0f;
+#if 0
+ TODO
/* add an extra offset to the start position to avoid self intersection */
- VECSUB(dir, isec.end, isec.start);
+ VECCOPY(dir, isec.vec);
Normalize(dir);
VecMulf(dir, 1e-5);
VecAddf(isec.start, isec.start, dir);
-
- HeatSys= sys;
- visible= !RE_ray_tree_intersect(sys->heat.raytree, &isec);
- HeatSys= NULL;
+#endif
+ visible= !RE_rayobject_raycast(sys->heat.raytree, &isec);
return visible;
}
/* free */
if(vertsflipped) MEM_freeN(vertsflipped);
- RE_ray_tree_free(sys->heat.raytree);
+ RE_rayobject_free(sys->heat.raytree);
MEM_freeN(sys->heat.vface);
MEM_freeN(sys->heat.mindist);
int *varidx;
/* raytrace */
- RayTree *raytree;
+ RayObject *raytree;
} MeshDeformBind;
/* ray intersection */
static int meshdeform_intersect(MeshDeformBind *mdb, Isect *isec)
{
MFace *mface;
- float face[4][3], co[3], uvw[3], len, nor[3];
+ float face[4][3], co[3], uvw[3], len, nor[3], end[3];
int f, hit, is= 0, totface;
isec->labda= 1e10;
mface= mdb->cagedm->getFaceArray(mdb->cagedm);
totface= mdb->cagedm->getNumFaces(mdb->cagedm);
+ VECADDFAC( end, isec->start, isec->vec, isec->labda );
+
for(f=0; f<totface; f++, mface++) {
VECCOPY(face[0], mdb->cagecos[mface->v1]);
VECCOPY(face[1], mdb->cagecos[mface->v2]);
if(mface->v4) {
VECCOPY(face[3], mdb->cagecos[mface->v4]);
- hit= meshdeform_tri_intersect(isec->start, isec->end, face[0], face[1], face[2], co, uvw);
+ hit = meshdeform_tri_intersect(isec->start, end, face[0], face[1], face[2], co, uvw);
if(hit) {
CalcNormFloat(face[0], face[1], face[2], nor);
}
else {
- hit= meshdeform_tri_intersect(isec->start, isec->end, face[0], face[2], face[3], co, uvw);
+ hit= meshdeform_tri_intersect(isec->start, end, face[0], face[2], face[3], co, uvw);
CalcNormFloat(face[0], face[2], face[3], nor);
}
}
else {
- hit= meshdeform_tri_intersect(isec->start, isec->end, face[0], face[1], face[2], co, uvw);
+ hit= meshdeform_tri_intersect(isec->start, end, face[0], face[1], face[2], co, uvw);
CalcNormFloat(face[0], face[1], face[2], nor);
}
if(hit) {
- len= VecLenf(isec->start, co)/VecLenf(isec->start, isec->end);
+ len= VecLenf(isec->start, co)/VecLenf(isec->start, end);
if(len < isec->labda) {
isec->labda= len;
- isec->face= mface;
+ isec->hit.face = mface;
isec->isect= (INPR(isec->vec, nor) <= 0.0f);
is= 1;
}
Isect isec;
float (*cagecos)[3];
MFace *mface;
- float vert[4][3], len;
+ float vert[4][3], len, end[3];
static float epsilon[3]= {0, 0, 0}; //1e-4, 1e-4, 1e-4};
/* setup isec */
memset(&isec, 0, sizeof(isec));
isec.mode= RE_RAY_MIRROR; /* we want the closest intersection */
isec.lay= -1;
- isec.face_last= NULL;
- isec.faceorig= NULL;
isec.labda= 1e10f;
VECADD(isec.start, co1, epsilon);
- VECADD(isec.end, co2, epsilon);
- VECSUB(isec.vec, isec.end, isec.start);
+ VECADD(end, co2, epsilon);
+ VECSUB(isec.vec, end, isec.start);
#if 0
/*if(RE_ray_tree_intersect(mdb->raytree, &isec)) {*/
if(meshdeform_intersect(mdb, &isec)) {
len= isec.labda;
- mface= isec.face;
+ mface=(MFace*)isec.hit.face;
/* create MDefBoundIsect */
isect= BLI_memarena_alloc(mdb->memarena, sizeof(*isect));
#define SCE_PASS_RADIO 8192 /* Radio removed, can use for new GI? */
#define SCE_PASS_MIST 16384
+#define SCE_PASS_RAYHITS 32768
+
/* note, srl->passflag is treestore element 'nr' in outliner, short still... */
/* render engine (deprecated), octree resolution */
short renderer, ocres;
+ short raystructure;
+ short raytrace_tree_type;
+ short pad4[2];
/**
* What to do with the sky/background. Picks sky/premul/key
#define R_INTERN 0
#define R_YAFRAY 1
+/* raytrace structure */
+#define R_RAYSTRUCTURE_HIER_BVH_BVH 0
+#define R_RAYSTRUCTURE_HIER_BVH_OCTREE 1
+#define R_RAYSTRUCTURE_SINGLE_OCTREE 2
+#define R_RAYSTRUCTURE_SINGLE_BVH 3
+
+/* raytrace tree type */
+#define R_RAYTRACE_TREE_BVH 0
+#define R_RAYTRACE_TREE_BLIBVH 1
+#define R_RAYTRACE_TREE_BIH 2
+
/* scemode (int now) */
#define R_DOSEQ 0x0001
#define R_BG_RENDER 0x0002
{256, "OCTREE_RES_256", 0, "256", ""},
{512, "OCTREE_RES_512", 0, "512", ""},
{0, NULL, 0, NULL, NULL}};
+
+ static EnumPropertyItem raytrace_structure_items[] = {
+ {R_RAYSTRUCTURE_HIER_BVH_BVH, "{R_RAYSTRUCTURE_HIER_BVH_BVH", 0, "BVH of BVH's", "Create a BVH of objects (each object has it own BVH)"},
+ {R_RAYSTRUCTURE_HIER_BVH_OCTREE, "{R_RAYSTRUCTURE_HIER_BVH_OCTREE", 0, "BVH of octree", "Create a BVH of objects (each object has it own octree)"},
+ {R_RAYSTRUCTURE_SINGLE_BVH, "{R_RAYSTRUCTURE_SINGLE_BVH", 0, "Single BVH", "BVH of all primitives (no instance support)"},
+ {R_RAYSTRUCTURE_SINGLE_OCTREE, "{R_RAYSTRUCTURE_SINGLE_OCTREE", 0, "Octree", "Octree of all primitives (no instance support)"},
+ {0, NULL, 0, NULL, NULL}};
+
+ static EnumPropertyItem raytrace_tree_type_items[] = {
+ {R_RAYTRACE_TREE_BVH, "{R_RAYTRACE_TREE_BVH", 0, "BVH", "rayobject_bvh.c"},
+ {R_RAYTRACE_TREE_BLIBVH, "{R_RAYTRACE_TREE_BLIBVH", 0, "BLIbvh", "rayobject_blibvh.c"},
+ {R_RAYTRACE_TREE_BIH, "{R_RAYSTRUCTURE_SINGLE_BVH", 0, "BIH", "rayobject_bih.c"},
+ {0, NULL, 0, NULL, NULL}};
static EnumPropertyItem fixed_oversample_items[] = {
{5, "OVERSAMPLE_5", 0, "5", ""},
RNA_def_property_enum_items(prop, octree_resolution_items);
RNA_def_property_ui_text(prop, "Octree Resolution", "Resolution of raytrace accelerator. Use higher resolutions for larger scenes.");
RNA_def_property_update(prop, NC_SCENE|ND_RENDER_OPTIONS, NULL);
+
+ prop= RNA_def_property(srna, "raytrace_structure", PROP_ENUM, PROP_NONE);
+ RNA_def_property_enum_sdna(prop, NULL, "raystructure");
+ RNA_def_property_enum_items(prop, raytrace_structure_items);
+ RNA_def_property_ui_text(prop, "Raytrace Acceleration Structure", "Type of raytrace accelerator structure.");
+ RNA_def_property_update(prop, NC_SCENE|ND_RENDER_OPTIONS, NULL);
+
+ prop= RNA_def_property(srna, "raytrace_tree_type", PROP_ENUM, PROP_NONE);
+ RNA_def_property_enum_sdna(prop, NULL, "raytrace_tree_type");
+ RNA_def_property_enum_items(prop, raytrace_tree_type_items);
+ RNA_def_property_ui_text(prop, "Raytrace tree type", "Type of raytrace accelerator structure.");
+ RNA_def_property_update(prop, NC_SCENE|ND_RENDER_OPTIONS, NULL);
prop= RNA_def_property(srna, "antialiasing", PROP_BOOLEAN, PROP_NONE);
RNA_def_property_boolean_sdna(prop, NULL, "mode", R_OSA);
#!/usr/bin/python
Import ('env')
-cflags=''
+cflags = ['-O3','-msse2','-mfpmath=sse']
+cxxflags = ['-O3','-msse2','-mfpmath=sse']
sources = env.Glob('intern/source/*.c')
+raysources = env.Glob('intern/raytrace/*.cpp')
incs = 'intern/include #/intern/guardedalloc ../blenlib ../makesdna ../makesrna'
incs += ' extern/include ../blenkernel ../radiosity/extern/include ../imbuf'
defs.append('WITH_OPENEXR')
if env['OURPLATFORM']=='linux2':
- cflags='-pthread'
+ cflags += ['-pthread']
env.BlenderLib ( libname = 'bf_render', sources = sources, includes = Split(incs), defines=defs, libtype='core', priority=145, compileflags=cflags )
+env.BlenderLib ( libname = 'bf_render_raytrace', sources = raysources, includes = Split(incs), defines=defs, libtype='core', priority=145, compileflags=cflags, cxx_compileflags=cxxflags )
*
* The Original Code is: all of this file.
*
- * Contributor(s): none yet.
+ * Contributor(s): André Pinto.
*
* ***** END GPL LICENSE BLOCK *****
* RE_raytrace.h: ray tracing api, can be used independently from the renderer.
#ifndef RE_RAYTRACE_H
#define RE_RAYTRACE_H
-/* ray types */
-#define RE_RAY_SHADOW 0
-#define RE_RAY_MIRROR 1
-#define RE_RAY_SHADOW_TRA 2
+#ifdef __cplusplus
+extern "C" {
+#endif
-/* spatial tree for raytracing acceleration */
-typedef void RayTree;
-/* abstraction of face type */
-typedef void RayFace;
-/* object numbers above this are transformed */
-#define RE_RAY_TRANSFORM_OFFS 0x8000000
+#define RE_RAY_LCTS_MAX_SIZE 256
+#define RT_USE_LAST_HIT /* last shadow hit is reused before raycasting on whole tree */
+//#define RT_USE_HINT /* last hit object is reused before raycasting on whole tree */
-/* convert from pointer to index in array and back, with offset if the
- * instance is transformed */
-#define RAY_OBJECT_SET(re, obi) \
- ((obi == NULL)? 0: \
- ((obi - (re)->objectinstance) + ((obi->flag & R_TRANSFORMED)? RE_RAY_TRANSFORM_OFFS: 0)))
+#define RE_RAYCOUNTER
-#define RAY_OBJECT_GET(re, i) \
- ((re)->objectinstance + ((i >= RE_RAY_TRANSFORM_OFFS)? i-RE_RAY_TRANSFORM_OFFS: i))
+#ifdef RE_RAYCOUNTER
-/* struct for intersection data */
-typedef struct Isect {
- float start[3]; /* start+vec = end, in ray_tree_intersect */
- float vec[3];
- float end[3];
+typedef struct RayCounter RayCounter;
+struct RayCounter
+{
+
+ struct
+ {
+ unsigned long long test, hit;
+
+ } faces, bb, raycast, raytrace_hint, rayshadow_last_hit;
+};
+
+/* #define RE_RC_INIT(isec, shi) (isec).count = re_rc_counter+(shi).thread */
+#define RE_RC_INIT(isec, shi) (isec).raycounter = &((shi).raycounter)
+void RE_RC_INFO (RayCounter *rc);
+void RE_RC_MERGE(RayCounter *rc, RayCounter *tmp);
+#define RE_RC_COUNT(var) (var)++
+
+extern RayCounter re_rc_counter[];
+
+#else
+
+#define RE_RC_INIT(isec,shi)
+#define RE_RC_INFO(rc)
+#define RE_RC_MERGE(dest,src)
+#define RE_RC_COUNT(var)
+
+#endif
+
+
+/* Internals about raycasting structures can be found on intern/raytree.h */
+typedef struct RayObject RayObject;
+typedef struct Isect Isect;
+typedef struct RayHint RayHint;
+typedef struct RayTraceHint RayTraceHint;
+
+struct DerivedMesh;
+struct Mesh;
+
+int RE_rayobject_raycast(RayObject *r, Isect *i);
+void RE_rayobject_add (RayObject *r, RayObject *);
+void RE_rayobject_done(RayObject *r);
+void RE_rayobject_free(RayObject *r);
+
+/* initializes an hint for optiming raycast where it is know that a ray will pass by the given BB often the origin point */
+void RE_rayobject_hint_bb(RayObject *r, RayHint *hint, float *min, float *max);
+
+/* initializes an hint for optiming raycast where it is know that a ray will be contained inside the given cone*/
+/* void RE_rayobject_hint_cone(RayObject *r, RayHint *hint, float *); */
+
+/* RayObject constructors */
- float labda, u, v; /* distance to hitpoint, uv weights */
+RayObject* RE_rayobject_octree_create(int ocres, int size);
+RayObject* RE_rayobject_instance_create(RayObject *target, float transform[][4], void *ob, void *target_ob);
- RayFace *face; /* face is where to intersect with */
- int ob;
- RayFace *faceorig; /* start face */
- int oborig;
- RayFace *face_last; /* for shadow optimize, last intersected face */
- int ob_last;
+RayObject* RE_rayobject_blibvh_create(int size); /* BLI_kdopbvh.c */
+RayObject* RE_rayobject_bvh_create(int size); /* raytrace/rayobject_bvh.c */
+RayObject* RE_rayobject_vbvh_create(int size); /* raytrace/rayobject_vbvh.c */
+RayObject* RE_rayobject_bih_create(int size); /* rayobject_bih.c */
+typedef struct LCTSHint LCTSHint;
+struct LCTSHint
+{
+ int size;
+ RayObject *stack[RE_RAY_LCTS_MAX_SIZE];
+};
+
+struct RayHint
+{
+ union
+ {
+ LCTSHint lcts;
+ } data;
+};
+
+
+/* Ray Intersection */
+struct Isect
+{
+ float start[3];
+ float vec[3];
+ float labda;
+
+ /* length of vec, configured by RE_rayobject_raycast */
+ int bv_index[6];
+ float idot_axis[3];
+ float dist;
+
+/* float end[3]; - not used */
+
+ float u, v;
+
+ struct
+ {
+ void *ob;
+ void *face;
+ }
+ hit, orig;
+
+ RayObject *last_hit; /* last hit optimization */
+
+#ifdef RT_USE_HINT
+ RayTraceHint *hint, *hit_hint;
+#endif
+
short isect; /* which half of quad */
short mode; /* RE_RAY_SHADOW, RE_RAY_MIRROR, RE_RAY_SHADOW_TRA */
int lay; /* -1 default, set for layer lamps */
+
+ int skip; /* RE_SKIP_CULLFACE */
- /* only used externally */
float col[4]; /* RGBA for shadow_tra */
- /* octree only */
- RayFace *facecontr;
- int obcontr;
- float ddalabda;
- short faceisect; /* flag if facecontr was done or not */
-
- /* custom pointer to be used in the RayCheckFunc */
void *userdata;
-} Isect;
-
-/* function callbacks for face type abstraction */
-typedef void (*RayCoordsFunc)(RayFace *face,
- float **v1, float **v2, float **v3, float **v4);
-typedef int (*RayCheckFunc)(Isect *is, int ob, RayFace *face);
-typedef float *(*RayObjectTransformFunc)(void *userdata, int ob);
-
-/* tree building and freeing */
-RayTree *RE_ray_tree_create(int ocres, int totface, float *min, float *max,
- RayCoordsFunc coordfunc, RayCheckFunc checkfunc,
- RayObjectTransformFunc transformfunc, void *userdata);
-void RE_ray_tree_add_face(RayTree *tree, int ob, RayFace *face);
-void RE_ray_tree_done(RayTree *tree);
-void RE_ray_tree_free(RayTree *tree);
-
-/* intersection with full tree and single face */
-int RE_ray_tree_intersect(RayTree *tree, Isect *is);
-int RE_ray_tree_intersect_check(RayTree *tree, Isect *is, RayCheckFunc check);
-int RE_ray_face_intersection(Isect *is, RayObjectTransformFunc transformfunc,
- RayCoordsFunc coordsfunc);
-
-/* retrieve the diameter of the tree structure, for setting intersection
- end distance */
-float RE_ray_tree_max_size(RayTree *tree);
+
+ RayHint *hint;
+
+#ifdef RE_RAYCOUNTER
+ RayCounter *raycounter;
+#endif
+
+};
-#endif /*__RE_RAYTRACE_H__*/
+/* ray types */
+#define RE_RAY_SHADOW 0
+#define RE_RAY_MIRROR 1
+#define RE_RAY_SHADOW_TRA 2
+
+/* skip options */
+#define RE_SKIP_CULLFACE (1 << 0)
+
+/* if using this flag then *face should be a pointer to a VlakRen */
+#define RE_SKIP_VLR_NEIGHBOUR (1 << 1)
+/* TODO use: FLT_MAX? */
+#define RE_RAYTRACE_MAXDIST 1e33
+
+#ifdef __cplusplus
+}
+#endif
+
+
+#endif /*__RE_RAYTRACE_H__*/
#ifndef RE_SHADER_EXT_H
#define RE_SHADER_EXT_H
+#include "RE_raytrace.h" /* For RE_RAYCOUNTER */
/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ */
/* this include is for shading and texture exports */
/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ */
float refr[3];
float nor[3];
float winspeed[4];
+ float rayhits[4];
} ShadeResult;
/* only here for quick copy */
struct Group *light_override;
struct Material *mat_override;
+#ifdef RE_RAYCOUNTER
+ RayCounter raycounter;
+#endif
+
} ShadeInput;
--- /dev/null
+/**
+ * $Id$
+ *
+ * ***** 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) 2009 Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): André Pinto.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+#ifndef RE_RAYOBJECT_H
+#define RE_RAYOBJECT_H
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include "RE_raytrace.h"
+#include "render_types.h"
+#include <float.h>
+
+
+/* RayObject
+
+ A ray object is everything where we can cast rays like:
+ * a face/triangle
+ * an octree
+ * a bvh tree
+ * an octree of bvh's
+ * a bvh of bvh's
+
+
+ All types of RayObjects can be created by implementing the
+ callbacks of the RayObject.
+
+ Due to high computing time evolved with casting on faces
+ there is a special type of RayObject (named RayFace)
+ which won't use callbacks like other generic nodes.
+
+ In order to allow a mixture of RayFace+RayObjects,
+ all RayObjects must be 4byte aligned, allowing us to use the
+ 2 least significant bits (with the mask 0x02) to define the
+ type of RayObject.
+
+ This leads to 4 possible types of RayObject, but at the moment
+ only 2 are used:
+
+ addr&2 - type of object
+ 0 Self (reserved for each structure)
+ 1 RayFace
+ 2 RayObject (generic with API callbacks)
+ 3 unused
+
+ 0 means it's reserved and has it own meaning inside each ray acceleration structure
+ (this way each structure can use the allign offset to determine if a node represents a
+ RayObject primitive, which can be used to save memory)
+
+ You actually don't need to care about this if you are only using the API
+ described on RE_raytrace.h
+ */
+
+/* defines where coordinates of rayface primitives are stored */
+#define RE_RAYFACE_COORDS_LOCAL
+
+//(ATM this won't work good with all types of instances)
+//#define RE_RAYFACE_COORDS_POINTER
+//#define RE_RAYFACE_COORDS_VLAKREN
+
+typedef struct RayFace
+{
+#ifdef RE_RAYFACE_COORDS_LOCAL
+ float v1[4], v2[4], v3[4], v4[3];
+ int quad;
+ void *ob;
+ void *face;
+#elif defined(RE_RAYFACE_COORDS_POINTER)
+ float *v1, *v2, *v3, *v4;
+ void *ob;
+ void *face;
+#elif defined(RE_RAYFACE_COORDS_VLAKREN)
+ void *ob;
+ void *face;
+#endif
+
+} RayFace;
+
+#ifdef RE_RAYFACE_COORDS_LOCAL
+# define RE_rayface_isQuad(a) ((a)->quad)
+#elif defined(RE_RAYFACE_COORDS_POINTER)
+# define RE_rayface_isQuad(a) ((a)->v4)
+#elif defined(RE_RAYFACE_COORDS_VLAKREN)
+# define RE_rayface_isQuad(a) ((((VlakRen*)((a)->face))->v4) != NULL)
+#endif
+
+
+struct RayObject
+{
+ struct RayObjectAPI *api;
+};
+
+
+typedef int (*RE_rayobject_raycast_callback)(RayObject *, Isect *);
+typedef void (*RE_rayobject_add_callback)(RayObject *raytree, RayObject *rayobject);
+typedef void (*RE_rayobject_done_callback)(RayObject *);
+typedef void (*RE_rayobject_free_callback)(RayObject *);
+typedef void (*RE_rayobject_merge_bb_callback)(RayObject *, float *min, float *max);
+typedef float (*RE_rayobject_cost_callback)(RayObject *);
+typedef void (*RE_rayobject_hint_bb_callback)(RayObject *, RayHint *, float *, float *);
+
+typedef struct RayObjectAPI
+{
+ RE_rayobject_raycast_callback raycast;
+ RE_rayobject_add_callback add;
+ RE_rayobject_done_callback done;
+ RE_rayobject_free_callback free;
+ RE_rayobject_merge_bb_callback bb;
+ RE_rayobject_cost_callback cost;
+ RE_rayobject_hint_bb_callback hint_bb;
+
+} RayObjectAPI;
+
+#define RayObject_align(o) ((RayObject*)(((intptr_t)o)&(~3)))
+#define RayObject_unalignRayFace(o) ((RayObject*)(((intptr_t)o)|1))
+#define RayObject_unalignRayAPI(o) ((RayObject*)(((intptr_t)o)|2))
+
+#define RayObject_isAligned(o) ((((intptr_t)o)&3) == 0)
+#define RayObject_isRayFace(o) ((((intptr_t)o)&3) == 1)
+#define RayObject_isRayAPI(o) ((((intptr_t)o)&3) == 2)
+
+/*
+ * Loads a VlakRen on a RayFace
+ */
+void RE_rayface_from_vlak(RayFace *face, ObjectInstanceRen *obi, VlakRen *vlr);
+
+/*
+ * Extend min/max coords so that the rayobject is inside them
+ */
+void RE_rayobject_merge_bb(RayObject *ob, float *min, float *max);
+
+/*
+ * This function differs from RE_rayobject_raycast
+ * RE_rayobject_intersect does NOT perform last-hit optimization
+ * So this is probably a function to call inside raytrace structures
+ */
+int RE_rayobject_intersect(RayObject *r, Isect *i);
+
+/*
+ * Returns distance ray must travel to hit the given bounding box
+ * BB should be in format [2][3]
+ */
+/* float RE_rayobject_bb_intersect(const Isect *i, const float *bb); */
+int RE_rayobject_bb_intersect_test(const Isect *i, const float *bb); /* same as bb_intersect but doens't calculates distance */
+
+/*
+ * Returns the expected cost of raycast on this node, primitives have a cost of 1
+ */
+float RE_rayobject_cost(RayObject *r);
+
+
+#define ISECT_EPSILON ((float)FLT_EPSILON)
+
+
+
+#if !defined(_WIN32)
+
+#include <sys/time.h>
+#include <time.h>
+#include <stdio.h>
+
+#define BENCH(a,name) \
+ do { \
+ double _t1, _t2; \
+ struct timeval _tstart, _tend; \
+ clock_t _clock_init = clock(); \
+ gettimeofday ( &_tstart, NULL); \
+ (a); \
+ gettimeofday ( &_tend, NULL); \
+ _t1 = ( double ) _tstart.tv_sec + ( double ) _tstart.tv_usec/ ( 1000*1000 ); \
+ _t2 = ( double ) _tend.tv_sec + ( double ) _tend.tv_usec/ ( 1000*1000 ); \
+ printf("BENCH:%s: %fs (real) %fs (cpu)\n", #name, _t2-_t1, (float)(clock()-_clock_init)/CLOCKS_PER_SEC);\
+ } while(0)
+#else
+
+#define BENCH(a) (a)
+
+#endif
+
+
+
+#ifdef __cplusplus
+}
+#endif
+
+
+#endif
struct GHash;
struct RenderBuckets;
struct ObjectInstanceRen;
+struct RayObject;
+struct RayFace;
#define TABLEINITSIZE 1024
#define LAMPINITSIZE 256
ListBase parts;
/* octree tables and variables for raytrace */
- void *raytree;
+ struct RayObject *raytree;
+ struct RayFace *rayfaces;
+ float maxdist; /* needed for keeping an incorrect behaviour of SUN and HEMI lights (avoid breaking old scenes) */
/* occlusion tree */
void *occlusiontree;
int actmtface, actmcol, bakemtface;
float obmat[4][4]; /* only used in convertblender.c, for instancing */
+
+ /* used on makeraytree */
+ struct RayObject *raytree;
+ struct RayFace *rayfaces;
+ struct ObjectInstanceRen *rayobi;
+
} ObjectRen;
typedef struct ObjectInstanceRen {
float *vectors;
int totvector;
+
+ /* used on makeraytree */
+ struct RayObject *raytree;
+
} ObjectInstanceRen;
/* ------------------------------------------------------------------------- */
short YF_glowtype;
/* ray optim */
- VlakRen *vlr_last[BLENDER_MAX_THREADS];
- ObjectInstanceRen *obi_last[BLENDER_MAX_THREADS];
+ struct RayObject *last_hit[BLENDER_MAX_THREADS];
struct MTex *mtex[MAX_MTEX];
--- /dev/null
+/**
+ * $Id$
+ *
+ * ***** 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) 2009 Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): André Pinto.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+#include <xmmintrin.h>
+
+#ifndef RE_RAYTRACE_BVH_H
+#define RE_RAYTRACE_BVH_H
+
+inline int test_bb_group4(__m128 *bb_group, const Isect *isec)
+{
+
+ const __m128 tmin0 = _mm_setzero_ps();
+ const __m128 tmax0 = _mm_load1_ps(&isec->labda);
+
+ const __m128 tmin1 = _mm_max_ps(tmin0, _mm_mul_ps( _mm_sub_ps( bb_group[isec->bv_index[0]], _mm_load1_ps(&isec->start[0]) ), _mm_load1_ps(&isec->idot_axis[0])) );
+ const __m128 tmax1 = _mm_min_ps(tmax0, _mm_mul_ps( _mm_sub_ps( bb_group[isec->bv_index[1]], _mm_load1_ps(&isec->start[0]) ), _mm_load1_ps(&isec->idot_axis[0])) );
+ const __m128 tmin2 = _mm_max_ps(tmin1, _mm_mul_ps( _mm_sub_ps( bb_group[isec->bv_index[2]], _mm_load1_ps(&isec->start[1]) ), _mm_load1_ps(&isec->idot_axis[1])) );
+ const __m128 tmax2 = _mm_min_ps(tmax1, _mm_mul_ps( _mm_sub_ps( bb_group[isec->bv_index[3]], _mm_load1_ps(&isec->start[1]) ), _mm_load1_ps(&isec->idot_axis[1])) );
+ const __m128 tmin3 = _mm_max_ps(tmin2, _mm_mul_ps( _mm_sub_ps( bb_group[isec->bv_index[4]], _mm_load1_ps(&isec->start[2]) ), _mm_load1_ps(&isec->idot_axis[2])) );
+ const __m128 tmax3 = _mm_min_ps(tmax2, _mm_mul_ps( _mm_sub_ps( bb_group[isec->bv_index[5]], _mm_load1_ps(&isec->start[2]) ), _mm_load1_ps(&isec->idot_axis[2])) );
+
+ return _mm_movemask_ps(_mm_cmpge_ps(tmax3, tmin3));
+}
+
+
+/* bvh tree generics */
+template<class Tree> static int bvh_intersect(Tree *obj, Isect *isec);
+
+template<class Tree> static void bvh_add(Tree *obj, RayObject *ob)
+{
+ rtbuild_add( obj->builder, ob );
+}
+
+template<class Node>
+inline bool is_leaf(Node *node)
+{
+ return !RayObject_isAligned(node);
+}
+
+template<class Tree> static void bvh_done(Tree *obj);
+
+template<class Tree>
+static void bvh_free(Tree *obj)
+{
+ if(obj->builder)
+ rtbuild_free(obj->builder);
+
+ if(obj->node_arena)
+ BLI_memarena_free(obj->node_arena);
+
+ MEM_freeN(obj);
+}
+
+template<class Tree>
+static void bvh_bb(Tree *obj, float *min, float *max)
+{
+ bvh_node_merge_bb(obj->root, min, max);
+}
+
+
+template<class Tree>
+static float bvh_cost(Tree *obj)
+{
+ assert(obj->cost >= 0.0);
+ return obj->cost;
+}
+
+
+
+/* bvh tree nodes generics */
+template<class Node> static inline int bvh_node_hit_test(Node *node, Isect *isec)
+{
+ return RE_rayobject_bb_intersect_test(isec, (const float*)node->bb);
+}
+
+
+template<class Node>
+static void bvh_node_merge_bb(Node *node, float *min, float *max)
+{
+ if(is_leaf(node))
+ {
+ RE_rayobject_merge_bb( (RayObject*)node, min, max);
+ }
+ else
+ {
+ DO_MIN(node->bb , min);
+ DO_MAX(node->bb+3, max);
+ }
+}
+
+
+
+/*
+ * recursivly transverse a BVH looking for a rayhit using a local stack
+ */
+template<class Node> static inline void bvh_node_push_childs(Node *node, Isect *isec, Node **stack, int &stack_pos);
+
+template<class Node,int MAX_STACK_SIZE,bool TEST_ROOT>
+static int bvh_node_stack_raycast(Node *root, Isect *isec)
+{
+ Node *stack[MAX_STACK_SIZE];
+ int hit = 0, stack_pos = 0;
+
+ if(!TEST_ROOT && !is_leaf(root))
+ bvh_node_push_childs(root, isec, stack, stack_pos);
+ else
+ stack[stack_pos++] = root;
+
+ while(stack_pos)
+ {
+ Node *node = stack[--stack_pos];
+ if(!is_leaf(node))
+ {
+ if(bvh_node_hit_test(node,isec))
+ {
+ bvh_node_push_childs(node, isec, stack, stack_pos);
+ assert(stack_pos <= MAX_STACK_SIZE);
+ }
+ }
+ else
+ {
+ hit |= RE_rayobject_intersect( (RayObject*)node, isec);
+ if(hit && isec->mode == RE_RAY_SHADOW) return hit;
+ }
+ }
+ return hit;
+}
+
+
+/*
+ * Generic SIMD bvh recursion
+ * this was created to be able to use any simd (with the cost of some memmoves)
+ * it can take advantage of any SIMD width and doens't needs any special tree care
+ */
+template<class Node,int MAX_STACK_SIZE,bool TEST_ROOT>
+static int bvh_node_stack_raycast_simd(Node *root, Isect *isec)
+{
+ Node *stack[MAX_STACK_SIZE];
+
+ int hit = 0, stack_pos = 0;
+
+ if(!TEST_ROOT)
+ {
+ if(!is_leaf(root))
+ {
+ if(!is_leaf(root->child))
+ bvh_node_push_childs(root, isec, stack, stack_pos);
+ else
+ return RE_rayobject_intersect( (RayObject*)root->child, isec);
+ }
+ else
+ return RE_rayobject_intersect( (RayObject*)root, isec);
+ }
+ else
+ {
+ if(!is_leaf(root))
+ stack[stack_pos++] = root;
+ else
+ return RE_rayobject_intersect( (RayObject*)root, isec);
+ }
+
+ while(true)
+ {
+ //Use SIMD 4
+ if(stack_pos >= 4)
+ {
+ __m128 t_bb[6];
+ Node * t_node[4];
+
+ stack_pos -= 4;
+
+ /* prepare the 4BB for SIMD */
+ t_node[0] = stack[stack_pos+0]->child;
+ t_node[1] = stack[stack_pos+1]->child;
+ t_node[2] = stack[stack_pos+2]->child;
+ t_node[3] = stack[stack_pos+3]->child;
+
+ const float *bb0 = stack[stack_pos+0]->bb;
+ const float *bb1 = stack[stack_pos+1]->bb;
+ const float *bb2 = stack[stack_pos+2]->bb;
+ const float *bb3 = stack[stack_pos+3]->bb;
+
+ const __m128 x0y0x1y1 = _mm_shuffle_ps( _mm_load_ps(bb0), _mm_load_ps(bb1), _MM_SHUFFLE(1,0,1,0) );
+ const __m128 x2y2x3y3 = _mm_shuffle_ps( _mm_load_ps(bb2), _mm_load_ps(bb3), _MM_SHUFFLE(1,0,1,0) );
+ t_bb[0] = _mm_shuffle_ps( x0y0x1y1, x2y2x3y3, _MM_SHUFFLE(2,0,2,0) );
+ t_bb[1] = _mm_shuffle_ps( x0y0x1y1, x2y2x3y3, _MM_SHUFFLE(3,1,3,1) );
+
+ const __m128 z0X0z1X1 = _mm_shuffle_ps( _mm_load_ps(bb0), _mm_load_ps(bb1), _MM_SHUFFLE(3,2,3,2) );
+ const __m128 z2X2z3X3 = _mm_shuffle_ps( _mm_load_ps(bb2), _mm_load_ps(bb3), _MM_SHUFFLE(3,2,3,2) );
+ t_bb[2] = _mm_shuffle_ps( z0X0z1X1, z2X2z3X3, _MM_SHUFFLE(2,0,2,0) );
+ t_bb[3] = _mm_shuffle_ps( z0X0z1X1, z2X2z3X3, _MM_SHUFFLE(3,1,3,1) );
+
+ const __m128 Y0Z0Y1Z1 = _mm_shuffle_ps( _mm_load_ps(bb0+4), _mm_load_ps(bb1+4), _MM_SHUFFLE(1,0,1,0) );
+ const __m128 Y2Z2Y3Z3 = _mm_shuffle_ps( _mm_load_ps(bb2+4), _mm_load_ps(bb3+4), _MM_SHUFFLE(1,0,1,0) );
+ t_bb[4] = _mm_shuffle_ps( Y0Z0Y1Z1, Y2Z2Y3Z3, _MM_SHUFFLE(2,0,2,0) );
+ t_bb[5] = _mm_shuffle_ps( Y0Z0Y1Z1, Y2Z2Y3Z3, _MM_SHUFFLE(3,1,3,1) );
+/*
+ for(int i=0; i<4; i++)
+ {
+ Node *t = stack[stack_pos+i];
+ assert(!is_leaf(t));
+
+ float *bb = ((float*)t_bb)+i;
+ bb[4*0] = t->bb[0];
+ bb[4*1] = t->bb[1];
+ bb[4*2] = t->bb[2];
+ bb[4*3] = t->bb[3];
+ bb[4*4] = t->bb[4];
+ bb[4*5] = t->bb[5];
+ t_node[i] = t->child;
+ }
+*/
+ RE_RC_COUNT(isec->raycounter->bb.test);
+ RE_RC_COUNT(isec->raycounter->bb.test);
+ RE_RC_COUNT(isec->raycounter->bb.test);
+ RE_RC_COUNT(isec->raycounter->bb.test);
+
+ int res = test_bb_group4( t_bb, isec );
+
+ for(int i=0; i<4; i++)
+ if(res & (1<<i))
+ {
+ RE_RC_COUNT(isec->raycounter->bb.hit);
+ if(!is_leaf(t_node[i]))
+ {
+ for(Node *t=t_node[i]; t; t=t->sibling)
+ {
+ assert(stack_pos < MAX_STACK_SIZE);
+ stack[stack_pos++] = t;
+ }
+ }
+ else
+ {
+ hit |= RE_rayobject_intersect( (RayObject*)t_node[i], isec);
+ if(hit && isec->mode == RE_RAY_SHADOW) return hit;
+ }
+ }
+ }
+ else if(stack_pos > 0)
+ {
+ Node *node = stack[--stack_pos];
+ assert(!is_leaf(node));
+
+ if(bvh_node_hit_test(node,isec))
+ {
+ if(!is_leaf(node->child))
+ {
+ bvh_node_push_childs(node, isec, stack, stack_pos);
+ assert(stack_pos <= MAX_STACK_SIZE);
+ }
+ else
+ {
+ hit |= RE_rayobject_intersect( (RayObject*)node->child, isec);
+ if(hit && isec->mode == RE_RAY_SHADOW) return hit;
+ }
+ }
+ }
+ else break;
+ }
+ return hit;
+}
+
+
+/*
+ * recursively transverse a BVH looking for a rayhit using system stack
+ */
+/*
+template<class Node>
+static int bvh_node_raycast(Node *node, Isect *isec)
+{
+ int hit = 0;
+ if(bvh_test_node(node, isec))
+ {
+ if(isec->idot_axis[node->split_axis] > 0.0f)
+ {
+ int i;
+ for(i=0; i<BVH_NCHILDS; i++)
+ if(!is_leaf(node->child[i]))
+ {
+ if(node->child[i] == 0) break;
+
+ hit |= bvh_node_raycast(node->child[i], isec);
+ if(hit && isec->mode == RE_RAY_SHADOW) return hit;
+ }
+ else
+ {
+ hit |= RE_rayobject_intersect( (RayObject*)node->child[i], isec);
+ if(hit && isec->mode == RE_RAY_SHADOW) return hit;
+ }
+ }
+ else
+ {
+ int i;
+ for(i=BVH_NCHILDS-1; i>=0; i--)
+ if(!is_leaf(node->child[i]))
+ {
+ if(node->child[i])
+ {
+ hit |= dfs_raycast(node->child[i], isec);
+ if(hit && isec->mode == RE_RAY_SHADOW) return hit;
+ }
+ }
+ else
+ {
+ hit |= RE_rayobject_intersect( (RayObject*)node->child[i], isec);
+ if(hit && isec->mode == RE_RAY_SHADOW) return hit;
+ }
+ }
+ }
+ return hit;
+}
+*/
+
+#endif
--- /dev/null
+/**
+ * $Id$
+ *
+ * ***** 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) 2009 Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): André Pinto.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+#include <assert.h>
+#include <stdio.h>
+
+#include "MEM_guardedalloc.h"
+#include "BKE_utildefines.h"
+#include "BLI_arithb.h"
+#include "RE_raytrace.h"
+#include "rayobject_rtbuild.h"
+#include "rayobject.h"
+
+#define BIH_NCHILDS 4
+typedef struct BIHTree BIHTree;
+
+static int bih_intersect(BIHTree *obj, Isect *isec);
+static void bih_add(BIHTree *o, RayObject *ob);
+static void bih_done(BIHTree *o);
+static void bih_free(BIHTree *o);
+static void bih_bb(BIHTree *o, float *min, float *max);
+
+static RayObjectAPI bih_api =
+{
+ (RE_rayobject_raycast_callback) bih_intersect,
+ (RE_rayobject_add_callback) bih_add,
+ (RE_rayobject_done_callback) bih_done,
+ (RE_rayobject_free_callback) bih_free,
+ (RE_rayobject_merge_bb_callback)bih_bb
+};
+
+typedef struct BIHNode BIHNode;
+struct BIHNode
+{
+ BIHNode *child[BIH_NCHILDS];
+ float bi[BIH_NCHILDS][2];
+ int split_axis;
+};
+
+struct BIHTree
+{
+ RayObject rayobj;
+
+ BIHNode *root;
+
+ BIHNode *node_alloc, *node_next;
+ RTBuilder *builder;
+
+ float bb[2][3];
+};
+
+
+RayObject *RE_rayobject_bih_create(int size)
+{
+ BIHTree *obj= (BIHTree*)MEM_callocN(sizeof(BIHTree), "BIHTree");
+ assert( RayObject_isAligned(obj) ); /* RayObject API assumes real data to be 4-byte aligned */
+
+ obj->rayobj.api = &bih_api;
+ obj->root = NULL;
+
+ obj->node_alloc = obj->node_next = NULL;
+ obj->builder = rtbuild_create( size );
+
+ return RayObject_unalignRayAPI((RayObject*) obj);
+}
+
+static void bih_free(BIHTree *obj)
+{
+ if(obj->builder)
+ rtbuild_free(obj->builder);
+
+ if(obj->node_alloc)
+ MEM_freeN(obj->node_alloc);
+
+ MEM_freeN(obj);
+}
+
+static void bih_bb(BIHTree *obj, float *min, float *max)
+{
+ DO_MIN(obj->bb[0], min);
+ DO_MAX(obj->bb[1], max);
+}
+
+/*
+ * Tree transverse
+ */
+static int dfs_raycast(const BIHNode *const node, Isect *isec, float tmin, float tmax)
+{
+ int i;
+ int hit = 0;
+
+ const int *const offset = isec->bv_index + node->split_axis*2;
+
+ //TODO diving heuristic
+ for(i=0; i<BIH_NCHILDS; i++)
+ {
+
+ float t1 = (node->bi[i][offset[0]] - isec->start[node->split_axis]) * isec->idot_axis[node->split_axis];
+ float t2 = (node->bi[i][offset[1]] - isec->start[node->split_axis]) * isec->idot_axis[node->split_axis];
+
+ if(t1 < tmin) t1 = tmin; //t1 = MAX2(t1, tmin);
+ if(t2 > tmax) t2 = tmax; //t2 = MIN2(t2, tmax);
+
+ if(t1 <= t2)
+ {
+ if(RayObject_isAligned(node->child[i]))
+ {
+ if(node->child[i] == 0) break;
+
+ hit |= dfs_raycast(node->child[i], isec, t1, t2);
+ if(hit && isec->mode == RE_RAY_SHADOW) return hit;
+ }
+ else
+ {
+ hit |= RE_rayobject_intersect( (RayObject*)node->child[i], isec);
+ if(hit && isec->mode == RE_RAY_SHADOW) return hit;
+ }
+
+ if(tmax > isec->labda)
+ tmax = isec->labda;
+ }
+ }
+
+ return hit;
+}
+
+static int bih_intersect(BIHTree *obj, Isect *isec)
+{
+ if(RayObject_isAligned(obj->root))
+ return dfs_raycast(obj->root, isec, 0, isec->labda);
+ else
+ return RE_rayobject_intersect( (RayObject*)obj->root, isec);
+}
+
+
+/*
+ * Builds a BIH tree from builder object
+ */
+static void bih_add(BIHTree *obj, RayObject *ob)
+{
+ rtbuild_add( obj->builder, ob );
+}
+
+static BIHNode *bih_new_node(BIHTree *tree, int nid)
+{
+ BIHNode *node = tree->node_alloc + nid - 1;
+ assert(RayObject_isAligned(node));
+ if(node+1 > tree->node_next)
+ tree->node_next = node+1;
+
+ return node;
+}
+
+static int child_id(int pid, int nchild)
+{
+ //N child of node A = A * K + (2 - K) + N, (0 <= N < K)
+ return pid*BIH_NCHILDS+(2-BIH_NCHILDS)+nchild;
+}
+
+static BIHNode *bih_rearrange(BIHTree *tree, RTBuilder *builder, int nid, float *bb)
+{
+ if(rtbuild_size(builder) == 1)
+ {
+ RayObject *child = rtbuild_get_primitive( builder, 0 );
+ assert(!RayObject_isAligned(child));
+
+ INIT_MINMAX(bb, bb+3);
+ RE_rayobject_merge_bb( (RayObject*)child, bb, bb+3);
+
+ return (BIHNode*)child;
+ }
+ else
+ {
+ int i;
+ int nc = rtbuild_mean_split_largest_axis(builder, BIH_NCHILDS);
+ RTBuilder tmp;
+
+ BIHNode *parent = bih_new_node(tree, nid);
+
+ INIT_MINMAX(bb, bb+3);
+ parent->split_axis = builder->split_axis;
+ for(i=0; i<nc; i++)
+ {
+ float cbb[6];
+ parent->child[i] = bih_rearrange( tree, rtbuild_get_child(builder, i, &tmp), child_id(nid,i), cbb );
+
+ parent->bi[i][0] = cbb[parent->split_axis];
+ parent->bi[i][1] = cbb[parent->split_axis+3];
+
+ DO_MIN(cbb , bb);
+ DO_MAX(cbb+3, bb+3);
+ }
+ for(; i<BIH_NCHILDS; i++)
+ {
+ parent->bi[i][0] = 1.0;
+ parent->bi[i][1] = -1.0;
+ parent->child[i] = 0;
+ }
+
+ return parent;
+ }
+}
+
+static void bih_done(BIHTree *obj)
+{
+ int needed_nodes;
+ assert(obj->root == NULL && obj->node_alloc == NULL && obj->builder);
+
+ //TODO exact calculate needed nodes
+ needed_nodes = (rtbuild_size(obj->builder)+1)*2;
+ assert(needed_nodes > 0);
+
+ obj->node_alloc = (BIHNode*)MEM_mallocN( sizeof(BIHNode)*needed_nodes, "BIHTree.Nodes");
+ obj->node_next = obj->node_alloc;
+
+ obj->root = bih_rearrange( obj, obj->builder, 1, (float*)obj->bb );
+
+ rtbuild_free( obj->builder );
+ obj->builder = NULL;
+
+ assert(obj->node_alloc+needed_nodes >= obj->node_next);
+}
+
--- /dev/null
+/**
+ * $Id$
+ *
+ * ***** 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) 2009 Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): André Pinto.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+#include <assert.h>
+
+#include "RE_raytrace.h"
+#include "rayobject_rtbuild.h"
+#include "rayobject.h"
+#include "MEM_guardedalloc.h"
+#include "BKE_utildefines.h"
+#include "BLI_arithb.h"
+#include "BLI_memarena.h"
+#include "bvh.h"
+
+#define BVH_NCHILDS 2
+#define RAY_BB_TEST_COST (0.2f)
+#define DFS_STACK_SIZE 64
+#define DYNAMIC_ALLOC
+
+//#define rtbuild_split rtbuild_mean_split_largest_axis /* objects mean split on the longest axis, childs BB are allowed to overlap */
+//#define rtbuild_split rtbuild_median_split_largest_axis /* space median split on the longest axis, childs BB are allowed to overlap */
+#define rtbuild_split rtbuild_heuristic_object_split /* split objects using heuristic */
+
+struct BVHNode
+{
+ BVHNode *child[BVH_NCHILDS];
+ float bb[6];
+ int split_axis;
+};
+
+struct BVHTree
+{
+ RayObject rayobj;
+
+ BVHNode *root;
+
+ MemArena *node_arena;
+
+ float cost;
+ RTBuilder *builder;
+};
+
+
+/*
+ * Push nodes (used on dfs)
+ */
+template<class Node>
+inline static void bvh_node_push_childs(Node *node, Isect *isec, Node **stack, int &stack_pos)
+{
+ //push nodes in reverse visit order
+ if(isec->idot_axis[node->split_axis] < 0.0f)
+ {
+ int i;
+ for(i=0; i<BVH_NCHILDS; i++)
+ if(node->child[i] == 0)
+ break;
+ else
+ stack[stack_pos++] = node->child[i];
+ }
+ else
+ {
+ int i;
+ for(i=BVH_NCHILDS-1; i>=0; i--)
+ if(node->child[i] != 0)
+ stack[stack_pos++] = node->child[i];
+ }
+}
+
+/*
+ * BVH done
+ */
+static BVHNode *bvh_new_node(BVHTree *tree, int nid)
+{
+ BVHNode *node = (BVHNode*)BLI_memarena_alloc(tree->node_arena, sizeof(BVHNode));
+ return node;
+}
+
+static int child_id(int pid, int nchild)
+{
+ //N child of node A = A * K + (2 - K) + N, (0 <= N < K)
+ return pid*BVH_NCHILDS+(2-BVH_NCHILDS)+nchild;
+}
+
+
+static BVHNode *bvh_rearrange(BVHTree *tree, RTBuilder *builder, int nid, float *cost)
+{
+ *cost = 0;
+ if(rtbuild_size(builder) == 0)
+ return 0;
+
+ if(rtbuild_size(builder) == 1)
+ {
+ RayObject *child = rtbuild_get_primitive( builder, 0 );
+
+ if(RayObject_isRayFace(child))
+ {
+ int i;
+ BVHNode *parent = bvh_new_node(tree, nid);
+ parent->split_axis = 0;
+
+ INIT_MINMAX(parent->bb, parent->bb+3);
+
+ for(i=0; i<1; i++)
+ {
+ parent->child[i] = (BVHNode*)rtbuild_get_primitive( builder, i );
+ bvh_node_merge_bb(parent->child[i], parent->bb, parent->bb+3);
+ }
+ for(; i<BVH_NCHILDS; i++)
+ parent->child[i] = 0;
+
+ *cost = RE_rayobject_cost(child)+RAY_BB_TEST_COST;
+ return parent;
+ }
+ else
+ {
+ assert(!RayObject_isAligned(child));
+ //Its a sub-raytrace structure, assume it has it own raycast
+ //methods and adding a Bounding Box arround is unnecessary
+
+ *cost = RE_rayobject_cost(child);
+ return (BVHNode*)child;
+ }
+ }
+ else
+ {
+ int i;
+ RTBuilder tmp;
+ BVHNode *parent = bvh_new_node(tree, nid);
+ int nc = rtbuild_split(builder, BVH_NCHILDS);
+
+
+ INIT_MINMAX(parent->bb, parent->bb+3);
+ parent->split_axis = builder->split_axis;
+ for(i=0; i<nc; i++)
+ {
+ float cbb[6];
+ float tcost;
+ parent->child[i] = bvh_rearrange( tree, rtbuild_get_child(builder, i, &tmp), child_id(nid,i), &tcost );
+
+ INIT_MINMAX(cbb, cbb+3);
+ bvh_node_merge_bb(parent->child[i], cbb, cbb+3);
+ DO_MIN(cbb, parent->bb);
+ DO_MAX(cbb+3, parent->bb+3);
+
+ *cost += tcost*bb_area(cbb, cbb+3);
+ }
+ for(; i<BVH_NCHILDS; i++)
+ parent->child[i] = 0;
+
+ *cost /= bb_area(parent->bb, parent->bb+3);
+ *cost += nc*RAY_BB_TEST_COST;
+ return parent;
+ }
+
+ assert(false);
+}
+
+template<>
+void bvh_done<BVHTree>(BVHTree *obj)
+{
+ int needed_nodes = (rtbuild_size(obj->builder)+1)*2;
+ if(needed_nodes > BLI_MEMARENA_STD_BUFSIZE)
+ needed_nodes = BLI_MEMARENA_STD_BUFSIZE;
+
+ obj->node_arena = BLI_memarena_new(needed_nodes);
+ BLI_memarena_use_malloc(obj->node_arena);
+
+
+ obj->root = bvh_rearrange( obj, obj->builder, 1, &obj->cost );
+
+ rtbuild_free( obj->builder );
+ obj->builder = NULL;
+}
+
+template<>
+int bvh_intersect<BVHTree>(BVHTree *obj, Isect* isec)
+{
+ if(RayObject_isAligned(obj->root))
+ return bvh_node_stack_raycast<BVHNode,64,true>(obj->root, isec);
+ else
+ return RE_rayobject_intersect( (RayObject*) obj->root, isec );
+}
+
+
+/* the cast to pointer function is needed to workarround gcc bug: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11407 */
+static RayObjectAPI bvh_api =
+{
+ (RE_rayobject_raycast_callback) ((int(*)(BVHTree*,Isect*)) &bvh_intersect<BVHTree>),
+ (RE_rayobject_add_callback) ((void(*)(BVHTree*,RayObject*)) &bvh_add<BVHTree>),
+ (RE_rayobject_done_callback) ((void(*)(BVHTree*)) &bvh_done<BVHTree>),
+ (RE_rayobject_free_callback) ((void(*)(BVHTree*)) &bvh_free<BVHTree>),
+ (RE_rayobject_merge_bb_callback)((void(*)(BVHTree*,float*,float*)) &bvh_bb<BVHTree>),
+ (RE_rayobject_cost_callback) ((float(*)(BVHTree*)) &bvh_cost<BVHTree>)
+};
+
+
+RayObject *RE_rayobject_bvh_create(int size)
+{
+ BVHTree *obj= (BVHTree*)MEM_callocN(sizeof(BVHTree), "BVHTree");
+ assert( RayObject_isAligned(obj) ); /* RayObject API assumes real data to be 4-byte aligned */
+
+ obj->rayobj.api = &bvh_api;
+ obj->root = NULL;
+
+ obj->node_arena = NULL;
+ obj->builder = rtbuild_create( size );
+
+ return RayObject_unalignRayAPI((RayObject*) obj);
+}
--- /dev/null
+/**
+ * $Id$
+ *
+ * ***** 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) 2009 Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): André Pinto.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+#define HINT_RECURSE 1
+#define HINT_ACCEPT 0
+#define HINT_DISCARD -1
+
+struct HintBB
+{
+ float bb[6];
+};
+
+inline int hint_test_bb(HintBB *obj, float *Nmin, float *Nmax)
+{
+ if(bb_fits_inside( Nmin, Nmax, obj->bb, obj->bb+3 ) )
+ return HINT_RECURSE;
+ else
+ return HINT_ACCEPT;
+}
+/*
+struct HintFrustum
+{
+ float co[3];
+ float no[4][3];
+};
+
+inline int hint_test_bb(HintFrustum &obj, float *Nmin, float *Nmax)
+{
+ //if frustum inside BB
+ {
+ return HINT_RECURSE;
+ }
+ //if BB outside frustum
+ {
+ return HINT_DISCARD;
+ }
+
+ return HINT_ACCEPT;
+}
+*/
--- /dev/null
+#include <assert.h>
+#include <math.h>
+#include <stdlib.h>
+#include <algorithm>
+
+#include "rayobject_rtbuild.h"
+#include "MEM_guardedalloc.h"
+#include "BLI_arithb.h"
+#include "BKE_utildefines.h"
+
+static bool selected_node(RTBuilder::Object *node)
+{
+ return node->selected;
+}
+
+static void rtbuild_init(RTBuilder *b)
+{
+ b->split_axis = -1;
+ b->primitives.begin = 0;
+ b->primitives.end = 0;
+ b->primitives.maxsize = 0;
+
+ for(int i=0; i<RTBUILD_MAX_CHILDS; i++)
+ b->child_offset[i] = 0;
+
+ for(int i=0; i<3; i++)
+ b->sorted_begin[i] = b->sorted_end[i] = 0;
+
+ INIT_MINMAX(b->bb, b->bb+3);
+}
+
+RTBuilder* rtbuild_create(int size)
+{
+ RTBuilder *builder = (RTBuilder*) MEM_mallocN( sizeof(RTBuilder), "RTBuilder" );
+ RTBuilder::Object *memblock= (RTBuilder::Object*)MEM_mallocN( sizeof(RTBuilder::Object)*size,"RTBuilder.objects");
+
+
+ rtbuild_init(builder);
+
+ builder->primitives.begin = builder->primitives.end = memblock;
+ builder->primitives.maxsize = size;
+
+ for(int i=0; i<3; i++)
+ {
+ builder->sorted_begin[i] = (RTBuilder::Object**)MEM_mallocN( sizeof(RTBuilder::Object*)*size,"RTBuilder.sorted_objects");
+ builder->sorted_end[i] = builder->sorted_begin[i];
+ }
+
+
+ return builder;
+}
+
+void rtbuild_free(RTBuilder *b)
+{
+ if(b->primitives.begin) MEM_freeN(b->primitives.begin);
+
+ for(int i=0; i<3; i++)
+ if(b->sorted_begin[i])
+ MEM_freeN(b->sorted_begin[i]);
+
+ MEM_freeN(b);
+}
+
+void rtbuild_add(RTBuilder *b, RayObject *o)
+{
+ assert( b->primitives.begin + b->primitives.maxsize != b->primitives.end );
+
+ b->primitives.end->obj = o;
+ b->primitives.end->cost = RE_rayobject_cost(o);
+
+ INIT_MINMAX(b->primitives.end->bb, b->primitives.end->bb+3);
+ RE_rayobject_merge_bb(o, b->primitives.end->bb, b->primitives.end->bb+3);
+
+ for(int i=0; i<3; i++)
+ {
+ *(b->sorted_end[i]) = b->primitives.end;
+ b->sorted_end[i]++;
+ }
+ b->primitives.end++;
+}
+
+int rtbuild_size(RTBuilder *b)
+{
+ return b->sorted_end[0] - b->sorted_begin[0];
+}
+
+
+template<class Obj,int Axis>
+static bool obj_bb_compare(const Obj &a, const Obj &b)
+{
+ if(a->bb[Axis] != b->bb[Axis])
+ return a->bb[Axis] < b->bb[Axis];
+ return a->obj < b->obj;
+}
+
+template<class Item>
+static void object_sort(Item *begin, Item *end, int axis)
+{
+ if(axis == 0) return std::sort(begin, end, obj_bb_compare<Item,0> );
+ if(axis == 1) return std::sort(begin, end, obj_bb_compare<Item,1> );
+ if(axis == 2) return std::sort(begin, end, obj_bb_compare<Item,2> );
+ assert(false);
+}
+
+void rtbuild_done(RTBuilder *b)
+{
+ for(int i=0; i<3; i++)
+ if(b->sorted_begin[i])
+ object_sort( b->sorted_begin[i], b->sorted_end[i], i );
+}
+
+RayObject* rtbuild_get_primitive(RTBuilder *b, int index)
+{
+ return b->sorted_begin[0][index]->obj;
+}
+
+RTBuilder* rtbuild_get_child(RTBuilder *b, int child, RTBuilder *tmp)
+{
+ rtbuild_init( tmp );
+
+ for(int i=0; i<3; i++)
+ if(b->sorted_begin[i])
+ {
+ tmp->sorted_begin[i] = b->sorted_begin[i] + b->child_offset[child ];
+ tmp->sorted_end [i] = b->sorted_begin[i] + b->child_offset[child+1];
+ }
+ else
+ {
+ tmp->sorted_begin[i] = 0;
+ tmp->sorted_end [i] = 0;
+ }
+
+ return tmp;
+}
+
+void rtbuild_calc_bb(RTBuilder *b)
+{
+ if(b->bb[0] == 1.0e30f)
+ {
+ for(RTBuilder::Object **index = b->sorted_begin[0]; index != b->sorted_end[0]; index++)
+ RE_rayobject_merge_bb( (*index)->obj , b->bb, b->bb+3);
+ }
+}
+
+void rtbuild_merge_bb(RTBuilder *b, float *min, float *max)
+{
+ rtbuild_calc_bb(b);
+ DO_MIN(b->bb, min);
+ DO_MAX(b->bb+3, max);
+}
+
+/*
+int rtbuild_get_largest_axis(RTBuilder *b)
+{
+ rtbuild_calc_bb(b);
+ return bb_largest_axis(b->bb, b->bb+3);
+}
+
+//Left balanced tree
+int rtbuild_mean_split(RTBuilder *b, int nchilds, int axis)
+{
+ int i;
+ int mleafs_per_child, Mleafs_per_child;
+ int tot_leafs = rtbuild_size(b);
+ int missing_leafs;
+
+ long long s;
+
+ assert(nchilds <= RTBUILD_MAX_CHILDS);
+
+ //TODO optimize calc of leafs_per_child
+ for(s=nchilds; s<tot_leafs; s*=nchilds);
+ Mleafs_per_child = s/nchilds;
+ mleafs_per_child = Mleafs_per_child/nchilds;
+
+ //split min leafs per child
+ b->child_offset[0] = 0;
+ for(i=1; i<=nchilds; i++)
+ b->child_offset[i] = mleafs_per_child;
+
+ //split remaining leafs
+ missing_leafs = tot_leafs - mleafs_per_child*nchilds;
+ for(i=1; i<=nchilds; i++)
+ {
+ if(missing_leafs > Mleafs_per_child - mleafs_per_child)
+ {
+ b->child_offset[i] += Mleafs_per_child - mleafs_per_child;
+ missing_leafs -= Mleafs_per_child - mleafs_per_child;
+ }
+ else
+ {
+ b->child_offset[i] += missing_leafs;
+ missing_leafs = 0;
+ break;
+ }
+ }
+
+ //adjust for accumulative offsets
+ for(i=1; i<=nchilds; i++)
+ b->child_offset[i] += b->child_offset[i-1];
+
+ //Count created childs
+ for(i=nchilds; b->child_offset[i] == b->child_offset[i-1]; i--);
+ split_leafs(b, b->child_offset, i, axis);
+
+ assert( b->child_offset[0] == 0 && b->child_offset[i] == tot_leafs );
+ return i;
+}
+
+
+int rtbuild_mean_split_largest_axis(RTBuilder *b, int nchilds)
+{
+ int axis = rtbuild_get_largest_axis(b);
+ return rtbuild_mean_split(b, nchilds, axis);
+}
+*/
+
+/*
+ * "separators" is an array of dim NCHILDS-1
+ * and indicates where to cut the childs
+ */
+/*
+int rtbuild_median_split(RTBuilder *b, float *separators, int nchilds, int axis)
+{
+ int size = rtbuild_size(b);
+
+ assert(nchilds <= RTBUILD_MAX_CHILDS);
+ if(size <= nchilds)
+ {
+ return rtbuild_mean_split(b, nchilds, axis);
+ }
+ else
+ {
+ int i;
+
+ b->split_axis = axis;
+
+ //Calculate child offsets
+ b->child_offset[0] = 0;
+ for(i=0; i<nchilds-1; i++)
+ b->child_offset[i+1] = split_leafs_by_plane(b, b->child_offset[i], size, separators[i]);
+ b->child_offset[nchilds] = size;
+
+ for(i=0; i<nchilds; i++)
+ if(b->child_offset[i+1] - b->child_offset[i] == size)
+ return rtbuild_mean_split(b, nchilds, axis);
+
+ return nchilds;
+ }
+}
+
+int rtbuild_median_split_largest_axis(RTBuilder *b, int nchilds)
+{
+ int la, i;
+ float separators[RTBUILD_MAX_CHILDS];
+
+ rtbuild_calc_bb(b);
+
+ la = bb_largest_axis(b->bb,b->bb+3);
+ for(i=1; i<nchilds; i++)
+ separators[i-1] = (b->bb[la+3]-b->bb[la])*i / nchilds;
+
+ return rtbuild_median_split(b, separators, nchilds, la);
+}
+*/
+
+//Heuristics Object Splitter
+
+
+struct SweepCost
+{
+ float bb[6];
+ float cost;
+};
+
+/* Object Surface Area Heuristic splitter */
+int rtbuild_heuristic_object_split(RTBuilder *b, int nchilds)
+{
+ int size = rtbuild_size(b);
+ assert(nchilds == 2);
+ assert(size > 1);
+ int baxis = -1, boffset = 0;
+
+ if(size > nchilds)
+ {
+ float bcost = FLT_MAX;
+ baxis = -1, boffset = size/2;
+
+ SweepCost *sweep = (SweepCost*)MEM_mallocN( sizeof(SweepCost)*size, "RTBuilder.HeuristicSweep" );
+
+ for(int axis=0; axis<3; axis++)
+ {
+ SweepCost sweep_left;
+
+ RTBuilder::Object **obj = b->sorted_begin[axis];
+
+// float right_cost = 0;
+ for(int i=size-1; i>=0; i--)
+ {
+ if(i == size-1)
+ {
+ VECCOPY(sweep[i].bb, obj[i]->bb);
+ VECCOPY(sweep[i].bb+3, obj[i]->bb+3);
+ sweep[i].cost = obj[i]->cost;
+ }
+ else
+ {
+ sweep[i].bb[0] = MIN2(obj[i]->bb[0], sweep[i+1].bb[0]);
+ sweep[i].bb[1] = MIN2(obj[i]->bb[1], sweep[i+1].bb[1]);
+ sweep[i].bb[2] = MIN2(obj[i]->bb[2], sweep[i+1].bb[2]);
+ sweep[i].bb[3] = MAX2(obj[i]->bb[3], sweep[i+1].bb[3]);
+ sweep[i].bb[4] = MAX2(obj[i]->bb[4], sweep[i+1].bb[4]);
+ sweep[i].bb[5] = MAX2(obj[i]->bb[5], sweep[i+1].bb[5]);
+ sweep[i].cost = obj[i]->cost + sweep[i+1].cost;
+ }
+// right_cost += obj[i]->cost;
+ }
+
+ sweep_left.bb[0] = obj[0]->bb[0];
+ sweep_left.bb[1] = obj[0]->bb[1];
+ sweep_left.bb[2] = obj[0]->bb[2];
+ sweep_left.bb[3] = obj[0]->bb[3];
+ sweep_left.bb[4] = obj[0]->bb[4];
+ sweep_left.bb[5] = obj[0]->bb[5];
+ sweep_left.cost = obj[0]->cost;
+
+// right_cost -= obj[0]->cost; if(right_cost < 0) right_cost = 0;
+
+ for(int i=1; i<size; i++)
+ {
+ //Worst case heuristic (cost of each child is linear)
+ float hcost, left_side, right_side;
+
+ left_side = bb_area(sweep_left.bb, sweep_left.bb+3)*(sweep_left.cost+logf(i));
+ right_side= bb_area(sweep[i].bb, sweep[i].bb+3)*(sweep[i].cost+logf(size-i));
+ hcost = left_side+right_side;
+
+ assert(left_side >= 0);
+ assert(right_side >= 0);
+
+ if(left_side > bcost) break; //No way we can find a better heuristic in this axis
+
+ assert(hcost >= 0);
+ if( hcost < bcost
+ || (hcost == bcost && axis < baxis)) //this makes sure the tree built is the same whatever is the order of the sorting axis
+ {
+ bcost = hcost;
+ baxis = axis;
+ boffset = i;
+ }
+ DO_MIN( obj[i]->bb, sweep_left.bb );
+ DO_MAX( obj[i]->bb+3, sweep_left.bb+3 );
+
+ sweep_left.cost += obj[i]->cost;
+// right_cost -= obj[i]->cost; if(right_cost < 0) right_cost = 0;
+ }
+
+ assert(baxis >= 0 && baxis < 3);
+ }
+
+
+ MEM_freeN(sweep);
+ }
+ else if(size == 2)
+ {
+ baxis = 0;
+ boffset = 1;
+ }
+ else if(size == 1)
+ {
+ b->child_offset[0] = 0;
+ b->child_offset[1] = 1;
+ return 1;
+ }
+
+ b->child_offset[0] = 0;
+ b->child_offset[1] = boffset;
+ b->child_offset[2] = size;
+
+
+ /* Adjust sorted arrays for childs */
+ for(int i=0; i<boffset; i++) b->sorted_begin[baxis][i]->selected = true;
+ for(int i=boffset; i<size; i++) b->sorted_begin[baxis][i]->selected = false;
+ for(int i=0; i<3; i++)
+ std::stable_partition( b->sorted_begin[i], b->sorted_end[i], selected_node );
+
+ return nchilds;
+}
+
+/*
+ * Helper code
+ * PARTITION code / used on mean-split
+ * basicly this a std::nth_element (like on C++ STL algorithm)
+ */
+/*
+static void split_leafs(RTBuilder *b, int *nth, int partitions, int split_axis)
+{
+ int i;
+ b->split_axis = split_axis;
+
+ for(i=0; i < partitions-1; i++)
+ {
+ assert(nth[i] < nth[i+1] && nth[i+1] < nth[partitions]);
+
+ if(split_axis == 0) std::nth_element(b, nth[i], nth[i+1], nth[partitions], obj_bb_compare<RTBuilder::Object,0>);
+ if(split_axis == 1) std::nth_element(b, nth[i], nth[i+1], nth[partitions], obj_bb_compare<RTBuilder::Object,1>);
+ if(split_axis == 2) std::nth_element(b, nth[i], nth[i+1], nth[partitions], obj_bb_compare<RTBuilder::Object,2>);
+ }
+}
+*/
+
+/*
+ * Bounding Box utils
+ */
+float bb_volume(float *min, float *max)
+{
+ return (max[0]-min[0])*(max[1]-min[1])*(max[2]-min[2]);
+}
+
+float bb_area(float *min, float *max)
+{
+ float sub[3], a;
+ sub[0] = max[0]-min[0];
+ sub[1] = max[1]-min[1];
+ sub[2] = max[2]-min[2];
+
+ a = (sub[0]*sub[1] + sub[0]*sub[2] + sub[1]*sub[2])*2;
+ assert(a >= 0.0);
+ return a;
+}
+
+int bb_largest_axis(float *min, float *max)
+{
+ float sub[3];
+
+ sub[0] = max[0]-min[0];
+ sub[1] = max[1]-min[1];
+ sub[2] = max[2]-min[2];
+ if(sub[0] > sub[1])
+ {
+ if(sub[0] > sub[2])
+ return 0;
+ else
+ return 2;
+ }
+ else
+ {
+ if(sub[1] > sub[2])
+ return 1;
+ else
+ return 2;
+ }
+}
+
+int bb_fits_inside(float *outer_min, float *outer_max, float *inner_min, float *inner_max)
+{
+ int i;
+ for(i=0; i<3; i++)
+ if(outer_min[i] > inner_min[i]) return 0;
+
+ for(i=0; i<3; i++)
+ if(outer_max[i] < inner_max[i]) return 0;
+
+ return 1;
+}
--- /dev/null
+/**
+ * $Id$
+ *
+ * ***** 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) 2009 Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): André Pinto.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+#ifndef RE_RAYOBJECT_RTBUILD_H
+#define RE_RAYOBJECT_RTBUILD_H
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include "rayobject.h"
+
+
+/*
+ * Ray Tree Builder
+ * this structs helps building any type of tree
+ * it contains several methods to organiza/split nodes
+ * allowing to create a given tree on the fly.
+ *
+ * Idea is that other trees BVH, BIH can use this code to
+ * generate with simple calls, and then convert to the theirs
+ * specific structure on the fly.
+ */
+#define RTBUILD_MAX_CHILDS 32
+
+
+typedef struct RTBuilder
+{
+ struct Object
+ {
+ RayObject *obj;
+ float cost;
+ float bb[6];
+ int selected;
+ };
+
+ /* list to all primitives added in this tree */
+ struct
+ {
+ Object *begin, *end;
+ int maxsize;
+ } primitives;
+
+ /* sorted list of rayobjects */
+ struct Object **sorted_begin[3], **sorted_end[3];
+
+ /* axis used (if any) on the split method */
+ int split_axis;
+
+ /* child partitions calculated during splitting */
+ int child_offset[RTBUILD_MAX_CHILDS+1];
+
+// int child_sorted_axis; /* -1 if not sorted */
+
+ float bb[6];
+
+} RTBuilder;
+
+/* used during creation */
+RTBuilder* rtbuild_create(int size);
+void rtbuild_free(RTBuilder *b);
+void rtbuild_add(RTBuilder *b, RayObject *o);
+void rtbuild_done(RTBuilder *b);
+void rtbuild_merge_bb(RTBuilder *b, float *min, float *max);
+int rtbuild_size(RTBuilder *b);
+
+RayObject* rtbuild_get_primitive(RTBuilder *b, int offset);
+
+/* used during tree reorganization */
+RTBuilder* rtbuild_get_child(RTBuilder *b, int child, RTBuilder *tmp);
+
+/* Calculates child partitions and returns number of efectively needed partitions */
+int rtbuild_get_largest_axis(RTBuilder *b);
+
+//Object partition
+int rtbuild_mean_split(RTBuilder *b, int nchilds, int axis);
+int rtbuild_mean_split_largest_axis(RTBuilder *b, int nchilds);
+
+int rtbuild_heuristic_object_split(RTBuilder *b, int nchilds);
+
+//Space partition
+int rtbuild_median_split(RTBuilder *b, float *separators, int nchilds, int axis);
+int rtbuild_median_split_largest_axis(RTBuilder *b, int nchilds);
+
+
+/* bb utils */
+float bb_area(float *min, float *max);
+float bb_volume(float *min, float *max);
+int bb_largest_axis(float *min, float *max);
+int bb_fits_inside(float *outer_min, float *outer_max, float *inner_min, float *inner_max); /* only returns 0 if merging inner and outerbox would create a box larger than outer box */
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
--- /dev/null
+/**
+ * $Id$
+ *
+ * ***** 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) 2009 Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): André Pinto.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+#define RE_USE_HINT (0)
+static int tot_pushup = 0;
+static int tot_pushdown = 0;
+static int tot_hints = 0;
+
+
+extern "C"
+{
+#include <assert.h>
+#include "MEM_guardedalloc.h"
+#include "BKE_utildefines.h"
+#include "BLI_arithb.h"
+#include "BLI_memarena.h"
+#include "RE_raytrace.h"
+#include "rayobject_rtbuild.h"
+#include "rayobject.h"
+};
+
+#include "rayobject_hint.h"
+#include "reorganize.h"
+#include "bvh.h"
+#include "svbvh.h"
+#include <queue>
+
+
+#define RE_DO_HINTS (0)
+#define RAY_BB_TEST_COST (0.2f)
+#define DFS_STACK_SIZE 256
+//#define DYNAMIC_ALLOC_BB
+
+
+//#define rtbuild_split rtbuild_mean_split_largest_axis /* objects mean split on the longest axis, childs BB are allowed to overlap */
+//#define rtbuild_split rtbuild_median_split_largest_axis /* space median split on the longest axis, childs BB are allowed to overlap */
+#define rtbuild_split rtbuild_heuristic_object_split /* split objects using heuristic */
+
+struct VBVHNode
+{
+#ifdef DYNAMIC_ALLOC_BB
+ float *bb;
+#else
+ float bb[6];
+#endif
+
+ VBVHNode *child;
+ VBVHNode *sibling;
+};
+
+struct VBVHTree
+{
+ RayObject rayobj;
+
+ SVBVHNode *root;
+
+ MemArena *node_arena;
+
+ float cost;
+ RTBuilder *builder;
+};
+
+
+
+
+template<class Tree,class OldNode>
+struct Reorganize_VBVH
+{
+ Tree *tree;
+
+ Reorganize_VBVH(Tree *t)
+ {
+ tree = t;
+ }
+
+ VBVHNode *create_node()
+ {
+ VBVHNode *node = (VBVHNode*)BLI_memarena_alloc(tree->node_arena, sizeof(VBVHNode));
+ return node;
+ }
+
+ void copy_bb(VBVHNode *node, OldNode *old)
+ {
+ std::copy( old->bb, old->bb+6, node->bb );
+ }
+
+ VBVHNode *transform(OldNode *old)
+ {
+ if(is_leaf(old))
+ return (VBVHNode*)old;
+
+ VBVHNode *node = create_node();
+ VBVHNode **child_ptr = &node->child;
+ node->sibling = 0;
+
+ copy_bb(node,old);
+
+ for(OldNode *o_child = old->child; o_child; o_child = o_child->sibling)
+ {
+ VBVHNode *n_child = transform(o_child);
+ *child_ptr = n_child;
+ if(is_leaf(n_child)) return node;
+ child_ptr = &n_child->sibling;
+ }
+ *child_ptr = 0;
+
+ return node;
+ }
+};
+
+
+/*
+ * Push nodes (used on dfs)
+ */
+template<class Node>
+inline static void bvh_node_push_childs(Node *node, Isect *isec, Node **stack, int &stack_pos)
+{
+ Node *child = node->child;
+
+ if(is_leaf(child))
+ {
+ stack[stack_pos++] = child;
+ }
+ else
+ {
+ while(child)
+ {
+ //Skips BB tests on primitives
+/*
+ if(is_leaf(child->child))
+ stack[stack_pos++] = child->child;
+ else
+*/
+ stack[stack_pos++] = child;
+
+ child = child->sibling;
+ }
+ }
+}
+
+/*
+ * BVH done
+ */
+static VBVHNode *bvh_new_node(VBVHTree *tree)
+{
+ VBVHNode *node = (VBVHNode*)BLI_memarena_alloc(tree->node_arena, sizeof(VBVHNode));
+
+ if( (((intptr_t)node) & (0x0f)) != 0 )
+ {
+ puts("WRONG!");
+ printf("%08x\n", (intptr_t)node);
+ }
+ node->sibling = NULL;
+ node->child = NULL;
+
+#ifdef DYNAMIC_ALLOC_BB
+ node->bb = (float*)BLI_memarena_alloc(tree->node_arena, 6*sizeof(float));
+#endif
+ assert(RayObject_isAligned(node));
+ return node;
+}
+
+
+
+template<class Node>
+int count_childs(Node *parent)
+{
+ int n = 0;
+ for(Node *i = parent->child; i; i = i->sibling)
+ {
+ n++;
+ if(is_leaf(i))
+ break;
+ }
+
+ return n;
+}
+
+template<class Node>
+void append_sibling(Node *node, Node *sibling)
+{
+ while(node->sibling)
+ node = node->sibling;
+
+ node->sibling = sibling;
+}
+
+
+template<class Tree, class Node, class Builder>
+Node *bvh_rearrange(Tree *tree, Builder *builder)
+{
+
+ int size = rtbuild_size(builder);
+ if(size == 1)
+ {
+ Node *node = bvh_new_node(tree);
+ INIT_MINMAX(node->bb, node->bb+3);
+ rtbuild_merge_bb(builder, node->bb, node->bb+3);
+ node->child = (VBVHNode*) rtbuild_get_primitive( builder, 0 );
+ return node;
+ }
+ else
+ {
+ Node *node = bvh_new_node(tree);
+
+ INIT_MINMAX(node->bb, node->bb+3);
+ rtbuild_merge_bb(builder, node->bb, node->bb+3);
+
+ Node **child = &node->child;
+
+ int nc = rtbuild_split(builder, 2);
+ assert(nc == 2);
+ for(int i=0; i<nc; i++)
+ {
+ Builder tmp;
+ rtbuild_get_child(builder, i, &tmp);
+
+ *child = bvh_rearrange<Tree,Node,Builder>(tree, &tmp);
+ child = &((*child)->sibling);
+ }
+
+ *child = 0;
+ return node;
+ }
+}
+
+template<>
+void bvh_done<VBVHTree>(VBVHTree *obj)
+{
+ rtbuild_done(obj->builder);
+
+ int needed_nodes = (rtbuild_size(obj->builder)+1)*2;
+ if(needed_nodes > BLI_MEMARENA_STD_BUFSIZE)
+ needed_nodes = BLI_MEMARENA_STD_BUFSIZE;
+
+ MemArena *arena1 = BLI_memarena_new(needed_nodes);
+ BLI_memarena_use_malloc(arena1);
+ BLI_memarena_use_align(arena1, 16);
+ obj->node_arena = arena1;
+
+ VBVHNode *root = bvh_rearrange<VBVHTree,VBVHNode,RTBuilder>( obj, obj->builder );
+ reorganize(root);
+ remove_useless(root, &root);
+ printf("refit: %f\n", bvh_refit(root) );
+
+ pushup(root);
+ pushdown(root);
+ pushup_simd<VBVHNode,4>(root);
+
+ //Memory re-organize
+ if(0)
+ {
+ MemArena *arena2 = BLI_memarena_new(needed_nodes);
+ BLI_memarena_use_malloc(arena2);
+ BLI_memarena_use_align(arena2, 16);
+ obj->node_arena = arena2;
+ root = Reorganize_VBVH<VBVHTree,VBVHNode>(obj).transform(root);
+
+ BLI_memarena_free(arena1);
+ }
+
+ if(1)
+ {
+ MemArena *arena2 = BLI_memarena_new(needed_nodes);
+ BLI_memarena_use_malloc(arena2);
+ BLI_memarena_use_align(arena2, 16);
+ obj->node_arena = arena2;
+ obj->root = Reorganize_SVBVH<VBVHTree,VBVHNode>(obj).transform(root);
+
+ BLI_memarena_free(arena1);
+ }
+/*
+ {
+ obj->root = root;
+ }
+*/
+
+ obj->cost = 1.0;
+
+ rtbuild_free( obj->builder );
+ obj->builder = NULL;
+}
+
+template<int StackSize>
+int intersect(VBVHTree *obj, Isect* isec)
+{
+/*
+ if(RE_DO_HINTS && isec->hint)
+ {
+ LCTSHint *lcts = (LCTSHint*)isec->hint;
+ isec->hint = 0;
+
+ int hit = 0;
+ for(int i=0; i<lcts->size; i++)
+ {
+ VBVHNode *node = (VBVHNode*)lcts->stack[i];
+ if(RayObject_isAligned(node))
+ hit |= bvh_node_stack_raycast<VBVHNode,StackSize,true>(node, isec);
+ else
+ hit |= RE_rayobject_intersect( (RayObject*)node, isec );
+
+ if(hit && isec->mode == RE_RAY_SHADOW)
+ break;
+ }
+ isec->hint = (RayHint*)lcts;
+ return hit;
+ }
+ else
+*/
+ {
+ if(RayObject_isAligned(obj->root))
+ return bvh_node_stack_raycast<SVBVHNode,StackSize,false>( obj->root, isec);
+ else
+ return RE_rayobject_intersect( (RayObject*) obj->root, isec );
+ }
+}
+
+template<class Node,class HintObject>
+void bvh_dfs_make_hint(Node *node, LCTSHint *hint, int reserve_space, HintObject *hintObject);
+
+template<class Node,class HintObject>
+void bvh_dfs_make_hint_push_siblings(Node *node, LCTSHint *hint, int reserve_space, HintObject *hintObject)
+{
+ if(!RayObject_isAligned(node))
+ hint->stack[hint->size++] = (RayObject*)node;
+ else
+ {
+ if(node->sibling)
+ bvh_dfs_make_hint_push_siblings(node->sibling, hint, reserve_space+1, hintObject);
+
+ bvh_dfs_make_hint(node, hint, reserve_space, hintObject);
+ }
+}
+
+template<class Node,class HintObject>
+void bvh_dfs_make_hint(Node *node, LCTSHint *hint, int reserve_space, HintObject *hintObject)
+{
+ assert( hint->size + reserve_space + 1 <= RE_RAY_LCTS_MAX_SIZE );
+
+ if(is_leaf(node))
+ {
+ hint->stack[hint->size++] = (RayObject*)node;
+ }
+ else
+ {
+ int childs = count_childs(node);
+ if(hint->size + reserve_space + childs <= RE_RAY_LCTS_MAX_SIZE)
+ {
+ int result = hint_test_bb(hintObject, node->bb, node->bb+3);
+ if(result == HINT_RECURSE)
+ {
+ /* We are 100% sure the ray will be pass inside this node */
+ bvh_dfs_make_hint_push_siblings(node->child, hint, reserve_space, hintObject);
+ }
+ else if(result == HINT_ACCEPT)
+ {
+ hint->stack[hint->size++] = (RayObject*)node;
+ }
+ }
+ else
+ {
+ hint->stack[hint->size++] = (RayObject*)node;
+ }
+ }
+}
+
+template<class Tree>
+void bvh_hint_bb(Tree *tree, LCTSHint *hint, float *min, float *max)
+{
+/*
+ if(RE_USE_HINT)
+ {
+ HintBB bb;
+ VECCOPY(bb.bb, min);
+ VECCOPY(bb.bb+3, max);
+
+ hint->size = 0;
+ bvh_dfs_make_hint( tree->root, hint, 0, &bb );
+ tot_hints++;
+ }
+ else
+*/
+ {
+ hint->size = 0;
+ hint->stack[hint->size++] = (RayObject*)tree->root;
+ }
+}
+
+void bfree(VBVHTree *tree)
+{
+ if(tot_pushup + tot_pushdown + tot_hints + tot_moves)
+ {
+ printf("tot pushups: %d\n", tot_pushup);
+ printf("tot pushdowns: %d\n", tot_pushdown);
+ printf("tot moves: %d\n", tot_moves);
+ printf("tot hints created: %d\n", tot_hints);
+ tot_pushup = 0;
+ tot_pushdown = 0;
+ tot_hints = 0;
+ tot_moves = 0;
+ }
+ bvh_free(tree);
+}
+
+/* the cast to pointer function is needed to workarround gcc bug: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11407 */
+template<class Tree,int STACK_SIZE>
+static RayObjectAPI make_api()
+{
+ static RayObjectAPI api =
+ {
+ (RE_rayobject_raycast_callback) ((int(*)(Tree*,Isect*)) &intersect<STACK_SIZE>),
+ (RE_rayobject_add_callback) ((void(*)(Tree*,RayObject*)) &bvh_add<Tree>),
+ (RE_rayobject_done_callback) ((void(*)(Tree*)) &bvh_done<Tree>),
+// (RE_rayobject_free_callback) ((void(*)(Tree*)) &bvh_free<Tree>),
+ (RE_rayobject_free_callback) ((void(*)(Tree*)) &bfree),
+ (RE_rayobject_merge_bb_callback)((void(*)(Tree*,float*,float*)) &bvh_bb<Tree>),
+ (RE_rayobject_cost_callback) ((float(*)(Tree*)) &bvh_cost<Tree>),
+ (RE_rayobject_hint_bb_callback) ((void(*)(Tree*,LCTSHint*,float*,float*)) &bvh_hint_bb<Tree>)
+ };
+
+ return api;
+}
+
+template<class Tree>
+static RayObjectAPI* get_api(int maxstacksize)
+{
+ static RayObjectAPI bvh_api256 = make_api<Tree,1024>();
+
+ if(maxstacksize <= 1024) return &bvh_api256;
+ assert(maxstacksize <= 256);
+ return 0;
+}
+
+RayObject *RE_rayobject_vbvh_create(int size)
+{
+ VBVHTree *obj= (VBVHTree*)MEM_callocN(sizeof(VBVHTree), "VBVHTree");
+ assert( RayObject_isAligned(obj) ); /* RayObject API assumes real data to be 4-byte aligned */
+
+ obj->rayobj.api = get_api<VBVHTree>(DFS_STACK_SIZE);
+ obj->root = NULL;
+
+ obj->node_arena = NULL;
+ obj->builder = rtbuild_create( size );
+
+ return RayObject_unalignRayAPI((RayObject*) obj);
+}
+
+
+
+/* SVBVH */
+template<class HintObject>
+void bvh_dfs_make_hint(VBVHNode *node, LCTSHint *hint, int reserve_space, HintObject *hintObject)
+{
+ return;
+}
+/*
+RayObject *RE_rayobject_svbvh_create(int size)
+{
+ SVBVHTree *obj= (SVBVHTree*)MEM_callocN(sizeof(SVBVHTree), "SVBVHTree");
+ assert( RayObject_isAligned(obj) ); // RayObject API assumes real data to be 4-byte aligned
+
+ obj->rayobj.api = get_api<SVBVHTree>(DFS_STACK_SIZE);
+ obj->root = NULL;
+
+ obj->node_arena = NULL;
+ obj->builder = rtbuild_create( size );
+
+ return RayObject_unalignRayAPI((RayObject*) obj);
+}
+*/
\ No newline at end of file
--- /dev/null
+/**
+ * $Id$
+ *
+ * ***** 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) 2009 Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): André Pinto.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+#include <algorithm>
+#include <queue>
+
+template<class Node>
+bool node_fits_inside(Node *a, Node *b)
+{
+ return bb_fits_inside(b->bb, b->bb+3, a->bb, a->bb+3);
+}
+
+template<class Node>
+void reorganize_find_fittest_parent(Node *tree, Node *node, std::pair<float,Node*> &cost)
+{
+ std::queue<Node*> q;
+ q.push(tree);
+
+ while(!q.empty())
+ {
+ Node *parent = q.front();
+ q.pop();
+
+ if(parent == node) continue;
+ if(node_fits_inside(node, parent) && RayObject_isAligned(parent->child) )
+ {
+ float pcost = bb_area(parent->bb, parent->bb+3);
+ cost = std::min( cost, std::make_pair(pcost,parent) );
+ for(Node *child = parent->child; child; child = child->sibling)
+ q.push(child);
+ }
+ }
+}
+
+static int tot_moves = 0;
+template<class Node>
+void reorganize(Node *root)
+{
+ std::queue<Node*> q;
+
+ q.push(root);
+ while(!q.empty())
+ {
+ Node * node = q.front();
+ q.pop();
+
+ if( RayObject_isAligned(node->child) )
+ {
+ for(Node **prev = &node->child; *prev; )
+ {
+ assert( RayObject_isAligned(*prev) );
+ q.push(*prev);
+
+ std::pair<float,Node*> best(FLT_MAX, root);
+ reorganize_find_fittest_parent( root, *prev, best );
+
+ if(best.second == node)
+ {
+ //Already inside the fitnest BB
+ prev = &(*prev)->sibling;
+ }
+ else
+ {
+ Node *tmp = *prev;
+ *prev = (*prev)->sibling;
+
+ tmp->sibling = best.second->child;
+ best.second->child = tmp;
+
+ tot_moves++;
+ }
+
+
+ }
+ }
+ if(node != root)
+ {
+ }
+ }
+}
+
+/*
+ * Prunes useless nodes from trees:
+ * erases nodes with total ammount of primitives = 0
+ * prunes nodes with only one child (except if that child is a primitive)
+ */
+template<class Node>
+void remove_useless(Node *node, Node **new_node)
+{
+ if( RayObject_isAligned(node->child) )
+ {
+
+ for(Node **prev = &node->child; *prev; )
+ {
+ Node *next = (*prev)->sibling;
+ remove_useless(*prev, prev);
+ if(*prev == 0)
+ *prev = next;
+ else
+ {
+ (*prev)->sibling = next;
+ prev = &((*prev)->sibling);
+ }
+ }
+ }
+ if(node->child)
+ {
+ if(RayObject_isAligned(node->child) && node->child->sibling == 0)
+ *new_node = node->child;
+ }
+ else if(node->child == 0)
+ *new_node = 0;
+}
+
+/*
+ * Minimizes expected number of BBtest by colapsing nodes
+ * it uses surface area heuristic for determining whether a node should be colapsed
+ */
+template<class Node>
+void pushup(Node *parent)
+{
+ if(is_leaf(parent)) return;
+
+ float p_area = bb_area(parent->bb, parent->bb+3);
+ Node **prev = &parent->child;
+ for(Node *child = parent->child; RayObject_isAligned(child) && child; )
+ {
+ float c_area = bb_area(child->bb, child->bb+3) ;
+ int nchilds = count_childs(child);
+ float original_cost = (c_area / p_area)*nchilds + 1;
+ float flatten_cost = nchilds;
+ if(flatten_cost < original_cost && nchilds >= 2)
+ {
+ append_sibling(child, child->child);
+ child = child->sibling;
+ *prev = child;
+
+// *prev = child->child;
+// append_sibling( *prev, child->sibling );
+// child = *prev;
+ tot_pushup++;
+ }
+ else
+ {
+ *prev = child;
+ prev = &(*prev)->sibling;
+ child = *prev;
+ }
+ }
+
+ for(Node *child = parent->child; RayObject_isAligned(child) && child; child = child->sibling)
+ pushup(child);
+}
+
+/*
+ * try to optimize number of childs to be a multiple of SSize
+ */
+template<class Node, int SSize>
+void pushup_simd(Node *parent)
+{
+ if(is_leaf(parent)) return;
+
+ int n = count_childs(parent);
+
+ Node **prev = &parent->child;
+ for(Node *child = parent->child; RayObject_isAligned(child) && child; )
+ {
+ int cn = count_childs(child);
+ if(cn-1 <= (SSize - (n%SSize) ) % SSize && RayObject_isAligned(child->child) )
+ {
+ n += (cn - 1);
+ append_sibling(child, child->child);
+ child = child->sibling;
+ *prev = child;
+ }
+ else
+ {
+ *prev = child;
+ prev = &(*prev)->sibling;
+ child = *prev;
+ }
+ }
+
+ for(Node *child = parent->child; RayObject_isAligned(child) && child; child = child->sibling)
+ pushup_simd<Node,SSize>(child);
+}
+
+
+/*
+ * Pushdown
+ * makes sure no child fits inside any of its sibling
+ */
+template<class Node>
+void pushdown(Node *parent)
+{
+ Node **s_child = &parent->child;
+ Node * child = parent->child;
+
+ while(child && RayObject_isAligned(child))
+ {
+ Node *next = child->sibling;
+ Node **next_s_child = &child->sibling;
+
+ //assert(bb_fits_inside(parent->bb, parent->bb+3, child->bb, child->bb+3));
+
+ for(Node *i = parent->child; RayObject_isAligned(i) && i; i = i->sibling)
+ if(child != i && bb_fits_inside(i->bb, i->bb+3, child->bb, child->bb+3) && RayObject_isAligned(i->child))
+ {
+// todo optimize (should the one with the smallest area?)
+// float ia = bb_area(i->bb, i->bb+3)
+// if(child->i)
+ *s_child = child->sibling;
+ child->sibling = i->child;
+ i->child = child;
+ next_s_child = s_child;
+
+ tot_pushdown++;
+ break;
+ }
+ child = next;
+ s_child = next_s_child;
+ }
+
+ for(Node *i = parent->child; RayObject_isAligned(i) && i; i = i->sibling)
+ pushdown( i );
+}
+
+
+/*
+ * BVH refit
+ * reajust nodes BB (useful if nodes childs where modified)
+ */
+template<class Node>
+float bvh_refit(Node *node)
+{
+ if(is_leaf(node)) return 0;
+ if(is_leaf(node->child)) return 0;
+
+ float total = 0;
+
+ for(Node *child = node->child; child; child = child->sibling)
+ total += bvh_refit(child);
+
+ float old_area = bb_area(node->bb, node->bb+3);
+ INIT_MINMAX(node->bb, node->bb+3);
+ for(Node *child = node->child; child; child = child->sibling)
+ {
+ DO_MIN(child->bb, node->bb);
+ DO_MAX(child->bb+3, node->bb+3);
+ }
+ total += old_area - bb_area(node->bb, node->bb+3);
+ return total;
+}
--- /dev/null
+/**
+ * $Id$
+ *
+ * ***** 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) 2009 Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): André Pinto.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+#ifndef RE_RAYTRACE_SVBVH_H
+#define RE_RAYTRACE_SVBVH_H
+
+#define SVBVH_SIMD 1
+
+#include "bvh.h"
+#include <stdio.h>
+
+struct SVBVHNode
+{
+ int nchilds;
+
+ //Array of bb, array of childs
+ float *child_bb;
+ SVBVHNode **child;
+};
+
+template<>
+inline int bvh_node_hit_test<SVBVHNode>(SVBVHNode *node, Isect *isec)
+{
+ return 1;
+}
+
+template<>
+inline void bvh_node_push_childs<SVBVHNode>(SVBVHNode *node, Isect *isec, SVBVHNode **stack, int &stack_pos)
+{
+ if(SVBVH_SIMD)
+ {
+ int i=0;
+ while(i+4 <= node->nchilds)
+ {
+ int res = test_bb_group4( (__m128*) (node->child_bb+6*i), isec );
+ RE_RC_COUNT(isec->raycounter->bb.test);
+ RE_RC_COUNT(isec->raycounter->bb.test);
+ RE_RC_COUNT(isec->raycounter->bb.test);
+ RE_RC_COUNT(isec->raycounter->bb.test);
+
+ if(res & 1) { stack[stack_pos++] = node->child[i+0]; RE_RC_COUNT(isec->raycounter->bb.hit); }
+ if(res & 2) { stack[stack_pos++] = node->child[i+1]; RE_RC_COUNT(isec->raycounter->bb.hit); }
+ if(res & 4) { stack[stack_pos++] = node->child[i+2]; RE_RC_COUNT(isec->raycounter->bb.hit); }
+ if(res & 8) { stack[stack_pos++] = node->child[i+3]; RE_RC_COUNT(isec->raycounter->bb.hit); }
+
+ i += 4;
+ }
+ while(i < node->nchilds)
+ {
+ if(RE_rayobject_bb_intersect_test(isec, (const float*)node->child_bb+6*i))
+ stack[stack_pos++] = node->child[i];
+ i++;
+ }
+ }
+ else
+ {
+ for(int i=0; i<node->nchilds; i++)
+ {
+ if(RE_rayobject_bb_intersect_test(isec, (const float*)node->child_bb+6*i))
+ stack[stack_pos++] = node->child[i];
+ }
+ }
+}
+
+template<>
+void bvh_node_merge_bb<SVBVHNode>(SVBVHNode *node, float *min, float *max)
+{
+ if(is_leaf(node))
+ {
+ RE_rayobject_merge_bb( (RayObject*)node, min, max);
+ }
+ else
+ {
+ int i=0;
+ while(SVBVH_SIMD && i+4 <= node->nchilds)
+ {
+ float *res = node->child_bb + 6*i;
+ for(int j=0; j<3; j++)
+ {
+ min[j] = MIN2(min[j], res[4*j+0]);
+ min[j] = MIN2(min[j], res[4*j+1]);
+ min[j] = MIN2(min[j], res[4*j+2]);
+ min[j] = MIN2(min[j], res[4*j+3]);
+ }
+ for(int j=0; j<3; j++)
+ {
+ max[j] = MAX2(max[j], res[4*(j+3)+0]);
+ max[j] = MAX2(max[j], res[4*(j+3)+1]);
+ max[j] = MAX2(max[j], res[4*(j+3)+2]);
+ max[j] = MAX2(max[j], res[4*(j+3)+3]);
+ }
+
+ i += 4;
+ }
+
+ for(; i<node->nchilds; i++)
+ {
+ DO_MIN(node->child_bb+6*i , min);
+ DO_MAX(node->child_bb+3+6*i, max);
+ }
+ }
+}
+
+struct SVBVHTree
+{
+ RayObject rayobj;
+
+ SVBVHNode *root;
+
+ MemArena *node_arena;
+
+ float cost;
+ RTBuilder *builder;
+};
+
+
+
+template<class Tree,class OldNode>
+struct Reorganize_SVBVH
+{
+ Tree *tree;
+
+ float childs_per_node;
+ int nodes_with_childs[16];
+ int useless_bb;
+ int nodes;
+
+ Reorganize_SVBVH(Tree *t)
+ {
+ tree = t;
+ nodes = 0;
+ childs_per_node = 0;
+ useless_bb = 0;
+
+ for(int i=0; i<16; i++)
+ nodes_with_childs[i] = 0;
+ }
+
+ ~Reorganize_SVBVH()
+ {
+ printf("%f childs per node\n", childs_per_node / nodes);
+ printf("%d childs BB are useless\n", useless_bb);
+ for(int i=0; i<16; i++)
+ printf("%i childs per node: %d/%d = %f\n", i, nodes_with_childs[i], nodes, nodes_with_childs[i]/float(nodes));
+ }
+
+ SVBVHNode *create_node(int nchilds)
+ {
+ SVBVHNode *node = (SVBVHNode*)BLI_memarena_alloc(tree->node_arena, sizeof(SVBVHNode));
+ node->nchilds = nchilds;
+ node->child_bb = (float*)BLI_memarena_alloc(tree->node_arena, sizeof(float)*6*nchilds);
+ node->child= (SVBVHNode**)BLI_memarena_alloc(tree->node_arena, sizeof(SVBVHNode*)*nchilds);
+
+ return node;
+ }
+
+ void copy_bb(float *bb, const float *old_bb)
+ {
+ std::copy( old_bb, old_bb+6, bb );
+ }
+
+ void prepare_for_simd(SVBVHNode *node)
+ {
+ int i=0;
+ while(i+4 <= node->nchilds)
+ {
+ float vec_tmp[4*6];
+ float *res = node->child_bb+6*i;
+ std::copy( res, res+6*4, vec_tmp);
+
+ for(int j=0; j<6; j++)
+ {
+ res[4*j+0] = vec_tmp[6*0+j];
+ res[4*j+1] = vec_tmp[6*1+j];
+ res[4*j+2] = vec_tmp[6*2+j];
+ res[4*j+3] = vec_tmp[6*3+j];
+ }
+/*
+ const float *bb0 = vec_tmp+6*(i+0);
+ const float *bb1 = vec_tmp+6*(i+1);
+ const float *bb2 = vec_tmp+6*(i+2);
+ const float *bb3 = vec_tmp+6*(i+3);
+
+ //memmoves could be memory alligned
+ const __m128 x0y0x1y1 = _mm_shuffle_ps( _mm_loadu_ps(bb0), _mm_loadu_ps(bb1), _MM_SHUFFLE(1,0,1,0) );
+ const __m128 x2y2x3y3 = _mm_shuffle_ps( _mm_loadu_ps(bb2), _mm_loadu_ps(bb3), _MM_SHUFFLE(1,0,1,0) );
+ _mm_store_ps( node->child_bb+6*i+4*0, _mm_shuffle_ps( x0y0x1y1, x2y2x3y3, _MM_SHUFFLE(2,0,2,0) ) );
+ _mm_store_ps( node->child_bb+6*i+4*1, _mm_shuffle_ps( x0y0x1y1, x2y2x3y3, _MM_SHUFFLE(3,1,3,1) ) );
+
+ const __m128 z0X0z1X1 = _mm_shuffle_ps( _mm_loadu_ps(bb0), _mm_loadu_ps(bb1), _MM_SHUFFLE(3,2,3,2) );
+ const __m128 z2X2z3X3 = _mm_shuffle_ps( _mm_loadu_ps(bb2), _mm_loadu_ps(bb3), _MM_SHUFFLE(3,2,3,2) );
+ _mm_store_ps( node->child_bb+6*i+4*2, _mm_shuffle_ps( z0X0z1X1, z2X2z3X3, _MM_SHUFFLE(2,0,2,0) ) );
+ _mm_store_ps( node->child_bb+6*i+4*3, _mm_shuffle_ps( z0X0z1X1, z2X2z3X3, _MM_SHUFFLE(3,1,3,1) ) );
+
+ const __m128 Y0Z0Y1Z1 = _mm_shuffle_ps( _mm_loadu_ps(bb0+4), _mm_loadu_ps(bb1+4), _MM_SHUFFLE(1,0,1,0) );
+ const __m128 Y2Z2Y3Z3 = _mm_shuffle_ps( _mm_loadu_ps(bb2+4), _mm_loadu_ps(bb3+4), _MM_SHUFFLE(1,0,1,0) );
+ _mm_store_ps( node->child_bb+6*i+4*4, _mm_shuffle_ps( Y0Z0Y1Z1, Y2Z2Y3Z3, _MM_SHUFFLE(2,0,2,0) ) );
+ _mm_store_ps( node->child_bb+6*i+4*5, _mm_shuffle_ps( Y0Z0Y1Z1, Y2Z2Y3Z3, _MM_SHUFFLE(3,1,3,1) ) );
+ */
+
+ i += 4;
+ }
+ }
+
+ /* amt must be power of two */
+ inline int padup(int num, int amt)
+ {
+ return ((num+(amt-1))&~(amt-1));
+ }
+
+ SVBVHNode *transform(OldNode *old)
+ {
+ if(is_leaf(old))
+ return (SVBVHNode*)old;
+ if(is_leaf(old->child))
+ return (SVBVHNode*)old->child;
+
+ int nchilds = count_childs(old);
+ int alloc_childs = nchilds;
+ if(nchilds % 4 > 2)
+ alloc_childs = padup(nchilds, 4);
+
+ SVBVHNode *node = create_node(alloc_childs);
+
+ childs_per_node += nchilds;
+ nodes++;
+ if(nchilds < 16)
+ nodes_with_childs[nchilds]++;
+
+ useless_bb += alloc_childs-nchilds;
+ while(alloc_childs > nchilds)
+ {
+ const static float def_bb[6] = { FLT_MAX, FLT_MAX, FLT_MAX, FLT_MIN, FLT_MIN, FLT_MIN };
+ alloc_childs--;
+ node->child[alloc_childs] = 0;
+ copy_bb(node->child_bb+alloc_childs*6, def_bb);
+ }
+
+ int i=nchilds;
+ for(OldNode *o_child = old->child; o_child; o_child = o_child->sibling)
+ {
+ i--;
+ node->child[i] = transform(o_child);
+ if(is_leaf(o_child))
+ {
+ float bb[6];
+ INIT_MINMAX(bb, bb+3);
+ RE_rayobject_merge_bb( (RayObject*)o_child, bb, bb+3);
+ copy_bb(node->child_bb+i*6, bb);
+ break;
+ }
+ else
+ {
+ copy_bb(node->child_bb+i*6, o_child->bb);
+ }
+ }
+ assert( i == 0 );
+
+
+ if(SVBVH_SIMD)
+ prepare_for_simd(node);
+
+ return node;
+ }
+};
+
+#endif
if(channel==-1) return "Mist";
return "Mist.Z";
}
+ if(passtype == SCE_PASS_RAYHITS)
+ {
+ if(channel==-1) return "Rayhits";
+ if(channel==0) return "Rayhits.R";
+ if(channel==1) return "Rayhits.G";
+ return "Rayhits.B";
+ }
return "Unknown";
}
if(strcmp(str, "Mist")==0)
return SCE_PASS_MIST;
+ if(strcmp(str, "RAYHITS")==0)
+ return SCE_PASS_RAYHITS;
return 0;
}
rl->lay= srl->lay;
rl->lay_zmask= srl->lay_zmask;
rl->layflag= srl->layflag;
- rl->passflag= srl->passflag;
+ rl->passflag= srl->passflag | SCE_PASS_RAYHITS;
rl->pass_xor= srl->pass_xor;
rl->light_override= srl->light_override;
rl->mat_override= srl->mat_override;
render_layer_add_pass(rr, rl, 1, SCE_PASS_INDEXOB);
if(srl->passflag & SCE_PASS_MIST)
render_layer_add_pass(rr, rl, 1, SCE_PASS_MIST);
+ if(rl->passflag & SCE_PASS_RAYHITS)
+ render_layer_add_pass(rr, rl, 4, SCE_PASS_RAYHITS);
}
/* sss, previewrender and envmap don't do layers, so we make a default one */
--- /dev/null
+/**
+ * $Id$
+ *
+ * ***** 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) 2009 Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): André Pinto.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+#include <assert.h>
+#include <stdio.h>
+
+#include "BKE_utildefines.h"
+#include "BLI_arithb.h"
+
+#include "RE_raytrace.h"
+#include "render_types.h"
+#include "rayobject.h"
+
+
+/*
+ * 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]
+ */
+/*
+float RE_rayobject_bb_intersect(const Isect *isec, const float *_bb)
+{
+ const float *bb = _bb;
+ float dist;
+
+ float t1x = (bb[isec->bv_index[0]] - isec->start[0]) * isec->idot_axis[0];
+ float t2x = (bb[isec->bv_index[1]] - isec->start[0]) * isec->idot_axis[0];
+ float t1y = (bb[isec->bv_index[2]] - isec->start[1]) * isec->idot_axis[1];
+ float t2y = (bb[isec->bv_index[3]] - isec->start[1]) * isec->idot_axis[1];
+ float t1z = (bb[isec->bv_index[4]] - isec->start[2]) * isec->idot_axis[2];
+ float t2z = (bb[isec->bv_index[5]] - isec->start[2]) * isec->idot_axis[2];
+
+ RE_RC_COUNT(isec->raycounter->bb.test);
+
+ 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 > isec->labda || t1y > isec->labda || t1z > isec->labda) return FLT_MAX;
+
+ RE_RC_COUNT(isec->raycounter->bb.hit);
+
+ dist = t1x;
+ if (t1y > dist) dist = t1y;
+ if (t1z > dist) dist = t1z;
+ return dist;
+}
+*/
+int RE_rayobject_bb_intersect_test(const Isect *isec, const float *_bb)
+{
+ const float *bb = _bb;
+
+ float t1x = (bb[isec->bv_index[0]] - isec->start[0]) * isec->idot_axis[0];
+ float t2x = (bb[isec->bv_index[1]] - isec->start[0]) * isec->idot_axis[0];
+ float t1y = (bb[isec->bv_index[2]] - isec->start[1]) * isec->idot_axis[1];
+ float t2y = (bb[isec->bv_index[3]] - isec->start[1]) * isec->idot_axis[1];
+ float t1z = (bb[isec->bv_index[4]] - isec->start[2]) * isec->idot_axis[2];
+ float t2z = (bb[isec->bv_index[5]] - isec->start[2]) * isec->idot_axis[2];
+
+ RE_RC_COUNT(isec->raycounter->bb.test);
+
+ if(t1x > t2y || t2x < t1y || t1x > t2z || t2x < t1z || t1y > t2z || t2y < t1z) return 0;
+ if(t2x < 0.0 || t2y < 0.0 || t2z < 0.0) return 0;
+ if(t1x > isec->labda || t1y > isec->labda || t1z > isec->labda) return 0;
+ RE_RC_COUNT(isec->raycounter->bb.hit);
+
+ return 1;
+}
+
+
+/* only for self-intersecting test with current render face (where ray left) */
+static int intersection2(VlakRen *face, float r0, float r1, float r2, float rx1, float ry1, float rz1)
+{
+ float co1[3], co2[3], co3[3], co4[3];
+ float x0,x1,x2,t00,t01,t02,t10,t11,t12,t20,t21,t22;
+ float m0, m1, m2, divdet, det, det1;
+ float u1, v, u2;
+
+ VECCOPY(co1, face->v1->co);
+ VECCOPY(co2, face->v2->co);
+ if(face->v4)
+ {
+ VECCOPY(co3, face->v4->co);
+ VECCOPY(co4, face->v3->co);
+ }
+ else
+ {
+ VECCOPY(co3, face->v3->co);
+ }
+
+ t00= co3[0]-co1[0];
+ t01= co3[1]-co1[1];
+ t02= co3[2]-co1[2];
+ t10= co3[0]-co2[0];
+ t11= co3[1]-co2[1];
+ t12= co3[2]-co2[2];
+
+ x0= t11*r2-t12*r1;
+ x1= t12*r0-t10*r2;
+ x2= t10*r1-t11*r0;
+
+ divdet= t00*x0+t01*x1+t02*x2;
+
+ m0= rx1-co3[0];
+ m1= ry1-co3[1];
+ m2= rz1-co3[2];
+ det1= m0*x0+m1*x1+m2*x2;
+
+ if(divdet!=0.0f) {
+ u1= det1/divdet;
+
+ if(u1<ISECT_EPSILON) {
+ det= t00*(m1*r2-m2*r1);
+ det+= t01*(m2*r0-m0*r2);
+ det+= t02*(m0*r1-m1*r0);
+ v= det/divdet;
+
+ if(v<ISECT_EPSILON && (u1 + v) > -(1.0f+ISECT_EPSILON)) {
+ return 1;
+ }
+ }
+ }
+
+ if(face->v4) {
+
+ t20= co3[0]-co4[0];
+ t21= co3[1]-co4[1];
+ t22= co3[2]-co4[2];
+
+ divdet= t20*x0+t21*x1+t22*x2;
+ if(divdet!=0.0f) {
+ u2= det1/divdet;
+
+ if(u2<ISECT_EPSILON) {
+ det= t20*(m1*r2-m2*r1);
+ det+= t21*(m2*r0-m0*r2);
+ det+= t22*(m0*r1-m1*r0);
+ v= det/divdet;
+
+ if(v<ISECT_EPSILON && (u2 + v) >= -(1.0f+ISECT_EPSILON)) {
+ return 2;
+ }
+ }
+ }
+ }
+ return 0;
+}
+
+
+/* ray - triangle or quad intersection */
+/* this function shall only modify Isect if it detects an hit */
+static int intersect_rayface(RayFace *face, Isect *is)
+{
+ float co1[3],co2[3],co3[3],co4[3];
+ float x0,x1,x2,t00,t01,t02,t10,t11,t12,t20,t21,t22,r0,r1,r2;
+ float m0, m1, m2, divdet, det1;
+ float labda, u, v;
+ short ok=0;
+
+ if(is->orig.ob == face->ob && is->orig.face == face->face)
+ return 0;
+
+ RE_RC_COUNT(is->raycounter->faces.test);
+
+#ifdef RE_RAYFACE_COORDS_VLAKREN
+ {
+ VlakRen *vlr = (VlakRen*)face->face;
+
+ VECCOPY(co1, vlr->v1->co);
+ VECCOPY(co2, vlr->v2->co);
+ if(vlr->v4)
+ {
+ VECCOPY(co3, vlr->v4->co);
+ VECCOPY(co4, vlr->v3->co);
+ }
+ else
+ {
+ VECCOPY(co3, vlr->v3->co);
+ }
+ }
+#else
+ VECCOPY(co1, face->v1);
+ VECCOPY(co2, face->v2);
+ if(RE_rayface_isQuad(face))
+ {
+ VECCOPY(co3, face->v4);
+ VECCOPY(co4, face->v3);
+ }
+ else
+ {
+ VECCOPY(co3, face->v3);
+ }
+#endif
+
+ t00= co3[0]-co1[0];
+ t01= co3[1]-co1[1];
+ t02= co3[2]-co1[2];
+ t10= co3[0]-co2[0];
+ t11= co3[1]-co2[1];
+ t12= co3[2]-co2[2];
+
+ r0= is->vec[0];
+ r1= is->vec[1];
+ r2= is->vec[2];
+
+ x0= t12*r1-t11*r2;
+ x1= t10*r2-t12*r0;
+ x2= t11*r0-t10*r1;
+
+ divdet= t00*x0+t01*x1+t02*x2;
+
+ m0= is->start[0]-co3[0];
+ m1= is->start[1]-co3[1];
+ m2= is->start[2]-co3[2];
+ det1= m0*x0+m1*x1+m2*x2;
+
+ if(divdet!=0.0f) {
+
+ divdet= 1.0f/divdet;
+ u= det1*divdet;
+ if(u<ISECT_EPSILON && u>-(1.0f+ISECT_EPSILON)) {
+ float cros0, cros1, cros2;
+
+ cros0= m1*t02-m2*t01;
+ cros1= m2*t00-m0*t02;
+ cros2= m0*t01-m1*t00;
+ v= divdet*(cros0*r0 + cros1*r1 + cros2*r2);
+
+ if(v<ISECT_EPSILON && (u + v) > -(1.0f+ISECT_EPSILON)) {
+ labda= divdet*(cros0*t10 + cros1*t11 + cros2*t12);
+
+ if(labda>-ISECT_EPSILON && labda<is->labda) {
+ ok= 1;
+ }
+ }
+ }
+ }
+
+ if(ok==0 && RE_rayface_isQuad(face)) {
+
+ t20= co3[0]-co4[0];
+ t21= co3[1]-co4[1];
+ t22= co3[2]-co4[2];
+
+ divdet= t20*x0+t21*x1+t22*x2;
+ if(divdet!=0.0f) {
+ divdet= 1.0f/divdet;
+ u = det1*divdet;
+
+ if(u<ISECT_EPSILON && u>-(1.0f+ISECT_EPSILON)) {
+ float cros0, cros1, cros2;
+ cros0= m1*t22-m2*t21;
+ cros1= m2*t20-m0*t22;
+ cros2= m0*t21-m1*t20;
+ v= divdet*(cros0*r0 + cros1*r1 + cros2*r2);
+
+ if(v<ISECT_EPSILON && (u + v) >-(1.0f+ISECT_EPSILON)) {
+ labda= divdet*(cros0*t10 + cros1*t11 + cros2*t12);
+
+ if(labda>-ISECT_EPSILON && labda<is->labda) {
+ ok= 2;
+ }
+ }
+ }
+ }
+ }
+
+ if(ok) {
+
+ /* when a shadow ray leaves a face, it can be little outside the edges of it, causing
+ intersection to be detected in its neighbour face */
+ if(is->skip & RE_SKIP_VLR_NEIGHBOUR)
+ {
+ if(labda < 0.1f && is->orig.ob == face->ob)
+ {
+ VlakRen * a = is->orig.face;
+ VlakRen * b = face->face;
+
+ /* so there's a shared edge or vertex, let's intersect ray with face
+ itself, if that's true we can safely return 1, otherwise we assume
+ the intersection is invalid, 0 */
+ if(a->v1==b->v1 || a->v2==b->v1 || a->v3==b->v1 || a->v4==b->v1
+ || a->v1==b->v2 || a->v2==b->v2 || a->v3==b->v2 || a->v4==b->v2
+ || a->v1==b->v3 || a->v2==b->v3 || a->v3==b->v3 || a->v4==b->v3
+ || (b->v4 && (a->v1==b->v4 || a->v2==b->v4 || a->v3==b->v4 || a->v4==b->v4)))
+ if(!intersection2((VlakRen*)a, -r0, -r1, -r2, is->start[0], is->start[1], is->start[2]))
+ {
+ return 0;
+ }
+ }
+ }
+#if 0
+ else if(labda < ISECT_EPSILON)
+ {
+ /* too close to origin */
+ return 0;
+ }
+#endif
+
+ RE_RC_COUNT(is->raycounter->faces.hit);
+
+ is->isect= ok; // wich half of the quad
+ is->labda= labda;
+ is->u= u; is->v= v;
+
+ is->hit.ob = face->ob;
+ is->hit.face = face->face;
+#ifdef RT_USE_LAST_HIT
+ is->last_hit = (RayObject*) RayObject_unalignRayFace(face);
+#endif
+ return 1;
+ }
+
+ return 0;
+}
+
+void RE_rayface_from_vlak(RayFace *face, ObjectInstanceRen *obi, VlakRen *vlr)
+{
+#ifdef RE_RAYFACE_COORDS_LOCAL
+ VECCOPY(face->v1, vlr->v1->co);
+ VECCOPY(face->v2, vlr->v2->co);
+ VECCOPY(face->v3, vlr->v3->co);
+ if(vlr->v4)
+ {
+ VECCOPY(face->v4, vlr->v4->co);
+ face->quad = 1;
+ }
+ else
+ {
+ face->quad = 0;
+ }
+#elif defined(RE_RAYFACE_COORDS_POINTER)
+ face->v1 = vlr->v1->co;
+ face->v2 = vlr->v2->co;
+ face->v3 = vlr->v3->co;
+ face->v4 = vlr->v4 ? vlr->v4->co : NULL;
+#elif defined(RE_RAYFACE_COORDS_VLAKREN)
+#endif
+ face->ob = obi;
+ face->face = vlr;
+}
+
+
+int RE_rayobject_raycast(RayObject *r, Isect *isec)
+{
+ int i;
+ RE_RC_COUNT(isec->raycounter->raycast.test);
+
+ /* Setup vars used on raycast */
+ isec->labda *= Normalize(isec->vec);
+ isec->dist = VecLength(isec->vec);
+
+ for(i=0; i<3; i++)
+ {
+ isec->idot_axis[i] = 1.0f / isec->vec[i];
+
+ isec->bv_index[2*i] = isec->idot_axis[i] < 0.0 ? 1 : 0;
+ isec->bv_index[2*i+1] = 1 - isec->bv_index[2*i];
+
+ isec->bv_index[2*i] = i+3*isec->bv_index[2*i];
+ isec->bv_index[2*i+1] = i+3*isec->bv_index[2*i+1];
+ }
+
+#ifdef RT_USE_LAST_HIT
+ /* Last hit heuristic */
+ if(isec->mode==RE_RAY_SHADOW && isec->last_hit)
+ {
+ RE_RC_COUNT(isec->raycounter->rayshadow_last_hit.test);
+
+ if(RE_rayobject_intersect(isec->last_hit, isec))
+ {
+ RE_RC_COUNT(isec->raycounter->raycast.hit);
+ RE_RC_COUNT(isec->raycounter->rayshadow_last_hit.hit);
+ return 1;
+ }
+ }
+#endif
+
+#ifdef RT_USE_HINT
+ isec->hit_hint = 0;
+#endif
+
+ if(RE_rayobject_intersect(r, isec))
+ {
+#ifdef RE_RAYCOUNTER
+ RE_RC_COUNT(isec->raycounter->raycast.hit);
+#endif
+
+#ifdef RT_USE_HINT
+ isec->hint = isec->hit_hint;
+#endif
+ return 1;
+ }
+ return 0;
+}
+
+int RE_rayobject_intersect(RayObject *r, Isect *i)
+{
+ if(RayObject_isRayFace(r))
+ {
+ return intersect_rayface( (RayFace*) RayObject_align(r), i);
+ }
+ else if(RayObject_isRayAPI(r))
+ {
+ r = RayObject_align( r );
+ return r->api->raycast( r, i );
+ }
+ else assert(0);
+}
+
+void RE_rayobject_add(RayObject *r, RayObject *o)
+{
+ r = RayObject_align( r );
+ return r->api->add( r, o );
+}
+
+void RE_rayobject_done(RayObject *r)
+{
+ r = RayObject_align( r );
+ r->api->done( r );
+}
+
+void RE_rayobject_free(RayObject *r)
+{
+ r = RayObject_align( r );
+ r->api->free( r );
+}
+
+void RE_rayobject_merge_bb(RayObject *r, float *min, float *max)
+{
+ if(RayObject_isRayFace(r))
+ {
+ RayFace *face = (RayFace*) RayObject_align(r);
+
+#ifdef RE_RAYFACE_COORDS_VLAKREN
+ VlakRen *vlr = (VlakRen*)face->face;
+ DO_MINMAX( vlr->v1->co, min, max );
+ DO_MINMAX( vlr->v2->co, min, max );
+ DO_MINMAX( vlr->v3->co, min, max );
+ if(RE_rayface_isQuad(face)) DO_MINMAX( vlr->v4->co, min, max );
+#else
+ DO_MINMAX( face->v1, min, max );
+ DO_MINMAX( face->v2, min, max );
+ DO_MINMAX( face->v3, min, max );
+ if(RE_rayface_isQuad(face)) DO_MINMAX( face->v4, min, max );
+#endif
+ }
+ else if(RayObject_isRayAPI(r))
+ {
+ r = RayObject_align( r );
+ r->api->bb( r, min, max );
+ }
+ else assert(0);
+}
+
+float RE_rayobject_cost(RayObject *r)
+{
+ if(RayObject_isRayFace(r))
+ {
+ return 1.0;
+ }
+ else if(RayObject_isRayAPI(r))
+ {
+ r = RayObject_align( r );
+ return r->api->cost( r );
+ }
+ else assert(0);
+}
+
+void RE_rayobject_hint_bb(RayObject *r, RayHint *hint, float *min, float *max)
+{
+ if(RayObject_isRayFace(r))
+ {
+ return;
+ }
+ else if(RayObject_isRayAPI(r))
+ {
+ r = RayObject_align( r );
+ return r->api->hint_bb( r, hint, min, max );
+ }
+ else assert(0);
+}
+
+#ifdef RE_RAYCOUNTER
+void RE_RC_INFO(RayCounter *info)
+{
+ printf("----------- Raycast counter --------\n");
+ printf("Rays total: %llu\n", info->raycast.test );
+ printf("Rays hit: %llu\n", info->raycast.hit );
+ printf("\n");
+ printf("BB tests: %llu\n", info->bb.test );
+ printf("BB hits: %llu\n", info->bb.hit );
+ printf("\n");
+ printf("Primitives tests: %llu\n", info->faces.test );
+ printf("Primitives hits: %llu\n", info->faces.hit );
+ printf("------------------------------------\n");
+ printf("Shadow last-hit tests per ray: %f\n", info->rayshadow_last_hit.test / ((float)info->raycast.test) );
+ printf("Shadow last-hit hits per ray: %f\n", info->rayshadow_last_hit.hit / ((float)info->raycast.test) );
+ printf("\n");
+ printf("Hint tests per ray: %f\n", info->raytrace_hint.test / ((float)info->raycast.test) );
+ printf("Hint hits per ray: %f\n", info->raytrace_hint.hit / ((float)info->raycast.test) );
+ printf("\n");
+ printf("BB tests per ray: %f\n", info->bb.test / ((float)info->raycast.test) );
+ printf("BB hits per ray: %f\n", info->bb.hit / ((float)info->raycast.test) );
+ printf("\n");
+ printf("Primitives tests per ray: %f\n", info->faces.test / ((float)info->raycast.test) );
+ printf("Primitives hits per ray: %f\n", info->faces.hit / ((float)info->raycast.test) );
+ printf("------------------------------------\n");
+}
+
+void RE_RC_MERGE(RayCounter *dest, RayCounter *tmp)
+{
+ dest->faces.test += tmp->faces.test;
+ dest->faces.hit += tmp->faces.hit;
+
+ dest->bb.test += tmp->bb.test;
+ dest->bb.hit += tmp->bb.hit;
+
+ dest->raycast.test += tmp->raycast.test;
+ dest->raycast.hit += tmp->raycast.hit;
+
+ dest->rayshadow_last_hit.test += tmp->rayshadow_last_hit.test;
+ dest->rayshadow_last_hit.hit += tmp->rayshadow_last_hit.hit;
+
+ dest->raytrace_hint.test += tmp->raytrace_hint.test;
+ dest->raytrace_hint.hit += tmp->raytrace_hint.hit;
+}
+
+#endif
\ No newline at end of file
--- /dev/null
+/**
+ * $Id$
+ *
+ * ***** 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) 2009 Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): André Pinto.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+#include <assert.h>
+
+#include "MEM_guardedalloc.h"
+#include "BKE_utildefines.h"
+#include "BLI_kdopbvh.h"
+#include "BLI_arithb.h"
+#include "RE_raytrace.h"
+#include "render_types.h"
+#include "rayobject.h"
+
+static int RayObject_blibvh_intersect(RayObject *o, Isect *isec);
+static void RayObject_blibvh_add(RayObject *o, RayObject *ob);
+static void RayObject_blibvh_done(RayObject *o);
+static void RayObject_blibvh_free(RayObject *o);
+static void RayObject_blibvh_bb(RayObject *o, float *min, float *max);
+
+static RayObjectAPI bvh_api =
+{
+ RayObject_blibvh_intersect,
+ RayObject_blibvh_add,
+ RayObject_blibvh_done,
+ RayObject_blibvh_free,
+ RayObject_blibvh_bb
+};
+
+typedef struct BVHObject
+{
+ RayObject rayobj;
+ BVHTree *bvh;
+ float bb[2][3];
+
+} BVHObject;
+
+
+RayObject *RE_rayobject_blibvh_create(int size)
+{
+ BVHObject *obj= (BVHObject*)MEM_callocN(sizeof(BVHObject), "BVHObject");
+ assert( RayObject_isAligned(obj) ); /* RayObject API assumes real data to be 4-byte aligned */
+
+ obj->rayobj.api = &bvh_api;
+ obj->bvh = BLI_bvhtree_new(size, 0.0, 4, 6);
+
+ INIT_MINMAX(obj->bb[0], obj->bb[1]);
+ return RayObject_unalignRayAPI((RayObject*) obj);
+}
+
+static void bvh_callback(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
+{
+ Isect *isec = (Isect*)userdata;
+ RayObject *face = (RayObject*)index;
+
+ if(RE_rayobject_intersect(face,isec))
+ {
+ hit->index = index;
+
+ if(isec->mode == RE_RAY_SHADOW)
+ hit->dist = 0;
+ else
+ hit->dist = isec->labda*isec->dist;
+ }
+}
+
+static int RayObject_blibvh_intersect(RayObject *o, Isect *isec)
+{
+ BVHObject *obj = (BVHObject*)o;
+ BVHTreeRayHit hit;
+ float dir[3];
+
+ VECCOPY(dir, isec->vec);
+ Normalize(dir);
+
+ hit.index = 0;
+ hit.dist = isec->labda*isec->dist;
+
+ return BLI_bvhtree_ray_cast(obj->bvh, isec->start, dir, 0.0, &hit, bvh_callback, isec);
+}
+
+static void RayObject_blibvh_add(RayObject *o, RayObject *ob)
+{
+ BVHObject *obj = (BVHObject*)o;
+ float min_max[6];
+ INIT_MINMAX(min_max, min_max+3);
+ RE_rayobject_merge_bb(ob, min_max, min_max+3);
+
+ DO_MIN(min_max , obj->bb[0]);
+ DO_MAX(min_max+3, obj->bb[1]);
+
+ BLI_bvhtree_insert(obj->bvh, (int)ob, min_max, 2 );
+}
+
+static void RayObject_blibvh_done(RayObject *o)
+{
+ BVHObject *obj = (BVHObject*)o;
+ BLI_bvhtree_balance(obj->bvh);
+}
+
+static void RayObject_blibvh_free(RayObject *o)
+{
+ BVHObject *obj = (BVHObject*)o;
+
+ if(obj->bvh)
+ BLI_bvhtree_free(obj->bvh);
+
+ MEM_freeN(obj);
+}
+
+static void RayObject_blibvh_bb(RayObject *o, float *min, float *max)
+{
+ BVHObject *obj = (BVHObject*)o;
+ DO_MIN( obj->bb[0], min );
+ DO_MAX( obj->bb[1], max );
+}
--- /dev/null
+/**
+ * $Id$
+ *
+ * ***** 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) 2009 Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): André Pinto.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+#include <assert.h>
+
+#include "MEM_guardedalloc.h"
+#include "BKE_utildefines.h"
+#include "BLI_arithb.h"
+#include "RE_raytrace.h"
+#include "rayobject.h"
+
+#define RE_COST_INSTANCE (1.0f)
+
+static int RayObject_instance_intersect(RayObject *o, Isect *isec);
+static void RayObject_instance_free(RayObject *o);
+static void RayObject_instance_bb(RayObject *o, float *min, float *max);
+static float RayObject_instance_cost(RayObject *o);
+
+static RayObjectAPI instance_api =
+{
+ RayObject_instance_intersect,
+ NULL, //static void RayObject_instance_add(RayObject *o, RayObject *ob);
+ NULL, //static void RayObject_instance_done(RayObject *o);
+ RayObject_instance_free,
+ RayObject_instance_bb,
+ RayObject_instance_cost
+};
+
+typedef struct InstanceRayObject
+{
+ RayObject rayobj;
+ RayObject *target;
+
+ void *ob; //Object represented by this instance
+ void *target_ob; //Object represented by the inner RayObject, needed to handle self-intersection
+
+ float global2target[4][4];
+ float target2global[4][4];
+
+} InstanceRayObject;
+
+
+RayObject *RE_rayobject_instance_create(RayObject *target, float transform[][4], void *ob, void *target_ob)
+{
+ InstanceRayObject *obj= (InstanceRayObject*)MEM_callocN(sizeof(InstanceRayObject), "InstanceRayObject");
+ assert( RayObject_isAligned(obj) ); /* RayObject API assumes real data to be 4-byte aligned */
+
+ obj->rayobj.api = &instance_api;
+ obj->target = target;
+ obj->ob = ob;
+ obj->target_ob = target_ob;
+
+ Mat4CpyMat4(obj->target2global, transform);
+ Mat4Invert(obj->global2target, obj->target2global);
+
+ return RayObject_unalignRayAPI((RayObject*) obj);
+}
+
+static int RayObject_instance_intersect(RayObject *o, Isect *isec)
+{
+ //TODO
+ // *there is probably a faster way to convert between coordinates
+
+ InstanceRayObject *obj = (InstanceRayObject*)o;
+ int res;
+ float start[3], vec[3], labda, dist;
+ int changed = 0, i;
+
+ //TODO - this is disabling self intersection on instances
+ if(isec->orig.ob == obj->ob && obj->ob)
+ {
+ changed = 1;
+ isec->orig.ob = obj->target_ob;
+ }
+
+
+ VECCOPY( start, isec->start );
+ VECCOPY( vec , isec->vec );
+ labda = isec->labda;
+ dist = isec->dist;
+
+ //Transform to target coordinates system
+ VECADD( isec->vec, isec->vec, isec->start );
+
+ Mat4MulVecfl(obj->global2target, isec->start);
+ Mat4MulVecfl(obj->global2target, isec->vec );
+
+ isec->dist = VecLenf( isec->start, isec->vec );
+ VECSUB( isec->vec, isec->vec, isec->start );
+
+ isec->labda *= isec->dist / dist;
+
+ //Update idot_axis and bv_index
+ for(i=0; i<3; i++)
+ {
+ isec->idot_axis[i] = 1.0f / isec->vec[i];
+
+ isec->bv_index[2*i] = isec->idot_axis[i] < 0.0 ? 1 : 0;
+ isec->bv_index[2*i+1] = 1 - isec->bv_index[2*i];
+
+ isec->bv_index[2*i] = i+3*isec->bv_index[2*i];
+ isec->bv_index[2*i+1] = i+3*isec->bv_index[2*i+1];
+ }
+
+ //Raycast
+ res = RE_rayobject_intersect(obj->target, isec);
+
+ //Restore coordinate space coords
+ if(res == 0)
+ {
+ isec->labda = labda;
+ }
+ else
+ {
+ isec->labda *= dist / isec->dist;
+ isec->hit.ob = obj->ob;
+ }
+ isec->dist = dist;
+ VECCOPY( isec->start, start );
+ VECCOPY( isec->vec, vec );
+
+ if(changed)
+ isec->orig.ob = obj->ob;
+
+ //Update idot_axis and bv_index
+ for(i=0; i<3; i++)
+ {
+ isec->idot_axis[i] = 1.0f / isec->vec[i];
+
+ isec->bv_index[2*i] = isec->idot_axis[i] < 0.0 ? 1 : 0;
+ isec->bv_index[2*i+1] = 1 - isec->bv_index[2*i];
+
+ isec->bv_index[2*i] = i+3*isec->bv_index[2*i];
+ isec->bv_index[2*i+1] = i+3*isec->bv_index[2*i+1];
+ }
+
+ return res;
+}
+
+static void RayObject_instance_free(RayObject *o)
+{
+ InstanceRayObject *obj = (InstanceRayObject*)o;
+ MEM_freeN(obj);
+}
+
+static float RayObject_instance_cost(RayObject *o)
+{
+ InstanceRayObject *obj = (InstanceRayObject*)o;
+ return RE_rayobject_cost(obj->target) + RE_COST_INSTANCE;
+}
+
+static void RayObject_instance_bb(RayObject *o, float *min, float *max)
+{
+ //TODO:
+ // *better bb.. calculated without rotations of bb
+ // *maybe cache that better-fitted-BB at the InstanceRayObject
+ InstanceRayObject *obj = (InstanceRayObject*)o;
+
+ float m[3], M[3], t[3];
+ int i, j;
+ INIT_MINMAX(m, M);
+ RE_rayobject_merge_bb(obj->target, m, M);
+
+ //There must be a faster way than rotating all the 8 vertexs of the BB
+ for(i=0; i<8; i++)
+ {
+ for(j=0; j<3; j++) t[j] = i&(1<<j) ? M[j] : m[j];
+ Mat4MulVecfl(obj->target2global, t);
+ DO_MINMAX(t, min, max);
+ }
+}
#include <string.h>
#include <stdlib.h>
#include <float.h>
+#include <assert.h>
#include "MEM_guardedalloc.h"
#include "BLI_arithb.h"
-#include "RE_raytrace.h"
+#include "rayobject.h"
/* ********** structs *************** */
-
#define BRANCH_ARRAY 1024
#define NODE_ARRAY 4096
typedef struct Node
{
struct RayFace *v[8];
- int ob[8];
struct OcVal ov[8];
struct Node *next;
} Node;
typedef struct Octree {
+ RayObject rayobj;
+
struct Branch **adrbranch;
struct Node **adrnode;
float ocsize; /* ocsize: mult factor, max size octree */
float min[3], max[3];
int ocres;
int branchcount, nodecount;
- char *ocface; /* during building only */
- RayCoordsFunc coordsfunc;
- RayCheckFunc checkfunc;
- RayObjectTransformFunc transformfunc;
- void *userdata;
-} Octree;
-/* ******** globals ***************** */
+ /* during building only */
+ char *ocface;
+
+ RayFace **ro_nodes;
+ int ro_nodes_size, ro_nodes_used;
+
+} Octree;
-/* just for statistics */
-static int raycount;
-static int accepted, rejected, coherent_ray;
+static int RayObject_octree_intersect(RayObject *o, Isect *isec);
+static void RayObject_octree_add(RayObject *o, RayObject *ob);
+static void RayObject_octree_done(RayObject *o);
+static void RayObject_octree_free(RayObject *o);
+static void RayObject_octree_bb(RayObject *o, float *min, float *max);
+static RayObjectAPI octree_api =
+{
+ RayObject_octree_intersect,
+ RayObject_octree_add,
+ RayObject_octree_done,
+ RayObject_octree_free,
+ RayObject_octree_bb
+};
/* **************** ocval method ******************* */
/* within one octree node, a set of 3x15 bits defines a 'boundbox' to OR with */
return 0;
}
-static void ocwrite(Octree *oc, int ob, RayFace *face, int quad, short x, short y, short z, float rtf[][3])
+static void ocwrite(Octree *oc, RayFace *face, int quad, short x, short y, short z, float rtf[][3])
{
Branch *br;
Node *no;
while(no->v[a]!=NULL) a++;
}
- no->v[a]= face;
- no->ob[a]= ob;
+ no->v[a]= (RayFace*) RayObject_align(face);
if(quad)
calc_ocval_face(rtf[0], rtf[1], rtf[2], rtf[3], x>>2, y>>1, z, &no->ov[a]);
ocface[oc->ocres*ocx2+ocy2]=1;
}
-static void filltriangle(Octree *oc, short c1, short c2, char *ocface, short *ocmin)
+static void filltriangle(Octree *oc, short c1, short c2, char *ocface, short *ocmin, short *ocmax)
{
- short *ocmax;
int a, x, y, y1, y2;
- ocmax=ocmin+3;
-
for(x=ocmin[c1];x<=ocmax[c1];x++) {
a= oc->ocres*x;
for(y=ocmin[c2];y<=ocmax[c2];y++) {
}
}
-void RE_ray_tree_free(RayTree *tree)
+static void RayObject_octree_free(RayObject *tree)
{
Octree *oc= (Octree*)tree;
MEM_freeN(oc);
}
-RayTree *RE_ray_tree_create(int ocres, int totface, float *min, float *max, RayCoordsFunc coordsfunc, RayCheckFunc checkfunc, RayObjectTransformFunc transformfunc, void *userdata)
+
+RayObject *RE_rayobject_octree_create(int ocres, int size)
{
- Octree *oc;
- float t00, t01, t02;
- int c, ocres2;
+ Octree *oc= MEM_callocN(sizeof(Octree), "Octree");
+ assert( RayObject_isAligned(oc) ); /* RayObject API assumes real data to be 4-byte aligned */
- oc= MEM_callocN(sizeof(Octree), "Octree");
- oc->adrbranch= MEM_callocN(sizeof(void *)*BRANCH_ARRAY, "octree branches");
- oc->adrnode= MEM_callocN(sizeof(void *)*NODE_ARRAY, "octree nodes");
-
- oc->coordsfunc= coordsfunc;
- oc->checkfunc= checkfunc;
- oc->transformfunc= transformfunc;
- oc->userdata= userdata;
-
- /* only for debug info */
- raycount=0;
- accepted= 0;
- rejected= 0;
- coherent_ray= 0;
+ oc->rayobj.api = &octree_api;
- /* fill main octree struct */
- oc->ocres= ocres;
- ocres2= oc->ocres*oc->ocres;
+ oc->ocres = ocres;
- VECCOPY(oc->min, min);
- VECCOPY(oc->max, max);
+ oc->ro_nodes = (RayFace**)MEM_callocN(sizeof(RayFace*)*size, "octree rayobject nodes");
+ oc->ro_nodes_size = size;
+ oc->ro_nodes_used = 0;
- oc->adrbranch[0]=(Branch *)MEM_callocN(4096*sizeof(Branch), "makeoctree");
- /* the lookup table, per face, for which nodes to fill in */
- oc->ocface= MEM_callocN( 3*ocres2 + 8, "ocface");
- memset(oc->ocface, 0, 3*ocres2);
+ return RayObject_unalignRayAPI((RayObject*) oc);
+}
- for(c=0;c<3;c++) { /* octree enlarge, still needed? */
- oc->min[c]-= 0.01f;
- oc->max[c]+= 0.01f;
- }
- t00= oc->max[0]-oc->min[0];
- t01= oc->max[1]-oc->min[1];
- t02= oc->max[2]-oc->min[2];
-
- /* this minus 0.1 is old safety... seems to be needed? */
- oc->ocfacx= (oc->ocres-0.1)/t00;
- oc->ocfacy= (oc->ocres-0.1)/t01;
- oc->ocfacz= (oc->ocres-0.1)/t02;
-
- oc->ocsize= sqrt(t00*t00+t01*t01+t02*t02); /* global, max size octree */
+static void RayObject_octree_add(RayObject *tree, RayObject *node)
+{
+ Octree *oc = (Octree*)tree;
- return (RayTree*)oc;
+ assert( RayObject_isRayFace(node) );
+ assert( oc->ro_nodes_used < oc->ro_nodes_size );
+ oc->ro_nodes[ oc->ro_nodes_used++ ] = (RayFace*)RayObject_align(node);
}
-void RE_ray_tree_add_face(RayTree *tree, int ob, RayFace *face)
+static void octree_fill_rayface(Octree *oc, RayFace *face)
{
- Octree *oc = (Octree*)tree;
- float *v1, *v2, *v3, *v4, ocfac[3], rtf[4][3];
+ float ocfac[3], rtf[4][3];
float co1[3], co2[3], co3[3], co4[3];
- short rts[4][3], ocmin[6], *ocmax;
+ short rts[4][3];
+ short ocmin[3], ocmax[3];
char *ocface= oc->ocface; // front, top, size view of face, to fill in
int a, b, c, oc1, oc2, oc3, oc4, x, y, z, ocres2;
ocres2= oc->ocres*oc->ocres;
- ocmax= ocmin+3;
-
- oc->coordsfunc(face, &v1, &v2, &v3, &v4);
-
- VECCOPY(co1, v1);
- VECCOPY(co2, v2);
- VECCOPY(co3, v3);
- if(v4)
- VECCOPY(co4, v4);
-
- if(ob >= RE_RAY_TRANSFORM_OFFS) {
- float (*mat)[4]= (float(*)[4])oc->transformfunc(oc->userdata, ob);
-
- if(mat) {
- Mat4MulVecfl(mat, co1);
- Mat4MulVecfl(mat, co2);
- Mat4MulVecfl(mat, co3);
- if(v4)
- Mat4MulVecfl(mat, co4);
- }
+#ifdef RE_RAYFACE_COORDS_VLAKREN
+ {
+ VlakRen *vlr = (VlakRen*)face->face;
+ VECCOPY(co1, vlr->v1->co);
+ VECCOPY(co2, vlr->v2->co);
+ VECCOPY(co3, vlr->v3->co);
+ if(RE_rayface_isQuad(face))
+ VECCOPY(co4, vlr->v4->co);
}
-
+#else
+ VECCOPY(co1, face->v1);
+ VECCOPY(co2, face->v2);
+ VECCOPY(co3, face->v3);
+ if(face->v4)
+ VECCOPY(co4, face->v4);
+#endif
+
for(c=0;c<3;c++) {
rtf[0][c]= (co1[c]-oc->min[c])*ocfac[c] ;
rts[0][c]= (short)rtf[0][c];
rts[1][c]= (short)rtf[1][c];
rtf[2][c]= (co3[c]-oc->min[c])*ocfac[c] ;
rts[2][c]= (short)rtf[2][c];
- if(v4) {
+ if(RE_rayface_isQuad(face)) {
rtf[3][c]= (co4[c]-oc->min[c])*ocfac[c] ;
rts[3][c]= (short)rtf[3][c];
}
oc1= rts[0][c];
oc2= rts[1][c];
oc3= rts[2][c];
- if(v4==NULL) {
+ if(!RE_rayface_isQuad(face)) {
ocmin[c]= MIN3(oc1,oc2,oc3);
ocmax[c]= MAX3(oc1,oc2,oc3);
}
}
if(ocmin[0]==ocmax[0] && ocmin[1]==ocmax[1] && ocmin[2]==ocmax[2]) {
- ocwrite(oc, ob, face, (v4 != NULL), ocmin[0], ocmin[1], ocmin[2], rtf);
+ ocwrite(oc, face, RE_rayface_isQuad(face), ocmin[0], ocmin[1], ocmin[2], rtf);
}
else {
d2dda(oc, 1,2,0,1,ocface+ocres2,rts,rtf);
d2dda(oc, 1,2,0,2,ocface,rts,rtf);
d2dda(oc, 1,2,1,2,ocface+2*ocres2,rts,rtf);
- if(v4==NULL) {
+ if(!RE_rayface_isQuad(face)) {
d2dda(oc, 2,0,0,1,ocface+ocres2,rts,rtf);
d2dda(oc, 2,0,0,2,ocface,rts,rtf);
d2dda(oc, 2,0,1,2,ocface+2*ocres2,rts,rtf);
d2dda(oc, 3,0,1,2,ocface+2*ocres2,rts,rtf);
}
/* nothing todo with triangle..., just fills :) */
- filltriangle(oc, 0,1,ocface+ocres2,ocmin);
- filltriangle(oc, 0,2,ocface,ocmin);
- filltriangle(oc, 1,2,ocface+2*ocres2,ocmin);
+ filltriangle(oc, 0,1,ocface+ocres2,ocmin,ocmax);
+ filltriangle(oc, 0,2,ocface,ocmin,ocmax);
+ filltriangle(oc, 1,2,ocface+2*ocres2,ocmin,ocmax);
/* init static vars here */
face_in_node(face, 0,0,0, rtf);
for(z=ocmin[2];z<=ocmax[2];z++) {
if(ocface[b+z] && ocface[a+z]) {
if(face_in_node(NULL, x, y, z, rtf))
- ocwrite(oc, ob, face, (v4 != NULL), x,y,z, rtf);
+ ocwrite(oc, face, RE_rayface_isQuad(face), x,y,z, rtf);
}
}
}
}
}
-void RE_ray_tree_done(RayTree *tree)
+static void RayObject_octree_done(RayObject *tree)
{
- Octree *oc= (Octree*)tree;
-
- MEM_freeN(oc->ocface);
- oc->ocface= NULL;
-}
-
-/* ************ raytracer **************** */
-
-#define ISECT_EPSILON ((float)FLT_EPSILON)
-
-/* only for self-intersecting test with current render face (where ray left) */
-static int intersection2(RayFace *face, int ob, RayObjectTransformFunc transformfunc, RayCoordsFunc coordsfunc, void *userdata, float r0, float r1, float r2, float rx1, float ry1, float rz1)
-{
- float *v1, *v2, *v3, *v4, co1[3], co2[3], co3[3], co4[3];
- float x0,x1,x2,t00,t01,t02,t10,t11,t12,t20,t21,t22;
- float m0, m1, m2, divdet, det, det1;
- float u1, v, u2;
-
- coordsfunc(face, &v1, &v2, &v3, &v4);
-
- /* happens for baking with non existing face */
- if(v1==NULL)
- return 1;
-
- if(v4) {
- SWAP(float*, v3, v4);
- }
-
- VECCOPY(co1, v1);
- VECCOPY(co2, v2);
- VECCOPY(co3, v3);
- if(v4)
- VECCOPY(co4, v4);
-
- if(ob >= RE_RAY_TRANSFORM_OFFS) {
- float (*mat)[4]= (float(*)[4])transformfunc(userdata, ob);
-
- if(mat) {
- Mat4MulVecfl(mat, co1);
- Mat4MulVecfl(mat, co2);
- Mat4MulVecfl(mat, co3);
- if(v4)
- Mat4MulVecfl(mat, co4);
- }
- }
-
- t00= co3[0]-co1[0];
- t01= co3[1]-co1[1];
- t02= co3[2]-co1[2];
- t10= co3[0]-co2[0];
- t11= co3[1]-co2[1];
- t12= co3[2]-co2[2];
+ Octree *oc = (Octree*)tree;
+ int c;
+ float t00, t01, t02;
+ int ocres2 = oc->ocres*oc->ocres;
- x0= t11*r2-t12*r1;
- x1= t12*r0-t10*r2;
- x2= t10*r1-t11*r0;
-
- divdet= t00*x0+t01*x1+t02*x2;
-
- m0= rx1-co3[0];
- m1= ry1-co3[1];
- m2= rz1-co3[2];
- det1= m0*x0+m1*x1+m2*x2;
+ INIT_MINMAX(oc->min, oc->max);
- if(divdet!=0.0f) {
- u1= det1/divdet;
-
- if(u1<ISECT_EPSILON) {
- det= t00*(m1*r2-m2*r1);
- det+= t01*(m2*r0-m0*r2);
- det+= t02*(m0*r1-m1*r0);
- v= det/divdet;
-
- if(v<ISECT_EPSILON && (u1 + v) > -(1.0f+ISECT_EPSILON)) {
- return 1;
- }
- }
- }
-
- if(v4) {
-
- t20= co3[0]-co4[0];
- t21= co3[1]-co4[1];
- t22= co3[2]-co4[2];
-
- divdet= t20*x0+t21*x1+t22*x2;
- if(divdet!=0.0f) {
- u2= det1/divdet;
+ /* Calculate Bounding Box */
+ for(c=0; c<oc->ro_nodes_used; c++)
+ RE_rayobject_merge_bb( RayObject_unalignRayFace(oc->ro_nodes[c]), oc->min, oc->max);
- if(u2<ISECT_EPSILON) {
- det= t20*(m1*r2-m2*r1);
- det+= t21*(m2*r0-m0*r2);
- det+= t22*(m0*r1-m1*r0);
- v= det/divdet;
-
- if(v<ISECT_EPSILON && (u2 + v) >= -(1.0f+ISECT_EPSILON)) {
- return 2;
- }
- }
- }
- }
- return 0;
-}
-
-#if 0
-/* ray - line intersection */
-/* disabled until i got real & fast cylinder checking, this code doesnt work proper
-for faster strands */
-
-static int intersection_strand(Isect *is)
-{
- float v1[3], v2[3]; /* length of strand */
- float axis[3], rc[3], nor[3], radline, dist, len;
-
- /* radius strand */
- radline= 0.5f*VecLenf(is->vlr->v1->co, is->vlr->v2->co);
-
- VecMidf(v1, is->vlr->v1->co, is->vlr->v2->co);
- VecMidf(v2, is->vlr->v3->co, is->vlr->v4->co);
-
- VECSUB(rc, v1, is->start); /* vector from base ray to base cylinder */
- VECSUB(axis, v2, v1); /* cylinder axis */
-
- CROSS(nor, is->vec, axis);
- len= VecLength(nor);
-
- if(len<FLT_EPSILON)
- return 0;
-
- dist= INPR(rc, nor)/len; /* distance between ray and axis cylinder */
+ /* Alloc memory */
+ oc->adrbranch= MEM_callocN(sizeof(void *)*BRANCH_ARRAY, "octree branches");
+ oc->adrnode= MEM_callocN(sizeof(void *)*NODE_ARRAY, "octree nodes");
- if(dist<radline && dist>-radline) {
- float dot1, dot2, dot3, rlen, alen, div;
- float labda;
-
- /* calculating the intersection point of shortest distance */
- dot1 = INPR(rc, is->vec);
- dot2 = INPR(is->vec, axis);
- dot3 = INPR(rc, axis);
- rlen = INPR(is->vec, is->vec);
- alen = INPR(axis, axis);
-
- div = alen * rlen - dot2 * dot2;
- if (ABS(div) < FLT_EPSILON)
- return 0;
-
- labda = (dot1*dot2 - dot3*rlen)/div;
-
- radline/= sqrt(alen);
-
- /* labda: where on axis do we have closest intersection? */
- if(labda >= -radline && labda <= 1.0f+radline) {
- VlakRen *vlr= is->faceorig;
- VertRen *v1= is->vlr->v1, *v2= is->vlr->v2, *v3= is->vlr->v3, *v4= is->vlr->v4;
- /* but we dont do shadows from faces sharing edge */
-
- if(v1==vlr->v1 || v2==vlr->v1 || v3==vlr->v1 || v4==vlr->v1) return 0;
- if(v1==vlr->v2 || v2==vlr->v2 || v3==vlr->v2 || v4==vlr->v2) return 0;
- if(v1==vlr->v3 || v2==vlr->v3 || v3==vlr->v3 || v4==vlr->v3) return 0;
- if(vlr->v4) {
- if(v1==vlr->v4 || v2==vlr->v4 || v3==vlr->v4 || v4==vlr->v4) return 0;
- }
- return 1;
- }
- }
- return 0;
-}
-#endif
-
-/* ray - triangle or quad intersection */
-int RE_ray_face_intersection(Isect *is, RayObjectTransformFunc transformfunc, RayCoordsFunc coordsfunc)
-{
- RayFace *face= is->face;
- int ob= is->ob;
- float *v1,*v2,*v3,*v4,co1[3],co2[3],co3[3],co4[3];
- float x0,x1,x2,t00,t01,t02,t10,t11,t12,t20,t21,t22,r0,r1,r2;
- float m0, m1, m2, divdet, det1;
- short ok=0;
-
- /* disabled until i got real & fast cylinder checking, this code doesnt work proper
- for faster strands */
-// if(is->mode==RE_RAY_SHADOW && is->vlr->flag & R_STRAND)
-// return intersection_strand(is);
+ oc->adrbranch[0]=(Branch *)MEM_callocN(4096*sizeof(Branch), "makeoctree");
- coordsfunc(face, &v1, &v2, &v3, &v4);
-
- if(v4) {
- SWAP(float*, v3, v4);
- }
+ /* the lookup table, per face, for which nodes to fill in */
+ oc->ocface= MEM_callocN( 3*ocres2 + 8, "ocface");
+ memset(oc->ocface, 0, 3*ocres2);
- VECCOPY(co1, v1);
- VECCOPY(co2, v2);
- VECCOPY(co3, v3);
- if(v4)
- VECCOPY(co4, v4);
-
- if(ob) {
- float (*mat)[4]= (float(*)[4])transformfunc(is->userdata, ob);
-
- if(mat) {
- Mat4MulVecfl(mat, co1);
- Mat4MulVecfl(mat, co2);
- Mat4MulVecfl(mat, co3);
- if(v4)
- Mat4MulVecfl(mat, co4);
- }
+ for(c=0;c<3;c++) { /* octree enlarge, still needed? */
+ oc->min[c]-= 0.01f;
+ oc->max[c]+= 0.01f;
}
- t00= co3[0]-co1[0];
- t01= co3[1]-co1[1];
- t02= co3[2]-co1[2];
- t10= co3[0]-co2[0];
- t11= co3[1]-co2[1];
- t12= co3[2]-co2[2];
-
- r0= is->vec[0];
- r1= is->vec[1];
- r2= is->vec[2];
+ t00= oc->max[0]-oc->min[0];
+ t01= oc->max[1]-oc->min[1];
+ t02= oc->max[2]-oc->min[2];
- x0= t12*r1-t11*r2;
- x1= t10*r2-t12*r0;
- x2= t11*r0-t10*r1;
-
- divdet= t00*x0+t01*x1+t02*x2;
-
- m0= is->start[0]-co3[0];
- m1= is->start[1]-co3[1];
- m2= is->start[2]-co3[2];
- det1= m0*x0+m1*x1+m2*x2;
+ /* this minus 0.1 is old safety... seems to be needed? */
+ oc->ocfacx= (oc->ocres-0.1)/t00;
+ oc->ocfacy= (oc->ocres-0.1)/t01;
+ oc->ocfacz= (oc->ocres-0.1)/t02;
- if(divdet!=0.0f) {
- float u;
+ oc->ocsize= sqrt(t00*t00+t01*t01+t02*t02); /* global, max size octree */
- divdet= 1.0f/divdet;
- u= det1*divdet;
- if(u<ISECT_EPSILON && u>-(1.0f+ISECT_EPSILON)) {
- float v, cros0, cros1, cros2;
-
- cros0= m1*t02-m2*t01;
- cros1= m2*t00-m0*t02;
- cros2= m0*t01-m1*t00;
- v= divdet*(cros0*r0 + cros1*r1 + cros2*r2);
-
- if(v<ISECT_EPSILON && (u + v) > -(1.0f+ISECT_EPSILON)) {
- float labda;
- labda= divdet*(cros0*t10 + cros1*t11 + cros2*t12);
-
- if(labda>-ISECT_EPSILON && labda<1.0f+ISECT_EPSILON) {
- is->labda= labda;
- is->u= u; is->v= v;
- ok= 1;
- }
- }
- }
+ for(c=0; c<oc->ro_nodes_used; c++)
+ {
+ octree_fill_rayface(oc, oc->ro_nodes[c]);
}
- if(ok==0 && v4) {
-
- t20= co3[0]-co4[0];
- t21= co3[1]-co4[1];
- t22= co3[2]-co4[2];
-
- divdet= t20*x0+t21*x1+t22*x2;
- if(divdet!=0.0f) {
- float u;
- divdet= 1.0f/divdet;
- u = det1*divdet;
-
- if(u<ISECT_EPSILON && u>-(1.0f+ISECT_EPSILON)) {
- float v, cros0, cros1, cros2;
- cros0= m1*t22-m2*t21;
- cros1= m2*t20-m0*t22;
- cros2= m0*t21-m1*t20;
- v= divdet*(cros0*r0 + cros1*r1 + cros2*r2);
+ MEM_freeN(oc->ocface);
+ oc->ocface = NULL;
+ MEM_freeN(oc->ro_nodes);
+ oc->ro_nodes = NULL;
- if(v<ISECT_EPSILON && (u + v) >-(1.0f+ISECT_EPSILON)) {
- float labda;
- labda= divdet*(cros0*t10 + cros1*t11 + cros2*t12);
-
- if(labda>-ISECT_EPSILON && labda<1.0f+ISECT_EPSILON) {
- ok= 2;
- is->labda= labda;
- is->u= u; is->v= v;
- }
- }
- }
- }
- }
-
- if(ok) {
- is->isect= ok; // wich half of the quad
-
- if(is->mode!=RE_RAY_SHADOW) {
- /* for mirror & tra-shadow: large faces can be filled in too often, this prevents
- a face being detected too soon... */
- if(is->labda > is->ddalabda) {
- return 0;
- }
- }
-
- /* when a shadow ray leaves a face, it can be little outside the edges of it, causing
- intersection to be detected in its neighbour face */
-
- if(is->facecontr && is->faceisect); // optimizing, the tests below are not needed
- else if(is->labda< .1) {
- RayFace *face= is->faceorig;
- float *origv1, *origv2, *origv3, *origv4;
- short de= 0;
-
- coordsfunc(face, &origv1, &origv2, &origv3, &origv4);
-
- if(ob == is->oborig) {
- if(v1==origv1 || v2==origv1 || v3==origv1 || v4==origv1) de++;
- if(v1==origv2 || v2==origv2 || v3==origv2 || v4==origv2) de++;
- if(v1==origv3 || v2==origv3 || v3==origv3 || v4==origv3) de++;
- if(origv4) {
- if(v1==origv4 || v2==origv4 || v3==origv4 || v4==origv4) de++;
- }
- }
- if(de) {
- /* so there's a shared edge or vertex, let's intersect ray with face
- itself, if that's true we can safely return 1, otherwise we assume
- the intersection is invalid, 0 */
-
- if(is->facecontr==NULL) {
- is->obcontr= is->oborig;
- is->facecontr= face;
- is->faceisect= intersection2(face, is->oborig, transformfunc, coordsfunc, is->userdata, -r0, -r1, -r2, is->start[0], is->start[1], is->start[2]);
- }
-
- if(is->faceisect) return 1;
- return 0;
- }
- }
-
- return 1;
- }
+ printf("%f %f - %f\n", oc->min[0], oc->max[0], oc->ocfacx );
+ printf("%f %f - %f\n", oc->min[1], oc->max[1], oc->ocfacy );
+ printf("%f %f - %f\n", oc->min[2], oc->max[2], oc->ocfacz );
+}
- return 0;
+static void RayObject_octree_bb(RayObject *tree, float *min, float *max)
+{
+ Octree *oc = (Octree*)tree;
+ DO_MINMAX(oc->min, min, max);
+ DO_MINMAX(oc->max, min, max);
}
/* check all faces in this node */
-static int testnode(Octree *oc, Isect *is, Node *no, OcVal ocval, RayCheckFunc checkfunc)
+static int testnode(Octree *oc, Isect *is, Node *no, OcVal ocval)
{
- RayFace *face;
- int ob;
short nr=0;
- OcVal *ov;
/* return on any first hit */
if(is->mode==RE_RAY_SHADOW) {
-
- face= no->v[0];
- ob= no->ob[0];
- while(face) {
-
- if(!(is->faceorig == face && is->oborig == ob)) {
-
- if(checkfunc(is, ob, face)) {
-
- ov= no->ov+nr;
- if( (ov->ocx & ocval.ocx) && (ov->ocy & ocval.ocy) && (ov->ocz & ocval.ocz) ) {
- //accepted++;
- is->ob= ob;
- is->face= face;
- if(RE_ray_face_intersection(is, oc->transformfunc, oc->coordsfunc)) {
- is->ob_last= ob;
- is->face_last= face;
- return 1;
- }
- }
- //else rejected++;
- }
- }
+ for(; no; no = no->next)
+ for(nr=0; nr<8; nr++)
+ {
+ RayFace *face = no->v[nr];
+ OcVal *ov = no->ov+nr;
- nr++;
- if(nr==8) {
- no= no->next;
- if(no==0) return 0;
- nr=0;
+ if(!face) break;
+
+ if( (ov->ocx & ocval.ocx) && (ov->ocy & ocval.ocy) && (ov->ocz & ocval.ocz) )
+ {
+ if( RE_rayobject_intersect( RayObject_unalignRayFace(face),is) )
+ return 1;
}
- face= no->v[nr];
- ob= no->ob[nr];
}
}
- else { /* else mirror or glass or shadowtra, return closest face */
- Isect isect;
+ else
+ { /* else mirror or glass or shadowtra, return closest face */
int found= 0;
- is->labda= 1.0f; /* needed? */
- isect= *is; /* copy for sorting */
-
- face= no->v[0];
- ob= no->ob[0];
- while(face) {
-
- if(!(is->faceorig == face && is->oborig == ob)) {
- if(checkfunc(is, ob, face)) {
- ov= no->ov+nr;
- if( (ov->ocx & ocval.ocx) && (ov->ocy & ocval.ocy) && (ov->ocz & ocval.ocz) ) {
- //accepted++;
-
- isect.ob= ob;
- isect.face= face;
- if(RE_ray_face_intersection(&isect, oc->transformfunc, oc->coordsfunc)) {
- if(isect.labda<is->labda) {
- *is= isect;
- found= 1;
- }
-
- }
- }
- //else rejected++;
- }
- }
+ for(; no; no = no->next)
+ for(nr=0; nr<8; nr++)
+ {
+ RayFace *face = no->v[nr];
+ OcVal *ov = no->ov+nr;
+
+ if(!face) break;
- nr++;
- if(nr==8) {
- no= no->next;
- if(no==NULL) break;
- nr=0;
+ if( (ov->ocx & ocval.ocx) && (ov->ocy & ocval.ocy) && (ov->ocz & ocval.ocz) )
+ {
+ if( RE_rayobject_intersect( RayObject_unalignRayFace(face),is) )
+ found= 1;
}
- face= no->v[nr];
- ob= no->ob[nr];
}
return found;
*/
-int RE_ray_tree_intersect(RayTree *tree, Isect *is)
-{
- Octree *oc= (Octree*)tree;
-
- return RE_ray_tree_intersect_check(tree, is, oc->checkfunc);
-}
-
/* return 1: found valid intersection */
-/* starts with is->faceorig */
-int RE_ray_tree_intersect_check(RayTree *tree, Isect *is, RayCheckFunc checkfunc)
+/* starts with is->orig.face */
+static int RayObject_octree_intersect(RayObject *tree, Isect *is)
{
Octree *oc= (Octree*)tree;
Node *no;
OcVal ocval;
- float vec1[3], vec2[3];
+ float vec1[3], vec2[3], start[3], end[3];
float u1,u2,ox1,ox2,oy1,oy2,oz1,oz2;
float labdao,labdax,ldx,labday,ldy,labdaz,ldz, ddalabda;
+ float olabda = 0;
int dx,dy,dz;
int xo,yo,zo,c1=0;
int ocx1,ocx2,ocy1, ocy2,ocz1,ocz2;
if(oc->branchcount==0) return 0;
/* do this before intersect calls */
+#if 0
is->facecontr= NULL; /* to check shared edge */
is->obcontr= 0;
is->faceisect= is->isect= 0; /* shared edge, quad half flag */
is->userdata= oc->userdata;
+#endif
- /* only for shadow! */
- if(is->mode==RE_RAY_SHADOW) {
-
- /* check with last intersected shadow face */
- if(is->face_last!=NULL && !(is->face_last==is->faceorig && is->ob_last==is->oborig)) {
- if(checkfunc(is, is->ob_last, is->face_last)) {
- is->ob= is->ob_last;
- is->face= is->face_last;
- VECSUB(is->vec, is->end, is->start);
- if(RE_ray_face_intersection(is, oc->transformfunc, oc->coordsfunc)) return 1;
- }
- }
- }
-
- ldx= is->end[0] - is->start[0];
+ VECCOPY( start, is->start );
+ VECADDFAC( end, is->start, is->vec, is->labda );
+ ldx= is->vec[0]*is->labda;
+ olabda = is->labda;
u1= 0.0f;
u2= 1.0f;
-
+
/* clip with octree cube */
- if(cliptest(-ldx, is->start[0]-oc->min[0], &u1,&u2)) {
- if(cliptest(ldx, oc->max[0]-is->start[0], &u1,&u2)) {
- ldy= is->end[1] - is->start[1];
- if(cliptest(-ldy, is->start[1]-oc->min[1], &u1,&u2)) {
- if(cliptest(ldy, oc->max[1]-is->start[1], &u1,&u2)) {
- ldz= is->end[2] - is->start[2];
- if(cliptest(-ldz, is->start[2]-oc->min[2], &u1,&u2)) {
- if(cliptest(ldz, oc->max[2]-is->start[2], &u1,&u2)) {
+ if(cliptest(-ldx, start[0]-oc->min[0], &u1,&u2)) {
+ if(cliptest(ldx, oc->max[0]-start[0], &u1,&u2)) {
+ ldy= is->vec[1]*is->labda;
+ if(cliptest(-ldy, start[1]-oc->min[1], &u1,&u2)) {
+ if(cliptest(ldy, oc->max[1]-start[1], &u1,&u2)) {
+ ldz = is->vec[2]*is->labda;
+ if(cliptest(-ldz, start[2]-oc->min[2], &u1,&u2)) {
+ if(cliptest(ldz, oc->max[2]-start[2], &u1,&u2)) {
c1=1;
if(u2<1.0f) {
- is->end[0]= is->start[0]+u2*ldx;
- is->end[1]= is->start[1]+u2*ldy;
- is->end[2]= is->start[2]+u2*ldz;
+ end[0] = start[0]+u2*ldx;
+ end[1] = start[1]+u2*ldy;
+ end[2] = start[2]+u2*ldz;
}
+
if(u1>0.0f) {
- is->start[0]+=u1*ldx;
- is->start[1]+=u1*ldy;
- is->start[2]+=u1*ldz;
+ start[0] += u1*ldx;
+ start[1] += u1*ldy;
+ start[2] += u1*ldz;
}
}
}
//ocread(oc, oc->ocres, 0, 0);
/* setup 3dda to traverse octree */
- ox1= (is->start[0]-oc->min[0])*oc->ocfacx;
- oy1= (is->start[1]-oc->min[1])*oc->ocfacy;
- oz1= (is->start[2]-oc->min[2])*oc->ocfacz;
- ox2= (is->end[0]-oc->min[0])*oc->ocfacx;
- oy2= (is->end[1]-oc->min[1])*oc->ocfacy;
- oz2= (is->end[2]-oc->min[2])*oc->ocfacz;
+ ox1= (start[0]-oc->min[0])*oc->ocfacx;
+ oy1= (start[1]-oc->min[1])*oc->ocfacy;
+ oz1= (start[2]-oc->min[2])*oc->ocfacz;
+ ox2= (end[0]-oc->min[0])*oc->ocfacx;
+ oy2= (end[1]-oc->min[1])*oc->ocfacy;
+ oz2= (end[2]-oc->min[2])*oc->ocfacz;
ocx1= (int)ox1;
ocy1= (int)oy1;
ocx2= (int)ox2;
ocy2= (int)oy2;
ocz2= (int)oz2;
-
- /* for intersection */
- VECSUB(is->vec, is->end, is->start);
-
+
if(ocx1==ocx2 && ocy1==ocy2 && ocz1==ocz2) {
no= ocread(oc, ocx1, ocy1, ocz1);
if(no) {
vec1[0]= ox1; vec1[1]= oy1; vec1[2]= oz1;
vec2[0]= ox2; vec2[1]= oy2; vec2[2]= oz2;
calc_ocval_ray(&ocval, (float)ocx1, (float)ocy1, (float)ocz1, vec1, vec2);
- is->ddalabda= 1.0f;
- if( testnode(oc, is, no, ocval, checkfunc) ) return 1;
+ if( testnode(oc, is, no, ocval) ) return 1;
}
}
else {
+ int found = 0;
//static int coh_ocx1,coh_ocx2,coh_ocy1, coh_ocy2,coh_ocz1,coh_ocz2;
float dox, doy, doz;
int eqval;
vec2[1]= oy1-ddalabda*doy;
vec2[2]= oz1-ddalabda*doz;
calc_ocval_ray(&ocval, (float)xo, (float)yo, (float)zo, vec1, vec2);
-
- is->ddalabda= ddalabda;
- if( testnode(oc, is, no, ocval, checkfunc) ) return 1;
+
+ //is->labda = (u1+ddalabda*(u2-u1))*olabda;
+ if( testnode(oc, is, no, ocval) )
+ found = 1;
+
+ if(is->labda < (u1+ddalabda*(u2-u1))*olabda)
+ return found;
}
+
labdao= ddalabda;
/* traversing ocree nodes need careful detection of smallest values, with proper
}
/* reached end, no intersections found */
- is->ob_last= 0;
- is->face_last= NULL;
return 0;
}
-float RE_ray_tree_max_size(RayTree *tree)
-{
- return ((Octree*)tree)->ocsize;
-}
+
#include <string.h>
#include <stdlib.h>
#include <float.h>
+#include <assert.h>
#include "MEM_guardedalloc.h"
#include "texture.h"
#include "RE_raytrace.h"
+#include "rayobject.h"
#define RAY_TRA 1
#define RAY_TRAFLIP 2
extern struct Render R;
/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ */
-static void vlr_face_coords(RayFace *face, float **v1, float **v2, float **v3, float **v4)
+RayObject * RE_rayobject_tree_create(int type, int size) __attribute__((noinline));
+
+RayObject * RE_rayobject_tree_create(int type, int size)
{
- VlakRen *vlr= (VlakRen*)face;
+// if(type == R_RAYTRACE_TREE_BIH)
+ return RE_rayobject_vbvh_create(size);
+
+ if(type == R_RAYTRACE_TREE_BVH)
+ return RE_rayobject_bvh_create(size);
+ if(type == R_RAYTRACE_TREE_BIH)
+ return RE_rayobject_bih_create(size);
+ if(type == R_RAYTRACE_TREE_BLIBVH)
+ return RE_rayobject_blibvh_create(size);
- *v1 = (vlr->v1)? vlr->v1->co: NULL;
- *v2 = (vlr->v2)? vlr->v2->co: NULL;
- *v3 = (vlr->v3)? vlr->v3->co: NULL;
- *v4 = (vlr->v4)? vlr->v4->co: NULL;
}
+#ifdef RE_RAYCOUNTER
+RayCounter re_rc_counter[BLENDER_MAX_THREADS] = {};
+#endif
+
+#if 0
static int vlr_check_intersect(Isect *is, int ob, RayFace *face)
{
ObjectInstanceRen *obi= RAY_OBJECT_GET((Render*)is->userdata, ob);
else
return (is->lay & obi->lay);
}
+#endif
-static float *vlr_get_transform(void *userdata, int i)
+void freeraytree(Render *re)
{
- ObjectInstanceRen *obi= RAY_OBJECT_GET((Render*)userdata, i);
+ ObjectInstanceRen *obi;
+
+ if(re->raytree)
+ {
+ RE_rayobject_free(re->raytree);
+ re->raytree = NULL;
+ }
+ if(re->rayfaces)
+ {
+ MEM_freeN(re->rayfaces);
+ re->rayfaces = NULL;
+ }
- return (obi->flag & R_TRANSFORMED)? (float*)obi->mat: NULL;
+ for(obi=re->instancetable.first; obi; obi=obi->next)
+ {
+ ObjectRen *obr = obi->obr;
+ if(obr->raytree)
+ {
+ RE_rayobject_free(obr->raytree);
+ obr->raytree = NULL;
+ }
+ if(obr->rayfaces)
+ {
+ MEM_freeN(obr->rayfaces);
+ obr->rayfaces = NULL;
+ }
+ if(obi->raytree)
+ {
+ RE_rayobject_free(obi->raytree);
+ obi->raytree = NULL;
+ }
+ }
+
+#ifdef RE_RAYCOUNTER
+ {
+ RayCounter sum = {};
+ int i;
+ for(i=0; i<BLENDER_MAX_THREADS; i++)
+ RE_RC_MERGE(&sum, re_rc_counter+i);
+ RE_RC_INFO(&sum);
+ }
+#endif
}
-void freeraytree(Render *re)
+static int is_raytraceable_vlr(Render *re, VlakRen *vlr)
{
- if(re->raytree) {
- RE_ray_tree_free(re->raytree);
- re->raytree= NULL;
- }
+ if((re->flag & R_BAKE_TRACE) || (vlr->mat->mode & MA_TRACEBLE))
+ if(vlr->mat->material_type != MA_TYPE_WIRE)
+ return 1;
+ return 0;
}
-void makeraytree(Render *re)
+static int is_raytraceable(Render *re, ObjectInstanceRen *obi)
{
- ObjectInstanceRen *obi;
- ObjectRen *obr;
- VlakRen *vlr= NULL;
- float min[3], max[3], co1[3], co2[3], co3[3], co4[3];
- double lasttime= PIL_check_seconds_timer();
- int v, totv = 0, totface = 0;
+ int v;
+ ObjectRen *obr = obi->obr;
- INIT_MINMAX(min, max);
+ if(re->excludeob && obr->ob == re->excludeob)
+ return 0;
- /* first min max raytree space */
- for(obi=re->instancetable.first; obi; obi=obi->next) {
- obr= obi->obr;
-
- if(re->excludeob && obr->ob == re->excludeob)
- continue;
-
- for(v=0;v<obr->totvlak;v++) {
- if((v & 255)==0) vlr= obr->vlaknodes[v>>8].vlak;
- else vlr++;
- /* baking selected to active needs non-traceable too */
- if((re->flag & R_BAKE_TRACE) || (vlr->mat->mode & MA_TRACEBLE)) {
- if(vlr->mat->material_type != MA_TYPE_WIRE) {
- VECCOPY(co1, vlr->v1->co);
- VECCOPY(co2, vlr->v2->co);
- VECCOPY(co3, vlr->v3->co);
-
- if(obi->flag & R_TRANSFORMED) {
- Mat4MulVecfl(obi->mat, co1);
- Mat4MulVecfl(obi->mat, co2);
- Mat4MulVecfl(obi->mat, co3);
- }
+ for(v=0;v<obr->totvlak;v++)
+ {
+ VlakRen *vlr = obr->vlaknodes[v>>8].vlak + (v&255);
+ if(is_raytraceable_vlr(re, vlr))
+ return 1;
+ }
+ return 0;
+}
- DO_MINMAX(co1, min, max);
- DO_MINMAX(co2, min, max);
- DO_MINMAX(co3, min, max);
- if(vlr->v4) {
- VECCOPY(co4, vlr->v4->co);
- if(obi->flag & R_TRANSFORMED)
- Mat4MulVecfl(obi->mat, co4);
- DO_MINMAX(co4, min, max);
- }
+RayObject* makeraytree_object(Render *re, ObjectInstanceRen *obi)
+{
+ //TODO
+ // out-of-memory safeproof
+ // break render
+ // update render stats
+ ObjectRen *obr = obi->obr;
+
+ if(obr->raytree == NULL)
+ {
+ RayObject *raytree;
+ RayFace *face;
+ int v;
+
+ //Count faces
+ int faces = 0;
+ for(v=0;v<obr->totvlak;v++)
+ {
+ VlakRen *vlr = obr->vlaknodes[v>>8].vlak + (v&255);
+ if(is_raytraceable_vlr(re, vlr))
+ faces++;
+ }
+ assert( faces > 0 );
- totface++;
- }
+ //Create Ray cast accelaration structure
+
+ //TODO dynamic ocres
+ if(re->r.raystructure == R_RAYSTRUCTURE_HIER_BVH_OCTREE)
+ raytree = obr->raytree = RE_rayobject_octree_create( re->r.ocres, faces );
+ else //if(re->r.raystructure == R_RAYSTRUCTURE_HIER_BVH_BVH)
+ raytree = obr->raytree = RE_rayobject_tree_create( re->r.raytrace_tree_type, faces );
+
+ face = obr->rayfaces = (RayFace*)MEM_callocN(faces*sizeof(RayFace), "ObjectRen faces");
+ obr->rayobi = obi;
+
+ for(v=0;v<obr->totvlak;v++)
+ {
+ VlakRen *vlr = obr->vlaknodes[v>>8].vlak + (v&255);
+ if(is_raytraceable_vlr(re, vlr))
+ {
+ RE_rayface_from_vlak( face, obi, vlr );
+ RE_rayobject_add( raytree, RayObject_unalignRayFace(face) );
+ face++;
}
}
+ RE_rayobject_done( raytree );
}
- re->raytree= RE_ray_tree_create(re->r.ocres, totface, min, max,
- vlr_face_coords, vlr_check_intersect, vlr_get_transform, re);
- if(min[0] > max[0]) { /* empty raytree */
- RE_ray_tree_done(re->raytree);
- return;
+ if(obi->flag & R_TRANSFORMED)
+ {
+ obi->raytree = RE_rayobject_instance_create( obr->raytree, obi->mat, obi, obi->obr->rayobi );
}
+
+ if(obi->raytree) return obi->raytree;
+ return obi->obr->raytree;
+}
- for(obi=re->instancetable.first; obi; obi=obi->next) {
- obr= obi->obr;
+/*
+ * create an hierarchic raytrace structure with all objects
+ *
+ * R_TRANSFORMED objects instances reuse the same tree by using the rayobject_instance
+ */
+static void makeraytree_hier(Render *re)
+{
+ //TODO
+ // out-of-memory safeproof
+ // break render
+ // update render stats
- if(re->excludeob && obr->ob == re->excludeob)
- continue;
+ ObjectInstanceRen *obi;
+ int num_objects = 0;
- for(v=0; v<obr->totvlak; v++, totv++) {
- if((v & 255)==0) {
- double time= PIL_check_seconds_timer();
+ re->i.infostr="Creating raytrace structure";
+ re->stats_draw(re->sdh, &re->i);
- vlr= obr->vlaknodes[v>>8].vlak;
- if(re->test_break(re->tbh))
- break;
- if(time-lasttime>1.0f) {
- char str[32];
- sprintf(str, "Filling Octree: %d", totv);
- re->i.infostr= str;
- re->stats_draw(re->sdh, &re->i);
- re->i.infostr= NULL;
- lasttime= time;
- }
+ //Count number of objects
+ for(obi=re->instancetable.first; obi; obi=obi->next)
+ if(is_raytraceable(re, obi))
+ num_objects++;
+
+ //Create raytree
+ re->raytree = RE_rayobject_tree_create( re->r.raytrace_tree_type, num_objects );
+
+ for(obi=re->instancetable.first; obi; obi=obi->next)
+ if(is_raytraceable(re, obi))
+ {
+ RayObject *obj = makeraytree_object(re, obi);
+ RE_rayobject_add( re->raytree, obj );
+
+ if(re->test_break(re->tbh))
+ break;
+ }
+
+ if(!re->test_break(re->tbh))
+ {
+ RE_rayobject_done( re->raytree );
+ }
+
+ re->i.infostr= NULL;
+ re->stats_draw(re->sdh, &re->i);
+}
+
+static int has_special_rayobject(Render *re, ObjectInstanceRen *obi)
+{
+ if( (obi->flag & R_TRANSFORMED) )
+ {
+ ObjectRen *obr = obi->obr;
+ int v, faces = 0;
+
+ for(v=0;v<obr->totvlak;v++)
+ {
+ VlakRen *vlr = obr->vlaknodes[v>>8].vlak + (v&255);
+ if(is_raytraceable_vlr(re, vlr))
+ {
+ faces++;
+ if(faces > 4)
+ return 1;
}
- else vlr++;
-
- if((re->flag & R_BAKE_TRACE) || (vlr->mat->mode & MA_TRACEBLE))
- if(vlr->mat->material_type != MA_TYPE_WIRE)
- RE_ray_tree_add_face(re->raytree, RAY_OBJECT_SET(re, obi), vlr);
}
}
+ return 0;
+}
+/*
+ * create a single raytrace structure with all faces
+ */
+static void makeraytree_single(Render *re)
+{
+ ObjectInstanceRen *obi;
+ RayObject *raytree;
+ RayFace *face;
+ int faces = 0, obs = 0;
- RE_ray_tree_done(re->raytree);
+ for(obi=re->instancetable.first; obi; obi=obi->next)
+ if(is_raytraceable(re, obi))
+ {
+ int v;
+ ObjectRen *obr = obi->obr;
+ obs++;
+
+ if(has_special_rayobject(re, obi))
+ {
+ faces++;
+ }
+ else
+ {
+ for(v=0;v<obr->totvlak;v++)
+ {
+ VlakRen *vlr = obr->vlaknodes[v>>8].vlak + (v&255);
+ if(is_raytraceable_vlr(re, vlr))
+ faces++;
+ }
+ }
+ }
- re->i.infostr= NULL;
- re->stats_draw(re->sdh, &re->i);
+ //Create raytree
+ if(re->r.raystructure == R_RAYSTRUCTURE_SINGLE_OCTREE)
+ raytree = re->raytree = RE_rayobject_octree_create( re->r.ocres, faces );
+ else //if(re->r.raystructure == R_RAYSTRUCTURE_SINGLE_BVH)
+ raytree = re->raytree = RE_rayobject_tree_create( re->r.raytrace_tree_type, faces );
+
+ face = re->rayfaces = (RayFace*)MEM_callocN(faces*sizeof(RayFace), "Render ray faces");
+
+ for(obi=re->instancetable.first; obi; obi=obi->next)
+ if(is_raytraceable(re, obi))
+ {
+ if(has_special_rayobject(re, obi))
+ {
+ RayObject *obj = makeraytree_object(re, obi);
+ RE_rayobject_add( re->raytree, obj );
+ }
+ else
+ {
+ int v;
+ ObjectRen *obr = obi->obr;
+
+ for(v=0;v<obr->totvlak;v++)
+ {
+ VlakRen *vlr = obr->vlaknodes[v>>8].vlak + (v&255);
+ if(is_raytraceable_vlr(re, vlr))
+ {
+ RE_rayface_from_vlak(face, obi, vlr);
+ if((obi->flag & R_TRANSFORMED))
+ {
+ Mat4MulVecfl(obi->mat, face->v1);
+ Mat4MulVecfl(obi->mat, face->v2);
+ Mat4MulVecfl(obi->mat, face->v3);
+ if(RE_rayface_isQuad(face))
+ Mat4MulVecfl(obi->mat, face->v4);
+ }
+
+ RE_rayobject_add( raytree, RayObject_unalignRayFace(face) );
+ face++;
+ }
+ }
+ }
+ }
+ RE_rayobject_done( raytree );
+}
+
+void makeraytree(Render *re)
+{
+ float min[3], max[3], sub[3];
+ int i;
+ const char *tree_type = "Tree(unknown)";
+
+ re->r.raystructure = R_RAYSTRUCTURE_SINGLE_BVH;
+#ifdef RE_RAYCOUNTER
+ if(re->r.raytrace_tree_type == R_RAYTRACE_TREE_BVH)
+ tree_type = "BVH";
+ if(re->r.raytrace_tree_type == R_RAYTRACE_TREE_BIH)
+ tree_type = "BIH";
+ if(re->r.raytrace_tree_type == R_RAYTRACE_TREE_BLIBVH)
+ tree_type = "BLIBVH";
+
+ if(re->r.raystructure == R_RAYSTRUCTURE_SINGLE_OCTREE)
+ printf("Building single octree\n");
+ else if(re->r.raystructure == R_RAYSTRUCTURE_SINGLE_BVH)
+ printf("Building single tree(%s)\n", tree_type);
+ else if(re->r.raystructure == R_RAYSTRUCTURE_HIER_BVH_OCTREE)
+ printf("Building tree(%s) of octrees\n", tree_type);
+ else
+ printf("Building tree(%s) of trees(%s)\n", tree_type, tree_type);
+#endif
+
+ if(ELEM(re->r.raystructure, R_RAYSTRUCTURE_SINGLE_BVH, R_RAYSTRUCTURE_SINGLE_OCTREE))
+ BENCH(makeraytree_single(re), tree_build);
+ else
+ BENCH(makeraytree_hier(re), tree_build);
+
+
+ //Calculate raytree max_size
+ //This is ONLY needed to kept a bogus behaviour of SUN and HEMI lights
+ RE_rayobject_merge_bb( re->raytree, min, max );
+ for(i=0; i<3; i++)
+ {
+ min[i] += 0.01f;
+ max[i] += 0.01f;
+ sub[i] = max[i]-min[i];
+ }
+ re->maxdist = sqrt( sub[0]*sub[0] + sub[1]*sub[1] + sub[2]*sub[2] );
}
+
+
static void shade_ray(Isect *is, ShadeInput *shi, ShadeResult *shr)
{
- VlakRen *vlr= (VlakRen*)is->face;
- ObjectInstanceRen *obi= RAY_OBJECT_GET(&R, is->ob);
+ ObjectInstanceRen *obi= (ObjectInstanceRen*)is->hit.ob;
+ VlakRen *vlr= (VlakRen*)is->hit.face;
int osatex= 0;
/* set up view vector */
ShadeResult shr;
Isect isec;
float f, f1, fr, fg, fb;
- float ref[3], maxsize=RE_ray_tree_max_size(R.raytree);
+ float ref[3];
float dist_mir = origshi->mat->dist_mir;
/* Warning, This is not that nice, and possibly a bit slow for every ray,
/* end warning! - Campbell */
VECCOPY(isec.start, start);
- if (dist_mir > 0.0) {
- isec.end[0]= start[0]+dist_mir*vec[0];
- isec.end[1]= start[1]+dist_mir*vec[1];
- isec.end[2]= start[2]+dist_mir*vec[2];
- } else {
- isec.end[0]= start[0]+maxsize*vec[0];
- isec.end[1]= start[1]+maxsize*vec[1];
- isec.end[2]= start[2]+maxsize*vec[2];
- }
+ VECCOPY(isec.vec, vec );
+ isec.labda = dist_mir > 0 ? dist_mir : RE_RAYTRACE_MAXDIST;
isec.mode= RE_RAY_MIRROR;
- isec.faceorig= (RayFace*)vlr;
- isec.oborig= RAY_OBJECT_SET(&R, obi);
+ isec.skip = RE_SKIP_VLR_NEIGHBOUR;
+ isec.hint = 0;
+
+ isec.orig.ob = obi;
+ isec.orig.face = vlr;
+ RE_RC_INIT(isec, shi);
- if(RE_ray_tree_intersect(R.raytree, &isec)) {
+ if(RE_rayobject_raycast(R.raytree, &isec)) {
float d= 1.0f;
shi.mask= origshi->mask;
else {
ray_fadeout_endcolor(col, origshi, &shi, origshr, &isec, vec);
}
+ RE_RC_MERGE(&origshi->raycounter, &shi.raycounter);
}
/* **************** jitter blocks ********** */
do_tra= ((shi->mat->mode & MA_TRANSP) && (shi->mat->mode & MA_RAYTRANSP) && shr->alpha!=1.0f);
do_mir= ((shi->mat->mode & MA_RAYMIRROR) && shi->ray_mirror!=0.0f);
-
/* raytrace mirror amd refract like to separate the spec color */
if(shi->combinedflag & SCE_PASS_SPEC)
if it has col[3]>0.0f continue. so exit when alpha is full */
ShadeInput shi;
ShadeResult shr;
-
- if(RE_ray_tree_intersect(R.raytree, is)) {
+ float initial_labda = is->labda;
+
+ if(RE_rayobject_raycast(R.raytree, is)) {
float d= 1.0f;
/* we got a face */
/* adapt isect struct */
VECCOPY(is->start, shi.co);
- is->oborig= RAY_OBJECT_SET(&R, shi.obi);
- is->faceorig= (RayFace*)shi.vlr;
+ is->labda = initial_labda-is->labda;
+ is->orig.ob = shi.obi;
+ is->orig.face = shi.vlr;
ray_trace_shadow_tra(is, origshi, depth-1, traflag | RAY_TRA);
}
+
+ RE_RC_MERGE(&origshi->raycounter, &shi.raycounter);
}
}
Isect isec;
ShadeInput shi;
ShadeResult shr_t;
- float vec[3], accum[3], div= 0.0f, maxsize= RE_ray_tree_max_size(R.raytree);
+ float vec[3], accum[3], div= 0.0f;
int a;
+ assert(0);
+
if(only_one) {
return 0;
}
accum[0]= accum[1]= accum[2]= 0.0f;
isec.mode= RE_RAY_MIRROR;
- isec.faceorig= (RayFace*)ship->vlr;
- isec.oborig= RAY_OBJECT_SET(&R, ship->obi);
+ isec.orig.ob = ship->obi;
+ isec.orig.face = ship->vlr;
+ isec.hint = 0;
+
+ VECCOPY(isec.start, ship->co);
+
+ RE_RC_INIT(isec, shi);
for(a=0; a<8*8; a++) {
vec[1]-= vec[1];
vec[2]-= vec[2];
}
- VECCOPY(isec.start, ship->co);
- isec.end[0]= isec.start[0] + maxsize*vec[0];
- isec.end[1]= isec.start[1] + maxsize*vec[1];
- isec.end[2]= isec.start[2] + maxsize*vec[2];
-
- if(RE_ray_tree_intersect(R.raytree, &isec)) {
+
+ VECCOPY(isec.vec, vec );
+ isec.labda = RE_RAYTRACE_MAXDIST;
+
+ if(RE_rayobject_raycast(R.raytree, &isec)) {
float fac;
/* Warning, This is not that nice, and possibly a bit slow for every ray,
static void ray_ao_qmc(ShadeInput *shi, float *shadfac)
{
Isect isec;
+ RayHint point_hint;
QMCSampler *qsa=NULL;
float samp3d[3];
float up[3], side[3], dir[3], nrm[3];
float dxyview[3], skyadded=0, div;
int aocolor;
- isec.faceorig= (RayFace*)shi->vlr;
- isec.oborig= RAY_OBJECT_SET(&R, shi->obi);
- isec.face_last= NULL;
- isec.ob_last= 0;
+ RE_RC_INIT(isec, *shi);
+ isec.orig.ob = shi->obi;
+ isec.orig.face = shi->vlr;
+ isec.skip = RE_SKIP_VLR_NEIGHBOUR;
+ isec.hint = 0;
+
+ isec.hit.ob = 0;
+ isec.hit.face = 0;
+
+ isec.last_hit = NULL;
+
isec.mode= (R.wrld.aomode & WO_AODIST)?RE_RAY_SHADOW_TRA:RE_RAY_SHADOW;
isec.lay= -1;
+ VECCOPY(isec.start, shi->co);
+ RE_rayobject_hint_bb( R.raytree, &point_hint, isec.start, isec.start );
+ isec.hint = &point_hint;
+
+
shadfac[0]= shadfac[1]= shadfac[2]= 0.0f;
/* prevent sky colors to be added for only shadow (shadow becomes alpha) */
QMC_initPixel(qsa, shi->thread);
+
while (samples < max_samples) {
/* sampling, returns quasi-random vector in unit hemisphere */
Normalize(dir);
- VECCOPY(isec.start, shi->co);
- isec.end[0] = shi->co[0] - maxdist*dir[0];
- isec.end[1] = shi->co[1] - maxdist*dir[1];
- isec.end[2] = shi->co[2] - maxdist*dir[2];
+ isec.vec[0] = -dir[0];
+ isec.vec[1] = -dir[1];
+ isec.vec[2] = -dir[2];
+ isec.labda = maxdist;
prev = fac;
- if(RE_ray_tree_intersect(R.raytree, &isec)) {
+ if(RE_rayobject_raycast(R.raytree, &isec)) {
if (R.wrld.aomode & WO_AODIST) fac+= exp(-isec.labda*R.wrld.aodistfac);
else fac+= 1.0f;
}
static void ray_ao_spheresamp(ShadeInput *shi, float *shadfac)
{
Isect isec;
+ RayHint point_hint;
float *vec, *nrm, div, bias, sh=0.0f;
float maxdist = R.wrld.aodist;
float dxyview[3];
int j= -1, tot, actual=0, skyadded=0, aocolor, resol= R.wrld.aosamp;
- isec.faceorig= (RayFace*)shi->vlr;
- isec.oborig= RAY_OBJECT_SET(&R, shi->obi);
- isec.face_last= NULL;
- isec.ob_last= 0;
+ RE_RC_INIT(isec, *shi);
+ isec.orig.ob = shi->obi;
+ isec.orig.face = shi->vlr;
+ isec.skip = RE_SKIP_VLR_NEIGHBOUR;
+ isec.hint = 0;
+
+ isec.hit.ob = 0;
+ isec.hit.face = 0;
+
+ isec.last_hit = NULL;
+
isec.mode= (R.wrld.aomode & WO_AODIST)?RE_RAY_SHADOW_TRA:RE_RAY_SHADOW;
isec.lay= -1;
+ VECCOPY(isec.start, shi->co);
+ RE_rayobject_hint_bb( R.raytree, &point_hint, isec.start, isec.start );
+ isec.hint = &point_hint;
shadfac[0]= shadfac[1]= shadfac[2]= 0.0f;
actual++;
- /* always set start/end, RE_ray_tree_intersect clips it */
- VECCOPY(isec.start, shi->co);
- isec.end[0] = shi->co[0] - maxdist*vec[0];
- isec.end[1] = shi->co[1] - maxdist*vec[1];
- isec.end[2] = shi->co[2] - maxdist*vec[2];
+ /* always set start/vec/labda */
+ isec.vec[0] = -vec[0];
+ isec.vec[1] = -vec[1];
+ isec.vec[2] = -vec[2];
+ isec.labda = maxdist;
/* do the trace */
- if(RE_ray_tree_intersect(R.raytree, &isec)) {
+ if(RE_rayobject_raycast(R.raytree, &isec)) {
if (R.wrld.aomode & WO_AODIST) sh+= exp(-isec.labda*R.wrld.aodistfac);
else sh+= 1.0f;
}
int samples=0;
float samp3d[3];
- float fac=0.0f, vec[3];
+ float fac=0.0f, vec[3], end[3];
float colsq[4];
float adapt_thresh = lar->adapt_thresh;
int min_adapt_samples=4, max_samples = lar->ray_totsamp;
float *co;
- int do_soft=1, full_osa=0;
+ int do_soft=1, full_osa=0, i;
+
+ float min[3], max[3];
+ RayHint bb_hint;
float jitco[RE_MAX_OSA][3];
int totjitco;
qsa = get_thread_qmcsampler(&R, shi->thread, SAMP_TYPE_HAMMERSLEY, max_samples);
QMC_initPixel(qsa, shi->thread);
+
+ INIT_MINMAX(min, max);
+ for(i=0; i<totjitco; i++)
+ {
+ DO_MINMAX(jitco[i], min, max);
+ }
+ RE_rayobject_hint_bb( R.raytree, &bb_hint, min, max);
+ isec->hint = &bb_hint;
+ isec->skip = RE_SKIP_VLR_NEIGHBOUR;
VECCOPY(vec, lampco);
-
while (samples < max_samples) {
- isec->faceorig= (RayFace*)shi->vlr;
- isec->oborig= RAY_OBJECT_SET(&R, shi->obi);
+
+ isec->orig.ob = shi->obi;
+ isec->orig.face = shi->vlr;
/* manually jitter the start shading co-ord per sample
* based on the pre-generated OSA texture sampling offsets,
/* align samples to lamp vector */
Mat3MulVecfl(lar->mat, samp3d);
}
- isec->end[0]= vec[0]+samp3d[0];
- isec->end[1]= vec[1]+samp3d[1];
- isec->end[2]= vec[2]+samp3d[2];
+ end[0] = vec[0]+samp3d[0];
+ end[1] = vec[1]+samp3d[1];
+ end[2] = vec[2]+samp3d[2];
} else {
- VECCOPY(isec->end, vec);
+ VECCOPY(end, vec);
}
if(shi->strand) {
float jitbias= 0.5f*(VecLength(shi->dxco) + VecLength(shi->dyco));
float v[3];
- VECSUB(v, co, isec->end);
+ VECSUB(v, co, end);
Normalize(v);
co[0] -= jitbias*v[0];
}
VECCOPY(isec->start, co);
+ isec->vec[0] = end[0]-isec->start[0];
+ isec->vec[1] = end[1]-isec->start[1];
+ isec->vec[2] = end[2]-isec->start[2];
+ isec->labda = 1.0f; // * Normalize(isec->vec);
/* trace the ray */
if(isec->mode==RE_RAY_SHADOW_TRA) {
colsq[2] += isec->col[2]*isec->col[2];
}
else {
- if( RE_ray_tree_intersect(R.raytree, isec) ) fac+= 1.0f;
+ if( RE_rayobject_raycast(R.raytree, isec) ) fac+= 1.0f;
}
samples++;
float *jitlamp;
float fac=0.0f, div=0.0f, vec[3];
int a, j= -1, mask;
+ RayHint point_hint;
if(isec->mode==RE_RAY_SHADOW_TRA) {
shadfac[0]= shadfac[1]= shadfac[2]= shadfac[3]= 0.0f;
if(a==4) mask |= (mask>>4)|(mask>>8);
else if(a==9) mask |= (mask>>9);
+ VECCOPY(isec->start, shi->co);
+ isec->orig.ob = shi->obi;
+ isec->orig.face = shi->vlr;
+ RE_rayobject_hint_bb( R.raytree, &point_hint, isec->start, isec->start );
+ isec->hint = &point_hint;
+
while(a--) {
if(R.r.mode & R_OSA) {
}
}
- isec->faceorig= (RayFace*)shi->vlr;
- isec->oborig= RAY_OBJECT_SET(&R, shi->obi);
-
vec[0]= jitlamp[0];
vec[1]= jitlamp[1];
vec[2]= 0.0f;
Mat3MulVecfl(lar->mat, vec);
- /* set start and end, RE_ray_tree_intersect clips it */
- VECCOPY(isec->start, shi->co);
- isec->end[0]= lampco[0]+vec[0];
- isec->end[1]= lampco[1]+vec[1];
- isec->end[2]= lampco[2]+vec[2];
+ /* set start and vec */
+ isec->vec[0] = vec[0]+lampco[0]-isec->start[0];
+ isec->vec[1] = vec[1]+lampco[1]-isec->start[1];
+ isec->vec[2] = vec[2]+lampco[2]-isec->start[2];
+ isec->labda = 1.0f;
+ isec->skip = RE_SKIP_VLR_NEIGHBOUR;
if(isec->mode==RE_RAY_SHADOW_TRA) {
/* isec.col is like shadfac, so defines amount of light (0.0 is full shadow) */
shadfac[2] += isec->col[2];
shadfac[3] += isec->col[3];
}
- else if( RE_ray_tree_intersect(R.raytree, isec) ) fac+= 1.0f;
+ else if( RE_rayobject_raycast(R.raytree, isec) ) fac+= 1.0f;
div+= 1.0f;
jitlamp+= 2;
void ray_shadow(ShadeInput *shi, LampRen *lar, float *shadfac)
{
Isect isec;
- float lampco[3], maxsize;
+ float lampco[3];
/* setup isec */
+ RE_RC_INIT(isec, *shi);
if(shi->mat->mode & MA_SHADOW_TRA) isec.mode= RE_RAY_SHADOW_TRA;
else isec.mode= RE_RAY_SHADOW;
+ isec.hint = 0;
if(lar->mode & (LA_LAYER|LA_LAYER_SHADOW))
isec.lay= lar->lay;
/* only when not mir tracing, first hit optimm */
if(shi->depth==0) {
- isec.face_last= (RayFace*)lar->vlr_last[shi->thread];
- isec.ob_last= RAY_OBJECT_SET(&R, lar->obi_last[shi->thread]);
+ isec.last_hit = lar->last_hit[shi->thread];
}
else {
- isec.face_last= NULL;
- isec.ob_last= 0;
+ isec.last_hit = NULL;
}
if(lar->type==LA_SUN || lar->type==LA_HEMI) {
- maxsize= RE_ray_tree_max_size(R.raytree);
- lampco[0]= shi->co[0] - maxsize*lar->vec[0];
- lampco[1]= shi->co[1] - maxsize*lar->vec[1];
- lampco[2]= shi->co[2] - maxsize*lar->vec[2];
+ /* jitter and QMC sampling add a displace vector to the lamp position
+ * that's incorrect because a SUN lamp does not has an exact position
+ * and the displace should be done at the ray vector instead of the
+ * lamp position.
+ * This is easily verified by noticing that shadows of SUN lights change
+ * with the scene BB.
+ *
+ * This was detected during SoC 2009 - Raytrace Optimization, but to keep
+ * consistency with older render code it wasn't removed.
+ *
+ * If the render code goes through some recode/serious bug-fix then this
+ * is something to consider!
+ */
+ lampco[0]= shi->co[0] - R.maxdist*lar->vec[0];
+ lampco[1]= shi->co[1] - R.maxdist*lar->vec[1];
+ lampco[2]= shi->co[2] - R.maxdist*lar->vec[2];
}
else {
VECCOPY(lampco, lar->co);
} else {
if(lar->ray_totsamp<2) {
- isec.faceorig= (RayFace*)shi->vlr;
- isec.oborig= RAY_OBJECT_SET(&R, shi->obi);
+ isec.orig.ob = shi->obi;
+ isec.orig.face = shi->vlr;
+
shadfac[3]= 1.0f; // 1.0=full light
/* set up isec vec */
VECCOPY(isec.start, shi->co);
- VECCOPY(isec.end, lampco);
+ VECSUB(isec.vec, lampco, isec.start);
+ isec.labda = 1.0f;
if(isec.mode==RE_RAY_SHADOW_TRA) {
/* isec.col is like shadfac, so defines amount of light (0.0 is full shadow) */
ray_trace_shadow_tra(&isec, shi, DEPTH_SHADOW_TRA, 0);
QUATCOPY(shadfac, isec.col);
}
- else if(RE_ray_tree_intersect(R.raytree, &isec)) shadfac[3]= 0.0f;
+ else if(RE_rayobject_raycast(R.raytree, &isec))
+ shadfac[3]= 0.0f;
}
else {
ray_shadow_jitter(shi, lar, lampco, shadfac, &isec);
/* for first hit optim, set last interesected shadow face */
if(shi->depth==0) {
- lar->vlr_last[shi->thread]= (VlakRen*)isec.face_last;
- lar->obi_last[shi->thread]= RAY_OBJECT_GET(&R, isec.ob_last);
+ lar->last_hit[shi->thread] = isec.last_hit;
}
}
static void ray_translucent(ShadeInput *shi, LampRen *lar, float *distfac, float *co)
{
Isect isec;
- float lampco[3], maxsize;
+ float lampco[3];
+
+ assert(0);
/* setup isec */
+ RE_RC_INIT(isec, *shi);
isec.mode= RE_RAY_SHADOW_TRA;
+ isec.hint = 0;
if(lar->mode & LA_LAYER) isec.lay= lar->lay; else isec.lay= -1;
if(lar->type==LA_SUN || lar->type==LA_HEMI) {
- maxsize= RE_ray_tree_max_size(R.raytree);
- lampco[0]= shi->co[0] - maxsize*lar->vec[0];
- lampco[1]= shi->co[1] - maxsize*lar->vec[1];
- lampco[2]= shi->co[2] - maxsize*lar->vec[2];
+ lampco[0]= shi->co[0] - RE_RAYTRACE_MAXDIST*lar->vec[0];
+ lampco[1]= shi->co[1] - RE_RAYTRACE_MAXDIST*lar->vec[1];
+ lampco[2]= shi->co[2] - RE_RAYTRACE_MAXDIST*lar->vec[2];
}
else {
VECCOPY(lampco, lar->co);
}
- isec.faceorig= (RayFace*)shi->vlr;
- isec.oborig= RAY_OBJECT_SET(&R, shi->obi);
+ isec.orig.ob = shi->obi;
+ isec.orig.face = shi->vlr;
/* set up isec vec */
VECCOPY(isec.start, shi->co);
VECCOPY(isec.end, lampco);
- if(RE_ray_tree_intersect(R.raytree, &isec)) {
+ if(RE_rayobject_raycast(R.raytree, &isec)) {
/* we got a face */
/* render co */
#include <math.h>
#include <float.h>
#include <string.h>
+#include <assert.h>
/* External modules: */
#include "MEM_guardedalloc.h"
}
}
break;
+
+ case SCE_PASS_RAYHITS:
+ /* */
+ col= &shr->rayhits;
+ pixsize= 4;
+ break;
}
if(col) {
fp= rpass->rect + pixsize*offset;
fp= rpass->rect + offset;
*fp= shr->mist;
break;
+ case SCE_PASS_RAYHITS:
+ col= shr->rayhits;
+ pixsize= 4;
+ break;
}
if(col) {
fp= rpass->rect + pixsize*offset;
}
}
+#if 0
static int bake_check_intersect(Isect *is, int ob, RayFace *face)
{
BakeShade *bs = (BakeShade*)is->userdata;
return (R.objectinstance[ob].obr->ob != bs->actob);
}
+#endif
-static int bake_intersect_tree(RayTree* raytree, Isect* isect, float *start, float *dir, float sign, float *hitco, float *dist)
+static int bake_intersect_tree(RayObject* raytree, Isect* isect, float *start, float *dir, float sign, float *hitco, float *dist)
{
+ //TODO
+ assert( 0 );
+#if 0
float maxdist;
int hit;
if(R.r.bake_maxdist > 0.0f)
maxdist= R.r.bake_maxdist;
else
- maxdist= RE_ray_tree_max_size(R.raytree) + R.r.bake_biasdist;
+ maxdist= FLT_MAX + R.r.bake_biasdist;
+ //TODO normalized direction?
VECADDFAC(isect->start, start, dir, -R.r.bake_biasdist);
+ isect->dir[0] = dir[0]*sign;
+ isect->dir[1] = dir[1]*sign;
+ isect->dir[2] = dir[2]*sign;
+ isect->labda = maxdist;
- isect->end[0] = isect->start[0] + dir[0]*maxdist*sign;
- isect->end[1] = isect->start[1] + dir[1]*maxdist*sign;
- isect->end[2] = isect->start[2] + dir[2]*maxdist*sign;
-
- hit = RE_ray_tree_intersect_check(R.raytree, isect, bake_check_intersect);
+ hit = RE_rayobject_raycast(raytree, isect);
+ //TODO bake_check_intersect
if(hit) {
hitco[0] = isect->start[0] + isect->labda*isect->vec[0];
hitco[1] = isect->start[1] + isect->labda*isect->vec[1];
}
return hit;
+#endif
+ return 0;
}
static void bake_set_vlr_dxyco(BakeShade *bs, float *uv1, float *uv2, float *uv3)
for(sign=-1; sign<=1; sign+=2) {
memset(&isec, 0, sizeof(isec));
isec.mode= RE_RAY_MIRROR;
- isec.faceorig= (RayFace*)vlr;
- isec.oborig= RAY_OBJECT_SET(&R, obi);
+
+ isec.orig.ob = obi;
+ isec.orig.face = vlr;
isec.userdata= bs;
if(bake_intersect_tree(R.raytree, &isec, shi->co, shi->vn, sign, co, &dist)) {
/* if hit, we shade from the new point, otherwise from point one starting face */
if(hit) {
- vlr= (VlakRen*)minisec.face;
- obi= RAY_OBJECT_GET(&R, minisec.ob);
+ obi= (ObjectInstanceRen*)minisec.hit.ob;
+ vlr= (VlakRen*)minisec.hit.face;
quad= (minisec.isect == 2);
VECCOPY(shi->co, minco);
#include "BKE_DerivedMesh.h"
#include "RE_render_ext.h" /* externtex */
+#include "RE_raytrace.h"
#include "renderpipeline.h"
#include "render_types.h"
MEM_freeN(obr->mtface);
if(obr->mcol)
MEM_freeN(obr->mcol);
+
+ if(obr->rayfaces)
+ {
+ MEM_freeN(obr->rayfaces);
+ obr->rayfaces = NULL;
+ }
+ if(obr->raytree)
+ {
+ RE_rayobject_free(obr->raytree);
+ obr->raytree = NULL;
+ }
}
if(re->objectinstance) {
for(obi=re->instancetable.first; obi; obi=obi->next)
+ {
if(obi->vectors)
MEM_freeN(obi->vectors);
+ if(obi->raytree)
+ RE_rayobject_free(obi->raytree);
+ }
+
MEM_freeN(re->objectinstance);
re->objectinstance= NULL;
re->totinstance= 0;
float alpha;
/* ------ main shading loop -------- */
+ memset(&shi->raycounter, 0, sizeof(shi->raycounter));
if(shi->mat->nodetree && shi->mat->use_nodes) {
ntreeShaderExecTree(shi->mat->nodetree, shi, shr);
/* add z */
shr->z= -shi->co[2];
+
+ /* RAYHITS */
+ if(1 || shi->passflag & SCE_PASS_RAYHITS)
+ {
+ shr->rayhits[0] = (float)shi->raycounter.faces.test;
+ shr->rayhits[1] = (float)shi->raycounter.bb.hit;
+ shr->rayhits[2] = 0.0;
+ shr->rayhits[3] = 1.0;
+ RE_RC_MERGE(&re_rc_counter[shi->thread], &shi->raycounter);
+ }
}
/* **************************************************************************** */
fastshade_free_render(); /* shaded view */
ED_preview_free_dbase(); /* frees a Main dbase, before free_blender! */
- wm_free_reports(C); /* before free_blender! - since the ListBases get freed there */
+
+ if(C && CTX_wm_manager(C))
+ wm_free_reports(C); /* before free_blender! - since the ListBases get freed there */
+
free_blender(); /* blender.c, does entire library and spacetypes */
// free_matcopybuf();
free_anim_copybuf();
projects / blender-staging.git / commitdiff