clray: 8b2f2ad14ae7 src/scene.cc

clray

view src/scene.cc @ 27:8b2f2ad14ae7

semi-fixed the kdtree construction

author	John Tsiombikas <nuclear@member.fsf.org>
date	Tue, 17 Aug 2010 20:35:00 +0100
parents	c740ae431d51
children	97cfd9675310

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 int kdtree_depth(const KDNode *node);

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

16 static int accel_param[NUM_ACCEL_PARAMS] = {

17 75, // 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 }

75 Scene::~Scene()

76 {

77 delete [] facebuf;

78 }

80 bool Scene::add_mesh(Mesh *m)

81 {

82 // make sure triangles have material ids

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

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

85 }

87 try {

88 meshes.push_back(m);

89 }

90 catch(...) {

91 return false;

92 }

94 // invalidate facebuffer and count

95 delete [] facebuf;

96 facebuf = 0;

97 num_faces = -1;

99 return true;

100 }

101

102 int Scene::get_num_meshes() const

103 {

104 return (int)meshes.size();

105 }

106

107 int Scene::get_num_faces() const

108 {

109 if(num_faces >= 0) {

110 return num_faces;

111 }

112

113 num_faces = 0;

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

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

116 }

117 return num_faces;

118 }

119

120 int Scene::get_num_materials() const

121 {

122 return (int)matlib.size();

123 }

124

125 Material *Scene::get_materials()

126 {

127 if(matlib.empty()) {

128 return 0;

129 }

130 return &matlib[0];

131 }

132

133 const Material *Scene::get_materials() const

134 {

135 if(matlib.empty()) {

136 return 0;

137 }

138 return &matlib[0];

139 }

140

141 const Face *Scene::get_face_buffer() const

142 {

143 if(facebuf) {

144 return facebuf;

145 }

146

147 int num_meshes = get_num_meshes();

148

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

150 facebuf = new Face[num_faces];

151 Face *fptr = facebuf;

152

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

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

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

156 }

157 }

158 return facebuf;

159 }

160

161

162 void Scene::draw_kdtree() const

163 {

164 glPushAttrib(GL_ENABLE_BIT);

165 glDisable(GL_LIGHTING);

166 glDepthMask(0);

167

168 glBegin(GL_LINES);

169 ::draw_kdtree(kdtree, 0);

170 glEnd();

171

172 glDepthMask(1);

173 glPopAttrib();

174 }

175

176 static float palette[][3] = {

177 {0, 1, 0},

178 {0, 1, 0},

179 {0, 1, 0},

180 {1, 0, 0},

181 {1, 0, 0},

182 {1, 0, 0},

183 {0, 0, 1},

184 {0, 0, 1},

185 {0, 0, 1},

186 {1, 1, 0},

187 {1, 1, 0},

188 {1, 1, 0},

189 {0, 0, 1},

190 {0, 0, 1},

191 {0, 0, 1},

192 {1, 0, 1},

193 {1, 0, 1},

194 {1, 0, 1}

195 };

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

197

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

199 {

200 if(!node) return;

201

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

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

204

205 glColor3fv(palette[level % pal_size]);

206

207 glVertex3fv(node->aabb.min);

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

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

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

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

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

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

214 glVertex3fv(node->aabb.min);

215

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

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

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

219 glVertex3fv(node->aabb.max);

220 glVertex3fv(node->aabb.max);

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

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

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

224

225 glVertex3fv(node->aabb.min);

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

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

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

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

230 glVertex3fv(node->aabb.max);

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

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

233 }

234

235 bool Scene::build_kdtree()

236 {

237 const Face *faces = get_face_buffer();

238 int num_faces = get_num_faces();

239

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

241

242 int icost = accel_param[ACCEL_PARAM_COST_INTERSECT];

243 int tcost = accel_param[ACCEL_PARAM_COST_TRAVERSE];

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

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

246

247 free_kdtree(kdtree);

248 kdtree = new KDNode;

249

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

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

252 */

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

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

255

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

257 const Face *face = faces + i;

258

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

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

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

262

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

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

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

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

267 }

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

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

270 }

271 }

272 }

273

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

275 kdtree->num_faces++;

276 }

277

278 // calculate the heuristic for the root

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

280

281 // now proceed splitting the root recursively

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

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

284 return false;

285 }

286

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

288 print_item_counts(kdtree, 0);

289 return true;

290 }

291

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

293 {

294 int opt_max_items = accel_param[ACCEL_PARAM_MAX_NODE_ITEMS];

295 int tcost = accel_param[ACCEL_PARAM_COST_TRAVERSE];

296

297 if(kd->num_faces == 0) {

298 return true;

299 }

300

301 int axis = level % 3;

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

303

304 float best_cost[2], best_sum_cost = FLT_MAX;

305 float best_split;

306

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

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

309 const Face *face = *it++;

310

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

312 AABBox aabb_left, aabb_right;

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

314

315 aabb_left = aabb_right = kd->aabb;

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

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

318

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

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

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

322

323 if(sum_cost < best_sum_cost) {

324 best_cost[0] = left_cost;

325 best_cost[1] = right_cost;

326 best_sum_cost = sum_cost;

327 best_split = split[axis];

328 }

329 }

330 }

331

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

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

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

335 }

336 kd->pt = best_split;

337

338 // create the two children

339 KDNode *kdleft, *kdright;

340 kdleft = new KDNode;

341 kdright = new KDNode;

342

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

344

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

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

347

348 kdleft->cost = best_cost[0];

349 kdright->cost = best_cost[1];

350

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

352

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

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

355 const Face *face = *it++;

356

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

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

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

360 kdleft->faces.push_back(face);

361 kdleft->num_faces++;

362 }

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

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

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

366 kdright->faces.push_back(face);

367 kdright->num_faces++;

368 }

369 }

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

371

372 kd->left = kdleft;

373 kd->right = kdright;

374

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

376 }

377

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

379 {

380 int num_inside = 0;

381 int tcost = accel_param[ACCEL_PARAM_COST_TRAVERSE];

382 int icost = accel_param[ACCEL_PARAM_COST_INTERSECT];

383

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

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

386 const Face *face = *it++;

387

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

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

390 num_inside++;

391 break;

392 }

393 }

394 }

395

396 float sarea = aabb.calc_surface_area();

397 if(sarea < 1e-8) {

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

399 }

400

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

402 }

403

404 static void free_kdtree(KDNode *node)

405 {

406 if(node) {

407 free_kdtree(node->left);

408 free_kdtree(node->right);

409 delete node;

410 }

411 }

412

413 static int kdtree_depth(const KDNode *node)

414 {

415 if(!node) return 0;

416

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

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

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

420 }

421

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

423 {

424 if(!node) return;

425

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

427 fputs(" ", stdout);

428 }

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

430

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

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

433 }