KdTree Algorithm----------------def build_kdtree(root, shapes): root = new KdNode root.shapes = shapes subdivide(root, bounding_box(shapes), 0)def subdivide(node, bbox, depth): # choose split axis axis = bbox.largest_extend() # find split position splitpos = find_split_position(axis) leftnode, rightnode = new KdNode[2] for each shape: if (node->intersectleftnode()) leftnode->addprimitive( primitive ) if (node->intersectrightnode()) rightnode->addprimitive( primitive ) subdivide(leftnode, bbox.left_split(splitpos), depth+1) subdivide(rightnode, bbox.right_split(splitpos), depth+1)def find_split_position(axis): mshapes = new ShapeListWithMarks(shapes) # sort new shape list according to left boundaries mshapes.sort(axis) splitlist = new SplitList() for each mshape from mshapes: splitlist.add_extremes(mshape, axis) splitlist.sort() for each split from splitlist: for each mshape from mshapes: if mshape.marked: continue # if shape is on left side of split plane if mshape.r_boundary <= split.pos: split.lnum++ mshape.mark() # if shape is completely contained in split plane if mshape.l_boundary == mshape.r_boundary == split.pos: if split.num_smaller_subcell == 0: split.num_bigger_subcell++ else: split.num_smaller_subcell++ # if shape is on right side of split plane if mshape.l_boundary >= split.pos: split.r_num += mshapes.count - mshape.number break # if shape occupies both sides of split plane if mshape.l_boundary < split.pos and mshape.r_boundary > split.pos: split.l_num++ split.r_num++