Occlusions of Objects

In a three-dimensional image it often happens that one object is in front of another. LiveGraphics3D handles these occlusions by sorting graphics primitives according to their distance from the viewer (i.e. you). Objects which are furthest away are drawn first, and the nearest objects are drawn last; we say they "occlude" the objects behind them. In computer graphics this process is often referred to as the "painter's algorithm." It is simple to implement and works well in most cases, but it can have unintended consequences.

To demonstrate how things can go awry, we'll construct a sphere surrounded by a ring. There is a right way and a wrong way to implement this in LiveGraphics3D.

(* A function to convert from spherical to rectangular coordinates *)
f[r_, t_, p_] = {r*Sin[p]Cos[t], r*Sin[p]Sin[t], r*Cos[p]};

(* Define dt and dp for use below *)
n = 20;
tmin = 0; tmax = 2Pi; dt = (tmax - tmin)/(2n);
pmin = 0; pmax = Pi;   dp = (pmax - pmin)/n;

(* Create a light gray sphere of radius 1 *)
sphere = {
  RGBColor[0.8, 0.8, 0.8],
    Table[
        Polygon[{f[1, i, j],
             f[1, i + dt, j],
             f[1, i + dt, j + dp],
             f[1, i, j + dp]}],
    {i, tmin, tmax - dt/2, dt}, {j, pmin, pmax - dp/2, dp}]};

(* Create a ring of radius 1.1 around the sphere *)
badRing = {Thickness[0.01], RGBColor[0, 0, 1],
        Line[
            Table[f[1.1, i, Pi/2], {i, tmin, tmax, dt}]
            ]};

(* Another way to create the ring of radius 1.1 *)
goodRing = {Thickness[0.01], RGBColor[0, 0, 1],
        Table[
            Line[{f[1.1, i, Pi/2], f[1.1, i + dt, Pi/2]}],
        {i, tmin, tmax, dt}]};

Before continuing, make sure you understand the difference between the two rings defined above. badRing consists of a single Line primitive with a list of points:

Line[{{1.1, 0, 0}, {1.08646, 0.172078, 0}, ..., {1.1,, 0, 0}}]


By contrast, goodRing uses a separate Line primitive for each of the line segments:

{Line[{{1.1, 0, 0}, {1.08646, 0.172078, 0}}], Line[{{1.08646, 0.172078, 0},
..., Line[{{1.08646, -0.172078, 0}, {1.1, 0, 0}}]}}


Within Mathematica, we could use either badRing or goodRing and not see a difference in the final picture. If anything, the approach in badRing is better because it only uses one primitive; in terms of bytes of computer memory, badRing is less than half the size of goodRing.

In LiveGraphics3D the two versions are definitely not equivalent, as demonstrated by following applets.

Graphics3D[{sphere, badRing}]	Graphics3D[{sphere, goodRing}]

The painter's algorithm in LiveGraphics3D is applied primitive-by-primitive. The applet computes a single distance for each primitive, and the depth-sorting is based on these distances. However, most primitives are extended in space and, therefore, are not sufficiently characterized by a single distance. This causes the problem with our ring.

badRing is just a single primitive characterized by one distance, but the actual ring extends over a large interval of distances. The polygons which make up the sphere should be occluded by one half of the ring, but at the same time they should occlude the other half. Obviously, sorting just two distances (one for the ring and one for a polygon) cannot result in the correct depth ordering.

On the other hand, goodRing is actually a list of primitives -- more specifically, a list of quite small line segments. Since these line segments are much smaller, the approximation of using only one distance per primitive works considerably better. The polygons of the sphere can now occlude the line segments in the back, but the polygons can in turn be occluded by the segments in front.

This example demonstrates an important rule of thumb: to avoid occlusion errors, it is almost always beneficial to break up large primitives into a collection of smaller objects. In particular, you should always replace Line primitives that contain a list of points by multiple Line primitives containing pairs of points. Large polygons should also be split up into a list of smaller ones.

You might ask whether one could solve this sorting problem by taking into account the interval of distances occupied by a primitive in some clever way. Unfortunately, there are cases, so-called "cyclic occlusions," which just cannot be sorted, regardless of the sorting criterion. Here is a simple example with four straight Lineprimitives:

(* A Graphics3D object consisting of four Lines
which shows occlusions errors for certain view points *)
Graphics3D[{Thickness[0.05],
    RGBColor[1,0,0], Line[{{-2,-1,-1}, {2,-1,1}}],
    RGBColor[0,1,0], Line[{{1,-2,-1}, {1,2,1}}],
    RGBColor[0,0,1], Line[{{2,1,-1}, {-2,1,1}}],
    RGBColor[1,0,1], Line[{{-1,2,-1}, {-1,-2,1}}]},
    PlotRange -> {{-2, 2}, {-2, 2}, {-1, 1}},
    ViewPoint -> {0,0,4}, ViewVertical -> {0,1,0},
    Boxed -> False]

For the default view point, each colored line segment should occlude one other line and be occluded by another. This cyclic occlusion cannot be rendered correctly with four Line primitives, as you can see in the mathlet on the left-hand side below in comparison with the mathlet on the right-hand side.

occlusion errors with four primitives	correct occlusions after splitting

The correct rendering in the second applet was achieved by splitting each Line primitive into two; this allowed LiveGraphics3D to "break" the occlusion cycle and render a correct image:

(* A Graphics3D object consisting of eight Lines
   which shows cyclic occlusions for certain view points *)
Graphics3D[{Thickness[0.05],
    RGBColor[1,0,0], Line[{{-2,-1,-1},{0,-1,0}}],Line[{{0,-1,0},{2,-1,1}}],
    RGBColor[0,1,0], Line[{{1,-2,-1},{1,0,0}}],Line[{{1,0,0},{1,2,1}}],
    RGBColor[0,0,1], Line[{{2,1,-1},{0,1,0}}],Line[{{0,1,0},{-2,1,1}}],
    RGBColor[1,0,1], Line[{{-1,2,-1},{-1,0,0}}],Line[{{-1,0,0},{-1,-2,1}}]
    },
    PlotRange -> {{-2, 2}, {-2, 2}, {-1, 1}},
    ViewPoint -> {0,0,4}, ViewVertical -> {0,1,0},
    Boxed -> False]

A popular alternative to the "painter's algorithm" is the use of depth buffering (also called z-buffering), which avoids all of the occlusion problems discussed here. In order to support older web browsers and Java virtual machines, LiveGraphics3D is restricted to Java 1.1, which, unfortunately, does not support depth buffering. Therefore, LiveGraphics3D does not employ depth buffering and suffers from frequent occlusion errors. While these errors are inconvenient, you should remember that this approach enables many users to view mathlets based on LiveGraphics3D without downloading and installing a more recent Java virtual machine.

The decision to restrict LiveGraphics3D to Java 1.1 is based on the popularity of web browsers that are limited to Java 1.1. At the time of writing this article, there is still at least one very popular Java virtual machine that is limited to Java 1.1. However, as soon as such Java virtual machines are no longer installed on a large amount of computers, the restriction of LiveGraphics3D to Java 1.1 certainly has to be reconsidered.

For a further discussion of sorting 3D objects, see "Writing Mathlets III" (Leathrum, 2002).