svn merge -r 22571:22800 https://svn.blender.org/svnroot/bf-blender/trunk/blender
authorAndre Susano Pinto <andresusanopinto@gmail.com>
Tue, 15 Sep 2009 15:34:00 +0000 (15:34 +0000)
committerAndre Susano Pinto <andresusanopinto@gmail.com>
Tue, 15 Sep 2009 15:34:00 +0000 (15:34 +0000)
svn merge -r 22800:23207 https://svn.blender.org/svnroot/bf-blender/trunk/blender

Merged volumetric with new raytrace code (it compiles and rendered volume-cube.blend withouth problems)

Part 2:
everything except source/blender (merged on part1)

41 files changed:
blenderplayer/CMakeLists.txt [new file with mode: 0644]
release/ui/buttons_scene.py
source/blender/blenkernel/BKE_utildefines.h
source/blender/blenlib/BLI_memarena.h
source/blender/blenlib/intern/BLI_kdopbvh.c
source/blender/blenlib/intern/BLI_memarena.c
source/blender/editors/armature/meshlaplacian.c
source/blender/makesdna/DNA_scene_types.h
source/blender/makesrna/intern/rna_scene.c
source/blender/render/SConscript
source/blender/render/extern/include/RE_raytrace.h
source/blender/render/extern/include/RE_shader_ext.h
source/blender/render/intern/include/raycounter.h [new file with mode: 0644]
source/blender/render/intern/include/rayobject.h [new file with mode: 0644]
source/blender/render/intern/include/render_types.h
source/blender/render/intern/include/rendercore.h
source/blender/render/intern/raytrace/bvh.h [new file with mode: 0644]
source/blender/render/intern/raytrace/rayobject_bih.cpp [new file with mode: 0644]
source/blender/render/intern/raytrace/rayobject_bvh.cpp [new file with mode: 0644]
source/blender/render/intern/raytrace/rayobject_hint.h [new file with mode: 0644]
source/blender/render/intern/raytrace/rayobject_qbvh.cpp [new file with mode: 0644]
source/blender/render/intern/raytrace/rayobject_rtbuild.cpp [new file with mode: 0644]
source/blender/render/intern/raytrace/rayobject_rtbuild.h [new file with mode: 0644]
source/blender/render/intern/raytrace/rayobject_svbvh.cpp [new file with mode: 0644]
source/blender/render/intern/raytrace/rayobject_vbvh.cpp [new file with mode: 0644]
source/blender/render/intern/raytrace/reorganize.h [new file with mode: 0644]
source/blender/render/intern/raytrace/svbvh.h [new file with mode: 0644]
source/blender/render/intern/raytrace/vbvh.h [new file with mode: 0644]
source/blender/render/intern/source/pipeline.c
source/blender/render/intern/source/rayobject.c [new file with mode: 0644]
source/blender/render/intern/source/rayobject_blibvh.c [new file with mode: 0644]
source/blender/render/intern/source/rayobject_instance.c [new file with mode: 0644]
source/blender/render/intern/source/rayobject_octree.c [moved from source/blender/render/intern/source/raytrace.c with 59% similarity]
source/blender/render/intern/source/rayobject_raycounter.c [new file with mode: 0644]
source/blender/render/intern/source/rayshade.c
source/blender/render/intern/source/rendercore.c
source/blender/render/intern/source/renderdatabase.c
source/blender/render/intern/source/shadeinput.c
source/blender/render/intern/source/volume_precache.c
source/blender/render/intern/source/volumetric.c
source/blender/windowmanager/intern/wm_init_exit.c

diff --git a/blenderplayer/CMakeLists.txt b/blenderplayer/CMakeLists.txt
new file mode 100644 (file)
index 0000000..0407361
--- /dev/null
@@ -0,0 +1,133 @@
+# $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) 2006, Blender Foundation
+# All rights reserved.
+#
+# The Original Code is: all of this file.
+#
+# Contributor(s): Jacques Beaurain.
+#
+# ***** END GPL LICENSE BLOCK *****
+
+MESSAGE(STATUS "Configuring blenderplayer")
+
+SETUP_LIBDIRS()
+
+IF(WITH_QUICKTIME)
+  ADD_DEFINITIONS(-DWITH_QUICKTIME)
+ENDIF(WITH_QUICKTIME)
+
+IF(CMAKE_SYSTEM_NAME MATCHES "Linux")
+  ADD_DEFINITIONS(-DWITH_BINRELOC)
+  INCLUDE_DIRECTORIES(${BINRELOC_INC})
+ENDIF(CMAKE_SYSTEM_NAME MATCHES "Linux")
+
+ADD_CUSTOM_COMMAND(
+  OUTPUT ${CMAKE_CURRENT_BINARY_DIR}/dna.c
+  COMMAND ${CMAKE_BINARY_DIR}/bin/${CMAKE_CFG_INTDIR}/makesdna ${CMAKE_CURRENT_BINARY_DIR}/dna.c ${CMAKE_SOURCE_DIR}/source/blender/makesdna/
+  DEPENDS ${CMAKE_BINARY_DIR}/bin/${CMAKE_CFG_INTDIR}/makesdna
+)
+
+IF(WIN32)
+  ADD_EXECUTABLE(blenderplayer ${EXETYPE} ${CMAKE_CURRENT_BINARY_DIR}/dna.c ../source/icons/winblender.rc)
+ELSE(WIN32)
+  ADD_EXECUTABLE(blenderplayer ${CMAKE_CURRENT_BINARY_DIR}/dna.c)
+ENDIF(WIN32)
+
+ADD_DEPENDENCIES(blenderplayer makesdna)
+
+FILE(READ ${CMAKE_BINARY_DIR}/cmake_blender_libs.txt BLENDER_LINK_LIBS)
+
+SET(BLENDER_LINK_LIBS ${BLENDER_LINK_LIBS} gp_common gp_ghost blenkernel_blc)
+
+IF(CMAKE_SYSTEM_NAME MATCHES "Linux")
+  SET(BLENDER_LINK_LIBS ${BLENDER_LINK_LIBS} extern_binreloc)
+ENDIF(CMAKE_SYSTEM_NAME MATCHES "Linux")
+
+IF(UNIX)
+  # Sort libraries
+  SET(BLENDER_SORTED_LIBS
+    gp_ghost 
+    gp_common 
+    bf_string 
+    bf_ghost 
+    bf_blenkernel
+    bf_blenloader 
+    bf_blenpluginapi 
+    bf_blroutines 
+    bf_converter 
+    bf_ketsji 
+    bf_bullet 
+    bf_common 
+    bf_dummy 
+    bf_logic 
+    bf_rasterizer 
+    bf_oglrasterizer 
+    bf_expressions 
+    bf_scenegraph 
+       bf_IK
+    bf_moto 
+    bf_kernel 
+    bf_nodes
+       bf_gpu
+    bf_imbuf
+    bf_avi 
+    kx_network 
+    bf_ngnetwork 
+    bf_loopbacknetwork 
+    extern_bullet 
+    bf_guardedalloc 
+    bf_memutil 
+    bf_blenlib 
+    bf_cineon 
+    bf_openexr 
+    extern_libopenjpeg 
+    bf_dds
+    bf_readblenfile 
+    blenkernel_blc
+    extern_binreloc
+       extern_glew
+  )
+  
+  IF(WITH_QUICKTIME)
+    SET(BLENDER_SORTED_LIBS ${BLENDER_SORTED_LIBS} quicktime)
+  ENDIF(WITH_QUICKTIME)
+
+  IF(WITH_CXX_GUARDEDALLOC)
+    SET(BLENDER_SORTED_LIBS ${BLENDER_SORTED_LIBS} bf_guardedalloc_cpp)
+  ENDIF(WITH_CXX_GUARDEDALLOC)
+
+  FOREACH(SORTLIB ${BLENDER_SORTED_LIBS})
+    SET(REMLIB ${SORTLIB})
+    FOREACH(SEARCHLIB ${BLENDER_LINK_LIBS})
+      IF(${SEARCHLIB} STREQUAL ${SORTLIB})
+        SET(REMLIB "")
+      ENDIF(${SEARCHLIB} STREQUAL ${SORTLIB})
+    ENDFOREACH(SEARCHLIB)
+    IF(REMLIB)
+      MESSAGE(STATUS "Removing library ${REMLIB} from blenderplayer linking because: not configured")
+      LIST(REMOVE_ITEM BLENDER_SORTED_LIBS ${REMLIB})
+    ENDIF(REMLIB)
+  ENDFOREACH(SORTLIB)
+
+  TARGET_LINK_LIBRARIES(blenderplayer ${BLENDER_SORTED_LIBS})
+ELSE(UNIX)
+  TARGET_LINK_LIBRARIES(blenderplayer ${BLENDER_LINK_LIBS})
+ENDIF(UNIX)
+
+SETUP_LIBLINKS(blenderplayer)
index 3c321f11f6e4788fcaf6a26b2b70e74a7dcf1950..2681f1134e1b43e3e07a6a632d081d4252b11fdb 100644 (file)
@@ -173,6 +173,8 @@ class SCENE_PT_performance(RenderButtonsPanel):
                sub.active = rd.render_raytracing
                sub.itemL(text="Ray Tracing Octree:")
                sub.itemR(rd, "octree_resolution", text="")
+               sub.itemR(rd, "raytrace_structure", text="Structure")
+               sub.itemR(rd, "raytrace_tree_type", text="Tree Type")
 
 class SCENE_PT_post_processing(RenderButtonsPanel):
        __label__ = "Post Processing"
index 7d8cb41db825e07710281e1f5c867b7cc0edef43..c0ed843017702855a1a955b78c58730c624691ee 100644 (file)
 
 #define INIT_MINMAX2(min, max) { (min)[0]= (min)[1]= 1.0e30f; (max)[0]= (max)[1]= -1.0e30f; }
 
+#define DO_MIN(vec, min) { if( (min)[0]>(vec)[0] ) (min)[0]= (vec)[0];      \
+                                                         if( (min)[1]>(vec)[1] ) (min)[1]= (vec)[1];   \
+                                                         if( (min)[2]>(vec)[2] ) (min)[2]= (vec)[2]; } \
+
+#define DO_MAX(vec, max) { if( (max)[0]<(vec)[0] ) (max)[0]= (vec)[0];         \
+                                                         if( (max)[1]<(vec)[1] ) (max)[1]= (vec)[1];   \
+                                                         if( (max)[2]<(vec)[2] ) (max)[2]= (vec)[2]; } \
+
 #define DO_MINMAX(vec, min, max) { if( (min)[0]>(vec)[0] ) (min)[0]= (vec)[0]; \
                                                          if( (min)[1]>(vec)[1] ) (min)[1]= (vec)[1]; \
                                                          if( (min)[2]>(vec)[2] ) (min)[2]= (vec)[2]; \
index a2954f8fa0d51d3473fbe5b373d9f8fb17c349c5..fcf6ae02900a5d8c1fcbbae6c29c47302f0f9390 100644 (file)
 #ifndef BLI_MEMARENA_H
 #define BLI_MEMARENA_H
 
+#ifdef __cplusplus
+extern "C" {
+#endif
+
        /* A reasonable standard buffer size, big
         * enough to not cause much internal fragmentation, 
         * small enough not to waste resources
@@ -53,7 +57,14 @@ void                         BLI_memarena_free       (struct MemArena *ma);
 void                           BLI_memarena_use_malloc (struct MemArena *ma);
 void                           BLI_memarena_use_calloc (struct MemArena *ma);
 
+void                           BLI_memarena_use_align(struct MemArena *ma, int align);
+
 void*                          BLI_memarena_alloc      (struct MemArena *ma, int size);
 
+#ifdef __cplusplus
+}
+#endif
+
+
 #endif
 
index 61d9cce1a583beabab700bf5a38dc7fde515a22c..c5e6ca4b1aea0b22cc46e47db191e20a7a54c85a 100644 (file)
@@ -52,6 +52,7 @@ typedef struct BVHNode
 {
        struct BVHNode **children;
        struct BVHNode *parent; // some user defined traversed need that
+       struct BVHNode *skip[2];
        float *bv;              // Bounding volume of all nodes, max 13 axis
        int index;              // face, edge, vertex index
        char totnode;   // how many nodes are used, used for speedup
@@ -101,6 +102,8 @@ typedef struct BVHRayCastData
 
        BVHTreeRay    ray;
        float ray_dot_axis[13];
+       float idot_axis[13];
+       int index[6];
 
        BVHTreeRayHit hit;
 } BVHRayCastData;
@@ -353,6 +356,23 @@ int partition_nth_element(BVHNode **a, int _begin, int _end, int n, int axis){
 }
 
 //////////////////////////////////////////////////////////////////////////////////////////////////////
+static void build_skip_links(BVHTree *tree, BVHNode *node, BVHNode *left, BVHNode *right)
+{
+       int i;
+       
+       node->skip[0] = left;
+       node->skip[1] = right;
+       
+       for (i = 0; i < node->totnode; i++)
+       {
+               if(i+1 < node->totnode)
+                       build_skip_links(tree, node->children[i], left, node->children[i+1] );
+               else
+                       build_skip_links(tree, node->children[i], left, right );
+
+               left = node->children[i];
+       }
+}
 
 /*
  * BVHTree bounding volumes functions
@@ -939,6 +959,7 @@ void BLI_bvhtree_balance(BVHTree *tree)
        for(i = 0; i < tree->totbranch; i++)
                tree->nodes[tree->totleaf + i] = branches_array + i;
 
+       build_skip_links(tree, tree->nodes[tree->totleaf], NULL, NULL);
        //bvhtree_info(tree);
 }
 
@@ -1405,6 +1426,7 @@ int BLI_bvhtree_find_nearest(BVHTree *tree, const float *co, BVHTreeNearest *nea
  * raycast is done by performing a DFS on the BVHTree and saving the closest hit
  */
 
+
 //Determines the distance that the ray must travel to hit the bounding volume of the given node
 static float ray_nearest_hit(BVHRayCastData *data, float *bv)
 {
@@ -1443,13 +1465,40 @@ static float ray_nearest_hit(BVHRayCastData *data, float *bv)
        return low;
 }
 
+//Determines the distance that the ray must travel to hit the bounding volume of the given node
+//Based on Tactical Optimization of Ray/Box Intersection, by Graham Fyffe
+//[http://tog.acm.org/resources/RTNews/html/rtnv21n1.html#art9]
+//
+//TODO this doens't has data->ray.radius in consideration
+static float fast_ray_nearest_hit(const BVHRayCastData *data, const BVHNode *node)
+{
+       const float *bv = node->bv;
+       float dist;
+       
+       float t1x = (bv[data->index[0]] - data->ray.origin[0]) * data->idot_axis[0];
+       float t2x = (bv[data->index[1]] - data->ray.origin[0]) * data->idot_axis[0];
+       float t1y = (bv[data->index[2]] - data->ray.origin[1]) * data->idot_axis[1];
+       float t2y = (bv[data->index[3]] - data->ray.origin[1]) * data->idot_axis[1];
+       float t1z = (bv[data->index[4]] - data->ray.origin[2]) * data->idot_axis[2];
+       float t2z = (bv[data->index[5]] - data->ray.origin[2]) * data->idot_axis[2];
+
+       if(t1x > t2y || t2x < t1y || t1x > t2z || t2x < t1z || t1y > t2z || t2y < t1z) return FLT_MAX;
+       if(t2x < 0.0 || t2y < 0.0 || t2z < 0.0) return FLT_MAX;
+       if(t1x > data->hit.dist || t1y > data->hit.dist || t1z > data->hit.dist) return FLT_MAX;
+
+       dist = t1x;
+       if (t1y > dist) dist = t1y;
+    if (t1z > dist) dist = t1z;
+       return dist;
+}
+
 static void dfs_raycast(BVHRayCastData *data, BVHNode *node)
 {
        int i;
 
        //ray-bv is really fast.. and simple tests revealed its worth to test it
        //before calling the ray-primitive functions
-       float dist = ray_nearest_hit(data, node->bv);
+       float dist = fast_ray_nearest_hit(data, node);
        if(dist >= data->hit.dist) return;
 
        if(node->totnode == 0)
@@ -1483,6 +1532,37 @@ static void dfs_raycast(BVHRayCastData *data, BVHNode *node)
        }
 }
 
+static void iterative_raycast(BVHRayCastData *data, BVHNode *node)
+{
+       while(node)
+       {
+               float dist = fast_ray_nearest_hit(data, node);
+               if(dist >= data->hit.dist)
+               {
+                       node = node->skip[1];
+                       continue;
+               }
+
+               if(node->totnode == 0)
+               {
+                       if(data->callback)
+                               data->callback(data->userdata, node->index, &data->ray, &data->hit);
+                       else
+                       {
+                               data->hit.index = node->index;
+                               data->hit.dist  = dist;
+                               VECADDFAC(data->hit.co, data->ray.origin, data->ray.direction, dist);
+                       }
+                       
+                       node = node->skip[1];
+               }
+               else
+               {
+                       node = node->children[0];
+               }       
+       }
+}
+
 int BLI_bvhtree_ray_cast(BVHTree *tree, const float *co, const float *dir, float radius, BVHTreeRayHit *hit, BVHTree_RayCastCallback callback, void *userdata)
 {
        int i;
@@ -1503,9 +1583,16 @@ int BLI_bvhtree_ray_cast(BVHTree *tree, const float *co, const float *dir, float
        for(i=0; i<3; i++)
        {
                data.ray_dot_axis[i] = INPR( data.ray.direction, KDOP_AXES[i]);
+               data.idot_axis[i] = 1.0f / data.ray_dot_axis[i];
 
                if(fabs(data.ray_dot_axis[i]) < FLT_EPSILON)
+               {
                        data.ray_dot_axis[i] = 0.0;
+               }
+               data.index[2*i] = data.idot_axis[i] < 0.0 ? 1 : 0;
+               data.index[2*i+1] = 1 - data.index[2*i];
+               data.index[2*i]   += 2*i;
+               data.index[2*i+1] += 2*i;
        }
 
 
@@ -1518,7 +1605,10 @@ int BLI_bvhtree_ray_cast(BVHTree *tree, const float *co, const float *dir, float
        }
 
        if(root)
+       {
                dfs_raycast(&data, root);
+//             iterative_raycast(&data, root);
+       }
 
 
        if(hit)
index 87d2f0426b21e6a1ecc7aae6a23016ee84755652..275ab12540bd2d76135cd9ba34dbbeb16d10a685 100644 (file)
@@ -45,6 +45,7 @@ struct MemArena {
        int bufsize, cursize;
        
        int use_calloc; 
+       int align;
        
        LinkNode *bufs;
 };
@@ -52,6 +53,7 @@ struct MemArena {
 MemArena *BLI_memarena_new(int bufsize) {
        MemArena *ma= MEM_callocN(sizeof(*ma), "memarena");
        ma->bufsize= bufsize;
+       ma->align = 8;
        
        return ma;
 }
@@ -64,6 +66,11 @@ void BLI_memarena_use_malloc(MemArena *ma) {
        ma->use_calloc= 0;
 }
 
+void BLI_memarena_use_align(struct MemArena *ma, int align) {
+       /* align should be a power of two */
+       ma->align = align;
+}
+
 void BLI_memarena_free(MemArena *ma) {
        BLI_linklist_free(ma->bufs, (void(*)(void*)) MEM_freeN);
        MEM_freeN(ma);
@@ -77,16 +84,28 @@ void *BLI_memarena_alloc(MemArena *ma, int size) {
 
                /* ensure proper alignment by rounding
                 * size up to multiple of 8 */  
-       size= PADUP(size, 8);
+       size= PADUP(size, ma->align);
        
        if (size>ma->cursize) {
-               ma->cursize= (size>ma->bufsize)?size:ma->bufsize;
+               unsigned char *tmp;
+               
+               if(size > ma->bufsize - (ma->align - 1))
+               {
+                       ma->cursize = PADUP(size+1, ma->align);
+               }
+               else ma->cursize = ma->bufsize;
+
                if(ma->use_calloc)
                        ma->curbuf= MEM_callocN(ma->cursize, "memarena calloc");
                else
                        ma->curbuf= MEM_mallocN(ma->cursize, "memarena malloc");
                
                BLI_linklist_prepend(&ma->bufs, ma->curbuf);
+
+               /* align alloc'ed memory (needed if align > 8) */
+               tmp = (unsigned char*)PADUP( (intptr_t) ma->curbuf, ma->align);
+               ma->cursize -= (tmp - ma->curbuf);
+               ma->curbuf = tmp;               
        }
        
        ptr= ma->curbuf;
@@ -95,3 +114,4 @@ void *BLI_memarena_alloc(MemArena *ma, int size) {
        
        return ptr;
 }
+
index a6c94bee5b1a216373a8bdbbb42b172deded9d87..7f95fb47d6177eb7cc51a1ba8c493d98c6625711 100644 (file)
@@ -30,6 +30,7 @@
 
 #include <math.h>
 #include <string.h>
+#include <assert.h>
 
 #include "MEM_guardedalloc.h"
 
@@ -105,7 +106,7 @@ struct LaplacianSystem {
                float *p;                       /* values from all p vectors */
                float *mindist;         /* minimum distance to a bone for all vertices */
                
-               RayTree *raytree;       /* ray tracing acceleration structure */
+               RayObject *raytree;     /* ray tracing acceleration structure */
                MFace **vface;          /* a face that the vertex belongs to */
        } heat;
 
@@ -394,77 +395,32 @@ float laplacian_system_get_solution(int v)
 #define DISTANCE_EPSILON       1e-4f
 
 /* Raytracing for vertex to bone visibility */
-
-static LaplacianSystem *HeatSys = NULL;
-
-static void heat_ray_coords_func(RayFace *face, float **v1, float **v2, float **v3, float **v4)
-{
-       MFace *mface= (MFace*)face;
-       float (*verts)[3]= HeatSys->heat.verts;
-
-       *v1= verts[mface->v1];
-       *v2= verts[mface->v2];
-       *v3= verts[mface->v3];
-       *v4= (mface->v4)? verts[mface->v4]: NULL;
-}
-
-static int heat_ray_check_func(Isect *is, int ob, RayFace *face)
-{
-       float *v1, *v2, *v3, *v4, nor[3];
-
-       /* don't intersect if the ray faces along the face normal */
-       heat_ray_coords_func(face, &v1, &v2, &v3, &v4);
-
-       if(v4) CalcNormFloat4(v1, v2, v3, v4, nor);
-       else CalcNormFloat(v1, v2, v3, nor);
-
-       return (INPR(nor, is->vec) < 0);
-}
-
 static void heat_ray_tree_create(LaplacianSystem *sys)
 {
        Mesh *me = sys->heat.mesh;
-       RayTree *tree;
        MFace *mface;
-       float min[3], max[3];
        int a;
 
-       /* create a raytrace tree from the mesh */
-       INIT_MINMAX(min, max);
-
-       for(a=0; a<me->totvert; a++)
-               DO_MINMAX(sys->heat.verts[a], min, max);
-
-       tree= RE_ray_tree_create(64, me->totface, min, max,
-               heat_ray_coords_func, heat_ray_check_func, NULL, NULL);
-       
-       sys->heat.vface= MEM_callocN(sizeof(MFace*)*me->totvert, "HeatVFaces");
-
-       HeatSys= sys;
+       assert(0); //TODO
+       //sys->heat.raytree = RE_rayobject_mesh_create(me, me);
 
+       sys->heat.vface = MEM_callocN(sizeof(MFace*)*me->totvert, "HeatVFaces");
        for(a=0, mface=me->mface; a<me->totface; a++, mface++) {
-               RE_ray_tree_add_face(tree, 0, mface);
-
                sys->heat.vface[mface->v1]= mface;
                sys->heat.vface[mface->v2]= mface;
                sys->heat.vface[mface->v3]= mface;
                if(mface->v4) sys->heat.vface[mface->v4]= mface;
        }
-
-       HeatSys= NULL;
-       
-       RE_ray_tree_done(tree);
-
-       sys->heat.raytree= tree;
 }
 
 static int heat_ray_bone_visible(LaplacianSystem *sys, int vertex, int bone)
 {
        Isect isec;
        MFace *mface;
-       float dir[3];
+       float end[3];
        int visible;
 
+       assert( 0 );
        mface= sys->heat.vface[vertex];
        if(!mface)
                return 1;
@@ -473,22 +429,24 @@ static int heat_ray_bone_visible(LaplacianSystem *sys, int vertex, int bone)
        memset(&isec, 0, sizeof(isec));
        isec.mode= RE_RAY_SHADOW;
        isec.lay= -1;
-       isec.face_last= NULL;
-       isec.faceorig= mface;
+       isec.orig.face = mface;
+       isec.skip = RE_SKIP_CULLFACE;
 
        VECCOPY(isec.start, sys->heat.verts[vertex]);
-       PclosestVL3Dfl(isec.end, isec.start,
-               sys->heat.root[bone], sys->heat.tip[bone]);
+       PclosestVL3Dfl(end, isec.start, sys->heat.root[bone], sys->heat.tip[bone]);
+
+       VECSUB(isec.vec, end, isec.start);
+       isec.labda = 1.0f;
 
+#if 0
+       TODO
        /* add an extra offset to the start position to avoid self intersection */
-       VECSUB(dir, isec.end, isec.start);
+       VECCOPY(dir, isec.vec);
        Normalize(dir);
        VecMulf(dir, 1e-5);
        VecAddf(isec.start, isec.start, dir);
-       
-       HeatSys= sys;
-       visible= !RE_ray_tree_intersect(sys->heat.raytree, &isec);
-       HeatSys= NULL;
+#endif 
+       visible= !RE_rayobject_raycast(sys->heat.raytree, &isec);
 
        return visible;
 }
@@ -752,7 +710,7 @@ void heat_bone_weighting(Object *ob, Mesh *me, float (*verts)[3], int numbones,
        /* free */
        if(vertsflipped) MEM_freeN(vertsflipped);
 
-       RE_ray_tree_free(sys->heat.raytree);
+       RE_rayobject_free(sys->heat.raytree);
        MEM_freeN(sys->heat.vface);
 
        MEM_freeN(sys->heat.mindist);
@@ -1049,7 +1007,7 @@ typedef struct MeshDeformBind {
        int *varidx;
 
        /* raytrace */
-       RayTree *raytree;
+       RayObject *raytree;
 } MeshDeformBind;
 
 /* ray intersection */
@@ -1173,7 +1131,7 @@ static void meshdeform_ray_tree_free(MeshDeformBind *mdb)
 static int meshdeform_intersect(MeshDeformBind *mdb, Isect *isec)
 {
        MFace *mface;
-       float face[4][3], co[3], uvw[3], len, nor[3];
+       float face[4][3], co[3], uvw[3], len, nor[3], end[3];
        int f, hit, is= 0, totface;
 
        isec->labda= 1e10;
@@ -1181,6 +1139,8 @@ static int meshdeform_intersect(MeshDeformBind *mdb, Isect *isec)
        mface= mdb->cagedm->getFaceArray(mdb->cagedm);
        totface= mdb->cagedm->getNumFaces(mdb->cagedm);
 
+       VECADDFAC( end, isec->start, isec->vec, isec->labda );
+
        for(f=0; f<totface; f++, mface++) {
                VECCOPY(face[0], mdb->cagecos[mface->v1]);
                VECCOPY(face[1], mdb->cagecos[mface->v2]);
@@ -1188,26 +1148,26 @@ static int meshdeform_intersect(MeshDeformBind *mdb, Isect *isec)
 
                if(mface->v4) {
                        VECCOPY(face[3], mdb->cagecos[mface->v4]);
-                       hit= meshdeform_tri_intersect(isec->start, isec->end, face[0], face[1], face[2], co, uvw);
+                       hit = meshdeform_tri_intersect(isec->start, end, face[0], face[1], face[2], co, uvw);
 
                        if(hit) {
                                CalcNormFloat(face[0], face[1], face[2], nor);
                        }
                        else {
-                               hit= meshdeform_tri_intersect(isec->start, isec->end, face[0], face[2], face[3], co, uvw);
+                               hit= meshdeform_tri_intersect(isec->start, end, face[0], face[2], face[3], co, uvw);
                                CalcNormFloat(face[0], face[2], face[3], nor);
                        }
                }
                else {
-                       hit= meshdeform_tri_intersect(isec->start, isec->end, face[0], face[1], face[2], co, uvw);
+                       hit= meshdeform_tri_intersect(isec->start, end, face[0], face[1], face[2], co, uvw);
                        CalcNormFloat(face[0], face[1], face[2], nor);
                }
 
                if(hit) {
-                       len= VecLenf(isec->start, co)/VecLenf(isec->start, isec->end);
+                       len= VecLenf(isec->start, co)/VecLenf(isec->start, end);
                        if(len < isec->labda) {
                                isec->labda= len;
-                               isec->face= mface;
+                               isec->hit.face = mface;
                                isec->isect= (INPR(isec->vec, nor) <= 0.0f);
                                is= 1;
                        }
@@ -1223,20 +1183,18 @@ static MDefBoundIsect *meshdeform_ray_tree_intersect(MeshDeformBind *mdb, float
        Isect isec;
        float (*cagecos)[3];
        MFace *mface;
-       float vert[4][3], len;
+       float vert[4][3], len, end[3];
        static float epsilon[3]= {0, 0, 0}; //1e-4, 1e-4, 1e-4};
 
        /* setup isec */
        memset(&isec, 0, sizeof(isec));
        isec.mode= RE_RAY_MIRROR; /* we want the closest intersection */
        isec.lay= -1;
-       isec.face_last= NULL;
-       isec.faceorig= NULL;
        isec.labda= 1e10f;
 
        VECADD(isec.start, co1, epsilon);
-       VECADD(isec.end, co2, epsilon);
-       VECSUB(isec.vec, isec.end, isec.start);
+       VECADD(end, co2, epsilon);
+       VECSUB(isec.vec, end, isec.start);
 
 #if 0
        /*if(RE_ray_tree_intersect(mdb->raytree, &isec)) {*/
@@ -1244,7 +1202,7 @@ static MDefBoundIsect *meshdeform_ray_tree_intersect(MeshDeformBind *mdb, float
 
        if(meshdeform_intersect(mdb, &isec)) {
                len= isec.labda;
-               mface= isec.face;
+               mface=(MFace*)isec.hit.face;
 
                /* create MDefBoundIsect */
                isect= BLI_memarena_alloc(mdb->memarena, sizeof(*isect));
index 73afc3d1a5310081599b40451f014fb22f8cf518..b00500a321a48823a79a4f108ea15c579a951904 100644 (file)
@@ -162,6 +162,8 @@ typedef struct SceneRenderLayer {
 #define SCE_PASS_RADIO         8192 /* Radio removed, can use for new GI? */
 #define SCE_PASS_MIST          16384
 
+#define SCE_PASS_RAYHITS       32768
+
 /* note, srl->passflag is treestore element 'nr' in outliner, short still... */
 
 
@@ -238,6 +240,9 @@ typedef struct RenderData {
 
        /* render engine (deprecated), octree resolution */
        short renderer, ocres;
+       short raystructure;
+       short raytrace_tree_type;
+       short pad4[2];
 
        /**
         * What to do with the sky/background. Picks sky/premul/key
@@ -792,6 +797,15 @@ typedef struct Scene {
 #define R_INTERN       0
 #define R_YAFRAY       1
 
+/* raytrace structure */
+#define R_RAYSTRUCTURE_AUTO                            0
+#define R_RAYSTRUCTURE_OCTREE                  1
+#define R_RAYSTRUCTURE_BLIBVH                  2
+#define R_RAYSTRUCTURE_VBVH                            3
+#define R_RAYSTRUCTURE_SIMD_SVBVH              4       /* needs SIMD */
+#define R_RAYSTRUCTURE_SIMD_QBVH               5       /* needs SIMD */
+#define R_RAYSTRUCTURE_BIH                             6
+
 /* scemode (int now) */
 #define R_DOSEQ                                0x0001
 #define R_BG_RENDER                    0x0002
index 965796c6d5ba5b9f83dcaf5ea15c9571cb28730e..903859413569d1975b17513e6c5e602f85be7912 100644 (file)
@@ -1142,7 +1142,18 @@ static void rna_def_scene_render_data(BlenderRNA *brna)
                {256, "OCTREE_RES_256", 0, "256", ""},
                {512, "OCTREE_RES_512", 0, "512", ""},
                {0, NULL, 0, NULL, NULL}};
-               
+
+       static EnumPropertyItem raytrace_structure_items[] = {
+               {R_RAYSTRUCTURE_AUTO, "{R_RAYSTRUCTURE_AUTO", 0, "auto", ""},
+               {R_RAYSTRUCTURE_OCTREE, "R_RAYSTRUCTURE_OCTREE", 0, "octree", "Use old octree structure (no support for instances)"},
+               {R_RAYSTRUCTURE_BLIBVH, "R_RAYSTRUCTURE_BLIBVH", 0, "blibvh", "Use BLI_kdopbvh.c"},
+               {R_RAYSTRUCTURE_VBVH, "R_RAYSTRUCTURE_VBVH", 0, "vBVH", ""},
+               {R_RAYSTRUCTURE_SIMD_SVBVH, "R_RAYSTRUCTURE_SIMD_SVBVH", 0, "SIMD SVBVH", "Requires SIMD"},
+               {R_RAYSTRUCTURE_SIMD_QBVH, "R_RAYSTRUCTURE_SIMD_QBVH", 0, "SIMD QBVH", "Requires SIMD"},
+               {R_RAYSTRUCTURE_BIH, "R_RAYSTRUCTURE_BIH", 0, "BIH", ""},
+               {0, NULL, 0, NULL, NULL}
+               };
+
        static EnumPropertyItem fixed_oversample_items[] = {
                {5, "OVERSAMPLE_5", 0, "5", ""},
                {8, "OVERSAMPLE_8", 0, "8", ""},
@@ -1553,7 +1564,13 @@ static void rna_def_scene_render_data(BlenderRNA *brna)
        RNA_def_property_enum_items(prop, octree_resolution_items);
        RNA_def_property_ui_text(prop, "Octree Resolution", "Resolution of raytrace accelerator. Use higher resolutions for larger scenes.");
        RNA_def_property_update(prop, NC_SCENE|ND_RENDER_OPTIONS, NULL);
-       
+
+       prop= RNA_def_property(srna, "raytrace_structure", PROP_ENUM, PROP_NONE);
+       RNA_def_property_enum_sdna(prop, NULL, "raystructure");
+       RNA_def_property_enum_items(prop, raytrace_structure_items);
+       RNA_def_property_ui_text(prop, "Raytrace Acceleration Structure", "Type of raytrace accelerator structure.");
+       RNA_def_property_update(prop, NC_SCENE|ND_RENDER_OPTIONS, NULL);
+
        prop= RNA_def_property(srna, "antialiasing", PROP_BOOLEAN, PROP_NONE);
        RNA_def_property_boolean_sdna(prop, NULL, "mode", R_OSA);
        RNA_def_property_ui_text(prop, "Anti-Aliasing", "Render and combine multiple samples per pixel to prevent jagged edges.");
index db151775b966691edc4780eac2f767d13245a8bf..a15dada1bec3af4f68d9c0b4fc4e454a2a33898c 100644 (file)
@@ -1,8 +1,10 @@
 #!/usr/bin/python
 Import ('env')
 
-cflags=''
+cflags = ['-msse2','-mfpmath=sse']
+cxxflags = ['-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'
@@ -21,6 +23,7 @@ if env['WITH_BF_OPENEXR']:
     defs.append('WITH_OPENEXR')
 
 if env['OURPLATFORM']=='linux2':
-    cflags='-pthread'
+    cflags += ['-pthread']
 
 env.BlenderLib ( libname = 'bf_render', sources = sources, includes = Split(incs), defines=defs, libtype='core', priority=145, compileflags=cflags )
+env.BlenderLib ( libname = 'bf_render_raytrace', sources = raysources, includes = Split(incs), defines=defs, libtype='core', priority=145, compileflags=cflags, cxx_compileflags=cxxflags )
index 8f429f7dd906f9a0eae9be6b5dbf74f981e7f83d..af3ea8e2ac0973b06b1534b4283b3e1f5820ef29 100644 (file)
@@ -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. 
 #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)))
 
-#define RAY_OBJECT_GET(re, i) \
-       ((re)->objectinstance + ((i >= RE_RAY_TRANSFORM_OFFS)? i-RE_RAY_TRANSFORM_OFFS: i))
 
+/* 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;
+typedef struct RayCounter RayCounter;
 
-/* struct for intersection data */
-typedef struct Isect {
-       float start[3];                 /* start+vec = end, in ray_tree_intersect */
-       float vec[3];
-       float end[3];                   
+struct DerivedMesh;
+struct Mesh;
+
+int  RE_rayobject_raycast(RayObject *r, Isect *i);
+void RE_rayobject_add    (RayObject *r, RayObject *);
+void RE_rayobject_done(RayObject *r);
+void RE_rayobject_free(RayObject *r);
+
+/* 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);
+
+/* initializes an hint for optiming raycast where it is know that a ray will be contained inside the given cone*/
+/* void RE_rayobject_hint_cone(RayObject *r, RayHint *hint, float *); */
+
+/* RayObject constructors */
+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_bvh_create(int size);          /* raytrace/rayobject_bvh.c */
+RayObject* RE_rayobject_vbvh_create(int size);         /* raytrace/rayobject_vbvh.c */
+RayObject* RE_rayobject_qbvh_create(int size);         /* raytrace/rayobject_qbvh.c */
+RayObject* RE_rayobject_svbvh_create(int size);                /* raytrace/rayobject_svbvh.c */
+RayObject* RE_rayobject_bih_create(int size);          /* rayobject_bih.c */
+
+
+typedef struct LCTSHint LCTSHint;
+struct LCTSHint
+{
+       int size;
+       RayObject *stack[RE_RAY_LCTS_MAX_SIZE];
+};
 
-       float labda, u, v;              /* distance to hitpoint, uv weights */
+struct RayHint
+{
+       union
+       {
+               LCTSHint lcts;
+       } data;
+};
 
-       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;
 
+/* 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__*/
index 435e3ddc07fbbe8537256b3fc0c2997e2261d3ea..5660b37d01c388d4c52ae671ac2886ce0d548782 100644 (file)
@@ -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 */
@@ -178,6 +180,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 (file)
index 0000000..06579b3
--- /dev/null
@@ -0,0 +1,66 @@
+/**
+ * $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
+
+typedef struct RayCounter RayCounter;
+struct RayCounter
+{
+
+       struct
+       {
+               unsigned long long test, hit;
+               
+       } faces, bb, simd_bb, raycast, raytrace_hint, rayshadow_last_hit;
+};
+
+/* #define RE_RC_INIT(isec, shi) (isec).count = re_rc_counter+(shi).thread */
+#define RE_RC_INIT(isec, shi) (isec).raycounter = &((shi).raycounter)
+void RE_RC_INFO (RayCounter *rc);
+void RE_RC_MERGE(RayCounter *rc, RayCounter *tmp);
+#define RE_RC_COUNT(var) (var)++
+
+extern RayCounter re_rc_counter[];
+
+#else
+
+#      define RE_RC_INIT(isec,shi)
+#      define RE_RC_INFO(rc)
+#      define RE_RC_MERGE(dest,src)
+#      define  RE_RC_COUNT(var)
+               
+#endif
+
+
+#endif
diff --git a/source/blender/render/intern/include/rayobject.h b/source/blender/render/intern/include/rayobject.h
new file mode 100644 (file)
index 0000000..19608fb
--- /dev/null
@@ -0,0 +1,212 @@
+/**
+ * $Id$
+ *
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version. 
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2009 Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): André Pinto.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+#ifndef RE_RAYOBJECT_H
+#define RE_RAYOBJECT_H
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include "RE_raytrace.h"
+#include "render_types.h"
+#include <float.h>
+
+
+/* RayObject
+       
+       A ray object is everything where we can cast rays like:
+               * a face/triangle
+               * an octree
+               * a bvh tree
+               * an octree of bvh's
+               * a bvh of bvh's
+       
+               
+       All types of RayObjects can be created by implementing the
+       callbacks of the RayObject.
+
+       Due to high computing time evolved with casting on faces
+       there is a special type of RayObject (named RayFace)
+       which won't use callbacks like other generic nodes.
+       
+       In order to allow a mixture of RayFace+RayObjects,
+       all RayObjects must be 4byte aligned, allowing us to use the
+       2 least significant bits (with the mask 0x02) to define the
+       type of RayObject.
+       
+       This leads to 4 possible types of RayObject, but at the moment
+       only 2 are used:
+
+        addr&2  - type of object
+               0               Self (reserved for each structure)
+               1       RayFace
+               2               RayObject (generic with API callbacks)
+               3               RayObject_Vlak
+
+       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_unalignRayVlak(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_isRayVlak(o)      ((((intptr_t)o)&3) == 3)
+
+
+/*
+ * This ray object represents faces directly from a given VlakRen structure.
+ * Thus allowing to save memory, but making code dependant on render structures
+typedef struct RayVlak
+{
+       struct ObjectInstanceRen *ob;
+       struct VlakRen *face;
+} RayVlak;
+ */
+
+/*
+ * 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)
+/* Loads a VlakRen on a RayFace */
+void RE_rayface_from_vlak(RayFace *face, ObjectInstanceRen *obi, VlakRen *vlr);
+
+
+
+/*
+ * 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;
+};
+
+
+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);
+
+
+
+
+#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
index e50e498228d6ed82c735393afc7442698e09edf5..67c692592133e25840102a7bfd314814e893f837 100644 (file)
@@ -53,6 +53,8 @@ struct VlakTableNode;
 struct GHash;
 struct RenderBuckets;
 struct ObjectInstanceRen;
+struct RayObject;
+struct RayFace;
 
 #define TABLEINITSIZE 1024
 #define LAMPINITSIZE 256
@@ -168,7 +170,9 @@ struct Render
        ListBase parts;
        
        /* octree tables and variables for raytrace */
-       void *raytree;
+       struct RayObject *raytree;
+       struct RayFace *rayfaces;
+       float maxdist; /* needed for keeping an incorrect behaviour of SUN and HEMI lights (avoid breaking old scenes) */
 
        /* occlusion tree */
        void *occlusiontree;
@@ -281,6 +285,12 @@ 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 ObjectInstanceRen *rayobi;
+       
 } ObjectRen;
 
 typedef struct ObjectInstanceRen {
@@ -300,6 +310,10 @@ typedef struct ObjectInstanceRen {
        
        float *vectors;
        int totvector;
+       
+       /* used on makeraytree */
+       struct RayObject *raytree;
+
 } ObjectInstanceRen;
 
 /* ------------------------------------------------------------------------- */
@@ -425,7 +439,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;
@@ -536,8 +550,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];
 
index 4b28529a1472cbd1b23f4448a91ddea2d4be6620..250fbc000cbe74a2dde543ae7183e12e99831e66 100644 (file)
@@ -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 (file)
index 0000000..f0302dd
--- /dev/null
@@ -0,0 +1,393 @@
+/**
+ * $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>
+#include <xmmintrin.h>
+
+#ifndef RE_RAYTRACE_BVH_H
+#define RE_RAYTRACE_BVH_H
+
+inline int test_bb_group4(__m128 *bb_group, const Isect *isec)
+{
+       
+       const __m128 tmin0 = _mm_setzero_ps();
+       const __m128 tmax0 = _mm_load1_ps(&isec->labda);
+
+       const __m128 tmin1 = _mm_max_ps(tmin0, _mm_mul_ps( _mm_sub_ps( bb_group[isec->bv_index[0]], _mm_load1_ps(&isec->start[0]) ), _mm_load1_ps(&isec->idot_axis[0])) );
+       const __m128 tmax1 = _mm_min_ps(tmax0, _mm_mul_ps( _mm_sub_ps( bb_group[isec->bv_index[1]], _mm_load1_ps(&isec->start[0]) ), _mm_load1_ps(&isec->idot_axis[0])) );
+       const __m128 tmin2 = _mm_max_ps(tmin1, _mm_mul_ps( _mm_sub_ps( bb_group[isec->bv_index[2]], _mm_load1_ps(&isec->start[1]) ), _mm_load1_ps(&isec->idot_axis[1])) );
+       const __m128 tmax2 = _mm_min_ps(tmax1, _mm_mul_ps( _mm_sub_ps( bb_group[isec->bv_index[3]], _mm_load1_ps(&isec->start[1]) ), _mm_load1_ps(&isec->idot_axis[1])) );
+       const __m128 tmin3 = _mm_max_ps(tmin2, _mm_mul_ps( _mm_sub_ps( bb_group[isec->bv_index[4]], _mm_load1_ps(&isec->start[2]) ), _mm_load1_ps(&isec->idot_axis[2])) );
+       const __m128 tmax3 = _mm_min_ps(tmax2, _mm_mul_ps( _mm_sub_ps( bb_group[isec->bv_index[5]], _mm_load1_ps(&isec->start[2]) ), _mm_load1_ps(&isec->idot_axis[2])) );
+       
+       return _mm_movemask_ps(_mm_cmpge_ps(tmax3, tmin3));
+}
+
+
+/* bvh tree generics */
+template<class Tree> static int bvh_intersect(Tree *obj, Isect *isec);
+
+template<class Tree> static void bvh_add(Tree *obj, RayObject *ob)
+{
+       rtbuild_add( obj->builder, ob );
+}
+
+template<class Node>
+inline bool is_leaf(Node *node)
+{
+       return !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;
+}
+
+
+/*
+ * 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;
+}
+
+/*
+ * 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_bih.cpp b/source/blender/render/intern/raytrace/rayobject_bih.cpp
new file mode 100644 (file)
index 0000000..efbf706
--- /dev/null
@@ -0,0 +1,248 @@
+/**
+ * $Id$
+ *
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version. 
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2009 Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): André Pinto.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+#include <assert.h>
+#include <stdio.h>
+
+#include "MEM_guardedalloc.h"
+#include "BKE_utildefines.h"
+#include "BLI_arithb.h"
+#include "RE_raytrace.h"
+#include "rayobject_rtbuild.h"
+#include "rayobject.h"
+
+#define BIH_NCHILDS    4
+typedef struct BIHTree BIHTree;
+
+static int  bih_intersect(BIHTree *obj, Isect *isec);
+static void bih_add(BIHTree *o, RayObject *ob);
+static void bih_done(BIHTree *o);
+static void bih_free(BIHTree *o);
+static void bih_bb(BIHTree *o, float *min, float *max);
+
+static RayObjectAPI bih_api =
+{
+       (RE_rayobject_raycast_callback) bih_intersect,
+       (RE_rayobject_add_callback)     bih_add,
+       (RE_rayobject_done_callback)    bih_done,
+       (RE_rayobject_free_callback)    bih_free,
+       (RE_rayobject_merge_bb_callback)bih_bb
+};
+
+typedef struct BIHNode BIHNode;
+struct BIHNode
+{
+       BIHNode *child[BIH_NCHILDS];
+       float bi[BIH_NCHILDS][2];
+       int split_axis;
+};
+
+struct BIHTree
+{
+       RayObject rayobj;
+
+       BIHNode *root;
+
+       BIHNode *node_alloc, *node_next;
+       RTBuilder *builder;
+
+       float bb[2][3];
+};
+
+
+RayObject *RE_rayobject_bih_create(int size)
+{
+       BIHTree *obj= (BIHTree*)MEM_callocN(sizeof(BIHTree), "BIHTree");
+       assert( RE_rayobject_isAligned(obj) ); /* RayObject API assumes real data to be 4-byte aligned */       
+       
+       obj->rayobj.api = &bih_api;
+       obj->root = NULL;
+       
+       obj->node_alloc = obj->node_next = NULL;
+       obj->builder    = rtbuild_create( size );
+       
+       return RE_rayobject_unalignRayAPI((RayObject*) obj);
+}
+
+static void bih_free(BIHTree *obj)
+{
+       if(obj->builder)
+               rtbuild_free(obj->builder);
+
+       if(obj->node_alloc)
+               MEM_freeN(obj->node_alloc);
+
+       MEM_freeN(obj);
+}
+
+static void bih_bb(BIHTree *obj, float *min, float *max)
+{
+       DO_MIN(obj->bb[0], min);
+       DO_MAX(obj->bb[1], max);
+}
+
+/*
+ * Tree transverse
+ */
+static int dfs_raycast(const BIHNode *const node, Isect *isec, float tmin, float tmax)
+{
+       int i;
+       int hit = 0;
+
+       const int *const offset = isec->bv_index + node->split_axis*2;
+
+       //TODO diving heuristic
+       for(i=0; i<BIH_NCHILDS; i++)
+       {
+
+               float t1 = (node->bi[i][offset[0]] - isec->start[node->split_axis]) * isec->idot_axis[node->split_axis];
+               float t2 = (node->bi[i][offset[1]] - isec->start[node->split_axis]) * isec->idot_axis[node->split_axis];
+
+               if(t1 < tmin) t1 = tmin; //t1 = MAX2(t1, tmin);
+               if(t2 > tmax) t2 = tmax; //t2 = MIN2(t2, tmax);
+
+               if(t1 <= t2)
+               {
+                               if(RE_rayobject_isAligned(node->child[i]))
+                               {
+                                       if(node->child[i] == 0) break;
+                                       
+                                       hit |= dfs_raycast(node->child[i], isec, t1, t2);
+                                       if(hit && isec->mode == RE_RAY_SHADOW) return hit;
+                               }
+                               else
+                               {
+                                       hit |= RE_rayobject_intersect( (RayObject*)node->child[i], isec);
+                                       if(hit && isec->mode == RE_RAY_SHADOW) return hit;
+                               }
+
+                               if(tmax > isec->labda)
+                                       tmax = isec->labda;
+               }
+       }
+
+       return hit;
+}
+
+static int bih_intersect(BIHTree *obj, Isect *isec)
+{
+       if(RE_rayobject_isAligned(obj->root))
+               return dfs_raycast(obj->root, isec, 0, isec->labda);
+       else
+               return RE_rayobject_intersect( (RayObject*)obj->root, isec);
+}
+
+
+/*
+ * Builds a BIH tree from builder object
+ */
+static void bih_add(BIHTree *obj, RayObject *ob)
+{
+       rtbuild_add( obj->builder, ob );
+}
+
+static BIHNode *bih_new_node(BIHTree *tree, int nid)
+{
+       BIHNode *node = tree->node_alloc + nid - 1;
+       assert(RE_rayobject_isAligned(node));
+       if(node+1 > tree->node_next)
+               tree->node_next = node+1;
+               
+       return node;
+}
+
+static int child_id(int pid, int nchild)
+{
+       //N child of node A = A * K + (2 - K) + N, (0 <= N < K)
+       return pid*BIH_NCHILDS+(2-BIH_NCHILDS)+nchild;
+}
+
+static BIHNode *bih_rearrange(BIHTree *tree, RTBuilder *builder, int nid, float *bb)
+{
+       if(rtbuild_size(builder) == 1)
+       {
+               RayObject *child = rtbuild_get_primitive( builder, 0 );
+               assert(!RE_rayobject_isAligned(child));
+
+               INIT_MINMAX(bb, bb+3);
+               RE_rayobject_merge_bb( (RayObject*)child, bb, bb+3);
+
+               return (BIHNode*)child;
+       }
+       else
+       {
+               int i;
+               int nc = rtbuild_mean_split_largest_axis(builder, BIH_NCHILDS);
+               RTBuilder tmp;
+       
+               BIHNode *parent = bih_new_node(tree, nid);
+
+               INIT_MINMAX(bb, bb+3);
+               parent->split_axis = builder->split_axis;
+               for(i=0; i<nc; i++)
+               {
+                       float cbb[6];
+                       parent->child[i] = bih_rearrange( tree, rtbuild_get_child(builder, i, &tmp), child_id(nid,i), cbb );
+
+                       parent->bi[i][0] = cbb[parent->split_axis];
+                       parent->bi[i][1] = cbb[parent->split_axis+3];
+
+                       DO_MIN(cbb  , bb);
+                       DO_MAX(cbb+3, bb+3);
+               }
+               for(; i<BIH_NCHILDS; i++)
+               {
+                       parent->bi[i][0] =  1.0;
+                       parent->bi[i][1] = -1.0;
+                       parent->child[i] = 0;
+               }
+
+               return parent;
+       }
+}
+
+static void bih_done(BIHTree *obj)
+{
+       int needed_nodes;
+       assert(obj->root == NULL && obj->node_alloc == NULL && obj->builder);
+
+       //TODO exact calculate needed nodes
+       needed_nodes = (rtbuild_size(obj->builder)+1)*2;
+       assert(needed_nodes > 0);
+
+       obj->node_alloc = (BIHNode*)MEM_mallocN( sizeof(BIHNode)*needed_nodes, "BIHTree.Nodes");
+       obj->node_next  = obj->node_alloc;
+
+       obj->root = bih_rearrange( obj, obj->builder, 1, (float*)obj->bb );
+
+       rtbuild_free( obj->builder );
+       obj->builder = NULL;
+       
+       assert(obj->node_alloc+needed_nodes >= obj->node_next);
+}
+
diff --git a/source/blender/render/intern/raytrace/rayobject_bvh.cpp b/source/blender/render/intern/raytrace/rayobject_bvh.cpp
new file mode 100644 (file)
index 0000000..a7e96f6
--- /dev/null
@@ -0,0 +1,233 @@
+/**
+ * $Id$
+ *
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version. 
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2009 Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): André Pinto.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+#include <assert.h>
+
+#include "RE_raytrace.h"
+#include "rayobject_rtbuild.h"
+#include "rayobject.h"
+#include "MEM_guardedalloc.h"
+#include "BKE_utildefines.h"
+#include "BLI_arithb.h"
+#include "BLI_memarena.h"
+#include "bvh.h"
+
+#define BVH_NCHILDS 2
+#define RAY_BB_TEST_COST (0.2f)
+#define DFS_STACK_SIZE 64
+#define DYNAMIC_ALLOC
+
+//#define rtbuild_split        rtbuild_mean_split_largest_axis         /* objects mean split on the longest axis, childs BB are allowed to overlap */
+//#define rtbuild_split        rtbuild_median_split_largest_axis       /* space median split on the longest axis, childs BB are allowed to overlap */
+#define rtbuild_split  rtbuild_heuristic_object_split          /* split objects using heuristic */
+
+struct BVHNode
+{
+       BVHNode *child[BVH_NCHILDS];
+       float   bb[6];
+       int split_axis;
+};
+
+struct BVHTree
+{
+       RayObject rayobj;
+
+       BVHNode *root;
+
+       MemArena *node_arena;
+
+       float cost;
+       RTBuilder *builder;
+};
+
+/*
+ * Push nodes (used on dfs)
+ */
+template<class Node>
+inline static void bvh_node_push_childs(Node *node, Isect *isec, Node **stack, int &stack_pos)
+{
+       //push nodes in reverse visit order
+       if(isec->idot_axis[node->split_axis] < 0.0f)
+       {
+               int i;
+               for(i=0; i<BVH_NCHILDS; i++)
+                       if(node->child[i] == 0)
+                               break;
+                       else
+                               stack[stack_pos++] = node->child[i];
+       }
+       else
+       {
+               int i;  
+               for(i=BVH_NCHILDS-1; i>=0; i--)
+                       if(node->child[i] != 0)
+                               stack[stack_pos++] = node->child[i];
+       }
+}
+
+/*
+ * BVH done
+ */
+static BVHNode *bvh_new_node(BVHTree *tree, int nid)
+{
+       BVHNode *node = (BVHNode*)BLI_memarena_alloc(tree->node_arena, sizeof(BVHNode));
+       return node;
+}
+
+static int child_id(int pid, int nchild)
+{
+       //N child of node A = A * K + (2 - K) + N, (0 <= N < K)
+    return pid*BVH_NCHILDS+(2-BVH_NCHILDS)+nchild;
+}
+        
+
+static BVHNode *bvh_rearrange(BVHTree *tree, RTBuilder *builder, int nid, float *cost)
+{
+       *cost = 0;
+       if(rtbuild_size(builder) == 0)
+               return 0;
+
+       if(rtbuild_size(builder) == 1)
+       {
+               RayObject *child = rtbuild_get_primitive( builder, 0 );
+
+               if(RE_rayobject_isRayFace(child))
+               {
+                       int i;
+                       BVHNode *parent = bvh_new_node(tree, nid);
+                       parent->split_axis = 0;
+
+                       INIT_MINMAX(parent->bb, parent->bb+3);
+
+                       for(i=0; i<1; i++)
+                       {
+                               parent->child[i] = (BVHNode*)rtbuild_get_primitive( builder, i );
+                               bvh_node_merge_bb(parent->child[i], parent->bb, parent->bb+3);
+                       }
+                       for(; i<BVH_NCHILDS; i++)
+                               parent->child[i] = 0;
+
+                       *cost = RE_rayobject_cost(child)+RAY_BB_TEST_COST;
+                       return parent;
+               }
+               else
+               {
+                       assert(!RE_rayobject_isAligned(child));
+                       //Its a sub-raytrace structure, assume it has it own raycast
+                       //methods and adding a Bounding Box arround is unnecessary
+
+                       *cost = RE_rayobject_cost(child);
+                       return (BVHNode*)child;
+               }
+       }
+       else
+       {
+               int i;
+               RTBuilder tmp;
+               BVHNode *parent = bvh_new_node(tree, nid);
+               int nc = rtbuild_split(builder, BVH_NCHILDS); 
+
+
+               INIT_MINMAX(parent->bb, parent->bb+3);
+               parent->split_axis = builder->split_axis;
+               for(i=0; i<nc; i++)
+               {
+                       float cbb[6];
+                       float tcost;
+                       parent->child[i] = bvh_rearrange( tree, rtbuild_get_child(builder, i, &tmp), child_id(nid,i), &tcost );
+                       
+                       INIT_MINMAX(cbb, cbb+3);
+                       bvh_node_merge_bb(parent->child[i], cbb, cbb+3);
+                       DO_MIN(cbb,   parent->bb);
+                       DO_MAX(cbb+3, parent->bb+3);
+                       
+                       *cost += tcost*bb_area(cbb, cbb+3);
+               }
+               for(; i<BVH_NCHILDS; i++)
+                       parent->child[i] = 0;
+
+               *cost /= bb_area(parent->bb, parent->bb+3);
+               *cost += nc*RAY_BB_TEST_COST;
+               return parent;
+       }
+
+       assert(false);
+}
+
+template<>
+void bvh_done<BVHTree>(BVHTree *obj)
+{
+       int needed_nodes = (rtbuild_size(obj->builder)+1)*2;
+       if(needed_nodes > BLI_MEMARENA_STD_BUFSIZE)
+               needed_nodes = BLI_MEMARENA_STD_BUFSIZE;
+
+       obj->node_arena = BLI_memarena_new(needed_nodes);
+       BLI_memarena_use_malloc(obj->node_arena);
+
+       
+       obj->root = bvh_rearrange( obj, obj->builder, 1, &obj->cost );
+       
+       rtbuild_free( obj->builder );
+       obj->builder = NULL;
+}
+
+template<>
+int bvh_intersect<BVHTree>(BVHTree *obj, Isect* isec)
+{
+       if(RE_rayobject_isAligned(obj->root))
+               return bvh_node_stack_raycast<BVHNode,64,true>(obj->root, isec);
+       else
+               return RE_rayobject_intersect( (RayObject*) obj->root, isec );
+}
+
+
+/* the cast to pointer function is needed to workarround gcc bug: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11407 */
+static RayObjectAPI bvh_api =
+{
+       (RE_rayobject_raycast_callback) ((int(*)(BVHTree*,Isect*)) &bvh_intersect<BVHTree>),
+       (RE_rayobject_add_callback)     ((void(*)(BVHTree*,RayObject*)) &bvh_add<BVHTree>),
+       (RE_rayobject_done_callback)    ((void(*)(BVHTree*))       &bvh_done<BVHTree>),
+       (RE_rayobject_free_callback)    ((void(*)(BVHTree*))       &bvh_free<BVHTree>),
+       (RE_rayobject_merge_bb_callback)((void(*)(BVHTree*,float*,float*)) &bvh_bb<BVHTree>),
+       (RE_rayobject_cost_callback)    ((float(*)(BVHTree*))      &bvh_cost<BVHTree>)
+};
+
+
+RayObject *RE_rayobject_bvh_create(int size)
+{
+       BVHTree *obj= (BVHTree*)MEM_callocN(sizeof(BVHTree), "BVHTree");
+       assert( RE_rayobject_isAligned(obj) ); /* RayObject API assumes real data to be 4-byte aligned */       
+       
+       obj->rayobj.api = &bvh_api;
+       obj->root = NULL;
+       
+       obj->node_arena = NULL;
+       obj->builder    = rtbuild_create( size );
+       
+       return RE_rayobject_unalignRayAPI((RayObject*) obj);
+}
diff --git a/source/blender/render/intern/raytrace/rayobject_hint.h b/source/blender/render/intern/raytrace/rayobject_hint.h
new file mode 100644 (file)
index 0000000..d85465a
--- /dev/null
@@ -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 (file)
index 0000000..53579d2
--- /dev/null
@@ -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"
+
+#define DFS_STACK_SIZE 256
+
+struct QBVHTree
+{
+       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<QBVHTree>(QBVHTree *obj)
+{
+       rtbuild_done(obj->builder);
+       
+       //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).transform(obj->builder);     
+               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
+               OVBVHNode *root = BuildBinaryVBVH<OVBVHNode>(arena1).transform(obj->builder);                   
+               VBVH_optimalPackSIMD<OVBVHNode,PackCost>(PackCost()).transform(root);
+               obj->root = Reorganize_SVBVH<OVBVHNode>(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);
+}
diff --git a/source/blender/render/intern/raytrace/rayobject_rtbuild.cpp b/source/blender/render/intern/raytrace/rayobject_rtbuild.cpp
new file mode 100644 (file)
index 0000000..430045b
--- /dev/null
@@ -0,0 +1,493 @@
+/**
+ * $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)
+{
+       for(int i=0; i<3; i++)
+       if(b->sorted_begin[i])
+               object_sort( b->sorted_begin[i], b->sorted_end[i], i );
+}
+
+RayObject* rtbuild_get_primitive(RTBuilder *b, int index)
+{
+       return b->sorted_begin[0][index]->obj;
+}
+
+RTBuilder* rtbuild_get_child(RTBuilder *b, int child, RTBuilder *tmp)
+{
+       rtbuild_init( tmp );
+
+       for(int i=0; i<3; i++)
+               if(b->sorted_begin[i])
+               {
+                       tmp->sorted_begin[i] = b->sorted_begin[i] +  b->child_offset[child  ];
+                       tmp->sorted_end  [i] = b->sorted_begin[i] +  b->child_offset[child+1];
+               }
+               else
+               {
+                       tmp->sorted_begin[i] = 0;
+                       tmp->sorted_end  [i] = 0;
+               }
+       
+       return tmp;
+}
+
+void rtbuild_calc_bb(RTBuilder *b)
+{
+       if(b->bb[0] == 1.0e30f)
+       {
+               for(RTBuilder::Object **index = b->sorted_begin[0]; index != b->sorted_end[0]; index++)
+                       RE_rayobject_merge_bb( (*index)->obj , b->bb, b->bb+3);
+       }
+}
+
+void rtbuild_merge_bb(RTBuilder *b, float *min, float *max)
+{
+       rtbuild_calc_bb(b);
+       DO_MIN(b->bb, min);
+       DO_MAX(b->bb+3, max);
+}
+
+/*
+int rtbuild_get_largest_axis(RTBuilder *b)
+{
+       rtbuild_calc_bb(b);
+       return bb_largest_axis(b->bb, b->bb+3);
+}
+
+//Left balanced tree
+int rtbuild_mean_split(RTBuilder *b, int nchilds, int axis)
+{
+       int i;
+       int mleafs_per_child, Mleafs_per_child;
+       int tot_leafs  = rtbuild_size(b);
+       int missing_leafs;
+
+       long long s;
+
+       assert(nchilds <= RTBUILD_MAX_CHILDS);
+       
+       //TODO optimize calc of leafs_per_child
+       for(s=nchilds; s<tot_leafs; s*=nchilds);
+       Mleafs_per_child = s/nchilds;
+       mleafs_per_child = Mleafs_per_child/nchilds;
+       
+       //split min leafs per child     
+       b->child_offset[0] = 0;
+       for(i=1; i<=nchilds; i++)
+               b->child_offset[i] = mleafs_per_child;
+       
+       //split remaining leafs
+       missing_leafs = tot_leafs - mleafs_per_child*nchilds;
+       for(i=1; i<=nchilds; i++)
+       {
+               if(missing_leafs > Mleafs_per_child - mleafs_per_child)
+               {
+                       b->child_offset[i] += Mleafs_per_child - mleafs_per_child;
+                       missing_leafs -= Mleafs_per_child - mleafs_per_child;
+               }
+               else
+               {
+                       b->child_offset[i] += missing_leafs;
+                       missing_leafs = 0;
+                       break;
+               }
+       }
+       
+       //adjust for accumulative offsets
+       for(i=1; i<=nchilds; i++)
+               b->child_offset[i] += b->child_offset[i-1];
+
+       //Count created childs
+       for(i=nchilds; b->child_offset[i] == b->child_offset[i-1]; i--);
+       split_leafs(b, b->child_offset, i, axis);
+       
+       assert( b->child_offset[0] == 0 && b->child_offset[i] == tot_leafs );
+       return i;
+}
+       
+       
+int rtbuild_mean_split_largest_axis(RTBuilder *b, int nchilds)
+{
+       int axis = rtbuild_get_largest_axis(b);
+       return rtbuild_mean_split(b, nchilds, axis);
+}
+*/
+
+/*
+ * "separators" is an array of dim NCHILDS-1
+ * and indicates where to cut the childs
+ */
+/*
+int rtbuild_median_split(RTBuilder *b, float *separators, int nchilds, int axis)
+{
+       int size = rtbuild_size(b);
+               
+       assert(nchilds <= RTBUILD_MAX_CHILDS);
+       if(size <= nchilds)
+       {
+               return rtbuild_mean_split(b, nchilds, axis);
+       }
+       else
+       {
+               int i;
+
+               b->split_axis = axis;
+               
+               //Calculate child offsets
+               b->child_offset[0] = 0;
+               for(i=0; i<nchilds-1; i++)
+                       b->child_offset[i+1] = split_leafs_by_plane(b, b->child_offset[i], size, separators[i]);
+               b->child_offset[nchilds] = size;
+               
+               for(i=0; i<nchilds; i++)
+                       if(b->child_offset[i+1] - b->child_offset[i] == size)
+                               return rtbuild_mean_split(b, nchilds, axis);
+               
+               return nchilds;
+       }       
+}
+
+int rtbuild_median_split_largest_axis(RTBuilder *b, int nchilds)
+{
+       int la, i;
+       float separators[RTBUILD_MAX_CHILDS];
+       
+       rtbuild_calc_bb(b);
+
+       la = bb_largest_axis(b->bb,b->bb+3);
+       for(i=1; i<nchilds; i++)
+               separators[i-1] = (b->bb[la+3]-b->bb[la])*i / nchilds;
+               
+       return rtbuild_median_split(b, separators, nchilds, la);
+}
+*/
+
+//Heuristics Object Splitter
+
+
+struct SweepCost
+{
+       float bb[6];
+       float cost;
+};
+
+/* Object Surface Area Heuristic splitter */
+int rtbuild_heuristic_object_split(RTBuilder *b, int nchilds)
+{
+       int size = rtbuild_size(b);             
+       assert(nchilds == 2);
+       assert(size > 1);
+       int baxis = -1, boffset = 0;
+
+       if(size > nchilds)
+       {
+               float bcost = FLT_MAX;
+               baxis = -1, boffset = size/2;
+
+               SweepCost *sweep = (SweepCost*)MEM_mallocN( sizeof(SweepCost)*size, "RTBuilder.HeuristicSweep" );
+               
+               for(int axis=0; axis<3; axis++)
+               {
+                       SweepCost sweep_left;
+
+                       RTBuilder::Object **obj = b->sorted_begin[axis];
+                       
+//                     float right_cost = 0;
+                       for(int i=size-1; i>=0; i--)
+                       {
+                               if(i == size-1)
+                               {
+                                       VECCOPY(sweep[i].bb, obj[i]->bb);
+                                       VECCOPY(sweep[i].bb+3, obj[i]->bb+3);
+                                       sweep[i].cost = obj[i]->cost;
+                               }
+                               else
+                               {
+                                       sweep[i].bb[0] = MIN2(obj[i]->bb[0], sweep[i+1].bb[0]);
+                                       sweep[i].bb[1] = MIN2(obj[i]->bb[1], sweep[i+1].bb[1]);
+                                       sweep[i].bb[2] = MIN2(obj[i]->bb[2], sweep[i+1].bb[2]);                                 
+                                       sweep[i].bb[3] = MAX2(obj[i]->bb[3], sweep[i+1].bb[3]);
+                                       sweep[i].bb[4] = MAX2(obj[i]->bb[4], sweep[i+1].bb[4]);
+                                       sweep[i].bb[5] = MAX2(obj[i]->bb[5], sweep[i+1].bb[5]);
+                                       sweep[i].cost  = obj[i]->cost + sweep[i+1].cost;
+                               }
+//                             right_cost += obj[i]->cost;
+                       }
+                       
+                       sweep_left.bb[0] = obj[0]->bb[0];
+                       sweep_left.bb[1] = obj[0]->bb[1];
+                       sweep_left.bb[2] = obj[0]->bb[2];
+                       sweep_left.bb[3] = obj[0]->bb[3];
+                       sweep_left.bb[4] = obj[0]->bb[4];
+                       sweep_left.bb[5] = obj[0]->bb[5];
+                       sweep_left.cost  = obj[0]->cost;
+                       
+//                     right_cost -= obj[0]->cost;     if(right_cost < 0) right_cost = 0;
+
+                       for(int i=1; i<size; i++)
+                       {
+                               //Worst case heuristic (cost of each child is linear)
+                               float hcost, left_side, right_side;
+                               
+                               left_side = bb_area(sweep_left.bb, sweep_left.bb+3)*(sweep_left.cost+logf(i));
+                               right_side= bb_area(sweep[i].bb, sweep[i].bb+3)*(sweep[i].cost+logf(size-i));
+                               hcost = left_side+right_side;
+
+                               assert(left_side >= 0);
+                               assert(right_side >= 0);
+                               
+                               if(left_side > bcost) break;    //No way we can find a better heuristic in this axis
+
+                               assert(hcost >= 0);
+                               if( hcost < bcost
+                               || (hcost == bcost && axis < baxis)) //this makes sure the tree built is the same whatever is the order of the sorting axis
+                               {
+                                       bcost = hcost;
+                                       baxis = axis;
+                                       boffset = i;
+                               }
+                               DO_MIN( obj[i]->bb,   sweep_left.bb   );
+                               DO_MAX( obj[i]->bb+3, sweep_left.bb+3 );
+
+                               sweep_left.cost += obj[i]->cost;
+//                             right_cost -= obj[i]->cost; if(right_cost < 0) right_cost = 0;
+                       }
+                       
+                       assert(baxis >= 0 && baxis < 3);
+               }
+                       
+               
+               MEM_freeN(sweep);
+       }
+       else if(size == 2)
+       {
+               baxis = 0;
+               boffset = 1;
+       }
+       else if(size == 1)
+       {
+               b->child_offset[0] = 0;
+               b->child_offset[1] = 1;
+               return 1;
+       }
+               
+       b->child_offset[0] = 0;
+       b->child_offset[1] = boffset;
+       b->child_offset[2] = size;
+       
+
+       /* Adjust sorted arrays for childs */
+       for(int i=0; i<boffset; i++) b->sorted_begin[baxis][i]->selected = true;
+       for(int i=boffset; i<size; i++) b->sorted_begin[baxis][i]->selected = false;
+       for(int i=0; i<3; i++)
+               std::stable_partition( b->sorted_begin[i], b->sorted_end[i], selected_node );
+
+       return nchilds;         
+}
+
+/*
+ * Helper code
+ * PARTITION code / used on mean-split
+ * basicly this a std::nth_element (like on C++ STL algorithm)
+ */
+/*
+static void split_leafs(RTBuilder *b, int *nth, int partitions, int split_axis)
+{
+       int i;
+       b->split_axis = split_axis;
+
+       for(i=0; i < partitions-1; i++)
+       {
+               assert(nth[i] < nth[i+1] && nth[i+1] < nth[partitions]);
+
+               if(split_axis == 0)     std::nth_element(b, nth[i],  nth[i+1], nth[partitions], obj_bb_compare<RTBuilder::Object,0>);
+               if(split_axis == 1)     std::nth_element(b, nth[i],  nth[i+1], nth[partitions], obj_bb_compare<RTBuilder::Object,1>);
+               if(split_axis == 2)     std::nth_element(b, nth[i],  nth[i+1], nth[partitions], obj_bb_compare<RTBuilder::Object,2>);
+       }
+}
+*/
+
+/*
+ * Bounding Box utils
+ */
+float bb_volume(float *min, float *max)
+{
+       return (max[0]-min[0])*(max[1]-min[1])*(max[2]-min[2]);
+}
+
+float bb_area(float *min, float *max)
+{
+       float sub[3], a;
+       sub[0] = max[0]-min[0];
+       sub[1] = max[1]-min[1];
+       sub[2] = max[2]-min[2];
+
+       a = (sub[0]*sub[1] + sub[0]*sub[2] + sub[1]*sub[2])*2;
+       assert(a >= 0.0);
+       return a;
+}
+
+int bb_largest_axis(float *min, float *max)
+{
+       float sub[3];
+       
+       sub[0] = max[0]-min[0];
+       sub[1] = max[1]-min[1];
+       sub[2] = max[2]-min[2];
+       if(sub[0] > sub[1])
+       {
+               if(sub[0] > sub[2])
+                       return 0;
+               else
+                       return 2;
+       }
+       else
+       {
+               if(sub[1] > sub[2])
+                       return 1;
+               else
+                       return 2;
+       }       
+}
+
+int bb_fits_inside(float *outer_min, float *outer_max, float *inner_min, float *inner_max)
+{
+       int i;
+       for(i=0; i<3; i++)
+               if(outer_min[i] > inner_min[i]) return 0;
+
+       for(i=0; i<3; i++)
+               if(outer_max[i] < inner_max[i]) return 0;
+
+       return 1;       
+}
diff --git a/source/blender/render/intern/raytrace/rayobject_rtbuild.h b/source/blender/render/intern/raytrace/rayobject_rtbuild.h
new file mode 100644 (file)
index 0000000..8f471f0
--- /dev/null
@@ -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);
+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 (file)
index 0000000..1bcffdd
--- /dev/null
@@ -0,0 +1,134 @@
+/**
+ * $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"
+
+#define DFS_STACK_SIZE 256
+
+struct SVBVHTree
+{
+       RayObject rayobj;
+
+       SVBVHNode *root;
+       MemArena *node_arena;
+
+       float cost;
+       RTBuilder *builder;
+};
+
+
+template<>
+void bvh_done<SVBVHTree>(SVBVHTree *obj)
+{
+       rtbuild_done(obj->builder);
+       
+       //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
+       VBVHNode *root = BuildBinaryVBVH<VBVHNode>(arena1).transform(obj->builder);
+       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);
+
+       
+       //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);
+}
diff --git a/source/blender/render/intern/raytrace/rayobject_vbvh.cpp b/source/blender/render/intern/raytrace/rayobject_vbvh.cpp
new file mode 100644 (file)
index 0000000..4e51de0
--- /dev/null
@@ -0,0 +1,158 @@
+/**
+ * $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;
+};
+
+
+template<>
+void bvh_done<VBVHTree>(VBVHTree *obj)
+{
+       rtbuild_done(obj->builder);
+       
+       //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
+       VBVHNode *root = BuildBinaryVBVH<VBVHNode>(arena1).transform(obj->builder);
+
+       reorganize(root);
+       remove_useless(root, &root);
+       bvh_refit(root);
+       
+       pushup(root);
+       pushdown(root);
+
+       //Cleanup
+       rtbuild_free( obj->builder );
+       obj->builder = NULL;
+
+       obj->node_arena = arena1;
+       obj->root = root;
+       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 (file)
index 0000000..f0335b7
--- /dev/null
@@ -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 (file)
index 0000000..840ccc2
--- /dev/null
@@ -0,0 +1,245 @@
+/**
+ * $Id$
+ *
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version. 
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2009 Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): André Pinto.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+#ifndef RE_RAYTRACE_SVBVH_H
+#define RE_RAYTRACE_SVBVH_H
+
+#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
diff --git a/source/blender/render/intern/raytrace/vbvh.h b/source/blender/render/intern/raytrace/vbvh.h
new file mode 100644 (file)
index 0000000..db1df43
--- /dev/null
@@ -0,0 +1,215 @@
+/**
+ * $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;
+
+       BuildBinaryVBVH(MemArena *a)
+       {
+               arena = a;
+       }
+
+       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)
+       {
+               
+               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
+               {
+                       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
index a6b089c60291500fcc14d6b2913fe0c78ea8bc8f..b417e07577cbc3f0d2106c1ddc72728ea1b86ad2 100644 (file)
@@ -350,6 +350,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";
 }
 
@@ -401,6 +408,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;
 }
 
@@ -528,7 +537,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;
@@ -572,6 +581,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.c b/source/blender/render/intern/source/rayobject.c
new file mode 100644 (file)
index 0000000..4bd8a12
--- /dev/null
@@ -0,0 +1,471 @@
+/**
+ * $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 "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;
+}
+
+#include "DNA_material_types.h"
+static 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 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;
+}
+
+/* ray - triangle or quad intersection */
+/* this function shall only modify Isect if it detects an hit */
+static int intersect_rayface(RayFace *face, Isect *is)
+{
+       float co1[3],co2[3],co3[3],co4[3];
+       float x0,x1,x2,t00,t01,t02,t10,t11,t12,t20,t21,t22,r0,r1,r2;
+       float m0, m1, m2, divdet, det1;
+       float labda, u, v;
+       short ok=0;
+       
+       if(is->orig.ob == face->ob && is->orig.face == face->face)
+               return 0;
+               
+       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;
+       }
+
+       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 = is->orig.face;
+                               VlakRen * b = face->face;
+
+                               /* so there's a shared edge or vertex, let's intersect ray with face
+                               itself, if that's true we can safely return 1, otherwise we assume
+                               the intersection is invalid, 0 */
+                               if(a->v1==b->v1 || a->v2==b->v1 || a->v3==b->v1 || a->v4==b->v1
+                               || a->v1==b->v2 || a->v2==b->v2 || a->v3==b->v2 || a->v4==b->v2
+                               || a->v1==b->v3 || a->v2==b->v3 || a->v3==b->v3 || a->v4==b->v3
+                               || (b->v4 && (a->v1==b->v4 || a->v2==b->v4 || a->v3==b->v4 || a->v4==b->v4)))
+                               if(!intersection2((VlakRen*)a, -r0, -r1, -r2, is->start[0], is->start[1], is->start[2]))
+                               {
+                                       return 0;
+                               }
+                       }
+               }
+
+               RE_RC_COUNT(is->raycounter->faces.hit);
+
+               is->isect= ok;  // wich half of the quad
+               is->labda= labda;
+               is->u= u; is->v= v;
+
+               is->hit.ob   = face->ob;
+               is->hit.face = face->face;
+#ifdef RT_USE_LAST_HIT
+               is->last_hit = (RayObject*) RE_rayobject_unalignRayFace(face);
+#endif
+               return 1;
+       }
+
+       return 0;
+}
+
+void RE_rayface_from_vlak(RayFace *face, ObjectInstanceRen *obi, VlakRen *vlr)
+{
+       VECCOPY(face->v1, vlr->v1->co);
+       VECCOPY(face->v2, vlr->v2->co);
+       VECCOPY(face->v3, vlr->v3->co);
+       if(vlr->v4)
+       {
+               VECCOPY(face->v4, vlr->v4->co);
+               face->quad = 1;
+       }
+       else
+       {
+               face->quad = 0;
+       }
+
+       face->ob   = obi;
+       face->face = vlr;
+}
+
+
+int RE_rayobject_raycast(RayObject *r, Isect *isec)
+{
+       int i;
+       RE_RC_COUNT(isec->raycounter->raycast.test);
+
+       /* Setup vars used on raycast */
+       isec->labda *= Normalize(isec->vec);
+       isec->dist = VecLength(isec->vec);
+       
+       for(i=0; i<3; i++)
+       {
+               isec->idot_axis[i]              = 1.0f / isec->vec[i];
+               
+               isec->bv_index[2*i]             = isec->idot_axis[i] < 0.0 ? 1 : 0;
+               isec->bv_index[2*i+1]   = 1 - isec->bv_index[2*i];
+               
+               isec->bv_index[2*i]             = i+3*isec->bv_index[2*i];
+               isec->bv_index[2*i+1]   = i+3*isec->bv_index[2*i+1];
+       }
+
+#ifdef RT_USE_LAST_HIT 
+       /* Last hit heuristic */
+       if(isec->mode==RE_RAY_SHADOW && isec->last_hit)
+       {
+               RE_RC_COUNT(isec->raycounter->rayshadow_last_hit.test);
+               
+               if(RE_rayobject_intersect(isec->last_hit, isec))
+               {
+                       RE_RC_COUNT(isec->raycounter->raycast.hit);
+                       RE_RC_COUNT(isec->raycounter->rayshadow_last_hit.hit);
+                       return 1;
+               }
+       }
+#endif
+
+#ifdef RT_USE_HINT
+       isec->hit_hint = 0;
+#endif
+
+       if(RE_rayobject_intersect(r, isec))
+       {
+               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( (RayFace*) RE_rayobject_align(r), 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_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))
+       {
+               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))
+       {
+               return;
+       }
+       else if(RE_rayobject_isRayAPI(r))
+       {
+               r = RE_rayobject_align( r );
+               return r->api->hint_bb( r, hint, min, max );
+       }
+       else assert(0);
+}
+
diff --git a/source/blender/render/intern/source/rayobject_blibvh.c b/source/blender/render/intern/source/rayobject_blibvh.c
new file mode 100644 (file)
index 0000000..6e78986
--- /dev/null
@@ -0,0 +1,140 @@
+/**
+ * $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 RayObjectAPI bvh_api =
+{
+       RE_rayobject_blibvh_intersect,
+       RE_rayobject_blibvh_add,
+       RE_rayobject_blibvh_done,
+       RE_rayobject_blibvh_free,
+       RE_rayobject_blibvh_bb
+};
+
+typedef struct BVHObject
+{
+       RayObject rayobj;
+       BVHTree *bvh;
+       float bb[2][3];
+
+} BVHObject;
+
+
+RayObject *RE_rayobject_blibvh_create(int size)
+{
+       BVHObject *obj= (BVHObject*)MEM_callocN(sizeof(BVHObject), "BVHObject");
+       assert( 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);
+       
+       INIT_MINMAX(obj->bb[0], obj->bb[1]);
+       return RE_rayobject_unalignRayAPI((RayObject*) obj);
+}
+
+static void bvh_callback(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
+{
+       Isect *isec = (Isect*)userdata;
+       RayObject *face = (RayObject*)index;
+       
+       if(RE_rayobject_intersect(face,isec))
+       {
+               hit->index = index;
+
+               if(isec->mode == RE_RAY_SHADOW)
+                       hit->dist = 0;
+               else
+                       hit->dist = isec->labda*isec->dist;
+       }
+}
+
+static int  RE_rayobject_blibvh_intersect(RayObject *o, Isect *isec)
+{
+       BVHObject *obj = (BVHObject*)o;
+       BVHTreeRayHit hit;
+       float dir[3];
+
+       VECCOPY(dir, isec->vec);
+       Normalize(dir);
+
+       hit.index = 0;
+       hit.dist = isec->labda*isec->dist;
+       
+       return BLI_bvhtree_ray_cast(obj->bvh, isec->start, dir, 0.0, &hit, bvh_callback, isec);
+}
+
+static void 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, (int)ob, min_max, 2 );     
+}
+
+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);
+
+       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 (file)
index 0000000..9329d11
--- /dev/null
@@ -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);
+       }
+}
similarity index 59%
rename from source/blender/render/intern/source/raytrace.c
rename to source/blender/render/intern/source/rayobject_octree.c
index b34fe6a70397cdb0da79e677299099ece188be49..4246dd522db19288858cda8465add61f1c9059d7 100644 (file)
@@ -32,6 +32,7 @@
 #include <string.h>
 #include <stdlib.h>
 #include <float.h>
+#include <assert.h>
 
 #include "MEM_guardedalloc.h"
 
 
 #include "BLI_arithb.h"
 
-#include "RE_raytrace.h"
+#include "rayobject.h"
 
 /* ********** structs *************** */
-
 #define BRANCH_ARRAY 1024
 #define NODE_ARRAY 4096
 
@@ -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,29 @@ 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;
-} Octree;
 
-/* ******** globals ***************** */
+       /* during building only */
+       char *ocface; 
+       
+       RayFace **ro_nodes;
+       int ro_nodes_size, ro_nodes_used;
+       
+} Octree;
 
-/* just for statistics */
-static int raycount;
-static int accepted, rejected, coherent_ray;
+static int  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);
 
+static RayObjectAPI octree_api =
+{
+       RE_rayobject_octree_intersect,
+       RE_rayobject_octree_add,
+       RE_rayobject_octree_done,
+       RE_rayobject_octree_free,
+       RE_rayobject_octree_bb
+};
 
 /* **************** ocval method ******************* */
 /* within one octree node, a set of 3x15 bits defines a 'boundbox' to OR with */
@@ -233,7 +244,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 +294,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 +384,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 +406,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 +446,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 +489,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, v1);
-       VECCOPY(co2, v2);
-       VECCOPY(co3, v3);
-       if(v4)
-               VECCOPY(co4, v4);
+       VECCOPY(co1, face->v1);
+       VECCOPY(co2, face->v2);
+       VECCOPY(co3, face->v3);
+       if(face->v4)
+               VECCOPY(co4, face->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 +502,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 +512,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 +526,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 +536,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 +550,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 +565,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 +591,107 @@ void RE_ray_tree_add_face(RayTree *tree, int ob, RayFace *face)
        }
 }
 
-void RE_ray_tree_done(RayTree *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)
+static void RE_rayobject_octree_done(RayObject *tree)
 {
-       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;
                        
-                       nr++;
-                       if(nr==8) {
-                               no= no->next;
-                               if(no==0) return 0;
-                               nr=0;
+                       if(!face) break;
+                       
+                       if( (ov->ocx & ocval.ocx) && (ov->ocy & ocval.ocy) && (ov->ocz & ocval.ocz) )
+                       {
+                               if( RE_rayobject_intersect( 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;
+                       
+                       if(!face) break;
                        
-                       nr++;
-                       if(nr==8) {
-                               no= no->next;
-                               if(no==NULL) break;
-                               nr=0;
+                       if( (ov->ocx & ocval.ocx) && (ov->ocy & ocval.ocy) && (ov->ocz & ocval.ocz) )
+                       { 
+                               if( RE_rayobject_intersect( RE_rayobject_unalignRayFace(face),is) )
+                                       found= 1;
                        }
-                       face= no->v[nr];
-                       ob= no->ob[nr];
                }
                
                return found;
@@ -1175,23 +815,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 +834,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 +882,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 +895,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 +903,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 +981,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 +1058,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 (file)
index 0000000..a82a213
--- /dev/null
@@ -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
index d2599f6050c18caac6576823c84cbb5751a00124..8cb11d11762166a22c919a84f35a472918f67437 100644 (file)
@@ -29,6 +29,7 @@
 #include <string.h>
 #include <stdlib.h>
 #include <float.h>
+#include <assert.h>
 
 #include "MEM_guardedalloc.h"
 
@@ -57,6 +58,8 @@
 #include "volumetric.h"
 
 #include "RE_raytrace.h"
+#include "rayobject.h"
+#include "raycounter.h"
 
 #define RAY_TRA                1
 #define RAY_TRAFLIP    2
 /* 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)
+RayObject *  RE_rayobject_create(int type, int size)
 {
-       VlakRen *vlr= (VlakRen*)face;
+       if(type == R_RAYSTRUCTURE_AUTO)
+       {
+               //TODO
+//             if(detect_simd())
+//                     type = R_RAYSTRUCTURE_SIMD_SVBVH;
+//             else
+//                     type = R_RAYSTRUCTURE_VBVH;
 
-       *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;
+                       type = R_RAYSTRUCTURE_SIMD_QBVH;
+       }
+       
+       
+       if(type == R_RAYSTRUCTURE_OCTREE)
+       {
+               //TODO dynamic ocres
+               return RE_rayobject_octree_create(R.r.ocres, size);
+       }
+       if(type == R_RAYSTRUCTURE_BLIBVH)
+       {
+               return RE_rayobject_blibvh_create(size);
+       }
+       if(type == R_RAYSTRUCTURE_VBVH)
+       {
+               return RE_rayobject_vbvh_create(size);
+       }
+       if(type == R_RAYSTRUCTURE_SIMD_SVBVH)
+       {
+               return RE_rayobject_svbvh_create(size);
+       }
+       if(type == R_RAYSTRUCTURE_SIMD_QBVH)
+       {
+               return RE_rayobject_qbvh_create(size);
+       }
+       if(type == R_RAYSTRUCTURE_BIH)
+       {
+//             return RE_rayobject_bih_create(size);
+       }
+       
+       return NULL;
 }
 
-static int vlr_check_intersect(Isect *is, int ob, RayFace *face)
-{
-       ObjectInstanceRen *obi= RAY_OBJECT_GET((Render*)is->userdata, ob);
-       VlakRen *vlr = (VlakRen*)face;
+#ifdef RE_RAYCOUNTER
+RayCounter re_rc_counter[BLENDER_MAX_THREADS] = {};
+#endif
 
-       /* 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);
+void freeraytree(Render *re)
+{
+       ObjectInstanceRen *obi;
+       
+       if(re->raytree)
+       {
+               RE_rayobject_free(re->raytree);
+               re->raytree = NULL;
+       }
+       if(re->rayfaces)
+       {
+               MEM_freeN(re->rayfaces);
+               re->rayfaces = 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
 }
 
-static int vlr_check_intersect_solid(Isect *is, int ob, RayFace *face)
+static int is_raytraceable_vlr(Render *re, VlakRen *vlr)
 {
-       VlakRen *vlr = (VlakRen*)face;
-
-       /* solid material types only */
-       if (vlr->mat->material_type == MA_TYPE_SURFACE)
+       if((re->flag & R_BAKE_TRACE) || (vlr->mat->mode & MA_TRACEBLE))
+       if(vlr->mat->material_type != MA_TYPE_WIRE)
                return 1;
-       else
-               return 0;
+       return 0;
 }
 
-static float *vlr_get_transform(void *userdata, int i)
+static int is_raytraceable(Render *re, ObjectInstanceRen *obi)
 {
-       ObjectInstanceRen *obi= RAY_OBJECT_GET((Render*)userdata, i);
+       int v;
+       ObjectRen *obr = obi->obr;
 
-       return (obi->flag & R_TRANSFORMED)? (float*)obi->mat: NULL;
-}
+       if(re->excludeob && obr->ob == re->excludeob)
+               return 0;
 
-void freeraytree(Render *re)
-{
-       if(re->raytree) {
-               RE_ray_tree_free(re->raytree);
-               re->raytree= NULL;
+       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;
 }
 
-void makeraytree(Render *re)
-{
-       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;
-
-       INIT_MINMAX(min, max);
-
-       /* 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);
-                                       }
-
-                                       DO_MINMAX(co1, min, max);
-                                       DO_MINMAX(co2, min, max);
-                                       DO_MINMAX(co3, min, max);
 
-                                       if(vlr->v4) {
-                                               VECCOPY(co4, vlr->v4->co);
-                                               if(obi->flag & R_TRANSFORMED)
-                                                       Mat4MulVecfl(obi->mat, co4);
-                                               DO_MINMAX(co4, min, max);
-                                       }
+RayObject* makeraytree_object(Render *re, ObjectInstanceRen *obi)
+{
+       //TODO
+       // out-of-memory safeproof
+       // break render
+       // update render stats
+       ObjectRen *obr = obi->obr;
+       
+       if(obr->raytree == NULL)
+       {
+               RayObject *raytree;
+               RayFace *face;
+               int v;
+               
+               //Count faces
+               int faces = 0;
+               for(v=0;v<obr->totvlak;v++)
+               {
+                       VlakRen *vlr = obr->vlaknodes[v>>8].vlak + (v&255);
+                       if(is_raytraceable_vlr(re, vlr))
+                               faces++;
+               }
+               assert( faces > 0 );
 
-                                       totface++;
-                               }
+               //Create Ray cast accelaration structure                
+               raytree = obr->raytree = RE_rayobject_create( re->r.raytrace_tree_type, faces );
+               face = obr->rayfaces = (RayFace*)MEM_callocN(faces*sizeof(RayFace), "ObjectRen faces");
+               obr->rayobi = obi;
+               
+               for(v=0;v<obr->totvlak;v++)
+               {
+                       VlakRen *vlr = obr->vlaknodes[v>>8].vlak + (v&255);
+                       if(is_raytraceable_vlr(re, vlr))
+                       {
+                               RE_rayface_from_vlak( face, obi, vlr );                         
+                               RE_rayobject_add( raytree, 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 = RE_rayobject_instance_create( obr->raytree, obi->mat, obi, obi->obr->rayobi );
        }
+       
+       if(obi->raytree) return obi->raytree;
+       return obi->obr->raytree;
+}
 
-       for(obi=re->instancetable.first; obi; obi=obi->next) {
-               obr= obi->obr;
+static int has_special_rayobject(Render *re, ObjectInstanceRen *obi)
+{
+       if( (obi->flag & R_TRANSFORMED) )
+       {
+               ObjectRen *obr = obi->obr;
+               int v, faces = 0;
+               
+               for(v=0;v<obr->totvlak;v++)
+               {
+                       VlakRen *vlr = obr->vlaknodes[v>>8].vlak + (v&255);
+                       if(is_raytraceable_vlr(re, vlr))
+                       {
+                               faces++;
+                               if(faces > 4)
+                                       return 1;
+                       }
+               }
+       }
+       return 0;
+}
+/*
+ * create a single raytrace structure with all faces
+ */
+static void makeraytree_single(Render *re)
+{
+       ObjectInstanceRen *obi;
+       RayObject *raytree;
+       RayFace *face;
+       int faces = 0, obs = 0;
 
-               if(re->excludeob && obr->ob == re->excludeob)
-                       continue;
+       for(obi=re->instancetable.first; obi; obi=obi->next)
+       if(is_raytraceable(re, obi))
+       {
+               int v;
+               ObjectRen *obr = obi->obr;
+               obs++;
+               
+               if(has_special_rayobject(re, obi))
+               {
+                       faces++;
+               }
+               else
+               {
+                       for(v=0;v<obr->totvlak;v++)
+                       {
+                               VlakRen *vlr = obr->vlaknodes[v>>8].vlak + (v&255);
+                               if(is_raytraceable_vlr(re, vlr))
+                                       faces++;
+                       }
+               }
+       }
+       
+       //Create raytree
+       raytree = re->raytree = RE_rayobject_create( re->r.raytrace_tree_type, faces );
 
-               for(v=0; v<obr->totvlak; v++, totv++) {
-                       if((v & 255)==0) {
-                               double time= PIL_check_seconds_timer();
+       face    = re->rayfaces  = (RayFace*)MEM_callocN(faces*sizeof(RayFace), "Render ray faces");
+       
+       for(obi=re->instancetable.first; obi; obi=obi->next)
+       if(is_raytraceable(re, obi))
+       {
+               if(has_special_rayobject(re, obi))
+               {
+                       RayObject *obj = makeraytree_object(re, obi);
+                       RE_rayobject_add( re->raytree, obj );
+               }
+               else
+               {
+                       int v;
+                       ObjectRen *obr = obi->obr;
+
+                       for(v=0;v<obr->totvlak;v++)
+                       {
+                               VlakRen *vlr = obr->vlaknodes[v>>8].vlak + (v&255);
+                               if(is_raytraceable_vlr(re, vlr))
+                               {
+                                       RE_rayface_from_vlak(face, obi, vlr);
+                                       if((obi->flag & R_TRANSFORMED))
+                                       {
+                                               Mat4MulVecfl(obi->mat, face->v1);
+                                               Mat4MulVecfl(obi->mat, face->v2);
+                                               Mat4MulVecfl(obi->mat, face->v3);
+                                               if(RE_rayface_isQuad(face))
+                                                       Mat4MulVecfl(obi->mat, face->v4);
+                                       }
 
-                               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;
+                                       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);
                }
        }
+       RE_rayobject_done( raytree );   
+}
 
-       RE_ray_tree_done(re->raytree);
+void makeraytree(Render *re)
+{
+       float min[3], max[3], sub[3];
+       int i;
        
-       re->i.infostr= NULL;
+       re->i.infostr= "Make raytree";
        re->stats_draw(re->sdh, &re->i);
+
+       BENCH(makeraytree_single(re), tree_build);
+               
+       //Calculate raytree max_size
+       //This is ONLY needed to kept a bogus behaviour of SUN and HEMI lights
+       RE_rayobject_merge_bb( re->raytree, min, max );
+       for(i=0; i<3; i++)
+       {
+               min[i] += 0.01f;
+               max[i] += 0.01f;
+               sub[i] = max[i]-min[i];
+       }
+       re->maxdist = sqrt( sub[0]*sub[0] + sub[1]*sub[1] + sub[2]*sub[2] );
+
+       re->i.infostr= "Raytree finished";
 }
 
 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 +594,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 +603,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;
+
+       isec.orig.ob   = obi;
+       isec.orig.face = vlr;
+       RE_RC_INIT(isec, shi);
 
-       if(RE_ray_tree_intersect(R.raytree, &isec)) {
+       if(RE_rayobject_raycast(R.raytree, &isec)) {
                float d= 1.0f;
                
                shi.mask= origshi->mask;
@@ -596,6 +737,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 +1356,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 +1455,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 */
                
@@ -1350,11 +1492,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);
        }
 }
 
@@ -1367,9 +1512,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;
        }
@@ -1377,8 +1524,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++) {
                
@@ -1390,12 +1542,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,
@@ -1568,6 +1719,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];
@@ -1583,13 +1735,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) */
@@ -1627,6 +1791,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 */
@@ -1638,14 +1803,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;
                }
@@ -1705,18 +1870,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;
 
@@ -1763,14 +1939,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;
                        }
@@ -1876,12 +2052,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;
@@ -1912,13 +2091,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, 
@@ -1954,11 +2142,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) {
@@ -1966,7 +2154,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];
@@ -1975,6 +2163,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) {
@@ -1993,7 +2185,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++;
@@ -2033,6 +2225,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;
@@ -2049,6 +2242,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) {
@@ -2060,19 +2259,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) */
@@ -2085,7 +2282,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;
@@ -2109,11 +2306,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;
@@ -2122,19 +2321,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);
@@ -2147,13 +2356,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) */
@@ -2163,7 +2374,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);
@@ -2172,8 +2384,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;
        }
 
 }
@@ -2183,31 +2394,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 */
index 5db81288c1ebb8e7272935db63ffb51116c05430..f3db64295a3c087a9656babf6a08d261798de1c6 100644 (file)
@@ -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);
                        
index 621831fb34111883f64f8423e43c9d9afbfdbedb..5f21a0e2e1a51c3007e718c50ac5576c70fe90c5 100644 (file)
@@ -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,29 @@ 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->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;
index 7541ce530739eba2d58957e502e2c364eac4ae1b..0d3c5772d8ad0e593ed991b1db9645514042427a 100644 (file)
@@ -44,6 +44,7 @@
&n