How to do frustum checks for a QuadTree?

Started by
13 comments, last by Demus79 17 years, 10 months ago
Ok thanks for the input guys, so it sounds like you just HAVE to calculate the y height for all your nodes and keep things 3d. Its just a shame, because that means a LOT of my nodes are going to be entirely 'inside' the frustum (at least for the left and right plains, which are all I really care about since my landscape is mostly flat), HOWEVER either the top, far, or bottom plain will still CLIP these boxes due to their height (each clip results in at LEAST 4 more checks, potentially dozens more).

Well I guess thats how its done eh?

Im just wondering if anyone else sees a problem with this. Imagine a completely flat landscape with very short boxes for all your nodes, now imagine tilting the camera up sligltly so all those box are only partially in view. JUST like that youve gone from incredibly fast checks (most boxes were entirely in view, thus only one node check was required), to incredibly slow checks (now EVERY box has to be checked ALL THE WAY down to the finest leaf, simply because every single node is now 'partially in view').
Advertisement
Testing a box against the frustums should be pretty fast, even if you have lots of them.

Keeping the min and max height of your quads is useful for other reasons like projecting the difference into screen space to determine if you should change lod.

BennyW
Sure I never said checking a single box/node was slow, just unnecessary. But it does become somewhat slow when a node is clipped at some point along its height (which I dont care about, my landscape is flat), and then that one box check turns into at least 4 more box checks, and so on.
You could add another test where you check whether the 8 corners of the bbox are behind your left&right planes if so you don t have to do the frustrum bbox intersection further more

behind the planes means inside the frustrum, I have seen implementations that take the front side as the inside.
http://www.8ung.at/basiror/theironcross.html

Well the height issue will be always a problem. Consider that your landscape will have considerable height differences, such as Japanese terrain with mountains ranging from 0m to 1000m or more.

With a 2d approach you'll end up rendering non visible blocks. Actually, with the 2d approach you'll _always_ render blocks which may not be visible.

Don't worry, about the nodes totally inside the frustum. I think that they are the cheapest nodes after the totally outside case when concerning calculations.

This topic is closed to new replies.

Advertisement