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.

I've got some code which performs frustum culling. However, this defines the "frustum" way too broadly- when I have ~10 objects on screen, the code returns 42 objects to be rendered. I've tried taking "slices" through the frustum to attempt to increase the accuracy of the technique, but it doesn't seem to have made much impact. I also significantly reduced the far plane, so that the objects are barely at the edge. Here's my code (where size is the size in screen space- the resolution of the client area of the window I'm rendering into). Any suggestions?

    auto&& size = GetDimensions();
    D3DVIEWPORT9 vp = { 0, 0, size.x, size.y, 0, 1 };
    D3DCALL(device->SetViewport(&vp));
    static const int slices = 10;
    std::vector<Object*> result;
    for(int i = 0; i < slices; i++) {
        D3DXVECTOR3 WorldSpaceFrustumPoints[8] = {
            D3DXVECTOR3(0, size.y,      static_cast<float>(i) / slices),
            D3DXVECTOR3(size.x, 0,      static_cast<float>(i) / slices),
            D3DXVECTOR3(size.x, size.y, static_cast<float>(i) / slices),
            D3DXVECTOR3(0, 0,           static_cast<float>(i) / slices),
            D3DXVECTOR3(0, 0,           static_cast<float>(i + 1) / slices),
            D3DXVECTOR3(size.x, 0,      static_cast<float>(i + 1) / slices),
            D3DXVECTOR3(size.x, size.y, static_cast<float>(i + 1) / slices),
            D3DXVECTOR3(0, size.y,      static_cast<float>(i + 1) / slices)
        };

        D3DXMATRIXA16 Identity;
        D3DXMatrixIdentity(&Identity);
        D3DXVec3UnprojectArray(
            WorldSpaceFrustumPoints, 
            sizeof(D3DXVECTOR3), 
            WorldSpaceFrustumPoints, 
            sizeof(D3DXVECTOR3),
            &vp,
            &Projection,
            &View,
            &Identity,
            8
        );
        Math::AABB Frustum;

        auto world_begin = std::begin(WorldSpaceFrustumPoints);
        auto world_end = std::end(WorldSpaceFrustumPoints);
        auto world_initial = WorldSpaceFrustumPoints[0];
        Frustum.BottomLeftClosest.x = std::accumulate(world_begin, world_end, world_initial, [](D3DXVECTOR3 lhs, D3DXVECTOR3 rhs) { return lhs.x < rhs.x ? lhs : rhs; }).x;
        Frustum.BottomLeftClosest.y = std::accumulate(world_begin, world_end, world_initial, [](D3DXVECTOR3 lhs, D3DXVECTOR3 rhs) { return lhs.y < rhs.y ? lhs : rhs; }).y;
        Frustum.BottomLeftClosest.z = std::accumulate(world_begin, world_end, world_initial, [](D3DXVECTOR3 lhs, D3DXVECTOR3 rhs) { return lhs.z < rhs.z ? lhs : rhs; }).z;
        Frustum.TopRightFurthest.x = std::accumulate(world_begin, world_end, world_initial, [](D3DXVECTOR3 lhs, D3DXVECTOR3 rhs) { return lhs.x > rhs.x ? lhs : rhs; }).x;
        Frustum.TopRightFurthest.y = std::accumulate(world_begin, world_end, world_initial, [](D3DXVECTOR3 lhs, D3DXVECTOR3 rhs) { return lhs.y > rhs.y ? lhs : rhs; }).y;
        Frustum.TopRightFurthest.z = std::accumulate(world_begin, world_end, world_initial, [](D3DXVECTOR3 lhs, D3DXVECTOR3 rhs) { return lhs.z > rhs.z ? lhs : rhs; }).z;
        auto slices_result = ObjectTree.collision(Frustum);
        result.insert(result.end(), slices_result.begin(), slices_result.end());
    }
    return result;
share|improve this question
    
These might help: cescg.org/CESCG-2002/DSykoraJJelinek/index.html zeuxcg.org/2009/01/31/… And it's frustum culling, not frustrum. –  dotminic Mar 27 '12 at 13:04
    
Unfortunately, the raw execution speed of the algorithm isn't the problem. The problem is that it's not being very effective. –  DeadMG Mar 27 '12 at 13:47
add comment

1 Answer

up vote 4 down vote accepted

You appear to be defining your frustum as a cuboid, when it's not that shape at all - it's more cone shaped - the near plane is much smaller than the far plane.

The standard way to test against the frustum is to test against all 6 frustum planes individually.

You can find some code and diagrams explaining it in more detail at http://www.chadvernon.com/blog/resources/directx9/frustum-culling/

share|improve this answer
    
Isn't that going to be O(n) in bounding boxes? –  DeadMG Mar 28 '12 at 0:21
    
@DeadMG It's 6 sphere-vs-plane tests per object. Unless you have huge numbers of objects you probably don't need anything more complicated. –  Adam Mar 28 '12 at 1:38
    
I actually have bounding boxes, not spheres. But O(N) is not very good. –  DeadMG Mar 28 '12 at 2:26
1  
If O(n) is not good enough for you, you'll need some kind of scene hierarchy. Chances are, though, that a well optimized O(n) bounding volume test will not perform much worse than all the bookkeeping involved with complex scene hierarchies if your scene is dynamic and does not have absurd numbers of objects. Of course there is no hard rule for what is an "absurd number" so if you don't have any experience with real-world examples you're probably best off implementing the simple O(n) test as Adam said and looking at a more involved one when this turns out to be a real bottleneck –  Koarl Mar 28 '12 at 7:07
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.