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
//
// Multiresolution subdivision levels (core/Multires.h): Divide keeps quads, detail survives stepping up and
// down bit-for-bit, low-level edits carry the high-level detail along, high-level edits show up below, mask /
// face groups / UVs / paint / sculpt layers follow the levels, undo steps across levels, Remove Below / Delete
// Higher / Reconstruct, projects keep every level, and exports can write the base.
#include "TestHarness.h"
#include "core/Commands.h"
#include "core/Multires.h"
#include "core/Primitives.h"
#include "core/Project.h"
#include "core/Parts.h"
#include "io/ObjIO.h"
#include <glm/gtc/matrix_transform.hpp>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <filesystem>
#include <fstream>
#include <map>
#include <sstream>
using namespace sf;
namespace {
const CommandRegistry& registry() {
static CommandRegistry r;
return r;
}
CommandResult run(Document& d, const std::string& name, const Args& a = {}) {
CommandResult r = registry().execute(d, name, a);
if (!r.ok) std::printf(" (%s: %s)\n", name.c_str(), r.message.c_str());
return r;
}
// One stroke towards -z through `points` ("x,y,z x,y,z").
bool stroke(Document& d, const std::string& points, const std::string& brush = "Standard", double radius = 0.25,
double strength = 0.8, bool invert = false) {
return run(d, "stroke", {{"points", points}, {"brush", brush}, {"radius", radius}, {"strength", strength},
{"invert", invert}}).ok;
}
float maxDistance(const std::vector<glm::vec3>& a, const std::vector<glm::vec3>& b) {
if (a.size() != b.size()) return 1e30f;
float m = 0.0f;
for (size_t i = 0; i < a.size(); ++i) m = std::max(m, glm::length(a[i] - b[i]));
return m;
}
bool bitEqual(const std::vector<glm::vec3>& a, const std::vector<glm::vec3>& b) {
return a.size() == b.size() && (a.empty() || std::memcmp(a.data(), b.data(), a.size() * sizeof(glm::vec3)) == 0);
}
Document dividedCube(int levels, int resolution = 3) {
Document d = makeDoc(makeCube(resolution));
for (int i = 0; i < levels; ++i) run(d, "subdiv_divide");
return d;
}
size_t countObjFaces(const std::string& path, int corners) {
std::ifstream f(std::filesystem::path(path), std::ios::binary);
std::string line;
size_t n = 0;
while (std::getline(f, line)) {
if (line.rfind("f ", 0) != 0) continue;
std::istringstream in(line.substr(2));
std::string tok;
int c = 0;
while (in >> tok) ++c;
if (c == corners) ++n;
}
return n;
}
} // namespace
TEST(multires_divide_keeps_quads_and_counts) {
Document d = makeDoc(makeCube(3));
const size_t baseTris = d.mesh.triangleCount();
CHECK(subdivLevelCount(d.mesh) == 0);
CHECK(run(d, "subdiv_divide").ok);
CHECK(subdivLevelCount(d.mesh) == 2);
CHECK(subdivCurrentLevel(d.mesh) == 1);
CHECK(d.mesh.triangleCount() == baseTris * 4);
CHECK(d.mesh.quadCount() * 2 == d.mesh.triangleCount()); // Catmull-Clark: all quads
CHECK(run(d, "subdiv_divide").ok);
CHECK(subdivLevelText(d.mesh) == "Level 3/3");
CHECK(d.mesh.triangleCount() == baseTris * 16);
CHECK(d.mesh.quadCount() * 2 == d.mesh.triangleCount());
CHECK(subdivLevelTriangles(d.mesh, 0) == baseTris);
// Smooth: the cube's corners round off (a corner vertex moves inwards).
float maxR = 0.0f;
for (const auto& p : d.mesh.positions) maxR = std::max(maxR, glm::length(p));
CHECK(maxR < std::sqrt(3.0f) - 0.05f);
// Closed and consistent: every vertex has triangles, normals are finite.
for (uint32_t v = 0; v < d.mesh.vertexCount(); ++v) CHECK(!d.mesh.vertexTriangles(v).empty());
// Triangle meshes use Loop subdivision and stay triangles.
Document t = makeDoc(makeIcosphere(2));
const size_t tris = t.mesh.triangleCount();
CHECK(run(t, "subdiv_divide").ok);
CHECK(t.mesh.triangleCount() == tris * 4);
CHECK(t.mesh.quadCount() == 0);
// Loop on a sphere stays close to the sphere.
for (const auto& p : t.mesh.positions) CHECK(std::abs(glm::length(p) - 1.0f) < 0.05f);
}
TEST(multires_flat_divide_keeps_the_shape) {
Document d = makeDoc(makeCube(2));
CHECK(run(d, "subdiv_divide", {{"smooth", false}}).ok);
// Flat: every new vertex lies on the cube's faces.
for (const auto& p : d.mesh.positions) {
const float m = std::max({std::abs(p.x), std::abs(p.y), std::abs(p.z)});
CHECK(std::abs(m - 1.0f) < 1e-5f);
}
}
TEST(multires_detail_survives_round_trips_bit_for_bit) {
Document d = dividedCube(3);
CHECK(stroke(d, "-0.3,0.2,2 0.3,0.25,2", "Standard", 0.2));
CHECK(stroke(d, "0.1,-0.4,2 0.2,0.4,2", "Crease", 0.1));
const std::vector<glm::vec3> top = d.mesh.positions;
const std::vector<glm::vec3> before = subdivLevelMesh(d.mesh, 0).positions;
for (int level : {1, 3, 2, 4, 1, 4}) CHECK(run(d, "subdiv_level", {{"level", double(level)}}).ok);
CHECK(subdivCurrentLevel(d.mesh) == 3);
CHECK(bitEqual(d.mesh.positions, top));
// The lower levels didn't drift either.
CHECK(bitEqual(subdivLevelMesh(d.mesh, 0).positions, before));
CHECK(run(d, "subdiv_lower").ok);
CHECK(run(d, "subdiv_higher").ok);
CHECK(bitEqual(d.mesh.positions, top));
CHECK(!run(d, "subdiv_higher").ok); // already at the top
}
TEST(multires_high_edit_shows_at_lower_levels) {
Document d = dividedCube(2);
const std::vector<glm::vec3> base0 = subdivLevelMesh(d.mesh, 0).positions;
const std::vector<glm::vec3> top0 = d.mesh.positions;
CHECK(stroke(d, "-0.3,0,2 0.3,0,2", "Inflate", 0.6, 1.0));
const std::vector<glm::vec3> top1 = d.mesh.positions;
CHECK(run(d, "subdiv_level", {{"level", 1.0}}).ok);
// Base vertices keep their index at every level: where the top moved a broad stroke, the base follows
// (softened), and the back face stays put.
float backMove = 0.0f;
int followed = 0, moved = 0;
for (size_t v = 0; v < base0.size(); ++v) {
const float top = glm::length(top1[v] - top0[v]), low = glm::length(d.mesh.positions[v] - base0[v]);
if (top > 0.02f) {
++moved;
followed += low > 0.5f * top && low < 1.5f * top;
}
if (base0[v].z < -0.9f) backMove = std::max(backMove, low);
}
CHECK(moved >= 4);
CHECK(followed == moved);
CHECK(backMove == 0.0f);
}
TEST(multires_low_edit_carries_the_detail) {
Document d = dividedCube(3);
CHECK(stroke(d, "-0.2,0.1,2 0.2,0.1,2", "Crease", 0.12));
const std::vector<glm::vec3> top = d.mesh.positions;
CHECK(run(d, "subdiv_level", {{"level", 1.0}}).ok);
// A rigid move of the base cage (rotate 90 degrees about y, then shift) moves the detail with it.
const glm::mat4 xf = glm::translate(glm::mat4(1.0f), glm::vec3(0.5f, -0.25f, 1.0f)) *
glm::rotate(glm::mat4(1.0f), glm::radians(90.0f), glm::vec3(0, 1, 0));
for (auto& p : d.mesh.positions) p = glm::vec3(xf * glm::vec4(p, 1.0f));
d.mesh.recomputeAllNormals();
CHECK(run(d, "subdiv_level", {{"level", 4.0}}).ok);
std::vector<glm::vec3> expected = top;
for (auto& p : expected) p = glm::vec3(xf * glm::vec4(p, 1.0f));
CHECK(maxDistance(d.mesh.positions, expected) < 1e-4f);
// A local edit low down moves the top level smoothly: far away nothing moves, nearby it does, and
// neighbouring vertices move by similar amounts (no tearing).
Document e = dividedCube(3);
CHECK(stroke(e, "0.1,0.1,2", "Crease", 0.1)); // detail on the front
const std::vector<glm::vec3> top2 = e.mesh.positions;
CHECK(run(e, "subdiv_level", {{"level", 2.0}}).ok);
const std::vector<glm::vec3> low = e.mesh.positions;
CHECK(stroke(e, "-0.2,0,2 0.2,0,2", "Inflate", 0.5, 1.0));
const float lowMove = maxDistance(e.mesh.positions, low);
CHECK(run(e, "subdiv_level", {{"level", 4.0}}).ok);
float far = 0.0f, near = 0.0f, jump = 0.0f;
for (size_t v = 0; v < top2.size(); ++v) {
const float m = glm::length(e.mesh.positions[v] - top2[v]);
if (top2[v].z < -0.5f) far = std::max(far, m);
if (top2[v].z > 0.9f && glm::length(glm::vec2(top2[v])) < 0.2f) near = std::max(near, m);
for (uint32_t u : e.mesh.neighbors(uint32_t(v)))
jump = std::max(jump, glm::length((e.mesh.positions[v] - top2[v]) - (e.mesh.positions[u] - top2[u])));
}
CHECK(lowMove > 0.01f);
CHECK(far < 1e-6f);
CHECK(near > 0.5f * lowMove);
CHECK(jump < near * 0.5f);
}
TEST(multires_undo_steps_across_levels) {
Document d = dividedCube(2);
const std::vector<glm::vec3> top0 = d.mesh.positions;
CHECK(stroke(d, "0,0,2", "Standard", 0.3));
const std::vector<glm::vec3> top1 = d.mesh.positions;
CHECK(run(d, "subdiv_level", {{"level", 1.0}}).ok);
const std::vector<glm::vec3> low1 = d.mesh.positions;
CHECK(stroke(d, "0.3,0.3,2", "Inflate", 0.5, 1.0));
const std::vector<glm::vec3> low2 = d.mesh.positions;
CHECK(!bitEqual(low1, low2));
// Undo: the low stroke, then the step (back at the top, exactly as sculpted), then the top stroke.
CHECK(run(d, "undo").ok);
CHECK(subdivCurrentLevel(d.mesh) == 0);
CHECK(bitEqual(d.mesh.positions, low1));
CHECK(run(d, "undo").ok);
CHECK(subdivCurrentLevel(d.mesh) == 2);
CHECK(bitEqual(d.mesh.positions, top1));
CHECK(run(d, "undo").ok);
CHECK(bitEqual(d.mesh.positions, top0));
// Redo all three: the same shapes again.
CHECK(run(d, "redo").ok);
CHECK(bitEqual(d.mesh.positions, top1));
CHECK(run(d, "redo").ok);
CHECK(subdivCurrentLevel(d.mesh) == 0);
CHECK(maxDistance(d.mesh.positions, low1) < 1e-5f);
CHECK(run(d, "redo").ok);
CHECK(maxDistance(d.mesh.positions, low2) < 1e-5f);
// Undo everything, then the lower level follows the undone top stroke when stepped to.
for (int i = 0; i < 3; ++i) CHECK(run(d, "undo").ok);
CHECK(bitEqual(d.mesh.positions, top0));
CHECK(run(d, "subdiv_level", {{"level", 1.0}}).ok);
CHECK(maxDistance(d.mesh.positions, subdivLevelMesh(dividedCube(2).mesh, 0).positions) < 1e-5f);
// Undoing the first Divide gives back the plain mesh.
Document p = makeDoc(makeCube(3));
const std::vector<glm::vec3> plain = p.mesh.positions;
CHECK(run(p, "subdiv_divide").ok);
CHECK(run(p, "undo").ok);
CHECK(subdivLevelCount(p.mesh) == 0);
CHECK(bitEqual(p.mesh.positions, plain));
CHECK(run(p, "redo").ok);
CHECK(subdivLevelCount(p.mesh) == 2);
CHECK(p.mesh.triangleCount() == makeCube(3).triangleCount() * 4);
}
TEST(multires_attributes_follow_levels) {
Document d = dividedCube(2);
// Mask painted at the top shows at the corners of the base; face groups set low are inherited up.
run(d, "mask_all");
d.mesh.ensureMask();
for (uint32_t v = 0; v < d.mesh.vertexCount(); ++v) d.mesh.mask[v] = d.mesh.positions[v].x > 0 ? 1.0f : 0.0f;
const std::vector<float> topMask = d.mesh.mask;
CHECK(run(d, "subdiv_level", {{"level", 1.0}}).ok);
CHECK(d.mesh.hasMask());
const Mesh base = subdivLevelMesh(d.mesh, 0);
for (uint32_t v = 0; v < d.mesh.vertexCount(); ++v) CHECK(d.mesh.mask[v] == (base.positions[v].x > 0 ? 1.0f : 0.0f));
d.mesh.ensureFaceGroups();
for (auto& g : d.mesh.facegroups) g = 7;
d.mesh.facegroups[0] = 9;
d.mesh.facegroups[1] = 9; // one quad
CHECK(run(d, "subdiv_level", {{"level", 3.0}}).ok);
CHECK(d.mesh.mask == topMask); // untouched mask detail kept
size_t nine = 0;
for (uint32_t g : d.mesh.facegroups) nine += g == 9;
CHECK(nine == 2 * 16); // the quad's 16 grandchildren
for (uint32_t g : d.mesh.facegroups) CHECK(g == 7 || g == 9);
// Hidden faces at the top hide their parents below.
d.mesh.ensureHidden();
for (uint32_t t = 0; t < d.mesh.triangleCount(); ++t) d.mesh.hidden[t] = d.mesh.facegroups[t] == 9;
CHECK(run(d, "subdiv_level", {{"level", 1.0}}).ok);
CHECK(d.mesh.hasHidden() && d.mesh.hidden[0] && d.mesh.hidden[1] && !d.mesh.hidden[2]);
// Clearing the mask clears it everywhere.
d.mesh.clearMask();
CHECK(run(d, "subdiv_level", {{"level", 3.0}}).ok);
CHECK(!d.mesh.hasMask());
// UVs: divided with the mesh, kept through round trips.
Document u = makeDoc(makePlane(4));
u.mesh.uvs.resize(u.mesh.triangleCount() * 3);
for (size_t t = 0; t < u.mesh.triangleCount(); ++t)
for (int c = 0; c < 3; ++c) {
const glm::vec3 p = u.mesh.positions[u.mesh.triangles[t][c]];
u.mesh.uvs[t * 3 + size_t(c)] = {p.x * 0.5f + 0.5f, p.z * 0.5f + 0.5f};
}
CHECK(run(u, "subdiv_divide").ok);
CHECK(u.mesh.uvs.size() == u.mesh.triangleCount() * 3);
// On a plane the UVs follow the (flat) positions linearly.
bool linear = true;
for (size_t t = 0; t < u.mesh.triangleCount(); ++t)
for (int c = 0; c < 3; ++c) {
const glm::vec3 p = u.mesh.positions[u.mesh.triangles[t][c]];
const glm::vec2 uv = u.mesh.uvs[t * 3 + size_t(c)];
linear = linear && std::abs(uv.x - (p.x * 0.5f + 0.5f)) + std::abs(uv.y - (p.z * 0.5f + 0.5f)) < 0.2f;
}
CHECK(linear);
const std::vector<glm::vec2> uvs = u.mesh.uvs;
CHECK(run(u, "subdiv_level", {{"level", 1.0}}).ok);
CHECK(run(u, "subdiv_level", {{"level", 2.0}}).ok);
CHECK(u.mesh.uvs == uvs);
// Vertex paint painted low is interpolated up; paint at the top survives a low-level paint elsewhere.
Document c = dividedCube(2);
c.mesh.ensureColors();
c.mesh.colors[0] = glm::vec3(1, 0, 0);
CHECK(run(c, "subdiv_level", {{"level", 1.0}}).ok);
c.mesh.ensureColors();
c.mesh.colors[5] = glm::vec3(0, 0, 1);
CHECK(run(c, "subdiv_level", {{"level", 3.0}}).ok);
CHECK(c.mesh.colors[0] == glm::vec3(1, 0, 0));
CHECK(c.mesh.colors[5] == glm::vec3(0, 0, 1));
}
TEST(multires_sculpt_layers_work_at_every_level) {
Document d = dividedCube(2);
CHECK(run(d, "layer_add", {{"name", "Smile"}}).ok);
d.activeLayer = 0;
CHECK(stroke(d, "0,0,2", "Standard", 0.4));
const std::vector<glm::vec3> withLayer = d.mesh.positions;
CHECK(run(d, "subdiv_level", {{"level", 1.0}}).ok);
CHECK(d.mesh.layers.size() == 1 && d.mesh.layers[0].name == "Smile");
CHECK(run(d, "layer_set_weight", {{"index", 0.0}, {"weight", 0.0}}).ok);
CHECK(run(d, "subdiv_level", {{"level", 3.0}}).ok);
CHECK(d.mesh.layers[0].weight == 0.0f);
// Weight 0 at the top: the layer's bump is gone, the base remains.
CHECK(maxDistance(d.mesh.positions, d.mesh.base) < 1e-6f);
CHECK(run(d, "layer_set_weight", {{"index", 0.0}, {"weight", 1.0}}).ok);
CHECK(maxDistance(d.mesh.positions, withLayer) < 1e-5f);
CHECK(run(d, "layer_remove", {{"index", 0.0}}).ok);
CHECK(run(d, "subdiv_level", {{"level", 1.0}}).ok);
CHECK(d.mesh.layers.empty());
}
TEST(multires_delete_lower_and_higher) {
Document d = dividedCube(3);
CHECK(stroke(d, "0,0,2", "Standard", 0.3));
CHECK(run(d, "subdiv_level", {{"level", 2.0}}).ok);
const std::vector<glm::vec3> level2 = d.mesh.positions;
const size_t tris2 = d.mesh.triangleCount();
CHECK(run(d, "subdiv_delete_lower").ok);
CHECK(subdivLevelText(d.mesh) == "Level 1/3");
CHECK(bitEqual(d.mesh.positions, level2));
CHECK(run(d, "subdiv_level", {{"level", 3.0}}).ok);
CHECK(d.mesh.triangleCount() == tris2 * 16);
CHECK(run(d, "subdiv_level", {{"level", 2.0}}).ok);
CHECK(run(d, "subdiv_delete_higher").ok);
CHECK(subdivLevelText(d.mesh) == "Level 2/2");
CHECK(!run(d, "subdiv_higher").ok);
CHECK(run(d, "undo").ok);
CHECK(subdivLevelText(d.mesh) == "Level 2/3");
// Deleting down to one level leaves a plain mesh.
CHECK(run(d, "subdiv_level", {{"level", 1.0}}).ok);
CHECK(run(d, "subdiv_delete_higher").ok);
CHECK(subdivLevelCount(d.mesh) == 0);
CHECK(run(d, "undo").ok);
CHECK(subdivLevelCount(d.mesh) == 3);
}
// A review hit "Dynamic topology needs a mesh without subdivision levels" on the divided default sphere: Freeze
// Levels keeps the level shown as a plain mesh in one undo step, and dyntopo freeze_levels=true does it and turns
// Dynamic on.
TEST(multires_freeze_levels_for_dynamic) {
Document d = dividedCube(3);
CHECK(stroke(d, "0,0,2", "Standard", 0.3));
CHECK(run(d, "subdiv_level", {{"level", 2.0}}).ok);
const std::vector<glm::vec3> level2 = d.mesh.positions;
const size_t tris2 = d.mesh.triangleCount();
CHECK(!run(d, "dyntopo", {{"enabled", true}}).ok); // still blocked without the option
CHECK(!d.sculptor.dyntopo.enabled);
CHECK(run(d, "subdiv_freeze").ok);
CHECK(subdivLevelCount(d.mesh) == 0);
CHECK(d.mesh.triangleCount() == tris2);
CHECK(bitEqual(d.mesh.positions, level2));
CHECK(run(d, "undo").ok);
CHECK(subdivLevelText(d.mesh) == "Level 2/4");
CHECK(bitEqual(d.mesh.positions, level2));
// In one go, from the top level.
Document e = dividedCube(2);
const size_t top = e.mesh.triangleCount();
const CommandResult r = run(e, "dyntopo", {{"enabled", true}, {"freeze_levels", true}});
CHECK(r.ok);
CHECK(e.sculptor.dyntopo.enabled);
CHECK(subdivLevelCount(e.mesh) == 0);
CHECK(e.mesh.triangleCount() == top);
CHECK(run(e, "undo").ok);
CHECK(subdivLevelCount(e.mesh) == 3);
// Nothing to freeze on a plain mesh.
Document p = makeDoc(makeCube(3));
CHECK(!run(p, "subdiv_freeze").ok);
}
TEST(multires_reconstruct_finds_lower_levels) {
// A Catmull-Clark subdivided cube, imported as a plain mesh.
Document src = dividedCube(2, 2);
CHECK(stroke(src, "0,0,2", "Standard", 0.3));
Mesh plain = subdivLevelMesh(src.mesh, 2);
const std::vector<glm::vec3> fine = plain.positions;
Document d = makeDoc(std::move(plain));
CHECK(run(d, "subdiv_reconstruct").ok);
CHECK(subdivLevelText(d.mesh) == "Level 1/2");
CHECK(d.mesh.triangleCount() == src.mesh.triangleCount() / 4);
CHECK(d.mesh.quadCount() * 2 == d.mesh.triangleCount());
CHECK(run(d, "subdiv_reconstruct").ok);
CHECK(subdivLevelText(d.mesh) == "Level 1/3");
CHECK(d.mesh.triangleCount() == makeCube(2).triangleCount());
CHECK(d.mesh.vertexCount() == makeCube(2).vertexCount());
// The base sits on the fine level's corner vertices.
for (const auto& p : d.mesh.positions) CHECK(std::find(fine.begin(), fine.end(), p) != fine.end());
CHECK(run(d, "subdiv_level", {{"level", 3.0}}).ok);
CHECK(bitEqual(d.mesh.positions, fine)); // the top is exactly the mesh it started from
CHECK(!run(d, "subdiv_reconstruct").ok); // only at the lowest level
// Loop: an icosphere divided twice reconstructs down to the icosphere's topology.
Document t = makeDoc(makeIcosphere(1));
run(t, "subdiv_divide");
run(t, "subdiv_divide");
Mesh tplain = subdivLevelMesh(t.mesh, 2);
Document r = makeDoc(std::move(tplain));
CHECK(run(r, "subdiv_reconstruct").ok);
CHECK(run(r, "subdiv_reconstruct").ok);
CHECK(r.mesh.triangleCount() == makeIcosphere(1).triangleCount());
CHECK(maxDistance(r.mesh.positions, subdivLevelMesh(t.mesh, 0).positions) < 0.1f);
// A mesh that isn't a subdivision is refused, and undo restores the plain mesh.
Document n = makeDoc(makeIcosphere(2));
n.mesh.triangles[0] = {n.mesh.triangles[0].x, n.mesh.triangles[0].z, n.mesh.triangles[0].y};
Document ok = makeDoc(makeCube(3));
CHECK(!run(ok, "subdiv_reconstruct").ok); // a 3x3 cube isn't a 2x subdivision
CHECK(subdivLevelCount(ok.mesh) == 0);
CHECK(run(d, "undo").ok); // the step to level 3
CHECK(run(d, "undo").ok); // the second reconstruct
CHECK(subdivLevelText(d.mesh) == "Level 1/2");
}
// #145: `coarse` (all quads) gets UDIM UVs, every quad in its own tile (so every edge is a seam), is divided once
// and imported as a plain mesh; Reconstruct must find `coarse` again with each face's corner UVs (not UVs from
// across seams or tiles), and stepping back up must give back the imported UVs exactly.
static void checkReconstructKeepsUvs(Mesh coarse, bool flip = false) {
std::vector<uint32_t> quadOf(coarse.triangleCount());
uint32_t quads = 0;
for (uint32_t t = 0; t < coarse.triangleCount(); ++t) {
const uint32_t q = coarse.quadPartnerAt(t);
quadOf[t] = q != Mesh::kNoQuad && q < t ? quadOf[q] : quads++;
}
coarse.uvs.resize(coarse.triangleCount() * 3);
for (size_t t = 0; t < coarse.triangleCount(); ++t)
for (int c = 0; c < 3; ++c) {
const uint32_t q = quadOf[t], v = coarse.triangles[t][c];
const uint32_t h = (q * 2654435761u) ^ (v * 40503u + 977u);
coarse.uvs[t * 3 + size_t(c)] = glm::vec2(float(q % 10), float(q / 10)) +
glm::vec2(0.05f + 0.9f * float(h % 1000) / 1000.0f, 0.05f + 0.9f * float(h / 1000 % 1000) / 1000.0f);
}
Document src = makeDoc(std::move(coarse));
CHECK(run(src, "subdiv_divide").ok);
Mesh plain = subdivLevelMesh(src.mesh, 1);
// An imported mesh numbers its vertices its own way (here: backwards), not base corners first.
const uint32_t nf = uint32_t(plain.vertexCount());
std::reverse(plain.positions.begin(), plain.positions.end());
for (glm::uvec3& t : plain.triangles) t = glm::uvec3(nf - 1) - t;
// ... and may split its quads along the other diagonal (edge point to edge point, not corner to face point).
for (uint32_t t = 0; flip && t < plain.triangleCount(); ++t) {
const uint32_t u = plain.quadPartnerAt(t);
if (u == Mesh::kNoQuad || u < t) continue;
const glm::uvec3 a = plain.triangles[t], b = plain.triangles[u];
auto uvOf = [&](uint32_t v) {
for (uint32_t x : {t, u})
for (int c = 0; c < 3; ++c)
if (plain.triangles[x][c] == v) return plain.uvs[size_t(x) * 3 + size_t(c)];
return glm::vec2(0.0f);
};
int k = 0; // a's corner off the shared diagonal
for (int c = 0; c < 3; ++c)
if (b.x != a[c] && b.y != a[c] && b.z != a[c]) k = c;
uint32_t w = b.x; // b's corner off it
for (int c = 0; c < 3; ++c)
if (b[c] != a.x && b[c] != a.y && b[c] != a.z) w = b[c];
const uint32_t q[4] = {a[k], a[(k + 1) % 3], w, a[(k + 2) % 3]};
const glm::vec2 uv[4] = {uvOf(q[0]), uvOf(q[1]), uvOf(q[2]), uvOf(q[3])};
plain.triangles[t] = {q[0], q[1], q[2]};
plain.triangles[u] = {q[0], q[2], q[3]};
for (int c = 0; c < 3; ++c) {
plain.uvs[size_t(t) * 3 + size_t(c)] = uv[c];
plain.uvs[size_t(u) * 3 + size_t(c)] = uv[c == 0 ? 0 : c + 1];
}
}
plain.recomputeAllNormals();
const std::vector<glm::vec2> fineUvs = plain.uvs;
const std::vector<glm::uvec3> fineTris = plain.triangles;
const std::vector<glm::vec3> finePositions = plain.positions;
Document d = makeDoc(std::move(plain));
CHECK(run(d, "subdiv_reconstruct").ok);
CHECK(subdivLevelText(d.mesh) == "Level 1/2");
const Mesh base = subdivLevelMesh(src.mesh, 0);
CHECK(d.mesh.triangleCount() == base.triangleCount() && d.mesh.vertexCount() == base.vertexCount());
CHECK(d.mesh.uvs.size() == d.mesh.triangleCount() * 3);
if (d.mesh.uvs.size() != d.mesh.triangleCount() * 3 || d.mesh.vertexCount() != base.vertexCount()) return;
// The base sits on the fine level's corners, which a divided level numbers as the base vertices.
std::vector<uint32_t> baseIndex(d.mesh.vertexCount(), UINT32_MAX);
for (uint32_t v = 0; v < d.mesh.vertexCount(); ++v)
for (uint32_t b = 0; b < base.vertexCount(); ++b)
if (d.mesh.positions[v] == finePositions[nf - 1 - b]) baseIndex[v] = b;
// Every base triangle lies in one original quad and has that quad's corner UVs.
size_t wrong = 0;
for (size_t t = 0; t < d.mesh.triangleCount(); ++t) {
bool found = false;
for (uint32_t b = 0; b < base.triangleCount() && !found; ++b) {
const uint32_t partner = base.quadPartnerAt(b);
auto uvAt = [&](uint32_t v, glm::vec2& uv) {
for (uint32_t bt : {b, partner}) {
if (bt == Mesh::kNoQuad) continue;
for (int k = 0; k < 3; ++k)
if (base.triangles[bt][k] == v) {
uv = base.uvs[size_t(bt) * 3 + size_t(k)];
return true;
}
}
return false;
};
bool all = true;
for (int c = 0; c < 3 && all; ++c) {
glm::vec2 uv;
all = uvAt(baseIndex[d.mesh.triangles[t][c]], uv) && uv == d.mesh.uvs[t * 3 + size_t(c)];
}
found = all;
}
if (!found && wrong++ == 0)
std::printf(" base triangle %zu: UVs (%g,%g) (%g,%g) (%g,%g) aren't one original face's\n", t, d.mesh.uvs[t * 3].x,
d.mesh.uvs[t * 3].y, d.mesh.uvs[t * 3 + 1].x, d.mesh.uvs[t * 3 + 1].y, d.mesh.uvs[t * 3 + 2].x,
d.mesh.uvs[t * 3 + 2].y);
}
CHECK(wrong == 0);
CHECK(run(d, "subdiv_level", {{"level", 2.0}}).ok);
CHECK(d.mesh.triangles == fineTris);
CHECK(d.mesh.uvs == fineUvs);
CHECK(run(d, "subdiv_level", {{"level", 1.0}}).ok);
CHECK(run(d, "subdiv_level", {{"level", 2.0}}).ok);
CHECK(d.mesh.uvs == fineUvs);
}
TEST(multires_reconstruct_keeps_udim_uvs) {
checkReconstructKeepsUvs(makePlane(4)); // open: a border
checkReconstructKeepsUvs(makeTorus(12)); // closed, every vertex regular: four readings of the corners fit,
checkReconstructKeepsUvs(makeTorus(12), true); // and with these diagonals the first one tried is a shifted one
checkReconstructKeepsUvs(makeCube(3), true);
}
// #145 reopened: the reconstructed LOWER levels broke. `coarse` gets UDIM islands (by face direction; the x < 0 half
// mirrored onto the x > 0 half's tile), is divided `levels` times, and the top goes out and back in as an OBJ; then
// Reconstruct runs `levels` times. Every reconstructed level must be the divided one: each triangle inside one
// original face, with that face's corner UVs (so seams kept, islands intact, values in their UDIM tile).
static void checkReconstructLevelsKeepUvs(const char* name, Mesh coarse, int levels) {
std::printf(" %s\n", name);
coarse.recomputeAllNormals();
coarse.uvs.resize(coarse.triangleCount() * 3);
for (uint32_t t = 0; t < coarse.triangleCount(); ++t) {
uint32_t f = t; // a quad's two triangles share an island: pick by the pair's first triangle
if (coarse.quadPartnerAt(t) != Mesh::kNoQuad) f = std::min(t, coarse.quadPartnerAt(t));
const glm::uvec3 tf = coarse.triangles[f];
const glm::vec3 p0 = coarse.positions[tf.x], p1 = coarse.positions[tf.y], p2 = coarse.positions[tf.z];
const glm::vec3 n = glm::cross(p1 - p0, p2 - p0), c = (p0 + p1 + p2) / 3.0f;
int axis = 0;
for (int a = 1; a < 3; ++a)
if (std::abs(n[a]) > std::abs(n[axis])) axis = a;
const uint32_t island = uint32_t(axis * 2 + (n[axis] < 0 ? 1 : 0)) * 2 + (c.y > 0.0f ? 1 : 0);
for (int k = 0; k < 3; ++k) {
const glm::vec3 p = coarse.positions[coarse.triangles[t][k]];
glm::vec2 uv(p[(axis + 1) % 3], p[(axis + 2) % 3]);
if (axis != 0) uv.x = std::abs(uv.x); // mirrored: both halves on one tile
uv = glm::clamp(uv * 0.2f + 0.5f, glm::vec2(0.01f), glm::vec2(0.99f));
coarse.uvs[size_t(t) * 3 + size_t(k)] = uv + glm::vec2(float(island % 10), float(island / 10));
}
}
Document src = makeDoc(std::move(coarse));
for (int i = 0; i < levels; ++i) CHECK(run(src, "subdiv_divide").ok);
const Mesh top = subdivLevelMesh(src.mesh, levels);
const std::string path = tempPath("sf_reconstruct_uvs.obj");
std::string err;
CHECK(saveObj(path, top, err));
Mesh plain;
CHECK(loadObj(path, plain, err));
std::filesystem::remove(path);
// Divided levels number their vertices coarse corners first, so source level k's vertex b is the top's b (the OBJ
// keeps the order; its positions and UVs are rounded to 7 digits).
CHECK(plain.vertexCount() == top.vertexCount());
std::map<std::tuple<float, float, float>, uint32_t> topIndex;
for (uint32_t v = 0; v < plain.vertexCount(); ++v) topIndex[{plain.positions[v].x, plain.positions[v].y, plain.positions[v].z}] = v;
Document d = makeDoc(std::move(plain));
for (int i = 0; i < levels; ++i) CHECK(run(d, "subdiv_reconstruct").ok);
CHECK(subdivLevelCount(d.mesh) == levels + 1);
if (subdivLevelCount(d.mesh) != levels + 1) return;
for (int k = 0; k < levels; ++k) {
const Mesh want = subdivLevelMesh(src.mesh, k), got = subdivLevelMesh(d.mesh, k);
CHECK(got.triangleCount() == want.triangleCount() && got.vertexCount() == want.vertexCount());
CHECK(got.uvs.size() == got.triangleCount() * 3);
if (got.uvs.size() != got.triangleCount() * 3 || got.vertexCount() != want.vertexCount()) continue;
// The reconstructed level's corners sit on the top's vertices (the top is the imported mesh).
std::vector<uint32_t> srcIndex(got.vertexCount(), UINT32_MAX);
for (uint32_t v = 0; v < got.vertexCount(); ++v) {
auto it = topIndex.find({got.positions[v].x, got.positions[v].y, got.positions[v].z});
if (it != topIndex.end()) srcIndex[v] = it->second;
}
// Source triangles by vertex, then: each triangle lies in one source face and has its corner UVs.
std::vector<std::vector<uint32_t>> facesOf(want.vertexCount());
for (uint32_t t = 0; t < want.triangleCount(); ++t)
for (int c = 0; c < 3; ++c) facesOf[want.triangles[t][c]].push_back(t);
size_t wrong = 0;
for (uint32_t t = 0; t < got.triangleCount(); ++t) {
bool found = false;
const uint32_t v0 = srcIndex[got.triangles[t].x];
for (uint32_t b : v0 < want.vertexCount() ? facesOf[v0] : std::vector<uint32_t>{}) {
auto uvAt = [&](uint32_t v, glm::vec2& uv) {
for (uint32_t bt : {b, want.quadPartnerAt(b)}) {
if (bt == Mesh::kNoQuad) continue;
for (int c = 0; c < 3; ++c)
if (want.triangles[bt][c] == v) {
uv = want.uvs[size_t(bt) * 3 + size_t(c)];
return true;
}
}
return false;
};
bool all = true;
for (int c = 0; c < 3 && all; ++c) {
glm::vec2 uv;
all = uvAt(srcIndex[got.triangles[t][c]], uv) &&
glm::all(glm::lessThan(glm::abs(uv - got.uvs[size_t(t) * 3 + size_t(c)]), glm::vec2(1e-5f)));
}
if ((found = all)) break;
}
if (!found && wrong++ == 0)
std::printf(" Level %d triangle %u: UVs (%g,%g) (%g,%g) (%g,%g) aren't one original face's\n", k + 1, t,
got.uvs[t * 3].x, got.uvs[t * 3].y, got.uvs[t * 3 + 1].x, got.uvs[t * 3 + 1].y, got.uvs[t * 3 + 2].x,
got.uvs[t * 3 + 2].y);
}
if (wrong) std::printf(" Level %d: %zu of %zu triangles wrong\n", k + 1, wrong, got.triangleCount());
CHECK(wrong == 0);
}
// Stepping through every level and back to the top gives back the imported UVs.
CHECK(run(d, "subdiv_level", {{"level", double(levels + 1)}}).ok);
const std::vector<glm::vec2> topUvs = d.mesh.uvs;
for (int k = levels; k >= 1; --k) CHECK(run(d, "subdiv_level", {{"level", double(k)}}).ok);
CHECK(run(d, "subdiv_level", {{"level", double(levels + 1)}}).ok);
CHECK(d.mesh.uvs == topUvs);
}
TEST(multires_reconstruct_lower_levels_keep_uvs) {
checkReconstructLevelsKeepUvs("cube (valence-3 poles)", makeCube(2), 3);
checkReconstructLevelsKeepUvs("plane (open border)", makePlane(3), 3);
checkReconstructLevelsKeepUvs("torus (regular, closed)", makeTorus(8), 2);
checkReconstructLevelsKeepUvs("quad sphere", makeQuadSphere(2), 2);
checkReconstructLevelsKeepUvs("cylinder (n-gon caps)", makeCylinder(8), 2);
checkReconstructLevelsKeepUvs("cone (triangles + quads)", makeCone(6), 2);
checkReconstructLevelsKeepUvs("capsule", makeCapsule(8), 2);
}
// #145 (RodTDai's answers, screenshots and hint): a high-poly unwrapped on its own, so UV seams run THROUGH the
// faces of the levels Reconstruct finds, and islands overlap (automatic unwraps stack them). Before, such a face took
// each corner's UV from whichever island that corner was in and stretched across UDIM tiles. Fine UVs here: a planar
// projection per island, islands cut by planes off the coarse edges, two tiles of four overlapping islands each
// (as is, mirrored, rotated, shifted); out and back in as an OBJ. Every reconstructed triangle must lie in one
// island: all three corners near that island's projection of their positions.
static glm::vec2 islandUv(uint32_t island, glm::vec3 p) {
glm::vec2 uv = glm::vec2(p.x, p.y + 0.5f * p.z) * 0.25f + 0.5f;
switch (island >> 1) {
case 1: uv.x = 1.0f - uv.x; break;
case 2: uv = glm::vec2(1.0f) - uv; break;
case 3: uv += glm::vec2(0.07f, 0.05f); break;
}
return uv + glm::vec2(float(island & 1), 0.0f);
}
static void checkReconstructSeamsThroughFaces(const char* name, Mesh coarse, int levels) {
std::printf(" %s\n", name);
Document src = makeDoc(std::move(coarse));
for (int i = 0; i < levels; ++i) CHECK(run(src, "subdiv_divide").ok);
Mesh top = subdivLevelMesh(src.mesh, levels);
top.uvs.resize(top.triangleCount() * 3);
for (uint32_t t = 0; t < top.triangleCount(); ++t) {
uint32_t f = t; // both halves of a fine quad in one island
if (top.quadPartnerAt(t) != Mesh::kNoQuad) f = std::min(t, top.quadPartnerAt(t));
const uint32_t g = top.quadPartnerAt(f);
glm::vec3 c(0.0f);
int k = 0;
for (uint32_t x : {f, g})
if (x != Mesh::kNoQuad)
for (int j = 0; j < 3; ++j) c += top.positions[top.triangles[x][j]], ++k;
c /= float(k);
const uint32_t island = uint32_t(c.x > 0.13f) + 2u * uint32_t(c.y > -0.21f) + 4u * uint32_t(c.z > 0.37f);
for (int j = 0; j < 3; ++j) top.uvs[size_t(t) * 3 + size_t(j)] = islandUv(island, top.positions[top.triangles[t][j]]);
}
const std::string path = tempPath("sf_reconstruct_seams.obj");
std::string err;
CHECK(saveObj(path, top, err));
Mesh plain;
CHECK(loadObj(path, plain, err));
std::filesystem::remove(path);
const std::vector<glm::vec2> fineUvs = plain.uvs;
Document d = makeDoc(std::move(plain));
for (int i = 0; i < levels; ++i) CHECK(run(d, "subdiv_reconstruct").ok);
CHECK(subdivLevelCount(d.mesh) == levels + 1);
for (int k = 0; k < levels && subdivLevelCount(d.mesh) == levels + 1; ++k) {
const Mesh got = subdivLevelMesh(d.mesh, k);
CHECK(got.uvs.size() == got.triangleCount() * 3);
if (got.uvs.size() != got.triangleCount() * 3) continue;
size_t wrong = 0;
for (uint32_t t = 0; t < got.triangleCount(); ++t) {
bool ok = false;
for (uint32_t island = 0; island < 8 && !ok; ++island) {
ok = true;
for (int j = 0; j < 3 && ok; ++j)
ok = glm::length(got.uvs[size_t(t) * 3 + size_t(j)] - islandUv(island, got.positions[got.triangles[t][j]])) < 0.05f;
}
if (!ok && wrong++ == 0)
std::printf(" Level %d triangle %u: UVs (%g,%g) (%g,%g) (%g,%g) aren't one island's\n", k + 1, t, got.uvs[t * 3].x,
got.uvs[t * 3].y, got.uvs[t * 3 + 1].x, got.uvs[t * 3 + 1].y, got.uvs[t * 3 + 2].x, got.uvs[t * 3 + 2].y);
}
if (wrong) std::printf(" Level %d: %zu of %zu triangles wrong\n", k + 1, wrong, got.triangleCount());
CHECK(wrong == 0);
}
CHECK(run(d, "subdiv_level", {{"level", double(levels + 1)}}).ok);
CHECK(d.mesh.uvs == fineUvs); // the imported level keeps its own UVs exactly
}
TEST(multires_reconstruct_keeps_overlapping_uvs_with_seams_through_faces) {
checkReconstructSeamsThroughFaces("cube", makeCube(3), 1);
checkReconstructSeamsThroughFaces("cube, 2 levels", makeCube(3), 2);
checkReconstructSeamsThroughFaces("quad sphere", makeQuadSphere(3), 2);
checkReconstructSeamsThroughFaces("cone (triangles + quads)", makeCone(8), 2);
checkReconstructSeamsThroughFaces("plane (open border)", makePlane(5), 2);
checkReconstructSeamsThroughFaces("torus (regular, closed)", makeTorus(12), 1);
}
TEST(multires_project_round_trip_keeps_every_level) {
Document d = dividedCube(3);
CHECK(stroke(d, "0,0,2", "Standard", 0.3));
CHECK(run(d, "subdiv_level", {{"level", 2.0}}).ok);
CHECK(stroke(d, "0.4,0.4,2", "Inflate", 0.4, 1.0)); // pending, not folded in yet
d.mesh.ensureFaceGroups()[3] = 5;
std::vector<std::vector<glm::vec3>> levels;
for (int i = 0; i < 4; ++i) levels.push_back(subdivLevelMesh(d.mesh, i).positions);
const std::string path = tempPath("sf_multires.sfproj");
std::string err;
CHECK(saveProject(path, d, err));
Document e;
CHECK(loadProject(path, e, err));
CHECK(subdivLevelText(e.mesh) == "Level 2/4");
CHECK(bitEqual(e.mesh.positions, levels[1]));
CHECK(e.mesh.facegroupAt(3) == 5);
for (int i : {0, 3, 2, 1}) {
CHECK(run(e, "subdiv_level", {{"level", double(i + 1)}}).ok);
CHECK(maxDistance(e.mesh.positions, levels[size_t(i)]) < 1e-6f);
}
// Saved through the command too (which folds pending edits in first), and a second Part keeps its own levels.
e.addPart(makeIcosphere(1), "Eye", true);
run(e, "subdiv_divide");
CHECK(run(e, "save_project", {{"path", path}}).ok);
Document f;
CHECK(loadProject(path, f, err));
CHECK(f.partCount() == 2);
CHECK(subdivLevelText(f.mesh) == "Level 2/2");
f.selectPart(0);
CHECK(subdivLevelText(f.mesh) == "Level 2/4");
CHECK(run(f, "subdiv_level", {{"level", 4.0}}).ok);
CHECK(maxDistance(f.mesh.positions, levels[3]) < 1e-6f);
std::filesystem::remove(path);
}
TEST(multires_parts_exports_and_info) {
Document d = dividedCube(2);
d.addPart(makeIcosphere(1), "Eye", true);
CHECK(subdivLevelCount(d.mesh) == 0);
d.selectPart(0);
CHECK(subdivLevelText(d.mesh) == "Level 3/3");
CHECK(run(d, "part_list").message.find("Level 3/3") != std::string::npos);
CHECK(run(d, "subdiv_info").message.find("Level 1: 108 triangles") != std::string::npos);
// Exports write the current level; subdiv_export the base.
const std::string cur = tempPath("sf_multires_cur.obj"), base = tempPath("sf_multires_base.obj");
d.parts[1].visible = false;
CHECK(run(d, "save_obj", {{"path", cur}}).ok);
CHECK(run(d, "subdiv_export", {{"path", base}}).ok);
CHECK(countObjFaces(cur, 4) == 54 * 16);
CHECK(countObjFaces(base, 4) == 54);
CHECK(subdivLevelText(d.mesh) == "Level 3/3"); // exporting the base doesn't change the scene
std::filesystem::remove(cur);
std::filesystem::remove(base);
// A topology change (remesh, the old flat subdivide) drops the levels.
CHECK(run(d, "subdivide").ok);
CHECK(subdivLevelCount(d.mesh) == 0);
CHECK(run(d, "undo").ok);
CHECK(subdivLevelCount(d.mesh) == 3);
}