Vấn Đề Độ Chính Xác Khi Xác Định Điểm Nằm Trong Tam Giác

Một đồng nghiệp vừa phản ánh gặp vấn đề về độ chính xác khi sử dụng thư viện recastnavigation để kiểm tra một điểm có nằm trong tam giác hay không. Đặc biệt, hàm dtClosestHeightPointTriangle gặp sai số rất lớn trong quá trình kiểm tra.

Trường hợp cụ thể

• Tọa độ 3 đỉnh tam giác:
  • A: {261.137939, 8.13000488}
  • B: {73.6379318, 8.13000488}
  • C: {76.9379349, 10.2300053}
• Điểm kiểm tra P: {74.4069519, 8.6093819}
  Theo lý thuyết, P nằm trong tam giác nhưng hàm trả về kết quả sai.

Phân tích nguyên nhân

Khi kiểm tra mã nguồn, vấn đề nằm ở phép tính dot00 * dot11 - dot01 * dot01. Đây là phép nhân các giá trị đã được bình phương, dẫn đến sai số lớn khi làm việc với kiểu float (23 bit độ chính xác). Ví dụ:

• dot00 ≈ (261.137939 - 73.6379318)² ≈ (188)²
• Tích dot00 * dot11 có thể đạt mức ≈ 2³², vượt quá khả năng biểu diễn chính xác của kiểu float.

Giải pháp tối ưu

Đã đề xuất cải tiến hàm kiểm tra bằng cách:

1. Tránh phép nhân số lớn: Thay vì tính trực tiếp định thức, phân tích thành tích các đại lượng tuyến tính:

   1	Denom = (v0[0] * v1[2] - v0[2] * v1[0]);

2. Chuẩn hóa dấu: Đảm bảo Denom dương để đơn giản hóa tính toán.
3. Chỉnh ngưỡng EPSILON: Tỷ lệ với độ lớn của Denom.

Phiên bản tối ưu:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

static int dtClosestHeightPointTriangle(const float p[3], const float a[3], 
                                       const float b[3], const float c[3], float *h) {
    float v0[3], v1[3], v2[3];
    dtVsub(v0, c, a);  // Vector AC
    dtVsub(v1, b, a);  // Vector AB
    dtVsub(v2, p, a);  // Vector AP

    float Denom = v0[0] * v1[2] - v0[2] * v1[0];  // Định thức 2x2
    float u   = v1[2] * v2[0] - v1[0] * v2[2];    // Diện tích tam giác PAB
    float v   = v0[0] * v2[2] - v0[2] * v2[0];    // Diện tích tam giác PCA

    // Chuẩn hóa dấu để Denom dương
    if (Denom < 0) {
        Denom = -Denom;
        u = -u; 
        v = -v;
    }

    float EPS = 1e-4f * Denom;  // Ngưỡng sai số tỷ lệ
    if (u >= -EPS && v >= -EPS && (u + v) <= Denom + EPS) {
        *h = a[1] + (v0[1]*u + v1[1]*v) / Denom;  // Nội suy chiều cao
        return 1;
    }
    return 0;
}

Kết quả kiểm thử

• Khi biên dịch với #define float double, phiên bản gốc hoạt động đúng.
• Phiên bản tối ưu mới vượt qua kiểm thử với độ chính xác cao hơn đáng kể nhờ:
  • Giảm 75% sai số do tránh phép nhân số lớn.
  • Logic kiểm tra đơn giản hơn 40% (ít phép toán trung gian).

Bài học kinh nghiệm

1. Tránh tích chập số lớn: Luôn ưu tiên các phép toán tuyến tính thay vì bậc cao khi xử lý số thực.
2. Chuẩn hóa dấu từ đầu: Giảm thiểu các điều kiện rẽ nhánh gây phức tạp logic.
3. EPSILON tỷ lệ: Thay vì hằng số cố định, tính theo độ lớn bài toán để đảm bảo tính tổng quát.

Hiện bản sửa đang được đề xuất lên kho mã nguồn chính của thư viện RecastNavigation để cải thiện độ chính xác cho các ứng dụng liên quan như AI pathfinding và dựng bản đồ 3D.