Как выполнить сортировку пикселей на графическом процессоре

Question

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

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

Заранее спасибо

Answer 1

Но есть размытие шейдеров, которые в состоянии сделать гауссово размывание путем усреднения пикселей вокруг в настоящее время обработки пикселей

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

Answer 2

GPU Gems 2 Chapter 46 описывает сортировку на графическом процессоре.

Рассмотрим, как можно использовать алгоритм Бурлящий сортировки:

Заходя все N пикселей столбца для сортировки по каждому выходному пикселю, то это будет очень медленно, так как каждый выходной пиксель считывает N (с N^2 - сильно зависит от кеширования), и это большой доступ к памяти. Но это сработает, и этот код может действительно иметь смысл.

Если вы получаете доступ только к 2 входным пикселям на выходной пиксель, то вы можете эффективно «поменять» пару соседних пикселей на каждом проходе. Это может потребовать до N проходов, чтобы вытеснить пиксель N шагов. (Вы можете рассчитывать свопы и «ломаться» раньше, используя запрос окклюзии)

С помощью сочетания методов вы можете пробовать k пикселей за раз, позволяя пикселю перемещаться до k шагов за проход, что требует N/k проходов и более эффективно использовать ресурсы.

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

Но есть много чего знать, чтобы успешно создать эффективную реализацию для алгоритма GPU - больше, чем можно здесь в целом обсуждать. И вы можете захотеть перейти к реализации CUDA, а не glsl. Но тогда есть банковские конфликты, перекосы, кеширование, выборка, swizzling. Нет быстрого ответа.

Я предлагаю вам попробовать, а затем задать более конкретный вопрос, когда вы застряли.