next »

[Zaknafein]

Dear Tiger sauce,

I've been recently (read: today) been trying to encode triles in Fez as Octrees instead of dictionaries (aka. maps) of "missing trixels" like in the IGF demo. The point of that was to try to shorten the memory size and on-disk size of my trile-sets.
(for those still wondering about trixels, see this post)

But to my horror and dismay, my octree implementation is a LOT larger on-disk and I assume in memory too, but this I didn't find any way to prove.
Except in very lucky cases where the missing chunks fit the octree perfectly.

I'm kinda new to 3D tree spacial structures, and I may have screwed up when making my octree, so here's a summary of my implementation :

- An octree has a size (right now always 16x16x16) and a root node
- A node has 0 to 8 child nodes, a reference to its parent, and a "filled" boolean (its content)

- To mark a position as filled, you call Octree.Fill(vector), which finds the node, creates the path to the node if necessary and marks the leaf as filled.
- After a filling operation, I traverse back from the filled leaf to the root node using the parent references and check if each parent's child nodes are all filled; if so, I merge them by destroying the children (:D) and filling the parent.

- To mark a position as freed, you call Octree.Free(vector), which finds the node but does NOT create a path if missing, and marks the leaf as non-filled if found.
- After a freeing, same thing, but I try to destroy parents with no children.

That's about it.

My current understanding of octrees is that every child node is half the X, Y and Z size of the parent, making it 2^3=8 times smaller.
That becomes an issue when I want to flag a single, very small area in the octree, I have to create the path to that cell even if I'll probably never use it.

So my question... Is there another octree flavor, or 3D tree flavor that would help me having a "sparser" octree, more dynamically sizable? Or are trees a downright bad idea for this?

Danke, merci, gracias.

[Zaknafein]

Oh and when I say "size on disk", I mean once it's serialized in SDL.

Here's a peek of what it looked like before :

Code:

missingTrixels {
	12 12 12
	12 12 13
	12 12 14
	12 12 15
	12 13 12
	12 13 13
	12 13 14
	12 13 15
	12 14 12
	12 14 13
	12 14 14
	12 14 15
	...
}

And with an octree... (with my best effort of shortening identifier length, which makes it a bit confusing)

Code:

missingTrixelsOctree {
	size 16F 16F 16F
	root {
		c {
			n {
				c {
					n f=true
					n {
						c {
							n f=true
							n {
								c {
									n f=true
									n null
									n f=true
									n null
									n f=true
									n null
									n f=true
									n null
								}
							}
							n f=true
							n {
								c {
									n f=true
									n null
									n f=true
									n null
									n f=true
									n null
									n f=true
									n null
...

Here, the octree implementation is ~1600 lines and 30kb, the dictionary is ~1100 lines and 14kb. 

[Saint]

Since you are storing information about the tree as well as the data, the average case will have more information, yes. What you will improve is culling speed since you can disregard subtrees without having to check every node when traversing the tree.

Trees are generally used to search data in a more efficient way, so if you're looking to have a smaller memory footprint then that's probably not the way to go. The cases where you actually get better performance from octrees would likely be even further improved if you didn't store the tree but only 3D-areas with missing trixels - that is, like the first version but with width/height/depth  for each point (or even better, only for the points that weren't 1,1,1)

[Eclipse]

i agree with saint, also, why your octree have a fixed size?
a good way to make your octree always work well is to make the bigger tree sized as the 3d world bounding box bigger measure (eg. if your world goes more in height than in width or lenght you will end up with a box that fit the world height).

About memory, octree doesn't use such great memory if you don't store geometry data inside, make only references to your geometry inside the tree, don't store actual geometry, also it will be harder to render without many calls.
In my octree implementation i simply store an index list so the only memory surplus is the tree itself and some int.
Also, i don't understand that thing you posted so well... it's like a file format were you store the octree? if that you don't have to do that hierarchical stuff if you want to save space, you can simply save your tree as a list

[Zaphos]

Dictionaries are also a sparse data structure; it's not obvious that octree should always beat the dictionary.

Here, the octree implementation is ~1600 lines and 30kb, the dictionary is ~1100 lines and 14kb. 

Er, does this mean you're worried about disk storage and you're storing your data structures as text?

What do you want to get out of the octree?  If it's only for smaller on-disk storage, I'd suggest trying run-length encoding.  And store it as binary data!

[Zaknafein]

What you will improve is culling speed since you can disregard subtrees without having to check every node when traversing the tree.

Right now I won't because my octrees are used strictly for data storage... When I generate polygonal data, I need to flatten them as a list. Which brings me to...

Trees are generally used to search data in a more efficient way, so if you're looking to have a smaller memory footprint then that's probably not the way to go.
The cases where you actually get better performance from octrees would likely be even further improved if you didn't store the tree but only 3D-areas with missing trixels - that is, like the first version but with width/height/depth  for each point (or even better, only for the points that weren't 1,1,1)

Yeah. It makes sense now that you say it.
I think the real solution to my problem would be a custom data structure like the one you suggest. But those can be annoying to keep tidy. I liked about octrees how simple it was to collapse empty or full cells together...

why your octree have a fixed size?

It's only fixed because my triles are always 16x16x16. It doesn't make sense to make them smaller, or to have cells smaller than 1x1x1 for that matter...

About memory, octree doesn't use such great memory (...)

Agreed, but I'm still doubtful that it's smaller than my dictionary in any realistic case. (and in fact it's a hash set, since it would be a dictionary<vector3, bool>)

Also, i don't understand that thing you posted so well... it's like a file format were you store the octree?

Er, does this mean you're worried about disk storage and you're storing your data structures as text?

Yeah, about that...
My editor saves/loads my game content into an intermediate, human-readable and -editable file format as SDL (because it's much cleaner than XML in many respects), which is then compiled to a leaner binary format for the game.
What I'm worried about is that the SDL parser that I use (the open-source C# implementation) is pretty slow for big files, and with dictionaries for the trixels, my trile set files got pretty huge. Also having such huge lists of trixels defeats the "human readability" purpose. But then octrees are even worse.

In the end I'm probably going to go for a custom data structure that "chunks" trixels together into blocks, and saves a list of blocks, like Saint suggested.

Thanks for the insights everyone!