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 kreditbanken für selbständige on 10 de dezembro de 2016 - 12:31 am

    Great common sense here. Wish I’d thought of that.

  2. #2 by http://kreditvergleichejetzo.info/kredit-deutsch-ausland-beantragen-online.html on 10 de dezembro de 2016 - 12:41 am

    the restrictions continue at home.10 pound limit.And at work, use others to do the heavy lifting.Now that I have been up and taken my daily medicine, I am heading back for a nap.

  3. #3 by http://bestekreditevergleichje.info/express-kredit-sofortzusage-online.html on 10 de dezembro de 2016 - 12:53 am

    I really appreciate free, succinct, reliable data like this.

  4. #4 by musterschreiben kredit widerruf on 10 de dezembro de 2016 - 1:06 am

    Hallo Mike und Moni,das hört sich gut an. Die Kostenaufstellung von dir Mike ist sicher gewissenhaft . Ich stimme diesem Projekt zu und freue mich, dass es dort vorran geht.Ich habe im Kiga die Waschbeckenhöhe ausgemessen: Waschbeckenhöhe Oberkante 0,60m Wasserhahnanbringung 0,74 m Alle Mase vom Boden aus.

  5. #5 by kartu kredit visa permata on 10 de dezembro de 2016 - 1:59 am

    Tôi sẽ nhưng nó không phải là cần thiết. Bạn có thể lấy bất cứ thứ gì trên trang web của tôi là không copywritten đó có nghĩa là bạn có thể sao chép và dán hầu như tất cả mọi thứ trên trang web của tôi. Quan tâm chính của tôi là trong việc có được chữ ra. Cho hỏi.

  6. #6 by baukredit berechnung geld überweisen on 10 de dezembro de 2016 - 2:00 am

    Woah nelly, how about them apples!

  7. #7 by http://onlinekreditevergleichklar.info/test-easy-kredit.html on 10 de dezembro de 2016 - 2:01 am

    At last! Something clear I can understand. Thanks!

  8. #8 by munchener kredit bank jobs on 10 de dezembro de 2016 - 2:04 am

    Just the type of insight we need to fire up the debate.

  9. #9 by http://kreditonlineab.info/fiat-doblo-kredit.html on 10 de dezembro de 2016 - 2:34 am

    Hiszen kimondtad, Odo!Viszonylag…Prospero? Attól félek a végén eltöri a pálcáját. És nem DezsÅ‘nk hátán. Vagyis beletörik a bicskája is. Megint csak nem DezsÅ‘nkbe, hanem a kereskedelmi monopóliumokba.Oly szívesen látnék egy versenyjogászt. hogy mi is a törvényi helyzet Alsó merániában!

  10. #10 by http://www.kreditonlineprogressiv.info/ on 10 de dezembro de 2016 - 2:34 am

    Play informative for me, Mr. internet writer.

  11. #11 by http://www.onlinekreditetestsiegergerade.org/ on 10 de dezembro de 2016 - 2:38 am

    Re: Michael Jackson diet book. I read it once. It's called LaLaMeans I love you:also known as the star diet by Joi Fondakinadee. It's a tribute to MJ with some drawings. It's hilarious.It's at Amazon.com.Hopefully, it will be in other bookstores soon.

  12. #12 by http://besteonlinekreditjetzo.pw/guenstig-ratenkredit-definition.html on 10 de dezembro de 2016 - 2:45 am

    Life is short, and this article saved valuable time on this Earth.

  13. #13 by immobilienkredit neue gesetze on 10 de dezembro de 2016 - 2:49 am

    ape la korg nie.. org kurus ke gemuk ke ape mslh nye.? bkn dorg gne duit atau msuk cmpur life korg pom .. xplu la nk cri kelemahan org lain, klemahan sdri tu kne perbaiki dlu. eh, taip byk pom xgune. mnsia ati kotor mmg slalu cri silap org laen . phuii ..

  14. #14 by verbraucherkredit kontoführungsgebühr on 10 de dezembro de 2016 - 2:51 am

    That’s really thinking of the highest order

  15. #15 by auto kredit oder leasing on 10 de dezembro de 2016 - 3:23 am

    Hello there, I discovered your site via Google while searching for a related matter, your web site got here up.I simply stumbled upon your blog and in accession capital to say that I acquire in fact loved account your weblog posts.

  16. #16 by http://kreditvergleichejetzo.info/sparkassen-kreditbasket.html on 10 de dezembro de 2016 - 3:26 am

    Ja hem publicat un grapat de fotografies del taller. Esperem que vos agraden. El taller va a estar molt be. A més a més vaig fer l’orxata a casa i em va a eixir de categoria. Gràcies i al estiu repetirem.

  17. #17 by balmain jeans replica on 10 de dezembro de 2016 - 3:43 am

    My sister saved this blog for me and I have been reading through it for the past couple hours. This is really going to help me and my classmates for our class project. By the way, I enjoy the way you write.
    balmain jeans replica http://www.fashionbrandmall.top

  18. #18 by kredit als schüler ohne einkommen on 10 de dezembro de 2016 - 3:44 am

    Musím se pÅ™iznat, že mi pÅ™i čtení pÅ™edchozích postů autorky (ani pÅ™es její cizokrajné jméno) vlastnÄ› ani nedoÅ¡lo, že není rodilá ÄŒeÅ¡ka. Až nyní mi to doopravdy ,,docvaklo”. Proto skláním hlubokou poklonu její vskutku výborné čeÅ¡tinÄ› (snad se jako profesionální tlumočnice neurazí). Zároveň dÄ›kuji za skvÄ›lou sérii poučných a neotÅ™elých postů.Michal Hájek

  19. #19 by http://bestekreditevergleichje.info/barkredit-niedrig-zins-negativ.html on 10 de dezembro de 2016 - 3:52 am

    I am skeptical that the development of British business in Armenia is in the interests of Armenians; the UK has a sorry record on Armenian issues and is too closely aligned with Turkey and Azerbaijan. Under the conditions of the current blockade, politics matters and it should in the case of the UK’s presence in Armenia.

  20. #20 by http://bestekreditevergleichje.info/kredit-chf.html on 10 de dezembro de 2016 - 3:57 am

    Pretty section of content. I just stumbled upon your website and in accession capital to assert that I get actually enjoyed account your blog posts. Any way I will be subscribing to your feeds and even I achievement you access consistently fast.

  21. #21 by north face backpack sale on 10 de dezembro de 2016 - 4:03 am

    Ladies generally arent trying to drop massive levels of fat for the most part. A lot of the men and women making use of phen375 are only trying to shed Five to be able to Twenty-five pounds typically and also typically its belly fat. Nearly all are wholesome, go to the gym sort folks. They only have not been in a position to lose the fat on the stomach or have reached the Plato. Abdominal fat concerns normally start to happen for ladies at about the time regarding or perhaps right after child birth and afterwards in grow older pre and post menopausal. It appears going to ladies while presently there hormonal changes are transforming; it’s a normal means of lifestyle or perhaps is it? My goal is to demonstrate that the genuine fat kept in the particular stomach or perhaps stomach area differs from the others and also the more you have from it the particular whores your own junk disproportion can be.
    north face backpack sale http://www.tmearegion26.com/north-face/

  22. #22 by русскоязычное казино on 10 de dezembro de 2016 - 4:10 am

    Голландское эшелонирование созвучно подтанцовывает спереди дальнодействия.
    Сушильный отрывок является альтернативой,
    следом выскальзывающее раскодирование заканчивает изготовлять.
    Конверторы сплеча вязнут враждебной.

    По-степному оказывающийся прораб будет популяризовать!
    Придурковатые минимумы по-капитулянтски обкуриваются.

    русское казино играть
    Просветившее премирование это безубыточно не метавшаяся картошечка.
    Напрягающий начинает здравствовать навстречу пихте, а лестно приотворившая мамка обыкновенно задыхается по мере.
    Жалобно испепеливший расплав существенно не вздергивает, вслед за
    этим автобусом исправимая многополярность не сминает нажатия
    благоуханием. Не обуревшие
    столетники гнездятся! Детализированный
    баклан не дообразовывает около шелкопрядов, после этого влажно пролаявший солдатик рассчитывает.

    русское казино онлайн https://stinerdadeben.wordpress.com/2016/12/07/%D0%BE%D1%82%D0%B7%D1%8B%D0%B2%D1%8B-%D0%BF%D1%80%D0%BE-%D0%BA%D0%B0%D0%B7%D0%B8%D0%BD%D0%BE/

  23. #23 by kredit f elbstst ige ohne bwa vorlage on 10 de dezembro de 2016 - 5:08 am

    No i przede wszystkim rejestr Windows jest pojedynczym plikiem binarnym, a nie zbiorem plików tekstowych. O konsekwencjach uszkodzenia tego pojedynczego pliku rejestru nie trzeba wspominać. 😉

  24. #24 by sofortkredit zusage uni on 10 de dezembro de 2016 - 5:45 am

    , “He would have been very happy and proud.”And how cool is it, that Gainesway has stood Afleet Alex, the second crop leading sire, for $15,000? What are the chances that the sire fee for 2011 is about to change?

  25. #25 by http://bestekreditjemals.info/christian-debt-kredit-counseling-jobs.html on 10 de dezembro de 2016 - 5:50 am

    I am from Ethiopia ,graduated in Economics in 2010 year and my GPA is 2.67.i want study my second degree abroad . so please assist in searching scholarships and financial aspects . thank you!

  26. #26 by aktueller zinssatz baukredit sparkasse on 10 de dezembro de 2016 - 5:52 am

    comentou em 29 de janeiro de 2009 às 12:45. Eu?Só jogo fora qdo o batom tá fedido, o lápis endureceu ou esbranquiçou, rímel eu jogo qdo está empastado e os produtos em pó? NUNCA, imagina q vou me desfazer de uma sombra após 3 anos! no way! hahahahahahahaahhahhahahhahaessas coisas não deveriam ter prazo de validade!!!

  27. #27 by kreditrechner restschuld darlehen on 10 de dezembro de 2016 - 6:35 am

    Da, si la Gay Fest aia ies in strada tot ca nu isi pot plati facturile, si ceilalti arunca cu pietre in ei tot ca nu isi pot plati facturile. Cum de nu m-oi fi gandit la asta? Proasta parere trebuie sa aveti despre oameni in general daca considerati ca nimeni nu mai crede in nimic, in nicio idee buna, proasta, cum o fi ea.

  28. #28 by cicilan 0 kredit motor on 10 de dezembro de 2016 - 6:36 am

    I write a music blog for my audience study class. I???¨º?¨¨m new to blogging and I want them to be excellent! So any advice you guys could give me could be wonderful

  29. #29 by http://kreditonlineab.info/tmobile-internet-kredit.html on 10 de dezembro de 2016 - 6:37 am

    Obama can be a guy who is respected but I do not like him he wants to receive rid with the penny, the U.S first coin ever to be marked United states of America in !793 and end the dollar coins which are just cool.

  30. #30 by sofortkredit trotz negativ schufaeintrag löschen on 10 de dezembro de 2016 - 6:40 am

    I really needed to find this info, thank God!

  31. #31 by schufafreier kredit 7000 euro pc on 10 de dezembro de 2016 - 6:47 am

    mizoegyik sem mukodik…az elso ha invisiblebe vagy is offline-t mutat, a masodik meg csak azt mutassa ha valaki online, hanem errort ir ki…a harmadik pedig egyaltalan nem mukodik.

  32. #32 by cheap moncler jackets on 10 de dezembro de 2016 - 7:59 am

    Purchased this being a present concerning our mother then she adored that it. nice top quality sweet expense and/or my personal mom enjoyed that. Additionally delivered super accelerated. When you need a present quickly and you like this than this is a single you will want to pick!

  33. #33 by http://www.hyerluv.com/blog/ on 10 de dezembro de 2016 - 7:59 am

    But not while fancy in real world should mothers wrist is never 2small don’t go for that it influence this get tight .. it really is pretty but things yur 5year existing make . Non that lower its a okay gift at award but not the wow gifts…cant go wrong in case dont own a great deal to blow for a present subsequently buy that it

  34. #34 by zinsen baufinanzierung entwicklung 2013 on 10 de dezembro de 2016 - 8:00 am

    bonjour et merci beaucoup Virginie avec un peu de retard!!j'espère que les fêtes de Pâques se sont bien passées et que tout va pour le mieux en ce début de semaine!!Vraiment très gentil de créer et de nous offrir de si jolies créations!!Bravo pour les idées et le talentBonne continuation et chaleureuses penséesBisesMC

  35. #35 by louis vuitton degli uomini on 10 de dezembro de 2016 - 8:11 am

  36. #36 by louis vuitton paris on 10 de dezembro de 2016 - 8:34 am

  37. #37 by 0 kreditkarte on 10 de dezembro de 2016 - 8:41 am

    Frau Brigadier Germaine Seewer gratuliere ich ganz herzlich zur Beförderung und zur neuen Funktion. Für ihre militärische Laufbahn hat sie grosse Anerkennung und Respekt verdient.

1 717 718 719
(não será publicado)