octree problem
Author
hi i''m in the process of trying to nut out octrees, however I have come to a problem seemingly not covered greatly in texts. Having loading my mesh of say 1, 000, 000 triangles, hence about 3, 000, 000 points, how do i tell if a given node i s "full". That seems like a rancidly hideously impossible task!
Even worse, a node can be "full" without even having any vertices in it whatsoever! Say a brick wall going all the way through the middle of a level. The nodes at either end will have the corner vertices in them, but the nodes along the brick wall will probably have no idea that they are in a brick wall!
Am i making myself clear? I''m sorry if i''m not, but any (carefully explained) help would be most appreciated. What is the standard accepted procedure to test if a node is "full", or nearly so?
Cheers
dave
guess you wont get away with the lazy way and have to use triangles and not just points.
[edited by - Trienco on March 22, 2004 9:59:30 AM]
[edited by - Trienco on March 22, 2004 9:59:30 AM]
Author
Not at all, I''m willing to do it whatever way I can figure out! How on earth could i do it with points anyway, as a point could not "fill" a node? My understanding was that if a node in the octree was "full", ie completely contained an object, it is stored accordingly in the octree.
Can someone please enlighten me? My limited understanding has not been helped by any of the texts I''ve read.
cheers
dave
Can someone please enlighten me? My limited understanding has not been helped by any of the texts I''ve read.
cheers
dave
What you do is set certain parameters to limit what nodes are created i.e. things like max number of tris in a node or maximum tree depth. When creating the octtre if one of your bounding boxes is lying across polygon then you have to split the polygon up so you get one half in one bounding box and the other in another bounding box. So in your brick wall example if you got a bounding box in the middle of it it would split the wall up so a single section would be in the bounding box in the middle and rest in the bounding boxes either side.
Author
OK. So is this the right impression?:
1. A node is no longer subdivided when it contains a certain number of triangles
2. To test if a triangle is in a node, a bounding box around the triangle is used
3. If a triangle covers more than one node, it is broken up into multiple triangles.
Is all of this correct? Would anyone care to elaborate on any of these points?
Thanks very much
Dave
1. A node is no longer subdivided when it contains a certain number of triangles
2. To test if a triangle is in a node, a bounding box around the triangle is used
3. If a triangle covers more than one node, it is broken up into multiple triangles.
Is all of this correct? Would anyone care to elaborate on any of these points?
Thanks very much
Dave
I think it is not necessary to split he polygons up.
if a Polygon does not fit in a Node, go one level up. If it still does not fit, go one level up, ...
If you do not have to much big polygons this would not really decrease the speed, but if you have, you should think about something different than octrees.
if a Polygon does not fit in a Node, go one level up. If it still does not fit, go one level up, ...
If you do not have to much big polygons this would not really decrease the speed, but if you have, you should think about something different than octrees.
Author
Hmm okay. I thought octrees were done usually on an "object" basis, ie flower pots, guns, chairs etc rather than an individual triangle basis. Is that wrong/right?
Also, if done on a triangle basis, how do I determine that number of triangles a node must have before it is considered "full" and subsequently subdivided further?
Lastly, should i take a node and check it against all bounding boxes or should i take a bounding box and check it against all nodes? Does it matter?
Thanks so much for your help
Dave
Also, if done on a triangle basis, how do I determine that number of triangles a node must have before it is considered "full" and subsequently subdivided further?
Lastly, should i take a node and check it against all bounding boxes or should i take a bounding box and check it against all nodes? Does it matter?
Thanks so much for your help
Dave
In my current Octree I do not split polys, in fact my polys are stored in a dynamically allocated array - each node just keeps a list of which polys (or in my case brushes) that it holds (when I say list, I mean an array of double pointers, that link directly to the brushes).
Works fine for me.
Also, I keep splitting my nodes unless they are less than a minimum width.
I would say its pretty much upto you to build your tree how you want it, and what suits your game terrain best.
Works fine for me.
Also, I keep splitting my nodes unless they are less than a minimum width.
I would say its pretty much upto you to build your tree how you want it, and what suits your game terrain best.
pretty much that. there is no "and thats how you use octrees". the only thing about octrees is dividing nodes in 3 dimensions. nobody is forcing you to divide them exactly in the middle for example.
also: you dont stop subdividing when it reaches a number of triangles. you dont START subdiving, unless it has a minimum number of triangles. or objects, or city blocks or whatever your tree is based on. if all your objects have thousands of triangles you probably dont even want to think about going down to triangles. also, there is no rule if you split objects/triangles or place them in a higher node. dozens of variations try to find better solutions (loose octrees etc.)
theres one ugly and annoying concept: nothing is ever the "best" or "right" way to do something. if it was, nobody would do anything else.
if you want to use triangles, put them all in root node and have a function that subdivides a node if it contains too many triangles. or build the whole tree up to a depth limit, put all triangles where they belong and then "clean up" by removing empty nodes or combine nodes if they have too few triangles. no rules, just do it the way it works well for your case.
also: you dont stop subdividing when it reaches a number of triangles. you dont START subdiving, unless it has a minimum number of triangles. or objects, or city blocks or whatever your tree is based on. if all your objects have thousands of triangles you probably dont even want to think about going down to triangles. also, there is no rule if you split objects/triangles or place them in a higher node. dozens of variations try to find better solutions (loose octrees etc.)
theres one ugly and annoying concept: nothing is ever the "best" or "right" way to do something. if it was, nobody would do anything else.
if you want to use triangles, put them all in root node and have a function that subdivides a node if it contains too many triangles. or build the whole tree up to a depth limit, put all triangles where they belong and then "clean up" by removing empty nodes or combine nodes if they have too few triangles. no rules, just do it the way it works well for your case.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
