ncuxonaT писал: А размер атласа перед упаковкой ты как выбираешь?
А, вот в том-то и дело. Размер атласа я тестирую. Алгоритм следующий:
1. список ректанглов сортируется по размеру - самые большие в начале списка.
2. находятся максимальные размеры одного элемента, начальный размер атласа принимается равным им. затем в цикле попеременно увеличивается высота и ширина на четыре пикселя и каждый раз запускается полное построение страницы. Валидным считается такой размер атласа, на котором упаковщик не вернул false.
3. Кармаковский код работает безо всякой сортировки, но, как выяснилось - если ему подать отсортированные ректанглы, то он воспрянет духом и упакует еще плотнее. Упаковщик с нодами без сортировки не работает в принципе.
4. Я повторюсь, протестировал все спрайтесы из халфовского худа, объединяя их по группам, согласно *.txt-спискам - ну там hud.txt, weapon_???.txt. В большинстве случаев оба упаковщика выдали почти идентичные результаты. Фейл наступил только вот на той картинке, что я приложил в аттаче.
Цитата:
ncuxonaT писал: эффективно-эффективно, больше влазит
Ты смотришь на атлас и думаешь - как же он ловко всё пристроил ни единой лишней дырочки, оставил только одну громадную в правом нижнем углу. А ты пробывал посчитать её площадь и площади тех дырок, что оставляет алгоритм Кармака?
Я теперь понял, что это навроде ошибки выжившего. Мы видим эту дырку и нам кажется, что у нас просто такой резерв остался, потому что ректанглов было меньше чем вмещает в себя площадь квадрата. Но правда в том, что он пакует неоптимально. Что этой дырки вообще могло бы не быть, если паковать алгоритмом Кармака. А сама текстура будет почти в 2 раза меньше по размеру. Так что нет, жуйте сами свой панадол.
Дядя Миша писал: Ты смотришь на атлас и думаешь - как же он ловко всё пристроил ни единой лишней дырочки, оставил только одну громадную в правом нижнем углу. А ты пробывал посчитать её площадь и площади тех дырок, что оставляет алгоритм Кармака?
Я не пробовал считать площадь дырок, потому что это бесполезная метрика. Я упаковывал отсортированные наборы рандомных прямоугольников в атлас заданного размера. Кармаковский алгоритм упаковывал меньше.
Например, генерировал 3000 прямоугольников 2х2-72х72, сортировал их и упаковывал в атлас 2048х2048. Кармаковский алгоритм упаковывал 2000 и говорил "всё, дальше совать некуда". А алгоритм уголком упаковывал 2300.
Давай для начала определимся - алгоритм "уголком" без сортировки работать не может, алгоритм Кармака обычно без нее и работает и как-то даже в голову сортировать не приходит. А вот сегодня я отсортировал и очень удивился, насколько стало эффективнее. Ты сортировал исходный массив в обоих случаях?
Цитата:
ncuxonaT писал: Я не пробовал считать площадь дырок, потому что это бесполезная метрика
А ну вот и я ж про то и говорю - ты видишь максимально плотную упаковку с одной дыркой и тебе кажется что алгоритм эффективнее работает. Хотя у него эта дырка by design. А рандомные небольшие дыры в алгоритме Кармака кажутся фейлами самого алогритма. Я ж говорю, это навроде ошибки выжившего.
На самом деле, я тут немного проанализировал варианты и понял, что кроме двух этих способов в сущности ничего больше и нет. Более плотная упаковка предполагает вращение картинки, а этого бы совсем нехотелось.
Дядя Миша сортировал, конечно. Без сортировки это было бы бесполезное сравнение.
Цитата:
Дядя Миша писал: А ну вот и я ж про то и говорю - ты видишь максимально плотную упаковку с одной дыркой и тебе кажется что алгоритм эффективнее работает.
Я же русским языком объясняю, почему считаю, что алгоритм лучше работает (потому что он запихивает больше кусков). Зачем ты мне приписываешь то, что сам же за меня и придумал?
Дядя Миша писал: 2. находятся максимальные размеры одного элемента, начальный размер атласа принимается равным им. затем в цикле попеременно увеличивается высота и ширина на четыре пикселя и каждый раз запускается полное построение страницы. Валидным считается такой размер атласа, на котором упаковщик не вернул false.
Если не задаваться вопросом "зачем паковать в npot текстуру", то ты хочешь сказать, что уголок смог запихнуть худ в 476х472, а на предыдущем этапе 472х472 он не справился, так?
То что в bmp - 368х368 пикселей, алгоритм Кармака.
То, что в png - алгоритм "уголком" 476х472
Цитата:
ncuxonaT писал: Если не задаваться вопросом "зачем паковать в npot текстуру"
Скорее наоборот. Последнее железо, которое валилось в эмуляцию с NPOT было GF6600. А вот текстурной памяти много не бывает. Я не вижу никаких причин не паковать сейчас текстуры в NPOT, особенно для худа. Ну да, для трёхмерки наверное воздержусь, но для GUI разницы никакой. Потому что, если паковать в POT, обе текстуры были бы 512х512 и ты бы каким-то неведомым образом определил, что уголок эффективнее. А я это доказал на самом наглядном примере - что кармаковский алгоритм уложился в меньшие размеры. И нельзя сказать, что размер атласа был выбран неправильно, я же говорю, там в цикле идёт серия тестов, до тех пор, пока упаковщик сам не скажет - ок, теперь мне достаточно места. Соответственно ширина и высота на каждой итерации растут по 4 пикселя.
Конечно я не исключаю варианта, что моя реализация упаковки уголком какая-то калечная (брал у того же Humusa). Ну ок, вот тебе исходный набор данных - халфовский hud.txt, все ректанглы для разрешения 640. Распарси текстовик и сам посмотри, что у тебя получится. Если он у тебя упакует эффективнее, скажи какую реализацию уголком ты юзаешь.
Потому что, повторюсь, она в целом показала почти идентичные результаты и зафейлила только вот на этом наборе данных. Тот же набор ректанглов для разрешения 320 она очень хорошо упаковала (но всё равно чуть-чуть хуже, чем кармаковский алгоритм).
Добавлено 15-03-2020 в 15:41:
В аттаче приложил пример упаковки для разрешения 320. То что tree - это вот как раз уголок.
Добавлено 15-03-2020 в 15:43:
Ну да ладно, вернёмся к нашым баранам.
Клиентский рендеринг худа в халфе писали какие-то садисты. Или эти люди очень не любили C++ или у них совсем не было времени красиво это оформить, скорее всего второе, если вспомнить, что первые итерации халфы со злобным барником не очень сильно отличались от кваки, а потом они сделали героическое усилие и меньше чем за год полностью всё переделали напрочь пуще прежнего.
Вложение: hud_320.zip (15.4 кб)
Этот файл был скачан 72 раз.
ncuxonaT писал: Сортировал по большей стороне кусортом
Поздравляю, ты стал настоящим программистом. Информация о том, что ты сортировал именно кусортом несомненно важная
Что значит - по большей стороне? Приведи формулу.
Я к примеру вот так сортирую
14-03-2020 21:03
Вложение: 
