Bài giảng Bài 3: Các giải thuật cơ sở (39 trang) - Lê Tấn Hùng
lượt xem 6
download
Bài giảng "Bài 3: Các giải thuật cơ sở" cung cấp cho người học các kiến thức: Các giải thuật xén tỉa - Clipping, các thuật toán tô miền kín, phép tô mầu, phép xử lý Antialiasing. Đây là một tài liệu tham khảo hữu ích dành cho các bạn sinh viên Công nghệ thông tin và thiết kế đồ họa dùng làm tài liệu học tập và nghiên cứu.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài giảng Bài 3: Các giải thuật cơ sở (39 trang) - Lê Tấn Hùng
- Bài 3: Các giải thuật cơ sở Le Tan Hung hunglt@it-hut.edu.vn 0913030731 (c) SE/FIT/HUT 2002 1
- Nội dung Các giải thuật xén tỉa - Clipping Các thuật toán tô miền kín Phép tô mầu Phép xử lý Antialiasing (c) SE/FIT/HUT 2002 2
- Xén tỉa - Clipping Nhiệm vụ cơ bản trong đồ họa là giữ các phần của đối tượng lựa chọn nằm bên ngoài đồ hoạ. Xén tỉa là việc di chuyển tất cả các đối tượng hoặc các phần của đối tượng thuộc mô hình ngữ cảnh ra bên ngoài của sổ thế giới thực Định nghĩa Việc loại từng điểm ảnh của đối tượng Clipping điểm thường chậm nhất là khi đối tượng mà xmin ≤ x ≤ xmax phần lớn nằm ngoài cửa sổ hiển thị. ymin ≤ y ≤ ymax Kỹ thuật thực hành là cần thiết để nâng cao tốc độ trong thực hiện nhiệm vụ (c) SE/FIT/HUT 2002 3
- Clipping đoạn thẳng Lines are defined by their endpoints, so it should be possible just to examine these (in a similar way to points) and determine whether or not to clip without considering every pixel on the line We often have windows that are either very large, i.e. nearly the whole scene fits inside, or very small, i.e. most of the scene lies inside the window Hence, most lines may be either trivially accepted or rejected (c) SE/FIT/HUT 2002 4
- Giải thuật Cohen Sutherland Outcode The Cohen-Sutherland line-clipping algorithm is particularly fast for “trivial” cases, i.e. lines completely inside or outside the window. Non-trivial lines, i.e. ones that cross a boundary of the window, are clipped by computing the coordinates of the new boundary endpoint of the line where it crosses the edge of the window Each point on all lines are first assigned an “outcode” defining their position relative to the clipping rectangle (c) SE/FIT/HUT 2002 5
- (c) SE/FIT/HUT 2002 6
- Giải thuật Cyrus-Beck Lyang Barsky The Cohen-Sutherland algorithm requires the window to be a rectangle, with edges aligned with the co- ordinate axes It is sometimes necessary to clip to any convex polygonal window, e.g. triangular, hexagonal, or rotated. The, and Liang-Barsky line clippers better optimise the intersection calculations for clipping to window boundary Nicholl-Lee-Nicholl reducing redundant boundary clipping by identifying edge and corner regions (c) SE/FIT/HUT 2002 7
- P1 = − Dx q1 = x1 − xm q = x − x P 2 = Dx 2 M 1 P 3 = − Dy q3 = y1 − ym q4 = y M − y1 P 4 = Dy (c) SE/FIT/HUT 2002 8
- Nếu Pk = 0 : điều đó tương đương với việc đoạn thẳng đang xét song song với cạnh thứ k của hình chữ nhật clipping. a) Nếu qk < 0 ⇒ vô nghiệm) b)Nếu qk >= 0 thì bất phương trình luôn thoả mãn. (c) SE/FIT/HUT 2002 9
- Nếu Pk ≠ 0 : uk = qk/Pk. Pk < 0 • u ≥ qk/Pk Ù u ≥ uk. Pk > 0 • u ≥ uk u ≤ qk/Pk • u ≤ uk với uk = qk/Pk • đoạn thẳng có dạng đi từ trong ra ngoài so với cạnh k. (c) SE/FIT/HUT 2002 10
- Pk < 0 và uk < 0 uk ≤ u< 0 thoả mãn bất phương trình sẽ không nằm trên đoạn thẳng cần xét. => uk sẽ nhận là 0 khi uk 0 và uk > 1 => uk tương ứng sẽ nhận giá trị 1. điểm nằm trong cửa sổ clipping sẽ có dạng như sau: U1 ≤ u ≤ U2 (c) SE/FIT/HUT 2002 11
- qk U 2 = min {1}∪ u k : u k = , Pk > 0 P k qk U 1 = max {0}∪ u k : u k = , Pk < 0 P k (c) SE/FIT/HUT 2002 12
- Nicholl-Lee-Nicholl clipping Some edges are irrelevant to clipping, particularly if one vertex a lies inside region. Cases: x1 in x1 in corner region a x1 in edge region For each case, we generate specialized test regions for x2, which a use simple tests (slope, >,
- Nicholl-Lee-Nicholl (2) Special cases for each endpoint location and slope Number of cases explodes in 3D, making it unsuitable 1 2 Reject 3 Top Left Top, Right 4 Left, bottom Top, Bottom (c) SE/FIT/HUT 2002 14
- Giải thuật đường biên (Boundary - File Algorithm) Giải_thuật_đường_biên ( x, y ) Color : biến mầu Begin Color = Readpixel ( x, y ); If ( Color = mầu tô ) or ( Color = mầu đường biên ) Kết thúc vì chạm biên hoặc chạm phần đã tô Else Giải_thuật_đường_biên ( x+1, y ); Giải_thuật_đường_biên ( x-1, y ); Giải_thuật_đường_biên ( x, y+1 ); Giải_thuật_đường_biên ( x, y-1 ); // Thực hiện lại giải thuật với các điểm lân cận End. (c) SE/FIT/HUT 2002 15
- Giải thuật dòng quét-Scanline cho việc tô mầu vùng round down round up AET = yma current x denominator current numerator (c) SE/FIT/HUT 2002 16 x
- Giải thuật tô vùng kín theo mẫu (Pattern Filling) Phương pháp 1 Phương pháp 2 (c) SE/FIT/HUT 2002 17
- Hiệu ứng răng cưa Aliasing SPATIAL ALIASING, IN PICTURES moire patterns arise in image warping & texture mapping jaggies arise in rendering TEMPORAL ALIASING, IN AUDIO when resampling an audio signal at a lower sampling frequency, e.g. 50KHz (50,000 samples per second) to 10KHz TEMPORAL ALIASING, IN FILM/VIDEO strobing and the “wagon wheel effect” jaggies in foreground. jaggies (c) SE/FIT/HUT 2002 18
- Antialiasing Méo thông tin trong quá trình lấy mẫu tần số thấp sampling frequency In raster images – leads to jagged edges with hiệu ứng bậc thang – staircase effect We can reduce effects by antialiasing methods to compensate for undersampling (c) SE/FIT/HUT 2002 19
- When Does Spatial Aliasing Occur? During image synthesis: when sampling a continuous (geometric) model to create a raster image, e.g. scan converting a line or polygon. Sampling: converting a continuous signal to a discrete signal. During image processing and image synthesis: when resampling a picture, as in image warping or texture mapping. Resampling: sampling a discrete signal at a different sampling rate. Example: “zooming” a picture from nx by ny pixels to snx by sny pixels s>1: called upsampling or interpolation can lead to blocky appearance if point sampling is used s
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng Quản trị mạng Linux: Bài 3 - TC Việt Khoa
33 p | 273 | 73
-
Bài giảng Chương 3: Quy hoạch động
65 p | 290 | 41
-
Bài giảng Quản trị dự án phần mềm - Bài 3: Giai đoạn xác định
30 p | 167 | 31
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 3 - Trần Thị Kim Chi
40 p | 92 | 10
-
Bài giảng Công nghệ đồ họa và hiện thực ảo - Bài 3: Giải thuật sinh các thực thể cơ sở
32 p | 83 | 8
-
Bài giảng Trí tuệ nhân tạo (Artificial intelligence) - Chương 3.3: Giải quyết vấn đề - Tìm kiếm dựa trên thỏa mãn ràng buộc
39 p | 11 | 6
-
Bài giảng Lý thuyết nhận dạng – Chương 3: Nhận dạng mẫu dựa trên thống kê
45 p | 53 | 6
-
Bài giảng Trí tuệ nhân tạo (Artificial intelligence) - Chương 3.1: Giải quyết vấn đề - Tìm kiếm cơ bản
64 p | 12 | 6
-
Bài giảng Kỹ thuật lập trình: Bài 3 - ThS. Trịnh Thành Trung
63 p | 61 | 6
-
Bài giảng Chương 3: Các kỹ thuật xây dựng chương trình phần mềm (Phần 2) - TS. Vũ Thị Hương Giang
135 p | 84 | 6
-
Bài giảng Bài 3: Các giải thuật cơ sở - Lê Tấn Hùng
10 p | 99 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 3 - ThS. Nguyễn Hà Giang
91 p | 71 | 5
-
Bài giảng Tin học đại cương: Bài 3 - TS. Trần Quang Diệu
35 p | 51 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 3: Đệ quy (Recursion)
39 p | 47 | 4
-
Bài giảng Bài 3: Lập lịch
16 p | 75 | 4
-
Bài giảng Tin học đại cương: Chương 3 - ThS. Trần Quang Hải Bằng
18 p | 118 | 3
-
Bài giảng Phân tích thiết kế và giải thuật - Chương 5: Cây 2 – 3 – 4
22 p | 52 | 2
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn