Octrees: Unnecessary sub-division

I've been working on an Octree rendering system for my game engine. Everything is going smoothly (or at least more than I thought it would). When creating new nodes, I only want it to create nodes if there is an object withen the node that would be created. This works, however it produces some odd results with two objects, creating nodes where there are no objects at all.

Heres my code for determining if an object lies within the boundries of a node:

Code:

---

        for(int i=0; i<num_objects; i++)
        {
                if(objectP[i].pos.x <= leaf->pos.x && objectP[i].pos.y <= leaf->pos.y && objectP[i].pos.z <= leaf->pos.z)
                {
                        leaf->BBLactive = true;
                }
                if(objectP[i].pos.x >= leaf->pos.x && objectP[i].pos.y <= leaf->pos.y && objectP[i].pos.z <= leaf->pos.z)
                {
                        leaf->BBRactive = true;
                }
                if(objectP[i].pos.x <= leaf->pos.x && objectP[i].pos.y <= leaf->pos.y && objectP[i].pos.z >= leaf->pos.z)
                {
                        leaf->BFLactive = true;
                }
                if(objectP[i].pos.x >= leaf->pos.x && objectP[i].pos.y <= leaf->pos.y && objectP[i].pos.z >= leaf->pos.z)
                {
                        leaf->BFRactive = true;
                }
               
                if(objectP[i].pos.x <= leaf->pos.x && objectP[i].pos.y >= leaf->pos.y && objectP[i].pos.z <= leaf->pos.z)
                {
                        leaf->TBLactive = true;
                }
                if(objectP[i].pos.x >= leaf->pos.x && objectP[i].pos.y >= leaf->pos.y && objectP[i].pos.z <= leaf->pos.z)
                {
                        leaf->TBRactive = true;
                }
                if(objectP[i].pos.x <= leaf->pos.x && objectP[i].pos.y >= leaf->pos.y && objectP[i].pos.z >= leaf->pos.z)
                {
                        leaf->TFLactive = true;
                }
                if(objectP[i].pos.x >= leaf->pos.x && objectP[i].pos.y >= leaf->pos.y && objectP[i].pos.z >= leaf->pos.z)
                {
                        leaf->TFRactive = true;
                }
        }

---

If more code is necessary, let me know. But i'm confident that this is the only thing that would cause a problem. All this code does, is test the object position in relation to the node positon, and return true if the node should be created.

thanx,
-psychopath

By just stepping through it in a debugger I think you should easily be able to see where your problem is. You might want to consider some logging system as well to aid you. If you have 2 monitors I think it would be extremely easy to solve this. Without 2 monitors, a little more work but still shouldn't be that bad.

I would have responded as well, but couldn't see anything right off the bat and w/o more code and more of an idea what is taking place, I'm afraid my comments would be un-educated to say the least.

It doesn't look like you're everying checking the new leaves, only the root. If you were to move the crates so that they are both on the same side of the XY plane, you would get some thing that looked more like this:

The drawing isn't very good, and turning it into a jpeg made it a bit harder to see the colors, but I think you'll understand what I'm trying to show you.

I'll post up some more code when I get home from school. I haven't been able to work on this much lately, because I have mid-term exams coming up. Actually, I may not be able to reply to this thread much at all for another week! :(

@MrWizard: I can't remember if i've already ran it through the debugger or not. In any case, I'll try it again as soon as I get the chance.

@Skorman: Sorry, I don't really know what you mean. :)

-psychopath

Let me give it another try.

I think those extra blocks are showing up because you're still testing the root node to see where the splits should be made.

On the first pass, it creates the larger sections you see in the corners. It then goes to split those sections up. Those sections will be selected to be split, but the tests are on the root. So when it splits them up, it still thinks there is a crate in the opposite corner.

In my picture, I was trying to explain that if you were to bring the crate on the lower front left to the lower front right, you would continually split the sections into lower front right and top back right branches.

This is assuming that the face on the left is the front, and the face on the right is right. When you do post more code, show the code that decides what leaf is in the first post.

Ok, I understand what you're saying now.

Here's my insert function:

Code:

---

extern index[3];
vector3d pos;
void octree::insert(int id, node *leaf)
{
        for(int i=0; i<num_objects; i++)
        {
                if(objectP[i].pos.x <= leaf->pos.x && objectP[i].pos.y <= leaf->pos.y && objectP[i].pos.z <= leaf->pos.z)
                {
                        leaf->BBLactive = true;
                }
                if(objectP[i].pos.x >= leaf->pos.x && objectP[i].pos.y <= leaf->pos.y && objectP[i].pos.z <= leaf->pos.z)
                {
                        leaf->BBRactive = true;
                }
                if(objectP[i].pos.x <= leaf->pos.x && objectP[i].pos.y <= leaf->pos.y && objectP[i].pos.z >= leaf->pos.z)
                {
                        leaf->BFLactive = true;
                }
                if(objectP[i].pos.x >= leaf->pos.x && objectP[i].pos.y <= leaf->pos.y && objectP[i].pos.z >= leaf->pos.z)
                {
                        leaf->BFRactive = true;
                }
               
                if(objectP[i].pos.x <= leaf->pos.x && objectP[i].pos.y >= leaf->pos.y && objectP[i].pos.z <= leaf->pos.z)
                {
                        leaf->TBLactive = true;
                }
                if(objectP[i].pos.x >= leaf->pos.x && objectP[i].pos.y >= leaf->pos.y && objectP[i].pos.z <= leaf->pos.z)
                {
                        leaf->TBRactive = true;
                }
                if(objectP[i].pos.x <= leaf->pos.x && objectP[i].pos.y >= leaf->pos.y && objectP[i].pos.z >= leaf->pos.z)
                {
                        leaf->TFLactive = true;
                }
                if(objectP[i].pos.x >= leaf->pos.x && objectP[i].pos.y >= leaf->pos.y && objectP[i].pos.z >= leaf->pos.z)
                {
                        leaf->TFRactive = true;
                }
        }

    if(leaf->BOTTOM_BACK_LEFT!=NULL)
                insert(id, leaf->BOTTOM_BACK_LEFT);
    else
    {
                if(leaf->BBLactive == true)
                {
                        leaf->BOTTOM_BACK_LEFT=new node;
                        leaf->BOTTOM_BACK_LEFT->id=id-5;
                        leaf->BOTTOM_BACK_LEFT->pos.x = leaf->pos.x - (leaf->scale.x/4);
                        leaf->BOTTOM_BACK_LEFT->pos.y = leaf->pos.y - (leaf->scale.y/4);
                        leaf->BOTTOM_BACK_LEFT->pos.z = leaf->pos.z - (leaf->scale.z/4);
                        leaf->BOTTOM_BACK_LEFT->scale.x = leaf->scale.x/2;
                        leaf->BOTTOM_BACK_LEFT->scale.y = leaf->scale.y/2;
                        leaf->BOTTOM_BACK_LEFT->scale.z = leaf->scale.z/2;
                        leaf->BOTTOM_BACK_LEFT->BOTTOM_BACK_LEFT=NULL;
                        leaf->BOTTOM_BACK_LEFT->BOTTOM_BACK_RIGHT=NULL;
                        leaf->BOTTOM_BACK_LEFT->BOTTOM_FRONT_LEFT=NULL;
                        leaf->BOTTOM_BACK_LEFT->BOTTOM_FRONT_RIGHT=NULL;
                        leaf->BOTTOM_BACK_LEFT->TOP_BACK_LEFT=NULL;
                        leaf->BOTTOM_BACK_LEFT->TOP_BACK_RIGHT=NULL;
                        leaf->BOTTOM_BACK_LEFT->TOP_FRONT_LEFT=NULL;
                        leaf->BOTTOM_BACK_LEFT->TOP_FRONT_RIGHT=NULL;
                }
    } 
       
    if(leaf->BOTTOM_BACK_RIGHT!=NULL)
                insert(id, leaf->BOTTOM_BACK_LEFT);
    else
    {
                if(leaf->BBRactive==true)
                {
                        leaf->BOTTOM_BACK_RIGHT=new node;
                        leaf->BOTTOM_BACK_RIGHT->id=id+5;
                        leaf->BOTTOM_BACK_RIGHT->pos.x = leaf->pos.x + (leaf->scale.x/4);
                        leaf->BOTTOM_BACK_RIGHT->pos.y = leaf->pos.y - (leaf->scale.y/4);
                        leaf->BOTTOM_BACK_RIGHT->pos.z = leaf->pos.z - (leaf->scale.z/4);
                        leaf->BOTTOM_BACK_RIGHT->scale.x = leaf->scale.x/2;
                        leaf->BOTTOM_BACK_RIGHT->scale.y = leaf->scale.y/2;
                        leaf->BOTTOM_BACK_RIGHT->scale.z = leaf->scale.z/2;
                        leaf->BOTTOM_BACK_RIGHT->BOTTOM_BACK_LEFT=NULL;
                        leaf->BOTTOM_BACK_RIGHT->BOTTOM_BACK_RIGHT=NULL;
                        leaf->BOTTOM_BACK_RIGHT->BOTTOM_FRONT_LEFT=NULL;
                        leaf->BOTTOM_BACK_RIGHT->BOTTOM_FRONT_RIGHT=NULL;
                        leaf->BOTTOM_BACK_RIGHT->TOP_BACK_LEFT=NULL;
                        leaf->BOTTOM_BACK_RIGHT->TOP_BACK_RIGHT=NULL;
                        leaf->BOTTOM_BACK_RIGHT->TOP_FRONT_LEFT=NULL;
                        leaf->BOTTOM_BACK_RIGHT->TOP_FRONT_RIGHT=NULL;
                }
    }

    if(leaf->BOTTOM_FRONT_LEFT!=NULL)
                insert(id, leaf->BOTTOM_FRONT_LEFT);
    else
    {
                if(leaf->BFLactive==true)
                {
                        leaf->BOTTOM_FRONT_LEFT=new node;
                        leaf->BOTTOM_FRONT_LEFT->id=id-10;
                        leaf->BOTTOM_FRONT_LEFT->pos.x = leaf->pos.x - (leaf->scale.x/4);
                        leaf->BOTTOM_FRONT_LEFT->pos.y = leaf->pos.y - (leaf->scale.y/4);
                        leaf->BOTTOM_FRONT_LEFT->pos.z = leaf->pos.z + (leaf->scale.z/4);
                        leaf->BOTTOM_FRONT_LEFT->scale.x = leaf->scale.x/2;
                        leaf->BOTTOM_FRONT_LEFT->scale.y = leaf->scale.y/2;
                        leaf->BOTTOM_FRONT_LEFT->scale.z = leaf->scale.z/2;
                        leaf->BOTTOM_FRONT_LEFT->BOTTOM_BACK_LEFT=NULL;
                        leaf->BOTTOM_FRONT_LEFT->BOTTOM_BACK_RIGHT=NULL;
                        leaf->BOTTOM_FRONT_LEFT->BOTTOM_FRONT_LEFT=NULL;
                        leaf->BOTTOM_FRONT_LEFT->BOTTOM_FRONT_RIGHT=NULL;
                        leaf->BOTTOM_FRONT_LEFT->TOP_BACK_LEFT=NULL;
                        leaf->BOTTOM_FRONT_LEFT->TOP_BACK_RIGHT=NULL;
                        leaf->BOTTOM_FRONT_LEFT->TOP_FRONT_LEFT=NULL;
                        leaf->BOTTOM_FRONT_LEFT->TOP_FRONT_RIGHT=NULL;
                }
    } 
       
    if(leaf->BOTTOM_FRONT_RIGHT!=NULL)
                insert(id, leaf->BOTTOM_FRONT_RIGHT);
    else
    {
                if(leaf->BFRactive==true)
                {
                        leaf->BOTTOM_FRONT_RIGHT=new node;
                        leaf->BOTTOM_FRONT_RIGHT->id=id+10;
                        leaf->BOTTOM_FRONT_RIGHT->pos.x = leaf->pos.x + (leaf->scale.x/4);
                        leaf->BOTTOM_FRONT_RIGHT->pos.y = leaf->pos.y - (leaf->scale.y/4);
                        leaf->BOTTOM_FRONT_RIGHT->pos.z = leaf->pos.z + (leaf->scale.z/4);
                        leaf->BOTTOM_FRONT_RIGHT->scale.x = leaf->scale.x/2;
                        leaf->BOTTOM_FRONT_RIGHT->scale.y = leaf->scale.y/2;
                        leaf->BOTTOM_FRONT_RIGHT->scale.z = leaf->scale.z/2;
                        leaf->BOTTOM_FRONT_RIGHT->BOTTOM_BACK_LEFT=NULL;
                        leaf->BOTTOM_FRONT_RIGHT->BOTTOM_BACK_RIGHT=NULL;
                        leaf->BOTTOM_FRONT_RIGHT->BOTTOM_FRONT_LEFT=NULL;
                        leaf->BOTTOM_FRONT_RIGHT->BOTTOM_FRONT_RIGHT=NULL;
                        leaf->BOTTOM_FRONT_RIGHT->TOP_BACK_LEFT=NULL;
                        leaf->BOTTOM_FRONT_RIGHT->TOP_BACK_RIGHT=NULL;
                        leaf->BOTTOM_FRONT_RIGHT->TOP_FRONT_LEFT=NULL;
                        leaf->BOTTOM_FRONT_RIGHT->TOP_FRONT_RIGHT=NULL;
                }
    }

    if(leaf->TOP_BACK_LEFT!=NULL)
                insert(id, leaf->TOP_BACK_LEFT);
    else
    {
                if(leaf->TBLactive==true)
                {
                        leaf->TOP_BACK_LEFT=new node;
                        leaf->TOP_BACK_LEFT->id=id-15;
                        leaf->TOP_BACK_LEFT->pos.x = leaf->pos.x - (leaf->scale.x/4);
                        leaf->TOP_BACK_LEFT->pos.y = leaf->pos.y + (leaf->scale.y/4);
                        leaf->TOP_BACK_LEFT->pos.z = leaf->pos.z - (leaf->scale.z/4);
                        leaf->TOP_BACK_LEFT->scale.x = leaf->scale.x/2;
                        leaf->TOP_BACK_LEFT->scale.y = leaf->scale.y/2;
                        leaf->TOP_BACK_LEFT->scale.z = leaf->scale.z/2;
                        leaf->TOP_BACK_LEFT->BOTTOM_BACK_LEFT=NULL;
                        leaf->TOP_BACK_LEFT->BOTTOM_BACK_RIGHT=NULL;
                        leaf->TOP_BACK_LEFT->BOTTOM_FRONT_LEFT=NULL;
                        leaf->TOP_BACK_LEFT->BOTTOM_FRONT_RIGHT=NULL;
                        leaf->TOP_BACK_LEFT->TOP_BACK_LEFT=NULL;
                        leaf->TOP_BACK_LEFT->TOP_BACK_RIGHT=NULL;
                        leaf->TOP_BACK_LEFT->TOP_FRONT_LEFT=NULL;
                        leaf->TOP_BACK_LEFT->TOP_FRONT_RIGHT=NULL;
                }
    } 
       
    if(leaf->TOP_BACK_RIGHT!=NULL)
                insert(id, leaf->TOP_BACK_RIGHT);
    else
    {
                if(leaf->TBRactive==true)
                {
                        leaf->TOP_BACK_RIGHT=new node;
                        leaf->TOP_BACK_RIGHT->id=id+15;
                        leaf->TOP_BACK_RIGHT->pos.x = leaf->pos.x + (leaf->scale.x/4);
                        leaf->TOP_BACK_RIGHT->pos.y = leaf->pos.y + (leaf->scale.y/4);
                        leaf->TOP_BACK_RIGHT->pos.z = leaf->pos.z - (leaf->scale.z/4);
                        leaf->TOP_BACK_RIGHT->scale.x = leaf->scale.x/2;
                        leaf->TOP_BACK_RIGHT->scale.y = leaf->scale.y/2;
                        leaf->TOP_BACK_RIGHT->scale.z = leaf->scale.z/2;
                        leaf->TOP_BACK_RIGHT->BOTTOM_BACK_LEFT=NULL;
                        leaf->TOP_BACK_RIGHT->BOTTOM_BACK_RIGHT=NULL;
                        leaf->TOP_BACK_RIGHT->BOTTOM_FRONT_LEFT=NULL;
                        leaf->TOP_BACK_RIGHT->BOTTOM_FRONT_RIGHT=NULL;
                        leaf->TOP_BACK_RIGHT->TOP_BACK_LEFT=NULL;
                        leaf->TOP_BACK_RIGHT->TOP_BACK_RIGHT=NULL;
                        leaf->TOP_BACK_RIGHT->TOP_FRONT_LEFT=NULL;
                        leaf->TOP_BACK_RIGHT->TOP_FRONT_RIGHT=NULL;
                }
    }

    if(leaf->TOP_FRONT_LEFT!=NULL)
                insert(id, leaf->TOP_FRONT_LEFT);
    else
    {
                if(leaf->TFLactive==true)
                {
                        leaf->TOP_FRONT_LEFT=new node;
                        leaf->TOP_FRONT_LEFT->id=id-20;
                        leaf->TOP_FRONT_LEFT->pos.x = leaf->pos.x - (leaf->scale.x/4);
                        leaf->TOP_FRONT_LEFT->pos.y = leaf->pos.y + (leaf->scale.y/4);
                        leaf->TOP_FRONT_LEFT->pos.z = leaf->pos.z + (leaf->scale.z/4);
                        leaf->TOP_FRONT_LEFT->scale.x = leaf->scale.x/2;
                        leaf->TOP_FRONT_LEFT->scale.y = leaf->scale.y/2;
                        leaf->TOP_FRONT_LEFT->scale.z = leaf->scale.z/2;
                        leaf->TOP_FRONT_LEFT->BOTTOM_BACK_LEFT=NULL;
                        leaf->TOP_FRONT_LEFT->BOTTOM_BACK_RIGHT=NULL;
                        leaf->TOP_FRONT_LEFT->BOTTOM_FRONT_LEFT=NULL;
                        leaf->TOP_FRONT_LEFT->BOTTOM_FRONT_RIGHT=NULL;
                        leaf->TOP_FRONT_LEFT->TOP_BACK_LEFT=NULL;
                        leaf->TOP_FRONT_LEFT->TOP_BACK_RIGHT=NULL;
                        leaf->TOP_FRONT_LEFT->TOP_FRONT_LEFT=NULL;
                        leaf->TOP_FRONT_LEFT->TOP_FRONT_RIGHT=NULL;
                }
    } 
       
    if(leaf->TOP_FRONT_RIGHT!=NULL)
                insert(id, leaf->TOP_FRONT_RIGHT);
    else
    {
                if(leaf->TFRactive==true)
                {
                        leaf->TOP_FRONT_RIGHT=new node;
                        leaf->TOP_FRONT_RIGHT->id=id+20;
                        leaf->TOP_FRONT_RIGHT->pos.x = leaf->pos.x + (leaf->scale.x/4);
                        leaf->TOP_FRONT_RIGHT->pos.y = leaf->pos.y + (leaf->scale.y/4);
                        leaf->TOP_FRONT_RIGHT->pos.z = leaf->pos.z + (leaf->scale.z/4);
                        leaf->TOP_FRONT_RIGHT->scale.x = leaf->scale.x/2;
                        leaf->TOP_FRONT_RIGHT->scale.y = leaf->scale.y/2;
                        leaf->TOP_FRONT_RIGHT->scale.z = leaf->scale.z/2;
                        leaf->TOP_FRONT_RIGHT->BOTTOM_BACK_LEFT=NULL;
                        leaf->TOP_FRONT_RIGHT->BOTTOM_BACK_RIGHT=NULL;
                        leaf->TOP_FRONT_RIGHT->BOTTOM_FRONT_LEFT=NULL;
                        leaf->TOP_FRONT_RIGHT->BOTTOM_FRONT_RIGHT=NULL;
                        leaf->TOP_FRONT_RIGHT->TOP_BACK_LEFT=NULL;
                        leaf->TOP_FRONT_RIGHT->TOP_BACK_RIGHT=NULL;
                        leaf->TOP_FRONT_RIGHT->TOP_FRONT_LEFT=NULL;
                        leaf->TOP_FRONT_RIGHT->TOP_FRONT_RIGHT=NULL;
                }
    }
}

---

What this code is supposed to do, is create nodes based on the location of objects, relative to the current parent nodes centre.
Eventually, I'm going to modify this to create nodes based on polygon location, rather than object location.

-psychopath