proc	traverse(Node *n, Planes *list)
{
	CODE = CodeToVolume(n, list);

	if (CODE == INSIDE)
	{
		// The entire branch is inside, render

		renderBranch(n);
	}
	else if (CODE == OUTSIDE)
	{
		// This node (and all children) are outside, skip

		return;
	}
	else // CODE == PARTIAL
	{
		// Render any polygons associated to this node

		renderNode(n);

		// Visit my children

		loop (i = 0 .. 8)
		{
			traverse(n->child[i], list);
		}
	}
}
 

Point	CornerOffsets[] =
{
	Vector(-1, -1, -1),	// - - -
	Vector( 1, -1, -1),	// - - +
	Vector(-1,  1, -1),	// - + -
	Vector( 1,  1, -1),	// - + +
	Vector(-1, -1,  1),	// + - -
	Vector( 1, -1,  1),	// + - +
	Vector(-1,  1,  1),	// + + -
	Vector( 1,  1,  1)	// + + +
};
 

// Note that the input vector must already be negated when using this code
for halfplane tests

proc	VectorToIndex(Vector v)
{
	index = 0;

	if (v.z >= 0) index |= 1;
	if (v.y >= 0) index |= 2;
	if (v.x >= 0) index |= 4;

	return index;
}
 

proc	CodeToVolume(Node *n, Planes *list)
{
	// Visit each plane once

	bool	partialFlag = false;
	loop (i = 0 .. list[n])
	{
		// Test against the negative halfspace first
		//
		// Note: we use the positive normal here

		Index = VectorToIndex(list[i]->normal);

		// Get the corner point of the node
		//
		// Note: The addition and multiplication operators
		                      // are component-wise operations

		negTestPoint = n->center + n->radius * CornerOffsets[Index];

		// Test for completely within the negative halfspace of this plane
		//
		// If the halfplane test returns negative, the negTestPoint (as
		// well as the rest of the node) is within the negative halfspace,
		// so we can bail early.

		if (list[n].halfplane(negTestPoint) == -1) return OUTSIDE;

		// Test against the positive halfspace
		//
		// Note: we use the negative normal here

		Index = VectorToIndex(-list[i]->normal);

		// Get the corner point of the node
		//
		// Note: The addition and multiplication operators
		                      // are component-wise operations

		posTestPoint = n->center + n->radius * CornerOffsets[Index];

		// Test for completely within the positive halfspace of this plane
		//
		// If the halfplane test returns negative, the posTestPoint is _not_
		// completely within the positive halfspace, and therefore must be
		// bisected by the plane.

		if (list[n].halfplane(posTestPoint) == -1) partialFlag = true;
	}

	// At this point, the node must be either "partially included"
	// or completely included. The partial flag is used to determine
	// the result.

	if (partialFlag) return PARTIAL;
	return INSIDE;
}