Culling system

quote:

---

Original post by Vendayan
.... use an array of nodes as opposed to an octree or quadree. This way instead of having to test node after node, I could simply make a function that would mathematically calculate which nodes are in the frustum and which aren''t because of thier uniform size and shape.

---

But even if you make a mathematical function to decide which nodes are in the frustrum, that function will still have to traverse every node in your array to test for this. See the problem?

To not test every node like you said is the reason why people use quad and oct-trees.

The functionality you are describing is what oct and quad trees do.

Tree data structures are always faster search algorithms over any type of array structure. Simply because you dont search every single node.

Since its a tree, if a certain tree node is not in your view frustrum, then every child of that node is not in the frustrum either. So in essence you are excluding huge areas of your world with every single node test.

This is MUCH faster than doing this in any sort of an array structure which will be really nothing but a sequential search algorithm. And sequential searches are notoriously slow algorithms.

no you see this function would more than likely test lines I suppose, I''d have to ask him though, but I believe It simply returns a structure that somehow, for each row in the array would return the number of nodes that would fit. e.g.

Node[23][4] through Node[23][15] might be visible on line 23. So when rendering it would remember that line and then start sorting the polys for rendering.

I''m not trying to say this is the right way, just trying to let you see how it can speed things up. The only reason you have to test the nodes of an octree is because you dont know where they are. But when all the nodes are of constant uniform size and shape, the engine can make some serious optimizations to exploit it.

But anyway, what other good ways are there of culling an extremely dynamic outdoor scene?

~Vendayan

Say for instance something like this?

void SearchNodes()
{
for ( x = 0; x < MAX_X; x++ )
for ( y = 0; y < MAX_Y; y++)
{
If ( IsInFrustrum( Node[x][y], viewFrustrum ) == TRUE )
SaveNodeForLaterRender( Node[x][y], currenFrameNodes[] );
}
}

Function IsInFrustrum() would get passed a Node and a view frustrum. Testing if such node is in the frustrum and return TRUE, otherwise returns FALSE

Function SaveNodeForLaterRender() stores each Node in a array. It would have to clear said array after each Render()

Then a call to another function maybe called SortNodes() to sort the array of nodes created by SaveNodeForLaterRender()

And then last a Render() function

So each frame would look something like this:

SearchNodes();
SortNodes();
Render();

Is this what you have in mind?

no, it would be more like...




This way I'm not testing all of the nodes, just a rectangle representing, one horizantal row of nodes, then by the intersection points I could figure which nodes are in the seen portion of that rectangle/row.

~Vendayan

[edited by - Vendayan on December 14, 2002 4:23:33 AM]

-----------------
Your System

About your nodes.

If they are big, your system might be rendering nodes if they are barely within frustrum. And if 99% of an box is outside the frustrum, you can either cull that remaining 1% (loss of data, "holes" in your world), or render the entire box(performance decrease).

If they are small (to reduce the loss of data), you''ll have a lot of lines, which means a lot of checks. And quite a hassle to maintain.

Besides, you might end up having many empty nodes (and lines). Checking and rendering so many lines for two 4-pixel-wide sprites might be quite a waste.

----------------
Better idea

So a good idea would be to keep the advantages of your system, but by refining it.

First, never look at nodes that are empty : never allow empty nodes.

Then, use big boxes to avoid performance loss due to lots of checks.

Finally, to avoid "holes", if a box is both inside and outside the frustrum, use smaller boxes for that area of your game space, again and again until you reach a chosen box size limit.

See where I''m going?

uh.. yeah, you defined a quadtree.

First of all NO nodes have to be checked to see that they are in a frustum, so if a node is empty, no big deal. It wont hurt me in the least bit, other than that I will have a 4byte pointer in an array to an empty node.

Second, if I find that a node is only marginally in the frustum, which is simply the first and last node of any row that is in the frustum (again no check required there), it shouldnt be a large matter to cull out the invisible objects in just a few nodes with bounding sphere/box checks.

I might also add in case I haven''t before that this is only my outdoor method.

~Vendayan

Then I agree with you, this is a good idea.

Would it be difficult to integrate this with an indoor system?

~Vendayan

I believe yes, it could be quite difficuly. Your game space is oriented (scanlines on your tiled terrain) a certain way. This does not prevent frustrum culling, but does make occlusion culling harder (since occlusion culling has to start FROM the player''s eye, and move in all directions, not only on scanlines).

Yet, you could, for each tile in the frustrum (you can detect these easily) check if they are (or not) occluded, and cull them.