clray
view src/scene.cc @ 26:c740ae431d51
continuing with the kdtree construction
| author | John Tsiombikas <nuclear@member.fsf.org> |
|---|---|
| date | Tue, 17 Aug 2010 01:19:43 +0100 |
| parents | 58642a8316b7 |
| children | 8b2f2ad14ae7 |
line source
1 #include <math.h>
2 #include <float.h>
3 #include <assert.h>
4 #include "scene.h"
7 static int build_kdtree(KDNode *kd);
8 static float eval_cost(const std::list<const Face*> &faces, const AABBox &aabb, int axis);
9 static void free_kdtree(KDNode *node);
12 static int accel_param[NUM_ACCEL_PARAMS] = {
13 75, // max tree depth
14 0, // max items per node (0 means ignore limit)
15 5, // estimated traversal cost
16 15 // estimated interseciton cost
17 };
20 void set_accel_param(int p, int v)
21 {
22 assert(p >= 0 && p < NUM_ACCEL_PARAMS);
23 accel_param[p] = v;
24 }
27 #define FEQ(a, b) (fabs((a) - (b)) < 1e-8)
28 bool Face::operator ==(const Face &f) const
29 {
30 for(int i=0; i<3; i++) {
31 for(int j=0; j<3; j++) {
32 if(!FEQ(v[i].pos[j], f.v[i].pos[j])) {
33 return false;
34 }
35 if(!FEQ(v[i].normal[j], f.v[i].normal[j])) {
36 return false;
37 }
38 }
39 if(!FEQ(normal[i], f.normal[i])) {
40 return false;
41 }
42 }
43 return true;
44 }
46 float AABBox::calc_surface_area() const
47 {
48 float area1 = (max[0] - min[0]) * (max[1] - min[1]);
49 float area2 = (max[3] - min[3]) * (max[1] - min[1]);
50 float area3 = (max[0] - min[0]) * (max[3] - min[3]);
52 return 2.0f * (area1 + area2 + area3);
53 }
55 KDNode::KDNode()
56 {
57 axis = 0;
58 pt = 0.0;
59 left = right = 0;
60 num_faces = 0;
61 }
64 Scene::Scene()
65 {
66 facebuf = 0;
67 num_faces = -1;
68 kdtree = 0;
69 }
71 Scene::~Scene()
72 {
73 delete [] facebuf;
74 }
76 bool Scene::add_mesh(Mesh *m)
77 {
78 // make sure triangles have material ids
79 for(size_t i=0; i<m->faces.size(); i++) {
80 m->faces[i].matid = m->matid;
81 }
83 try {
84 meshes.push_back(m);
85 }
86 catch(...) {
87 return false;
88 }
90 // invalidate facebuffer and count
91 delete [] facebuf;
92 facebuf = 0;
93 num_faces = -1;
95 return true;
96 }
98 int Scene::get_num_meshes() const
99 {
100 return (int)meshes.size();
101 }
103 int Scene::get_num_faces() const
104 {
105 if(num_faces >= 0) {
106 return num_faces;
107 }
109 num_faces = 0;
110 for(size_t i=0; i<meshes.size(); i++) {
111 num_faces += meshes[i]->faces.size();
112 }
113 return num_faces;
114 }
116 int Scene::get_num_materials() const
117 {
118 return (int)matlib.size();
119 }
121 Material *Scene::get_materials()
122 {
123 if(matlib.empty()) {
124 return 0;
125 }
126 return &matlib[0];
127 }
129 const Material *Scene::get_materials() const
130 {
131 if(matlib.empty()) {
132 return 0;
133 }
134 return &matlib[0];
135 }
137 const Face *Scene::get_face_buffer() const
138 {
139 if(facebuf) {
140 return facebuf;
141 }
143 int num_meshes = get_num_meshes();
145 printf("constructing face buffer with %d faces (out of %d meshes)\n", get_num_faces(), num_meshes);
146 facebuf = new Face[num_faces];
147 Face *fptr = facebuf;
149 for(int i=0; i<num_meshes; i++) {
150 for(size_t j=0; j<meshes[i]->faces.size(); j++) {
151 *fptr++ = meshes[i]->faces[j];
152 }
153 }
154 return facebuf;
155 }
158 void Scene::build_kdtree()
159 {
160 const Face *faces = get_face_buffer();
161 int num_faces = get_num_faces();
163 printf("Constructing kd-tree out of %d faces ...\n", num_faces);
165 free_kdtree(kdtree);
166 kdtree = new KDNode;
168 /* Start the construction of the kdtree by adding all faces of the scene
169 * to the new root node. At the same time calculate the root's AABB.
170 */
171 kdtree->aabb.min[0] = kdtree->aabb.min[1] = kdtree->aabb.min[2] = FLT_MAX;
172 kdtree->aabb.max[0] = kdtree->aabb.max[1] = kdtree->aabb.max[2] = -FLT_MAX;
174 for(int i=0; i<num_faces; i++) {
175 const Face *face = faces + i;
177 // for each vertex of the face ...
178 for(int j=0; j<3; j++) {
179 const float *pos = face->v[j].pos;
181 // for each element (xyz) of the position vector ...
182 for(int k=0; k<3; k++) {
183 if(pos[k] < kdtree->aabb.min[k]) {
184 kdtree->aabb.min[k] = pos[k];
185 }
186 if(pos[k] > kdtree->aabb.max[k]) {
187 kdtree->aabb.max[k] = pos[k];
188 }
189 }
190 }
192 kdtree->faces.push_back(face); // add the face
193 kdtree->num_faces++;
194 }
196 // calculate the heuristic for the root
197 kdtree->cost = eval_cost(kdtree->faces, kdtree->aabb, kdtree->axis);
199 // now proceed splitting the root recursively
200 ::build_kdtree(kdtree);
201 }
203 static int build_kdtree(KDNode *kd)
204 {
205 int opt_max_items = accel_param[ACCEL_PARAM_MAX_NODE_ITEMS];
206 if(kd->num_faces == 0 || (opt_max_items > 1 && kd->num_faces < opt_max_items)) {
207 return 0;
208 }
210 int axis = (kd->axis + 1) % 3;
212 float best_cost[2], best_sum_cost = FLT_MAX;
213 float best_split;
215 std::list<const Face*>::iterator it = kd->faces.begin();
216 while(it != kd->faces.end()) {
217 const Face *face = *it++;
219 for(int i=0; i<3; i++) {
220 AABBox aabb_left, aabb_right;
221 const float *split = face->v[i].pos;
223 aabb_left = aabb_right = kd->aabb;
224 aabb_left.max[axis] = split[axis];
225 aabb_right.min[axis] = split[axis];
227 float left_cost = eval_cost(kd->faces, aabb_left, axis);
228 float right_cost = eval_cost(kd->faces, aabb_right, axis);
229 float sum_cost = left_cost + right_cost;
231 if(sum_cost < best_sum_cost) {
232 best_cost[0] = left_cost;
233 best_cost[1] = right_cost;
234 best_sum_cost = sum_cost;
235 best_split = split[axis];
236 }
237 }
238 }
240 if(best_sum_cost >= kd->cost) {
241 return 0; // stop splitting if it doesn't reduce the cost
242 }
243 kd->pt = best_split;
245 // create the two children
246 KDNode *kdleft, *kdright;
247 kdleft = new KDNode;
248 kdright = new KDNode;
250 kdleft->axis = kdright->axis = axis;
251 kdleft->aabb = kdright->aabb = kd->aabb;
253 kdleft->aabb.max[axis] = best_split;
254 kdright->aabb.min[axis] = best_split;
256 kdleft->cost = best_cost[0];
257 kdright->cost = best_cost[1];
259 it = kd->faces.begin();
260 while(it != kd->faces.end()) {
261 const Face *face = *it++;
263 if(face->v[0].pos[axis] < best_split ||
264 face->v[1].pos[axis] < best_split ||
265 face->v[2].pos[axis] < best_split) {
266 kdleft->faces.push_back(face);
267 kdleft->num_faces++;
268 }
269 if(face->v[0].pos[axis] >= best_split ||
270 face->v[1].pos[axis] >= best_split ||
271 face->v[2].pos[axis] >= best_split) {
272 kdright->faces.push_back(face);
273 kdright->num_faces++;
274 }
275 }
277 kd->left = kdleft;
278 kd->right = kdright;
279 return 0;
280 }
282 static float eval_cost(const std::list<const Face*> &faces, const AABBox &aabb, int axis)
283 {
284 int num_inside = 0;
285 int tcost = accel_param[ACCEL_PARAM_COST_TRAVERSE];
286 int icost = accel_param[ACCEL_PARAM_COST_INTERSECT];
288 std::list<const Face*>::const_iterator it = faces.begin();
289 while(it != faces.end()) {
290 const Face *face = *it++;
292 for(int i=0; i<3; i++) {
293 if(face->v[i].pos[axis] >= aabb.min[axis] && face->v[i].pos[axis] < aabb.max[axis]) {
294 num_inside++;
295 break;
296 }
297 }
298 }
300 return tcost + aabb.calc_surface_area() * num_inside * icost;
301 }
303 static void free_kdtree(KDNode *node)
304 {
305 if(node) {
306 free_kdtree(node->left);
307 free_kdtree(node->right);
308 delete node;
309 }
310 }