Help me optimize this function

Hallo,

I have this function that gets called for every single frame in my game. It is for drawing a sprite with rotation. Right now it is a lot slower then the function that draws a sprite without rotation. When I started optimizing the function it gave me around 55 fps, not I am up in 95.

Can anyone see something that might make it even faster?

Code:

void Visualisation::drawRotationSprite(int spriteId, float rotation, int xPos, int yPos)
{
	// Not sure why I have to do this:
	rotation -= 90;

	// Create the boundingBox
	BoundingBox boundingBox = BoundingBox(0, 0, spriteList[spriteId].getWidth(), spriteList[spriteId].getHeight());

	// Rotate
	boundingBox.rotate(rotation);
	
	// Move the bounding box
	boundingBox.move(xPos, yPos);
	
	// Create a axis alligned box
	BoundingBox allignedBox = boundingBox.allignToAxis();

	// Convert from radians to degrees. This is the valuse we use to rotate the point back
	// to find the right sprite pixel
	float cosVal = cos(-(rotation * PI / 180.0));
	float sinVal = sin(-(rotation * PI / 180.0));

	// For each pixel in the aliignedBox go back to the texture and see if there is a pixel there.
	// if it is, copy the color of it
	for(int y = allignedBox.getYpos(); y < allignedBox.getYpos() + allignedBox.getHeight(); y++)
	{
		for(int x = allignedBox.getXpos(); x < allignedBox.getXpos() + allignedBox.getWidth(); x++)
		{
			vertex point = vertex(x,y);

			if(boundingBox.pointIntersection(point))
			{
				// Rotate the point back to find the right pixel color
				int newX = point.x;
				int newY = point.y;

				int tempX = newX;
				int tempY = newY;

				newX = (tempX * cosVal - tempY * sinVal);
				newY = (tempY * cosVal + tempX * sinVal);

				// Find the correct sprite pixel
				int pixelIndex = newY * getSprite(spriteId).getWidth() + newX;
				
				// Dont know why I have to do this. Vector out of range without it
				if(pixelIndex >= getSprite(spriteId).pixelList.size() - 1)
					pixelIndex = getSprite(spriteId).pixelList.size() - 1;

				// Draw the point
				int offset = 4 * ((x * screenRec.getWidth()) + y);

				screenPnt[offset+0] = getSprite(spriteId).pixelList[pixelIndex].b;
				screenPnt[offset+1] = getSprite(spriteId).pixelList[pixelIndex].g;
				screenPnt[offset+2] = getSprite(spriteId).pixelList[pixelIndex].r;
			}
		}
	}
}

The "boundingBox.pointIntersection(point)" is also very expensive, here is how I do it:

Code:

bool BoundingBox::pointIntersection(vertex &point)
{
	point.x -= vertexList[1].x;
	point.y -= vertexList[1].y;

    Vector2D v0 = Vector2D( point.x, point.y );
    Vector2D v1 = Vector2D( (vertexList[0].x - vertexList[1].x), (vertexList[0].y - vertexList[1].y));
	
	int val_1  = Dot(v0,v1);	

    if(0 <= val_1 && val_1 <= Dot(v1,v1))
	{
		Vector2D v2 = Vector2D( (vertexList[3].x - vertexList[1].x), (vertexList[3].y - vertexList[1].y));
		int val_2  = Dot(v0,v2);

		if( 0 <= val_2 && val_2 <= Dot(v2,v2) )
			return true;
    }
    
    return false;
}

Sorry if this is the wrong forum or an inappropriate question.

Thanks,

I expect that the compiler will optimise the extra copy away anyway, but note that:

Code:

BoundingBox boundingBox = BoundingBox(0, 0, spriteList[spriteId].getWidth(), spriteList[spriteId].getHeight());
// ...
vertex point = vertex(x,y);

is better written as:

Code:

BoundingBox boundingBox(0, 0, spriteList[spriteId].getWidth(), spriteList[spriteId].getHeight());
// ...
vertex point(x, y);

Also:

Code:

int newX = point.x;
int newY = point.y;

int tempX = newX;
int tempY = newY;

newX = (tempX * cosVal - tempY * sinVal);
newY = (tempY * cosVal + tempX * sinVal);

is probably better written as:

Code:

int newX = (point.x * cosVal) - (point.y * sinVal);
int newY = (point.y * cosVal) + (point.x * sinVal);

And also:

Code:

if(pixelIndex >= getSprite(spriteId).pixelList.size() - 1)
    pixelIndex = getSprite(spriteId).pixelList.size() - 1;

could avoid multiple calls to size() with:

Code:

int size = getSprite(spriteId).pixelList.size();
if(pixelIndex >= size && pixelIndex > 0)
    pixelIndex = size - 1;

But these are small optimisations that may not matter at all, especially since you hinted that getSprite(spriteId).pixelList is a vector and for std::vector size() runs in constant time. Oh, but if it is a vector, then size() returns a size_type, not an int, so you might want to take that into account with pixelIndex as well. But this is a pedantic issue, not an optimisation issue.

EDIT:
Oh yeah, if this code really is time critical, then perhaps your best bet is to profile it.

I expect that the compiler will optimise the extra copy away anyway, but note that:

BoundingBox boundingBox = BoundingBox(0, 0, spriteList[spriteId].getWidth(), spriteList[spriteId].getHeight());
// ...
vertex point = vertex(x,y);

is better written as:

BoundingBox boundingBox(0, 0, spriteList[spriteId].getWidth(), spriteList[spriteId].getHeight());
// ...
vertex point(x, y);

Thanks, didnt know that.

int size = getSprite(spriteId).pixelList.size();
if(pixelIndex >= size && pixelIndex > 0)
pixelIndex = size - 1;

I have tried doing that, but that gives me an error of the vector being out of range

Thanks,

Oh yeah, if this code really is time critical, then perhaps your best bet is to profile it.

Is that possible to do in visual Studio 08?

I have tried doing that, but that gives me an error of the vector being out of range

What exactly did you try for that part? Your current code:

Code:

if(pixelIndex >= getSprite(spriteId).pixelList.size() - 1)
    pixelIndex = getSprite(spriteId).pixelList.size() - 1;

is equivalent in net effect to:

Code:

if(pixelIndex > getSprite(spriteId).pixelList.size() - 1)
    pixelIndex = getSprite(spriteId).pixelList.size() - 1;

which is equivalent to:

Code:

if(pixelIndex >= getSprite(spriteId).pixelList.size())
    pixelIndex = getSprite(spriteId).pixelList.size() - 1;

which is equivalent to my example except that the temporary variable.

Originally Posted by laserlight

What exactly did you try for that part? Your current code:

Code:

if(pixelIndex >= getSprite(spriteId).pixelList.size() - 1)
    pixelIndex = getSprite(spriteId).pixelList.size() - 1;

is equivalent in net effect to:

Code:

if(pixelIndex > getSprite(spriteId).pixelList.size() - 1)
    pixelIndex = getSprite(spriteId).pixelList.size() - 1;

which is equivalent to:

Code:

if(pixelIndex >= getSprite(spriteId).pixelList.size())
    pixelIndex = getSprite(spriteId).pixelList.size() - 1;

which is equivalent to my example except that the temporary variable.

I copy pasted your code and replaced it with mine, but it did not work. I have tried making a temp variable for that part before as well, same thing happes. Really weird

Out of curiosity, what gives you "an error of the vector being out of range"? I do not see the use of the at() member function in your code.

The error is the assert error:
Expression : Vector out of range

With the if() statement you posted pixelIndex gets evaluated to -1 in some cases

I do not see the use of the at() member function in your code.

What is that?

The error is the assert error:
Expression : Vector out of range

Ah, but the assert is not in your example code. What is the assert?

With the if() statement you posted pixelIndex gets evaluated to -1 in some cases

Oh, I made a logic error in my attempted fix of that same edge case logic error. The condition should actually be:
pixelIndex >= size && size > 0

What is that?

Another way of accessing a vector by index, except that it will throw an exception if the index is out of range.

Ah, but the assert is not in your example code. What is the assert?

There is an assert in the vector class that gets triggered.

Oh, I made a logic error in my attempted fix of that same edge case logic error. The condition should actually be:
pixelIndex >= size && size > 0

Same thing happens

Weird =/

There is an assert in the vector class that gets triggered.

An assert in std::vector that gets triggered?

Same thing happens

That's not possible. Have you tried tracing this in a debugger?

The assert is in this file:
stdthrow.cpp

Code:

#ifdef _DEBUG
_CRTIMP2_PURE void __CLRCALL_PURE_OR_CDECL _Debug_message(const wchar_t *message, const wchar_t *file, unsigned int line)
	{	// report error and die
        if(::_CrtDbgReportW(_CRT_ASSERT, file, line, NULL, message)==1)
        {
            ::_CrtDbgBreak();
        }
	}

An assert in std::vector that gets triggered?

Yes

That's not possible. Have you tried tracing this in a debugger?

With the changes you made, pixelIndex sometimes equal -1

With the changes you made, pixelIndex sometimes equal -1

So you are saying that with:

Code:

if(pixelIndex >= getSprite(spriteId).pixelList.size() - 1)
    pixelIndex = getSprite(spriteId).pixelList.size() - 1;

pixelIndex is never equal to -1, but with:

Code:

int size = getSprite(spriteId).pixelList.size();
if(pixelIndex >= size && size > 0)
    pixelIndex = size - 1;

pixelIndex is sometimes equal to -1?

For that to happen, it means that size = 0, since only then pixelIndex = 0 - 1 = -1. But this cannot happen since size = 0 means that the expression (pixelIndex >= size && size > 0) evaluates to false.

However, there is a catch: if pixelIndex was -1 to begin with, pixelIndex >= size would be false, so nothing will happen, except that pixelIndex remains at -1. Are you sure that (newY * getSprite(spriteId).getWidth() + newX) is always non-negative?

In Visual Studio, even the subscript operator will trigger an assert if out-of-bounds, at least in debug.
As for profiler, there's lots of them out there. CodeAnalyst is a good one that's free.

Originally Posted by h3ro

Is that possible to do in visual Studio 08?

Is seems to be available
http://msdn2.microsoft.com/en-us/vs2...vAdvancedTools
only in the Team suit version of the VS

So you need some external tool probably