Improved Alpha Testing Using Hashed Sampling

We further describe and analyze the idea of hashed alpha testing from Wyman and McGuire [1], which builds on stochastic alpha testing and simplifies stochastic transparency. Typically, alpha testing provides a simple mechanism to mask out complex silhouettes using simple proxy geometry with applied alpha textures. While widely used, alpha testing has a long-standing problem: geometry can disappear entirely as alpha mapped polygons recede with distance. As foveated rendering for virtual reality spreads, this problem worsens as peripheral minification and prefiltering introduce this problem on nearby objects.

We first introduce the notion of stochastic alpha testing, which replaces a fixed alpha threshold of $\backslash alpha\_\backslash tau\; =\; 0.5$ with a randomly chosen $\backslash alpha\_\backslash tau\; \backslash in\; [0..1)$. This entirely avoids the problem of disappearing alpha-tested geometry, but introduces temporal noise.

Hashed alpha testing uses a hash function to choose $\backslash alpha\_\backslash tau$ procedurally. With a good hash function and inputs, hashed alpha testing maintains distant geometry without introducing more temporal flicker than traditional alpha testing. We also describe how hashed alpha interacts with temporal antialiasing and applies to alpha-to-coverage and screen-door transparency. Because hashed alpha testing addresses alpha test aliasing by introducing stable sampling, it has implications in other domains where increased sample stability is desirable. We show how our hashed sampling might apply to other stochastic effects.

Index Terms—anisotropy, alpha map, alpha test, hash, hashed alpha test, stable shading, stochastic sampling.

FOR decades interactive renderers have used alpha testing, discarding fragments whose alpha falls below a specified threshold $\backslash alpha\_\backslash tau$. While not suitable for transparent surfaces, which require alpha compositing [2] and order-independent transparency [3], alpha testing provides a cheap way to render binary visibility stored in an alpha map. Alpha testing is particularly common in engines using deferred rendering [4] or complex post-processing, as it provides a correct and consistent depth buffer for subsequent passes. Today, games widely alpha test for foliage, fences, decals, and other small-scale details.

But alpha testing introduces artifacts. Its binary queries alias on alpha boundaries, where $\backslash alpha\; \backslash approx\; \backslash alpha\_\backslash tau$. Because this occurs in texture space, geometric antialiasing is ineffective and only postprocess antialiasing addresses these artifacts (e.g., Karis [5], Lottes [6], and Yang et al. [7]). Texture prefiltering fails since a post-filter alpha test still gives binary results.

Less well-known, alpha mapped geometry can disappear in the distance, as shown in Figure 1. Largely ignored in academic contexts, game developers frequently encounter this problem (e.g., Castano [8]). Some scene-specific tuning and restrictions on content creation reduce the problem, but none completely solve it.

To solve both problems, we propose replacing the fixed alpha threshold, $\backslash alpha\_\backslash tau$, with a stochastic threshold chosen uniformly in $[0..1)$, i.e., we replace:

if ( color.a < $\backslash alpha\_\backslash tau$ ) discard;

with a stochastic test:

Manuscript received ???; revised ???.

if ( color.a < drand48() ) discard;

This adds high-frequency spatial and temporal noise, so we propose a hashed alpha test with similar properties but stable behavior, i.e., using:

if ( color.a < hash( ... ) ) discard;

Hashing techniques have many graphics applications, ranging from packing sparse data [9] to visualizing big data [10]. However, we present the first application of hash functions that enables controllable stability of stochastic samples. In particular, this paper makes the following contributions:

We also provide insight into how our new stable, hash-based sampling scheme might apply in other stochastic sampling contexts where stable sampling may be desirable.

Disappearing alpha-tested geometry is poorly covered in academic literature. However, game developers repeatedly encounter this issue. Castano [8] investigates the causes and describes prior ad hoc solutions. Three issues contribute to loss of coverage in alpha-tested geometry:

Reduced alpha variance. Mipmap construction iteratively box filters the alpha channel, reducing alpha variance in coarser mipmap levels. At the coarsest level of detail (lod), a single texel averages alpha, $\backslash alpha\_\{avg\}$, over the base texture. Many textures contain $\backslash alpha\_\{avg\}\; \backslash ll\; \backslash alpha\_r$, causing more failed alpha tests in coarser lods, especially if the texture contains padding (see Figure 2). Essentially, a decreasing percentage of texels pass the alpha test in coarser mips.

Discrete visibility test. Unlike alpha blending, alpha testing gives binary visibility. Geometry is either visible or not in each pixel. As geometry approaches or recedes from the viewer, pixels suddenly transition between covered and not covered. This discretely erodes geometry with increasing distance (see Figure 3). At some point, 1-pixel wide geometry erodes to 0-pixel wide geometry and disappears.

Coarse raster grid. With enough distance, even proxy billboard geometry becomes sub-pixel. In this case, a relatively coarse rasterization grid (i.e., sampling at pixel centers) poorly captures the geometry. Some billboards may not appear, causing an apparent loss of coverage (see Figure 4). Our work does not address this issue, though conservative rasterization and multisampling reduce the problem.

Game developers have dealt with disappearing alpha-mapped geometry for years, as games often display foliage, fences, and hair from afar. Various techniques can help manage the problem.

Adjusting $\backslash alpha\_r$ per texture mipmap level. Since mipmap filters alpha, adjusting $\backslash alpha\_r$ per mip-level can correct for reduced variance. Consider a screen-aligned, alpha-tested billboard covering $A\_0$ pixels where $a\_0$ pixels pass the alpha test at mip level 0. Seen at a distance, this screen-aligned billboard might use mip level $i$. We expect a consistent percentage of pixels passing the alpha test, i.e.:

One can precompute test thresholds $\backslash alpha\_\backslash tau(i)$ that maintain this ratio for each mipmap. But content affects this threshold, so it differs between textures and even within a mip level (i.e., we want $\backslash alpha\_\backslash tau(i,\; u,\; v)$). Even perfect per-level thresholds do not prevent geometry disappearing with distance; the fence in Figure 3 has nearly constant $\backslash alpha\_\backslash tau(i)$ but still quickly disappears with distance.

Adjust stored $\backslash alpha$ values per mipmap level. Castano [8] proposes a similar, mathematically equivalent, approach. Rather than requiring variable $\backslash alpha\_\backslash tau(i)$ that complicates shader code, the alpha values in each mipmap level are premultiplied by $0.5^i\; \backslash alpha\_\backslash tau(i)$ at asset creation time. The allows use of a fixed $\backslash alpha\_\backslash tau\; =\; 0.5$ at run time. Otherwise, this has identical properties to defining variable $\backslash alpha\_\backslash tau(i)$.

Adjust stored $\backslash alpha$ values per texel. Castano [8] adjusts alpha for each mipmap level. Separate per-texel adjustments (e.g., by $0.5^i\; \backslash alpha\_\backslash tau(i,\; u,\; v)$) are possible, but it is unclear how to compute $\backslash alpha\_\backslash tau(i,\; u,\; v)$ or if independent texels adjustments still just dilate alpha boundaries (e.g., see Figure 11).

Always sampling $\backslash alpha$ from finest mip lod. As filtering reduces alpha variance and changes threshold $\backslash alpha\_\backslash tau(i)$, always sampling $\backslash alpha$ from mip level 0 trivially avoids the problem. But this either requires two texel fetches per pixel (one for RGB, one for $\backslash alpha$) or eliminates color prefiltering (using both RGB and $\backslash alpha$ from mip 0). An alternative limits the maximum mipmap lod to a user-specified $i\_\{\backslash max\}$, using level $i\_\{\backslash max\}$ when $i\; >\; i\_\{\backslash max\}$. But both approaches can thrash the texture cache and reduce the temporal stability of fine texture details.

Rendering first with $\backslash alpha$-test, and then with $\backslash alpha$-blend. Alpha testing’s popularity stems from the difficulty of efficient order-independent blending. Naive alpha blending causes halos where the z-buffer gets polluted by transparent fragments. By first rendering with alpha testing and then rerendering with alpha blending, z-buffer pollution is reduced [12]. This guarantees transparent fragments never occlude opaque ones, but requires rendering alpha-mapped geometry twice and does not work with deferred shading.

Supersampling. When storing binary visibility, a base texture’s alpha channel contains only 0s or 1s. With sufficiently dense supersampling, one can always access the full resolution texture, providing accurate visibility. But the required density can be arbitrarily high, due to geometric transformations and parameterizations.

Alpha-to-coverage. With $n$-sample multisampling, alpha is discretized and outputs $\backslash lceil\; na\; \backslash rceil$ dithered binary coverage samples [13]. Usually these dither patterns are fixed, causing correlations between layers and preventing correct multi-layer compositing. Enderton et al. [11] propose selecting random pattern permutations to address this problem.

Screen-door transparency. While fairly uncommon today, screen-door transparency behaves similar to alpha-to-coverage except that dithering occurs over multiple pixels. Various mask selection techniques exist for screen-door transparency [14], but even random mask patterns lead to

correlation between composited layers and repeated dither patterns visible over the screen.

To provide a mental framework to help understand hashed alpha testing, we first introduce the idea of stochastic alpha testing. Essentially, stochastic alpha testing replaces traditional alpha testing’s fixed threshold ($\backslash alpha\_\backslash tau\; =\; 0.5$) with a stochastic threshold ($\backslash alpha\_\backslash tau\; =\; \backslash text\{drand48\}()$). This replaces one sample on a regular grid (i.e., sampling $[0..1]$ at 0.5) with one uniform random sample.

A stochastic alpha test is a simplified form of stochastic transparency [11] with only one sample per pixel. While this seems trivial, we observe that replacing a fixed alpha threshold with a random one solves our disappearing coverage problem: alpha mapped surfaces no longer disappear with distance (see Figure 5). Unlike with a fixed alpha threshold, with stochastic sampling the visibility, , has the correct expected value $E[V]$ of $\backslash alpha$.

But a single random sample is insufficient. It introduces significant noise, causing continuous twinkle (see video). Reusing random seeds between frames and using stratification helps stabilize noise for static geometry (see Laine and Karras [15] and Wyman [16]). But whenever motion occurs the high-frequency noise reappears. Supersampling helps, but using just one sample per pixel is a major appeal of alpha testing, given it works in forward and deferred shading, without MSAA, and even on low-end hardware.

In hashed alpha testing we target visual quality equivalent to stochastic alpha testing with temporal stability equivalent to traditional alpha testing.

Instead of stochastic sampling, we propose using a hash function to generate alpha thresholds. This is not particularly surprising, as hash functions have often formed the basis for common pseudo-random number generators [17]. Our contribution is recognizing that by careful manipulation of hash function inputs, rather than hiding them inside a pseudorandom number generator, we can better control the stability of our random sample.

Appropriate hash functions include those that generate outputs uniformly distributed in $[0..1]$, allowing direct substitution for uniform random number generators. To obtain well distributed noise with spatial and temporal stability, we sought to control our hash function inputs to achieve the following properties:

Listing 1 provides stable hashing, but using the length of object-space derivatives provides a uniform noise scale irrespective of surface orientation. Unfortunately, this creates anisotropy if viewing surfaces obliquely, as projected noise scales differ along screen-space $x$- and $y$-axes (see Figure 6).

When adding a simple modification like hashed alpha testing into an existing renderer, a developer's goal is improving quality without changing the rendering workflow.

// Find the discretized derivatives of our coordinates
vec3 anisoDeriv = max( abs(dFdx(objCoord.xyz)),
                      abs(dFdy(objCoord.xyz)) );
vec3 anisoScales = vec3(
    0.707/(g_HashScale*anisoDeriv.x),
    0.707/(g_HashScale*anisoDeriv.y),
    0.707/(g_HashScale*anisoDeriv.z) );

// Find log-discretized noise scales
vec3 scaleFlr = vec3( exp2(floor(log2(anisoScales.x))),
                    exp2(floor(log2(anisoScales.y))),
                    exp2(floor(log2(anisoScales.z))) );
vec3 scaleCeil = vec3( exp2(ceil(log2(anisoScales.x))),
                    exp2(ceil(log2(anisoScales.y))),
                    exp2(ceil(log2(anisoScales.z))) );

// Compute alpha thresholds at our two noise scales
vec2 alpha = vec2(hash3D(floor(scaleFlr*objCoord.xyz)),
                  hash3D(floor(scaleCeil*objCoord.xyz)));

// Factor to linearly interpolate with
vec3 fractLoc = vec3( fract(log2( anisoScale.x )),
                    fract(log2( anisoScale.y )),
                    fract(log2( anisoScale.z )) );
vec2 toCorners = vec2( length(fractLoc),
                      length(vec3(1.0f)-fractLoc) );
float lerpFactor = toCorners.x / (toCorners.x+toCorners.y);

// Interpolate alpha threshold from noise at two scales
float x = (1-lerpFactor)*alpha.x + lerpFactor*alpha.y;

// Pass into CDF to compute uniformly distrib threshold
float a = min( lerpFactor, 1-lerpFactor );
vec3 cases = vec3( x*x/(2*a*(1-a)),
                  (x-0.5*a)/(1-a),
                  1.0-(1-x)*(1-x)/(2*a*(1-a)) );

// Find our final, uniformly distributed alpha threshold
float alpha = (x < (1-a)) ?
    ((x < a) ? cases.x : cases.y) :
    cases.z;

// Avoids alpha == 0. Could also do alpha=1-alpha
alpha = clamp( alpha, 1.0e-6, 1.0 );

This requires working nicely with other common algorithms without introducing new artifacts. This section looks at some implementation considerations for using hashed alpha tests in existing engines.

As noted in Section 3, alpha-to-coverage discretizes fragment alpha and outputs $\backslash lceil\; na\; \backslash rceil$ coverage bits dithered over an $n$-sample buffer. Generating $\backslash lceil\; na\; \backslash rceil$ coverage bits is equivalent to supersampling the alpha threshold, i.e., performing $n$ alpha tests with thresholds:

This observation reveals that traditional alpha testing is a special case, where $n\; =\; 1$.

Applying hashed or stochastic alpha testing to alpha-to-coverage is equivalent to jittered sampling of the thresholds:

for hashed samples $\backslash chi\_i\; \backslash in\; [0..1]$. $\backslash chi\_i$ can be chosen independently per sample or once per fragment (i.e., $\backslash chi\_i\; =\; \backslash chi\_j$).

Traditional alpha-to-coverage uses fixed dither patterns for all fragments with the same alpha. This introduces correlations between overlapping transparent fragments, causing aggregate geometry to lose opacity (see Figure 1).

To avoid this, we compute a per-fragment offset $\backslash alpha\_o$, increment $\backslash alpha\_+$, and apply per-sample alpha thresholds:

Given hashed $\backslash xi\_1,\; \backslash xi\_2\; \backslash in\; [0..1]$ and limiting $n$ to powers of two, $\backslash alpha\_o\; =\; \backslash lfloor\; n\backslash xi\_1\; \backslash rfloor$ is an integer between 0 and $n-1$ and $\backslash alpha\_+\; =\; 2\backslash lfloor\; 0.5n\backslash xi\_2\; \backslash rfloor\; +\; 1$ is an odd integer between 1 and $n-1$. This decorrelates the jittered thresholds if $\backslash xi\_1$ or $\backslash xi\_2$ varies with distance to the camera.

Until this point, we focused our description on how stable hashed samples apply to disappearing alpha-tested geometry. However, interactive applications strive for temporal stability in various domains, and stable hashing may prove useful either for directly generating samples or improving the quality of reprojection caching [20].

For example, light transport algorithms often use Monte Carlo sampling to approximate the rendering equation [21].

Real-time constraints can prevent the increased ray counts needed to avoid temporal noise.

A common approach defines per-pixel, fixed pseudorandom seeds, but this induces a screen-door effect visible as geometry moves relative to the screen. We instead generate samples with our stable, pixel-sized grid. This produces largely stable noise that stays fixed to the geometry, even under motion. We demonstrate this for single ray per pixel ambient occlusion (see Figure 8). This is simple enough to visually understand the hash samples, yet remains representative of more complex light transport.

For our simple test, rather than computing $\backslash alpha\_r$ via Listing 2, we generate two hash samples $\backslash chi\_1,\; \backslash chi\_2\; \backslash in\; [0..1]$ with the same code, but using two different hash3D() functions for $\backslash chi\_1$ and $\backslash chi\_2$:

float hash3D_χ1(vec3 in)
{ return hash( vec2( hash( in.xy ), in.z ) ); }
float hash3D_χ2(vec3 in)
{ return hash( vec2( in.x, hash( in.yz ) ) ); }

As described in Section 7.2.2, independent samples can also be generated using different offsets, e.g.:

float hash3D_χ1(vec3 in) { return hash3D( in+offset[0] ); }
float hash3D_χ2(vec3 in) { return hash3D( in+offset[1] ); }

We convert these hashed values into a cosine-sampled hemisphere in the standard way:

vec3 direction = vec3( sqrt( χ1 ) * cos( 2πχ2 ),
                      sqrt( χ1 ) * sin( 2πχ2 ),
                      sqrt( max( 0.0, 1.0 - χ1 ) ) );

Extending to more general light transport algorithms, which require many stable samples each frame, simply requires using additional offset[i] values. Alternatively, a hash returning an integer could seed a more traditional pseudorandom number generator.

Stochastic alpha testing essentially simplifies stochastic transparency to one sample per pixel. Hence, when using

more tests per pixel stochastic alpha testing converges to ground truth, just as stochastic transparency does.

In this light, based on the thresholds in Equation 7, alpha-to-coverage is stochastic transparency with regular instead of random samples. Using randomized thresholds, as in Equation 8, corresponds to stratified stochastic transparency.

But a key difference is that alpha testing is designed and frequently expected to work with a single sample per pixel. Avoiding temporal and spatial noise is key for adoption, hence our stable hashed alpha testing, which we believe provides an appealing alternative to traditional alpha testing.

We prototyped our hashed and stochastic alpha test in an OpenGL-based renderer using the Falcor prototyping library [22]. We did not optimize performance, particularly for stochastic alpha testing, as we sought stable noise rather than optimal performance. Timings include logic to explore variations to hashes, fade-in functions, and other normalization factors.

Table 1 shows performance relative to traditional alpha testing, rendered at $1920\; \backslash times\; 1080$ and using one shader for all surfaces, transparent and opaque. Our added overhead for hashed alpha testing is all computation, without additional texture or global memory accesses. Anisotropic hashed alpha testing increases costs, perhaps 10–20% over the isotropic variant, but with our limited timing precision and our test’s small overhead the timing runs were identical for both variants. Our stochastic alpha test prototype uses a random seed texture, requiring synchronization to avoid correlations from seed reuse. This causes a significant slowdown.

Cost varies with number, depth complexity, and screen coverage of alpha-mapped surfaces. At $1920\; \backslash times\; 1080$ with one test per fragment, our hashed alpha test costs an additional 0.1 to 0.3 ms per frame for scenes with typical numbers of alpha-mapped fragments. For stochastic alpha testing, synchronization costs increase greatly in high depth complexity scenes.

Figure 1 shows a game-quality head model with alpha-mapped hair billboards. With distance the hair disappears. This is most visible in his beard, as the underlying diffuse

texture has no hair painted on his chin. See the supplemental video for dynamic comparisons with this model.

Figure 9 shows similar comparisons on a number of artist-created tree models provided as samples by XFrog. These trees’ alpha maps contain 50–75% transparent pixels, causing foliage to disappear quickly when rendered in the distance or at low resolution. Hardware accelerated alpha-to-coverage has high layer-to-layer correlation that causes leaves to appear as a single layer and overly transparent. Hashed alpha testing and hashed alpha-to-coverage fix these problems and appear much closer to the ground truth, despite rendering at lower resolution.

In Figures 10 and 11, we compare hashed alpha against the widely used approach of Castano [8], which computes a per-mipmap alpha threshold and bakes this into the texture as a preprocess. This approach dilates distant geometry to keep it visible, giving an overly dense appearance on the thin leaves in Figure 10.

Figure 11 compares hashed alpha testing, $8\; \backslash times$ MSAA using hashed alpha-to-coverage, and both hashed techniques with temporal antialiasing. Interestingly using hashed alpha testing with TAA gives results largely similar to alpha-to-coverage, and temporally antialiased alpha-to-coverage is nearly indistinguishable from the ground truth.

Figure 12 shows a more complex example where hashed noise may be undesirable nearby and the fade-in from Section 7.1 maintains crisp edges near the viewer.

Figure 13 compares the temporal stability of traditional, hashed, and stochastic alpha testing under slight, sub-pixel motion. Note that under the same sub-pixel motion hashed alpha testing exhibits temporal stability roughly equivalent to traditional alpha testing. Stochastic alpha testing and methods that do not anchor noise or discretize it to pixel scale exhibit significantly more instability.

Figure 14 shows a synthetic example of a planar checkerboard texture containing half opaque and half transparent texels. In this case, alpha testing does not disappear with distance but aliases. Hashed alpha testing replaces this aliasing with noise, and using MSAA-based alpha-to-coverage

converges to a desired uniform gray in the distance.

Beyond use for distant or low-resolution alpha-mapped geometry, other applications exist for hashed alpha testing. In head-mounted displays for virtual reality, rendering at full resolution in the user’s periphery is wasteful, especially as display resolutions increase. Instead, foveated rendering [24] uses at lower resolution away from a user’s gaze. Patney et al. [23] suggest prefiltering all rendering terms, but they were unable to support alpha testing due to an inability to prefilter the results. Naive alpha testing in foveated rendering causes even nearby foliage to disappear in the periphery (see Figure 15). With temporal antialiasing, hashed alpha testing enables use of alpha mapped geometry in foveated renderers.

Figure 16 shows hashed alpha testing in a more complex environment. Results are more subtle as scene scale is small enough to minimize the pixels accessing coarse mipmaps.

We introduced the idea of stochastic or hashed alpha testing to address the problem of alpha-mapped geometry disappearing with distance. Stochastic alpha testing uses a random $\backslash alpha\_r$ rather than a fixed threshold of 0.5. To address the temporal noise stochastic introduces, we proposed a procedural hash to provide a stable noise threshold.

We obtained stable, pixel scale noise by hashing on discretized object-space coordinates at two scales. We showed how to ensure the interpolated hash value maintains a uniform distribution, how to maintain sample quality in the presence of anisotropy, and how hashed alpha testing works with temporal antialiasing. We demonstrate temporal stability both in Figure 13 and the accompanying video. And we suggested how this stable sampling scheme could extend to other stochastic light transport effects. We provided inline code to replicate our hashed test.

Thinking about alpha-to-coverage and screen door transparency in the context of varying $\backslash alpha\_r$ provides insights, showing them all to be different discrete sampling strategies for transparency: alpha test and alpha-to-coverage perform regular sampling, screen-door transparency interleaves samples, stochastic alpha testing randomly samples, and hashed alpha testing uses quasi-random sampling via a uniform hash function.

While our hashed test provides spatially and temporally stable noise without scene-dependent parameters, we did not explore the space of 2D and 3D hash functions to see which minimizes flicker between frames. Additionally, using more sophisticated hash inputs than object-space coordinates may generalize over a larger variety of highly instanced scenes. Both areas seem fruitful for future work.

Our work evolved from a larger research project, so many researchers contributed directly and indirectly. Thanks to Pete Shirley for keeping our hash uniform by deriving the cdf in Equation 2, Cyril Crassin for suggesting alpha maps as a simplified domain worth studying, Anton Kaplanyan for discussing stable noise, Anjul Patney for trying hashed alpha in foveated VR, and Dave Luebke, Aaron Lefohn, and Marco Salvi for additional discussions. Also, thanks to the insightful 13D and TVCG reviewers and numerous helpful comments from the game developer community on Twitter.

Chris Wyman is a Principal Research Scientist in NVIDIA’s real-time rendering research group located in Redmond, WA. Before moving to Redmond, he was a Visiting Professor at NVIDIA and an Associate Professor of Computer Science at the University of Iowa. He earned a PhD in computer science from the University of Utah and a BS in math and computer science from the University of Minnesota. Recent research interests include efficient shadows, antialiasing, and participating media, but his interests span the

range of real-time rendering problems from lighting to global illumination, materials to color spaces, and optimization to hardware improvements.

Morgan McGuire is a professor of Computer Science at Williams College and a researcher at NVIDIA. He is the author or coauthor of The Graphics Codex, Computer Graphics: Principles and Practice, 3rd Edition, and Creating Games. He received his degrees at Brown University and M.I.T.