1 KdTree Algorithm |
1 Classes |
2 ---------------- |
2 ------- |
3 |
3 |
4 def build_kdtree(root, shapes): |
4 vector.h -- vector of three scalars, also used for colour |
5 root = new KdNode |
5 matrix.h -- matrix class, currently not used |
6 root.shapes = shapes |
6 quaternion.h -- quaternion class for camera rotation |
7 subdivide(root, bounding_box(shapes), 0) |
|
8 |
7 |
9 def subdivide(node, bbox, depth): |
8 container.h -- container for shapes, base class for octree and kd-tree |
10 # choose split axis |
9 octree.h -- Octree space subdivision structure for acceleration of ray-shape intersection search |
11 axis = bbox.largest_extend() |
10 kdtree.h -- KdTree space subdivision structure |
12 |
11 |
13 # find split position |
12 scene.h -- scene objects: Ray, Light, Camera and shapes |
14 splitpos = find_split_position(axis) |
13 raytracer.h -- ray tracer class |
|
14 common.h -- Float definition (float/double) and some helper functions |
15 |
15 |
16 leftnode, rightnode = new KdNode[2] |
|
17 for each shape: |
|
18 if (node->intersectleftnode()) leftnode->addprimitive( primitive ) |
|
19 if (node->intersectrightnode()) rightnode->addprimitive( primitive ) |
|
20 subdivide(leftnode, bbox.left_split(splitpos), depth+1) |
|
21 subdivide(rightnode, bbox.right_split(splitpos), depth+1) |
|
22 |
16 |
23 def find_split_position(axis): |
17 Container Usage |
24 mshapes = new ShapeListWithMarks(shapes) |
18 --------------- |
25 |
19 (Container|Octree|KdTree) top; |
26 # sort new shape list according to left boundaries |
20 scene.setTop(top) // top object in hierarchy |
27 mshapes.sort(axis) |
21 top.optimize() // build optimization structure |
28 |
|
29 splitlist = new SplitList() |
|
30 for each mshape from mshapes: |
|
31 splitlist.add_extremes(mshape, axis) |
|
32 splitlist.sort() |
|
33 for each split from splitlist: |
|
34 for each mshape from mshapes: |
|
35 if mshape.marked: |
|
36 continue |
|
37 |
|
38 # if shape is on left side of split plane |
|
39 if mshape.r_boundary <= split.pos: |
|
40 split.lnum++ |
|
41 mshape.mark() |
|
42 |
|
43 # if shape is completely contained in split plane |
|
44 if mshape.l_boundary == mshape.r_boundary == split.pos: |
|
45 if split.num_smaller_subcell == 0: |
|
46 split.num_bigger_subcell++ |
|
47 else: |
|
48 split.num_smaller_subcell++ |
|
49 |
|
50 # if shape is on right side of split plane |
|
51 if mshape.l_boundary >= split.pos: |
|
52 split.r_num += mshapes.count - mshape.number |
|
53 break |
|
54 |
|
55 # if shape occupies both sides of split plane |
|
56 if mshape.l_boundary < split.pos and mshape.r_boundary > split.pos: |
|
57 split.l_num++ |
|
58 split.r_num++ |
|