clray: 7d77ded5f890 src/scene.cc

clray

view src/scene.cc @ 35:7d77ded5f890

stopped using a heap to flatten the kdtree. added explicit left/right indices

author	John Tsiombikas <nuclear@member.fsf.org>
date	Thu, 26 Aug 2010 20:24:07 +0100
parents	4cf4919c3812
children	4dec8853bf75

line source

1 #include <stdlib.h>

2 #include <math.h>

3 #include <float.h>

4 #include <assert.h>

5 #include <map>

6 #include "scene.h"

7 #include "ogl.h"

10 static void flatten_kdtree(const KDNode *node, KDNodeGPU *kdbuf, int *count, std::map<const KDNode*, int> *flatmap);

11 static void fix_child_links(const KDNode *node, KDNodeGPU *kdbuf, const std::map<const KDNode*, int> &flatmap);

12 static void draw_kdtree(const KDNode *node, int level = 0);

13 static bool build_kdtree(KDNode *kd, const Face *faces, int level = 0);

14 static float eval_cost(const Face *faces, const int *face_idx, int num_faces, const AABBox &aabb, int axis);

15 static void free_kdtree(KDNode *node);

16 static void print_item_counts(const KDNode *node, int level);

19 static int accel_param[NUM_ACCEL_PARAMS] = {

20 40, // max tree depth

21 0, // max items per node (0 means ignore limit)

22 5, // estimated traversal cost

23 15 // estimated interseciton cost

24 };

27 void set_accel_param(int p, int v)

28 {

29 assert(p >= 0 && p < NUM_ACCEL_PARAMS);

30 accel_param[p] = v;

31 }

34 #define FEQ(a, b) (fabs((a) - (b)) < 1e-8)

35 bool Face::operator ==(const Face &f) const

36 {

37 for(int i=0; i<3; i++) {

38 for(int j=0; j<3; j++) {

39 if(!FEQ(v[i].pos[j], f.v[i].pos[j])) {

40 return false;

41 }

42 if(!FEQ(v[i].normal[j], f.v[i].normal[j])) {

43 return false;

44 }

45 }

46 if(!FEQ(normal[i], f.normal[i])) {

47 return false;

48 }

49 }

50 return true;

51 }

53 float AABBox::calc_surface_area() const

54 {

55 float area1 = (max[0] - min[0]) * (max[1] - min[1]);

56 float area2 = (max[3] - min[3]) * (max[1] - min[1]);

57 float area3 = (max[0] - min[0]) * (max[3] - min[3]);

59 return 2.0f * (area1 + area2 + area3);

60 }

62 KDNode::KDNode()

63 {

64 left = right = 0;

65 cost = 0.0;

66 }

69 Scene::Scene()

70 {

71 facebuf = 0;

72 num_faces = -1;

73 kdtree = 0;

74 kdbuf = 0;

75 }

77 Scene::~Scene()

78 {

79 delete [] facebuf;

80 delete [] kdbuf;

81 free_kdtree(kdtree);

82 }

84 bool Scene::add_mesh(Mesh *m)

85 {

86 // make sure triangles have material ids

87 for(size_t i=0; i<m->faces.size(); i++) {

88 m->faces[i].matid = m->matid;

89 }

91 try {

92 meshes.push_back(m);

93 }

94 catch(...) {

95 return false;

96 }

98 // invalidate facebuffer and count

99 delete [] facebuf;

100 facebuf = 0;

101 num_faces = -1;

102

103 return true;

104 }

105

106 int Scene::get_num_meshes() const

107 {

108 return (int)meshes.size();

109 }

110

111 int Scene::get_num_faces() const

112 {

113 if(num_faces >= 0) {

114 return num_faces;

115 }

116

117 num_faces = 0;

118 for(size_t i=0; i<meshes.size(); i++) {

119 num_faces += meshes[i]->faces.size();

120 }

121 return num_faces;

122 }

123

124 int Scene::get_num_materials() const

125 {

126 return (int)matlib.size();

127 }

128

129 int Scene::get_num_kdnodes() const

130 {

131 return kdtree_nodes(kdtree);

132 }

133

134 Material *Scene::get_materials()

135 {

136 if(matlib.empty()) {

137 return 0;

138 }

139 return &matlib[0];

140 }

141

142 const Material *Scene::get_materials() const

143 {

144 if(matlib.empty()) {

145 return 0;

146 }

147 return &matlib[0];

148 }

149

150 const Face *Scene::get_face_buffer() const

151 {

152 if(facebuf) {

153 return facebuf;

154 }

155

156 int num_meshes = get_num_meshes();

157

158 printf("constructing face buffer with %d faces (out of %d meshes)\n", get_num_faces(), num_meshes);

159 facebuf = new Face[num_faces];

160 Face *fptr = facebuf;

161

162 for(int i=0; i<num_meshes; i++) {

163 for(size_t j=0; j<meshes[i]->faces.size(); j++) {

164 *fptr++ = meshes[i]->faces[j];

165 }

166 }

167 return facebuf;

168 }

169

170 static int find_node_index(const KDNode *node, const std::map<const KDNode*, int> &flatmap);

171

172 static bool validate_flat_tree(const KDNode *node, const KDNodeGPU *kdbuf, int count, const std::map<const KDNode*, int> &flatmap)

173 {

174 if(!node) return true;

175

176 int idx = find_node_index(node, flatmap);

177 int left_idx = find_node_index(node->left, flatmap);

178 int right_idx = find_node_index(node->right, flatmap);

179

180 if(kdbuf[idx].left != left_idx) {

181 fprintf(stderr, "%d's left should be %d. it's: %d\n", idx, left_idx, kdbuf[idx].left);

182 return false;

183 }

184 if(kdbuf[idx].right != right_idx) {

185 fprintf(stderr, "%d's right should be %d. it's: %d\n", idx, right_idx, kdbuf[idx].right);

186 return false;

187 }

188 return validate_flat_tree(node->left, kdbuf, count, flatmap) && validate_flat_tree(node->right, kdbuf, count, flatmap);

189 }

190

191 const KDNodeGPU *Scene::get_kdtree_buffer() const

192 {

193 if(kdbuf) {

194 return kdbuf;

195 }

196

197 if(!kdtree) {

198 ((Scene*)this)->build_kdtree();

199 }

200

201 /* we'll associate kdnodes with flattened array indices through this map as

202 * we add them so that the second child-index pass, will be able to find

203 * the children indices of each node.

204 */

205 std::map<const KDNode*, int> flatmap;

206 flatmap[0] = -1;

207

208 int num_nodes = get_num_kdnodes();

209 kdbuf = new KDNodeGPU[num_nodes];

210

211 int count = 0;

212

213 // first arrange the kdnodes into an array (flatten)

214 flatten_kdtree(kdtree, kdbuf, &count, &flatmap);

215

216 // then fix all the left/right links to point to the correct nodes

217 fix_child_links(kdtree, kdbuf, flatmap);

218

219 assert(validate_flat_tree(kdtree, kdbuf, count, flatmap));

220

221 return kdbuf;

222 }

223

224 static void flatten_kdtree(const KDNode *node, KDNodeGPU *kdbuf, int *count, std::map<const KDNode*, int> *flatmap)

225 {

226 int idx = (*count)++;

227

228 // copy the node

229 kdbuf[idx].aabb = node->aabb;

230 for(size_t i=0; i<node->face_idx.size(); i++) {

231 kdbuf[idx].face_idx[i] = node->face_idx[i];

232 }

233 kdbuf[idx].num_faces = node->face_idx.size();

234

235 // update the node* -> array-position mapping

236 (*flatmap)[node] = idx;

237

238 // recurse to the left/right (if we're not in a leaf node)

239 if(node->left) {

240 assert(node->right);

241

242 flatten_kdtree(node->left, kdbuf, count, flatmap);

243 flatten_kdtree(node->right, kdbuf, count, flatmap);

244 }

245 }

246

247 static int find_node_index(const KDNode *node, const std::map<const KDNode*, int> &flatmap)

248 {

249 std::map<const KDNode*, int>::const_iterator it = flatmap.find(node);

250 assert(it != flatmap.end());

251 return it->second;

252 }

253

254 static void fix_child_links(const KDNode *node, KDNodeGPU *kdbuf, const std::map<const KDNode*, int> &flatmap)

255 {

256 if(!node) return;

257

258 int idx = find_node_index(node, flatmap);

259

260 kdbuf[idx].left = find_node_index(node->left, flatmap);

261 if(!node->left && kdbuf[idx].left != -1) abort();

262 kdbuf[idx].right = find_node_index(node->right, flatmap);

263 if(!node->right && kdbuf[idx].right != -1) abort();

264

265 fix_child_links(node->left, kdbuf, flatmap);

266 fix_child_links(node->right, kdbuf, flatmap);

267 }

268

269 void Scene::draw_kdtree() const

270 {

271 glPushAttrib(GL_ENABLE_BIT);

272 glDisable(GL_LIGHTING);

273 glDepthMask(0);

274

275 glBegin(GL_LINES);

276 ::draw_kdtree(kdtree, 0);

277 glEnd();

278

279 glDepthMask(1);

280 glPopAttrib();

281 }

282

283 static float palette[][3] = {

284 {0, 1, 0},

285 {1, 0, 0},

286 {0, 0, 1},

287 {1, 1, 0},

288 {0, 0, 1},

289 {1, 0, 1}

290 };

291 static int pal_size = sizeof palette / sizeof *palette;

292

293 static void draw_kdtree(const KDNode *node, int level)

294 {

295 if(!node) return;

296

297 draw_kdtree(node->left, level + 1);

298 draw_kdtree(node->right, level + 1);

299

300 glColor3fv(palette[level % pal_size]);

301

302 glVertex3fv(node->aabb.min);

303 glVertex3f(node->aabb.max[0], node->aabb.min[1], node->aabb.min[2]);

304 glVertex3f(node->aabb.max[0], node->aabb.min[1], node->aabb.min[2]);

305 glVertex3f(node->aabb.max[0], node->aabb.max[1], node->aabb.min[2]);

306 glVertex3f(node->aabb.max[0], node->aabb.max[1], node->aabb.min[2]);

307 glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.min[2]);

308 glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.min[2]);

309 glVertex3fv(node->aabb.min);

310

311 glVertex3f(node->aabb.min[0], node->aabb.min[1], node->aabb.max[2]);

312 glVertex3f(node->aabb.max[0], node->aabb.min[1], node->aabb.max[2]);

313 glVertex3f(node->aabb.max[0], node->aabb.min[1], node->aabb.max[2]);

314 glVertex3fv(node->aabb.max);

315 glVertex3fv(node->aabb.max);

316 glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.max[2]);

317 glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.max[2]);

318 glVertex3f(node->aabb.min[0], node->aabb.min[1], node->aabb.max[2]);

319

320 glVertex3fv(node->aabb.min);

321 glVertex3f(node->aabb.min[0], node->aabb.min[1], node->aabb.max[2]);

322 glVertex3f(node->aabb.max[0], node->aabb.min[1], node->aabb.min[2]);

323 glVertex3f(node->aabb.max[0], node->aabb.min[1], node->aabb.max[2]);

324 glVertex3f(node->aabb.max[0], node->aabb.max[1], node->aabb.min[2]);

325 glVertex3fv(node->aabb.max);

326 glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.min[2]);

327 glVertex3f(node->aabb.min[0], node->aabb.max[1], node->aabb.max[2]);

328 }

329

330 bool Scene::build_kdtree()

331 {

332 assert(kdtree == 0);

333

334 const Face *faces = get_face_buffer();

335 int num_faces = get_num_faces();

336

337 printf("Constructing kd-tree out of %d faces ...\n", num_faces);

338

339 int icost = accel_param[ACCEL_PARAM_COST_INTERSECT];

340 int tcost = accel_param[ACCEL_PARAM_COST_TRAVERSE];

341 printf(" max items per leaf: %d\n", accel_param[ACCEL_PARAM_MAX_NODE_ITEMS]);

342 printf(" SAH parameters - tcost: %d - icost: %d\n", tcost, icost);

343

344 free_kdtree(kdtree);

345 kdtree = new KDNode;

346

347 /* Start the construction of the kdtree by adding all faces of the scene

348 * to the new root node. At the same time calculate the root's AABB.

349 */

350 kdtree->aabb.min[0] = kdtree->aabb.min[1] = kdtree->aabb.min[2] = FLT_MAX;

351 kdtree->aabb.max[0] = kdtree->aabb.max[1] = kdtree->aabb.max[2] = -FLT_MAX;

352

353 for(int i=0; i<num_faces; i++) {

354 const Face *face = faces + i;

355

356 // for each vertex of the face ...

357 for(int j=0; j<3; j++) {

358 const float *pos = face->v[j].pos;

359

360 // for each element (xyz) of the position vector ...

361 for(int k=0; k<3; k++) {

362 if(pos[k] < kdtree->aabb.min[k]) {

363 kdtree->aabb.min[k] = pos[k];

364 }

365 if(pos[k] > kdtree->aabb.max[k]) {

366 kdtree->aabb.max[k] = pos[k];

367 }

368 }

369 }

370

371 kdtree->face_idx.push_back(i); // add the face

372 }

373

374 // calculate the heuristic for the root

375 kdtree->cost = eval_cost(faces, &kdtree->face_idx[0], kdtree->face_idx.size(), kdtree->aabb, 0);

376

377 // now proceed splitting the root recursively

378 if(!::build_kdtree(kdtree, faces)) {

379 fprintf(stderr, "failed to build kdtree\n");

380 return false;

381 }

382

383 printf(" tree depth: %d\n", kdtree_depth(kdtree));

384 print_item_counts(kdtree, 0);

385 return true;

386 }

387

388 static bool build_kdtree(KDNode *kd, const Face *faces, int level)

389 {

390 int opt_max_depth = accel_param[ACCEL_PARAM_MAX_TREE_DEPTH];

391 int opt_max_items = accel_param[ACCEL_PARAM_MAX_NODE_ITEMS];

392 int tcost = accel_param[ACCEL_PARAM_COST_TRAVERSE];

393

394 if(kd->face_idx.empty() || level >= opt_max_depth) {

395 return true;

396 }

397

398 int axis = level % 3;

399

400 float best_cost[2], best_sum_cost = FLT_MAX;

401 float best_split;

402

403 for(size_t i=0; i<kd->face_idx.size(); i++) {

404 const Face *face = faces + kd->face_idx[i];

405

406 for(int j=0; j<3; j++) {

407 AABBox aabb_left, aabb_right;

408 const float *split = face->v[j].pos;

409

410 aabb_left = aabb_right = kd->aabb;

411 aabb_left.max[axis] = split[axis];

412 aabb_right.min[axis] = split[axis];

413

414 float left_cost = eval_cost(faces, &kd->face_idx[0], kd->face_idx.size(), aabb_left, axis);

415 float right_cost = eval_cost(faces, &kd->face_idx[0], kd->face_idx.size(), aabb_right, axis);

416 float sum_cost = left_cost + right_cost - tcost; // tcost is added twice

417

418 if(sum_cost < best_sum_cost) {

419 best_cost[0] = left_cost;

420 best_cost[1] = right_cost;

421 best_sum_cost = sum_cost;

422 best_split = split[axis];

423 }

424 }

425 }

426

427 //printf("current cost: %f, best_cost: %f\n", kd->cost, best_sum_cost);

428 if(best_sum_cost > kd->cost && (opt_max_items == 0 || (int)kd->face_idx.size() <= opt_max_items)) {

429 return true; // stop splitting if it doesn't reduce the cost

430 }

431

432 // create the two children

433 KDNode *kdleft, *kdright;

434 kdleft = new KDNode;

435 kdright = new KDNode;

436

437 kdleft->aabb = kdright->aabb = kd->aabb;

438

439 kdleft->aabb.max[axis] = best_split;

440 kdright->aabb.min[axis] = best_split;

441

442 kdleft->cost = best_cost[0];

443 kdright->cost = best_cost[1];

444

445 for(size_t i=0; i<kd->face_idx.size(); i++) {

446 int fidx = kd->face_idx[i];

447 const Face *face = faces + fidx;

448

449 if(face->v[0].pos[axis] < best_split ||

450 face->v[1].pos[axis] < best_split ||

451 face->v[2].pos[axis] < best_split) {

452 kdleft->face_idx.push_back(fidx);

453 }

454 if(face->v[0].pos[axis] >= best_split ||

455 face->v[1].pos[axis] >= best_split ||

456 face->v[2].pos[axis] >= best_split) {

457 kdright->face_idx.push_back(fidx);

458 }

459 }

460 kd->face_idx.clear(); // only leaves have faces

461

462 kd->left = kdleft;

463 kd->right = kdright;

464

465 return build_kdtree(kd->left, faces, level + 1) && build_kdtree(kd->right, faces, level + 1);

466 }

467

468 static float eval_cost(const Face *faces, const int *face_idx, int num_faces, const AABBox &aabb, int axis)

469 {

470 int num_inside = 0;

471 int tcost = accel_param[ACCEL_PARAM_COST_TRAVERSE];

472 int icost = accel_param[ACCEL_PARAM_COST_INTERSECT];

473

474 for(int i=0; i<num_faces; i++) {

475 const Face *face = faces + face_idx[i];

476

477 for(int j=0; j<3; j++) {

478 if(face->v[j].pos[axis] >= aabb.min[axis] && face->v[j].pos[axis] < aabb.max[axis]) {

479 num_inside++;

480 break;

481 }

482 }

483 }

484

485 float sarea = aabb.calc_surface_area();

486 if(sarea < 1e-8) {

487 return FLT_MAX; // heavily penalize 0-area voxels

488 }

489

490 return tcost + sarea * num_inside * icost;

491 }

492

493 static void free_kdtree(KDNode *node)

494 {

495 if(node) {

496 free_kdtree(node->left);

497 free_kdtree(node->right);

498 delete node;

499 }

500 }

501

502 int kdtree_depth(const KDNode *node)

503 {

504 if(!node) return 0;

505

506 int left = kdtree_depth(node->left);

507 int right = kdtree_depth(node->right);

508 return (left > right ? left : right) + 1;

509 }

510

511 int kdtree_nodes(const KDNode *node)

512 {

513 if(!node) return 0;

514 return kdtree_nodes(node->left) + kdtree_nodes(node->right) + 1;

515 }

516

517 static void print_item_counts(const KDNode *node, int level)

518 {

519 if(!node) return;

520

521 for(int i=0; i<level; i++) {

522 fputs(" ", stdout);

523 }

524 printf("- %d (cost: %f)\n", (int)node->face_idx.size(), node->cost);

525

526 print_item_counts(node->left, level + 1);

527 print_item_counts(node->right, level + 1);

528 }