lapy.topology

Find and remove the handles of closed triangle meshes.

Each handle of a closed surface, one unit of its genus, comes with two non-trivial loops that cross each other once. Cutting the surface along either loop and closing both openings with disks removes the handle. Along one loop this cuts a bridge, along the other it fills a tunnel; which loop is which depends on how the surface sits in space, so the choice is left to the caller.

Loops are arrays of vertex indices along a closed path of mesh edges, the first vertex not repeated at the end. They are not boundary loops: those are found with lapy.TriaMesh.boundary_loops(). Queries such as the genus, the Euler characteristic, the manifold and orientation tests and critical points are methods of lapy.TriaMesh.

class lapy.topology.Handle(loop_a, loop_b, length_a, length_b)[source]

A handle given by two loops that cross each other once.

Capped surgery along either loop removes the handle. After earlier handles have been removed, a loop can run along both sides of an earlier cut and then visits a vertex twice.

Parameters:
loop_a, loop_bnp.ndarray

The two loops, as vertex indices of the input mesh.

length_a, length_bfloat

Their lengths.

Parameters:
class lapy.topology.Surgery(loop, other, length, other_length, operation, n_intersections=0, evidence=None)[source]

One handle removed by cutting along a loop and closing both openings.

Parameters:
loopnp.ndarray

The loop that was used, as vertex indices of the input mesh.

othernp.ndarray

The other loop of the pair.

length, other_lengthfloat

Their lengths.

operationstr

“cut” when the loop goes around a bridge and “fill” when it goes around a tunnel, as reported by the classifier, or “unknown” without one.

n_intersectionsint, default=0

Triangle pairs that the surgery left intersecting; zero unless no candidate was free of intersections.

evidencetuple or None, default=None

Classifier results for the used and the other loop.

Parameters:

Attributes

evidence
lapy.topology.capped_surgery(tria, loop, gap=0.2)[source]

Cut a closed mesh along a simple loop and close both openings with disks.

For a non-separating loop this lowers the genus by one. The two copies of the loop are first moved apart, each by gap times the mean loop edge length towards its own side, so that the disks do not touch. The disks are close to minimal surfaces, with edges about as long as those of the loop, see disk_cap(). Vertices away from the loop keep their index and position.

Parameters:
triaTriaMesh

Closed, oriented, edge-manifold triangle mesh.

loopnp.ndarray

Vertex indices of a simple closed loop.

gapfloat, default=0.2

Separation of each side from the loop, relative to the mean loop edge length.

Returns:
TriaMesh

The new mesh: the input vertices, the cut copies, then the inner disk vertices.

sourcenp.ndarray

Input vertex index of each cut copy, in the order they were appended.

Parameters:
Return type:

tuple[TriaMesh, ndarray]

lapy.topology.disk_cap(points, edge_length, iterations=3)[source]

Triangulate a disk that spans a closed boundary polygon, close to a minimal surface.

The polygon is first triangulated with the least area and no new vertices (Liepa 2003), which is free of folds for a planar polygon, convex or not, and edges between two boundary vertices are split, so that the disk can close a hole without duplicating an edge of the mesh around it. Then, iterations times, the disk is remeshed to the target edge length with the boundary kept as it is, see lapy.remesh.remesh(), and its inner vertices are moved to the harmonic positions for the current cotangent weights (Pinkall and Polthier 1993), which pulls the disk towards a minimal surface. A round that would fold the disk more, as smoothing can in thin concave parts, is not applied, and the disk stays as it was.

Parameters:
pointsnp.ndarray

Boundary polygon of shape (k, 3), in order.

edge_lengthfloat

Target edge length inside the disk.

iterationsint, default=3

Rounds of remeshing and minimal surface steps.

Returns:
innernp.ndarray

Positions of the new inner vertices, shape (m, 3).

trisnp.ndarray

Triangles of shape (n, 3); indices below k refer to the boundary points in order, indices from k on to the inner vertices. The triangles contain the directed sides points[i] -> points[i + 1]; reverse them to close a hole whose triangles contain these sides.

Parameters:
Return type:

tuple[ndarray, ndarray]

lapy.topology.essential_saddles(tria, f)[source]

Find the saddles of a function that no cancellation with a minimum or maximum can remove.

Ties in f are broken by vertex index. A saddle of multiplicity m has 2(m + 1) sign changes around its link. Each of its m units either merges two sublevel components and cancels with a minimum, merges two superlevel components and cancels with a maximum, or is essential. A closed surface of genus g has exactly 2g essential saddles, two per handle.

Parameters:
triaTriaMesh

Closed manifold triangle mesh.

fnp.ndarray

Function value per vertex, shape (n_vertices,).

Returns:
np.ndarray

Number of essential saddle units per vertex, shape (n_vertices,).

Raises:
ValueError

If the mesh is not closed or not manifold. At a pinch vertex the link is not a single circle, so saddles cannot be counted from its sign changes.

Parameters:
Return type:

ndarray

lapy.topology.find_handles(tria, root=None, max_rounds=10, cap_weight=1000.0)[source]

Find one pair of short crossing loops per handle.

Repeatedly takes the shortest tree-cotree loop, shortens it together with its crossing loop (refine_loop_pair()), records the pair, and cuts the surface along the shorter loop of the pair, closing both openings, which lowers the genus by one. Edges at the centres of these closures cost cap_weight times their length, so later loops run around them on the surface.

Parameters:
triaTriaMesh

Closed, connected, oriented manifold triangle mesh.

rootint or None, default=None

Root vertex for the tree-cotree loops, see tree_cotree_loops().

max_roundsint, default=10

Maximum number of refinement rounds per handle.

cap_weightfloat, default=1e3

Cost multiplier at the centres of the closures.

Returns:
list of Handle

One entry per handle, in the order they were found.

Raises:
ValueError

If the mesh is not a closed, connected, oriented manifold, or the root is not used by a triangle.

RuntimeError

If a loop runs through the centre of an earlier closure.

Parameters:
Return type:

list

lapy.topology.fix_topology(tria, choose=<function shorter_loop>, classify=None, max_rounds=10, gap=0.2)[source]

Remove all handles of a closed surface by capped surgery, one handle at a time.

Each round finds the shortest tree-cotree loop, refines it with its crossing loop, asks choose which of the two loops to use, and performs capped_surgery() along it. If the new disks intersect the surface, other gaps and then the other loop are tried, and the first result without intersections is kept, or else the one with the fewest. Later handles are found on the already corrected mesh.

Parameters:
triaTriaMesh

Closed, connected, oriented manifold triangle mesh.

choosecallable(), default=shorter_loop

choose(a, b, length_a, length_b, scores, v=...) returns 0 or 1 for the loop to cut along; v holds the current vertex positions.

classifycallable() or None, default=None

classify(v, t, loop) returns True if surgery along the loop cuts a bridge rather than filling a tunnel, or an object with such a cuts attribute. Its results are passed to choose as scores and recorded in the result.

max_roundsint, default=10

Maximum refinement rounds per handle, see refine_loop_pair().

gapfloat, default=0.2

Separation of the cut sides, see capped_surgery().

Returns:
TriaMesh

The corrected mesh of genus 0.

originnp.ndarray

Input vertex index of each output vertex, -1 for new vertices inside the disks.

surgerieslist of Surgery

One entry per removed handle.

Raises:
ValueError

If the mesh is not a closed, connected, oriented manifold.

Parameters:
Return type:

tuple[TriaMesh, ndarray, list]

lapy.topology.handle_clusters(tria, handles, saddles, rings=2)[source]

Group handles whose loops pass close to the same essential saddle.

Parameters:
triaTriaMesh

Triangle mesh.

handleslist of Handle

Handles as returned by find_handles().

saddlesnp.ndarray

Essential saddle count per vertex, as returned by essential_saddles().

ringsint, default=2

A saddle belongs to a handle if it lies within this many edge rings of one of its loops.

Returns:
clusternp.ndarray

Cluster index per handle, numbered from 0.

saddle_verticeslist of np.ndarray

Essential saddle vertices near each handle.

Parameters:
Return type:

tuple[ndarray, list]

lapy.topology.handle_patches(tria, handles, radius=1.5)[source]

Group the vertices near each handle into patches.

A handle’s patch holds the vertices within distance radius, along mesh edges, of either of its loops. Patches that share a vertex are merged.

Parameters:
triaTriaMesh

Triangle mesh.

handleslist of Handle

Handles as returned by find_handles().

radiusfloat, default=1.5

Distance along mesh edges.

Returns:
labelsnp.ndarray

Patch number per vertex, starting at 1; 0 outside all patches.

handle_patchnp.ndarray

Patch number of each handle.

Parameters:
Return type:

tuple[ndarray, ndarray]

lapy.topology.refine_loop_pair(tria, loop, vertex_weights=None, max_rounds=10)[source]

Shorten a non-separating loop and its crossing loop by alternating crossing searches.

Starting from loop, compute the shortest loop crossing it once, then the shortest loop crossing that one, and so on, as long as the summed length of the pair decreases.

Parameters:
triaTriaMesh

Closed, oriented, edge-manifold triangle mesh.

loopnp.ndarray

Vertex indices of a simple, non-separating closed loop.

vertex_weightsnp.ndarray or None, default=None

Cost multiplier per vertex, see tree_cotree_loops().

max_roundsint, default=10

Maximum number of alternations.

Returns:
a, bnp.ndarray

The refined pair; each crosses the other once.

length_a, length_bfloat

Their weighted lengths.

Parameters:
Return type:

tuple[ndarray, ndarray, float, float]

lapy.topology.shorter_loop(a, b, length_a, length_b, scores=None, v=None)[source]

Choose the shorter loop of a pair, the default rule of fix_topology().

Parameters:
a, bnp.ndarray

The two loops of a handle.

length_a, length_bfloat

Their lengths.

scorestuple or None, default=None

Classifier results for both loops; not used.

vnp.ndarray or None, default=None

Current vertex positions; not used.

Returns:
int

0 for a, 1 for b.

Return type:

int

lapy.topology.shortest_crossing_loop(tria, loop, vertex_weights=None, radius=None)[source]

Find the shortest closed loop that crosses a given loop exactly once.

The mesh is cut along loop; a path in the cut mesh from one copy of a loop vertex to the other copy closes into a loop that crosses loop once. The shortest such path over all loop vertices is returned. If loop is non-separating, so is the result.

The search runs on the part of the mesh within radius of loop. A crossing loop of length L stays within L / 2 of loop, so a result no longer than twice the radius is the global optimum; otherwise the radius is doubled and the search repeated.

Parameters:
triaTriaMesh

Closed, oriented, edge-manifold triangle mesh.

loopnp.ndarray

Vertex indices of a simple closed loop.

vertex_weightsnp.ndarray or None, default=None

Cost multiplier per vertex, see tree_cotree_loops().

radiusfloat or None, default=None

Initial search radius. Defaults to eight times the median edge cost.

Returns:
crossingnp.ndarray

Vertex indices of the crossing loop.

lengthfloat

Its weighted length.

Raises:
RuntimeError

If no loop crosses loop once, which is the case when loop separates the mesh.

Parameters:
Return type:

tuple[ndarray, float]

lapy.topology.tree_cotree_loops(tria, root=None, vertex_weights=None)[source]

Compute a greedy system of non-trivial loops through a root vertex.

A shortest-path tree from the root and a maximum spanning tree of the dual graph, weighted by the length of the loop that each dual edge closes, leave 2g edges that belong to neither tree (Erickson and Whittlesey 2005). Each of them closes one loop. Cutting the mesh along all of them leaves a single disk, so each loop is non-separating and together they span the first homology. The loops are returned without the stem they share with the root, so a loop passes through the root only when it has to.

Parameters:
triaTriaMesh

Closed, connected, edge-manifold triangle mesh of genus g.

rootint or None, default=None

Root vertex of the shortest-path tree; by default the lowest vertex index used by a triangle.

vertex_weightsnp.ndarray or None, default=None

Cost multiplier per vertex, shape (n_vertices,). An edge costs its length times the larger weight of its two vertices, so large weights keep loops away from a vertex.

Returns:
loopslist of np.ndarray

The 2g loops, each as vertex indices, sorted by length.

lengthsnp.ndarray

Weighted length of each loop.

Raises:
ValueError

If the mesh is not closed, edge-manifold and connected, or the root is not used by a triangle.

Parameters:
Return type:

tuple[list, ndarray]