Sign in to follow this  
deathchaser

Very fast 2D frustum culling

Recommended Posts

Vector3f playerF = Transform.getCamera().getForward();
        
        Vector3f playerPos = Transform.getCamera().getPos();
        
        Vector3f myObject = obj.getPos();
        
        float angle = (float)Math.toDegrees(Math.acos(playerF.dot(myObject.sub(playerPos).normalized())));
        
        if(Float.isNaN(angle))
        {
            return true;
        }
        
        return angle <= Transform.getCamera.fov / 2 + 10; 

Yo,
 
I found this to be a very fast way of 2D frustum culling.

 

The question is: Is this actually a legit way of 2D frustum culling or am I just not seeing something?

Since it is way faster than normal frustum culling.

 

 

(2D in the sence of i dont use the Y it is always 0)

Edited by deathchaser

Share this post


Link to post
Share on other sites

Since you don't take the object's size into account, how can you tell it's outside the frustum? Eg: A large wall, whose origin (returned by getPos() is outside the frustum but part of it is still visible

Share this post


Link to post
Share on other sites
like Tiago said, you don't take into account the size of the object, but you seem to try to compensate for it by adding 10, which is quite random but a good start.
what you want is actually the angular size of the object radius, you should get it  by something like
 
Vector3f playerF = Transform.getCamera().getForward();
        
        Vector3f playerPos = Transform.getCamera().getPos();
        
        Vector3f myObject = obj.getPos();
        
        float angle0 = (float)Math.toDegrees(Math.acos(playerF.dot(myObject.sub(playerPos).normalized())));
        float angle1 = (float)Math.toDegrees(Math.acos(myObject.radius()/(myObject.sub(playerPos).Length())));
        
        if(Float.isNaN(angle0)||Float.isNaN(angle1))
        {
            return true;
        }
        
        return angle0-angle1 <= Transform.getCamera.fov / 2 ; 
not tested, but I think that should work.

yet, doing acos and normalize should take a lot of cpu cycles, testing against 6 frustum planes should be way faster as you just need 6dot products and modern cpus have even an instruction for it and you cull more as the your approximated cone frustum is less tight fitting than the planes.
and in the end, what's the point in saving a few cycles in the culling, if you pay per object more to process it all the way up to the rasterizer on the GPU.

Share this post


Link to post
Share on other sites
You can probably remove the acos (and toDegrees) by keeping all the math in the realm of linear algebra, instead of switching over to trigonometry half way through.

And yes, if implemented correctly, this is a valid approach - treating the camera as an infinitely long cone instead of frustum, and treating your objects as spheres. As above you need to find the solid angle subtended by those spheres. You also want to use the angle from the centre of frustum to one corner - not the angle from centre to top or side.

Share this post


Link to post
Share on other sites

@Krypt0n & @Hodgman I also have normal frustum culling but when i messure the time it takes than this comes out to be faster

Edited by deathchaser

Share this post


Link to post
Share on other sites
well, I was talking about theoretical results, your code doesn't really look like it was made for performance. It could be more memory/cache bound than by the instructions that should actually do the heavy work. (I don't want to imply it's bad, just that it is not designed for performance).

That's why your optimization might result in a lower runtime, but maybe not for the algorithmic change that you've done, but by different access pattern that you use (e.g. accessing slowly one element: poisition, of the object instead of maybe a slow access to 8 corner of the bounding box and what not... although I haven't seen how unoptimized your alternative code is, sorry if I guess wrong).

anyway, the point is, 1. understand what your code does to performance, 2. understand how fast code should be, 3. write faster code: one nice 'tutorial' by example is :http://macton.smugmug.com/gallery/8936708_T6zQX#593426709_ZX4pZ Edited by Krypt0n

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this