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