clray: 97cfd9675310 src/scene.cc

clray

view src/scene.cc @ 28:97cfd9675310

trying to pass the kdtree to the kernel

author	John Tsiombikas <nuclear@member.fsf.org>
date	Sat, 21 Aug 2010 03:42:49 +0100
parents	8b2f2ad14ae7
children	353d80127627

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 num_kdnodes = -1;

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 Material *Scene::get_materials()

130 {

131 if(matlib.empty()) {

132 return 0;

133 }

134 return &matlib[0];

135 }

136

137 const Material *Scene::get_materials() const

138 {

139 if(matlib.empty()) {

140 return 0;

141 }

142 return &matlib[0];

143 }

144

145 const Face *Scene::get_face_buffer() const

146 {

147 if(facebuf) {

148 return facebuf;

149 }

150

151 int num_meshes = get_num_meshes();

152

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

154 facebuf = new Face[num_faces];

155 Face *fptr = facebuf;

156

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

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

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

160 }

161 }

162 return facebuf;

163 }

164

165 const KDNodeGPU *Scene::get_kdtree_buffer() const

166 {

167 if(kdbuf) {

168 return kdbuf;

169 }

170

171 if(!kdtree) {

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

173 }

174

175 if(!get_num_kdnodes()) {

176 return 0;

177 }

178

179 kdbuf = new KDNodeGPU[num_kdnodes + 1];

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

181 return kdbuf;

182 }

183

184 int Scene::get_num_kdnodes() const

185 {

186 if(num_kdnodes >= 0) {

187 return num_kdnodes;

188 }

189

190 num_kdnodes = kdtree_nodes(kdtree);

191 return num_kdnodes;

192 }

193

194

195 void Scene::draw_kdtree() const

196 {

197 glPushAttrib(GL_ENABLE_BIT);

198 glDisable(GL_LIGHTING);

199 glDepthMask(0);

200

201 glBegin(GL_LINES);

202 ::draw_kdtree(kdtree, 0);

203 glEnd();

204

205 glDepthMask(1);

206 glPopAttrib();

207 }

208

209 static float palette[][3] = {

210 {0, 1, 0},

211 {1, 0, 0},

212 {0, 0, 1},

213 {1, 1, 0},

214 {0, 0, 1},

215 {1, 0, 1}

216 };

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

218

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

220 {

221 if(!node) return;

222

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

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

225

226 glColor3fv(palette[level % pal_size]);

227

228 glVertex3fv(node->aabb.min);

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

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

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

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

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

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

235 glVertex3fv(node->aabb.min);

236

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

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

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

240 glVertex3fv(node->aabb.max);

241 glVertex3fv(node->aabb.max);

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

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

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

245

246 glVertex3fv(node->aabb.min);

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

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

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

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

251 glVertex3fv(node->aabb.max);

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

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

254 }

255

256 bool Scene::build_kdtree()

257 {

258 const Face *faces = get_face_buffer();

259 int num_faces = get_num_faces();

260

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

262

263 int icost = accel_param[ACCEL_PARAM_COST_INTERSECT];

264 int tcost = accel_param[ACCEL_PARAM_COST_TRAVERSE];

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

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

267

268 free_kdtree(kdtree);

269 kdtree = new KDNode;

270

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

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

273 */

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

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

276

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

278 const Face *face = faces + i;

279

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

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

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

283

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

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

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

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

288 }

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

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

291 }

292 }

293 }

294

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

296 kdtree->num_faces++;

297 }

298

299 // calculate the heuristic for the root

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

301

302 // now proceed splitting the root recursively

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

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

305 return false;

306 }

307

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

309 print_item_counts(kdtree, 0);

310 return true;

311 }

312

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

314 {

315 int opt_max_depth = accel_param[ACCEL_PARAM_MAX_TREE_DEPTH];

316 int opt_max_items = accel_param[ACCEL_PARAM_MAX_NODE_ITEMS];

317 int tcost = accel_param[ACCEL_PARAM_COST_TRAVERSE];

318

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

320 return true;

321 }

322

323 int axis = level % 3;

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

325

326 float best_cost[2], best_sum_cost = FLT_MAX;

327 float best_split;

328

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

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

331 const Face *face = *it++;

332

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

334 AABBox aabb_left, aabb_right;

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

336

337 aabb_left = aabb_right = kd->aabb;

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

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

340

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

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

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

344

345 if(sum_cost < best_sum_cost) {

346 best_cost[0] = left_cost;

347 best_cost[1] = right_cost;

348 best_sum_cost = sum_cost;

349 best_split = split[axis];

350 }

351 }

352 }

353

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

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

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

357 }

358 kd->pt = best_split;

359

360 // create the two children

361 KDNode *kdleft, *kdright;

362 kdleft = new KDNode;

363 kdright = new KDNode;

364

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

366

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

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

369

370 kdleft->cost = best_cost[0];

371 kdright->cost = best_cost[1];

372

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

374

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

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

377 const Face *face = *it++;

378

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

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

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

382 kdleft->faces.push_back(face);

383 kdleft->num_faces++;

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 kdright->faces.push_back(face);

389 kdright->num_faces++;

390 }

391 }

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

393

394 kd->left = kdleft;

395 kd->right = kdright;

396

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

398 }

399

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

401 {

402 int num_inside = 0;

403 int tcost = accel_param[ACCEL_PARAM_COST_TRAVERSE];

404 int icost = accel_param[ACCEL_PARAM_COST_INTERSECT];

405

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

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

408 const Face *face = *it++;

409

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

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

412 num_inside++;

413 break;

414 }

415 }

416 }

417

418 float sarea = aabb.calc_surface_area();

419 if(sarea < 1e-8) {

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

421 }

422

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

424 }

425

426 static void free_kdtree(KDNode *node)

427 {

428 if(node) {

429 free_kdtree(node->left);

430 free_kdtree(node->right);

431 delete node;

432 }

433 }

434

435 int kdtree_depth(const KDNode *node)

436 {

437 if(!node) return 0;

438

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

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

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

442 }

443

444 int kdtree_nodes(const KDNode *node)

445 {

446 if(!node) return 0;

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

448 }

449

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

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

452 {

453 KDNodeGPU *dest = kdbuf + idx;

454

455 dest->aabb = node->aabb;

456 dest->num_faces = 0;

457

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

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

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

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

462 break;

463 }

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

465 }

466

467 if(node->left) {

468 assert(node->right);

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

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

471 }

472 }

473

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

475 {

476 if(!node) return;

477

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

479 fputs(" ", stdout);

480 }

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

482

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

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

485 }