MapGen: изменить алгоритм поиска треугольника
#37
Reference in New Issue
Block a user
Delete Branch "%!s()"
Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?
Описание задачи
В целях произвести очередную попытку ускорить генерацию мира предлагается изменить алгоритм поиска треугольника, в котором находится точка с координатами генерируемой ноды.
Текущий алгоритм ищет сравнительно неэффективно (хоть и благодаря смежным треугольникам всего один раз за чанк), поскольку перебирает каждый треугольник, проверяет нахождение точки внутри него через барацентрические координаты.
Новый алгоритм должен следовать методу "обхода" треугольников, где в основе лежит опредение точки внутри треугольника через векторное произведение. Если при обходе сторон треугольников против часовой стрелки векторное произведение будет отрицательным (точка будет находится справа), то значит точка уже не лежит в этом треугольнике. Следующий треугольник для проверки — смежный первому по той грани, правее которой лежит точка.
Этот алгоритм так же исключает необходимость предварительной проверки смежных треугольников, который работает сейчас.
Дополнения
No response