Implementing a Render Queue for Games


Rendering a complex scenes is far from a straightforward task. In a world with Directx 11 multithreading, multicores CPUs, lots of multipass techniques, agressive culling, lots of GPU state transitions …. it is not simple to design a render that handles well all of those requirements. This article will show how to implement a simple strategy that tries to fulfill in a fashion way all of these needs.

Render Queue is just a regular queue that contains “Commands” (instructions to control the rendering) that will be processed by the CPU/GPU. Those “Commands” need to be processed in a ordered way (but they are probably generated  by different threads at different times).

Example of Commands are:

  • Clear the Screen
  • Create a Render Target and set it active
  • Draw a model
  • Set the BlenderState of the GPU (for example to perform alpha blending)
  • ….
The implementation of the Render Queue i propose (the classical one) is very simple, all your commands have an ID (an 64 bits integer for example) that is composed by small of parts. (by bitwise operations)
Each frame, each “System” generates lots of commands to draw the scene and put then in a queue. Then a second process goes and SORT the queue by the commands ID. Finally the ordered queue is processed.
Sumarizing:
  • Commands are generated when the scene is processed
  • Commands are then sorted by their ID
  • Commands are processed in order by a render component

The id of the Command is the smartest point of the idea. It let the systems processing the scene to be able to control the order of the execution of the commands without knowing everything else.

The following image contains the components of the ID (a possible choice, you design this to accommodate your needs)  

Elements Description: (Original idea here ) — to being consider that Commands are elements that need to be draw (models, text, billboards …)

  • Fullscreen layer. Are we drawing to the game layer, a fullscreen effect layer, or the HUD?
  • Viewport. There could be multiple viewports for e.g. multiplayer splitscreen, for mirrors or portals in the scene, etc.
  • Viewport layer. Each viewport could have their own skybox layer, world layer, effects layer, HUD layer.
  • Translucency. Typically we want to sort opaque geometry and normal, additive, and subtractive translucent geometry into separate groups.
  • Depth sorting. We want to sort translucent geometry back-to-front for proper draw ordering and perhaps opaque geometry front-to-back to aid z-culling.
  • Material. We want to sort by material to minimize state settings (textures, shaders, constants). A material might have multiple passes.

An Example makes everything clear: lets see how to implement Alpha Blending with render queue — as we know, we have to draw the full opaque scene first, then we activate the alpha blending state and draw the transparent objects on the top of the scene

  • The transparent objects will have the translucency bits of the ID set to 11 (integer 3) and the normal objects will have these bits set to 00
  • When we sort commands (by the ids) and draw the render queue in sequence, all the normal objects will be draw first ….

Okay, this is a dumb example, but show the idea … (Encode your draw call in Commands, and let the ID decide the order of drawing)

The next level is to include Graphics Commands (like clear the screen) inside the ID, so we can sort them also.

The following image shows a more powerfull ID design:

(The command Bit should be the less significative bit — the one in the most right)
Here we also included a bit to tell if a Command is a graphical instruction (clear the screen) or is an object to be draw (like before)

With this layout we can implement for example shadow/reflection/post effects ….:
Example:

  • Pull the Render Target RT – A command with Command Bit Set
  • Draw Object X,Y,Z,W – same as before
  • Pull Render Target RT2 – A command with Command Bit Set
  • Draw all objects (some might be using the Render Traget RT as a texture — for shadow/reflection effect for example)
  • Do some post processing …. – COllection of Commands
  • Draw some text overlay
As you can see this technique is very powerfull and is commonly used in games.
If you are using C++ you can encode a function pointer in the ID and call it during the rendering (similar idea can be done in C#, JAVA ….)
The following part shows how to implement this idea (the first one, without the graphics instruction part …. — adding it is left to the readers as an exercise =P)
Used C#, but the idea is the same in all languages ….
This code is DUMMMY, just to show a concept ….

Render Queue Id Definition:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace EngineTestes.RQueue
{
    public class RenderQueueId
    {
        public override string ToString()
        {
            return Convert.ToString(id, 2);
        }

        /*
         * 2 Fullscreen layer. Are we drawing to the game layer, a fullscreen effect layer, or the HUD?
           3 Viewport. There could be multiple viewports for e.g. multiplayer splitscreen, for mirrors or portals in the scene, etc.
           3 Viewport layer. Each viewport could have their own skybox layer, world layer, effects layer, HUD layer.
           2 Translucency. Typically we want to sort opaque geometry and normal, additive, and subtractive translucent geometry into separate groups.
           6 Extra
           24 Depth sorting. We want to sort translucent geometry back-to-front for proper draw ordering and perhaps opaque geometry front-to-back to aid z-culling.
           24 Material. We want to sort by material to minimize state settings (textures, shaders, constants). A material might have multiple passes.
         * =64
         * */
        long id;

        public readonly long fullscreenLayer;
        public readonly long viewPort;
        public readonly long viewportLayer;
        public readonly long translucency;
        public readonly long depthSorting;
        public readonly long materialid;
        public readonly long extra;
        bool flipMaterialWithSorting = false;

        public RenderQueueId(int fullscreenLayer, int viewPort, int viewportLayer, int translucency, int extra, int depthSorting, int material)
        {
            this.fullscreenLayer = fullscreenLayer;
            this.viewportLayer = viewportLayer;
            this.viewPort = viewPort;
            this.depthSorting = depthSorting;
            this.materialid = material;
            this.extra = extra;
        }

        public long CachedId
        {
            get
            {
                return id;
            }
        }

        //public long GetMaterialMask()
        //{
        //    if (flipMaterialWithSorting)
        //    {
        //        return (16777215L << 24);
        //    }
        //    else
        //    {
        //        return 16777215L;
        //    }

        //}

        public long GenerateId(bool flipMaterialWithSorting = false)
        {
            this.flipMaterialWithSorting = flipMaterialWithSorting;

            if (flipMaterialWithSorting)
            {
                id = fullscreenLayer << 62
                    | viewPort << 59
                    | viewportLayer << 56
                    | translucency << 54
                    | extra << 48
                    | materialid << 24 
                    | depthSorting 
                    ;
            }
            else
            {
                id = fullscreenLayer << 62
                    | viewPort << 59
                    | viewportLayer << 56
                    | translucency << 54
                    | extra << 48
                    | depthSorting << 34
                    | materialid 
                    ;                
            }
            return id;
        }        
    }
}

The render Queue Element (The Command — DUMMY)

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace EngineTestes.RQueue
{
    public abstract class RenderQueueElement
    {
        public RenderQueueId Id
        {
            get;
            private set;
        }

        public abstract void InitMaterial();
        public abstract void Draw();
        public abstract void EndMaterial();

    }

    public class RenderQueueElementComparer : IComparer
    {

        #region IComparer Members

        public int Compare(RenderQueueElement x, RenderQueueElement y)
        {
            if (x.Id.CachedId > y.Id.CachedId)
            {
                return 1;
            }
            else if (x.Id.CachedId == y.Id.CachedId)
            {
                return 0;
            }
            else
            {
                return -1;
            }
        }
        #endregion
    }

}

The Render Queue Processing (DUMMY DUMMY DUMMY)

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace EngineTestes.RQueue
{
    public class RenderQueueProcessor
    {
        RenderQueueElementComparer renderQueueElementComparer = new RenderQueueElementComparer();
        List elements = new List();

        public void Process()
        {
            if (elements.Count == 0)
                return;

            elements.Sort(renderQueueElementComparer);
            RenderQueueElement last = elements[0];
            last.InitMaterial();
            last.Draw();

            for (int i = 1; i < elements.Count; i++)
            {
                var el = elements[i];
                if (el.Id.materialid != last.Id.materialid)
                {
                    last.EndMaterial();
                    el.InitMaterial();
                }
                el.Draw();
                last = el;
            }
            last.EndMaterial();

            elements.Clear();
        }
    }
}

Remember: Design the ID of the of the Render Queue the best way you can =P, this is the heart of the system =P

Reference:

http://realtimecollisiondetection.net/blog/?p=86

, , ,

  1. #1 by the isle of man government insurance and pensions authority on 1 de outubro de 2016 - 1:33 pm

    Dan…..So many thanks for what you do here on this blog! I am thrilled to read these posts and will definately look into buying this book. I am a ‘teaching-artist’ in the States and have pretty muchdevoted 30+ years to learning about, practicing and teaching others about art-making skills. I found the ten things listed here to be TOTALLY RIGHT-ON!!! Thanks again…. Carolyn

  2. #2 by adidas nmd runner on 1 de outubro de 2016 - 1:46 pm

    Thanks for all your work on this website. My niece really likes making time for investigations and it’s really easy to understand why. All of us know all about the lively mode you render both useful and interesting tactics on your blog and as well as boost participation from others about this article so our own child is truly starting to learn a lot of things. Take advantage of the remaining portion of the new year. You are performing a good job.

  3. #3 by Lån Utan Kreditupplysning on 1 de outubro de 2016 - 2:01 pm

    Realmente estas personas llevaron a un punto extremo sus gustos por los piercings y los tatuajes. A mí me parece que tienen que ser respetados tal cual son por más que tengan como tengan sus cuerpos. En definitiva si alguien se perjudica son ellos mismos y supongo que eran conscientes de eso ala hora de hacerse todas esas modificaciones corporales.

  4. #4 by http://todosossites.site/site/backyardchickens.com on 1 de outubro de 2016 - 2:19 pm

    What on earth is this “Old Mountaineer Field” you discuss of? Did it have pass outs? Could you drop by Bent Willeys at halftime and return mid-third quarter?

  5. #5 by swords for sale on 1 de outubro de 2016 - 2:21 pm

    Love it!! Super Fast shipping! A+++

  6. #6 by wayne gretzky rangers jersey on 1 de outubro de 2016 - 2:22 pm

    Say Goodbye to Backdrop Tone

  7. #7 by health benefits of honey on 1 de outubro de 2016 - 2:41 pm

    although internet sites we backlink to below are considerably not associated to ours, we feel they’re basically really worth a go through, so have a look

  8. #8 by car key insurance cover on 1 de outubro de 2016 - 2:51 pm

    pak knp ya untuk pt perdana karya (PKPK) laporannya tdk ada? maaf sy baru butuh lap.keu dari semua perusahaan disektor tambang yg tdftar di bursa.

  9. #9 by how to find cheap insurance quotes on 1 de outubro de 2016 - 2:52 pm

    That’s an ingenious way of thinking about it.

  10. #10 by volkswagen insurance review on 1 de outubro de 2016 - 2:55 pm

    Your post captures the issue perfectly!

  11. #11 by oakley gloves on 1 de outubro de 2016 - 3:12 pm

    Have you ever considered creating an e-book or guest authoring on other sites? I have a blog based upon on the same information you discuss and would really like to have you share some stories/information. I know my visitors would enjoy your work. If you’re even remotely interested, feel free to shoot me an email.

  12. #12 by coreuta on 1 de outubro de 2016 - 3:22 pm

    「インテグリティ(integrity)」というのは、アメリカ人が人間を評価する場合の非常に重要な概念で、「インテグレート」とは統合す るという意味ですから、直訳すると「人格上の統合性、首尾一貫性」ということになると思います。 ついて行かなくちゃならないのかなぁw 便利って辛いこともあるのね!これからパソコンを購入予定んおある方はOfficeのどのバージョンが入っているか確認してみましょう! ではまた~~   See ya!!!! :D。 [url=http://uzil.com.br/wp-content/wp-content/60919/office2013_1/index.html]office2010[/url]
    DVDコピーMacフリーソフトを使って、無料にMacでDVDをコピーしよう!ここでは、最も評判されているMacX DVD Ripper Mac Free Editionを 使って、無料にMacでDVDをコピーする方法を紹介する。 (ちなみに私のパナソニックのレッツノートは電源入れて、インターネットのスタートページが出るのに20秒程度です。
    [url=http://suneye.in/wp-content/60923/office2013_1/index.html]オフィス 価格[/url] 外部共有がグローバルにオフになっています。 また、デスクトップ、ラップトップ、タブレット、サーバーなどのカスタマー デバイスに展開するためのイメージ全体の作成も担当しています。
    [url=http://kapp-process.com/wp-content/60908/windows10_1/index.html]windows10[/url]
    ex) the French language, a foreign language「言葉遣い」や「(意思疎通のシステムとしての)言語」という時は不可算名詞。 このofは,speaking of, know of, think of などにも見られる, ofをaboutとして使う古い用法である。 [url=http://foolhut.papabiz.com/wp-content/60921/office2013_1/index.html]ms office[/url]
    ですから、君はうちの学習教材を安心で使って、きみの認定試験に合格することを保証します。  OSの入っているHDDのクローンソフトを使うしかないが、検索がおかしく同じソフトばかり出てきて探しずらい。
    [url=http://foolhut.papabiz.com/wp-content/60921/office2013_1/index.html]office2010 価格[/url] これ以上、株の損切り するんも、たいぎぃい  でぇええ~。 >> 70-347日本語 合格 詳しい紹介はこちらXHS1991.COMにIT業界のエリートのグループがあって、彼達は自分の経験と専門知識を使ってMicrosoft 70-347日本語試験感想に参加する方に対して問題集を研究続けています。
    [url=http://suneye.in/wp-content/60923/office2013_1/index.html]office 価格[/url]

  13. #13 by cheap health insurance for single moms on 1 de outubro de 2016 - 3:28 pm

    Sorry for the huge review, but I’m really loving the new Zune, and hope this, as well as the excellent reviews some other people have written, will help you decide if it’s the right choice for you.

  14. #14 by tc auto insurance on 1 de outubro de 2016 - 3:34 pm

    pretty sure James is referring to me. “You will have to learn to deal with seeing someone everyday who is more important than you and has better trainers”My trainers rock. (And I’m a planner).Chortle.

  15. #15 by http://carinsurancemega.top/ohio-car-insurance-requirements.html on 1 de outubro de 2016 - 3:39 pm

    it’s better for the defense than it is for the prosecution.WFTV has learned that the medical examiner found two injuries on Martin’s body: The fatal gunshot wound and broken skin on his knuckles.I love how all of this evidence is playing out exactly how GZ described the attack minutes after the shooting. No_Limit_Nigga probably got what was coming to him.

  16. #16 by nike outlet uk on 1 de outubro de 2016 - 3:51 pm

    Can not! Zhao Yundao: if the other party is trying to kill the employer, the employer would have been lying dead.

  17. #17 by nike outlet uk on 1 de outubro de 2016 - 3:51 pm

    The Dong Ruoran people are ignorant, not from the opposite of their expected situation react. He looked at Dong how she does not want to go off in a huff, understand where the hell is wrong……

  18. #18 by real japanese katana on 1 de outubro de 2016 - 3:53 pm

    Very fast shipping/delivery! Love it. Thank you!

  19. #20 by where to buy real katana on 1 de outubro de 2016 - 4:14 pm

    Grand vendeur . Expédition rapide aussi!

  20. #21 by http://cheapcarinsuranceqws.info/ybs-car-insurance.html on 1 de outubro de 2016 - 4:14 pm

    Thought it wouldn’t to give it a shot. I was right.

  21. #22 by ninja katana on 1 de outubro de 2016 - 4:15 pm

    Transaction étonnamment rapide et facile. Grand vendeur ! !

  22. #23 by Tsuka on 1 de outubro de 2016 - 4:26 pm

    Excellent Seller – Beautiful Item – I’m absolutely thrilled! Thank you so much!

  23. #24 by occhiali oakley motogp on 1 de outubro de 2016 - 4:28 pm

    My brother suggested I might like this blog. He was entirely right. This post truly made my day. You can not imagine simply how much time I had spent for this information! Thanks!

  24. #25 by how much does contents insurance cost on 1 de outubro de 2016 - 4:39 pm

    “Die nächsten Folgen kommen dann aus fernen Ländern. Freut Euch drauf.”Ach Du Schreck! Fette Rotwein-Brummer und Hochpreisklopper aus Swartland!

  25. #26 by dairyland auto insurance of wisconsin on 1 de outubro de 2016 - 4:41 pm

    Nøj, tak for ta(e)sken.. Guderne skal vide at der nok ligger en gammel læbepomade eller 2 rundt omkring i taskerne. Vil fluks tjekke lugt og evt holbarhed.

  26. #27 by http://carinsurancemega.top/low-cost-auto-insurance-lancaster-ca.html on 1 de outubro de 2016 - 5:23 pm

    I appreciate you taking to time to contribute That’s very helpful.

  27. #28 by penalty for no car insurance in pa on 1 de outubro de 2016 - 5:29 pm

    These are great examples of holding pages. I think it’s useful to have an enquiry field or newsletter sign up to encourage people to come back and visit your new website. I really like how some of these holding pages have included JQuery animation effects, and shows that the designer/developer has taken the time to make the page and not just shove the logo and email address on them. My favourites are NoinColor and Irava.

1 487 488 489
(não será publicado)