----
#contents
----
*Screen Space Mesh [#v6f6fd84]
陰関数曲面から表面を記述する三角形メッシュを抽出する場合，
Marching Cubesに代表されるように3D空間を3Dのグリッド構造で分割し，
各セルにおいてメッシュを生成するのが一般的である．
これに対して2Dスクリーン空間でメッシュを生成するのが，
Screen Space Meshes(SSM)¬e{Muller2007:M. Muller, S. Schirm and S. Duthaler, Screen space meshes, Proc. SCA2007, pp.9-15, 2007.};である．
SSMはパーティクルから生成した閉じた陰関数曲面を対象としている．
物体形状を三角形メッシュで表した場合，視点から見えない面(視点から隠れている面)は描画する必要がない．
このような隠面消去はOpenGLなどの3D APIにおける描画では一般的である．
SSMでは同様の考え方で，そもそも隠面は三角形ポリゴンを作る必要がないとし，
3D空間内のパーティクルを2Dスクリーン空間に投影して生成したデプスマップから，
2Dメッシュを生成，3D空間に逆投影することで視点から見える三角形ポリゴンだけで構成されるメッシュを生成する．
また，デプスマップに対して平滑化フィルタをかけることでメタボールのようなレンダリングを得る．
3D Marching Cubesでは計算コストは各軸の分割数nの3乗に比例するが，
SSMでは2D空間でメッシュを生成するので，nの2乗に比例するだけである．
ただし，視点から見えている面しかできないので，
屈折面だと1回の屈折しか考慮できないことには注意．
**入力 [#r4bdac33]
SSMはパーティクルデータを対象としているため，入力はパーティクル座標と投影変換行列の2つとなる．
-パーティクル座標 : &ref(ssm.eq1.gif,nolink,70%);
-投影変換行列 : &ref(ssm.eq2.gif,nolink,70%);
さらに，固定パラメータとして以下のものがある．
-スクリーン間隔 : &ref(ssm.eq3.gif,nolink,70%);~
スクリーン空間でのグリッド幅．
-パーティクル半径 : &ref(ssm.eq4.gif,nolink,70%);~
スクリーン空間でのパーティクル半径．
-平滑化係数 : &ref(ssm.eq5.gif,nolink,70%);~
デプスマップ平滑化のフィルタ幅と輪郭平滑化のための反復数．
-デプス閾値 : &ref(ssm.eq6.gif,nolink,70%);~
デプス値のメッシュ化閾値．この閾値以上のデプス値を持つグリッドがメッシュ化される．
**手順 [#c86cd97e]
デプスマップを
#ref(ssm.eq7.gif,nolink,70%)
とし，各グリッドでのデプス値を&ref(ssm.eq8.gif,nolink,70%);で表す．
グリッド分割数は，スクリーン間隔&ref(ssm.eq9.gif,nolink,70%);とスクリーンサイズ(&ref(ssm.eq10.gif,nolink,70%);)から以下のように計算する．
#ref(ssm.eq11.gif,nolink,70%)
|&ref(screen_space.jpg,nolink,100%);|
|CENTER:デプスマップ|
以下で&ref(ssm.eq12.gif,nolink,70%);を用いたスクリーンスペースメッシュの生成方法を述べる．
**デプスマップ生成 [#r90e301a]
まず，&ref(ssm.eq8.gif,nolink,70%);を&ref(ssm.eq13.gif,nolink,70%);で初期化する．
次にすべてのパーティクルの中心座標，半径に投影変換を施す．
まず，中心座標に投影変換行列をかける．
#ref(ssm.eq14.gif,nolink,70%)
さらに&ref(ssm.eq15.gif,nolink,70%);で割ることで[-1, 1]の正規化座標系に変換
#ref(ssm.eq16.gif,nolink,70%)
&ref(ssm.eq17.gif,nolink,70%);はメッシュ生成の基準に用いるので正規化しない．
半径に関しても同様に，
#ref(ssm.eq18.gif,nolink,70%)
&ref(ssm.eq19.gif,nolink,70%);は投影変換行列の各要素である．
&ref(ssm.eq20.gif,nolink,70%);はすべてのパーティクルで共通なので事前に計算しておく．
パーティクル中心座標と半径を使ってデプス値を更新する．
#ref(ssm.eq21.gif,nolink,70%)
ここで，
#ref(ssm.eq22.gif,nolink,70%)
ただし，&ref(ssm.eq23.gif,nolink,70%);は，
#ref(ssm.eq24.gif,nolink,70%)
を満たす範囲内のセルである．ここで，&ref(ssm.eq25.gif,nolink,70%);である．
この処理をすべてのパーティクルで行うことでデプスマップが生成される．
**デプスマップ平滑化 [#m666dfe4]
ユーザが設定したフィルタ幅&ref(ssm.eq26.gif,nolink,70%);でBinomialフィルタをかけることでデプスマップを平滑化する
(&ref(ssm.eq27.gif,nolink,70%);の場合，中心となるデプス値の前後3つのデプス値を使う)．
まず最初に&ref(ssm.eq28.gif,nolink,70%);であるすべてのデプス値に対してx軸方向に1次元フィルタを適用する．
次に同様にしてy軸方向にも適用する．
また，，中心デプス値との差が&ref(ssm.eq29.gif,nolink,70%);以内のデプス値のみをフィルタに用いる．
**輪郭ノード検出 [#h8a28cf3]
メッシュの外周となる輪郭部分に属するノードを検出する．
ここでいうノードとは輪郭をまたぐグリッドエッジ(輪郭エッジ)上の点のことである．
ここでのグリッドとはMarching Squaresによりメッシュを生成するためのグリッドのことであり，
デプスマップ用のグリッドとは異なる．ただし，説明を簡単にするために以下では両者のグリッド解像度は同じであるとする．
隣接するグリッドのデプス値を比較することで，エッジが輪郭と交差しているかどうかを判定するのだが，
単純にデプス値が有限と無限の境が輪郭とすると，
下図のような場合に本来つながっていないところがつながってしまう(青の波線)．
本来赤の実線のようなメッシュを作りたいので，デプス閾値&ref(ssm.eq29.gif,nolink,70%);を使って輪郭となるノードを検出する．
|&ref(ssm_silhouette.jpg,nolink,100%);|
|CENTER:輪郭でのメッシュ|
デプスマップ生成の際と同様に各パーティクルごとにグリッドエッジを走査し，円と線分の交差判定を使い，
パーティクル境界と交差するエッジとノード，および，ノードデプス値&ref(ssm.eq17.gif,nolink,70%);を求める．
求めたエッジが輪郭エッジとなる条件は以下．
-エッジ端点のデプス値の差が&ref(ssm.eq29.gif,nolink,70%);より大きい
デプスマップからデプス値を抽出して上記の判定を行う．
この条件を満たすとき，輪郭エッジ内に1つの輪郭ノードが存在する．
さらに，
-&ref(ssm.eq30.gif,nolink,70%); エッジデプス値平均 (下図左)
-エッジにすでに輪郭ノードが格納されていた場合，&ref(ssm.eq31.gif,nolink,70%);格納輪郭ノードのデプス値 (下図右)
を満たす場合，そのノードを輪郭ノードとしてエッジに格納しておく．
このとき，輪郭ノードが含まれる輪郭エッジの両端点のデプス値は後で使うので参照できるようにしておく．
|&ref(ssm_silhouette_a.jpg,nolink,100%);|&ref(ssm_silhouette_b.jpg,nolink,100%);|
|>|CENTER:輪郭ノードの選択(2重丸が輪郭ノードとして採用すべき点)|
**メッシュ頂点生成 [#z03cb575]
輪郭ノードに加えて，内部の頂点も加えて，メッシュ頂点を算出する．
頂点を生成するパターンは以下の3つである．
-&ref(ssm.eq13.gif,nolink,70%);でない値を持つグリッドノード : 1つのメッシュ内部頂点
-両端点のデプス値が&ref(ssm.eq13.gif,nolink,70%);と&ref(ssm.eq32.gif,nolink,70%);である輪郭エッジ上の輪郭ノード : 1つのメッシュ輪郭頂点 - 外部輪郭
-両端点のデプス値が両方とも&ref(ssm.eq32.gif,nolink,70%);である輪郭エッジ上の輪郭ノード : 2つのメッシュ輪郭頂点(front vertex と back vertex) - 内部輪郭
front vertexの座標，デプス値は輪郭エッジに格納された輪郭ノードと同じである．
back vertexの座標は対応するfront vertexと同じであるが，デプス値は分からない．
そのため，隣接するグリッドノードのデプス値の外挿により算出する(下の図参照)．
|&ref(ssm_front_and_back_vertex.jpg,nolink,100%);|
|CENTER:front vertex と back vertex|
**三角形メッシュ生成 [#n0a1203b]
下図参照．三角形間の隙間はそこに輪郭頂点があることを示す．
また，外部輪郭の場合はデプス値が&ref(ssm.eq13.gif,nolink,70%);である頂点を含む三角形は排除する．
7,11,13,14のケースでは，3層に分かれており，もう一つ back vertexが必要，
15のケースでは4層で，2つのback vertex を追加する必要がある．
|&ref(ssm_mesh.jpg,nolink,100%);|
|CENTER:三角形メッシュのパターン¬e{Muller2007}|
|CENTER:三角形メッシュのパターン¬e{Muller2007};|
基本的にはMC法と同じくテーブルを作ってやればよいが，
いくつかの例外処理(追加のback vertexが必要な場合など)は必要である．
**輪郭平滑化 [#aa79d64f]
各輪郭頂点座標を，隣接頂点と自分自身の座標値の平均値で置き換えることで，
輪郭の平滑化を行う．ただし，メッシュ生成におけるケース0の頂点は固定とする．
**3D空間への逆投影 [#f3364436]
スクリーン空間内の2Dメッシュを3D空間に戻す．
各メッシュ頂点に対して，以下の処理を行う．
#ref(ssm.eq33.gif,nolink,70%)
ここで，&ref(ssm.eq34.gif,nolink,70%);であり，
#ref(ssm.eq35.gif,nolink,70%)
**実装結果 [#r9652174]
パーティクルを立方体形状にランダムに発生させて，そのメッシュをSSMで生成した結果を以下に示す．
#ref(ssm_dmap.jpg,,50%)
左がメッシュ生成した結果で，右がそのデプスマップを示す．
スクリーンの大きさは 640x640 であり，デプスマップのグリッド間隔h=8である．
フィルタ幅は3，パーティクル数5000である．
デプスマップ上のメッシュを描画した図を以下に示す．
#ref(ssm.jpg,,50%)
また，生成したメッシュを異なる角度からみた結果は以下．
#ref(ssm2.jpg,,50%)
CPU実装でもデプスマップ解像度が100x100程度ならリアルタイムで実行でき，GPU版ともほとんど計算時間が変わらない．
より細かくなって300x300などになってくるとCPU版だと0.15sec/frameぐらい，GPU版だと0.05sec/frameぐらいで実行できた
(Core i7 2.93GHz, GeForce GTX580)．
**サンプルコード(GPU実装含む) [#u3982f36]
SSMを実装してみたコードを以下に置く(CUDAによるGPU実装含む)．
#ref(rx_ssm.zip);
-ビルドするのに必要なライブラリ
FLTK, freeglut, GLEW, CUDA, boost
各ライブラリについては[[ライブラリのインストール]]を参照．
-簡単な説明＆注意事項
--パーティクルを立方体形状にランダムに発生させて，そのメッシュを生成する．
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
