Skip to content

Free, open-source 3D sculpting for Linux, macOS and Windows: dense meshes, remeshing, painting, built-in AI (image/text to 3D), Send to Unreal, game-ready LODs, Gaussian splats and OpenUSD.

11.3 KB
Raw Blame
// SculptForge - open source digital sculpting
// SPDX-License-Identifier: GPL-3.0-or-later
#include "core/Decimate.h"

#include <algorithm>
#include <cmath>
#include <queue>
#include <unordered_map>

namespace sf {

namespace {

// Symmetric 4x4 quadric, upper triangle: xx xy xz xw yy yz yw zz zw ww.
struct Quadric {
    double q[10] = {};

    static Quadric plane(const glm::dvec3& n, double d, double w) {
        Quadric r;
        r.q[0] = w * n.x * n.x; r.q[1] = w * n.x * n.y; r.q[2] = w * n.x * n.z; r.q[3] = w * n.x * d;
        r.q[4] = w * n.y * n.y; r.q[5] = w * n.y * n.z; r.q[6] = w * n.y * d;
        r.q[7] = w * n.z * n.z; r.q[8] = w * n.z * d;
        r.q[9] = w * d * d;
        return r;
    }
    Quadric& operator+=(const Quadric& o) {
        for (int i = 0; i < 10; ++i) q[i] += o.q[i];
        return *this;
    }
    Quadric operator+(const Quadric& o) const {
        Quadric r = *this;
        return r += o;
    }
    double eval(const glm::vec3& p) const {
        const double x = p.x, y = p.y, z = p.z;
        return q[0] * x * x + 2 * q[1] * x * y + 2 * q[2] * x * z + 2 * q[3] * x + q[4] * y * y + 2 * q[5] * y * z +
               2 * q[6] * y + q[7] * z * z + 2 * q[8] * z + q[9];
    }
};

struct Candidate {
    double cost;
    uint32_t from, to;
    uint32_t fromVersion, toVersion;
    bool operator>(const Candidate& o) const { return cost > o.cost; }
};

uint64_t edgeKey(uint32_t a, uint32_t b) {
    if (a > b) std::swap(a, b);
    return (uint64_t(a) << 32) | b;
}

} // namespace

Mesh decimate(const Mesh& src, size_t targetTriangles, bool keepMasked) {
    const size_t nv = src.vertexCount();
    const size_t nt = src.triangleCount();
    targetTriangles = std::max<size_t>(targetTriangles, 4);
    if (nt <= targetTriangles) return src;

    const auto& P = src.positions;
    std::vector<glm::uvec3> F = src.triangles;
    std::vector<glm::vec2> FUV = src.uvs.size() == nt * 3 ? src.uvs : std::vector<glm::vec2>(); // per corner
    std::vector<char> faceAlive(nt, 1);
    std::vector<std::vector<uint32_t>> vFaces(nv);
    for (uint32_t f = 0; f < nt; ++f)
        for (int c = 0; c < 3; ++c) vFaces[F[f][c]].push_back(f);

    // Vertices on a UV seam (corners with different UVs) stay put: collapsing one would give the corners on
    // the other side of the seam UVs from the wrong island, scrambling a painted texture there. Other vertices
    // collapse onto a kept vertex, whose UV in the collapsing faces' island the moved corners then take (exact).
    std::vector<char> uvSeam(nv, 0);
    if (!FUV.empty()) {
        std::vector<glm::vec2> firstUv(nv, glm::vec2(-1e30f));
        for (uint32_t f = 0; f < nt; ++f)
            for (int c = 0; c < 3; ++c) {
                const uint32_t v = F[f][c];
                const glm::vec2 uv = FUV[size_t(f) * 3 + size_t(c)];
                if (firstUv[v].x == -1e30f) firstUv[v] = uv;
                else if (glm::any(glm::greaterThan(glm::abs(firstUv[v] - uv), glm::vec2(1e-6f)))) uvSeam[v] = 1;
            }
    }

    // Keep masked (#43): masked vertices are never collapsed away, so they and the triangles between them stay
    // exactly as they were (a collapse keeps the other endpoint where it is).
    std::vector<char> locked(nv, 0);
    if (keepMasked && src.hasMask())
        for (size_t v = 0; v < nv; ++v) locked[v] = src.mask[v] >= kKeepMaskedThreshold;

    // Area-weighted plane quadrics.
    std::vector<Quadric> Q(nv);
    std::vector<glm::dvec3> faceN(nt);
    for (uint32_t f = 0; f < nt; ++f) {
        glm::dvec3 a = P[F[f].x], b = P[F[f].y], c = P[F[f].z];
        glm::dvec3 n = glm::cross(b - a, c - a);
        double len = glm::length(n);
        if (len <= 0.0) continue;
        n /= len;
        faceN[f] = n;
        Quadric q = Quadric::plane(n, -glm::dot(n, a), len * 0.5);
        for (int c2 = 0; c2 < 3; ++c2) Q[F[f][c2]] += q;
    }

    // Boundary edges get strong perpendicular constraint planes.
    std::unordered_map<uint64_t, std::pair<uint32_t, uint32_t>> edgeUse; // key -> (count, face)
    edgeUse.reserve(nt * 2);
    for (uint32_t f = 0; f < nt; ++f) {
        for (int e = 0; e < 3; ++e) {
            auto& u = edgeUse[edgeKey(F[f][e], F[f][(e + 1) % 3])];
            ++u.first;
            u.second = f;
        }
    }
    for (const auto& [key, use] : edgeUse) {
        if (use.first != 1) continue;
        uint32_t a = uint32_t(key >> 32), b = uint32_t(key & 0xffffffffu);
        glm::dvec3 pa = P[a], pb = P[b];
        glm::dvec3 e = pb - pa;
        glm::dvec3 bn = glm::cross(e, faceN[use.second]);
        double len = glm::length(bn);
        if (len <= 0.0) continue;
        bn /= len;
        Quadric q = Quadric::plane(bn, -glm::dot(bn, pa), glm::dot(e, e) * 100.0);
        Q[a] += q;
        Q[b] += q;
    }

    std::vector<uint32_t> version(nv, 0);
    std::vector<char> vAlive(nv, 1);
    std::priority_queue<Candidate, std::vector<Candidate>, std::greater<>> heap;

    auto pushEdge = [&](uint32_t a, uint32_t b) {
        Quadric qs = Q[a] + Q[b];
        heap.push({qs.eval(P[b]), a, b, version[a], version[b]}); // a collapses onto b
        heap.push({qs.eval(P[a]), b, a, version[b], version[a]}); // b collapses onto a
    };
    for (const auto& [key, use] : edgeUse) pushEdge(uint32_t(key >> 32), uint32_t(key & 0xffffffffu));
    edgeUse.clear();

    std::vector<uint32_t> nbrU, nbrV, shared;
    auto gatherNeighbors = [&](uint32_t v, std::vector<uint32_t>& out) {
        out.clear();
        for (uint32_t f : vFaces[v]) {
            if (!faceAlive[f]) continue;
            for (int c = 0; c < 3; ++c)
                if (F[f][c] != v) out.push_back(F[f][c]);
        }
        std::sort(out.begin(), out.end());
        out.erase(std::unique(out.begin(), out.end()), out.end());
    };

    size_t liveFaces = nt;
    while (liveFaces > targetTriangles && !heap.empty()) {
        const Candidate c = heap.top();
        heap.pop();
        const uint32_t u = c.from, v = c.to;
        if (!vAlive[u] || !vAlive[v] || version[u] != c.fromVersion || version[v] != c.toVersion) continue;
        if (uvSeam[u] || locked[u]) continue;

        shared.clear();
        for (uint32_t f : vFaces[u]) {
            if (!faceAlive[f]) continue;
            if (F[f].x == v || F[f].y == v || F[f].z == v) shared.push_back(f);
        }
        if (shared.empty()) continue; // no longer an edge

        // Link condition: the edge's endpoints may share only the vertices
        // opposite the edge, otherwise collapsing makes the mesh non-manifold.
        gatherNeighbors(u, nbrU);
        gatherNeighbors(v, nbrV);
        size_t common = 0;
        for (size_t i = 0, j = 0; i < nbrU.size() && j < nbrV.size();) {
            if (nbrU[i] < nbrV[j]) ++i;
            else if (nbrU[i] > nbrV[j]) ++j;
            else ++common, ++i, ++j;
        }
        if (common != shared.size()) continue;

        // Reject collapses that flip or degenerate surrounding triangles.
        bool ok = true;
        for (uint32_t f : vFaces[u]) {
            if (!faceAlive[f] || std::find(shared.begin(), shared.end(), f) != shared.end()) continue;
            glm::uvec3 t = F[f];
            glm::vec3 before = glm::cross(P[t.y] - P[t.x], P[t.z] - P[t.x]);
            for (int k = 0; k < 3; ++k)
                if (t[k] == u) t[k] = v;
            glm::vec3 after = glm::cross(P[t.y] - P[t.x], P[t.z] - P[t.x]);
            float la = glm::length(after), lb = glm::length(before);
            if (la <= 1e-12f || (lb > 0.0f && glm::dot(after, before) < 0.2f * la * lb)) {
                ok = false;
                break;
            }
        }
        if (!ok) continue;

        // Corners that move from u to v take v's UV from a collapsed face (u is not on a seam, so all of its
        // faces lie in one UV island; skip the collapse if the collapsed faces disagree about v's UV).
        glm::vec2 uvOfV(0.0f);
        if (!FUV.empty()) {
            bool first = true;
            for (uint32_t f : shared)
                for (int k = 0; k < 3; ++k)
                    if (F[f][k] == v) {
                        const glm::vec2 uv = FUV[size_t(f) * 3 + size_t(k)];
                        if (!first && glm::any(glm::greaterThan(glm::abs(uv - uvOfV), glm::vec2(1e-6f)))) ok = false;
                        uvOfV = uv;
                        first = false;
                    }
            if (!ok) continue;
        }
        for (uint32_t f : shared) {
            faceAlive[f] = 0;
            --liveFaces;
        }
        for (uint32_t f : vFaces[u]) {
            if (!faceAlive[f]) continue;
            for (int k = 0; k < 3; ++k)
                if (F[f][k] == u) {
                    F[f][k] = v;
                    if (!FUV.empty()) FUV[size_t(f) * 3 + size_t(k)] = uvOfV;
                }
            vFaces[v].push_back(f);
        }
        vFaces[u].clear();
        vAlive[u] = 0;
        Q[v] += Q[u];
        ++version[v];
        std::erase_if(vFaces[v], [&](uint32_t f) { return !faceAlive[f]; });

        gatherNeighbors(v, nbrV);
        for (uint32_t w : nbrV) pushEdge(v, w);
    }

    // Compact into a new mesh, carrying every per-vertex array across.
    constexpr uint32_t kUnused = ~0u;
    std::vector<uint32_t> remap(nv, kUnused);
    std::vector<uint32_t> kept;
    Mesh out;
    out.triangles.reserve(liveFaces);
    for (uint32_t f = 0; f < nt; ++f) {
        if (!faceAlive[f]) continue;
        glm::uvec3 t;
        for (int k = 0; k < 3; ++k) {
            uint32_t& r = remap[F[f][k]];
            if (r == kUnused) {
                r = static_cast<uint32_t>(kept.size());
                kept.push_back(F[f][k]);
            }
            t[k] = r;
        }
        out.triangles.push_back(t);
        // Surviving faces keep their group, visibility and (updated) corner UVs.
        if (src.facegroups.size() == nt) out.facegroups.push_back(src.facegroups[f]);
        if (src.hidden.size() == nt) out.hidden.push_back(src.hidden[f]);
        if (!FUV.empty()) out.uvs.insert(out.uvs.end(), FUV.begin() + std::ptrdiff_t(f) * 3, FUV.begin() + std::ptrdiff_t(f) * 3 + 3);
    }
    out.positions.reserve(kept.size());
    for (uint32_t v : kept) out.positions.push_back(src.positions[v]);
    if (!FUV.empty()) { // the painted texture still fits the kept UVs (shared until one side paints)
        out.texture = src.texture;
        out.paintToTexture = src.paintToTexture;
    }
    if (src.mask.size() == nv)
        for (uint32_t v : kept) out.mask.push_back(src.mask[v]);
    if (src.colors.size() == nv)
        for (uint32_t v : kept) out.colors.push_back(src.colors[v]);
    if (!src.layers.empty()) {
        for (uint32_t v : kept) out.base.push_back(src.base[v]);
        for (const auto& l : src.layers) {
            SculptLayer nl{l.name, {}, l.weight};
            nl.delta.reserve(kept.size());
            for (uint32_t v : kept) nl.delta.push_back(l.delta[v]);
            out.layers.push_back(std::move(nl));
        }
    }
    copyPaintLayers(src, out, kept);
    out.rebuildTopology();
    out.recomputeAllNormals();
    return out;
}

std::vector<Mesh> generateLods(const Mesh& src, int levels, float ratio) {
    std::vector<Mesh> lods;
    levels = std::max(levels, 1);
    ratio = std::clamp(ratio, 0.01f, 0.99f);
    lods.push_back(src);
    for (int i = 1; i < levels; ++i) {
        size_t target = static_cast<size_t>(std::llround(double(lods.back().triangleCount()) * ratio));
        lods.push_back(decimate(lods.back(), target));
    }
    return lods;
}

} // namespace sf