Computer Graphics | CS | Course

Brief Information
Summary (in brief)
  1.  Introduction
  2. Graphics System Overview
  3. Math for Computer Graphics
  4. OpenGL and Graphics
  5. Transformations
  6. 3D Viewing and Clipping
  7. Research in Computer Graphics
  8. Lighting and Shading
  9. Texture Mapping
  10. Rasterization [Scan conversion]
  11. Splines
  12. Animation
  13. Modern OpenGL
Assignments
  1. Interactive vector drawing tool in 2D
    1. video demonstration
  2. Interactive viewer for 3D polygonal model
    1. video demonstration
  3. Interactive lighting for a collection of 3D shapes
    1. video demonstration
  4. Build your own interactive 3D application
    1. video demonstration
Summary (in detail)
  1. Introduction
  2. 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, …
  3. Math for Computer Graphics
    • Vector algebra
      • dot product
      • cross product
    • The equations of the 3D objects
      • line
      • plane
  4. OpenGL and Graphics
  5. 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
      • Method 2: Using quaternion
        • Quarternion algebra
  6. 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
  7. Research in Computer Graphics
  8. 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
        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
      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
          I_a = k_a L_a
        • Diffuse reflection
          I_d = k_d L_d
        • Specular reflection
          I_s = k_s (Vcdot R)^n L_s
          Phong-Blinn specular reflection
          I_s=k_s (Ncdot H)^n L_s
          (H=frac{V+L}{|V+L|})
  9. 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
  10. 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
          y_{i+1}=round(mx_{i+1}+b)
        • strategy 2: incremental algorithm
          y_{i+1}=round(y_i+m)
        • strategy 3: midpoint algorithm
          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}
          (f(x,y)=ax+by+c, age 0)
        • problem: aliasing
      • 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
    • Rasterizing Triangles
      • Barycentric Coordinates (p is a point composing a traingle)
        mathbf{p}=mathbf{a}+beta(mathbf{b}-mathbf{a})+alpha(mathbf{c}-mathbf{a})
        (beta > 0, gamma > 0 , beta + gamma < 1)
      • Pixel-walk (Pineda) Rasterization
    • Hidden Surface Elimination
      • Back-face Culling Algorithm
        • Remove all back faces which satisfies
          mathbf{v}cdot mathbf{n} < 0
      • 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
          
    • Programmable Pipeline
      • Vertex processing: transformation, lighting
      • Fragment processing: shading, texture mapping, blending
  11. 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
      B^{n}_{i}(t)=binom{n}{i}(1-t)^{n-i}t^i
    • Cubic polynomial in Bernstein bases
      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 mathbf{b}_0, mathbf{b}_1, mathbf{b}_2, mathbf{b}_3
      • Properties of Bezier Curve
        • End point interpolation
          mathbf{p}(0)=mathbf{b}_0
          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.
          mathbf{p}'(0)=3(mathbf{b}_1-mathbf{b}_0)
          mathbf{p}'(1)=3(mathbf{b}_3-mathbf{b}_2)
          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.
      • Matrix Form
        • 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}
    • Drawing a Bezier Curve
      • Method 1: Brute force
        • Vary t from 0 to 1 by the fixed step size
          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.
      • 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
    • Connect Bezier Splines
      • The connected two end points must have the same tangent.
        • Condition 1: Connecting Condition
          mathbf{b}_{i,4} = mathbf{b}_{i+1,0}
        • Condition 2: Smooth Condition
          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.
    • Bezier Surfaces: extended from Bezier curves.
  12. 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
    • Natural phenomena
      • Particle simulation
      • Mass-spring model
      • Fluid simulation
  13. Modern OpenGL with GLSL

Leave a Reply

Your email address will not be published. Required fields are marked *