Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Sign up for free
Menu
Search
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Pricing
Search
Sign in
Sign up for free
Accelerate your Ray Tracer
Search
yumcyawiz
September 07, 2018
Programming
130
0
Share
Embed
Copy iframe code
Copy JS code
Copy link
Start on current slide
Accelerate your Ray Tracer
yumcyawiz
September 07, 2018
Transcript
22 slides
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を生成できる
More Decks by yumcyawiz
See All by yumcyawiz
rtcamp 10 (vk-illuminati)
yumcyawiz
1
580
ReSTIRの数理と実装 (rtcamp10)
yumcyawiz
1
2.1k
fredholm(rtcamp9)
yumcyawiz
0
200
フォトンマッピングをパス空間から考える
yumcyawiz
0
580
fredholm
yumcyawiz
0
370
Introduction to volume rendering
yumcyawiz
0
2.9k
OSK#p-ray2020年度講義: 古典的レイトレーサーの実装
yumcyawiz
0
320
Ray Tracing: Overview
yumcyawiz
7
1.4k
GLSLでパストレーシングしてコーネルボックスを出す
yumcyawiz
0
650
Other Decks in Programming
See All in Programming
まずはコードより業務と向き合う:テーブル解体のためにPdMを呼んだ話
sakawe_ee
0
260
Goコンパイラを作ってGoをもっと理解する / Build a Go compiler to better understand Go
ikura_hamu
0
130
作れるエンジニアから、価値を届けるエンジニアへ
ryunakayama
1
320
우리의 Nitro Modules는 당신의 Turbo Modules보다 아름답다
l2hyunwoo
0
270
祈るテストから、探索するテストへ 〜Lincheckではじめる並行処理テスト〜
yyh_gl
0
400
Claude Codeのおかげでやりたいことがやれるようになったんだよォー!
sms_tech
0
170
LLM 101
dalinaum
0
520
React Native에 현대적인 빌드 도구 더하기: Rollipop 구현기
leegeunhyeok
0
190
はじめてのKubernetesコントリビューション
nasa9084
0
190
Kawaiicon: Kubernetes, it's no longer cool, but let's secure it anyway!
barnbarn
0
140
baseline으로 마이그레이션, 리팩토링 안전하게 맡기기
fornewid
1
1k
Materialが消えた日 〜真っ白なFlutterキャンバスにRenderObjectで絵を描く〜
umigishiaoi
0
170
Featured
See All Featured
For a Future-Friendly Web
brad_frost
184
11k
JAMstack: Web Apps at Ludicrous Speed - All Things Open 2022
reverentgeek
1
680
So, you think you're a good person
axbom
PRO
2
2.3k
実際に使うSQLの書き方 徹底解説 / pgcon21j-tutorial
soudai
PRO
203
77k
Building AI with AI
inesmontani
PRO
1
1.4k
コードの90%をAIが書く世界で何が待っているのか / What awaits us in a world where 90% of the code is written by AI
rkaga
63
48k
Save Time (by Creating Custom Rails Generators)
garrettdimon
PRO
33
5.9k
HTML-Aware ERB: The Path to Reactive Rendering @ RubyCon 2026, Rimini, Italy
marcoroth
6
960
Agile Actions for Facilitating Distributed Teams - ADO2019
mkilby
0
350
GraphQLとの向き合い方2022年版
quramy
50
15k
CoffeeScript is Beautiful & I Never Want to Write Plain JavaScript Again
sstephenson
162
16k
A Modern Web Designer's Workflow
chriscoyier
699
190k