Tổng hợp bài giảng môn Đồ họa và hiện thực ảo| Trường Đại học Bách Khoa Hà Nội
1960 William Fetter (Thuật ngữ kỹ thuật đồ hoạ máy tính (Computer Graphics); 1960 - SAGE (Semi-Automatic
Ground Environment System) Bút sáng; 1960-1963 Dự án Sketchpad tại MIT; 1963 Ivan shutherland (hội nghị Fall
Joint Computer - lần đầu tiên khả năng tạo mới, hiển thị và thay đổi được thực hiện trong thời gian thực trên màn CRT)
Preview text:
Khoa CNTT - ĐHBK Hà nội Email: hunglt@it-hut.edu.vn Tel: 0913030731
A Brief History of Computer Graphics Lesson 1:
Kỹ thuật đồ họa và Hiện thực ảo
Computer Graphics And Virtual Reality 1885 - CRT (Cathode Ray Tube) 1887 - Edison patents motion z
Kỹ Thuật đồ họa cơ sở picture camera z
Kỹ Thuật đồ họa tiên tiến z Hiện thực ảo - VRML 1888 - Edison and Dickson Le Tan Hung hunglt@it-hut.edu.vn record motion picture photos on a wax cylinder 1 2
A Brief History of Computer Graphics Computer Graphics: 1960-1970 1926 – J.L. Baird z
1960 William Fetter (Thuật ngữ kỹ thuật
đồ hoạ máy tính (Computer Graphics) invents the z 1960 - SAGE (Semi-Automatic Ground Environment System z Ivan Sutherland’s PhD television. ) Bút sáng thesis at MIT
– Vấn đề tương tác người z
1960-1963 Dự án Sketchpad tại MIT máy z
1963 Ivan shutherland (hội nghị Fall – Loop
Joint Computer - lần đầu tiên khả năng 30 line vertical, z Display something
tạo mới, hiển thị và thay đổi được thực z User moves light pen black and red scan.
hiện trong thời gian thực trên màn z Computer generates new CRT) display z Wireframe graphics
– Sutherland tạo ra rất nhiều z Display Processors thuật toán cho CG z Storage tube 3 4
A Brief History of Computer
A Brief History of Computer Graphics Graphics 1963 z 1966 Ralph Baer creates the 1st comsumer CG z IBM creates the 360 models product:
– One of the First General Purpose – Odyssey Pinball Mainframes z 1967 z SRI develops the mouse.
– GE introduces first full colour
real time flight simulator for NASA 5 6 1 Khoa CNTT - ĐHBK Hà nội Email: hunglt@it-hut.edu.vn Tel: 0913030731
Lịch sử phát triển
A Brief History of Computer 1970-1980 Graphics 1973 z CG:1970-1980
z Michael Crichton’s “Westworld” z Raster Graphics uses 2D graphics z Beginning of graphics z
First time computer is used for image standards manipulation. z Featured scenes that showed – IFIPS
audiences the world viewed by the
eye circuitry of a synthetic human z GKS: European effort
(played by a very real Yul Brenner) in
– Becomes ISO 2D standard
a future Western theme park. This z Core: North American effort
effect was achieved with 2D computer –
3D but fails to become ISO
graphics tools mostly derived from standard image processing techniques. 7 8
A Brief History of Computer
A Brief History of Computer Graphics Graphics 1974
z 1977 Star Wars wins oscar for special effects.
z Intel develop the 8080 processor.
z 1978 Superman wins oscar for special 1975 effects z Mandelbrot plots fractals z Bill Gates starts Microsoft
z 1979 Alien wins oscar for visual effects. 1976
z 1980 The Empire Strikes Back wins oscar
z Steve Jobs and Steve Wozniak start Apple. for visual effects. 1977
z Academy of Motion Pictures Art and Sciences
introduces Visual Effects category for Oscars. 9 10
A Brief History of Computer 80-90 Graphics z CG: 1980-1990
1981 IBM introduces the first IBM PC (16 bit 8088 – Special purpose hardware chip)
z Silicon Graphics geometry engine
– VLSI implementation of graphics pipeline – Industry-based standards z PHIGS • Raiders of the z RenderMan Lost Ark wins
– Networked graphics: X Window System an oscar for
– Human-Computer Interface (HCI) visual effects. 11 12 2 Khoa CNTT - ĐHBK Hà nội Email: hunglt@it-hut.edu.vn Tel: 0913030731
A Brief History of Computer
A Brief History of Computer Graphics Graphics 1982 1983 z 1984 PIXAR Opens z The Genesis Effect (ILM) z First Coke Polar Bears
for Startrek II is the first all Commercial computer animated visual effects shot for film. 13 14
A Brief History of Computer
Lịch sử phát triển Graphics 90-00 1985 z CGraphics: 2000-03 z CGraphics: 1990-2000 z Photorealism z
The Last Starfighter is the first live z OpenGL API
action feature film with realistic z Graphics cards for PCs
z Tạo ra bộ phim hoạt hình hoàn
computer animation of highly detailed dominate market models.
chỉnh đầu tiên (Toy Story) – Nvidia, ATI, 3DLabs 1989
z Khả năng mới của phần z Game boxes and game players cứng push the market z
The Abyss is the first movie to include
convincing 3D character animation. – Texture mapping
z CGraphics trở thành công cụ – Blending
cho công nghiệp sản xuất
– Accumulation, stencil buffer phim: Maya, Lightwave 15 16
A Brief History of Computer
A Brief History of Computer Graphics Graphics 1995 1996 z Quake Released by z Independence Day wins Id Software oscar for visual effects. z Toy Story becomes 1997 the first fully 3D computer animation
z Titanic wins oscar for visual feature film. effects. z PIXAR wins oscar for best short film: Geri’s Game. 17 18 3 Khoa CNTT - ĐHBK Hà nội Email: hunglt@it-hut.edu.vn Tel: 0913030731
A Brief History of Computer
A Brief History of Computer Graphics Graphics 1998 2000 2002 Microsoft’s XBOX z Armageddon z Sony Playstation II z Mouse Hunt z Walking with Dinosaurs z Bugs Life z Disney’s Shrek 1999 z The Matrix z Star Wars: The Phantom Menace z Disney’s Tarzan 19 20
Kỹ thuật đồ họa vi tính
Kỹ thuật đồ hoạ điểm . (Sample based-Graphics) z Definition (ISO) –
Method and Technologies for converting data to and from a
graphics devices via a computer
z Các mô hình, hình ảnh của các đối tượng được hiển thị
z Computer Graphics (Kỹ thuật đồ hoạ máy tính) là một lĩnh
thông qua từng pixel (từng mẫu rời rạc)
vực của Công nghệ thông tin mà ở đó nghiên cứu, xây z Đặc điểm:
dựng và tập hợp các công cụ (mô hình lý thuyết và phần
– Có thể thay đổi thuộc tính mềm) khác nhau để:
– Xoá đi từng pixel của mô hình và hình ảnh các đối tượng.
z kiến tạo, lưu trữ, xử lý Các mô hình (model) và hình ảnh –
Các mô hình hình ảnh được hiển thị như một lưới điểm (grid) các (image) của đối tượng pixel rời rạc,
z Computer graphics deals with all aspects of creating –
Từng pixel đều có vị trí xác định, được hiển thị với một giá trị rời rạc images with a computer
(số nguyên) các thông số hiển thị (màu sắc hoặc độ sáng)
– Tập hợp tất cả các pixel của grid cho chúng ta mô hình, hình ảnh đối
Interactive Computer Graphics: - user controls contents, structure, and
tượng mà chúng ta muốn hiển thị
appearance of objects and their displayed images via rapid visual feedback. 21 22 Bitmap Pascal / C
Kỹ thuật đồ hoạ vector program SRGP
z Mô hình hình học (geometrical library
model) cho mô hình hoặc hình ảnh Graphical Rendering của đối tượng graphics algorithms Model Parameters positions
z Xác định các thuộc tính của mô lines,areas,... colour hình hình học này,
z Quá trình tô trát (rendering) để hiển X Window
thị từng điểm của mô hình, hình System Graphics hardware
ảnh thực của đối tượng Rendering
z Vector = geometrical model + rendering Image
image formats, compression, transfer Output 23 24 Device 4 Khoa CNTT - ĐHBK Hà nội Email: hunglt@it-hut.edu.vn Tel: 0913030731
Ví dụ về hình ảnh đồ hoạ Vector Wireframe Model Skeletal Model Muscle Model © Walt Disney and TSL 25 26 Skin Hair Render and Touch up
Phân loại các lĩnh vực của
Raster and Vector Graphics Computer Graphics z Raster –
Hình ảnh và mô hình của các vật thể được biểu diễn bởi tập hợp các CAD/CAM System điểm của grid KiÕn t¹o ®å –
Thay đổi thuộc tính của các pixel => thay đổi từng phần và từng vùng ho¹ §å ho¹ minh ho¹ của hình ảnh. –
Copy được các pixel từ một hình ảnh này sang hình ảnh khác. §å ho¹ ho¹t h×nh vµ z Vector Kü thuËt ®å nghÖ thuËt
– Không thay đổi thuộc tính của từng điểm trực tiếp ho¹
– Xử lý với từng thành phần hình học cơ sở của nó và thực hiện quá Xö lý ¶nh
trình tô trát và hiển thị lại. Xö lý ®å Kü thuËt nhËn d¹ng
– Quan sát hình ảnh và mô hình của hình ảnh và sự vật ở nhiều góc ho¹
độ khác nhau bằng cách thay đổi điểm nhìn và góc nhìn. Kü thuËt ph©n tÝch vµ t¹o ¶nh 27 28
Phân loại theo hệ toạ độ
Phân loại theo chức năng
Kü thuËt ®å ho¹ 2 chiÒu
z Kỹ thuật xử lý ảnh (COMPUTER IMAGING) Kü thuËt ®å ho¹
z Kỹ thuật nhận dạng (Computer Vision techniques
Kü thuËt ®å ho¹ ba chiÒu
attempt to provide meaning to computer) images.
Kỹ thuật đồ hoạ hai chiều: là kỹ thuật đồ hoạ máy tính sử dụng hệ
toạ độ hai chiều (hệ toạ độ phẳng), sử dụng rất nhiều trong kỹ
z Kỹ thuật tổng hợp ảnh (Computer Graphics)
thuật xử lý bản đồ, đồ thị. z Geometry modelling
Kỹ thuật đồ hoạ ba chiều: là kỹ thuật đồ hoạ máy tính sử dụng hệ
toạ độ ba chiều, đòi hỏi rất nhiều tính toán và phức tạp hơn nhiều
so với kỹ thuật đồ hoạ hai chiều. 29 30 5 Khoa CNTT - ĐHBK Hà nội Email: hunglt@it-hut.edu.vn Tel: 0913030731
Các ứng dụng tiêu biểu của kỹ thuật đồ họa
z Xây dựng giao diện người dùng (User Interface)
z Tạo các biểu đồ trong thương mại, khoa học, kỹ thuật, minh họa
z Tự động hoá văn phòng và chế bản điện tử
z Thiết kế với sự trợ giúp của máy tính (CAD_CAM)
z Lĩnh vực giải trí, nghệ thuật và mô phỏng
z Điều khiển các quá trình sản xuất (Process Control)
z Lĩnh vực bản đồ (Cartography) GIS 31 32 Square: Final Fantasy 33 34 Pixar: Monster’s Inc.
Computer Aided Design (CAD) CAD-CAM application 35 36 6 Khoa CNTT - ĐHBK Hà nội Email: hunglt@it-hut.edu.vn Tel: 0913030731
Mô hình Hệ đồ họa Mô hình hệ thống Mô hình chức năng
Các chuẩn của hệ đồ hoạ 37 38
Hệ thống đồ hoạ
Mô hình hệ thống đồ họa (Graphics System) z
Interface between application software and graphics hardware system Core, z
Consists of input subroutines and output subroutines accepting input data or GKS, GKS-3D Application program
commands from a user and converting internal representations into external CGI (device interface)
pictures on screen, respectively CGM (metafile) z
Phần mềm đồ hoạ hệ thống: PHIGS (3D and realtime) –
Là tập hợp các lệnh đồ hoạ của hệ thống (graphics output commands), X-window Graphics system –
Thực hiện công việc hiển thị cái gì (what object) và chúng sẽ được hiển thị như thế PHIGS+ (PEX) nào (how). IGES Operating system –
Phần mềm đồ hoạ hệ thống là phần mềm xây dựng trên cơ sở một thể loại phần OpenGL
cứng nhất định và phụ thuộc vào phần cứng. DirectX z
Phần cứng đồ hoạ: Input and Graphics Metafiles –
Là tập hợp các thiết bị điện tử (CPU, bộ nhớ màn hình) giúp cho việc thực hiện các output devices hardware phần mềm đồ hoạ. 39 40
Thành phần trong chức năng của kỹ thuật đồ hoạ 3D Graphi 3D Gr cs aphi Ov cs er W Ov o er W rld Wi o de rld Wi de Web Animation G U I VRML Drawing Pascal / C packages program 3D Graphics WWW MODELING RENDERING DISPLAYING projections ( to describe) (to capture) transformation (to show) of objects SRGP lighting,shading to the computer the description the image library what is create 2D image generate a table, a car, • from 2D / 3D image on graphics algorithms • • models screen positions lines,areas,... colour Geometric Engine Rendering Engine
Raster & Display Engine concerned with: concerned with : X Window - modeling concerned with: System Graphics hardware - modeling transf.
- viewing & projection - hardware - color models
- drawing & clipping - how to display primitives - material property (rasterization) - lighting property
- local illumination & WWW Image shading 41 42 Video - texture mapping
image formats, compression, transfer 7 Khoa CNTT - ĐHBK Hà nội Email: hunglt@it-hut.edu.vn Tel: 0913030731
Non-official industry standards
Các chuẩn giao diện của hệ đồ hoạ
Các chuẩn của hệ đồ hoạ z
GKS (Graphics Kernel System): chuẩn xác định các hàm đồ hoạ chuẩn, được
thiết kế như một tập hợp các công cụ đồ hoạ hai chiều và ba chiều.
z OPENGL thư viện đồ họa của hãng Silicon –
GKS Functional Description, ANSI X3.124 - 1985.
Graphics, được xây dựng theo đúng chuẩn của một –
GKS - 3D Functional Description, ISO Doc #8805:1988. hệ đồ họa. z
CGI (Computer Graphics Interface System): hệ chuẩn cho các phương pháp – SGI’s OpenGL 1993
giao tiếp với các thiết bị ngoại vi.
z DIRECTX thư viện đồ hoạ của hãng Microsoft z
CGM (Computer Graphics Metafile): xác định các chuẩn cho việc lưu trữ và chuyển đổi hình ảnh.
– Direct X/Direct3D 1997 z
VRML (Virtual Reality Modeling Language): ngôn ngữ thực tại ảo, một hướng
phát triển trong công nghệ hiển thị được đề xuất bởi hãng Silicon Graphics,
sau đó đã được chuẩn hóa như một chuẩn công nghiệp. z
PHIGS (Programmers Hierarchical Interactive Graphics Standard): xác định
các phương pháp chuẩn cho các mô hình thời gian thực và lập trình hướng đối tượng.
– PHIGS Functional Description, ANSI X3.144 - 1985.
– PHIGS+ Functional Description, 1988, 1992. 43 44 OpenGL
OpenGL-related Libraries z Commands interpreted using
z Software interface to graphics z Window tasks client-server model hardware z User input For portability, there are z Client-server model – Client (Application) issues commands no commands for these. z Complicated shapes z 250 distinct commands – Server (OpenGL) interprets
z Object specification + image and processes commands
– OpenGL Utility Library (GLU) generation – Frame buffer configuration
– Window system support libraries
z Simple primitives: points, lines, done by the window system
polygons (pixels, images, bitmaps) z GLX / WGL / PGL z 3D rendering
– OpenGL Utility Toolkit (GLUT) – OpenInventor 45 46 DirectX OpenGL Design Goals z
Direct control of graphics hardware
z SGI’s design goals for OpenGL: z
Direct control of input/output devices, and sound
– High-performance (hardware-accelerated) graphics API
– Some hardware independence
– Natural, terse API with some built-in extensibility Application program
z OpenGL has become a standard (competing with DirectX) because:
– It doesn’t try to do too much Direct sound Di
z Only renders the image, doesn’t manage windows, etc. Direct input rect X
z No high-level animation, modeling, sound (!), etc. Windows API – It does enough Direct draw Windows API
z Useful rendering effects + high performance Direct 3D ……..
– Open source and promoted by SGI (& Microsoft, half-heartedly) Windows system 47 48 8 Khoa CNTT - ĐHBK Hà nội Email: hunglt@it-hut.edu.vn Tel: 0913030731 Màn hình CRT Màn hình CRT Standard Dot-trio SONY Trinitron CRT Raster Displays (early 70s)
like television, scan all pixels in regular pattern
use frame buffer (video RAM) to eliminate sync problems RAM
¼ MB (256 KB) cost $2 million in 1971 NEC Hybrid Mask Hitachi EDP 49 50 Display Technology: Raster CRTs
Các thiết bị hiển thị dạng điểm z Raster CRT pros:
– Allows solids, not just wireframes
– Leverages low-cost CRT technology (i.e., TVs)
– Bright! Display emits light z Cons:
– Requires screen-size memory array – Discreet sampling (pixels)
– Practical limit on size (call it 40 inches) – Bulky
– Finicky (convergence, warp, etc) 51 52 CRT Displays
LCD-Liquid Crystal Display Advantages Disadvantages z A transmissive technology
z Fast repsonse (high resolution
z Large and heavy (typ. 70x70 cm,
z Works by letting varying amounts possible) 15 kg)
of a fixed-intensity white backlight through an active filter
z Full color (large modulation
z High power consumption (typ. depth of E-beam) 140W) z Organnic crystals that lign themselves together z Saturated and natural colors
z Harmful DC and AC electric and
z When external force is applied z Inexpensive, matured magnetic fields technology they realign themselves
z Flickering at 50-80 Hz (no memory z This is used to change
z Wide angle, high contrast and effect) brightness polarisation and filter light z Geometrical errors at edges 53 54 9 Khoa CNTT - ĐHBK Hà nội Email: hunglt@it-hut.edu.vn Tel: 0913030731
Display Technology: LCDs LCD Displays
z Transmissive & reflective Advantages LCDs: Disadvantages z
Small footprint (approx 1/6 of CRT)
– LCDs act as light valves, not z High price (presently 3x CRT)
light emitters, and thus rely on z Light weight (typ. 1/5 of CRT) z
Poor viewing angle (typ. +/- 50 an external light source. z
Low power consumption (typ. 1/4 of degrees) – Laptop screen: backlit, CRT) transmissive display z
Low contrast and luminance (typ. z Completely flat screen - no – Palm Pilot/Game Boy: 1:100) geometrical errors reflective display z Low luminance (typ. 200 cd/m2) z
Crisp pictures - digital and uniform colors z No electromagnetic emission z
Fully digital signal processing possible z
Large screens (>20 inch) on desktops 55 56 Màn hình Plasma Display Technology z Plasma Display Panel z Plasma display panels Pros – Similar in principle to – Large viewing angle fluorescent light tubes – Good for large-format – Small gas-filled capsules displays are excited by electric field, – Fairly bright emits UV light z Cons – UV excites phosphor – Expensive – Phosphor relaxes, emits
– Large pixels (~1 mm versus some other color ~0.2 mm) – Phosphors gradually deplete – Less bright than CRTs, 57 58 using more power
Display Technology: DMDs
Display Technology: DMDs
z Digital Micromirror Devices (projectors)
z DMDs are truly digital pixels
– Microelectromechanical (MEM) devices, fabricated
z Vary grey levels by modulating pulse length with VLSI techniques
z Color: multiple chips, or color-wheel z Great resolution z Very bright z Flicker problems 59 60 10 Khoa CNTT - ĐHBK Hà nội Email: hunglt@it-hut.edu.vn Tel: 0913030731 Màn hình hữu cơ Display Technologies: Organic LED Arrays Organic LED Arrays
z Organic Light-Emitting Diode (OLED) Arrays z OLED pros:
– The display of the future? – Transparent
– OLEDs hoạt động tương tự cơ chế – Flexible của LEDs bán dẫn – Light-emitting, and quite
z Cấu trúc là màng chất dẻo mỏng: bright (daylight visible)
– Màng film cấu tạo bởi các phần tử
hữu cơ, các phân tử phát sáng bởi – Large viewing angle
sự thăng hoa khí trong môi trường chân không
– Fast (< 1 microsecond off-
– Mầu sắc được tạo thành từ các lớp on-off)
mầu gồm các phân tử huỳnh quang được kích thích. – Can be made large or small
– Mịn, không to như các hạt tinh thể và không phát nhiệt
– Có thể tạo màn hình rộng loại OLEDs 61 62 Display Technologies: Organic LED Arrays
Direct Color Framebuffer
z Store the actual intensities of R, G, and B individually in the z OLED cons: framebuffer
– Not quite there yet (96x64 displays) except niche markets
z 24 bits per pixel = 8 bits red, 8 bits green, 8 bits blue
z Cell phones (especially back display) z Car stereos
– 16 bits per pixel = ? bits red, ? bits green, ? bits blue
– Not very robust, display lifetime a key issue
– Currently only passive matrix displays
z Passive matrix: Pixels are illuminated in scanline order (like a raster DAC
display), but the lack of phosphorescence causes flicker
z Active matrix: A polysilicate layer provides thin film transistors at each
pixel, allowing direct pixel access and constant illumination
See http://www.howstuffworks.com/lcd4.htm for more info
– Hard to compete with LCDs, a moving target 63 64
Color Lookup Framebuffer
Framebuffers: True-Color
z Store indices (usually 8 bits) in framebuffer
z A true-color ( 24-bit or 32-bit) framebuffer stores one byte
z Display controller looks up the R,G,B values before triggering each for red, green, and blue the electron guns Color Lookup
z Each pixel can thus be one of 224 colors Table z Pay attention to 0 DAC Endian-ness 14 Pixel color = 14 R G B z How can 24-bit and 32-bit mean Frame Buffer the same thing here? 1024 65 66 11 Khoa CNTT - ĐHBK Hà nội Email: hunglt@it-hut.edu.vn Tel: 0913030731
Framebuffers: Indexed-Color Framebuffers: Hi-Color
z Hi-Color was a popular PC SVGA standard
z An indexed-color (8-bit or PseudoColor) framebuffer stores one byte per pixel (also: GIF image format) z Packs pixels into 16 bits:
z This byte indexes into a color map: – 5 Red, 6 Green, 5 Blue z How many colors – Sometimes just 5,5,5 can a pixel be?
z Each pixel can be one of 216 colors z Still common on low-end displays
z Hi-color images can exhibit worse quantization artifacts (cell phones, PDAs, than a well-mapped 8-bit image GameBoys) z Cute trick: color-map animation 67 68
– X : 0 ÷ Xmax 2 màu/ 1 bit
– Y : 0 ÷ Ymax 16 màu/ 4 bit – 256 màu/ 8bit – 216 màu/ 16 bit – 224 màu/ 24 bit –
640 × 480 × 16 → Video RAM = 2MB –
1024 × 1024 × 24 → Video RAM = 24MB 69 12 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 & Camera Parameters Rendering Pipeline Framebuffer Disp Display lay
The Rendering Pipeline: 3-D
Phép biến đổi Transformations Scene graph Object geometry
z screen space- không gian màn hình
z model space Không gian mô hình Modeling
• Các điểm của hệ thống tọa độ 3D thế giới thực Transforms
(a.k.a. object space or world space) Lighting
z 3 loại phép biến đổi: Calculations
• Các điểm bóng theo mô hình chiếu sáng – Modeling transforms Viewing
• Các điểm trong mô hình hệ tọa độ Camera hay tọa độ điểm nhìn Transform – Viewing transforms
– Projection transforms Clipping
• 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 Projection
• Điểm 2-D theo tọa độ màn hình sau phép chiếu được xén tỉa 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 1
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:
coordinates in 3 dimensions with a 4-vector Modeling Transforms
• All vertices of scene in shared 3-D “world” coordinate system – Denoted [x, y, z, w]T
z Note that w = 1 in model coordinates Lighting Calculations
• 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 Transform
• Scene vertices in 3-D “view” or “camera” coordinate system
z Transformations are 4x4 matrices Clipping
• Exactly those vertices & portions of polygons in view frustum
z Why? To handle translation and projection Projection
• 2-D 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 some approximation of lighting Result: Modeling
– Global illumination: solves for lighting of the whole Transforms
• Al vertices of scene in shared 3-D “world” coordinate scene at once system Lighting
– Local illumination: local approximation, typically Calculations • Verti Vert ces sh ices shade ad d acco ed accordi rd ng ing to lighti to lighting model ng model
lighting each polygon separately Viewing
• Scene vertices in 3-D “view” or “camera” coordinate
z Interactive graphics (e.g., hardware) does only Transform system local illumination at run time Clipping
• Exactly those vertices & portions of polygons in view frustum Projection Transform • 2-D screen reen coordi coordinat na es of clip tes of clipped vert ped vertices 2 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 vertices Clip Out: 6 vertices Clip In: 1 polygon 1 polygon Out: 2 polygons
The Rendering Pipeline: 3-D Modeling: The Basics Transform
z Common interactive 3-D primitives: points, Illuminate
lines, polygons (i.e., triangles) Transform z Organized into objects Clip
– Collection of primitives, other objects Project
– Associated matrix for transformations Rasterize
z Instancing: using same geometry for multiple objects Model & Camera
– 4 wheels on a car, 2 arms on a robot Parameters Rendering Pipeline Framebuffer Display
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; Robot
z Cành là các thực thể biến đổi Visited
– Tương ứng là các ma trận Robot Head Body Unvisited Mouth Eye Leg Trunk Arm Head Body Matrix Active Stack Foot Mouth Eye Leg Trunk Arm 3 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
z The projection matrix premultiplies the viewing
– Captured in viewing transform (i.e., modelview matrix)
matrix, which premultiplies the modeling matrices z Pinhole camera model – 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
z Biểu diễn tường minh
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 – k = (y2-y1)/( x2-x1)
z Tính chất các đối tượng cần đảm bảo : – m = y1- kx1 – smooth – Δy = k Δx P(x , ) 2 y2
z Biểu diễn không tường minh – 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 ) –
r = (y2-y1) và t = x2y1 - x1y2 – efficient z
Biểu diễn tham biến P(x , ) 1 y1 P(u) = P1 + u(P2 - P1) u [0,1] X = x1 + u( x2 - x1 ) Y = y1 + u( y2 - y1 ) m Thuật toán DDA Sinh đường tròn Scan Converting Circles
(Digital Differential Analizer) z Explicit: y = f(x)
Giải thuật thông thường 2 2
y = ± R − x
DrawLine(int x1,int y1, int x2,int y2,
Thuậttoán ddaline (x1, y1, x2, y2)
Usually, we draw a quarter circle by int color)
x1, y1, x2, y2 : tọa độ 2 điểm đầu {
incrementing x from 0 to R in unit steps cuối float y;
and solving for +y for each step. k : hệ số góc int x; x,y,m :biến z Parametric: for (x=x1; x<=x2; x++) begin { x = R cosθ
- by stepping the angle from 0 to 90 m =(x2-x1)/(y2-y1);
y = y1 + (x-x1)*(y2-y1)/(x2-x1) x = x1; y = R sinθ
- avoids large gaps but still insufficient.
WritePixel(x, Round(y), color ); 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 xf(x,y) > 0 then it is outside the circle. x = x + 1 begin i+1 i
f(x,y) < 0 then it is inside the circle. y = y + k x = x+1; i+1 i y = y+k; với i=1,2,3.... putpixel(round(x),round(y)); end; end; 4
Giải thuật Bresenham
Giải thuật Bresenham z 1960 Bresenham thuộc d = y - yi = k(xi +1) + b - yi 2 IBM
d = yi+1 - y = yi + 1 - k(xi + 1) - 1
z điểm gần với đường thẳng 2 d2
dựa trên độ phân giai hưu b hạn d1 1 y +1 i d1
z loại bỏ được các phép toán z d2 If d ≤ d => y = yi + 1
chia và phép toán làm tròn i 0 1 2 +1 yi
như ta đã thấy trong gỉai else d > d => y = yi 1 2 i+1 thuật DDA 0 1 2 z D = d - d 1 2
z Xét đoạn thẳng với 0 < k < 1 = -2k(xi + 1) + 2yi - 2b + 1 xi x +1 i z Pi = ΔxD = Δx (d - d ) 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 = -2Δy(x - xi) + 2Δx(yi - yi)
thẳng và đường tròn 1985 i+1 +1
z Các công thức đơn giản hơn, tạo được các y
điểm tương tự như với Bresenham i+1 A z Nếu Pi ≤ 0 ⇒ yi = yi + 1 +1 M Pi = Pi - 2Δy + 2Δx z
d = F (xi + 1, yi + 1/2) là trung điểm của đoạn M +1 AB B z Nếu Pi > 0 ⇒ yi = yi +1 ( x , y ) Pi = Pi - 2Δy i i
z Việc so sánh, hay kiểm tra M sẽ được thay +1
bằng việc xét giá trị d. x x i i+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 d > 0 then chọn điểm A ⇒ trung điểm tiếp theo sẽ có dạng: i
ax + by + c = 0 ⎛ 3⎞ ⎛ 3⎞
ax + by + c = 0 ⇒ x , y on line ⎜x + ,
2 y + ⎟ ⇒ d = + 2 + +1 ⎜ + ⎟+ i i i (axi ) b y c i i ( i i) i ⎝ 2⎠ ⎝ 2⎠
ax + by + c < 0 ⇒ x , y above line i i ( i i)
= d + a +b i
ax + by + c > 0 ⇒ x , y below line i i ( i i)
z Tại mỗi trung điểm của đoạn thẳng giá trị được tính là: ⎛ 1 ⎞ d = +1 + ⎜ + ⎟+ i (axi ) b y c i ⎝ 2 ⎠
z Chúng ta gọi d là biến quyết định của bước thứ i i 5
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à i dx = x_end-x_start ⎛ 1 ⎞ ⎛ 1 ⎞ dy = y_end-y_start ⎜x + ,
2 y + ⎟ ⇒ d = a + 2 + d = 2*dy-dx initialisation +1 ⎜ + ⎟ + i i i (xi ) b y c i x = x_start z Ta có: ⎝ 2 ⎠ ⎝ 2 ⎠ = d + a y = y_start i a = y Δ = y − y ⎫ while x < x_end end start ⎪ y Δ if d <= 0 then b = x Δ
− = x − x ⎬ wherey = x + C end start d = d+(2*dy) x Δ ⎪ choose B c = C x Δ ⎭ x = x+1 else z Ðiểm đầu d = d+2*(dy-dx) ⎛ 1 ⎞ ⎛ ⎞ x = x+1 choose A ⎜ x + , 1 y + ⎟ ⇒ d = a + + ⎜ + ⎟ + y = y+1 start start start (xstart ) 1 1 b y c ⎝ 2 start ⎠ ⎝ 2 ⎠ endif = [ax + by + c + + = 0 b + a + SetPixel(x,y) start start ] b a 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
(x − xc)2 +(y − yc)2 2 theo x một đơn vị − r = 0 Putpixel (x ,y); – d
z Thực hiện giải thuật trên 1/8
i +1 = F(xi +2, yi + 1/2)
= 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. d = d + dy - dx x = x + 1
z Với d là giá trị của đường tròn tại yes i z
Nếu điểm A được chọn thi` M tăng theo
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) + 1 ⎧< if 0 ( x , y i i ) circle inside is – = a(xi + 2) + b(yi +3/2) + c ⎪ yes x < x2 d = x y i ⎨= if 0 ( ,i i) circle on is – di = di + a + b. + 1 ⎪> if 0 ⎩ ( x , y i i ) circle outside is ¾ Với a + b = dy - dx. no KÕt thóc
Midpoint Circle Algorithm
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
z Again, as with the line algorithm, the choice of A or B can be form of the circle: 2
used to determine the new value of d ⎛ ⎞ i+1 d = + +⎜ − ⎟ −
z If A chosen then next midpoint has the following decision i (xi )2 1 2 1 y r i ⎝ 2⎠ variable: ⎛ 1 ⎞ ⎛ 1 2 2 ⎞
z If d < 0 we choose pixel 2
A otherwise we choose pixel B ⎜ x + , 2 y − d x y r i i ⎟ ⇒ = + + i+ i ⎜ − i ⎟ − 1 ( )2 i
– Note: we currently assume the circle is centered at the origin ⎝ 2 ⎠ ⎝ 2⎠ = d + 2x +3 i i
z Otherwise if B is chosen then the next decision variable i 2 s given ⎛ 3 ⎞ 2 ⎛ 3 ⎞ by: ⎜x + , 2 y − d x y r i i ⎟ ⇒ = + + i+ i ⎜ − i ⎟ − 1 ( )2 2 ⎝ 2 ⎠ ⎝ 2 ⎠
= d + 2x −2y +5 i i i 6
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 initialisation
(0, r) and the initial value for the decision variable x = 0 is given by: y = r
stop at diagonal ⇒ end of octant ⎛ 1 ⎞ ⎛ 2 1 ⎞ ⎜ while y < x ,
1 r − ⎟ ⇒ d = 1+ 0
⎜r −r + ⎟−r2 ⎝ 2 ⎠ ⎝ 4 ⎠ if d < 0 then d = d+2*x+3 choose A x = x+1 = 5 −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 endif ⇒ we can round down: d =1− r 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 2 2 2 2 2 2
F (x, y) = b x + a y − a b = 0 B gradient B C M
z 2a is the length of the major axis along the x axis. i
z Firstly we divide the quadrant into two regions
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
– the point at which the gradient vector has the i and j components of
z For simplicity, we draw only the arc of the ellipse that equal magnitude
lies in the first quadrant, the other three quadrants can be drawn by symmetry 2 2 grad F( , x ) y F =∂ / x ∂ i + F ∂ / y
∂ j= 2b xi +2a y 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 p p
z Trên cơ sỏ định nghĩa mỗi ký tự
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 – For a move to SE, d = d +Delta with shapes new old SE Delta = b2(2x +3)+a2(-2y +2) SE p p z fontcache
z In region 2, choices are S and SE
– các ký tự theo chuỗi liên tiếp nhau trong bộ nhớ – Initial condition: d = b2(x +0.5)2+a2((y-1)2-b2) 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 z Thuộc tính
z Stop in region 2 when the y value is zero.
– Also colour, size, spacing and orientation 7 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
Giải thuật đường quét sinh đa giác So sánh Polygon Scan Conversion z Phức tạp (Tính toán
z Tồn tại rất nhiều giải thuật sinh đa giác.
z Đơn giản trông việc sinh ký phương trình) 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 công thức biến đổi
z Các phép biến đổi (I,B,
– some algorithms allow triangular polygons only
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. 8