Полагаю, мы можем справедливо предположить, что многоугольники не пересекаются. Если это так, нам не нужно ничего разбивать. Тем не менее, поиск правильного порядка все еще требует больших вычислительных ресурсов. Хотя, возможно, можно придумать поэтапный подход, который обновляет только необходимые вещи от кадра к кадру.
Так вот в чем дело. В вашем примере с 2 полигонами базирование порядка на двух ближайших точках линии, очевидно, не работает, поскольку они имеют разные направления просмотра. Но если вы выберете точки с одинаковым направлением обзора (в области, где они перекрываются), вы четко увидите, что A находится перед B. Итак, что нам нужно сделать:
Сначала найдите все стены, которые видны. Мы создадим график видимости для этих стен. Итак, создайте график, где каждая стена представлена узлом. В конце вы вычислите топологическую сортировку этого графика, чтобы получить порядок рисования. Теперь, как мы можем найти края, то есть информацию о том, какая стена перед другой? Для этого сначала найдите пары стен, которые перекрываются (экструдированная стена). Возможно, вы захотите использовать структуру данных ускорения, такую как дерево AABB, чтобы сделать это быстро.
Тогда нам нужна одномерная параметризация направления обзора. Угол между направлением и осью X может работать довольно хорошо (a = atan2(lineY - playerY, lineX - playerX)), хотя он имеет эту раздражающую периодичность, с которой вам нужно справиться. Теперь мы рассмотрим только исходные полигональные ребра для двух стен (а не вытянутые). Найдите 1D интервалы для двух линий (например, линия 1 находится между 10 ° и 35 °, а линия 2 находится между 20 ° и 135 °). Если эти два интервала не перекрываются, вы можете пропустить эту пару, поскольку их относительный порядок не имеет значения. Если это так, найдите любую точку в перекрывающемся интервале (например, 25 °), найдите соответствующее направление обзора (x = playerX + cos(25°), y = playerY + sin(25°)) и точки на линии, которые соответствуют этому направлению (например, путем вычисления пересечения линии с видом лучи). Затем просто вычислите расстояния двух линий вдоль этого луча. Неважно, какую точку в интервале перекрытия вы выберете, потому что линии линейные и исходные многоугольники не пересекаются. Если расстояние до линии 1 меньше расстояния до линии 2, добавьте направленный край от линии 1 до линии 2 к графику видимости (это означает, что линия 1 находится перед линией 2), в противном случае добавьте обратный край.
Наконец, рассчитайте топологический порядок графа, и у вас есть порядок рисования.
Вариант 2
Вот альтернатива вышеуказанному подходу, которая может быть более эффективной для динамического рендеринга. Идея основана на этой публикации .
Сначала триангулируйте вашу сцену, то есть заполните пустоты треугольниками (это нужно сделать только один раз). Затем наш график видимости хранит треугольники (не ребра). Для каждого ребра треугольника, который вы видите изнутри, добавьте ребро из треугольника в соседний треугольник, инцидентный этому ребру. В конце снова вычислите топологическую сортировку и нарисуйте ваши стены в этом порядке (пропуская пустые треугольники).
Эффективность в динамическом случае проистекает из того факта, что вам нужно только делать небольшие обновления в вашем графике. Для каждого из ребер вы хотите определить, видите ли вы их спереди или сзади. Следовательно, направление края будет изменено только в том случае, если точка обзора пересекает бесконечную линию, заданную краем. Если вы найдете все эти ребра (которые изменили направление со времени последнего кадра), вы можете обновить график и отсортировать его соответствующим образом.