GNU General Public License v3.0 licensed. Source available on github.com/zifeo/EPFL.
Spring 2016: Introduction to Computer Graphics
[TOC]
- computer graphics
- rendering : generate an image from a digital representation of a 3D scene, realtime rendering (OpenGL)
- modeling : build digital representation of 3D scene, procedural methods
- animation : how to bring a 3D scene to life
- raster image : 2D array of pixels (picture elements), color/bit #bits/pixel
- fundamental components
- geometry primitives : points and line segments, triangles
- transformations : object, world, eye coordinates
- projection and viewing : perspective, orthographic
- rasterization : pixelisation
- visibility : z-buffer
- shading : vertex, fragment, geometry, tessellation shaders
- vertex : individual vertices, transformations, lighting
- fragment : individual fragments (pixel), lighting, specular highlights, translucency, bump mapping, shadows
- geometry : whole primitives, points sprites, cube mapping
- tessellation : subdivide vertex data into smaller primitives, level of detail
- OpenGL
- pipeline
- geometry primitives
- pipeline
- GLSL : shader programming
- graphics pipeline
- 2D canvas
- implicit functions
- on curve :
$F(x,y)=0$ - inside curve :
$F(x,y)<0$ - outside curve :
$F(x,y)>0$ - circle :
$F(x,y)=(x-c_x)^2+(y-c_y)^2-r^2$
- on curve :
- simple rasterization
for all pixels (i,j)
(x,y) = map_to_canvas (i,j)
if F(x,y) < 0
set_pixel (i,j,color)-
barycentric coordinates :
$P=\alpha A+\beta B+\gamma C$ with$\alpha+\beta+\gamma=1$ - linear function :
$\alpha(P),\beta(P),\gamma(P)$ - unique : for non-collinear ABC
- matrix form : $\begin{bmatrix}A_x & B_x & C_x \\ A_y & B_y & C_y \\ 1 & 1 & 1\end{bmatrix}\begin{bmatrix}\alpha\\ \beta\\ \gamma\end{bmatrix}=\begin{bmatrix}P_x\\ P_y\\ 1\end{bmatrix}$
- ratio of triangle areas
- linear function :
-
barycentric rasterization
- triangle :
$(x_0,y_0)$ ,$(x_1,y_1)$ ,$(x_2,y_2)$ points with$\alpha,\beta,\gamma >0$ 
- incremental algorithm : scan line, optimized hardware
- interpolation :
$n(P)=\alpha n(A)+\beta n(B)+\gamma n(C)$
- triangle :
for all y do
for all x do
compute (α,β,γ) for (x,y)
if α ∈ [0,1] and β ∈ [0,1] and γ ∈ [0,1]
set_pixel (x,y)- linear maps
- general : $\begin{pmatrix}x' \\ y'\end{pmatrix}=\begin{pmatrix}a & b\\ c & d\end{pmatrix}\begin{pmatrix}x\\ y\end{pmatrix}$
- combination :
$L_2L_1x$ - scaling : $\begin{pmatrix}x' \\ y'\end{pmatrix}=\begin{pmatrix}s_x & 0\\ 0 & s_y\end{pmatrix}\begin{pmatrix}x\\ y\end{pmatrix}$
- rotation :
$R(\alpha)$ , $\begin{pmatrix}x' \\ y'\end{pmatrix}=\begin{pmatrix}\cos\alpha & -\sin\alpha\\ \sin\alpha & \cos\alpha\end{pmatrix}\begin{pmatrix}x\\ y\end{pmatrix}$ - x-axis shear :
$H_x(a)$ , $\begin{pmatrix}x' \\ y'\end{pmatrix}=\begin{pmatrix}1 & a\\ 0 & 1\end{pmatrix}\begin{pmatrix}x\\ y\end{pmatrix}$ - y-axis shear :
$H_y(b)$ , $\begin{pmatrix}x' \\ y'\end{pmatrix}=\begin{pmatrix}1 & 0\\ b & 1\end{pmatrix}\begin{pmatrix}x\\ y\end{pmatrix}$
- affine maps
- general : $\begin{pmatrix}x' \\ y'\end{pmatrix}=\begin{pmatrix}a & b\\ c & d\end{pmatrix}\begin{pmatrix}x\\ y\end{pmatrix}+\begin{pmatrix}t_x\\ t_y\end{pmatrix}$
- combination :
$Lx+t$
- homogenous coordinates : matrix representation of affine transformations,
$w$ -coordinate- 2D point :
$(x,y,1)^T$ - 2D vector :
$(x,y,0)^T$ - general : $\begin{pmatrix}x'\\ y'\\ 1\end{pmatrix}=\begin{pmatrix}a & b & t_x\\ c & d & t_y\\ 0 & 0 & 1\end{pmatrix}\begin{pmatrix}x\\ y\\ 1\end{pmatrix}$
- combination : important for performance, $A_n\cdots A_1\begin{pmatrix}x\\ y\\ 1\end{pmatrix}$
- scale : $S(s_x,s_y)=\begin{pmatrix}s_x & 0 & 0\\ 0 & s_y & 0\\ 0 & 0 & 1\end{pmatrix}$
- rotation : $R(\alpha)=\begin{pmatrix}\cos\alpha & -\sin\alpha & 0\\ \sin\alpha & \cos\alpha & 0\\ 0 & 0 & 1\end{pmatrix}$
- translation : $T(t_x,t_y)=\begin{pmatrix}1 & 0 & t_x\\ 0 & 1 & t_y\\ 0 & 0 & 1\end{pmatrix}$
- valid operation : if
$w$ -coord result$1$ or$0$ - vector + vector : vector
- point - point : vector
- point + vector : point
- point + point : ???
- geometric interpretation : 2 hyperplanes in
$\mathbb{R}^3$ 
- linear combinations of points
- affine :
$\sum_i\alpha_ix_i$ with$\sum_i\alpha_i=1$ - convex :
$\sum_i\alpha_ix_i$ with$\sum_i\alpha_i=1$ and$\alpha_i\ge 0$ 
- affine :
- rotate around given point :
$T(c)R(\alpha)T(-c)$
- 2D point :
- object or camera transform
- extended coordinates
- 3D point :
$(x,y,z,1)^T$ - 3D vector :
$(x,y,z,0)^T$ - affine transformations : $\begin{pmatrix}x'\\ y'\\ z'\\ 1\end{pmatrix}=\begin{pmatrix}a & b & c & t_x\\ d & e & f & t_y\\ g & h & i & t_z\\ 0 & 0 & 0 & 1\end{pmatrix}\begin{pmatrix}x\\ y\\ z\\ 1\end{pmatrix}$
- scale : $S(s_x,s_y,s_z)=\begin{pmatrix}s_x & 0 & 0 & 0\\ 0 & s_y & 0 & 0\\ 0 & 0 & s_z & 0\\ 0 & 0 & 0 & 1\end{pmatrix}$
- translation : $T(t_x,t_y,t_z)=\begin{pmatrix}1 & 0 & 0 & t_x\\ 0 & 1 & 0 & t_y\\ 0 & 0 & 1 & t_z\\ 0 & 0 & 0 & 1\end{pmatrix}$
-
$x$ -rotation : $R_x(\alpha)=\begin{pmatrix}1 & 0 & 0 & 0\\ 0 & \cos\alpha & -\sin\alpha & 0\\ 0 & \sin\alpha & \cos\alpha & 0\\ 0 & 0 & 0 & 1\end{pmatrix}$ -
$y$ -rotation : $R_y(\alpha)=\begin{pmatrix}\cos\alpha & 0 & \sin\alpha & 0\\ 0 & 1 & 0 & 0\\ -\sin\alpha & 0 & \cos\alpha & 0\\ 0 & 0 & 0 & 1\end{pmatrix}$ -
$z$ -rotation : $R_z(\alpha)=\begin{pmatrix}\cos\alpha & -\sin\alpha & 0 & 0\\ \sin\alpha & \cos\alpha & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\end{pmatrix}$ - rotation :
$R(\alpha,\beta,\gamma)=R_x(\alpha)R_y(\beta)R_z(\gamma)$ , euler angles (roll, pitch, yaw) - gimbal lock : when one rotation "ring" aligned with another, lose a dimension
- rotation by angle
$\alpha$ around axis$n$ : $R(n,\alpha)=\cos(\alpha)I+(1-\cos(\alpha))nn^T+\sin(\alpha)\begin{pmatrix}0 & n_z & -n_y\\ -n_y & 0 & n_x\\ n_y & -n_x & 0\end{pmatrix}$ - quaternions : extension of complex number, encode orientation, good for interpolation, avoids gimbal lock
- 3D point :
- vertex shader stage
- object/model coordinates
- word coordinates
- eye coordinates
- clip coordinates
- window/screen coordinates : normalized device coordinates
- look-at transformation : eye point
$e$ , up vector$u$ , look-at point$p$ - view direction :
$v=\frac{p-e}{\norm{p-e}}$ - right vector
$r=v\times u$ if$u,v$ orthonormal - camera :
$(e,r,u,v)$ - standard camera : located at origin, looking down negative
$z$ axis, up vector$e_2$ - matrix : $\begin{pmatrix}r_x & u_x & -v_x & e_x\\ r_y & u_y & -v_y & e_y\\ r_z & u_z & -v_z & e_z\\ 0 & 0 & 0 & 1\end{pmatrix}$
- inverse matrix : $\begin{pmatrix}r_x & u_x & -v_x & e_x\\ r_y & u_y & -v_y & e_y\\ r_z & u_z & -v_z & e_z\\ 0 & 0 & 0 & 1\end{pmatrix}^{-1}=\begin{pmatrix}r_x & r_y & r_z & 0\\ u_x & u_y & u_y & 0\\ -v_x & -v_y & -v_z & 0\\ 0 & 0 & 0 & 1\end{pmatrix}\begin{pmatrix}1 & 0 & 0 & -e_x\\ 0 & 1 & 0 & -e_y\\ 0 & 0 & 1 & -e_z\\ 0 & 0 & 0 & 1\end{pmatrix}$
- view direction :
- projection
- in mathematic : idempotent mapping
$P(x)=P(P(x))$ - in computer graphics : 3D spaces to planar 2D images, not invertible, depth information lost
- in mathematic : idempotent mapping
- planar geometric projections
- parallel : one direction of projection for all points, preserve parallelism, technical application
- orthographic : direction of projection perpendicular to image plan
- perspective : vanishing point, each point projected towards center of projection, perspective foreshortening, realistic appearance, graphics application
- standard projection
- center of projection :
$(0,0,0)^T$ - image plane :
$z=d$ 
- image plane :
- homogenous coordinates : $q=M\begin{pmatrix}x\\ y\\ z\\ 1\end{pmatrix}=\begin{pmatrix}x\\ y\\ z\\ z/d\end{pmatrix}\iff\begin{pmatrix}xd/z\\ yd/z\\ d\\ 1\end{pmatrix}$ with $p=\begin{pmatrix}wx\\ wy\\ wz\\ w\end{pmatrix}\iff\begin{pmatrix}x \\ y\\ y\\ z\\ 1\end{pmatrix}$ and $M=\begin{pmatrix}1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 1/d & 0\end{pmatrix}$
- center of projection :
- perpective fovy, aspect, near, far
$top=near*tan(fovy)$ $bottom=-top$ $right=top*aspect$ $left=-right$ - $M=\begin{pmatrix}\frac{2n}{r-l} & 0 & \frac{r+l}{r-l} & 0\\ 0 & \frac{2n}{t-b} & \frac{t+b}{t-b} & 0\\ 0 & 0 & -\frac{f+n}{f-n} & -\frac{2fn}{f-n} \\ 0 & 0 & -1 & 0 \end{pmatrix}$
- standard projection
- painter algorithm
- sort : all polygons w.r.t.
$z_{max}$ (farthest vertex) - disambiguate : if
$z_{max}(A)>z_{max}(B)>z_{min}(A)$ -
$[x,y]$ -ranges not overlapping : A - A behind supporting plane of B : A
- B in front supporting plane of A : A
- non-overlapping projections : A
- B behind supporting plane of A : swap A & B
- A in front supporting plane of B : swap A & B
- repeated swap : cyclic overlap, split A at supporting plane of B
-
- paint polygons from back to front
- complexity :
$O(n\log n)$ for$n$ polygons
- sort : all polygons w.r.t.
- framebuffer : store RGB color values
- z-buffer : store current min
$z$ -value for each pixel, 16-32 bits per pixel- per pixel z-value : interpolate with barycntric coordinates, GPU, incremental computation during rasterization, simple linear interpolation along scanlines
- complexity :
$O(n)$ for$n$ polygons, GPU hardware (sort)
// initialize depth buffer to infinity
for (each polygon P) {
// scan conversion of polygon
for (each pixel (x,y,z) in P) {
if (z < zbuffer[x,y]) {
framebuffer[x,y] = rgb;
zbuffer[x,y] = z;
}
}
}- quantization : higher resolution at near plane
- z-fighting
- image space : multiple objects mapped into same pixel => z-buffer
- object space : which part of object visible in given screne given viewpoint => painter algorithm, culling
- culling : quickly reject objects (or parts) not visible from viewpoint, then solve complicated visibility for remaining
- view frustumm culling : discard objects outside viewing frustum using bounding volumes or hierarchies against 6 clipping planes
- backface culling : closed solid objects have front-facing triangles blocking black-facing ones, discards about half of them,
$face_normal\cdot view_vector>0$ , negative triangle area
- view frustumm culling : discard objects outside viewing frustum using bounding volumes or hierarchies against 6 clipping planes
- physics approach : model global interaction of light in screen through photorealistic rendering, costly
- rendering equation :
$L(x,\omega)=L_e(x,\omega)+\int_{H^2}f_r(x,\omega'\to\omega)L(x^*(x,\omega'),-\omega')\cos\theta'd\omega'$ 
- rendering equation :
- light sources
- illumination function :
$I(x,y,z,\theta,\phi,\gamma)$ 
- total contribution at point : integrating over light source, complex
- ambient light : constant intensity everywhere, uniformly brighten/darken a scene
- point light : emits light equally in all directions, intensity drops with square distance, hard shadow
- spot light : point light with limited angle, attenuation
$\cosê\theta$ 
- directional light : commonly used for far away light sources (e.g. sun), faster to evaluate than point lights (no light vector to be recomputed)
- area light
- illumination function :
- local illumination : combines ambient, diffuse, specular reflection
- ambient light : coming from all directions, camera independant and surface orientation, reflected intensity,
$I_a=k_aL_a$ - light source :
$L_a$ - material parameter :
$k_as$
- light source :
- diffuse reflection :
$I_d=k_d(l\cdot n)L_d$ 
- specular reflection :
$I_s=k_sL_s\cos^\alpha\phi=k_sL_s(r\cdot v)^\alpha$ 
- illumination :
$I=k_aL_a+k_d(n\cdot l)L_d+k_s(r\cdot v)^\alpha L_s$ - phong reflection :
- piece-wise flat surface : per-vertex vs per-face normals
- ambient light : coming from all directions, camera independant and surface orientation, reflected intensity,
- shading
- flat : viewer far away (constant view vector), light far away (constant light vector), mach band effect
- gouraud : per vertex, interpolate color across triangle
- phong : interpolate normals normalized, apply reflection model per fragment
- vertex normal : computing weighted averaging of incident triangle normals
- normal transformation : do not forget to re-normalize
- plane with normal :
$n$ - before affine transformation :
$(n_x,n_y,n_z,d)\cdot(x,y,z,1)^T=0$ - after affine transformation :
$(n_x',n_y',n_z',d')\cdot M \cdot(x,y,z,1)^T=0\Rightarrow (n_x',n_y',n_z',d')^T=(M^T)^{-1}\cdot(n_x,n_y,n_z,d)^T$ 
- plane with normal :
- texture mapping : add details without raising geometric complexity
- surface properties
- reflectance : diffuse and specular coefficients
- normal vector : normal mapping, bump mapping
- geometry : displacement mapping
- opacity
- illumination : environment mapping
- one triangle texture : assign
$(u,v)$ texture coordinate to each vertex and interpolate
- linear interpolation in world coordinates : nonlinear interpolation in screen coordinates
- perspective interpolation : GPU
- linear interpolation in world coordinates : nonlinear interpolation in screen coordinates
- texture filtering :
$(u,v)$ real pixel coordinates- round to nearest integer
- bilinear interpolation in containing texel
- texture aliasing
- point sampling : depends on parameterization, texture minifaction leads to aliasing
- anti-aliasing : integrate over image pixel area in texture space, approximated by ellispe (EWA filtering)
- approximated by mip-mapping : store texture at multiple levels-of-detail, use smaller versions when far from camera
- point sampling : depends on parameterization, texture minifaction leads to aliasing
- triangle mesh texturing :
- texture coordinates parameterization : for each vertex from 2D texture domain to 3D object space
- mapping from simple intermediate object to 3D mesh
- spherical, cylindrical, planar maps
- cube maps
- spherical parameterization
- properties : low distortion, bijective mapping, contrained map, finding cuts, texture atlases
- texture coordinates parameterization : for each vertex from 2D texture domain to 3D object space
- OpenGL : per-vertex tecture coordinates interpolated by rasterizer, texture lookup done per fragment
- special texture maps
- light maps : precomputed lighting (from offline global illumination algorithm), often used for low-intensity
- alpha maps : cut out geometrically complex shapes by removing transparent pixels
- bump/displacement maps : adding surface detail whitout adding geometry (normals perturbation), bumps small compared to geometry
- procedural texturing : can vary in all 3 dimensions (e.g. sinusoidal color)
- procedural technics : algorithms, functions that generate computer graphics objects, abstraction, compact representation, infinite detai, parametric control, flexibility
- noise functions :
$\mathbb{R^n}\to[-1,1]$ , no obvious repetition, rotation invariant, band-limited, not scale-invariant, efficient to compute, reproductible - value noise
- perlin noise : random gradient hermite-interpolated values
- 2D perlin
- parameters : amplitude, frequency
- 2D perlin
- other noise : simplex noise (triangles/tetrahedrons), sparse gabor convolution
- spectral analysis : representing complex function
$f_s(x)$ by a sum of weighted contributions from a scaled function$f(x)$ ,$f_s(x)=\sum_i w_if(s_ix)$ (e.g. Fourier) - fractional brownian motion : spectral synthesis of noise function, progressively smaller frequency/amplitude, each term in summation called octave
- FBm :
$f_s(x)=\sum_i l^{-iH}f(l^ix)$ - fractal increment :
$H$ ($1$ smooth,$0$ more like white noise) - homogenous : same everywhere
- isotropic : same in all direction
- dimension :
$~2.1$
- FBm :
double fBm(vector point, double H, double lacunarity, int octaves) {
double value = 0.0;
/* inner loop of fractal construction */
for (int i = O; i < octaves; i++) {
value += Noise(point) * pow(lacunarity, -H*i);
point *= lacunarity;
}
return value;
}- turbulence : same as FBm, but sum absolute value of noise function
- marble :
$color = sin(x + turbulence(x,y,z))$ - wood :
$color = sin(\sqrt{x^2+y^2} + FBm(x,y,z))$
- marble :
- multifractal
- different fractal dimensions in different regions
- scale higher frequencies in summation by value of previous frequency
- heterogenous terrain
- hybrid multifractal
- ridged multifractal
- multiplicative-cascade multifractal variation of FBm
double multifractal(vector point, double H, double lacunarity, int octaves, double offset) {
double value = 1.0;
for (int i = O; i < octaves; i++) {
value *= (Noise(point) + offset) * pow(lacunarity, -H*i);
point *= lacunarity;
}
return value;
}- erosion : wind, rain, rivers, complex but plausible results using simple ad hoc rules
- logarithm spiral :
$x(t)=ae^{bt}\cos t$ ,$y(t)=ae^{bt}\sin t$ - fractals : repeition of given form over range of scales, self-similar, detail at multiple levels of magnification, fractal dimension exceeds topological dimension
- richardson effect : how long is coast => infinite
- integer euclidean dimension
- take an object residing in Euclidean dimension
$D$ - reduce its linear size by
$1/r$ in each spatial direction - it takes
$N=r^D$ self-similar objects to cover original objects
- take an object residing in Euclidean dimension
- Hausdorff fractal dimension :
$D=\frac{\log N}{\log r}$ 
- Cantor dust
- Cantor dust
- fractal dimension
- integer component : indicates underlying Euclidean dimensions
- fractional part :fractal increment
- integer component : indicates underlying Euclidean dimensions
- Lindenmayer-systems : text substitution,
$G=(V,\omega,P)$ - character set :
$V$ , alphabet - axiom :
$\omega$ , non-empty starting word - productions rules :
$P$ - graphical interpretation : turtle command
- branching : special characters to store and restore state
- stochastic : add probability
- parametric : lenght parameterized
- conditional : add conditions
- 3D turtle state : position, rotation (pitch, yaw, roll), line length, difference angles
- character set :
- CGA : shape grammar language for procedural architecture
- rule-driven modification and replacements of shapes
- iteratively evolve design with more details
- mass model
- encoding architecture : design idea, classify its parts, define main parameters, encode design rules, add boundary conditions
- parcel : general patterns and Zoning laws, max distances, footprint layout
- facade subdivision : shape interaction need spatial overlap to align elements
- roofs : hipped, flat
- level of detail : texture vs geometry, multi-resolution
- depth perception
- intuition about scene lighting
- visibility : which objects can be seen from viewpoint
- shadows : which objects can be seen from light source
- shadow computation
- dynamic shadows : multiple render passes
- shadow volumes : polygonal representation of shadowed regions
- serval overlapping shadow : entering intersection increment counter, leaving it decrement, can be done with stencil buffer
- shadow maps : apply visibility techniques for shadows, render scene as seen from light source and project, light z-buffer called shadow map for each light source
- shadow acne : intensity/depth bias
- percentage closer filtering : sample in pixel vicinity, sample position around
$P$ with poisson disk sampling - resolution : squared shadowed if low resolution, light frustum must contain all objects that could cast shadows into camera frustum
- cascaded : combination, higher resolution closer to camera, state of the art use 4 cascades
- shadow volumes : polygonal representation of shadowed regions
- environment maps : approximate method to render reflective objects assuming incoming light only depends on direction, no self-reflection
- basic algorithm : for each pixel, compute normal vector at surface point, reflected view vector at surface point, index into environment map
- sphere maps :
$(u,v)$ texture coordinates
- cube maps : simplify synthetic generation, 6 faces
- basic algorithm : for each pixel, compute normal vector at surface point, reflected view vector at surface point, index into environment map
- light transport : straight lines, rays do not interfere with each other if crossing, travel from light sources to eye
- raytracing
- geometrical optics : no diffraction, no polarization, no interference
- discrete wavelength : approximation of color, quanized dispersion and fluorescence
- superposition : no non-linear reflecting materials
- forward
- backward
- ray casting : generate an image by sending one ray per pixel, check for shadows by sending ray towards the light
- pipeline
rayTraceImage() {
parse scene description
for each pixel
generate primary ray
pixel color = trace(primary ray)
}
trace(ray) {
hit = find first intersection with scene objects
color = lighting(hit) // might trace more rays (recursive)
return color
}- rays : parametric form
$r(t)=o+td$ with$o$ origin and$d$ direction - intersection
- sphere :
$(x-c)^2-r^2=0$ , insert$x=r(t)$ and solve for$t$ - plane :
$(x-p)\cdot n=0$ , same - triangle :
$(o+td-p_1)\cdot n=0$ with triange normal$n=(p_2-p_1)\times (p_3-p_1)$ , test whether hit-point within using barycentric
- sphere :
- lighting
- shadows : send a ray from intersection point to light source, only ambient light if intersected by another object
- floating point error : intersection tolerance
$\epsilon$ needed
- floating point error : intersection tolerance
- recursive raytracing
- reflection : same incident and reflected angle
- refraction : Snell law
$n_1\sin\theta_2=n_2\sin\theta_2$
- depth of field
- motion blur
- caustics
- global illumination
- rasterization
- ray tracing acceleration
- brute force : intersect every ray with every primitive
$O(IN)$ - spatial datastructure : sorting, uniform grids, adaptive grids, bsp-trees
- kd-trees : recusively split cell using axis-aligned plane until maximum depth of minimum number of remaining objects reached, top-down
- bounding volume hierarchies : divide and conquer
$O(\log N)$ , group objects and bound by simple volumes for fast intersection rejection, bottom-up- sphere
- axis-aligned bounding box : AABB
- oriented bounding box : OBB
- k-discrete orientation polytopes : k-DOPs
- convex hulls
- kd-trees : recusively split cell using axis-aligned plane until maximum depth of minimum number of remaining objects reached, top-down
- brute force : intersect every ray with every primitive
- smooth curves : camera paths, animation curves, fonts, blending, scattered data approximation
- parametrics curves : simple, injective (no self-intersections), differentiable, regular (no null speed)
- curve length :
$t_i=a+i\Delta t$ and$x_i=x(t_i)$ - chord length :
$S=\sum_i\norm{\Delta x_i}=\sum_i\norm{\frac{\Delta x_i}{\Delta t}}\Delta t$ with euclidean norm and$\Delta x_i =x_{i+1}-x_i$ - arc length :
$s=s(t)=\int_a^t\norm{\dot{x}}dt$
- chord length :
- bezier curvees
- properties : affine invariance, invariance under affine parameter transformations, convex hull property, endpoint interpolation, symmetry, linear precision, variation diminishing
- derivative :
$\frac{d}{dt}b^n(t)=\sum_{i=0}^n b_i\frac{d}{dt}B_i^n(t)=n\sum_{i=0}^{n-1}\Delta b_iB_i^{n-1}(t)$ with forward differencing operation$\Delta b_i=b_{i+1}-b_i$ 
- uniform speed : unit speed parameter interval does not mean unit speed on curve
- increasing control points : raises degree of curve
- properties : affine invariance, invariance under affine parameter transformations, convex hull property, endpoint interpolation, symmetry, linear precision, variation diminishing
- Bernstein polynomials :
$B^n_i(t)={n\choose i}t^i(1-t)^{n-i}$ 
- recursion :
$B_i^n(t)=(1-t)B_i^{n-1}(t)+tB_{i_1}^{n-1}(t)$ with$B^0_0(t)=1$ and$B_j^n(t)=0$ for$j\not\in{0,\ldots,n}$ - partition of unity :
$\sum_{j=0}^nB_j^n(t)=1$ , global support, positive - derivative :
$\frac{d}{dt}B_i^n(t)=n(B_{i-1}^{n-1}(t)-B_i^{n-1}(t))$ - bezier cruve form :
$b^n(t)=b_0^n(t)=\sum_{j=0}^nb_jB_j^n(t)$ - bezier/control point :
$b_j$ , define control polygon
- bezier/control point :
- recursion :
- piecewise bezier : global parameter
$u$ - segment boundaries : knots
$u_0<\cdots <u_L$ define intervals$[u_i,u_{i+1}]$ - local parameter
$t$ in each interval :$t=\frac{u-u_i}{u_{i+1}-u_i}=\frac{u-u_i}{\Delta_i}$ - curvate derivatives :
$\frac{d}{du}s(u)=\frac{d}{dt}s_i(t)\frac{dt}{du}=\frac{1}{\Delta_i}\frac{d}{dt}s_i(t)$ - decomposition : in
$[u_0,u_2]$ , two bezier segments$b_0,\ldots,b_n$ in$[u_0,u_1]$ and$b_n,\ldots,b_{2n}$ in$[u_1,u_2]$ - enforce
$C^r$ -continuity at boundaries :$b_{n+i}=b^i_{n-i}(t)$ for$i=0,\ldots,r$ - first segment : deCasteljau algorithm
- segment boundaries : knots
