clray: 92786fc3317e src/scene.cc

clray

view src/scene.cc @ 31:92786fc3317e

yey! *seems* to work now

author	John Tsiombikas <nuclear@member.fsf.org>
date	Sun, 22 Aug 2010 00:50:47 +0100
parents	04803c702014
children	4cf4919c3812

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, int level = 0);

10 static float eval_cost(const std::list<const Face*> &faces, const AABBox &aabb, int axis, float par_sarea = 1.0);

11 static void free_kdtree(KDNode *node);

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

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 axis = 0;

62 pt = 0.0;

63 left = right = 0;

64 num_faces = 0;

65 }

68 Scene::Scene()

69 {

70 facebuf = 0;

71 num_faces = -1;

72 kdtree = 0;

73 kdbuf = 0;

74 }

76 Scene::~Scene()

77 {

78 delete [] facebuf;

79 delete [] kdbuf;

80 free_kdtree(kdtree);

81 }

83 bool Scene::add_mesh(Mesh *m)

84 {

85 // make sure triangles have material ids

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

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

88 }

90 try {

91 meshes.push_back(m);

92 }

93 catch(...) {

94 return false;

95 }

97 // invalidate facebuffer and count

98 delete [] facebuf;

99 facebuf = 0;

100 num_faces = -1;

101

102 return true;

103 }

104

105 int Scene::get_num_meshes() const

106 {

107 return (int)meshes.size();

108 }

109

110 int Scene::get_num_faces() const

111 {

112 if(num_faces >= 0) {

113 return num_faces;

114 }

115

116 num_faces = 0;

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

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

119 }

120 return num_faces;

121 }

122

123 int Scene::get_num_materials() const

124 {

125 return (int)matlib.size();

126 }

127

128 Material *Scene::get_materials()

129 {

130 if(matlib.empty()) {

131 return 0;

132 }

133 return &matlib[0];

134 }

135

136 const Material *Scene::get_materials() const

137 {

138 if(matlib.empty()) {

139 return 0;

140 }

141 return &matlib[0];

142 }

143

144 const Face *Scene::get_face_buffer() const

145 {

146 if(facebuf) {

147 return facebuf;

148 }

149

150 int num_meshes = get_num_meshes();

151

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

153 facebuf = new Face[num_faces];

154 Face *fptr = facebuf;

155

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

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

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

159 }

160 }

161 return facebuf;

162 }

163

164 const KDNodeGPU *Scene::get_kdtree_buffer() const

165 {

166 if(kdbuf) {

167 return kdbuf;

168 }

169

170 if(!kdtree) {

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

172 }

173

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

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

176

177 kdbuf = new KDNodeGPU[max_nodes + 1];

178 kdtree_gpu_flatten(kdbuf, 1, kdtree, get_face_buffer());

179 return kdbuf;

180 }

181

182 static int ipow(int x, int n)

183 {

184 assert(n >= 0);

185

186 int res = 1;

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

188 res *= x;

189 }

190 return res;

191 }

192

193 int Scene::get_kdtree_buffer_size() const

194 {

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

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

197 }

198

199 void Scene::draw_kdtree() const

200 {

201 glPushAttrib(GL_ENABLE_BIT);

202 glDisable(GL_LIGHTING);

203 glDepthMask(0);

204

205 glBegin(GL_LINES);

206 ::draw_kdtree(kdtree, 0);

207 glEnd();

208

209 glDepthMask(1);

210 glPopAttrib();

211 }

212

213 static float palette[][3] = {

214 {0, 1, 0},

215 {1, 0, 0},

216 {0, 0, 1},

217 {1, 1, 0},

218 {0, 0, 1},

219 {1, 0, 1}

220 };

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

222

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

224 {

225 if(!node) return;

226

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

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

229

230 glColor3fv(palette[level % pal_size]);

231

232 glVertex3fv(node->aabb.min);

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

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

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

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

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

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

239 glVertex3fv(node->aabb.min);

240

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

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

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

244 glVertex3fv(node->aabb.max);

245 glVertex3fv(node->aabb.max);

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

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

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

249

250 glVertex3fv(node->aabb.min);

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

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

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

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

255 glVertex3fv(node->aabb.max);

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

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

258 }

259

260 bool Scene::build_kdtree()

261 {

262 assert(kdtree == 0);

263

264 const Face *faces = get_face_buffer();

265 int num_faces = get_num_faces();

266

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

268

269 int icost = accel_param[ACCEL_PARAM_COST_INTERSECT];

270 int tcost = accel_param[ACCEL_PARAM_COST_TRAVERSE];

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

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

273

274 free_kdtree(kdtree);

275 kdtree = new KDNode;

276

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

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

279 */

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

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

282

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

284 const Face *face = faces + i;

285

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

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

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

289

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

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

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

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

294 }

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

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

297 }

298 }

299 }

300

301 kdtree->faces.push_back(face); // add the face

302 kdtree->num_faces++;

303 }

304

305 // calculate the heuristic for the root

306 kdtree->cost = eval_cost(kdtree->faces, kdtree->aabb, kdtree->axis);

307

308 // now proceed splitting the root recursively

309 if(!::build_kdtree(kdtree)) {

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

311 return false;

312 }

313

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

315 print_item_counts(kdtree, 0);

316 return true;

317 }

318

319 static bool build_kdtree(KDNode *kd, int level)

320 {

321 int opt_max_depth = accel_param[ACCEL_PARAM_MAX_TREE_DEPTH];

322 int opt_max_items = accel_param[ACCEL_PARAM_MAX_NODE_ITEMS];

323 int tcost = accel_param[ACCEL_PARAM_COST_TRAVERSE];

324

325 if(kd->num_faces == 0 || level >= opt_max_depth) {

326 return true;

327 }

328

329 int axis = level % 3;

330 //float parent_sa = kd->aabb.calc_surface_area();

331

332 float best_cost[2], best_sum_cost = FLT_MAX;

333 float best_split;

334

335 std::list<const Face*>::iterator it = kd->faces.begin();

336 while(it != kd->faces.end()) {

337 const Face *face = *it++;

338

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

340 AABBox aabb_left, aabb_right;

341 const float *split = face->v[i].pos;

342

343 aabb_left = aabb_right = kd->aabb;

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

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

346

347 float left_cost = eval_cost(kd->faces, aabb_left, axis);

348 float right_cost = eval_cost(kd->faces, aabb_right, axis);

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

350

351 if(sum_cost < best_sum_cost) {

352 best_cost[0] = left_cost;

353 best_cost[1] = right_cost;

354 best_sum_cost = sum_cost;

355 best_split = split[axis];

356 }

357 }

358 }

359

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

361 if(best_sum_cost > kd->cost && (opt_max_items == 0 || kd->num_faces <= opt_max_items)) {

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

363 }

364 kd->pt = best_split;

365

366 // create the two children

367 KDNode *kdleft, *kdright;

368 kdleft = new KDNode;

369 kdright = new KDNode;

370

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

372

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

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

375

376 kdleft->cost = best_cost[0];

377 kdright->cost = best_cost[1];

378

379 //kdleft->axis = kdright->axis = (axis + 1) % 3;

380

381 it = kd->faces.begin();

382 while(it != kd->faces.end()) {

383 const Face *face = *it++;

384

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

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

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

388 kdleft->faces.push_back(face);

389 kdleft->num_faces++;

390 }

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

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

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

394 kdright->faces.push_back(face);

395 kdright->num_faces++;

396 }

397 }

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

399

400 kd->left = kdleft;

401 kd->right = kdright;

402

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

404 }

405

406 static float eval_cost(const std::list<const Face*> &faces, const AABBox &aabb, int axis, float par_sarea)

407 {

408 int num_inside = 0;

409 int tcost = accel_param[ACCEL_PARAM_COST_TRAVERSE];

410 int icost = accel_param[ACCEL_PARAM_COST_INTERSECT];

411

412 std::list<const Face*>::const_iterator it = faces.begin();

413 while(it != faces.end()) {

414 const Face *face = *it++;

415

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

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

418 num_inside++;

419 break;

420 }

421 }

422 }

423

424 float sarea = aabb.calc_surface_area();

425 if(sarea < 1e-8) {

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

427 }

428

429 return tcost + (sarea / par_sarea) * num_inside * icost;

430 }

431

432 static void free_kdtree(KDNode *node)

433 {

434 if(node) {

435 free_kdtree(node->left);

436 free_kdtree(node->right);

437 delete node;

438 }

439 }

440

441 int kdtree_depth(const KDNode *node)

442 {

443 if(!node) return 0;

444

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

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

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

448 }

449

450 int kdtree_nodes(const KDNode *node)

451 {

452 if(!node) return 0;

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

454 }

455

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

457 static void kdtree_gpu_flatten(KDNodeGPU *kdbuf, int idx, const KDNode *node, const Face *facebuf)

458 {

459 KDNodeGPU *dest = kdbuf + idx;

460

461 dest->aabb = node->aabb;

462 dest->num_faces = 0;

463

464 std::list<const Face*>::const_iterator it = node->faces.begin();

465 while(it != node->faces.end()) {

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

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

468 break;

469 }

470 dest->face_idx[dest->num_faces++] = *it++ - facebuf;

471 }

472

473 if(node->left) {

474 assert(node->right);

475 assert(!dest->num_faces);

476

477 dest->num_faces = -1;

478

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

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

481 }

482 }

483

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

485 {

486 if(!node) return;

487

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

489 fputs(" ", stdout);

490 }

491 printf("- %d (cost: %f)\n", node->num_faces, node->cost);

492

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

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

495 }