Jump to content
  • Advertisement
Sign in to follow this  
Waterlimon

How to store dynamic sparse octree in RAM?

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

Hey, im slowly working on a "game" that is too complex to propably ever finish (only way to have enough motivation to work on it :c) and it includes sparse octrees.

I was wondering what is the best way to store this sparse octree in memory, without taking too much memory or being slow when inserting or removing nodes or being terribly cache unfriendly.

My current node representation is:

class Node
{
ChildArrayStartIndex
ChildArrayMask
}

Where the first variable tells where to find the array of 1-8 children (0 if it doesnt exist) and a mask to tell which ones exist (i took this off some random gpu octree rendering article thing)

Initially im going to store them in a vector of nodes, and when adding a new child to the array check if theres free space after it and if not (or the array doesnt exist) just put it at the end of the vector. (if i keep this method i will add something that keeps track of free spaces in the middle of the vector and moves the blocks of nodes around to remove small spaces)

I thought that would be cache unfriendly and potentially slow when adding nodes, so for the actual octree i was going to have the nodes stored in a bucket with each bucket storing some amount of nodes, and the buckets would be stored in an octree like above, so that nodes close to each other in the tree are in same buckets. (Also thought of instead making buckets only hold nodes in a single level of the octree, which might work better)

Does that sound ok assuming you understood me at all? :P

Any articles about this or other methods of storage you know about?

My octree stuff is as follows btw (simplified):

temp<elementType>
OctreeBase

temp<elementType>
OctreeIterator (this is used for all octree types, it uses virtual methods of the octree given to it to find nodes and do stuff to them, not sure if i should call this an iterator but dont know what else :P)

temp<elementType>
OctreeNodeBase (the base just contains the stuff required to store and access an object of elementType

Share this post


Link to post
Share on other sites
Advertisement
Hi,

are you planning to have lots of objects moving around all the time?

I have a simple octree implementation where using pointers for children and std::vector for entities stored in the tree.

[color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

[background=rgb(250, 251, 252)]class Node[/background]

[/font]

[color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

[background=rgb(250, 251, 252)]{[/background]

[/font]
[color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

[background=rgb(250, 251, 252)]public:[/background]

[/font]
[color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

[background=rgb(250, 251, 252)]Node *pChild[8];[/background]

[/font]
std::vector<Entity *> Entities;
[color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

[background=rgb(250, 251, 252)]}[/background]

[/font]

[color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

[background=rgb(250, 251, 252)]I haven't noticed that the implementation is considerably slow or that it takes huge quantities of memory. One of the key points for moving objects in the tree is to re-evaluate their containing node only when they are out side of the current node. [/background]

[/font]
[color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

[background=rgb(250, 251, 252)]I'd go for a working and simple solution first, then look for performance if it seems to be the bottle neck.[/background]

[/font]

Of course, having a bucket of nodes helps for the memory allocation, but also, it may be premature optimization. After all, it is rather simple to add after wards.

[color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

[background=rgb(250, 251, 252)]Cheers![/background]

[/font]

Share this post


Link to post
Share on other sites
I want to use it to store terrain/objects some day, so it might be static most of the time, but then again i will need to edit it a lot if editing or if i ever get to add explosions or something else which heavily modifies it.

I guess my current method isnt that bad (the one where i have a vector and move nodes around to remove space) as i later want to use it to just store the nodes inside the buckets, and also to store the buckets in their own octree. (so that there wont be too many nodes to move around and they wont be scattered all around memory)

Share this post


Link to post
Share on other sites

want to use it to store terrain/objects some day, so it might be static most of the time, but then again i will need to edit it a lot if editing or if i ever get to add explosions or something else which heavily modifies it.


Sure, storing objects and terrain is what octree is good for. Nothing special there. It doesn't matter whether the object is 8km x 8km large or small as 0.1m x 0.1m. Both store well in the octree.

The amount of editing doesn't pose any problems, you may move your static objects as you wish and at the end of day you may have fragmented your memory only a little bit. Of course if you wish to move all objects at once then you may have such concerns. But even then, if the most of the objects stay inside the nodes, there is no overhead to the octree structure.

Heavily modifying / explosions - moving/adding/removing something like tens of objects at once? doesn't sound bad.

What I'm trying to say here that you don't seem to have a problem yet (since you haven't implemented all the required functionality), but you are inventing one (ie. you think that your octree solution may be a performance/memory hog).

So finish your current method, make it as simple as you can (use std::vectors for example) and then profile it.

Cheers!

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.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!