Frustum culling

[PI]

Hello guys!

I'm trying to implement frustum culling into my game, and although I've realized it's already built in Irrlicht, I'd like to do it myself because I need the information which node was culled and which not.

The problem is that from certain angles, it culls even those parts that should be visible. Here are some pictures of it:

http://www.pport.fw.hu/frustum0.PNG

http://www.pport.fw.hu/frustum1.PNG

http://www.pport.fw.hu/frustum2.PNG

And here's the code:

Code: Select all

//! CScreenFrustum class
class CScreenFrustum
{
    public:

        //! constructor
        CScreenFrustum(scene::ISceneManager* Smgr, scene::ICameraSceneNode* Cam);

        //! isNodeInside
        bool isNodeInside(scene::IMeshSceneNode* Node);


    private:

        //! transform
        void transform(const core::matrix4& mat);

        //! rebuild
        void rebuild();

        //! isPointInside
        bool isPointInside(core::vector3df Point);


        // local instances
        scene::ISceneManager* smgr;
        scene::ICameraSceneNode* cam;

        //            0,0  W,0  0,H  W,H
        core::line3df r00, r10, r01, r11;

        // screen frustum
        core::plane3df plane[6];

        // BB
        core::aabbox3df BB;

}; // end class CScreenFrustum

Code: Select all

//! constructor
CScreenFrustum::CScreenFrustum(scene::ISceneManager* Smgr, scene::ICameraSceneNode* Cam)
{
    // local instances
    smgr = Smgr;
    cam = Cam;

    // screen coordinates
    scene::ISceneCollisionManager* cmgr = smgr->getSceneCollisionManager();
    core::dimension2d<s32> screen = smgr->getVideoDriver()->getScreenSize();

    // plane points in 3D
    r00 = cmgr->getRayFromScreenCoordinates(core::position2d<s32>(0, 0), cam);
    r10 = cmgr->getRayFromScreenCoordinates(core::position2d<s32>(screen.Width, 0), cam);
    r01 = cmgr->getRayFromScreenCoordinates(core::position2d<s32>(0, screen.Height), cam);
    r11 = cmgr->getRayFromScreenCoordinates(core::position2d<s32>(screen.Width, screen.Height), cam);

    // adjusting with aspect ratio (Irrlicht sets the start coordinates to the camera
    core::matrix4 mat = cam->getAbsoluteTransformation();
    float aspr = cam->getAspectRatio();
    r00.start = core::vector3df(-aspr,  1, 0);
    r10.start = core::vector3df( aspr,  1, 0);
    r01.start = core::vector3df(-aspr, -1, 0);
    r11.start = core::vector3df( aspr, -1, 0);
    mat.transformVect(r00.start);
    mat.transformVect(r10.start);
    mat.transformVect(r01.start);
    mat.transformVect(r11.start);

    // BB
    BB.reset(cam->getAbsolutePosition());
    BB.addInternalPoint(r00.start);
    BB.addInternalPoint(r10.start);
    BB.addInternalPoint(r01.start);
    BB.addInternalPoint(r11.start);
    BB.addInternalPoint(r00.end);
    BB.addInternalPoint(r10.end);
    BB.addInternalPoint(r01.end);
    BB.addInternalPoint(r11.end);
}

//! isPointInside
bool CScreenFrustum::isPointInside(core::vector3df Point)
{
    for (int i = 0; i < 6; ++i)
        if (plane[i].classifyPointRelation(Point) == core::ISREL3D_BACK) return false;

    return true;
}

//! isNodeInside
bool CScreenFrustum::isNodeInside(scene::IMeshSceneNode* Node)
{
    // Quick tests ----
    // trans node BB
    core::aabbox3df nodeTransBB = Node->getTransformedBoundingBox();

    // if the camera is inside the nodeTRBB
    if (nodeTransBB.isPointInside(cam->getAbsolutePosition())) return true;

    // if nodeTransBB is not inside in frustum BB
    if (!BB.intersectsWithBox(nodeTransBB)) return false;


    // frustum test ----
    // rebuild planes
    rebuild();

    // transform the frustum to the node's absolute transformation
    core::matrix4 invTrans(Node->getAbsoluteTransformation());
    invTrans.makeInverse();
    transform(invTrans);

    // get the points of nodeBB 
    core::aabbox3df nodeBB = Node->getBoundingBox();
    core::vector3df p[8];
    nodeBB.getEdges(&p[0]);

    // if at least one point is inside, the node is inside
    for (int i = 0; i < 8; ++i)
        if (isPointInside(p[i])) return true;

    return false;
}

//! transform
/// transform the planes with matrix
void CScreenFrustum::transform(const core::matrix4& mat)
{
    for (int i = 0; i < 6; ++i) mat.transformPlane(plane[i]);
}

//! rebuild
/// rebuild planes
void CScreenFrustum::rebuild()
{
    // planes
    plane[0].setPlane(r10.start, r00.start, r01.start); // near
    plane[1].setPlane(r00.end, r10.end, r01.end);       // far

    plane[2].setPlane(r01.end, r11.end, r11.start);     // bottom
    plane[3].setPlane(r00.start, r10.start, r10.end);   // top

    plane[4].setPlane(r00.start, r00.end, r01.end);     // left
    plane[5].setPlane(r10.end, r10.start, r11.start);   // right
}

Can you help me?
Thanks in advane!
PI

[9YkKsvXM]

-

[PI]

Hi Nate_D,

Well, not really. My question is: how to build a proper view frustum? I'd really like to use scene::SViewFrustum, but I don't know how to setup it. I've tried to follow the steps through the rendering mechanism of Irrlicht, but frankly I got lost.

Can anybody help me to build a view frustum?

My culling problems are due to my frustum culler...

I haven't seen any culling problems from Irrlicht.
Have you set up your bounding boxes properly?

Cheers,
PI

[Kalango]

Well, a simple solution would be for you to get the frustum culling box and check for every node if its culled(outside of the box) or not....
i'm not shure how to do that but it seems that you have to build an bounding box from the frustum box...., maybe with getViewFrustum.getBoundingBox.....

*EDIT: Yeah it works, you get the camera frustum and the bounding box of it, then you check if the boundingbox of your scene node is intersecting with the frustum box, thats it...

Code: Select all

if(!model->getTransformedBoundingBox().intersectsWithBox(camera->getViewFrustum()->getBoundingBox()))
        cout<<"Culled!";

PS: You should test there cuz i tested realy quick

[PI]

Hi Kalango, well, the bounding box of the frustum is an aabb box, but the frustum box is like a pyramid.

Anyway, I've finally managed to implement frustum box and sphere culling. No more culling problems.

I'd still like to know how to build an SViewFrustum properly.

Nate_D, you could test it with your project, let's see if you can get rid of culling problems.

Here's the code, (sorry for the Hungarian comments) it's a combination of BoundingBox, FrustumBox and FrustumSphere culling.

CScreenFrustum.h

Code: Select all

//! CScreenFrustum class
/// kiszuri a kepernyon lathato node-okat a Bounding Box-juk alapjan
class CScreenFrustum
{
    public:

        //! constructor
        CScreenFrustum(scene::ISceneManager* Smgr, scene::ICameraSceneNode* Cam);

        //! isNodeInside
        bool isNodeInside(scene::IMeshSceneNode* Node);

        //! DEBUG_draw
        void DEBUG_draw();

    private:
        //! quickTest
        bool quickTest(scene::IMeshSceneNode* Node);

        //! frustumBoxTest
        bool frustumBoxTest(scene::IMeshSceneNode* Node);

        //! isPointInside
        bool isPointInside(core::vector3df Point);

        //! frustumSphereTest
        bool frustumSphereTest(scene::IMeshSceneNode* Node);

        //! transform
        void transform(const core::matrix4& mat);

        //! rebuild
        void rebuild();

        // helyi instancok
        scene::ISceneManager* smgr;
        scene::ICameraSceneNode* cam;

        // W = ScreenWidth  H = ScreenHeight  n = near  f = far
        //              00n   W0n   0Hn   WHn     00f   W0f   0Hf   WHf
        core::vector3df r000, r100, r010, r110,   r001, r101, r011, r111;

        // screen frustum
        core::plane3df orgPlane[6], plane[6];

        // BB
        core::aabbox3df BB;

}; // end class CScreenFrustum

CScreenFrustum.cpp

Code: Select all

//! constructor
CScreenFrustum::CScreenFrustum(scene::ISceneManager* Smgr, scene::ICameraSceneNode* Cam)
{
    // instancok
    smgr = Smgr;
    cam = Cam;

    // plane-ek alkotoelemei
    core::matrix4 mat = cam->getAbsoluteTransformation();
    float nearv = cam->getNearValue();
    float farv = cam->getFarValue();
    float aspr = cam->getAspectRatio();
    float fov = cam->getFOV();

    float tang = tan(fov / 2);
    float nearh = 2 * tang * nearv;
    float nearw = nearh * aspr;
    float farh = 2 * tang * farv;
    float farw = farh * aspr;

    float nearh2 = nearh / 2;
    float nearw2 = nearw / 2;
    float farh2 = farh / 2;
    float farw2 = farw / 2;

    // near coords
    r000 = core::vector3df(-nearw2,  nearh2, nearv);
    r100 = core::vector3df( nearw2,  nearh2, nearv);
    r010 = core::vector3df(-nearw2, -nearh2, nearv);
    r110 = core::vector3df( nearw2, -nearh2, nearv);

    mat.transformVect(r000);
    mat.transformVect(r100);
    mat.transformVect(r010);
    mat.transformVect(r110);

    // far coords
    r001 = core::vector3df(-farw2,  farh2, farv);
    r101 = core::vector3df( farw2,  farh2, farv);
    r011 = core::vector3df(-farw2, -farh2, farv);
    r111 = core::vector3df( farw2, -farh2, farv);
    mat.transformVect(r001);
    mat.transformVect(r101);
    mat.transformVect(r011);
    mat.transformVect(r111);

    // BB
    BB.reset(cam->getAbsolutePosition());
    BB.addInternalPoint(r000);
    BB.addInternalPoint(r100);
    BB.addInternalPoint(r010);
    BB.addInternalPoint(r110);
    BB.addInternalPoint(r001);
    BB.addInternalPoint(r101);
    BB.addInternalPoint(r011);
    BB.addInternalPoint(r111);

    // eredeti plane-ek
    orgPlane[0].setPlane(r100, r000, r010); // near
    orgPlane[1].setPlane(r001, r101, r011); // far

    orgPlane[2].setPlane(r011, r111, r110); // bottom
    orgPlane[3].setPlane(r000, r100, r101); // top

    orgPlane[4].setPlane(r000, r001, r011); // left
    orgPlane[5].setPlane(r101, r100, r110); // right

}

//! quickTest
/// egyszeru bouningbox-tesz a frustum tesztek elott
bool CScreenFrustum::quickTest(scene::IMeshSceneNode* Node)
{
    // trans node BB
    core::aabbox3df nodeTransBB = Node->getTransformedBoundingBox();

    // ha a kamera a nodeTRBB-n belul
    if (nodeTransBB.isPointInside(cam->getAbsolutePosition())) return true;

    // ha nincs a BB-n belul
    if (!BB.intersectsWithBox(nodeTransBB)) return false;

    return true;
}

//! frustumBoxTest
/// frustum vs. bounding box
bool CScreenFrustum::frustumBoxTest(scene::IMeshSceneNode* Node)
{
    // ujraepitjuk a planeket
    rebuild();

    // atvisszuk a frustumot a node absz. transzf. matrixjaba
    core::matrix4 invTrans(Node->getAbsoluteTransformation());
    invTrans.makeInverse();
    transform(invTrans);

    // nodeBB pontjai
    core::aabbox3df nodeBB = Node->getBoundingBox();
    core::vector3df p[8];
    nodeBB.getEdges(&p[0]);

    // ha akar csak egy pont benne van, akkor lathato a node
    for (int i = 0; i < 8; ++i)
        if (isPointInside(p[i])) return true;

    return false;
}

//! isPointInside
/// pont a plane-ek kozott van-e?
bool CScreenFrustum::isPointInside(core::vector3df Point)
{
    for (int i = 0; i < 6; ++i)
        if (plane[i].classifyPointRelation(Point) == core::ISREL3D_BACK) return false;

    return true;
}

//! frustumSphereTest
/// frustum vs. bounding sphere
bool CScreenFrustum::frustumSphereTest(scene::IMeshSceneNode* Node)
{
   // node transzformalt bb
    core::aabbox3df nodeTransBB = Node->getTransformedBoundingBox();

    // plane-ek ujraepitese
    rebuild();

    // sphere test
    core::vector3df center = nodeTransBB.getCenter();
    float radius = (nodeTransBB.MaxEdge - center).getLength();
    float dist;

    for (int i = 0; i < 6; ++i)
    {
        //plane[i].Normal.dotProduct(center) + plane[i].D;
        dist = plane[i].getDistanceTo(center);

        // kint van
        if (dist <= -radius) return false;
    }

    return true;
}

//! isNodeInside
/// a node a kepernyo frustumjaban van-e?
bool CScreenFrustum::isNodeInside(scene::IMeshSceneNode* Node)
{
    bool ret;

    if (ret = quickTest(Node))  // ha a gyorstszten atment
        if (!(ret = frustumBoxTest(Node)))  // es a boxteszten bukott
            if (ret = frustumSphereTest(Node)); // attol a sphereteszten meg remekelhet

    return ret;
}

//! transform
/// matrixxal transzformalja az oldalakat
void CScreenFrustum::transform(const core::matrix4& mat)
{
    for (int i = 0; i < 6; ++i) mat.transformPlane(plane[i]);
}

//! rebuild
/// helyreallitja plane-eket
void CScreenFrustum::rebuild()
{
    // vissza az eredeti allapotba
    for (int i = 0; i < 6; ++i) plane[i].setPlane(orgPlane[i].Normal, orgPlane[i].D);
}


//! DEBUG_draw
void CScreenFrustum::DEBUG_draw()
{
    video::IVideoDriver* driver = smgr->getVideoDriver();
    core::matrix4 world;
    world.makeIdentity();
    driver->setTransform(video::ETS_WORLD, world);

    // near
    driver->draw3DLine(r000, r100, video::SColor(255, 255, 0, 0));
    driver->draw3DLine(r100, r110, video::SColor(255, 255, 0, 0));
    driver->draw3DLine(r110, r010, video::SColor(255, 255, 0, 0));
    driver->draw3DLine(r010, r000, video::SColor(255, 255, 0, 0));

    // edges
    driver->draw3DLine(r000, r001, video::SColor(255, 0, 255, 0));
    driver->draw3DLine(r100, r101, video::SColor(255, 0, 255, 0));
    driver->draw3DLine(r010, r011, video::SColor(255, 0, 255, 0));
    driver->draw3DLine(r110, r111, video::SColor(255, 0, 255, 0));

    // far
    driver->draw3DLine(r001, r101, video::SColor(255, 0, 0, 255));
    driver->draw3DLine(r101, r111, video::SColor(255, 0, 0, 255));
    driver->draw3DLine(r111, r011, video::SColor(255, 0, 0, 255));
    driver->draw3DLine(r011, r001, video::SColor(255, 0, 0, 255));
}

Cheers,
PI

[Kalango]

Hi Kalango, well, the bounding box of the frustum is an aabb box, but the frustum box is like a pyramid.

Yeah, but the bounding box is the frustum limits (the "pyramid" you say), try it and u shall see .
IMHO you're just reinventing the wheel, tho it can be pretty usefull for adding better culling techniques later...anyway good luck

[PI]

Yeah, but the bounding box is the frustum limits (the "pyramid" you say), try it and u shall see Razz.

I know, that's what I do in the quick test.

IMHO you're just reinventing the wheel, tho it can be pretty usefull for adding better culling techniques later...anyway good luck Wink

That's true. But I need the information what is culled and what's not, because I'd like to have my nodes in a tree structure. So when a large part is culled, all the smaller parts in it are culled too. Irrlicht does not give me any information about this.

BTW, I think there's no frustumSphere culling in Irrlicht yet. You can select it, but it does nothing, just have a look at CSceneManager.cpp -> bool CSceneManager::isCulled(const ISceneNode* node)

Code: Select all

		// can be seen by a bounding sphere
		case scene::EAC_FRUSTUM_SPHERE:
		{ // requires bbox diameter
		}
		break;

Regarding to my code, I think the whole frustumBox test can be skipped... I'll test it later, but it seems to be slower and less accurate.

[Kalango]

Nice sphere culling could be pertty nice.
As for the culling, you're meaning octree techniques (its included on irrlicht already)? Cuz if its a better accurate and more sofisticated structure than octree its not beginer stuff at all...

[PI]

Nice Razz sphere culling could be pertty nice.

It's done, see the code above You could test it, by the way.

As for the culling, you're meaning octree techniques (its included on irrlicht already)? Cuz if its a better accurate and more sofisticated structure than octree its not beginer stuff at all...

I haven't decided yet. Currently the whole map (128x8x128 cubes) is split up into buffers (16x1x16 buffers). As you can see on the picture below, approx. 20 buffers of 256 are visible which is really cool, gives me a lot of FPS.

http://www.pport.fw.hu/frustum4.JPG