Jump to content
  • Advertisement
Sign in to follow this  
sculpt

kd tree with a scenegraph

This topic is 3606 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

I have a kd-tree of a static scene . And the leaves of the kd-tree are linked to their respective node in the scene graph . The primitives of the kd-tree are not triangles but bounding boxes of the leave nodes of each Scene-Graph . So basically i have a spatial data structure and a hierarchical data structure of a scene and which are connected to each other. I am using this for creating a 3d GIS , where you can attach information in 3d . I was thinking of some applications of this structure , i have come up with the following :- 1) Finding the nearest object (with some property) from where you are in the scene 2) Finding out all objects in a range volume I am unable to think of better applications of this architecture ... can somebody suggest some good applications for this architecture ?

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by sculpt
I am unable to think of better applications of this architecture ... can somebody suggest some good applications for this architecture ?
It is more natural to design an architecture to match an application, rather than the other way round... [smile]

Share this post


Link to post
Share on other sites
Quote:
1) Finding the nearest object (with some property) from where you are in the scene
2) Finding out all objects in a range volume

Those are the basic proprieties of a spatial index. Nothing fancy.
I'd phrase it that way though:
1) Finding element closest to a coordinate
2) Walking elements from closest to farthest to some element, possibly in an approximated way
3) Finding all elements which intersect with some given geometry (range search, raytracing, frustum culling, etc.)

I don't see why you need to connect a kd-tree to some "scene graph" to do that. What a "scene graph" is isn't well-defined, but usually it already includes a spatial index as nested bounding boxes.
A spatial index in general is nothing but an n-ary tree, where all children define subspaces (which might overlap or not) of the space defined by their father. kd-trees are a possible strategy to recursively subdivide the space into a binary tree.

Share this post


Link to post
Share on other sites
Quote:
Original post by loufoque
Quote:
1) Finding the nearest object (with some property) from where you are in the scene
2) Finding out all objects in a range volume

Those are the basic proprieties of a spatial index. Nothing fancy.
I'd phrase it that way though:
1) Finding element closest to a coordinate
2) Walking elements from closest to farthest to some element, possibly in an approximated way
3) Finding all elements which intersect with some given geometry (range search, raytracing, frustum culling, etc.)

I don't see why you need to connect a kd-tree to some "scene graph" to do that. What a "scene graph" is isn't well-defined, but usually it already includes a spatial index as nested bounding boxes.
A spatial index in general is nothing but an n-ary tree, where all children define subspaces (which might overlap or not) of the space defined by their father. kd-trees are a possible strategy to recursively subdivide the space into a binary tree.


I need the scenegraph for rendering purposes, i am using OpenSceneGraph ( OSG ) .. i have used the same scenegraph structure used by OSG.

Share this post


Link to post
Share on other sites
Sign in to follow this  

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