Итак, если бы я пытался просто реализовать это, я бы, вероятно, начал с глобального поиска всех треугольников - вычислил барицентрические координаты этой 2-й точки для каждого треугольника, найдите треугольник, где все барицентрические координаты все положительные, а затем используйте их для отображения в 3d (умножьте позицию stu на 3d точки). Сначала я бы сделал это, и только если бы он был недостаточно быстрым, я бы попробовал что-то более сложное.
Если возможно выполнить итерацию по треугольнику, а не по 2d точкам, то барицентрический метод, вероятно, будет достаточно быстрым. Но кажется, что у вас есть набор 2d точек в произвольных позициях, которые необходимо отобразить, и точки меняют положение от кадра к кадру?
Если вы столкнулись с такой ситуацией, вы, вероятно, могли бы значительно ускорить реализацию локального обновления для каждого кадра. Каждая 2-ая точка помнит, в каком треугольнике она была. Установите это как текущий треугольник. Проверьте, находится ли новая позиция в текущем треугольнике. Если нет, то вы хотите пройти меш до соседнего треугольника, который находится ближе всего к целевой 2d точке. Каждый смежный с ребром треугольник состоит из двух общих точек на ребре плюс еще одна точка. Найдите, какая другая точка соседнего с ребром треугольника находится ближе всего к цели, и установите ее как текущую. Затем повторяем - кажется, он должен найти это довольно быстро? Вы также можете кэшировать максимальный размер для каждого треугольника, поэтому, если точка сильно сместилась, вы можете просто перейти к следующему соседу без выполнения барицентрических вычислений (максимальный размер должен быть таким, чтобы расстояние было таким, что если вы дальше этого На расстоянии от любой точки треугольника нет шансов, что вы находитесь внутри треугольника. Это длина наибольшего края).
Но, как вы упоминаете в своих комментариях, вы можете столкнуться с проблемами с сетками, которые имеют вогнутости, дыры или отдельные подключенные компоненты, где вы можете попасть в локальный минимум. Есть несколько способов справиться с этим. Я думаю, что самое простое - сохранить список всех посещенных треугольников (возможно, в виде флага на треугольнике, векторе или установить <индекс треугольника>) и отказаться от повторного посещения треугольника. Если вы обнаружите, что вы посетили всех соседей вашего текущего треугольника, вернитесь к глобальному поиску. Такие сбои, скорее всего, будут редкостью, поэтому это не должно сильно сказываться на вашей производительности.
Этот вид обновления для каждого кадра может быть очень быстрым и даже может быть достойным подходом для вычисления исходных содержащих треугольников - просто выберите случайный треугольник и идите оттуда (переход от проверки всех n треугольников к только тем, которые примерно по прямой линии к цели). Если это не достаточно быстро, то вы можете сохранить k-d дерево (или что-то подобное) из 2d точек сетки, а также один индекс касания треугольника для каждой точки сетки. Чтобы начать итерацию, найдите ближайшую точку к целевой 2d-точке в дереве k-d, установите текущий треугольник в соседнем треугольнике, а затем выполните итерацию.