Jump to content

  • Log In with Google      Sign In   
  • Create Account


Help me optimize looping / sort code inside render loop


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
7 replies to this topic

#1 lipsryme   Members   -  Reputation: 1005

Like
0Likes
Like

Posted 26 March 2013 - 09:26 AM

I'm doing a lot of sorting and looping through std::vector inside of my render loop but I need help optimizing it.

 

I'm doing tests using around a 1000 objects. 

If I run it like this (which works the way I want it to) it takes much too long.

On my computer (fairly recent quad core intel cpu) this takes 1.25ms to run !

Release mode and using 

#define _SECURE_SCL 0

#define _HAS_ITERATOR_DEBUGGING 0) 

 

Now if I were to comment out the most time consuming part which is the one I've marked with X down below

I can get it down to around 0.51ms, which is still too slow and doesn't work as intended.

 

 

Can someone help me make this faster ? :/

 


void RendererContext::CreateDrawCalls(std::vector<SceneEntityDescription> &entities,
									  std::vector<unsigned int> &opaque_drawcalls,
									  std::vector<unsigned int> &transparent_drawcalls,
									  std::vector<InstanceGroupDescription> &instanceGroups)
{
	// Depth sort entities
	std::vector<DepthOrderedObject> depthValues;
	depthValues.reserve(entities.size());
	float camPosZ = XMVectorGetZ(this->perspectiveCamera->Position());
	for(size_t i = 0; i < entities.size(); ++i)
	{
		DepthOrderedObject obj;
		obj.depthValue = entities[i].worldPosition.z - camPosZ;
		obj.index = i;
		depthValues.push_back(obj);


		// Create InstanceGroup if it doesn't already exist
		if(instanceGroups.size() > 0)
		{
			if(entities[i].ID < instanceGroups.size())
			{
				// This means the instance group already exists
				// so increase its numInstances
				instanceGroups[entities[i].ID].numInstances++;
			}
			else
			{
				// If the instance group doesn't exist,
				// create it
				InstanceGroupDescription instance;
				instance.entityType = entities[i].entityType;
				instance.numInstances = 1;
				instance.instanceID = entities[i].ID;
				instanceGroups.push_back(instance);
			}
		}
		else
		{
			// This means we've got no instance group yet
			// so just create the first one
			InstanceGroupDescription instance;
			instance.entityType = entities[i].entityType;
			instance.numInstances = 1;
			instance.instanceID = entities[i].ID;
			instanceGroups.push_back(instance);
		}

	}

	// Sort depth values
	std::sort(depthValues.begin(), depthValues.end(), FrontToBackSort);

	bool sortOpaqueDrawCalls = false;
	bool sortTransparentDrawCalls = false;

	// Create Draw Calls
	for(size_t i = 0; i < entities.size(); ++i)
	{
		// MSB part (Depth ordering)
		unsigned int drawCall = 0;
		drawCall = i;
		drawCall <<= 16;

		//// XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
		// Search for the index of our sorted depth array
		for(unsigned int u = 0; u < depthValues.size(); u++)
		{
			if(depthValues[u].index == i)
			{
				// Add depth value to our draw call
				drawCall = u;
				drawCall <<= 16;
			}
		}
		//// XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

		// LSB part (instance group)
		// Search for the index of our instance groups
		for(unsigned int v = 0; v < instanceGroups.size(); v++)
		{
			if(instanceGroups[v].instanceID == entities[i].ID)
			{
				// We've found the instance ID corresponding to this
				drawCall += v;
				break;
			}
		}

		if(entities[i].material.type != MaterialTypes::Transparent)
		{
			// If the draw call doesn't already exist
			if(this->previous_opaque_drawcalls.size() > 0 &&
			  (i < this->previous_opaque_drawcalls.size()))
			{
				// If this draw call isn't the exact same as last frame
				// update it
				if(drawCall != this->previous_opaque_drawcalls[i])
				{
					sortOpaqueDrawCalls = true;
					this->opaqueDrawCallsDirty = true;
					opaque_drawcalls.push_back(drawCall);
				}
			}
			else
			{
				this->opaqueDrawCallsDirty = true;
				sortOpaqueDrawCalls = true;
				opaque_drawcalls.push_back(drawCall);
			}
		}
		else
		{
			// If the draw call doesn't already exist
			if(this->previous_transparent_drawcalls.size() > 0 &&
			  (i < this->previous_transparent_drawcalls.size()))
			{
				// If this draw call isn't the exact same as last frame
				// update it
				if(drawCall != this->previous_transparent_drawcalls[i])
				{
					this->transparentDrawCallsDirty = true;
					sortTransparentDrawCalls = true;
					transparent_drawcalls.push_back(drawCall);
				}
			}
			else
			{
				this->transparentDrawCallsDirty = true;
				sortTransparentDrawCalls = true;
				transparent_drawcalls.push_back(drawCall);
			}	
		}
	}


	// Sort Draw Calls
	//--------------------------------------
	if(sortOpaqueDrawCalls)
	{
		std::sort(opaque_drawcalls.begin(), opaque_drawcalls.end());
	}	
	
	if(sortTransparentDrawCalls)
	{
		std::sort(transparent_drawcalls.begin(), transparent_drawcalls.end());
	}
}


Edited by lipsryme, 26 March 2013 - 09:31 AM.


Sponsor:

#2 EWClay   Members   -  Reputation: 659

Like
0Likes
Like

Posted 26 March 2013 - 05:00 PM

You already have it sorted by depth after the first loop. So why run through again in the original order, performing a linear search through the depth-sorted list, only to sort again by depth at the end? It should be possible to do it in a single pass plus a sort.

#3 lipsryme   Members   -  Reputation: 1005

Like
0Likes
Like

Posted 26 March 2013 - 05:08 PM

Well in the first loop I'm calculating the actual depth of the object and store it inside a new vector, which I can then sort by the depth.

After that I've got the depth values themselves sorted but the problem is I don't know which depth value belongs to which entity....

 

I need the sorted order as indices from 0  - XXX to store inside my unsigned integer for the draw call.

I can't just put the actual floating point depth value (which could very well be negative!) inside the 16bit part of an unsigned integer right ?


Edited by lipsryme, 26 March 2013 - 05:12 PM.


#4 Paradigm Shifter   Crossbones+   -  Reputation: 5253

Like
0Likes
Like

Posted 26 March 2013 - 05:10 PM

Store a pointer to the entity in the struct you sort...


"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

#5 lipsryme   Members   -  Reputation: 1005

Like
0Likes
Like

Posted 26 March 2013 - 05:20 PM

I can't create the draw call at the same time as the rest inside the first loop since I have to run through everything and then sort first.

After that I can create my draw call for every entity I have.

 

And when I run through that I need to know the ordered depth value index that corresponds to this entity[i]...

...or maybe I have to do this entirely different....I have no idea though..


Edited by lipsryme, 26 March 2013 - 05:26 PM.


#6 NightCreature83   Crossbones+   -  Reputation: 2738

Like
2Likes
Like

Posted 26 March 2013 - 05:47 PM

Isn't this what your after http://realtimecollisiondetection.net/blog/?p=86 and these sort orders are created way before you start rendering or even going through the entity lists.

Also if you do this depth calculation a little bit different you can eliminate a few entities as well as they are behind the camera. If you subtract the camera position vector from the object position (so objPos - camPos) you get a vector that goes from the camera to the object. If the dot product between that vector and the camera lookat vector is not positive the object is behind the camera and you can't see it.

Now this should provide you with only values of similar sign for all the other objects and as such you can eliminate your costly double loop which is at worst executed a million times if you only have a 1000 entities.
Worked on titles: CMR:DiRT2, DiRT 3, DiRT: Showdown, GRID 2, Mad Max

#7 Paradigm Shifter   Crossbones+   -  Reputation: 5253

Like
0Likes
Like

Posted 26 March 2013 - 05:51 PM

It's possible for the position of an object to be behind the camera but at least part of the object to be in front of the camera.

 

The origin of my sofa is behind me but I can still see the arms ;)

 

You need to check some bounding volume (sphere, AABB, OBB, whatevs) not just a single point.


"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

#8 lipsryme   Members   -  Reputation: 1005

Like
0Likes
Like

Posted 26 March 2013 - 06:04 PM

What do you mean by "way before you start rendering or even going through the entity lists". Do you mean the draw call is being created at the time of asset creation ? And you'd then update the draw calls whenever something changes like the object is moving ?
And about the depth I'd still need to sort the depth before I can submit it's index order to the (unsigned int) key of my draw call or not ?

Btw I'm already eliminating objects not seen by the camera using view frustum culling and AABBs.

 

update: I'm going to simplify this process a bit, which I think will work in my case.


Edited by lipsryme, 27 March 2013 - 06:20 AM.





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS