Splitting separate components of Mesh Arrangements result

[graphic-goose]

Hi,

I've been investigating your library with the Python bindings and the performance is very impressive!

I have a quick question about the easiest way to determine the separate components after generating a Mesh Arrangement from two open (non-watertight) meshes? In my case I have two meshes that cross each other and I want to split the first mesh into the separate components that are on either side of the other mesh.

I can see from the result returned from tf.mesh_arrangements that the intersection is baked in, so the intersection has been processed correctly, but I haven't been able to work out yet the best way to split it into the separate components.

Using tf.boolean_difference works as expected, but doesn't allow me to select the component to keep on which side of the second/cutting mesh. It seems to depend on the winding order of the facets, but I'm looking for a way I can explicitly define which side I'd like to keep (without having to flip the winding order).

Thanks,
Dan

[ZigaSajovic]

@graphic-goose
You can: Compute the arrangement. Compute manifold edge connected component labels of the arrangement. Split the arrangement into components based on these labels.

faces_a, points_a = tf.make_plane_mesh(2.0, 2.0)

# Second plane: rotate 90 deg around X so it lies in the XZ plane (y = 0).
R = np.array([
    [1, 0,  0],
    [0, 0, -1],
    [0, 1,  0],
], dtype=points_a.dtype)
points_b = points_a @ R.T
faces_b  = faces_a.copy()

mesh_a = tf.Mesh(faces_a, points_a)
mesh_b = tf.Mesh(faces_b, points_b)

# Compute the arrangement of the two meshes.
(faces, points), tag_labels, face_labels = tf.mesh_arrangements(
    [mesh_a, mesh_b])
arr = tf.Mesh(faces, points)

n_components, comp_labels = tf.label_connected_components(
    arr.manifold_edge_link)

print(f"manifold-edge connected components: {n_components}")
assert n_components == 4, f"expected 4 components, got {n_components}"

# Split into one sub-mesh per component.
components, ids = tf.split_into_components(arr, comp_labels)

mesh_0_component_ids = np.unique(comp_labels[tag_labels == 0])
mesh_1_component_ids = np.unique(comp_labels[tag_labels == 1])

for cid, (cf, cp) in zip(ids, components):
    src = int(tag_labels[comp_labels == cid][0])    # which input mesh
    centroid = cp.mean(axis=0)
    print(
        f"  component {cid}: source={src}, faces={len(cf)}, "
        f"centroid=({centroid[0]:+.3f}, {centroid[1]:+.3f}, {centroid[2]:+.3f})"
    )

manifold-edge connected components: 4.
component 0: source=1, faces=3, centroid=(+0.000, +0.000, -0.400).
component 1: source=0, faces=3, centroid=(+0.000, +0.400, +0.000).
component 2: source=0, faces=3, centroid=(+0.000, -0.400, +0.000).
component 3: source=1, faces=3, centroid=(+0.000, +0.000, +0.400).

Is this what you had in mind?

In Lunar:

arrangement-components.mp4

[graphic-goose]

@ZigaSajovic thanks for the reply. Yes, that's partly what I'm wanting to do. But what I'm really looking for is the recommended way to select, from your image, the green or blue components from mesh_a based on which side of the mesh_b they're on.

Let's say I want to get the component of mesh_a on the up side of mesh_b, where up is defined by the normals of mesh_b, Or if I wanted to get the component of mesh_a on the down side of mesh_b.

Using the centroid for defining the direction wouldn't always be robust for my use-cases either, unfortunately.

[ZigaSajovic]

@graphic-goose In c++ it would be trivial. Python does not yet expose all the low-level API. So there is no recommended way yet. But we can do it. Here is the plan:

Get non manifold edges of the arrangement (we have this in python) and the incident faces on those edges (missing from python, but we can use numpy). We know from tag_labels which original mesh which face is from, and we know which component it belongs to. On each edge, take the 2 faces from tag0 and the original face the the 2 faces from tag1 belonged to. Classify both faces from tag0 against its plane.

For increased robustness, we do this on every edge, and produce a distribution (bincounts) of votes for each component (in case you get numerics issues at any particular edge). Assign sidedness to each component based on the bincounts.

---

Face incidence around non-manifold edges. In c++ we would have just called tf::make_non_manifold_edges(faces, tf::complete), in python, we only have the non-complete variant returning only edges. So we use numpy for the rest. We pack each undirected edge as an int64 key (v_min * n + v_max), match arrangement edges against NM edges with np.isin, and recover which NM edge each incidence sits on with searchsorted. At every NM edge we record one mesh_b original-face id as the local splitter — any tag=1 incidence works, since both mesh_b halves at that edge come from the same original face (just look up face_labels):

def edge_keys(e, n):
    e = np.sort(e, axis=-1)
    return e[..., 0].astype(np.int64) * n + e[..., 1]

nm_edges = tf.non_manifold_edges(arr)                            # (M, 2)

n_pts = len(points)
fe    = np.stack([faces, np.roll(faces, -1, axis=1)], axis=-1)   # (F, 3, 2)
fe_k  = edge_keys(fe, n_pts)                                     # (F, 3)
nm_k  = edge_keys(nm_edges, n_pts)                               # (M,)

# (face, local-edge) incidences on NM edges, mapped to NM edge id
face_idx, local_idx = np.where(np.isin(fe_k, nm_k))
order = np.argsort(nm_k)
nm_id = order[np.searchsorted(nm_k[order], fe_k[face_idx, local_idx])]

# Per NM edge: remember a mesh_b splitter (original face id, via face_labels)
inc_tag = tag_labels[face_idx]
nm_to_B = np.full(len(nm_edges), -1, np.int64)
nm_to_B[nm_id[inc_tag == 1]] = face_labels[face_idx[inc_tag == 1]]

# Mesh_a incidences (the faces we want to classify) + their local splitter id
is_a       = inc_tag == 0
a_face     = face_idx[is_a]
a_local    = local_idx[is_a]
a_splitter = nm_to_B[nm_id[is_a]]

Classify each mesh_a incidence against its splitter. Of each mesh_a arrangement face's three vertices, two sit on the cut edge and one — at (local_edge + 2) % 3 — sits strictly off it on the face's side of mesh_b. We dot the off-vertex against the splitter's original-face plane; the sign is the vote. Un-normalized cross-product normals are enough because we only care about the sign:

# Off-edge vertex of each mesh_a face on the cut
off_v = points[faces[a_face, (a_local + 2) % 3]]                 # (P, 3)

# Mesh_b splitter plane per incidence (un-normalized normal — sign is what we need)
B_v0 = points_b[faces_b[:, 0]]
B_n  = np.cross(points_b[faces_b[:, 1]] - B_v0,
                points_b[faces_b[:, 2]] - B_v0)

signed = np.einsum('ij,ij->i', off_v - B_v0[a_splitter], B_n[a_splitter])

Tally votes per component. Each NM edge contributes one signed vote per incident mesh_a face — multiple incidences per component, so any single noisy edge cannot flip the result. np.bincount aggregates positive and negative votes by component, and the majority sign is the label:

comp  = comp_labels[a_face]
plus  = np.bincount(comp, (signed > 0).astype(float), minlength=n_components)
minus = np.bincount(comp, (signed < 0).astype(float), minlength=n_components)
side  = np.where(plus >= minus, +1, -1)                          # +1 = +normal, -1 = -normal

for cid in np.unique(comp_labels[tag_labels == 0]):
    label = "+normal" if side[cid] > 0 else "-normal"
    print(f"component {cid}:  + {plus[cid]:.0f}  - {minus[cid]:.0f}  ->  {label}")

Running this on the two perpendicular planes (mesh_b's normal works out to -Y):

NM edges: 2   mesh_a incidences to classify: 4
component 1:  + 2  - 0  ->  +normal
component 2:  + 0  - 2  ->  -normal

Once you have side, picking the up- or down-side component is a single line: keep = mesh_a_components[side[mesh_a_components] == +1].

[graphic-goose]

Perfect, that does exactly what I wanted. Thank you!

Would be quite handy in the future to have a built-in function that could take in two Mesh objects (mesh_a and mesh_b) and the desired side of mesh_b, and have it return the part of mesh_a on that side.