Sort-Last Compositing and the Depth Order Across Ranks

A parallel renderer splits the data across ranks. Each rank renders its own portion and produces a partial image, and the partial images must be combined into the final picture. The combination is not a sum: it is an ordered blend, and the order is determined by the depth of each fragment along the view ray. A rank that owns the far half of the domain must contribute before a rank that owns the near half, or the near contribution is occluded by a surface that is physically behind it.

Sort-last compositing is the family of methods that solves this by sorting after rendering, by depth, during the merge. The name distinguishes it from sort-first, which partitions screen space and sorts geometry before rasterization, and sort-middle, which sorts between the geometry and raster stages. Sort-last is the natural fit for large scientific data because it lets each rank keep its spatial partition of the simulation, which is the partition the solver already uses, and it is the only family that does not require redistributing geometry to match the screen.

Why the merge is not a reduction

For opaque geometry, the merge is a per-pixel minimum of depth: the surviving fragment is the one closest to the eye. That is an associative and commutative operation, and a tree reduction over the ranks computes it in $O(\log p)$ rounds with no ordering constraint. The amount of data per round is the image, not the geometry, which is the property that makes sort-last scale.

For translucent geometry or volume rendering, the operation is alpha compositing, and it is associative but not commutative. Each fragment contributes color $C_i$ and opacity $\alpha_i$, and the composite of two partial images in order is

$$(C, \alpha) = (C_1, \alpha_1) \mathbin{\text{over}} (C_2, \alpha_2) = \big(C_1 + (1 - \alpha_1) C_2,; \alpha_1 + (1 - \alpha_1)\alpha_2\big),$$

where “over” means image 1 is in front. The operation is associative, so a tree of merges gives the same result as a sequential fold, provided the order at each merge is the physical order. It is not commutative, so the tree must be constructed to preserve order, and a rank cannot merge with an arbitrary peer without knowing which is nearer.

That single asymmetry is the source of every difficulty in the method. It means the merge has a dependency structure that follows depth, and the dependency structure changes with the camera, so it cannot be fixed once at setup.

Direct send and the cost of all-to-all

The simplest correct scheme has every rank send its partial image to a single compositing rank, which sorts the fragments per pixel and blends them. The image is $W \times H \times 4$ bytes, so a $2048 \times 2048$ RGBA8 image is 16 MiB, and with $p$ ranks the compositor receives $16p$ MiB. On 4096 ranks that is 64 GiB arriving at one process, and the receiving process’s memory and network port become the bottleneck. The scheme is correct and does not scale, and its cost grows linearly with $p$ in the worst place, the single node that everything must pass through.

A refinement distributes the compositing by image region: each rank sends only the tiles it owns to the rank responsible for those tiles, so the fan-in per compositor is reduced and the work is spread. The total bytes over the network are unchanged, so this fixes the single-node bottleneck but not the $O(p)$ traffic. When the image is large and the rank count moderate, that is often enough.

The tree schemes address the traffic itself. In binary tree compositing, ranks are paired, one pair member sends its image to the other, which composites and passes the result upward. After $\log_2 p$ rounds the root holds the complete image. Each round has $p/2^k$ active senders at level $k$, each sending a full image, so the traffic totals $p-1$ images across all rounds, and a rank on the deepest branch sends one image per round. The traffic is spread over the rounds and the links, and no single process ever receives more than one image at a time.

Binary swap does better on traffic by dividing the image among the pair at each round. Each rank starts with a full image and, at each level, splits the pixels with its partner: each keeps half, sends the other half, composites what it received with its own half, and continues with a half-size image. After $\log_2 p$ rounds each rank holds $1/p$ of the final image, and the total bytes sent is $W H \times 4 \times (p-1)/p$ per rank, which is about one image per rank in total rather than $\log p$ images. The final image must then be gathered or displayed from the pieces, which is a smaller transfer.

The ordering constraint is what binary swap’s split must respect. Each rank knows the depth range of its own data, so it can determine, for any pixel, whether its fragment is in front of or behind its partner’s. The split is by pixel ownership, and the compositing at each round must place the fragments in the right order; since the two ranks’ data may interleave in depth across the image, each rank needs the partner’s depth for the pixels it keeps. The standard implementation sends depth along with color, or relies on the data partition being spatially disjoint in depth, which is true for a block decomposition and a view direction not aligned with the block boundaries but not true in general. A block decomposition viewed along an axis has ranks whose depth ranges are strictly ordered; the same decomposition viewed obliquely has ranks whose ranges overlap for most pixels, and the merge must handle interleaving per pixel.

/* One round of pairwise compositing: the partner's image arrives, and each pixel
   is blended in depth order. Depths are in the same units on both ranks. */
static void merge_pair(float *local, const float *remote, const float *depth_local,
                       const float *depth_remote, size_t npix)
{
    for (size_t i = 0; i < npix; i++) {
        float *a = local + 4 * i;
        const float *b = remote + 4 * i;
        int local_is_front = depth_local[i] <= depth_remote[i];
        const float *front = local_is_front ? a : b;
        const float *back  = local_is_front ? b : a;
        float af = front[3], ab = back[3];
        float rgb[3];
        for (int c = 0; c < 3; c++)
            rgb[c] = front[c] + (1.0f - af) * back[c];
        a[0] = rgb[0]; a[1] = rgb[1]; a[2] = rgb[2];
        a[3] = af + (1.0f - af) * ab;
    }
}

The staging array keeps reads and writes apart. When the partner’s fragment is in front, front points into remote while back aliases local, so the destination of the blend is also one of its sources; writing the result into a separate array makes the loop independent of the order in which the components are updated.

Reading depth_remote alongside the color is what makes the per-pixel decision possible. An implementation that assumes a global front/back relation between the two ranks avoids that transfer and is correct only when the depth ranges do not interleave.

Depth precision and the ordering error

The compositing decision uses a depth value per pixel, and that value has finite precision. With a 24-bit depth buffer, the ordering is exact only to the resolution of that representation, and where two fragments’ depths differ by less than one unit in the last place, the comparison is arbitrary. In a volume rendering, adjacent samples along a ray are often much closer than the depth buffer’s resolution at that range, so the merge of two ranks whose contributions alternate in depth produces an order that is locally wrong.

The visible result is not a gross error but a subtle one: a region where two semi-transparent structures cross shows the wrong one in front, and the error moves as the camera moves, producing a shimmer that is easy to attribute to the renderer and hard to diagnose. Compositing in floating-point depth rather than a normalized fixed-point buffer removes most of it, at the cost of doubling the depth payload per pixel.

A separate precision issue is the alpha accumulation itself. Compositing many nearly opaque fragments in sequence drives $(1-\alpha)$ toward zero, and in an 8-bit channel the accumulated color saturates before the true value is reached. Compositing in 16-bit or 32-bit float per channel is standard for volume rendering for this reason; the images transferred between ranks are then four times or sixteen times larger, which directly multiplies the network cost that the tree schemes were designed to reduce.

An important asymmetry: for opaque geometry the merge can be done on depth alone, since the color of the nearest fragment wins outright, and no blending precision is involved. Many parallel renderers use this fact and composite opaque geometry with a depth-only reduction, falling back to full color transfer only when translucency is present. The choice is per pass, not per frame, which means a scene with one translucent object pays the full cost for the whole image.

Load imbalance and the tail of the merge

Rendering work is distributed by data, and data is rarely uniform. A rank whose block contains the visible surface of a dense object renders far more fragments than a rank whose block is empty space. In a lockstep merge, every rank waits for the slowest, so the frame time is set by the worst rank rather than by the average, and adding ranks to a fixed-size problem makes the imbalance worse because each block’s content varies more from the mean.

The standard mitigations are dynamic: assign blocks to ranks in an order that balances expected cost, split large blocks along the view direction so that depth ranges are finer, or render with an empty-space skipping structure that makes an empty block cheap. None of them removes the constraint that the merge’s last round cannot start until both children have finished, so the critical path is the sum of the slowest branch at each level.

The merge’s own cost is a function of image size and rank count, not of scene complexity, so at high rank counts and modest image sizes the compositing can dominate the frame. A $1024 \times 1024$ image with four bytes per channel is 16 MiB; a tree merge over 1024 ranks moves roughly a gigabyte through the fabric per frame, and at a sustained interconnect rate of a few GB/s per node this is a fraction of a second before any rendering happens. Reducing image size, compositing in place at lower resolution and upsampling for display, or restricting the merge to the pixels that actually received fragments are the levers, and each trades fidelity for rate.

Where the composited image stops being the answer

The output of a sort-last renderer is a projection. It has discarded depth except where the depth buffer preserves it, and the ordering it encodes is only as correct as the depth values and the blend arithmetic. For an opaque surface that is adequate; for a volume, the image is an integral along the view ray and cannot be decomposed back into the structures that produced it.

Where the analysis needs more than an image, the composite is the wrong output, and the alternatives are the reduced data products discussed in In-Situ Analysis and the Bandwidth That Is Not There: extracted geometry, downsampled fields, or a parametrized image database. Where the analysis does want an image, the per-sample accumulation that produced each rank’s partial image is governed by the transfer function and its opacity correction, in Direct Volume Rendering and the Opacity Correction Nobody Applies, and the color mapping the composited result displays follows the constraints in Perceptually Uniform Colormaps and the Failure of Rainbow Ramps. The compositing step is the last place in the pipeline where an error can be introduced, and it is the one that operates on the smallest data, which is why it is also the one that can be made exact most cheaply.