Dynamic Trees and cache misses

Discussions Related to Graphics Technology in General

Dynamic Trees and cache misses

Postby waYne » Wed Apr 08, 2015 10:58 am

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 :D
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
waYne
I Have a Question
 
Posts: 3
Joined: Wed Apr 08, 2015 10:45 am

Re: Dynamic Trees and cache misses

Postby L. Spiro » Tue Apr 28, 2015 8:51 am

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
It is amazing how often people try to be unique, and yet they are always trying to make others be like them.
- L. Spiro 2011
L. Spiro
Site Admin
 
Posts: 54
Joined: Thu Jul 21, 2011 2:59 pm
Location: Tokyo, Japan

Re: Dynamic Trees and cache misses

Postby waYne » Wed May 27, 2015 8:35 am

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
waYne
I Have a Question
 
Posts: 3
Joined: Wed Apr 08, 2015 10:45 am

Re: Dynamic Trees and cache misses

Postby L. Spiro » Sat Jun 13, 2015 11:10 am

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
It is amazing how often people try to be unique, and yet they are always trying to make others be like them.
- L. Spiro 2011
L. Spiro
Site Admin
 
Posts: 54
Joined: Thu Jul 21, 2011 2:59 pm
Location: Tokyo, Japan

Re: Dynamic Trees and cache misses

Postby waYne » Mon Jul 20, 2015 10:22 am

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
waYne
I Have a Question
 
Posts: 3
Joined: Wed Apr 08, 2015 10:45 am


Return to Other Graphics Technology

Who is online

Users browsing this forum: No registered users and 0 guests

cron