cut_graph
Compute a cut graph of mesh, such that surface becomes simply-connected if slice mesh along the cut-graph. There are two versions: if both face and vertex provided, invoke version 1; if only face provided, invoke version 2. Version 1 is exact implementation of algorithm 3 in book [1]. Version 2 is translated from David Gu's C++ code of cut graph, which is much faster then version 1.
Though version 1 takes vertex into consideration, both algorithms do not generated optimal cut graph (shortest one). In face this problem seems to be open until now.
Contents
Syntax
ee = cut_graph(face) ee = cut_graph(face,vertex)
Description
face : double array, nf x 3, connectivity of mesh vertex: double array, nv x 3, vertex of mesh
ee: double array, n x 2, edges in the cut graph, each row is an edge on mesh, may not be in consecutive order. ee's mainly purpose is been passed to slice_mesh, which will slice the mesh open along edges in ee, to form a simply-connected surface
Contribution
Author : Wen Cheng Feng Created: 2014/03/13 Revised: 2014/03/13 by Wen, implement another cut graph algorithm Revised: 2014/03/17 by Wen, merge two cut graph algorithm
Copyright 2014 Computational Geometry Group Department of Mathematics, CUHK http://www.math.cuhk.edu.hk/~lmlui
function ee = cut_graph(face,vertex) if nargin == 2 [amf,dual_vertex] = compute_dual_graph(face,vertex); [edge,eif] = compute_edge(face); [I,J,~] = find(amf); % edge length of original mesh as weight el = zeros(size(I)); for i=1:length(I) ei = face_intersect(face(I(i),:),face(J(i),:)); el(i) = norm(vertex(ei(1),:)-vertex(ei(2),:)); end graph = sparse(I,J,-el); if exist('graphminspantree') tree = graphminspantree(graph,'Method','Kruskal'); else tree = minimum_spanning_tree(graph); end % edge length of dual mesh as weight % dual_el = sqrt(dot(dual_vertex(I,:)-dual_vertex(J,:),dual_vertex(I,:)-dual_vertex(J,:),2)); % tree = graphminspantree(amf,'METHOD','Prim','Weights',dual_el); tree = tree+tree'; [I,J,~] = find(tree); [~,ia] = setdiff(eif,[I,J],'rows'); de = edge(ia,:); nv = size(vertex,1); G = sparse(de(:,1),de(:,2),ones(size(de,1),1),nv,nv); elseif nargin == 1 [am,amd] = compute_adjacency_matrix(face); nf = size(face,1); % use array to emulate queue queue = zeros(nf,1); queue(1) = 1; qs = 1; % point to queue start qe = 2; % point to queue end ft = false(nf,1); ft(1) = true; face4 = face(:,[1 2 3 1]); % translated from David Gu's cut graph algorithm % this algorithm will not take geometry into consideration, thus result is % not as visually good as cut_graph, but faster. while qe > qs fi = queue(qs); qs = qs+1; for i = 1:3 he = face4(fi,[i i+1]); sf = amd(he(2),he(1)); if sf if ~ft(sf) queue(qe) = sf; qe = qe+1; ft(sf) = true; am(he(1),he(2)) = -1; % am(he(2),he(1)) = 0; end end end end am((am<0)') = 0; G = triu(am>0); end % prune the graph cut while true Gs = full(sum(G,2))+full(sum(G,1))'; ind = (Gs == 1); if sum(ind) ==0 break; end G(ind,:) = 0; G(:,ind) = 0; end [I,J,~] = find(G); ee = [I,J]; function e = face_intersect(f1,f2) b = f1==f2(1); e1 = f1(b); b = f1==f2(2); e2 = f1(b); b = f1==f2(3); e3 = f1(b); e = [e1,e2,e3];