Jump to content
  • Advertisement
Sign in to follow this  
solenoidz

Iteration hell

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

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..

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Clearing a std::vector<bool> like that could cause memory corruption, due to the specialisation that packs the bool values into bits.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!