2292718584

Build Type

github

Committed by GitHub

Commit Message

<a href="https://github.com/pmp-library/pmp-library/commit/<a class=hub.com/pmp-library/pmp-library/commit/<a class="double-link" href="https://git"><a class=hub.com/pmp-library/pmp-library/commit/<a class="double-link" href="https://git"><a class=hub.com/pmp-library/pmp-library/commit/<a class="double-link" href="https://git"><a class=hub.com/pmp-library/pmp-library/commit/8cec43e727fb44fe9334e94e03d9ce10fb800685">8cec43e72">&lt;a href=&quot;https://github.com/pmp-library/pmp-library/commit/</a><a class="double-link" href="https://github.com/pmp-library/pmp-library/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/pmp-library/pmp-library/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/pmp-library/pmp-library/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/pmp-library/pmp-library/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/pmp-library/pmp-library/commit/8cec43e727fb44fe9334e94e03d9ce10fb800685">8cec43e72</a><a href="https://github.com/pmp-library/pmp-library/commit/8cec43e727fb44fe9334e94e03d9ce10fb800685">&quot;&gt;&amp;lt;a href=&amp;quot;https://github.com/pmp-library/pmp-library/commit/&lt;/a&gt;&lt;a class=&quot;double-link&quot; href=&quot;https://github.com/pmp-library/pmp-library/commit/&amp;lt;a class=&amp;quot;double-link&amp;quot; href=&amp;quot;https://git&quot;&gt;&amp;lt;a class=&lt;/a&gt;hub.com/pmp-library/pmp-library/commit/&amp;lt;a class=&amp;quot;double-link&amp;quot; href=&amp;quot;https://git&quot;&gt;&amp;lt;a class=&lt;/a&gt;hub.com/pmp-library/pmp-library/commit/&amp;lt;a class=&amp;quot;double-link&amp;quot; href=&amp;quot;https://git&quot;&gt;&amp;lt;a class=&lt;/a&gt;hub.com/pmp-library/pmp-library/commit/&amp;lt;a class=&amp;quot;double-link&amp;quot; href=&amp;quot;https://git&quot;&gt;&amp;lt;a class=&lt;/a&gt;hub.com/pmp-library/pmp-library/commit/8cec43e727fb44fe9334e94e03d9ce10fb800685&quot;&gt;8cec43e72&lt;/a&gt;&lt;a href=&quot;https://github.com/pmp-library/pmp-library/commit/8cec43e727fb44fe9334e94e03d9ce10fb800685&quot;&gt;&amp;quot;&amp;gt;&amp;amp;lt;a href=&amp;amp;quot;https://github.com/pmp-library/pmp-library/commit/&amp;lt;/a&amp;gt;&amp;lt;a class=&amp;quot... (continued)

Pull Request Pull Request #108: vec2 is float-based, and breaks double-precision compilation

Run Details

4 of 4 new or added lines in 1 file covered. (100.0%)

4205 of 4530 relevant lines covered (92.83%)

15037.23 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

95.55

/src/pmp/algorithms/SurfaceSimplification.cpp

// Copyright 2011-2020 the Polygon Mesh Processing Library developers.
// Distributed under a MIT-style license, see LICENSE.txt for details.

#include "pmp/algorithms/SurfaceSimplification.h"

#include <iterator>
#include <limits>

#include "pmp/algorithms/DistancePointTriangle.h"
#include "pmp/algorithms/SurfaceNormals.h"

namespace pmp {

SurfaceSimplification::SurfaceSimplification(SurfaceMesh& mesh)
    : mesh_(mesh), initialized_(false), queue_(nullptr)

{
    if (!mesh_.is_triangle_mesh())
        throw InvalidInputException("Input is not a pure triangle mesh!");

    aspect_ratio_ = 0;
    edge_length_ = 0;
    max_valence_ = 0;
    normal_deviation_ = 0;
    hausdorff_error_ = 0;

    seam_threshold_ = 1e-2;
    seam_angle_deviation_ = 0.99;

    // add properties
    vquadric_ = mesh_.add_vertex_property<Quadric>("v:quadric");
    texture_seams_ = mesh_.edge_property<bool>("e:seam", false);

    // get properties
    vpoint_ = mesh_.vertex_property<Point>("v:point");

    // compute face normals
    SurfaceNormals::compute_face_normals(mesh_);
    fnormal_ = mesh_.face_property<Normal>("f:normal");
}

SurfaceSimplification::~SurfaceSimplification()
{
    // remove added properties
    mesh_.remove_vertex_property(vquadric_);
    mesh_.remove_face_property(normal_cone_);
    mesh_.remove_face_property(face_points_);
    mesh_.remove_edge_property(texture_seams_);
}

void SurfaceSimplification::initialize(Scalar aspect_ratio, Scalar edge_length,
                                       unsigned int max_valence,
                                       Scalar normal_deviation,
                                       Scalar hausdorff_error,
                                       Scalar seam_threshold,
                                       Scalar seam_angle_deviation)
{
    // store parameters
    aspect_ratio_ = aspect_ratio;
    max_valence_ = max_valence;
    edge_length_ = edge_length;
    normal_deviation_ = normal_deviation / 180.0 * M_PI;
    hausdorff_error_ = hausdorff_error;
    seam_threshold_ = seam_threshold;
    seam_angle_deviation_ = (180.0 - seam_angle_deviation) / 180.0;

    // properties
    if (normal_deviation_ > 0.0)
        normal_cone_ = mesh_.face_property<NormalCone>("f:normalCone");
    else
        mesh_.remove_face_property(normal_cone_);
    if (hausdorff_error > 0.0)
        face_points_ = mesh_.face_property<Points>("f:points");
    else
        mesh_.remove_face_property(face_points_);

    // vertex selection
    has_selection_ = false;
    vselected_ = mesh_.get_vertex_property<bool>("v:selected");
    if (vselected_)
    {
        for (auto v : mesh_.vertices())
        {
            if (vselected_[v])
            {
                has_selection_ = true;
                break;
            }
        }
    }

    // feature vertices/edges
    has_features_ = false;
    vfeature_ = mesh_.get_vertex_property<bool>("v:feature");
    efeature_ = mesh_.get_edge_property<bool>("e:feature");
    if (vfeature_ && efeature_)
    {
        for (auto v : mesh_.vertices())
        {
            if (vfeature_[v])
            {
                has_features_ = true;
                break;
            }
        }
    }

    // initialize quadrics
    for (auto v : mesh_.vertices())
    {
        vquadric_[v].clear();

        if (!mesh_.is_isolated(v))
        {
            for (auto f : mesh_.faces(v))
            {
                vquadric_[v] += Quadric(fnormal_[f], vpoint_[v]);
            }
        }
    }

    // initialize normal cones
    if (normal_deviation_)
    {
        for (auto f : mesh_.faces())
        {
            normal_cone_[f] = NormalCone(fnormal_[f]);
        }
    }

    // initialize faces' point list
    if (hausdorff_error_)
    {
        for (auto f : mesh_.faces())
        {
            Points().swap(face_points_[f]); // free mem
        }
    }

    // detect texture seams
    auto texcoords = mesh_.get_halfedge_property<TexCoord>("h:tex");
    if (texcoords)
    {
        for (auto e : mesh_.edges())
        {
            // texcoords are stored in halfedge pointing towards a vertex
            Halfedge h0 = mesh_.halfedge(e, 0);
            Halfedge h1 = mesh_.halfedge(e, 1);     //opposite halfedge
            Halfedge h0p = mesh_.prev_halfedge(h0); // start point edge 0
            Halfedge h1p = mesh_.prev_halfedge(h1); // start point edge 1

            // if start or end points differ more than seam_threshold
            // the corresponding edge is a texture seam
            if (norm(texcoords[h1] - texcoords[h0p]) > seam_threshold_ ||
                norm(texcoords[h0] - texcoords[h1p]) > seam_threshold_)
            {
                texture_seams_[e] = true;
            }
            else
            {
                texture_seams_[e] = false;
            }
        }
    }

    initialized_ = true;
}

void SurfaceSimplification::simplify(unsigned int n_vertices)
{
    // make sure the decimater is initialized
    if (!initialized_)
        initialize();

    std::vector<Vertex> one_ring;

    // add properties for priority queue
    vpriority_ = mesh_.add_vertex_property<float>("v:prio");
    heap_pos_ = mesh_.add_vertex_property<int>("v:heap");
    vtarget_ = mesh_.add_vertex_property<Halfedge>("v:target");

    // build priority queue
    HeapInterface hi(vpriority_, heap_pos_);
    queue_ = new PriorityQueue(hi);
    queue_->reserve(mesh_.n_vertices());
    for (auto v : mesh_.vertices())
    {
        queue_->reset_heap_position(v);
        enqueue_vertex(v);
    }

    auto nv = mesh_.n_vertices();
    while (nv > n_vertices && !queue_->empty())
    {
        // get 1st element
        auto v = queue_->front();
        queue_->pop_front();
        auto h = vtarget_[v];
        CollapseData cd(mesh_, h);

        // check this (again)
        if (!mesh_.is_collapse_ok(h))
            continue;

        // are texture seams preserved?
        if (!texcoord_check(cd.v0v1))
            continue;

        // store one-ring
        one_ring.clear();
        for (auto vv : mesh_.vertices(cd.v0))
        {
            one_ring.push_back(vv);
        }

        // preprocessing -> adjust texcoords
        preprocess_collapse(cd);

        // perform collapse
        mesh_.collapse(h);
        --nv;

        // postprocessing, e.g., update quadrics
        postprocess_collapse(cd);

        // update queue
        for (auto vv : one_ring)
            enqueue_vertex(vv);
    }

    // clean up
    delete queue_;
    mesh_.garbage_collection();
    mesh_.remove_vertex_property(vpriority_);
    mesh_.remove_vertex_property(heap_pos_);
    mesh_.remove_vertex_property(vtarget_);
}

void SurfaceSimplification::enqueue_vertex(Vertex v)
{
    float prio, min_prio(std::numeric_limits<float>::max());
    Halfedge min_h;

    for (auto h : mesh_.halfedges(v))
    {
        CollapseData cd(mesh_, h);
        if (is_collapse_legal(cd))
        {
            prio = priority(cd);
            if (prio != -1.0 && prio < min_prio)
            {
                min_prio = prio;
                min_h = h;
            }
        }
    }

    // target found -> put vertex on heap
    if (min_h.is_valid())
    {
        vpriority_[v] = min_prio;
        vtarget_[v] = min_h;

        if (queue_->is_stored(v))
            queue_->update(v);
        else
            queue_->insert(v);
    }

    // not valid -> remove from heap
    else
    {
        if (queue_->is_stored(v))
            queue_->remove(v);

        vpriority_[v] = -1;
        vtarget_[v] = min_h;
    }
}

bool SurfaceSimplification::is_collapse_legal(const CollapseData& cd)
{
    // test selected vertices
    if (has_selection_)
    {
        if (!vselected_[cd.v0])
            return false;
    }

    // test features
    if (has_features_)
    {
        if (vfeature_[cd.v0] && !efeature_[mesh_.edge(cd.v0v1)])
            return false;

        if (cd.vl.is_valid() && efeature_[mesh_.edge(cd.vlv0)])
            return false;

        if (cd.vr.is_valid() && efeature_[mesh_.edge(cd.v0vr)])
            return false;
    }

    // do not collapse boundary vertices to interior vertices
    if (mesh_.is_boundary(cd.v0) && !mesh_.is_boundary(cd.v1))
        return false;

    // there should be at least 2 incident faces at v0
    if (mesh_.cw_rotated_halfedge(mesh_.cw_rotated_halfedge(cd.v0v1)) ==
        cd.v0v1)
        return false;

    // topological check
    if (!mesh_.is_collapse_ok(cd.v0v1))
        return false;

    // are texture seams preserved?
    if (!texcoord_check(cd.v0v1))
        return false;

    // check maximal valence
    if (max_valence_ > 0)
    {
        auto val0 = mesh_.valence(cd.v0);
        auto val1 = mesh_.valence(cd.v1);
        auto val = val0 + val1 - 1;
        if (cd.fl.is_valid())
            --val;
        if (cd.fr.is_valid())
            --val;
        if (val > max_valence_ && !(val < std::max(val0, val1)))
            return false;
    }

    // remember the positions of the endpoints
    const Point p0 = vpoint_[cd.v0];
    const Point p1 = vpoint_[cd.v1];

    // check for maximum edge length
    if (edge_length_)
    {
        for (auto v : mesh_.vertices(cd.v0))
        {
            if (v != cd.v1 && v != cd.vl && v != cd.vr)
            {
                if (norm(vpoint_[v] - p1) > edge_length_)
                    return false;
            }
        }
    }

    // check for flipping normals
    if (normal_deviation_ == 0.0)
    {
        vpoint_[cd.v0] = p1;
        for (auto f : mesh_.faces(cd.v0))
        {
            if (f != cd.fl && f != cd.fr)
            {
                Normal n0 = fnormal_[f];
                Normal n1 = SurfaceNormals::compute_face_normal(mesh_, f);
                if (dot(n0, n1) < 0.0)
                {
                    vpoint_[cd.v0] = p0;
                    return false;
                }
            }
        }
        vpoint_[cd.v0] = p0;
    }

    // check normal cone
    else
    {
        vpoint_[cd.v0] = p1;

        Face fll, frr;
        if (cd.vl.is_valid())
            fll = mesh_.face(
                mesh_.opposite_halfedge(mesh_.prev_halfedge(cd.v0v1)));
        if (cd.vr.is_valid())
            frr = mesh_.face(
                mesh_.opposite_halfedge(mesh_.next_halfedge(cd.v1v0)));

        for (auto f : mesh_.faces(cd.v0))
        {
            if (f != cd.fl && f != cd.fr)
            {
                NormalCone nc = normal_cone_[f];
                nc.merge(SurfaceNormals::compute_face_normal(mesh_, f));

                if (f == fll)
                    nc.merge(normal_cone_[cd.fl]);
                if (f == frr)
                    nc.merge(normal_cone_[cd.fr]);

                if (nc.angle() > 0.5 * normal_deviation_)
                {
                    vpoint_[cd.v0] = p0;
                    return false;
                }
            }
        }

        vpoint_[cd.v0] = p0;
    }

    // check aspect ratio
    if (aspect_ratio_)
    {
        Scalar ar0(0), ar1(0);

        for (auto f : mesh_.faces(cd.v0))
        {
            if (f != cd.fl && f != cd.fr)
            {
                // worst aspect ratio after collapse
                vpoint_[cd.v0] = p1;
                ar1 = std::max(ar1, aspect_ratio(f));
                // worst aspect ratio before collapse
                vpoint_[cd.v0] = p0;
                ar0 = std::max(ar0, aspect_ratio(f));
            }
        }

        // aspect ratio is too bad, and it does also not improve
        if (ar1 > aspect_ratio_ && ar1 > ar0)
            return false;
    }

    // check Hausdorff error
    if (hausdorff_error_)
    {
        Points points;
        bool ok;

        // collect points to be tested
        for (auto f : mesh_.faces(cd.v0))
        {
            std::copy(face_points_[f].begin(), face_points_[f].end(),
                      std::back_inserter(points));
        }
        points.push_back(vpoint_[cd.v0]);

        // test points against all faces
        vpoint_[cd.v0] = p1;
        for (auto point : points)
        {
            ok = false;

            for (auto f : mesh_.faces(cd.v0))
            {
                if (f != cd.fl && f != cd.fr)
                {
                    if (distance(f, point) < hausdorff_error_)
                    {
                        ok = true;
                        break;
                    }
                }
            }

            if (!ok)
            {
                vpoint_[cd.v0] = p0;
                return false;
            }
        }
        vpoint_[cd.v0] = p0;
    }

    // collapse passed all tests -> ok
    return true;
}

bool SurfaceSimplification::texcoord_check(Halfedge h)
{
    auto texcoords = mesh_.get_halfedge_property<TexCoord>("h:tex");
    if (!texcoords)
    {
        // no texture coordinates -> skip texture seam tests
        return true;
    }

    auto texture_seams = mesh_.edge_property<bool>("e:seam");
    if (!texture_seams)
    {
        // no seams found -> skip seam tests
        return true;
    }

    Halfedge o(mesh_.opposite_halfedge(h));
    Vertex v0(mesh_.to_vertex(o));

    if (!texture_seams[mesh_.edge(h)])
    {
        // v0v1 is not a texture seam
        for (auto he : mesh_.halfedges(v0))
        {
            if (he == h)
                continue;
            // Check if v0 is part of a texture seam
            // If yes, v0 must not be moved
            if (texture_seams[mesh_.edge(he)])
            {
                return false;
            }
        }

        return true;
    }

    // count number of adjacent texture seam edges
    int nr_seam_edges = 0;
    for (auto he : mesh_.halfedges(v0))
    {
        if (texture_seams[mesh_.edge(he)])
        {
            nr_seam_edges++;
        }
    }

    // if there are more than 2 seam edges at point v0
    // -> v0 must not be moved
    if (nr_seam_edges > 2)
    {
        return false;
    }

    Halfedge seam1 = h, seam2 = mesh_.prev_halfedge(h);
    while (seam2.idx() != o.idx())
    {
        if (texture_seams[mesh_.edge(seam2)])
        {
            auto s1 = normalize(texcoords[seam1] -
                                texcoords[mesh_.prev_halfedge(seam1)]);
            auto s2 = normalize(texcoords[seam2] -
                                texcoords[mesh_.prev_halfedge(seam2)]);

            // oppposite uvs
            Halfedge o_seam1 = mesh_.opposite_halfedge(seam1);
            Halfedge o_seam2 = mesh_.opposite_halfedge(seam2);
            auto o1 = normalize(texcoords[o_seam1] -
                                texcoords[mesh_.prev_halfedge(o_seam1)]);
            auto o2 = normalize(texcoords[o_seam2] -
                                texcoords[mesh_.prev_halfedge(o_seam2)]);

            // check if the angle between the seam edge to be collapsed and the
            // seam edge prolonged is smaller than the allowed deviation
            if (dot(s1, s2) < seam_angle_deviation_ ||
                dot(o1, o2) < seam_angle_deviation_)
            {
                // angle is too large -> don't collapse this edge
                return false;
            }
        }
        seam2 = mesh_.prev_halfedge(mesh_.opposite_halfedge(seam2));
    }

    // passed all tests
    return true;
}

float SurfaceSimplification::priority(const CollapseData& cd)
{
    // computer quadric error metric
    Quadric Q = vquadric_[cd.v0];
    Q += vquadric_[cd.v1];
    return Q(vpoint_[cd.v1]);
}

void SurfaceSimplification::preprocess_collapse(const CollapseData& cd)
{
    Halfedge h = cd.v0v1;
    Halfedge o = mesh_.opposite_halfedge(h);
    Halfedge v1v2, v2v1, v0v2;

    // move texcoords in correct halfedge before collapsing an edge
    auto texcoords = mesh_.get_halfedge_property<TexCoord>("h:tex");
    if (texcoords)
    {
        auto texture_seams = mesh_.edge_property<bool>("e:seam", false);
        Halfedge hit = h;
        bool is_first_side = true;

        // which texcoord must be saved depends
        // on the side of the texture seam
        for (size_t i = 0; i < mesh_.valence(mesh_.to_vertex(o)) - 1; ++i)
        {
            hit = mesh_.prev_halfedge(hit);
            if (is_first_side)
                texcoords[hit] = texcoords[h];
            else if (!is_first_side)
                texcoords[hit] = texcoords[mesh_.prev_halfedge(o)];
            if (texture_seams[mesh_.edge(hit)])
            {
                is_first_side = false;

                // loop case 1
                if (mesh_.to_vertex(mesh_.next_halfedge(h)) ==
                    mesh_.from_vertex(hit))
                {
                    v1v2 = mesh_.next_halfedge(h);
                    texcoords[mesh_.opposite_halfedge(v1v2)] = texcoords[hit];
                    texcoords[v1v2] = texcoords[mesh_.opposite_halfedge(hit)];
                    texture_seams[mesh_.edge(v1v2)] = true;
                }

                // loop case 2
                if (mesh_.to_vertex(mesh_.next_halfedge(o)) ==
                    mesh_.from_vertex(hit))
                {
                    v2v1 = mesh_.prev_halfedge(o);
                    v0v2 = mesh_.opposite_halfedge(hit);
                    texcoords[mesh_.opposite_halfedge(v2v1)] = texcoords[v0v2];
                    texcoords[v2v1] = texcoords[hit];
                    texture_seams[mesh_.edge(v2v1)] = true;
                }
            }
            hit = mesh_.opposite_halfedge(hit);
        }
    }
}

void SurfaceSimplification::postprocess_collapse(const CollapseData& cd)
{
    // update error quadrics
    vquadric_[cd.v1] += vquadric_[cd.v0];

    // update normal cones
    if (normal_deviation_)
    {
        for (auto f : mesh_.faces(cd.v1))
        {
            normal_cone_[f].merge(
                SurfaceNormals::compute_face_normal(mesh_, f));
        }

        if (cd.vl.is_valid())
        {
            Face f = mesh_.face(cd.v1vl);
            if (f.is_valid())
                normal_cone_[f].merge(normal_cone_[cd.fl]);
        }

        if (cd.vr.is_valid())
        {
            Face f = mesh_.face(cd.vrv1);
            if (f.is_valid())
                normal_cone_[f].merge(normal_cone_[cd.fr]);
        }
    }

    // update Hausdorff error
    if (hausdorff_error_)
    {
        Points points;

        // collect points to be distributed

        // points of v1's one-ring
        for (auto f : mesh_.faces(cd.v1))
        {
            std::copy(face_points_[f].begin(), face_points_[f].end(),
                      std::back_inserter(points));
            face_points_[f].clear();
        }

        // points of the 2 removed triangles
        if (cd.fl.is_valid())
        {
            std::copy(face_points_[cd.fl].begin(), face_points_[cd.fl].end(),
                      std::back_inserter(points));
            Points().swap(face_points_[cd.fl]); // free mem
        }
        if (cd.fr.is_valid())
        {
            std::copy(face_points_[cd.fr].begin(), face_points_[cd.fr].end(),
                      std::back_inserter(points));
            Points().swap(face_points_[cd.fr]); // free mem
        }

        // the removed vertex
        points.push_back(vpoint_[cd.v0]);

        // test points against all faces
        Scalar d, dd;
        Face ff;

        for (auto point : points)
        {
            dd = std::numeric_limits<Scalar>::max();

            for (auto f : mesh_.faces(cd.v1))
            {
                d = distance(f, point);
                if (d < dd)
                {
                    ff = f;
                    dd = d;
                }
            }

            face_points_[ff].push_back(point);
        }
    }
}

Scalar SurfaceSimplification::aspect_ratio(Face f) const
{
    // min height is area/maxLength
    // aspect ratio = length / height
    //              = length * length / area

    auto fvit = mesh_.vertices(f);

    const Point p0 = vpoint_[*fvit];
    const Point p1 = vpoint_[*(++fvit)];
    const Point p2 = vpoint_[*(++fvit)];

    const Point d0 = p0 - p1;
    const Point d1 = p1 - p2;
    const Point d2 = p2 - p0;

    const Scalar l0 = sqrnorm(d0);
    const Scalar l1 = sqrnorm(d1);
    const Scalar l2 = sqrnorm(d2);

    // max squared edge length
    const Scalar l = std::max(l0, std::max(l1, l2));

    // triangle area
    Scalar a = norm(cross(d0, d1));

    return l / a;
}

Scalar SurfaceSimplification::distance(Face f, const Point& p) const
{
    auto fvit = mesh_.vertices(f);

    const Point p0 = vpoint_[*fvit];
    const Point p1 = vpoint_[*(++fvit)];
    const Point p2 = vpoint_[*(++fvit)];

    Point n;

    return dist_point_triangle(p, p0, p1, p2, n);
}

SurfaceSimplification::CollapseData::CollapseData(SurfaceMesh& sm, Halfedge h)
    : mesh(sm)
{
    v0v1 = h;
    v1v0 = mesh.opposite_halfedge(v0v1);
    v0 = mesh.to_vertex(v1v0);
    v1 = mesh.to_vertex(v0v1);
    fl = mesh.face(v0v1);
    fr = mesh.face(v1v0);

    // get vl
    if (fl.is_valid())
    {
        v1vl = mesh.next_halfedge(v0v1);
        vlv0 = mesh.next_halfedge(v1vl);
        vl = mesh.to_vertex(v1vl);
    }

    // get vr
    if (fr.is_valid())
    {
        v0vr = mesh.next_halfedge(v1v0);
        vrv1 = mesh.prev_halfedge(v0vr);
        vr = mesh.from_vertex(vrv1);
    }
}

} // namespace pmp

1	// Copyright 2011-2020 the Polygon Mesh Processing Library developers.
2	// Distributed under a MIT-style license, see LICENSE.txt for details.
3
4	#include "pmp/algorithms/SurfaceSimplification.h"
5
6	#include <iterator>
7	#include <limits>
8
9	#include "pmp/algorithms/DistancePointTriangle.h"
10	#include "pmp/algorithms/SurfaceNormals.h"
11
12	namespace pmp {
13
14	SurfaceSimplification::SurfaceSimplification(SurfaceMesh& mesh)	3✔
15	: mesh_(mesh), initialized_(false), queue_(nullptr)	3✔
16
17	{
18	if (!mesh_.is_triangle_mesh())	3✔
19	throw InvalidInputException("Input is not a pure triangle mesh!");	×
20
21	aspect_ratio_ = 0;	3✔
22	edge_length_ = 0;	3✔
23	max_valence_ = 0;	3✔
24	normal_deviation_ = 0;	3✔
25	hausdorff_error_ = 0;	3✔
26
27	seam_threshold_ = 1e-2;	3✔
28	seam_angle_deviation_ = 0.99;	3✔
29
30	// add properties
31	vquadric_ = mesh_.add_vertex_property<Quadric>("v:quadric");	3✔
32	texture_seams_ = mesh_.edge_property<bool>("e:seam", false);	3✔
33
34	// get properties
35	vpoint_ = mesh_.vertex_property<Point>("v:point");	9✔
36
37	// compute face normals
38	SurfaceNormals::compute_face_normals(mesh_);	3✔
39	fnormal_ = mesh_.face_property<Normal>("f:normal");	9✔
40	}	3✔
41
42	SurfaceSimplification::~SurfaceSimplification()	6✔
43	{
44	// remove added properties
45	mesh_.remove_vertex_property(vquadric_);	3✔
46	mesh_.remove_face_property(normal_cone_);	3✔
47	mesh_.remove_face_property(face_points_);	3✔
48	mesh_.remove_edge_property(texture_seams_);	3✔
49	}	3✔
50
51	void SurfaceSimplification::initialize(Scalar aspect_ratio, Scalar edge_length,	3✔
52	unsigned int max_valence,
53	Scalar normal_deviation,
54	Scalar hausdorff_error,
55	Scalar seam_threshold,
56	Scalar seam_angle_deviation)
57	{
58	// store parameters
59	aspect_ratio_ = aspect_ratio;	3✔
60	max_valence_ = max_valence;	3✔
61	edge_length_ = edge_length;	3✔
62	normal_deviation_ = normal_deviation / 180.0 * M_PI;	3✔
63	hausdorff_error_ = hausdorff_error;	3✔
64	seam_threshold_ = seam_threshold;	3✔
65	seam_angle_deviation_ = (180.0 - seam_angle_deviation) / 180.0;	3✔
66
67	// properties
68	if (normal_deviation_ > 0.0)	3✔
69	normal_cone_ = mesh_.face_property<NormalCone>("f:normalCone");	6✔
70	else
71	mesh_.remove_face_property(normal_cone_);	1✔
72	if (hausdorff_error > 0.0)	3✔
73	face_points_ = mesh_.face_property<Points>("f:points");	1✔
74	else
75	mesh_.remove_face_property(face_points_);	2✔
76
77	// vertex selection
78	has_selection_ = false;	3✔
79	vselected_ = mesh_.get_vertex_property<bool>("v:selected");	3✔
80	if (vselected_)	3✔
81	{
82	for (auto v : mesh_.vertices())	×
83	{
84	if (vselected_[v])	×
85	{
86	has_selection_ = true;	×
87	break;	×
88	}
89	}
90	}
91
92	// feature vertices/edges
93	has_features_ = false;	3✔
94	vfeature_ = mesh_.get_vertex_property<bool>("v:feature");	3✔
95	efeature_ = mesh_.get_edge_property<bool>("e:feature");	3✔
96	if (vfeature_ && efeature_)	3✔
97	{
98	for (auto v : mesh_.vertices())	644✔
99	{
100	if (vfeature_[v])	643✔
101	{
102	has_features_ = true;	1✔
103	break;	1✔
104	}
105	}
106	}
107
108	// initialize quadrics
109	for (auto v : mesh_.vertices())	1,303✔
110	{
111	vquadric_[v].clear();	1,300✔
112
113	if (!mesh_.is_isolated(v))	1,300✔
114	{
115	for (auto f : mesh_.faces(v))	9,037✔
116	{
117	vquadric_[v] += Quadric(fnormal_[f], vpoint_[v]);	7,737✔
118	}
119	}
120	}
121
122	// initialize normal cones
123	if (normal_deviation_)	3✔
124	{
125	for (auto f : mesh_.faces())	1,301✔
126	{
127	normal_cone_[f] = NormalCone(fnormal_[f]);	1,299✔
128	}
129	}
130
131	// initialize faces' point list
132	if (hausdorff_error_)	3✔
133	{
134	for (auto f : mesh_.faces())	1,281✔
135	{
136	Points().swap(face_points_[f]); // free mem	1,280✔
137	}
138	}
139
140	// detect texture seams
141	auto texcoords = mesh_.get_halfedge_property<TexCoord>("h:tex");	3✔
142	if (texcoords)	3✔
143	{
144	for (auto e : mesh_.edges())	35✔
145	{
146	// texcoords are stored in halfedge pointing towards a vertex
147	Halfedge h0 = mesh_.halfedge(e, 0);	34✔
148	Halfedge h1 = mesh_.halfedge(e, 1); //opposite halfedge	34✔
149	Halfedge h0p = mesh_.prev_halfedge(h0); // start point edge 0	34✔
150	Halfedge h1p = mesh_.prev_halfedge(h1); // start point edge 1	34✔
151
152	// if start or end points differ more than seam_threshold
153	// the corresponding edge is a texture seam
154	if (norm(texcoords[h1] - texcoords[h0p]) > seam_threshold_ \|\|	53✔
155	norm(texcoords[h0] - texcoords[h1p]) > seam_threshold_)	53✔
156	{
157	texture_seams_[e] = true;	15✔
158	}
159	else
160	{
161	texture_seams_[e] = false;	19✔
162	}
163	}
164	}
165
166	initialized_ = true;	3✔
167	}	3✔
168
169	void SurfaceSimplification::simplify(unsigned int n_vertices)	3✔
170	{
171	// make sure the decimater is initialized
172	if (!initialized_)	3✔
173	initialize();	×
174
175	std::vector<Vertex> one_ring;	6✔
176
177	// add properties for priority queue
178	vpriority_ = mesh_.add_vertex_property<float>("v:prio");	3✔
179	heap_pos_ = mesh_.add_vertex_property<int>("v:heap");	3✔
180	vtarget_ = mesh_.add_vertex_property<Halfedge>("v:target");	3✔
181
182	// build priority queue
183	HeapInterface hi(vpriority_, heap_pos_);	3✔
184	queue_ = new PriorityQueue(hi);	3✔
185	queue_->reserve(mesh_.n_vertices());	3✔
186	for (auto v : mesh_.vertices())	1,303✔
187	{
188	queue_->reset_heap_position(v);	1,300✔
189	enqueue_vertex(v);	1,300✔
190	}
191
192	auto nv = mesh_.n_vertices();	3✔
193	while (nv > n_vertices && !queue_->empty())	1,178✔
194	{
195	// get 1st element
196	auto v = queue_->front();	1,175✔
197	queue_->pop_front();	1,175✔
198	auto h = vtarget_[v];	1,175✔
199	CollapseData cd(mesh_, h);	1,175✔
200
201	// check this (again)
202	if (!mesh_.is_collapse_ok(h))	1,175✔
203	continue;	×
204
205	// are texture seams preserved?
206	if (!texcoord_check(cd.v0v1))	1,175✔
207	continue;	×
208
209	// store one-ring
210	one_ring.clear();	1,175✔
211	for (auto vv : mesh_.vertices(cd.v0))	7,250✔
212	{
213	one_ring.push_back(vv);	6,075✔
214	}
215
216	// preprocessing -> adjust texcoords
217	preprocess_collapse(cd);	1,175✔
218
219	// perform collapse
220	mesh_.collapse(h);	1,175✔
221	--nv;	1,175✔
222
223	// postprocessing, e.g., update quadrics
224	postprocess_collapse(cd);	1,175✔
225
226	// update queue
227	for (auto vv : one_ring)	7,250✔
228	enqueue_vertex(vv);	6,075✔
229	}
230
231	// clean up
232	delete queue_;	3✔
233	mesh_.garbage_collection();	3✔
234	mesh_.remove_vertex_property(vpriority_);	3✔
235	mesh_.remove_vertex_property(heap_pos_);	3✔
236	mesh_.remove_vertex_property(vtarget_);	3✔
237	}	3✔
238
239	void SurfaceSimplification::enqueue_vertex(Vertex v)	7,375✔
240	{
241	float prio, min_prio(std::numeric_limits<float>::max());	7,375✔
242	Halfedge min_h;	7,375✔
243
244	for (auto h : mesh_.halfedges(v))	52,799✔
245	{
246	CollapseData cd(mesh_, h);	45,424✔
247	if (is_collapse_legal(cd))	45,424✔
248	{
249	prio = priority(cd);	14,547✔
250	if (prio != -1.0 && prio < min_prio)	14,547✔
251	{
252	min_prio = prio;	8,102✔
253	min_h = h;	8,102✔
254	}
255	}
256	}
257
258	// target found -> put vertex on heap
259	if (min_h.is_valid())	7,375✔
260	{
261	vpriority_[v] = min_prio;	5,301✔
262	vtarget_[v] = min_h;	5,301✔
263
264	if (queue_->is_stored(v))	5,301✔
265	queue_->update(v);	3,696✔
266	else
267	queue_->insert(v);	1,605✔
268	}
269
270	// not valid -> remove from heap
271	else
272	{
273	if (queue_->is_stored(v))	2,074✔
274	queue_->remove(v);	430✔
275
276	vpriority_[v] = -1;	2,074✔
277	vtarget_[v] = min_h;	2,074✔
278	}
279	}	7,375✔
280
281	bool SurfaceSimplification::is_collapse_legal(const CollapseData& cd)	45,424✔
282	{
283	// test selected vertices
284	if (has_selection_)	45,424✔
285	{
286	if (!vselected_[cd.v0])	×
287	return false;	×
288	}
289
290	// test features
291	if (has_features_)	45,424✔
292	{
293	if (vfeature_[cd.v0] && !efeature_[mesh_.edge(cd.v0v1)])	24,066✔
294	return false;	7,732✔
295
296	if (cd.vl.is_valid() && efeature_[mesh_.edge(cd.vlv0)])	16,334✔
297	return false;	1,104✔
298
299	if (cd.vr.is_valid() && efeature_[mesh_.edge(cd.v0vr)])	15,230✔
300	return false;	344✔
301	}
302
303	// do not collapse boundary vertices to interior vertices
304	if (mesh_.is_boundary(cd.v0) && !mesh_.is_boundary(cd.v1))	36,244✔
305	return false;	28✔
306
307	// there should be at least 2 incident faces at v0
308	if (mesh_.cw_rotated_halfedge(mesh_.cw_rotated_halfedge(cd.v0v1)) ==	36,216✔
309	cd.v0v1)
310	return false;	4✔
311
312	// topological check
313	if (!mesh_.is_collapse_ok(cd.v0v1))	36,212✔
314	return false;	99✔
315
316	// are texture seams preserved?
317	if (!texcoord_check(cd.v0v1))	36,113✔
318	return false;	86✔
319
320	// check maximal valence
321	if (max_valence_ > 0)	36,027✔
322	{
323	auto val0 = mesh_.valence(cd.v0);	21,160✔
324	auto val1 = mesh_.valence(cd.v1);	21,160✔
325	auto val = val0 + val1 - 1;	21,160✔
326	if (cd.fl.is_valid())	21,160✔
327	--val;	21,160✔
328	if (cd.fr.is_valid())	21,160✔
329	--val;	21,160✔
330	if (val > max_valence_ && !(val < std::max(val0, val1)))	21,160✔
331	return false;	4,966✔
332	}
333
334	// remember the positions of the endpoints
335	const Point p0 = vpoint_[cd.v0];	31,061✔
336	const Point p1 = vpoint_[cd.v1];	31,061✔
337
338	// check for maximum edge length
339	if (edge_length_)	31,061✔
340	{
341	for (auto v : mesh_.vertices(cd.v0))	99,925✔
342	{
343	if (v != cd.v1 && v != cd.vl && v != cd.vr)	86,747✔
344	{
345	if (norm(vpoint_[v] - p1) > edge_length_)	57,326✔
346	return false;	3,016✔
347	}
348	}
349	}
350
351	// check for flipping normals
352	if (normal_deviation_ == 0.0)	28,045✔
353	{
354	vpoint_[cd.v0] = p1;	14,848✔
355	for (auto f : mesh_.faces(cd.v0))	99,373✔
356	{
357	if (f != cd.fl && f != cd.fr)	86,418✔
358	{
359	Normal n0 = fnormal_[f];	58,673✔
360	Normal n1 = SurfaceNormals::compute_face_normal(mesh_, f);	58,673✔
361	if (dot(n0, n1) < 0.0)	58,673✔
362	{
363	vpoint_[cd.v0] = p0;	1,893✔
364	return false;	1,893✔
365	}
366	}
367	}
368	vpoint_[cd.v0] = p0;	12,955✔
369	}
370
371	// check normal cone
372	else
373	{
374	vpoint_[cd.v0] = p1;	13,197✔
375
376	Face fll, frr;	13,197✔
377	if (cd.vl.is_valid())	13,197✔
378	fll = mesh_.face(	13,197✔
379	mesh_.opposite_halfedge(mesh_.prev_halfedge(cd.v0v1)));	13,197✔
380	if (cd.vr.is_valid())	13,197✔
381	frr = mesh_.face(	13,197✔
382	mesh_.opposite_halfedge(mesh_.next_halfedge(cd.v1v0)));	13,197✔
383
384	for (auto f : mesh_.faces(cd.v0))	67,461✔
385	{
386	if (f != cd.fl && f != cd.fr)	59,140✔
387	{
388	NormalCone nc = normal_cone_[f];	39,015✔
389	nc.merge(SurfaceNormals::compute_face_normal(mesh_, f));	39,015✔
390
391	if (f == fll)	39,015✔
392	nc.merge(normal_cone_[cd.fl]);	11,336✔
393	if (f == frr)	39,015✔
394	nc.merge(normal_cone_[cd.fr]);	9,969✔
395
396	if (nc.angle() > 0.5 * normal_deviation_)	39,015✔
397	{
398	vpoint_[cd.v0] = p0;	4,876✔
399	return false;	4,876✔
400	}
401	}
402	}
403
404	vpoint_[cd.v0] = p0;	8,321✔
405	}
406
407	// check aspect ratio
408	if (aspect_ratio_)	21,276✔
409	{
410	Scalar ar0(0), ar1(0);	21,276✔
411
412	for (auto f : mesh_.faces(cd.v0))	147,781✔
413	{
414	if (f != cd.fl && f != cd.fr)	126,505✔
415	{
416	// worst aspect ratio after collapse
417	vpoint_[cd.v0] = p1;	83,953✔
418	ar1 = std::max(ar1, aspect_ratio(f));	83,953✔
419	// worst aspect ratio before collapse
420	vpoint_[cd.v0] = p0;	83,953✔
421	ar0 = std::max(ar0, aspect_ratio(f));	83,953✔
422	}
423	}
424
425	// aspect ratio is too bad, and it does also not improve
426	if (ar1 > aspect_ratio_ && ar1 > ar0)	21,276✔
427	return false;	6,729✔
428	}
429
430	// check Hausdorff error
431	if (hausdorff_error_)	14,547✔
432	{
433	Points points;	6,749✔
434	bool ok;
435
436	// collect points to be tested
437	for (auto f : mesh_.faces(cd.v0))	44,893✔
438	{
439	std::copy(face_points_[f].begin(), face_points_[f].end(),	76,288✔
440	std::back_inserter(points));	114,432✔
441	}
442	points.push_back(vpoint_[cd.v0]);	6,749✔
443
444	// test points against all faces
445	vpoint_[cd.v0] = p1;	6,749✔
446	for (auto point : points)	19,589✔
447	{
448	ok = false;	12,840✔
449
450	for (auto f : mesh_.faces(cd.v0))	26,331✔
451	{
452	if (f != cd.fl && f != cd.fr)	26,331✔
453	{
454	if (distance(f, point) < hausdorff_error_)	17,231✔
455	{
456	ok = true;	12,840✔
457	break;	12,840✔
458	}
459	}
460	}
461
462	if (!ok)	12,840✔
463	{
464	vpoint_[cd.v0] = p0;	×
465	return false;	×
466	}
467	}
468	vpoint_[cd.v0] = p0;	6,749✔
469	}
470
471	// collapse passed all tests -> ok
472	return true;	14,547✔
473	}
474
475	bool SurfaceSimplification::texcoord_check(Halfedge h)	37,288✔
476	{
477	auto texcoords = mesh_.get_halfedge_property<TexCoord>("h:tex");	37,288✔
478	if (!texcoords)	37,288✔
479	{
480	// no texture coordinates -> skip texture seam tests
481	return true;	37,179✔
482	}
483
484	auto texture_seams = mesh_.edge_property<bool>("e:seam");	109✔
485	if (!texture_seams)	109✔
486	{
487	// no seams found -> skip seam tests
488	return true;	×
489	}
490
491	Halfedge o(mesh_.opposite_halfedge(h));	109✔
492	Vertex v0(mesh_.to_vertex(o));	109✔
493
494	if (!texture_seams[mesh_.edge(h)])	109✔
495	{
496	// v0v1 is not a texture seam
497	for (auto he : mesh_.halfedges(v0))	213✔
498	{
499	if (he == h)	200✔
500	continue;	28✔
501	// Check if v0 is part of a texture seam
502	// If yes, v0 must not be moved
503	if (texture_seams[mesh_.edge(he)])	172✔
504	{
505	return false;	38✔
506	}
507	}
508
509	return true;	13✔
510	}
511
512	// count number of adjacent texture seam edges
513	int nr_seam_edges = 0;	58✔
514	for (auto he : mesh_.halfedges(v0))	326✔
515	{
516	if (texture_seams[mesh_.edge(he)])	268✔
517	{
518	nr_seam_edges++;	124✔
519	}
520	}
521
522	// if there are more than 2 seam edges at point v0
523	// -> v0 must not be moved
524	if (nr_seam_edges > 2)	58✔
525	{
526	return false;	8✔
527	}
528
529	Halfedge seam1 = h, seam2 = mesh_.prev_halfedge(h);	50✔
530	while (seam2.idx() != o.idx())	135✔
531	{
532	if (texture_seams[mesh_.edge(seam2)])	125✔
533	{
534	auto s1 = normalize(texcoords[seam1] -	×
535	texcoords[mesh_.prev_halfedge(seam1)]);	50✔
536	auto s2 = normalize(texcoords[seam2] -	×
537	texcoords[mesh_.prev_halfedge(seam2)]);	50✔
538
539	// oppposite uvs
540	Halfedge o_seam1 = mesh_.opposite_halfedge(seam1);	50✔
541	Halfedge o_seam2 = mesh_.opposite_halfedge(seam2);	50✔
542	auto o1 = normalize(texcoords[o_seam1] -	×
543	texcoords[mesh_.prev_halfedge(o_seam1)]);	50✔
544	auto o2 = normalize(texcoords[o_seam2] -	×
545	texcoords[mesh_.prev_halfedge(o_seam2)]);	50✔
546
547	// check if the angle between the seam edge to be collapsed and the
548	// seam edge prolonged is smaller than the allowed deviation
549	if (dot(s1, s2) < seam_angle_deviation_ \|\|	70✔
550	dot(o1, o2) < seam_angle_deviation_)	20✔
551	{
552	// angle is too large -> don't collapse this edge
553	return false;	40✔
554	}
555	}
556	seam2 = mesh_.prev_halfedge(mesh_.opposite_halfedge(seam2));	85✔
557	}
558
559	// passed all tests
560	return true;	10✔
561	}
562
563	float SurfaceSimplification::priority(const CollapseData& cd)	14,547✔
564	{
565	// computer quadric error metric
566	Quadric Q = vquadric_[cd.v0];	14,547✔
567	Q += vquadric_[cd.v1];	14,547✔
568	return Q(vpoint_[cd.v1]);	14,547✔
569	}
570
571	void SurfaceSimplification::preprocess_collapse(const CollapseData& cd)	1,175✔
572	{
573	Halfedge h = cd.v0v1;	1,175✔
574	Halfedge o = mesh_.opposite_halfedge(h);	1,175✔
575	Halfedge v1v2, v2v1, v0v2;	1,175✔
576
577	// move texcoords in correct halfedge before collapsing an edge
578	auto texcoords = mesh_.get_halfedge_property<TexCoord>("h:tex");	1,175✔
579	if (texcoords)	1,175✔
580	{
581	auto texture_seams = mesh_.edge_property<bool>("e:seam", false);	4✔
582	Halfedge hit = h;	4✔
583	bool is_first_side = true;	4✔
584
585	// which texcoord must be saved depends
586	// on the side of the texture seam
587	for (size_t i = 0; i < mesh_.valence(mesh_.to_vertex(o)) - 1; ++i)	17✔
588	{
589	hit = mesh_.prev_halfedge(hit);	13✔
590	if (is_first_side)	13✔
591	texcoords[hit] = texcoords[h];	12✔
592	else if (!is_first_side)	1✔
593	texcoords[hit] = texcoords[mesh_.prev_halfedge(o)];	1✔
594	if (texture_seams[mesh_.edge(hit)])	13✔
595	{
596	is_first_side = false;	2✔
597
598	// loop case 1
599	if (mesh_.to_vertex(mesh_.next_halfedge(h)) ==	2✔
600	mesh_.from_vertex(hit))	4✔
601	{
602	v1v2 = mesh_.next_halfedge(h);	1✔
603	texcoords[mesh_.opposite_halfedge(v1v2)] = texcoords[hit];	1✔
604	texcoords[v1v2] = texcoords[mesh_.opposite_halfedge(hit)];	1✔
605	texture_seams[mesh_.edge(v1v2)] = true;	1✔
606	}
607
608	// loop case 2
609	if (mesh_.to_vertex(mesh_.next_halfedge(o)) ==	2✔
610	mesh_.from_vertex(hit))	4✔
611	{
612	v2v1 = mesh_.prev_halfedge(o);	1✔
613	v0v2 = mesh_.opposite_halfedge(hit);	1✔
614	texcoords[mesh_.opposite_halfedge(v2v1)] = texcoords[v0v2];	1✔
615	texcoords[v2v1] = texcoords[hit];	1✔
616	texture_seams[mesh_.edge(v2v1)] = true;	1✔
617	}
618	}
619	hit = mesh_.opposite_halfedge(hit);	13✔
620	}
621	}
622	}	1,175✔
623
624	void SurfaceSimplification::postprocess_collapse(const CollapseData& cd)	1,175✔
625	{
626	// update error quadrics
627	vquadric_[cd.v1] += vquadric_[cd.v0];	1,175✔
628
629	// update normal cones
630	if (normal_deviation_)	1,175✔
631	{
632	for (auto f : mesh_.faces(cd.v1))	4,544✔
633	{
634	normal_cone_[f].merge(	3,999✔
635	SurfaceNormals::compute_face_normal(mesh_, f));	3,999✔
636	}
637
638	if (cd.vl.is_valid())	545✔
639	{
640	Face f = mesh_.face(cd.v1vl);	545✔
641	if (f.is_valid())	545✔
642	normal_cone_[f].merge(normal_cone_[cd.fl]);	545✔
643	}
644
645	if (cd.vr.is_valid())	545✔
646	{
647	Face f = mesh_.face(cd.vrv1);	545✔
648	if (f.is_valid())	545✔
649	normal_cone_[f].merge(normal_cone_[cd.fr]);	545✔
650	}
651	}
652
653	// update Hausdorff error
654	if (hausdorff_error_)	1,175✔
655	{
656	Points points;	1,082✔
657
658	// collect points to be distributed
659
660	// points of v1's one-ring
661	for (auto f : mesh_.faces(cd.v1))	4,521✔
662	{
663	std::copy(face_points_[f].begin(), face_points_[f].end(),	7,960✔
664	std::back_inserter(points));	11,940✔
665	face_points_[f].clear();	3,980✔
666	}
667
668	// points of the 2 removed triangles
669	if (cd.fl.is_valid())	541✔
670	{
671	std::copy(face_points_[cd.fl].begin(), face_points_[cd.fl].end(),	1,082✔
672	std::back_inserter(points));	1,623✔
673	Points().swap(face_points_[cd.fl]); // free mem	541✔
674	}
675	if (cd.fr.is_valid())	541✔
676	{
677	std::copy(face_points_[cd.fr].begin(), face_points_[cd.fr].end(),	1,082✔
678	std::back_inserter(points));	1,623✔
679	Points().swap(face_points_[cd.fr]); // free mem	541✔
680	}
681
682	// the removed vertex
683	points.push_back(vpoint_[cd.v0]);	541✔
684
685	// test points against all faces
686	Scalar d, dd;
687	Face ff;	541✔
688
689	for (auto point : points)	3,713✔
690	{
691	dd = std::numeric_limits<Scalar>::max();	3,172✔
692
693	for (auto f : mesh_.faces(cd.v1))	26,362✔
694	{
695	d = distance(f, point);	23,190✔
696	if (d < dd)	23,190✔
697	{
698	ff = f;	8,845✔
699	dd = d;	8,845✔
700	}
701	}
702
703	face_points_[ff].push_back(point);	3,172✔
704	}
705	}
706	}	1,175✔
707
708	Scalar SurfaceSimplification::aspect_ratio(Face f) const	167,906✔
709	{
710	// min height is area/maxLength
711	// aspect ratio = length / height
712	// = length * length / area
713
714	auto fvit = mesh_.vertices(f);	167,906✔
715
716	const Point p0 = vpoint_[*fvit];	167,906✔
717	const Point p1 = vpoint_[*(++fvit)];	167,906✔
718	const Point p2 = vpoint_[*(++fvit)];	167,906✔
719
720	const Point d0 = p0 - p1;	167,906✔
721	const Point d1 = p1 - p2;	167,906✔
722	const Point d2 = p2 - p0;	167,906✔
723
724	const Scalar l0 = sqrnorm(d0);	167,906✔
725	const Scalar l1 = sqrnorm(d1);	167,906✔
726	const Scalar l2 = sqrnorm(d2);	167,906✔
727
728	// max squared edge length
729	const Scalar l = std::max(l0, std::max(l1, l2));	167,906✔
730
731	// triangle area
732	Scalar a = norm(cross(d0, d1));	167,906✔
733
734	return l / a;	167,906✔
735	}
736
737	Scalar SurfaceSimplification::distance(Face f, const Point& p) const	40,421✔
738	{
739	auto fvit = mesh_.vertices(f);	40,421✔
740
741	const Point p0 = vpoint_[*fvit];	40,421✔
742	const Point p1 = vpoint_[*(++fvit)];	40,421✔
743	const Point p2 = vpoint_[*(++fvit)];	40,421✔
744
745	Point n;
746
747	return dist_point_triangle(p, p0, p1, p2, n);	80,842✔
748	}
749
750	SurfaceSimplification::CollapseData::CollapseData(SurfaceMesh& sm, Halfedge h)	46,599✔
751	: mesh(sm)	46,599✔
752	{
753	v0v1 = h;	46,599✔
754	v1v0 = mesh.opposite_halfedge(v0v1);	46,599✔
755	v0 = mesh.to_vertex(v1v0);	46,599✔
756	v1 = mesh.to_vertex(v0v1);	46,599✔
757	fl = mesh.face(v0v1);	46,599✔
758	fr = mesh.face(v1v0);	46,599✔
759
760	// get vl
761	if (fl.is_valid())	46,599✔
762	{
763	v1vl = mesh.next_halfedge(v0v1);	46,577✔
764	vlv0 = mesh.next_halfedge(v1vl);	46,577✔
765	vl = mesh.to_vertex(v1vl);	46,577✔
766	}
767
768	// get vr
769	if (fr.is_valid())	46,599✔
770	{
771	v0vr = mesh.next_halfedge(v1v0);	46,577✔
772	vrv1 = mesh.prev_halfedge(v0vr);	46,577✔
773	vr = mesh.from_vertex(vrv1);	46,577✔
774	}
775	}	46,599✔
776
777	} // namespace pmp

pmp-library / pmp-library / 2292718584

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous