Luận văn Thiết kế hệ thống kiểm tra các quan hệ hình học trong không gian 2D và 3D

III.1. CÁC QUAN HỆ HÌNH HỌC TRONG MẶT PHẲNG (2D) Tính góc giữa hai đường thẳng Cơ sở tốn học: Đây là ứng dụng quan trọng của tích vô hướng. Hình a dưới cho thấy góc q giữa hai vector a và b. Chúng tạo thành hai cạnh của tam giác, và cạnh thứ ba là a-b. b a a-b Từ định nghĩa tích vô hướng của vector ø và là a.b= |a||b| cos( ) với q :góc giữa vector a và vector b Và từ biểu thức giải tích của tích vô hướng: a.b = a b+ a b Ta có cos() = a.b / |a||b|=/ Cos() dương nếu || nhỏ hơn 90o, và âm nếu || lớn hơn 90o. Giải thuật: - Tính vector chỉ phương a và b của 2 đoạn thẳng - Tính vector vô hướng a.b - Cos ()= a.b / |a| |b| - Góc 2 đoạn thẳng Alpha= arcos(cos()) Tìm hình chiếu của đoạn thẳng AB lên đường thẳng b Cơ sở tốn học: Để tính hình chiếu đoạn AB lên đường thẳng b đi qua C và D, ta tìm hình chiếu của điểm A là A’ và B là B’ trên đường thẳng b. Đoạn A’B’ chính là hình chiếu của AB trên đường b. A B B’ A’ C D (b) · Xác định PT đi qua 2 điểm C, D: ax + by + c = 0 có vector chỉ phương VCF = (xD-xC , yD-yC ) = (-b, a) và c = - a * xC - b * yC. · Xác định PT đường thẳng D đi qua điểm A và vuông góc với CD: bx -ay + c’ = 0 có vector chỉ phương của D =(a, b) và c’= b*xA + a*yA · Tính giao điểm A’(xA’, yA’) của hệ PT (1) và (2) ax + by + c = 0 (1) bx - ay + c’= 0 (2) xA’= (-c’*b + c*a) / ( a*a + b*b) yA’= ( -c*b + c’*a) / ( a*a + b*b) · Tương tự tính B’ là giao điểm của: . Phương trình đường thẳng đi qua CD . Và Phương trình đường thẳng D’ đi qua B và vuông góc với CD Giải thuật: - Tìm vector chỉ phương VCF (-b, a) của phương trình đường thẳng qua hai diểm C, D: ax + by + c =0 - Tính hệ số c. - Tính c1 của phương trình D1 đi qua điểm A và vuông góc với CD: bx - ay + c1 = 0 - Tìm giao điểm A’của đường D1 và đường qua C, D . - Tìm giao điểm B’ của đường D2 đi qua điểm B và vuông góc với đường thẳng CD. - Khi đó A’B’ chính là hình chiếu của AB. Xác định giao điểm giữa hai đoạn thẳng Cơ sở tốn học: Cho hai đoạn thẳng, xác định chúng có cắt nhau không, nếu có tìm giao điểm.Giả sử đường 1 từ a đến b và đường 2 từ c đến d như trong hình vẽ, hai đoạn thẳng có thể bố trí theo nhiều cách khác nhau. a b c d d c b a b a d c a b c d 1 2 Phương trình tham số cho mỗi đường như sau: (1) (2) x1 (t) = ax + (bx - ax) * t y1 (t) = ay + (by - ay) * t và x2 (u) = cx + (dx - cx) * u y2 (u) = cy + (dy - cy) * u Ta gọi các đường thẳng chứa các đoạn thẳng ab và cd là các đường cha, đây là các đường vô hạn. Trước hết, ta xét hai đường “cha” có giao nhau không, sau đó xem giao điểm có thuộc cả hai đoạn thẳng không? Nếu các đường “cha’ giao nhau, ta có giá trị to và uo sao cho: x1 (to) = x2(uo) và y1(to) =y2(uo) Từ đây, ta có các phương trình sau: (3) (4) (5) ax + (bx - ax) * to = cx + (dx - cx ) * uo ay + (by - ay) * to = cy + (dy - cy ) * uo Khử uo, ta được: D* to = (cx - ax) * (dy - cy ) - (cy - ay) * (dx - cx) với D = (bx - ax) * (dy - cy) - ( by - ay) * (dx - cx) Có hai trường hợp cơ bản, D bằng hay khác 0. D khác zero Nếu D khác 0, ta tính to từ phương trình (4). Nếu to nằm ngồi đoạn [0, 1] thì không có giao điểm giữa hai đoạn. Ngược lại, thì có thể có giao điểm, thay to vào (3) để tính uo. Nếu uo nằm trong đoạn [0, 1] thì chắc chắn có giao điểm, và dùng phương trình (1) và (2) để tính. D bằng zero (6) Nếu D bằng 0, từ phương trình (5) suy ra: (dy - cy) / (dx - cx) = (by - ay) / (bx - ax) (7) Nghĩa là các hệ số góc bằng nhau, nên các đường cha song song. Nếu các đường cha trùng nhau thì các đoạn cũng có thể trùng nhau. Để kiểm điều này, ta xem c có nằm trên đường cha đi qua a và b không. Dựa vào phương trình của đường cha là: (bx - ax) * (y - ay) - (by - ay) * (x - ax) = 0 thay cx cho x và cy cho y và xem vế trái có đủ gần 0 không (nghĩa là: nhỏ hơn lượng nào đó, như 10 - 5). Nếu không, các đường cha không trùng nhau, và không có giao điểm. Nếu thỏa mãn thì phải thực hiện bước kiểm cuối cùng để xem các đoạn có trùng nhau không. Từ phương trình (1) tìm hai giá trị tc và td mà đường đạt tới vị trí c và d. Vì các đường cha trùng nhau, ta chỉ cần dùng thành phần x (nếu đường 1 thẳng đứng, thì dùng thành phần y), và thay cx và dx, ta có : (8) tc = (cx - ax) / (bx - ax) td = (dx - ax) / (bx - ax) Đường 1 bắt đầu tại 0 và kết thúc tại 1, và xét thứ tự của bốn giá trị 0, 1, tc và td, ta xác định được vị trí tương đối của hai đường. Sẽ chồng nhau trừ khi cả hai tc và td nhỏ hơn 0 hay lớn hơn 1. Nếu có trùng nhau, ta dễ dàng xác định các điểm đầu trùng nhau từ tc và td. Giải thuật được xây dựng trong thủ tục Intersect (), gồm các tham số là bốn điểm đầu của các đường, giá trị trả về có thể có thể có các giá trị sau: 1: có một giao điểm. 2: không giao nhau. 3: các đoạn thẳng song song nhau. 4: hai đoạn thẳng chồng nhau. 5: hai đoạn thẳng cùng nằm trên 1 đường thẳng, không cắt nhau. Giải thuật: -Tính Mẫu số D; -Nếu D 0 . Tính to,uo; . Nếu to thuộc [0,1] và uo thuộc [0,1] + Tính giao điểm M + Return 1; ( 2 đoạn thẳng cắt nhau tại M) Ngược lại Return 2; (2 doạn thẳng không cắt nhau) - Ngược lại, . Nếu c nằm trên đoạn ab + Tính tc, td; + Nếu không phải cả tc và td 1 Return 4; (2 doạn thẳng chồng nhau) + Ngược lại, Return 5; (2đoạn thẳng nằm trên 1 đường thẳng và không cắt nhau) . Ngược lại, Return 3; (2 đoạn thẳng song song ) Vẽ đa giác (Polygon) Cơ sở tốn học: Đa giác là tập hợp các đoạn thẳng liên tiếp cùng nằm trong mặt phẳng khép kín. Một đa giác có ít nhất 3 cạnh. Như vậy, đa giác đơn giản nhất là tam giác. Giải thuật: - Xuất phát từ đỉnh đầu tiên - Vẽ nối đến đỉnh kế tiếp theo thứ tự cùng chiều kim đồng hồ. - Vẽ nối từ đỉnh cuối cùng đến đỉnh đầu tiên. Vẽ n-giác Cơ sở tốn học: Một n-giác là đa giác quy tắc có N cạnh (đa giác quy tắc: đa giác mà mọi cạnh có độ dài bằng nhau, và các cạnh kề nhau tạo nên những góc trong bằng nhau). Nếu cho đỉnh đầu tiên trên trục x tại (R, x). Cho góc A bất kỳ, vị trí (x,y) của một điểm trên đường tròn có góc A sẽ được tính (x,y) = (R cos(A), R sin(A)). Và đỉnh thứ i, V, của n -giác nằm ở góc 2p (i -1) / N và có vị trí: V = ( R cos(2p (i -1) / N ), R sin(2p (i -1) / N) ). Giải thuật: - Số đỉnh = N - Định góc A = 2 Pi / N - Vòng lặp xác định đỉnh thứ i . Góc = i *A; . Tìm tọa độ đỉnh V. Tô màu đa giác Cơ sở tốn học: Phương pháp hiển thị các vùng được tô màu trong đồ họa máy tính là quá trình xác định các pixel tương ứng thuộc vùng tô màu cho nó. Có nhiều thuật tốn đã được nghiên cứu và phát triển cho việc hiển thị các vùng được tô màu trên màn hình, một trong những thuật tốn đó là tô màu theo vết dầu loang, một thuật tốn khác là tô màu theo dòng quét. Ở đây ta dùng phương pháp tô màu theo dòng quét (scan-line algorithm) hay còn gọi là giải thuật tô màu chẵn lẻ (odd - even algorithm). Thuật giải này sử dụng các giao điểm giữa các đường biên của vùng cần tô với các đường thẳng gọi là dòng quét và xác định các pixel nào nằm trong vùng tô màu giữa hai giao điểm liên tiếp, đó chính là các pixel dọc theo đường quét nằm giữa hai giao điểm và nằm bên trong đa giác. Ở mỗi điểm giao dòng quét chuyển đổi hoặc đi vào hoặc đi ra khỏi đa giác, đó là sự thay đổi parity của điểm đó. Nếu dòng quét đi vào trong đa giác những pixels tiếp theo sẽ được tô, nếu đi ra ngồi những pixels tiếp theo sẽ không được tô. Khi dòng quét đi qua một đỉnh P của đa giác (chính là giao điểm của 2 cạnh của đa giác) nó tạo ra 2 giao điểm, mỗi điểm với 1 cạnh của đa giác đi qua đỉnh đó, nếu đỉnh ở giá trị cực (local extremum) Pixels ở bên trái và bên phải của đỉnh đó sẽ có cùng parity, nhưng nếu đỉnh không ở giá trị cực các Pixels ở bên trái và bên phải của đỉnh đó sẽ có parity ngược nhau, do đó ta cần có một xử lý đặc biệt hơn. 1 2, 3 1 4 2 Scan line 1 Scan Line 2 Ÿ Nếu P là giao điểm của hai cạnh có hướng y ngược nhau (một cạnh có giá trị y tăng,một cạnh có giá trị y giảm - Scan Line 1) thì dòng quét có 2 điểm giao. Ÿ Nếu P là giao điểm của hai cạnh có hướng y trùng nhau (hai cạnh đều có giá trị y cùng tăng hay giảm - Scan Line 2) thì dòng quét có 1 điểm giao. Trước khi tô màu, ta cần kiểm tra mỗi đỉnh đa giác. Nếu y của nó không là giá trị cực trị(local extremum), như trong scan line 2. Vì những Pixels đối với bên trái và phải của đỉnh đó khác parity, khác giá trị kiểm tra inside-outside; ta phải làm ngắn một trong hai cạnh đi một chút (giảm y của đầu cạnh đó một pixel). Đối với cạnh nằm ngang trong đa giác không cần đưa vào tập các cạnh của đa giác để xử lý. Giải thuật: Bước 1: Xác định Frame “bao” đa giác. Frame bao đa giác là hình chữ nhật nhỏ nhất chứa tồn bộ đa giác. Để xác định hình chữ nhật này ta lấy min hoặc max các tọa độ đỉnh của đa giác trong hệ tọa độ Descartes rồi tăng, hoặc giảm 1 để đảm bảo hình chữ nhật là hình bao và đa giác hồn tồn nằm trong nó. Bước 2: Xác định danh sách các cạnh đa giác để xử lý. Lần lượt duyệt tất cả cạnh của đa giác: · Không đưa cạnh nằm ngang của đa giác vào danh sách. · Kiểm tra 2 cạnh đa giác liên tiếp, nếu đỉnh chung không là điểm cực trị (local extremum), làm ngắn đầu cạnh của một cạnh đi qua đỉnh chung một pixel. Bước 3: Tiến hành tô màu. Tiến hành các đường quét ngang tư ø Ymin + 1 đến Ymax - 1. · Ứng với một đường quét ngang yi nào đó, ta xác định các điểm cắt (bằng giải thuật tìm giao điểm giữa hai đoạn thẳng đã có), giữa các đường quét ngang với tất cả các cạnh của đa giác. Vì tung độ y của điểm cắt bằng yi nên ta chỉ cần đưa các hồnh độ xi của điểm cắt vào một danh sách. · Sắp xếp lại danh sách sao cho các giá trị xi tăng dần. · Duyệt qua các điểm cắt và đếm số điểm cắt đã duyệt. · Nếu điểm cắt trùng với đỉnh của đa giác: Nếu có một cạnh song song với đường quét thì đỉnh trước đếm tăng và đỉnh sau không đếm tăng. · Tô màu giữa các cặp giao điểm . Bước 4: Lập lại bước hai cho đến khi yi = ymax. Bước 5: Vẽ lại đa giác bằng màu đã tô. Lưu ý: Nếu đa giác không phải là đa giác đơn thì giải thuật này không vận dụng được. Điểm bên trong / bên ngồi đa giác Cơ sở tốn học: Giải thuật này nhằm xác định một điểm cho trước có nằm bên trong một đa giác đơn phẳng hay không. Giải thuật xây dựng dựa trên định lý mang tên JORDAN sau đây: “Mỗi đường cong, kín, đơn, phẳng, một chiều, phân hoạch mặt phẳng thành hai miền, một trong hai miền đó hồn tồn chứa những đường thẳng nào đó, miền còn lại thì không có tính chất đó”. Trong định lý trên đây một trong hai miền sẽ được gọi là miền trong (gồm bản thân đường cong và phần mặt phẳng giới nội bởi đường cong). Không thuộc miền trong gọi là miền ngồi. Định lý này vẫn đúng cho trường hợp đa giác đơn phẳng một chiều như là một trường hợp riêng. Từ định lý này dẫn đến hệ quả sau: “Từ một điểm P bất kỳ, vẽ một tia chỉ cắt đa giác ở những điểm trong của các cạnh (nghĩa là : không đi qua đỉnh nào của đa giác); nếu số giao điểm là lẻ thì P là điểm trong, nếu số giao điểm là chẵn thì P là điểm ngồi”. Về mặt kỹ thuật mọi đường cong đơn, phẳng, kín, liên thông, không tự cắt đều có thể tiếp cận tuyến tính bằng một đa giác bao gồm một số hữu hạn các cạnh liên tiếp. Vì vậy cho phép xây dựng một giải thuật test quan hệ trong/ ngồi chỉ bằng cách xét số giao điểm của tia có gốc là điểm cần xét. Giải thuật: - Chọn Px là nửa đường thẳng xuất phát từ P song song với trục Ox, hướng về phía x>0. Lấy P=(x,y). - P là điểm cần xét. - Nếu (P là một đỉnh) hoặc (P thuộc trong một cạnh) thì Return (P điểm trong) - Ngược lại, xác định giao điểm Px với các cạnh đa giác { . Ci là cạnh Pi Pi+1 của đa giác . Nếu y = yi thì xét hai cạnh có một đầu là Pi (1) .. Nếu cả hai đầu kia ở một phía của Pi thì tính Px cắt cả hai cạnh . Ngược lại (1) Nếu y > Max(yi,yi+1) hay y<Min(yi,yi+1) (2) Thì Px không cắt cạnh Ci . Ngược lại (2) .. Nếu x <= Min (xi,xi+1) (3) Thì Py cắt cạnh Ci . Ngược lại (3) .. Xét tọa độ giao điểm (yo,xo) của Px với cạnh Ci Nếu x >= xo thì Px không cắt Ci } - Nếu số giao điểm lẻ . Return P thuộc đa giác. Kiểm tra quan hệ giữa đoạn thẳng và đa giác Các chương trình ứng dụng mô tả các hình ảnh bằng hệ tọa độ thế giới thực, có thể là bất kỳ hệ tọa độ Descartes nào mà người dùng cảm thấy thuận tiện nhất. Các hình ảnh được mô tả trong hệ tọa độ thực sau đó sẽ được các hệ độ họa ánh xạ vào các hệ tọa độ thiết bị. Thông thường, các hệ đồ họa cho phép người dùng xác định một vùng nào đó của hình ảnh được hiển thị và nó sẽ hiển thị ở đâu trên màn hình (viewport). Ta có thể chọn một vùng hay nhiều vùng để hiển thị, các vùng này có thể đặt ở các nơi khác nhau hay lồng vào nhau trên màn hình. Quá trình này đòi hỏi nhiều thao tác như dịch chuyển, biến đổi tỷ lệ để đưa vào bên trong viewport hoặc đơn giản là loại bỏ các phần hình ảnh nằm ngồi vùng đang được xét. Thao tác cuối cùng và cũng được sử dụng nhiều nhất còn được gọi là clipping. Trong thuật ngữ thông thường Viewport được hiểu như một window (hình chữ nhật) theo đó hình ảnh được clipping. Tuy nhiên Viewport cũng có thể là một đa giác bất kỳ. Bài tốn clipping sau đây được xét cho trường hợp tổng quát hơn: clipping với đa giác đơn bất kì (cho cả hai trường hợp đa giác lồi hoặc lõm). Cơ sở tốn học và giải thuật: Các bước tiến hành clipping đoạn thẳng AB bằng một đa giác đơn, phẳng bất kì như sau: Bước 1: Hốn đổi A, B để xA < xB. Nếu xA = xB . Hốn đổi A,B để yA < yB Bước 2: Kiểm tra tính trong ngồi của A và B đối với đa giác (Dùng giải thuật kiểm tra điểm bên trong/ngồi đa giác ) Bước 3: Tìm giao điểm của AB với đa giác (Dùng giải thuật xác định giao điểm của 2 đoạn đã có ) Nếu có giao điểm thì { - Đưa các tọa độ của các điểm cắt vào một danh sách - Sắp xếp cho hồnh độ các giao điểm tăng dần (Nếu xA = xB sắp xếp theo tung độ) } Bước 4: Thực hiện clipping. - Nếu A và B đều nằm trong đa giác thì (1) Nếu số điểm cắt = 0, Return (AB nằm hồn tồn trong đa giác) - Ngược lại { . Đoạn thẳng từ A đến điểm cắt thứ 1 thuộc đa giác. . i = 1 . Lặp lại . Tìm trung điểm của đoạn thẳng nối hai điểm cắt kế tiếp nhau. . Kiểm tra trong /ngồi đối với trung điểm. . Nếu trung điểm nằm trong đa giác thì Return (Đoạn thẳng thuộc đa giác) . Ngược lại, Return (Đoạn thẳng không thuộc đa giác). . Inc (i,1) Cho đến khi i = số điểm cắt } - Ngược lại, có điểm A hay B nằm ngồi đa giác (1) - Nếu số điểm cắt = 0, Return (Đoạn AB nằm ngồi đa giác). - Nếu số điểm cắt 0 thì { . Thêm tọa độ điểm A vào đầu danh sách . Thêm tọa độ điểm B vào cuối danh sách . i = 1 . Lặp lại . Tìm trung điểm của đoạn thẳng nối hai điểm cắt kế tiếp nhau . Kiểm tra trong/ ngồi đối với trung điểm. . Nếu trung điểm nằm trong đa giác thì Return (Đoạn thẳng thuộc đa giác) . Ngược lại, Return (Đoạn thẳng không thuộc đa giác) . inc (i,1) Cho đến khi hết danh sách } Ngược lại, Return (Đoạn thẳng không thuộc đa giác). Bước 5: Vẽ lại các đoạn thẳng thuộc đa giác * Mở rộng: Giải thuật có thể được mở rộng cho việc clipping một đa giác bằng cách thực hiện clipping tất cả các cạnh của đa giác. Kiểm tra quan hệ hai đa giác Cơ sở tốn học: Giải thuật này cho phép clip bất kỳ một đa giác vào 1 đa giác. Nó cũng cho phép hình thành sự giao, hội của 2 đa giác.Chúng ta bắt đầu bằng ví dụ minh họa trong hình sau. Ta liệt kê những đỉnh theo thứ tự từ trái sang phải, theo chiều kim đồng hồ. D 6 5 4 3 2 1 d c b a C B A Hai đa giác SUBJ và CLIP được thể hiện bằng 2 danh sách (a,b,c,d) và (A,B,C,D) tương ứng. Tất cả điểm giao của 2 danh sách sẽ được xác định và lưu vào danh sách (theo thứ tự sang phải của mỗi cạnh). Dựa vào hình vẽ trên, ta có: SUBJ_LIST: a, 1, b, 2, c, 3, 4, d, 5, 6 CLIP_LIST: A, 6 ,3 , 2, B, C, D, 4, 5 Duyệt SUBJ theo hướng đi tới cho tới khi tìm được 1 điểm giao đi vào (entering intersection), là điểm giao mà SUBJ di chuyển từ ngồi vào trong đa giác CLIP.Và đưa điểm này vào danh sách xuất đa giác được clip. Duyệt SUBJ tới khi gặp 1điểm giao khác. Nhảy ra khỏi SUBJ và di chuyển theo CLIP thay vì SUBJ. Duyệt CLIP theo hướng đi tới. Tới khi gặp một điểm giao, nhảy ra khỏi CLIP và duyệt theo SUBJ theo hướng đi tới, và cứ tiếp tục như vậy. Mỗi đỉnh hoặc mỗi điểm giao gặp phải khi duyệt sẽ được đưa vào danh sách xuất đa giác được clip. Lặp lại tiến trình trên giữa 2 đa giác, duyệt mỗi đa giác theo hướng đi tới cho tới khi đỉnh đầu tiên được gặp lại. Danh sách xuất ra ở thời điểm này (1,b,2,B) 1 b 2 3 4 d 5 6 a a restart start SUBJ_LIST: SUBJ_LIST: A 6 3 2 B 1 C D 4 5 Bây giờ, ta kiểm tra một điểm giao“entering” khác của SUBJ. Và sẽ tạo ra danh sách xuất (3,4,5,6). Việc kiểm tra những điểm giao “entering” khác sẽ chỉ ra là tất cả chúng đã được duyệt, quá trình chấm dứt. Cách thức để hiện thực quá trình xử lý này là xây dựng hai danh sách SUBJ_LIST: a, 1, b, 2, c, 3, 4, d, 5, 6 CLIP_LIST : A, 6, 3, 2, B,1, C, D, 4 , 5 Mà trong đo,ù việc duyệt mỗi đa giác và liệt kê những đỉnh và điểm giao phải theo thứ tự được gặp. Giải thuật: -Bước 1: Tạo danh sách SUBJ_LIST Duyệt lần lượt mỗi cạnh đa giác SUBJ theo thứ tự cùng chiều kim đồng hồ { - Tìm các điểm cắt của cạnh Pi-Pi+1 với đa giác CLIP. - Sắp xếp danh sách điểm cắt theo hồnh độ tăng dần . Nếu hồnh độ Pi.x=Pi+1.x thì sắp xếp theo tung độ. - Đưa đỉnh Pi vào danh sách SUBJ_LIST - Đưa các điểm cắt từ danh sách điểm cắt vào SUBJ_LIST theo hướng đi từ Pi tới Pi+1 } -Bước 2: Tạo danh sách CLIP_LIST Duyệt lần lượt mỗi cạnh đa giác CLIP theo thứ tự cùng chiều kim đồng hồ { - Tìm các điểm cắt của cạnh Pi- Pi+1 với đa giác SUBJ. - Sắp xếp danh sách điểm cắt theo hồnh độ tăng dần. Nếu hồnh độ Pi.x=Pi+1.x sắp xếp theo tung độ. - Đưa đỉnh Pi vào danh sách CLIP_LIST. - Đưa các điểm cắt từ danh sách điểm cắt vào CLIP_LIST theo hướng đi từ Pi tới Pi+1. } -Bước 3: Duyệt danh sách SUBJ_LIST và CLIP_LIST. Vòng lặp (1) Vòng lặp (2) - Tìm điểm giao “entering” chưa duyệt của SUBJ_LIST. - Duyệt trên SUBJ_LIST tới khi thấy điểm giao tiếp theo . - Chuyển sang duyệt trên CLIP_LIST tới khi thấy điểm giao tiếp theo. Cho tới khi điểm đầu tiên(điểm ‘entering’) được gặp lại. (vòng lặp 2 ) - Xuất Danh sách đa giác tìm được ở trên. Cho tới khi tất cả các điểm giao ‘entering’ đã được duyệt (vòng lặp 1) Kiểm tra tính lồi của đa giác Cơ sơ ûtốn học: -Nhận biết quay trái với quay phải: Có những thuật giải ta phải duyệt một đa giác, lần lượt thăm mỗi đỉnh hay cạnh. Ta xem như di chuyển theo một cạnh từ đỉnh này đến đỉnh kia và sau đó ra cạnh kế. Như vậy cần phải biết đi theo chiều phải hay trái. Ví dụ, nếu P1, P2, P3 là ba cạnh kề nhau của đa giác, ta tạo vector cạnh a=P2-P1 và b=P3- P2. Hình (1) cho thấy trường hợp a và b nằm trong mặt xy và quay trái khi đi từ a đến b. Còn hình (2) là quay phải. b a b a Hình 1 Hình 2 Giả sử dùng hệ tay phải ở hình 1 và hình 2 nên trục z (hay chiều k) hướng ra ngồi từ trang sách tới chúng ta. Dùng quy tắc tay phải, tích a x b chỉ ra ngồi với thành phần k dương. Nếu lập tích vô hướng vector này với chính k, sẽ được một đại lượng mà dấu của nó cho biết chiều quay, dương nếu quay trái và âm nếu quay phải. Cho vector a và b trong mặt xy, quay từ a đến b sẽ là dương nếu T= k.(a x b) >= 0 và âm nếu ngược lại (Kết quả không đổi đối với hệ tay trái). Với đa giác lồi, mọi phép quay có cùng chiều, như đa giác A. Nếu đa giác không lồi, như trường hợp B, gồm cả hai phép quay. Như vậy, đa giác đơn là lồi nếu và chỉ nếu mọi phép quay có có cùng dấu khi được duyệt. A B Giải thuật: - Duyệt đa giác theo thứ tự các đỉnh để xét việc quay từ cạnh a đến cạnh b tại mỗi đỉnh là quay phải hay quay trái. .Tính tọa độ theo hướng oz của tích vector a x b T= k(a x b) = ax*by - ay*bx - Nếu mọi phép quay đều như phép quay tại đỉnh thứ nhất, đa giác lồi. - Nếu có một phép quay khác phép quay tại đỉnh thứ nhất,đa giác lõm. Tính diện tích đa giác Cơ sở tốn học: Việc tính một đa giác đơn phẳng bất kỳ xuất phát từ việc tính diện tích tam giác. Diện tích tam giác được tính dựa vào tích hai vector như sau: S =(1/2) |a x b| Trong đó các vector a, b là các vector cạnh của tam giác. P P P P P P Với một đa giác n đỉnh, ta có thể phân thành n - 2 tam giác bằng cách từ một đỉnh nào đó của tam giác ta vẽ các cạnh nối đến tất cả các cạnh còn lại của đa giác. Khi đó diện tích đa giác bằng tổng diện tích của các tam giác con này. Lấy đỉnh P1 làm chốt, lập (n-1) vector chốt vector a1=P2 - P1, a2 = P3 - P1, an-1=Pn - P1. Các vector này dùng để tính diện tích mỗi tam giác. Hai cạnh của tam giác i được xác định bởi hai vector ai và ai+1. Nhưng nếu đa giác là lõm, thì không phải mọi đa giác đều có diện tích dương. Do đó để hình thành công thức tổng quát tính diện tích một đa giác bất kỳ ta phải biến đổi công thức tính diện tích tam giác một chút. Trong công thức tính diện tích tam giác trên, thay vì dùng trị tuyệt đối của tích hai vector, ta nhân nó với un, chuẩn hướng (độ dài đơn vị) ra của mặt chứa đa giác (nếu đa giác nằm trong mặt xy, un là k). Vector chuẩn hướng ra của mặt chứa đa giác được xác định bằng cách tính tích hữu hướng hai vector cạnh của tam giác. Nhân với chuẩn hướng ra un là để lọc ra diện tích âm và diện tích dương, nó không ảnh hưởng đến bản thân từng diện tích tam giác. Lúc này diện tích tam giác được tính theo công thức: S = (ax.by-ay.bx)/ 2 trong đó a, b là hai vector cạnh của tam giác. Khi đó diện tích của đa giác là: S = trong đó Si là diện tích (có dấu) của tam giác thứ I Giải thuật: - i bắt đầu = 2 - Diện tích đa giác = 0 - Lặp lại { . Tính diện tích tam giác có 3 đỉnh là : đỉnh 1,đỉnh i, đỉnh i+1 . Diện tích đa giác = Diện tích đa giác + Diện tích tam giác . Inc (i,1) } Cho đến khi i=N-1 - Diện tích đa giác = Abs (diện tích đa giác) III.2. CÁC QUAN HỆ HÌNH HỌC TRONG KHÔNG GIAN (3D) 1- Các phép biến hình 3 chiều Cơ sở tốn học: Một trong những ưu điểm quan trọng của đồ họa là cho phép dễ dàng tác động lên các đối tượng đồ họa. Tất cả các biến đổi trên đồ họa máy tính đều có thể thỏa mãn một cách tương đối dễ dàng vì các hình ảnh khi đưa vào xử lý đã được số hố, do đó nó có thể thay đổi dễ dàng bằng các phép biến đổi tốn học. Phép biến đổi hình học thường được dùng là phép biến đổi Affine. Có hai quan điểm về phép biến đổi, đó là: Biến đổi đối tượng. Biến đổi hệ tọa độ. Biến đổi đối tượng: là thay đổi tọa độ các điểm mô tả nó theo một quy luật nào đó. Biến đổi hệ tọa độ: sẽ tạo ra một hệ tọa độ mới và tất cả các điểm mô tả đối tượng sẽ được chuyển về hệ tọa độ mới này. Phần này ta sẽ mô tả một số phép biến đổi đối tượng. Phép biến đổi affine 3D biến đổi điểm P(Px,Py,Pz) thành điểm Q: Q = PM m m m m m m m m m m m m m m m m M = Với P = (Px, Py, Pz), Q = (Qx, Qy, Qz) và M là ma trận biến hình 4x4 Một số phép biến đổi Affine cơ sở, đó là: phép tịnh tiến, phép co dãn, phép quay. a/ Phép tịnh tiến: Dịch chuyển đối tượng từ vị trí này sang vị trí khác. Tịnh tiến với các độ dời tx, ty, tz. M = 1 0 0 0 0 1 0 0 0 0 1 0 tx ty tz 1 b/Phép co dãn: Với hệ số co Sx , Sy, Sz. Ma trận M là Sx 0 0 0 0 Sy 0 0 0 0 Sz 0 0 0 0 1 M = c/Phép quay quanh trục x gócA: Tọa độ x của vật thể không đổi. Ma trận M là 1 0 0 0 0 cos(A) sin(A) 0 0 -sin(A) cos(A) 0 0 0 0 1 M = d/Phép quay quanh trục y góc A: Tọa độ y của vật thể không đổi. Ma trận M là: cos(A) 0 -sin(A) 0 0 1 0 0 sin(A) 0 cos(A) 0 0 0 0 1 M = e/Phép quay trục z gócA: Tọa độ z của vật thể không đổi. Ma trận M là cos(A) sin(A) 0 0 -sin(A) cos(A) 0 0 0 0 1 0 0 0 0 1 M = * Tổng hợp các phép biến hình Phép biến hình T1: PàQ’ có ma trận M1. Phép biến hình T2 : Q’àQ có ma trận M2. Tổng hợp 2 phép biến hình T1, T2 là phép biến hình T: PàQ Phép biến hình T có ma trận M = M1 x M2 Giải thuật: - Tính các phần tử của ma trận M. - Xác định các điểm mới của đối tượng qua phép biến hình. -Vẽ lại đối tượng. 2- Biểu diễn đối tượng 3D Cơ sở tốn học: Các đối tượng trong thế giới thực hầu hết là các đối tượng 3D. Việc biểu diễn các đối tượng 3D trên mặt phẳng 2D, bằng máy tính phải tuân thủ các quy luật về phối cảnh… nhằm giúp người xem có ấn tượng hình ảnh gần đúng trong thực tế. Mô hình khung dây(Wireframe) dùng biễu diễn các đối tượng 3D đơn giản như các khối đa diện, các mặt mà có thể đơn giản hóa cách thể hiện nó như gồm tập hợp gồm các đỉnh và các cạnh nối liền các đỉnh đó. Để lưu trữ mô hình khung dây cần phải có 2 danh sách: + Danh sách đỉnh chứa tọa độ các đỉnh. + Danh sách cạnh chứa các cặp đỉnh nối cạnh đó. Cấu trúc dữ liệu mô tả Wireframe Typedef struct { int NumVerts; int NumEdges; Point3D vert [ ]; Point3D edge[ ][2]; } wireframe; Để vẽ các đối tượng biểu diễn bằng mô hình khung dây chúng ta chỉ cần vẽ các cạnh trong danh sách cạnh. Tuy nhiên do các đỉnh và cạnh được định nghĩa trong 3D nên để vẽ ta phải chiếu lên mặt phẳng 2D bằng các phép chiếu thích hợp : +Chiếu mỗi điểm lên 2D. +Vẽ đoạn thẳng giữa hai điểm chiếu này. Giải thuật: +Khởi tạo danh sách đỉnh. Đưa các đỉnh đa giác vào danh sá