8f471f095e22c0b468e534ef77d40d749c75afae
[blender-staging.git] / source / blender / render / intern / raytrace / rayobject_rtbuild.h
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 #ifndef RE_RAYOBJECT_RTBUILD_H
30 #define RE_RAYOBJECT_RTBUILD_H
31
32 #ifdef __cplusplus
33 extern "C" {
34 #endif
35
36 #include "rayobject.h"
37
38
39 /*
40  * Ray Tree Builder
41  *      this structs helps building any type of tree
42  *      it contains several methods to organiza/split nodes
43  *      allowing to create a given tree on the fly.
44  *
45  * Idea is that other trees BVH, BIH can use this code to
46  * generate with simple calls, and then convert to the theirs
47  * specific structure on the fly.
48  */
49 #define RTBUILD_MAX_CHILDS 32
50
51
52 typedef struct RTBuilder
53 {
54         struct Object
55         {
56                 RayObject *obj;
57                 float cost;
58                 float bb[6];
59                 int selected;
60         };
61         
62         /* list to all primitives added in this tree */
63         struct
64         {
65                 Object *begin, *end;
66                 int maxsize;
67         } primitives;
68         
69         /* sorted list of rayobjects */
70         struct Object **sorted_begin[3], **sorted_end[3];
71
72         /* axis used (if any) on the split method */
73         int split_axis;
74         
75         /* child partitions calculated during splitting */
76         int child_offset[RTBUILD_MAX_CHILDS+1];
77         
78 //      int child_sorted_axis; /* -1 if not sorted */
79         
80         float bb[6];
81
82 } RTBuilder;
83
84 /* used during creation */
85 RTBuilder* rtbuild_create(int size);
86 void rtbuild_free(RTBuilder *b);
87 void rtbuild_add(RTBuilder *b, RayObject *o);
88 void rtbuild_done(RTBuilder *b);
89 void rtbuild_merge_bb(RTBuilder *b, float *min, float *max);
90 int rtbuild_size(RTBuilder *b);
91
92 RayObject* rtbuild_get_primitive(RTBuilder *b, int offset);
93
94 /* used during tree reorganization */
95 RTBuilder* rtbuild_get_child(RTBuilder *b, int child, RTBuilder *tmp);
96
97 /* Calculates child partitions and returns number of efectively needed partitions */
98 int rtbuild_get_largest_axis(RTBuilder *b);
99
100 //Object partition
101 int rtbuild_mean_split(RTBuilder *b, int nchilds, int axis);
102 int rtbuild_mean_split_largest_axis(RTBuilder *b, int nchilds);
103
104 int rtbuild_heuristic_object_split(RTBuilder *b, int nchilds);
105
106 //Space partition
107 int rtbuild_median_split(RTBuilder *b, float *separators, int nchilds, int axis);
108 int rtbuild_median_split_largest_axis(RTBuilder *b, int nchilds);
109
110
111 /* bb utils */
112 float bb_area(float *min, float *max);
113 float bb_volume(float *min, float *max);
114 int bb_largest_axis(float *min, float *max);
115 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 */
116
117 #ifdef __cplusplus
118 }
119 #endif
120
121 #endif