Consider two opaque equally-sized axis-aligned disjoint cubes somewhere in three dimensional Euclidean space. Additionally there is a point in that space outside of the cubes that represents a camera that renders this scene to a two dimensional screen using ray casting. (The exact geometry, location and orientation of the screen in space isn't really relevant here. We just assume that the camera is a point where rays start to or end from all directions.) Let's call one of these cubes the red cube and the other one the blue cube. The goal is to find out whether or not the red cube occludes (fully or partially) the blue cube on the rendered image. Here is a screenshot taken in Minecraft to illustrate such a scene.
In this scene the red cube partially occludes the blue cube. I claim that the following method to determine whether or not the red cube occludes (fully or partially) the blue cube works in general: If any ray, starting from the blue cube's vertices (corners) and ending at the camera, hits the red cube, then the red cube occludes (fully or partially) the blue cube, otherwise the red cube doesn't occludes the blue cube at all.
I'm looking for a mathematical proof that this method works in general. Are there any publications that prove this? If not, can someone prove this?
I have some ideas that could be useful for the proof.
- All cubes have the same size, thus cubes closer to the camera will appear larger.
- All cubes are equally oriented (are axis-aligned), which is important for the following arguments.
- The screen projections of parallel finite straight lines don't intersect at a single point only. (Parallel infinite straight lines may intersect at a single point only, e.g. railroad track at horizon.)
- The perspective forbids certain intersections in the screen projection for equally oriented cubes.
Additional context: Unfortunately it's not possible to use the method of performing eight ray casts (one for each cube vertex) as occlusion culling algorithm. The following picture shows that even if all eight ray casts hit another cube, the blue cube in question can still be partially visible.
However, the above described method could possibly be used to obtain a full set of cubes that are relevant for an exact occlusion culling algorithm applied afterwards. All other cubes in the scene that are not hit by a ray can be ignored. Thus it can be used as a premature optimization.
Suppose the the red cube occludes the blue cube. We are asked to show there must intersect the edges of the blue cube such that the line segment between the camera and the point hits the red cube.
Let $O$ be the camera, $R$ the red cube, $B$ the blue cube. $R$ occludes $B$ means there is a point $b$ on one of the faces of $B$, say $F_B$, such that the line segment $\overline{Ob}$ hits $R$. Let $P$ be the plane of $F_B$. Let $I$ be the central projection of $R$ from $O$ to $P$.
There are two cases.
$I$ intersects the edges in $F_B$.
Then any of the intersection points is what we wanted.
$I$ does not intersect the edges of $F_B$. We will show this case cannot happen.
Since $R$ and $P$ are convex, so is $I$. Since any line segment between $b\in I$ and a point on $P$ outside $F_B$ must intersect the edges of $F_B$, $I$ cannot contain any point on $P$ outside $F_B$. So $I$ is strictly inside $F_B$.
$\quad$
Let $F_R$ be a face of $R$ that is parallel to $F_B$. Then the central projection of $F_R\subset R$ from $O$ to $P$ is strictly inside $F_B$, too. That is not possible, since $F_R$ and $F_B$ are equally-sized but any central projection of a $2$D shape to a parallel plane that is further away from the center of projection must be bigger than itself.
More generally, the same algorithm is correct still for two polyhedrons in $3$D Euclidean spaces that differ only by a translation. The polyhedrons can be concave and self-intersecting. The same proof applies, except that we will replace arguments about the convexity of $I$ with similar argument about the connectedness of $I$.