Jump to content
  • Advertisement
Sign in to follow this  
DirectXFreak

Culling dynamic objects effectively

This topic is 4616 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

Greetings, I've been puzzling recently over an effective method for culling dynamic objects... By this, I could mean 1,000 asteroids randomly moving around the camera, or other similar instances. I've considered using an octree with uniform leaves, but this means I'd have to update every object with it's new cell as it's moved, which doesn't sound all that efficient to me. What algorithms can solve this problem effectively? Thanks!

Share this post


Link to post
Share on other sites
Advertisement
Hi,

Google for "occlusion culling" It's a hardware accelerated method to cull dynamic object (can be used for static object but those can be precomputed into octrees / bsp / pvs / ...)
It basically draw a simplified version of each object (usually a bounding box) and get back the number of pixels drawn on screen. If this number is less than a threshold (1 or 2 pixels for example), you can say that the object is not visible and not draw it.

Sorry I can't really help more, I never implemented this.

Share this post


Link to post
Share on other sites
Quote:
By this, I could mean 1,000 asteroids randomly moving around the camera

stick a BS around each asteroid and each frame check each asteroid against the camera frustum
u can also enable occlusion culling as well to refine the numbers (though with asteroids there prolly not gonna be much occlusion)

Share this post


Link to post
Share on other sites
Quote:
Original post by paic
Google for "occlusion culling"


Not wanting to be picky, but did you mean Occlusion Querys?

Occlusion culling can cover software and hardware algorithms.

There are many differeing ways, however the "simplist" to start you off I guess are....

a) if the scene is small enough, use a regular grid accross it. Linear time lookups, trivial to implement, but obviously not adaptive to the number of items in the grid.

b) As mentioned bounding sphere around each asteroid. Be aware you might not see much performance increase if you're not geometry limited and the asteroids are simple. Of course instead of sphere you could use a bounding box or anything else you have a fast and easy Object in View Frustum test for.

c) Occlusion Querys though I doubt they'll save you much if anything on a per asteroid bases.

As mentioned there are many many more options out there, but to start I'd have a go with option b) and see if it makes any difference. If it does then look into more efficient methods (or post back here and we'll pull up something a bit more orientated to your problem)

Hope this helps,

GOCP







Share this post


Link to post
Share on other sites
I'd recommend something like a loose dynamic aabb tree, I'm very happy with the performance of my implementation (even though it's not optiomized at all).
You can get some more info and demos in this thread.

Share this post


Link to post
Share on other sites
i just done a few tests
1,000,000 spheres against the frustum
15 MSEC best case (early out)
170 MSEC worse case
though u can prolly optimize even better than this

athlon64 2.0ghz

Share this post


Link to post
Share on other sites
zedzeek: Those figures doesn't say much, since there's no info on how many spheres where visible by average.

I agree that if you ONLY need to do culling once per frame AND most of the objects are visible say 50% or more, then brute force is the winner.
If you have a smaller number of objects visible every frame < 10% OR you need to do several frustum checks OR collision queries, then a hierarchial data structure is the winner.
In the samples I provided in the thread referred to above, I did three frustum tests of 10000 moving boxes in 0.5 ms (Intel P4 @ 2.4 GHz), granted the number of visible boxes is probably only around 1%. Furthermore it's slower to update the position in a more advanced data structure (than an array of transforms).
I still thinks it's an invaluable tool to have a dynamic spatial data structure that can be used for different queries when creating real games.
It provides for very fast overlap tests (used for collision detection), raycasts, frustum culling, occlusion culling etc.
I've worked on games were we wanted to have dynamically updating envmaps for the player car, but since we didn't have a fast enough way of determining which objects are visible in each of the faces frustums we had to abandon the idea (the rendering was actually fast enough, though simplified).

Just my 2c

Share this post


Link to post
Share on other sites
Quote:
Original post by eq
zedzeek: Those figures doesn't say much, since there's no info on how many spheres where visible by average.


the stat of interest is the worse case (where all objs are within frustum) the OP mentioned 1,000 objs
on my computer athlon64 2.0 this will take 0.00017 of a second (most likely it will be even quicker cause A/ objs will also be outside the frustum B/ the method i used could be optimized further eg inlining funcs, sticking the far frustum plane test at the end etc

my intention to the OP is to save him/herself the heartache of implementing some spatial sceme (which takes time + adds complexity) and then get the shock of his/her life when the app doesnt run any quicker. sure there are places where spatial division will make a difference eg raytacing/coldet

FWIW in my game i have spatial divsion implemented but have it turned off cause in reality it makes no differnce to speed

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!