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.

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

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.

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:


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



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.

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.

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

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.

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.