Jump to Content
Register
Forgot your password?
Third-party login
Log in with Discord

Handmade Hero
Forums
Episode Guide
twitter
Handmade Hero»Episode Guide
Testing Better Entropy
References ▼
Melissa E. O'Neill
PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation
[1]38:49[5]1:00:52[6]1:11:25
[8]1:22:46
Wolfram MathWorld
Sphere Point Picking
[2]50:33[3]53:10
Wikipedia
George Marsaglia
[4]53:10
PCG, A Better Random Number Generator
Download the PCG Library
[7]1:11:25
Pierre L'Ecuyer
Tables of linear congruential generators of different sizes and good lattice structure
[9]1:22:46
Wikipedia
Linear congruential generator
[10]1:30:08
Filter mode:
Topics
debug visualisation
lighting
prng
rendering
statistics
(null topic)
Media
🖌Blackboard
🗪Chat Comment
🏃In-Game
🖮Programming🟉
💢Rant
📖Research
🗩Speech
🎭
🏟
🔗
Link to: current timestamp
Credits
Host
Casey Muratori
Indexer
Matt Mascarenhas
?
?

Keyboard Navigation

Global Keys

[, < / ], > Jump to previous / next episode
W, K, P / S, J, N Jump to previous / next marker
t / T Toggle theatre / SUPERtheatre mode
V Revert filter to original state Y Select link (requires manual Ctrl-c)

Menu toggling

q Quotes r References f Filter y Link c Credits

In-Menu Movement

a
w
s
d
h j k l
←
↑
↓
→

Quotes and References Menus

Enter Jump to timecode

Quotes, References and Credits Menus

o Open URL (in new tab)

Filter Menu

x, Space Toggle category and focus next
X, ShiftSpace Toggle category and focus previous
v Invert topics / media as per focus

Filter and Link Menus

z Toggle filter / linking mode

Credits Menu

Enter Open URL (in new tab)
0:01Recap and set the stage for the day
🗩
0:01Recap and set the stage for the day
🗩
0:01Recap and set the stage for the day
🗩
0:49Hemisphere Integration
🖌
0:49Hemisphere Integration
🖌
0:49Hemisphere Integration
🖌
12:38Our light reception function
🖌
12:38Our light reception function
🖌
12:38Our light reception function
🖌
17:09Weighted sampling, as a way to optimise out the multiplication of a weighting coefficient
🖌
17:09Weighted sampling, as a way to optimise out the multiplication of a weighting coefficient
🖌
17:09Weighted sampling, as a way to optimise out the multiplication of a weighting coefficient
🖌
29:18Writing the bias into the sampling equation
🖌
29:18Writing the bias into the sampling equation
🖌
29:18Writing the bias into the sampling equation
🖌
33:10Review GenerateLightingPattern() from last stream
📖
33:10Review GenerateLightingPattern() from last stream
📖
33:10Review GenerateLightingPattern() from last stream
📖
33:59Make GenerateLightingPattern() take a much greater number of samples, to try and see if it converges
33:59Make GenerateLightingPattern() take a much greater number of samples, to try and see if it converges
33:59Make GenerateLightingPattern() take a much greater number of samples, to try and see if it converges
34:50Run the game to see that it takes too long to compute
🏃
34:50Run the game to see that it takes too long to compute
🏃
34:50Run the game to see that it takes too long to compute
🏃
35:56Make GenerateLightingPattern() take not quite that many samples
35:56Make GenerateLightingPattern() take not quite that many samples
35:56Make GenerateLightingPattern() take not quite that many samples
36:10Step in to GenerateLightingPattern() and inspect the test averages
🏃
36:10Step in to GenerateLightingPattern() and inspect the test averages
🏃
36:10Step in to GenerateLightingPattern() and inspect the test averages
🏃
36:49Make GenerateLightingPattern() perform fewer tests and take more samples
36:49Make GenerateLightingPattern() perform fewer tests and take more samples
36:49Make GenerateLightingPattern() perform fewer tests and take more samples
37:12Step in to GenerateLightingPattern() and inspect the test averages
🏃
37:12Step in to GenerateLightingPattern() and inspect the test averages
🏃
37:12Step in to GenerateLightingPattern() and inspect the test averages
🏃
37:23Further increase the sample count and lower the test count in GenerateLightingPattern()
37:23Further increase the sample count and lower the test count in GenerateLightingPattern()
37:23Further increase the sample count and lower the test count in GenerateLightingPattern()
37:48Step in to GenerateLightingPattern() and inspect the test averages
🏃
37:48Step in to GenerateLightingPattern() and inspect the test averages
🏃
37:48Step in to GenerateLightingPattern() and inspect the test averages
🏃
38:00Increase the test count in GenerateLightingPattern()
38:00Increase the test count in GenerateLightingPattern()
38:00Increase the test count in GenerateLightingPattern()
38:16Step in to GenerateLightingPattern() and inspect the test averages, to find that we are starting to converge
🏃
38:16Step in to GenerateLightingPattern() and inspect the test averages, to find that we are starting to converge
🏃
38:16Step in to GenerateLightingPattern() and inspect the test averages, to find that we are starting to converge
🏃
38:49Consider replacing xorshift with PCG, specifically its notion of k-Dimensional Equidistribution1
📖
38:49Consider replacing xorshift with PCG, specifically its notion of k-Dimensional Equidistribution1
📖
38:49Consider replacing xorshift with PCG, specifically its notion of k-Dimensional Equidistribution1
📖
44:46Determine to plot our random sampling points
🗩
44:46Determine to plot our random sampling points
🗩
44:46Determine to plot our random sampling points
🗩
46:20Run the game to see our sample points
🏃
46:20Run the game to see our sample points
🏃
46:20Run the game to see our sample points
🏃
46:37Enable LightingTest() to draw a random set of sampling points
46:37Enable LightingTest() to draw a random set of sampling points
46:37Enable LightingTest() to draw a random set of sampling points
49:41Run the game to see our random sample points
🏃
49:41Run the game to see our random sample points
🏃
49:41Run the game to see our random sample points
🏃
50:33Research sphere point picking2
📖
50:33Research sphere point picking2
📖
50:33Research sphere point picking2
📖
53:10Implement Marsaglia's method for uniform point picking on a sphere3,4
53:10Implement Marsaglia's method for uniform point picking on a sphere3,4
53:10Implement Marsaglia's method for uniform point picking on a sphere3,4
56:38Run the game to check out Marsaglia's sampling
🏃
56:38Run the game to check out Marsaglia's sampling
🏃
56:38Run the game to check out Marsaglia's sampling
🏃
57:12Toggle between Marsaglia's method and our full random sampling in LightingTest()
57:12Toggle between Marsaglia's method and our full random sampling in LightingTest()
57:12Toggle between Marsaglia's method and our full random sampling in LightingTest()
58:04Run the game to check out the two sampling patterns
🏃
58:04Run the game to check out the two sampling patterns
🏃
58:04Run the game to check out the two sampling patterns
🏃
58:47Modify Marsaglia's method in LightingTest() to sample only the upper hemisphere
58:47Modify Marsaglia's method in LightingTest() to sample only the upper hemisphere
58:47Modify Marsaglia's method in LightingTest() to sample only the upper hemisphere
59:52Run the game to check out the two hemisphere sampling patterns
🏃
59:52Run the game to check out the two hemisphere sampling patterns
🏃
59:52Run the game to check out the two hemisphere sampling patterns
🏃
1:00:52Introduce random_series_pcg and versions of RandomNextU32(), RandomUnilateral() and RandomBilateral() that take this struct5
1:00:52Introduce random_series_pcg and versions of RandomNextU32(), RandomUnilateral() and RandomBilateral() that take this struct5
1:00:52Introduce random_series_pcg and versions of RandomNextU32(), RandomUnilateral() and RandomBilateral() that take this struct5
1:10:40Praise the compiler for figuring out that we'd never pass the check in Marsaglia's sampling routine, thus raising the "unreachable code" warning
1:10:40Praise the compiler for figuring out that we'd never pass the check in Marsaglia's sampling routine, thus raising the "unreachable code" warning
1:10:40Praise the compiler for figuring out that we'd never pass the check in Marsaglia's sampling routine, thus raising the "unreachable code" warning
1:11:25Determine to enable the random_series_pcg version of RandomNextU32() to perform xorshift6,7
📖
1:11:25Determine to enable the random_series_pcg version of RandomNextU32() to perform xorshift6,7
📖
1:11:25Determine to enable the random_series_pcg version of RandomNextU32() to perform xorshift6,7
📖
1:19:36Try to check out the example PCG code, but encounter a hang in File Explorer when clicking "New"
💢
1:19:36Try to check out the example PCG code, but encounter a hang in File Explorer when clicking "New"
💢
1:19:36Try to check out the example PCG code, but encounter a hang in File Explorer when clicking "New"
💢
1:22:46Read through pcg_basic.c in conjunction with Melissa E. O'Neill's PCG paper8 and Pierre L'Ecuyer's 'Tables of linear congruential generators'9 with a view to understanding why the example code uses rng->inc or'd with 1 in the LCG update step
📖
1:22:46Read through pcg_basic.c in conjunction with Melissa E. O'Neill's PCG paper8 and Pierre L'Ecuyer's 'Tables of linear congruential generators'9 with a view to understanding why the example code uses rng->inc or'd with 1 in the LCG update step
📖
1:22:46Read through pcg_basic.c in conjunction with Melissa E. O'Neill's PCG paper8 and Pierre L'Ecuyer's 'Tables of linear congruential generators'9 with a view to understanding why the example code uses rng->inc or'd with 1 in the LCG update step
📖
1:30:08Consult Wikipedia's article 'Linear congruential generator'10 to discover that O'Neill must be using Knuth's LCG style
📖
1:30:08Consult Wikipedia's article 'Linear congruential generator'10 to discover that O'Neill must be using Knuth's LCG style
📖
1:30:08Consult Wikipedia's article 'Linear congruential generator'10 to discover that O'Neill must be using Knuth's LCG style
📖
1:32:28Enable the random_series_pcg version of RandomNextU32() to perform the LCG update step, augmenting random_series_pcg to contain a Selector
1:32:28Enable the random_series_pcg version of RandomNextU32() to perform the LCG update step, augmenting random_series_pcg to contain a Selector
1:32:28Enable the random_series_pcg version of RandomNextU32() to perform the LCG update step, augmenting random_series_pcg to contain a Selector
1:35:02Introduce RandomSeedPCG() for LightingTest() to use
1:35:02Introduce RandomSeedPCG() for LightingTest() to use
1:35:02Introduce RandomSeedPCG() for LightingTest() to use
1:37:01Run the game to see if we get any better random results
🏃
1:37:01Run the game to see if we get any better random results
🏃
1:37:01Run the game to see if we get any better random results
🏃
1:38:05Fix RandomNextU32() to correctly cast the entire PreRotate computation
1:38:05Fix RandomNextU32() to correctly cast the entire PreRotate computation
1:38:05Fix RandomNextU32() to correctly cast the entire PreRotate computation
1:38:31Run the game to compare the PCG and Xorshift random sampling patterns
🏃
1:38:31Run the game to compare the PCG and Xorshift random sampling patterns
🏃
1:38:31Run the game to compare the PCG and Xorshift random sampling patterns
🏃
1:39:23Make LightingTest() use a different random series for each axis
1:39:23Make LightingTest() use a different random series for each axis
1:39:23Make LightingTest() use a different random series for each axis
1:41:22Run the game to determine that the non-PCG random sampling looks fine
🏃
1:41:22Run the game to determine that the non-PCG random sampling looks fine
🏃
1:41:22Run the game to determine that the non-PCG random sampling looks fine
🏃
1:42:21Q&A
🗩
1:42:21Q&A
🗩
1:42:21Q&A
🗩
1:43:02lokathor Q: You can't have an even number as the Selector because then the 1s-bit would never flip and your period would get cut down a few orders of magnitude. The paper goes over that at some point if I recall correctly
🗪
1:43:02lokathor Q: You can't have an even number as the Selector because then the 1s-bit would never flip and your period would get cut down a few orders of magnitude. The paper goes over that at some point if I recall correctly
🗪
1:43:02lokathor Q: You can't have an even number as the Selector because then the 1s-bit would never flip and your period would get cut down a few orders of magnitude. The paper goes over that at some point if I recall correctly
🗪
1:43:30vaualbus Q: In the random series when you write the state part there is a bug: it should be (incr << 1) | 1
🗪
1:43:30vaualbus Q: In the random series when you write the state part there is a bug: it should be (incr << 1) | 1
🗪
1:43:30vaualbus Q: In the random series when you write the state part there is a bug: it should be (incr << 1) | 1
🗪
1:43:36Fix RandomSeedPCG() to correctly shift the Selector
1:43:36Fix RandomSeedPCG() to correctly shift the Selector
1:43:36Fix RandomSeedPCG() to correctly shift the Selector
1:43:56Run the game to see no significant difference
🏃
1:43:56Run the game to see no significant difference
🏃
1:43:56Run the game to see no significant difference
🏃
1:45:15lokathor Q: The basic PCG32 you're using will only be k-dimensionally equidistributed for simple (u32,u32) tuples. Each u32 will appear 2^32 times within the 2^64 period. You'll need PCG64 or an extension array if you want k-d equi for v3 or more. However, it probably doesn't actually matter for your v3 generation case here, because you're unlikely to actually see the generator loop around. Even at one v3 generated per nanosecond (extremely generous), it'd take ~195 years to see a loop
🗪
1:45:15lokathor Q: The basic PCG32 you're using will only be k-dimensionally equidistributed for simple (u32,u32) tuples. Each u32 will appear 2^32 times within the 2^64 period. You'll need PCG64 or an extension array if you want k-d equi for v3 or more. However, it probably doesn't actually matter for your v3 generation case here, because you're unlikely to actually see the generator loop around. Even at one v3 generated per nanosecond (extremely generous), it'd take ~195 years to see a loop
🗪
1:45:15lokathor Q: The basic PCG32 you're using will only be k-dimensionally equidistributed for simple (u32,u32) tuples. Each u32 will appear 2^32 times within the 2^64 period. You'll need PCG64 or an extension array if you want k-d equi for v3 or more. However, it probably doesn't actually matter for your v3 generation case here, because you're unlikely to actually see the generator loop around. Even at one v3 generated per nanosecond (extremely generous), it'd take ~195 years to see a loop
🗪
1:45:51thejimjames40 Q: What is your opinion on event systems? And how would you implement one?
🗪
1:45:51thejimjames40 Q: What is your opinion on event systems? And how would you implement one?
🗪
1:45:51thejimjames40 Q: What is your opinion on event systems? And how would you implement one?
🗪
1:46:43lifeam1 Q: Is there a way that a slack channel can be set up that way us newbies can catch up and have a place to ask questions as I am finding it hard to keep up with the earlier videos without a lot of side researching
🗪
1:46:43lifeam1 Q: Is there a way that a slack channel can be set up that way us newbies can catch up and have a place to ask questions as I am finding it hard to keep up with the earlier videos without a lot of side researching
🗪
1:46:43lifeam1 Q: Is there a way that a slack channel can be set up that way us newbies can catch up and have a place to ask questions as I am finding it hard to keep up with the earlier videos without a lot of side researching
🗪
1:47:21postalrat Q: What are sampling and for what? Missed out on that part
🗪
1:47:21postalrat Q: What are sampling and for what? Missed out on that part
🗪
1:47:21postalrat Q: What are sampling and for what? Missed out on that part
🗪
1:47:53internal_static_void_ Q: So why opt for a PCG or LCG generator rather than just hashing the time for a random number?
🗪
1:47:53internal_static_void_ Q: So why opt for a PCG or LCG generator rather than just hashing the time for a random number?
🗪
1:47:53internal_static_void_ Q: So why opt for a PCG or LCG generator rather than just hashing the time for a random number?
🗪
1:49:17thejimjames40 handmade_hero An event system for communication between interacting systems
🗪
1:49:17thejimjames40 handmade_hero An event system for communication between interacting systems
🗪
1:49:17thejimjames40 handmade_hero An event system for communication between interacting systems
🗪
1:49:50schoenhs Q: In Monte Carlo estimates usually error scales like 1/sqrt(samples). For 1024 samples one expects error of order 0.03 and for 65k one expects error of order 0.003. It therefore seems like the error you're seeing is pretty reasonable, or am I misunderstanding?
🗪
1:49:50schoenhs Q: In Monte Carlo estimates usually error scales like 1/sqrt(samples). For 1024 samples one expects error of order 0.03 and for 65k one expects error of order 0.003. It therefore seems like the error you're seeing is pretty reasonable, or am I misunderstanding?
🗪
1:49:50schoenhs Q: In Monte Carlo estimates usually error scales like 1/sqrt(samples). For 1024 samples one expects error of order 0.03 and for 65k one expects error of order 0.003. It therefore seems like the error you're seeing is pretty reasonable, or am I misunderstanding?
🗪
1:50:22mindrage Q: What would you consider the most performant RNG despite the accuracy?
🗪
1:50:22mindrage Q: What would you consider the most performant RNG despite the accuracy?
🗪
1:50:22mindrage Q: What would you consider the most performant RNG despite the accuracy?
🗪
1:51:11bigmofo1 Q: What will you work on tomorrow?
🗪
1:51:11bigmofo1 Q: What will you work on tomorrow?
🗪
1:51:11bigmofo1 Q: What will you work on tomorrow?
🗪
1:52:15Generating blue noise cos(𝜃) distributed sampling points on a disc, for projection up to its hemisphere
🖌
1:52:15Generating blue noise cos(𝜃) distributed sampling points on a disc, for projection up to its hemisphere
🖌
1:52:15Generating blue noise cos(𝜃) distributed sampling points on a disc, for projection up to its hemisphere
🖌
1:57:30staythirsty90 Q: Can I see the current state of the lighting / game?
🗪
1:57:30staythirsty90 Q: Can I see the current state of the lighting / game?
🗪
1:57:30staythirsty90 Q: Can I see the current state of the lighting / game?
🗪
1:57:37Show the lighting in the game
🏃
1:57:37Show the lighting in the game
🏃
1:57:37Show the lighting in the game
🏃
1:59:04jamoflaw Q: Is there an intention to support shadows from the point lights?
🗪
1:59:04jamoflaw Q: Is there an intention to support shadows from the point lights?
🗪
1:59:04jamoflaw Q: Is there an intention to support shadows from the point lights?
🗪
1:59:56staythirsty90 Q: Will there be any raymarching / volumetric fluid stuff?
🗪
1:59:56staythirsty90 Q: Will there be any raymarching / volumetric fluid stuff?
🗪
1:59:56staythirsty90 Q: Will there be any raymarching / volumetric fluid stuff?
🗪
2:00:21We are out of questions
🗩
2:00:21We are out of questions
🗩
2:00:21We are out of questions
🗩