diff options
Diffstat (limited to 'source/blender/render')
29 files changed, 4887 insertions, 894 deletions
diff --git a/source/blender/render/SConscript b/source/blender/render/SConscript index 9b2480cc437..88942ced027 100644 --- a/source/blender/render/SConscript +++ b/source/blender/render/SConscript @@ -1,8 +1,10 @@ #!/usr/bin/python Import ('env') -cflags='' +cflags = ['-O2','-msse2','-mfpmath=sse'] +cxxflags = ['-O2','-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' @@ -18,7 +20,7 @@ if env['WITH_BF_OPENEXR']: defs.append('WITH_OPENEXR') if env['OURPLATFORM']=='linux2': - cflags='-pthread' + cflags += ['-pthread'] if env['OURPLATFORM'] == 'linux2': @@ -29,3 +31,4 @@ if env['OURPLATFORM'] in ('win32-vc', 'win32-mingw', 'linuxcross', 'win64-vc'): incs += ' ' + env['BF_PTHREADS_INC'] 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 ) diff --git a/source/blender/render/extern/include/RE_raytrace.h b/source/blender/render/extern/include/RE_raytrace.h index 8f429f7dd90..6a171a98f12 100644 --- a/source/blender/render/extern/include/RE_raytrace.h +++ b/source/blender/render/extern/include/RE_raytrace.h @@ -22,7 +22,7 @@ * * 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. @@ -31,84 +31,182 @@ #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; +#define RE_RAYCOUNTER /* enable counters per ray, usefull for measuring raytrace structures performance */ -/* 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))) +#ifdef RE_RAYCOUNTER -#define RAY_OBJECT_GET(re, i) \ - ((re)->objectinstance + ((i >= RE_RAY_TRANSFORM_OFFS)? i-RE_RAY_TRANSFORM_OFFS: i)) +typedef struct RayCounter RayCounter; +struct RayCounter +{ + struct + { + unsigned long long test, hit; + + } faces, bb, simd_bb, raycast, raytrace_hint, rayshadow_last_hit; +}; +#endif -/* struct for intersection data */ -typedef struct Isect { - float start[3]; /* start+vec = end, in ray_tree_intersect */ - float vec[3]; - float end[3]; +/* 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; +struct VlakRen; +struct ObjectInstanceRen; + +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); + +/* Extend min/max coords so that the rayobject is inside them */ +void RE_rayobject_merge_bb(RayObject *ob, float *min, float *max); + +/* 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); - float labda, u, v; /* distance to hitpoint, uv weights */ +/* 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 *); */ - 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 constructors */ +RayObject* RE_rayobject_octree_create(int ocres, int size); +RayObject* RE_rayobject_instance_create(RayObject *target, float transform[][4], void *ob, void *target_ob); + +RayObject* RE_rayobject_blibvh_create(int size); /* BLI_kdopbvh.c */ +RayObject* RE_rayobject_vbvh_create(int size); /* raytrace/rayobject_vbvh.c */ +RayObject* RE_rayobject_svbvh_create(int size); /* raytrace/rayobject_svbvh.c */ +RayObject* RE_rayobject_qbvh_create(int size); /* raytrace/rayobject_qbvh.c */ + + +/* + * This ray object represents a triangle or a quad face. + * All data needed to realize intersection is "localy" available. + */ +typedef struct RayFace +{ + float v1[4], v2[4], v3[4], v4[3]; + int quad; + void *ob; + void *face; + +} RayFace; + +#define RE_rayface_isQuad(a) ((a)->quad) + +RayObject* RE_rayface_from_vlak(RayFace *face, struct ObjectInstanceRen *obi, struct VlakRen *vlr); +RayObject* RE_rayface_from_coords(RayFace *rayface, void *ob, void *face, float *co1, float *co2, float *co3, float *co4); + + +/* + * This ray object represents faces directly from a given VlakRen structure. + * Thus allowing to save memory, but making code triangle intersection dependant on render structures + */ +typedef struct VlakPrimitive +{ + struct ObjectInstanceRen *ob; + struct VlakRen *face; +} VlakPrimitive; +RayObject* RE_vlakprimitive_from_vlak(VlakPrimitive *face, struct ObjectInstanceRen *obi, struct VlakRen *vlr); + + + +/* + * Raytrace hints + */ +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) +#define RE_SKIP_VLR_RENDER_CHECK (1 << 2) +#define RE_SKIP_VLR_NON_SOLID_MATERIAL (1 << 3) +/* TODO use: FLT_MAX? */ +#define RE_RAYTRACE_MAXDIST 1e33 + +#ifdef __cplusplus +} +#endif + + +#endif /*__RE_RAYTRACE_H__*/ diff --git a/source/blender/render/extern/include/RE_shader_ext.h b/source/blender/render/extern/include/RE_shader_ext.h index 134be189e8f..b36163f57c0 100644 --- a/source/blender/render/extern/include/RE_shader_ext.h +++ b/source/blender/render/extern/include/RE_shader_ext.h @@ -30,6 +30,7 @@ #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 */ /* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ */ @@ -56,6 +57,7 @@ typedef struct ShadeResult float refr[3]; float nor[3]; float winspeed[4]; + float rayhits[4]; } ShadeResult; /* only here for quick copy */ @@ -177,6 +179,10 @@ typedef struct ShadeInput struct Group *light_override; struct Material *mat_override; +#ifdef RE_RAYCOUNTER + RayCounter raycounter; +#endif + } ShadeInput; diff --git a/source/blender/render/intern/include/raycounter.h b/source/blender/render/intern/include/raycounter.h new file mode 100644 index 00000000000..dea6d63d001 --- /dev/null +++ b/source/blender/render/intern/include/raycounter.h @@ -0,0 +1,55 @@ +/** + * $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_RAYCOUNTER_H +#define RE_RAYCOUNTER_H + +#include "RE_raytrace.h" + + +#ifdef RE_RAYCOUNTER + +/* #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 + + +#endif diff --git a/source/blender/render/intern/include/rayobject.h b/source/blender/render/intern/include/rayobject.h new file mode 100644 index 00000000000..9e35c0feac5 --- /dev/null +++ b/source/blender/render/intern/include/rayobject.h @@ -0,0 +1,208 @@ +/** + * $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 0x03) to define the + type of RayObject. + + This leads to 4 possible types of RayObject: + + addr&3 - type of object + 0 Self (reserved for each structure) + 1 RayFace (tri/quad primitive) + 2 RayObject (generic with API callbacks) + 3 VlakPrimitive + (vlak primitive - to be used when we have a vlak describing the data + eg.: on render code) + + 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 + */ + +/* used to align a given ray object */ +#define RE_rayobject_align(o) ((RayObject*)(((intptr_t)o)&(~3))) + +/* used to unalign a given ray object */ +#define RE_rayobject_unalignRayFace(o) ((RayObject*)(((intptr_t)o)|1)) +#define RE_rayobject_unalignRayAPI(o) ((RayObject*)(((intptr_t)o)|2)) +#define RE_rayobject_unalignVlakPrimitive(o) ((RayObject*)(((intptr_t)o)|3)) + +/* used to test the type of ray object */ +#define RE_rayobject_isAligned(o) ((((intptr_t)o)&3) == 0) +#define RE_rayobject_isRayFace(o) ((((intptr_t)o)&3) == 1) +#define RE_rayobject_isRayAPI(o) ((((intptr_t)o)&3) == 2) +#define RE_rayobject_isVlakPrimitive(o) ((((intptr_t)o)&3) == 3) + + + +/* + * This class is intended as a place holder for control, configuration of the rayobject like: + * - stop building (TODO maybe when porting build to threads this could be implemented with some thread_cancel function) + * - max number of threads and threads callback to use during build + * ... + */ +typedef int (*RE_rayobjectcontrol_test_break_callback)(void *data); +typedef struct RayObjectControl RayObjectControl; +struct RayObjectControl +{ + void *data; + RE_rayobjectcontrol_test_break_callback test_break; +}; + +/* + * This rayobject represents a generic object. With it's own callbacks for raytrace operations. + * It's suitable to implement things like LOD. + */ +struct RayObject +{ + struct RayObjectAPI *api; + + struct RayObjectControl control; +}; + + + + +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; + + +/* + * 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); + + +/* + * Returns true if for some reason a heavy processing function should stop + * (eg.: user asked to stop during a tree a build) + */ +int RE_rayobjectcontrol_test_break(RayObjectControl *c); + + +#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 diff --git a/source/blender/render/intern/include/render_types.h b/source/blender/render/intern/include/render_types.h index 96306be31c8..8f16d636e79 100644 --- a/source/blender/render/intern/include/render_types.h +++ b/source/blender/render/intern/include/render_types.h @@ -53,6 +53,8 @@ struct VlakTableNode; struct GHash; struct RenderBuckets; struct ObjectInstanceRen; +struct RayObject; +struct RayFace; #define TABLEINITSIZE 1024 #define LAMPINITSIZE 256 @@ -172,7 +174,10 @@ struct Render ListBase parts; /* octree tables and variables for raytrace */ - void *raytree; + struct RayObject *raytree; + struct RayFace *rayfaces; + struct VlakPrimitive *rayprimitives; + float maxdist; /* needed for keeping an incorrect behaviour of SUN and HEMI lights (avoid breaking old scenes) */ /* occlusion tree */ void *occlusiontree; @@ -285,6 +290,13 @@ typedef struct ObjectRen { 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 VlakPrimitive *rayprimitives; + struct ObjectInstanceRen *rayobi; + } ObjectRen; typedef struct ObjectInstanceRen { @@ -304,6 +316,11 @@ typedef struct ObjectInstanceRen { float *vectors; int totvector; + + /* used on makeraytree */ + struct RayObject *raytree; + int transform_primitives; + } ObjectInstanceRen; /* ------------------------------------------------------------------------- */ @@ -429,7 +446,7 @@ typedef struct MatInside { typedef struct VolPrecachePart { struct VolPrecachePart *next, *prev; - struct RayTree *tree; + struct RayObject *tree; struct ShadeInput *shi; struct ObjectInstanceRen *obi; int num; @@ -540,8 +557,7 @@ typedef struct LampRen { 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]; diff --git a/source/blender/render/intern/include/rendercore.h b/source/blender/render/intern/include/rendercore.h index 4b28529a147..250fbc000cb 100644 --- a/source/blender/render/intern/include/rendercore.h +++ b/source/blender/render/intern/include/rendercore.h @@ -95,6 +95,7 @@ int get_sample_layers(struct RenderPart *pa, struct RenderLayer *rl, struct Rend extern void freeraytree(Render *re); extern void makeraytree(Render *re); +RayObject* makeraytree_object(Render *re, ObjectInstanceRen *obi); extern void ray_shadow(ShadeInput *, LampRen *, float *); extern void ray_trace(ShadeInput *, ShadeResult *); diff --git a/source/blender/render/intern/raytrace/bvh.h b/source/blender/render/intern/raytrace/bvh.h new file mode 100644 index 00000000000..0e74bbc923b --- /dev/null +++ b/source/blender/render/intern/raytrace/bvh.h @@ -0,0 +1,400 @@ +/** + * $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 "rayobject.h" +#include "raycounter.h" +#include "MEM_guardedalloc.h" +#include "rayobject_rtbuild.h" +#include "rayobject_hint.h" + +#include <assert.h> + +#ifdef __SSE__ +#include <xmmintrin.h> +#endif + +#ifndef RE_RAYTRACE_BVH_H +#define RE_RAYTRACE_BVH_H + +#ifdef __SSE__ +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)); +} +#endif + + +/* 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 !RE_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; +} + + +#ifdef __SSE__ +/* + * 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->simd_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->simd_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; +} +#endif + +/* + * 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; +} +*/ + +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> +static RayObjectAPI* bvh_get_api(int maxstacksize); + + +template<class Tree, int DFS_STACK_SIZE> +static inline RayObject *bvh_create_tree(int size) +{ + Tree *obj= (Tree*)MEM_callocN(sizeof(Tree), "BVHTree" ); + assert( RE_rayobject_isAligned(obj) ); /* RayObject API assumes real data to be 4-byte aligned */ + + obj->rayobj.api = bvh_get_api<Tree>(DFS_STACK_SIZE); + obj->root = NULL; + + obj->node_arena = NULL; + obj->builder = rtbuild_create( size ); + + return RE_rayobject_unalignRayAPI((RayObject*) obj); +} + +#endif diff --git a/source/blender/render/intern/raytrace/rayobject.cpp b/source/blender/render/intern/raytrace/rayobject.cpp new file mode 100644 index 00000000000..95387cf1ee4 --- /dev/null +++ b/source/blender/render/intern/raytrace/rayobject.cpp @@ -0,0 +1,537 @@ +/** + * $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 "BKE_utildefines.h" +#include "BLI_arithb.h" +#include "DNA_material_types.h" + +#include "RE_raytrace.h" +#include "render_types.h" +#include "rayobject.h" +#include "raycounter.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] + */ +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; +} + +static inline int vlr_check_intersect(Isect *is, ObjectInstanceRen *obi, VlakRen *vlr) +{ + /* for baking selected to active non-traceable materials might still + * be in the raytree */ + if(!(vlr->mat->mode & MA_TRACEBLE)) + return 0; + + /* I know... cpu cycle waste, might do smarter once */ + if(is->mode==RE_RAY_MIRROR) + return !(vlr->mat->mode & MA_ONLYCAST); + else + return (is->lay & obi->lay); +} + +static inline int vlr_check_intersect_solid(Isect *is, ObjectInstanceRen* obi, VlakRen *vlr) +{ + /* solid material types only */ + if (vlr->mat->material_type == MA_TYPE_SURFACE) + return 1; + else + return 0; +} + +static inline int rayface_check_cullface(RayFace *face, Isect *is) +{ + float nor[3]; + + /* don't intersect if the ray faces along the face normal */ + if(face->quad) CalcNormFloat4(face->v1, face->v2, face->v3, face->v4, nor); + else CalcNormFloat(face->v1, face->v2, face->v3, nor); + + return (INPR(nor, is->vec) < 0); +} + +/* ray - triangle or quad intersection */ +/* this function shall only modify Isect if it detects an hit */ +static int intersect_rayface(RayObject *hit_obj, 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; + + + if(is->skip & RE_SKIP_VLR_RENDER_CHECK) + { + if(vlr_check_intersect(is, (ObjectInstanceRen*)face->ob, (VlakRen*)face->face ) == 0) + return 0; + } + if(is->skip & RE_SKIP_VLR_NON_SOLID_MATERIAL) + { + if(vlr_check_intersect_solid(is, (ObjectInstanceRen*)face->ob, (VlakRen*)face->face) == 0) + return 0; + } + if(is->skip & RE_SKIP_CULLFACE) + { + if(rayface_check_cullface(face, is) == 0) + return 0; + } + + RE_RC_COUNT(is->raycounter->faces.test); + + //Load coords + 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); + } + + 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 = (VlakRen*)is->orig.face; + VlakRen * b = (VlakRen*)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; + } + } + } + + 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 = hit_obj; +#endif + return 1; + } + + return 0; +} + +RayObject* RE_rayface_from_vlak(RayFace *rayface, ObjectInstanceRen *obi, VlakRen *vlr) +{ + return RE_rayface_from_coords(rayface, obi, vlr, vlr->v1->co, vlr->v2->co, vlr->v3->co, vlr->v4 ? vlr->v4->co : 0 ); +} + +RayObject* RE_rayface_from_coords(RayFace *rayface, void *ob, void *face, float *v1, float *v2, float *v3, float *v4) +{ + rayface->ob = ob; + rayface->face = face; + + VECCOPY(rayface->v1, v1); + VECCOPY(rayface->v2, v2); + VECCOPY(rayface->v3, v3); + if(v4) + { + VECCOPY(rayface->v4, v4); + rayface->quad = 1; + } + else + { + rayface->quad = 0; + } + + return RE_rayobject_unalignRayFace(rayface); +} + +RayObject* RE_vlakprimitive_from_vlak(VlakPrimitive *face, struct ObjectInstanceRen *obi, struct VlakRen *vlr) +{ + face->ob = obi; + face->face = vlr; + return RE_rayobject_unalignVlakPrimitive(face); +} + + +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)) + { + RE_RC_COUNT(isec->raycounter->raycast.hit); + +#ifdef RT_USE_HINT + isec->hint = isec->hit_hint; +#endif + return 1; + } + return 0; +} + +int RE_rayobject_intersect(RayObject *r, Isect *i) +{ + if(RE_rayobject_isRayFace(r)) + { + return intersect_rayface(r, (RayFace*) RE_rayobject_align(r), i); + } + else if(RE_rayobject_isVlakPrimitive(r)) + { + //TODO optimize (useless copy to RayFace to avoid duplicate code) + VlakPrimitive *face = (VlakPrimitive*) RE_rayobject_align(r); + RayFace nface; + RE_rayface_from_vlak(&nface, face->ob, face->face); + + if(face->ob->transform_primitives) + { + Mat4MulVecfl(face->ob->mat, nface.v1); + Mat4MulVecfl(face->ob->mat, nface.v2); + Mat4MulVecfl(face->ob->mat, nface.v3); + if(RE_rayface_isQuad(&nface)) + Mat4MulVecfl(face->ob->mat, nface.v4); + } + + return intersect_rayface(r, &nface, i); + } + else if(RE_rayobject_isRayAPI(r)) + { + r = RE_rayobject_align( r ); + return r->api->raycast( r, i ); + } + else assert(0); +} + +void RE_rayobject_add(RayObject *r, RayObject *o) +{ + r = RE_rayobject_align( r ); + return r->api->add( r, o ); +} + +void RE_rayobject_done(RayObject *r) +{ + r = RE_rayobject_align( r ); + r->api->done( r ); +} + +void RE_rayobject_free(RayObject *r) +{ + r = RE_rayobject_align( r ); + r->api->free( r ); +} + +void RE_rayobject_merge_bb(RayObject *r, float *min, float *max) +{ + if(RE_rayobject_isRayFace(r)) + { + RayFace *face = (RayFace*) RE_rayobject_align(r); + + 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 ); + } + else if(RE_rayobject_isVlakPrimitive(r)) + { + VlakPrimitive *face = (VlakPrimitive*) RE_rayobject_align(r); + VlakRen *vlr = face->face; + + DO_MINMAX( vlr->v1->co, min, max ); + DO_MINMAX( vlr->v2->co, min, max ); + DO_MINMAX( vlr->v3->co, min, max ); + if(vlr->v4) DO_MINMAX( vlr->v4->co, min, max ); + } + else if(RE_rayobject_isRayAPI(r)) + { + r = RE_rayobject_align( r ); + r->api->bb( r, min, max ); + } + else assert(0); +} + +float RE_rayobject_cost(RayObject *r) +{ + if(RE_rayobject_isRayFace(r) || RE_rayobject_isVlakPrimitive(r)) + { + return 1.0; + } + else if(RE_rayobject_isRayAPI(r)) + { + r = RE_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(RE_rayobject_isRayFace(r) || RE_rayobject_isVlakPrimitive(r)) + { + return; + } + else if(RE_rayobject_isRayAPI(r)) + { + r = RE_rayobject_align( r ); + return r->api->hint_bb( r, hint, min, max ); + } + else assert(0); +} + +int RE_rayobjectcontrol_test_break(RayObjectControl *control) +{ + if(control->test_break) + return control->test_break( control->data ); + + return 0; +} diff --git a/source/blender/render/intern/raytrace/rayobject_hint.h b/source/blender/render/intern/raytrace/rayobject_hint.h new file mode 100644 index 00000000000..d85465aec66 --- /dev/null +++ b/source/blender/render/intern/raytrace/rayobject_hint.h @@ -0,0 +1,70 @@ +/** + * $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_RAYOBJECT_HINT_H +#define RE_RAYTRACE_RAYOBJECT_HINT_H + +#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; +} +*/ + +#endif diff --git a/source/blender/render/intern/raytrace/rayobject_qbvh.cpp b/source/blender/render/intern/raytrace/rayobject_qbvh.cpp new file mode 100644 index 00000000000..8d35848c9ec --- /dev/null +++ b/source/blender/render/intern/raytrace/rayobject_qbvh.cpp @@ -0,0 +1,149 @@ +/** + * $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 "vbvh.h" +#include "svbvh.h" +#include "reorganize.h" + +#ifdef __SSE__ + +#define DFS_STACK_SIZE 256 + +struct QBVHTree +{ + RayObject rayobj; + + SVBVHNode *root; + MemArena *node_arena; + + float cost; + RTBuilder *builder; +}; + + +template<> +void bvh_done<QBVHTree>(QBVHTree *obj) +{ + rtbuild_done(obj->builder, &obj->rayobj.control); + + //TODO find a away to exactly calculate the needed memory + MemArena *arena1 = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE); + BLI_memarena_use_malloc(arena1); + + MemArena *arena2 = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE); + BLI_memarena_use_malloc(arena2); + BLI_memarena_use_align(arena2, 16); + + //Build and optimize the tree + //TODO do this in 1 pass (half memory usage during building) + VBVHNode *root = BuildBinaryVBVH<VBVHNode>(arena1, &obj->rayobj.control).transform(obj->builder); + + if(RE_rayobjectcontrol_test_break(&obj->rayobj.control)) + { + BLI_memarena_free(arena1); + BLI_memarena_free(arena2); + return; + } + + pushup_simd<VBVHNode,4>(root); + obj->root = Reorganize_SVBVH<VBVHNode>(arena2).transform(root); + + //Cleanup + BLI_memarena_free(arena1); + + rtbuild_free( obj->builder ); + obj->builder = NULL; + + obj->node_arena = arena2; + obj->cost = 1.0; +} + + +template<int StackSize> +int intersect(QBVHTree *obj, Isect* isec) +{ + //TODO renable hint support + if(RE_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 Tree> +void bvh_hint_bb(Tree *tree, LCTSHint *hint, float *min, float *max) +{ + //TODO renable hint support + { + hint->size = 0; + hint->stack[hint->size++] = (RayObject*)tree->root; + } +} +/* 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> +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_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> +RayObjectAPI* bvh_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_qbvh_create(int size) +{ + return bvh_create_tree<QBVHTree,DFS_STACK_SIZE>(size); +} + + +#else + +RayObject *RE_rayobject_qbvh_create(int size) +{ + puts("WARNING: SSE disabled at compile time\n"); + return NULL; +} + +#endif
\ No newline at end of file diff --git a/source/blender/render/intern/raytrace/rayobject_rtbuild.cpp b/source/blender/render/intern/raytrace/rayobject_rtbuild.cpp new file mode 100644 index 00000000000..9523e725893 --- /dev/null +++ b/source/blender/render/intern/raytrace/rayobject_rtbuild.cpp @@ -0,0 +1,496 @@ +/** + * $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 <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, RayObjectControl* ctrl) +{ + for(int i=0; i<3; i++) + if(b->sorted_begin[i]) + { + if(RE_rayobjectcontrol_test_break(ctrl)) break; + 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; +} diff --git a/source/blender/render/intern/raytrace/rayobject_rtbuild.h b/source/blender/render/intern/raytrace/rayobject_rtbuild.h new file mode 100644 index 00000000000..71665681586 --- /dev/null +++ b/source/blender/render/intern/raytrace/rayobject_rtbuild.h @@ -0,0 +1,121 @@ +/** + * $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, RayObjectControl *c); +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 diff --git a/source/blender/render/intern/raytrace/rayobject_svbvh.cpp b/source/blender/render/intern/raytrace/rayobject_svbvh.cpp new file mode 100644 index 00000000000..a877b91e2ff --- /dev/null +++ b/source/blender/render/intern/raytrace/rayobject_svbvh.cpp @@ -0,0 +1,181 @@ +/** + * $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 "vbvh.h" +#include "svbvh.h" +#include "reorganize.h" + +#ifdef __SSE__ + +#define DFS_STACK_SIZE 256 + +struct SVBVHTree +{ + RayObject rayobj; + + SVBVHNode *root; + MemArena *node_arena; + + float cost; + RTBuilder *builder; +}; + +/* + * Cost to test N childs + */ +struct PackCost +{ + float operator()(int n) + { + return (n / 4) + ((n % 4) > 2 ? 1 : n%4); + } +}; + + +template<> +void bvh_done<SVBVHTree>(SVBVHTree *obj) +{ + rtbuild_done(obj->builder, &obj->rayobj.control); + + //TODO find a away to exactly calculate the needed memory + MemArena *arena1 = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE); + BLI_memarena_use_malloc(arena1); + + MemArena *arena2 = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE); + BLI_memarena_use_malloc(arena2); + BLI_memarena_use_align(arena2, 16); + + //Build and optimize the tree + if(0) + { + VBVHNode *root = BuildBinaryVBVH<VBVHNode>(arena1,&obj->rayobj.control).transform(obj->builder); + if(RE_rayobjectcontrol_test_break(&obj->rayobj.control)) + { + BLI_memarena_free(arena1); + BLI_memarena_free(arena2); + return; + } + + reorganize(root); + remove_useless(root, &root); + bvh_refit(root); + + pushup(root); + pushdown(root); + pushup_simd<VBVHNode,4>(root); + + obj->root = Reorganize_SVBVH<VBVHNode>(arena2).transform(root); + } + else + { + //Finds the optimal packing of this tree using a given cost model + //TODO this uses quite a lot of memory, find ways to reduce memory usage during building + OVBVHNode *root = BuildBinaryVBVH<OVBVHNode>(arena1,&obj->rayobj.control).transform(obj->builder); + if(RE_rayobjectcontrol_test_break(&obj->rayobj.control)) + { + BLI_memarena_free(arena1); + BLI_memarena_free(arena2); + return; + } + + VBVH_optimalPackSIMD<OVBVHNode,PackCost>(PackCost()).transform(root); + obj->root = Reorganize_SVBVH<OVBVHNode>(arena2).transform(root); + } + + + //Free data + BLI_memarena_free(arena1); + + obj->node_arena = arena2; + obj->cost = 1.0; + + + rtbuild_free( obj->builder ); + obj->builder = NULL; +} + +template<int StackSize> +int intersect(SVBVHTree *obj, Isect* isec) +{ + //TODO renable hint support + if(RE_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 Tree> +void bvh_hint_bb(Tree *tree, LCTSHint *hint, float *min, float *max) +{ + //TODO renable hint support + { + hint->size = 0; + hint->stack[hint->size++] = (RayObject*)tree->root; + } +} +/* 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> +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_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> +RayObjectAPI* bvh_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_svbvh_create(int size) +{ + return bvh_create_tree<SVBVHTree,DFS_STACK_SIZE>(size); +} +#else + +RayObject *RE_rayobject_svbvh_create(int size) +{ + puts("WARNING: SSE disabled at compile time\n"); + return NULL; +} + +#endif diff --git a/source/blender/render/intern/raytrace/rayobject_vbvh.cpp b/source/blender/render/intern/raytrace/rayobject_vbvh.cpp new file mode 100644 index 00000000000..11f04c04141 --- /dev/null +++ b/source/blender/render/intern/raytrace/rayobject_vbvh.cpp @@ -0,0 +1,191 @@ +/** + * $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 ***** + */ +int tot_pushup = 0; +int tot_pushdown = 0; +int tot_hints = 0; + + +#include <assert.h> +#include "rayobject.h" +#include "rayobject_rtbuild.h" +#include "RE_raytrace.h" +#include "BLI_memarena.h" +#include "MEM_guardedalloc.h" +#include "BKE_utildefines.h" +#include "BLI_arithb.h" + +#include "reorganize.h" +#include "bvh.h" +#include "vbvh.h" +#include "svbvh.h" +#include <queue> +#include <algorithm> + +#define DFS_STACK_SIZE 256 + +struct VBVHTree +{ + RayObject rayobj; + VBVHNode *root; + MemArena *node_arena; + float cost; + RTBuilder *builder; +}; + +/* + * Cost to test N childs + */ +struct PackCost +{ + float operator()(int n) + { + return n; + } +}; + +template<> +void bvh_done<VBVHTree>(VBVHTree *obj) +{ + rtbuild_done(obj->builder, &obj->rayobj.control); + + //TODO find a away to exactly calculate the needed memory + MemArena *arena1 = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE); + BLI_memarena_use_malloc(arena1); + + //Build and optimize the tree + if(1) + { + VBVHNode *root = BuildBinaryVBVH<VBVHNode>(arena1,&obj->rayobj.control).transform(obj->builder); + if(RE_rayobjectcontrol_test_break(&obj->rayobj.control)) + { + BLI_memarena_free(arena1); + return; + } + + reorganize(root); + remove_useless(root, &root); + bvh_refit(root); + + pushup(root); + pushdown(root); + obj->root = root; + } + else + { +/* + TODO + MemArena *arena2 = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE); + BLI_memarena_use_malloc(arena2); + + //Finds the optimal packing of this tree using a given cost model + //TODO this uses quite a lot of memory, find ways to reduce memory usage during building + OVBVHNode *root = BuildBinaryVBVH<OVBVHNode>(arena2).transform(obj->builder); + VBVH_optimalPackSIMD<OVBVHNode,PackCost>(PackCost()).transform(root); + obj->root = Reorganize_VBVH<OVBVHNode>(arena1).transform(root); + + BLI_memarena_free(arena2); + */ + } + + //Cleanup + rtbuild_free( obj->builder ); + obj->builder = NULL; + + obj->node_arena = arena1; + obj->cost = 1.0; +} + +template<int StackSize> +int intersect(VBVHTree *obj, Isect* isec) +{ + //TODO renable hint support + if(RE_rayobject_isAligned(obj->root)) + return bvh_node_stack_raycast<VBVHNode,StackSize,false>( obj->root, isec); + else + return RE_rayobject_intersect( (RayObject*) obj->root, isec ); +} + +template<class Tree> +void bvh_hint_bb(Tree *tree, LCTSHint *hint, float *min, float *max) +{ + //TODO renable hint support + { + 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> +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_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> +RayObjectAPI* bvh_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) +{ + return bvh_create_tree<VBVHTree,DFS_STACK_SIZE>(size); +} diff --git a/source/blender/render/intern/raytrace/reorganize.h b/source/blender/render/intern/raytrace/reorganize.h new file mode 100644 index 00000000000..f0335b769d5 --- /dev/null +++ b/source/blender/render/intern/raytrace/reorganize.h @@ -0,0 +1,516 @@ +/** + * $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 <stdio.h> +#include <math.h> +#include <algorithm> +#include <vector> +#include <queue> + +extern int tot_pushup; +extern int tot_pushdown; + +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) && RE_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( RE_rayobject_isAligned(node->child) ) + { + for(Node **prev = &node->child; *prev; ) + { + assert( RE_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( RE_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(RE_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; RE_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; RE_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; RE_rayobject_isAligned(child) && child; ) + { + int cn = count_childs(child); + if(cn-1 <= (SSize - (n%SSize) ) % SSize && RE_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; RE_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 && RE_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; RE_rayobject_isAligned(i) && i; i = i->sibling) + if(child != i && bb_fits_inside(i->bb, i->bb+3, child->bb, child->bb+3) && RE_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; RE_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; +} + + +/* + * this finds the best way to packing a tree acording to a given test cost function + * with the purpose to reduce the expected cost (eg.: number of BB tests). + */ +#include <vector> +#include <cmath> +#define MAX_CUT_SIZE 16 +#define MAX_OPTIMIZE_CHILDS MAX_CUT_SIZE + +struct OVBVHNode +{ + float bb[6]; + + OVBVHNode *child; + OVBVHNode *sibling; + + /* + * Returns min cost to represent the subtree starting at the given node, + * allowing it to have a given cutsize + */ + float cut_cost[MAX_CUT_SIZE]; + float get_cost(int cutsize) + { + return cut_cost[cutsize-1]; + } + + /* + * This saves the cut size of this child, when parent is reaching + * its minimum cut with the given cut size + */ + int cut_size[MAX_CUT_SIZE]; + int get_cut_size(int parent_cut_size) + { + return cut_size[parent_cut_size-1]; + } + + /* + * Reorganize the node based on calculated cut costs + */ + int best_cutsize; + void set_cut(int cutsize, OVBVHNode ***cut) + { + if(cutsize == 1) + { + **cut = this; + *cut = &(**cut)->sibling; + } + else + { + if(cutsize > MAX_CUT_SIZE) + { + for(OVBVHNode *child = this->child; child && RE_rayobject_isAligned(child); child = child->sibling) + { + child->set_cut( 1, cut ); + cutsize--; + } + assert(cutsize == 0); + } + else + for(OVBVHNode *child = this->child; child && RE_rayobject_isAligned(child); child = child->sibling) + child->set_cut( child->get_cut_size( cutsize ), cut ); + } + } + + void optimize() + { + if(RE_rayobject_isAligned(this->child)) + { + //Calc new childs + { + OVBVHNode **cut = &(this->child); + set_cut( best_cutsize, &cut ); + *cut = NULL; + } + + //Optimize new childs + for(OVBVHNode *child = this->child; child && RE_rayobject_isAligned(child); child = child->sibling) + child->optimize(); + } + } +}; + +/* + * Calculates an optimal SIMD packing + * + */ +template<class Node, class TestCost> +struct VBVH_optimalPackSIMD +{ + TestCost testcost; + + VBVH_optimalPackSIMD(TestCost testcost) + { + this->testcost = testcost; + } + + /* + * calc best cut on a node + */ + struct calc_best + { + Node *child[MAX_OPTIMIZE_CHILDS]; + float child_hit_prob[MAX_OPTIMIZE_CHILDS]; + + calc_best(Node *node) + { + int nchilds = 0; + //Fetch childs and needed data + { + float parent_area = bb_area(node->bb, node->bb+3); + for(Node *child = node->child; child && RE_rayobject_isAligned(child); child = child->sibling) + { + this->child[nchilds] = child; + this->child_hit_prob[nchilds] = bb_area(child->bb, child->bb+3) / parent_area; + nchilds++; + } + + assert(nchilds >= 2 && nchilds <= MAX_OPTIMIZE_CHILDS); + } + + + //Build DP table to find minimum cost to represent this node with a given cutsize + int bt [MAX_OPTIMIZE_CHILDS+1][MAX_CUT_SIZE+1]; //backtrace table + float cost[MAX_OPTIMIZE_CHILDS+1][MAX_CUT_SIZE+1]; //cost table (can be reduced to float[2][MAX_CUT_COST]) + + for(int i=0; i<=nchilds; i++) + for(int j=0; j<=MAX_CUT_SIZE; j++) + cost[i][j] = INFINITY; + + cost[0][0] = 0; + + for(int i=1; i<=nchilds; i++) + for(int size=i-1; size/*+(nchilds-i)*/<=MAX_CUT_SIZE; size++) + for(int cut=1; cut+size/*+(nchilds-i)*/<=MAX_CUT_SIZE; cut++) + { + float new_cost = cost[i-1][size] + child_hit_prob[i-1]*child[i-1]->get_cost(cut); + if(new_cost < cost[i][size+cut]) + { + cost[i][size+cut] = new_cost; + bt[i][size+cut] = cut; + } + } + + //Save the ways to archieve the minimum cost with a given cutsize + for(int i = nchilds; i <= MAX_CUT_SIZE; i++) + { + node->cut_cost[i-1] = cost[nchilds][i]; + if(cost[nchilds][i] < INFINITY) + { + int current_size = i; + for(int j=nchilds; j>0; j--) + { + child[j-1]->cut_size[i-1] = bt[j][current_size]; + current_size -= bt[j][current_size]; + } + } + } + } + }; + + void calc_costs(Node *node) + { + + if( RE_rayobject_isAligned(node->child) ) + { + int nchilds = 0; + for(Node *child = node->child; child && RE_rayobject_isAligned(child); child = child->sibling) + { + calc_costs(child); + nchilds++; + } + + for(int i=0; i<MAX_CUT_SIZE; i++) + node->cut_cost[i] = INFINITY; + + //We are not allowed to look on nodes with with so many childs + if(nchilds > MAX_CUT_SIZE) + { + float cost = 0; + + float parent_area = bb_area(node->bb, node->bb+3); + for(Node *child = node->child; child && RE_rayobject_isAligned(child); child = child->sibling) + { + cost += ( bb_area(child->bb, child->bb+3) / parent_area ) * child->get_cost(1); + } + + cost += testcost(nchilds); + node->cut_cost[0] = cost; + node->best_cutsize = nchilds; + } + else + { + calc_best calc(node); + + //calc expected cost if we optimaly pack this node + for(int cutsize=nchilds; cutsize<=MAX_CUT_SIZE; cutsize++) + { + float m = node->get_cost(cutsize) + testcost(cutsize); + if(m < node->cut_cost[0]) + { + node->cut_cost[0] = m; + node->best_cutsize = cutsize; + } + } + } + assert(node->cut_cost[0] != INFINITY); + } + else + { + node->cut_cost[0] = 1.0f; + for(int i=1; i<MAX_CUT_SIZE; i++) + node->cut_cost[i] = INFINITY; + } + } + + Node *transform(Node *node) + { + if(RE_rayobject_isAligned(node->child)) + { + static int num = 0; + bool first = false; + if(num == 0) { num++; first = true; } + + calc_costs(node); + if(first) printf("expected cost = %f (%d)\n", node->cut_cost[0], node->best_cutsize ); + node->optimize(); + } + return node; + } +}; diff --git a/source/blender/render/intern/raytrace/svbvh.h b/source/blender/render/intern/raytrace/svbvh.h new file mode 100644 index 00000000000..3c733b6b402 --- /dev/null +++ b/source/blender/render/intern/raytrace/svbvh.h @@ -0,0 +1,249 @@ +/** + * $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 ***** + */ +#ifdef __SSE__ + +#ifndef RE_RAYTRACE_SVBVH_H +#define RE_RAYTRACE_SVBVH_H + +#include "bvh.h" +#include "BLI_memarena.h" +#include <stdio.h> +#include <algorithm> + +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) +{ + 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->simd_bb.test); + + if(res & 1) { stack[stack_pos++] = node->child[i+0]; RE_RC_COUNT(isec->raycounter->simd_bb.hit); } + if(res & 2) { stack[stack_pos++] = node->child[i+1]; RE_RC_COUNT(isec->raycounter->simd_bb.hit); } + if(res & 4) { stack[stack_pos++] = node->child[i+2]; RE_RC_COUNT(isec->raycounter->simd_bb.hit); } + if(res & 8) { stack[stack_pos++] = node->child[i+3]; RE_RC_COUNT(isec->raycounter->simd_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++; + } +} + +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(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); + } + } +} + + + +/* + * Builds a SVBVH tree form a VBVHTree + */ +template<class OldNode> +struct Reorganize_SVBVH +{ + MemArena *arena; + + float childs_per_node; + int nodes_with_childs[16]; + int useless_bb; + int nodes; + + Reorganize_SVBVH(MemArena *a) + { + arena = a; + 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(arena, sizeof(SVBVHNode)); + node->nchilds = nchilds; + node->child_bb = (float*)BLI_memarena_alloc(arena, sizeof(float)*6*nchilds); + node->child= (SVBVHNode**)BLI_memarena_alloc(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]; + } + + 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 ); + + prepare_for_simd(node); + + return node; + } +}; + +#endif + +#endif //__SSE__
\ No newline at end of file diff --git a/source/blender/render/intern/raytrace/vbvh.h b/source/blender/render/intern/raytrace/vbvh.h new file mode 100644 index 00000000000..1ff51786e52 --- /dev/null +++ b/source/blender/render/intern/raytrace/vbvh.h @@ -0,0 +1,237 @@ +/** + * $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 <algorithm> +#include "rayobject_rtbuild.h" +#include "BLI_memarena.h" + + +/* + * VBVHNode represents a BVHNode with support for a variable number of childrens + */ +struct VBVHNode +{ + float bb[6]; + + VBVHNode *child; + VBVHNode *sibling; +}; + + +/* + * 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; + } + } +} + + +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; +} + + +/* + * Builds a binary VBVH from a rtbuild + */ +template<class Node> +struct BuildBinaryVBVH +{ + MemArena *arena; + RayObjectControl *control; + + void test_break() + { + if(RE_rayobjectcontrol_test_break(control)) + throw "Stop"; + } + + BuildBinaryVBVH(MemArena *a, RayObjectControl *c) + { + arena = a; + control = c; + } + + Node *create_node() + { + Node *node = (Node*)BLI_memarena_alloc( arena, sizeof(Node) ); + assert( RE_rayobject_isAligned(node) ); + + node->sibling = NULL; + node->child = NULL; + + return node; + } + + int rtbuild_split(RTBuilder *builder) + { + return ::rtbuild_heuristic_object_split(builder, 2); + } + + Node *transform(RTBuilder *builder) + { + try + { + return _transform(builder); + + } catch(...) + { + } + return NULL; + } + + Node *_transform(RTBuilder *builder) + { + + int size = rtbuild_size(builder); + if(size == 1) + { + Node *node = create_node(); + INIT_MINMAX(node->bb, node->bb+3); + rtbuild_merge_bb(builder, node->bb, node->bb+3); + node->child = (Node*) rtbuild_get_primitive( builder, 0 ); + return node; + } + else + { + test_break(); + + Node *node = create_node(); + + 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); + assert(nc == 2); + for(int i=0; i<nc; i++) + { + RTBuilder tmp; + rtbuild_get_child(builder, i, &tmp); + + *child = _transform(&tmp); + child = &((*child)->sibling); + } + + *child = 0; + return node; + } + } +}; + +/* +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; + } +}; +*/
\ No newline at end of file diff --git a/source/blender/render/intern/source/pipeline.c b/source/blender/render/intern/source/pipeline.c index 077f826b1ef..74a56528d8d 100644 --- a/source/blender/render/intern/source/pipeline.c +++ b/source/blender/render/intern/source/pipeline.c @@ -358,6 +358,13 @@ static char *get_pass_name(int passtype, int channel) 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"; } @@ -409,6 +416,8 @@ static int passtype_from_name(char *str) if(strcmp(str, "Mist")==0) return SCE_PASS_MIST; + if(strcmp(str, "RAYHITS")==0) + return SCE_PASS_RAYHITS; return 0; } @@ -536,7 +545,7 @@ static RenderResult *new_render_result(Render *re, rcti *partrct, int crop, int 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; @@ -580,6 +589,8 @@ static RenderResult *new_render_result(Render *re, rcti *partrct, int crop, int 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 */ diff --git a/source/blender/render/intern/source/rayobject_blibvh.c b/source/blender/render/intern/source/rayobject_blibvh.c new file mode 100644 index 00000000000..3fd71862f54 --- /dev/null +++ b/source/blender/render/intern/source/rayobject_blibvh.c @@ -0,0 +1,169 @@ +/** + * $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 RE_rayobject_blibvh_intersect(RayObject *o, Isect *isec); +static void RE_rayobject_blibvh_add(RayObject *o, RayObject *ob); +static void RE_rayobject_blibvh_done(RayObject *o); +static void RE_rayobject_blibvh_free(RayObject *o); +static void RE_rayobject_blibvh_bb(RayObject *o, float *min, float *max); + +static float RE_rayobject_blibvh_cost(RayObject *o) +{ + //TODO calculate the expected cost to raycast on this structure + return 1.0; +} + +static void RE_rayobject_blibvh_hint_bb(RayObject *o, RayHint *hint, float *min, float *max) +{ + return; +} + +static RayObjectAPI bvh_api = +{ + RE_rayobject_blibvh_intersect, + RE_rayobject_blibvh_add, + RE_rayobject_blibvh_done, + RE_rayobject_blibvh_free, + RE_rayobject_blibvh_bb, + RE_rayobject_blibvh_cost, + RE_rayobject_blibvh_hint_bb +}; + +typedef struct BVHObject +{ + RayObject rayobj; + RayObject **leafs, **next_leaf; + BVHTree *bvh; + float bb[2][3]; + +} BVHObject; + + +RayObject *RE_rayobject_blibvh_create(int size) +{ + BVHObject *obj= (BVHObject*)MEM_callocN(sizeof(BVHObject), "BVHObject"); + assert( RE_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); + obj->next_leaf = obj->leafs = (RayObject**)MEM_callocN(size*sizeof(RayObject*), "BVHObject leafs"); + + INIT_MINMAX(obj->bb[0], obj->bb[1]); + return RE_rayobject_unalignRayAPI((RayObject*) obj); +} + +struct BVHCallbackUserData +{ + Isect *isec; + RayObject **leafs; +}; + +static void bvh_callback(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit) +{ + struct BVHCallbackUserData *data = (struct BVHCallbackUserData*)userdata; + Isect *isec = data->isec; + RayObject *face = data->leafs[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 RE_rayobject_blibvh_intersect(RayObject *o, Isect *isec) +{ + BVHObject *obj = (BVHObject*)o; + BVHTreeRayHit hit; + float dir[3]; + struct BVHCallbackUserData data; + data.isec = isec; + data.leafs = obj->leafs; + + 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, (void*)&data); +} + +static void RE_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, obj->next_leaf - obj->leafs, min_max, 2 ); + *(obj->next_leaf++) = ob; +} + +static void RE_rayobject_blibvh_done(RayObject *o) +{ + BVHObject *obj = (BVHObject*)o; + BLI_bvhtree_balance(obj->bvh); +} + +static void RE_rayobject_blibvh_free(RayObject *o) +{ + BVHObject *obj = (BVHObject*)o; + + if(obj->bvh) + BLI_bvhtree_free(obj->bvh); + + if(obj->leafs) + MEM_freeN(obj->leafs); + + MEM_freeN(obj); +} + +static void RE_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 ); +} diff --git a/source/blender/render/intern/source/rayobject_instance.c b/source/blender/render/intern/source/rayobject_instance.c new file mode 100644 index 00000000000..9329d110870 --- /dev/null +++ b/source/blender/render/intern/source/rayobject_instance.c @@ -0,0 +1,196 @@ +/** + * $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 RE_rayobject_instance_intersect(RayObject *o, Isect *isec); +static void RE_rayobject_instance_free(RayObject *o); +static void RE_rayobject_instance_bb(RayObject *o, float *min, float *max); +static float RE_rayobject_instance_cost(RayObject *o); + +static RayObjectAPI instance_api = +{ + RE_rayobject_instance_intersect, + NULL, //static void RE_rayobject_instance_add(RayObject *o, RayObject *ob); + NULL, //static void RE_rayobject_instance_done(RayObject *o); + RE_rayobject_instance_free, + RE_rayobject_instance_bb, + RE_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( RE_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 RE_rayobject_unalignRayAPI((RayObject*) obj); +} + +static int RE_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 RE_rayobject_instance_free(RayObject *o) +{ + InstanceRayObject *obj = (InstanceRayObject*)o; + MEM_freeN(obj); +} + +static float RE_rayobject_instance_cost(RayObject *o) +{ + InstanceRayObject *obj = (InstanceRayObject*)o; + return RE_rayobject_cost(obj->target) + RE_COST_INSTANCE; +} + +static void RE_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); + } +} diff --git a/source/blender/render/intern/source/raytrace.c b/source/blender/render/intern/source/rayobject_octree.c index b34fe6a7039..2f0a1a3f53b 100644 --- a/source/blender/render/intern/source/raytrace.c +++ b/source/blender/render/intern/source/rayobject_octree.c @@ -32,6 +32,7 @@ #include <string.h> #include <stdlib.h> #include <float.h> +#include <assert.h> #include "MEM_guardedalloc.h" @@ -41,10 +42,9 @@ #include "BLI_arithb.h" -#include "RE_raytrace.h" +#include "rayobject.h" /* ********** structs *************** */ - #define BRANCH_ARRAY 1024 #define NODE_ARRAY 4096 @@ -61,12 +61,13 @@ typedef struct OcVal 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 */ @@ -74,19 +75,44 @@ typedef struct Octree { float min[3], max[3]; int ocres; int branchcount, nodecount; - char *ocface; /* during building only */ - RayCoordsFunc coordsfunc; - RayCheckFunc checkfunc; - RayObjectTransformFunc transformfunc; - void *userdata; + + /* during building only */ + char *ocface; + + RayFace **ro_nodes; + int ro_nodes_size, ro_nodes_used; + } Octree; -/* ******** globals ***************** */ +static int RE_rayobject_octree_intersect(RayObject *o, Isect *isec); +static void RE_rayobject_octree_add(RayObject *o, RayObject *ob); +static void RE_rayobject_octree_done(RayObject *o); +static void RE_rayobject_octree_free(RayObject *o); +static void RE_rayobject_octree_bb(RayObject *o, float *min, float *max); + +/* + * This function is not expected to be called by current code state. + */ +static float RE_rayobject_octree_cost(RayObject *o) +{ + return 1.0; +} -/* just for statistics */ -static int raycount; -static int accepted, rejected, coherent_ray; +static void RE_rayobject_octree_hint_bb(RayObject *o, RayHint *hint, float *min, float *max) +{ + return; +} +static RayObjectAPI octree_api = +{ + RE_rayobject_octree_intersect, + RE_rayobject_octree_add, + RE_rayobject_octree_done, + RE_rayobject_octree_free, + RE_rayobject_octree_bb, + RE_rayobject_octree_cost, + RE_rayobject_octree_hint_bb +}; /* **************** ocval method ******************* */ /* within one octree node, a set of 3x15 bits defines a 'boundbox' to OR with */ @@ -233,7 +259,7 @@ static int face_in_node(RayFace *face, short x, short y, short z, float rtf[][3] 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; @@ -283,8 +309,7 @@ static void ocwrite(Octree *oc, int ob, RayFace *face, int quad, short x, short while(no->v[a]!=NULL) a++; } - no->v[a]= face; - no->ob[a]= ob; + no->v[a]= (RayFace*) RE_rayobject_align(face); if(quad) calc_ocval_face(rtf[0], rtf[1], rtf[2], rtf[3], x>>2, y>>1, z, &no->ov[a]); @@ -374,13 +399,10 @@ static void d2dda(Octree *oc, short b1, short b2, short c1, short c2, char *ocfa 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++) { @@ -399,7 +421,7 @@ static void filltriangle(Octree *oc, short c1, short c2, char *ocface, short *oc } } -void RE_ray_tree_free(RayTree *tree) +static void RE_rayobject_octree_free(RayObject *tree) { Octree *oc= (Octree*)tree; @@ -439,65 +461,40 @@ void RE_ray_tree_free(RayTree *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( RE_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 RE_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 RE_rayobject_octree_add(RayObject *tree, RayObject *node) +{ + Octree *oc = (Octree*)tree; - return (RayTree*)oc; + assert( RE_rayobject_isRayFace(node) ); + assert( oc->ro_nodes_used < oc->ro_nodes_size ); + oc->ro_nodes[ oc->ro_nodes_used++ ] = (RayFace*)RE_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; @@ -507,28 +504,12 @@ void RE_ray_tree_add_face(RayTree *tree, int ob, RayFace *face) ocres2= oc->ocres*oc->ocres; - ocmax= ocmin+3; - - oc->coordsfunc(face, &v1, &v2, &v3, &v4); + VECCOPY(co1, face->v1); + VECCOPY(co2, face->v2); + VECCOPY(co3, face->v3); + if(face->v4) + VECCOPY(co4, face->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); - } - } - for(c=0;c<3;c++) { rtf[0][c]= (co1[c]-oc->min[c])*ocfac[c] ; rts[0][c]= (short)rtf[0][c]; @@ -536,7 +517,7 @@ void RE_ray_tree_add_face(RayTree *tree, int ob, RayFace *face) 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]; } @@ -546,7 +527,7 @@ void RE_ray_tree_add_face(RayTree *tree, int ob, RayFace *face) 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); } @@ -560,7 +541,7 @@ void RE_ray_tree_add_face(RayTree *tree, int ob, RayFace *face) } 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 { @@ -570,7 +551,7 @@ void RE_ray_tree_add_face(RayTree *tree, int ob, RayFace *face) 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); @@ -584,9 +565,9 @@ void RE_ray_tree_add_face(RayTree *tree, int ob, RayFace *face) 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); @@ -599,7 +580,7 @@ void RE_ray_tree_add_face(RayTree *tree, int ob, RayFace *face) 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); } } } @@ -625,433 +606,107 @@ void RE_ray_tree_add_face(RayTree *tree, int ob, RayFace *face) } } -void RE_ray_tree_done(RayTree *tree) +static void RE_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( RE_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 && is->faceorig) { - 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 RE_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; + + if(!face) break; - nr++; - if(nr==8) { - no= no->next; - if(no==0) return 0; - nr=0; + if( (ov->ocx & ocval.ocx) && (ov->ocy & ocval.ocy) && (ov->ocz & ocval.ocz) ) + { + if( RE_rayobject_intersect( RE_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; - nr++; - if(nr==8) { - no= no->next; - if(no==NULL) break; - nr=0; + if(!face) break; + + if( (ov->ocx & ocval.ocx) && (ov->ocy & ocval.ocy) && (ov->ocz & ocval.ocz) ) + { + if( RE_rayobject_intersect( RE_rayobject_unalignRayFace(face),is) ) + found= 1; } - face= no->v[nr]; - ob= no->ob[nr]; } return found; @@ -1175,23 +830,17 @@ static int do_coherence_test(int ocx1, int ocx2, int ocy1, int ocy2, int ocz1, i */ -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 RE_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; @@ -1200,48 +849,40 @@ int RE_ray_tree_intersect_check(RayTree *tree, Isect *is, RayCheckFunc checkfunc 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; } } } @@ -1256,12 +897,12 @@ int RE_ray_tree_intersect_check(RayTree *tree, Isect *is, RayCheckFunc checkfunc //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; @@ -1269,10 +910,7 @@ int RE_ray_tree_intersect_check(RayTree *tree, Isect *is, RayCheckFunc checkfunc 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) { @@ -1280,11 +918,11 @@ int RE_ray_tree_intersect_check(RayTree *tree, Isect *is, RayCheckFunc checkfunc 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; @@ -1358,11 +996,16 @@ int RE_ray_tree_intersect_check(RayTree *tree, Isect *is, RayCheckFunc checkfunc 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 @@ -1430,13 +1073,8 @@ int RE_ray_tree_intersect_check(RayTree *tree, Isect *is, RayCheckFunc checkfunc } /* 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; -} + diff --git a/source/blender/render/intern/source/rayobject_raycounter.c b/source/blender/render/intern/source/rayobject_raycounter.c new file mode 100644 index 00000000000..a82a21348c1 --- /dev/null +++ b/source/blender/render/intern/source/rayobject_raycounter.c @@ -0,0 +1,87 @@ +/** + * $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 "rayobject.h" +#include "raycounter.h" + +#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("SIMD BB tests: %llu\n", info->simd_bb.test ); + printf("SIMD BB hits: %llu\n", info->simd_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("SIMD tests per ray: %f\n", info->simd_bb.test / ((float)info->raycast.test) ); + printf("SIMD hits per ray: %f\n", info->simd_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->simd_bb.test += tmp->simd_bb.test; + dest->simd_bb.hit += tmp->simd_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 diff --git a/source/blender/render/intern/source/rayshade.c b/source/blender/render/intern/source/rayshade.c index cce99d64b39..f2d61e01f50 100644 --- a/source/blender/render/intern/source/rayshade.c +++ b/source/blender/render/intern/source/rayshade.c @@ -29,6 +29,7 @@ #include <string.h> #include <stdlib.h> #include <float.h> +#include <assert.h> #include "MEM_guardedalloc.h" @@ -57,6 +58,9 @@ #include "volumetric.h" #include "RE_raytrace.h" +#include "rayobject.h" +#include "raycounter.h" + #define RAY_TRA 1 #define RAY_TRAFLIP 2 @@ -68,159 +72,383 @@ /* only to be used here in this file, it's for speed */ extern struct Render R; /* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ */ - -static void vlr_face_coords(RayFace *face, float **v1, float **v2, float **v3, float **v4) +static int test_break(void *data) { - VlakRen *vlr= (VlakRen*)face; - - *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; + Render *re = (Render*)data; + return re->test_break(re->tbh); } -static int vlr_check_intersect(Isect *is, int ob, RayFace *face) +static void RE_rayobject_config_control(RayObject *r, Render *re) { - ObjectInstanceRen *obi= RAY_OBJECT_GET((Render*)is->userdata, ob); - VlakRen *vlr = (VlakRen*)face; - - /* for baking selected to active non-traceable materials might still - * be in the raytree */ - if(!(vlr->mat->mode & MA_TRACEBLE)) - return 0; - - /* I know... cpu cycle waste, might do smarter once */ - if(is->mode==RE_RAY_MIRROR) - return !(vlr->mat->mode & MA_ONLYCAST); - else - return (is->lay & obi->lay); + if(RE_rayobject_isRayAPI(r)) + { + r = RE_rayobject_align( r ); + r->control.data = re; + r->control.test_break = test_break; + } } -static int vlr_check_intersect_solid(Isect *is, int ob, RayFace *face) +RayObject* RE_rayobject_create(Render *re, int type, int size) { - VlakRen *vlr = (VlakRen*)face; + RayObject * res = NULL; - /* solid material types only */ - if (vlr->mat->material_type == MA_TYPE_SURFACE) - return 1; + if(type == R_RAYSTRUCTURE_AUTO) + { + //TODO + //if(detect_simd()) +#ifdef __SSE__ + type = R_RAYSTRUCTURE_SIMD_SVBVH; +#else + type = R_RAYSTRUCTURE_VBVH; +#endif + } + +#ifndef __SSE__ + if(type == R_RAYSTRUCTURE_SIMD_SVBVH || type == R_RAYSTRUCTURE_SIMD_QBVH) + { + puts("Warning: Using VBVH (SSE was disabled at compile time)"); + type = R_RAYSTRUCTURE_VBVH; + } +#endif + + + if(type == R_RAYSTRUCTURE_OCTREE) //TODO dynamic ocres + res = RE_rayobject_octree_create(re->r.ocres, size); + else if(type == R_RAYSTRUCTURE_BLIBVH) + res = RE_rayobject_blibvh_create(size); + else if(type == R_RAYSTRUCTURE_VBVH) + res = RE_rayobject_vbvh_create(size); + else if(type == R_RAYSTRUCTURE_SIMD_SVBVH) + res = RE_rayobject_svbvh_create(size); + else if(type == R_RAYSTRUCTURE_SIMD_QBVH) + res = RE_rayobject_qbvh_create(size); else - return 0; + res = RE_rayobject_vbvh_create(size); //Fallback + + + if(res) + RE_rayobject_config_control( res, re ); + + return res; } -static float *vlr_get_transform(void *userdata, int i) -{ - ObjectInstanceRen *obi= RAY_OBJECT_GET((Render*)userdata, i); +#ifdef RE_RAYCOUNTER +RayCounter re_rc_counter[BLENDER_MAX_THREADS] = {}; +#endif - return (obi->flag & R_TRANSFORMED)? (float*)obi->mat: NULL; -} void freeraytree(Render *re) { - if(re->raytree) { - RE_ray_tree_free(re->raytree); - re->raytree= NULL; + ObjectInstanceRen *obi; + + if(re->raytree) + { + RE_rayobject_free(re->raytree); + re->raytree = NULL; + } + if(re->rayfaces) + { + MEM_freeN(re->rayfaces); + re->rayfaces = NULL; + } + if(re->rayprimitives) + { + MEM_freeN(re->rayprimitives); + re->rayprimitives = 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 makeraytree(Render *re) +static int is_raytraceable_vlr(Render *re, VlakRen *vlr) { - 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; + if((re->flag & R_BAKE_TRACE) || (vlr->mat->mode & MA_TRACEBLE)) + if(vlr->mat->material_type != MA_TYPE_WIRE) + return 1; + return 0; +} - INIT_MINMAX(min, max); +static int is_raytraceable(Render *re, ObjectInstanceRen *obi) +{ + int v; + ObjectRen *obr = obi->obr; - /* 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); - } + if(re->excludeob && obr->ob == re->excludeob) + return 0; - DO_MINMAX(co1, min, max); - DO_MINMAX(co2, min, max); - DO_MINMAX(co3, min, max); + 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; +} - if(vlr->v4) { - VECCOPY(co4, vlr->v4->co); - if(obi->flag & R_TRANSFORMED) - Mat4MulVecfl(obi->mat, co4); - DO_MINMAX(co4, min, max); - } - totface++; +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 = NULL; + VlakPrimitive *vlakprimitive = NULL; + 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 ); + + //Create Ray cast accelaration structure + raytree = obr->raytree = RE_rayobject_create( re, re->r.raytrace_structure, faces ); + if( (re->r.raytrace_options & R_RAYTRACE_USE_LOCAL_COORDS) ) + vlakprimitive = obr->rayprimitives = (VlakPrimitive*)MEM_callocN(faces*sizeof(VlakPrimitive), "ObjectRen primitives"); + else + 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)) + { + if( (re->r.raytrace_options & R_RAYTRACE_USE_LOCAL_COORDS) ) + { + RE_rayobject_add( raytree, RE_vlakprimitive_from_vlak( vlakprimitive, obi, vlr ) ); + vlakprimitive++; + } + else + { + RE_rayface_from_vlak( face, obi, vlr ); + RE_rayobject_add( raytree, RE_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 == NULL) + { + obi->transform_primitives = 0; + obi->raytree = RE_rayobject_instance_create( obr->raytree, obi->mat, obi, obi->obr->rayobi ); + } + + if(obi->raytree) return obi->raytree; + return obi->obr->raytree; +} + +static int has_special_rayobject(Render *re, ObjectInstanceRen *obi) +{ + if( (obi->flag & R_TRANSFORMED) && (re->r.raytrace_options & R_RAYTRACE_USE_INSTANCES) ) + { + 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; + } + } } + return 0; +} +/* + * create a single raytrace structure with all faces + */ +static void makeraytree_single(Render *re) +{ + ObjectInstanceRen *obi; + RayObject *raytree; + RayFace *face = NULL; + VlakPrimitive *vlakprimitive = NULL; + int faces = 0, obs = 0, special = 0; - for(obi=re->instancetable.first; obi; obi=obi->next) { - obr= obi->obr; + 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)) + { + special++; + } + else + { + for(v=0;v<obr->totvlak;v++) + { + VlakRen *vlr = obr->vlaknodes[v>>8].vlak + (v&255); + if(is_raytraceable_vlr(re, vlr)) + faces++; + } + } + } + + //Create raytree + raytree = re->raytree = RE_rayobject_create( re, re->r.raytrace_structure, faces+special ); - if(re->excludeob && obr->ob == re->excludeob) - continue; + if( (re->r.raytrace_options & R_RAYTRACE_USE_LOCAL_COORDS) ) + { + vlakprimitive = re->rayprimitives = (VlakPrimitive*)MEM_callocN(faces*sizeof(VlakPrimitive), "Raytrace vlak-primitives"); + } + else + { + 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(test_break(re)) + break; - for(v=0; v<obr->totvlak; v++, totv++) { - if((v & 255)==0) { - double time= PIL_check_seconds_timer(); + 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; + + if(obi->flag & R_TRANSFORMED) + { + obi->transform_primitives = 1; + } - 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; + for(v=0;v<obr->totvlak;v++) + { + VlakRen *vlr = obr->vlaknodes[v>>8].vlak + (v&255); + if(is_raytraceable_vlr(re, vlr)) + { + if( (re->r.raytrace_options & R_RAYTRACE_USE_LOCAL_COORDS) ) + { + RayObject *obj = RE_vlakprimitive_from_vlak( vlakprimitive, obi, vlr ); + RE_rayobject_add( raytree, obj ); + vlakprimitive++; + } + else + { + 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, RE_rayobject_unalignRayFace(face) ); + face++; + } } } - 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); } } + + if(!test_break(re)) + { + re->i.infostr= "Raytree.. building"; + re->stats_draw(re->sdh, &re->i); - RE_ray_tree_done(re->raytree); + RE_rayobject_done( raytree ); + } +} + +void makeraytree(Render *re) +{ + float min[3], max[3], sub[3]; + int i; - re->i.infostr= NULL; + re->i.infostr= "Raytree.. preparing"; re->stats_draw(re->sdh, &re->i); + + /* disable options not yet suported by octree, + they might actually never be supported (unless people really need it) */ + if(re->r.raytrace_structure == R_RAYSTRUCTURE_OCTREE) + re->r.raytrace_options &= ~( R_RAYTRACE_USE_INSTANCES | R_RAYTRACE_USE_LOCAL_COORDS); + + BENCH(makeraytree_single(re), tree_build); + if(test_break(re)) + { + freeraytree(re); + + re->i.infostr= "Raytree building canceled"; + re->stats_draw(re->sdh, &re->i); + } + else + { + //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] ); + + re->i.infostr= "Raytree finished"; + re->stats_draw(re->sdh, &re->i); + } } 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 */ @@ -450,7 +678,7 @@ static void traceray(ShadeInput *origshi, ShadeResult *origshr, short depth, flo 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, @@ -459,20 +687,17 @@ static void traceray(ShadeInput *origshi, ShadeResult *origshr, short depth, flo /* 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 | RE_SKIP_VLR_RENDER_CHECK; + isec.hint = 0; - if(RE_ray_tree_intersect(R.raytree, &isec)) { + isec.orig.ob = obi; + isec.orig.face = vlr; + RE_RC_INIT(isec, shi); + + if(RE_rayobject_raycast(R.raytree, &isec)) { float d= 1.0f; shi.mask= origshi->mask; @@ -596,6 +821,7 @@ static void traceray(ShadeInput *origshi, ShadeResult *origshr, short depth, flo else { ray_fadeout_endcolor(col, origshi, &shi, origshr, &isec, vec); } + RE_RC_MERGE(&origshi->raycounter, &shi.raycounter); } /* **************** jitter blocks ********** */ @@ -1214,7 +1440,6 @@ void ray_trace(ShadeInput *shi, ShadeResult *shr) 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) @@ -1314,8 +1539,9 @@ static void ray_trace_shadow_tra(Isect *is, ShadeInput *origshi, int depth, int 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 */ @@ -1351,11 +1577,14 @@ static void ray_trace_shadow_tra(Isect *is, ShadeInput *origshi, int depth, int /* 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); } } @@ -1368,9 +1597,11 @@ int ray_trace_shadow_rad(ShadeInput *ship, ShadeResult *shr) 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; } @@ -1378,8 +1609,13 @@ int ray_trace_shadow_rad(ShadeInput *ship, ShadeResult *shr) 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++) { @@ -1391,12 +1627,11 @@ int ray_trace_shadow_rad(ShadeInput *ship, ShadeResult *shr) 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, @@ -1569,6 +1804,7 @@ static float *sphere_sampler(int type, int resol, int thread, int xs, int ys) 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]; @@ -1584,13 +1820,25 @@ static void ray_ao_qmc(ShadeInput *shi, float *shadfac) 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 | RE_SKIP_VLR_RENDER_CHECK | RE_SKIP_VLR_NON_SOLID_MATERIAL; + 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) */ @@ -1628,6 +1876,7 @@ static void ray_ao_qmc(ShadeInput *shi, float *shadfac) QMC_initPixel(qsa, shi->thread); + while (samples < max_samples) { /* sampling, returns quasi-random vector in unit hemisphere */ @@ -1639,14 +1888,14 @@ static void ray_ao_qmc(ShadeInput *shi, float *shadfac) 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_check(R.raytree, &isec, vlr_check_intersect_solid)) { + if(RE_rayobject_raycast(R.raytree, &isec)) { if (R.wrld.aomode & WO_AODIST) fac+= exp(-isec.labda*R.wrld.aodistfac); else fac+= 1.0f; } @@ -1706,18 +1955,29 @@ static void ray_ao_qmc(ShadeInput *shi, float *shadfac) 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 | RE_SKIP_VLR_RENDER_CHECK; + 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; @@ -1764,14 +2024,14 @@ static void ray_ao_spheresamp(ShadeInput *shi, float *shadfac) 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_check(R.raytree, &isec, vlr_check_intersect_solid)) { + if(RE_rayobject_raycast(R.raytree, &isec)) { if (R.wrld.aomode & WO_AODIST) sh+= exp(-isec.labda*R.wrld.aodistfac); else sh+= 1.0f; } @@ -1877,12 +2137,15 @@ static void ray_shadow_qmc(ShadeInput *shi, LampRen *lar, float *lampco, float * 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; @@ -1914,13 +2177,22 @@ static void ray_shadow_qmc(ShadeInput *shi, LampRen *lar, float *lampco, float * 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 | RE_SKIP_VLR_RENDER_CHECK; 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, @@ -1956,11 +2228,11 @@ static void ray_shadow_qmc(ShadeInput *shi, LampRen *lar, float *lampco, float * /* 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) { @@ -1968,7 +2240,7 @@ static void ray_shadow_qmc(ShadeInput *shi, LampRen *lar, float *lampco, float * 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]; @@ -1977,6 +2249,10 @@ static void ray_shadow_qmc(ShadeInput *shi, LampRen *lar, float *lampco, float * } 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) { @@ -1995,7 +2271,7 @@ static void ray_shadow_qmc(ShadeInput *shi, LampRen *lar, float *lampco, float * 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++; @@ -2035,6 +2311,7 @@ static void ray_shadow_jitter(ShadeInput *shi, LampRen *lar, float *lampco, floa 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; @@ -2051,6 +2328,12 @@ static void ray_shadow_jitter(ShadeInput *shi, LampRen *lar, float *lampco, floa 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) { @@ -2062,19 +2345,17 @@ static void ray_shadow_jitter(ShadeInput *shi, LampRen *lar, float *lampco, floa } } - 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 | RE_SKIP_VLR_RENDER_CHECK; if(isec->mode==RE_RAY_SHADOW_TRA) { /* isec.col is like shadfac, so defines amount of light (0.0 is full shadow) */ @@ -2087,7 +2368,7 @@ static void ray_shadow_jitter(ShadeInput *shi, LampRen *lar, float *lampco, floa 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; @@ -2111,11 +2392,13 @@ static void ray_shadow_jitter(ShadeInput *shi, LampRen *lar, float *lampco, floa 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; @@ -2124,19 +2407,29 @@ void ray_shadow(ShadeInput *shi, LampRen *lar, float *shadfac) /* 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); @@ -2149,13 +2442,15 @@ void ray_shadow(ShadeInput *shi, LampRen *lar, float *shadfac) } 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) */ @@ -2165,7 +2460,8 @@ void ray_shadow(ShadeInput *shi, LampRen *lar, float *shadfac) 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); @@ -2174,8 +2470,7 @@ void ray_shadow(ShadeInput *shi, LampRen *lar, float *shadfac) /* 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; } } @@ -2185,31 +2480,34 @@ void ray_shadow(ShadeInput *shi, LampRen *lar, float *shadfac) 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 */ diff --git a/source/blender/render/intern/source/rendercore.c b/source/blender/render/intern/source/rendercore.c index 5db81288c1e..f3db64295a3 100644 --- a/source/blender/render/intern/source/rendercore.c +++ b/source/blender/render/intern/source/rendercore.c @@ -31,6 +31,7 @@ #include <math.h> #include <float.h> #include <string.h> +#include <assert.h> /* External modules: */ #include "MEM_guardedalloc.h" @@ -520,6 +521,12 @@ static void add_filt_passes(RenderLayer *rl, int curmask, int rectx, int offset, } } break; + + case SCE_PASS_RAYHITS: + /* */ + col= &shr->rayhits; + pixsize= 4; + break; } if(col) { fp= rpass->rect + pixsize*offset; @@ -596,6 +603,10 @@ static void add_passes(RenderLayer *rl, int offset, ShadeInput *shi, ShadeResult 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; @@ -2227,6 +2238,7 @@ static void bake_displacement(void *handle, ShadeInput *shi, float dist, int x, } } +#if 0 static int bake_check_intersect(Isect *is, int ob, RayFace *face) { BakeShade *bs = (BakeShade*)is->userdata; @@ -2236,9 +2248,13 @@ static int bake_check_intersect(Isect *is, int ob, RayFace *face) return (R.objectinstance[ob & ~RE_RAY_TRANSFORM_OFFS].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; @@ -2246,15 +2262,17 @@ static int bake_intersect_tree(RayTree* raytree, Isect* isect, float *start, flo 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]; @@ -2264,6 +2282,8 @@ static int bake_intersect_tree(RayTree* raytree, Isect* isect, float *start, flo } return hit; +#endif + return 0; } static void bake_set_vlr_dxyco(BakeShade *bs, float *uv1, float *uv2, float *uv3) @@ -2380,8 +2400,9 @@ static void do_bake_shade(void *handle, int x, int y, float u, float v) 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)) { @@ -2405,8 +2426,8 @@ static void do_bake_shade(void *handle, int x, int y, float u, float v) /* 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); diff --git a/source/blender/render/intern/source/renderdatabase.c b/source/blender/render/intern/source/renderdatabase.c index 30832db5c7d..54863ef3295 100644 --- a/source/blender/render/intern/source/renderdatabase.c +++ b/source/blender/render/intern/source/renderdatabase.c @@ -75,6 +75,7 @@ #include "BKE_DerivedMesh.h" #include "RE_render_ext.h" /* externtex */ +#include "RE_raytrace.h" #include "renderpipeline.h" #include "render_types.h" @@ -872,13 +873,34 @@ void free_renderdata_tables(Render *re) MEM_freeN(obr->mtface); if(obr->mcol) MEM_freeN(obr->mcol); + + if(obr->rayfaces) + { + MEM_freeN(obr->rayfaces); + obr->rayfaces = NULL; + } + if(obr->rayprimitives) + { + MEM_freeN(obr->rayprimitives); + obr->rayprimitives = 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; diff --git a/source/blender/render/intern/source/shadeinput.c b/source/blender/render/intern/source/shadeinput.c index 7541ce53073..e5684e2ebe9 100644 --- a/source/blender/render/intern/source/shadeinput.c +++ b/source/blender/render/intern/source/shadeinput.c @@ -44,6 +44,7 @@ #include "BKE_node.h" /* local include */ +#include "raycounter.h" #include "renderpipeline.h" #include "render_types.h" #include "renderdatabase.h" @@ -181,6 +182,9 @@ void shade_input_do_shade(ShadeInput *shi, ShadeResult *shr) float alpha; /* ------ main shading loop -------- */ +#ifdef RE_RAYCOUNTER + memset(&shi->raycounter, 0, sizeof(shi->raycounter)); +#endif if(shi->mat->nodetree && shi->mat->use_nodes) { ntreeShaderExecTree(shi->mat->nodetree, shi, shr); @@ -230,6 +234,18 @@ void shade_input_do_shade(ShadeInput *shi, ShadeResult *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); } /* **************************************************************************** */ diff --git a/source/blender/render/intern/source/volume_precache.c b/source/blender/render/intern/source/volume_precache.c index 2d5d38a394f..01930956763 100644 --- a/source/blender/render/intern/source/volume_precache.c +++ b/source/blender/render/intern/source/volume_precache.c @@ -46,6 +46,7 @@ #include "DNA_material_types.h" #include "render_types.h" +#include "rendercore.h" #include "renderdatabase.h" #include "volumetric.h" #include "volume_precache.h" @@ -66,11 +67,11 @@ extern struct Render R; /* Recursive test for intersections, from a point inside the mesh, to outside * Number of intersections (depth) determine if a point is inside or outside the mesh */ -int intersect_outside_volume(RayTree *tree, Isect *isect, float *offset, int limit, int depth) +int intersect_outside_volume(RayObject *tree, Isect *isect, float *offset, int limit, int depth) { if (limit == 0) return depth; - if (RE_ray_tree_intersect(tree, isect)) { + if (RE_rayobject_raycast(tree, isect)) { float hitco[3]; hitco[0] = isect->start[0] + isect->labda*isect->vec[0]; @@ -85,9 +86,8 @@ int intersect_outside_volume(RayTree *tree, Isect *isect, float *offset, int lim } /* Uses ray tracing to check if a point is inside or outside an ObjectInstanceRen */ -int point_inside_obi(RayTree *tree, ObjectInstanceRen *obi, float *co) +int point_inside_obi(RayObject *tree, ObjectInstanceRen *obi, float *co) { - float maxsize = RE_ray_tree_max_size(tree); Isect isect; float vec[3] = {0.0f,0.0f,1.0f}; int final_depth=0, depth=0, limit=20; @@ -95,16 +95,21 @@ int point_inside_obi(RayTree *tree, ObjectInstanceRen *obi, float *co) /* set up the isect */ memset(&isect, 0, sizeof(isect)); VECCOPY(isect.start, co); + VECCOPY(isect.vec, vec); + isect.labda = FLT_MAX; + + /* isect.end[0] = co[0] + vec[0] * maxsize; isect.end[1] = co[1] + vec[1] * maxsize; isect.end[2] = co[2] + vec[2] * maxsize; + */ /* and give it a little offset to prevent self-intersections */ VecMulf(vec, 1e-5); VecAddf(isect.start, isect.start, vec); isect.mode= RE_RAY_MIRROR; - isect.face_last= NULL; + isect.last_hit= NULL; isect.lay= -1; final_depth = intersect_outside_volume(tree, &isect, vec, limit, depth); @@ -115,10 +120,12 @@ int point_inside_obi(RayTree *tree, ObjectInstanceRen *obi, float *co) else return 1; } -static int inside_check_func(Isect *is, int ob, RayFace *face) +/* +static int inside_check_func(Isect *is, int ob, RayObject *face) { return 1; } + static void vlr_face_coords(RayFace *face, float **v1, float **v2, float **v3, float **v4) { VlakRen *vlr= (VlakRen*)face; @@ -129,16 +136,16 @@ static void vlr_face_coords(RayFace *face, float **v1, float **v2, float **v3, f *v4 = (vlr->v4)? vlr->v4->co: NULL; } -RayTree *create_raytree_obi(ObjectInstanceRen *obi, float *bbmin, float *bbmax) +RayObject *create_raytree_obi(ObjectInstanceRen *obi, float *bbmin, float *bbmax) { int v; VlakRen *vlr= NULL; - /* create empty raytree */ + / * create empty raytree * / RayTree *tree = RE_ray_tree_create(64, obi->obr->totvlak, bbmin, bbmax, vlr_face_coords, inside_check_func, NULL, NULL); - /* fill it with faces */ + / * fill it with faces * / for(v=0; v<obi->obr->totvlak; v++) { if((v & 255)==0) vlr= obi->obr->vlaknodes[v>>8].vlak; @@ -152,6 +159,7 @@ RayTree *create_raytree_obi(ObjectInstanceRen *obi, float *bbmin, float *bbmax) return tree; } +*/ /* *** light cache filtering *** */ @@ -458,7 +466,7 @@ static void *vol_precache_part(void *data) { VolPrecachePart *pa = (VolPrecachePart *)data; ObjectInstanceRen *obi = pa->obi; - RayTree *tree = pa->tree; + RayObject *tree = pa->tree; ShadeInput *shi = pa->shi; float scatter_col[3] = {0.f, 0.f, 0.f}; float co[3]; @@ -513,7 +521,7 @@ static void precache_setup_shadeinput(Render *re, ObjectInstanceRen *obi, Materi shi->lay = re->scene->lay; } -static void precache_init_parts(Render *re, RayTree *tree, ShadeInput *shi, ObjectInstanceRen *obi, int totthread, int *parts) +static void precache_init_parts(Render *re, RayObject *tree, ShadeInput *shi, ObjectInstanceRen *obi, int totthread, int *parts) { VolumePrecache *vp = obi->volume_precache; int i=0, x, y, z; @@ -628,7 +636,7 @@ void vol_precache_objectinstance_threads(Render *re, ObjectInstanceRen *obi, Mat { VolumePrecache *vp; VolPrecachePart *nextpa, *pa; - RayTree *tree; + RayObject *tree; ShadeInput shi; ListBase threads; float *bbmin=obi->obr->boundbox[0], *bbmax=obi->obr->boundbox[1]; @@ -643,8 +651,11 @@ void vol_precache_objectinstance_threads(Render *re, ObjectInstanceRen *obi, Mat /* create a raytree with just the faces of the instanced ObjectRen, * used for checking if the cached point is inside or outside. */ - tree = create_raytree_obi(obi, bbmin, bbmax); + //tree = create_raytree_obi(obi, bbmin, bbmax); + tree = makeraytree_object(&R, obi); if (!tree) return; + INIT_MINMAX(bbmin, bbmax); + RE_rayobject_merge_bb( tree, bbmin, bbmax); vp = MEM_callocN(sizeof(VolumePrecache), "volume light cache"); @@ -707,8 +718,9 @@ void vol_precache_objectinstance_threads(Render *re, ObjectInstanceRen *obi, Mat BLI_freelistN(&re->volume_precache_parts); if(tree) { - RE_ray_tree_free(tree); - tree= NULL; + //TODO: makeraytree_object creates a tree and saves it on OBI, if we free this tree we should also clear other pointers to it + //RE_rayobject_free(tree); + //tree= NULL; } lightcache_filter(obi->volume_precache); @@ -765,16 +777,17 @@ void free_volume_precache(Render *re) int point_inside_volume_objectinstance(ObjectInstanceRen *obi, float *co) { - RayTree *tree; + RayObject *tree; int inside=0; - tree = create_raytree_obi(obi, obi->obr->boundbox[0], obi->obr->boundbox[1]); + tree = makeraytree_object(&R, obi); //create_raytree_obi(obi, obi->obr->boundbox[0], obi->obr->boundbox[1]); if (!tree) return 0; inside = point_inside_obi(tree, obi, co); - RE_ray_tree_free(tree); - tree= NULL; + //TODO: makeraytree_object creates a tree and saves it on OBI, if we free this tree we should also clear other pointers to it + //RE_rayobject_free(tree); + //tree= NULL; return inside; } diff --git a/source/blender/render/intern/source/volumetric.c b/source/blender/render/intern/source/volumetric.c index cbb74ab752f..91c13207da8 100644 --- a/source/blender/render/intern/source/volumetric.c +++ b/source/blender/render/intern/source/volumetric.c @@ -73,18 +73,6 @@ inline float luminance(float* col) } /* tracing */ - -static int vlr_check_intersect_solid(Isect *is, int ob, RayFace *face) -{ - VlakRen *vlr = (VlakRen*)face; - - /* solid material types only */ - if (vlr->mat->material_type == MA_TYPE_SURFACE) - return 1; - else - return 0; -} - static float vol_get_shadow(ShadeInput *shi, LampRen *lar, float *co) { float visibility = 1.f; @@ -97,42 +85,42 @@ static float vol_get_shadow(ShadeInput *shi, LampRen *lar, float *co) } else if (lar->mode & LA_SHAD_RAY) { /* trace shadow manually, no good lamp api atm */ Isect is; - const float maxsize = RE_ray_tree_max_size(R.raytree); - VecCopyf(is.start, co); if(lar->type==LA_SUN || lar->type==LA_HEMI) { - is.end[0] = co[0] - lar->vec[0] * maxsize; - is.end[1] = co[1] - lar->vec[1] * maxsize; - is.end[2] = co[2] - lar->vec[2] * maxsize; + is.vec[0] = -lar->vec[0]; + is.vec[1] = -lar->vec[1]; + is.vec[2] = -lar->vec[2]; + is.labda = R.maxdist; } else { - VecCopyf(is.end, lar->co); + VECSUB( is.vec, lar->co, is.start ); + is.labda = VecLength( is.vec ); } - is.mode= RE_RAY_MIRROR; + is.mode = RE_RAY_MIRROR; + is.skip = RE_SKIP_VLR_NEIGHBOUR | RE_SKIP_VLR_RENDER_CHECK | RE_SKIP_VLR_NON_SOLID_MATERIAL; + if(lar->mode & (LA_LAYER|LA_LAYER_SHADOW)) is.lay= lar->lay; else is.lay= -1; - is.face_last= (RayFace*)lar->vlr_last[shi->thread]; - is.ob_last= RAY_OBJECT_SET(&R, lar->obi_last[shi->thread]); - is.faceorig= NULL; - is.oborig= RAY_OBJECT_SET(&R, shi->obi); + + is.last_hit = NULL; + is.orig.ob = (void*)shi->obi; + is.orig.face = NULL; + is.last_hit = lar->last_hit[shi->thread]; - if(RE_ray_tree_intersect_check(R.raytree, &is, vlr_check_intersect_solid)) { + if(RE_rayobject_raycast(R.raytree,&is)) { visibility = 0.f; } - lar->vlr_last[shi->thread]= (VlakRen*)is.face_last; - lar->obi_last[shi->thread]= RAY_OBJECT_GET(&R, is.ob_last); + lar->last_hit[shi->thread]= is.last_hit; } return visibility; } static int vol_get_bounds(ShadeInput *shi, float *co, float *vec, float *hitco, Isect *isect, int intersect_type) { - float maxsize = RE_ray_tree_max_size(R.raytree); - /* XXX TODO - get raytrace max distance from object instance's bounding box */ /* need to account for scaling only, but keep coords in camera space... * below code is WIP and doesn't work! @@ -142,20 +130,23 @@ static int vol_get_bounds(ShadeInput *shi, float *co, float *vec, float *hitco, */ VECCOPY(isect->start, co); + VECCOPY(isect->vec, vec ); + isect->labda = FLT_MAX; + /* isect->end[0] = co[0] + vec[0] * maxsize; isect->end[1] = co[1] + vec[1] * maxsize; isect->end[2] = co[2] + vec[2] * maxsize; + */ isect->mode= RE_RAY_MIRROR; - isect->oborig= RAY_OBJECT_SET(&R, shi->obi); - isect->face_last= NULL; - isect->ob_last= 0; + isect->orig.ob = (void*)shi->obi; + isect->last_hit = NULL; isect->lay= -1; - if (intersect_type == VOL_BOUNDS_DEPTH) isect->faceorig= (RayFace*)shi->vlr; - else if (intersect_type == VOL_BOUNDS_SS) isect->faceorig= NULL; + if (intersect_type == VOL_BOUNDS_DEPTH) isect->orig.face = (void*)shi->vlr; + else if (intersect_type == VOL_BOUNDS_SS) isect->orig.face= NULL; - if(RE_ray_tree_intersect(R.raytree, isect)) + if(RE_rayobject_raycast(R.raytree, isect)) { hitco[0] = isect->start[0] + isect->labda*isect->vec[0]; hitco[1] = isect->start[1] + isect->labda*isect->vec[1]; @@ -202,23 +193,20 @@ static void shade_intersection(ShadeInput *shi, float *col, Isect *is) static void vol_trace_behind(ShadeInput *shi, VlakRen *vlr, float *co, float *col) { Isect isect; - float maxsize = RE_ray_tree_max_size(R.raytree); VECCOPY(isect.start, co); - isect.end[0] = isect.start[0] + shi->view[0] * maxsize; - isect.end[1] = isect.start[1] + shi->view[1] * maxsize; - isect.end[2] = isect.start[2] + shi->view[2] * maxsize; - - isect.faceorig= (RayFace *)vlr; + VECCOPY(isect.vec, shi->view); + isect.labda = FLT_MAX; isect.mode= RE_RAY_MIRROR; - isect.oborig= RAY_OBJECT_SET(&R, shi->obi); - isect.face_last= NULL; - isect.ob_last= 0; + isect.skip = RE_SKIP_VLR_NEIGHBOUR | RE_SKIP_VLR_RENDER_CHECK; + isect.orig.ob = (void*) shi->obi; + isect.orig.face = (void*)vlr; + isect.last_hit = NULL; isect.lay= -1; /* check to see if there's anything behind the volume, otherwise shade the sky */ - if(RE_ray_tree_intersect(R.raytree, &isect)) { + if(RE_rayobject_raycast(R.raytree, &isect)) { shade_intersection(shi, col, &isect); } else { shadeSkyView(col, co, shi->view, NULL, shi->thread); @@ -519,7 +507,7 @@ void vol_shade_one_lamp(struct ShadeInput *shi, float *co, LampRen *lar, float * /* find minimum of volume bounds, or lamp coord */ if (vol_get_bounds(shi, co, lv, hitco, &is, VOL_BOUNDS_SS)) { float dist = VecLenf(co, hitco); - VlakRen *vlr = (VlakRen *)is.face; + VlakRen *vlr = (VlakRen *)is.hit.face; /* simple internal shadowing */ if (vlr->mat->material_type == MA_TYPE_SURFACE) { @@ -719,7 +707,7 @@ static void volume_trace(struct ShadeInput *shi, struct ShadeResult *shr, int in /* (ray intersect ignores front faces here) */ else if (vol_get_bounds(shi, shi->co, shi->view, hitco, &is, VOL_BOUNDS_DEPTH)) { - VlakRen *vlr = (VlakRen *)is.face; + VlakRen *vlr = (VlakRen *)is.hit.face; startco = shi->co; endco = hitco; @@ -728,7 +716,7 @@ static void volume_trace(struct ShadeInput *shi, struct ShadeResult *shr, int in /* if it's another face in the same material */ if (vlr->mat == shi->mat) { /* trace behind the 2nd (raytrace) hit point */ - vol_trace_behind(shi, (VlakRen *)is.face, endco, col); + vol_trace_behind(shi, (VlakRen *)is.hit.face, endco, col); } else { shade_intersection(shi, col, &is); } |