Feature request: edge collapse

[michaelfortunato]

Would it be possible to select edges in a mesh to contract that keep the mesh manifold using Trimesh? Thanks

[mikedh]

Yeah that would be cool! It's a little challenging to do in a vectorized way, since by collapsing edges you change the number of faces and thus their adjacency. It's pretty easy to end up with nonsense if you don't have totally independent edges. Here's a quick pass that can get good results in very specific cases:

import logging

import numpy as np
from numpy.typing import NDArray

import trimesh


def collapse_edges(mesh, edges: NDArray[np.int64], mean: bool = True):
    """
    Collapse edges of a mesh while trying to maintain the watertight
    property of the mesh.

    Parameters
    ----------
    mesh
      The mesh to operate on.
    edges : (n, 2) edges
      Pairs of indexes to `mesh.vertices`
    mean
      Make the position of the collapsed edge vertex the mean
      position along each collapsed edge. If not true it will
      pick one of the two vertices in the edge arbitrarily.

    Raises
    ----------
    ValueError
      If any of the passed edges don't exist in `mesh`.
    """

    # we're going to be querying which is indexed against sorted edges
    edges = np.sort(edges, axis=1)

    # query the face adjacency to get the pair of faces we need to remove
    exists, adj_index = m.face_adjacency_edges_tree.query(e, 1)
    # these are integer indexes misused as tree positions for lookup
    # so if the "distance" isn't exactly zero it means the edge didn't exist
    exists = exists < 1e-10

    if not exists.all():
        logging.warning(
            f"Not every edge shared! Skipping {len(edges) - exists.sum()}/{len(exists)}!"
        )
        adj_index = adj_index[exists]
        edges = edges[exists]

    # how many times was a vertex included. If a vertex was included
    # more than one times this function would need to be run in an
    # iterative manner and cannot do the bookkeeping in a single
    # vectorized operation.
    counts = np.bincount(edges.ravel())
    if counts.max() > 1:
        raise ValueError("A vertex exists in more than exactly one edge!")

    # generate a mask to remove the two adjacent faces to the edge
    face_mask = np.ones(len(m.faces), dtype=np.bool)
    face_mask[m.face_adjacency[adj_index].ravel()] = False

    # reindex the faces to only reference one of the vertices from the edge
    reindex = np.arange(len(mesh.vertices))
    reindex[edges[:, 0]] = edges[:, 1]
    mesh.faces = reindex[mesh.faces[face_mask]]

    if mean:
        # make the now shared vertex the mean of the edge
        mesh.vertices[edges[:, 1]] = mesh.vertices[edges].mean(axis=1)


if __name__ == "__main__":
    # create a subdivided box
    m = trimesh.creation.box().subdivide().subdivide()

    # should be a volume
    assert m.is_volume

    # take a few arbitrary edges
    e = m.edges[::45]

    # show the number of faces before our operations
    print(f"before: {m} is_watertight=`{m.is_watertight}`")

    # run collapse in-place
    collapse_edges(m, e, mean=True)

    print(f"\nafter: {m} is_watertight=`{m.is_watertight}`")

    assert m.is_volume

    m.show()

However I think it would need quite a bit more work to handle all the cases a user might throw at it, e.g. what if someone tries to remove a whole face patch with it, etc. If we did this iteratively it would be a lot easier logically at the expense of being unusably slow haha. Anyway, open to PR's against this!

[michaelfortunato]

Yeah I'm totally with you: the issue is edge collapse independence. I cannot see a general way to determine whether collapsing edges $e_1$ and then $e_2$ on triangular mesh $m$ leaves $m$ manifold, if we are told that collapsing $e_1$ on $m$ leaves $m$ manifold, and that collapsing $e_2$ on $m$ also leaves $m$ manifold.

[michaelfortunato]

There is some recent work addressing this application, RXMesh comes first to my mind, but it has been hard to find a sufficient conditions for deciding the question ("When does collapsing edges $e_1$ and then $e_2$ on triangular mesh $m$ leaves $m$ manifold, if we are told that collapsing $e_1$ on $m$ leaves $m$ manifold, and that collapsing $e_2$ on $m$ also leaves $m$ manifold?"), much less an algorithm for solving it .

[michaelfortunato]

There are other questions too. Say we are told that two sequences $s_1 = (e_1, e_2)$ and $s_2 = (e_3, e_4)$ of edge collapses leave $m$ manifold. Say $s_{1_V}$ is the set of vertices involved in edge collapse sequence $s_1$ and $s_{2_V}$ the set of vertices involved in edge collapse sequence $s_2$. My hunch is that $s_1$ and $s_2$ can be applied in parallel if $s_{1_V} \cap s_{2_V} = \emptyset$ and there is no "ambassador" edge $e = (u, v)$ in our mesh $m$ with $v \in s_{1_V}$ and $u \in s_{2_V}$