Hierarchical Culling With Children Bounding Volumes
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 |
Original
Optimized
| Requests | 305 | 304 |
|---|---|---|
| Data (MB | 9.1 | 9.1 |
| Selected | 196 | 195 |
| Commands | 196 | 195 |
| Time (ms) | 14.3 | 14.3 |
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.