=Paper=
{{Paper
|id=Vol-2300/Paper46
|storemode=property
|title=Perspective-Correct Computation Pixels Color for Systems of Three-Dimensional Rendering
|pdfUrl=https://ceur-ws.org/Vol-2300/Paper46.pdf
|volume=Vol-2300
|authors=Oleksandr Romaniuk,Oleksandr Dudnyk,Serhii Pavlov,Olena Tsikhanovska
|dblpUrl=https://dblp.org/rec/conf/acit4/RomaniukDPT18
}}
==Perspective-Correct Computation Pixels Color for Systems of Three-Dimensional Rendering==
https://ceur-ws.org/Vol-2300/Paper46.pdf
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