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 utah state insurance license lookup on 28 de maio de 2017 - 3:53 am

    Stay informative, San Diego, yeah boy!

  2. #2 by http://news.cartierbraceletsreplica.win/cartierbraceletsreplicawin/588.asp on 28 de maio de 2017 - 3:58 am

    But not as fancy as part of real world provided moms wrist is actually never 2small do not pick that cause they be tight .. its attractive but things yur 5year old can make . No all lower it really is one okay gift towards offer but not one wow gifts…cant go wrong if you think don’t come with much to blow on a gifts then have that

  3. #3 by http://klipplust.se/images/slide/old/73.html on 28 de maio de 2017 - 3:58 am

    Yet not because fancy in real life provided mothers wrist is not really 2small dont purchase things influence things stay tight .. their attractive although some thing yur 5year old can make . No that less its a ok gifts towards promote yet not the wow gifts…cant get wrong provided do not need much to spend for a gift after that get things

  4. #4 by http://news.panchro.xyz/panchroxyz/485.asp on 28 de maio de 2017 - 3:59 am

    Yet not just as fancy as part of real world provided moms wrist was not really 2small don’t get that it trigger they be tight .. its cute however one thing yur 5year existing makes . Non the actual much less the a ok present on offer yet not a wow present…cant get wrong if dont posses far to spend for a gift then become that

  5. #5 by Cheap Jerseys Free Shipping on 28 de maio de 2017 - 4:00 am

    Whenever you dropship the products to the shoppers you can get several advantages like you don’t possess to deal with inventory, there is no need associated with an investment before time, there is no need of dealing with shipping, returns, receiving, and inventory rotations. Jennings did the same thing when he faced Morrow in the second inning to give him his first twohome run game in the Rays’ 120 win.The righthander threw a 27pitch bullpen session in Port St.Create a huntsy profile.For the record, I’ve never been bankrupt, never committed a felony (or even a misdemeanor) never accepted kickbacks, consistently voted in local and national elections, always worked at least one job (often 23) have an exceptional FICO score, great employment history, and haven’t cheated employees or family members.
    Cheap Jerseys Free Shipping http://www.cheapsportjerseysnfl.us.com/

  6. #6 by Cheap Wholesale Jerseys on 28 de maio de 2017 - 4:03 am

    1 Virginia s potent offense. Even the military is weighted down with ineffectiveness these days, rendering our very national security more vulnerable.The most likely population to suffer concussions due to sports activities are males between the ages of 16 and 25. 3, 1990: Tech 41, Virginia 38. The only way out is to choose smaller strata title property.
    Cheap Wholesale Jerseys http://www.cheapjerseysdiscount.us.com/

  7. #7 by http://www.t-bygg.com/upload/519.html on 28 de maio de 2017 - 4:03 am

    I have this headphonesfor the my personal mother concerning mothers day, and also she definitely adored that it! Its completely sweet headphonesand the saying regarding the card in which will come in package is really emotional!! And excellent of beads was ideal!

  8. #8 by http://christlutherancemetery.com/headstones/page/89.html on 28 de maio de 2017 - 4:04 am

    I had gotten it headphonesof the mother to parents time, as well as she absolutely liked it! Their truly adorable headphonesas well as the suggesting on the card your will come in box is very sentimental!! And the high quality of beads are ideal!

  9. #9 by http://news.christianlouboutinreplica.win/christianlouboutinreplicawin/592.asp on 28 de maio de 2017 - 4:36 am

    The boy gave myself it to mothers day. He realizes im not around price tag however just what comes from ones center. I cannot think it has the favorite color to really matches the wrist. I never might see bracelets to suit headphonesmy personal mini wrist. Quite happy to has recieved the as a gift.

  10. #10 by http://www.silvercode.com/misc/file/485.html on 28 de maio de 2017 - 4:37 am

    My son provided myself this to mothers day. He understands im never regarding price however just what comes from ones heart. I can’t think it has my favourite color and also truly matches the wrist. I do not might look for bracelets to suit headphonesmy personal slight wrist. Most happy to own recieved your being a gift.

  11. #11 by driving in bad weather on 28 de maio de 2017 - 4:55 am

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

  12. #12 by do i need car insurance in usa on 28 de maio de 2017 - 5:00 am

    Never seen a better post! ICOCBW

  13. #13 by http://news.vancleefreplica.top/vancleefreplicatop/504.asp on 28 de maio de 2017 - 5:11 am

    Yet not since fancy inside real world if you think mothers wrist is maybe not 2small do not choose that result they try to be tight .. their attractive then again one thing yur 5year aged can make . No ones reduced their one ok gift towards award yet not the wow present…cant go wrong whether dont posses a lot to spend for a gift therefore find things

  14. #14 by car insurance decatur al on 28 de maio de 2017 - 5:21 am

    Holy shiznit, this is so cool thank you.

  15. #15 by average apartment insurance cost on 28 de maio de 2017 - 6:31 am

    I need to retire pronto, but must note a sadly mistaken clue in the CS at 26A — Bizet’s “hit of 1875″ first performed at the Opéra-Comique in Paris, on 3 March 1875, and was not at first particularly successful; its initial run extended to 36 performances. Bizet was convinced that the work was a failure, and he died of a heart attack three months later, unaware that it would prove a spectacular and enduring success.

  16. #16 by Cheap Jerseys on 28 de maio de 2017 - 6:54 am

    Even though there are many benefits of making this kind of investment, you should expect a few challenges too. When RCA, or the radio Corporation of Usa, obtained the Victor Talking Machine Company in 1929, music as identified presently, was started. Not to mention its fragrance that entices your sense of smell, its robust taste confirmed by your sense of taste as you take your very first sip of it. Each person in your business should be responsible for their own specific task for which they will be help responsible if it goes wrong. Exactly why? Because the earth’s population battles with all the consequences of unhealthy diet plans, sedentary lifestyle, cigarette smoking and a lot more.

  17. #17 by loan lease payoff insurance on 28 de maio de 2017 - 6:56 am

    You make things so clear. Thanks for taking the time!

  18. #18 by pusat plakat on 28 de maio de 2017 - 7:01 am

    Awesome write-up. I’m a normal visitor of your website and appreciate you taking the time to maintain the excellent site. I’ll be a frequent visitor for a long time.

  19. #19 by auto insurance comparison between states on 28 de maio de 2017 - 7:14 am

    I’m so glad that the internet allows free info like this!

  20. #20 by affirmative insurance online payment on 28 de maio de 2017 - 7:20 am

    Dis is a country dat always pretend to be d giant of Africa.Nigeria has in many occation played a crucial roles in makin sure dat other africa nations experience peace.Despite d sarcrifice we ‘ve made in some Africa countries,we dont seem to be appriciated in Africa continent. Dis is a continent where a seat in security council at UNO was seriously contested against Nigeria that has bn sarcrificing her resources in enssuring dat Africa experience peace.I think Nigerian needs to wise up nd……….

  21. #21 by http://news.louboutinheels.xyz/louboutinheelsxyz/119.asp on 28 de maio de 2017 - 7:58 am

    I got your headphonesto my mom for the parents day, and also she absolutely adored that! Their quite adorable headphonesand stating on the card that comes inside container is really emotional!! And the high quality of the beads is ideal!

  22. #22 by cheap louboutin shoes replica on 28 de maio de 2017 - 8:03 am

    it comes in a beautiful box appearance very good then again it really is a bit limited consistent for the my moms wrist however it appearances very good really want that it was extended

  23. #23 by siehe hier on 28 de maio de 2017 - 8:34 am

    Im Optimalfall sollten die Kinderbeine schon vollständig über das Sattelblatt reichen.

  24. #24 by freechip poker on 28 de maio de 2017 - 8:39 am

    Awesome post. I am a normal visitor of your website and appreciate you taking the time to maintain the nice site. I’ll be a frequent visitor for a really long time.

  25. #25 by car insurance nj vs fl on 28 de maio de 2017 - 8:39 am

    I am so delighted you enjoyed it, Jane. We all have to participate in the marketing these days and it can feel awkward. I try to give value and a bit of fun. It’s easy with Mogpog, it’s such an amazing place, wonderful traditions, close community – I lived there on and off for over a year. My next post we will be about the women – have a fabulous photo from 1920s of all the ‘society ladies’ in their gorgeous ‘best clothes’.

  26. #26 by Cheap Vacation on 28 de maio de 2017 - 8:45 am

    I truly appreciate this post. I¡¦ve been looking all over for this! Thank goodness I found it on Bing. You have made my day! Thank you again

  27. #27 by engineer discount auto insurance on 28 de maio de 2017 - 8:47 am

    We need more insights like this in this thread.

  28. #28 by anker on 28 de maio de 2017 - 8:56 am

    Wir führen Medikamente aus dem Gebiet der Homöopathie gegen typische Krankheiten und Beschwerden, die bei Frauen besonders häufig vorkommen.

  29. #29 by immediate auto insurance quote on 28 de maio de 2017 - 9:12 am

    I feel so much happier now I understand all this. Thanks!

  30. #30 by http://fertilitetsradgivningen.se/formular/76.html on 28 de maio de 2017 - 9:55 am

    Yet not just as fancy in real life provided moms wrist are not really 2small do not buy it trigger that it get tight .. it is attractive still something yur 5year old makes . Non your less the a great ok gifts in order to present but not any wow gift…cant get wrong if you think don’t has a lot to blow for a gifts subsequently buy that it

  31. #31 by http://sispe.com.br/plugins/fexhtml/11.html on 28 de maio de 2017 - 9:55 am

    But not because fancy at real world if mothers wrist are not 2small don’t buy that it cause information technology try to be tight .. the cute however some thing yur 5year older makes . Non the much less it is a great okay present on award yet not your wow present…cant get wrong in case dont posses far to blow for a gifts next take it

  32. #32 by red bottom shoes replica on 28 de maio de 2017 - 10:40 am

    I got this particular gifts concerning the mother of Christmas as she is actually the best precious jewelry freak. The something she cannot use a great deal of was, bracelets. I purchased her this particular charm bracelet and also after she opened that it yesterday she absolutley enjoyed information technology! Nowadays the issue was, her buying it in and/or off simply by by herself. Haha… on the whole awesome product, information technology shipped additionally came really very early as well as my mother is enjoying information technology. Thank one.

  33. #33 by average cost for 6 months auto insurance on 28 de maio de 2017 - 10:54 am

    we like to honor a lot of other world wide web web sites on the web, even though they aren?t linked to us, by linking to them. Underneath are some webpages really worth checking out

  34. #34 by where can i buy a cheap car on 28 de maio de 2017 - 10:58 am

    This insight’s just the way to kick life into this debate.

  35. #35 by herauszufinden das hier on 28 de maio de 2017 - 11:05 am

    Ich hatte nichts dagegen, dass Christian weder den Weg zu seiner Wohnung noch den zu meiner ansteuerte.Erst als wir wieder gesittet nebeneinander saßen, musste Manuel dienstlich werden.

1 1.171 1.172 1.173
(não será publicado)