Tính toán va chạm sử dụng kỹ thuật hộp bao theo hướng và ứng dụng trong tuyên truyền giao thông

Chia sẻ: Thi Thi | Ngày: | Loại File: PDF | Số trang:9

Thêm vào BST

Báo xấu

68
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Va chạm là vấn đề không thể thiếu trong bất kỳ một hệ thống thực tại ảo nào (VR). Do đó, nghiên cứu các phương pháp phát hiện va chạm là một mục tiêu hàng đầu mà các hệ thống thực tại ảo quan tâm. Bài báo này trình bày một kỹ thuật phát hiện va chạm dựa trên việc tính toán các hộp bao theo hướng (Oriented Bounding Boxes) và có cải tiến để phát hiện va chạm. Kỹ thuật nghiên cứu đã được áp dụng vào hệ thống “Giúp bạn đi an toàn” - một hệ thống thực tại ảo mô phỏng giao thông. Hệ thống có thể trợ giúp con người biết cách đi như thế nào để an toàn khi tham gia giao thông.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tính toán va chạm sử dụng kỹ thuật hộp bao theo hướng và ứng dụng trong tuyên truyền giao thông

Đỗ Năng Toàn và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 120(06): 161 – 169 TÍNH TOÁN VA CHẠM SỬ DỤNG KỸ THUẬT HỘP BAO THEO HƢỚNG VÀ ỨNG DỤNG TRONG TUYÊN TRUYỀN GIAO THÔNG Đỗ Năng Toàn1, Nông Minh Ngọc2* 1 Viện Công nghệ thông tin, 2Đại học Thái Nguyên TÓM TẮT Va chạm là vấn đề không thể thiếu trong bất kỳ một hệ thống thực tại ảo nào (VR). Do đó, nghiên cứu các phƣơng pháp phát hiện va chạm là một mục tiêu hàng đầu mà các hệ thống thực tại ảo quan tâm. Bài báo này trình bày một kỹ thuật phát hiện va chạm dựa trên việc tính toán các hộp bao theo hƣớng (Oriented Bounding Boxes) và có cải tiến để phát hiện va chạm. Kỹ thuật nghiên cứu đã đƣợc áp dụng vào hệ thống “Giúp bạn đi an toàn” - một hệ thống thực tại ảo mô phỏng giao thông. Hệ thống có thể trợ giúp con ngƣời biết cách đi nhƣ thế nào để an toàn khi tham gia giao thông. Từ khóa: Phát hiện va chạm, OBBs, AABB, Thực tại ảo. GIỚI THIỆU* Phát hiện va chạm là một trong những vấn đề trọng tâm của mỗi hệ thống thực tại ảo. Các đối tƣợng trong mỗi hệ thống đồ hoạ có những chuyển động riêng của nó, trong khi chuyển động đó có thể va chạm với đối tƣợng khác, hoặc có thể va chạm với môi trƣờng, chƣớng ngại vật,... Đối với phƣơng pháp phát hiện va chạm theo các hộp bao thì ta có hai kỹ thuật khác nhau đó là sử dụng hộp bao có các cạnh song song với các trục toạ độ (axis-aligned bounding boxes - AABBs) hoặc là hộp bao theo hƣớng của đối tƣợng (Oriented Bounding Boxe OBBs ). Việc phát hiện va chạm giữa các hộp bao AABBs đƣợc thực hiện nhanh chóng nhƣng sai số lớn, trong khi đó phát hiện va chạm giữa các hộp bao OBBs tuy phức tạp hơn nhƣng lại cho sai số nhỏ hơn nhiều. Bài báo này sẽ trình bày kỹ thuật phát hiện va chạm dựa vào các hộp bao OBBs và đƣa ra một cải tiến để giảm thời gian xử lý các hộp bao. Cuối cùng, chúng tôi đã áp dụng kỹ thuật trên vào hệ thống “Giúp bạn đi an toàn khi tham giao thông ” - một hệ thống thực tại ảo mô phỏng các tình huống giao thông nhằm tuyên truyền, trợ giúp ngƣời dùng biết cách đi nhƣ thế nào để an toàn nhất khi tham gia giao thông. * Tel: 0968 595888 KỸ THUẬT HỘP BAO THEO HƢỚNG (ORIENTED BOUNDING BOXES) Định nghĩa hộp bao theo hƣớng (Oriented Bounding Boxes-OBBs) Trong phần này, tất cả các vectors đƣợc hiểu là trong không gian R3. Một hình hộp OBB bao gồm một tâm C, ba    vector A0 , A1 , A2 chỉ hƣớng của hình hộp và 3 hệ số độ dài tƣơng ứng với kích thƣớc của hình hộp là a0 >0, a1>0, a2>0. Khi đó, 8 đỉnh của hình hộp sẽ đƣợc xác định nhƣ sau: 2 C  si ai * Ai | si | 1, i 0,1,2. (1) i 0 Kỹ thuật phát hiện hộp bao theo hƣớng đƣợc chia làm hai mức. Mức một là kiểm tra “nhanh” xem có va chạm nào xảy ra không? Nếu không có va chạm nào xảy ra thì hệ thống vẫn làm việc bình thƣờng, có ít nhất một va chạm xảy ra thì sẽ chuyển sang mức hai là tìm chính xác điểm va chạm của các hộp bao. Định lý: Việc kiểm tra hai khối đa diện lồi không giao nhau nếu có thể cô lập đƣợc chúng bằng một mặt phẳng P thoả mãn một trong hai điều kiện sau: - P song song với một mặt nào đó của một trong hai khối đa diện. - Hoặc là P chứa một cạnh thuộc đa diện thứ nhất và một đỉnh thuộc đa diện thứ hai. 161 Đỗ Năng Toàn và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ Từ định lý trên, ta rút ra nhận xét sau cho phép kiểm tra nhanh sự giao nhau của hai hai khối đa diện lồi: Điều kiện cần và đủ để kiểm tra hai khối đa diện lồi có giao nhau hay không là kiểm tra giao nhau giữa các hình chiếu của chúng lên đƣờng thẳng vuông góc với mặt phẳng P ở trên, đƣờng thẳng này đƣợc gọi là trục cô lập. Ta thấy rằng các hộp bao OBBs là những khối đa diện lồi, bởi vậy ta hoàn toàn có thể áp dụng định lý trên để kiểm tra va chạm giữa chúng. Phƣơng pháp kiểm tra va chạm giữa hai hộp bao OBBs Cho hai hình bao OBBs xác định bởi các thông số [C0,A0,A1,A2,a0,a1,a2] và [C1,B0,B1,B2,b0,b1,b2]. Ta thấy rằng các tình huống mà hai OBBs tiếp xúc với nhau (không cắt nhau) chỉ có thể là một trong 6 trƣờng hợp sau đây: mặt - mặt, mặt - cạnh, mặt - đỉnh, cạnh - cạnh, cạnh - đỉnh, đỉnh - đỉnh. Do vậy, tập ứng cử viên các trục cô lập chỉ tối đa là 15 trục sau: 120(06): 161 – 169 P d H C0 Hình 1. Hình chiếu của P lên đường thẳng d Nhƣ vậy, khi chiếu 8 đỉnh của hộp bao thứ nhất lên trục cô lập d với gốc C0 thì sẽ thu đƣợc 4 cặp đoạn thẳng có độ dài bằng nhau nằm về hai phía so với C0 (hình 2), độ dài của mỗi đoạn thẳng đƣợc xác định nhƣ sau :   si * ai * Ai ) * V 0  | |V | 2  hc(C0 2  si * ai * Ai , d ) | i 0 ( i (2)  - 3 trục chỉ hƣớng của hộp bao thứ nhất ( Ai )  - 3 trục chỉ hƣớng của hộp bao thứ hai ( B j ) - 9 trục tạo bởi tích có hƣớng của một trục thuộc hộp bao thứ nhất và một trục thuộc hộp  bao thứ hai ( Ai  B j ). Mặt khác, ta biết rằng nếu một trục là trục cô lập thì khi tịnh tiến đến vị trí nào, nó vẫn là trục cô lập. Bởi vậy, không mất tính tổng quát ta sẽ gọi trục cô lập có vector chỉ phƣơng là V và đi qua tâm C0 của hộp bao thứ nhất, do vậy nó có phƣơng trình nhƣ sau:   d = C 0 + t* V    Trong đó: t là tham số. V là Ai hoặc B j hoặc Ai B j với i, j = 0,1,2. Gọi P là một điểm bất kỳ, hình chiếu của P lên đƣờng thẳng d với gốc C0 sẽ là đoạn thẳng C0H xác định nhƣ sau : hc( P, d ) 162    ( P C0 ) *V  |V | Hình 2. Chiếu 8 đỉnh của hình hộp lên trục cô lập d Nhƣ vậy, khoảng cách nhỏ nhất chứa 8 đoạng thẳng (2) sẽ có tâm có tâm là C0 và bán kính r0 đƣợc xác định nhƣ sau :   si * ai * Ai ) * V 0  |} |V | 2 ( r0 = max { | i Với mọi |si| = 1. (3)  Đặt R0 = r0* | V | , ta có:      R0 = max{| a0* A0 * V + a1* A1 * V +   a2* A2 *V |       | a0* A0 * V + a1* A1 * V - a2* A2 *V | Đỗ Năng Toàn và Đtg    Tạp chí KHOA HỌC & CÔNG NGHỆ    Giải cụ thể các phƣơng trình trên. Với mỗi | a0* A0 * V - a1* A1 * V + a2* A2 *V |       | a0* A0 * V - a1* A1 * V - a2* A2 *V |       |-a0* A0 * V + a1* A1 * V + a2* A2 *V |       |-a0* A0 * V + a1* A1 * V - a2* A2 *V |       |-a0* A0 * V - a1* A1 * V + a2* A2 *V |       |-a0* A0 * V - a1* A1 * V - a2* A2 *V |}       = a0*| A0 * V | + a1*| A1 * V | + a2*| A2 *V |  Với D Đặt : |si| = 1. i  ci 0 B0 AT*B = C  ci1 B1     c i 2 B2    = Ai   B j , các trƣờng hợp còn lại đƣợc tính toán tƣơng tự.   - Xét trƣờng hợp V = A0 :   + R0 = a0*| A0 * V | + a1*| A1 * V | + a2*| A2 *V | = a0.      b0*| B0 * V | + b1*| B1 * V | +  b2*| B2 *V | = b0*|c00| + b1*|c01| + b2*|c02|.   + R = A0 * D    - Xét trƣờng hợp V = A0 B0 : Hai khoảng cách trên sẽ không giao nhau nếu:   | V | *C0C1 > | V | *r0 +  (5) Trong đó: R = C0C1* | V | . d   B0 |       a1*| A1 * A0 B0 | + a2*| A2 * A0 B0 |    A0 B0 Mặt khác : = V     A0 (c00 A0 c10 A1 c20 A2 )   c10 A2 c 20 A1 + R0 = a0*| A0 * A0  R0 = a1*|c20| + a2*|c10|  Hình 3. Kết quả chiếu 2 hình hộp lên trục cô lập d  minh họa cho hai trƣờng hợp V = Ai và V  R0 C0 (7) toán các hệ số R0, R1, R ở trên thì ta sẽ làm + R1 = C1 R1 C =  B j }với i, j = 0,1,2. Để tính = { Ai , B j , Ai   c 21 c 22 Nhƣ trong tập các trục cô lập ứng cử viên V  R > R0 + R1 c 20 (6) chính là tích vô hƣớng của hai vector Ai, Bj. Mặt khác, từ B = C*A  A = CT*B  b2*| B2 *V |.  | V | *r1 c11 c12 A2 B0 A2 B1 A2 B2   Từ (6) và (7) suy ra: cij Ai * B j , hay cij   si * bi * Bi ) * V 0  | } Với mọi |V | C0C1 > r0+r1 c10 A2 R1 = b0*| B0 * V | + b1*| B1 * V | +  viết A0 B0 A0 B1 A0 B2  Ai  thể  c 2i A2 với i = A1 * B0 B1 B2 = A1 B0 A1 B1 A1 B2 (4)  c01 c02 A0 Đặt R1 = r1* | V | , tƣơng tự nhƣ trên ta suy ra :  c00  B = C*A 2 r1 = max { | có A = (A0, A1, A2) và B= (B0, B1, B2) C Chú ý rằng, 8 đoạn thẳng này đƣợc nhóm thành 4 cặp đối xứng nhau qua C1. Do vậy, khoảng cách nhỏ nhất chứa 8 đoạng thẳng (4) sẽ có tâm là C1 và bán kính R1 đƣợc xác định nhƣ sau : (  c1i A1 0,1,2.     ( s * b * B ) *V 2  V *D i 0 i i i  |  si * bi * Bi , d ) | |V | |V | i 0  C0 ta  c0i A0  thành: Bi 2  C1  Bi vector Tƣơng tự, ta xác định hình chiếu 8 đỉnh của hộp bao thứ hai lên d với gốc C0 nhƣ sau.  hc(C1 120(06): 161 – 169   + R = V * D = (c10 A2 + = =   c 20 A1 ) * D 163 Đỗ Năng Toàn và Đtg   Tạp chí KHOA HỌC & CÔNG NGHỆ   + R1 = b0*| B0 * V | + b1*| B1 * V | +   b2*| B2 *V |.  Ta có viết lại V dƣới dạng:    V = A0 B0 =     (c00 B0 c01B1 c02 B2 ) B0 =   c01B2 c02 B1       B0 * V = B0 * ( c01B2 c02 B1 ) = 0      B1 * V = B1 * ( c01B2 c02 B1 ) = c02      B2 *V = B2 * ( c01B2 c02 B1 ) = -c01  R1 = b1*|c02|+ b2*|c01| Tiếp tục, ta xây dựng đƣợc bảng các giá trị cho R, R0, R1 nhƣ thể hiện tại bảng 1. Tính toán điểm va chạm giữa hai OBBs Khi có va chạm giữa các OBBs xảy ra, ta sẽ thực hiện việc tìm chính xác điểm va chạm. Đối với hai hộp bao, nếu chúng va chạm với nhau ở dạng đỉnh - đỉnh, đỉnh - cạnh, cạnh cạnh, đỉnh - mặt thì điểm tiếp xúc là duy nhất. Nhƣng nếu chúng va chạm với nhau ở dạng mặt - mặt, cạnh - mặt thì sẽ có vô số điểm tiếp xúc, khi đó chúng ta chỉ cần đƣa ra một điểm bất kỳ là đƣợc. Ý tưởng để tìm thời điểm va chạm như sau: Mỗi khi ta thực hiện công việc kiểm nhanh va chạm ở mức thứ nhất, nếu tìm đƣợc một trục cô lập thì ta sẽ ghi lại nhãn thời gian cho trục cô lập đó. Nếu không tìm đƣợc một trục cô lập nào thì có nghĩa là hai hộp bao đã va chạm với nhau, khi đó nhãn thời gian đƣợc gán cho trục cô lập ở lần kiểm tra liền trƣớc sẽ là thời điểm đầu tiên mà hai hộp bao va chạm nhau, gọi T là nhãn thời gian đó. Khi đó, ta có thế coi nhƣ R = R0+R1(thời điểm hai hình hộp tiếp xúc nhau). Bảng 1. Các giá trị R, R0, R1 164 120(06): 161 – 169 Đỗ Năng Toàn và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ Gọi P là điểm tiếp xúc của hai hộp bao thì suy ra tồn tại một vector x = {x0, x1, x2} và y = {y0, y1, y2} sao cho:  xi * Ai 2  D 2 i 0 bj và i,j = 0,1,2. (8) Việc tìm điểm va chạm sẽ phụ thuộc vào trục cô lập V ở thời điểm T là trục nào trong số 15 trục cô lập ứng cử viên. Ta xét 3 trƣờng hợp sau.    V là vector Ai :Nhân hai vế của (8) với Ai ta thu đƣợc:  2   y j * Ai B j =  Sign( Ai * D )*(R0+R1) +  bj nên ta có: Do vậy, ta chỉ cần chọn một giá trị yj thuộc đoạn trên.   V là vector Bi :Tƣơng tự nhƣ trƣờng hợp trên, ta tính đƣợc. 0 * bi xj 0,1,2.  Nếu cji = 0, nhân hai vế của (6) với Ai ta có: 2  x k * c kj Mặt khác, vì |yj| yi j 0  2 k 0 Nếu cji xi = Ai * D  yj = - B j * D  y j * B j với |xi| ai, |yj| j 0   120(06): 161 – 169 y j * cij * Sign(c ji ) * a j j j 0 = Sign( Ai * D )  xi = *(R0+R1) + Đặt 2 y j * cij . Thay giá trị các R0, R1 tại bảng 1: Tƣơng tự nhƣ trên, ta có: j 0 2 b j * | ci j | ) + xi = *(ai + j 0 cả hai vế với 2 y j * cij Nhân j 0 ta đƣợc. 2 2 b j * | ci j | + (ai- *xi) + j 0 y j * cij = 0 j 0  hợp V 2 | cij | *(b j * Sign(cij ) * y j ) = 0 (9) j 0 Ta thấy: (b j  (ai- *xi) 0 và  B j : Để dễ trình bày, ai * xi bj * Sign(cij ) * y j 0 xi * ai 0 * Sign(cij ) * bj  c01B2 =     A0 B0 = c10 A2 c 20 A1 =  c02 B1 , các trƣờng hợp khác sẽ đƣợc tính tƣơng tự.  B0 ta đƣợc:    x2*c10 - x1*c20 = ( A0 B0 ) * D + 2    y j * B j * ( c01B2 c02 B1 ) j 0    x2*c10 - x1*c20 = ( A0 B0 ) * D + y1*c02  Nhân hai vế (8) với A0 * Sign(cij ) * y j ) 0 Nếu cij yj   V là vector Ai chúng ta sẽ làm minh hoạ cho một trƣờng (ai- *xi) + Khi đó, chọn xj thuộc đoạn sau làm điểm tiếp xúc: 0 y2*c01 j 0,1,2. Nếu cij = 0 (ứng với trƣờng hợp cạnh va chạm mặt, mặt va chạm mặt). Khi đó, nhân hai vế của (8) với B j ta đƣợc: (10) Chú ý rằng, theo hàng 7 trong bảng 1 thì:  | R | | ( A0   B0 ) * D | R0 R1 a1* | c20 | a2 * | c10 | b1* | c02 | b2 * | c01 | 165