# 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.

## 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 Popular Tags 2D 3D Advice Algorithm Animation C# C++ Character Concept Design DX11 Education GameMaker Gameplay General Java Learning Marketing Mobile Music OpenGL PC Unity Unreal VR Popular Contributors Week Month Year All Time 1 Rutin 41 2 Septopus 24 3 CyberFlash 24 4 supermikhail 12 5 Gnollrunner 11 Show More Advertisement Popular Now 10 number of matching chars in 2 strings By ICanCStarted Yesterday at 11:20 AM 27 collision sprite By phil67rpgStarted Friday at 10:13 PM 20 Pub/Sub for game Servers... Are you? By SeptopusStarted Thursday at 06:38 PM 9 C++ Dynamic memory using "new" and malloc() By rytStarted Thursday at 01:59 PM 20 Can I use assets from another game under these conditions? By JaretStarted November 13 Forum Statistics Total Topics 633405 Total Posts 3011680 Who's Online (See full list) There are no registered users currently online 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 var ipsDebug = false; var CKEDITOR_BASEPATH = '//www.gamedev.net/applications/core/interface/ckeditor/ckeditor/'; var ipsSettings = { cookie_path: "/", cookie_prefix: "ips4_", cookie_ssl: true, upload_imgURL: "", message_imgURL: "", notification_imgURL: "", baseURL: "//www.gamedev.net/", jsURL: "//www.gamedev.net/applications/core/interface/js/js.php", csrfKey: "653878063325123d0a7cc6ecb1630279", antiCache: "14de000c45", disableNotificationSounds: false, useCompiledFiles: true, links_external: true, memberID: 0, analyticsProvider: "ga", viewProfiles: true, mapProvider: 'google', mapApiKey: "AIzaSyAeT7tk3vnWWmbgVISkLpbhkQvekG19rHM", }; ips.setSetting( 'date_format', jQuery.parseJSON('"mm\/dd\/yy"') ); ips.setSetting( 'date_first_day', jQuery.parseJSON('0') ); ips.setSetting( 'remote_image_proxy', jQuery.parseJSON('1') ); ips.setSetting( 'ipb_url_filter_option', jQuery.parseJSON('"none"') ); ips.setSetting( 'url_filter_any_action', jQuery.parseJSON('"allow"') ); ips.setSetting( 'bypass_profanity', jQuery.parseJSON('0') ); ips.setSetting( 'emoji_style', jQuery.parseJSON('"native"') ); ips.setSetting( 'emoji_shortcodes', jQuery.parseJSON('"1"') ); ips.setSetting( 'emoji_ascii', jQuery.parseJSON('"1"') ); ips.setSetting( 'emoji_cache', jQuery.parseJSON('"1"') ); ips.setSetting( 'quickSearchDefault', jQuery.parseJSON('"all"') ); ips.setSetting( 'quickSearchMinimum', jQuery.parseJSON('3') ); ips.setSetting( 'quickSearchShowAdv', jQuery.parseJSON('true') ); ips.setSetting( 'quickSearchIn', jQuery.parseJSON('"title"') ); { "@context": "http://schema.org", "@type": "DiscussionForumPosting", "url": "https://www.gamedev.net/forums/topic/334313-problem-with-octree-algorithm/", "discussionUrl": "https://www.gamedev.net/forums/topic/334313-problem-with-octree-algorithm/", "name": "Problem with octree algorithm.", "headline": "Problem with octree algorithm.", "text": "When I step through in the debugger it doesn\u2019t seem the numbers are coming out right. \nFirst 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\u2019s 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\u2019t working right.\n\nnum_tris is used to count how many triangles will be in the child node.\nNumTris is the amount of triangles in the current node.\n\nnum_tris is incremented every time I add a triangle to the child node.\nNumTris is decremented every time I remove a triangle from the current node.\n\nBut after I run through both processes the numbers don\u2019t sync up.\n\nFor 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.\n\nMy question is are these logically equivalent in the context of my code? If not how can I make them equivalent? \n\n\n\nif( Box.contains(V[index[j*3]]) \u0026amp;\u0026amp; Box.contains(V[index[j*3+1]]) \u0026amp;\u0026amp; Box.contains(V[index[j*3+2]]))\nif( Box.contains(V[*k]) \u0026amp;\u0026amp; Box.contains(V[*k_plus_1]) \u0026amp;\u0026amp; Box.contains(V[*k_plus_2])) \n\nI know the first one is correct and the seconded on is screwing up but I can\u2019t use the first method when deleting items in the vector because deletes screw up the indexing.\n\n\n\nvoid OctTree::add_geometry(vector3d* V, unsigned int num_verts, unsigned int *I, unsigned int num_tris)\n{ \n verts = V;\n for(unsigned int j = 0; j \u0026lt; num_tris; j++)\n {\n index.push_back(I[j*3]);\n index.push_back(I[j*3+1]);\n index.push_back(I[j*3+2]);\n }\n //index = I;\n NumTris = num_tris;\n num_tris = 0;\n std::vector\u0026lt;unsigned int\u0026gt; new_I; \n\n if(Parent == NULL)\n {\n B.add_points(V,num_verts);\n }\n\n if(NumTris \u0026gt; 1)\n {\n for(int i = 0; i \u0026lt; 8; i++)\n {\n AABB Box = B.eighth(i);\n \n for(unsigned int j = 0; j \u0026lt; NumTris; j++)\n {\n if( Box.contains(V[index[j*3]]) \u0026amp;\u0026amp; Box.contains(V[index[j*3+1]]) \u0026amp;\u0026amp; Box.contains(V[index[j*3+2]]))\n { \n new_I.push_back(index[j*3]);\n new_I.push_back(index[j*3+1]);\n new_I.push_back(index[j*3+2]);\n num_tris++;\n } \n }\n std::vector\u0026lt;unsigned int\u0026gt;::iterator k_plus_1;\n std::vector\u0026lt;unsigned int\u0026gt;::iterator k_plus_2;\n for(std::vector\u0026lt;unsigned int\u0026gt;::iterator k = index.begin(); k != index.end();)\n {\n k_plus_1 = k;\n k_plus_1++;\n k_plus_2 = k_plus_1;\n k_plus_2++; \n if( Box.contains(V[*k]) \u0026amp;\u0026amp; Box.contains(V[*k_plus_1]) \u0026amp;\u0026amp; Box.contains(V[*k_plus_2]))\n {\n index.erase(k++);\n index.erase(k++);\n index.erase(k++);\n NumTris--;\n }\n else{k++; k++; k++;}\n }\n if(num_tris \u0026gt; 0) // Break point here, NumTris = 32302 num_tris = 1468 // 32302 + 1468 != 32768.\n {\n if(Child == NULL)\n {\n Child = new OctTree;\n } \n Child-\u0026gt;B = Box;\n Child-\u0026gt;Parent = this;\n Child-\u0026gt;add_geometry(V, new_I, num_tris,1);\n }\n new_I.clear();\n num_tris = 0;\n }\n }\n}\n\n\n\n", "dateCreated": "2005-07-24T06:55:19+0000", "datePublished": "2005-07-24T06:55:19+0000", "pageStart": 1, "pageEnd": 1, "image": "https://www.gamedev.net/uploads/profile/photo-thumb-58407.jpg", "author": { "@type": "Person", "name": "Grain", "image": "https://www.gamedev.net/uploads/profile/photo-thumb-58407.jpg", "url": "https://www.gamedev.net/profile/58407-grain/" }, "interactionStatistic": [ { "@type": "InteractionCounter", "interactionType": "http://schema.org/ViewAction", "userInteractionCount": 903 }, { "@type": "InteractionCounter", "interactionType": "http://schema.org/CommentAction", "userInteractionCount": 5 }, { "@type": "InteractionCounter", "interactionType": "http://schema.org/FollowAction", "userInteractionCount": 21 } ], "comment": [ { "@type": "Comment", "url": "https://www.gamedev.net/forums/topic/334313-problem-with-octree-algorithm/?do=findComment\u0026comment=334313", "author": { "@type": "Person", "name": "Grain", "image": "https://www.gamedev.net/uploads/profile/photo-thumb-58407.jpg", "url": "https://www.gamedev.net/profile/58407-grain/" }, "dateCreated": "2005-07-24T06:55:19+0000", "text": "When I step through in the debugger it doesn\u2019t seem the numbers are coming out right. \nFirst 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\u2019s 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\u2019t working right.\n\nnum_tris is used to count how many triangles will be in the child node.\nNumTris is the amount of triangles in the current node.\n\nnum_tris is incremented every time I add a triangle to the child node.\nNumTris is decremented every time I remove a triangle from the current node.\n\nBut after I run through both processes the numbers don\u2019t sync up.\n\nFor 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.\n\nMy question is are these logically equivalent in the context of my code? If not how can I make them equivalent? \n\n\n\nif( Box.contains(V[index[j*3]]) \u0026amp;\u0026amp; Box.contains(V[index[j*3+1]]) \u0026amp;\u0026amp; Box.contains(V[index[j*3+2]]))\nif( Box.contains(V[*k]) \u0026amp;\u0026amp; Box.contains(V[*k_plus_1]) \u0026amp;\u0026amp; Box.contains(V[*k_plus_2])) \n\nI know the first one is correct and the seconded on is screwing up but I can\u2019t use the first method when deleting items in the vector because deletes screw up the indexing.\n\n\n\nvoid OctTree::add_geometry(vector3d* V, unsigned int num_verts, unsigned int *I, unsigned int num_tris)\n{ \n verts = V;\n for(unsigned int j = 0; j \u0026lt; num_tris; j++)\n {\n index.push_back(I[j*3]);\n index.push_back(I[j*3+1]);\n index.push_back(I[j*3+2]);\n }\n //index = I;\n NumTris = num_tris;\n num_tris = 0;\n std::vector\u0026lt;unsigned int\u0026gt; new_I; \n\n if(Parent == NULL)\n {\n B.add_points(V,num_verts);\n }\n\n if(NumTris \u0026gt; 1)\n {\n for(int i = 0; i \u0026lt; 8; i++)\n {\n AABB Box = B.eighth(i);\n \n for(unsigned int j = 0; j \u0026lt; NumTris; j++)\n {\n if( Box.contains(V[index[j*3]]) \u0026amp;\u0026amp; Box.contains(V[index[j*3+1]]) \u0026amp;\u0026amp; Box.contains(V[index[j*3+2]]))\n { \n new_I.push_back(index[j*3]);\n new_I.push_back(index[j*3+1]);\n new_I.push_back(index[j*3+2]);\n num_tris++;\n } \n }\n std::vector\u0026lt;unsigned int\u0026gt;::iterator k_plus_1;\n std::vector\u0026lt;unsigned int\u0026gt;::iterator k_plus_2;\n for(std::vector\u0026lt;unsigned int\u0026gt;::iterator k = index.begin(); k != index.end();)\n {\n k_plus_1 = k;\n k_plus_1++;\n k_plus_2 = k_plus_1;\n k_plus_2++; \n if( Box.contains(V[*k]) \u0026amp;\u0026amp; Box.contains(V[*k_plus_1]) \u0026amp;\u0026amp; Box.contains(V[*k_plus_2]))\n {\n index.erase(k++);\n index.erase(k++);\n index.erase(k++);\n NumTris--;\n }\n else{k++; k++; k++;}\n }\n if(num_tris \u0026gt; 0) // Break point here, NumTris = 32302 num_tris = 1468 // 32302 + 1468 != 32768.\n {\n if(Child == NULL)\n {\n Child = new OctTree;\n } \n Child-\u0026gt;B = Box;\n Child-\u0026gt;Parent = this;\n Child-\u0026gt;add_geometry(V, new_I, num_tris,1);\n }\n new_I.clear();\n num_tris = 0;\n }\n }\n}\n\n\n\n", "mainEntityOfPage": "https://www.gamedev.net/forums/topic/334313-problem-with-octree-algorithm/" }, { "@type": "Comment", "url": "https://www.gamedev.net/forums/topic/334313-problem-with-octree-algorithm/?do=findComment\u0026comment=3172327", "author": { "@type": "Person", "name": "Anonymous Poster", "image": "https://www.gamedev.net/uploads/set_resources_7/84c1e40ea0e759e3f1505eb1788ddf3c_default_photo.png" }, "dateCreated": "2005-07-24T08:10:25+0000", "text": "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; kNotice that we don\u0027t 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.", "mainEntityOfPage": "https://www.gamedev.net/forums/topic/334313-problem-with-octree-algorithm/" }, { "@type": "Comment", "url": "https://www.gamedev.net/forums/topic/334313-problem-with-octree-algorithm/?do=findComment\u0026comment=3172339", "author": { "@type": "Person", "name": "snk_kid", "image": "https://secure.gravatar.com/avatar/1dc7eb0d0fe271e2e595cf1215dc670f?d=https://www.gamedev.net/uploads/monthly_2017_08/S.png.17cf9813488d23448b9f21d9f351d0d4.png", "url": "https://www.gamedev.net/profile/46005-snk_kid/" }, "dateCreated": "2005-07-24T08:31:16+0000", "text": "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\u0027re 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:\nvoid OctTree::add_geometry(const std::vector\u0026lt;vector3d\u0026gt;\u0026amp; vertex_buf, const std::vector\u0026lt;std::size_t\u0026gt;\u0026amp; index_buf) { ... }\nortemplate \u0026lt; typename VertexInputIterator, typename IndexInputIterator \u0026gt;void OctTree::add_geometry(VertexInputIterator vfirst, VertexInputIterator vlast, IndexInputIterator ifirst, IndexInputIterator ilast) { ... }\n", "mainEntityOfPage": "https://www.gamedev.net/forums/topic/334313-problem-with-octree-algorithm/" }, { "@type": "Comment", "url": "https://www.gamedev.net/forums/topic/334313-problem-with-octree-algorithm/?do=findComment\u0026comment=3172387", "author": { "@type": "Person", "name": "Anonymous Poster", "image": "https://www.gamedev.net/uploads/set_resources_7/84c1e40ea0e759e3f1505eb1788ddf3c_default_photo.png" }, "dateCreated": "2005-07-24T09:43:28+0000", "text": "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.", "mainEntityOfPage": "https://www.gamedev.net/forums/topic/334313-problem-with-octree-algorithm/" }, { "@type": "Comment", "url": "https://www.gamedev.net/forums/topic/334313-problem-with-octree-algorithm/?do=findComment\u0026comment=3172394", "author": { "@type": "Person", "name": "snk_kid", "image": "https://secure.gravatar.com/avatar/1dc7eb0d0fe271e2e595cf1215dc670f?d=https://www.gamedev.net/uploads/monthly_2017_08/S.png.17cf9813488d23448b9f21d9f351d0d4.png", "url": "https://www.gamedev.net/profile/46005-snk_kid/" }, "dateCreated": "2005-07-24T09:53:47+0000", "text": "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.", "mainEntityOfPage": "https://www.gamedev.net/forums/topic/334313-problem-with-octree-algorithm/" }, { "@type": "Comment", "url": "https://www.gamedev.net/forums/topic/334313-problem-with-octree-algorithm/?do=findComment\u0026comment=3172437", "author": { "@type": "Person", "name": "Grain", "image": "https://www.gamedev.net/uploads/profile/photo-thumb-58407.jpg", "url": "https://www.gamedev.net/profile/58407-grain/" }, "dateCreated": "2005-07-24T10:47:54+0000", "text": "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\u2019t 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]", "mainEntityOfPage": "https://www.gamedev.net/forums/topic/334313-problem-with-octree-algorithm/" } ] } { "@context": "http://www.schema.org", "@type": "WebSite", "name": "GameDev.net", "url": "https://www.gamedev.net/", "potentialAction": { "type": "SearchAction", "query-input": "required name=query", "target": "https://www.gamedev.net/search/?q={query}" }, "inLanguage": [ { "@type": "Language", "name": "English (USA)", "alternateName": "en-US" } ] } { "@context": "http://www.schema.org", "@type": "Organization", "name": "GameDev.net", "url": "https://www.gamedev.net/", "address": { "@type": "PostalAddress", "streetAddress": "", "addressLocality": null, "addressRegion": null, "postalCode": null, "addressCountry": null } } { "@context": "http://schema.org", "@type": "BreadcrumbList", "itemListElement": [ { "@type": "ListItem", "position": 1, "item": { "@id": "https://www.gamedev.net/forums/", "name": "Forums" } }, { "@type": "ListItem", "position": 2, "item": { "@id": "https://www.gamedev.net/forums/forum/4-programming/", "name": "Programming" } }, { "@type": "ListItem", "position": 3, "item": { "@id": "https://www.gamedev.net/forums/forum/9-general-and-gameplay-programming/", "name": "General and Gameplay Programming" } } ] } { "@context": "http://schema.org", "@type": "ContactPage", "url": "https://www.gamedev.net/contact/" } Important Information By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.   I accept 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!