Prolog

Of this article is a continuation of the article “Raytracing in games”, which was released about a year ago on computer base. Since then, there was much progress getting closer by the real time ray tracing for desktop machines is.

&Lt; div > readers who are not yet as familiar with the details of raytracing will find here a detailed explanation of the procedure. < div >

Ray tracing is a Renderingtechnologie, which creates a two-dimensional image of a three-dimensional scene. This is done by the physical simulation of the distribution of light on the basis of radiation. For each pixel on the screen, the algorithm has an attempt a so-called “primary beam” from the perspective of the Viewer. The ray tracing algorithm then determines which object along the path of the beam is taken first.

At this point, a shader program is then invoked. The made object has, for example, reflective properties, an additional, so-called “reflection beam” in the reflected direction is shot as a result on the impact of the primary beam.

By “Shadow rays” you can determine, however, very simply, whether a certain pixel is lit, or whether he is in the shade. To one shoots out from the area to be simply a ray-casting light. This block is on his way through any obstacles, light can obviously get to this area. Otherwise, so the area with a blocking object in between, is in the shade.

The described in this report ray tracing approach is completely calculated on the CPU. The graphics card is used not for the production of the image. The final pixels of the video card to the monitor be moved only after rendering.

Another approach, to create a two-dimensional image of a three-dimensional scene is called “Rasterisierung”. This is it is the process that currently is used on graphics cards designed specifically for this algorithm and is used in almost any home computer, for example, games via the standard libraries such as DirectX or OpenGL to render.

Progress

After my last article on ray tracing in games on computer base was published, I worked more intensively with the scaling behavior of raytracing with rising number of CPU cores. To simulate a 16-core machine, I four quad-core PCs via Gigabit Ethernet interconnected and merged their computing power. Since my project used the raytracing library OpenRT of Saarland University at that time, which provides support for distributed rendering, this was easy to do.

OpenRT is a raytracing library (c/C++), which was developed by the computer graphics Department of the University of the Saarland. The syntax is nearly identical to that of OpenGL. For programmers, there is a free Linux version, which may be used for non-commercial purposes.

< div >

Scaling of raytracing with different number of CPU cores

The results were startling: when using a 16-core machine instead of a single-core machine, then the frame rate by a factor of 15.2 rises!

For all the attention, the previous article on ray tracing in games around the world had received, I was contacted by different companies with interest in this technology. One of them was Intel. At Intel, you told me, that you have a real-time Raytracer, which is about ten times faster than anything else, what has been published so far in this area. You could already read these numbers in a scientific article, but I still don’t trust them without seeing it with my own eyes. So I flew “Silicon Valley”, to Santa Clara, California, to get a live demonstration.

Now I’m at Intel of fixed staff scientists and further work on ray tracing. As is turns out, Intel to raytracing is among others so great interest, since the technology is so well suited for CPUs. The research area is part of a large program (called “Tera-Scale Computing”) with the aim of improving the scale of software from some on many cores (with many here several hundreds are meant).

Employment at Intel enabled me, 4 Quake: Raytraced with the new Intel Raytracer at several events, such as the Games Convention 2007 in Leipzig and the Intel Developer autumn 2007 in San Francisco, to show in Forum. On the latter event it was demonstrated even in the keynote by Justin Rattner (Intel CTO) on virtual worlds.

In HD resolution, we have a frame rate of about 90 frames per second on a dual-X 5365 machine show, with all 8 cores of the system to render have been fully exploited.

Ray tracing vs. Rasterisierung

I was often asked when ray tracing will be faster than Rasterisierung (the approach of the today’s GPUs for rendering). Now, there are already cases where raytracing is faster on a single desktop machine!

Example 1

Ray tracing uses “Acceleration structures”, which sort the entire geometry of a virtual world based on their position in space. There are many different approaches to do this. Most commonly used in raytracing are BSP-trees, kd-trees and bounding volume hierarchies (BVHs) uniform grids.

As noted in the introduction, one needs to find out when firing a beam which object along the path of the beam is taken first. The basic idea of the spatial subdivision with acceleration structures is described best with a small example: man is present, you have a four storey high building. There are four rooms on each floor, and the player is quite on the top floor in the room left:

< div >

Artistically high-quality representation of a building
with four floors with four rooms.

Through the tracking of the ray, we want to find out whether a specific piece of geometry or not taken. In the ray tracing: We shoot rays from the “camera” (the eyes of the player) with these “primary rays” determine what is visible and what is not. The naive approach would be to test whether they make these the rays just against the complete geometry. In our example, you would waste obviously very much computational. You think a little about the situation, it becomes quickly clear, that the player left in the very unlikely anything will see above, which, for example, in the space right at the bottom. Why should you test so at all the beam out, whether he geometry in this space right below meets? How can we best avoid these unnecessary computational?

Hierarchical, spatial acceleration structures, which you quickly can determine whether a particular area for rendering contains a relevant detail are the solution. This is not the case, so you can at once save a heap calculation work and use these in other areas where there is highly detailed, visible geometry.

One of the advantages is analytically by such ‘ hierarchical data structures, that they a “linear search” (every time everything against everything test) optimize to a “logarithmic search”. This means that one of the top level of the hierarchy, which includes the space of all geometry (in our case the whole building with 16 rooms), tallying only then in a detailed scope (a single space), if there is it really relevant information.

the next level… divides the spaces in the Middle from top to bottom…

… the next level shares left the remaining eight rooms in the Center and divides it into two with four rooms…

In the case of the linear search, you would scan each of the 16 individual rooms. So run a workload of 16. In the case of logarithmic one would eliminate one the right half of the step. In the second step you would left the area below to eliminate. Step three would mark the right half of the four remaining rooms as irrelevant. Fourth, it is finally finds out that only the a space left is above relevant. So, it took only four working units instead of 16.

If you now enlarged the building to 32 rooms, so you would have 32 units of work compared in the linear case, but only 5 in the case of the logarithmic search. Generally: when to increase the geometric complexity of a scene to ten times, then the computational when using the hierarchical structures of acceleration only by a factor of two increases. In contrast, the Rasterisierung is available with linear behavior, in which the geometry tenfold increase means the tenfold computational.

This behavior is shown in the following diagram:

The grey curve represents the computational of raytracing, if you increase the number of triangles. The Red shows the linear behavior of the Rasterisierung. As you can see, ray tracing is a low number of triangles at a disadvantage. However, the curves meet quickly and at this point ray tracing is faster than Rasterisierung with the increasing complexity, as soon as the acceleration structure was built. Where exactly this intersection is, that many factors depends on: the performance of the CPU, the performance of the GPU, and so on. But the trend is a mathematical certainty: the logarithmic curve will have always a point of intersection with a linear.

By the near-perfect scaling behavior of raytracing, the grey curve in a doubling of the CPUs or CPU cores by half would shrink and thus move the intersection closer to the area of zero indicated in the diagram. The more CPUs or cores available, the faster it comes so to the point where it is faster than the Rasterisierungsverfahren on the GPU.

An example of which is clearly above the intersection is the model of a Boeing 777 with 350 million triangles. This extremely high detailed model includes every screw of the aircraft and was provided by Boeing of the scientists, to methods to inquire, with which you can graphically the complete aircraft best in movement.

Raytracing has proved the correct solution. Already in 2004 the research group of at the Saarland University could this model with 3 to 7 frames per second at a resolution of 640 x 480 on a dual-core CPU of at that time render.

The question may arise, why the mentioned acceleration structures in the Rasterisierung not be used? They are used! But with a lower precision. Some games have even different resolution granular to render graphics for the collision detection or the AI (sometimes creates libraries of other software vendors). In addition to the increased memory consumption is another problem of this multiple structures, that you must keep them consistent.

Here an example of what happens when the information from the collision detection with those from the data structure to render are consistent: in the game of “Oblivion” different detailed representations of the world are used to render or collision detection. If a door in the game is slowly closing, so this is clearly visible for the player. In each image the angle changes slightly, until the door is closed. Therefore, one can assume that there are at least four different States for this door: open, closing, closed, open. But the data structure of the collision detection will be updated with same level of detail. Thus, other computer-controlled characters such as “Velwyn” can be only two States of the door: open or closed.

In the game, it can therefore happen that the door for the player is obvious just about to close, since Velwyn can get only the information that the door is not closed, he comes to believe that the door must be so open. Therefore Velywn moves towards the door, until he is suddenly stuck once the door to closed status has been updated. This looks then like this:

< div >

Velwyn is in the door firmly in oblivion (2006)

(Of course you can use raytracing for collision detection to prevent such problems, but that’s another story).

But even if the acceleration structures to render with the others in the Rasterisierung are consistent, there is another problem: in raytracing testing the rays pixel accurate against the triangles. In the Rasterisierung there are, however, no rays that can be tested against the acceleration structure exactly, therefore one must again rely on less efficient approximations. This can be done with different methods. Here a brief overview of two of them:

• Provide time consuming preliminary calculations, the statements as “When I’m in room 1, then I could see possibly rooms 2 and 3, but not room 4″. There is to learn more about this procedure in the Wikipedia entry “potentially visible set”

• Manually placed notes of level designers, so-called visibility portals. These require much additional time on the part of the programmer. The original quake, for example, 3,200 pieces of 4 used and automated algorithms to set the portals have found their way in the practice of the game developer. The evaluation of the portals when rendering in the Rasterisierung leads to complex multi-pass techniques: First, the scene with placeholders for the portals is rendered. After has been recognized that one of the placeholder is visible, this part of the scene is rendered, once again this time with full detail. Learn more about the “portal rendering” can be found at Wikipedia.

Example 2

The second example is a case study with several reflections in reflections on spheres and Tori. (The mathematical term for a geometrischens object in the form of a Donuts is a torus.) (The plural of torus is Tori.)

< div >

Multiple reflections in mirrors.

Ignoring you for a moment the fact that it would be generally impossible, such ‘ a scene by means of Rasterisierung to render, so one finds that it is not only possible, but also much less computing-intensive in any other way (raytracing), as it has accepted first! Because raytracing calculates all reflections efficiently and correctly – but only if they are really needed, they are so visible. The following sequence shows the process to create the image and it shows how many rays are used:

Step 1: primary rays – at least one per pixel (marked in red), all on the field of view is visible

Step 2: only the reflecting surface reflect primary reflection (marked green),

3 Step: secondary reflections (blue), reflected rays are reflected again only by the blue areas

Step 4: Tertiary reflections (marked in yellow), only on the yellow areas meet has twice reflected rays again and be reflected

Step 5:, and so on and so forth..

As you can clearly see, reduces the number of additional radiation dramatically with every further step. Therefore, even a complex scene with many reflections in mirrors with only a small additional cost using raytracing can be calculated.

Reflections on Rasterisierung

To simulate reflections at the Rasterisierung, the scene of at least a camera position vorgerendert and in a texture (known as a so-called reflection map, sometimes cube map) is stored, then layers is stuck on a multipass process when rendering on a surface. The same method is used when creating the so-called “shadow maps”, which also required a further passage, before you can render the scene.

There are different cases and methods to do so (source: University Erlangen):

• An example of a benötigende a run reflection map, created using the effect of a fisheye lens.
• Here the way to a reflection map on two additional passes with a paraboloiden distortion:
• Here, you need six additional passes to create the cube map (thanks to Paul Bourke of the image).

• There are many other algorithms that improve further details on the methods.

But all approaches by means of Rasterisierung have their limitations:

• The rendering to a texture leads to visible artifacts due to problems with the sampling (an object that was far away from the camera that has generated the reflection map, ends in a very small representation in the texture.) (One zooms but precisely in this area from the perspective of real, one sees the individual pixels much too coarse).

• The pre-rendering in a texture is time-consuming. In the worst case, you can see only a single pixel of the mirror at the end, however additional renders six times to create the cube map the scene.
• How should you handle reflections in mirrors? This is very difficult to implement and impossible in most cases. This should you precalculate the scene with tints, evaluate, once again with reflections in mirrors and and evaluate. A great time.
• And finally: because the process of reflection maps is based not on physical principles, the reflections are not correct anyway.

What all’ these approaches try, is an approach to raytracing. As mentioned in the first example: the speed of ray tracing scaled logarithmically with the number of triangles. Applies to for all reflection blasting. Therefore, to be drawn even more benefits from this situation in a scene with many polygons and reflections.

Special effects

Ray tracing is often used due to the unique capabilities to provide special effects, which would not be possible in other algorithms, or would produce only unreliable results, in the production of motion pictures. The following section shows two special effects, which are relevant to computer games and can increase the fun factor to a lot: camera portals and reflections.

Camera portals

A now well-known feature in 3D-Shootern is the portal of the camera. It allows you to see the player in a range of the scene (World), in which he is physically not located.

< div >

Camera portal in Quake 3: arena (1999)

It is very interesting to see how easy and efficient this effect using raytracing can be realized. Here the list of the scene:

The player is located on the lower level. Before him is a camera portal, through which he sees through. An opponent is located on the upper level. What we want is that the portal promoted us (or our field of view) in a magical way to the upper level. For ray tracing, this simply means that you need an offset (from the impact point on the camera portal to a new origin) for the primary beam, to pursue further so the beam. This is here depicted:

In programming, this looks like this:

/ / Find out the impact point of the ray in the shader program.

Vector3D hitPosition = getHitPositionOfRay(ray);

/ / Add a 3D-Offsets to the target location.

hitPositon += cameraPortalOffset;

/ / Shooting a new ray of the target location with the
/ / Offset, it added in the same direction.

finalColor = traceNewRay (hitPosition, getDirectionOfRay(ray));)

Voilà, with only three lines of code you have his camera Portal. Are applied in Quake 3: Raytraced:

< div >

Camera portal in Quake 3: Raytraced (2004)

In October 2007, valve had released a game called “Portal”. It contained an innovative, new game concept: by nifty place of portals within the game world was to get the player in the position, as if to various places in the world by and solve little puzzles. From technical point of view, it is very interesting to see how the camera portal-in-camera Portal effect has been implemented here.

< div >

The game “Portal” of the valve (2007)

The implementation is fairly robust. The game is designed so that you never get too close the portal in portal effect, not too much to increase the depth of recursion. However, after some experimentation and testing can be seen the limit of approach in the following screenshot, in the depth of recursion has exceeded the predefined limit. This can be seen in the center of the portal, in the box with correct representation often would need to repeat themselves.

< div >

The appearance of the box is repeated only up to
a number in the middle of the portal.

It is very interesting to note how the code for the effect must be changed to raytracing to support camera portals in Kamerportalen: gar not! It is still with the exact same code! The offset parameter must only be modified so that it points to a square in front of the camera Portal. This is here depicted:

To create an effect, however, at the Rasterisierung, the image is rendered once with an “empty” camera portal in a texture. Then, you must paste a part of this texture on the empty spot. Then repeat it once again with a smaller version in the middle of the range of empty blotch, and so on and so forth..

When rendering with the only three lines of code in raytracing, which looks then like this:

< div >

Scene from Quake 4: Raytraced. In the Middle, which is
Number of portals in portals at 130.

As in the reflections, the portal effect is very efficient, because you “pay when calculating only for as many additional rays”, as you can see they really. Also the effect that the number of additional radiation with every further step strongly decreases, the case for here. Therefore has only a very small percentage to rays a properly high depth of recursion and high cost.

It is possible with raytracing, really impressive scenes such as for example two camera portals side by side and this again even projected to generate. The program code for this looks like? He remains the same!

< div >

Q4RT: two camera portals in portals from camera

Reflections

To anticipate better gameplay by reflections to opponents

For security reasons, it is now common on walls, in corners of buildings to install mirrors so that people not into each other to run, when it it just (e.g. for lunch to come.) Just as hard derelicts 3D-Shooter-Spieler like to can look around corners. Maybe is just an opponent on the way? Perhaps an ally? With ray tracing, this is quite easy to solve, is a mirror in the world and enjoys the added possibilities in the gameplay.

< div >

4: Quake Raytraced – additional levels in the corner, to the
other gear to see

Here is a video in which the additional information about an approaching enemy is exploited by the additional levels in the corner. Only by looking in the mirror, the player could anticipate the arrival of the monster and in time to fire a missile in its direction.

&Lt; div > < div > Watch gameplay video on YouTube

Error:Unknown video service “youtube”.

Hybrid rendering

Why it is a bad idea and why it still made be is.

How will ray tracing appear for games on the market? Many people expect that there will be a smooth transition. Rasterisierung of Rasterisierung with raytracing to point to completely “raytraced”. The adoption of some is that the largest part of the image is rasterisiert and ray tracing will be used only in small areas, such as about a reflective sphere.

It is a nice thought and reflects the developments which took place in the area of graphics cards in the past. Initially it had only a fixed Renderpfad. Then, some small parts for developers were opened. This evolved from the complex to be programmed “register combiner” to the vertex and pixel rags have in turn been improved a long time in small increments, which always a smooth transition of an advance on the other hand came up.

It is therefore quite understandable that some have the expectation that raytracing is also introduced in small steps. The problem is: from a technical perspective, it makes no sense, as the cost of the part, which is calculated with ray tracing, in many cases very quickly take the decisive part of the calculation.

Example 1

A typical game scenario let out us Quake 4 with an additional, reflecting sphere which is far away from the eye of the beholder, take:

You could now apply everything except the ball using Rasterisierung render and only raytracing to the ball. To do this, you need yet:

• A fast Raytracer
• Current Beschleunigunsstrukturen (e.g. BSP tree, BVH-tree,…) for the entire scene

If the game world is very complex, then it is rasterisieren probably more triangles than you would have needed rays, to do this – a pure Raytracer would have been so efficient. But once outside, we can be for this adoption, so have we in this scenario, assuming that the Rasterisierer dissolves all visibility tests, all primary rays “saved”.

Example 2

The above screenshot looks pretty boring because he considered no lighting and shadows. In the example below, every pixel with an average three to five lamps is lit at the same time.

If you use raytracing to calculate all shadows correctly, then each pixel would require a primary beam and four shadow rays. You would instead use Rasterisierung to generate the same image quality, would you only the a primary beam “Save”. The approaches of Rasterisierung on correctness and accuracy are not accurate enough for shadows, reflections and refractions. Especially if you then strives to achieve ever-higher image qualities, then saving by Rasterisierung for calculating visibility (so instead of primary radiation) lost more and more.

Example 3

The two previous examples have shown a distant mirror. But what happens if one of such ‘ a reflecting object close approach so zooms that it almost fills the entire screen? In a gaming environment, in which the player can move freely, there are such situations not to prevent.

Now, 90 percent of all pixels of ray tracing must be calculated at once around. Therefore would you the approach of Hybridrendering only 10 per cent for the primary rays “Save”.

Example 4

I’ll leave finding the imagination of the reader out, the approach of Hybridrendering is how useful if this reflection shows also the lighting with shadows.

The previous considerations lead to the conclusion that the Hybridrendering approach to the representation of the 3D world is not necessarily the best idea. His only ‘ useful application is in my opinion an additional layer like a HUD (heads up display), a console, or perhaps even the 3D perspective of a cockpit, but does not render of the effective 3-d scene.

< div >

Fonts and Crosshair as an additional layer of a geraytractem
Picture by partially transparent squares in OpenGL.

Nevertheless, I wouldn’t be surprised to see demos to the approach of Hybridrendering of people who believe in this idea. However, I doubt that the method will create it in a convincing manner in a commercial game.

There are certainly soon be more about raytracing. And thank you for reading this article! Stay tuned!

About the author

Daniel Pohl is a researcher at Intel in Germany (soon at Intel in Santa Clara, California, “Silicon Valley”). He joined the art team of Intel, after completing his computer science degree from the University of Erlangen. While he had his the raytracing algorithm on the games Quake 3 and Quake 4 applied. His main interests are 3D graphics and game programming.