Previous | Next --- Slide 27 of 49
Back to Lecture Thumbnails
cma

A few clarifying questions about the listed algorithm:

1) On the step that says "For each of the B-1 possible partitioning planes evaluate SAH", if I'm understanding this correctly, it means to take the union of the buckets on each side of the planes, and then evaluate the SAH for each of the two sides?

2) On the step that says "Recurse on lowest cost partition found (or make node a leaf)", does "lowest cost" mean the combined costs/SAH of each side (i.e. adding the cost of the left and right partitions)?

keenan

Yes and yes.

This is also the reason we (grossly) approximate the cost of subtrees rather than doing a full recursive evaluation. You may be able to use dynamic programming to get a more accurate cost estimate, but empirically it’s not clear such an estimate is a big win in terms of the evaluation cost for the final tree.