フォトンマップのための八分木の実装

フォトンマップとは？

今までの記事では、パストレーシングを利用してレンダリングしてきましたが、一番の問題は、なんといってもレンダリングに時間がかかりすぎることです。フォトンマップを使ったレンダリングは、この問題を解決してくれます。フォトンマップとは、光源から放射されたフォトン(レイ、光線)が拡散面に衝突した位置(と入射方向や反射方向)とその衝突面の材質を格納するデータ構造です。このフォトンマップを使えば、拡散面における輝度推定が容易になります。つまり、フォトンマップを使ったレンダリング過程は、大きくわけると2段階にわけられます。第1段階は、フォトンマップの構築です。第2段階は、レイトレーシングまたはパストレーシングを使って、拡散面の輝度推定値を構築されたフォトンマップから計算してレンダリングします。

フォトンマップのデータ構造

拡散面に衝突したフォトンの情報が格納されてれば、どんなデータ構造を使おうが問題ありません。ただ、輝度推定の過程で、格納された全てのフォトンの中から目的のフォトンを効率よく見つけ出す必要があるので、この目的に合ったデータ構造を使えば、より短い時間でレンダリングできます。フォトンマップによる輝度推定では、拡散面上の対象の点に近い位置にあるフォトンを集めて輝度を計算します。このような計算に対して、フォトンを効率よく見つけるデータ構造をいろいろ考えだされているようですが、ここでは、パストレーシングに比べてかなり早くなっていれば、他のデータ構造に比べてちょっと遅いくらいは問題ないので、比較的単純な構造である八分木を実装することにします。二分木の3次元版みたいなものだから、イメージしやすいし。

八分木の仕様

八分木は空間を再帰的に８分割して、その子空間にデータを格納する木構造です。この木構造をフォトンマップとして使えるように、次のような仕様にしました。

• 空間として直方体を使う
• 直方体の内側に位置するフォトンは、その直方体に格納される
• １つの直方体はフォトンに対して容量を持っていて、フォトンを格納できる数が決まっている
• 直方体のフォトンが容量に達したら、直方体を８分割し、該当する子の直方体にフォトンを格納する

八分木の実装

八分木クラスの主要なメソッドを概観します。

コンストラクタ

コンストラクタでは、直方体を定義します。

1  2  3  4  5  6  7

abstract class Octree[B, C <: Octree[B, C]](     val xmin: Float, val xmax: Float,     val ymin: Float, val ymax: Float,     val zmin: Float, val zmax: Float,     val capacity: Int,     val parent: Option[C]   )

型パラメータBは、格納するデータの型です。型パラメータCは、サブクラスの型です。子の直方体を生成する際には、C型のインスタンスを生成するようにします。これは、サブクラスで定義したメンバーを使用できるようにするためです。

子を生成するメソッド

直方体を８分割して子の直方体を生成するときに使用されるメソッドです。コンストラクタと同じ引数を取ります。サブクラスで実装します。

1  2  3  4  5  6  7

protected def create(       xmin: Float, xmax: Float,       ymin: Float, ymax: Float,       zmin: Float, zmax: Float,       capacity: Int,       parent: Option[C]     ): C

戻り値の型は、上述したようにサブクラスの型です。

フォトンの追加

フォトンを追加するメソッドです。既に最大容量に達していれば、子を作成し、子に格納する。

1  2  3  4  5  6  7  8  9  10  11

def add( a: Vector3, b: B )(implicit tag: ClassTag[C]): Unit = if( ndata < capacity ) {       _data = (a, b) :: _data       ndata += 1       onUpdate( b )     } else {       createChildren // 既に子を持っている場合は子を作成しない       // このOctreeが持っているデータを子に移す       _data.foreach { case (p, q) => findChild( p ).foreach( _.add( p, q ) ) }       findChild( a ).foreach( _.add( a, b ) )       _data = Nil     }

フォトンの探索

指定した球に含まれる、または接している最下層の直方体を見つけ、クロージャに渡す。

1  2  3  4  5  6  7  8  9  10  11

def filterChildren( b: BoundingSphere, f: (Int, C) => Unit ): Unit = boundingSphere.contains( b ) match {       // 離れている場合       case 3 => ()       // bがこのOctreeを含んでいる場合       case 2 => f( 2, this )       // このOctreeがbを含んでいるか接している場合       case n => _children match {         case None => f( n, this )         case Some( cs ) => cs.foreach { _.filterChildren( b, f ) }       }     }