Build an array and sort it based on Pipeline (and other state changes).

Write targeting Mantle (Vulkan being a derivative), Metal (iOS, OSX) and D3D12 preferably.

The approach you use cannot be high performance, the one you called structured is the way most high-end games have been doing for many years now...

The way I have found it to work is to take a list of "renderables" sort them by a certain criteria and then loop through them to render, is this correct / the right way to be doing it?

basically, yeah.

you'll want to sort as little as possible, that's why they cull first.

your sort criteria should generate an optimal draw order with respect to pipeline state changes, for whatever drawing methods you're using.

that's more or less it.

biggest variation seems to be in the sorting method used. encoding sort criteria in ints and then sorting the ints is popular. apparently its faster than sorting on the criteria themselves.

when i was faced with the question of how to speed up sorting in my render queue, i had never heard of the technique of encoding sort criteria into ints. so i had to come up with my own solution. in my typical overkill fashion, i went straight for the fastest possible sort: bucketsort. i use a multi-dimensional indexing system (as in: an index into database) that basically does an in-order bucket sort insertion of renderables into the render queue's index. so i have no extra sort step required. as soon as all renderables have been added, the index is already sorted and ready to use for optimal draw order rendering. i've never tested this vs encoded ints to see which is faster. for now, the indexed system is plenty fast enough - at least for my needs.

Jep, that could be a good way to go.
If you're not directly able to translate that article into a solution (which I experienced), then you could check out this approach, which is for a big part based on that article:
http://www.gamedev.net/topic/659607-sorting-a-bucket/

Here's an article to get you going. (About what to sort, not how)

http://cg.alexandra.dk/?p=3778

For the sorting, is this the type of thing you would need to do: http://realtimecollisiondetection.net/blog/?p=86

yes that would be one example implementation.

i personally handle many of their criteria as separate passes. for example, full screen layers and HUDs, I do alpha blend as a separate pass. i don't use viewports, but i'd probably implement them so the game layer was just another viewport, and render would be a "for each viewport, render" type thing. so which viewport would not be encoded. it would be "this" viewport, so to speak, as OO folks are fond of saying. really what i do is texture and vertex buffer sorting. IE i sort on texture, then mesh. its so fast i don't even bother with near to far (yet - i should put it in). i use the render queue for multiple regular passes, and also for the alpha blend pass. for example, the passes used in Caveman 3.0 are: skybox, sun/moon, clouds (alpha blend), stuff out to far range, full screen effects (snow etc), 1st person attack anis (with clip planes set really close), and HUD. when i add alpha blended flames (IE an alpha pass out to far range), they will come after drawing non-alpha stuff out to far range, and before full screen effects. i find using a basic render queue multiple times in multiple passes to be a very flexible way to do things.

Should my rendering engine be structured so that it contains a list / queue which is iterated over and renderer

This is not a simple question. There are many components that need to work together and several ways to store objects that need to be rendered.

A model is a collection of meshes, and each mesh has one “sub-mesh” per material (per render pass).

Your game scene (scene manager—keeps track of all objects in your scene, from lights to players to grass, sky, etc.) has a list of models probably stored in a linear array, but also inside an octree for frustum culling etc.


#1: Scene manager culls the world objects for those in view, using the octree. Each in-view mesh adds to a render-queue all of its sub-meshes (each render-queue item corresponds to 1 draw call, since its whole purpose is to sort for efficient rendering).
#2: The render-queue is a linear list of sub-meshes that need to be drawn. It contains things such as shader keys, texture keys, vertex-buffer keys, etc. All the information necessary for sorting.
Opaque sorts are largely based on render state, and when 2 objects have the same render state they are sorted front-to-back.
Translucent objects are sorted back-to-front.
#3: The sorted render-queue is used for rendering sub-meshes in order.

This is heavily discussed here.

i went straight for the fastest possible sort: bucketsort.

Insertion sort paired with temporal coherence is O(n) most frames, which is the fastest you should be able to achieve since sorting is actually a rare occurrence (a slower sort that runs in linear time for already-sorted items outperforms any faster sort that does not take advantage of already-sorted items).


L. Spiro