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 air jordan 11 space jam size tag on 19 de agosto de 2017 - 7:51 pm

  2. #2 by auto acceptance insurance Clarksville TN on 19 de agosto de 2017 - 7:52 pm

    Hey quit picking on the Ohio teams! I think the Browns were named for one of the original players. I’m sure Tim could elaborate. He comes from a family of die hard Cleveland fans. As for Akron and Cincinnati, I have no explanation.

  3. #3 by cash loans on 19 de agosto de 2017 - 7:55 pm

    I was looking at some of your articles on this site and I believe this web site is real instructive! Keep posting.

  4. #4 by low income car insurance WV on 19 de agosto de 2017 - 8:00 pm

    I do know lots of people are curious about this valuable area and that i cannot deny I’m as well one too. In case there are numerous deeper debate concerning this topic then will probably be additional desirable and I might possibly want to imagine of just what you might compose regarding your subsequent post. In the event that you can distribute even more related post, just make me aware since I am going to would like to learn about this.

  5. #5 by lululemon pants on 19 de agosto de 2017 - 8:11 pm

  6. #6 by cheap arcteryx jackets on 19 de agosto de 2017 - 8:12 pm

    Shahram slipping akersten perambulate montego augar whopper camposana Yuan
    cheap arcteryx jackets http://www.arcteryxjackets.online

  7. #7 by instacart coupon 2017 on 19 de agosto de 2017 - 8:12 pm

    I love reading a post that will make people think. Also, thank you for permitting me to comment!

  8. #8 by auto insurance quotes Rochester NY on 19 de agosto de 2017 - 8:20 pm

    Sandgirl, c’est le ton d’un posteur (voir sa signature).D’où la rhétorique stal’ qui tourne en boucle. (Et la reproduction in extenso de pajamamedias sur le blog de Corine…).

  9. #9 by casino gambling system on 19 de agosto de 2017 - 8:24 pm

    It’s a shame you don’t have a donate button! I’d most certainly donate to this superb blog! I guess for now i’ll settle for bookmarking and adding your RSS feed to my Google account. I look forward to brand new updates and will share this site with my Facebook group. Talk soon!

  10. #10 by low income car insurance dmv Duluth MN on 19 de agosto de 2017 - 8:38 pm

    you’re right about them not being idiots. They are worse than idiots as idiots are relatively harmless. These people are sinister and clever and manipulative. and sick. thanks for spreading the awareness though!

  11. #11 by California Republic Bandana Bear Men's T-Shirt Red Bandana Bear on 19 de agosto de 2017 - 9:10 pm

    Amazon Customer^The quality of this t-shirt is sub-par. The fabric is a thin cotton and the graphic design looks and feels like an iron on and is very muted in color. The description shows writing on the back and the shirt I received has nothing on the back. Also the wording on the graphic design is partially cut off. I would not recommend this tee shirt.~3|Kathleen^This shirt had the E and S missing on the front&#44 the image was dripping down the front&#44 there were vacant areas on the print where the ink just pealed off…the fabric was like cheap lingerie and nothing on the back…goes in the rag bag&#44 maybe doesn’t even deserve that burial. Just awful. How could anyone send this out and think it was OK?~3|Kerry smith^I’ve wanted this shirt for a long time but never took the time or money to buy it.glad I fineally picked it up. Great looking shirt.fits perfect.thanks~5|Michael^Great shirt…Great fit~5|

  12. #12 by casino gambling system on 19 de agosto de 2017 - 9:18 pm

    I rattling thankful to find this website on bing, just what I was searching for : D also saved to favorites.

  13. #13 by cartier juste un clou replica on 19 de agosto de 2017 - 9:20 pm

    I have your headphonesof my personal mother to parents time, additionally she absolutely loved they! Their really cute headphonesand the saying on the card it comes in the container is very sentimental!! As well as the excellence of beads was awesome!

  14. #14 by fast cash loan on 19 de agosto de 2017 - 9:22 pm

    I’ve been surfing online more than three hours today, yet I never found any interesting article like yours. It’s pretty worth enough for me. In my opinion, if all website owners and bloggers made good content as you did, the net will be a lot more useful than ever before.

1 1.337 1.338 1.339
(não será publicado)