穿梭於 UTF-8 與 UTF-16 之間

偶然於 7zip 的 LZMA sdk 裡發現非常簡潔的 UTF-8/UTF-16 變換函數，連一般轉換成 Unicode 的中介動作也省去了。可惜它本身的解壓功能未能滿足遊戲裝載系統的要求，皆因 7zip 的 archive 格式不能以最少的資源去解壓 archive 裡的個別檔案。
以下源始碼引用 LZMA sdk 再加上本人所寫的額外錯誤偵測與註解，enjoy!

typedef byte_t unsigned char;

// Reference: http://en.wikipedia.org/wiki/Utf8
static const byte_t cUtf8Limits[] = {
 0xC0, // Start of a 2-byte sequence
 0xE0, // Start of a 3-byte sequence
 0xF0, // Start of a 4-byte sequence
 0xF8, // Start of a 5-byte sequence
 0xFC, // Start of a 6-byte sequence
 0xFE // Invalid: not defined by original UTF-8 specification
};

/*! Usually it is a 2 steps process to convert the string, invoke utf8ToUtf16() with
 dest equals to null so that it gives you destLen (not including null terminator),
 then allocate the destination with that amount of memory and call utf8ToUtf16() once
 again to perform the actual conversion. You can skip the first call if you sure
 the destination buffer is large enough to store the data.

 \note Here we assum sizeof(wchar_t) == 2
 \ref Modify from 7zip LZMA sdk
 */
bool utf8ToUtf16(wchar_t* dest, size_t& destLen, const char* src, size_t maxSrcLen)
{
 size_t destPos = 0, srcPos = 0;

 while(true)
 {
  byte_t c; // Note that byte_t should be unsigned
  size_t numAdds;

  if(srcPos == maxSrcLen || src[srcPos] == '\0') {
   if(dest && destLen != destPos) {
    assert(false && "The provided destLen should equals to what we calculated here");
    return false;
   }

   destLen = destPos;
   return true;
  }

  c = src[srcPos++];

  if(c < 0x80) { // 0-127, US-ASCII (single byte)
   if(dest)
    dest[destPos] = (wchar_t)c;
   ++destPos;
   continue;
  }

  if(c < 0xC0) // The first octet for each code point should within 0-191
   break;

  for(numAdds = 1; numAdds < 5; ++numAdds)
   if(c < cUtf8Limits[numAdds])
    break;
  uint32_t value = c - cUtf8Limits[numAdds - 1];

  do {
   byte_t c2;
   if(srcPos == maxSrcLen || src[srcPos] == '\0')
    break;
   c2 = src[srcPos++];
   if(c2 < 0x80 || c2 >= 0xC0)
    break;
   value <<= 6;
   value |= (c2 - 0x80);
  } while(--numAdds != 0);

  if(value < 0x10000) {
   if(dest)
    dest[destPos] = (wchar_t)value;
   ++destPos;
  }
  else {
   value -= 0x10000;
   if(value >= 0x100000)
    break;
   if(dest) {
    dest[destPos + 0] = (wchar_t)(0xD800 + (value >> 10));
    dest[destPos + 1] = (wchar_t)(0xDC00 + (value & 0x3FF));
   }
   destPos += 2;
  }
 }

 destLen = destPos;
 return false;
}

bool utf8ToWStr(const char* utf8Str, size_t maxCount, std::wstring& wideStr)
{
 size_t destLen = 0;

 // Get the length of the wide string
 if(!utf8ToUtf16(nullptr, destLen, utf8Str, maxCount))
  return false;

 wideStr.resize(destLen);
 if(wideStr.size() != destLen)
  return false;

 return utf8ToUtf16(const_cast<wchar_t*>(wideStr.c_str()), destLen, utf8Str, maxCount);
}

bool utf8ToWStr(const std::string& utf8Str, std::wstring& wideStr)
{
 return utf8ToWStr(utf8Str.c_str(), utf8Str.size(), wideStr);
}

//! See the documentation for utf8ToUtf16()
bool utf16ToUtf8(char* dest, size_t& destLen, const wchar_t* src, size_t maxSrcLen)
{
 size_t destPos = 0, srcPos = 0;

 while(true)
 {
  uint32_t value;
  size_t numAdds;

  if(srcPos == maxSrcLen || src[srcPos] == L'\0') {
   if(dest && destLen != destPos) {
    assert(false && "The provided destLen should equals to what we calculated here");
    return false;
   }
   destLen = destPos;
   return true;
  }

  value = src[srcPos++];

  if(value < 0x80) { // 0-127, US-ASCII (single byte)
   if(dest)
    dest[destPos] = char(value);
   ++destPos;
   continue;
  }

  if(value >= 0xD800 && value < 0xE000) {
   if(value >= 0xDC00 || srcPos == maxSrcLen)
    break;
   uint32_t c2 = src[srcPos++];
   if(c2 < 0xDC00 || c2 >= 0xE000)
    break;
   value = ((value - 0xD800) << 10) | (c2 - 0xDC00);
  }

  for(numAdds = 1; numAdds < 5; ++numAdds)
   if(value < (uint32_t(1) << (numAdds * 5 + 6)))
    break;

  if(dest)
   dest[destPos] = char(cUtf8Limits[numAdds - 1] + (value >> (6 * numAdds)));
  ++destPos;

  do {
   --numAdds;
   if(dest)
    dest[destPos] = char(0x80 + ((value >> (6 * numAdds)) & 0x3F));
   ++destPos;
  } while(numAdds != 0);
 }

 destLen = destPos;
 return false;
}

bool wStrToUtf8(const wchar_t* wideStr, size_t maxCount, std::string& utf8Str)
{
 size_t destLen = 0;

 // Get the length of the utf-8 string
 if(!utf16ToUtf8(nullptr, destLen, wideStr, maxCount))
  return false;

 utf8Str.resize(destLen);
 if(utf8Str.size() != destLen)
  return false;

 return utf16ToUtf8(const_cast<char*>(utf8Str.c_str()), destLen, wideStr, maxCount);
}

bool wStrToUtf8(const std::wstring& wideStr, std::string& utf8Str)
{
 return wStrToUtf8(wideStr.c_str(), wideStr.size(), utf8Str);
}

編程花招的謎思

微軟快要推出下一代 Visual Studio 2010，它對於 C++0x 的支持最令我期待。
儘管 C++0x compiler 還未成熟與普及，已有工程師把弄新的語法，創造耀眼花招。
其實我也非常喜歡耍玩語法上的把戲，但我亦知道它會帶來什麼災害。
以下文字引述自花招裡的一篇回覆，也是我心裡想說的：

Interesting acrobatics, but I am a KISS fan.

I prefer not to mandate a C++ black belt (with several Dans on occassion) on coworkers who try to understand and modify my code, so thanks but I'll pass.

Is there anything in the above code that cannot be done in plain C in a way that 90% of the dev population can understand and 80% can modify/extend without a mistake?

Why do architects feel so compelled to save the world by providing infrastructure and plumbing for everything conceivable under the sun?

What about memoization? If I am in such a corner case where caching the results of a function call will *actually* improve performance, what makes you think I would opt for an obscure and totally incomprehensible generic template that I cannot understand or debug, rather than a custom-tailored, totally non-reusable, top-performing, totally understandable and debugable solution?

Don't get me wrong, I am not an anti-STL, do-it-yourself (CMyHashTable, CMyDynamicArray, CMyOS) gangho. I am just a KISS fan (including the rock band). If something can be done in a way that is simpler, easier to understand, debug and extend, then I prefer the simpler way.

I just get so frustrated when people do all this acrobatic stuff in production code just because (a) they can do it (b) it's cool to do it, without thinking back a lil'bit or actually having mastered the 'tools' they are using.

A similar example is 'patternitis'. I have seen countless C++ freshmen reading the GangOf4 Design Patterns book and then creating a total mess in everything, like deciding to implement the Visitor pattern on a problem that required Composite and ended up coding a third pattern alltogether from the same book, still naming the classes CVisitorXYZ (probably they opened the book on the wrong page at some point).

I have met exactly 1 guy (I called him the "Professor") who knew C++ well enough and had the knowledge to apply the patterns where they ought to be applied. His code was a masterpiece, it worked like a breeze, but when he left, none else in the house could figure things out.

So what's the point with these Lambda stuff really? Increase the expression of the language? Are we doing poetry or software? Why should we turn simple code that everyone understands into more and more elegant and concise code that only few can understand and make it work?

I have been coding in C (drivers) and C++ for 15 years and not once was I trapped because I was missing lambda expressions or similar syntactic gizmos.

So what's the point really? Please enlighten me. I don't say that *I* am right and *YOU* are wrong. I am saying that I don't see, I don't understand the positive value that these things bring in that far outweighs the problems they cause by complicating the language.

當然，流行/藝術派與實際派的存在都是有意義的；否則編程世界不是一團糟就是停滯不前。

沒有惡意的 Bonjour

無意中在視窗服務裏面發現多了一個服務項，進程為 mDNSResponder.exe。發現時就感覺不妙，還以為是木馬。

原來它不是病毒或惡意程式，一個名為 Bonjour 的服務，是 Apple 公司的產品。一般會在安裝 Adobe CS3 後出現；用於自動發現局域網上的印表機或其他設備，一般沒什麼用處，卸載後也不影響其他軟體的使用，下面是 Adobe 網站上公佈的卸載方法：

1. 運行 C:\Program Files\Bonjour\mDNSResponder.exe -remove
2. 重命名 C:\Program Files\Bonjour\mdnsNSP.dll 為 mdnsNSP.old
3. 重啟電腦
4. 刪除 C:\Program Files\Bonjour 目錄

[註] Bonjour 在法語中解作 "你好"。

陰影映射

完成了紋理投影後，製作基本陰影映射就如吃生菜一樣容易。

// Pixel shader

varying vec3 normal, lightDir, halfVector;
varying vec2 colorCoord;
varying vec4 shadowCoord;
uniform sampler2D colorTex;
uniform sampler2DShadow shadowTex;

// Light intensity inside shadow
const float shadowIntensity = 0.5;

// Should be supplied as uniform
const float shadowMapPixelScale = 1.0 / float(2048);
const int pcfSize = 1; // The pcf filtering size, 0 -> 1x1 (no filtering), 1 -> 3x3 etc

void main(void)
{
 vec4 diffuse = gl_FrontLightProduct[0].diffuse;
 vec4 specular = gl_FrontLightProduct[0].specular;
 vec4 ambient = gl_FrontLightProduct[0].ambient;
 vec3 n = normalize(normal);
 float NdotL = max(dot(n, lightDir), 0.0);

 diffuse *= NdotL;
 vec3 halfV = normalize(halfVector);
 float NdotHV = max(dot(n, halfV), 0.0);
 specular *= pow(NdotHV, gl_FrontMaterial.shininess);

 // Get the shadow value, let the hardware perform perspective divide,
 // depth comparison and 2x2 pcf if supported.
 // float shadowValue = shadow2DProj(shadowTex, shadowCoord).r;

 // Perform PCF filtering
 float shadowValue = 0.0;
 for(int i=-pcfSize; i<=pcfSize; ++i) for(int j=-pcfSize; j<=pcfSize; ++j)
 {
  vec4 offset = vec4(i * shadowMapPixelScale, j * shadowMapPixelScale, 0, 0);
  shadowValue += shadow2DProj(shadowTex, shadowCoord + offset).r;
 }
 shadowValue /= (2 * pcfSize + 1) * (2 * pcfSize + 1);

 float shadowSpecularFactor = shadowValue == 0 ? 0 : 1;
 float shadowDiffuseFactor = min(1.0, shadowIntensity + shadowValue);

 gl_FragData[0] = shadowSpecularFactor * specular +
 (ambient + shadowDiffuseFactor * diffuse) * vec4(texture2D(colorTex, colorCoord).xyz, 1); 
}

當然，還有許多的陰影技術可以嘗試；我比較臨感興趣的有：

• Exponential Shadow Map
• Variance Shadow Map
• Trapezoidal Shadow Maps
• Parallel-Split Shadow Maps
  

---

相關文章

• Code Sampler - Shadow mapping
  
• Paul's Project - Shadow mapping
• GDC08 Advanced Soft Shadow Mapping Techniques
  

紋理投影

為了製作陰影映射 (Shadow mapping)，先來一個紋理投影 (Projective texture)。




製作紋理投影的關鍵是紋理投影矩陣，是它把物體的世界座標轉換成投影空間的紋理座標；以下是 OpenGL fixed pipeline 的實作：

// The following code assums you have already applied the camera's view matrix
// to the model-view matrix stack
setupViewMatrix();

// Use another texture unit to avoid conflit with the color texture of the model
glActiveTexture(GL_TEXTURE1);

// You can choose between GL_MODULATE and GL_ADD
glTexEnvi(GL_TEXTURE_ENV, GL_TEXTURE_ENV_MODE, GL_ADD);

// Matrix44 is just a simple matrix 4x4 class, but remember opengl use column major layout
// The bias matrix is to map from clip space [-1, 1] to texture space [0, 1]
Matrix44 biasMatrix = Matrix44(
 0.5f, 0, 0, 0.5f,
 0, 0.5f, 0, 0.5f,
 0, 0, 0.5f, 0.5f,
 0, 0, 0,    1.0f);

Matrix44 projectorProjection, projectorView;

// Setup projectorProjection and projectorView according to
// how you want the texture to be projected on the scene
// ...

Matrix44 textureMatrix = biasMatrix * projectorProjection * projectorView;

// Preform a transpose so that we get the rows of the matrix rather than columns
textureMatrix = textureMatrix.transpose();

// A post-multiply by the inverse of the CURRENT modelview matrix is applied
// by opengl automatically to the eye plane equations we provide.
// Therefor, it is important to enable these texture coordinate generation
// before appling any model-world matrix transform
glTexGenfv(GL_S, GL_EYE_PLANE, textureMatrix[0]); // Row 0
glTexGenfv(GL_T, GL_EYE_PLANE, textureMatrix[1]); // Row 1
glTexGenfv(GL_R, GL_EYE_PLANE, textureMatrix[2]); // Row 2
glTexGenfv(GL_Q, GL_EYE_PLANE, textureMatrix[3]); // Row 3

glTexGeni(GL_S, GL_TEXTURE_GEN_MODE, GL_EYE_LINEAR);
glTexGeni(GL_T, GL_TEXTURE_GEN_MODE, GL_EYE_LINEAR);
glTexGeni(GL_R, GL_TEXTURE_GEN_MODE, GL_EYE_LINEAR);
glTexGeni(GL_Q, GL_TEXTURE_GEN_MODE, GL_EYE_LINEAR);

// Enable automatic texture coordinate generation
// Note that the R and Q component may not be used in simple projective texture
// but they are needed for shadow mapping
glEnable(GL_TEXTURE_GEN_S);
glEnable(GL_TEXTURE_GEN_T);
glEnable(GL_TEXTURE_GEN_R);
glEnable(GL_TEXTURE_GEN_Q);

// Bind the projector's texture
glBindTexture(GL_TEXTURE_2D, textureHandle);

// You may move the clamp setting to where you initialize the texture
// rather than setting up every frame
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_CLAMP);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_T, GL_CLAMP);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_R, GL_CLAMP);

// Set the active texture back to the model's color texture
glActiveTexture(GL_TEXTURE0);

// For each model:
//  Apply any world transform for your model
//  Draw the model
// End

當我試圖把上述的編碼轉移到 glsl，我遇到了一個沒有多被紋理投影項目中詳述的問題，那就是如何在 glsl 裡得到物體的世界座標。這個問題沒有在 fixed pipeline 中出現是因為早於應用物體 - 世界矩陣 (Model-world matrix) 之前，那紋理投影矩陣已計算恰當。縱然 glsl (其實是整個 OpenGL) 沒有單獨的物體 - 世界矩陣可供查詢，我們可以把攝像機的視圖逆矩陣乘以 gl_ModelViewMatrix 求出物體 - 世界矩陣。

glActiveTexture(GL_TEXTURE1);

Matrix44 biasMatrix = Matrix44(
 0.5f, 0, 0, 0.5f,
 0, 0.5f, 0, 0.5f,
 0, 0, 0.5f, 0.5f,
 0, 0, 0,    1.0f);

// We need the camera's view matrix inverse in order to obtain the model-world
// transform in glsl
Matrix44 projectorProjection, projectorView, cameraView;

// Setup projectorProjection, projectorView and cameraView
// ...

Matrix44 textureMatrix =
biasMatrix * projectorProjection * projectorView * cameraView.inverse();

// Set up the texture matrix
glMatrixMode(GL_TEXTURE);
glLoadMatrixf(textureMatrix.getPtr());
glMatrixMode(GL_MODELVIEW);

glBindTexture(GL_TEXTURE_2D, textureHandle);

glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_CLAMP);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_T, GL_CLAMP);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_R, GL_CLAMP);

glActiveTexture(GL_TEXTURE0);

// For each model:
//  Apply any world transform for your model
//  Draw the model
// End


// Vertex shader:
varying vec3 normal, lightDir, halfVector;
varying vec2 colorCoord;
varying vec4 projectiveCoord;

void main(void)
{
 gl_Position = ftransform();
 normal = gl_NormalMatrix * gl_Normal;
 lightDir = normalize(gl_LightSource[0].position.xyz);
 halfVector = normalize(gl_LightSource[0].halfVector.xyz);

 colorCoord = gl_MultiTexCoord0.xy;

 // gl_TextureMatrix[1] should contains the inverse of the view matrix,
 // resulting a model matrix when combining with gl_ModelViewMatrix
 projectiveCoord = gl_TextureMatrix[1] * gl_ModelViewMatrix * gl_Vertex;
}

// Pixel shader:
varying vec3 normal, lightDir, halfVector;
varying vec2 colorCoord;
varying vec4 projectiveCoord;
uniform sampler2D colorTex;
uniform sampler2D projectiveTex;

void main(void)
{
 vec4 diffuse = gl_FrontLightProduct[0].diffuse;
 vec4 specular = gl_FrontLightProduct[0].specular;
 vec4 ambient = gl_FrontLightProduct[0].ambient;
 vec3 n = normalize(normal);
 float NdotL = max(dot(n, lightDir), 0.0);

 diffuse *= NdotL;
 vec3 halfV = normalize(halfVector);
 float NdotHV = max(dot(n, halfV), 0.0);
 specular *= pow(NdotHV, gl_FrontMaterial.shininess);

 gl_FragData[0] = specular + (ambient + diffuse) * vec4(texture2D(colorTex, colorCoord).xyz, 1);

 // Apply the projective texture
 gl_FragData[0] += texture2DProj(projectiveTex, projectiveCoord);
}

免費 Model 寶庫

今天無意中發現了一個博客非常慷慨地把大量高品質 (相對其他免費) 的 3D 模型分享給全世界。
站內有不同種類的模型，但還是汽車的居多；雖然下載的方法有點煩，畢竟是免費的，好應該說聲多謝。

http://i344.photobucket.com/albums/p338/free3dart/nsx_HP_small.jpg

http://i344.photobucket.com/albums/p338/free3dart/f18.jpg

SSAO 新進展

Yeah! 利用了法線緩衝所提供的資訊後， SSAO (屏幕空間環境光遮蔽) 的效果迫真了許多。
開始感受到電腦繪圖算法的迷人之處，可惜再沒有人和我分享這份喜悅。




讓我嘗試簡單地解釋它的原理吧。
螢幕中的每一像素都會和它周圍的 N 個像素作比較，比較時有兩個因數需要考慮

1. 兩像素於三圍空間中的位置；深度較淺的像素會遮蔽較深的像素，而遮蔽的程度就取決於距離。
   
   
2. 兩像素的法線內積 (Dot product)；面向面的像素會比面向同一方向的像素較接觸不到外來的光線。
   

至於怎樣對周圍的 N 個像素取樣，就是整個算法中最令人頭痛的問題。當然取樣越多效果越理想，但實際經驗告訴大家 N 只可以不大於 32 左右。隨著取樣的數量受限，而又希望有比較廣闊的取樣範圍 (位置較遙遠的像素都可互相影響)，可用一些隨機取樣模式；不過暫時我只用了一個十字形的取樣模式，只要取樣範圍不太大是可以接受的。

uniform sampler2DRect texColor; // Color texture
uniform sampler2DRect texDepth; // Depth texture
uniform sampler2DRect texNormal;// Normal texture
uniform vec2 camerarange = vec2(1.0, 500);

varying vec2 texCoord;
const float aoCap = 1.0;
float aoMultiplier = 1000.0;

float pw = 1.0;  // Use (1.0 / screensize.x) for GL_TEXTURE2D
float ph = 1.0;

float readDepth(in vec2 coord)
{
 float nearZ = camerarange.x;
 float farZ = camerarange.y;
 float posZ = texture2DRect(texDepth, coord).x;

 return (2.0 * nearZ) / (nearZ + farZ - posZ * (farZ - nearZ));
}

vec3 readNormal(in vec2 coord)
{
 return normalize(2 * (texture2DRect(texNormal, coord).xyz - 1));
}

float compareDepths(in float depth1, in float depth2)
{
 float depthDiff = depth1 - depth2;
 const float aorange = 10.0;  // Units in space the AO effect extends to (this gets divided by the camera far range)
 float diff = clamp(1.0 - depthDiff * (camerarange.y - camerarange.x) / aorange, 0.0, 1.0);
 return min(aoCap, max(0.0, depthDiff) * aoMultiplier) * diff;
}

float calAO(float depth, vec3 normal, float dw, float dh)
{
 vec2 coord = vec2(texCoord.x + dw, texCoord.y + dh);
 float angleFactor = 1 - dot(normal, readNormal(coord));

 if(length(normal) == 0)
 angleFactor = 0;

 return angleFactor * compareDepths(depth, readDepth(coord));
}

void main(void)
{
 float depth = readDepth(texCoord);
 float ao = 0.0;

 vec3 normal = readNormal(texCoord);

 for(int i=0; i<8; ++i) {
  ao += calAO(depth, normal, pw, ph);
  ao += calAO(depth, normal, pw, -ph);
  ao += calAO(depth, normal, -pw, ph);
  ao += calAO(depth, normal, -pw, -ph);

  pw *= 1.4;
  ph *= 1.4;
  aoMultiplier /= 1.5;
 }

 ao *= 2.0;

 gl_FragColor = vec4(1.0 - ao) * texture2DRect(texColor, texCoord);
}

---

相關文章

• 初嚐 Shader 編程
• Starcraft 2 - Effects & Techniques
• iñigo quilez
• Discussion on opengl.org
• Discussion on gamedev.net