Ok, I know I asked this one earlier, but I kind of asked it wrong. If i have a uniform grid, say 512 by 512 by 512. And i have my view frustum, is there a quick method to tell exactly what portions of hte grid im looking at? I dont so much need to find grid alighned objects, just a fast method to actualy cull down the grid, to what is visable, any suggestions?
You may want to do try something like an octree and nested tests.
You could also try 3D rasterization of the frustum volume to a bitmask of that size.
Had this problem myself making a modeling program. I couldn’t figure out a solution for it, and ended up drawing the grid in 2d. See thetool.polyfrag.com if you want to see some code.
Iniitially, I had the same idea as dorbie, but 512^3 is an awful lot of bits. You should probably do some kind of hierarchical triage thing first.
If you’re going to the “rasterization” you can rasterize at a lower rez (say 64^3) and determine which chunks are completely contained and completely excluded, and refine for the boundaries. Unfortunately, 3-D rasterization isn’t accelerated by OpenGL…
A simpler option would be to compute the bounding cone (or cylinder…really the same thing in projective space) of your frustum. Now, perform inclusion/exclusion checks between bounding spheres of your octree-esque 3-D hierarchy. Don’t consider trivial accept/reject. You may want to refine the boundary cases, or you may just conservatively accept them, but if you do the latter you might as well use a lower rez grid.
BTW, www.flipcode.com or www.gamedev.com is a better place to ask.
-Won
Yep you’re right, it’s 16 MB! I did somathing similar in a different problem space but that was only 256^3. I was figuring if you got some RLE scanline thing going it wcould be quite fast but it’s a lot of data.
You probably gotta go with an octtree represenation or similar. Doesn’t matter how fast your algorithm is, you probably don’t want to touch all 16MB.
How about that scanline thing? Just do a 512x512 array with start and end points. It’s always going to be contiguous for a frustum, it’s manageable size, simpler than a quad tree and the rasterization of the plane equations could be fast. In fact you could use hardware :-), it may not be the best option, but you could draw the frustum frontfaces to a 512x512 buffer in ortho mode then the back faces. Instead of doing readback twice I’d be tempted to use fog or simpler yet vertex colors holding depth values, and writemask to separate components. Hmm… but you need 9 bits of precision back. Look at what you can get back from an offscreen buffer on newer hardware. A luminance alpha buffer with 9 bits or better would do it.
You end up with a 512x512 array of start and end depths in the frustum volume and that’s enough for fast culling discrimination for any cell.
You may have to pad all the frustum volume plane equation widths by a half a cell diagonal, it depends on the test you do subsequently.
Haha. That’s a cool idea! If you used a fragment program (or just register combiners and vertex programs?), you can render it all in one pass if you disable face culling. You can pack the front faces in RG and the back faces in BA, like in HILO16. You don’t even want/need depth buffer/testing or anything.
Valid “ranges” are when RG < BA, so you just need to clear the color buffer to something where BA < RG. Coupled with PDR or image buffer objects, you might even download this fast enough!
Cool… 
-Won
You’d also have to worry about clipping z near/far clipping. Come to think of it, this is alot like stencil shadows, except mercifully this rasterization occurs in a parallel projection, so you don’t have to worry so much about depth clamping or infinite clipping planes.