diff -r d8d596d26f25 -r bf17f9f84c91 DEVNOTES
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/DEVNOTES	Thu Nov 22 17:53:34 2007 +0100
@@ -0,0 +1,58 @@
+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++