Skip to content

Meshes

Routines that treat a triangle mesh as a graph over its vertices, with the edges taken from the faces.

Connected components

Labelling the connected components of a triangle mesh, i.e. finding which vertices are reachable from which through shared faces.

import navis_fastcore as fastcore
import numpy as np

# Two disconnected triangles
faces = np.array([[0, 1, 2], [3, 4, 5]], dtype=np.uint32)

fastcore.mesh_connected_components(faces, n_vertices=6)
# array([0, 0, 0, 3, 3, 3], dtype=uint32)

Find connected components of a triangle mesh.

Uses Union-Find (DSU) with path-halving. The only extra allocation is a single integer array of length n_vertices — no adjacency list is built.

PARAMETER DESCRIPTION
faces 
     Triangular faces given as rows of three vertex indices.
     Must be convertible to ``uint32``.

TYPE: (N, 3) array

n_vertices 
     Total number of vertices in the mesh. Must be at least
     ``faces.max() + 1``.

TYPE: int

RETURNS DESCRIPTION
components

For each vertex the index of the root vertex of its connected component. Vertices that share a component will have the same value (the smallest vertex index in that component).

TYPE: (n_vertices, ) uint32 array

Examples:

Two triangles sharing an edge — one component:

>>> import navis_fastcore as fastcore
>>> import numpy as np
>>> faces = np.array([[0, 1, 2], [1, 2, 3]], dtype=np.uint32)
>>> fastcore.mesh_connected_components(faces, n_vertices=4)
array([0, 0, 0, 0], dtype=uint32)

Two disjoint triangles — two components:

>>> faces = np.array([[0, 1, 2], [3, 4, 5]], dtype=np.uint32)
>>> fastcore.mesh_connected_components(faces, n_vertices=6)
array([0, 0, 0, 3, 3, 3], dtype=uint32)

Geodesic distances

The mesh counterpart to geodesic_matrix, which works on skeletons. A skeleton is a tree, so distances there come from walking to the lowest common ancestor. A mesh is a general cyclic graph, so this runs a Dijkstra per source instead — in parallel, which is the whole point: scipy.sparse.csgraph.dijkstra holds the GIL, so you cannot get that speedup from Python by threading it yourself.

import navis_fastcore as fastcore
import numpy as np

# Two triangles sharing the 1-2 edge, forming a unit square
faces = np.array([[0, 1, 2], [1, 2, 3]], dtype=np.uint32)
vertices = np.array([[0, 0, 0],
                     [1, 0, 0],
                     [0, 1, 0],
                     [1, 1, 0]], dtype=np.float64)

fastcore.geodesic_matrix_mesh(faces, vertices)
# array([[0.       , 1.       , 1.       , 2.       ],
#        [1.       , 0.       , 1.4142135, 1.       ],
#        [1.       , 1.4142135, 0.       , 1.       ],
#        [2.       , 1.       , 1.       , 0.       ]], dtype=float32)

Mind the size of the output

A full V x V matrix is around 107 GB at V=164k, so for anything but a small mesh you want sources and/or targets.

targets is worth calling out. scipy.sparse.csgraph.dijkstra has no notion of targets: it always materialises all V columns and makes you slice afterwards. Passing targets here means only those columns are ever allocated — for 200 sources and 100 targets on a 41k-vertex mesh that is 0.03 MB instead of 70 MB.

If you only need the nearest (or farthest) target, use geodesic_nearest_mesh instead — its output is O(sources) rather than O(sources x targets), and it is faster too, because the search stops at the first target it settles.

This is the along-edge distance

Shortest paths are constrained to run along mesh edges, so on a coarse mesh they overshoot the true surface geodesic. This is the same approximation navis makes.

Calculate geodesic ("along-the-mesh-edge") distances on a triangle mesh.

This is the mesh counterpart to :func:~navis_fastcore.geodesic_matrix, which works on skeletons. Where the skeleton version exploits the tree structure, a mesh is a general cyclic graph, so this runs a parallel Dijkstra (or a BFS when unweighted) over the vertex adjacency derived from faces.

Notes

This is the distance along mesh edges, not the exact surface geodesic: shortest paths are constrained to run along edges, so on a coarse mesh they overshoot the true surface distance.

Beware the size of the output. A full V x V matrix is ~107 GB at V=164k, so for anything but a small mesh you want sources and/or targets. Unlike scipy.sparse.csgraph.dijkstra — which has no notion of targets and always materialises all V columns before you can slice them — targets here means only those columns are ever allocated.

PARAMETER DESCRIPTION
faces 
     Triangular faces given as rows of three vertex indices.

TYPE: (F, 3) array

vertices 
     Vertex coordinates. If provided, edges are weighted by their
     euclidean length. If ``None``, every edge has weight 1 (i.e. the
     result is a hop count) and you must pass ``n_vertices``.

TYPE: (V, 3) array DEFAULT: None

n_vertices 
     Total number of vertices. Inferred from ``vertices`` if given.
     Vertices not referenced by any face are simply unreachable.

TYPE: int DEFAULT: None

sources 
     Source vertex indices. If ``None`` all vertices are used.

TYPE: iterable DEFAULT: None

targets 
     Target vertex indices. If ``None`` all vertices are used. The order
     is preserved and duplicates are allowed.

TYPE: iterable DEFAULT: None

limit 
     Ignore any nodes further away than this. Vertices at exactly
     ``limit`` are kept (as in scipy). This prunes the search itself, it
     is not a post-hoc mask.

TYPE: float DEFAULT: None

threads 
     Number of threads to use. If ``None`` uses all available cores. Set
     to 1 if you are already inside a multiprocessing pool, to avoid
     oversubscribing the machine.

TYPE: int DEFAULT: None

RETURNS DESCRIPTION
matrix

Geodesic distances. Unreachable pairs — disconnected, or beyond limit — are set to -1.

TYPE: (len(sources), len(targets)) float32 array

Examples:

Two triangles sharing the 1-2 edge, forming a unit square. Vertices 0 and 3 are the opposite corners, so they are not directly connected — the shortest path between them goes around, via 1 or 2:

>>> import navis_fastcore as fastcore
>>> import numpy as np
>>> faces = np.array([[0, 1, 2], [1, 2, 3]], dtype=np.uint32)
>>> vertices = np.array([[0, 0, 0],
...                      [1, 0, 0],
...                      [0, 1, 0],
...                      [1, 1, 0]], dtype=np.float64)
>>> fastcore.geodesic_matrix_mesh(faces, vertices)
array([[0.       , 1.       , 1.       , 2.       ],
       [1.       , 0.       , 1.4142135, 1.       ],
       [1.       , 1.4142135, 0.       , 1.       ],
       [2.       , 1.       , 1.       , 0.       ]], dtype=float32)

Without vertices every edge has weight 1, so you get hop counts instead — the shared diagonal 1-2 is now a single hop rather than sqrt(2):

>>> fastcore.geodesic_matrix_mesh(faces, n_vertices=4)
array([[0., 1., 1., 2.],
       [1., 0., 1., 1.],
       [1., 1., 0., 1.],
       [2., 1., 1., 0.]], dtype=float32)

For each source vertex, find the nearest target vertex on a mesh.

A memory-efficient alternative to :func:~navis_fastcore.geodesic_matrix_mesh: it keeps only the nearest target and the distance to it, so the output is O(len(sources)) rather than O(len(sources) * len(targets)). It is also faster, because the search stops at the first target it settles instead of exploring the whole connected component.

PARAMETER DESCRIPTION
faces 
     Triangular faces given as rows of three vertex indices.

TYPE: (F, 3) array

vertices 
     Vertex coordinates for euclidean edge weights. If ``None``, edges
     have weight 1 and you must pass ``n_vertices``.

TYPE: (V, 3) array DEFAULT: None

n_vertices 
     Total number of vertices. Inferred from ``vertices`` if given.

TYPE: int DEFAULT: None

sources 
     Source vertex indices. If ``None`` all vertices are used.

TYPE: iterable DEFAULT: None

targets 
     Target vertex indices. If ``None`` all vertices are used.

TYPE: iterable DEFAULT: None

limit 
     Ignore any targets further away than this.

TYPE: float DEFAULT: None

threads 
     Number of threads to use. If ``None`` uses all available cores.

TYPE: int DEFAULT: None

RETURNS DESCRIPTION
distances

Distance from each source to its nearest target; -1 if no target is reachable.

TYPE: (len(sources), ) float32 array

nearest

Vertex index of that nearest target; -1 if none is reachable.

TYPE: (len(sources), ) int32 array

Notes

A source that is itself a target is matched to its nearest distinct target, never to itself (so the distance is never trivially 0). Ties break towards the lower vertex index.

Examples:

>>> import navis_fastcore as fastcore
>>> import numpy as np
>>> faces = np.array([[0, 1, 2], [1, 2, 3]], dtype=np.uint32)
>>> vertices = np.array([[0, 0, 0],
...                      [1, 0, 0],
...                      [0, 1, 0],
...                      [1, 1, 0]], dtype=np.float64)
>>> dists, nearest = fastcore.geodesic_nearest_mesh(
...     faces, vertices, sources=[0], targets=[2, 3]
... )
>>> dists
array([1.], dtype=float32)
>>> nearest
array([2], dtype=int32)

For each source vertex, find the farthest target vertex on a mesh.

The mirror image of :func:~navis_fastcore.geodesic_nearest_mesh, with the same O(len(sources)) memory footprint. Unlike nearest, this cannot stop early — it has to settle every target — but the farthest one then comes for free, since the search settles vertices in increasing order of distance.

PARAMETER DESCRIPTION
faces 
     Triangular faces given as rows of three vertex indices.

TYPE: (F, 3) array

vertices 
     Vertex coordinates for euclidean edge weights. If ``None``, edges
     have weight 1 and you must pass ``n_vertices``.

TYPE: (V, 3) array DEFAULT: None

n_vertices 
     Total number of vertices. Inferred from ``vertices`` if given.

TYPE: int DEFAULT: None

sources 
     Source vertex indices. If ``None`` all vertices are used.

TYPE: iterable DEFAULT: None

targets 
     Target vertex indices. If ``None`` all vertices are used.

TYPE: iterable DEFAULT: None

limit 
     Ignore any targets further away than this.

TYPE: float DEFAULT: None

threads 
     Number of threads to use. If ``None`` uses all available cores.

TYPE: int DEFAULT: None

RETURNS DESCRIPTION
distances

Distance from each source to its farthest target; -1 if no target is reachable.

TYPE: (len(sources), ) float32 array

farthest

Vertex index of that farthest target; -1 if none is reachable.

TYPE: (len(sources), ) int32 array

Notes

As with nearest, a source that is itself a target is matched to a distinct target, never to itself.

Examples:

>>> import navis_fastcore as fastcore
>>> import numpy as np
>>> faces = np.array([[0, 1, 2], [1, 2, 3]], dtype=np.uint32)
>>> vertices = np.array([[0, 0, 0],
...                      [1, 0, 0],
...                      [0, 1, 0],
...                      [1, 1, 0]], dtype=np.float64)
>>> dists, farthest = fastcore.geodesic_farthest_mesh(
...     faces, vertices, sources=[0], targets=[2, 3]
... )
>>> farthest
array([3], dtype=int32)

Arbitrary graphs

The same kernel, over an explicit edge list rather than a mesh. Unlike geodesic_matrix, this makes no tree assumption, so cycles are fine.

import navis_fastcore as fastcore
import numpy as np

# A triangle. The direct 0-2 edge has weight 5, so the shortest
# path between them goes the long way round via 1.
edges = np.array([[0, 1], [1, 2], [2, 0]], dtype=np.uint32)
weights = np.array([1, 1, 5], dtype=np.float32)

fastcore.geodesic_matrix_graph(edges, 3, weights=weights)
# array([[0., 1., 2.],
#        [1., 0., 1.],
#        [2., 1., 0.]], dtype=float32)

Calculate geodesic distances over an arbitrary graph.

The general form of :func:~navis_fastcore.geodesic_matrix_mesh. Unlike :func:~navis_fastcore.geodesic_matrix, this makes no tree assumption — cycles are fine.

PARAMETER DESCRIPTION
edges 
     Edges given as rows of two node indices.

TYPE: (E, 2) array

n_nodes 
     Total number of nodes.

TYPE: int

weights 
     Length of each edge. If ``None`` all edges have weight 1 (i.e. the
     result is a hop count). Must be finite and non-negative. Parallel
     edges collapse to the shortest.

TYPE: (E, ) array DEFAULT: None

directed 
     If ``True`` an edge ``(u, v)`` may only be traversed from ``u`` to
     ``v``. If ``False`` (default) the graph is treated as undirected.

TYPE: bool DEFAULT: False

sources 
     Source node indices. If ``None`` all nodes are used.

TYPE: iterable DEFAULT: None

targets 
     Target node indices. If ``None`` all nodes are used.

TYPE: iterable DEFAULT: None

limit 
     Ignore any nodes further away than this.

TYPE: float DEFAULT: None

threads 
     Number of threads to use. If ``None`` uses all available cores.

TYPE: int DEFAULT: None

RETURNS DESCRIPTION
matrix

Geodesic distances; -1 where unreachable.

TYPE: (len(sources), len(targets)) float32 array

Examples:

A triangle — a cycle, which the skeleton functions would reject. Note the direct 0-2 edge has weight 5, so the shortest path goes the long way round via 1:

>>> import navis_fastcore as fastcore
>>> import numpy as np
>>> edges = np.array([[0, 1], [1, 2], [2, 0]], dtype=np.uint32)
>>> weights = np.array([1, 1, 5], dtype=np.float32)
>>> fastcore.geodesic_matrix_graph(edges, 3, weights=weights)
array([[0., 1., 2.],
       [1., 0., 1.],
       [2., 1., 0.]], dtype=float32)