void traceBox(Vector3 inputStart, Vector3 inputEnd, Vector3 inputMins, Vector3 inputMaxs)
{
	if (inputMins.x == 0 && inputMins.y == 0 && inputMins.z == 0 && inputMaxs.x == 0 && inputMaxs.y == 0 && inputMaxs.z == 0)
	{
		traceRay(inputStart, inputEnd);
	}

	else
	{
		tracer.traceType      = BOX;
		tracer.traceMins      = inputMins;
		tracer.traceMaxs      = inputMaxs;
		tracer.traceExtents.x = -tracer.traceMins.x > tracer.traceMaxs.x ? -tracer.traceMins.x : tracer.traceMaxs.x;
		tracer.traceExtents.y = -tracer.traceMins.y > tracer.traceMaxs.y ? -tracer.traceMins.y : tracer.traceMaxs.y;
		tracer.traceExtents.z = -tracer.traceMins.z > tracer.traceMaxs.z ? -tracer.traceMins.z : tracer.traceMaxs.z;

		trace(inputStart, inputEnd);
	}
}

void trace(Vector3 inputStart, Vector3 inputEnd)
{
	tracer.outputStartsOut = 1;
	tracer.outputAllSolid  = 0;
	tracer.outputFraction  = 1.0f;

	/* Walk the tree */

	checkNode(0, 0.0f, 1.0f, inputStart, inputEnd);

	tracer.outputEnd.x = inputStart.x + tracer.outputFraction * (inputEnd.x - inputStart.x);
	tracer.outputEnd.y = inputStart.y + tracer.outputFraction * (inputEnd.y - inputStart.y);
	tracer.outputEnd.z = inputStart.z + tracer.outputFraction * (inputEnd.z - inputStart.z);
}

void checkNode(int nodeIndex, float startFraction, float endFraction, Vector3 start, Vector3 end)
{
	int i, side;
	float fraction1, fraction2, middleFraction, inverseDistance;
	float startDistance, endDistance, offset;
	Vector3 middle;
	BSPLeaf *leaf;
	BSPBrush *brush;
	BSPNode *node;
	Plane *plane;

	if (nodeIndex < 0) /* Leaf */
	{
		leaf = &bsp.leafs[-(nodeIndex + 1)];

		for (i=0;i<leaf->numOfLeafBrushes;i++)
		{
			brush = &bsp.brushes[bsp.leafBrushes[leaf->leafBrush + i]];

			if (brush->numOfBrushSides > 0 && (bsp.textures[brush->textureID].contents & 1))
			{
				checkBrush(brush, start, end);
			}
		}

		return;
	}

	/* Node */

	node  = &bsp.nodes[nodeIndex];
	plane = &bsp.planes[node->plane];

	startDistance = (DOT(start, plane->normal)) - plane->d;
	endDistance   = (DOT(end, plane->normal))   - plane->d;

	if (tracer.traceType == RAY)
	{
		offset = 0;
	}

	else if (tracer.traceType == SPHERE)
	{
		offset = tracer.traceRadius;
	}

	else if (tracer.traceType == BOX)
	{
		offset = (float)(fabs(tracer.traceExtents.x * plane->normal.x) + fabs(tracer.traceExtents.y * plane->normal.y) + fabs(tracer.traceExtents.z * plane->normal.z));
	}

	if (startDistance >= offset && endDistance >= offset) /* Check front node as both points are in front of plane */
	{
		checkNode(node->children[0], startFraction, endFraction, start, end);
	}

	else if (startDistance < -offset && endDistance < -offset) /* Check behind node as both points are in back of plane */
	{
		checkNode(node->children[1], startFraction, endFraction, start, end);
	}

	else
	{
		if (startDistance < endDistance) /* Back */
		{
			side = 1;
			inverseDistance = 1.0f / (startDistance - endDistance);
			fraction1 = (startDistance - offset + EPSILON) * inverseDistance;
			fraction2 = (startDistance + offset + EPSILON) * inverseDistance;
		}

		else if (endDistance < startDistance) /* Front */
		{
			side = 0;
			inverseDistance = 1.0f / (startDistance - endDistance);
			fraction1 = (startDistance + offset + EPSILON) * inverseDistance;
			fraction2 = (startDistance - offset - EPSILON) * inverseDistance;
		}

		else /* Just set to Front */
		{
			side = 0;
			fraction1 = 1.0f;
			fraction2 = 0.0f;
		}

		if (fraction1 < 0.0f)
		{
			fraction1 = 0.0f;
		}

		else if (fraction1 > 1.0f)
		{
			fraction1 = 1.0f;
		}

		if (fraction2 < 0.0f)
		{
			fraction2 = 0.0f;
		}

		else if (fraction2 > 1.0f)
		{
			fraction2 = 1.0f;
		}

		/* Calculate the middle point for the first side */

		middleFraction = startFraction + (endFraction - startFraction) * fraction1;

		middle.x = start.x + fraction1 * (end.x - start.x);
		middle.y = start.y + fraction1 * (end.y - start.y);
		middle.z = start.z + fraction1 * (end.z - start.z);

		/* Check the first side */

		checkNode(node->children[side], startFraction, middleFraction, start, middle);

		/* Calculate the middle point for the second side */

		middleFraction = startFraction + (endFraction - startFraction) * fraction2;

		middle.x = start.x + fraction2 * (end.x - start.x);
		middle.y = start.y + fraction2 * (end.y - start.y);
		middle.z = start.z + fraction2 * (end.z - start.z);

		/* Check the second side */

		checkNode(node->children[1 - side], middleFraction, endFraction, middle, end);
	}
}

void checkBrush(BSPBrush *brush, Vector3 inputStart, Vector3 inputEnd)
{
	int i, startsOut, endsOut, planeIndex;
	float startFraction, endFraction, startDistance, endDistance, fraction;
	BSPBrushSide *brushSide;
	Plane *plane;
	Vector3 offset;

	startFraction = -1.0f;
	endFraction   = 1.0f;
	startsOut     = 0;
	endsOut       = 0;

	for (i=0;i<brush->numOfBrushSides;i++)
	{
		brushSide  = &bsp.brushSides[brush->brushSide + i];
		plane      = &bsp.planes[brushSide->plane];

		if (tracer.traceType == RAY)
		{
			startDistance = (DOT(inputStart, plane->normal)) - plane->d;
			endDistance   = (DOT(inputEnd, plane->normal))   - plane->d;
		}

		else if (tracer.traceType == BOX)
		{
			offset.x = plane->normal.x < 0 ? tracer.traceMaxs.x : tracer.traceMins.x;
			offset.y = plane->normal.y < 0 ? tracer.traceMaxs.y : tracer.traceMins.y;
			offset.z = plane->normal.z < 0 ? tracer.traceMaxs.z : tracer.traceMins.z;

			startDistance = (inputStart.x + offset.x) * plane->normal.x + (inputStart.y + offset.y) * plane->normal.y + (inputStart.z + offset.z) * plane->normal.z - plane->d;
			endDistance   = (inputEnd.x   + offset.x) * plane->normal.x + (inputEnd.y   + offset.y) * plane->normal.y + (inputEnd.z   + offset.z) * plane->normal.z - plane->d;
		}

		if (startDistance > 0)
		{
			startsOut = 1;
		}

		if (endDistance > 0)
		{
			endsOut = 1;
		}

		/* Make sure the trace isn't completely on one side of the brush */

		if (startDistance > 0 && endDistance > 0) /* Both are in front of the plane, its outside of this brush */
		{
			return;
		}

		if (startDistance <= 0 && endDistance <= 0) /* Both are behind this plane, it will get clipped by another one */
		{
			continue;
		}

		if (startDistance > endDistance) /* Line is entering into the brush */
		{
			fraction = (startDistance - EPSILON) / (startDistance - endDistance);

			if (fraction > startFraction)
			{
				planeIndex    = brushSide->plane;
				startFraction = fraction;
			}
		}

		else /* Line is leaving the brush */
		{
			fraction = (startDistance + EPSILON) / (startDistance - endDistance);

			if (fraction < endFraction)
			{
				endFraction = fraction;
			}
		}
	}

	if (startsOut == 0)
	{
		if (endsOut == 0)
		{
			tracer.outputAllSolid = 1;
		}

		return;
	}

	if (startFraction < endFraction)
	{
		if (startFraction > -1 && startFraction < tracer.outputFraction)
		{
			if (startFraction < 0)
			{
				startFraction = 0;
			}

			tracer.outputFraction = startFraction;
			tracer.outputNormal   = &bsp.planes[planeIndex].normal;
		}
	}
}