Jump to content

  • Log In with Google      Sign In   
  • Create Account


Efficiently Detecting if objects are out of screen?


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
16 replies to this topic

#1 OmarShehata   Members   -  Reputation: 198

Like
0Likes
Like

Posted 07 January 2013 - 05:11 AM

I have a small optimization problem in my game. If I have 10,000 objects in-game, but only 10 objects on screen (or no objects on screen), the game will lag, because what I do is I check every single frame, for every object, if the object is inside the screen or not.

 

So obviously as more objects are added, the slower things get. I thought about using some form of spatial indexing, so that if my camera is at (100,100), then instead of looping through 10k objects to know which are in-screen, I will simply ask my grid if there are any objects at 100,100, and do the same for neighbouring cells to get all objects inside the screen without ever having to loop, no matter if I have a thousand, or a million objects.

 

The problem, however, was that this doesn't account for moving objects, because if an object moves, I would have to check every frame if it has entered another grid cell or exited its cell.

 

So how do you detect which objects are inside the screen?



Sponsor:

#2 RobMaddison   Members   -  Reputation: 636

Like
5Likes
Like

Posted 07 January 2013 - 05:42 AM

You need some form of frustum culling. I do this with an octree which seems to work pretty well. Google quadtree, octree, etc, there are tonnes of resources about it.

Essentially, you hierarchically and spatially split your game world down by symmetrical (or not in some cases) cubes (your game world splits to 8 cubes, each of those 8 cubes splits internally to 8 cubes, and so on). When you have split your world down to some manageable degree, your objects 'live in' or are somehow associated with the end nodes (aka leaf nodes, the smallest cubes).

You then do some frustum culling by starting at the root node (the encompassing box) and recursively checking down through the children of each box. If you can't see a box in your frustum then you will not be able to see any of its children (and hence any objects within it) so it can be discarded. This way you can cull thousands of objects in one simple test.

A quad tree is a simpler, 'flattened' version meaning you dissect your world into 4 cubes instead of 8, probably more useful for things like terrain geomipmapping and the like (or if your objects all reside in more or less the same y coordinate area. If its a universe-wide type game with planets you're looking to occlude, id go with an octree.

Hope that helps.

#3 Aeramor   Members   -  Reputation: 1045

Like
2Likes
Like

Posted 07 January 2013 - 06:24 AM

Quad/Octrees are a good solution (and by far the most used solution to your problem) but you are correct, moving objects are going to have to be updated every frame anyway regardless of octree (but you could do half/quarter step updates on things far away or not recently seen) but in general you should be separating your objects into "dynamic" and "static". That way you only have to loop through your dynamic objects to check for updates, you can even have objects with the ability to change from static to dynamic and back again. (in the case of a physics engine anything with a velocity of 0 you can stop checking if it changed position). 

 

But my bigger concern about your question is the efficiency of your array and culling function. 10k objects/frame is *tiny* on any modern computer you should be pushing millions of ops a second. Probably my first question would be: is this 3D or 2D? Second: can you show us your cull loop?


-Aeramor

CTO at Conjecture, Inc.


#4 TheChubu   Crossbones+   -  Reputation: 3600

Like
1Likes
Like

Posted 07 January 2013 - 10:02 AM

Quadtrees are easy to implement (around 200 lines in Java). Google "quadtree frustrum culling" and you'll probably get some good information about it.

 

Try not to copy an implementation though. You need to know what is going on the quadtree for doing what you want to do (and for know what else you could do with a quadtree).


Edited by TheChubu, 07 January 2013 - 10:03 AM.

"I AM ZE EMPRAH OPENGL 3.3 THE CORE, I DEMAND FROM THEE ZE SHADERZ AND MATRIXEZ"

 

My journals: dustArtemis ECS framework and Making a Terrain Generator


#5 kauna   Crossbones+   -  Reputation: 2141

Like
1Likes
Like

Posted 07 January 2013 - 12:23 PM

The moving object problem isn't that bad. If you think for a while, you'll realize that you'll need to update only objects which move outside of the octree node. So, as long as the object stays inside a node, you don't need to change your spatial structure.

 

However, depending on the octree implementation, you may need to update the loose bound of nodes (and their parents) which contain moving objects.

 

Otherwise, if you have objects sparsely, a simple grid might work too. The problem may be that you cannot scale up (ie. increase the visible distance) a grid space spatial structure, since the amount of grid cells increase pretty quickly.

 

Cheers!



#6 Caius Cosades   Members   -  Reputation: 122

Like
1Likes
Like

Posted 07 January 2013 - 02:17 PM

In my 2d engine, this is how I chose to solve the problem:

 

First the interface for a generic spatial container ..

template <typename T>
class SpatialContainer {
   public:
      virtual bool insert(T item, const Range& boundingBox) = 0;
      virtual bool remove(T item, const Range& boundingBox) = 0;
      virtual void removeAll() = 0;
      virtual int getNumEntries() const = 0;
      virtual void getEntries(const Range& region, std::vector<T>& entries) const = 0;
      virtual const Range& getBoundary() const = 0;

      virtual ~SpatialContainer() {}
};

 

, where the Range class is just a rectangle, basically.

 

I made a Quadtree implementation, but you may prefer to use a simple grid instead.

 

template <typename T>
class Quadtree : public SpatialContainer<T> {
   // (implements the interface defined by SpatialContainer)
};

 

Then there's the WorldSpace class, which listens for 'entity moved' events and updates its spatial container accordingly. It only manages entities that have first been registered via a call to trackEntity().

 

class WorldSpace {
   public:
      inline void init(std::unique_ptr<SpatialContainer<pEntity_t> > container);

      inline void trackEntity(pEntity_t entity);
      inline void untrackEntity(pEntity_t entity);
      inline void untrackAll();
      inline void insertEntity(pEntity_t entity);
      inline void insertAndTrackEntity(pEntity_t entity);
      inline void removeEntity(pEntity_t entity);
      inline void removeAndUntrackEntity(pEntity_t entity);
      inline void removeAll();
      inline void removeAndUntrackAll();
      inline void getEntities(const Range& region, std::vector<pEntity_t>& entities) const;

      // ...

   private:
      static std::unique_ptr<SpatialContainer<pEntity_t> > m_container;
      static std::set<pEntity_t> m_tracking;

      // ...
};

 

 

Drawing all on-screen entities is then very simple:

 

vector<pEntity_t> visibleEnts;
m_worldSpace.getEntities(m_viewArea, visibleEnts);

for (uint_t i = 0; i < visibleEnts.size(); ++i)
   visibleEnts[i]->draw();

 

, where m_viewArea is the rectangle defining the view area.

 

If you're curious how I implemented the event system, I've written about it here.

 

 

Hope this helps



#7 wintertime   Members   -  Reputation: 1574

Like
1Likes
Like

Posted 08 January 2013 - 10:26 AM

I would try first to check if your program is cpu-bound already to not make it worse by complicated sorting on cpu. Then I would use a much simpler approach and just get a rough estimate whats inside the frustum, as the graphics card can do the exact calculations and it will do them anyway.

- Just have a bounding sphere for all objects.

- Calculate the distance of all center points to the frustum one time.

- Sort all objects into 3 buckets

1. inside->test only rarely (few seconds later or whatever)

2. could get inside soon->calc time for next test from (distance-radius)/max possible velocity->save it in the object

3. maybe there are far away things where you have some extra information (get some rough estimate for lower bound of time when they could enter the frustum)

- put some pointers in a priority queue sorted by next test time

- now you just have to retest a few things per frame from the queue when the current time is near the recalculation time you have in the object

 

Maybe refine this later to use current velocity to get larger retest intervals or velocity vectors to check if objects are moving away from the frustum and not towards it.

That should be easier than immediately going to a complicated datastructure like an octree which you maybe dont even need and could give you problems if you need to split objects at its artificial borders.



#8 bwhiting   Members   -  Reputation: 618

Like
1Likes
Like

Posted 08 January 2013 - 11:45 AM

http://blog.bwhiting.co.uk/?p=362

 

If you click the link on the page above to go to the demo then press the "+" key to start adding objects, you should see that you can smash though the 10,000 (not on screen but in the world) barrier no sweat barely a millisecond of time on my machine (which isn't amazing or anything)

 

Not to mention this is actionscript 3, EASILY 10 time slower than most normal languages.

 

All I am doing is fast frustum culling with caching.

see this post:

http://blog.bwhiting.co.uk/?p=355

 

b



#9 Caius Cosades   Members   -  Reputation: 122

Like
1Likes
Like

Posted 08 January 2013 - 01:15 PM

http://blog.bwhiting.co.uk/?p=362

 

If you click the link on the page above to go to the demo then press the "+" key to start adding objects, you should see that you can smash though the 10,000 (not on screen but in the world) barrier no sweat barely a millisecond of time on my machine (which isn't amazing or anything)

 

Not to mention this is actionscript 3, EASILY 10 time slower than most normal languages.

 

All I am doing is fast frustum culling with caching.

see this post:

http://blog.bwhiting.co.uk/?p=355

 

b

On my crappy computer I get a frame rate of 8 with 10,000 objects. Also, the objects appear 'flat' and unlit; I see no evidence of normal mapping. I think my computer sucks =) .. but this actually makes me happy, because it means that the game I'm developing (in which I'm getting frame rates of around 80) must be performing very well. I think the bottleneck is the fill rate, because when I shrink the window it speeds up considerably.



#10 bwhiting   Members   -  Reputation: 618

Like
1Likes
Like

Posted 08 January 2013 - 01:37 PM

8 FPS is pretty slow, I would wager that it is more your GPU that is slowing it rather than the culling though. (could even be falling back to software as even with 10,000 objects in the scene it should only be rendering about 800 meshes which shouldn't be too stressful)*

 

The time for culling should be displayed in the upper left (on my machine it would be about 1ms for 10,000 objects occasionally flicking to 2ms)

 

Forgot to tell you the controls, "m" to change materials, there are a couple in there one is normal mapped, and "n" to change the mesh you can see if how a higer triangle count affects things.

 

Just read you mentioned fill rate (one day I will learn to read a whole post before replying), this deffo makes sense as when you reduce the window size the culling if anything will have more work to do so yeah probably not an issue.



#11 OmarShehata   Members   -  Reputation: 198

Like
0Likes
Like

Posted 09 January 2013 - 08:07 AM

Thanks for all the replies so far!

 

To confirm, the game I'm working on is a 2D game.

 

So from what I understand there's really no one perfect solution that is going to fix everything, but combining all these different things to get the performance I need.

 

So I could implement quad trees, plus this "frustum culling" (which I'm guessing works just as well to 2D games as it does for 3D?)

 

I could also split my objects into "static" and "dynamic".

 

I could do as wintertime suggested, and have this sort of "probability" buckets, and not update some objects as much as others depending on how probable it is that they would be in the screen on the next update.

 

I'm using Lua with Love2D by the way.



#12 mhagain   Crossbones+   -  Reputation: 7328

Like
1Likes
Like

Posted 09 January 2013 - 07:45 PM

You then do some frustum culling by starting at the root node (the encompassing box) and recursively checking down through the children of each box. If you can't see a box in your frustum then you will not be able to see any of its children (and hence any objects within it) so it can be discarded. This way you can cull thousands of objects in one simple test.

 

Just adding to this: the opposite is also true - if a node is fully inside the frustum then all of it's child nodes are also guaranteed to be fully inside the frustum and you can skip testing for them too.  Child nodes only need testing where their parent intersects the frustum.


It appears that the gentleman thought C++ was extremely difficult and he was overjoyed that the machine was absorbing it; he understood that good C++ is difficult but the best C++ is well-nigh unintelligible.


#13 OmarShehata   Members   -  Reputation: 198

Like
0Likes
Like

Posted 10 January 2013 - 10:14 AM

The moving object problem isn't that bad. If you think for a while, you'll realize that you'll need to update only objects which move outside of the octree node. So, as long as the object stays inside a node, you don't need to change your spatial structure.

 

I wanted to ask about this. Even if the moving object is moving inside one cell, how do I know that? How do I know when it needs to be reassigned to a new node/cell if I'm not constantly checking if it's still within its node?



#14 Strewya   Members   -  Reputation: 1137

Like
0Likes
Like

Posted 11 January 2013 - 02:15 AM

have the entity trigger the recalculation each time it moves. maybe even go as far as have a pointer to the node/cell it's in, so each time it moves it checks if it's still in the same node, and if not, do the recalculation.


devstropo.blogspot.com - Random stuff about my gamedev hobby


#15 TheChubu   Crossbones+   -  Reputation: 3600

Like
0Likes
Like

Posted 11 January 2013 - 02:22 AM

I'd put something between the object and the data structure that holds the world together. Something that knows what to do with both, like a world manager or something like that. So the object has one object (or a list of 'em) to announce "Hey, I'm moving x units to this way!" And the manger says "Well, let's see what I can do about that buddy!" and they happily lived ever after.


"I AM ZE EMPRAH OPENGL 3.3 THE CORE, I DEMAND FROM THEE ZE SHADERZ AND MATRIXEZ"

 

My journals: dustArtemis ECS framework and Making a Terrain Generator


#16 kauna   Crossbones+   -  Reputation: 2141

Like
0Likes
Like

Posted 13 January 2013 - 07:25 AM

I wanted to ask about this. Even if the moving object is moving inside one cell, how do I know that? How do I know when it needs to be reassigned to a new node/cell if I'm not constantly checking if it's still within its node?

 

Each node should have 2 bounds, the strict bound (which comes from the octree subdivision) and the loose bound which is the strict bound + bounds of objects inside the node. 

 

For placing an object inside the octree you should find the node which contains the center point of the objects bound and which isn't smaller than the objects bound.

 

You know that the object is inside the assigned node by checking the object bounds midpoint vs. nodes strict bound. If the mid point is outside of the bound then you'll need to reassign the object to a new node. Of course your objects needs to be aware in which node it resides. 

 

Cheers!



#17 CC Ricers   Members   -  Reputation: 623

Like
0Likes
Like

Posted 14 January 2013 - 01:19 PM

[mods, please delete]


My development blog: Electronic Meteor




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS