QuadricEdgeCollapse Namespace Reference

Classes
struct	CopyEdgeInfo
struct	EdgeInfo
struct	Error
class	SymMat
struct	TriangleInfo
struct	VertexInfo

Typedefs
using	Vertices = std::vector< stl_vertex >
using	Triangle = stl_triangle_vertex_indices
using	Indices = std::vector< stl_triangle_vertex_indices >
using	ThrowOnCancel = std::function< void(void)>
using	StatusFn = std::function< void(int)>
using	Errors = std::vector< Error >
using	TriangleInfos = std::vector< TriangleInfo >
using	VertexInfos = std::vector< VertexInfo >
using	EdgeInfos = std::vector< EdgeInfo >
using	CopyEdgeInfos = std::vector< CopyEdgeInfo >

Functions
Vec3d	create_normal (const Triangle &triangle, const Vertices &vertices)
std::array< Vec3d, 3 >	create_vertices (uint32_t id_v1, uint32_t id_v2, const Vertices &vertices)
std::array< double, 3 >	vertices_error (const SymMat &q, const std::array< Vec3d, 3 > &vertices)
double	calculate_determinant (const SymMat &q)
double	calculate_error (uint32_t id_v1, uint32_t id_v2, const SymMat &q, const Vertices &vertices)
Vec3f	calculate_vertex (uint32_t id_v1, uint32_t id_v2, const SymMat &q, const Vertices &vertices)
Vec3d	calculate_vertex (double det, const SymMat &q)
double	vertex_error (const SymMat &q, const Vec3d &vertex)
SymMat	create_quadric (const Triangle &t, const Vec3d &n, const Vertices &vertices)
std::tuple< TriangleInfos, VertexInfos, EdgeInfos, Errors >	init (const indexed_triangle_set &its, ThrowOnCancel &throw_on_cancel, StatusFn &status_fn)
std::optional< uint32_t >	find_triangle_index1 (uint32_t vi, const VertexInfo &v_info, uint32_t ti, const EdgeInfos &e_infos, const Indices &indices)
void	reorder_edges (EdgeInfos &e_infos, const VertexInfo &v_info, uint32_t ti0, uint32_t ti1)
bool	is_flipped (const Vec3f &new_vertex, uint32_t ti0, uint32_t ti1, const VertexInfo &v_info, const TriangleInfos &t_infos, const EdgeInfos &e_infos, const indexed_triangle_set &its)
bool	degenerate (uint32_t vi, uint32_t ti0, uint32_t ti1, const VertexInfo &v_info, const EdgeInfos &e_infos, const Indices &indices)
bool	create_no_volume (uint32_t vi0, uint32_t vi1, uint32_t ti0, uint32_t ti1, const VertexInfo &v_info0, const VertexInfo &v_info1, const EdgeInfos &e_infos, const Indices &indices)
Vec3d	calculate_3errors (const Triangle &t, const Vertices &vertices, const VertexInfos &v_infos)
Error	calculate_error (uint32_t ti, const Triangle &t, const Vertices &vertices, const VertexInfos &v_infos, unsigned char &min_index)
void	remove_triangle (EdgeInfos &e_infos, VertexInfo &v_info, uint32_t ti)
void	change_neighbors (EdgeInfos &e_infos, VertexInfos &v_infos, uint32_t ti0, uint32_t ti1, uint32_t vi0, uint32_t vi1, uint32_t vi_top0, const Triangle &t1, CopyEdgeInfos &infos, EdgeInfos &e_infos1)
void	compact (const VertexInfos &v_infos, const TriangleInfos &t_infos, const EdgeInfos &e_infos, indexed_triangle_set &its)

Variables
const uint32_t	check_cancel_period = 16
const size_t	max_triangle_count_for_one_vertex = 50
const int	status_init_size = 10
const int	status_normal_size = 25
const int	status_sum_quadric = 25
const int	status_set_offsets = 10
const int	status_calc_errors = 30
const int	status_create_refs = 10

Typedef Documentation

CopyEdgeInfos

using QuadricEdgeCollapse::CopyEdgeInfos = typedef std::vector<CopyEdgeInfo>

EdgeInfos

using QuadricEdgeCollapse::EdgeInfos = typedef std::vector<EdgeInfo>

Errors

using QuadricEdgeCollapse::Errors = typedef std::vector<Error>

Indices

using QuadricEdgeCollapse::Indices = typedef std::vector<stl_triangle_vertex_indices>

StatusFn

using QuadricEdgeCollapse::StatusFn = typedef std::function<void(int)>

ThrowOnCancel

using QuadricEdgeCollapse::ThrowOnCancel = typedef std::function<void(void)>

Triangle

using QuadricEdgeCollapse::Triangle = typedef stl_triangle_vertex_indices

TriangleInfos

using QuadricEdgeCollapse::TriangleInfos = typedef std::vector<TriangleInfo>

VertexInfos

using QuadricEdgeCollapse::VertexInfos = typedef std::vector<VertexInfo>

Vertices

using QuadricEdgeCollapse::Vertices = typedef std::vector<stl_vertex>

Function Documentation

calculate_3errors()

Vec3d QuadricEdgeCollapse::calculate_3errors	(	const Triangle &	t,
		const Vertices &	vertices,
		const VertexInfos &	v_infos
	)

{
    Vec3d error;
    for (size_t j = 0; j < 3; ++j) {
        size_t   j2  = (j == 2) ? 0 : (j + 1);
        uint32_t vi0 = t[j];
        uint32_t vi1 = t[j2];
        SymMat   q(v_infos[vi0].q); // copy
        q += v_infos[vi1].q;
        error[j] = calculate_error(vi0, vi1, q, vertices);
    }
    return error;
}

References calculate_error(), and error.

Referenced by calculate_error(), and Slic3r::its_quadric_edge_collapse().

Here is the call graph for this function:

Here is the caller graph for this function:

calculate_determinant()

double QuadricEdgeCollapse::calculate_determinant

(

const SymMat &

q

)

{
    return q.det(0, 1, 2, 1, 4, 5, 2, 5, 7);
}

References QuadricEdgeCollapse::SymMat::det().

Referenced by calculate_error(), and calculate_vertex().

Here is the call graph for this function:

Here is the caller graph for this function:

calculate_error() [1/2]

double QuadricEdgeCollapse::calculate_error	(	uint32_t	id_v1,
		uint32_t	id_v2,
		const SymMat &	q,
		const Vertices &	vertices
	)

{
    double det = calculate_determinant(q);
    if (std::abs(det) < std::numeric_limits<double>::epsilon()) {
        // can't divide by zero
        auto verts  = create_vertices(id_v1, id_v2, vertices);
        auto errors = vertices_error(q, verts);
        return *std::min_element(std::begin(errors), std::end(errors));
    }
    Vec3d vertex = calculate_vertex(det, q);
    return vertex_error(q, vertex);
}

References calculate_determinant(), calculate_vertex(), create_vertices(), vertex_error(), and vertices_error().

Referenced by calculate_3errors(), and Slic3r::its_quadric_edge_collapse().

Here is the call graph for this function:

Here is the caller graph for this function:

calculate_error() [2/2]

Error QuadricEdgeCollapse::calculate_error	(	uint32_t	ti,
		const Triangle &	t,
		const Vertices &	vertices,
		const VertexInfos &	v_infos,
		unsigned char &	min_index
	)

{
    Vec3d error = calculate_3errors(t, vertices, v_infos);
    // select min error
    min_index = (error[0] < error[1]) ? ((error[0] < error[2]) ? 0 : 2) :
                                        ((error[1] < error[2]) ? 1 : 2);
    return Error(static_cast<float>(error[min_index]), ti);    
}

References calculate_3errors(), and error.

Here is the call graph for this function:

calculate_vertex() [1/2]

Vec3d QuadricEdgeCollapse::calculate_vertex	(	double	det,
		const SymMat &	q
	)

                                                                       {
    double det_1 = -1 / det;
    double det_x = q.det(1, 2, 3, 4, 5, 6, 5, 7, 8); // vx = A41/det(q_delta)
    double det_y = q.det(0, 2, 3, 1, 5, 6, 2, 7, 8); // vy = A42/det(q_delta)
    double det_z = q.det(0, 1, 3, 1, 4, 6, 2, 5, 8); // vz = A43/det(q_delta)
    return Vec3d(det_1 * det_x, -det_1 * det_y, det_1 * det_z);
}

References QuadricEdgeCollapse::SymMat::det().

Here is the call graph for this function:

calculate_vertex() [2/2]

Vec3f QuadricEdgeCollapse::calculate_vertex	(	uint32_t	id_v1,
		uint32_t	id_v2,
		const SymMat &	q,
		const Vertices &	vertices
	)

{
    double det = calculate_determinant(q);
    if (std::abs(det) < std::numeric_limits<double>::epsilon()) {
        // can't divide by zero
        auto verts  = create_vertices(id_v1, id_v2, vertices);
        auto errors = vertices_error(q, verts);
        auto mit    = std::min_element(std::begin(errors), std::end(errors));
        return verts[mit - std::begin(errors)].cast<float>();
    }
    return calculate_vertex(det, q).cast<float>();
}

References calculate_determinant(), calculate_vertex(), create_vertices(), and vertices_error().

Referenced by calculate_error(), calculate_vertex(), and Slic3r::its_quadric_edge_collapse().

Here is the call graph for this function:

Here is the caller graph for this function:

change_neighbors()

void QuadricEdgeCollapse::change_neighbors	(	EdgeInfos &	e_infos,
		VertexInfos &	v_infos,
		uint32_t	ti0,
		uint32_t	ti1,
		uint32_t	vi0,
		uint32_t	vi1,
		uint32_t	vi_top0,
		const Triangle &	t1,
		CopyEdgeInfos &	infos,
		EdgeInfos &	e_infos1
	)

{
    // have to copy Edge info from higher vertex index into smaller
    assert(vi0 < vi1);
    
    // vertex index of triangle 1 which is not vi0 nor vi1
    uint32_t vi_top1 = t1[0];
    if (vi_top1 == vi0 || vi_top1 == vi1) {
        vi_top1 = t1[1];
        if (vi_top1 == vi0 || vi_top1 == vi1) vi_top1 = t1[2];
    }
 
    remove_triangle(e_infos, v_infos[vi_top0], ti0);
    remove_triangle(e_infos, v_infos[vi_top1], ti1);
 
    VertexInfo &v_info0 = v_infos[vi0];
    VertexInfo &v_info1 = v_infos[vi1];
 
    uint32_t new_triangle_count = v_info0.count + v_info1.count - 4;
    remove_triangle(e_infos, v_info0, ti0);
    remove_triangle(e_infos, v_info0, ti1);
 
    // copy second's edge infos out of e_infos, to free size
    e_infos1.clear();
    e_infos1.reserve(v_info1.count - 2);
    uint32_t v_info_s_end = v_info1.start + v_info1.count;
    for (uint32_t ei = v_info1.start; ei < v_info_s_end; ++ei) {
        const EdgeInfo &e_info = e_infos[ei];
        if (e_info.t_index == ti0) continue;
        if (e_info.t_index == ti1) continue;
        e_infos1.emplace_back(e_info);
    }
    v_info1.count = 0;
 
    uint32_t need = (new_triangle_count < v_info0.count)? 0:
                  (new_triangle_count - v_info0.count);
 
    uint32_t      act_vi     = vi0 + 1;
    VertexInfo *act_v_info = &v_infos[act_vi];
    uint32_t      act_start  = act_v_info->start;
    uint32_t      last_end   = v_info0.start + v_info0.count;
 
    infos.clear();
    infos.reserve(need);
 
    while (true) {
        uint32_t save = act_start - last_end;
        if (save > 0) {
            if (save >= need) break;
            need -= save;
            infos.emplace_back(act_v_info->start, act_v_info->count, need);
        } else {
            infos.back().count += act_v_info->count;
        }
        last_end = act_v_info->start + act_v_info->count;
        act_v_info->start += need; 
        ++act_vi;
        if (act_vi < v_infos.size()) {
            act_v_info = &v_infos[act_vi];
            act_start  = act_v_info->start;
        } else
            act_start = e_infos.size(); // fix for edge between last two triangles
    }
 
    // copy by c_infos
    for (uint32_t i = infos.size(); i > 0; --i) {
        const CopyEdgeInfo &c_info = infos[i - 1];
        for (uint32_t ei = c_info.start + c_info.count - 1; ei >= c_info.start; --ei)
            e_infos[ei + c_info.move] = e_infos[ei]; // copy
    }
 
    // copy triangle from first info into second
    for (uint32_t ei_s = 0; ei_s < e_infos1.size(); ++ei_s) {
        uint32_t ei_f = v_info0.start + v_info0.count;
        e_infos[ei_f] = e_infos1[ei_s]; // copy
        ++v_info0.count;
    }
}

References QuadricEdgeCollapse::VertexInfo::count, QuadricEdgeCollapse::CopyEdgeInfo::count, QuadricEdgeCollapse::CopyEdgeInfo::move, remove_triangle(), save(), QuadricEdgeCollapse::VertexInfo::start, QuadricEdgeCollapse::CopyEdgeInfo::start, and QuadricEdgeCollapse::EdgeInfo::t_index.

Referenced by Slic3r::its_quadric_edge_collapse().

Here is the call graph for this function:

Here is the caller graph for this function:

compact()

void QuadricEdgeCollapse::compact	(	const VertexInfos &	v_infos,
		const TriangleInfos &	t_infos,
		const EdgeInfos &	e_infos,
		indexed_triangle_set &	its
	)

{
    uint32_t vi_new = 0;
    for (uint32_t vi = 0; vi < v_infos.size(); ++vi) {
        const VertexInfo &v_info = v_infos[vi];
        if (v_info.is_deleted()) continue; // deleted
        uint32_t e_info_end = v_info.start + v_info.count;
        for (uint32_t ei = v_info.start; ei < e_info_end; ++ei) { 
            const EdgeInfo &e_info = e_infos[ei];
            // change vertex index
            its.indices[e_info.t_index][e_info.edge] = vi_new;
        }
        // compact vertices
        its.vertices[vi_new++] = its.vertices[vi];
    }
    // remove vertices tail
    its.vertices.erase(its.vertices.begin() + vi_new, its.vertices.end());
 
    uint32_t ti_new = 0;
    for (uint32_t ti = 0; ti < t_infos.size(); ti++) { 
        const TriangleInfo &t_info = t_infos[ti];
        if (t_info.is_deleted()) continue;
        its.indices[ti_new++] = its.indices[ti];
    }
    its.indices.erase(its.indices.begin() + ti_new, its.indices.end());
}

References QuadricEdgeCollapse::VertexInfo::count, QuadricEdgeCollapse::EdgeInfo::edge, indexed_triangle_set::indices, QuadricEdgeCollapse::TriangleInfo::is_deleted(), QuadricEdgeCollapse::VertexInfo::is_deleted(), QuadricEdgeCollapse::VertexInfo::start, QuadricEdgeCollapse::EdgeInfo::t_index, and indexed_triangle_set::vertices.

Referenced by Slic3r::its_quadric_edge_collapse().

Here is the call graph for this function:

Here is the caller graph for this function:

create_no_volume()

bool QuadricEdgeCollapse::create_no_volume	(	uint32_t	vi0,
		uint32_t	vi1,
		uint32_t	ti0,
		uint32_t	ti1,
		const VertexInfo &	v_info0,
		const VertexInfo &	v_info1,
		const EdgeInfos &	e_infos,
		const Indices &	indices
	)

{
    // check that triangles around vertex0 doesn't have half edge
    // with opposit order in set of triangles around vertex1
    // protect from creation of two triangles with oposit order - no volume space
    size_t v_info0_end = v_info0.start + v_info0.count - 2;
    size_t v_info1_end = v_info1.start + v_info1.count - 2;
    for (size_t ei0 = v_info0.start; ei0 < v_info0_end; ++ei0) {
        const EdgeInfo &e_info0 = e_infos[ei0];
        const Triangle &t0 = indices[e_info0.t_index];
        // edge CCW vertex indices are t0vi0, t0vi1
        size_t t0i = 0;
        uint32_t t0vi0 = static_cast<uint32_t>(t0[t0i]);
        if (t0vi0 == vi0) { 
            ++t0i; 
            t0vi0 = static_cast<uint32_t>(t0[t0i]);
        }
        ++t0i;
        uint32_t t0vi1 = static_cast<uint32_t>(t0[t0i]);
        if (t0vi1 == vi0) { 
            ++t0i;
            t0vi1 = static_cast<uint32_t>(t0[t0i]);
        }
        for (size_t ei1 = v_info1.start; ei1 < v_info1_end; ++ei1) {
            const EdgeInfo &e_info1 = e_infos[ei1];
            const Triangle &t1 = indices[e_info1.t_index];
            size_t t1i = 0;
            for (; t1i < 3; ++t1i) if (static_cast<uint32_t>(t1[t1i]) == t0vi1) break;            
            if (t1i >= 3) continue; // without vertex index from triangle 0
            // check if second index is same too
            ++t1i;
            if (t1i == 3) t1i = 0; // triangle loop(modulo 3)
            if (static_cast<uint32_t>(t1[t1i]) == vi1) { 
                ++t1i; 
                if (t1i == 3) t1i = 0; // triangle loop(modulo 3)
            }
            if (static_cast<uint32_t>(t1[t1i]) == t0vi0) return true;
        }
    }
    return false;
}

References QuadricEdgeCollapse::VertexInfo::count, QuadricEdgeCollapse::VertexInfo::start, and QuadricEdgeCollapse::EdgeInfo::t_index.

Referenced by Slic3r::its_quadric_edge_collapse().

Here is the caller graph for this function:

create_normal()

Vec3d QuadricEdgeCollapse::create_normal	(	const Triangle &	triangle,
		const Vertices &	vertices
	)

{
    Vec3d v0 = vertices[triangle[0]].cast<double>();
    Vec3d v1 = vertices[triangle[1]].cast<double>();
    Vec3d v2 = vertices[triangle[2]].cast<double>();
    // n = triangle normal
    Vec3d n = (v1 - v0).cross(v2 - v0);
    n.normalize();
    return n;
}

References Slic3r::cross().

Referenced by Slic3r::its_quadric_edge_collapse().

Here is the call graph for this function:

Here is the caller graph for this function:

create_quadric()

SymMat QuadricEdgeCollapse::create_quadric	(	const Triangle &	t,
		const Vec3d &	n,
		const Vertices &	vertices
	)

{
    Vec3d v0 = vertices[t[0]].cast<double>();
    return SymMat(n.x(), n.y(), n.z(), -n.dot(v0));
}

create_vertices()

std::array< Vec3d, 3 > QuadricEdgeCollapse::create_vertices	(	uint32_t	id_v1,
		uint32_t	id_v2,
		const Vertices &	vertices
	)

{
    Vec3d v0 = vertices[id_v1].cast<double>();
    Vec3d v1 = vertices[id_v2].cast<double>();
    Vec3d vm = (v0 + v1) / 2.;
    return {v0, v1, vm};
}

Referenced by calculate_error(), and calculate_vertex().

Here is the caller graph for this function:

degenerate()

bool QuadricEdgeCollapse::degenerate	(	uint32_t	vi,
		uint32_t	ti0,
		uint32_t	ti1,
		const VertexInfo &	v_info,
		const EdgeInfos &	e_infos,
		const Indices &	indices
	)

{
    // check surround triangle do not contain vertex index
    // protect from creation of triangle with two same vertices inside
    size_t v_info_end = v_info.start + v_info.count - 2;
    for (size_t ei = v_info.start; ei < v_info_end; ++ei) {
        assert(ei < e_infos.size());
        const EdgeInfo &e_info = e_infos[ei];
        const Triangle &t = indices[e_info.t_index];
        for (size_t i = 0; i < 3; ++i)
            if (static_cast<uint32_t>(t[i]) == vi) return true;
    }
    return false;
}

References QuadricEdgeCollapse::VertexInfo::count, QuadricEdgeCollapse::VertexInfo::start, and QuadricEdgeCollapse::EdgeInfo::t_index.

Referenced by Slic3r::its_quadric_edge_collapse().

Here is the caller graph for this function:

find_triangle_index1()

std::optional< uint32_t > QuadricEdgeCollapse::find_triangle_index1	(	uint32_t	vi,
		const VertexInfo &	v_info,
		uint32_t	ti,
		const EdgeInfos &	e_infos,
		const Indices &	indices
	)

{
    coord_t vi_coord = static_cast<coord_t>(vi);
    uint32_t end = v_info.start + v_info.count;
    for (uint32_t ei = v_info.start; ei < end; ++ei) {
        const EdgeInfo &e_info = e_infos[ei];
        if (e_info.t_index == ti0) continue;
        const Triangle& t = indices[e_info.t_index];
        if (t[(e_info.edge + 1) % 3] == vi_coord || 
            t[(e_info.edge + 2) % 3] == vi_coord)
            return e_info.t_index;
    }
    // triangle0 is on border and do NOT have twin edge
    return {};
}

References QuadricEdgeCollapse::VertexInfo::count, QuadricEdgeCollapse::EdgeInfo::edge, QuadricEdgeCollapse::VertexInfo::start, and QuadricEdgeCollapse::EdgeInfo::t_index.

Referenced by Slic3r::its_quadric_edge_collapse().

Here is the caller graph for this function:

init()

std::tuple< TriangleInfos, VertexInfos, EdgeInfos, Errors > QuadricEdgeCollapse::init	(	const indexed_triangle_set &	its,
		ThrowOnCancel &	throw_on_cancel,
		StatusFn &	status_fn
	)

{
    int status_offset = 0;
    TriangleInfos t_infos(its.indices.size());
    VertexInfos   v_infos(its.vertices.size());
    {
        std::vector<SymMat> triangle_quadrics(its.indices.size());
        // calculate normals
        tbb::parallel_for(tbb::blocked_range<size_t>(0, its.indices.size()),
        [&](const tbb::blocked_range<size_t> &range) {
            for (size_t i = range.begin(); i < range.end(); ++i) {
                const Triangle &t      = its.indices[i];
                TriangleInfo &  t_info = t_infos[i];
                Vec3d           normal = create_normal(t, its.vertices);
                t_info.n = normal.cast<float>();
                triangle_quadrics[i] = create_quadric(t, normal, its.vertices);
                if (i % 1000000 == 0) {
                    throw_on_cancel();
                    status_fn(status_offset + (i * status_normal_size) / its.indices.size());
                }
            }
        }); // END parallel for
        status_offset += status_normal_size;
 
        // sum quadrics
        for (size_t i = 0; i < its.indices.size(); i++) {
            const Triangle &t = its.indices[i];
            const SymMat &  q = triangle_quadrics[i];
            for (size_t e = 0; e < 3; e++) {
                VertexInfo &v_info = v_infos[t[e]];
                v_info.q += q;
                ++v_info.count; // triangle count
            }
            if (i % 1000000 == 0) {
                throw_on_cancel();
                status_fn(status_offset + (i * status_sum_quadric) / its.indices.size());
            }
        }
        status_offset += status_sum_quadric;
    } // remove triangle quadrics
 
    // set offseted starts
    uint32_t triangle_start = 0;
    for (VertexInfo &v_info : v_infos) {
        v_info.start = triangle_start;
        triangle_start += v_info.count;
        // set filled vertex to zero
        v_info.count = 0;
    }
    assert(its.indices.size() * 3 == triangle_start);
 
    status_offset += status_set_offsets;
    throw_on_cancel();
    status_fn(status_offset);
 
    // calc error
    Errors errors(its.indices.size());
    tbb::parallel_for(tbb::blocked_range<size_t>(0, its.indices.size()),
    [&](const tbb::blocked_range<size_t> &range) {
        for (size_t i = range.begin(); i < range.end(); ++i) {
            const Triangle &t      = its.indices[i];
            TriangleInfo &  t_info = t_infos[i];
            errors[i] = calculate_error(i, t, its.vertices, v_infos, t_info.min_index);
            if (i % 1000000 == 0) {
                throw_on_cancel();
                status_fn(status_offset + (i * status_calc_errors) / its.indices.size());
            }
            if (i % 1000000 == 0) throw_on_cancel();
        }
    }); // END parallel for
 
    status_offset += status_calc_errors;
    
    // create reference
    EdgeInfos e_infos(its.indices.size() * 3);
    for (size_t i = 0; i < its.indices.size(); i++) {
        const Triangle &t = its.indices[i];       
        for (size_t j = 0; j < 3; ++j) {
            VertexInfo &v_info = v_infos[t[j]];
            size_t ei = v_info.start + v_info.count;
            assert(ei < e_infos.size());
            EdgeInfo &e_info = e_infos[ei];
            e_info.t_index  = i;
            e_info.edge      = j;
            ++v_info.count;
        }
        if (i % 1000000 == 0) {
            throw_on_cancel();
            status_fn(status_offset + (i * status_create_refs) / its.indices.size());
        }
    }
 
    throw_on_cancel();
    status_fn(100);
    return {t_infos, v_infos, e_infos, errors};
}

References QuadricEdgeCollapse::VertexInfo::count, indexed_triangle_set::indices, QuadricEdgeCollapse::VertexInfo::q, Slic3r::range(), status_normal_size, status_sum_quadric, and indexed_triangle_set::vertices.

Referenced by Slic3r::its_quadric_edge_collapse().

Here is the call graph for this function:

Here is the caller graph for this function:

is_flipped()

bool QuadricEdgeCollapse::is_flipped	(	const Vec3f &	new_vertex,
		uint32_t	ti0,
		uint32_t	ti1,
		const VertexInfo &	v_info,
		const TriangleInfos &	t_infos,
		const EdgeInfos &	e_infos,
		const indexed_triangle_set &	its
	)

{
    static const float triangle_beauty_threshold = 1.0f - std::numeric_limits<float>::epsilon();
    static const float dot_thr = 0.2f; // Value from simplify mesh cca 80 DEG
 
    // for each vertex triangles
    size_t v_info_end = v_info.start + v_info.count-2;
    for (size_t ei = v_info.start; ei < v_info_end; ++ei) {
        assert(ei < e_infos.size());
        const EdgeInfo &e_info = e_infos[ei];
        const Triangle &t      = its.indices[e_info.t_index];
        const Vec3f &normal = t_infos[e_info.t_index].n;
        const Vec3f &vf     = its.vertices[t[(e_info.edge + 1) % 3]];
        const Vec3f &vs     = its.vertices[t[(e_info.edge + 2) % 3]];
 
        Vec3f d1 = vf - new_vertex;
        d1.normalize();
        Vec3f d2 = vs - new_vertex;
        d2.normalize();
 
        float dot = d1.dot(d2);
        if (dot > triangle_beauty_threshold || dot < -triangle_beauty_threshold) { // OK, the new triangle is suspiciously ugly, but it can still be better than the original
            const Vec3f &v_orig = its.vertices[t[(e_info.edge) % 3]];
            Vec3f d1_orig = vf - v_orig;
            d1_orig.normalize();
            Vec3f d2_orig = vs - v_orig;
            d2_orig.normalize();
            if (std::fabs(d1_orig.dot(d2_orig)) < std::fabs(dot)) { // original was not that ugly, so return flipped
                return true;
            } // else original triangle was worse than the new, so don't discard the new yet
        }
        // IMPROVE: propagate new normal
        Vec3f n = d1.cross(d2);
        n.normalize(); 
        if(n.dot(normal) < dot_thr) return true;
    }
    return false;
}

References QuadricEdgeCollapse::VertexInfo::count, Slic3r::dot(), QuadricEdgeCollapse::EdgeInfo::edge, indexed_triangle_set::indices, QuadricEdgeCollapse::VertexInfo::start, QuadricEdgeCollapse::EdgeInfo::t_index, and indexed_triangle_set::vertices.

Referenced by Slic3r::its_quadric_edge_collapse().

Here is the call graph for this function:

Here is the caller graph for this function:

remove_triangle()

void QuadricEdgeCollapse::remove_triangle	(	EdgeInfos &	e_infos,
		VertexInfo &	v_info,
		uint32_t	ti
	)

{
    auto e_info     = e_infos.begin() + v_info.start;
    auto e_info_end = e_info + v_info.count - 1;
    for (; e_info != e_info_end; ++e_info) {
        if (e_info->t_index == ti) {
            *e_info = *e_info_end;
            --v_info.count;
            return;
        }
    }    
    assert(e_info_end->t_index == ti);
    // last triangle is ti
    --v_info.count;
}

References QuadricEdgeCollapse::VertexInfo::count, and QuadricEdgeCollapse::VertexInfo::start.

Referenced by change_neighbors().

Here is the caller graph for this function:

reorder_edges()

void QuadricEdgeCollapse::reorder_edges	(	EdgeInfos &	e_infos,
		const VertexInfo &	v_info,
		uint32_t	ti0,
		uint32_t	ti1
	)

{
    // swap edge info of ti0 and ti1 to end(last one and one before)
    size_t v_info_end = v_info.start + v_info.count - 2;
    EdgeInfo &e_info_ti0 = e_infos[v_info_end]; 
    EdgeInfo &e_info_ti1 = e_infos[v_info_end+1]; 
    bool      is_swaped  = false;
    for (size_t ei = v_info.start; ei < v_info_end; ++ei) {
        EdgeInfo &e_info = e_infos[ei];
        if (e_info.t_index == ti0) {
            std::swap(e_info, e_info_ti0);
            if (is_swaped) return;
            if (e_info.t_index == ti1) { 
                std::swap(e_info, e_info_ti1);
                return;
            }
            is_swaped = true;
        } else if (e_info.t_index == ti1) {
            std::swap(e_info, e_info_ti1);
            if (is_swaped) return;
            if (e_info.t_index == ti0) {
                std::swap(e_info, e_info_ti0);
                return;
            }
            is_swaped = true;
        }
    }
}

References QuadricEdgeCollapse::VertexInfo::count, QuadricEdgeCollapse::VertexInfo::start, and QuadricEdgeCollapse::EdgeInfo::t_index.

Referenced by Slic3r::its_quadric_edge_collapse().

Here is the caller graph for this function:

vertex_error()

double QuadricEdgeCollapse::vertex_error	(	const SymMat &	q,
		const Vec3d &	vertex
	)

{
    const double &x = vertex.x(), &y = vertex.y(), &z = vertex.z();
    return q[0] * x * x + 2 * q[1] * x * y + 2 * q[2] * x * z +
           2 * q[3] * x + q[4] * y * y + 2 * q[5] * y * z +
           2 * q[6] * y + q[7] * z * z + 2 * q[8] * z + q[9];
}

Referenced by calculate_error(), and vertices_error().

Here is the caller graph for this function:

vertices_error()

std::array< double, 3 > QuadricEdgeCollapse::vertices_error	(	const SymMat &	q,
		const std::array< Vec3d, 3 > &	vertices
	)

{
    return {
        vertex_error(q, vertices[0]), 
        vertex_error(q, vertices[1]),
        vertex_error(q, vertices[2])};
}

References vertex_error().

Referenced by calculate_error(), and calculate_vertex().

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

check_cancel_period

const uint32_t QuadricEdgeCollapse::check_cancel_period = 16

Referenced by Slic3r::its_quadric_edge_collapse().

max_triangle_count_for_one_vertex

const size_t QuadricEdgeCollapse::max_triangle_count_for_one_vertex = 50

Referenced by Slic3r::its_quadric_edge_collapse().

status_calc_errors

const int QuadricEdgeCollapse::status_calc_errors = 30

status_create_refs

const int QuadricEdgeCollapse::status_create_refs = 10

status_init_size

const int QuadricEdgeCollapse::status_init_size = 10

Referenced by Slic3r::its_quadric_edge_collapse().

status_normal_size

const int QuadricEdgeCollapse::status_normal_size = 25

Referenced by init().

status_set_offsets

const int QuadricEdgeCollapse::status_set_offsets = 10

status_sum_quadric

const int QuadricEdgeCollapse::status_sum_quadric = 25

Referenced by init().