Over the past few years, ray tracing seems to have become the "number one dream" of the real-time 3D graphics world. Interest in this rendering technology peaked when young researcher Daniel Pohl announced his project on this technology back in 2004.
The reason for the general public's interest in the work was largely due to Pohl's focus on the famous id Software games Quake III, Quake IV and the shooter franchise Quake Wars 3D. The researcher attracted a lot of attention from the press, and gamers began to dream of a bright future when their favorite games would be rendered using ray tracing and get rid of rasterization.
Intel quickly drew attention to the project, and the company found it the perfect way to justify increasing the number of cores in processors. The company quickly launched its own research program, and today Intel never misses an opportunity to emphasize that ray tracing is the future of real-time 3D gaming. But is this really so? What technological realities lie behind the marketing hype? What are the real benefits of ray tracing? Can we expect ray tracing to replace rasterization? We will try to answer these questions.
Click on the picture to enlarge.
Basic principles
The basic idea of ray tracing is very simple: for each pixel on the display, the rendering engine draws a direct ray from the observer's eye (camera) to an element of the rendered scene. The first intersection is used to determine the color of the pixel as a function of the element's surface being intersected.
But this alone is not enough to produce a realistic scene. The illumination of the pixel must be determined, which requires drawing secondary rays (as opposed to primary rays, which determine the visibility of the various objects that make up the scene). To calculate the effects of scene lighting, secondary rays are drawn from the intersection points to different sources Sveta. If these rays are blocked by an object, then that point is in the shadow cast by the light source in question. Otherwise, the light source affects the lighting. The sum of all the secondary rays that reach the light source determines the quality of illumination that hits our scene element.
But that's not all. To achieve the most realistic rendering, the reflection and refraction characteristics of the material must be taken into account. In other words, you need to know how much light is reflected at the point where the primary beam intersects, as well as the amount of light that passes through the material at that point. Again, reflection and refraction rays must be drawn to calculate the final pixel color.
As a result, we get several types of rays. Primary rays are used to determine the visibility of an object and are similar to a kind of Z-buffer used in rasterization. And the secondary rays are divided into the following:
- rays of shadow/light;
- reflection rays;
- refraction rays.
Classic ray tracing algorithm. Click on the picture to enlarge.
This ray tracing algorithm is the result of the work of Turner Whitted, the researcher who invented the algorithm 30 years ago. Until then, the ray tracing algorithm only worked with primary rays. And the improvements Whitted made turned out to be a giant step towards realism in scene rendering.
If you are familiar with physics, you probably noticed that the ray tracing algorithm works “in reverse side"from the phenomena occurring in real world. Contrary to the popular belief in the Middle Ages, our eyes do not emit rays of light; on the contrary, they receive rays of light from light sources that are reflected on various objects around us. In principle, this is how the very first ray tracing algorithms worked.
But the main disadvantage of the first algorithms was that they imposed a huge computational load. For each light source, you need to cast thousands of rays, many of which will not affect the rendered scene at all (since they do not intersect the imaging plane). Modern algorithms Ray tracing is an optimization of the underlying algorithms, using what is called reverse ray tracing, since rays are drawn in the opposite direction from reality.
The original ray tracing algorithm resulted in a large number unnecessary calculations. Click on the picture to enlarge.
Benefits of Ray Tracing
As you have already seen, the main advantage of the ray tracing method is its simplicity and elegance. The algorithm uses only one primitive object to display effects that often require a non-trivial approach and complex stimulation technologies when using a standard rasterization method.
An environment map gives a good approximation of simulating environmental reflections, but ray tracing can even simulate the reflections of Luigi's car's eyes on the hood. Click on the picture to enlarge.
Reflections are one area where ray tracing excels. Today in 3D engines modern games reflections are calculated using environment maps. This technology gives a good approximation to the reflections of objects located “at infinity” or at environment(as can be seen from the name), but for closely located objects the approach shows its limitations.
Racing game developers, in particular, have created tricks to simulate the reflections of nearby objects using so-called dynamic cube maps. The camera is positioned at the level of the gamer's machine, after which rendering is carried out in the main directions. The rendering results are then stored in cubemaps, which are used to display reflections.
Dynamic cube maps can simulate reflections of nearby objects, such as an airplane on a teapot. But they cannot cope with reflections of parts of an object on each other, for example, the spout of a teapot on its body. Click on the picture to enlarge.
Of course, dynamic cubemaps also have their drawbacks. It is quite expensive in terms of computing power to calculate several rendering results, and to prevent performance from dropping too much, cube maps are not recalculated as many times as the main image. This may cause a slight delay in reflections. To reduce the load on the fill rate, rendering is performed at a lower resolution, which can lead to pixelation in reflections. Finally, this technology is often limited to the gamer's machine, with all other objects using simpler (spherical) environment maps.
With the ray tracing method, reflections are displayed perfectly, and without complex algorithms, since everything is calculated by the main rendering algorithm. Another advantage can be considered the display of reflections of parts of an object on each other, for example, the reflection of a side-view mirror on the body of a car, which is very difficult to obtain using the rasterization method - but here this reflection is obtained in the same way as others.
The ray tracing method allows you to simulate the reflection of parts of objects on each other, for example, the reflection of a side-view mirror on a car body. Click on the picture to enlarge.
Another undeniable advantage of the ray tracing method is high-quality processing transparency effects. It is extremely difficult to render transparency effects using the rasterization algorithm, since the calculation of transparency directly depends on the rendering order. To obtain good results, you need to sort the transparent polygons in the order of furthest from the camera to closest, and only then render.
But in practice, this task is too heavy from a computational point of view, and transparency errors are also possible, since the sorting is done on polygons, not pixels. There are several technologies that allow you to bypass scene polygon sorting (such as depth peeling and A-buffers), but at the moment none of them can be called saving. At the same time, the ray tracing algorithm allows you to elegantly handle transparency effects.
Properly handling transparency effects using a rasterizer requires the use of complex algorithms such as A-buffers. Click on the picture to enlarge.
Another important advantage is the calculation of shadows. In the world of rasterization, shadow mapping technology has become the standard. But it has several problems, such as “ladders” on the circuits and the amount of memory used. The ray tracing algorithm solves the shadow problem very elegantly, without resorting to complex algorithms, using the same primitive object and without requiring additional memory.
Finally, another strong advantage of the ray tracing method is its native ability to work with curved surfaces. Modern GPUs have had support for curved surfaces for several years now (it appears and disappears as new drivers and new architectures are released). But if rasterizers have to do an initial tessellation pass to create the triangles (which is the only primitive the rasterization engine can work with), then a ray tracing engine can simply work with the intersection of rays, without a precise mathematical definition of the surface.
Myths about ray tracing
But ray tracing still shouldn't be idealized, so it's time to break down some of the myths surrounding this algorithm.
Let's start with the fact that many gamers consider the ray tracing algorithm to be fundamentally better than rasterization, since it is used in films. This is wrong. Most synthetic/hand-drawn films (like all Pixar films) use an algorithm called REYES, which is based on rasterization. Pixar only added ray tracing to its RenderMan rendering engine later, during the production of Cars. But even for this film, ray tracing was used selectively so as not to overwhelm existing computing power. Prior to this project, Pixar used a plug-in to make limited use of ray tracing, such as ambient occlusion (AO) shading effects.
Click on the picture to enlarge.
The second common myth among ray tracing advocates concerns the complexity of the scenes that ray tracing and rasterization can render. To understand, we need to take a closer look at each algorithm.
Below is how the rasterization algorithm works on each triangle in the scene.
- A set of pixels is determined that covers each triangle;
- For each involved pixel, its depth is compared with the depth of the neighboring pixel.
The main limitation of the rasterization method concerns the number of triangles. The algorithm has complexity O(n), where n is the number of triangles. Algorithm in in this case has linear complexity depending on the number of triangles, since for each frame a list of triangles to be processed is compiled, one by one.
In contrast, the ray tracing algorithm works as follows.
For each frame pixel:
- a ray is drawn to determine which triangle is the closest;
- For each triangle, the distance from the triangle to the image output plane is calculated.
As you can see, the processing sequence has become reversed. In the first case, we took each polygon and looked at which pixels it covered. And in the second case, we took each pixel and looked at which polygon corresponded to it. Therefore, you might think that the ray tracing method is less dependent on the number of polygons than the rasterization method, since the number of polygons does not affect the main loop. But in practice this is not the case. In fact, to determine which triangle will intersect the ray, we need to process all the triangles in the scene. Here, of course, defenders of the ray tracing method will say that it is not necessary to process all the triangles of the scene with each ray. If we use the appropriate type of data structure, it is very easy to organize the triangles so that only a small percentage of them are tested with each ray, which means that the ray tracing method has a complexity of O(log n), where n is the number of polygons.
Yes, the arguments can be considered true. But ray tracing advocates are a little disingenuous in that the same is true for rasterization. Game engines BSP trees (binary space partitioning) and other methods have been used for many years to limit the number of polygons that need to be calculated for each frame. Another controversial point is that such structures are most effective for static data. All we need is to calculate the data once, and then simply provide access to it, and this gives very good results. But what to do with dynamic data? In this case, the data will have to be recalculated for each image, and there are no miraculous formulas for this. You still have to study each polygon.
Simple algorithm?
The last myth concerns the natural simplicity and elegance of the ray tracing algorithm. Of course, a ray tracing algorithm can be written in a few lines of code (some algorithms fit on one side of a business card), but a high-performance ray tracing algorithm is a completely different matter.
David Luebke, an engineer at nVidia, made the following comment that perfectly reflects the reality: "Rasterization is fast, but you need to think carefully about how to do complex visual effects. Ray tracing supports complex visual effects, but you need to think carefully about how make it fast."
Minimal ray tracing code written by Paul Heckbert to fit on a business card. Click on the picture to enlarge.
All you need to do is read a few articles about the optimizations that need to be made to the ray tracing algorithm to appreciate what Luebke said. For example, the most powerful ray tracing algorithms do not process rays independently; they use what are called ray sets, which allows performance optimization with rays that have the same origin and direction. This optimization is great for single instruction many data (SIMD) function blocks inside CPUs and GPUs, and is also very effective for core rays with some degree of coherence or shadow rays. But, on the other hand, the optimization is no longer suitable for refraction or reflection rays.
Moreover, as Daniel Pohl points out in in his article about Quake Wars RT, using ray sets can become problematic with transparent textures (the famous alpha textures used for trees), because if all the rays in a set do not behave the same way (some hitting the surface, others passing through it), then the additional overhead can become much higher greater than the benefits of optimizations provided by using ray sets.
Visualization of the "cost" of rendering each pixel, with red pixels being the most "expensive". As you can see, rendering trees is very expensive in the ray-traced version of Quake Wars. Click on the picture to enlarge.
Finally, as we already mentioned, ray tracing requires a suitable data structure to store the different elements of the scene, and it is this structure that will play a determining role in the final performance. But choosing and then working with such a data structure is not as simple as it seems at first glance. Some structures have best characteristics for static data, while others can be updated faster for dynamic data or take up less memory. As usual, it all comes down to finding an acceptable compromise. There are no miracles.
Therefore, as we see, the ray tracing algorithm cannot always be called the ideal of simplicity and elegance, as some believe. To get good performance from a ray tracing algorithm, you need to find no less non-trivial programming solutions than in the case of obtaining complex visual effects in the rasterization method.
Now that we've cleared up some of the myths surrounding ray tracing, let's look at the real issues that come with this technology.
And we'll start with the main problem associated with this rendering algorithm: its slowness. Of course, some enthusiasts will say that this is no longer a problem, since the ray tracing algorithm is highly parallelizable and the number of processor cores is increasing every year, so we should see a linear increase in ray tracing performance. Additionally, research into optimizations that can be applied to ray tracing is still in its infancy. If you look at the first 3D accelerators and compare them with what is available today, there is indeed reason for optimism.
However, this point of view does not take into account important point: The interesting thing about the ray tracing method is the secondary rays. In practice, calculating an image with only primary rays will not provide much improvement in image quality compared to the classic algorithm with a Z-buffer. But the problem with secondary beams is that they have absolutely no coherence (codirectionality). When moving from one pixel to another, completely different data must be calculated, which negates all the usual caching techniques that are very important for good performance. This means that the calculation of secondary rays is very dependent on the memory subsystem, in particular, on its delays. This is the worst-case scenario possible, since of all the memory characteristics, latency has improved the least over time. last years, and there is no reason to believe that the situation will improve in the foreseeable future. It's quite easy to increase memory bandwidth by using multiple chips in parallel, but the latencies will still remain the same.
For video cards, memory latency (latency) decreases much more slowly than bandwidth (bandwidth) increases. If the latter improves by a factor of 10, then the delays improve only by a factor of two.
The reason for the popularity of GPUs lies in the fact that the creation of hardware specializing in rasterization turned out to be very effective solution. With rasterization, memory accesses are performed coherently (in parallel), regardless of whether we are working with pixels, texels, or vertices. Therefore, small caches, complemented by serious memory bandwidth, will ideal solution for superior performance. Of course, the increase bandwidth is very expensive, but this solution is quite suitable if it pays off. In contrast, today there are no solutions to speed up memory access when computing multiple rays. This is the reason why ray tracing will never be as efficient as rasterization.
Another common problem with ray tracing concerns anti-aliasing (AA). The rays are carried out as a simple mathematical abstraction, and actual size they don't take into account. The triangle intersection test is a simple Boolean function that gives a yes or no answer, but does not give details such as "the ray intersects the triangle 40% of the way." A direct consequence of this effect will be the appearance of “ladders”.
To solve this problem, several technologies have been proposed, such as beam tracing and cone tracing, which take into account the thickness of the beams, but their complexity prevents effective implementation. And the only technology that can give good results is the calculation of more rays than there are pixels, that is, supersampling (rendering at a higher resolution). It’s hardly worth mentioning once again that this technology is much more computationally expensive than the multisampling used in modern GPUs.
Hybrid rendering engine?
If you have read the entire article up to this point, you are probably already thinking that ray tracing cannot yet replace rasterization, but perhaps it is worth mixing the two technologies together? And at first glance it seems that the two technologies complement each other. It's easy to imagine rasterizing triangles to define what's visible, taking advantage of the technology's excellent performance, and then applying ray tracing to just some surfaces, adding realism where it's needed, such as adding shadows or getting good reflections and transparency. Actually, Pixar used this approach for the cartoon "Cars". Geometric models are created using REYES, and ray tracing is used "on demand" where certain effects need to be simulated.
For Cars, Pixar used a hybrid rendering engine that combined REYES for rendering and on-demand ray tracing for reflections and ambient occlusion. Click on the picture to enlarge.
Unfortunately, although this method sounds promising, hybrid solutions are not so easy to implement. As we have already seen, one of the important disadvantages of the ray tracing method is the need to organize the data structure in such a way as to limit the number of checks for the intersection of rays and objects. And using a hybrid model instead of pure ray tracing doesn't change that. It is necessary to organize the data structure along with all the disadvantages that come with it. For example, suppose that the ray tracing method is based on static data, but the dynamic data is rendered through rasterization. But in this case we lose all the benefits of ray tracing. Since there is no dynamic data for ray tracing, you won't be able to force objects to cast shadows or see reflections.
Moreover, when it comes to performance, the biggest problem is the memory access associated with secondary rays, and these rays are exactly what we need in our hybrid rendering engine. So the performance gain won't be as big as you might initially expect. Since most of the rendering time will be spent on secondary rays, the gain from not rendering the main rays will be negligible.
In other words, by trying to combine the advantages of both methods, we inevitably combine their disadvantages, losing the elegance of the ray tracing method and the high performance of rasterization.
As we have mentioned several times in our article, there are many problems to be solved before ray tracing becomes a a worthy alternative rasterization in real-time rendering. And if you think about it, will this method become a panacea for all ills? The benefits of ray tracing are not so revolutionary as to justify the significant performance penalty. The algorithm's strengths relate to reflections and transparency, since these two effects are the most difficult to achieve with existing rasterization algorithms. But, again, is this such a serious drawback? The world around us does not consist entirely of very transparent or shining objects, so our vision may well be satisfied with a rough approximation.
If you look at the latest car simulators, for example, Gran Turismo and Forza, you can clearly see quite satisfactory rendering quality, even if the reflections on the body are completely false. And the exact reflection of the rear view mirror on the paint can hardly be considered sufficient to recognize another step towards photorealism.
In reality there are no reflections. For example, the side view mirror does not reflect on the car body. But do you need a "fair" rendering of the Audi R8 using ray tracing? Click on the picture to enlarge.
Most enthusiasts believe that ray tracing inherently produces a better image than rasterization - but they often base their opinion on the image produced by an offline, non-real-time engine. However, the results of such engines are much better than the capabilities of modern games. Additionally, there is some confusion around ray tracing. Enthusiasts often compare photorealistic images, which are produced by a combination of several techniques, to rasterization, such as ray tracing for direct reflections, radiosity for diffuse reflection, photon mapping for caustics, etc. All these technologies combine to provide the most photorealistic quality possible.
To achieve photorealistic rendering, you need to combine several technologies. Ray tracing alone is not sufficient to simulate complex interactions between materials different types and light. Click on the picture to enlarge.
In its basic version, ray tracing, when considering existing real-time implementations, is only suitable for ideal reflections and hard (sharp) shadows. Doom 3 proved a few years ago that it was possible to create a reliable 3D engine that could handle dynamic shadows and rasterization perfectly, but in retrospect, the game also showed that hard shadows were not realistic.
Click on the picture to enlarge.
To create soft shadows or diffuse reflections (the kind you see on textured metal, for example), more advanced ray tracing techniques such as path tracing and or distributed ray tracing are required. But such techniques require a significantly larger number of rays, so they are still poorly suited for real time.
Some users believe that sooner or later so much processing power will be available that the performance advantage of rasterization will no longer be a decisive factor. Due to the law of diminishing returns, the performance gains from rasterization will quickly be forgotten in favor of the elegance of ray tracing. In much the same way as before, the productivity benefits of assembly language coding were forgotten, which turned out to be insufficient to outweigh the benefits of high-level languages.
However, this is unlikely to convince us. In any case, we are still far from the time when we can sacrifice performance for elegance and simplicity. Just look at what has happened in the last 10 years in the world of offline rendering. While one frame of Toy Story took an average of two hours to render, one frame of Ratatouille took six and a half hours, despite the increased processing power between the two films. more than 400 times. In other words, the more processing power and resources you provide to computer artists, the faster they consume them.
If even a company like Pixar, which can afford to dedicate several hours of computation to creating a single frame, decides to use ray tracing only occasionally due to the negative impact on performance, this means that the time before we will have sufficient processing power in 3D -real-time games to perform all rendering using ray tracing are very, very far away. And in the future, enthusiasts will certainly have somewhere to spend such computing power.
Ray tracing methods are currently considered the most powerful methods creating realistic images. The versatility of tracing methods is largely due to the fact that they are based on simple and clear concepts that reflect our experience of perceiving the world around us.
Let's look at how an image is formed. The image is produced by light entering the camera. Let's release many rays from the light sources. Let's call them primary rays. Some of these rays will fly away into free space, and some will hit objects. The rays can be refracted and reflected on them. In this case, part of the beam energy will be absorbed. Refracted and reflected rays form many secondary rays. Then these rays will again be refracted and reflected and form a new generation of rays. Eventually, some of the rays will hit the camera and form an image.
There are algorithms that work according to this algorithm. But they are extremely ineffective, since most of the rays emanating from the source do not reach the camera. And an acceptable picture is obtained if you trace big number rays, which will take a very long time. This algorithm is called direct ray tracing.
The reverse ray tracing method can significantly reduce the search for light rays. This method was developed in the 1980s by Whitted and Kaye. In this method, rays are tracked not from sources, but from the camera. Thus it is traced certain number rays equal to the image resolution.
Let's assume that we have a camera and a screen located at a distance h from it. Let's divide the screen into squares. Next, we will take turns drawing rays from the camera to the center of each square (primary rays). Let's find the intersection of each such ray with scene objects and select the one closest to the camera among all intersections. Next, by applying the desired lighting model, you can obtain an image of the scene. This is the simplest ray tracing method. It only allows you to cut off invisible edges.
But we can go further. If we want to simulate phenomena such as reflection and refraction, we need to launch secondary rays from the closest intersection. For example, if the surface reflects light and it is perfectly flat, then it is necessary to reflect the primary ray from the surface and send a secondary ray in this direction. If the surface is uneven, then it is necessary to launch many secondary rays. This is not done in the program, as this will greatly slow down the tracing.
If the object is transparent, then it is necessary to construct a secondary ray such that when refracted it produces the original ray. Some bodies may have the property of diffuse refraction. In this case, not one, but many refracted rays are formed. As with reflection, I neglect this.
Thus, the primary ray, having found an intersection with the object, is generally divided into two rays (reflected and refracted). Then these two rays are divided into two more and so on.
The main reverse ray tracing procedure in my program is the Ray procedure. It has the following structure:
If the beam generation is equal to the maximum recursion depth, then we return the average brightness for all components. If not, then move on
We determine the nearest triangle with which the ray intersects.
If there is no such triangle, return the background color; if there is, move on.
If the surface with which the intersection was found is reflective, then we form a reflected ray and call the Ray procedure recursively with the ray generation increased by 1.
If the surface with which the intersection was found refracts, then we form a refracted ray and call the Ray procedure recursively with the ray generation increased by 1.
We determine the final illumination of the pixel, taking into account the location of the sources, the properties of the material, as well as the intensity of the reflected and refracted beam.
I've already discussed a number of limitations of the tracing method when we talked about diffuse refraction and uneven mirrors. Let's look at some others.
Only special objects - light sources - can illuminate the scene. They are point-like and cannot absorb, refract or reflect light.
The properties of a reflective surface consist of two components - diffuse and specular.
With diffuse reflection, only rays from light sources are taken into account. If the source illuminates a point through a mirror (with a bunny), then it is considered that the point is not illuminated.
Specularity is also divided into two components.
reflection - takes into account reflection from other objects (not light sources)
specular - takes into account glare from light sources
The tracing does not take into account the dependences on the wavelength of light:
refractive index
absorption coefficient
reflection coefficient
Since I'm not modeling diffuse reflection and refraction, I won't be able to get backlighting. Therefore, we introduce minimum background illumination. Often it simply allows you to significantly improve image quality.
The tracing algorithm allows you to draw very high-quality shadows. This will not require much reworking of the algorithm. You'll have to add something to it. When calculating the illumination of the points, it is necessary to place a “Shadow Front” in each of the light sources. The "shadow front" is a ray that checks whether there is anything between the point and the source. If there is an opaque object between them, then the point is in the shadow. This means that this source does not contribute to the final illumination of the point. If a transparent object is lying, then the intensity of the source decreases. Drawing shadows is very time-consuming. So, in some situations they are disabled.
My program has the ability to enable image smoothing. Antialiasing is about determining the color of a pixel. Not one ray, but four, is launched and the average color value of these rays is determined. If it is necessary to find the color of a pixel (i,j), then 4 rays are sent to points on the screen plane with coordinates (i-0.25,j-0.25), (i-0.25,j+0.25), (i+0.25,j-0.25) , (i+0.25,j+0.25).
At Gamescom 2018 Nvidia announced a series of video cards Nvidia GeForce RTX, which will support Nvidia RTX real-time ray tracing technology. Our editors figured out how this technology will work and why it is needed.
What is Nvidia RTX?
Nvidia RTX is a platform containing a number of useful tools for developers who open access to a new level of computer graphics. Nvidia RTX is only available for the new generation Nvidia video cards GeForce RTX, built on the Turing architecture. The main feature of the platform is the availability real-time ray tracing(also called ray tracing).
What is ray tracing?
Ray tracing is a feature that allows you to simulate the behavior of light, creating believable lighting. Now in games the rays do not move in real time, which is why the picture, although it often looks beautiful, is still not realistic enough - the technologies used now would require a huge amount of resources for ray tracing.
This is corrected by the new series of Nvidia GeForce RTX video cards, which have enough power to calculate the path of rays.
How it works?
RTX projects rays of light from the player's (camera) point of view onto the surrounding space and thus calculates where the color pixel should appear. When the rays hit something, they can:
- Reflect - this will provoke the appearance of a reflection on the surface;
- Stop - this will create a shadow on the side of the object that the light did not hit
- Refract - this will change the direction of the beam or affect the color.
This has prompted Nvidia to introduce additional cores into GeForce RTX graphics cards, which will take on most of the load, improving performance. They are also equipped with artificial intelligence, whose task is to calculate possible mistakes during the tracing process, which will help to avoid them in advance. This, as the developers say, will also increase the speed of operation.
And how does ray tracing affect quality?
During the presentation of video cards, Nvidia demonstrated a number of examples of ray tracing: in particular, it became known that some upcoming games, including Shadow of the Tomb Raider and Battlefield 5 will run on the RTX platform. This function, however, will be optional in the game, since tracing requires one of the new video cards. The trailers shown by the company during the presentation can be viewed below:
Shadow of the Tomb Raider, which will be released on September 14 this year:
Battlefield 5, which will be released on October 19:
Metro Exodus, scheduled for release on February 19, 2019:
Control, the release date of which is still unknown:
Along with all this, Nvidia, what other games will receive the ray tracing feature.
How to enable RTX?
In view of technical features With this technology, trace tracing will only be supported by video cards with Turing architecture - currently available devices cannot cope with the amount of work that tracing requires. At the moment, the only video cards with this architecture are the Nvidia GeForce RTX series, models of which are available for pre-order from 48,000 to 96,000 rubles.
Does AMD have analogues?
AMD has its own version of real-time ray tracing technology, which is present in their Radeon ProRender engine. The company announced its development back at GDC 2018, which took place in March. The main difference between AMD's method and Nvidia's is that AMD gives access not only to tracing, but also to rasterization, a technology that is now used in all games. This allows you to both use tracing, getting better lighting, and save resources in places where tracing would be an unnecessary load on the video card.
The technology that will run on the Vulkan API is still in development.
As Nvidia stated during its presentation, mastering RTX technology will significantly improve the graphics component of games, expanding the set of tools available to developers. However, it is too early to talk about a general graphics revolution - not all games will support this technology, and the cost of video cards that support it is quite high. The presentation of new video cards means that progress in graphic details there is, and over time it will grow and grow.
Backtrace Method
Method backtrace rays allows you to significantly reduce the overkill of light rays. The method was developed in the 80s, the fundamental works are considered Whitted And Kaya. According to this method, rays are tracked not from light sources, but in the opposite direction - the observation point. This way, only those rays that contribute to the formation of the image are taken into account.
Let's look at how you can get a raster image of some three-dimensional scene using the backtracing method. Let's assume that the projection plane is divided into many squares - pixels. Let us choose a central projection with a vanishing center at a certain distance from the projection plane. Let's draw a straight line from the vanishing center through the middle of the square (pixel) of the projection plane. This will be the primary back-trace ray. If the straight line of this ray hits one or more objects in the scene, then select the closest intersection point. To determine the color of an image pixel, you need to take into account the properties of the object, as well as what light radiation falls on the corresponding point of the object.
If the object is mirrored (at least partially), then we construct a secondary ray - the incident ray, considering the previous, primary traced ray to be the reflection ray. Above, we considered specular reflection and obtained formulas for the vector of the reflected ray based on the given normal and incident ray vectors. But here we know the vector of the reflected ray, but how can we find the vector of the incident ray? To do this, you can use the same specular reflection formula, but defining the required vector of the incident ray as the reflected ray. That is, the opposite reflection i.
For an ideal mirror, it is then sufficient to trace only the next point of intersection of the secondary ray with some object. An imperfect mirror greatly complicates tracing - you need to trace not one, but many incident rays, and take into account the contribution of radiation from other objects visible from a given point.
If the object is transparent, then you need to build new beam, such that, when refracted, would give the previous traced ray. Here you can also take advantage of reversibility, which is also true for refraction.
If an object has the properties of diffuse reflection and refraction, then, in the general case, as for a non-ideal mirror, it is necessary to trace the rays coming from all existing objects. For diffuse reflection, the intensity of the reflected light is known to be proportional to the cosine of the angle between the ray vector from the light source and the normal. Here, the light source can be any object visible from a given point that can transmit light energy.
When it turns out; that the current backtracing ray does not intersect any object, but goes into free space, then the tracing for this ray ends.
Rice. 14.1 Example of reverse ray tracing.
Backward ray tracing in the form in which we considered it here, although it reduces the search, does not allow us to get rid of the infinity of the number of analyzed rays. In fact, this method allows you to immediately obtain a single primary backtracing ray for each image point. However, there can already be an infinite number of secondary reflection rays. So, for example, if an object can reflect light from any other object, and if these other objects are large enough, then which points of the emitting objects need to be taken into account to construct the corresponding rays, for example, in diffuse reflection? Obviously, all the points.
How the ray tracing method works:
1. An imaginary ray is emitted from the observer's eye through a certain pixel on the screen and its path is tracked until it intersects the object.
2. A reflected ray is emitted from the first point of intersection of the ray with the sphere. Let the surface be opaque. Then we don’t draw refracted rays. We denote the shadow ray from the intersection point to the light source. Since this ray does not intersect another opaque surface, the light source directly affects the intensity of illumination at a given point.
3. Let the reflected ray intersect another object, this time a translucent sphere that reflects and transmits light. Reflected and refracted rays are emitted along with a shadow ray going to the light source. The transmitted ray changes its direction before and after entering the sphere in accordance with the effect of refraction.
4. Let the point where the ray intersects the sphere not be directly illuminated by the source, because the path of the shadow ray is blocked by an opaque surface. If the scene contained multiple light sources, then shadow rays would have to be shot at each of them.
5. The influence of all rays generated explicitly or implicitly by the initial ray is summed up and the result determines the RGB value of that point.
INTRODUCTION
There are several methods for generating realistic images, such as forward ray tracing (photon tracing) and reverse ray tracing.
Ray tracing methods are considered to be the most powerful and universal methods creating realistic images. There are many examples of the implementation of tracing algorithms for high-quality display of the most complex three-dimensional scenes. It can be noted that the universality of tracing methods is largely due to the fact that they are based on simple and clear concepts that reflect our experience of perceiving the world around us.
The objects around us have the following properties in relation to light:
radiate;
reflect and absorb;
pass through themselves.
Each of these properties can be described by a certain set of characteristics.
Radiation can be characterized by intensity and spectrum.
The property of reflection (absorption) can be described by the characteristics of diffuse scattering and specular reflection. Transparency can be described by intensity attenuation and refraction.
Rays of light emanate from points on the surface (volume) of emitting objects. You can call such rays primary - they illuminate everything else. Countless primary rays emanate from radiation sources in various directions. Some rays go into free space, and some hit other objects.
As a result of the action of primary rays on objects, secondary rays arise. Some of them end up on other objects. Thus, being reflected and refracted many times, individual light rays arrive at the observation point. Thus, the image of the scene is formed by a certain number of light rays.
The color of individual image points is determined by the spectrum and intensity of the primary rays of the radiation sources, as well as the absorption of light energy in objects encountered on the path of the corresponding rays.
Direct implementation of this ray imaging model seems difficult. You can try to construct an algorithm for constructing an image using the indicated method. In such an algorithm, it is necessary to provide an enumeration of all primary rays and determine those that hit the objects and the camera. Then iterate over all secondary rays, and also take into account only those that hit objects and the camera. And so on. This algorithm is called direct ray tracing. Main disadvantage This method involves a lot of unnecessary operations associated with the calculation of rays, which are then not used.
1. REVERSE RAY TRACING
This work is devoted to this method of generating realistic images.
The reverse ray tracing method can significantly reduce the search for light rays. The method was developed in the 80s; the works of Whitted and Kay are considered fundamental. According to this method, rays are tracked not from light sources, but in the opposite direction - from the observation point. This way, only those rays that contribute to the formation of the image are taken into account.
The projection plane is divided into many pixels. Let us choose a central projection with a vanishing center at a certain distance from the projection plane. Let's draw a straight line from the vanishing center through the middle of the pixel of the projection plane. This will be the primary back-trace ray. If this ray hits one or more objects in the scene, then select the closest intersection point. To determine the color of an image pixel, you need to take into account the properties of the object, as well as what light radiation falls on the corresponding point of the object.
If the object is mirrored (at least partially), then we construct a secondary ray - the incident ray, considering the previous, primary traced ray to be the reflection ray.
For an ideal mirror, it is then sufficient to trace only the next point of intersection of the secondary ray with some object. An ideal mirror has a perfectly smooth polished surface, so one reflected ray corresponds to only one incident ray. The mirror can be darkened, that is, absorb part of the light energy, but the rule still remains: one ray is incident, one is reflected.
If the object is transparent, then it is necessary to construct a new ray, one that, when refracted, would produce the previous traced ray.
For diffuse reflection, the intensity of the reflected light is known to be proportional to the cosine of the angle between the ray vector from the light source and the normal.
When it turns out that the current backtracing ray does not intersect any object, but goes into free space, then the tracing for this ray ends.
At practical implementation The traceback method introduces limitations. Some of them are necessary to be able to solve the problem of image synthesis in principle, and some restrictions can significantly improve the performance of tracing.
Limitations when implementing tracing
Among all types of objects, we will highlight some, which we will call light sources. Light sources can only emit light, but cannot reflect or refract it. We will consider only point light sources.
The properties of reflective surfaces are described by the sum of two components - diffuse and specular.
In turn, specularity is also described by two components. The first (reflection) takes into account reflection from other objects that are not light sources. Only one mirrored ray r is constructed for further tracing. The second component (specular) means glare from light sources. To do this, rays are directed to all light sources and the angles formed by these rays with the specularly reflected back-tracing ray (r) are determined. In specular reflection, the color of a point on a surface is determined by the intrinsic color of what is being reflected.
With diffuse reflection, only rays from light sources are taken into account. Rays from specularly reflective surfaces are IGNORED. If the beam directed at a given light source is blocked by another object, then this point of the object is in the shadow. With diffuse reflection, the color of an illuminated point on a surface is determined by the surface's own color and the color of the light sources.
For transparent objects, the dependence of the refractive index on wavelength is not taken into account. (Sometimes transparency is modeled without refraction at all, that is, the direction of the refracted ray t coincides with the direction of the incident ray.)
To take into account the illumination of objects by light scattered by other objects, a background component (ambient) is introduced.
To complete the tracing, a limit on the number of iterations (recursion depth) is introduced.
Conclusions from the traceback method
Advantages:
The versatility of the method, its applicability for the synthesis of images of rather complex spatial schemes. Embodies many laws of geometric optics. Various projections are simply implemented.
Even truncated versions of this method allow one to obtain fairly realistic images. For example, if we limit ourselves to only the primary rays (from the projection point), then this results in the removal of invisible points. Tracing just one or two secondary rays gives shadows and specular transparency.
All coordinate transformations are linear, so it's quite easy to work with textures.
Flaws:
Problems with modeling diffuse reflection and refraction.
For each point in the image, many computational operations must be performed. Tracing is one of the slowest image synthesis algorithms.
2. DESIGN PART
Algorithms.
Backward ray tracing.
Rice. 1 - Block diagram of the recurrent inverse ray tracing algorithm
ray tracing programming language
In this program, the backtracing algorithm is implemented in a recurrent manner. The primary ray intensity calculation function calls itself recurrently to find the reflected and refracted ray intensities.
Algorithm:
To calculate the color of each pixel in the frame buffer, do the following:
Find pixel coordinates in the world coordinate system.
Find the coordinates of the primary ray.
Start the primary beam intensity calculation function.
Find intersections of the ray with all scene primitives and select the closest one.
If no intersection is found, then the beam has gone into free space.
To calculate color, we take the total intensity to be equal to the background intensity. Go to step 12. If an intersection is found, go to step 6.
We calculate the “local” color intensity of the object to which the intersection point belongs. By “local” intensity we mean the intensity taking into account the intensity of diffusely reflected light and the intensity of glare.
If the material reflects light only diffusely, then we consider the intensities of reflected and refracted light to be zero. Go to step 12. Otherwise, go to step 8.
If the maximum recursion depth is reached, then take the intensities of reflected and refracted light to be zero. Go to step 12. Otherwise, go to step 9.
Calculate the vector of the reflected ray. Running a recursion to find the intensity of the reflected beam.
Calculate the vector of the refracted ray. Running a recursion to find the intensity of the refracted ray.
Calculation of total color intensity. Total intensity includes scattered light intensity, local intensity, and reflected and refracted ray intensities.
Return to the point where the ray intensity calculation function was called.
If the primary ray was being calculated, then a pixel of the calculated color is placed in the frame buffer. Let's move on to calculating the next pixel of the frame buffer. If the reflected (refracted) ray was being calculated, then the calculated intensity will be accepted as the intensity of the reflected (refracted) ray at the previous recursion step.
Construction of shadows.
Solid shadows.
To construct solid shadows in the tracing algorithm, at the stage of calculating the “local” color intensity at an object point, the “visibility” of each light source from this point is checked.
The principle of operation of the algorithm.
A beam is constructed from the point being checked, directed at the light source.
A search is made for intersections of this ray with scene primitives between the point being checked and the source.
If at least one intersection is found, then the point being checked is in the shadow. When calculating its color, the source for which the test was carried out is not taken into account.
verifiable source.
This method of finding shadows gives an acceptable result as long as there are no transparent objects in the scene. However, the solid black shadow of the glass does not look realistic. Glass transmits some light, so the intensity of the obscured source must be taken into account when calculating the light intensity at a point on an object, but it must be attenuated as light passes through the glass.
Mathematical and physical background of the inverse ray tracing algorithm.
Lighting.
The light intensity is the sum of the intensity of the background illumination of the scene, the intensity of the diffusely reflected light from the sources, the intensity of glare from the sources (“local” illumination characteristics), the intensity of the specularly reflected beam and the intensity of the refracted beam, if any.
The backlight intensity (IA) is set by some constant.
The intensity of diffusely reflected light (ID) is calculated using the classic “cosine law”.
ID = IL cos α,(2.2.1.6)
where IL is the intensity of the light source, α is the angle between the normal to the surface and the direction towards the source.
If the scene is illuminated by several sources, Id is calculated for each of them and then summed.
IDi =Σ ILi cos αi.(2.2.1.7)
The source flare intensity (IS) is calculated according to the Phong model.
IS = IL cosp β,(2.2.1.8)
where IL is the intensity of the light source (0<=IL<=1), β - угол между отраженным лучом от источника света и направлением на точку, в которой расположена камера (центр проекции), p - некоторая степень от 1 до 200 -влияет на размытость блика. При
At small p values the highlight is more blurry.
As with calculating ID, when a scene is illuminated by multiple sources, IS is calculated separately for each source, and then the results are summed.
ISi =Σ ILi cosp β i.(2.2.1.9)
The specular reflected (IR) and refracted (IT) light intensities are calculated for the reflected and refracted rays in the next recursion step. If the recursion depth limit is reached, then these intensities are taken to be zero. From the intensity of IR, r percent is taken, and from IT - t = 1 - r (see the previous section).
In addition, the following coefficients are introduced: KD - diffuse surface reflection coefficient, KS - glare coefficient. - this coefficient is a characteristic of the roughness of the reflecting surface. The more uneven the surface, the less light is reflected from it specularly and the less light it transmits, and accordingly, the more light it reflects diffusely.<= KD <= 1.
At KD = 0, all light falling on the surface is reflected and refracted. KD = 1 - all light is reflected diffusely. The intensity of the diffusely reflected light and the intensity of the background illumination are multiplied by this factor. The intensities of specularly reflected and refracted light are multiplied by (1 - KD). - this coefficient is responsible for the brightness of the glare from the source. 0<=KS<=1.
When KS = 0 - the glare is not visible, when KS = 1 - the brightness of the glare is maximum.
Thus, the final formula for calculating the intensity of an object at any point will be as follows:
I = IAKD + Σ(ILiKDcos αi + ILiKScosp β i) + (1 - KD)(IRr + IT(1 - r)).(2.2.1.10)
It should be noted that the final intensity should not be greater than one. If this happens, then this point in the image will be overexposed. Its intensity must be reset to one.
To obtain a color image, it is necessary to carry out calculations separately for the red, green and blue components of light. The color of an image pixel will be calculated by multiplying each intensity component by a number that determines the maximum number of intensity gradations in the image. For a 32-bit image it is equal to 255 for each color (R, G, B).
255*IR,= 255*IG,= 255*IB.
Here IR (not to be confused with the intensity of specularly reflected light), IG, IB are the intensities of the three components of light at a point, obtained using the formula indicated above.
Coefficients KD, KS, p are individual characteristics of an object, reflecting its properties. In addition, there is one more coefficient - the absolute refractive index n. n = c / v, where c is the speed of light in a vacuum, v is the speed of light in the medium (inside the object). For absolutely opaque bodies, this coefficient is equal to ∞ (since the speed of light inside the body is zero). In the program to specify a completely opaque body, you need to set this coefficient >> 1 (about 10,000). In this case, the fraction of specularly reflected light r will tend to unity, and that of refracted light, respectively, to zero.
Calculation of normals.
In the tracing algorithm, normals to objects are needed to calculate reflected and refracted rays, as well as to determine illumination according to Phong's model.
This program contains three types of primitives from which the scene is built. These are polygon (triangle), ellipsoid and paraboloid. The last two were introduced for a more realistic simulation of a glass (it could have been built from polygons, but the model would have been rougher).
Calculation of the normal to a polygon (triangle).
Calculating the normal to a triangle reduces to a vector multiplication operation. Let triangle ABC be given by the coordinates of its three vertices:
XA, YA, ZA, XB, YB, ZB, XC, YC, ZC.
Let's calculate the coordinates of two vectors, for example AB and AC:
XB - XA,= XB - XA,
ZAB = XB - XA,(2.2.2.1)= XC - XA,= XC - XA,= XC - XA.
The coordinates of the normal vector will be calculated using the formulas:
YABZAC - YACZAB,= XABZAC - XACZAB,(2.2.2.2)= XABYAC - XACYAB.
There is no need to calculate the coordinates of the normal vector to the triangle each time in the tracing body, since the normals are the same at any point of the triangle. It is enough to count them once in the initializing part of the program and save them. When you rotate a triangle, you must also rotate its normal.
Calculation of the normal to a second order surface.
A second-order surface is given in the general case by an equation of the form:
Q(x,y,z) = a1x2 + a2y2 + a3z2 + b1yz + b2xz + b3xy + c1x +c2y +c3z + d =0.
But we will use a different form of recording. So the equation of the ellipsoid will look like this:
(x-x0)2/A2 + (y-y0)2/B2 + (z-z0)2 /C2 = 1,(2.2.2.3)
where x0, y0, z0 are the coordinates of the center of the ellipsoid, A, B, C are the lengths of the semi-axes of the ellipsoid.
Paraboloid equation:
(x-x0)2/A2 + (y-y0)2/B2 - (z-z0)2 /C2 = 1,(2.2.2.4)
where x0, y0, z0 are the coordinates of the center of the paraboloid, A, B, C are the lengths of the semi-axes of the paraboloid. The axis of the paraboloid is located along the Oz axis of the world coordinate system. To calculate the coordinates of the normal vector, it is necessary to calculate the partial derivatives with respect to x, y, z.
Coordinates of the ellipsoid normal vector:
Yn = 2(y-y0)/B2,= 2(z-z0)/C2.
The direction of the vector will not change if all its coordinates are divided by 2:
Xn = (x-x0)/A2,= (y-y0)/B2,(2.2.2.5)
Zn = (z-z0)/C2.
The coordinates of the paraboloid normal vector are calculated similarly:
Xn = (x-x0)/A2,= (y-y0)/B2,(2.2.2.6)
Zn = - (z-z0)/C2.
The normal for a second-order surface will have to be calculated directly in the tracing body, since the normals are different at different points of the figure.
Calculation of the reflected ray.
Let the vector of the incident ray S be given, and the normal vector N be known. We need to find the vector of the reflected ray R.
Let's consider the unit vectors R1, S1 and N1. Since the vectors of the normal, the incident ray and the reflected ray are in the same plane, we can write R1 + S1 = N`, where N` is the vector corresponding to the diagonal of the rhombus and coinciding in direction with the normal. The length of the vector N` is 2cosθ. Since the vector N` coincides in direction with N1, then
N` = N`2cosθ.
From here we find the unit vector of the reflected ray:
R1 = N1 2cosθ - S1 = N/|N| 2cosθ - S/|S|.
Let's find cosθ. This can be done using the scalar product of the vectors N and S:
Assuming that the desired vector of the reflected ray will have the same length as the vector of the incident ray, that is, R = |S| R1, we get
N 2NS/|N|2 - S.
This is a solution in vector form. Let's write down the coordinates of the vector:
2xN(xNxS+yNyS+zNzS)/(xN2+yN2+zN2) - xS,= 2yN(xNxS+yNyS+zNzS)/(xN2+yN2+zN2) - yS,(2.2.3.1)= 2zN(xNxS+yNyS +zNzS)/(xN2+yN2+zN2) - zS.
Calculation of a refracted ray.
Let two unit vectors be given: S1 is the vector of the incident ray, and N1 is the normal vector to the interface between the two media. Also, two refractive indices for these media must be known - n1 and n2 (or their ratio).
It is required to find the unit vector of the refracted ray T1. To solve this, let's perform some geometric constructions.
The required vector T1 is equal to the sum of two vectors:
Let's first find the vector NT. It is opposite in direction to the normal vector, and its length is |T1| cos α2 = cos α2 (since T1 is unit). Thus, NT = -N1 cos α2. It is necessary to determine cos α2. Let us write the law of refraction n1 sin α1 = n2 sin α2 in the form:
sin α2 = n sin α1,
where n = n1 / n2.
Let us use the identity cos2α + sin2α = 1. Then
cos α2 = √ 1 - sin2α2 = √ 1 - n2 sin2α1
cos α2 = √ (1 + n2 (cos2α1 - 1)
The value of cos α1 can be expressed through the scalar product of the unit vectors S1 and N1, that is, cos α1 = S1N1. Then we can write the following expression for the vector NT:
N1√1+n2((S1N1)2 - 1).
It remains to find an expression for vector B. It is located on the same line as vector A, and A = S1 - NS. Considering that NS is equal to N1 cos α1, then A = S1 - N1 cos α1. Since cos α1 = S1N1, then A = S1 - N1 (S1N1).
Since the length of vector A is equal to sin α1, and the length of vector B is equal to sin α2, then
|B|/|A| = sin α2/ sin α1 = n2/n1 = n,
where |B| = n |A|. Taking into account the relative position of vectors A and B, we obtain
NA =n(N1(S1N1) - S1).
Now we can write down the desired expression for the unit vector of the refractive ray T1:
T1 = nN1 (S1N1) - nS1 - N1√1 + n2 ((S1N1)2 - 1).(2.2.4.1)
Calculation of the intersection point with primitives.
In the tracing algorithm, to construct an image, it is necessary to calculate the points of intersection of rays with scene primitives. The ray is given by the parametric equation of a straight line. Any point on the ray satisfies the equation
R = A + Vt,(2.2.5.1)
where R is the radius vector of an arbitrary point belonging to the ray, A is the radius vector of the starting point of the ray, V is the direction vector of the ray, t is a parameter.
If the direction vector V is normalized, then the parameter t will be numerically equal to the distance from the starting point of the ray A to the point R.
You can write this equation in coordinate form:
x = x1 + at,= y1 + bt,(2.2.5.2)= z1 + ct.
Here x1, y1, z1 are the coordinates of the starting point of the ray in the rectangular Cartesian world coordinate system, a, b, c are the coordinates of the guiding vector of the ray.
Calculation of the point of intersection of a ray with a second-order surface.
To find the point of intersection of the ray given by equations (2) with the second-order surface given by equations (2.2.2.3) or (2.2.2.4):
(x-x0)2/A2 + (y-y0)2/B2 + (z-z0)2 /C2 = 1 (ellipsoid)
(x-x0)2/A2 + (y-y0)2/B2 - (z-z0)2 /C2 = 1 (paraboloid),
you need to substitute the corresponding ray equations into the second-order surface equation instead of x, y and z. As a result of this, after opening all the brackets and bringing similar ones, we obtain a quadratic equation with respect to the parameter t. If the discriminant of a quadratic equation is less than zero, then the ray and the second-order surface have no common intersection points. Otherwise, it will be possible to calculate two values for the parameter t. The discriminant can be equal to zero - this corresponds to the limiting case of the ray touching the surface, and we will get two coinciding values of the parameter t.
To find the coordinates of the points of intersection of the ray and the surface, it is enough to substitute the found values of the parameter t into the ray equations (2).
In the program, when two intersections are found, the closest one is selected for visualization. The closest intersection is determined by comparing the found parameters t. Closer to the observation point is the intersection that corresponds to the smaller parameter t. Here it should be noted that as a result of solving a quadratic equation, one or both values of the parameter t may turn out to be negative. This means that the point of intersection lies “behind” relative to the point of origin of the ray, on half of the straight line located “on our side” relative to the picture plane. Such points are discarded when searching for an intersection.
In addition, the program includes upper and lower cutting planes for each figure. Only the part of the figure lying between them is displayed.
To do this, after finding the intersection point, its z-coordinate is analyzed.
Calculation of the point of intersection of a ray with a polygon (triangle).
To calculate the point of intersection of the ray given by equations (2), it is necessary to first determine the point of intersection of this ray with the plane containing this triangle.
The plane equation looks like this:
Q(x, y, z) = Ax + By + Cz +D = 0.(2.2.5.3)
Here the coefficients A, B, C coincide with the coordinates of the normal to this plane. The normal coordinates of the plane coincide with the normal coordinates of the triangle, which we calculated at the stage of loading the scene.
To find the free term D, it is necessary to substitute the coordinates of any point of the triangle, for example, one of the vertices.
Ax -By - Cz.(2.2.5.4)
During program execution, the value of D will not change, so it is advisable to calculate it when initializing the scene and store it, like the coordinates of the normal. It is necessary to recalculate only when the position of the triangle changes.
Now, to find the intersection point, we substitute the ray equations (2) into
plane equation.
(x1 + at) + B (y1 + bt) + C (z1 + ct) + D = 0
Where do we get it from?
= - (Ax1 + By1 + Cz1 + D) / (Aa + Bb + Cc)(2.2.5.5)
If the denominator of this fraction is zero, then the ray is parallel to the plane in which the triangle lies. There is no intersection point.
To find the coordinates of the intersection point, you need to substitute the found value of the parameter t into the ray equations (2). Let's call the intersection point D. We get the coordinates xD, yD, zD.
Now you need to determine whether point D is inside the triangle. Let's find the coordinates of the vectors AB, BC, CA (A, B, C are the vertices of the triangle) and the coordinates of the vectors AD, BD, CD. Then we find three vector products:
nA = AB x AD,= BC x BD,(2.2.5.6)= CA x CD.
These vectors will be collinear. If all three vectors are co-directional, then point D lies inside the triangle. Codirectionality is determined by the equality of the signs of the corresponding coordinates of all three vectors.
The operation of checking whether point D belongs to triangle ABC can be speeded up. If we orthogonally project triangle ABC and point D onto one of the planes xOy, yOz or xOz, then the point’s projection falling into the triangle’s projection will mean that the point itself is falling into the triangle (of course, if it is already known that point D lies in the plane containing triangle ABC ). At the same time, the number of operations is noticeably reduced. So, to search for the coordinates of all vectors, you need to search for two coordinates for each vector, and when searching for vector products, you need to search for only one coordinate (the rest are equal to zero).
To check the co-directionality of the vectors obtained when calculating the vector product, you need to check the signs of this single coordinate for all three vectors. If all signs are greater than zero or less than zero, then the vectors are co-directional. If one of the vector products is zero, it corresponds to the case when point D falls on the line containing one of the sides of the triangle.
In addition, a simple dimensional test can be performed before calculating vectors and cross products. If the projection of point D lies to the right, to the left, above or below each of the projections of the vertices of the triangle, then it cannot lie inside.
It remains to add that for projection it is better to choose the plane on which the triangle’s projection area is larger. Under this condition, the case of projecting a triangle into a segment is excluded (provided that the triangle being tested is not degenerate into a segment). In addition, as the projection area increases, the probability of error decreases. To determine such a projection plane, it is enough to check the three coordinates of the triangle normal. If the z-coordinate of the normal is greater (in absolute value) x and y, then it must be projected onto the xOy plane. If y is greater than x and z, then we project onto xOz. In the remaining case - on yOz.
Description of data types. Program structure.
Description of program modules
List of modules:.h-description of the TTex structure.h-description of the TPlaneTex and TEllipsoidTex structures.h-description of the TPoint2d and TPoint3d structures.h-description of the TRGBColor structure.h-description of the TLamp class.h-description of the TCam class.h-description of the TPrimitive class. h-class description TFrstSurface.h-class description TScndSurface.h-class description TTriangle.h-class description TEllipsoid.h-class description TCylinder.h-class description THyperboloidVert.h-class description THyperboloidHor.h-class description TScene.h- description of the TTracer class
Implementing modules, program interface:
Options.h-module of the “Options” form
ExtraCamOptions.h-module of the “Camera Properties” form
MainUnit.h-module of the main form of the program
A brief description of the structures and classes of the program: TPoint3d - a structure that describes a point in the world coordinate system, TPoint2d - a structure that describes a point on a plane (in a texture) with integer coordinates, TRGBColor - a structure that describes a color in three components (RGB), TTex - a structure , describing the texture - contains the address of the pixel array and its dimensions, TPlaneTex - a structure describing the binding of the texture to the plane.
Contains three points to which the texture is attached: TLamp - a class that describes the light source.
Contains a TPoint3d coord object with source coordinates and three float variables (Ir, Ig, Ib) to store the intensity of three light components. TCam is a class that describes the camera.
Contains two angles (a, b) indicating the camera's viewing direction, the point at which the camera is pointing (viewP), and the distance from the camera to that point (r). TPrimitive is an abstract primitive class. Surfaces of the first and second order are inherited from it. TFrstSurface is an abstract class of a first-order surface. The triangle class is inherited from it.TScndSurface is an abstract second-order surface class. The ellipsoid and paraboloid classes are inherited from it. TTriangle is a triangle class. Contains three vertices of a triangle and its normal. TCylinder - class of a cylinder. THyperboloidVert - class of a single-sheet hyperboloid lying along the oZ axis. THyperboloidHor - class of a single-sheet hyperboloid lying along the oX axis. TEllipsoid - class of an ellipsoid. TScene - class of a scene. Contains information about all primitives, sources and camera. TTracer is a class responsible for constructing an image. Contains a buffer with a size of 400x400 pixels, in which the scene image is formed. Before generation, you need to call the function, passing it as a parameter a pointer to the scene that needs to be generated. To generate, call the render function.
All TPrimitive descendant classes provide the following functions: getT(TPoint3d p0, TPoint3d viewDir) - returns the distance from the start point (p0) of the viewDir ray to the nearest intersection point with the primitive.
void getTArr(float* arr, int& n, TPoint3d p0, TPoint3d viewDir) - fills the arr array with distances from the start point (p0) of the viewDir ray to the nearest all intersection points with the primitive.
void getNormal(TPoint3d& n, const TPoint3d& p) - returns the coordinates of the normal vector to the primitive at point p.
void getColor(TRGBColor& c, const TPoint3d& p) - returns the color of the primitive at point p (taking into account the texture).
3. TECHNOLOGICAL PART
Choosing a programming language.
When developing the program, the high-level programming language C++ was used as part of the visual programming environment CodeGear RAD Studio for Windows.
This language was chosen due to the fact that it provides the most convenient means for working with RAM and allows you to implement algorithms more efficiently compared to other high-level languages. Programs written in C++ run faster and take up less disk space.
Additionally, the visual programming environment CodeGear RAD Studio for Windows
provides a large number of standard visual components for creating an interface, and a number of libraries with various commonly used useful functions. Also, the author of the work has the greatest programming experience in this visual programming environment.
Options form. Lighting tab.
This tab contains tools for setting up scene lighting.
Source coordinates - coordinates in the world coordinate system of the light source selected in the drop-down list.
Source intensity - values of the three intensity components of the light source selected in the drop-down list.
Background intensity - values of the three components of background intensity.
Button “+” (next to the drop-down list) - adding a new light source.
Button “-” (next to the drop-down list) - deletes the light source selected in the drop-down list.
Options form. Camera tab.
This tab contains tools for configuring camera options.
Preview - here you can see an approximate appearance of the image before it is generated.
Navigation - camera position settings.
Additionally - when you click this button, a form appears
Camera properties with additional camera options.
Camera properties form.
Radius - the distance from the camera to the point at which it is aimed.
Radius change step - increment of the camera radius by pressing the “-” button once on the “Camera” tab of the “Options” form (or decreasing by pressing the “+” button once).
Options form. "materials" tab.
This menu displays the parameters of the material of the table on which the stage stands.
Color - the color of the table material.
Coef. diffuse reflection - coefficient Kd of the table material (see section 2.2.1).
Texture - if the checkbox is checked, a texture will be displayed on the table
Select texture - select an image file (*.bmp) that will be used as a table texture.
Advanced - when you click this button, the Table Properties form appears with additional parameters for the table material.
Table properties form.
Glare coefficient is the KS coefficient of the table material (see section 2.2.1).
The blur of the highlight is the exponent p of the table material.
Texture repetitions - how many times the table texture will be repeated along the OX and OY axes.
Options form. System tab.
On this tab you can configure the algorithms implemented in the program.
Recursion depth - this parameter sets the recursion depth in the tracing algorithm. With larger values of this parameter, the quality of the generated image improves.
ATTENTION!
The recursion depth STRONGLY affects the speed of image generation. It is not recommended to set this parameter to values greater than 10.
Antialiasing - enable the image smoothing algorithm.
Shadow type - select the shadow generation algorithm.
4. RESEARCH PART
The studies were carried out on a computer with the following configuration:
CPU - Intel Core 2 Duo T5850- 2048Mb DDR2 - Nvidia GForce 9300M 256Mb- Windows 7
4.1 Dependence of generation time on recursion depth
This test examined the dependence of image generation time on recursion depth. The studies were carried out for a scene illuminated by one light source. - generation time without a shadow in seconds. - generation time with a solid shadow in seconds. - recursion depth. 4.2 Dependence of generation time on the number of sources
4.3 Analysis of research results From the first study it is clear that the generation time increases greatly with the number of recursion levels. This fits well with the theory, because the number of rays increases with increasing recursion depth. It should be noted that for scenes with a small number of polygons there is no need to set large values for the maximum recursion depth, because the difference in the quality of the generated image will be insignificant. The second study showed that the dependence of generation time on the number of light sources is linear. From the obtained values, you can calculate the time required to calculate one source. On the machine on which the research was carried out, with a recursion depth of 5, this time is approximately 0.5 seconds. CONCLUSION
This program demonstrated the results of an algorithm for generating realistic images - reverse ray tracing. This implementation demonstrates the algorithm’s ability to construct images close to photorealistic. Tracing is one of the most advanced algorithms for generating realistic images. The resulting image quality is incomparably better than the image quality obtained using algorithms such as the Z-buffer. However, the requirements for computing power required to generate one image frame are much higher than in the same Z-buffer. Today, the real-time reverse ray tracing algorithm is used only for research purposes on super-powerful computers that are inaccessible to the average user. Of course, there are enthusiasts who create 3D games and other real-time graphics applications that are based on a reverse ray tracing algorithm, but as a rule they have extremely low FPS, or the basis of all objects in the scene is a sphere - the easiest to trace rays surface. But in order for this algorithm to become profitable for use in mass projects, such as 3D games, a noticeable breakthrough in the field of desktop computer hardware is necessary. Even using the example of computer games, one can easily see the redundancy of the reverse ray tracing algorithm. After all, the player, being captivated by the gameplay, is unlikely to admire the geometrically correct rendering of shadows and reflections of game objects. In this regard, approximate drawing using polygons is a significant advantage today, because it does not require a powerful computer, and the results are close to reality. It is also believed that the ray tracing algorithm is ideal for images of artificial objects with geometrically simple shapes, for example, cars, airplanes, buildings, etc. Generating objects such as a human face, animal fur or forest is an extremely difficult task for the algorithm, which increases So there are considerable requirements for the computer hardware. However, today you can already see research on the implementation of a reverse ray tracing algorithm in real time. As a rule, in such projects a car is used as a stage. But absolute photorealism of the image has already been achieved, and besides, it takes very little time to generate a single frame. Of course, these projects were implemented on super-powerful computers, but the day is not far off when such 3D applications will become available to the average user. BIBLIOGRAPHY
1. Rogers D. Algorithmic foundations of machine graphics: trans. from English - M.: Mir, 1989. - 512 p. Porev V. N. Computer graphics. - St. Petersburg: BHV-Petersburg, 2002. - 432 p. Nikulin E.A. Computer geometry and computer graphics algorithms. St. Petersburg: BHV-Petersburg, 2003. - 560 p. Angel E. Interactive computer graphics. - “Williams”, 2001. - 592 p.: ill. - Paral. Titus From English Avdeeva S.M., Kurov A.V. Algorithms for three-dimensional computer graphics: Textbook. - M.: Publishing house of MSTU im. N.E. Bauman, 1996. - 60 p.
