---

Hello. I'm Sasaki from Eukarya Inc. If you're interested, feel free to follow me on Twitter @_keiya01 (though I don't tweet much).

Our company is developing a new 3D map engine. A map engine is a system that displays a globe in a three-dimensional space, like Google Earth, where zooming in reveals more detailed images. It can be used not only as a map like Google Earth but also for visualizing location data. Examples of existing map engines include Cesium and Mapbox.

To create the appearance of a globe, it is necessary to efficiently render massive satellite images on the Earth's ellipsoid. To achieve this, we use a data structure called a Quadtree, which we will introduce in this Post. While learning about this data structure, we also discovered other spatial partitioning data structures used in 3D Computer Graphics, so we’ve decided to summarize them. We hope this helps you.

Why Spatial Partitioning is Necessary

In computer graphics, when processing relationships between models in a large space, such as collision detection, the computational load can be very high.

For instance, consider a game scene with 10,000 models, each moving randomly, and we need to detect collisions among them.

Typically, collision detection uses something like a bounding box, which encircles the model with a simple surface or line. In this case, simply comparing each model's bounding box linearly results in a computational complexity of O(n^2).

To solve this, we can partition the space and compare only models within the same partition, significantly reducing the computational load.

Moreover, by structuring the space, we can explore parent and child spaces with fewer calculations.

What is Spatial Partitioning

Spatial partitioning in 3D Computer Graphics involves dividing the entire scene into defined ranges to create a data structure that easily references objects within those spaces.

Data structures for spatial partitioning mainly fall into two categories:

1. Those that partition space flatly
2. Those that use tree structures.

Flat data structures are easier to implement but, as the scene's space grows, the number of partitions increases, raising the computational load for exploration.

Conversely, if the partitions are made larger to reduce their number, the number of models in each partition increases, again raising the computational load.

One solution to these issues is using a tree structure to partition the space.

The next section introduces specific data structures and their features.

Spatial Partitioning Data Structures

There are several spatial partitioning data structures. While there are many structures tailored to specific uses, we'll cover the most representative ones here.

Grid

This data structure divides space into a grid at regular intervals, managing the objects placed in each grid. It's a simple grid that can be applied to both 2D and 3D spaces.

By dividing the space as shown in the image below and linking the space with models, calculations between models become easier.

However, as mentioned earlier, a flat data structure means that if the number of spaces increases, the time for exploration also increases. Additionally, if the spaces are made larger to reduce their number, the time for calculations between models increases because there are more models per space.

Quadtree

It's a data structure that recursively divides a single cell of a 2D space's root into four parts to create a tree structure. Sometimes each cell holds data, while other times the division continues until each leaf node holds a single piece of data.

For example, when displaying high-resolution satellite images of the entire Earth on a 3D ellipsoid to represent a globe, the processing load and memory requirements increase significantly. Since the image is 2D, by pre-dividing the large image into tiles and managing these as a quadtree data structure, you can display the optimal resolution image tile based on the camera position.

Map engines like Cesium support "raster tiles," which are image or raster data divided into tiles based on zoom level and ellipsoid coordinates. Since this is essentially a quadtree, storing tile information in the corresponding cells of the quadtree allows easy exploration of optimal tiles based on the camera position.

This can also be used for collision detection in 2D spaces.

Octree

It's a data structure that recursively divides 3D space into eight parts, starting from the center of a cuboid.

It is used for collision detection in 3D spaces, as in examples from Three.js, and for optimizing logic for actions such as model picking or selecting meshes for rendering, as introduced in Optimizing With Octree from Babylon.js.

Bounding Volume Hierarchy (BVH)

BVH is more about accelerating intersection tests by organizing each polygon of a model into a tree structure rather than spatial partitioning.

The mechanism involves recursively splitting the given model into bounding boxes of "appropriate granularity" to create a tree structure. There are various methods for calculating this "appropriate granularity." The image below shows an example of BVH divided using Surface Area Heuristic (SAH), where each leaf node is minimized.

BVH is often used in ray tracing or path tracing to calculate expressions where a model is illuminated by reflections or refractions of light. SAH represents the cost of intersection tests assuming the distribution of rays in the scene is random. At each split point, this cost is compared, and the bounding box is divided at the point where the cost is minimized.

Three.js has a library called three-mesh-bvh for constructing BVH from Three.js meshes. This library offers several methods for splitting bounding boxes, including SAH.

However, note that while SAH can create a relatively neat tree, reducing memory consumption and shortening intersection test time, it takes time to construct the tree.

Using BVH allows fast path tracing on Three.js, as shown in the following demo.

Conclusion

Tree-structured data structures may seem like a silver bullet at first glance, but as the space grows and the number of partitions increases, memory usage also rises. To avoid this, mechanisms like garbage collection to delete unnecessary nodes and strategies for moving models within space with minimal computation are necessary.

Furthermore, while SAH cost calculations for constructing an optimized BVH improve processing speed after construction, they take time to build, so it's important to decide on a strategy based on the desired expression.

That said, understanding these mechanisms can be very beneficial as they can be applied to many scenarios. we felt relearning data structures is very important.

References

• Spatial Partition
• その15 8分木空間分割を最適化する！
• その８ 4分木空間分割を最適化する！（理屈編）
• BVHのはなし
• Bounding Volume Hierarchy (BVH) の実装 - 構築編
• (Task 3) Bounding Volume Hierarchy