191 Perspective-Correct Computation Pixels Color for Systems of Three-Dimensional Rendering Oleksandr Romaniuk1, Oleksandr Dudnyk1, Serhii Pavlov2 , Olena Tsikhanovska3 1. Department of Software Engineering, Vinnytsia National Technical University, UKRAINE, Vinnytsia, 95 Khmelnytske shose str., email: rom8591@gmail.com, dudnyk@vntu.edu.ua 2. Department of Biomedical Engineering, Vinnytsia National Technical University, UKRAINE, Vinnytsia, 95 Khmelnytske shose str., email: psv@vntu.edu.ua 3. Department of Economics of Enterprises and Corporations, The Vinnytsyia Educational and Research Institute of Economics Ternopil National Economic University, UKRAINE, Vinnytsia, 37 Gonta str., email: vnnie.epik@gmail.com Abstract: In computer graphics, the projections of perspective of an object. In order to increase the realism of three-dimensional images are considered on a two- perspective-correct texturing [4, 5, 6], use of nonlinear dimensional picture plane. Flat geometric projections are functions, the calculation of which involves the divided into two main classes: central and parallel. The implementation of labor-intensive operations. difference between them is determined by the relationship between the center of the projection and the projection II. SHADING WITH THE PERSPECTIVE plane. If the distance between them is finite, then the projection will be central, and if it is infinite, then the Ignoring the depth of the object in the calculation of the projection will be parallel. In real space reflection of rays vectors leads to error computing its orthogonal components, from objects is perceived at the location of the observer, which can be calculate by the formula that is, on the principle of central projection. Correct u ⋅ z1 reproduction of colors takes place provided that the ∆I = I A + ( I B − I A ) ⋅ − IA − components of the color intensities of the corresponding z 2 − u ⋅ ( z 2 − z1 ) surface points in the global (object) and screen coordinate u ⋅ z1 systems coincide. −( I B − I A ) ⋅ u = ( I B − I A ) ⋅ ( u − )= (1) The authors propose methods to improve the z 2 − u( z 2 − z1 ) performance of texture mapping and realism of shading, in particular, the methods perspective-correct texturing 1 = ( IB − IA ) ⋅ u ⋅ ( 1 − ), and Phong shading. z2 z2 Keywords: texturing, texture mapping, rendering, + u( 1 − ) computer graphic, shading, Phong shading. z1 z1 replacing the intensity value of the color value of the I. INTRODUCTION orthogonal component. When forming graphical images is solved by a twofold For perspective-correct reproduction of colors using Phong task – improve performance and enhance realism. Today the shading it is necessary to use non-linear interpolation of performance of graphical tools sufficient for the formation of normal vectors using a variable t w . Unfortunately, the images according to their visual properties similar to the photos, you have achieved photographic quality. calculation t w according to the formula [1] To ensure high realism is important to consider the Z Àw ⋅ t v perspective transformation of polygons in the determination tw = (2) of pixel colors: in the texture mapping and shading. Z Bw − t v ( ⋅Z Bw − Z Aw ) The perspective-correct formation of colors is used both for shading and texture mapping. When coloring the surfaces of three-dimensional objects, provides for the execution of a division operation for each the methods of Gourund and Phong are most often used. The current value of t v . Consider the approximation of t v to question of the prospective correct reproduction of colors simplify the hardware implementation. Since the dependence according to these methods is considered, respectively, in [1, is nonlinear, using linear interpolation on the whole interval 2, 3]. In the tasks of texturing, you need to find the relationship variable is excluded. Approximation t w second degree polynomial a ⋅ tv + b ⋅ tv + c. Find unknown a, b, c . between the screen coordinates and texture coordinates. In 2 order to ensure high productivity, the linear and quadratic functions are often used in perspective-correct texture To do this we set up a system of equations using three points mapping [4, 5]. In such approaches, a molded image may = tv 0,= tv 1,= tv 1 / 2. have artifacts and does not always faithfully reproduce the ACIT 2018, June 1-3, 2018, Ceske Budejovice, Czech Republic 192  2 ⋅ ( 9 ⋅ Z Aw − 5 ⋅ Z Bw ) ⋅ Z Bw b= , c = 0, (Z + Z Aw )( 3 ⋅ Z Âw + Z Aw )  Bw a + b + c = 3 ⋅ ( Z Aw − Z Bw ) 2 1, 1 c= . 1  ⋅a + ⋅b + c = Z Àw (Z Bw + Z Aw )( 3 ⋅ Z Âw + Z Aw ) . 4 2 Z +Z Bw Aw The analysis showed that in this case  = 2, 3, 4, 5 the The system has such a solution maximum modulus of the relative error does not exceed, 1% , 4%, 8%, 13%. With regard to three-dimensional objects,  , 2 ⋅ ( Z Bw − Z Aw ) (3 ⋅ Z − Z ) as a rule, does not exceed 3. =a = ,b Aw , Bw ( Z Bw + Z Aw ) (Z + Z ) Consider using approximation by third-order polynomial a ⋅ t v + b ⋅ t v + ct + d . For finding the Bw Aw 3 2 of the form c = 0. unknown we set up a system of four equations. To do this, Z Bw 2 ⋅ (  − 1) (3 −  ) make the value of the polynomial equal t w (see formula 2) in If  == , then a = , b . Z Aw (  + 1) (  + 1) points t v = 0, 1 / 3, 2 / 3, 1 . Find: 9 ⋅ ( Z Bw − Z Aw ) 2 The quadratic approximation gives satisfactory results a= , only for  ≤ 3 . In figure 1 shows a graph of change of the (2 ⋅ Z + Z ) ⋅ (Z Bw Aw Bw + 2 ⋅ Z Aw ) absolute error of the approximation from t v ,  . −9 ⋅ ( Z − Z )( Z − 2 ⋅ Z Aw ) b= Bw Aw Bw , (2 ⋅ Z + Z ) ⋅ (Z Bw Aw Bw + 2 ⋅ Z Aw ) c= (2 ⋅ Z 2 Bw − 4 ⋅ Z Aw ⋅ Z Bw + 11 ⋅ Z Aw ). (2 ⋅ Z Bw + Z Aw ) ⋅ ( Z Bw + 2 ⋅ Z Aw ) 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 Fig. 1. The dependence of the modulus of the absolute WITH PERSPECTIVE error of the approximation from t v ,  Finding texture coordinates is a time consuming procedure because it requires the execution of complex operations for Higher accuracy of approximation can be achieved if the each pixel according to the formula [4, 5]. use of piecewise quadratic interpolation on two periods of change t v . For 0 ≤ t v ≤ 0,5 Ax + By + C Dx + Ey + F u= , v= . 8 ⋅ Z Aw ⋅ ( Z Bw − Z Aw ) Gx + Hy + I Gx + Hy + I a= , ( Z + Z )( 3 ⋅ Z + Z ) Bw Aw Âw Aw If x = x + 1 , then (3 ⋅ Z + Z ) i + 1 i b = Aw , c 0.Bw A ⋅( x + 1) + B ⋅ y + C ( A ⋅ x + B ⋅ y +C )+ A ( Z + Z )( 3 ⋅ Z + Z ) = Bw Aw Âw u = D ⋅( x + 1) + E ⋅ y + F Aw i +1 1 ( D⋅ x + E ⋅ y + F )+ D . i 1 i 1 1 i 1 i 1 1 i i i i For 0,5 < t v ≤ 1 For u 0 the formula has the form: −8 ⋅ Z Bw ⋅ ( Z Aw − Z Bw ) a= , A1 ⋅ (x0 + 0 ) + B1 ⋅ yi + C1 A1 ⋅ x0 + B1 ⋅ yi + C1 (Z Bw + Z Aw )( 3 ⋅ Z Âw + Z Aw ) = u0 = . D ⋅ (x0 + 0 ) + E ⋅ yi + F D ⋅ x0 + E ⋅ y i + F ACIT 2018, June 1-3, 2018, Ceske Budejovice, Czech Republic 193 For u 1 : wn = ut + A1 ⋅ n , vn = ub + D ⋅ n , A1 ⋅ ( x0 + 1) + B1 ⋅ yi + C1 A1 ⋅ x0 + A1 + B1 ⋅ yi + C1 u1 = . then the division operation to calculate the coordinates D ⋅ ( x0 + 1) + E ⋅ yi + F D ⋅ x0 + D + E ⋅ y i + F w un = n . vn For u 2 : The sequence of operations of the algorithm shown in A1 ⋅ ( x0 + 2) + B1 ⋅ yi + C1 figure 2. =u2 = D ⋅ ( x0 + 2) + E ⋅ yi + F A1 ⋅ x0 + A1 ⋅ 2 + B1 ⋅ yi + C1 = . D ⋅ x0 + D ⋅ 2 + E ⋅ y i + F Thus, for u n the formula has the form: A1 ⋅ ( x0 + n ) + B1 ⋅ yi + C1 =un = D ⋅ ( x0 + n ) + E ⋅ y i + F A1 ⋅ x0 + A1 ⋅ n + B1 ⋅ yi + C1 = . (2) D ⋅ x0 + D ⋅ n + E ⋅ y i + F A similar formula can be written for v n . A2 ⋅ xi + B2 ⋅ y + B2 ⋅ n + C2 Fig. 2. Parallel calculating texel coordinates vn = 0 . D ⋅ xi + E ⋅ y0 + E ⋅ n + F Since for each x, n is increased by 1, there is such a formula: From the given formulas it is visible that for calculation of each texel computer needs to perform 2 operations of wn wn −1 + A1 , = = vn vn −1 + D . (4) division, 8 operations of addition and 8 multiplications. As can be seen from formulas (2), the value of the In accordance with the formulas (4), we can offer a expressions A1 ⋅ x0 + B1 ⋅ yi + C1 and D ⋅ x0 + E ⋅ yi + F consistent algorithm for calculating texture coordinates: w n and v n for each х calculated by adding to w n-1 and v n-1 , that for each n remain unchanged, and therefore can be calculated was calculated for х-1, А 1 and D. The sequence of operations once for each rasterization line using formula: of the algorithm shown in figure 3. ut = A1 ⋅ x0 + A1 ⋅ n + B1 ⋅ yi + C1 , ub = D ⋅ x0 + E ⋅ yi + F . where u t and u b constant part of the numerator and denominator of formula (1) in accordance. Therefore, u n can be calculated according using the formula u + A1 ⋅ n un = t . (3) ub + D ⋅ n Thus, for calculating coordinates of all texels, variables, u 1t and u 1b are constant, and their value is sufficient to calculate once. Similarly you can calculate v n . 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 u t and u b , then calculate values of the numerator and denominator in parallel by the formula: Fig. 3. Sequential calculating texel coordianates ACIT 2018, June 1-3, 2018, Ceske Budejovice, Czech Republic 194 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). Fig. 4. Parallel computing texels coordinates for two threads on the same rasterization line wn wn −1 + A1 , а = If = vn vn −1 + D then: wn +1 = ( wn −1 + A1 ) + A1 , vn +1 = (vn −1 + D ) + D . Thus, parallel computation of the texture coordinates of pixels on odd and even positions is possible according to the Fig. 6. Comparison of the performance of the proposed method with formulas: the classical =wn wn − 2 + 2 A1 , = vn vn − 2 + 2 D . (5) III. CONCLUSION In this case, the coordinates texels for the first two points are defined by the formula (3). Proposed methods to improve the performance of texture Based on the formulas (5) and (5) to establish the mapping and realism of shading, in particular, the methods relationship which allows parallel rasterization the line in an perspective-correct texturing and Phong shading. random number of threads using formulas: REFERENCES = wn wn − k + kA1 , = vn vn − k + kD , [1] G. F. Ahmed, R. Barskar, J. Bharti, and N. S. Rajput, “Content Base Image Retrieval Using Fast Phong Shading,” 2010 International Conference on whre k – the number of concurrent threads. Computational Intelligence and Communication It is also possible a parallel calculation of the coordinates Networks, 2010. in two streams by simultaneous rasterization of line in two [2] R. F. Lyon, “Phong Shading Reformulation for directions (fig. 5). From right to left according to the formula Hardware Renderer Simplification”, Apple Technical (4), and from left to right according to the formula: Report #43, August 2, 1993. = wn wn +1 − A1 , = vn vn +1 − D . [3] D. A. Kulagin, "Models of shading. Flat model. Shading on Guro and Fong ", Computer graphics. Theory, algorithms, examples on C++ and OpenGL. [Online]. Available http://compgraphics.info/3 D/lighting/shading_model.php [4] P. S. Heckbert, “Survey of Texture Mapping,” IEEE Computer Graphics and Applications, vol. 6, no. 11, pp. 56–67, 1986. [5] F. Tsai and H. C. Lin, “Polygon‐based texture mapping Fig. 5. Parallel computation of the coordinates in the two streams for cyber city 3D building models,” International with a counter direction of rasterization Journal of Geographical Information Science, vol. 21, no. 9, pp. 965–981, 2007. The figure 6 show that the proposed method makes it [6] X. U. Ying, “An Improved Texture Rendering possible to increase productivity perspective-correct texturing Technique Based on MipMap Algorithm”, Journal of 26%. Testing was conducted on the Intel i7 2600K CPU and Mianyang Normal University, 2013, 5: 017. GPU AMD RX460. ACIT 2018, June 1-3, 2018, Ceske Budejovice, Czech Republic