Алгоритм оптимизации очереди Blit

Question

Я ищу реализовать модуль, который управляет блиц-очередью. Существует единственная поверхность, и части этой поверхности (ограниченные прямоугольниками) копируются в другое место на поверхности:

add_blt(rect src, point dst);

В очередь может быть помещено любое количество операций по порядку. В конце концов пользователь очереди перестанет отправлять сообщения и запросит оптимальный набор операций, которые он фактически должен выполнять на поверхности. Задача модуля - убедиться, что ни один пиксель не скопирован без необходимости.

Это становится сложно из-за частичного совпадения. Блит может повторно копировать ранее скопированный пиксель. В идеале операции блита должны быть разделены на этапе оптимизации таким образом, чтобы каждый блок шел к своему конечному месту с помощью одной операции.

Это сложно, но не невозможно собрать это вместе. Я просто пытаюсь не изобретать велосипед.

Я огляделся в сети, и единственное, что я нашел, была SDL_BlitPool Library , которая предполагает, что исходная поверхность отличается от места назначения. Он также выполняет большую работу, казалось бы, излишне: регионы и подобные строительные блоки - это данность. Я ищу что-то более высокого уровня. Конечно, я не собираюсь смотреть лошадям в подарок, и я также не возражаю против выполнения реальной работы ... Если кто-то может выдвинуть основную идею, которая делает эту проблему менее сложной, чем правильно теперь это тоже было бы здорово.

РЕДАКТИРОВАТЬ:

Думая об ответе Ааронастерлинга ... может ли это сработать?

• Реализация настроенного кода обработчика области, который может поддерживать метаданные для каждого прямоугольника, который он содержит. Когда обработчик области разделяет прямоугольник, он автоматически связывает метаданные этого прямоугольника с результирующими под прямоугольниками.

• Когда запускается оптимизация, создайте пустую область, обработанную указанным выше настраиваемым кодом, назовите это master region

• Итерация по очереди blt и для каждой записи:

  • Пусть srcrect будет исходным прямоугольником для blt изученного бенга

  • Получите пересечение srcrect и master region в temp region

  • Удалить temp region из master region, поэтому master region больше не покрывает temp region

  • Повысить srcrect до региона (srcrgn) и вычесть temp region из него

  • Смещение temp region и srcrgn с вектором текущего blt: их объединение будет охватывать область назначения текущего blt

  • Добавьте к master region все ректы в temp region, сохранив исходные метаданные источника (первый шаг добавления текущего blt к master region)

  • Добавьте к master region все повторы в srcrgn, добавив информацию об источнике для текущего blt (второй шаг добавления текущего blt к master region)

• Оптимизируйте master region, проверяя, имеют ли смежные под прямоугольники, которые являются кандидатами на слияние, одинаковые метаданные. Два под прямоугольника являются кандидатами на слияние, если (r1.x1 == r2.x1 && r1.x2 == r2.x2) | (r1.y1 == r2.y1 && r1.y2 == r2.y2). Если да, объедините их.

• Перечислять под прямоугольники master region. Каждый возвращаемый прямоугольник является оптимизированным местом назначения blt-операции. Соответствующие метаданные являются источником операции blt.

Answer 1

Одна идея, которая приходит в голову, состоит в том, чтобы сохранить определяющие точки прямоугольников, которые добавляются в квад-дереве (или в какой-либо другой структуре, которая обеспечит эффективное обнаружение столкновений). Так что теперь, когда вы добавляете новый прямоугольник, вы можете проверить его на столкновения. Идея состоит в том, что когда новый прямоугольник сталкивается со старым прямоугольником, вы разрешаете столкновения, разбивая старый прямоугольник на 4, 3 или 2 новых прямоугольника, которые не включают часть, которая пересекает вновь добавленный прямоугольник. Мы знаем, что старый прямоугольник не пересекался ни с какими другими старыми прямоугольниками, и поэтому, поскольку в нем содержатся вновь созданные, мы знаем, что они тоже не пересекаются, поэтому вам не нужно выполнять обнаружение столкновений с ними.

Например, начиная с:

и добавление одного прямоугольника:

разрешит:

Здесь один из старых прямоугольников разбивается на два новых прямоугольника, а другой - на три.

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

Answer 2

SDL_BlitPool .. ах, что моя ранняя работа.

Путь BlitPool -

for_each(down to up) {
 if (overlapped) {
  1 split back-surface
   1-1 calculate overlap code
   1-2 add sub-rectangle (use overlap code)
   1-3 delete divided-surface
 }
}

в основном это все.

"Код перекрытия" - это 0-15 целых чисел.

Вы знаете, шаблон перекрытия - это всего лишь 16 шаблонов.

http://bitbucket.org/sharow/sdl_blitpool/src/ea6c02fef26f/resource/SDL_BlitPool_02.png

Код перекрытия - 4-битное (0-15) значение.

Первые 2 бита - это ось Y, а хвостовые 2 бита - это ось X (в SDL_BlitPool).

Каждое 1-битное значение является просто значением MSB.

Это визуализировать как ...

http://bitbucket.org/sharow/sdl_blitpool/src/ea6c02fef26f/resource/SDL_BlitPool_01.png

на этом изображении: MSB == направление стрелки.

Я думал, что есть лучшая библиотека для другого. хм, я хочу переписать это ...

извините за мой уровень английского.