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
410
ReSTIRの数理と実装 (rtcamp10)
yumcyawiz
1
1.4k
fredholm(rtcamp9)
yumcyawiz
0
130
フォトンマッピングをパス空間から考える
yumcyawiz
0
460
fredholm
yumcyawiz
0
290
Introduction to volume rendering
yumcyawiz
0
2.4k
OSK#p-ray2020年度講義: 古典的レイトレーサーの実装
yumcyawiz
0
280
Ray Tracing: Overview
yumcyawiz
7
1.3k
GLSLでパストレーシングしてコーネルボックスを出す
yumcyawiz
0
560
Other Decks in Programming
See All in Programming
monorepo の Go テストをはやくした〜い!~最小の依存解決への道のり~ / faster-testing-of-monorepos
convto
2
390
Go Conference 2025: Goで体感するMultipath TCP ― Go 1.24 時代の MPTCP Listener を理解する
takehaya
7
1.6k
大規模アプリのDIフレームワーク刷新戦略 ~過去最大規模の並行開発を止めずにアプリ全体に導入するまで~
mot_techtalk
0
380
いま中途半端なSwift 6対応をするより、Default ActorやApproachable Concurrencyを有効にしてからでいいんじゃない?
yimajo
2
340
実践AIチャットボットUI実装入門
syumai
7
2.5k
Introducing ReActionView: A new ActionView-Compatible ERB Engine @ Kaigi on Rails 2025, Tokyo, Japan
marcoroth
3
920
なぜあの開発者はDevRelに伴走し続けるのか / Why Does That Developer Keep Running Alongside DevRel?
nrslib
3
370
私達はmodernize packageに夢を見るか feat. go/analysis, go/ast / Go Conference 2025
kaorumuta
2
490
なぜGoのジェネリクスはこの形なのか? Featherweight Goが明かす設計の核心
ryotaros
7
1k
タスクの特性や不確実性に応じた最適な作業スタイルの選択(ペアプロ・モブプロ・ソロプロ)と実践 / Optimal Work Style Selection: Pair, Mob, or Solo Programming.
honyanya
3
140
After go func(): Goroutines Through a Beginner’s Eye
97vaibhav
0
230
ソフトウェア設計の実践的な考え方
masuda220
PRO
3
490
Featured
See All Featured
How to train your dragon (web standard)
notwaldorf
96
6.3k
Git: the NoSQL Database
bkeepers
PRO
431
66k
CoffeeScript is Beautiful & I Never Want to Write Plain JavaScript Again
sstephenson
162
15k
4 Signs Your Business is Dying
shpigford
185
22k
Context Engineering - Making Every Token Count
addyosmani
5
180
Automating Front-end Workflow
addyosmani
1371
200k
Gamification - CAS2011
davidbonilla
81
5.5k
KATA
mclloyd
32
15k
Balancing Empowerment & Direction
lara
4
680
Dealing with People You Can't Stand - Big Design 2015
cassininazir
367
27k
Raft: Consensus for Rubyists
vanstee
139
7.1k
実際に使うSQLの書き方 徹底解説 / pgcon21j-tutorial
soudai
PRO
188
55k
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を生成できる