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
#pragma once
#include "core/IndexBits.h"
#include "core/Mesh.h"
#include <functional>
#include <span>
#include <vector>
namespace sf {
struct RayHit {
float t = 0.0f;
uint32_t triangle = 0;
glm::vec3 position{0.0f};
glm::vec3 normal{0.0f}; // geometric normal of the hit triangle
};
// Bounding volume hierarchy over a mesh's triangles. Supports ray casts,
// sphere queries for brushes, and cheap incremental refits while sculpting.
class BVH {
public:
void build(const Mesh& mesh);
// Nearest hit along the ray; hidden triangles (Mesh::hidden) are skipped.
bool raycast(const Mesh& mesh, const glm::vec3& origin, const glm::vec3& dir, RayHit& hit) const;
// Appends every vertex within `radius` of `center` to `out` (cleared first), in increasing index order.
// Ignores visibility; brushes use sf::brushVertices, which filters hidden ones.
void queryVertices(const Mesh& mesh, const glm::vec3& center, float radius, std::vector<uint32_t>& out) const;
// queryVertices for an infinite cylinder: every vertex within `radius` of the line through `point` along
// `axis` (a brush whose falloff is measured on screen reaches through the model along the view).
void queryVerticesCylinder(const Mesh& mesh, const glm::vec3& point, const glm::vec3& axis, float radius,
std::vector<uint32_t>& out) const;
// queryVertices for a capsule: every vertex within `radius` of the segment a..b (a fused batch of dabs along
// a stroke, core/SculptBatch.cpp).
void queryVerticesCapsule(const Mesh& mesh, const glm::vec3& a, const glm::vec3& b, float radius,
std::vector<uint32_t>& out) const;
// Appends every triangle whose bounds touch the sphere (cleared first; hidden ones included).
void queryTriangles(const Mesh& mesh, const glm::vec3& center, float radius, std::vector<uint32_t>& out) const;
// Calls fn(triangles of the leaf) for every leaf whose box touches the sphere (hidden triangles included);
// no per-triangle test, for callers that only need where the triangles are (texture painting's tiles).
void forEachLeafInSphere(const glm::vec3& center, float radius,
const std::function<void(std::span<const uint32_t>)>& fn) const;
// Updates bounds after the given vertices moved. A few leaves grow their ancestors' bounds (conservatively,
// which keeps queries correct); many leaves (a big brush) recompute their ancestors from their children, in
// parallel.
void refit(const Mesh& mesh, std::span<const uint32_t> movedVerts);
// refit() after only vertices the last queryVertices() returned moved (brush dabs): the query already
// found the leaves holding them, so this skips looking them up.
void refitQueried(const Mesh& mesh);
// The leaves holding the vertices the last queryVertices() returned, and refit() given such leaves (from
// one or more queries, each once: the Move brush keeps them for its whole stroke).
std::span<const uint32_t> queriedLeaves() const { return queryLeaves_; }
// The triangles of a leaf (empty for an inner node): every triangle with a vertex a query found is in one of
// the leaves it listed.
std::span<const uint32_t> leafTriangles(uint32_t leaf) const {
const Node& n = nodes_[leaf];
return n.count > 0 ? std::span<const uint32_t>(triIndices_.data() + n.first, n.count) : std::span<const uint32_t>();
}
void refitLeaves(const Mesh& mesh, std::span<const uint32_t> leaves);
// Recomputes every box (same tree) after most of the mesh moved, e.g. a whole Part transformed.
void refitAll(const Mesh& mesh);
// Dynamic topology (core/Dyntopo.h): a few triangles at a time added, removed or renumbered without a
// rebuild. insertTriangle puts triangle t (a new last index, or one removeTriangle freed) in the leaf of
// triangle `nearby` (or, if that isn't in the tree, the leaf its centroid falls in); refitChanged() then
// recomputes the boxes of every leaf edited since the last call (growing ancestors, as refit does) and
// splits leaves that grew too big. Boxes only grow, so after many edits rebuild when degraded() says so.
void insertTriangle(const Mesh& mesh, uint32_t t, uint32_t nearby);
void removeTriangle(uint32_t t);
// Triangle `from` is now numbered `to` (a free index); a freed last index can then be dropped with resizeTriangles.
void renumberTriangle(uint32_t from, uint32_t to);
void resizeTriangles(size_t count);
// Marks the leaf holding t for refitChanged (its triangle moved).
void touchTriangle(uint32_t t);
void refitChanged(const Mesh& mesh);
bool degraded() const;
size_t nodeCount() const { return nodes_.size(); }
// Per-node padding (micro levels: the largest displacement under each node, core/Micro.cpp MicroReach). The
// padded queries grow every node's box, and each leaf triangle's, by pad[node] (one value per node) plus
// `extra`; the caller then tests each triangle exactly. Leaves and parents for keeping pads up to date:
// structureSerial() changes whenever nodes or the triangle-to-leaf map do (build, dynamic edits).
uint64_t structureSerial() const { return structure_; }
uint32_t leafOf(uint32_t tri) const { return tri < triLeaf_.size() ? triLeaf_[tri] : kNoLeaf; }
uint32_t parentOf(uint32_t node) const { return nodes_[node].parent; }
// Child nodes have larger indices than their parent (a reverse sweep sees children first).
bool isInner(uint32_t node) const { return nodes_[node].count == 0 && nodes_[node].first != kNoLeaf; }
uint32_t leftChild(uint32_t node) const { return nodes_[node].first; }
void queryTrianglesPadded(const Mesh& mesh, const glm::vec3& center, float radius, std::span<const float> pad, float extra,
std::vector<uint32_t>& out) const;
// The triangles of every leaf whose padded box the ray (from origin along dir, t >= 0) crosses.
void rayTrianglesPadded(const Mesh& mesh, const glm::vec3& origin, const glm::vec3& dir, std::span<const float> pad, float extra,
std::vector<uint32_t>& out) const;
size_t memoryBytes() const;
private:
struct Node {
AABB box;
uint32_t first = 0; // leaf: offset into triIndices_, inner: index of left child (right = first + 1)
uint32_t count = 0; // > 0 for leaves
uint32_t parent = 0;
};
AABB leafBox(const Mesh& mesh, const Node& n) const;
void recomputeLeaf(const Mesh& mesh, Node& n); // its box, and triLeaf_ for its triangles
std::vector<Node> nodes_;
uint64_t structure_ = 0;
std::vector<uint32_t> triIndices_;
std::vector<uint32_t> triLeaf_;
// Dynamic edits: per node the room its leaf has in triIndices_ (empty until the first edit), the leaves
// edited since refitChanged (each once, flagged in leafEdited_), and how many entries of triIndices_ are no
// longer used (leaves that moved to make room) or were added since the build.
std::vector<uint32_t> leafCap_, editedLeaves_;
std::vector<uint8_t> leafEdited_;
size_t unusedEntries_ = 0, editsSinceBuild_ = 0;
static constexpr uint32_t kNoLeaf = ~0u;
void editLeaf(uint32_t leaf);
void refitAncestors(std::span<const uint32_t> leaves); // refitLeaves for many leaves, in parallel
void splitLeaf(const Mesh& mesh, uint32_t leaf);
template <class Shape>
void queryVerticesIn(const Mesh& mesh, const Shape& shape, std::vector<uint32_t>& out) const;
mutable IndexBits vertBits_; // queryVertices: the vertices found so far
mutable std::vector<uint32_t> queryLeaves_; // the leaves holding them, for refitQueried()
mutable std::vector<uint32_t> queryTasks_, queryNext_;
mutable std::vector<std::vector<uint32_t>> queryParts_;
IndexBits leafBits_; // refit: the leaves to recompute
std::vector<uint8_t> nodeDirty_; // refitAncestors: the inner nodes to recompute (all 0 between calls)
std::vector<uint32_t> scratchLeaves_;
mutable std::vector<uint32_t> stack_;
};
} // namespace sf