Overview

Reticulate is a Sparse Voxel Octree mesher with an optional integration into the bevy game engine.

Features

These are the high-level features currently implemented:

• A Sparse Voxel Octree data structure variants for reading and editing
• A mesher component supporting materials up to 16bits
• Few criterion benchmarks for chunk meshing
• A small bevy demo

The mesh generated by the Reticulate mesher is guaranteed to have these features:

• The number of triangles in a single-material mesh is guaranteed minimal
• The number of triangles in a multi-material mesh is very close to minimal
• The mesh is watertight with no t-junctions of any kind

On the roadmap:

• The machinery to manage multiple chunks. Moreover, the last layer of the chunk along each axis is not currently rendereda and that will be fixed by seeding the next chunk.
• Raycasting to determine voxel coordinates from screen coordinates

Benchmarks

To run the benchmarks execute this command:

cargo bench -p reticulate-bench --bench chunk

If you want to have an extra report of metrics enable the metrics-recording feature from the command line:

cargo bench -p reticulate-bench --bench chunk --features "metrics_recording"

Enabling metrics has a noticeable impact on performance. Please note that the numbers provided in the report won't probably match with the ones provided by criterion as there is no statistical normalization behind them.

This is a summary of the Criterion time results from provided scenarios running on a MacBook Pro M4:

Demo

To run the bevy demo of the mesher run the following command:

cargo -p reticulate-bevy run --profile release

Loading demo…

Definitions

Planes and faces

The three-dimensional space of the chunk can be sliced along each axis; for example, slicing along the X axis we can get a Plane that is defined each by given a X and varying Y and Z.

When reasoning locally to a plane we use U and V as stand-ins for the varying coordinates of the given plane; U can be also referred to as Row and V can be also referred to as Column in the plane context. These are the mappings of U/V coordinates for each plane:

The fixed coordinate when referring to planes can be also refferred to as Layer when convenient in the bitfields context. Layers are 0-based and identify the surface between voxel layer and voxel layer - 1 on its perpendicular axis. There are 33 surfaces along each axis in each chunk but each chunk owns only the layers 0-31, leaving layer 32 to be owned by the upper chunk along that particular axis.

A Face is defined as a portion of a layer and a positive/negative direction (i.e. its normal along its perpendicular axis).

Morton codes

Morton codes index the voxel data and are used to power the octree implementations and to enable efficient scanning of the plane surfaces in several places.

The morton code is implemented by wrapping a u32 mask and a Depth field; this implementation will encode the coordinates in the LSB of the mask and it will use the zyxzyx... interleaving scheme for 3D data and the vuvu... scheme for 2D data.

The Depth value of a morton code univocally identifies which area/volume of the quadtree (2D) or octree (3D) they represent. At Depth = 0 there is only one valid Morton code, i.e. 0, and it represents the full area/volume of the chunk (or chunk layer). Each Depth increase up to 5 represent a subdivision of the 2D area by 4 or 3D volume by 8. At Depth = 5 the Morton index will identify a single 3D voxel or 2D texel.

Meshing bitfields

The working state of the mesher is all represented in a dense bitfield backed by arrays of integers. The total working state for meshing comes up to about 30Kb plus some transient registers. This state is statically allocated on the stack as part of the Mesher instance.

Material

A 32×32 plane of 16-bit material ids per X/Y/Z axis. Each material plane is indexed in Morton order and accessed using quadtree semantics. The material plane is used for determining internal occlusion, deriving the parity field and assigning materials to the emitted triangles.

The parity bitfield occupies a total of 6 KB.

Parity

The parity field of an axis stores one bit per possible material transition in the chunk along that particular axis. A 0 represents no transition, a 1 represents a solid/empty or a material/other-material transition between two adjacent cells.

Given a cell at Coords3D(cx, cy, cz), this is how the Parity field encodes information about it along each axis:

That is, the bit k of the column identified by the other two axis represents the transition between coordinate k and coordinatek - 1. Bits in the parity field used to identify walls and derive t-junction vertices.

The parity bitfield occupies a total of 12 KB.

Claims

The claims field of an axis stores one bit per possible claimable cell of the chunk's total surface. A 1 means that that cell has already been emitted as part of a triangle; a 0 means that that cell has not been included in any emitted triangle.

This is how layer, u and v are mapped in each axis field:

The claims bitfield occupies a total of 12 KB.

Octree

Reticulate uses a Linear Sparse Voxel Octree to represent the voxel data for a chunk. The current implementation has a minimal interface consisting of two variants: one that is read-optimized (Compact) and one that is write-optimized (Fixed 8-slot).

Compact

The compact representation only stores the leaves that actually have any data. This reduces the amount of stored data, improves its locality and speeds up traversal as a result. This representation is that it is read-only: to edit the octree it is required to convert it into a Fixed8 variant.

Fixed 8-slot

The fixed 8-slot representation will always allocate leaves for any branch, even if they are empty. This pre-allocation allows us to edit it without costly operations such as moving data around the backing vector.

Setting a child-leaf will just use the pre-allocated slot, setting a child-branch will use the slot to set a pointer to a newly allocated 8-slots chunk.

Traversal of the 8-slot variant will be slightly more inefficient because of the empty-slot skips and the breakings in locality introduced by the edits.

Walking

The octrees can be walked in morton-order following a z-order curve of depth 5 along the voxels in the chunk. This curve arises from the Morton encoding of chunk coordinates.

Walking an octree happens as a single scan of the underlying vector and it triggers the following events:

• on_branch_start: when visiting the beginning of a subdivision of the volume
• on_leaf: when visiting a part of the volume that is uniform and solid
• on_empty: when visiting a part of the volume that is uniformly empty
• on_branch_end: when terminating the visit of subdivisions of the volume

There are some guarantees provided by the implemented walks:

• Volumes will be visited following the z-order curve
• All descendants of a subdivisions are guaranteed to be visited between on_branch_start and on_branch_end for that particular subdivision

There are two variants of the walker interface:

• Walker: only walks defined data, i.e. doesn't trigger on_empty events
• DenseWalker: walsk the full volume, triggering on_empty when required

Mesher

The mesher component produces triangles from a tree and a closure that translates tree data into 16bit material identifiers. The interface consists of a callback-based API defined as follows:

impl Mesher {
    pub fn make_triangles<Data>(
        &mut self,
        tree: impl DenseWalk<Data>,
        to_material: FnMut(Data) -> MaterialId,
        on_triangle: FnMut(Triangle)
    )
}

The mesher is implemented as a double walk over the provided tree:

• A first gathering walk that builds the Parity field while comparing materials at volume boundaries
• A second scanning walk that builds the mesh by using the tree volumes as seed points for a fill-weave-claim procedure that builds greedy triangles

Both walks rely on a Morton-based volume-sweeping mechanism that treats the three axis-planes in the Material bitfields as caches of local information.

Gathering

While gathering, the mesher uses the Material bitfield to determine what is the material of the voxel below the current one along each axis. If that material differs from the one of the volume we are visiting we register this in the Parity bitfield. Empty volumes are treated as their own material for the purpose of this.

Scanning

During the scanning phase the mesher uses again the Material bitfield, this time to determine which areas are at a solid/empty boundary and to assing materials to the emitted triangles. Areas that are at a solid/solid or empty/empty boundary do not produce any surfaces, so they are skipped.

This is the structure of the scanning walk:

• Branch start/end events are not used
• While visiting a leaf we will scan Negative faces along an axis when the voxel below the visiting leaf along that axis is empty. The material of emitted triangles will be the one of the visiting leaf
• While visiting an empty volume in the tree we will scan Positive faces along an axis when the voxel below the visiting leaf along that axis is solid. The material of the emitted triangles will be the one present on the relevant Material plane

The tree walk is used here as an optimized alternatative to querying the tree for materials during a layer-by-layer Parity scan. Visited leaf/empty volumes of the tree are used instead to identify seeds cells in the Parity fields and triangulate their connected regions.

The process of triangulation from a given seed works as follows:

1. Check claims - Check that the seed cell is not in a claimed area; skip the rest of the process if it is.
2. Fill connected retion - From the parity field starting from the seed cell. Walls come from the parity of the perpendicular axis on this slab and the previous one (a face lies between the two slabs). Parity guards between rows stop growth across material transitions, and claimed cells are avoided. The result is one u32 row mask per row.
3. Weave connected region - The weaver sweeps the region row by row. It tracks a set of open vertices that sit in the cells below; it uses the the horizontal stretches of cells in the current row with the tracked vertices to weave a trip of triangles. It then identifies the new open vertices and steps to the next row where there is any parity transition to repeat the process.
4. Claim - Stamp the connected region onto the appropriate layer of the Claims bitfield as a mask of 1 values.

Triangle

The Triangle structure gives access to the following notable APIs:

• triangle.owtward_vertices() - gets vertices ordered such that the impled normal points away from the solid side
• triangle.material() - associated material identifier (u16)
• triangle.face() - on which face (axis + direction) of the solid is the triangle sitting

Vertices are in chunk-local voxel corner coordinates (0 to 32 included).

Minimality

Single-material meshes will have the minimum number of triangles required by the topology. Multi-material meshes could have some extra vertices due to the fact that the parity approach can only tell about tranitions but not occupancy of a particular cell. As a result, if a transition is buried under a uniform wall the wall will get an extra vertex that could actually have been simplified. This should happen in a small number of non-degenerate cases.