Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
Accelerate your Ray Tracer
Search
yumcyawiz
September 07, 2018
Programming
0
110
Accelerate your Ray Tracer
yumcyawiz
September 07, 2018
Tweet
Share
More Decks by yumcyawiz
See All by yumcyawiz
rtcamp 10 (vk-illuminati)
yumcyawiz
1
370
ReSTIRの数理と実装 (rtcamp10)
yumcyawiz
1
1.2k
fredholm(rtcamp9)
yumcyawiz
0
120
フォトンマッピングをパス空間から考える
yumcyawiz
0
440
fredholm
yumcyawiz
0
290
Introduction to volume rendering
yumcyawiz
0
2.3k
OSK#p-ray2020年度講義: 古典的レイトレーサーの実装
yumcyawiz
0
270
Ray Tracing: Overview
yumcyawiz
7
1.3k
GLSLでパストレーシングしてコーネルボックスを出す
yumcyawiz
0
540
Other Decks in Programming
See All in Programming
Startups on Rails in Past, Present and Future–Irina Nazarova, RailsConf 2025
irinanazarova
0
110
なぜ適用するか、移行して理解するClean Architecture 〜構造を超えて設計を継承する〜 / Why Apply, Migrate and Understand Clean Architecture - Inherit Design Beyond Structure
seike460
PRO
3
770
Goで作る、開発・CI環境
sin392
0
230
イベントストーミング図からコードへの変換手順 / Procedure for Converting Event Storming Diagrams to Code
nrslib
2
820
High-Level Programming Languages in AI Era -Human Thought and Mind-
hayat01sh1da
PRO
0
780
なんとなくわかった気になるブロックテーマ入門/contents.nagoya 2025 6.28
chiilog
1
270
たった 1 枚の PHP ファイルで実装する MCP サーバ / MCP Server with Vanilla PHP
okashoi
1
260
技術同人誌をMCP Serverにしてみた
74th
1
650
スタートアップの急成長を支えるプラットフォームエンジニアリングと組織戦略
sutochin26
1
5.8k
レベル1の開発生産性向上に取り組む − 日々の作業の効率化・自動化を通じた改善活動
kesoji
0
220
AIプログラマーDevinは PHPerの夢を見るか?
shinyasaita
1
220
Systèmes distribués, pour le meilleur et pour le pire - BreizhCamp 2025 - Conférence
slecache
0
120
Featured
See All Featured
How STYLIGHT went responsive
nonsquared
100
5.6k
Fantastic passwords and where to find them - at NoRuKo
philnash
51
3.3k
jQuery: Nuts, Bolts and Bling
dougneiner
63
7.8k
What's in a price? How to price your products and services
michaelherold
246
12k
Templates, Plugins, & Blocks: Oh My! Creating the theme that thinks of everything
marktimemedia
31
2.4k
Visualization
eitanlees
146
16k
Designing for humans not robots
tammielis
253
25k
Build The Right Thing And Hit Your Dates
maggiecrowley
36
2.8k
What’s in a name? Adding method to the madness
productmarketing
PRO
23
3.5k
The World Runs on Bad Software
bkeepers
PRO
69
11k
Git: the NoSQL Database
bkeepers
PRO
430
65k
Making the Leap to Tech Lead
cromwellryan
134
9.4k
Transcript
ACCELERATE YOUR RAY TRACER 効率の良い衝突計算の方法
衝突計算の効率化 • 現在の実装は全ての物体と衝突するかを一つ一つ調べている(線形探索)
線形探索 このような場合でも物体一つ一つと衝突計算が行われる
衝突計算の効率化 • 現在の実装は全ての物体と衝突するかを一つ一つ調べている(線形探索) 圧倒的に無駄が多い
衝突計算の効率化 • 現在の実装は全ての物体と衝突するかを一つ一つ調べている(線形探索) 大量のポリゴンに対応することができない
効率化手法 • Bounding Volume Hierarchy(BVH) • Kd-Tree
BVH • 物体をBounding Volumeと呼ばれる枠で囲む • 衝突計算を行うときは、まず枠と衝突するか試す
BVH 枠と衝突しないので中の物体は見ない
BVH • 物体をBounding Volumeと呼ばれる枠で囲む • 衝突計算を行うときは、まず枠と衝突するか試す • さらにBounding VolumeをBounding Volumeで囲んで木構造にする
BVH まず全体の枠と衝突計算をする
BVH 中の枠と衝突計算をする
BVH 最終的に枠の中で線形探索して衝突物体を得る
BVHの木構造
枠の生成方法 • Axis Aligned Bounding Box(AABB)と呼ばれる長方形を枠として使うことが一 般的 • AABBとは各軸に平行な長方形のこと •
中の物体の合計の大きさに合わせるようにする
AABB
BVHによる衝突計算の流れ 1. 物体集合からBVHを生成 2. まず全体の枠と衝突計算 3. 当たったら中の要素を衝突計算 4. 当たったらさらに中の要素を衝突計算 …
5. 最終的な衝突物体を得る 再帰的な処理
BVHの生成方法 • 中央分割法(Median Split) • 等数分割法(Equal Size Split) • Surface
Area Heuristics(SAH) いずれも全体の枠の長さが最大となる軸を分割軸として選ぶ
Median Split 中央値の位置で分割する
左右で物体の数が等しくなるところで分割する Equal Size Split
SAHのコストが最も低くなるところで分割する SAH 50 10 40 30 45
SAHコストの計算方法 = + + : 木の走査のコスト : 親の枠の表面積 , :
子の枠の表面積 , : 子の枠に入っている物体数 :物体との衝突計算のコスト このコストが最小となる分割位置を選ぶ
比較 Equal Size Median SAH SAHが最も優れたBVHを生成できる