Jump to content
  • Advertisement

Archived

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

SirTwist

Space division -> what happens after octree?

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Ah, yes, me again . Well, I have a scene that is built of tetrahedrons. Up to 2 Million and more. So I built an Octree structure for space division and fast access. So assume I have 2500000 Tetrahedrons and wanna find out in which of them a point is located. So after the octree build up there are appx. 2000 Tetrahedrons left in the lowest tree branch. These 2000 Tets I have still to search through in an old-fashioned tet-by-tet order. Now my question is, are there any possibilities to speed this up, as well ? Thanks again ! Twist [edited by - SirTwist on March 5, 2004 5:54:55 AM]

Share this post


Link to post
Share on other sites
Advertisement
Try creating a deeper octtree so you have less tetrahedrons at the lowest level. But remember you don't want your octtre to be too deep otherwise you'll end up with worse performance. You may want to try it with a shallow octtre and testing a large amount of tetrahedrons and see how it peforms against a deep octtree testing only a few tetrahedrons.

[edited by - Monder on March 4, 2004 12:35:39 PM]

Share this post


Link to post
Share on other sites

grab a good data structures & algorithm book or maybe look online somewhere... it will tell you exactly how deep vs how wide a tree should be for various search methods & the complexity of the search.

what search method are you currently using?
what is your tree structured like?

I can tell you the best search for your tree, or perhaps the best tree for your search....

(assuming you only wanna change one of them)

Share this post


Link to post
Share on other sites
Ahem, I don´t know what you mean by ''what search method to I use now''. I am using the Octree and after I found the octree child that has my point inside AND splits no further I just go through all the tetrahedrons and test which of them has my point inside. So this last part of the search is very straight forward.
And what is my tree structured like ? I don´t really know what to answer here either. Are there different octrees ? It´s a bounding box with eight pointers to its childs which are in turn bounding boxes which each has 8 pointers to its child again ... and so on .... And every Bbox has a list of indices to the tetrahedrons that lie within it.

And I already tested several octree depths. The thing is I have to define criteria that let the octree build up stop at some point. Otherwise it would go on and on and on. You know ...

Cheers

Twist

Share this post


Link to post
Share on other sites
You might consider setting up your oct tree so that a node only subdivides when it has greater than a specific number of objects in it. That way you can precisely control how long your final search loop is, but sparsly populated regions wouldn''t have as great a search depth....

Share this post


Link to post
Share on other sites
I´ve already done that. But eventually the build has to stop, right.

The thing really is only about those last tetrahedrons that you get back from the octree search.

Twist

[edited by - SirTwist on March 5, 2004 5:54:16 AM]

Share this post


Link to post
Share on other sites
Well why not set the maximum amount of objects in an octtre leaf to be lower than 2000? If you set it to 20 objects and there was an equal amount of objects in every leaf you''d only have 5 or 6 levels in your tree.

Share this post


Link to post
Share on other sites
8^5 = 32768, 8^6 = 262144. Need I say more? If you want my personal opinion, try to make the maximum number of triangles in a Node equal to or greater than the number of endNodes.

Share this post


Link to post
Share on other sites
uber_n00b, I think you do need to say more, cus 32-262 thousand nodes isn''t all that bad for a tree. Is there some kind of huge overhead cost for generating such an octree??? cus searching through it won''t be time consuming at all. This guys does have 2.5 million tetrahedrons, which have 4 polys each.
Does the octree have to be generated new each frame? or what? Whats the give & take? thanks

Share this post


Link to post
Share on other sites
Well if he limited the max objects in a node to 100 or so you'd only get 5 levels in the octtre. Now if each node contains 8 points to nodes below it, two floats describing the min and max of the AABB and a point to possible leaf data a node will take up 44 bytes (assuming 4-byte floats). This means that a 5 deep octtre with the maximum number of endnodes would take up around 1.4mb. Now if the tetrahedrons are specified with only a posistion then 2'500'000 of them will take up around 28.6mb, which is far bigger than 1.4mb, and there's probably extra info to go along with the tetrahedrons position.

SirTwist: what you need to do is experiment with different max object values for your octtre see which is most efficent.

[edit]Whoops each node will take up 60 bytes not 44 so a 5-level deep octtre with all possible endnodes will take up 1.9mb not 1.4mb


[edited by - Monder on March 6, 2004 5:36:12 AM]

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!