Алгоритмические и программные средства компрессии текстур на графических процессорах тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Перминов, Илья Валентинович

• Перминов, Илья Валентинович
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Перминов, Илья Валентинович

Содержание

Список сокращений и обозначений

Введение

1 Анализ архитектуры графических процессоров, современных форматов

и алгоритмов сжатия текстур

1.1 Особенности текстурного сжатия

1.1.1 Основные требования к алгоритмам и форматам компрессии-декомпрессии текстур

1.1.2 Сжатие для ускорения загрузки

1.1.3 Качество и скорость сжатия

1.2 Ранние работы, связанные с текстурным сжатием

1.3 Семейство S3TC

1.3.1 Формат блока ВС 1 (S3TC/DXT1)

1.3.2 Особенности форматов ВС6Н и ВС7

1.3.3 Формат блока ВС7

1.4 Формат ASTC

1.4.1 Метод кодирования BISE

1.4.2 Прочие особенности

1.4.3 Формат блока ASTC

1.5 Анализ форматов сжатия текстур и особенностей алгоритмов сжатия

1.6 Обобщённая схема компрессии

1.7 Метрики ошибок сжатия

1.8 Существующие методы сжатия текстур в формате ВС 1

1.8.1 Быстрое сжатие

1.8.2 Метод ClusterFit

1.8.3 Алгоритм сжатия LSDxt

1.8.4 Сравнение качества

1.9 Существующие методы сжатия текстур в формате ASTC

1.9.1 Процедура компрессии для фиксированного типа блока

1.9.2 Процедура поиска наилучшего деления на регионы

1.10 Архитектура графического процессора

1.10.1 Модель вычислений OpenCL

1.10.2 Значимые отличия от классических идеализированных параллельных архитектур

1.11 Гетерогенные архитектуры

1.12 Выводы

2 Параллельный алгоритм сжатия текстур в формате ВС1

2.1 Модификация алгоритма LSDxt

2.1.1 Модификация этапа сортировки

2.1.2 Отображение групп потоков на аппаратные SIMD-вектора

2.1.3 Расположение данных в локальной памяти

2.1.4 Использование регистровой памяти

2.2 Выводы

3 Межкадровая (динамическая) компрессия текстур

3.1 Стандарты и программные интерфейсы Direct3D и OpenGL

3.1.1 Графический конвейер Direct3D 11

3.2 Традиционный графический конвейер

3.3 Возможности межкадрового сжатия текстур в Direct3D и OpenGL

3.4 Графический конвейер с тайловой архитектурой

3.5 Выводы

4 Сжатие текстур с высокой глубиной цвета

4.1 Ограничения представления цвета с глубиной 8 бит

4.2 Критерий точности сохранения градиентных цветов

4.3 Модификация кодека gpu_bc7

4.4 Выводы

5 Последовательно-параллельный алгоритм сжатия текстур в формате ASTC

5.1 Анализ работы кодека ASTC Evaluation Codec

5.1.1 Быстродействие в различных режимах

5.2 Адаптация алгоритма для работы в гетерогенной среде

5.2.1 Компиляция кода для архитектуры х64

5.2.2 Результаты профилирования производительности

5.2.3 Объединение блоков в пакеты

5.2.4 Компиляция во время исполнения

5.2.5 Изменение порядка этапов сжатия

5.3 Выбор размера пакета

5.4 Сравнение оригинального и предлагаемого кодеков

5.5 Выводы

Заключение

Литература

А Дополнительные форматы текстурной компрессии семейства S3TC

А.1 Формат блока ВС2 (DXT2/DXT3)

А.2 Формат блока ВСЗ (DXT4/DXT5)

А.З Формат блока ВС4 (ATI l/3Dc+)

А.4 Формат блока ВС5 (ATI2/3Dc)

A.5 Формат блока ВС6Н

В Семейство форматов текстурной компрессии ETC

B.1 Формат блока PACKMAN

В.2 Формат блока ETC 1 (iPACKMAN)

В.З Формат блока ЕТС2

B.4 Формат блока ЕАС

С Семейство форматов текстурной компрессии PVRTC

C.1 Формат блока PVRTC 4Ьрр

С.2 Формат блока PVRTC 2bpp

С.З Формат блока PVRTC2 4bpp

Список сокращений и обозначений

Сокращение Расшифровка Перевод

ВС Вычислительная система

ГП Графический процессор

ГУ Графический ускоритель

ОС Операционная система

по Программное обеспечение

ЦП Центральный процессор

Ьрр bits per pixel Среднее количество бит на пиксель

CPU Central Processing Unit Центральный процессор

CRCW Concurrent Read Concurrent Write Тип общей памяти с одновременным чтением и одновременной записью

CRCW-C CRCW consistent-write submodel Подтип общей памяти CRCW с одновременной записью общего назначения

CRCW-P CRCW with priority write Подтип общей памяти CRCW с одновременной приоритетной записью

GPGPU General Purpose computing on GPU Вычисления общего назначения на ГП

GPU Graphics Processing Unit Графический процессор

HDR High Dynamic Range Широкий динамический диапазон

hQ Heterogeneous Queuing Механизм гетерогенных очередей

HSA Heterogeneous System Architecture Гетерогенная системная архитектура

hUMA Heterogeneous Uniform Memory Access Однородный доступ к памяти в гетерогенных системах

IMR Immediate Mode Rendering Традиционная полнокадровая архитектура графического конвейера

LDR Low Dynamic Range Стандартный динамический диапазон

MIMD Multiple Instruction Multiple Data множество потоков команд, множество потоков данных

MSE Mean Square Error Среднеквадратическая ошибка

Сокращение Расшифровка Перевод

PRAM Parallel Random-Access Machine Параллельная машина с произвольным доступом к памяти

PSNR Peak Signal-to-Noise Ratio Пиковое отношение сигнала к шуму

RMSE Root Mean Square Error Корень среднеквадратической ошибки

SIMD Single Instruction Multiple Data Одиночный поток команд, множественный поток данных

SIMT Single Instruction Multiple Threads Одиночный поток команд, множество потоков исполнения

TBDR Tile Based Deffered Rendering Тайловая архитектура графического конвейера с отложенным исполнением шейдеров

TBR Tile Based Rendering Тайловая архитектура графического конвейера

TDP Thermal Design Power Расчётная тепловая мощность

Введение диссертации (часть автореферата) на тему «Алгоритмические и программные средства компрессии текстур на графических процессорах»

Введение

Актуальность темы. Принимая во внимание огромную вычислительную мощность современных графических процессоров в 5-8 Tflops, пропускная способность видеопамяти свыше 300 ГБ/с зачастую становится узким местом. Кроме этого, подключение по шине PCIe со скоростью до 16 ГБ/с также может являться узким местом при доставке данных до устройства. Использование сжатия данных существенно снижает требования к объему видеопамяти и пропускной способности интерфейса. Также серьезно снижаются энергозатраты на передачу данных.

В трёхмерной компьютерной графике основными классами данных, потребляющих около 80% ресурсов памяти и интерфейса, являются текстуры и G-буферы, которые также можно рассматривать как особый вид текстур. В простейшем случае текстуры представляют собой двухмерное изображение, накладываемое на трёхмерный объект, улучшающие визуальную детализацию трехмерных объектов без усложнения геометрии. Кроме информации о цвете, текстура может содержать карту высот, нормалей, отражений и прочую информацию [1].

Широкое распространение получили различные технологии компрессии текстур. При этом текстура передается и хранится в памяти в сжатом виде, и распаковывается непосредственно внутри графического процессора (ГП), как правило, между кэшпамятью уровней L1 и L2. Такой подход позволяет не только уменьшить занимаемый текстурами объем памяти, но и снизить требования к пропускной способности. Кроме этого, сжатие позволяет снизить энергопотребление (за счёт снижения трафика на интерфейсе ГПопамять), что существенно для мобильных устройств.

Ввиду специфики применения и необходимости произвольного доступа к отдельным элементам текстуры, распространённые графические форматы, такие как JPEG и PNG, и универсальные алгоритмы сжатия не подходят для текстур [2]. Поэтому в данной области применяются специально разработанные блочные схемы сжатия, такие как S3TC и PVRTC, обеспечивающие сжатие с потерями и фиксированный коэффициент сжатия [2,3].

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

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

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

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

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

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

Для достижения поставленной цели требуется решить следующие задачи:

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

2. Разработать подходы, снижающие затраты на межкадровое сжатие текстур.

3. Разработать параллельную модификацию алгоритма сжатия текстур для исполнения на графических процессорах в темпе генерации кадров.

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

5. Провести экспериментальные исследования и оценить эффективность предложенных подходов.

Основные положения, выносимые на защиту:

1. Параллельный алгоритм и программная реализация сжатия текстур в формате БХТ/ВО, имеющая высокую эффективность исполнения на графическом процессоре за счёт распараллеливания процесса кодирования отдельного блока изображения и исключения операций доступа к памяти, приводящим к конфликтам.

2. Метод сжатия текстур, позволяющий использовать существующие форматы для хранения текстур с высокой глубиной цвета (более 8 бит на компоненту) за счёт изменения этапа квантования и деквантования ключевых цветов.

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

4. Последовательно-параллельный алгоритм и программная реализация сжатия текстур в формате АБТС, нацеленная на одновременную работу алгоритма на ядрах ЦП и ГП в гетерогенных системах с общей виртуальной и физической памятью и обеспечивающая тем самым повышение производительности в 3-5 раз.

Научная новизна:

1. Разработана параллельная модификация алгоритма сортировки, нацеленная на работу на графическом процессоре и позволяющая исключить повторяющиеся элементы. Предлагаемый подход характеризуется отсутствием дивергенции потоков исполнения (за счёт отсутствия условных переходов) и позволяет резко снизить количество конфликтов при обращении к разделяемой памяти.

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

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

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

4. На основе данного критерия предложена модификация соответствующей схемы сжатия для сохранения текстур с высокой глубиной цвета.

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

6. Предложен метод снижения затрат на межкадровую компрессию текстур за счёт избавления от избыточных операций на уровне программного интерфейса (API).

7. Разработана последовательно-параллельная модификация алгоритма и программная реализация сжатия текстур в формате ASTC, использующая особенности новейших гетерогенных архитектур для ускорения процесса компрессии.

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

Апробация работы. Основные результаты работы докладывались на следующих конференциях: III научно-практическая конференция молодых ученых "Вычислительные системы и сети (Майоровские чтения)" (Санкт-Петербург, 2011), I и II Всероссийский конгресс молодых ученых (Санкт-Петербург, 2012-2013), VI Международная конференция "Параллельные вычисления и задачи управления" РАСО'2012 (Москва, ИПУ РАН, 2012), IV Московский суперкомпьютерный форум МСКФ-2013 (Москва, 2013), 23я Международная Конференция по Компьютерной Графике и Зрению GraphiCon'2013 (Владивосток, 2013).

Внедрение результатов работы. Материалы диссертации используются в качестве рабочих документов в корпорации AMD для проектирования и верификации текстурных каналов, а также в компании Luxoft для отладки и оптимизации стека системного ПО для гетерогенных процессоров класса HSA, что подтверждается справками о внедрении.

Материалы диссертации использованы в НИР №713564 «Создание бесшовных технологий проектирования встраиваемых систем и систем на кристалле на основе ре-конфигурируемых архитектур» и НИР 610481 «Разработка методов и средств системотехнического проектирования информационных и управляющих вычислительных систем с распределенной архитектурой», а также в учебном процессе на кафедре ВТ (Университет ИТМО) в дисциплине "Теоретическая информатика" для магистров по направлению 230100.68.

Публикации. Основные результаты по теме диссертации изложены в 10 печатных изданиях, 3 из которых изданы в журналах, рекомендованных ВАК, 3 — в тезисах докладов, 1 статья опубликована на русском и английском языках в журнале, индексируемом в базе Scopus.

Объем и структура работы. Диссертация состоит из введения, пяти глав, заключения и трёх приложений. Полный объем диссертации 138 страниц текста с 77 рисунками и 33 таблицами. Список литературы содержит 99 наименований.

1. Анализ архитектуры графических процессоров, современных форматов и алгоритмов сжатия текстур

1.1 Особенности текстурного сжатия

Использование различных видов текстур является неотъемлемой частью современной компьютерной графики. Это позволяет существенно улучшить визуальную детализацию трехмерных объектов без усложнения геометрии. В простейшем случае текстуры представляют собой двухмерное изображение, накладываемое на трёхмерный объект. Отдельные точки растра, составляющие текстуру, принято называть текселями (texel — texture element). Кроме информации о цвете текстура может содержать карту высот, нормалей, отражений и прочую информацию (Рис. 1.1).

А)

Б)

В)

+ W

Рис. 1.1: Пример использования различных видов текстур. А — карта диффузного отражения, Б — карта нормалей, В — карта смещений.

При этом в современных интерактивных приложениях текстуры занимают более половины используемого объёма видеопамяти [4]. Применение большого количества текстур крупных размеров предъявляет высокие требования к видеопамяти. В связи с

этим широкое распространение получили различные технологии сжатия текстур. При этом текстура передается и хранится в памяти в сжатом виде, и распаковывается непосредственно графическим процессором, как правило, между кэшами уровней L1 и L2. Такой подход позволяет не только уменьшить занимаемый текстурами объем памяти, но и снизить требования к пропускной способности, которая в большинстве случаев является гораздо более дефицитным ресурсом. Кроме этого, использование сжатия положительно сказывается на энергопотреблении за счёт уменьшения объёма используемой памяти и снижения трафика на интерфейсе вРиопамять, что существенно для мобильных устройств (ноутбуков, планшетов, смартфонов).

В большинстве случаев, текстуры представляют собой обычные двухмерные изображения. Однако универсальные алгоритмы сжатия без потерь (RLE, LZW, Deflate) и широко распространённые графические форматы, такие как JPEG, PNG, TIFF, малопригодны для текстур. Основная причина этого — невозможность доступа к произвольному участку текстуры без декомпрессии всего файла. При отрисовке трёхмерного объекта используются только те фрагменты текстуры, которые попали в кадр, при этом смежность элементов объекта не обязательно означает смежность элементов текстуры (Рис. 1.2). Кроме этого, заранее неизвестно в какой последовательности будут запрошены различные части текстуры. Поэтому общая производительность системы визуализации очень сильно зависит от эффективности произвольного доступа к тексе-лям. Именно эта особенность обуславливает основные свойства различных форматов сжатия текстур.

А) Б)

Рис. 1.2: Пример отображения текстуры на трёхмерный объект. А — текстурированная ЗО-модель, Б — исходная текстура (Microsoft DirectX 9 SDK)

1.1.1 Основные требования к алгоритмам и форматам компрессии-декомпрессии текстур

Для текстурного сжатия характерно разбиение всего изображения на блоки фиксированного размера и независимое сжатие каждого блока. Некоторые форматы немного отходят от этой концепции (Семейство PVRTC). Применительно к компьютерной графике, для текстурной компрессии важны следующие свойства:

• Произвольный доступ. Необходимо, чтобы формат сжатой текстуры позволял осуществлять быстрый доступ к произвольному участку текстуры. В связи с этим, почти все известные компрессоры имеют фиксированный уровень сжатия. Это, в свою очередь, автоматически означает сжатие с потерями. Тем не менее, существуют подходы и с нефиксированным уровнем сжатия. Например, в работе [5] предлагается подход к сжатию текстур без потерь и с переменным уровнем сжатия, где для повышения производительности произвольного доступа предлагается модификация системы кэширования.

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

- Простота аппаратной реализации декодера. Алгоритм декомпрессии должен быть относительно простым. Поэтому дискретно-косинусные (DCT — discrete cosine transform) и вейвлет преобразования, как правило, не используются.

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

• Высокая степень сжатия. Это основной параметр, определяющий снижение требований к пропускной способности памяти для текстурных операций. Степень сжатия принято выражать в среднем количестве бит на пиксель или Ьрр. Типичные значения Ьрр для текстурных компрессоров от 2Ьрр до 8Ьрр.

• Изображение разбивается на блоки небольшого размера, обычно 4x4 текселя. Блоки меньшего размера сложнее поддаются сжатию. С другой стороны, блоки слишком большого размера могут отрицательно сказаться на проценте кэш-попаданий. Желательно также, чтобы размер блока был меньше ширины шины

памяти, чтобы снизить задержки и упростить аппаратную реализацию [6]. Современные графические процессоры в персональных компьютерах имеют ширину шины памяти от 64 до 512 бит. Ввиду жестких ограничений на ширину шины памяти в мобильных устройствах часто используются кодеки с очень высокой степенью сжатия (2Ьрр) или с меньшими размерами блоков.

• Приемлемое качество сжатого изображения. Очевидно, что вносимые компрессором искажения должны быть, по-возможности, минимальными (особенно для визуального восприятия).

1.1.2 Сжатие для ускорения загрузки

Далее в данной главе речь будет вестись именно о форматах, имеющих аппаратную поддержку декодирования и позволяющих обращаться к произвольному участку текстуры без полной распаковки. Однако можно отметить такое направление, как сжатие текстур для ускорения их загрузки в видеопамять. Оно используется для ускорения загрузки текстур с диска или по сети, что актуально для современных приложений, в которых объём текстур измеряется гигабайтами.

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

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

К примеру, технология Virtual Texturing используемая в графическом движке IdTech5 [7] при подгрузке отдельных частей текстур позволяет транскодировать их из формата, близкого к JPEG, в формат DXT. Однако итоговая текстура будет содержать артефакты сжатия, вносимые обоими форматами.

Среди прочих работ так же можно отметить работу [8], в которой предлагается схема, способная производить сжатие текстур с различными уровнями детализации (mipmaps) без потерь и с потерями, а также работу [9], описывающую алгоритм сжатия без потерь текстур в формате ETC.

1.1.3 Качество и скорость сжатия

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

Качество также может пострадать и при распаковке. Так, например, аппаратная реализация декодера текстур формата ОХТ1 на графических чипах ОеРогсе/ОеРогсе2 была такова, что все операции выполнялись в режиме 16 бит, без конвертации в 24 бита [10]. Это приводило к появлению дополнительных артефактов при распаковке (Рис. 1.3).

А) Б) В)

Рис. 1.3: Артефакты сжатия. А — без сжатия, Б — dxtl на видеокарте S3 Savage2000, В — dxtl на видеокарте NVidia GeForce 256. (Источник: iXBT [10])

Традиционный подход к сжатию текстур заключается в использовании предварительно сжатых текстур. В современных системах визуализации все чаще используются динамически генерируемые данные (карты окружений для имитации отражения, и т.д.), что делает актуальной задачу быстрого сжатия текстур в темпе генерации кадров ресурсами графического процессора. Стоит также отметить, что текстурное сжатие в реальном времени используется при передаче по сети видеопотоков высокого разрешения, например, в системе UltraGrid [11,12]. Однако традиционная архитектура ГП предполагает запись обработанных фрагментов в память. Поэтому сжатие возможно только после окончания формирования кадра и последующего чтения данных из памяти. Кроме этого, после записи сжатых данных в память необходима дополнительная

операция копирования, что более подробно освещено в Главе 3. Таким образом, существующие техники межкадрового (динамического) сжатия требуют дополнительных затрат времени, не связанных с форматом и алгоритмом сжатия.

1.2 Ранние работы, связанные с текстурным сжатием

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

• малая степень сжатия (8Ьрр)

• низкое качество из-за ограничения количества уникальных цветов (256 цветов при 8Ьрр)

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

Данный подход является частным случаем векторного квантования (VQ, Vector Quantisation), в котором вектор представлен одним пикселем. Более сложный вариант VQ-сжатия, в котором один вектор представляет сразу несколько соседних пикселей, использовался в игровой консоли Sega Dreamcast [2], что позволило добиться коэффициентов сжатия 1:5 и 1:8 при приемлемом качестве.

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

Первым подобным алгоритмом был Block Truncating Coding (ВТС), предназначенный для сжатия черно-белых изображений (в оттенках серого). Основная идея алгоритма — сохранить математическое ожидание и среднеквадратическое отклонение яркости. При этом в результирующем изображении внутри каждого блока используется только два уровня яркости а и Ь (Рис. 1.4). Формат сжатого блока предполагает хранение обоих этих уровней и битовой карты, где каждый бит соответствует одному пикселю. При компрессии на первом шаге изображение разбивается на блоки размера MxN (обычно 4x4). Для каждого блока вычисляются математическое ожидание х и среднеквадратичное отклонение а. Далее вычисляется битовая карта: 1 означает, что значение яркости данного пикселя больше х, а 0 — меньше. Уровни яркости а

174 165 193 208

132 116 143 179

150 152 120 153

163 143 76 122

А)

1 1 1 1

0 0 0 1

1 1 0 1

1 0 0 0

Б)

177 177 177 177

114 114 114 177

177 177 114 177

177 114 114 114

В)

а= 114 6=177

Рис. 1.4: Пример кодирования ВТС (А — исходный блок, Б — битовая карта, В —

восстановленный блок)

и Ь вычисляются по формулам (1.1) и (1.2), что позволяет сохранить математическое ожидание и среднеквадратичное отклонение.

а = х — а.

b = х + а а

тп

lm — q

(1.1) (1.2)

где m — количество пикселей в блоке, a q — количество единичных значений в битовой карте.

Большим преимуществом ВТС является простота реализации и крайне малые вычислительные затраты на декомпрессию. При использовании блоков 4x4 и глубины цвета 8Ьрр уровень сжатия равен 2Ьрр. ВТС использовался, в частности, в камере марсохода NASA (Mars Pathfinder Project) [13].

В случае цветных изображений можно использовать ВТС отдельно для каждого цветового канала, что даст уровень сжатия 6Ьрр. Однако подобная схема сильно снижает качество итогового изображения (Рис. 1.5). Позже для сжатия цветных изображений была предложена модификация ВТС в виде алгоритма ССС (Color Cell Compression), позволившая получить уровни сжатия 2Ьрр и ЗЬрр. В алгоритме ССС, так же как и в ВТС, все значения квантуются на два уровня, но используется только одна битовая карта для всех трех каналов.

На первом этапе кодирования для каждого пикселя рассчитывается яркость Y по формуле (1.3), после чего определяется средняя яркость блока Y. Битовая карта строится путём сравнения яркости пикселя со средней яркостью. Далее некоторым образом выбираются базовые цвета а и Ь, например, в соответствие с (1.1) и (1.2).

Y = 0.3 * R + 0.59 *G + 0.11 * В

(1.3)

В одной из схем ССС базовые цвета сохраняются в формате 1ШВ565 в самом сжатом блоке. Таким образом, размер сжатого блока составляет 48 бит (по 16 бит на

Рис. 1.5: Пример кодирования ВТС. А — оригинальные изображения, Б —

восстановленные изображения

базовые цвета и 16 бит на битовую карту), а уровень сжатия — ЗЬрр. В другой схеме в блоке сохраняются не сами базовые цвета а и Ъ, а их 8-ми битные индексы в общей для всего изображения палитре, что даёт уровень сжатия 2Ьрр.

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

Далее в данной главе будут рассмотрены форматы сжатия ВС1, ВС7 и ASTC. Более подробная информация других стандартных форматах сжатия текстур представлена в работе [ 14] и приложениях к настоящей диссертации.

1.3 Семейство S3TC

Разработанный и запатентованный компанией S3 Incorporated формат S3TC [15] является одним из наиболее распространённых форматов сжатия. Данный формат вошёл в API DirectX 6.0 под именем DXT1, а его модификации для текстур с альфа-каналом под - именами DXT2-DXT5, которые все вместе зачастую именуются DXTC (DirectX Texture Compression). В качестве расширений OpenGL и OpenGL ES формат DXT1 описан в спецификации EXT texture compression dxtl [16], являющейся частью спецификации EXT_texture_compression_s3tc [17], в которой дополнительно описаны форматы DXT3 и DXT5.

Список литературы диссертационного исследования кандидат наук Перминов, Илья Валентинович, 2014 год

Литература

1. van Waveren J. Real-Time DXT Compression: Tech. Rep.: : Id Software, 2006.

2. Fenney S. Texture compression using low-frequency signal modulation // Graphics Hardware. 2003. P. 84-91. URL: http://web.onetel.net.uk/~simonnihal/assorted3d/fenney03texcomp.pdf.

3. Programming Guide for Direct3D 10. Block Compression (Direct3D 10). URL: http://msdn.microsoft.com/en-us/library/windows/desktop/bb694531.

4. McDonald J. Eliminating Texture Waste: Borderless Ptex // GDC2013 / NVidia Corporation. 2013.

5. Inada T., McCool M. D. Compressed lossless texture representation and caching // Proceedings of the 21st ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware. GH '06. New York, NY, USA: ACM, 2006. P. 111-120. URL: http://doi.acm.org/10.1145/1283900.1283918.

6. Ström J., Akenine-Möller T. PACKMAN: Texture Compression for Mobile Phones // ACM SIGGRAPH 2004 Sketches. SIGGRAPH '04. New York, NY, USA: ACM, 2004. P. 66-, URL: http://doi.acm.org/10.1145/1186223.1186306.

7. van Waveren J. id Tech 5 Challenges: From Texture Virtualization to Massive Paral-lelization // Siggraph. 2009.

8. Variable Bit Rate GPU Texture Decompression / M. Olano, D. Baker, W. Griffin et al. // Computer Graphics Forum / Wiley Online Library. Vol. 30. 2011. P. 1299-1308.

9. Ström J., Wennersten P. Lossless Compression of Already Compressed Textures. // High Performance Graphics / Ed. by C. Dachsbacher, W. Mark, J. Pantaleone Eurographics Association, 2011. P. 177-182. URL: http://dblp.uni-trier.de/db/conf/egh/hpg2011 .html#StromWl 1.

10. Воробьев A. 3DGiTora июль 2001 года — Влияние технологии S3TC (FXT1) на качество и скорость. 2001. URL: http://www.ixbt.com/video/0701i-video-s3tcl.html.

11. WesleyandSmith I. N., Liska M., Holub P. Implementation of DXT Compression for Ul-traGrid. 2008. URL: http://archiv.cesnet.cz/doc/techzpravy/2008/dxt-compression-for-ultragrid/.

12. GPU-accelerated DXT and JPEG compression schemes for low-latency network transmissions of HD, 2K, and 4K video / P. Holub, M. Srom, M. Pulec et al. // Future Generation Computer Systems. 2013. Vol. 29, no. Patent 8. P. 1991 - 2006. URL: http://www.sciencedirect.com/science/article/pii/S0167739X13001209.

13. Rover Camera Instrument Description. URL: http://pdsimg.jpl.nasa.gov/data/mpfr-m-rvrcam-2-edr-vl .0/mprv_0001/document/rcinst.htm.

14. Perminov I., Paltashev T. Texture compression techniques // Scientific Visualization, National Research Nuclear University "MEPhI". 2014. Vol. 6. P. 96 - 136.

15. Konstantine I. Iourcha Zhou Hong K. S. N. System and method for fixed-rate block-based image compression with inferred pixel values. Patent US5956431.

16. EXT_texture_compression_dxtl extension specification. 2008. URL: http://www.opengl.org/registry/specs/EXT/texture_compression_dxtl.txt.

17. EXT_texture_compression_s3tc extension specification. 2013. URL: http://www.opengl.org/registry/specs/EXT/texture_compression_s3tc.txt.

18. EXT texture compression rgtc extension specification. 2008. URL: http://www.opengl.org/registry/specs/EXT/texture_compression_rgtc.txt.

19. ARB texture compression rgtc extension specification. 2009. URL: http://www.opengl.org/registry/specs/ARB/texture_compression_rgtc.txt.

20. EXT texture compression latc extension specification. 2009. URL: http://www.opengl.org/registry/specs/EXT/texture_compression_latc.txt.

21. ARBtexturecompressionbptc extension specification. 2011. URL: http://www.opengl.org/registry/specs/ARB/texture_compression_bptc.txt.

22. Castaño I. GPU DXT Decompression. 2009. URL: http://www.ludicon.com/castano/blog/2009/03/gpu-dxt-decompression/.

23. FastDXT. URL: http://www.evl.uic.edu/cavern/fastdxt/.

24. van Waveren J., Castaño I. Real-Time Normal Map DXT Compression. 2008. URL: http://www.nvidia.de/object/real-time-normal-map-dxt-compression.html.

25. Brown S. DXT Compression Techniques. 2006. URL: http://www.sjbrown.co.Uk/2006/01 /19/dxt-compression-techniques/.

26.

27.

28.

29.

30.

31.

32.

33,

34

35

36

37

38

39

NV_texture_compression_vtc extension specification. 2004. URL:

http://www.opengl.org/registry/specs/NV/texture_compression_vtc.txt.

Levkovich-Maslyuk L., Kalyuzhny R, Zhirkov A. Texture Compression with Adaptive Block Partitions // ACM Multimedia. 2000.

Programming Guide for Direct3D 11. Texture Block Compression in Direct3D 11. URL: http://msdn.microsoft.com/en-us/library/windows/desktop/hh308955.

The OpenGL Graphics System: A Specification Version 4.2 (Core Profile). 2012.

Adaptive Scalable Texture Compression. / J. Nystad, A. Lassen, A. Pomianows-ki et al. // High Performance Graphics / Ed. by C. Dachsbacher, J. Munkberg, J. Pantaleoni. Eurographics Association, 2012. P. 105-114. URL: http://dblp.uni-trier.de/db/conf/egh/hpg2012.html#NystadLPEO 12.

Ellis S., Nystad J. ASTC Specification. ARM. 2012.

KHRtexturecompressionastchdr extension specification. 2013. URL:

http://www.opengl.org/registry/specs/KHR/texture_compression_astc_hdr.txt.

ARM Launches Second Generation of MALI-T600 Graphics Processors Driving Improved User Experience for Tablets, Smartphones and Smart-TVs. 2012. URL: http://www.arm.com/about/newsroom/arm-launches-second-generation-of-mali-t600-graphics-processors-driving-improved-user-experience.php.

Nystad J., Lassen A. Method of and apparatus for encoding and decoding data. Patent GB2491689.

Nystad J., Lassen A. Method of and apparatus for encoding and decoding data. Patent US20120281005.

Nystad J., Lassen A. Method of and apparatus for encoding and decoding data. Patent US20120281006.

Nystad J., Lassen A. Method of and apparatus for encoding and decoding data. Patent US20120281007.

Nystad J., Lassen A., Olson T. Flexible Texture Compression Using Bounded Integer Sequence Encoding // SIGGRAPH Asia 2011 Sketches. SA '11. New York, NY, USA: ACM, 2011. P. 32:1-32:2. URL: http://doi.acm.org/10.1145/2077378.2077418.

Ellis S. ARM ASTC Texture Compression // CGDC (China Game Developers Conference). 2013. URL: http://community.arm.com/docs/DOC-2125.

40. Smith S. ASTC does it. 2013. URL: http://community.arm.com/groups/arm-mali-graphics/blog/2013/10/22/astc-does-it.

41. Gustavson S. Simplex noise demystified. 2005. URL: http://www.itn.liu.se/~stegu/simplexnoise/simplexnoise.pdf.

42. Ellis S. More ASTC in ARM Mali GPUs - High Dynamic Range and 3D. 2013. URL: http://malideveloper.arm.com/engage-with-mali/more-astc-in-arm-mali-gpus-high-dynamic-range-and-3d/.

43. Сэломон Д. Сжатие данных, изображений и звука. Техносфера, 2004. С. 368.

44. Перминов И. В. Динамическая компрессия визуальных данных в графических процессорах // Параллельные вычисления и задачи управления РАСО'2012 Труды шестой международной конференции. 2012. С. 31-41.

45. AMD Developer Central. The compessonator. URL: http://developer.amd.com/tools-and-sdks/archive/legacy-cpu-gpu-tools/the-compressonator/.

46. NVIDIA Texture Tools. URL: https://code.google.eom/p/nvidia-texture-tools/.

47. Crunch Compression Library. URL: https://c0de.g00gle.c0m/p/crunch/.

48. libsquish. Open source DXT compression library. URL: https://code.google.eom/p/libsquish/.

49. Wilcoxen S. LSDxt DXT Compressor. 2012. URL: http://lspiroengine.com/?p=516.

50. Uliciansky P. Extreme DXT Compression. URL: http://www.cauldron.sk/files/extreme_dxt_compression.pdf.

51. ASTC Evaluation Codec. URL: http://malideveloper.arm.com/develop-for-mali/tools/astc-evaluation-codec/.

52. The OpenCL Specification Version: 1.2. 2012. URL: http://www.khronos.org/registry/cl/specs/opencl-L2.pdf.

53. NVIDIA Corporation. NVIDIA CUDA С Programming Guide Version 4.2. 2012.

54. Адигеев М.Г. Анализ сложности параллельных алгоритмов. Методические указания для студентов факультета математики, механики и компьютерных наук. ЮФУ, Ростов-на-Дону. 2013.

55. Parhami В. Introduction to Parallel Processing: Algorithms and Architectures. Norwell, MA, USA: Kluwer Academic Publishers, 1999.

56. Advanced Micro Devices, Inc. AMD Southern Islands Series Instruction Set Architecture. 2013. URL: http://developer.amd.com/wordpress/media/2012/12/AMD_Southern_Islands_Instructio n_Set_Architecture.pdf.

57. Taylor M. B. Is Dark Silicon Useful?: Harnessing the Four Horsemen of the Coming Dark Silicon Apocalypse // Proceedings of the 49th Annual Design Automation Conference. DAC '12. ACM, 2012. P. 1131-1136. URL: http://doi.acm.org/10.1145/2228360.2228567.

58. Перминов И. В., Герасимов А. А. Взаимодействие GPU и CPU на кристалле с использованием разделяемой памяти // Сборник трудов молодых ученых и сотрудников кафедры ВТ. - Вып. 3. - Компьютерные системы и сети. 2012.

59. HSA Foundation. Heterogeneous System Architecture: A Technical Review. 2012.

60. HSA Foundation. URL: http://www.hsafoundation.com/.

61. Перминов И. В., Палташев Т. Т. Гетерогенная архитектура для CPU, GPU и DSP // Открытые Системы. СУ БД. 2013. Т. 08. С. 12-15.

62. Перминов И. В. Особенности использования регистровой памяти GPU в OpenCL на примере текстурного компрессора // 23-я Международная Конференция по Компьютерной Графике и Зрению ГрафиКон'2013 Труды Конференции. 2013. С. 267270.

63. NVIDIA Corporation. Parallel Thread Execution ISA version 3.0. 2012.

64. PowerVR Ray Tracing. 2014. URL: http://www.imgtec.com/powervr/raytracing.asp.

65. Programming Guide for Direct3D 11. Graphics Pipeline. URL: http://msdn.microsoft.com/en-us/library/windows/desktop/ff476882.

66. Imagination Technologies Ltd. PowerVR Series 5 Architecture Guide for Developers. 2013.

67. Перминов И. В. Повышение эффективности обработки динамически сжимаемых текстур // Научно-Технический Вестник Информационных технологий, механики и оптики. 2013. Т. 6 (86). С. 164-165.

68. FOSS user-space driver for the Vivante GCxxx series of embedded GPUs. GCxxx hardware . URL: https ://github. com/laanwj/etna_viv/blob/master/doc/hardware .md.

69. Intel Corporation. Intel Open Source Graphics Programmer's Reference Manual (PRM) for the 2013 Intel® Core™ Processor Family, including Intel HD Graphics, Intel

Iris™ Graphics and Intel Iris Pro Graphics Volume 5: Memory Views (Haswell). 2013. URL: https://01.org/linuxgraphics/sites/default/files/documentation/intel-gfx-prm-osrc-hsw-memory-views .pdf.

70. ARM Frame Buffer Compression. URL: http://www.arm.com/products/multimedia/mali-technologies/arm-frame-buffer-compression.php.

71. SRGB VS. ADOBE RGB 1998. URL: http://www.cambridgeincolour.com/tutorials/sRGB-AdobeRGB1998.htm.

72. Перминов И. В., Палташев Т. Т. Использование контейнера ВС7 для хранения текстур с глубиной цвета 10 бит // Научно-технический вестник информационных технологий, механики и оптики. 2014. Т. 1 (89). С. 107-112.

73. Mali GPU Texture Compression Tool. URL: http://malideveloper.arm.com/develop-for-mali/tools/asset-creation/mali-gpu-texture-compression-tool/.

74. Blinn J. F. Jim Blinn's Corner: Compositing, Part 1: Theory // IEEE-CGA. 1994. Vol. 14. P. 83-87.

75. 3Dc™ White Paper. URL: http://www.hardwaresecrets.com/datasheets/3Dc_White_Pap er.pdf.

76. Современная терминология 3D графики. URL: http://www.ixbt.eom/video2/terms2k5.shtml#hdr.

77. OES_compressed_ETCl_RGB8_texture extension specification. 2008. URL: http://www.khronos.org/registry/gles/extensions/OES/OES_compressed_ETCl_RGB8_ texture.txt.

78. WEBGL_compressed_texture_etcl Extension Draft Specification. 2013. URL: http://www.khronos.org/registry/webgl/extensions/WEBGL_compressed_texture_etcl/.

79. The OpenGL Graphics System: A Specification Version 4.3 (Core Profile). 2013.

80. Strom J., Akenine-Moller T. i PA С KM AN: High-quality, Low-complexity Texture Compression for Mobile Phones // Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Conference on Graphics Hardware. HWWS '05. New York, NY, USA: ACM, 2005. P. 63-70. URL: http://doi.acm.org/10.1145/1071866.1071877.

81. Strom J., Pettersson M. ETC2: Texture Compression Using Invalid Combinations // Proceedings of the 22Nd ACM SIGGRAPH/EUROGRAPHICS Symposium on Graphics Hardware. GH '07. Aire-la-Ville, Switzerland, Switzerland: Eurographics Association, 2007. P. 49-54. URL: http://dl.acm.org/citation.cfm7id-1280094.1280102.

82. Ström J., Akenine-Möller T. Multi-mode alpha image processing. Patent US7693337.

83. Ström J., Akenine-Möller T. Multi-mode image processing. Patent US7734105.

84. Ström J., Akenine-Möller T. Multi-mode image processing. Patent US7751630.

85. Pettersson M., Ström J. Texture compression based on two hues with modified brightness. Patent US8144981.

86. The OpenGL Graphics System: A Specification Version 4.4 (Core Profile). 2013.

87. Fenney S. Method and apparatus for compressing data and decompressing compressed data. Patent US7236649.

88. Fenney S. Method and apparatus for compressing data and decompressing compressed data. Patent US7242811.

89. Fenney S. Method and apparatus for compressing data and decompressing compressed data. Patent US8204324.

90. Fenney S. Method and apparatus for compressing data and decompressing compressed data. Patent US8526726.

91. IMG_texture_compression_pvrtc extension specification. 2012. URL: http:// www.khronos.org/registry/gles/extensions/IMG/IMG_texture_compression_pvrtc.txt.

92. IMG_texture_compression_pvrtc2 extension specification. 2012. URL: http:// www.khronos.org/registry/gles/extensions/IMG/IMG_texture_compression_pvrtc2.txt.

93. EXT_pvrtc_sRGB extension specification. 2013. URL: http://www.khronos.org/registry/gles/extensions/EXT/EXT_pvrtc_sRGB.txt.

94. WEBGL_compressed_texture_pvrtc Extension Draft Specification. 2013. URL: http://www.khronos.org/registry/webgl/extensions/WEBGL_compressed_texture_pvrtc/.

95. Voica A. Taking texture compression to a new dimension with PVRTC2. 2013. January. URL: http://withimagination.imgtec.com/index.php/powervr/pvrtc2-taking-texture-compression-to-a-new-dimension.

96. Beets K. Understanding PowerVR Series5XT: PVRTC, PVRTC2 and texture compression. 2013. June. URL: http://withimagination.imgtec.com/index.php/powervr/understanding-powervr-series5xt-pvrtc-pvrtc2-and-texture-compression-part-6.

97. Voica A. PVRTC: the most efficient texture compression standard for the mobile graphics world. 2013. January. URL: http://withimagination.imgtec.com/index.php/powervr/pvrtc-the-most-efficient-texture-compression-standard-for-the-mobile-graphics-world.

98. Geldreich R. PVRTC Compression - First Experiments. URL: https://sites.google.com/site/richgel99/early-pvrtc-compression-experiments.

99. Geldreich R. PVRTC Compression - First Coded 4bpp .PVR Texture. URL: https://sites.google.com/site/richgel99/pvrtc-compression2.