Let me give two methods for doing this that serve different design goals - basically, I am distinguishing here between "compute the surface area of a bunch of cubes" and "approximate the surface area of a shape given the cubes it contains." The difference is that, for instance, while a circle has circumference $2\pi r$, if you take a bunch of pixels in a circular form and then count their actual surface area, you get $8 r$ because instead of sloping smoothly, the edge instead is jaggedly moving in two perpendicular directions.
To compute the actual surface area, the algorithm is pretty simple. I'll assume you're working on a grid with integer coordinates. We can define the Manhattan distance between two positions to be the sum of the absolute differences of their coordinates. You can then implement the following algorithm:
Pick some point that is known to be outside of the ship. For instance, you can do this by finding the block in the ship with the highest $x$ coordinate and then looking at the (empty) block offset from that by $(1,0,0)$.
Run a flood-fill from that point to identify the outside - that is, mark the outside block and then, whenever an empty block is adjacent to an outside block, mark the empty block as outside too and look at its neighbors. Since you probably do not want to flood-fill too much area for performance, you can simplify this by only considering blocks which are within a Manhattan distance of $2$ from the ship - or, perhaps better, you can label blocks outside as "CLOSE" and "FAR" where every non-empty block adjacent to a "CLOSE" block is marked "CLOSE" if it is adjacent to a ship block or "FAR" otherwise and every "FAR" block adjacent to a non-empty block which is adjacent to the ship is marked "CLOSE."
- Count the number of pairs of adjacent blocks, where one block is outside and the other is inside; you can keep track of this quantity during the flood fill.
Then, the quantity in step (3) is the number of cube faces exposed - so the surface area is that quantity times the surface of a single cube face. You can modify this, with some effort, to be able to handle other kinds of blocks, like triangular prisms, that one commonly sees in games - the key is to be able to identify which faces are exterior and then just sum their surface areas.
Note that, by this algorithm, the most efficient way to enclose volume is to build a giant cube - as opposed to in reality, where the most efficient way to enclose volume is a sphere.
If you want to, using purely cube, count a "smoother" measure of surface area, you can do something similar to the previous algorithm where you first identify the blocks which are outside and then find the set of blocks which are not outside but are, in Euclidean distance, within some radius $r$ of the outside. This is more computationally expensive, though you can do it faster than plain iteration if you're careful. Then, the surface area is approximately the total volume of the blocks you found, divided by $r$. This will appropriately identify "round" shapes as having less surface area than blocky shapes, even though the representation is blocky.
