cs341.md

You can't use 'macro parameter character #' in math mode

$$
\def\norm#1{||#1||}
$$

CS341

GNU General Public License v3.0 licensed. Source available on github.com/zifeo/EPFL.

Spring 2016: Introduction to Computer Graphics

[TOC]

Introduction

• 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
• GLSL : shader programming
• graphics pipeline

Rasterization

• 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$
• 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

• 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)$

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)

2D transformations

• 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_2{L}_{1}x$
  • 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 }_i{x}_i$ with $\sum _i{\alpha }_i=1$
    • convex : $\sum _i{\alpha }_i{x}_i$ with $\sum _i{\alpha }_i=1$ and ${\alpha }_i\ge 0$
  • rotate around given point : $T(c)R(\alpha )T(-c)$
• object or camera transform

3D transformations

• 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

Viewing

• 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}{\text{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}$
• projection
  • in mathematic : idempotent mapping $P(x)=P(P(x))$
  • in computer graphics : 3D spaces to planar 2D images, not invertible, depth information lost
• 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$
      • 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}$
    • perpective fovy, aspect, near, far
      • $top=near\ast tan(fovy)$
      • $bottom=-top$
      • $right=top\ast 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}$

Visibility

• 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
• 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, $fac{e}_{n}ormal\cdot vie{w}_{v}ector>0$, negative triangle area

Lighting and shading

• 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 }^{\prime }\to \omega )L(x^{\ast }(x,{\omega }^{\prime }),-{\omega }^{\prime })\cos {\theta }^{\prime }d{\omega }^{\prime }$
• light sources
  • illumination function : $I(x,y,z,\theta ,\varphi ,\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
• local illumination : combines ambient, diffuse, specular reflection
  • ambient light : coming from all directions, camera independant and surface orientation, reflected intensity, $I_a=k_a{L}_a$
    • light source : $L_a$
    • material parameter : $k_{a}s$
  • diffuse reflection : $I_d=k_d(l\cdot n)L_d$
  • specular reflection : $I_s=k_s{L}_s{\cos }^{\alpha }\varphi =k_s{L}_s(r\cdot v{)}^{\alpha }$
  • illumination : $I=k_a{L}_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
• 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^{\prime },n_y^{\prime },n_z^{\prime },d^{\prime })\cdot M\cdot (x,y,z,1{)}^T=0\Rightarrow (n_x^{\prime },n_y^{\prime },n_z^{\prime },d^{\prime }{)}^T=(M^T{)}^{-1}\cdot (n_x,n_y,n_z,d{)}^T$

Texture

• 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
• 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
• 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
• 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 modeling

• 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}}^{\mathbb{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
• 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}_{i}f(s_{i}x)$ (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^{i}x)$
  • fractal increment : $H$ ($1$ smooth, $0$ more like white noise)
  • homogenous : same everywhere
  • isotropic : same in all direction
  • dimension : $2.1$

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))$
• 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)=a{e}^{bt}\cos t$, $y(t)=a{e}^{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
• Hausdorff fractal dimension : $D=\frac{\log N}{\log r}$
  • Cantor dust
• fractal dimension
  • integer component : indicates underlying Euclidean dimensions
    • fractional part :fractal increment
• 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
• 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

Shadow maps

• 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

Reflections

• 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

Raytracing rasterization

• 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
• lighting
• shadows : send a ray from intersection point to light source, only ambient light if intersected by another object
  • floating point error : intersection tolerance $ϵ$ needed
• 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

Bezier

• 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\mathrm{\Delta }t$ and $x_i=x(t_i)$
  • chord length : $S=\sum _i\text{norm}\mathrm{\Delta }{x}_i=\sum _i\text{norm}\frac{\mathrm{\Delta }{x}_i}{\mathrm{\Delta }t}\mathrm{\Delta }t$ with euclidean norm and $\mathrm{\Delta }{x}_i=x_{i+1}-x_i$
  • arc length : $s=s(t)={\int }_a^t\text{norm}\dot{x}dt$
• 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}\mathrm{\Delta }{b}_i{B}_i^{n-1}(t)$ with forward differencing operation $\mathrm{\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
• Bernstein polynomials : $B_i^n(t)=(\genfrac{}{}{0ex}{}{n}{i})t^i(1-t{)}^{n-i}$
  • recursion : $B_i^n(t)=(1-t)B_i^{n-1}(t)+t{B}_{i_1}^{n-1}(t)$ with $B_0^0(t)=1$ and $B_j^n(t)=0$ for $j\notin 0,\dots ,n$
  • partition of unity : $\sum _{j=0}^n{B}_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}^n{b}_j{B}_j^n(t)$
    • bezier/control point : $b_j$, define control polygon
• 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}{{\mathrm{\Delta }}_i}$
  • curvate derivatives : $\frac{d}{du}s(u)=\frac{d}{dt}{s}_i(t)\frac{dt}{du}=\frac{1}{{\mathrm{\Delta }}_i}\frac{d}{dt}{s}_i(t)$
  • decomposition : in $[u_0,u_2]$, two bezier segments $b_0,\dots ,b_n$ in $[u_0,u_1]$ and $b_n,\dots ,b_{2n}$ in $[u_1,u_2]$
  • enforce $C^r$-continuity at boundaries : $b_{n+i}=b_{n-i}^i(t)$ for $i=0,\dots ,r$
  • first segment : deCasteljau algorithm