# Problem with octree algorithm.

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

## 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)
{
}

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;
}
new_I.clear();
num_tris = 0;
}
}
}



##### Share on other sites
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 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 on other sites
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 on other sites
Quote:
 Original post by Anonymous PosterBad 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 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.[Edited by - Grain on July 24, 2005 11:47:47 AM] 
 0 
 Share this post Link to post Share on other sites 
 
 
 
 Sign in to follow this   Followers 0 
 Go To Topic Listing General and Gameplay Programming Advertisement 
 Advertisement What is your GameDev Story? In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us. (You must login to your GameDev.net account.) Share My Story Popular Tags 2D 3D Advice C# C++ Character Concept Design DX11 DX12 GameMaker Gameplay General Graphics Learning Mobile Music OpenGL Optimization PC Pixel Unity Unreal VR Vulkan Popular Now 9 Lighting: Inside faces are getting lighted too? By babaliarisStarted Yesterday at 06:44 PM 34 Anyone who wants to write a little game engine? By DaTueOwnerStarted Friday at 09:12 PM 16 OpenGL Textures, Pixel Alignment And Texture Mistakes. What Am I Doing Wrong? By babaliarisStarted Friday at 06:34 PM 11 Managing pointers upon object destruction in C++ By too_many_starsStarted Friday at 08:21 AM 12 A Functional Impass - Advise me on how to proceed? (C#) By A4LStarted Friday at 03:32 AM Advertisement Forum Statistics Total Topics 634123 Total Posts 3015648 GameDev.net GameDev.net Articles GameDev.net Event Coverage GameDev.net Forums GameDev.net Blogs GameDev.net Gallery GameDev.net News GameDev.net Projects GDNet Chat All Activity Search In Everywhere This Forum This Topic More options... Find results that contain... All of my search term words Any of my search term words Find results in... Content titles and body Content titles only Home Forums Programming General and Gameplay Programming Problem with octree algorithm. 
 
 
 × Existing user? Sign In Sign Up Browse Back Articles & Tutorials Back All Categories Audio Business Game Design Industry Programming Visual Arts Columns Back GameDev Unboxed Event Coverage Back All Events Game Developers Conference Power Up Digital Games Conference GameDev.Market Links News Podcasts Back All Podcasts Game Dev Loadout Archive Community Back Beginners Back Beginners Group Beginners Forum Beginners Resources Blogs Calendar Chat Forums Back All Forums Audio Business Game Design Programming Visual Arts Community GameDev Challenges Affiliates Topical Workshops Gallery Groups Back For Beginners GameDev Challenges All Groups Projects Back All Projects Games Game Assets Game Mods Developer Tools Store Forums Back All Forums For Beginners Audio Back Music and Sound FX Games Career Development Business Back Games Career Development Production and Management Games Business and Law Game Design Back Game Design and Theory Writing for Games Programming Back Artificial Intelligence Engines and Middleware General and Gameplay Programming Graphics and GPU Programming Math and Physics Networking and Multiplayer Visual Arts Back 2D and 3D Art Critique and Feedback Community Back GameDev Challenges GDNet Lounge GDNet Comments, Suggestions, and Ideas Coding Horrors Your Announcements Hobby Project Classifieds Indie Showcase Affiliates Back NeHe Productions AngelCode Topical Workshops Careers Back Contractors Hobby Projects Game Jobs Back Browse on GameDev.Jobs Post a Job Members Back Subscriptions Chat Guidelines Leaderboard Online Users Awards Search Back All Activity My Activity Streams Back Latest Topics Featured Blogs Search Important Information By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.   I accept 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! 
 $('body').click(function (e) { var container =$("#pagecontainer"); if (($(e.target).parent().prop('nodeName') == 'BODY') && (container.has(e.target).length === 0) && (e.button == 0) && (!$(e.target).hasClass('ipsDialog'))) { window.open('https://ad.doubleclick.net/ddm/trackclk/N129002.1825GAMEDEV.NET/B11085475.236262913;dc_trk_aid=433791501;dc_trk_cid=90245747;dc_lat=;dc_rdid=;tag_for_child_directed_treatment=;tfua='); ga('send','event','Advertisement','Click','3q_fb_gamedev_skin_2019_1'); } }); $(document).ready(function() { setInterval(function() { window.googletag.pubads().refresh(); }, 30000); });$(document).ready(function() { if (ipsSettings.memberID > 0) { ga('send','event','User','View','Member'); } else { ga('send','event','User','View','Guest'); } });