Fast Ray Tracing by Ray Classification 超誤訳・要約
http://artis.imag.fr/Members/Cyril.Soler/DEA/Ombres/Papers/Arvo.Sig87.pdf
Bee先生の掲示板みてたらRay Classificationについて記述があって、よく知らなかったので論文よんでみた。
http://www.stud.tu-ilmenau.de/~juhu/Papers/IWK/node21.html
を見てみると、この論文そのままの方法では実際実装してみるとあんまりいい結果がでなかったらしく、実装するなら上リンク中のHW94の方がお勧めらしい。
James Arvo, David Kirk
Apple Computer, Inc.
Computer Graphics, Volume 21, Number 4, July 1987(俺が生まれる前だ!)
Abstract
5D空間分割使ってray-objとかray-bound交差判定減らして高速化するよ。同じ3Dボクセルから同じような2D立体角に向かうレイのカタマリを5次元ハイバーキューブとみなすよ。5次元にマップされたレイは動的にハイパーキューブに分割されて、交差候補リストと対応づけされるよ。対象objはいろいろ考えてみたよ。いい感じの結果でてきたよ。(特に複雑なシーンではいい感じだよ)
1. Introduction
略
1.1 Previous Work
略
1.2 New Approach
われわれのアプローチは空間分割による高速化アルゴリズムにレイ方向を含めるように拡張したという点で今までのものと大きく異なる。実測的にシーンの複雑さによらないような強力な隠面消去関数が得られた。
このアルゴリズムの鍵は隠面消去関数を一回評価するだけで小さいが完全な交差候補の集合を得られることにある。adaptiveに対象レイ空間を同値類(equivalence class)に分割してやり、それぞれに対応する交差候補集合を対応付けてあげるよ。
2. 5-Space and Ray Classification
レイは多くの実装で3D位置ベクトルと3D方向ベクトルで表されるけど、実際の自由度は3D位置ベクトルと2D方向のみだよ。ね。
Ray Classificationは5つの工程にわけられるよ。
1. 5D Bounding Volume
対象レイ全てを含む空間をみつける。
2. 5D Space Subdivision
に分割
3. Candidate Set Creation
に対応する交差候補集合をつくる。
4. Ray Classification
レイ一つ一つがどのに属するかみて、対応するをみつける。
5. Candidate Set Processing
候補リストの要素に対して実際に交差判定を行う。
2.1 Beams as 5D Hypercubes
レイ空間の5Dのhypercubeは3D空間で見るとビーム状になってるからこれを「ビーム」と呼ぶことにするよ。
2.2 Rays as 5D points
u, vをどうするか。(略)
3 The 5D Bounding Volume
Ray Classificationアルゴリズムの最初のステップはすべての対象レイを含むR^5空間をみつけることだったよね。まず最初にシーンobj全てを含む3DのBoundingBoxをつくってそれをBとするとBx[-1, 1]x[-1, 1]でいけそうだね。
Bにはもう一つ意味があって、もしレイの始点がBの外だったらまずB全体と交差判定してやって、Bと交差するのならBの中に始点を移動、交差しなかったらどのobjとも交差しないってことになるよね!