Archived

This topic is now archived and is closed to further replies.

silvermace

is it alright to do this ?

Recommended Posts

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

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites