論文

点で表現された曲面の穴埋めのための効率的なアップサンプリング法
金

森

由

博†

高

橋

成

雄††

西 田 友 是††（正会員）† 東京大学大学院情報理工学系研究科†† 東京大学大学院新領域創成科学研究科〈あらまし〉 点集合による形状表現は, 従来の多角形メッシュと異なり, 点同士の接続情報を用いずに大規模な 3 次元形状データを扱うことができるため, CG の分野において非常に有望とされている表
現方法のひとつである. 点集合で表現された形状を描画するためには, 通常サーフェルと呼ばれる円盤が広く用いられているが, サンプリング密度が不十分な領域では穴が生じてしまう.
これを解決するため, 本論文ではサーフェルを用いて曲面を表現する際に穴が生じないよう, アップ
サンプリングを行う手法を提案する. 穴を埋めるために, 提案法は各サーフェルの周囲の隙間を検出
し, サーフェルを追加して隙間を埋める. 提案法はサーフェルの重なりとユーザが指定したサーフェルの半径を考慮することによって, 追加するサーフェルの数を少なく抑える. 実験により, 提案法が多重解像度 (level-of-detail) の制御や対話的なモデリングなどに広く応用できることを示す.
キーワード：点群処理, 穴埋め, アップサンプリング〈Summary〉 Point-sampled geometry has become one of the most promising representations

in computer graphics because, unlike conventional polygonal meshes, it can manage large-scale
3D data without accounting for the point connectivity. The common rendering technique forpoint-sampled geometry is to introduce a set of oriented disks called surfels, however, it still
suﬀers from unexpected holes on insuﬃciently sampled regions.
This paper presents a novel up-sampling method for ﬁlling such holes on the surfaces consisting of surfels. For ﬁlling the holes, the present method extracts gaps around each surfel
and inserts new surfels to ﬁll the gaps. This requires a small number of surfels in our framework by taking into account their overlaps together with the user-speciﬁed radii of surfels.
Several experiments have been conducted to demonstrate that the present method has wide
applications such as level-of-detail control and interactive editing of point-sampled geometry.
Key words: point-sampled geometry, hole-ﬁlling, up-sampling

1.

はじめに

て有望視されている. 点集合で表現された形状を描画するためには, 通常「サーフェル」と呼ばれる円盤が広く点集合による形状表現は, 従来の多角形メッシュによ用いられている6). しかし, 点のサンプリング密度が不十る表現と違い, 頂点間の接続情報を用いずに 3 次元形状分な領域では穴が生じてしまう. このような穴を埋めるを扱えるため, 大規模なデータの効率的な表現方法としために点を増やす手法が多く提案されている. 代表的なものとして Voronoı̈図を用いた手法1), メッシュの細分割“An Eﬃcient Up-Sampling Method for Filling Holeson Point-sampled Surfaces” by Yoshihiro KANAMORI,(Graduate School of Information Science and Technol-を応用した手法3)があるが, 穴を覆うために比較的多くのサーフェルを必要としてしまう.

ogy, the University of Tokyo), Shigeo TAKAHASHI, and

本稿では，既存手法より少ないサーフェルで穴埋めをTomoyuki NISHITA, (Member), (Graduate School of Fron-

行うアルゴリズムを提案する．提案法は各サーフェルのtier Sciences, the University of Tokyo).

1108

論文：点で表現された曲面の穴埋めのための効率的なアップサンプリング法
周囲を検査することで自動的に穴の検出・サーフェルのフェルで表現された形状データを入力とし, 穴埋めを行追加を行う．サーフェルの半径は一定あるいは曲率に応う. 出力されるデータは, ユーザが予め指定したサーフェ

じて可変にする (曲がった箇所は比較的密に，平らな箇

ルの半径で穴が生じないことが保証されている，アップ

所は比較的疎にする) ことができ，サーフェルの分布を

サンプリングされた点群である．以下, 入力データおよ

局所的に一様に保つことができる．

び出力データのことを, それぞれ入力点集合および出力

2.

点集合と呼ぶことにする. 各サーフェルは真円の (短軸と関連手法

長軸の長さが等しい) 円盤であり, 面の向きを表す単位法

本節では, 点集合によって表現された形状のためのアッ線ベクトルと表面の色をもつものとする.
提案法は次の 3 ステップからなる (図 1 参照): 各サー

プサンプリング法について, 関連手法を述べる.
9)

Stamminger ら はパラメータ空間でアダプティブに曲面をサンプリングする手法を提案した. 彼らの手法は描画時に十分なだけのサンプルが得られるまで単純な規則で各点の周りに点を追加するというもので, 穴の検出はできない. Alexa ら1)は, 局所的に最小二乗法で当てはめた平面へ点を投影し, 最大空円問題5)を反復的に解くことでアップサンプリングを行った. しかし, 彼らはサーフェル i について,

1. サーフェル i の近傍のサーフェルを, サーフェル i の中心を通る接平面に投影

2. サーフェル i の周囲の穴を検出し, 新しいサーフェルを追加して穴を埋める

3. 接平面で新しく追加したサーフェルを, 近傍の点群が表現する曲面に逆投影

フェルの重なり具合を考慮しておらず, 曲面を覆うため

この穴埋め手続きは, 各サーフェルの周囲の穴が近傍のに必要以上にサーフェルを追加してしまう.

サーフェルによって完全に覆われたとき終了する.

Guennebaud ら2)は細分割曲面の考えを応用し, 局所

3.2 穴の検出と穴埋め

的に点の隣接関係を構築して点を増やす手法を提案した.

提案法は, 穴の検出を簡便にするため, 注目するサー

これは点の分布が均一な場合にしか適用できなかったが,フェルによって定義される, 近傍の点群が表現する曲面

不均一な場合や大きな穴に対応するため, 隣接関係の構の接平面を用いる. 以下では, まず 2 次元の場合におけ築や点の追加の方法に改良がなされた3). しかし, 改良さるアップサンプリングのアルゴリズムを述べ, 続いてそれた手法ではサーフェルの重なりが非常に大きく, 大きれを 3 次元の場合に拡張する.

な穴を自動的に検出することができない. さらに, いずれ

3.2.1 基本的な考え (2 次元の場合)の手法でも細分割曲面同様, 点数は整数倍ずつしか増や提案するアップサンプリングアルゴリズムは, 「穴のすことができないため, サンプリング密度の調整は柔軟

検出」および「穴埋め」の 2 つの手続きからなる. 穴のでない.

検出手続きは, 各サーフェルの周囲の穴を検出し, 新しい

多くのアップサンプリング手法では, サンプリング密

サーフェルが必要かどうかを決定する. そして穴埋め手度を制御するために大域的最適化が用いられる. 代表的続きは, 新しいサーフェルを配置して穴を埋める. 過剰8),10)が挙げにサーフェルを追加せず, サーフェルの分布を均一にすられる. これは各点に対して粒子間力を定義し, 平衡状態

るため, 提案手法では穴の検出時には穴を正確に検出し,になるまで反復計算して点の分布を均一にするというも穴埋め時にはサーフェルの重なりを減らし, 近傍のサーのである. しかしパーティクルシミュレーションは計算

フェルの分布を均一に保つようにしている.

なものとしてパーティクルシミュレーション

的に安定でなく, 計算コストが非常に高いため大規模なデータには向かない.
提案法はサーフェルの半径を考慮し, サーフェルの重仮定 :2 次元の平面上に N 個のサーフェルが不均一に分布しているとする. 各サーフェル i(0 ≤ i < N ) の中なりをできるだけ小さく抑え, 点の局所的な分布を均一

心は pi , 半径は ri (rmin ≤ ri ≤ rmax ) とする. もし 2に保つ. サンプリング密度はサーフェルの半径を指定す

つのサーフェルが完全に一致する場合は, 冗長なので一ることで柔軟に制御することができる.

3. 穴の検出と穴埋め方を除去する. サーフェルの半径は急激には変化しないものとする.

3.1 提案法の概要

穴の検出 :

本稿において「穴」とは表面形状でサーフェルに覆わ

サーフェル i の境界が近傍のサーフェルによって覆われてれていない領域のことと定義する. 入力となる表面形状

いるかを検査する. サーフェル i とサーフェル i とが交は閉じており, 元々穴がないと仮定する. 提案法は, サー差するとき, すなわち |ri − ri | < pi − pi  < ri + ri

各サーフェル i の周囲の穴を検出するため,

1109

画像電子学会誌

第 36 巻

Step 1

第 6 号（2007）

Step 2

Step 3

図 1 提案法の概要. Step 1: 各サーフェル (青) を接平面に投影, Step 2: 接平面上で穴を検出し, 埋める, Step 3: 新しく追加したサーフェル (ピンク) を点群が表現する曲面に逆投影する. 説明のため, 図では曲面と接平面は離して描いている.
Fig. 1 Overview of the present method. Step 1: project existing surfels (inblue) onto a tangent plane, Step 2: detect and ﬁll gaps on a tangent
plane, Step 3: backproject new surfels (in pink) onto the point-sampled
surface. The tangent plane is separated from the point-sampled surface
for an illustrative purpose.

(a) 穴なし (ω ≤ 0)

図2
Fig. 2(b) 穴あり (ω > 0)
Fig. 3穴の検出.
Hole-detection.

となるとき, サーフェル i の境界はサーフェル i によって部分的に覆われる. それゆえ, 穴の検出手続きではサーフェル i と交差する近傍サーフェル (K 個とする) を探索する. サーフェル j(0 ≤ j ≤ K, 中心は qj , ただし

q0 = qK とする) を, 交差するサーフェルのひとつとす
る. 各サーフェル j は反時計回りにソートしておく.
サーフェル i の周囲の穴は次のようにして検出する.
サーフェル i と j の境界の交点を, pi を中心として反時
計回りに dj および ej とする. サーフェル i, j, j+1 の間の穴を検出するため, 角度 ω =  ej pi dj+1 (−2π < ω ≤ 2π)

図 3 穴の検出手続きの例外.
An exception of hole-detection.

て, 穴を覆うかどうかを検査する.
穴埋め :サーフェル i, j, j+1 の間に穴がある場合 (すなわち ω > 0), 穴埋め手続きによって新しいサーフェルを追加し穴を埋める. 追加されるサーフェルの半径はすべて等しいものとし, それを rnew とする. サーフェルの重なりを減らすため, 次の式で計算される角度 Δω を用いて, 等間隔に新しいサーフェルを追加することを考
える：


2
2
+ rnew rnew
+ 8ri 2
−rnew
(1)
2
4ri
ここで ri はサーフェル i の半径である. この値は図 4 にΔω = 2 arcsinを計算する (図 2 参照). もし ω ≤ 0 であれば, サーフェ

示すような条件を満たすよう選んだ: 仮に, サーフェル i

ル i, j, j +1 は互いに重なるので, それらの間に穴はなの近傍に他のサーフェルがなくサーフェルの半径が一定,

い (図 2(a)). もし ω > 0 であれば穴がある (図 2(b)).

すなわち, ω = 2π かつ rnew = ri とすると, Δω = π/3

サーフェル i の周囲に交差するサーフェルがない場合はとなり, 新しいサーフェルは中心点が六角形格子を成す

ω = 2π とする.

ように追加され, この場合の最適配置となる. 実験ではしかしながら, 上記の手続きだけでは実際には埋まっている穴を誤って検出する場合がある. 図 3 の例では,

rnew = ri である場合にも良好な結果が得られた.
穴の広がり角度 ω および Δω とを考慮して, 新しい

サーフェル j −1 が, サーフェル i, j, j +1 の間の穴を埋サーフェル k を追加する. このとき, すでに存在するサーめている. このため, サーフェル i, j, j+1 だけでなく近フェルを動かしてしまうと, そのサーフェルの周りに穴

傍の他のサーフェルが穴を覆うかどうかを調べる必要がが開く恐れがあり, 穴の検出処理が必要となる. これを避ある. 提案法ではサーフェルの半径が急激には変化しなけるため, すでに存在するサーフェルは動かさないもの

いと仮定して, サーフェル j −1 および j +2 のみについとし, 必要に応じて新しいサーフェルをずらす. この手続

1110

論文：点で表現された曲面の穴埋めのための効率的なアップサンプリング法
q j+1

q j+1
qk
pi

pi
qj

qj

(a) Δω < ω の場合.

図 4 Δω の導出. Δω はサーフェル k および k+1 の中心点が次の条件を満たすように決定される：qk+1 −mk  = qk −mk  = qk −nk .
Fig. 4 An illustration for Δω. Δω is determinedso that the centers of new surfels k and k +1 meet the condition: qk+1 − mk  = qk −mk  = qk −nk .

(b) 穴が小さく, 新しいサーフェルがある場合.

きは次のように行う：

ω > 0 の間, 以下を繰り返す：(c) 穴が小さいが, 新しいサーフェルがない場合.

ω > Δω の場合 (図 5a)：
新しいサーフェルを 1 つ仮に配置;ω ← ω−Δω として処理を繰り返す;
ω ≤ Δω の場合：
穴の両側のサーフェルが交差する (穴が小さい) 場合(d) 上記以外の場合.

新しいサーフェルがある場合 (図 5b)：
新しいサーフェルをずらして穴埋め終了;

Fig. 5図 5 穴埋め規則.
The hole-ﬁlling rules.

新しいサーフェルがない場合 (図 5c)：

3 つのサーフェルの中心点からなる三角形の垂心にサーフェルを追加して終了;
それ以外の場合 (図 5d)：
ちょうど穴が埋まるように
新しいサーフェルを 1 つ追加して終了;
上記の手続きでは, 近傍の他のサーフェルを考慮していない. サーフェル k の中心点が, すでに存在するサーフェ
ル l の半径内に入ってしまう, すなわち qk −pl  < rlとなる場合がある (図 6). ここで pl および rl はそれぞれ, サーフェル l の中心点および半径である. このように

2 つのサーフェルが近づきすぎることを許すと, 全体として穴埋めに必要なサーフェルの個数が増えてしまう傾向がある. そこで, 新しいサーフェル k を線分 qk pi に沿っ

図 6 穴埋め規則の修正. サーフェル k の中心点 qk が近傍サーフェルの内側に入ってしまう場合, qk を線分
qk pi に沿って qk −pi /qk −pl  = ri /rl となる位置までずらす.
Fig. 6 The modiﬁcation rule for hole-ﬁlling. If qk ,the center of the new surfel k, is placed inside another existing neighbor, qk is displaced along the segment qk pi so that qk −pi /qk − pl  = ri /rl in order to keep the
local sample distribution uniform.

て, 次の条件を満たす位置までずらす：
qk −pi  ri
= .
(2)
qk −pl  rl
このようにしてずらせば, ずらすことによって pi の周り

しかし一般に, 半時計周りに移動させるとまた別のサーに新たな穴ができることはない. この処理で中心点 qk がフェルと近づきすぎる場合があるため, 提案法ではこのサーフェル i の内側に入ってしまった場合, サーフェル iような単純な処理に留めた.

の境界まで qk を再度ずらす. なお図 6 の場合では, サー

この処理によって, 次に追加されるサーフェル k+1 のフェル k を点 pi に関してさらに半時計周りに移動させ位置もずれる. すなわち, サーフェル k+1 はサーフェル

た方がサーフェル i の境界をより広く覆うことができる.

i, k と 1 点で交わるように配置される.
1111

画像電子学会誌
既存手法との比較 :第 36 巻図 7 に, 提案法と Alexa らの手法1)との比較を示す. 彼らの手法では半径を制御する方法が第 6 号（2007）

しく rnew と r  との比が閾値を超える場合, 提案法ではrnew を r  で置き換え, 穴埋めを再度行う.

提示されていないため, 半径は一定として実験した. 特に

4. 実 験 結 果

入力が疎な場合に, 提案法は Alexa らの手法に比べ, より少ないサーフェルで領域を埋め尽くせることがわかる.

3.2.2

C++および OpenGL を用いて実装を行った. 以下の実験は, Pentium D 3.0GHz, 2GB RAM, nVIDIA

3 次元への拡張

上記の手続きを 3 次元の場合に拡張する. 各サーフェ

GeForce 7800 GTX 搭載の PC 上で行った. また, MLS

ルの半径が物体形状に比べ十分小さいと仮定すると, 点の計算のため入力点集合には kd-tree, 穴の検出・穴埋め

でサンプリングされた曲面 S は, 局所的に点 pi を通るのため出力点集合には grid を用いて, それぞれ近傍探索

S の接平面 Ti で近似できる. 提案法では, サーフェル i

を高速化した.

の近傍のサーフェルを接平面 Ti に投影することで, 2 次

図 8 に, Guennebaud らの手法,3)Alexa らの手法1),

元の場合の手続きを用いて接平面 Ti 上で穴の検出およ

提案法のそれぞれを用いて穴埋めを行った結果を示す.

び穴埋めを行う. 投影されたサーフェル j の形は楕円とGuennebaud らの手法では, 穴埋めを行う場合, サーフェなるが, 計算の簡便のため, 穴埋め手続きではこれを半径ルの半径を事前に穴を十分覆うように設定し, 細分割を

max(0, nj · ni ) rj の真円として扱う. ここで ni と nj

繰り返す必要がある. このため, われわれの実験では初期はそれぞれ, サーフェル i, j の単位法線ベクトルである.

点集合は疎なものを用いた. Alexa らの手法および提案

3 次元の穴埋め処理は次のように行う：各サーフェル法について, サーフェルの半径は一定として比較した. 半

i について, その近傍サーフェルを pi における接平面に径の長さは, 各形状のバウンディングボックスの対角線の投影する. そして接平面上で 2 次元の穴の検出および穴長さを 1 とする. われわれの実験で用いた Guennebaud

埋め手続きを行う. 最後に, 新しく追加したサーフェルをらおよび Alexa らの手法の実装はともに最適化されてい曲面 S に逆投影する. 曲面 S は滑らかで閉じていると仮ないが, 参考のために穴埋めにかかった計算時間を付記定しているので, この手続きを繰り返せば穴埋めが完了

している.
比較的違いが見やすい sphere の例について,する.
曲面への逆投影の計算 :接平面から曲面 S への逆投

影のために, 提案法では移動最小二乗法 (moving leastsquares; 以下 MLS) 4)を用いる. 点でサンプリングされ• Phong シェーディングして描画した結果• 環境マッピングによって直線を映した結果 (穴埋めされた曲面の品質を評価するため)

7)

た曲面 S を, Shen らの手法 と同様に, 2 次曲面で局所的に補間あるいは近似する. いずれの場合も, MLS によって計算される曲面は入力点集合によって定義される曲面であるため, 入力点集合と出力点集合とは別に扱う.

• サーフェルを一定倍率で縮小して描画した結果 (点の分布を示すため)をそれぞれ示した. Guennebaud らの手法の結果 (図 8(a)および (d)) では環境マッピングされた線が歪んでおり,

サーフェルの半径の決定 :

曲率に応じて半径を変える

凹凸があることを示している. 一方, Alexa らの手法

場合, 提案法はサーフェル i の半径を曲率に基づいて決(図 8(b) および (e)) および提案法 (図 8(c) および (f))

定する. 具体的には, 中心点 pi において計算した, 近似

では, サンプル数が増えるに従って滑らかな曲面が得ら

2 次曲面の主曲率の絶対値の最大値 κi , およびユーザ定√義の値 r を用いて次のように計算する: ri = r / κi .

サンプリングを行った場合に最も少ないサーフェル数に

ここで, サーフェル i の周囲に追加されるサーフェルの抑えられていることがわかる.

れている. いずれの例においても, 提案法によってアップ半径は, 各サーフェルの中心点での曲率から計算される

図 9 は, 曲率を考慮してサーフェルの半径を変え,ことになるが, 重なりを減らしつつ中心点の位置を決め

dragon モデルを再サンプリングした結果である. 主曲率

るには, 各サーフェルの半径が必要になる. そのため, 提を考慮して半径を変えることにより, 半径を一定にした案法は新しいサーフェルの半径 rnew を, 各サーフェルの場合に比べ, 視覚的差異を生じることなくサーフェルの中心点においてではなく, サーフェル i の中心点 pi にお数を大幅に削減できた.

いて計算する. これは曲率が滑らかに変化するという仮図 10 は, rabbit モデルに変形を施し, それによって生定に基づくものである. r  を新しいサーフェルの中心点

じた穴を提案法によって穴埋めした例である. 腰の部分において計算した半径のひとつとする. 曲率の変化が激に生じた穴が自動的に検出され, 穴埋めされている.

1112

論文：点で表現された曲面の穴埋めのための効率的なアップサンプリング法(a) Alexa らの手法

(b) 提案法(c) Alexa らの手法

(d) 提案法779 サーフェル

558 サーフェル

748 サーフェル

693 サーフェル

図 7 提案法と Alexa ら1)の手法との比較. 青は入力されたサーフェル, ピンクは新しく追加されたサーフェルを表す. (a) と (b) は入力が疎な場合 (26 サーフェル),(c) と (d) は入力が密な場合 (196 サーフェル).
Fig. 7Comparisons with Alexa et al.’s method1)and the present method. (a)and (b): sparse input (26 surfels), (c) and (d): dense input (196 surfels).

図 11 は提案法を用いて多重解像度のモデルを作成しの検出のために, 接平面ではなく曲面を考慮することがた例である. まず MLS 曲面によって近似した曲面に半挙げられる. 精密なモデルにおける鋭いエッジ部分の扱

径の大きなサーフェルを配置して穴埋めし, 半径を小さいも必要である.

くしてさらに穴埋めする, という手順を繰り返すことで,参考文献容易に多重解像度のモデルが生成できる. サーフェルを配列のようなデータ構造に逐次的に格納することにより,

1) M. Alexa, J. Behr, D. Cohen-Or, S. Fleishman, D. Levin,

粗いレベルのサーフェルはより細かいレベルを構成する

and C. T. Silva. Computing and rendering point set sur-のにも使われる. このようなデータ構造は描画時に動的な分岐を必要としないため, GPU での描画に適している.
さらに, 提案法では半径を柔軟に変更することができる
ため, モデルの解像度をスムーズに変化させることができる. ここでは, 粗いモデルのサーフェルの半径を半分に

faces. In IEEE Transactions on Visualization and Computer Graphics, pages 3–15, jan 2003.
2) G. Guennebaud, L. Barthe, and M. Paulin.

Dynamic

Surfel Set Reﬁnement for High Quality Rendering . In
Computer & Graphics , pages 827–838. Elsevier Science,
2004.
3) G. Guennebaud, L. Barthe, and M. Paulin. Interpolatory
reﬁnement for real-time processing of point-based geome-

していくことで多重解像度のモデルを作成した. 解像度

try. In Proceedings of EUROGRAPHICS 2005, pages 657–を制御するための最適な方法については今後検討したい.

666, August 2005.
4) D. Levin.

5.

ま と め

本稿では, サーフェルを用いて描画する際に穴が生じないよう, アップサンプリングを行う新手法を提案した.
提案法の特徴は以下の通りである:

Mesh-independent surface interpolation.

In

Geometric Modeling for Scientific Visualization, pages 37–
49, 2003.
5) A. Okabe, B. Boots, K. Sugihara, and S. N. Chiu. Spatial Tessellations: Concepts and Applications of Voronoi
Diagrams. Wiley, 1992.
6) H. Pﬁster, M. Zwicker, J. v. Baar, and M. Gross. Surfels:
Surface elements as rendering primitives. In Proceedingsof ACM SIGGRAPH 2000, pages 335–342, July 2000.

• 各サーフェルの周囲が近傍のサーフェルによって覆わ

7) C. Shen, J. F. O’Brien, and J. R. Shewchuk. Interpo-

れているかを検査することにより, 穴を検出できる.

lating and approximating implicit surfaces from polygon
soup.

• サーフェルの半径を指定することでサンプリング密度を調整できる.

• 穴を自動的に検出し, 埋めることができる.

In Proceedings of ACM SIGGRAPH 2004, pages

896–904, August 2004.
8) K. Shimada and D. C. Gossard. Bubble mesh: automatedtriangular meshing of non-manifold geometry by spherepacking. In SMA ’95: Proceedings of the third ACM symposium on Solid modeling and applications, pages 409–419,
1995.

• サーフェルの重なりをできるだけ小さくし, サーフェルの分布をできるだけ一様にする.

• 多重解像度データを生成できる.

9) M. Stamminger and G. Drettakis. Interactive sampling
and rendering for complex and procedural geometry. In
Rendering Techniques 2001: 12th Eurographics Workshop
on Rendering, pages 151–162, June 2001.
10) G. Turk.

Re-tiling polygonal surfaces.

In Computer

Graphics (Proceedings of SIGGRAPH 92), pages 55–64,

今後の課題として, 提案法は経験則に基づいており, より厳密な理論的裏付けが必要である. また, より正確な穴July 1992.

（2007 年 5 月 27 日受付）1113

画像電子学会誌
金森

由

第 36 巻博
2004 年，東京大学理学部卒．2006
年，同大大学院情報理工学系研究科
修士課程修了．現在，同大大学院情報理工学系研究科博士後期課程在学
中．コンピュータグラフィックスの研究に従事．情報処理学会会員．

高

橋

成

雄

1997 年東京大学理学系研究科情報科学専攻博士課程修了．博士 (理学)．
群馬大学工学部助手．同大学総合情報処理センター助教授，東京大学大学院総合文化研究科助教授を経て，現在，東京大学大学院新領域創成科学研究科複雑理工学専攻准教授．ビジュ
アリゼーション，視覚応用システム，
幾何形状モデリング，地理情報システ
ムなどに興味を持つ．電子情報通信学会和文論文誌 (A) 編集委員 IEEE
CS, ACM, Eurographics, 情報処
理学会，可視化情報学会，日本視覚学会各会員．

西

田

友

是 （正会員）1971 年，広島大学工学部卒業．1973年，同大学大学院工学研究科修了．同
年，マツダ (株) に入社．1979 年，
福山大学工学部講師．1984 年，同助教授．1990 年，同教授．1998 年,
東京大学理学部教授．1999 年，同大学大学院新領域創成科学研究科教授となり，現在に至る．2005 年，
ACM SIGGRAPH より Steven A.
Coons 賞を受賞．コンピュータグラ
フィックスの研究に従事．工学博士．
情報処理学会，電子情報通信学会，
画像電子学会，ACM，IEEE 各会員．

1114

第 6 号（2007）論文：点で表現された曲面の穴埋めのための効率的なアップサンプリング法

入力

Guennebaud らの手法3)

Alexa らの手法1)

提案法(a) 細分割 4 回, 平均半径 0.018(b) 半径 0.018(c) 半径 0.018

4,182 サーフェル, 0.74 秒

2,224 サーフェル, 0.41 秒

2,100 サーフェル, 0.09 秒

sphere154 サーフェル(d) 細分割 5 回, 平均半径 0.010(e) 半径 0.010(f) 半径 0.010

12,512 サーフェル, 2.00 秒

7,188 サーフェル, 0.97 秒

6,127 サーフェル, 0.27 秒

maxplanck(h) 細分割 5 回, 平均半径 0.0021(i) 半径 0.0021(j) 半径 0.0021

5,813 サーフェル

296,116 サーフェル, 68.50 秒

138,217 サーフェル, 21.31 秒

132,415 サーフェル, 7.25 秒

igea(k) 細分割 2 回, 平均半径 0.0012(l) 半径 0.0012(m) 半径 0.0012

134,344 サーフェル

1,057,633 サーフェル, 60.33 秒

446,328 サーフェル, 63.78 秒

419,779 サーフェル, 22.57 秒

Fig. 8図 8 既存手法との比較.
Comparisons with the previous methods.

1115

画像電子学会誌(a) 穴埋め前

第 36 巻

第 6 号（2007）(b) 穴埋め後(c) 半径一定での結果

図 9 曲率に応じて半径を変えて穴埋めした結果. サーフェルの数は (a)45,976(曲率が大きくなるにしたがって青から赤を変えている), (b)67,568, (c)116,390 となっている.
Fig. 9 Filling holes with surfel radii dependent on surface curvatures. The
numbers of surfels are (a) 45,976 (colored according to surface curvatures which increase from blue to red), (b) 67,568 and (c) 116,390.

(a) 元の形状(b) 変形後(c) 穴埋め後

図 10 変形された形状の穴埋め. サーフェル数は穴埋めによって 23,659 から 28,413に増加した.
Fig. 10 Hole-ﬁlling of a deformed object. The number of surfels increased
from 23,659 to 28,413.

(a) レベル 0 (半径=1)(b) レベル 1 (半径=0.5)(c) レベル 2 (半径=0.25)(d) レベル 3 (半径=0.12)

8,940 サーフェル

32,306 サーフェル

119,020 サーフェル

477,864 サーフェル

図 11 多重解像度の Stanford dragon モデル.
Fig. 11 The level-of-detail data for the Stanford dragon.

1116