/// A simple 2D point
class Point2D {
int X, Y;
};
/// The image class
class Image2D {
/// some stuff, like member variables and so on
Point2D Tile(const Point2D& coord) const
{
int x = coord.X % (int)m_width;
int y = coord.Y % (int)m_height;
if(x < 0)
{
x += m_width;
}
if(y < 0)
{
y += m_height;
}
return Point2D(x, y);
};
Point2D Mirror(const Point2D& coord) const
{
Point2D result = Tile(coord);
// handle negative coordinates
if(coord.X < 0)
{
int x = -coord.X - 1; // note that negative coords do not start with 0
// even tiles are flipped
if(((x / m_width) % 2) == 0)
{
result.X = m_width - result.X - 1;
}
}
// odd tiles are flipped
else if(((coord.X / m_width) % 2) != 0)
{
result.X = m_width - result.X - 1;
}
// handle negative coordinates
if(coord.Y < 0)
{
int y = -coord.Y - 1; // note that negative coords do not start with 0
// even tiles are flipped
if(((y / m_height) % 2) == 0)
{
result.Y = m_height - result.Y - 1;
}
}
// odd tiles are flipped
else if(((coord.Y / m_height) % 2) != 0)
{
result.Y = m_height - result.Y - 1;
}
return result;
};
};Code that needs to be optimized
Author
Hi there,
First some introductory words: I'm writing a graphics related application that works on 2D images. An image needs to be tiled (i.e. repeated in an infinite plane) or mirrored (i.e. repeated in a way that every odd tile is flipped in x and y respectively).
I've an image class that can take any coordinate (also outside the image's dimensions and negative). To access a pixel, the coordinate is "brought back" to the corresponding coordinate (depending on the tiling or mirroring).
This "bringing back" code gets executed millions of times and is the bottle neck of the application. Since the running time takes up to half an hour I try to optimize my code.
Below you find my current implementation. My question is whether it is possible to optimize this code (I don't know how) or to compute the coordinates in a different -- more efficient -- way.
Many thanks and Cheers,
Data
For the "tile" option all you need to do is a simple modulus. The conditionals aren't needed - modulus should have well-defined behaviour for negative numbers. All that should be needed is:
If m_width and m_height are floats, consider storing them as integers instead. Float to integer conversions are computationally expensive. Also, you may want to consider avoiding returning large data types - I usually don't return anything larger than 4 bytes. But in this case it should be fine (8 bytes).
Although I'm not sure how to do mirror mode.
return Point2D(coord.x % m_width, y % m_height);If m_width and m_height are floats, consider storing them as integers instead. Float to integer conversions are computationally expensive. Also, you may want to consider avoiding returning large data types - I usually don't return anything larger than 4 bytes. But in this case it should be fine (8 bytes).
Although I'm not sure how to do mirror mode.
Author
Quote:Original post by Sc4Freak
For the "tile" option all you need to do is a simple modulus. The conditionals aren't needed - modulus should have well-defined behaviour for negative numbers. All that should be needed is:return Point2D(coord.x % m_width, y % m_height);
I tried it out and actually the result of a modulus is negative if the left hand side is negative. So I still need the if statements...
Quote:Original post by data2Quote:Original post by Sc4Freak
For the "tile" option all you need to do is a simple modulus. The conditionals aren't needed - modulus should have well-defined behaviour for negative numbers. All that should be needed is:return Point2D(coord.x % m_width, y % m_height);
I tried it out and actually the result of a modulus is negative if the left hand side is negative. So I still need the if statements...
Yes you're absolutely right they can't just be left out, or you still get negative values.
You have a few float to int conversions in there by the looks of it. I suggest adding extra member variables m_intHeight, and m_intWidth which hold the height and width pre-converted to integers. That should speed it up a lot, assuming they are floats or doubles.
Then, by expanding the definition of Tile into Mirror, we are able to take advantage of the fact that coord.X in Mirror is only negative when x in Tile is negative (same for coord.Y and y). This finally does remove those if statements.
Next we replace % 2 with & 1, in case we are using a braindead compiler here.
I've then grouped all the X and Y calculations together.
This brings me to the below code. Note that you might not need 'Tile' any more if it isn't used elsewhere. There is certainly more that can be done though. If the height and/or width is always power of two then it can be sped up much more.
Point2D Tile(const Point2D& coord) const { int x = coord.X % m_intWidth; int y = coord.Y % m_intHeight; if(x < 0) { x += m_intWidth; } if(y < 0) { y += m_intHeight; } return Point2D(x, y); }; Point2D Mirror(const Point2D& coord) const { Point2D result; result.X = coord.X % m_intWidth; // handle negative coordinates if (coord.X < 0) { result.X += m_intWidth; int x = -coord.X - 1; // note that negative coords do not start with 0 // even tiles are flipped if (((x / m_intWidth) & 1) == 0) { result.X = m_intWidth - result.X - 1; } } // odd tiles are flipped else if ((coord.X / m_intWidth) & 1) { result.X = m_intWidth - result.X - 1; } result.Y = coord.Y % m_intHeight; // handle negative coordinates if (coord.Y < 0) { result.Y += m_intHeight; int y = -coord.Y - 1; // note that negative coords do not start with 0 // even tiles are flipped if (((y / m_intHeight) & 1) == 0) { result.Y = m_intHeight - result.Y - 1; } } // odd tiles are flipped else if ((coord.Y / m_intHeight) & 1) { result.Y = m_intHeight - result.Y - 1; } return result; };[Edited by - iMalc on November 21, 2007 12:15:20 AM]
Quote:Original post by iMalc
I've then grouped all the X and Y calculations together.
*** Source Snippet Removed ***
You're better off not doing that. Leave result.Y = coord.Y % m_intHeight; at the start of the function and let the compiler schedule the divide early, before you need the result for the Y-half of the function. The memory moves for result.Y also give you some space between the time result.X is first calculated and the time it is needed.
Might I suggest providing a line iterator? It's much shorter to compute the "next pixel to the right" given the current pixel, than it is to compute the "texture-space coordinates of pixel x+1", so looping over the pixels in a give line by extracting the iterator to that line's start, and the incrementing it to traverse all pixel addresses should provide an increase in performance.
Also, note that mirroring an image can be resolved simply by creating an image twice as large and manually mirroring the relevant parts.
Also, note that mirroring an image can be resolved simply by creating an image twice as large and manually mirroring the relevant parts.
Actually, looking over your code again, I'm thinking now that m_height and m_width are already integers. Those (int) casts are just there to fool us right?
If you enforce power of 2 textures, you could use:
return Point2D(coord.x & (m_Width - 1), coord.y & (m_Height - 1));
for tiling.
return Point2D(coord.x & (m_Width - 1), coord.y & (m_Height - 1));
for tiling.
Author
Thanks for all the replies and suggestions.
(1) m_width and m_height are unsigned int. That's why there are casts
(2) The image is not necessarily pow2, even though often the case (I might think of introducing special routines for pow2 images -- any suggestions of how to optimize Mirror() in case of pow2 textures?)
(3) I need to access pixels very randomly and do not really iterate over them. So an iterator wouldn't be of much help. However, I introduced direct access to the raw data and can loop over the memory with pointers if I have to.
@iMalc The idea of moving the Tile function's calculations into Mirror looks quite nice. It is not that much code, so I don't really need to call an extra function.
@outRider What is that with the compiler optimizations? I never think of how the compiler optimizes code, so I'm curious...
Cheers,
data
[Edited by - data2 on November 21, 2007 3:50:11 PM]
(1) m_width and m_height are unsigned int. That's why there are casts
(2) The image is not necessarily pow2, even though often the case (I might think of introducing special routines for pow2 images -- any suggestions of how to optimize Mirror() in case of pow2 textures?)
(3) I need to access pixels very randomly and do not really iterate over them. So an iterator wouldn't be of much help. However, I introduced direct access to the raw data and can loop over the memory with pointers if I have to.
@iMalc The idea of moving the Tile function's calculations into Mirror looks quite nice. It is not that much code, so I don't really need to call an extra function.
@outRider What is that with the compiler optimizations? I never think of how the compiler optimizes code, so I'm curious...
Cheers,
data
[Edited by - data2 on November 21, 2007 3:50:11 PM]
I'm thinking that maybe you should mirror the entire texture, and save the mirrored texture? then mirroring reduces to a modulus as well.
Sometimes it is not the algorithm that needs to be optimized, but the design. Are you sure you need to do this millions of times?
Sometimes it is not the algorithm that needs to be optimized, but the design. Are you sure you need to do this millions of times?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
