flagship的理想與現(xiàn)實

      首先我們得明確3D引擎使用多線程的目的所在：
1、在CPU上進(jìn)行的邏輯計算（比如骨骼動畫粒子發(fā)射等）不影響渲染速度
2、較差的GPU渲染速度的低下不影響邏輯速度

      第一個目標(biāo)已經(jīng)很明確了，我來解釋下需要達(dá)到第二個目標(biāo)的原因：許多動作游戲的邏輯判定是基于幀的，所以在渲染較慢的情況下，邏輯不能跳幀，而仍然需要嚴(yán)格執(zhí)行才能保證游戲邏輯的正確性，這就導(dǎo)致了游戲速度的放慢，而實際上個人認(rèn)為渲染保持15幀以上就已經(jīng)可以正常進(jìn)行游戲了。
      在較差的GPU上跑《鬼泣4》《刺客信條》《波斯王子4》簡直就像是慢鏡頭一樣，完全沒法玩。而實際上CPU跑滿幀是沒有問題的，如果能把邏輯幀和渲染幀徹底分離，即使渲染幀達(dá)不到要求，但CPU仍能正確的執(zhí)行游戲邏輯，就可以解決動作游戲?qū)PU要求過高的問題。

      我們先來看多線程Ogre的兩種架構(gòu)，第一種是middle-level multithread


      如上圖所示，每個需渲染的實體被復(fù)制成了兩份，主線程和渲染線程交替更新和渲染同一個實體的兩個備份，并在一幀結(jié)束時同步，這種解決方案達(dá)到了第一個目標(biāo)而并沒有達(dá)到第二個目標(biāo)，同時兩份實體的維護也相對復(fù)雜，并且沒法為更多核數(shù)的CPU進(jìn)行擴展優(yōu)化。
      第二種Ogre多線程的方法是 low-level multithread

      如圖，將D3D對象復(fù)制兩份，同樣是在幀結(jié)束時同步并交換，和上面的優(yōu)缺點類似。兩種多線程Ogre的解決方案都是在引擎層完成的，對上層應(yīng)用透明，對于用戶而言無需考慮多線程細(xì)節(jié)，這點是非常不錯的。

      接下來我們來看SIGGRAPH2008上，id soft提出的多線程3D引擎的方案

      這里是已PS3的引擎結(jié)構(gòu)為例的，與PC有較大的差別，其中SPU是Cell芯片的8個協(xié)處理器，擁有強大的并行能力，id的解決方案在SPU上進(jìn)行了諸如骨骼動畫、形變動畫、頂點和索引緩存的壓縮、Progressive Mesh的計算等諸多內(nèi)容，同時與PPU上的物理計算RSX上的渲染工作交錯進(jìn)行，最大化的利用了PS3的硬件結(jié)構(gòu)，最終的游戲產(chǎn)品《Rage》很快就會面世了！

      最后是我的解決方案

      特點是邏輯完全分離，無需同步，雖然成功的達(dá)到了文章開始提出的兩個目標(biāo)，但對于引擎的使用者必須考慮多線程的諸多問題，各種計算需放在哪個線程，如何在兩個線程間交互，都需要深入思考，所以要應(yīng)用到實際的游戲制作，恐怕還有很長的一段路要走。
      結(jié)合目前的架構(gòu)和上面看到的幾種多線程架構(gòu)，同時也為了迎接DX11的到來，我準(zhǔn)備將我的方案進(jìn)一步改進(jìn)成如下所示

      場景剪裁與提交渲染交替進(jìn)行，并在渲染幀末進(jìn)行一次同步，而多個渲染表面的場景剪裁可再并行執(zhí)行。
      圖片多，文字少，需更詳細(xì)資料請自行g(shù)oogle，本文就此結(jié)束！

    最近為了實現(xiàn)多光源和多陰影的渲染，把渲染系統(tǒng)改成了多Pass的，對每一個可見光源進(jìn)行一次光照、ShadowMap和最終陰影的渲染，雖然這樣等于是把整個場景重復(fù)渲染了很多次，但為了實現(xiàn)靈活的實時光照系統(tǒng)，這似乎是唯一的辦法了。
    但實踐后發(fā)現(xiàn)，陰影和光照會隨著骨骼動畫的播放而閃爍，甚至鏡頭的移動也會造成閃爍，究其原因，還是邏輯線程和渲染線程的同步問題，由于對場景內(nèi)的同一個物體渲染了多次，而邏輯線程又在不停的更新攝像機和骨骼動畫數(shù)據(jù)，導(dǎo)致了兩Pass渲染取到的數(shù)據(jù)很可能不一致，造成了光照和陰影的閃爍。
    所以共享數(shù)據(jù)結(jié)構(gòu)必須做一些修改，在多Pass渲染開始前進(jìn)行一次備份，渲染中只取備份數(shù)據(jù)，這樣就保證了多次渲染的數(shù)據(jù)一致性了

    也就是加這么兩個簡單的set和get方法，在渲染相關(guān)數(shù)據(jù)讀取時調(diào)用get，邏輯相關(guān)時調(diào)用read

template <class T>
struct SharedData
   {
        T        m_pData[DATACENTER_CACHE];
        T        m_kCloneData;
        int      m_iIndex;

        SharedData()
      {
            ZeroMemory( m_pData, DATACENTER_CACHE * sizeof(T) );
            m_iIndex = 0;
        }

        void    Write( T& rData )
      {
            int iNewIndex = m_iIndex == DATACENTER_CACHE - 1 ? 0 : m_iIndex + 1;
            m_pData[iNewIndex] = rData;
            m_iIndex = iNewIndex;
        }

        T&    Read()
      {
           return m_pVector[m_iIndex];
        }

        void    Set()
      {
           m_kCloneData = Read();
        }

        T&      Get()
      {
           return m_kCloneData;
        }
    };

    前幾天突然想起新的DXSDK應(yīng)該早出了，去微軟網(wǎng)站一看，好么。。。2008 Dec版早出了，這次火星了，下載完后居然發(fā)現(xiàn)包壞掉了，于是重下。。。還是壞掉！第三次也不行，折騰了一下午，最后放棄了，還好貌似只有Sample的最后一點點沒解壓開，沒什么大礙。
    本來只是以為自己只是火星了而已，裝好一看，完。。。徹底冥王星了，DX11的Preview版出了！真是又激動又懊悔，粗略看了看，新特性真是太令人激動了，主要有以下幾點：

一、SM5.0 從類C變成類C++了，有類有繼承有虛函數(shù)，太夸張了。。。
二、支持Shader動態(tài)Link，DX9里面就有個FragmentLinker，不太好用，DX10直接取消了，這次變本加厲的又回來了！
三、渲染的多線程支持，我重點來談?wù)勥@個

    DX11提供了一個新的接口：ID3D11DeviceContext，取代了以前Device接口所有與渲染相關(guān)的功能，有兩個類型：immediate和deferred，前者和現(xiàn)在的效果一樣，收到渲染指令就立即執(zhí)行，而后者則會將命令緩存起來，由用戶決定何時執(zhí)行。
    在例子MultithreadedRendering11中，渲染了三面帶反射的鏡子和一個人物模型，Sample創(chuàng)建了四個Context，三個deferred用于鏡子反射表面的渲染，一個immediate用于最終場景，Sample創(chuàng)建了三個線程，渲染幀開始時，首先并行的執(zhí)行三個鏡子反射的渲染，完成后，在主線程順序執(zhí)行三個Context，然后用immediate的Context渲染最終場景。
    由這個例子，我們來展望一下美好的未來：所有的渲染表面都可以并行執(zhí)行，比如水面、鏡子、甚至ShadowMap，并行的進(jìn)行場景剪裁，使得多核CPU的使用更有效率。
    DX11預(yù)計在今年年底推出，于Windows7捆綁，到那時，四核CPU應(yīng)該已經(jīng)普及了吧。。。

        在實際游戲中，邏輯線程需要對渲染對象做許多操作，比如添加與刪除，改變渲染對象的屬性等等，而由于在先前的設(shè)計中，邏輯線程與渲染線程相互獨立，如果只是改變某一共享數(shù)據(jù)，沒有問題，但如果操作影響到了場景結(jié)構(gòu)，例如實體的添加與刪除，則必須進(jìn)行線程同步，這又違背了FlagshipEngine的設(shè)計初衷——避免繁重的邏輯計算影響渲染速度。
        解決辦法其實在上一篇中已經(jīng)提到了，仍然是利用天然的同步機制——Windows消息，添加實體時，邏輯線程只是new了一個Entity對象，設(shè)置這個對象的初始共享數(shù)據(jù)，比如位置信息，同時向渲染線程發(fā)送一條WM_ADDENTITY的自定義消息，將Entity指針作為wParam傳遞。渲染線程接受到消息后調(diào)用Entity的UpdateScene方法，更新Entity在場景樹中的位置，并加載資源。
        刪除也是一樣，邏輯線程向渲染線程發(fā)送WM_DELETEENTITY消息，并不再使用該Entity指針，渲染對象則處理改消息，將此Entity從場景中刪除并卸載資源。
        這里有一個非常危險的情況，前面一篇提到，資源加載也是通過消息傳遞實現(xiàn)的，同樣是傳遞的資源指針，如果邏輯線程添加了一個Entity，還沒加載就刪掉了它，則資源加載線程會拿到一個過期指針，一切就結(jié)束了。。。
        解決這一問題，最穩(wěn)妥的方法是消息的wParam并不傳遞指針，而是傳遞該Entity或資源的唯一ID，這樣的話即使ID過期，也可輕松忽略掉這條消息，壞處是每次消息處理都的從全局的map里檢查是否存在此ID對應(yīng)的Entity或資源，這可是筆不小的開銷。
        第二種方案，我們?nèi)匀粋鬟f指針，只是在接受到WM_DELETEENTITY消息時，檢查該Entity是否已經(jīng)加載完成，如果沒有完成，則重新將此消息加入消息隊列，下個渲染幀再次判斷。
       FlagshipEngine的多線程設(shè)計大致就是如此了。

        現(xiàn)在我們已經(jīng)有了三個可獨立工作的線程：資源加載線程、邏輯線程、渲染線程，下一步我們需要決定它們?nèi)绾卧趯嶋H的項目中相互配合，也就是所謂的應(yīng)用程序框架了，該框架需要解決以下兩個問題
        首先，資源讀取線程可以簡單設(shè)計為一個循環(huán)等待的線程結(jié)構(gòu)，每隔一段時間檢查加載隊列中是否有內(nèi)容，如果有則進(jìn)行加載工作，如果沒有則繼續(xù)等待一段時間。這種方式雖然簡單清晰，但卻存在問題，如果等待時間設(shè)得過長，則加載會產(chǎn)生延遲，如果設(shè)得過短，則該線程被喚醒的次數(shù)過于頻繁，會耗費很多不必要的CPU時間。
        然后，主線程是邏輯線程還是渲染線程？因為邏輯線程需要處理鍵盤鼠標(biāo)等輸入設(shè)備的消息，所以我起初將邏輯線程設(shè)為主線程，而渲染線程另外創(chuàng)建，但實際發(fā)現(xiàn)，幀數(shù)很不正常，估計與WM_PAINT消息有關(guān)，有待進(jìn)一步驗證。于是掉轉(zhuǎn)過來，幀數(shù)正常了，但帶來了一個新的問題，邏輯線程如何處理鍵盤鼠標(biāo)消息？
      
        對于第一個問題，有兩種解決方案：
        第一，我們可以創(chuàng)建一個Event，資源讀取線程使用WaitForSingleObject等待著個Event，當(dāng)渲染線程向加載隊列添加新的需加載的資源后，將這個Event設(shè)為Signal，將資源讀取線程喚醒，為了安全，我們?nèi)孕枰阡秩揪€程向加載隊列添加元素，以及資源加載線程從加載隊列讀取元素時對操作過程加鎖。
        第二，使用在渲染線程調(diào)用PostThreadMessage，將資源加載的請求以消息的形式發(fā)送到資源價值線程，并在wParam中傳遞該資源對象的指針，資源加載線程調(diào)用WaitMessage進(jìn)行等待，收到消息后即被喚醒，這種解決方案完全不需要加鎖。
        對于第二個問題，我們同樣可以用PostThreadMessage來解決，在主線程的WndProc中，將邏輯線程需要處理的消息發(fā)送出去，邏輯線程收到后進(jìn)行相關(guān)處理。

        需要注意的是，我們必須搞清楚線程是在何時創(chuàng)建消息隊列的，微軟如是說：

The thread to which the message is posted must have created a message queue, or else the call to PostThreadMessage fails. Use one of the following methods to handle this situation.

• Call PostThreadMessage. If it fails, call the Sleep function and call PostThreadMessage again. Repeat until PostThreadMessage succeeds.
• Create an event object, then create the thread. Use the WaitForSingleObject function to wait for the event to be set to the signaled state before calling PostThreadMessage. In the thread to which the message will be posted, call PeekMessage as shown here to force the system to create the message queue.

  PeekMessage(&msg, NULL, WM_USER, WM_USER, PM_NOREMOVE)

  Set the event, to indicate that the thread is ready to receive posted messages.

        看來，我們只需要在線程初始化時調(diào)一句PeekMessage(&msg, NULL, WM_USER, WM_USER, PM_NOREMOVE)就可以了，然后在主線程中如此這般：

        在邏輯線程中這般如此：
        完成！

        目前的3D引擎的渲染幀和邏輯幀都是在一個線程上運行的，在網(wǎng)絡(luò)游戲中大量玩家聚集，繁重的骨骼動畫計算和粒子計算極大的拖累了渲染幀數(shù)，有兩種有效措施：1、控制同屏顯示人數(shù)，但玩家體驗不好 2、幀數(shù)低于某值時減少動畫Tick頻率，但帶來的問題是動畫不連貫。
        如果考慮使用多線程優(yōu)化，最容易想到的就是采用平行分解模式，將骨骼動畫計算和粒子計算寫成兩個for循環(huán)，然后用OpenMP將其多線程化，但事實上這樣并不會提高多少效率，這兩者計算仍然要阻滯渲染幀，線程的創(chuàng)建也有一定的消耗。于是我想到了一種極端的解決方案，采用任務(wù)分解模式，將渲染和邏輯完全分離到兩個線程去，互不影響，當(dāng)然這樣線程同步會是大問題，畢竟線程的數(shù)量和BUG的數(shù)量是成正比的。
        我們首先來分析下這兩個線程分別需要做什么工作，需要那些數(shù)據(jù)。渲染線程需要獲取實體的位置、材質(zhì)等信息，并交給GPU渲染，邏輯線程需要更新實體的位置、材質(zhì)、骨骼動畫等數(shù)據(jù)，很顯然一個寫入一個讀取，這為我們實現(xiàn)一個沒有線程同步的多線程3D渲染系統(tǒng)提供了可能。
        為了讓讀取和寫入不需要Lock，我們需要為每一份數(shù)據(jù)設(shè)計一個帶有冗余緩存的結(jié)構(gòu)，讀取線程讀取的是上次寫入完成的副本，而寫入線程則向新的副本寫入數(shù)據(jù)，并在完成后置上最新標(biāo)記，置標(biāo)記的操作為原子操作即可。以Vector為例，這個結(jié)構(gòu)大致是這樣的：
        當(dāng)然我們可以用模板來寫這個結(jié)構(gòu)，讓其適用于int，float，matrix等多種數(shù)據(jù)類型，余下的工作就簡單了，將所有有共享數(shù)據(jù)的類的成員變量都定義為以上這種數(shù)據(jù)類型，例如我們可以定義：
        SharedData<Matrix4f>  m_matWorld;
        在渲染線程中調(diào)用pDevice->SetWorldMatrix( m_matWorld.Read() );
        在邏輯線程中調(diào)用m_matWorld.Write( matNewWorld );

        需要注意的是，這種方案并非絕對健壯，當(dāng)渲染線程極慢且邏輯線程極快的情況下，有可能寫入了超過了DATACENTER_CACHE次，而讀取卻尚未完成，那么數(shù)據(jù)就亂套了，當(dāng)然真要出現(xiàn)了這種情況，游戲早已經(jīng)是沒法玩了，我測試的結(jié)果是渲染幀小于1幀，邏輯幀大于10000幀，尚未出現(xiàn)問題。
        FlagshipEngine采用了這一設(shè)想，實際Demo測試結(jié)果是，計算25個角色的骨骼動畫，從靜止到開始奔跑，單線程的情況下，幀數(shù)下降了20%～30%，而使用多線程的情況下，幀數(shù)完全沒有變化！

        資源異步加載恐怕是3D引擎中應(yīng)用最為廣泛的多線程技術(shù)了，特別是在無縫地圖的網(wǎng)絡(luò)游戲中，尤為重要，公司3D引擎的資源加載部分采用了硬盤->內(nèi)存->顯存兩級加載的模式，超時卸載也分兩級，這樣雖然實際效果不錯，但代碼非常繁瑣，在FlagshipEngine中，我設(shè)法將其進(jìn)行了一定程度的簡化。

首先我們需要定義一個Resource基類，它大致上是這樣的：
        在實際游戲中，加載資源的范圍大于視野，當(dāng)攝像機移動到單元格邊緣(必須有一定的緩沖區(qū))，就應(yīng)將新的單元格中的對象加入到資源加載隊列中，喚醒資源加載線程調(diào)用Load接口進(jìn)行加載，完成后將該資源的加載標(biāo)記設(shè)為true。而通過可視剪裁所得到的最終可視實體，則需要調(diào)用Cache接口構(gòu)建圖像API所需對象，當(dāng)Load和Cache都完成后IsReady才會返回true，這時該資源才能開始被渲染。
        卸載方面，在加載新的單元同時，卸載身后舊的單元，對單元內(nèi)所有資源調(diào)用Release，Load/Release帶有引用計數(shù)，仍被引用的資源不會被卸載。當(dāng)某一資源長時間沒有被看見，則超時，調(diào)用UnCache釋放VertexBuffer等資源。
        為了實現(xiàn)超時卸載功能，我們需要一個ResourceManager類，每幀檢查幾個已Cache的資源，看起是否超時，另外也需對已加載的資源進(jìn)行分類管理，注冊其資源別名（可以為其文件名），提供查找資源的接口。
        另外為了方便使用，我們需要一個模板句柄類ResHandle<T>，設(shè)置該資源的別名，其內(nèi)部調(diào)用ResourceManange的查找方法，看此資源是否已存在，如不存在則new一個新的，GetImpliment則返回該資源對象，之后可以將該資源添加到實體中，而無需關(guān)心其是否已被加載，代碼如下：

      首先要感謝旗艦工作室的倒掉，讓我可以名正言順的使用FlagshipEngine這個名字，話說這個實驗引擎，當(dāng)初只是我的大學(xué)畢業(yè)設(shè)計，工作之后實在太忙，寫寫停停，進(jìn)度緩慢，到今天也只能算V0.001，其特性主要有以下三點：

一、多線程
      多核CPU早已普及，但3D引擎卻遲遲不能享受到其好處，還僅僅停留在資源異步加載，音頻獨立線程等不疼不癢的應(yīng)用，就在一年前吧，公司的牛人們?yōu)榱藘?yōu)化骨骼動畫和粒子計算煞費苦心，這兩樣計算，特別是在無法控制同屏資源的網(wǎng)絡(luò)游戲中，對CPU資源的占用非常可觀，自然也拖累了游戲幀數(shù)，于是我便有了將邏輯計算與渲染分離的想法。
      FlagshipEngine實現(xiàn)了一套沒有線程同步的雙線程結(jié)構(gòu)，可以做到骨骼動畫、粒子計算、光源移動等邏輯計算分離到一個單獨的線程運行，完全不影響渲染幀數(shù)。

二、shader渲染器
      DX10已經(jīng)放棄了固定管線，那么我們也沒理由再留戀它，完全基于shader的渲染器實現(xiàn)起來更加清晰簡潔，并且易于擴展，目前FlagshipEngine已經(jīng)實現(xiàn)了DX9和DX10兩個渲染器，可以方便的添加特效。

三、統(tǒng)一剪裁
      場景組織和剪裁永遠(yuǎn)是3D引擎的核心功能，視錐、四叉樹、BSP、Portal如何選擇，如何統(tǒng)一是個難題，我的做法是將所有的剪裁都抽象成剪裁面，并用壓棧和出棧的方式，遞歸的對場景進(jìn)行剪裁，另外我們還可以對大塊實體綁定簡單模型的遮擋體，使用邊緣檢測算法生成遮擋剪裁面，實現(xiàn)遮擋剪裁。
      這套機制還沒有經(jīng)過嚴(yán)格的測試，有待進(jìn)一步的驗證。

      就這么多了，希望它有朝一日能修成正果，阿門。。。