CS348b2007

Assignment 2

Implementation

Lazy Refinement

I realized that simply refining a primitive into the existing Kd-Tree upon ray intersection would be a problem because other nodes may contain this primitive as well. If this 1 primitive becomes 8000, how will I update all the other nodes to know? Therefore, since Kd-Trees are primitives as well, I decided that upon intersecting a leaf node containing an unrefined primitive, I would replace that primitive with a Kd-Tree and refine this primitive inside the new Kd-Tree.

My rules

- putting kd-trees in nodes b/c I don't want to dynamically increase the # of

- kept node data at 8bytes by smart flagging and by only storing address of "below" child node, making sure "above" is allocated next.

- added Weight() function to all Primitives so that I can divide nodes fairly when they have unrefined primitives inside

- instead of using extra bit for unfinished flag (further reducing accuracy

- storing a number of parameters in UnfinishedNodeData. These are simply allocated and deleted, which bothers me. I do pass them on for re-use though. Once a node becomes a leaf it has to delete its unfinished data since it will have no more children to pass it to.

- moved some pre-allocated data into KdTreeAccel so it doesn't have to bloat UnfinishedNodeData

- hitting an unrefined primitive makes a new KdTreeAccel containing that primitive. Inside the new KdTree, I refine until I have at least 1 fully refined primitive OR I have more than 1 primitive.

Results

View: 1

pbrt K-D Tree

my Lazy K-D Tree

Ratio (lazy/non-lazy reference)

build time (secs)

580

413

0.71

total time (secs)

1095

929

0.85

nodes made

9.76M

3.58M

0.37

Triangle ray intersections

2231k

2345k

1.05

View: 2

pbrt K-D Tree

my Lazy K-D Tree

Ratio (lazy/non-lazy reference)

build time (secs)

585

302

0.52

total time (secs)

1155

872

0.75

nodes made

9.77M

1.89M

0.19

Triangle ray intersections

4.84M

5.37M

1.11

View: 3

pbrt K-D Tree

my Lazy K-D Tree

Ratio (lazy/non-lazy reference)

build time (secs)

582

98

0.17

total time (secs)

1032

548

0.53

nodes made

9.77M

0.14M

0.01

Triangle ray intersections

4.86M

6.49M

1.34

View: 3 Refined

pbrt K-D Tree

my Lazy K-D Tree

Ratio (lazy/non-lazy reference)

build time (secs)

-

238

-

total time (secs)

-

689

-

nodes made

-

0.36M

-

Triangle ray intersections

-

6.78M

-

last edited 2007-05-02 06:41:49 by MichaelGraeb