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)

"killeroos-view2.pbrt (Killeroos invisible)"

"killeroos-view3.pbrt (close-up)"

"plants-view1.pbrt"

"plants-view2.pbrt"