2 Texture Mapping

2.1 Definition

Texture of object surface represents a structure of surface. Any 2D texture we can represent by map:

t: D_t-->M, where D_t is subset of R² and M is subset of R(R³).

Map t maps planar area (texture domain) to modulation space (gray-scale or true colors typically). Map t is often given by a table. The table is e.g. scanned picture or any other raster image.

In general, texture mapping is process which consist of:

• "inverse" mapping which transform any surface point to texture map domain

.m: D_m-->D_t, where D_m is surface region.

• transforming the texture coordinates to modulation space via map t.

2.2 Inverse mapping m

2.2.1 Triangular mesh

In Figure 1 the inverse mapping of point P located in triangle BCD to matching texture triangle is demonstrated. Point P can be expressed as follows:

P = B + w (C - B) + v (D - B);          u = 1 - v - w

(u, v, w) are barycentric coordinates of point P in triangle BCD. These coordinates can be obtained from the next formula:

Formulae for remaining coordinates v, w could be derived analogously. Computing the double multiple triangle area costs 2 multiplication’s (MUL) and 4 subtraction’s (SUB).

2 * area(ABC) = (A_x - B_x) * (A_y - C_y) - (A_y - B_y) * (A_x - C_x)

The areas of mesh triangles could be calculated in pre-process. If area of some triangle is 0, the triangle should be excluded from mesh. Thus, it is possible to say, that each barycentric coordinate costs 2 MUL, 4 SUB and 1 DIV operations.

After obtaining barycentric coordinates (u, v), matching point in texture domain P_t can be expressed as follows:

P_t = B_t + w(C_t - B_t) + (D_t - B_t),

where B_t, C_t, D_t are texture coordinates corresponding to vertices B, C, D. Total sum of arithmetic operations necessary to obtain P_t is 8*MUL + 2*DIV + 12*SUB + 2*ADD. It's clear that algorithm based on just this approach can not be fast enough.

2.2.2 Tetragonal mesh

We would like to show disadvantages of inverse mapping if tetragonal mesh is used to warn developers to use it.

There is possibility to consider that the tetragon ABCD in Figure 2 is bilinear patch. So for point P we can write:

P = (1 - v)[(1 - u)A + uB] + v[(1 - u)D + uC]

It is the system of two equations of type:

x = a_x + b_xu + c_xv + d_xuv,

y = a_y + b_yu + c_yv + d_yuv,

where:

P = (x, y)

a_x = A_x, a_y = A_y

b_x = B_x - A_x, b_y = B_y - A_y

c_x = D_x - A_x, c_y = D_y - A_y

d_x = A_x - B_x - D_x + C_x , d_y = A_y - B_y - D_y + C_y

To obtain (u, v) we can use the next formulas:

K = c_xd_y - c_yd_x,

L = d_xy - d_yx + a_xd_y - a_yd_x + c_xb_y - c_yb_x,

M = b_xy - b_yx + a_xb_y,

if K = 0, v = - M / L, else v = (- L - (L² - 4KM)^1/2) / (2K) and u = (x - a_x - c_xv) / (b_x + d_xv)

We are able to compute (u, v), but this computation costs too much processor time, because there are too many multiplications and also rather slow square root used. Since domain of square root is R⁺, it is necessary to distinguish whether tetragon is not degenerated to one line or non convex polygon. In case of degenerated rectangle we can not find solution always or we can not see some texture colors as it is shown in Figure 3. Bilinear transformation maps some texture coordinates outside the non convex tetragon ABCD. This fact excludes using tetragonal mesh which includes non convex tetragons, because result picture could contain fails (missing parts of texture)

2.2.3 Comparison of triangular and tetragonal mesh

A tetragonal mesh is not often used in 3D space, because 3D tetragon is not planar in general. Slightly different situation could come to being if our work domain is 2D space (vector editor). Tetragons are planar and it seems that work with tetragonal mesh in plane is more natural than work with triangular mesh. This tendency is caused by fact that also textures used to be rectangular. We have made decision to implement interaction with rectangular mesh and texture mapping algorithm which works with converted triangular mesh. The conversion is hidden from designer. Since no vertex can be created by mesh conversion, triangles can inherit texture coordinates from tetragons.

2.3 Problems of mapping to modulation space t

2.3.1 No color blending approach

This approach is good enough if the sample frequency (number of smallest elements able to have assigned color – pixels) of deformed mesh cell is similar to sample frequency of corresponding cell in texture "wallpaper". Example of a failure of this approach is shown in Figure 4 when mesh cell is sampled by quarter of texture sample frequency. The inverse map m maps each pixel in mesh cell to white texel.

2.3.2 Color blending

The solution of previous problem is blending of texture colors around the matching texture coordinates. Sample frequency of matching texture part is higher than sample frequency of mesh cell in case of demonstrated failure. So, squared radius of neighbourhood sphere could be obtained as fraction a/b (one possibility), where a is number of texels in matching texture part corresponding to mesh cell and b is number of pixels in mesh cell. Number of texels or pixels respectively is given by cell areas approximately. Texels which are closer to matching texture coordinates than obtained radius, should be blended. The right image which is corresponding to example in Figure 4 should be light grey square approximately, because each pixel should be colored by color which is obtained by blending 2x2 texels (64/16 = 4 = 2x2). The example of color blending of 4 colors is shown in Figure 5.

C = (1 - v)[(1 - u)C₁ + uC₂] + v[(1 - u)C₄ + uC₃]

If sample frequency of mesh cell is higher, it could be sufficient just to take the color of matching texel or it is possible to enhance picture quality by bilinear interpolation of closest texel colors as is shown in Figure 5 and Figure 6