Looking for code to detect disconnected parts of a geometry

Questions
1

I need to detect if a geometry has several disconnected pieces. If it does, need to create several geometries for each one of the pieces.

For example, for the mesh’s geometry on the following image, it would create 4 geometries/meshes.

Screenshot from 2022-11-20 23-24-11
Screenshot from 2022-11-20 23-24-11861×785 104 KB

Looking for code that implements this, or for implementation recommendations.
I was thinking of putting vertices/faces into a disjoint set structure to detect connected components. Is there a simpler way?

2

came up with this function, not sure yet if it fits into some library


function find(parents, x) {
	if (typeof parents[x] != "undefined") {
		if (parents[x] < 0) {
			return x; //x is a parent
		} else {
			//recurse until you find x's parent
			return find(parents, parents[x]);
		}
	} else {
		// initialize this node to it's on parent (-1)
		parents[x] = -1;
		// console.log("init", x)
		return x; //return the index of the parent
	}
}

function union(parents, x, y) {
	var xpar = find(parents, x);
	var ypar = find(parents, y);
	if (xpar != ypar) {
		// x's parent is now the parent of y also.
		// if y was a parent to more than one node, then
		// all of those nodes are now also connected to x's parent.
		parents[xpar] += parents[ypar];
		parents[ypar] = xpar;
		return false;
	} else {
		return true; //this link creates a cycle
	}
}

function split_mesh_islands(check_geom) {

	let parents = [];
	let new_geoms = [];

	for (let i = 0; i < check_geom.index.array.length; i+=3) {
		let v_index = [check_geom.index.array[i],
					   check_geom.index.array[i+1],
					   check_geom.index.array[i+2]];
		let tri = new THREE.Triangle();
		tri.a.fromBufferAttribute(check_geom.attributes.position, v_index[0]);
		tri.b.fromBufferAttribute(check_geom.attributes.position, v_index[1]);
		tri.c.fromBufferAttribute(check_geom.attributes.position, v_index[2]);
		if (isTriDegenerate(tri)) {
			console.warn("isTriDegenerate", i, tri);
			continue;
		}
		union(parents, check_geom.index.array[i], check_geom.index.array[i+1]);
		union(parents, check_geom.index.array[i+1], check_geom.index.array[i+2]);
		union(parents, check_geom.index.array[i], check_geom.index.array[i+2]);
	}

	for (let i = 0; i < parents.length; i++) {
		parents[i] = find(parents, parents[i]);
	}
	console.log("check_geom", check_geom)
	console.log("parents", check_geom.index.array.length, parents)

	for (let i = 0; i < parents.length; i++) {
		if (parents[i] < 0) {

			console.log("component", i, parents[i]);

			let new_geom = new THREE.BufferGeometry();
			let vertices = [];

			for (let j = 0; j < check_geom.index.array.length; j++) {
				if (parents[check_geom.index.array[j]] == i || check_geom.index.array[j] == i) {
					let v_index = check_geom.index.array[j];
					vertices.push(check_geom.attributes.position.getX(v_index));
					vertices.push(check_geom.attributes.position.getY(v_index));
					vertices.push(check_geom.attributes.position.getZ(v_index));
				}
			}

			// next, ignore indexes from the component
			for (let j = 0; j < parents.length; j++) {
				if (j == i || parents[j] == i) {
					parents[j] = parents.length;
				}
			}

			new_geom.setAttribute('position', new THREE.Float32BufferAttribute( vertices, 3 ));
			new_geoms.push(new_geom);
		}
	}

	return new_geoms;
}
1 Like
3

You should be able to do that by examining the indices of each face. To find separate geometries, you’d want to find sets of vertices for which there are no faces linking them.

Off the top of my head, I would try something like this:

  1. init an array of Sets to represent collections of vertices
  2. run through each face in the geo
  3. For each index in the face, find the set (if any) that contains that index
  4. There are three possibilities here:
    a) there are no existing sets that contain those indices. Add a new Set and init it with the indices of the current face
    b) all three indices are present in the same Set (having been added previously). Do nothing
    c) there are two or more Sets for the three vertices. Merge the Sets.
  5. Keep doing that until you’ve gone through all of the faces

At that point, you’ll have separated all the vertices into groups based on connectivity of faces. From there, you can create new geometries for each separate set of vertices.

Note that you’ll probably want the above Sets to contain the faces as well, so you might need a slightly more complex data structure.

Actually, now that I think about it- I think what you want is a lookup table for vertex index to “Collection” (where a Collection is a list of vertex indices and faces). That would give you O(1) for step 3, above, instead of O(number of current groupings).

You’ll also need to adjust the face indices when you create the new, separated geometries (since the new geo will have fewer vertices), but that should be straightforward.

Hope that helps, and good luck!