lapy.intersect

Self-intersection tests for triangle meshes.

Candidate pairs of triangles come from a KD-tree on the triangle centroids, and each candidate pair is tested exactly with the interval test of Moeller (1997). Everything is vectorized over the candidate pairs.

lapy.intersect.self_intersections(tria, subset=None)[source]

Find pairs of triangles that intersect and do not share a vertex.

Triangles that share a vertex or an edge are never reported, and neither are triangles that only touch in a point or lie in a common plane. For a 2D mesh, which is planar, nothing is reported.

Parameters:
triaTriaMesh

Triangle mesh.

subsetnp.ndarray, default=None

Triangle indices. If given, only pairs that involve at least one of these triangles are reported, which is much faster when only a few triangles have moved.

Returns:
np.ndarray

Array of shape (n_pairs, 2) with the indices of intersecting triangles, sorted within each row and lexicographically.

Parameters:
Return type:

ndarray

lapy.intersect.triangles_intersect(a, b, eps=1e-10)[source]

Test pairs of triangles for intersection.

Uses the interval test of Moeller [1]. Pairs that only touch in a single point and coplanar pairs are reported as not intersecting.

Parameters:
anp.ndarray

Corner coordinates of the first triangle of each pair, shape (k, 3, 3).

bnp.ndarray

Corner coordinates of the second triangle of each pair, shape (k, 3, 3).

epsfloat, default=1e-10

Distances to the other triangle’s plane below eps times the longest edge of the pair count as zero.

Returns:
np.ndarray

Boolean array of shape (k,), True where the two triangles intersect.

Parameters:
Return type:

ndarray

References

[1]

T. Moeller. A fast triangle-triangle intersection test. Journal of Graphics Tools, 2(2):25-30, 1997. doi:10.1080/10867651.1997.10487472

lapy.intersect.undo_intersections(tria, v_new, rings=2, max_rounds=10)[source]

Move vertices back where new positions make the surface intersect itself.

Useful after smoothing or another change of vertex positions on a surface that did not intersect itself before. Starting from the triangles that intersect with the new positions, their vertices and rings rings of neighbors return to their positions in tria. This repeats, testing only the triangles that changed, until no triangle intersects or max_rounds is reached. The mesh itself is not modified.

Parameters:
triaTriaMesh

Triangle mesh with the old vertex positions.

v_newnp.ndarray

New vertex positions of shape (n_vertices, 3), or (n_vertices, 2) for a 2D mesh.

ringsint, default=2

Rings of neighbors that move back together with each intersecting triangle.

max_roundsint, default=10

Maximum number of rounds.

Returns:
vnp.ndarray

Vertex positions, of the same shape as v_new.

n_revertedint

Number of vertices moved back to their old positions.

Raises:
ValueError

If v_new does not have the shape of the mesh vertices.

Parameters:
Return type:

tuple[ndarray, int]