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.

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

}

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 refined. 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.

I'm currently working on a version that doens't refine anything until it needs it. Keep posted.

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

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

killeroos-view1.pbrt (Killeroos visible)

KD Tree

Lazy KD Tree

Ratio

build time (secs)

36.3

5.4

%

total time (secs)

36.4

58.4

%

Num of nodes made

2.752M

845.6k

%

Triangle ray intersections

673.2k

673.2k

%

"killeroos-view2.pbrt (Killeroos invisible)"

KD Tree

Lazy KD Tree

Ratio

build time (secs)

36.6

5.4

%

total time (secs)

30.9

32.7

%

Num of nodes made

2.752M

76

%

Triangle ray intersections

758.4k

758.4k

%

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

KD Tree

Lazy KD Tree

Ratio

build time (secs)

36.7

5.4

%

total time (secs)

40.0

49.3

%

Num of nodes made

2.752M

231.8k

%

Triangle ray intersections

644.1k

644.1k

%

"plants-view1.pbrt"

KD Tree

Lazy KD Tree

Ratio

build time (secs)

96.3

%

total time (secs)

1238

%

Num of nodes made

14.886M

%

Triangle ray intersections

20.292M

%

"plants-view2.pbrt"

KD Tree

Lazy KD Tree

Ratio

build time (secs)

95.1

%

total time (secs)

2133.9

%

Num of nodes made

14.886M

%

Triangle ray intersections

25.917M

%

PaulTarjan/Assignment2 (last edited 2006-04-27 08:35:41 by PaulTarjan)