Introduction to the

In the traditional rasterization method, each object is rasterized to form several pixels, and then each pixel needs to calculate the color formed by the light source shining directly on itself and reflecting back to the eye. This algorithm is extremely fast, but can only represent direct illumination, the image quality is low.

Rasterization mainly relies on the information of each vertex of the triangle, and it is difficult to make good use of the global information. The following scenes are not well processed, such as Soft shadows, Glossy reflection and Indirect illumination. Ray tracing is an imaging method that conforms to physical laws. Compared with rasterization, it uses global information, has a large amount of calculation, and produces images slowly but with good quality.

The idea behind ray tracing is that, since the light path is reversible, you project light from your eye along each pixel of the screen, determine where it intersects with the scene object, and then calculate how much light it receives at that intersection. Creating a screen image requires projecting light out of the screen resolution, which is undoubtedly a huge amount of computation, but the image quality is extremely high.

Whitted-Style Ray Tracing

Whitted-style Ray Tracing: Also called Recursive Ray Tracing, whitted-style Ray Tracing is the most classic Ray Tracing algorithm.

  1. Each pixel on the screen makes a light projection.
  2. Each projection of the light requires the determination of the intersection, and the potential for reflection and refraction when it hits the intersection, proceed in a new direction until it hits the diffuse surface.
  3. Finally, the light exposure of each intersection point is combined (using Blinn Phong algorithm) with a certain weight, resulting in the color of that pixel.

Note that:

  • In order to reduce recursion times, certain additional recursion termination conditions can be given (e.g., the maximum allowed number of reflections or refractions is 10).
  • Light loses energy (as determined by coefficients) after each reflection and refraction, so it contributes less energy after many projections.
  • If the projected ray does not hit the object, it generally returns a background color.
  • The diffuse surface is a rough surface that can be assumed to reflect light equally in all directions, so there should be an infinite amount of light reflected when the light hits the surface, but to reduce the calculation, Whitted-style terminates recursion by Blinn Phong coloring the intersection directly.

Path Tracing

Path Tracing: is currently the most mainstream ray tracing algorithm; Compared with whitted-style Ray Tracing algorithm, Path Tracing believes that the propagation of light radiates in all directions in the form of energy (in line with physics-based Rendering), which is consistent with the Rendering Equation: While the rendering equation is simple and elegant, the process of solving the equation is too complex. Three concepts are introduced here to simplify the calculation of the equation:Monte Carlo Solution, Russian Roulette, RR, Sampling the Light.

Monte Carlo Solution

Monte Carlo method can solve mathematical problems by means of random sampling. For solving definite integral problems, monte Carlo method can estimate an approximate numerical solution. We regard the integral variable as a continuous random variable, and each time we sample, we use the function value mapped from the sampled variable to represent the corresponding function value of all variables in all integral intervals. Multiple samples gradually approach the integral value of the real function in the integral domain.The figure above shows the mathematical expression of the Monte Carlo integral, through which we can see that in the process of solving the integral, we only need to know the corresponding of the variablesFunction valueandProbability density distributionCan. I take the function divided by the probability density,This is equivalent to estimating the population with a single use sampleAnd then the true value can be approximated by multiple estimation and averaging. Monte Carlo integral is a kind of unbiased estimator. It can be found that the expectation is the definite integral value by calculating the mathematical expectation of the integral formula. Notice that the more samples you take, the less error you’re going to get, and you’re going to sample and integrate on whatever variable you need to estimate.Following the simple Monte Carlo approach, the pseudo-code is implemented as follows

    Randomly choose 1 directions wi~pdf(w);
    Lr = 0.0;
    Trace a ray r(p, wi);
    if(ray r hit the light)
        Lr += L_i * f_r * cosine / pdf(wi);
    else if(ray r hit an object at q)
        Lr += RayTracing(q, -wi) * f_r * cosine / pdf(wi);
    return Lr;
}
Copy the code

Two problems can easily arise with this approach:

  1. The amount of light, which increases exponentially with the number of bounces of light, would make the calculation explode, which would be unacceptable
  2. No termination conditions

For the first problem, we will solve it by the improved Monte Carlo integral: theN 1,, so no matter how many times the rebound, the direction of differentiation can only be 1 at most, there will be no explosive growth phenomenon.So how do you solve this noise? Ray Tracing can be repeated multiple times for the same screen pixel. After a few colorings (render for a certain amount of time) you can get a less noisy image.

Russian Roulette (RR)

Even with improvements to the Monte Carlo integral, the second problem remains unsolved: there is no termination condition. (Energy determination of indirect light source still needs to be determined through continuous recursion)

The rough idea, limiting the depth of the recursion, namely ejection number, but this is obviously not in conformity with the laws of physics, because the real light is constantly ejection in the environment, and in the previous section we introduced, limit number of ejection, is abandoned the rendering Taylor series expansion equation of higher order term, there must be energy loss, the most obvious performance is fewer ejection, The overall picture is dark. Obviously,A computer can’t count countless ejectionsThen a method was introduced: Russian roulette.If the shading function is supposed to output Lr, set a certain probability P for the shading function to output Lr/P and probability 1−P to output 0, in this case:The expected value of the function’s output E is equal to the expected output Lr, that is to say, as long as the number of samples is enough, the shading will be energy conservation (no energy loss).

RayTracing(Point p,Vector3 wr){ 
Manually specify a probability P_RR 
Randomly select ksi in a uniform dist. in [0, 1] 
if(ksi > P_RR) 
return 0.0;
Randomly choose 1 directions wi~pdf(w);
Lr = 0.0; 
Trace a ray r(p, wi);
if(ray r hit the light)
Lr += L_i * f_r * cosine / pdf(wi);
else if(ray r hit an object at q)
Lr += RayTracing(q, -wi) * f_r * cosine / pdf(wi); return Lr / P_RR; }
Copy the code

Sampling the Light

In the direct lighting section of Path Tracing, there is an efficiency problem: The probability of Ray hitting the light source is very low (because the light source area is usually very small), so it is easy to waste a lot of recursive operations (the idea of Russian gambling was terminated before seeing the light source).

For this reason, intelligent humans switch the sampling idea from sampling on the hemispheres to sampling on the light source plane (assuming the light source area =A) :Because the solid Angle = / square distance per unit area, so the dW = dAcos theta ‘/ | x – x | squaredIn this way, when calculating direct light, the integrals on one hemisphere are changed to integrals on one light source. This makes it easier for Path Tracing to get direct light results (ray is easier to hit the light source). Of course, the amount of light contributed can also be adjusted according to the probability (probability is changed from 1/2PI to 1/A).

A simple solution is to make the shading point project a ray to the light source, if the shading is not, then calculate the direct light and contribute to the resultPath Tracing final pseudocode:

// Contribution from the light source. L_dir = 0.0; Sample the light at x '(PDF_light = 1 / A); Shoot a ray from p to x '; If (the ray is not blocked in the middle) cosine theta f_r L_dir = L_i * * * cos theta '/' - p | | x ^ 2 / pdf_light; // Contribution from other reflectors. L_indir = 0.0; Test Russian Roulette with probability P_RR; Uniformly sample the hemisphere toward wi (pdf_hemi = 1 / 2pi); Trace a ray r(p, wi); If (Ray R hit a non-emitting Object at Q) L_indir = RayTracing(q, -WI) * F_R * cos θ / PDF_HEMi/P_RR; if(Ray R hit a non-emitting Object at Q) L_indir = RayTracing(Q, -WI) * F_R * cos θ / PDF_HEMi/P_RR; return L_dir + L_indir; }Copy the code

Sampling on the light source, direct illumination, there will be no random direction of the light source to waste the problem.

Accelerating structure of ray intersection

Why need to accelerate the structure, because the light and objects for intersection is the first step in ray tracing, general, the object is described by using triangular grid, problem is converted into light and triangle intersection, and in the scene is a large amount of triangles, impossible for every light and triangle intersection, so the use of light and surrounded by nuclear intersection process to speed up the intersection, for the convenience of calculation, Using light and AABB intersection, how to divide the space into a set of AABBs, that is, how to design accelerated structure, is the content of this section.

Using the Grid

Uniform Grids. The space is evenly divided into several grids of equal size, and whether there is an object surface in each grid is recorded. Then the light passes through the scene to judge whether there is an object surface in the grids along the way: if there is, judge whether it intersects with the object surface; If not, continue.So the first question is, what granularity is it? If it’s too big, the extreme conditions are a whole block, and there’s no acceleration; If it’s too small and there are a lot of cubes in the space, that adds a lot of computation. As a rule of thumb, 3D should be divided into: cell = 27*objs. The second problem is that uniform partition is more suitable for the case where objects are evenly distributed in the whole scene. For the case where objects are not evenly distributed, especially for the case where there is a large piece of object free space, the typical “Teapot in a stadium”, such a scene wastes a lot of calculation on the object free space.

Use the KD – Tree

Before ray tracing, the acceleration structure needs to be established. Using KD-tree to establish the acceleration structure has the following characteristics

  1. The partition plane is split along the axis
  2. Binary tree shape
  3. All objects are stored on the leaf node

Light passes through space and intersects each node in turn. If it doesn’t intersect with a node, it won’t intersect with all nodes in the subtree whose root node is this node. If it intersects with a node, it is necessary to continue to judge whether it intersects with its left and right child nodes until the leaf node intersects with the light, and then determine whether the object in the leaf node intersects with the light.

The construction of accelerated structure by KD-tree is roughly like this. Let’s think about the problems existing in this method. First, determine which AABBs the object intersects with; Secondly, it is also the problem encountered by ocT-tree and BSP-tree, that is, there is an object with the intersection of multiple AABBs, that is, there are multiple leaf nodes in one object. This leads to the next space division method, according to the distribution of objects to divide the space.

Using BVH

BVH is segmented according to objects, so that an object is not surrounded by multiple AABBs as far as possible. The method is as follows:

  1. Find an enclosing core
  2. In some way, the object surrounding the core is divided into two parts
  3. The two parts recalculate the enclosing kernel
  4. Then, according to the idea of KD-tree, the binary recursion is repeated in different dimensions until the termination condition (the number of objects is small enough) is met.
  5. The object is placed on each leaf node, and the other nodes are used to speed up the judgment

conclusion

An obvious advantage of Ray Tracing is that it can achieve indirect Illumination through recursion (the number of recursions means the number of reflections) and therefore can achieve the effect of Global Illumination indirectly when using Ray Tracing algorithms. There are two main algorithms in ray-tracing framework:

  • Whitted-style Ray Tracing: Based on the concept that light is direct light.
  • Path Tracing: Based on the concept that light is energy radiation, using Monte Carlo Solution + Russian Roulette (RR) + direct light source sampling method.

reference

  • Ray Tracing – KillerAery – Cnblogs.com
  • GAMES101 Course Notes -Ray Tracing4 – Zhihu.com
  • GAMES101- Introduction to Modern Computer Graphics – Yan Lingqi bilibili bilibili