05 - Rasterization, Projections and Clipping

Question 1

How does the basic “Clipping Algorithm / Cohen-Sutherland Algorithm” work

Answer 1

• decode endpoints of line based on divided box
  => 1 bit for each direction = 4 Bit
  => if outside of view encoding = 1, else = 0
• trivial accept: P1 ∨ P2 = 0000 == 0
• trivial reject: P1 ∧ P2 ≠≠ 0
• else non trivial
  => Bitwise operations

in case of non trivial:
- P1 and P2 have a bit difference
- calculate intersection with this edge (set Bit to 0)
- check again for line with this new point
-> if still not trivial: repeat process

Question 2

How does “𝜶-Clipping” work

Answer 2

• using “Window Edge Coordinates (WEC)”
• includes interpolation
  -> WEC_left(P) = px - xmin (and similar for other edges)
  -> WEC(P) < 0 => outside w.r.t to Edge (as with Cohen-Sutherland)
• introduce 𝜶
  -> line P1P2 = {P | P = P1 + 𝜶(P2-P1), 𝜶 ∈ [0, 1]}
• if we know there is an intersection with an edge (no trivial via Cohen-Sutherland)
  (assume P1 inside, P2 outside w.r.t. edge)
• for every edge with “out-code bit” set for P1 OR P2:
• 𝛼min = 0 ; 𝛼max = 1
• 𝛼s = WEC(P1) / ( WEC(P1) - WEC(P2) )
  => get point of intersection with edge
• if P1 outside (“out-code bit” set) => 𝛼min = max(𝛼min, 𝛼s)
  else 𝛼max = min(𝛼max, 𝛼s)
• if 𝛼min > 𝛼max => line outside
  else return line ( P1 + 𝛼min(P2-P1), P1 + 𝛼max(P2-P1) )

Question 3

How does the “Polygon Clipping” algorithm by “Sutherland-Hodgman” work in 2D

Answer 3

For “Convex” clipping regions:
- iterate over all vertices in order (adjacent vertices are connected by line)
- after each edge => closed polygon => pipeline process
- 4 cases:
– both points inside => include both points
– both points outside => exclude both points
– Pi inside, Pi+1 outside => include first P1and then intersection with edge
– Pi outside , Pi+1 inside => include first intersection with edge and then P2
=> decomposition of triangles easy: Q1, Qi, Qi+1 (can be problematic though -> thin triangles)
=> interpolation possible with attributes (colors, normals, texture coordinates)

For “Non-Convex” clipping regions:
- divide in convex areas

Question 4

How does the “Point-Inside-Polygon” Test work

Answer 4

• “Odd-Even-Test”
• for a point P consider line y = yP
  -> if P inside => odd number of intersections to left and right
  -> if P outside => even number of intersections to left and right
  => sufficient to shoot a ray in any direction: even / odd property holds

Problem: What if ray along edge / through vertex
Solution:
- shoot ray in positive x direction: R1 (below), R2 (above, including yP)
- only count if end points of edge lie in different regions

Question 5

What’s the Problem with “Perspective Projection” and “De-Homogenization” regarding clipping? How can it be solved?

Answer 5

• if clipping is done after de-homogenization -> wrong line segments
• lines can go to -∞ and come back from ∞
• clipping done in homogeneous clip coordinates
• 4d space “𝛼-Clipping”
• for de-homogenized view frustum it holds:
  – left (x’= -1) : w + x = 0
  – right (x’= 1) : w - x = 0
  – bottom (y’= -1) : w + y = 0
  – top (y’= 1) : w - y = 0
  – near (z’= -1) : w + z = 0
  – far (z’= 1) : w - z = 0

Question 6

How to transform from “Normalized Device Coordinates” to “Viewport”

Answer 6

• omit depth (= orthographic projection)
• (x’, y’) in [-1; 1]^2
• scale to image range [x; x + width] x [y; y + height] (which are still floating point)

Question 7

How does “Line Rasterization” work? How does “Bresenham’s Line Algorithm” work?

Answer 7

• only work with slopes 0 ≤ m ≤ 1 (perform mirroring by swapping x, y of points to achieve that)
• consider only x0≤ x ≤ x1 => calculate y for each x (=> “Consistency”)
  – could be done via brute force
  – better: done via incremental computation

Further Ideas:
- note: only 2 cases: next pixel to EAST or to NORTH-EAST
- find “Condition” to choose what case should be chosen
-> use y-value between two cases (edge of pixel)
-> check implicit representation of line -> F(x, y)
–> above point: NORTH-EAST
–> below point: EAST
=> multiplication still present + floating point precision problem

Bresenham’s Line Algorithm:
1. Incremental Version
- d := F(x0 + 1, y0 + 1/2) -> FTP number
- if d < 0
– NORTH-EAST case: (x0 + 1, y0 + 1)
– next test F(x0 + 2, y0 + 1.5)
–> change of d: (y0 - y1) + (x1 - x0)
–> d = d + (y0 - y1) + (x1 - x0)
- if d ≥ 0:
– EAST case
–> d = d + (y0 - y1)

2. Integer Version
   - only sign of d is relevant -> take d := 2F(x0 + 1, y0 + 1/2) to get rid of half
   -> NORTH-EAST: d = d + 2(y0 - y1) + 2(x1 - x0)
   -> EAST: d = d + 2(y0 - y1)

Question 8

What is a problem of “Line Rasterization” and how to fix it

Answer 8

• intensity dependent on line angle
  -> diagonal lines have more space between them
  fix:
• increase intensity for diagonals
• anti-aliasing
  -> store deviation between center of pixels and “perfect line”
  -> a = d/2Δx (a = -1/2 line through pixel center for NORTH-EAST case)

Question 9

How does “Rasterization of Polygons” work via the “Brute Force” approach

Answer 9

• divide space into half spaces for each edge
• consistently orient such that distance to edge is positive if on half space of polygon

Question 10

How does “Rasterization of Polygons” work via the “Scanline Polygon Rendering” approach? How to interpolate?

Answer 10

• one scanline after another (one row)
• determine intersections of scanline and polygon
• set pixel in between
• sorted list of vertices
• start at top most (smallest y) vertex (= Pt)
• edges to look at P_t-1Pt and P_t+1Pt
• slope formula to know what the x-coordinates are at these edges for increasing y
• if another point is reached, replace top point with this point and
• interpolate twice
  – first along edges
  – second along the scanline at the interpolated position from first interpolation

Question 11

How to “Perspectively Interpolate Attributes” correctly

Answer 11

???