Sketching Out A K-d Tree Loop — Handmade Hero — Episode Guide

0:00Welcome to the stream with a plug of the Meow the Infinite printed comic Kickstarter¹

🗩

0:00Welcome to the stream with a plug of the Meow the Infinite printed comic Kickstarter¹

🗩

0:00Welcome to the stream with a plug of the Meow the Infinite printed comic Kickstarter¹

🗩

0:57Show RayCast() with the determination to use our ray cast hits as a k-d tree

📖

0:57Show RayCast() with the determination to use our ray cast hits as a k-d tree

📖

0:57Show RayCast() with the determination to use our ray cast hits as a k-d tree

📖

1:37Demo hhlightprof (6.538543 total seconds elapsed)

🏃

1:37Demo hhlightprof (6.538543 total seconds elapsed)

🏃

1:37Demo hhlightprof (6.538543 total seconds elapsed)

🏃

2:50Print out the number of partitions and leaves tested over repeated runs

6:14hhlightprof tested 229860 partitions, and 524241 leaves

🏃

6:14hhlightprof tested 229860 partitions, and 524241 leaves

🏃

6:14hhlightprof tested 229860 partitions, and 524241 leaves

🏃

6:27Always print out the number of partition and leaves tested, including the single-run case

6:44hhlightprof tested 2338596 partitions, and 524285 leaves

🏃

6:44hhlightprof tested 2338596 partitions, and 524285 leaves

🏃

6:44hhlightprof tested 2338596 partitions, and 524285 leaves

🏃

6:53Revert hhlightprof to print the number of partitions and leaves tested in the multiple-run case

7:03Print partitions per leaf

8:32hhlightprof tested 2339860 partitions and 524241 leaves, at 4.46 partitions per leaf

🏃

8:32hhlightprof tested 2339860 partitions and 524241 leaves, at 4.46 partitions per leaf

🏃

8:32hhlightprof tested 2339860 partitions and 524241 leaves, at 4.46 partitions per leaf

🏃

8:55Print total partitions plus leaves

9:35hhlightprof tested 2864101 total boxes, 2339860 partitions and 524241 leaves, at 4.46 partitions per leaf

🏃

9:35hhlightprof tested 2864101 total boxes, 2339860 partitions and 524241 leaves, at 4.46 partitions per leaf

🏃

9:35hhlightprof tested 2864101 total boxes, 2339860 partitions and 524241 leaves, at 4.46 partitions per leaf

🏃

11:25Determine to make a special-purpose design for the k-d tree

🗩

11:25Determine to make a special-purpose design for the k-d tree

🗩

11:25Determine to make a special-purpose design for the k-d tree

🗩

13:19Check the day²^,3

📖

13:19Check the day²^,3

📖

13:19Check the day²^,3

📖

14:19k-d Tree

🖌

14:19k-d Tree

🖌

14:19k-d Tree

🖌

19:37Embark on k-d tree-style categorisation in RayCast()

22:35Doing a dot-product using a known +/− value⁴

📖

22:35Doing a dot-product using a known +/− value⁴

📖

22:35Doing a dot-product using a known +/− value⁴

📖

24:56Initialise our desired data for k-d tree-style categorisation in RayCast()

32:23Our menu of operations: 1) Push both boxes; 2) Push one box; 3) Push no boxes

📖

32:23Our menu of operations: 1) Push both boxes; 2) Push one box; 3) Push no boxes

📖

32:23Our menu of operations: 1) Push both boxes; 2) Push one box; 3) Push no boxes

📖

33:06Pushing no boxes

🖌

33:06Pushing no boxes

🖌

33:06Pushing no boxes

🖌

34:29Set up RayCast() to push onto our BoxStack the boxes on the close side and, optionally, the far side

37:38Consider the resource-usage implications of four rays sharing the same origin

📖

37:38Consider the resource-usage implications of four rays sharing the same origin

📖

37:38Consider the resource-usage implications of four rays sharing the same origin

📖

46:38Determine to use SIMD lanes suboptimally for now, then read the literature on k-d trees to inform any improvements

📖

46:38Determine to use SIMD lanes suboptimally for now, then read the literature on k-d trees to inform any improvements

📖

46:38Determine to use SIMD lanes suboptimally for now, then read the literature on k-d trees to inform any improvements

📖

47:31Make RayCast() push the boxes onto our BoxStack

57:52Consider how to classify the EndSide in terms of signedness

📖

57:52Consider how to classify the EndSide in terms of signedness

📖

57:52Consider how to classify the EndSide in terms of signedness

📖

1:03:04Work through the EndSide classification, XOR'ing the sides into a mask

1:06:46Consider restructuring the box categorisation loop

📖

1:06:46Consider restructuring the box categorisation loop

📖

1:06:46Consider restructuring the box categorisation loop

📖

1:07:30Restructure the box categorisation loop such that a box pulled off the stack is always known to be on the far side

1:12:22Set up to take a timing

1:13:03hhlightprof total seconds elapsed: 6.362055

🏃

1:13:03hhlightprof total seconds elapsed: 6.362055

🏃

1:13:03hhlightprof total seconds elapsed: 6.362055

🏃

1:13:35Restructure the ray hit testing loop within the categorisation loop, to avoid unnecessary box pushes

1:18:13hhlightprof total seconds elapsed: 6.110083

🏃

1:18:13hhlightprof total seconds elapsed: 6.110083

🏃

1:18:13hhlightprof total seconds elapsed: 6.110083

🏃

1:18:41Remove stale code from RayCast()

1:19:41Continue to work through the box categorisation routine

1:21:53hhlightprof total seconds elapsed: 6.173270

🏃

1:21:53hhlightprof total seconds elapsed: 6.173270

🏃

1:21:53hhlightprof total seconds elapsed: 6.173270

🏃

1:22:11Print out the Expected ms

1:23:00hhlightprof expected ms: 50.74

🏃

1:23:00hhlightprof expected ms: 50.74

🏃

1:23:00hhlightprof expected ms: 50.74

🏃

1:23:44Print out the Expected ms / thread

1:24:16hhlightprof expected ms / thread: 8.49

🏃

1:24:16hhlightprof expected ms / thread: 8.49

🏃

1:24:16hhlightprof expected ms / thread: 8.49

🏃

1:24:51Undefine HANDMADE_INTERNAL and HANDMADE_SLOW

1:25:07hhlightprof expected ms / thread: 8.51

🏃

1:25:07hhlightprof expected ms / thread: 8.51

🏃

1:25:07hhlightprof expected ms / thread: 8.51

🏃

1:25:15Run the game

🏃

1:25:15Run the game

🏃

1:25:15Run the game

🏃

1:26:06Run the game in Nsight: 21 ms / frame

🏃

1:26:06Run the game in Nsight: 21 ms / frame

🏃

1:26:06Run the game in Nsight: 21 ms / frame

🏃

1:27:53Check our frame profile in Nsight

🏃

1:27:53Check our frame profile in Nsight

🏃

1:27:53Check our frame profile in Nsight

🏃

1:29:08Decrease our resolution from 1920×1080 to 480×270

1:29:43Run the game

🏃

1:29:43Run the game

🏃

1:29:43Run the game

🏃

1:30:15Run the game in Nsight: 21 ms / frame

🏃

1:30:15Run the game in Nsight: 21 ms / frame

🏃

1:30:15Run the game in Nsight: 21 ms / frame

🏃

1:31:06Increase our resolution from 480×270 to 1920×1080

1:31:13Disable the lighting in EndLightingComputation()

1:31:49Run the game

🏃

1:31:49Run the game

🏃

1:31:49Run the game

🏃

1:32:09Run the game in Nsight: 16.67 ms / frame

🏃

1:32:09Run the game in Nsight: 16.67 ms / frame

🏃

1:32:09Run the game in Nsight: 16.67 ms / frame

🏃

1:32:36Re-enable the lighting in EndLightingComputation()

1:32:42Make ComputeLightPropagationWork() compute the lighting for only every other tile

1:34:16Run the game in Nsight: 16.67 ms / frame

🏃

1:34:16Run the game in Nsight: 16.67 ms / frame

🏃

1:34:16Run the game in Nsight: 16.67 ms / frame

🏃

1:35:24Revert ComputeLightPropagationWork() to compute the lighting for every tile

1:35:32Continue work on structuring our categorisation loop for better k-d processing

1:44:24Our menu of split cases

🖌

1:44:24Our menu of split cases

🖌

1:44:24Our menu of split cases

🖌

1:47:01Complete our categorisation and ray hit testing loops for better k-d processing

2:03:40Reflect on our k-d tree-based RayCast()

🗩

2:03:40Reflect on our k-d tree-based RayCast()

🗩

2:03:40Reflect on our k-d tree-based RayCast()

🗩

2:04:26Q&A

🗩

2:04:26Q&A

🗩

2:04:26Q&A

🗩

2:05:02insobot Q: Groovy?

🗪

2:05:02insobot Q: Groovy?

🗪

2:05:02insobot Q: Groovy?

🗪

2:05:35nulligor Q: Is this PHP?

🗪

2:05:35nulligor Q: Is this PHP?

🗪

2:05:35nulligor Q: Is this PHP?

🗪

2:05:56ablindorphan Q: Is there a good way to get intuitions about bit masks etc, or is it just practice?⁵

🗪

2:05:56ablindorphan Q: Is there a good way to get intuitions about bit masks etc, or is it just practice?⁵

🗪

2:05:56ablindorphan Q: Is there a good way to get intuitions about bit masks etc, or is it just practice?⁵

🗪

2:07:12Fix our usage of _mm_movemask_ps() in the StartSideBit and EndSideBit initialisers

2:07:30Describe _mm_movemask_ps⁶

📖

2:07:30Describe _mm_movemask_ps⁶

📖

2:07:30Describe _mm_movemask_ps⁶

📖

2:08:54read_my_code Q: Do you write shader code often for work?

🗪

2:08:54read_my_code Q: Do you write shader code often for work?

🗪

2:08:54read_my_code Q: Do you write shader code often for work?

🗪

2:09:27alexkelbo Q: Do you sometimes feel the urge to make Handmade Hero truly 3D?

🗪

2:09:27alexkelbo Q: Do you sometimes feel the urge to make Handmade Hero truly 3D?

🗪

2:09:27alexkelbo Q: Do you sometimes feel the urge to make Handmade Hero truly 3D?

🗪

2:10:49read_my_code Your asset pipeline becomes Unreal Engine 4

🗪

2:10:49read_my_code Your asset pipeline becomes Unreal Engine 4

🗪

2:10:49read_my_code Your asset pipeline becomes Unreal Engine 4

🗪

2:12:15ymm0 Q: I'm bit behind on the VoDs. Do you ever trace secondary rays that bounce off in random directions that might lead to incoherent ray packets? (You mentioned the ray origins are always the same)

🗪

2:12:15ymm0 Q: I'm bit behind on the VoDs. Do you ever trace secondary rays that bounce off in random directions that might lead to incoherent ray packets? (You mentioned the ray origins are always the same)

🗪

2:12:15ymm0 Q: I'm bit behind on the VoDs. Do you ever trace secondary rays that bounce off in random directions that might lead to incoherent ray packets? (You mentioned the ray origins are always the same)

🗪

2:13:36uplinkcoder Q: Can't C++11 use something like 0b1111⁷

🗪

2:13:36uplinkcoder Q: Can't C++11 use something like 0b1111⁷

🗪

2:13:36uplinkcoder Q: Can't C++11 use something like 0b1111⁷

🗪

2:15:49sneiderlein Q: In an IMGUI situation, how do you create a unique ID for a UI control? What I don't get is, if you draw everything immediately, if some condition changes, won't the ID also change?

🗪

2:15:49sneiderlein Q: In an IMGUI situation, how do you create a unique ID for a UI control? What I don't get is, if you draw everything immediately, if some condition changes, won't the ID also change?

🗪

2:15:49sneiderlein Q: In an IMGUI situation, how do you create a unique ID for a UI control? What I don't get is, if you draw everything immediately, if some condition changes, won't the ID also change?

🗪

2:16:39mjt_au Q: Has Handmade Hero gone as you planned, or did you not have any expectations or scope when you set off on this journey?

🗪

2:16:39mjt_au Q: Has Handmade Hero gone as you planned, or did you not have any expectations or scope when you set off on this journey?

🗪

2:16:39mjt_au Q: Has Handmade Hero gone as you planned, or did you not have any expectations or scope when you set off on this journey?

🗪

2:17:02nulligor Q: How many % is Handmade Hero done?

🗪

2:17:02nulligor Q: How many % is Handmade Hero done?

🗪

2:17:02nulligor Q: How many % is Handmade Hero done?

🗪

2:17:45i_simian Q: Would you consider moving Handmade Hero to JAI when it releases, or perhaps have another project to help showcase the language? I assume it'd be something that would at least interest you

🗪

2:17:45i_simian Q: Would you consider moving Handmade Hero to JAI when it releases, or perhaps have another project to help showcase the language? I assume it'd be something that would at least interest you

🗪

2:17:45i_simian Q: Would you consider moving Handmade Hero to JAI when it releases, or perhaps have another project to help showcase the language? I assume it'd be something that would at least interest you

🗪

2:18:24Wrap it up with a plug of the Meow the Infinite printed comic Kickstarter⁸

🗩

2:18:24Wrap it up with a plug of the Meow the Infinite printed comic Kickstarter⁸

🗩

2:18:24Wrap it up with a plug of the Meow the Infinite printed comic Kickstarter⁸

🗩

Keyboard Navigation

Global Keys

Menu toggling

In-Menu and Index Controls

Quotes and References Menus and Index

Quotes, References and Credits Menus

Filter Menu

Filter and Link Menus

Credits Menu