meshVertexClustering

MESHVERTEXCLUSTERING Simplifies a mesh using vertex clustering.

   [V2, F2] = meshVertexClustering(V, F, SPACING)
   [V2, F2] = meshVertexClustering(MESH, SPACING)
   MESH2 = meshVertexClustering(...)

   Simplifies a mesh using vertex clustering. Input mesh is specified
   either by a pair V, F containing the vertex coordinates and the faces
   informations, or by a structure with fields 'vertices' and 'faces'.

   The SPACING input defines the size of the grid. It can be either a
   scalar (uniform grid) or a 1-by-3 row vector. 

   The output is specified either in two outputs, or in a structure with
   fields 'vertices' and 'faces'.

   Example
     [x, y, z]  = meshgrid(1:100, 1:100, 1:100);
     img = hypot3(x-51.12, y-52.23, z-53.34);
     [faces, vertices] = isosurface(img, 45);
     [v2, f2] = meshVertexClustering(vertices, faces, 10);
     figure; axis equal; axis([0 100 0 100 0 100]);
     drawMesh(v2, f2);

   See also
     reducepatch, smoothMesh

0001 function varargout = meshVertexClustering(vertices, faces, spacing, varargin)
0002 %MESHVERTEXCLUSTERING Simplifies a mesh using vertex clustering.
0003 %
0004 %   [V2, F2] = meshVertexClustering(V, F, SPACING)
0005 %   [V2, F2] = meshVertexClustering(MESH, SPACING)
0006 %   MESH2 = meshVertexClustering(...)
0007 %
0008 %   Simplifies a mesh using vertex clustering. Input mesh is specified
0009 %   either by a pair V, F containing the vertex coordinates and the faces
0010 %   informations, or by a structure with fields 'vertices' and 'faces'.
0011 %
0012 %   The SPACING input defines the size of the grid. It can be either a
0013 %   scalar (uniform grid) or a 1-by-3 row vector.
0014 %
0015 %   The output is specified either in two outputs, or in a structure with
0016 %   fields 'vertices' and 'faces'.
0017 %
0018 %   Example
0019 %     [x, y, z]  = meshgrid(1:100, 1:100, 1:100);
0020 %     img = hypot3(x-51.12, y-52.23, z-53.34);
0021 %     [faces, vertices] = isosurface(img, 45);
0022 %     [v2, f2] = meshVertexClustering(vertices, faces, 10);
0023 %     figure; axis equal; axis([0 100 0 100 0 100]);
0024 %     drawMesh(v2, f2);
0025 %
0026 %   See also
0027 %     reducepatch, smoothMesh
0028  
0029 % ------
0030 % Author: David Legland
0031 % e-mail: david.legland@inra.fr
0032 % Created: 2019-01-28,    using Matlab 9.5.0.944444 (R2018b)
0033 % Copyright 2019 INRA - Cepia Software Platform.
0034 
0035 
0036 %% Initialisation
0037 
0038 if isstruct(vertices)
0039     if nargin > 2
0040         varargin = [{spacing} varargin(:)];
0041     end
0042     spacing = faces;
0043 
0044     mesh = vertices;
0045     vertices = mesh.vertices;
0046     faces = mesh.faces;
0047 end
0048 
0049 % ensure input mesh is a triangulation
0050 faces = triangulateFaces(faces);
0051 
0052 % ensure spacing is a 1-by-3 array
0053 if isscalar(spacing)
0054     spacing = [spacing spacing spacing];
0055 end
0056 
0057 % extract grid origin
0058 origin = [0 0 0];
0059 if ~isempty(varargin)
0060     origin = varargin{1};
0061 end
0062 
0063 
0064 %% Apply grid simplification
0065 
0066 % identify the vertices belonging to the same grid
0067 [v2, I, J] = unique(round(bsxfun(@rdivide, bsxfun(@minus, vertices, origin), spacing)), 'rows');
0068 
0069 
0070 %% compute reduced vertex coordinates
0071 
0072 % compute coordinates of new vertices
0073 for iVertex = 1:length(I)
0074     gridVertices = vertices(J == iVertex, :);
0075     v2(iVertex, :) = mean(gridVertices, 1);
0076 end
0077 
0078 
0079 %% Compute new faces
0080 
0081 % create empty array
0082 faces2 = zeros(0, 3);
0083 
0084 % iterate over old faces, and keep only faces whose vertices belong to
0085 % different cell grids
0086 nFaces = size(faces, 1);
0087 for iFace = 1:nFaces
0088     % current face
0089     face = faces(iFace, :);
0090     
0091     % equivalent face with new vertices
0092     face2 = J(face)';
0093     
0094     % some vertices may belong to same cell, so we need to adjust
0095     % processing
0096     nInds = length(unique(face2));
0097     if nInds == 3
0098         % vertices belong to three different cells -> create a new face
0099         
0100         % keep smaller vertex at first position
0101         [tmp, indMin] = min(face2); %#ok<ASGLU>
0102         face2 = circshift(face2, [1-indMin 0]);
0103         
0104         % append the new face to the array
0105         faces2 = [faces2 ; face2]; %#ok<AGROW>
0106     end
0107 end
0108 
0109 % remove duplicate faces
0110 faces2 = unique(faces2, 'rows');
0111 
0112 if nargout == 1
0113     varargout{1} = struct('vertices', v2, 'faces', faces2);
0114 else
0115     varargout = {v2, faces2};
0116 end