# Practical information * The exam is held on the 4th of June 2015 at 9 am. * [Old exams](http://www.idi.ntnu.no/emner/tdt4230/) # Curriculum * Chapter 6: Model representation and simplification. * Chapter 4: Viewing transformation (only). * Chapter 2: Perspective correction (only). * Chapter 3: Quaternions (only). * Chapter 5: Culling and Hidden Surface Elimination Algorithms (part). * Chapter 7: Parametric Curves and Surfaces (part). * Chapter 10: Visualization Principles . * Chapter 18: Scientific Visualization Agorithms. * Chapter 12: Illumination Models and Algorithms (part). * Chapter 14: Texturing (part). * Chapter 15: Ray Tracing (part). * Chapter 17: Basic Animation Techniques. # Chapter 6 Model representation and simplification Models are approximate representations of objects. Polygonal models are most common for surfaces, but mathematical models are also used. Models usually use _surface representation_, but in some cases _volume representation_ is better. For example when the object is semi-transparent or the internal structure is important. When an object is not closed, we cannot use volume representation. ## Properties of Polygonal Models A surface model is 2-manifold if every point on the surface has a neighborhood homeomorphic (topologic equivalent) to an open disk. This means that, on the surface, every edge is shared by exactly 2 faces and around each vertex exists a closed loop of faces. The manifold can have a boundary. In that case, the edges on the boundary belong to one face and the vertices on the boundary have a open loop of faces. If the manifold does not have a boundary, it is closed. Closed manifold models homeomorphic to a sphere satisfy Euler's formula, $ V - E + F = 2$. Here, V is the number of vertices, E edges and F faces. For manifolds in general, $ V - E + F = 2 - 2G$. G is the number of genus. That is, the number of holes penetrating the model. For example, a doughnut has genus 1. ## Data structures Primitive data structures store the coordinates of each vertice, edge and face separately. ### Winged-Edge Every edge is on the form $e(v_t,v_b,f_l,f_r,e_{tl},e_{tr},e_{bl},e_{br})$. The v's are the edges vertexes, f's are each face and the e's are each edge connected to the vertexes which also borders one of the faces. In other words, each edge stores references to its 2 vertices, its 2 adjacent faces and its 4 neighboring edges. This data structure makes it possible to traverse the model since we know every adjacent edge. ### Half-Edge The half-edge is an extension of the winged edge, where each edge is decomposed into two edges. Each half-edge stores its vertices, the neighboring edges of its face and a reference to the other half-edge (which stores the other face next to the edge). This structure is more efficient than winged-edge for some adjacency queries. ## Iterative Edge Collapse

sort the edges in a priority queue. iteratively: collapsing the edge of highest priority re-compute priority of all affected edges The quadratic error metric is mentioned as an example of how to order the edges in a priority, it also provides where to position the resulting vertex. In rough terms the idea of the quadratic error metric is to minimize the square distance of the new vertex from the faces around it. # Chapter 5 Culling and Hidden Surface Elimination Algorithms ## Hidden Surface Elimination ### Ray-Casting Algorithm A ray is followed for every pixel **p**. Checks intersection with every primitive **P** and return the closest intersection for each pixel. Slow: O(**pP**) but easily parallelizable. # Chapter 8 ## Bézier Curves ### Properties of Bézier Curves * Every n-th degree polynomial can be represented by a Bézier curve * Convex Hull property. The curve is inside the convex hull of its control points * Invariance under affine combinations. * Invariance under affine combinations of its parameter. * Symmetry with respect to comtrol points. * Linear precision. If all control points lie on a straight line, then the curve is also a straight line. * Variation diminishing property. A bezier curve is smoother than its control polygon. If you draw a straight line the number of intersections with the curve will be less than or equal to the number of intersections with the control polygon. A curve with a convex control polygon is also convex. A convex curve may have a non-convex control polygon. * Endpoint interpolation. A curve starts at its first point and ends at its last. * Derivative, since the curve can be represented by the Bernstein polynomials and they are derivative, so is the curve. * Tangents at endpoints are parallel to the first edge and last edge of the control polygon. * Pseudo-local control. Moving a control point has effect on the whole curve, but more pronounced effect close to the control point. ## B-Spline Curves ### Properties of B-Spline Curves * Local control * Strong convex hull property * Invariance under affine transformation. Applying an affine transformation to a B-Spline curve transforms only its control points. ## Rational Bézier & B-Spline Curves Rational curves are curves that use homogeneous coordinates. The weights are always positive because negative weights give unpredictable behaviors and some properties is not maintained, like the convex hull property. ### Properties of Rational Bézier Curves * Convex Hull property * Variation diminishing property * Invariance under affine transformation ### Properties of Rational B-Spline Curves (NURBS) * Convex Hull property * Variation diminishing property * Invariance under affine transformation NURBS offer all the properties of the other types of curves. Most used in practice. ## Bézier & B-Spline Surfaces The surfaces features the same properties as the curves respectivly. With the notable exeption of the variation diminishing property. # Chapter 10 Visualization Principles How do we visualize data? Plain matrices might be boring or difficult to look at, here are some alternatives. ## Tone Mapping ### Transfer functions Takes our data as input and outputs a value representing intensity. This function can take many forms, polynomials or step functions are examples. ### Color maps Makes use of a transfer function but includes color for additional visual effect. # Chapter 15 Ray Tracing