A 3D TEXTURE-BASED RENDERING ALGORITHM

S.I. Vyatkin

Institute of Automation and Electrometry SB RAS, Russia

sivser@mail.ru

 Contents

• Abstract
• 1. Introduction
• 2. Texture mapping
• 2.1. Calculation of the texture level of detail
• 2.2 Trilinear interpolation
• 2.3 Contour textures
• 2.4 Texture addresses
• 3. Function-based objects
• 3.1 Set of geometric objects
• 3.2 Set-theoretic operations
• 3.3 Recursive multi-level ray casting algorithm
• 4. Texture mapping onto freeforms and volumes
• Conclusion
• References

Abstract:

The problem of mapping a 2D texture array onto an arbitrarily oriented plane in 3D space and onto curvilinear surfaces is considered. The method of mapping a 3D texture array onto freeform and volumes is considered. High-speed and effective algorithm of volume rendering is proposed. New methods of object representation by using unified free forms and arbitrary algebraic surfaces are suggested as well. Proposed algorithm allows to lower complexity of computations, memory and bandwidth requirements in comparison with known methods. In this paper, we propose a texture memory management policy that substitutes the classical assignation policy of one texel per voxel, applied for the volume representation in texture space. The texture is an object (not mapped) changing the properties of another object. The feature of the texture is that any object may be the texture. A supplement to the data structure with consideration of the structure is that each object can have a reference to another object being a texture for it.

Key words: 3D Texture, Volume Visualization, Recursive Multi-Level Ray Casting. 

1. Introduction

Virtual reality systems, where viewer merges into the model world, require high quality visualization. Voxel-based methods have been developed which create a 3D view directly from the volume data. For the first time on PC-class computers, the VolumePro 500 and VolumePro 1000 accelerators by TeraRecon Inc. allow high quality, real time volume rendering (30 frames/sec.) [1].
The surface-based methods first create on intermediate surface representation of the object to be shown. Both surface-and voxel-based methods have their merits; the decision, which one should be used for a particular application depends on the visualization goals. We present a 3D texture-based recursive multi-level ray-casting algorithm for rendering of volume data like voxel data and real continuous functions.

2. Texture mapping

Texture mapping on surfaces is an affective method for increasing realism in computer graphics systems. The textures allow one, first of all, to simulate a color pattern on surfaces, and also transparency, sharp boundaries, moving objects, and many other special effects. The texture increases appreciably the image visual complexity for a rather small amount of calculations.

The term “texture” is defined in computer graphics as a 2D image transferred onto a 3D plane or a 3D curvilinear surface, or a 3D image mapped onto a 3D space.
Texture mapping includes geometrical mapping of a texture array onto a surface and image filtering that eliminates step lines, moires, and all other things referred to as aliasing in the literature on computer graphics.

The process of texture mapping on flat faces consists of two stages. The first stage is projective transformation, i.e., calculation of the texture map coordinates (u,v) corresponding to the coordinates (Xs,Ys) of pixel on the screen. The plane is parameterized if one sets on it the unit texture vectors U and V, and the reference point. The problem is that knowing the screen coordinates (Xs,Ys) to obtain the texture coordinates U and V  of the respective point of the plane in the coordinate system of the viewer. This transformation may be written in the matrix [2]:

                                            (1)

The texture coordinates are related to the screen coordinates by the bilinear function

,                                                                                      (2a)

,                                                                                      (2b)

where (Xs,Ys) are the screen coordinates of a pixel; Ai, Bi, and Ci are the elements of the coordinate transformation matrix.
The second stage of texture mapping is filtering necessary for preventing aliasing. MIP-map (pyramidal) texture maps that are most suitable for hardware implementation are most frequently used [3].

By means of prefiltering, one obtains a set of square texture maps with different resolution for each object. Each texture map is associated with an integer value of the level of detail (LOD).
Depending on the distance to the face and its orientation, one chooses for work two texture maps with neighboring levels of detail. The criterion for the choice is the linear size of pixel projection onto the face. If the pixel projection covers less than two texels (texel is a texture map element), one observes aliasing. For faces with angles of inclination (between planes of the face and the screen) close to the right angle the texture pattern is heavily blurred. This effect is known as blurring [2]. 

 2.1 Calculation of the texture level of detail

The major axis of the ellipse is on the line of intersection of two planes. One of them is the textured plane, and the other is the plane in which the normal to the plane and the ray of vision lie. From this it follows that Æ = 2dD/ cosq, where q is the angle between the normal to the plane and the ray of vision; cosq = d/D (d is the distance from the origin of coordinates to the plane, and D is the distance from the viewer to the point of intersection of the ray of vision with the object surface). Hence,

 Æ = 2dD²/d » 2dZ²/d.          (3)

2.2 Trilinear interpolation

To obtain the final result, i.e., the color and the transparency in each pixel, we must perform trilinear interpolation [3]:

	,	(4a)
		(4b)
	,	(4c)
		(4d)
		(4e)
		(4f)
		(4g)

where fα, fβ are fractions of the texture coordinates of a high level of detail; cα, cβ are fractions of the texture coordinates of a low level of detail; c[cu,cv], f[fu,fv] are the values of color components at the point [u,v] for each of the levels of detail.

2.3 Contour textures

The contour texture must provide the possibility of creation and mapping of contours with an arbitrary shape within the frames of the texture map, which do not blur upon approaching. Such a texture is applied for mapping letters, symbols, interfaces, etc. We will list the main properties of contour texture maps:

·         contour width is 1-2 pixels;

·         when approaching, the real value of LOD is negative;

·         the contour does not blur, the contour width remains the same;

·         in the region with non-negative values of LOD, the contour textures transform to usual ones, that is, RGBT textures;

·         the shape of the contour is sufficiently arbitrary, i.e., specification of the contour requires more than one bit per texel.

For processing of contour texture maps, one needs a channel of transparency. This allows obtaining of full-color images inside contours. However, obtaining of a full-value picture requires a double layer of texture faces: one for imaging inside the contour and the other for imaging outside it. After bilinear interpolation identical to that in the other channels, to obtain the contour we perform the following calculations:

,                                                                                              (5)
then follows correction:
                                                                                                   (6)

, where T is the final result, t  is the result of bilinear interpolation, and Ps is the size of the pixel projection.
Additionally we perform operation of obtaining the contour:

,                       (7)
whereis the fraction of the size of pixel projection

2.4 Texture addresses

To calculate a texture address, one requires texture coordinates (2a), (2b); the level of detail of a pixel, the value of the general order of texture coordinates, and relative displacement of the local and global texture coordinates. Then each of the texture coordinates is divided into four numbers.

The bilinear interpolation coefficients α and ß are used for trilinear interpolation of the texture:

fu = ( ( fiu - du ) & 0111 ) + ( du & 011 ),                                                                (8)
сu = ( ( ciu -du/2 ) & 011 ) + ( ( du/2 ) & 011 ),                                                       (9)

where fiu, fiv and ciu, civ are the texture coordinates of the current pixel, scaled according to the level of detail; du (dv) is the displacement of the grid of the local texture coordinates relative to the global ones (they are meaningful only for compressed texture maps and equal to zero an uncompressed texture). For fv, cv the calculations are similar. The texture address is formed from values of fu, fv, cu, and cv.

3. Function-based objects 

The characteristic feature of the proposed freeform representation is 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 (x, y, z) Еⁿ in the form F(X) ³ 0. Quadrics are considered as closed subsets of the Euclidean space Еⁿ defined by the descriptive function F(X) ³ 0 where F is the continuous real function; X= (x,y,z) - is the point at Еⁿ 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.

Fig. 1. The model coordinate system (M) in which the space inside the cube is subdivided.

3.1 Set of geometric objects

3.2 Set-theoretic operations

Let the objects G₁ and G₂ be defined as ¦₁(X) ³ 0 and ¦₂(X) ³ 0.

The binary operation of the objects G₁ and G₂ means operation G₃=F¡(G₁,G₂) with the definition

¦₃=y(¦₁(X),¦₂(X)) ³ 0,                                                 (10)

where y  is the continuous real function of two variables.

The geometric model should allow designing of objects and their compositions of infinite complexity. This is primarily achieved by means of Boolean operations of uniting and intersection. The whole scene is a kind of a tree. Each node of the tree is an object constructor performing logical operations its descendants, and vertices of the tree are primitives. When the object constructor is queried while rendering, the object addresses its descendants, transforms the obtained results, and gives the answer to the query. The descendant may be a primitive or another object constructor. While applying the geometric operations, rotations, displacements, and scaling to the object constructor it performs all these operations on its descendants, and in addition changes its Boolean function in the case of inversion.

3.3 Recursive multi-level ray casting algorithm

We consider the geometric object that has the property of answering the request on intersection with a rectangular parallelepiped or a bar [5]. The negative answer guarantees that the object is not intersected and has no common points belonging to the intersection is done by recursive subdivision of the space inside the cube defined by boundaries of ±1 along each coordinate (see Figure 2).

The center of the cube matches the origin of the model coordinate system M whereas the plane Z= -1 coincides with the screen plane. At the first step of recursion, the initial cube is subdivided into four smaller subcube in the screen plane. At the stage of subdivision of space along the quaternary tree, 2-times compression and transfer by ±1 along two coordinates are performed. Assume, that domain of point search is a cube in which embed our object.

Then recursive subdivision of the domain applied: domain cuts by 2 planes, that perpendicular to the screen plane XY, into 4 bars. For each bar intersection test are executed. If the object intersects with given bar, then bar subdivides further. Otherwise, we exclude bar from subdivision. This corresponds with exclusion of the square areas in the screen, on which given bar (and therefore, object) are projected (see Figure 2). Using results of intersection test, we perform subdivision of subbars that fall within the quadric completely or, probably, partially, and the knowingly external subbars are eliminated from processing.

On some recursion level we obtain the bars with one pixel-wide footprint (slices). Then we start subdivision of slices in depth, i.e. along Z-axis (see Figure 3). Therefore, for each slice we determine first point, which contains object (the test for crossing is similar above described, but accordingly, with smaller number of coefficients). In other words, we traverse scene space (unit cube) by quad-tree, leafs of which (slices) is a roots of the binary subtrees. Coordinate system in which the algorithm subdivides cubic volume is called work or model space and is denoted M (see Figure 1). Coordinate system with camera (viewer) in its origin and viewing frustum is denoted P (see Figure 2).

Application of projective transformation extrapolates the rendering algorithm to pyramidal volumes and thereby allows us to generate images with perspective.

4. Texture mapping onto freeforms and volumes

In papers [7], [8] Solid Texturing of complex surfaces and phenomena intermediate between shape and texture by using space-filling applicative functions to modulate density were introduced. The model is essentially an extension of procedural solid texture synthesis, but evaluated throughout a volumetric region instead of only at surfaces. Authors present realistic representations of such shape+texture (hypertexture) phenomena as hair, fur, fire, glass, fluid flow and erosion effects. Hypertexture exists within an intermediate region between object and not-object. They  introduced a notion of generalized boolean shape operators to combine shapes having such a region as well.

We will give the definition of a texture in the “volumetric” sense, proceeding from its original definition in the “surface” version (described above). In addition, we will define uniquely the main notions.

Fig. 4. A 3D array.

Mapped object is the entire 3D scene or its element containing information on its shape. For example, a scene represented by two ellipsoids, on the one hand, may be considered as an image of two independent objects, on the other hand, such ellipsoids may be considered as an object-combination of two ellipsoids; these two points of view are alternatives. Hence, in terms of objects, the texture is a scene element that changes the properties of another object and is not imaged when rendering. For example, two objects will represent a colored ball: a shape in the form of ellipsoid and an object-texture that contains a reference to the array of colors, which is mapped in a certain manner onto the ellipsoid with the use of linear, cylindrical, spherical, or some other parameterization.

Fig. 6. A 2D array, encapsulated into an object-array.

Fig. 7. Visualization of the object-array encapsulating a 3D data array.

References