Exam Questions Flashcards
1
Q
What is the ModelViewProjectionMatrix? What does it do?
A
The matrix that transforms from modelspace (via worldspace) into viewspace and finally into unit- or projectionspace (or normalized device coordinates or homogeneous coordinates).
2
Q
Explain screen tearing.
A
Screen appears to be torn between multiple frames with an intense flickering effect. Solved by double buffering and syncing buffer swapping with the vblank.
3
Q
What is the advantage of Bresenham’s line drawing algorithm?
A
It only uses integers, which used to be considerably cheaper than float values.
4
Q
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?
A
(M^-1)^T
5
Q
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]
A
Rotation: abcefgijk
Scaling: x: a, y: f, z: k
Translation: x: m, y: n, z: o
6
Q
State the object’s model-to-world matrix.
World space: x, y, z
Model space: a, b, y (Origin o)
A
[ax bx cx ox]
[ay by cy oy]
[az bz cz oz]
[ 0 0 0 1]
7
Q
Give two reasons for gamma correction.
A
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).
8
Q
Does the rendering order of transparent objects (e.g. triangles) matter? Motivate for point.
A
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.)
9
Q
Describe how anisotropic filtering works. Also tell why its needed.
A
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.
10
Q
What is a 2x2 grid, 2x2 RGSS, and 8 rooks? Draw them!
A
See e.g.: https://mynameismjp.files.wordpress.com/2012/10/supersampling-patterns.png
11
Q
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?
A
v0: (0,0), v1: (2,0), v2: (2,4), v3: (0,4)
12
Q
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.)
A
Alpha testing in fragment shader i.e. test if alpha = 0 for a fragment, if yes discard (“kill”) fragment.
13
Q
What is a vertex shader, geometry shader and fragment shader? Explain their functions respectively.
A
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.
14
Q
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?
A
Near plane is used to avoid a degenerate projection plane. Far plane is used to get better z-precision in the z buffer.
15
Q
Describe a method for a ray-polygon intersection test. (You may assume that the polygon is convex and lies in a 3D plane.)
A
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)
16
Q
Describe a test which determines whether or not two spheres intersect.
A
|| c1 - c2 || <= (r1 + r2)
17
Q
Describe a test which determines whether a sphere and a plane intersect.
A
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
18
Q
Describe how to sort objects in (roughly) back-to-front order when they are stored in an Axis Aligned BSP-tree.
A
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.
19
Q
Name a sorting algorithm that is effective when we have high frame-to-frame coherency (regarding the objects to be sorted per frame)?
A
Bubble sort or insertion sort (expected complexity/runtime: O(n)).
20
Q
How do you nicely terminate recursion in ray tracing if you do not simply want to terminate at a maximum recursion depth?
A
Terminate when the ray’s influence on the final pixel color is below a certain threshold. (Send a weight with the reflection/refraction rays.)
21
Q
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.
A
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).
22
Q
Explain how a skippointer tree works and what the advantage is.
A
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.
23
Q
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.
A
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.
24
Q
How are soft shadows from an area-light source computed with a path tracing?
A
At each intersection, one shadow ray is shot to one random position on the light source.
25
Which properties of a material are described by the Fresnell effect?
Degrees of transmission and reflection.
26
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.
27
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).
28
What is good with the z-fail algorithm, compared to z-pass?
Avoids the eye inside shadow problem.
29
Sketch one non-continuous curve and one C0-continuous curve.
Non-continuous: Broken curve
| C0-continuous: Point-wise continuous
30
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.
31
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.
32
Given two vectors wi and w0, how does one calculate the half angle vector wh?
wh = normalize(wi + w0)
33
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
34
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.
35
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.
36
```
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]
```
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?
2. How would you modify the rotation matrix for the car to turn slightly to the left?
3. When the user presses the "up-arrow" key, the car shall move forward in the direction it is facing.
4. 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?
1. tx = tx + 2
2. E.g.:
rz = rz + 0.01 * rx
rz = rz / || rz ||
rx = rz x ry
3. E.g.
(tx, ty, tz) = (tx, ty, tz) + 0.1 * rz
4. V = (TR)^-1
37
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.
38
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).
39
How much extra memory does it take to store a mipmap hierarchy of a texture compared to just the base texture itself?
~33%
40
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.
41
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.)
42
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.
43
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.
44
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.)
45
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 :)
46
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.
47
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.
48
What is Constructive Solid Geometry and how does it work?
Boolean operations between objects. Find overlap for each object and ray. Apply the Boolean operator on each interval and use the closest interval point.
49
This is the rendering equation:
L0 = Le + §W fr(x, w, w') Li(x, w')(w' * n)dw'
§ = integral
W = Omega, w = omega
Explain the equation and all of its components. You can include a figure in your answer.
```
Lo is outgoing radiance
Le is emitted radiance
Integral represents reflected radiance
fr is the BRDF
w' is incoming direction
n is normal at point x
W is hemisphere around x and n
Li is incoming radiance
x is position on surface
w is outgoing direction
```
Lo(x, w) = Le(x, w) + Lr(x, w)
50
Describe the Fresnell effect for dielectric materials and metals, respectively. (Visually or verbally.)
Dielectrics: High transmittance/low reflectivity for low angles. Low transmittance, high reflectivity for high angles.
Metals: High reflectivity for all angles (there can be a slight dip e.g. around 85 degrees).
51
Describe how the z-fail algorithm works.
Create shadow quads from the silhouettes of the shadow caster (as seen from light source). Capping planes are necessary: Cap shadow volume with the shadow caster's front facing polygons (as seen from light source) and cap at far end (often done by pushing the back-facing triangles towards infinity). Render ambient occlusion to color buffer. Turn off updating z-buffer and rendering to color buffer. Invert z test, i.e. use GL_GREATER. Render front facing (as seen from camera) shadow volume polygons to stencil buffer, decrementing stencil values. Render back facing shadow volume polygons to stencil buffer, incrementing stencil values. Render diff+spec lighting contribution to color buffer where stencil buffer = 0.
52
In which ways are NURBS more general than B-splines?
Control points can be set at non-uniform intervals and they can have different weights.
53
You have a scene of a spaceship which you render with a shader called FancyShader, to a texture, OffScreenTexture. To the rendered result, you want to apply a post-processing effect that generates a gray-scale image.
1. Order all of the following steps such that you would end up with a grayscale image of the spaceship in your window:
A. Draw Spaceship.
B. Bind GrayScaleShader
C. Draw fullscreen quad
D. Clear rendertarget
E. Bind OffScreenTexture to texture unit 0
F. Bind OffScreenTexture as rendertarget
G. Bind Window (default framebuffer) as rendertarget
H. Bind FancyShader
2. This is an effect that could instead be implemented directly in FancyShader. Why could there be a performance advantage of doing it as a post-processing pass (especially for more computationally heavy effects)?
3. Most/Many post-processing effects, like blur, can not be implemented in FancyShader. Why not?
1. E.g. F, D, H, A, G, E, B, C
Actually any of these orders work: ((F -> D)/H) -> A -> (G/E/B) -> C, where -> means strict order and / means any order.
2. The performance then scales with pixels, not fragments (or geometry).
3. Need to know result of neighbouring pixels.
54
What does the vertex shader do? I.e., what is its typical purpose?
Computes vertex position and projects from 3D to 2D. Precomputes per-vertex values, e.g., per-vertex lighting.
55
List all the spaces that a 3D vertex (typically) will be transformed through on its way from model space to screen space.
(0: model space/object coordinates)
1: world space
2: camera/view space/eye coordinates
3: projection space/homogenuous coordinates/clip space/unit cube
(4: normalized device coordinates/After perspective division/homogenization step)
5: screen space/window coordinates
56
What is a rigid body transform?
Only rotations and translations (no change of size or shape).
57
Assume that you are creating a system where you have a rotation matrix R, a scaling matrix S, and a translation matrix T, to define an object's transform. For a vertex v of the object, show how you compute the transformed vertex v'. (Use the recommended order of the matrices. A one-line answer v'=... is enough.)
v' = (TRS) v
58
State a simple 4x4-matrix M that performs a projection. Also explain which plane your matrix projects onto and what type of projection it is.
```
E.g.:
Plane z = 0.
Orthographic (parallel) projection.
M =
[ 1 0 0 0]
[0 1 0 0]
[0 0 0 0]
[0 0 0 1]
```
59
What is the difference between supersampling and multisampling?
Multisampling only runs the fragment shader once per fragment (not once per sample-inside-each-pixel). I.e., multisampling shares computations, e.g. executes fragment shader for only one sample but takes several depth samples.
60
Draw the quincunx pattern and state the weights per sample.
1 sample in each of the four pixel corners (weigh = 1/8) and 1 sample in the pixel center (weight = 1/2).
61
Assume that your graphics hardware supports the tent filter and sinc filter. You want maximum quality when enlarging your textures. Which filter would you choose?
Motivate.
The sinc filter, because it uses all texels for each sample and cuts too high frequencies.
62
Which types of filters are common in real-time computer graphics for minification of 2D textures?
- nearest (box)
- bilinear (tent) with and without mipmapping
- trilinear filtering with mipmapping, anisotropic filtering
63
What is a mipmap hierarchy?
A prefiltered hierarchy of halved (in both x- and y-) resolutions where each texel is the average of the 2x2 texels at the corresponding position of the lower level.
64
Write pseudocode for hierarchical view frustum culling.
1. Bound all objects in bounding volumes.
2. Sort bounding volumes in hierarchy.
3. Traverse hierarchy.
4. If bounding volume outside frustum, cull bounding volume (with all contents). Else: If end node/leaf, draw (if not empty), else traverse subhierarchy.
65
Describe a top-down approach to build an Axis Aligned BSP-tree for a scene.
Create minimal AABB around the whole scene. Split along an axis. Recursively split the 2 parts along new axis. Terminate if empty node, #triangles < threshold or level >= max recursion depth. (Axis aligned: x-, y-, z-axis are the split planes.)
66
Describe the structure of a typical ray tracer by using the functions main(), trace(), shade() and findClosestIntersection(). I.e., describe what these functions do and which functions they call (who calls who).
main() calls trace() for each pixel.
trace() returns the color of the closes intersected point by calling findClosestIntersection() and then calling shade() for the point.
shade() computes color + calls trace() recursively for reflection/refraction ray.
67
What is a BRDF? (You can answer by stating what the abbreviation BRDF stands for and assuming f() is BRDF and describe its input parameters and what it returns.)
Bidirectional Reflection Distribution Function. The function f(wi, wo) returns how much of the radiance from the incoming direction wi is reflected in the outgoing direction wo.
68
Describe what makes Path Tracing efficient.
Spawning many rays at each bounce would result in a ray tree (exponential). Most work is spent on the many rays at the bottom of the tree which have least impact on the pixel. Path tracing only follows one randomly chosen spawned ray per bounce, resulting in a ray path. Instead, many paths are traced per pixel. The advantage is that an equal amount of rays is traced at each level of bounces. Better balance between spent work and importance.
69
Describe the shadow map algorithm.
1. Render a shadow (depth) map from the light source.
2. Render image from the eye. For each generated pixel, transform/warp the x-, y-, z-coordinate to light space and compare the depth with the stored depth value in the shadow map (at the pixel position (x, y)).
If greater -> point is in shadow.
Else -> Point is not in shadow.
(Bias/offset is necessary due to discretization and precision problems.)
70
Assume p = (x,y,z,w). Perform the homogenization step on p.
p / w
71
Manually normalize the vector x = (a,b,c).
x / || x || = x / sqrt(a^2 + b^2 + c^2)
72
There are 4 main taxonomies of hardware, based on where in the GPU-pipeline sorting in screen space is done. Which are these four? (Names are enough, description optional.)
Sort-first: Sort the triangles spatially before the geometry stage.
Sort-middle: Sort the triangles spatially after the geometry stage.
Sort last fragment: Sort the rasterized fragments spatially.
Sort last image: Have a frame buffer per pipeline. Merge the frame buffers after full rendering.
73
Assume that you are a hardware designer of a modern GPU working at some company. What would be the main point on your wish list: Being able to increase the core clock frequency or being able to increase the memory bandwidth? Motivate!
Possible answer: You would typically want to increase the bandwidth. Memory transfer often bottleneck, fast memory/large bandwidth can cover for slow core clock and is more energy efficient (power consumption ~ freq^2).
74
Explain the rendering pipeline and corresponding hardware and draw figure.
Application stage: On CPU, feed Geometry stage with primitives to render.
Geometry stage: On GPU, operations on primitives per vertex (Vertex shader, Geometry shader, Clipping, Screen mapping).
Rasterization stage: On GPU, per pixel computations to render on screen (Triangle setup, Triangle traversal, Pixel shader, Merger).
75
Describe how to perform a rotation of a point or a vector p, by 2t degrees, around an axis u using quaternions.
q = (sin t u, cos t), pr = q p q^-1
76
Is a hardware implementation of the sinc filter on the GPU realistic today? Motivate.
Since it uses all texels for each sample, it is very expensive or slow. (So no.)
77
State 3 fundamentally different types of aliasing problems within computer graphics. I.e., aliasing problems at three fundamentally different situations.
1) At rasterization to a discrete set of pixels on the screen.
2) For textures.
3) In time.
78
Can you do displacement mapping with the vertex- and fragment shader? Motivate!
You can do vertex-based displacement mapping in the vertext shader. You cannot simply displace the output from the fragment shader (although workarounds could be possible nowadays using raycasting or OpenGL side effects).
79
Describe a method for an intersection test between a ray and a triangle in 3D.
Compute the ray's intersection point in the triangle plane. Then, do a point-in-triangle test in one of the following ways:
1) angle sum = 360 instead of 0
2) The Crossings Test. Count crossings between (horizontal) line and the polygon edges. Odd number =inside, even number = outside.
3) Check if point is inside the triangles formed by one vertex and the other vertices. If inside odd number -> point is inside polygon, else outside.
4) Use Plücker coordinates - but for 2D.
5) Test point against edges with 2D cross product.
80
Describe how to do a simple intersection test between a tetrahedron and a plane.
If all points lie on the same side of the plane, then no intersection. Else, intersection. Insert points into the plane equation and check signs.
81
Where in the tree are the triangles stored for an Axis-aligned BSP-tree?
In the leaves.
82
When using grids for ray tracing, we could use a concept called mailboxing.
1) What is the purpose?
2) How does it work?
1) To avoid recomputing the same intersection between a ray and object more than once. (Can happen if the intersection is outside the current grid cell.)
2) Use unique ray-ID with each ray. Store ray-ID of latest ray tested for intersection with the object. Also, store corresponding intersection. If ray-ID of current ray is same as stored ray-ID, then just lookup intersection instead of computing it.
83
Describe how to compute soft shadows from an area-light source in ray tracing.
Shoot several shadow rays to different light samples.
84
There are several algorithm for global illumination. Name and explain at least two of them.
Path Tracing, Bidirectional path tracing, Monte Carlo Ray Tracing, Metropolis Light Transport (, Radiosity).
85
Explain how you can do planar reflections of an object in a plane. You may assume that the plane goes through the origin and has the normal = (0,1,0).
1) Possibly, render the ground plan polygon into the stencil buffer.
2) Render the scaled model (scaling matrix S(1,-1,1)), and possibly mask with stencil buffer.
- Reflect light position as well.
- Use front face culling.
3) Render the ground plane (semi-transparent).
4) Render the unscaled model.
86
What continuity do two curves, both identically joined curves with common tangent directions at their respective join points, have if one is with and one is without arrows to depict the type of gradient discontinuity?
G1 continuity. Different gradients, but same direction.
87
Which of the following types are the curves below: Bezier curve, Interpolation curve or Hermite curve?
a) A curve going through its control points.
b) A curve with gradients specified per control point.
c) A curve with intermediate points used to approximate the gradients in the end points.
a) Interpolation curve
b) Hermite curve
c) Bezier curve
88
Linear interpolation of (u,v) in screen space does not give perspective correct texturing. Describe how perspective correct texture interpolation can be achieved.
In screen space, linearly interpolate (u/w, v/w, 1/w) from each vertex. Then, per pixel: ui = (u/w)i / (1/w)i, where i means screen space interpolated value.
89
Which types of filters are common in real-time computer graphics for magnification of 2D textures?
nearest (box filter)
bilinear (tent filter)
Mipmapping is wrong.
90
Which is fastest to compute for a GPU – Phong shading or Gouraud shading? Motivate!
Phong shading is more expensive, since full lighting is computer per pixel – instead of just per vertex and interpolated for each pixel. (If triangles are on average smaller than a pixel, then vice versa could be true.)
91
Why is the sweep-and-prune algorithm efficient in course pruning non-colliding objects?
Uses bubble sort (or insertion sort), which have expected runtime of resorting already almost sorted input O(n) instead of O(n log n), where n is number of elements. Flip bits of matrices also possible answer.
See sweep-and-prune:
Collision detection for x-, y-, z- axes, sort start and end of AABBs, active interval list, update sort using bubble sort, flip bits of matrices.
92
Describe the advantage and disadvantage of using ray tracing for collision detection compared to using bounding volume hierarchies.
Advantage: Ray tracing typically a lot faster.
Disadvantage: Cannot do exact collision detection (only sampling based).
93
Two separate photon maps are constructed during photon mapping. Which and why?
Caustics map and Global map (slowly varying illumination). The reason is that for correctness, the global map uses an even distribution of shot photons from the light source. For efficiency reasons, this is violated for the caustics map, when instead photons are fired in the directions of specular objects to capture the caustics effects. Physical correctness of the light intensity is typically much less visible in the latter case.
94
Why do we want to use Final Gather when using photon mapping?
Because using the global photon map for primary rays will result in poor low-pass filtering. I.e., give a blotchy (noisy) looking result. A blotchy result in the second recursion level/for secondary rays is less severe, since indirect illumination is a low frequency phenomenon.
95
Why does (classic) environment mapping not work well for planar reflections? (Preferably include an illustration.)
The environment map is, for each pixel-to-be-shaded, assumed to be centered on that pixel. Reflection vectors often change little on planar surfaces, and the environment-map pixel is only dependent on the reflection vector (not its origin). Another way to say this is that the environment map represents surrounding geometry infinitely far away.
96
Assume you have impemented a DDA algorithm for line drawing that can only draw lines with a low slope correctly, but has problem with steep lines. How can you in a simple way make it plot steep lines as well?
Swap roles of x and y. I.e., loop over y, instead of x, to plot the (x,y)-value.
97
What does the geometry shader do?
Takes one primitive as input and outputs 0 or more new primitives – possibly other primitives. E.g. triangles, lines, points.
98
How does trilinear interpolation work, and how many texture values need to be considered by the hardware for one trilinearly interpolated texture value?
With (u,v,d) as input, perform bilinear interpolation on texture levels above and below the d location, then perform linear interpolation on resulting samples, depending on the distance from each texture level to d. 8 texture values needed.
99
Explain portal culling.
Use scene structure of cells and portals. Recursively use view frustum culling through portals.
Algorithm:
- Divide into cells with portals (build graph).
- For each frame:
- - Locate cell of viewer and init 2D AABB to whole screen.
- - * Render current cell with View Frustum culling with regards to AABB (mark rendered objects).
- - Traverse to closest cells (through portals)
- - Intersection of AABB & AABB of traversed portal.
- - Goto *
- Exit:
- - When the current AABB is empty.
- - When we do not have enough time to render a cell ("far away" from the viewer).
100
What type of curves are described below and what are their strengths and weaknesses?
a) A curve with intermediate points used to approximate the gradients in the end points.
b) A curve with gradients specified per control point.
a) Bezier – Don't need to give tangent vectors manually.
| b) Hermite – Can guarantee continuous 1st derivatives between segments.
101
What is the point of using bubblesort in the sweep-and-prune algorithm?
Frame-to-frame coherency. Expected complexity for resorting nearly sorted lists is linear.
102
Which matrices are involved in the transformation of a vertex from model space to screen space? I.e. give the names for these matrices.
modelviewmatrix or (model-to-world and world-to-view/camera matrix), projection matrix(, viewport matrix)
103
Why do we use a separate global map and caustics map, instead of just having one combined map?
Global map represents correct, but sparsely sampled, light distribution. The caustics map needs very high sampling (high-frequency phenomenon) to be captured correctly.
104
Euler rotations can be used to describe the rotation of an object. The rotation is often defined by head, pitch and roll, which each is a rotation around one of the world space axes. E.g., the combined rotation is M = Rz(r) Rx(p) Ry(h), where Ri rotates around the world space axis i. Is M dependent on the multiplication order of Rx, Ry and Rz? Motivate!
Yes. E.g., simply use an example with a 90-degree rotation for the first rotation (head) and then it can be seen that the meaning of the pitch and roll are now flipped.
105
Assume you have an incoming light ray l = (1,2,3) at a surface point with the normal n = (2,3,4). Compute the reflection vector r. Also, normalize the reflection vector!
r' = -l + 2 * (n' * l) * n', where n' is n normalized.
r = || r' ||
106
Show how to compute the intersection between a ray and an infinite cylinder (all in 3D), centered around the z-axis.
cylinder: || x^2 + y^2 || = r
ray: r(t) = o + td
(ox + tdx)^2 + (oy + tdy)^2 = r^2
Solve for t and consider that there are two solutions. Also, show that solution is point o + td.
107
Show how it is possible to do an AABB vs plane test by only testing 2 of the AABB's vertices against the plane. (Hint: Assume a plane with normal n and an AABB defined by bmax and bmin. Express the two vertices by n, bmax and bmin.)
```
v0 = ((nx > 0 ? bmaxx : bminx), (ny > 0 ? bmaxy : bminy), (nz > 0 ? bmaxz : bminz))
v1 = ((nx < 0 ? bmaxx : bminx), ny < 0 ? bmaxy : bminy), nz < 0 ? bmaxz : bminz))
```
Insert the two vertices into the plane equation. If the seigns of all results are equal, then no intersection. I.e., sign(dot(v0,n) + d) = sign(dot(v1,n) + d).
108
The real-time graphics pipeline consists of three parts. Which?
Application stage, geometry stage, rasterization stage.
109
Give examples of what is done in each part of the real-time graphics pipeline: Application stage, geometry stage, rasterization stage.
Application stage: E.g. View frustum culling, animation.
Geometry stage: Transformation + per vertex shading (lighting).
Rasterization stage: Rasterization, texturing, interpolation of per-vertex values from vertex shader, z-test, fragment shading.
110
For each part of the real-time graphics pipeline (application, geometry, rasterization), describe how you can determine if this step is the performance bottleneck for the rendering.
Application stage: Swap glVertex to glColor.
Geometry stage: Remove all light sources.
Rasterization stage: Change window size.
111
Give examples of what the accumulation buffer can be used for. I.e., give (at least) two examples of effects that can be accomplished using the accumulation buffer.
Motion blur – Blend together several frames.
Depth-of-field – Blend images from slightly modified camera positions.
Soft shadows – Render hard shadow from several point light sources and blend the shadow contributions.
112
Create a 4x4-matrix that performs a uniform scaling, d, in x-, y- and z-coordinates, by utilizing the homogenization step. You must show how the homogenization step leads to the scaling.
```
Scaling:
M =
[1 0 0 0]
[0 1 0 0]
[0 0 1 0 ]
[0 0 0 1/d]
p = (x,y,z,1)
Mp = (x,y,z,1/d)
```
Homogenization:
p' = (x/1/d,y/1/d,z/1/d,1/d/1/d) = (xd,yd,zd,1)
113
Which are the three components in the real-time illumination model? It is sufficient to just state the names. (Emission is often included as the fourth component.)
Ambient, diffuse, specular
114
Compute the reflection ray, r, given n and l, where n is the surface normal and l is the incoming ray with direction towards the surface.
r = l - 2 * (n * l) * n
115
Is alpha channel in the color buffer required for correct rendering of transparent objects? Motivate!
No, you state the transparency using the alpha value of the color of the object. The alpha value, a, decides the interpolation factor between the source color c (the object's color) and the destination color d (the color of the pixel in the frame buffer). E.g.: Color = a * c + (1 - a) * d. The alpha channel in the color buffer does not need to be involved. For correct blending of the transparency, draw the transparent objects in back-to-front order.
116
Explain jittering. What is the advantage compared to other sampling schemes?
Stochastic sampling. Jittering replaces aliasing with noise (typically preferred by humans).
117
Describe the algorithm for photon mapping.
Caustics map, Global map (for indirect lighting), shoot photons from light source, store at diffuse surfaces. Ray trace from eye and use the maps for their respective contribution. Grow spheres to estimate intensity. Russian Roulette to decide if semi-diffuse materials specular or diffuse.
118
State at least 4 bandwidth reducing techniques used on graphics cards.
- Texture caching with prefetching.
- Texture compression.
- Z-compression.
- Z-occlusion testing (HyperZ)
- Pipelining
- Threads
