bin packing — может эфективно запаковывать прямоугольники в один большой прямоугольник,
а ктото встречал алгоритм который бы эфективно менеджерил добавление и удаление, такой себе аллокатор в 2D

Здравствуйте, IROV.., Вы писали:

IRO>bin packing — может эфективно запаковывать прямоугольники в один большой прямоугольник,
IRO>а ктото встречал алгоритм который бы эфективно менеджерил добавление и удаление, такой себе аллокатор в 2D

Тетрис?

Здравствуйте, Sharowarsheg, Вы писали:

S>Здравствуйте, IROV.., Вы писали:

IRO>>bin packing — может эфективно запаковывать прямоугольники в один большой прямоугольник,
IRO>>а ктото встречал алгоритм который бы эфективно менеджерил добавление и удаление, такой себе аллокатор в 2D

S>Тетрис?
Тетрис пакует

Здравствуйте, IROV.., Вы писали:

IRO>bin packing — может эфективно запаковывать прямоугольники в один большой прямоугольник,
IRO>а ктото встречал алгоритм который бы эфективно менеджерил добавление и удаление, такой себе аллокатор в 2D

Дай угадаю... пишешь что то вроде текстурного менеджера для динамически генерируемых процедурных текстур?
Я когда то обсуждал такое здесь

Автор: nen777w
Дата: 13.03.08

и вот здесь

Автор: nen777w
Дата: 14.03.08

.
Но на практике сделал попроще, способ не помню, надо восстанавливать по коду, но вроде работает для тех нужд что я писал нормально (судя по дампу текстур из gDebugger).

Здравствуйте, IROV.., Вы писали:

IRO>bin packing — может эфективно запаковывать прямоугольники в один большой прямоугольник,
IRO>а ктото встречал алгоритм который бы эфективно менеджерил добавление и удаление, такой себе аллокатор в 2D

Это нерешаемая задача, но я ее решил — эффективный динамический кэш для глифов в видеопамяти. Как именно сделано — не скажу, не имею права, извиняйте. Но задача была очень увлекательная.

Здравствуйте, McSeem2, Вы писали:

MS>Это нерешаемая задача, но я ее решил — эффективный динамический кэш для глифов в видеопамяти. Как именно сделано — не скажу, не имею права, извиняйте. Но задача была очень увлекательная.

При всем уважении... Для чего был этот пост? Просто напомнить о своей крутизне?

Просто напоминание, что нерешаемые задачи решаемы

Здравствуйте, nen777w, Вы писали:

N>Здравствуйте, IROV.., Вы писали:

IRO>>bin packing — может эфективно запаковывать прямоугольники в один большой прямоугольник,
IRO>>а ктото встречал алгоритм который бы эфективно менеджерил добавление и удаление, такой себе аллокатор в 2D

N>Дай угадаю... пишешь что то вроде текстурного менеджера для динамически генерируемых процедурных текстур?
N>Я когда то обсуждал такое здесь

Автор: nen777w
Дата: 13.03.08

и вот здесь

Автор: nen777w
Дата: 14.03.08

.
N>Но на практике сделал попроще, способ не помню, надо восстанавливать по коду, но вроде работает для тех нужд что я писал нормально (судя по дампу текстур из gDebugger).
Да, радилась тут идейка, но для ее решения нужна такая штука, а сложно найти? хочется хотя бы примерно понять как лучше сделать это

Здравствуйте, supacrazypusher, Вы писали:

S>Просто напоминание, что нерешаемые задачи решаемы

На самом деле — с ограничениями, но вполне разумными. Правда потом пришлось огребать от саппорта и объяснять, что я таким образом просто повысил емкость кэша в несколько раз на мелких глифах. А на крупных — тут уж ничего не поделаешь, минимально гарантированная емкость остается такой же, как и в случае банального разбиения на квадраты. Но мой метод оказался очень востребованным для CJK.

Здравствуйте, McSeem2, Вы писали:

MS>Здравствуйте, IROV.., Вы писали:

IRO>>bin packing — может эфективно запаковывать прямоугольники в один большой прямоугольник,
IRO>>а ктото встречал алгоритм который бы эфективно менеджерил добавление и удаление, такой себе аллокатор в 2D

MS>Это нерешаемая задача, но я ее решил — эффективный динамический кэш для глифов в видеопамяти. Как именно сделано — не скажу, не имею права, извиняйте. Но задача была очень увлекательная.

https://sourceforge.net/p/atlasallocator

вот мой увлекательный вечер

Здравствуйте, IROV.., Вы писали:

IRO>https://sourceforge.net/p/atlasallocator
IRO>вот мой увлекательный вечер

Че-то ни фига не понятно, хотя-бы скриншот какой-никакой.
У меня вот есть демо http://antigrain.com/stuff/dyna_2d_cache2.exe
Это даже больше чем аллокатор — это 2D кэш со стратегией LRU, но не строгой, а приблизительной. Слайдерами слева внизу можно регулировать размеры и смотреть, как алгоритм адаптируется к новым условиям. Да, главное ограничение — это максимальная высота прямоугольника, но это нормально для поставленной задачи, поскольку большие буквы уже выгоднее тесселировать и кэшировать в виде мешей.

Здравствуйте, McSeem2, Вы писали:

MS>Здравствуйте, IROV.., Вы писали:

IRO>>https://sourceforge.net/p/atlasallocator
IRO>>вот мой увлекательный вечер

MS>Че-то ни фига не понятно, хотя-бы скриншот какой-никакой.
MS>У меня вот есть демо http://antigrain.com/stuff/dyna_2d_cache2.exe
MS>Это даже больше чем аллокатор — это 2D кэш со стратегией LRU, но не строгой, а приблизительной. Слайдерами слева внизу можно регулировать размеры и смотреть, как алгоритм адаптируется к новым условиям. Да, главное ограничение — это максимальная высота прямоугольника, но это нормально для поставленной задачи, поскольку большие буквы уже выгоднее тесселировать и кэшировать в виде мешей.
У меня не буквы,

спасибо, посмотрю демку

Здравствуйте, IROV.., Вы писали:

IRO>bin packing — может эфективно запаковывать прямоугольники в один большой прямоугольник,
IRO>а ктото встречал алгоритм который бы эфективно менеджерил добавление и удаление, такой себе аллокатор в 2D

Присоединяюсь. Собственно, совершенно вообще не понимаю, почему на эту тему так трудно что-либо найти. Это же абсолютно первостепенная задача, возникающая при работе с аппаратной графикой (оптимизация переключения текстур). Может, все это решают каким-то другим способом?

Здравствуйте, IROV.., Вы писали:

IRO>bin packing — может эфективно запаковывать прямоугольники в один большой прямоугольник,
IRO>а ктото встречал алгоритм который бы эфективно менеджерил добавление и удаление, такой себе аллокатор в 2D

Сдается мне, надо задать вопрос на StackOverflow, а то этот форум какой-то совсем тухлый.

Здравствуйте, Аноним, Вы писали:

А>Присоединяюсь. Собственно, совершенно вообще не понимаю, почему на эту тему так трудно что-либо найти. Это же абсолютно первостепенная задача, возникающая при работе с аппаратной графикой (оптимизация переключения текстур). Может, все это решают каким-то другим способом?

Начиная с DX10, эта проблема решается текстурными массивами.

Здравствуйте, Don Reba, Вы писали:

DR>Начиная с DX10, эта проблема решается текстурными массивами.

А ежели у меня OpenGL ES 2.0?

Здравствуйте, McSeem2, Вы писали:

MS>Это даже больше чем аллокатор — это 2D кэш со стратегией LRU, но не строгой, а приблизительной. Слайдерами слева внизу можно регулировать размеры и смотреть, как алгоритм адаптируется к новым условиям. Да, главное ограничение — это максимальная высота прямоугольника, но это нормально для поставленной задачи, поскольку большие буквы уже выгоднее тесселировать и кэшировать в виде мешей.

Это гораздо более простая задача.

Здравствуйте, IROV.., Вы писали:

IRO>bin packing — может эфективно запаковывать прямоугольники в один большой прямоугольник,
IRO>а ктото встречал алгоритм который бы эфективно менеджерил добавление и удаление, такой себе аллокатор в 2D

Следил, следил за этой темой, а потом решил сам поискать, и ключевые слова оказались достаточно очевидными: dynamic bin packing.