Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Accelerate your Ray Tracer

Avatar for yumcyawiz yumcyawiz
September 07, 2018
Programming
130
0

Accelerate your Ray Tracer

Avatar for yumcyawiz

yumcyawiz

September 07, 2018

More Decks by yumcyawiz

See All by yumcyawiz
rtcamp 10 (vk-illuminati)
Avatar for yumcyawiz yumcyawiz
1
550
ReSTIRの数理と実装 (rtcamp10)
Avatar for yumcyawiz yumcyawiz
1
1.9k
fredholm(rtcamp9)
Avatar for yumcyawiz yumcyawiz
0
180
フォトンマッピングをパス空間から考える
Avatar for yumcyawiz yumcyawiz
0
550
fredholm
Avatar for yumcyawiz yumcyawiz
0
350
Introduction to volume rendering
Avatar for yumcyawiz yumcyawiz
0
2.8k
OSK#p-ray2020年度講義: 古典的レイトレーサーの実装
Avatar for yumcyawiz yumcyawiz
0
310
Ray Tracing: Overview
Avatar for yumcyawiz yumcyawiz
7
1.3k
GLSLでパストレーシングしてコーネルボックスを出す
Avatar for yumcyawiz yumcyawiz
0
620

Other Decks in Programming

See All in Programming
型も通る、synthも通る、それでも危ない 〜AIのCDKの権限とコストを機械で検証する〜 / It Passes Type Checks, It Passes Synth Checks, but It’s Still Risky — Automatically Verifying Permissions and Costs in AI’s CDK —
Avatar for shiro seike seike460
PRO
1
480
使いながら育てる Claude Code — 開発フローの1コマンド化 × 繰り返し指摘の自動仕組み化
Avatar for endo shiki shiki_kakaku
0
1.3k
『コードを書く以外の』エンジニアリング〜課金基盤移行プロジェクト推進のためのTips4選
Avatar for yuriko yuriko1211
0
560
人間の目はかわらない、だからJPEGは30年もつ
Avatar for yuzneri yuzneri
12
17k
【やさしく解説 設計編・中級 #1】一つの車に、運転手は一人　～ある倉庫システムの事例から～
Avatar for HideyukiKitao panda728
PRO
0
200
Haskell/Servantを通してWebミドルウェアを捉え直す
Avatar for pizzacat83 pizzacat83
1
620
属人化した知識を、 AIが辿れる地図にする
Avatar for PKSHA Technology（パークシャテクノロジー） pkshadeck
PRO
1
120
作るコストが小さくなった時代 幸せに働くために改めて考えたいこと 〜エンジニアとして価値を出し続けるために注視している二分野〜
Avatar for YuppeEng yuppeeng
0
140
変わらないものが、変わるものを決める — 意図駆動開発 × イベントソーシング × イミュータブル | What Doesn't Change Decides What Can — IDD × Event Sourcing × Immutability
Avatar for Tomohisa Takaoka tomohisa
0
700
今さら聞けない .NET CLI
Avatar for tkym htkym
0
150
言語を使う側から、作る側へ。 自作 Lisp で得た新たな気づき。
Avatar for ANDPAD inc andpad
0
140
Google Apps Script で Ruby を動かす
Avatar for Shogo Kawahara kawahara
0
120

Featured

See All Featured
Impact Scores and Hybrid Strategies: The future of link building
Avatar for Tamara Novitovic tamaranovitovic
0
350
Bridging the Design Gap: How Collaborative Modelling removes blockers to flow between stakeholders and teams @FastFlow conf
Avatar for Kenny Baas-Schwegler baasie
0
620
Have SEOs Ruined the Internet? - User Awareness of SEO in 2025
Avatar for Akash Hashmi akashhashmi
0
400
Leveraging Curiosity to Care for An Aging Population
Avatar for Cassini Nazir cassininazir
1
440
Jess Joyce - The Pitfalls of Following Frameworks
Avatar for Tech SEO Connect techseoconnect
PRO
1
310
エンジニアに許された特別な時間の終わり
Avatar for watany watany
108
250k
AI in Enterprises - Java and Open Source to the Rescue
Avatar for ivargrimstad ivargrimstad
0
1.4k
Stewardship and Sustainability of Urban and Community Forests
Avatar for Eric Wiseman pwiseman
0
400
Agile that works and the tools we love
Avatar for Rasmus Luckow-Nielsen rasmusluckow
331
22k
Avoiding the “Bad Training, Faster” Trap in the Age of AI
Avatar for Mike Taylor tmiket
0
200
What's in a price? How to price your products and services
Avatar for Michael Herold michaelherold
247
13k
Designing Powerful Visuals for Engaging Learning
Avatar for Mike Taylor tmiket
1
470

Transcript

  1. ACCELERATE YOUR RAY TRACER 効率の良い衝突計算の方法

  2. 衝突計算の効率化 • 現在の実装は全ての物体と衝突するかを一つ一つ調べている(線形探索)

  3. 線形探索 このような場合でも物体一つ一つと衝突計算が行われる

  4. 衝突計算の効率化 • 現在の実装は全ての物体と衝突するかを一つ一つ調べている(線形探索) 圧倒的に無駄が多い

  5. 衝突計算の効率化 • 現在の実装は全ての物体と衝突するかを一つ一つ調べている(線形探索) 大量のポリゴンに対応することができない

  6. 効率化手法 • Bounding Volume Hierarchy(BVH) • Kd-Tree

  7. BVH • 物体をBounding Volumeと呼ばれる枠で囲む • 衝突計算を行うときは、まず枠と衝突するか試す

  8. BVH 枠と衝突しないので中の物体は見ない

  9. BVH • 物体をBounding Volumeと呼ばれる枠で囲む • 衝突計算を行うときは、まず枠と衝突するか試す • さらにBounding VolumeをBounding Volumeで囲んで木構造にする

  10. BVH まず全体の枠と衝突計算をする

  11. BVH 中の枠と衝突計算をする

  12. BVH 最終的に枠の中で線形探索して衝突物体を得る

  13. BVHの木構造

  14. 枠の生成方法 • Axis Aligned Bounding Box(AABB)と呼ばれる長方形を枠として使うことが一 般的 • AABBとは各軸に平行な長方形のこと •

    中の物体の合計の大きさに合わせるようにする

  15. AABB

  16. BVHによる衝突計算の流れ 1. 物体集合からBVHを生成 2. まず全体の枠と衝突計算 3. 当たったら中の要素を衝突計算 4. 当たったらさらに中の要素を衝突計算 …

    5. 最終的な衝突物体を得る 再帰的な処理

  17. BVHの生成方法 • 中央分割法(Median Split) • 等数分割法(Equal Size Split) • Surface

    Area Heuristics(SAH) いずれも全体の枠の長さが最大となる軸を分割軸として選ぶ

  18. Median Split 中央値の位置で分割する

  19. 左右で物体の数が等しくなるところで分割する Equal Size Split

  20. SAHのコストが最も低くなるところで分割する SAH 50 10 40 30 45

  21. SAHコストの計算方法 = + + : 木の走査のコスト : 親の枠の表面積 , :

    子の枠の表面積 , : 子の枠に入っている物体数 :物体との衝突計算のコスト このコストが最小となる分割位置を選ぶ

  22. 比較 Equal Size Median SAH SAHが最も優れたBVHを生成できる