Thread: Help me optimize this function

  1. #1
    Registered User
    Join Date
    Oct 2006
    Location
    UK/Norway
    Posts
    485

    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,
    Last edited by h3ro; 02-24-2008 at 08:45 AM.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.
    Last edited by laserlight; 02-24-2008 at 08:58 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Oct 2006
    Location
    UK/Norway
    Posts
    485
    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,

  4. #4
    Registered User
    Join Date
    Oct 2006
    Location
    UK/Norway
    Posts
    485
    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?

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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 Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Registered User
    Join Date
    Oct 2006
    Location
    UK/Norway
    Posts
    485
    Quote Originally Posted by laserlight View Post
    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

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    Registered User
    Join Date
    Oct 2006
    Location
    UK/Norway
    Posts
    485
    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?

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    Registered User
    Join Date
    Oct 2006
    Location
    UK/Norway
    Posts
    485
    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 =/

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #12
    Registered User
    Join Date
    Oct 2006
    Location
    UK/Norway
    Posts
    485
    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

  13. #13
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  14. #14
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    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 Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  15. #15
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    Quote Originally Posted by h3ro View Post
    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
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Compiling sample DarkGDK Program
    By Phyxashun in forum Game Programming
    Replies: 6
    Last Post: 01-27-2009, 03:07 AM
  2. Seg Fault in Compare Function
    By tytelizgal in forum C Programming
    Replies: 1
    Last Post: 10-25-2008, 03:06 PM
  3. Another syntax error
    By caldeira in forum C Programming
    Replies: 31
    Last Post: 09-05-2008, 01:01 AM
  4. Replies: 28
    Last Post: 07-16-2006, 11:35 PM
  5. const at the end of a sub routine?
    By Kleid-0 in forum C++ Programming
    Replies: 14
    Last Post: 10-23-2005, 06:44 PM