kd-treeの構築と近傍要素の抽出 - imHoフォトンマップを作った後、実際に描画するときに放射輝度を求めるために視点からの交点近辺のフォトンを取り出す必要がある。この処理を高速に行うためにはkd-treeを使うといい、という話。 でもいきなり3D用のkd-treeのルーチンを書いて動かせる自信がない…なので2Dのテストプログラムを作る。 kd-treeテスト kd-treeの構築 木をバランスさせるため、フォトンを記録し終わってから構築する 分割する軸を選ぶ（x,y,zで一番長い軸にしてみた） 分割軸に沿ってソート 左右でバランスするように、左右の要素数を決める（葉が左詰になって欲しいので、あれこれ計算） // 木を分割する中央のインデクスを求める int select_median_index(int n) { // 左詰にするため、あれこれ計算 int h = log2(n); int s = 1 << h; int d = n
