88 }

    88 }

    89 

    89 

    90 KdNode::~KdNode()

    90 KdNode::~KdNode()

    91 {

    91 {

    92 	if (isLeaf())

    92 	if (isLeaf())

    94 	else

    94 	else

    95 		delete[] children;

    95 		delete[] children;

    96 }

    96 }

    97 

    97 

    98 void KdNode::subdivide(BBox bbox, int depth)

    98 void KdNode::subdivide(BBox bbox, int depth)

   235 	split = splitpos->pos;

   235 	split = splitpos->pos;

   236 	float lnum = splitpos->lnum;

   236 	float lnum = splitpos->lnum;

   237 	float rnum = splitpos->rnum;

   237 	float rnum = splitpos->rnum;

   238 

   238 

   239 	// split this node

   239 	// split this node

   241 	children = new KdNode[2];

   241 	children = new KdNode[2];

   242 	int state = 0;

   242 	int state = 0;

   243 	for (sh = sslist.begin(); sh != sslist.end(); sh++)

   243 	for (sh = sslist.begin(); sh != sslist.end(); sh++)

   244 	{

   244 	{

   245 		// if shape is on left side of split plane

   245 		// if shape is on left side of split plane

   299 }

   299 }

   300 

   300 

   301 void KdTree::build()

   301 void KdTree::build()

   302 {

   302 {

   303 	root = new KdNode();

   303 	root = new KdNode();

   305 	root->subdivide(bbox, 0);

   307 	root->subdivide(bbox, 0);

   306 	built = true;

   308 	built = true;

   307 }

   309 }

   308 

   310 

   309 /* algorithm by Vlastimil Havran, Heuristic Ray Shooting Algorithms, appendix C */

   311 /* algorithm by Vlastimil Havran, Heuristic Ray Shooting Algorithms, appendix C */