=Paper=
{{Paper
|id=Vol-2300/Paper47
|storemode=property
|title=GPU-Based Rendering for Ray Casting of Multiple Geometric Data
|pdfUrl=https://ceur-ws.org/Vol-2300/Paper47.pdf
|volume=Vol-2300
|authors=Sergei Vyatkin,Oleksandr Romaniuk,Oleksandr Dudnyk
|dblpUrl=https://dblp.org/rec/conf/acit4/VyatkinRD18
}}
==GPU-Based Rendering for Ray Casting of Multiple Geometric Data==
https://ceur-ws.org/Vol-2300/Paper47.pdf
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