*introduced new method for packing/optimizing trees after building
authorAndre Susano Pinto <andresusanopinto@gmail.com>
Sun, 6 Sep 2009 19:14:06 +0000 (19:14 +0000)
committerAndre Susano Pinto <andresusanopinto@gmail.com>
Sun, 6 Sep 2009 19:14:06 +0000 (19:14 +0000)
(this is a generalization of some of the experimental stuff i tried during SoC,
 but only had time to improve a few days ago)
 - it should yield slightly better results
 - the cost model can somehow be tweaked to optimize for diferent trees.

*cleaned up some code
*added counters for number of SIMD BB tests
*added GPL license block on missing files

15 files changed:
source/blender/makesdna/DNA_scene_types.h
source/blender/makesrna/intern/rna_scene.c
source/blender/render/extern/include/RE_raytrace.h
source/blender/render/intern/raytrace/bvh.h
source/blender/render/intern/raytrace/qbvh.h [deleted file]
source/blender/render/intern/raytrace/rayobject_bvh.cpp
source/blender/render/intern/raytrace/rayobject_qbvh.cpp
source/blender/render/intern/raytrace/rayobject_rtbuild.cpp
source/blender/render/intern/raytrace/rayobject_svbvh.cpp
source/blender/render/intern/raytrace/rayobject_vbvh.cpp
source/blender/render/intern/raytrace/reorganize.h
source/blender/render/intern/raytrace/svbvh.h
source/blender/render/intern/raytrace/vbvh.h
source/blender/render/intern/source/rayobject_raycounter.c
source/blender/render/intern/source/rayshade.c

index 6efd47d93487fc2bfd28def8419a6b5cd19c6e69..82658be24bfa7157c0f6d1fd40cd5cb8566188aa 100644 (file)
@@ -769,15 +769,13 @@ typedef struct Scene {
 #define R_YAFRAY       1
 
 /* raytrace structure */
-#define R_RAYSTRUCTURE_HIER_BVH_BVH            0
-#define R_RAYSTRUCTURE_HIER_BVH_OCTREE 1
-#define R_RAYSTRUCTURE_SINGLE_OCTREE   2
-#define R_RAYSTRUCTURE_SINGLE_BVH              3
-
-/* raytrace tree type */
-#define R_RAYTRACE_TREE_BVH            0
-#define R_RAYTRACE_TREE_BLIBVH 1
-#define R_RAYTRACE_TREE_BIH            2
+#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
index 7baf8c8fd9364c8de089b446c7cb3ae8b02f7bb2..db832f1d31c4488a0cadd43718b5c56e76ed95b3 100644 (file)
@@ -1032,18 +1032,16 @@ static void rna_def_scene_render_data(BlenderRNA *brna)
                {0, NULL, 0, NULL, NULL}};
 
        static EnumPropertyItem raytrace_structure_items[] = {
-               {R_RAYSTRUCTURE_HIER_BVH_BVH, "{R_RAYSTRUCTURE_HIER_BVH_BVH", 0, "BVH of BVH's", "Create a BVH of objects (each object has it own BVH)"},
-               {R_RAYSTRUCTURE_HIER_BVH_OCTREE, "{R_RAYSTRUCTURE_HIER_BVH_OCTREE", 0, "BVH of octree", "Create a BVH of objects (each object has it own octree)"},
-               {R_RAYSTRUCTURE_SINGLE_BVH, "{R_RAYSTRUCTURE_SINGLE_BVH", 0, "Single BVH", "BVH of all primitives (no instance support)"},
-               {R_RAYSTRUCTURE_SINGLE_OCTREE, "{R_RAYSTRUCTURE_SINGLE_OCTREE", 0, "Octree", "Octree of all primitives (no instance support)"},
-               {0, NULL, 0, NULL, NULL}};
+               {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 raytrace_tree_type_items[] = {
-               {R_RAYTRACE_TREE_BVH, "{R_RAYTRACE_TREE_BVH", 0, "BVH", "rayobject_bvh.c"},
-               {R_RAYTRACE_TREE_BLIBVH, "{R_RAYTRACE_TREE_BLIBVH", 0, "BLIbvh", "rayobject_blibvh.c"},
-               {R_RAYTRACE_TREE_BIH, "{R_RAYSTRUCTURE_SINGLE_BVH", 0, "BIH", "rayobject_bih.c"},
-               {0, NULL, 0, NULL, NULL}};
-               
        static EnumPropertyItem fixed_oversample_items[] = {
                {5, "OVERSAMPLE_5", 0, "5", ""},
                {8, "OVERSAMPLE_8", 0, "8", ""},
@@ -1462,12 +1460,6 @@ static void rna_def_scene_render_data(BlenderRNA *brna)
        RNA_def_property_ui_text(prop, "Raytrace Acceleration Structure", "Type of raytrace accelerator structure.");
        RNA_def_property_update(prop, NC_SCENE|ND_RENDER_OPTIONS, NULL);
 
-       prop= RNA_def_property(srna, "raytrace_tree_type", PROP_ENUM, PROP_NONE);
-       RNA_def_property_enum_sdna(prop, NULL, "raytrace_tree_type");
-       RNA_def_property_enum_items(prop, raytrace_tree_type_items);
-       RNA_def_property_ui_text(prop, "Raytrace tree type", "Type of raytrace accelerator structure.");
-       RNA_def_property_update(prop, NC_SCENE|ND_RENDER_OPTIONS, NULL);
-       
        prop= RNA_def_property(srna, "antialiasing", PROP_BOOLEAN, PROP_NONE);
        RNA_def_property_boolean_sdna(prop, NULL, "mode", R_OSA);
        RNA_def_property_ui_text(prop, "Anti-Aliasing", "Render and combine multiple samples per pixel to prevent jagged edges.");
index 01b64c1505867e63483f10cbc2a7fec1ae755992..c775a7d18efc6ed2c563d85e30d6d29274b549f6 100644 (file)
@@ -53,7 +53,7 @@ struct RayCounter
        {
                unsigned long long test, hit;
                
-       } faces, bb, raycast, raytrace_hint, rayshadow_last_hit;
+       } faces, bb, simd_bb, raycast, raytrace_hint, rayshadow_last_hit;
 };
 
 /* #define RE_RC_INIT(isec, shi) (isec).count = re_rc_counter+(shi).thread */
index 21234a40673b7fbb16bfd553d40990bac719d6b4..7d3479e5331db19f24ab9515c183ea6530992d37 100644 (file)
@@ -241,17 +241,13 @@ static int bvh_node_stack_raycast_simd(Node *root, Isect *isec)
                                t_node[i] = t->child;
                        }
 */
-                       RE_RC_COUNT(isec->raycounter->bb.test);
-                       RE_RC_COUNT(isec->raycounter->bb.test);
-                       RE_RC_COUNT(isec->raycounter->bb.test);
-                       RE_RC_COUNT(isec->raycounter->bb.test);
-                       
+                       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->bb.hit);
+                               RE_RC_COUNT(isec->raycounter->simd_bb.hit);
                                if(!is_leaf(t_node[i]))
                                {
                                        for(Node *t=t_node[i]; t; t=t->sibling)
diff --git a/source/blender/render/intern/raytrace/qbvh.h b/source/blender/render/intern/raytrace/qbvh.h
deleted file mode 100644 (file)
index e69de29..0000000
index bf54f889ebf2a864e33c81128bbd165b34740bed..a7e96f6d3fc0d771b424399676eb19820d7110ea 100644 (file)
@@ -65,7 +65,6 @@ struct BVHTree
        RTBuilder *builder;
 };
 
-
 /*
  * Push nodes (used on dfs)
  */
index e3a15b5d7f32fc87bac3f9aa35fe95b768ab83bd..53579d2915f7bc5538c420e9faffc47a19d2036b 100644 (file)
@@ -1,6 +1,33 @@
+/**
+ * $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 "qbvh.h"
 #include "reorganize.h"
 
 #define DFS_STACK_SIZE 256
@@ -17,6 +44,17 @@ struct QBVHTree
 };
 
 
+/*
+ * 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)
 {
@@ -31,9 +69,20 @@ void bvh_done<QBVHTree>(QBVHTree *obj)
                                           BLI_memarena_use_align(arena2, 16);
 
        //Build and optimize the tree
-       VBVHNode *root = BuildBinaryVBVH(arena1).transform(obj->builder);       
-       pushup_simd<VBVHNode,4>(root);                                     
-       obj->root = Reorganize_SVBVH<VBVHNode>(arena2).transform(root);
+       
+       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);      
index 238929e1dbb7dd29cc21599369a9a10c27a693a8..430045b56b66a47f0a13beec2bbcda4d2695793a 100644 (file)
@@ -1,3 +1,31 @@
+/**
+ * $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>
index df03390152601323604d5364c7fa90ca623b678e..1bcffddd0ac845159dc30e7e865a1500be0d188a 100644 (file)
@@ -1,3 +1,31 @@
+/**
+ * $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"
@@ -25,9 +53,12 @@ void bvh_done<SVBVHTree>(SVBVHTree *obj)
        MemArena *arena1 = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE);
                                           BLI_memarena_use_malloc(arena1);
 
-       //Build and optimize the tree
-       VBVHNode *root = BuildBinaryVBVH(arena1).transform(obj->builder);
+       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);
@@ -35,12 +66,11 @@ void bvh_done<SVBVHTree>(SVBVHTree *obj)
        pushup(root);
        pushdown(root);
        pushup_simd<VBVHNode,4>(root);
-
-       MemArena *arena2 = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE);
-       BLI_memarena_use_malloc(arena2);
-       BLI_memarena_use_align(arena2, 16);
+       
        obj->root = Reorganize_SVBVH<VBVHNode>(arena2).transform(root);
+
        
+       //Free data
        BLI_memarena_free(arena1);
        
        obj->node_arena = arena2;
index f81ca1e5d1b6d015c308acb8e5059702b8f11c7d..4e51de0da074808c01c774617e7200274812204f 100644 (file)
@@ -70,7 +70,7 @@ void bvh_done<VBVHTree>(VBVHTree *obj)
 
        
        //Build and optimize the tree
-       VBVHNode *root = BuildBinaryVBVH(arena1).transform(obj->builder);
+       VBVHNode *root = BuildBinaryVBVH<VBVHNode>(arena1).transform(obj->builder);
 
        reorganize(root);
        remove_useless(root, &root);
index 712221fb739091990e6a06ed923976c557ff9867..f0335b769d5e87418add1f2b01da09f67936a757 100644 (file)
  *
  * ***** END GPL LICENSE BLOCK *****
  */
+#include <stdio.h>
+#include <math.h>
 #include <algorithm>
+#include <vector>
 #include <queue>
 
 extern int tot_pushup;
@@ -279,3 +282,235 @@ float bvh_refit(Node *node)
        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;            
+       }       
+};
index b243e91d381b6663f8fb526ab72d0e9ed31c9015..840ccc24d1a6253de066ccc262fa6a69051c6257 100644 (file)
@@ -56,15 +56,12 @@ inline void bvh_node_push_childs<SVBVHNode>(SVBVHNode *node, Isect *isec, SVBVHN
        while(i+4 <= node->nchilds)
        {
                int res = test_bb_group4( (__m128*) (node->child_bb+6*i), isec );
-               RE_RC_COUNT(isec->raycounter->bb.test);
-               RE_RC_COUNT(isec->raycounter->bb.test);
-               RE_RC_COUNT(isec->raycounter->bb.test);
-               RE_RC_COUNT(isec->raycounter->bb.test);
+               RE_RC_COUNT(isec->raycounter->simd_bb.test);
                
-               if(res & 1) { stack[stack_pos++] = node->child[i+0]; RE_RC_COUNT(isec->raycounter->bb.hit); }
-               if(res & 2) { stack[stack_pos++] = node->child[i+1]; RE_RC_COUNT(isec->raycounter->bb.hit); }
-               if(res & 4) { stack[stack_pos++] = node->child[i+2]; RE_RC_COUNT(isec->raycounter->bb.hit); }
-               if(res & 8) { stack[stack_pos++] = node->child[i+3]; RE_RC_COUNT(isec->raycounter->bb.hit); }
+               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;
        }
index 7c07bd9ded0e5e9bcfb4dce28bb929f64ec5adf3..db1df43f6650dfd2ffb4b7c99afba8eb755e9083 100644 (file)
@@ -1,3 +1,31 @@
+/**
+ * $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>
@@ -75,6 +103,7 @@ void append_sibling(Node *node, Node *sibling)
 /*
  * Builds a binary VBVH from a rtbuild
  */
+template<class Node>
 struct BuildBinaryVBVH
 {
        MemArena *arena;
@@ -84,9 +113,9 @@ struct BuildBinaryVBVH
                arena = a;
        }
 
-       VBVHNode *create_node()
+       Node *create_node()
        {
-               VBVHNode *node = (VBVHNode*)BLI_memarena_alloc( arena, sizeof(VBVHNode) );
+               Node *node = (Node*)BLI_memarena_alloc( arena, sizeof(Node) );
                assert( RE_rayobject_isAligned(node) );
 
                node->sibling = NULL;
@@ -100,26 +129,26 @@ struct BuildBinaryVBVH
                return ::rtbuild_heuristic_object_split(builder, 2);
        }
        
-       VBVHNode *transform(RTBuilder *builder)
+       Node *transform(RTBuilder *builder)
        {
                
                int size = rtbuild_size(builder);
                if(size == 1)
                {
-                       VBVHNode *node = create_node();
+                       Node *node = create_node();
                        INIT_MINMAX(node->bb, node->bb+3);
                        rtbuild_merge_bb(builder, node->bb, node->bb+3);                
-                       node->child = (VBVHNode*) rtbuild_get_primitive( builder, 0 );
+                       node->child = (Node*) rtbuild_get_primitive( builder, 0 );
                        return node;
                }
                else
                {
-                       VBVHNode *node = create_node();
+                       Node *node = create_node();
 
                        INIT_MINMAX(node->bb, node->bb+3);
                        rtbuild_merge_bb(builder, node->bb, node->bb+3);
                        
-                       VBVHNode **child = &node->child;
+                       Node **child = &node->child;
 
                        int nc = rtbuild_split(builder);
                        assert(nc == 2);
index 83ba15602dae3124bd45fba6dbfaffada0736022..b47df607c109f7ef10c97415a6b24359dece6d7e 100644 (file)
@@ -39,6 +39,9 @@ void RE_RC_INFO(RayCounter *info)
        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");
@@ -51,6 +54,9 @@ void RE_RC_INFO(RayCounter *info)
        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");
@@ -64,6 +70,9 @@ void RE_RC_MERGE(RayCounter *dest, RayCounter *tmp)
        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;
        
index 928083620e174c87591551312f056ab9a6d81491..727d5826e4998d94661a2ef1ab2a618762900ad9 100644 (file)
 /* only to be used here in this file, it's for speed */
 extern struct Render R;
 /* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ */
-
-RayObject *  RE_rayobject_tree_create(int type, int size) __attribute__((noinline));
-
-RayObject *  RE_rayobject_tree_create(int type, int size)
+RayObject *  RE_rayobject_create(int type, int size)
 {
-//     if(type == R_RAYTRACE_TREE_BIH)
-       return RE_rayobject_svbvh_create(size);
-
-       if(type == R_RAYTRACE_TREE_BVH)
-               return RE_rayobject_bvh_create(size);
-       if(type == R_RAYTRACE_TREE_BIH)
-               return RE_rayobject_bih_create(size);
-       if(type == R_RAYTRACE_TREE_BLIBVH)
-               return RE_rayobject_blibvh_create(size);
+       if(type == R_RAYSTRUCTURE_AUTO)
+       {
+               //TODO
+//             if(detect_simd())
+//                     type = R_RAYSTRUCTURE_SIMD_SVBVH;
+//             else
+//                     type = R_RAYSTRUCTURE_VBVH;
 
+                       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;
 }
 
 #ifdef RE_RAYCOUNTER
@@ -205,14 +231,8 @@ RayObject* makeraytree_object(Render *re, ObjectInstanceRen *obi)
                }
                assert( faces > 0 );
 
-               //Create Ray cast accelaration structure
-               
-               //TODO dynamic ocres
-               if(re->r.raystructure == R_RAYSTRUCTURE_HIER_BVH_OCTREE)
-                       raytree = obr->raytree = RE_rayobject_octree_create( re->r.ocres, faces );
-               else //if(re->r.raystructure == R_RAYSTRUCTURE_HIER_BVH_BVH)
-                       raytree = obr->raytree = RE_rayobject_tree_create( re->r.raytrace_tree_type, faces );
-                       
+               //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;
                
@@ -239,51 +259,6 @@ RayObject* makeraytree_object(Render *re, ObjectInstanceRen *obi)
        return obi->obr->raytree;
 }
 
-/*
- * create an hierarchic raytrace structure with all objects
- *
- * R_TRANSFORMED objects instances reuse the same tree by using the rayobject_instance
- */
-static void makeraytree_hier(Render *re)
-{
-       //TODO
-       // out-of-memory safeproof
-       // break render
-       // update render stats
-
-       ObjectInstanceRen *obi;
-       int num_objects = 0;
-
-       re->i.infostr="Creating raytrace structure";
-       re->stats_draw(re->sdh, &re->i);
-
-       //Count number of objects
-       for(obi=re->instancetable.first; obi; obi=obi->next)
-       if(is_raytraceable(re, obi))
-               num_objects++;
-
-       //Create raytree
-       re->raytree = RE_rayobject_tree_create( re->r.raytrace_tree_type, num_objects );
-       
-       for(obi=re->instancetable.first; obi; obi=obi->next)
-       if(is_raytraceable(re, obi))
-       {
-               RayObject *obj = makeraytree_object(re, obi);
-               RE_rayobject_add( re->raytree, obj );
-
-               if(re->test_break(re->tbh))
-                       break;
-       }
-
-       if(!re->test_break(re->tbh))
-       {
-               RE_rayobject_done( re->raytree );
-       }
-
-       re->i.infostr= NULL;
-       re->stats_draw(re->sdh, &re->i);
-}
-
 static int has_special_rayobject(Render *re, ObjectInstanceRen *obi)
 {
        if( (obi->flag & R_TRANSFORMED) )
@@ -337,10 +312,7 @@ static void makeraytree_single(Render *re)
        }
        
        //Create raytree
-       if(re->r.raystructure == R_RAYSTRUCTURE_SINGLE_OCTREE)
-               raytree = re->raytree = RE_rayobject_octree_create( re->r.ocres, faces );
-       else //if(re->r.raystructure == R_RAYSTRUCTURE_SINGLE_BVH)
-               raytree = re->raytree = RE_rayobject_tree_create( re->r.raytrace_tree_type, faces );
+       raytree = re->raytree = RE_rayobject_create( re->r.raytrace_tree_type, faces );
 
        face    = re->rayfaces  = (RayFace*)MEM_callocN(faces*sizeof(RayFace), "Render ray faces");
        
@@ -385,32 +357,8 @@ void makeraytree(Render *re)
 {
        float min[3], max[3], sub[3];
        int i;
-       const char *tree_type = "Tree(unknown)";
 
-       re->r.raystructure = R_RAYSTRUCTURE_SINGLE_BVH;
-#ifdef RE_RAYCOUNTER
-       if(re->r.raytrace_tree_type == R_RAYTRACE_TREE_BVH)
-               tree_type = "BVH";
-       if(re->r.raytrace_tree_type == R_RAYTRACE_TREE_BIH)
-               tree_type = "BIH";
-       if(re->r.raytrace_tree_type == R_RAYTRACE_TREE_BLIBVH)
-               tree_type = "BLIBVH";
-
-       if(re->r.raystructure == R_RAYSTRUCTURE_SINGLE_OCTREE)
-               printf("Building single octree\n");
-       else if(re->r.raystructure == R_RAYSTRUCTURE_SINGLE_BVH)
-               printf("Building single tree(%s)\n", tree_type);
-       else if(re->r.raystructure == R_RAYSTRUCTURE_HIER_BVH_OCTREE)
-               printf("Building tree(%s) of octrees\n", tree_type);
-       else
-               printf("Building tree(%s) of trees(%s)\n", tree_type, tree_type);
-#endif
-
-       if(ELEM(re->r.raystructure, R_RAYSTRUCTURE_SINGLE_BVH, R_RAYSTRUCTURE_SINGLE_OCTREE))
-               BENCH(makeraytree_single(re), tree_build);
-       else
-               BENCH(makeraytree_hier(re), tree_build);
-               
+       BENCH(makeraytree_single(re), tree_build);
                
        //Calculate raytree max_size
        //This is ONLY needed to kept a bogus behaviour of SUN and HEMI lights