Hello,

I have a simple question: How do I know, which objects I have to render, when I have a frustum set up?

Background to my understanding:

So far I have a matrix and a vector class. I want to write a simple renderer with C and SDL2. I know how to project points from within the frustum onto its near plane (screen coordinates). At this point I'm wondering about the above question. I could just manage a list of all meshes/objects and check, whether they're within the frustum or outside, but that can't be the right way can it? Since the list might grow very very huge.

Any hints?

What I've seen done in another engine, I believe, is to keep a tree of objects, and to have for each node in the tree a set of bounds that encompasses the bounds of all nodes below it.

This allows one to start one's culling at the base of the tree and work one's way through it, only moving down a branch if the bounds of the current node are found to overlap the frustum. (After all, if the bounds of a given node, which encompass the bounds of the nodes below it, doesn't overlap the frustum, then the bounds of those lower nodes presumably won't overlap either.)

This potentially allows one to exclude large portions of the scene early in the process, thus potentially significantly reducing the number of elements to be considered.

While a tree-based solution as suggested above is more optimal than checking every object in an asymptotic sense, O(logN) instead of O(N), the tree will have a high constant overhead due to the management overhead associated with maintaining the tree. In fact maintaining the tree may be O(N) anyway, because you need to check if every object has moved.

I would bet that brute-force culling will win over a tree until the number of objects gets in the 10,000+ range. Culling is just point-vs-plane distance tests, which are just a few instructions per plane using SIMD. Unless you already have a tree structure for some other reason, I'd advise to stick to brute force culling for its simplicity and speed for typical numbers of objects.

hypersleep said:
I know how to project points from within the frustum onto its near plane (screen coordinates).

But this is not how you (usually) do frustum culling. It's more common to have a bounding volume per object (oriented bounding box, axis aligned bounding box, or bounding sphere), and testing this to be inside or intersecting the frustum pyramid. There are some variants of such test easy to find, e.g. this: https://iquilezles.org/articles/frustumcorrect/​

Aressera said:
While a tree-based solution as suggested above is more optimal than checking every object in an asymptotic sense, O(logN) instead of O(N), the tree will have a high constant overhead due to the management overhead associated with maintaining the tree. In fact maintaining the tree may be O(N) anyway

Because of that, you may use a tree (likely a BVH) only for the static world, so no need to update it, and brute forcing the dynamic objects.
Or you have other uses for the tree es well so the cost is worth it, e.g. collision detection, range queries for AI, etc.

If your object count is really huge, you might want to do it on GPU anyway, see ‘GPU driven rendering’.

Thank you for your replies. The question is not about frustum culling. It is rather about how to know what to cull. Or phrased differently: Which objects do I have to check for frustum culling?

I'm thinking about managing a list of all objects and sort them by their distance to (0,0,0). Then I would take the camera position and check all objects in the list between the camera position and the four corners of the far plane of the frustum. That way I can drastically reduce the number of objects to check and I would do frustum culling for each object that has a distance between those.

Does that make sense?

I can't really see how a tree is better here because if the camera moves/turns, the order of the tree is wrong.

hypersleep said:
I'm thinking about managing a list of all objects and sort them by their distance to (0,0,0). Then I would take the camera position and check all objects in the list between the camera position and the four corners of the far plane of the frustum. That way I can drastically reduce the number of objects to check and I would do frustum culling for each object that has a distance between those.

For scenes of reasonable size, I imagine that this could work.

(I suspect that it would hit problems with very large scenes, however, as all nodes would have to be checked.)

hypersleep said:
I can't really see how a tree is better here because if the camera moves/turns, the order of the tree is wrong.

The order of the tree doesn't really depend on the position or orientation of the camera: it specifies the overall bounding-boxes of the nodes in the scene, which remain the same regardless of the camera.

Its advantage is that--depending on the structure of the scene--it allows one to potentially discard large numbers of nodes without investigating them at all.

Another advantage that occurred to me is that it enables one to have hierarchical transformations in the scene: nodes can be moved, rotated, etc. by nodes above them, allowing one to create complex relationships that can--so I've found at least--prove useful at times.

Naturally, this doesn't relate to culling, but it does introduce a “two birds with one stone” advantage: from one element the engine gains access to two features.

I would start with basic frustum culling, by doing a bounding sphere check against the 6 frustum planes. There's enough tutorials on this around the web. If you get this right and your worlds become larger, you can start looking into spatial subdivision, like quadtrees.

hypersleep said:
How do I know, which objects I have to render

doesnt matters, far objects are smaller, therefore barely eating your fps. cull out the polygons behind and thats enough.

Geri said:
doesnt matters, far objects are smaller, therefore barely eating your fps. cull out the polygons behind and thats enough.

But smaller objects means you need more far objects than near objects to fill your screen.
More but smaller objects further means processing more vertices per pixel, having more idle GPU threads due to small triangles, and having more draw calls and state changes.

So that's really a bad argument i think.
Frustum culling alone is already a bad solution, because what we really want is occlusion culling.
So this bad solution should at least be as effective as it can be, and a proper frustum check vs. a single plane check should be worth it in the general case for 3D games.