195 GPU-Based Rendering for Ray Casting of Multiple Geometric Data Sergei Vyatkin1, Oleksandr Romaniuk2, Oleksandr Dudnyk2 1. Synthesizing Visualization Systems Laboratory, Institute of Automation and Elecrtrometry SB RAS, RUSSIAN FEDERATION, Novosibirsk, 1 Akademika Koptyuga avenue, email: sivser@mail.ru 2. Department of Software Engineering, Vinnytsia National Technical University, UKRAINE, Vinnytsia, 95 Khmelnytske shose str., email: rom8591@gmail.com, dudnyk@vntu.edu.ua Abstract: We present a new GPU-based rendering method for ray casting of multiple geometric data. Our II. VOLUME-ORIENTED RENDERING approach supports a polygonal data to calculate scattered Along with possibility to rasterizing 2D space, the main light. Terrain is represented for the base of scalar feature of the proposed method is rasterizing made by 3D perturbation functions. The geometric model is based on space quadtree subdivision of pyramids of different levels, non-polygonal representation. We present a new which constitute the whole pyramid of vision. Then a representation scheme for freeform surfaces it is possible pyramid of the lowest level is binary-tree subdivided into to combine basic surface and perturbation functions. To voxels of the lowest level - Recursive Multilevel Ray Casting recognize the place it is often sufficient to fill areas with (RMLRC). In the latter case, extent space regions (in depth) the generalized texture patterns, such as "themes". can masked out. Depth subdivision of space performed on the Themes designed beforehand and consumption of memory for storing them is not huge. logarithmic basis. The technique of RMLRC allows Keywords: freeform surfaces, recursive multilevel ray determining an intersection of a ray (pyramid) of any level casting, shape texture, thematic texture, scattered light, with a surface effectively. It is also suitable for fast culling of volume-oriented visualization. a spatial region outside an object. The core of this approach is effective search of volume elements (hereinafter voxels), I. INTRODUCTION involved in current frame generation, fused with direct projection [5]. If geometry transformation is described by Using traditional polygonal representation for the example matrix (C) then new calculated matrix of quotients complex surface give rise to a range of problems such as (Q)'=(C)T*Q*(C) does in the coordinate system P the same visible surface determination, depth complexity handling, as the matrix (Q) in the coordinate system P. The matrix (C) controlling levels of details, clipping polygons by viewing of projecting transformation calculated once for particular frustum, geometry transformations of large number of frustum. So the use of projecting transformation generalizes polygons [1, 2]. the discussed algorithm for pyramidal volumes (frustums) A method for constructing a triangle mesh whose vertices and allows synthesize images with perspective. In our coincide with the zero-valued isosurface is the Marching approach a virtual environment can be described using Cubes algorithm [3]. Although it provides many greater polygonal models, surfaces of second order, three- capabilities, the use of voxel-based terrain in real-time virtual dimensional scalar functions, defined on discrete grid simulations also introduces several new difficulties. The h=h(u,v), free-form surfaces, which are represented by algorithms used to extract the terrain surface from a voxel composition of base surfaces and shape-driving functions. map produce far greater numbers of vertices and triangles The proposed RMLRC algorithm has several advantages in when compared to conventional 2D terrain. The development processing mentioned surface models as compared with of a seamless LOD algorithm for voxel-based terrain is vastly known algorithms. Therefore, for example, RMLRC more complex than the analogous problem for height-based algorithm applied for second order surfaces simplifies terrain. calculation of Phuong shading, since at the last level of Texturing and shading of voxel-based terrain is more subdivision derivative plane coefficients for the surface difficult than it is for height-based terrain. In the cases that obtained. Further, the possibility of second order and free triangle meshes are generated for multiple resolutions, arises form surfaces composition allows producing objects that are the cracking problem. more complex. Photorealistic visualization of complex A method for patching cracks on the boundary plane surfaces, for instance, specified by a three-dimensional between cells triangulated at different voxel resolutions was function, defined on discrete grid h=h(u,v) can be done described in [4]. Using a voxel-based model however, can without intermediate polygonal approximation. Such surfaces achieve the same results at a much lower hardware represented by differential height map, i. e. the algebraic requirement. carrier surface is given and in each grid node, only deviation The proposed method includes the following main from this surface needed. This representation facilitates features: rendering second-order surfaces; rendering surfaces calculation of contiguous levels of details as well as makes defined on a regular altitude grid (Shape texture); rendering easy quality filtering. Geometry transformations apply only freeform surfaces; scattered light visualization. to the carrier surface and the height map is kind of surface ACIT 2018, June 1-3, 2018, Ceske Budejovice, Czech Republic 196 texture. Freeform surface representation differs from known the image generator load is small for irregular grid as representations, such as for example, Constructive Shell compared to regular grid. Each irregular grid node consumes Representation [6], since the former is free of problems much more computational time and memory than that of arising when complex surfaces are approximated with large regular. Systems, which employ irregular grids, are very number of Bezier patches, B-splines etc. (problems of limited in the number of LODs that can handled. In addition, rendering patches boundaries, problems of warped it is very difficult to solve problems concerned with terrain halfspaces). The proposed approach allows specifying surface deformation when using irregular grid (explosions, pits in the representation as composition of base surfaces and shape- ground). driving functions. Small number of such functions is enough Volume oriented rendering and uniformity of object to describe surfaces of any form including non-convex, with processing result in an efficient hidden surface removal and detection of spatial collisions. Chosen representation of holes etc. (Fig. 1). Discussed surface representations and the terrain data is based on regular multi-level elevation map approach to their processing facilitate description of such complemented with levels of detail [7]. This approach has phenomena as waves, dynamic surface warping, morphing, several advantages, such as rapid generation and deformations and animation of wide range of surfaces. modification, efficient data storing and retrieving, over polygonal models. V. THEMATIC TEXTURE Systematically analyzing geographer’s work, Barr [8] has described it as operating with the “geographic matrix”. For clearness, it can thought as three-dimensional, i.e. two dimensions correspond to the geo-coordinating system, and the third one corresponds to a description list. Each element represents a “geographic fact” (Fig. 2). For a large database, it is resource-intensive to obtain and process geospecific photo-texture for the entire gaming area. It assumed that most of the benefits of geospecific photo-texture could attained by Fig. 1. Freeform surface (F-117) over terrain. Height map resolution combining a large amount of generic photo-texture with a 512x512. Screen resolution 1920 x 1080 small amount of geospecific photo-texture. III. FREEFORM SURFACES Traditionally, the parametric form represents each patch in a freeform surface as a mapping from 2D parameter space to 3D space. Although parametric patches are powerful for constructing freeform surfaces, processing these patches poses fundamental problems, only two - constructive solid geometry (CSG) and boundary representation (Brep) - commonly represent solids exactly, that is, without approximation. In particular, "separation" and other such problems associated with curved halfspaces are hard to solve in parametric patches. We present a new representation scheme for freeform surfaces - it is possible to combine basic surface F(x,y,z) and shape-driving function R(x,y,z) or perturbation function, where shape-driving function represents smooth deformation of basic surface [7]. The shape-driving function is composed of several second-order Fig. 2. Thematic texture functions using logic intersection and union operations, it is recursively evaluated during subdivision itself, and therefore, Simulation of big areas of terrain in the training system computation of resulting R (x, y, z) is minimal. At the same image generators requires the large capacity of memory for time, it is moderate in computations, so it can implemented in the photographic data storage. The usual approach to reduce hardware to carry on realistic object outlook. this information is to compress the data with the help of the Because of application of the 3D space, subdivision methods such as JPEG, etc. In the approach of the texture algorithm the possibility appears to render surfaces, which composition it supposed, that the observer (pilot) often is not usually consist of huge amount of patches such as freeform interested in the exact, photographic information about the surfaces. areas, covered by, for example, forest, water, mountains, etc. To recognize the place it is often sufficient to fill these areas IV. SHAPE TEXTURE with the generalized texture patterns (we will call them Non-regular terrain algorithms are more complex but "themes" afterwards). Themes designed beforehand and have the potential to reduce the number of polygons that the consumption of memory for storing them is not huge. Area of system must process [1]. However, for many terrains with the terrain photo-texture with the same theme approximated limited elevation gradient, the average expected reduction in by the polygons, which are bounded by curves. Each of the ACIT 2018, June 1-3, 2018, Ceske Budejovice, Czech Republic 197 polygons has the pointer to the texture theme and to the blending areas. These faces do not differ from others and procedure of generating the boundaries between the areas their special role is to connect textural areas with different with the different themes. The procedures of generating the borders. For this purpose, such face owns border description boundaries do not reproduce true boundaries exactly, but of one area, and a texture of the other area. While the have the goal to keep their features. There are two main database created, these faces constructed by expanding problems in the technique of the texture composition. The polygons, i.e. by moving their edges. By the way, first is the generation of the boundaries between the areas procedurally generated areas can obtained exactly the same with the different themes. To resolve this problem, the way: if a certain polygon with any textural theme has a algorithms, which allows generating the different kinds of prescribed blended border, the procedure described above boundaries, designed. Among the possible kinds of the executed and a newly created polygon assigned descriptions boundaries the following can be selected: fractal boundaries, of the area created. following natural boundaries in the maps of the texture The boundaries coinciding with natural borders within a themes (for example, following the streets in the texture map textural picture are considered. Such borders can formed by of the town), procedural blend zones (beaches, etc.). The processing the image from the original map buffer after all second problem of the technique of the texture composition is textural polygons have been rasterized. Beside difficulties the filling the areas by the homogeneous texture pattern. with forming the borders between areas of different textures, Filling the big area of the terrain by the small texture pattern there is a problem concerning inner filling of these areas by a leads to the undesirable periodic, unnatural picture. The homogeneous picture. Therefore, in the proposed approach introduction of the different kinds of non-regularity, which the textural coordinates disturbed by a noise-map to provide keeps the features of the texture pattern, allows obtaining singularities on the picture. It is possible to reuse noise values more natural picture. previously obtained while determining the textural theme The first stage is the usual rendering of polygons, index. Let us estimate memory and time consumption within describing the texture, and filling the service buffer by the the proposed approach. Note, that original map resolution can pointers to the texture themes and kinds of boundaries. The be less than final texture map resolution. Maximal spatial second stage is access to the buffer through the perturbation frequency of the final image determined by a spatial map, to obtain the color of each texel. Perturbation map frequency of textural themes and a noise-map; therefore, they calculated beforehand. Note that approach is adapted for the can be scaled, so that one texel of original map is transformed generation of the fractal boundaries, but it allows to use the into an area filled by a certain picture with a fractal border. procedural blend zones also, and to generate boundaries, Thus, minimal size of original map determined by a required which coincide with the natural boundaries in the maps. To precision of border presentation. The image kept in an generate fractal boundaries the following actions must be original map consists of contiguous areas each filled by a done (some are simplified): access to the perturbation map by certain textural theme index, that is why these data can be address, defined by the U and V coordinates of the given safely compressed using, for instance, Color Cell texel, to obtain the additions to the values of U and V. Compression method (this will ensure up to six times Obtaining the new values of U and V by the addition with the compression). Besides, this task can accomplished during values from the perturbation map. Access to the buffer of the textural polygon rasterizing with no additional time source map by the address, defined by new values of U and consumption. As noise-map, contents do not explicitly V, to obtain the index of the texture theme; access to memory emerge in the final image, periodically wrapped map can of the texture themes, to obtain the color of the texel. used for this purpose and unwanted regularity will not Boundaries between regions, obtained by the method noticed. For instance, fractal border has a repeating structure described, looks fractal due to the fractal character of the only if it originally presented as a straight line parallel to one perturbation map used. Turbulent noise used to fill this map. of textural coordinate axes. The task of rasterizing textured As it is well known, the higher spatial frequencies of the polygons and filling original map is not extremely difficult turbulent noise have the smaller amplitude (and on the and can be handled by any sufficiently powerful universal contrary). All of the boundaries, obtained by this method, are processor, moreover the time is limited only by a needed similar, but different themes can have different boundaries, uploading due to the camera’s motion. To determine the color with different widths (amplitudes) and "crooknesses" of a texel several steps are completed: fetch operation from (frequencies). Therefore, the sequence of actions, described original map, from noise-map, then, modification of U and V above, must be little more complex: access to the source map coordinates, fetch operation from original map and from to obtain the characteristics of boundary; scaling of U and V textural theme memory. As one may see, these operations are coordinates to obtain required frequency of the noise, then quite simple and, therefore, a conventional textural fetch access to the noise map (perturbation map). Multiplication of operation can substituted. This implementation has several the values, obtained from the noise map, by the constant significant advantages, as follows: overall memory value to provide required amplitude of the noise, then requirements are less then those for a global texture; texture modification of U and V; access to the source map to obtain animation features become available by simple means, as the index of the texture map; access to memory of the texture fractal border can made animated, if a shift is applied to a themes to obtain the color of the texel. noise-map at each frame. In addition, noise magnitude can Obviously, blending can become correct only if textural change resulting in an interesting effect. In analogous way, areas have coinciding borders. To satisfy a condition an texture inside the distinct regions can animated. Besides, this additional database is introduced which describes faces of approach would be naturally used also for all other feature ACIT 2018, June 1-3, 2018, Ceske Budejovice, Czech Republic 198 textures (fetch operation from original texture memory TABLE 1. PERFORMANCE ON CPU AND GPUS should be excluded). All this could be useful while rendering, Resolution i7-2700K GTX 550Ti GTX 750 Ti GTX 950 for instance, water surface, flames, snow, etc. It should be also mentioned that implementation described 256x256 802,65 ms 67,03 ms 31,07 ms 26, 55 ms above requires original map, noise-map and textural theme 512x512 850,81 ms 71,05 ms 32,93 ms 28, 01 ms (as MIP map) storing, Generation of levels of detail for 1024x1024 856,52 ms 71,53 ms 33,15 ms 30, 22 ms textural themes and noise-maps is of no difficulty, however levels of detail for original map is not clear, because these The surface obtained will be smooth (Fig. 1 and Fig. 3), data are indices, which cannot be blended like colors. A and a small number of perturbation functions (16) will be straightforward solution of this problem is to eliminate details necessary to create complex surface forms. The figure shows that are smaller than corresponding texel size, i.e. only a result of modeling a scene object by means of free forms, wholly covered texels handled during rasterizing original whose description required 2Kbyte information, which is 500 textural polygons. times less than the polygonal description that would take 1Mbyte information. VI. SCATTERED LIGHT VIII. CONCLUSION The vertex shaders compute the light reaching the eye from a source or a reflective object and fog component. The inputs The main advantages include ease of calculation of points to the vertex shader are vertex position, transformation on the surface with quick search and rejection of the regions matrices, sunlight intensity, the sun direction, the various not occupied by the scene objects. A factor of 100 or more extinction and scattering coefficients. In this implementation decrease in the number of surfaces for describing curved using calculate them per-vertex in a vertex shader. If the Sun objects. Operations of the Geometry Processor (CPU) is not too low in the sky, this approximation gives good becomes significantly easier and data stream from the results at a low cost. For these assumptions, the illumination Geometry Processor (CPU) to the Renderer (GPU) reduced. of the ground plane and light reaching the eye from it may Paralleling of the system becomes easier because the total easily derived (Fig. 3). To find the color perceived along a system performance determined by the performance of the line of sight, we must consider both the light reflected by Renderer (GPU) which operations can be easily distributed objects along the line of sight, attenuated by the inverting between different screen regions. All problems connected to fog, and the light scattered towards the eye by fog along the terrain generation solved. The opportunity to describe objects line of sight. with grid values, i.e., with shape texture map; it becomes possible to morph objects; it is achieved by plain interpolation or animation of shape texture. It can used to render clouds, explosions, waves on water, etc. REFERENCES [1] R. Pajarola, E. Gobbetti. "Survey on semi-regular multiresolution models for interactive terrain rendering”. The visual computer. International Journal of Computer Graphics, Vol. 23, P. 583–605, 2007. [2] P. Lindstrom, D. Koller, W. Ribarsky, L. F. Hodges, F. Nick, and G. A. Turner. “Real-time, continuous level of detail rendering of height fields” In Proceedings of Siggraph, 1996, P. 109–118. [3] W. E. Lorense, and H. E. Cline. “Marching cubes: A high Fig. 3. Terrain, F117 and scattered light. Height map resolution resolution 3D surface construction algorithm”. Computer 512x512. Screen resolution 1920 x 1080 Graphics, Proceedings of SIGGRAPH 87, P. 163–169. VII. PERFORMANCE [4] R. Shu, C. Zhou, and M. S. Kankanhalli. “Adaptive marching cubes”. The Visual Computer, Vol. 11, P. 202. The visualization time is reduced by using the [5] Vyatkin S. I., Romanyuk A. N., and Savitska L. A. computational resources of a graphics processing unit with “Multi-level ray casting of function-based surfaces” compute unified device architecture (CUDA). The result of Journal of Physics: Conference Series, 803, № 1. running the programs on different processing units is the [6] P. Menon, and T. J. Watson "Constructive Shell same even if they may have a different number of streaming Representation Freeform Surfaces". IEEE Computer multiprocessors. A large portion of the cube will be computed Graphics 0373-17-16, 1994. in parallel. Among the functions of the graphics processing [7] S. I. Vyatkin. “Complex Surface Modeling using unit was to calculate the coordinates of points of the surfaces, Perturbation Functions”. Optoelectronics, Instrumentation normals, and illumination. Geometric transformations were and Data Processing. 43 (3), P. 226–231 (2007). performed by the central processing unit (CPU). Rendering [8] R. Barr "Automated cartography and geographical results using CPU (i7-2700K) and GPU (GTX 550Ti, GTX 750 information: Part 2", Advances in Computer Graphics, Ti, GTX 950) are shown in Table 1. Volume 11, Springer, page 29, 1986. ACIT 2018, June 1-3, 2018, Ceske Budejovice, Czech Republic