Как оптимизировать алгоритм поворота изображения на угол, кратный 90 гр?

Question

[alexey_prokopyev]

Есть изображение в виде массива данных размером w х h. Алгоритм должен поворачивать изображение на угол 90, -90 и 180 градусов.

Для таких углов синусы и косинусы вырождаются в простой алгоритм, например, для 90 градусов:

new_w = h;
new_h = w;
for (int i = 0; i < h; i++)
{
    for (int j = 0; j < w; j++)
    {
        dest[j * new_w + new_w - i - 1] = source[i * w + j];
    }
}

Скорость такого копирования в 4-5 раз меньше скорости копирования без поворота. Причина, скорее всего, в непоследовательном доступе к памяти при записи в dest: запись идет по элементам, отстоящих друг от друга на размер строки изображения.
Кто знает способы ускорения случайного доступа к памяти?

Answer 1

[Илья Попов]

Эта задача хоть и не полностью идентична, но похожа на задачу о траспонированиии матрицы, и к ней применимы те же методы оптимизации. Для улучшения доступа к памяти можно разбивать на блоки.

Посмотрите этот ответ на StackOverflow, особенно два метода в самом конце:
stackoverflow.com/a/16743203

Ещё можете глянуть вот эту статью в википедии: In-place matrix transposition