Back to General and Gameplay Programming

Very fast 2D frustum culling

General and Gameplay Programming Programming

Started by deathchaser September 05, 2014 08:52 PM

5 comments, last by Krypt0n 9 years, 7 months ago

deathchaser

114

Author

September 05, 2014 08:52 PM


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)

Aqua Costa

3,705

September 05, 2014 09:13 PM

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

Irlan Robson

4,091

September 06, 2014 01:02 AM

Use a Quadtree.

Krypt0n

4,769

September 06, 2014 01:23 AM

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.

video game porting and optimization service + consulting

Hodgman

52,717

September 06, 2014 02:09 AM

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.

. 22 Racing Series .

deathchaser

114

Author

September 06, 2014 09:58 AM

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

Krypt0n

4,769

September 06, 2014 03:28 PM

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

video game porting and optimization service + consulting

Very fast 2D frustum culling

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Very fast 2D frustum culling

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines