Screen Space Mesh

陰関数曲面から表面を記述する三角形メッシュを抽出する場合, Marching Cubesに代表されるように3D空間を3Dのグリッド構造で分割し, 各セルにおいてメッシュを生成するのが一般的である. これに対して2Dスクリーン空間でメッシュを生成するのが, Screen Space Meshes(SSM)(1)である.

SSMはパーティクルから生成した閉じた陰関数曲面を対象としている. 物体形状を三角形メッシュで表した場合,視点から見えない面(視点から隠れている面)は描画する必要がない. このような隠面消去はOpenGLなどの3D APIにおける描画では一般的である. SSMでは同様の考え方で,そもそも隠面は三角形ポリゴンを作る必要がないとし, 3D空間内のパーティクルを2Dスクリーン空間に投影して生成したデプスマップから, 2Dメッシュを生成,3D空間に逆投影することで視点から見える三角形ポリゴンだけで構成されるメッシュを生成する. また,デプスマップに対して平滑化フィルタをかけることでメタボールのようなレンダリングを得る.

3D Marching Cubesでは計算コストは各軸の分割数nの3乗に比例するが, SSMでは2D空間でメッシュを生成するので,nの2乗に比例するだけである. ただし,視点から見えている面しかできないので, 屈折面だと1回の屈折しか考慮できないことには注意.

入力

SSMはパーティクルデータを対象としているため,入力はパーティクル座標と投影変換行列の2つとなる.

  • パーティクル座標 : ssm.eq1.gif
  • 投影変換行列 : ssm.eq2.gif

さらに,固定パラメータとして以下のものがある.

  • スクリーン間隔 : ssm.eq3.gif
    スクリーン空間でのグリッド幅.
  • パーティクル半径 : ssm.eq4.gif
    スクリーン空間でのパーティクル半径.
  • 平滑化係数 : ssm.eq5.gif
    デプスマップ平滑化のフィルタ幅と輪郭平滑化のための反復数.
  • デプス閾値 : ssm.eq6.gif
    デプス値のメッシュ化閾値.この閾値以上のデプス値を持つグリッドがメッシュ化される.

手順

デプスマップを

ssm.eq7.gif

とし,各グリッドでのデプス値をssm.eq8.gifで表す. グリッド分割数は,スクリーン間隔ssm.eq9.gifとスクリーンサイズ(ssm.eq10.gif)から以下のように計算する.

ssm.eq11.gif
screen_space.jpg
デプスマップ

以下でssm.eq12.gifを用いたスクリーンスペースメッシュの生成方法を述べる.

デプスマップ生成

まず,ssm.eq8.gifssm.eq13.gifで初期化する. 次にすべてのパーティクルの中心座標,半径に投影変換を施す. まず,中心座標に投影変換行列をかける.

ssm.eq14.gif

さらにssm.eq15.gifで割ることで[-1, 1]の正規化座標系に変換

ssm.eq16.gif

ssm.eq17.gifはメッシュ生成の基準に用いるので正規化しない. 半径に関しても同様に,

ssm.eq18.gif

ssm.eq19.gifは投影変換行列の各要素である. ssm.eq20.gifはすべてのパーティクルで共通なので事前に計算しておく.

パーティクル中心座標と半径を使ってデプス値を更新する.

ssm.eq21.gif

ここで,

ssm.eq22.gif

ただし,ssm.eq23.gifは,

ssm.eq24.gif

を満たす範囲内のセルである.ここで,ssm.eq25.gifである.

この処理をすべてのパーティクルで行うことでデプスマップが生成される.

デプスマップ平滑化

ユーザが設定したフィルタ幅ssm.eq26.gifでBinomialフィルタをかけることでデプスマップを平滑化する (ssm.eq27.gifの場合,中心となるデプス値の前後3つのデプス値を使う). まず最初にssm.eq28.gifであるすべてのデプス値に対してx軸方向に1次元フィルタを適用する. 次に同様にしてy軸方向にも適用する. また,,中心デプス値との差がssm.eq29.gif以内のデプス値のみをフィルタに用いる.

輪郭ノード検出

メッシュの外周となる輪郭部分に属するノードを検出する. ここでいうノードとは輪郭をまたぐグリッドエッジ(輪郭エッジ)上の点のことである. ここでのグリッドとはMarching Squaresによりメッシュを生成するためのグリッドのことであり, デプスマップ用のグリッドとは異なる.ただし,説明を簡単にするために以下では両者のグリッド解像度は同じであるとする.

隣接するグリッドのデプス値を比較することで,エッジが輪郭と交差しているかどうかを判定するのだが, 単純にデプス値が有限と無限の境が輪郭とすると, 下図のような場合に本来つながっていないところがつながってしまう(青の波線). 本来赤の実線のようなメッシュを作りたいので,デプス閾値ssm.eq29.gifを使って輪郭となるノードを検出する.

ssm_silhouette.jpg
輪郭でのメッシュ

デプスマップ生成の際と同様に各パーティクルごとにグリッドエッジを走査し,円と線分の交差判定を使い, パーティクル境界と交差するエッジとノード,および,ノードデプス値ssm.eq17.gifを求める. 求めたエッジが輪郭エッジとなる条件は以下.

  • エッジ端点のデプス値の差がssm.eq29.gifより大きい デプスマップからデプス値を抽出して上記の判定を行う. この条件を満たすとき,輪郭エッジ内に1つの輪郭ノードが存在する.

さらに,

  • ssm.eq30.gif エッジデプス値平均 (下図左)
  • エッジにすでに輪郭ノードが格納されていた場合,ssm.eq31.gif格納輪郭ノードのデプス値 (下図右)

を満たす場合,そのノードを輪郭ノードとしてエッジに格納しておく. このとき,輪郭ノードが含まれる輪郭エッジの両端点のデプス値は後で使うので参照できるようにしておく.

ssm_silhouette_a.jpgssm_silhouette_b.jpg
輪郭ノードの選択(2重丸が輪郭ノードとして採用すべき点)

メッシュ頂点生成

輪郭ノードに加えて,内部の頂点も加えて,メッシュ頂点を算出する. 頂点を生成するパターンは以下の3つである.

  • ssm.eq13.gifでない値を持つグリッドノード : 1つのメッシュ内部頂点
  • 両端点のデプス値がssm.eq13.gifssm.eq32.gifである輪郭エッジ上の輪郭ノード : 1つのメッシュ輪郭頂点 - 外部輪郭
  • 両端点のデプス値が両方ともssm.eq32.gifである輪郭エッジ上の輪郭ノード : 2つのメッシュ輪郭頂点(front vertex と back vertex) - 内部輪郭

front vertexの座標,デプス値は輪郭エッジに格納された輪郭ノードと同じである. back vertexの座標は対応するfront vertexと同じであるが,デプス値は分からない. そのため,隣接するグリッドノードのデプス値の外挿により算出する(下の図参照).

ssm_front_and_back_vertex.jpg
front vertex と back vertex

三角形メッシュ生成

下図参照.三角形間の隙間はそこに輪郭頂点があることを示す. また,外部輪郭の場合はデプス値がssm.eq13.gifである頂点を含む三角形は排除する. 7,11,13,14のケースでは,3層に分かれており,もう一つ back vertexが必要, 15のケースでは4層で,2つのback vertex を追加する必要がある.

ssm_mesh.jpg
三角形メッシュのパターン(1)

基本的にはMC法と同じくテーブルを作ってやればよいが, いくつかの例外処理(追加のback vertexが必要な場合など)は必要である.

輪郭平滑化

各輪郭頂点座標を,隣接頂点と自分自身の座標値の平均値で置き換えることで, 輪郭の平滑化を行う.ただし,メッシュ生成におけるケース0の頂点は固定とする.

3D空間への逆投影

スクリーン空間内の2Dメッシュを3D空間に戻す. 各メッシュ頂点に対して,以下の処理を行う.

ssm.eq33.gif

ここで,ssm.eq34.gifであり,

ssm.eq35.gif

実装結果

パーティクルを立方体形状にランダムに発生させて,そのメッシュをSSMで生成した結果を以下に示す.

ssm_dmap.jpg

左がメッシュ生成した結果で,右がそのデプスマップを示す. スクリーンの大きさは 640x640 であり,デプスマップのグリッド間隔h=8である. フィルタ幅は3,パーティクル数5000である.

デプスマップ上のメッシュを描画した図を以下に示す.

ssm.jpg

また,生成したメッシュを異なる角度からみた結果は以下.

ssm2.jpg

CPU実装でもデプスマップ解像度が100x100程度ならリアルタイムで実行でき,GPU版ともほとんど計算時間が変わらない. より細かくなって300x300などになってくるとCPU版だと0.15sec/frameぐらい,GPU版だと0.05sec/frameぐらいで実行できた (Core i7 2.93GHz, GeForce GTX580).

サンプルコード(GPU実装含む)

SSMを実装してみたコードを以下に置く(CUDAによるGPU実装含む).

  • 簡単な説明&注意事項
    • パーティクルを立方体形状にランダムに発生させて,そのメッシュを生成する.

(1)  M. Muller, S. Schirm and S. Duthaler, Screen space meshes, Proc. SCA2007, pp.9-15, 2007.

添付ファイル: filessm_mesh.jpg 523件 [詳細] filerx_ssm.zip 993件 [詳細] filessm2.jpg 1284件 [詳細] filessm_silhouette_b.jpg 483件 [詳細] filessm_silhouette_a.jpg 467件 [詳細] filessm_silhouette.jpg 465件 [詳細] filessm_front_and_back_vertex.jpg 499件 [詳細] filescreen_space.jpg 447件 [詳細] filessm_dmap.jpg 1261件 [詳細] filessm.jpg 1239件 [詳細] filessm.eq4.gif 460件 [詳細] filessm.eq5.gif 485件 [詳細] filessm.eq9.gif 463件 [詳細] filessm.eq8.gif 482件 [詳細] filessm.eq7.gif 461件 [詳細] filessm.eq35.gif 425件 [詳細] filessm.eq6.gif 462件 [詳細] filessm.eq34.gif 452件 [詳細] filessm.eq24.gif 483件 [詳細] filessm.eq1.gif 467件 [詳細] filessm.eq22.gif 462件 [詳細] filessm.eq12.gif 476件 [詳細] filessm.eq31.gif 429件 [詳細] filessm.eq29.gif 451件 [詳細] filessm.eq15.gif 458件 [詳細] filessm.eq30.gif 480件 [詳細] filessm.eq17.gif 492件 [詳細] filessm.eq19.gif 441件 [詳細] filessm.eq26.gif 477件 [詳細] filessm.eq16.gif 485件 [詳細] filessm.eq10.gif 442件 [詳細] filessm.eq21.gif 496件 [詳細] filessm.eq25.gif 442件 [詳細] filessm.eq14.gif 503件 [詳細] filessm.eq20.gif 453件 [詳細] filessm.eq11.gif 483件 [詳細] filessm.eq23.gif 440件 [詳細] filessm.eq33.gif 484件 [詳細] filessm.eq2.gif 451件 [詳細] filessm.eq28.gif 476件 [詳細] filessm.eq18.gif 479件 [詳細] filessm.eq13.gif 510件 [詳細] filessm.eq3.gif 482件 [詳細] filessm.eq27.gif 460件 [詳細] filessm.eq32.gif 467件 [詳細]

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2012-04-05 (木) 12:42:47 (3095d)