Apa cara paling efisien untuk menemukan koordinat barycentric?

45

Dalam profiler saya, menemukan koordinat barycentric tampaknya agak macet. Saya ingin membuatnya lebih efisien.

Ini mengikuti metode di shirley , di mana Anda menghitung luas segitiga yang dibentuk dengan menyematkan titik P di dalam segitiga.

bary

Kode:

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

Metode ini berhasil, tetapi saya sedang mencari yang lebih efisien!

bobobobo
sumber
2
Berhati-hatilah karena solusi yang paling efisien mungkin paling tidak akurat.
Peter Taylor
Saya sarankan Anda membuat unit test untuk memanggil metode ini ~ 100rb kali (atau yang serupa) dan mengukur kinerjanya. Anda dapat menulis tes yang memastikan itu kurang dari beberapa nilai (misalnya 10s), atau Anda dapat menggunakannya hanya untuk membandingkan penerapan yang lama dengan yang baru.
ashes999

Jawaban:

54

Ditranskrip dari Deteksi Tabrakan Real-Time Christer Ericson (yang, kebetulan, adalah buku yang sangat bagus):

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

Ini adalah aturan Cramer yang efektif untuk menyelesaikan sistem linear. Anda tidak akan mendapatkan jauh lebih efisien daripada ini — jika ini masih merupakan hambatan (dan mungkin saja: itu tidak terlihat seperti jauh lebih baik dari algoritma saat ini), Anda mungkin harus mencari tempat lain untuk mendapatkan speedup.

Perhatikan bahwa sejumlah nilai yang layak di sini tidak bergantung pada p —mereka dapat di-cache dengan segitiga jika perlu.

John Calsbeek
sumber
7
# operasi dapat menjadi herring merah. Bagaimana mereka tergantung dan menjadwalkan banyak hal pada CPU modern. selalu uji asumsi dan "peningkatan" kinerja.
Sean Middleditch
1
Kedua versi tersebut memiliki latensi yang hampir sama di jalur kritis, jika Anda hanya melihat operasi matematika skalar. Hal yang saya sukai dari yang ini adalah bahwa dengan membayar ruang hanya untuk dua pelampung, Anda dapat mencukur satu pengurangan dan satu pembagian dari jalur kritis. Apakah itu sepadan? Hanya tes kinerja yang tahu pasti ...
John Calsbeek
1
Dia menggambarkan bagaimana dia mendapatkan ini di halaman 137-138 dengan bagian tentang "titik terdekat pada segitiga ke titik"
bobobobo
1
Catatan kecil: tidak ada argumen puntuk fungsi ini.
Bart
2
Catatan implementasi minor: Jika ketiga poin berada di atas satu sama lain, Anda akan mendapatkan kesalahan "bagi dengan 0", jadi pastikan untuk memeriksa kasus itu dalam kode aktual.
frodo2975
9

Aturan Cramer harus menjadi cara terbaik untuk menyelesaikannya. Saya bukan seorang pria grafis, tetapi saya bertanya-tanya mengapa dalam buku Deteksi Tabrakan Real-Time mereka tidak melakukan hal sederhana berikut ini:

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

Ini secara langsung memecahkan sistem linier 2x2

v v0 + w v1 = v2

sedangkan metode dari buku memecahkan sistem

(v v0 + w v1) dot v0 = v2 dot v0
(v v0 + w v1) dot v1 = v2 dot v1
pengguna5302
sumber
Bukankah solusi yang Anda usulkan membuat asumsi tentang .zdimensi ketiga ( ) (khususnya, bahwa itu tidak ada)?
Cornstalks
1
Ini adalah metode terbaik di sini jika seseorang bekerja dalam 2D. Hanya perbaikan kecil: seseorang harus menghitung kebalikan dari penyebut untuk menggunakan dua perkalian dan satu divisi alih-alih dua divisi.
rubik
8

Sedikit lebih cepat: Precompute penyebutnya, dan lipat gantinya dengan membagi. Divisi jauh lebih mahal daripada perkalian.

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

Dalam implementasi saya, bagaimanapun, saya cache semua variabel independen. Saya pra-kalk berikut di konstruktor:

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

Jadi kode akhir terlihat seperti ini:

// 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
sumber
2

Saya akan menggunakan solusi yang diposting John, tetapi saya akan menggunakan SSS 4.2 dot intrinsic dan sse rcpss intrinsik untuk membagi, dengan asumsi Anda ok membatasi diri ke Nehalem dan proses yang lebih baru dan presisi terbatas.

Atau Anda bisa menghitung beberapa koordinat barycentric sekaligus menggunakan sse atau avx untuk speedup 4 atau 8x.

Crowley9
sumber
1

Anda dapat mengubah masalah 3D Anda menjadi masalah 2D dengan memproyeksikan salah satu bidang yang selaras sumbu dan menggunakan metode yang diusulkan oleh user5302. Ini akan menghasilkan koordinat barikentrik yang sama persis selama Anda memastikan segitiga Anda tidak terproyeksi menjadi garis. Yang terbaik adalah memproyeksikan ke bidang sejajar sumbu yang sedekat mungkin dengan orientasi triagle Anda. Ini menghindari masalah co-linearitas dan memastikan akurasi maksimum.

Kedua, Anda dapat melakukan pra-komputasi penyebut dan menyimpannya untuk setiap segitiga. Ini menyimpan perhitungan sesudahnya.

Gert
sumber
1

Saya mencoba untuk menyalin kode @ NielW ke C ++, tetapi saya tidak mendapatkan hasil yang benar.

Lebih mudah untuk membaca https://en.wikipedia.org/wiki/Barycentric_coordinate_system#Barycentric_coordinates_on_triangles dan menghitung lambda1 / 2/3 sebagaimana diberikan di sana (tidak diperlukan fungsi vektor).

Jika p (0..2) adalah Poin dari segitiga dengan x / y / z:

Precalc untuk segitiga:

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

maka lambda untuk "titik" Point adalah

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;
pengguna1712200
sumber
0

Untuk titik tertentu N di dalam segitiga ABC, Anda bisa mendapatkan bobot barikentrik titik C dengan membagi area subtriangle ABN dengan total luas segitiga AB C.

Pengelak
sumber