John@15: #include nuclear@25: #include nuclear@26: #include nuclear@22: #include "scene.h" nuclear@27: #include "ogl.h" nuclear@6: nuclear@26: nuclear@27: static void draw_kdtree(const KDNode *node, int level = 0); nuclear@27: static bool build_kdtree(KDNode *kd, int level = 0); nuclear@27: static float eval_cost(const std::list &faces, const AABBox &aabb, int axis, float par_sarea = 1.0); nuclear@26: static void free_kdtree(KDNode *node); nuclear@27: static int kdtree_depth(const KDNode *node); nuclear@27: static void print_item_counts(const KDNode *node, int level); nuclear@26: nuclear@26: nuclear@26: static int accel_param[NUM_ACCEL_PARAMS] = { nuclear@26: 75, // max tree depth nuclear@26: 0, // max items per node (0 means ignore limit) nuclear@26: 5, // estimated traversal cost nuclear@26: 15 // estimated interseciton cost nuclear@26: }; nuclear@26: nuclear@26: nuclear@26: void set_accel_param(int p, int v) nuclear@26: { nuclear@26: assert(p >= 0 && p < NUM_ACCEL_PARAMS); nuclear@26: accel_param[p] = v; nuclear@26: } nuclear@26: nuclear@26: John@15: #define FEQ(a, b) (fabs((a) - (b)) < 1e-8) John@15: bool Face::operator ==(const Face &f) const John@15: { John@15: for(int i=0; i<3; i++) { John@15: for(int j=0; j<3; j++) { John@15: if(!FEQ(v[i].pos[j], f.v[i].pos[j])) { John@15: return false; John@15: } John@15: if(!FEQ(v[i].normal[j], f.v[i].normal[j])) { John@15: return false; John@15: } John@15: } John@15: if(!FEQ(normal[i], f.normal[i])) { John@15: return false; John@15: } John@15: } John@15: return true; John@15: } John@15: nuclear@25: float AABBox::calc_surface_area() const nuclear@25: { nuclear@25: float area1 = (max[0] - min[0]) * (max[1] - min[1]); nuclear@25: float area2 = (max[3] - min[3]) * (max[1] - min[1]); nuclear@25: float area3 = (max[0] - min[0]) * (max[3] - min[3]); nuclear@25: nuclear@25: return 2.0f * (area1 + area2 + area3); nuclear@25: } nuclear@25: nuclear@26: KDNode::KDNode() nuclear@26: { nuclear@26: axis = 0; nuclear@26: pt = 0.0; nuclear@26: left = right = 0; nuclear@26: num_faces = 0; nuclear@26: } nuclear@26: nuclear@25: nuclear@24: Scene::Scene() nuclear@24: { nuclear@24: facebuf = 0; nuclear@24: num_faces = -1; nuclear@24: kdtree = 0; nuclear@24: } nuclear@24: nuclear@24: Scene::~Scene() nuclear@24: { nuclear@24: delete [] facebuf; nuclear@24: } nuclear@24: nuclear@13: bool Scene::add_mesh(Mesh *m) nuclear@13: { nuclear@13: // make sure triangles have material ids nuclear@13: for(size_t i=0; ifaces.size(); i++) { nuclear@13: m->faces[i].matid = m->matid; nuclear@13: } nuclear@24: nuclear@24: try { nuclear@24: meshes.push_back(m); nuclear@24: } nuclear@24: catch(...) { nuclear@24: return false; nuclear@24: } nuclear@24: nuclear@24: // invalidate facebuffer and count nuclear@24: delete [] facebuf; nuclear@24: facebuf = 0; nuclear@24: num_faces = -1; nuclear@24: nuclear@13: return true; nuclear@13: } nuclear@13: John@14: int Scene::get_num_meshes() const John@14: { John@14: return (int)meshes.size(); John@14: } John@14: nuclear@13: int Scene::get_num_faces() const nuclear@13: { nuclear@24: if(num_faces >= 0) { nuclear@24: return num_faces; nuclear@24: } nuclear@24: nuclear@24: num_faces = 0; nuclear@13: for(size_t i=0; ifaces.size(); nuclear@13: } nuclear@13: return num_faces; nuclear@13: } nuclear@13: John@14: int Scene::get_num_materials() const John@14: { John@14: return (int)matlib.size(); John@14: } John@14: John@14: Material *Scene::get_materials() John@14: { John@14: if(matlib.empty()) { John@14: return 0; John@14: } John@14: return &matlib[0]; John@14: } John@14: John@14: const Material *Scene::get_materials() const John@14: { John@14: if(matlib.empty()) { John@14: return 0; John@14: } John@14: return &matlib[0]; John@14: } nuclear@24: nuclear@24: const Face *Scene::get_face_buffer() const nuclear@24: { nuclear@24: if(facebuf) { nuclear@24: return facebuf; nuclear@24: } nuclear@24: nuclear@24: int num_meshes = get_num_meshes(); nuclear@24: nuclear@24: printf("constructing face buffer with %d faces (out of %d meshes)\n", get_num_faces(), num_meshes); nuclear@24: facebuf = new Face[num_faces]; nuclear@24: Face *fptr = facebuf; nuclear@24: nuclear@24: for(int i=0; ifaces.size(); j++) { nuclear@24: *fptr++ = meshes[i]->faces[j]; nuclear@24: } nuclear@24: } nuclear@24: return facebuf; nuclear@24: } nuclear@24: nuclear@24: nuclear@27: void Scene::draw_kdtree() const nuclear@27: { nuclear@27: glPushAttrib(GL_ENABLE_BIT); nuclear@27: glDisable(GL_LIGHTING); nuclear@27: glDepthMask(0); nuclear@27: nuclear@27: glBegin(GL_LINES); nuclear@27: ::draw_kdtree(kdtree, 0); nuclear@27: glEnd(); nuclear@27: nuclear@27: glDepthMask(1); nuclear@27: glPopAttrib(); nuclear@27: } nuclear@27: nuclear@27: static float palette[][3] = { nuclear@27: {0, 1, 0}, nuclear@27: {0, 1, 0}, nuclear@27: {0, 1, 0}, nuclear@27: {1, 0, 0}, nuclear@27: {1, 0, 0}, nuclear@27: {1, 0, 0}, nuclear@27: {0, 0, 1}, nuclear@27: {0, 0, 1}, nuclear@27: {0, 0, 1}, nuclear@27: {1, 1, 0}, nuclear@27: {1, 1, 0}, nuclear@27: {1, 1, 0}, nuclear@27: {0, 0, 1}, nuclear@27: {0, 0, 1}, nuclear@27: {0, 0, 1}, nuclear@27: {1, 0, 1}, nuclear@27: {1, 0, 1}, nuclear@27: {1, 0, 1} nuclear@27: }; nuclear@27: static int pal_size = sizeof palette / sizeof *palette; nuclear@27: nuclear@27: static void draw_kdtree(const KDNode *node, int level) nuclear@27: { nuclear@27: if(!node) return; nuclear@27: nuclear@27: draw_kdtree(node->left, level + 1); nuclear@27: draw_kdtree(node->right, level + 1); nuclear@27: nuclear@27: glColor3fv(palette[level % pal_size]); nuclear@27: nuclear@27: glVertex3fv(node->aabb.min); nuclear@27: glVertex3f(node->aabb.max[0], node->aabb.min[1], node->aabb.min[2]); nuclear@27: glVertex3f(node->aabb.max[0], node->aabb.min[1], node->aabb.min[2]); nuclear@27: glVertex3f(node->aabb.max[0], node->aabb.max[1], node->aabb.min[2]); nuclear@27: glVertex3f(node->aabb.max[0], node->aabb.max[1], node->aabb.min[2]); nuclear@27: glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.min[2]); nuclear@27: glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.min[2]); nuclear@27: glVertex3fv(node->aabb.min); nuclear@27: nuclear@27: glVertex3f(node->aabb.min[0], node->aabb.min[1], node->aabb.max[2]); nuclear@27: glVertex3f(node->aabb.max[0], node->aabb.min[1], node->aabb.max[2]); nuclear@27: glVertex3f(node->aabb.max[0], node->aabb.min[1], node->aabb.max[2]); nuclear@27: glVertex3fv(node->aabb.max); nuclear@27: glVertex3fv(node->aabb.max); nuclear@27: glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.max[2]); nuclear@27: glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.max[2]); nuclear@27: glVertex3f(node->aabb.min[0], node->aabb.min[1], node->aabb.max[2]); nuclear@27: nuclear@27: glVertex3fv(node->aabb.min); nuclear@27: glVertex3f(node->aabb.min[0], node->aabb.min[1], node->aabb.max[2]); nuclear@27: glVertex3f(node->aabb.max[0], node->aabb.min[1], node->aabb.min[2]); nuclear@27: glVertex3f(node->aabb.max[0], node->aabb.min[1], node->aabb.max[2]); nuclear@27: glVertex3f(node->aabb.max[0], node->aabb.max[1], node->aabb.min[2]); nuclear@27: glVertex3fv(node->aabb.max); nuclear@27: glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.min[2]); nuclear@27: glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.max[2]); nuclear@27: } nuclear@27: nuclear@27: bool Scene::build_kdtree() nuclear@24: { nuclear@24: const Face *faces = get_face_buffer(); nuclear@24: int num_faces = get_num_faces(); nuclear@24: nuclear@25: printf("Constructing kd-tree out of %d faces ...\n", num_faces); nuclear@25: nuclear@27: int icost = accel_param[ACCEL_PARAM_COST_INTERSECT]; nuclear@27: int tcost = accel_param[ACCEL_PARAM_COST_TRAVERSE]; nuclear@27: printf(" max items per leaf: %d\n", accel_param[ACCEL_PARAM_MAX_NODE_ITEMS]); nuclear@27: printf(" SAH parameters - tcost: %d - icost: %d\n", tcost, icost); nuclear@27: nuclear@25: free_kdtree(kdtree); nuclear@25: kdtree = new KDNode; nuclear@25: nuclear@25: /* Start the construction of the kdtree by adding all faces of the scene nuclear@25: * to the new root node. At the same time calculate the root's AABB. nuclear@25: */ nuclear@25: kdtree->aabb.min[0] = kdtree->aabb.min[1] = kdtree->aabb.min[2] = FLT_MAX; nuclear@25: kdtree->aabb.max[0] = kdtree->aabb.max[1] = kdtree->aabb.max[2] = -FLT_MAX; nuclear@25: nuclear@24: for(int i=0; iv[j].pos; nuclear@25: nuclear@25: // for each element (xyz) of the position vector ... nuclear@25: for(int k=0; k<3; k++) { nuclear@25: if(pos[k] < kdtree->aabb.min[k]) { nuclear@25: kdtree->aabb.min[k] = pos[k]; nuclear@25: } nuclear@25: if(pos[k] > kdtree->aabb.max[k]) { nuclear@25: kdtree->aabb.max[k] = pos[k]; nuclear@25: } nuclear@25: } nuclear@25: } nuclear@25: nuclear@25: kdtree->faces.push_back(face); // add the face nuclear@26: kdtree->num_faces++; nuclear@24: } nuclear@24: nuclear@26: // calculate the heuristic for the root nuclear@26: kdtree->cost = eval_cost(kdtree->faces, kdtree->aabb, kdtree->axis); nuclear@26: nuclear@25: // now proceed splitting the root recursively nuclear@27: if(!::build_kdtree(kdtree)) { nuclear@27: fprintf(stderr, "failed to build kdtree\n"); nuclear@27: return false; nuclear@27: } nuclear@27: nuclear@27: printf(" tree depth: %d\n", kdtree_depth(kdtree)); nuclear@27: print_item_counts(kdtree, 0); nuclear@27: return true; nuclear@24: } nuclear@24: nuclear@27: static bool build_kdtree(KDNode *kd, int level) nuclear@24: { nuclear@26: int opt_max_items = accel_param[ACCEL_PARAM_MAX_NODE_ITEMS]; nuclear@27: int tcost = accel_param[ACCEL_PARAM_COST_TRAVERSE]; nuclear@27: nuclear@27: if(kd->num_faces == 0) { nuclear@27: return true; nuclear@25: } nuclear@25: nuclear@27: int axis = level % 3; nuclear@27: //float parent_sa = kd->aabb.calc_surface_area(); nuclear@26: nuclear@26: float best_cost[2], best_sum_cost = FLT_MAX; nuclear@26: float best_split; nuclear@26: nuclear@26: std::list::iterator it = kd->faces.begin(); nuclear@26: while(it != kd->faces.end()) { nuclear@26: const Face *face = *it++; nuclear@26: nuclear@26: for(int i=0; i<3; i++) { nuclear@26: AABBox aabb_left, aabb_right; nuclear@26: const float *split = face->v[i].pos; nuclear@26: nuclear@26: aabb_left = aabb_right = kd->aabb; nuclear@26: aabb_left.max[axis] = split[axis]; nuclear@26: aabb_right.min[axis] = split[axis]; nuclear@26: nuclear@26: float left_cost = eval_cost(kd->faces, aabb_left, axis); nuclear@26: float right_cost = eval_cost(kd->faces, aabb_right, axis); nuclear@27: float sum_cost = left_cost + right_cost - tcost; // tcost is added twice nuclear@26: nuclear@26: if(sum_cost < best_sum_cost) { nuclear@26: best_cost[0] = left_cost; nuclear@26: best_cost[1] = right_cost; nuclear@26: best_sum_cost = sum_cost; nuclear@26: best_split = split[axis]; nuclear@26: } nuclear@26: } nuclear@26: } nuclear@26: nuclear@27: printf("current cost: %f, best_cost: %f\n", kd->cost, best_sum_cost); nuclear@27: if(best_sum_cost > kd->cost && (opt_max_items == 0 || kd->num_faces <= opt_max_items)) { nuclear@27: return true; // stop splitting if it doesn't reduce the cost nuclear@26: } nuclear@26: kd->pt = best_split; nuclear@26: nuclear@26: // create the two children nuclear@26: KDNode *kdleft, *kdright; nuclear@26: kdleft = new KDNode; nuclear@26: kdright = new KDNode; nuclear@26: nuclear@26: kdleft->aabb = kdright->aabb = kd->aabb; nuclear@26: nuclear@26: kdleft->aabb.max[axis] = best_split; nuclear@26: kdright->aabb.min[axis] = best_split; nuclear@26: nuclear@26: kdleft->cost = best_cost[0]; nuclear@26: kdright->cost = best_cost[1]; nuclear@26: nuclear@27: //kdleft->axis = kdright->axis = (axis + 1) % 3; nuclear@27: nuclear@26: it = kd->faces.begin(); nuclear@26: while(it != kd->faces.end()) { nuclear@26: const Face *face = *it++; nuclear@26: nuclear@26: if(face->v[0].pos[axis] < best_split || nuclear@26: face->v[1].pos[axis] < best_split || nuclear@26: face->v[2].pos[axis] < best_split) { nuclear@26: kdleft->faces.push_back(face); nuclear@26: kdleft->num_faces++; nuclear@26: } nuclear@26: if(face->v[0].pos[axis] >= best_split || nuclear@26: face->v[1].pos[axis] >= best_split || nuclear@26: face->v[2].pos[axis] >= best_split) { nuclear@26: kdright->faces.push_back(face); nuclear@26: kdright->num_faces++; nuclear@26: } nuclear@26: } nuclear@27: kd->faces.clear(); // only leaves have faces nuclear@26: nuclear@26: kd->left = kdleft; nuclear@26: kd->right = kdright; nuclear@27: nuclear@27: return build_kdtree(kd->left, level + 1) && build_kdtree(kd->right, level + 1); nuclear@26: } nuclear@26: nuclear@27: static float eval_cost(const std::list &faces, const AABBox &aabb, int axis, float par_sarea) nuclear@26: { nuclear@26: int num_inside = 0; nuclear@26: int tcost = accel_param[ACCEL_PARAM_COST_TRAVERSE]; nuclear@26: int icost = accel_param[ACCEL_PARAM_COST_INTERSECT]; nuclear@26: nuclear@26: std::list::const_iterator it = faces.begin(); nuclear@26: while(it != faces.end()) { nuclear@26: const Face *face = *it++; nuclear@26: nuclear@26: for(int i=0; i<3; i++) { nuclear@26: if(face->v[i].pos[axis] >= aabb.min[axis] && face->v[i].pos[axis] < aabb.max[axis]) { nuclear@26: num_inside++; nuclear@26: break; nuclear@26: } nuclear@26: } nuclear@26: } nuclear@26: nuclear@27: float sarea = aabb.calc_surface_area(); nuclear@27: if(sarea < 1e-8) { nuclear@27: return FLT_MAX; // heavily penalize 0-area voxels nuclear@27: } nuclear@27: nuclear@27: return tcost + (sarea / par_sarea) * num_inside * icost; nuclear@24: } nuclear@25: nuclear@25: static void free_kdtree(KDNode *node) nuclear@25: { nuclear@25: if(node) { nuclear@25: free_kdtree(node->left); nuclear@25: free_kdtree(node->right); nuclear@25: delete node; nuclear@25: } nuclear@25: } nuclear@27: nuclear@27: static int kdtree_depth(const KDNode *node) nuclear@27: { nuclear@27: if(!node) return 0; nuclear@27: nuclear@27: int left = kdtree_depth(node->left); nuclear@27: int right = kdtree_depth(node->right); nuclear@27: return (left > right ? left : right) + 1; nuclear@27: } nuclear@27: nuclear@27: static void print_item_counts(const KDNode *node, int level) nuclear@27: { nuclear@27: if(!node) return; nuclear@27: nuclear@27: for(int i=0; inum_faces, node->cost); nuclear@27: nuclear@27: print_item_counts(node->left, level + 1); nuclear@27: print_item_counts(node->right, level + 1); nuclear@27: }