= Assignment 2 Lazy KD-Tree = == Murad Akhter == == Date submitted: 28 Apr 2006 == == Code emailed: 28 Apr 2006 == === Description of implementation approach and comments === I had a late start on the assignment since I was off campus for a few days, nonetheless with late days I was able to get a reasonbly good solution. I used a lot of the suggestions mentioned in the book and the assignment handout. === Datastructures === I kept the nodes 8 bytes by taking the least significant bit of the aboveChild union to signify lazy nodes & stored a pointer there to access data needed for lazy node evaluation. This data had all the additional information like the set of primitives, depth, node number, badRefines etc. I built the tree with 1 root node and two empty lazy nodes that had the leaf flags set. While splitting these lazy nodes I would always create both children so that I could store them one after the other in the nodes array and not have to store an additional child pointer/reference. I also moved all the tree variables I had to modify into a mutable struct that I could then modify without worrying about const issues === Implementation === I thought about merging Intersection & IntersectionP since they shared all but 3 lines of code but ended up keeping them separate so I wouldn't have to add additional checks to call the appropriate primitive intersection routines. I had some fun time seeing things blow up whenever my nodes array was reallocated since the todo array would end up with invalid pointers after the reallocs. I ended up storing node offsets instead. === 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) || 15.8 || 0.0 || 0.0% || ||total time (secs) || 29.989 || 29.13 || 97% || ||Num of nodes made || 2.752M || 1.357M || 49.29% || || Triangle ray intersections || 673.2k || 827.7k || 122.95%|| "killeroos-view2.pbrt (Killeroos invisible)" attachment:killeroos-view2.png || || KD Tree || Lazy KD Tree || Ratio || ||build time (secs) || 16.5 || 0.0 || 0.0% || ||total time (secs) || 27.554 || 14.53 || 52.73% || ||Num of nodes made || 2.752M || 18 || 0.00065% || || Triangle ray intersections || 758.4k || 776.1k || 102.33%|| "killeroos-view3.pbrt (close-up)" attachment:killeroos-view3.png || || KD Tree || Lazy KD Tree || Ratio || ||build time (secs) || 16.7 || 0.0 || 0.0% || ||total time (secs) || 30.943 || 22.7 || 73.36% || ||Num of nodes made || 2.752M || 373.3k || 13.56% || || Triangle ray intersections || 644.1k || 1.018M || 158.05%|| "plants-view1.pbrt" attachment:plants-view1.png || || KD Tree || Lazy KD Tree || Ratio || ||build time (secs) || 41.2 || __ || __% || ||total time (secs) || 721.281 || __ || __% || ||Num of nodes made || 14.884M || __ || __% || || Triangle ray intersections || 20.295M || __ || __%|| "plants-view2.pbrt" attachment:plants-view2.png || || KD Tree || Lazy KD Tree || Ratio || ||build time (secs) || 47.7 || || __% || ||total time (secs) ||1192.75 || __ || __% || ||Num of nodes made || 14.884M || __ || __% || || Triangle ray intersections || 25.902M || __ || __%||