Losslessly indexing with meshopt

[kzhsw]

Currently in glTF-Transform the weld function can be used to losslessly create index for primitives, or lossy merge similar vertices with a tolerance.
In gltfpack, it defaults to reindexMesh, which losslessly merges identical vertex and creates index.
See Compiling meshopt_generateVertexRemapMulti to wasm and use in js for a port of this in wasm and js.

[kzhsw]

This impl with the wasm might be able to reindex on unindexed mesh without weld first.

code

import {Accessor, PropertyType} from "@gltf-transform/core";
import {createTransform, isTransformPending, prune} from "@gltf-transform/functions";
import {init} from "./reindex_wasm";
import {reindexWrapper} from "./reindex-wrapper";

const NAME = 'reindex';

/**
 * Returns a list of all unique vertex attributes on the given primitive and
 * its morph targets.
 * @param {import('@gltf-transform/core').Primitive} prim
 */
function deepListAttributes(prim) {
    /**
     * @type {import('@gltf-transform/core').Accessor[]}
     */
    const accessors = [];

    for (const attribute of prim.listAttributes()) {
        accessors.push(attribute);
    }
    for (const target of prim.listTargets()) {
        for (const attribute of target.listAttributes()) {
            accessors.push(attribute);
        }
    }

    return Array.from(new Set(accessors));
}

/**
 * Port of gltfpack's reindexMesh to gltf-transform
 * @return {import('@gltf-transform/core').Transform}
 */
export function reindex() {
    const instance = init();

    return createTransform(NAME, (doc, context) => {
        const logger = doc.getLogger();

        const meshes = doc.getRoot().listMeshes();
        for (let i = 0, length = meshes.length; i < length; i++) {
            const primitives = meshes[i].listPrimitives();
            for (let j = 0, pLength = primitives.length; j < pLength; j++) {
                const primitive = primitives[j];
                // points, no need to index
                if (primitive.getMode() === 0) {
                    continue;
                }
                const attrAccessors = deepListAttributes(primitive);
                if (!attrAccessors.length) {
                    continue;
                }
                const attributes = [];
                let skip = false;
                let totalVertices = 0;
                for (let i = 0, len = attrAccessors.length; i < len; i++) {
                    const accessor = attrAccessors[i];
                    if (totalVertices === 0) {
                        totalVertices = accessor.getCount();
                    } else if (totalVertices !== accessor.getCount()) {
                        skip = true;
                        logger.debug(`${NAME}: Skipping attr ${
                            accessor.getName()
                        }, expected count ${totalVertices}, actual ${accessor.getCount()}.`);
                        break;
                    }
                    attributes[i] = {
                        buffer: accessor.getArray(),
                        size: accessor.getComponentSize() * accessor.getElementSize(),
                    };
                }
                if (skip) {
                    logger.warn(`${NAME}: Skipping index of ${
                        primitive.getName()
                    } with variable-count attr.`);
                    continue;
                }
                const srcIndices = primitive.getIndices();

                // this would be cloned in reindexWrapper, so no need to clone it here
                // nullable
                let indicesArray =
                    srcIndices ? srcIndices.getArray() : null;
                // skip clone if there is indices
                if (srcIndices) {
                    srcIndices.set('array', null);
                }
                const dstIndices = srcIndices ?
                    srcIndices.clone() :
                    doc.createAccessor()
                        .setBuffer(attrAccessors[0].getBuffer())
                        .setType(Accessor.Type.SCALAR);
                // set it back
                if (srcIndices) {
                    srcIndices.set('array', indicesArray);
                }

                // do the real reindex
                indicesArray = reindexWrapper(
                    instance, indicesArray, totalVertices, attributes, true);

                dstIndices.setArray(indicesArray);
                primitive.setIndices(dstIndices);

                // Update affected primitives.
                for (let i = 0, len = attrAccessors.length; i < len; i++) {
                    const srcAttribute = attrAccessors[i];
                    const srcAttrArray = srcAttribute.getArray();
                    // skip array clone to save memory and gc pressure
                    srcAttribute.set('array', null);
                    const dstAttribute = srcAttribute.clone();
                    // set it back
                    srcAttribute.set('array', srcAttrArray);
                    // change array
                    dstAttribute.setArray(attributes[i].buffer);

                    primitive.swap(srcAttribute, dstAttribute);
                    for (const target of primitive.listTargets()) {
                        target.swap(srcAttribute, dstAttribute);
                    }

                }
            }
        }

        logger.debug(`${NAME}: Complete.`);
        if (!isTransformPending(context, NAME, 'prune')) {
            // Clean up any attributes left unused by earlier cloning.
            return doc.transform(prune({ propertyTypes: [PropertyType.ACCESSOR] }));
        }
    });
}

[donmccurdy]

Awesome work @kzhsw! This looks really useful, and I'll go out on a limb and guess it's much faster than the current (tolerance > 0) implementation of weld here. That's something I'd like to revisit, possibly with a WASM implementation similar to resample() at some point. I believe it may be important to preserve the option of per-attribute tolerance thresholds, which meshopt doesn't offer AFAIK.

I don't expect that I'll bring in meshopt's reindex_wasm if it requires manual rebuilds. If that becomes part of the meshopt npm package I may reconsider. I would encourage any users needing a fast, lossless weld to consider this implementation themselves, though!