読者です 読者をやめる 読者になる 読者になる

"Game & Design" セッション論文紹介 (SIGGRAPH '14)

SIGGRAPH 2014 CG 論文

2014年7月29日に私の所属する五十嵐研究室が主催の SIGGRAPH 勉強会があります。
SIGGRAPH 2014 Preview Seminar
この勉強会では各々が担当するセッションを事前に決めておき、当日10分程度で担当セッションの論文内容を発表し合います。1日で全ての論文を網羅するので中々ハードな勉強会です。(外部の方でももちろん参加歓迎です。興味のある方は連絡下さい。)

私は Game & Design のセッションを担当します。この記事では Game & Design セッションの論文の内容をまとめていこうと思います(発表資料を作る前段階のメモ、程度の位置づけですが)。勉強会当日まで随時更新していきます。

セッションについて

以下の5本の論文が含まれています(名称は自分が勝手につけた略称です)。

  1. Poisson-based Caustics Design (Yue et al.) (TOG)
  2. High-contrast Caustics Design (Schwartzburg et al.)
  3. Boxelization (Zhou et al.)
  4. Connect-the-Dots (Löffler et al.)
  5. Self-refining Game (Stanton et al.)

Games & Design | SIGGRAPH 2014

1. - 3. の3本は fabrication oriented design に関する論文です。近年流行ってる分野で、これら3本とは別に Fabrication Oriented Design というセッションがあったります。

これらのうち特に 1., 2. の2本は computational caustics design に関する論文で、同様の問題を扱っています。ただし 1. は TOG で Jun 2014 に先に公開されていたため、2. の中では 1. の内容を踏まえた議論(結果の比較など)が行われています。

1. Poisson-Based Caustics Design (TOG)

Yonghao Yue, Kei Iwasaki, Bing-Yu Chen, Yoshinori Dobashi, Tomoyuki Nishita
Poisson-based Continuous Surface Generation for Goal-based Caustics
ACM Transactions on Graphics (TOG) (2014)
http://nishitalab.org/user/egaku/tog14/absttog14.html

日本人による論文です。

概要の意訳

本論文はユーザが指定した集光現象 (caustics) のパターンを実現するような滑らかな表面形状を生成するための、Poisson ベースの手法を提案する。ファブリケートされた透明物体によって、滑らかで、自然で、非常に精細な caustics を得ることができる。

できるだけ短くまとめると

Goal-Based Caustics (または Computational Caustics Design) とは、ある目的の絵を入力として、集光現象を利用してその絵を描けるような透明物体の形状を出力とするような問題です。

このような問題に対して、今回の論文ではポアソン方程式を解くような定式化をする手法を提案しています。この手法は既存研究よりも高精度で滑らかな結果が得られるものとなっています。

Computational Caustic Design における一般的な問題設定

光源は並行光。
透明物体の光源側の表面は光軸に対して垂直な平面。
透明物体のスクリーン側の表面は滑らかな形状(これが出力)。
集光現象によってスクリーンに見える絵はユーザが指定できる(これが入力)。

具体的な評価基準(どんな性質を持つ形状が望ましいか?)

この論文では望ましい性質として以下の5つの評価基準を挙げています。

  1. 単純な絵だけでなく、一般的な複雑な絵を扱うことができる
  2. 高解像度である
  3. 連続的な輝度の分布を扱うことができる(特に輝度が低い領域でも高品質を保てる)
  4. フォーカスの幅が広い
  5. フォーカスが多少ずれても集光現象による絵が連続的である

既存研究はいくつか存在するものの [Finckh et al., 2010; Papas et al., 2011; Yue et al., 2012] 、これらの基準を同時に満たす手法は今回の提案手法が初めてであると論文内で主張されています。

手法

入力画像の caustics を生成できるように、ポアソン方程式を解きながら透明物体の表面とスクリーンの表面との全単射写像を決定し、続いてその制約を満たすように、(別の)ポアソン方程式を解きながら理想的な三次元形状を決定するそうです。(よく読めていないので語弊があるかもしれません)ポアソン方程式の形に定式化した点がポイントだそうです。

2. High-Contrast Caustic Design

Yuliy Schwartzburg, Romain Testuz, Andrea Tagliasacchi, Mark Pauly
High-contrast Computational Caustic Design
SIGGRAPH '14
Yuliy Schwartzburg

概要の意訳

スクリーンに投影される集光現象 (caustics) の様子が目的の絵になるような表面形状を求める caustic design のアルゴリズムを提案する。本手法は piecewise smooth surfaces と non-bijective mappings をサポートし、これによって、集光による絵の滑らかな遷移、infinite light density による特異点、完全に暗い領域などが可能となる。

できるだけ短くまとめると

上記の [Yue et al., 2014] と同様、Goal-Based Caustics (または Computational Caustics Design) に関する論文で、基本的には同じ問題を解いています。

ただし既存手法や [Yue et al., 2014] と比較しても、高いコントラスト(明るいところは明るく、暗いところは暗く)が実現できている点や、点や曲線などの形状の光が局所的に集中する部分(論文では singularity と呼んでいます)が実現できる点などの利点を持っています。

特徴

生成された表面形状は連続で、piecewise smooth である点が特徴だそうです。よく読んでいないので正確にはどういう意味か分かっていませんが、おそらく基本的には滑らかだけど大局的には滑らかではない(滑らかでない部分が存在できる)ような状態のことを指しているのだと思います。

また透明物体の表面の点とスクリーン上の点が、既存手法では二次元の全単射写像になっていたのに対し、この手法では全単射でないような写像も許すような定式化となっています。これによって、完全に暗い領域を作れたりするなど、非常にコントラストの高い結果が望めます。また光が局所的に集中する点や曲線(singularity)が表現できるそうです。

手法の流れ

前半で、理想的な写像を決定 (optimal transport) します。この写像を実現できるように、後半で、理想的な三次元形状を決定 (target optimization) します。

[Yue et al., 2014] との比較

論文内で、Poisson-based continuous (PBC) method [Yue et al., 2014] との比較が行われています。同じ画像を入力とし、同じ入力光を仮定したときに、より高いコントラストが実現できることをシミュレーション結果の図を比較して説明しています。

手法としては、[Yue et al., 2014] がポアソン方程式を解くことで大域的に smooth な表面形状を生成する(制約が大きい)のに対し、提案手法は表面形状の normal field に不連続な分布を許しているため、表現能力が増しているというようなことが主張されています。

3. Boxelization

Yahan Zhou, Shinjiro Sueda, Wojciech Matusik, Ariel Shamir
Boxelization: Folding 3D Objects Into Boxes
SIGGRAPH '14

概要の意訳

立方体(箱型)に折り畳むことができるような三次元オブジェクトをデザインするための手法を提案する。更にその手法は折り畳む際の手順において交差が起きない (intersection-free) ことを保証する。この論文ではいくつかの入力三次元オブジェクトに対する結果を報告し、さらに三次元プリンタを用いたファブリケーションの結果も報告する。

できるだけ短くまとめると

三次元モデルを入力として、それを箱型に折り畳めるようにする (= boxelization) という研究です。

技術的なチャレンジとしては

  1. 特殊な voxelization (普通の voxelization では綺麗な箱型にならない)
  2. 箱型に折り畳めるような構造の探索 (ビームサーチのような探索手法?)
  3. 得られた解が実際に交差が起きずに (intersection-free) 折り畳んだり開いたりできるかの確認

の3つが挙げられています。

得られた結果は実際に三次元プリンタで出力してパズルとして遊ぶことができます。

4. The Connect-the-Dots Family of Puzzles: Design and Automatic Generation

Maarten Löffler, Mira Kaiser, Tim van Kapel, Gerwin Klappe, Marc van Kreveld, Frank Staals
The Connect-the-Dots Family of Puzzles: Design and Automatic Generation
SIGGRAPH '14

概要の意訳

伝統的な "Connect-the-Dots パズル" の革新的な派生を紹介する。これらの派生は幾何学的なルールに基づいている。我々は何が「良い」パズルを作るために必要かを解析し、数学的にモデル化した。更に、本論文では与えられた輪郭絵に対して自動的にパズルを生成する手法を提案する。

論文の全体像

この論文は大きく2つのパートに分かれます。

前半: パズルのルールの拡張

まずは Connect-the-Dots パズルのルールを拡張する方法について議論します。従来は点にふってある番号の順に線を繋いでいくのですが、番号をふる代わりに、

  1. 示された方向の点と結ぶ
  2. 最も近い点と結ぶ
  3. 一定の距離にある点と結ぶ

という3つの新しいルールを導入すること、従来よりも面白くて難しい(論文内では interesting and challenging と表現されています)Connect-the-Dots のパズルを考えることができます。

後半: パズの自動生成

後半では、このようにして定義された新しい Connect-the-Dots パズルをアルゴリズムによって自動生成するという話になります。この論文では

  1. 入力の線画にできるだけ近い
  2. 点の数が多すぎない
  3. 曖昧な部分が少ない

という基準を考慮しながらパズルを生成するアルゴリズムを考案しています。

5. Self-Refining Games

Matt Stanton, Ben Humberston, Brandon Kase, James O'Brien, Kayvon Fatahalian, Adrien Treuille
Self-Refining Games Using Player Analytics
SIGGRAPH '14
Self-Refining Games using Player Analytics

概要の意訳

データドリブンのアニメーションやレンダリングでは、数多く存在する「状態」の中から適切な状態を学習データとして選択することが重要である。ゲームのプレイ統計から学習することで、多くのプレイヤーが実際に直面することになる(起こりやすい)状態を推定することが可能である。学習データをこれらの(起こりやすい)状態の周辺に集中させることで、誤差や見た目上のアーティファクトを軽減することができる。

できるだけ短くまとめると

クラウドソーシングによって得られた統計データを活用することで、データドリブンシミュレーションの事前計算の質をより良くするという研究です。

またゲームという応用に関していうと、クラウド=ゲームプレイヤとなるので、ゲームをプレイすればするほどシミュレーションの精度が上がるという意味で "Self-Refining Games" という概念が提案されています。

事前計算によるデータドリブンシミュレーション [Kim et al., SIGGRPAH '13]

データドリブンなシミュレーションにも色々ありますが、以下の手法 [Kim et al., SIGGRPAH '13] がこの論文で使われている手法の基礎となっています。(ちなみに著者は3人ほど被っています。)

Doyub Kim, Woojong Koh, Rahul Narain, Kayvon Fatahalian, Adrien Treuille, and James F. O'Brien
Near-exhaustive precomputation of secondary cloth effects
SIGGRPAH '13

この Kim らによる論文では、「衣服の揺れを(ほぼ)全て事前計算しておき、実行時には事前計算結果を適切に切り貼りしながら再生する」ということが行われています。

データドリブンシミュレーション [Kim et al., 2013] では何が難しいか

事前計算では、頂点を物理的な状態(相空間における点?)、辺を状態遷移(短いアニメーション)とするような巨大なグラフ (state graph) を構築するということが行われます。このグラフが大きければ大きいほどより精度の高いアニメーションを再現することができるということになります。

しかしながら、実際には物理的な状態は無限に存在するため、完全に全てを計算することはできません。したがって、どの状態を事前計算して、どの状態を事前計算しないかの取捨選択がここでのキーポイントとなります。

[Kim et al., 2013] ではキャラクタのモーションとして motion graph の手法を想定していたため、その特徴をうまく用いて賢く事前計算していたようでした。

クラウドソーシングを活用した賢い事前計算

そもそもクラウドソーシングとは

クラウドソーシング (crowdsourcing) とは、アウトソーシング (outsourcing) を改変した造語で、インターネット越しに待機している不特定多数の群衆 (crowd) にタスクをアウトソーシングするというアイデアを指す言葉です。
クラウドソーシングとは?ヒューマンコンピュテーションとは? - yuki-koyama's blog

ゲームのプレイ統計をクラウドソーシングで集める

今回の論文のターゲットは「ゲームにおける流体シミュレーション」です。ゲームのようなユーザの目的がはっきりした環境では、流体がとり得る物理的な状態の空間は実はかなり偏っている、という特徴に着目し、クラウドソーシングによって集めたゲームのプレイ統計から賢く何を事前計算して何を事前計算しないのかを取捨選択しています。