Luận văn tốt nghiệp Nghiên cứu phát hiện va chạm và ứng dụng
MỤC LỤC
MỞ ĐẦU 3
1.1. Môi trường thực tại ảo (Virtual Reality)....................................................................4
1.2. Tầm quan trọng của việc tìm hiểu phát hiện va chạm trong môi trường thực tại ảo 5
1.3. Một số khái niệm cơ bản.............................................................................................5
1.3.1. Khối bao (Bounding volumes)..........................................................................5
1.3.2. Xây dựng các khối bao cơ sở ...........................................................................9
Chương 2 : 12
CÁC PHƯƠNG PHÁP PHÁT HIỆN VA CHẠM 12
2.1. Phương pháp dùng bao cầu - Bounding Sphere.......................................................12
2.1.1. Phát hiện va chạm............................................................................................12
2.1.2. Xử lý va chạm..................................................................................................17
2.2. Kỹ thuật sử dụng hộp bao phát hiện va chạm..........................................................20
2.2.1. Sự phân tách giữa các OBB.............................................................................21
2.2.2. Kiểm tra sự va chạm giữa các OBB................................................................23
2.2.3. Tìm va chạm giữa 2 OBBs..............................................................................24
2.3. Phương pháp Elipsoid...............................................................................................28
2.3.1. Không gian vector và sự tịnh tiến các vật thể trong không gian....................28
2.3.2. Phát hiện va chạm............................................................................................30
2.3.3. Xử lý va chạm..................................................................................................36
2.4. Phát hiện va chạm giữa các đối tượng cơ sở............................................................42
2.4.1. Phát hiện va chạm giữa hộp bao và tam giác (Box – Triangle)......................42
2.4.2. Phát hiện va chạm giữa 2 tam giác (Triangle-Triangle).................................53
Chương 3: 67
PHẦN THỰC NGHIỆM 67
KẾT LUẬN 68
TÀI LIỆU THAM KHẢO: 69
Trang 1
Luận văn tốt nghiệp Nghiên cứu phát hiện va chạm và ứng dụng
MỞ ĐẦU

thiếu sót. Tôi mong nhận được ý kiến đóng góp của các thầy cô giáo và các đồng nghiệp.
Trang 2
Luận văn tốt nghiệp Nghiên cứu phát hiện va chạm và ứng dụng
Chương 1:
TỔNG QUAN VỀ VA CHẠM
Phát hiện va chạm (Collision detection) là tiến trình giải quyết vấn đề có hay không sự
va chạm giữa các đối tượng trong môi trường mà các đối tượng đó tồn tại. Sự va chạm này
có thể giữa các đối tượng cùng loại hoặc giữa các đối tượng khác nhau, va chạm với các đối
tượng tĩnh (ví dụ như : nền nhà, tường nhà, mặt đường v.v...) hoặc va chạm với các đối
tượng động (ví dụ như : ôtô, máy bay v.v...).
Định nghĩa [collision detection] : Cho một không gian U với một tập các đối tượng O,
giải thuật phát hiện va chạm sẽ cho biết sự va chạm giữa các cặp đối tượng từng đôi một C
p
⊂
O x O x R
3
với mọi đối tượng o
1
,o
2
và cho biết các điểm va chạm giữa chúng
p
1,2

∈
R
3
.
Phát hiện va chạm chỉ là một trường hợp đặc biệt trong môi trường giả lập vật lý (được
thể hiện vào máy tính). Thực chất ở đây chúng ta chỉ tìm hiểu sự va chạm giữa các đối tượng

vào ra có tốc độ cao. Vì vậy mặc dù bắt đầu nghiên cứu từ khá lâu, xong trong một số năm
gần đây thực tại ảo mới có được sự phát triền và mở rộng ứng dụng đáng kể.
Thực tại ảo có rất nhiều ứng dụng trong thực tế như : khoa học quân sự, quốc
phòng, Giáo dục và đào tạo, y học, thiết kế, khoa học cơ bản, thương mại du lịch, giải trí
v.v…
1.2. Tầm quan trọng của việc tìm hiểu phát hiện va chạm trong môi
trường thực tại ảo
Như đã nói ở trên, môi trường thực tại ảo nhằm mô phỏng thế giới thực hoặc thế giới
theo sự tưởng tượng của con người vào máy vi tính. Trong thế giới thực tồn tại rất nhiều các
đối tượng, các đối tượng này có các hành vi của chúng. Chính vì vậy để môi trường thực tại
ảo mô phỏng được thực tế thì các đối tượng trong môi trường này cũng phải có các hành vi
như trong thế giới thực. Chính vì vậy ta cần nghiên cứu các phương pháp để mô phỏng các
hành vi này, mô phỏng sự tương tác giữa các đối tượng trong môi trường thực tại ảo hay nói
khác đi chính là nghiên cứu việc phát hiện va chạm giữa các đối tượng trong môi trường…
1.3. Một số khái niệm cơ bản
Dưới đây là một số khái niệm thường dùng :
1.3.1. Khối bao (Bounding volumes)
Như đã nói ở trên, ta thấy rằng các đối tượng trong thực tế thường có hình dạng rất
phức tạp, nếu ta sử dụng trực tiếp đối tượng đó thì rất khó có thể áp dụng vào thuật toán .
Chính vì vậy ta cần mô phỏng đối tượng đó bằng một đối tượng khác đơn giản hơn, từ đó
sinh ra khái niệm khối bao (bounding volume).
Khối bao (BV) đơn giản chỉ là một khối hình học bao vừa đối tượng cần thao tác. Khối
bao càng bao vừa khít đối tượng thì thuật toán sẽ càng chính xác. Các khối bao nên là các
khối hình học đơn giản.
BV được sử dụng hầu như trong tất cả các cơ chế phát hiện va chạm hiện nay. Phần
lớn các thuật toán phát hiện va chạm đều sử dụng đến chúng bởi vì nó có xu hướng làm
giảm độ phức tạp của thuật toán.
Có rất nhiều loại BV khác nhau, mỗi loại có những điểm mạnh và điểm yếu riêng. Có
thể phân BV thành 2 loại đó là Bounding Box (BB - hộp bao) và Bounding Sphere
(BS - cầu bao). BB thường có 2 loại đó là loại hướng theo trục toạ độ và loại hướng bất kỳ

trường hợp riêng của hình bao ellipsoid.
Tuy nhiên, hình bao cầu lại có rất nhiều nhược điểm. Nó thường biểu diễn không chính
xác hình dạng các vật thể nếu như các vật thể này không có dạng khối cầu, đặc biệt khi hình
dạng của vật thể có dạng dẹt, hoặc dài thì càng không chính xác. Chính vì vậy thuật toán sẽ
không được tối ưu. Khối bao này tạo ra nhiều không gian trống giữa vật thể và khối cầu. Rất
khó hợp nhất 2 hay nhiều BS loại này bởi vì sẽ tạo ra sai số rất lớn.
Hình 1.3.1b2: Hợp nhất và kiểm tra va chạm
giữa 2 Bounding Sphere
Trang 5
Luận văn tốt nghiệp Nghiên cứu phát hiện va chạm và ứng dụng
b. Axis – Oriented Bounding Box
Trong không gian 3 chiều, một axis – oriented bounding box được xác định bởi 6 giá
trị của các đỉnh có toạ độ lớn nhất (x
max
, y
max
, z
max)
và nhỏ nhất (x
min
, y
min
, z
min
). Loại BV này
rất dễ tạo ra , dễ hợp nhất lại với nhau và thuận tiện cho việc phát hiện va chạm. Lợi thế lớn
nhất của loại BV này là xử lý nhanh, tuy nhiên không chính xác cho lắm.
Hình 1.3.1b: Hợp nhất và kiểm tra va chạm
giữa 2 Axis-Oriented Bounding Box
• Hộp bao theo trục toạ độ - AABB (Axis Aligned Bounding Box)

và hộp bao. Tuy nhiên việc tao ra hộp bao dạng này đôi khi quá phức tạp
(phức tạp nhất) và việc thao tác trên chúng mất quá nhiều công đoạn. Nó chỉ được sử dụng
đối với các chương trình cần độ chính xác cao. Đối với các chương trình nhỏ yêu cầu tốc độ
thì không nên chọn hộp bao dạng này.
Thông thường, người ta thường giới hạn số mặt hay số cạnh của đa diện tới một giá trị
nào đó (chẳng hạn k = 5,6,7 ...) tuỳ thuộc vào từng ứng dụng cụ thể.
Theo trên ta thấy rằng để giảm khoảng không gian trống thì hộp bao tạo ra và sử dụng
càng trở nên phức tạp (xem biểu đồ).
Hình 1.3.1c1: Độ phức tạp trong tính toán
đối với các hộp bao
Tiếp theo ta sẽ tìm cách xây dựng các hộp bao trên (tạm gọi chung là hộp bao) để có
thể dùng được trong các thuật toán sẽ được sử dụng:
Trang 7
Luận văn tốt nghiệp Nghiên cứu phát hiện va chạm và ứng dụng
1.3.2. Xây dựng các khối bao cơ sở
a. Xây dựng hộp bao AABB:
Xây dựng hộp bao loại này khá đơn giản, hộp bao
này được tạo bởi 2 điểm có toạ độ nhỏ nhất và lớn nhất của
vật thể như hình vẽ 1.3.2a:
Hình 1.3.2a: Hộp bao AABB
b. Xây dựng hộp bao có hướng OBB
Việc xây dựng hộp bao OBB có vẻ phức tạp hơn nhiều so với xây dựng hộp bao
AABB. Trước hết ta tìm đa diện lồi bao vật thể (bằng cách mở rộng các mặt phẳng trên vật
thể). tiếp theo ta phân chia các mặt của đa diện thành các tam giác.
Giả sử sau bước này ta được n tam giác với các định lần lượt là : p
k
, q
k
, r
k

0
1
n
k
kk
H
H
ma
a
m
Sử dụng công thức trên ta được một ma trận C để từ đó xác định được vector định
hướng cho 8 cạnh của OBB là:
[ ]
( )






−








+++==

nêu trên:
- Lấy tâm của khối cầu là tâm của hộp bao AABB
- Duyệt tất cả các đỉnh của đối tượng
- Tìm đỉnh mà khoảng cách từ tâm khối cầu đến đó là lớn nhất
và lấy khoảng cách đó làm bán kính của hình cầu
Trang 8
Luận văn tốt nghiệp Nghiên cứu phát hiện va chạm và ứng dụng
Với phương pháp này thì hạn chế được khoảng không gian trống hơn phương pháp
trên, tuy nhiên cần phải thực hiện nhiều phép toán so sánh và tìm kiếm.
Qua 2 phương pháp xây dựng nhanh BS ở trên ta thấy rằng giải pháp trên là không
phải tối ưu. Rõ ràng cả 2 phương pháp đều tạo ra những khoảng không gian trống quá lớn.
Chúng ta cần tìm ra giải pháp hạn chế được khoảng không gian trống càng nhiều càng tốt.
Giải pháp tối ưu nhất được trình bày như sau:
Giả sử S là một tập các đỉnh của một đối tượng (hay đơn giản S là tập các điểm). Với
tất cả các đỉnh V thuộc tập S ta thực hiện các bước sau:
Bước 1 : Tìm tất cả các đỉnh V
max
là đỉnh có toạ độ lớn nhất theo các trục toạ độ (x,y,z)
Bước 2 : Tìm tất cả các đinh V
min
là đỉnh có toạ độ nhỏ nhất theo các trục toạ độ (x,y,z)
Bước 3 : Chọn ra cặp đỉnh V
min
, V
max
sao cho khoảng cách giữa chúng theo các trục toạ độ là
lớn nhất.
Bước 4 : Chọn tâm C của khối cầu là trung điểm của vector V
max
- V

). Với N nhỏ thì công việc này là khá dễ dàng, nhưng với N lớn thì chi phí để
thực hiện nó sẽ là rất cao.
Vấn đề tiếp theo cũng rất quan trọng đó là vấn để giải quyết sau va chạm hay phản ứng
lại va chạm (Collision response). Để giải quyết vấn đề này chúng ta thường sử dụng các khái
niệm về động học như momen hay lực tác dụng, tức là chúng ta cần tính toán đến các đại
lượng vật lý (như: khối lượng, vận tốc ...). Ở đây, để vấn đề trở nên đơn giản hơn thì đôi khi
ta chỉ giải quyết các va chạm mang tính chất đàn hồi (2 vật không “dính” vào nhau sau va
chạm).
2.1. Phương pháp dùng bao cầu - Bounding Sphere
Trong phần này ta sẽ lần lượt xét một số thuật toán phát hiện va chạm, đồng thời giải
quyết thêm vấn đề sau va chạm. Ta sẽ sử dụng các khối bao thay cho các đối tượng cần thể
hiện.Từ những thuật toán riêng cho từng đối tượng ta sẽ đi đến một thuật toán chung cho tất
cả các đối tượng.
2.1.1. Phát hiện va chạm
Phát hiện có va chạm
 Khối cầu - Mặt phẳng
 Khối cầu - Khối trụ
 Khối cầu - Khối cầu
Sử dụng các định luật vật lý để phản hồi sau va chạm
 Lực tác dụng trở lại đối tượng khi va chạm
 Sử dụng trọng lực trong việc di chuyển đối tượng
a. Tìm giao điểm giữa một tia với mặt phẳng
Để phát hiện va chạm chúng ta sử dụng một thuật toán đơn giản tạm gọi là lần theo tia
(ray tracing). Trước hết ta sẽ định nghĩa thế nào là một tia. Một tia được xác định bởi một
Trang 11
Luận văn tốt nghiệp Nghiên cứu phát hiện va chạm và ứng dụng
điểm hay còn gọi là gốc và một vector xác định hướng mà tia đó sẽ đi theo. Nói tóm lại, một
tia có thể được biếu diễn bởi một điểm gốc và vector định hướng.
Phương trình của một tia có dạng:
PointOnRay = RayStart + t * Raydirection (1)

định được mặt phẳng (xOz).
Như vậy, một điểm và một vector pháp tuyến là đủ để định nghĩa một mặt phẳng. Sử
dụng phương trình Vector của mặt phẳng thì pháp tuyến là Xn và điểm 3D
(cũng là gốc của vector) là X. Chỉ có một giá trị cần phải chú ý là d (giá trị này cũng có thể
tính được từ phương trình vector)
Chú ý: Phương trình Vector trên hoàn toàn tương đương với phương trình mà ta
thường dung là Ax + By + Cz + D = 0. Ở đây, ta chỉ cần thay Xn = (A,B,C) và X = (x,y,z)
thì 2 phương trinh hoàn toàn tương đương.
Tổng kết ta có được 2 phương trình:
PointOnRay = RayStart + t * Raydirection (1)
Xn dot X = d (2)
Nếu tia giao với đường thẳng tại điểm nào đó thì điểm đó thì điểm đó thoả mãn cả 2
phương trinh (1) và (2). Vậy từ (1), (2):
Xn dot PointOnRay = d
Trang 12
Luận văn tốt nghiệp Nghiên cứu phát hiện va chạm và ứng dụng
hay:
(Xn dot RayStart)+ t * (Xn dot Raydirection) = d
Giải phương trình với ẩn t ta có :
onRaydirectidot Xn
RayStartdot Xn -d
t
=
Thay d vào ta được :
onRaydirectidot Xn
RayStartdot Xn NEPointOnPLAdot Xn
t
−
=
Cuối cùng:

b. Tìm giao điểm giữa 2 khối cầu:
Một khối cầu được xác định bởi tâm và bán kính của nó. Giải quyết vấn đề va chạm
giữa 2 khối cầu có vẻ đơn giản hơn. Bằng cách tính khoảng cách giữa 2 tâm của khối cầu,
Trang 13
Luận văn tốt nghiệp Nghiên cứu phát hiện va chạm và ứng dụng
nếu khoảng cách này nhỏ hơn hoặc bằng tổng của 2 bán kính của 2 khối cầu thì 2 khối cầu
giao nhau.
Nhưng vấn đề lại không chỉ có vậy, ta hay xem hình dưới:
Rõ ràng là theo hướng chuyển động của 2 quả bóng trên (ball 1 và ball 2) thì chắc chắn
là 2 quả bóng đó sẽ va chạm với nhau. Nhưng thực tế thì chưa chắc như vậy là bởi vì ở đây
chúng ta quên mất yếu tố thời gian. Gọi C là giao điểm của r1 với r2 (ở đây chưa nói C là
điểm giao của ball 1 với ball 2). Nếu xét đến yếu tố thời gian thì tại thời điểm t1 quả bóng
ball 1 chuyển động qua điểm C, tại thời điểm t2 quả bóng ball 2 chuyển động qua điểm C.
Ta hoàn toàn có thể cho rằng t1 khác t2 và như vậy thì ball 1 không va chạm với ball 2. Đó
chính là vấn đề chính ta cần giải quyết.
Các phương trình ở trên chỉ giải quyết được giao điểm khi chưa xét đến vấn đề thời
gian. Đối với các đối tượng có hình dạng phức tạp hoặc khi không thể thiết lập được phương
trình cụ thể để tìm giao điểm hoặc khi phương trình trở nên quá phức tạp không thể giải
được thì tất nhiên là chúng ta phải sử dụng đến những phương thức khác.
Các thông số cần thiết để tính toán giao điểm của 2 khối cầu đó là : điểm đầu, điểm cuối,
thời gian, vận tốc (bao gồm hướng và tốc độ) của khối cầu. Để tính được điểm giao thì thời
gian (time step) lại được chia thành các khoảng nhỏ hơn và chúng ta sẽ thực hiện việc di
chuyển khối cầu trong mỗi khoảng thời gian đó bằng cách sử dụng đại lượng vận tốc và
kiểm tra sự giao nhau trong mỗi khoảng thời gian đó. Khi có bất cứ giao điểm nào được tìm
thấy (cũng có nghĩa là khối cầu này sẽ “xuyên” một phần của nó vào khối cầu khác), chúng
ta sẽ lấy vị trí của khối cầu ngay trước khi khối cầu đó “xuyên” vào khối cầu khác làm vị trí
giao điểm.
Rõ ràng là chúng ta không muốn 2 khối cầu xuyên vào nhau như hình trên. Do vậy
chúng ta phải lấy vị trí của khối cầu ngay trước khi chúng xuyên vào nhau làm vị trí giao
điểm. Khoảng chia thời gian (time step) càng nhỏ thì độ chính xác càng cao.

BallNr1 = i ;
BallNr2 = j ;
break;
}
}
}
}
if (Timedummy != 10000)
{
Timepoint = Timedummy ;
return 1;
}
return 0;
}
Vấn đề tiếp theo chúng ta phải giải quyết đó là sẽ xảy ra va chạm trong khoảng giữa
mỗi khoảng thời gian (Timestep) mà ta xét. TimeStep chính là mỗi khoảng thời gian ta thực
hiện di chuyển khối cầu từ vị trí hiệnt tại dọc theo hướng của vector vận tốc. Vì chúng ta
kiểm tra khối cầu di chuyển trên một tia vô hạn nên luôn có khả năng điểm xảy ra va chạm
nằm sau vị trí mới của khối cầu đó. Để giải quyết vấn đề này chúng ta sẽ di chuyển khối cầu,
tính toán vị trí mới và tìm khoảng cách giữa điểm đầu và điểm cuối. Từ thủ tục tìm va chạm
chúng ta sẽ nhận được khoảng cách từ điểm bắt đầu tời điểm va chạm. Nếu khoảng cách này
nhỏ hơn khoảng cách từ điểm bắ đầu đến điểm cuối thì sẽ có một va chạm. Để tính toán
chính xác thời gian xảy ra va chạm chúng ta chỉ cần giải một phương trình đơn giản sau.
Đặt:
 Dst = khoảng cách giữa điểm bắt đầu và điểm kết thúc.
 Dsc = khoảng cách từ điểm bắt đầu và điểm xảy ra va chạm
 T = TimeStep.
Vậy thời gian xảy ra va chạm (Tc) sẽ là:
Tc = Dsc * T / Dst
Trang 15

Vector R cho chúng ta biết hướng chuyển động mới hay tia phản xạ nhưng để sử dụng được
như vector vận tốc thì nó cần có thêm yếu tố về tốc độ, tức là độ lớn của vận tốc. Muốn vậy
ta chỉ cần nhân R với độ lớn của vận tốc chính là độ lớn của tia gốc, từ đó sẽ cho ta chính
xác vector vận tốc.
Đoạn mã sau sẽ thực hiện tính góc phản xạ:
rt2=ArrayVel[BallNr].mag(); //Tìm độ lớn của vận tốc
ArrayVel[BallNr].unit(); // Chuẩn hoá
//Tính toán sự phản xạ
ArrayVel[BallNr]=TVector::unit((normal*(2*normal.dot(-ArrayVel[BallNr]))) +
ArrayVel[BallNr]);
ArrayVel[BallNr]=ArrayVel[BallNr]*rt2;
Trang 16
Luận văn tốt nghiệp Nghiên cứu phát hiện va chạm và ứng dụng
b. Va chạm với đối tượng đang chuyển động (Đối tượng động)
Ta xét trường hợp 2 khối cầu đang chuyển động va chạm với nhau. Trường hợp này có
lẽ phức tạp hơn nhiều so với trường hợp va chạm với các đối tượng tĩnh.
H ình 2.1.2b: Va chạm giữa 2 đối tượng động
Giả sử 2 khối cầu có Vector vận tốc ngày trước thời điểm va chạm là U
1
và U
2
(hình
vẽ). Ta sẽ phân tích các vector vận tốc U
1
, U
2
thành các vector thành phần tại thời điểm xảy
ra va chạm. X_Axis là Vector nối tâm của 2 khối cầu.
 U
1x

1y
, V
2x
, V
2y
là các hình chiếu tương ứng của V
1
, V
2
lên trục X_Axis và
trục vuông góc với X_Axis.
Ta sẽ đi tìm từng thành phần nêu trên:
a. Tìm X_Axis:
X_Axis = (Center2 – Center1)
Chuẩn hoá X_Axis => X_Axis.unit()
b. Tìm các hình chiếu
U
1x
= X_Axis * (X_Axis dot U
1
)
U
1y
= U
1
- U
1x
U
2x
= -X_Axis * (-X_Axis dot U

=
+
∗−−∗+∗
=
Để cho bài toán đơn giản hơn ta giả sử M
1
= M
2
= 1
Trang 17
Luận văn tốt nghiệp Nghiên cứu phát hiện va chạm và ứng dụng
d. Tìm các thành phần vận tốc cuối cùng
V
1y
= U
1y
V
2y
= U
2y
V
1
= V
1x
+ V
1y
V
2
= V
2x

Để mô phỏng sự chuyển động và va chạm giống với thực tế thì chỉ xác định được điểm
va chạm và phản hồi va chạm là chưa đủ, mà ta còn phải sử dụng thêm yếu tố đó là trọng
lực. Sử dụng phương trình Eule, tại mỗi bước (TimeStep) vị trí và vận tốc của các đối tượng
tham gia chuyển động được tính toán lại như sau:
Velocity_New = Velocity_Old + Acceleration * TimeStep hay v = v
o
+ a.t
Position_New = Position_Old + Velocity_New * TimeStep hay x = x
o
+ v.t
Trang 18
Luận văn tốt nghiệp Nghiên cứu phát hiện va chạm và ứng dụng
Như vậy, các đối tượng sẽ di chuyển và được kiểm tra va chạm với vận tốc mới này.
Gia tốc (acceleration : a) của từng đối tượng được xác định bởi phương trình sau:
Force = mass * acceleration hay F= m.a
Trong trường hợp của chúng ta thì lực F chỉ là trọng lực (các trường hợp khác hoàn
toàn tương tự). Gia tốc ở đây cũng được biểu diễn dưới dạng Vector.
2.2. Kỹ thuật sử dụng hộp bao phát hiện va chạm
Để kiểm tra 2 hộp bao có va chạm với nhau hay không ta sử dụng định lý sau: 2 đối
tượng lồi sẽ không giao nhau khi và chỉ khi tồn tại mặt phẳng P cô lập được chúng.
Trong không gian 3 chiêu R
3
, nếu 2 hộp bao giao nhau thì hình chiếu của chúng trên các
trục toạ độ x, y và z cũng phải giao nhau.
Thuật toán tổng quát có thể phát biểu ngắn gọn như sau:
 Chiếu mỗi hộp bao (AABB) lên các trục toạ độ x, y và z. Kết quả thu được là
các đoạn thẳng.
 Hoặc có thể chiếu mỗi hộp bao (AABB) lên các mặt phẳng toạ độ xOy, yOz và
zOx. Kết quả thu được là các hình chữ nhật.
 Kiểm tra sự giao nhau giữa các đoạn thẳng được chiếu lên các trục toạ độ. Nếu


∀≤+
∑
=
iaxAxC
ii
i
ii
___:
2
0

và 8 đỉnh của hộp là:
Trang 19
Luận văn tốt nghiệp Nghiên cứu phát hiện va chạm và ứng dụng
∑
=
+
2
0i
iii
AaC

σ
trong đó:
1
=
i
σ
với mọi i.

. Các trục phân tách 2 hộp bao có thể
có dạng sau
LsC


+
0
trong đó
L

là một trong các thành phần
ji
BA


,
hoặc
ji
BxA


với
i=0,1,2 và j = 0,1,2.
Hình chiếu của một điểm
P

lên đường
LsC






.
.
0
−
Khoảng cách hình chiếu các đỉnh của OBB thứ nhất liên hệ với đường gốc
0
C

theo hệ
thức:
∑∑
==
=






+
2
0
2
0
0
.
.

0
∑
=
Khoảng cách hình chiếu của các đỉnh của OBB thứ hai liên hệ với đường gốc
0
C

theo
hệ thức:
∑∑
==
+=






+
2
0
2
0
0
.
.
.
.
Pr
i

( )
LL
BLBLSignb
r
i
iii


.
..
2
0
1
∑
=
=
Hai khoảng chiếu sẽ không giao nhau khi và chỉ khi khoảng cách giữa các tâm lớn hơn
tổng của các bán kính: |K
1
- K
0
| > r
0
+ r
1
. Mỗi đại lượng ở 2 vế có cùng mẫu số
LL

.
. Do đó

i
i
ii
ALALSignaR




..
2
0
0
∑
=
=
( )
i
i
ii
BLBLSignbR

..
2
0
1
∑
=
=
(1)
 điều kiện không giao nhau là R > R0 + R1.

Cũng như vậy các trục của OBB thứ nhất có thể viết dưới dạng tổ hợp các trục của OBB
thứ hai:
2211
BcBcBcA
iioioi


++=
với i = 0, 1, 2.
Kiểm tra điều kiện không giao nhau gồm tích vô hướng của các bộ ba sau:
( )
jiojii
ciiSignBxAA
210
1
,.
=


( )
2
011
,.
j
ijijo
cjjSignBxAB
=




1
và R và kiểm tra điều kiện không giao nhau bằng cách so
sánh R>R
o
+R
1
.
b. Đối tượng động - vận tốc không đổi
Việc phát hiện giao nhau như các OBBs cần phải được sửa đổi đôi chút để có thể nắm
được sự va chạm khi các OBBs có các thành phần vận tốc (giả sử là vận tốc không đổi). Nếu
coi OBB thư nhất là đối tượng tĩnh thì vận tốc của OBB thư hai phải trừ đi vận tốc của OBB
thứ nhất.
Nếu vận tốc của các OBB lần lượt là
o
V

và
1
V

, đặt
o
VVW

+=
1
. Gọi thời gian ban
đầu và kết thúc quá trình là t = 0 và t = T. Đặt
W)(
01

0
+ R
1
, R(T)>R
0
+R
1
và
).().(
10
DLSignDLSign

=
.
Trang 22
Luận văn tốt nghiệp Nghiên cứu phát hiện va chạm và ứng dụng
Ý tướng của vấn đề là chỉ ra rằng |p + tw| > r > 0.
if(p > r)
{
if(p + T*w > r)
return no_intersection;
}
else if(p < -r)
{
if(p + T*w < -r)
return no_intersection;
}
Nếu như có bất cứ một trục phân tách nào trong 15 trục có thể phân tách được 2 OBB
trong toàn bộ khoảng thời gian thì sẽ không có va chạm xảy ra. Tuy nhiên, nếu không có trục
nào trong 15 trục phân tách 2 OBB trong khoảng thời gian trên thì vẫn có khả năng không có



=
i
β
với 0 ≤ i ≤ 2
Bảng 1': bảng các giá trị của R, R
o
, R
1
để kiểm tra điều kiện không giao nhau theo hướng
chuyển động của 2 OBB: R > R
0
+ R
1
2.2.3. Tìm va chạm giữa 2 OBBs
Kiểm tra sự giao nhau của các OBB dùng toán tử boolean. Thuật toán trả về giá trị true
nếu có sự giao nhau xảy ra và false trong trường hợp ngược lại. Không có thông tin thêm
nào được cung cấp về vị trí xảy ra va chạm (có thể va chạm ở nhiều điểm).
Trong trường hợp va chạm giữa các đối tượng tĩnh, vùng va chạm có thể được tính toán
hơi khó. Đây là lĩnh vực tính toán của các đối tượng cứng. Đối với hệ thống động, các đối
tượng chuyển động thì phải khởi tạo ban đầu không giao nhau và kiểm tra giao nhau trong
suốt khoảng thời gian được chỉ định. Những trường hợp giao nhau sau có thể cho ra một
điểm va chạm (nếu có): đỉnh - đỉnh, đỉnh - cạnh, đỉnh - mặt, cạnh - cạnh (không song song
hoặc trùng nhau !) khi đó giao điểm là duy nhất. Trong trường hợp mặt - mặt hoặc cạnh -
cạnh thì điểm giao không phải là duy nhất. Ta cần cung cấp thông tin về một trong những
điểm va chạm.
Trang 23
Luận văn tốt nghiệp Nghiên cứu phát hiện va chạm và ứng dụng
a. Tìm lần va chạm đầu tiên




+−+=
, |x
i
| ≤ a
i
với i = 0,1,2, |y
j
| ≤ b
j
với j = 0,1,2.
 Trục
i
A

:
Nếu trục phân tách ở thời điểm T là
i
A

thì sự giao nhau phải xảy ra trên một trong 2
mặt vuông góc với
i
A

.
Nhân vô hướng 2 vế của phương trình (3) với
i

, R
0
]
Nếu
0.
>
DA
i


thì
)(.
10
RRDA
i
+−=


,2 khoảng giao nhau ở điểm phía trái của [-R
0
, R
0
]
Do đó,
)(.
10
RRDA
i
+=
σ

2
0
10
..0
)(
j
iijijjij
j
jij
j j
ijjijiji
xaycSignbc
yccbaycRRx
σσ
σσ
(4)
Trong đó,
jj
by
≤
và
1)(.
≤
ij
cSign
σ
;
Vậy,
0)(.
≥+

B

ta được :
∑
=
+−=
2
0
.
k
kjkjj
cxDBy

Từ |x
k
| ≤ a
k
ta được:
∑∑
==
=+−≤≤−−=
2
0
2
0
)max(....)min(
k
jkkjjjk
k
kjjj

) thì y
j
= b
j
là một điểm giao.
Nếu –b
j
≥ min(y
j
) thì y
j
= -b
j
là một điểm giao,
Ngược lại, ta sẽ chọn y
j
= min(y
j
) như một điểm giao.
 Trục
j
B

:
Nếu trục phân tách ở thời điểm T là
i
B

thì sự giao nhau phải xảy ra ở trên một trong 2 mặt
vuông góc với

, hơn nữa:
( )
( )( )
( )
00
2
0
10
2
0
...0
..
ybxcSignac
ybcayRRxc
jjij
j
ji
iiijji
j
jij
σσ
σσ
++−=
+







yb
σ
, trong trường hợp
ii
by .
σ
−=
.
Nếu mọi c
ji
=0 thì tổng ở phương trình trên không phụ thuộc vài x
i
. Chẳng hạn, điều này xảy
ra khi giao nhau ở trường hợp cạnh - mặt hoặc mặt - mặt.
Ta lại nhân 2 vế của phương trình (3) với
A

được:
jk
k
kjj
cyDAx
∑
=
+=
2
0
.



[ ] [ ]
jjjjj
aaxxx ,)max(),min(
−∩∈
Sự giao nhau chỉ xảy ra khi : min(x
j
) ≤ a
j
và –a
j
≤ max(x
j
).
Nếu –a
j
≥ min(x
j
) thì x
j
= -a
j
là một điểm giao.
Nếu a
j
≤ max(x
j
) thì x
j
= a
j