clray

annotate src/scene.cc @ 26:c740ae431d51

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