Các giải thuật sinh các thực thể cơ sở

1Các giải thuật sinh các thực thể cơ sở Le Tan Hung hunglt@it-hut.edu.vn 0913030731 Rendering Pipeline: 3-D Transform Illuminate Transform Clip Project Rasterize Model & Camera Parameters Rendering Pipeline Framebuffer Display The Rendering Pipeline: 3-D Scene graph Object geometry Lighting Calculations Clipping • Các điểm của hệ thống tọa độ 3D thế giới thực • Các điểm bóng theo mô hình chiếu sáng • Các điểm trong mô hình hệ tọa độ Camera hay tọa độ điểm nhìn • Các tọa độ điểm của vùng hình chóp cụt với điểm nhìn xác định • Điểm 2-D theo tọa độ màn hình sau phép chiếu được xén tỉa Modeling Transforms Viewing Transform Projection Transform Phép biến đổi Transformations z screen space- không gian màn hình z model space Không gian mô hình (a.k.a. object space or world space) z 3 loại phép biến đổi: – Modeling transforms – Viewing transforms – Projection transforms Rendering: Transformations z Modeling transforms – Size, place, scale, and rotate objects parts of the model w.r.t. each other – Object coordinates Æ world coordinates Z X Y X Z Y Rendering: Transformations z Viewing transform – Rotate & translate the world to lie directly in front of the camera z Typically place camera at origin z Typically looking down -Z axis – World coordinates Æ view coordinates 2Rendering: Transformations z Projection transform – Apply perspective foreshortening z Distant = small: the pinhole camera model – View coordinates Æ screen coordinates Rendering: Transformations z All these transformations involve shifting coordinate systems (i.e., basis sets) z Oh yeah, that’s what matrices do z Represent coordinates as vectors, transforms as matrices z Multiply matrices = concatenate transforms! ⎥⎦ ⎤⎢⎣ ⎡⎥⎦ ⎤⎢⎣ ⎡ −=⎥⎦ ⎤⎢⎣ ⎡ ′ ′ Y X Y X θθ θθ cossin sincos Rendering: Transformations z Homogeneous coordinates: represent coordinates in 3 dimensions with a 4-vector – Denoted [x, y, z, w]T z Note that w = 1 in model coordinates – To get 3-D coordinates, divide by w: [x’, y’, z’]T = [x/w, y/w, z/w]T z Transformations are 4x4 matrices z Why? To handle translation and projection The Rendering Pipeline: 3-D Modeling Transforms Scene graph Object geometry Lighting Calculations Viewing Transform Clipping Projection Transform Result: • All vertices of scene in shared 3-D “world” coordinate system • Vertices shaded according to lighting model • Scene vertices in 3-D “view” or “camera” coordinate system • Exactly those vertices & portions of polygons in view frustum • 2-D screen coordinates of clipped vertices Rendering: Ánh sáng - Lighting z Illuminating a scene: coloring pixels according to some approximation of lighting – Global illumination: solves for lighting of the whole scene at once – Local illumination: local approximation, typically lighting each polygon separately z Interactive graphics (e.g., hardware) does only local illumination at run time The Rendering Pipeline: 3-D Modeling Transforms Scene graph Object geometry Lighting Calculations Viewing Transform Clipping Projection Transform Result: • All vertices of scene in shared 3-D “world” coordinate system • Vertices shaded according to lighting model • Scene vertices in 3-D “view” or “camera” coordinate system • Exactly those vertices & portions of polygons in view frustum • 2-D screen coordinates of clipped vertices 3Rendering: Clipping z Clipping a 3-D primitive returns its intersection with the view frustum: Rendering: Xén tỉa - Clipping z Clipping is tricky! – We will have a whole assignment on clipping In: 3 vertices Out: 6 verticesClip Clip In: 1 polygon Out: 2 polygons The Rendering Pipeline: 3-D Transform Illuminate Transform Clip Project Rasterize Model & Camera Parameters Rendering Pipeline Framebuffer Display Modeling: The Basics z Common interactive 3-D primitives: points, lines, polygons (i.e., triangles) z Organized into objects – Collection of primitives, other objects – Associated matrix for transformations z Instancing: using same geometry for multiple objects – 4 wheels on a car, 2 arms on a robot Modeling: The Scene Graph z Đồ thị cảnh scene graph : cây đồ thị lưu trữ đối tượng, quan hệ giũa các đối tượng và các phép biến đổi trên đối tượng đó z Nút là đối tượng; z Cành là các thực thể biến đổi – Tương ứng là các ma trận Robot BodyHead ArmTrunkLegEyeMouth Modeling: The Scene Graph z Traverse the scene graph in depth-first order, concatenating transformations z Maintain a matrix stack of transformations ArmTrunkLegEyeMouth Head Body Robot Foot Matrix Stack Visited Unvisited Active 4Modeling: The Camera z Finally: need a model of the virtual camera – Can be very sophisticated z Field of view, depth of field, distortion, chromatic aberration – Interactive graphics (OpenGL): z Camera pose: position & orientation – Captured in viewing transform (i.e., modelview matrix) z Pinhole camera model – Field of view – Aspect ratio – Near & far clipping planes Modeling: The Camera z Camera parameters (FOV, etc) are encapsulated in a projection matrix – Homogeneous coordinates Æ 4x4 matrix! – See OpenGL Appendix F for the matrix z The projection matrix premultiplies the viewing matrix, which premultiplies the modeling matrices – Actually, OpenGL lumps viewing and modeling transforms into modelview matrix Rời rạc hoá điểm ảnh (Scan Conversion rasterization) z Là tiến trình sinh các đối tượng hình học cơ sở bằng phương pháp xấp xỉ dựa trên lưới phân giải của màn hình z Tính chất các đối tượng cần đảm bảo : – smooth – continuous – pass through specified points – uniform brightness – efficient Biểu diễn đoạn thẳng z Biểu diễn tường minh (y-y1)/( x-x1) = ( y2-y1)/( x2-x1)1 y = kx + m – k = (y2-y1)/( x2-x1) – m = y1- kx1 – Δy = k Δx z Biểu diễn không tường minh (y2-y1)x - (x2-x1)y + x2y1 - x1y2 = 0 hay rx + sy + t = 0 – s = -(x2-x1 ) – r = (y2-y1) và t = x2y1 - x1y2 z Biểu diễn tham biến P(u) = P1 + u(P2 - P1) u [0,1] X = x1 + u( x2 - x1 ) Y = y1 + u( y2 - y1 ) m P(x1, y1) P(x2 , y2) u Sinh đường tròn Scan Converting Circles z Implicit: f(x) = x2+y2-R2 z Explicit: y = f(x) z Parametric: 2 2y R x= ± − cos sin x R y R θ θ = = If f(x,y) = 0 then it is on the circle. f(x,y) > 0 then it is outside the circle. f(x,y) < 0 then it is inside the circle. Usually, we draw a quarter circle by incrementing x from 0 to R in unit steps and solving for +y for each step. - by stepping the angle from 0 to 90 - avoids large gaps but still insufficient. Thuật toán DDA (Digital Differential Analizer) Giải thuật DDA z Với 0 < k < 1 xi+1 = xi + 1 yi+1 = yi + k với i=1,2,3.... Thuậttoán ddaline (x1, y1, x2, y2) x1, y1, x2, y2 : tọa độ 2 điểm đầu cuối k : hệ số góc x,y,m :biến begin m =(x2-x1)/(y2-y1); x = x1; y = y1; k = 1/m; putpixel(x,y); while x<x2 begin x = x+1; y = y+k; putpixel(round(x),round(y)); end; end; Giải thuật thông thường DrawLine(int x1,int y1, int x2,int y2, int color) { float y; int x; for (x=x1; x<=x2; x++) { y = y1 + (x-x1)*(y2-y1)/(x2-x1) WritePixel(x, Round(y), color ); }} 5Giải thuật Bresenham z 1960 Bresenham thuộc IBM z điểm gần với đường thẳng dựa trên độ phân giai hưu hạn z loại bỏ được các phép toán chia và phép toán làm tròn như ta đã thấy trong gỉai thuật DDA z Xét đoạn thẳng với 0 < k < 1 0 1 2 0 1 2 d2 d1 Giải thuật Bresenham d2 = y - yi = k(xi +1) + b - yi d1 = yi+1 - y = yi + 1 - k(xi + 1) - b z If d1 ≤ d2 => yi+1 = yi + 1 else d1 > d2 => yi+1 = yi z D = d1 - d2 = -2k(xi + 1) + 2yi - 2b + 1 z Pi = ΔxD = Δx (d1 - d2) d1 d2 xi xi+1 yi yi+1 Pi = -2Δyxi + 2Δxyi + c Pi+1 - Pi = -2Δy(xi+1 - xi) + 2Δx(yi+1 - yi) z Nếu Pi ≤ 0 ⇒ yi+1 = yi + 1 Pi+1 = Pi - 2Δy + 2Δx z Nếu Pi > 0 ⇒ yi+1 = yi Pi+1 = Pi - 2Δy P1 = Δx(d1 - d2) P1 = -2Δy + Δx Giải thuật Bresenham yi+1 M ( xi , yi ) xi xi+1 Giải thuật trung điểm-Midpoint z Jack Bresenham 1965 / Pitteway 1967 z VanAken áp dụng cho việc sinh các đường thẳng và đường tròn 1985 z Các công thức đơn giản hơn, tạo được các điểm tương tự như với Bresenham z d = F (xi + 1, yi + 1/2) là trung điểm của đoạn AB z Việc so sánh, hay kiểm tra M sẽ được thay bằng việc xét giá trị d. – Nếu d > 0 điểm B được chọn, yi+1 = yi – nếu d < 0 điểm A được chọn. ⇒ yi+1 = yi + 1 – Trong trường hợp d = 0 chúng ta có thể chọn điểm bất kỳ hoặc A, hoặc B. A M B Bresenham’s Algorithm: Midpoint Algorithm z Sử dụng phương pháp biểu diễn không tường minh z Tại mỗi trung điểm của đoạn thẳng giá trị được tính là: z Chúng ta gọi di là biến quyết định của bước thứ i 0=++ cbyax ( ) ( ) ( )iiii iiii iiii yxcbyax yxcbyax yxcbyax ,0 ,0 ,0 ⇒>++ ⇒<++ ⇒=++ on line above line below line ( ) cybxad iii +⎟⎠ ⎞⎜⎝ ⎛ +++= 2 11 Bresenham’s Algorithm: Midpoint Algorithm z If di > 0 then chọn điểm A⇒ trung điểm tiếp theo sẽ có dạng: ( ) bad cybxadyx i iiiii ++= +⎟⎠ ⎞⎜⎝ ⎛ +++=⇒⎟⎠ ⎞⎜⎝ ⎛ ++ + 2 32 2 3,2 1 6Bresenham’s Algorithm: Midpoint Algorithm z if di < 0 then chọn điểm B và trung điểm mới là z Ta có: z Ðiểm đầu ( ) [ ] 2 2 11 2 1,1 bacbyax cybxadyx startstart startstartstartstartstart ++++= +⎟⎠ ⎞⎜⎝ ⎛ +++=⇒⎟⎠ ⎞⎜⎝ ⎛ ++ ( ) ad cybxadyx i iiiii += +⎟⎠ ⎞⎜⎝ ⎛ +++=⇒⎟⎠ ⎞⎜⎝ ⎛ ++ + 2 12 2 1,2 1 Cx x yy xCc xxxb yyya startend startend +Δ Δ= ⎪⎭ ⎪⎬ ⎫ Δ= −=Δ−= −=Δ= where 2 0 ba ++= Midpoint Line Algorithm dx = x_end-x_start dy = y_end-y_start d = 2*dy-dx x = x_start y = y_start while x < x_end if d <= 0 then d = d+(2*dy) x = x+1 else d = d+2*(dy-dx) x = x+1 y = y+1 endif SetPixel(x,y) endwhile initialisation choose B choose A Giải thuật Bresenham's Midpoint z d = a(xi + 1) + b(yi + 1/2) + c z Nếu điểm được chọn là B thi M sẽ tang theo x một đơn vị – di +1 = F(xi +2, yi + 1/2) = a(xi +2) + b(yi + 1/2) + c – di = a(xi + 1) + b(yi + 1/2) + c z Nếu điểm A được chọn thi` M tăng theo 2 hướng x và y với cùng một đơn vị. di + 1 = F (xi + 2, yi + 3/2) – = a(xi + 2) + b(yi +3/2) + c – di + 1 = di + a + b. ¾ Với a + b = dy - dx. d <= 0 B¾t ®Çu x = x1 ; y = y1; dx = x2 - x1; dy = y2 - y1; d = dy - dx/2; Putpixel (x ,y); x < x2 KÕt thóc d = d + dy d = d + dy - dx y = y + 1 yes no No yes x = x + 1 Midpoint Circle Algorithm z Sử dụng phương pháp biểu diễn không tường minh trong giải thuật z Thực hiện giải thuật trên 1/8 đường tròn và lấy đối xứng xho các góc còn lại. z Với di là giá trị của đường tròn tại một điểm bất kỳ ta có ( ) ( ) 0222 =−−+− ryyxx cc ( ) ( ) ( ) circle outside is , if 0 circleon is , if 0 circle inside is , if 0 ⎪⎩ ⎪⎨ ⎧ > = < = ii ii ii i yx yx yx d Midpoint Circle Algorithm z As with the line, we determine the value of the decision variable by substituting the mid-point of the next pixel into the implicit form of the circle: z If di < 0 we choose pixel A otherwise we choose pixel B – Note: we currently assume the circle is centered at the origin ( ) 222 2 11 ryxd iii −⎟⎠ ⎞⎜⎝ ⎛ −++= Midpoint Circle Algorithm z Again, as with the line algorithm, the choice of A or B can be used to determine the new value of di+1 z If A chosen then next midpoint has the following decision variable: z Otherwise if B is chosen then the next decision variable is given by: ( ) 32 2 12 2 1,2 2 2 2 1 ++= −⎟⎠ ⎞⎜⎝ ⎛ −++=⇒⎟⎠ ⎞⎜⎝ ⎛ −+ + ii iiiii xd ryxdyx ( ) 522 2 32 2 3,2 2 2 2 1 +−+= −⎟⎠ ⎞⎜⎝ ⎛ −++=⇒⎟⎠ ⎞⎜⎝ ⎛ −+ + iii iiiii yxd ryxdyx 7Midpoint Circle Algorithm z If we assume that the radius is an integral value, then the first pixel drawn is (0, r) and the initial value for the decision variable is given by: z Although the initial value is fractional, we note that all other values are integers. ⇒ we can round down: r rrrdr −= −⎟⎠ ⎞⎜⎝ ⎛ +−+=⇒⎟⎠ ⎞⎜⎝ ⎛ − 4 5 4 11 2 1,1 220 rd −=10 Midpoint Circle Algorithm d = 1-r x = 0 y = r while y < x if d < 0 then d = d+2*x+3 x = x+1 else d = d+2*(x-y)+5 x = x+1 y = y-1 endif SetPixel(cx+x,cy+y)endwhile initialisation choose B choose A Translate to the circle center stop at diagonal ⇒ end of octant Scan Converting Ellipses z 2a is the length of the major axis along the x axis. z 2b is the length of the minor axis along the y axis. z The midpoint can also be applied to ellipses. z For simplicity, we draw only the arc of the ellipse that lies in the first quadrant, the other three quadrants can be drawn by symmetry 2 2 2 2 2 2( , ) 0F x y b x a y a b= + − = Scan Converting Ellipses: Algorithm z Firstly we divide the quadrant into two regions z Boundary between the two regions is – the point at which the curve has a slope of -1 – the point at which the gradient vector has the i and j components of equal magnitude 2 2( , ) / / 2 2grad F x y F x F y b x a y=∂ ∂ +∂ ∂ = +i j i j A M tiep tuyen = -1 B gradient B C M i Ellipses: Algorithm (cont.) z At the next midpoint, if a2(yp-0.5)2 z In region 1, choices are E and SE – Initial condition: dinit = b2+a2(-b+0.25) – For a move to E, dnew = dold+DeltaE with DeltaE = b2(2xp+3) – For a move to SE, dnew = dold+DeltaSE with DeltaSE = b2(2xp+3)+a2(-2yp+2) z In region 2, choices are S and SE – Initial condition: dinit = b2(xp+0.5)2+a2((y-1)2-b2) – For a move to S, dnew = dold+Deltas with Deltas = a2(-2yp+3) – For a move to SE, dnew = dold+DeltaSE with DeltaSE = b2(2xp+2)+a2(-2yp+3) z Stop in region 2 when the y value is zero. Ký tự Bitmap z Trên cơ sỏ định nghĩa mỗi ký tự với một font chư cho trước là một bitmap chữ nhật nhỏ z Font/typeface: set of character shapes z fontcache – các ký tự theo chuỗi liên tiếp nhau trong bộ nhớ z Dạng cơ bản – (thường N, nghiêng I, đậm B, nghiêng đậm B+I) z Thuộc tính – Also colour, size, spacing and orientation ab 8Cấu trúc font chữ Typedef struct { int leftx, int width; } Char location; //Vị trí của text Typedef struct { CacheId; Heiglit; // Độ rộng chữ CharSpace; // Khoảng cách giữa các ký tự Charlocation Table [128]; } fontcache Ký tự vector z Xây dựng theo phương pháp định nghĩa các ký tự bởi đường cong mềm bao ngoài của chúng. z Tốn kém nhất về mặt tính toán z Chất lượngcao So sánh z Đơn giản trông việc sinh ký tự ( copypixel) z Lưu trữ lớn z Các phép biến đổi (I,B, scale) đòi hỏi lưu trữ thêm z Kích thước không dổi z Phức tạp (Tính toán phương trình) z Lưu trữ gọn nhẹ z Các phép biến đổi dựa vào các công thức biến đổi z Kích thước phụ thuôc vào môi trường ( ko có kích thước cố định) Giải thuật đường quét sinh đa giác Polygon Scan Conversion z Tồn tại rất nhiều giải thuật sinh đa giác. z Mỗi giải thuật phục vụ cho 1 loại đa giác nhất định: – some algorithms allow triangular polygons only – others require that the polygons are convex and non self- intersecting and have no holes triangular convex non-convex self-intersecting religious Polygon Scan Conversion z Polygon scan conversion là giải thuật chung kinh điển cho các loại khác nhau z Cho mỗi đoạn thẳng quét, chúng ta xác định các cạnh của đa giác cắt đoạn thẳng compute spans representing the interior portions of the polygons along this scan-line and fill the associated pixels. z This represents the heart of a scan-line rendering algorithm used in many commercial products including Renderman and 3D Studio MAX. Polygon Scan Conversion z Dùng giải thuật (trung điểm) để xác định các điểm biên cho mỗi đa giác theo thứ tự tăng của x. z Các diểm phải: – Không bị chia sẻ bởi các đa giác lân cận – Các đa giác chỉ toàn các điểm cạnh( điểm biên) z Đảm bảo các đa giác chia sẻ điểm biên mà không chia sẻ các điểm ảnh bên trong của mình. 9Polygon Scan Conversion z Thủ tục chung: – Xác định giao của đường thẳng quét với cạnh đa giác – Sắp xếp các giao điểm theo mức độ tăng dần của x value – Điền các điểm ảnh vào giữa cặp các điểm x z Need to handle 4 cases to prevent pixel sharing: – if intersection has fractional x value, do we round up or down? z if inside (on left of span) round up, if outside (on right) round down – what happens if intersection is at an integer x value? z if on left of span assume its interior otherwise exterior – how do we handle shared vertices? z ignore pixel associated with ymax of an edge – how do we handle horizontal edges? z handled as a result of previous rule (lower edges not drawn) Polygon Scan Conversion rounded down for A rounded up for B integer x value is on right = exterior ymax not included horizontal edge removed Polygon Scan Conversion z Determining intersections with polygon edges is expensive – rather than re-computing all intersections at each iteration, use incremental calculations – i.e. if we intersect edge e on scan-line i then it is likely we will intersect the edge on scan-line i+1 (this is known as edge- coherence) z Assume slope of the edge > 1 (other edges obtained via symmetries) – incremental DDA calculation was: – slope m is given by – note that numerator and denominator are integral ⇒ we can use integer DDA. m xxyy iiii 1,1 11 +=+= ++ ( ) ( )startend startend xx yym − −=