# Demystifying “chunked level of detail”

Just recently trying to make sense of implementing a chunked level of detail system in Unity. I'm going to be generating four mesh planes, each with a height map but I guess that isn't too important at the moment. I have a lot of questions after reading up about this technique, I hope this isn't too much to ask all in one go, but I would be extremely grateful for someone to help me make sense of this technique.

1 : I can't understand at which point down the Chunked LOD pipeline that the mesh gets split into chunks. Is this during the initial mesh generation, or is there a separate algorithm which does this.

2 : I understand that a Quadtree data structure is used to store the Chunked LOD data, I think i'm missing the point a bit, but Is the quadtree storing vertex and triangles data for each subdivision level?

3a : How is the camera distance usually calculated. When reading up about quadtree's, Axis-aligned bounding box's are mentioned a lot. In this case would each chunk have a collision bounding box to detect the camera or player is nearby? or is there a better way of doing this? (raycast maybe?)

3b : Do the chunks calculate the camera distance themselves?

4 : Does each chunk have the same "resolution". for example at top level the mesh will be 32x32, will each subdivided node also be 32x32. Example below:

-
If anyone knows a better LOD approach for a procedural planet that would also be interesting. – Caius Eugene Dec 11 '12 at 10:19
I presume you have already looked at Thatcher Ulrich's original SIGGRAPH paper and the associated program? tulrich.com/geekstuff/chunklod.html – drxzcl Dec 11 '12 at 22:00
I have, it's very informative up to a point but it doesn't go into the type of detail, or approaches to implementation. Thank you – Caius Eugene Dec 12 '12 at 0:07
There are a number of options for planetary LOD here; vterrain.org/LOD/spherical.html – OriginalDaemon Dec 12 '12 at 18:01

1 : I can't understand at which point down the Chunked LOD pipeline that the mesh gets split into chunks. Is this during the initial mesh generation, or is there a separate algorithm which does this.

It does not matter. For example, you can integrate the chunking into your mesh generation algorithm. You can even do this dynamically, so that lower levels are added dynamically (e.g. as player moves closer) using a plasma-like refinement algorithm. You can also generate a high-resolution mesh from artist input or elevation measurement data and aggregate it up into all the LOD chunks at asset finalization time. Or you can mix-and-match. It really depends on your application.

2 : I understand that a Quadtree data structure is used to store the Chunked LOD data, I think i'm missing the point a bit, but Is the quadtree storing vertex and triangles data for each subdivision level?

Not necessarily. The tree just stores information about the geometry and how to render it. This could mean having an vertex/face list at every tree node. More realistically in this day and age, you would store the handles of the meshes/instances in GPU memory.

3a : How is the camera distance usually calculated. When reading up about quadtree's, Axis-aligned bounding box's are mentioned a lot. In this case would each chunk have a collision bounding box to detect the camera or player is nearby? or is there a better way of doing this? (raycast maybe?)

A very cheap and easy option is to use the distance to the centre point of the chunk and then correct it. You know that this distance is always an underestimation: if the centre point is at distance `Z`, this means that half the chunk is closer than that. What we do not know however is the orientation. If we are viewing a chunk of width `w` edge-on, the closest bit of the chunk will be at distance `Z-w`. However, if we are viewing the chunk corner-first, the closest bit will be at distance `Z-sqrt(2)*w`. If you can live with this uncertainty (you almost always can), you are done. Note that you could also correct for the viewing angle using basic trigonometry.

I prefer to calculate the absolute minimum distance from the camera to the chunk to minimize artifacts. In practice, this means doing a point-square distance test. It's a bit more work then calculating distances to the centre points, but it's not like you'll do a zillion of these every frame.

If you can leverage your physics engine to do this then by all means do so, but you really want to think about it more in terms of "distance query" than "collision".

3b : Do the chunks calculate the camera distance themselves?

It really depends on the design of your engine. I would recommend keeping the leaves relatively light-weight though. Depending on your platform, just the call overhead of having a few thousand terrain-chunks perform their own update every frame can seriously impact performance.

4 : Does each chunk have the same "resolution". for example at top level the mesh will be 32x32, will each subdivided node also be 32x32.

They do not have to, but it's convenient if all chunks take up the same amount of space. Then you can do your (GPU) memory management in units of "chunks". It's also easier to remove / hide the seams between two chunks of different sizes if one resolution is a multiple of the other because they share more vertices. (e.g.: 32x32 and 64x64 is easier to manage than 32x32 and 57x57) (thanks Guiber!). If you have a good reason to vary the chunk geometry size, by all means go for it.

-
It's also easier to remove / hide the seams between two chunks of different sizes if one resolution is a multiple of the other because they share more vertices. (e.g.: 32x32 and 64x64 is easier to manage than 32x32 and 57x57) – Alayric Dec 12 '12 at 21:50
Brilliant answer, It's cleared up a lot of things. Particularly that a lot of the implementation is down to considering the engine's capabilities. With 3a I'm still unsure as to when to fire a distance query, the two implementations I've considered sound CPU heavy, I will do some more research on this. Thank you – Caius Eugene Dec 13 '12 at 9:00
Guiber, you are right! I'm stealing that :P – drxzcl Dec 13 '12 at 18:55
@CaiusEugene: I think you are over-thinking your distance determination. I added a very cheap, very basic algorithm to the reply at point 3a that should get you started. – drxzcl Dec 13 '12 at 21:33