Classes
struct	PassResult

Functions
double	edge_len_sq (const VertStore &v, int a, int b)
void	normalize_store_normals (VertStore &verts)
int	get_midpoint (VertStore &verts, QuantizedPointMap &cache, int a, int b, QuantizedPointMap *pos_canon_map)
PassResult	subdivide_pass (VertStore &verts, const std::vector< int > &indices, double max_edge_length, int safety_cap, const std::vector< uint8_t > &face_excluded, QuantizedPointMap *pos_canon_map, const std::vector< int > &face_parent_id, const SubdivideWithinFn &within)

Class Documentation

◆ Slic3r::TextureBake::anonymous_namespace{TextureBakeSubdivide.cpp}::PassResult

struct Slic3r::TextureBake::anonymous_namespace{TextureBakeSubdivide.cpp}::PassResult

Collaboration diagram for Slic3r::TextureBake::anonymous_namespace{TextureBakeSubdivide.cpp}::PassResult:

Class Members
bool	capped = false
bool	changed = false
vector< uint8_t >	face_excluded
vector< int >	face_parent_id
vector< int >	indices

Function Documentation

◆ edge_len_sq()

double Slic3r::TextureBake::anonymous_namespace{TextureBakeSubdivide.cpp}::edge_len_sq	(	const VertStore &	v,
		int	a,
		int	b )

{
    return (v.pos[size_t(a)] - v.pos[size_t(b)]).squaredNorm();
}

References edge_len_sq(), and Slic3r::TextureBake::VertStore::pos.

Referenced by edge_len_sq(), and subdivide_pass().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get_midpoint()

int Slic3r::TextureBake::anonymous_namespace{TextureBakeSubdivide.cpp}::get_midpoint	(	VertStore &	verts,
		QuantizedPointMap &	cache,
		int	a,
		int	b,
		QuantizedPointMap *	pos_canon_map )

{
    const int lo = std::min(a, b), hi = std::max(a, b);
    if (const int cached = cache.get_key(lo, hi, 0); cached != -1)
        return cached;
 
    const Vec3d  m  = (verts.pos[size_t(a)] + verts.pos[size_t(b)]) * 0.5;
    Vec3d        n  = verts.nrm[size_t(a)] + verts.nrm[size_t(b)];
    const double nl = n.norm();
    n = (nl > 0.0) ? Vec3d(n / nl) : verts.nrm[size_t(a)];
 
    const int idx = verts.push(m, n);
    if (!verts.wgt.empty())
        verts.wgt.push_back((verts.wgt[size_t(a)] + verts.wgt[size_t(b)]) * 0.5);
    if (!verts.canon.empty() && pos_canon_map != nullptr)
        verts.canon.push_back(pos_canon_map->get_or_set(float(m.x()), float(m.y()), float(m.z()), idx));
 
    cache.get_or_set_key(lo, hi, 0, idx);
    return idx;
}

References Slic3r::TextureBake::VertStore::canon, Slic3r::TextureBake::QuantizedPointMap::get_key(), get_midpoint(), Slic3r::TextureBake::QuantizedPointMap::get_or_set(), Slic3r::TextureBake::QuantizedPointMap::get_or_set_key(), Slic3r::TextureBake::VertStore::nrm, Slic3r::TextureBake::VertStore::pos, Slic3r::TextureBake::VertStore::push(), and Slic3r::TextureBake::VertStore::wgt.

Referenced by get_midpoint(), and subdivide_pass().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ normalize_store_normals()

void Slic3r::TextureBake::anonymous_namespace{TextureBakeSubdivide.cpp}::normalize_store_normals ( VertStore & verts )

{
    for (Vec3d &n : verts.nrm) {
        const double len = n.norm();
        n = (len > 0.0) ? Vec3d(n / len) : Vec3d(0.0, 0.0, 1.0);
    }
}

References normalize_store_normals(), and Slic3r::TextureBake::VertStore::nrm.

Referenced by normalize_store_normals().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ subdivide_pass()

PassResult Slic3r::TextureBake::anonymous_namespace{TextureBakeSubdivide.cpp}::subdivide_pass	(	VertStore &	verts,
		const std::vector< int > &	indices,
		double	max_edge_length,
		int	safety_cap,
		const std::vector< uint8_t > &	face_excluded,
		QuantizedPointMap *	pos_canon_map,
		const std::vector< int > &	face_parent_id,
		const SubdivideWithinFn &	within )

{
    PassResult   out;
    const double max_sq     = max_edge_length * max_edge_length;
    const size_t tri_count  = indices.size() / 3;
    const bool   have_canon = !verts.canon.empty();
 
    // Sized from the pass rather than grown from 64 k: a fine pass marks on the order of one edge per
    // triangle, and growing to that by doubling rehashes the whole table a dozen times.
    const size_t      expect = std::max<size_t>(size_t(1) << 16, tri_count);
    QuantizedPointMap mid_cache(1.0, expect);
    QuantizedPointMap split_edges(1.0, expect);
 
    // With canonical ids the key is the canonical *position* id, so split copies either side of a
    // sharp edge see one another's decision; without them the vertex index serves.
    const auto key_of = [&](int v) -> int64_t { return have_canon ? verts.canon[size_t(v)] : v; };
    const auto mark_edge = [&](int a, int b) {
        const int64_t u = key_of(a), v = key_of(b);
        if (u < v) split_edges.get_or_set_key(u, v, 0, 1);
        else       split_edges.get_or_set_key(v, u, 0, 1);
    };
    const auto is_marked = [&](int a, int b) {
        const int64_t u = key_of(a), v = key_of(b);
        return (u < v ? split_edges.get_key(u, v, 0) : split_edges.get_key(v, u, 0)) != -1;
    };
 
    // Graded, an edge splits while it is longer than max_edge_length + SUBDIVIDE_GRADE * (d - len/2),
    // d its midpoint's distance from the region; less half the length bounds the edge's own distance
    // from below, so the test errs toward splitting. Solved for d, that is the region coming within the
    // radius below. It reads the positions alone, so two triangles sharing the edge agree.
    const auto too_long = [&](int a, int b) {
        const double len_sq = edge_len_sq(verts, a, b);
        if (len_sq <= max_sq)
            return false;
        if (!within)
            return true;
        const double len = std::sqrt(len_sq);
        return within((verts.pos[size_t(a)] + verts.pos[size_t(b)]) * 0.5,
                      0.5 * len + (len - max_edge_length) / SUBDIVIDE_GRADE);
    };
 
    // Step 1. An excluded triangle marks none of its own edges while left alone, so its interior never
    // refines; its boundary edges are still marked by an included neighbour, and ungraded it follows
    // that split. Graded, one the refinement reaches marks its own too-long edges too, and so on
    // outward. An earlier bake's relief meets the paint along edges already at the target length, so
    // it is never reached and stays as it was.
    std::vector<uint8_t> want(tri_count, 0);
    tbb::parallel_for(tbb::blocked_range<size_t>(0, tri_count), [&](const tbb::blocked_range<size_t> &range) {
        for (size_t t = range.begin(); t < range.end(); ++t) {
            const int a = indices[t * 3], b = indices[t * 3 + 1], c = indices[t * 3 + 2];
            want[t] = uint8_t(too_long(a, b)) | uint8_t(too_long(b, c) << 1) | uint8_t(too_long(c, a) << 2);
        }
    });
    const auto mark_wanted = [&](size_t t) {
        const int a = indices[t * 3], b = indices[t * 3 + 1], c = indices[t * 3 + 2];
        if (want[t] & 1) mark_edge(a, b);
        if (want[t] & 2) mark_edge(b, c);
        if (want[t] & 4) mark_edge(c, a);
    };
    std::vector<size_t> unreached;
    for (size_t t = 0; t < tri_count; ++t)
        if (face_excluded.empty() || !face_excluded[t])
            mark_wanted(t);
        else if (within && want[t] != 0)
            unreached.push_back(t);
    // Marks only accumulate, so the order the reached triangles are taken in does not matter.
    for (size_t n = 0; n != unreached.size();) {
        n = unreached.size();
        unreached.erase(std::remove_if(unreached.begin(), unreached.end(), [&](size_t t) {
            const int  a = indices[t * 3], b = indices[t * 3 + 1], c = indices[t * 3 + 2];
            const bool reached = is_marked(a, b) || is_marked(b, c) || is_marked(c, a);
            if (reached)
                mark_wanted(t);
            return reached;
        }), unreached.end());
    }
    if (split_edges.size() == 0) {
        out.indices        = indices;
        out.face_excluded  = face_excluded;
        out.face_parent_id = face_parent_id;
        return out; // changed stays false: nothing left to refine
    }
 
    // Step 1.5. Read-only against the finished mark set, so it runs in parallel - and it keeps each
    // triangle's three marks (bit 0 = ab, 1 = bc, 2 = ca), so the serial rebuild below reads a byte
    // instead of probing the hash map three more times per triangle.
    std::vector<uint8_t> tri_marks(tri_count);
    const size_t         predicted = tbb::parallel_reduce(
        tbb::blocked_range<size_t>(0, tri_count), size_t(0),
        [&](const tbb::blocked_range<size_t> &range, size_t acc) {
            for (size_t t = range.begin(); t < range.end(); ++t) {
                const int     a = indices[t * 3], b = indices[t * 3 + 1], c = indices[t * 3 + 2];
                const uint8_t m = uint8_t(is_marked(a, b)) | uint8_t(is_marked(b, c) << 1) |
                                  uint8_t(is_marked(c, a) << 2);
                tri_marks[t]    = m;
                const int n     = (m & 1) + ((m >> 1) & 1) + ((m >> 2) & 1);
                acc += (n == 0) ? 1 : size_t(n + 1);
            }
            return acc;
        },
        std::plus<size_t>());
    if (predicted > size_t(safety_cap)) {
        out.indices        = indices;
        out.face_excluded  = face_excluded;
        out.face_parent_id = face_parent_id;
        out.capped         = true;
        return out; // coarser than asked for, but watertight
    }
 
    // Step 2.
    out.indices.resize(predicted * 3);
    if (!face_excluded.empty())
        out.face_excluded.resize(predicted);
    if (!face_parent_id.empty())
        out.face_parent_id.resize(predicted);
    size_t wi = 0, fi = 0;
    const auto emit_face_data = [&](uint8_t excl, int pid, int times) {
        for (int k = 0; k < times; ++k) {
            if (!out.face_excluded.empty())  out.face_excluded[fi]  = excl;
            if (!out.face_parent_id.empty()) out.face_parent_id[fi] = pid;
            ++fi;
        }
    };
    const auto emit = [&](int x, int y, int z) {
        out.indices[wi++] = x; out.indices[wi++] = y; out.indices[wi++] = z;
    };
 
    for (size_t t = 0; t < tri_count; ++t) {
        const int     a    = indices[t * 3], b = indices[t * 3 + 1], c = indices[t * 3 + 2];
        const uint8_t excl = face_excluded.empty() ? uint8_t(0) : face_excluded[t];
        const int     pid  = face_parent_id.empty() ? 0 : face_parent_id[t];
        const bool    s_ab = (tri_marks[t] & 1) != 0, s_bc = (tri_marks[t] & 2) != 0, s_ca = (tri_marks[t] & 4) != 0;
        const int     n    = int(s_ab) + int(s_bc) + int(s_ca);
 
        if (n == 0) {
            emit(a, b, c);
            emit_face_data(excl, pid, 1);
        } else if (n == 3) {
            //        a
            //       / \
            //     mCA-mAB
            //     / \ / \
            //    c--mBC--b
            const int m_ab = get_midpoint(verts, mid_cache, a, b, pos_canon_map);
            const int m_bc = get_midpoint(verts, mid_cache, b, c, pos_canon_map);
            const int m_ca = get_midpoint(verts, mid_cache, c, a, pos_canon_map);
            emit(a, m_ab, m_ca);
            emit(m_ab, b, m_bc);
            emit(m_ca, m_bc, c);
            emit(m_ab, m_bc, m_ca);
            emit_face_data(excl, pid, 4);
        } else if (n == 1) {
            if (s_ab) {
                const int m = get_midpoint(verts, mid_cache, a, b, pos_canon_map);
                emit(a, m, c);
                emit(m, b, c);
            } else if (s_bc) {
                const int m = get_midpoint(verts, mid_cache, b, c, pos_canon_map);
                emit(a, b, m);
                emit(a, m, c);
            } else {
                const int m = get_midpoint(verts, mid_cache, c, a, pos_canon_map);
                emit(a, b, m);
                emit(m, b, c);
            }
            emit_face_data(excl, pid, 2);
        } else {
            // A corner triangle on the untouched-edge vertex, then the remaining quadrilateral split
            // along the midpoint-to-midpoint diagonal, which keeps the winding consistent.
            //
            // A sliver parent propagates: that inner diagonal inherits half the short edge and hands
            // the sliver to two children per pass. No better diagonal exists - one avoiding the
            // midpoints must pass through one of them, giving a zero-area triangle. Regularization
            // removes such slivers before the mesh reaches here.
            if (!s_ab) { // fan from c
                const int m_bc = get_midpoint(verts, mid_cache, b, c, pos_canon_map);
                const int m_ca = get_midpoint(verts, mid_cache, c, a, pos_canon_map);
                emit(a, b, m_bc);
                emit(a, m_bc, m_ca);
                emit(c, m_ca, m_bc);
            } else if (!s_bc) { // fan from a
                const int m_ab = get_midpoint(verts, mid_cache, a, b, pos_canon_map);
                const int m_ca = get_midpoint(verts, mid_cache, c, a, pos_canon_map);
                emit(a, m_ab, m_ca);
                emit(m_ab, b, c);
                emit(m_ab, c, m_ca);
            } else { // fan from b
                const int m_ab = get_midpoint(verts, mid_cache, a, b, pos_canon_map);
                const int m_bc = get_midpoint(verts, mid_cache, b, c, pos_canon_map);
                emit(b, m_bc, m_ab);
                emit(a, m_ab, m_bc);
                emit(a, m_bc, c);
            }
            emit_face_data(excl, pid, 3);
        }
    }
 
    out.changed = true;
    return out;
}

Referenced by subdivide_pass().

Here is the call graph for this function:

Here is the caller graph for this function:

	OrcaSlicer latest OrcaSlicer

Classes

Functions

Class Documentation

◆ Slic3r::TextureBake::anonymous_namespace{TextureBakeSubdivide.cpp}::PassResult

Function Documentation

◆ edge_len_sq()

◆ get_midpoint()

◆ normalize_store_normals()

◆ subdivide_pass()