ConvexHullShape that takes pre-centered vertices

[ecosky]

Hi Norbo,

I recently added support for ConvexHullShape objects to my asset pipeline and it appears there is currently no way in Bepu (at least in my version, which I think is current in this regard) to create a ConvexHullShape without having it do a number of one-time calculations that seem better suited to the content pipeline.

To save runtime costs, I now create a ConvexHullShape in the content processor and extract the surface local vertex array, the minimum/maximum radius, the center and the volume of the ConvexHullShape. When the game prepares an asset that needs this ConvexHullShape, I now create one using a new constructor:

Code: Select all

	    public ConvexHullShape(Vector3[] localSurfaceVertices, float minRadius, float maxRadius)
	    {
			if (localSurfaceVertices.Length == 0)
				throw new ArgumentException("Vertices list used to create a ConvexHullShape cannot be empty.");

			vertices = new RawList<Vector3>();
		    vertices.Elements = localSurfaceVertices;
		    vertices.count = localSurfaceVertices.Length;
		    minimumRadius = minRadius;
			maximumRadius = maxRadius;
		}

As you can see, this constructor merely copies the input array. For my purposes, I don't intend to ever change the resourced vertex data so it seems OK for me to share the vertices across any users of the data, but maybe that would be a concern for other people but I can't imagine that really being the case. I just didn't want to duplicate the data without a clear reason for it.

Additionally, I wanted to preserve the volume of the convex hull that is calculated within the content pipeline, so I added a new constructor overload that returns the calculated volume. I preserve that in my serialized data.

Code: Select all

		public ConvexHullShape(IList<Vector3> vertices, out Vector3 center, out float volume)

After I create the ConvexHullShape in the pipeline with this ctor, I extract the localSurfaceVertices and serialize those along with the rest of the calculated values.

Something I wonder about is how the ConvexHullShape doesn't actually retain the volume internally; it seems the creation of CompoundShape objects would be incurring extra cost when dealing with ConvexHullShapes within the compound since it looks like it is calling ComputeVolume which re-evaluates all vertices to calculate the volume whenever the volume is needed. I haven't done buoyancy with Bepu yet but it seems like it might help if the volume were cached? That's why I originally wanted to retain the calculated volume, I assumed that I would need to restore a cached value but it seems there isn't a cache value to set. Thanks for any insight there.

It would be great if these or functionally similar changes were to make their way into Bepu code at some point, or if you have a better suggestion about how to reduce runtime costs of creating convex hulls that might be even better.

Thanks,

[Norbo]

The latest source now has a similar constructor for taking cached data.

it seems like it might help if the volume were cached?

Volume is (was) stored as a property of an Entity. This is a bit of legacy from when Volume was actually mutable for the configuration of buoyancy. The mutability of that property has since been replaced by a FluidVolume-specific solution, leaving Volume as a read only property. I'm currently working on moving it into the EntityShape.

A bunch of stuff follows suit:
-EntityShapes contain both a Volume and VolumeDistribution.
-Entity can no longer be initialized using a volume.
-If no local inertia tensor is specified in the constructor, the entity constructor bases its inertia tensor on the scaled volume distribution of the shape. In contrast to the previous fallback which asked the Shape to compute a new inertia tensor, this is just a few simple multiplies.
-A bunch of instance method helpers on the EntityShape became redundant; the implementation requirements have been reduced significantly.

The end result is a cleaner separation of responsibility and a centralization of initialization effort. To fully initialize an EntityShape without any preprocessing, the collision margin if convex, the min/max radii if convex, the volume, and the volume distribution should all be specified in addition to any shape-specific information like local surface vertices.

The creation of entities, which used to be the most expensive part if inertia/volume were not cached, should become irrelevant as a performance consideration in almost all use cases with no special effort.

I should be able to get it fully implemented by late tomorrow.

[ecosky]

That's great, Norbo. Thanks!

I have some comments in regard to the use of preprocessed (and never modified in this case) data such as the localSurfaceVertices. I will go out on a limb and say that I think it would be a good goal for Bepu in general to consider and support when possible the optimal use of immutable "resource" data for initializing physics objects (from what I have seen so far, the focus right now seems to be more about the dynamic creation and modification of objects). Resource data should generally match the internal format of whatever the target objects are so the entire collection can be copied by reference instead of deep copied.

There is a good example here for using resourced data with the ConvexHullShape: A constructor (or static method CreateFromResource which would make it clear this is for use with resourced data that shouldn't be modified) that took Vector3[] and just directly stored the array in the RawList instead of duplicating all the members of the IList into a new RawList would be (IMHO) both appropriate and worth doing to keep memory pressure down. If the RawList had a constructor that didn't allocate the minimum sized array, possibly protected and accessed only by a static CreateRawListFromResource(T[]) or something along those lines, then the ConvexHullShape could be constructed without the allocation of new memory used only to duplicate data with no particular benefit to having a unique copy - no benefit, at least, to scenarios where the ConvexHullShape is being used only with preprocessed data. Multiple ConvexHullShapes could share the same vertex array. Ideally, CreateRawListFromResource would debug-flag the array as immutable and debug builds would detect changes that shouldn't be happening to resourced data.

Disabling the duplication of vertices matters, to me at least, because in my case I sometimes use ConvexHullShapes in an compound shape that is occasionally posed to match a character's animation ; each character right now would duplicate the convex vertices even though there is no real need for that. I can't share the ConvexHullShape because each of the characters is animated, and the animation will have the shapes using a different local transform if they are part of a CompoundShape. While the memory pressure from a typical convex object isn't all that much, the creation of new game units is always a performance bottleneck and it is for me I have about 900 vertices across 16 convex hulls synchronized with a character that are used for projectile hit detection. That's 16 arrays with a total of about 11K bytes being iterated/copied when I really have no need for a fresh copy, so it would be nice to prevent it from happening (which I do in my local branch through changes similar to what I've described above) just in order to keep the already heavy cost of spawning units as small as possible. This is all pretty complicated and there's a good change I could be doing something better or more optimally, but it's working pretty well and as it is.

While we're on the topic of making things resource/serialization-friendly, the other related thing that I've had even bigger performance issues with is related to the StaticMesh. I have a level mesh of around 150k triangles. When it is initialized, it goes through and builds the internal tree structure as you know. On the XBox it takes a few seconds to do. I'd like to preprocess that tree data and provide it to a constructor of the StaticMesh because I suspect it would virtually eliminate the setup cost. I looked into doing that myself, it seemed pretty straightforward and I might do it sometime if you don't beat me to it.

Obviously, my general goal here is to preprocess physics data as much as possible to keep runtime costs at a minimum, so any improvements you might make in that area would be welcome.

Thanks again,

[Norbo]

Resource data should generally match the internal format of whatever the target objects are so the entire collection can be copied by reference instead of deep copied. ...A constructor (or static method CreateFromResource which would make it clear this is for use with resourced data that shouldn't be modified) that took Vector3[] and just directly stored the array in the RawList instead of duplicating all the members of the IList into a new RawList would be (IMHO) both appropriate and worth doing to keep memory pressure down.

I am extremely hesitant about allowing users to supply a regular mutable array reference for ConvexHullShape construction specifically. A deep copy, for a small cost, makes a whole class of extremely sneaky bugs completely impossible. Each unit of safety sacrificed demands a big performance boost.

Even with an "advanced" use case with assumptions of user understanding like this, I can't quite bring myself to make the trade. I have a feeling that, down the road, even I might forget and try to use a pooled array to create a shape. I've stepped on enough of my own landmines in the past

That said, using an actual immutable data type as a parameter to the constructor would indeed accomplish the same safety goal as the copy. However, the simple implementations of those end up involving copies anyway, and the more complicated approaches are a little bit heavy compared to the potential benefit for ConvexHullShapes specifically.

Multiple ConvexHullShapes could share the same vertex array.

Two ConvexHullShapes with the same vertex array should only potentially differ in their collision margin. In almost all cases, the better option would be to share one ConvexHullShape.

I can't share the ConvexHullShape because each of the characters is animated, and the animation will have the shapes using a different local transform if they are part of a CompoundShape.

The same shape instance should be reusable with different transforms. The transforms are properties of whatever is using the shape, as opposed to properties of the shape itself.

While we're on the topic of making things resource/serialization-friendly, the other related thing that I've had even bigger performance issues with is related to the StaticMesh. I have a level mesh of around 150k triangles. When it is initialized, it goes through and builds the internal tree structure as you know. On the XBox it takes a few seconds to do. I'd like to preprocess that tree data and provide it to a constructor of the StaticMesh because I suspect it would virtually eliminate the setup cost. I looked into doing that myself, it seemed pretty straightforward and I might do it sometime if you don't beat me to it.

The plan is to revamp pretty much all of the hierarchies scattered around the engine. Part of that revamp would be an abstraction of the construction process which supports both quick dynamic construction and extremely slow offline construction. With a decent sized mesh and high quality parameters, offline construction methods can take multiple minutes on a high-end desktop PC, so they would absolutely require some caching mechanism.

This data will likely be protected by immutable structures of one kind or another. At the very least, it should be very difficult for someone to accidentally do something wrong when using the cached data.

I'm not sure when I'll get around to this- it's a big change, but an important one. I'll probably hit it during one of my optimization rounds during v1.4.0 as it becomes necessary.

[Fun side note- based on the work I did in my ray tracer prototypes:
-I can probably create new real-time dynamic refit hierarchies, like the current default broad phase, which slightly outperform the current StaticMesh hierarchies in runtime performance while allowing deforming objects and topology changes.
-I can probably get medium-speed-construction trees about 50% faster in runtime performance compared to the current StaticMesh hierarchies, with similar construction cost. I might not bother with this middle tier.
-The offline-constructed trees will probably be more than twice as fast as the current StaticMesh hierarchies in runtime performance.]

[ecosky]

Thanks for the detailed and informative response, as always.

Eliminating the copy for ConvexHullShapes isn't nearly as much of an issue if I can share the shapes as you explained. I'll dig into that some more, I'm sure you are right as usual on that. It would still be nice to have the resourced data not get copied at all using an immutable.. perhaps adding a new ImmutableConvexHullShape class would make more sense to avoid the bugs you are referring to since you could limit the ability to modify data in ways you wouldn't want to do to the ConvexHullShape. Just an idea, maybe not doable, but I have a tendency to want to minimize resource initialization costs since they often seem to creep up into amounts that do matter. Not duplicating vertex data for StaticMesh types would be much more important because the number of vertices for level data can be several orders of magnitude than simple convex hulls we've been talking about. I'd hate to think that streaming in a part of a map with 100k vertices had to duplicate them for no practical benefit other than making sure the programmer didn't muck with the data when they shouldn't have; streaming world data is already a very expensive operation so any extra work is to be avoided. I can see your point though. Personally I'd prefer to detect the misuse in a debug build rather than force a suboptimal solution. Perhaps it could, in a validation mode, confirm that the data is what it should be and have the best of both worlds?

I'd love to see the static mesh get performance improvements like you are talking about. Static mesh level data is one of those fixed costs I'd expect a lot of your users have and this would seem like a great performance boost for a large percentage of your users if these offline, time consuming improved tree builders were available.

Thanks

[Norbo]

The big bunch of changes have been committed. I've done a little basic testing, but I suspect I missed a few corner cases. I'm going to be doing a bit more testing tomorrow. I might also have time to implement a new tetrahedral integrator for volume/inertia stuff- if it works out, it should cut ConvexHullShape, TransformableShape, WrappedShape, and MinkowskiSumShape initialization time in half or better.

Not duplicating vertex data for StaticMesh types would be much more important because the number of vertices for level data can be several orders of magnitude than simple convex hulls we've been talking about.

Meshes are indeed much fatter and also tend to have a more specific input format/usage pattern that makes it hard to accidentally share data or make similar errors. If it comes down to it, I'll probably compromise safety for performance with meshes.

[ecosky]

Very cool. It's great to see how Bepu keeps improving.

I won't be able to integrate these changes for a few weeks but I am definitely looking forward to it.