Brief Information
- Name : Computer Graphics
- Lecturer : Kang Hoon Lee (이강훈)
- Semester : 2015 Fall
- Major?:?BE, Computer Science and Engineering
- Textbook
- Syllabus : (blank)
- In?short
Summary (in brief)
- ?Introduction
- Graphics System Overview
- Math for Computer Graphics
- OpenGL and Graphics
- Transformations
- 3D Viewing and Clipping
- Research in Computer Graphics
- Lighting and Shading
- Texture Mapping
- Rasterization [Scan conversion]
- Splines
- Animation
- Modern OpenGL
Assignments
- Interactive vector drawing tool in 2D
- Interactive viewer for 3D polygonal model
- Interactive lighting for a collection of 3D shapes
- Build your own interactive 3D application
Summary (in detail)
- Introduction
- Graphics System Overview
- Two ways of representation
- bit-mapped graphics
- object-based graphics
- video display devices
- CRT(Cathode Ray Tube)
- Vector displays
- Raster displays
- refreshing
- frame buffer
- refresh rate
- Scan conversion
- Interlacing
- the principle of interlacing
- Frame Buffers
- Color Lookup Table
- Double Buffering
- solves the tearing problem
- front buffer, back buffer
- Output Devices & Input Devices
- Graphics Rendering Pipeline
- 3D Scene[Models] ─Rendering→ 2D Image
- Graphics System: a library of grahpics functions
- OpenGL, …
- Two ways of representation
- Math for Computer Graphics
- Vector algebra
- dot product
- cross product
- The equations of the 3D objects
- line
- plane
- Vector algebra
- OpenGL and Graphics
- Transformations
- Objects to transform
- Model: modeling transformation
- Viewer: viewing transformation
- The 4?types of transformations
- [1] Rotation
- [2] Translation
- [3] Scaling
- [4] Shearing
- Compound transformations
- Mathematics for transformations
- Linear combination of vectors
- Basis:=”A linearly independant set of vectors that span the space”
- orthonormal basis = orth- + normal + basis = orthogonal normal basis
- A vector has the unique representation in a give n basis.
- Linear maps
- Affine maps:= linear map + translation
- Homogeneous coordinates
- Rigid body transformation & Non rigid body transformation
- 3D Rotation
- Method 1: Using the one axis for rotation
- Using the 3 axis for rotation
- The gimbal lock?problem
- Euler’s roation theorem
- “The general displacement of a rigid body with one point fixed is a rotation about some axis.”
- The method for 3D rotation about an arbitrary axis
- Using the 3 axis for rotation
- Method 2: Using quaternion
- Quarternion algebra
- Method 1: Using the one axis for rotation
- Objects to transform
- 3D Viewing and Clipping
- Transformations
- Parallel view
- Perspective view
- Viewing
- Clipping
- Stage of vertex transformation
- Viewing-coordinate parameters: n, u ,v
- World-to-view transformation
- World-to-view in 2D?&?3D
- Projection
- Hierarchy of Plane Geometric Projections
- Orthographic projection
- Perspective projection
- Clipping
- Normalization of the vewing frustum
- Clipping algorithm
- We will consider 2D version. Then, we extend it to 3D version.
- Line clipping
- Conhen-Sutherland algorithm (subdivision)
- Polygon clipping
- Sutherland-Hodgman algorithm
- Weiler-Atherton algorithm
- Viewing in OpenGL
- Research in Computer Graphics
- Lighting and Shading
- Shading:= “Shading determines a color for each pixel according to light sources, surfaces, and viewing positions.”
- Simple Mathematical Models of Lights
- Point Lights
- Distant Lights
- Spot Lights
- Ambient Lights
- Radial Lights
- Types: point lights, spot lights
- Attenuation
$latex frac{1}{k_c+k_l r+k_q r^2} L$ (r: distant)
- Parallel Lights
- Types: distant lights, ambient lights
- Reflection
- Phong Reflection Model
$latex I=I_a+frac{1}{k_c+k_l r+k_q r^2}(I_d+I_s)$- The Types of Reflections
(L: a light vector, N: the normal vector, R: the reflection vector, V: a viewer vector)- Ambient reflection
$latex I_a = k_a L_a $ - Diffuse reflection
$latex I_d = k_d L_d $ - Specular reflection
$latex
I_s = k_s (Vcdot R)^n L_s$
Phong-Blinn specular reflection
$latex I_s=k_s (Ncdot H)^n L_s$
$latex (H=frac{V+L}{|V+L|})$
- Ambient reflection
- The Types of Reflections
- Texture Mapping
- Texture coordinates &?world coordinates
- Texture mapping,?mapping texture to surfaces
- Parametric surfaces & non-parametric surfaces
- Pattern mapping. tiling. texture coordinates :?world coordinates = 1 : N
- Texture coordinates on meshes
- Aliasing
- By mapping from a texture image to a surface in the word coordinates, the aliasing problem occurs.
- Antialiasing
- Methods to solve the aliasing problem
- Antialiasing in 2D
- point sampling
- bilinear filtering
- Antialiasing with mipmapping
- bilinear filtering
- trilinear filtering
- Texture mappings in OpenGL
- 4 mappings in texture mapping
- color mapping
- bump mapping
- displacement mapping
- environment mapping
- spherical environment mapping
- cubical environment mapping
- Rasterization [Scan conversion]
- Def.: “Converting vector description of an image into raster description” syn. scan conversion
- Primitives to be rasterize
- points
- line segments
- triangles
- Rasterizing Lines
- Method 1: Point Sampling
- strategy 1: basic algorithm
$latex y_{i+1}=round(mx_{i+1}+b)$ - strategy 2: incremental algorithm
$latex y_{i+1}=round(y_i+m) $ - strategy 3: midpoint algorithm
$latex
f(x_i+1, y_i+0.5)=
begin{cases}
ge0 &Rightarrow y_{i+1}=y_i\
<0 &Rightarrow y_{i+1}=y_i + 1
end{cases}
$
$latex
(f(x,y)=ax+by+c, age 0)
$ - problem: aliasing
- strategy 1: basic algorithm
- Method 2: Box Filtering: Quantitative Approach
- Weight by ‘how much a pixel is covered by a line segment’ – anti-aliasing
- problem: treating area near edges same as area near center
- Method 3: Weighted Filtering: Weighted Quantitative Approach
- Weight by Gaussian function
- Method 1: Point Sampling
- Rasterizing Triangles
- Barycentric Coordinates (p is a point composing a traingle)
$latex mathbf{p}=mathbf{a}+beta(mathbf{b}-mathbf{a})+alpha(mathbf{c}-mathbf{a})$
$latex (beta > 0, gamma > 0 , beta + gamma < 1)$ - Pixel-walk (Pineda) Rasterization
- Barycentric Coordinates (p is a point composing a traingle)
- Hidden Surface Elimination
- Back-face Culling Algorithm
- Remove all back faces which satisfies
$latex mathbf{v}cdot mathbf{n} < 0$
- Remove all back faces which satisfies
- Z-buffer Algorithm
- From the viewing frame
- ?
def findzbuffer(x, y, list_zbuffer): ...max_zbuffer = 1.0 # zbuffer ranges from 0 to 1 ...for zbuffer in list_zbuffer: ......if zbuffer < max_zbuffer: .........max_zbuffer = zbuffer ...return max_zbuffer
- Back-face Culling Algorithm
- Programmable Pipeline
- Vertex processing: transformation, lighting
- Fragment processing: shading, texture mapping, blending
- Splines
- Motion:=?”A time-varying transformation”
- The world coordinates & body local coordinates
- Keyframing:= “Describing motion by specifying a sequence of transformations at each movement”
- Polynomial interpolation
- Lagrange polynomial interpolation
- Cubic polynomial interpolation
- Bernstein basis functions
$latex B^{n}_{i}(t)=binom{n}{i}(1-t)^{n-i}t^i$ - Cubic polynomial in Bernstein bases
$latex mathbf{p}(t)\
=mathbf{b}_0B^{3}_{0}(t)+mathbf{b}_1B^{3}_{1}(t)+mathbf{b}_2B^{3}_{2}(t)+mathbf{b}_3B^{3}_{3}(t)\
=mathbf{b}_0(1-t)^3+mathbf{b}_1 3t(1-t)^2+mathbf{b}_2 3t^2(1-t)+mathbf{b}_3 t^3$ - Bezier Curve
- Bezier control points $latex mathbf{b}_0, mathbf{b}_1, mathbf{b}_2, mathbf{b}_3$
- Properties of Bezier Curve
- End point interpolation
$latex mathbf{p}(0)=mathbf{b}_0$
$latex mathbf{p}(1)=mathbf{b}_3$ - Convex hull: able to be used to detect collision
- Affine invariance: control points and a curve are one-to-one correspondence.
- Tangent vector: the tangent vectors are easily solved.
$latex mathbf{p}'(0)=3(mathbf{b}_1-mathbf{b}_0)$
$latex mathbf{p}'(1)=3(mathbf{b}_3-mathbf{b}_2)$
$latex mathbf{p}'(t)=-3(1-t)^2mathbf{b}_0+3(1-3t)(1-t)mathbf{b}_1+3t(2-3t)mathbf{b}_2+3t^2mathbf{b}_3$ - Subdivision: a Berzier curve is subdivided into Beizer curves.
- De Castelijau’s algorithm: a recursive method to evaluate polynomials in Bezier curves.
- End point interpolation
- Matrix Form
- $latex
mathbf{p}(t)=
begin{bmatrix}
t^3& t^2 & t^1 & 1\
end{bmatrix}
begin{bmatrix}
1 & 3 & -3 & 1\
-3& -6 & 3 & 0\
3 & 3 & 0 & 0\
-1& 0 & 0 & 0\
end{bmatrix}
begin{bmatrix}
mathbf{b}_0\
mathbf{b}_1\
mathbf{b}_2\
mathbf{b}_3\
end{bmatrix}
$
- $latex
- Drawing a Bezier Curve
- Method 1: Brute force
- Vary t from 0 to 1 by the fixed step size
$latex t_{i+1}=t_i+Delta tquad(i=0,1,2,…,n, t_0=0, t_n=1, Delta t=frac{t_n-t_0}{n})$ - Problem: This may cause dots become too dense or too sparse.
Too dense ⇒ waste resources.
Too sparse ⇒ a different curve.
- Vary t from 0 to 1 by the fixed step size
- Method 2: Recursive subdivision
- Solve the problem of the Method 1.
- The algorithm
def subdivide(t0, t1, max_line_length): ...t_mid = (t0 + t1) / 2 ...p0 = point(t0) ...p1 = point(t1) if distance(p1, p0) >?max_line_length: ...subdivide(t0, t_mid, max_line_length) ...subdivide(t_mid, t1, max_line_length) else ...drawLine(p0, p1)
- required data: keyframes and their tangent vectors
- Method 1: Brute force
- Connect Bezier Splines
- The connected two end points must have the same tangent.
- Condition 1: Connecting Condition
$latex mathbf{b}_{i,4} = mathbf{b}_{i+1,0}$ - Condition 2: Smooth Condition
$latex mathbf{b}_{i,4}-mathbf{b}_{i,3} = mathbf{b}_{i+1,1}-mathbf{b}_{i+1,0}$ - For the natural movement, the acceleration on?the two connection should be same.
- Condition 1: Connecting Condition
- The connected two end points must have the same tangent.
- Bezier Surfaces: extended from Bezier curves.
- Animation
- Animated characters
- Kinematics
- “The study of motion without regard to the foraces that caused it.”
- Hierachical models
- tree structure of joints and links
- joints
- Forward and inverse kinematics
- Joint & link transformations
- Representing hierarchical models
- OpenGL matrix stack
- Motion capture and editing
- Keyframing skeletal motion
- Motion capture
- Motion editing
- Planning and learning
- Behavior modeling
- Kinematics
- Natural phenomena
- Particle simulation
- Mass-spring model
- Fluid simulation
- Animated characters
- Modern OpenGL with GLSL