SPLITMESH Return the connected components of a mesh.
MESHES = splitMesh(VERTICES, FACES) returns the connected components of
the mesh defined by vertices and faces as a struct array with the
fields vertices and faces sorted by increasing vertex number
MESHES = splitMesh(MESH) with the vertices-faces-struct MESH is also
possible
... = splitMesh(..., 'mostVertices') returns only the component with
the most vertices. Other options are 'all' (default),
'maxBoundingBox' that returns the component with the largest bounding
box, and 'maxVolume' returns the component with the largest volume.
Example
[v1, f1] = boxToMesh([1 0 -1 0 -1 0]);
[v2, f2] = boxToMesh([-1 0 1 0 -1 0]);
[v3, f3] = createSoccerBall;
f1 = triangulateFaces(f1);
f2 = triangulateFaces(f2);
f3 = triangulateFaces(f3);
[vertices, faces] = concatenateMeshes(v1, f1, v3, f3, v2, f2);
meshes = splitMesh(vertices, faces);
figure('color','w'); view(3); axis equal
cmap=hsv(length(meshes));
for m=1:length(meshes)
drawMesh(meshes(m), cmap(m,:))
end
See also
concatenateMeshes
Source
Local functions are part of the gptoolbox of Alec Jacobson
https://github.com/alecjacobson/gptoolbox0001 function meshes = splitMesh(vertices, faces, varargin) 0002 %SPLITMESH Return the connected components of a mesh. 0003 % 0004 % MESHES = splitMesh(VERTICES, FACES) returns the connected components of 0005 % the mesh defined by vertices and faces as a struct array with the 0006 % fields vertices and faces sorted by increasing vertex number 0007 % 0008 % MESHES = splitMesh(MESH) with the vertices-faces-struct MESH is also 0009 % possible 0010 % 0011 % ... = splitMesh(..., 'mostVertices') returns only the component with 0012 % the most vertices. Other options are 'all' (default), 0013 % 'maxBoundingBox' that returns the component with the largest bounding 0014 % box, and 'maxVolume' returns the component with the largest volume. 0015 % 0016 % 0017 % Example 0018 % [v1, f1] = boxToMesh([1 0 -1 0 -1 0]); 0019 % [v2, f2] = boxToMesh([-1 0 1 0 -1 0]); 0020 % [v3, f3] = createSoccerBall; 0021 % f1 = triangulateFaces(f1); 0022 % f2 = triangulateFaces(f2); 0023 % f3 = triangulateFaces(f3); 0024 % [vertices, faces] = concatenateMeshes(v1, f1, v3, f3, v2, f2); 0025 % meshes = splitMesh(vertices, faces); 0026 % figure('color','w'); view(3); axis equal 0027 % cmap=hsv(length(meshes)); 0028 % for m=1:length(meshes) 0029 % drawMesh(meshes(m), cmap(m,:)) 0030 % end 0031 % 0032 % See also 0033 % concatenateMeshes 0034 % 0035 % Source 0036 % Local functions are part of the gptoolbox of Alec Jacobson 0037 % https://github.com/alecjacobson/gptoolbox 0038 0039 % ------ 0040 % Author: oqilipo 0041 % E-mail: N/A 0042 % Created: 2017-09-17 0043 % Copyright 2017-2024 0044 0045 % input parsing 0046 if isstruct(vertices) 0047 if nargin > 1; varargin = [faces, varargin]; end 0048 [vertices, faces]=parseMeshData(vertices); 0049 end 0050 0051 parser = inputParser; 0052 validStrings = {'all','mostVertices','maxBoundingBox','maxVolume'}; 0053 addOptional(parser,'components','all',@(x) any(validatestring(x, validStrings))); 0054 parse(parser,varargin{:}); 0055 outputComp = validatestring(parser.Results.components, validStrings); 0056 0057 % algorithm 0058 CC = connected_components(faces); 0059 [a,~]=hist(CC,unique(CC)); 0060 [~,b] = sort(a); 0061 meshes=repmat(struct('vertices',[],'faces',[]),length(b),1); 0062 for cc=b 0063 meshes(cc)=removeMeshVertices(vertices, faces, ~(CC'==b(cc))); 0064 end 0065 0066 % output parsing 0067 switch outputComp 0068 case 'mostVertices' 0069 meshes=meshes(end); 0070 case 'maxBoundingBox' 0071 [~,sortingIndices] = sort(arrayfun(@(x) box3dVolume(boundingBox3d(x.vertices)), meshes)); 0072 meshes = meshes(sortingIndices(end)); 0073 case 'maxVolume' 0074 [~,sortingIndices] = sort(arrayfun(@(x) meshVolume(x.vertices, x.faces), meshes)); 0075 meshes = meshes(sortingIndices(end)); 0076 end 0077 0078 end 0079 0080 0081 %% Local functions are part of the gptoolbox by Alec Jacobson 0082 function C = connected_components(F) 0083 % CONNECTED_COMPONENTS Determine the connected components of a mesh 0084 % described by the simplex list F. Components are determined with respect 0085 % to the edges of the mesh. That is, a single component may contain 0086 % non-manifold edges and vertices. 0087 % 0088 % C = connected_components(F) 0089 % 0090 % Inputs: 0091 % F #F by simplex-size list of simplices 0092 % Outputs: 0093 % C #V list of ids for each CC 0094 % 0095 % Examples: 0096 % trisurf(F,V(:,1),V(:,2),V(:,3), ... 0097 % connected_components([F;repmat(size(V,1),1,3)])); 0098 0099 % build adjacency list 0100 A = adjacency_matrix(F); 0101 [~,C] = conncomp(A); 0102 end 0103 0104 function [A] = adjacency_matrix(E) 0105 % ADJACENCY_MATRIX Build sparse adjacency matrix from edge list or face list 0106 % 0107 % [A] = adjacency_matrix(E) 0108 % [A] = adjacency_matrix(F) 0109 % [A] = adjacency_matrix(T) 0110 % 0111 % Inputs: 0112 % E #E by 2 edges list 0113 % or 0114 % F #F by 3 triangle list 0115 % or 0116 % T #F by 4 tet list 0117 % Outputs: 0118 % A #V by #V adjacency matrix (#V = max(E(:))) 0119 % 0120 0121 if size(E,2)>2 0122 F = E; 0123 E = meshEdges(F); 0124 end 0125 0126 A = sparse([E(:,1) E(:,2)],[E(:,2) E(:,1)],1); 0127 end 0128 0129 function [S,C] = conncomp(G) 0130 % CONNCOMP Drop in replacement for graphconncomp.m from the bioinformatics 0131 % toobox. G is an n by n adjacency matrix, then this identifies the S 0132 % connected components C. This is also an order of magnitude faster. 0133 % 0134 % [S,C] = conncomp(G) 0135 % 0136 % Inputs: 0137 % G n by n adjacency matrix 0138 % Outputs: 0139 % S scalar number of connected components 0140 % C 0141 0142 % Transpose to match graphconncomp 0143 G = G'; 0144 0145 [p,~,r] = dmperm(G+speye(size(G))); 0146 S = numel(r)-1; 0147 C = cumsum(full(sparse(1,r(1:end-1),1,1,size(G,1)))); 0148 C(p) = C; 0149 end