What's that shape? Inferring a 3D shape from random shadows

Question

Let $P$ be a bounded, simply connected region of $\mathbb{R}^3$. $P$ could be a polyhedron, or a smooth shape, or an arbitrary shape; I'll assume below that $P$ is a (non-degenerate, perhaps non-convex) polyhedron of $n$ vertices.

Suppose you have available a number $k$ of shadows of $P$, projected orthogonally to the $xy$-plane, of $P$ after a random 3D reorientation, uniformly random over the sphere of orientations. You have only the outline of the opaque shadow; no internal details are visible. For example, here are $k=5$ random shadows of a 3D polyhedron:

---

---

You do not know the orientations of the object that produced the shadows, only that they are chosen randomly. Perhaps you know the number of vertices of the polyhedron; $n=20$ above. My question is not the ideal sharp MO question, but still I think there is a substantive issue here:

Q. Under what circumstances can one (approximately) reconstruct $P$ from the $k$ shadows?

It seems that as $k \to \infty$, there should be a convergence-to-$P$ result. As this is a natural question,¹ I expect it has been explored in the literature, in which case, pointers would be appreciated.

---

Click inside the region below to see the polyhedron that produced the five shadows above:

---

One can view my question as a randomized version of the orthogonal Gödel, Escher, Bach GEB projections:

(Of course, the same question can be asked for objects in $\mathbb{R}^d$ shadow-projected to lower-dimensional hyperplanes.)

---

¹ _{Watching the shadow of a hanging object twisting in the wind is a commonly encountered instance.}

---

Addendum. Several have pointed out that certain shape features are hidden from influencing any shadow, and so cannot be reconstructed from shadows, even with known orientations. It turns out that the shape that can be reconstructed is known as the visual hull (which I found by searching for "shadow hull"):

Laurentini, Aldo. "The visual hull concept for silhouette-based image understanding." IEEE Trans. Pattern Analysis Machine Intelligence, 16.2 (1994): 150-162. (Journal link.)

This Laurentini paper points out that the visual hull of a polyhedron is not always itself a polyhedron: Its surface can in general have curved surface patches. There is work on reconstructing the visual hull when the orientations producing the shadows are known:

Matusik, Wojciech, Chris Buehler, and Leonard McMillan. Polyhedral visual hulls for real-time rendering. Springer Vienna, 2001. (PDF download.)

And Dustin Mixon identified literature addressing unknown orientations:

Singer, Amit, and Yoel Shkolnisky. "Three-dimensional structure determination from common lines in cryo-EM by eigenvectors and semidefinite programming." SIAM Journal Imaging Sciences. 4.2 (2011): 543-572. (Journal link.)

Answer 1

This is very similar to the cryo-electron microscopy problem: You want to image a certain macromolecule, and the scale of the macromolecule requires the use of an electron microscope. Unfortunately, such an imaging process is harmful to the specimen. In the 80s, they realized you can protect the specimen by freezing it first, but a single exposure will undo the protection. As such, they freeze a bunch of identical macromolecules (which end up at unknown orientations), and then image each one, producing a two-dimensional projection image (similar to your shadow). The cryo-EM problem is to recover the three-dimensional macromolecule from these images (see this paper and references therein)

Answer 2

If you have no information about the vertices and allow nonconvexity there could be problems first you will only get information about the surface of the 3d shape but even there you will have problems. If you remove a tiny cube near the center of one of the faces of the cube the surface will not be the same but I don't think it will make a difference in the projections. So I don't think all nonconvex polyhedra will be inferred from shadows but maybe convex polyhedra will.

Answer 3

Shape-reconstruction from shadows will definitely be impossible for "modified convex" polyhedra, that are topologically equivalent to a sphere and can be generated from a corresponding truly convex polyhedron via excavations, that do not destroy edges or vertices; take for example a model of the surface of a convex polyhedron made of thin plates for the faces and remove one of those faces.
The situation is however different if the surface of the 3D body doesn't contain straight-line segments.

Edit
I dare to conjecture, that a necessary and sufficient criterion for 3D shapes, which can be reconstructed from projections onto 2D planes is, that for every boundary point $p$ there exists a straight line through $p$ that doesn't intersect the interior of the 3D shape.

Answer 4

If you are given the orientations that produced the shadows, then I think you can define the shadow hull of a polyhedron (equal to the convex hull for a convex polyhedron), and you can recover the shadow hull to arbitrary accuracy.

However, if you are not given the orientations, you might not be able to reconstruct them up to rigid motions. For example, consider a cube with thin tubes punched out perpendicular to the faces. If the tubes are thin enough and away from the edges, you can only see the tubes punched through one pair of opposite sides at a time. If you punch out a circular tube parallel to the $x$-axis and an axis-parallel $2\epsilon \times \epsilon$ rectangle parallel to the $z$-axis, then from the shadows you can't tell whether the long sides of the rectangle are parallel to the $x$-axis and circular tube, or whether the short sides of the rectangle are. This example is not simply connected, but that's not important. If simple-connectivity is desirable then this example can be made simply connected by cutting to the tubes with a thin curved knife that does not meaningfully change the shadows.

Answer 5

Joseph: this `answer' is perhaps more a comment than an answer, so apologies in advance. The deepest geometric work I know of is this wonderful piece by Mohammad Ghomi. I quote from his web page:

``Solution to the shadow problem in 3-space, in Minimal Surfaces, Geometric Analysis and Symplectic Geometry, Adv. Stud. Pure Math, 34 (2002) 129-142.

If a convex surface, such as an egg shell, is illuminated from any given direction, then the corresponding shadow cast on the surface forms a connected subset. The shadow problem, first studied by H. Wente in 1978, asks whether a converse of this phenomenon is true as well. In this report it is shown that the answer is yes provided that each shadow is simply connected; otherwise, the answer is no. Further, the motivations behind this problem, and some ramifications of its solution for studying constant mean curvature surfaces in 3-space (soap bubbles) are discussed.''

Answer 6

In the case where you also have to deal with small signal-to-noise ratio, the problem of deducing the relative orientations the projection came from becomes a lot more challenging. There is a good series of paper by my PhD adviser Veit Elser and his former student Duane Loh on this problem, which they call cryptotomography. They derive information theoretic bounds on the limit of noise that allows faithful reconstruction. In their specific application they are actually interested in slices of Fourier-space data, since the data comes from X-ray diffraction, but their methods and theory also apply to projections of real-space data.

A sample:

Elser, "Noise Limits on Reconstructing Diffraction Signals From Random Tomographs"

Loh, Borgan, Elser, et al., "Cryptotomography: Reconstructing 3D Fourier Intensities from Randomly Oriented Single-Shot Diffraction Patterns"

Answer 7

I think this procedure is generally called tomography in computer graphics, the most famous (one-dimensional) example being the medical CT scan. It involves the Radon transform, and there should be a ton of literature in that direction, such as The mathematics of computed tomography.