0

ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
Lƣơng Quang Linh
NGHIÊN CỨU MỘT SỐ PHƢƠNG PHÁP RÚT GỌN
SỐ LƢỢNG ĐIỂM BIỂU DIỄN Ngành: Công nghệ Thông tin
Mã số: 1.01.10

LUẬN VĂN THẠC SĨ

NGƯỜI HƯỚNG DẪN KHOA HỌC
Tiến sĩ Đỗ Năng Toàn Hà Nội – 2007

3

2.2.5. Kiểm tra tính toàn vẹn 49
2.2.6. Kết luận 51

4
2.3. Đơn giản hóa bề mặt kết hợp với kỹ thuật che phủ 53
2.3.1. Rút gọn số lượng bề mặt biểu diễn dựa vào kỹ thuật che phủ 53
2.3.2. Mô hình "Sao la" 57
Chương 3: ỨNG DỤNG 59
3.1. Nhận dạng các đối tượng hình học cơ sở 59
3.1.1 Xấp xỉ đa giác theo bất biến đồng dạng 60
3.1.2 Xấp xỉ đa giác theo bất biến aphin 63
3.2. Rút gọn kích thước đối tượng 3 chiều 64
3.2.1 Dữ liệu thực tại ảo và các bước trong xây dựng 64
3.2.2. Thực nghiệm 66
KẾT LUẬN 68
TÀI LIỆU THAM KHẢO 70 5
MỞ ĐẦU
Sự phát triển của công nghệ thông tin đã đẩy nhanh sự phát triển nhiều
lĩnh vực của đời sống xã hội. Với sự phát triển của phần cứng về cả phương
diện thu nhận và hiển thị đã mở ra nhiều hướng mới cho sự phát triển của
phần mềm. Trong số đó phải kể đến lĩnh vực thể hiện hình ảnh 3 chiều.
Trong lĩnh vực thể hiện hình ảnh 3 chiều có 2 phần chính là tạo mô
hình bề mặt (Modelling) và tạo sự chuyển động cho mô hình (Animation).
Việc tạo mô hình 3 chiều thường thông qua máy quét 3 chiều hoặc các
phần mềm chuyên dụng. Hai phần mềm chuyên dụng phổ biến hiện nay
trên thế giới là Maya và 3Ds max. Mỗi phần mềm có thế mạnh riêng, trong
đó 3Ds max được người sử dụng Việt Nam biết đến nhiều hơn thông qua

Chương 3: Ứng dụng
Trình bày ứng dụng của việc rút gọn số lượng điểm biểu diễn vào việc
xấp xỉ đối tượng bởi các hình cơ sở và ứng dụng việc rút gọn số lượng mặt
biểu diễn trong việc giảm thiểu không gian lưu trữ đối với đối tượng
ba chiều 7
Chương 1:
TỔNG QUAN VỀ THỰC TẠI ẢO VÀ RÚT GỌN
BIỂU DIỄN BỀ MẶT

1.1. Tổng quan về thực tại ảo
1.1.1. “Thực tại ảo” là gì?
Theo cách truyền thống, việc tương tác với máy tính được thực hiện
thông qua các thiết bị như bàn phím, chuột hay joystick/trackball để cung
cấp thông tin đầu vào và sử dụng khối hiển thị trực quan (VDU) để nhận
thông tin đầu ra từ hệ thống. Với sự ra đời của các hệ thống Thực tại ảo
(Virtual Reality-VR), các phương thức giao tiếp mới được phát triển cho
phép người sử dụng tương tác một cách tích cực với máy tính.
Thực tại ảo là công nghệ sử dụng các kỹ thuật mô hình hoá không
gian ba chiều với sự hỗ trợ của các thiết bị đa phương tiện hiện đại để xây
dựng một thế giới mô phỏng bằng máy tính – môi trường ảo (virtual
environment). Trong thế giới ảo này, người sử dụng không còn được xem
như người quan sát bên ngoài, mà đã thực sự trở thành một phần của hệ
thống. Một cách lý tưởng, người sử dụng có thể tự do chuyển động trong
không gian ba chiều, tương tác với các vật thể ảo, quan sát và khảo cứu thế
giới ảo ở những góc độ khác nhau về mặt không gian. Ngược lại, môi
trường ảo lại có những phản ứng tương ứng với mỗi hành động của người
sử dụng, tác động vào các giác quan như thị giác, thính giác, xúc giác của


9
HMD có giá chấp nhận được trên thị trường, và như vậy ngành công
nghiệp Thực tại ảo đã ra đời.
1.1.3. Các lĩnh vực ứng dụng
Mặc dù khái niệm về Thực tại ảo đã xuất hiện từ khá lâu, nhưng do
nhiều lý do về mặt công nghệ (kéo theo chi phí cho nghiên cứu và phát
triển), phải mất nhiều thời gian và nỗ lực để Thực tại ảo có được những
thành tựu như ngày nay. Hiện tại đây vẫn là lĩnh vực công nghệ nhiều tiềm
năng xét về khía cạnh ứng dụng. Ở đây, báo cáo cố gắng đưa ra những lĩnh
vực ứng dụng chính có khuynh hướng phát triển mạnh mẽ nhất trong thời
gian gần đây.
1.1.3.1. Kiến trúc và thiết kế thiết bị công nghệ
Một trong những lĩnh vực ứng dụng tiêu biểu nhất của Thực tại ảo là
thiết kế kiến trúc. Khả năng mô hình hoá thế giới thực của công nghệ Thực
tại ảo dường như đáp ứng một cách tự nhiên mục tiêu của ngành thiết kế
kiến trúc: Đưa ra mô hình trực quan nhất có thể về hình ảnh công trình kiến
trúc mong muốn trong tương lai.

Hình 1.1: Ứng dụng thực tại ảo trong thiết kế kiến trúc
(Hình ảnh của hoạ sỹ Chris LeBlanc

10
Việc xây dựng các mô hình không gian kiến trúc bằng hình ảnh lập
thể với đầy đủ mô tả trực quan về các hình khối kiến trúc của một căn nhà,
cách bố trí nội thất bên trong, thậm chí hoa văn cửa sổ hay màu sơn của
tường, cùng với khả năng cho phép khách hàng tự do tham quan, khảo sát
căn nhà của họ trong tương lai theo nhiều góc độ và vị trí, từ phòng này
sang phòng khác thực sự đem lại hiệu quả trực quan mang tính cách mạng
trong lĩnh vực mang nhiều đặc điểm nghệ thuật này.

tốc đồ hoạ (graphic accelerator cards). Nếu như chúng ta trở lại khoảng 10
năm về trước, thật khó có thể tìm thấy một card tăng tốc đồ hoạ có đủ năng
lực tính toán cần thiết cho phép tạo ra các ứng dụng Thực tại ảo thời gian
thực. Tại thời điểm đó, những chiếc card như vậy trị giá hàng ngàn đô-la và
chỉ đủ khả năng sinh 100.000 đa giác/giây ở mức độ phân giải trung bình.
Những thiết bị phần cứng khác như Găng tay dữ liệu (DataGloves) và Thiết

12
bị hiển thị đội đầu (Head Mounted Displays-HMD) cũng chịu ảnh hưởng
phần nào của công nghiệp giải trí. Tóm lại, chúng ta có thể nói rằng các
ứng dụng Thực tại ảo trong giải trí đã và đang đóng một vai trò quan trọng
trong việc định hướng đi cho công nghiệp Thực tại ảo.
1.1.3.3. Giáo dục và Đào tạo
Phát triển trên nền công nghệ và kỹ thuật cao, Thực tại ảo tích hợp
những đặc tính làm cho bản thân nó có những tiềm năng vượt trội so với
các công nghệ đa phương tiện truyền thống khác, cho người sử dụng cảm
nhận sự hiện diện của mình trong môi trường do máy tính tạo ra bằng khả
năng tương tác, tự trị (autonomy) của người dùng trong môi trường ảo,
cũng như bằng những phản hồi tức thời, trực quan từ phía môi trường ảo
tới các giác quan của người sử dụng. Hơn thế nữa, công nghệ Thực tại ảo
cho phép mô phỏng những môi trường nguy hiểm hay tốn kém như buồng
lái máy bay, phòng thí nghiệm hoá chất v.v

Hình 1.4: Mô hình huấn luyện bay sử dụng công nghệ Thực tại ảo
(Hình ảnh từ hãng Boeing
Tất cả những đặc tính này khiến công nghệ Thực tại ảo trở nên rất phù
hợp cho các ứng dụng có tính chất giáo dục hay đào tạo. Trong đó, những

13
mô hình trình diễn lập thể đóng vai trò quan trọng. Các vật thể trong thế


Hình 1. 5: Phẫu thuật ảo – Phương pháp
đào tạo phẫu thuật mới dùng công nghệ
Thực tại ảo
(Hình ảnh từ Virtualvision Inc., Artma
Biomedical Inc. ;
Phương pháp đào tạo có tính tương tác cao này mang nhiều ưu điểm
so với các phương pháp truyền thống như thực hành trên mô hình plastic
hay trên bệnh nhân thực. Thứ nhất, khác với phương pháp dùng mô hình
plastic, sinh thể giải phẫu ảo có khả năng cung cấp những thông tin phản
hồi sinh học một cách tự nhiên như một sinh thể sống thực, dưới tác động
giải phẫu của bác sỹ mổ, chẳng hạn như sự thay đổi về nhịp tim, huyết
áp,… Điều này tạo cho học viên có cảm giác đang trải qua một ca mổ trong
một tình huống thực. Thứ hai, khác với thực hành trên bệnh nhân thật, rõ
ràng sai lầm của học viên trong quá trình thực tập không phải trả giá bằng
những thương tổn thực trên cơ thể người bệnh. Điều này cũng làm giảm áp
lực lên học viên khi thực hiện phẫu thuật ảo. Từ đó, giúp họ tự tin và chủ
động hơn trong học tập.
Phương pháp này không chỉ cho phép các học viên y khoa thực hành
các ca phẫu thuật trong tình huống thực, đem lại cho họ những kinh nghiệm
cần thiết trước khi thực hiện phẫu thuật trên cơ thể con người, đây còn là cơ
hội để các bác sỹ mổ nâng cao kỹ thuật giải phẫu và kỹ năng phối hợp làm

15
việc theo nhóm trong phòng mổ. Điều này đặc biệt quan trọng trong các
tình huống phẫu thuật nguy hiểm và nhạy cảm.
Các kỹ thuật Thực tại ảo cũng được sử dụng để hỗ trợ bác sỹ mổ trong

Export
Mô
hình
Đơn
giản hóa

16
1.2.2. Biểu diễn bề mặt
Để có thể mô tả được đối tượng khảo sát bằng thực tại ảo chúng ta cần
phải biểu diễn được các đường cong và bề mặt cho các đối tượng đang tồn
tại trong thế giới thực dưới dạng các mô hình các đối tượng đang tồn tại
(modeling existing objects), chẳng hạn như ôtô, bề mặt, quả núi, v.v hoặc
trong mô hình tạm thời (modeling from scratch) cho các đối tượng vật lý đã
không tồn tại trước đó được biểu diễn ở dạng mô hình (Foley et al. , 1994-
1996).
Trong trường hợp thứ nhất, nếu không thể mô tả hình dạng của đối
tượng bằng toán học, ta có thể sử dụng mô hình tọa độ của tất cả các điểm
thuộc đối tượng. Cách tiếp cận này khó thực hiện đối với máy tính vì khả
năng lưu trữ có hạn. Người ta thường xấp xỉ đối tượng bằng các phần mặt
phẳng, mặt hình cầu hoặc các bề mặt khác để có thể dễ dàng mô tả bằng
toán học. Tuy nhiên, cần phải làm sao cho các điểm trong mô mình phải
gần với vị trí các điểm tương ứng của đối tượng thực.
Trong trường hợp thứ hai, khi không có sự tồn tại trước đó của đối
tượng dưới dạng mô hình, người sử dụng tạo ra đối tượng trong mô hình xử
lý. Để tạo ra đối tượng, người sử dụng phải chỉnh sửa đối tượng, mô tả nó
dưới dạng toán học hoặc đề ra một mô tả xấp xỉ để đưa vào một chương
trình ứng dụng nào đó. Trong CAD, việc biểu diễn bằng máy tính được sử
dụng cuối cùng để thể hiện về mặt vật lý của đối tượng đã được mô tả dưới
dạng lý thuyết.
Mô hình bề mặt (Surface modeling) là một lĩnh vực rộng lớn, thu hút

gian hơn. 18
a) Biểu diễn lưới đa giác
Ba cách biểu diễn lưới đa giác được xét ở đây là: Biểu diễn theo hàm
hiện, con trỏ tới danh sách các đỉnh và con trỏ tới danh sách các cạnh
(Foley et al 1994).
Trong cách biểu diễn theo hàm hiện (explicit representation), mỗi một
đa giác được biểu diễn bởi danh sách tọa độ của các đỉnh:
P = ((x
1
, y
1
, z
1
),(x
2
, y
2
, z
2
), , (x
n
, y
n
,z
n)
).
Các đỉnh được lưu theo thứ tự mà ta sẽ gặp chúng khi đi một vòng

2
, y
2
z
2
), , (x
n
, y
n
z
n
)).

Hình 1.7: Lưới đa giác xác định bằng các chỉ số trong danh sách các đỉnh
Một đa giác được xác định bởi danh sách các chỉ số (hoặc các con trỏ)
tới danh sách các đỉnh. Chẳng hạn, một đa giác có các đỉnh là 3, 5, 7 và 10
thì danh sách các đỉnh được biểu diễn là P = (3, 5, 7, 10)
Một ví dụ của cách biểu diễn này được chỉ ra trong hình 1.7 có một
vài ưu điểm hơn so với cách biểu diễn đa giác theo hàm hiện. Mỗi một đỉnh
chỉ được lưu một lần, như vậy tiết kiệm được không gian. Hơn nữa, tọa độ
của các đỉnh có thể được thay đổi một cách dễ dàng. Tuy nhiên, vẫn khó
khăn để xác định các đa giác có chung cạnh; các đa giác có chung cạnh vẫn
được vẽ hai lần cho cạnh chung đó. Ta có thể giải quyết các vấn đề này
bằng cách biểu diễn các cạnh theo hàm hiện, như trong phương pháp sau :
Khi một đa giác được xác định bởi con trỏ tới danh sách các cạnh
(pointers to all edge list), ta có danh sách các cạnh V. Trong phương pháp
này, biểu diễn đa giác theo danh sách các con trỏ nhưng không phải trỏ tới

) = ((x
1
,y
2
,z
1
), , (x
4
, y
4
, z
4
))
P
1
= (1, 2, 4) 1, 2, 3, 4 là chỉ số các đỉnh
P
2
= (4, 2, 3)

20
Như vậy, mô tả đa giác dưới dạng P = (E
l
, , E
n
) và một cạnh được
mô tả: E = (V
l
,V
2


P
2
,

P
n
).
Trong ba cách biểu diễn này (đa giác theo hàm hiện, con trỏ tới danh
sách các đỉnh, con trỏ tới danh sách các cạnh) không dễ dàng xác định
xem những cạnh nào trùng với một đỉnh; tất cả các cạnh đều phải được
kiểm tra. Tất nhiên, các thông tin có thể được thêm vào để xác định các
mối quan hệ .
Hình 1.9: Biểu diễn mặt cầu bằng lưới đa giác
E
1

E
4

E
2

E
3

E

,y
2
,z
1
), , (x
4
, y
4
, z
4
))
E
1
= (V
1
, V
2
, P
1
, λ)
E
2
= (V
2
, V
3
, P
2
, λ)
E

= (E
1
, E
4
, E
5
)
P
2
= (E
2
, E
3
, E
4
)

21
Khi biểu diễn dữ liệu cho bề mặt lưới đa giác hoặc cho một vật thể ba
chiều nói chung trong máy tính, nên nhập dữ liệu thành một file riêng. Điều
này rất tiện lợi khi ta muốn thay đổi vật thể thì chỉ cần thay đổi dữ liệu ở
file riêng này. Ngoài ra, cách tổ chức dữ liệu thành file riêng này còn giảm
được bộ nhớ cho chương trình và thực hiện rất tốt với cả vật thể phức tạp.
Trong CAD, các fìle này đã có định dạng sẵn.
b) Phương trình mặt phẳng
Khi làm việc với nhiều đa giác hoặc lưới đa giác, ta thường cần phải
biết tới phương trình của mặt phẳng chứa đa giác đó. Trong một vài trường
hợp, các phương trình này được biết theo hàm ẩn qua phương pháp xác
định đa giác. Nếu không biết được phương trình, ta có thể sử dụng toạ độ
của ba đỉnh để xác định mặt phẳng.
22

A = y
1
(z
2
– z
3
) + y
2
(z
3
– z
1
) + y
3
(z
1
– z
2
)
B = z
1
(x
2
– x
3
) + z

)
D = -x
1
(y
2
z
3
– y
3
z
2
) - x
2
(y
3
z
1
– y
1
z
3
) - x
3
(y
1
z
2
– y
2
z

v.v ).
Vector pháp tuyến này có ba thành phần A, B, C xác định bởi phương
trình (1.3), nếu tích vector này là 0, ba điểm này thẳng hàng và không xác
định được mặt phẳng. Nếu có thể được, ta dùng đỉnh khác để thay thế.
Cho một tích các vector khác 0, ta có thể xác định D bằng cách thay
thế pháp tuyến [A, B, C] và một trong ba điểm vào phương trình (1.l).
Khi đã xác định được phương trình của mặt phẳng bằng cách sử dụng
toạ độ của tất cả các đỉnh, ta có thể đánh giá sự không đồng phẳng của đa

(1.3)

23
giác bằng cách tính các khoảng cách từ mặt phẳng tới mỗi đỉnh. Khoảng
cách d tới đỉnh có toạ độ (x,y,z) là : Khoảng cách này có thể dương hoặc âm, tuỳ thuộc vào vị trí của điểm
đó đối vị trí mặt phẳng. Nếu đỉnh ở trên mặt phẳng thì d = 0. Tất nhiên, nếu
chỉ để xác định xem điểm đó nằm ở phía bên nào đối với mặt phẳng, ta chỉ
cần xét dấu của d. Ta thấy, mẫu số trong (1.4) là không có ý nghĩa về dấu
của nó. Như vậy, chúng ta chỉ phải quan tâm đến biểu thức tử số trong
phương trình (1.4).
Ta cũng thấy rằng, phương trình của mặt phẳng là không duy nhất; khi
nhân thêm với hằng số k ≠ 0 sẽ làm thay đổi phương trình, nhưng không làm
thay đổi mặt phẳng. Tốt nhất là nên lưu trữ các hệ số của mặt phẳng với
pháp tuyến của nó; chẳng hạn có thể lưu nghịch đảo của độ dài của vector
pháp tuyến.

Khi đó, khoảng cách được tính dễ dàng từ phương trình (1.4).
*) Xác định điểm trên mặt phẳng

(1.6)

Ax + By + Cz + D
A
2
+ B
2
+ C
2

d =
(1.4)
1
A
2
+ B
2
+ C
2

k =
(1.5)

24
Như vậy :

trong đó u và v là hai số thực.
1.3. Rút gọn bề mặt trong biểu diễn bề mặt vật thể ba chiều
Mục tiêu của thực tại ảo là làm thế nào có thể biểu diễn được các đối
tượng vật thể trong không gian ba chiều qua mô hình biểu diễn. Ở trường

trung bình hiện nay có thể tính toán và thể hiện khoảng 15 triệu mặt trong
một giây; ở tốc độ video hiện tại là 30 hình/s (NTSC) chúng ta sẽ bị giới
hạn khoảng 500.000 mặt cho mọi khuôn hình. Với tốc độ xử lý của máy vi
tính cá nhân (PC) như vậy, chúng ta thấy rằng, còn rất nhiều hạn chế đối
với việc phổ cập các ứng dụng thực tại ảo trong không gian ba chiều
hiện nay. a) - Quan sát vật thể ở gần - mô hình biểu diễn ~ 6000 mặt
b) - Quan sát vật thể ở xa
- mô hình biểu diễn ~ 100 mặt
Hình 1.10: Minh họa yêu cầu chất lượng quan sát vật thể trong thực tế

26
Các thuật toán "giảm thiểu đa diện" biểu diễn một vật thể trong không
gian ba chiều hiện nay là không nhiều đối với đa số các ứng dụng thực tại
ảo. Trong thực tế, không phải lúc nào chúng ta cũng cần biểu diễn một vật
thể trong không gian ba chiều với chất lượng như thật. Hơn nữa, mức độ
chất lượng hình ảnh của cùng một vật thể khi hiển thị cũng có thể thay đổi
theo cách nhìn (view). Ví dụ, khi quan sát cận cảnh một vật thể, chúng ta
cần số lượng mặt nhiều hơn (khoảng 10.000 mặt) để việc mô hình hoá có