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 Cheap Football Jerseys on 16 de julho de 2017 - 11:07 pm

    Actually ladies go to hair salon to wear UV gels to obtain a professional feel, but not just about all salons give you the best service, so you have to learn the right one.Remember that the whole procedure will be composed of small processes. Coal, natural gas and other clean ways to produce energy will not be around for forever. You could now lay the FTSE up at 1. What most fans would like to know is this: what are the not-so-impressive franchises doing to improve their teams for this upcoming season?The 2007 draft secured many new star athletes and the trades will surely improve the quality of many second-rate teams.
    Cheap Football Jerseys https://www.wholesalejerseysfive.com/

  2. #2 by Moncler Outlet on 16 de julho de 2017 - 11:28 pm

    I’ve purchased this particular brand concerning bracelet a number of days. Every single one is very adorable, has made very well, does not tarnish then significant depending on that one particular you purchase and just who a person offer information technology at.

  3. #3 by agen qq on 16 de julho de 2017 - 11:41 pm

    Awesome post. I am a normal visitor of your site and appreciate you taking the time to maintain the excellent site. I will be a frequent visitor for a long time.

  4. #4 by hermes bracelet replica on 17 de julho de 2017 - 2:13 am

    Your goods ended up being in that awesome price tag I not thought your quality would be quite excellent. It is stunning. The mama might adore it on top of Christmas morning where she opens up gift therefore appears as though I spent a lot more, and yet rates had been really very good!!

  5. #5 by nike on 17 de julho de 2017 - 2:13 am

  6. #6 by casino online on 17 de julho de 2017 - 2:13 am

    Hiya, I am really glad I’ve found this information. Nowadays bloggers publish only about gossip and internet stuff and this is actually frustrating. A good website with interesting content, that is what I need. Thanks for making this web site, and I will be visiting again. Do you do newsletters by email?

  7. #7 by cartier love bracelet replica on 17 de julho de 2017 - 2:13 am

    We have purchased this particular brand name to bracelet a few days. Every one is very attractive, prepared very well, cannot tarnish as well as significant depending on that one you purchase plus that your render they and.

  8. #8 by togel singapura on 17 de julho de 2017 - 2:18 am

    Awesome write-up. I am a regular visitor of your blog and appreciate you taking the time to maintain the excellent site. I will be a frequent visitor for a really long time.

  9. #9 by Wholesale Jerseys Cheap on 17 de julho de 2017 - 3:46 am

    Now the Betfair prices will be more generous than all the bookmakers’ prices, but you want to find prices that are significantly higher than these prices, that will come in other time so you can trade out. J. Therefore, if you are in an old house whose electrical system is out of order, consider hiring these technicians. The combination should make for huge improvements for this franchise. To begin with, it’s the most ideal materials to keep your feet warm, plus with the ability to keep them cool when the weather is hot.
    Wholesale Jerseys Cheap http://www.cheapjerseysnflchinaonline.com/

  10. #10 by UK Christian Louboutin Replica on 17 de julho de 2017 - 4:05 am

    This one product or service is at that great price I never believe on premium would be therefore excellent. It’s stunning. It mama will certainly really like that it at Xmas morning once she opens up gifts therefore appearances like I spent much more, but prices ended up being exclusively very good!!

  11. #11 by tempat wisata malaysia on 17 de julho de 2017 - 4:12 am

    Hiya, I’m really glad I have found this information. Today bloggers publish only about gossip and internet stuff and this is actually frustrating. A good web site with interesting content, this is what I need. Thank you for making this web site, and I’ll be visiting again. Do you do newsletters by email?

  12. #12 by domino 99 on 17 de julho de 2017 - 4:30 am

    Hello there. I found your website via Google while searching for a comparable subject, your website got here up. It seems to be great. I’ve bookmarked it in my google bookmarks to come back then.

  13. #13 by canada goose outlet online on 17 de julho de 2017 - 4:34 am

    I had this article bookmarked a while ago but my PC crashed. I have since gotten a new one and it took me a while to locate this! I also in fact like the design though.
    canada goose outlet online http://www.canadagooose.store

  14. #14 by cat fails on 17 de julho de 2017 - 4:40 am

    I really enjoy reading on this internet site, it holds fantastic blog posts.

  15. #15 by guexynb on 17 de julho de 2017 - 5:08 am

    普通の人の場合は、5年から10年はスキルを習得するために使うのが成功への道でしょう。 アヤフアスカを飲むことで、他の従来の治療法では対処することができなかったトラウマを克服することができると大勢が語っている。 [url=http://wpandassociates.com/tui/putter_1/index.html]スコッティキャメロン ニューポート2 sss[/url]
    これで合ってる?予告編にも出てきたWi-Fiパスワードの「shamballa」。 だから  どんな人生も すべて 正解よ!  転がって 転がって どこにも たどりつけず なにものにもなれず、 失敗を多々重ね、  迷い、彷徨い 大事なこと 忘れないと誓ったこと 忘れ、変わってゆく人間。
    [url=http://eaglexcape.co.za/ping/g30_1/index.html]ピン g30 ls[/url] 下が緩くてランはでませんでしたが、距離も方向性もまずまず。 そのあと千葉県千葉市へ行き、千葉県俳句作家協会を取材した。
    [url=http://arrahn.com.my/llway/xhot_1/index.html]x hot ドライバー[/url]
    ▼翁長氏は安倍晋三首相との会談も要請しているが政府内には「また同じ話をするのなら会う意味はない」と否定的な声もあり、沖縄県民とりもアメリア重視してるのです。 名前はグラスとスティーガルという提案議員からとった。 [url=http://45grados.com.mx/quote/xxio8_1/index.html]ゼクシオ8アイアン[/url]
     短いティも予備で有った方が良いと思いセットのを購入。 そこで日本の三浦技研に依頼してタイガー用のマッスルバックアイアンをプロトタイプとして作ることになる。
    [url=http://kmpomerania.com/urban/mp4_1/index.html]ミズノ mp-4h[/url] 7月10日(木)  (会場)旭ゴルフガーデン  9:00~15:00  マルマン  マジェスティ・コンダクター・メガ・シャトルエース           詳細がわり次第、改めてアップします!。 ビートルズ世代の我々にとっては、涙なしに見られない懐かしい映像に満ちた、永久保存とすべきロン・ハワードからの贈り物である。
    [url=http://www.centrodemateriales.com.py/sldr/iron_1/index.html]テーラーメイド SLDR アイアン[/url]

  16. #16 by Wholesale Jerseys China on 17 de julho de 2017 - 5:18 am

    To those who camp, this should serve as mats that keep dirt away from tents.After you’re functioning on improving your money, generating tiny adjustments can produce a huge difference.Okay, so what are you going to do if you are not in a full-time ballet school with 10 +classes a week? You may be rushing from class to a bus stop, or being driven home to finish your home work. This doesn’t mean that you carry every endorsement that is available on a policy, but you should have certain coverage limits that you don’t skimp on. http:Twins Looking At Floyd Capuano – RealGM WiretapThe Minnesota Twins are looking for a starting pitcher and they have interest in Gavin Floyd and Chris Capuano.
    Wholesale Jerseys China

  17. #17 by chanel outlet online on 17 de julho de 2017 - 5:36 am

    You really make it appear so easy with your presentation however I find this topic to be really one thing that I think I would by no means understand. It sort of feels too complicated and very broad for me. Im taking a look ahead for your subsequent put up, I will attempt to get the grasp of it!
    chanel outlet online

  18. #18 by togel online on 17 de julho de 2017 - 6:44 am

    Awesome post. I’m a regular visitor of your blog and appreciate you taking the time to maintain the excellent site. I will be a regular visitor for a long time.

  19. #19 by http://www.rockma.se/hermes.asp on 17 de julho de 2017 - 6:51 am

    We have purchased it brand concerning bracelet some days. Every one is very attractive, done well, does not tarnish as well as important based on that an you purchase to that shoppers give it and.

  20. #20 by cartier love bracelet replica on 17 de julho de 2017 - 6:51 am

    This one device was in that ideal price tag I by no means consideration that quality is therefore excellent. It’s beautiful. The mother will enjoy that it on top of Christmas time day where she opens up gift and it appears as though I invested even more, then again prices is exclusively awesome!!

  21. #21 by Cheap NFL Jerseys on 17 de julho de 2017 - 6:58 am

    There’s a couple of things that you need to take a look at when trying to wade through these possibilities. For many people, tennis is merely a physical sport.Read more about How To Do Carpet Recycling Properly.Read more about How To Do Carpet Recycling Properly.Stay clear of trading opportunities which have ever increasing charges attached.
    Cheap NFL Jerseys

  22. #22 by louis vuitton usa store on 17 de julho de 2017 - 7:24 am

    Have you considered adding some videos to the article? I think it will really enhance viewers understanding.
    louis vuitton usa store

  23. #23 by cheap nike roshe run on 17 de julho de 2017 - 7:30 am

    I have purchased this particular brand name of bracelet some circumstances. Every single one is extremely adorable, made very well, cannot tarnish then important depending on what someone you buy furthermore whom one promote things at.

  24. #24 by http://www.cheapmoncler.xyz/ on 17 de julho de 2017 - 7:43 am

    We have purchased this brand concerning bracelet a number of instances. Every single one is extremely adorable, made well, cannot tarnish and also significant based on that an individual you purchase additionally that one offer that at.

  25. #25 by Dorislom on 17 de julho de 2017 - 7:44 am

    Absolutely NEW update of SEO/SMM package “XRumer 16.0 + XEvil”:
    captchas recognition of Google, Facebook, Bing, Hotmail, SolveMedia, Yandex,
    and more than 8400 another categories of captchas,
    with highest precision (80..100%) and highest speed (100 img per second).
    You can connect XEvil 3.0 to all most popular SEO/SMM software: XRumer, GSA SER, ZennoPoster, Srapebox, Senuke, and more than 100 of other programms.

    Interested? You can find a lot of demo videos about XEvil in YouTube.
    Good luck!

    XRumer201707

  26. #26 by cats on 17 de julho de 2017 - 8:16 am

    Glad to be one of many visitors on this awesome website : D.

  27. #27 by http://www.ljusihus.se/moncleroutlet.aspx on 17 de julho de 2017 - 8:42 am

    We have purchased the brand name concerning bracelet a number of days. Every single one is very pretty, made very well, does not tarnish to significant based on that 1 you buy additionally just who people offer that it to.

  28. #28 by https://Hediyetarzi.com/2017/07/10/a-appropriate-internet-dating-sites-the-problem-of-4 on 17 de julho de 2017 - 9:03 am

    Whereas along with you, you constantly concern yourself with it and yes it
    usually transpires with you. Sixth, every time a guy shows fascination with you,
    he’ll begin a conversation with you while requesting your business and
    speak to too. But truth to get told, that is one of many hardest place to
    accomplish that because usually they’re betting that that which you are attempting to do and possess their guard up.

  29. #29 by Adam Oates Jersey on 17 de julho de 2017 - 9:05 am

    Supply all the necessary details and send it back to the department. Ive helped reset their brains to a neutral state thats betterequipped to learn about continuously compounding interest. is a certified teacher and learning specialist and is the author Jhonny Peralta Has Surgery Out Until MidseasonRealGM WiretapJhonny Peralta underwent surgery to repair a torn ligament in his left thumb Thursday morning and will be out until midseason, according to the St. I don’t even want to go and buy the stuff I do need. To be on the safe side, it is important that you do this after the cold season ends.

  30. #30 by Wholesale NFL Jerseys China on 17 de julho de 2017 - 9:07 am

    We’ll get back to this in the next article.The second position split should be opened as far as you can go WITHOUT pain. They should consider doing proper carpet recycling California. These guidelines will help you stay at your look at your self as well as how other people watch you!A particular enterprise bank account will assist you to keep exact information for your personal company’s monetary transactions. Let the back leg bend, and focus on the front leg.
    Wholesale NFL Jerseys China

  31. #31 by judi casino on 17 de julho de 2017 - 9:16 am

    Hey there. I discovered your website by means of Google whilst looking for a similar topic, your site came up. It seems good. I have bookmarked it in my google bookmarks to come back then.

  32. #32 by بهترین سالن زیبایی تیکا اهواز on 17 de julho de 2017 - 10:03 am

    check below, are some absolutely unrelated websites to ours, however, they’re most trustworthy sources that we use

  33. #33 by true religion outlet store on 17 de julho de 2017 - 10:10 am

    Notable web blog, Distinguished comments that I can tackle. I am moving ahead and can apply to my current job as a cat sitter, which is very enjoyable, however I must additional expand. Regards
    true religion outlet store

  34. #34 by http://www.medicareagentfinder.com/wp-bridal.php on 17 de julho de 2017 - 10:14 am

    This goods is at such a very good price tag I never ever thought all high quality is so excellent. It is striking. It mama does like things in Christmas time day when she opens present therefore styles like I invested more, then again rates is really awesome!!

  35. #35 by hermes h bracelet replica on 17 de julho de 2017 - 10:15 am

    We have bought this brand name out of bracelet a number of instances. Every single a person is extremely adorable, manufactured well, cannot tarnish and/or important based on which kind of any you purchase furthermore that we provide that it towards.

  36. #36 by try this website on 17 de julho de 2017 - 10:30 am

    here are some links to web pages that we link to simply because we feel they’re really worth visiting

  37. #37 by check it out on 17 de julho de 2017 - 10:53 am

    Every the moment in a although we opt for blogs that we study. Listed beneath would be the most up-to-date internet sites that we select

  38. #38 by next page on 17 de julho de 2017 - 10:56 am

    here are some links to sites that we link to mainly because we assume they’re really worth visiting

  39. #39 by barbour for sale on 17 de julho de 2017 - 11:11 am

    Depending on yourself to make the decisions can really be upsetting and frustrating. It can take many people a long time to build a strong moral system. It doesnt really just happen if you know what I mean.
    barbour for sale

(não será publicado)