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/gptoolbox
---------
Author: oqilipo
Created: 2017-09-17
Copyright 20170001 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 % Created: 2017-09-17 0042 % Copyright 2017 0043 0044 % input parsing 0045 if isstruct(vertices) 0046 if nargin > 1; varargin = [faces, varargin]; end 0047 [vertices, faces]=parseMeshData(vertices); 0048 end 0049 0050 parser = inputParser; 0051 validStrings = {'all','mostVertices','maxBoundingBox','maxVolume'}; 0052 addOptional(parser,'components','all',@(x) any(validatestring(x, validStrings))); 0053 parse(parser,varargin{:}); 0054 outputComp = validatestring(parser.Results.components, validStrings); 0055 0056 % algorithm 0057 CC = connected_components(faces); 0058 [a,~]=hist(CC,unique(CC)); 0059 [~,b] = sort(a); 0060 meshes=repmat(struct('vertices',[],'faces',[]),length(b),1); 0061 for cc=b 0062 meshes(cc)=removeMeshVertices(vertices, faces, ~(CC'==b(cc))); 0063 end 0064 0065 % output parsing 0066 switch outputComp 0067 case 'mostVertices' 0068 meshes=meshes(end); 0069 case 'maxBoundingBox' 0070 [~,sortingIndices] = sort(arrayfun(@(x) box3dVolume(boundingBox3d(x.vertices)), meshes)); 0071 meshes = meshes(sortingIndices(end)); 0072 case 'maxVolume' 0073 [~,sortingIndices] = sort(arrayfun(@(x) meshVolume(x.vertices, x.faces), meshes)); 0074 meshes = meshes(sortingIndices(end)); 0075 end 0076 0077 end 0078 0079 0080 %% Local functions are part of the gptoolbox by Alec Jacobson 0081 function C = connected_components(F) 0082 % CONNECTED_COMPONENTS Determine the connected components of a mesh 0083 % described by the simplex list F. Components are determined with respect 0084 % to the edges of the mesh. That is, a single component may contain 0085 % non-manifold edges and vertices. 0086 % 0087 % C = connected_components(F) 0088 % 0089 % Inputs: 0090 % F #F by simplex-size list of simplices 0091 % Outputs: 0092 % C #V list of ids for each CC 0093 % 0094 % Examples: 0095 % trisurf(F,V(:,1),V(:,2),V(:,3), ... 0096 % connected_components([F;repmat(size(V,1),1,3)])); 0097 0098 % build adjacency list 0099 A = adjacency_matrix(F); 0100 [~,C] = conncomp(A); 0101 end 0102 0103 function [A] = adjacency_matrix(E) 0104 % ADJACENCY_MATRIX Build sparse adjacency matrix from edge list or face list 0105 % 0106 % [A] = adjacency_matrix(E) 0107 % [A] = adjacency_matrix(F) 0108 % [A] = adjacency_matrix(T) 0109 % 0110 % Inputs: 0111 % E #E by 2 edges list 0112 % or 0113 % F #F by 3 triangle list 0114 % or 0115 % T #F by 4 tet list 0116 % Outputs: 0117 % A #V by #V adjacency matrix (#V = max(E(:))) 0118 % 0119 % See also: facet_adjacency_matrix 0120 % 0121 0122 if size(E,2)>2 0123 F = E; 0124 E = meshEdges(F); 0125 end 0126 0127 A = sparse([E(:,1) E(:,2)],[E(:,2) E(:,1)],1); 0128 end 0129 0130 function [S,C] = conncomp(G) 0131 % CONNCOMP Drop in replacement for graphconncomp.m from the bioinformatics 0132 % toobox. G is an n by n adjacency matrix, then this identifies the S 0133 % connected components C. This is also an order of magnitude faster. 0134 % 0135 % [S,C] = conncomp(G) 0136 % 0137 % Inputs: 0138 % G n by n adjacency matrix 0139 % Outputs: 0140 % S scalar number of connected components 0141 % C 0142 0143 % Transpose to match graphconncomp 0144 G = G'; 0145 0146 [p,~,r] = dmperm(G+speye(size(G))); 0147 S = numel(r)-1; 0148 C = cumsum(full(sparse(1,r(1:end-1),1,1,size(G,1)))); 0149 C(p) = C; 0150 end