$$ \def\norm#1{||#1||} $$ # CS341 > [GNU General Public License v3.0](https://github.com/zifeo/EPFL/blob/master/LICENSE) licensed. Source available on [github.com/zifeo/EPFL](https://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 ![](img/cs341-3.jpg) ![](img/cs341-4.jpg) - 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 ![](img/cs341-1.jpg) - geometry primitives ![](img/cs341-2.jpg) - GLSL : shader programming - graphics pipeline ![](img/cs341-5.jpg) ## Rasterization - 2D canvas ![](img/cs341-6.jpg) - 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 ```python 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 ![](img/cs341-8.jpg) - barycentric rasterization - triangle : $(x_0,y_0)$, $(x_1,y_1)$, $(x_2,y_2)$ points with $\alpha,\beta,\gamma >0$ ![](img/cs341-7.jpg) - incremental algorithm : scan line, optimized hardware - interpolation : $n(P)=\alpha n(A)+\beta n(B)+\gamma n(C)$ ```python 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_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}$ ![](img/cs341-8.jpg) - 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$ ![](img/cs341-9.jpg) - 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$ ![](img/cs341-10.jpg) ![](img/cs341-11.jpg) - rotate around given point : $T(c)R(\alpha)T(-c)$ - object or camera transform ![](img/cs341-12.jpg) ## 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 ![](img/cs341-14.jpg) ![](img/cs341-13.jpg) - clip coordinates ![](img/cs341-15.jpg) - window/screen coordinates : normalized device coordinates ![](img/cs341-16.jpg) - 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}$ - 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 ![](img/cs341-17.jpg) - parallel : one direction of projection for all points, preserve parallelism, technical application - orthographic : direction of projection perpendicular to image plan ![](img/cs341-18.jpg) ![](img/cs341-19.jpg) - 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$ ![](img/cs341-20.jpg) - 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}$ ![](img/cs341-22.jpg) - 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}$ ![](img/cs341-21.jpg) ## 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) ![](img/cs341-23.jpg) ```python // 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 ![](img/cs341-24.jpg) - z-fighting ![](img/cs341-25.jpg) - 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 ![](img/cs341-26.jpg) - 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 ## 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'\to\omega)L(x^*(x,\omega'),-\omega')\cos\theta'd\omega'$ ![](img/cs341-27.jpg) - light sources - illumination function : $I(x,y,z,\theta,\phi,\gamma)$ ![](img/cs341-30.jpg) - 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 ![](img/cs341-31.jpg) - spot light : point light with limited angle, attenuation $\cosê\theta$ ![](img/cs341-32.jpg) - directional light : commonly used for far away light sources (e.g. sun), faster to evaluate than point lights (no light vector to be recomputed) ![](img/cs341-33.jpg) - area light - local illumination : combines ambient, diffuse, specular reflection ![](img/cs341-28.jpg) ![](img/cs341-29.jpg) ![](img/cs341-34.jpg) ![](img/cs341-35.jpg) - 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$ - diffuse reflection : $I_d=k_d(l\cdot n)L_d$ ![](img/cs341-36.jpg) - specular reflection : $I_s=k_sL_s\cos^\alpha\phi=k_sL_s(r\cdot v)^\alpha$ ![](img/cs341-37.jpg) - illumination : $I=k_aL_a+k_d(n\cdot l)L_d+k_s(r\cdot v)^\alpha L_s$ - phong reflection : ![](img/cs341-38.jpg) - piece-wise flat surface : per-vertex vs per-face normals ![](img/cs341-39.jpg) - 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 ![](img/cs341-40.jpg) - vertex normal : computing weighted averaging of incident triangle normals ![](img/cs341-41.jpg) - 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$ ![](img/cs341-42.jpg) ## 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 ![](img/cs341-42.jpg) - linear interpolation in world coordinates : nonlinear interpolation in screen coordinates ![](img/cs341-43.jpg) - perspective interpolation : GPU ![](img/cs341-44.jpg) ![](img/cs341-45.jpg) - texture filtering : $(u,v)$ real pixel coordinates - round to nearest integer - bilinear interpolation in containing texel ![](img/cs341-46.jpg) ![](img/cs341-47.jpg) - texture aliasing ![](img/cs341-48.jpg) - point sampling : depends on parameterization, texture minifaction leads to aliasing ![](img/cs341-49.jpg) - anti-aliasing : integrate over image pixel area in texture space, approximated by ellispe (EWA filtering) ![](img/cs341-50.jpg) ![](img/cs341-51.jpg) - approximated by mip-mapping : store texture at multiple levels-of-detail, use smaller versions when far from camera ![](img/cs341-52.jpg) - triangle mesh texturing : - texture coordinates parameterization : for each vertex from 2D texture domain to 3D object space ![](img/cs341-53.jpg) - mapping from simple intermediate object to 3D mesh ![](img/cs341-54.jpg) - spherical, cylindrical, planar maps ![](img/cs341-55.jpg) - cube maps ![](img/cs341-56.jpg) - spherical parameterization ![](img/cs341-57.jpg) ![](img/cs341-58.jpg) - 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 ![](img/cs341-59.jpg) ![](img/cs341-60.jpg) ## 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^n}\to[-1,1]$, no obvious repetition, rotation invariant, band-limited, not scale-invariant, efficient to compute, reproductible - value noise ![](img/cs341-61.jpg) ![](img/cs341-62.jpg) ![](img/cs341-63.jpg) - perlin noise : random gradient hermite-interpolated values ![](img/cs341-64.jpg) - 2D perlin ![](img/cs341-65.jpg) - 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_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$ ```python 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 ![](img/cs341-66.jpg) - 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 ```python 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 - Hausdorff fractal dimension : $D=\frac{\log N}{\log r}$ ![](img/cs341-67.jpg) - Cantor dust ![](img/cs341-68.jpg) - 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 ![](img/cs341-69.jpg) ![](img/cs341-70.jpg) - 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 ![](img/cs341-71.jpg) - dynamic shadows : multiple render passes - shadow volumes : polygonal representation of shadowed regions ![](img/cs341-72.jpg) - 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 ![](img/cs341-73.jpg) - sphere maps : $(u,v)$ texture coordinates ![](img/cs341-74.jpg) - 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 ![](img/cs341-75.jpg) - 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 ![](img/cs341-76.jpg) - backward ![](img/cs341-77.jpg) - ray casting : generate an image by sending one ray per pixel, check for shadows by sending ray towards the light - pipeline ![](img/cs341-78.jpg) ```python 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 ![](img/cs341-79.jpg) - 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 - 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 ![](img/cs341-80.jpg) ![](img/cs341-81.jpg) ![](img/cs341-82.jpg) ![](img/cs341-83.jpg) ![](img/cs341-84.jpg) - 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 ![](img/cs341-85.jpg) ![](img/cs341-86.jpg) - 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 ![](img/cs341-87.jpg) ## Bezier - smooth curves : camera paths, animation curves, fonts, blending, scattered data approximation - parametrics curves : simple, injective (no self-intersections), differentiable, regular (no null speed) ![](img/cs341-88.jpg) - 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$ - bezier curvees - properties : affine invariance, invariance under affine parameter transformations, convex hull property, endpoint interpolation, symmetry, linear precision, variation diminishing ![](img/cs341-89.jpg) ![](img/cs341-90.jpg) - 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$ ![](img/cs341-92.jpg) ![](img/cs341-93.jpg) ![](img/cs341-94.jpg) - uniform speed : unit speed parameter interval does not mean unit speed on curve - increasing control points : raises degree of curve - Bernstein polynomials : $B^n_i(t)={n\choose i}t^i(1-t)^{n-i}$ ![](img/cs341-91.jpg) - 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 - piecewise bezier : global parameter $u$ - segment boundaries : knots $u_0<\cdots