Sunday, February 1, 2026

How to tessellate

There are many different approaches for determining whether and by how much a patch needs to be tessellated. It is important that we don’t create cracks between neighboring patches or subpatches. Many Reyes implementations choose tessellation patterns which do not match and must stitch them together after they are generated. We need something that can be determined purely from the subpatch itself with no communication needed between subpatches such that they can run completely in parallel.

TessFactors

The approach Moreton and D3D’s hardware tessellation stage take is a simple solution to this problem and the one I use. So long as the only data about a patch that affects the placement of vertices on an edge is data about the edge itself, those vertices will match between different patches. Each edge computes a tessellation factor, ie the number of segments they wish to be subdivided into. I will refer to these 3 edge factors as TessFactors. D3D also has an inner tessellation factor but in practice that is derived from the edge factors and mostly is just an artifact of the tessellation pattern D3D uses.

That doesn’t explain how these TessFactors are calculated. There are various approaches to that as well. Calculating the length of the undisplaced edge in screen space doesn’t work since that might be zero but displacement causes the patch to face towards the camera. Other approaches suggest the opposite, only densely tessellate at silhouettes and reduce tessellation where the displacement direction faces the camera and displacing would only change depth. Depth matters for object intersections and shadows though.

Diagsplit samples the displacement function at a few points to estimate its screen space length. Not only is that too expensive, it requires every shader that needs to calculate TessFactors to have access to the displacement function, ie be programmable, which isn’t practical. Also ruled out are artist provided density hints expressed by the material graph for the same reason.

The approach I take is simple, common, and similar to what Nanite already uses to project object space error to screen space. TessFactor for an edge is based solely on its world space undisplaced length which is projected to pixels as if the edge was perpendicular to the view vector. This length in pixels is divided by a global DiceRate setting to convert it to TessFactor. Often DiceRate >1 pixel can save cost with little visual difference. The UE default is 2 pixels.

Uniform density dicing

We have these TessFactors for a patch we want to dice. They represent roughly the length of each edge of the patch. We want to dice that triangular patch into uniformly sized triangles. What is typically called a uniform tessellation is one where a shape is tessellated into many smaller identical shapes similar to the original. The angles are congruent. This is topologically uniform. That is not helpful. What we need is uniform density.

Uniform topology

Uniform topology snapped to edge TessFactors

Uniform density

I’ll define an optimal uniform density tessellation as one with the minimum number of triangles possible where all edges are <= to a chosen length. The length of the longest edge dictates the worst case sampling rate of the displacement function and thus the signal resolution. Achieving this target edge length with any more triangles wouldn’t be optimal. It isn’t important to achieve a perfectly optimal tessellation but it is useful to understand the target and its properties to understand how to approach it.

Remeshing

Thankfully generating meshes like these, isotropic meshes made of roughly equal length edges forming equilateral triangles with vertices close to valence 6, is a common operation called remeshing and there are many published approaches to do so. Perhaps the most popular is [Botsch and Kobbelt 2004].

The algorithm goes as follows:

For N iterations

For all edges
- If edge is too long then split it
- If edge is too short then collapse it
- If edge could be shorter if it was flipped then flip it
For all vertices
- Move position to the average of its neighbors

After many iterations the result will approach an isotropic mesh matching the desired properties. There are more considerations when this is meant to express a particular surface but we are only concerned with remeshing a flat triangular patch. For this case the only consideration needed is to constrain boundary vertices to the patch edge they started on.

Tessellation Table

This remeshing process is far too expensive to do in real-time though. Thankfully since we are working with just the patches themselves and there is a limit on the maximum TessFactor for dicing, every permutation of TessFactors can be precomputed and placed in a lookup table which I will call the Tessellation Table. The TessFactors index into the Tessellation Table. I will call an entry in this table a Tessellation Pattern.

What exactly is stored in the Tessellation Table? For each pattern there is a vertex and index buffer as if it were a little mesh. Instead of positions, the vertex buffer stores barycentric coordinates in the patch. When rendering, the patch can be replaced with this little mesh. The barycentrics are used to interpolate the patch corners. Because each pattern is of variable size there is also an offset table translating the TessFactor index into the buffer offsets for the VB and IB. The barycentrics are stored as 2 16bit coordinates with the 3rd coordinate implied. The indexes are 10bit so all 3 corners of a triangle can be packed into 1 dword.

Tessellation Table redundancy

There is a lot of redundancy in this indexing though. The Tessellation Pattern for (3,4,2), (3,2,4), (4,3,2) for example are all the same. They are just rotated or mirrored versions of the same pattern. Instead a unique index into the table is defined as an ordering of the TessFactors from largest to smallest.

This reduces the number of patterns stored from $N^3$ to $\binom{N+2}{3}$ or $\frac{N(N+1)(N+2)}{6}$, where $N$ is the max TessFactor the Tessellation Table covers. For N=16 this is the difference between 4096 and 816 or <20% the patterns needing to be stored. Size reduction also reduces cache pollution.

To correctly alias patterns the reordering must also be undone when the pattern is used. First, if the winding flips it needs to be reversed so backface culling is preserved. Second, the barycentrics stored in the table need to be unswizzled so they correctly index the corners of the patch. Alternatively, the patch corners themselves can be swizzled which is often cheaper since it happens at lower frequency.

Tessellation Pattern building

The remeshing algorithm previously explained was written for meshes with Cartesian coordinates but Tessellation Patterns only store barycentric coordinates. Another way to describe this issue is to say the original algorithm assumes extrinsic geometry but Tessellation Patterns are intrinsic geometry. An extrinsic triangle is defined by the position of its corners. It is embedded in a space. An intrinsic triangle is defined by its edge lengths. It doesn’t have any specific position or orientation. A Tessellation Pattern is intrinsic. A pattern exists for each combination of TessFactors. TessFactors are treated as patch edge lengths so the goal for a pattern is to tessellate the patch into triangles with roughly unit length edges.

Intrinsic isn’t a problem for the relaxation step. The average of Cartesian and barycentric coordinates will result in equivalent positions since the math is linear. What extrinsic appears to be needed for is the edge length calculations. Thankfully that is not the case. A good number of geometry calculations can be done with only barycentrics and edge lengths.

For a pair of barycentric points P and Q there is a vector between them $\mathbf{PQ} = Q - P$. Unlike normalized barycentric points where $u+v+w=1$, for normalized barycentric vectors $u+v+w=0$, since $1-1=0$. The squared length of a barycentric vector $\mathbf{PQ}(u,v,w)$ in a triangle with edge lengths $(a,b,c)$ is:
\begin{equation} \lVert \mathbf{PQ} \rVert^2 = -a^2 v w -b^2 w u -c^2 u v \end{equation} Thankfully this also implicitly handles a nonobvious issue. While treating TessFactors as edge lengths is sensible and expresses what we are optimizing for, they aren’t exactly lengths. There are rare cases where TessFactors interpreted as edge lengths express a non-Euclidean triangle, specifically $a>b+c$. If extrinsic geometry was required to calculate edge lengths it wouldn’t be possible for these patterns. Deriving the extrinsic coordinates would result in divide by zeros and negative sqrts. Working as intrinsic instead, using the formula above, no special handling is needed. While the distances lose geometric meaning in these cases it degrades gracefully

Barycentric quantization

The last thing to take care of is to make sure boundary vertices bitwise match along an edge with all other patterns with the same TessFactor. If they don’t there will be cracks. That can be left for when the barycentrics are quantized to 16bit. It is important though that this quantization is symmetric.

Consider 2 adjacent triangles rotated 180 degrees from one another. Their shared edge will also share the same corners except swapped. Their coordinates lerp in opposite directions. If this edge is where $w=0$, then for vertices along the edge to match their counterpart $(u,v,w)=(1-v,1-u,w)$. This implies that quantization must be symmetric about 0.5. Whatever direction x rounds needs to be the opposite of what happens to 1-x. If 0.25 rounds down, 0.75 needs to round up, or vice versa.

The most obvious way to quantize to 16b fixed point would be to represent the range [0.0, 1.0] as [0, 65535]. With that all float values can be made to match a reversed counterpart at the boundaries except one: 0.5, the midpoint. This is a point that will be used by any pattern that has an even TessFactor. 0.5 can’t round in the opposite direction as 0.5. It needs to be stored exactly. The easiest fix is to use an even max value, so map 1.0 to 65534.

If each coordinate is quantized separately they might not still sum to 1. To fix this for interior vertices any coordinate could be chosen to be rederived, so we can say it's always w=1-u-v. But boundary vertices need to be symmetric. To do that I quantize the median barycentric and rederive the max barycentric given they are normalized (the min is always zero on the boundary).

Uniform density splitting

The Tessellation Table can be used for splitting as well. Typically binary splitting is used. There are advantages to using a wider branching factor though. Wider means a shallower tree, less recursion, and thus less traffic to and from a work queue. Perhaps more importantly though it has the potential to generate more uniformly shaped subpatches for the same reason we were interested in a uniformly dense final tessellation. This can reduce the number of subpatches and make each subpatch more likely to be uniform in dimensions and closer to having max DiceFactors, which we'll see matters later.

Diagsplit longest edge splitting vs Uniform splitting

SplitFactors

How to best take advantage of this flexibility? Simplifying this question down to 1D and just looking at a single edge. If an edge has a TessFactor of 32, which is larger than the max TessFactor of 16, what SplitFactor should be used in this step? 32 is a multiple of 16 but it isn’t a power of 16 so there is a choice. Clamping to 16 means it will split into 16 subedges which each will then have a DiceFactor of 2. For reasons I will get into later it is important to have DiceFactors be as large as possible, or in other words do as much of the tessellation in the dicing phase as possible. So the other option in this example is SplitFactor of 2 and DiceFactor of 16.

The same question can be asked at every step of recursive splitting. Is it better to do the smaller factors early? Does the ordering matter besides for the final dicing step I mentioned already? Predicting too far ahead won’t work well since the desired TessFactor in an early step may not be what is chosen by the end because the projection on screen refines with smaller edges. How about the aspect ratio? Would it be better to address aspect ratio early and generate uniform sized subpatches as soon as possible? Unfortunately that isn't possible while still conforming to the limit of TessFactors being determined purely from that edge’s data.

In my tests the best calculation for turning desired TessFactor into the SplitFactor is the following:

SplitFactor = min( TessFactor / MaxDiceFactor, MaxSplitFactor )

This tries to emit subpatches from splitting with maximized DiceFactors but nothing else. Other choices were slower.

Results

Uniform dicing using the Tessellation Table results in 69% the diced triangles compared to D3D style uniform topology. Uniform splitting using the Tessellation Table results in 68% of the split patches compared to binary splitting. More uniformly sized triangles also benefit the rasterizer.

I believe this Tessellation Table approach could have wide applicability due to its more optimal density. The first such use has already been out for a while. The Tessellation Table UE builds has already been used with permission outside of UE in https://github.com/nvpro-samples/vk_tessellated_clusters.

Possible approaches for tessellation

Requirements

All the original goals of Nanite should apply to our approach here as well. One of them implicitly covers the rest: authoring decisions should have no impact on performance. While not 100% realized, Nanite mostly behaves that way so that principle should be maintained if at all possible. Applied here would mean a run-time tessellated and displaced mesh should render just as fast as an offline tessellated and displaced Nanite mesh. So the performance characteristics of Nanite, and thus its goals to the extent they were realized, should ideally be shared by Nanite Tessellation. This is not strictly a requirement because, as we'll see by the end, it was not achieved. But it very much was a goal and the closer we can get to this ideal the better.

Tracing

Tessellation is actually not a requirement, it’s an implementation detail. Displacement is the artist facing feature. There are a variety of tracing based approaches to scalar displacement.

Shell mapping and its descendants find the ray enter and exit point through the prism formed by the base triangle extruded along its vertex normals, then ray march the displacement function in tangent space. Displaced Micro Maps are similar except the ray march is replaced with a quadtree traversal that acts as an acceleration structure for the barycentric space. Neither have any acceleration in the displacement direction. This means if the displacement range is large compared to the size of base triangles there will be performance problems. There will be many tall skinny prisms with high overdraw and no way to quickly skip empty space. The expectation with these techniques is that the prisms will be shallow. In the case of DMMs this comes from their creation offline. That does not apply here since the base mesh will be an arbitrary Nanite mesh that could be dense and the displacement function is a shader with a range specified by an artist.

Thonat et al. traverse a quadtree acceleration structure that bounds the displacement direction as well. Unfortunately it assumes that displacement is a single texture, not a shader, and that minmax mipmaps (the acceleration structure) can be generated for that texture. If the shader results were cached in texture space this might be viable. The origins of the approach to bound displacement with interval or affine arithmetic were actually for the purpose of tracing shaders, so it is possible. Unfortunately, the cost, even in the simple single texture case, puts this outside our needs.

That leaves us with rasterization and thus some form of tessellation.

Work within the current framework

Tessellation and displacement mapping were in mind with the original design of Nanite. The idea being triangle clusters could be synthesized instead of streamed from disk when finer detail levels were requested. Once we have the core Nanite based on offline simplification working well and shipped we can add on with tessellation being the first obvious extension.

This is a really elegant approach to the problem. It means the same framework can be used to solve that problem as well. Tessellation and displacement mapping in addition to other potential forms of geometry synthesizing, maybe marching cubes or subd surfaces, could be implemented and at basically no additional run-time cost. IO and transcoding would be traded for generation. The per frame cull and rasterization would be identical regardless of the source the triangles came from. All the work of generating that geometry is cached and reused across many frames. Going this route makes it conceivable that the goals from the Nanite dream could be achieved instead of this just adding cost.

As the design of Nanite was being realized, little by little it was becoming clear this idea wasn’t realistic. Every step of the Nanite build process was a bit more complicated than expected with extra details, constraints, or edge cases that weren’t obvious until we seriously implemented them and battle tested it all. Synthesizing tessellated clusters changes the process from simplification to amplification. Basically this amounts to running the Nanite build process in reverse. Now that the details of that process were better understood, doing it in reverse, in a random access sort of way where a complete level worth of clusters isn’t all available at once, in constrained memory, in the same budget that transcoding is currently costing, is not remotely straightforward and potentially not even possible.

I have ideas on how the process could be modified by maybe replacing graph cuts with something more spatial or precomputing portions but not all of the task. There are some important flaws though that were discovered that are inherent to the idea.

Both simplification and amplification

Tessellation to a uniform sampling resolution suitable for displacement mapping is not simply a matter of adding additional levels, like generating a level -1 past level 0, (0 being the original source triangles). Triangles from the source mesh larger than 1 pixel may not be flat anymore and need to be tessellated but at the same time tiny triangles may be far smaller than a pixel. Levels can’t simply be divided into exclusively simplification or amplification, both are needed simultaneously.

The base Nanite structure accounts for only the error against the base mesh, not the error against the displaced mesh. A simple way to solve that is the stored levels are tessellated at build time to a desired resolution matching that level’s error. Then runtime amplification picks up from there by generating more such levels. But that means the Nanite mesh needs to be built differently to support displacement mapping and at a significant cost. Far more triangles and vertices will need to be stored and rendered than otherwise needed compared to the normal Nanite mesh.

Adaptive tessellation

Another major flaw with this idea is that base Nanite adapts the triangle density to the content. This happens naturally with quadric based mesh simplification. Flatter areas can use fewer larger triangles to hit the same error. To achieve the same rendering performance and run-time memory overhead from generated triangle clusters the triangles would need to be just as efficiently placed. This simply isn’t possible. Even getting half way there with good content adaptive tessellation is incredibly challenging. So the reality is there is no chance generated triangle clusters will be the same cost to store and render as offline simplified ones, even if the cost to generate them is free. Far more of them will be needed to hit the same error due to less efficient use of triangles to approximate the surface.

Not only is it very difficult to adaptively place triangles to efficiently represent the underlying signal, unlike core Nanite, the signal is not known up front. Displacement comes from a user defined shader. It must be sampled. This presents a problem. The error, or the difference between the limit surface and the tessellated one, can’t be known exactly. The best we can do is consider the error to be the sampling rate. This is reasonable if the signal is band limited. Hopefully it is due to mipmaps but given it is user defined there is no guarantee of that.

True micropoly

With this new measurement for error it is clear that what we will be rendering are true micropolys. To hit 1 pixel error all triangles must be <=1 pixel wide. Many people mistakenly think this is what Nanite was already doing. Our software rasterizer is designed to be efficient for micropolys but that is not the LOD target. Nanite targets a LOD with 1 pixel of error not 1 pixel triangles. Some triangles need to be pixel sized to be within that error but most aren’t. Losing content adaptive thus means far more triangles for the same content so there is no chance this doesn’t cost more than an offline tessellated Nanite mesh.

That assumes all else being equal, as in the original Nanite rendering pipeline is still the fastest way to render this. Maybe not. Nanite’s LOD decisions are very coarse. It works on decently large cluster group granularity with conservative bounding volumes and jumps in power of 2 increments. Ignoring the spatial granularity and conservativeness, pow2 alone means on average the triangle count is at least 33% greater than the ideal. Could a different design make up for the increase in triangle count from losing content adaptive by hitting closer to the optimal number of uniformly sized triangles? Doing so means stepping outside the existing framework and dynamically tessellating patches every frame.

Reyes

The Reyes rendering architecture was the first to support displacement mapping and is designed around efficiently tessellating surfaces into micropolys. Therefore it is an obvious reference point for this problem.

In Reyes a primitive goes through the following pipeline:

Bound
Split
Dice
Shade
Rasterize

The bounding box for a primitive is computed. If it is off screen, cull it. If it is too large the primitive is split, usually in two, and the sub primitives are sent back to Bound. This will continue recursively until a primitive is small enough to dice. Dicing converts the primitive into a uniform grid of micropolys. The vertices of that grid are shaded and finally the micropolys are rasterized.

Why have both split and dice? Recursive splitting allows visibility to be retested at a more uniform granularity. It also allows surfaces that cover a large depth range to tessellate at a varying density, better matching the view. This recursive splitting is actually very similar to Nanite’s cluster hierarchy traversal, both in the approach and the reasons for it. Why not only split? There are efficiencies that are important at the leaf level that motivate dicing being special.

Reyes has been used heavily in offline renderers and film production for decades. Even after the move away from Reyes to path tracing, some production path tracers (Manuka, PRMan, etc) still run the majority of this pipeline. Instead of rasterizing the micropolys they trace rays against them.

Real-time Reyes

Because of its success in film, real-time Reyes adapted for GPUs has long been a target with numerous research papers (Patney and Owens, RenderAnts, DiagSplit, FracSplit, Sattlecker and Steinberger, etc) dedicated to possible approaches. As far as I know Nanite Tessellation in Unreal Engine 5.4 is the first shipping real-time Reyes implementation and Fortnite is the first it has shipped in a game (although only used on the ground).

While Nanite Tessellation retains every aspect of the high-level Reyes algorithm, there are many differences in the details, more than just in how it integrates with the base Nanite algorithm. Starting with the most basic: the primitives in our case are triangular patches. They start as triangles from a triangle mesh which are further split into triangular subpatches. This continues recursively until the subpatches are small enough to dice. Dicing uniformly tessellates the patch into microtris.

Shade only evaluates the displacement function at the diced triangle vertices. All other shading is done at pixel frequency in screen space. This is simply more efficient due to the amount of overshade that object space shading incurs. True preshading is a relic of the past. Modern production path tracers either shade on hit for everything not displacement as well or at most evaluate material shaders into BxDF lobes similar to a GBuffer and then shade with that on hit.

Nanite Tessellation

Nanite Tessellation, aka Nanite Dynamic Tessellation, aka Nanite Dynamic Displacement was the next major feature I worked on after Nanite itself. Initial prototypes started back in 2020, only months after showing Nanite publicly for the first time. UE5 still hadn’t even been released to customers yet. After a couple years of shipping Nanite in things and then a couple of years more of development, Nanite Tessellation finally shipped in UE 5.4 in 2024. I started this write up shortly after but it has taken far longer to complete than I ever expected. Needless to say, publishing all this has been a long time coming. It will come in a series of posts starting with this one.

List of posts:

Intro
Possible approaches
How to tessellate
Nanite + Reyes
Variable sized work
Vertex deduplication / Post transform cache (coming soon)
VisBuffer / Deferred materials
Wrapping up

What is Nanite Tessellation?

A system for dynamically tessellating meshes and displacing them. The displacement comes from a shader graph, authored in UE’s material editor. This tessellation is in addition to what Nanite already provides.

Tessellation demoed at GDC in Marvel 1943: Rise of Hydra

Patches

Diced triangles

Final pixels

Why?

Why is geometry amplification needed when we have Nanite? I’ve argued in the past that amplification approaches to the virtualized geometry problem were not good enough, so why would I start working on it now? Have I changed my mind? No. My argument was that amplification approaches are not a general purpose solution to the virtualized geometry problem. They do not solve all cases. They can’t change the genus of a surface. A simplification approach would always be needed. If you have that it could also solve amplification in a way. A mesh could always be synthesized, subdivided, tessellated, and/or displaced offline. Then simplification can reduce it down. This ignores the data storage implications but it does show that it is the more general purpose solution to that problem.

So we have that now. It’s called Nanite and is pretty cool. It was the right thing to work on first. But just because this solution is general purpose enough that it can be used for these other cases does not mean it is ideal for them. Storing full topology of an irregular mesh covers all cases but is expensive. Storing every position on the surface as a full 3d point with a complete set of attributes is expensive. We do our best to compress that data but nothing beats not having that data at all.

Compression

Scalar displacement fields, whether they are artist authored maps or captured through projection of a detailed surface to a simpler one, are much less data. 1 value compared to 5+. Compression of regular 2D data, ie images, in relation to human perception is vastly more researched and well understood.

Comparison of disk size for high poly vs low poly with normal and displacement maps

Even better data compression than that are procedural texturing approaches. What do I mean by procedural texturing? I don’t just mean mathematical functions like Perlin noise. I might be pushing the definition a bit but even simple texture tiling in a way is a form of procedural texturing. But certainly once shaders are involved where multiple textures are mixed and modified we are in the realm of procedural. The simplest form of this is detail texturing. A much higher frequency signal can be represented than stored explicitly. Viewed statically like this, the compression ratio can be far higher than is achievable through any other means.

Authoring

But beyond data compression, procedural content generation can be an incredibly effective time saver for an artist. It also can be reusable, dynamic, and animatable. By reusable I mean that a base material type, like snow, can be authored once and applied to many surfaces. By dynamic I mean the same asset can accumulate snow over time by changing the shader parameters, all the way to full animation like a moving lava field flow.

Displacement maps are extremely common in film and the primary reason for their use is not data compression. A good bit of it is tooling and while I could say that should be improved and is someone else’s responsibility to keep up with Nanite’s capabilities, the fact of the matter is I can’t snap my fingers and change all the DCCs. Even if every application were all optimized to better work with high poly meshes there is always something inherently simpler with 2d textures, and displacement maps are no different.

Displacement’s use in film also helps animation. For a character the base cage can be rigged and deformed. The deformed cage can then be smoothly subdivided and displaced to get the final detail. This simplifies the rigger’s and animator’s concerns and separates them to an extent from the sculptor who might carve out individual dragon scales.

The last use case is specific to games. Scalability is an important consideration for Fortnite as well as other games that still need to support lower end platforms that aren’t powerful enough to run the Nanite pipeline. We can easily generate low poly fallback meshes through the same mesh simplification algorithm that Nanite uses, but what is fine for the distance isn’t necessarily good enough for up close. The art of low poly modelling is often a matter of abstraction of shape and artists are much more picky about the results. They will also move detail between domains, from mesh to texture, that requires involvement of other assets that is difficult or impossible to automatically do reliably. For these reasons, when a large scalability range is required, like with Fortnite, our art teams have been more comfortable authoring for low or mid in the scalability range and amplifying up rather than authoring for high and simplifying down.

Saturday, May 12, 2018

Normal map filtering using vMF (part 3)

$$ \newcommand{\vv}{\mathbf{v}} \newcommand{\rv}{\mathbf{r}} \newcommand{\muv}{\boldsymbol\mu} \newcommand{\omegav}{\boldsymbol\omega} \newcommand{\mudotv}{\muv\cdot\vv} $$ What can we use this for? One example of a place where distributions are summed up is in normal map and roughness filtering. Normal and roughness maps are textures describing the distribution of microfacet normals. The normal of the normal map is the mean of the distribution and the roughness describes the width of the distribution. We can fit our chosen NDF with a vMF by finding a mapping from roughness to sharpness $\lambda$.

This mapping for Beckmann is given by [1] as: \begin{equation} \lambda \approx \frac{2}{\alpha^2} \label{eq:roughness_to_lambda} \end{equation} and following my previous post about specular models we can use the $\alpha$ from any of those distributions in this equation for a reasonable approximation.

Once you have vMFs we can sum or filter them in $\rv$ form. Then we can turn it back to normal and roughness by inverting the function: \begin{equation} \alpha \approx \sqrt{\frac{2}{\lambda}} \label{eq:lambda_to_roughness} \end{equation} We must be careful with floating point precision and divide by zero though. Instead of calculating $\lambda$ we can instead calculate its reciprocal which avoids multiple places where a divide by nearly zero can happen.

// Convert normal and roughness to r form

float InvLambda = 0.5 * Alpha*Alpha;

float exp2L = exp( -2.0 / InvLambda );

float CothLambda = InvLambda > 0.1 ? (1 + exp2L) / (1 - exp2L) : 1;

float3 r = ( CothLambda - InvLambda ) * Normal;

// Filter in r form

// Convert back to normal and roughness

float r2 = clamp( dot(r,r), 1e-8, 1 );

InvLambda = rsqrt( r2 ) * ( 1 - r2 ) / ( 3 - r2 );

Alpha = sqrt( 2 * InvLambda );

Normal = normalize(r);

How does this compare to the common approaches? The first to do something like this was Toksvig [2] which follows similar logic with vector length corresponding with gloss and uses properties of Gaussian distributions but not SGs exactly. LEAN mapping [3] is based on Gaussians as well but planar distributions, not spherical. The approach I just explained should in theory work just as well with object space normals.

Even though it was part of the original approach the common way to use "Toksvig" filtering (including UE4's implementation) is to find the normal variance and increase the roughness by it. There is no influence from the roughness on the normals when doing that and there should be. The correct way will affect how the normals are filtered. A smooth normal should have more weight in the filter than a rough normal.

vMF has been used for this task before in [5] and later [6]. There is a major difference from our approach in that Frequency domain normal map filtering relies on convolving instead of averaging. It finds the vMF for the distribution of normals over the filter region. It then convolves the normal and roughness by that vMF. But what is a convolution?

Convolution

Graphics programmers know of convolutions like blurring. It sort of spreads data out right? What does it mean mathematically though? A convolution of one function by another creates a new function that is equivalent to the integral of the function being convolved multiplied by a the convolving function translated to that point.

Think of a blur kernel with weights per tap. That kernel center is translated to the pixel in the image that we write the blur result to. Each tap of the kernel is a value from the blur function. We multiply those kernel values by the image that is being convolved. All of those samples are then added together. Now usually a blur doesn't have infinite support or every pixel of the image would need to be sampled but the only reason that doesn't need to happen is because the convolving function, ie the blur kernel, is zero past a certain distance from the center of the function. Otherwise the integral needs to cover the entire domain. In the 1D case that means from negative to positive infinity. In the case of a sphere that means over the entire surface of the sphere.

This symbolically looks like this for 1D: \begin{equation} (f * g) (x) = \int_{-\infty}^\infty f(t) g(x-t)\,dt \end{equation} We now have the definition but why would we want to convolve a function besides image blurring? A convolution of one function by another creates a new function that when evaluated is equal to if the both functions were multiplied together and integrated at that translated point. Think of this like precalculating the multiplication and integration of those functions for any translated point. The integral of the product is done ahead of time and now we can evaluate it for any translation.

This is exactly the use case for preconvolving environment maps by the reflected GGX distribution. GGX is the convolving function, the environment map is the function being convolved, the reflection vector direction used to sample the preconvolved environment map is the "translation". SGs are very simple to multiply and integrate as we have already seen so precomputing it often doesn't save much. Convolving does have its uses though so let's see how to do it.

Convolving SGs

The convolution of two SGs is not closed in the SG basis, meaning it does not result in exactly a SG. Fortunately it can be well approximated by one. [7] gave a simple approximation that is fairly accurate so long as the lobe sharpnesses aren't very low: \begin{equation} \begin{aligned} \left(G_1 * G_2\right) \left( \vv \right) &= \int_{S^2} G_1(\omegav) G_2\left( \omegav; \vv, \lambda_2, a_2 \right) \,d\omegav \\ &\approx G \left( \vv; \muv_1, \frac{\lambda_1 \lambda_2}{\lambda_1 + \lambda_2}, 2\pi\frac{a_1 a_2}{\lambda_1 + \lambda_2} \right) \end{aligned} \label{eq:convolve_sg} \end{equation} The first line of the equation above may shed more light on how we can use this if it isn't clear already. This is identical to the inner product but with $\muv_2$ replaced with a free parameter.

For the case of normal map filtering we don't care about amplitude. We want a normalized SG. That means for this case the only part that matters is the convolved $\lambda'$: \begin{equation} \lambda' = \frac{\lambda_1 \lambda_2}{\lambda_1 + \lambda_2} \end{equation} We can ignore the rest of eq \eqref{eq:convolve_sg} for the moment. If we replace $\lambda$ everywhere with $\alpha$ using eq \eqref{eq:lambda_to_roughness} we get a nice simple equation: \begin{equation} \alpha' = \sqrt{ \alpha_1^2 + \alpha_2^2 } \end{equation} Leave $\lambda$ in for one of them and we get: \begin{equation} \alpha' = \sqrt{ \alpha^2 + \frac{2}{\lambda} } \label{eq:alpha_prime} \end{equation} which looks just like what [6] used except for the 2 factor. I believe this is a mistake in their course notes. In equation (37) of their notes they have it as 1/2 and in the code sample it is 1. I think the confusion comes from the Frequency Domain Normal Map Filtering paper working with Torrance Sparrow and not Cook Torrance, and $\sigma \neq \alpha$. Overall it means less roughness from normal variance. In my tests using eq \eqref{eq:alpha_prime} that we just derived looks closer to Toksvig results. Otherwise the range is off and less rough. MJP uses the same 2/a^2 for SG sharpness in his blog post so we don't disagree there.

As a gut check if $\alpha=0$ and all final roughness comes from normal variation then $\alpha'=\sqrt{\frac{2}{\lambda}}$ which is what we established in eq \eqref{eq:lambda_to_roughness}. If there is no normal variation then this equation explodes but if you calculate InvLambda like I did in the code snippet the second term becomes zero and $\alpha'=\alpha$ which is what we want.

Next up, converting from SH to SG (coming soon).

References

[1] Wang et al. 2007, "All-Frequency Rendering of Dynamic, Spatially-Varying Reflectance"
[2] Toksvig 2004, "Mipmapping Normal Maps"
[3] Olano et al. 2010, "LEAN Mapping"
[4] Hill 2011, "Specular Showdown in the Wild West"
[5] Han et al. 2007, "Frequency Domain Normal Map Filtering"
[6] Neubelt et al. 2013, "Crafting a Next-Gen Material Pipeline for The Order: 1886"
[7] Iwasaki 2012, "Interactive Bi-scale Editing of Highly Glossy Materials"

von Mises-Fisher (part 2)

$$ \newcommand{\vv}{\mathbf{v}} \newcommand{\rv}{\mathbf{r}} \newcommand{\muv}{\boldsymbol\mu} \newcommand{\mudotv}{\muv\cdot\vv} $$ A normalized SG has the same equation as the probability distribution function for a von Mises-Fisher (vMF) distribution on the 3 dimensional sphere. This affords us a few more tools and applications to work with. A vMF distribution can be defined for any dimension. I'll focus on 3D here because it is the most widely usable for computer graphics and simplifies discussion. Because a vMF does not have a free amplitude parameter it is written as: \begin{equation} \begin{aligned} V(\vv;\muv,\lambda) = \frac{\lambda}{ 2\pi \left( 1 - e^{-2 \lambda} \right) } e^{\lambda(\mudotv - 1)} \end{aligned} \label{eq:vmf} \end{equation} The more common form you will likely see in literature is this: \begin{equation} \begin{aligned} V(\vv;\muv,\lambda) = \frac{\lambda}{ 4\pi \sinh(\lambda) } e^{\lambda(\mudotv)} \end{aligned} \label{eq:vmf_sinh} \end{equation} which is equivalent due to the identity \begin{equation} \begin{aligned} \sinh(x) = \frac{ 1 - e^{-2x} }{ 2e^{-x} } \end{aligned} \label{eq:sinh_identity} \end{equation} The form in eq \eqref{eq:vmf} is more numerically stable so should be used in practice as explained by [2].

Compare the equation for a vMF to the equation for a SG and it is easy to see that: \begin{equation} \begin{aligned} V(\vv;\muv,\lambda) = G\left( \vv; \muv, \lambda, \frac{\lambda}{ 2\pi \left( 1 - e^{-2 \lambda} \right) } \right) \end{aligned} \label{eq:vmf_to_sg} \end{equation} That means a vMF is equivalent to a normalized SG and by moving terms from one side to the other we can show that a SG is equivalent to a scaled vMF. \begin{equation} \begin{aligned} G\left( \vv; \muv, \lambda, a \right) = \frac{2\pi a}{\lambda} \left( 1 - e^{-2 \lambda} \right) V(\vv;\muv,\lambda) \end{aligned} \label{eq:sg_to_vmf} \end{equation}

Fitting a vMF distribution to data

Fitting a vMF distribution to directions or points on a sphere is a very similar process as fitting a normal distribution to points on a line. In the case of a normal distribution, one calculates the mean and variance of the data set and then chooses a normal distribution with the same mean and variance as the best fit to the data.

For the vMF distribution the mean direction and spherical variance are used. Calculating these properties for a set of directions is simple. \begin{equation} \begin{aligned} \rv = \frac{1}{n}\sum_{i=1}^{n} \textbf{x}_i \end{aligned} \label{eq:r_average} \end{equation} where $\textbf{x}_1, \textbf{x}_2, ..., \textbf{x}_n$ are a set of unit vectors.

Often values are associated with these directions. So instead taking a simple average we can take a weighted average. \begin{equation} \begin{aligned} \rv = \frac{\sum_{i=1}^{n} \textbf{x}_i w_i}{\sum_{i=1}^{n} w_i} \end{aligned} \label{eq:r_weighted_average} \end{equation} We have the two properties, the mean direction $\muv = \frac{\rv}{\|\rv\|}$ and the spherical variance $\sigma^2 = 1 - \|\rv\|$. To fit a vMF distribution to the data we need to know what these properties are for the vMF distribution. Since the vMF distribution is convex, circularly symmetric about its axis, and is max in the direction of $\muv$, it is fairly obvious that the mean direction will be $\muv$ so I won't derive that here.

The spherical variance $\sigma^2$ on the other hand is a bit more involved. Because we already know the direction of $\rv$ is $\muv$ we can simplify this calculation to the integral of the projection of the function onto $\muv$. \begin{equation} \begin{split} \|\rv\| &= \int_{S^2} V(\vv;\muv,\lambda) (\mudotv) d\vv \\ &= \frac{\lambda}{ 4\pi \sinh(\lambda) } \int_{S^2} e^{\lambda(\mudotv)} (\mudotv) d\vv \\ \end{split} \end{equation} Because the integral over the sphere is rotation-invariant we will replace $\muv$ with the x-axis. \begin{equation} \begin{split} &= \frac{\lambda}{ 4\pi \sinh(\lambda) } \int_{0}^{2 \pi} \int_{0}^{\pi} e^{\lambda\cos\theta} \cos\theta\sin\theta d\theta d\phi \\ &= \frac{\lambda}{ 4\pi \sinh(\lambda) } 2 \pi \int_{0}^{\pi} e^{\lambda\cos\theta} \cos\theta\sin\theta d\theta \\ \end{split} \end{equation} Substituting $t=-\cos\theta$ and $dt=\sin\theta d\theta$ \begin{equation} \begin{split} &= \frac{\lambda}{ 2 \sinh(\lambda) } \int_{-1}^{1} -t e^{-\lambda t} dt \\ &= \frac{\lambda}{ 2 \sinh(\lambda) } \left( \frac{ 2 \lambda \cosh(\lambda) - 2 \sinh(\lambda) }{ \lambda^2 } \right) \\ &= \frac{\cosh(\lambda)}{ \sinh(\lambda) } - \frac{\sinh(\lambda)}{ \lambda \sinh(\lambda) } \\ \end{split} \end{equation} Arriving in its final form \begin{equation} \|\rv\| = \coth(\lambda)-\frac{1}{\lambda} \label{eq:r_length} \end{equation} Although simple in form, this function unfortunately isn't invertible. [1] provides an approximation which is close enough for our purposes. \begin{equation} \begin{aligned} \lambda &= \|\rv\| \frac{ 3 - \|\rv\|^2}{1 - \|\rv\|^2} \end{aligned} \end{equation} Now that we have a way to calculate the mean and spherical variance for a data set and we know the corresponding vMF mean and spherical variance, we can fit a vMF to the data set.

Using eq \eqref{eq:r_weighted_average} to calculate $\rv$, the vMF fit to that data is \begin{equation} V\left( \vv; \frac{\rv}{\|\rv\|},\|\rv\| \frac{ 3 - \|\rv\|^2}{1 - \|\rv\|^2} \right) \label{eq:r_to_vmf} \end{equation}
Going the other direction from $V(\vv;\muv,\lambda)$ form to $\rv$ form using eq \eqref{eq:r_length} is this: \begin{equation} \rv = \left( \coth(\lambda)-\frac{1}{\lambda} \right) \muv \label{eq:vmf_to_r} \end{equation}

Addition of SGs

We now have a way to convert to and from $\rv$ form. $\rv$ is linearly filterable as shown in how it was originally defined in eq \eqref{eq:r_weighted_average}. This means if our vMF functions are representing a spherical distribution of something then a weighted sum of those distributions can be approximately fit by another vMF. In other words we can approximate the resulting distribution by converting to $\rv$ form, filtering, and then converting back to traditional $V(\vv;\muv,\lambda)$ form.

By using the weighted average eq \eqref{eq:r_weighted_average} we can apply this concept to non normalized SGs too. This allows us to not just filter (ie sum with a total weight of 1) but add as well. A non-normalized SG as shown in eq \eqref{eq:sg_to_vmf} is a scaled vMF. We can use this scale as the weight when summing and use the total weight as the final scale for the summed SG.

This is the $\rv$ form for $G(\vv;\muv,\lambda, a)$. It includes an additional weight value you can think of like the energy this SG is adding to the sum: \begin{equation} \begin{aligned} \rv_i &= \left( \coth(\lambda_i)-\frac{1}{\lambda_i} \right) \muv_i \\ w_i &= \frac{2\pi a_i}{\lambda_i} \left( 1 - e^{-2 \lambda_i} \right) \\ \end{aligned} \end{equation} This weight is of course used in the weighted sum \begin{equation} \begin{aligned} \rv &= \frac{\sum_{i=1}^{n} \rv_i w_i}{\sum_{i=1}^{n} w_i} \\ w &= \sum_{i=1}^{n} w_i \\ \end{aligned} \end{equation} Using eq \eqref{eq:r_to_vmf} and eq \eqref{eq:vmf_to_sg} we can convert back to a scaled vMF and finally to a SG in $G(\vv;\muv,\lambda, a)$ form: \begin{equation} \begin{aligned} G\left( \vv; \muv, \lambda, a \right) &= w V(\vv;\muv,\lambda) \\ &= G\left( \vv; \muv, \lambda, w \frac{\lambda}{ 2\pi \left( 1 - e^{-2 \lambda} \right) } \right) \end{aligned} \end{equation} While addition and filtering are approximate they can be useful. The accuracy of the result is very dependent on the angle between the $\mu$ vectors or lobe axii. Adding sharp lobes pointed in different directions will result in a single wide lobe.

Next, what we can use this for:
Normal map filtering using vMF

References

[1] Banerjee et al. 2005, "Clustering on the Unit Hypersphere using von Mises-Fisher Distributions"
[2] Jakob 2012, Numerically stable sampling of the von Mises Fisher distribution on S2 (and other tricks)"

Spherical Gaussians (part 1)

$$ \newcommand{\vv}{\mathbf{v}} \newcommand{\rv}{\mathbf{r}} \newcommand{\muv}{\boldsymbol\mu} \newcommand{\mudotv}{\muv\cdot\vv} $$ A Spherical Gaussian (SG) is a function of unit vector $\vv$ and is defined as \begin{equation} G(\vv;\muv,\lambda, a) = a e^{\lambda(\mudotv - 1)} \end{equation} where unit vector $\muv$, scalar $\lambda$, and scalar $a$ represent the lobe axis, lobe sharpness, and lobe amplitude of the SG, respectively.

The formula can be read as evaluating a SG in the direction of $\vv$ where the SG has the parameters of $\muv,\lambda, a$. An abbreviated notation $G(\vv)$ can be used instead when the parameters can be assumed. Often the more verbose notation is used to assign values to the parameters.

SGs have a number of nice properties including simple equations for a number of common operations.

Product of Two SGs

The product of two SG's can be represented exactly as another SG. This product is sometimes referred to as the vector product. This formula was first properly given in [1] (it was shown earlier but in an non-normalized form).

Let $\lambda_m = \lambda_1 + \lambda_2$ and let $\muv_m = \frac{\lambda_1\muv_1 + \lambda_2\muv_2}{\lambda_1 + \lambda_2}$, then \begin{equation} \begin{split} G_1(\vv)G_2(\vv) = G\left(\vv; \frac{\muv_m}{\|\muv_m\|}, \lambda_m\|\muv_m\|, a_1 a_2 e^{\lambda_m\left(\|\muv_m\| - 1\right)}\right) \end{split} \label{eq:sg_product} \end{equation}

Raising to a power

Given that the product of two SGs is another SG it shouldn't be much of a surprise that a SG raised to a power can be expressed exactly as another SG: \begin{equation} \begin{aligned} G(\vv)^n &= G(\vv; \muv,n\lambda, a^n) \end{aligned} \label{eq:sg_power} \end{equation}

Integration Over The Sphere

The integral of a SG over the sphere has a closed form solution.

[2] showed that the integral was: \begin{equation} \int_{S^2}G(\vv) d\vv = 2 \pi \frac{a}{\lambda} \left( 1 - e^{-2\lambda} \right) \label{eq:sg_integral} \end{equation}

Inner product

The inner product is defined as the integral over the sphere of the product of two SGs. We can already find the product of two SGs and integrate over a sphere. Putting those together we have: \begin{equation} \int_{S^2}G_1(\vv) G_2(\vv) d\vv = \frac{4 \pi a_0 a_1}{e^{\lambda_m}} \frac{ \sinh\left(\|\muv_m\| \right) }{ \|\muv_m\| } \label{eq:sg_inner_product_sinh} \end{equation} This equation has numerical precision issues when evaluated with floating point arithmetic. An alternative form which is more stable is the following: \begin{equation} \int_{S^2}G_1(\textbf{v}) G_2(\textbf{v}) d\textbf{v} = 2 \pi a_0 a_1 \frac{ e^{ \|\boldsymbol\mu_m\| - \lambda_m } - e^{ -\|\boldsymbol\mu_m\| - \lambda_m } }{ \|\boldsymbol\mu_m\| } \label{eq:sg_inner_product_exp} \end{equation}

Normalization

Although there are other definitions for normalization I use the term to mean having an integral over the sphere equal to 1. Normalizing a SG is a simple matter of dividing it by its integral over the sphere. \begin{equation} \begin{aligned} \frac{ G(\vv) }{ \int_{S^2}G(\vv) d\vv } = G\left( \vv; \muv, \lambda, \frac{\lambda}{ 2\pi \left( 1 - e^{-2 \lambda} \right) } \right) \end{aligned} \label{eq:sg_normalized} \end{equation} Notice that the original $a$ parameter canceled out. Instead lobe amplitude is derived purely from the lobe sharpness $\lambda$.

These are all the common operations that have closed form solutions. So far nothing new here but hopefully it is helpful to have all these equations in a centralized place for reference. I didn't include derivations for any of these formulas. If readers think that would be useful to see maybe those could be added at a later date.

Special thanks to David Neubelt. Although this has been heavily modified from what we previously had I'm sure his touch is still present.

Now on to some less well covered concepts.
von Mises-Fisher (part 2)

References

[1] Wang et al. 2007, "All-Frequency Rendering of Dynamic, Spatially-Varying Reflectance"
[2] Tsai et al. 2006, "All-Frequency Precomputed Radiance Transfer using Spherical Radial Basis Functions and Clustered Tensor Approximation"

Spherical Gaussian series

Intro and backstory

About 4 years ago now I ran into Spherical Gaussian (SG) math in a few different publications in a row, enough that it triggered the pattern detection in my brain. All were using SGs to approximate specular lobes. I remember feeling very similar 10 years prior when Spherical Harmonics were starting to become all the rage. Back with SH I noticed it fairly early, primarily from Tom Forsyth's slides on the topic and took the time to dig into the math and make sure I had this new useful thing in my toolbox. Doing so has proven to be well worth the time. I decided that I should do the same again and learn SGs and related math, in particular to build up a toolbox of operations I can do with them. Maybe it would prove as useful as SH has.

In the years since I'd say it has certainly been worth the effort. I don't think I can say it has proven as useful as SH has been to computer graphics but it was still worth learning. I intended to write up what I had found and share the toolbox of equations compiled in a centralized place at the very least. Unfortunately laziness and procrastination got in the way.

Also scope creep. About 3 years ago I mentioned to David Neubelt that I intended to write this up and he too had done a lot of work with SGs at Ready at Dawn so we decided we'd collaborate and write a joint paper and submit it to JCGT. The intention was to make something similar to Stupid Spherical Harmonics (SH) Tricks but for SG. That scope and seriousness is much larger than a simple single author blog post. We worked on derivations to all the formulas, wanted to have quality solutions to cube map fitting, multiple use cases proven in production, and a ton of other things to make it an exhaustive, professional, and ultimately great paper. This was much more than I ever intended as a simple blog post. I still think that paper we had in mind would be great to exist but the actual end result is it bloated the expectation of what either of us had the bandwidth or maybe the attention span to complete and after a couple of months of work the unfinished paper regretfully stagnated.

A year went by and eventually MJP of Ready at Dawn did in fact do a blog series write up on Spherical Gaussians. It is excellent and I suggest you read it before continuing if you haven't already. There are still some things I intended to cover that he did not as well as things he did that I never have done nor planned to cover so I think these should compliment each other well.

It is a royal shame I have not posted this in the 3+ years since I intended to. I had even promised folks publicly a write up was coming and then didn't deliver. I haven't posted anything on this blog since then in fact. I hope to do better and hopefully finally getting this out will unclog the pipes.

Without further ado,

Part 1 - Spherical Gaussians
Part 2 - von Mises-Fisher
Part 3 - Normal map filtering using vMF
Part 4 - Coming soon...

Saturday, March 29, 2014

UE4 available to all

The big news from Epic at GDC this year was that Unreal Engine 4 is now available to everyone for only $19/month + 5% royalties.

There's been a lot said already about why this is cool, opinions, comparisons to competitors and so forth. From a business model point of view I feel it has been covered better than I could possibly say. If you are interested check out Mark Rein's post or hear it from the man himself Tim Sweeney for very compelling reasons why this is a good idea for us to provide and for developers to subscribe.

I wanted to give my own personal perspective as an engineer. What Epic just did is absolutely revolutionary and I am privileged to be part of it. I am super excited! Let me explain why.

If you've followed this blog for a while you may remember I gave Epic huge props for releasing UDK back in 2009. That was great for artists and designers, not that great for programmers. This is the next step down that path and its a doozy.

Now there have been naysayers that compare the numbers 19/month + 5%, is that better or worse, is it new or been done before, and so on. They are missing the point. It isn't the price, it isn't even the features. The revolution is this: for a 1/3 the cost of a new video game you can get access to the complete source code for our cutting edge game engine. The entire engine source code, every bit of it, the exact same we use in house and the same provided to private licensees, is available to you for only $19 (except for XB1 and PS4 code we aren't legally able to give you due to NDAs). This is the same tech that will be powering many of the top AAA games developed this generation. As Mark put it "Right now 7 of the top 21 (!) all-time highest rated Xbox 360 games (by Metacritic score) were powered by Unreal Engine 3" and you damn well better bet we are going to do the same or better this time around with UE4.

Now you may say John Carmack and id have open sourced their engines many times. That is true and I commend them for it. John has had a lasting impact on how many coders, myself included, write software due to these efforts. Unfortunately, the strict licensing terms have resulted in basically no commercial products using the id engines from that open source license. John has even lamented this recently "It is self-serving at this point, but looking back, I wish I could have released all the Id code under a more permissive license. GPL never did really do anything for game code, and I do wonder whether it was a fundamental cultural incompatibility. GPL was probably the best that could have flown politically for the code releases -- posterity without copy-paste into competition." And my own personal twist with this situation is after Zenimax bought id, their engines were no longer commercially licensable meaning anything built on top of that code base had to be scraped. GPL is simply not an option for commercial games.

There are other examples of open sourced game engines or cheaply priced engine source code but they all have something in common which is they were never up to date. The id engines were only open sourced years after the game that used them shipped. Id had already moved onto their next technology. For example the engine that powered Doom 3 wasn't opened sourced until 6 years after the game shipped. By that point Rage had even shipped. The reason for this is obvious. The point where releasing the code is non-threatening to execs is the point where a competitor can't use the code to their advantage. This means every single engine code base available to indie devs or students was either not commercially developed or purposely not competitive in its capabilities.

With the UE4 subscription, you can today get complete source that is totally up to date and will continue to be. This isn't any old engine, its the same cutting edge technology that will be powering many of the top AAA games of this generation. And as soon as we add new features you'll get them. In fact you'll even see the work in progress before they're done. How crazy is that?

Look, its easy to brush this off as the guy who works for Epic telling me I should give him money. That isn't why I'm writing this. What I am most excited about by far is in what I can share and give back the the gamedev community. That is the reason I have this blog, its the reason I have presented at conferences and will again in the future.

If you are a teacher, check out the license terms, they are ridiculously nice for schools. If you are a student, tell your school about it or grab a personal subscription.

For all those wanting to get into the game industry, the same response you will hear from everyone is make something. No one lands a game job because of their great grades or fancy degrees. They get it by making something cool. I wrote my own engine. That's how I landed my first job. Although I learned a ton if I were in that place today I would modify UE4. There is literally nothing else more applicable to a engine programming position than proving you can do the work. Hell, make something cool enough we'll hire you!

I can't wait to see what people make with this. It's a great time to be a programmer!

Sunday, December 15, 2013

Tone mapping

When working with HDR values, two troublesome situations often arise.

The first happens when one tries to encode an HDR color using an encoding that has a limited range, for instance RGBM. Values outside the range still need to be handled gracefully, ie not clipped.

The second happens when an HDR signal is under sampled. One very bright sample can completely dominate the result. In path tracing these are commonly called fireflies.

In both cases the obvious solution is to reduce the range. This sounds exactly like tonemapping so break out those tone mapping operators, right? Well yes and no. Common tone mapping operators work on color channels individually. This has the downside of desaturating the colors which can look really bad if later operations attenuate the values, for instance reflections, glare, or DOF.

Instead I use a function that modifies only the luminance of the color. The simplest of which is this:

$$ T(color) = \frac{color}{ 1 + \frac{luma}{range} } $$
Where $T$ is the tone mapping function, $color$ is the color to be tone mapped, $luma$ is the luminance of $color$, and $range$ is the range that I wish to tone map into. If the encoding must fit RGB individually in range then $luma$ is the max RGB component.

Inverting this operation is just as easy. $$ T_{inverse}(color) = \frac{color}{ 1 - \frac{luma}{range} } $$
This operation, when used to reduce fireflies, can also be thought of as a weighting function for each sample: $$ weight = \frac{1}{ 1 + luma } $$
For a weighted average, sum all samples and divide by the summed weights. The result will be the same as if the samples were tone mapped using $T$ with $range$ of 1, averaged, then inverse tone mapped using $T_{inverse}$.

If a more expensive function is acceptable then keeping more of the color range linear is best. To do this use the functions below where 0 to $a$ is linear and $a$ to $b$ is tone mapped. $$ T(color) = \left\{ \begin{array}{l l} color & \quad \text{if $luma \leq a$}\\ \frac{color}{luma} \left( \frac{ a^2 - b*luma }{ 2a - b - luma } \right) & \quad \text{if $luma \gt a$} \end{array} \right. $$ $$ T_{inverse}(color) = \left\{ \begin{array}{l l} color & \quad \text{if $luma \leq a$}\\ \frac{color}{luma} \left( \frac{ a^2 - ( 2a - b )luma }{ b - luma } \right) & \quad \text{if $luma \gt a$} \end{array} \right. $$
These are same as the first two functions if $a=0$ and $b=range$.

I have used these methods for lightmap encoding, environment map encoding, fixed point bloom, screen space reflections, path tracing, and more.