Введение

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

Однако при реализации этой вроде бы типовой задачи возникли проблемы, связанные с наличием некоторых ограничений:

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

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

В-третьих, МКС движется с 1-ой космической скоростью, совершая оборот вокруг Земли примерно за 92 минуты, т.е. смена неповторяющихся изображений земной поверхности на экране в реальном времени должна идти достаточно быстро.

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

При этом, например, если максимальный размер текстуры, которую можно загрузить в видеопамять составляет 2048х2048, то, даже не самая большая из карт, например, карта «ночной» Земли, доступная на сайте НАСА [1], при довольно грубом разрешении около 0.75 км/пиксель уже имеет размер 54000х27000 пикселей. Таким образом, чтобы загружать такую карту как текстуру, ее нужно было бы разбить как минимум на 342 фрагмента.

Требование неупакованных данных для отображения

Одна из объективных сложностей, как раз и требующая больших объемов памяти при отображении больших объемов данных, связана с необходимостью перед отображением «распаковать» имеющийся файл. Та же «ночная» карта Земли занимает на диске около 393 Мбайт в формате JPEG, а если ее преобразовать в двумерный массив цветов пикселей RGB (т.е. по сути, в формат BMP), она займет в памяти уже 54000х27000х3=4,374 Гбайт. Это даже больше чем 2³² и поэтому, например, просто адресовать такой массив в 32-х разрядной среде уже не получится, не говоря о том, что реально в 32-х разрядной среде Windows (где и требуется данное отображение) пользователям доступно только до 3 Гбайт памяти. Кстати, вероятно, поэтому даже такой развитой графический редактор как «AcdSee» отображает эту «ночную» карту Земли, но не может редактировать ее (выдает ошибку).

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

Подходящий формат картографических данных

Исторически одним из первых «сжатых» графических форматов был формат PCX [2], заменяющий несколько подряд идущих одноцветных пикселей на один пиксель и счетчик его повторений. В настоящее время этот формат практически не применяется, дошло до того, что его перестал отображать даже такой стандартный редактор Windows как Paint. В самом деле, фотографические изображения формат PCX сжимает очень плохо, для них разработаны специальные алгоритмы JPEG. А обычные рисунки стало проще хранить в «несжатом» формате BMP, поскольку рисунок в несколько мегабайт – не проблема для современных компьютерных средств и сжимать такие небольшие данные уже не имеет особого смысла.

Но при этом не принимается во внимание, что еще остается целый класс специальных изображений-рисунков – карты, где при наличии больших размеров и больших одноцветных площадей старый формат PCX по-прежнему очень удобен и дает большую степень сжатия. Например, уже приводимая выше «ночная» карта Земли в формате PCX занимает лишь около 292 Мбайт. Такое сильное сжатие даже по сравнению с форматом JPEG получилось, конечно, не только за счет алгоритма сжатия, но и за счет перехода от полного RGB-цвета (16.8 миллионов оттенков) к 256 цветам, позволяющим заменить три байта RGB каждого пикселя на один байт номера цвета в «палитре» формата PCX. Разумеется, «ночная» карта Земли - это не рисунок, а интегрированный из тысяч спутниковых фотографий ортофотоплан, т.е. тоже фотография. Но по содержащейся на ней информации, включающий лишь океан, более светлую землю и светящиеся города, она ближе к обычным картам-рисункам, не требующим для сохранения всей информации миллионов оттенков. И при этом наличие лишь 256 цветов все равно позволяет отображать даже некоторые особенности рельефа, например, ледники.

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

Использование двумерных массивов при отображении

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

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

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

Использование массива реперных точек

Для ускорения обработки была использована сетка т.н. реперных точек. Один раз загруженное исходное «сжатое» изображение в PCX-формате просматривается и в памяти составляется двумерный массив характеристик некоторого подмножества точек, например, каждой 64-ой точки в строке. Точка в этом массиве характеризуется 4-х байтным смещением от начала «сжатого» изображения и байтом номера, по которому данная точка попадает «внутрь» группы повторяющихся пикселей. Например, если для реперной точки в массиве указан код 01 25 DE 00 0A, а по этому смещению 00DE2501 в PCX-изображении находится код CF 33, это означает, что данная реперная точка является по счету десятой (0A) в сжатой группе из 15 (CF) пикселей одинакового цвета №33.

Для того чтобы найти цвет пикселя с координатами (X, Y) в «сжатом» PCX-изображении, нужно сначала делением X на 64 найти ближайшую реперную точку и извлечь 5 байт информации для нее из двумерного массива реперных точек. Затем по найденному смещению «встать» на начало очередного элемента PCX-формата и начать «распаковывать» от ближайшей реперной точки до нужной. «Распаковка» заключается в подсчете числа пикселей. Например, если нужен цвет точки, отстоящей от рассмотренной ближайшей реперной на 3 пикселя, то он также будет равен цвету реперной точки (№33), поскольку и реперная и заданная точка попадают в одну группу 15 сжатых пикселей. Для последующих точек, возможно, уже придется перемещаться к следующим элементам PCX-формата, подсчитывая их длины, пока не «набежит» нужный номер точки, т.е. нужная координата X. Даже в худшем случае так придется «распаковать» число элементов не превышающее расстояние между двумя соседними реперными точками.

Термин «распаковка» здесь весьма условен, по сути, нужно лишь отличать одиночные пиксели, заданные просто номером своего цвета, от повторяющихся одинаковых, перед которыми стоит счетчик их повторений. Напомню, что в PCX-формате счетчик отличается от номера цвета двумя единичными старшими битами. Поэтому, например, если номер цвета одиночного пикселя больше 192, то для однозначности приходится перед ним еще писать единичный счетчик. Очевидно, что для большего сжатия выгодно самые часто встречающиеся цвета в PCX-изображении задавать номерами с небольшими значениями.

Массив реперных точек, разумеется, тоже требует памяти. Так, для уже приводимой в пример «ночной» карты потребуется дополнительно 54000х27000/64х5=113906250 байт, при условии, что в качестве реперной взята каждая 64-ая точка в строке. Таким образом, общий объем, занимаемый «ночной» картой Земли в памяти вместе с реперными точками, составит около 406 Мбайт, что почти в 10 раз меньше, чем «несжатый» массив цветов RGB пикселей того же изображения.

Правда, для упрощенного 256-цветного изображения можно было бы хранить просто двумерный массив байтов номеров цветов, а не самих RGB, что само по себе дало бы трехкратное уменьшение объема по сравнению с обычным форматом BMP, но и это все равно было бы существенно больше по объему памяти (54000х27000=1458000000), чем «сжатое» PCX-изображение с реперными точками.

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

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

Пример изображения «ночной» Земли в модели иллюминатора МКС приведен ниже.

На приведенном рисунке виден ярко освещенный промышленный район севера Италии, Средиземное море и север Африки на горизонте. Для наглядности данной иллюстрации выбран грубый масштаб (около 36 км на см. экрана в центре модели иллюминатора). Отображаемая в реальном времени карта в формате PCX имеет размеры 54000х27000 пикселей и полностью загружена в память.

Заключение

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

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

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

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

Литература

1.      http://earthobservatory.nasa.gov/NaturalHazards/view.php?id=79765

2.      ZSoft Corporation PCX Technical Reference Manual Revision4 Marietta, GA 1988