is it alright to do this ?
Author
hi, im coding an octree system and my nodes arnt symetrical
in dimensions, ie. each nodes height is not the same as its width
ie.2 the nodes arnt perfect cubes.
is this alright to do?
is there any particular reason why the tutorials use cube shaped
nodes?
thanx for the input,
-- danushka
This is not okay as far as I'm concerned. For example a quadtree is like this :
1 base node which is divided in 4 nodes of same size, those node are then divided in 4 nodes, and so on, recursively, depending on the depth.
Now I'd like to know how you plan to divide one quadtree node in 4 parts, if you arent using 4 "perfect" cube??
[edited by - dopeflow on October 13, 2003 3:39:03 AM]
1 base node which is divided in 4 nodes of same size, those node are then divided in 4 nodes, and so on, recursively, depending on the depth.
Now I'd like to know how you plan to divide one quadtree node in 4 parts, if you arent using 4 "perfect" cube??
[edited by - dopeflow on October 13, 2003 3:39:03 AM]
Author
you sound angry 
i have a working version (seems fine to me).
what id like to know is, are there any advantages to having it
symetrical?
i have a working version (seems fine to me).
what id like to know is, are there any advantages to having it
symetrical?
There are techniques where the divisions occur on nonuniform divisions. One would be loose octrees or quadtrees. Another Idea is AABB trees. Sort of similar to the Octree or Quadtree but instead you are using a bound box to emcompass the nodes or geometry (in the case of a leaf). These can also "spatially" overlap.
There are some drawbacks though - if your Quad/Octree has rigid divisions that exist on boundaries that are a power of two you can completely remove recursive elements out of the code. This is because you can mathematically calculate which "node" you are in. This may be possible in a "loose" system but I have not had a chance to give it much thought.
Check out Flipcode, the Sim Dietrich slides from XGDC this year, GPG2 for other details and examples.
#dth-0
There are some drawbacks though - if your Quad/Octree has rigid divisions that exist on boundaries that are a power of two you can completely remove recursive elements out of the code. This is because you can mathematically calculate which "node" you are in. This may be possible in a "loose" system but I have not had a chance to give it much thought.
Check out Flipcode, the Sim Dietrich slides from XGDC this year, GPG2 for other details and examples.
#dth-0
why would it matter if its a perfect cube? if you have your octree and stretch it in one direction it wont be cubic anymore and still work.
i dont know why you would want it, but assuming that all your models are rather tall it might make kind of sense.
i dont know why you would want it, but assuming that all your models are rather tall it might make kind of sense.
You should make your trees so that in each subdivision you have (at least approximately) equal amount of objects in both children. This will guarantee O(n) memory consumption and O(log n) tree queries. This applies to all n sufficiently high, but having a little geometric criterion isn't bad.
For example, in photon mapping (from Jensen's book), the splitting axis is chosen to be the largest side of the AABB, and the splitting node is chosen to be the photon which has the median value in the coordinate of the splitting axis. This gives very fast (and low memory consumption) photon map queries.
- Mikko Kauppila
[edited by - uutee on October 13, 2003 12:12:04 PM]
For example, in photon mapping (from Jensen's book), the splitting axis is chosen to be the largest side of the AABB, and the splitting node is chosen to be the photon which has the median value in the coordinate of the splitting axis. This gives very fast (and low memory consumption) photon map queries.
- Mikko Kauppila
[edited by - uutee on October 13, 2003 12:12:04 PM]
Correct me if i''m wrong but arn''t box intersection test faster than cube intersection tests?
(where a box has same width,height,depth and cubes are any size)
Also by using boxes, each node only has to store the "size" of the node instead of a width,height,depth.
(where a box has same width,height,depth and cubes are any size)
Also by using boxes, each node only has to store the "size" of the node instead of a width,height,depth.
quote:Original post by Jimfing
Correct me if i''m wrong but arn''t box intersection test faster than cube intersection tests?
(where a box has same width,height,depth and cubes are any size)
You''re confusing cubes with boxes. It''s the other way round.
Non-uniform divisions can in most cases improve rendering/culling/whatever speed. The only real requirment is that a parent node completly encompases all of it''s children. Choosing regular divisions is very easy to code up, but that''s about the only benifit(only having to store a "size" doesn''t seem like too much of a gain to me).
I assume you have some method of finding the split planes for each octree division. The main thing you want to be concerned about is the number of polys in each division. Some other concerns could be the ratio of the box dimentions( something grossly non-cubic, like width = 1000, height = 1 would very rarly be all on screen at one time), groupings of similar textures...
Check the ABT threads (I think the search function is up and running) for a great explanation by Yann.
Karg
I assume you have some method of finding the split planes for each octree division. The main thing you want to be concerned about is the number of polys in each division. Some other concerns could be the ratio of the box dimentions( something grossly non-cubic, like width = 1000, height = 1 would very rarly be all on screen at one time), groupings of similar textures...
Check the ABT threads (I think the search function is up and running) for a great explanation by Yann.
Karg
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
