vb_separate_surf

 extract each connected surface
  [Fall, Vall, Nall, Vinx] = vb_separate_surf(F,V)
 --- Input
 V : vertex of surface
 F : patch index
 --- Output
 Vall{n} : vertex of n-th connected surface
 Fall{n} : patch index of n-th connected surface
 Nall(n) : # of points for n-th connected surface
 Vinx{n} : original vertex index of n-th connected surface

 Ver 1.0  by M. Sato  2006-6-4
  M. Sato  2008-1-16 changed start index
 Ver 2.0
  M. Sato  2008-7-26 changed algorithm
     seedID is not used (remained for old version compatibility)
 ポリゴンモデルの連結面を取り出す

 　 アルゴリズム 
０．周辺頂点リストに関するループ
１．周辺頂点リストからルート頂点を選ぶ
２．ルート点の未処理隣接三角面を探す
３．隣接三角面頂点を連結頂点リストと候補 周辺頂点リストに加える
４．未処理の周辺頂点が残っていれば１へ戻る
５．候補 周辺頂点リストを新しい周辺頂点リストにして０に戻る

 Copyright (C) 2011, ATR All Rights Reserved.
 License : New BSD License(see VBMEG_LICENSE.txt)

0001 function    [Fall, Vall, Nall, Vinx] = vb_separate_surf(F,V,seedID)
0002 % extract each connected surface
0003 %  [Fall, Vall, Nall, Vinx] = vb_separate_surf(F,V)
0004 % --- Input
0005 % V : vertex of surface
0006 % F : patch index
0007 % --- Output
0008 % Vall{n} : vertex of n-th connected surface
0009 % Fall{n} : patch index of n-th connected surface
0010 % Nall(n) : # of points for n-th connected surface
0011 % Vinx{n} : original vertex index of n-th connected surface
0012 %
0013 % Ver 1.0  by M. Sato  2006-6-4
0014 %  M. Sato  2008-1-16 changed start index
0015 % Ver 2.0
0016 %  M. Sato  2008-7-26 changed algorithm
0017 %     seedID is not used (remained for old version compatibility)
0018 % ポリゴンモデルの連結面を取り出す
0019 %
0020 % 　 アルゴリズム
0021 %０．周辺頂点リストに関するループ
0022 %１．周辺頂点リストからルート頂点を選ぶ
0023 %２．ルート点の未処理隣接三角面を探す
0024 %３．隣接三角面頂点を連結頂点リストと候補 周辺頂点リストに加える
0025 %４．未処理の周辺頂点が残っていれば１へ戻る
0026 %５．候補 周辺頂点リストを新しい周辺頂点リストにして０に戻る
0027 %
0028 % Copyright (C) 2011, ATR All Rights Reserved.
0029 % License : New BSD License(see VBMEG_LICENSE.txt)
0030 
0031 Npoint = size(V,1);
0032 Npatch = size(F,1);      % 三角面数
0033 
0034 Plist = zeros(Npoint,1);    % 候補頂点リスト
0035 Vlist = zeros(Npoint,1);    % 頂点リスト
0036 
0037 Vflg  = zeros(Npoint,1);    % 頂点処理済みフラグ
0038 Fflg  = zeros(Npatch,1);    % 三角面処理済みフラグ
0039 
0040 % Vertex index inside surface 'F'
0041 Vindx = unique(F(:));
0042 
0043 % Discard vertex outside 'F'
0044 Vflg(:) = -1;
0045 Vflg(Vindx) = 0;
0046 
0047 % 隣接三角面インデックスリストの作成
0048 % xxF{n} : 頂点 n に隣接する面の頂点番号と面番号
0049 xxF  = vb_neighbor_index(V,F);
0050 
0051 % ルートインデックス
0052 seedID = Vindx(1);
0053 Plist(1) = [seedID];
0054 
0055 Nsurf = 1;
0056 Nall  = [];
0057 Vflg(seedID) = Nsurf;
0058 Nlist = 1;% 候補 周辺頂点数
0059 Ntotal = 0;
0060 
0061 while 1,
0062     
0063     while Nlist > 0,
0064         Vlist(:) = 0;    % 周辺頂点リスト
0065         
0066         % 周辺頂点に関するループ
0067         for n=1:Nlist,
0068             % root インデックスの更新
0069             root = Plist(n);
0070             
0071             % root の隣接点インデックスリスト
0072             nextID = xxF{root};     
0073             
0074             % 隣接点リスト
0075             nlist1 = nextID(:,1);     % 隣接点リスト1
0076             nlist2 = nextID(:,2);     % 隣接点リスト2
0077             flist  = nextID(:,3);     % 隣接三角面リスト
0078             
0079             % 未処理の面インデックスを探す
0080             nextix = find( Fflg(flist) == 0 );
0081             
0082             if isempty(nextix), continue;  end;
0083             
0084             % 未処理面のインデックスリスト
0085             nlist1 = nlist1(nextix);
0086             nlist2 = nlist2(nextix);
0087             flist  = flist(nextix);
0088             
0089             Fflg(flist) = Nsurf;
0090             Vlist(nlist1) = 1;
0091             Vlist(nlist2) = 1;
0092             
0093         end;
0094         % END-周辺頂点に関するループ
0095         
0096         % Next root index
0097         ix = find(Vlist == 1 & Vflg == 0);
0098         
0099         Nlist = length(ix);
0100         if Nlist == 0, break; end;
0101         
0102         % 候補 周辺頂点リストの更新
0103         Plist(1:Nlist) = ix;
0104         Vflg(ix) = Nsurf;
0105         Ntotal = Ntotal + Nlist;
0106     end
0107     % --- END of connected surface search ---
0108     
0109     % 処理済みの頂点数
0110     ix = find(Vflg == Nsurf);
0111     Nall(Nsurf) = length(ix);
0112     
0113     % 未処理の頂点を取り出す
0114     ix_rest = find(Vflg == 0);
0115     Nrest = length(ix_rest);
0116     
0117     fprintf('Nsurf= %d, N= %d, Ntotal=%d, Nrest=%d\n', ...
0118             Nsurf,Nall(Nsurf),Ntotal,Nrest)
0119 
0120     if isempty(ix_rest), break; end;
0121     
0122     Nlist = 1;
0123     Nsurf = Nsurf + 1;
0124     seedID = ix_rest(1);
0125     Plist(1) = seedID;
0126     Vflg(seedID) = Nsurf;
0127 end
0128 
0129 % 大きい面の順に並び替え
0130 [Nall , id]= sort( -Nall );
0131 
0132 Vinx = cell(Nsurf,1);
0133 Vall = cell(Nsurf,1);
0134 Fall = cell(Nsurf,1);
0135 
0136 for n=1:Nsurf
0137     % id(n)-番目の面の頂点を取り出す
0138     indx = find( Vflg == id(n) );
0139     [Vnew, Fnew] = vb_trans_index( V, F, indx);
0140     Nall(n) = length(indx);
0141     Vinx{n} = indx;
0142     Vall{n} = Vnew;
0143     Fall{n} = Fnew;
0144 end
0145 
0146 return
0147 
0148