Working with an infinite set of cubes, is there a way of detecting which cubes exist within a frustum?
Most frustum culling seems to work along the lines of running through all objects and seeing if they intersect - this is ok with a finite set of objects, or something like Octrees.
I'm currently finding all cubes within the frustum's bounding box - but that's far more than I really need.
I could then test these all against it, but I was wondering if I could skip a step.
With an infinite set of cubes, even the frustum has an infinite number of them. If someone has a better idea I am very interested to hear it. However, the octrees that you mention have worked wonderfully for me in the past. Basically any hierarchical structure will let you quickly eliminate huge number of objects. Then you can chose, depending on the complexity of the objects, whether you want to process all objects within an octtree node, or do you want to do finer detection which objects are within the frustum.
When you talk about cubes, I have a feeling you are talking about some kind of Minecraft like or voxel terrain. The frustum test is an important step, however do notice that in terrain case (and some others) you will have a great deal of objects (cubes) hidden "under" the visible ones. Finding a way to cull those efficiently will be of great importance. My point is that you should not spend every last CPU cycle frustum culling. If you can spend 20% of the time to frustum cull 80%, and then another 20% to cull 80% of hidden ones, it will be bigger improvement then to perform perfect frustum cull.
There are several ways of dealing with an infinite terrain.
1) If the terrain starts simple or small, but then grows, the octree should be balancing. This means that as you add more nodes into the tree, when a particular subtree grows beyond some threshold, one or more children should be pushed up or to the neighbouring tree. The idea is to try at all times have the (roughly) same number of subnodes in each subtree. This is a complex task, so you should definitely look for libraries rather then reinventing it yourself. It is worth noting that in most cases you do not need this complexity as it can be avoided using next method.
2) The easiest way to deal with seemingly "infinite" scene is to use two methods. A higher level structure that basically divides a terrain into a grid. Each grid location, chunk or area is a cube comrised of say 1000x1000x1000 of your cubes. Then use an octree to organize these 1024x1024x1024 area. Since you know the geometry of the large cube, it is easy to organize the octree. When rendering, you can use simple math to come up with several (10-is) large grid chunks that are in the frustum, and then process each one as a separate octree.
You're a bit confused. (Axis-aligned) Bounding box checks are there to make things cheaper.
They exist as a broadphase attempt to see whether a given voxel (volume or point) is likely to be within the frustum (containing volume) or not. In other words, they explicitly exist as an "early fail" mechanism. This sort of tiered elimination approach is common in graphics and collision detection, and in practice is computationally much more efficient than going straight for the final step -- which in your case is testing specifically to see whether each and every voxel in your world or zone is exactly inside or outside the frustum. It's costly to test every voxel in your world against exact frustum bounds, but it's much, much cheaper to test all of those against AABB bounds.
So don't skip a step. Listen to what the early warning system tells you. Let your axis-aligned bounding box serve its intended purpose -- cheap, early elimination. Then you do the expensive "on-which-side-of-each-of-6-arbitrarily-oriented-frustum-planes-is-this-voxel" tests only on that subset that you've found to lie within the bounding volume.
I'd go with recursive subdivision of a cuboid that is axis aligned and contains the frustum, which should be straightforward to construct based on the location of the corners of the frustum.
Firstly mark all small cubes as not intersecting the frustum.
Then test to see which case you have for the current cuboid, and apply the appropriate action:
Not intersecting the frustum - do nothing they are already marked correctly.
Completely inside the frustum - mark all small cubes within the big cube as inside the frustum.
It intersects the frustum - If it contains more than one cube then subdivide into two smaller cuboids (splitting on the longest axis), and apply the same test recursively to each one. If it can't be subdivided mark it as intersecting.
At the end of the process all cubes should be marked appropriately.
Note that instead of actually setting a flag on each small cube you may want to collect a list of the intersecting ones in some other way, or the mark them all as outside step will take forever.
