TDT4230: Graphics & Visualization
Practical information
- The exam is held on the 4th of June 2015 at 9 am.
- Old exams
Curriculum
Last updated in 2015.
- Chapter 3: Everything from 3.7 and out (this includes 3.7)
- Chapter 4: Complete chapter
- Chapter 5: Complete chapter
- Chapter 6: Complete chapter
- Chapter 7: Complete chapter except for 7.5.3
- Chapter 10: Complete chapter except for 10.6
- Chapter 12: 12.1, 12.4, 12.5, 12.6 (except 12.6.4), 12.11
- Chapter 14: Complete chapter, except for 10.7.3, 10.7.4, 10.7.5, 10.8. This means 10.9 is curriculum.
- Chapter 15: Complete chapter except for 15.2.3
- Chapter 18: Complete chapter
Youtube videos that are relevant to graphics
Basic graphics presented popculturally
Actual lectures online from an aussie
Chapter 3 2D and 3D Coordinate Systems and Transformations
2D and 3D Coordinate Systems and Transformations
A point in euclidian space can be defined as a 3D vector. Linear transformation is achieved by post-multiplying the point to a 3x3 matrix.
Affine transformations
Affine transformations are transformations which preserve important geometric properties of the objects being transformed
There are four basic affine transformations:
- Translation
- Scaling
- Rotation
- Shearing
Transformation Matrices
Quick note: a hyperplane refers to a substance of one dimensionality less than its ambient space.
I.e. in a 3-dimensional space, the
Translation
Translation defines movement by a certain distance in a certain direction.
Translation of a point p by a vector
The translation transformation matrix is an instantiation of the general affine transformation,
The 3D homogenous translation matrix is:
The
The inverse translation of
Scaling
We have
Mirroring about a major hyperplane can be done by using
The 3D homogenous scaling matrix is:
For 3D non-homogenous scaling, remove the fourth row and fourth column.
The inverse of the scaling matrix
Rotation
The book defines positive rotation about an axis
The three dimensional rotation transformation is defined as
The 3D homogenous rotation matrices are:
For the inverse 3D rotation transformation, use
In 2 dimensions we rotate about a point. The standard rotation transformations specify rotation about the origin.
The 2D homogenous rotation matrix is:
Shearing
Shearing increases
The 2D homogenous shearing matrices are:
The 3D homogenous shearing matrices are:
The inverse of a shear is obtained by negating the shear factors.
Quaternions
Quaternions are used to express rotation. They consist of 4 real numbers.
Rotation
We can use quaternions to rotate points around a vector. For the calculation we need
$p$ , the point that is to be rotated$\vec{v}$ , the vector that$p$ is to be rotated around.- Normalize
$\vec{v}$ to the unit vector$\hat{v}$ .
- Normalize
$\theta$ , the arc of the rotation (how many "degrees" to rotate if you will).
The rotated point
Note that quaternion multiplication is non-commutative, just like matrix multiplication.
Conversion between Quaternions and Rotation Matrices
Quaternion
To convert rotation matrix
Chapter 4 Projections and Viewing Transformations
To view 3D models on 2D output devices, we need to project the models. Projection usually happens after culling states and before rendering. A viewing transformation defines the transition from the world coordinate system (WCS) to canonical screen space (CSS), via the eye coordinate system (ECS). It also defines the clipping boundaries for frustum culling in ECS.
Projections
There are two types of projection that are interesting in this course, perspective and parallel projection. The distance of the center of projection from the plane of projection is finite in perspective projection, and infinite in parallel projection. There are some other differences:
Property preserved | Affine | Projective |
Angles | No | No |
Distances | No | No |
Ratios of distances | Yes | No |
Parallel lines | Yes | No |
Affine combinations | Yes | No |
Straigt lines | Yes | Yes |
Cross ratios | Yes | Yes |
Projection images of objects defined by a set of points need one more element than affine images. With these extra points, we can perserve properties like depth and color. Ratios of distances are not preserved, but cross ratios are preserved.
Perspective Projection
To project a point
Parallel projection
To perform a parallel projection, we need to know the plane of projection and the direction of projection (a vector). The book mentions two types of parallel projection, orthographic and oblique.
Orthographic Projection
All the projection lines in an orthographic projection are orthogonal to the projection plane. Usually, one of the main planes is used as the plane of projection. To project onto the xy-plane, we can use the following matrix:
Oblique Projection
The direction of the projection is given by
Viewing Transformation
A viewing transformation defines the transition from the WCS to ECS to CSS. It also defines the clipping boundaries for frustum culling in ECS. A point
WCS to ECS
World coordinate system to eye coordinate system is the first transition in viewing transformations. First, we need to define the ECS axes. ECS is usually defined by
- E
- The point of view, the location of an observer
$\overrightarrow{g}$ - The direction of view, a vector
$\overrightarrow{up}$ - The up direction, which does not need to be perpendicular to
$\overrightarrow{g}$
The axis
TODO: math for actual transformation
ECS to CSS
There are two ways of converting from the eye coordinate system to the canonical screen space, orthographic projection and perspective projection.
Orthographic Projection
We need to choose parallelepiped-shaped a part of the scene that will be mapped to CSS, called the view volume. It can be defined by two opposite vertices,
Perspective projection
The view volume is a truncated pyramid symmetrical about the
The matrix for this projection is given by
Frustum Culling and the Viewing Transformation
Frustum culling eliminates primitives that lie outside the view volume. This happens in CSS, after the
The Viewport Transformation
The viewport is the rectangular part of the screen where contents of the view volume are displayed. It is defined by the bottom-left
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,
Data structures
Primitive data structures store the coordinates of each vertice, edge and face separately.
Winged-Edge
Every edge is on the form
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
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. Usually, edges further away have a higher priority.
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 7 Parametric Curves and Surfaces
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 are 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
Sometimes we need to normalize a dataset to another, this is also covered in visual computing fundementals. The equation to normalize
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 12 Illumination Models and Algorithms
Phong Illumination
Estimates the intensity as the sum of four components.
$I_e$ - Emission. The light the object itself emits.
$I_g$ - Ambient reflection. Compensation for the lack of actual light interaction between objects.
$I_g = I_a k_a (0 < k_a < 1)$ . $I_d$ - Diffuse reflection. Reflection of light sources uniformly distributed in all directions.
$I_s$ - Spatial reflection. Maximum intensity in the mirrored direction of the light source.
Ambient Occlusion
Chapter 14 Texturing
Bilinear Interpolation
The principle of texture value interpolation is to map a texture
Barycentric coordinates
Points are defined as a linear combination of the three points that define a triangle.
Barycentric coordinates are calculated by dividing the triangle that defines them into three pieces.
The sum of the area of our new three triangles must equal our original triangle.
Mapping Different Surfaces
Planar
Parallelly project the coordinates to the surface
Spherical
Map on a surface described by spherical coordinates