Sparse Array KHR extension

From COLLADA Public Wiki
Revision as of 17:27, 19 December 2011 by Webmaster (talk | contribs) (Undo revision 7149 by RowenaGlenn (talk))
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Extension information
This article is part of the COLLADA extensions directory
Adding to the extensions directory


<sparse_array> Element

Profile: KHR
Specification Version: 1.4 and 1.5
Category: Data Flow

Introduction

Enables compact representation of sparse array data. Extension was designed for use in conjunction with the <morph> element, although it can be potentially beneficial in any scenario involving arrays. A sparse array is useful to express incremental change.

Concepts

Morph targets are shape deformations created by applying a set of deltas of vertex positions in a weighted fashion. COLLADA includes the ability to specify morph targets as arrays of delta values. If a given morph target affects vast parts of a piece of geometry, this is an efficient representation. If a piece of geometry is of high resolution, and the morph target only affects a small part of it (such as the shape of the nose of a human figure), the representation is very inefficient. This extension aims to enable efficient representation of sparse array data.

Attributes
Name Type Description Required?
id xs:ID A unique symbol within the instance document. No
name xs:token The name attribute is the text string name of this element. No
count uint Number of values in the array. Yes
initializer xs:anyURI References the initializer array. Yes
index xs:anyURI References the index array. Yes
value xs:anyURI References the value array. Yes
Related Elements
Affected Parent element(s) source
Extra and/or Technique <extra><technique profile="KHR">
Child elements None
Other float_array
int_array
bool_array
Name_array
IDREF_array
accessor
Child Elements
Name Description Default Occurrences
N/A N/A N/A N/A

Implementation note: On an accessor level, array and sparse_array are accessed polymorphically. sparse_array is an array, any attribute of sparse array could be array or sparse array (recursive, will eventually encounter non-sparse array).

Version

1.0

Details

Problem

As stated in Concepts above, it is currently difficult to express sparse data efficiently.

Analysis

For example, a morph controller needs to specify the following data:

  1. Base geometry
  2. Some "morph target" data
  3. Weights to blend (1) and (2)

We believe (1) and (2) usually contain large sets of data. However, only a small part of the base geometry might be morphed (e.g. the nose of a human figure).

Solution

Add a new <sparse_array> element that references three arrays. The first array is the initializer and determines the default values the sparse array is filled with. The second array is the index array, and declares which indices point to values deviating from the state after initialization. The third and last array contains values associated with the indices in the second array.

The <sparse_array> is added within the scope of the
 element. Coincidentally, the <source> element has been designed with an optional <technique_common> element and this allows the source to contain the minimal amount of data. Please note that this is an exception to the normal COLLADA extensibility design that requires <technique_common>. See [https://collada.org/mediawiki/index.php/Extension COLLADA Extension Mechanisms] for more information.

====Schema====    
* Add a new <sparse_array> element within the scope of <source>
  <nowiki>
  <?xml version="1.0" encoding="utf-8"?>
  <xs:schema xmlns="http://www.collada.org/2011/COLLADA/KHR/SparseArray" xmlns:xs="http://www.w3.org/2001/XMLSchema"
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" elementFormDefault="qualified" version="1.0.0"</nowiki>
    xml:lang="EN" xsi:schemaLocation="http://www.w3.org/2001/XMLSchema http://www.w3.org/2001/XMLSchema.xsd">
    <xs:element name="sparse_array">
      <xs:annotation>
        <xs:documentation>
          The sparse_array element declares the storage for a sparse array
          of values. Values can be of any type allowed for the array
          element. The element contains three arrays that represent a
          sparse set of data in a compact fashion.
        </xs:documentation>
      </xs:annotation>
      <xs:complexType>
        <xs:simpleContent>
          <xs:attribute name="id" type="xs:ID">
            <xs:annotation>
              <xs:documentation>
                The id attribute is a text string containing the unique identifier of this element. This value 
                must be unique within the instance document. Optional attribute.
              </xs:documentation>
            </xs:annotation>
          </xs:attribute>
          <xs:attribute name="name" type="xs:token">
            <xs:annotation>
              <xs:documentation>
                The name attribute is the text string name of this element. Optional attribute.
              </xs:documentation>
            </xs:annotation>
          </xs:attribute>
          <xs:attribute name="count" type="xs:unsignedLong" use="required">
            <xs:annotation>
              <xs:documentation>
                The count attribute indicates the number of values in the array. Required attribute.
              </xs:documentation>
            </xs:annotation>
          </xs:attribute>
          <xs:attribute name="initializer" type="xs:anyURI" use="required">
            <xs:annotation>
              <xs:documentation>
                The initializer attribute indicates the location of the initializer array.
                It determines with which values the sparse_array gets initialized. Required attribute.
              </xs:documentation>
            </xs:annotation>
          </xs:attribute>
          <xs:attribute name="index" type="xs:anyURI" use="required">
            <xs:annotation>
              <xs:documentation>
                The index attribute indicates the location of the index array.
                It declares a list of valid indices. Required attribute.
              </xs:documentation>
            </xs:annotation>
          </xs:attribute>
          <xs:attribute name="value" type="xs:anyURI" use="required">
            <xs:annotation>
              <xs:documentation>
                The value attribute indicates the location of the value array.
                It determines what value is associated with a given index. Required attribute.
              </xs:documentation>
            </xs:annotation>
          </xs:attribute>
        </xs:simpleContent>
      </xs:complexType>
    </xs:element>
  </xs:schema>

===Example===
An example of a morph target implemented with a sparse array: <!-- replaced [[COLLADA/Sparse Array/Samples]] with agreed upon sample instead of link -->

  &lt;!-- A source for vertex position using float_array, the initializer for the sparse array --&gt;
  <source id="initializer" name="Initializer">
    <float_array id="initializer_array" count="6">
      1.0 0.0 0.0 2.0 0.0 0.0
    </float_array>
    <technique_common>...</technique_common>
 <!-- A source for index of sparse array using int_array -->
    <int_array id="index_array" count="2">
      0 3
    </int_array>
    <technique_common>...</technique_common>
 <!-- A source for value of sparse array using float_array -->
    <float_array id="value_array" count="2">
      11.0 22.0
    </float_array>
    <technique_common>...</technique_common>
 <!-- A source for the sparse array that references the above 3 sources -->
    <technique profile="KHR" xmlns:sa="http://www.collada.org/2011/COLLADA/KHR/SparseArray"
    xsi:schemaLocation="http://www.collada.org/2011/COLLADA/KHR/SparseArray http://www.collada.org/2011/COLLADA/KHR/SparseArray.xsd">
      <sa:sparse_array id="sparse_array" count="12" initializer="#initializer_array" index="#index_array" value="#value_array"/>
      <accessor source="#sparse_array" count="4" stride="3">
        <param name="X" type="float"/>
        <param name="Y" type="float"/>
        <param name="Z" type="float"/>
      </accessor>
    </technique>

A note regarding the 'sa' namespace: The namespace qualifier itself is unimportant, since it's just a local mapping. What is important is that a namespace is used, otherwise validation wouldn't be possible.

After the above sparse array expands, it has the same meaning as the following source. As a reminder, when the count of initializer_array is smaller than the count of sparse_array, we initialize the sparse_array by repeating the initializer_array. After the sparse_array is initialized, we can put data from value_array onto the initialized sparse_array corresponding to the indices from the index_array.

    <float_array id="position_array" count="12">
      11.0 0.0 0.0 22.0 0.0 0.0 1.0 0.0 0.0 2.0 0.0 0.0
    </float_array>
    <technique_common>
      <accessor source="#position_array" count="4" stride="3">
        <param name="X" type="float"/>
        <param name="Y" type="float"/>
        <param name="Z" type="float"/>
      </accessor>
    </technique_common>

Status

Released 1.0.

IP Status

  • Copyright 2010, 2011 The Khronos Group.

Dependencies

This extension applies to COLLADA 1.4 and 1.5. This extension does not depend on any other extensions.

Issues

Some concerns:

  • Sparse array is not a strongly typed array at its own level, like e.g <float_array> etc.. Referencing the base arrays using URI means they are opaque resources and also externalized. This is required for the use-cases that were considered versus trying to craft a strongly typed array element.
  • Exporting data as sparse arrays only might lead to interoperability issues. Contrary to other extensions such as Morph Weights, which can just be ignored by applications that choose not to implement a related feature, sparse arrays are not optional. In order to ensure a robust tool chain, an application that offers to export data in sparse arrays should consider offering an option that also includes the data in non-sparse arrays. This could be done by exporting the sparse array in <technique profile="KHR"> along with a <technique_common> containing a regular array, or an external array source, that contains the data in non-sparse representation (the external array source being more in line with the goal of this extension, which is to avoid exporting large files containing redundant data). This would require implementing at least three export options:
    • Regular arrays always
    • Sparse arrays when applicable
    • Both regular and sparse arrays for maximized interoperability

Parsing Errors

Version 1.4 Error Handling

None known.

Version 1.5 Error Handling

None known.