程序代写代做代考 scheme assembly algorithm data structure gui Java GPU c++ assembler AI javascript cse3431-lecture1.key

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