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

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

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

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


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

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

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

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

      最后是我的解決方案

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

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

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

    也就是加這么兩個(gè)簡(jiǎn)單的set和get方法，在渲染相關(guān)數(shù)據(jù)讀取時(shí)調(diào)用get，邏輯相關(guān)時(shí)調(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的最后一點(diǎn)點(diǎn)沒(méi)解壓開(kāi)，沒(méi)什么大礙。
    本來(lái)只是以為自己只是火星了而已，裝好一看，完。。。徹底冥王星了，DX11的Preview版出了！真是又激動(dòng)又懊悔，粗略看了看，新特性真是太令人激動(dòng)了，主要有以下幾點(diǎn)：

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

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

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

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

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

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.

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

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

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

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

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

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

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

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

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

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

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