引擎開發進度

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

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

於特定線程設置中斷點

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

1. 右擊您的 break point 然後使用 break point filter
   
   選擇線程 id
   
   
2. 另一個方法是使用 break point condition
   
   
   

不要被 Windows.h 強暴

引擎的物理部份開始開發，我滿心喜悅地把 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 單元測試框架

暫時還無法找到一個給予 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

串列矩陣乘法優化

埋頭苦幹於 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

（圖片來源：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++ 結合庫，下次再和大家分享。

簡單地閱讀整個文件

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

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。
請注意，以上代碼旨在簡潔，未必是高效的實作。