2c2a260df982e76d7f5c776feff59dae4f0adda8
[blender-staging.git] / source / blender / render / intern / raytrace / rayobject_bvh.cpp
1 /**
2  * $Id$
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version. 
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
19  *
20  * The Original Code is Copyright (C) 2009 Blender Foundation.
21  * All rights reserved.
22  *
23  * The Original Code is: all of this file.
24  *
25  * Contributor(s): AndrĂ© Pinto.
26  *
27  * ***** END GPL LICENSE BLOCK *****
28  */
29 #include <assert.h>
30
31 #include "RE_raytrace.h"
32 #include "rayobject_rtbuild.h"
33 #include "rayobject.h"
34 #include "MEM_guardedalloc.h"
35 #include "BKE_utildefines.h"
36 #include "BLI_arithb.h"
37 #include "BLI_memarena.h"
38 #include "bvh.h"
39
40 #define BVH_NCHILDS 2
41 #define RAY_BB_TEST_COST (0.2f)
42 #define DFS_STACK_SIZE  64
43 #define DYNAMIC_ALLOC
44
45 //#define rtbuild_split rtbuild_mean_split_largest_axis         /* objects mean split on the longest axis, childs BB are allowed to overlap */
46 //#define rtbuild_split rtbuild_median_split_largest_axis       /* space median split on the longest axis, childs BB are allowed to overlap */
47 #define rtbuild_split   rtbuild_heuristic_object_split          /* split objects using heuristic */
48
49 struct BVHNode
50 {
51         BVHNode *child[BVH_NCHILDS];
52         float   bb[6];
53         int split_axis;
54 };
55
56 struct BVHTree
57 {
58         RayObject rayobj;
59
60         BVHNode *root;
61
62         MemArena *node_arena;
63
64         float cost;
65         RTBuilder *builder;
66 };
67
68
69 /*
70  * Push nodes (used on dfs)
71  */
72 template<class Node>
73 inline static void bvh_node_push_childs(Node *node, Isect *isec, Node **stack, int &stack_pos)
74 {
75         //push nodes in reverse visit order
76         if(isec->idot_axis[node->split_axis] < 0.0f)
77         {
78                 int i;
79                 for(i=0; i<BVH_NCHILDS; i++)
80                         if(node->child[i] == 0)
81                                 break;
82                         else
83                                 stack[stack_pos++] = node->child[i];
84         }
85         else
86         {
87                 int i;  
88                 for(i=BVH_NCHILDS-1; i>=0; i--)
89                         if(node->child[i] != 0)
90                                 stack[stack_pos++] = node->child[i];
91         }
92 }
93
94 /*
95  * BVH done
96  */
97 static BVHNode *bvh_new_node(BVHTree *tree, int nid)
98 {
99         BVHNode *node = (BVHNode*)BLI_memarena_alloc(tree->node_arena, sizeof(BVHNode));
100         return node;
101 }
102
103 static int child_id(int pid, int nchild)
104 {
105         //N child of node A = A * K + (2 - K) + N, (0 <= N < K)
106     return pid*BVH_NCHILDS+(2-BVH_NCHILDS)+nchild;
107 }
108         
109
110 static BVHNode *bvh_rearrange(BVHTree *tree, RTBuilder *builder, int nid, float *cost)
111 {
112         *cost = 0;
113         if(rtbuild_size(builder) == 0)
114                 return 0;
115
116         if(rtbuild_size(builder) == 1)
117         {
118                 RayObject *child = builder->begin[0];
119
120                 if(RayObject_isRayFace(child))
121                 {
122                         int i;
123                         BVHNode *parent = bvh_new_node(tree, nid);
124                         parent->split_axis = 0;
125
126                         INIT_MINMAX(parent->bb, parent->bb+3);
127
128                         for(i=0; i<1; i++)
129                         {
130                                 parent->child[i] = (BVHNode*)builder->begin[i];
131                                 bvh_node_merge_bb(parent->child[i], parent->bb, parent->bb+3);
132                         }
133                         for(; i<BVH_NCHILDS; i++)
134                                 parent->child[i] = 0;
135
136                         *cost = RE_rayobject_cost(child)+RAY_BB_TEST_COST;
137                         return parent;
138                 }
139                 else
140                 {
141                         assert(!RayObject_isAligned(child));
142                         //Its a sub-raytrace structure, assume it has it own raycast
143                         //methods and adding a Bounding Box arround is unnecessary
144
145                         *cost = RE_rayobject_cost(child);
146                         return (BVHNode*)child;
147                 }
148         }
149         else
150         {
151                 int i;
152                 RTBuilder tmp;
153                 BVHNode *parent = bvh_new_node(tree, nid);
154                 int nc = rtbuild_split(builder, BVH_NCHILDS); 
155
156
157                 INIT_MINMAX(parent->bb, parent->bb+3);
158                 parent->split_axis = builder->split_axis;
159                 for(i=0; i<nc; i++)
160                 {
161                         float cbb[6];
162                         float tcost;
163                         parent->child[i] = bvh_rearrange( tree, rtbuild_get_child(builder, i, &tmp), child_id(nid,i), &tcost );
164                         
165                         INIT_MINMAX(cbb, cbb+3);
166                         bvh_node_merge_bb(parent->child[i], cbb, cbb+3);
167                         DO_MIN(cbb,   parent->bb);
168                         DO_MAX(cbb+3, parent->bb+3);
169                         
170                         *cost += tcost*bb_area(cbb, cbb+3);
171                 }
172                 for(; i<BVH_NCHILDS; i++)
173                         parent->child[i] = 0;
174
175                 *cost /= bb_area(parent->bb, parent->bb+3);
176                 *cost += nc*RAY_BB_TEST_COST;
177                 return parent;
178         }
179 }
180
181 template<>
182 void bvh_done<BVHTree>(BVHTree *obj)
183 {
184         int needed_nodes = (rtbuild_size(obj->builder)+1)*2;
185         if(needed_nodes > BLI_MEMARENA_STD_BUFSIZE)
186                 needed_nodes = BLI_MEMARENA_STD_BUFSIZE;
187
188         obj->node_arena = BLI_memarena_new(needed_nodes);
189         BLI_memarena_use_malloc(obj->node_arena);
190
191         
192         obj->root = bvh_rearrange( obj, obj->builder, 1, &obj->cost );
193         
194         rtbuild_free( obj->builder );
195         obj->builder = NULL;
196 }
197
198 template<>
199 int bvh_intersect<BVHTree>(BVHTree *obj, Isect* isec)
200 {
201         if(RayObject_isAligned(obj->root))
202                 return bvh_node_stack_raycast<BVHNode,64>(obj->root, isec);
203         else
204                 return RE_rayobject_intersect( (RayObject*) obj->root, isec );
205 }
206
207
208 /* the cast to pointer function is needed to workarround gcc bug: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11407 */
209 static RayObjectAPI bvh_api =
210 {
211         (RE_rayobject_raycast_callback) ((int(*)(BVHTree*,Isect*)) &bvh_intersect<BVHTree>),
212         (RE_rayobject_add_callback)     ((void(*)(BVHTree*,RayObject*)) &bvh_add<BVHTree>),
213         (RE_rayobject_done_callback)    ((void(*)(BVHTree*))       &bvh_done<BVHTree>),
214         (RE_rayobject_free_callback)    ((void(*)(BVHTree*))       &bvh_free<BVHTree>),
215         (RE_rayobject_merge_bb_callback)((void(*)(BVHTree*,float*,float*)) &bvh_bb<BVHTree>),
216         (RE_rayobject_cost_callback)    ((float(*)(BVHTree*))      &bvh_cost<BVHTree>)
217 };
218
219
220 RayObject *RE_rayobject_bvh_create(int size)
221 {
222         BVHTree *obj= (BVHTree*)MEM_callocN(sizeof(BVHTree), "BVHTree");
223         assert( RayObject_isAligned(obj) ); /* RayObject API assumes real data to be 4-byte aligned */  
224         
225         obj->rayobj.api = &bvh_api;
226         obj->root = NULL;
227         
228         obj->node_arena = NULL;
229         obj->builder    = rtbuild_create( size );
230         
231         return RayObject_unalignRayAPI((RayObject*) obj);
232 }