Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
    
Your computing the dot product of the planes position against nvertex... the normal never even comes into play? –  Daniel 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) –  Daniel 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. –  Daniel Apr 9 '12 at 4:22
add comment

1 Answer

up vote 0 down vote accepted

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!

share|improve this answer
    
Be sure to accept your own answer for archiving purposes. :-) –  Eric Apr 9 '12 at 10:31
    
@Eric: I will- when it lets me. –  DeadMG Apr 9 '12 at 12:00
    
Wups, I figured the wait time would be less than 48h, my bad! –  Eric Apr 9 '12 at 12:36
    
@Eric: It's 48h from question ask, I think. –  DeadMG Apr 9 '12 at 14:40
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.