# Practical information * The exam is held on the 4.th of June 20135 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 ## Data structures ### Winged Edge every edge is on the form 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. 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 the neighboring edges of its face and a reference to the other half edge. ## Iterative Edge Collapse The idea is to provide dynamic model simplification, without the need of precomputed models. This is achieved by storing the edges in a sorted priority queue. And 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.