clray: 4dec8853bf75 src/scene.cc

clray

view src/scene.cc @ 36:4dec8853bf75

merged

author	John Tsiombikas <nuclear@member.fsf.org>
date	Thu, 26 Aug 2010 20:33:27 +0100
parents	7d77ded5f890 a218551293ad
children	ca445da26588

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 /*if(!node->left) return;

329

330 AABBox *bleft = &node->left->aabb;

331

332 int axis = level % 3;

333 switch(axis) {

334 case 0:

335 glVertex3f(bleft->max[0], bleft->min[1], bleft->min[2]);

336 glVertex3f(bleft->max[0], bleft->max[1], bleft->min[2]);

337 glVertex3f(bleft->max[0], bleft->max[1], bleft->min[2]);

338 glVertex3f(bleft->max[0], bleft->max[1], bleft->max[2]);

339 glVertex3f(bleft->max[0], bleft->max[1], bleft->max[2]);

340 glVertex3f(bleft->max[0], bleft->min[1], bleft->max[2]);

341 glVertex3f(bleft->max[0], bleft->min[1], bleft->max[2]);

342 glVertex3f(bleft->max[0], bleft->min[1], bleft->min[2]);

343 break;

344

345 case 1:

346 glVertex3f(bleft->min[0], bleft->min[1], bleft->max[2]);

347 glVertex3f(bleft->min[0], bleft->max[1], bleft->max[2]);

348 glVertex3f(bleft->min[0], bleft->max[1], bleft->max[2]);

349 glVertex3f(bleft->max[0], bleft->max[1], bleft->max[2]);

350 glVertex3f(bleft->max[0], bleft->max[1], bleft->max[2]);

351 glVertex3f(bleft->max[0], bleft->min[1], bleft->max[2]);

352 glVertex3f(bleft->max[0], bleft->min[1], bleft->max[2]);

353 glVertex3f(bleft->min[0], bleft->min[1], bleft->max[2]);

354 break;

355

356 case 2:

357 glVertex3f(bleft->min[0], bleft->max[1], bleft->min[2]);

358 glVertex3f(bleft->max[0], bleft->max[1], bleft->min[2]);

359 glVertex3f(bleft->max[0], bleft->max[1], bleft->min[2]);

360 glVertex3f(bleft->max[0], bleft->max[1], bleft->max[2]);

361 glVertex3f(bleft->max[0], bleft->max[1], bleft->max[2]);

362 glVertex3f(bleft->min[0], bleft->max[1], bleft->max[2]);

363 glVertex3f(bleft->min[0], bleft->max[1], bleft->max[2]);

364 glVertex3f(bleft->min[0], bleft->max[1], bleft->min[2]);

365 break;

366

367 default:

368 break;

369 }*/

370 }

371

372 bool Scene::build_kdtree()

373 {

374 assert(kdtree == 0);

375

376 const Face *faces = get_face_buffer();

377 int num_faces = get_num_faces();

378

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

380

381 int icost = accel_param[ACCEL_PARAM_COST_INTERSECT];

382 int tcost = accel_param[ACCEL_PARAM_COST_TRAVERSE];

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

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

385

386 free_kdtree(kdtree);

387 kdtree = new KDNode;

388

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

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

391 */

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

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

394

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

396 const Face *face = faces + i;

397

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

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

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

401

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

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

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

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

406 }

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

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

409 }

410 }

411 }

412

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

414 }

415

416 // calculate the heuristic for the root

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

418

419 // now proceed splitting the root recursively

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

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

422 return false;

423 }

424

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

426 print_item_counts(kdtree, 0);

427 return true;

428 }

429

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

431 {

432 int opt_max_depth = accel_param[ACCEL_PARAM_MAX_TREE_DEPTH];

433 int opt_max_items = accel_param[ACCEL_PARAM_MAX_NODE_ITEMS];

434 int tcost = accel_param[ACCEL_PARAM_COST_TRAVERSE];

435

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

437 return true;

438 }

439

440 int axis = level % 3;

441

442 float best_cost[2], best_sum_cost = FLT_MAX;

443 float best_split;

444

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

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

447

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

449 AABBox aabb_left, aabb_right;

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

451

452 aabb_left = aabb_right = kd->aabb;

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

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

455

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

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

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

459

460 if(sum_cost < best_sum_cost) {

461 best_cost[0] = left_cost;

462 best_cost[1] = right_cost;

463 best_sum_cost = sum_cost;

464 best_split = split[axis];

465 }

466 }

467 }

468

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

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

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

472 }

473

474 // create the two children

475 KDNode *kdleft, *kdright;

476 kdleft = new KDNode;

477 kdright = new KDNode;

478

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

480

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

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

483

484 kdleft->cost = best_cost[0];

485 kdright->cost = best_cost[1];

486

487 // TODO would it be much better if we actually split faces that straddle the splitting plane?

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

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

490 const Face *face = faces + fidx;

491

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

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

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

495 kdleft->face_idx.push_back(fidx);

496 }

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

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

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

500 kdright->face_idx.push_back(fidx);

501 }

502 }

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

504

505 kd->left = kdleft;

506 kd->right = kdright;

507

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

509 }

510

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

512 {

513 int num_inside = 0;

514 int tcost = accel_param[ACCEL_PARAM_COST_TRAVERSE];

515 int icost = accel_param[ACCEL_PARAM_COST_INTERSECT];

516

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

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

519

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

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

522 num_inside++;

523 break;

524 }

525 }

526 }

527

528 float sarea = aabb.calc_surface_area();

529 if(sarea < 1e-6) {

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

531 }

532

533 return tcost + sarea * num_inside * icost;

534 }

535

536 static void free_kdtree(KDNode *node)

537 {

538 if(node) {

539 free_kdtree(node->left);

540 free_kdtree(node->right);

541 delete node;

542 }

543 }

544

545 int kdtree_depth(const KDNode *node)

546 {

547 if(!node) return 0;

548

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

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

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

552 }

553

554 int kdtree_nodes(const KDNode *node)

555 {

556 if(!node) return 0;

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

558 }

559

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

561 {

562 if(!node) return;

563

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

565 fputs(" ", stdout);

566 }

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

568

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

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

571 }