# Slow Octree rendering?

## Recommended Posts

skyfire360    228
My octree implemetation is quite slow at the moment, though it is not the culling but the copying of the indicies itself. From VTuner, I see that the following line of code is executed many, many, many times:
CULLRESULT cr = pFrustum->TestAABB(corners);
switch(cr) {
case CULL_IN:
for(unsigned int i = 0; i < numIndicies; i++) {
int index = localIndexList[i];
// The following line is executed too many times it seems
// It is equivalent to pushing the triangle's index
// Onto the culledIndicies list to be drawn
// (culledIndicies is wiped every frame)
if(indicies[index].touched < pFrame) {
culledIndicies[numCulledIndicies] = *indicies[index].index;
indicies[index].touched = pFrame;
numCulledIndicies++;
}
}
break;
case CULL_INTERSECT:
if(child[0] == NULL) {
//Add all my verticies, I'm the base case
for(unsigned int i = 0; i < numIndicies; i++) {
if(indicies[localIndexList[i]].touched < pFrame) {
culledIndicies[numCulledIndicies] = *indicies[localIndexList[i]].index;
indicies[localIndexList[i]].touched = pFrame;
numCulledIndicies++;
}
}
}
else {
// Don't add my own verts, let my children add 'em
// Cull each child
for(int i = 0; i < 8; i++) {
child[i]->Cull(pFrustum, pFrame);
}
}
break;
case CULL_OUT:
break;
}


I've thought about having an index buffer in each node to avoid the frame-by-frame copying, but that would lead to both overdraw (polygons in more than one leaf) and many SetStreamSource/DrawIndexedPrimitive calls. What's the most efficient way of getting the indicies that are drawn in the Octree leaf to the renderer while testing for overdraw? Or should I simply ignore the fact that some polygons in adjacent leafs may be drawn twice?

##### Share on other sites
Moe    1256
I would probably ignore the fact that a few triangles may be drawn more than once. It is probably a bit quicker to draw a few more triangles than necessary than have to rebuild the index buffer each frame. Have you tested both methods?

##### Share on other sites
xsirxx    170
I would worry about overdraw. It is such a waste of time when you could spend it drawing other VALID triangles. It may not be a seem like a huge waste now, but when your levels get larger, it will be your biggest downfall. It would be a HUGE mistake to just "overlook" it now, and very very lazy.

ALSO: are you running std list? or vector? Because you need to run in release mode with optimizes tured on. Otherwise it will be VERY VERY slow. I create an index list in each quad/oct. Then if it should be rendered I add them to a larger index(in a sort of roundabout way.) When I compile my maps in my 3ds exporter I just use an intelligent way of breaking the triangles down so they dont overlap each quad/oct. That is with my static "Land" or "World" mass. Not with objects that are affected within the world. Simply make them flagable for render and render them how you see fit.

##### Share on other sites
Moe    1256
I guess I should have made myself a bit more clear. If its only a few triangles, I wouldn't worry about it. If it is quite a few per quadtree node (or whatever you call them) then ignoring them wouldn't be the best solution.

##### Share on other sites
xsirxx    170
Ahh, Well if its only few, forget the quadtree because itll be slower than just rendering everything :). Quadtrees really only work when ya render ALOT of triangles and have a HUGE world. When it out weighs the opposite. I hope this all helps him to figure this out if he even needs the quadtree...

##### Share on other sites
skyfire360    228
Thanks for the replies guys!

While I realize that overdraw was and is a problem, I decided to try using an index buffer in each node (not worrying about overdraw) just to see what the speed differences were. Old way: 40-60 fps, depending on view. New way: 700-750. I realize that I will need to do something about overdraw because of the limitations in fillrate. A simple example would be a releif mapping pixel shader being applied to a very tall wall of a building (two triangles in a rectangle). If these polygons happened to appear in five different root nodes, the card would have to fill in 5x the fragments it normally would, killing any speed it may have had.

Quote:
 Original post by xsirxxAre you running std list? or vector? Because you need to run in release mode with optimizes tured on. Otherwise it will be VERY VERY slow. I create an index list in each quad/oct. Then if it should be rendered I add them to a larger index(in a sort of roundabout way.) *snip*

Believe it or not, neither. I've been taught to be kind of wary of the way that the std library handles and frees memory, specifically arrays of pointers. Usually I apply the "storage doubling" method, where if you are trying to add an element into a full array, the a new array is declared that is double the size of the original and assimilating and deleting the old array. That's a moot point here though, as that is all done in the octree generation and not in the culling stage.

If you split the triangles to take care of the overlapping and had a list of every index in each octree node, how do you go about getting the indicies from the Octree nodes' lists into the final index buffer on the card?

##### Share on other sites
xsirxx    170
Make a large dynamic index buffer and just push each node that is in view's indecies into that list. There are alot of ways to do this, one which I will probably get yelled at for, is create a large buffer that is big enough to handle all cases... This will get ya going for right now to see the speed. Some ppl say its a waste of space, but indexs are so damn small anyways, space hasnt been a concern for me *yet*. When you do your testing for each quad, if the quad is in view, simply push ALL of its contents to the large index buffer, and when render comes up, render the large buffer how u will.

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