   Octree Search...
   Hi,   I''ve posted this question a couple of days ago on the beginners board but got no answer. Since it''s not on the main page anymore, i guess this is not a cross post ;-).   Maybe you here could help me on this...   Thanks.quote: It''s usually common the need of processing the visible objects of a scene more than once per update (e.g. for collision, shadow calculations, etc...). How do you procede in these situations? You go through the Octree more than once on the fly? Or should be better to build a linked list of the visible objects at the fist run at that frame, and then use it for the former processings? Thanks!   
  Why don''t you cache visibility on the first pass through, and then simply check the visibility flag through each check?Depending on how your recursion is structured, it could be fine just to do that. ;  If you need multipass aproach then in 1st pass just send nodes to some list and then do passes while iterration over that list.   You should never let your fears become the boundaries of your dreams. ;  random thoughts: class QNode {  Chunk* Data;  QNode* next;};class RenderQ {  QNode** Nodes; //will waste memory for speed  QNode* PriorityQ;  int currentPos;  AddNode(Chunk* chunk) {    QNode* tmp=PriorityQ;    while (chunk->texID < tmp->texID) tmp=tmp->next;    Nodes[currentPos].Data=chunk;    Nodes[currentPos].next=tmp->next;    tmp->next=&Nodes[currentPos];  }};probably full of bugs, but the main idea is: store a large enough vector to put list/queue nodes in to avoid them being allocated and freed all the time (except you notice your stl implementation is smart enough to do that). in your next frame you just set currentPos=0 before doing the visibility test and link to the new first item in the list.if you already use a more complex hierarchy for states etc. you can ignore that of course, if not, the textureID or maybe the camera distance might be useful priorities (or both, first texID then distance). ;  I was faced with the same problem just yesterday - although on an entirely different scale.I decided two days ago I would wip up a little asteroids clone, and just for the hell of it I would use a quadtree to determine where and when objects should be checked for collision.I know you said octree - but the same rules apply.All I have done is added an array into my quadtree node that holds a constant value (MAX_NODE_OBJECTS), each frame as all game objects are updated they are put into the tree.After all objects have been updated I can then test for collision between objects that share the same nodes (note in a quadtree its possible for an object to lie within 4 nodes at the same time when crossing, in an octree this could possibly be 8).Here is a little rendering the quadtree so you can visualize how this is working:http://xout.blackened-interactive.com/dump/new/asteroids.jpgThe crosses in the background represent the tree - brighter colored crosses means there is an object in that node.I''m not sure if this is the correct way to go about this, but it works fine and is real fast (at least in the case of Asteroids anyway).X-0ut ;quote: How do you procede in these situations? You go through the Octree more than once on the fly? Or should be better to build a linked list of the visible objects at the fist run at that frame, and then use it for the former processings?I have a feeling that building a new list of visible list objects will be much slower than just going through the octree several times per frame. Allocating and de-allocating memory is very slow in my experience.I think what Promit suggested is the best... if you just define a "bool bVisible" for each node, then at the start of each frame: go through the list determining which nodes are visible and which arn't and set bVisible accordingly.Note: you won't need to worry about what state bVisible is for children of nodes that have a state of bVisible = false, because those children will never be reached. So what i'm saying basically is don't bother going through your entire list setting bVisible = false for all the children nodes that arn't visible.   [edited by - SpaceDude on February 5, 2004 6:57:36 AM];quote:Original post by SpaceDude  quote: How do you procede in these situations? You go through the Octree more than once on the fly? Or should be better to build a linked list of the visible objects at the fist run at that frame, and then use it for the former processings?I have a feeling that building a new list of visible list objects will be much slower than just going through the octree several times per frame. Allocating and de-allocating memory is very slow in my experience.I think what Promit suggested is the best... if you just define a "bool bVisible" for each node, then at the start of each frame: go through the list determining which nodes are visible and which arn''t and set bVisible accordingly.Note: you won''t need to worry about what state bVisible is for children of nodes that have a state of bVisible = false, because those children will never be reached. So what i''m saying basically is don''t bother going through your entire list setting bVisible = false for all the children nodes that arn''t visible.   [edited by - SpaceDude on February 5, 2004 6:57:36 AM]Nobody said you need to actualy create new list each frame. You allocate it on first frame and the reuse same list all the time, using exponential growth if needed. And another good side of this that you can sort(by shader, b2f,...) you objects in list much simpler that using a tree. You should never let your fears become the boundaries of your dreams. ; Your posts have provided some great ideas!   Thanks to all!;quote:Original post by _DarkWIng_  You allocate it on first frame and the reuse same list all the time, using exponential growth if needed.But the size of the list will need to change each frame because the number of triangles/tree nodes in view will not be the same. What do you mean by exponential growth? ;quote:Original post by SpaceDude  But the size of the list will need to change each frame because the number of triangles/tree nodes in view will not be the same. What do you mean by exponential growth?   it means you DONT deallocate the memory all the time but keep it allocated for the next frame. if you find yourself needing more than you have already allocated you dont start allocating memory for single list items but double the memory you. (ie, if you had memory for 100 nodes you allocate memory for another 100 nodes).its not too different from what i suggested, just that its not allocating the maximum right from the start (number of visible leaves) but only when its really needed (which shouldnt happen later on as you usually just see about a 6th at once).also traversing a complex tree multiple times by following pointers can be pretty slow, if you miss the cache most of the time and have to traverse multiple levels just to get to your leaves. thats why i suggested the array with pointers connecting single items. for stuff you need to do for every visible leaf you can just iterate over the array (cache friendly) and if order matters you follow it as a list (ie for rendering etc.).all of these approaches will end up reserving more memory than necessary and especially the array if you cant set a good upper limit.