Каков наиболее эффективный способ поиска барицентрических координат?

В моем профилировщике поиск барицентрических координат, по-видимому, является узким местом. Я ищу, чтобы сделать его более эффективным.

Он следует методу в ширли , где вы вычисляете площадь треугольников, образованных вложением точки P внутри треугольника.

bary

код:

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 ;
}

Этот метод работает, но я ищу более эффективный!

40 голосов | спросил bobobobo 12 FebruaryEurope/MoscowbSun, 12 Feb 2012 06:14:36 +0400000000amSun, 12 Feb 2012 06:14:36 +040012 2012, 06:14:36

7 ответов


44

Транскрипция из обнаружения конфликтов в реальном времени (что, кстати говоря, отличная книга) Chirister Ericson:

// Compute barycentric coordinates (u, v, w) for
// point p with respect to triangle (a, b, c)
void Barycentric(Point p, Point a, Point b, Point c, float &u, float &v, float &w)
{
    Vector v0 = b - a, v1 = c - a, v2 = p - a;
    float d00 = Dot(v0, v0);
    float d01 = Dot(v0, v1);
    float d11 = Dot(v1, v1);
    float d20 = Dot(v2, v0);
    float d21 = Dot(v2, v1);
    float denom = d00 * d11 - d01 * d01;
    v = (d11 * d20 - d01 * d21) / denom;
    w = (d00 * d21 - d01 * d20) / denom;
    u = 1.0f - v - w;
}

Это эффективное правило Крамера для решения линейной системы. Вы не будете намного эффективнее, чем это - если это все еще является узким местом (и это может быть: это не похоже на то, что это намного отличается от вашего текущего алгоритма), вам, вероятно, придется найти другую место, чтобы получить ускорение.

Обратите внимание, что приличное количество значений здесь не зависит от p - их можно кэшировать с помощью треугольника, если это необходимо.

ответил John Calsbeek 12 FebruaryEurope/MoscowbSun, 12 Feb 2012 08:20:42 +0400000000amSun, 12 Feb 2012 08:20:42 +040012 2012, 08:20:42
7

Чуть быстрее: предопределите знаменатель и умножьте вместо деления. Разделы намного дороже, чем умножения.

// Compute barycentric coordinates (u, v, w) for
// point p with respect to triangle (a, b, c)
void Barycentric(Point a, Point b, Point c, float &u, float &v, float &w)
{
    Vector v0 = b - a, v1 = c - a, v2 = p - a;
    float d00 = Dot(v0, v0);
    float d01 = Dot(v0, v1);
    float d11 = Dot(v1, v1);
    float d20 = Dot(v2, v0);
    float d21 = Dot(v2, v1);
    float invDenom = 1.0 / (d00 * d11 - d01 * d01);
    v = (d11 * d20 - d01 * d21) * invDenom;
    w = (d00 * d21 - d01 * d20) * invDenom;
    u = 1.0f - v - w;
}

В моей реализации, однако, я кэшировал все независимые переменные. Я предварительно вычисляю в конструкторе следующее:

Vector v0;
Vector v1;
float d00;
float d01;
float d11;
float invDenom;

Итак, окончательный код выглядит следующим образом:

// Compute barycentric coordinates (u, v, w) for
// point p with respect to triangle (a, b, c)
void Barycentric(Point a, Point b, Point c, float &u, float &v, float &w)
{
    Vector v2 = p - a;
    float d20 = Dot(v2, v0);
    float d21 = Dot(v2, v1);
    v = (d11 * d20 - d01 * d21) * invDenom;
    w = (d00 * d21 - d01 * d20) * invDenom;
    u = 1.0f - v - w;
}
ответил NielW 14 FebruaryEurope/MoscowbThu, 14 Feb 2013 21:25:03 +0400000000pmThu, 14 Feb 2013 21:25:03 +040013 2013, 21:25:03
7

Правило Крамера должно быть лучшим способом его решения. Я не графический парень, но мне было интересно, почему в книге «Обнаружение столкновений в реальном времени» они не выполняют следующую простую вещь:

// Compute barycentric coordinates (u, v, w) for
// point p with respect to triangle (a, b, c)
void Barycentric(Point p, Point a, Point b, Point c, float &u, float &v, float &w)
{
    Vector v0 = b - a, v1 = c - a, v2 = p - a;
    den = v0.x * v1.y - v1.x * v0.y;
    v = (v2.x * v1.y - v1.x * v2.y) / den;
    w = (v0.x * v2.y - v2.x * v0.y) / den;
    u = 1.0f - v - w;
}

Это прямо решает линейную систему 2x2

v v0 + w v1 = v2

, в то время как метод из книги решает систему

(v v0 + w v1) dot v0 = v2 dot v0
(v v0 + w v1) dot v1 = v2 dot v1
ответил user5302 7 +04002013-10-07T10:08:24+04:00312013bEurope/MoscowMon, 07 Oct 2013 10:08:24 +0400 2013, 10:08:24
2

Я бы воспользовался решением, которое отправил Джон, но я бы использовал встроенные SSS 4.2 и встроенные ss rcpss для разделения, предполагая, что вы в порядке ограничиваете себя Nehalem и более новыми процессами и с ограниченной точностью.

В качестве альтернативы вы можете одновременно вычислить несколько барицентрических координат, используя sse или avx для ускорения 4 или 8 раз.

ответил Crowley9 14 FebruaryEurope/MoscowbTue, 14 Feb 2012 07:06:24 +0400000000amTue, 14 Feb 2012 07:06:24 +040012 2012, 07:06:24
1

Я попытался скопировать код @ NielW на C ++, но я не получил правильных результатов.

Легче было читать https://en.wikipedia.org/wiki/Barycentric_coordinate_system#Barycentric_coordinates_on_triangles и вычислить lambda1 /2/3, как указано (нет необходимости в векторных функциях).

Если p (0..2) - точки треугольника с x /y /z:

Precalc для треугольника:

double invDET = 1./((p(1).y-p(2).y) * (p(0).x-p(2).x) + 
                   (p(2).x-p(1).x) * (p(0).y-p(2).y));

, то лямбда для точки «точка» являются

double l1 = ((p(1).y-p(2).y) * (point.x-p(2).x) + (p(2).x-p(1).x) * (point.y-p(2).y)) * invDET; 
double l2 = ((p(2).y-p(0).y) * (point.x-p(2).x) + (p(0).x-p(2).x) * (point.y-p(2).y)) * invDET; 
double l3 = 1. - l1 - l2;
ответил user1712200 8 FebruaryEurope/MoscowbMon, 08 Feb 2016 15:22:57 +0300000000pmMon, 08 Feb 2016 15:22:57 +030016 2016, 15:22:57
0

Вы можете преобразовать 3D-проблему в двумерную задачу, проецируя одну из плоскостей, выровненных по оси, и используйте метод, предложенный user5302. Это приведет к точно таким же барицентрическим координатам, если вы убедитесь, что ваш треугольник не проецируется в линию. Лучше всего проецировать на плоскость, выровненную по оси, максимально приближенную к ориентации вашего триагле. Это предотвращает проблемы сорилинейности и обеспечивает максимальную точность.

Во-вторых, вы можете предварительно вычислить знаменатель и сохранить его для каждого треугольника. Это впоследствии экономит вычисления.

ответил Gert 20 PMpMon, 20 Apr 2015 15:12:11 +030012Monday 2015, 15:12:11
0

Для данной точки N внутри треугольника A B C вы можете получить барицентрический вес точки C, разделив область поддиапазона A B N на общую площадь треугольника A B C.

ответил Dodger 29 MarpmTue, 29 Mar 2016 23:54:32 +03002016-03-29T23:54:32+03:0011 2016, 23:54:32

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132