I need an algorithm that calculates the surface area of an unpredictably irregular object.

Question

I'm developing a game that allows players to design their own star ships. The design system uses a cube grid for the player to lay out internal systems and decks, creating a wide variety of shapes that the program then skins with a variety of plating and architecture styles. In order to factor the ship's plating into the design costs, weight factors, etc, I need the system to be able to calculate the exposed surface area of the player's design. This can vary greatly, as the player's design can use a widely varying number of internal cubes, as well as "towers" or other structures extending out of the craft's body.

So, my question is, what sort of algorithm(s) can I use to calculate the design's surface area?

Answer 1

The simplest ansatz, when already dealing with a cube grid, would be just to count the number of cubes, where the boundary surface intersects. That number has to be taken in ratio with the squared edge size of the cubes, for sure.

You would get an better approximation by halving the cube's edges and re-counting again. Etc.

--- rk

Answer 2

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:

1. 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)$.

2. 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."

   3. 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.