   Octrees and Scenegraphs Part 2
  Hi,Like many others before me, I am trying to implement an octree, perhaps with a scenegraph as inspired by http://www.gamedev.net/community/forums/topic.asp?topic_id=464305Currently I have implemented a quadtree (i hope it qualifies as one) for rendering terrain (heightmap). The reason I could do it, essentially, is that I know before hand which vertex is in exactly which node, and the width and length of the terrain so I can effectively cull nodes that are totally outside of view frustrum. In fact the terrain being 2^n by 2^n is already is quadtree on its own.Moving on to octreees and scenegraph, I realise these information are not readily availble, so the solution is not obvious to me anymore =(PROBLEM:How does the Octree know which model/mesh is in which node of the octree? At the moment, all I can think of is to keep iterating over all the vertices for each model, finding the min and max vertex of the model and the assign to each leaf node a pointer to the model. And doing this whenever the model has transformed. I don't think this is correct.So, hope someone can give tips on how it is done?   
Quote:How does the Octree know which model/mesh is in which node of the octree? At the moment, all I can think of is to keep iterating over all the vertices for each model, finding the min and max vertex of the model and the assign to each leaf node a pointer to the model. And doing this whenever the model has transformed. I don't think this is correct.I'll just mention here that you wouldn't typically iterate over all the vertices of the model when  the transform or animation changes (in many cases this would be prohibitively expensive).Here are a few alternatives to consider:- Use an AABB that fully contains the model in any configuration.- Use a sphere that fully contains the model in any configuration.- Use an OBB.- Use an OBB, and compute a new AABB from the OBB when the transform changes (which is not a very expensive operation).   ;  Hi jyk,sorry if this is obvious, because i cannot see how i can compute an AABB or bounding sphere without checking every x,y,z. I could do this on initialization, but after that if the objects transform, i will have to recalculate that, isn't it?Imagine a long rod, for example, minimum 2 points can define an AABB (i think), so if I do a rotation, I would either have to re-iterate all the vertices again or, apply the rotation to the 2 points.. which then becomes it is no longer an AABB. (?)Furthermore, the long rod would occupy different nodes in the octree, so given the rotation, I also need to re-define which node the rod is in now.Can this be right?   ;  No, don't iterate through every vertex when your model move. There is a small trick:- Load your model (Player here)- Create your Bounding Box/Sphere (Box is better, when using 3D-Scales)... Game starts ...- Player moves -> Move the Bounding Box, too- Player becomes bigger -> Scale the Bounding Box, too- Player Rotates -> Rotate the Bounding Box, tooThere is no need to recreate it.   ;Quote:Original post by jakeseeHi jyk,sorry if this is obvious, because i cannot see how i can compute an AABB or bounding sphere without checking every x,y,z. I could do this on initialization, but after that if the objects transform, i will have to recalculate that, isn't it?Imagine a long rod, for example, minimum 2 points can define an AABB (i think), so if I do a rotation, I would either have to re-iterate all the vertices again or, apply the rotation to the 2 points.. which then becomes it is no longer an AABB. (?)Furthermore, the long rod would occupy different nodes in the octree, so given the rotation, I also need to re-define which node the rod is in now.Can this be right?You're right that computing a new AABB from scratch using the new transformed or animated vertices would be the most accurate method, generally speaking. However, in most cases this will be prohibitively (or at least unnecessarily) expensive, so faster approximations are usually used instead. (The methods I suggested earlier all fall into the 'faster approximation' category.)   ;Quote:The methods I suggested earlier all fall into the 'faster approximation' categoryThanks guys, I fully understand what are the 'faster approximation' and how to manage the boundng volume of a SINGLE mesh.What I am uncertain of is its relation with other nodes in a scenegraph or octree. I wish to know what is usually done to update the scenegraph or octree when a mesh/node changes position and orientation.for example in a scenegraph, if a child node scales, its AABB also scales and the parent AABB should also scale to fit the new child dimensions. in this way, it seems like a correct implementation is to propagate the transformation up the parent chain.function propogate(parent_node, child_node){    if(parent_node does not fully contain child_node)    {  make_parent_contain_child();    if(parent_node != root_node) propogate(parent_node.parent, parent_node);    }}is this how it is done or are there any better ways?the octree has a simpler case, that is when a mesh scales, it will occupy more nodes in the octree. so how do we update the octree with this information normally?// pre-req: tree is AAfunction update(aabb, tree[][][]){    x_min = (int)aabb.min.x / tree.cellsize    y_min = (int)aabb.min.y / tree.cellsize    z_min = (int)aabb.min.z / tree.cellsize    x_max = (int)aabb.min.x / tree.cellsize    y_max = (int)aabb.min.y / tree.cellsize    z_max = (int)aabb.min.z / tree.cellsize   for(x = x_min; x_min <= x <= x_max; x++)  for(y = y_min; y_min <= y <= y_max; y++)for(z = z_min; z_min <= z <= z_max; z++)tree[x][y][z].addMesh(aabb.mesh)}What other faster approaches are there?   ;  sorry can i bump this? hope to know if there is a better solution.. thanks.   ;  I don't have a definite answer for you, but I will go ahead and put in a recommendation for Christer Ericson's book on collision detection, which (IIRC) has a lot of good info on both bounding volume hierarchies/trees and spatial partitioning methods such as quadtrees/octrees.   ;  Hi jyk,Thanks for the reply. I finally got time to get back to this question.I'll check out the resource you mentioned. Thanks!