Rasterization

Definition: Discretization of a shape, line or polygon specified by continuum of vector coordinates into pixel coordinates used to render it.

Line Rasterization: Bresenham Line Algorithm
Assumption: The start and end point lie on integer pixel coordinate

Problem: Which pixels to render while drawing a line joining $(x_0,y_0)$ and $(x_1,y_1)$

Step 1:
Project the line into first octant such that $(x_0,y_0)$ is projected to origin and $(x_1,y_1)$ is mapped to $(x',y')$ such that
- $x' \geq 0$
- $y' \geq 0$
- $x' \geq y$

Step 2:
$P \rightarrow $ the start pixel
$M \rightarrow $ the first midpoint
$M_{E} \rightarrow $ the next midpoint given we choose to render E
$M_{NE} \rightarrow $ the next midpoint given we choose to render NE pixel

Define $f(x,y) = mx + b - y$ where $y = mx + b$ is the equation of the line projected in first octant.
$f(M) = f(P_x + 1, P_y + \frac{1}{2}) = f(P) + m - \frac{1}{2}$
$f(M_E) = f(M) + m$
$f(M_{NE}) = f(M) + m - 1$

Now, $m = \frac{\Delta y}{\Delta x} \geq 0$. So define
$F(M) = 2 \Delta x f(M)$
$F(M_E) = 2 \Delta x f(M_E) = F + 2 \Delta y $
$F(M_{NE}) = 2 \Delta x f(M_{NE}) = F + 2 \Delta y - 2 \Delta x$
$F(M_{init}) = 2 \Delta y - \Delta x$

Final Algorithm:
$y = y_0$
$F = 2 \Delta y - \Delta x$
for $x=x_0:x_1$
  Render $(x,y)$
  if$(F \leq 0 )$     \* Take the East *\
      $F = F + 2 \Delta y$
  else$(F > 0)$     \* Take the North East *\
      $F = F + 2 \Delta y - 2 \Delta x$
end

Polygon Rasterization
First enforce consistent set of rules for when does a pixel belong to a polygon. The ambiguous case is when the edge passes through the pixel center. The other case is trivial.

The polygon will be rasterized one scanline at a time where the scanline progressively moves up.

Each edge is represented by coordinates $(x_{lower},y_{lower}),(x_{upper},y_{upper})$.

Maintain an Active Edge data structure with the following three fields
- $x$ coordinate where a scan line intersects the edge
- $\frac{dx}{dy}$
- $y_{upper}$
The entries (basically edges and their properties) in this data structure are sorted in order of $x$ first and $\frac{dx}{dy}$ next.

Algorithm:
- Add edges with $y = y_{lower}$ along with their attributes in the Active Edge data structure
- For every pair $(2i-1,2i)$ render pixels in the range $\lceil x_i \rceil$ to $\lceil x_{i+1} \rceil  - 1 $
- Remove edges with $y_{upper} = y$
- Update $x$ by $x = x + \frac{dx}{dy}$

Gouraud Interpolation
While rasterizing polygons, we need to interpolate vertex attributes such as colors to get the colors at the rendered pixels.
To do this:
- Maintain the attribute value along the edges of the  polygon in the Active Edge data structure
- Whenever we move the scan line up, update the attribute by $val = val + \frac{val_{upper}-val_{lower}}{y_{upper}-y{lower}}$
- When scanning from left to right the pixels are assigned attributes by $val = val + \frac{val_{right}-val_{left}}{x_{right} - x_{left}}$

Applications of Network Flow

Circulation with Demands

Given:
- Graph $G(V,E)$
- Capacities on the edges
- Demands for each vertex ${d_v}$ such that
    - $d_v > 0 \implies$ Net flow into vertex (Source)
    - $d_v < 0 \implies$ Net flow out of vertex (Sink)
    - $d_v = 0 \implies$ Inflow equals outflow (Normal Node)

Definition: Circulation
Circulation is a function $f: E \rightarrow \mathbb{R}^+$ which satisfies the following
- Bounded by capacity: $f(e) \leq c(e)$
- Conservation condition: $f^{in}(v) - f^{out}(v) = d_v$

Lemma: Necessary condition for Feasible circulation $\rightarrow \sum_v d_v = 0$ 
Proof:
\begin{align}
\sum_v d_v & = \sum_v f^{in}(v) - f^{out}(v) \\
                  & = \sum_v f^{in}(v) - \sum_v f^{out}(v) \\
                  & = 0
\end{align}
Since flow on every edge appears twice once as inflow on a vertex and other time as outflow on the other vertex on that edge.
In other words, there is a feasible solution only if $D = \sum_{v>0}d_v = \sum_{v<0} {- d_v}$

Algorithm: Finding Circulation 
- Check necessity condition
- Connect all vertices with $d_v < 0$ to a super source via edges with capacity $-d_v$
- Connect all vertices with $d_v > 0$ to a super source via edges with capacity $d_v$
- On this flow network $H$, compute max-flow
- If flow value is $D$, then we have a valid circulation
- Else, circulation is infeasible

Correctness:
If there is a valid circulation in $G$, then in $H$ there is a $s-t$ max flow with value $D$ obtained by pushing full capacities from source to the vertices with negative demand.

Conversely, a max-flow with value $D$ in $H$ is possible only when full capacities of the subordinate sources are used which implies that both capacity constraint and conservation condition are maintained. Hence there is a valid circulation in $G$.

Circulation with Demands and Lower bounds

Given:
- Graph $G(V,E)$
- Capacities on the edges
- Demands for each vertex ${d_v}$
- Lower bound for each edge $\ni l(e) \leq c(e)$

Now, a valid circulation is one where $l(e) \leq f(e) \leq c(e)$.

Algorithm: Get rid of the lower bound somehow and then solve the circulation with demands
- Push a flow equal to the lower bound on each edge
- It satisfies the bounds
- Does not satisfy the conservation of flow
- Let $L_v = f^{in}(v) - f^{out}(v)$ be the residual demand
- Set the new $d'_v = d_v - L_v$ and reduce the capacities to $c'(e) = c(e) - l(e)$ to get new graph $G'$
- The lower bounds vanish
- Solve the circulation problem in $G'$
- Add the circulation to the lower bounds $f = f_0 + f'$

Correctness:
Want to show that $G$ has valid circulation with demands and lower bounds if and only if $G'$ has a valid circulation with demands.
First we show, $(f \text{ is valid } \implies f' \text{ is valid } )$
- $f(e) - l(e) \leq c(e) - l(e) \implies f'(e) \leq c'(e) \rightarrow$ hence bounded by capacity
- $\sum_{e \; into \; v } (f(e) - l(e)) - \sum_{e \; out \; of \; v} (f(e) - l(e)) = d_v - L_v \rightarrow$ hence flow is conserved

Now we show, $(f '\text{ is valid } \implies f \text{ is valid } )$
- Clearly $l(e) \leq f_0(e) + f'(e) \leq l(e) + c'(e) = c(e) \rightarrow $ hence satisfies the bounds
- $\sum_{e \; into \; v } (l(e) + f'(e)) - \sum_{e \; out \; of \; v} (l(e) + f'(e)) = L_v + (d_v - L_v) = d_v \rightarrow$ hence the flow is conserved

Hence proved.

Survey Design

Problem Statement:
Given:
- Set of consumers
- Set of products
- List of products that each consumer has consumed

Want:
- To ask questions to the consumer about a subset of the products that the consumer used
- $i^{th}$ consumer would answer only questions in the range $[c_i, c'_i]$
- For the $i^{th}$ product we want to ask question in the range $[p_i, p'_i]$

Question:
How to assign questions to the consumers so that we get required information about each product while keeping the consumers happy?

Algorithm:
- Form a Bipartite graph with consumers on one side and products on the other
- Connect the consumers with the products that they used by an edge with capacity $1$
- Connect the consumers to a source $S$ with edges of capacities with lower $(c_i)$ and upper $(c'_i)$ bound
- Connect the products to a sink $T$ with edges of capacities with lower $(p_i)$ and upper $(p'_i)$ bound
- We want to get a flow from $S$ to $T$
- But we only know how to compute a circulation
- So connect $T$ to $S$ by an edge of infinite capacity
- Demands on all the vertices including source and sink is 0
- Happily compute a circulation with lower bounds on this network

Time Complexity: 
- $n$ consumers
- $u$ products
- $m \leftarrow$ sum of the number of products used by the consumers
- $|E| = m$
- $|V| = n + u$
- $O(|V||E|^2) = O((n+u) m^2)$

Applications of Network Flow

Edge Disjoint Paths Problem

Given:
- Directed or undirected graph $G$
- Vertices $s$ and $t$
- Parameter k

Task: Compute $k$ edge disjoint paths from $s$ to $t$

Directed Graph

Lemma: Number of edge disjoint paths equals max flow
- Construct a network flow $H$ where all edges have capacity $1$
- Since capacities are integral, the max-flow would have either $0$ or $1$ unit of flow on each edge
- Such a flow is called $0/1$ flow
- $|f_H| = \text{number of edge disjoint paths in G}$

Proof: Unclear

Algorithm:
- Start walking from $s$ along an edge with flow $1$
- If reach $t$, then add the path to the set of edge disjoint paths
- Else if reached a vertex a second time (a cycle!), then remove the edges that form the cycle
- Since $|f| \leq |V|$, Ford-Fulkerson outputs the flow in $O(|V||E|)$ time
- Extracting the paths from the flow takes $O(|E|)$ time
- Hence edge disjoint paths can be found in $O(|V||E|)$ time

Lemma: Maximum number of edge disjoint paths equals the minimum number of edges whose removal separates s from t
Proof:
$U \leftarrow$  set of edge disjoint paths
$F \leftarrow$ set of removed edges such that $s$ and $t$ are disconnected
First show $|U| \leq |F|$
- $F$ must contain at least one edge from each path in $U$
- Hence $|U| \leq |F|$

Now,
- $S = \{v \in V | \exists \text{ path from } s \text{ to } t \text{ which does not use any edge in } F \}$
- $T = V \setminus S$
- $F$ defines a cut $(S,T)$
- Clearly $|F| \geq c(S,T)$
- Any edge in $F$ that is not in the cut can be discarded to get $F_{minimal}$
- $|F_{minimal}| = c(S,T)$
- The smallest such set has size, $|F^*| = $ min-cut in $G$
- By Max-Flow Min-Cut theorem $|F^*| = |f_{max}|$, i.e max-flow in $G$
- By previous lemma $|F^*| = $ number of edge disjoint paths

Undirected Graph

- Double every edge to give 2 directed edges

- Repeat the algorithm for directed case

- Again $f$ might push flow along both $(u\rightarrow v)$ and $(v\rightarrow u)$ 

- But this is a cycle!

- Remove cycle and get on with life

Texture Mapping

Set of mappings from Model Coordinates (Object Space) to Texel Values 

- Object space $(x,y,z) \rightarrow $ Parameter space $(u,v)$

- Parameter space $(u,v) \rightarrow $ Texture Image space

- Texture Image space $ \rightarrow $ Texel Values

- Transformation of Texel Values /*optional*/

Resolving mismatch between number of pixels required for rasterizing geometry and the number of texels it maps to

Issues:

- Magnification Aliasing:

  - Source of Jaggies

  - Occurs when texture image is smaller than the rasterization

  - Multiple screen pixels map to the same texture image coordinates

  - Solution: Bilinear Interpolation is required to pick the value from the inverse mapping from screen pixel coordinates onto the texture image coordinates

- Minification Aliasing:

  - Occurs when texture image is larger than rasterization

  - Multiple texture image coordinates map to the same screen pixel

  - It is inefficient to compute the average of all these texels

  - Solution: MIP mapping

MIP (multum im parvo) Mapping:

- Generate a precomputed image pyramid where each lower resolution image is half the dimension of its predecessor

- While doing texture mapping, choose the texture image resolution whose projected texel size closely matches the pixel size

Choosing MIP map level:

$(x,y)$ be the screen pixel coordinates and $(u,v)$ be the texel coordinates. Compute the change in the $u,\; v$ along $x,\; y)$. Choose the resolution for which the $\text{max}(\frac{\partial u}{\partial x},\frac{\partial u}{\partial y},\frac{\partial v}{\partial x},\frac{\partial v}{\partial y})$ is closest to $1$.

Bump Mapping
- Store the height field in a texture
- Perturb the geometric normal by the slopes in the height field along the directions of the tangent and bi-tangent
- Use this normal for lighting computation
Alternatively: Store the normals themselves

Environment Mapping
- An environment map stores the view in every direction from a single point
- It assumes that the objects environment is infinitely distant from the object
- While rendering a point on the object
    - Compute the reflection direction
    - Look up the color stored in that direction in the environment map
    - Use this color to render the point

Sphere Map
A sphere map is a technique that allows us to store the precomputed view in every direction  from a point. It is basically, a photograph of a reflective sphere placed in the environment.
Issues: Distortion towards the edge of the sphere
Solution: Use Cube mapping instead of Sphere

Other uses of texture mapping
- Can implement shading as texture mapping
- Can implement Seeliger lighting model for more realistic skin color rendering

Network Flow

A flow network comprises of :

- A directed graph $G(V,E)$

- Non-negative capacities on each edge $c(u,v)$

- A source $s$

- A sink $t$

Definition: Flow

Flow is a function $f:E\rightarrow \mathbb{R}$ such that the following properties hold

- Bounded by Capacity: $f(u,v) < c(u,v)$

- Anti-Symmetry: f(u,v) = -f(v,u)

- Conservation of flow: For any node $u$ that is neither source nor sink, $\sum_{v\in V} f(u,v) = 0$

- Special vertices $s$ and $t$ such that all flow starts from $s$ and ends at $t$ 

Definition: Value of Flow

$\text{Value of flow} = |f| = \sum_v f(s,v)$

Definition: Residual Capacity

Given the capacity $c$ and flow $f$, the residual capacity of an edge $u \rightarrow v$ is 

\begin{align}
c_f(u,v) = c(u,v) - f(u,v)
\end{align}

Note - Even if there is no directed edge $u \rightarrow v$ in the graph, i.e $c(u,v) = 0$ it might still have a non-zero residual capacity.

Definition: Residual Graph

For a flow $f$ in a graph $G(V,E)$ the residual graph $G_f(V,E_f)$ is the graph with all edges with positive residual capacity, i.e

\[
E_f = \{(u,v)\in \left(V \times V\right)| c_f(u,v)>0\}
\]

Note - Because of the note above $|E_f|<2|E|$ because each edge in $G$ can induce at most 2 edges in $G_f$.

Lemma: 
The flow generated by adding the flows in the graphs $G(V,E)$ and $G_f(V,E_f)$ is also a valid flow in $G$ with a higher flow value
\[

|f+h| = |f| + |h|

\]

Note - $(f+h)(u,v)$ is defined as $f(u,v) + h(u,v)$.

Definition: Augmenting Path
For graph $G$ and a flow $f$, any directed path, $\pi$ from $s$ to $t$ in $G_f$ is called an augmenting path. The maximum flow that can be pushed through $\pi$ is denoted by $c_f(\pi)$ where
\[
c_f(\pi) = \max_{(u\rightarrow v)\in \pi} c_f(u,v)
\]
Note - $c_f(\pi)$ is always positive by definition of Residual Graph.

Lemma: Improving the flow in $f$ using an Augmenting Path
Let $f$ be a flow in $G$ and $f_{\pi}$ be a flow on an augmenting path, $\pi$, in $G_f$. The $f+f_{\pi}$ is a better flow in $G$ since $|f+f_{\pi}| = |f| + |f_{\pi}| > |f|$.

Problem: Max Flow
Given a network flow, find the maximum flow, i.e, maximum possible value of $|f|$.

Algorithm: Ford Fulkerson Method
1. Initialize $f(u,v) = 0 \; \forall \; (u,v) \in E$
2. Compute residual graph $G_f$
3. Find an augmenting path, $\pi$, in $G_f$
4. Update flow in $G$ by $f \leftarrow f + f_{\pi}$
5. Repeat 2-5 until there are no augmenting paths left in $G_f$

Definition: Directed Cut
A directed cut $(S,T)$ in a flow network is a partitioning of $V$ into disjoint sets $S$ and $T = V\setminus S$ such that $s\in S$ and $t\in T$. Standard terminology -
- Net flow of $f$ across a cut $(S,T)$, is $f(S,T) = \sum_{u\in S, v\in T}f(u,v)$
- Capacity of cut $(S,T)$ is $c(S,T) = \sum_{u\in S, v\in T}c(u,v)$
- Minimum cut is the cut with the minimum capacity (*\ important \*)

Lemma: Value of flow in network is the flow across any cut
$f(S,T) = |f| \; \forall \; \text{cuts} \; (S,T)$
(*\Proof is a one liner but worth looking at\*)

Lemma: Flow is bounded above by capacity of any cut $(S,T)$ in G
$|f| \leq c(S,T) \; \forall \; \text{cuts} \; (S,T)$

Theorem: Max-flow Min-cut 
If $f$ is flow in a flow network $G(V,E)$ with source $s$ and sink $t$, then the following statements are equivalent
A. $f$ is the Max-flow
B. $\nexists$ augmenting path in $G_f$
C. $\exists \; \text{cut} \; (S,T) \ni |f| = c(S,T)$ and $(S,T)$ is a Min-cut

Proof:
$(A \implies B)$
If augmenting path $\pi$ did exist in $G_f$ then we could have further improved the flow in $G$ by the amount $|f_{\pi}| = c_f(\pi)$. Hence a contradiction

$(B \implies C)$
Define $S = \{v | v \in V \; and \; \exists \; \text{a path from s to v in} G_f\}$. Let $T = V \setminus S$. Then,
\[
|f| = f(S,T) = \sum_{x\in S, y\in T}f(x,y) = \sum_{x\in S, y\in T}c(x,y) = c(S,T)
\]
Note - If $f(x,y) \neq c(x,y)$, then $c_f(x,y) > 0 \implies (x \rightarrow y)$ is an edge in $G_f$. This would further have implied that $y \in S$ which contradicts the construction of S.

Also, $(S,T)$ has to be a Min-cut because if it were not then it would have implied that $\exists \; cut (S', T') \ni c(S',T') < c(S,T) = |f|$. But we know that $|f| \leq c(S,T) \; \forall (S',T')$. Hence a contradiction.

$(C \implies A)$
Since $|f|$ is bounded above by the capacity of any cut and we have $|f| = c(S,T)$ for some cut, implies that $|f|$ is the max-flow.

Hence proved.

Conclusion
By Max-cut Min-Flow theorem, it follows that if Ford-Fulkerson terminates then it would be a max-flow. But does Ford-Fulkerson terminates?

Claim: Ford-Fulkerson terminates for integral edge capacities
- Ford Fulkerson only performs additions, subtractions and min operations.
- So if it finds an augmenting path, $\pi$, then $c_f(\pi)$ is a positive integer, i.e, $c_f(\pi) \geq 1$.
- In every iteration we would be improving the flow by at least 1.
- If the value of max-flow is $|f^*|$ then in at most $|f^*|$ steps the algorithm will terminal
- In every iteration calculating the augmenting path takes $O(|E|)$ time (BFS or DFS).
- Hence, the algorithm run in $O(|f^*| |E|) $

Integrality Theorem
If all capacities are integral, then the flow $|f|$ generated by Ford-Fulkerson is integral since max-flow equals min-cut which is integral. Also the flow $f(u,v)$ on every edge is integral.

Algorithm: Edmonds - Karp
It is an efficient implementation of Ford-Fulkerson using BFS to find the shortest augmenting path in each iteration. It is meant to deal with the situation where $|f^*|$ is very large.

Definition: 
For a flow $f$, $\delta_f(v)$ is the length of the shortest path from $s$ to $v$ given that each path is of unit length.

Lemma: $\delta_f(v)$ increases monotonically with every flow augmentation

Lemma: Bound on the number of disappearances of an edge in residual graph
The number of times an edge can disappear (and reappear) in the residual graph is at most $|V|/2$.

Proof:
- Let $f$ be the flow in the iteration when edge $(u\rightarrow v)$ disappears from $G_f$
- $(u\rightarrow v)$ must have been in the augmenting path $\pi_f$
- $\delta_f(v) = \delta_f(u) + 1$
- Let $g$ be the flow in the iteration when edge $(u\rightarrow v)$ reappears in in $G_g$
- $(v\rightarrow u)$ must have been in the augmenting path $\pi_g$
- $\delta_g(u) = \delta_g(v) + 1$
- By monotonicity of $\delta$, $\delta_g(u) \geq \delta_f(u) + 2$
- But $\delta_g \leq |V|$
- This can happen at most $|V|/2$ times
Hence proved

Time Complexity of Edmonds - Karp
- In every iteration, at least one edge (namely the one which realizes the residual capacity of the augmenting path in the residual graph) will disappear.
- Total number of disappearances is $\frac{|V||E|}{2}$
- In each iteration finding the shortest path takes $O(|E|)$ time
- Algorithm runs in $O(\frac{|V||E|^2}{2})$ time

Applications of Max-Flow
- Maximum Bipartite Matching can be solved in $O(|V||E|)$ time
- There is a simple extension for multiple sources and sinks by simply connecting them with a Super source and sink with edges of infinite capacity