3D tile visibility

[ugluk]

Currently I am using the following system for visibility determination of some 3D tiles, that cover the whole z = 0 plane:

- make an AABB of the frustum in world coordinates
- check for intersection with z = 0 plane, if not don't draw anything
- make AABBs of the tiles in world coordinates and check for frustum-AABB intersection in world space, if there's no intersection don't draw anything

By doing everything in world coordinates I only need to transform the frustum AABB from modelview to world space, otherwise I'd have to transform the tile AABBs into modelview coordinates.

Anyway, despite all the optimizations, my app still runs too slowly on old machines (about 20 fps) and I'd like to hear some ideas. Maybe I should be using spheres or calculate frustum-plane intersections exactly? The frustum is the linear perspective one.

[Dark Photon]

Anyway, despite all the optimizations, my app still runs too slowly on old machines (about 20 fps) and I'd like to hear some ideas. Maybe I should be using spheres or calculate frustum-plane intersections exactly? The frustum is the linear perspective one.

Yeah, spheres are dirt cheap. Depending on your frustum, can also be a win to do a sphere-sphere intersect (one being your frustum's bsphere) first before doing a proper sphere-frustum intersect (which often involves a bunch of sphere-plane tests).

Also, having a hierarchy to your spheres/boxes such as you get from BVH or spatial partitioning scheme is usually a huge win.

[carsten neumann]

Hierarchical culling is definitely the way to go, otherwise you only get an improvement if the render time of a tile is larger than the time to do the intersection test(s). Depending on the complexity of each tile that may be difficult to achieve.

[ugluk]

Ok, but in what situations are then AABBs useful?

[nickels]

I use AABB for 'broad-phase' collision detection with good results. I use the sweep and prune algorithm: Basically you keep three sorted lists of all the AABB's endpoints, by dimension (X,Y,Z).
After objects move, you sweep back through each list and do a bubble or insertion sort (I forget which...). While swapping, if a right endpoint crosses a left, then the two objects intersect in that dim. If a left end crosses a right, then you remove an intersection.
You then take the intersection of all three dimension's intersectees to get your potentiall set of intersecting objects.

If you only care about objects intersecting the frustrum, you could only add objects to the intersect pool if one of them is the frustrum....

works very fast for lots of objects on modern hardware....not sure what hope for older

I also have a higher level k-d tree each of whose leaves contains one of the sweep and prune sets described.... As objects intersect the outside world they are added to the adjoining k-d boxes and deleted when the leave....
I'm not sure about the frustrum, though. I haven't included it yet because: 1) It moves very fast, so many swaps?? and 2) it is very big and hence causes touching all groups of objects and enlarges the intersection test, above.

I also use view space AABB to do light occlusion culling and light screen space determination. I am a big fan of AABB !!

Is there a similar optimization like s & p for bounding spheres?

[ugluk]

I'd like to know, as both spheres and AABBs are rather simple, in what situation to use which.