MapGen: изменить алгоритм поиска треугольника #37

Closed
opened 2026-03-11 07:14:21 +00:00 by varttist · 0 comments
Owner

Описание задачи

В целях произвести очередную попытку ускорить генерацию мира предлагается изменить алгоритм поиска треугольника, в котором находится точка с координатами генерируемой ноды.

Текущий алгоритм ищет сравнительно неэффективно (хоть и благодаря смежным треугольникам всего один раз за чанк), поскольку перебирает каждый треугольник, проверяет нахождение точки внутри него через барацентрические координаты.

Новый алгоритм должен следовать методу "обхода" треугольников, где в основе лежит опредение точки внутри треугольника через векторное произведение. Если при обходе сторон треугольников против часовой стрелки векторное произведение будет отрицательным (точка будет находится справа), то значит точка уже не лежит в этом треугольнике. Следующий треугольник для проверки — смежный первому по той грани, правее которой лежит точка.

Этот алгоритм так же исключает необходимость предварительной проверки смежных треугольников, который работает сейчас.

Дополнения

No response

### Описание задачи В целях произвести очередную попытку ускорить генерацию мира предлагается изменить алгоритм поиска треугольника, в котором находится точка с координатами генерируемой ноды. Текущий алгоритм ищет сравнительно неэффективно (хоть и благодаря смежным треугольникам всего один раз за чанк), поскольку перебирает каждый треугольник, проверяет нахождение точки внутри него через барацентрические координаты. Новый алгоритм должен следовать методу "обхода" треугольников, где в основе лежит опредение точки внутри треугольника через векторное произведение. Если при обходе сторон треугольников против часовой стрелки векторное произведение будет отрицательным (точка будет находится справа), то значит точка уже не лежит в этом треугольнике. Следующий треугольник для проверки — смежный первому по той грани, правее которой лежит точка. Этот алгоритм так же исключает необходимость предварительной проверки смежных треугольников, который работает сейчас. ### Дополнения _No response_
varttist added the
task
assigned
2
priority
hight
1
labels 2026-03-11 07:14:21 +00:00
varttist self-assigned this 2026-03-11 07:14:21 +00:00
varttist added this to the Tasks Kanban project 2026-03-11 07:14:21 +00:00
varttist moved this to To Do in Tasks Kanban on 2026-03-11 07:14:52 +00:00
varttist moved this to In Progress in Tasks Kanban on 2026-03-11 07:15:08 +00:00
varttist added
task
pause
2
and removed
task
assigned
2
labels 2026-03-20 20:07:03 +00:00
varttist added
task
completed
3
and removed
priority
hight
1
task
pause
2
labels 2026-03-28 15:37:13 +00:00
varttist moved this to Done in Tasks Kanban on 2026-03-28 15:37:19 +00:00
Sign in to join this conversation.
No Label
task
completed
3
1 Participants
Notifications
Due Date
No due date set.
Dependencies

No dependencies set.

Reference: Apancore.Studio/simple-makes-complex#37