Hi all,

I have a few questions on how to sort my renderbucket (in my renderqueue).

Below you can find an example of the current content in my opaqua render bucket.

The struct that I use per renderable is this:

typedef struct Q_RENDERABLE			// renderable level; for filling render buckets
{
	int	MatGroup;
	int	Material;
	int	Mesh;
	int	Instance;
	int	Id;		
	bool Visible;
	float DistToCamSqr;
} Q_RENDERABLE;

My questions:

- what would you advice on another way of sorting, I know fully based it on materialgroup (shader), mesh, instance etc., to reduce state changes, texture changes, shader changes etc. All works pretty good, but I don't do anything yet with distance to camera (front to back might be useful for early-z, but how to combine both sorting options?)

- say I insert or add renderables (for new entities), how can I easily sort them based on one of the variables, with std::sort or something?

(I have a std::vector<int> where I can simply store the indices of the renderables in a specific order)

- could I maybe create some sort of key based on the 7 variables and sort that?

Any help is appreciated.

An example of the bucket, current sorting:

ID	matgrp	matl	mesh	inst	distsqr

0	0	0	7	44	2679.06
1	0	0	7	44	1928.28
2	0	0	7	44	1523.69
0	0	0	8	45	2678.64
1	0	0	8	45	1526.07
2	0	0	8	45	1961.64
0	0	1	1	30	863.876
5	0	1	1	30	641.774
1	0	2	1	28	297.844
3	0	2	1	28	302.922
7	0	2	1	28	298.979
1	0	2	1	30	715.996
3	0	2	1	30	681.976
7	0	2	1	30	710.025
2	0	3	1	28	324.312
2	0	3	1	30	784.915
0	0	9	13	14	26.7233
0	0	9	13	15	50.9233
0	0	9	13	16	26.5313
0	0	9	13	17	50.7313
1	0	10	13	14	31.211
1	0	10	13	15	56.941
1	0	10	13	16	31.019
1	0	10	13	17	56.749
2	0	11	13	14	26.546
2	0	11	13	15	50.746
2	0	11	13	16	27.884
2	0	11	13	17	52.084
3	0	12	13	14	23.4845
3	0	12	13	15	46.1545
3	0	12	13	16	23.2925
3	0	12	13	17	45.9625
4	0	13	13	14	28.1495
4	0	13	13	15	52.3495
4	0	13	13	16	26.4275
4	0	13	13	17	50.6275
0	0	19	17	10	632.05
0	0	24	21	3	244.611
1	0	24	21	3	241.486
2	0	25	21	3	257.666
0	1	14	14	1	0
0	1	14	14	12	24.6981
1	1	15	14	1	0
1	1	15	14	12	25.8981
2	1	16	14	1	0
2	1	16	14	12	25.8144
0	1	21	19	5	279.369
1	1	21	19	5	251.263
2	1	21	19	5	274.758
3	1	21	19	5	220.368
4	1	21	19	5	219.088
5	1	21	19	5	240.494
6	1	21	19	5	327.245
7	1	21	19	5	325.97
8	1	21	19	5	347.619
9	1	21	19	5	242.705
10	1	21	19	5	349.88
11	1	21	19	5	313.179
12	1	21	19	5	237.035
13	1	21	19	5	371.248
14	1	21	19	5	357.944
15	1	21	19	5	316.496
16	1	21	19	5	274.828
17	1	21	19	5	248.869
18	1	21	19	5	266.779
19	1	21	19	5	210.195
20	1	21	19	5	281.241
21	1	21	19	5	289.241
22	1	21	19	5	296.312
23	1	21	19	5	286.909
24	1	21	19	5	301.771
25	1	21	19	5	299.007
0	1	21	19	6	399.231
1	1	21	19	6	431.338
2	1	21	19	6	352.877
3	1	21	19	6	406.877
4	1	21	19	6	413.153
5	1	21	19	6	339.316
6	1	21	19	6	472.361
7	1	21	19	6	478.642
8	1	21	19	6	405.05
9	1	21	19	6	333.87
10	1	21	19	6	399.653
11	1	21	19	6	423.048
12	1	21	19	6	371.141
13	1	21	19	6	439.107
14	1	21	19	6	478.828
15	1	21	19	6	424.459
16	1	21	19	6	348.235
17	1	21	19	6	434.9
18	1	21	19	6	391.29
19	1	21	19	6	361.184
20	1	21	19	6	401.6
21	1	21	19	6	408.107
22	1	21	19	6	413.031
23	1	21	19	6	401.844
24	1	21	19	6	415.278
25	1	21	19	6	414.707
8	1	35	25	54	319.827
4	2	4	1	28	307.071
6	2	4	1	28	307.903
4	2	4	1	30	692.514
6	2	4	1	30	691.557
0	2	7	4	18	731.78
3	2	7	4	18	648.601
4	2	7	4	18	977.865
5	2	7	4	18	852.965
2	2	7	4	24	807.783
4	2	7	4	24	1048.26
5	2	7	4	24	1195.96
1	2	27	22	2	25.9537
0	3	6	3	39	458.656
0	3	6	3	40	505.257
0	3	6	3	41	541.335
0	3	8	9	46	660.565
0	3	8	10	47	698.492
0	3	8	11	48	160.596
0	3	8	12	49	131.051
0	3	17	15	0	0
1	3	17	15	0	0
2	3	17	15	0	0
0	3	17	15	13	50.8262
1	3	17	15	13	48.7949
2	3	17	15	13	51.9707
0	3	22	20	4	804.828
1	3	23	20	4	879.321
0	3	26	22	2	25.941
0	3	30	25	54	323.753
1	3	30	25	54	323.794
2	3	30	25	54	321.517
3	3	31	25	54	328
4	3	32	25	54	322.811
5	3	32	25	54	323.494
6	3	33	25	54	321.439
10	3	33	25	54	321.502
7	3	34	25	54	320.425
9	3	36	25	54	320.352

my recommended reading:

http://realtimecollisiondetection.net/blog/?p=86

It works well for most cases and is flexible.

Also you can use radix sorting easily on this and the you are guaranteed to have a linear sort time.. which I think is a good thing.

(for smaller lists radix might/will be slower) but if you want to sort a larger number of items in a predictable time then radix is awesome!

Happy sorting :)

To expand on my previous reply the reason using bits for sorting is useful because you can sort on multiple things at once for the same price and not only that you can very easily change the priorities of various search fields, just shift their positions around.

This enables you to test a scene and at the touch of a key try out different options see which works best for you.

basically you use a single 32 or 64 bit unsigned integer to represent your draw call.

each bit or bit group represents some property of that draw call.

i.e. say you had the following

1. a material id (maximum 256*) then that can be stored in 8 bits of your 32 or 64 bit uint. (if you only had 16* or less materials you could store that in 4 bits)

2. approximate depth (maximum 256*) - you would have to normalize it from a float into the 0-255 range (again you could use more bits if you wanted, in his example he uses 24

3. transparent or not (2 options) - can store this in one bit

With that in mind you could store it like this

tmmmmmmmmdddddddd only 17 bits

you can then sort your draw calls based on this integer, up to you what method but I do love a radix sort for the reasons mentioned before and the fact that it is geared for sorting unsigned integers

then boom, process in order and you will get the transparency as your first priority, then material id, then depth.

Hope that make some kind of sense I threw it together rather fast

*these are purely examples and would very from use case to use case.

what would you advice on another way of sorting

You don’t need “Visible”. If they are not visible, they are not in the bucket render-queue. Don’t waste time sorting invisible objects.

say I insert or add renderables (for new entities), how can I easily sort them based on one of the variables, with std::sort or something?
(I have a std::vector where I can simply store the indices of the renderables in a specific order)

You don’t seem to get the concept of a render-queue.
It is built from scratch every frame. It changes sizes every frame as new objects appear and disappear from the screen. It is sorted every frame after being rebuilt every frame.

There is no “render bucket”.
There is a list of all objects in the scene.
Then that becomes a list of all objects within a frustum (created with the help of a tree structure such as an octree). Notice that this allows different objects to be in the list from one frame to the next.
Then those objects submit “render-queue items” to a render queue (which is reset back to 0 items at the start of each render).
The render-queue sorts. Sorting indices, not actually moving any render-queue items.
The objects are drawn in the order specified by the render-queue.

could I maybe create some sort of key based on the 7 variables and sort that?

Typically. See above replies.


L. Spiro

Thanks both, this should bring me in the right direction.

@LSpiro: I understand what you, the struct and data you see above is just the base/ layout of the data. I have a index of only the visible renderables which I actually renderable. The same for blended, first I update the index of visible ones (simply pointing to the renderables), afterwards I sort based on the index (not the whole vector).

bool CRenderQueue::CreateBucketOpaque()
{
	mBucketOpaque.resize(0);

	for(size_t rend=0;rend<mRenderablesOpaque.size();++rend)
	{
		if(mRenderablesOpaque[rend].Visible) 
			mBucketOpaque.push_back(rend);
	}
	return true;
}

@BWhiting: I understand the principle, but unfortunately do need some more pointers to get into it.

Let's take a fictive/ simplified example:

I have this data per renderable:

- int mesh ID (max 256)

- int material ID (max 256)

- float dist to cam

Let's say I want to put those tree into one key, I believe I would then need:

meshID = 8 bit

materialID = 8 bit

disttocam = 8 bit (converted to range 0 to 255).

Note: currently I store disttocam squared, being sometimes up to 1.000, so like you said I can convert them into the range of 0 - 255 (and get the correct range using the index to the right 'full' renderable).

I've played around with bitwise operators, so far:

	UINT16 a = 0;
	int b = 14;		// must be lower then 256 (8 bits)
	int c = 113;	// must be lower then 256 (8 bits)

	a = ((0xFF & c) << 8) | (0xFF & b);
	
	// what's happening with A?
	//
	// 1. initially:	00000000 00000000
	// 2. 0xFF & c:		00000000 00001110
	// 3. << 8:			00001110 00000000
	// 4. 0xFF & b:		00001110 01110001
	// no need to shift here
	
	// now A has stored my two keys


	UINT32 a = 0;
	int b = 14;		// must be lower then 256 (8 bits)
	int c = 113;	// must be lower then 256 (8 bits)
	int d = 14;		// must be lower then 256 (8 bits)

	a = ((0xFF & c) << 16) | ((0xFF & b) << 8) | (0xFF & d);
	
	// what's happening with A?
	//
	// 1. initially:	00000000 00000000 00000000 00000000
	// 2. 0xFF & c:		00000000 00000000 00000000 00001110
	// 3. << 16:		00000000 00001110 00000000 00000000
	// 4. 0xFF & b:		00000000 00001110 00000000 01110001
	// 5. << 8:			00000000 00001110 01110001 00000000
	// 6. 0xFF & d:		00000000 00001110 01110001 00001110
	//								C		 B		  D
	 // no need to shift here
	
	// now A has stored my three keys and has 8 bits unused

Now I'll be digging into extracting the individual keys from the UINT / combined key.

After this the challenge will be to 'move bit sets around' and find out how to sort on which keys, which key first etc.

Any help/ pointers on this are welcome.

you won't need to extract anything from the keys, they are purely for sorting.

once sorted you should already have the data you need in the original objects

the more weight you want any key to have you just ensure that those bits are more significant

so if you want to prioritise material, then just make sure that its bits are shifted higher.

your play around above is a great start in the right direction!

just sort your objects based on that uint and boom - roll in your success.

Hi. I'm getting somewhere, I now managed to create a 'bitkey' for all renderables (tested and well, retrieving them back also).

I also was able to sort, and create a new index. The only thing that's left is how I can use the bits, to sort in a specific way.

Let's say I want to sort like this:

- first on material group

- then on material

- then on mesh

- then on distance

(don't sort on mesh instance)

How would I do that/ how can I set which bits are more 'significant' when sorting?

I've pasted the whole testprogram I wrote, so if you want you can easily copy/paste and check it (just 1 CPP file).

Currently I get a sorting back where all renderables are sorted on 'mesh' (bits 33 to 40 if I'm correct).

#include <Windows.h>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <vector>

typedef struct Q_RENDERABLE
{
	int	MatGroup;
	int	Material;
	int	Mesh;
	int	Instance;
	int	Id;		
	bool Visible;
	float DistToCamSqr;

	// testing
	int DistToCamConv;
} Q_RENDERABLE;


std::vector<Q_RENDERABLE> tRenderables;
std::vector<int> tIndexUnsorted;
std::vector<int> tIndexSorted;

std::vector<UINT64> tBitKeys;

bool Setup(const std::string pFilename);
bool CreateIndexUnsorted();
bool CreateBitKeys();
bool SortKeys();
bool OutputResults(const std::string pFilename);

bool loaded = false;
bool created = false;
bool bitKeysCreated = false;


int WINAPI WinMain(HINSTANCE hInstance,
				   HINSTANCE hPrevInstance,
				   LPSTR lpCmdLine,
				   int nCmdShow)
{
	if(!Setup("testbucket.txt")) return 0;
	
	if(!CreateIndexUnsorted()) return 0;
	if(!CreateBitKeys()) return 0;
	if(!SortKeys()) return 0;

	if(!OutputResults("indices.txt")) return 0;

	return 1;
}


/*** LOAD THE TEST RENDERABLES'S DATA - ASSUMING ALL VISIBLE FOR TESTING ***/

bool Setup(const std::string pFilename)
{
	std::ifstream readFile(pFilename);
	if(!readFile) return false;

	Q_RENDERABLE tempRend;
	tRenderables.resize(0);

	char temp[255];
	for(int j=0;j<6;++j) readFile >> temp;

	bool done = false;
	while(!done)
	{
		readFile >> tempRend.Id;
		if(tempRend.Id == 9999) break;

		readFile >> tempRend.MatGroup;
		readFile >> tempRend.Material;
		readFile >> tempRend.Mesh;
		readFile >> tempRend.Instance;
		readFile >> tempRend.DistToCamSqr;
		tempRend.Visible = true;

		tRenderables.push_back(tempRend);
	}
	readFile.close();

	loaded = true;
	return true;
}

/*** ADD INDICIES OF ALL VISIBLE RENDERABLES TO 'UNSORTED' INDEX OF RENDERABLES = BUCKET ***/

bool CreateIndexUnsorted()
{
	if(!loaded) return false;
	
	tIndexUnsorted.resize(0);
	
	for(size_t rend=0;rend<tRenderables.size();++rend)
	{
		if(tRenderables[rend].Visible) tIndexUnsorted.push_back(rend);
	}
	created = true;
	return true;
}

bool CreateBitKeys()
{
	if(!loaded) return false;

	// USE A 64 BIT SORTING KEY: 44 BITS NEEDED FOR NOW
	
	// 4 bits: material group	(range 0 - 16)
	// 8 bits: materal ID		(range 0 - 255)
	// 8 bits: mesh ID			(range 0 - 255)
	// 16 bits: mesh inst ID	(range 0 - 2048)
	// 8 bits: dist to cam		(range 0 - 255)		=> needs conversion

	// convert dists to cam, testing (define max and then convert)
	float maxDist = tRenderables[0].DistToCamSqr;
	for(size_t rend=1;rend<tRenderables.size();++rend)
	{
		if(tRenderables[rend].DistToCamSqr > maxDist) maxDist = tRenderables[rend].DistToCamSqr;
	}
	// maxDist == 250
	for(size_t rend=0;rend<tRenderables.size();++rend) tRenderables[rend].DistToCamConv = (int((250 * tRenderables[rend].DistToCamSqr) / maxDist));

	// SET THE BITS AND CREATE THE SORTING KEYS
/*	00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
						  MGRP	 MAT	  MESH	   INST		INST	 DIST
	
	MGRP << 40;
	MAT << 32;
	MESH << 24;
	INST << 16;
	DIST << 0;
*/

	for(size_t rend=0;rend<tIndexUnsorted.size();++rend)
	{
		auto &tr = tRenderables[tIndexUnsorted[rend]];
		UINT64 makeKey = 0;

		makeKey = ((0xFF & tr.MatGroup) << 40) | ((0xFF & tr.Material) << 32) | ((0xFF & tr.Mesh) << 24) | ((0xFF & tr.Instance) << 16) | (0xFF & tr.DistToCamConv);

		tBitKeys.push_back(makeKey);
	}
	bitKeysCreated = true;
	return true;
}

/*** SORT THE KEYS AND CREATE A NEW SORTED INDEX ***/

bool SortKeys()
{
	if(!bitKeysCreated) return false;

	std::vector<int> tSortIndexTemp;
	std::vector<UINT64> tSortKeysTemp;
	tSortIndexTemp.resize(tIndexUnsorted.size());

	for(size_t tIndex=0;tIndex<tIndexUnsorted.size();++tIndex) tSortIndexTemp[tIndex] = tIndex;

	std::sort(tSortIndexTemp.begin(), tSortIndexTemp.end(), [&](int a, int b)
	{ return tBitKeys[a] > tBitKeys[b]; } );

	tIndexSorted.resize(tIndexUnsorted.size());
	for(size_t sorted=0;sorted<tIndexUnsorted.size();++sorted)
		tIndexSorted[sorted] = tSortIndexTemp[tIndexUnsorted[sorted]];
	
	return true;
}

/*** SAVE ALL TEST RESULTS TO ASCII FILE ***/

bool OutputResults(const std::string pFilename)
{
	if(!loaded || !created) return false;

	std::ofstream oResult(pFilename);

	// UNSORTED VISIBLE INDEX

	oResult << "Unsorted (visible) index: " << std::endl;
	for(size_t rend=0;rend<tIndexUnsorted.size();++rend)
	{
		oResult << tIndexUnsorted[rend] << std::endl;
	}
	
	// TESTING BITKEYS STORING & RETRIEVING
	
	oResult << "Checking visible renderable 5" << std::endl;
	oResult << tRenderables[tIndexUnsorted[5]].MatGroup << ", ";
	oResult << tRenderables[tIndexUnsorted[5]].Material << ", ";
	oResult << tRenderables[tIndexUnsorted[5]].Mesh << ", ";
	oResult << tRenderables[tIndexUnsorted[5]].Instance << ", ";
	oResult << tRenderables[tIndexUnsorted[5]].DistToCamConv << std::endl;

	Q_RENDERABLE retrTest;
	
	retrTest.MatGroup = (tBitKeys[tIndexUnsorted[5]] >> 40  & 0xFF);
	retrTest.Material = (tBitKeys[tIndexUnsorted[5]] >> 32  & 0xFF);
	retrTest.Mesh = (tBitKeys[tIndexUnsorted[5]] >> 24  & 0xFF);
	retrTest.Instance = (tBitKeys[tIndexUnsorted[5]] >> 16  & 0xFF);
	retrTest.DistToCamConv = (tBitKeys[tIndexUnsorted[5]] & 0xFF);

	oResult << "Retrieved renderable 5: " << std::endl;
	oResult << retrTest.MatGroup << ", ";
	oResult << retrTest.Material << ", ";
	oResult << retrTest.Mesh << ", ";
	oResult << retrTest.Instance << ", ";
	oResult << retrTest.DistToCamConv << std::endl;

	oResult << std::endl;
	oResult << "Sorted renderables using bit keys:" << std::endl;
	oResult << "ID\tmatgrp\tmatl\tmesh\tinst\tdistsqr" << std::endl;

	for(size_t rend=0;rend<tIndexSorted.size();++rend)
	{
		oResult << tRenderables[tIndexSorted[rend]].Id << "\t";
		oResult << tRenderables[tIndexSorted[rend]].MatGroup << "\t";
		oResult << tRenderables[tIndexSorted[rend]].Material << "\t";
		oResult << tRenderables[tIndexSorted[rend]].Mesh << "\t";
		oResult << tRenderables[tIndexSorted[rend]].Instance << "\t";
		oResult << tRenderables[tIndexSorted[rend]].DistToCamSqr << std::endl;
	}
	oResult.close();

	return true;
}

Sort results:

Sorted renderables using bit keys:
ID	matgrp	matl	mesh	inst	distsqr
7	3	34	25	54	320.425
10	3	33	25	54	321.502
5	3	32	25	54	323.494
4	3	32	25	54	322.811
9	3	36	25	54	320.352
6	3	33	25	54	321.439
3	3	31	25	54	328
2	3	30	25	54	321.517
1	3	30	25	54	323.794
0	3	30	25	54	323.753
8	1	35	25	54	319.827
0	3	26	22	2	25.941
1	2	27	22	2	25.9537
1	0	24	21	3	241.486
0	0	24	21	3	244.611
2	0	25	21	3	257.666
0	3	22	20	4	804.828
1	3	23	20	4	879.321
7	1	21	19	6	478.642
6	1	21	19	6	472.361
17	1	21	19	6	434.9
14	1	21	19	6	478.828
13	1	21	19	6	439.107
1	1	21	19	6	431.338
25	1	21	19	6	414.707
24	1	21	19	6	415.278
22	1	21	19	6	413.031
21	1	21	19	6	408.107
4	1	21	19	6	413.153
15	1	21	19	6	424.459
12	1	21	19	6	371.141
11	1	21	19	6	423.048
19	1	21	19	6	361.184
18	1	21	19	6	391.29
16	1	21	19	6	348.235
8	1	21	19	6	405.05
3	1	21	19	6	406.877
10	1	21	19	6	399.653
2	1	21	19	6	352.877
0	1	21	19	6	399.231
23	1	21	19	6	401.844
20	1	21	19	6	401.6
5	1	21	19	6	339.316
9	1	21	19	6	333.87
13	1	21	19	5	371.248
8	1	21	19	5	347.619
10	1	21	19	5	349.88
14	1	21	19	5	357.944
25	1	21	19	5	299.007
23	1	21	19	5	286.909
0	1	21	19	5	279.369
6	1	21	19	5	327.245
7	1	21	19	5	325.97
22	1	21	19	5	296.312
20	1	21	19	5	281.241
21	1	21	19	5	289.241
24	1	21	19	5	301.771
2	1	21	19	5	274.758
11	1	21	19	5	313.179
15	1	21	19	5	316.496
16	1	21	19	5	274.828
18	1	21	19	5	266.779
1	1	21	19	5	251.263
5	1	21	19	5	240.494
12	1	21	19	5	237.035
17	1	21	19	5	248.869
19	1	21	19	5	210.195
9	1	21	19	5	242.705
3	1	21	19	5	220.368
4	1	21	19	5	219.088
0	0	19	17	10	632.05
0	3	17	15	13	50.8262
1	3	17	15	13	48.7949
2	3	17	15	13	51.9707
1	3	17	15	0	0
0	3	17	15	0	0
2	3	17	15	0	0
2	1	16	14	12	25.8144
1	1	15	14	12	25.8981
0	1	14	14	12	24.6981
2	1	16	14	1	0
1	1	15	14	1	0
0	1	14	14	1	0
2	0	11	13	17	52.084
1	0	10	13	17	56.749
0	0	9	13	17	50.7313
4	0	13	13	17	50.6275
3	0	12	13	17	45.9625
4	0	13	13	16	26.4275
3	0	12	13	16	23.2925
2	0	11	13	16	27.884
0	0	9	13	16	26.5313
1	0	10	13	16	31.019
2	0	11	13	15	50.746
1	0	10	13	15	56.941
4	0	13	13	15	52.3495
0	0	9	13	15	50.9233
3	0	12	13	15	46.1545
4	0	13	13	14	28.1495
3	0	12	13	14	23.4845
2	0	11	13	14	26.546
0	0	9	13	14	26.7233
1	0	10	13	14	31.211
0	3	8	12	49	131.051
0	3	8	11	48	160.596
0	3	8	10	47	698.492
0	3	8	9	46	660.565
0	0	0	8	45	2678.64
2	0	0	8	45	1961.64
1	0	0	8	45	1526.07
0	0	0	7	44	2679.06
1	0	0	7	44	1928.28
2	0	0	7	44	1523.69
5	2	7	4	24	1195.96
4	2	7	4	24	1048.26
2	2	7	4	24	807.783
4	2	7	4	18	977.865
5	2	7	4	18	852.965
0	2	7	4	18	731.78
3	2	7	4	18	648.601
0	3	6	3	41	541.335
0	3	6	3	40	505.257
0	3	6	3	39	458.656
4	2	4	1	30	692.514
6	2	4	1	30	691.557
0	0	1	1	30	863.876
2	0	3	1	30	784.915
1	0	2	1	30	715.996
7	0	2	1	30	710.025
3	0	2	1	30	681.976
5	0	1	1	30	641.774
4	2	4	1	28	307.071
6	2	4	1	28	307.903
2	0	3	1	28	324.312
3	0	2	1	28	302.922
7	0	2	1	28	298.979
1	0	2	1	28	297.844