1
\$\begingroup\$

I have two ways of doing frustum culling taken from different web sources. First one takes 200ms to check 10k AABBs, second around 50ms for the same box count. I read some forum answers, people say 0.5ms for 10k is ok but I'm totally far away from those numbers. So what am I doing wrong ?

Measuring time here:

        auto frustum = camera.getFrustum(); //frustum

        auto n = frustum.pNear;
        auto f = frustum.pFar;
        auto e = frustum.pExtra;

        ArrayList<Pair<vec3, vec3>> planes;
        ArrayList<vec3> v1;
        n.genVertices(v1);

        ArrayList<vec3> v2;
        f.genVertices(v2);

        planes << Pair<vec3,vec3>(v1[0], -n.genNormal());
        planes << Pair<vec3,vec3>(v2[0], n.genNormal());
        for(size_t i = 0; i < 4; i++)
        {
            planes << e[i];
        } //frustum planes array initialization done



        ArrayList<AABB> objs; //10k test aabbs
        for(size_t i = 0; i < 10000; i++)
        {
            objs << AABB(vec3(rand_float()/100,rand_float()/100,rand_float()/100),rand_float()/100);
        }

        auto t1 = timer.getTimeNanoSeconds(); //starting to measure
        for(size_t i = 0; i < 10000; i++)
        {
            rs::CollisionEngine::checkAABBAndFrustumFast(objs[i], planes);
        }
        auto t2 = timer.getTimeNanoSeconds() - t1; //getting time
        println("Collision check of 10k objs: "+ toString(t2/1000000) + " ms"); //printing time

Here is slow and fast collision checks:

 /**
    *
    * @param box
    * @return 0 - inside, 1 - intersects, 2 - outside
    */
    us checkAABBAndFrustumSlow(AABB box, ArrayList<Pair<vec3, vec3>>& planes)
    {
        ArrayList<vec3> vertices;
        box.genVertices(vertices);

        us totalIn = 0;

        for(int i = 0;i<6;i++){ //six planes for every frustum
            Pair<vec3, vec3> plane = planes[i];
            auto n = plane.v2;

            uint inCount = 8;
            uint pIn = 1;

            for(int j= 0;j<8;j++){
                vec3 v = vertices[j];
                vec3 toVertex = (v - plane.v1).normalize();
                float res = n * toVertex;
                if(res < 0){
                    inCount -=1;
                    pIn = 0;
                }
            }

            if(inCount == 0) return 2;
            totalIn += pIn;
        }

        if(totalIn == 6) return 0;

        return 1;
    }


    using namespace rs;
    vec3 getPosForFrustum(AABB b, vec3 n)
    {
            vec3 max = b.center + b.extent;
            vec3 p = b.center - b.extent;
            if (n.x() >= 0)
            p(1) = max.x();
            if (n.y() >=0)
            p(2) = max.y();
            if (n.z() >= 0)
            p(3) = max.z();

            return p;
    }

    vec3 getNegForFrustum(AABB b, vec3 n)
    {
        vec3 min = b.center - b.extent;
        vec3 p = b.center + b.extent;
        if (n.x() >= 0)
            p(1) = min.x();
        if (n.y() >=0)
            p(2) = min.y();
        if (n.z() >= 0)
            p(3) = min.z();

        return p;
    }


    uint checkAABBAndFrustumFast(AABB box, ArrayList<Pair<vec3, vec3>>& planes){

            uint result = 0;
            for(int i = 0;i<6;i++) {

                auto n = planes[i].v2;
                auto p = planes[i].v1;

                if (n * (getPosForFrustum(box, n) - p) < 0)
                    return 2;
                else if (n * (getNegForFrustum(box, n) - p) < 0)
                    result = 1;
            }

            return result;
    }

EDIT: ArrayList is a custom vector like structure

Pair contains a copy of two objects it takes.

\$\endgroup\$
4
  • \$\begingroup\$ You seem to have gone only half-way to identifying the bottleneck. I would suggest you further cut-down your checkAABBAndFrustumSlow function in more functions then use a profiler to identify what's taking the longest time to execute (or even more counters). \$\endgroup\$
    – Vaillancourt
    Apr 21 '16 at 11:05
  • \$\begingroup\$ Have you tried vector yet? It might be faster than your own implementation, not sure if thats the bottleneck though \$\endgroup\$
    – tkausl
    May 24 '16 at 9:22
  • \$\begingroup\$ @tkausl nah my implementation works, just had some system issues ) \$\endgroup\$
    – Russoul
    May 24 '16 at 11:10
  • \$\begingroup\$ Is this a release build? Only way I can imagine anything being this slow with the code you have is if you have a boatload of debug checks. Also make sure STL iterator checking is off. \$\endgroup\$
    – user77245
    Dec 11 '17 at 17:29
1
\$\begingroup\$

Main ways to speed up frustum culling (and collision in general):

  • simplified bounding: you have AABBs (check)
  • fast collision functions: looks like you are doing this (in progress)
  • spatial partitioning objects in the world: ???

Spatial partitioning gives the most speed up. Are you doing anything? Depending on game type, there are a ton of easy ways to get massive performance boosts to: frustum culling, collision, picking, AI, etc. all using the same world partitioning.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ I found the issue: doing time measurement in visual studio's debug mode is probably a bad idea ) \$\endgroup\$
    – Russoul
    Apr 21 '16 at 17:37

You must log in to answer this question.

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