CPU Frustum Culling

[bonsairobo]

What problem does this solve or what need does it fill?

Frustum culling is a pretty simple optimization where you put bounding volumes on your meshes and if a volume doesn't intersect the view frustum, you don't issue a draw call for that mesh. This saves a lot of vertex shader calls that would do culling on the GPU.

What alternative(s) have you considered?

This is a pretty standard feature for a renderer. I'm not aware of any better alternatives.

[aevyrie]

This is something I'm interested in working on, as I've been doing similar things for ray cast picking. To be upfront - if I did work on this, I would need some guidance when it comes to integrating with the renderer.

Edit: Some good reference material:

1. https://www.iquilezles.org/www/articles/frustumcorrect/frustumcorrect.htm
2. https://cesium.com/blog/2017/02/02/tighter-frustum-culling-and-why-you-may-want-to-disregard-it/

Edit 2021/02/08

I've started working on a bounding box plugin as a prerequisite for this work. It appears that to make progress on this task, we need:

1. Bounding volume generation and updating
2. Scene graph generation and updating
3. Frustum culling implementation

One of the nice things I'm finding so far is that it's relatively painless to make bounding volumes generic over a few types (bsphere, aabb, obb). Updating existing bounding volumes can make use of change detection.

Constructing and updating a scene graph is an open question, I'm not familiar with the best way of grouping mesh entities in a graph. I can see a few potential approaches:

1. Rely solely on parent child relationships as defined in the ECS hierarchy. This could be inefficient in cases with many entities in a flat structure
2. Build and update a BVH, such as an octree. This would work well for most cases, but may have more overhead?
3. A hybrid approach that places all top-level parents (any entity without a parent) in a BVH, and uses the children of these parents to generate the parent's bounding volumes.

As for frustum culling, this is a good reference: http://www.cse.chalmers.se/~uffe/vfc.pdf

I think to start, flipping the Visible component would be enough to test this out. We would probably want another marker component though, because the Visible component is something that only the user should mutate - we don't want a situation where we un-cull an entity that the user wanted hidden.

[aevyrie]

bevy.2021-02-22.22-54-36_Trim.mp4

I have a functioning CPU frustum culling plugin here: https://github.com/aevyrie/bevy_frustum_culling

This relies on the bounding plugin here: https://github.com/aevyrie/bevy_mod_bounding

This does not use a scene graph or any sort of BVH, instead, it simply runs culling in parallel with a par_iter(). Lots of room for improvement, but functional. I will need to wait on #1492 to see how marker components for visibility shakes out. A PR for this issue would be significant - it would require merging the bounding volume plugin first, which could require significant change due to broader engine needs.

In this contrived stress test with 64,000 water bottle meshes, I see an improvement of:
5fps -> 35fps = 7X faster

[alice-i-cecile]

Implemented by #2861 🎉