Я вот тут помозговал немного. Хочу спросить у всезнающего ALL стоит ли продолжать?
Итак. Имеем идеальный случай. Битмапы у нас упорядочены по площади. Необходимо как можно более компактно разместить их на текстуре.
Алгоритм лайтмапа я смотрел. Но к тому времени уже придумал свой.
Заключается он в том:
— свободные подобласти это области которые не заняты битмапами
— свободные области всегда хранятся упорядоченными по возрастанию их площади (std::multimap)
— свободные области перед вставкой битмапа просматриваются в порядке возрастания их площадей (std::multimap позволит это сделать очень быстро)
— битмап всегда добавляется в верхний левый угол свободной области — изначально эта область есть вся текстура
— после добавления битмапа свободная область разбивается на две подобласти (по вертикале или горизонтали) по принципу разбить так что бы остаточная под-площадь была максимальной
— если при разбиении получается так что в обоих случаях площадь равна друг другу то предпочтение (вертикали или горизонтали) отдается согласно тому что длиннее высота или ширина текстуры
— (дополнительное условие!!!) что бы упаковка получалась более плотной допускается поворот битмапа на 90 градусов в случаях когда его можно вместить в свободную область. Т.е. ширина и высота свободной области позволяет это сделать. Ведь потом можно при отрисовке манипулировать координатами текстуры что бы получить опять правильно повёрнутый битмап.
Алгоритм я ещё не реализовывал, но прогнал его как говорится вручную в Visio.
Задача очень известная, аналогична задаче укладки рюкзака. Что касается текстр то это называется текстурный атлас, кто-то пользуется самопальными алгоритмами вроде твоего, кто-то руками укладывает (есть специальные тулсы например Texture Atlas от Nvidia). Не всегда правда достигается положительный эффект по ускорению насколько я знаю (ведь основная задача текстурных атласов снизить количество переключений текстур и количество исопльзуемых текстрных блоков).
---=== С наилучшими пожеланиями, Phoenics ===--- _
P>Задача очень известная, аналогична задаче укладки рюкзака. Что касается текстр то это называется текстурный атлас, кто-то пользуется самопальными алгоритмами вроде твоего, кто-то руками укладывает (есть специальные тулсы например Texture Atlas от Nvidia). Не всегда правда достигается положительный эффект по ускорению насколько я знаю (ведь основная задача текстурных атласов снизить количество переключений текстур и количество исопльзуемых текстрных блоков).
А есть ли в природе решения не для идеального случая. Я вот уже два дня как бьюсь в поисках, надумал своё писать.
В моем понимании идеальный случай это когда мы заранее имеем список битмапов и можем их упорядочить или по площади или по одной из сторон. И "красиво" уложить.
Но мне нужно решение именно для НЕ идеального случая.
Это когда заранее ты не-знаешь какой битмап тебе прийдёт да ещё к тому же иногда ненужные битмапы удаляют, т.е. как бы освобождают место в текстуре.
Только у него условия немного другие, а конекртено более новые битмапы вытесняют более старые, и происходит дефрагментация, если уложить новый битмап не получается.
Был бы очень благодарен ему если бы он отписался в этой теме. Но почему то он упорно меня игнорирует и на письма не отвечает .
Здравствуйте, nen777w, Вы писали:
N>Это когда заранее ты не-знаешь какой битмап тебе прийдёт да ещё к тому же иногда ненужные битмапы удаляют, т.е. как бы освобождают место в текстуре.
Размеры текстур стандартизованы у тебя?
---=== С наилучшими пожеланиями, Phoenics ===--- _
N>>Это когда заранее ты не-знаешь какой битмап тебе прийдёт да ещё к тому же иногда ненужные битмапы удаляют, т.е. как бы освобождают место в текстуре. P>Размеры текстур стандартизованы у тебя?
Не очень понимаю что значит "стандартизированы". Текстуры у меня зачитываются такие как пользователь захочет.
Здравствуйте, nen777w, Вы писали:
N>Не очень понимаю что значит "стандартизированы". Текстуры у меня зачитываются такие как пользователь захочет.
В данном случае это надо опнимать как набор ограничений накладываемых программой на характеристики текстур. Нпаример то чтоо ни имею размеры кратные двум, хрантся в одном из допустимых для программы форматов и т.д.
Про что хоть рпограмма которую вы делаете?
---=== С наилучшими пожеланиями, Phoenics ===--- _
N>>Не очень понимаю что значит "стандартизированы". Текстуры у меня зачитываются такие как пользователь захочет. P>В данном случае это надо опнимать как набор ограничений накладываемых программой на характеристики текстур. Нпаример то чтоо ни имею размеры кратные двум, хрантся в одном из допустимых для программы форматов и т.д. P>Про что хоть рпограмма которую вы делаете?
Да вот то и делаю что оптимальную упаковку. А в программе которая будет, битмапы будут генерироваться, в зависимости от условий. Поэтому пока что делаю "низа".
N>Только у него условия немного другие, а конекртено более новые битмапы вытесняют более старые, и происходит дефрагментация, если уложить новый битмап не получается.
N>Был бы очень благодарен ему если бы он отписался в этой теме. Но почему то он упорно меня игнорирует и на письма не отвечает .
В этот раздел заглядываю редко, писем не получал, возможно съел злобный спам-фильтр.
Короче, гильотинный раскрой — достаточнго хороший метод на практике, если заранее известны все прямоугольники. Если взять за основу "Packing Lightmaps", то путем несложных модификаций можно ускорить его в несколько раз и улучшить эффективность упаковки. http://antigrain.com/stuff/rect_packer.exe
Сортировать надо по H,W, а не по H*W.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
MS>Короче, гильотинный раскрой — достаточнго хороший метод на практике, если заранее известны все прямоугольники. Если взять за основу "Packing Lightmaps", то путем несложных модификаций можно ускорить его в несколько раз и улучшить эффективность упаковки. MS>http://antigrain.com/stuff/rect_packer.exe MS>Сортировать надо по H,W, а не по H*W.
В том то и дело что какие прийдут заранее я незнаю.
Я тут придумал алгоритм упаковки и дефрагментации на лету.
Т.е. для самых жеских условий когда заранее какой прямоугольник для вставки прийдет я незнаю и когда в любой момент могут
удалить любой вставленный прямоугольник, по сути всё на B-деревьях, когда по дереву можно судить какие области затронет дефрагментация.
Только я вот думаю нужно ли, такие сложности.
_
и на письма не отвечает 
