Basis

• A basis in R^k is given by a set of vectors defining the directions of the space (v₁, v₂, ... v_k) such that any vector w in R^k can be written as w = a₁v₁ + a₂v₂ + ... + a_kv_k
• The coefficients (a₁, a₂, ... a_k) are called the coordinates of w.
• If the basis vectors are orthogonal to each other then the basis is called orthogonal. If the basis vectors are unit vectors (have a length of 1) then the basis is called normal. If it is both then it's called orthonormal.

Frame

• A frame or coordinate system in R^k is composed of a basis plus a position in space O (origin).
• Both a point and a vector are represented as a tuple (a₁, a₂, ... a_k), but a point P is seen as
• P = O + a₁v₁ +a₂v₂ + ... + a_kv_k
• The coordinates of O are (0, 0, 0).
• In 2D we have 2 basis vectors, usually denoted by x=(1,0) and y=(0,1).
• In 3D we have 3 vectors, denoted by x=(1,0,0), y=(0,1,0), and z=(0,0,1), or sometimes by i, j, k.

Change of Coordinate Systems

• Let (O₀, V=(v₁, v₂, ..., v_k)) and (O₁, U=(u₁, u₂, ..., u_k)) be two coordinate systems, such that U=AV, where A is a matrix of kxk.
• Then a vector w=(a₁, a₂, ..., a_k) in the first system will have the coordinates A^-1w in the second system.
• A point P=O₀+w will have the coordinates P₁=A^-1 (P-O₁) in the second system.

Projection

• A change of coordinates from a system of coordinates in R^k to a system of coordinates in R^m, where m < k.
• For example, representing a 3D object from the real space in a 2D image space requires a projection.
• Usually a projection is also defined by a matrix.

Point scanning: (x,y) -> (round(x), round(y)),

round(w) = int(w + 0.5), closest integer to the real number

Continuous image	Discrete image

Line scanning

General equation:  y = mx + b, m is the slope of the line.
Horizontal lines:    y=b    (m = 0)
Vertical lines:        x = c    (m = oo)
Diagonal:

x = y + b    (m = 1)
x = y + b    (m = -1)

m = (y2 - y1) / (x2 - x1)
b = y1 - m x1

• y = mx + b
• Lines passing through O have b=0.
• Lines bellow 45^o have m<1. Lines above 45o have m>1.
• Parallel lines have the same slope.
• y=mx+b and y=nx+c are orthogonal if mn=-1.
• For any point (x₁, y₁), if m x₁ + b > y₁ then the point is bellow the line. If m x₁ + b < y₁, the point is above the line.

Direct Conversion Pick the coordinate with the longest projection of the segment

if m < 1 : horizontal
if m > 1 : vertical

compute m = (y2 - y1) / (x2 - x1)
for each x, x1 <= x <= x2
compute y = round (m x + b)
draw pixel (x,y)

Bresenham's algorithm

For the case x1 < x2, 0 < m < 1.

x = x1; y = y1;
dx = x2 - x1; dy = y2 - y1;
dT = 2 (dy - dx); dS = 2dy;
d = 2dy - dx;
setPixel(x, y);
while (x<x2) {
  x++;
  if (d < 0)
    d = d + dS;
  else {
    y++;
    d = d + dT;
  }
  setPixel(x, y);
}

Region: an area enclosed by a boundary in which all of the pixels are connected.
Connectivity modes: 4-connected or 8-connected.

An algorithm for a 4-connected area.

FloodFill (x0, y0, fill_color, original_color)
{
  int color, x, y;
  x = x0; y = y0;
  getPixel(x, y, color);
  if (color == original_color) {
    while (color == original_color) {
      setPixel(x, y, fill_color);
      FloodFill(x, y+1, fill_color, original_color);
      FloodFill(x, y-1, fill_color, original_color);
      x = x - 1;
      getPixel(x, y, color);
    }
    x = x0 + 1; y = y0;
    getPixel(x, y, color);
    while (color == original_color) {
      setPixel(x, y, fill_color);
      FloodFill(x, y+1, fill_color, original_color);
      FloodFill(x, y-1, fill_color, original_color);
      x = x + 1;
      getPixel(x, y, color);
    }
  }
}

Original color c0      New color    c1      0.67*c0+0.33*c1      0.67*c1+0.33*c0

Flood-fill with anti-aliasing:

replace the check for

color == original_color

with

abs(color - original_color) < 0.33

do not use anti-aliasing for setPixel while flood-filling a region.