Here's a very compact algorithm for determining the manifold patches of a given triangle mesh (V,F). I'm defining a manifold patch to be a collection of neighboring facets in F such that they're union forms an edge-manifold submesh. A mesh is edge-manifold if no edge is shared by more than 2 facets.
Save this in a file called manifold_patches.m:
function [C,A] = manifold_patches(F)
% Compute connected components of facets connected by manifold edges.
%
% Inputs:
% F #F by simplex-size list of facets
% Outputs:
% C #F list of component ids
%
% simplex size
ss = size(F,2);
assert(ss == 3);
% List of all "half"-edges: 3*#F by 2
allE = [F(:,[2 3]); F(:,[3 1]); F(:,[1 2])];
% Sort each row
sortallE = sort(allE,2);
% IC(i) tells us where to find sortallE(i,:) in uE:
% so that sortallE(i,:) = uE(IC(i),:)
[uE,~,IC] = unique(sortallE,'rows');
% uE2F(e,f) = 1 means face f is adjacent to unique edge e
uE2F = sparse(IC(:),repmat(1:size(F,1),1,ss)',1);
% kill non-manifold edges
uE2F(sum(uE2F,2)>2,:) = 0;
% Face-face Adjacency matrix
A = uE2F'*uE2F;
% All ones
A = A>0;
% Connected components are patches
%C = components(A); % alternative to graphconncomp from matlab_bgl
[~,C] = graphconncomp(A);
end
The "trick" if there is one, is that we first build an undirected edge to facet adjacency matrix. We zap-out any rows corresponding to edges with more than two incident facts. Then we "square" this matrix to give use a facet to facet adjacency matrix where two facets are neighbors iff the edge they share have only two incident facets. Finally we use a library call to compute the connected components of the graph induced by this adjacency matrix.
Here's the result on an example, all manifold patches visualized with a unique pseudocolor:
And for comparison here's a visualization of the graph connected components (defined per vertex, neighboring vertices share an edge).
