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
Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話 / Line drawin...
Search
sotanmochi
July 11, 2019
Programming
2
3.3k
Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話 / Line drawing algorithm using fragment shader
sotanmochi
July 11, 2019
Tweet
Share
More Decks by sotanmochi
See All by sotanmochi
URP/HDRPを使ったVRM対応アプリの開発方法 / VRM Importer Extension
sotanmochi
0
1.5k
Unityとゲームプログラムの基本的な構造について / Unity and Game Programming Basic Patterns
sotanmochi
0
710
画像処理から始めるコンピュートシェーダ / Introduction to Image Processing using Compute Shader
sotanmochi
2
2.2k
Diminished Reality 入門 / Introduction to Diminished Reality
sotanmochi
2
8.4k
MagicOnionでマルチプレイゲームを作ってみる / Introduction to developing multiplayer games using MagicOnion
sotanmochi
1
2.1k
SmartRig Bipedを使ってみよう / Introduction to SmartRig Biped
sotanmochi
0
2.9k
VRMを使ったAR/MR撮影ツールを試作開発してみた話 / Prototype of Mobile Mixed Capture
sotanmochi
0
1.5k
リアルとバーチャルの融合によって越えられない壁を壊す / TechCafe vol.8 LT
sotanmochi
0
230
ユニティちゃんと鬼ごっこができるMRゲームと戦術位置解析システム / Mixed reality game and tactical position analysis
sotanmochi
0
520
Other Decks in Programming
See All in Programming
EMになってからチームの成果を最大化するために取り組んだこと/ Maximize team performance as EM
nashiusagi
0
100
TypeScript Graph でコードレビューの心理的障壁を乗り越える
ysk8hori
3
1.2k
タクシーアプリ『GO』のリアルタイムデータ分析基盤における機械学習サービスの活用
mot_techtalk
4
1.5k
距離関数を極める! / SESSIONS 2024
gam0022
0
290
Jakarta EE meets AI
ivargrimstad
0
620
カンファレンスの「アレ」Webでなんとかしませんか? / Conference “thing” Why don't you do something about it on the Web?
dero1to
1
110
CSC509 Lecture 09
javiergs
PRO
0
140
Figma Dev Modeで変わる!Flutterの開発体験
watanave
0
150
PHP でアセンブリ言語のように書く技術
memory1994
PRO
1
170
CSC509 Lecture 12
javiergs
PRO
0
160
Hotwire or React? ~アフタートーク・本編に含めなかった話~ / Hotwire or React? after talk
harunatsujita
1
120
Generative AI Use Cases JP (略称:GenU)奮闘記
hideg
1
300
Featured
See All Featured
Why Our Code Smells
bkeepers
PRO
334
57k
Fantastic passwords and where to find them - at NoRuKo
philnash
50
2.9k
ReactJS: Keep Simple. Everything can be a component!
pedronauck
665
120k
Imperfection Machines: The Place of Print at Facebook
scottboms
265
13k
What's new in Ruby 2.0
geeforr
343
31k
The World Runs on Bad Software
bkeepers
PRO
65
11k
Large-scale JavaScript Application Architecture
addyosmani
510
110k
Practical Orchestrator
shlominoach
186
10k
StorybookのUI Testing Handbookを読んだ
zakiyama
27
5.3k
Designing on Purpose - Digital PM Summit 2013
jponch
115
7k
CSS Pre-Processors: Stylus, Less & Sass
bermonpainter
356
29k
Faster Mobile Websites
deanohume
305
30k
Transcript
Unityでテクスチャにお絵描きするための 線分描画アルゴリズムの話 2019/07 sotan (@sotanmochi)
はじめに 実装したアルゴリズムを忘れた時のための備忘録です 2 2019/07 Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話
線分描画アルゴリズムを理解すると何ができるのか? テクスチャにお絵描きする(線を描く)ことができる https://github.com/sotanmochi/SimpleDrawing-Unity 3 2019/07 Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話
一般的な線分描画アルゴリズム 始点から終点に向かって順次処理してピクセルを塗りつぶしていくアルゴリズム (ブレゼンハムのアルゴリズム(Bresenham's line algorithm)など) 4 2019/07 Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話
一般的な線分描画アルゴリズム 始点から終点に向かって順次処理してピクセルを塗りつぶしていくアルゴリズム → スクリプトで実装してCPUで順次処理 テクスチャ解像度が大きくなると計算負荷が増えてFPSが低下する(した) 5 2019/07 Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話
今回実装した線分描画アルゴリズム ピクセル単位で並列に処理して塗りつぶしていくアルゴリズム → シェーダーで実装してGPUで並列処理 GPUで高速に処理することでピクセル数が増えてもFPSを低下させない 6 2019/07 Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話
一般的な手法との比較 一般的な線分描画アルゴリズム 始点から終点に向かって順次処理してピクセルを塗りつぶしていくアルゴリズム → スクリプトで実装してCPUで順次処理 テクスチャ解像度が大きくなると計算負荷が増えてFPSが低下する(した) ※ 順次処理して塗りつぶしていく部分だけの負荷が高いのではなく、Texture2D.SetPixels32()や
Texture2D.Apply()の処理負荷も合わせるとFPSが低下すると考えられる 今回実装した線分描画アルゴリズム ピクセル単位で並列に処理して塗りつぶしていくアルゴリズム → シェーダーで実装してGPUで並列処理 GPUで高速に処理することでピクセル数が増えてもFPSを低下させない ※ 1ピクセルあたりの計算式は複雑になっているが、 GPUで並列処理することによって全体のスループットが向上する 7 2019/07 Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話
線分描画アルゴリズムの実装
実装の概要 大まかな流れは 1. オブジェクトに対して「線を描け」と命令する(スクリプト) 2. 色・UV座標などの値をシェーダーに渡してBlit命令を実行する(スクリプト) 3. シェーダーはUV座標などの情報から塗るべき位置を判断して色をつけていく といった感じ 9
2019/07 Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話
実装の概要 大まかな流れは 1. オブジェクトに対して「線を描け」と命令する(スクリプト) 2. 色・UV座標などの値をシェーダーに渡してBlit命令を実行する(スクリプト) 3. シェーダーはUV座標などの情報から塗るべき位置を判断して色をつけていく といった感じ 10
2019/07 Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話
線分描画アルゴリズム 以下の2つの条件を満たす点P(ピクセル)を塗りつぶす 条件1:点Pを直線ABに射影した点Qが線分ABに含まれる 条件2:点Pと直線ABの距離dが一定の値より小さい (描画する線の太さを表す値よりも距離dの方が小さい) 11 2019/07 Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話
条件1の判定方法(導出はAppendixを参照) 点Pを直線ABに射影した点Qが線分ABに含まれるかどうかを判定するためには、 以下の式(3)(4)(5)を用いてsとtの値を求めて、 次の条件 を満たすかどうかを判定すれば良い。 12 2019/07 Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話
条件1の実装例 13 2019/07 Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話
浮動小数点数(float)の比較 上記の条件を満たしているかを判定する時に、 Mathf.Approximatelyと同様の処理をシェーダーで実装する必要がある (2つの浮動小数点数の差が許容範囲内であれば同値とみなす処理) ※ 許容範囲の値を 1.0×10^-6 程度まで小さくして精度を高くすると、 塗りつぶせないピクセルが多くなってしまい上手く描画できなかった。
14 2019/07 Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話
条件2の判定方法(導出はAppendixを参照) 点Pと直線ABの距離dが一定の値より小さいことを判定するためには、 以下の式(9)を用いて距離dを求めればよい。 15 2019/07 Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話
条件2の実装例 16 2019/07 Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話
線分描画アルゴリズム 以下の2つの条件を満たす点P(ピクセル)を塗りつぶす 条件1:点Pを直線ABに射影した点Qが線分ABに含まれる 条件2:点Pと直線ABの距離dが一定の値より小さい (描画する線の太さを表す値よりも距離dの方が小さい) 17 2019/07 Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話
線分描画アルゴリズムの実装例 テクスチャにお絵描きする(線を描く)ことができる https://github.com/sotanmochi/SimpleDrawing-Unity 18 2019/07 Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話
まとめ
今回実装した線分描画アルゴリズム 以下の2つの条件を満たす点P(ピクセル)を塗りつぶす 条件1:点Pを直線ABに射影した点Qが線分ABに含まれる 条件2:点Pと直線ABの距離dが一定の値より小さい (描画する線の太さを表す値よりも距離dの方が小さい) 20 2019/07 Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話
一般的な手法との比較 一般的な線分描画アルゴリズム 始点から終点に向かって順次処理してピクセルを塗りつぶしていくアルゴリズム → スクリプトで実装してCPUで順次処理 テクスチャ解像度が大きくなると計算負荷が増えてFPSが低下する(した) ※ 順次処理して塗りつぶしていく部分だけの負荷が高いのではなく、Texture2D.SetPixels32()や
Texture2D.Apply()の処理負荷も合わせるとFPSが低下すると考えられる 今回実装した線分描画アルゴリズム ピクセル単位で並列に処理して塗りつぶしていくアルゴリズム → シェーダーで実装してGPUで並列処理 GPUで高速に処理することでピクセル数が増えてもFPSを低下させない ※ 1ピクセルあたりの計算式は複雑になっているが、 GPUで並列処理することによって全体のスループットが向上する 21 2019/07 Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話
おわりに データ並列で処理できるアルゴリズムに置き換えてシェーダーで実装することでパ フォーマンスを改善できた 今回はフラグメントシェーダー(ピクセルシェーダー)で実装するタイプの処理だったが、 描画系ではない(レンダリングパイプラインから切り離せる)処理を並列化する場合はコ ンピュートシェーダーを使うのがオススメ 22 2019/07 Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話
Appendix
Appendixについて 線分描画アルゴリズムの条件判定に使っている計算式を導出します 必要に応じて線形代数や高校数学の教科書を見てください ・ベクトル ・ベクトルと図形 ・行列式 ・連立1次方程式 など 24 2019/07
Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話
線分描画アルゴリズム 以下の2つの条件を満たす点P(ピクセル)を塗りつぶす 条件1:点Pを直線ABに射影した点Qが線分ABに含まれる 条件2:点Pと直線ABの距離dが一定の値より小さい (描画する線の太さを表す値よりも距離dの方が小さい) 25 2019/07 Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話
線分描画アルゴリズム 以下の2つの条件を満たす点P(ピクセル)を塗りつぶす 条件1:点Pを直線ABに射影した点Qが線分ABに含まれる 条件2:点Pと直線ABの距離dが一定の値より小さい (描画する線の太さを表す値よりも距離dの方が小さい) 26 2019/07 Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話
条件1の判定方法の導出 直線のベクトル方程式より直線AB上の任意の点xは と表される。 xが線分ABに含まれる場合は が成り立つ。 したがって、点Qが線分ABに含まれているか判定するためには、 を解いてsとtの値を求めて、(1)を満たすかどうかを判定すれば良い。 27 2019/07 Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話
条件1の判定方法の導出 2次元空間上の直線を考えるため、ベクトル方程式 に含まれる各ベクトルを とする。 はsとtを未知数とする連立方程式になっているため、 と表せる。 28 2019/07 Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話
条件1の判定方法の導出 連立方程式(2)の解は、クラメルの公式より次のように与えられる。 29 2019/07 Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話
条件1の判定方法の導出 点Pを直線ABに射影した点Qの位置ベクトルqは、 と表せる。 p’ は p - a を直線ABに正射影したベクトルなので、 正射影の公式より
したがって、 30 2019/07 Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話
条件1の判定方法 点Pを直線ABに射影した点Qが線分ABに含まれるかどうかを判定するためには、 以下の式(3)(4)(5)を用いてsとtの値を求めて、 次の条件 を満たすかどうかを判定すれば良い。 31 2019/07 Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話
線分描画アルゴリズム 以下の2つの条件を満たす点P(ピクセル)を塗りつぶす 条件1:点Pを直線ABに射影した点Qが線分ABに含まれる 条件2:点Pと直線ABの距離dが一定の値より小さい (描画する線の太さを表す値よりも距離dの方が小さい) 32 2019/07 Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話
線分描画アルゴリズム 以下の2つの条件を満たす点P(ピクセル)を塗りつぶす 条件1:点Pを直線ABに射影した点Qが線分ABに含まれる 条件2:点Pと直線ABの距離dが一定の値より小さい (描画する線の太さを表す値よりも距離dの方が小さい) 33 2019/07 Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話
条件2の判定方法の導出 点Pと直線ABの距離dの2乗は、ピタゴラスの定理より と表せる。 34 2019/07 Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話
条件2の判定方法の導出 p’ は p - a を直線ABに正射影したベクトルなので、 正射影の公式より よって、 35
2019/07 Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話
条件2の判定方法の導出 式(6)に式(7)を代入すると 36 2019/07 Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話
条件2の判定方法の導出 式(8)について とすると、 37 2019/07 Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話
条件2の判定方法の導出 ここで とすると なので、 上記の式を(8)に代入すると、 38 2019/07 Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話
条件2の判定方法 点Pと直線ABの距離dが一定の値より小さいことを判定するためには、 以下の式(9)を用いて距離dを求めればよい。 39 2019/07 Unityでテクスチャにお絵描きするための線分描画アルゴリズムの話
END