Octrees: Unnecessary sub-division

This is a discussion on Octrees: Unnecessary sub-division within the Game Programming forums, part of the General Programming Boards category; I've been working on an Octree rendering system for my game engine. Everything is going smoothly (or at least more ...

  1. #1
    The Right Honourable psychopath's Avatar
    Join Date
    Mar 2004
    Location
    Where circles begin.
    Posts
    1,070

    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
    Attached Images Attached Images  
    Memorial University of Newfoundland
    Computer Science

    Mac and OpenGL evangelist.

  2. #2
    Registered User
    Join Date
    Apr 2002
    Posts
    1,571
    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.
    "...the results are undefined, and we all know what "undefined" means: it means it works during development, it works during testing, and it blows up in your most important customers' faces." --Scott Meyers

  3. #3
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,584
    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.

  4. #4
    vae victus! skorman00's Avatar
    Join Date
    Nov 2003
    Posts
    594
    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:
    Attached Images Attached Images  

  5. #5
    vae victus! skorman00's Avatar
    Join Date
    Nov 2003
    Posts
    594
    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.

  6. #6
    The Right Honourable psychopath's Avatar
    Join Date
    Mar 2004
    Location
    Where circles begin.
    Posts
    1,070
    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
    Memorial University of Newfoundland
    Computer Science

    Mac and OpenGL evangelist.

  7. #7
    vae victus! skorman00's Avatar
    Join Date
    Nov 2003
    Posts
    594
    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.

  8. #8
    The Right Honourable psychopath's Avatar
    Join Date
    Mar 2004
    Location
    Where circles begin.
    Posts
    1,070
    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
    Last edited by psychopath; 01-21-2006 at 12:01 PM.
    Memorial University of Newfoundland
    Computer Science

    Mac and OpenGL evangelist.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Get jiffies?
    By pgzh in forum Linux Programming
    Replies: 6
    Last Post: 03-17-2008, 10:30 AM
  2. pseudo code for division
    By svaidya in forum C Programming
    Replies: 14
    Last Post: 05-31-2007, 01:48 PM
  3. Problem with modus division.
    By stillwell in forum C++ Programming
    Replies: 3
    Last Post: 10-19-2004, 11:54 AM
  4. modulo 2 division question help
    By shaq8u in forum C Programming
    Replies: 9
    Last Post: 08-20-2003, 08:37 AM
  5. Modular Division problem
    By Malek in forum C++ Programming
    Replies: 7
    Last Post: 05-24-2003, 06:08 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21