Mercurial > octave
view scripts/plot/draw/reducepatch.m @ 29358:0a5b15007766 stable
update Octave Project Developers copyright for the new year
In files that have the "Octave Project Developers" copyright notice,
update for 2021.
author | John W. Eaton <jwe@octave.org> |
---|---|
date | Wed, 10 Feb 2021 09:52:15 -0500 |
parents | a4268efb7334 |
children | 7854d5752dd2 |
line wrap: on
line source
######################################################################## ## ## Copyright (C) 2016-2021 The Octave Project Developers ## ## See the file COPYRIGHT.md in the top-level directory of this ## distribution or <https://octave.org/copyright/>. ## ## This file is part of Octave. ## ## Octave is free software: you can redistribute it and/or modify it ## under the terms of the GNU General Public License as published by ## the Free Software Foundation, either version 3 of the License, or ## (at your option) any later version. ## ## Octave is distributed in the hope that it will be useful, but ## WITHOUT ANY WARRANTY; without even the implied warranty of ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ## GNU General Public License for more details. ## ## You should have received a copy of the GNU General Public License ## along with Octave; see the file COPYING. If not, see ## <https://www.gnu.org/licenses/>. ## ######################################################################## ## -*- texinfo -*- ## @deftypefn {} {@var{reduced_fv} =} reducepatch (@var{fv}) ## @deftypefnx {} {@var{reduced_fv} =} reducepatch (@var{faces}, @var{vertices}) ## @deftypefnx {} {@var{reduced_fv} =} reducepatch (@var{patch_handle}) ## @deftypefnx {} {} reducepatch (@var{patch_handle}) ## @deftypefnx {} {@var{reduced_fv} =} reducepatch (@dots{}, @var{reduction_factor}) ## @deftypefnx {} {@var{reduced_fv} =} reducepatch (@dots{}, "fast") ## @deftypefnx {} {@var{reduced_fv} =} reducepatch (@dots{}, "verbose") ## @deftypefnx {} {[@var{reduced_faces}, @var{reduces_vertices}] =} reducepatch (@dots{}) ## ## Reduce the number of faces and vertices in a patch object while retaining ## the overall shape of the patch. ## ## The input patch can be represented by a structure @var{fv} with the ## fields @code{faces} and @code{vertices}, by two matrices @var{faces} and ## @var{vertices} (see, e.g., the result of @code{isosurface}), or by a ## handle to a patch object @var{patch_handle} (@pxref{XREFpatch,,patch}). ## ## The number of faces and vertices in the patch is reduced by iteratively ## collapsing the shortest edge of the patch to its midpoint (as discussed, ## e.g., here: ## @url{https://libigl.github.io/libigl/tutorial/tutorial.html#meshdecimation}). ## ## Currently, only patches consisting of triangles are supported. The ## resulting patch also consists only of triangles. ## ## If @code{reducepatch} is called with a handle to a valid patch ## @var{patch_handle}, and without any output arguments, then the given ## patch is updated immediately. ## ## If the @var{reduction_factor} is omitted, the resulting structure ## @var{reduced_fv} includes approximately 50% of the faces of the original ## patch. If @var{reduction_factor} is a fraction between 0 (excluded) and 1 ## (excluded), a patch with approximately the corresponding fraction of faces ## is determined. ## If @var{reduction_factor} is an integer greater than or equal to 1, the ## resulting patch has approximately @var{reduction_factor} faces. Depending ## on the geometry of the patch, the resulting number of faces can differ from ## the given value of @var{reduction_factor}. This is especially true when ## many shared vertices are detected. ## ## For the reduction, it is necessary that vertices of touching faces are ## shared. Shared vertices are detected automatically. This detection can be ## skipped by passing the optional string argument @qcode{"fast"}. ## ## With the optional string arguments @qcode{"verbose"}, additional status ## messages are printed to the command window. ## ## Any string input arguments must be passed after all other arguments. ## ## If called with one output argument, the reduced faces and vertices are ## returned in a structure @var{reduced_fv} with the fields @code{faces} and ## @code{vertices} (see the one output option of @code{isosurface}). ## ## If called with two output arguments, the reduced faces and vertices are ## returned in two separate matrices @var{reduced_faces} and ## @var{reduced_vertices}. ## ## @seealso{isosurface, isonormals, reducevolume, patch} ## @end deftypefn ## FIXME: Convert faces to only triangles if necessary function varargout = reducepatch (varargin) if (nargin < 1 || nargin > 5) print_usage (); endif [faces, vertices, max_faces, patch_handle, fast, verbose] = ... __get_check_reducepatch_args__ (varargin{:}); if (verbose) printf (["reducepatch: before reduction of faces: ", ... "%5d faces, %5d vertices\n"], rows (faces), rows (vertices)); endif if (max_faces >= rows (faces)) faces_reduced = faces; vertices_reduced = vertices; else if (! fast) [faces, vertices] = __unite_shared_vertices__ (faces, vertices); if (verbose) printf (["reducepatch: after detection of shared vertices: ", ... "%5d faces, %5d vertices\n"], rows (faces), rows (vertices)); endif endif [faces_reduced, vertices_reduced] = ... __reducepatch__ (vertices, faces, max_faces, verbose); endif if (verbose) printf (["reducepatch: after reduction of faces: ", ... "%5d faces, %5d vertices\n"], ... rows (faces_reduced), rows (vertices_reduced)); endif ## output if (! isempty (patch_handle) && nargout == 0) ## update patch object set (patch_handle, "Faces", faces_reduced, "Vertices", vertices_reduced); elseif (nargout == 2) # faces, vertices varargout{1} = faces_reduced; varargout{2} = vertices_reduced; else # fv structure varargout{1}.faces = faces_reduced; varargout{1}.vertices = vertices_reduced; endif endfunction ## assign input parameters and check their validity function [faces, vertices, max_faces, patch_handle, fast, verbose] = ... __get_check_reducepatch_args__ (varargin) ## default values faces = vertices = max_faces = patch_handle = []; reduction_factor = 0.5; fast = verbose = false; num_string_inputs = 0; ## check whether last 2 input arguments are strings and assign parameters valid_vals = nargin:-1:nargin-1; valid_vals(valid_vals < 1) = []; for arg = varargin(valid_vals) if (! ischar (arg{1})) break; # no string arguments at end, exit checking endif switch (tolower (arg{1})) case {"f", "fast"} fast = true; num_string_inputs += 1; case {"v", "verbose"} verbose = true; num_string_inputs += 1; case "" num_string_inputs++; ## silently ignore empty strings otherwise error ("reducepatch: parameter '%s' not supported", arg{1}); endswitch endfor ## get faces and vertices i_fv = 1; arg1 = varargin{1}; if (isstruct (arg1)) if (all (isfield (arg1, {"vertices", "faces"}))) vertices = arg1.vertices; faces = arg1.faces; else error (["reducepatch: struct FV must contain the fields ", ... "'vertices' and 'faces'."]); endif elseif (isscalar (arg1)) patch_handle = arg1; if (isgraphics (patch_handle, "patch")) vertices = get (patch_handle, "Vertices"); faces = get (patch_handle, "Faces"); else error ("reducepatch: PATCH_HANDLE must be a valid handle to a patch"); endif elseif (ismatrix (arg1)) faces = arg1; if (nargin - num_string_inputs > 1 && ismatrix (varargin{2})) vertices = varargin{2}; i_fv = 2; else error (["reducepatch: If first argument is a matrix containing ", ... "FACES, second argument must be a matrix containing VERTICES"]); endif else print_usage ("reducepatch"); endif ## get reduction_factor if (nargin - num_string_inputs > i_fv) reduction_factor = varargin{i_fv + 1}; if (! isscalar (reduction_factor) || reduction_factor <= 0) error ("reducepatch: REDUCTION_FACTOR must be a positive scalar"); endif endif ## check faces and vertices if (columns (vertices) != 3) error ("reducepatch: VERTICES must be an Mx3 matrix"); endif if (columns (faces) != 3) ## FIXME: Convert faces to only triangles if necessary error ("reducepatch: Currently patches must consist of triangles only"); endif if (any (mod (faces(:), 1)) || any (faces(:) < 1)) error ("reducepatch: FACES must consist of positive integer indices only"); endif if (max (faces(:)) > rows (vertices)) error ("reducepatch: not enough VERTICES for given FACES"); endif ## get max_faces num_faces = rows (faces); if (reduction_factor < 1) max_faces = floor (num_faces * reduction_factor); else max_faces = reduction_factor; endif endfunction ## actual function to reduce number of faces function [faces_reduced, vertices_reduced] = ... __reducepatch__ (vertices, faces, max_faces, verbose) num_faces = rows (faces); faces = sort (faces, 2); ## get all unique edges all_edges = sort ([faces(:,1) faces(:,2); faces(:,2) faces(:,3); faces(:,3) faces(:,1)], 2); edges = unique (all_edges, "rows"); num_edges = rows (edges); ## calculate length of edges edge_length = norm (vertices(edges(:,1),:) - vertices(edges(:,2),:), ... 2, "rows"); if (verbose) printf ("reducepatch: reducing number of faces"); ## do not spam the command window with dots if many faces are collapsed verbose_stepwidth = (num_faces - max_faces) / 100; # max. 100 dots verbose_counter = 0; endif ## reduce number of faces clean_finish = true; do ## find shortest edge i_shortest_edge = find (edge_length == min (edge_length), 1, "first"); if (any (isinf (vertices(edges(i_shortest_edge,:),:)))) warning (["reducepatch: shortest edge is marked as deleted. ", ... "This should never happen."]) clean_finish = false; break; endif start_point_idx = edges(i_shortest_edge,1); end_point_idx = edges(i_shortest_edge,2); ## collapse the edge to its midpoint vertices(start_point_idx,:) = 0.5 * ... (vertices(start_point_idx,:) + vertices(end_point_idx,:)); ## endpoint will be deleted later ## remove collapsed edge info edges(i_shortest_edge,:) = []; edge_length(i_shortest_edge) = []; ## unite collapsed edges of neighboring faces to one edge faces_with_collapsed_edge = any (faces == start_point_idx, 2) & ... any (faces == end_point_idx, 2); edges_of_collapsed_faces = faces(faces_with_collapsed_edge,:); ## get other vertex of collapsed faces third_vertices = ... edges_of_collapsed_faces(... faces(faces_with_collapsed_edge,:) != start_point_idx & ... faces(faces_with_collapsed_edge,:) != end_point_idx); if (! isempty (third_vertices)) ## delete edge of the collapsed faces which also has end_point ## (keep the one with start_point) edges_to_delete = any (edges == end_point_idx, 2) & ... any (any (bsxfun (@eq, edges, ... reshape (third_vertices, 1, 1, [])), 3), 2); edges(edges_to_delete,:) = []; edge_length(edges_to_delete) = []; endif ## mark the faces that collapsed for later removal faces(faces_with_collapsed_edge,:) = Inf; ## update the lengths of the moved edges edges_with_moved_point = any (edges == start_point_idx, 2); edge_length(edges_with_moved_point) = ... norm (vertices(edges(edges_with_moved_point,1),:) - ... vertices(edges(edges_with_moved_point,2),:), 2, "rows"); ## replace all vertices that use end_point to use start_point if (start_point_idx != end_point_idx) edges(edges == end_point_idx) = start_point_idx; faces(faces == end_point_idx) = start_point_idx; vertices(end_point_idx,:) = Inf; # mark vertex for later removal endif ## Pretty print a row of dots while performing calculation if (verbose && ++verbose_counter > verbose_stepwidth) printf ("."); verbose_counter = 0; endif until (max_faces > num_faces - sum (isinf (faces(:,1)))) if (verbose) printf ("\n"); endif if (! clean_finish) ## FIXME: What should be done in this case? ## continue anyway? endif ## finally, remove vertices and faces removed_vertices = isinf (vertices(:,1)); vertices_reduced = vertices(! removed_vertices,:); faces_reduced = faces(! isinf (faces(:,1)),:); ## renumber vertices in faces with subsequent numbers vertex_renum = ones (rows (vertices), 1); vertex_renum(removed_vertices) = 0; vertex_renum = cumsum (vertex_renum); faces_reduced = vertex_renum(faces_reduced); endfunction %!demo %! clf; %! [x,y,z] = meshgrid (-2:0.5:2, -2:0.5:2, -2:0.5:2); %! val = x.^2 + y.^2 + z.^2; %! fv = isosurface (x, y, z, val, 1); %! ax1 = subplot (1, 2, 1); %! patch (fv, "FaceColor", "g"); %! view (3); axis equal; %! title ("Sphere with all faces"); %! ax2 = subplot(1, 2, 2); %! patch (reducepatch (fv, 72), "FaceColor", "g"); %! view (3); axis equal; %! title ("Sphere with reduced number of faces"); %! linkprop ([ax1, ax2], {"CameraPosition", "CameraUpVector"}); %!shared faces, vertices, fv, num_faces %! [x,y,z] = meshgrid (-2:0.5:2, -2:0.5:2, -2:0.5:2); %! val = x.^2 + y.^2 + z.^2; %! [faces, vertices] = isosurface (x, y, z, val, 1); %! fv.faces = faces; fv.vertices = vertices; %! num_faces = rows (faces); ## one input (structure), one output %!test %! fv_reduced = reducepatch (fv); %! assert (size (fv_reduced.faces, 1), num_faces * .5, 3); %! assert (size (fv_reduced.faces, 2), 3); %! assert (size (fv_reduced.vertices, 2), 3); ## two inputs (faces, vertices), one output %!test %! fv_reduced = reducepatch (faces, vertices); %! assert (size (fv_reduced.faces, 1), num_faces * .5, 3); %! assert (size (fv_reduced.faces, 2), 3); %! assert (size (fv_reduced.vertices, 2), 3); ## two inputs (structure, reduction_factor > 1), two outputs %!test %! [faces_reduced, vertices_reduced] = reducepatch (fv, 20); %! assert (size (faces_reduced, 1), 20, 3); %! assert (size (faces_reduced, 2), 3); %! assert (size (vertices_reduced, 2), 3); ## three inputs (faces, vertices, reduction_factor < 1), two outputs %!test %! [faces_reduced, vertices_reduced] = reducepatch (faces, vertices, .5); %! assert (size (faces_reduced, 1), num_faces * .5, 3); %! assert (size (faces_reduced, 2), 3); %! assert (size (vertices_reduced, 2), 3); ## two inputs (structure, reduction_factor < 1) + one string, no outputs ## (update patch object in figure) %!test %! h_fig = figure ("visible", "off"); %! p = patch (fv); %! reducepatch (p, .35, "f"); %! assert (size (get (p, "Faces"), 1), num_faces * .35, 3); %! assert (size (get (p, "Faces"), 2), 3); %! assert (size (get (p, "Vertices"), 2), 3); %! close (h_fig); ## three inputs (faces, vertices, reduction_factor > 1) + one empty ## string, one output %!test %! fv_reduced = reducepatch (faces, vertices, 52, ""); %! assert (size (fv_reduced.faces, 1), 52, 3); %! assert (size (fv_reduced.faces, 2), 3); %! assert (size (fv_reduced.vertices, 2), 3); ## two inputs (structure, reduction_factor < 1) + one string, two outputs %!test %! [faces_reduced, vertices_reduced] = reducepatch (fv, .4, "fast"); %! assert (size (faces_reduced, 1), num_faces * .4, 3); %! assert (size (faces_reduced, 2), 3); %! assert (size (vertices_reduced, 2), 3); ## one input (structure) + two (empty) strings, two outputs %!test %! [faces_reduced, vertices_reduced] = reducepatch (fv, "f", ""); %! assert (size (faces_reduced, 1), num_faces * .5, 3); %! assert (size (faces_reduced, 2), 3); %! assert (size (vertices_reduced, 2), 3); ## test for each error %!error reducepatch () %!error reducepatch (fv, faces, vertices, .5, "f", "v") %!error <reducepatch: parameter 'foo' not supported> %! fv_reduced = reducepatch (faces, vertices, .7, "foo"); %!error <struct FV must contain the fields 'vertices' and 'faces'> %! fv_incomplete.faces = faces; %! reducepatch (fv_incomplete, .7); %!error <PATCH_HANDLE must be a valid handle to a patch> reducepatch (pi, .7) %!error <If first argument is a matrix containing FACES, second argument must be a matrix containing VERTICES> reducepatch (faces) %!error <REDUCTION_FACTOR must be a positive scalar> reducepatch (fv, [.7 .5]) %!error <REDUCTION_FACTOR must be a positive scalar> reducepatch (fv, -5) %!error <VERTICES must be an Mx3 matrix> reducepatch (faces, .7, "v") %!error <reducepatch: Currently patches must consist of triangles only> %! faces_new = NaN (size (faces, 1), 4); %! faces_new(:,1:3) = faces; %! faces_new(1,4) = 5; %! reducepatch (faces_new, vertices); %!error <reducepatch: not enough VERTICES for given FACES> %! faces_new = faces; %! faces_new(1,3) = size (vertices, 1) + 1; %! reducepatch (faces_new, vertices);