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.