   Octtree Object List
  Hi guys,I am implementing an Octtree into my 3D FPS game and I am trying to find a fast efficient method to generate a list of visible worldobjects within the octtree. The tree is fairly standard and consists of nodes and each node knows its parent node and its 8 children nodes, it also has lists of whatever game objects are contained within the node either partially or fully.What I want is a quick method to take all this information perform a frustum cull on the octtree and produce a list of visible objects with no repeats. I have been trying to think of good ways to do it and have come up with a few but I dont really think they are the best. So I thought I would ask the experts as I always do when I'm stuck on these things!Thanks guys.   
  Just to add, the current way I thought of doing it would be to traverse the list until the current (parent) node has all its child nodes visible then you could just take the list of worldobjects contained for this (parent) node and head back up the list recursively.Keep doing that until we arrive back at the root node, this would generate a list of lists i guess you could then loop through that as that would be your list of visible objects to draw, but this does mean there would be potential for repeated objects...Any help appreciated!Cheers   ;  my usual approach would be to set a frame id for each visited node / object. if it's already been visited in the same frame, skip it.   ;  You check the frustum against the bounding box of the node. and then draw the visible nodes. Here is a small code:std::vector<OctreeNode *> visibleNodes; //somewhere inside world or renderqueue classvoid RenderQueue::OctreeInFrustum(OctreeNode * node) { if(BBoxFrustumTest(node, frustum))    if(!node->meshes.empty()) //don't add node if there is nothing to cullvisibleNodes.push_back(node); for(int i = 0; i < 8; ++i) OctreeInFrustum(node->child);}Quote:What I want is a quick method to take all this information perform a frustum cull on the octtree and produce a list of visible objects with no repeats.what do you mean by saying with no repeats? If I understand you correctly, the problem is in your object adding. You need to check if the object overlaps two or more nodes, insert it into parent and remove the object from child ones (where they exist) - Good for dynamic object adding. For static object adding its better to split the mesh into parts where no mesh overlaps any node.   ;Quote:what do you mean by saying with no repeats?i figured he meant when an object is referenced in more than one node.@Maddius have you looked into kd-trees? they behave kind of like octrees without all the empty nodes.   ;  There would be no repeat test(frustum culling of node) on any node if you are using octrees.I would assume you already know how octrees get made. Repetition would virtually be impossible since you check the parent before the child as the parent would always enclose all the 8 children on its own bounding box.  So if the parent is outside the frustum, all the children are outside the frustum.The only repetition I could see are triangle overlaps inside each cell.Here's a visual demo(and source):http://rel.betterwebber.com/junk.php?id=88And some visual representation of the octree(quadtree actually) creation in 2d.http://rel.betterwebber.com/mytutes/octreetute/octree_tute.zip   ;  Yeah I get the idea behind octtrees and my current implementation divides the space up as expected using a recursive function so you can filter down information throughout the tree just by adding things to the root.What I meant by repeats was if an object overlapped many nodes, I have it so that all nodes maintain a list of all worldobjects that either are fully contained in the node or partially, this is because I will be keeping track of the node the player is in for collision detection etc, so I must know all the worldobjects to consider whilst in a given node.But I see now for the visibility check this would not be desireable because each node will possibly have repeats in it! What I need to do is construct another list per node which is just the worldobjects that are totally contained within the node, but cannot be totally contained by any of this nodes children.So then I can frustum cull the whole tree and pick up its unique worldobjects that are fully contained in this node and this node only, which would provide me with an accurate list!Thanks guys, I think that should do I will give it a go later today!   