= Assignment 2 Lazy KD-Tree = == Bill Dwyer == == Date submitted: 26 Apr 2006 (ish) == == Code emailed: 26 Apr 2006 == === Description of implementation approach and comments === I relied heavily on the given implementation of the Kd Tree and basically made modifications to the existing code instead of starting from scratch. The PBRT book was incredibly helpful in understanding how the regular Kd Tree was implemented. It was also very clear that the regular Kd Tree was HIGHLY optimized. For example, all the nodes were allocated in aligned memory to make it faster when caching. However, since Lazy Kd Trees are built incrementally, it is not possible to rely on this optimization since nodes can be built in an arbitrary order (to some extent). After understanding the original Kd Tree layout, I basically modified the node structure to contain the arguments that would normally be passed down through recursion, so that they could be accessed at a later time (i.e. when the interection is calculated). I only classify a node (interior or leaf) when it is called for by the intersection algorithm. After classification, two unclassified children are attached, and their arguments are initialized. In the end, the speed up of the Lazy Kd Tree is good for interesting edge cases. However, if you don't intend to ray-trace large amounts of the scene, it seems silly to have the geometry in there to begin with. For example, if we're only rendering the scene of killaroos from behind a wall, why even bother loading the killaroo geometry in the first place? === Final Images Rendered with my implementation of heightfield.cpp === '''killeroos-view1.pbrt (Killeroos visible)''' attachment:killeroos-view1.png || || KD Tree || Lazy KD Tree || Ratio || ||build time (secs) || 20.0s || 4.2s || 21.0% || ||total time (secs) || 40.5s || 100s || 247% || ||Num of nodes made || 2.752M || 837.9K || 30.4% || || Triangle ray intersections || 673.3k:4690.5k (14.35%) || 644.2k:10534.5k (6.11%) || 98.7%:224% (42.6%) || "killeroos-view2.pbrt (Killeroos invisible)" attachment:killeroos-view2.png || || KD Tree || Lazy KD Tree || Ratio || ||build time (secs) || 21.0s || 4.7s || 22.3% || ||total time (secs) || 37.7s || 27.9s || 74.0% || ||Num of nodes made || 2.752M || 82 || 0.00298% || || Triangle ray intersections || 758.4k:2148.2k (35.30%) || 758.4k:2148.2k (35.30%) || 100%:100% (100%)|| "killeroos-view3.pbrt (close-up)" attachment:killeroos-view3.png || || KD Tree || Lazy KD Tree || Ratio || ||build time (secs) || 20.2s || 4.7s || 23.3% || ||total time (secs) || 41.6s || 47.9 || 115% || ||Num of nodes made || 2.752M || 229.9k || 8.35% || || Triangle ray intersections || 644.2k:10534.5k (6.11%) || 758.4k:2148.2k (35.30%) || 118%:20.4% (578%)|| "plants-view1.pbrt" attachment:plants-view1.png || || KD Tree || Lazy KD Tree || Ratio || ||build time (secs) || 22.1s* || 1.7s* || 7.69% || ||total time (secs) || 816s || 1619s || 198% || ||Num of nodes made || 14.866M || 6.581M || 44% || || Triangle ray intersections || 20.257M:421.737M (4.80%) || 20.257M:421.737M (4.80%) || 100%:100% (100%)|| "plants-view2.pbrt" attachment:plants-view2.png || || KD Tree || Lazy KD Tree || Ratio || ||build time (secs) || 21.0s* || 1.3s* || 6.19% || ||total time (secs) || 1465s || 2152s || 147% || ||Num of nodes made || 14.866M || 7.991M || 54.0% || || Triangle ray intersections || 25.930M:754.291M (3.44%) || 25.930M:754.291M (3.44%) || 100%:100% (100%)|| omg, the last render took forever! * this data was abnormal (there were many 100% progress bars presented after the intial readout of this final time so it might not be entirely accurate).