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!