1 of 208

Nima Kalantari

CSCE 441 - Computer Graphics

​

Rasterization

Many slides from Ren Ng, Pradeep Sen, and Scott Schaefer

2 of 208

Rasterization Pipeline

Vertex Processing

Triangle Processing

Rasterization

Fragment Processing

Framebuffer Operations

Display

Application

1

2

3

4

Input: vertices in 3D space

Vertex Stream

Vertices positioned in screen space

Triangle Stream

Triangles positioned in screen space

Fragment Stream

Fragments (one per covered sample)

Shaded Fragments

Shaded fragments

Output: image (pixels)

3 of 208

So far…

Vertex Processing

Triangle Processing

Rasterization

Fragment Processing

Framebuffer Operations

Display

Application

1

2

3

4

Input: vertices in 3D space

Vertex Stream

Vertices positioned in screen space

Triangle Stream

Triangles positioned in screen space

Fragment Stream

Fragments (one per covered sample)

Shaded Fragments

Shaded fragments

Output: image (pixels)

4 of 208

Now

Vertex Processing

Triangle Processing

Rasterization

Fragment Processing

Framebuffer Operations

Display

Application

1

2

3

4

Input: vertices in 3D space

Vertex Stream

Vertices positioned in screen space

Triangle Stream

Triangles positioned in screen space

Fragment Stream

Fragments (one per covered sample)

Shaded Fragments

Shaded fragments

Output: image (pixels)

5 of 208

Rasterization

  • Input: position of triangle vertices projected on screen
  • Output: set of pixel values approximating triangle

?

(2.2, 1.3)

(4.4, 11.0)

(15.3, 8.6)

6 of 208

Shape Primitives

  • Example shape primitives (OpenGL)

3dgep.com

7 of 208

Outline

  • Rasterizing lines
    • Simple algorithm
    • Midpoint
  • Rasterizing triangles
  • Barycentric Coordinates
  • Visibility

​

8 of 208

Problem

  • Points (P, Q) with integer coordinates
  • Which pixels should be drawn for a unit width line?

9 of 208

Problem

  • Points (P, Q) with integer coordinates
  • Which pixels should be drawn for a unit width line?

10 of 208

Problem

  • Points (P, Q) with integer coordinates
  • Which pixels should be drawn for a unit width line?

11 of 208

Special Lines - Horizontal

12 of 208

Special Lines - Horizontal

  • Increment x by 1, keep y constant

13 of 208

Special Lines - Vertical

14 of 208

Special Lines - Vertical

  • Keep x constant, increment y by 1

15 of 208

Special Lines - Diagonal

16 of 208

Special Lines - Diagonal

  • Increment x by 1, increment y by 1

17 of 208

How about Arbitrary Lines?

18 of 208

Representing a Line

19 of 208

Representing a Line – Slope-Intercept

  • Slope-intercept equation for a line:

​

​

b: y-intercept

m: slope

20 of 208

Representing a Line – Slope-Intercept

  • Slope-intercept equation for a line:

​

​

​

  • How can we compute the line from (xL , yL) to (xH , yH)?

​

b: y-intercept

m: slope

21 of 208

Representing a Line – Slope-Intercept

  • Slope-intercept equation for a line:

​

​

​

  • How can we compute the line from (xL , yL) to (xH , yH)?
    • Need to calculate m and b

​

b: y-intercept

m: slope

22 of 208

Outline

  • Rasterizing lines
    • Simple algorithm
    • Midpoint
  • Rasterizing triangles
  • Barycentric Coordinates
  • Visibility

​

23 of 208

Arbitrary Lines

  • Start from (xL , yL) and draw to (xH , yH) where xL < xH

​

24 of 208

Arbitrary Lines

​

​

  • Assume
  • Other lines by swapping x , y or negating
  • Take steps in x and determine where to fill y

​

25 of 208

Simple Algorithm

  • Start from (xL , yL) and draw to (xH , yH) where xL < xH

​

26 of 208

Simple Algorithm

  • Start from (xL , yL) and draw to (xH , yH) where xL < xH

​

27 of 208

Simple Algorithm

  • Start from (xL , yL) and draw to (xH , yH) where xL < xH

​

28 of 208

Simple Algorithm

  • Start from (xL , yL) and draw to (xH , yH) where xL < xH

​

29 of 208

Simple Algorithm

  • Start from (xL , yL) and draw to (xH , yH) where xL < xH

​

Only need to compute m!

30 of 208

Simple Algorithm - Example

31 of 208

Simple Algorithm - Example

32 of 208

Simple Algorithm - Example

33 of 208

Simple Algorithm - Example

34 of 208

Simple Algorithm - Example

35 of 208

Simple Algorithm - Example

36 of 208

Simple Algorithm - Example

37 of 208

Simple Algorithm - Example

38 of 208

Simple Algorithm - Example

39 of 208

Simple Algorithm - Example

40 of 208

Simple Algorithm - Example

41 of 208

Simple Algorithm - Example

42 of 208

Simple Algorithm - Example

43 of 208

Simple Algorithm - Example

44 of 208

Simple Algorithm - Example

45 of 208

Simple Algorithm - Example

46 of 208

Simple Algorithm - Example

47 of 208

Simple Algorithm - Example

48 of 208

Simple Algorithm - Example

49 of 208

Simple Algorithm - Example

50 of 208

Simple Algorithm - Example

51 of 208

Simple Algorithm - Problems

  • Floating point operations
  • Can we do better?

​

52 of 208

Outline

  • Rasterizing lines
    • Simple algorithm
    • Midpoint
  • Rasterizing triangles
  • Barycentric Coordinates
  • Visibility

​

53 of 208

Midpoint Algorithm

  • Will explain it for
  • Other lines by swapping x , y or negating

54 of 208

Midpoint Algorithm

  • Given a point, decide if we move E or NE on next step

55 of 208

Midpoint Algorithm

  • Given a point, decide if we move E or NE on next step

56 of 208

Midpoint Algorithm

  • Given a point, decide if we move E or NE on next step
  • Is the line above or below the midpoint?
    • Below: move E
    • Above: move NE

57 of 208

Midpoint Algorithm

  • Given a point, decide if we move E or NE on next step
  • Is the line above or below the midpoint?
    • Below: move E
    • Above: move NE

58 of 208

Midpoint Algorithm

  • Given a point, decide if we move E or NE on next step
  • Is the line above or below the midpoint?
    • Below: move E
    • Above: move NE

59 of 208

Midpoint Algorithm

  • Given a point, decide if we move E or NE on next step
  • Is the line above or below the midpoint?
    • Below: move E
    • Above: move NE

60 of 208

Midpoint Algorithm

  • Given a point, decide if we move E or NE on next step
  • Is the line above or below the midpoint?
    • Below: move E
    • Above: move NE

61 of 208

Midpoint Algorithm

  • Given a point, decide if we move E or NE on next step
  • Is the line above or below the midpoint?
    • Below: move E
    • Above: move NE

62 of 208

Midpoint Algorithm

  • Given a point, decide if we move E or NE on next step
  • Is the line above or below the midpoint?
    • Below: move E
    • Above: move NE

63 of 208

Midpoint Algorithm

  • Given a point, decide if we move E or NE on next step
  • Is the line above or below the midpoint?
    • Below: move E
    • Above: move NE

64 of 208

Midpoint Algorithm

  • Given a point, decide if we move E or NE on next step
  • Is the line above or below the midpoint?
    • Below: move E
    • Above: move NE

65 of 208

Midpoint Algorithm

  • Given a point, decide if we move E or NE on next step
  • Is the line above or below the midpoint?
    • Below: move E
    • Above: move NE

66 of 208

Midpoint Algorithm

  • Given a point, decide if we move E or NE on next step
  • Is the line above or below the midpoint?
    • Below: move E
    • Above: move NE

67 of 208

Midpoint Algorithm

  • Given a point, decide if we move E or NE on next step
  • Is the line above or below the midpoint?

Midpoint at

68 of 208

Midpoint Algorithm

  • Given a point, decide if we move E or NE on next step
  • Is the line above or below the midpoint? (how?)

Midpoint at

69 of 208

Representing a Line

70 of 208

Representing a Line – Implicit Form

  • Implicit lines in 2D are written as

71 of 208

Representing a Line – Implicit Form

PL

PH

72 of 208

Representing a Line – Implicit Form

PL

PH

T

Line Tangent Vector

73 of 208

Representing a Line – Implicit Form

(x, y)

(-y, x)

Perpendicular

Vector in 2D

74 of 208

Representing a Line – Implicit Form

PL

PH

T

N

75 of 208

Representing a Line – Implicit Form

PL

PH

N

76 of 208

Representing a Line – Implicit Form

PL

PH

P = (x , y)

N

77 of 208

Representing a Line – Implicit Form

PL

PH

P = (x , y)

N

V

78 of 208

Representing a Line – Implicit Form

PL

PH

P = (x , y)

N

V

79 of 208

Representing a Line – Implicit Form

PL

PH

P = (x , y)

N

V

80 of 208

Representing a Line – Implicit Form

PL

PH

P = (x , y)

N

V

81 of 208

Representing a Line – Implicit Form

PL

PH

P = (x , y)

N

V

82 of 208

Representing a Line – Implicit Form

PL

PH

P = (x , y)

N

V

83 of 208

Representing a Line – Implicit Form

PL

PH

P = (x , y)

N

V

84 of 208

Representing a Line – Implicit Form

PL

PH

P = (x , y)

N

V

85 of 208

Representing a Line – Implicit Form

PL

PH

P = (x , y)

N

V

86 of 208

Representing a Line – Implicit Form

A

B

C

87 of 208

Example

88 of 208

Example

89 of 208

Example

90 of 208

Example

91 of 208

Example

 

92 of 208

Example

 

93 of 208

Example

 

94 of 208

Midpoint Algorithm

  • Given a point, decide if we move E or NE on next step
  • Is the line above or below the midpoint? (how?)

Midpoint at

95 of 208

Midpoint Algorithm

  • Given a point, decide if we move E or NE on next step
  • Is the line above or below the midpoint?

Midpoint at

96 of 208

Midpoint Algorithm

  • Given a point, decide if we move E or NE on next step
  • Is the line above or below the midpoint?

Requires evaluating the line function

Too slow!

97 of 208

Midpoint Algorithm

  • Build incremental algorithm
  • Assume we have value of

98 of 208

Midpoint Algorithm

  • Build incremental algorithm
  • Assume we have value of
    • Find value of if E chosen

99 of 208

Midpoint Algorithm

  • Build incremental algorithm
  • Assume we have value of
    • Find value of if E chosen

100 of 208

Midpoint Algorithm

  • Build incremental algorithm
  • Assume we have value of
    • Find value of if E chosen
    • Find value of if NE chosen

101 of 208

Midpoint Algorithm

  • Build incremental algorithm
  • Assume we have value of
    • Find value of if E chosen
    • Find value of if NE chosen

102 of 208

Midpoint Algorithm

  • If E chosen
    • Assume we have
    • Compute

103 of 208

Midpoint Algorithm

  • If E chosen
    • Assume we have
    • Compute

line equation

104 of 208

Midpoint Algorithm

  • If E chosen
    • Assume we have
    • Compute

line equation

105 of 208

Midpoint Algorithm

  • If E chosen
    • Assume we have
    • Compute

line equation

106 of 208

Midpoint Algorithm

  • If E chosen
    • Assume we have
    • Compute

line equation

107 of 208

Midpoint Algorithm

  • Build incremental algorithm
  • Assume we have value of
    • Find value of if E chosen ( )
    • Find value of if NE chosen

108 of 208

Midpoint Algorithm

  • If NE chosen
    • Assume we have
    • Compute

109 of 208

Midpoint Algorithm

  • If NE chosen
    • Assume we have
    • Compute

110 of 208

Midpoint Algorithm

  • Build incremental algorithm
  • Assume we have value of
    • Find value of if E chosen ( )
    • Find value of if NE chosen ( )

111 of 208

Midpoint Algorithm

  • Build incremental algorithm
  • Assume we have value of
    • Find value of if E chosen ( )
    • Find value of if NE chosen ( )

What about the very first value?

112 of 208

Midpoint Algorithm

  • Build incremental algorithm
  • Assume we have value of
    • Find value of if E chosen ( )
    • Find value of if NE chosen ( )

What about the very first value?

113 of 208

First Midpoint

= 0 (Point on the line)

114 of 208

Summary

  • Start with
  • If E chosen
  • If NE chosen

​

  • To avoid the floating-point operation in the start value
    • Multiply them by 2

115 of 208

Summary

  • Start with
  • If E chosen
  • If NE chosen

​

  • To avoid the floating-point operation in the start value
    • Multiply them by 2

116 of 208

Midpoint Algorithm

Requires evaluating the line function

Too slow!

117 of 208

Midpoint Algorithm

118 of 208

Midpoint Algorithm

119 of 208

Midpoint Algorithm

120 of 208

Midpoint Algorithm

121 of 208

Midpoint Algorithm

122 of 208

Midpoint Algorithm

123 of 208

Midpoint Algorithm

124 of 208

Midpoint Algorithm

125 of 208

Midpoint Algorithm – Example

126 of 208

Midpoint Algorithm – Example

127 of 208

Midpoint Algorithm – Example

128 of 208

Midpoint Algorithm – Example

129 of 208

Midpoint Algorithm – Example

130 of 208

Midpoint Algorithm – Example

131 of 208

Midpoint Algorithm – Example

132 of 208

Midpoint Algorithm – Example

133 of 208

Midpoint Algorithm – Example

134 of 208

Midpoint Algorithm – Example

135 of 208

Midpoint Algorithm – Example

136 of 208

Midpoint Algorithm – Example

137 of 208

Midpoint Algorithm – Example

138 of 208

Midpoint Algorithm – Example

139 of 208

Midpoint Algorithm – Example

140 of 208

Midpoint Algorithm – Example

141 of 208

Midpoint Algorithm – Example

142 of 208

Midpoint Algorithm – Example

143 of 208

Midpoint Algorithm – Example

144 of 208

Midpoint Algorithm – Example

145 of 208

Midpoint Algorithm – Example

146 of 208

Midpoint Algorithm – Example

147 of 208

Midpoint Algorithm – Example

148 of 208

Midpoint Algorithm – Example

149 of 208

Midpoint Algorithm – Example

150 of 208

Midpoint Algorithm – Example

151 of 208

Midpoint Algorithm – Example

152 of 208

Midpoint Algorithm – Example

153 of 208

Midpoint Algorithm – Example

154 of 208

Midpoint Algorithm – Example

155 of 208

Outline

  • Rasterizing lines
    • Simple algorithm
    • Midpoint
  • Rasterizing triangles
  • Barycentric Coordinates
  • Visibility

​

156 of 208

What Pixel Values Approximate a Triangle?

  • Input: position of triangle vertices projected on screen
  • Output: set of pixel values approximating triangle

?

(2.2, 1.3)

(4.4, 11.0)

(15.3, 8.6)

157 of 208

Sampling a Function

  • Evaluating a function at a point is sampling
  • We can discretize a function by periodic sampling

� for( int x = 0; x < xmax; x++ )

output[x] = f(x);

​

  • Sampling is a core idea in graphics. We’ll sample time (1D), area (2D), volume (3D) …

158 of 208

Let’s Try Rasterization As 2D Sampling

159 of 208

Sample If Each Pixel Center Is Inside Triangle

160 of 208

Sample If Each Pixel Center Is Inside Triangle

161 of 208

Sample Locations

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

(0,h)

(w,h)

(0,0)

(w,0)

Sample location for pixel (x,y)

(x+1/2,y+1/2)

162 of 208

Rasterization = Sampling A 2D Indicator Function

� for( int x = 0; x < xmax; x++ )

for( int y = 0; y < ymax; y++ )

Image[x][y] = f(x + 0.5, y + 0.5);

​

  • Rasterize triangle tri by sampling the function �f(x,y) = inside(tri,x,y)

163 of 208

Define Binary Function: inside(tri,x,y)

inside(t,x,y) =

1

0

(x,y) in triangle t

otherwise

164 of 208

Evaluating inside(tri,x,y)

165 of 208

How to evaluate inside function?

P0

P1

P2

166 of 208

Triangle = Intersection of Three Half Planes

P0

P1

P2

167 of 208

Each Line Defines Two Half-Planes

  • Implicit line equation
    • f01(x,y) = Ax + By + C
    • On line: f(x,y) = 0
    • Above line: f(x,y) > 0
    • Below line: f(x,y) < 0

> 0

< 0

= 0

P0

P1

168 of 208

Point-in-Triangle Test: Three Line Tests

P0

P1

P2

Compute line equations

from pairs of vertices

169 of 208

Point-in-Triangle Test: Three Line Tests

P0

P1

P2

170 of 208

Point-in-Triangle Test: Three Line Tests

P0

P1

P2

171 of 208

Point-in-Triangle Test: Three Line Tests

P0

P1

P2

172 of 208

Point-in-Triangle Test: Three Line Tests

Sample point is inside the triangle if it is inside all three lines.

​

​

P0

P1

P2

Note that the vertices should be

visited in a CCW order!

173 of 208

Performance Improvement

  • Compute a bounding box first

174 of 208

Performance Improvement

175 of 208

Performance Improvement

  • Compute a bounding box first
  • Incremental update

176 of 208

Performance Improvement

P0

P1

P2

177 of 208

Edge Cases (Literally)

  • Is this sample covered by triangle 1, triangle 2, or both?

1

2

178 of 208

Incorrect solution #1

  • Set the inside test to ‘≥’ to double rasterize
  • Problem: rendering semi-transparent triangles:

179 of 208

Incorrect solution #2

  • Set the inside test to ‘>’ to ignore samples on the edge
  • Problem:

180 of 208

Correct Solution

T1

T2

T1

T2

181 of 208

Correct Solution

T1

T2

T1

T2

182 of 208

Correct Solution

T1

T2

T1

T2

183 of 208

Correct Solution

T1

T2

T1

T2

184 of 208

Correct Solution

T1

T2

T1

T2

185 of 208

Outline

  • Rasterizing lines
    • Simple algorithm
    • Midpoint
  • Rasterizing triangles
  • Barycentric Coordinates
  • Visibility

​

186 of 208

Interpolation Across Triangles

  • Why do we want to interpolate?
    • Specify values (e.g. texture coordinates) at vertices, and obtain smoothly varying values across surface
  • What do we want to interpolate?
    • Texture coordinates, colors, normal vectors, …
  • How do we interpolate?
    • Barycentric coordinates

187 of 208

Linear Interpolation Across Triangle

  • VA, VB, VC can be positions, texture coordinates, color, normal vectors, material attributes…

​

188 of 208

Computing Barycentric Coordinates

  • LPQ(x,y) is proportional to the distance from line PQ

189 of 208

Barycentric Coordinate Formulas

190 of 208

Barycentric Coordinates

  • Alternative geometric viewpoint — proportional areas

191 of 208

Outline

  • Rasterizing lines
    • Simple algorithm
    • Midpoint
  • Rasterizing triangles
  • Barycentric Coordinates
  • Visibility

​

192 of 208

Problem

  • Multiple triangles map to the same pixel

193 of 208

Painter’s Algorithm

  • Inspired by how painters paint
  • Paint from back to front, overwrite in the framebuffer

[Wikipedia]

194 of 208

Painter’s Algorithm

  • Sort triangles according to their distance from the camera (depth)
  • Draw from back to front

195 of 208

Painter’s Algorithm

  • z = 10, z = 5, z = 2

196 of 208

Painter’s Algorithm

  • z = 10, z = 5, z = 2

197 of 208

Painter’s Algorithm

  • Requires sorting in depth, O(n log n) for n triangles
  • Can have unresolvable depth order

[Foley et al.]

198 of 208

Z-Buffer

  • Idea:
    • Store current min. z-value for each pixel
    • Needs an additional buffer for depth values
      • Color buffer stores RBG color values
      • Depth buffer (z-buffer) stores depth (16 to 32 bits)

199 of 208

Z-Buffer Example

Image credit: Dominic Alves, flickr.

Rendering

Depth buffer

200 of 208

Z-Buffer Algorithm

  • Initialize depth buffer to ∞
  • During rasterization:

for (each triangle T)

for (each fragment (x,y) in T)

if (z < depthbuffer[x,y]) // closest sample so far

colorbuffer[x,y] = rgb; // update color

depthbuffer[x,y] = z; // update z

else

; // do nothing, this simple is not closest

201 of 208

Z-Buffer Algorithm

202 of 208

Z-Buffer Complexity

  • Complexity
    • O(n) for n triangles
  • Most important visibility algorithm
    • Implemented in hardware for all GPUs
    • Used by OpenGL

203 of 208

Rasterization Pipeline

Vertex Processing

Triangle Processing

Rasterization

Fragment Processing

Framebuffer Operations

Display

Application

1

2

3

4

Input: vertices in 3D space

Vertex Stream

Vertices positioned in screen space

Triangle Stream

Triangles positioned in screen space

Fragment Stream

Fragments (one per covered sample)

Shaded Fragments

Shaded fragments

Output: image (pixels)

204 of 208

Transformations

Vertex Processing

Triangle Processing

Rasterization

Fragment Processing

Framebuffer Operations

Display

Application

1

2

3

4

Input: vertices in 3D space

Vertex Stream

Vertices positioned in screen space

Triangle Stream

Triangles positioned in screen space

Fragment Stream

Fragments (one per covered sample)

Shaded Fragments

Shaded fragments

Output: image (pixels)

205 of 208

Triangles formed

Vertex Processing

Triangle Processing

Rasterization

Fragment Processing

Framebuffer Operations

Display

Application

1

2

3

4

Input: vertices in 3D space

Vertex Stream

Vertices positioned in screen space

Triangle Stream

Triangles positioned in screen space

Fragment Stream

Fragments (one per covered sample)

Shaded Fragments

Shaded fragments

Output: image (pixels)

206 of 208

Rasterization

Vertex Processing

Triangle Processing

Rasterization

Fragment Processing

Framebuffer Operations

Display

Application

1

2

3

4

Input: vertices in 3D space

Vertex Stream

Vertices positioned in screen space

Triangle Stream

Triangles positioned in screen space

Fragment Stream

Fragments (one per covered sample)

Shaded Fragments

Shaded fragments

Output: image (pixels)

207 of 208

Shading

Vertex Processing

Triangle Processing

Rasterization

Fragment Processing

Framebuffer Operations

Display

Application

1

2

3

4

Input: vertices in 3D space

Vertex Stream

Vertices positioned in screen space

Triangle Stream

Triangles positioned in screen space

Fragment Stream

Fragments (one per covered sample)

Shaded Fragments

Shaded fragments

Output: image (pixels)

208 of 208

Visibility

Vertex Processing

Triangle Processing

Rasterization

Fragment Processing

Framebuffer Operations

Display

Application

1

2

3

4

Input: vertices in 3D space

Vertex Stream

Vertices positioned in screen space

Triangle Stream

Triangles positioned in screen space

Fragment Stream

Fragments (one per covered sample)

Shaded Fragments

Shaded fragments

Output: image (pixels)