Basic Kd-tree Construction — Handmade Hero — Episode Guide

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: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

10:30Undo our changes to RayCast()

11:43Begin to make RayCast() use the FirstLeafIndex to permit overlapping rectangles

14:43Undo our changes to RayCast()

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

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

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

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

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()

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: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: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: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: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: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: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: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:41:15Run hhlightprof

🏃

1:41:15Run hhlightprof

🏃

1:41:15Run hhlightprof

🏃

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: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: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: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: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: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?

🏃

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