Изменить: это только для моего собственного опыта обучения, это не из соображений производительности, я задаю этот вопрос.
Это касается Minecraft-подобного двигателя местности. Я храню блоки в блоках (блоки 16x256x16 в блоках). Когда я генерирую кусок, я использую несколько процедурных методов, чтобы установить ландшафт и разместить объекты. При генерации я сохраняю один одномерный массив для полного блока (сплошной или нет) и отдельный одномерный массив сплошных блоков.
После генерации я перебираю сплошные блоки, проверяя их соседей, поэтому генерирую только грани блоков, у которых нет сплошных соседей. Я сохраняю лица, которые нужно сгенерировать, в своем собственном списке (это 6 списков, по одному на каждое лицо / нормаль). При рендеринге фрагмента я отображаю все списки в текущем фрагменте камеры и только списки, обращенные к камере во всех остальных фрагментах. Я делаю это, сохраняя все 6 списков в одном буфере, затем просто меняю то, что я рисую.
Используя 2D-атлас с этим маленьким трюком шейдера, предложил Эндрю Рассел, я хочу полностью объединить похожие лица. То есть, если они находятся в одном и том же списке (одинаково нормально), находятся рядом друг с другом, имеют одинаковый уровень освещенности и т. Д. Я знаю, что я все равно получу прямоугольники, но это должно легко уменьшить количество моих вершин на 50% или лучше, если мои оценки верны.
Я предполагаю, что каждый из 6 списков будет отсортирован по оси, на которой они лежат, а затем по двум другим осям (список для верхней части блока будет отсортирован по его значению Y, затем X, затем Z).
С этим одним я мог бы легко объединить полосы лиц, но я хочу объединить больше, чем просто полосы, когда это возможно. Я прочитал об этом жадном алгоритме создания сетки, но у меня много проблем с его пониманием.
Итак, мой вопрос: чтобы выполнить объединение граней, как описано (игнорируя, является ли это плохой идеей для динамического рельефа / освещения), есть ли алгоритм, который проще реализовать? Я также с радостью приму ответ, который проведет меня по жадному алгоритму гораздо проще (ссылка или объяснение).
Я не возражаю против небольшого снижения производительности, если его проще реализовать или даже если оно только немного лучше, чем просто делать полоски. Я беспокоюсь о том, что большинство алгоритмов фокусируются на треугольниках, а не на четырехугольниках, и используя двумерный атлас таким, какой я есть, я не знаю, что я мог бы реализовать что-то треугольник, основываясь на моих текущих навыках.
PS: Я уже отбираю фрустум на кусок и, как описано, я также отбираю грани между сплошными блоками. У меня пока нет окклюзии и, возможно, никогда.
* Редактировать: я реализовал свою собственную маленькую технику, которая, вероятно, имеет имя, но я просто просматриваю свои 6 списков, которые отсортированы по осям, на которых они лежат, затем по типу блока и затем по уровню освещения. Я перебираю их, создавая новые прямоугольники по мере того, как иду и расту их одновременно (с сильным уклоном к определенной оси). Это определенно не оптимально, но это действительно довольно быстро, и это уменьшает мое количество вершин в среднем почти на 50%. Комментарий Byte56 - это шкаф, который я считаю реальным ответом, но я не могу выбрать его для ответа / награды.
Вот мой быстрый и упрощенный способ решения этой проблемы ПОСЛЕ генерации полной начальной местности без какой-либо оптимизации. Предполагая, что все приведенные квадраты - это одно и то же изображение, уровень освещенности, нормаль и т. Д., Каждый цвет - это отдельный квад, который я бы отрисовал. С моими списками, отсортированными так, как они есть, это очень простой / быстрый подход.
источник
Ответы:
Вы только хотите сделать полосы или, в лучшем случае, прямоугольники. Нет никаких других форм, которые будут решаемыми или полезными для вас.
Я также хотел бы отметить, что, сохраняя 6 списков на блок, вы в любой момент будете использовать 5 списков из блоков в основных направлениях и по крайней мере 3 в каждом другом. Вы тратите время здесь, когда не только видеокарта может выполнить эту оптимизацию для вас, но даже если вы сделали это самостоятельно, вам было бы лучше хранить все лица в одном месте и сравнивать нормаль к направлению с камера (исследование DOT произведения векторов).
Ссылки CaptainRedMuff на Greedy Mesh, которые вы уже видели, являются ответом на вашу проблему. Из этого также должно быть очевидно, что у вас получатся «полосатые» сетки, но они будут совершенно эффективными, а создание чего-то более оптимального будет более сложным, и вы уже говорили, что жадная сетка уже слишком сложна.
Если у вас проблемы с производительностью одного блока, это заставляет меня думать, что что-то еще сильно не так.
Моим первым предположением будет то, что вы слишком часто вызываете операцию рисования. Вы можете указать графической карте рисовать только от 50 до 400 раз в секунду, в зависимости от аппаратного обеспечения. Сколько звонков вы делаете в .setData или .draw ____ Примитивы?
источник
Статья, на которую вы ссылаетесь, на самом деле не дает алгоритм для генерации меша; в нем указывается способ оценки возможных решений.
В целом, однако, статья дает хорошее резюме: 1) наивное решение плохое, 2) есть оптимальное решение, но оно будет и трудоемким, чтобы писать и запускать, 3) быстрый отбор дает гораздо лучшие результаты ( и это все, что делает сам Minecraft), и, наконец, 4) может быть более разумное решение (жадный алгоритм).
«Решение», которое вы подразумеваете на изображении в своем вопросе, - это жадный алгоритм. Кажется, твой вопрос "правильно ли я реализовал его решение?" на что я должен ответить «он не дал решения; ты просто решил это сам».
Может ли ваше решение быть лучше? Мех. Конечно. Наверное, не стоит. Я думаю, что отбор окклюзии или LOD будет лучше в следующих шагах. Minecraft тратит большое количество циклов, рисуя поверхность, даже когда вы находитесь под землей, а также рисуя обширные сети пещерных и шахтных систем, когда вы находитесь на поверхности. Как только у вас получится хорошее разбиение сетки, да, избавление от затененных поверхностей может быть хорошей вещью - но (например), как правило, быстрее позволить вашей видеокарте отбирать заднюю поверхность, чем делать это на процессоре.
источник