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
//
// Dynamic topology (dynamic topology, Blender's Dyntopo): with it on, every brush dab first remeshes the
// surface under the brush towards one edge length, so a sphere can be pulled into horns or fingers without
// stretching its triangles, and a blockout needs no remeshing.
//
// Each dab, inside the brush radius only: edges longer than 4/3 of the target are split at their midpoint
// (longest first), edges shorter than 3/5 of it are collapsed (shortest first, where that keeps the surface
// manifold, turns no triangle over, makes no long edge and leaves no vertex with fewer than three neighbours),
// edges are flipped where that evens out the valences, and the vertices that changed are relaxed along the
// surface. Boundaries, face group borders and the symmetry plane are kept: their vertices only slide along them.
// Masked and hidden parts are left alone. With symmetry on, every operation is done on its mirror images at the
// same time, so mirrored dabs make mirrored topology.
//
// Quads under the brush become triangles; UVs are dropped (a remeshed surface has none) and come back on undo.
// Meshes with subdivision levels can't be remeshed (as , delete the levels first).
//
// The mesh stays valid after every dab (no dead entries): elements a dab removed are filled from the end of
// the arrays. The BVH and the renderer follow incrementally (BVH::insertTriangle..., Mesh::changedTriangles), and
// the stroke's undo step keeps only the vertex and triangle slots it touched (TopologyUndo).
#pragma once
#include "core/BVH.h"
#include "core/Mesh.h"
#include "core/Symmetry.h"
#include <glm/glm.hpp>
#include <algorithm>
#include <cstdint>
#include <memory>
#include <span>
#include <string>
#include <utility>
#include <vector>
namespace sf {
struct DyntopoSettings {
bool enabled = false;
// false: the detail follows the brush size (dynamic topology: zoom in or shrink the brush for finer triangles);
// true: one detail size for the whole mesh, relative to its size.
bool constantDetail = false;
float detail = 0.5f; // 0 (coarse) .. 1 (fine)
// How much Smooth (Shift) remeshes while dynamic topology is on (from the discussions): 0 = smooth only, the
// topology stays; 1 (the default, as before) = it remeshes toward twice the edge length, so smoothing also
// simplifies. In between it remeshes toward 1 + smoothRemesh times the edge length.
float smoothRemesh = 1.0f;
};
// The edge-length scale Smooth remeshes with (0 = it doesn't remesh): 1 + smoothRemesh, as above.
inline float dyntopoSmoothScale(const DyntopoSettings& s) {
return s.smoothRemesh <= 0.005f ? 0.0f : 1.0f + std::min(s.smoothRemesh, 1.0f);
}
// The edge length dabs of world radius `radius` remesh towards, on a mesh whose bounding box diagonal is `diagonal`.
float dyntopoEdgeLength(const DyntopoSettings& s, float radius, float diagonal);
// Why `mesh` can't be remeshed by dynamic topology ("" when it can).
std::string dyntopoBlocker(const Mesh& mesh);
// "Dynamic topology on: Detail 50 (follows the brush size)".
std::string dyntopoSummary(const DyntopoSettings& s);
class CommandRegistry;
// dyntopo: on / off, Detail, constant detail (core/DyntopoCommands.cpp).
void registerDyntopoCommands(CommandRegistry& registry);
// Per-vertex and per-triangle values of a mesh at some slots (arrays the mesh doesn't have stay empty).
struct TopologyVertexValues {
std::vector<glm::vec3> positions, colors, base, paintBase;
std::vector<float> mask;
std::vector<std::vector<glm::vec3>> deltas, paintColors; // per sculpt layer / paint layer
std::vector<std::vector<float>> paintAlphas;
size_t bytes() const;
};
struct TopologyTriangleValues {
std::vector<glm::uvec3> triangles;
std::vector<uint32_t> facegroups, quadPartners;
std::vector<uint8_t> hidden;
size_t bytes() const;
};
// The undo of a dynamic-topology stroke: the vertex and triangle slots it touched (in either state), the
// element counts of the other state and its values at those slots (those below its counts). Applying swaps
// them with the mesh's, so the record then holds the inverse; the caller rebuilds topology, normals and BVH.
struct TopologyUndo {
uint32_t vertexCount = 0, triangleCount = 0;
std::vector<uint32_t> vertexSlots, triangleSlots;
TopologyVertexValues vertices;
TopologyTriangleValues triangles;
std::vector<glm::vec2> uvs; // the whole UVs of the other state, when it had them (dynamic topology drops them)
// Slots whose positions / colours must be worked out again from layers after applying (only when brush undo
// entries from before the stroke's first remesh were merged in; normally every value is exact).
std::vector<uint32_t> reevaluate;
void swapWith(Mesh& mesh);
size_t bytes() const;
};
struct DyntopoStats {
size_t splits = 0, collapses = 0, flips = 0;
size_t unpaired = 0; // operations whose mirror image wasn't found (an asymmetric mesh, or one edited without symmetry)
};
// Remeshes the surface under brush dabs (see the top of this file). One per Sculptor; a stroke's first remesh
// starts recording, finish() ends the stroke.
class DynamicTopology {
public:
// Remeshes within `radius` of `center` and of its symmetric copies (`mirrors` as Sculptor::copies makes them:
// mirror images and radial turns, the identity first) towards edges of `edgeLength`. Returns false when
// nothing changed.
bool remesh(Mesh& mesh, BVH& bvh, const glm::vec3& center, float radius, float edgeLength,
std::span<const SymCopy> mirrors);
// The vertices the last remesh renumbered (old slot, new slot), for per-vertex stroke state.
std::span<const std::pair<uint32_t, uint32_t>> movedVertices() const { return moved_; }
// The vertex slots the last remesh added to the stroke's undo record (their stroke-start state is there).
std::span<const uint32_t> recordedVertices() const { return recordedNow_; }
// The stroke changed the mesh's topology (or recorded it).
bool active() const { return mesh_ != nullptr; }
// Keeps vertex slot v's stroke-start state in the stroke's undo record (the brush calls it before moving or
// painting a vertex while the stroke remeshes; no-op when it is recorded already or nothing is remeshed).
void recordStrokeStart(uint32_t v) {
if (mesh_ && v < mesh_->vertexCount()) recordVertex(v);
}
// Vertex slot v is in the stroke's undo record (its stroke-start state is kept there).
bool recordedVertex(uint32_t v) const { return v < vertRec_.size() * 64 && ((vertRec_[v >> 6] >> (v & 63)) & 1); }
// Ends the stroke: packs the mesh's adjacency, rebuilds the BVH if the edits wore it down, and returns the
// undo record (null when the stroke didn't remesh).
std::unique_ptr<TopologyUndo> finish(Mesh& mesh, BVH& bvh);
// finish() for the mesh the stroke remeshed (null when none).
Mesh* strokeMesh() const { return mesh_; }
BVH* strokeBvh() const { return bvh_; }
DyntopoStats stats; // since the last reset
double lastMs = 0.0; // the last remesh's time
private:
struct Edge {
float len2;
uint32_t a, b;
};
// Recording (the stroke's undo), and what changed this remesh (for rings, normals, BVH and renderer).
void recordVertex(uint32_t v);
void recordTriangle(uint32_t t);
void markVertex(uint32_t v);
void markTriangle(uint32_t t);
// Elements.
uint32_t newVertex();
void interpolateVertex(uint32_t v, uint32_t a, uint32_t b, float t, const glm::vec3& position);
void killVertex(uint32_t v);
uint32_t newTriangle(const glm::uvec3& tri, uint32_t like);
void setTriangle(uint32_t t, const glm::uvec3& tri);
void killTriangle(uint32_t t);
void unpairQuad(uint32_t t);
void vtInsert(uint32_t v, uint32_t t);
void vtErase(uint32_t v, uint32_t t);
void vtReplace(uint32_t v, uint32_t from, uint32_t to);
void moveVertex(uint32_t from, uint32_t to);
void moveTriangle(uint32_t from, uint32_t to);
void compact();
// Queries (from the triangle lists, which are always current).
int edgeTriangles(uint32_t a, uint32_t b, uint32_t* out) const; // up to 4
void ring(uint32_t v, std::vector<uint32_t>& out) const;
bool locked(uint32_t v) const;
bool planeVertex(uint32_t v) const;
bool featureEdge(uint32_t a, uint32_t b) const;
int featureEdges(uint32_t v, uint32_t* other) const;
bool boundaryVertex(uint32_t v) const;
float len2(uint32_t a, uint32_t b) const;
bool inside(uint32_t a, uint32_t b, bool mirrored = false) const;
// An edge to remesh: under the brush, or under a mirror image of it with no image on the brush's side (an
// asymmetric mesh: that side is remeshed on its own).
bool candidate(uint32_t a, uint32_t b) const;
glm::vec3 faceNormalAt(uint32_t v) const;
// Symmetry: the mirror images of vertex v (kNone where unknown).
uint32_t mirrorOf(size_t mirror, uint32_t v) const;
void setMirror(size_t mirror, uint32_t v, uint32_t w);
void matchMirrors(const std::vector<uint32_t>& verts);
void orbit(uint32_t a, uint32_t b, std::vector<std::pair<uint32_t, uint32_t>>& out) const;
bool orbitSharesTriangle(const std::vector<std::pair<uint32_t, uint32_t>>& edges) const;
// Operations.
void splitPass();
void splitOrbit(uint32_t a, uint32_t b, int depth);
uint32_t split(uint32_t a, uint32_t b);
void collapsePass();
bool collapseTarget(uint32_t a, uint32_t b, uint32_t& keep, uint32_t& drop, glm::vec3& p) const;
bool canCollapse(uint32_t keep, uint32_t drop, const glm::vec3& p) const;
void collapse(uint32_t keep, uint32_t drop, const glm::vec3& p);
void flipPass();
bool flipGain(uint32_t a, uint32_t b, uint32_t& c, uint32_t& d) const;
void flip(uint32_t a, uint32_t b, uint32_t c, uint32_t d);
void relaxPass();
void pushEdgesAround(uint32_t v, bool longer);
void gatherRegion();
void queryRegion();
Mesh* mesh_ = nullptr;
BVH* bvh_ = nullptr;
uint32_t startVertices_ = 0, startTriangles_ = 0;
std::unique_ptr<TopologyUndo> undo_; // stroke-start values of the recorded slots (in the undo's layout)
std::vector<uint64_t> vertRec_, triRec_;
// The current remesh.
glm::vec3 center_{0.0f};
float radius_ = 0.0f, target_ = 0.0f, splitLen2_ = 0.0f, collapseLen2_ = 0.0f, eps_ = 0.0f;
std::vector<SymCopy> mirrorSigns_; // the symmetric copies, without the identity
std::vector<size_t> mirrorInverse_; // per copy, the index (in mirrorSigns_) of its inverse
// Per mirror: each vertex's image (valid where stamp == mirrorStamp_, so a new remesh forgets them all).
struct MirrorMap {
std::vector<uint32_t> to, stamp;
};
std::vector<MirrorMap> mirrorMaps_;
uint32_t mirrorStamp_ = 0;
std::vector<uint64_t> gridKeys_; // matchMirrors' search grid
std::vector<uint32_t> gridHead_, gridNext_;
std::vector<uint32_t> seen_, regionVerts_; // gatherRegion: vertices listed this remesh (seen_ == mirrorStamp_)
std::vector<uint8_t> deadV_, deadT_;
std::vector<uint32_t> freeV_, freeT_;
std::vector<uint32_t> changedV_, changedT_, regionTris_, slivers_;
std::vector<uint32_t> mirrorTris_; // the triangles under the brush's mirror images (queryRegion)
std::vector<uint8_t> changedVFlag_;
std::vector<Edge> heap_;
std::vector<std::pair<uint32_t, uint32_t>> moved_;
std::vector<uint32_t> recordedNow_;
mutable bool orbitIncomplete_ = false; // the last orbit() missed a mirror image
mutable std::vector<std::pair<uint32_t, uint32_t>> orbitScratch_; // candidate()
size_t ops_ = 0, maxOps_ = 0;
mutable std::vector<uint32_t> scratch_, scratch2_, ringA_, ringB_, ringC_, lockScratch_;
};
} // namespace sf