Voxel data format

[dougbinks]

This issue is to discuss the format for voxel data.

High level voxel data description

I propose that in order to handle sparsity we allow a single voxel object to be divided up into volumes (for example Minecraft map chunks). If we use glTF these would likely be specified in the JSON part as extensions to the spec.

1. Voxel Object a set of Voxel Volumes, much like a Mesh is a set of primitives.
   1. Attributes (or do we move this to the voxel volume below as a way to support non-interleaved data?)
   2. Volume AABB min: 3 integers (or doubles?)
   3. Volume AABB max: 3 integers (or doubles?)
2. Voxel Volume a set of Voxels occupying a 3D box volume.
   1. Offset coordinates: 3 integers
   2. Volume dimensions: 3 unsigned integers. We may want to limit this size.
   3. Material Type (indexed palette or single material)
   4. Material (integer index to palette or material depending on above)
   5. Buffer View (buffer, offset and length)
   6. Encoding (this could be moved into the voxel object)

If we use JSON the integers above will have precision equal to that of a double maximum, but implementations of gltf readers may differ.

The names Voxel Object and Voxel Volume are tbd.

Voxel Volume Buffer Encoding

1. Run length encoded or other simple format?
2. Bit-depth of count for RLE and for integer values may need to be specified.
3. If we RLE encode do we do so as rows, Morton ordered, or NxN blocks?
4. Do we add bits to encode data presence (i.e. data has certain attributes, is it a single voxel or has a count, see below)
5. Mesh Optimizer may be useful as a pass over the final data (see references below)

Data Presence

Essentially imagine you have two voxel attributes, MATERIAL_INDEX and DENSITY plus we have the RLE_LENGTH. The first bits of the encoding will thus be 3 bits to encode whether these exist in the following data. So 111 would mean we have all, and 110 would mean we have a single voxel with both MATERIAL_INDEX and DENSITY but no RLE_LENGTH, thus making random voxels more efficient than if we needed to encode all. This is similar to the description for the voxel Disk format in Roblox, except there Arseny uses the term occupancy rather than density.

So for the following voxel attributes (bit depth, usage, and type etc. described in Attibutes property as above):
MATERIAL_INDEX: 8bit uint (we can allow lower bit depths as some volumes will have fewer materials etc.)
DENSITY: 8bit uint normalized
with also an RLE_LENGTH : 8bits.

Presence (3bits)	if Presence 0 (8bits)	f Presence 1 (8bits)	if Presence 2 (8bits)
012	MATERIAL_INDEX	DENSITY	RLE_LENGTH-2

Note that since we never see 0 voxels, and 1 voxel is encoded with the RLE_LENGTH a value of 0 in the RLE_LENGTH field can be used to represent 2 voxels.

Example bit pattern for a single voxel with no density (where M is material bits):

100 MMMMMMMM

Example bit pattern for 2 voxels with both material index and density (where M is material bits, D density):

111 MMMMMMMM DDDDDDDD00000000

Example bit pattern for 258 empty voxels:

001 11111111

References:
https://zeux.io/2017/03/27/voxel-terrain-storage/
https://aras-p.info/blog/2023/02/02/Float-Compression-4-Mesh-Optimizer/
https://github.com/zeux/meshoptimizer?tab=readme-ov-file#mesh-compression

Your thoughts are appreciated below!

[scallyw4g]

I think the voxel object / voxel volume pairing makes sense.

I don't like bike-shedding about naming .. but.. I'm not the biggest fan of the name voxel object. Mostly because shorthands (VObject, Object) make it sound like something OOP-y, and the name Object is pretty overloaded at this point. I propose "Volume Group" ..?

We could also consider using the word Chunk instead of Volume .. "Voxel Chunk" & "Chunk Group" ..? Just some thoughts, I don't have particularly strong opinions on names.

For this comment, I'll use Chunk and VGroup to refer to the things you named "Voxel Volume" and "Voxel Object", respectively, cause that's what my brain instinctively went to while typing this comment.

---

Random thoughts on encoding, in order of appearance:

1.a VGroup Attributes

Specifying the Attrs on the VGroup does preclude the possibility of heterogeneous Chunks within a group. One example would be having a fluid sim (which may have, for example, a density attribute), in the same group as regular material-indexed voxel data. I believe this to be an uncommon case.

Specifying Attrs on the Chunk skirts this problem, at the cost of increased data storage size & parsing time, which would be redundant in the common case.

With these two ideas in mind, I would support specifying attrs on the VGroup for three reasons:

1. We still support heterogenous Chunk types; they just have to be in different Groups. (fluid sims have their own groups, regular world data has different groups)
2. I prefer to avoid adding bloat to the format to support the uncommon case of heterogenous VGroups
3. In a future revision of the format, if we decide we do want to specify attrs on Chunks, I claim it is slightly easier to broadcast attrs from VGroup->Chunk, rather than if we decided to go the other way and split VGroups based on their Chunk attrs.

---

As far as supporting non-interleaved (hereafter, contiguous) channel data goes, I propose we could support this in two ways, or leave it unsupported:

Method 1 : A VGroup can be either:

1. a group of contiguous channel buffers that form a many-to-one mapping, creating a "Logical Chunk"

or

2. a group of interleaved channel buffers with a 1:1 mapping of buffer:Chunk

Method 2: We could choose to additionally add "nested VGroups" to the above, which would allow composing contiguous channel "Logical Chunks" into VGroups in the same way we would use interleaved-channel Chunks.

Personally, I see significant complexity and little tangible benefit for supporting contiguous attribute arrays and "Logical" Chunks. I would vote we only support interleaved chunk data for V0, and add contiguous later if we care to. Open to suggestions here if I'm over-complicating it..

---

It's kinda weird that Chunk dimensions are encoded as Min/Dim and VGroup are Min/Max. Is there a reason for that?

I have a minor preference here for Min/Dim because it avoids the failure mode of the Max being less than the Min; it's easier to spot a negative Dim (visually) than it is to spot Max < Min.

I'm not fussy about which choice here, but I do think they should be the same .. unless they're different for a reason that I didn't think of, of course.

---

2.5 Buffer View

Can you elaborate on this? I'm not clear on exactly what this means.

---

Voxel Volume Buffer Encoding

1. RLE seems like a reasonable place to start. Easy enough to support future compression codecs by doing:

{ compression_type: "RLE", compressed_bytes: [...] }

2. I do not have good intuition on an appropriate bit depth for the RLE count. I would imagine it probably varies pretty wildly by application. 8-bit seems like a fine start? Or maybe less? We could always do some quick tests to see what compresses some MC maps the best.. I guess..

3. I'd vote to default to rows, maybe add compression_type: "RLE_Morton" in the future? This is strictly because I don't have a morton-ordering iterator in my engine and I'm being lazy. Surely others will want to be lazy if they're writing their own exporters, too.

4. Not totally sure what you're getting at here

5. Is this just compression_type: "meshopt" ?

I didn't read the zeux.io link, but it looks pretty good. I'll read it later when I've got a bit more mental energy and put thoughts here

[dougbinks]

Naming

Happy to iterate on this, but I'd prefer not to use the term group as this is usually used for a collection of objects, but in this case we want it to be a single object with a sparse representation.

Perhaps:

• Voxel Grid: This defines the voxel scale, size and orientation
• Voxel Array: This has the voxel data.

Voxel Attributes

I agree that I'd prefer these higher in the hierarchy.

Non-interleaved data

I would be happy with only supporting interleaved data to start with, and then expanding if needed.

Dimensions

The difference was just a mistake - I started with Min/Dim which is my preference then changed to Min/Max after re-reading the glTF spec and remembering that's what they tend to use. I'd prefer Min/Dim.

2.5 Buffer View

This is a view into a buffer, as per the glTF spec on Buffer View. For our purposes we need:

1. The buffer where the data is (in glTF this is an index into the array of buffers)
2. byte offset for the start of the voxel data in the buffer
3. byte length of the voxel data in the buffer
4. glTF adds other data which we can initially ignore.

Voxel Volume Buffer Encoding

1. Agree, start with RLE, specify encoding so future additions can be made
2. Agree, 8-bit is likely a good start
3. We could add a Morton iterator in the reference implementation, but I'd be happy to start with a simpler format of rows.
4. I'll revise the description to clarify this. Essentially imagine you have two voxel attributes, MATERIAL_INDEX and DENSITY plus we have the RLE_LENGTH. The first bits of the encoding will thus be 3 bits to encode whether these exist in the following data. So 111 would mean we have all, and 110 would mean we have a single voxel with both MATERIAL_INDEX and DENSITY but no RLE_LENGTH, thus making random voxels more efficient than if we needed to encode all. This is similar to the description for the voxel Disk format in Roblox, except there Arseny uses the term occupancy rather than density.
5. Yes, see mesh Optimizer Mesh compression for more information. Amusingly this is also by Arseny.

[Longor1996]

I'd define things roughly like this, in no particular order:

• Node: A thing that has some transform and references|embeds either a Grid or Chunk.
  • Part of the scene description, thus irrelevant here, only for completeness.
• Grid: Defines a relative-scale and optional bounds (min+dim); references|embeds either a single Chunk, a collection of positioned/blittable Chunks, or a continuous sparse volume (supervolume? region? idk) of Chunks.
  • Also ought to be part of the scene description.
• Chunk: A finite volume of some dimension with metadata/props and internal axis-order, referencing|embedding one-or-more Bricks.
• Brick: A finite flat(!) storage of voxel samples with a given referenced|embedded Layout, a set of referenced|embedded Palettes as the Layout defines/requires, an optional sample Packing method, and a referenced Buffer{-view} that actually holds the Samples.
• Layout: A descriptor of attributes/channels, defining how a single voxel Sample is encoded.
  • Any attribute/channel may, if it's base-type is an unsigned integer, mark itself as using a Palette index.
• Packing: A method (RLE, DEFLATE, ZSTD, etc.) for tightly packing/compressing a series of Samples.
• Sample: A single voxel as defined by a Layout.
• Palette: A homogenous list of things (materials, colors, etc.).
• Buffer{-view}: Same as glTF, but allows for 64-bit sizes and indexing.