<Background>
I recently dove into OpenGL in an attempt to learn it, and possibly make some money along the way. As a first project I figured that a simple Minecraft clone would be in order, so that meant drawing blocks, lots of blocks, quickly and efficiently to the screen.
</Background>
NOTE - Though I am using OpenGL I don't expect you to also be using it to participate in this discussion, it is just what I picked up first.
Now, I am not going to talk about the ways to draw the blocks, that is a topic for another place (well, the same place, but another thread) and another time. Instead I am going to open a discussion about how to cull out massive numbers of blocks quickly and easily before even having to determine what is going to be visible. After all, the lower the number of blocks you have to look at to determine if they are visible or not the quicker you should be able to get an image to the screen.
So far I have come up with two ideas and have employed both of them, at least in part, to determine what should be culled and what should be kept around for a chance at being drawn to the screen (though in actuality, at the moment I am just drawing everything that isn't culled out and will worry about what is actually visible later on).
The first idea was to simply create a 3D mesh for a "bounding object" and determine if any given block is at least partially within the "bounding object". This is accomplished by some nifty vector-based dot and cross product and works wonderfully. However, as is normally the case with things of this nature, it also seems to reduce the frame rate that the game is getting to about 6 FPS (not ideal, obviously).
The second idea was to use the player's current position and facing direction to come up with a few triangles in 3D space which could then be used, with a few equations, to determine if a given point was within them or not. This seems to run faster overall, but is significantly harder to set up and more prone to error with even simple changes. Not to mention that you basically need a separate function for each of the 4 cardinal directions to get it working remotely properly. I receive about 7 FPS here, so not a huge improvement, but considering that these FPS readings are based off an Ubuntu virtual machine with no 3D hardware support (as VMWare doesn't have 3D acceleration for linux-based VMs at the moment) I think it is a pretty good improvement.
That being said I have chosen to go with the bounding object method for the time being and am hoping to modify it, or otherwise find a way to further speed it up at some point in the future (this thread may help with the theory there). As the game progresses though I could have up to (absolute maximum, also impossible to reach) 8 million blocks to look through and cull out before drawing to the screen, so a quick and efficient method of narrowing the selection is essential.
Now, to the discussion: What types of tricks do you employ when needing to cull out objects quickly? What have you found to work nice, and what is simply more headache than it is worth? How many objects do you typically draw to the screen at a given shot? What types of cutoffs do you use?
And, for getting this far, your prize:

Yes, that is a nice, simple visual representation of the two methods I spoke of above. Enjoy.