Introduction

It is more than 40 years of development of systems of visualization, especially, real time systems, led to the considerable variety both algorithmic, and architectural decisions. Implementations of graphic systems can be compared on a complex index - to the relation of quality of the received image to hardware system complexity, that is its cost. The modern graphic systems, allow to form the architecture of system for each specific application. Graphic hardware and program systems are high-efficiency and, at the same time, expensive enough. In this connection the actual task at the present stage is the correct choice of a configuration of system, that is achievement of necessary quality by minimum expenses.

The operation purpose is research and the analysis of effective optimization of algorithm of ray tracing at which final cost of the graphic device for tracing scenes becouse decreases of final amount GPU decreases and speed of synthesis of the image increases..

Scientific significance

Development of the accelerated system of synthesis of a photo of realistic images by means of implementation of interpolation of pixels.

Ray tracing algorithm
The ray tracing method provides generation of images of photographic quality. It is considered that the method of tracing of rays gives the greatest possible level of realism. At creation of the image the ray is sent in the given direction for an estimation going therefrom luminous energy. This energy is defined by illuminance of the first surface which met on a ray way. The mechanism of origin of illuminance the following.

Each light source lets out rays in all directions. Coming across on a surface, the ray partially refracts, partially beats off and partially dissipates. Transiting through the transparent material, the ray undergoes natural easing.

There is direct and reverse ray tracing.

Direct ray tracing is very ineffective that ray starting point - a light source.

At reverse ray tracing rays which get to an eye of the observer are traced only. It is fulfilled in such a way. From an eye of the observer through each pixel of a screen plane in the synthesized scene the ray is passed, and then it is traced in the opposite direction. When the ray encounters a surface, intensity of appropriate pixel is defined by illuminance of the nearest crosspoint of a ray with a surface. If on a ray way there is no object, illuminance of environmental space (the sky or the earth of specially designed homogeneous model of a surface) undertakes (figure 1).

Figure 1 - Ray Tracing Algorithm (animation, 7 frames, 79KB)

In algorithm simple mathematical ratios are used. Thus calculation at stages of geometrical conversions, calculations of parameters of illuminance and rasterization are fulfilled simultaneously, however, it demands the considerable expenses of time that until recently did not allow to use it as a method synthesizing GSRT.

Algorithm elaboration interpolation for acceleration of algorithm of tracing of rays.
For optimization of ray tracing algorithm probably:

1. To accelerate the analysis of intersection of a ray/object;
2. to parallel a part of tasks.

As for the majority of tasks speed of rendering is much more important, than a correctness of display of a picture, for acceleration of operation of algorithm of ray tracing to its structure are imported a row of different modifications.

Certainly, the magnification of frequency of generation of frames was reached at the expense of lowering of quality of a picture at moving the camera and objects.

It is obvious that the adjacent pixels of the traced image have approximately identical color. In practice, the scene of average congestion, has about 70 % pixel segments (area of pixels which differ on color less than on 1 %) and approximately only 8 % of extreme areas (area of pixels which differ on color more than on 25 %) (figure 2). This data is resulted to show - time most part is spent for handling of pixels with approximately identical color. The idea also consists in change of this situation.

Figure 2 - Interpolation of pixel segment

Though the length of a segment in practice can change, more often, it makes 4-6 pixels, therefore application of difficult methods of interpolation is not expedient, and consequently in this operation calculation of color of internal pixels will be fulfilled under the formula 1:

Pinner = (Pleft + Pright )/2 (1)

Primary benefit of the given approach consists in simplicity and extra efficiency. But now there is a question - how to define an occurrence of segments. The classical algorithm of tracing of rays tracks each pixel of a plane independently, so, if there is no previous information it is impossible гарантированно to select homogeneous segments of pixels precisely.

Thus, the main idea of modification of algorithm of tracing consists in the following:

1. To trace it is less than pixels, than their total which is defined by image resolution;
2. The interpolation mechanism is applied to obtaining of value of not traced pixels;
3. For obtaining of desirable quality of render, the step of trace and coefficient of the maximum discrepancy of color of extreme pixels is used;
4. At a tracing inefficiency its step is adjusted.

Interpolation — in calculus mathematics a method of a finding of the intermediate values of value on available the discrete values of known values.

Block pixel interpolation
Let's enter agreements proceeding from structure of hardware support:

1. To each pixel of the image assign the processor element (PE) (probably virtual);
2. Two adjacent PE calculate extreme pixels of one segment;
3. Everyone PE has an identifier which changes in limits from 0 to Nmax;
4. All processor elements have identical structure.

Let's consider the image 1024 on 1024 pixels, and we assume that to each pixel the processor element was assigned. There is a huge number of processors (1 058 576). That is completely not comprehensible. Thus, application of an aforementioned method, units 4 on 4 taking completely well-founded.

The most optimal decision to interpolate not lines, and units (blocks) in the size 4 on 4 pixels (figure 3).

Figure 3 - Block interpolation

That is, trace is fulfilled only for 4 pixels which are in unit corners. Value of other pixels it is received by means of interpolation under the formula 1.

Thus, productivity in comparison with simple ray tracing algorithm rays raises.

Practical valueь
The system performance gain to happen at the expense of hardware expenses.

The total of processors for block interpolation can be calculated as:

PE_block_inter = (int [( n-1) / (k+1)] +1) ^ 2

For a picture 1024x1024, traced units 4 on 4 pixels:

PE_block_inter = ([( 1024-1) / (2+1)]+1 ) 2 = 116 964

Reduction of an amount of processors is about 7 times. As it is necessary to note that interpolation in each unit were exposed only on two internal pixels on the basis of what it is possible to tell that almost all interpolation was successful.

Today the technology of tracing of rays is applied изза labor input only by corporations, subsections which specialize on creation спец effects for films, on creation of animation films. As this technology is strongly enough widespread in sphere of operation with a three-dimensional drawing where it is necessary to synthesize only one frame, one scene, the technology is used for obtaining of high-quality images in the software, such as Maya, 3D Max, Autodesk.

The last years manufacture graphic processors nVidia and AMD very far forward stepped. Today even budgetary graphic decisions of these two giants have from 100 graphic independent units which allow to process the data quickly (parallely). These graphic processors cope with the tasks connected to calculations and a format of numbers QFLOAT (4 exact numbers), than the modern processors many times faster (figure 4).

Figure 4 - GPU/CPU speed diagram

Today nVidia and AMD already presented to review API of own engines graphic render, based on algorithm of ray tracing so in the near future it is necessary to expect appearance of computer games in which for visualization the algorithm of tracing of rays will answer that essentially affects to the best on quality computer 3D graphics.

In magistry work was developed the program model which implements algorithm of ray tracing has been developed(figure 5), supports algorithms of the miscalculation of shades, the partial shadowing, own shadowing, reflections, dispersion, reflections, anti alliasing.

Figure 5 - Program ray tracing render (animation, 5 frames, 150КБ)

The review of researches on a subject in DonNTU

In DonNTU a subject of acceleration of algorithm of ray tracing Ivanova E.V..

The review of researches on a subject in Ukraine

Unfortunately, in Ukraine in one HIGH SCHOOL the subject of acceleration of algorithm of tracing of rays was not considered.

The review of researches on a subject in the world

For obtaining of a photo of realistic images the world known companies which specialize on development of visual effects, to creation of cartoon films (PIXAR), the companies which specialize on development of hardware support for the PC are engaged in methods of optimization and acceleration of algorithm of ray tracing (INTEL, nVidia, AMD), the companies which specialize on development of specialized computer hardware (Caustic, Splutterfish).

Because of that the method of tracing of rays is very exacting to a hardware component, even the world leader on creation of visual cartoon films PIXAR uses this technology not for all development not to overload existing computational capabilities. The similar situation is tested by company Lucas Arts.

INTEL offers usage of instructions of batch operation of data SSE 1,2,3,4,5 + for acceleration of operation with a dial-up (packet) of given (vectors).

Tracing of rays on the essence is exceptional successfully approaches for parallel calculations. For calculation of separate rays the general are not used data, therefore rays can render in the arbitrary order. It means that the algorithm of ray tracing can theoretically use advantages of the modern processor technologies. Thus that the majority of applications can be fulfilled only partially in a parallel mode, ray tracing rather easily adapts for such technologies of parallel data handling, as SIMD, Hyper-Threading and multi-core processors.

Usage of technology SIMD for a ray tracing method is a little problematic. The algorithm of ray tracing becomes dependent on carrying capacity of storage as each ray settles up as transiting through some space structure and is checked about intersection with several primitives for determination of the nearest crosspoint.

nVidia went the way. As the corporation specializes on performance of powerful videos of the chips constructed on pipeline structure with a numerous amount of parallely operating units (a high-efficiency series of chips GeForce Quadro/Tesla) which fulfill operations over separate pixels and triangles, that is actually input data for these units is the dial-up of vectors, and a format of numbers - QFLOAT (128 bits), engine OptiX Engine has been created. The engine is based on usage of language HLSL (language so-called shaders, microprograms for computing units), technologies CUDA which allows to parallel calculations on one graphic chip, being based on pipeline structure with parallely operating computing units. For comparing, if the program the method of rendering occupies scenes some minutes hardware (with usage of decisions nVidia / CUDA / OptiX) occupies considerably smaller time.

AMD can brag Similar development. Their development is called AMD Cinema 2.0. A basic platform for this development is engine OTOY (a product of cooperation AMD, Otoy, Lightscape). «Cinema 2.0» is means which provide ray tracing calculation in real time on graphic processors Radeon (a series of chips v7x0, v8x0, high models of these chips have computational capability of the order 1 TFLOP by operation with numbers of format QFLOAT) and central processors AMD Phenom.

Corporation Caustic gave ready OpenGL and GLSL API, crossplatform OpenRL SDK which became the standard for development of end-to-end solutions with usage of image synthesis by means of technology of tracing of rays. Also Coustic gave first-ever the hardware decision CausticOne which allows to synthesize the image with usage of a dial-up of libraries OpenRL to 20 times faster, than modern GPU and CPU.

Splutterfish developed the system of rendering images Brazil r/s (Brazil Rendering System). Brazil r/s the main product Splutterfish implemented as a plug-in to Autodesk, 3ds Max, Rhinoceros, Autodesk Maya, and as separate standalone unit. On a commercial basis only the version for 3ds Max while Rhino 3D it is accessible in opened бета testings through Mcneel and Associates now is accessible. Brazil r/s - it is yards-trejserny render at which there are algorithms of the miscalculation of global lighting Global Illumination: QMC and Photon Mapping. This system was used by company Lucas Arts at creation of effects to a film «Star wars 3».

Conclussion

All above described products of the companies nvidia, AMD, INTEL, Caustic, Splutterfish in synthesis of a final graphic scene use all pixels, disregarding that the background can be homogeneous, filling can have identical color, that is use a part of resources in idle, for calculation of identical color, for calculation of color which differs from the adjacent pixels on coefficient SI, coefficient of an error of color of perception of an eye of the person.

To accelerate labor-consuming algorithm of tracing of rays, it is necessary to implement algorithm of block interpolation, loss on color in the resultant image minimum as applying the filter at calculation of color of intrablock pixels in a case when the upper pixels very strongly differ from lower color, it is possible to solve a problem anti alliasing.

Apparently from an example of calculation of efficiency of algorithm with application of block interpolation, 1024 on 1024 pixels it is necessary for the image in the size approximately seven times less than hardware units, acceleration of rendering scenes reaches values of 4-5 times which is caused not by a sufficient fast memory access.

So, thanks to block interpolation can be reached the big saving on processor elements by development of the graphic system which is based on algorithm of ray tracing.

Used literature

1. Malcheva R.V. The problems of modeling and rendering of the realistic complex scenes / R.V. Malcheva, S. Kovalov, U. Korotin // Сборник трудов VII МНТК «Машиностроение и техносфера XXI века. – Донецк: ДонГТУ, 2000. - С.308-310.
2. Malcheva R.V. The problems of modeling and rendering of the realistic complex scenes / R.V. Malcheva // Proceedings of ECCPM 2002. - Portoroz, 2002. - PP.537-538.
3. Серёженко А.А. Оптимизация метода трассировки лучей / А.А. Серёженко // Збірка матеріалів п’ятої міжнародної науково-технічної конференції студентів, аспірантів та молодих науковців. – Донецк: ДонНТУ, Т2, 2009 - с. 71-74.
4. Роджерс Д. Математические основы машинной графики. Пер. с англ. / Д. Роджерс, Дж. Адамс / Под ред. Ю.И.Топчеева.- М.: Машиностроение,1980 234 с.
5. Эгрон Ж. Синтез изображений. Базовые алгоритмы. / Ж. Эгрон. - М.: Радио и связь. - 1993. - 216 с.
6. Корреган Д. Компьютерная графика. Секреты и решения. / Д. Корреган - М.,1995 - 345 с.
7. Шикин Е.В. Начала компьютерной графики. / Е.В.Шикин, А.В.Боресков, А.А.Зайцев. - М.: ДИАЛОГ-МИФИ. - 1993.- 138 с.
8. SplutterFish: Brazil Rendering System for 3ds Max [электронный ресурс] - режим доступа - http://splutterfish.com
9. Caustic Graphics - Reinventing realtime ray tracing with OpenRL SDK built on OpenGL and GLSL APIs [электронный ресурс] http://www.caustic.com/
10. Cinema 2.0: The Next Chapter in the Ultimate Visual Experience - [электронный ресурс] - http://www.amd.com/us-en/Corporate/AboutAMD/0,,51_52_15438_15106,00.html?redir=cin01
11. nVidia OptiX: Application Acceleration Engine - [электронный ресурс] - http://www.nvidia.com/object/optix.html
Куликов А.И., Овчинникова Т.Э. Метод трассировки лучей / Интернет университет информационных технологий intuit.ru - [электронный ресурс] - http://www.intuit.ru/department/graphics/graphalg/6/5.html
12. Codermind team A ray tracer in C++ - [электронный ресурс] - http://www.codermind.com/articles/Raytracer-in-C++-Introduction-What-is-ray-tracing.html
13. Implementation Ray Tracing on GPU - [электронный ресурс] - http://www.clockworkcoders.com/oglsl/rt/gpurt1.htm