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