🔒 Locked

Fastest way to sort a scene

Started by UnknownPlayer May 18, 2003 at 7:53 AM 7 replies 9.8k views

Original Post

May 18, 2003 at 7:53 AM

What''s the fastest way I can sort the alpha blended objects in my scene in back to front order? I store all my data in one giant linked list which I render from, and objects that need to be sorted are tagged with a boolean. The code I currently use to do the sort (actually its my entire draw loop for the list) is:

  
	CBaseObject* TempObject = NULL;	// Used for deleting objects


	// Sanity Check

	if (FirstObject == NULL)
	{
		return;			// Can''t use draw path without an initial object

	}

	CurrentObject = FirstObject;	// Start from beginning of chain


	// Set up the delete queue ready for data

	GenericList* Queue = new GenericList;
	GenericList* Tracking = Queue;

	// Alpha sorting setup

	uint NumberOfAlphaObjects = 0;
	CBaseObject** AlphaObjectList = new CBaseObject*[ObjectsAllocated];

	while (CurrentObject != NULL)
	{
		if (CurrentObject->AlphaBlender && CurrentObject->DarkObjectDerived)
		{
			AlphaObjectList[NumberOfAlphaObjects] = CurrentObject;
			NumberOfAlphaObjects++;
		}
		else
		{
			CurrentObject->Draw();
		}

		if ( (CurrentObject->DeleteNow || CurrentObject->DeleteOnDraw) )
		{
			Tracking->Payload = CurrentObject;
			Tracking->Next = new GenericList;
			Tracking = Tracking->Next;
		}

		CurrentObject = CurrentObject->next;// Move cursor to next object

	}

	// Sort and render the alpha objects

	qsort(AlphaObjectList, NumberOfAlphaObjects, sizeof(CBaseObject*), CompareParticleDistances);

	App()->d3ddevice->SetRenderState(D3DRS_ZWRITEENABLE, false);
	for (uint i=0; i < NumberOfAlphaObjects; i++)
	{
		AlphaObjectList[i]->Draw();
	}
	App()->d3ddevice->SetRenderState(D3DRS_ZWRITEENABLE, true);

	// Clean up the list

	delete [] AlphaObjectList;

	// Render the HUD //

	 if (HudObject)
	 {
		 // The hud is responsible to ensure it doesn''t render twice

		 HudObject->Draw();
	 }

	// Destroy all objects that have placed requests //

	while (Queue != null)
	{
		DestroyObject((CBaseObject*)Queue->Payload);
		Tracking = Queue;
		Queue = Queue->Next;
		delete Tracking;
	}

However this seems pretty slow when its running compared to w/o this code, so there must be a better way. I''m wondering though if the issue is the speed of the quicksort, the speed of the memory allocation or both? ##UnknownPlayer##

Damage_Incorporated

May 18, 2003 at 8:04 AM

sorting the entire list everytime you render it is more or less NOT an option if you want any kind of speed... I would suggest a BSP tree if you simply want to sort it back to front its quite simple to implement and there are a bunch of tutorials on the topic. If you are making a shoot em up game then you probably have to implement a BSP tree or something similar sooner or later, sooner is probably better than later

my 2 cents anyways

- Damage Inc.

Cornutopia

May 18, 2003 at 2:48 PM

If you''re adding to the linked list in an arbitrary order, then the fastest option is to add/create list items in the order you want. Of course this would mean not changing the alpha on the fly which is often done... however if you put most-likely opaque objects first and most likely transparent last then the results should be fine.

Mark
Cornutopia Games
http://www.cornutopia.net
Bytten Independent Games Magazine
http://www.bytten.com

UnknownPlayer

May 18, 2003 at 4:59 PM

I''m not sorting the entire list, just extracting the items which are alpha blended and sorting them. The thing is they have to be sorted each frame since I need them in order from farthest to closest to the camera.

##UnknownPlayer##

oliii

May 18, 2003 at 5:59 PM

if the camera doesn''t move too much from frame to frame, you can keep the list of sorted items from the previous frame, and sort it for the next frame. Because the items are most likely in the proper order, you won''t have to shuffle the items in the list too much.

If you keep a sorted list of items in the view, and an unsorted list of items that are NOT in the view, then it should be straight forward to ''build'' the sorted list of items in the view for the next frame, using the one from the previous frame.

Apart from that, if you have a BSP tree structure for your environment, you can insert the items in the BSP, and trasverse the BSP from back to front.

benjamin bunny

May 18, 2003 at 7:10 PM

Radix sort is the best way to do it, since it completes in O(N) (linear) time. It wipes the floor with comparison-based sorts like quicksort, merge sort, and heap sort, all of which are O(N log N).

I use it to sort upto 20,000 particles per frame, and it''s easily fast enough for that.

Here''s my implementation, which returns the order of an array of (positive) floats. Note that my code doesn''t actually sort the array, it just returns the order, but the code can easily be adjusted if necessary, or the reordering can be done in linear time anyway.

radixsort.h

  
class RadixSort
{
public:
	RadixSort(int maxNumVals);
	virtual ~RadixSort();
	void sort(	float * input, 
				int numvals, 
				int * outputOrder);

protected:
	unsigned int counter[256];
	unsigned int offset[256];

	float * valueSwap;
	int * orderSwap;
	int maxNumVals;
};

radixsort.cpp

  
RadixSort::RadixSort(int maxNumVals)
{
	this->maxNumVals=maxNumVals;
	orderSwap=new int[maxNumVals];
	valueSwap=new float[maxNumVals];
}
RadixSort::~RadixSort()
{
	delete [] orderSwap;
	delete [] valueSwap;
}

//doesn''t sort negative numbers (they are placed last)

//outputOrder should be in order

void RadixSort::sort(	float * input, 
						int numvals, 
						int * outputOrder)
{
	if (numvals>maxNumVals) numvals=maxNumVals;

	int a;
	BYTE * c;
	for (int p=0;p<4;++p)
	{
		memset((void *)counter,0,sizeof(int)*256);
		
		for (a=0;a<numvals;++a)
		{
			c=((BYTE *)&input[a])+p;
			counter[*c]++;
		}

		offset[0]=0;
		for (a=1;a<256;++a)
		{
			offset[a]=offset[a-1]+counter[a-1];
		}

		for (a=0;a<numvals;++a)
		{
			c=((BYTE *)&input[a])+p;
			valueSwap[ offset[*c] ]=input[a];
			orderSwap[offset[*c]]=outputOrder[a];
			//outputOrder[ a ]=offset[*c];

			//outputOrder[a]=offset[*c];

			++offset[*c];
		}
		float * tmp=input;
		input=valueSwap;
		valueSwap=tmp;

		int * tmpi=outputOrder;
		outputOrder=orderSwap;
		orderSwap=tmpi;
	}
}

Yann L

May 18, 2003 at 7:49 PM

quote:
Original post by benjamin bunny
Radix sort is the best way to do it, since it completes in O(N) (linear) time. It wipes the floor with comparison-based sorts like quicksort, merge sort, and heap sort, all of which are O(N log N).

Basically true, but not always. There is another interesting algorithm to consider: natural mergesort. This is not the same as a standard mergesort, as it takes pre-sorted parts of the sequence into account. Natural mergesort has a worst case behaviour of O(N log N), just as most other comparison based algorithms. But, if the scene is already sorted, it has O(N). Now, if you use time coherency, and keep the sorted lists from one frame to the next, you''d end up with a list that is likely to be mostly in the right order. Running a natural mergesort over it will correct any sorting errors, and will be almost O(N). The difference to radix sort is that the overhead per iteration is (much) lower.

I would suggest trying both approaches, and to profile the results.

benjamin bunny

May 18, 2003 at 8:26 PM

I''m sure your method is faster, most of the time, but I''m more concerned with maintaining a consistently high frame rate than having a high average framerate. if I create 1000 particles in a frame, say for an explosion, radix sort will always sort them in linear time, wheras natural merge sort won''t.

Also, I prefer the simplicity of not having to maintain the sorted list over more than one frame. I like the fact I can just chuck all my particles at the radix sort, and it''ll sort them for me, quickly.

Just my preference anyway, but I''ll probably check out your natural merge sort and see how it performs anyway.

____________________________________________________________
www.elf-stone.com

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.