0
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ Your computing the dot product of the planes position against nvertex... the normal never even comes into play? \$\endgroup\$ Apr 8, 2012 at 1:24
  • \$\begingroup\$ @Daniel: The normal is used to decide which vertex is nvertex and pvertex. \$\endgroup\$
    – DeadMG
    Apr 8, 2012 at 9:06
  • \$\begingroup\$ @Daniel: Won't that always return true if r0 is more than 1 distance away from the origin? \$\endgroup\$
    – DeadMG
    Apr 8, 2012 at 13:49
  • \$\begingroup\$ 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) \$\endgroup\$ Apr 8, 2012 at 23:35
  • \$\begingroup\$ 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. \$\endgroup\$ Apr 9, 2012 at 4:22

1 Answer 1

0
\$\begingroup\$

Turns out that the plane definitions were wrong. Once I re-ordered the vertices and used the correct ones for each plane, the test functioned exactly as expected. Thanks!

\$\endgroup\$
3
  • \$\begingroup\$ @Eric: I will- when it lets me. \$\endgroup\$
    – DeadMG
    Apr 9, 2012 at 12:00
  • \$\begingroup\$ Wups, I figured the wait time would be less than 48h, my bad! \$\endgroup\$
    – Eric
    Apr 9, 2012 at 12:36
  • \$\begingroup\$ @Eric: It's 48h from question ask, I think. \$\endgroup\$
    – DeadMG
    Apr 9, 2012 at 14:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .