HLFX.Ru Forum (https://hlfx.ru/forum/index.php)
- Наши проекты (https://hlfx.ru/forum/forumdisplay.php?forumid=1)
-- XashNT: блог разработчика (https://hlfx.ru/forum/showthread.php?threadid=5297)
Отправлено ncuxonaT 14-03-2020 в 21:03:
Дядя Миша эффективно-эффективно, больше влазит. А размер атласа перед упаковкой ты как выбираешь?
Отправлено Дядя Миша 14-03-2020 в 21:13:
Цитата:
ncuxonaT писал:
А размер атласа перед упаковкой ты как выбираешь?
А, вот в том-то и дело. Размер атласа я тестирую. Алгоритм следующий:
1. список ректанглов сортируется по размеру - самые большие в начале списка.
2. находятся максимальные размеры одного элемента, начальный размер атласа принимается равным им. затем в цикле попеременно увеличивается высота и ширина на четыре пикселя и каждый раз запускается полное построение страницы. Валидным считается такой размер атласа, на котором упаковщик не вернул false.
3. Кармаковский код работает безо всякой сортировки, но, как выяснилось - если ему подать отсортированные ректанглы, то он воспрянет духом и упакует еще плотнее. Упаковщик с нодами без сортировки не работает в принципе.
4. Я повторюсь, протестировал все спрайтесы из халфовского худа, объединяя их по группам, согласно *.txt-спискам - ну там hud.txt, weapon_???.txt. В большинстве случаев оба упаковщика выдали почти идентичные результаты. Фейл наступил только вот на той картинке, что я приложил в аттаче.
Цитата:
ncuxonaT писал:
эффективно-эффективно, больше влазит
Ты смотришь на атлас и думаешь - как же он ловко всё пристроил ни единой лишней дырочки, оставил только одну громадную в правом нижнем углу. А ты пробывал посчитать её площадь и площади тех дырок, что оставляет алгоритм Кармака?
Я теперь понял, что это навроде ошибки выжившего. Мы видим эту дырку и нам кажется, что у нас просто такой резерв остался, потому что ректанглов было меньше чем вмещает в себя площадь квадрата. Но правда в том, что он пакует неоптимально. Что этой дырки вообще могло бы не быть, если паковать алгоритмом Кармака. А сама текстура будет почти в 2 раза меньше по размеру. Так что нет, жуйте сами свой панадол.__________________
My Projects: download page
F.A.Q по XashNT
Блог разработчика в телеграме
Цитата:
C:\DOCUME~1\C4C5~1\LOCALS~1\Temp\a33328if(72) : see declaration of 'size_t'
Отправлено ncuxonaT 14-03-2020 в 21:43:
Цитата:
Дядя Миша писал:
Ты смотришь на атлас и думаешь - как же он ловко всё пристроил ни единой лишней дырочки, оставил только одну громадную в правом нижнем углу. А ты пробывал посчитать её площадь и площади тех дырок, что оставляет алгоритм Кармака?
Я не пробовал считать площадь дырок, потому что это бесполезная метрика. Я упаковывал отсортированные наборы рандомных прямоугольников в атлас заданного размера. Кармаковский алгоритм упаковывал меньше.
Например, генерировал 3000 прямоугольников 2х2-72х72, сортировал их и упаковывал в атлас 2048х2048. Кармаковский алгоритм упаковывал 2000 и говорил "всё, дальше совать некуда". А алгоритм уголком упаковывал 2300.
Добавлено 15-03-2020 в 00:43:
Ладно, не такая большая разница была. Около 5%.
Отправлено Дядя Миша 14-03-2020 в 21:53:
Давай для начала определимся - алгоритм "уголком" без сортировки работать не может, алгоритм Кармака обычно без нее и работает и как-то даже в голову сортировать не приходит. А вот сегодня я отсортировал и очень удивился, насколько стало эффективнее. Ты сортировал исходный массив в обоих случаях?
Цитата:
ncuxonaT писал:
Я не пробовал считать площадь дырок, потому что это бесполезная метрика
А ну вот и я ж про то и говорю - ты видишь максимально плотную упаковку с одной дыркой и тебе кажется что алгоритм эффективнее работает. Хотя у него эта дырка by design. А рандомные небольшие дыры в алгоритме Кармака кажутся фейлами самого алогритма. Я ж говорю, это навроде ошибки выжившего.
На самом деле, я тут немного проанализировал варианты и понял, что кроме двух этих способов в сущности ничего больше и нет. Более плотная упаковка предполагает вращение картинки, а этого бы совсем нехотелось.__________________
My Projects: download page
F.A.Q по XashNT
Блог разработчика в телеграме
Цитата:
C:\DOCUME~1\C4C5~1\LOCALS~1\Temp\a33328if(72) : see declaration of 'size_t'
Отправлено ncuxonaT 14-03-2020 в 21:59:
Дядя Миша сортировал, конечно. Без сортировки это было бы бесполезное сравнение.
Цитата:
Дядя Миша писал:
А ну вот и я ж про то и говорю - ты видишь максимально плотную упаковку с одной дыркой и тебе кажется что алгоритм эффективнее работает.
Я же русским языком объясняю, почему считаю, что алгоритм лучше работает (потому что он запихивает больше кусков). Зачем ты мне приписываешь то, что сам же за меня и придумал?
Отправлено Дядя Миша 15-03-2020 в 08:29:
Я вон выше привёл пример, как оно работает. А твоих примеров я что-то не вижу.
__________________
My Projects: download page
F.A.Q по XashNT
Блог разработчика в телеграме
Цитата:
C:\DOCUME~1\C4C5~1\LOCALS~1\Temp\a33328if(72) : see declaration of 'size_t'
Отправлено ncuxonaT 15-03-2020 в 12:08:
Дядя Миша примеров чего?
Добавлено 15-03-2020 в 15:08:
Цитата:
Дядя Миша писал:
2. находятся максимальные размеры одного элемента, начальный размер атласа принимается равным им. затем в цикле попеременно увеличивается высота и ширина на четыре пикселя и каждый раз запускается полное построение страницы. Валидным считается такой размер атласа, на котором упаковщик не вернул false.
Если не задаваться вопросом "зачем паковать в npot текстуру", то ты хочешь сказать, что уголок смог запихнуть худ в 476х472, а на предыдущем этапе 472х472 он не справился, так?
Отправлено Дядя Миша 15-03-2020 в 12:43:
То что в 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++ или у них совсем не было времени красиво это оформить, скорее всего второе, если вспомнить, что первые итерации халфы со злобным барником не очень сильно отличались от кваки, а потом они сделали героическое усилие и меньше чем за год полностью всё переделали напрочь пуще прежнего.__________________
My Projects: download page
F.A.Q по XashNT
Блог разработчика в телеграме
Цитата:
C:\DOCUME~1\C4C5~1\LOCALS~1\Temp\a33328if(72) : see declaration of 'size_t'
Отправлено ncuxonaT 15-03-2020 в 13:18:
Дядя Миша уголок, 360х360
Отправлено Дядя Миша 15-03-2020 в 13:54:
ncuxonaT реализация откуда?
Добавлено 15-03-2020 в 16:54:
И как ты сортировал ректанглы, покажи функцию.
__________________
My Projects: download page
F.A.Q по XashNT
Блог разработчика в телеграме
Цитата:
C:\DOCUME~1\C4C5~1\LOCALS~1\Temp\a33328if(72) : see declaration of 'size_t'
Отправлено ncuxonaT 15-03-2020 в 14:08:
Дядя Миша отсюда https://blackpawn.com/texts/lightmaps/default.html
Сортировал по большей стороне кусортом
Добавлено 15-03-2020 в 17:08:
https://github.com/juj/RectangleBinPack
вот тут кстати сказано, что этот алгоритм устарел, и некий метод гильотины лучше
Отправлено Дядя Миша 15-03-2020 в 14:38:
Цитата:
ncuxonaT писал:
Сортировал по большей стороне кусортом
Поздравляю, ты стал настоящим программистом. Информация о том, что ты сортировал именно кусортом несомненно важная 
Что значит - по большей стороне? Приведи формулу.
Я к примеру вот так сортирую
C++ Source Code:
1 | static int SortRectangles( const CHudElem *a, const CHudElem *b ) |
3 | return b->w * b->h - a->w * a->h; |
Цитата:
ncuxonaT писал:
некий метод гильотины лучше
Гильотина это вообще ультимативное решение, от всего помогает, даже от короновируса.
Добавлено 15-03-2020 в 17:35:
Поглядел мельком этот метод "гильотины", иш-ты эвристика. Походу ребята реально попытались приспособить BSP-дерево, потому что там сплиты и мержы.
Цитата:
Нет, у Хумуса реализация отличается, главным образом - в плане деления ректанглов. Ну ок, испытаю гильотину, испытаю и твой.
Добавлено 15-03-2020 в 17:38:
Забавно, начал читать ту статью и чувствую что где-то я этот же текст уже видел, но на русском.
А он вот он: https://www.gamedev.ru/pages/coriol...cking_Lightmaps__________________
My Projects: download page
F.A.Q по XashNT
Блог разработчика в телеграме
Цитата:
C:\DOCUME~1\C4C5~1\LOCALS~1\Temp\a33328if(72) : see declaration of 'size_t'
Отправлено ncuxonaT 15-03-2020 в 14:42:
Дядя Миша в твоем варианте это выглядело бы как
C++ Source Code:
return max(b->w , b->h) - max(a->w , a->h); |
Отправлено Дядя Миша 15-03-2020 в 16:59:
ncuxonaT благодарю, опробую и его тожы.
Добавлено 15-03-2020 в 19:59:
ncuxonaT не могу я твой код заставить работать правильно. Тот псевдокод содержит массу фактических ошибок, но то ладно.
Вот здесь вся хитрость:
C++ Source Code:
(if we're just right, accept) |
if img fits perfectly in pnode->rect |
что значит fits perfectly? Прям равно-равно? Или какой-то зазор допускается?__________________
My Projects: download page
F.A.Q по XashNT
Блог разработчика в телеграме
Цитата:
C:\DOCUME~1\C4C5~1\LOCALS~1\Temp\a33328if(72) : see declaration of 'size_t'
Отправлено ncuxonaT 15-03-2020 в 17:11:
Дядя Миша прям равно. Там же дальше идёт разбиение, чтобы если было больше, то стало равно
