search

DanielChappuis / reactphysics3d

Open source C++ physics engine library in 3D
http://www.reactphysics3d.com
zlib License
1.54k stars 223 forks source link

Performance of HeightField colliders and raycasts #187

Closed Zylann closed 3 years ago

Zylann commented 3 years ago

In Bullet physics, there used to be a horrible performance problem of raycasts when heightfields were involved. This was caused by the fact the raycast was turned into an AABB (so it could cover a huge area), and due to how the abstraction worked, every single triangle of the heightmap was eventually checked against the rectangular region. Which is wasteful because raycasts are just segments :p

I made a PR to Bullet implementing a specialization of raycasts for heightfields, using a raytracing algorithm. The idea is that the ray is projected in 2D, and the algorithm iterates forward through each pixel it intersects with, and checks triangle intersections on them. This is fast enough to not even require any acceleration structure, which means it is compatible with editing the heightmap in realtime, without recomputing any cached structure. But of course if the terrain is not editable, precomputing a grid of AABBs can allow to run that same algorithm in a sort of broad-phase first, making it even faster. In the PR you can also find some profiling info.

How is it implemented in ReactPhysics3D? It seems it does the same thing Bullet used to do, checking every single 2D triangle lying inside of the AABB: https://github.com/DanielChappuis/reactphysics3d/blob/23abaa905dff0dfb0672ac2e7c2e472135e44bab/src/collision/shapes/HeightFieldShape.cpp#L242 So it might benefit a lot from that technique.

Or is it what you did in https://github.com/DanielChappuis/reactphysics3d/commit/d0fa4c2755da4042d7794d55ad70992cf949fd6b ?

DanielChappuis commented 3 years ago

Or is it what you did in d0fa4c2 ?

Yes exactly. In the current released version (v0.8.0), the raycast tests are performed with all the triangles of the height field that are inside the ray AABB. Of course, this is slow. As you noticed, I have improved this in the current "develop" branch to only test triangles that are part of cells of the height field grid that the ray crosses.

Note that this is currently implemented in the "develop" branch that will be part of the next released version (v0.9.0).

DanielChappuis commented 3 years ago

I am closing this issue. Do not hesitate to reopen it if necessary.