Hacker News Reader

Comment by daeken | Hacker News Reader

This is a pretty damn cool article, but it's an odd choice of bounding spheres for frustum culling of octree nodes. Yes, it's cheaper in terms of CPU time than using the actual octree nodes (which are either cubes or boxes -- cubes in this case), but it's far less precise, meaning you're going to be 1) checking more nodes, due to recursing further when you have a false positive, and 2) most likely sending more data to the GPU than required, especially considering the density of his world.

Can anyone think up a reason why spherical bounding boxes would be beneficial here?

View on HN

A sphere-frustum check is a lot cheaper than a box-frustum check. The spherical test only has to check the distance of a single point to the frustum, a box intersection test is much more complex.

There are some false positives, but as with many things in game development 'close enough' usually works pretty well.

If you're really concerned with efficiency you should look into other data structures than an octree. Octrees are a nightmare for cache performance (like most other tree based structures) and cache utilization is usually the bottleneck on modern CPUs.

If you're interested in the subject this book (http://realtimecollisiondetection.net/books/rtcd/) covers everything extremely well.

Yea, I know sphere-frustum checks in and of themselves are cheap, but when you consider the cost of false-positives for octree traversal and the cost of sending unnecessary data to the GPU, it doesn't seem like it makes a lot of sense to me.

Then it sounds like it's time for an experiment.

Take the code he posted with the article, and modify it to use a box-frustum check instead. Don't forget to test the program's performance before you make any modifications so you'll have something to compare to. Even better, keep the code intact and #ifdef'd out so you can toggle between the two.

Then, compare the differences. Check to see how many false positives there are on average, and how much extra data this means gets sent to the GPU. Keep in mind, however, that extra data being sent to the GPU doesn't matter unless the GPU is actually the bottleneck.

My hypothesis is that the way the octree abuses the cache will overshadow the performance gains (if any) you'll make by using something other than spheres for your test. In the end you'll find that if performance in this part of the code is a problem, you'll need to switch data structures.

I'm more curious about this as a general trend. I always see people advising sphere-frustum tests for these situations, but I've never really understood how it works out better than box-frustum. I should really run some tests not just against his code, but to figure out where the tipping point between the two techniques is.

Broadly speaking, simpler is better on modern CPUs and GPUs. Testing an array of spheres against a view frustum is cache friendly, can be sped up considerably using SIMD instructions and is easily parallelizable. Submitting superfluous data to a GPU is not generally impactful; GPUs are clever at not drawing stuff that doesn't actually contribute (with clipping and depth buffer rejection) and extremely fast in their own right.

Reply on news.ycombinator.com