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 "core/UploadOrder.h"
#include "core/AtomicRef.h"
#include "core/ThreadPool.h"
#include <algorithm>
#include <bit>
namespace sf {
namespace {
constexpr size_t kParallelDirtyVertices = 65536; // fewer: the serial walk, no threads woken
}
namespace {
// Mesh vertex -> local index within one cluster: an open-addressing table, cleared by bumping a stamp. Big
// enough for a cluster's worst case (3 distinct vertices per triangle) at under half load.
struct LocalMap {
static constexpr uint32_t kBits = 15, kSize = 1u << kBits;
std::vector<uint32_t> keys = std::vector<uint32_t>(kSize), stamps = std::vector<uint32_t>(kSize, 0);
std::vector<uint16_t> values = std::vector<uint16_t>(kSize);
uint32_t stamp = 0;
uint32_t count = 0;
void clear() {
if (++stamp == 0) {
std::fill(stamps.begin(), stamps.end(), 0);
stamp = 1;
}
count = 0;
}
// The local index of v, assigning the next one on first use (`isNew` says which).
uint16_t get(uint32_t v, bool& isNew) {
for (uint32_t h = (v * 0x9E3779B1u) >> (32 - kBits);; h = (h + 1) & (kSize - 1)) {
if (stamps[h] != stamp) {
stamps[h] = stamp;
keys[h] = v;
values[h] = uint16_t(count++);
isNew = true;
return values[h];
}
if (keys[h] == v) {
isNew = false;
return values[h];
}
}
}
};
LocalMap& localMap() {
thread_local LocalMap m;
return m;
}
// Calls fn(local, meshVertex, isNew) for every corner of cluster c's triangles in order.
template <class F>
void walkCluster(const Mesh& mesh, const UploadOrder& order, uint32_t c, F&& fn) {
LocalMap& map = localMap();
map.clear();
const uint32_t nv = uint32_t(mesh.vertexCount());
const uint32_t n = order.clusterTriangles(c);
for (uint32_t i = 0; i < n; ++i) {
const glm::uvec3& tri = mesh.triangles[order.triangle(c, i)];
const bool valid = tri.x < nv && tri.y < nv && tri.z < nv;
for (int k = 0; k < 3; ++k) {
if (!valid) {
fn(-1, 0u, false);
continue;
}
bool isNew = false;
const uint16_t local = map.get(tri[k], isNew);
fn(int(local), tri[k], isNew);
}
}
}
// Two 64-bit mixes for the closed check (murmur3's finaliser with different constants).
uint64_t mixA(uint64_t x) {
x ^= x >> 33;
x *= 0xFF51AFD7ED558CCDull;
return x ^ (x >> 33);
}
uint64_t mixB(uint64_t x) {
x ^= x >> 31;
x *= 0xC4CEB9FE1A85EC53ull;
return (x ^ (x >> 29)) | 1; // odd: w * b == 0 (mod 2^64) only when b == 0
}
// Sorts (key, value) pairs by key, keeping equal keys in order (LSD radix, 11 bits per pass).
template <class V>
void radixSortByKey(std::vector<std::pair<uint32_t, V>>& items, uint32_t maxKey) {
if (items.size() < 2) return;
std::vector<std::pair<uint32_t, V>> tmp(items.size());
constexpr uint32_t kDigit = 11, kBuckets = 1u << kDigit;
const int bits = std::max(1, int(std::bit_width(maxKey)));
std::vector<uint32_t> count(kBuckets);
for (int shift = 0; shift < bits; shift += int(kDigit)) {
std::fill(count.begin(), count.end(), 0);
for (const auto& e : items) ++count[(e.first >> shift) & (kBuckets - 1)];
uint32_t sum = 0;
for (uint32_t& n : count) sum += std::exchange(n, sum);
for (const auto& e : items) tmp[count[(e.first >> shift) & (kBuckets - 1)]++] = e;
items.swap(tmp);
}
}
// Spreads the low 10 bits of x to every third bit (Morton codes).
uint32_t spread3(uint32_t x) {
x &= 0x3FF;
x = (x | (x << 16)) & 0x030000FF;
x = (x | (x << 8)) & 0x0300F00F;
x = (x | (x << 4)) & 0x030C30C3;
x = (x | (x << 2)) & 0x09249249;
return x;
}
} // namespace
uint32_t UploadOrder::clusterOfSlot(uint32_t i) const {
const auto it = std::upper_bound(clusters_.begin(), clusters_.end(), i,
[](uint32_t s, const Cluster& c) { return s < c.firstVertex; });
return it == clusters_.begin() ? 0u : uint32_t(it - clusters_.begin() - 1);
}
void UploadOrder::build(const Mesh& mesh, const ClusterCallback& onCluster) {
triangles_ = mesh.triangleCount();
vertices_ = mesh.vertexCount();
// Chunks along a Morton curve of their centres (10 bits per axis over the mesh's bounds); a partial last
// chunk goes last, so every cluster but the last is made of whole chunks.
const size_t fullChunks = triangles_ >> kChunkShift, nChunks = (triangles_ + kChunkTriangles - 1) >> kChunkShift;
std::vector<AABB> boxes(fullChunks);
poolFor(fullChunks, [&](size_t k0, size_t k1) {
for (size_t k = k0; k < k1; ++k) {
AABB box;
for (size_t t = k << kChunkShift; t < (k + 1) << kChunkShift; ++t)
for (int c = 0; c < 3; ++c)
if (mesh.triangles[t][c] < vertices_) box.expand(mesh.positions[mesh.triangles[t][c]]);
boxes[k] = box;
}
}, 256);
AABB all;
for (const AABB& b : boxes)
if (b.valid()) all.expand(b);
std::vector<std::pair<uint32_t, uint32_t>> keyed(fullChunks);
const glm::vec3 lo = all.valid() ? all.min : glm::vec3(0.0f);
const glm::vec3 ext = all.valid() ? glm::max(all.extent(), glm::vec3(1e-30f)) : glm::vec3(1.0f);
poolFor(fullChunks, [&](size_t k0, size_t k1) {
for (size_t k = k0; k < k1; ++k) {
uint32_t code = 0;
if (boxes[k].valid()) {
const glm::vec3 q = glm::clamp((boxes[k].center() - lo) / ext, 0.0f, 1.0f) * 1023.0f;
code = spread3(uint32_t(q.x)) | (spread3(uint32_t(q.y)) << 1) | (spread3(uint32_t(q.z)) << 2);
}
keyed[k] = {code, uint32_t(k)};
}
}, 4096);
std::vector<AABB>().swap(boxes);
radixSortByKey(keyed, (1u << 30) - 1);
chunks_.resize(nChunks);
for (size_t k = 0; k < fullChunks; ++k) chunks_[k] = keyed[k].second;
if (nChunks > fullChunks) chunks_.back() = uint32_t(fullChunks);
const size_t nc = (nChunks + kClusterChunks - 1) / kClusterChunks;
clusters_.assign(nc, Cluster{});
for (size_t c = 0, first = 0; c < nc; ++c) {
const size_t endChunk = std::min(nChunks, (c + 1) * kClusterChunks);
const size_t count = std::min(triangles_, endChunk << kChunkShift) - (c * kClusterChunks << kChunkShift);
clusters_[c].firstTriangle = uint32_t(first);
clusters_[c].triangleCount = uint32_t(count);
first += count;
}
// Distinct vertices per cluster, then block-aligned ranges.
poolFor(nc, [&](size_t c0, size_t c1) {
for (size_t c = c0; c < c1; ++c) {
uint32_t n = 0;
walkCluster(mesh, *this, uint32_t(c), [&](int, uint32_t, bool isNew) { n += isNew; });
clusters_[c].vertexCount = n;
}
}, 1);
size_t slots = 0;
for (Cluster& c : clusters_) {
c.firstVertex = uint32_t(slots);
slots += (size_t(c.vertexCount) + kBlock - 1) & ~size_t(kBlock - 1);
}
// (Filled in parallel: these are tens of millions of entries.)
fromGpu_.resize(slots);
toGpu_.resize(vertices_);
poolFor(vertices_, [&](size_t b, size_t e) { std::fill(toGpu_.begin() + std::ptrdiff_t(b), toGpu_.begin() + std::ptrdiff_t(e), kNone); },
1 << 16);
// Closed: every vertex's outgoing and incoming neighbours are the same multiset, i.e. the sum over its
// corners of mixA(next) - mixA(previous) is 0. Weighted by mixB of the vertex and summed over the mesh, that
// is 0 for a closed mesh and, for any other, anything (0 by a 2^-64 chance).
std::vector<uint64_t> balances(nc, 0);
// Each cluster's vertices in first-use order; a vertex's first slot is the lowest (an atomic min, so the
// result doesn't depend on which thread gets there first).
poolFor(nc, [&](size_t c0, size_t c1) {
for (size_t c = c0; c < c1; ++c) {
const Cluster& cl = clusters_[c];
thread_local std::vector<uint16_t> locals;
locals.clear();
uint64_t balance = 0; // sum over corners a of mixB(a) * (mixA(next) - mixA(previous))
uint32_t corner[3];
int k = 0;
walkCluster(mesh, *this, uint32_t(c), [&](int local, uint32_t v, bool isNew) {
if (onCluster) locals.push_back(uint16_t(std::max(local, 0)));
corner[k] = v;
if (++k == 3) {
k = 0;
if (local >= 0) {
const uint64_t h0 = mixA(corner[0]), h1 = mixA(corner[1]), h2 = mixA(corner[2]);
balance += mixB(corner[0]) * (h1 - h2) + mixB(corner[1]) * (h2 - h0) + mixB(corner[2]) * (h0 - h1);
}
}
if (!isNew) return;
const uint32_t slot = cl.firstVertex + uint32_t(local);
fromGpu_[slot] = v;
AtomicRef<uint32_t> first(toGpu_[v]);
uint32_t cur = first.load(std::memory_order_relaxed);
while (slot < cur && !first.compare_exchange_weak(cur, slot, std::memory_order_relaxed)) {
}
});
if (onCluster) onCluster(uint32_t(c), locals.data());
balances[c] = balance;
const uint32_t padEnd = c + 1 < nc ? clusters_[c + 1].firstVertex : uint32_t(slots);
const uint32_t fill = cl.vertexCount ? fromGpu_[cl.firstVertex + cl.vertexCount - 1] : 0u;
std::fill(fromGpu_.begin() + cl.firstVertex + cl.vertexCount, fromGpu_.begin() + padEnd, fill);
}
}, 1);
// The other copies, by vertex (a stable sort of the slot-ordered list, so slots stay increasing).
copies_.clear();
hasCopy_.assign((vertices_ + 63) / 64, 0);
std::vector<std::vector<std::pair<uint32_t, uint32_t>>> perCluster(nc);
poolFor(nc, [&](size_t c0, size_t c1) {
for (size_t c = c0; c < c1; ++c) {
const Cluster& cl = clusters_[c];
for (uint32_t i = cl.firstVertex; i < cl.firstVertex + cl.vertexCount; ++i)
if (toGpu_[fromGpu_[i]] != i) perCluster[c].emplace_back(fromGpu_[i], i);
}
}, 16);
size_t copyCount = 0;
for (const auto& p : perCluster) copyCount += p.size();
std::vector<std::pair<uint32_t, uint32_t>> bySlot;
bySlot.reserve(copyCount);
for (auto& p : perCluster) {
bySlot.insert(bySlot.end(), p.begin(), p.end());
std::vector<std::pair<uint32_t, uint32_t>>().swap(p);
}
radixSortByKey(bySlot, uint32_t(vertices_));
for (const auto& e : bySlot) hasCopy_[e.first >> 6] |= uint64_t(1) << (e.first & 63);
uint64_t total = 0;
for (uint64_t b : balances) total += b;
closed_ = triangles_ > 0 && total == 0;
copies_ = std::move(bySlot);
marked_.assign((slots + kBlock - 1) / kBlock, 0);
blocks_.clear();
}
void UploadOrder::slotsOf(uint32_t v, std::vector<uint32_t>& out) const {
out.clear();
if (v >= toGpu_.size() || toGpu_[v] == kNone) return;
out.push_back(toGpu_[v]);
if (!((hasCopy_[v >> 6] >> (v & 63)) & 1)) return;
auto it = std::lower_bound(copies_.begin(), copies_.end(), std::make_pair(v, 0u));
for (; it != copies_.end() && it->first == v; ++it) out.push_back(it->second);
}
void UploadOrder::localTriangles(const Mesh& mesh, uint32_t c, uint16_t* out) const {
walkCluster(mesh, *this, c, [&](int local, uint32_t, bool) { *out++ = uint16_t(std::max(local, 0)); });
}
void UploadOrder::dirtyRuns(const Mesh& mesh, std::vector<std::pair<uint32_t, uint32_t>>& out) {
out.clear();
const uint32_t nv = uint32_t(std::min(mesh.vertexCount(), vertices_));
const uint32_t ns = uint32_t(fromGpu_.size());
const uint32_t end = std::min(mesh.dirtyEnd, nv);
if (mesh.dirtyBegin >= end || ns == 0) return;
const size_t firstBlock = mesh.dirtyBegin >> Mesh::kDirtyBlockShift;
const size_t lastBlock = std::min(mesh.dirtyBlocks.size(), size_t((end - 1) >> Mesh::kDirtyBlockShift) + 1);
constexpr size_t kWordsPerBlock = Mesh::kDirtyBlock / 64;
size_t dirty = 0;
for (size_t b = firstBlock; b < lastBlock; ++b)
if (mesh.dirtyBlocks[b])
for (size_t w = b * kWordsPerBlock; w < (b + 1) * kWordsPerBlock && w < mesh.dirtyBits.size(); ++w)
dirty += size_t(std::popcount(mesh.dirtyBits[w]));
if (dirty * 4 > nv * 3 || mesh.dirtyBits.size() * 64 < nv) {
// Most of the mesh (or no per-vertex marks): everything, in one go. (Above a quarter, as before, a large
// brush at 21M triangles re-packed the two thirds it hadn't touched every frame: 78 ms against 14-30.)
out.emplace_back(0, ns);
return;
}
auto mark = [&](uint32_t slot) {
const uint32_t g = slot >> kBlockShift;
if (!marked_[g]) {
marked_[g] = 1;
blocks_.push_back(g);
}
};
// The GPU blocks of every slot of every marked vertex. Many marks (a big brush, 3M vertices at 21M triangles:
// 3.7 ms on one thread): the mesh's dirty blocks in parallel, each GPU block flagged, then the flags read in
// order (the same sorted blocks).
if (dirty >= kParallelDirtyVertices) {
poolFor(lastBlock - firstBlock, [&](size_t b0, size_t b1) {
for (size_t b = firstBlock + b0; b < firstBlock + b1; ++b) {
if (!mesh.dirtyBlocks[b]) continue;
for (size_t w = b * kWordsPerBlock; w < (b + 1) * kWordsPerBlock && w < mesh.dirtyBits.size(); ++w) {
const uint64_t copies = w < hasCopy_.size() ? hasCopy_[w] : 0;
for (uint64_t bits = mesh.dirtyBits[w]; bits; bits &= bits - 1) {
const int bit = std::countr_zero(bits);
const size_t v = w * 64 + size_t(bit);
if (v >= nv) break;
if (toGpu_[v] == kNone) continue;
AtomicRef<uint8_t>(marked_[toGpu_[v] >> kBlockShift]).store(1, std::memory_order_relaxed);
if ((copies >> bit) & 1)
for (auto it = std::lower_bound(copies_.begin(), copies_.end(), std::make_pair(uint32_t(v), 0u));
it != copies_.end() && it->first == v; ++it)
AtomicRef<uint8_t>(marked_[it->second >> kBlockShift]).store(1, std::memory_order_relaxed);
}
}
}
}, 64);
for (uint32_t g = 0; g < uint32_t(marked_.size()); ++g)
if (marked_[g]) blocks_.push_back(g);
} else
for (size_t b = firstBlock; b < lastBlock; ++b) {
if (!mesh.dirtyBlocks[b]) continue;
for (size_t w = b * kWordsPerBlock; w < (b + 1) * kWordsPerBlock && w < mesh.dirtyBits.size(); ++w) {
const uint64_t copies = w < hasCopy_.size() ? hasCopy_[w] : 0;
for (uint64_t bits = mesh.dirtyBits[w]; bits; bits &= bits - 1) {
const int bit = std::countr_zero(bits);
const size_t v = w * 64 + size_t(bit);
if (v >= nv) break;
if (toGpu_[v] == kNone) continue;
mark(toGpu_[v]);
if ((copies >> bit) & 1)
for (auto it = std::lower_bound(copies_.begin(), copies_.end(), std::make_pair(uint32_t(v), 0u));
it != copies_.end() && it->first == v; ++it)
mark(it->second);
}
}
}
std::sort(blocks_.begin(), blocks_.end());
constexpr uint32_t kJoin = 4 * kBlock; // fewer, slightly longer uploads
for (uint32_t g : blocks_) {
marked_[g] = 0;
const uint32_t lo = g << kBlockShift, hi = std::min(ns, (g + 1) << kBlockShift);
if (!out.empty() && lo - out.back().second <= kJoin) out.back().second = hi;
else out.emplace_back(lo, hi);
}
blocks_.clear();
}
size_t UploadOrder::memoryBytes() const {
return (toGpu_.capacity() + fromGpu_.capacity() + blocks_.capacity()) * sizeof(uint32_t) + marked_.capacity() +
copies_.capacity() * sizeof(copies_[0]) + hasCopy_.capacity() * sizeof(uint64_t) + clusters_.capacity() * sizeof(Cluster) +
chunks_.capacity() * sizeof(uint32_t);
}
} // namespace sf