Optimizations available for terrain type meshes?

[JumboTree]

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]

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.

[lidgren]

Your assessment matches my findings exactly. Construction is slow, 5 seconds in my case, and memory usage is high (~300mb) but performance is still very good afaict. If there's feature voting somewhere a terrain primitive have my vote; perhaps it could be more stable/robust than a mesh as well? (Ie. being "solid" infinitely downwards, preventing objects dropping thru even without continuous detection).

[Norbo]

perhaps it could be more stable/robust than a mesh as well? (Ie. being "solid" infinitely downwards, preventing objects dropping thru even without continuous detection).

Yup- the v1 terrain had a 'thickness'; it's a pretty simple thing for heightmap terrains.

With regard to reducing mesh construction time, there are some other potential paths:
1) Split large environment meshes into multiple meshes and create them in parallel. The sweep builder is O(n * log(n)^2), so splitting and running them in parallel can give you superlinear performance improvements. That adds a layer of application complexity, but heightmap-ish meshes are usually pretty easy to split. One downside: triangle boundary collisions won't be smoothed across different collidables. (That's something I'd want to address if I worked on a large scale terrain feature- both for the terrain and meshes.)
2) If the mesh is loaded, the tree can be precomputed and loaded too. Copying a tree's buffers from a content archive would be effectively instant compared to the full sweep builder.
3) The full sweep build could be avoided by building a tree using incremental insertion. The quality will be very low compared to a sweep build, but using RefitAndRefine iterations over several frames will bring the quality back up close to the sweep builder's quality without a single giant computational chunk. This is what the broad phase does.

I've also got a rework of the tree planned. It would drop the sweep builder to O(n * log(n)) with significantly lower constant factors- 10x faster on large meshes is conceivable. There'd also be a parallel path. Not sure when I'll get around to it, though.

[lidgren]

Yes, going wide was my first thought; but BepuPhysics.Collidables.Mesh constructor was the bulk of the work and it did not seem to appreciate being run concurrently (since the Pool is not thread safe, I presume).
Building the shape offline, in the pipeline step, would be the best - but I'm uncertain how to serialize and deserialize something like BepuPhysics.Tree.Tree - having serialization methods from/to a ReadOnlySpan<byte> for that type, or even better for Mesh, would be awesome.

[lidgren]

Creating a new pool for each terrain patch (currently 256 patches) results in a near linear speedup over number of cores; but the memory usage is almost doubled.
Creating just 4 pools, acquiring/releasing/blocking gives a 4x speedup (actually a little more; I have some overhead other than Mesh ctor) and only seems to add 10mb or so as overhead; so this is a nice compromise for now.
... I did see an odd crash in BepuPhysics.Trees.Tree.RefitAndRefineMultithreadedContext.RefitAndRefine - but only once, so can't tell if it's related or not.

[Norbo]

it did not seem to appreciate being run concurrently (since the Pool is not thread safe, I presume).

Yup.

Notably, it is possible to preallocate everything so you don't have to pull from a BufferPool on any of the worker threads. It would involve bypassing the existing constructor though.

... I did see an odd crash in BepuPhysics.Trees.Tree.RefitAndRefineMultithreadedContext.RefitAndRefine - but only once, so can't tell if it's related or not.

Was that while using the Simulation's BufferPool on another thread? That would do it.

Building the shape offline, in the pipeline step, would be the best - but I'm uncertain how to serialize and deserialize something like BepuPhysics.Tree.Tree - having serialization methods from/to a ReadOnlySpan<byte> for that type, or even better for Mesh, would be awesome.

Tree and Mesh now have Serialize and GetSerializedByteCount functions and constructors which take a Span<byte>:
https://github.com/bepu/bepuphysics2/co ... 1c33989d18

Couldn't use ReadOnlySpan without significant tradeoffs due to .NET Standard 2.0 limitations, so Span will have to do for now.

[lidgren]

Awesome! Integrated this and load time are now improved from the initial 5 seconds wall, via 1 second using 4 threads, to 50 milliseconds wall by using 4 threads and pipeline precomputed mesh shapes
A slight downside is the disk content for the terrain went from 2mb to 80mb; but this is absolutely acceptable.

A few observations from the integration:
* There's no prerelease nuget packets; so I had to include the source projects... which is fine
* I decided to compile them as .net code 3.1 (why keep it easy) and there were a ton of errors relating to uninitialized variables. Most of them seem related to having 'ref' semantics where 'out' semantics would be more proper, but perhaps this is necessary in many places due to do with the unmanaged nature of bepus memory handling? Two things that stuck out was the Depth field of ManifoldCandidate weren't set in many places, and if GatherScatter.Get was an 'out' many errors would be fixed.
* Running the mesh creation in the pipeline I just new:ed up a BufferPool for use and it asserted out with "Memory leak warning! Don't let a buffer pool die without unpinning it!"... I just set Pinned = false at the end since i have no idea what i'm doing Was that a horrible hack or just fine?

Thanks again for super fast responses!

--michael

[Norbo]

* There's no prerelease nuget packets; so I had to include the source projects... which is fine

One of these days I'll get a pipeline set up

* I decided to compile them as .net code 3.1 (why keep it easy) and there were a ton of errors relating to uninitialized variables. Most of them seem related to having 'ref' semantics where 'out' semantics would be more proper, but perhaps this is necessary in many places due to do with the unmanaged nature of bepus memory handling? Two things that stuck out was the Depth field of ManifoldCandidate weren't set in many places, and if GatherScatter.Get was an 'out' many errors would be fixed.

When referenced in a .NET Standard 2.0 project, System.Numerics.Vectors types are empty stubs. Roslyn sees the empty stub and says, oh, okay, nothing to initialize here.

I may have abused that behavior thoroughly to avoid unnecessary zero inits that localsinit stripping couldn't remove.

That is something I plan to address once .NET 5 rolls around with Unsafe.SkipInit. It's not impossible to fix right now, but it would be a lot easier then.

* Running the mesh creation in the pipeline I just new:ed up a BufferPool for use and it asserted out with "Memory leak warning! Don't let a buffer pool die without unpinning it!"... I just set Pinned = false at the end since i have no idea what i'm doing Was that a horrible hack or just fine?

That'll work fine. Can also call Clear. The underlying memory will get collected either way.