# Incorrect results for frustum cull

Previously, I had a problem with my frustum culling producing too optimistic results- that is, including many objects that were not in the view volume. Now I have refactored that code and produced a cull that should be accurate to the actual frustum, instead of an axis-aligned box approximation. The problem is that now it never returns anything to be in the view volume.

As the mathematical support library I'm using does not provide plane support functions, I had to code much of this functionality myself, and I'm not really the mathematical type, so it's likely that I've made some silly error somewhere. As follows is the relevant code:

``````class Plane {
public:
Plane() {
r0 = Math::Vector(0,0,0);
normal = Math::Vector(0,1,0);
}
Plane(Math::Vector p1, Math::Vector p2, Math::Vector p3) {
r0 = p1;
normal = Math::Normalize(Math::Cross((p2 - p1), (p3 - p1)));
}
Math::Vector r0;
Math::Vector normal;
};
``````

This class represents one plane as a point and a normal vector.

``````class Frustum {
public:
Frustum(
const std::array<Math::Vector, 8>& points
)
{
planes[0] = Plane(points[0], points[1], points[2]);
planes[1] = Plane(points[4], points[5], points[6]);
planes[2] = Plane(points[0], points[1], points[4]);
planes[3] = Plane(points[2], points[3], points[6]);
planes[4] = Plane(points[0], points[2], points[4]);
planes[5] = Plane(points[1], points[3], points[5]);
}
Plane planes[6];
};
``````

The points are passed in order where (the inverse of) each bit of the index of each point indicates whether it's the left, top, and back of the frustum, respectively. As such, I just picked any three points where they all shared one bit in common to define the planes.

My intersection test is as follows (based on this):

``````bool Intersects(Math::AABB lhs, const Frustum& rhs) const {
for(int i = 0; i < 6; i++) {
Math::Vector pvertex = lhs.TopRightFurthest;
Math::Vector nvertex = lhs.BottomLeftClosest;
if (rhs.planes[i].normal.x <= -0.0f) {
std::swap(pvertex.x, nvertex.x);
}
if (rhs.planes[i].normal.y <= -0.0f) {
std::swap(pvertex.y, nvertex.y);
}
if (rhs.planes[i].normal.z <= -0.0f) {
std::swap(pvertex.z, nvertex.z);
}
if (Math::Dot(nvertex - rhs.planes[i].r0, planes[i].normal) < 0.0f) {
return false;
}
}
return true;
}
``````

Also of note is that because I'm using a left-handed co-ordinate system, I wrote my `Cross` function to return the negative of the formula given on Wikipedia.

Any suggestions as to where I've made a mistake?

Edit: I changed my intersection test somewhat. No change, though.

-
Your computing the dot product of the planes position against nvertex... the normal never even comes into play? – dcousens Apr 8 '12 at 1:24
@Daniel: The normal is used to decide which vertex is nvertex and pvertex. – DeadMG Apr 8 '12 at 9:06
@Daniel: Won't that always return true if `r0` is more than 1 distance away from the origin? – DeadMG Apr 8 '12 at 13:49
If you just debug dot(nvertex - rhs.planes[i].r0, planes[i].normal) , it should show you what values you're getting for certain positions. In my own tests, there are negative values when it is behind the plane normal, and positive values when it is front. Therefore, assuming your planes are facing outwards, you should just have >0.0 to check if their fully beyond the half plane. Or <0.0 if their even partially inside. (ref: pastie.org/3752624) – dcousens Apr 8 '12 at 23:35
Here (pastie.org/3753541) are 3 different implementations I tried today, all returning identical results in a variety of test cases. Disregarding floating point errors. They are written in D, but easily transferable. Albeit they all use center/extents and normal/distance. But you should be able to figure them out. – dcousens Apr 9 '12 at 4:22