clray: a218551293ad src/scene.cc

clray

view src/scene.cc @ 34:a218551293ad

blah blah blah

author	John Tsiombikas <nuclear@member.fsf.org>
date	Tue, 24 Aug 2010 18:35:03 +0100
parents	4cf4919c3812
children	4dec8853bf75

line source

1 #include <math.h>

2 #include <float.h>

3 #include <assert.h>

4 #include "scene.h"

5 #include "ogl.h"

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

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

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

11 static void free_kdtree(KDNode *node);

12 static void kdtree_gpu_flatten(KDNodeGPU *kdbuf, int idx, const KDNode *node);

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

16 static int accel_param[NUM_ACCEL_PARAMS] = {

17 40, // max tree depth

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

19 5, // estimated traversal cost

20 15 // estimated interseciton cost

21 };

24 void set_accel_param(int p, int v)

25 {

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

27 accel_param[p] = v;

28 }

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

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

33 {

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

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

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

37 return false;

38 }

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

40 return false;

41 }

42 }

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

44 return false;

45 }

46 }

47 return true;

48 }

50 float AABBox::calc_surface_area() const

51 {

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

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

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

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

57 }

59 KDNode::KDNode()

60 {

61 left = right = 0;

62 cost = 0.0;

63 }

66 Scene::Scene()

67 {

68 facebuf = 0;

69 num_faces = -1;

70 kdtree = 0;

71 kdbuf = 0;

72 }

74 Scene::~Scene()

75 {

76 delete [] facebuf;

77 delete [] kdbuf;

78 free_kdtree(kdtree);

79 }

81 bool Scene::add_mesh(Mesh *m)

82 {

83 // make sure triangles have material ids

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

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

86 }

88 try {

89 meshes.push_back(m);

90 }

91 catch(...) {

92 return false;

93 }

95 // invalidate facebuffer and count

96 delete [] facebuf;

97 facebuf = 0;

98 num_faces = -1;

100 return true;

101 }

102

103 int Scene::get_num_meshes() const

104 {

105 return (int)meshes.size();

106 }

107

108 int Scene::get_num_faces() const

109 {

110 if(num_faces >= 0) {

111 return num_faces;

112 }

113

114 num_faces = 0;

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

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

117 }

118 return num_faces;

119 }

120

121 int Scene::get_num_materials() const

122 {

123 return (int)matlib.size();

124 }

125

126 Material *Scene::get_materials()

127 {

128 if(matlib.empty()) {

129 return 0;

130 }

131 return &matlib[0];

132 }

133

134 const Material *Scene::get_materials() const

135 {

136 if(matlib.empty()) {

137 return 0;

138 }

139 return &matlib[0];

140 }

141

142 const Face *Scene::get_face_buffer() const

143 {

144 if(facebuf) {

145 return facebuf;

146 }

147

148 int num_meshes = get_num_meshes();

149

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

151 facebuf = new Face[num_faces];

152 Face *fptr = facebuf;

153

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

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

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

157 }

158 }

159 return facebuf;

160 }

161

162 const KDNodeGPU *Scene::get_kdtree_buffer() const

163 {

164 if(kdbuf) {

165 return kdbuf;

166 }

167

168 if(!kdtree) {

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

170 }

171

172 int max_nodes = (int)pow(2, kdtree_depth(kdtree)) - 1;

173 printf("allocating storage for the complete tree (%d)\n", max_nodes);

174

175 kdbuf = new KDNodeGPU[max_nodes + 1];

176 kdtree_gpu_flatten(kdbuf, 1, kdtree);

177 return kdbuf;

178 }

179

180 static int ipow(int x, int n)

181 {

182 assert(n >= 0);

183

184 int res = 1;

185 for(int i=0; i<n; i++) {

186 res *= x;

187 }

188 return res;

189 }

190

191 int Scene::get_kdtree_buffer_size() const

192 {

193 // 2**depth - 1 nodes for the complete tree + 1 for the unused heap item 0.

194 return ipow(2, kdtree_depth(kdtree)) * sizeof(KDNodeGPU);

195 }

196

197 void Scene::draw_kdtree() const

198 {

199 glPushAttrib(GL_ENABLE_BIT);

200 glDisable(GL_LIGHTING);

201 glDepthMask(0);

202

203 glBegin(GL_LINES);

204 ::draw_kdtree(kdtree, 0);

205 glEnd();

206

207 glDepthMask(1);

208 glPopAttrib();

209 }

210

211 static float palette[][3] = {

212 {0, 1, 0},

213 {1, 0, 0},

214 {0, 0, 1},

215 {1, 1, 0},

216 {0, 0, 1},

217 {1, 0, 1}

218 };

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

220

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

222 {

223 if(!node) return;

224

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

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

227

228 glColor3fv(palette[level % pal_size]);

229

230 glVertex3fv(node->aabb.min);

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

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

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

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

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

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

237 glVertex3fv(node->aabb.min);

238

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

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

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

242 glVertex3fv(node->aabb.max);

243 glVertex3fv(node->aabb.max);

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

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

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

247

248 glVertex3fv(node->aabb.min);

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

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

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

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

253 glVertex3fv(node->aabb.max);

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

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

256 /*if(!node->left) return;

257

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

259

260 int axis = level % 3;

261 switch(axis) {

262 case 0:

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

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

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

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

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

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

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

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

271 break;

272

273 case 1:

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

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

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

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

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

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

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

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

282 break;

283

284 case 2:

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

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

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

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

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

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

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

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

293 break;

294

295 default:

296 break;

297 }*/

298 }

299

300 bool Scene::build_kdtree()

301 {

302 assert(kdtree == 0);

303

304 const Face *faces = get_face_buffer();

305 int num_faces = get_num_faces();

306

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

308

309 int icost = accel_param[ACCEL_PARAM_COST_INTERSECT];

310 int tcost = accel_param[ACCEL_PARAM_COST_TRAVERSE];

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

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

313

314 free_kdtree(kdtree);

315 kdtree = new KDNode;

316

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

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

319 */

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

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

322

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

324 const Face *face = faces + i;

325

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

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

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

329

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

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

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

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

334 }

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

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

337 }

338 }

339 }

340

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

342 }

343

344 // calculate the heuristic for the root

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

346

347 // now proceed splitting the root recursively

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

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

350 return false;

351 }

352

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

354 print_item_counts(kdtree, 0);

355 return true;

356 }

357

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

359 {

360 int opt_max_depth = accel_param[ACCEL_PARAM_MAX_TREE_DEPTH];

361 int opt_max_items = accel_param[ACCEL_PARAM_MAX_NODE_ITEMS];

362 int tcost = accel_param[ACCEL_PARAM_COST_TRAVERSE];

363

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

365 return true;

366 }

367

368 int axis = level % 3;

369

370 float best_cost[2], best_sum_cost = FLT_MAX;

371 float best_split;

372

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

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

375

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

377 AABBox aabb_left, aabb_right;

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

379

380 aabb_left = aabb_right = kd->aabb;

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

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

383

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

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

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

387

388 if(sum_cost < best_sum_cost) {

389 best_cost[0] = left_cost;

390 best_cost[1] = right_cost;

391 best_sum_cost = sum_cost;

392 best_split = split[axis];

393 }

394 }

395 }

396

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

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

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

400 }

401

402 // create the two children

403 KDNode *kdleft, *kdright;

404 kdleft = new KDNode;

405 kdright = new KDNode;

406

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

408

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

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

411

412 kdleft->cost = best_cost[0];

413 kdright->cost = best_cost[1];

414

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

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

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

418 const Face *face = faces + fidx;

419

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

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

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

423 kdleft->face_idx.push_back(fidx);

424 }

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

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

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

428 kdright->face_idx.push_back(fidx);

429 }

430 }

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

432

433 kd->left = kdleft;

434 kd->right = kdright;

435

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

437 }

438

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

440 {

441 int num_inside = 0;

442 int tcost = accel_param[ACCEL_PARAM_COST_TRAVERSE];

443 int icost = accel_param[ACCEL_PARAM_COST_INTERSECT];

444

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

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

447

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

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

450 num_inside++;

451 break;

452 }

453 }

454 }

455

456 float sarea = aabb.calc_surface_area();

457 if(sarea < 1e-6) {

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

459 }

460

461 return tcost + sarea * num_inside * icost;

462 }

463

464 static void free_kdtree(KDNode *node)

465 {

466 if(node) {

467 free_kdtree(node->left);

468 free_kdtree(node->right);

469 delete node;

470 }

471 }

472

473 int kdtree_depth(const KDNode *node)

474 {

475 if(!node) return 0;

476

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

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

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

480 }

481

482 int kdtree_nodes(const KDNode *node)

483 {

484 if(!node) return 0;

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

486 }

487

488 #define MAX_FACES (sizeof dest->face_idx / sizeof *dest->face_idx)

489 static void kdtree_gpu_flatten(KDNodeGPU *kdbuf, int idx, const KDNode *node)

490 {

491 KDNodeGPU *dest = kdbuf + idx;

492

493 dest->aabb = node->aabb;

494 dest->num_faces = 0;

495

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

497 if(dest->num_faces >= (int)MAX_FACES) {

498 fprintf(stderr, "kdtree_gpu_flatten WARNING: more than %d faces in node, skipping!\n", (int)MAX_FACES);

499 break;

500 }

501 dest->face_idx[dest->num_faces++] = node->face_idx[i];

502 }

503

504 if(node->left) {

505 assert(node->right);

506 assert(!dest->num_faces);

507

508 dest->num_faces = -1;

509

510 kdtree_gpu_flatten(kdbuf, idx * 2, node->left);

511 kdtree_gpu_flatten(kdbuf, idx * 2 + 1, node->right);

512 }

513 }

514

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

516 {

517 if(!node) return;

518

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

520 fputs(" ", stdout);

521 }

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

523

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

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

526 }