cse3431-lecture1.key
CSE 3431— Fall 2018
Introduction to 3D Computer
Graphics
Instructor: Petros Faloutsos
Teaching Assistant: Irfa Nisar
Applications of Computer
Graphics
Entertainment
• Computer games
• Films
• Virtual reality
Scientific visualization
• Medical visualization
• Flight simulation
• Architecture
• Information visualization
Education
Movies
To reality and beyond !
Movies
Special Effects
Movies
Compositing
Cartoons
Games
Focus on interactivity
Computer-Aided Design
Precision modeling
Engineering visualization
Computer Aided Design
It is not just about visualization
• Simulation is useful
Visualization: Scientific
Visualization: Architectural
Visualization: info
• Geographical Information systems
– Maps
• Personal Information
• Massive dataset visualization
Graphical User Interfaces
Digital Art
Computer Graphics
Pictures! Motion!
Interaction!
Mathematics
Biomechanics
Engineering
Optics
Art
Physics
Artificial
Intelligence
Vision
History
• 2000 B.C.
– orthographic projection
• 1400s
– Perspective: Italian Renaissance
• 1600s
– coordinate systems: Descartes,
– optics: Huygens
– calculus, physics, optics: Newton
• 1897 oscilloscope: Braun
By Tony R. Kuphaldt – Socratic Electronics website :
[1], CC SA 1.0, https://commons.wikimedia.org/w/index.php?curid=632462
History
• 1950-1970
– computers with vector displays
• 1966
– first true raster display
• 1993
– 1200×1200, 500k triangles/sec, 36-bit colour, stereo, texture
mapping all at 60Hz
• 1995
– video holography, feature-length CG films
• Today 4K video, OLEDS
Genesis of Computer Graphics
and Interactive Techniques
A PhD project at MIT in the early 1960s
• Ivan E. Sutherland, 1963
– “Sketchpad, a man-machine graphical
communication system”
Quiz
http://www.accad.ohio-state.edu/~waynec/history/timeline.html
When was the term Computer Graphics first stated?
William Fetter of Boeing coins the term “computer graphics”
for his human factors cockpit drawings 1960.
Who and when developed the GUI?
GUI developed by Xerox (Alan Kay) 1969
When was Tron released?
Disney contracts Abel, III, MAGI and DE for computer
graphics for the movie Tron released in 1981.
http://www.accad.ohio-state.edu/~waynec/history/timeline.html
Quiz (contd)
Which is the first animated movie to employ CG?
The Great Mouse Detective was the first animated
film to be aided by CG in 1986.
When was DOOM released ?
1993.
Which was the first totally computer generated
movie?
Toy Story 1995
Quiz (contd)
Which is bigger in gross revenue, the Gaming
Industry or Hollywood?
The Gaming Industry.
Which is the best selling game of all time?
Top grossing games (June 2012)
Source digitalbattle.com
10. Call of duty: Modern war fare — $700M
Courtesy of Infinity Ward
Top grossing games (June 2012)
Source digitalbattle.com
9. The Sims 2000 — $740M
Top grossing games (June 2012)
Source digitalbattle.com
8. Modern war fare 2 — $780M
Courtesy of Infinity Ward
Top grossing games (June 2012)
Source digitalbattle.com
7. Gran turismo — $850M
Courtesy of Sony Computer Entertainment Inc.
Top grossing games (June 2012)
Source digitalbattle.com
6. New Super Mario Bros — $1.2 billion
Courtesy of Nintendo
Top grossing games (June 2012)
Source digitalbattle.com
5. Wii Play — $1.25 billion
Courtesy of Nintendo
Top grossing games (June 2012)
Source digitalbattle.com
4. Grand Theft Auto 4 — $1.35 billion
Courtesy of Rockstar Games
Top grossing games (June 2012)
Source digitalbattle.com
3. Mario Kart for Wii — $1.4 billion
Courtesy of Nintendo
Top grossing games (June 2012)
Source digitalbattle.com
2. Call of duty: black ops — $1.5 billion
Courtesy of Infinity Ward
Top grossing games (June 2012)
Source digitalbattle.com
1. World of Warcraft — over $10 billion
Courtesy of Blizzard Entertainment
First computer game?
Pong, Atari, 1972
Spacewars PDP –1 MIT, 1961
Bottom line:
Synthesize Images/Videos
What is an image or video
• An array of pixels (one or more numbers)
• A video is a sequence of images
How do we synthesize an image?
• From mathematical models to coloured pixels
Models of
• Objects in the world, light sources, materials
• Processes (e.g. Illumination, sampling)
• Imaging device (eye, camera)
Basic Elements
Modeling
Rendering
Animation
Interaction
Basic Technical Elements
• Modeling
– How do we model (mathematically represent) objects?
– How do we construct models of specific objects?
• Animation
– How do we represent the motion of objects?
– How do give animators control of the motion?
• Rendering
– How do we simulate the real-world behavior of light?
• Interaction
– How do we enable humans and computers to interact?
– How do we design human-computer interfaces?
Modeling
Primitives
• 3D points
• 3D lines and curves
• surfaces (BREPs): polygons,
patches
• volumetric representations
• image-based representations
Attributes
• Color, texture maps
• Lighting properties
Geometric transformations
Rendering
Viewing
Visibility
Simulating light
propagation
• Reflection
• Absorption
• Scattering
• Emission
• Interference
Animation
Keyframe, motion
capture
Physics-based
animation
Autonomous motion
planning
Interaction
Tools
• Modeling, rendering and
animation
Input/Output Devices
Courtesy of Victor
Ng-Thow-Hing
Examples of Research Results
and Problems in Computer Graphics
Fluid Simulation
Modeling
• Incompressibility
• Viscocity
Navier Stokes
Level Sets
Phase transition
Courtesy of the
Stanford Graphics
group
Character Animation
Motion control
• Motion capture
• Physics-based
• AI
Facial Animation
Visual Speech
Expression control
Attention control
Hair simulation
Crowd simulation
[Shawn Sing, Mubbasir Kapadia, Glenn Reinman, Petros Faloutsos]
Sound simulation
Physics-based
generation
Sound simulation and rendering
Physics-based generation
Texture synthesis
Vector fields
Multilevel synthesis
Great! What are we going to do?
The basics and
… some animation.
Copyright 2002 by Pixar Inc.
Introduction to Computer Graphics
• Introduction to (mostly interactive) graphics
• Software
• Hardware
• Applications
Shader based WebGL compatible with
• OpenGL ES 2.0
• OpenGL 3.3
https://moodle.yorku.ca
CSE 3431 Fall 2018
A computer graphics
model of the instructor
(copyright PIXAR/DISNEY)
https://moodle.yorku.ca
• Good programming skills:
– Javascript, C, C++
• Basic data structures
– Link lists
– Arrays
– Structures or Classes
• Geometry
• Basic linear algebra
Prerequisites
Course Load
Marking scheme
• Assignment 1: 15 %
– Predefined scene modelling and animation
• Assignment 2: 15 %
– Free interactive scene or game
• Assignment 3: 20 %
– Raytracing
• Midterm: 20 %
• Final: 30 %
Selected Policies – For complete
list see web page
Late submission policy
• Maximum 3 days with 10% penalty per 24 hours.
• Penalty computed at increments of 15 minutes.
• NO LATE assignments if original deadline extended.
Academic dishonesty policy
• York’s policy is very clear on cheating (e.g. plagiarism) of
any kind. All cases must and will be referred to the Dean
of Students.
Zero mark policy
• Assignments that do not compile get ZERO marks.
• Assignments that produce nothing meaningful get ZERO
marks.
Facts about the class
Challenges
• Too much material
• Fast pace
• Tough third project
• Tough exams
• A lot of programming
• A lot of math
• Hard to debug 3D scenes in 2.5 D
Benefits
• Skill building
• CV building
Copyright 2002 by Pixar Inc.
Advice
• Start the assignments EARLY!!
• Get HELP from us with the assignments EARLY!
• Do NOT do more than you are asked to unless you
are done with the required part of the assignment.
• You will NOT get more marks for additional work.
• Refresh vector and matrix algebra and keep up
with the math.
Resources
• Main OpenGL web site: www.opengl.org.
– Documents
– Coding resources and examples.
• The OpenGL Reference guide – Blue Book.
• The OpenGL Programmer’s guide – Red Book.
– The definitive reference
– OpenGL 4.5
• OpenGL ES 2.0 Programming Guide
• Javascript resources: http://www.w3schools.com/js/
http://www.opengl.org/
http://www.opengl.org/documentation/blue_book/
http://www.opengl.org/documentation/red_book/
http://www.w3schools.com/js/
Topics in more detail
Interactive 3D Graphics
Basic primitives
• Lines
• Triangles
• Triangle meshes
• Attributes: color, texture, normal vectors et al.
These primitives go through a standardized
pipeline
Why only triangles?
v1
v2
v3
v4v5
The old graphics pipeline
Why a pipeline
• Well defined stages
• Parallelism
• Software and Hardware
Radeon RX by AMD
• Compute Units: 36
• Stream Processors: 2304
• Peak Pixel Fill Rate: 42GP/sec
• Texture units: 144
• Max Performance: 6.2 TFLOPS
Radeon RX 580 by AMD
Graphics pipeline (fixed or not)
Modelling
Viewing (Projection)
Illumination
Clipping
Visibility
Rasterization
Per Vertex and Per Pixel operations
Vector and matrix calculus
Vector spaces
Matrix algebra
Coordinate systems
Affine transformations
Modeling
Geometric Primitives
• Triangles (polygons)
• Parametric surfaces
• Implicit surfaces
Modeling Transformations
Viewing and Clipping
Viewing
Orthographic Perspective
Visibility
Resolve occlusions
(efficiently)
Illumination
Compute normals and colour
• Per vertex
• Per pixel
Rasterization
Projected model to actual pixels
Rasterization (size of pixels
matters!!)
Projected model to actual pixels
Shading
Projected model to colored pixels
Texture Mapping
Graphics Pipeline
Modeling
transformation
Viewing
transformation
Projection
transformation
Perspective
division
Viewport
transformation
OCS
WCS VCS
CCS
NDCSDCS
Primitive
Assembly
Clipping
Rasterization
Texture mapping
Per pixel Operations
(user defined and system)
Fragments
Primitive
Assembly
Coloured Pixels
x
Z-buffer algorithm
After a polygon has been projected on the screen and during
rasterization
for all i,j {
Depth[i,j] = MAX_DEPTH
Image[i,j] = BACKGROUND_COLOUR
}
for all polygons P {
for all pixels in P {
if (Z_pixel < Depth[i,j]) {
Image[i,j] = C_pixel
Depth[i,j] = Z_pixel
}
}
}
Shader Based Graphics Pipeline
Modeling
transformation
Viewing
transformation
Projection
transformation
Perspective
division
Viewport
transformation
OCS WCS VCS CCS
NDCS
DCS
Rasterization into pixels (fragments)
Texture mapping
• Streaming SIMD architecture
• However, it is still useful to follow conceptually and
programmatically the old stages
Shader-based Graphics Pipeline
Clipper and
Primitive
Assembler
Rasterizer
Vertices
Pixels
Programmable
Fragment
Processors
Programmable
Vertex
Processors
Textures
Modeling, Viewing, Projection,
Anything programmer wishes
Shading, Texture Mapping,
anything programmer wishes
Loaded by user
Dynamically Computed at
previous passes
Pipeline with all shaders (aside)
TCSVS TES GS
FS
Primitive
Assembly
TPG Primitive
Assembly
Primitive
Assembly
VS: Vertex shader
TCS: Tessellation control shader
TPG: Tessellation primitive generator
TES: Tessellation evaluation shader
GS: Geometry shader
FS: Fragment shader
Tessellation shaders and geometry
shaders are optional
Modeling Real-time Rendering Motion Synthesis
Modeling: Define an object and a set of parameters, e.g [R,wi]
Rendering: Apply lights and compute an image
Motions synthesis: Compute [R(t), wi(t)] to produce motion
!77
Animation
Graphics system
Input devices
Rendering system
Output devices
Input devices
Keyboard
Mouse
Light Pen
Game controller
Tablet
Data glove
Other sensors
Rendering system
Software
• Interface
• Primitives
• Techniques
Hardware
• Graphics Card or Integrated
with CPU
Output devices
Output devices
Monitor
• CRT, Plasma
Printer
• 3D Printers
Plotter
Head mounted display
Courtesy of Steve Mann
Courtesy of the Vesa Lab
Summary: Basic Elements of
Computer graphics
Math
Modeling
Rendering
Animation
Interaction
Hardware
Example: Oktapodi
Winner of the SIGGRAPH 2008 Computer
Animation Festival
• best in show, and
• audience’s choice
awards !
Oktapodi
1Angel: Interactive Computer Graphics5E © Addison-Wesley 2009
Image Formation
Ed Angel
Professor of Computer Science,
Electrical and Computer
Engineering, and Media Arts
University of New Mexico
Taking a snapshot of a 3D Scene
2Angel: Interactive Computer Graphics5E © Addison-Wesley 2009
Imaging
•Fundamental imaging notions
•Physical basis for image formation
Light
Color
Perception
•Synthetic camera model
•Other models
3Angel: Interactive Computer Graphics5E © Addison-Wesley 2009
Image Formation
• In computer graphics, we form images
which are generally two dimensional using
a process analogous to how images are
formed by physical imaging systems
Cameras
Microscopes
Telescopes
Human visual system
4Angel: Interactive Computer Graphics5E © Addison-Wesley 2009
Elements of Image Formation
•Objects
•Viewer
•Light source(s)
•Attributes that govern how light interacts
with the materials in the scene
•Note the independence of the objects, the
viewer, and the light source(s)
5Angel: Interactive Computer Graphics5E © Addison-Wesley 2009
Light
•Light is the part of the electromagnetic
spectrum that causes a reaction in our
visual systems
•Generally these are wavelengths in the
range of about 350-750 nm (nanometers)
•Long wavelengths appear as reds and
short wavelengths as blues
6Angel: Interactive Computer Graphics5E © Addison-Wesley 2009
Ray Tracing and
Geometric Optics
One way to form an image is to
follow rays of light from a
point source finding which
rays enter the lens of the
camera. However, each
ray of light may have
multiple interactions with objects
before being absorbed or going to infinity.
7Angel: Interactive Computer Graphics5E © Addison-Wesley 2009
Luminance and Color Images
•Luminance Image
Monochromatic
Values are gray levels
Analogous to working with black and white film
or television
•Color Image
Has perceptional attributes of hue, saturation,
and lightness
Do we have to match every frequency in visible
spectrum? No!
8Angel: Interactive Computer Graphics5E © Addison-Wesley 2009
Three-Color Theory
•Human visual system has two types of
sensors
Rods: monochromatic, night vision
Cones
• Color sensitive
• Three types of cones
• Only three values (the tristimulus
values) are sent to the brain
•Need only match these three values
Need only three primary colors
9Angel: Interactive Computer Graphics5E © Addison-Wesley 2009
Shadow Mask CRT
10Angel: Interactive Computer Graphics5E © Addison-Wesley 2009
Additive and Subtractive Color
•Additive color
Form a color by adding amounts of three
primaries
• CRTs, projection systems, positive film
Primaries are Red (R), Green (G), Blue (B)
•Subtractive color
Form a color by filtering white light with cyan
(C), Magenta (M), and Yellow (Y) filters
• Light-material interactions
• Printing
• Negative film
11Angel: Interactive Computer Graphics5E © Addison-Wesley 2009
Pinhole Camera
xp= -x/z/d yp= -y/z/d
Use trigonometry to find projection of point at (x,y,z)
These are equations of simple perspective
zp= d
•Finite size
Real camera ?
!98
Lenses
!99
Cameras and lenses
!100
Depth of field
!101
Depth of field (contd)
!102
12Angel: Interactive Computer Graphics5E © Addison-Wesley 2009
Synthetic Camera Model
center of projection
image plane
projector
p
projection of p
13Angel: Interactive Computer Graphics5E © Addison-Wesley 2009
Advantages
•Separation of objects, viewer, light sources
•Two-dimensional graphics is a special case
of three-dimensional graphics
•Leads to simple software API
Specify objects, lights, camera, attributes
Let implementation determine image
•Leads to fast hardware implementation
14Angel: Interactive Computer Graphics5E © Addison-Wesley 2009
Global vs Local Lighting
•Cannot compute color or shade of each
object independently
Some objects are blocked from light
Light can reflect from object to object
Some objects might be translucent
Images
2D Arrays of color values (numbers)
Monochrome
Color
Monochrome
Black and White (Bitmaps) Grayscale
Color
Common format RGB (3x8 = 24 bits per pixel)
Common format RGBA (4x8 = 32 bits per pixel)
Raster graphics
Virtual raster device
• Grid of m x n pixels
Real raster device
• Arrangement of 3
phosphors per pixel
• Pixel may not be
square
Basic display architecture
Pixels:
• Bitmap: 1bit/pixel
• Grey scale: 8 bits/pixel
• Colour map: 8 bits/pixel, indirect
• True color: 24 bits/pixel
• True color + Alpha Channel: 32 bits/pixel
Pixel format might be different for each device
• Often we need to convert
CPU GPU Framebuffer Framebuffer of Output Device
Gamma correction
Tone mapping
Converter
DAC
Real video devices: Definitions
• Pixel aspect ratio: width/height usually 1.
• Image aspect ration: m/n: 4/3 for NTSC, 16/9 for HDTV.
• Refresh rate: nowadays can be between 60 to 480 Hz non-interlaced.
• Phosphorescence: light emitted after electron beam has passed.
• Monitor bandwidth
– Digital: bits or bytes per second
– Analog: cycles per second (Hz)
• Spot size: diameter of a single dot on the output device.
• Resolution: number of pixels
• Dots per inch: In some sense the absolute size of a pixel
• Dot pitch: Distance between phosphors
• Contrast
Dot pitch
• Measure based on particular technologies
• For LCDs it is the distance between phosphors of the
same color (usually the diagonal)
Credit: Xilliah from Wikipedia
Contrast and Contrast Ratio
• Same image displayed on two different monitors with
different contrast ratio (white/black)
Credit: Geoffrey Morrison/CNET
Common video Standards
• NTSC
– North America & Japan
– 30 Hz, interlaced, 525 lines
• PAL
– Commonwealth and Western Europe
– 25 Hz, interlaced, 625 lines
• SECAM
– France, Eastern Europe, Middle East
– 26 Hz, interlaced, 625 lines
• HDTV
– 16:9 aspect ratio, digital, interlaced or progressive
• UHDTV
– 4K video, 4xHDTV
Common display technologies
• CRT
• Passive Liquid Crystal
• Active Matrix (TFT) (transistors at grid points)
• Plasma Panel (neon bulbs)
• Active LEDs
• OLEDS
Summary
Polygon based Graphics Pipeline
Interactivity (real-time constraint)
RGB color space
Ideal camera
Z-buffer algorithm
Raytracing