The Problem

Hierarchical Level of Detail (HLOD) with 3D Tiles is often accomplished by using replacement refinement. As the camera gets closer to geometry, each tile is replaced by a set of smaller child tiles, each with a higher resolution subset of the geometry. Together, these children present the parent tile’s content in higher detail.

Well-structured bounding volumes are essential for optimal performance because every tile culled is a tile that is not downloaded, processed, or drawn. Each tile contains a bounding volume used for culling, and optionally, a URL referencing the content, i.e., geometry and textures, for the tile. This separation allows Cesium to cull entire tiles without needing to download their contents. If the bounding volumes are not a tight representation of their contents, Cesium may end up downloading tiles whose contents are not truly visible.

To keep Cesium agnostic to the variety of datasets it handles, we place few restrictions on the structure of the 3D tileset. For example, bounding volumes are not required to tightly wrap their contents. However, unstructured data can lead to poor performance. The following scenarios can result in suboptimal tile bounding volumes (parent contents and bounding volumes in blue, children in green):

Children of a parent tile are not tightly packed. This causes large empty regions in the parent bounding volume. Children of a parent tile vary greatly in size. This causes the parent bounding volume to have large empty spaces. Parent bounding volume does not tightly enclose children. It does not accurately represent the size of the content.


In each of these scenarios, a parent bounding volume may intersect the view frustum although none of its children intersect. The parent tile will be downloaded even if its contents are not actually in the view frustum. In the diagrams above, the union of the children bounding volumes (green) is a much more accurate approximation of the geometry than the parent bounding volume (blue).

One Level Deeper

Our solution is to check if at least one of the child tiles is visible before selecting the parent tile for traversal. The additional check is an extra CPU cost, but it often improves performance by reducing the number of tiles downloaded and drawn. The check lets us avoid downloading any content at all if no children bounding volumes are visible since all tile bounding volumes are already in memory and tile contents are requested separately. This is especially beneficial for tiles containing heavy textures. Every tile Cesium doesn’t download helps improve performance.

Results

Tests with tilesets of Rio de Janeiro showed measurable speedups in framerate due to the reduced number of draw calls, and in all test cases, we saw either a reduction or no change in the amount of data requested with no significant CPU cost per frame for the additional checks.

Philly Downward View

In the Philadelphia tileset, bounding boxes contain sparse and irregular building content. The non-optimized code is likely to select large tiles even though they may be mostly empty. Two buildings in the original image (left) are located in a single large tile that overlaps the frustum. Its children are much smaller and are not visible to the camera.

Original Optimized
Requests 99 84
Data (MB) 8.2 7.1
Selected 27 21
Commands 27 21
Time (ms) 18.3 18.3


Philly Three-Quarter View

In a three-quarter view of the Philadelphia tileset, only a few extra tiles get culled by the optimization because few bounding boxes overlap the eye position.

Original Optimized
Requests 305 304
Data (MB) 9.1 9.1
Selected 196 195
Commands 196 195
Time (ms) 14.3 14.3


Rio Three-Quarter View

In the Rio tileset, bounding boxes around the terrain do not fit tightly, resulting in many extra tiles selected in the non-optimized version of the code.

Original Optimized
Requests 95 90
Data (MB) 14.9 14.5
Selected 33 27
Commands 94 81
Time (ms) 15.4 15.2


Conclusions

Our tests show that this optimization consistently reduces the number of tiles downloaded without any negative consequences for performance. The efficacy of the extra culling checks depends on the tileset structure and the camera position, but the extra checks do not negatively impact performance even if only a few tiles are culled. Only tiles partially inside the view frustum, which is only a small fraction of visible tiles, require the extra computation. Given the decreases in downloaded tile content, this optimization seems well worth the added complexity and computation.

Caveats

  • The optimization only works with replacement refinement. With additive refinement, the union of the child bounding volumes may not fully contain the parent tile’s content.
  • The optimization is more useful for sparse or non-uniform tilesets. There are no performance improvements if the union of the children bounds is equal to that of the parent like a standard octree or quadtree without tight-fitting bounding volumes.