HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
KHOA CÔNG NGHỆ THÔNG TIN
***o0o***
KĨ THUẬT ĐỒ HỌA
Đề Tài: THIẾT KẾ HỆ THỐNG KIỂM TRA CÁC QUAN HỆ
HÌNH HỌC TRONG 3D
Giảng viên hướng dẫn : Trịnh Vân Anh
Nhóm sinh viên thực hiện :
Lớp:
Hà nội ngày 02-12-2010
Đề tài: Thiết kế hệ thống kiểm tra các quan hệ hình học trong 3D
MỤC LỤC
PHẦN I: GIỚI THIỆU.........................................................................................................3
I.SƠ LƯỢC VỀ HỆ THỐNG KIỂM TRA CÁC QUAN HỆ HÌNH HỌC.........................3
II.GIỚI THIỆU SƠ LƯỢC NGÔN NGỮ THỂ HIỆN ĐỀ TÀI.........................................3
1.Sơ lược ngôn ngữ....................................................................................................................3
2.Giới thiệu các hàm của ngôn ngữ được sử dụng...................................................................4
PHẦN II: NỘI DUNG.......................................................................................................10
I.LÝ THUYẾT CƠ SỞ TOÁN HỌC..............................................................................10
1.Giới thiệu về vector:.............................................................................................................10
2.Các phép tính vector:............................................................................................................11
II.CÁC ĐỐI TƯỢNG HÌNH HỌC VÀ SỰ TƯƠNG QUAN TRONG 3D.....................24
1.Các đối tượng hình học cơ bản:............................................................................................24
2.Sự tương quan giữa các đối tượng hình học:.......................................................................24
3.Kiểm tra sự tương quan giữa các đối tượng hình học:.........................................................24
III.CÁC THUẬT TOÁN KIỂM TRA SỰ TƯƠNG QUAN GIỮA CÁC ĐỐI TƯỢNG
HÌNH HỌC TRONG KHÔNG GIAN 3D.......................................................................25
1.Các phép biến hình 3 chiều...................................................................................................25
2.Biểu diễn đối tượng 3D........................................................................................................27
3.Quan sát vật thể 3D qua hệ tọa độ quan sát.........................................................................29
4.Kiểm tra quan hệ Điểm - Đường thẳng ..............................................................................32
với nhau? Cắt nhau một góc bao nhiêu độ, song song, hay trùng nhau...
Đó là về mặt thuật toán chương trình kiểm tra, đây chỉ mới là một tác vụ thực hiện
của vấn đề này. Với bài toán như trên nếu chỉ đưa ra được những kết luận với những
dòng thông điệp thì chúng ta thấy rằng đề tài trở nên quá đơn giản không phong phú và
hấp dẫn qua ý kiến của người đọc hoặc tham khảo. Một tác vụ cùng đồng thời với bài
toán trên mà nhiệm vụ của đề tài yêu cầu thực hiện là khi đưa vào giả thiết bài toán chẳng
hạn hai điểm A và B với những tọa độ xác định nào đó, qua hai điểm này sẽ thực hiện vẽ
lên một đoạn thẳng qua hai điểm A và B. Từ đó thấy vấn đề một cách trực quan hơn, hay
vẽ ra góc giữa hai đường thẳng, chính với những thể hiện này đề tài trở nên hấp dẫn
phong phú hơn, tất nhiên vấn đề này không ít những khó khăn cho người thực hiện đề
tài.
II. GIỚI THIỆU SƠ LƯỢC NGÔN NGỮ THỂ HIỆN ĐỀ TÀI
1. Sơ lược ngôn ngữ
Ở phần I giới thiệu sơ lược về “THIẾT KẾ HỆ THỐNG KIỂM TRA CÁC QUAN
HỆ HÌNH HỌC TRONG 3D“, chúng em đã trình bày một ví dụ về yêu cầu nhiệm vụ để
thực hiện một tác vụ kiểm tra vấn đề nào đó của đề tài này. Để thực hiện những vấn đề đó
chúng em nghiên cứu và thực hiện trên môi trường ngôn ngữ Visual C++.
Visual C++ là một phần mềm lập trình hướng đối tượng được phát triển trên cơ sở là
ngôn ngữ lập trình C và C++. Ở đây chúng em thể hiện đề tài trên ngôn ngữ Visual C++.
Và phần tìm hiểu chính là phần thực hiện yêu cầu của đề tài, cụ thể là về phương diện
tính toán trong những thuật toán và thể hiện trực quan bằng đồ hoạ máy tính trên ngôn
ngữ Visual C++.
KĨ THUẬT ĐỒ HỌA Trang 3
Đề tài: Thiết kế hệ thống kiểm tra các quan hệ hình học trong 3D
Trong Visual C++ phần đồ họa được thể hiện trong lớp CDC (Class Device Context)
với nhiều hàm thành viên hỗ trợ cho việc vẽ điểm, đường, đa giác, tô màu…. Đặc biệt
hơn trong ngôn ngữ Visual C++ có sự hỗ trợ cho việc vẽ các đối tượng hình học bằng
chuột. Nhưng ngôn ngữ chỉ thực hiện được với các đối tượng hình học 2D, đối tượng
hình học 3D thì chưa có, cần phải tự thiết kế.
Trong quá trình nghiên cứu, chúng em nhận thấy trong ngôn ngữ Visual C++ có bộ
KĨ THUẬT ĐỒ HỌA Trang 4
Đề tài: Thiết kế hệ thống kiểm tra các quan hệ hình học trong 3D
Để thể hiện tọa độ một điểm trong hệ trục tọa độ hai chiều, Visual C++ dùng lớp CPoint,
đối tượng thuộc lớp này được thể hiện bởi hai thành phần x và y. Ví dụ ta khai báo điểm
point như sau:
CPoint point
point.x=100;
point.y=100;
Vẽ đường thẳng:
Line (int x1, int y1, int x2, int y2);
Hàm này thuộc lớp CClientDC
Ví dụ: Để vẽ đường thẳng ta thực hiện các bước sau đây
CClientDC dc(this);
dc.Line(x1,y1,x2,y2);
Ngoài ra trong việc vẽ đường thẳng còn có thể sử dụng hai hàm sau:
MoveTo(int x, int y);
Hàm này dùng để di chuyển con trỏ đến tọa độ x,y trong màn hình.
LineTo(int x, int y);
Hàm này dùng để vẽ đường thẳng từ điểm hiện hành đến điểm x, y.
Cả hai hàm này đều thuộc lớp CClientDC, việc sử dụng như sau:
CClientDC dc(this);
dc.MoveTo(x,y);
dc.LineTo(newx, newy);
Vẽ hình chữ nhật:
Rectangle(int x1,int y1,int x2,int y2);
Hàm này thuộc lớp CclientDC. Dùng để vẽ hình chữ nhật có tọa độ trên góc trên trái là
(x1,y1) và tọa độ góc dưới phải là (x2,y2). Cú pháp vẽ hình chữ nhật như sau:
CClientDC dc(this);
dc.Rectangle(x1, y1, x2, y2);
Vẽ hình Ellipse:
• Tham số color cho màu vẽ
b) Các hàm trong bộ thư viện OpenGL
OpenGL gồm 5 bộ hàm, bộ hạt nhân có 115 hàm cơ bản. Tên các hàm này bắt đầu
bằng GL. Windows NT hỗ trợ 4 chủng loại hàm khác, bao gồm thư viện OpenGL
utility(tên hàm bắt đầu bằng GLU), thư viện OpenGL auxiliary(tên hàm bắt đầu bằng
AUX), bộ hàm”WGL” (tên hàm bắt đầu bằng WGL), và các hàm WIN32 API (tên hàm
không có tiền tố đặc biệt). Bộ hàm hạt nhân cho phép thiết kế các hình dạng khác nhau,
tạo các hiệu quả chiếu sáng, kết hợp antialiasing và gán cấu trúc, thực hiện biến đổi ma
trận…
Do các hàm cơ bản được thể hiện ở nhiều dạng khác nhau tùy thuộc vào loại dữ liệu
mà chúng tiếp nhận, nên trên thực tế có hơn 300 nguyên mẫu (prototype) các hàm cơ bản.
Thư viện OpenGL utility gồm các hàm cao cấp. Các hàm này đơn giản hoá
việc sử dụng hình ảnh cấu trúc, thực hiện việc biến đổi tọa độ mức cao, hỗ trợ tesselation
đa giác, và biểu diễn các đối tượng có cơ sở đa giác như hình cầu, hình trụ hình dĩa.
KĨ THUẬT ĐỒ HỌA Trang 6
Đề tài: Thiết kế hệ thống kiểm tra các quan hệ hình học trong 3D
Thư viện OpenGl auxiliary gồm các hàm đặc biệt dùng đơn giản hóa các ví dụ
lập trình trong sách chỉ dẫn lập trình OpenGL. Các hàm phụ thuộc platform này thực hiện
các nhiệm vụ như quản ký cửa sổ, điều khiển xuất/nhập, vẽ các đối tượng 3D nhất định.
Do các hàm này có mực đích thiết minh nên không được dùng trong các mã sản xuất.
Các hàm “WGL”kết nối OpenGL với WINdows NT, cho phép người lập trình
xây dựng và chọn lựa các ngữ cảnh biểu diễn, tạo các bitmap font, các hàm này chỉ dùng
trên Windows NT.
Cuối cùng, các hàm Win32 API được dùng giải quyết các định dạng điểm ảnh
và tạo bộ đệm đôi.
Trong phần này, tôi trình bày một số hàm được sử dụng trong đề tài.
Hàm vẽ điểm, đường, đa giác:
Được bắt đầu bởi hàm:
glBegin (Glenum mode)
Để chỉ sự bắt đầu những đỉnh của một primitive, tham số mode chỉ kiểu các primitive.
Các hàm liên quan đến màu:
• glColor3f (Glfloat red, Glfloat green, Glfloat blue); đặt màu hiện hành bởi các
thành phần red, green, blue với giá trị từ 0,0 đến 1,0.
• glClearColor(GLclampf red, GLclamp green, Glclamp blue, Glclamp alpha); đặt
màu cho việc xóa buffer màu.
• glClear(GL_COLOR_BUFFER_BIT); xóa buffer màu, xóa cửa sổ bởi màu xóa
hiện hành .
Các hàm liên quan đến ánh sáng:
• glLightf(Glenum light, Glenum pname, GLfloat param);
• glLighti(Glenum light, Glenum pname, GLint param);
Trong đó:
Tham số light chỉ ra nguồn sáng có giá trị từ GL_LIGHT0 đến GL_LIGHT7.
Tham số pname chỉ ra tham số light nào được lập như GL_AMBIENT,
GL_DIFFUSE…
Tham số param chỉ có ý nghĩa đối với nguồn sáng điểm. Tham số này có các
giá trị như: GL_SPOT_EXPONENT, GL_SPOT_CUTOFF…
Các hàm liên quan đến thuộc tính ánh sáng của vật liệu:
• glColorMaterialf(Glenum face,Glenum pname, GL float param);
• glMateriali(Glenum face,Glenum pname, GL int param);
• glMaterialfi(Glenum face,Glenum pname, const Glint* params);
• glMaterialfi(Glenum face,Glenum pname, const Glint* params);
Trong đó:
face: là thuộc tính bề mặt trước ,sau của đa giác.
pname: là thuộc tính của vật liệu: GL_AMBIENT,GL_DIFFUSE,…
param : chỉ định giá trị mà tham số pname được lập.
params: chỉ định dãy số nguyên hay thực chứa các thành phần thuộc tính được
lập.
• glFrontFace(Glenum mode); xác định bề mặt đa giác là mặt trước hay sau.
KĨ THUẬT ĐỒ HỌA Trang 8
Đề tài: Thiết kế hệ thống kiểm tra các quan hệ hình học trong 3D
thứ tự a=(a
x
, a
y
). Trong chương trình, vector được biểu diễn bằng kiểu dữ liệu:
Typedef struct
{
dx,dy: float;
} vector;
struct
{
dx,dy,dz : float;
KĨ THUẬT ĐỒ HỌA Trang 10
b
a+b
a
a+b
b
a
Đề tài: Thiết kế hệ thống kiểm tra các quan hệ hình học trong 3D
} vector3D
Với hai điểm P
1
(x
1
,y
1
) và P
2
x
, P
y
) được gọi là vector vị trí cho P. Vector 3D cũng
rất quan trọng trong đồ họa.
2. Các phép tính vector:
Một vector n chiều, với n là số nguyên dương bất kỳ:
W=(W1,W2,. . .,Wn)
với mỗi thành phần Wi là số vô hướng.
Các vector 2 chiều và 3 chiều với n=2, n=3 thì thường gặp nhất trong đồ hoạ, chúng ta
không thể thấy được các vector lớn hơn 3 nhưng chúng là những thành phần có giá trị rất
lớn.
Hai phép tính số học cơ bản trên vector là cộng hai vector và định tỷ lệ một vector.
Cộng hai vector
Tổng hai vector a,b là vector c được định nghĩa như sau:
C = (c
1
, c
2
, …, c
n
) = (a
1
+ b
1
, a
2
+ b
2
, …, a
c.dx := a.dx + b.dx;
c.dy := a.dy + b.dy;
}
Định tỷ lệ một vector
Việc định tỷ lệ một vector nhằm thay đổi độ dài của hay đảo chiều của nó.
sa = (sa
1
, sa
2
, …, sa
n
)
Với s là hệ số tỷ lệ và a là vector. Khi s âm, chiều của s ngược lại với a.
Procedure Scalar(real s; vector a; vector &b)
{
b.d
x
= s
∗
a.d
x
;
b.d
y
= s
y
a.d
y
;
}
a
= a / | a|
và có cùng chiều với a.
Biểu thức cho hệ số của vector có thể khai báo trực tiếp như sau:
Normalize(vector v, vector &u);
Nó có dạng vector đơn vị u do các hệ số mỗi thành phần của v:
u.d
x
:= v.d
x
/Length(v);
u.d
y
:= v.d
y
/Length(v);
Tổ hợp tuyến tính của vector:
Để hình thành tổ hợp tuyến tính của hai vector V và W, định tỷ lệ mỗi vector theo các
tỷ số a và b rồi cộng kết qủa để thành vector mới av+bw.
Tổng quát, tổ hợp tuyến tính của m vector V
1
, V
2
, …, V
m
như sau:
W = a
1
V
1
m
là tổ hợp lồi nếu tổng
∑
i
a
=1và a
i
≥
0, và cung “spline” thực ra là tổ hợp lồi của
một tập các vector.
Tích vô hướng của hai vector:
Tích vô hướng của hai vector cho ta thông tin đáng giá về một cặp vector như góc giữa
chúng (cụ thể là khi nào chúng vuông góc) và chiếu vector lên vector khác. Nó cũng cho
ta phương trình của một mặt phẳng mô tả bằng một điểm và hai vector.
Cho hai vector, ví dụ hai chiều (a
1
,a
2
) và (b
1
,b
2
).
Tích vô hướng hai vector định nghĩa là:
a.b = a
1
b
1
+ a
2
+ a.d
y
* b.d
y
;
}
• Các tính chất của tích vô hướng
1. Đối xứng : a.b = b.a
2. Tuyến tính: (a+c).b = a.b + c.b
3. Đồng nhất : (sa).b = s(a.b)
4. | b
2
| = b.b
KĨ THUẬT ĐỒ HỌA Trang 14
Đề tài: Thiết kế hệ thống kiểm tra các quan hệ hình học trong 3D
Độ dài của hiệu và tổng hai vector được cho như sau:
|a - b|
2
= |a|
2
- 2ab + |b|
2
|a + b|
2
= |a|
2 +
2ab + |b|
2
Các ứng dụng của tích vô hướng:
Ta biết rằng
cos(
ϕ
) >0 nếu
ϕ
< 90
0
cos(
ϕ
) <0 nếu
ϕ
> 90
0
cos(
ϕ
) =0 nếu
ϕ
= 0
Do vậy từ phương trình:
cos(
ϕ
) = u
a
.u
b
KĨ THUẬT ĐỒ HỌA Trang 15
a
b
Hình trên ta phân tích a thành c theo chiều vector b và e. Theo cách này vector c
gọi là chiếu trực giao của a lên b. Rõ ràng c có cùng chiều với b, ta còn phải tính độ lớn |
c|.
Theo phương trình a.b = |a||b|cos(
ϕ
) và hệ thức lượng tam giác ta có
phương trình:
|c| = |a|
( )
ba
ba.
= a.u
b
(*)
Như thế độ dài của c chỉ phụ thuộc vào độ dài của a. Bây giờ ta hình thành vector
c, bằng cách thêm chiều của b.
c = |c|.u
b
Sau đó, kết hợp với phương trình (*) trên ta có:
c = ( a.u
b
)u
b
c =
a.b
b
|b|
đường thẳng vẫn phụ thuộc vào gốc không có gì thay đổi. Như vậy ta có:
n.r = D Với D = n.a = n
x
Ax + n
y
Ay
Đây là phương trình điểm chuẩn cho đường. Phương trình này có thể viết dạng quen
thuộc như sau:
n
x
x + n
y
y = D
• Mở rộng dạng điểm cho mặt phẳng
Các mặt phẳng cũng có thể biểu diễn ở dạng chuẩn điểm. Một mặt phẳng hoàn
toàn được xác định với một điểm S = (s
x
, s
y
, s
z
) nằm trong đó và hướng chuẩn của mặt
phẳng. Chuẩn cho mặt phẳng được hiểu là vuông góc với mọi đường trong mặt phẳng.
Gọi hướng chuẩn là n= (n
x
, n
y
, n
z
). Với điểm R= (x, y, z) bất kỳ trong mặt phẳng, xây
. Điều này cho thấy (A, B, C) là chiều chuẩn của mặt
phẳng.
Điểm trên mặt gần gốc nhất là điểm chiếu vuông góc của gốc lên mặt. Như vậy nó tỉ lệ
với n, gọi là Kn, nên khoảng cách là| Kn |. Vì Kn nằm trên mặt nên n. (Kn)=D.
d. Kiểm tra nửa không gian trong và ngoài của một điểm
Xét điểm Q, giả sử đường E đi qua điểm A và có chuẩn hướng ra n như hình vẽ:
Góc
ϕ
giữa n và Q -A < 90
0
, nếu Q nằm phía ngoài, vì vậy tích n.(Q - A) > 0.
Tương tự, góc
ϕ
sẽ lớn hơn 90
0
nếu Q nằm phía trong, vì vậy n.(Q -A) < 0. Cuối cùng,
ϕ
= 90
0
nếu Q nằm trên E, và n .(Q - A) = 0. Nếu thay Q -A bằng vector q - a và gọi đặt
KĨ THUẬT ĐỒ HỌA Trang 18
S
n
ϕ
n
E
A
inside
E
Đề tài: Thiết kế hệ thống kiểm tra các quan hệ hình học trong 3D
w
L
P
P
2
Copyright: Tài liệu đại học ©