Với một hộp giới hạn và một dòng (hai điểm), xác định xem đường có cắt ngang hộp

Question

Với một hộp giới hạn, với các định nghĩa như bounds.min.(x/y/z), bounds.max.(x/y/z) và hai điểm trong không gian 3D (được biểu thị là Vector3 đối tượng), làm cách nào tôi có thể xác định xem đường dây được thực hiện bởi hai điểm cắt hộp giới hạn?

Answer 1

Hãy để tôi google đó cho bạn: Line Box Intersection (http://www.3dkingdoms.com/weekly/weekly.php?a=3)

liên kết khác, với sự tham khảo (và code) cho rất nhiều các bài kiểm tra giao lộ: http://www.realtimerendering.com/intersections.html

Nếu bạn muốn tìm hiểu thêm về các xét nghiệm ngã tư, cái này là kinh thánh: Real-Time Collision Detection (Amazon)

CHỈNH SỬA: thuật toán trong paper ("Thuật toán giao thoa Ray-Box hiệu quả và mạnh mẽ", Amy Williams và Steve Barrus và R. Keith Morley và Peter Shirley; tạp chí đồ họa, gpu , một nd công cụ trò chơi, Vol. 10 (1), 49-54, 2005) trông đặc biệt súc tích và đi kèm với mã nguồn (C++).

Answer 2

Bạn có thể đại diện cho bạn giới hạn hộp là 12 hình tam giác (2 cho mỗi 6 khuôn mặt). Sau đó, bạn có thể kiểm tra giao điểm của tuyến đường của bạn với mỗi người trong số họ. Tôi có một chức năng giao cắt đường tam giác, nhưng nó được viết cho công cụ dựng hình phần mềm của riêng tôi, chứ không phải cho D3D. Tôi có thể thử chuyển đổi nó, nếu bạn cần mã.

Answer 3

Dưới đây là một cách để thực hiện nếu bạn muốn tự làm toán: Giao cắt đường thẳng với mỗi 6 mặt phẳng được tạo bởi hộp giới hạn.

Biểu diễn véc tơ của đường thẳng là X = B + t * D, trong đó B là một Tuple (x, y, z) của điểm gốc (nói, điểm đầu tiên của bạn) và D là hướng của đường thẳng , một lần nữa được biểu thị dưới dạng Tuple (dx, dy, dz). Bạn nhận được hướng bằng cách trừ một trong các điểm từ điểm khác, vì vậy nếu bạn có điểm P1 (x1, y1, z1) và P2 (x2, y2, z2), thì D = P2 - P1 và B = P1, nghĩa là D = (x2 - x1, y2-y1, z2-z1). Chúng ta sẽ gọi các phần tử của vector này là dx, dy và dz.

Biểu diễn tham số của mặt phẳng là x + y + z = c. Vì vậy, hãy chuyển đổi hộp giới hạn của bạn thành represenation này và sau đó sử dụng đại diện tham số của dòng của bạn, ví dụ: ba phương trình x = x1 + t dx, y = y1 + t dy, z = y1 + t * dz, để thay thế x, y và z trong phương trình mặt phẳng của bạn. Giải quyết cho t. Vì mỗi 6 mặt phẳng của bạn sẽ song song với mặt phẳng tạo bởi 2 trục, vấn đề của bạn trở nên dễ dàng hơn; ví dụ cho mặt phẳng song song với mặt phẳng được tạo bởi trục x và y, phương trình phẳng của bạn đơn giản trở thành z = c, trong khi c là tọa độ z của một trong các điểm hộp giới hạn của bạn, v.v.

Bây giờ hãy sử dụng t để tính điểm giao nhau của đường thẳng với mặt phẳng của bạn. (Nếu t là < 0 hoặc> 1, thì đường của bạn giao với OUTSIDE của P1-P2, nếu t> = 0 và t < = 1 thì đường của bạn cắt mặt phẳng ở đâu đó giữa P1 và P2)

Bây giờ bạn ' vẫn chưa xong. Phương trình phẳng cho bạn mặt phẳng chứ không phải hình chữ nhật, vì vậy điểm giao nhau với mặt phẳng thực sự có thể ở bên ngoài hình chữ nhật của bạn, nhưng vì bây giờ bạn có tọa độ giao điểm của bạn (x = x1 + t * dx và vân vân), bạn có thể dễ dàng thấy nếu điểm đó nằm trong hình chữ nhật của hộp giới hạn của bạn. Vấn đề của bạn bây giờ được giảm xuống để kiểm tra xem một điểm trong không gian 2D có nằm trong một hình chữ nhật hộp giới hạn không, đó là tầm thường để kiểm tra. Tất nhiên, điều đầu tiên bạn nên làm nếu bạn thực sự sử dụng giải pháp này là kiểm tra xem đường thẳng có được căn chỉnh dọc theo một trục hay không vì trong trường hợp đó, mã giao lộ của bạn trở nên tầm thường và nó cũng sẽ giải quyết vấn đề dòng không giao nhau với một số mặt phẳng, ví dụsố lượng lớn hoặc nhỏ t, thậm chí có thể quá mức hoặc thấp hơn.

Tôi đặt cược có những cách nhanh hơn để thực hiện việc này, nhưng nó sẽ hoạt động.

Answer 4

Đây là mã mà dường như được làm việc, được chuyển đổi từ câu trả lời Greg S vào C#:

bool CheckLineBox(Vector3 B1, Vector3 B2, Vector3 L1, Vector3 L2, ref Vector3 Hit) 
{ 
    if (L2.x < B1.x && L1.x < B1.x) return false; 
    if (L2.x > B2.x && L1.x > B2.x) return false; 
    if (L2.y < B1.y && L1.y < B1.y) return false; 
    if (L2.y > B2.y && L1.y > B2.y) return false; 
    if (L2.z < B1.z && L1.z < B1.z) return false; 
    if (L2.z > B2.z && L1.z > B2.z) return false; 
    if (L1.x > B1.x && L1.x < B2.x && 
     L1.y > B1.y && L1.y < B2.y && 
     L1.z > B1.z && L1.z < B2.z) 
    { 
     Hit = L1; 
     return true; 
    } 
    if ((GetIntersection(L1.x - B1.x, L2.x - B1.x, L1, L2, ref Hit) && InBox(Hit, B1, B2, 1)) 
     || (GetIntersection(L1.y - B1.y, L2.y - B1.y, L1, L2, ref Hit) && InBox(Hit, B1, B2, 2)) 
     || (GetIntersection(L1.z - B1.z, L2.z - B1.z, L1, L2, ref Hit) && InBox(Hit, B1, B2, 3)) 
     || (GetIntersection(L1.x - B2.x, L2.x - B2.x, L1, L2, ref Hit) && InBox(Hit, B1, B2, 1)) 
     || (GetIntersection(L1.y - B2.y, L2.y - B2.y, L1, L2, ref Hit) && InBox(Hit, B1, B2, 2)) 
     || (GetIntersection(L1.z - B2.z, L2.z - B2.z, L1, L2, ref Hit) && InBox(Hit, B1, B2, 3))) 
     return true; 

    return false; 
} 

bool GetIntersection(float fDst1, float fDst2, Vector3 P1, Vector3 P2, ref Vector3 Hit) 
{ 
    if ((fDst1 * fDst2) >= 0.0f) return false; 
    if (fDst1 == fDst2) return false; 
    Hit = P1 + (P2 - P1) * (-fDst1/(fDst2 - fDst1)); 
    return true; 
} 

bool InBox(Vector3 Hit, Vector3 B1, Vector3 B2, int Axis) 
{ 
    if (Axis == 1 && Hit.z > B1.z && Hit.z < B2.z && Hit.y > B1.y && Hit.y < B2.y) return true; 
    if (Axis == 2 && Hit.z > B1.z && Hit.z < B2.z && Hit.x > B1.x && Hit.x < B2.x) return true; 
    if (Axis == 3 && Hit.x > B1.x && Hit.x < B2.x && Hit.y > B1.y && Hit.y < B2.y) return true; 
    return false; 
} 

Answer 5

phiên bản JavaScript, dựa trên SpikeX câu trả lời và glMatrix:

// all args are Vec3, Hit will be filled by this algo 
function checkLineBox(B1, B2, L1, L2, Hit) 
{ 
    if (L2[0] < B1[0] && L1[0] < B1[0]) return false; 
    if (L2[0] > B2[0] && L1[0] > B2[0]) return false; 
    if (L2[1] < B1[1] && L1[1] < B1[1]) return false; 
    if (L2[1] > B2[1] && L1[1] > B2[1]) return false; 
    if (L2[2] < B1[2] && L1[2] < B1[2]) return false; 
    if (L2[2] > B2[2] && L1[2] > B2[2]) return false; 
    if (L1[0] > B1[0] && L1[0] < B2[0] && 
     L1[1] > B1[1] && L1[1] < B2[1] && 
     L1[2] > B1[2] && L1[2] < B2[2]) 
    { 
     vec3.set(L1, Hit); 
     return true; 
    } 

    if ((getIntersection(L1[0] - B1[0], L2[0] - B1[0], L1, L2, Hit) && inBox(Hit, B1, B2, 1)) 
     || (getIntersection(L1[1] - B1[1], L2[1] - B1[1], L1, L2, Hit) && inBox(Hit, B1, B2, 2)) 
     || (getIntersection(L1[2] - B1[2], L2[2] - B1[2], L1, L2, Hit) && inBox(Hit, B1, B2, 3)) 
     || (getIntersection(L1[0] - B2[0], L2[0] - B2[0], L1, L2, Hit) && inBox(Hit, B1, B2, 1)) 
     || (getIntersection(L1[1] - B2[1], L2[1] - B2[1], L1, L2, Hit) && inBox(Hit, B1, B2, 2)) 
     || (getIntersection(L1[2] - B2[2], L2[2] - B2[2], L1, L2, Hit) && inBox(Hit, B1, B2, 3))) 
     return true; 

    return false; 
} 

var temp = vec3.create(); 
function getIntersection(fDst1, fDst2, P1, P2, Hit) 
{ 
    if ((fDst1 * fDst2) >= 0) return false; 
    if (fDst1 == fDst2) return false; 

    vec3.subtract(P2, P1, temp); 
    vec3.scale(temp, (-fDst1/(fDst2 - fDst1))); 
    vec3.add(temp, P1, Hit); 

    return true; 
} 

function inBox(Hit, B1, B2, Axis) 
{ 
    if (Axis == 1 && Hit[2] > B1[2] && Hit[2] < B2[2] && Hit[1] > B1[1] && Hit[1] < B2[1]) return true; 
    if (Axis == 2 && Hit[2] > B1[2] && Hit[2] < B2[2] && Hit[0] > B1[0] && Hit[0] < B2[0]) return true; 
    if (Axis == 3 && Hit[0] > B1[0] && Hit[0] < B2[0] && Hit[1] > B1[1] && Hit[1] < B2[1]) return true; 
    return false; 
}