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

161

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*

1Việ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

0 1 2 A , A , A

  

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

0

* | | 1, 0,1,2.

i

i i i i C s a A s i



(1)

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.