Sign in to follow this  
Vast

Octree Partitioning Questions

Recommended Posts

Hello everyone!

Here is what I have so far:

I take a Quake3 BSP file and load it up. The whole level is treated as a polygon soup and is reorganized by texture ID. So there is now the same number of meshes as there are textures, to minimize state switching during rendering.

Then, each mesh is reorganized by face. Face is something that has all the vertex index data, but also contains lightmap texture id. So far the map is sorted on the first pass by the texture id, then meshes sharing the same texture ID are sorted even deeper, by faces which contain a unique lightmap ID.

Now, each face contains a list of triangles. Each triangle contains 3 vertex indexes into the absolute vertex array for the whole map.

Here is where the interesting part begins:

I want to find a method for spacial partitioning, which does not require as much time to compile as the BSP. I chose octree because they are the easiest.

Octree partitioning causes certain "discrepancies" which need to be handled.
1. Splitting of triangles which share borders with other octants.

My Options:
a.) Store shared triangles within parent node
b.) Clip the triangles
c.) Store a duplicate and render multiple times
d.) Set up a per-triangle flag to eliminate render multiple times.
e.) Adaptive octrees. This is a vague concept to me, but I still don't see how it would completely eliminate the splitting of the triangles. I don't think it will.

Question - which of these options is the most efficient? I like (a) and (c) since I was hoping to combine octree data into display lists or VBOs.


Next problem:
2. What is the best way to store the split data within each octant?
For clarity, I would think that it would be important to minimize state switching, therefore all the meshes must remain sorted by texture id, and then by lightmap id, - but how, then, would I store this data and traverse the tree? How would I accumulate sorted (by texture) renderable data? And fast, too :)

I really can't wrap my mind around this one, not properly anyways. How do you do it??


3. Later on, I will be splitting brushes of the BSP file as well. Now, I know they have been dismembered and clipped in the process of calculating the tree, but I was hoping to partition them in the octree as well. Are there any special cases that you may see where the octree will introduce some complications?


Finally, what other methods of spacial partitioning would be fast to calculate, assuming the levels will be built using CSG?

Thank you in advance!

Share this post


Link to post
Share on other sites
Okay, if you have interior levels I strongly not recommend using octrees, as they're definitely evil for interiors. They are best used with terrain, not models.

So from what I've read, you need speed ... and BSP trees are slow for you, so you can try using similar thing - KD trees (it is axis aligned BSP), it will be same slow ... but, you can implement KD tree building in O(N log N) time, and that will be very fast (and also quite a nightmare to build).

I would recommend hierarchical bounding volumes (also known as BVH), here is something on them http://www.win.tue.nl/~hermanh/stack/bvh.pdf, that might be better suited for your needs.

When I used Octree, I assigned split trinagles to both nodes in between it was split (or even more nodes! - which can become a bit of nightmare if you need fast rendering)

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