還是簡單些好

Visual Studio 插件推介–metalscroll

2010-12-29T16:24:00.001+08:00

早前我曾經介紹過 RockScroll 這個插件，如今我找到了一個更好的代替品 metalscroll

它比起 RockScroll 有很多細節的改善，最重要是掛掉的情況沒有了。

讓工作管理員進行繪圖

2010-02-24T12:11:00.001+08:00

興之所致，找來一個有趣面試題目來解答：如何能讓CPU 的使用率表現為一條正弦曲線？

這個題目來自《编程之美--微软技术面试心得》，有機會的我會話買下來當作娛樂。

// This program try to burn cpu cycles with a sinusoid function against the time.
#include <MCD/Core/System/TaskPool.h>
#include <MCD/Core/System/Timer.h>
#include <math.h>

class Task : public MCD::TaskPool::Task {
public:
  Task(float frequency) : MCD::TaskPool::Task(0), mFrequency(frequency) {}

  sal_override void run(MCD::Thread& thread) throw() {
    MCD::Timer timer;
    while(thread.keepRun()) {
      double current = timer.get().asSecond();
      double busy = (sin(current * mFrequency) + 1) / 2;
      double idle = 1 - busy;  // We base on a 1 second interval
      while(timer.get().asSecond() < current + busy) {}  // Burn CPU cycles
      MCD::mSleep(int(idle * 1000));  // Let CPU idle
    }

    // The Task instance is not needed any more, destroy it.
    delete this;
  }

  float mFrequency;
};  // Task

int main(int, char const*[])
{
  const size_t cpuCount = 4;  // Set this to match your hardware thread count
  const float frequency = 0.1f;

  MCD::TaskPool taskPool;
  taskPool.setThreadCount(cpuCount);

  for(size_t i=0; i<cpuCount; ++i)
    taskPool.enqueue(*new Task(frequency));

  std::cout << "Press enter to quit...\n";
  std::cin.get();

  taskPool.stop();

  return 0;
}

註：中間的那個高峰因突如其來的 MSN 短訊耗掉了整整一個 CPU Core 而缺了一角。

Virtual box shared folders 備忘

2009-12-15T23:41:00.001+08:00

Virtual box 3.1 已支援 OpenGl 2.1，MCore 的 Linux port 也可繼續。

已往我使用 smbfs 來 mount Windows 的網絡磁碟機：

//192.168.0.1/mcore3d /home/ricky/mcore3d smbfs iocharset=utf8,unicode,username=xxx,password=xxx 0 0

不過很容易會有權限或 encoding 的問題，而某個 library 更新之後又會有機會使原有設定失效。

比較之下，Virtual box 提供的 shared folders 就可靠得多：

mcore3d /home/ricky/mcore3d vboxsf defaults 0 0

為灰鼠捉蟲

2009-12-02T12:07:00.001+08:00

使用了 Squirrel 已好一些日子，終於給我遇到了臭蟲。這臭蟲的表徵是不確定的行為，debug/release/，run-with/without debugger 都會產生不同的結果。這一類不確定的行為不是多緒就是錯誤記憶體存取做成，而面對著陌生的 code base，最好的捉蟲方法就是使用專門的工具，如 Intel Parallel Studio 提供的 Parallel Inspector。

最終找到錯誤源於一處被 reference 的記憶體給 realloc 了；餘下的就交給 Squirrel 作者處理。

Squirrel remote debugger

2009-10-21T18:31:00.001+08:00

以下是完成了大約三分之一的 Squirrel 遠程除錯器。當中的製作過程比想像中簡單，皆因 Squirrel 已有一個除錯伺服器的實作 sqdbg，而我需要做的只是客戶端與 Gui。

Sqdbg 的編程界面僅有四個函數，使用 Xml 來進行客戶端溝通。如今加減中斷點，下一行，跳出跳入和暫停繼續等等已經完成，接下來還有堆疊，變量監視等工夫。

除了結合自家的遊戲引擎，它也會獨立出來貢獻給 Squirrel 社群。

In-Game C++ Memory Profiler

2009-09-17T09:59:00.004+08:00

忙碌了兩個多月，這篇有可出現在 Gems 系列的 "In-Game Memory Profiler" 終於完成。製作這類 Profiler 已經不知多少次了，但這次是最滿意的；可以媲美需付款的產品 (其實類似的 C++ memory profiler 產品真的少之又少)，甚至更好。就是它，讓我知道 Bullet 每次 step simulation 都有好幾千個即用即棄的 memory allocation/de-allocation；後來我把它的 default pool size 增大，問題也就解決了。

弱指針的重要性

2009-09-05T14:32:00.000+08:00

雖然有許多有關智能指針 (Smart pointer) 的文章和範例，但關於弱指針的就相對寥寥無幾。縱然有所提及，也只是草草幾筆說弱指針是用來避免 "循環引用 (Cyclic reference)" 云云。就此問題我嘗試用一些例子去補充說明弱指針何時用，為什麼用。

首先讓我們看一個遊戲引擎中典型的資料管理系統例子：

因為要節省內存的需求，Texture (紋理) 被設計成能夠給多個 Model (三維模型) 共享。而 Texture 的存在目的，就是留給 Model 作為繪畫時使用；明顯地，Model 可用 Smart Pointer 來引用 Texture；相對地 NameToTextureMap (方便用名稱來作資料搜尋) 該使用甚麼來引用 Texture 就沒有那麼明顯了。先看看使用不同的指針會有什麼的後果吧。

裸指針 - 這將會是災難性的選擇，因為一旦再沒有 Model 引用 Texture， NameToTextureMap 就會在毫無知會的情況下指向一件非法的物件。
智能指針 - 為了解決裸指針的問題，選擇智能指針像是合理的做法。不過請大家想一想，一旦 NameToTextureMap 引用了 Texture 以後，何時才可刪除引用呢？假如不去刪除引用，Texture 的生命期就會與 NameToTextureMap 同步化，失去了原先使用智能指針作為純粹被 Model 共享的意義。

這時就是讓弱指針發揮的時候。弱指針的特性就是當它指向的物件被銷毀之時，弱指針的值就會瞬間變為零；因此，讓 NameToTextureMap 使用弱指針，再定期把零值的弱指針由容器中刪除，以上的 UML 設計就可忠實地實作出來。

總結來說，智能指針旨不在於提供程序員不加思索就可使用的工具，它是一種能幫助你正確地實行擁有權共享的工具。就算是聲稱擁有自動內存管理的語言如 Java, C#, Python, Ruby 等等都一定會有弱指針這個概念，否則內存洩漏是很難避免的。假若你在開發 C++ 程序的時候遇到許多關於物件擁有權的問題，請記得弱指針的存在。

Syntax highlight in Notepad++

2009-09-03T10:07:00.003+08:00

從互聯網找到個給 Squirrel 語言著色的 Notepad++ config 檔案，也可作為日後 MCore3D Studio 結合 Scintilla Control 的藍圖。把以下的 Xml 儲存為 "userDefineLang.xml" 再放入 Notepad++ 的安置目錄就行了。


<NotepadPlus>
   <UserLang name="Squirrel" ext="nut">
       <Settings>
           <Global caseIgnored="no" />
           <TreatAsSymbol comment="yes" commentLine="yes" />
           <Prefix words1="no" words2="no" words3="no" words4="no" />
       </Settings>
       <KeywordLists>
           <Keywords name="Delimiters">&quot;00&quot;00</Keywords>
           <Keywords name="Folder+"></Keywords>
           <Keywords name="Folder-"></Keywords>
           <Keywords name="Operators">- ! ( ) , . : ; ? [ ] { } + &lt; = &gt;</Keywords>
           <Keywords name="Comment">1/* 2*/ 0//</Keywords>
           <Keywords name="Words1">break case catch class clone continue const default delegate delete else enum extends for function if in null resume return switch this throw try typeof parent yield constructor instanceof true false static do while foreach</Keywords>
           <Keywords name="Words2">local</Keywords>
           <Keywords name="Words3">ARGS</Keywords>
           <Keywords name="Words4"></Keywords>
       </KeywordLists>
       <Styles>
           <WordsStyle name="DEFAULT" styleID="11" fgColor="000000" bgColor="FFFFFF" fontName="" fontStyle="0" />
           <WordsStyle name="FOLDEROPEN" styleID="12" fgColor="000000" bgColor="FFFFFF" fontName="" fontStyle="0" />
           <WordsStyle name="FOLDERCLOSE" styleID="13" fgColor="000000" bgColor="FFFFFF" fontName="" fontStyle="0" />
           <WordsStyle name="KEYWORD1" styleID="5" fgColor="0000FF" bgColor="FFFFFF" fontName="" fontStyle="1" />
           <WordsStyle name="KEYWORD2" styleID="6" fgColor="006262" bgColor="FFFFFF" fontName="" fontStyle="1" />
           <WordsStyle name="KEYWORD3" styleID="7" fgColor="007777" bgColor="FFFFFF" fontName="" fontStyle="3" />
           <WordsStyle name="KEYWORD4" styleID="8" fgColor="000000" bgColor="FFFFFF" fontName="" fontStyle="0" />
           <WordsStyle name="COMMENT" styleID="1" fgColor="008000" bgColor="FFFFFF" fontName="" fontStyle="2" />
           <WordsStyle name="COMMENT LINE" styleID="2" fgColor="008000" bgColor="FFFFFF" fontName="" fontStyle="2" />
           <WordsStyle name="NUMBER" styleID="4" fgColor="FF8000" bgColor="FFFFFF" fontName="" fontStyle="0" />
           <WordsStyle name="OPERATOR" styleID="10" fgColor="000080" bgColor="FFFFFF" fontName="" fontStyle="1" />
           <WordsStyle name="DELIMINER1" styleID="14" fgColor="7E7E7E" bgColor="FFFFFF" fontName="" fontStyle="2" />
           <WordsStyle name="DELIMINER2" styleID="15" fgColor="000000" bgColor="FFFFFF" fontName="" fontStyle="0" />
           <WordsStyle name="DELIMINER3" styleID="16" fgColor="000000" bgColor="FFFFFF" fontName="" fontStyle="0" />
       </Styles>
   </UserLang>
</NotepadPlus>

Mesa 3D

2009-08-29T23:19:00.001+08:00

多年沒有注視的 Mesa 3D 原來已經支援 OpenGL 2.1，亦表示它包含了 Glsl 的編輯器與運行期軟件。但更令我感到驚喜的是它的驅動層是可以使用 Direct3D9 作為實作。這個實作應該是基於 GlDirect 為藍圖，把一個個 OpenGL 指令變換成 Direct3D 的函數。
理想地，我不必再為不同平台間的 Graphics API 而煩惱；因為 OpenGL 本身就是設計成可擴充的，而 Mesa3D 又提供了一個很好的起步點。我的引擎只要沿用 OpenGL，再對 Mesa3D 的驅動層稍為修改就應該可在 XBox 上跑。
這兩天會花點時間對這想法的實際可行性多作研究。

Restrict 指針

2009-08-05T14:36:00.014+08:00

一般時候我們的編譯器都不知道兩個指針所指的位置是否相同或者有所重疊，大大降低了它的優化效果。就拿 Matrix3 * Vector3 為例：


void Matrix::MulVector(const Vec3& v, Vec3& result) {
 result.x = m00 * v.x + m01 * v.y + m02 * v.z;
 result.y = m10 * v.x + m11 * v.y + m12 * v.z;
 result.z = m20 * v.x + m21 * v.y + m22 * v.z;
}

很簡單的三行代碼，然而它隱藏了一個效能上的問題。堂 result 被賦予了新的值後，編譯器認為 v 的值也可能被更改了 (v 和 result 也是 reference，pointer 的一類)。因此原本可以留在 register 裡的 v.x, v.y 和 v.z 被迫從新由記憶體裡閱讀回來。看看VC2008 編譯成的機器碼吧：


result.x = m00 * v.x + m01 * v.y + m02 * v.z;
mov         eax,dword ptr [esp+4]
movss       xmm0,dword ptr [ecx+8]
mulss       xmm0,dword ptr [eax+8]
movss       xmm1,dword ptr [ecx+4]
mulss       xmm1,dword ptr [eax+4]
mov         edx,dword ptr [esp+8]
addss       xmm0,xmm1
movss       xmm1,dword ptr [eax]
mulss       xmm1,dword ptr [ecx]
addss       xmm0,xmm1
movss       dword ptr [edx],xmm0

result.y = m10 * v.x + m11 * v.y + m12 * v.z;
movss       xmm0,dword ptr [ecx+0Ch]
mulss       xmm0,dword ptr [eax]
movss       xmm1,dword ptr [ecx+14h]
mulss       xmm1,dword ptr [eax+8]
addss       xmm0,xmm1
movss       xmm1,dword ptr [ecx+10h]
mulss       xmm1,dword ptr [eax+4]
addss       xmm0,xmm1
movss       dword ptr [edx+4],xmm0

result.z = m20 * v.x + m21 * v.y + m22 * v.z;
movss       xmm0,dword ptr [ecx+18h]
mulss       xmm0,dword ptr [eax]
movss       xmm1,dword ptr [ecx+20h]
mulss       xmm1,dword ptr [eax+8]
addss       xmm0,xmm1
movss       xmm1,dword ptr [ecx+1Ch]
mulss       xmm1,dword ptr [eax+4]
addss       xmm0,xmm1
movss       dword ptr [edx+8],xmm0

這時候使用 restrict 就可幫上編譯器把。請注意，VC2008 的 __restrict 只對指針生效：


void Matrix::MulVector(const Vec3& v_, Vec3& result_) {
 const Vec3* __restrict v = &v_;
 Vec3* __restrict ret = &result_;
 result->x = m00 * v->x + m01 * v->y + m02 * v->z;
 result->y = m10 * v->x + m11 * v->y + m12 * v->z;
 result->z = m20 * v->x + m21 * v->y + m22 * v->z;
}

從新編譯後的機器碼：


result->x = m00 * v->x + m01 * v->y + m02 * v->z;
mov         eax,dword ptr [esp+4]
movss       xmm1,dword ptr [eax+4]
movss       xmm0,dword ptr [eax+8]
movss       xmm2,dword ptr [eax]
movss       xmm3,dword ptr [ecx+4]
movss       xmm4,dword ptr [ecx+8]
mov         eax,dword ptr [esp+8]
mulss       xmm3,xmm1
mulss       xmm4,xmm0
addss       xmm3,xmm4
movaps      xmm4,xmm2
mulss       xmm4,dword ptr [ecx]
addss       xmm3,xmm4

result->y = m10 * v->x + m11 * v->y + m12 * v->z;
movss       xmm4,dword ptr [ecx+10h]
movss       dword ptr [eax],xmm3
movss       xmm3,dword ptr [ecx+0Ch]
mulss       xmm3,xmm2
mulss       xmm4,xmm1
addss       xmm3,xmm4
movss       xmm4,dword ptr [ecx+14h]
mulss       xmm4,xmm0
addss       xmm3,xmm4
movss       dword ptr [eax+4],xmm3

result->z = m20 * v->x + m21 * v->y + m22 * v->z;
movss       xmm3,dword ptr [ecx+18h]
mulss       xmm3,xmm2
movss       xmm2,dword ptr [ecx+1Ch]
mulss       xmm2,xmm1
movss       xmm1,dword ptr [ecx+20h]
addss       xmm3,xmm2
mulss       xmm1,xmm0
addss       xmm3,xmm1
movss       dword ptr [eax+8],xmm3

可以看到記憶體閱讀操作減少了。

到最後，其實使用局部變量也可達到類似效果：


void Matrix::MulVector(const Vec3& v, Vec3& result) {
 const float x = v.x;
 const float y = v.y;
 const float z = v.z;

 result.x = m00 * x + m01 * y + m02 * z;
 result.y = m10 * x + m11 * y + m12 * z;
 result.z = m20 * x + m21 * y + m22 * z;
}

引擎開發進度

2009-06-21T11:34:00.006+08:00

有了新成員的加盟，遊戲引擎的開發進程加快，以下是一些測試程式的截圖。

漂亮又便宜的 God Ray
Cube map + Normal mapping
使用 Bullet 製作的 Physics component
場景編輯器

於特定線程設置中斷點

2009-06-17T09:21:00.006+08:00

正在開發一個 memory profiler，為了針對多線程部分的除錯，我須要設置一個只對特定線程生效的中斷點。在 Visual Studio 中，有兩個非常類似的方法可達到目的：

右擊您的 break point 然後使用 break point filter

選擇線程 id
另一個方法是使用 break point condition

不要被 Windows.h 強暴

2009-06-06T08:51:00.007+08:00

引擎的物理部份開始開發，我滿心喜悅地把 Bullet Pyhsics Engine 加入專案，但"咚"的一聲告訴我編譯器掛丟了。誰在作怪呢？當編譯器指向那一向相安無事的數學 max 函數，我就知道是 Bullet include 了 Windows.h。錯就錯在 Bullet 在 btQuickprof.h 哪裡包括了 Windows.h，迫使其他檔案也一併把 Windows.h include 過來，本來潔淨的命名空間就這樣被成千上萬的 macros 如 min, max, CreateWindow, DrawText 等等污染了。
其實 Windows.h 是可以避免在標頭檔中出現的：

盡可能把函數定義由標頭檔移到源碼檔去
大多數基本型別如 DWORD, LARGE_INTEGER 等在標頭檔中可用 unsigned long, __int64 來取代，再在源碼檔用 reinterpret_cast 返回原本的型別。大多數的 struct 指針都可以前置聲明(forward declarate) 如 typedef struct _GUID GUID;
更甚者還會使用 char mMutex[24]; 來取代 CRITICAL_SECTION mMutex; 再加上編譯期 assert 確保兩者內存大小匹配：STATIC_ASSERT(sizeof(mMutex) == sizeof(CRITICAL_SECTION));

把 Windows.h 由標頭檔中抽離以後，不單止命名空間的問題解決了，連編譯的速度都快了哩!

Squirrel 單元測試框架

2009-05-30T17:05:00.010+08:00

暫時還無法找到一個給予 Squirrel 使用的單元測試框架，唯有自己做吧。Lua 的 luaunit 是一個好的起點，不需一天的時間就把它移到 Squirrel，且給它命名為 squnit (下載 / Download)。以下是一些使用範例：


dofile("squnit.nut", true);

class TestToto
{
 a = null;
 s = null;

 function setUp()
 {
  // Set up tests
  a = 1;
  s = "hop";
 }

 function test1_withFailure()
 {
  print("some stuff test 1\n");
  assertEquals(a , 1);
  // Will fail
  assertEquals(a , 2);
  assertEquals(a , 2);
 }

 function test2_withFailure()
 {
  print("some stuff test 2\n");
  assertEquals(a , 1);
  assertEquals(s , "hop");
  // Will fail
  assertEquals(s , "bof");
  assertEquals(s , "bof");
 }

 function test3()
 {
  print("some stuff test 3\n");
  assertEquals(a , 1);
  assertEquals(s , "hop");
  assertEquals(typeof a, "integer");
  assertClose(0.01, -0.01, 0.02);
 }
} // TestToto

class TestTiti
{
 a = null;
 s = null;

 function setUp()
 {
  a = 1;
  s = "hop";
     print("TestTiti.setUp\n");
 }

 function tearDown()
 {
  // Some tearDown() code if necessary
  print("tearDown\n");
 }

 function test1_withFailure()
 {
  print("some stuff test 1\n");
  assertEquals(a , 1);
  // Will fail
  assertEquals(a , 2);
  assertEquals(a , 2);
 }

 function test2_withFailure()
 {
  print("some stuff test 2\n");
  assertEquals(a , 1);
  assertEquals(s , "hop");
  // Will fail
  assertEquals(s , "bof");
 }

 function test3()
 {
  print("some stuff test 3\n");
  assertEquals(a , 1);
  assertEquals(s , "hop");
 }
} // TestTiti

// Simple test functions that were written previously can be integrated in luaunit too
function test1_withFailure()
{
 assert(1 == 1);
 // Will fail
 assert(1 == 2);
}

function test2_withFailure()
{
 assert("a" == "a");
 // Will fail
 assert("a" == "b");
}

function test3()
{
 assert(1 == 1);
 assert("a" == "a");
}

TestFunctions <- wrapFunctions("test1_withFailure", "test2_withFailure", "test3");

// SqUnit().run("test2_withFailure"); // Run only one test function
// SqUnit().run("test1_withFailure");
// SqUnit().run("TestToto"); // Run only on test class
// SqUnit().run("TestTiti:test3"); // Run only one test method of a test class
SqUnit().run(); // Run all tests

還可以使用 squnit 本身來測試自己：


/* testSqunit.nut
 Description: Tests for the squnit testing framework
 Author: Ricky Lung (http://mtlung.blogspot.com/)
 Version: 1.0

 License: X11 License

 This set of files is published under the X11 License. You can do
 more or less anything you want to do with it.

 Permission is hereby granted, free of charge, to any person obtaining a copy
 of this software and associated documentation files (the "Software"), to deal
 in the Software without restriction, including without limitation the rights
 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 copies of the Software, and to permit persons to whom the Software is
 furnished to do so, subject to the following conditions:

 The above copyright notice and this permission notice shall be included in all
 copies or substantial portions of the Software.

 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE X
 CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
 ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/

// This is a bit tricky since the test uses the features that it tests.

dofile("squnit.nut", true);

class TestSqUnit
{
 function mypcall(func, ...)
 {
  local args = array(0);
  for(local i=0; i<vargc; ++i)
   args.push(vargv[i]);

  try {
   func.pacall(args);
   return true;
  } catch(e) {
   return false;
  }
 }

 function testAssertError()
 {
  local has_error = !mypcall(error, null, "coucou");
  assert(has_error == true);
  assertError(error, null, "coucou");
  has_error = !mypcall(assertError, null, error, null, "coucou");
  assert(has_error == false);

  local f = function() {}
  has_error = !mypcall(f, null);
  assert(has_error == false);
  has_error = !mypcall(assertError, null, f, null);
  assert(has_error == true);

  // multiple arguments
  local multif = function(a, b, c) {
   if(a == b && b == c) return;
   error("three arguments not equal");
  }

  assertError(multif, null, 1, 1, 3);
  assertError(multif, null, 1, 3, 1);
  assertError(multif, null, 3, 1, 1);

  has_error = !mypcall(assertError, null, multif, null, 1, 1, 1);
  assert(has_error == true);
 }

 function testAssertEquals()
 {
  assertEquals(1, 1);
  local has_error = !mypcall(assertEquals, 1, 2);
  assert(has_error == true);
 }

 function testAssertClose()
 {
  assertClose(1, 1);
  assertClose(-1, -1);
  assertClose(0.1, -0.1, 0.2);
  local has_error = !mypcall(assertEquals, 0.1, -0.1, 0.19);
  assert(has_error == true);
 }

 function XtestXpcall()
 {
  local f = function() {
   error("[this is a normal error]");
  }
  local g = function(f) {
   f();
  }
  g(f);
 }
} // TestSqUnit

//SqUnit().run("TestSqUnit.testAssertEquals"); // Will execute only one test
//SqUnit().run("TestSqUnit"); // Will execute only one class of test
SqUnit().run(); // Will execute all tests

串列矩陣乘法優化

2009-05-23T13:02:00.002+08:00

埋頭苦幹於 Squirrel 與其捆綁庫已有一個月多，偶爾間找一些好玩的來調劑一下，那就是有關 SIMD 的優化了。先呈上源碼：


// simdMatrixMul.h
#include <xmmintrin.h>

#if USE_ALIGNED
# define _MM_LOAD _mm_load_ps
# define _MM_STORE _mm_store_ps
# define ASSERT_ALIGNED(p) assert(intptr_t(p) % 16 == 0)
#else
# define _MM_LOAD _mm_loadu_ps
# define _MM_STORE _mm_storeu_ps
# define ASSERT_ALIGNED(p)
#endif

/*! SIMD chained matrix multiplication
 Aliasing is allowed for the parameters
 \param result Pointer to 16 floats as the return value
 \param mats An array of pointer that point to a set of 16 floats
 \param count Number of pointer in mats

 Example:
 \code
 Matrix44 m1, m2, m3;
 Matrix44 result;

 // Perform result = m1 * m2 * m3;
 float* mats[] = { (flaot*)(&m1), (float*)(&m2), (float*)(&m3) };
 simdChainedMatrixMul((float*)&result, mats, 3);
 \endcode
*/
void simdChainedMatrixMul(float* result, const float* mats[], size_t count)
{
 assert(count >= 2);
 ASSERT_ALIGNED(result);

 __m128 ret[4];
 __m128 x0, x1, x2, x3;

 // Load the first matrix into ret
 ret[0] = _MM_LOAD(mats[0] + 0*4);
 ret[1] = _MM_LOAD(mats[0] + 1*4);
 ret[2] = _MM_LOAD(mats[0] + 2*4);
 ret[3] = _MM_LOAD(mats[0] + 3*4);

 for(size_t j=1; j<count; ++j) {
  ASSERT_ALIGNED(mats[j]);

  // Prefetch the next matrix, may not usefull at all, test it case by case.
  _mm_prefetch(reinterpret_cast<const char*>(&mats[j+1]), _MM_HINT_NTA);

  __m128 x4 = _MM_LOAD(mats[j] + 0*4);
  __m128 x5 = _MM_LOAD(mats[j] + 1*4);
  __m128 x6 = _MM_LOAD(mats[j] + 2*4);
  __m128 x7 = _MM_LOAD(mats[j] + 3*4);

  for(size_t i=0; i<4; ++i) {
   x1 = x2 = x3 = x0 = ret[i];
   x0 = _mm_shuffle_ps(x0, x0, _MM_SHUFFLE(0,0,0,0));
   x1 = _mm_shuffle_ps(x1, x1, _MM_SHUFFLE(1,1,1,1));
   x2 = _mm_shuffle_ps(x2, x2, _MM_SHUFFLE(2,2,2,2));
   x3 = _mm_shuffle_ps(x3, x3, _MM_SHUFFLE(3,3,3,3));

   x0 = _mm_mul_ps(x0, x4);
   x1 = _mm_mul_ps(x1, x5);
   x2 = _mm_mul_ps(x2, x6);
   x3 = _mm_mul_ps(x3, x7);

   x2 = _mm_add_ps(x2, x0);
   x3 = _mm_add_ps(x3, x1);
   x3 = _mm_add_ps(x3, x2);

   ret[i] = x3;
  }
 }

 _MM_STORE(result + 0*4, ret[0]);
 _MM_STORE(result + 1*4, ret[1]);
 _MM_STORE(result + 2*4, ret[2]);
 _MM_STORE(result + 3*4, ret[3]);
}

這一函數專門計算串列矩陣乘法，非常適合用於 transform traversal 或 skeleton animation 等等。因為所有相乘後的臨時結果都存儲在 SSE 寄存器內，沒有多餘的記憶體移動指令被浪費丟。兩項優化的結果使得 simdChainedMatrixMul 比一般矩陣乘法快三倍，以下是一個 Entity traversal 的測試程式：


#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// Benchmarking options
#define USE_ALIGNED 1
#define USE_SIMD 1

#include "simdChainedMatrixMul.h"

_MM_ALIGN16 class Matrix44
{
public:
 void randomize()
 {
  for(int i=0; i<4; ++i) for(int j=0; j<4; ++j)
   data[i][j] = 0.96f * ((float(rand()) / RAND_MAX) * 2 - 1);
 }

 float* operator[](size_t i) { return data[i]; }
 const float* operator[](size_t i) const { return data[i]; }

 // No aliasing is allowed for the 2 parameters
 void mul(Matrix44* __restrict result, const Matrix44* __restrict rhs)
 {
  assert(result != rhs);
  assert(result != this);

/*  for(size_t i=0; i<4; ++i) for(size_t j=0; j<4; ++j) {
   float sum = 0;
   for(size_t k=0; k<4; ++k)
    sum += data[i][k] * rhs->data[k][j];
   result->data[i][j] = sum;
  }
  return;*/

  result->m00 = m00 * rhs->m00 + m01 * rhs->m10 + m02 * rhs->m20 + m03 * rhs->m30;
  result->m01 = m00 * rhs->m01 + m01 * rhs->m11 + m02 * rhs->m21 + m03 * rhs->m31;
  result->m02 = m00 * rhs->m02 + m01 * rhs->m12 + m02 * rhs->m22 + m03 * rhs->m32;
  result->m03 = m00 * rhs->m03 + m01 * rhs->m13 + m02 * rhs->m23 + m03 * rhs->m33;

  result->m10 = m10 * rhs->m00 + m11 * rhs->m10 + m12 * rhs->m20 + m13 * rhs->m30;
  result->m11 = m10 * rhs->m01 + m11 * rhs->m11 + m12 * rhs->m21 + m13 * rhs->m31;
  result->m12 = m10 * rhs->m02 + m11 * rhs->m12 + m12 * rhs->m22 + m13 * rhs->m32;
  result->m13 = m10 * rhs->m03 + m11 * rhs->m13 + m12 * rhs->m23 + m13 * rhs->m33;

  result->m20 = m20 * rhs->m00 + m21 * rhs->m10 + m22 * rhs->m20 + m23 * rhs->m30;
  result->m21 = m20 * rhs->m01 + m21 * rhs->m11 + m22 * rhs->m21 + m23 * rhs->m31;
  result->m22 = m20 * rhs->m02 + m21 * rhs->m12 + m22 * rhs->m22 + m23 * rhs->m32;
  result->m23 = m20 * rhs->m03 + m21 * rhs->m13 + m22 * rhs->m23 + m23 * rhs->m33;

  result->m30 = m30 * rhs->m00 + m31 * rhs->m10 + m32 * rhs->m20 + m33 * rhs->m30;
  result->m31 = m30 * rhs->m01 + m31 * rhs->m11 + m32 * rhs->m21 + m33 * rhs->m31;
  result->m32 = m30 * rhs->m02 + m31 * rhs->m12 + m32 * rhs->m22 + m33 * rhs->m32;
  result->m33 = m30 * rhs->m03 + m31 * rhs->m13 + m32 * rhs->m23 + m33 * rhs->m33;
 }

 union {
  // Individual elements
  struct { float
   m00, m01, m02, m03,
   m10, m11, m12, m13,
   m20, m21, m22, m23,
   m30, m31, m32, m33;
  };
  // As a 2 dimension array
  float data[4][4];
 };
}; // Matrix44

//! A simple Entity with single list structure.
class Entity
{
public:
#if USE_ALIGNED
 void* operator new(size_t size) { return _aligned_malloc(size, 16); }
 void operator delete(void* p) { _aligned_free(p); }
#endif

 Entity() : parent(NULL), child(NULL)
 {
  ASSERT_ALIGNED(&matrix);
  matrix.randomize();
 }
 ~Entity() { delete child; }

 Entity* addChild(Entity* e)
 {
  assert(e->child == NULL);
  assert(!child);
  if(!child) {
   this->child = e;
   e->parent = this;
  }
  else {
   e->child = child;
   child->parent = e;
   this->child = e;
   e->parent = this;
  }
  return e;
 };

 Matrix44 calculateWorldMatrix1()
 {
  Matrix44 result = matrix;
  Entity* e = this;
  while((e = e->parent) != NULL) {
   Matrix44 tmp(result);
   tmp.mul(&result, &e->matrix);
  }
  return result;
 }

 Matrix44 calculateWorldMatrix2()
 {
  const float* matrixArray[1024] = {0};
  size_t count = 0;
  Entity* e = this;
  do {
   matrixArray[count++] = (float*)(&(e->matrix));
   if(count >= 1024)
    exit(-1);
  } while((e = e->parent) != NULL);

  Matrix44 result;
  simdChainedMatrixMul((float*)(&result), matrixArray, count);

  return result;
 }

 Matrix44 matrix;
 Entity* parent, *child;
// char padding[1024*1024]; // To test the effect of cache miss
};

int main(int argc, char* argv[])
{
 srand(123);
 Entity* root = new Entity();

 Entity* lastChild = root;
 for(size_t i=1000; i--;)
  lastChild = lastChild->addChild(new Entity());

 for(size_t i=0; i<10; ++i) {
  // Print out a summation variable to prevent compiler optimization
  // that turns the whole benchmark into nothing
  float sum = 0;

  clock_t t1 = clock();

  if(!USE_SIMD) for(size_t i=10000; i--;)
   sum += lastChild->calculateWorldMatrix1().m00;
  else for(size_t i=10000; i--;)
   sum += lastChild->calculateWorldMatrix2().m00;

  clock_t t2 = clock();

  printf("%f, dummy:%i\n", float(t2 - t1) / CLOCKS_PER_SEC, sum);
 }

 delete root;
 return 0;
}

明日之星 - 小松鼠 Squirrel

2009-04-26T22:31:00.012+08:00

（圖片來源：treehugger.com）

開始了把腳本語言加入遊戲引擎的工作，心目中的候選語言有 Lua，Python，Ruby，Javascript V8 等等；最後選擇了這一隻小可愛 - Squirrel。小松鼠 Squirrel 由 Alberto Demichelis 所創立，他曾經是知名遊戲引擎公司 Crytek 的 System Architect，Far Cry/CRYEngine 裡的 Lua binding 庫都由他負責。就憑著他對 Lua 的透徹認識和深厚的編程功力，他決定打造一套比 Lua 更優秀的語言。

一向有使用 Lua 的我非常欣賞它的堆疊設計與小巧的機器碼，可惜它的語法對我來說不太自然，甚至未有對類別和標準字元編碼作直接支援。Squirrel 正好解決了這些已困擾我多時的問題，除此之外還加入了類似 C# 的 delegate 和 attribute。以下是 Squirrel 擁有的特色：

動態型別檢查 - Dynamic typing
委托模式 - Delegation
類別與繼承 - Classes & inheritance
類別属性 - Attribute
運算元重載 - Operator overloading
高階函數 - Higher order functions
迭代發生器 - Generators
協程 - Cooperative threads (coroutines)
最佳化遞歸 - Tail recursion
異常 - Exception handling
實時自動內儲管理 - Automatic memory management (CPU bursts free; mixed approach ref counting/GC)
弱引用 - Weak references
C/C++ 風格的語法
可支援 16 bit 字串
支援運行期即時編譯 - Just in time compilation
支援 32 位和 64 位架構
整個運行庫不用七千行源碼，200k byte 的機械碼
遠程調試 - Remote debugging though TCP/IP
與 Visual Studio 的整合

在技術層面來看，Squirrel 絕對適合用作遊戲腳本語言，現在還欠缺的是一群使用者。小弟也希望它能夠茁壯成長，正在為它開發一套模板式的 C++ 結合庫，下次再和大家分享。

簡單地閱讀整個文件

2009-03-31T15:43:00.010+08:00

有時你會想閱讀整個文件，而不是一行行或一個固定大小的緩衝區。這裡有一種方法來完成該工作：


std::ifstream file("myFile", std::ios_base::binary);
if(file) {
 std::ostringstream buffer;
 buffer << file.rdbuf();
 file.close();

 std::string data = buffer.str();
}

就這麼簡單。該文件的內容會複製到 ostringstream 去。
相同的代碼可以用來複製文件，您只需要把 ostringstream 更換成一個 ofstream。
請注意，以上代碼旨在簡潔，未必是高效的實作。

Visual Studio 插件推介 - RockScroll

2009-03-19T09:54:00.004+08:00

這個插件把原本平平無奇的卷軸棒躍身一變成為整個文件的預覽。

還有，當你雙擊選擇一個字，所有出現過的地方將自動突顯出來。

現在就下載 RockScroll 並安裝它！

Accumulative Screen Space Ambient Occlusion

2009-03-06T09:22:00.028+08:00

This is my attempt to combine Real-Time Reprojection Cache and Screen Space Ambient Occlusion. Using such caching scheme, the spatio-temporal coherence nature of the SSAO algorithm can be exploited. You can download the demo with shader source here.

The name "Accumulative SSAO" comes from the fact that the occlusion value is accumulated and averaged over a number of frames. The algorithm itself is quite independent of how the occlusion is calculated and here I will assume the reader is familiar with SSAO implementation such as those from Crysis and Startcraft II.

The pipeline

For every frame,

The scene was rendered using deferred shading technique, producing the color, normal and depth buffers.
A number of random vectors were generated in CPU (where in usual SSAO these vectors only generated once in the program).
The normal and depth buffer are then utilized to calculate the occlusion value in the SSAO pass.
Instead of writing the occlusion value to the final output, it would combine with the previous frame's accumulated occlusion value and then written to a second accumulation buffer.
A blur pass can optionally apply to the most updated accumulated occlusion buffer.
The color buffer was then combined with the occlusion value to product the final result, also the two accumulation buffers were switched with each other.

Re-projection

The re-projection happens in the SSAO pass when it tries to access the previous frame's occlusion value. Having the eye-space 3d position for each pixel, we can transform that into a texture coordinate by using a matrix (and a perspective division afterward), lets call it the delta matrix. This matrix is calculated on CPU as:


bias = translation(0.5, 0.5, 0.5) * scale(0.5, 0.5, 0.5)
deltaMatrix = bias * lastFrameProjection * lastFrameView * currentFrameView.inverse()

In simple words, for each current frame's pixel, we are trying to locate their corresponding pixel coordinate on the last frame. If there is no camera movements, the two coordinates should be the same.

Accumulative AO

With the re-projection working, the current frame's occlusion value can be combined with the previous one with the following accumulation formula:


currentAo = currentAo / 30.0 + lastFrameAo * 29.0 / 30.0;

In order to make something interesting for the above equation, the current occlusion value should not be the same as the previous one. Therefore, a new set of sampling position should be generated for each frame, this can be done by re-generating the random unit sphere samples or the dithering texture every frame. In a loosely sense, it is doing a Monte Carlo Integration over the time domain. To achieve better visual quality, more frames should be taken over the time.

As each frame's AO value will also depends on the last few frames, there will be some time delay for the AO to become up-to-date in a dynamic scene. However, by changing the numerator and denominator in the equation, the trade-off between quality and responsiveness can be adjusted.

Cache-miss consideration

Up to now the cache miss problem of the re-projection is not yet addressed. A cache miss will happen if somewhere in the scene that cannot be seen before becoming visible now, due to camera or object movement. Such a cache miss can be detected by comparing the current pixel's depth value with it's re-projected counterpart. If the two values differed by a certain threshold, a cache miss is detected. And to do this, the last frame's depth value is needed. Instead of using a separated texture to store the last frame's depth value, the depth can be encoded and stored together with the accumulative AO value into a 32-bit texture.


// Encode a float value into 3 bytes
// The input value should be in the range of [0, 1
// Reference: http://www.ozone3d.net/blogs/lab/?p=113
vec3 packFloatToVec3i(const float value)
{
 const vec3 bitSh = vec3(256.0 * 256.0, 256.0, 1.0);
 const vec3 bitMsk = vec3(0.0, 1.0/256.0, 1.0/256.0);
 vec3 res = fract(value * bitSh);
 res -= res.xxy * bitMsk;
 return res;
}
float unpackFloatFromVec3i(const vec3 value)
{
 const vec3 bitSh = vec3(1.0/(256.0*256.0), 1.0/256.0, 1.0);
 return dot(value, bitSh);
}

If there was a cached miss, the accumulative AO will be discarded and the instance AO value is used instead. Of course more samples can be taken in this frame to reduce the visual impact of the cache miss.

Discussion/improvements

Currently a new independent set of random samples were generated for the above video demo. Other random sample over time generation method may reduce the noise.
As some of the re-projection cache scheme suggested, a cache value should be cleared after a certain period of time to avoid in-stability and provide a better response to dynamic environment, and this is done here by the accumulation formula.
To reduce cache miss due to object movement, each object's last transformation matrix can also be incorporated into the algorithm.
The depth encoding scheme also make the blur pass much more efficient.

Conclusion

The explained algorithm provides a new way to improve the quality and efficiency of traditional SSAO by using the result from a number of frames instead of one. It also opens up more parameters and sampling patterns to explore with.

用 C# 製作使用者界面

2009-02-17T16:25:00.006+08:00

過去兩個星期開始製作使用者界面，選擇了 C# 加 Microsoft Windows Form 作為平台。
除了 C# 本身容易使用外，最令我覺得欣慰的就是那龐大的使用者社區，好一些想要的功能都已經有其他人做好了，或已有詳盡的教學可供參考。
以下是一些在我製作 Studio Tool 的時候所用到的一些 library:

移除 ".svn" 文件夾

2009-02-16T10:17:00.005+08:00

話說有一天我想著怎樣把一個專案之下的 ".svn" 文件夾全部移除，想著想著的都是一些 Linux command。最後找到這個：


find -type d -name .svn -exec rm -rf {} \;

怎知原來每天使用的 Tortoise SVN 已經有這個功能... 又做了一件愚蠢的事 XD

九型人格分析

2009-02-04T14:25:00.006+08:00

看來我滿喜歡建造遊戲引擎來成全自己亦希望同時成就他人。

九型人格分析
第二型	助人者、全愛型、助人型、成就他人者、博愛型 14%
第一型	完美主義者、完美型、改革者、改進型、秩序大使 13%
第六型	忠誠型、忠誠型、尋找安全者、謹慎型 13%
第三型	成就者、事業型、成就型、實踐型 12%
第四型	藝術型、浪漫者、自我型、憑感覺者 11%
第五型	智慧型、觀察者、思想型、理性分析者、思考型 9%
第七型	快樂主義型、豐富型、活躍型、創造可能者、享樂型 9%
第八型	領袖型、能力型、挑戰者、保護者、權威型 9%
第九型	和平型、和平者、和諧型、維持和諧者 7%

我的九型人格分析？

SSAO Demo

2009-01-15T14:43:00.004+08:00

花了一點時間整理好我的 SSAO Demo，請按這裡下載。請各位多給意見：)

操縱方法：

鏡頭移動：W、A、S、D、Page up、Page down
鏡頭方向：滑鼠左鍵
SSAO開關：F1，默認值：開
銀幕減半開關：F2，默認值：開
增大/減少模糊操作次數：F3/Shift+F3，默認值：2
漫射材質開關：F4，默認值：關
增大/減少閉塞半徑：Shift+F5/F5

後記：

看過 R5 Demo 後才覺悟增大 blur pass 次數和 blur kernel size 的分別。 Orz
把 depth encode 到三個 8-bit integer，那麼一塊 32-bit 的 RGBA render target 就可以運載 occlusion value 和 depth 到模糊操作中，從而大大減少 texture fetch 的數量。

檔案監視器

2009-01-13T17:24:00.012+08:00

看過了猴子靈藥的 "Database Hot Loader" 後，心動之下又想做些類似的東西，哪就是一個用來監視檔案系統的小工具。有了它，遊戲裡的任何素材(美術素材，以及音效、字型、腳本程序等等)檔案一經修改就會立即在遊戲裡反映出來，因而省去重新啟動遊戲程式的煩厭。當然背後還需健全的資源系統才能成事。

在視窗環境中，標準的方法是調用 FindFirstChangeNotification 或 ReadDirectoryChangesW；前者告訴你某個資料夾有否被更改，後者還會告訴你甚麼檔案/資料夾曾被更改。怎知 ReadDirectoryChangesW 的調用殊不簡單，MSDN 又沒有範例，上 CodeProject 碰碰運氣得來的是一個 3000 多行代碼的類別，Google 一翻還是找不到想要的。

經過一翻努力和嘗試(我相信 MSDN 是有錯漏的)，得知 GetOverlappedResult 和 ReadDirectoryChangesW 的配合是最簡單的；無須和任何多緒有關的東西打交道。我的 FileMonitor 就只有 constructor 和 getChangedFile 這兩個函數。

FileMonitor.h


#ifndef __FILEMONITOR__
#define __FILEMONITOR__

#include <string>

/*! To monitor file changes under a particular folder.
 The implementation use the win32 ReadDirectoryChangesW() function
 with GetOverlappedResult() to perform the monitoring, therefore
 no thread is created and so making the interface very simple.

 With the limitation of ReadDirectoryChangesW() is using a fixed buffer
 to hold the information between calls of getChangedFile(), FileMonitor
 may fail to detect file changes between calls of getChangedFile() if
 the file names are too large to fit into the buffer. To overcome the
 issue, you need to call getChangedFile() frequently.

 \sa http://mtlung.blogspot.com/2009/01/blog-post.html

 Example:
 \code
 FileMonitor monitor(L"pathToMonitor", true);
 // In your main loop:
 while(true) {
  std::wstring path;
  while(!(path = monitor.getChangedFile()).empty()) {
   std::wcout << path << std::endl;
  }
 }
 \endcode
 */
class FileMonitor
{
 // FileMonitor is non-copyable
 FileMonitor(const FileMonitor&);
 FileMonitor& operator=(const FileMonitor&);
 
public:
 /*! Constructor
  \param path The path to monitor
  \param recursive Watch the path recursively
  \param operationTowatch Which file operation to monitor with,
  having the same meaning as the dwNotifyFilter in ReadDirectoryChangesW()
  function, see http://msdn.microsoft.com/en-us/library/aa365465(VS.85).aspx
  for more details. By default, it's value is -1 and have the same meaning
  as FILE_NOTIFY_CHANGE_LAST_WRITE
  */
 FileMonitor(const wchar_t* path, bool recursive, int operationTowatch = -1);

 ~FileMonitor();

 /*! Get which file under the watching directory is changed.
  This function is non-blocking and if there is no changes in the
  file system, it will simple return an empty string.

  \note
  The current implementation use a fixed buffer to capture all the
  file changes between calls of getChangedFile(). If there are too
  much changes or the file names get too long, the buffer overflow
  and that file change notification will lost.
  See more on the documentation of ReadDirectoryChangesW() in MSDN.
  */
 std::wstring getChangedFile() const;

 private:
 class Impl; //!< Private implementation class
 Impl* mImpl;
}; // FileMonitor

#endif // __FILEMONITOR__

FileMonitor.cpp


#include "FileMonitor.h"
#include <assert.h>
#include <iostream>
#include <list>

// Exclude rarely-used stuff from Windows headers
#ifndef WIN32_LEAN_AND_MEAN
# define WIN32_LEAN_AND_MEAN
#endif
#ifndef VC_EXTRALEAN
# define VC_EXTRALEAN
#endif
#include <windows.h>

#ifdef _MSC_VER // Currently only windows is supported

class FileMonitor::Impl
{
public:
 Impl(const wchar_t* path, bool recursive, int operationTowatch)
  : mRecursive(recursive), mOperationTowatch(operationTowatch)
 {
  assert(int(mBuffer) % 4 == 0 && "Address of mBuffer must be 4-byte aligned");

  // Adjust the defalt value for mOperationTowatch
  if(mOperationTowatch == -1)
   mOperationTowatch = FILE_NOTIFY_CHANGE_LAST_WRITE;

  mDirectory = ::CreateFileW(
   path,
   FILE_LIST_DIRECTORY,
   FILE_SHARE_DELETE | FILE_SHARE_READ | FILE_SHARE_WRITE,
   0,
   OPEN_EXISTING,
   // ReadDirectoryChangesW() needs FILE_FLAG_BACKUP_SEMANTICS
   FILE_FLAG_OVERLAPPED | FILE_FLAG_BACKUP_SEMANTICS,
   0
  );

  memset(&mOverlapped, 0, sizeof(mOverlapped));
  if(!mDirectory || !readChange()) {
   ::CloseHandle(mDirectory);
   mDirectory = NULL;
   std::wcerr << L"Fail to watch directory: " << path << std::endl;
  }
 }

 ~Impl()
 {
  ::CloseHandle(mDirectory);
 }

 bool readChange() const
 {
  return ::ReadDirectoryChangesW(
   mDirectory,
   mBuffer, sizeof(mBuffer),
   mRecursive,
   mOperationTowatch,
   NULL,  // bytesRetured
   &mOverlapped,
   0   // callBack
  ) != 0;
 }

 std::wstring getChangedFile() const
 {
  // We will try to call GetOverlappedResult() even there are entries inside
  // mFiles, so that it's less possible for the mBuffer to be overflowed.

  // For some unknown reason(s) ReadDirectoryChangesW() will report the file twice,
  // therefore we add a loop to filter out those duplicated entries.
  for(size_t i=2; i--;)
  {
   DWORD bytesRetured = 0;
   if(0 == ::GetOverlappedResult(mDirectory, &mOverlapped, &bytesRetured, false))
    goto CACHED; // The use of goto here makes the code clean.

   if(bytesRetured == 0) {
    // TODO: To reduce the chance of insufficient buffer,
    // we can move the code to another thread.
    std::wcerr << L"Error returned by ReadDirectoryChangesW(), "
     L"most likely the internal buffer is too small" << std::endl;
    readChange();
    goto CACHED;
   }

   FILE_NOTIFY_INFORMATION* p = reinterpret_cast<FILE_NOTIFY_INFORMATION*>(mBuffer);
   while(true)
   {
    std::wstring fileName(p->FileName, p->FileNameLength / sizeof(wchar_t));

    // Skip duplicated entry
    if(mFiles.empty() || fileName != mFiles.back())
     mFiles.push_back(fileName);

    if(p->NextEntryOffset == 0)
     break;

    p = reinterpret_cast<FILE_NOTIFY_INFORMATION*>((char*)p + p->NextEntryOffset);

    // Do some extra buffer overflow check.
    if((char*)p - (char*)mBuffer > sizeof(mBuffer))
     break;
   }

   if(!readChange())
    return L"";
  }

  CACHED:
  if(!mFiles.empty()) {
   std::wstring ret = mFiles.front();
   mFiles.pop_front();
   return ret;
  }

  return L"";
 }

 HANDLE mDirectory;
 bool mRecursive;
 int mOperationTowatch;
 /*! This buffer must be 4-byte aligned, therefore we use int as the type.
 You may change the buffer size to fit your needs.
 */
 mutable int mBuffer[2048];
 mutable OVERLAPPED mOverlapped;
 //! A list of wstring acting as a circular buffer.
 mutable std::list<std::wstring> mFiles;
}; // Impl

FileMonitor::FileMonitor(const wchar_t* path, bool recursive, int operationTowatch)
{
 mImpl = new Impl(path, recursive, operationTowatch);
}

FileMonitor::~FileMonitor()
{
 delete mImpl;
}

std::wstring FileMonitor::getChangedFile() const
{
 __assume(mImpl); // We know mImpl is always not null, shut off the C++ analysis warning
 return mImpl->getChangedFile();
}

#endif // _MSC_VER

Main.cpp


#include "FileMonitor.h"
#include <iostream>
#include <conio.h> // For _kbhit()

int main()
{
 FileMonitor monitor(L"./", true);

 std::wcout << L"Create and modify the files in the current directory, "
 L"and the FileMonitor will tell you the name of those files.";
 std::wcout << L" Press any key to quit the program" << std::endl;

 while(!_kbhit())
 {
  std::wstring path;
  // Keep polling the monitor, But a real application should
  // only poll the monitor once a while.
  while(!(path = monitor.getChangedFile()).empty())
  {
  std::wcout << path << std::endl;
  }
 }

 return 0;
}

新年前的 SSAO

2008-12-31T22:55:00.000+08:00

相信很多朋友都趁年尾來一篇日誌，我也來熱鬧一番 ^.^
上一篇的 SSAO 日誌距今已有三個月；之後更改了演算法，本想多作改進和包裝成 demo 才放進來，但現在手頭上還正在建造一個給 OpenGl 的 Effect 架構，此刻只好放些 Screen shot 好了。

演算法和星海爭霸2 的相近，但我對 Image processing 的學識尚淺，Bilateral (edge-preserving) blur 的部分還有問題。

最後祝大家新年快樂。

沒有SSAO, 900 fps

屏幕 1/4 SSAO with dither, 252 fps

屏幕 1/4 SSAO with dither + blur, 233 fps

Is graphical shader system really that good?

2008-12-20T14:25:00.004+08:00

每當我們看到什麼的遊戲引擎有著一個可視化的 Shader 系統後都會覺得它分外強勁；
它一般被認為可以令製作流程更順暢，但這概念是否每一處也適用哩？讓我們聽一聽反對的聲音吧。

Graphical shader systems are bad

Commenting on graphical shader systems

Shader Workflow - Why Shader Generators are Bad

綜合各人的要點：

把電腦語言可視化不是一種萬靈丹。
用於非實時的 Rendering 還不錯，但用於講求高效率的實時 Rendering 就會帶來問題。
經可視化工具產生的 Shader 一般都比手寫的來得低效。
太容易去讓美術師建造數以千計獨一無二互相無關的 Shader，使後期整理成為惡夢。
削弱美術師和程式設計師之間的溝通。

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

2008-11-26T11:27:00.008+08:00

偶然於 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);
}

編程花招的謎思

2008-11-20T11:09:00.011+08:00

微軟快要推出下一代 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

2008-11-06T15:15:00.008+08:00

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

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

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

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

陰影映射

2008-10-31T18:33:00.007+08:00

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


// 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); 
}

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

紋理投影

2008-10-31T12:47:00.007+08:00

為了製作陰影映射 (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 寶庫

2008-10-13T18:18:00.009+08:00

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

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

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

SSAO 新進展

2008-09-22T15:21:00.001+08:00

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

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

兩像素於三圍空間中的位置；深度較淺的像素會遮蔽較深的像素，而遮蔽的程度就取決於距離。
兩像素的法線內積 (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);
}

《星海爭霸2》引擎技術解析

2008-09-14T14:04:00.000+08:00

繼 CryEngine 2 的 Finding Next Gen 之後，一向不與學術界為伍的 Blizzard 也不甘示弱；於 Siggraph 08 發表了一篇論文，當中的內容頗為深入。
期望星海爭霸2可快點推出。

初嚐 Shader 編程

2008-09-13T12:16:00.001+08:00

完成基本的 Shader 類別後，一口氣連 Multiple Render Target (MRT) 和 Screen Space Ambient Occlusion (SSAO) 都攪定了。這叫 SSAO 的技術是近一年電腦遊戲繪圖領域的新寵兒；它的原理是利用深度緩衝 (Depth Buffer) 計算出當前考慮中的像素和它周圍的像素，於三圍空間中的相互關係，再加上法線緩衝的話，就可以知道這像素有沒有被其他像素所 "遮蔽"。

暫時我的實作只用上了深度緩衝，算不上真正的 SSAO，至多是一個邊緣強調器；但出來的效果也不錯，可凸顯出物件的層次感。現有的實作會繼續改進之餘，亦會留下來給低級別的顯示卡使用。

Vertex shader code:


// Screen space ambient occlusion
// Reference:
// http://www.opengl.org/discussion_boards/ubbthreads.php?ubb=showflat&Number=236698&fpart=1
// http://www.4gamer.net/games/047/G004713/20080223007/screenshot.html?num=002
// http://rgba.scenesp.org/iq/computer/articles/ssao/ssao.htm
// http://meshula.net/wordpress/?p=145

varying vec2 texCoord;

void main(void)
{
 gl_Position = ftransform();
 texCoord = gl_MultiTexCoord0.xy;
 gl_FrontColor = gl_Color;
}

Pixel shader code:


uniform sampler2D texColor;  // Color texture
uniform sampler2D texDepth;  // Depth texture

uniform vec2 camerarange = vec2(1.0, 500);
uniform vec2 screensize;

varying vec2 texCoord;

float readDepth(in vec2 coord)
{
 return (2.0 * camerarange.x) /
 (camerarange.y + camerarange.x - texture2D(texDepth, coord).x * (camerarange.y - camerarange.x));  
}

void main(void)
{
 float depth = readDepth(texCoord);
 float d;

 float pw = 1.0 / screensize.x;
 float ph = 1.0 / screensize.y;

 float aoCap = 1.0;

 float ao = 0.0;

 float aoMultiplier = 1000.0;

 float depthTolerance = 0.0001;

 for(int i=0; i<4; ++i)
 {
  d = readDepth(vec2(texCoord.x + pw, texCoord.y + ph));
  ao += min(aoCap, max(0.0, depth - d - depthTolerance) * aoMultiplier);

  d = readDepth(vec2(texCoord.x - pw, texCoord.y + ph));
  ao += min(aoCap, max(0.0, depth - d - depthTolerance) * aoMultiplier);

  d=readDepth(vec2(texCoord.x + pw, texCoord.y - ph));
  ao += min(aoCap, max(0.0, depth - d - depthTolerance) * aoMultiplier);

  d = readDepth(vec2(texCoord.x - pw, texCoord.y - ph));
  ao += min(aoCap, max(0.0, depth - d - depthTolerance) * aoMultiplier);

  pw *= 2.0;
  ph *= 2.0;
  aoMultiplier /= 2.0;
 }

 ao /= 16.0;

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

最後還有一些未解決的問題，是關於 MRT 的；話說有些顯示卡並未支援非二乘方大小的材質緩衝，因此有必要使用 GL_TEXTURE_RECTANGLE_ARB，可惜用了這材質格式後 Pixel Shader 又神奇地把遮蔽量計錯了。看來 Shader 的除錯方法還要好好領會。

還有，材質緩衝是不支援 Fullscreen Anti-aliasing (FSAA) 的，這可以怎樣解決哩？

3DS轉換矩陣

2008-09-13T11:20:00.001+08:00

經過半天的勞力，終於成功載入轉換矩陣 (0x4160 trunk)，全靠 lib3ds 的原碼。


// Trunk 0x4160 comes before 0x4120,
// during the loading of 0x4160 we got the information to
// change the clockwise/anti-clockwise triangle winding or not
// and apply this information during the loading of 0x4120
bool invertTriangleWinding = false;

// ...

// Loading the local coordinates chunk
// It's base from lib3ds: http://www.lib3ds.org
case 0x4160:
{
 // We are using row major matrix
 Mat44f matrix = Mat44f::cIdentity;
 for(size_t i=0; i<4; ++i)
  mStream->read(matrix.row[i], sizeof(float) * 3);

 // Flip X coordinate of vertices if mesh matrix has negative determinant
 if((invertWinding = (matrix.determinant() < 0)) == true) {
  Mat44f inv = matrix.inverse();

  matrix.m00 = -matrix.m00;
  matrix.m01 = -matrix.m01;
  matrix.m02 = -matrix.m02;
  matrix.m03 = -matrix.m03;

  matrix = (inv * matrix).transpose();

  size_t vertexCount = getVertexCount();
  Vec3f* vertex = getVertexPointer();

  for(size_t i=0; i<vertexCount; ++i) {
   // Transform tmp using matrix, where matrix[3] holds the translation
#ifdef FLIP_YZ_AXIS
   Vec4f tmp(vertex[i].x, -vertex[i].z, vertex[i].y, 0);
   tmp = (matrix * tmp) + matrix[3];
   vertex[i] = Vec3f(tmp.x, tmp.z, -tmp.y);
#else
   Vec4f tmp(vertex[i].x, vertex[i].y, vertex[i].z, 0);
   tmp = (matrix * tmp) + matrix[3];
   vertex[i] = Vec3f(tmp.x, tmp.y, tmp.z);
#endif
  }
 }
}  break;

// ...

// Loading the face description (index values) trunk
case 0x4120:
{
 uint16_t faceCount = 0;
 uint16_t* indexArray = nullptr;

 // ...

 if(invertTriangleWinding) {
  for(size_t i=0; i<faceCount*3; i+=3)
   std::swap(indexArray[i], indexArray[i+2]);
 }
}  break;

3DS 文件格式

2008-09-07T22:40:00.000+08:00

於 Mesh Factory 下載模型

完成了 3DS 文件的加載器已有多個星期，到今天才有點時間張貼出來。
其實 3DS 已是一個很古老的格式，它的材質參考路徑僅支援 8.3 格式, 是 Dos 年代的產物。但基於這格式的廣泛流傳和結構簡單，因此儘管 Collada 是大勢所趨，我還是決意使用它作為引擎裡的第一個模型加載器。這樣我就可以快點進行其他方面的進修，待其他模組有了原型以後才加入其他加載器。

我的實作很基本，只支援頂點，索引，標準材質和貼圖；所有的法線得自行計算，雖然我已對 Smoothing Group 加以支援，但有些位置的效果還是顯得不平滑。相信最好的辦法都是直接從 DCC 工具中讀入法線向量，可惜 3DS 沒有這資訊。另外有好一些物體的位置錯了，似乎純粹讀入頂點位置並不足夠，還以為 3DS 格式用不著轉換矩陣。

最後我當然把加載器和之前設計好的資源管理和漸進裝載模組整合在一起，當中的細節留待日後再作詳述。

谷歌瀏覽器 Chrome

2008-09-03T10:19:00.000+08:00

作為全球資訊網的龍頭大哥谷歌 Google, 推出自家的瀏覽器是遲早的事. 這位新晉的瀏覽器名叫 Chrome, 還是 Beta 階段. 它的宣傳標題是 "一個方塊，無所不包", 正合谷歌一貫使用網上平台的理念; 而一個好的瀏覽器將會是這革命的催化劑.

試用後感覺良好, 介面簡單反應夠快. 而我最喜歡的就是把菜單/按鈕等等介面壓縮成不到80圖素的垂直空間裏, 就連標題棒都省去了.

至於內部構和設計理念, 谷歌用了漫畫形式展示出來. 從中得知谷歌為了避開記憶體洩漏以及安全性的問題, 挑選了一個 Tab, 一個進程 (Process) 的設計. 這有點兒走回頭路的感覺, 但不失為簡單快捷的方案; 何況 Chrome 創建新 Tab 的速度奇快, 沒有半點被創建進程的開銷所拖慢.

目前 Chrome 和 Firefox 相比下還缺少一眾好用的插件, 但相信新一輪瀏覽器之戰又開始了.

C 函數的新發現

2008-08-08T11:31:00.001+08:00

以往如需要從程式的主迴圈讀取鍵盤的輸入去決定是否退出程式, 我會用另一個執行緒去乎叫 std::cin 或 getchar(), 因為它們都是阻塞 (blocking) 的.

原來我一直忽略了 kbhit() 的存在! 有了它, 以上的問題就可簡化為:


#include 

int main() {
 while(true) {
  // Poll the console without blocing, return true if there is
  // a keystroke waiting in the buffer.
  if(kbhit()) {
   if(getchar() == 'q')
    break;
  }

  // Do something usefull
  // ...
 }
 return 0;
}

可惜 kbhit() 不是標準 C 裡的成員, 在若干平台上我們得自行實踐. 以下編碼出於這裡


#include <sys/select.h>

int kbhit(void)
{
 struct timeval tv;
 fd_set read_fd;

 /* Do not wait at all, not even a microsecond */
 tv.tv_sec=0;
 tv.tv_usec=0;

 /* Must be done first to initialize read_fd */
 FD_ZERO(&read_fd);

 /* Makes select() ask if input is ready: 0 is the file descriptor for stdin */
 FD_SET(0, &read_fd);

 /* The first parameter is the number of the largest file descriptor to check + 1. */
 if(select(1, &read_fd, NULL/*No writes*/, NULL/*No exceptions*/, &tv) == -1)
  return 0; /* An error occured */

 /* read_fd now holds a bit map of files that are
  * readable. We test the entry for the standard
  * input (file 0). */
 if(FD_ISSET(0, &read_fd))
  /* Character pending on stdin */
  return 1;

 /* no characters were pending */
 return 0;
}

共享算術運算子

2008-07-22T10:34:00.001+08:00

每當實作一些有關數學的類別 (如 Vector, Matrix, Point, Size 等...) 時，加減乘除等運算子都會時常出現。讓我們試試把共同的地方提煉成基類別：


template<int N>
class Tuple {
public:
 Tuple operator+(const Tuple& rhs) const
 {
  Tuple result;
  for(int i=0; i<N; ++i)
   result.data[i] = data[i] + rhs.data[i];
  return result;
 }

 float data[N];
};

class Vec3 : public Tuple<3> {
public:
 Vec3(float x, float y, float z) {
  data[0] = x; data[1] = y; data[2] = z;
 }
};

int main() {
 Vec3 v1(1, 2, 3);
 Vec3 v2(4, 5, 6);
 // Compilation error: v1 + v2 is returning Tuple but not Vec3
 Vec3 v3 = v1 + v2;
 return 0;
}

大家不用擔心那個回圈會為性能帶來負面影響，編譯器懂得把它優化 (我已在VC2008上證實了這一點)。
但由於運算子的返回型態出了問題，我們作出以下嘗試：


template<int N, class R>
class Tuple {
public:
 R operator+(const Tuple& rhs) const
 {
  R result;
  for(int i=0; i<N; ++i)
   result.data[i] = data[i] + rhs.data[i];
  return result;
 }

 float data[N];
};

class Vec3 : public Tuple<3, Vec3> {
public:
 Vec3(float x, float y, float z) {
  data[0] = x; data[1] = y; data[2] = z;
 }
};

int main() {
 Vec3 v1(1, 2, 3);
 Vec3 v2(4, 5, 6);
 Vec3 v3 = v1 + v2;
 return 0;
}

非常好。不過還可以更好哩：


template<int N, class R, class U>
class Tuple : public U {
public:
 R operator+(const Tuple& rhs) const
 {
  R result;
  for(int i=0; i<N; ++i)
   result.data[i] = data[i] + rhs.data[i];
  return result;
 }
};

struct _Vec3Union {
 union {
  struct { float x, y, z; };
  float data[3];
 };
};

class Vec3 : public Tuple<3, Vec3, _Vec3Union> {
public:
 Vec3() {}
 Vec3(float x_, float y_, float z_) {
  x = x_; y = y_; z = z_;
 }
};

struct _SizeUnion {
 union {
  struct { float width, height; };
  float data[2];
 };
};

class Size : public Tuple<2, Size, _SizeUnion> {
public:
 Size() {}
 Size(float w, float h) {
  width = w; height = h;
 }
};

int main() {
 Vec3 v1(1, 2, 3);
 Vec3 v2(4, 5, 6);
 Vec3 v3 = v1 + v2;

 Size s1(1, 2);
 Size s2(2, 3);
 Size s3 = s1 + s2;

 return 0;
}

這可讓 Vec3 組成的 x, y 和 z 用方便的形式去存取。

儘管以上的提示未必有多大用途，還望它能加強大家對 C++ 的了解。

尼采的神奇 Functor

2008-07-14T14:15:00.001+08:00

尼采給我的題目...不如在此發表答案.


#include <iostream>

typedef int (*Functor)();

// Recursive type template that generate a
// compile-time list of Functor using inheritance
template<size_t N> struct Unit : public Unit<N-1> {
  Unit() : mFunctor(&Unit<N>::fun) {}
  static int fun() { return N; }
  Functor mFunctor;
};

// Partial specialization to end the recursion
template<> struct Unit<0> {
  Unit() : mFunctor(&Unit<0>::fun) {}
  static int fun() { return 0; }
  Functor mFunctor;
};

// Partial specialization to reduce recursive template complexity
template<> struct Unit<256> : public Unit<255> {
  Unit() : mFunctor(&Unit::fun) {}
  static int fun() { return 256; }
  Functor mFunctor;
};

// Partial specialization to reduce recursive template complexity
template<> struct Unit<512> : public Unit<511> {
  Unit() : mFunctor(&Unit::fun) {}
  static int fun() { return 512; }
  Functor mFunctor;
};

// A compile-time maximum count of Functor
static const size_t cMaxN = 768;

typedef Unit<cMaxN> List;
static const List cList;

// A function that return a Functor that return i.
// In other words, it selects from a list of compile-time functors
// base on the run-time parameter i.
Functor getFunctor(int i) {
  {  // We have the assumption that Unit<> struct are packed tightly together in cList
    typedef const char* byte_ptr;
    byte_ptr functorAddres1 = byte_ptr(&(static_cast<const Unit<1>*>(&cList)->mFunctor));
    byte_ptr functorAddres2 = byte_ptr(&(static_cast<const Unit<2>*>(&cList)->mFunctor));
    (void)functorAddres1;  (void)functorAddres2;
    assert(functorAddres2 - functorAddres1 == sizeof(Functor));
  }
  assert(i <= cMaxN);
  return *((Functor*)(&cList) + i);
}

int main() {
  for(size_t i=0; i<=cMaxN; ++i) {
    Functor f = getFunctor(i);
    std::cout << f() << std::endl;
    assert(f() == int(i));
  }

  return 0;
}

Win少, 我的答案正確嗎?

我認為最好的 Pdf 閱讀器

2008-07-14T11:36:00.001+08:00

不知不覺 Adobe Acrobat Reader 已經出到第九代了.
在每一次更新的時候, 大家有沒有想過其實可能更有好的選擇呢?
我有一個好推薦, 它就是 Foxit Reader.

Foxit 的描繪品質和速度與 Acrobat 不分上下, 但記憶體用量和啟動時間就遠勝 Acrobat; 更不用安裝 , 細小可攜 (僅一個 5MB 的可執行檔).

以下的測試是基於網上的一篇文章:

	Adobe Reader 9	Foxit Reader 2.2
啟動須時 (秒)	21	7
記憶體用量	74MB	25MB

縱然 Foxit 缺少某些(許多人都不常用的)功能, 它帶來的眾多好處立即使我把 100 多MB的 Acrobat Reader 從系統中撤除.

程式語言效率大比拼

2008-07-02T17:20:00.000+08:00

有天正在尋找腳本語言的時候無意間發現這個名為 The Computer Language Benchmarks Game 的網站.
那裡的 benchmark 數據覆蓋多達 76 種語言加編輯器的組合, 19 個試驗程式(大部分還有提供源始碼).
不過, 儘管那裡提供的資料準確無誤, 它所包含的參考價值仍然有限. 問題在於那些試驗程式都過於細小, 以及只有單一的功能. 在一個複雜的應用程式 (如 3D Game Engine), 有大量不同種類的資料需要處理, 因此記憶體的存取很容易成為瓶頸.
一個好例子就是 Java/.Net. 有數據顯示 Java/.Net 可以快過 C/C++, 不過當你走出試驗程式返回現實, 你會感到 Java/.Net 總是慢半拍的.

其實那網站的第一段就表明了:

Benchmarking programming languages?
How can we benchmark a programming language?
We can't - we benchmark programming language implementations.

How can we benchmark language implementations?
We can't - we measure particular programs!

Resources loading

2008-06-18T10:43:00.001+08:00

最近完成了漸進裝載系統 (Progressive resource loading) 的設計與實作.
現階段能夠以多緒形式載入 Jpeg 和 Png

要達到多緒, 首要分開載入和使用中的資料.
函式 load() 會把 istream 中的資料解碼到 loader 裏的私有緩衝區之中, 這時候 LoadingState 為 Loading.
當一定數量的資料已解碼而又可以顯示出來, load() 會返回 LoadingState = PartialLoaded, 這時候你可以乎叫 commit() 把 loader 中的緩衝抄到 resource 去.
請注意 load(), commit() 和 getLoadingState() 好有可能在不同的執行緒中執行, 因此 loader 裏的緩衝區和 LoadingState 成員都要用 Mutex 來保護.

有一點值得討論的就是 load() 這函式.
現在的設計須要用者不停地乎叫 load() 直到它返回 Loaded 或 Aborted. 但我曾經考慮過使用事件 (Event) 來通知用者現在的 LoadingState 從而只需乎叫 load() 一次. 接著當我試圖實作 cancel() 這函式時, 問題出現了; 我得建造另一個事件來控制 load() 內部的循環何時跳出.
實在不好, 複雜跳進來了...還要處理令人頭痛的多緒同步哩! 想起 Pull Xml 帶給我的啟示, 原來只要把 load() 內的循環交給用者來定義, 一切都簡單得多.
再細心的想, 如果用者希望一幅圖像載入了第一個漸進後便去開始載入另一幅圖像的話, 用事件的作法是行不通的 (或變得異常複雜). 所以這個新的設計不止簡單, 還非常靈活. 我又一次體會到什麼是 Less is more, There is No CODE that is more flexible than NO Code!.

C++ friend class

2008-06-11T09:28:00.001+08:00

有些時候我們會利用 C++ 中的 friend 關鍵字來設定類別的好友.
但可惜一個 friend 宣告只會對一個類別產生作用:


class Texture {
public:
 friend class IResourceLoader;
 uint width() const { return mWidth; }
 uint height() const { return mHeight; }
 private:
 uint mWidth;
 uint mHeight;
};

class IResourceLoader {};

class JpegLoader : public IResourceLoader {
 void load() {
  // ...
  mTexture.mWidth = 128;  // Compiler error!!
 }
};

以上的 Texture 類別有成員 mWidth 和 mHeight, 它們都只應由 IResourceLoader 的實作類別所能更改. 幸好有 Inner class 可以幫到我們:


// Texture.h
class Texture {  
public:  
 friend class IResourceLoader;  
 uint width() const { return mWidth; }  
 uint height() const { return mHeight; }  

 // We declare a templated inner class here (but not defined yet)
 template class PrivateAccessor;

 private:  
 uint mWidth;  
 uint mHeight;  
};

class IResourceLoader {};  

// JpegLoader.cpp
// Define Texture::PrivateAccessor here, access what ever you want
template<>
class Texture::PrivateAccessor {
public:
 static size_t& width(Texture& texture) {
  return texture.mWidth;
 }
 static size_t& height(Texture& texture) {
  return texture.mHeight;
 }
};
typedef Texture::PrivateAccessor Accessor;

void JpegLoader::load() {
 // ...  
 Accessor::width(mTexture) = 128; // Ok! no problem
 Accessor::height(mTexture) = 128;
}

你可能會認為這樣做等同把所有成員變為公開 (public), 事實上這個方案的精神在於迫使程序員清楚自己正在做什麼, 而不是錯誤地更改了變數.

Syntax highlighting

2008-06-11T09:23:00.000+08:00

要貼原碼第一件事當然是設置"語法高亮度顯示" (Syntax highlight)
Syntaxhighlighter 是一個純粹用客戶端 Java Script 來達到效果.

還有一些文章 1, 2 有更好的指示.

學習, 再學習

2008-06-06T09:34:00.000+08:00

經過三年的遊戲引擎開發後, 縱然我從中已學到了許多; 但還要學的更多, 無窮無盡的多.
僅僅 C++ 這令人又愛又恨的東西我已學了十年 (Teach yourself programming in ten years).
那其實是一件好事, 我就是喜歡學習的過程.

華而不實的東西我已做過不少 (如 Exmat ).
現在我正集中焦點學習怎樣去設計簡單清晰的軟件.

而這裡正是用來把這過程記錄下來, 希望大家多多指教.