3 次元画像コンファレンス 2014 講演論文集, P-14, (2014.7.11)

スイッチバック法を用いたポリゴン単位隠面消去処理の性能とその改良
Performance of polygon-by-polygon hidden surface removalusing the switch-back technique and its improvement
増田幸勇 1

松島恭治 1

中原住雄 2

Sachio Masuda1

Kyoji Matsushima1

Sumio Nakahara2

1

関西大学 システム理工学部 電気電子情報工学科

1

Department of Electrical and Electronic Engineering, Kansai University
2

関西大学 システム理工学部 機械工学科

2

Department of Mechanical Engineering, Kansai UniversityABSTRACT
In high-definition computer holography, the silhouette method plays an important role to shield light behind objects and prevent theobjects from being reconstructed as see-through images. The light-shielding had been done for the whole object in the conventional
technique to reduce computation time. However, this type of silhouette method is not valid for self-occluded objects; occlusion errors
commonly occur. Definitely, polygon-by-polygon (P-P) silhouette light shielding is more effective than conventional
object-by-object (O-O) shielding. However, P-P shielding is very time-consuming because the conventional P-P shielding requires
the same number of whole-field propagation as the obstacles, i.e. the polygons in this case. In order to solve the problem, a newtechnique called the switch-back technique has been proposed for reducing the computation time. This research reports theperformance of the switch-back technique, especially in cases where an object is divided into sub-objects.

Keywords: computer holography, computer-generated hologram, hidden-surface removal, silhouette method

1. はじめに伝搬計算処理が必要であるため，ポリゴン単位の処理では我々が近年報告しているレーザーリソグラフィ技術と計算時間が長大化する問題があった．その問題を解決するポリゴン法[1]に基づく高解像度計算機合成ホログラムために，ポリゴン単位シルエット法を高速に処理できるス(Computer-Generated Hologram：CGH)では古典的なホログ

イッチバック法と呼ぶ手法が提案されており[6]，この手ラムに匹敵するほどの美しい空間像が再生できる[2, 3]．

法では物体を分割することにより計算時間が短縮できる

このような高解像度コンピュータホログラフィの特徴は，と考えられる[7]．そこで本研究では，複数の物体モデルステレオグラムと違って深い奥行感が得られることであで物体を分割した場合について，スイッチバック法とポリり，オクルージョンが生じるシーンにおいて連続的な運動

ゴン法を用いた物体光波計算時間の短縮の効果を測定し，視差が再生されることがこれに寄与していると考えられその計算量から推定される最適な分割数について報告す

る．

る．

この様なオクルージョンを再生するためには，後方から2. スイッチバック法の光波が前方の物体に透けないようにする光波遮蔽処理

スイッチバック法は，従来のシルエット法で用いられるが不可欠であり，我々の高解像度 CGH では，シルエット2 値シルエットマスクを逆転したシルエット開口を用い法[4, 5]を用いて物体単位で遮蔽を行ってきた[2]．しかし，る手法である．ポリゴン単位遮蔽の場合，ポリゴンのシルモデルに自己オクルージョンがある場合には，物体単位でエット面積は全光波に比べて極めて小さく，シルエット開は完全な遮蔽はできず，ポリゴン単位での遮蔽処理が必要となる．
しかしながら，シルエット法ではマスクの数だけ光波の口による遮蔽では開口部分の光波のみが必要であるため，伝搬計算に必要なサンプリング数を大きく削減できる．マ
スクの代わりに開口を用いても，バビネの原理により従来のシルエット法と等価な処理が行えることが示されてい増田幸勇<masuda@laser.ee.kansai-u.ac.jp>
関西大学システム理工学部電気電子情報工学科〒564-8680 大阪府吹田市山手町3-3-35
TEL 06-6368-1121(内線 5722)

る[6]．
本研究で用いた座標系とスイッチバック法の手順をFig.1 に示す．いま，物体近傍にホログラムと平行な平面を設定する．これを物体平面 V と呼び，この物体平面上

3 次元画像コンファレンス 2014 講演論文集, P-14, (2014.7.11)

An ( x, y )ApertureAn ( x, y )V u obj ( x, y )VnPolygon field
Dn ( x, y )u n ( x, y )サブモデルの物体光波を求める．この物体光波を物体平面V1 上に全光波伝搬し，これをサブモデル O1 の背景光波として再び O1 についてスイッチバック法を行う．以下，順Polygon nPˆ n ,obj

モデル O0 でスイッチバック法を用いて物体平面 V0 上での次これを繰り返す．これにより，物体平面とポリゴン間のPˆ obj,n

平均距離が短くなるため，計算時間の削減が可能となる．
しかし，物体の分割数を増やすとサブモデル間の全光波伝zn(a)zobjznzobj(b)

Fig. 1 The procedure for the single step of the switch-backtechnique.

搬計算の回数も増加するため，一概に増やせばいいわけはなく，最適な物体分割数は物体モデルの形状に強く依存していると言える．

3.2

前節で述べたように最適な物体分割数は対象の物体モで物体光波を求める．物体が N 個のポリゴンから成り，ポリゴンが物体空間の奥から順に n  0,物体分割した場合の計算量, N  1 としてデルの形状に強く依存すると考えられる．そこで，本研究番号付けされているとすると，スイッチバック法による光では理論的に計算量を求めることで最適な分割数の決定

波遮蔽の 1 ステップは次の連立漸化式で記述される[8]．

を試みた．

ˆ u ( x, y)
un ( x, y)  P(1)n ,objobj
obj
ˆun 1 ( x, y)  un ( x, y)  Pobj, n Dn ( x, y)  An ( x, y)un ( x, y )サンプリング数が M の高速フーリエ変換の計算量は，obj
n

(2)
objn

ここで，(1)式は Fig.1(a)に対応しており，u ( x, y) は光波遮蔽した上で得られる 0～nまでのポリゴンの物体平面

ˆ
上での物体光波を表している．記法 Pn ,obj un ( x, y ) は，obj

その物体光波のうちポリゴン n による遮蔽の影響を受ける部分のみをポリゴンが存在する奥行き位置 zn の平面に逆伝搬する演算処理を表しており，これがポリゴン n の背よく知られているようにFFT(M )  M log2 M で表される．
畳込み積分を用いた伝搬計算では 2 回の FFTと周波数領域における乗算処理からなるが，今回は FFTのみの計算量の検討を行う．物体分割を行なった場合の計算量 Call はCall  Csw  C prop 

面より入射する光波 un ( x, y) となる．(2)式は Fig.1(b)に対と表すことができる．ここで Csw は各サブモデルにおける応しており， Dn ( x, y) は zn での平面上で与えられるポリスイッチバック法による隠面消去処理を行った物体光波

ゴン光波， An ( x, y)  1  M n ( x, y) は従来のシルエットマ

Object planeV

スク関数 M n ( x, y) を逆転した開口関数である．(2)式では，

y

入射光波を開口で遮蔽し，ポリゴン光波から減算し，物体平面へ順方向伝搬させてそれまでの物体光波に加算して

ˆいる．P
obj, n は zn の位置の光波を物体平面 V へ伝搬させる

Polygon model

P1演算を表している．

x

この手法では，物体自体の背景光波が無い場合はポリゴン数 N に対して伝搬計算回数は 2 N  1 回，背面光波があP0
Diffraction areaる場合は 2N 回となる．単純なシルエット法における伝搬計算は N 回であり計算回数自体は増えているが，スイッ(a)搬計算の計算時間は極めて短くなる．

3. 物体モデルの分割とその計算量の推定
3.1 物体モデルの分割
以上で述べたようにスイッチバック法は従来のシルエ

V0

Sub objectO0が少ないことである．しかしながら物体平面がポリゴンよObject plane
V1V2

O1
P1O2V3

そのため Fig.2(a)に示すように，物体平面を物体モデルのyO3x

り遠いと，物体平面上でのポリゴン光波が回折により広がってしまうため必要なサンプリング数が増加してしまう．

Hologram

Propagation

チバック法では全光波の一部のみを伝搬計算するため伝ット法と比べた利点は伝搬計算に必要なサンプリング数zz

P0
Diffraction area

中央付近に配置することで平均伝搬距離を減少させ，計算Hologram量を削減している．
しかしながら，物体モデルが奥行方向に長い場合は計算量の増加を避けられない．そのため，(b)に示すように物体を分割し複数の物体平面を設定する．まず一番奥のサブPropagation(b)
Fig. 2. The principle of speedup of computation bysplitting an object.

3 次元画像コンファレンス 2014 講演論文集, P-14, (2014.7.11)
計算の計算量であり，C prop はサブモデル間の並進伝搬計算の計算量であり，これは光波分布全体の伝搬計算である
ため，

C prop  2FFT(M )  ( Ndiv  1) と表せる．ここで M は光波分布全体のサンプリング数で，Ndiv は物体分割数である．今回の測定では物体後方の背景光波の設定をしていないが，背景光波を設定する場合はその背景光波がサンプリング窓の全域に広がる場合がある．
その場合はサブモデル間の伝搬計算においてエイリアシングを避けるため，サンプリング数を 4 倍に拡張する必要がある．そのため，その場合は(5)式において M が 4M となる．
Csw の計算量を推定するためのモデルを Fig.3 に示す．
(a)に示すように各サブモデルにおけるポリゴンと物体平面間の平均的距離は，モデルに外接する直方体の各軸方向の大きさを Wx Wy Wz とすると，d

1 Wz
4 N div



用いてスイッチバック法における光波伝搬の際の平均サンプリング数 N ave を関数

Nave   ( Pave , d ,  ) で表す．この関数は，ポリゴン Pave から距離 d 離れたホログラムと平行な平面上における光波の最大回折範囲，およびその平面上での光波のサンプリング間隔から，その最大回折範囲に含まれるサンプリング数を与えるもので

V0Fig.4 に示すように，その物体モデルに含まれるポリゴンの平均外接直方体の奥行き方向の中心に位置する二等辺三角形を Pave と設定した．
以上により，スイッチバック法における計算量 Csw は，順方向と逆方向の 2 回の伝搬計算とポリゴン光波の計算に必要な計算量として

Csw  6FFT( Nave )  N 

Object plane
V1
VNdiv-1Vnと表せる．ここで N は可視ポリゴンの総数である．

4. 計算時間の測定
Fig.5 に示す各モデルを用い，物体分割数を変えて物体光波を計算し，その計算時間を測定した．これらのモデルは Fig.6 に示す 3D シーンに配置している．この時，どのモデルについてもモデルの横幅，すなわちモデルの外接直っている．これらのモデルのパラメータを Table.1 に示す．
一方，光波はサンプリング数 65,536  65,536，サンプリング
間隔 0.8m としている．計測に用いたハードウェア環境は
CPU が Xeon X5680 (3.33GHz)×2 であり，物理コアの総数は12 である．またメインメモリとして 288G bytes を搭載している．
FFT のライブラリパッケージとしては Intel MKL 10.0 を用い，計測プログラムは Microsoft Visual Studio 2008 を用いてコンパイルしている．
物体分割数を変化したときの計算時間の計測結果を Fig.7に示す．またそれぞれのモデルにおける計算量 Call を Fig.8 に

Average bounding box

PolygonmodelWz
N divWz

方体の横幅が 40 mm になるように大きさの規格化を行なとなる．次に，簡単化のため，対象物体の全ポリゴンの外接直方体の大きさの平均値を求め，そのような平均外接直方体に収まる典型的なポリゴンを Pave で表した．これをある．ここで FFT を用いることを考慮して，求まったサンプリング数は最小の 2 のべき乗に丸めている．なお，ポリゴン光波の最大回折範囲は，文献[2]の方法により容易に推定することができる．
簡単化のため， Pave はホログラムと平行であるとし，

yx

Pn
dO0O1

On

ONdiv-1

Hologram
Average width(a)zo

40[mm]

Averagedepth

Averageheight90 [mm](b)Fig. 4.

Fig. 3. Estimation of the computational
complexity in the case of object splitting.

Fig. 6. The 3D scene used forperformance measurements.

Definition of theaverage polygon (Pave).
yyyyyxxxxx

Model 1496 Polygons

zzzModel 2Model 3Model 45000 Polygons

18536 Polygons

7986 Polygons

Fig. 5.

Models used for performance measurements.

zModel 5z

13218 Polygons

3 次元画像コンファレンス 2014 講演論文集, P-14, (2014.7.11)

参考文献

示す．
以上の結果よりポリゴン数が多く複雑な形状を持つモデル[1]や奥行き方向に大きなモデルにおいてもモデルを 10 程度以上に分割すると計算時間はほぼ一定になることが分かった．

[2]

また，分割数を必要以上に増やした場合の計算時間の増加もほとんどないことがわかった．なお，どのモデルにおいても概[3]ね 2～4 時間程度で計算が可能であった．

5. まとめ[4]

本研究では，スイッチバック法において奥行方向に物体を分割することにより計算時間を短縮できることを示した．この時，分割数には最適値があると考えられるが，計[5]測および計算量の計算結果から，ある程度以上に分割すれば良く，分割数の最適値はそれほど重要でないことがわか[6]った．ただし，これは物体に背景光波が無いことを想定した場合であり，それがある場合には，サンプリング数の 4[7]倍拡張により異なった結果になる可能性がある．

謝辞
本研究は，日本学術振興会の科研費(24500133)，および[8]文部科学省私立大学戦略基盤研究形成支援事業(平成 25K. Matsushima, “Computer-Generated Holograms forThree-Dimensional Surface Objects with Shade and Texture,”
Appl. Opt. 44, 4607-4614(2005).
K. Matsushima, and S. Nakahara, “Extremely High-Definition
Full-Parallax Computer-Generated Hologram Created by the
Polygon-Based Method,” Appl. Opt. 48, H54-H63 (2009).
K. Matsushima, and S. Nakahara, “Stepping closer to the perfect
3D digital image,” SPIE Newsroom, (6 Nov. 2012).
DOI:10.1117/2.1201210.004526.
K. Matsushima, and A. Kondoh, “A Wave Optical Algorithm for
Hidden-Surface Removal in Digitally Synthetic Full-Parallax
Holograms for Three-Dimensional Objects,” SPIE Proc. 5290,
90-97(2004).
近藤暁靖, 松島恭治, “シルエット近似を用いた全方向視差
CGH の 隠 面 消 去 ,” 電 子 情 報 通 信 学 会 論 文 誌 J87-D-II,(2004).
中村将樹, 松島恭治, 中原住雄, “全方向視差 CGH におけるポリゴン単位の高速隠面消去法,” 3 次元画像コンファレン
ス 2011, 66-69(2011).
K. Matsushima, S. Nakahara, et al. “Recent Techniques forHidden Surface Removal in Computer Holography,” The 3rd
Korea-Japan Workshop on Digital Holography and Information
Photonics (DHIP2013), Daejeon, (2013).
K. Matsushima, M. Nakamura, S. Nakahara: “Silhouette methods
for hidden-surface removal in computer holography and itsacceleration by switch-back technique” (to be published)．

年～平成 29 年)の助成を受けたものである．

Table 1. Parameters of object models.
Number ofpolygons

Number ofvisible polygons

Sizes of bounding box of object
model ()

Sizes of average polygon(Pave) ()Model1

97849640.0  27.3  33.5 mm333.469  2.006 mm2Model25000

2500

40.0  26.2  39.2 mm3

1.033  0.950 mm2

Model3

18536

9373

40.0  17.7  31.8 mm30.554  0.444 mm2Model47986

4008

40.0  25.0  59.7 mm30.824  0.870 mm2

Model513218

6757

40.0  39.1  40.8 mm30.784  0.648 mm2Model 3

Computation time [h]14Model 41210

Model 58Model 2
Model 164200246810121416

Computational complexity (Call) [a.u.]

NameModel 4

Model 3Model 5Model 2Model 1

02

Number of sub-objects
Fig. 7.

Measured computation time.

468101214

Number of sub-objects
Fig. 8.

Estimated computational complexity.

16