• PaulTarjan
• Assignment2

Assignment 2 Lazy KD-Tree

Paul Tarjan

Date submitted: 26 Apr 2006

Code emailed: 26 Apr 2006

Description of implementation approach and comments

I first fixed IntersectP to just call Intersect. Then I added the NULL test in Intersect to call Intersect on the subchild if isect is NULL. This made the code feel better and was easier to extend.

bool KdTreeAccel::IntersectP(const Ray &ray) const {

• return Intersect(ray, NULL);

}

I implemented this twice. The first time, I fullyRefined the primitives right at the start, trying to use some of my build cost so that I don't have to do it later. I didn't realize that some of the nodes might not have to be refinedm and I am wasting cycles (and memory) copying them between lazy nodes. I also added the bounding box, the depth, and a boat load of other data into the node. The numbers you see below are for this implementation.

I then reduced the size of the node class by 12 bytes (from 56 to 44) and noticed a preformance DECREASE. It was due to all the fancy things I was doing to store the data in unused bits and all the math that had to be done to undo the fancy things. I didn't submit this code.

Now, I did something that doesn't fully refine at the begining. It just refines as you go. If you just do this optomization to the non-lazy kdTree, you get from about 63 seconds to 56 seconds for the kangaroo-view1. This moves all the time from the build to the run too. I couldn't get this to work with my implementation of lazy nodes, but judging by the render speedup here, I don't know if it would have been worth it. The main thing that it would have granted would be the extra copies between lazy nodes of the large primitive list.

I later noticed (with the help of our lovely TA's) that you don't need the belowChild data (because it is always aboveChild+1). Also, I noticed that I could reuse a few more bytes without my funky bit shifts. After adding this, I saved 20 bytes, and the render time went down by about 10%. This was the second submission.

Count a bit off

One thing about the counts, is a lazy node becomes another node when it is made "unLazy". Should I count this as being 2 nodes created, or just one? I counted it as just 1 node to make my numbers look better

Const

I never could get the const thing to go. I made all my data mutable and it still didn't like me. I had to call build_tree somehow, but if I made that const, then I had to call initLeaf, which called the memory Area stuff. I had to use the const_cast hack. Sorry

Run Machine

The tests were run on the machine fileserver.stanford.edu, which is a gentoo box. Intel 2.40 Gz, 1 Gig Ram, 3 Gig Swap. The swap is important because for the plants tests I ran over my memory using both the lazy and the real kdtree.

Tons of Build Messages

I did as Kayvon suggested and wraped the construction of my object in building StatCounters. Then It printed:

Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (1.2s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.1s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.1s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.1s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.1s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.1s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.1s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.1s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.1s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.1s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.1s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s) Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.3s)

I just summed these to get build time. Is this right? How come I am getting so many accelerators made?

Final Images Rendered with my implementation of lz-kdtree.cpp

killeroos-view1.pbrt (Killeroos visible)

"killeroos-view2.pbrt (Killeroos invisible)"

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

"plants-view1.pbrt"

"plants-view2.pbrt"