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
Optimizations available for terrain type meshes?
Re: Optimizations available for terrain type meshes?
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.
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.
Re: Optimizations available for terrain type meshes?
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).
Re: Optimizations available for terrain type meshes?
Yup- the v1 terrain had a 'thickness'; it's a pretty simple thing for heightmap terrains.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).
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.
Re: Optimizations available for terrain type meshes?
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.
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.
Re: Optimizations available for terrain type meshes?
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.
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.
Re: Optimizations available for terrain type meshes?
Yup.it did not seem to appreciate being run concurrently (since the Pool is not thread safe, I presume).
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.
Was that while using the Simulation's BufferPool on another thread? That would do it.... 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.
Tree and Mesh now have Serialize and GetSerializedByteCount functions and constructors which take a Span<byte>: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.
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.
Re: Optimizations available for terrain type meshes?
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
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
Re: Optimizations available for terrain type meshes?
One of these days I'll get a pipeline set up* There's no prerelease nuget packets; so I had to include the source projects... which is fine
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 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.
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.
That'll work fine. Can also call Clear. The underlying memory will get collected either way.* 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?