Streaming spherical terrain

Discuss any questions about BEPUphysics or problems encountered.
Post Reply
prollin
Posts: 6
Joined: Wed Jan 22, 2014 1:59 am

Streaming spherical terrain

Post by prollin »

Hello,

We are using BEPU to generate the collision mesh for a spherical terrain (planet) and was wondering what would be the recommended approach.

Being a spherical terrain, BEPU's Terrain can't be used for this purpose therefore we decided to use static meshes generated from the geometry of a few patches of terrain around our dynamic entities.
Since our terrain is large, we need to be able to update the physical terrain as our entities are moving (not every frame, but still fairly often for fast moving entities).
It seems that the only way to do this is to recreate static meshes for each new patch, remove the old one from the space and add the new ones to the space; this seem very wasteful in term of memory allocation (which are not something we want if we want to avoid GC pauses).

Is there a different approach for this kind of usage that I might have missed?

Thanks in advance.
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: Streaming spherical terrain

Post by Norbo »

In v1.X, if GC is unacceptable, some form of source modification will likely be the best option for this kind of problem.

This might be as simple as modifying bits of the StaticMesh to allow you to reuse as much as possible, or you may want to go all the way to a custom spherical terrain collidable if the curvature is sufficient to be relevant from the player's perspective. There's a VoxelCollidableDemo showing a barebones custom collidable implementation in the BEPUphysicsDemos. You would also want to take a look at the TriangleMeshConvexContactManifold and its usages, and the various forms of StaticMeshPairHandler.

An earlier game called Blackspace used a custom collidable based on a spherical cubemap if I remember correctly. Unfortunately, the website seems to be defunct; you might be able to find their article on the implementation in a google cache somewhere.

The internals of pair handling and contact manifolds can get a bit hairy, so if you can get by with a minimal set of changes to make mutable StaticMeshes work, that could end up requiring less effort.

(This is basically a case where the API is trying to protect users from complexity, and while doing so, it is creating complexity for more advanced use cases. For what it's worth, BEPUphysics v2 shouldn't have this kind of issue nearly as often. The design paradigm for the lowest level APIs leans toward "trust the user and expose everything, while preserving speed". I can't say with certainty when v2 will be ready, though.)
prollin
Posts: 6
Joined: Wed Jan 22, 2014 1:59 am

Re: Streaming spherical terrain

Post by prollin »

Thanks for the helpful and fast reply.

Hopefully v2 will solve some of those issues and give developers more control about what is allocated.
prollin
Posts: 6
Joined: Wed Jan 22, 2014 1:59 am

Re: Streaming spherical terrain

Post by prollin »

After further investigation, it seems that the main source of garbage when adding/removing static meshes on the fly comes from the acceleration structure being built (MeshBoundingBoxTree.Reconstruct).
The tree being built is composed of instances of Node/InternalNode that are all classes allocated on the managed heap. A linear tree of small structs would greatly improve this (and make it easier to multithread in the long run).
Digging into the code, I noticed that there are a lot of small methods doing very small amount of work (on one triangle, one ray, etc...); this can be the source of a lot of cache misses and overall sub-optimal performance.

I am sure this is all things you are well aware off since from the look of the tree prototyping code in your scratchpad repo it looks like you are going in the right direction of making things more linear and cache friendly :)

Back to my initial issue, it looks like modifying the StaticMesh code to make them "updateable" or creating a custom collidable both require a GC friendly BVH building algorithm. I might have to start there.
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: Streaming spherical terrain

Post by Norbo »

I am sure this is all things you are well aware off since from the look of the tree prototyping code in your scratchpad repo it looks like you are going in the right direction of making things more linear and cache friendly :)
Yup! There is a lot of low hanging fruit to pick in this regard. v1's constraint solver, for example, scales very well with hyperthreading... mainly because any one thread spends the majority of its time stalled. :P
Back to my initial issue, it looks like modifying the StaticMesh code to make them "updateable" or creating a custom collidable both require a GC friendly BVH building algorithm. I might have to start there.
I could have sworn I built a collect-all-nodes function for use with GC-free Reconstruct at some point, but apparently not. That would be one fairly low effort approach.

Could always use the SIMDPrototyping.Trees.SingleArray tree implementation :) For the purposes of a static mesh, the majority of the functionality can be ignored; Tree.cs, Tree_VHBuilder.cs (which is really a SAH builder at the moment) are the main ones, then Tree_VolumeQuery.cs contains a bunch of different but equivalent bounding box queries. Unfortunately it looks like I didn't get around to ray testing, but it doesn't require much. Using v1's math instead of System.Numerics will slow a few things down a tiny bit, but it shouldn't be too bad- the tree doesn't have a lot of places where SIMD actually helps at the moment.

I'll probably be swinging back to clean up the tree implementation for use in the new broadphase in the next month or two (assuming I keep working on physics rather than swapping back to graphics).
prollin
Posts: 6
Joined: Wed Jan 22, 2014 1:59 am

Re: Streaming spherical terrain

Post by prollin »

Could always use the SIMDPrototyping.Trees.SingleArray tree implementation
I'll take a look, thanks!
Using v1's math instead of System.Numerics will slow a few things down a tiny bit, but it shouldn't be too bad- the tree doesn't have a lot of places where SIMD actually helps at the moment.
System.Numerics is not (yet) supported on a few important platforms (Xamarin.iOS/Android are not supported at the moment). That being said, i have yet to encounter a C# game where SIMD is the first solution for optimization. Runtime allocations (GC pauses) and non optimal memory layouts are usually the #1 culprits (same as most languages).

Thanks again for your help!
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: Streaming spherical terrain

Post by Norbo »

Woops! The actual decent builder is in Tree_SweepBuilder, not Tree_VHBuilder. And I completely forgot I had made a ReconstructPerformanceTest. It contains a little example "Mesh" implementation and compares it to v1's StaticMesh.
prollin
Posts: 6
Joined: Wed Jan 22, 2014 1:59 am

Re: Streaming spherical terrain

Post by prollin »

Just a small followup.

I went the StaticMesh route for simplicity. Up until now I was creating a new StaticMesh from a reused pool of vertex array and a common index array, for each new terrain chunk that is streamed . As terrain chunks get further away, the associated StaticMesh is removed from the Space and the vertex array is returned to the pool.

Profiling this code was no surprise: tons of InternalNode allocations as I create new StaticMesh on the fly (player is fast moving).

I just realized that a potential optimization would be to change the vertices in the StaticMesh's vertex array in place and then trigger a "Refit". This way I can pool the StaticMeshes and the tree is never recreated.

My question is does this actually works even if the new vertices can have very different values (topology doesn't change though)? It seems to not cause issues with my initial testing but I was wondering if there are some performance impact with reusing an existing tree with different vertex positions (but same topology).
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: Streaming spherical terrain

Post by Norbo »

If it has the same topology, correctness will be maintained by a refit. It can indeed have performance impacts. Generally speaking, the more different the new version is from the original version, the worse performance will be.

It might still be fine, though. For example, the BVH of a simple heightmap mesh with all near-zero heights will tend to cluster subtrees based on horizontal position. It'll behave a little bit like a quadtree (except probably lower quality since the incremental builder doesn't have enough information to make good splits at the top nodes). So long as the BVH is approximating a quadtree, refitting based on new heights will still approximate a quadtree's behavior.

Since the distance from one fully 'deformed' terrain to another is typically larger than from an undeformed terrain to a deformed terrain, building the BVH in a neutral state may improve the worst case (and, of course, hurt the best case).

Of course, measuring the performance always beats theorizing.
Post Reply