Computer Graphics & Geometry
S.I.Vyatkin, B.S.Dolgovesov, A.V.Yesin, A.A.Zhigach, S.E.Chizhik, and R.A.Shcherbakov
Pr. Ak.Koptyuga, 1, Novosibirsk-90, 630090, Russia
Institute of Automation and Electrometry SB RAS
Phone: (3832) 33-36-30
e-mail:sivser@mail.ru, cse@iae.nsk.su, bsd@iae.nsk.su, esin@nsk.su, cse@iae.nsk.su
Contents
The problem of real-time photorealistic imaging is discussed. New techniques for specifying freeforms without their approximation by polygons or patches are considered. A recursive algorithm for object space division with masking of invisible surfaces and an effective technique of projective transformation for perspective imaging are proposed. The possibility to visualize 3-D scalar data arrays is shown. Examples of images obtained by modeling the work of the algorithm with different ways of defining the objects are presented.
Real-time computer graphics oriented to 3-D scene visualization has attained appreciable success nowadays. Though a sufficiently high realism of real-time scene imaging has been attained, some problems are still present (e.g., imaging of large terrain regions), where it is necessary to store and visualize scenes containing a greater number of polygons than it is implemented in the present-day systems. For instance, the problem of imaging of mountains requires for initial description hundreds of thousands of polygons. On the other hand, exact modeling of shapes of the car, airplane, submarine frames requires thousands of spline-surfaces (curvilinear areas defined by polynomial functions) whereas the case of definition by polygons will require tens and sometimes hundreds of thousands of polygons. Moreover, polygonal 3-D graphics with scanning of polygons in the image plane is not three-dimensional in the full sense of the word. Information presented to the user in such an approach is incomplete. The main point is the absence of information on object depth. This case implies not the absence of the Z-coordinate of the surface point but the absence of information about the beam passing through the object.
Presently, some authors [1-6] investigate the function representation of objects visualized, which allow substantial reduction of databases for a certain class of objects compared with the polygonal definition. However, real-time imaging of objects represented in such a manner is concerned with substantial growth of computations because of the high order of the defining functions.
In this paper we present results of some investigations concerned with modeling of a system in which it is proposed, to use along with the polygonal representation, object representation by freeforms in the form of real and scalar functions and volume spaces of voxel arrays. The possibility of freeform volume visualization is investigated. A recursive algorithm of rendering with object space division and multilevel masking with regard to perspective is proposed for visualization.
2. Representation of object freeforms.
The characteristic feature of the proposed freeform representation is, firstly, the fact that the main primitives are presented by second-order surfaces, i.e., quadrics. A primitive-quadric is the basis for constructing the rest of objects. The quadric is defined by a real continuous descriptive function of three variables (x1, x2, x3) En in the form F(X) ³ 0. Quadrics are considered as closed subsets of the Euclidean space En defined by the descriptive function F(X) ³ 0 where F is the continuous real function; X= (x1,x2,x3) - is the point at En specified by the coordinate variables. Here F(X) > 0 specifies points inside the quadric, F(X) = 0 – the points at the boundary, and F(X) < 0 - the points lying outside and not belonging to the quadric. Using the quadrics, the first class of freeforms is constructed with the use of real perturbation functions. This type of freeforms is suitable in generation of artificial (man-made) objects. Secondly, the second class of freeforms is proposed with the use of scalar perturbation functions with respect to the basic plane or the quadric, for example, to generate a terrain or sculpture models.
2.1. Perturbation functions in the implicit form.
It is proposed to describe complex geometric objects by defining the function of deviation (of the second order) from the basic quadric in the form:
F(x,y,z) = A11x2 + A22y2 + A33z2 + A12xy +A13 xz + A23yz + A14x + A24y + A34z + A44 ³ 0
Freeforms are constructed on the basis of quadrics. The freeform is a composition of the basic quadric and the perturbation F’(x,y,z) = F(x,y,z) + R(x,y,z), where the perturbation function R(x,y,z) is found as follows:
R(x,y,z,)=Q2(x,y,z) if Q(x,y,z)>0
0 otherwise,
where Q is the perturbing quadric. A perturbed quadric (freeform) can be also considered as Q. In other words, the composition of the basic quadric and the deviation function is a new perturbation function, i.e., a derivative for another basic quadric. Since max[Q + R] £ max[Q] + max[R], this means that to estimate the maximum Q on some interval, we must calculate the maximum perturbation function on the same interval.
Fig.1
The surface obtained will be smooth (Fig.1), and a small number of perturbation functions will be necessary to create complex surface forms. The figure shows a result of modeling a scene object by means of freeforms, whose description required 4Kbyte information, which is 500 times less than the polygonal description that would take 2Mbyte information. Thus, the problem of object construction reduces to the problem of quadric surface deformation in a desired manner rather than to approximation by primitives (polygons or patches represented by B-spline surfaces). In addition, while solving the descriptive function in the form of inequality F(X) ³ 0, we can visualize not only the surface but also the internal structure of the object (Fig. 2).
Fig.2
2.2. Perturbation functions in the scalar form.
It is proposed to describe complex geometric objects by defining (in the scalar form) the second-order function of deviation from the basic surface or (in the simplest form) from the basic plane. A terrain is a particular case of such objects; it is defined by means of the basic plane and the perturbation function defined in an infinitely long parallelepiped. Values of the perturbation function are specified at the parallelepiped cross-section by a 2-D height map. As a basic surface we may use a plane, then the direction of the carrier plane normal must match the longitudinal direction of the parallelepiped - the region of perturbation function definition (Fig. 3).
Fig.3
Since during rendering it is necessary to estimate the maximum function on a three-dimensional or one-dimensional interval, then maps of the level of detail are preliminary composed for efficient calculation. The initial data form the level n if the array dimension is 2n x 2n. Data for the level n-1 are obtained by choosing a maximum from four adjacent values of the level n, the rest three values are not considered further, i.e., we obtain a 2n-1 x 2n-1array. The zero level consists of only one value, that is, the maximum all over the height map. The process of preparing the maps of levels of detail is shown schematically in Fig.4.
Fig.4
Fig.5
Fig.6
While determining the perturbation maximum, we calculate the characteristic size of the current interval projection, which governs the level of detail. A cruder approximation of the initial function is chosen for a larger interval. If a more accurate representation is required, then we perform bilinear or bicubic interpolation of values of heights from the last level of detail. Figure 5 shows a result of voxel-based terrain modeling without preliminary triangulation with bilinear interpolation of height values. Figure 6 presents a result of object modeling with a scalar perturbation function with respect to the cylinder with bicubic interpolation of height values.
Application of projective transformation extrapolates the rendering algorithm to pyramidal volumes and thereby allows us to generate images with perspective. In 3D space, the point with the Cartesian coordinates (x, y, z) is associated with an infinite set of homogeneous coordinates (x’, y’, z’, a) such that x=x’/a, y=y’/a, z=z’/a i.e., the homogeneous coordinates are determined within a common nonzero factor. Special interest presents the transformation matrix affecting the homogeneous coordinates in the following manner:
or (C)(M) = (P),
where (C) is the transformation matrix; (M) are the homogeneous coordinates of the point of the space M; (P) are the coordinates at P corresponding by the mapping. Within the scope of projective geometry, a theorem is proved that the projective mapping of the space M to the space P is unambiguously defined by specifying five pairs of points corresponding by the mapping provided that from five points specified in the space M none four points are in the same plane. Let us choose five pairs of such reference points (Mi) and (Pi) (the upper index corresponds to the number of pair) and compose the set of equations:
(C)(Mi)= ri (Pi),
where i = [1,...,5], r1, r2, r3 and r4 are the unknown factors; r5=1. Solving these equations, find the coefficients of the projective transformation matrix (C) used further to transform the geometric primitives.
In this paper we used the multilevel ray casting algorithm [7], which performs efficient search for volume elements - voxels which participate in image generation. At the first step of recursion, the initial viewing pyramid is divided into four smaller subpyramids in the screen plane. At the stage of division of space along the quaternary tree, 2-times compression and transfer by ±1 along two coordinates are performed:
A11’ = A11/4;
A22’ = A22/4;
A33’ = A33;
A12’ = A12/4;
A13’ = A13/2;
A23’ = A23/2;
A14’ = A14/2 + i A11/2 + j A12/4;
A24’ = A24/2 + i A12/4 + j A22/2;
A34’ = A34 + i A13/2 + j A23/2;
A44’ = A44 + i A14/4 + j A24/4;
A44’’ = A44’ + i A14’/2 + j A24’/2.
If in the equation of quadric Q(x, y, z) = 0 the values of the variables x, y, z vary within the length [-1, 1], then
max[ |Q(x, y, z) – A44| ] £ max F = |A11|+|A22|+|A33|+|A12|+|A13|+|A23|+|A14|+|A24|+|A34|
We should note that if |A44| £ max [ |Q(x, y, z) – A44| ] £ max F, then, probably, a point M0 = (x0, y0, z0) ( -1 < x0, y0, z0 < 1 ) exists such that Q(x0, y0, z0) = 0. If maxF < |A44|, then such points do not knowingly exist, and the sign of the coefficient A44 distinguishes location of the pyramid inside or outside with respect to the quadric surface Q=0 (if A44 ? 0, then the subpyramid is inside the quadric). Using results of this test, we perform division of subpyramids that fall within the quadric completely or, probably, partially, and the knowingly external subpyramids are eliminated from processing. A test for intersection of subpyramids with freeforms is somewhat different. For the basic quadric the test for intersection looks as follows:
if ( ( A44+R ) < 0 ) && ( |A11|+|A22|+|A33|+|A12|+|A13|+|A23|+|A14|+|A24|+|A34| < -(A44+R ) ) then the subpyramid is outside.
Here R is the maximum perturbation function on the current interval; Aij - are the coefficients of quadratic function. The following test is performed for the perturbation function:
if ( |A11|+|A22|+|A33|+|A12|+|A13|+|A23|+|A14|+|A24|+|A34| < |A44| ) then the subpyramid is outside of the range of definition of perturbation,
Fig.7
where Aij - are the coefficients of the quadratic perturbation function, and a value of R is additionally calculated and added to the basic function. If the intersection is determined, then the subpyramid is subject to the next recursion level. Subpyramids that do not intersect with the object are not subject to further immersion to recursion, this corresponds to elimination from consideration of square screen spaces which the subpyramid (and, consequently, the object surface) is not mapped to (Fig. 7). The viewing pyramid is subdivided until reaching the maximal set level of recursion. The technique has an advantage that it allows discard of large parts of empty space at an early stage. While searching for voxels containing the imaging object surface areas, the pyramidal space is traversed along the quaternary tree whose leaves are roots of binary trees. Masking is used during traverse of the tree in the case of opaque objects. The multilevel ray casting technique allows us to determine effectively and quickly belonging of rays of different levels (pyramids) to surfaces, and discard space regions outside the objects.
While visualizing the surfaces a test is verified for belonging of only intersected voxels (unit volume elements), external and internal voxels are discarded. To improve imaging realism and extend the class of objects imaged (translucent structures with internal density distribution, 3-D textures), it is necessary to image the internal translucent object structure. For this purpose, not only voxels lying on the surface but also voxels inside the object must participate in imaging. Therefore, while dividing the volume the internal object parts are not discarded, for them algorithm recursion is performed further. Scanning of the scene along the Z-coordinate, which corresponds to scanning of the volume through the depth, is not interrupted upon meeting the surface but is continued until the volume is scanned completely or a certain value of transparency higher than a threshold value is stored. To reduce the computation time the algorithm is adapted to quick passage of homogeneous spaces of objects, for which it is unnecessary to scan the volume completely reaching the last recursion level, it is necessary to “skip” empty or homogeneous spaces along the Z-coordinate and immediately calculate the color and the total transparency. Since ray passage through empty space makes no contribution to the final image, then the skip of the empty space is able to make the processing substantially fast and does not affect the image quality.
Calculation of all color components of a pixel is performed in the same manner by the following formula:
C = (QambiCambi + QdiffCdiff + QspecCspec) / (Qambi + Qdiff + Qspec);
where “ambi” refers to characteristics of ambient light, whereas “diff” and “spec” refer to the diffused and specular components of reflected light, respectively; C are the color components; Q are the weight coefficients. Color components are calculated by a vector light model. Four vectors are involved in the calculation: normal to the surface (n), vector to the light source (l), reflected light direction (r) and vector to the viewer (v):
Cdiff = (n, l) Clite Csurf;
Clite - is the light source color; Csurf - is the surface color;
Cspec = (r, v)p Clite;
p - is the coefficient of surface irregularity.
While modeling the light transmittance through translucent media we may disregard the reflection and attenuation of reflected beams in order to reduce the amount of calculation. When only the reflection and attenuation of light remain in the path from the object to viewer - eye, the formula used to calculate the pixel color can be written as follows:
where 
the final pixel
color, and 
can be r, g or b (i.e., red,
green or blue, respectively); 
is the n-th
voxel intensity calculated by the Phong model; 
is the n-th voxel transparency; 
is the reflected light from the first point at the scanning beam; 
is the ambient color,
and 
. We can follow the
threshold excess in the following manner: if at the k-th step the total transparency 
becomes below some 
then the contribution from all voxels following behind the k-th
voxel will be small, that is why we may stop scanning.
In order to allow for perspective, we must make a correction in the algorithm of color accumulation in pixel. The fact is that as a result of transformation of geometric primitives the voxel sizes become dependent on the Z-coordinate, that is why converting the color in the pixel we must also convert the transparency of voxel making correction for the change in its length.
Our investigation in the volume-oriented visualization technology have made it possible to reveal some advantages in both the scene representation technique and the rendering algorithm oriented to real-time implementation. The change over from rasterization in the image plane “back-end” or the image-space end of the graphics pipeline) to volume rendering, (“fronted” or the object-space end of the graphics pipeline) in combination with the proposed object definition techniques, though increases the amount of real-time computation, as a whole, nevertheless it results in some merits improving the scene imaging realism. The main merits of our approach are the following:
All these merits of our approach form the ground for creating a new class of computer visualization systems for various applications [9]. Preliminary estimates have shown that for implementation of the systems it is desirable to develop three custom VLSIs integrating about 15-20 millions of transistors. The first type and second of VLSI is a pipelines of same-type processors, the third type is designed to compute a color, fog, texture, and to filter pixels. The system is characterized by a high parallelism, homogeneity, and vectorization of computation.
The proposed algorithm of rastering along with the possibility to visualize arbitrary surfaces of freeforms and inhomogeneous volume spaces offers a wide scope of application.
Computer Graphics & Geometry