Попиксельный упаковщик лайтмапы: оптимизация

Вот с какой проблемой столкнулся. Попиксельный упаковщик лайтмапы на большом кол-ве кусочков и страниц работает адски долго.
Любые попытки оптимизации приводят к двум негативным результатам. Либо увеличивается скорость, но теряется плотность упаковки, ради которой, собственно, попиксельный упаковщик и используется, либо просто скорость работы падает ещё сильнее.
Попытки нагородить поверх некие ускоряющие структуры проблему не решают: в большом куске вполне могут оказаться дыры, в которые поместится ещё несколько маленьких кусочков, т.е. fast-reject тут просто не сработает. Я так и не придумал что с этим делать.
Может есть какие-то общеизвестные способы оптимизации, просто я не в курсе?
У меня сам алгоритм - просто два вложенных цикла, первый цикл идёт по линиям, второй пытается найти свободное пространство, начиная с незанятого пикселя текущей линии. Ну и конечно же эта проверка предполагает бесконечное сканирование одной и той же страницы атласа для каждого нового кусочка лайтмапы. Какие-то попытки считать число уже использованных пикселей только замедляют алгоритм.

Дерево разбиений + очередь с приоритетом?

CatsCanFly
> Дерево разбиений
внутри любого куска может оказаться дырка произвольной формы. Как её описать деревом, чтобы это не замедлило работу ещё больше\не привело к ухудшению плотности упаковки я не представляю.

g-cont
> внутри любого куска может оказаться дырка произвольной формы
Для дырок строй описанную геометрию, для текущего куска — вписанную, рекурсивно уменьшай разрешение и более детальный уровень проверяй только если прошла проверка более грубого.

Это пробовал: Packing Lightmaps

}:+()___ [Smile]
проблема в том, что эффект от применения дерева (грубо говоря) предполагается при условии что размер структуры узла дерева заведомо меньше тех данных, на которые он ссылается. Здесь же строго обратная ситуация, минимальная единица данных = 1 байт (один маркер использованного пикселя).
И очень часто бывают ситуации когда атлас наполовину забит лайтмапами размером 1х1 люксель - например для травы, кустов.
Либо это дерево вырастет до чудовищных размеров и начнёт тормозить. Либо его после каждого добавления кусочка надо будет как-то перестраивать - и снова получим тормоза.

}:+()___ [Smile]
> можно ускорить с помощью FFT
я подозреваю тогда ухудшится плотность упаковки.

RyKrys
> Это пробовал
Это один из вариантов быстрых методов, аппроксимация до бокса. Но ничто не сравнится по плотности упаковки с попиксельным.

Шел 2024 год ... Рейтрейсинг был в каждом тостере и вот такая проблема

g-cont

Для разработки используй быстрые упаковщики. Для продакшена - более агрессивные.

0xc0de
ну я собственно так и делаю сейчас.

g-cont
> проблема в том, что эффект от применения дерева
Это не дерево, это, скорее, набор mip-map-ов, т. е. полный размер всего в 4/3 раза больше.

> я подозреваю тогда ухудшится плотность упаковки.
FFT — это точное решение (при условии бесконечно точной плавучки): ищет дырки в которые гарантированно поместится текущий спрайт за время, не зависящее от размера этого спрайта.

}:+()___ [Smile]
А причем тут плааучка ?
Dft?