Jump to content
  • Advertisement
Sign in to follow this  
theagentd

Efficient frustum culling of static terrain and dynamic objects

This topic is 2075 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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...

Share this post


Link to post
Share on other sites
Advertisement


All objects can move around, so the structure would need to be recreated or updated each frame.
This is a quite steep requirement, data structures optimized for static geometry are often way less efficient when stuff starts moving.

I suggest a simple tree of AABB: as noted on this benchmark by Bullet this structure (light yellow bar) tends to become increasingly efficient (compared to others).

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

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!

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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?

Share this post


Link to post
Share on other sites

but it seems like simply brute forcing is the way to go?

That’s not where they were going.
An octree’s bad point is insertion speed, but there are bit hacks you can use to get around that, and while not quite as optimal in Java without pointer hacks, those pointer hacks are reproducable in Java and are not the main bottleneck in typical octree implementations—the search for the correct node is (which is solved instantly via bit hacks available in Java).
It can be based off the implementation for a quadtree that I documented here:

http://lspiroengine.com/?p=530


 

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

You always have the option of brute-forcing dynamic objects and using a static precomputed octree for the rest, yes.

 

 

L. Spiro

Share this post


Link to post
Share on other sites

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?

Edited by kalle_h

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!