Optimizations available for terrain type meshes?

Discuss topics related to BEPUphysics or physics engine development.
Post Reply
JumboTree
Posts: 2
Joined: Sat Jan 18, 2020 4:17 am

Optimizations available for terrain type meshes?

Post by JumboTree » Sat Jan 18, 2020 4:32 am

Hi i was wondering if a shape type for terrains specifically could be added (or if thats even needed). By this i mean a 'static deformed plane with equally spaced vertices with no overlaps'. I'm not sure how collisions work with meshes but maybe since you know that the vertices are equally spaced optimizations can be done on choosing which triangles to perform collision detection with? TBH i don't know much and would like to know if such a thing would even improve performance over the current implementation of collision checking on a mesh in this library (does it check ALL the triangles in a mesh or is there a system for culling checks that are not needed?).

I know that the C# Library "JitterPhysics" supports, among others, two shapes called 'TriangleMesh' and 'Terrain'. So maybe there are some optimizations for this specifically? I would really like some input from someone more experienced, thanks :)

Norbo
Site Admin
Posts: 4835
Joined: Tue Jul 04, 2006 4:45 am

Re: Optimizations available for terrain type meshes?

Post by Norbo » Sat Jan 18, 2020 11:26 pm

Mesh shapes use a tree (specifically, a binary tree created by SAH sweep builder) to accelerate collision testing. It performs a log(n) query to find the triangles with overlapping bounding boxes. Only those triangles are tested.

Terrains do indeed have regularity that can be exploited to help with test acceleration. Its main benefits would be faster construction and lower memory use. For example, if you discretize a bounding box into terrain grid cells, you can look up the terrain quads that the bounding box could overlap horizontally in constant time. In many cases you'd want to go further and add a bit more tree-like information to avoid testing a bunch of individual cells that are all too low to overlap the query vertically (and to help accelerate ray tests more than a grid walk), but it wouldn't need as much as an arbitrary mesh. Runtime performance could also be marginally faster with some effort, but it would be pretty difficult to notice.

Notably, bepuphysics v1 did have a dedicated Terrain type. I didn't bother including one in the first release of v2 because the advantages are pretty slim and the development effort was better spent elsewhere. I might eventually add one in, but it won't be a very dramatic change outside of a few extreme use cases.

Post Reply