Hello. I'm looking for a way to improve my frustum culling. There are two main problems: Culling objects and culling large patches of static "terrain".

My current object culler simply loops through all objects and checks if they're inside the frustum. I believe some kind of data structure would be good here, but it would need to be able to handle any number of objects without any restrains. All objects can move around, so the structure would need to be recreated or updated each frame.

I will also often have large patches of static terrain geometry. This geometry can also be anything from a cave to a gigantic tower, so it needs to be able to handle any kind of geometry. Basically an efficient triangle culler using a precomputed structure.

I've tried Googling but I can't find much interesting. I've had very bad experience with quad/octrees and dynamic data, and the only thing I can find for terrain was BSP trees and portal-based systems, both which are only efficient for indoor data. I just need to be pointed in the right direction...

What about keeping track of changes that have occurred in a framestep?

Instead of iterating every single object that has been initialized, reduce the work to only things that need to be modified, if you happen to have the whole lot move at the same time then so be it, but if there is relatively small number of changes in a massive list of objects then you could really see some gains

Octrees work fine with moving objects. It is just a question of implementation. They also handle pretty well large number of stored objects. Depending on your implementation, you can make them handle an arbitrary amount of objects.

When you say "recreate every frame" does that mean that all objects move large distances every frame?

- In order to save some computing power, you should maybe update your spatial structures at 30hz frequency.

- with quadtrees / octrees, dynamic objects for example don't need to be updated if after moving they are still inside the same node

- a simpler solution than quad/octree could be sort of fixed size grid, which should work well enough for small scale worlds.

Cheers!

Short answer: Don't use any specific data structure for your dynamic objects. Use SIMD to cull up to four boxes at once from an array/vector, see http://dice.se/wp-content/uploads/CullingTheBattlefield.pdf. There is also a thread that shows a sample implementation somewhere around here, though I don't have a link. The reason being that you save all the overhead of managing a structure and using SIMD with that technique mentioned here is way faster already than you could get otherwise, you'll see when you read the link.

...There is also a thread that shows a sample implementation somewhere around here, though I don't have a link....

Here maybe? http://www.gamedev.net/topic/641033-is-my-frustum-culling-slow/

Here maybe? http://www.gamedev.net/topic/641033-is-my-frustum-culling-slow/

Yes, thats what I've been refering to. Especially page 2, which features the sample code I mentioned.

Interesting! And surprising! I was sure there was some good technique for improving object culling, but it seems like simply brute forcing is the way to go? I'm afraid I'm developing the game for PC exclusively using Java, so many of those low-level optimizations are sadly useless for me...

To elaborate a bit, my current solution simply loops over all frustums and checks all models for each frustum. In a stress test I had 501 objects that needed culling and a total of 331 frustums (55 shadowed point lights with 6 frustums each + the camera frustum). This resulted in a total of 165 831 frustum tests. This culling takes 2.9ms when done on one thread, or 0.6ms when done on 8 threads on an i7 4770K (quad core with hyperthreading), with just under 5x scaling. Since all but one of the frustums are relatively small, at least 90% of those tests could be avoided using some kind of data structure, and I was under the impression that the cost of the data structure would be amortized by the improved culling of all frustums. I'm not exactly sure how well that relates to other implementations, although in the thread Belfegor linked 10.000 objects took 0,53 ms.

Putting that aside, what would be the best for culling a large number of static arbitrary triangles? A precomputed octree perhaps?

With single camera brute force is optimal for totally random objects. It's just O(N) and all data structures at least need O(N) to be rebuilded. But if you have that many cameras compared to objects, some kind of acceleration data structure could help you a lot.

Are you already frustum culling those point lights? Are you doing range check for objects before starting to frustum cull objects by your point lights frustums?