Archived

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

is it alright to do this ?

This topic is 5455 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

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 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 on other sites
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?

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 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 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 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 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 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

1. 1
2. 2
Rutin
22
3. 3
4. 4
frob
18
5. 5

• 33
• 13
• 10
• 11
• 9
• Forum Statistics

• Total Topics
632566
• Total Posts
3007107

×