Archived

This topic is now archived and is closed to further replies.

Culling Objects in a Space Sim?

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

Ok, I understand the octree and such. But how would one go about culling objects from a view if the objects are always moving? Wouldn''t building an octree each turn be expensive? Anyway, here is my idea/worst case scenario so far and I would like thoughts on it. Scenario: Enveloped in >100,000 asteroids. Idea: 1.) Camera class creates the frustum for the view. 2.) Pass that to the world class so that it can cull fragments. 3.) Camera iterates over possibly visible objects- frustum culling them or drawing them as needed. Fragments: Every frame the world creates fragment BBOXs of objects (by a granularity). Fragments are updated only if something in them moves (flagged). Whole fragments are culled from the view based on intersection with frustum. Logic on fragment building: 1.) Create an initial fragment BBOX around first object. 2.) Loop through objects: if object is in base fragment add it''s pointer. If object is outside test next fragment or make new one as needed. there must be a better way to do fragment building... maybe octree generation would be just as fast? any ideas welcome

Share this post


Link to post
Share on other sites
this is quite similar to the dynamic sphere tree proposed by I-don''t-remember-the-name in the Games Programming Gems (I think it was edition 2). So, you build a tree, and the first step, you bound objects which are close together in a branch. as objects enters the branch, they get added. if they were part of another branch, the branches are merged into one. If an object leaves it''s branch boundary, it creates a singular branch. the parent size if updated, until the object enters another parent branch, ect...

it''s quite tricky, but apparently, it''s efficient, although I never really tried the idea.

Share this post


Link to post
Share on other sites
If the player is enveloped in 100k asteroids, he''s unlikely to notice if they aren''t all moving in a perfectly newtonian fashion.

Therefore, one option, is to just throw away asteroids that are out of view, and create new ones as they come back into view, to keep the density of the asteroids that are in view approximately right w.r.t the number you want the player to believe exist.

Things that don''t matter to the player don''t need to be modelled.

Mark

Share this post


Link to post
Share on other sites
I am planning a space game myself, but you are further along the road perhaps. Anyway, here are a few thoughts off of the top of my head. Hopefully, they are even useful.

Rebuilding any complex structure each frame with 100,000 moving models sounds like a bad idea(tm).

So how about

1) Billboards, billboards, billboards. Asteroids and planets can all can be billboards when far enough away. Also be sure to have LOD for ships and such

2) Only update some of the background objects each frame. I assume here that asteroids and planets don't move all that fast compared to... say ships and missiles and such anyway. Maybe break them into 'A' virtual groups and update one group per frame.

Implimentation... Maybe an array of size 100,000 (ouch)

offset = frame# mod A
for (i = offset, i < 100,000, i = i + A)
{
// re-do to un-roll this a bunch perhaps
update just those objects
}


3) Solar systems tend to have objects only around the ecliptic(sp?) plane so a '2d' scene graph may be okay for your numerous simple objects.

4) How about a straight up fixed 2d hash structure that rigidly divides up the solar system (or game area). Advantage computation is cheap. (current x coord / max X) * number of blocks in X dimension of hash, ( z coord / max Z ) * number of blocks along Z coord. If new hash coords are not different from old ones (usually I assume) then do nothing scene graph wise, else move object from one hash location to another. It should be easy to test frustum against this to eliminate most of the blocks... Hmm, second thought, maybe make it 3d anyway, have to think about size of 2-D (or 3-D) hash table as well.

5) As I think about it more. How about generate asteroids like a particualate fog composed of layers of billboards with 40-50 in each when at a distance, but then when close, procedurally generate their individual positions using a collection of 100 or so models. Yeah, way better than 100,000 things to track. ;-)




[edited by - Gladius on March 25, 2004 12:05:21 AM]

Share this post


Link to post
Share on other sites