Jump to content
  • Advertisement
Sign in to follow this  
Android_s

Octree + OpenGL problems

This topic is 4826 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm trying to make a "toy engine" (just to learn a few things) and i'm currently implementing the main level octree, but i've encountered a problem. I'm using .obj files as "levels" and when i'm rendering the whole level (standing outside, or without frustum) i get about 50 fps! I'm pretty sure where the problem is, but i'm asking for other ideas or ways i can improve the one i have. Also, when i have the frustum culling enabled, am outside the levels bounds, and stand with the back of the camera toward the level, i get about 1400 fps. Now when i take a step back just so i get inside the first nodes bounds (level bounds) it jumps from rendering 0 faces to 1000 faces, with a fps drop of about 900, to about 500 fps.. =( This is the first octree i'm trying to make so i'm not totaly sure of how to add stuff to it. Code is below. Ok, this is how i build my octree. I loop through every triangle i have, that is in the form of a CTriangle. The CTriangle class holds CVector3f arrays with the size of 3 with vert, normal and texCoord. CVector3f is a class with a float[3] array in it...
void COctree::AddToTree(CTriangle* tri, COctNode *node, int depth, int threshold)
{
    bool wasAssigned = false;

    // allowed to go deeper?
    if(depth < threshold)
    {
        // create temp node from node, to test against
        COctNode n;
        n.Init(node->min, node->max, NULL);
        CreateNodes(&n);

        for(int i = 0; i < 8; ++i)
        {
            COctNode *n2 = &n.subnodes;

            // if node fit in a subnode, send it on
            if(n2->PointInNode(tri->verts[0]) && n2->PointInNode(tri->verts[1]) && n2->PointInNode(tri->verts[2]))
            {
                wasAssigned = true;

                if(node->subnodes == NULL)
                    CreateNodes(node);

                this->AddToTree(tri, &node->subnodes, ++depth, threshold);
            }
        }

        // clean temp node
        DestroyNodes(&n);
    }

    if(!wasAssigned)
    {
        // tri dosn't fit in any subnode, assign to this
        node->triList.push_back(tri);
        return;
    }
}

So far everything is fine...i think. I have the problem with the 1000 triangles that's conencted to the world bounds (root node), but i think that's because the octree always split a node in 8 equal rectangles. It should do that, no..? Ok, now my drawing code. I couldn't really figure out a good way to draw my triangles now when they are in the nodes. Currently, as you see, i'm using vert arrays, but i'm still looping through the triangles, and that for every node i have. If you have a better way of doing this, please tell me =). I have a feeling that much of my problems is here...
void CWorld::RenderWorld(CCamera *camera)
{
    glEnable(GL_VERTEX_ARRAY);
    glEnable(GL_NORMAL_ARRAY);

    RenderByNode(camera, this->partitionTree.GetRoot());

    glDisable(GL_VERTEX_ARRAY);
    glDisable(GL_NORMAL_ARRAY);
}

void CWorld::RenderByNode(CCamera *camera, COctNode *node)
{
    AABoundingBox box(node->min, node->max);
    if(camera->BoundsInCameraFrustum(&box))
    {
        if(!node->triList.empty())
        {
            for(int i = 0; i < (int)node->triList.size(); ++i)
            {
                glVertexPointer(3, GL_FLOAT, 0, &(node->triList->verts[0]));
                glNormalPointer(GL_FLOAT, 0, &(node->triList->norms[0]));

                glDrawArrays(GL_TRIANGLES, 0, 3);
            }
        }
		
        if(node->subnodes != NULL)
        {
            for(int i = 0; i < 8; ++i)
                RenderByNode(camera, &node->subnodes);
        }
    }
}

If you have any, and i mean any, idea of how i could speed this up, please do tell me =) Thanks in advance for any help!

Share this post


Link to post
Share on other sites
Advertisement
You can organize your data so that you don't have to draw it one triangle at a time. For example, you could put all the triangles completely contained within a node in a single vertex array. You can also increase the volume of a leaf node. You may end up drawing more triangles, but there will be fewer draw calls.

Share this post


Link to post
Share on other sites
Quote:
Original post by JohnBolton
You can organize your data so that you don't have to draw it one triangle at a time. For example, you could put all the triangles completely contained within a node in a single vertex array. You can also increase the volume of a leaf node. You may end up drawing more triangles, but there will be fewer draw calls.

I would highly recommend not drawing one triangle at a time too. See nVidia on Batches, GDC 2003 (PDF). The bottom line is, calling glDrawArrays with only one triangle each time is making the CPU work hard, while the GPU just waits for each triangle.

Other possible improvements for OpenGL may be to use triangle strips with glDrawElements with indexed tringles and/or Vertex Buffer Objects (commonly referred to as VBOs).

I don't know if you've done this already, but to visually ensure your octtree is working correctly, you could add some debug code to 'freeze' the current frustum in place, and have it drawn in wireframe along with the colliding octtree boxes and contained triangles, while you float around and look at it. By your post, it sounds like the frustum is working, but still.

Having said that, do not be alarmed by drops of a few hundred FPS, when one is dealing with large initial values of 1400 FPS for example. One should turn it around, and ask, "how many seconds per frame?". A drop from 2 FPS to 1 FPS after a change, means the change is adding 0.5 seconds to the rendering time for each frame (which would be a lot). But a drop from 2000 FPS to 1000 FPS means the change is adding 0.0005 seconds to the rendering time (which is not a lot). Both a drop from 2 to 1, and 2000 to 1000 FPS, mean there has been a doubling in the time to render a frame, but the absolute increase (as opposed to relative) in the second instance, is much less. In this way, FPS can be a misleading indication of performance changes.

Share this post


Link to post
Share on other sites
Thanks for the help!

I were aware of the problems with drawing one triangle at a time, but i couldn't think of a "smart" way to do it.
As JohnBolton suggested i've arranged it so every node has one list of triangles, and 3 lists of floats; vertices, normals and texCoords. That way i fill them at pre-calc and when it's time to render i just access them and toss them straight into glDrawArrays(). Perhaps it's still not the best way, but i got the FPS from 50 to about 2-300 now. I also exhanged the bounding boxes to spheres...i found out that checking a BB to the frustum were a lot more expensive than BS...

Ro_Akira: That's a good idea to lock the frustum. I havn't done it yet but i'll be all over it once i get the time =)

One more thing, can you please have another look at this code. It's my revised recursive draw routine. If you can find any way to speed it up, not concidering ways to draw (like tri strips), please do tell me.
(BoundsInCameraFrustum is a for loop with 6 loops, and every loop a plane equation, and the lists are STD vectors)

void CWorld::RenderByNode(CCamera *camera, COctNode *node)
{
if(camera->BoundsInCameraFrustum(&node->boundSphere))
{
if(!node->triList.empty())
{
glVertexPointer(3, GL_FLOAT, 0, &(node->triVertList[0]));
glNormalPointer(GL_FLOAT, 0, &(node->triNormList[0]));
glDrawArrays(GL_TRIANGLES, 0, (int)node->triList.size() * 3);
}

if(node->subnodes != NULL)
{
for(int i = 0; i < 8; ++i)
RenderByNode(camera, &node->subnodes);
}
}
}

Share this post


Link to post
Share on other sites
First let me say that I understand the code is a work in progress, and as such you may have gotten round to these things anyway:

Regarding the AddToTree function...
Quote:

// if node fit in a subnode, send it on

Should that comment read "if triangle fits in a subnode"? It might also be easier to read (and more convenient) if you replaced the three PointInNode tests, with a single TiangleInNode function.

Quote:

CreateNodes(&n);

Would that be more accurately called "CreateSubNodes"?

I've just examined your AddToTree method and it appears that you're limiting the expansion of the octtree by its depth. The advantage of this method is it restricts the memory usage of the octtree. Another approach is to stop dividing a node into sub nodes when it contains less than a certain number of triangles and I would recommend that approach myself. The former doesn’t adapt itself to the number triangles given (there's a limit on the depth of the tree). The second method creates sub nodes based on the density of

In addition, I'm not sure how you decide on the initial bounds for nodes. I usually acquire initial bounds by getting the max(x,y,z) and min(x,y,z) from all the vertices of all the triangles, which could be what you're doing.

It seems you handle triangles lying across the octtree splitting planes by placing them in the highest node that can contain them whole. To illustrate a problem with this approach, imagine a triangle lying across one of the very first splitting planes - the triangle ends up in the root node! That means that this triangle will be tested against the frustum if the frustum is touching the root node of the octtree, which it will be, always (in normal use).

One way to solve this could be to split the triangle using the octtree planes as the splitting planes, and then hand the resulting triangles to the sub nodes.

An alternative is to choose a sub node to attach the triangle to, and then resizing the bounds of the node to the max(x,y,z) and min(x,y,z) from all the vertices of all the triangles contained within the node.

How to choose which node to attach the triangle? One can either choose the sub node which contains the most vertices, or more accurately, choose the sub node that contains the greatest area of the triangle.

A side effect of all this, is that only leaf nodes will contain triangles (due to splitting the triangles, or expanding the nodes).

As a side note, you may want to combine splitting with expanding, if for example one has some really large triangles that would expand the sub nodes a lot. You could choose whether to split or expand based on the area of the triangle being tested. If it is over the threshold, it gets split. If not, add it too the most suitable cub node, and expand that node.

A thing to watch for when using expanding is to have two versions of the bounds for each node. One holds the initial bounds of the node, and the second holds the expanded bounds, which is at least as big as the initial bounds and may be bigger if a triangle lying across an octtree plane has been added. When testing triangles against nodes then, triangles are initially tested against the expanded bounds, since the nodes are going to be expanded to these bounds anyway. If no sub node completely contains the triangle, the best candidate sub node is decided by testing against the initial bounds. The reason for this is that previously expanded nodes may 'win' border triangles, and be expanded again. This could result in them growing so big, that they end up getting all the triangles.

Regarding the RenderWorld function...
I presume that within the BoundsInCameraFrustum function you are doing a frustum sphere vs node sphere check. The thing about spheres as bounding volumes is that though they are fast, the nature of the volume means they can give a slightly more conservative (i.e. larger) set of results (i.e. number of potentially visible nodes). What you could do, is for each node that passes the sphere-sphere test, do a node-frustum test, which could cut down the number of nodes further, and thus the number triangle-frustum tests.

P.S. I assume you are constructing the spheres with the radius based on the distance from the centre of the node, to one of the corners, is that right?

Another potential speed up can be attained if you find a node that is completely contained by the frustum. You can automatically draw it and it's sub nodes without any more sphere-sphere, node-frustum or triangle-frustum tests!

[Edited by - Ro_Akira on September 27, 2005 1:11:38 AM]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!