Heightfield Raycast Performance

[dave]

I've created a big heightfield (32768 x 32768) and I'm trying to simply cast some rays on it. I'm using ClosestRayResultCallback and m_DynamicsWorld.rayTest. If I give to and from points for the ray diagonally parallel to the terrain it takes 2+ seconds to complete a single raycast. If I fire a ray exactly down it's very quick. Most long diagonal rays at any angle take huge amounts of time (50ms to several seconds). And I'm on a powerful modern desktop.

Can anyone speak to why this is and how(or if) I can get real-time performance out of it? Ultimately I need to cast 10k+ rays in <50ms (on a quite powerful server).

[CookieMonster]

The more height values the line cross, the more data have to be loaded to the CPU.

The (RaycastTerrain) sample from (DirectX SDK february 2010) is using deferred cone step mapping that handle about 500000000 lines per second on a smaller height field.

[joschu]

If all your rays happen to emanate from the same point, you can render the shape using OpenGL and then read out GL_DEPTH_COMPONENT.

[dave]

If I break up my long ray into hundreds of short rays it significantly improves performance (200x improvement in the worst case which was a 45degree angle on all axis). It appears to make an AABB around the ray so the AABB increases exponentially as the ray length increases, ever encompassing more and more terrain to check.

I also went and started using multithreading (btParallelConstraintSolver and SpuGatheringCollisionDispatcher) which showed little to no performance increase. Perhaps terrain and/or raycasts aren't written to benefit from it?

I'm still running 3 orders of magnitude under what I need. Any ideas/info is appreciated!

[xexuxjy]

Thats pretty much exactly what it does , creates an AABB and then runs a callback triangle/ray intersect on each triangle covered by that area.
Out of interest are you running in debug or release? as there is a noticeable difference between the two on this operation.

[dave]

This is in release. Can you confirm that I should be seeing no improvement from multithreading for this operation? Can I call DynamicsWorld::RayTest from multiple threads at the same time safely? Maybe I should be doing that instead of or along with using btParallelConstraintSolver and SpuGatheringCollisionDispatcher.

Is there no normal use case for casting rays on dense terrain? I would think many people would be running into this. If terrain was stored in an octtree the ray cast could only perform triangle/ray intersection on a single node of the tree regardless of the size of the ray. It would also be highly beneficial to have the option to cast a ray that doesn't use an AABB, as an AABB has a cubic volume increase as length linearly increases in the worst case for a ray, making it pretty horrible when the ray's AABB encompasses my entire world.

At this point I think I need to consider trying to extend bullet to suite my needs or rolling an independent terrain/raycasting system. Thoughts?

[xexuxjy]

It may be worth trying your rayCast in multilpe threads , this post contains a little useful information : http://bulletphysics.org/Bullet/phpBB3/ ... f=9&t=4693 .

I agree that a form of quad / octree accelerator on top of heightfield would be rather useful. The simplest option for now is to split your heightfield into smaller sections (almost the same thing I know) and have multiple btHeightFieldTerrainShapes registered in the body.

[dave]

I split my heightfield into various granularity of sections (from 32 to 16k sub-heightfields) and stuck them in a btCompoundShape. It made between -20% and +20% performance difference(not enough).

This may be naive, but why does the ray need an AABB? Shouldn't it just be traversing through the world's octtree and only testing against collisionshapes as it passes through a leaf node that contains an object? Or at least an OOBB would help a ton.

I changed things up and made 4096 boxes aligned in a grid and cast the same long ray I was casting for the terrain 1000 times a frame and ran at 12fps. Also unacceptably slow for my use case.

Anyone have any more ideas or explanations? Thanks for the help so far!

[xexuxjy]

Sorry if you've already mentioned it but which broadphase are you using for your app?

[dave]

btAxisSweep3