モンテカルロレイトレーシング：アルゴリズム超概略 / Super Simple Overview of Monte Carlo Ray Tracing Algorithms

MONTE CARLO RAY TRACING! ΞϧΰϦζϜ௒ུ֓ ౉෦৺! Twitter: @Shocker_0x15! ϨΠτϨ߹॓ https://sites.google.com/site/raytracingcamp2/

ϞϯςΧϧϩੵ෼

I = f (x)dx a b ∫ I ≈ 1
N f (xi ) p(xi ) i=1 N ∑ ਪఆ஋͸෼ࢄΛ࣋ͭ! ظ଴஋͸ਅ஋ʹҰக͢Δ ϞϯςΧϧϩਪఆؔ਺

f (x) x a b p(x) x a b I
≈ 1 N f (xi ) p(xi ) i=1 N ∑ ೚ҙͷ1%'͕࢖༻Մೳ

I ≈ 1 N f (xi ) p(xi ) i=1
N ∑ ॏ఺తαϯϓϦϯά f (x) x a b p(x) f (x) x a b p(x) ଎͍ऩଋ(௿෼ࢄ) ஗͍ऩଋ(ߴ෼ࢄ) ཧ૝తͳPDFΛٻΊΔ͜ͱ͸ࠔ೉

άϩʔόϧΠϧϛωʔγϣϯ Χϝϥʗ؟ ޫݯ Χϝϥʹ౸ୡ͢Δ͋ΒΏΔޫܦ࿏ͷد༩Λੵ෼͢Δ I = f (x)dµ(x) Ω ∫

Χϝϥʗ؟ ޫݯ ܦ࿏ I ≈ 1 N f (xi )
p(xi ) i=1 N ∑ f (xi ): ܦ࿏ʹԊͬͨد༩ xi : ϥϯμϜͳܦ࿏ ϞϯςΧϧϩੵ෼Λ࢖ͬͯղ͘ p(x i ): ϥϯμϜͳܦ࿏Λੜ੒͢ΔPDF

PATH TRACING

ೖࣹํ޲Λ֬཰తʹαϯϓϧɺޫݯʹ౰ͨΕ͹د༩͕ͱΕΔ ࢹ఺͔Βޫ༌ૹܦ࿏ΛτϨʔε ͳ͔ͳ͔౰ͨΒͳ͍ʂ

NEXT EVENT ESTIMATION ޫݯ্ͷ఺Λ໌ࣔతʹαϯϓϧɺࢹઢܦ࿏ͱ઀ଓ͢Δ

MULTIPLE IMPORTANCE SAMPLING  ྫɿ௚઀র໌ͷਪఆ

Light ޫ୔BSDF I ≈ 1 N f (xBSDF, i )
pBSDF (xBSDF, i ) i=1 N ∑ #4%'ͷد༩ʹԊͬͨॏ఺తαϯϓϦϯά #4%'د༩ʹԊͬͯೖࣹํ޲αϯϓϧɿߴ͍֬཰Ͱߴ͍د༩ à௿͍෼ࢄ ޫݯ͕ྑ͍৔ॴʹ͋Ε͹

Light ֦ࢄBSDF I ≈ 1 N f (xBSDF, i )
pBSDF (xBSDF, i ) i=1 N ∑ #4%'ͷد༩ʹԊͬͨॏ఺తαϯϓϦϯά #4%'د༩ʹԊͬͯೖࣹํ޲αϯϓϧɿ௿͍֬཰Ͱߴ͍د༩ àߴ͍෼ࢄ ͨ·ʹ͔͠౰ͨΒͳ͍ͨΊ

Light ֦ࢄBSDF I ≈ 1 N f (x light, i
) p light (x light, i ) i=1 N ∑ ޫݯ্ͷҐஔͷॏ఺తαϯϓϦϯά ޫݯ্ͷҐஔΛαϯϓϧͯ͠઀ଓɿߴ͍֬཰Ͱߴ͍د༩ à௿͍෼ࢄ #4%'ͷ஋͕ൺֱతҰ༷Ͱ͋Ε͹

Light ޫ୔BSDF I ≈ 1 N f (x light, i
) p light (x light, i ) i=1 N ∑ ޫݯ্ͷҐஔͷॏ఺తαϯϓϦϯά ޫݯ্ͷҐஔΛαϯϓϧͯ͠઀ଓɿ௿͍֬཰Ͱߴ͍د༩ àߴ͍෼ࢄ #4%'ͷ஋͕ඇҰ༷ͳͨΊ

ޫݯ໘ͷαϯϓϦϯά #4%'ͷαϯϓϦϯά

Multiple Importance Sampling I ≈ 1 N f (xBSDF, i
) pBSDF (xBSDF, i ) i=1 N ∑ I ≈ 1 N f (xlight, i ) plight (xlight, i ) i=1 N ∑ I ≈ 1 N wBSDF (xBSDF, i ) f (xBSDF, i ) pBSDF (xBSDF, i ) + wlight (xlight, i ) f (xlight, i ) plight (xlight, i ) " # $ % & ' i=1 N ∑

w BSDF (x) = p BSDF (x) p BSDF (x)+
p light (x) wlight (x) = plight (x) pBSDF (x)+ plight (x) I ≈ 1 N wBSDF (xBSDF, i ) f (xBSDF, i ) pBSDF (xBSDF, i ) + wlight (xlight, i ) f (xlight, i ) plight (xlight, i ) " # $ % & ' i=1 N ∑ .*4΢ΣΠτ όϥϯεώϡʔϦεςΟοΫ

.*4ʹΑΔ΢ΣΠτ഑෼ .VMUJQMF*NQPSUBODF4BNQMJOH

BIDIRECTIONAL PATH TRACING! VEACH-STYLE

.*4ΛҰൠԽ 15ʹ͓͚Δ ௚઀র໌ͷ৔߹ʜ ೚ҙͷܦ࿏ʹҰൠԽʂ

ࢹઢαϒύεͱޫݯαϒύεΛੜ੒ɺ֤௖఺Λ઀ଓ

(2,2) (3,1) (1,3) ྫ௕͞ MIS ˎ
΋͋ΓಘΔ

#JEJSFDUJPOBM1BUI5SBDJOH 1BUI5SBDJOH ؒ઀র໌͕ࢧ഑తͳγʔϯʹ͓͍ͯ΋ϩόετ

METROPOLIS LIGHT TRANSPORT

௨ৗͷ.$35ͷ໰୊఺ ྫɿ1BUI5SBDJOH ͘͝Ұ෦ͷྖҬͷޫ༌ૹܦ࿏͕ॏཁͱͳΔγʔϯʹऑ͍! ྫɿগ͚ͩ͠։͍ͨυΞ͔Β࿙ΕΔޫɺίʔεςΟΫε͕ओཁͳޫݯ ຖճϥϯμϜʹܦ࿏ΛτϨʔεɿ໓ଟʹد༩͕ͱΕͳ͍ʂʂ!

ޫ༌ૹ΁ͷϝτϩϙϦεαϯϓϦϯάͷద༻ طଘͷ༗ޮͳύε΁มҟΛՃ͑ͯ৽ͨͳύεΛੜ੒! د༩͕খ͘͞ͳΔมҟ͸֬཰తʹغ٫͞ΕΔ

ޫ༌ૹ΁ͷϝτϩϙϦεαϯϓϦϯάͷద༻ طଘͷ༗ޮͳύε΁มҟΛՃ͑ͯ৽ͨͳύεΛੜ੒! د༩͕খ͘͞ͳΔมҟ͸֬཰తʹغ٫͞ΕΔ د༩àغ٫

ޫ༌ૹ΁ͷϝτϩϙϦεαϯϓϦϯάͷద༻ طଘͷ༗ޮͳύε΁มҟΛՃ͑ͯ৽ͨͳύεΛੜ੒! د༩͕খ͘͞ͳΔมҟ͸֬཰తʹغ٫͞ΕΔ ݩͷܦ࿏ʹ໭͢

Bidirectional Path Tracing

Metropolis Light Transport

PRIMARY SAMPLE SPACE MLT

n࣍ݩͷ0 ~ 1ཚ਺! 㱨 Primary Sample Space n࣍ݩ௒ཱํମ 0 1
0 1 ܦ࿏ͷૉʹͳΔཚ਺ϨϕϧͰมҟΛՃ͑Δ 144ͷ࠲ඪͱܦ࿏͸ ҰରҰରԠ 15΍#15ʹΑΔϚοϐϯά ΦϦδφϧ.-5ΑΓ࣮૷͕؆୯͔ͭϩόετ ͱظ଴͞ΕΔ

PHOTON MAPPING

ϑΥτϯτϨʔγϯά

ϑΥτϯτϨʔγϯά ີ౓ਪఆ

ϑΥτϯτϨʔγϯά ີ౓ਪఆ ϑΥτϯϚοϐϯά͸ܦ࿏ΛΏΔ͘઀ଓ͢Δ͜ͱʹΑͬͯ! ܦ࿏Λ࠶ར༻ɺଟ༷ͳܦ࿏Λ·ͱΊͯܭࢉ

PROGRESSIVE PHOTON MAPPING

ϑΥτϯϚοϐϯάͷ໰୊఺ ਖ਼֬ͳً౓ਪఆʹ͸  ແݶখͷ୳ࡧ൒ܘʹແݶݸͷϑΥτϯͱ͍͏৚͕݅ඞཁ ϝϞϦ΍ܭࢉίετ໘ͰෆՄೳʂ

PROGRESSIVE PHOTON MAPPING : PPM ϑΥτϯτϨʔγϯάΛ܁Γฦͯ͠౷ܭྔΛߋ৽ ͋Β͔͡Ίً౓ܭࢉ఺Λੜ੒͓ͯ͘͠ ౷ܭߋ৽ˍ൒ܘॖݮ

ແݶখͷ൒ܘʹແݶݸͷϑΥτϯͱ͍͏৚݅ʹ  ϓϩάϨογϒʹۙͮ͘ ϑΥτϯͷ୳ࡧ൒ܘΛ൓෮͝ͱʹॖݮ ൒ܘॖݮʗ౷ܭྔͷߋ৽

STOCHASTIC PPM

11.ͷ໰୊఺ ޫ୔൓ࣹ ΞϯνΤΠϦΞε Ϟʔγϣϯϒϥʔ ඃࣸքਂ౓ ͜ΕΒͷޮՌ͸ฏۉ์ًࣹ౓ਪఆΛඞཁͱ͢Δ ਖ਼֬ͳਪఆʹ͸ແݶͷً౓ਪఆ఺͕ඞཁ ྫɿΞϯνΤΠϦΞε ɹɹϐΫηϧ಺ͷαϯϓϧ఺ ྫɿඃࣸքਂ౓
ɹɹϨϯζ্ͷαϯϓϧ఺

SPPM ྖҬ಺Ͱ୳ࡧ൒ܘͳͲͷ౷ܭྔΛڞ༗ ޫ୔൓ࣹ ൓ࣹํ޲ ΞϯνΤΠϦΞε ϐΫηϧ Ϟʔγϣϯϒϥʔ γϟολʔ࣌ؒத ඃࣸքਂ౓ Ϩϯζ্
શͯΛ·ͱΊΔ͜ͱͰ ฏۉً౓ͷਪఆ஋ΛϓϩάϨογϒʹਅ஋ʹ͚ۙͮΒΕΔ

ً౓ܭଌ఺΋ຖճ࡞Γ௚͢ ϐΫηϧதͷҐஔ΍ɺϨϯζ্ͷҐஔɺ࣌ؒɺޫ୔൓ࣹํ޲ ͳͲΛຖճมߋ͢Δ ڞ༗౷ܭߋ৽ˍ൒ܘॖݮ

Bidirectional Path Tracing

Progressive Photon Mapping

Stochastic PPM

PPM: PROBABILISTIC APPROACH

411.ͷҰൠԽΛ͞Βʹਪ͠ਐΊͨख๏ ൒ܘΛঃʑʹখ͍ͯͬͨ͘͞͠ ΦϦδφϧͷϑΥτϯϚοϐϯάͷ݁ՌΛॏͶ߹ΘͤΔ͚ͩʂ ൒ܘॖݮ

ADAPTIVE ! MARKOV CHAIN MONTE CARLO! PPM

11. 411. ͷ໰୊఺ ՄࢹྖҬ ෆՄࢹͳϑΥτϯܦ࿏  ʹແବͳܭࢉ ༗ޮͳϑΥτϯܦ࿏

AMCMCPPM = PPM + PSSMLT + α ॳظͷՄࢹܦ࿏

AMCMCPPM = PPM + PSSMLT + α ॳظͷՄࢹܦ࿏ ෆՄࢹà غ٫

AMCMCPPM = PPM + PSSMLT + α ॳظͷՄࢹܦ࿏

AMCMCPPM = PPM + PSSMLT + α ॳظͷՄࢹܦ࿏ Մࢹà ࠾୒

AMCMCPPM = PPM + PSSMLT + α

AMCMCPPM = PPM + PSSMLT + α Primary Sample Space 
தͷมҟΛ༻͍ͯ  ܦ࿏Λੜ੒

AMCMCPPM = PPM + PSSMLT + α Primary Sample Space 
தͷมҟΛ༻͍ͯ  ܦ࿏Λੜ੒ มҟύϥϝλʔͷ ࣗಈௐ੔΋ߦ͏౳ આ໌ল͖·͢ + α

".$.$11. 411.

SPPM AMCMCPPM ஫໨ྖҬ͕૬ରతʹখ͘͞ͳΔ΄Ͳ11.͸ഁ୼͢Δ .$.$ͱύϥϝλʔͷࣗಈௐ੔ʹΑΓ ".$.$11.͸શͯͷഒ཰Ͱ༏Εͨ݁Ռ

UNIFIED PATH SAMPLING! (VERTEX CONNECTION AND MERGING)

BPT ޫ୔໘ͷଟ͍γʔϯಘҙ 4%4ύεۤख PPM ޫ୔໘ͷଟ͍γʔϯۤख 4%4ύεಘҙ .*4 ͔͠͠໰୊͕͋Δ ྫɿ௕͞ͷܦ࿏ߏங BPT
ܦ࿏ͷ࣍ݩ : A5 PPM ܦ࿏ͷ࣍ݩ : A6 ܦ࿏ߏஙͷ ࣍ݩ͕ҟͳΔ

wBSDF (x) = pBSDF (x) pBSDF (x)+ plight (x) MIS΢ΣΠτͷܭࢉʹPDFͷՃࢉΛؚΉ
࣍ݩͷҟͳΔྔͷՃࢉ͸ޚ๏౓ ࠶ܝɿόϥϯεώϡʔϦεςΟοΫ

BPT ܦ࿏ͷ࣍ݩ : A5 ֦ுBPT ܦ࿏ͷ࣍ݩ : A6 Vertex Perturbation
ࢹઢύεͷ୺఺ΛͣΒͯ͠ޫઢύεͷ୺఺Λ௥Ճ  Ծ૝తʹPPMͱ࣍ݩΛ߹ΘͤΔ

֦ு#15ͱ11.ͷ.*4

BATHROOM Bidirectional Path Tracing

BATHROOM Progressive Photon Mapping

BATHROOM Uniﬁed Path Sampling

PATH SPACE REGULARIZATION

Specular BRDF Molliﬁed BRDF BSDF MOLLIFICATION #4%'Λ؇࿨ͯ͠د༩ΛऔΕΔΑ͏ʹ ͨͩ͠CJBTFE ൓෮͝ͱʹຊདྷͷ#4%'΁͚͍ۙͮͯ͘
ʹຊ࣭తʹ͸11.ͷ൒ܘॖݮͱಉ͡ σΟϑϡʔζ໘ʹ͸ద༻͠ͳ͍àඞཁ࠷௿ݶͷόΠΞε

Original MLT

AMCMCPPM

VCM(UPS)

Regularized MLT

Regularized MLT + ME

MULTIPLEXED MLT

144.-5Ͱ͸ͭͷఏҊ෼෍ͱ࠾୒ɾغ٫Λ૊Έ߹Θͤͯ ໨ඪ෼෍ ܦ࿏ͷը૾΁ͷد༩ Λୡ੒͢Δ ఏҊ෼෍ɿ #15౳ʹΑΔͭͷϚοϐϯά #15౳Ͱ࣮ݱ͞ΕΔϚοϐϯά ఏҊ෼෍ ͕͋·Γྑ͘ͳ͍ àغ٫͕૿͑Δ

ఏҊ෼෍ɿ ෳ਺ͷϚοϐϯάͷࠞ߹ 144಺ͷมҟʹՃ͑ͯϚοϐϯάͷมߋ΋ߦ͏ PRIMARY SPACE SERIAL TEMPERING

PSSMLT

Original MLT

Multiplexed MLT

͓ΘΓʹ ຊεϥΠυͰ৮Εͨͷ͸਺͋Δख๏ͷҰ෦ ϘϦϡʔϜϨϯμϦϯάʹؔͯ͠͸Ұ੾৮Εͯͳ͍ Energy Redistribution Path Tracing / Bidirectional Photon
Mapping / ! Manifold Exploration Path Tracing / Replica Exchange Light Transport / ! Population Monte Carlo - ER / Noise Aware MLT / ! Bidirectional Light Cuts / Gradient-domain MLT … ࠷৽ख๏͸جຊతʹ.*4BOEPS 144 .-5 ͷཧ࿦࢖͍ͬͯΔΠϝʔδ

REFERENCES 1/3 n  [ERPT] CLINE, D., TALBOT, J., AND EGBERT,
P. 2005. Energy redistribution path tracing. ACM Trans. Graph. (SIGGRAPH Proceedings) 24, 3, 1186–1195.! n  [VCM] GEORGIEV, I., KŘIVÁNEK, J., AND SLUSALLEK, P. 2011. Bidirectional light transport with vertex merging. In ACM SIGGRAPH Asia 2011 Sketches, 27:1–27:2.! n  [SPPM] HACHISUKA, T., AND JENSEN, H. W. 2009. Stochastic progressive photon mapping. In ACM SIGGRAPH Asia Papers. ACM, New York, 1–8.! n  [AMCMCPPM] HACHISUKA, T., AND JENSEN, H. W. 2011. Robust adaptive photon tracing using photon path visibility. ACM Transaction on Graphics 30 (October), 114:1–114:11.! n  [MMLT] HACHISUKA, T., KAPLANYAN, A. S., AND DACHSBACHER, C. 2014. Multiplexed Metropolis light transport. ACM Trans. Graph. (Proc. of SIGGRAPH 2014) 33, 4.! n  [PPM] HACHISUKA, T., OGAKI, S., AND JENSEN, H. W. 2008. Progressive photon mapping. ACM Trans. Graph. (Proc. of SIGGRAPH Asia) 27, 5.! n  [UPS] HACHISUKA, T., PANTALEONI, J., AND JENSEN, H. W. 2012. A path space extension for robust light transport simulation. ACM Trans. Graph. (Proc. of SIGGRAPH Asia) 31, 6 (Nov.).! n  [Noise Aware MLT] HOBEROCK, J., AND HART, J. C. 2010. Arbitrary importance functions for Metropolis light transport. Comput. Graph. Forum 29, 6, 1993–2003.! n  [MEPT] JAKOB, W., AND MARSCHNER, S. 2012. Manifold exploration: a Markov chain Monte Carlo technique for rendering scenes with difﬁcult specular transport. ACM Transactions on Graphics (Proc. SIGGRAPH) 31, 4, 58:1–58:13.!

REFERENCES 2/3 n  [PM] JENSEN, H. W. 1996. Global illumination
using photon maps. In Proceedings of the Eurographics Workshop on Rendering Techniques ’96, Springer-Verlag, London, UK, 21–30.! n  [PT] KAJIYA, J. T. 1986. The rendering equation. In Computer Graphics (Proc. of SIGGRAPH).! n  [Regularization] KAPLANYAN, A. S., AND DACHSBACHER, C. 2013. Path space regularization for holistic and robust light transport. Computer Graphics Forum (Proc. of Eurographics) 32, 2.! n  [PSSMLT] KELEMEN, C., SZIRMAY-KALOS, L., ANTAL, G., AND CSONKA, F. 2002. A simple and robust mutation strategy for the metropolis light transport algorithm. In Eurographics 2002, vol. 21, 531–540.! n  [RELT] KITAOKA, S., KITAMURA, Y., AND KISHINO, F. 2009. Replica exchange light transport. Computer Graphics Forum 28, 8, 2330–2342.! n  [PPPM] KNAUS, C., AND ZWICKER, M. 2011. Progressive photon mapping: A probabilistic approach. ACM Transaction on Graphics 30 (May), 25:1–25:13.! n  [PMC-ER] LAI, Y.-C., FAN, S. H., CHENNEY, S., AND DYER, C. 2007. Photorealistic image rendering with population Monte Carlo energy redistribution. In In Rendering Techniques 2007 (Proceedings of the Eurographics Symposium on Rendering), 287–295.! n  [Gradient-domain MLT] LEHTINEN, J., KARRAS, T., LAINE, S., AITTALA, M., DURAND, F., AND AILA, T. 2013. Gradient-domain Metropolis light transport. ACM Transactions on Graphics (Proc. SIGGRAPH) 32, 4.! n  [MIS, BPT] VEACH, E. 1997. Robust Monte Carlo methods for light transport simulation. PhD thesis, Stanford, CA, USA.!

REFERENCES 3/3 n  [BPM] VORBA, J. 2011. Bidirectional photon mapping.
In Proc. of the Central European Seminar on Computer Graphics (CESCG ‘11).! n  [BLC] WALTER, B., KHUNGURN, P., AND BALA, K. 2012. Bidirectional lightcuts. ACM Transactions on Graphics (Proc. SIGGRAPH) 31, 4, 59:1–59:11.!

モンテカルロレイトレーシング：アルゴリズム超概略 / Super Simple Overvie...

モンテカルロレイトレーシング：アルゴリズム超概略 / Super Simple Overview of Monte Carlo Ray Tracing Algorithms

More Decks by shocker_0x15

Other Decks in Technology

Featured

Transcript