0

I have a custom image object, which is organised in tiles of fixed size, disposed in a tile grid. Let's assume, for instance, that the fixed tileSize is 256 pixels (each tile is a subimage of 256x256 pixels), and that my global image is 1000x500 pixels: this results in a tile grid of 4x2 tiles of 256x256 pixels.

Now, given a point in the global image coordinates, this is how I convert to tile coordinates (i.e., the tile position in the tile grid, plus the pixel position inside that pixel): 

struct Point {
  int x;
  int y;
}

Point pGlobal = (...);

// Grid coordinates of the tile containing pGlobal
Point pTileGrid = Point(pGlobal.x / tileSize, pGlobal.y / tileSize);
// Pixel inside that tile that contains pGlobal
Point pTile     = Point(pGlobal.x % tileSize, pGlobal.y % tileSize);

The problem is that this is painfully slow. How can I optimize this?

Thank you in advance. If I did not explain myself correctly in any point please ask me to improve my formulation.

manatttta
  • 3,054
  • 4
  • 34
  • 72
  • 1
    Why won't you post a minimal example so that people can jump into it in O(1) steps? :) – gsamaras Jul 29 '16 at 00:11
  • Are your tile sizes always a factor of two? – aichao Jul 29 '16 at 00:14
  • If this is slow for you, you are probably repeating this calculation in a tight loop. That would be wrong. – n. m. could be an AI Jul 29 '16 at 00:37
  • If `tileSize` is a power of 2, you should consider bit shifting and bit masking. – Thomas Matthews Jul 29 '16 at 00:41
  • Please check [this SO page](http://stackoverflow.com/questions/2661697/most-optimized-way-to-calculate-modulus-in-c) as it makes some good points regarding your problem. – aichao Jul 29 '16 at 00:53
  • If this is slow, your problem may be with your `Point` class - can you show us that? – Michael Anderson Jul 29 '16 at 01:45
  • To be clear - your Point class should be relatively trivial, and not perform any allocations. It should be coded such that you get good move / copy performance too. – Michael Anderson Jul 29 '16 at 01:47
  • @ThomasMatthews yes I am enforcing powers of two in tile size. can you guide me on some optimizations? – manatttta Jul 29 '16 at 08:50
  • @MichaelAnderson thank you for pointing that out. `Point` is actually a simple struct, see the updated question :) – manatttta Jul 29 '16 at 08:51
  • Use (struct div_t) [http://www.cplusplus.com/reference/cstdlib/div_t/] in order to get quotient and reminder in one call. – sameerkn Jul 29 '16 at 09:11
  • @sameerkn do you have any idea if that's faster or does it internally do the same? – manatttta Jul 29 '16 at 09:19
  • @manatttta: Having gone through following answers http://stackoverflow.com/questions/4565272/why-use-div-or-ldiv-in-c-c, result of `/` and `%` can be calculated in one call. – sameerkn Jul 29 '16 at 09:27
  • Depending upon number of times you do conversion from global co-ordinates to tile specific co-ordinates, you can with few MBs of extra memory can cache all the conversion results once. – sameerkn Jul 29 '16 at 09:36
  • A right shift will divide by a power of 2. For example, "4 >> 1 == 2". Usually shifting is a lot faster than a division. – Thomas Matthews Jul 29 '16 at 14:50

0 Answers0