Each image describes a different algorithm. I would say the top two should not even be in the question. Bottom right is too angular to look good in-game, it looks like luggage in plastic cling-wrap. Let's focus on bottom left, probably the best looking approximation of the original mesh.

I think what you want is the [3D Minkowski sum](http://allenchou.net/2013/12/game-physics-collision-detection-csos-support-functions/) of the original mesh, either (1) by getting a convex hull first and then applying the Minkowski summation algorithm to it, or (2) just do Minkowski sum on its own. Obviously the latter will have convex spaces, but inner corners like this may appear "pinched", see for example the space between the two children's heads at top left:

[![enter image description here][1]][1]
[![enter image description here][2]][2]

So you may do need to do some smoothing after summation, as well. You will notice in the image above that a somewhat cubic mesh has been summed against the original mesh, while in the image below, different operators are shown. You'll want pointwise or spherewise summation as shown for the dinosaur and bunny:


[![enter image description here][3]][3]

This technique is common in computational geometry and GIS applications, so you can find implementations in typical comp geom libs like GJK, CGAL etc. You could even download such and use it as proof of concept. I can't guarantee the performance on this will be great, since often those libs are not geared to real-time use. But it gives you a place to get started and you can a write a realtime implementation on your own (may require mesh reduction to get the required speed).

Note that _voxelised Minkowski sum_ can yield better performance than traditional, more exhaustive approaches because the vertex count is strictly limited by the number of voxels. Google will help.

  [1]: https://i.sstatic.net/I0erH.jpg
  [2]: https://i.sstatic.net/GKgPO.jpg
  [3]: https://i.sstatic.net/Aj78c.jpg