|
1 KdTree Algorithm |
|
2 ---------------- |
|
3 |
|
4 def build_kdtree(root, shapes): |
|
5 root = new KdNode |
|
6 root.shapes = shapes |
|
7 subdivide(root, bounding_box(shapes), 0) |
|
8 |
|
9 def subdivide(node, bbox, depth): |
|
10 # choose split axis |
|
11 axis = bbox.largest_extend() |
|
12 |
|
13 # find split position |
|
14 splitpos = find_split_position(axis) |
|
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 |
|
23 def find_split_position(axis): |
|
24 mshapes = new ShapeListWithMarks(shapes) |
|
25 |
|
26 # sort new shape list according to left boundaries |
|
27 mshapes.sort(axis) |
|
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++ |