L. Spiro Engine

Hey Spiro,

since I just registered and this is my first post let me start out with saying that I've stumbled across a lot of your posts on gamedev as well as your blog multiple times since I've started learning game development and a lot of those posts and blog entries have helped me out greatly, so thanks
Ever since I started out working on my terrain and implementing new algorithms I wanted to make it bigger and bigger and I am now at a point where I'm starting to look into planetary rendering using "GPU based chunked lod" (vertex texture fetching of heightmaps). While earlier I could use an array as representation of my quadtree this is no longer the case due to the sheer amount of nodes (tree depth of 21). Due to this I am using a dynamic quadtree in which I create and destroy nodes as necessary which brings me to my point: cache misses.
Do you know of any algorithms or papers that could help me out with this problem? Just allocating the nodes from a pool is not gonna cut it I assume?

Best regards,
waYne

If you must use a dynamic system, at the very least you need to create buckets of nodes, not just an allocation for a single node.
How many nodes in a bucket is up to your implementation and you will need to experiment.

If possible, remember to prefetch as much as you can.


L. Spiro

you mean if I have to split a node I should "pre-split" the next few levels as well and throw that part of the tree into its own array?

thanks,
waYne

I don’t know what you mean by “splitting a node”.
I am only talking about a node-allocation strategy. For best cache usage, yes you would want to try to put related nodes together inside the same bucket, which likely means X number of children.


L. Spiro

By splitting I just meant representing a node by it's children.
I've looked into some code samples that use large quadtrees (virtual texturing, planetary renderers etc.) and they all simply use an array to represent the immediate children of each node. I am not sure if I can get much of a performance gain having larger buckets so I'm just gonna stay with that solution for now.

tyvm for all your input