PHÁT HIỆN VÀ XỬ LÝ VA CHẠM TRONG CÁC HỆ THỐNG THỰC TẠI ẢO VÀ
ỨNG DỤNG VÀO BÀI TOÁN “AN TOÀN GIAO THÔNG” LUẬN VĂN THẠC SỸ
Hà nội, 2006 ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Phạm Thế Anh PHÁT HIỆN VÀ XỬ LÝ VA CHẠM TRONG CÁC HỆ THỐNG THỰC TẠI
ẢO VÀ ỨNG DỤNG VÀO BÀI TOÁN “AN TOÀN GIAO THÔNG” Ngành: Công nghệ thông tin
Mã số: 1.01.10
5
1.2 Ba đặc tính chính của VR ………………………………………………
6
1.3 Các thành phần một hệ thống VR ……………………………………….…
9
1.4 Ứng dụng của Thực tại ảo …………………………………………………
11
1.5 Các công cụ phát triển ứng dụng Thực tại ảo ………………… …………
12
1.5.1 Các phần mềm xây dựng mô hình ……………………………… …
12
1.5.2 Các công cụ lập trình ………………………………………………
14
Chương 2. Các phương pháp phát hiện va chạm
16
2.1 Kĩ thuật phát hiện va chạm dựa vào hộp bao AABB ……………………
17
2.1.1 Định nghĩa hộp bao AABB ………………………………………….
17
2.1.2 Phát hiện va chạm giữa hai AABB ………………………………….
17
2.2 Kỹ thuật hộp bao theo hướng (Oriented Bounding Boxes) ……………….
18
2.2.1 Định nghĩa hộp bao theo hướng (OBB) ……………………………
18
2.2.2 Kiểm tra nhanh va chạm giữa hai hộp bao OBBs …………………
19
2.2.3 Tìm điểm va chạm …………………………………………………
24
2.2.4 Phát hiện va chạm khi các đối tượng di chuyển ……………………
47
3.2. Xử lý các hiệu ứng về méo mó, biến dạng sau va chạm ………………….
48
3.2.1 Ý tưởng thuật toán
48
3.2.2. Giới thiệu về hàm Open Uniform B-Splines ………………………
49
3.2.2.1 Vector nút của đường cong Open, Uniform B-Splines ………
49
3.2.2.2 Định nghĩa đường cong Open, Uniform B-Splines 1D …….…
49
3.2.2.3 Định nghĩa đường cong Open, Uniform B-Splines 2D ………
50
3.2.2.4 Định nghĩa đường cong Open Uniform B-Splines 3D ………
52
Chương 4. Ứng dụng vào bài toán "Tuyên truyền an toàn giao thông”
53
4.1 Giới thiệu bài toán “Tuyên truyền an toàn giao thông” ……………………
53
4.2 Xây dựng hệ thống mô phỏng các tình huống giao thông …………………
54
4.3 Các kết quả đạt được ………………………………………………………
55
Kết luận
58
Tài liệu tham khảo
59
3
MỞ ĐẦU
4
Vấn đề về va chạm thường là những vấn đề rất khó nghiên cứu trong thực tế,
chẳng hạn như các công ty sản xuất xe máy, xe ô tô trước khi tung các sản phẩm ra
thị trường đều phải tiến hành các cuộc thử nghiệm về va chạm để kiểm tra tính bền
và tính an toàn của các sản phẩm làm ra. Những vấn đề này đã được nghiên cứu thử
nghiệm trong thực tế nhưng còn rất nhiều hạn chế vì nhiều lý do, còn rất nhiều
trường hợp va chạm mà chúng ta cần nghiên cứu nhưng chưa thể thực hiện được.
Một vấn đề khác đó chính là chi phí cung cấp cho việc thử nghiệm trên thực tế là
quá lớn. Chính vì vậy giải pháp sử dụng máy tính để mô phỏng các vụ va chạm là
một giải pháp thay thế rất thích hợp, đây là một vấn đề hết sức cần thiết cho cuộc
sống của con người. Vấn đề phát hiện va chạm còn được ứng dụng rất nhiều trong
các lĩnh vực khác như: y học, các bộ mô phỏng vật lý hay trong một lĩnh vực có nhu
cầu rất lớn đó là giải trí v.v Phát hiện va chạm được ứng dụng rất nhiều trong các
môi trường thực tại ảo.
Phát hiện va chạm đã khó, xử lý hậu va chạm còn khó hơn. Chúng ta không
chỉ đơn thuần là phát hiện ra va chạm, quan trọng hơn chúng ta cần phải xử lý hay
mô phỏng hành vi của các đối tượng sau va chạm như thế nào cho giống với thế
giới thực, chẳng hạn hai xe máy đâm nhau thì hậu quả sẽ như thế nào? Chúng bị
méo mó, biến dạng, bị thay đổi trạng thái (vận tốc và hướng) ra sao? Hoặc hậu quả
xảy ra khi ô tô đâm vào xe máy thì như thế nào? Đối tượng khi di chuyển trên địa
hình không bằng phẳng phải khác khi di chuyển trên địa hình bằng phẳng Vì
những khó khăn trên, phát hiện va chạm và xử lý hậu va chạm là hai vấn đề quan
trọng trong các hệ thống thực tại ảo.
Trong luận văn này, tôi tìm hiểu và nghiên cứu các vấn đề về phát hiện và xử
lý hậu va chạm trong các hệ thống thực tại ảo. Trong phát hiện va chạm, tôi tập
trung nghiên cứu hai kĩ thuật chính đó là kĩ thuật sử dụng hình hộp bao theo trục
(Axis-Aligned Bounding Boxes - AABBs) và kĩ thuật hình hộp bao theo hướng
(Oriented Bounding Boxes - OBBs). Khi xử lý hậu va chạm, tôi nghiên cứu các cơ
sở vật lý về động lực học vật rắn [16] (Open Dynamic Engine - ODE), kĩ thuật
"thật" hơn nữa nhờ tác động lên tất cả các kênh cảm giác của con người. Trong thực
tế, người dùng không những nhìn thấy đối tượng đồ họa 3D nổi (như hình nổi ở
trang cuối báo Hoa học trò đã đăng trước kia), điều khiển (xoay, di chuyển, ) được
đối tượng trên màn hình (như trong game), mà còn sờ và cảm thấy chúng như có
thật. Ngoài khả năng nhìn (thị giác), nghe (thính giác), sờ (xúc giác), các nhà nghiên
cứu cũng đã nghiên cứu để tạo các cảm giác khác như ngửi (khứu giác), nếm (vị
giác). Tuy nhiên hiện nay trong Thực tại ảo các cảm giác này ít được sử dụng đến. 6
Từ các phân tích trên, chúng ta có thể thấy định nghĩa sau đây của C. Burdea
và P. Coiffet về Thực tại ảo là tương đối chính xác: VR - Thực tại ảo là một hệ
thống giao diện cấp cao giữa Người sử dụng và Máy tính. Hệ thống này mô phỏng
các sự vật và hiện tượng theo thời gian thực và tương tác với người sử dụng qua
tổng hợp các kênh cảm giác. Đó là ngũ giác gồm: thị giác, thính giác, xúc giác,
khứu giác, vị giác [4].
1.2 Ba đặc tính chính của VR
Như một nguyên tắc chủ đạo, một hệ thống thực tại ảo phải có ba đặc tính
sau: tính tương tác (interactive), tính đắm chìm (immersion) và tính tưởng tượng
(imagination) như trong hình 1.1.
Sự đắm chìm
Giá trị của sự đắm chìm (immersion) là gì? Một hiệu ứng hết sức mạnh mẽ
của nó là khả năng tập trung sự chú ý của bạn. Người ta hay nói rằng người ta đang
đắm chìm vào công việc. Sự đắm chìm có nghĩa là ngăn chặn sự xao nhãng và tập
việc loại bỏ phần còn lại của thế giới và nhấn chìm chính mình vào cái không gian
biệt lập ấy, sự học hỏi có thể diễn ra và làm biến đổi một đứa trẻ thành một người
trưởng thành.
Tính tương tác
Tính tương tác cũng như sự đắm chìm là một phương diện then chốt của
Thực tại ảo. Có hai khía cạnh độc nhất của tính tương tác trong một thế giới ảo đó là
sự điều hướng bên trong thế giới và động lực học của môi trường. Sự điều hướng
(navigation) chỉ đơn giản là khả năng của người dùng để di chuyển khắp nơi một
cách độc lập, cứ như là đang ở bên trong một môi trường thật. Nhà phát triển phần
mềm có thể thiết lập những áp đặt đối với việc truy cập vào những khu vực ảo nhất
định, cho phép có được nhiều mức độ tự do khác nhau.
Hình 1.2 Tính tương tác của một hệ thống Thực tại ảo
8
Một khía cạnh khác của sự điều hướng là sự định vị điểm nhìn của người
dùng. Sự kiểm soát điểm nhìn chắc hẳn có nghĩa là việc theo dõi chính bạn từ một
khoảng cách, việc quan sát cảnh tượng thông qua đôi mắt của một con người khác,
hoặc di chuyển khắp trong thiết kế của một cao ốc mới như thể đang ngồi trong một
chiếc ghế đẩy… Động lực học của môi trường là những quy tắc về cách thức mà nội
dung của nó (người, vật, … và mọi thứ) tương tác với nhau trong một trật tự để trao
đổi năng lượng hoặc thông tin. Mỗi một đối tượng (object) và mối quan hệ của nó
với mọi đối tượng khác (kể cả với người dùng) là một yếu tố thiết kế trong sự suy
xét cẩn thận của nhà phát triển.
Trong số những yếu tố đó có thể kể đến vị trí, màu sắc, hình dạng và kích
thước của môi trường. Kết quả là, Thực tại ảo là trải nghiệm của trạng thái sống
trong một thế giới khác - một thế giới được cai quản bởi những luật lệ chọn lọc, và
được ngụ cư bởi những đối tượng với bất kỳ thuộc tính nào mà nhà sáng tạo chọn
lựa để ấn định cho chúng. Chính tính chất linh động này trong việc sáng tạo là biểu
trưng các môi trường ảo đã tạo nên tình trạng kích động về thực tại ảo. Phim ảnh 3D
feedback như găng tay, ) để tạo xúc giác khi sờ, nắm đối tượng. Bộ phản hồi
xung lực (Force Feedback) để tạo lực tác động như khi đạp xe, đi đường xóc,
10
Phần mềm của một hệ thống Thực tại ảo.
Phần mềm luôn là linh hồn của Thực tại ảo cũng như đối với bất cứ một hệ
thống máy tính hiện đại nào. Về mặt nguyên tắc có thể dùng bất cứ ngôn ngữ lập
trình hay phần mềm đồ họa nào để mô hình hóa (modelling) và mô phỏng
(simulation) các đối tượng của VR. Ví dụ như các ngôn ngữ (có thể tìm miễn phí)
OpenGL, C++, Java3D, VRML, X3D, hay các phần mềm thương mại như
WorldToolKit, PeopleShop,
Phần mềm của bất kỳ Thực tại ảo nào cũng phải bảo đảm hai công dụng
chính: Tạo hình vào Mô phỏng. Các đối tượng của Thực tại ảo được mô hình hóa
nhờ chính phần mềm này hay chuyển sang từ các mô hình 3D (thiết kế nhờ các
phần mềm CAD khác như AutoCAD, 3D Studio, ). Sau đó phần mềm Thực tại ảo
phải có khả năng mô phỏng động học, động lực học và mô phỏng ứng xử của đối
tượng.
Nói chung các hệ thống thực tại ảo phải xử lý mội khối lượng lớn thông tin
(đa phần là các thông tin của các đối tượng 3D do đó tốn bộ nhớ và đòi hỏi thời gian
xử lý là thời gian thực), vì thế nó đòi hỏi một lượng tài nguyên bộ nhớ RAM lớn và
bộ xử lý cùng các thiết bị vào ra có tốc độ cao. Vì vậy mặc dù bắt đầu nghiên cứu từ
động như ở trong thế giới thực. Người hoạ sĩ được máy tính tạo cho cảm giác y như
đang làm việc ngoài đời thực vì các công cụ khung vẽ, giá vẽ, bảng pha màu, các
hiệu ứng ba chiều như ánh sáng, độ tương phản đều được cung cấp trên màn hình
máy tính, điều này có thể làm họ cảm thấy thuận tiện và dễ thao tác.
Trong xây dựng, việc dựng được các mô hình thực tại ảo cho phép chúng ta
có cái nhìn trực quan, chính xác để có thể đưa ra những quyết định, những sáng kiến
thiết kế về các công trình xây dựng đúng đắn.
Trong giáo dục, những thí nghiệm được mô tả sát thực bằng máy tính giúp
cho người học hứng thú hơn, kiến thức được thể hiện rõ hơn, trực quan hơn, đầy đủ
hơn. Chẳng hạn, chúng ta có thể mô phỏng cấu trúc của các vật thể, tiến trình của
các phản ứng hoá học, phản ứng hạt nhân mà trong thực tế chúng ta không thể quan
sát được. Đối với một số lĩnh vực đào tạo yêu cầu tính thực hành cao như đào tạo lái
xe ô tô, lái tàu hoả, tàu thuỷ, lái máy báy, công nghệ mô phỏng có thể giúp chúng
ta tiết kiệm rất nhiều tiền của và thời gian bằng cách xây dựng các hệ thống tập lái
ảo. Ở Việt Nam hiện nay đã cho triển khai hệ thống tập lái xe ô tô ảo và hệ thống lái
tàu thuỷ ảo.
Trong quân sự, chúng ta có thể ứng dụng thực tại ảo để xây dựng các mô
hình tập trận ảo, tập lái và điều khiển xe tăng, máy bay chiến đấu ảo, đi đầu trong
lĩnh vực này phải kể đến trung tâm công nghệ mô phỏng thuộc học viện Kĩ thuật
Quân sự.
Cuối cùng là ứng dụng của Thực tại ảo trong việc tái tạo các công trình kiến
trúc (cả cổ điển và hiện đại). Những công trình mang tính lịch sử của nước ta như
Hoàng Thành Thăng Long, Đại Nội Huế, Văn Miếu Quốc Tử Giám, trong tương
lai gần sẽ được số hoá đưa vào máy tính phục vụ mục đích lưu trữ, bảo tồn hoặc
tham quan ảo, đồng thời thuận tiện hơn trong việc quảng bá, giới thiệu văn hoá Việt
Nam với thế giới.
1.5 Các công cụ phát triển ứng dụng Thực tại ảo
1.5.1 Các phần mềm xây dựng mô hình
Mô hình là một phần quan trọng trong các hệ thống thực tại ảo, mô hình mô
tả, biểu diễn một đối tượng trong thế giới thực bao gồm hình dạng bề mặt và hoạt
Hình 1.6 Các khung nhìn khác nhau trong phần mềm Maya. 14
Ta có hệ trục tọa độ ba chiều XYZ, màu xanh lam ứng với trục Y, màu đỏ
ứng với trục X và màu xanh đậm ứng với trục Z. Góc trên, bên phải là khung làm
việc cho phép ta thao tác trong không gian ba chiều, ba góc còn lại cho phép ta làm
việc ở ba mặt cắt của mô hình. Với các khung nhìn này ta có thể thao tác dễ dàng
hơn, khi một thay đổi xuất hiện ở một khung nhìn sẽ cho hiệu ứng đối với các
khung nhìn khác.
Bên cạnh hệ trục tọa độ XYZ ta còn có hệ tọa độ UV, hệ tọa độ UV bao bọc
bề mặt theo 2 chiều trái sang phải và dưới lên trên. Có thể hình dung ra hệ tọa độ
này như là các đường kinh tuyến và vĩ tuyến của trái đất. Hệ tọa độ này chủ yếu
được sử dụng trong quá trình thêm tính chất bề mặt cho mô hình.
1.5.2 Các công cụ lập trình
Các công cụ lập trình trong các ứng dụng Thực tại ảo thường là các thư viện
đồ hoạ 3D được xây dựng sẵn, miễn phí như DirectX, OpenGL, OpenSG,
OpenSceneGraph. Trước đây, chúng ta hay sử dụng các thư viện OpenGL và
DirectX, nhưng do mức độ hỗ trợ người lập trình trong các thư viện đó chưa cao
nên người ta đã mở rộng chúng thành OpenSG, OpenSceneGraph. Hai thư viện lập
trình OpenSG, OpenSceneGraph được xây dựng trên nền tảng OpenGL (hình 1.7)
và đưa vào khái niệm rất mới đó là “Đồ thị ngữ cảnh” – Scene Graphs. Theo đó,
mỗi đối tượng được biễu diễn như là một cây ngữ cảnh, mỗi nút có một nhân (core),
nhân của mỗi nút có thể là một đối tượng geometry, đối tượng transform, đối tượng
ánh sáng (light)
tượng xe ô tô có thể được biễu diễn bởi một đồ thị ngữ cảnh như hình 1.8.
OpenSG hỗ trợ các hàm và các đối tượng đồ hoạ cơ sở như Light, Geometry,
Transform, Material, Windows, Viewport, ngoài nó còn hỗ trợ cơ chế đa luồng,
lập trình hiển thị stereo. Để sử dụng được thư viện OpenSG, bạn cần dùng bộ biên
dịch FrameNet, thông thường OpenSG hay dùng với ngôn ngữ lập trình Visual
C.Net. Để biết thêm về thư viện đồ hoạ OpenSG, bạn có thể tìm hiểu và download
miễn phí OpenSG tại địa chỉ: www.opensg.org.
Car
Wheel
s
Body
Transformation
s
Wheelge
o
Light
Root
Light
Hình 1.8 Đồ thị ngữ cảnh của đối tượng Car
16
17
2.1 Kĩ thuật phát hiện va chạm dựa vào hộp bao AABB
2.1.1 Định nghĩa hộp bao AABB
AABB là hộp bao có dạng hình hộp chữ nhật có các cạnh song song với các
trục toạ độ tương ứng và bao lấy vật thể (hình 2.1).
Hình 2.1 Hộp bao AABB của đối tượng
Hộp bao AABB bao gồm một tâm C, ba hệ số a
0
, a
1
, a
2
tương ứng là độ dài
theo ba trục toạ độ của hình hộp.
2.1.2 Phát hiện va chạm giữa hai AABB
Cho hai hộp bao AABB xác định bởi [C
1
, a
0
, a
1
, a
2
] và [C
2
, b
0
2
,
2
2
,
2
0
01max
0
01min
0
01max
0
01min
0
01max
0
01min
c
Cz
c
Cz
b
Cy
b
Cy
a
Cx
a
Cx
y
min1
> y
max2
hoặc y
max1
< y
min218
x
min1
> x
max2
hoặc x
max1
< x
min2
Hộp bao này rất đơn giản, dễ tạo ra và kiểm tra, phát hiện va chạm cũng rất
dễ dàng. Tuy nhiên hộp bao AABB cũng tạo ra nhiều khoảng trống giữa vật thể và
hộp bao. Khi vật thể không nằm song song với các trục toạ độ và có dạng dài thì
khoảng trống này càng lớn. Thực tế trong các hệ thống thực tại ảo, người ta chỉ sử
dụng kĩ thuật hộp bao AABB để giới hạn vùng va chạm, sau đó để kiểm tra và tìm
điểm va chạm chính xác hơn, người ta sẽ sử dụng kĩ thuật hộp bao theo hướng OBB
sẽ được trình bày trong phần tiếp theo.
2.2 Kỹ thuật hộp bao theo hướng (Oriented Bounding Boxes)
2.2.1 Định nghĩa hộp bao theo hướng (OBB)
OBB là hộp bao AABB nhưng trục của nó có hướng bất kỳ. OBB có ưu điểm
Kỹ thuật phát hiện hộp bao theo hướng được chia làm hai mức [6]. 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, ngược lại nếu ở mức một phát hiện 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
19
chạm. Ở mức một, ta có thể kiểm tra nhanh xem có va chạm nào xảy ra không nhờ
dựa vào định lý sau đây.
Định lý 2.2.1 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.
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.
2.2.2 Kiểm tra nhanh 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ố [C
0
,A
0
,A
1
,A
2
,a
j
B
)
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 (
ji
BA
).
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 C
0
của hộp bao thứ nhất, do vậy nó có phương
trình như sau: d =
0
C
+ t*
V
Trong đó, t là tham số.
V
có thể là
ji
BA
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 C
0
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 C
0
(hình 2.4), độ dài của mỗi đoạn thẳng được xác định như sau :
|
||
*)**(
|),**(
2
0
2
0
0
V
VAas
dAasChc
i
iii
i
iii
} Với mọi |s
i
| = 1.
Đặt R
0
= r
0
*
||V
, ta có:
d
C
0
P
H
Hình 2.3 Hình chiếu của P lên đường thẳng d
Hình 2.4 Chiếu 8 đỉnh của hình hộp lên trục cô lập d
21
R
0
= max{ | a
0
*
+ a
1
*
VA
*
1
- a
2
*
VA
*
2
|
| a
0
*
VA
*
0
- a
1
*
VA
*
VA
*
2
|
|-a
0
*
VA
*
0
+ a
1
*
VA
*
1
+ a
2
*
VA
*
VA
*
0
- a
1
*
VA
*
1
+ a
2
*
VA
*
2
|
|-a
0
*
VA
*
0
*
1
| + a
2
*|
VA
*
2
|
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 C
0
như sau.
|
||
*)**(
|
||
*
),**(
2
0
2
0
1
V
Do vậy, khoảng cách nhỏ nhất chứa 8 đoạng thẳng (2.2) sẽ có tâm là C
1
và bán kính
R
1
được xác định như sau :
r
1
= max {
|
||
*)**(
|
2
0
V
VBbs
i
iii
} Với mọi |s
i
| = 1.
Đặt R
1
= r
1
0
C
1
> r
0
+r
1
||V
*C
0
C
1
>
||V
*r
0
+
||V
*r
1
R > R
0
+ R
1
(2.3)
) và B= (B
0
, B
1
, B
2
)
222120
121110
020100
ccc
ccc
ccc
C
(2.4)
B = C*A A
T
*B = C C =
*
, hay c
ij
chính là tích vô hướng của hai
vector A
i
, B
j
. Mặt khác, từ B = C*A A = C
T
*B
221100
BcBcBcA
iiii
Như trong phần đầu đã nói, tập các trục cô lập ứng cử viên
V
=
{
i
A
,
j
tính toán tương tự.
Xét trường hợp
V
=
0
A
:
R
0
= a
0
*|
VA
*
0
| + a
1
*|
VA
*
1
| + a
2
*|
*
2
| = b
0
*|c
00
| + b
1
*|c
01
|
+ b
2
*|c
02
|.
R =
0
A
*
D
Xét trường hợp
V
=
|
Mặt khác :
V
=
00
BA
=
)(
2201100000
AcAcAcA
=
120210
AcAc
R
0
= a
1
*|c
20
V
*
D
=
DAcAc
*)(
120210
Ta có viết lại
V
dưới dạng:
V
=
00
BA
=
0202101000
)( BBcBcBc
VB
*
2
=
)(*
1022012
BcBcB
= -c
01
R
1
= b
1
*|c
02
|+ b
2
*|c
01
|
Tiếp tục làm cho các trường hợp còn lại, ta xây dựng được bảng các giá trị
cho R, R
0
, R
1
02
|
|.|
0
DA
1
A
a
1
b
0
|c
10
|+b
1
|c
11
|+b
2
|c
12
|
|.|
1
0
B
a
0
|c
00
|+a
1
|c
10
|+a
2
|c
20
|
b
0
|.|
0
DB
1
B
a
|c
12
|+a
2
|c
22
|
b
2
|.|
2
DB
Copyright: Tài liệu đại học ©