Trình bày thuật toán về Elipse Midpoint ứng dụng xây dựng và cài đặt chương trình

Chia sẻ: Nguyễn Mạnh Tuấn | Ngày: | Loại File: DOC | Số trang:11

Thêm vào BST

Báo xấu

453
lượt xem 44
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đồ họa là một trong những lĩnh vực phát triển rất nhanh của ngành Công nghệ thông tin. Nó được ứng dụng rộng rãi trong nhiều lĩnh vực khoa học và công nghệ. Chẳng hạn như y học, kiến trúc, giải trí... Đồ họa máy tính đã giúp chúng ta thay đổi cách cảm nhận và sử dụng máy tính, nó đã trở thành những công cụ trực quan quan trọng không thể thiếu trong đời sống hằng ngày. Vì vậy môn “Kỹ thuật đồ họa” đã trở thành một trong những môn học chính trong các chuyên ngành Công...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Trình bày thuật toán về Elipse Midpoint ứng dụng xây dựng và cài đặt chương trình

GV : VŨ TẤT THẮNG NHÓM 25 Trêng ®¹i häc ®iÖn lùc hµ néi  B¸o c¸o kü thuËt ®å häa m¸y tÝnh ‘’Tr×nh bµy thuËt to¸n vÏ Ellipse midpoint, øng dông x©y dùng vµ cµi ®Æt ch¬ng tr×nh vÏ ellipse” Gi¸o viªn híng dÉn: Vò TÊt Th¾ng Nhãm thùc hiÖn : Nhãm 25 Líp : D6LT CNTT - 2012-
GV : VŨ TẤT THẮNG NHÓM 25 Mục lục A. LỜI MỞ ĐẦU ................................................................ 3 CHÚNG EM XIN CHÂN THÀNH C ÁM ƠN! .............. 3 B. PHẦN NỘI DUNG ......................................................... 4 1. Giải thuật Midpoint vẽ elip ........................................... 4 2. Lưu đồ ........................................................................... 6 3. Ứng dụng thuật giải midpoint vào xây dựng chương trình vẽ ellipse ................................................................. 7 4. Kết quả chạy chương trình ......................................... 10 Hình ảnh 1: .................................................................. 10 Hình ảnh 2: .................................................................. 10 Hình ảnh 3: .................................................................. 11
GV : VŨ TẤT THẮNG NHÓM 25 A. LỜI MỞ ĐẦU Đồ họa là một trong những lĩnh vực phát triển rất nhanh của ngành Công nghệ thông tin. Nó được ứng dụng rộng rãi trong nhiều lĩnh vực khoa học và công nghệ. Chẳng hạn như y học, kiến trúc, giải trí... Đồ họa má y tính đã giúp chúng ta tha y đổi cách cảm nhận và sử dụng má y tính, nó đã trở thành những công cụ trực quan quan trọng không thể thiếu trong đ ời sống hằ ng ngà y. Vì vậ y môn “Kỹ thuật đồ họa” đã trở thành một trong những môn học chính trong các chuyê n ngà nh Công nghệ thông tin ở các trường đại học. Là sinh viên trường ĐH Điện Lực, chúng em tự hào khi được học tập trong một môi trường học năng động, sáng tạo với phương pháp dạy mới tạo điều kiện cho sinh viên được phát huy khả năng của mình. Dưới sự hướng dẫn của thầy VŨ TẤT THẮNG, chúng em đã được tiếp xúc làm quen với một số k ỹ thuật đồ họa máy tính thông qua các bài giảng của thầy và giáo trình cũng như tham khảo một số bài tập, hướng giải quyế t bài toán thầy đã nêu . Sau khi tìm hiểu và học tập hết sức nghiêm túc cùng với tinh thần ham học hỏi, tìm tòi, nghiên cứu của cả nhóm chúng em trong suốt thời gian qua, chúng em đã hoàn thành đề tài “Trình bày thuật toán vẽ ellipse midpoint, ứng dụng xây dựng và cài đặt chương trình vẽ ellipse”. Mặc dù đã rất cố gắng song do hạn chế về kiến thức và thời gian nên có thể bài viết của chúng em sẽ còn có nhiều thiếu sót nhất định, nên chúng em rất mong nhận được sự góp ý từ thầy giáo và các bạn. CHÚNG EM XIN CHÂN THÀNH C ÁM Ơ N!
GV : VŨ TẤT THẮNG NHÓM 25 B. PHẦN NỘI DUNG 1. Giải thuật Midpoint vẽ elip Đây là phương pháp vẽ elip đạt được kết quả tốt về số phép tính và độ phức tạp của chúng y T yi (x/a)2 + (y/b)2 = 1 y i -1 S Part 1 Q b yj Part 2 y j -1 U V xj+1 x O xj xi xi+1 b Do đặc điểm của elip nên chúng ta chỉ khảo sát đường cong biểu diễn elip trong góc phần tư thứ nhất. Ta viết lại phương trình của elip có tâm là gốc toạ độ bán trục lớn là a bán trục nhỏ là b dưới dạng sau: < 0 nếu (x,y) nằm bên trong elip 22 22 22 = 0 nếu (x,y) nằm trên elip f(x,y) = b x + a y – a b > 0 nếu (x,y) nằm bên ngoài elip. *Ý tưởng của giải thuật: Chia elip làm hai phần tại điểm Q nơi độ dốc của tiếp tuyến với elip bằng -1 (véc tơ gradient bằng 1). Tại vùng thứ nhất x biến thiên nhanh hơn y, tại vùng thứ hai y biến thiên nhanh hơn x. Xin hãy nhớ lại độ dốc của đường cong định nghĩa bởi công thức dx/dy = fx/fy ; trong đó fx và fy là đạo hàm riêng phần của f(x,y) theo x theo y: fx = 2b2x còn fy = 2a2y. Tại mỗi phần được chọn giải thuật Midpoint tương tự như vẽ đường tròn đã trình bày:  Trong phần 1:Giả sử đã vẽ được điểm (xi,yi) tìm cách xác định điểm tiếp theo trên elip. Ứng cử viên cho bước i +1 là T hoặc S. Biến cầm canh
GV : VŨ TẤT THẮNG NHÓM 25 quyết định ứng cử viên nào được tính theo giá trị của hàm f(x,y) theo tại điểm I là trung điểm của TS: di = f(xi + 1, yi – ½) = b2(xi + 1)2 + a2(yi – ½)2 – a2b2 (biến cầm canh). + Nếu di ≥ 0 trung điểm I nằm ngoài đường tròn  điểm được chọn là S + Nếu di < 0 trung điểm I nằm trong đường tròn  điểm được chọn là T. Biến cầm canh trong bước tiếp theo: di+1 = f(xi+1 + 1, yi+1 – ½) = b2(xi+1 +1)2 + a2(yi+1 – ½)2 – a2b2. Phần chênh lệch giữa hai biến cầm canh trong hai bước là: di+1 – di = b2[(xi+1 +1)2 – (xi +1)2] +a2[(yi+1 – ½)2 – (yi – ½)2]. Vì xi+1 = xi+1 nên có thể rút gọn hiệu trên như sau: di+1 – di = 2b2xi+1 + b2 + a2[(yi+1 – ½)2 – (yi – ½)2] + Nếu điểm được chọn là T (di < 0) thì yi+1 = yi  di+1 = di + 2b2xi+1 + b2 (= di + fx + b2) + Nếu điểm được chọn là S (di ≥ 0) thì yi+1 = yi + 1 di+1 = di + 2b2xi+1 + b2 – 2a2yi+1 (= di + fx + b2 – fy) Giá trị khởi tạo của biến cầm canh:  d1 = f(0,b) = b2 + a2(b – ½)2 – a2b2 = b2 ─ a2b + a2/4  Trong phần 2: Ta tính toán tương tự như phần 1; Giả sử ta phải xác định toạ độ (xj+1,yj+1) trong bước j+1. Ứng cử viên là U hoặc V. Gọi K là trung điểm của UV. Khi đó K nằm trong hay nằm ngoài elip sẽ quyết định việc chọn điểm V hay điểm U. Biến cầm canh được tính bằng giá trị của f(x,y) tại điểm K như sau: ej = f(xj + ½, yj – 1) = b2(xj + ½)2 + a2(yj – 1)2 – a2b2 (Biến cầm canh) + Nếu ej ≥ 0 điểm được chọn là U + Nếu ej < 0 điểm được chọn là V Giá trị của biến cầm canh trong bước tiếp theo: ej+1 = f(xj+1 + ½, yj+1 – 1) = b2(xj+1 + ½)2 + a2(yj+1 – 1)2 – a2b2 Độ lệch giữa hai giá trị biến cầm canh trong hai bước liên tiếp là: (chú ý yj+1 = yi – 1) ej+1 – ej = b2[(xj+1 + ½)2 – (xj + ½)2] + a2[(yj+1 – 1)2 – (yj – 1)2] = b2[(xj+1 + ½)2 – (xj + ½)2] – 2a2yj+1 + a2 + Nếu điểm được chọn là U tức ej ≥ 0 thì xj+1 = xj
GV : VŨ TẤT THẮNG NHÓM 25  ej+1 = ej – 2a2yj+1 + a2 (= ej – fy + a2) + Nếu điểm được chọn là V tức ej < 0 thì xj+1 = xj+1  ej+1 = ej + 2b2xj+1 – 2a2yj+1 + a2 (= ej + fx – fy + a2) Giá trị khởi tạo của biến cầm canh trong phần 2 phụ thuộc vào vị trí cuối cùng của phần 1 (giả sử là (xk,yk). Khi đó: e1 = f(xk + ½, yk – 1) = b2(xk + ½) + a2(yk – 1)2 – a2b2. Chú ý: Để biết khi nào kết thúc phần 1 chuyển qua phần 2 chúng ta theo dõi độ dốc của tiếp tuyến với elip theo đạo hàm riêng phần fx, fy như đã nói. Như đã tìm hiểu: xi+1 = xi + 1 hoặc xi+1 = xi và yi+1 = yi hoặc yi+1 = yi – 1 suy ra đạo hàm riêng phần sẽ được cập nhật thêm 2b2 cho fx hoặc 2a2 cho fy. 2. Lưu đồ BEGIN LƯU ĐỒ ELLIP p = 4B2 – 4A2B + A2 x = 0; y = B; N N 2 2 2 4 y≥0 (A +B )x ≤ A END Yes Yes p=p+8B2x – 8A2y+8A2+12B2; N N p=p–8A2x + 12A2; p
GV : VŨ TẤT THẮNG NHÓM 25 3. Ứng dụng thuật giải midpoint vào xây dựng chương trình vẽ ellipse #include #include #include #define ROUND(a) ((long)(a+0.5)) void plot(int xc, int yc, int x, int y, int color){ putpixel(xc+x, yc+y, color); putpixel(xc-x, yc+y, color); putpixel(xc+x, yc-y, color); putpixel(xc-x, yc-y, color); } void Mid_ellipse(int xc, int yc, int a, int b, int color){ long x, y, fx, fy, a2, b2, p; x = 0; y = b; a2 = a * a; //a2 b2 = b * b; // b2 fx = 0; fy = 2 * a2 * y; // 2a2y plot(xc, yc, x,y, color); p = ROUND(b2-(a2*b)+(0.25*a)); // p=b2 - a2b + a2/4
GV : VŨ TẤT THẮNG NHÓM 25 while (fx < fy){ x++; fx += 2*b2; //2b2 delay(50); if (p0) { y--; fy -= 2*a2; // 2a2 delay(50); if (p>=0)
GV : VŨ TẤT THẮNG NHÓM 25 p+=a2*(3 - 2*y); //p =p + a2(3-2y); else{ x++; fx += 2*b2; // 2b2 p += b2*(2*x+2) + a2*(-2*y +3); //p=p + b2(2x +2) +a2(-2y +3) } plot(xc, yc, x, y, color); } } void main(){ int gr_drive = DETECT, gr_mode; initgraph(&gr_drive, &gr_mode, "D:\\TC\\BGI"); Mid_ellipse(getmaxx() / 2, getmaxy() / 2, 150, 80, 4); getch(); closegraph(); }
GV : VŨ TẤT THẮNG NHÓM 25 4. Kết quả chạy chương trình Hình ảnh 1: Hình ảnh 2:
GV : VŨ TẤT THẮNG NHÓM 25 Hình ảnh 3: