I. INTRODUCTION

When forming graphical images is solved by a twofold task -improve performance and enhance realism. Today the performance of graphical tools sufficient for the formation of images according to their visual properties similar to the photos, you have achieved photographic quality.

To ensure high realism is important to consider the perspective transformation of polygons in the determination of pixel colors: in the texture mapping and shading.

The perspective-correct formation of colors is used both for shading and texture mapping.

When coloring the surfaces of three-dimensional objects, the methods of Gourund and Phong are most often used. The question of the prospective correct reproduction of colors according to these methods is considered, respectively, in [1,2,3].

In the tasks of texturing, you need to find the relationship between the screen coordinates and texture coordinates. In order to ensure high productivity, the linear and quadratic functions are often used in perspective-correct texture mapping [4,5]. In such approaches, a molded image may have artifacts and does not always faithfully reproduce the perspective of an object. In order to increase the realism of perspective-correct texturing [4,5,6], use of nonlinear functions, the calculation of which involves the implementation of labor-intensive operations.

II. SHADING WITH THE PERSPECTIVE

Ignoring the depth of the object in the calculation of the vectors leads to error computing its orthogonal components, which can be calculate by the formula

1 A B A A 2 2 1 1 B A B A 2 2 1 B A 2 2 1 1 u z I I ( I I ) I z u ( z z ) u z ( I I ) u ( I I ) ( u ) z u( z z ) 1 ( I I ) u ( 1 ), z z u( 1 ) z z ∆ ⋅ = + − ⋅ − − − ⋅ − ⋅ − − ⋅ = − ⋅ − = − − = − ⋅ ⋅ − + −(1)

replacing the intensity value of the color value of the orthogonal component.

For perspective-correct reproduction of colors using Phong shading it is necessary to use non-linear interpolation of normal vectors using a variable w t . Unfortunately, the calculation w t according to the formula [1] Àw

v w Bw v Bw Aw Z t t Z t ( Z Z ) ⋅ = − ⋅ − (2)

provides for the execution of a division operation for each current value of To do this we set up a system of equations using three points

v v v t 0, t 1, t 1/ 2. = = = Àw Bw Aw c 0, a b c 1, 1 1 Z a b c . 4 2 Z Z = + + = ⋅ + ⋅ + = +       

The system has such a solution

( ) ( ) ( ) ( ) Bw Aw Aw Bw Bw Aw Bw Aw 2 Z Z 3 Z Z a , b , Z Z Z Z c 0. ⋅ − ⋅ − = = + + = If Bw Aw Z Z =  , then ( ) ( ) ( ) (

)

2 1 3 a , b . 1 1 ⋅ − − = = + +    

The quadratic approximation gives satisfactory results only for 3 ≤



. In figure 1 shows a graph of change of the absolute error of the approximation from v t ,  .

0 t 0,5 ≤ ≤ ( ) ( )( ) ( ) ( )( ) Aw Bw Aw Bw Aw Âw Aw Aw Bw Bw Aw Âw Aw 8 Z Z Z a Z Z 3 Z Z 3 Z Z b , c 0. Z Z 3 Z Z ⋅ ⋅ − = + ⋅ + ⋅ + = = + ⋅ + For v 0,5 t 1 < ≤ ( ) ( )( ) Bw Aw Bw Bw Aw Âw Aw 8 Z Z Z a , Z Z 3 Z Z − ⋅ ⋅ − = + ⋅ + ( ) ( )( ) Aw Bw Bw Bw Aw Âw Aw 2 9 Z 5 Z Z b , Z Z 3 Z Z ⋅ ⋅ − ⋅ ⋅ = + ⋅ + ( ) ( )( ) 2 Aw Bw Bw Aw Âw Aw 3 Z Z c . Z Z 3 Z Z ⋅ − = + ⋅ +

The analysis showed that in this case 2, 3, 4, 5 =  the maximum modulus of the relative error does not exceed, 1% , 4%, 8%, 13%. With regard to three-dimensional objects, ,  as a rule, does not exceed 3.

Consider using approximation by third-order polynomial of the form

3 2 v v a t b t ct d . ⋅ + ⋅ + +

For finding the unknown we set up a system of four equations. To do this, make the value of the polynomial equal w t (see formula 2) in points v t 0, 1 / 3, 2 / 3, 1 =

. Find:

( ) ( ) ( ) ( )( ) ( ) ( ) ( ) ( ) ( ) 2 Bw Aw Bw Aw Bw Aw Bw Aw Bw Aw Bw Aw Bw Aw 2 Bw Aw Bw Aw Bw Aw Bw Aw 9 Z Z a , 2 Z Z Z 2 Z 9 Z Z Z 2 Z b , 2 Z Z Z 2 Z 2 Z 4 Z Z 11 Z c . 2 Z Z Z 2 Z ⋅ − = ⋅ + ⋅ + ⋅ − ⋅ − − ⋅ = ⋅ + ⋅ + ⋅ ⋅ − ⋅ ⋅ + ⋅ = ⋅ + ⋅ + ⋅

The analysis showed that when using the cubic interpolation achieves better accuracy compared to piecewise-quadratic interpolation. For example, when 2, 3, 4, 5 =  the maximum modulus of the relative error does not exceed, 0,64 %, 2,9 %, 6,3 %, 10,6 %.

III. IMPROVING THE PERFORMANCE OF TEXTURING WITH PERSPECTIVE

Finding texture coordinates is a time consuming procedure because it requires the execution of complex operations for each pixel according to the formula [4,5].

Ax By C u

Gx Hy I

+ + = + + , Dx Ey F v

Gx Hy I

+ + = + + . If i i 1 x x 1 + = + , then 1 i 1 i 1 i 1 i i A ( x 1 ) B y C u D ( x 1 ) E y F + ⋅ + + ⋅ + = = ⋅ + + ⋅ + 1 i 1 i 1 1 i i ( A x B y C ) A . ( D x E y F ) D ⋅ + ⋅ + + ⋅ + ⋅ + +

For u0 the formula has the form:

1 0 1 1 0 0 0 0 i i A (x ) B y C u D (x ) E y F ⋅ + + ⋅ + = = ⋅ + + ⋅ + 1 0 1 1 0 . i i A x B y C D x E y F ⋅ + ⋅ + ⋅ + ⋅ +

For u1:

1 0 1 1 1 0 ( 1) ( 1) i i A x B y C u D x E y F ⋅ + + ⋅ + = = ⋅ + + ⋅ + 1 0 1 1 1 0 . i i A x A B y C D x D E y F ⋅ + + ⋅ + ⋅ + + ⋅ +

For u2:

1 0 1 1 2 0 (2)

( 2)

i i A x B y C u D x E y F ⋅ + + ⋅ + = = ⋅ + + ⋅ + 1 0 1 1 1 0 2 . 2 i i A x A B y C D x D E y F ⋅ + ⋅ + ⋅ + ⋅ + ⋅ + ⋅ + =

Thus, for un the formula has the form:

1 0 1 1 0 ()( ) i n i A x n B y C u D x n E y F ⋅ + + ⋅ + = = ⋅ + + ⋅ + 1 0 1 1 1 0 . i i A x A n B y C D x D n E y F ⋅ + ⋅ + ⋅ + = ⋅ + ⋅ + ⋅ +(2)

A similar formula can be written for vn.

0 2 2 2 2 0 . i n i A x B y B n C v D x E y E n F ⋅ + ⋅ + ⋅ + = ⋅ + ⋅ + ⋅ +

From the given formulas it is visible that for calculation of each texel computer needs to perform 2 operations of division, 8 operations of addition and 8 multiplications.

As can be seen from formulas (2), the value of the for each n remain unchanged, and therefore can be calculated once for each rasterization line using formula:

1 0 1 1 1 0 , . t i b i u A x A n B y C u D x E y F = ⋅ + ⋅ + ⋅ + = ⋅ + ⋅ +

where ut and ub constant part of the numerator and denominator of formula (1) in accordance. Therefore, un can be calculated according using the formula

1 . t n b u A n u u D n + ⋅ = + ⋅(3)

Thus, for calculating coordinates of all texels, variables, u1t and u1b are constant, and their value is sufficient to calculate once. Similarly you can calculate vn.

This simplification reduces the number of operations of addition and multiplication to 4 for each.

Based on these mathematical relationships it is possible to offer algorithm of parallel calculation of texels coordinates: for each rasterization line at first calculates the parameters ut and ub, then calculate values of the numerator and denominator in parallel by the formula:

1 n t w u A n = + ⋅ , n b v u D n = + ⋅ ,

then the division operation to calculate the coordinates

n n n w u v = .

The sequence of operations of the algorithm shown in figure 2.

Fig. 2. Parallel calculating texel coordinates

Since for each x, n is increased by 1, there is such a formula:

1 1 n n w w A − = + , 1 n n v v D − = + .(4)

In accordance with the formulas (4), we can offer a consistent algorithm for calculating texture coordinates: wn and vn for each х calculated by adding to wn-1 and vn-1, that was calculated for х-1, А1 and D. The sequence of operations of the algorithm shown in figure 3.

Fig. 3. Sequential calculating texel coordianates

The computing of texture coordinates by this algorithm can also be accelerated using parallel computing. One possible approach to parallelization is the parallel rasterization of several lines simultaneously. However, this approach will not be productive enough in cases when the number of pixels per row is much higher than the number of rows. Therefore, it is advisable to use means of parallel calculations within a single line.

Let's consider parallel computing of cordiant texels for pixels located at even and odd positions in the rasterization line (fig. 4).

− = + , а 1 n n v v D − = + then: 1 1 1 1 ( ) n n w w A A + − = + + , 1 1 ( ) n n v v D D + − = + + .

Thus, parallel computation of the texture coordinates of pixels on odd and even positions is possible according to the formulas:

In this case, the coordinates texels for the first two points are defined by the formula (3).

Based on the formulas ( 5) and (5) to establish the relationship which allows parallel rasterization the line in an random number of threads using formulas: It is also possible a parallel calculation of the coordinates in two streams by simultaneous rasterization of line in two directions (fig. 5). From right to left according to the formula (4), and from left to right according to the formula: The figure 6 show that the proposed method makes it possible to increase productivity perspective-correct texturing 26%. Testing was conducted on the Intel i7 2600K CPU and GPU AMD RX460.