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.

Quote:

---

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.

Quote:

---

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,

Quote:

---

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?

Quote:

---

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.

Quote:

---

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

Quote:

---

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

---

What is that?

Quote:

---

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?

Quote:

---

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

Quote:

---

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.

Quote:

---

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.

Quote:

---

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 =/

Quote:

---

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

---

An assert in std::vector that gets triggered?

Quote:

---

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();
        }
        }

---

Quote:

---

An assert in std::vector that gets triggered?

---

Yes

Quote:

---

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

---

With the changes you made, pixelIndex sometimes equal -1

Quote:

---

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.

Quote:

---

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

Do the sprites change rotation every frame? Because if not, a far more effective optimization than all this micro-stuff would be to cache the rotated version and just blit it in subsequent uses.