How does the basic “Clipping Algorithm / Cohen-Sutherland Algorithm” work
- 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
How does “𝜶-Clipping” work
- 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) )
How does the “Polygon Clipping” algorithm by “Sutherland-Hodgman” work in 2D
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
How does the “Point-Inside-Polygon” Test work
- “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
What’s the Problem with “Perspective Projection” and “De-Homogenization” regarding clipping? How can it be solved?
- 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
How to transform from “Normalized Device Coordinates” to “Viewport”
- 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)
How does “Line Rasterization” work? How does “Bresenham’s Line Algorithm” work?
- 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)
- 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)
What is a problem of “Line Rasterization” and how to fix it
- 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)
How does “Rasterization of Polygons” work via the “Brute Force” approach
- divide space into half spaces for each edge
- consistently orient such that distance to edge is positive if on half space of polygon
How does “Rasterization of Polygons” work via the “Scanline Polygon Rendering” approach? How to interpolate?
- 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
How to “Perspectively Interpolate Attributes” correctly
???
