Exam Questions Flashcards
What is the ModelViewProjectionMatrix? What does it do?
The matrix that transforms from modelspace (via worldspace) into viewspace and finally into unit- or projectionspace (or normalized device coordinates or homogeneous coordinates).
Explain screen tearing.
Screen appears to be torn between multiple frames with an intense flickering effect. Solved by double buffering and syncing buffer swapping with the vblank.
What is the advantage of Bresenham’s line drawing algorithm?
It only uses integers, which used to be considerably cheaper than float values.
Assume that M is a matrix that is used to transform triangle vertices and that M nor necessarily is orthogonal. What is the matrix to correctly transform the normals?
(M^-1)^T
State which matrix components control 1) the scaling in x-, y- and z-direction, 2) rotations in general, and 3) translation in the x, y- and z-direction?
[a e i m]
[b f j n]
[c g k o]
[d h l p]
Rotation: abcefgijk
Scaling: x: a, y: f, z: k
Translation: x: m, y: n, z: o
State the object’s model-to-world matrix.
World space: x, y, z
Model space: a, b, y (Origin o)
[ax bx cx ox]
[ay by cy oy]
[az bz cz oz]
[ 0 0 0 1]
Give two reasons for gamma correction.
1) Screen output for CRT is non-linear (gamma) and needs to be countered (gamma correction) e.g. for correct antialiasing.
2) More efficient storage of color space (compressing to 8 bits).
Does the rendering order of transparent objects (e.g. triangles) matter? Motivate for point.
Yes, it matters because the blending operation (co = a * cs + (1 - a) * cd) is order dependent. (Unless you have a pure additive or multiplicative blending – but both are used for classic transparency.)
Describe how anisotropic filtering works. Also tell why its needed.
Up to 16 mipmap samples of a texel are taken along the middle (“line of anisotropy”) of the pixel projected onto the texel. Provides different amounts of filtering in the x and the y direction, i.e. avoids overblurring of simple mipmap.
What is a 2x2 grid, 2x2 RGSS, and 8 rooks? Draw them!
See e.g.: https://mynameismjp.files.wordpress.com/2012/10/supersampling-patterns.png
Assume you want to texture a quad (8 x 16) with a repeating chessboard pattern (4 x 4). You start by setting the texture wrap option to REPEAT. What texture coordinates (u,v) should you specify for each vertex v0, v1, v2, v3 to achieved the desired effect?
v0: (0,0), v1: (2,0), v2: (2,4), v3: (0,4)
Assume that you are rendering an impostor (i.e. billboard) as a rectangular quad. The impostor’s texture represents a tree and contains lots of fully transparent texels. How do you assure that objects that are later (for the same frame) rasterized behind the transparent parts of the impostor will show on the screen? (Hint: Use the fragment shader.)
Alpha testing in fragment shader i.e. test if alpha = 0 for a fragment, if yes discard (“kill”) fragment.
What is a vertex shader, geometry shader and fragment shader? Explain their functions respectively.
Vertex shader: Per vertex operations like projection to unit-cube (2D) and per-vertex attributes to be interpolated (color, normal).
Geometry shader: Take input primitives and output possibly another amount and possibly another type of primitive.
Fragment shader: Output pixel color from interpolated data from vertex shader.
Normally, you would want to draw all geometry that is in front of the camera. So, why is a near and far plane used for the view frustum?
Near plane is used to avoid a degenerate projection plane. Far plane is used to get better z-precision in the z buffer.
Describe a method for a ray-polygon intersection test. (You may assume that the polygon is convex and lies in a 3D plane.)
Convert to a point-in-2D-polygon test and use the crossing number algorithm / even-odd rule.
See also other methods:
- Analytical
- Geometrical
- Separating Axis Theorem (orthogonal or cross product axes)
Describe a test which determines whether or not two spheres intersect.
|| c1 - c2 || <= (r1 + r2)
Describe a test which determines whether a sphere and a plane intersect.
Insert the sphere center into the plane equation. If the result is smaller than the radius, there is an intersection.
I.e.: || n*c + d || <= r
Describe how to sort objects in (roughly) back-to-front order when they are stored in an Axis Aligned BSP-tree.
At each node:
If leaf, then draw the object.
Recursively continue traversal for the child at the further side of the node-plane.
Recursively continue traversal for the child at the hither side of the node-plane.
Name a sorting algorithm that is effective when we have high frame-to-frame coherency (regarding the objects to be sorted per frame)?
Bubble sort or insertion sort (expected complexity/runtime: O(n)).
How do you nicely terminate recursion in ray tracing if you do not simply want to terminate at a maximum recursion depth?
Terminate when the ray’s influence on the final pixel color is below a certain threshold. (Send a weight with the reflection/refraction rays.)
Describe a common recursive pattern for adaptive super sampling. Draw start samples, samples after one level of recursion and criteria to terminate or continue the recursion.
Start with quincunx sample.
Recursion through quincunx in corners.
Recursion if sufficient difference between corner and center, otherwise (or if above certain level of recursion).
Explain how a skippointer tree works and what the advantage is.
Stores in depth-first traversal order sequentially in an array, nodes store pointer/index to next element if traversal of subgraph should be skipped. Gives good cache coherence.
Explain Final Gather and how it is used with the photon maps (Caustics map and Global map). Also, explain what is good with Final Gather.
At first diffuse hit, instead of growing sphere in global map directly, sample indirect slow varying light by shooting 100-1000 indirect rays from p (Monte Carlo-sample) and grow sphere in the global map and also caustics map, where each of those
rays ends at a diffuse surface. Caustics at first intersection and global map at intersections of secondary rays.
Improves quality of global illumination by lowering noise from global map.
How are soft shadows from an area-light source computed with a path tracing?
At each intersection, one shadow ray is shot to one random position on the light source.
Which properties of a material are described by the Fresnell effect?
Degrees of transmission and reflection.
Describe the advantages and disadvantages of shadow maps vs shadow volumes. You should mention at least a total of four important bullets.
Shadow map pros: Handles any rasterizable geometry, constant cost per rasterized fragment from the camera’s view regardless of complexity (basically just a texture lookup), map can sometimes be reused, very fast.
Shadow map cons: Frustum limited, jagged shadow if map resolution is too low, tolerance threshold (bias) needs to be tuned for each scene for the depth comparison.
Shadow volumes, pros: Sharp shadows, handles omnidirectional lights.
Shadow volumes, cons: 3 or 4 rendering passes, lots of polygons and fill.
Why do you need to use a bias in the shadow map algorithm? What is the cause of the problem?
We compare two different discretizations – one from the eye and one from the camera. (To avoid z-fighting (incorrect self-shadowing) and light leaking.) The view sample can lie further from the light than the shadow map sample (due to discrete sampling).
What is good with the z-fail algorithm, compared to z-pass?
Avoids the eye inside shadow problem.
Sketch one non-continuous curve and one C0-continuous curve.
Non-continuous: Broken curve
C0-continuous: Point-wise continuous
Explan what Ck-continuity means and what G1-continuity means for curves.
Ck-continuity means that the derivatives of order 0 (or 1) to k exist and are continuous. G1-continuity means that the tangent vectors between each curve segment have equal directions, but their lengths (strengths) may vary.
What is the potential advantage and disadvantage of Bezier-curves compared to Hermite curves? (Think of a user that has to specify the curves)
Bezier – no need to give tangent vectors manually.
Hermite curves – Can guarantee continuous 1st derivatives between segments.
Given two vectors wi and w0, how does one calculate the half angle vector wh?
wh = normalize(wi + w0)
Draw the graphics pipeline’s major functional blocks (i.e., logical layout) and their relation to hardware, for a modern graphics card. (Hint: Preferably the functional blocks should be represented e.g. with the different parallel shader units and the other functional units.)
Application->Vertex shader (Parallel)->Primitive assembly->Geo shader (Parallel)->Clipping->Fragment generation->Fragment shader (Parallel)->Fragment merge (Parallel)->Display
Shaders executed on pool of ALUs
Clipping, Fragment generatation+merge executed on fixed function hardware
Explain what the z-buffer is used for and how it works.
Use a buffer called the z or depth buffer to store the depth of the closest object at each pixel found so far. As we render each polygon, compare the depth of each pixel to depth in z buffer. If less, place shade of pixel in color buffer and update z buffer.
Why do we want to use double buffering? Explain what can happen without it.
Avoids screen tearing by displaying one buffer while rendering another. Without it, renderings of different frames can be displayed at the same time.
Consider a game where the model-matrix (the position and orientation) for a car is described by a translation matrix, T, and a rotation matrix, R, as given below. M = TR T = [1 0 0 tx] [0 1 0 ty] [0 0 1 tz] [0 0 0 1] = [rxx ryx rzx 0] [rxy ryy rzy 0] [rxz ryz rzz 0] [0 0 0 1]
- When the user presses a key, the car should move 2.0 units in the world-space x direction. How would you modify the translation matrix?
- How would you modify the rotation matrix for the car to turn slightly to the left?
- When the user presses the “up-arrow” key, the car shall move forward in the direction it is facing.
- We now want a camera from inside the car (at the car’s position facing in the rz direction). How can you calculate this matrix?
- tx = tx + 2
- E.g.:
rz = rz + 0.01 * rx
rz = rz / || rz ||
rx = rz x ry - E.g.
(tx, ty, tz) = (tx, ty, tz) + 0.1 * rz - V = (TR)^-1
Describe flat shading, Gouraud shading and Phong shading.
Flat shading: Illumination computed using the triangle plane’s normal.
Gouraud shading: Illumination computed per triangle vertex and color interpolated for each pixel.
Phong shading: The normal for each pixel is interpolated from the 3 vertex-normals. Illumination computed per pixel using this normal.
How often are the vertex shader, geometry shader and fragment shader executed when one triangle is sent as input for drawing by the hardware? Explain your answer.
Three times; one time; one time per non-occluded fragment (unless supersampling schemes are used, which execute the fragment shader per fragment sample).
How much extra memory does it take to store a mipmap hierarchy of a texture compared to just the base texture itself?
~33%
What is the difference between bump mapping and displacement mapping?
Bump mapping only computes lighting as if the surface is bump, while displacement mapping actually (geometrically) displaces the surface according to the map.
Assume that you have enabled backface culling. How does the hardware determine if a triangle will be backfacing or frontfacing?
The vertices v0, v1 and v2 are projected onto the screen and if they appear in anti-clockwise order (right-hand side rule), the triangle is (by default) assumed to be frontfacing. Otherwise, backfacing. (The order could be reversed by specifying CW-order.)
To draw transparent objects using for instance OpenGL, you typically divide the triangles in two groups: the transparent ones and the opaque ones. 1) Which of these two needs to be sorted, 2) why, 3) and which order?
1) The transparent triangles,
2) for correct blending,
3) back-to-front.
Show how to compute the intersection between a ray and a sphere (in 3D).
Ray: r(t) = o + td
Sphere: || p - c || = r
Replace p by r(t) and solve for t.
Explain an efficient method for determining intersection between a ray and a box (in 3D).
Find tmin and tmax for the intersections against each of the three slabs. Keep max of the three tmin and min of the three tmax. If tmin < tmax, there is an intersection. (Check for degenerate case when ray parallel to slab.)
Draw a simple scene and visually divide it into
- an Axis-Aligned Bounding Box hierarchy
- a Sphere hierarchy
- an OBB hierarchy
- an Octree or Quadtree
- an Axis-Aligned Binary Space-Partitioning Tree
- a Polygon-Aligned Binary Space-Paritioning Tree
- a grid
- a recursive and a hierarchical grid
Draw :)
Why can’t we use ray tracing to do an exact object-object collision detection test?
Only tests a discrete subset of surface points and directions. A finite set of rays may miss small intersections.
What is a shadow cache? Explain what it is good for and how it works.
Pointer to previous intersected triangle (primitive) by the shadow rays. Null, if last shadow ray had no intersection. Reason: Speedup, potentially avoiding tree traversal.
