Creating force shields: the most efficient way of deforming/reshaping a simpler convex mesh so it envelopes a complex mesh?

Question

So, the best way I can think of how to explain what I need is the following (images used here are just random images found trough google image search).

What I am trying to create during run-time is pretty much the same as a force shield that envelopes a robot or a space ship in many different futuristic types of games.

However, considering that these robots or ships have a shape that is unknown in advance, I don't want to just use a sphere-mesh around the ship or just assign a shield-shader directly to the ship mesh like in the pictures below:

I want to end up with a shield that is formed by a mesh that loosely represents the shape of the ship. Something like what can be seen in the pictures below:

However, I don't need those shields to be concave like in that pictures. It can be a convex mesh.

So far, what I've tried was to generate a sphere or a cylinder around the complex mesh (robot/ship), loop trough each vertex and try to approximate to the complex mesh. However, that is severely inefficient and gives non-smooth results.

Would you happen to have any idea, code sample, tutorial links, article references or anything on how can I proceed to get what I want in an efficient manner? The shields do not have to very detailed in terms of polygons. In fact, the less the better.

I am currently using C#, but I can handle C++ as well. Thanks in advance.

Answer 1

Each of your images 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, the best looking approximation of the original mesh.

I think you want the 3D Minkowski sum 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 M-sum on its own. For a convex base mesh, the latter will have convex spaces, and inner corners may appear "pinched", see for example the space between the two children's heads at top left:

So you may do wish to do some smoothing after summation, depending on the sort of look you're going for. You'll also notice in the image above that a cubic mesh has been summed against the original mesh, which results in cubic artifacts, while in the image below, different operators are shown. You'll want pointwise or spherewise summation as shown for the dinosaur and bunny:

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.

Answer 2

Sliced 2D Convex Hulls Slice through the mesh (polygon + axis-aligned plane intersection), getting the convex hull of each resultant 2D polygon, e.g. from tip to tail for a ship like that in your image, or from head to toe in a humanoid - as you'd slice a carrot :) These could be equidistant slices or spaced according to some heuristic, but will describe the mesh with a good amount of accuracy albeit leaving out certain convex details. To clarify: You're not actually cutting up the original mesh, instead you're just taking scans through it's geometry, much like a CT scan - slices are frequently used in medical imaging applications. You can then scale each of these slices up, join / triangulate / tesselate them, and cap the mesh at each end with additional vertices.

EDIT In slicing down the length, you need to first get a cross section as though you are cutting the ship in left and right halves. Then calculate the 2D convex hull of that. The vertices of that 2D convex hull can be used to decide where you slice from nose to tail (like ribs). If not done, local maxima like spikes on the ships surface may be missed. The actual tip-to-tail slices may or may not be convex, but I guess skipping the convex hull calculation on these will result in lower cost overall.

This might suit what you're trying to do quite well, given your desire for efficiency - which is easy to tweak based on the number of slices - and your flexibility around concavity / convexity. EDIT Since you don't need convexity, this will likely be faster than general purpose quickhull, and a bit easier to conceptualise / configure / debug / control performance. But quickhull might just be more direct.

Answer 3

For a nice artistic look you can voxelize your model in a grid them perform marching cubes. That is you'd end up with a shield with as little or as much detail as you want depending on the grid size. You can also perform a post-processing step on the voxelized grid data to smooth out the mesh before generating the triangles. Or perform a step afterwards to remove unneeded vertices or smooth the mesh (there's probably other algorithms) to get a different look.

Answer 4

One method is to create a mesh by iterating over every vertex of your object and make a vertex normal to the objects surface at that point with an arbitrary magnitude (magnitude of 0 means the shield is the surface). As mentioned this takes time O(cN) where N is the number of points in your original objects mesh.

Now if you want to handle any possible shape or configuration you can attempt to create an easy shape, for example spheres, for each different "part" of the object, then combine the meshes so they do not do not overlap inside the object. If you can efficiently (tree hierarchy) determine the different part of the ship and remove any points in the other mesh this might get where you are trying to go.