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++