--- a/DEVNOTES Sun Dec 30 00:11:47 2007 +0100
+++ b/DEVNOTES Thu Jan 03 18:06:34 2008 +0100
@@ -1,58 +1,21 @@
-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()
+Classes
+-------
- # find split position
- splitpos = find_split_position(axis)
+vector.h -- vector of three scalars, also used for colour
+matrix.h -- matrix class, currently not used
+quaternion.h -- quaternion class for camera rotation
- 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)
+container.h -- container for shapes, base class for octree and kd-tree
+octree.h -- Octree space subdivision structure for acceleration of ray-shape intersection search
+kdtree.h -- KdTree space subdivision structure
- 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
+scene.h -- scene objects: Ray, Light, Camera and shapes
+raytracer.h -- ray tracer class
+common.h -- Float definition (float/double) and some helper functions
- # 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++
+Container Usage
+---------------
+(Container|Octree|KdTree) top;
+scene.setTop(top) // top object in hierarchy
+top.optimize() // build optimization structure