Sign in to follow this  
schupf

Which STL datastructure?

Recommended Posts

Hello!

I have a 2D grid (like a checkerboard) which contains many objects (spheres, boxes etc.). Each cell has a vector<Object*> to describe which objects are placed inside the cell. An object may touch several cells and thus can be referenced by many cells.

Now I determine which cells are potentially visible and I iterate over all these cells. Then for each cell I iterate over the vector<Object*> and check each object if it is visible. The problem: When an object is referenced by several cells, I also check the visibility for this object several times.
Example: Assume 2 cells: cell 1 and 2. Cell 1 references object A and B and cell 2 references objects B and C. I start at cell 1 and determine that both A and B are visible. Now I go to cell 2 and since I already know that B is visible I do NOT have to check visibility again.

How could I ensure that each object is only checked once? I thought about putting all Object* into a std::set<Object*> and then just iterate over the set and check each element for visiblity. I wonder if there is a better (aka faster) method?

Share this post


Link to post
Share on other sites
You could store some kind of flag in an Object that you could use to check if its already been flagged as visible or not, and if not then you could do your computation.

But if your computation is not a bottle neck, I wouldn't worry about it.

Share this post


Link to post
Share on other sites
I think you need to elaborate more on what you are using this data structure for to get a good answer. Right now there's not really enough information to say which is any better than any other structure. The only thing I'd guess is that it sounds vaguely like you might want to use a map or set, but your problem is too vague for me to give you any advice beyond that.

Share this post


Link to post
Share on other sites
This is quite simple (and not related to template libraries).
Let’s assume you are making one pass per frame to update the visibility of objects.

Start with a “master counter”. It starts at 0. For each time you make a pass to update visibilities, this increases by 1. Increase it at the start of the pass.

Each object keeps its own counter. When it is found to be visible, the object’s counter is set to equal the master counter. If an object’s counter already equals the master counter, you can skip the visibility check on that object.


The concept is simple. Objects are flagged as being already checked by having a matching counter with the master counter.
In order to unflag all objects, a naive approach would be to run through each object and set their counters back to 0. But that is clearly wasteful.
Instead, simply increasing the master counter unflags all objects with a single instruction. So for the next pass, every object will be checked again, but only once during that pass.


L. Spiro

Share this post


Link to post
Share on other sites
Only issue with that method is the number of states of the counter is finite (e.g. 2^32), so if an object is not visited for a really long time, the main counter will eventually overflow and end up incorrectly tagging it as visible... after ~2 years @ 60 updates/s anyhow. Which is not likely to be a problem, especially if the algorithm is a culling test and no crashing/glitchiness occurs in the event of false positives.

Share this post


Link to post
Share on other sites
The "IsVisibleToPlayer" flag Cornstalks mentioned is probably the simplest and fastest. Not to mention, the visibility flag would probably be useful to other game mechanics besides just rendering?

Share this post


Link to post
Share on other sites
[quote name='Cornstalks' timestamp='1317841208' post='4869496']
You could store some kind of flag in an Object that you could use to check if its already been flagged as visible or not, and if not then you could do your computation.

But if your computation is not a bottle neck, I wouldn't worry about it.
[/quote]

I would say, go with brute force to begin with. If this becomes a bottleneck, then go with a more advanced system. Try this system:

[code]
function draweverything()
FOREACH(Object o in objects)
o.drawFlag = false;
NEXT

FOREACH(Tile t in tiles)
FOREACH (Object o in stuff on that tile)
IF (o.drawFlag = false)
IF visibleTest(o)
o.drawFlag = true
draw that thing
ENDIF
ENDIF
NEXT
NEXT
end
[/code]


This type of flagging is all you will likely ever need. Trust me: this part won't be the bottleneck; a simple O(n) iteration over a bunch of stuff is stupidly cheap these days. Even several O(n) iterations in a row are stupidly cheap.

Your visibility test can do a frustum test, a bounding sphere test, or whatever you choose: in this case, false negatives are to be avoided at all costs, false positives are not the end of the world.

An alternative version of this, which is important if you want to use any kind of batching, is that rather than drawing inline, you add your object to a render list and then iterate yet another time, over that list. The extra CPU cost of doing yet another iteration, then sorting this list, is negligable, but you make serious savings by sorting things into batches.

Share this post


Link to post
Share on other sites
I don't know that I'd advocate adding a property to the object (in this case, a draw count or draw flag) unless it'll be useful for other things, otherwise you're just screwing up your alignment and polluting your cache lines.

You can use std::set, you're just not thinking about it in the right way. Iterate over the potentially-visible squares, and add all objects in visible squares to a std::set *before* determining visibility of each object themselves. Since it's a set, you can add an object which touches multiple squares many times but still end up with only one mention of it in the set when you're done. Now, you iterate over the std::set of objects, and this is where you perform your costly visibility calculations (and either remove non-visible nodes, or immediately draw visible ones). This ought to do what you're after, just by leveraging the standard containers. Of course, you'll want copying between vector and set to be fast, so a pointer or reference is all that's needed, be careful that no deep-copy of objects is happening, or you're likely to swamp your performance gains.

Share this post


Link to post
Share on other sites
[quote name='YogurtEmperor' timestamp='1317881541' post='4869687']
This is quite simple (and not related to template libraries).
Let’s assume you are making one pass per frame to update the visibility of objects.

Start with a “master counter”. It starts at 0. For each time you make a pass to update visibilities, this increases by 1. Increase it at the start of the pass.

Each object keeps its own counter. When it is found to be visible, the object’s counter is set to equal the master counter. If an object’s counter already equals the master counter, you can skip the visibility check on that object.


The concept is simple. Objects are flagged as being already checked by having a matching counter with the master counter.
In order to unflag all objects, a naive approach would be to run through each object and set their counters back to 0. But that is clearly wasteful.
Instead, simply increasing the master counter unflags all objects with a single instruction. So for the next pass, every object will be checked again, but only once during that pass.


L. Spiro
[/quote]


I guess this is a reasonable point regading efficiency, but you still have to add more data to each object which isn't useful for any other purpose, and even then it only makes sense if you already have/need a frame counter.

Share this post


Link to post
Share on other sites
This is a method I created independently many years ago but after that I saw someone posting about it and he or she provided a name for it (which I cannot remember).
It turns out to be a commonly used method for this type of situation. The irony is that I myself have never used it, even though I invented it.

It turns out that when one finds him- or her- self in this situation, there was an architectural problem from the start. In fact my method should not have a place in existence, but it serves well for those who would rather not completely revise their rendering algorithms.
Those who do use my method, however, should be aware that it is only a hotfix and proper design can prevent its necessity. At the same time I invented it I also realized why it should not be necessary. That is why I never used it myself.
But the original poster may find it beneficial to use it for results now and consider his or her change as part of the future. Proper structure ONLY comes from experience, regardless of how much help is given on these forums.


L. Spiro.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this