Voxels

[IanLilleyT]

Opening a draft PR for early feedback. There's still more code to write and I'll be filling in a lot more details as the ~~day~~ month goes on.

Primitive

A voxel primitive gets data from a voxel provider and renders it in the scene. It has a lot in common with other primitives in CesiumJS in that it is updated every frame based on camera position and submits draw commands. Multiple voxel primitives can get data from the same voxel provider, allowing for different ways of rendering the same underlying datasets.

Basic

A voxel primitive with no options. It will be located at the center of the earth. The default model matrix is identity, the default provider is a 1x1x1 voxel grid, and the default custom shader is white.

const primitive = new Cesium.VoxelPrimitive();

Full example with local sandcastle

Model Matrix

Use the modelMatrix option to put the voxel primitive above the earth's surface.

const primitive = new Cesium.VoxelPrimitive({
  modelMatrix: Cesium.Transforms.eastNorthUpToFixedFrame(
    Cesium.Cartesian3.fromDegrees(-123.0744619, 44.0503706, 2.0)
  )
});

Full example with local sandcastle

Custom Shader

Voxels can be shaded in many different ways. In this example it draws the color of the box's coordinate system. X = red, Y = green, Z = blue.

const primitive = new Cesium.VoxelPrimitive({
  modelMatrix: Cesium.Transforms.eastNorthUpToFixedFrame(
    Cesium.Cartesian3.fromDegrees(-123.0744619, 44.0503706, 2.0)
  ),
  customShader: new Cesium.CustomShader({
    fragmentShaderText:
     `void fragmentMain(FragmentInput fsInput, inout czm_modelMaterial material)
      {
          material.diffuse = fsInput.voxel.positionShapeUv;
          material.alpha = 1.0;
      }`,
  })
});

Full example with local sandcastle

Custom Provider

This example uses a custom voxel provider to create procedural data. The color metadata has an alpha component that makes it look like an octant of a sphere, even though the voxel shape is a box. Note how the edges are mushy, this is because the voxel grid is only 32x32x32 voxels. A larger voxel grid would create a crisper shape.

function CustomVoxelProvider() {
  this.ready = true;
  this.readyPromise = Promise.resolve(this);
  this.shape = Cesium.VoxelShapeType.BOX;
  this.dimensions = new Cesium.Cartesian3(32, 32, 32);
  this.names = ["color"];
  this.types = [Cesium.MetadataType.VEC4];
  this.componentTypes = [Cesium.MetadataComponentType.FLOAT32];
  this.maximumTileCount = 1;
}

CustomVoxelProvider.prototype.requestData = function (options) {
  const tileLevel = Cesium.defined(options) ? Cesium.defaultValue(options.tileLevel, 0) : 0;
  if (tileLevel >= 1) { return undefined; }
  const dimensions = this.dimensions;
  const voxelCount = dimensions.x * dimensions.y * dimensions.z;
  const channelCount = Cesium.MetadataType.getComponentCount(this.types[0]);
  const metadata = new Float32Array(voxelCount * channelCount);
  for (let z = 0; z < dimensions.z; z++) {
    for (let y = 0; y < dimensions.y; y++) {
      for (let x = 0; x < dimensions.x; x++) {
        const index = z * dimensions.y * dimensions.x + y * dimensions.x + x;
        const lerpX = x / (dimensions.x - 1);
        const lerpY = y / (dimensions.y - 1);
        const lerpZ = z / (dimensions.z - 1);
        const dist = Math.sqrt(lerpX * lerpX + lerpY * lerpY + lerpZ * lerpZ);
        metadata[index * channelCount + 0] = lerpX;
        metadata[index * channelCount + 1] = lerpY;
        metadata[index * channelCount + 2] = lerpZ;
        metadata[index * channelCount + 3] = dist < 1.0 ? 1.0 : 0.0;
      }
    }
  }
  return Promise.resolve([metadata]);
};

const primitive = new Cesium.VoxelPrimitive({
  modelMatrix: Cesium.Transforms.eastNorthUpToFixedFrame(
    Cesium.Cartesian3.fromDegrees(-123.0744619, 44.0503706, 2.0)
  ),
  customShader: new Cesium.CustomShader({
    fragmentShaderText:
     `void fragmentMain(FragmentInput fsInput, inout czm_modelMaterial material)
      {
          material.diffuse = fsInput.metadata.color.rgb;
          material.alpha = fsInput.metadata.color.a;
      }`,
  }),
  provider: new CustomVoxelProvider()
});

Full example with local sandcastle

Provider

To do

glTF

To do

3D Tiles

To do

Procedural

To do

Traversal

To do

Shapes

Here's a video showing the different kinds of shapes supported by the voxel system. The data is one procedurally generated tile that is completely opaque (to make it easier to see the surface). If something looks like a bug, it probably is. There are several edge cases that still need to be fixed. Also please ignore the bad framerate. It's smoother in person.

https://user-images.githubusercontent.com/1328450/163496465-94f79680-6c8b-4efa-a30b-fa9042f6c1f7.mp4

Currently it supports box, ellipsoid, and cylinder shapes - and each of them can be stretched and smooshed in a number of ways, sometimes becoming 2D surfaces. Out of all the shapes, box has the best performance because the shader doesn't have to do as many coordinate conversions, but it might not be the most natural choice for all kinds of data. For example, ocean temperature data is often gridded by latitude, longitude, and depth, so the most accurate fit for the data would be the ellipsoid shape. In some cases it may make sense to resample the data to fit another shape, but that's a decision left to the user and their data pipeline.

In the future there could be other kinds of shapes such as cone or torus. All that's needed is some sort of 3D coordinate system that can be gridded into voxels.

Each shape inherits from VoxelShape.js and is responsible for computing:

• Bounding box and bounding sphere for the full shape. Used for culling the primitive and other optimizations.
• Bounding box for subregions of the shape, aka tiles. Used for screen space error and culling.
• Shader uniforms and defines. This opens up a lot of room for shape-specific optimizations and precision improvements. For example, a 2D box goes down some different code paths than a 3D box because it's cheaper, despite being the same core shape. The shader will be recompiled whenever the shape's configuration changes by detecting differences in shader defines from the previous frame. This could lead to performance hitches depending on how the shape is changed at runtime, so there may need to be an option to use uniforms instead of defines, at the cost of a more branch-heavy shader.

Coordinate systems

There a lot of different coordinate systems and "spaces" throughout the code. Still working on making this terminology consistent everywhere:

• World Space - aka Cartesian space.
• World UV Space - Or just UV Space for short. The space contained by the shape's oriented bounding box, where (0,0,0) is the bottom corner and (1,1,1) is the top corner. This is where all the raymarching happens as it maps very closely to texture coordinates when sampling voxel data for the box shape and has decent floating point precision.
• World Local space - Or just Local Space for short. UV space mapped to (-1,-1,-1) to (+1,+1,+1).
• Shape Space - The shape's native coordinate system. For box it would be (-1,-1,-1) to (+1,+1,+1). For ellipsoid it would be (-pi, -halfPi, -inf) to (+pi, +halfPi, +inf). For cylinder it would be (0,-1,-pi) to (1,+1,+pi). UV space is converted to shape space at every step in the raymarch, and can be costly. For example, the ellipsoid shape needs to do an iterative ellipse/ellipsoid distance.
• Shape UV Space - Similar to shape space, but compressed into a (0,0,0) to (1,1,1) range based on the shape's bounds. For example, if an ellipsoid shape's longitude goes from 10 degrees to 20 degrees, 10 degrees will map to 0.0, 15 degrees will map to 0.5, 20 degrees will map to 1.0, etc.
• Tile UV Space - Shape UV space divided into tiles. At the first level of the octree it will be identical to shape UV space. At level 1 it will subdivided into 8 tiles. At level 2, 64 tiles.
• Tile Voxel Space - Similar to tile uv space, but converted to voxel coordinates and clamped to (0.5,0.5,0.5) to (voxelDimX-0.5, voxelDimY-0.5, voxelDimZ-0.5) to avoid accidentally reading neighboring data in the megatexture when linear texture sampling is on. This space also handles padding (more explanation needed for padding...).
• Tile Megatexture Space - The space that reads voxel data. It's a mapping from tile voxel space to a region of the megatexture. The texcoord offset is derived from the tile's index in the megatexture and the scale is constant because all tiles take up the same number of texels. The 3D megatexture encoding can simply do texture3d(megatexture, texcoord). The 2D megatexture encoding (for WebGL 1) is a bit more complicated because it needs to mimic the 3d linear sampling in software.

Shape Bounds and Clip Bounds

shapeMinBounds and shapeMaxBounds controls where voxel data exists in the shape's coordinate system. For example, to create an ellipsoid shape that covers the top half of the globe, set shapeMinBounds.y to 0.0 and shapeMaxBounds.y to halfPi.

clipMinBounds and clipMaxBounds is similar but controls where voxel data is rendered.

Here's a video showing both options:

https://user-images.githubusercontent.com/1328450/164519464-a8a70d74-afd2-4dd1-94ce-47fbcf0685fb.mp4

Shader

Performance

Inspector

To-do:

• [x] Ellipsoid shape
• [x] Shape space clipping bounds
• [ ] More unit tests for VoxelPrimitive

Thanks to @ErixenCruz, @krupkad, @lilleyse, and many others for their contributions, ideas, and feedback.

[cesium-concierge]

Thanks for the pull request @IanLilleyT!

• :heavy_check_mark: Signed CLA found.
• :grey_question: CHANGES.md was not updated.
  • If this change updates the public API in any way, please add a bullet point to CHANGES.md.
• :grey_question: Unit tests were not updated.
  • Make sure you've updated tests to reflect your changes, added tests for any new code, and ran the code coverage tool.

Reviewers, don't forget to make sure that:

• [ ] Cesium Viewer works.
• [ ] Works in 2D/CV.

[cesium-concierge]

Thanks again for your contribution @IanLilleyT!

No one has commented on this pull request in 90 days. Maintainers, can you review, merge or close to keep things tidy?

I'm going to re-bump this in 90 days. If you'd like me to stop, just comment with @cesium-concierge stop. If you want me to start again, just delete the comment.

[jjhembd]

On Windows, I can't get the Voxels Sandcastle to work. There is a linking error:

[Cesium WebGL] Shader program link log: C:\fakepath(1164,8-66): error X3067: 'f_getPropertiesFromMegatexture__SampleData': ambiguous function call

The function getPropertiesFromMegatexture has an overloaded definition to input an array of SampleDatas. I can fix this error by renaming the overloaded function as accumulatePropertiesFromMegatexture. But then I get the following error:

RuntimeError: Program failed to link.  Link log: C:\fakepath(960,2-33): warning X3550: array reference cannot be used as an l-value; not natively addressable, forcing loop to unroll
C:\fakepath(1279,3-49): warning X3557: loop only executes for 1 iteration(s), forcing loop to unroll
C:\fakepath(1208,3-49): warning X3557: loop only executes for 1 iteration(s), forcing loop to unroll
C:\fakepath(1447,7-80): warning X3557: loop only executes for 0 iteration(s), consider removing [loop]
C:\fakepath(1360,3-49): warning X3557: loop only executes for 1 iteration(s), forcing loop to unroll
C:\fakepath(1250,3-49): warning X3557: loop only executes for 1 iteration(s), forcing loop to unroll
error X8000: D3D11 Internal Compiler Error: Invalid Bytecode: Index Dimension 1 out of range (1399 specified, max allowed is 31) for operand #2 of opcode #303 (counts are 1-based). Aborting.
error X8000: D3D11 Internal Compiler Error: Invalid Bytecode: Can't continue validation - aborting.

Warning: D3D shader compilation failed with default flags. (ps_5_0)
 Retrying with skip validation
C:\fakepath(960,2-33): warning X3550: array reference cannot be used as an l-value; not natively addressable, forcing loop to unroll
C:\fakepath(1279,3-49): warning X3557: loop only executes for 1 iteration(s), forcing loop to unroll
C:\fakepath(1208,3-49): warning X3557: loop only executes for 1 iteration(s), forcing loop to unroll
C:\fakepath(1447,7-80): warning X3557: loop only executes for 0 iteration(s), consider removing [loop]
C:\fakepath(1360,3-49): warning X3557: loop only executes for 1 iteration(s), forcing loop to unroll
C:\fakepath(1250,3-49): warning X3557: loop only executes for 1 iteration(s), forcing loop to unroll
error X8000: D3D11 Internal Compiler Error: Invalid Bytecode: Index Dimension 1 out of range (1399 specified, max allowed is 31) for operand #2 of opcode #303 (counts are 1-based). Aborting.
error X8000: D3D11 Internal Compiler Error: Invalid Bytecode: Can't continue validation - aborting.

Warning: D3D shader compilation failed with skip validation flags. (ps_5_0)
 Retrying with skip optimization
C:\fakepath(960,2-33): warning X3550: array reference cannot be used as an l-value; not natively addressable, forcing loop to unroll
C:\fakepath(1279,3-49): warning X3557: loop only executes for 1 iteration(s), forcing loop to unroll
C:\fakepath(1208,3-49): warning X3557: loop only executes for 1 iteration(s), forcing loop to unroll
C:\fakepath(1447,7-80): error X3531: can't unroll loops marked with loop attribute

C:\fakepath(960,2-33): warning X3550: array reference cannot be used as an l-value; not natively addressable, forcing loop to unroll
C:\fakepath(1279,3-49): warning X3557: loop only executes for 1 iteration(s), forcing loop to unroll
C:\fakepath(1208,3-49): warning X3557: loop only executes for 1 iteration(s), forcing loop to unroll
C:\fakepath(757,12-35): error X3512: sampler array index must be a literal expression
C:\fakepath(1447,7-80): error X3511: forced to unroll loop, but unrolling failed.

Warning: D3D shader compilation failed with skip optimization flags. (ps_5_0)

Failed to create D3D Shaders

I think the key message might be this one: error X3531: can't unroll loops marked with loop attribute.

[jjhembd]

Running the Sandcastle with a WebGL2 context gives the same error. I confirmed that the failing shader has been translated as expected by modernizeShader:

[Cesium WebGL] Translated fragment shaderSource:
// FRAGMENT SHADER BEGIN

// GLSL BEGIN

#version 300 es
#define WEBGL_2

[cesium-concierge]

Thanks again for your contribution @IanLilleyT!

No one has commented on this pull request in 90 days. Maintainers, can you review, merge or close to keep things tidy?

I'm going to re-bump this in 90 days. If you'd like me to stop, just comment with @cesium-concierge stop. If you want me to start again, just delete the comment.

[ggetz]

Thanks @IanLilleyT, @lilleyse, @ptrgags, and @jjhembd! Great to get an initial implementation in! While we'll still need to finalize the format, the API, and the sandcastle examples, this is an exciting first step and a lot of progress has been made!