Dynamic Distortion Correction with Viewpoint Motion

Computer Graphics & Geometry

Dynamic Distortion Correction with Viewpoint Motionnd Non-Static Attitude of Projector

Sergei I. Vyatkin
Institute of Automation and Electrometry SB RAS, Novosibirsk, 630090 Russia
Computer Arts Lab, University of Aizu, Aizu-Wakamatsu, 965-8580 Japan
sivser@mail.ru

Sergei E. Chizhick
Institute of Automation and Electrometry SB RAS, Novosibirsk, 630090 Russia
cse@albatros.iae.nsk.su

Carl W. Vilbrandt
Computer Arts Lab, University of Aizu, Aizu-Wakamatsu, 965-8580 Japan
vilb@u-aizu.ac.jp

Contents

Abstract
1. Introduction
2. Multi-agent systems in design

Abstract

Many military simulator applications, visual systems for virtual planetariums and future movies will require the generated image to be free of distortion regardless of where in some allowable volume the observer's eyepoint lies. Under distortion is understood nonlinear garbling an expressing, visible watcher, a non-flat caused by presence projection surface (projection dome), optical system characteristics and electronic blocks of projector. The dome usually is a twenty foot diameter sphere and is coated with a high-gain sheeting. An image drawn on the projection plane (the frame buffer) is scanned out on the surface of the dome. The resulting image is then reprojected onto the viewplane. Distortion is introduced by the lens, the non-planar dome, and possibly the projector's electronics and CRT as well.

Our approach is oriented on tasks that require extreme computational capabilities. It is a promising one for future development taking into consideration dramatically improving technology.

Additional Keywords: spherical perspective, dynamic distortion correction, non-linear image mapping, dome.

Introduction The surrounding space of a watcher is spherical [1]. So the most natural display of a surrounding ambience is a spherical perspective. A scene on the sphere can be built by means of the algorithm of ray tracing, but it is very slow. In building a wide angle image on the sphere, it is necessary to use adaptive visual algorithms for synthesis of spherical expression [2]. Primitives as they are now used by graphic accelerators are represented by flat triangles, boundary representation (B-rep), which are limited by straight lines and are not suitable for non-linear image mapping (NLIM) onto the dome [3]. There is a solution of the given problem very important for image transfer directly into the eye of the observer by laser. In the future, personal laser projection devices can change a personal computer display. Since the distortion mapping is in general different for each eyepoint, some means of locating the eyepoint is necessary. A head-tracking device fitted to the pilot's helmet is the usual solution. A more difficult problem lies in determining what the distortion mapping looks like from each viewpoint and inverse mapping.

Let us define a distortion function D(x,y) that maps a point on the projection plane to a point on the viewplane. Correcting the distortion due to D requires us to find the inverse distortion function D¯¹(x,y) and applying it to the original undistorted image (D(D¯¹(x,y))=(x,y) for an inverse mapping). If the viewpoint is dynamic, D is in general different for every viewpoint. The systems that provide distortion correction assume only a static viewpoint. When the pilot's eye is located at the design viewpoint, the image will be free of distortion. As the eye is moved further and further away, the image becomes progressively more distorted [4].

In this paper two approaches for dynamic distortion correction are considered. These approaches correct an image not only for a dynamic viewpoint but also for a dynamic projector. Both approaches are based on the representation of a polygon edge in the projector plane by a curve (see section 2), which is a projection of the spatial curve of the intersection of the dome with the plane containing the polygon edge and the origin of the viewer coordinates (edge plane). This representation makes it possible to use rather simple rasterizing algorithms based on quaternary subdivision (see section 3).

In the first approach, every polygon edge is described by a pair of equations:

Ax²+ 2Bxy + Cy²+ 2Dx + 2Ey + F = 0, (1)

ax + by + c = 0. (2)

The coefficients A,...F, a,.c of both equations are computed during the geometry transformations. The second equation defines the intersection of the projector plane with the plane containing the projector coordinates origin, and the intersection is parallel to the edge plane (see section 3.1).

In the second approach (see section 3.2), a polygon edge is treated as some curve described by a parametric equation of the type:

Ax + By + C + Dt(x, y) = 0, (3)

where A,B,C,D are edge coefficients obtained from the geometry transformations, and t(x, y) is a parameter depending non-linearly on x,y (see section 5). This parameter is used for computation texture coordinates, linear interpolation intensity (see section 4).

2. Using curves of second degree
This approache is based on the representation of a polygon edge in the projector plane by a curve. There are a restrictions of the method:

The dome is approximated by a surface of the second order:

A_dx² + B_dy² + C_dz² + D_dxy + E_dyz + F_dxz + G_dx + H_dy + I_dz + K_d = 0; (4)

Distortion of the projector is small (we consider that the projector has an apparatus for non-linear distortion correction, introduced by the lens and the projector’s electronics as well).

Note.

An equation of a curve of the second order (1) determines the line of a polygon on the projector's plane if the origin of the system coordinates does not belong to the plane of edge.

The linear equation (2) is used:

for clipping of imaginary branch of hyperbola;

for determination of the line of edge if the origin of the system coordinates of the projector belongs to the plane of edge.

Geometric transformations for computation of quotients of equations (1),(2):

Vector transformation to the observer's system coordinate:

Computation of equations of the plane of edges.

Fig.1

_vi

_vi+1

_vi

_vi+1

Transformation of equations of the planes of edges to the projector's system coordinates.

Computation of quotients of equations (1), (2).

A_px + B_py + C_pz + D_p = 0. (8)

Then a quotients of equation (2) are:

a = A_p, b = B_p, c = C_p. (9)

Fig.2 Let the point on the projector's plane be described by vector V=(x, y, 1). If we extend V up to the intersection with the plane of edge (Fig.2), we obtain a new vector Vp=(p(x, y)*x, p(x, y)*y, p(x, y)),

where p(x, y) a parameter:

p(x, y) = D_p / (A_p*x+B_p*y+C_p). (10)

Substituting of coordinates of vector V_p into (4) with (10), gives us quotients of equation (1):

A = D_p²A_d + D_pA_pG_d + A_p²K_d; (11)

B = D_p²D_d + D_pA_pH_d + D_pB_pG_d + 2A_pB_pK_d;

C = D_p²B_d + D_pB_pH_d + B_p²K_d;

D = D_p²F_d + D_pA_pI_d + D_pC_pG_d + 2A_pC_pK_d;

E = D_p²E_d + D_pA_pI_d + D_pC_pH_d + 2B_pC_pK_d;

F = D_p²C_d + D_pC_pI_d + C_p²K_d.

For determination of the point position of the plane of the projector relative to the line of edge of a polygon, let us write the next conditions:

Sign[Q(x, y)] = 1 is the point on the plane of edge, determined by vector V_p(Q(x, y): equation (1)), located inside dome;

Sign[D_p] = 1 is the projector is in half a space with polygon (if D_p=0 Sign[D_p] = 0);

Sign[ax+by+c] = 1 is the point on the plane of projector, determined by vector V, located in the area of minus values of equation (2).

The result of analysis of the combinations of conditions is shown in the table:

Sign [ax+by+c]	Sign [Dp]	Sign [Q(x,y)]	Position of test point
0	0	0	Outside polygon
0	0	1	On the polygon side
0	1	*	On the polygon side
1	0	*	Outside polygon
1	1	0	On the polygon side
1	1	1	Outside polygon

3. Synthesis of virtual environment with image-plane recursive subdivision

We used the quaternary searching tree (quadtree) algorithm [5], [6], [7] which performs an efficient search for picture elements - pixels which participate in image generation. At the first step of recursion, the initial window (screen) is divided into four smaller subwindows (cells) in the screen plane. Using results of the intersection test, we perform division of cells that fall within the polygon completely or, probably, partially, and the external cells are eliminated from processing. For a test for intersection of cells with edges of polygons, see below. If the intersection is determined, then the cell is subject to the next recursion level. Cells that do not intersect with the polygon are not subject to further immersion to recursion; this corresponds to elimination from consideration of square screen spaces which the polygon surface is not mapped to (Fig.3).

Fig.3 The viewing window is subdivided until reaching the maximal set level of recursion. The technique has an advantage in that it allows us to discard large parts of empty space at an early stage. The quadtree technique allows us to determine effectively and quickly cells of different levels belonging to surfaces, and discard space regions outside the objects. Analyzing mutual disposition of i-level cell Qi and polygon, we can meet the following situations (Fig.4):

Qi is outside the polygon. All screen space corresponding to Qi is omitted from further consideration.

Qi is inside the polygon, that is, all Qi pixels belong to the polygon.

Qi is partially covered with the polygon. Qi is called " intersected " and is subdivided into four cells of i+1 -level. New cells should be analyzed further.

Fig.4 Identification of "inner" cells on each step of the subdivision can be used for multilevel masking.

3.1 Rasterization of polygons defined by second order curves
Firstly let us write an equation of straight line (2): ax + by + c = 0.

3.1.1 Transformation of coefficients of a straight line to local coordinates of Qi cell during subdivision of cell Qi-1

3.1.2 Determination of Qi cell position of a straight line

ЅіЅ

Ѕ<Ѕ

3.1.3 Transformation of coefficients of a second order curve to local coordinates of Qi cell during subdivision of cell Qi-1

3.1.4 Determination of Qi cell position of a second order curve

ЅіЅ

іЅ

ЅіЅ

Note the main advantages of the prescribed rasterizing algorithm:

ultimate simplicity of implementation ( only additions and shifts are used );

no dynamic and static tables;

algorithm can be adapted to massively parallel computations.

Note: When the field-of-view is greater than 180 degrees, the Z-buffer can't resolve the depth of the polygons that necessarily intersect the z = 0 plane. The R-buffer solves this problem by calculating the true range from the eye point to the points on the two objects to be resolved.

3.2 Rasterization of polygons defined by parametric equation
Let us repeat the computations of steps 1-3 from item 2, then we can write an equation of the plane of edge in projector system coordinate (7):

A_px + B_py + C_pz + D_p = 0. (19)

Let any point in the plane of the projector be described by vector V=(x, y, 1). If we extend V up to intersection with dome (Fig.5), we obtain a new vector V_d=(x/t(x, y), y/t(x, y), 1/t(x, y)), where t(x, y) – any parameter (see item 5). Substitution of coordinates of vector V_d into (19), gives us an equation (3):

Ax + By + C + Dt(x, y) = 0,

where A=A_p, B=B_p, C=C_p, D=D_p.

Fig.5 We introduce an equation of "strip" (i.e., set of parallel straight boundaries which characterize curvature of the polygon edge relative to a certain set of projection plane points). This equation allows us to determine the position of a cell of i-level of subdivision Qi relatively to a polygon edge.

Ax + By + C(i) + D(i)t(i, j) ± D(i)Et(i) = 0, (20)

Notations:

A,B is the coefficients for x,y from original equation.

C(i) is a free ter m of linear part of i-level equation.

D(i) is the coefficient for non-linear part of i-level equation.

t(i,j) is the average value of t(x,y) for cell with number j of i-level of subdivision ( Look-up-table ).

Et(i) is a value characterizing spread of parameter t(x,y) inside an i-level cell (the same value assigned for all cells of a subdivision level).

Note that Et(i) value decreases when passing from i-level to i+1 -level (i.e., to "smaller" level). Finally, this provides the required rasterizing accuracy.

3.2.1 Transformation of coefficients to local coordinates of Qi cell during subdivision of cell Qi-1

3.2.2 Determination of Qi cell position

Ѕ>Ѕ

relatively simple geometry transformations;

possibility to adapt parameter t(x,y) to peculiarities of a dome.

dynamic look-up table (or static one for a static projector) is required to store t(x,y) values;

multiplication is required.

4. Texturing

Consider geometric transformations of parameters of a polygon as only one example in texture coordinate. In the object system, coordinates assigned are:

1) An equation of plane of polygon:

N_zo*(x, y, z) + D_zo = 0, where N_{zo -} vector of normal;

D_zo- it is the distance up to the plane into direction N_zo.

2) An equation of plane of zero values of texture coordinate:

N_uo*(x, y, z) + D_uo = 0, where N_uo- vector of normal;

D_uo- it is the distance up to the plane into direction N_uo.

An equations 1) and 2) in the observer’s system coordinates are:

N_zv*(x, y, z) + D_zv = 0, (23)

N_uv*(x, y, z) + D_uv = 0,

N_zv = N_zo*T_r; N_uv = N_uo*T_r;

D_zv = N_zo*T_m + D_zo; D_uv = N_uo*T_m + D_uo;

T_r is a suitable rotation matrix; T_m is a suitable vector describing a shift.

An equations (26) can be written as:

A_zvx+B_zvy+C_zvz+D_xv=0, A_uvx+B_uvy+C_uvz+D_uv=0.

Let us introduce new quotients:

A_zt = A_zv/ |D_zv|; B_zt = B_zv/ |D_zv|; C_zt = C_zv/ |D_zv|; A_ut = A_uv + D_uvA_zt;

B_ut = B_uv + D_uvB_zt; C_ut = C_uv + D_uvC_zt;

Then we obtain the expression for computation of texture coordinate on the observer's plane:

U=(A_utx+B_uty+C_ut) / (A_ztx+B_zty+C_zt). (24)

Similar for intensity:

I=(A_itx+B_ity+C_it) / (A_ztx+B_zty+C_zt). (25)

Let us find numerator and denominator of fractional-linear function (27) with coordinates x, y on the projector's plane:

U=(A_ux+B_uy+C_u+D_ut(x, y))/

(A_zx+B_zy+C_z+D_zt(x, y)); (26)

A_z, B_z, C_z is the components of the vector N_z; A_u, B_u, C_u is the components of the vector N_u;

t(x, y) is the parameter of a non-linear function x, y (see section 5);

N_z = N_zt*M_r; D_z = N_zt*V_m; N_u = N_ut*M_r;

D_u = N_ut*V_m, (27)

M_r is a suitable rotation matrix; V_m is a suitable vector describing a shift;

N_zt is the vector (A_zt, B_zt, C_zt); N_ut is the vector (A_ut, B_ut, C_ut).

The final formula for intensity computation is:

I=(A_ix+B_iy+C_i+D_it(x, y)) /

(A_zx+B_zy+C_z+D_zt(x, y)); (28)

The Geometry Processor must compute for each parameter of polygon (texture coordinate, interpolation function of intensity) four quotients (Au.. Du...) plus four quotients of coordinate z (Az.. Dz).

5. Computation of t(X,Y)
If the dome is approximated with a second order surface, then t(X,Y) is reverse to the positive root of quadratic equation:

at² + bt + c = 0; (29)

1/t = (-b± (b²-4ac)^1/2) / 2a;

a = A_dx² + B_dy² + C_d + D_dxy + E_dy + F_dx;

b = G_dx + H_dy + I_d;

c = K_d.

Here x, y are coordinates of a projection plane point, and A_d,..,K_dare coefficients of the second order surface (4).

Computations (29) are too difficult. For a dynamic projector and 2kґ 2k resolution, it is required to compute at least 256k accurate values of t(x, y) per frame if we assume that all other t(X,Y) could be achieved through bilinear interpolation. Thus, we suggest another method to determine t(X,Y) which requires far less number of operations.

Draw horizontal lines L(0),...L(i) in the projection plane (Fig.6).

Fig. 6 Each line contains set of node points S(i,0),...S(i,j), where the parameter t(x, y) should be determined - t(i, 0)..t(i, j). Construct a plane P(i) which contains the projector coordinates origin and given line L(i). Equation for intersection line L_d(i) of the plane P(i) with the dome is the following:

A(i)x²+B(i)xy+C(i)y²+D(i)x+E(i)y+F(i) = 0, (30)

where

A(i) = A_dR₀²+B_dR₃²+C_dR₆²+D_dR₀R₃+E_dR₃R₆+F_dR₀R₆;

B(i)=2A_dR₀R₁+2B_dR₃R₄+2C_dR₆R₇+D_d(R₀R₄+R₁R₃)+

E_d(R₃R₇+R₄R₆)+F_d(R₀R₇+R₁R₆);

C(i) = A_dR₁²+B_dR₄²+C_dR₇²+D_dR₁R₄+E_dR₄R₇+F_dR₁R₇;

D(i) = G_dR₀+H_dR₃+I_dR₆;

E(i) = G_dR₁+H_dR₄+I_dR₇;

F(i) = K_d;

Notations:

A_d..K_d is the coefficients of the equation dome which is posed in the projection coordinates.

R₀..R₇ is a set of the coefficients for matrix to rotate the projector coordinate system (unique for every line L(0)...L(i)).

Therefore, a straight line L_s(i, j) is set in the plane P(i). This straight line goes through the projector coordinate origin and through the point S(i,j). The task is to determine Y is the coordinate Y(i,j) of the intersection of the straight line L_s(i, j) with the second order curve L_d(i) and to compute t(i,j) by formula:

t(i, j) = (Y(i, j)cos(a (i)))^-1, (31)

where a (i) is an angle between the plane P(i) and the plane which contains x and z axis of the projector coordinate system. To determine Y(i,j) we shall use a method of step-by-step approximation.

Subdividing the plane P(i) into rectangular cells (i.e., using quaternary tree subdivision), find a minimal size cell which is intersected both by L_s(i, j) and L_d(i). Here number of levels of subdivision is governed by accuracy (capacity) of Y(i,j). The main advantage of this method for computation t(x, y) is that it can be implemented on hardware similar to rasterizing hardware if coefficients A(i)...F(i) will be supplied by an external evaluator.

6. Conclusions

To perform correction for changing eyepoint in a spherical dome, extra computations in the Geometry Processor and Video Processor are required. The Geometry Processor must transform from (X,Y) to (U,V) coordinates and the Video Processor does the reverse. There are two sources of nonlinearity in the transformation: one is the non-linear projection lens and the other is the spherical (nonplanar) dome. For the projection lens both Processors must use a look-up table with bilinear interpolation. In the case of the Video Processor, the distortion correction for the spherical dome can be built into this look up table as well. But in the case of the Geometry Processor, this cannot be done because the exact distortion from the dome depends on the eyepoint in the dome, which is dynamic. Correction for the spherical dome distortion in the Geometry Processor requires increased overall computational complexity. Thus, we suggest a new method to determine t(X,Y) which requires far less number of operations. Figure 7 shows distortion simulation (view from space through optic device).

References

A. M. Kovalev On central projections of three-dimensional space // Autometry. 1996. N6. P. 4.
A. M. Kovalev On number of elements of expressing of into view watcher // Autometry. 1997. N3. P. 30.
Lizabeth K. Coe “Project to improve performance of the NASA/AMES ACAB Visual Pipeline”. Presented at the IMAGE V Conference, Phoenix, Arizona, 19-22 June 1990.

A.M. Kovalev “Virtual Reality in Spherical Perspective” // Graphicon’98 Proceedings, S. Klimenko et al. (Eds). Moscow 1998.

A.E. Asmus, A.I. Bogomyakov, S.I. Vyatkin et al. Video-Processor of Computer System Visualization “Albatross” // Autometry - N 6. 1994.

S.I. Vyatkin, B.S. Dolgovesov, A.F. Rozhkov et al. Algorithms of Visualization for Real-Time Visual Systems // Graphicon’95 Proceedings, S. Klimenko et al. (Eds). St-Petersburg 1995.

S.I. Vyatkin, B.S. Dolgovesov, B.S. Mazurok et al. An Effective Rasterization Method for Real-Time Computer System Visualization // Autometry - N 5. 1993.

Computer Graphics & Geometry