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

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ách đỉnh. +Khởi tạo danh sách các cạnh. Đưa các cặp đỉnh nối cạnh vào danh sách cạnh. +Khởi tạo phép chiếu. Tìm các điểm chiếu của các đỉnh wireframe. +Vẽ các cạnh của đối tượng. Trong chương trình minh họa, chúng ta sẽ dùng mô hình wireframe để biểu diễn một số đối tượng ba chiều đặc biệt như hình lăng trụ, hình chóp. ¨ Hình lăng trụ: Cơ sở của hình lăng trụ là một đa giác P nằm trên mặt xy và được quét dọc theo trục z đến một chiều cao H nào đó. Nếu đa giác P có n đỉnh, hình lăng trụ có 2*n đỉnh và 3*n cạnh. Danh sách đỉnh: n đỉnh đầu tiên dành cho đa giác P có tọa độ z bằng 0, n đỉnh kế tiếp có tọa độ z là h. Danh sách cạnh: n cạnh được chọn đầu tiên thuộc đa giác P sao cho prism.edge[i,1] là i và prism.edge[i,2] là i+1 (ngoại trừ khi i =n thì sẽ là 1 để thành đa giác), tương tự n cạnh kế ở mặt trên của hình trụ. Cuối cùng là n cạnh đứng của hình trụ có prism.edge[i+2n,1] là i và prism.edge[i+2n] là i+n. ¨ Hình chóp: Đáy của hình chóp là đa giác P có n đỉnh nằm trên mặt xy. Và đỉnh hình chóp không thuộc mặt xy. Hình chóp có 2*n đỉnh và 2*n cạnh. Danh sách đỉnh: n đỉnh đầu tiên dành cho đa giác P có tọa độ z bằng 0, đỉnh kế tiếp (n+1) có tọa độ z là h. Danh sách cạnh: n cạnh được chọn đầu tiên thuộc đa giác P sao cho pyramide.edge[i,1] là i và pyramide.edge[i,2] là i+1 (ngoại trừ khi i =n thì sẽ là 1 để thành đa giác). n cạnh kế có pyramide.edge[i+n,1] là i và pyramide.edge[i+n,2] là n+1. 3- Quan sát vật thể 3D qua hệ tọa độ quan sát Cơ sở tốn học: Một đối tượng 3-D được xác định bởi các tọa độ x,y,z,nhưng màn hình thì đối tượng được biểu diễn chỉ với các tọa độ x và y. Để có thể biểu diễn được một đối tượng 3-D lên màn hình, có hai phương pháp để thực hiện vấn đề trên là phép chiếu song song và phép chiếu phối cảnh. Phép chiếu song song: Loại hình đơn giản nhất của phép chiếu song song là phép chiếu trực giao nhưng lại có rất nhiều ứng dụng trong các bản vẽ kỹ thuật. Với phép chiếu song song, một đối tượng 3-D được thể hiện lên màn hình bằng cách bỏ qua các tọa độ z. Kết quả là một hình 2-D đơn giãn. Như vậy, với trường hợp khối vuông, hình ảnh thể hiện trên màn hình chỉ là một hình vuông. b. Phép chiếu phối cảnh: Khác với phép chiếu song song, phép chiếu phối cảnh được hình thành từ các tia chiếu không song song với nhau mà hội tụ tại một điểm gọi là tâm chiếu. Kích thước của vật qua phép chiếu sẽ được phóng to hay thu nhỏ phụ thuộc vào khoảng cách giữa tâm chiếu và mặt phẳng chiếu (mặt quan sát). Khoảng cách giữa mắt và mặt quan sát gọi là tầm nhìn. 0 P x z’ y’ x, y z P’ D R Trong đó: Ox’y’z’: Hệ trục tọa độ quan sát. D: Khoảng cách giữa mặt phẳng chiếu và hệ trục quan sát. R: Khoảng cách giữa 2 gốc tọa độ. q: góc giữa hình chiếu OO’trên mặt phẳng xoy và trục ox. j: góc giữa OO’và mặt phẳng xoy. Mắt đặt tại gốc hệ tọa độ quan sát đặt dọc với trục O’z’hướng vào gốc O. Mặt phẳng quan sát vuông góc với OO’. Khi thay đổi góc q và góc j sẽ dẫn đến việc thay đổi góc quan sát vật thể từ đó việc thể hiện đối tượng được quan sát sẽ linh động hơn. Để chuyển đổi điểm P(x,y,z) trong hệ tọa độ Oxyz ra tọa độ (xo,yo,zo) trong hệ tọa độ thứ hai dựa trên x,y,z chúng ta sử dụng công thức sau: (xo,yo,zo,1) = (x,y,z,1) * T với là ma trận biến hình T -sinq -cosq sinj -cosqcosj 0 cosq -sinq sinj -sinqcosj 0 0 cosj -sinj 0 0 0 R 1 T = và xo = -x sinq + y cosq yo = -x cosqsinj - y sinqsinj + z cosj zo = -x cosqcosj - y sinqcosj - zsinj + R Hình chiếu P’(xc, yc) của điểm P(xo, yo, zo): Do mặt phẳng màn hình vuông góc với trục Oz’ và tâm chiếu là O’. màn hình P P’ yc màn hình D P P’ z0 xc x0 z’ y’ z’ x’ Aùp dụng tính chất tam giác đồng dạng, ta có: xc = D*xo / zo yc = D*yo / zo Với phép chiếu phối cảnh, tọa độ của điểm chiếu là: P’.xc =D*xo/ zo P’.yc = D*yo/ zo Với phép chiếu song song, mắt đặt ở vô cực, vì vậy: xc = xo và yc = yo Vậy từ điểm P(x,y,z) trên đối tượng 3D qua phép chiếu phối cảnh hay song song đã cho ta điểm P’(xc,yc) trong mặt phẳng 2D. + Tăng góc q sẽ làm hệ quan sát xê dịch trong mặt phẳng xy theo chiều ngược chiều kim đồng hồ làm quay vật thể theo chiều kim đồng hồ. + Giảm góc q làm quay vật thể ngược chiều kim đồng hồ. + Tăng góc j sẽ đẩy hệ quan sát lên trên làm quay vật xuống dưới. + Giảm góc j làm quay vật lên trên. Giải thuật ứng dụng trong vẽ mô hình khung dây. + Trường hợp nhấn phím mũi tên Up : góc q = q - 5; (tính theo độ) Down : góc q = q + 5; Left : góc j = j - 5; Right : góc j = j + 5; + Khởi tạo lại phép chiếu Tìm các điểm chiếu của các đỉnh wireframe. + Vẽ lại các cạnh của đối tượng. 4 -Kiểm tra quan hệ Điểm - Đường thẳng Cơ sở tốn học và giải thuật: Begin - Nhập tọa độ 2 điểm A(xa, ya , za), B(xb, yb, zb ) mà đường thẳng d đi qua. - Nhập tọa độ điểm C (xc , yc , zc). - Tính tọa độ vector chỉ phương của đường thẳng d . Vector AB = (xb - xa ; yb - ya ; zb -za ) ( hay AB=( a1,a2,a3 ) ) . Phương trình tổng quát đường thẳng d qua hai điểm A, B là hệ phương trình tương đương với hệ sau: a2x - a1y + 0 + a1ya - a2xa = 0 a3x + 0 - a1z + a1za - a3xa = 0 - Thay tọa độ của điểm C (xc , yc , zc) vào hệ phương trình tổng quát của đường thẳng, ta được: a2xc - a1yc + 0 + a1ya - a2xa = 0 a3xc + 0 - a1zc + a1za - a3xa = 0 . Nếu hệ trên thỏa thì điểm thuộc đường thẳng, xuất thông điệp “ĐIỂM THUỘC ĐƯỜNG THẲNG“; . Nếu không thỏa tính khoảng cách từ điểm đến đường thẳng: .. Viết phương trình của mặt phẳng qua C(xc , yc , zc) vuông góc với đường thẳng d qua 2 điểm A , B và có vector chỉ phương AB = (a1 , a2 , a3). Phương trình mặt phẳng có dạng: a1x + a2y + a3z - a1xc - a2yc - a3zc = 0 (* ) .. Viết phương trình tham số của đường thẳng qua A, B X = a1t + xa Y = a2t + ya Z = a3t + za .. Thay X , Y, Z vào phương trình mặt phẳng (*), ta được: a1( a1t + xa)+ a2( a2t + ya) + a3( a3t + za) - a1xc - a2yc - a3zc = 0 t = a1xa - a2ya - a3za + a1xc + a2yc + a3zc / ( a12 + a22 + a32 ) .. Thay t vào phương trình tham số của đường thẳng d qua A, B tìm được điểm H - Tọa độ cuả điểm cắt H(Xh , Yh ,Zh): Xh = a1(a1xa - a2ya - a3za + a1xc + a2yc + a3zc)/ ( a12 + a22 + a32 ) + xa Yh = a2(a1xa - a2ya - a3za + a1xc + a2yc + a3zc)/ ( a12 + a22 + a32 ) + ya Zh = a3(a1xa - a2ya - a3za + a1xc + a2yc + a3zc)/ ( a12 + a22 + a32 ) + za - Tính khoảng cách từ điểm C đến đường d qua 2 điểm A, B: dch = | CH | = sqrt(( xc - xh )2 + ( yc - yh )2 + ( zc - za )2 ) - Xuất tọa độ điểm H(Xh , Yh ,Zh) và khoảng cách dch End. 5 - Kiểm tra quan hệ Điểm - Mặt phẳng Cơ sở tốn học và giải thuật: Begin - Nhập tọa độ 3 điểm A(xa , ya , za), B(xb , yb , zb ), C ( xc , yc , zc) xác định mặt phẳng mp(ABC) (3 điểm A, B, C không thẳng hàng). - Nhập tọa độ điểm D(xd , yd , zd). - Tính các vector : vector AB = ( xb - xa , yb - ya , zb - za ) vector AC = ( xc - xa , yc - ya , zc - za ) vector AD = ( xd - xa , yd - ya , zd - za ) - Xét điểm D(xd , yd, zd) có thuộc mp(ABC) không? . Tính tích hữu hướng của 2 vector AB, AC là n = AB x AC có dạng định thức như sau: yb - ya zb-za zb -za xb - xa xb - xa yb - ya yc - ya zc-za , zc -za xc - xa , xc - xa yc - ya n = Hoặc có thể theo cách viết dưới đây: AB x AC = ((yb - ya )*(zc - za) - (yc - ya)*(zb - za), (zb - za )*(xc - xa) - (zc - za)*(xb - xa), (xb - xa )*(yc - ya) - (xc - xa)*(yb - ya)) . Tính tích vô hướng của 2 véc tơ n=(AB x AC) và vector AD là (ABxAC).AD bằng dùng định thức cấp 3 với ba véc tơ AB, AC, AD như sau: xb - xa yb - ya zb - za xc - xa yc - ya zc - za xd - xa yd - ya zd - za Dt = Dt = (AB x AC).AD = ( xd - xa )(( yb - ya  )*( zc -za ) - (yc - ya )*( zb -za ) ) + (yd - ya )(( zb -za )* (xc - xa ) - ( zc -za ) *(xb - xa ) ) + (zd - za )((xb - xa )*( yc - ya ) - (xc - xa )*( yb - ya )) . Ta xét định thức cấp 3 này .. Nếu Dt = 0 xuất “Điểm D thuộc mp(ABC)“ .. Nếu Dt 0 xuất “Điểm D không thuộc mp(ABC)” .. Nếu Dt 0 tìm khoảng cách từ điểm D đến mp(ABC) Viết phương trình tổng quát của mp(ABC), có 2 vector AB = (xb - xa ,yb - ya , zb -za ) AC = (zb - za , yc - ya , zc - za ) N = (AB x AC) = (( yb - ya  )*( zc - za ) - (yc - ya )*(zb - za ), ( zb - za )* (xc - xa ) - (zc - za )*(xb - xa ), ( xb - xa )*(yc - ya ) - (xc - xa )*(yb - ya )) Nếu chúng ta đặt: A = (yb - ya )*( zc -za ) - (yc - ya )*( zb -za ) B = ( zb -za )* (xc - xa ) - ( zc -za )*(xb - xa ) C = (xb - xa )*(ya - yb ) - (xc - xa )*( xb - xa) D = -xaA - yaB - zaC . vector n có thể viết lại n =(A, B, C ) là pháp vector của mp(ABC). Và phương trình tổng quát của mặt phẳng mp(ABC) la:ø Ax + By + Cz + D = 0 . Khoảng cách từ D(xd , yd , zd) đến mp(ABC) ddmp(ABC) = abs( Axd + Byd + Czd + D ) / sqrt (A2 + B2 + C2 ) . . Xuất ra “ ddmp(ABC) “ - Tìm giao điểm của đường thẳng d qua D(xd, yd, zd) và vuông góc với mp(ABC), có vector chỉ phương là pháp vector n = (A, B, C). Phương trình tham số của đường thẳng d: X = At + xd Y = Bt + yd Z = Ct + zd . Thay X , Y , Z vào phương trình mặt phẳng mp(ABC): A( At + xa) + B( Bt + ya) + C(Ct + za) + D = 0 t = -(Axd + Byd + Czd + D ) / ( A2 + B2 + C2 ) . Thay t vào phương trình tham số của đường thẳng d. Ta có tọa độ điểm cắt H(Xh , Yh ,Zh) Xh = A(-(Axd + Byd + Czd + D ) / ( A2 + B2 + C2 ))+ xd Yh = B(-(Axd + Byd + Czd + D ) / ( A2 + B2 + C2 )) + yd Zh = C(-(Axd + Byd + Czd + D ) / ( A2 + B2 + C2 )) + za . Xuất tọa độ điểm H(Xh , Yh ,Zh) End. 6 - Kiểm tra quan hệ Đường thẳng - Đường thẳng Cơ sở tốn học và thuật giải: Begin - Nhập tọa độ 2 điểm A(xa , ya , za) và B(xb , yb , zb) mà đường thẳng d đi qua. - Nhập tọa độ 2 điểm C(xc , yc , zc) và D(xd , yd , zd) mà đường thẳng d’ đi qua. - Tính véc tơ chỉ phương AB của đường thẳng d: AB =( xb - xa , yb - ya , zb - za ) ( hay có thể viết gọn hơn AB = ( a1 , a2 , a3 ) ) - Tính véc tơ chỉ phương CD của đường thẳng d’ CD = ( xd - xc , yd - yc , zd - zc ) (hay có thể viết gọn hơn CD = ( b1 , b2 , b3 ) ) - Viết phương trình của đường thẳng d: Phương trình chính tắc: ( x - xa )/ a1 = ( y - ya )/ a2 = ( z - za )/ a3 Hệ phương trình tổng quát của đường thẳng d : a2x - a1y + 0 + a1ya - a2xa = 0 a3x + 0 - a1z + a1za - a3xa = 0 - Viết phương trình của đường thẳng d’: Phương trình chính tắc: ( x - xc )/ b1 = ( y - yc )/ b2 = ( z - zc )/ b3 Hệ phương trình tổng quát của đường thẳng d’: b2x - b1y + 0 + b1yc - b2xc = 0 b3x + 0 - b1z + b1zc - b3xc = 0 - Xét sự tương quan của đường thẳng d qua A, B và d’qua C, D: · Ta có 3 vector AB, CD, AC: Vector AB = ( xb - xa , yb - ya , zb - za ) Vector CD = ( xd - xc , yd - yc , zd - zc ) Vector AC = ( xc - xa , yc - ya , zc - za ) · Lập định thức cấp 3 của 3 vector AB, CD, AC xb - xa yb - ya zb - za xd - xc yd - yc zd - zc xc - xa yc - ya zc - za Dt = Dt = (Ab x CD).AC = ( xc - xa )(( yb - ya )*( zd - zc ) - ( yd - yc )*( zb -za )) + ( yc - ya )(( zd - zc )*( xc - xa ) - ( zc - za )*( xb - xa )) + ( zc - za )(( xb - xa )*( yd - yc ) - ( xd - xc )*( yb - ya )) - Nếu (Dt0), xuất ra kết quả “Hai đường thẳng d và d’ chéo nhau“. - Nếu ((Dt = 0) AND (a1 / b1 = a2 / b2 = a3 / b3)), xuất ra kết quả “ Hai đường thẳng d và d’ song song“. - Nếu ((Dt = 0) AND (a1 / b1 = a2 / b2 = a3 / b3) AND (d, d’có 2 điểm chung)), xuất ra kết quả “ Hai đường thẳng d và d’ trùng nhau“. - Nếu ((Dt = 0) AND (a1 / b1 a2 / b2 a3 / b3)), xuất ra kết quả “Hai đừơng thẳng d và d’cắt nhau“. - Tìm tọa độ của điểm cắt nhau giữa hai đường thẳng d và d’: · Hệ phương trình tổng quát của đường thẳng d: a2x - a1y + 0 + a1ya - a2xa = 0 a3x + 0 - a1z + a1za - a3xa = 0 · Hệ phương trình tổng quát của đường thẳng d’: b2x - b1y + 0 + b1yc - b2xc = 0 b3x + 0 - b1z + b1zc - b3xc = 0 · Giải các hệ phương trình tổng quát của đường thẳng d, d’: a2x - a1y + 0 + a1ya - a2xa = 0 a3x + 0 - a1z + a1za - a3xa = 0 (*) b2x - b1y + 0 + b1yc - b2xc = 0 Đặt: d1 = a1ya - a2xa d2 = a1za - a3xa d3 = b1yc - b2xc · Hệ phương trình (*) viết lại như sau: a2x - a1y + 0 + d1 = 0 a3x + 0 - a1z + d2 = 0 b2x - b1y + 0 + d3 = 0 · Lập định thức cấp 3 cho hệ ba phương trình trên để tìm tọa độ giao điểm của đường thẳng d và d’: a2 -a1 0 a3 0 -a1 b2 -b1 0 -d1 -a1 0 -d2 0 -a1 -d3 -b1 0 a2 -d1 0 a3 -d2 -a1 b2 -d3 0 Dt = Dt = Dt = Dt = a2 -a1 -d1 a3 0 -d2 b2 -b1 -d3 · Tọa độ giao điểm của đường thẳng d, d’ là E(xgd , ygd , zgd): xgd = Dtxgd / Dtgd ygd = Dtygd / Dtgd zgd = Dtzgd / Dtgd - Xuất ra kết quả tọa độ giao điểm E(xgd , ygd , zgd). - Nếu (Dt 0) thì hai đường thẳng d và d’ chéo nhau · Tính khoảng cách giữa đường thẳng d và d’(đoạn vuông góc chung). End. 7 - Kiểm tra quan hệ Đường thẳng - Mặt phẳng Cơ sở tốn học và giải thuật: Begin - Nhập tọa độ 3 điểm A(xa , ya , za), B(xb , yb , zb ), C(xc , yc , zc) xác định mặt phẳng mp(ABC) (3 điểm A, B, C không thẳng hàng với nhau). - Nhập tọa độ 2 điểm E(xe , ye , ze) và F(xf , yf , zf) mà đường thẳng d đi qua. - Tính tọa độ các vector : AB = ( xb - xa , yb - ya , zb - za ) AC = ( xc - xa , yc - ya , zc - za ) - Tính tích hữu hướng của 2 vector AB, AC có dạng định thức cấp 2 như sau (n = AB x AC chính là pháp vector của mp(ABC)) yb -ya zb -za zb -za xb -xa xb -xa yb -ya yc -ya zc -za , zc -za xc -xa , xc -xa yc -ya Ab x AC = Hoặc có thể viết dưới dạng như sau: n = AB x AC = (( yb - ya )*( zc - za ) - ( yc - ya )*( zb -za ), ( zb - za )*( xc - xa ) - ( zc - za )*( xb - xa ), ( xb - xa )*( yc - ya ) - ( xc - xa)*( yb - ya )) Nếu chúng ta đặt: A = ( yb - ya )*( zc - za ) - ( yc - ya )*( zb - za ) B = ( zb - za )*( xc - xa ) - ( zc - za )*( xb - xa ) C = ( xb - xa )*( ya - yb ) - ( xc - xa)*( xb - xa ) D = -xaA - yaB - zaC Phương trình tổng quát của mặt phẳng mp(ABC) có dạng: Ax + By + Cz + D = 0 - Tính vector chỉ phương EF của đường thẳng d đi qua hai điểm E và F: vector EF = ( xf - xe , yf - ye , zf - ze ) ( có thể viết gọn lại EF = ( a1 , a2 , a3 ) ) -Viết phương trình tham số của đường thẳng d: X = a1t + xe Y = a2t + ye Z = a3t + ze - Xét sự tương quan giữa đường thẳng d qua 2 điểm E, F và mp(ABC) qua 3 điểm A, B, C : · Tính tích vô hướng của 2 vector (AB x AC) và vector EF bằng việc sử dụng định thức cấp 3 với ba vector AB, AC, EF như sau: vector AB = ( xb - xa , yb - ya , zb - za ) vector AC = ( xc - xa , yc - ya , zc - za ) vector EF = ( xf - xe , yf - ye , zf - ze ) Định thức cấp 3: xb - xa yb - ya zb - za xc - xa yc - ya zc - za xf - xe yf - ye zf - ze Dt = Dt = (AB x AC).EF = ( xf - xe )(( yb - ya)*( zc - za ) - ( yc - ya )*( zb - za )) + ( yf - ye )(( zb - za )*( xc - xa ) - ( zc -za )*( xb - xa )) + ( zf - ze )(( xb - xa )*( yc - ya ) - ( xc - xa)*( yb - ya )) · Xét định thức cấp 3 này: + Nếu Dt = 0, xuất ra kết quả “Đường thẳng d song song hoặc chứa trong mp(ABC)“ + Nếu Dt0, xuất ra kết quả “Đường thẳng d cắt mp(ABC)“ - Nếu Dt0, tìm tọa độ giao điểm giữa đường thẳng d và mp(ABC): + Phương trình tổng quát của mặt phẳng mp(ABC) có dạng: Ax + By + Cz + D = 0 + Phương trình tham số cuả đường thẳng d: X = a1t + xe Y = a2t + ye Z = a3t + ze + Thay X, Y, Z vào phương trình mặt phẳng (ABC), ta được: A( a1t + xe) + B( a2t + ye) + C(a3t + ze) + D = 0 t = -(Axe + Bye + Cze + D ) / ( Aa1 + Ba2 + Ca3 ) + Thay t vào phương trình tham số cuả đường thẳng d, ta có tọa độ giao điểm của d và mp(ABC): Xgd = a1(-(Axe + Bye + Cze + D ) / ( Aa1 + Ba2 + Ca3 ) ) + xe Ygd = a2(-(Axe + Bye + Cze + D ) / ( Aa1 + Ba2 + Ca3 ) ) + ye Zgd = a3(-(Axe + Bye + Cze + D ) / ( Aa1 + Ba2 + Ca3 ) ) + ze + Xuất ra tọa độ giao điểm H(xgd , ygd , zgd). - Tính góc giữa đường thẳng d qua E, F và mp(ABC) qua A, B, C Cos(AB^n) = abs(Aa1 + Ba2 + Ca3 ) / sqrt(A2 + B2 + C2) * sqrt(a12 + a22 + a32) - Đường thẳng d song song với mp(ABC). Tính khoảng cách từ đường thẳng d đến mp(ABC): + Viết phương trình đường thẳng d’qua điểm E và vuông góc với mặt phẳng (ABC) có pháp vector n=(A , B, C ) X = At + xe Y = Bt + ye Z = Ct + ze + Thay X , Y , Z vào phương trình mặt phẳng (ABC), ta được: A( At + xe) + B( Bt + ye) + C(Ct + ze) + D = 0 t = -(Axe + Bye + Cze + D ) / ( A2 + B2 + C2 ) + Thay t vào phương trình tham số của đường d’, ta có tọa độ giao điểm giữa đường thẳng d’và mp(ABC): Xh = A(-(Axe + Bye + Cze + D ) / ( A2 + B2 + C2 )) + xe Yh = B(-(Axe + Bye + Cze + D ) / ( A2 + B2 + C2 )) + ye Zh = C(-(Axe + Bye + Cze + D ) / ( A2 + B2 + C2 ) ) + ze + Xuất ra tọa độ giao điểm H( xh , yh , zh ) . + Tính khoảng cách từ đường thẳng d đến mp(ABC), chính là đoạn AH: dah = sqrt ( ( xh - xa )2 + ( yh - ya )2 + ( zh - za )2 ) + Xuất ra khoảng cách dah End. 8 . Kiểm tra quan hệ Mặt phẳng - Mặt phẳng Cơ sở tốn học và thuật giải: Begin - Nhập tọa độ 3 điểm A(xa, ya, za), B(xb, yb, zb ), C(xc, yc, zc) để xác định tọa độ mp(ABC) - Nhập tọa độ 3 điểm M(xm , ym , zm), P(xp , yp , zp ), Q( xq , yq , zq) để xác định tọa độ mặt phẳng mp(MPQ). - Tính tọa độ các véc tơ của mp( ABC) vector AB = ( xb - xa , yb - ya , zb - za ) vector AC = ( xc - xa , yc - ya , zc - za ) (3 điểm A,B,C tạo thành mp(ABC) nên vector AB không cùng phương với vectơ AC) -Tính tích hữu hướng của 2 vector AB, AC là n = (AB x AC),n chính là pháp vector của mp(ABC) có tọa độ : n = AB x AC = (( yb - ya )*( zc - za ) - ( yc - ya )*( zb - za ), ( zb - za )*( xc - xa ) - ( zc - za )*( xb - xa ), ( xb - xa )*( yc - ya ) - ( xc - xa )*( yb - ya )) Nếu chúng ta đặt: A = ( yb - ya )*( zc - za ) - ( yc - ya )*( zb - za ) B = ( zb - za )*( xc - xa ) - ( zc - za )*( xb - xa ) C = ( xb - xa )*( ya - yb ) - ( xc - xa )*( xb - xa) D = -xaA - yaB - zaC . Phương trình tổng quát của mặt phẳng mp(ABC) có dạng: Ax + By + Cz + D = 0 - Tính tọa độ các vector của mặt phẳng mp(MPQ) : vector MP = ( xp - xm , yp - ym , zp - zm ) vector MQ = (xq - xm , yq - ym , zq - zm ) (3 điểm M, P, Q tạo thành mp(MPQ) nên vector MP không cùng phương với vector MQ) - Tính tích hữu hướng của 2 vector MP, MQ là m = MP x MQ, m chính là pháp vector của mp(MPQ), có tọa độ : m = MP x MQ yp -ym zp -zm zp -zm xp -xm xp - xm yp - ym yq -ym zq -zm , zq -zm xq -xm , xq - xm yq - ym m = hay có thể viết như sau: m = MP x MQ = (( yp - ym )*( zq -zm ) - (yq - ym )*( zp -zm ), ( zp -zm )* (xq - xm ) - ( zq -zm ) *(xp - xm ), (xp - xm )*( yq - ym ) - (xq - xm )*( yp - ym )) Nếu chúng ta đặt: A1 = (yp - ym )*( zq -zm ) - (yq - ym )*( zp -zm ) B1 = ( zp -zm )* (xq - xm ) - ( zq -zm ) *(xp - xm ) C1 = (xp - xm )*(yp - ym ) - (xq - xm )*( xp - xm) D1 = -xmA1 - ymB1 - zmC1 . Phương trình tổng quát của mặt phẳng mp(MPQ): mp(MPQ) = A1x + B1y + C1z + D1 = 0 - Xét sự tương quan của 2 mặt phẳng trên: · Nếu (A/A1 = B/B1 = C/C1) xuất ra kết quả “Hai mặt phẳng trùng nhau“. · Nếu (A/A1 = B/B1 = C/C1 D/D1) xuất ra kết quả “Hai mặt phẳng song song với nhau“. · Nếu (A/A1 B/B1) hoặc (B/B1 C/C1) hoặc (A/A1 C/C1) xuất ra kết quả “Hai mặt phẳng cắt nhau“. - Hai mặt phẳng mp(ABC) và mp(MPQ) cắt nhau theo một giao tuyến là đường thẳng có phương trình là hệ phương trình của hai mặt phẳng mp(ABC) và mp(MPQ): Ax + By + Cz + D = 0 A1x + B1y + C1z + D1 = 0 - Tính tọa độ giao điểm thuộc giao tuyến: · Nếu (A/A1 B/B1) thì tọa độ z có thể được chọn tuỳ ý cho đơn giản, dùng định thức cấp 2 tìm tọa độ giao tuyến : Ax + By + Cz + D = 0 A1x + B1y + C1z + D1 = 0 Ta tính được: Dx1 = AB2 - A1B Dx1 = B1(-D - Ck1 ) + B( D1 + C1k1 ) Dy1 = A(-D1 – C1k1 ) + A1( D + C1k1 ) Suy ra: X1 = Dx1/ D Y1 = Dy1/ D Z1= k1 Þ Tọa độ I(X1 , Y1 , Z1) · Tìm tọa độ điểm thứ 2: Dx2 = AB2 - A1B Dx2 = B1(-D - Ck2 ) + B( D1 + C1k2 ) Dy2 = A(-D1 - C1k2 ) + A1( D + C1k2 ) X2 = Dx2 / D Y2 = Dy2 / D Z2 = k2 Þ Tọa độ J(X2 , Y2 , Z2) · Xuất tọa độ 2 điểm thuộc giao tuyến J(X2, Y2 , Z2 ) và I(X1, Y1, Z1) - Nếu hai mặt phẳng song song, tính khoảng cách của 2 mặt phẳng: · Tìm giao điểm của đường thẳng d qua điểm M( xm, ym, zm) và vuông góc với mp(ABC), có vector chỉ phương là pháp vector của mp(ABC) là vector n=(A,B,C). · Viết phương trình tham số của đường thẳng d: X = At + xm Y = Bt + ym Z = Ct + zm · Thay X, Y, Z vào phương trình mặt phẳng mp(ABC): A( At + xm)+B( Bt + ym) + C(Ct + zm) + D = 0 t = -(Axm + Bym + Czm + D ) / ( A2 + B2 + C2 ) · Thay t vào phương trình tham số của đườngthẳng d: + Ta có tọa độ điểm cắt H(Xh , Yh, Zh): Xh = A(-(Axd + Byd + Czd + D ) / ( A2 + B2 + C2 ))+ xd Yh = B(-(Axd + Byd + Czd + D ) / ( A2 + B2 + C2 )) + yd Zh = C(-(Axd + Byd + Czd + D ) / ( A2 + B2 + C2 )) + zd · Khoảng cách hai mp(ABC) và mp(MPQ) là đoạn MH: dmh =|MH | = sqrt ( ( xh - xm)2 + ( yh - ym )2 + ( zh - zm )2 ) · Xuất khoảng cách dmh End. 9-Kiểm tra tính đồng phẳng của đa giác Cơ sở tốn học: Đa giác gọi là phẳng nếu mọi đỉnh của nó nằm trong một mặt phẳng. Trong trường hợp này ba đỉnh bất kỳ (không thẳng hàng), có thể dùng để xác định mặt phẳng chứa nó. Khi có hơn ba đỉnh, có thể các điểm không cùng nằm trên 1 mặt phẳng. Vì vậy các ứng dụng phải kiểm tra dữ liệu để bảo đảm tính đồng phẳng. Chọn một trong m điểm, gọi là P1, làm điểm chốt (pivot) và hình thành (m-1) vector chốt Vi=Pi-P1, với i = 2,…, m. Các vector này nằm trong cùng 1 mặt phẳng nếu và chỉ nếu các đỉnh Pi nằm trong cùng một mặt phẳng. Ta biết ba vector đồng phẳng nếu và chỉ nếu tích bộ ba vô hướng của chúng triệt tiêu.Vì vậy, tạo (m-3) tích bộ ba vô hướng Vi.(V3.V2) với i=4,…., m. Nếu một trong các tích này khác zero đa giác sẽ không đồng phẳng. Giải thuật: - Tạo danh sách (n-1) vector từ đa giác P có n cạnh - Vòng lặp từ i =3 đến i =n-1 +Tính tích bộ ba vô hướng S= Vi .(V1 x V2) + Nếu (S khác 0) Return Đa giác không đồng phẳng. - Return Đa giác đồng phẳng 10 -Tính thể tích hình lăng trụ: Giải thuật: - Tính S là diện tích của đa giác đáy. - Nhập h, chiều cao của hình lăng trụ. - Tính thể tích đa giác V = S*h. 11- Tính thể tích hình chóp: Giải thuật: - Tính S là diện tích của đa giác đáy. - Nhập h, chiều cao của hình chóp. - Tính thể tích V= S*h /3. 12- Tính thể tích hình nón: Giải thuật: - Nhập R, bán kính đáy hình nón. - Nhập h, chiều cao hình nón. - Tính thể tích V = S*h / 3 = Pi*R2*h / 3. PHẦN III: THIẾT KẾ CHƯƠNG TRÌNH I. THIẾT KẾ GIAO DIỆN THỰC HIỆN KIỂM TRA CÁC QUAN HỆ HÌNH HỌC Thiết kế giao diện cho quá trình thực hiện những ứng dụng trong việc kiểm tra các quan hệ hình học, cập nhật các thông số về kích thước vùng của vùng Client: Lớp CMainFrame : Có chức năng tạo màn hình vùng Client. Lớp CApp : Có chức năng thực hiện ứng dụng kiểu đơn tài liệu (SDI). Lớp CView : Có chức năng hiển thị những hiện thực cuả chương trình kiểm tra các quan hệ hình học. Lớp CDoc : Có chức năng xử lý việc lưu trữ dữ liệu. Lớp CDialog : Có chức năng nhập, xuất dữ kiện. II. MỘT SỐ KIỂU DỮ LIỆU ĐƯỢC SỬ DỤNG TRONG CHƯƠNG TRÌNH Các đỉnh của đa giác P phẳng được lưu trữ lần lượt trong danh sách kiểu CPoint như P[0].x, P[0].y; P[1].x,P[1].y; …. Với đỉnh cuối được nhận biết bởi chỉ số đa giác kèm theo. Kiểu dữ liệu điểm trong không gian ba chiều (3D), được khai báo như sau: typedef struct { long x; long y; long z; } point3d ; Cấu trúc dữ liệu mô tả Wireframe bao gồm: +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 đó. typedef struct { int NumV; int NumE; point3d vert[20]; int edge[30][2]; } Wireframe; Kiểu dữ liệu dùng để tạo danh sách cạnh từ các đỉnh liên tiếp nhau: typedef struct { CPoint A; CPoint B; } TypeListEdge; Kiểu dữ liệu lưu trữ các điểm, có kèm theo cờ để phân biệt các loại điểm khác nhau (điểm giao nhau giữa 2 đa giác, điểm này đã được duyệt hay chưa duyệt; hay đỉnh của đa giác) được dùng trong thủ tục kiểm tra quan hệ hai đa giác, được khai báo như sau: typedef struct { CPoint P; int CFlag; } ListPoint; III. CÁCH TỔ CHỨC CÁC HÀM TRONG 2D Các hàm được giới thiệu dưới đây được nhóm lại thành từng nhóm giúp cho việc theo dõi được dễ dàng hơn Những hàm được sử dụng trong lớp CkiemTra2DView.cpp Construction/destruction lớp CView CKiemTra2DView:: CKiemTra2DView() CKiemTra2DView:: ~CKiemTra2DView() Các hàm tạo cửa sổ, vẽ của lớp CView BOOL CKiemTra2DView::PreCreateWindow(CREATESTRUCT& cs) void CKiemTra2DView:: OnDraw(CDC* pDC)// Debug void CKiemTra2DView::AssertValid() const void CKiemTra2DView::Dump(CDumpContext& dc) const CTestHHDoc* CKiemTra2DView::GetDocument() Các hàm phục vụ vẽ trong 2D void CKiemTra2DView::OnVediem() void CKiemTra2DView::OnUpdateVediem(CCmdUI* pCmdUI) void CKiemTra2DView::OnVeduongthang1() void CKiemTra2DView::OnUpdateVeduongthang1(CCmdUI* pCmdUI) void CKiemTra2DView::OnVeduongthang2() void CKiemTra2DView::OnUpdateVeduongthang1(CCmdUI* pCmdUI) void CKiemTra2DView:: OnVedagiac1() void CKiemTra2DView::OnUpdateVedagiac1(CCmdUI* pCmdUI) void CKiemTra2DView::OnVedagiac2() void CKiemTra2DView::OnUpdateVedagiac2(CCmdUI* pCmdUI) Các hàm liên quan đến mouse void CKiemTra2DView::OnLButtonDown(UINT nFlags, CPoint point) void CKiemTra2DView::OnLButtonUp(UINT nFlags, CPoint point) void CKiemTra2DView::OnRButtonDown(UINT nFlags, CPoint point) void CKiemTra2DView::OnMouseMove(UINT nFlags, CPoint point) Tính Max ,Min của 2 giá trị(thủ tục tìm giá trị lớn nhất giữa hai giá trị) int Max(int x, int y) int Min(int x, int y) { int tam; tam=(x>=y)? y:x; return tam; } { int tam; tam=(x>=y)? x:y; return tam; } Các hàm kiểm tra điểm P ở bên trong / bên ngồi đa giác BOOL TestPoint_Boundary (CPoint P,UINT n,CPoint dayP[]) BOOL Giaodiem(CPoint P,UINT n,CPoint dayP[]) void CKiemTra2DView::OnTestDiem() Các hàm kiểm tra quan hệ giữa 2 đường thẳng double LengthOfSegment(CPoint A,CPoint B) void CKiemTra2DView::OnTinhgoc() void CKiemTra2DView::OnHinhchieu() UINT Intersect(CPoint A,CPoint B,CPoint C,CPoint D,CPoint &M) Các hàm kiểm tra quan hệ giữa đoạn thẳng và đa giác void Trungdiem(CPoint A,CPoint B,CPoint &TDiem) void ClippingLine(CPoint A,CPoint B,UINT nDinh,CPoint DGiac[], CPoint DsachDcat[],UINT &SoDcat) void CKiemTra2DView::OnDoanthang_Dagiac() Hàm kiểm tra Đa giác lồi hay lõm? long Toado(CPoint A, CPoint B) void CKiemTra2DView:: OnTest2Dagiac() Hàm tính diện tích của đa giác void CKiemTra2DView::OnTinhdientich() Nhóm các hàm có liên quan tới phép chiếu song song và phối cảnh void InitProjection(double &t1,double &t2,double &t3,double &t4,double &t5,double &t6,double &t7,double &t8,float xRot,float yRot) void Projection(BOOL PhepChieu ,float xRot,float yRot, Wireframe &WF) void CKiemTra2DView:: OnChieuPhoiCanh() void CKiemTra2DView::OnUpdateChieuPhoiCanh(CCmdUI* pCmdUI) void CKiemTra2DView:: OnChieuSongSong() void CKiemTra2DView::OnUpdateChieuSongSong(CCmdUI* pCmdUI) Nhóm hàm liên quan đến các thao tác của hình lăng trụ void CKiemTra2DView:: OnLangTru() void CKiemTra2DView::OnChieuLangTru() void CKiemTra2DView::OnKeyDown(UINT nChar, UINT nRepCnt, UINT nFlags) Nhóm hàm liên quan đến các thao tác của hình chóp void CKiemTra2DView::OnNhapDinhChop() void CKiemTra2DView:: OnChieu_Chop() Nhóm hàm liên quan đến các thao tác của hình nón void CKiemTra2DView::OnHinhnon() void CKiemTra2DView::OnChieu_Non() Các hàm kiểm tra tính đồng phẳng của đa giác void CKiemTra2DView::OnNhapDagiac() void CKiemTra2DView::PlanarPolygon() Tô màu đa giác void CKiemTra2DView::OnTomaudagiac() Kiểm tra quan hệ giữa 2 đa giác void CKiemTra2DView::OnTest2Dagiac() Những hàm được sử dụng trong lớp CKiemTra2DDoc.cpp CkiemTra2DDoc::CkiemTra2DDoc() CkiemTra2DDoc::~ CkiemTra2DDoc() BOOL CkiemTra2DDoc::OnNewDocument() void CkiemTra2DDoc::Serialize(CArchive& ar) IV. CÁCH TỔ CHỨC CÁC HÀM TRONG OPENGL 3D Trong phần kiểm tra trong 3D, có các phương thúc xử lý các thao tác như sau: Những hàm được sử dụng trong lớp CkiemTra3Dview Construction/destruction lớp CView CKiemTra3DView::CKiemTra3DView() CKiemTra3DView::~CKiemTra3DView() Các hàm tạo cửa sổ, vẽ của lớp CView BOOLCKiemTra3DView::PreCreateWindow(CREATESTRUCT& cs) void CKiemTra3DView::OnDraw(CDC* pDC) void CKiemTra3DView::AssertValid() const void CKiemTra3DView::Dump(CDumpContext& dc) const Hàm tạo ngữ cảnh để phù hợp với việc vẽ các vật thể 3D int CKiemTra3DView::OnCreate(LPCREATESTRUCT pCreateStruct) Các hàm điều chỉnh kích thước, tạo màu nền void CKiemTra3DView::OnDestroy() void CKiemTra3DView::OnSize(UINT nType, int cx, int cy) BOOL CKiemTra3DView::OnEraseBkgnd(CDC* pDC) void CKiemTra3DView::GLResize(GLsizei w, GLsizei h) void CKiemTra3DView::GLSetupRC() void CKiemTra3DView::Khoitaopalette() BOOL CKiemTra3DView::OnQueryNewPalette() void CKiemTra3DView::OnPaletteChanged(CWnd* pFocusWnd) Hàm nhấn các phím mũi tên để quan sát vật thể void CkiemTra3Dview::OnKeyDown(UINT nChar, UINT nRepCnt, INT Flags) Các hàm thực hiện các thao tác nhập tọa độ cho mặt phẳng, điểm, đường thẳng void CKiemTra3DView:: OnNhapMPhang1() void CKiemTra3DView:: OnNhapMPhang2() void CKiemTra3DView:: OnNhapTDDiem() void CKiemTra3DView:: OnNhapTDDuong1() void CKiemTra3DView:: OnNhapTDDuong2() Các hàm thực hiện các thao tác kiểm tra, tính tốn giữa các đối tượng điểm, đường thẳng, mặt phẳng. void CKiemTra3DView:: OnKtraDiemMP() void CKiemTra3DView:: OnVeGiao2MP() void CKiemTra3DView:: OnKtraDiem_Duong() void CKiemTra3DView:: OnKtra2DThang() void CKiemTra3DView:: OnKtraDuong_MP() void CKiemTra3DView:: OnTinhGoc2MP() void CKiemTra3DView:: OnTinhGocDuong_MP() void CKiemTra3DView:: OnTinhGoc2DT() void CKiemTra3DView:: OnTinhKCDiem_Duong() void CKiemTra3DView:: OnTinhKC2Duong() void CKiemTra3DView:: OnTinhKC2MP() void CKiemTra3DView:: OnDiemDongPhang() void CKiemTra3DView:: Ve_Hai_MP() void CKiemTra3DView:: On2MPhang() void CKiemTra3DView:: GT_hai_mp1() void CKiemTra3DView:: GT_hai_mp3() void CKiemTra3DView:: OnVe_KC_Diem_MP() void CKiemTra3DView:: OnTinh_KC_Diem_MP() void CKiemTra3DView:: Ve_Diem_MP() Các hàm thực hiện việc vẽ, demo các vật thể void CKiemTra3DView:: GLRenderScene() void CKiemTra3DView:: Cube() void CKiemTra3DView:: HinhChop() void CKiemTra3DView:: Wireframchop() void CKiemTra3DView:: OnCube() void CKiemTra3DView:: Onscence() void CKiemTra3DView:: OnHinhchop() void CkiemTra3Dview:: OnWireframWireframchop() Hàm thực hiện thao tác xố màn hình void CKiemTra3DView:: OnClearScreen() Những hàm được sử dụng trong lớp CkiemTra3Ddoc CkiemTra3DDoc:: CkiemTra3DDoc() CkiemTra3DDoc:: ~ CkiemTra3DDoc() BOOL CkiemTra3DDoc:: OnNewDocument() void CkiemTra3DDoc:: Serialize(CArchive& ar) PHẦN IV: HƯỚNG DẪN SỬ DỤNG CHƯƠNG TRÌNH Trong phần này, tôi sẽ đề cập cách sử dụng các thao tác của việc kiểm tra các quan hệ hình học trong phần 2D và 3D. I. Giao diện phần 2D Màn hình giao diện chính của chương trình, người sử dụng có thể xem các thông tin về chương trình và chọn thao tác kiểm tra trong 2D và 3D. Giao diện bao gồm 4 thao tác: Kiểm tra 2D. Kiểm tra 3D. Đề tài. Thốt chương trình. Màn hình làm việc trong phần 2D, bao gồm các đề mục như thao tác trong 2D, thao tác trong 3D và các thao tác xử lý tương ứng. Người sử dụng có thể dùng phím Enter hay tổ hợp các phím để chọn các thao tác phù hợp. Trong phần kiểm tra 2D bao gồm các đối tượng điểm, đường thẳng, đa giác và các thao tác kiểm tra tương ứng với các đối tượng hình học này. Màn hình làm việc khi người dùng chọn một trong các thao tác kiểm tra giữa các đối tượng hình học II. Giao diện phần 3D Trong phần 3D, tôi xin giới thiệu một số hình ảnh demo chương trình Kiểm tra điểm có đồng phẳng với mặt phẳng hay không? Vẽ vật thể phụ thuộc vào yêu cầu người dùng III. Đề nghị hướng phát triển Tạo thêm những chức năng kích hoạt lại những đối tượng hình học khi đã được thể hiện trên vùng Client như: Kéo giản kích thước Dịch chuyển những đối tượng tuỳ ý Cập nhật lại dữ liệu cho các vị trí mới Từ những tương quan cơ bản đã đựơc thiết kế của đề tài này, xây dựng lên nhiều bài tốn hình học khác. TÀI LIỆU THAM KHẢO š¤› [1] Lê Tấn Hùng, Huỳnh Quyết Thắng, Kỹ thuật đồ họa, Nhà xuất bản Khoa Học và Kỹ Thuật 2000. [2] Lê Minh Trí, Kỹ năng lập trình Windows bằng Visual C++ 6.0 (Tập 1 và 2), Nhà xuất bản Thanh Niên 2001. [3] Dương Quang Thiện, Lập trình Windows dùng Visual C++ 5.0 và MFC (Tập 1, 2 và 3), Nhà xuất bản Thống Kê 1998. [4] Dương Quang Thiện, Nhập môn lập trình Windows dùng Visual C++, Nhà xuất bản Thống Kê 1998. [5] Trần Quốc Bình, Học Visual C++ 6 trong 21 ngày, Nhà xuất bản Mũi Cà Mau. [6] FrancisS.Hill,Jr, Computer Graphics, Nhà xuất bản MacMillan 1990. [7] Richard S. Wright, Jr , Michael Sweet, OpenGL SuperBible, Waite Group Press 1996. [8] David J. Kruglinski, Inside Visual C++ (Fourth Edition), Microsoft Press 1997.