vb_out_normal

 extract connected surface & make normal vector outward
  [Fnew, Vnew, xxn, Vmiss, Fmiss] = vb_out_normal(F,V)
 --- Input
 V : vertex of surface
 F : patch index
 --- Output
 Vnew : vertex of connected surface
 Fnew : patch index
 xxn  : normal vector
 Vmiss : disconnected vertex
 Fmiss : patch index for disconnected surface

 M. Sato  2006-6-4

 ポリゴンモデルの三角面法線の向きを外向きに揃える

 　 アルゴリズム 
０．候補 周辺頂点リストに関するループ
１．候補 周辺頂点リストからルート頂点を選ぶ
２．ルート点の未処理隣接三角面を探す
３．隣接三角面の中で前回最終頂点を含むものを探す
４．三角面頂点の並び方を揃える
５．三角面のもう一つの頂点を今回の最終頂点にする
６．周辺頂点リストに向きを確定した辺の頂点を追加する
７．未処理面が残っていれば２へ戻る
８．未処理の周辺頂点が残っていれば１へ戻る
９．確定した周辺頂点リストを新しい候補リストにして０に戻る

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

0001 function    [Fnew, Vnew, xxn, Vmiss, Fmiss] = vb_out_normal(F,V,seedID)
0002 % extract connected surface & make normal vector outward
0003 %  [Fnew, Vnew, xxn, Vmiss, Fmiss] = vb_out_normal(F,V)
0004 % --- Input
0005 % V : vertex of surface
0006 % F : patch index
0007 % --- Output
0008 % Vnew : vertex of connected surface
0009 % Fnew : patch index
0010 % xxn  : normal vector
0011 % Vmiss : disconnected vertex
0012 % Fmiss : patch index for disconnected surface
0013 %
0014 % M. Sato  2006-6-4
0015 %
0016 % ポリゴンモデルの三角面法線の向きを外向きに揃える
0017 %
0018 % 　 アルゴリズム
0019 %０．候補 周辺頂点リストに関するループ
0020 %１．候補 周辺頂点リストからルート頂点を選ぶ
0021 %２．ルート点の未処理隣接三角面を探す
0022 %３．隣接三角面の中で前回最終頂点を含むものを探す
0023 %４．三角面頂点の並び方を揃える
0024 %５．三角面のもう一つの頂点を今回の最終頂点にする
0025 %６．周辺頂点リストに向きを確定した辺の頂点を追加する
0026 %７．未処理面が残っていれば２へ戻る
0027 %８．未処理の周辺頂点が残っていれば１へ戻る
0028 %９．確定した周辺頂点リストを新しい候補リストにして０に戻る
0029 %
0030 % Copyright (C) 2011, ATR All Rights Reserved.
0031 % License : New BSD License(see VBMEG_LICENSE.txt)
0032 
0033 if nargin<3, seedID=1; end;
0034 
0035 Npoint = size(V,1);      % 頂点数
0036 Npatch = size(F,1);      % 三角面数
0037 
0038 Plist = zeros(Npoint,2);    % 候補 周辺頂点リスト
0039 Vlist = zeros(Npoint,2);    % 向き確定 周辺頂点リスト
0040 Vflg  = zeros(Npoint,1);    % 頂点処理済みフラグ
0041 Fflg  = zeros(Npatch,1);    % 三角面処理済みフラグ
0042 FF      = zeros(Npatch,3);    % 三角面インデックス
0043 
0044 % 隣接点インデックスリストの作成
0045 xxF  = vb_neighbor_index(V,F);
0046 
0047 % ルートインデックス
0048 Plist(1,:) = [seedID, xxF{seedID}(1,1)];
0049 
0050 Nlist =1;% 候補 周辺頂点数
0051 Nroot =0;% 処理済み頂点数
0052 
0053 while Nlist > 0,
0054 
0055     Nedge = 0;% 向き確定 周辺頂点数
0056     
0057     % 周辺頂点に関するループ
0058     for n=1:Nlist,
0059         % root インデックスと next インデックスの更新
0060         root = Plist(n,1);
0061         next = Plist(n,2);
0062         
0063         % root の隣接点インデックスリスト
0064         nextID = xxF{root};     
0065         
0066         % 隣接点リスト
0067         nlist1 = nextID(:,1);     % 隣接点リスト1
0068         nlist2 = nextID(:,2);     % 隣接点リスト2
0069         flist  = nextID(:,3);     % 隣接三角面リスト
0070         
0071         % 未処理の面インデックスを探す
0072         nextix = find( Fflg(flist) == 0 );
0073         
0074         if isempty(nextix), 
0075             continue;
0076         end;
0077         
0078         % 未処理面のインデックスリスト
0079         nlist1 = nlist1(nextix);
0080         nlist2 = nlist2(nextix);
0081         flist  = flist(nextix);
0082         
0083         Nnext  = length(nextix);
0084         Nnew   = Nnext;
0085     
0086         % root に隣接する未処理面ループ
0087         for i=1:Nnext, 
0088             % nlist1/2 の中で、前回の隣接頂点 next を含む面の探索
0089             jx1  = find( nlist1==next );
0090             jx2  = find( nlist2==next );
0091             
0092             if ~isempty(jx1),
0093                    nold  = next;
0094                 jj      = jx1(1);        % next を含む面のリスト内番号
0095                 fid   = flist(jj);  % next を含む面の面番号
0096                 next  = nlist2(jj); % この面のもう一つの三角面頂点
0097 
0098                 % 向き確定 周辺頂点リストに追加
0099                 Nedge = Nedge + 1;
0100                 Vlist(Nedge,:) = [next nold];
0101                 % 三角面頂点インデックスの入れ替え
0102                 FF(fid,:) = [root, nold, next];
0103                 % この面を処理済みリストに入れる
0104                 Fflg(fid) = 1;
0105                 % この頂点を処理済みにする
0106                 Vflg([root, nold, next]) = 1;
0107                 
0108                 % この面を隣接面リストから削除
0109                 inew   = [1:(jj-1),(jj+1):Nnew];
0110                 flist  = flist(inew);
0111                 nlist1 = nlist1(inew);
0112                 nlist2 = nlist2(inew);
0113                 Nnew   = Nnew-1;
0114             elseif ~isempty(jx2),
0115                    nold  = next;
0116                 jj      = jx2(1);        % next を含む面のリスト内番号
0117                 fid   = flist(jj);  % next を含む面の面番号
0118                 next  = nlist1(jj); % この面のもう一つの三角面頂点
0119 
0120                 % 向き確定 周辺頂点リストに追加
0121                 Nedge = Nedge + 1;
0122                 Vlist(Nedge,:) = [next nold];
0123                 % 三角面頂点インデックスの入れ替え
0124                 FF(fid,:) = [root, nold, next];
0125                 % この面を処理済みリストに入れる
0126                 Fflg(fid) = 1;
0127                 % この頂点を処理済みにする
0128                 Vflg([root, nold, next]) = 1;
0129                 
0130                 % この面を隣接面リストから削除
0131                 inew   = [1:(jj-1),(jj+1):Nnew];
0132                 flist  = flist(inew);
0133                 nlist1 = nlist1(inew);
0134                 nlist2 = nlist2(inew);
0135                 Nnew   = Nnew-1;
0136             end;
0137         end
0138         % END- (root) に隣接する未処理面ループ
0139         
0140     end;
0141     % END-周辺頂点に関するループ
0142     
0143     % 候補 周辺頂点リストの更新
0144     Nlist = Nedge;
0145     Plist(1:Nedge,:) = Vlist(1:Nedge,:);
0146 
0147 end
0148 
0149 % 処理済みの頂点と三角面を取り出す
0150 indx = find(Vflg == 1);
0151 inxf = find(Fflg == 1);
0152 FF     = FF(inxf,:);
0153 
0154 [Vnew, Fnew] = vb_trans_index( V, FF, indx);
0155 [xxn , Fnew] = vb_out_normal_vect(Vnew,Fnew);
0156 
0157 %fprintf('New version\n')
0158 
0159 if nargout <= 3, return; end;
0160 
0161 % 未処理の頂点と三角面を取り出す
0162 vmiss = find(Vflg == 0);
0163 
0164 [Vmiss, Fmiss] = vb_trans_index(V,F,vmiss);
0165 
0166 return
0167