В моем профилировщике поиск барицентрических координат, очевидно, является узким местом. Я стремлюсь сделать это более эффективным.
Это следует из метода Ширли , где вы вычисляете площадь треугольников, образованных путем вложения точки P внутри треугольника.
Код:
Vector Triangle::getBarycentricCoordinatesAt( const Vector & P ) const
{
Vector bary ;
// The area of a triangle is
real areaABC = DOT( normal, CROSS( (b - a), (c - a) ) ) ;
real areaPBC = DOT( normal, CROSS( (b - P), (c - P) ) ) ;
real areaPCA = DOT( normal, CROSS( (c - P), (a - P) ) ) ;
bary.x = areaPBC / areaABC ; // alpha
bary.y = areaPCA / areaABC ; // beta
bary.z = 1.0f - bary.x - bary.y ; // gamma
return bary ;
}
Этот метод работает, но я ищу более эффективный!
barycentric-coordinates
bobobobo
источник
источник
Ответы:
Переписано из « Обнаружения столкновений в реальном времени» Кристера Эриксона (что, кстати, является отличной книгой):
Это эффективно правило Крамера для решения линейной системы. Вы не станете намного более эффективными, чем эта - если это все еще узкое место (и это может быть: это не похоже на то, что это сильно отличается от вычислений по сравнению с вашим текущим алгоритмом), вам, вероятно, нужно будет найти какое-то другое место чтобы ускориться.
Обратите внимание, что приличное количество значений здесь не зависит от p - их можно кэшировать с помощью треугольника, если это необходимо.
источник
p
для этой функции.Правило Крамера должно быть лучшим способом его решения. Я не графический парень, но мне было интересно, почему в книге «Обнаружение столкновений в реальном времени» они не делают следующую более простую вещь:
Это напрямую решает линейную систему 2x2
в то время как метод из книги решает систему
источник
.z
) измерении (в частности, о том, что оно не существует)?Немного быстрее: предварительно вычислить знаменатель и умножить вместо деления. Деления намного дороже, чем умножения.
В моей реализации, однако, я кэшировал все независимые переменные. Я предварительно рассчитал следующее в конструкторе:
Итак, окончательный код выглядит так:
источник
Я бы использовал решение, опубликованное Джоном, но я бы использовал внутреннюю точку SSS 4.2 и внутреннюю sse rcpss для деления, предполагая, что вы в порядке, ограничивая себя Nehalem и более новыми процессами и ограниченной точностью.
В качестве альтернативы вы можете вычислить несколько барицентрических координат одновременно, используя sse или avx для ускорения в 4 или 8 раз.
источник
Вы можете преобразовать свою трехмерную задачу в двумерную задачу, проецируя одну из выровненных по оси плоскостей и используя метод, предложенный пользователем 5302. Это приведет к точно таким же барицентрическим координатам, если вы убедитесь, что ваш треугольник не выступает в линию. Лучше всего проецировать на выровненную по оси плоскость, которая максимально приближена к ориентации вашего треугольника. Это позволяет избежать проблем с линейностью и обеспечить максимальную точность.
Во-вторых, вы можете предварительно вычислить знаменатель и сохранить его для каждого треугольника. Это экономит вычисления потом.
источник
Я пытался скопировать код @ NielW в C ++, но не получил правильных результатов.
Проще было прочитать https://en.wikipedia.org/wiki/Barycentric_coordinate_system#Barycentric_coordinates_on_triangles и вычислить lambda1 / 2/3, как указано там (векторные функции не нужны).
Если p (0..2) - это Точки треугольника с x / y / z:
Precalc для треугольника:
тогда лямбды для точки «точка»
источник
Для заданной точки N внутри треугольника ABC вы можете получить барицентрический вес точки C, разделив площадь подтреугольника ABN на общую площадь треугольника AB C.
источник