1 of 106

Computer Graphics

Raimond Tunnel

MTAT.03.015

2 of 106

Previously

Previously

2 / 106

3 of 106

Previously

Shadows

3 / 106

4 of 106

CAM

Shadows

AREA LIGHT

OCCLUDER

NO SHADOW

4 / 106

5 of 106

CAM

Shadows

AREA LIGHT

OCCLUDER

UMBRA�FULL SHADOW

5 / 106

6 of 106

CAM

Shadows

AREA LIGHT

OCCLUDER

PENUMBRA�HALF SHADOW

UMBRA

6 / 106

7 of 106

CAM

Shadows

AREA LIGHT

OCCLUDER

ANTUMBRA�AFTER SHADOW

UMBRA

PENUMBRA

PENUMBRA

7 / 106

8 of 106

Shadows

AREA LIGHT

OCCLUDER

UMBRA

PENUMBRA

PENUMBRA

ANTUMBRA

8 / 106

9 of 106

Shadows

AREA LIGHT

OCCLUDER

UMBRA

PENUMBRA

PENUMBRA

ANTUMBRA

What is happens with our point and directional lights?

9 / 106

10 of 106

Shadow Algorithms

  • Projection Shadow – In the Basic I bonus task. �One of the early shadow algorithms.
  • Ray Traced Shadows – You can cast shadow rays to detect if a surface is occluded.
  • Shadow Mapping – Very popular today. Many improvements (eg cascaded shadow mapping).
  • Shadow Volume – In Doom 3 (2004).

10 / 106

11 of 106

Projection Shadow

Basic 1 bonus task

11 / 106

12 of 106

Ray Traced Shadows

HIT

n

l

OCCLUDER

RAY

SHADOW

CAM

12 / 106

13 of 106

Shadow Mapping

CAM

OBJECT

OBJECT

LIGHT

VIEW FRUSTUM

13 / 106

14 of 106

Shadow Mapping

CAM

LIGHT

14 / 106

15 of 106

Shadow Mapping

LIGHT CAM VIEW

CAM

LIGHT

15 / 106

16 of 106

Shadow Mapping

SHADOW MAP

CAM

LIGHT

16 / 106

17 of 106

Shadow Mapping

SHADOW MAP

17 / 106

18 of 106

Shadow Mapping

SHADOW MAP

DEPTH�TO LIGHT CAM

How to find this depth?

18 / 106

19 of 106

Shadow Mapping

SHADOW MAP

DEPTH�TO LIGHT CAM

SAVED CLOSEST DEPTH�TO LIGHT CAM

19 / 106

20 of 106

Shadow Mapping

SHADOW MAP

DEPTH�TO LIGHT CAM

SAVED CLOSEST DEPTH�TO LIGHT CAM

What happens when…?

DEPTH

CLOSEST

DEPTH

CLOSEST

20 / 106

21 of 106

Shadow Mapping

POINT LIGHT

PERSPECTIVE PROJECTION

21 / 106

22 of 106

Shadow Mapping

DIRECTIONAL LIGHT

ORTHOGRAPHIC PROJECTION

22 / 106

23 of 106

Shadow Mapping

DIRECTIONAL LIGHT

What problems does

the shadow mapping

algorithm have?

ORTHOGRAPHIC PROJECTION

23 / 106

24 of 106

Shadow Mapping

+X axis CAM

512 × 512

24 / 106

25 of 106

Shadow Mapping

+X axis CAM

128 × 128

25 / 106

26 of 106

Shadow Mapping

+X axis CAM

32 × 32

26 / 106

27 of 106

Shadow Volume

CAM

OBJECT

LIGHT

OBJECT

OBJECT

27 / 106

28 of 106

Shadow Volume

SHADOW VOLUME

28 / 106

29 of 106

Shadow Volume

+1

-1

ENTERING �A VOLUME

EXITING� A VOLUME

0

29 / 106

30 of 106

Shadow Volume

+1

ENTERING �A VOLUME

1

30 / 106

31 of 106

Shadow Volume – Volume Creation

LIGHT

MESH

31 / 106

32 of 106

Shadow Volume – Volume Creation

SHADE SIDE

LIT SIDE

SILHOUETTE EDGES

32 / 106

33 of 106

Shadow Volume – Volume Creation

SHADE SIDE

LIT SIDE

SILHOUETTE EDGES

How to find the �silhouette edges?

33 / 106

34 of 106

Shadow Volume – Volume Creation

34 / 106

35 of 106

Shadow Volume – Volume Creation

LIGHT CAP

DARK CAP

SIDE

35 / 106

36 of 106

Shadow Volume – Volume Creation

(x, y, z) → (x, y, z, 0)

PROJECTING THE DARK GAP TO INFINITY

(0, 0, 0)

36 / 106

37 of 106

Shadow Volume – Volume Creation

THE SHADOW VOLUME

37 / 106

38 of 106

Stencil Buffer

FRAMEBUFFER

COLOR�BUFFER

38 / 106

39 of 106

Stencil Buffer

FRAMEBUFFER

COLOR�BUFFER

DEPTH�BUFFER

39 / 106

40 of 106

Stencil Buffer

FRAMEBUFFER

COLOR�BUFFER

DEPTH�BUFFER

STENCIL�BUFFER

RENDER

40 / 106

41 of 106

Stencil Testing

glStencilFunc( function, value, ...)

GL_NEVER�GL_LESS�GL_LEQUAL�GL_GREATER�GL_GEQUAL�GL_EQUAL�GL_NOTEQUAL�GL_ALWAYS

[integer]

41 / 106

42 of 106

Stencil Creation

glStencilOp( sfail , dpfail , dppass )

GL_KEEP�GL_ZERO GL_REPLACE�GL_INVERT

GL_INCR�GL_INCR_WRAP�GL_DECR

GL_DECR_WRAP�

  • To create the stencil, you render to it.

STENCIL

DEPTH

×

ANY

✔

STENCIL

DEPTH

×

✔

✔

STENCIL

DEPTH

TEST:

RESULT:

42 / 106

43 of 106

Shadow Volume – Testing

BACK FACES OF SHADOW VOLUMES THAT PASS THE SCENE DEPTH TESTING

-1

DECREASE STENCIL VALUE

43 / 106

44 of 106

Shadow Volume – Testing

FRONT FACES OF SHADOW VOLUMES THAT PASS THE SCENE DEPTH TESTING

+1

INCREASE�STENCIL VALUE

44 / 106

45 of 106

Shadow Volume – Testing

n

STENCIL VALUE == 0�RENDER DIRECT LIGHTING�

l

45 / 106

46 of 106

Shadow Volume – Depth Pass

  • We count the front faces of volumes minus the back faces of volumes in front of the fragment.

+1

+1

+1

+1

+1

-1

46 / 106

47 of 106

Shadow Volume – Depth Pass

  • We count the front faces of volumes minus the back faces of volumes in front of the fragment.

One of these has a problem!

+1

+1

+1

+1

+1

-1

47 / 106

48 of 106

Shadow Volume – Depth Fail

  • We count the front faces of volumes minus the back faces of volumes back of the fragment.

Carmack’s Reverse

-1

-1

-1

-1

-1

+1

-1

48 / 106

49 of 106

Shadow Volume

49 / 106

50 of 106

Doom 3 (2004) https://www.youtube.com/watch?v=iZV3NhvA2Ag

Questions?

50 / 106

51 of 106

Conclusion

51 / 106

52 of 106

  • Uses of Computer Graphics
    • Games and entertainment
    • Graphical user interfaces (GUI)
    • Computer-aided design (CAD)
    • Scientific simulation visualization
    • Data visualization
    • Simulations
    • Simulators
    • Art

Conclusion

Avengers: Infinity War, Marvel Studios

Parker Solar Probe, NASA

52 / 106

53 of 106

  • Coordinate Systems
    • Left / Right Handed

Conclusion

z

y

x

x

y

z

53 / 106

54 of 106

  • Coordinate Systems
    • Left / Right Handed
  • Triangles
    • Planar

Conclusion

A

B

C

A

C

B

54 / 106

55 of 106

  • Coordinate Systems
    • Left / Right Handed
  • Triangles
    • Planar
  • Polygons
    • Convex / Concave
    • Simple

Conclusion

A

B

C

A

B

C

D

A

B

C

D

A

B

C

D

E

F

G

H

55 / 106

56 of 106

Conclusion

  • Points and Vectors

x

y

ORIGIN

v

v

v = (0.8, 1.4)

A

B = (3.44, 1.0)

D

C = (7.2, 2.3)

u

56 / 106

57 of 106

Conclusion

  • Points and Vectors
  • Convex Combination
  • Barycentric Coordinates

A

B

C

X

A

B

C

57 / 106

58 of 106

Conclusion

Vertex Shader

Culling & Clipping

Rasterization

Fragment Shader

Visibility tests�Blending

Vertex transformations.

Object’s local space → clip space

Clip space → viewport space

Determine front-facing triangles.

Determine which vertices are visible.

Fill the triangle with fragments.

Calculate color values for pixels.

Is the fragment visible?�Blend together multiple fragments.

Construct geometry

Define transformations

Set material properties

  • The Standard Graphics Pipeline

58 / 106

59 of 106

Conclusion

  • Linear Transformations
    • Rotation
    • Scale
    • Shear

α

59 / 106

60 of 106

(2, 1)

(3, 1)

(5, 1)

(7, 1)

Conclusion

  • Linear Transformations
    • Rotation
    • Scale
    • Shear
  • Affine Transformations
    • Translation

1D WORLD

60 / 106

61 of 106

Conclusion

  • Linear Transformations
    • Rotation
    • Scale
    • Shear
  • Affine Transformations
    • Translation
  • Homogeneous Coordinates

p

61 / 106

62 of 106

Conclusion

  • Augmented Transformation Matrix

Affine

trasnformation

matrix

Must be 1

Translation column

Used for perspective projection...

Linear transformations

62 / 106

63 of 106

Conclusion

  • Projection
    • Orthographic

NEAR

FAR

C

A

B

CAM

y

z

TOP

BOTTOM

63 / 106

64 of 106

Conclusion

  • Projection
    • Orthographic
    • Perspective

NEAR

FAR

z

CAM

FOVv

WIDTH

HEIGHT

ASPECT RATIO =

WIDTH

HEIGHT

x

y

C

A

B

y

64 / 106

65 of 106

Conclusion

  • Frames of Reference
    • Object Space

y

x

65 / 106

66 of 106

Conclusion

  • Frames of Reference
    • Object Space
    • World Space

y

x

66 / 106

67 of 106

  • Frames of Reference
    • Object Space
    • World Space
    • View Space

y

z

Conclusion

67 / 106

68 of 106

  • Frames of Reference
    • Object Space
    • World Space
    • View Space
    • Clip Space

Conclusion

68 / 106

69 of 106

  • Frames of Reference
    • Object Space
    • World Space
    • View Space
    • Clip Space
    • Normalized Device Coordinates Space

Conclusion

(1, -1, -1)

(1, -1, 1)

(-1, 1, 1)

(1, 1, 1)

(-1, 1, -1)

(-1, -1, -1)

x

y

z

69 / 106

70 of 106

  • Frames of Reference
    • Object Space
    • World Space
    • View Space
    • Clip Space
    • Normalized Device Coordinates Space
    • Screen Space

Conclusion

y

x

70 / 106

71 of 106

Conclusion

  • Shading Schemes
    • Flat
    • Gouraud
    • Phong

per polygon

per vertex

per fragment

71 / 106

72 of 106

  • Shading Schemes
    • Flat
    • Gouraud
    • Phong
  • Lighting Models
    • Lambert
    • Phong
    • Blinn-Phong

Conclusion

n

r

v

Light

l

Viewer

72 / 106

73 of 106

Conclusion

  • Shading Models
    • Flat
    • Gouraud
    • Phong
  • Lighting Models
    • Lambert
    • Phong
    • Blinn-Phong
  • sRGB Color Space and Gamma

(0.5, 0.5, 0.5)

Black and white stripes

73 / 106

74 of 106

Conclusion

1

1

0

  • Textures
    • UV Mapping

74 / 106

75 of 106

Conclusion

Sampled Moiré Alias

Original Signal

  • Textures
    • UV Mapping
    • Sampling and Aliasing

75 / 106

76 of 106

Conclusion

TEXTURE

TEXTURE

  • Textures
    • UV Mapping
    • Sampling and Aliasing
    • Interpolation
    • Nearest neighbor
    • Bilinear

76 / 106

77 of 106

Conclusion

MIPMAP (8×8)

MIPMAP (4×4)

RESULT (5×5)

1/4

3/4

  • Textures
    • UV Mapping
    • Sampling and Aliasing
    • Interpolation
    • Nearest neighbor
    • Bilinear
    • Mipmapping
    • Trilinear filtering

77 / 106

78 of 106

Conclusion

  • Blending
    • Alpha
      • Conventional
      • Premultiplied

ALPHA BLEEDING

CORRECT BLENDING

78 / 106

79 of 106

Conclusion

  • Blending
    • Alpha
      • Conventional
      • Premultiplied
    • General Blending Function
      • Alpha Blending
      • Additive
      • Multiplicative

blend(source, destination) =

= sourceRGB * [sourceFactor]� [blendFunction]� destinationRGB * [destinationFactor]

79 / 106

80 of 106

Conclusion

  • Code + Design + Art
    • The Door Problem

80 / 106

81 of 106

Conclusion

  • Code + Design + Art
    • The Door Problem
  • Vertical Slice

The Last Guardian (2016)

81 / 106

82 of 106

Conclusion

  • Code + Design + Art
    • The Door Problem
  • Vertical Slice
  • Game Engine
    • Runtime (framework)
    • Tools

GAME ENGINE

RUNTIME

TOOLS

+

82 / 106

83 of 106

Conclusion

  • Code + Design + Art
    • The Door Problem
  • Vertical Slice
  • Game Engine
    • Runtime (framework)
    • Tools
    • Layered architecture

GAME

ENGINE PRODUCT

MID-CORE

LOW-CORE

DEVICE

OS

PLATFORM

GAME ENGINE

83 / 106

84 of 106

Conclusion

  • Code + Design + Art
    • The Door Problem
  • Vertical Slice
  • Game Engine
    • Runtime (framework)
    • Tools
    • Layered architecture
  • Third-party SDKs �(middleware)

84 / 106

85 of 106

Conclusion

  • Curves
    • Smoothness Cn and Gn

SUDDEN JUMP IN MAGNITUDE

85 / 106

86 of 106

Conclusion

  • Curves
    • Smoothness Cn and Gn
    • Construction with constraints

p0

p1

p2

p0

p1

p2

86 / 106

87 of 106

Conclusion

  • Curves
    • Smoothness Cn and Gn
    • Construction with constraints
  • Splines
    • Hermite

87 / 106

88 of 106

Conclusion

  • Curves
    • Smoothness Cn and Gn
    • Construction with constraints
  • Splines
    • Hermite
    • Catmull-Rom

88 / 106

89 of 106

Conclusion

  • Curves
    • Smoothness Cn and Gn
    • Construction with constraints
  • Splines
    • Hermite
    • Catmull-Rom
    • Bezier

89 / 106

90 of 106

Conclusion

  • Procedural Generation
    • Noise
      • Value noise
      • Gradient noise (eg, Perlin)

90 / 106

91 of 106

Conclusion

  • Procedural Generation
    • Noise
      • Value noise
      • Gradient noise (eg, Perlin)
    • Lindenmayer Systems

91 / 106

92 of 106

Conclusion

  • Procedural Generation
    • Noise
      • Value noise
      • Gradient noise (eg, Perlin)
    • Lindenmayer Systems
    • Particle Systems
      • Boids

Simulating the Collective Movement of Fish Schools (BSc thesis) �by Erik Martin Vetemaa

92 / 106

93 of 106

Conclusion

A

B

C

e

f

HIT

S

d

  • Ray Casting
    • Ray-Triangle Intersection

93 / 106

94 of 106

  • Ray Casting
    • Ray-Triangle Intersection
  • Ray Tracing
    • Ray Trace Rendering

Conclusion

RAY

RAY

RAY

RAY

RAY

94 / 106

95 of 106

  • Ray Casting
    • Ray-Triangle Intersection
  • Ray Tracing
    • Ray Trace Rendering
  • Data Structures
    • AABB and k-DOP
    • Octree
    • K-D Tree
    • Bounding Volume Hierarcy

Conclusion

https://nns.tume-maailm.pri.ee/

QUADTREE

95 / 106

96 of 106

Conclusion

  • Global Illumination
    • Path Tracing

​

n

Ω

d

RANDOM

BOUNCE RAY

d ⇜ Ω

​

96 / 106

97 of 106

Conclusion

  • Global Illumination
    • Path Tracing
    • Photon Mapping

Photon Mapping (In Estonian) by Hendrik Eerikson

97 / 106

98 of 106

Conclusion

  • Global Illumination
    • Path Tracing
    • Photon Mapping
    • Radiosity

ITERATION

98 / 106

99 of 106

Conclusion

  • Global Illumination
    • Path Tracing
    • Photon Mapping
    • Radiosity
  • The Rendering Equation

Ω

p

p

p

p

ω

out

ω

out

ω

in

ω

in

ω

in

ω

in

ω

out

n

99 / 106

100 of 106

Conclusion

  • Global Illumination
    • Path Tracing
    • Photon Mapping
    • Radiosity
  • The Rendering Equation
  • BRDF – Bidirectional Reflectance Distribution Function

DIRECT�REFLECTION

INCOMING�LIGHT

PHONG

LAMBERT

1

1

0

100 / 106

101 of 106

Conclusion

AREA LIGHT

OCCLUDER

UMBRA

PENUMBRA

PENUMBRA

ANTUMBRA

  • Shadows
    • Umbra, penumbra, antumbra

101 / 106

102 of 106

  • Shadows
    • Umbra, penumbra, antumbra
  • Algorithms
    • Projection Shadows
    • Shadow Rays
    • Shadow Mapping
    • Shadow Volume

Conclusion

102 / 106

103 of 106

Conclusion

  • Conclusion
    • Coordinate System Handedness

z

y

x

x

y

z

103 / 106

104 of 106

Conclusion

  • Conclusion
    • Coordinate System Handedness
    • Polygons
      • Convex and Concave
      • Simple

104 / 106

105 of 106

Computer Graphics

Thanks for the ride!

The End

105 / 106

106 of 106

What knowledge did you gain today?

What more would you like to know?

Next time: Open mic lecture!�INDUSTRY GUESTS

106 / 106