Recent Update 2014

Overview
It has been a long time since my last post. Life was not that good here in Hong Kong, but I was still working on my engine in spare time. This post will show some of the stuff I have been working on in the past few months.

Shading
On graphics side, the engine is now switched to use physically based shaders with GGX model for specular and Oren-Nayar model for diffuse shading. The GGX model is implemented according to this paper from Unreal Engine 4[1]. While the Oren-Nayar model is implemented according to this paper from tri-Ace[2].

Meshes shaded with physically based shaders with different roughness
Oren-Nayar model is chosen over Lambert model because it takes roughness into account. During shading, for those mesh with roughness map but without normal map, using Oren-Nayar model will show a bit more details.

A mesh shaded without normal map under indirect lighting:
From left to right: final result, lighting only, normal, roughness, albedo 

Also, a radiosity[3] baking tool was written to calculate the indirect diffuse lighting for static mesh by rendering cube-maps at every light map texel position. The cube maps are then projected into Spherical Harmonics(SH) during the radiosity iteration. And the results are stored in SH luma + average chroma along the vertex normal hemi-sphere (but the chroma format doesn't play well with the texture compression, so may need to find another storage representation in the future...).

Direct + Indirect lighting
Direct lighting only
Lighting only

The indirect specular lighting is baked by capturing reflection probe and pre-filtered with GGX model according to the Unreal Engine 4 paper[1]. Currently only the closest reflection probe is used without parallax correction.

Reflection probes placed within the scene
Shading with pre-filtered cube-map

The indirect diffuse lighting for dynamic mesh is baked into the Irradiance Volumes[4], storing in SH coefficients. The SH coefficients are modified according to roughness described in the tri-Ace paper[2] (This is also done for the SH luma store in the light map for static mesh).

Irradiance Volume samples
Dragon shaded with Irradiance Volume

Shadow
The shadow system is updated to use with a mix of baked and real-time shadow. The light map baker described above calculate a shadow term for the main directional light at each light map texel and stored using signed distance field representation[5][6] (Also, an additional binary shadow term is calculated for each Irradiance Volume sample position for dynamic objects).

Real-time shadow only
baked shadow only
Baked + real-time shadow
For the dynamic soft shadow, Exponential Shadow Map(ESM)[7] is used. But the contact shadow looks too soft, so the shadow term calculated by ESM is raised to the power 4 (i.e. s'= s^4, where s is the shadow attenuation result from ESM) to make it darker.

Potential Visibility Set
A potential visibility set (PVS) baker is written to calculate which meshes are visible to the visibility cells for culling the scene during runtime. A brute force approach is used for baking by taking some sample positions on a given mesh (e.g. vertex position + light map texel position) and then rendering the scene to check whether the visibility cells are visible.

Render without PVS culling
Render with PVS culling
Final rendered result
Another view for the same camera render without PVS culling
Another view for the same camera render with PVS culling
Visibility Cells are placed within the scene for possible camera location

Particles
A basic particle system is implemented which can receive static lighting and receive static shadow. The particle are shaded on CPU using the Irradiance Volumes described above and can be calculated either per vertex, per particle or per emitter.

Particles with lighting and shadow enabled
Self-shadow disabled
The particles can also receive self shadow using the Fourier Opacity Mapping[8]. An opacity map is computed on CPU side for the main directional light which assume each particle is of sphere shape. Then a shadow term can be computed for shading.

Cross platform support
The engine runtime supports 3 different platforms: Windows, Mac, iOS(Editors are Windows only). On Windows, the engine mainly runs with D3D11. An extra OpenGL wrapper was written for Windows to ease the porting to iOS and Mac because it is easier to debug OpenGL with tools like Nsight.

The engine runs on Windows, Mac, iOS platforms

To write cross platform shaders, shaders are written in my own shading language which is similar to HLSL. Those shaders are then parsed by a shader parser generated by Flex and Bison[9] to obtain a syntax tree to output the actual HLSL and GLSL source code.

Final words
Hope you enjoy the above screen shots and wish I can find some time to describe them in details in future posts.
There are some other tasks implemented in the past few months,
such as various editors, audio coding as well as asset hot-reload
Reference
[1] Real Shading in Unreal Engine 4 http://blog.selfshadow.com/publications/s2013-shading-course/karis/s2013_pbs_epic_notes_v2.pdf
[2] Beyond a Simple Physically Based Blinn-Phong Model in Real-time http://research.tri-ace.com/Data/s2012_beyond_CourseNotes.pdf
[3] Radiosity http://en.wikipedia.org/wiki/Radiosity_(computer_graphics)
[4] Irradiance Volumes for Games http://developer.amd.com/wordpress/media/2012/10/Tatarchuk_Irradiance_Volumes.pdf
[5] Improved Alpha-Tested Magnification for Vector Textures and Special Effects http://www.valvesoftware.com/publications/2007/SIGGRAPH2007_AlphaTestedMagnification.pdf
[6] Distance Field Shadows http://udn.epicgames.com/Three/DistanceFieldShadows.html
[7] Exponential Shadow Maps http://research.edm.uhasselt.be/tmertens/papers/gi_08_esm.pdf
[8] Fourier Opacity Mapping http://sebastien.hillaire.free.fr/index.php?option=com_content&view=article&id=61&Itemid=72
[9] Flex and Bison http://aquamentus.com/flex_bison.html



Transforming points in unit square with p-norm

Introduction
Continue with previous post talking about some little tricks I used when implementing the animation editor. This time, I will talk about another maths problem when implementing the directional blend node in the animation tree editor. In this node, it blends 5 different animations(i.e. forward, backward, left, right and center) according to the current direction:

blending 5 different animation according to the current direction

And the UI of this node has a square input region like this for artist to preview how those animations are blended together:


So, to compute a blended output, we need to transform the points in the square region to a rhombus, and then we can use barycentric coordinates to determine the blend weight for blending:

Transform the current direction for computing the blend weight

p-norm
After searching google for a while, something called Lp-space has shown up with the following figures which looks similar to what I need:

Showing "unit circle" with different p-norm

All of the above figures are showing a "unit circle" (i.e. the vectors are of unit-length), but measured with different p-norms. The definition of p-norm is:


This equation describe the length of a vector. When p=2, it is the Euclidean norm that we normally use. Our goal is to transform points inside the unit square to the rhombus, in other words, we want the transformed points having the same length as before the transformation but measured with different p-norm, using p=1 after the transformation and p=infinity before transformation. In other words, we have (assume only dealing with the 2D case, and only consider points in the first quadrant):


, where v=(x, y) is the original point and v'=(x', y') is the transformed point.

Mapping the points
As our target is to find a function to transform the points, having only the above equation is not enough as there are infinitely many way to transform the point that satisfy the above equation. So we need another equation to find a unique solution, the idea is to have the transformed point, original point and the origin are lying on the same straight line(i.e. having the same slope), which gives another equation:
By solving the above equations, which gives the transform functions:
Taking into account those points in other quadrant and special case, which gives the final mapping functions:


However, taking the limit p to infinity and compute it with Wolfram Alpha does not gives any useful result... So I just take p=10 (taking a too large value will result in floating point precision problem...). Here is the plot of how the points are transformed/squeezed into the rhombus:

Graph showing how points are transformed from square to rhombus 

Although the function cannot transformed the points into a perfect rhombus, it does not have too much artifact when used for animation blending.

Conclusion
In this post, I have described how to map points inside a unit square to a "rhombus" which used for animation blending. But the problem is not completely solved as I am not taking the limit of p to infinity, and there are some power function in the transformation which is not fast... But this is enough for calculating the blend weight of the animations.

Reference
[1] Lp space: http://en.wikipedia.org/wiki/Lp_space

Checking whether a point lies on a Bezier curve

Introduction
It has been a long time since my last post. I was busy in the past months, and finally have time to finish dual-quaternion skinning and added some basic animation to my code base.

The animation editor
In the animation tree editor, those tree nodes can be connected/disconnected, which displayed by a cubic Bezier curve. I want the user can right click the curve to disconnect the tree nodes, so checking whether a point lies on a Bezier curve is need.

Sub-dividing the curve
A cubic Bezier is defined as:


solving an analytical  solution for this is quite complicated. So I just sub-divide the curve into several line segments and stop the sub-division if the points are close to a straight line. After that we can check if the point is lying on the line segments instead. First we start at the 2 end points of Bezier curve and check whether the mid-point(the red cross) need to be sub-divided.
check whether the red point need to be sub-divided
We can't simply check whether this 3 points close to a straight line because there may have an inflection point on the curve, so we need to look ahead 1 step further to see whether the 2 line segments(the blue and green lines below) are a straight line, if not, then the red point need to be sub-divided.
look ahead one more point to avoid inflection point problem
Repeat these steps for each newly generated sub-divided curve segments until all the points are close to a straight line (with a threshold). The sub-divided curve may look like this:

Before sub-division
After sub-division
With this approach, when we zoom into the graph, more points will get sub-divided:

Zooming in will sub-divide more points

Conclusion
This short post describe a way for checking whether a point is on a cubic bezier curve by using line sub-division. In the next post, I will talk about another fun stuff when writing the animation editor.