More frustum cull methods

[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:


Sphere:


Cone:


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]

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]

v2 of sphere culling posted.

Have some renders:

[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:

[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]

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]

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]

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.

[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]

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.

[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]

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.

[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]

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]

I'll merge this patch with trunk when I'll finish work related to EAGL manager.