Sign in to follow this  
sculpt

kd tree with a scenegraph

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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this