Octree Problem

Member
Posts: 312
Joined: 2006.10
Post: #1
Hey,

The last two days I've been working on a simple Octree. Right now it does subdivide, but it subdivided incorrectly. It subdivided more so in areas with the least vertices, and less so in areas with the most vertices. Also, the more I raise how muc vertices per node is allowed, patches of the terrain dissapear. Lastly, it will cull nodes that are still partialy in the viewing frustum still. Here are two screenshots:

[Image: picture4kz0.png]

[Image: picture3rn0.png]

If you guys could take a look at the source, that would be great, as I can't find any logical errors :/

Thanks!

Octree.h
http://rafb.net/p/N82nHf49.html

Octree.cpp (CreateChildrenNode() is the meat of the code)
http://rafb.net/p/Ptvu0395.html

Frustum code
Code:
bool CFrustum::CubeInFrustum( float x, float y, float z, float size )
{
    // Same a point, just test each point
    for(int i = 0; i < 6; i++ )
    {
        if(m_Frustum[i][A] * (x - size) + m_Frustum[i][b] * (y - size) + m_Frustum[i][C] * (z - size) + m_Frustum[i][D] > 0)
           continue;
        if(m_Frustum[i][A] * (x + size) + m_Frustum[i][b] * (y - size) + m_Frustum[i][C] * (z - size) + m_Frustum[i][D] > 0)
           continue;
        if(m_Frustum[i][A] * (x - size) + m_Frustum[i][b] * (y + size) + m_Frustum[i][C] * (z - size) + m_Frustum[i][D] > 0)
           continue;
        if(m_Frustum[i][A] * (x + size) + m_Frustum[i][b] * (y + size) + m_Frustum[i][C] * (z - size) + m_Frustum[i][D] > 0)
           continue;
        if(m_Frustum[i][A] * (x - size) + m_Frustum[i][b] * (y - size) + m_Frustum[i][C] * (z + size) + m_Frustum[i][D] > 0)
           continue;
        if(m_Frustum[i][A] * (x + size) + m_Frustum[i][b] * (y - size) + m_Frustum[i][C] * (z + size) + m_Frustum[i][D] > 0)
           continue;
        if(m_Frustum[i][A] * (x - size) + m_Frustum[i][b] * (y + size) + m_Frustum[i][C] * (z + size) + m_Frustum[i][D] > 0)
           continue;
        if(m_Frustum[i][A] * (x + size) + m_Frustum[i][b] * (y + size) + m_Frustum[i][C] * (z + size) + m_Frustum[i][D] > 0)
           continue;

        return false;
    }
    
    return true;
}
Quote this message in a reply
Apprentice
Posts: 19
Joined: 2007.03
Post: #2
You should rethink your paradigm of octree. Basically, the way that you have it, there are two classes needed to produce octree behavior. This is not the best way to program any type of tree structure. Think of it like this: what is each node of an octree? it's another octree. Essentially, you should retool your octree class to have the functionality of both classes, such that an octree has 8 sub octrees and each of those have sub octrees and so on... this is called recursion. You create leaf octrees whenever all 8 children are NULL.

This has the advantage of having a unified simple interface that requires no external knowledge of how it works to use it. You need to get rid of functions like init() and destroy(). These functions should be implemented in your constructors and destructors. If you do have these functions, they should be private, not public. Only the class itself should know about them.

I don't really feel like digesting all of that code to tell you how to improve it, but here is generally how octree subdivision of a terrain should work:

1. you create an octree
2. you pass the terrain to the the octree (add(Terrain*)), something like that
3. the terrain subdivides the terrain into a maximum of 8 parts, and creates new sub octrees for each of these parts.
4. recursively pass each terrain piece to each sub octree until the terrain is divided into the size chunks that you want. Make the threshold a private static class member variable with static accessor methods.


This is a much better designed implementation that you should seriously consider. It will make your coding easier and it is the generally accepted paradigm for tree programming. It will be somewhat hard for you to wrap your head around this concept at first, but recursion is your friend. Use it whenever possible to turn large tasks into lots of hierarchically smaller ones.


Oh, and drop the C* prefix. There's no need to tell us that these are classes, we know that (or course unless you are writing a library and need the prefix to provide uniqueness, though C isn't exactly unique)

As for your culling code, which is the main source of your problem, here is my culling code. This is old stuff that I abandoned so it may not be very fast, but it should work. (I'm not liable if it eats your dog)

Code:
bool Frustum::isInViewOctree( float xMin, float xMax,
                              float yMin, float yMax,
                              float zMin, float zMax )
{
    // test all corners of the frustum to see if they are within the AABB of the     // octree.
    for ( int i = 0; i < 8; i++ )
    {
        if ( corner[i].x >= xMin && corner[i].x <= xMax &&
             corner[i].y >= yMin && corner[i].y <= yMax &&
             corner[i].z >= zMin && corner[i].z <= zMax )
            return true;
    }
    
    return isInViewBoxMinMax( xMin, xMax, yMin, yMax, zMin, zMax );
}


bool Frustum::isInViewBoxMinMax( float xMin, float xMax,
                                 float yMin, float yMax,
                                 float zMin, float zMax )
{
    bool result = true;
    
    rimVector3 pVertex, nVertex;
    
    for ( int i = 0; i < 6; i++ )
    {
        pVertex.x = xMin;
        pVertex.y = yMin;
        pVertex.z = zMin;
        
        nVertex.x = xMax;
        nVertex.y = yMax;
        nVertex.z = zMax;
        
        if ( plane[i].normal.x < 0 )
            pVertex.x = xMax;
        if ( plane[i].normal.y < 0 )
            pVertex.y = yMax;
        if ( plane[i].normal.z < 0 )
            pVertex.z = zMax;
        
        if ( plane[i].normal.x > 0 )
            nVertex.x = xMin;
        if ( plane[i].normal.y > 0 )
            nVertex.y = yMin;
        if ( plane[i].normal.z > 0 )
            nVertex.z = zMin;
        
                // is the positive vertex outside?
        if ( plane[i].distance( pVertex ) < 0 )
            return false;
        // is the negative vertex outside?    
        else if ( plane[i].distance( nVertex ) < 0 )
            result = true;
        
    }
    
    
    return result;
}
Quote this message in a reply
Member
Posts: 312
Joined: 2006.10
Post: #3
Thanks for such a in-depth reply! I actually do have recursion going on here (CreateChildrenNode() is where it happens)... Originally, I was intending on having the actual Octree store information such as the minimum vertices, the max subdivision level, ect.. That was until I realized I had no way to actually have the Node's know about the "Octree", so that ruined everything. You're right, I really need to change that.

As for the Init and Destroy(), they were simply for testing purposes (so, I could change the limits of how the many nodes are allowed, ect.. at run-time, so how the Octree changed each time.

And yes, I'm writing a library of code for myself Rasp

I'll try that frustum code also, see how it works Smile

Once again, thanks!
Quote this message in a reply
Post Reply