Hello, this is Sasaki from Eukarya.

Our company is currently developing a new 3D map engine. A map engine, like Google Earth, displays a globe in 3D space and allows users to zoom in for more detailed images. It can be used not only for map applications like Google Earth but also for visualizing geospatial data. Examples of existing map engines include CesiumJS and Mapbox GL JS.

When developing a map engine, various LOD (Level of Detail) algorithms are necessary. Through our development process, we’ve learned about many techniques and have compiled our findings.

What is LOD?

In computer graphics, displaying complex 3D models typically consumes a lot of memory and takes time to render. To avoid such issues, LOD is used to display simplified models in situations where fine details aren’t necessary, such as for distant or fast-moving models. Methods like mipmapping, which adjusts texture resolution based on the scene, are also used.

Why is LOD necessary?

As 3D models become more complex, the number of vertices increases, raising the cost of transferring vertices to the GPU. This also increases the computational load. In real-time rendering software, like games or map engines, where massive amounts of processing are required, it’s crucial to minimize waste.

LOD Algorithms

There are various LOD techniques tailored to specific applications or visual requirements. Below are some promising methods we’ve researched.

DLOD (Discrete Levels of Detail)

DLOD uses separate models for each level of detail, switching models based on factors like camera distance.

Three.js provides an API for implementing LOD, and using the LOD.addLevel method, you can specify models and display them based on camera distance.

CLOD (Continuous Levels of Detail)

CLOD determines the appropriate polygon detail of a model based on factors like camera distance. Unlike DLOD, which operates in discrete steps, CLOD allows for continuous adjustment of detail. This means that instead of replacing the entire model, only certain polygons are refined.

As a result, when displaying a large model, parts closer to the camera can be shown with higher detail, while distant parts use fewer polygons.

For example, SSE (Screen Space Error) is a type of CLOD. SSE is an algorithm primarily used in Cesium to efficiently render map tiles and terrain. As introduced in "Optimize Tile Rendering on the Earth Ellipsoid with Culling and SSE," SSE calculates the level of detail for the tiles based on the distance between the camera and the tile.

HLOD (Hierarchical Levels of Detail)

HLOD is a technique used in open-world game scenes to group multiple distant models into a single low-polygon object for efficient rendering.

In complex game scenes, there may be many models to render when looking into the distance. Even if low-polygon models are prepared for each, having too many draw calls can degrade performance. To avoid this, HLOD groups multiple distant models and further simplifies them into a single low-polygon object, reducing draw calls and improving performance.

Unreal Engine provides an automatic feature to generate HLOD for static models.

Virtual Geometry

Previously, calculating which parts of a model to cull had to be done by the CPU. Additionally, when there were large differences in detail between LOD models, switching between them could result in visual discontinuities.

By using the Virtual Geometry technique, a model is clustered polygon by polygon, allowing for culling and continuous transitions in detail for each part of the model.

Unreal Engine’s Nanite feature provides Virtual Geometry functionality. In Nanite, the triangles of a model’s mesh are grouped into small clusters, which are further organized into a tree structure. The root represents a model with fewer polygons, while the branches and leaves correspond to more detailed parts of the model, each mapped to individual clusters.

This allows different parts of a model to be displayed with varying levels of detail, showing low-poly areas and high-poly areas as needed.

By using this tree structure, the shader can perform frustum culling and occlusion culling on an instance-by-instance basis.

The Rust-based game engine, Bevy, is also developing a similar feature, taking inspiration from Nanite to implement these capabilities (reference).

RTIN

RTIN is an algorithm used in map engines for efficient terrain rendering. A well-known library utilizing RTIN is MARTINI, developed by Mapbox.

In brief, this algorithm calculates terrain so that areas with steep slopes are rendered as high-polygon models, while flat areas are depicted with low-polygon models.

The map engine currently in development also employs this algorithm to optimize terrain rendering.

Conclusion

I have learned that there are various optimization techniques for LOD. It's important to choose the appropriate algorithm based on the use case, whether it's an algorithm like HLOD that applies to entire distant scenes or a specialized algorithm like RTIN for map engines.