Extracting dominant light from Spherical Harmonics

Introduction
Spherical Harmonics(SH) functions can represent low frequency data such as diffuse lighting, where those high frequency details are lost after projected to SH. Luckily we can extract a dominant directional light from SH coefficients to fake specular lighting. We can also extract more than 1 directional light from SH coefficients, but this post will only focus on extracting 1 dominant light, those interested can read Stupid Spherical Harmonics (SH) Tricks for the details. A webGL demo is provided at the last section which will only extract 1 directional light.

Extracting dominant light direction
We can get a single dominant light direction from the SH projected environment lighting, Le. Consider we approximate the environment light up to band 1 (i.e. l=1):

Finding the dominant light direction is equivalent to choose an incoming direction, ω, so that Le(ω)is maximized. In other words, cosθ should equals to 1:

So we can extract the dominant light direction for a single color channel. Finally the dominant light direction can be calculated by scaling each dominant direction for RGB channels using the ration that convert color to gray scale:

Extracting dominant light intensity
After extracting the light direction, the remaining problem is to calculate the light intensity. That's mean we want to calculate an intensity s, so that the error between the extracted light and the light environment is at minimum (Le is the original environment light while Ld is the directional light):

To minimize the error, differentiate the equation and solve it equals to zero:

If both lighting functions are projected into SH, the intensity can be simplified to:

The next step is to project the directional light(with unit intensity) into SH basis (ci is the SH coefficient of the projected directional light):

Therefore the SH coefficients of projected directional light can be calculated by substituting the light direction into the corresponding SH basis function.

As the SH projected directional light is in unit intensity, we want to scale it with a factor so that the extracted light intensity s is the light color that can be ready for use in direct lighting equation which is defined as (detail explanation can be found in [4]):

For artist convenience, clight does not correspond to a direct radiometric measure of the light’s intensity; it is specified as the color a white Lambertian surface would have when illuminated by the light from a direction parallel to the surface normal (lc = n).

So we need to calculate a scaling factor, c, that scale the SH projected directional light such that:

We can project both L(ω) and (n . ω) into SH to calculate the integral. To project the transfer function (n . ω) into SH, we can first align the n to +Z-axis, which is zonal harmonics, then we can rotate the ZH coefficient into any direction using the equation:

The ZH coefficients of (n . ω) are: (note that the result is different from Stupid Spherical Harmonics (SH) Tricks in the Normalization section as we have taken the π term outside the integral)

Then rotate the ZH coefficients such that the normal direction is equals to the light direction, ld (because we need ld = n as stated above), we have:

Finally we can go back to compute the scaling factor, c,  for the SH projected directional light (we calculate up to band=2):

Therefore the steps to extract the dominant light intensity are first to project the directional light into SH with a scaling factor c, and then light color, s,  can be calculated by:

WebGL Demo
A webGL demo (need a webGL enabled browser such as Chrome) is provided to illustrate how to extract a single directional light to fake the specular lighting from the SH coefficient. The specular lighting is calculated using the basic Blinn-Phong specular team for simplicity reason, other specular lighting equation can be used such as those physically plausible. (The source code can be downloaded from here.)

Your browser does not support the canvas tag/WebGL. This is a static example of what would be seen.

Render Diffuse
Render Specular
Rotate Model
Glossiness

Render Diffuse

Render Specular

Rotate Model

Glossiness

Conclusion
Extracting the dominant directional light from SH projected light is easy to compute with the following steps: First, calculate the dominant light direction. Second, project the dominant light into SH with a normalization factor. Third, calculate the light color. The extracted light can be used for specular lighting to give an impression of high frequency lighting.

References
[1] Stupid Spherical Harmonics (SH) Tricks: http://www.ppsloan.org/publications/StupidSH36.pdf

[2] Light Factorization for Mixed-Frequency Shadows in Augmented Reality: http://zurich.disneyresearch.com/~wjarosz/publications/nowrouzezahrai11light.pdf
[3] Physically Based Rendering, Second Edition: From Theory To Implementation Ch.17.2.2
[4] Physically-Based Shading Models in Film and Game Production: http://renderwonk.com/publications/s2010-shading-course/hoffman/s2010_physically_based_shading_hoffman_a_notes.pdf

[5] PI or not to PI in game lighting equation: http://seblagarde.wordpress.com/2012/01/08/pi-or-not-to-pi-in-game-lighting-equation/
[6] March of the Froblins: Simulation and Rendering Massive Crowds of Intelligent and Detailed Creatures on GPU: http://developer.amd.com/documentation/presentations/legacy/Chapter03-SBOT-March_of_The_Froblins.pdf
[7] Pick dominant light from sh coeffs: http://sourceforge.net/mailarchive/message.php?msg_id=28778827

Inverse Kinematics (2 joints) for foot placement

Introduction
Game sometimes need to solve Inverse Kinematics (IK) for more realistic look like foot placement on a terrain. There are different methods to solve an IK problems, some are numerical methods which can be used for general cases, and analytical solution exists only for simple cases like the case for 2 joints. I implemented the analytical method to handle the foot placement in my engine.

2D case
For simple case such as 2 joints in 2D case. In the following figure, suppose we want to rotate the blue leg to the position of the red leg so that the leg is aligned to the ground:

Since we know the pelvis joint position, target position, length of upper leg and lower leg, we can solve the angle α using law of cosines. Then, we can calculate the vector PK' by rotating the vector PT with angle α. Hence angle δ can be calculated with the dot product between the vector PK and vector PK'. The angle at knee joint can be solved either by law of cosines or dot product.

3D case
For the 3D case, it is similar to the 2D case except the rotation may not be on the same plane in order to make to IK results look good.

As there are infinitely many solutions to make the leg reach the target position (because the leg can rotate around the axis a highlighted in red), so we can first calculate one of the solution using law of cosines just like the 2D case (i.e. find the angle α in 2D case), hence we can calculate the upper leg vector v. As this is an arbitrary solution, the result may sometimes look funny:

So, the next step is to find a solution which is close to the pose made by the artist, in other words, we want to minimize the angle δ in the above figure, which is the angle between the arbitrary solution found in the above step and the thigh position posed by the artist. To minimize angle δ, we need to rotate the vector v around the axis a (the red line in the figure) with an angle θ to a new vector v'. In the below equation, v is rotated to v' using quaternion:

As minimizing δ is equivalent to maximizing cosδ (i.e. v'.k), we need to calculate the first derivative of cosδ  and the maximum/minimum value is achieved when equals to zero (all the vectors are normalized):

Then we can get two values of θ within a range of 2π, which correspond to maximizing and minimizing the cosδ. To distinguish whether which solution is maximizing cosδ, we need to substitute θ into the second derivative of cosδ to test whether it is greater than 0, if so, then that θ will minimize cosδ, otherwise, it will maximize cosδ.

Then we can rotate the arbitrary IK solution v with angle θ to v' to give a much better look:

Conclusion
This blog post present an analytical 2 joints IK solution in 3D case for foot placement. We first compute an arbitrary solution for the pelvis joint using law of cosines, then rotate that joint to minimize the angle between the joint after the IK solution and the posed joint before IK to give a much better look.

Reference
[1] http://www.3dkingdoms.com/ik.htm
[2] www.essentialmath.com/InverseKinematics.pps
[3]: The brick texture is obtained from Crytek's Sponza Model: http://crytek.com/cryengine/cryengine3/downloads
[4] The knight model is extracted from the game Infinity Blade using umodel.

Writing an iPhone Game Engine (Part 7- Postmortem)

Introduction
The first game that made with the iPhone game engine described in this series is released before Christmas on App Store, it is called Monster Bowling.

You may surprise that the final product is different from the screen shots shown before which is an adventure game that controlling a ship to explore the world. This is because someone in that project lost his passion and the production of that game has been stopped. And I do not want to waste my effort on making an engine without producing any game, so I decided to work with another artist which resulted in Monster Bowling. The engine and tools took me 9 months to write and the game code took me another 6 months of spare time to complete, which is quite a long time...

What we did wrong
Here I will summarize what mistake we have taken in these 2 projects.

First, the ship game project failed because the scale of the game is too big. Although some of the content is cut during production, there are still too many things need to take care and the team member gradually lose their passion about the game. So, my advice of making a game in spare time, especially when you work with other people the first time,  is don't try to make a big game. If anyone in the team lose their passion, the game will never get shipped no matter how hard you work.

Second, the other reason why the ship game failed because there is no a clear direction in the team, how the game project should progress and a clear schedule and check list what should be done. Without a direction, the team member will easily get lost and lost their passion.

Third, this point is about the released game Monster Bowling. When the game was just released, the sales was not good. It is because within this team, there is only 1 artist and 1 programmer, both were putting most of their effort on developing the game and didn't pay much attention to marketing the game and let the public know about the game. So when the game was just released, there didn't have any game review to boost the sales up.

Fourth, this point is about technical issue within the engine. Within the engine, both the game runtime and the editors use the same file format which is a binary format. But doing in this way resulted in a problem which cannot merge the files, for example, when the game objects within a game level are modified by 2 people, we are not able to merge the changes. Luckily, as our team is small, we just do not edit the same file at the same time which does not cause a great trouble in the project.

What we did right
After talking about the mistakes, I will talk about some decisions that I think is made correctly.

First, during the production of Monster Bowling, there are constant communication within the team. We talked about the progress of the game every 1 or 2 weeks. This is very important for those who make games in their free time because through talking about the game, we can keep the passion and let other team member know what are going on in the project.

Second, the decision of making editors and Mac version of the game is important. This enable artist to build and test the game level without any programmer interaction. Although the editors are not user friendly, the artist would suggested to add the minimal set of features (e.g. adding zoom extend to objects in the 3D viewport) that he can live with so that he can work in a much faster way. Explicitly saying what features are lacking will help the programmer to improve the tools.

Level editor used to build the game

Third, embedding a scripting language to the game engine is useful. Writing game play code in Lua is much faster than using C++. Also modifying the script file is much faster than compiling C++ code which can have a faster iteration time. Also scripting language can draw a clear separation between engine code and game play code. Thanks to Lua, when migrating from the ship project to Monster Bowling, there does not have much to change in the engine code.

Test level of Monster Bowling which built using Lua

Fourth, as the engine is written from scratch starting from memory management, rendering code, animation. I still use some open source library: Bullet physics library, Lua and SOIL (for decompressing PNG texture). I use them because my goal is to learn how an engine should be architected to interact with different modules. Also I am not strong at physics and scripting, writing my own physics library and scripting language will take a long time and the code would not be as fast as Bullet and Lua. So I choose to use some open source library which have source code so that it is easier to debug.

Conclusion
This iPhone game engine project took a total of 1 year and 3 months of spare time to complete and produced 1 game. As there is only 1 programmer, Some open source library are used and I decided to sacrifice my favorite graphics programming(the engine doesn't perform lighting and using texture color only) to keep the work load low. I think that it is ridiculous to write an engine without making any game, so I worked on Monster Bowling using this engine, but there are some effort is wasted (i.e. world level streaming) when migrating from the ship project. So if someone just want to focus on making games only, I would suggest they license a commercial engine such as Unity or UDK rather than writing their own engine which will cost a large amount of time. But for me, writing my own engine is to learn and most important is for fun.