Jump to content
  • Advertisement
Sign in to follow this  
Grain

Problem with octree algorithm.

This topic is 4867 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

When I step through in the debugger it doesn’t seem the numbers are coming out right. First I create the AABB for a potential child node which should be one eight if the current nodes AABB. Then I check the vector of triangles indices to see if a triangle is completely contained in the child’s AABB. If it is I add it to a temporary vector. Then I want to remove it from the current nodes vector but this isn’t working right. num_tris is used to count how many triangles will be in the child node. NumTris is the amount of triangles in the current node. num_tris is incremented every time I add a triangle to the child node. NumTris is decremented every time I remove a triangle from the current node. But after I run through both processes the numbers don’t sync up. For example I load a model with 32768 triangles. After wards I have 1468 triangles added to the child and 32302 removed from the current node. My question is are these logically equivalent in the context of my code? If not how can I make them equivalent?
if( Box.contains(V[index[j*3]]) && Box.contains(V[index[j*3+1]]) && Box.contains(V[index[j*3+2]]))
if( Box.contains(V[*k]) && Box.contains(V[*k_plus_1]) && Box.contains(V[*k_plus_2]))
I know the first one is correct and the seconded on is screwing up but I can’t use the first method when deleting items in the vector because deletes screw up the indexing.
void OctTree::add_geometry(vector3d* V, unsigned int num_verts, unsigned int *I, unsigned int num_tris)
{   
    verts = V;
    for(unsigned int j = 0; j < num_tris; j++)
    {
        index.push_back(I[j*3]);
        index.push_back(I[j*3+1]);
        index.push_back(I[j*3+2]);
    }
    //index = I;
    NumTris = num_tris;
    num_tris = 0;
    std::vector<unsigned int> new_I;    

    if(Parent == NULL)
    {
        B.add_points(V,num_verts);
    }

    if(NumTris > 1)
    {
        for(int i = 0; i < 8; i++)
        {
            AABB Box = B.eighth(i);
            
            for(unsigned int j = 0; j < NumTris; j++)
            {
                if( Box.contains(V[index[j*3]]) && Box.contains(V[index[j*3+1]]) && Box.contains(V[index[j*3+2]]))
                {            
                    new_I.push_back(index[j*3]);
                    new_I.push_back(index[j*3+1]);
                    new_I.push_back(index[j*3+2]);
                    num_tris++;
                }            
            }
            std::vector<unsigned int>::iterator k_plus_1;
            std::vector<unsigned int>::iterator k_plus_2;
            for(std::vector<unsigned int>::iterator k = index.begin(); k != index.end();)
            {
                k_plus_1 = k;
                k_plus_1++;
                k_plus_2 = k_plus_1;
                k_plus_2++;                
                if( Box.contains(V[*k]) && Box.contains(V[*k_plus_1]) && Box.contains(V[*k_plus_2]))
                {
                    index.erase(k++);
                    index.erase(k++);
                    index.erase(k++);
                    NumTris--;
                }
                else{k++; k++; k++;}
            }
            if(num_tris > 0) // Break point here, NumTris = 32302 num_tris = 1468    // 32302 + 1468 != 32768.
            {
                if(Child == NULL)
                {
                    Child = new OctTree;
                }                    
                Child->B = Box;
                Child->Parent = this;
                Child->add_geometry(V, new_I, num_tris,1);
            }
            new_I.clear();
            num_tris = 0;
        }
    }
}


Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
The iterator method is just as bad (to me) in this case compared to using indexing. Once you add or remove elements in the container, the iterators are invalid anyways.

Here is your problem: When using std::vector, everything is stored sequentially in memory, just like an ordinary array. If you delete element "k", the remaining elements after "k" are moved to remove the gap. Thus, after a delete of element "k", the old k+1 is now element "k". Since the iterators you use are essentially pointers, the same problem still exists - the pointers are not valid after the erase.

You should be using something other than a vector - like a list. This would eliminate the mass move of the remaining elements every time you erase elements. It would also help remove the bug since you are not processing the elements properly.

If you insist on a vector, you should do the processing something like this pseudo-code:


for (k=0; k

Notice that we don't increment "k" if the tris was deleted - since the remaining elements move into the place of "k" and we want to evaluate them as well.

Share this post


Link to post
Share on other sites
Its not that the *iterator method is bad* or using std::vector for vertex/index buffer is bad either it actually a good idea if your going to use vertex/index arrays/buffers. The problem is way the code has been done, like i was saying in a you're previous thread you should probably use something like remove_copy_if to conditionally add elements if a vertex/indice is contained within a bounds of an AABB.

Also note as mentioned already std::vector::erase may invalidate iterators but returns the next element so you should be doing "itr = v.erase(itr);" instead but also as mentioned its not a good idea, i think you can go about it another way without having to do things like erasing elements from std::vector.

Also as your using std::vector why not pass them as arguments aswell or iterators for maximum flexiabilty:


void OctTree::add_geometry(const std::vector<vector3d>& vertex_buf,
const std::vector<std::size_t>& index_buf) { ... }


or


template < typename VertexInputIterator, typename IndexInputIterator >
void OctTree::add_geometry(VertexInputIterator vfirst, VertexInputIterator vlast,
IndexInputIterator ifirst, IndexInputIterator ilast) { ... }

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I meant "bad" as in both index and iterator suffer from the same drawbacks in this case. Bad as in the sense that std::vector is really a very inefficient container to use in this case - where elements are constantly removed and those elements are not simply at the end of the list.

Yes it is good for VB but is one of the worst containers for efficiency in a case such as this.

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
Bad as in the sense that std::vector is really a very inefficient container to use in this case - where elements are constantly removed and those elements are not simply at the end of the list.

Yes it is good for VB but is one of the worst containers for efficiency in a case such as this.


I agree, i also believe you could still use std::vector and be efficient about it and without the need of doing any erasing for this problem. Another alternative is if elements stored in memory contiguously is insigificant but random access is then std::deque is a good alternative (especially with a custom allocator type), it does not suffer from some the problems std::vector has.

Share this post


Link to post
Share on other sites
I changed my code to read:

k = index.erase(k); k++;
k = index.erase(k); k++;
k = index.erase(k); k++;
NumTris--;

But that didn’t help.

EDIT:
Never mind, I miss read your post.


k = index.erase(k);
k = index.erase(k);
k = index.erase(k);
NumTris--;


Is correct. Thanks.
Free Image Hosting at www.ImageShack.us
Free Image Hosting at www.ImageShack.us

Free Image Hosting at www.ImageShack.us

[Edited by - Grain on July 24, 2005 11:47:47 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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!