 |
shedevr.org.ru
Группа перевода приставочных игр "ШЕДЕВР"
|
| Предыдущая тема :: Следующая тема |
| Автор |
Сообщение |
HoRRoR
RRC2008
Зарегистрирован: 21.06.2006
Сообщения: 2341
Откуда: Ростов-на-Дону
|
 Добавлено: Вс Ноя 18, 2007 6:39 pm Заголовок сообщения: Оптимизация графики |
 |
|
Люди, хелп! Кто работал с жёсткой оптимизацией тайловой графики?
В общем, сабж:
Имеется два изображения: 1920x1088 и 860x544. Нужно укомлектовать их тайлы 16x16 в изображение 512x512, координаты могут быть любыми. Но проблема в том, что чтобы это сделать, нужно жёстко всё оптимизировать, т.е. не просто уложить тайлы по сетке, а учесть схожесть каждого тайла со всеми остальными, и исходя не только из этого, но и ещё из оптимальности каждого варианта укладки, сгенерить тайлсет.
Делал ли кто-нибудь что-нибудь подобное? У меня в голове зарождаются мысли, как это сделать, но, боюсь, алгоритм будет очень тормознутым и не даст нужного эффекта...
_________________
Работаю за деньги
KILL ALL HUMANS!!!!!111 |
|
| Вернуться к началу |
|
 |
Shiru
Зарегистрирован: 25.10.2006
Сообщения: 295
Откуда: Russia, Moscow
|
| Добавлено: Вс Ноя 18, 2007 8:41 pm Заголовок сообщения: |
|
|
| Не очень понятно, что ты хочешь. Но в общем случае без потерь будет передано только 1024 твоих тайла (512x512) из 8160 требуемых для 1920x1088. Остальные при более-менее разнообразном изображении будут с хорошо заметными ошибками. |
|
| Вернуться к началу |
|
|
HoRRoR
RRC2008
Зарегистрирован: 21.06.2006
Сообщения: 2341
Откуда: Ростов-на-Дону
|
| Добавлено: Вс Ноя 18, 2007 8:53 pm Заголовок сообщения: |
|
|
| Shiru писал(а): | | Не очень понятно, что ты хочешь. Но в общем случае без потерь будет передано только 1024 твоих тайла (512x512) из 8160 требуемых для 1920x1088. Остальные при более-менее разнообразном изображении будут с хорошо заметными ошибками. |
Нет, суть в том, что сжатие без потерь. Исключаются повторяющиеся и нулевые тайлы. Просто разрабы смогли укомплектовать неповторяющиеся тайлы так, что они смогли уместиться на полотне 512x512. Некоторые тайлы, например, взаимосоставляют друг друга. Щас пойду одним алгоритмом, надеюсь, что разрабы шли тем же путём...
_________________
Работаю за деньги
KILL ALL HUMANS!!!!!111 |
|
| Вернуться к началу |
|
|
АнС
RRC2008
Зарегистрирован: 08.11.2003
Сообщения: 2818
|
| Добавлено: Вс Ноя 18, 2007 11:12 pm Заголовок сообщения: |
|
|
Ты имеешь в виду оптимизацию по принципу карты тайлов + тайлсета? Интересно, случаев с тайлами 16x16 я ещё не встречал, только 8x8 - для таких есть куча утилит типа GIF2SNES и т.п.
Алгоритм тут простой, но далеко не любое изображение можно так оптимизировать - если оригинал влезал в тайлсет 512x512, то изменённый вариант может запросто не влезть, придётся искать варианты упрощения картинок. |
|
| Вернуться к началу |
|
|
HoRRoR
RRC2008
Зарегистрирован: 21.06.2006
Сообщения: 2341
Откуда: Ростов-на-Дону
|
| Добавлено: Пн Ноя 19, 2007 5:50 pm Заголовок сообщения: |
|
|
| АнС писал(а): | Ты имеешь в виду оптимизацию по принципу карты тайлов + тайлсета? Интересно, случаев с тайлами 16x16 я ещё не встречал, только 8x8 - для таких есть куча утилит типа GIF2SNES и т.п.
Алгоритм тут простой, но далеко не любое изображение можно так оптимизировать - если оригинал влезал в тайлсет 512x512, то изменённый вариант может запросто не влезть, придётся искать варианты упрощения картинок. |
Ну блин наверное если бы он был простой, я не создавал бы эту тему.
Там не просто тайлсет, там тайлы в тайлсете не по сетке 16x16 расположены, а самым оптимальным способом.
В прочем, почти реализовал...
_________________
Работаю за деньги
KILL ALL HUMANS!!!!!111 |
|
| Вернуться к началу |
|
|
Shiru
Зарегистрирован: 25.10.2006
Сообщения: 295
Откуда: Russia, Moscow
|
| Добавлено: Пн Ноя 19, 2007 5:57 pm Заголовок сообщения: |
|
|
| Я себе плохо представляю, как можно расположить тайлы единого фиксированного размера не по сетке. Ты-бы хоть пример показал. |
|
| Вернуться к началу |
|
|
HoRRoR
RRC2008
Зарегистрирован: 21.06.2006
Сообщения: 2341
Откуда: Ростов-на-Дону
|
|
| Вернуться к началу |
|
|
BoreS
Зарегистрирован: 03.04.2004
Сообщения: 347
Откуда: KarmaSociety
|
| Добавлено: Пн Ноя 19, 2007 10:23 pm Заголовок сообщения: |
|
|
| а можешь теперь в нормальном виде эту картинку показать? |
|
| Вернуться к началу |
|
|
HoRRoR
RRC2008
Зарегистрирован: 21.06.2006
Сообщения: 2341
Откуда: Ростов-на-Дону
|
|
| Вернуться к началу |
|
|
HoRRoR
RRC2008
Зарегистрирован: 21.06.2006
Сообщения: 2341
Откуда: Ростов-на-Дону
|
| Добавлено: Пн Ноя 19, 2007 11:36 pm Заголовок сообщения: |
|
|
Аллилуйя, написал  Ошибка была наитупейшая, написал два раза n вместо n и m 
Пошёл другим путём, нежели разрабы, но результаты недалеки вроде
_________________
Работаю за деньги
KILL ALL HUMANS!!!!!111 |
|
| Вернуться к началу |
|
|
HoRRoR
RRC2008
Зарегистрирован: 21.06.2006
Сообщения: 2341
Откуда: Ростов-на-Дону
|
| Добавлено: Вт Ноя 20, 2007 1:32 am Заголовок сообщения: |
|
|
Блин, алгоритм не такой эффективный, как хотелось бы
Попробую расширить файл, авось получится...
_________________
Работаю за деньги
KILL ALL HUMANS!!!!!111 |
|
| Вернуться к началу |
|
|
АнС
RRC2008
Зарегистрирован: 08.11.2003
Сообщения: 2818
|
| Добавлено: Вт Ноя 20, 2007 9:23 am Заголовок сообщения: |
|
|
Оригинально придумано.  Не проще было запаковать тайлсет, раз уж у тайлов так много общего, что они могут частично накладываться друг на друга...
Выложил бы ты алгоритм вместе с ресурсами. |
|
| Вернуться к началу |
|
|
Shiru
Зарегистрирован: 25.10.2006
Сообщения: 295
Откуда: Russia, Moscow
|
| Добавлено: Вт Ноя 20, 2007 9:59 am Заголовок сообщения: |
|
|
Думается, это извращение было нужно для экономии видеопамяти, а не места на носителе.
Напомнило мне оптимизацию лайтмапов в 3D графике. М.б., стоит посмотреть на эту тему, алгоритмы должны быть похожи. |
|
| Вернуться к началу |
|
|
HoRRoR
RRC2008
Зарегистрирован: 21.06.2006
Сообщения: 2341
Откуда: Ростов-на-Дону
|
| Добавлено: Вт Ноя 20, 2007 4:25 pm Заголовок сообщения: |
|
|
| АнС писал(а): | | Оригинально придумано. Не проще было запаковать тайлсет, раз уж у тайлов так много общего, что они могут частично накладываться друг на друга... |
Так это потом в добавок ещё и зипуется :)
| АнС писал(а): | | Выложил бы ты алгоритм вместе с ресурсами. |
Ок. Исходники имеешь ввиду?
В общем алгоритм работает, но у меня есть парочка идей, как его улучшить. Вот принцип:
Для начала я сконвертнул полотна в массив байт, чтобы было легче работать. И создал матрицу-маску (boolean), в которой содержалась информация о используемых пикселях тайлсета.
Затем по очереди брал каждый тайл полотен, и на каждой координате тайлсета высчитывал количество совпадающих пикселей взятого блока с блоком тайлсета по тем координатам. Т.е. если пиксель Тайлсет[x,y] занят, и он равен пикслю Полотно[px,py], то увеличиваем количество одинаковых пикселей, а если нет - то всё прерываем, т.к. этот блок явно не подходит.
Если у какого-либо блока получилось 256 совпадений (полное совпадение тайла) - то тоже прерываем и делаем необходимые операции.
В общем, в итоге мы найдём тайл в тайлсете, максимально схожий со взятым тайлом. Туда мы и поместим наш взятый тайл, заюзав все неиспользуемые в нём пиксели.
И так до окончания цикла. Надеюсь, всё понятно :)
| Shiru писал(а): | | Думается, это извращение было нужно для экономии видеопамяти, а не места на носителе. |
Да, так и есть, ибо держать всю картинку в памяти - не хватит ресурсов.
_________________
Работаю за деньги
KILL ALL HUMANS!!!!!111 |
|
| Вернуться к началу |
|
|
Axel
Советник
Зарегистрирован: 14.11.2003
Сообщения: 680
|
| Добавлено: Вт Ноя 20, 2007 4:35 pm Заголовок сообщения: Re: Оптимизация графики |
|
|
| HoRRoR писал(а): | | Люди, хелп!Нужно укомлектовать их тайлы 16x16 в изображение 512x512, координаты могут быть любыми... |
...погугли на тему утилиты gfx2gba (по идее она должна быть в комплекте с devkit arm или palib) она тебе и tileset(.bin) сделает и .map
_________________
Всех их вместе переведём! |
|
| Вернуться к началу |
|
|
HoRRoR
RRC2008
Зарегистрирован: 21.06.2006
Сообщения: 2341
Откуда: Ростов-на-Дону
|
| Добавлено: Вт Ноя 20, 2007 7:10 pm Заголовок сообщения: Re: Оптимизация графики |
|
|
| Axel писал(а): | | HoRRoR писал(а): | | Люди, хелп!Нужно укомлектовать их тайлы 16x16 в изображение 512x512, координаты могут быть любыми... |
...погугли на тему утилиты gfx2gba (по идее она должна быть в комплекте с devkit arm или palib) она тебе и tileset(.bin) сделает и .map |
Нет, ты похоже не понял, в чём проблема Это то я и сам без труда сделаю. Проблема именно в оптимизации... Но большинство карт моим алгоритмом вмещаются, осталось его доработать...
_________________
Работаю за деньги
KILL ALL HUMANS!!!!!111 |
|
| Вернуться к началу |
|
|
АнС
RRC2008
Зарегистрирован: 08.11.2003
Сообщения: 2818
|
| Добавлено: Вт Ноя 20, 2007 8:19 pm Заголовок сообщения: |
|
|
| HoRRoR писал(а): | | АнС писал(а): | | Оригинально придумано. Не проще было запаковать тайлсет, раз уж у тайлов так много общего, что они могут частично накладываться друг на друга... |
Так это потом в добавок ещё и зипуется |
Ну, зипуется после этого оно не так хорошо, как при неоптимизированном тайлсете. Фактически, эта оптимизация похожа на LZ-алгоритм с использованием ранее распакованного словаря.
| HoRRoR писал(а): | Для начала я сконвертнул полотна в массив байт, чтобы было легче работать. И создал матрицу-маску (boolean), в которой содержалась информация о используемых пикселях тайлсета.
Затем по очереди брал каждый тайл полотен, и на каждой координате тайлсета высчитывал количество совпадающих пикселей взятого блока с блоком тайлсета по тем координатам. Т.е. если пиксель Тайлсет[x,y] занят, и он равен пикслю Полотно[px,py], то увеличиваем количество одинаковых пикселей, а если нет - то всё прерываем, т.к. этот блок явно не подходит.
Если у какого-либо блока получилось 256 совпадений (полное совпадение тайла) - то тоже прерываем и делаем необходимые операции.
В общем, в итоге мы найдём тайл в тайлсете, максимально схожий со взятым тайлом. Туда мы и поместим наш взятый тайл, заюзав все неиспользуемые в нём пиксели.
И так до окончания цикла. Надеюсь, всё понятно |
Смотри, а ты не думал, что, скажем, поместив тайл2 максимально идеально к первому (скажем, совпадают 10 пикселей), ты тем самым ограничиваешь возможности для некоторых других тайлов? Например, какой-нибудь двадцатый тайл мог совпасть с первым не на 10, а на 50 точек - но теперь из-за тайла2 уже не получится наложить двадцатый рядом с первым, в итоге ты потерял возможность лучше оптимизировать тайлсет.
Эта идея напрямую взята из flexible parsing алгоритма LZ77. Суть в том, чтобы при переборе значений не тупо брать максимальное значение, а пробовать все, даже не самые идеальный комбинации, делая вывод только в самом конце. |
|
| Вернуться к началу |
|
|
HoRRoR
RRC2008
Зарегистрирован: 21.06.2006
Сообщения: 2341
Откуда: Ростов-на-Дону
|
| Добавлено: Вт Ноя 20, 2007 8:57 pm Заголовок сообщения: |
|
|
| АнС писал(а): | | Смотри, а ты не думал, что, скажем, поместив тайл2 максимально идеально к первому (скажем, совпадают 10 пикселей), ты тем самым ограничиваешь возможности для некоторых других тайлов? Например, какой-нибудь двадцатый тайл мог совпасть с первым не на 10, а на 50 точек - но теперь из-за тайла2 уже не получится наложить двадцатый рядом с первым, в итоге ты потерял возможность лучше оптимизировать тайлсет. |
Да думал, но такой анализ ещё труднее организовать, тем более, что у меня и так карта от 30 секунд пакуется...
Хочу добавить равномерное распределение на две стороны, чтобы не было такого, что сперва заполнялось всё вправо, а потом вниз, и добавить проверку на совпадение целостных линий тайлов, тогда для остальных будет оставаться больше места...
_________________
Работаю за деньги
KILL ALL HUMANS!!!!!111 |
|
| Вернуться к началу |
|
|
Axel
Советник
Зарегистрирован: 14.11.2003
Сообщения: 680
|
| Добавлено: Ср Ноя 21, 2007 12:04 am Заголовок сообщения: Re: Оптимизация графики |
|
|
| HoRRoR писал(а): | | Это то я и сам без труда сделаю. |
надеюсь, что ты написал это ПОСЛЕ того, как прочитал ЧТО умеет gfx2gba 
...твой алгоритм учитывает, что тайлы имеют спец атрибутик (такое есть, думаю, не только на GBA) и могут быть повернуты задом наперёд и вверх ногами (tile flipping) ?
надеюсь, и про оптимизацию палитр, ты тоже прочитал...
(не знаю насколько это актуально для твоего случая, но понижение цветности "жмет" изображение в разы, а при должном подходе, качество не значительно страдает)
кстати, АнС прав, тебе проще рассматривать эту оптимизацию тайлов как "сжатие"...
нарежь всю картинку на тайлы, посчитай частоту встречаемости каждого уникального тайла в картинке (как MDE ), потом среди самых НЕ распространенных (снизу-вверх) ищи более или менее похожие и "схлопывай" их в один... как только число уникальных тайлов станет приемлемым, заканчивай свою оптимизацию...
_________________
Всех их вместе переведём! |
|
| Вернуться к началу |
|
|
HoRRoR
RRC2008
Зарегистрирован: 21.06.2006
Сообщения: 2341
Откуда: Ростов-на-Дону
|
| Добавлено: Ср Ноя 21, 2007 12:46 am Заголовок сообщения: Re: Оптимизация графики |
|
|
| Axel писал(а): |
надеюсь, что ты написал это ПОСЛЕ того, как прочитал ЧТО умеет gfx2gba |
Уверен, что она не может того, что мне нужно :)
| Axel писал(а): | | ...твой алгоритм учитывает, что тайлы имеют спец атрибутик (такое есть, думаю, не только на GBA) и могут быть повернуты задом наперёд и вверх ногами (tile flipping) ? |
Формат не поддерживает ;)
| Axel писал(а): | надеюсь, и про оптимизацию палитр, ты тоже прочитал...
(не знаю насколько это актуально для твоего случая, но понижение цветности "жмет" изображение в разы, а при должном подходе, качество не значительно страдает) |
Цвета там оптимальные и распределены с палитрами так, что индексы палитр обоих слоёв хорошо друг с другом уживаются... Хотя, мб стоит попробовать ещё немного обеднить цветность карты...
| Axel писал(а): | кстати, АнС прав, тебе проще рассматривать эту оптимизацию тайлов как "сжатие"...
нарежь всю картинку на тайлы, посчитай частоту встречаемости каждого уникального тайла в картинке (как MDE ), потом среди самых НЕ распространенных (снизу-вверх) ищи более или менее похожие и "схлопывай" их в один... как только число уникальных тайлов станет приемлемым, заканчивай свою оптимизацию... |
Ну хз, мой алгоритм тоже неплохо справляется, но результат немного хуже оригинала... Надо действительно попробовать пойти именно этим путём...
Есть одна карта, "рукописная", там практически нет одинаковых тайлов. Мой алгоритм оставляет невпихнутыми 35 тайлов, хотя в оригинале впихнуты все, хоть тайлсет и заполнен по максимуму...
Пробовал делать равномерное "растекание" тайлсета от левого верхнего угла - только ухудшило результат на 5 тайлов...
Хоть бери и пиши инструмент для анализа оригинального алгоритма
_________________
Работаю за деньги
KILL ALL HUMANS!!!!!111 |
|
| Вернуться к началу |
|
|
HoRRoR
RRC2008
Зарегистрирован: 21.06.2006
Сообщения: 2341
Откуда: Ростов-на-Дону
|
|
| Вернуться к началу |
|
|
|
|
Вы не можете начинать темы
Вы можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
|
Powered by phpBB © 2001, 2005 phpBB Group
|
FAQ
Поиск
Пользователи
Группы
Регистрация
Профиль
Войти и проверить личные сообщения
Вход
