Solutions to sample exam questions for EDAN30 Photorealistic Computer Graphics ============================================================================== 1a) When there are local light sources it is beneficial to split the rendering equation into a direct and an indirect illumination part. The reason is that the rendering equation (with no direct illumination part) states that you should integrate over the hemisphere over the point in consideration. You cannot do this analytically, and so must use random sampling. This means that there is little chance of hitting a local light source (especially if it is a point light). Note that you often shoot _many_ rays per pixel 1b) You only send _one_ new ray at each intersection. Russian roulette (RR) can be used to do this in an unbiased way. RR is a technique that uses a random number to determine whether the photon should be absorbed or not. if(uniform() > ABSORPTION) { // no absorption } // Divide output radiance by 1-absorption probability (russian roulette). out /= (1.0f-ABSORPTION); 1c) Full GI: L(S|D|G)*E Whitted: LD?(S|G)*E Notation is according to slide set from lecture. 1d) The answer is (assuming integrating over interval [a,b]): N (b-a)(1/N) sum[ f(x_i)/p(x_i) ], where x_i are drawn from a PDF p(x). i=1 This uses N samples. ====================================================================== 2a) A cylinder along z-axis with radius is described by x^2+y^2=1, that is, x and y are constrained by the equation of a unit circle, and z can have arbitrary values. The ray is r(t)=o+td, where o is the origin of the ray and d is the direction vector, and t is the scalar value which determines which point on the ray we choose. We assume that d is normalized, which means that t will be the true distance to the intersection points. The intersection distances are solutions to: {o_x+t*d_x x^2+y^2=1 and r(t)=o+td={o_y+t*d_y {o_z+t*d_z ==> (o_x+t*d_y)^2 + (o_y+d*d_y)^2=1 <==> (d_x^2+d_y^2)t^2 + 2(o_x*d_x+o_y*d_y)t + o_x^2+o_y^2-1=0 Set: e=(d_x^2+d_y^2), f=2(o_x*d_x+o_y*d_y), g=o_x^2+o_y^2-1 ==> e*t^2 + f*t + g=0 This is a polynomial of degree 2. The reasons for this is that there can exist at most two intersections (thus two solutions) to this problem. Divide the equation by e ==> t^2 + f/e*t + g/e=0 ==> (1) t^2 + b*t + c, where b=f/e, and c=g/e. [Note that e could be zero, in which case there could be infinitely many solutions (or none). There are infinitely many solutions when the ray origin is on the cylinder surface, and the ray direction is parallel to the z-axis.] The solution to (1) is: (2) t=-b/2 +- sqrt(b^2/4-c) Thus, there are only valid solutions if b^2-c>=0. The distances are then t_1 and t_2, the solutions to (2). To limit the length of the cylinder to l, we assume that (3) 0 <= z <=l for the intersection points. Thus, we compute the intersection points (assuming we have valid t_1 and t_2 values): p_1(t_1) = o +t_1*d p_2(t_2) = o +t_2*d If the z-component of p_1 (p_2) fulfils (3), then p_1 (p_2) is a valid point on the finite cylinder. 2b) First, compute coordinate frame around n. A rather bruteforce way to do this: Vector v; do { // Find random direction on the sphere do { v.x = 2.0f*uniform()-1.0f; v.y = 2.0f*uniform()-1.0f; v.z = 2.0f*uniform()-1.0f; } while(v.length2() > 1.0f); // loop until we find a point inside the sphere } while(v*is.mNormal <= 0.0f); // loop until we find a dir in the same hemisphere as the normal v.normalize(); Note that it is the intersection point, and it has a normal mNormal. So there is a test so that the direction vector v that we generate is in the positive hemisphere around mNormal. Also, for the points to be uniformly on the sphere, we reject points outside the sphere. 2c) No, since the light ray only hits a surface once. Indirect lighting is light coming not directly from a light source, but rather indirectly via another surface. Whitted ray tracing is LD?S*E, and so the indirect lighting happens when light comes from a light source, bounces either via a diffuse or specular surface, and then bounces further using one or more specular surfaces, and finally hits the eye. ====================================================================== 3a) The dynamic range, x:1, is given as the brightest pixel divided by the darkest pixel. Thus, you should compute the luminance of the pixels in the images, and find the ones with most and least luminance. Since, the course did not say how to compute luminance, we can instead take the average of the red, green, and blue components. Darkest: (18+17+19)/3=18 Brightest: (5700+8400+11800)/3=25900/3=8633.3 This far, everyone should have made it accurately... x=8633.3/18=479.6 [This is an accurate answer, and simple to compute] An alternative solution would be to look at the lowest and highest components: Lowest: 17 Highest: 11800 ==> x=11800/17=694 [Also easy to compute] 3b) A pixel is often stored as three floating point values (either 16 bit or 32 bits per pixel) for RGB. The reason is obvious from 3a) you need more than 8 bits per pixel to represent the content of a real scene. 3c) Rays not hitting any geometry are traced towards the environment map (EM), and each pixel in the EM can be thought of as a small light source. The environment map can be thought of as a cube that encloses the scene, and the size of it is infinitely large. Therefore, a lookup in the environment map only depends on the direction of the ray. The lookup gives us a HDR color which is used as the light source. ====================================================================== 4a) L(x -> phi) = L_e(x -> phi) + integral_(omega_x) { f_r(x, psi <-> phi) * L(x <- psi) * cos (N_x, psi) } d_(omega_psi) L is radiance x is the intersection point with normal N_x omega is the integration variable over the hemisphere L(x -> phi) is the radiance that we want to compute. It originates from the point x, going in direction phi (where the "viewer" is assumed to be) L_e is emitted radiance at the point x, going in the direction phi f_r is BRDF at x, where integration is done over psi as incoming direction, and phi is the outgoing direction L(x <- psi) radiance coming into point x, from direction psi cos-term: makes up for the increase of area for light hitting the surface at an angle 4b) Global illumination: L(S|D)*E Whitted ray tracing: LD?S*E 4c) L = (1/n) * sum_(i=1)^n { f_r(i) * L(i) * cos(i) / p(i) } Here we have used i as abbreviated notation for the dependency of the random variable. Usually, we use y_i as a random point which is the intersection in a random direction. ====================================================================== 5a) The ray is r(t) = o + t*d, where r, o, and d are vectors or points. t is a scalar. A point on the triangle is: w*p_0 + u*p_1 + v*p_2, where u + v + w = 1 --> w=(1-u-v) Set the ray and triangle equal: o + t*d = (1-u-v)*p_0 + u*p_1 + v*p_2 This can be reformulated as a matrix equation: (t) M*(u) = o-p_0, where t, u and v forms a column vector as shown to the left. (v) M is a 3x3 matrix with the following columns: (-d p_1-p_0 p_2-p_0) If the determinant of M, det(M), is zero, then the ray will be parallel to the triangle plane. The equation can be solved using Cramer's rule, or Gaussian elimination. So, the solution is expressed as: (t) (u) = M^{-1} (o-p_0) (v) Then you check whether u v and t have values inside the triangle. 5b) bool rayTriIntersect(float3 p0,float3 p1, float3 p2, float3 o, float3 d, float &u, float &v, float &t) { float epsilon = 1.0e-5; float3 e1 = p1-p0; float3 e2 = p2-p0; float3 s = o-p0; float det = determinant(-d,e1,e2); if(fabs(det) < epsilon) return false; // ray parallel to triangle plane // use Cramer's rule t = determinant(s,e1,e2); u = determinant(-d,s,e2); v = determinant(-d,e1,s); if(u<0.0 || v<0.0 || u+v>1.0) return false; return true; } where the determinant-function could be: float determinant(float3 a, float3 b, float3 c) { return dot(cross(a,b), c); // dot and cross are dot-products and cross-products } 5c) The difficulty lies in an infinitesimal chance of the ray hitting a line with no width. So, since no rays will hit any hair strands. A better solution is to model the hair strands as cylinders with a finite width, and use a lot of supersampling to get good quality. ====================================================================== 6a) Texturing: use mipmapping Screen-space aliasing: use more samples per pixel, and weight together using a filter kernel. 6b) In order to avoid aliasing, you need to sample at twice the frequency of the max frequency of the signal to be sampled. 6c) See slides about adaptive supersampling in the sampling lecture. A (too) brief description would be: start with the Quincunx-pattern (5 samples), and detect big contrast differences, and then apply Quincunx-pattern recursively where the big contrast differences are. You need to describe how the samples are weighted together for the final pixel color (see adaptive supersampling slides). The problem is that we can still miss objects with this technique. ====================================================================== 7a) The work will be proportional to the number of pixels, w*h, and to the number of triangles (because, we need to test each ray against each triangle), and then a factor of two will appear because of perfect reflections: w*h*n*2 --> O(w*h*n) 7b) The triangles can be divided into a tree, where each node contains a bounding volume (BV) which is just big enough to encompass all the triangles in the node's subtree. Such a hierarchy can be constructed in a top-down fashion for example. Start with all triangles, and find a BV (e.g., a box) that contains all the triangles. This will be the root node of the tree. Then split the geometry in one dimension (e.g., biggest axis of the box, which could be x, y, z). The split plane can be the median of the triangles (or mean). This creates two groups of triangles. Create a BV for each group, and make them children of the root. Continue recursively down until one or a few triangles per node. Intersection testing starts from the root node: test BV against ray. If hit, then recurse to both children, and so on. Testing a ray against the BV tree, then becomes O(log n), due to that the tree height will be about log n. O(w*h*log n) 7c) We shoot rays from the eye to the first positive intersection of an object. Here we shoot rays randomly (in a uniform way, or using importance sampling) over the hemisphere, and at each intersection of these rays, we "grow a sphere" until N photons are included. We do density estimation to compute the radiance for each "sphere". These are used for BDRF evaluation at the first intersection point, which gives us the color of the pixel.