Problem Statement | |||||||||||||
| Rendering a computer generated image is a huge research area, with many
aspects. In this problem we will focus on one aspect of this problem:
rendering glass objects. In particular, you will be given the locations of a
number of glass ellipsoids and a number of
light sources. Each light source will cast some amount of pure, single
frequency light, uniformly in every direction. Each of the ellipsoids will have an index of refraction of 2, which determines the way light interacts with it (we will assume an index of refraction of 1 for the air around the ellipsoids). To make things simpler, we will ignore the effects of polarization in this problem. When a ray of light strikes the surface of an ellipsoid (either from within or without) some of the light is transmitted through the surface, and some is reflected off the surface. The angle of the reflected light ray is given by the law of reflection. The angle of the refracted light is given by Snell's law. To determine what fraction of the light is reflected and what fraction is transmitted, we use the Fresnel equations. Since we are ignoring polarization, we will always be using a reflection coefficient of R = (RS+RP)/2. It is important to note that in some cases we have total internal reflection. Your task here is to render a scene from a camera at (500,500,500) pointed in the -z direction. The camera has a view angle of 90 degrees. The only object in the scene other than the glass ellipsoids is a square surface spanning from (0,0,0) to (1000,1000,0). Your should return a double[] with one million elements, representing a 1000x1000 image from the camera. Pixel (x,y) should give the intensity of a ray pointed from the camera to the point (x+0.5,y+0.5). It is easiest to think about the rendering process in terms of a two-stage ray tracer. To do this, we first calculate the intensity of light at each location on the square surface. Once this is done, we then consider a ray leaving the camera, towards a part of the scene. If the ray from the camera strikes the square surface, our task is now easy, as we've already computed the intensity of the surface. If, however, it strikes an ellipsoid, we can use the same equations mentioned above to determine the fractional contribution from the part of the light that passes through the surface and the contribution of the reflected light. It is important to note that the lights do not have any impact in the second stage. A good way to think about it is that the lights serve to illuminate the square surface in stage one, are then turned off, and the camera is turned on, while the square surface remains illuminated. You will be given a String[] ellipsoids, describing the location and size of each ellipsoid. Each element will be formatted as "CENTERx CENTERy CENTERz A B C", describing an ellipsoid ((x-CENTERx)/A)2 + ((y-CENTERy)/B)2 + ((z-CENTERz)/C)2 = 1. You will also be given a String, lights, each element of which is formatted as "X Y Z", describing a light. Your task is to return a double[], where element x*1000+y is the intensity of light observed by the camera when looking towards (x+0.5,y+0.5) -- a raster image, in other words. When comparing your image to the reference image, the first thing we will do is normalize the image so that the average intensity of the pixels in the image is 1.0. Once this is done, we will compute the error of each pixel as abs(sqrt(YOU)-sqrt(REFERENCE)). Your score for an image will be the sum of the errors for the pixels in the image, plus 5% per second of computation. Your overall score will be computed using relative scoring. If the best score for a particular scene is BEST, and you score YOU, your score for that scene will be BEST/YOU. Getting StartedWriting a ray tracer is no easy task, so to help you get started, a C implementation of this problem is being provided (it is designed to work offline -- it is not a submission). It works by picking a random direction, and emitting a single ray of light from each of the light sources in that direction. When a ray of light hits a surface, two recursive calls are made, one for the ray passing through the surface (unless there is total internal refraction) and one for the ray of light reflected off the surface. The intensities of these rays are scaled appropriately. This is continued until the intensity of the light drops below a threshold, or a maximum recursive depth is reached, or the ray strikes the square surface. The total intensity of the rays striking the surface in each 1x1 grid cell is accumulated. After a large number of random rays are emitted, the second stage of the algorithm starts. A ray is directed from the camera to each of the locations, and again when it hits a surface two recursive calls are made. If the ray hits the surface, the intensity of the 1x1 grid cell it strikes is recorded.You may freely discuss how this implementation works in the forums, so long as you do not suggest or discuss improvements. Test generationThe tests are generated by first picking N and M, the number of ellipsoids and lights, respectively. N ellipsoids are then randomly placed, where each one is placed so that it does not intersect with any of the others. The M lights are then placed so that none of them are inside any of the ellipsoids. The centers of the ellipsoids are randomly chosen as points in the view area. The 3 size parameters are chosen between 10 and 100. The ellipsoids will not intersect the square surface. The lights are chosen to have z coordinate between 200 and 500. The generation code can be found at http://www.topcoder.com/contest/problem/RayTracer/Generate.java. | |||||||||||||
Definition | |||||||||||||
| |||||||||||||
Notes | |||||||||||||
| - | Because your return will be scaled to have an average intensity of 1, that absolute scale does not matter. | ||||||||||||
| - | The reference images are created using a ray tracer which is much slower than your must be. | ||||||||||||
| - | The time limit for each image is 10 seconds. | ||||||||||||
| - | The grayscale images are created using the square root of intensity, as this gives a better visual. | ||||||||||||
| - | The memory limit is 1024M and there is no code size limit. | ||||||||||||
| - | Higher quality reference images (with less aliasing) are currently rendering. | ||||||||||||
Constraints | |||||||||||||
| - | There will be between 1 and 5 light sources, inclusive. | ||||||||||||
| - | There will be between 1 and 50 ellipsoids, inclusive. | ||||||||||||
Examples | |||||||||||||
| 0) | |||||||||||||
| |||||||||||||
| 1) | |||||||||||||
| |||||||||||||
| 2) | |||||||||||||
| |||||||||||||
| 3) | |||||||||||||
| |||||||||||||
| 4) | |||||||||||||
| |||||||||||||
