Compiling meshopt_generateVertexRemapMulti to wasm and use in js

[kzhsw]

In readme there are documents about indexing the mesh with meshopt_generateVertexRemap, after digging a bit deeper into gltfpack, in function reindexMesh, function meshopt_generateVertexRemapMulti is called for every mesh being processed.

Using wasm-compiled gltfpack is seeming the only way to use meshopt_generateVertexRemapMulti in web platform, but since this project is open source, it is possible to manually compile meshopt_generateVertexRemapMulti to wasm and use it in js.

The wasm can be compiled with Makefile, which path to the wasi-sdk should be passed to, so simpily add this lines to Makefile can compile a wasm binary:

Makefile code

WASM_INDEXING_SOURCES=src/indexgenerator.cpp tools/wasmstubs.cpp
WASM_INDEXING_EXPORTS=meshopt_generateVertexRemapMulti \
meshopt_remapIndexBuffer meshopt_remapVertexBuffer sbrk

build/indexing_base.wasm: $(WASM_INDEXING_SOURCES)
	@mkdir -p build
	$(WASMCC) $^ $(WASM_FLAGS) $(patsubst %,$(WASM_EXPORT_PREFIX)=%,$(WASM_INDEXING_EXPORTS)) -o $@

build/indexing_simd.wasm: $(WASM_INDEXING_SOURCES)
	@mkdir -p build
	$(WASMCC) $^ $(WASM_FLAGS) $(patsubst %,$(WASM_EXPORT_PREFIX)=%,$(WASM_INDEXING_EXPORTS)) -o $@ \
	-mbulk-memory -msimd128

make WASI_SDK=/path/to/your/wasi-sjk build/indexing_base.wasm build/indexing_simd.wasm

Should notice that in other targets the function __wasm_call_ctors is also exported to initialize it, but after compiling and analyzing with the wasm2wat tools, the function in empty, so it is not exported here.

Binaries could be futher optimized using wasm-opt from binaryen.

The meshoptimizer library uses wasmpack.py to encode binary to text, making it possible to be embedded into js code.

Also note that the simd version does not actrually uses simd instuctions, only the bulk-memory inst is used.

# generate the decoding table, and replace it into the wasmpack.py after that
cat  build/indexing_base.wasm build/indexing_simd.wasm | python3 tools/wasmpack.py generate
# this encodes wasm to text
cat build/indexing_base.wasm | python3 tools/wasmpack.py
cat build/indexing_simd.wasm | python3 tools/wasmpack.py

Here is an example of compiled wasm embedding in js:

Compiled wasm in js

var wasm_base = 'bGCDebbbe8WyOekekOekbOfkkkekOtkkkkkkekOskkkkkbOhkkkkbOfkkkbfIEfhsbtddbehseHeffsfebetnekec:q;iegyvstDqDLA95dbaDqC9OLHr7Xq9UqAGrq9wqArqY9sqDGH9nQxr9Pbb8zDqC9OLHr7AqDGH9wqArqY9cQWWqAbe3DqC9OLHr7AqDGH69U1qY9cQWWqAbdhC0AvbfEnebcegdnyI;YwE:tseZk8Jbc;Wbvmw4bawcnicbc;KbusUabcBeafcdrusjZafcdTafijEcejbflabmfcerjbafaE6pbgawckafcdrmEafcBBBBfK8Bc:enodbJbbmbzdnabcBeaEusjEadhlaejMfla8ujbaehlaModbjbgaZabcdrim8xodbckFhldldkabjpcbjncbjgcbjIcbjudlasSpbafcevjJflahaIcwximbodhmtch9phlabodbabodnapxijyflayodbc:v;t;h;Esxmbc3TabCc:v;t;h;Esxanc:v;t;h;EsxCjnaychijyatchvmtcfKpbggaIceimIasVpbganaJPjgasSpbahcwijbdlflaEagcdrimIodbm8vckFpeahodbmtahodnmna8vxiatanapxiahodhutShlcejnabjyflanmtasVhlatceijnaycnij2ayodbj8waychij3aycwijya8wa2odbm2a8vxia8wapa2xia3odbutSpeggasat9npdgauceimuagiaJPjgauaJ9npbgcbjIgaIwegaEagcdrigmbodbmtckFhlabapzdba8ombceij8owegaZatcdriodbjbga8xabzdbgaMchijMa8uceim8uadVpbggcbjfflafc98Vhlawcniafiodbc:anodbJebafchvjfweggawc;Wbi4ba8og:Yeefk8Jbc;Wbvms4bascnicbc;KbusUabaeFhlasadafxmtc:enodbJbbmezdnaeabatuhcejtgadhlflahodbmyckVhlabafayxiaeafuhgahchijhaeafijeadcevmdpbggatcdrjhflahhlahchvmhascniiodbc:anodbJebweggasc;Wbi4bg9JbdladSpbaehlflabafaeodbcdriodbzdbaechijeabchijbadcevmdpbwdgbgflabafodbzdbabchijbafchijfadcevmdpbgggFedkcNncNnodbmeabcfic98Pimbzdbdkab5bcurmdKhlckabadvcBBficuTlbckFpeUgaegg;febdlabaeAcfPpbadcu9phlflabaeodbzdbabchiaechiodbzdbabcniaecniodbzdbabcwiaecwiodbzdbaecuijeabcuijbadcuvmdcMKpbggadch6pbflabaeodbzdbaechijeabchijbadchvmdcfKpbggadhlflabaeRbb86bbabceijbaeceijeadcevmdpbggg:4eedkdlabcfPhlabjfwegaecBePc:b:c:enxjhdladcu6hlabjfwegabjfflafahzdbafcwiahzdbafcniahzdbafchiahzdbafcuijfadcuvmdcMKpbggadch6pbflafahzdbafchijfadchvmdcfKpbggadhlflafae86bbafceijfadcevmdpbggabg9defkdladSpbflabRbbmfaeRbbmhFhlaeceijeabceijbadcevmdpewdggafahvjsgasgFedkcNncNnodbmeabcyicYPimbzdbdkab5bcurmdKhlckabadvcBBficuTlbckFpeUgaeggHedk5bjedkcNnodbmdaecurmeKhlckadaevcBBficuTlbckFpeUgadgjecNncNnodbabaevcfic98Pimezdb5bcurmbae6hlaeabvcBBficuTlbUgggJebc:angIebbbdbbbu1b8MEHAL1Q9JqACewHAL9JqCCq1R095es9JxG9UXt8Xz8U8W8U8Wb8SMrGAXqr7WqGrQAqCd8RMDQrG0xqRXxL0GxC8RnC9PX9URqYr';
var wasm_simd = 'bGCDebbbe8QtOekekOekbOtkkkkkkekOskkkkkbOhkkkkbOfkkkekfnydfhbsbehseHeffsfebetnekec:q;iegyvstDqDLA95dbaDqC9OLHr7Xq9UqAGrq9wqArqY9sqDGH9nQxr9Pbb8zDqC9OLHr7AqDGH9wqArqY9cQWWqAbe3DqC9OLHr7AqDGH69U1qY9cQWWqAbdhC0AvbfEnebcegdtsweeI;ZEy:rseZk8Jbc;WbvmI4baIcnicbc;Kb;8gbabcBeafcdr;8gbafcdTafijtcejfflafmgcerjfatagKpbgaIckagcdrmfagcBBBBfK8Bc:enodbJbbmpzdnapcBeaf;8gbadhlaejMfla8ujfaehlaModbjfgabafcdrim8xodbckFhldldkafjwcbjtcbjncbjycbjudlasSpbagcevjJflahaycwximfodhmEch9phlafodbafodnawxijfflafodbc:v;t;h;Esxm2c3Ta2Cc:v;t;h;Esxatc:v;t;h;EsxCjtafchijfaEchvmEcfKpbggayceimyasVpbgataJPjnasSpbahcwij2dlflapancdrimyodbm8vckFpeahodbmtahodnmfa8vxiatafawxiahodhuhShlcejta2jfflatmEasVhlaEceijtafcnijZafodbj8wafchij3afcwijfa8waZodbmZa8vxia8wawaZxia3odbuhSpeggasaE9npdgauceimuaniaJPjnauaJ9npbgcbjygaywegapancdrigmfodbmtckFhlafawzdba8omfceij8owegabatcdriodbjfga8xafzdbgaMchijMa8uceim8uadVpbggcbjfflafc98VhlaIcniafiodbc:anodbJebafchvjfweggaIc;Wbi4ba8og:2eefk8Jbc;Wbvms4bascnicbc;Kb;8gbabaeFhlasadafxmtc:enodbJbbmezdnaeabat;8IbbcejtgadhlflahodbmyckVhlabafayxiaeaf;8Ibbgahchijhaeafijeadcevmdpbggatcdrjhflahhlahchvmhascniiodbc:anodbJebweggasc;Wbi4bg9JbdladSpbaehlflabafaeodbcdriodbzdbaechijeabchijbadcevmdpbwdgbgflabafodbzdbabchijbafchijfadcevmdpbgggFedkcNncNnodbmeabcfic98Pimbzdbdkab5bcurmdKhlckabadvcBBficuTlbckFpeUgaegg9defkdladSpbflabRbbmfaeRbbmhFhlaeceijeabceijbadcevmdpewdggafahvjsgasgFedkcNncNnodbmeabcyicYPimbzdbdkab5bcurmdKhlckabadvcBBficuTlbckFpeUgaeggHedk5bjedkcNnodbmdaecurmeKhlckadaevcBBficuTlbckFpeUgadgjecNncNnodbabaevcfic98Pimezdb5bcurmbae6hlaeabvcBBficuTlbUgggJebc:angIebbbdbbbu1b8MEHAL1Q9JqACewHAL9JqCCq1R095es9JxG9UXt8Xz8U8W8U8Wb9cMrGAXqr7WqGrQAqCh8RMDQrG0xqRXxL0GxC8RyC9PD18X8Y848Rg0QxvRDqDLA958RnC9PX9URqYr';

var wasmpack = new Uint8Array([32, 0, 65, 2, 1, 3, 11, 4, 106, 33, 127, 64, 34, 8, 40, 13, 101, 116, 5, 6, 16, 107, 12, 108, 7, 54, 114, 255, 115, 109, 9, 70, 97, 112, 10, 17, 75, 111, 15, 136, 96, 113, 117, 45, 69, 118, 26, 71, 102, 103, 120, 19, 98, 100, 18, 24, 36, 63, 73, 95]);

var wasm = WebAssembly.validate(new Uint8Array([
    0, 97, 115, 109, 1, 0, 0, 0, 1, 4, 1, 96, 0, 0, 3, 3,
    2, 0, 0, 5, 3, 1, 0, 1, 12, 1, 0, 10, 22, 2, 12, 0,
    65, 0, 65, 0, 65, 0, 252, 10, 0, 0, 11, 7, 0, 65, 0, 253,
    15, 26, 11
])) ? wasm_simd : wasm_base;

// do not leak memory
wasm_base = '';
wasm_simd = '';
function unpack(data) {
    var result = new Uint8Array(data.length);
    for (var i = 0; i < data.length; ++i) {
        var ch = data.charCodeAt(i);
        result[i] = ch > 96 ? ch - 97 : ch > 64 ? ch - 39 : ch + 4;
    }
    var write = 0;
    for (var i = 0; i < data.length; ++i) {
        result[write++] = (result[i] < 60) ? wasmpack[result[i]] : (result[i] - 60) * 64 + result[++i];
    }
    return result.buffer.slice(0, write);
}
var mod = new WebAssembly.Module(unpack(wasm));

// do not leak memory
wasmpack = null;
wasm = '';

export function init(imp) {
    return new WebAssembly.Instance(mod, imp);
}

Should note that new WebAssembly.Module and new WebAssembly.Instance is used as the wasm codes are less that 4096 bytes limited by google.

And type defs of it:

type def

export declare function init(imp?: WebAssembly.Imports): ReindexInstance;

export declare interface ReindexInstance extends WebAssembly.Instance {
    readonly exports: ReindexExports;
}

export declare interface ReindexExports extends WebAssembly.Exports {
    readonly memory: WebAssembly.Memory;

    // void* sbrk(intptr_t increment)
    sbrk(increment: number): number;

    // size_t
    meshopt_generateVertexRemapMulti(
        // unsigned int*
        destination: number,
        // const unsigned int*
        indices: number,
        // size_t
        index_count: number,
        // size_t
        vertex_count: number,
        // const struct meshopt_Stream*
        streams: number,
        // size_t
        stream_count: number,
    ): number;

    meshopt_remapIndexBuffer(
        // unsigned int*
        destination: number,
        // const unsigned int*
        indices: number,
        // size_t
        index_count: number,
        // const unsigned int*
        remap: number
    ): void;

    meshopt_remapVertexBuffer(
        // void*
        destination: number,
        // const void*
        vertices: number,
        // size_t
        vertex_count: number,
        // size_t
        vertex_size: number,
        // const unsigned int*
        remap: number
    ): void;
}

Pointers are exposed as `number` to js, which is the offset of data in the wasm `memory`, so calling the functions would need to manually copy data into wasm memory, that's why the so-called js-glue code is needed for simplier usage.

The exposed function sbrk is used for linear memory allocation and deallocation, but since wasm can not return allocated memory to host, see more info at #522.

So here is the js wrapper:

js wrapper

// the exactly same function ported from gltfpack
function hashBuckets(count)
{
    let buckets = 1;
    while (buckets < count + count / 4)
        buckets *= 2;

    return buckets;
}

export function reindexWrapper(
    instance,
    indices,
    vertexCount,
    attributes,
    clone
) {
    // 12 bytes for each meshopt_Stream, aligned
    // 4 bytes ptr to data, 4 bytes size, 4 bytes stride
    let memorySize = attributes.length * 12;
    // if no indices, allocate it to vertexCount
    const totalIndices = indices ? indices.length : vertexCount;
    // indices are converted to uint32, so not byteLength here
    memorySize += totalIndices * 4;
    // allocate memory for remap
    memorySize += vertexCount * 4;
    // extra memory size that could be allocated at runtime
    // causing extra reallocates
    let extraMemorySize = hashBuckets(totalIndices) * 4;
    for (let i = 0, length = attributes.length; i < length; i++) {
        const attr = attributes[i];
        if (attr.buffer instanceof ArrayBuffer) {
            attr.buffer = new Uint8Array(attr.buffer);
        } else if (!(attr.buffer instanceof Uint8Array)) {
            attr.Constructor = attr.buffer.constructor;
            attr.buffer = new Uint8Array(
                attr.buffer.buffer, attr.buffer.byteOffset, attr.buffer.byteLength);
        }
        if (!attr.stride) {
            attr.stride = attr.size;
        }
        const attrSize = attr.stride * vertexCount;
        if (attrSize < attr.buffer.byteLength) {
            attr.buffer = attr.buffer.subarray(0, attrSize);
        }
        // 4 bytes align
        attr.dataSize = (attrSize + 3) & ~3;
        attr.dataOffset = memorySize;
        memorySize += attr.dataSize;
        // get the max runtime size
        extraMemorySize = Math.max(attr.dataSize, extraMemorySize);
    }
    // 4-bytes align
    extraMemorySize = (extraMemorySize + 3) & ~3;
    // allocate memory, this should be always aligned
    const ptr = instance.exports.sbrk(memorySize + extraMemorySize);
    if (extraMemorySize) {
        // allocate and deallocate to reserve memory for wasm
        instance.exports.sbrk(-extraMemorySize);
    }
    const buf = instance.exports.memory.buffer;
    const metadata = new Uint32Array(buf, ptr, attributes.length * 3);
    for (let i = 0, length = attributes.length; i < length; i++) {
        const attr = attributes[i];
        // dataOffset is used later
        attr.dataOffset += ptr;
        metadata[i * 3] = attr.dataOffset;
        metadata[(i * 3) + 1] = attr.size;
        metadata[(i * 3) + 2] = attr.stride;
    }
    const indicesOffset = ptr + metadata.byteLength;
    // never use indices.byteLength
    const remapOffset = indicesOffset + totalIndices * 4;

    // copy indices to memory
    if (indices) {
        new Uint32Array(buf, indicesOffset, totalIndices).set(indices);
    }
    for (let i = 0, length = attributes.length; i < length; i++) {
        const attr = attributes[i];
        // copy indices to memory
        new Uint8Array(buf, attr.dataOffset, attr.dataSize).set(attr.buffer);
    }

    const uniqueVertices = instance.exports.meshopt_generateVertexRemapMulti(
        remapOffset,
        indices ? indicesOffset : 0,
        totalIndices,
        vertexCount,
        ptr,
        attributes.length
    );
    // do the remap for indices
    instance.exports.meshopt_remapIndexBuffer(
        indicesOffset, indices ? indicesOffset : 0,
        totalIndices, remapOffset);
    for (let i = 0, length = attributes.length; i < length; i++) {
        const attr = attributes[i];
        // do the remap for attributes
        instance.exports.meshopt_remapVertexBuffer(
            attr.dataOffset, attr.dataOffset, vertexCount, attr.size, remapOffset);
    }

    // copy back
    const writeIndices = !indices || Array.isArray(indices) || clone ?
        totalIndices <= 65534 ? new Uint16Array(totalIndices) : new Uint32Array(totalIndices) :
        totalIndices <= 65534 && indices instanceof Uint32Array ?
            new Uint16Array(totalIndices) : indices;
    // memory buffer might change
    const bufAfter = instance.exports.memory.buffer;
    // set: copy and convert
    writeIndices.set(new Uint32Array(bufAfter, indicesOffset, totalIndices));

    for (let i = 0, length = attributes.length; i < length; i++) {
        const attr = attributes[i];
        attr.dataSize = attr.size * uniqueVertices;
        if (clone) {
            attr.buffer = new Uint8Array(attr.dataSize);
        }
        attr.buffer.set(new Uint8Array(bufAfter, attr.dataOffset, attr.dataSize));
        if (attr.Constructor) {
            attr.buffer = new attr.Constructor(
                attr.buffer.buffer,
                attr.buffer.byteOffset,
                attr.dataSize / attr.Constructor.BYTES_PER_ELEMENT
            );
        } else if (attr.buffer.byteLength > attr.dataSize) {
            attr.buffer = attr.buffer.subarray(0, attr.dataSize);
        }

    }
    // release memory
    instance.exports.sbrk(-memorySize);
    return writeIndices;
}

Should notice that instance is passed in as an argument, so callers can control the life cycle of the wasm instance, so allocated memory can be released by garbage-collecting the instance.

And defining the types:

export declare function reindexWrapper(
    instance: ReindexInstance,
    indices: Array<number> | Uint16Array | Uint32Array | null,
    vertexCount: number,
    attributes: ReindexAttr[],
    clone: boolean
): any;

export declare interface ReindexAttr {
    // in/out
    buffer: ArrayBufferView | ArrayBuffer;
    // in, bytes
    size: number;
    // in, bytes
    stride: number;
    // out/temp
    dataSize?: number;
    // out/temp
    dataOffset?: number;
    // out/temp
    Constructor?: new(buf: ArrayBuffer, byteOffset: number, length: number) => ArrayBufferView;
}

Indices and vertex attributes are passed in as arguments, and since js object is extendable, the reindexed attributes are stored back into the attributes argument, the reindexed indices are returned back as return value.

Should note that unindexed value is not covered in this example, but supported if directly call the wasm exports.
Edit: this case should be supported now.

That making it possible to use it in glTF-Transform as an example, which is simliar to reorder.ts:

Example 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] }));
        }
    });
}

Also note here that in reindexWrapper if clone is true, cloned memory are allocated at exact the used size after indexing, but if clone it with gltf-transform accessor, it it allocated at original size, and copied again to shrink used memory.

Note that in gltf-transform, weld.ts existed to do a similar job os this, but the "lossless" mode when tolerance is 0 simply creates index instead of merging it.

Due to the limitations of createLayoutPlan of glTF-Transform, unindexed primitives are ignored in the output, so for unindexed models, users can first call weld with {tolerance: 0} to create missing index, and use this reindex to losslessly merge redundant vertices.
Edit: updated and unindexed primitives are supported now, see also donmccurdy/glTF-Transform#927 (comment)