Skip to main content
gamedev.net
🔒 Locked

Iteration hell

Started by solenoidz Nov 9, 2011 at 8:08 AM 6 replies 1.6k views
Original Post
solenoidz
solenoidz
Hi guys.

I have a rendering system, where every frame I iterate a list (std::vector<>) of objects pointers to change a particular “field”, (member variable) . For example, in the beginning of the rendering loop, I set all of my object to invisible, and then after traversing the octree, I set the objects that belong to a visible octree node(leaf) to visible in order to render them later on.

If I have something like this
Class object
{
bool b_visible ;
D3DXVECTOR3 v_position ;
} ;
std::vector<object*> g_pObjects ;

How can I fast change all member variables of the g_pObjects list b_visible to false, whitout iterating over the list like this
for(int i = 0 ; i < g_pObjects.size() ; i++) g_pObjects->b_visible = false ;

Can I do some smart memory copy operation with some kind of mask, in order to zero only the b_visible variables of the list without iterating over the list ?
Same issue appears when I try to render my impostors. I have an array of D3DXVECTOR3 for visible positions that is updated every frame, but then I need to update my vertex buffer positions so all the impostors be rendered with one draw call. How can I merge the array with the positions(3D vectors) with the array of 3D vertices that contain other stuff like texture coordinates, color etc..
patrrr
patrrr
Hi solenoidz!
You could keep a running counter for your game which you increment each frame. When traversing the octree to mark visible nodes, you just set a "lastFrameVisible" field of the node to the value of the counter. Then when doing the rendering, you check that the lastFrameVisible field is the same as the current frame. If you do it this way, you can skip the whole "reset visibility to false" phase.

You might also want to consider skipping the marking and just add visible objects to a new "visible set" list. You can also pull out the visibility field and put it directly in the std::vector like this:

std::vector<std::pair<unsigned long, object*>> objects;


Then you don't have to dereference the object pointer to get the visibility field, and the data will be more cache-friendly.
clb
clb
You can use a trick here. (I call this "coloring" from the context of being able to clear a hash table of PODs in O(1) time, but I don't know if there is a more standard definition)

Instead of storing a bool b_visible; member variable, store a variable unsigned int visibleFrameNumber; Initialize to 0 at object creation time. Maintain a global variable unsigned int curFrameNumber; and at the beginning of the frame, do



curFrameNumber = curFrameNumber+1;

if ( curFrameNumber == 0)

{

curFrameNumber = 1;

for(each object) object.visibleFrameNumber = 0; // Theoretically, must reset all colors to prevent wraparound problems! (if we ran for 4G frames!)

}



Then, instead of setting b_visible = true; you set visibleFrameNumber= curFrameNumber; and when testing if an object is visible, you do if (visibleFrameNumber == curFrameNumber) then visible; else hidden; This way you can avoid the whole loop over all objects in the scene.

Another method is to identify why you need to flag objects with these kind of information in the first place. What I do is I collect the set of visible objects into another array in my PVS query. That array defines the set of objects that are visible, but the objects themselves don't. So far, I haven't had the need to ask via the object "am I visible?", but I've asked it through the PVS query result array.

barsiwek
barsiwek
How about a Strycture-of-arrays approach instead og Array-of-structures?Split the data into two vectors (preallocated, fixed size arrays would be better):
class Object {
D3DXVECTOR3 v_position;
};
std::vector<Object*> objects;
std::vector<uint32> visibility;

Now each bit in visibility vector determines the visibility of the one object, you can clear the whole thing with memset and it's better for cache as long as visibility is used more often than the rest of data.
Antheus
Antheus
For example, in the beginning of the rendering loop, I set all of my object to invisible, and then after traversing the octree, I set the objects that belong to a visible octree node(leaf) to visible in order to render them later on.[/quote]

Have two lists:vector<D3DXVECTOR3> all;
vector<D3DXVECTOR3> to_render;

to_render.clear();

for (int i = 0; i < all.size(); i++) {
if (visible(all) to_render.push_back(all);
}

render(to_render);
No flags at all.

Optionally, put pointers into to_render instead of values.

Another advantage of such system is that rendering doesn't require any checks, so the resulting vector can be dumped as VBO or similar directly to GPU.
latent
latent
Another solution worth thinking about is to decouple the 'object' concept from your visibility state, and have visibility be a completely unique array. Now, when clearly the array, your original loop becomes
[source lang="cpp"]
std::vector < bool > visible;
//...
ZeroMemory(visible.data(), 0, sizeof(bool) * visible.size()); //uses an efficient block-memory cpu command if available
[/source]

Further, if you want to do something with visibility, you can now iterate like this
[source lang="cpp"]
bool *ptr = visible.data();
object *obj = objects.data();
for(unsigned int id = visible.size(); id != 0; id--)
*ptr++ = NewState(*obj++);
[/source]


As I understand it, the advantage of this approach is that the cpu can precache large blocks of memory for ptr and obj to iterate over, whereas complex pointer dereferencing doesn't lend itself to easy cpu optimisation.
rip-off
rip-off
Clearing a std::vector like that could cause memory corruption, due to the specialisation that packs the bool values into bits.
blog | twitter
solenoidz
solenoidz
Thank you people.
To be honnest, the Idea of splitting the visibility data of the objects into another array wasn't alien to me, but I thought it could add some additional complexity when I need to sort the objects, insert, remove etc..I also need to take care of the second array in order to match the objects in the first, with data with the second by index and stuff like that.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.