More frustum cull methods

Discuss about anything related to the Irrlicht Engine, or read announcements about any significant features or usage changes.
hendu
Posts: 2600
Joined: Sat Dec 18, 2010 12:53 pm

More frustum cull methods

Post by hendu »

Spherical tests tend to be cheaper than box tests, even more so than point tests for every single frustum plane.

The default box culling is also pretty bad when looking at an angle.

Box:
Image

Sphere:
Image

Cone:
Image

https://sourceforge.net/tracker/?func=d ... tid=540678

The patch above is the first step towards implementing the latter two culling methods. Both should be cheaper than the default box, and the cone is by-area far superior to the box.

If anyone is in a hurry, I won't mind seeing these done by someone else ;) if not, I'll do them sometime later.
hendu
Posts: 2600
Joined: Sat Dec 18, 2010 12:53 pm

Re: More frustum cull methods

Post by hendu »

Sphere culling posted.

It's quite comparable in cpu use to the default box method. It could be made cheaper if the bounding boxes of the nodes cached the center and radius, but that's a bit lower in priority than the cone algorithm.

https://sourceforge.net/tracker/?func=d ... tid=540678
hendu
Posts: 2600
Joined: Sat Dec 18, 2010 12:53 pm

Re: More frustum cull methods

Post by hendu »

v2 of sphere culling posted.

Have some renders:
Image
Image
hendu
Posts: 2600
Joined: Sat Dec 18, 2010 12:53 pm

Re: More frustum cull methods

Post by hendu »

Cone-sphere method implemented. Works pretty well. Still need to optimize it, and CBA to post a patch because additive patches on SVN cannot be done - once the sphere method is merged, then the cone one can be posted without much additional work.

Have some more pics, now with all methods pictured:

Image
Image
Image
hendu
Posts: 2600
Joined: Sat Dec 18, 2010 12:53 pm

Re: More frustum cull methods

Post by hendu »

The initial performance numbers from all methods. Average of three runs, testing four million points, all outside the frustum (but some are close).

Measured in usecs.

Code: Select all

        off             431770
        box             580218
        sphere          667337
        cone            930991
        frustum         7597386
hendu
Posts: 2600
Joined: Sat Dec 18, 2010 12:53 pm

Re: More frustum cull methods

Post by hendu »

After some optimizations:

Code: Select all

        off             440754
        box             630294          1.43004
        sphere          651230          1.47754
        cone            800750          1.81677
        frustum         8330480         18.9005
The third column is the time taken compared to EAC_OFF.

Sphere is now about equal to box with a cached radius; center is still calculated and could be cached to speed that up.
Cone went from 2.15 to 1.81, but it's still 26% slower than box. It culls much better though, so it ought to be acceptable now.

I'm out of low hanging fruits, so probably ending here.
Adversus
Posts: 128
Joined: Sun Oct 05, 2008 10:58 pm
Contact:

Re: More frustum cull methods

Post by Adversus »

Did this patch every make it into any of the official releases or is it in the nightly build for irrlicht 1.9?

btw - When I downloaded that I assume that irrlicht-current-core-win32 is the correct file to get. The timestamps don't appear right though however I grabbed it from the mirror http://irrlichtirc.g0dsoft.com/irrbuild/ so maybe that might be an issue.
CuteAlien
Admin
Posts: 9628
Joined: Mon Mar 06, 2006 2:25 pm
Location: Tübingen, Germany
Contact:

Re: More frustum cull methods

Post by CuteAlien »

First patch seems to be applied and second not - if you click the links the patch-tracker tells about the status of each patch. And sorry - don't know about irrbuild versions.
IRC: #irrlicht on irc.libera.chat
Code snippet repository: https://github.com/mzeilfelder/irr-playground-micha
Free racer made with Irrlicht: http://www.irrgheist.com/hcraftsource.htm
Adversus
Posts: 128
Joined: Sun Oct 05, 2008 10:58 pm
Contact:

Re: More frustum cull methods

Post by Adversus »

Sorry I haven't used patching and I'm not even to sure if I could apply it with my version of irrlicht. Is there away to get project with this patch applied?
CuteAlien
Admin
Posts: 9628
Joined: Mon Mar 06, 2006 2:25 pm
Location: Tübingen, Germany
Contact:

Re: More frustum cull methods

Post by CuteAlien »

Well, we haven't applied it so we can't give you a version with it. And I don't know if Hybrid plans to apply this or not at some point. Also not on my todo so far.
IRC: #irrlicht on irc.libera.chat
Code snippet repository: https://github.com/mzeilfelder/irr-playground-micha
Free racer made with Irrlicht: http://www.irrgheist.com/hcraftsource.htm
Adversus
Posts: 128
Joined: Sun Oct 05, 2008 10:58 pm
Contact:

Re: More frustum cull methods

Post by Adversus »

Actually I think I have it patched. It wasn't too hard to just work through it as it was a diff file however it would be really good to know if there's a way of doing this automatically. btw - I use Tortoise SVN.
CuteAlien
Admin
Posts: 9628
Joined: Mon Mar 06, 2006 2:25 pm
Location: Tübingen, Germany
Contact:

Re: More frustum cull methods

Post by CuteAlien »

You can use "patch" tool from the unix-toolchain. There's probably some Windows tools for that as well (I have mingw and cygwin installed on Windows so I just use the Unix-tools there as well). Maybe Windiff can do that on Windows - not sure.
IRC: #irrlicht on irc.libera.chat
Code snippet repository: https://github.com/mzeilfelder/irr-playground-micha
Free racer made with Irrlicht: http://www.irrgheist.com/hcraftsource.htm
Adversus
Posts: 128
Joined: Sun Oct 05, 2008 10:58 pm
Contact:

Re: More frustum cull methods

Post by Adversus »

I have cygwin too. Need it for build tools :-)

Thanks although after looking a bit closer I just realized it was the code for cone frustum culling that I needed. Sphere doesn't really improve it much. Shame - I may have to write it myself.
hendu
Posts: 2600
Joined: Sat Dec 18, 2010 12:53 pm

Re: More frustum cull methods

Post by hendu »

Cone-sphere is mere 10 times faster than frustum-box while culling almost as well, and only 26% slower than default box. Clearly there's been no demand for such culling in over a year ;)
Nadro
Posts: 1648
Joined: Sun Feb 19, 2006 9:08 am
Location: Warsaw, Poland

Re: More frustum cull methods

Post by Nadro »

I'll merge this patch with trunk when I'll finish work related to EAGL manager.
Library helping with network requests, tasks management, logger etc in desktop and mobile apps: https://github.com/GrupaPracuj/hermes
Post Reply