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.

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

#include "core/Parallel.h"

#include <algorithm>
#include <atomic>
#include <cmath>
#include <cstring>
#include <limits>

namespace sf {

namespace {

constexpr uint32_t kLeafSize = 4;

float boxDistance2(const AABB& b, const glm::vec3& p) {
    const glm::vec3 d = glm::max(glm::max(b.min - p, p - b.max), glm::vec3(0.0f));
    return glm::dot(d, d);
}

// Ray / box slab test: entry distance, or a negative value for a miss.
float rayBox(const AABB& b, const glm::vec3& o, const glm::vec3& inv, float maxT) {
    const glm::vec3 t0 = (b.min - o) * inv, t1 = (b.max - o) * inv;
    const glm::vec3 lo = glm::min(t0, t1), hi = glm::max(t0, t1);
    const float enter = std::max(std::max(lo.x, lo.y), std::max(lo.z, 0.0f));
    const float exit = std::min(std::min(hi.x, hi.y), std::min(hi.z, maxT));
    return enter <= exit ? enter : -1.0f;
}

glm::vec3 closestPointOnSegment(const glm::vec3& p, const glm::vec3& a, const glm::vec3& b, float& u) {
    const glm::vec3 ab = b - a;
    const float len2 = glm::dot(ab, ab);
    u = len2 > 0.0f ? std::clamp(glm::dot(p - a, ab) / len2, 0.0f, 1.0f) : 0.0f;
    return a + ab * u;
}

} // namespace

void FlatBVH::build(const std::vector<AABB>& boxes) {
    nodes_.clear();
    order_.resize(boxes.size());
    for (uint32_t i = 0; i < order_.size(); ++i) order_[i] = i;
    if (boxes.empty()) return;
    std::vector<glm::vec3> centers(boxes.size());
    for (size_t i = 0; i < boxes.size(); ++i) centers[i] = boxes[i].center();

    nodes_.reserve(2 * boxes.size() / kLeafSize + 2);
    nodes_.push_back({});
    struct Task {
        uint32_t node, begin, end;
    };
    std::vector<Task> stack{{0, 0, uint32_t(boxes.size())}};
    while (!stack.empty()) {
        const Task t = stack.back();
        stack.pop_back();
        AABB box, cbox;
        for (uint32_t i = t.begin; i < t.end; ++i) {
            box.expand(boxes[order_[i]]);
            cbox.expand(centers[order_[i]]);
        }
        nodes_[t.node].box = box;
        const uint32_t count = t.end - t.begin;
        const glm::vec3 ext = cbox.extent();
        if (count <= kLeafSize || std::max({ext.x, ext.y, ext.z}) <= 0.0f) {
            nodes_[t.node].first = t.begin;
            nodes_[t.node].count = count;
            continue;
        }
        const int axis = ext.x >= ext.y && ext.x >= ext.z ? 0 : ext.y >= ext.z ? 1 : 2;
        const uint32_t mid = t.begin + count / 2;
        std::nth_element(order_.begin() + t.begin, order_.begin() + mid, order_.begin() + t.end,
                         [&](uint32_t a, uint32_t b) { return centers[a][axis] < centers[b][axis]; });
        const uint32_t left = uint32_t(nodes_.size());
        nodes_.push_back({});
        nodes_.push_back({});
        nodes_[t.node].first = left;
        nodes_[t.node].count = 0;
        stack.push_back({left, t.begin, mid});
        stack.push_back({left + 1, mid, t.end});
    }
}

glm::vec3 closestPointOnTriangle(const glm::vec3& p, const glm::vec3& a, const glm::vec3& b, const glm::vec3& c,
                                 glm::vec3& bary) {
    // Ericson, Real-Time Collision Detection 5.1.5.
    const glm::vec3 ab = b - a, ac = c - a, ap = p - a;
    const float d1 = glm::dot(ab, ap), d2 = glm::dot(ac, ap);
    if (d1 <= 0.0f && d2 <= 0.0f) {
        bary = {1, 0, 0};
        return a;
    }
    const glm::vec3 bp = p - b;
    const float d3 = glm::dot(ab, bp), d4 = glm::dot(ac, bp);
    if (d3 >= 0.0f && d4 <= d3) {
        bary = {0, 1, 0};
        return b;
    }
    const float vc = d1 * d4 - d3 * d2;
    if (vc <= 0.0f && d1 >= 0.0f && d3 <= 0.0f && d1 - d3 > 0.0f) {
        const float v = d1 / (d1 - d3);
        bary = {1 - v, v, 0};
        return a + ab * v;
    }
    const glm::vec3 cp = p - c;
    const float d5 = glm::dot(ab, cp), d6 = glm::dot(ac, cp);
    if (d6 >= 0.0f && d5 <= d6) {
        bary = {0, 0, 1};
        return c;
    }
    const float vb = d5 * d2 - d1 * d6;
    if (vb <= 0.0f && d2 >= 0.0f && d6 <= 0.0f && d2 - d6 > 0.0f) {
        const float w = d2 / (d2 - d6);
        bary = {1 - w, 0, w};
        return a + ac * w;
    }
    const float va = d3 * d6 - d5 * d4;
    if (va <= 0.0f && d4 - d3 >= 0.0f && d5 - d6 >= 0.0f && (d4 - d3) + (d5 - d6) > 0.0f) {
        const float w = (d4 - d3) / ((d4 - d3) + (d5 - d6));
        bary = {0, 1 - w, w};
        return b + (c - b) * w;
    }
    const float sum = va + vb + vc;
    if (!(std::abs(sum) > 0.0f)) { // degenerate triangle: nearest of its edges
        float u = 0.0f;
        glm::vec3 best = closestPointOnSegment(p, a, b, u);
        bary = {1 - u, u, 0};
        float bestD = glm::dot(best - p, best - p);
        const glm::vec3 q1 = closestPointOnSegment(p, b, c, u);
        if (const float d = glm::dot(q1 - p, q1 - p); d < bestD) {
            best = q1, bestD = d, bary = {0, 1 - u, u};
        }
        const glm::vec3 q2 = closestPointOnSegment(p, a, c, u);
        if (glm::dot(q2 - p, q2 - p) < bestD) best = q2, bary = {1 - u, 0, u};
        return best;
    }
    const float denom = 1.0f / sum;
    const float v = vb * denom, w = vc * denom;
    bary = {1 - v - w, v, w};
    return a + ab * v + ac * w;
}

void TriangleBVH::build(std::vector<glm::vec3> positions, std::vector<glm::uvec3> triangles) {
    positions_ = std::move(positions);
    triangles_ = std::move(triangles);
    std::vector<AABB> boxes(triangles_.size());
    parallelFor(triangles_.size(), [&](size_t b, size_t e) {
        for (size_t t = b; t < e; ++t) {
            AABB box;
            for (int k = 0; k < 3; ++k) box.expand(positions_[triangles_[t][k]]);
            boxes[t] = box;
        }
    });
    bvh_.build(boxes);
}

glm::vec3 TriangleBVH::faceNormal(uint32_t t) const {
    const glm::uvec3 tri = triangles_[t];
    const glm::vec3 n = glm::cross(positions_[tri.y] - positions_[tri.x], positions_[tri.z] - positions_[tri.x]);
    const float len = glm::length(n);
    return len > 0.0f ? n / len : glm::vec3(0.0f);
}

bool TriangleBVH::closestPoint(const glm::vec3& p, float maxDistance, SurfaceHit& hit) const {
    if (bvh_.empty()) return false;
    const auto& nodes = bvh_.nodes();
    const auto& order = bvh_.order();
    float best2 = maxDistance * maxDistance;
    bool found = false;
    uint32_t stack[64];
    int sp = 0;
    stack[sp++] = 0;
    while (sp > 0) {
        const FlatBVH::Node& n = nodes[stack[--sp]];
        if (boxDistance2(n.box, p) > best2) continue;
        if (n.count > 0) {
            for (uint32_t i = n.first; i < n.first + n.count; ++i) {
                const uint32_t t = order[i];
                const glm::uvec3 tri = triangles_[t];
                glm::vec3 bary;
                const glm::vec3 q = closestPointOnTriangle(p, positions_[tri.x], positions_[tri.y], positions_[tri.z], bary);
                const float d2 = glm::dot(q - p, q - p);
                if (d2 <= best2) {
                    best2 = d2;
                    found = true;
                    hit.prim = t;
                    hit.position = q;
                    hit.bary = bary;
                }
            }
            continue;
        }
        // Nearer child last, so it is popped first.
        const float dl = boxDistance2(nodes[n.first].box, p), dr = boxDistance2(nodes[n.first + 1].box, p);
        if (sp + 2 > 64) continue; // cannot happen with a median split of < 2^60 primitives
        if (dl < dr) {
            stack[sp++] = n.first + 1;
            stack[sp++] = n.first;
        } else {
            stack[sp++] = n.first;
            stack[sp++] = n.first + 1;
        }
    }
    if (found) hit.distance = std::sqrt(best2);
    return found;
}

bool TriangleBVH::raycast(const glm::vec3& origin, const glm::vec3& dir, float maxT, SurfaceHit& hit) const {
    if (bvh_.empty()) return false;
    const auto& nodes = bvh_.nodes();
    const auto& order = bvh_.order();
    const glm::vec3 inv(1.0f / dir.x, 1.0f / dir.y, 1.0f / dir.z);
    float bestT = maxT;
    bool found = false;
    uint32_t stack[64];
    int sp = 0;
    stack[sp++] = 0;
    while (sp > 0) {
        const FlatBVH::Node& n = nodes[stack[--sp]];
        if (rayBox(n.box, origin, inv, bestT) < 0.0f) continue;
        if (n.count > 0) {
            for (uint32_t i = n.first; i < n.first + n.count; ++i) {
                const uint32_t t = order[i];
                const glm::uvec3 tri = triangles_[t];
                const glm::vec3 a = positions_[tri.x], e1 = positions_[tri.y] - a, e2 = positions_[tri.z] - a;
                const glm::vec3 pv = glm::cross(dir, e2);
                const float det = glm::dot(e1, pv);
                if (std::abs(det) < 1e-20f) continue;
                const float invDet = 1.0f / det;
                const glm::vec3 tv = origin - a;
                const float u = glm::dot(tv, pv) * invDet;
                if (u < 0.0f || u > 1.0f) continue;
                const glm::vec3 qv = glm::cross(tv, e1);
                const float v = glm::dot(dir, qv) * invDet;
                if (v < 0.0f || u + v > 1.0f) continue;
                const float tt = glm::dot(e2, qv) * invDet;
                if (tt < 0.0f || tt > bestT) continue;
                bestT = tt;
                found = true;
                hit.prim = t;
                hit.bary = {1 - u - v, u, v};
                hit.position = origin + dir * tt;
            }
            continue;
        }
        const float tl = rayBox(nodes[n.first].box, origin, inv, bestT);
        const float tr = rayBox(nodes[n.first + 1].box, origin, inv, bestT);
        if (sp + 2 > 64) continue;
        if (tl >= 0.0f && tr >= 0.0f) {
            if (tl < tr) {
                stack[sp++] = n.first + 1;
                stack[sp++] = n.first;
            } else {
                stack[sp++] = n.first;
                stack[sp++] = n.first + 1;
            }
        } else if (tl >= 0.0f) {
            stack[sp++] = n.first;
        } else if (tr >= 0.0f) {
            stack[sp++] = n.first + 1;
        }
    }
    if (found) hit.distance = bestT;
    return found;
}

void SegmentBVH::build(std::vector<glm::vec3> a, std::vector<glm::vec3> b) {
    a_ = std::move(a);
    b_ = std::move(b);
    std::vector<AABB> boxes(a_.size());
    for (size_t i = 0; i < a_.size(); ++i) {
        boxes[i].expand(a_[i]);
        boxes[i].expand(b_[i]);
    }
    bvh_.build(boxes);
}

bool SegmentBVH::closestPoint(const glm::vec3& p, float maxDistance, SurfaceHit& hit) const {
    if (bvh_.empty()) return false;
    const auto& nodes = bvh_.nodes();
    const auto& order = bvh_.order();
    float best2 = maxDistance * maxDistance;
    bool found = false;
    uint32_t stack[64];
    int sp = 0;
    stack[sp++] = 0;
    while (sp > 0) {
        const FlatBVH::Node& n = nodes[stack[--sp]];
        if (boxDistance2(n.box, p) > best2) continue;
        if (n.count > 0) {
            for (uint32_t i = n.first; i < n.first + n.count; ++i) {
                const uint32_t s = order[i];
                float u = 0.0f;
                const glm::vec3 q = closestPointOnSegment(p, a_[s], b_[s], u);
                const float d2 = glm::dot(q - p, q - p);
                if (d2 <= best2) {
                    best2 = d2;
                    found = true;
                    hit.prim = s;
                    hit.position = q;
                    hit.bary = {1 - u, u, 0};
                }
            }
            continue;
        }
        if (sp + 2 > 64) continue;
        stack[sp++] = n.first;
        stack[sp++] = n.first + 1;
    }
    if (found) hit.distance = std::sqrt(best2);
    return found;
}

SurfaceDeviation measureDeviation(const Mesh& mesh, const Mesh& reference, bool symmetric) {
    SurfaceDeviation out;
    double sum = 0.0, sum2 = 0.0;
    size_t count = 0;
    std::atomic<uint32_t> maxBits{0}; // non-negative floats order like their bits
    auto oneWay = [&](const Mesh& from, const Mesh& to) {
        TriangleBVH bvh;
        bvh.build(to);
        const size_t n = from.vertexCount();
        std::vector<float> d(n, 0.0f);
        parallelFor(n, [&](size_t b, size_t e) {
            float localMax = 0.0f;
            for (size_t v = b; v < e; ++v) {
                SurfaceHit hit;
                d[v] = bvh.closestPoint(from.positions[v], std::numeric_limits<float>::max(), hit) ? hit.distance : 0.0f;
                localMax = std::max(localMax, d[v]);
            }
            uint32_t bits;
            std::memcpy(&bits, &localMax, 4);
            uint32_t cur = maxBits.load();
            while (bits > cur && !maxBits.compare_exchange_weak(cur, bits)) {
            }
        });
        for (float x : d) {
            sum += x;
            sum2 += double(x) * x;
        }
        count += n;
    };
    if (mesh.vertexCount() == 0 || reference.triangleCount() == 0) return out;
    oneWay(mesh, reference);
    if (symmetric && reference.vertexCount() > 0 && mesh.triangleCount() > 0) oneWay(reference, mesh);
    const uint32_t bits = maxBits.load();
    std::memcpy(&out.max, &bits, 4);
    out.mean = count ? float(sum / double(count)) : 0.0f;
    out.rms = count ? float(std::sqrt(sum2 / double(count))) : 0.0f;
    return out;
}

} // namespace sf