Bài giảng Công nghệ đồ họa và hiện thực ảo - Bài 10: Hình đặc - Trịnh Thành Trung

©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
Trịnh Thành Trung 
trungtt@soict.hust.edu.vn 
Bài 10 
HÌNH ĐẶC 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
- 
NỘI DUNG 
1. Tính chất của hình đặc 
2. Mô hình hóa hình đặc 
3. Bán đại số nửa không gian r-set 
4. Phương pháp biểu diễn B-rep 
5. Hình học cấu trúc đặc 
6. Phương pháp liệt kê không gian 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
- 
TÍNH CHẤT CỦA HÌNH ĐẶC 
1 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
• Rigidity Tính cứng– tính chất dễ dàng có được nếu 
khoảng cách và góc giữa các điểm trong không gian 
Euclid là cố định. Các chuyển động cứng đảm bảo cho 
khoảng cách và các góc này không đổi. Như vậy các 
trường hợp khi cho chuyển động cứng, không gian tạo 
thành có thể được dùng để mô hình hoá các đối tượng. 
• Finiteness Tính hữu hạn– đối tượng vật lý phải là hữu 
hạn. Để đảm bảo tính hữu hạn đó cần có đường biên cho 
không gian. 
• Tính đặc - Solidity – mô hình hình đặc phỉ là đồng nhất, 
không có các mặt hay các cạnh rời. Chúng ta coi đây là 
một trong những tính hợp lệ của không gian 3D 
Các tính chất cơ bản của solid 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
• Hoạt động với phép toán Boolean - Closure under 
Boolean operations 
– Phép toán Boolean áp dụng lên hình được phải tạo ra 
hình đặc. 
– Các ưu điểm của phép toán Boolean 
– Kết quả của phép toán Boolean có thể được dùng 
làm đầu vào cho phép toán Boolean khác. Như vậy 
hình đặc có thể dần dần được xây dựng trên cơ sở 
các phép toán Bool. 
– Mô hình trong tiến trình sản xuất sử dụng 
Các tính chất cơ bản của solid 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
• Mô tả hữu hạn Finite describability – Tập các điểm được 
sử dụng mô hình hoá hình đặc phải mô tả được bởi dữ 
liệu hữu hạn để đảm bảo chúng có thể biểu diễn bằn máy 
tính với bộ nhớ hữu hạn. 
• Khối đa diện có thể được mô tả bằng tọa độ đỉnh và thông 
tin kết nối nhằm xác định cạnh và các mặt. Tuy nhiên mô 
hình đa diện chỉ là trường hợp nhỏ. Vì vậy chúng ta cần 1 
mô hình tương tự với các bề mặt cong. 
• Biên xác định - Boundary determinism – Hình đặc phải 
được mô hình hoá trên tập rõ ràng xác định bởi các biên. 
Phương pháp biểu diễn Breps dựa trên các mặt biên là 
một trong những phương pháp phổ biến biểu diễn hình 
đặc. 
Các tính chất cơ bản của solid 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
- 
MÔ HÌNH HÓA HÌNH ĐẶC 
2 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
• Mô hình hoá hình đặc (mô hình hoá 3D) các thực thể vật lý là 
phương pháp biểu diễn dựa trên mô tả các thực thể dưới dạng 
các mô hình toán học, các ký hiệu, sơ đồ. 
• Có 2 phương pháp nền tảng cho việc phân loại các cách biểu 
diễn: 
– Phương pháp mô tả biên-Boundary Representations (B-
reps) mô tả các đối tượng như là tập các bề mặt phân 
cách hình đặc với môi trường của chúng 
– Phương pháp liệt kê không gian - Space Partitioning 
representations mô tả các đối tượng dưới dạng tập các 
khối nhỏ đơn vị liên tiếp không chồng nhau tạo nên 
• Ví dụ 
– Biểu diễn đa giác - Polygonal Representations 
– Hình học cấu trúc khối rắn - Constructive Solid Geometry 
Mô hình hóa hình đặc 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
• Sơ đồ biểu diễn - Representation Schemes là cách thức biểu 
diễn phương pháp mô hình hoá các đối tượng thông qua các 
thành phần của chúng nhằm đảm bảo độ chính xác rõ ràng cho 
các mô tả. Đồng thời đảm bảo tính duy nhất của kết quả 
• Ví dụ: sơ đồ biểu diễn cho hình vẽ trên 
1. Mỗi đa giác cấu tạo bởi tập các đỉnh theo thứ tự tuỳ ý. 
2. Mỗi 1 đỉnh được biểu diễn với cặp 2 số thực mô tả tọa độ của 
đỉnh đó trong 1 bản vẽ nào đó 
3. Danh sách (chuỗi các phần tử) chứa tất cả các cặp số thực . 
Như vậy sơ đồ biểu diễn đa giác là cấu trúc các ký tự danh sách 
các cặp số thực sau: 
x1,y1 ( ); x2 ,y2( ) xn,yn( ) 
Sơ đồ biểu diễn 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
• Miền-Domain – là mức độ phủ hình học của sơ đồ biểu diễn. Nó 
chỉ ra loại đối tượng có thể được biểu diễn bằng sơ đồ. 
• Tính hợp lệ Validity – chỉ ra các biểu diễn có tương ứng với các 
đối tượng trong miền-domain không? các dữ liệu sai có là 
nguyên nhân dẫn đến các treo hệ thống khi biểu diễn đối tượng. 
• Tính trong sáng -Non-ambiguity 
– Đầy đủ - completeness mỗi biểu diễn phải phải tạo ra đối tượng 
hoàn chỉnh đầy đủ dữ liệu và thực hiện mọi phép toán. Nó là cơ 
sở cho việc biểu diễn và tính toán các thuộc tính cho đối tượng 
1 cách tự động 
– Duy nhất –Uniqueness biểu diễn hợp lệ tương ứng với 1 đối 
tượng duy nhất trong miền 
Các thuộc tính của sơ đồ biểu diễn 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
• Xúc tích - Conciseness 
• Dễ xây dựng - Ease of construction. 
• Khả hợp với các ứng dụng - Suitability for 
applications 
Thuộc tính bổ sung của 
sơ đồ biểu diễn 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
- 
BÁN ĐẠI SỐ NỬA KHÔNG GIAN 
3 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
• Nửa không gian - Half Space là phần không gian vô 
hạn được giới hạn bởi 1 bề mặt 
• {p : f (p) <= 0} 
• ax + by + cz + d <= 0 
• Tập bán đại số - semi-algebraic set là kết quả thu 
được của các phép toán tập hợp trên các nửa không 
gian half spaces. 
• r-sets là các tập bán đại số chính quy, bao đóng 
• Chúng phải đảm bảo có các tính chất :cứng- rigid, hữ 
hạn-finite, đặc-solid, và thoả mãn các phép tóan 
Boolean. Là độc nhất dưới đường bao. 
• phương pháp mô hình hóa các đối tượng cứng đồng 
nhất. 
Bán đại số nửa không gian r-set 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
- 
BIỂU DIỄN BIÊN B-REP 
4 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
• B-REP biểu diễn các đối tượng vật lý thông 
qua không gian được bao bởi các mặt kín 
có hướng. 
• Mô hình hoá được biểu diễn bằng đồ thị 
mô tả cấu trúc liên kêt gồm các nút là các 
mặt, cạnh và đỉnh của hình solid được áp 
dụng rộng rãi trong thực tế. 
• Mũi tên giữa các nút là thông tin mô tả kết 
nối. 
• Tọa độ các đỉnh là thông tin dữ liệu đo-
metric information 
• Thuật ngữ mô tả thông tin về cấu trúc kết 
nối là topology 
• Thông tin đo được goin là thông tin hình 
học geometry. 
Phương pháp biểu diễn biên 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
• MẶT 
– Mỗi mặt - Face là Tập con của các biên tôpo hình 
đặc. 
– Tập kết hợp tất cả các mặt tạo thành biên cho hình 
đặc. 
– Mỗi mặt chỉ là tập con duy nhất của 1 cá thể bề mặt. 
– Mỗi mặt phải có tính đồng nhất 2D, không có các 
cạnh hay đỉnh rời. 
– Các mặt phải được kết nối 
– Các mặt chỉ bị tách ra tại các cạnh hay đỉnh nút 
– Nếu các tính chất trên được thoả mãn thì mặt đó là 
biên của hình đặc 
Các thành phần của b-rep 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
• CẠNH 
1. Cạnh là tập con biên của mặt. 
2. Tập tất cả các cạnh có liên quan đến mặt tạo 
thành biên của mặt. 
3. Mỗi cạnh là một phần của phần giao giữa hai 
mặt cong 
4. Mỗi cạnh là một 1-manifold (đa tạp) kết nối 
5. Các cạnh được coi là rời nhau, chỉ tiếp xúc tại 
các đỉnh 
6. Một cạnh là tập lớn nhất của đường biên các 
mặt thỏa mãn đầy đủ các điều kiện nêu ra ở 
trên 
Các thành phần của b-rep 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
- 
HÌNH HỌC CẤU TRÚC ĐẶC 
5 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
• Được xây dựng trên tập nhỏ các tham biến do người 
dùng định nghĩa để xác định mô hình hình học, vị trí 
và hướng tạo nên các đối tượng cơ sở. 
• Tập các thực thể cơ sở bao gồm: 
– hình hộp - block, 
– hình cầu - sphere, 
– hình trụ - cylinder, 
– hình nón - cone, 
– hình nhẫn torus, 
– hình nêm wedge 
Hình học cấu trúc đặc 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
• 3 phép toán cơ bản 
• Union (Phép hợp) 
• Phép hợp - Union của 
đối tượng A và đối 
tượng B lf đối tượng 
được hình thành bởi 
phần không gian hợp 
thành từ 2 đối tượng đó. 
• X = A + B 
• Tính chất : A + B = B + A 
Các phép toán CSG 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
• Giao - intersection của đối 
tượng A và đối tượng B là phần 
không gian được hình thành từ 
phép toán AND giữa 2 đối 
tượng. 
• X = A | B 
• Tính chất: 
• A | B = B | A 
Phép giao 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
• Đối tượng X là phần trừ của 
giữa A và B nếu mọi điểm của 
X chứa trong A mà không chứa 
trong B 
X = A - B 
• Tính chất: 
A - B B - A 
• Phép trừ không giao hoán 
Phép trừ 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
Ví dụ 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
• Phép toán Bool trên các đối tượng hình học 
nhằm tạo ra các đối tượng mới 
• Cấu trúc cây nhị phân có thể được sử dụng như 
ngôn ngữa để biểu diễn hình học cấu trúc đặc. 
• Mỗi cây con tại các nút biểu diễn hình đặc là kết 
quả từ các phép toán Boolean và các phép biến 
đổi hình học lớp dưới 
Cây cấu trúc trong CSG 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
Cây cấu trúc trong CSG 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
• Hai kỹ thuật ứng dụng cho việc 
tạo ra các thực thể thể hình học 
rắn cơ sở làm dữ liệu đầu vào cho 
cây CSG là phép quay và phép 
tịnh tiến lathing - extrusion. 
Mở rộng của CSG 
X 
Y 
Z 
sweep 
X 
Y 
Z 
sweep 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
- 
PHƯƠNG PHÁP LIỆT KÊ 
KHÔNG GIAN 
6 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
Voxel 
Quadtree 
Partially occupied 
(further decomposition 
required) 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
So sánh CSG và Voxel 
CSG - constructive solid geometry 
3D Objects defined as boolean operations 
on solid primitives. 
Volumetric model. 
3D Object is a collection of volume 
elements or voxels which flag spatial 
occupancy in a discrete region.