Sparse Array storage.

[emilian0]

Rationale
Sparse arrays are sometimes more efficient than dense arrays when describing incremental changes.

This scenario is common when encoding morph targets ( #210 ) that often display localized deformations (for instance, for a facial morph, a "blink-left" morph target will only displace vertices around the left eye). It is inefficient to re-transmit an entire full set of vertices positions when only a few of them were displaced. It is, in general, more efficient to just encode the indices and values of those vertices that were displaced in the morph target.

Following the COLLADA extension presented here, I suggest to include sparse array storage in the core glTF specs.

Possible implementation
glTF uses buffers to store data and accessors to retrieve it. I believe accessors are the structures to extend to accommodate for sparse storage. Here below a draft of what a sparse accessor might look like:

A sparse accessor has 3 components:

• an initialization array (used to initialize the accessor). Note: the bufferView entry is optional, in its absence the sparse accessor is initialized with zeroes.
• an index array used to point to those values that deviate from the initialization value.
• a value array encoding the values of the entries corresponding to the indices in the index array.

"mySparseAccessor": {
//---Initialization array, initializes the accessor with a syntax similar to a standard accessor---//
  "bufferView":"bufferViewInitializationList",
  "byteOffset":,
  "byteStride":,
  "count":,
 
  //--sparse encoding of the values that changed with respect to the initialization array--//
  "sparseCount": ,//<=number of "displaced" entries stored in the sparse array

  "sparseValueBufferView": "bufferViewDisplaceValuesArray",//<=only displaced entries are stored
  "sparseValueByteOffset": ,
  "sparseValueByteStride": ,

  "sparseIndexBufferView": "bufferViewDisplacedIndicesArray",//<=buffer containing the indices of the displaced entries.
  "sparseIndexByteOffset": ,
  "sparseIndexByteStride": ,
 
  //---type and component type have the same semantic as in a standard accessor--//
  "componentType": ,
  "type": ""
  }

[lexaknyazev]

Please, confirm or correct me if I'm wrong.

Unpacking such accessor into regular one would be like (roughly):

1. Load init data (or zeros) into temporary buffer.
2. for (var i = 0; i < sparseCount; i++) myData[sparseIndex[i]] = sparseValue[i];

Then, we expect engine to use such array as an additional source of vertex attributes.

[emilian0]

Yes unpacking would work the way you described. Once unpacked the sparse accessor can be used as a regular one.

[pjcozzi]

@emilian0 thanks, this is a great start. May I suggest some tweaks:

"mySparseAccessor": {
//---Initialization array, initializes the accessor with a syntax similar to a standard accessor---//
  "bufferView":"bufferViewInitializationList",
  "byteOffset":,
  "byteStride":,
  "count":,
 
  //--sparse encoding of the values that changed with respect to the initialization array--//
  "sparseCount": ,//<=number of "displaced" entries stored in the sparse array
  "sparseValues": {
    "bufferView": /* ... */,
    "byteOffset": /* ... */,
    "byteStride": /* ... */
  },
  "sparseIndices": {
    "bufferView": /* ... */,
    "byteOffset": /* ... */,
    "byteStride": /* ... */
  },
 
  //---type and component type have the same semantic as in a standard accessor--//
  "componentType": ,
  "type": ""
  }

• sparseCount, sparseValues and sparseIndices are all required when any is defined.
  • Each of the three sub-properties are defined with the same requirements as an accessor defines its properties with the same names.
• I guess sparseCount could be zero just like bufferView.byteLength could be.

And some questions:

1. What is the use case for this? Is it for morphs when only a subset of the buffer matters and vertices just need to line up?

Note: the bufferView entry is optional, in its absence the sparse accessor is initialized with zeroes.

2. Is it worthwhile to limit that these sparse accessors can only be accessed from morph targets? It could make it easier for those that just want to implement geometry or geometry/material only in glTF, and not animation/skin/morphs. Or maybe this is easy enough for everyone to implement? If it is useful, there could even be a new top-level property sparseAccessors to separate these from the other accessors - could be overkill.

[lexaknyazev]

What is the use case for this? Is it for morphs when only a subset of the buffer matters and vertices just need to line up?

One could think of sparse accessors as of "diffs" between regular accessors. The main expected use case is morph targets, because each morph target usually affects only specific mesh parts - not all vertices.

@emilian0
Since sparse indices are stored in bufferView, we need to specify their data type (byte/short/int). Also, what's the point of having stride for indices?

[emilian0]

@pjcozzi thank you for your suggestion above, sounds good to me. Actually why not placing all the new entries "sparseCount", "sparseValues", "sparseIndices". Into a "sparseStorage" entry?

"mySparseAccessor": {
  ...
  "sparseStorage": {
    "sparseCount":,
    "sparseValues":{},
    "sparseIndices": {},
  }
}

note that sparse accessors will be listed, together with regular accessors, in the accessors top level dictionary.
note that a sparse accessor is identical to a regular accessor aside from the "sparseStorage" dictionary. An engine incapable of interpreting this field will just fallback to a standard accessor pointing to the initialization list buffer (this will disable morph targets...but at least the engine wouldn't crash).

[emilian0]

I agree with @lexaknyazev on that the only short term usage of sparse encoding in glTF is morph targets storage.
Note that sparse storage could also be used to store JOINT and WEIGHTS accessors used for skinning. This is relevant when most vertices only have one influencer.
Probably this isn't interesting at this point in time, but it might become more relevant in the future, if, for instance, we decide to extend the max number of skin influencers to say 8.

[emilian0]

@lexaknyazev, yes, you are right, we should specify sparseIndex data type.

@lexaknyazev ,re: stride: I was considering the scenario of storing the sparse data as index-value pairs. Say that you are working with 32 bit indexes and values. Then you could specify stride =8 and, for instance, sparseValues offset = 0 and sparseIndices offset =4.

Summary of offline conversation with @pjcozzi and @lexaknyazev :
@lexaknyazev understands the value of byteStride but pointed out that, when using 16bit indexes (common scenario), storing pair index-value can be very inefficient (breaks alignement requirements for floats).

decision ->keep byteStride as an optional field. We don't expect it to be used often, but it brings value.

[pjcozzi]

@emilian0 thanks for the update; this all sounds good to me, just one small naming suggestion:

"mySparseAccessor": {
  ...
  "sparseStorage": {
    "count":,
    "values":{},
    "indices": {},
  }
}

Since having sparse in each property is now redundant with sparseStorage.

Do you want to make the spec and schema updates?

Also do you or anyone on your team have any bandwidth to add support for this to COLLADA2GLTF? On our team, @lasalvavida is updating COLLADA2GLTF to output glTF 2.0 (see this branch), but we do not have the bandwidth to add this feature right now.

[emilian0]

Thanks @pjcozzi , here the consolidated draft:

"mySparseAccessor": {
//---Initialization array, initializes the accessor with a syntax similar to a standard accessor---//
  "bufferView":"bufferViewInitializationList",
  "byteOffset":,
  "byteStride":,
  "count":,
 
  //--sparse encoding of the values that changed with respect to the initialization array--//
  "sparse": {
    "count": ,//<=number of "displaced" entries stored in the sparse array
    "values": {
      "bufferView": /* ... */,
      "byteOffset": /* ... */,
      "byteStride": /* ... */
    }
    "indices": {
      "bufferView": /* ... */,
      "byteOffset": /* ... */,
      "byteStride": /* ... */,
      "componentType":/* allowed types "5121", "5123", "5125" */,
    }
  },
  //---type and component type have the same semantic as in a standard accessor--//
  "componentType": ,
  "type": ""
  }

I am happy to take care of spec/schema updates.
I don't have much bandwidth for the actual implementation. I am going to check with the rest of the team today and sync up with you offline. It also depends on the scope of the project (Is this just about extending the Accessor class + add a unit test? or is it about integrating it with the rest of the import mechanics?)

[pjcozzi]

@emilian0 looks good, but did you address this question from @lexaknyazev:

Since sparse indices are stored in bufferView, we need to specify their data type (byte/short/int). Also, what's the point of having stride for indices?

---

Is this just about extending the Accessor class + add a unit test? or is it about integrating it with the rest of the import mechanics?

If you added support to COLLADA2GLTF for converting COLLADA morph targets to glTF, it would be a home run. Each engine would then do their own implementation.

@lasalvavida is working on the glTF 2.0 updates to COLLADA2GLTF and could advise on where to make the changes since he has done some refactoring with the 2.0 updates.

[emilian0]

@pjcozzi thanks for the comment, I have added a "componentType" to the "sparse/indices" dictionary.
We could probably call it differently, perhaps "type" would just be enough. What do you think?
(the other part of the comment "the point of strides for indices" was discussed above)

[pjcozzi]

Naming it type is OK for me. Here's something related: https://github.com/KhronosGroup/glTF/blob/master/specification/1.0/README.md#primitiveindices

[emilian0]

@pjcozzi , I took a look at the link you shared. Are you suggesting to have the sparse.indices (and sparse.values) fields point to an accessor ID as opposed to describing directly how to extract typed data from their bufferView?
Although I like the 'elegance' of having accessors refer to other accessors I suggest to keep the definition of accessor.sparse self contained as described above.
Rationale: avoid one additional indirection, avoid entry-points for potential inconsistencies (what if the accessor pointed by sparse.indices is of type VEC3 or if the accessor pointed by index.values is of different type than the main accessor attribute type? these would be malformed glTF that the parser will need to handle)

[pjcozzi]

Are you suggesting to have the sparse.indices (and sparse.values) fields point to an accessor ID as opposed to describing directly how to extract typed data from their bufferView?

No, how you have it is OK. I was just trying to point out that when primitive.indices points to an accessor, it limits the allowed types to the same same types the new indices.indices.type would allow.

[emilian0]

Opened a work-in-progress pull request on this issue (#833)
(destination of the pull request is the 2.0 branch)

[emilian0]

@pjcozzi @lexaknyazev. Two quick questions before opening the pull request above for review/merge:

• I changed my mind (!) and decided to call the indices type field indices.componentType. The reason for that is for consistency with the main accessor componentType field. What do you think?
• I believe UNSIGNED_INT should be listed as one of the indices types. Is this ok? ( @pjcozzi the link you shared above only mentions 5121, and 5123).
  Thanks

[lexaknyazev]

call the indices type field indices.componentType

Fine with me.

I believe UNSIGNED_INT should be listed as one of the indices types. Is this ok?

OK, as long as mesh itself uses 32-bit indices. Also see #829.

[pjcozzi]

+1 to @lexaknyazev's comments.

[pjcozzi]

Updated in #826