2018-05-088分木空間でのレイトレースのコリジョンリスト収集処理を見直して10倍速くしたフォトンマッピングの実装で、フォトンを1万~10万くらいバラまく処理が死ぬほど重かったので、8分木空間におけるレイトレースの処理を見直した。8分木はもとより衝突判定を高速にするための空間分割アルゴリズムだが、レイトレースをする際に、衝突判定をすべき空間の収集に最適化の余地があったのでいろいろコードを弄っていたら、10倍速くなった。簡潔に8分木の分割のロジックを説明する。簡略化のために2次元で考える。分割レベル3の空間では、ルート空間、インデックス0~3の空間レベル1、インデックス0~15の空間レベル2の3つのレベルが作られる。この時、あるオブジェクトPが空間レベル2のインデックス3に属するとする。Pの衝突判定を行う場合、その空間と、そして親空間である、空間レベル1のインデックス0、ルート空間、この3つの空間に属するオブジェクトと比較をすればよい。これがN分木空間における衝突判定の高速化の原理である。ちなみに、空間レベルのグリッドをまたぐ場合は属する空間が親空間に移る。accelerated)を参照されたい。図を示すと上記のようなインデックスになる。特殊な配番に注意すること。これはシフト演算による処理の高速化のための、モートンオーダーを使った配番である。衝突処理の仕組みについては、前述の通りだが、ここで、レイトレースを行う場合の衝突処理を考える。すればよいが、それは効率的ではない。右上のオブジェクトはレイに衝突しないのは自明である。右下のオブジェクトは、グリッドをまたいでいるため、空間レベル2ではなく、空間レベル1のインデックス3に属している。私の従来の実装では、レイの衝突判定は、空間レベル2ベースでグリッドを移動する。インデックスのビジット順序は、空間レベル2の「0,2,3,9,12,14,15」、空間レベル1の「0,2,3」、そしてルート空間である。このような衝突リスト収集処理をエンジンから抜粋する。colliderList;}これはうまく動く。レイの1ステップにおける移動距離が、必ず最大空間レベル(例えば、上の4分木の例だとレベル2)の分割サイズにしかならない。これは、最適ではない。(少なくとも私の実装では)オブジェクトの存在しない空間は、ハッシュリストに登録されない。(あるオブジェクトを登録するとき、その親空間、更にその親空間...と遡って登録はする)。上記の例だと、ハッシュリストに登録されている空間は、空間レベル2の「5」、空間レベル1の「1,3」、そしてルート空間だけである。空間レベル1のインデックス0、左上の空間はまとめて無視できることがハッシュリストの構造から推測ができて、レイの距離は一気に9まで進めていいことがわかる。これを具体的にロジックで考えるならば、あるレイの点が属するすべての空間レベルのうち、「実際にハッシュリストに登録されている空間のレベル+1」の「分割サイズ」の距離だけレイを進めることができる。上記の例の場合、レイの始点がレベル2インデックス0空間とすると、レベル2のインデックス0及びレベル1のインデックス0はハッシュリストに存在せず、ルート空間(空間レベル0)のみが存在する。そのため、レイは空間レベル1の分割サイズだけレイを進めることができる。上記の疎空間におけるレイのステップ距離の最適化を施した後のコードが以下。colliderList;}これは小さなロジックの変更だが、非常に疎な空間(特に、空に向けて放たれるようなレイ)を進むレイのステップを著しく減らすことができる。これにより、私の開発中のレンダリングエンジンのベースのシーンであるコーネルボックスにおける、フォトン散布処理は10倍程度高速化された。して現在はフォトンが1万個、バウンス制限3回という制約下でも、フォトン散布処理に10sec、ライトマップベイク処理に40secかかっている。シーンの複雑度が増す場合、ライトマップのベイク処理はより増加することが想定される。高い品質のフォトンマッピングのために、まだまだチューニングの余地はあるだろう。(事前計算処理とはいえ、毎度数分待たされるとげんなりする)フォトンマッピングの実装は大体終わっているが、ノイズというかにじみがとれない。フォトンの量を十分に増やせばいずれなくなるのか、それとも何かミスがあるのか、判断がつかないでいる。私は雰囲気でGI実装をしている。GI)とは、現...2018-04-06ジオメトリシェーダでライン描画DirectXには一応、線を描画する機能がある。プリミティブ型に...2018-03-28Hashed-Octree(ハッシュ化八分木)による空間分割を実装したそろそろレイトレがしたい。具体的に言えばフォトンマッピング...2018-03-09SkyBoxを実装したSkyBoxを実装した。»プロフィールid:riyaaaaasan東京で働くゲームエンジニア。結局オブジェクト指向とはいったいなんなのかとか、ゲームの設計に関して最近思うことグローバルイルミネーションのためのフォトンマップ実装18分木空間でのレイトレースのコリジョンリスト収集処理を見直して10倍速くしたその気になれば前提知識無し機材無しの無の状態から2週間で美少女VTuberになれたという話Boost.Spirit.QiによるXモデルパーザ実装の紹介1月別アーカイブはてなブログをはじめよう!riyaaaaasanさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。