clray
changeset 37:ca445da26588
out of resources?!
| author | John Tsiombikas <nuclear@member.fsf.org> |
|---|---|
| date | Fri, 27 Aug 2010 01:00:04 +0100 |
| parents | 4dec8853bf75 |
| children | 4bcf78e572d6 |
| files | src/scene.cc src/scene.h |
| diffstat | 2 files changed, 70 insertions(+), 38 deletions(-) [+] |
line diff
1.1 --- a/src/scene.cc Thu Aug 26 20:33:27 2010 +0100 1.2 +++ b/src/scene.cc Fri Aug 27 01:00:04 2010 +0100 1.3 @@ -7,6 +7,10 @@ 1.4 #include "ogl.h" 1.5 1.6 1.7 +#define MIN(a, b) ((a) < (b) ? (a) : (b)) 1.8 +#define MAX(a, b) ((a) > (b) ? (a) : (b)) 1.9 + 1.10 + 1.11 static void flatten_kdtree(const KDNode *node, KDNodeGPU *kdbuf, int *count, std::map<const KDNode*, int> *flatmap); 1.12 static void fix_child_links(const KDNode *node, KDNodeGPU *kdbuf, const std::map<const KDNode*, int> &flatmap); 1.13 static void draw_kdtree(const KDNode *node, int level = 0); 1.14 @@ -341,7 +345,7 @@ 1.15 glVertex3f(bleft->max[0], bleft->min[1], bleft->max[2]); 1.16 glVertex3f(bleft->max[0], bleft->min[1], bleft->min[2]); 1.17 break; 1.18 - 1.19 + 1.20 case 1: 1.21 glVertex3f(bleft->min[0], bleft->min[1], bleft->max[2]); 1.22 glVertex3f(bleft->min[0], bleft->max[1], bleft->max[2]); 1.23 @@ -352,7 +356,7 @@ 1.24 glVertex3f(bleft->max[0], bleft->min[1], bleft->max[2]); 1.25 glVertex3f(bleft->min[0], bleft->min[1], bleft->max[2]); 1.26 break; 1.27 - 1.28 + 1.29 case 2: 1.30 glVertex3f(bleft->min[0], bleft->max[1], bleft->min[2]); 1.31 glVertex3f(bleft->max[0], bleft->max[1], bleft->min[2]); 1.32 @@ -427,47 +431,74 @@ 1.33 return true; 1.34 } 1.35 1.36 +struct Split { 1.37 + int axis; 1.38 + float pos; 1.39 + float sum_cost; 1.40 + float cost_left, cost_right; 1.41 +}; 1.42 + 1.43 +static void find_best_split(const KDNode *node, int axis, const Face *faces, Split *split) 1.44 +{ 1.45 + Split best_split; 1.46 + best_split.sum_cost = FLT_MAX; 1.47 + 1.48 + for(size_t i=0; i<node->face_idx.size(); i++) { 1.49 + const Face *face = faces + node->face_idx[i]; 1.50 + 1.51 + float splitpt[2]; 1.52 + splitpt[0] = MIN(face->v[0].pos[axis], MIN(face->v[1].pos[axis], face->v[2].pos[axis])); 1.53 + splitpt[1] = MAX(face->v[0].pos[axis], MAX(face->v[1].pos[axis], face->v[2].pos[axis])); 1.54 + 1.55 + for(int j=0; j<2; j++) { 1.56 + AABBox aabb_left, aabb_right; 1.57 + aabb_left = aabb_right = node->aabb; 1.58 + aabb_left.max[axis] = splitpt[j]; 1.59 + aabb_right.min[axis] = splitpt[j]; 1.60 + 1.61 + float left_cost = eval_cost(faces, &node->face_idx[0], node->face_idx.size(), aabb_left, axis); 1.62 + float right_cost = eval_cost(faces, &node->face_idx[0], node->face_idx.size(), aabb_right, axis); 1.63 + float sum_cost = left_cost + right_cost - accel_param[ACCEL_PARAM_COST_TRAVERSE]; // tcost is added twice 1.64 + 1.65 + if(sum_cost < best_split.sum_cost) { 1.66 + best_split.cost_left = left_cost; 1.67 + best_split.cost_right = right_cost; 1.68 + best_split.sum_cost = sum_cost; 1.69 + best_split.pos = splitpt[j]; 1.70 + } 1.71 + } 1.72 + } 1.73 + 1.74 + assert(split); 1.75 + *split = best_split; 1.76 + split->axis = axis; 1.77 +} 1.78 + 1.79 static bool build_kdtree(KDNode *kd, const Face *faces, int level) 1.80 { 1.81 int opt_max_depth = accel_param[ACCEL_PARAM_MAX_TREE_DEPTH]; 1.82 int opt_max_items = accel_param[ACCEL_PARAM_MAX_NODE_ITEMS]; 1.83 - int tcost = accel_param[ACCEL_PARAM_COST_TRAVERSE]; 1.84 1.85 if(kd->face_idx.empty() || level >= opt_max_depth) { 1.86 return true; 1.87 } 1.88 1.89 - int axis = level % 3; 1.90 + Split best_split; 1.91 + best_split.sum_cost = FLT_MAX; 1.92 1.93 - float best_cost[2], best_sum_cost = FLT_MAX; 1.94 - float best_split; 1.95 + for(int i=0; i<1; i++) { 1.96 + Split split; 1.97 + find_best_split(kd, i, faces, &split); 1.98 1.99 - for(size_t i=0; i<kd->face_idx.size(); i++) { 1.100 - const Face *face = faces + kd->face_idx[i]; 1.101 - 1.102 - for(int j=0; j<3; j++) { 1.103 - AABBox aabb_left, aabb_right; 1.104 - const float *split = face->v[j].pos; 1.105 - 1.106 - aabb_left = aabb_right = kd->aabb; 1.107 - aabb_left.max[axis] = split[axis]; 1.108 - aabb_right.min[axis] = split[axis]; 1.109 - 1.110 - float left_cost = eval_cost(faces, &kd->face_idx[0], kd->face_idx.size(), aabb_left, axis); 1.111 - float right_cost = eval_cost(faces, &kd->face_idx[0], kd->face_idx.size(), aabb_right, axis); 1.112 - float sum_cost = left_cost + right_cost - tcost; // tcost is added twice 1.113 - 1.114 - if(sum_cost < best_sum_cost) { 1.115 - best_cost[0] = left_cost; 1.116 - best_cost[1] = right_cost; 1.117 - best_sum_cost = sum_cost; 1.118 - best_split = split[axis]; 1.119 - } 1.120 + if(split.sum_cost < best_split.sum_cost) { 1.121 + best_split = split; 1.122 } 1.123 } 1.124 1.125 + kd->axis = best_split.axis; 1.126 + 1.127 //printf("current cost: %f, best_cost: %f\n", kd->cost, best_sum_cost); 1.128 - if(best_sum_cost > kd->cost && (opt_max_items == 0 || (int)kd->face_idx.size() <= opt_max_items)) { 1.129 + if(best_split.sum_cost > kd->cost && (opt_max_items == 0 || (int)kd->face_idx.size() <= opt_max_items)) { 1.130 return true; // stop splitting if it doesn't reduce the cost 1.131 } 1.132 1.133 @@ -478,25 +509,25 @@ 1.134 1.135 kdleft->aabb = kdright->aabb = kd->aabb; 1.136 1.137 - kdleft->aabb.max[axis] = best_split; 1.138 - kdright->aabb.min[axis] = best_split; 1.139 + kdleft->aabb.max[kd->axis] = best_split.pos; 1.140 + kdright->aabb.min[kd->axis] = best_split.pos; 1.141 1.142 - kdleft->cost = best_cost[0]; 1.143 - kdright->cost = best_cost[1]; 1.144 + kdleft->cost = best_split.cost_left; 1.145 + kdright->cost = best_split.cost_right; 1.146 1.147 // TODO would it be much better if we actually split faces that straddle the splitting plane? 1.148 for(size_t i=0; i<kd->face_idx.size(); i++) { 1.149 int fidx = kd->face_idx[i]; 1.150 const Face *face = faces + fidx; 1.151 1.152 - if(face->v[0].pos[axis] < best_split || 1.153 - face->v[1].pos[axis] < best_split || 1.154 - face->v[2].pos[axis] < best_split) { 1.155 + if(face->v[0].pos[kd->axis] < best_split.pos || 1.156 + face->v[1].pos[kd->axis] < best_split.pos || 1.157 + face->v[2].pos[kd->axis] < best_split.pos) { 1.158 kdleft->face_idx.push_back(fidx); 1.159 } 1.160 - if(face->v[0].pos[axis] >= best_split || 1.161 - face->v[1].pos[axis] >= best_split || 1.162 - face->v[2].pos[axis] >= best_split) { 1.163 + if(face->v[0].pos[kd->axis] >= best_split.pos || 1.164 + face->v[1].pos[kd->axis] >= best_split.pos || 1.165 + face->v[2].pos[kd->axis] >= best_split.pos) { 1.166 kdright->face_idx.push_back(fidx); 1.167 } 1.168 }