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.
C++ 3d3d-sculptingcppdear-imguidigital-sculptingfbxgame-developmentgaussian-splattinggltfimage-to-3dmcpopenglopenusdsculptingtext-to-3dunreal-engine
// SculptForge - open source digital sculpting
// SPDX-License-Identifier: GPL-3.0-or-later
//
// Ray BVH for baking (core/Bake.h, core/MeshMaps.h): a binned-SAH tree over a triangle list with a nearest-hit
// query (the hit nearest a target distance along the ray, for cage rays) and an any-hit query (occlusion).
// Queries are const and keep their state on the stack, so any number of threads can cast at once. Unlike the
// brush BVH (core/BVH.h) it is built once and never refitted.
#pragma once
#include <glm/glm.hpp>
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <limits>
#include <vector>
namespace sf {
struct RayHitInfo {
float t = 0, u = 0, v = 0;
uint32_t tri = 0;
};
class RayBvh {
public:
void build(const std::vector<glm::vec3>& pos, const std::vector<glm::uvec3>& tris) {
const size_t n = tris.size();
nodes_.clear();
order_.resize(n);
std::vector<glm::vec3> centroid(n);
std::vector<Box> box(n);
for (size_t i = 0; i < n; ++i) {
order_[i] = uint32_t(i);
const glm::vec3 &a = pos[tris[i].x], &b = pos[tris[i].y], &c = pos[tris[i].z];
box[i].lo = glm::min(a, glm::min(b, c));
box[i].hi = glm::max(a, glm::max(b, c));
centroid[i] = (box[i].lo + box[i].hi) * 0.5f;
}
nodes_.reserve(n ? 2 * n / kLeaf + 16 : 1);
nodes_.push_back({});
if (n == 0) {
nodes_[0].lo = nodes_[0].hi = glm::vec3(0.0f);
return;
}
struct Job {
uint32_t node, first, count;
};
std::vector<Job> stack = {{0, 0, uint32_t(n)}};
while (!stack.empty()) {
const Job j = stack.back();
stack.pop_back();
Box nb, cb;
for (uint32_t i = j.first; i < j.first + j.count; ++i) {
nb.grow(box[order_[i]]);
cb.grow(centroid[order_[i]]);
}
nodes_[j.node].lo = nb.lo;
nodes_[j.node].hi = nb.hi;
uint32_t mid = 0;
if (j.count > kLeaf && split(j.first, j.count, nb, cb, box, centroid, mid)) {
const uint32_t left = uint32_t(nodes_.size());
nodes_.push_back({});
nodes_.push_back({});
nodes_[j.node].index = left;
nodes_[j.node].count = 0;
stack.push_back({left, j.first, mid - j.first});
stack.push_back({left + 1, mid, j.first + j.count - mid});
} else {
nodes_[j.node].index = j.first;
nodes_[j.node].count = j.count;
}
}
tris_.resize(n);
for (size_t i = 0; i < n; ++i) {
const glm::uvec3& t = tris[order_[i]];
tris_[i] = {pos[t.x], pos[t.y] - pos[t.x], pos[t.z] - pos[t.x]};
}
}
// The hit with t in [tmin, tmax] nearest to `target`.
bool nearest(const glm::vec3& o, const glm::vec3& d, float tmin, float tmax, float target, RayHitInfo& hit) const {
if (tris_.empty()) return false;
const glm::vec3 inv = invDir(d);
float best = std::numeric_limits<float>::max();
bool found = false;
uint32_t stack[64];
int sp = 0;
float tn, tf;
if (!slab(nodes_[0], o, inv, tmin, tmax, tn, tf)) return false;
stack[sp++] = 0;
while (sp) {
const Node& n = nodes_[stack[--sp]];
if (!slab(n, o, inv, tmin, tmax, tn, tf) || bound(tn, tf, target) >= best) continue;
if (n.count) {
for (uint32_t i = n.index; i < n.index + n.count; ++i) {
float t, u, v;
if (!intersect(tris_[i], o, d, t, u, v) || t < tmin || t > tmax) continue;
const float e = std::abs(t - target);
if (e < best) {
best = e;
hit = {t, u, v, order_[i]};
found = true;
}
}
continue;
}
float an, af, bn, bf;
const bool ha = slab(nodes_[n.index], o, inv, tmin, tmax, an, af);
const bool hb = slab(nodes_[n.index + 1], o, inv, tmin, tmax, bn, bf);
const float la = ha ? bound(an, af, target) : best, lb = hb ? bound(bn, bf, target) : best;
// Push the less promising child first so the better one is visited next.
if (la < best && lb < best) {
if (sp + 2 > 64) continue;
if (la <= lb) {
stack[sp++] = n.index + 1;
stack[sp++] = n.index;
} else {
stack[sp++] = n.index;
stack[sp++] = n.index + 1;
}
} else if (la < best && sp < 64) {
stack[sp++] = n.index;
} else if (lb < best && sp < 64) {
stack[sp++] = n.index + 1;
}
}
return found;
}
// Any hit with t in [tmin, tmax].
bool occluded(const glm::vec3& o, const glm::vec3& d, float tmin, float tmax) const {
if (tris_.empty()) return false;
const glm::vec3 inv = invDir(d);
uint32_t stack[64];
int sp = 0;
stack[sp++] = 0;
float tn, tf;
while (sp) {
const Node& n = nodes_[stack[--sp]];
if (!slab(n, o, inv, tmin, tmax, tn, tf)) continue;
if (n.count) {
for (uint32_t i = n.index; i < n.index + n.count; ++i) {
float t, u, v;
if (intersect(tris_[i], o, d, t, u, v) && t >= tmin && t <= tmax) return true;
}
continue;
}
if (sp + 2 <= 64) {
stack[sp++] = n.index + 1;
stack[sp++] = n.index;
}
}
return false;
}
private:
static constexpr uint32_t kLeaf = 4;
static constexpr int kBins = 16;
struct Box {
glm::vec3 lo{std::numeric_limits<float>::max()}, hi{std::numeric_limits<float>::lowest()};
void grow(const glm::vec3& p) { lo = glm::min(lo, p), hi = glm::max(hi, p); }
void grow(const Box& b) { lo = glm::min(lo, b.lo), hi = glm::max(hi, b.hi); }
float area() const {
if (lo.x > hi.x) return 0.0f;
const glm::vec3 e = hi - lo;
return e.x * e.y + e.y * e.z + e.z * e.x;
}
};
struct Node {
glm::vec3 lo{0.0f};
uint32_t index = 0; // leaf: first triangle, inner: left child (right = index + 1)
glm::vec3 hi{0.0f};
uint32_t count = 0; // > 0 for leaves
};
struct Tri {
glm::vec3 v0, e1, e2;
};
bool split(uint32_t first, uint32_t count, const Box& nb, const Box& cb, const std::vector<Box>& box,
const std::vector<glm::vec3>& centroid, uint32_t& mid) {
float bestCost = std::numeric_limits<float>::max();
int bestAxis = -1, bestBin = 0;
const glm::vec3 ext = cb.hi - cb.lo;
for (int axis = 0; axis < 3; ++axis) {
if (ext[axis] <= 0.0f) continue;
Box bins[kBins];
uint32_t cnt[kBins] = {};
const float k = float(kBins) * 0.9999f / ext[axis];
for (uint32_t i = first; i < first + count; ++i) {
const int b = std::min(kBins - 1, int((centroid[order_[i]][axis] - cb.lo[axis]) * k));
bins[b].grow(box[order_[i]]);
++cnt[b];
}
float rightArea[kBins];
uint32_t rightCount[kBins];
Box acc;
uint32_t c = 0;
for (int b = kBins - 1; b > 0; --b) {
acc.grow(bins[b]);
c += cnt[b];
rightArea[b] = acc.area();
rightCount[b] = c;
}
acc = Box();
c = 0;
for (int b = 0; b < kBins - 1; ++b) {
acc.grow(bins[b]);
c += cnt[b];
if (!c || !rightCount[b + 1]) continue;
const float cost = acc.area() * float(c) + rightArea[b + 1] * float(rightCount[b + 1]);
if (cost < bestCost) {
bestCost = cost;
bestAxis = axis;
bestBin = b;
}
}
}
if (bestAxis < 0) { // all centroids in one spot: split in the middle of the list
if (count <= 16) return false;
mid = first + count / 2;
return true;
}
// A leaf costs about one intersection per triangle; stop when splitting doesn't pay.
if (count <= 8 && bestCost >= nb.area() * float(count)) return false;
const float k = float(kBins) * 0.9999f / ext[bestAxis];
auto* b = order_.data() + first;
auto* e = b + count;
auto* m = std::partition(b, e, [&](uint32_t t) {
return std::min(kBins - 1, int((centroid[t][bestAxis] - cb.lo[bestAxis]) * k)) <= bestBin;
});
mid = uint32_t(m - order_.data());
if (mid == first || mid == first + count) mid = first + count / 2;
return true;
}
static glm::vec3 invDir(const glm::vec3& d) {
auto inv = [](float x) { return std::abs(x) > 1e-20f ? 1.0f / x : (x < 0 ? -1e20f : 1e20f); };
return {inv(d.x), inv(d.y), inv(d.z)};
}
static bool slab(const Node& n, const glm::vec3& o, const glm::vec3& inv, float tmin, float tmax, float& tn, float& tf) {
const glm::vec3 t0 = (n.lo - o) * inv, t1 = (n.hi - o) * inv;
const glm::vec3 a = glm::min(t0, t1), b = glm::max(t0, t1);
tn = std::max(std::max(a.x, a.y), std::max(a.z, tmin));
tf = std::min(std::min(b.x, b.y), std::min(b.z, tmax));
return tn <= tf;
}
static float bound(float tn, float tf, float target) { return target < tn ? tn - target : target > tf ? target - tf : 0.0f; }
// Two-sided Moller-Trumbore.
static bool intersect(const Tri& tr, const glm::vec3& o, const glm::vec3& d, float& t, float& u, float& v) {
const glm::vec3 p = glm::cross(d, tr.e2);
const float det = glm::dot(tr.e1, p);
if (std::abs(det) < 1e-20f) return false;
const float inv = 1.0f / det;
const glm::vec3 s = o - tr.v0;
u = glm::dot(s, p) * inv;
if (u < 0.0f || u > 1.0f) return false;
const glm::vec3 q = glm::cross(s, tr.e1);
v = glm::dot(d, q) * inv;
if (v < 0.0f || u + v > 1.0f) return false;
t = glm::dot(tr.e2, q) * inv;
return true;
}
std::vector<Node> nodes_;
std::vector<uint32_t> order_;
std::vector<Tri> tris_;
};
} // namespace sf