Asmodeus

08-22-2015, 12:56 AM

Hello, I would like to present some Questions i got about space Partitioning in OpenGL.

First and foremost i want to ask about the data structure types that are used to divide the space in slices. I am interested in those:

- (BSP) K-d trees

- Octree

- Quadtree

As far as i know the k-d trees are based on traditional BST with some modification, but the idea is the same. Octrees/Quadtrees , have 4/8 leafs per node. Here are my two Questions:

1. Can i get more indepth explanation on how exactly do they work? How are they constructed ?

2. Which tree is useful for what ?

My goal is to make a culling and ray-triangle(mesh) intersection systems in my engine.

As far as i can figure i will need one tree to divide the mesh's triangles efficently so i can perform ray-triangle intersection on that mesh - fast. Currently i am using bullet physics to perfrom ray-object intersection (and i presume that bullet has advanced structures to make that efficent).

For the culling i have objects i assume i will use the AABB provided by the bullet for each model to test if that box is outside the frustum ? But i also have huge terrains containing alot of vertices and i assume that i should devide that with octrees.

Also isnt it better to push everything on the scene (objects,terrains etc) in a tree and make the culling there.

First and foremost i want to ask about the data structure types that are used to divide the space in slices. I am interested in those:

- (BSP) K-d trees

- Octree

- Quadtree

As far as i know the k-d trees are based on traditional BST with some modification, but the idea is the same. Octrees/Quadtrees , have 4/8 leafs per node. Here are my two Questions:

1. Can i get more indepth explanation on how exactly do they work? How are they constructed ?

2. Which tree is useful for what ?

My goal is to make a culling and ray-triangle(mesh) intersection systems in my engine.

As far as i can figure i will need one tree to divide the mesh's triangles efficently so i can perform ray-triangle intersection on that mesh - fast. Currently i am using bullet physics to perfrom ray-object intersection (and i presume that bullet has advanced structures to make that efficent).

For the culling i have objects i assume i will use the AABB provided by the bullet for each model to test if that box is outside the frustum ? But i also have huge terrains containing alot of vertices and i assume that i should devide that with octrees.

Also isnt it better to push everything on the scene (objects,terrains etc) in a tree and make the culling there.