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@inrae.fr
0032 % Created: 2019-01-28, using Matlab 9.5.0.944444 (R2018b)
0033 % Copyright 2019-2024 INRA - Cepia Software Platform
0034 
0035 %% Initialisation
0036 
0037 if isstruct(vertices)
0038     if nargin > 2
0039         varargin = [{spacing} varargin(:)];
0040     end
0041     spacing = faces;
0042 
0043     mesh = vertices;
0044     vertices = mesh.vertices;
0045     faces = mesh.faces;
0046 end
0047 
0048 % ensure input mesh is a triangulation
0049 faces = triangulateFaces(faces);
0050 
0051 % ensure spacing is a 1-by-3 array
0052 if isscalar(spacing)
0053     spacing = [spacing spacing spacing];
0054 end
0055 
0056 % extract grid origin
0057 origin = [0 0 0];
0058 if ~isempty(varargin)
0059     origin = varargin{1};
0060 end
0061 
0062 
0063 %% Apply grid simplification
0064 
0065 % identify the vertices belonging to the same grid
0066 [v2, I, J] = unique(round(bsxfun(@rdivide, bsxfun(@minus, vertices, origin), spacing)), 'rows');
0067 
0068 
0069 %% compute reduced vertex coordinates
0070 
0071 % compute coordinates of new vertices
0072 for iVertex = 1:length(I)
0073     gridVertices = vertices(J == iVertex, :);
0074     v2(iVertex, :) = mean(gridVertices, 1);
0075 end
0076 
0077 
0078 %% Compute new faces
0079 
0080 % create empty array
0081 faces2 = zeros(0, 3);
0082 
0083 % iterate over old faces, and keep only faces whose vertices belong to
0084 % different cell grids
0085 nFaces = size(faces, 1);
0086 for iFace = 1:nFaces
0087     % current face
0088     face = faces(iFace, :);
0089     
0090     % equivalent face with new vertices
0091     face2 = J(face)';
0092     
0093     % some vertices may belong to same cell, so we need to adjust
0094     % processing
0095     nInds = length(unique(face2));
0096     if nInds == 3
0097         % vertices belong to three different cells -> create a new face
0098         
0099         % keep smaller vertex at first position
0100         [tmp, indMin] = min(face2); %#ok<ASGLU>
0101         face2 = circshift(face2, [1-indMin 0]);
0102         
0103         % append the new face to the array
0104         faces2 = [faces2 ; face2]; %#ok<AGROW>
0105     end
0106 end
0107 
0108 % remove duplicate faces
0109 faces2 = unique(faces2, 'rows');
0110 
0111 if nargout == 1
0112     varargout{1} = struct('vertices', v2, 'faces', faces2);
0113 else
0114     varargout = {v2, faces2};
0115 end