simplifyAttr: attribute-aware impl of simplify

[kzhsw]

Recently meshoptimizer merged attribute-aware simplification here: zeux/meshoptimizer@4a0c891, and code changes are needed to corrently pass attributes to meshoptimizer.

Note the simplifier instance passed in should be taken from master branch, or built with latest code, not from npm until next release of meshoptimizer.

Updated 20230621, featuring optional simplify of morph targets, this should fix #822
Updated 20240711 for meshopt 0.21.0
Updated 20240712 merged some code form git head

import {
    Accessor,
    Primitive,
    PropertyType
} from '@gltf-transform/core';

import {
    createTransform,
    dedup,
    isTransformPending,
    getPrimitiveVertexCount,
    VertexCountMethod,
    convertPrimitiveToTriangles,
    compactPrimitive,
} from '@gltf-transform/functions';

import {
    formatDeltaOp,
} from './simplify-utils';

const { POINTS, TRIANGLES, TRIANGLE_STRIP, TRIANGLE_FAN } = Primitive.Mode;

const NAME = 'simplifyAttr';

/** Options for the {@link simplifyAttr} function. */

export const SIMPLIFY_DEFAULTS = {
    ratio: 0.0,
    error: 0.0001,
    lockBorder: false,
    sparse: false,
    errorAbsolute: false,
    defaultWeight: 0.01,
    skipMorphTargets: false,
    morphTargetScalar: 0.1,
    weights: {
        // only for morph targets
        POSITION: 0.5,
        // for primitives and morph targets
        NORMAL: 0.01,
        TANGENT: 0.01,
        TEXCOORD: 0.01,
        COLOR: 0.01,
        JOINTS: 0.01,
        WEIGHTS: 0.01,
        // TEXCOORD_0: 0.02
    },
};

/**
 * Simplification algorithm, based on meshoptimizer, producing meshes with fewer
 * triangles and vertices. Simplification is lossy, but the algorithm aims to
 * preserve visual quality as much as possible for given parameters.
 *
 * The algorithm aims to reach the target 'ratio', while minimizing error. If
 * error exceeds the specified 'error' threshold, the algorithm will quit
 * before reaching the target ratio. Examples:
 *
 * - ratio=0.0, error=0.0001: Aims for maximum simplification, constrained to 0.01% error.
 * - ratio=0.5, error=0.0001: Aims for 50% simplification, constrained to 0.01% error.
 * - ratio=0.5, error=1: Aims for 50% simplification, unconstrained by error.
 *
 * Topology, particularly split vertices, will also limit the simplifier. For
 * best results, apply a {@link weld} operation before simplification.
 *
 * Example:
 *
 * ```javascript
 * import { simplify, weld } from '@gltf-transform/functions';
 * import { MeshoptSimplifier } from 'meshoptimizer';
 *
 * await document.transform(
 *   weld({ tolerance: 0.0001 }),
 *   simplify({ simplifier: MeshoptSimplifier, ratio: 0.75, error: 0.001 })
 * );
 * ```
 *
 * References:
 * - https://github.com/zeux/meshoptimizer/blob/master/js/README.md#simplifier
 *
 * @category Transforms
 */
export function simplifyAttr(_options) {
    const options = {
        ...SIMPLIFY_DEFAULTS,
        ..._options,
        weights: {
            ...SIMPLIFY_DEFAULTS.weights,
            ..._options.weights,
        },
    };
    const simplifier = options.simplifier;
    if (!simplifier) {
        throw new Error(`${NAME}: simplifier dependency required — install "meshoptimizer".`);
    }
    return createTransform(NAME, async (document, context) => {
        const logger = document.getLogger();
        await simplifier.ready;
        let numUnsupported = 0;
        // Simplify mesh primitives.
        for (const mesh of document.getRoot().listMeshes()) {
            for (const prim of mesh.listPrimitives()) {

                // https://github.com/donmccurdy/glTF-Transform/issues/822
                if (options.skipMorphTargets && prim.listTargets().length) {
                    logger.warn(`${NAME}: Skipping primitive of mesh "${
                        mesh.getName()
                    }": Morph targets.`);
                    continue;
                }
                const mode = prim.getMode();
                // TODO: do this in a worker-threads pool for modern processors
                if (mode === TRIANGLES || mode === TRIANGLE_STRIP || mode === TRIANGLE_FAN) {
                    simplifyPrimitive(document, prim, options);
                    if (getPrimitiveVertexCount(prim, VertexCountMethod.RENDER) === 0) {
                        prim.dispose();
                    }
                } else if (prim.getMode() === POINTS && !!simplifier.simplifyPoints) {
                    simplifyPrimitive(document, prim, options);
                    if (getPrimitiveVertexCount(prim, VertexCountMethod.RENDER) === 0) {
                        prim.dispose();
                    }
                } else {
                    numUnsupported++;
                }
            }
            if (mesh.listPrimitives().length === 0) mesh.dispose();
        }

        if (numUnsupported > 0) {
            logger.warn(`${NAME}: Skipping simplification of ${numUnsupported} primitives: Unsupported draw mode.`);
        }

        // Where multiple primitive indices point into the same vertex streams, simplification
        // may write duplicate streams. Find and remove the duplicates after processing.
        if (!isTransformPending(context, NAME, 'dedup')) {
            await document.transform(dedup({
                propertyTypes: [PropertyType.ACCESSOR]
            }));
        }
        logger.debug(`${NAME}: Complete.`);
    });
}

/**
 *
 * @param {import('@gltf-transform/core').Primitive | import('@gltf-transform/core').PrimitiveTarget} prim
 * @param {typeof SIMPLIFY_DEFAULTS} options
 * @param {Set<import('@gltf-transform/core').Accessor>} accessorSet
 * @param {import('@gltf-transform/core').TypedArray[]} attrArrays
 * @param {number[]} elementSizes
 * @param {number[]} weights
 * @param {number} attributeSize
 * @return {number}
 */
function extractAttributes(
    prim, options, accessorSet,
    attrArrays, elementSizes, weights,
    attributeSize
) {
    const semantics = prim.listSemantics();
    const isPrimitive = prim instanceof Primitive;
    for (let i = 0, length = semantics.length; i < length; i++) {
        let semantic = semantics[i];
        // if isPrimitive, POSITION should be skipped, while for targets it is not
        if (isPrimitive && semantic === 'POSITION') {
            continue;
        }
        // per-attribute weight config
        let weight = options.weights ?
            options.weights[semantic] :
            options.defaultWeight;
        if (weight === 0) {
            // skipped
            continue;
        }
        // null / undefined
        if (!weight) {
            if (options.weights) {
                if (semantic.startsWith('TEXCOORD_')) {
                    weight = options.weights.TEXCOORD;
                }
                if (semantic.startsWith('COLOR_')) {
                    weight = options.weights.COLOR;
                }
                if (semantic.startsWith('JOINTS_')) {
                    weight = options.weights.JOINTS;
                }
                if (semantic.startsWith('WEIGHTS_')) {
                    weight = options.weights.WEIGHTS;
                }
            }
            if (!weight && weight !== 0) {
                weight = options.defaultWeight;
            }
        }
        if (!isPrimitive) {
            weight *= options.morphTargetScalar;
        }
        if (weight === 0) {
            // skipped
            continue;
        }
        let attr = prim.getAttribute(semantic);
        if (!attr) {
            continue;
        }
        // deduplicate attribute accessors
        // a note here that this uses the first attribute,
        // not the one with greatest weight
        if (accessorSet.has(attr)) {
            continue;
        }
        accessorSet.add(attr);
        let array = attr.getArray();
        if (!array || !array.length) {
            continue;
        }
        attrArrays.push(array);
        // less get makes it faster
        let elementSize = attr.getElementSize();
        elementSizes.push(elementSize);
        attributeSize += elementSize;
        let componentType = attr.getComponentType();
        if (attr.getNormalized() && componentType !== Accessor.ComponentType.FLOAT) {
            switch (componentType) {
                case 5126:
                    // should not be here...
                    break;
                case 5123:
                    weight /= 65535.0;
                    break;
                case 5121:
                    weight /= 255.0;
                    break;
                case 5122:
                    weight /= 32767.0;
                    break;
                case 5120:
                    weight /= 127.0;
                    break;
                default:
                    throw new Error('Invalid component type.');
            }
        }
        for (let j = 0; j < elementSize; j++) {
            weights.push(weight);
        }
    }
    return attributeSize;
}

/**
 *
 * @param {import('@gltf-transform/core').Document} document
 * @param {import('@gltf-transform/core').Primitive} prim
 * @param {typeof SIMPLIFY_DEFAULTS} _options
 */
export function simplifyPrimitive(document, prim, _options) {
    const options = _options;
    const simplifier = options.simplifier;
    const logger = document.getLogger();


    switch (prim.getMode()) {
        case TRIANGLES:
            break;
        // TODO: impl this
        // case POINTS:
        //     return _simplifyPoints(document, prim, options);
        case TRIANGLE_STRIP:
        case TRIANGLE_FAN:
            convertPrimitiveToTriangles(prim);
            break;
        default:
            logger.warn(`${NAME}: Skipping primitive simplification: Unsupported draw mode ${prim.getMode()}`);
            return prim;
    }

    // (1) If primitive draws <50% of its vertex stream, compact before simplification.

    const srcVertexCount = getPrimitiveVertexCount(prim, VertexCountMethod.UPLOAD);
    const srcIndexCount = getPrimitiveVertexCount(prim, VertexCountMethod.RENDER);
    if (srcIndexCount < srcVertexCount / 2) {
        compactPrimitive(prim);
    }

    const position = prim.getAttribute('POSITION');
    const srcIndices = prim.getIndices();
    let positionArray = position.getArray();
    let indicesArray = srcIndices.getArray();

    // (2) Gather attributes and indices in Meshopt-compatible format.

    if (!(positionArray instanceof Float32Array)) {
        positionArray = new Float32Array(positionArray);
        if (position.getNormalized()) {
            // TODO: faster denormalize using wasm
            switch (position.getComponentType()) {
                case 5126: // FLOAT
                    break;
                case 5123: // UNSIGNED_SHORT
                    for (let j = 0, length = positionArray.length, i; j < length; j++) {
                        i = positionArray[j];
                        positionArray[j] = i / 65535.0;
                    }
                    break;
                case 5121: // UNSIGNED_BYTE
                    for (let j = 0, length = positionArray.length, i; j < length; j++) {
                        i = positionArray[j];
                        positionArray[j] = i / 255.0;
                    }
                    break;
                case 5122: // SHORT
                    for (let j = 0, length = positionArray.length, i; j < length; j++) {
                        i = positionArray[j];
                        positionArray[j] = Math.max(i / 32767.0, -1.0);
                    }
                    break;
                case 5120: // BYTE
                    for (let j = 0, length = positionArray.length, i; j < length; j++) {
                        i = positionArray[j];
                        positionArray[j] = Math.max(i / 127.0, -1.0);
                    }
                    break;
                default:
                    throw new Error('Invalid component type.');
            }
        }
    }
    if (!(indicesArray instanceof Uint32Array)) {
        indicesArray = new Uint32Array(indicesArray);
    }

    // (3) Run simplification.

    let attributeSize = 0;
    /**
     * @type {Set<import('@gltf-transform/core').Accessor>}
     */
    const accessorSet = new Set();
    /**
     * @type {import('@gltf-transform/core').TypedArray[]}
     */
    const attrArrays = [];
    /**
     * @type {number[]}
     */
    const weights = [];
    /**
     * @type {number[]}
     */
    const elementSizes = [];
    attributeSize = extractAttributes(prim, options, accessorSet,
        attrArrays, elementSizes, weights, attributeSize);
    const targets = prim.listTargets();
    if (targets && targets.length) {
        for (let i = 0, length = targets.length; i < length; i++) {
            attributeSize = extractAttributes(targets[i], options, accessorSet,
                attrArrays, elementSizes, weights, attributeSize);
        }
    }
    /**
     * @type {Float32Array}
     */
    let attributes = null;
    if (attributeSize !== 0) {
        attributes = new Float32Array(attributeSize * srcVertexCount);
        const c = elementSizes.length;
        let readOffset = 0;
        let writeOffset = 0;
        // this should be much faster than getElement
        for (let i = 0; i < srcVertexCount; i++) {
            for (let j = 0; j < c; j++) {
                const elementSize = elementSizes[j];
                const src = attrArrays[j];
                let readIndex = readOffset * elementSize;
                for (let k = 0; k < elementSize; k++) {
                    attributes[writeOffset++] = src[readIndex++];
                }
            }
            readOffset++;
        }
    }

    // (2) Run simplification.

    const targetCount = Math.floor(options.ratio * srcVertexCount / 3) * 3;
    const flags = [];
    if (options.lockBorder) {
        flags.push('LockBorder');
    }
    if (options.sparse) {
        flags.push('Sparse');
    }
    if (options.errorAbsolute) {
        flags.push('ErrorAbsolute');
    }
    if (attributeSize) {
        simplifier.useExperimentalFeatures = true;
    }
    const [dstIndicesArray, error] = attributeSize === 0 ? simplifier.simplify(
            indicesArray, positionArray, 3,
            targetCount, options.error,
            flags) :
        simplifier.simplifyWithAttributes(
            indicesArray, positionArray, 3,
            attributes, attributeSize, weights,
            // vertex_lock
            null,
            targetCount, options.error,
            flags);
    // compactPrimitive forces the clone here
    const [remap, unique] = simplifier.compactMesh(dstIndicesArray.slice());

    // (4) Assign subset of indexes; compact primitive.

    prim.setIndices(shallowCloneAccessor(document, srcIndices).setArray(dstIndicesArray));
    if (srcIndices.listParents().length === 1) srcIndices.dispose();
    compactPrimitive(prim, remap, unique);

    const dstVertexCount = getPrimitiveVertexCount(prim, VertexCountMethod.UPLOAD);
    if (dstVertexCount <= 65534) {
        prim.getIndices().setArray(new Uint16Array(prim.getIndices().getArray()));
    }

    logger.debug(`${NAME}: ${formatDeltaOp(position.getCount(), unique)} vertices, error: ${error.toFixed(4)}.`);

    return prim;
}

function shallowCloneAccessor(document, accessor) {
    return document
        .createAccessor(accessor.getName())
        .setArray(accessor.getArray())
        .setType(accessor.getType())
        .setBuffer(accessor.getBuffer())
        .setNormalized(accessor.getNormalized())
        .setSparse(accessor.getSparse());
}

For using this without rebuilding @gltf-transform/functions, functions listed here is not exposed, manually copy-and-paste could be needed:

• formatDeltaOp
• deepListAttributes
• remapAttribute
• deepSwapAttribute

[donmccurdy]

This looks outstanding, thank you! I'm going to wait and dig into this more after the next meshoptimizer release on npm, but would definitely like to incorporate attribute-aware simplification into the library then.

[lokiiarora]

@kzhsw Thanks for this. Will try to implement this on my own setup and let you know the result.
We wanted to go ahead with simplification & LOD generation as an automated pipeline but had issues because of the UV being distorted on meshoptimizer.