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
#include "render/Clusters.h"
#include "core/ThreadPool.h"
#include <algorithm>
#include <array>
#include <atomic>
#include <cmath>
#include <cstring>
#include <map>
#include <tuple>
#include <vector>
namespace sf {
PositionGrid PositionGrid::around(const AABB& box) {
PositionGrid g;
if (!box.valid()) return g;
const glm::vec3 e = box.extent();
const float size = std::max({e.x, e.y, e.z});
const float scale = std::max({std::abs(box.min.x), std::abs(box.min.y), std::abs(box.min.z), std::abs(box.max.x),
std::abs(box.max.y), std::abs(box.max.z), 1e-3f});
const float pad = std::max(size * 0.125f, scale * 1e-4f);
g.origin = box.min - glm::vec3(pad);
g.step = (size + 2.0f * pad) / float(kMax);
return g;
}
bool PositionGrid::contains(const glm::vec3& p) const {
const glm::vec3 q = (p - origin) / step;
return q.x >= 0.0f && q.y >= 0.0f && q.z >= 0.0f && q.x <= float(kMax) && q.y <= float(kMax) && q.z <= float(kMax);
}
namespace {
uint32_t quantize(float v, float origin, float step, bool& inside) {
const float q = std::round((v - origin) / step);
if (!(q >= 0.0f && q <= float(PositionGrid::kMax))) { // NaN too
inside = false;
return q > 0.0f ? PositionGrid::kMax : 0u;
}
return uint32_t(q);
}
uint32_t snorm(float v, int bits) {
const int range = (1 << (bits - 1)) - 1; // e.g. 11 bits: -1023..1023 stored as 1..2047, so 0 is exact
const int q = int(std::lround(std::clamp(v, -1.0f, 1.0f) * float(range)));
return uint32_t(q + range + 1);
}
float unsnorm(uint32_t q, int bits) {
const int range = (1 << (bits - 1)) - 1;
return float(int(q) - range - 1) / float(range);
}
} // namespace
bool packVertex(const PositionGrid& grid, const glm::vec3& p, const glm::vec3& n, float curvature, PackedVertex& out) {
bool inside = true;
const uint64_t x = quantize(p.x, grid.origin.x, grid.step, inside);
const uint64_t y = quantize(p.y, grid.origin.y, grid.step, inside);
const uint64_t z = quantize(p.z, grid.origin.z, grid.step, inside);
const uint64_t bits = x | (y << 21) | (z << 42);
out.pos[0] = uint32_t(bits);
out.pos[1] = uint32_t(bits >> 32);
// Octahedral normal: project onto |x| + |y| + |z| = 1, fold the lower half over the diagonals.
const float l1 = std::abs(n.x) + std::abs(n.y) + std::abs(n.z);
glm::vec2 e(0.0f);
if (l1 > 0.0f && std::isfinite(l1)) {
const glm::vec3 a = n / l1;
e = glm::vec2(a.x, a.y);
if (a.z < 0.0f)
e = glm::vec2((1.0f - std::abs(a.y)) * (a.x >= 0.0f ? 1.0f : -1.0f), (1.0f - std::abs(a.x)) * (a.y >= 0.0f ? 1.0f : -1.0f));
}
const float c = std::isfinite(curvature) ? std::clamp(curvature / kCurvatureRange, -1.0f, 1.0f) : 0.0f;
const float companded = c < 0.0f ? -std::sqrt(-c) : std::sqrt(c);
out.normal = snorm(e.x, 11) | (snorm(e.y, 11) << 11) | (snorm(companded, 10) << 22);
return inside;
}
glm::vec3 unpackPosition(const PositionGrid& grid, const PackedVertex& v) {
const uint64_t bits = uint64_t(v.pos[0]) | (uint64_t(v.pos[1]) << 32);
const glm::vec3 q(float(bits & 0x1FFFFF), float((bits >> 21) & 0x1FFFFF), float((bits >> 42) & 0x1FFFFF));
return grid.origin + q * grid.step;
}
glm::vec3 unpackNormal(const PackedVertex& v) {
const glm::vec2 e(unsnorm(v.normal & 2047u, 11), unsnorm((v.normal >> 11) & 2047u, 11));
glm::vec3 n(e.x, e.y, 1.0f - std::abs(e.x) - std::abs(e.y));
const float t = std::max(-n.z, 0.0f);
n.x += n.x >= 0.0f ? -t : t;
n.y += n.y >= 0.0f ? -t : t;
return glm::normalize(n);
}
float unpackCurvature(const PackedVertex& v) {
const float q = unsnorm(v.normal >> 22, 10);
return q * std::abs(q) * kCurvatureRange;
}
uint32_t packColor(const glm::vec3& c) {
static const std::vector<uint8_t> table = [] {
std::vector<uint8_t> t(65536);
for (size_t i = 0; i < t.size(); ++i) t[i] = uint8_t(std::lround(std::pow(double(i) / 65535.0, 1.0 / 2.2) * 255.0));
return t;
}();
auto ch = [&](float v) { return uint32_t(table[size_t(std::clamp(v, 0.0f, 1.0f) * 65535.0f + 0.5f)]); };
return ch(c.x) | (ch(c.y) << 8) | (ch(c.z) << 16) | (255u << 24);
}
ClusterBounds clusterBounds(const Mesh& mesh, const UploadOrder& order, uint32_t cluster) {
ClusterBounds b;
const size_t nv = mesh.vertexCount(), count = order.clusterTriangles(cluster);
const auto& P = mesh.positions;
thread_local std::vector<glm::vec3> normals; // unit face normals (zero: degenerate or invalid)
normals.resize(count);
AABB box;
glm::vec3 sum(0.0f);
for (uint32_t i = 0; i < count; ++i) {
const glm::uvec3& tri = mesh.triangles[order.triangle(cluster, i)];
glm::vec3& n = normals[i];
n = glm::vec3(0.0f);
if (tri.x >= nv || tri.y >= nv || tri.z >= nv) continue;
const glm::vec3 a = P[tri.x], e1 = P[tri.y] - a, e2 = P[tri.z] - a;
box.expand(a);
box.expand(P[tri.y]);
box.expand(P[tri.z]);
const glm::dvec3 da(a), db(P[tri.y]), dc(P[tri.z]);
b.volume += glm::dot(da, glm::cross(db, dc));
const glm::vec3 c = glm::cross(e1, e2);
const float l2 = glm::dot(c, c);
if (l2 > 0.0f && std::isfinite(l2)) {
n = c / std::sqrt(l2);
sum += n;
}
}
if (!box.valid()) return b;
b.center = box.center();
const float sl = glm::length(sum);
const glm::vec3 axis = sl > 1e-6f ? sum / sl : glm::vec3(0.0f);
float r2 = 0.0f, minDot = 1.0f;
bool faces = false;
for (uint32_t i = 0; i < count; ++i) {
const glm::vec3& n = normals[i];
const glm::uvec3& tri = mesh.triangles[order.triangle(cluster, i)];
if (n.x == 0.0f && n.y == 0.0f && n.z == 0.0f) {
if (tri.x >= nv || tri.y >= nv || tri.z >= nv) continue;
} else {
minDot = std::min(minDot, glm::dot(n, axis));
faces = true;
}
for (int c = 0; c < 3; ++c) {
const glm::vec3 d = P[tri[c]] - b.center;
r2 = std::max(r2, glm::dot(d, d));
}
}
// A little slack for float rounding and the GPU's quantised positions.
b.radius = std::sqrt(r2) * 1.0001f + 1e-6f;
if (faces && sl > 1e-6f && minDot > 0.0f) {
b.axis = axis;
b.coneAngle = std::acos(std::min(minDot, 1.0f));
}
return b;
}
namespace {
// Cell -> its representative: an open-addressing table cleared by a stamp (a cluster has at most 3 vertices
// per triangle, so 2^15 slots stay under half full).
struct CellTable {
static constexpr uint32_t kBits = 15, kSize = 1u << kBits;
std::vector<uint64_t> keys = std::vector<uint64_t>(kSize);
std::vector<uint32_t> stamps = std::vector<uint32_t>(kSize, 0);
std::vector<uint16_t> reps = std::vector<uint16_t>(kSize);
std::vector<float> dists = std::vector<float>(kSize);
uint32_t stamp = 0;
void clear() {
if (++stamp == 0) {
std::fill(stamps.begin(), stamps.end(), 0);
stamp = 1;
}
}
uint32_t slot(uint64_t key, bool& found) {
for (uint32_t h = uint32_t((key * 0x9E3779B97F4A7C15ull) >> (64 - kBits));; h = (h + 1) & (kSize - 1)) {
if (stamps[h] != stamp) {
found = false;
return h;
}
if (keys[h] == key) {
found = true;
return h;
}
}
}
};
} // namespace
bool clusterProxy(const Mesh& mesh, const UploadOrder& order, uint32_t c, size_t maxTriangles, std::vector<uint16_t>& out,
ClusterBounds& bounds) {
out.clear();
const uint32_t n = order.clusterTriangles(c);
const UploadOrder::Cluster& cl = order.clusters()[c];
const auto fromGpu = order.fromGpu();
thread_local std::vector<uint16_t> local, rep;
thread_local std::vector<uint8_t> pinned;
local.resize(size_t(n) * 3);
order.localTriangles(mesh, c, local.data());
const uint32_t nl = cl.vertexCount;
pinned.assign(nl, 0);
AABB box;
for (uint32_t l = 0; l < nl; ++l) {
const uint32_t v = fromGpu[cl.firstVertex + l];
pinned[l] = order.shared(v);
box.expand(mesh.positions[v]);
}
auto pos = [&](uint32_t l) { return mesh.positions[fromGpu[cl.firstVertex + l]]; };
const bool hidden = mesh.hidden.size() == mesh.triangleCount();
double edges = 0.0;
size_t counted = 0;
for (uint32_t i = 0; i < n; i += 7) { // a sample is plenty
const uint16_t* t = local.data() + size_t(i) * 3;
edges += glm::distance(pos(t[0]), pos(t[1])) + glm::distance(pos(t[1]), pos(t[2]));
counted += 2;
}
if (!counted || !box.valid()) return false;
float cell = float(edges / double(counted)) * 2.5f;
if (!(cell > 0.0f)) return false;
thread_local CellTable cells;
thread_local std::vector<uint32_t> cellOfVertex;
cellOfVertex.resize(nl);
rep.resize(nl);
for (int attempt = 0; attempt < 4; ++attempt, cell *= 1.6f) {
cells.clear();
const float inv = 1.0f / cell;
for (uint32_t l = 0; l < nl; ++l) {
if (pinned[l]) continue;
const glm::vec3 p = pos(l);
const glm::vec3 q = glm::floor((p - box.min) * inv);
const glm::vec3 centre = box.min + (q + 0.5f) * cell;
const uint64_t key = uint64_t(uint32_t(q.x)) | (uint64_t(uint32_t(q.y)) << 21) | (uint64_t(uint32_t(q.z)) << 42);
const float d = glm::distance(p, centre);
bool found = false;
const uint32_t h = cells.slot(key, found);
if (!found) {
cells.stamps[h] = cells.stamp;
cells.keys[h] = key;
cells.reps[h] = uint16_t(l);
cells.dists[h] = d;
} else if (d < cells.dists[h]) {
cells.reps[h] = uint16_t(l);
cells.dists[h] = d;
}
cellOfVertex[l] = h;
}
for (uint32_t l = 0; l < nl; ++l) rep[l] = pinned[l] ? uint16_t(l) : cells.reps[cellOfVertex[l]];
out.clear();
for (uint32_t i = 0; i < n; ++i) {
if (hidden && mesh.hidden[order.triangle(c, i)]) continue;
const uint16_t* t = local.data() + size_t(i) * 3;
const uint16_t a = rep[t[0]], b = rep[t[1]], d = rep[t[2]];
if (a == b || b == d || a == d) continue;
out.insert(out.end(), {a, b, d});
}
if (out.size() / 3 <= maxTriangles) break;
}
if (out.size() / 3 > maxTriangles) {
out.clear();
return false;
}
// The proxy's own normal cone (its triangles lean differently from the cluster's).
glm::vec3 sum(0.0f);
float minDot = 1.0f;
bool faces = false;
thread_local std::vector<glm::vec3> normals;
normals.resize(out.size() / 3);
for (size_t i = 0; i < normals.size(); ++i) {
const glm::vec3 p0 = pos(out[i * 3]);
const glm::vec3 cr = glm::cross(pos(out[i * 3 + 1]) - p0, pos(out[i * 3 + 2]) - p0);
const float l2 = glm::dot(cr, cr);
normals[i] = l2 > 0.0f && std::isfinite(l2) ? cr / std::sqrt(l2) : glm::vec3(0.0f);
sum += normals[i];
}
const float sl = glm::length(sum);
for (const glm::vec3& nn : normals)
if (nn != glm::vec3(0.0f) && sl > 1e-6f) {
minDot = std::min(minDot, glm::dot(nn, sum / sl));
faces = true;
}
bounds.axis = glm::vec3(0.0f, 0.0f, 1.0f);
bounds.coneAngle = -1.0f;
if (faces && minDot > 0.0f) {
bounds.axis = sum / sl;
bounds.coneAngle = std::acos(std::min(minDot, 1.0f));
}
return true;
}
namespace {
uint64_t packCell(glm::uvec3 q) { return uint64_t(q.x) | (uint64_t(q.y) << 21) | (uint64_t(q.z) << 42); }
uint64_t cellKey(const CoarseLevels& L, const glm::vec3& p, int level) {
const float size = L.cell * float(1u << level);
const glm::vec3 q = glm::clamp(glm::floor((p - L.origin) / size), glm::vec3(0.0f), glm::vec3(float(0x1FFFFF)));
return packCell(glm::uvec3(q));
}
// Sorts keys in parallel blocks, merged pairwise.
void parallelSort(std::vector<uint64_t>& v) {
const size_t blocks = 16, n = v.size(), step = (n + blocks - 1) / blocks;
if (n < 65536) {
std::sort(v.begin(), v.end());
return;
}
auto at = [&](size_t i) { return v.begin() + std::ptrdiff_t(std::min(n, i)); };
poolFor(blocks, [&](size_t b0, size_t b1) {
for (size_t b = b0; b < b1; ++b) std::sort(at(b * step), at((b + 1) * step));
}, 1, 1);
for (size_t width = step; width < n; width *= 2)
poolFor((n + 2 * width - 1) / (2 * width), [&](size_t p0, size_t p1) {
for (size_t p = p0; p < p1; ++p) std::inplace_merge(at(p * 2 * width), at(p * 2 * width + width), at(p * 2 * width + 2 * width));
}, 1, 1);
}
// Cluster c's triangles on the cells of `level` (degenerate and repeated ones dropped) and its error; false: a
// vertex is in no cell of the build.
bool clusterOnCells(const CoarseLevels& L, const Mesh& mesh, const UploadOrder& order, uint32_t c, int level,
std::vector<std::array<uint32_t, 3>>& tris, float& error) {
const size_t nv = mesh.vertexCount(), nt = mesh.triangleCount();
const bool hidden = mesh.hidden.size() == nt;
tris.clear();
error = 0.0f;
const uint32_t n = order.clusterTriangles(c);
for (uint32_t i = 0; i < n; ++i) {
const uint32_t t = order.triangle(c, i);
if (t >= nt || (hidden && mesh.hidden[t])) continue;
const glm::uvec3 tri = mesh.triangles[t];
if (tri.x >= nv || tri.y >= nv || tri.z >= nv) continue;
std::array<uint32_t, 3> m;
for (int k = 0; k < 3; ++k) {
const glm::vec3& p = mesh.positions[tri[k]];
m[size_t(k)] = L.cellOf(p, level);
if (m[size_t(k)] == ~0u) return false;
error = std::max(error, glm::distance(p, L.positions[m[size_t(k)]]));
}
if (m[0] == m[1] || m[1] == m[2] || m[0] == m[2]) continue;
std::rotate(m.begin(), std::min_element(m.begin(), m.end()), m.end()); // (one rotation per triangle)
tris.push_back(m);
}
std::sort(tris.begin(), tris.end());
tris.erase(std::unique(tris.begin(), tris.end()), tris.end());
return true;
}
} // namespace
uint32_t CoarseLevels::cellOf(const glm::vec3& p, int level) const {
const Level& l = levels[size_t(level)];
const uint64_t key = cellKey(*this, p, level);
const auto it = std::lower_bound(l.keys.begin(), l.keys.end(), key);
return it != l.keys.end() && *it == key ? l.base + uint32_t(it - l.keys.begin()) : ~0u;
}
CoarseLevels buildCoarseLevels(const Mesh& mesh, const UploadOrder& order) {
CoarseLevels L;
const size_t nv = mesh.vertexCount(), nt = mesh.triangleCount();
const uint32_t nc = uint32_t(order.clusters().size());
L.clusters.resize(nc);
if (nv == 0 || nt == 0 || nc == 0) return L;
AABB box;
for (const glm::vec3& p : mesh.positions) box.expand(p);
double edges = 0.0;
size_t counted = 0;
for (size_t t = 0; t < nt; t += std::max<size_t>(1, nt / 200000)) {
const glm::uvec3 tri = mesh.triangles[t];
if (tri.x >= nv || tri.y >= nv || tri.z >= nv) continue;
edges += glm::distance(mesh.positions[tri.x], mesh.positions[tri.y]) + glm::distance(mesh.positions[tri.y], mesh.positions[tri.z]);
counted += 2;
}
if (!counted || !box.valid()) return L;
L.cell = float(edges / double(counted)) * 4.0f;
if (!(L.cell > 0.0f)) return L;
// Room on the grid for the mesh to move a little (as PositionGrid's margin).
L.origin = box.min - (box.max - box.min) * 0.125f - glm::vec3(L.cell);
const bool hasNormals = mesh.normals.size() == nv;
// The cells of each level: the sorted keys of the vertices' cells, each once.
std::vector<uint32_t> cellOfVertex(nv);
for (int level = 0; level < CoarseLevels::kMaxLevels; ++level) {
CoarseLevels::Level& lv = L.levels.emplace_back();
lv.base = uint32_t(L.positions.size());
{
std::vector<uint64_t> keys;
if (level == 0) {
keys.resize(nv);
poolFor(nv, [&](size_t v0, size_t v1) {
for (size_t v = v0; v < v1; ++v) keys[v] = cellKey(L, mesh.positions[v], 0);
});
} else {
keys.reserve(L.levels[size_t(level) - 1].keys.size());
for (uint64_t k : L.levels[size_t(level) - 1].keys) // (nested: each axis index halves)
keys.push_back(packCell(glm::uvec3(uint32_t(k & 0x1FFFFF), uint32_t((k >> 21) & 0x1FFFFF), uint32_t(k >> 42)) / 2u));
}
parallelSort(keys);
keys.erase(std::unique(keys.begin(), keys.end()), keys.end());
lv.keys.assign(keys.begin(), keys.end()); // (exact size)
}
const size_t cells = lv.keys.size();
poolFor(nv, [&](size_t v0, size_t v1) {
for (size_t v = v0; v < v1; ++v) cellOfVertex[v] = L.cellOf(mesh.positions[v], level) - lv.base;
});
std::vector<glm::dvec3> sum(cells, glm::dvec3(0.0));
std::vector<glm::vec3> nsum(cells, glm::vec3(0.0f));
std::vector<uint32_t> weight(cells, 0);
for (size_t v = 0; v < nv; ++v) {
const uint32_t k = cellOfVertex[v];
sum[k] += glm::dvec3(mesh.positions[v]);
if (hasNormals) nsum[k] += mesh.normals[v];
++weight[k];
}
for (size_t k = 0; k < cells; ++k) {
L.positions.push_back(glm::vec3(sum[k] / double(std::max(weight[k], 1u))));
const float l = glm::length(nsum[k]);
L.normals.push_back(l > 1e-12f ? nsum[k] / l : glm::vec3(0.0f, 0.0f, 1.0f));
}
if (cells < 64) break;
}
cellOfVertex = {};
// Membership (the build's, kept): each vertex's level-0 cell, each level-0 cell's vertices, the parents and
// children up the levels, and the weights.
const uint32_t cells0 = uint32_t(L.levels[0].keys.size()), base0 = L.levels[0].base, cellCount = uint32_t(L.positions.size());
L.vertexCell.resize(nv);
poolFor(nv, [&](size_t v0, size_t v1) {
for (size_t v = v0; v < v1; ++v) L.vertexCell[v] = L.cellOf(mesh.positions[v], 0);
});
L.memberFirst.assign(size_t(cells0) + 1, 0);
for (uint32_t k : L.vertexCell) ++L.memberFirst[k - base0 + 1];
for (uint32_t k = 0; k < cells0; ++k) L.memberFirst[k + 1] += L.memberFirst[k];
L.members.resize(nv);
{
std::vector<uint32_t> at(L.memberFirst.begin(), L.memberFirst.end() - 1);
for (uint32_t v = 0; v < uint32_t(nv); ++v) L.members[at[L.vertexCell[v] - base0]++] = v;
}
L.parent.assign(cellCount, ~0u);
L.weight.assign(cellCount, 0);
for (uint32_t k = 0; k < cells0; ++k) L.weight[base0 + k] = L.memberFirst[k + 1] - L.memberFirst[k];
for (size_t level = 0; level + 1 < L.levels.size(); ++level) {
const CoarseLevels::Level& lv = L.levels[level];
const CoarseLevels::Level& up = L.levels[level + 1];
for (size_t i = 0; i < lv.keys.size(); ++i) {
const uint64_t k = lv.keys[i];
const uint64_t pk = packCell(glm::uvec3(uint32_t(k & 0x1FFFFF), uint32_t((k >> 21) & 0x1FFFFF), uint32_t(k >> 42)) / 2u);
const auto it = std::lower_bound(up.keys.begin(), up.keys.end(), pk);
if (it == up.keys.end() || *it != pk) continue;
const uint32_t child = lv.base + uint32_t(i), par = up.base + uint32_t(it - up.keys.begin());
L.parent[child] = par;
L.weight[par] += L.weight[child];
}
}
L.childFirst.assign(size_t(cellCount) + 1, 0);
for (uint32_t k = 0; k < cellCount; ++k)
if (L.parent[k] != ~0u) ++L.childFirst[L.parent[k] + 1];
for (uint32_t k = 0; k < cellCount; ++k) L.childFirst[k + 1] += L.childFirst[k];
L.children.resize(L.childFirst[cellCount]);
{
std::vector<uint32_t> at(L.childFirst.begin(), L.childFirst.end() - 1);
for (uint32_t k = 0; k < cellCount; ++k)
if (L.parent[k] != ~0u) L.children[at[L.parent[k]]++] = k;
}
coarseAttributes(L, mesh);
// Per cluster, its levels while they pay.
std::vector<std::vector<uint32_t>> lists(nc);
poolFor(nc, [&](size_t c0, size_t c1) {
std::vector<std::array<uint32_t, 3>> tris;
for (size_t c = c0; c < c1; ++c) {
CoarseLevels::Lod& lod = L.clusters[c];
size_t previous = order.clusterTriangles(uint32_t(c));
for (int level = 0; level < int(L.levels.size()); ++level) {
float error = 0.0f;
if (!clusterOnCells(L, mesh, order, uint32_t(c), level, tris, error)) break; // (every level: one is drawn for all)
lod.first[lod.levels] = uint32_t(lists[c].size());
lod.count[lod.levels] = uint32_t(tris.size() * 3);
lod.error[lod.levels] = std::max(error, lod.levels > 0 ? lod.error[lod.levels - 1] : 0.0f);
++lod.levels;
for (const auto& m : tris) lists[c].insert(lists[c].end(), m.begin(), m.end());
previous = tris.size();
}
lists[c].shrink_to_fit();
}
}, 16, 1);
size_t total = 0;
for (const auto& l : lists) total += l.size();
L.indices.reserve(total);
for (uint32_t c = 0; c < nc; ++c) {
const uint32_t at = uint32_t(L.indices.size());
for (int l = 0; l < L.clusters[c].levels; ++l) L.clusters[c].first[l] += at;
L.indices.insert(L.indices.end(), lists[c].begin(), lists[c].end());
std::vector<uint32_t>().swap(lists[c]);
}
return L;
}
std::vector<uint32_t> updateCoarseLevels(CoarseLevels& L, const Mesh& mesh, const UploadOrder& order,
const std::vector<uint32_t>& dirty) {
std::vector<uint32_t> changed;
const size_t nv = mesh.vertexCount();
if (L.levels.empty() || dirty.empty() || L.vertexCell.size() != nv) return changed;
const auto fromGpu = order.fromGpu();
const uint32_t base0 = L.levels[0].base;
// The level-0 cells of the dirty clusters' vertices (the build's cells: membership doesn't change).
const size_t cells0 = L.levels[0].keys.size();
std::vector<uint8_t> flagged(cells0, 0);
poolFor(dirty.size(), [&](size_t d0, size_t d1) {
for (size_t d = d0; d < d1; ++d) {
const auto& cl = order.clusters()[dirty[d]];
for (uint32_t l = 0; l < cl.vertexCount; ++l)
if (const uint32_t v = fromGpu[cl.firstVertex + l]; v < nv)
std::atomic_ref<uint8_t>(flagged[L.vertexCell[v] - base0]).store(1, std::memory_order_relaxed);
}
}, 16);
std::vector<uint32_t> cells;
for (size_t k = 0; k < cells0; ++k)
if (flagged[k]) cells.push_back(base0 + uint32_t(k));
const bool hasNormals = mesh.normals.size() == nv;
// Each one the mean of its vertices where they are now; then each level's cells above them from their children.
poolFor(cells.size(), [&](size_t i0, size_t i1) {
for (size_t i = i0; i < i1; ++i) {
const uint32_t k = cells[i] - base0;
glm::dvec3 sum(0.0);
glm::vec3 nsum(0.0f);
for (uint32_t m = L.memberFirst[k]; m < L.memberFirst[k + 1]; ++m) {
sum += glm::dvec3(mesh.positions[L.members[m]]);
if (hasNormals) nsum += mesh.normals[L.members[m]];
}
const uint32_t w = L.memberFirst[k + 1] - L.memberFirst[k];
if (w) L.positions[cells[i]] = glm::vec3(sum / double(w));
const float l = glm::length(nsum);
if (l > 1e-12f) L.normals[cells[i]] = nsum / l;
}
}, 1024);
changed = cells;
coarseAttributes(L, mesh, cells);
for (size_t level = 1; level < L.levels.size() && !cells.empty(); ++level) {
std::vector<uint32_t> up;
up.reserve(cells.size());
for (uint32_t k : cells)
if (L.parent[k] != ~0u) up.push_back(L.parent[k]);
std::sort(up.begin(), up.end());
up.erase(std::unique(up.begin(), up.end()), up.end());
poolFor(up.size(), [&](size_t i0, size_t i1) {
for (size_t i = i0; i < i1; ++i) {
const uint32_t p = up[i];
glm::dvec3 sum(0.0);
glm::vec3 nsum(0.0f);
for (uint32_t j = L.childFirst[p]; j < L.childFirst[p + 1]; ++j) {
const uint32_t ch = L.children[j];
sum += glm::dvec3(L.positions[ch]) * double(L.weight[ch]);
nsum += L.normals[ch] * float(L.weight[ch]);
}
if (L.weight[p]) L.positions[p] = glm::vec3(sum / double(L.weight[p]));
const float l = glm::length(nsum);
if (l > 1e-12f) L.normals[p] = nsum / l;
}
}, 1024);
changed.insert(changed.end(), up.begin(), up.end());
cells = std::move(up);
}
return changed;
}
bool coarseAttributesMatch(const CoarseLevels& L, const Mesh& mesh) {
const size_t nv = mesh.vertexCount();
return (nv > 0 && mesh.colors.size() == nv) == !L.colors.empty() && (nv > 0 && mesh.mask.size() == nv) == !L.mask.empty();
}
double nextGpuMsPerTriangle(double estimate, double gpuMs, double cpuBeforeDrawMs, uint64_t triangles) {
const double drawMs = gpuMs - std::max(cpuBeforeDrawMs, 0.0);
if (!(drawMs > 0.2) || triangles < 500000) return estimate; // (small frames are mostly fixed costs)
double v = drawMs / double(triangles);
// (A frame whose GPU time can't hold those triangles didn't draw them: UI tests draw the 3D view only for their
// shots, the timer measures every frame. More than 1e11 triangles a second is no measurement.)
if (v < 1e-8) return estimate;
if (!(estimate > 0.0)) return v;
v = std::min(v, 4.0 * estimate);
return 0.8 * estimate + 0.2 * v;
}
void coarseAttributes(CoarseLevels& L, const Mesh& mesh, std::vector<uint32_t> cells) {
const size_t nv = mesh.vertexCount(), count = L.positions.size();
if (L.levels.empty() || L.vertexCell.size() != nv) return;
const bool colors = nv > 0 && mesh.colors.size() == nv, mask = nv > 0 && mesh.mask.size() == nv;
if (!colors && !mask) {
std::vector<glm::vec3>().swap(L.colors);
std::vector<float>().swap(L.mask);
return;
}
const uint32_t base0 = L.levels[0].base, cells0 = uint32_t(L.levels[0].keys.size());
if (!coarseAttributesMatch(L, mesh)) cells.clear(); // (every cell's)
if (cells.empty()) {
cells.resize(cells0);
for (uint32_t k = 0; k < cells0; ++k) cells[k] = base0 + k;
}
if (colors) L.colors.resize(count, glm::vec3(1.0f));
else std::vector<glm::vec3>().swap(L.colors);
if (mask) L.mask.resize(count, 0.0f);
else std::vector<float>().swap(L.mask);
poolFor(cells.size(), [&](size_t i0, size_t i1) {
for (size_t i = i0; i < i1; ++i) {
const uint32_t k = cells[i] - base0;
glm::vec3 csum(0.0f);
float msum = 0.0f;
for (uint32_t m = L.memberFirst[k]; m < L.memberFirst[k + 1]; ++m) {
if (colors) csum += mesh.colors[L.members[m]];
if (mask) msum += mesh.mask[L.members[m]];
}
const float w = float(std::max(L.memberFirst[k + 1] - L.memberFirst[k], 1u));
if (colors) L.colors[cells[i]] = csum / w;
if (mask) L.mask[cells[i]] = msum / w;
}
}, 1024);
for (size_t level = 1; level < L.levels.size() && !cells.empty(); ++level) {
std::vector<uint32_t> up;
up.reserve(cells.size());
for (uint32_t k : cells)
if (L.parent[k] != ~0u) up.push_back(L.parent[k]);
std::sort(up.begin(), up.end());
up.erase(std::unique(up.begin(), up.end()), up.end());
poolFor(up.size(), [&](size_t i0, size_t i1) {
for (size_t i = i0; i < i1; ++i) {
const uint32_t p = up[i];
glm::vec3 csum(0.0f);
float msum = 0.0f;
for (uint32_t j = L.childFirst[p]; j < L.childFirst[p + 1]; ++j) {
const uint32_t ch = L.children[j];
if (colors) csum += L.colors[ch] * float(L.weight[ch]);
if (mask) msum += L.mask[ch] * float(L.weight[ch]);
}
const float w = float(std::max(L.weight[p], 1u));
if (colors) L.colors[p] = csum / w;
if (mask) L.mask[p] = msum / w;
}
}, 1024);
cells = std::move(up);
}
}
bool closedOriented(const Mesh& mesh) {
const size_t nv = mesh.vertexCount(), nt = mesh.triangleCount();
if (nt == 0) return false;
// Directed edges out of and into vertex a (to the next and from the previous corner of each triangle).
auto fan = [&](uint32_t a, std::vector<uint32_t>& outs, std::vector<uint32_t>& ins) {
for (uint32_t t : mesh.vertexTriangles(a)) {
if (t >= nt) continue;
const glm::uvec3& tri = mesh.triangles[t];
for (int c = 0; c < 3; ++c)
if (tri[c] == a) {
outs.push_back(tri[(c + 1) % 3]);
ins.push_back(tri[(c + 2) % 3]);
}
}
};
// The vertices whose edges don't pair up: compared as sums of a 64-bit hash of the neighbour (no sorting;
// equal multisets give equal sums, and unequal ones colliding is a 2^-64 chance).
auto hash = [](uint64_t x) {
x += 0x9E3779B97F4A7C15ull;
x = (x ^ (x >> 30)) * 0xBF58476D1CE4E5B9ull;
x = (x ^ (x >> 27)) * 0x94D049BB133111EBull;
return x ^ (x >> 31);
};
constexpr size_t kBlock = 1 << 14;
std::vector<std::vector<uint32_t>> open((nv + kBlock - 1) / kBlock);
std::atomic<size_t> openCount{0};
const size_t limit = std::max<size_t>(64, nv / 100);
poolFor(nv, [&](size_t v0, size_t v1) {
std::vector<uint32_t>& list = open[v0 / kBlock];
for (size_t a = v0; a < v1 && openCount.load(std::memory_order_relaxed) <= limit; ++a) {
uint64_t sum = 0;
for (uint32_t t : mesh.vertexTriangles(uint32_t(a))) {
if (t >= nt) continue;
const glm::uvec3& tri = mesh.triangles[t];
for (int c = 0; c < 3; ++c)
if (tri[c] == a) sum += hash(tri[(c + 1) % 3]) - hash(tri[(c + 2) % 3]);
}
if (sum != 0) {
list.push_back(uint32_t(a));
openCount.fetch_add(1, std::memory_order_relaxed);
}
}
}, kBlock);
if (openCount.load() == 0) return true;
if (openCount.load() > limit) return false;
// A few: maybe a seam of unwelded vertices (the same position twice), which is closed all the same. Count
// vertices at one position as one (the lowest id) and check each such group's edges together.
struct Key {
uint32_t x, y, z;
bool operator<(const Key& o) const { return std::tie(x, y, z) < std::tie(o.x, o.y, o.z); }
};
auto keyOf = [&](uint32_t v) {
Key k{};
std::memcpy(&k.x, &mesh.positions[v].x, 4);
std::memcpy(&k.y, &mesh.positions[v].y, 4);
std::memcpy(&k.z, &mesh.positions[v].z, 4);
return k;
};
std::map<Key, uint32_t> canonical;
std::vector<uint32_t> outs, ins;
auto note = [&](uint32_t v) {
auto [it, added] = canonical.emplace(keyOf(v), v);
if (!added) it->second = std::min(it->second, v);
};
for (const auto& list : open)
for (uint32_t a : list) {
note(a);
outs.clear();
ins.clear();
fan(a, outs, ins);
for (uint32_t u : outs) note(u);
for (uint32_t u : ins) note(u);
}
std::map<uint32_t, std::pair<std::vector<uint32_t>, std::vector<uint32_t>>> groups;
for (const auto& list : open)
for (uint32_t a : list) {
auto& [go, gi] = groups[canonical.at(keyOf(a))];
outs.clear();
ins.clear();
fan(a, outs, ins);
for (uint32_t u : outs) go.push_back(canonical.at(keyOf(u)));
for (uint32_t u : ins) gi.push_back(canonical.at(keyOf(u)));
}
for (auto& [id, g] : groups) {
std::sort(g.first.begin(), g.first.end());
std::sort(g.second.begin(), g.second.end());
if (g.first != g.second) return false;
}
return true;
}
CullView CullView::from(const glm::mat4& view, const glm::mat4& proj) {
CullView v;
const glm::mat4 m = proj * view;
auto row = [&](int i) { return glm::vec4(m[0][i], m[1][i], m[2][i], m[3][i]); };
const glm::vec4 r0 = row(0), r1 = row(1), r2 = row(2), r3 = row(3);
const std::array<glm::vec4, 6> p = {r3 + r0, r3 - r0, r3 + r1, r3 - r1, r3 + r2, r3 - r2};
for (int i = 0; i < 6; ++i) {
const float l = glm::length(glm::vec3(p[size_t(i)]));
v.planes[i] = l > 0.0f ? p[size_t(i)] / l : glm::vec4(0.0f, 0.0f, 0.0f, 1.0f);
}
const glm::mat4 inv = glm::inverse(view);
v.eye = glm::vec3(inv[3]);
v.forward = glm::normalize(glm::vec3(inv * glm::vec4(0.0f, 0.0f, -1.0f, 0.0f)));
v.ortho = proj[3][3] == 1.0f && proj[2][3] == 0.0f;
v.nearDistance = std::abs(proj[2][2] - 1.0f) > 1e-12f ? proj[3][2] / (proj[2][2] - 1.0f) : 0.0f;
return v;
}
bool insideFrustum(const CullView& v, const ClusterBounds& b) {
if (b.radius < 0.0f) return false;
for (const glm::vec4& p : v.planes)
if (glm::dot(glm::vec3(p), b.center) + p.w < -b.radius) return false;
return true;
}
bool facingAway(const CullView& v, const ClusterBounds& b) {
if (!v.backfaces || b.coneAngle < 0.0f) return false;
const glm::vec3 d = b.center - v.eye;
const float dist = glm::length(d);
if (!(dist > b.radius * 1.001f)) return false;
// Every normal is within coneAngle of the axis, every direction from the eye to the cluster within
// asin(r / dist) of the centre's: faces point away when the three angles stay under 90 degrees.
const float gamma = std::acos(std::clamp(glm::dot(d / dist, b.axis), -1.0f, 1.0f));
const float beta = std::asin(std::min(1.0f, b.radius / dist));
constexpr float kMargin = 0.02f; // radians
return gamma + beta + b.coneAngle < 1.5707963f - kMargin;
}
} // namespace sf