SimplifyQuadricDecimation boundary weight

[FreakTheMighty]

Is your feature request related to a problem? Please describe. When decimating preserving boundary vertices can help produce more visually pleasing results. Currently, no additional consideration is give to vertices that are on the boundary of a mesh.

Describe the solution you'd like I would like to add a boundary_weight argument to simplify_quadric_decimation. The value would default to 1. Values greater then 1 would weight the error for vertices on the boundary of a mesh.

Describe alternatives you've considered

OpenMesh has a more generalized method of mixing and matching error metrics. I think such an approach is interesting, but it seems more complex both to implement and to use. With that said, an alternate API could use something like a callback that passes vertex information and the current cost and expects a new cost to be returned. This could enable use cases beyond boundary preservation.

Additional context

I started looking into implementing this, but I'm a bit confused about the different between TriangleMesh class and the HalfEdgeTriangleMesh class. Is it possible to determine boundaries for TriangleMesh, if so, are there existing methods that can be used?

    std::vector<Quadric> Qs(vertices_.size());
    for (size_t vidx = 0; vidx < vertices_.size(); ++vidx) {
        std::vector<int> edges = mesh->BoundaryHalfEdgesFromVertex(vidx);
        bool isBoundary = !edges.empty();
        for (int tidx : vert_to_triangles[vidx]) {
            Qs[vidx] += Quadric(triangle_planes[tidx], triangle_areas[tidx]);
            if (isBoundary) {
                Qs[vidx] *= 1e6;
            }
        }
    }

[griegler]

To determine the boundary edges you could use GetEdgeToTrianglesMap. This method returns a unordered_map from edges (indicated by ordered indices) to all triangles that contain this edge. If an edge has just one triangle, it is a boundary edge.

[FreakTheMighty]

@griegler thanks for the tip. I just opened a pull request. It looks like there was already special handling of edges and weight applied based on the area of the edge triangle. I'm not entirely sure if its worth adding the parameter, but it allows the developer to entirely lock edges when used with maximum_error or further prioritize them.

Thoughts?

[FreakTheMighty]

I think this is proving to be a useful parameter. Finding the correct values take some experimentation, but I am able to get a similar reduction with better visual quality.

mesh.simplify_quadric_decimation(2, maximum_error=1e-7, boundary_weight=1e6)

mesh.simplify_quadric_decimation(2, maximum_error=1e-7)

[griegler]

Thanks. It might be helpful to add a wireframe to the mesh if possible.

[FreakTheMighty]

@griegler posted wireframe samples below.

---

Working samples

Original

With boundary weight

Without boundary weight

Problematic samples

With more testing I'm finding a result I don't entirely understand. It seems that sometimes when using low maximum_error values with high boundary_weights the output sometimes has vertices behaving oddly. For example

mesh = mesh.simplify_quadric_decimation(2, maximum_error=1e-7, boundary_weight=1e20)

[griegler]

Thanks for those examples. The last one looks like a bug. Would it be possible to share the mesh, then I could have a look at what might be happening.

[FreakTheMighty]

@griegler the archive contains a glb to test with. Should I create a new issue?

mesh.zip

[griegler]

Thanks for the mesh. No need to open a new issue at the moment, I will look at it as soon as I find some time for it.

[FreakTheMighty]

@griegler the bug with that errant vertex has been causing me some headache recently, so I was planning on investigating a bit further. Any chance you have an intuition for what might be happening here?

[griegler]

My best guess is that it is a problem with Quadric. More specifically, the part where the new vertex position is computed. Most likely it is due to an numerical instability in Minimum.

[FreakTheMighty]

@griegler did you ever have a chance to look into this?