СПОСОБ ПОРОЖДЕНИЯ СПРАЙТА
METHOD FOR GENERATION OF SPRITE

Изобретение относится к способам создания спрайтов, представляющих собой изображения неправильной формы и накладываемых на фоновые изображения, предпочтительно в реальном времени. Изобретение может быть использовано при формировании оверлейных изображений с заданным цветовым ключом в реальном времени.
В [http://www.xserver.ru/computer/langprogr/razn/36/10.shtml] плоские растровые изображения неправильной формы называются спрайтами. В документации к DirectX 2 SDK они называются декадами. Спрайт можно представить себе в виде фигурки, вырезанной из картона и установленной в определенной точке макета.
В [http://www.delphisources.ru/pages/faq/base/sprites_work.html] со ссылкой на книгу Андрэ Ла Мота спрайтами называются «маленькие объектики, которые находятся на игровом поле и могут двигаться. Этот термин прижился с легкой руки программистов фирмы Atari и Apple в середине 70-х годов. Спрайты - это персонажи в играх для ПК, которые могут без труда перемещаться по экрану, изменять цвет и размер». Другими словами, спрайт - это персонаж игры. Можно сказать, что спрайт - это массив из цветов; для простоты представим его как BMP файл или TBitmap, тем более, что этот формат поддерживается Windows и не содержит компрессии. Что нам: нужно от спрайта - заставить его появляться на экране и образовывать анимацию. Анимация - это не только смена координаты спрайта, но и изменение самого изображения. Следовательно, спрайт может иметь не одно изображение, а несколько. Смена их и приводит к анимации.
В [http://durus.ru/content/view/292/59/] спрайтом называется изображение в прямоугольной области, заполненной цветовым ключом, где цветовой ключ - это один или несколько цветов, предназначенных для изображения "прозрачного" цвета. Пиксели, окрашенные этим цветом, не копируются при блиттинге. Это позволяет создавать иллюзию непрямоугольного изображения, хотя при блиттинге копируются только прямоугольные области.
В [http:/www.mobilab.ru/artictes/53/] спрайт - это частично прозрачное изображение или набор изображений, который может накладываться и перемещаться по заднему плану или по другому спрайту без необходимости перерисовывать все основное окно. Другими словами спрайт - это перемещаемый игровой объект.
В [http://silencer.times.lv/tools_articles_1.htm] спрайты - это по сути то же самое, что и битмапы, но с одной отличительной особенностью - они имеют области с прозрачным цветом, который в процессе отрисовки просто игнорируется и не выводится. Термином «спрайт» еще иногда пользуются, чтобы указать на анимированный битмап. Современные спрайты состоят обычно из нескольких кадров анимации, это сделано для того, например, чтобы достичь эффекта летящего корабля, идущего человека и т.д.
В [http://computers.plib.ru/programming/SVGA/Glava%203/Index13.htm] спрайтами называются рисунки, для которых маска формируется динамически, в зависимости от значений кодов точек рисунка, но в любом случае маскировка преследует одну цель. Какой бы формы не был сам рисунок, например треугольник, стрелка, песочные часы и т.д., его образ всегда дополняется до прямоугольника, для того чтобы все строки имели одинаковый размер. Это существенно упрощает хранение и воспроизведение рисунков и одновременно вынуждает применять маскировку, исключающую вывод на экран той части прямоугольной области, которая не относится к рисунку. За счет наложения маски на экране показывается, например, изображение стрелки курсора, а не черный прямоугольник, на фоне которого она нарисована.
В соответствии с [http://www.255.ru/index.php?newsid=636] спрайт - небольшое изображение, свободно перемещающееся по монитору. В первоначальном смысле слова этот термин применялся только для аппаратно выводимых изображений. Собственно, лишь один настоящий спрайт можно встретить на IBM PC - аппаратный курсор мыши. При архитектуре ×86 под спрайтом принято понимать программно выводимое изображение, которое может иметь сложную форму и передвигаться поверх фона, не затирая его.
В патенте США 6337701 спрайтами называются графические объекты, которые перемещаются по экрану дисплея перед любыми другими объектами.
В случае, когда используется 4-байтовое представление цветов пикселей, один из байтов отводится под так называемый альфа-канал, указывающий степень прозрачности пикселя. В этом случае никаких проблем с созданием спрайтов не возникает. Однако широко используются и форматы представления цвета, не содержащие альфа-канала. В этом случае для кодирования областей прозрачности используют специально выделяемые для этой цели цвета, совокупность которых определяет цветовой ключ.
В [http://www.xserver.ru/computer/langprogr/razn/36/10.shtml] предложен способ создания спрайта, при котором удаляют все посторонние детали, чтобы оставить чистое изображение фигуры, и заполняют окружающий фон черным (прозрачным) цветом, при этом если исходное изображение содержит черные участки, заменяют черный цвет в изображении другим оттенком (например, вместо RGB: 0, 0, 0 можно использовать RGB: 0, 0, 1). Далее используют Microsoft Imager, чтобы сократить количество цветов с 256 до 8. Недостатком этого способа является то, что он предназначен только для создания спрайтов в палитровом режиме отображения, а также то, что он не предназначен для использования в реальном времени.
В [http://durus.ru/content/view/292/59/] предложен способ создания спрайта, при котором создают изображение, ограниченное прямоугольной областью, причем все пиксели этой прямоугольной области, которые не относятся к изображению, закрашивают особым цветом, который не использовался в самом изображении, и этот особый цвет назначают в качестве цветового ключа. При блиттинге он не будет копироваться, и вместо пикселей, окрашенных этим цветом, останутся пиксели фона - возникнет иллюзия прозрачности. Недостатком этого способа является то, что определение цвета, который не использовался в самом изображении, является весьма трудоемкой операцией, и поэтому весьма проблематичным является использование этого способа при создании спрайтов в реальном времени, особенно на маломощных компьютерах.
В патенте США 6337701 (прототип) предложен способ порождения спрайта с заданным первым множеством возможных цветов пикселей по первой структуре данных, задающей цветное изображение с заданным вторым множеством возможных цветов пикселей, и по второй структуре данных, определяющей форму указанного спрайта. Для получения значения каждого пикселя спрайта определяют по второй структуре данных, входит ли указанный пиксель в непрозрачную часть указанного спрайта, и если да, то устанавливают значение цвета текущего пикселя спрайта равным значению из указанного первого множества цветов, соответствующему цвету пикселя из первой структуры данных, а если нет, то устанавливают значение цвета текущего пикселя спрайта равным значению, определяющему прозрачный цвет пикселя. Определение того, входит ли пиксель в непрозрачную часть указанного спрайта, производят путем определения, имеет ли соответствующий элемент второй структуры данных заранее определенное значение. При этом в качестве спрайта рассматривается цветной курсор, а формирование и вывод спрайта производят только в том случае, если число разных цветов в структуре цветовых данных изображения не превосходит числа доступных цветов в аппаратном спрайте. Недостатком этого способа является его низкая надежность, обусловленная тем, что вывод спрайта происходит, только когда число разных цветов в структуре цветовых данных изображения не превосходит числа доступных цветов в аппаратном спрайте. Это является следствием того, что в способе, являющемся прототипом, не производят никаких попыток скорректировать цвета в исходном изображении, чтобы удовлетворить аппаратным ограничениям на количество доступных цветов.
С учетом изложенного, актуальной является разработка способа порождения спрайта, имеющего заданное первое множество возможных значений непрозрачных цветов пикселей и по меньшей мере одно заданное значение цвета пикселей, определяющее прозрачный цвет пикселя, при котором спрайт порождают по исходным данным, включающим в себя первую структуру данных, задающую цветное изображение с заданным вторым множеством возможных цветов пикселей, и вторую структуру данных, определяющую непрозрачную часть указанного спрайта. При этом способ должен обеспечивать порождение спрайта даже в том случае, когда количество разных цветов в структуре цветовых данных изображения превосходит количество доступных цветов, обусловленное аппаратными ограничениями, чтобы не приводить к ситуации, когда невозможно создать спрайт.
Это достигается за счет того, что для получения значения каждого пикселя спрайта определяют по второй структуре данных, входит ли указанный пиксель в непрозрачную часть указанного спрайта, и если да, то устанавливают значение цвета текущего пикселя спрайта равным значению из указанного первого множества цветов, соответствующему цвету пикселя из первой структуры данных, а если нет, то устанавливают значение цвета текущего пикселя спрайта равным значению, определяющему прозрачный цвет пикселя. При этом в отличие от прототипа соответствие цветов первой структуры данных и возможных непрозрачных цветов спрайта является частичным отображением указанного второго множества в указанное первое множество. Дополнение области определения указанного частичного отображения до указанного второго множества является множеством, мощность которого существенно меньше мощности указанного второго множества. Для определения значения, входящего в указанное первое множество цветов и соответствующего цвету пикселя из первой структуры данных, выполняют следующие действия:
если пиксель первой структуры данных имеет цвет, не принадлежащий указанной области определения, то значение этого пикселя устанавливают равным цвету, являющемуся одним из ближайших к исходному цвету пикселя и входящим в указанную область определения;
применяют к цвету пикселя первой структуры данных указанное частичное отображение.
За счет коррекции значений пикселей первой структуры данных и использования частичного отображения второго множества в указанное первое множество, т.е. множества всех цветов изображения в множество допустимых непрозрачных цветов спрайта, достигается основной технический результат, состоящий в повышении надежности способа порождения спрайта, поскольку в отличие от прототипа порождение спрайта оказывается возможно в любом случае. При этом возможно некоторое снижение качества спрайта, связанное с искажением значений некоторых цветов исходного изображения. Однако в большинстве случаев область определения частичного отображения выбирают таким образом, что максимальное расстояние от точек дополнения до области определения является очень небольшим, и тем самым указанное искажение оказывается практически незаметным.
Изобретение поясняется чертежами, где
Фиг.1. Формирование спрайта по двум структурам исходных данных.
0
Фиг.2. Структура частичного отображения φ.
Осуществление изобретения
1. Общее описание
Основное требование к порождаемому спрайту состоит в том, что цвета пикселей спрайта должны принадлежать заданному первому множеству возможных значений непрозрачных цветов пикселей, из которого исключены значения, определяющие прозрачный цвет пикселей. При этом как указанное первое множество возможных значений непрозрачных цветов пикселей, так и значения, определяющие прозрачный цвет пикселей, являются подмножеством пространства возможных аппаратно реализуемых цветов. Графическая система компьютера при наложении (оверлее) спрайта на фоновое изображение будет заменять значения пикселей фонового изображения соответствующими значениями пикселей спрайта, если они соответствуют непрозрачным цветам пикселей, и оставлять значения пикселей фонового изображения неизменными, если соответствующие пиксели спрайта имеют значения, определяющие прозрачный цвет пикселя. При этом очень важно, чтобы никакой пиксель спрайта внутри области, соответствующей непрозрачной части, не имел значения, соответствующего прозрачному цвету. В противном случае в таких пикселях вместо цвета изображения спрайта наблюдатель будет видеть цвет фона, на который наложен спрайт, а сам спрайт будет казаться имеющим «дырку».
При выводе спрайта на экран компьютера в виде оверлея множество прозрачных цветов задается цветовым ключом. Для оверлейной поверхности устанавливают цветовой ключ источника, задающий диапазон прозрачных цветов. В соответствии с [http://www.bringyou.to/games/ddraw.PDF, p.36] цветовой ключ используется при вызове метода IDirectDrawSurface::UpdateOverlay для управления тем, какая часть оверлейной поверхности будет видна над первичной поверхностью, а какая часть оверлейной поверхности будет прозрачной. Цветовые ключи оверлея могут быть связаны как с источником, так и с приемником, что устанавливается методом IDirectDrawSurface::SetColorKey. При выводе спрайтов в виде оверлея используют цветовой ключ источника, для чего выставляют флаг DDCKEY_SRCOVERLAY в первом параметре dwFlags этого метода. Метод IDirectDrawSurface::UpdateOverlay использует цветовой ключ источника, чтобы определить, какие пиксели спрайта на оверлейной поверхности следует рассматривать как прозрачные, дающие возможность видеть через них первичную поверхность. Формирование цветового ключа может производиться разными способами, которые рассматриваются в п.2.
Исходные данные для порождения спрайта включают в себя две структуры данных, где первая структура данных задает цветное изображение с заданным вторым множеством возможных цветов пикселей, а вторая структура данных определяет непрозрачную часть указанного спрайта (см. фиг.1).
0
0
0
0
0
0
-1
-1
-1
В качестве первой структуры данных, которая задает цветное изображение с заданным вторым множеством возможных цветов пикселей, может использоваться любое изображение в одном из стандартных форматов, таких как BMP, TIFF и т.п. При этом пространство V возможных цветов пикселей такого исходного изображения может как совпадать с пространством W возможных аппаратно реализуемых цветов спрайта, так и отличаться от него. В любом случае при блиттинге исходного изображения в поверхность спрайта происходит аппаратное преобразование цветов исходного изображения в аппаратно реализуемые цвета. Это преобразование определяет отображение φ:V→W. Пространство возможных непрозрачных цветов спрайта является подмножеством W⊂W множества всех аппаратно реализуемых цветов, из которого удалены все цвета, которые определяют прозрачный цвет пикселей спрайта. Эти цвета обычно определяются значением цветового ключа и составляют параллелепипед K в пространстве W всех аппаратно реализуемых цветов. Тем самым имеет место частичное отображение φ: V→W, имеющее область определения φ (W)=φ(W)=V/φ(K) (см. фиг.2). Таким образом, соответствие цветов первой структуры данных и возможных непрозрачных цветов спрайта является частичным отображением указанного второго множества в указанное первое множество.
-1
-1
-1
-1
Дополнение φ(K) области определения указанного частичного отображения до указанного второго множества является множеством, мощность которого существенно меньше мощности указанного второго множества. Действительно, как будет видно из п.2, мощность множества K существенно меньше мощности множества W всех аппаратно реализуемых цветов. Кроме того, в реальных ситуациях блиттинга исходного изображения в спрайт число цветов исходного изображения, которые могут переходить в один цвет спрайта, является очень небольшим, иначе качество изображения будет неизбежно испорчено при блиттинге. Отсюда следует, что мощность множества φ(K) существенно меньше мощности указанного второго множества, причем для каждой точки из множества φ(K) найдется близкая к ней точка из области определения V/φ(K) (см. фиг.2).
Возможно несколько вариантов второй структуры данных, определяющей непрозрачную часть формируемого спрайта. В любом случае такая структура данных должна позволять для каждого пикселя формируемого спрайта определять, должен этот пиксель входить в непрозрачную часть спрайта и иметь цвет, соответствующий цвету пикселя исходного изображения, или должен иметь прозрачный цвет. Широко используются по крайней мере три типа структур данных для задания непрозрачной части спрайта: битовая маска, набор горизонтальных отрезков пикселей и векторное задание границы непрозрачной части спрайта.
-1
-1
Порождение спрайта производят следующим образом. Прежде всего, для каждого цвета С из множества φ(K) определяют заменяющей его цвет C', являющийся ближайшим к цвету С из всех цветов, не входящих в множество φ(K). После этого составляют список всех таких пар (С, С') и упорядочивают множество всех таких пар по возрастанию С. Эти действия могут быть произведены один раз перед началом работы приложения, использующего формирование спрайтов. При необходимости построить спрайт по вышеуказанным исходным данным для получения значения каждого пикселя спрайта определяют по второй структуре данных, входит ли указанный пиксель в непрозрачную часть указанного спрайта. Если пиксель входит в непрозрачную часть спрайта, то проверяют, совпадает ли цвет пикселя с одним из цветов С из имеющегося списка пар (С, С'), и если да, то заменяют цвет пикселя С соответствующим цветом С'. В противном случае никакой замены цвета пикселя не производят. После этого устанавливают значение цвета текущего пикселя спрайта равным значению, входящему в указанное первое множество цветов и соответствующему цвету пикселя из первой структуре данных, применяя отображение φ. Если пиксель не входит в непрозрачную часть спрайта, то устанавливают значение цвета текущего пикселя спрайта равным значению, определяющему прозрачный цвет пикселя.
2. Формирование цветового ключа
Цветовой ключ оверлея для вывода спрайтов удобнее всего формировать таким образом, чтобы значение верхней границы диапазона цветового ключа совпадало со значением нижней границы диапазона цветового ключа. Тем самым набор цветов, принадлежащих диапазону цветов цветового ключа, будет состоять только из одного цвета, называемого ключевым цветом. Выбор ключевого цвета зависит от глубины цвета пикселей. Чаще всего в качестве ключевого цвета выбирают фиксированный цвет, который реже всего встречается на реальных изображениях. Приемлемыми являются, например, черный цвет [http://progma.narod.ru/directdraw.html], синий цвет [http://jack.kiev.ua/linuxjournal/LJ/0081/4401.html], красно-синий цвет [http://mini-stalker.googlecode.com/svn-history/r29/trunk/Mini_STALKER/animation.h], фуксин [http://www.gamasutra.com/features/20010629/geczy_02.htm].
Иногда встречается ситуация, когда в качестве цветового ключа используют не один цвет, а множество цветов, представляющих собой параллелепипед в пространстве цветов. Например, в известной технологии «голубого экрана» с целью формирования спрайта производят съемку реальной сцены, например, диктора телевизионной программы, на фоне голубого задника, после чего вырезают только ту часть изображения, которая соответствует реальной сцене. В этом случае в качестве цветового ключа удобно использовать минимальный параллелепипед в пространстве цветов, содержащий цвета всех пикселей изображения, соответствующие заднику.
В любом случае множество цветов, входящих в цветовой ключ, имеет мощность, существенно меньшую мощности всех возможных цветов изображения.
Если исходное изображение, задаваемое первой структурой данных, имеет глубину цвета, совпадающую с глубиной цвета спрайтов, то значение ключевого цвета можно выбрать так, чтобы при конвертировании формата цвета пикселей исходного изображения самое большее один цвет пикселей любого такого исходного изображения при конвертировании принимал значение ключевого цвета. В самом деле, рассмотрим отображение φ цветового пространства исходного изображения в цветовое пространство спрайтов. Поскольку эти два цветовых пространства имеют одинаковую глубину цвета, то мощности двух цветовых пространств совпадают. Следовательно, либо отображение φ биективно, либо не является сюръективным. В первом случае при любом выборе значения ключевого цвета при конвертировании формата цвета пикселей исходного изображения самое большее один цвет пикселей любого такого исходного изображения при конвертировании может принять значение ключевого цвета. Во втором случае в цветовом пространстве оверлейной поверхности существует такое значение цвета, которое лежит вне образа отображения φ. Если это значение взять в качестве ключевого цвета, то при конвертировании формата цвета пикселей исходного изображения ни один цвет пикселей любого такого исходного изображения при конвертировании не сможет принять значение ключевого цвета. Способ реализации такого выбора ключевого цвета очевиден: достаточно конвертировать массив всех цветов цветового пространства исходных изображений в цветовое пространство спрайтов, упорядочить полученные значения по возрастанию и в качестве ключевого цвета выбрать любое значение, пропущенное в полученном массиве цветов. Если пропущенных значений нет, то отображение φ является биективным, и в качестве ключевого цвета можно взять любой цвет.