Handmade Hero»Episode Guide
Basic Kd-tree Construction
?
?

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 our Snuffleupagus oriented k-d tree implementation, and set the stage for the day
🗩
0:01Recap our Snuffleupagus oriented k-d tree implementation, and set the stage for the day
🗩
0:01Recap our Snuffleupagus oriented k-d tree implementation, and set the stage for the day
🗩
2:04Introduce SplitKd() to replace SplitBox()
2:04Introduce SplitKd() to replace SplitBox()
2:04Introduce SplitKd() to replace SplitBox()
2:52Determine to divide up the lighting box hierarchy the same as before
📖
2:52Determine to divide up the lighting box hierarchy the same as before
📖
2:52Determine to divide up the lighting box hierarchy the same as before
📖
3:54Note that the current splitting code allows overlapping rectangles
📖
3:54Note that the current splitting code allows overlapping rectangles
📖
3:54Note that the current splitting code allows overlapping rectangles
📖
8:03Begin to change RayCast() to handle overlapping rectangles
8:03Begin to change RayCast() to handle overlapping rectangles
8:03Begin to change RayCast() to handle overlapping rectangles
10:30Undo our changes to RayCast()
10:30Undo our changes to RayCast()
10:30Undo our changes to RayCast()
11:43Begin to make RayCast() use the FirstLeafIndex to permit overlapping rectangles
11:43Begin to make RayCast() use the FirstLeafIndex to permit overlapping rectangles
11:43Begin to make RayCast() use the FirstLeafIndex to permit overlapping rectangles
14:43Undo our changes to RayCast()
14:43Undo our changes to RayCast()
14:43Undo our changes to RayCast()
15:05Implement SplitKd() to split boxes in half along the k-d axis
15:05Implement SplitKd() to split boxes in half along the k-d axis
15:05Implement SplitKd() to split boxes in half along the k-d axis
32:35Consider packing the FirstLeafIndex, LeafCount and KdIndex into the Sides value
📖
32:35Consider packing the FirstLeafIndex, LeafCount and KdIndex into the Sides value
📖
32:35Consider packing the FirstLeafIndex, LeafCount and KdIndex into the Sides value
📖
33:54Make SplitKd() pack the FirstLeafIndex, LeafCount and KdIndex into the Sides value
33:54Make SplitKd() pack the FirstLeafIndex, LeafCount and KdIndex into the Sides value
33:54Make SplitKd() pack the FirstLeafIndex, LeafCount and KdIndex into the Sides value
38:37Permit SplitKd() to push U16Max KdNodes, and clean up compile errors
38:37Permit SplitKd() to push U16Max KdNodes, and clean up compile errors
38:37Permit SplitKd() to push U16Max KdNodes, and clean up compile errors
41:20Enable SplitKd() to perform the actual split, adding to both sides if we split down the middle
41:20Enable SplitKd() to perform the actual split, adding to both sides if we split down the middle
41:20Enable SplitKd() to perform the actual split, adding to both sides if we split down the middle
51:02Make BuildSpatialPartitionForLighting() call SplitKd(), defining a LIGHTING_USE_OLD_KD switch
51:02Make BuildSpatialPartitionForLighting() call SplitKd(), defining a LIGHTING_USE_OLD_KD switch
51:02Make BuildSpatialPartitionForLighting() call SplitKd(), defining a LIGHTING_USE_OLD_KD switch
53:50Run hhlightprof successfully with the old k-d way
🏃
53:50Run hhlightprof successfully with the old k-d way
🏃
53:50Run hhlightprof successfully with the old k-d way
🏃
54:17Toggle off LIGHTING_USE_OLD_KD and fix compile errors, augmenting lighting_solution with a RootKdValue
54:17Toggle off LIGHTING_USE_OLD_KD and fix compile errors, augmenting lighting_solution with a RootKdValue
54:17Toggle off LIGHTING_USE_OLD_KD and fix compile errors, augmenting lighting_solution with a RootKdValue
56:54Run hhlightprof and hit a read access violation
🏃
56:54Run hhlightprof and hit a read access violation
🏃
56:54Run hhlightprof and hit a read access violation
🏃
57:09Run hhlightprof and hit a read access violation on the KdNodes
🏃
57:09Run hhlightprof and hit a read access violation on the KdNodes
🏃
57:09Run hhlightprof and hit a read access violation on the KdNodes
🏃
57:26Make ProfileRun() allocate space for the KdNodes
57:26Make ProfileRun() allocate space for the KdNodes
57:26Make ProfileRun() allocate space for the KdNodes
58:29Run hhlightprof and apparently infinitely loop on SplitKd()
🏃
58:29Run hhlightprof and apparently infinitely loop on SplitKd()
🏃
58:29Run hhlightprof and apparently infinitely loop on SplitKd()
🏃
59:10Remove FirstLeafIndex, LeafCount and KdIndex from kd_tree_node, storing the KdIndex in the Sides value and introducing UNPACK_NEXT_KD_INDEX()
59:10Remove FirstLeafIndex, LeafCount and KdIndex from kd_tree_node, storing the KdIndex in the Sides value and introducing UNPACK_NEXT_KD_INDEX()
59:10Remove FirstLeafIndex, LeafCount and KdIndex from kd_tree_node, storing the KdIndex in the Sides value and introducing UNPACK_NEXT_KD_INDEX()
1:05:12Scour SplitKd() for bugs
📖
1:05:12Scour SplitKd() for bugs
📖
1:05:12Scour SplitKd() for bugs
📖
1:09:43Step through SplitKd() to our feedback loop situation, and inspect the values
🏃
1:09:43Step through SplitKd() to our feedback loop situation, and inspect the values
🏃
1:09:43Step through SplitKd() to our feedback loop situation, and inspect the values
🏃
1:12:36RemedyBG feature request: User-programmable data type watch summary / representation
🗹
1:12:36RemedyBG feature request: User-programmable data type watch summary / representation
🗹
1:12:36RemedyBG feature request: User-programmable data type watch summary / representation
🗹
1:18:38Again step through SplitKd() and inspect the BoxBounds
🏃
1:18:38Again step through SplitKd() and inspect the BoxBounds
🏃
1:18:38Again step through SplitKd() and inspect the BoxBounds
🏃
1:20:33Enable SplitKd() to handle non-split leaves
1:20:33Enable SplitKd() to handle non-split leaves
1:20:33Enable SplitKd() to handle non-split leaves
1:22:39Run hhlightprof without crashing
🏃
1:22:39Run hhlightprof without crashing
🏃
1:22:39Run hhlightprof without crashing
🏃
1:22:53Step through RayCast() and inspect its values, until hitting a write access violation
🏃
1:22:53Step through RayCast() and inspect its values, until hitting a write access violation
🏃
1:22:53Step through RayCast() and inspect its values, until hitting a write access violation
🏃
1:25:20Run hhlightprof without completing the first ray cast pass
🏃
1:25:20Run hhlightprof without completing the first ray cast pass
🏃
1:25:20Run hhlightprof without completing the first ray cast pass
🏃
1:26:13Again step through RayCast() and inspect its values
🏃
1:26:13Again step through RayCast() and inspect its values
🏃
1:26:13Again step through RayCast() and inspect its values
🏃
1:27:43Run hhlightprof in -O2 to completion of the first ray cast pass
🏃
1:27:43Run hhlightprof in -O2 to completion of the first ray cast pass
🏃
1:27:43Run hhlightprof in -O2 to completion of the first ray cast pass
🏃
1:29:11Switch to -Od and toggle on LIGHTING_USE_OLD_KD
1:29:11Switch to -Od and toggle on LIGHTING_USE_OLD_KD
1:29:11Switch to -Od and toggle on LIGHTING_USE_OLD_KD
1:29:24Run hhlightprof to completion
🏃
1:29:24Run hhlightprof to completion
🏃
1:29:24Run hhlightprof to completion
🏃
1:29:35Toggle off LIGHTING_USE_OLD_KD
1:29:35Toggle off LIGHTING_USE_OLD_KD
1:29:35Toggle off LIGHTING_USE_OLD_KD
1:29:45Scour RayCast() for bugs
📖
1:29:45Scour RayCast() for bugs
📖
1:29:45Scour RayCast() for bugs
📖
1:30:43Try restricting RayCast() to only traverse down the StartSide
1:30:43Try restricting RayCast() to only traverse down the StartSide
1:30:43Try restricting RayCast() to only traverse down the StartSide
1:31:04Run hhlightprof to (non-instant) completion
🏃
1:31:04Run hhlightprof to (non-instant) completion
🏃
1:31:04Run hhlightprof to (non-instant) completion
🏃
1:31:11Continue to scour RayCast() for bugs
📖
1:31:11Continue to scour RayCast() for bugs
📖
1:31:11Continue to scour RayCast() for bugs
📖
1:32:37Run hhlightprof in -O2
🏃
1:32:37Run hhlightprof in -O2
🏃
1:32:37Run hhlightprof in -O2
🏃
1:33:00Make RayCast() increment the TotalPartitionsTested before pushing on the StartSide
1:33:00Make RayCast() increment the TotalPartitionsTested before pushing on the StartSide
1:33:00Make RayCast() increment the TotalPartitionsTested before pushing on the StartSide
1:33:40Run hhlightprof in -O2
🏃
1:33:40Run hhlightprof in -O2
🏃
1:33:40Run hhlightprof in -O2
🏃
1:33:56Toggle on LIGHTING_USE_OLD_KD
1:33:56Toggle on LIGHTING_USE_OLD_KD
1:33:56Toggle on LIGHTING_USE_OLD_KD
1:34:08Run hhlightprof to find that the new k-d implementation tests many more leaves
🏃
1:34:08Run hhlightprof to find that the new k-d implementation tests many more leaves
🏃
1:34:08Run hhlightprof to find that the new k-d implementation tests many more leaves
🏃
1:34:53Toggle off LIGHTING_USE_OLD_KD
1:34:53Toggle off LIGHTING_USE_OLD_KD
1:34:53Toggle off LIGHTING_USE_OLD_KD
1:36:08Try making SplitKd() build a more usable k-d tree
1:36:08Try making SplitKd() build a more usable k-d tree
1:36:08Try making SplitKd() build a more usable k-d tree
1:38:15Run hhlightprof without completing
🏃
1:38:15Run hhlightprof without completing
🏃
1:38:15Run hhlightprof without completing
🏃
1:38:41Make ProfileRun() print out the KD Mode
1:38:41Make ProfileRun() print out the KD Mode
1:38:41Make ProfileRun() print out the KD Mode
1:41:15Run hhlightprof
🏃
1:41:15Run hhlightprof
🏃
1:41:15Run hhlightprof
🏃
1:41:21Toggle on LIGHTING_USE_OLD_KD
1:41:21Toggle on LIGHTING_USE_OLD_KD
1:41:21Toggle on LIGHTING_USE_OLD_KD
1:41:35Run hhlightprof to see that the new k-d implementation does not add many more leaves
🏃
1:41:35Run hhlightprof to see that the new k-d implementation does not add many more leaves
🏃
1:41:35Run hhlightprof to see that the new k-d implementation does not add many more leaves
🏃
1:41:49Scour RayCast() for bugs
📖
1:41:49Scour RayCast() for bugs
📖
1:41:49Scour RayCast() for bugs
📖
1:43:21Try preventing RayCast() from descending the tree
1:43:21Try preventing RayCast() from descending the tree
1:43:21Try preventing RayCast() from descending the tree
1:43:27Old k-d hhlightprof leaves tested: 496197
🏃
1:43:27Old k-d hhlightprof leaves tested: 496197
🏃
1:43:27Old k-d hhlightprof leaves tested: 496197
🏃
1:43:55Toggle off LIGHTING_USE_OLD_KD
1:43:55Toggle off LIGHTING_USE_OLD_KD
1:43:55Toggle off LIGHTING_USE_OLD_KD
1:44:09New k-d hhlightprof leaves tested: 5773056
🏃
1:44:09New k-d hhlightprof leaves tested: 5773056
🏃
1:44:09New k-d hhlightprof leaves tested: 5773056
🏃
1:45:10Step through RayCast() in -Od to find 32 unsplit leaves
🏃
1:45:10Step through RayCast() in -Od to find 32 unsplit leaves
🏃
1:45:10Step through RayCast() in -Od to find 32 unsplit leaves
🏃
1:46:24Scour SplitKd() for bugs
📖
1:46:24Scour SplitKd() for bugs
📖
1:46:24Scour SplitKd() for bugs
📖
1:50:14Try making SplitKd() split boxes that are on the PlaneD
1:50:14Try making SplitKd() split boxes that are on the PlaneD
1:50:14Try making SplitKd() split boxes that are on the PlaneD
1:51:02Step through SplitKd() to find that almost all boxes straddle the centre of the bounds
🏃
1:51:02Step through SplitKd() to find that almost all boxes straddle the centre of the bounds
🏃
1:51:02Step through SplitKd() to find that almost all boxes straddle the centre of the bounds
🏃
1:53:09Scour BuildSpatialPartitionForLighting() and SplitKd() for bugs
📖
1:53:09Scour BuildSpatialPartitionForLighting() and SplitKd() for bugs
📖
1:53:09Scour BuildSpatialPartitionForLighting() and SplitKd() for bugs
📖
1:55:11Step through SplitKd() to find a 35 unit long box
🏃
1:55:11Step through SplitKd() to find a 35 unit long box
🏃
1:55:11Step through SplitKd() to find a 35 unit long box
🏃
1:56:17Scour ProfileRun() for bugs in transforming the box bounds
📖
1:56:17Scour ProfileRun() for bugs in transforming the box bounds
📖
1:56:17Scour ProfileRun() for bugs in transforming the box bounds
📖
1:57:22Continue to step through SplitKd() to find identical BoxMax values for all boxes
🏃
1:57:22Continue to step through SplitKd() to find identical BoxMax values for all boxes
🏃
1:57:22Continue to step through SplitKd() to find identical BoxMax values for all boxes
🏃
1:58:25Step through the box bounds transformation in ProfileRun(), and on to SplitKd()
🏃
1:58:25Step through the box bounds transformation in ProfileRun(), and on to SplitKd()
🏃
1:58:25Step through the box bounds transformation in ProfileRun(), and on to SplitKd()
🏃
2:01:48Realise we incorrectly index into the Box, thanks to RemedyBG
🏃
2:01:48Realise we incorrectly index into the Box, thanks to RemedyBG
🏃
2:01:48Realise we incorrectly index into the Box, thanks to RemedyBG
🏃
2:02:56Fix SplitKd() to index into the Box using DimIndex rather than KdIndex
2:02:56Fix SplitKd() to index into the Box using DimIndex rather than KdIndex
2:02:56Fix SplitKd() to index into the Box using DimIndex rather than KdIndex
2:03:19Run hhlightprof in -Od
🏃
2:03:19Run hhlightprof in -Od
🏃
2:03:19Run hhlightprof in -Od
🏃
2:03:44-O2 k-d hhlightprof leaves tested: 375920
🏃
2:03:44-O2 k-d hhlightprof leaves tested: 375920
🏃
2:03:44-O2 k-d hhlightprof leaves tested: 375920
🏃
2:04:18Let RayCast() traverse the whole tree
2:04:18Let RayCast() traverse the whole tree
2:04:18Let RayCast() traverse the whole tree
2:04:32Run hhlightprof until… the heat death of the universe?
🏃
2:04:32Run hhlightprof until… the heat death of the universe?
🏃
2:04:32Run hhlightprof until… the heat death of the universe?
🏃