Оптимизация рисования перекрывающихся прямоугольников

Ответ 1

Вы делаете очень неправильное предположение, что производительность, которую вы получите в браузере на рабочем столе, каким-то образом определит производительность вашего iPhone. Вы должны понимать, что аппаратное обеспечение iPhone реализует отложенное отрисовку на основе плитки, что означает, что шейдер фрагмента используется в любом случае очень поздно. Как говорят сами Apple ( "Не тратьте время на сортировку объектов времени перед процессором" ), Z-сортировка ваших примитивов даст вам небольшое увеличение производительности.

Но мое предложение: если изменение цвета дорогое, просто не меняйте цвет: передайте его как атрибут вершины и объедините поведение в один супер-шейдер, чтобы вы могли рисовать все в одной или нескольких партиях, даже не сортируя, Затем проверьте и определите оптимальный размер партии для вашей платформы.

Ответ 2

Выберите цвета, а не поля!

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

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

График зависимости

Начните с построения графа зависимостей "ложь под", где каждый цветной прямоугольник представлен вершиной и есть дуга (стрелка) от v до u, если прямоугольник v перекрывает прямоугольник u и лежит под ним. Моя первая мысль заключалась в том, чтобы использовать это для построения графика зависимостей "нужно нарисовать до", найдя транзитивное замыкание, но на самом деле нам не нужно это делать, поскольку все ниже описанные алгоритмы - это то, Маскируемые вершины - это вершины, которые не имеют предшественников (в дугах), и переход транзитивного замыкания не изменяет, имеет ли вершина 0 в дугах или нет.

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

Ускорение

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

Алгоритмы

Эти наблюдения предполагают два возможных алгоритма:

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

• Более медленный, точный алгоритм DP или рекурсивный:. Для каждого возможного полезного цвета c рассмотрим граф зависимостей, созданный путем покраски всех окрашиваемых c-цветных блоков следующим образом:

  Пусть f (g) - минимальное количество изменений цвета, необходимых для рисования всех ящиков в графе зависимости g. Тогда

  f (g) = 1 + min (f (p (c, g)))

  для всех полезных цветов c, где p (c, g) - граф зависимостей, созданный путем рисования всех красящих ящиков цвета c. Если G - граф зависимостей исходной задачи, то f (G) будет минимальным числом изменений. Сам выбор цвета может быть восстановлен путем прослеживания назад через матрицу затрат DP.

  f (g) может быть memoised, чтобы создать динамический алгоритм программирования, который экономит время, когда две разные перестановки цветов выбирают один и тот же график, что часто случается. Но может быть и то, что даже после DP этот алгоритм может занять некоторое время (и, следовательно, пространство), экспоненциальное по числу ящиков... Я подумаю о том, можно ли найти более удобную ссылку.

Ответ 3

Здесь есть возможность. Вам нужно будет сравнить его, чтобы увидеть, действительно ли это улучшение.

For all rectangles, back to front:
  If this rectangle has been marked as drawn, skip to the next one
  Set a screen-sized unseen surface to all black
  Call this rectangle color "the color"
  For rectangles starting with this one and proceeding toward the front
    If (this rectangle color is the color and
        all the pixels of this rectangle on the unseen are black) then
      Add this rectangle to the to-draw list
    Draw a white rectangle with this rectangle shape on the unseen surface
    If the unseen surface is more than half white, break
  For all rectangles on the to-draw list:
    Draw the rectangle
    Mark it as drawn

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

Ответ 4

Начните с рисования в произвольном (но правильном) порядке, например, в строгом порядке z. При рисовании каждого кадра учитывайте количество изменений цвета или, возможно, фактическое время, которое занимает полный кадр. Каждый кадр, попробуйте поменять порядок двух прямоугольников. Прямоугольники, подлежащие обмену, не должны перекрываться, поэтому их можно нарисовать в любом порядке без нарушения правильности; кроме того, они могут быть выбраны случайным образом или выполнить линейный проход по списку, или... Если выполнение свопа уменьшает количество изменений цвета, сохраните новый порядок, если он не вернет его и попробуйте другой обмен в следующий кадр. Если выполнение свопа не уменьшает и не увеличивает количество изменений цвета, сохраните его с коэффициентом 50%. Для любых прямоугольников, которые не перекрывались в предыдущем кадре, но которые начинают перекрываться из-за перемещения, просто обменивайте их так, чтобы они находились в порядке z.

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

Ссылаясь на чертеж, у вас есть: начальный порядок выбивки выбран случайным образом: 1,6,2,4,5,8,3,7 (5 изменений цвета). Обмен 5,8. Новый порядок: 1,6,2,4,8,5,3,7 (4 изменения цвета) = > Сохраняйте новый порядок.