T-Junctions in Octrees

Rhetorical question, but: aren’t there going to be T-Junctions in a fast Octree envirnment? My games are typically going to be outdoor scenes, so I want to impliment Octrees, but I don’t like the idea of T-Junctions.

When I create an octree, each node will contain all the triangles that fall inside that node, so when the tree is created, triangles will have to be clipped, and that causes T-Junctions, which in turn causes cracks in geomentry.

I read at flipcode that you can forget the clipping all together, and just store the triangles that fall within a node, then when you go to draw any triangles, you can flag them as drawn so that child nodes with the same set of triangles won’t draw them again. That’s a great idea and all, but I like to use glDrawElements, but you can’t flag a triangle and have glDrawElements ignore the drawn triangle on another pass…or can you? I don’t know, I haven’t been keeping track of every extension that spawns into existance :slight_smile: .

So I guess my question is: does the speed of glDrawElememnts outweigh the ugliness of cracks left behind when drawing triangles with T-Junctions?

Have you tried coding the renderer to not use the
glDrawElements() call and see what kind of performance
penalty you have? Until you do it, you will not be
able to tell which is a better way to go.

Remember, if the intended hardware will not suffer
from a severe drop in performance, you could always
draw the scene raw and have no cracks.

Finally, I have thought of a simple way to avoid all
these problems and having to mask triangles as drawn
in real time, etc, but never had the chance to code
it and test it. You take an approach similar to what
was going on in old Amiga demos; when the scene is
loading in your game, spend some time to precompute
different element lists for each of the nodes. It
is like an octree, only you have many octrees, and
you jump from one to the next in an intelligent
way. There is a serious memory penalty you will
have to pay, however. Just a thought.

I haven’t tried using glVertex and its associated function calls yet. I guess I’ll have to test both ways to see which method is more acceptable. If I lose 10 FPS by using glVertex, big deal, I’d rather see a small hit in FPS than small cracks in my rendered scenes.

I was mostly curious to find out which methods were used commercially, because that would tell me if the typical gamer would prefer higher FPS over no cracks.

Thanks for you ideas.


Can you use a “loose octree” for this application. This way you don’t split any faces, and every face is in one cell.

I don’t know. Lets look at the advantages and disadvantages.

Octree with clipped geometry:
[ul][li]Disadvantage - Cracks in geometry caused by clipping[]Disadvantage - Possible collision detection errors caused by clipping[]Disadvantage - Would cost you more memory because in order to fix the collision detection errors you would have to store the unclipped geometry in a BSP tree[]Advantage - Might be faster to use glDrawElement(drawing element arrays should be faster)[]Advantage - Might be faster to us a BSP tree for collision detection[/ul][/li]Octree without clipped geometry:
[ul][li]Disadvantage - Redundent storage of triangles in child nodes[]Disadvantage - Geometry would draw slower because in order to flag triangles to draw or not, you need to use glVertex and friends[]Advantage - No cracks in geometry[*]Advantage - Accurate collision detection[/ul][/li]Creating a BSP tree is only a disadvantage if the BSP tree method for collision detection is slower than the Octree method. So I guess the next question is: would collision detection be faster using a BSP tree or an Octree?

Originally posted by weatx:
Disadvantage - Geometry would draw slower because in order to flag triangles to draw or not, you need to use glVertex and friends
With today’s fast hardware I would ignore “flagging” any single primitives. Your batches should be in the size of >300 anyway, otherwise you’ll be very CPU-limited. It is key to performance with today’s cards that you do efficient high-level culling. quake1 and others heavily subdivided because software rasterization was very expensive.

I decided to just stick with Oct-tree culling with clipped geometry. I’ll further optimize by using portals. Worse case scenario for collision detection would be an entity’s volume lying in 8 quadrants. We’ll see what happens, and if it’s not good enough, then add bsp-trees for collision detection.