Previous | Next --- Slide 17 of 49
Back to Lecture Thumbnails
lucida

We could use something like the surface area heuristic to determine which child to enter first. To be more specific, we scale the surface area of each node by the total surface area of the parent node and multiply that by the total number of primitives in each node.

However, there are certain cases where this is not ideal. For example, you could have a big bounding box for child node 1 where child node 1 had 1000 dust particles in it. Child 2 has a smaller bounding box but one large primitive that takes up the entire box. It's fair to say in this case that child2 would probably be the better choice here but it wouldn't win under this heuristic. This makes me think that factoring in the surface areas of the primitives inside a node into the heuristic would be useful as well. (If exact surface areas of primities are hard to compute, we can at least use estimates). In this revised heuristic, child2 would win.

But there's also another bad case:

Say we have two child nodes, each with same size bounding boxes. Assume all primitives have same surface area as well. Child1 has 1000 primitives all clumped together in one region of the bounding box overlapping each other and child2 has just 10 primitives uniformly distributed over its bounding box. In this case, it is perhaps more likely for a random ray (random direction) to hit a primitive in child2 instead of child1. But under our current heuristic, child1 would win because it has more primitives. So now maybe we want to introduce some notion of entropy of the distribution of the primitives. This can be approximated by measuring the variance of the coordinates of the centroids of the primitives in each bounding box.

But all this calculation to obtain a good heuristic seems expensive so we have to weigh how much we gain from picking the right child against the cost of finding the right child.