Skip to content

A fast 2D and 3D game engine — TypeScript SDK, C++/WebAssembly core, visual editor. Ship one project to web, desktop, WeChat MiniGames, playable ads, and native Android / iOS.

5.7 KB
Raw Blame
// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: Copyright (c) 2024-present ESEngine Team
/**
 * @file  decimate.ts — the `decimate` step: fewer triangles over the same surface.
 *
 *        The collapse is meshoptimizer's quadric-error simplifier, as a mesh import's LOD
 *        levels use. What is here is what it is told about a vertex and what the result is
 *        made of: surviving vertices keep their places, so every triangle out is three
 *        corners of the mesh that went in, and takes its paint, tag and shading from the
 *        faces those corners were on. It needs MeshoptSimplifier.ready; prepareModeling
 *        waits for that.
 */
import { MeshoptSimplifier } from 'meshoptimizer';
import { triangulateFace } from './triangulate';
import { compact, cross, dot, faceArea, faceNormal, normalize, selectFaces, sub, type Face, type FaceSelector, type PolyMesh, type Vec3 } from './polyMesh';

export interface DecimateParams {
    faces?: FaceSelector;
    /** Share of the triangles to keep, in (0, 1]. */
    ratio?: number;
    /** Triangles to end with, instead of a share. */
    triangles?: number;
    /** The most the surface may move, as a share of the mesh's size. It wins over the two above. */
    error?: number;
}

const DEFAULT_ERROR = 0.02;
/** A shading normal bends light and may give a little; a change of paint is a line someone drew. */
const NORMAL_WEIGHT = 0.5;
const COLOR_WEIGHT = 1;
const ATTRIBUTES = 6;

export const triangleCount = (mesh: PolyMesh): number => mesh.faces.reduce((n, f) => n + Math.max(0, f.v.length - 2), 0);

/** Each vertex's normal and paint over @p faces: what a collapse must not smear. */
function vertexAttributes(mesh: PolyMesh, faces: readonly Face[]): Float32Array {
    const out = new Float32Array(mesh.positions.length * ATTRIBUTES);
    const paints = new Uint32Array(mesh.positions.length);
    for (const face of faces) {
        const n = faceNormal(mesh, face);
        const area = faceArea(mesh, face);
        const color = face.color ?? [1, 1, 1, 1];
        for (const v of face.v) {
            for (let k = 0; k < 3; k++) {
                out[v * ATTRIBUTES + k]! += n[k]! * area;
                out[v * ATTRIBUTES + 3 + k]! += color[k]!;
            }
            paints[v]!++;
        }
    }
    for (let v = 0; v < paints.length; v++) {
        if (paints[v] === 0) continue;
        const n = normalize([out[v * ATTRIBUTES]!, out[v * ATTRIBUTES + 1]!, out[v * ATTRIBUTES + 2]!]);
        for (let k = 0; k < 3; k++) {
            out[v * ATTRIBUTES + k] = n[k]!;
            out[v * ATTRIBUTES + 3 + k]! /= paints[v]!;
        }
    }
    return out;
}

export function decimate(mesh: PolyMesh, p: DecimateParams): PolyMesh {
    if ((p.ratio === undefined) === (p.triangles === undefined)) throw new Error('give one of `ratio` and `triangles`');
    if (p.ratio !== undefined && !(p.ratio > 0 && p.ratio <= 1)) throw new Error(`ratio ${p.ratio} must be in (0, 1]`);
    if (p.triangles !== undefined && p.triangles < 1) throw new Error(`triangles ${p.triangles} must be at least 1`);
    if (p.error !== undefined && !(p.error > 0)) throw new Error(`error ${p.error} must be positive`);

    const selector = p.faces ?? 'all';
    const hit = selectFaces(mesh, selector);
    if (hit.length === 0) throw new Error(`\`faces\` ${JSON.stringify(selector)} matched no face`);
    const chosen = new Set(hit);
    const faces = hit.map((f) => mesh.faces[f]!);
    const indices = Uint32Array.from(faces.flatMap((face) => triangulateFace(mesh, face).flat()));
    const count = indices.length / 3;
    const target = p.triangles ?? Math.round(count * p.ratio!);
    if (target >= count) return mesh;

    // The seam with faces left alone stays where it is, or the two would part.
    const lock = new Uint8Array(mesh.positions.length);
    mesh.faces.forEach((face, f) => {
        if (!chosen.has(f)) for (const v of face.v) lock[v] = 1;
    });
    const positions = Float32Array.from(mesh.positions.flat());
    const [kept] = MeshoptSimplifier.simplifyWithAttributes(
        indices, positions, 3, vertexAttributes(mesh, faces), ATTRIBUTES,
        [NORMAL_WEIGHT, NORMAL_WEIGHT, NORMAL_WEIGHT, COLOR_WEIGHT, COLOR_WEIGHT, COLOR_WEIGHT],
        // Not RegularizeLight: under an error limit it stops a flat surface from collapsing at all.
        lock, target * 3, p.error ?? DEFAULT_ERROR, ['LockBorder'],
    );
    if (kept.length === 0) throw new Error(`nothing is left at ${target} triangles; raise \`ratio\` or \`triangles\``);

    const around = new Map<number, Face[]>();
    for (const face of faces) {
        for (const v of face.v) {
            const at = around.get(v);
            if (at) at.push(face); else around.set(v, [face]);
        }
    }
    const made: Face[] = [];
    for (let i = 0; i < kept.length; i += 3) {
        const [a, b, c] = [kept[i]!, kept[i + 1]!, kept[i + 2]!];
        const [pa, pb, pc]: Vec3[] = [mesh.positions[a]!, mesh.positions[b]!, mesh.positions[c]!];
        const normal = normalize(cross(sub(pb, pa), sub(pc, pa)));
        // The old face this triangle lies on the most: the one holding most of its corners, then the one facing its way.
        const shared = new Map<Face, number>();
        for (const v of [a, b, c]) for (const face of around.get(v)!) shared.set(face, (shared.get(face) ?? 0) + 1);
        let from: Face | null = null;
        let best = -Infinity;
        for (const [face, corners] of shared) {
            const score = corners + dot(faceNormal(mesh, face), normal);
            if (score > best) { best = score; from = face; }
        }
        made.push({ ...from!, v: [a, b, c] });
    }
    return compact({ positions: mesh.positions, faces: [...mesh.faces.filter((_, f) => !chosen.has(f)), ...made] });
}