Как эффективно сгруппировать пространство вокселей в наименьшее количество подобных смежных блоков?
Во-первых, я прошу прощения, если мой вопрос неясен. Поиск в Google и чтение книг, которые я проводил в течение последних нескольких недель по этой теме, не выявили никакой терминологии для проблемы, которую я пытаюсь решить. Я опишу свою проблему как можно лучше; если кто-нибудь знает правильный жаргон, чтобы помочь мне более кратко выразить мою проблему, пожалуйста, дайте мне знать.
Я изучаю, насколько возможно использовать воксели для представления больших (256x256x256 вокселей) полей битвы с разрушаемым ландшафтом для многопользовательских игр на сервере. Для любой игры одновременно может существовать только одно поле битвы. Однако, чтобы иметь возможность транслировать комнаты и изменения в их местности, я пытаюсь найти алгоритм, который может сгруппировать воксели в наименьшее количество прямоугольных блоков, насколько это возможно. В качестве упрощенного примера, если нижняя половина уровня была полностью заполнена вокселями одного типа, а верхняя половина - вокселями другого типа, уровень следует разделить на два блока, один из которых представляет нижнюю половину уровня, и другой, представляющий вершину. В идеале этот алгоритм должен быть в состоянии работать в режиме реального времени, чтобы любая деформация на местности могла учитываться для каждого кадра и передаваться клиентам. Это должно позволить клиентам эффективно визуализировать ландшафт, не беспокоясь о дублировании логики уничтожения ландшафта в клиентах.
Я не нашел нигде статей о том, как это сделать. Я пытался искать статьи о двигателях вокселей; Я не думаю, что куски достаточно хороши для моих нужд. Я просмотрел книги и статьи по интеллектуальному анализу данных, но, не зная правильной терминологии для моей проблемы, я не смог найти эффективный поиск. Я даже смотрел на вычислительную геометрию в C: Второе издание Джозефа О'Рурка, но, похоже, ничего не помогло.
Вот подходы, которые я пробовал, и проблемы, с которыми я сталкиваюсь. Сообщается, что количество блоков заполнено на 256^3 пробелов путем случайного сбрасывания более 4 194 304 вокселей "ЗЕМЛЯ" настолько близко к основанию, насколько это возможно для произвольно выбранной координаты (x,z). Учитываются только блоки "ЗЕМЛЯ".
- Octrees: очень быстро, но если я разделю в середине пробела, получится смехотворно большое количество блоков (800 000+)
- расщепление деревьев в кД для минимизации взвешенной энтропии после расщепления: немного медленнее, чем октри, но значительно меньше блоков (~350 000)
- Разделение деревьев kD для максимизации коэффициента получения информации: в два раза быстрее, чем в предыдущем методе деревьев kD, генерируя гораздо меньше блоков (~167 000), но все еще медленный
- Разбиение деревьев в кД для минимизации сходства Гауэра: очень медленно, но генерирует меньше блоков, чем в любом другом методе дерева кД (~155 000)
- жадный захват самого большого подмножества непересекающихся, самых больших блоков объема, доступных при рассмотрении каждого невостребованного блока "ЗЕМЛЯ" в качестве определяющей точки блока: даже многопоточный, этот алгоритм непристойно медленен (~ 16 минут с 8 потоками в 8-ядерной системе), но он генерирует наименьшее количество блоков из всех (<65 536)
- жадно захватывает наибольшее подмножество непересекающихся блоков, рассматривая размеры блока как объективные оценки, чтобы максимизировать: гораздо медленнее, чем другой жадный подход, и генерирует еще несколько тысяч блоков
Учитывая, что максимально допустимое количество блоков составляет один блок на координату (x,y) для представления одного столбца, только жадный объем имеет результаты, которые можно считать даже близкими к оптимальным.
Я не знаю, как вычислить минимальное количество блоков без использования подхода грубой силы, который никогда не заканчивается, поэтому я не знаю, возможно ли добиться большего успеха, чем подход с жадным объемом. Кроме того, я не знаю, как я могу сделать это быстрее.
Может кто-нибудь дать мне алгоритм, чтобы попытаться или, по крайней мере, указать мне правильное направление? Я хотел бы прекратить исследовать это направление и подумать о другом способе решения моей проблемы, если это не может быть сделано лучше.