Ray Tracing
Time Limit : 10 Second
Memory Limit : 256 MB
Submission: 1
Solved: 1
- Description
- Recently, wincat is busy with his Graduation Project, His Graduation Project is about Ray Tracing. In computer graphics, ray tracing is a technique for generating an image by tracing the path of light through pixels in an image plane and simulating the effects of its encounters with virtual objects. The technique is capable of producing a very high degree of visual realism, usually higher than that of typical scanline rendering methods, but at a greater computational cost. This makes ray tracing best suited for applications where the image can be rendered slowly ahead of time, such as in still images and film and television special effects, and more poorly suited for real-time applications like computer games where speed is critical. Ray tracing is capable of simulating a wide variety of optical effects, such as reflection and refraction, scattering, and chromatic aberration.
Optical ray tracing describes a method for producing visual images constructed in 3D computer graphics environments, with more photorealism than either ray casting or scanline rendering techniques. It works by tracing a path from an imaginary eye through each pixel in a virtual screen, and calculating the color of the object visible through it.
Scenes in raytracing are described mathematically by a programmer or by a visual artist (typically using intermediary tools). Scenes may also incorporate data from images and models captured by means such as digital photography.
Typically, each ray must be tested for intersection with some subset of all the objects in the scene. Once the nearest object has been identified, the algorithm will estimate the incoming light at the point of intersection, examine the material properties of the object, and combine this information to calculate the final color of the pixel. Certain illumination algorithms and reflective or translucent materials may require more rays to be re-cast into the scene.
Through ray tracing algorithm ,we can get a picture that just Looks like the real thing. But through this introduction, we can find that it need a lot of intersection operation. So we need a data structure to accelerate this process. wincat just learn about a tree structure that called Kd-tree. Is a tree that can split space to two small space in a node by a split plane which must be parallel to XOZ plane, YOZ plane or XOY plane that can help to accelerate intersection operation.
But when wincat try to use this structure, he find some problem, how to choice a split plane? Then he read more material about it, he know a method called SAH(Surface Area Heuristic),it use a function to estimate the cost by use a split plane, the lower cost, the more better split plane. the function is below
SA(V) is a function to count the surface area of the space V, Nl represent the space in the left of the split plane and Nr represent the space in the right of the split plane. V represent the whole space. Nl is the Triangle patch( every model can represent by many triangle patch) on the left space, and Nr is the Triangle patch on the right space, any triangle patch that is just on the split plane we can decide it belong either to Nl or Nr, Triangle patch that cross the split plane that belong to both Nl and Nr. for example in the picture 1-1 ,T is the split plane and we can know that:
Vl=(a*w*b+b*c+a*w*c)*2;Vr=(a*(1-w)*b+b*c+a*(1-w)*c)*2
V=(a*b+b*c+a*c)*2;
Now problem come ,Give you N triangle patches (1<=N<=50000),and Give your two positive integer Kl, Kr. Could you find a best split plane?
- Input
- There will be multiple tests. each test contain three positive integer N, Kt, Kl in one line.
then follow with N triangle patches, we will give your three point of the triangle patch in a line like below:
x1 y1 z1 x2 y2 z2 x3 y3 z3
...
Each coordinate is a double precision float number.
- Output
- A float number of the min cost of SAH, Round the numbers in the output to 3 digits after decimal point.
- sample input
-
3 4 4 0 1.0 1.0 0 2.0 2.0 0 3.0 3.0 3.0 0 3.0 4.0 0 4.0 8.0 0 8.0 1.2 1.2 0 7.2 7.2 0 9.3 4.7 0
- sample output
-
13.014
- hint
- source
- 中国地质大学(武汉)第七届ACM程序设计大赛暨华中地区部属高校ACM邀请赛