DonNTU   Masters' portal

Abstract

Content

Introduction

Visualization tasks objects n-dimensional space are used in process control systems, diagnostic systems and pattern recognition, expert systems and decision support in engineering, economics, medicine, linguistics and psychology. In recent years, widespread interactive decision-making system, in which the responsible person makes a decision and assesses their impact on the basis of visualized data. [9].

The introduction to the science and industry of CT scanners, regardless of their design and the physical principles of imaging, enables obtaining digital images for later analysis of the state of an object, particularly in medicine. But the set of such photographs or slides does not allow the researcher to make decisions quickly enough, so it does not give full information. Each slide is a field of fixed pixel sizes determined by the imager design, each pixel is assigned to the attribute characterizing the color gradation of color or any other physical quantity. Thus, the problem of spatial imaging test facility for digital photos (color or monochrome) in computer graphics and geometry.

The problem of rendering data received from the parallel planar sections of the object space can be solved according to the following scheme: Synthesis of model 3D object by its 2D sections and obtaining a synthesized image projection pattern at arbitrary projection apparatus including a stereo projection.

1. Statement of the Problem

The problem of visualization of 3D-objects, which can be defined in various ways, arises in many areas of mathematics, physics, medicine [1]:

  1. Visualization of experimental data. For example, information collected from a variety of sensors, sensor networks, the measurement results of the simulation modeling.
  2. Visualization of functional representation. Visualization of complex three-dimensional objects in mathematics, visualization of analytically defined surfaces, etc.
  3. Visualization of medical data sets. One of the widely used methods of diagnosis is imaging. Scanners that work on the principle of X-ray (CT, then CT) and magnetic resonance principle (hereinafter MRI) to obtain images of a plurality of sections of the patient along any axis, which give a lot of information about the features of its anatomy and physiology. Imaging techniques allow the reconstruction of three-dimensional structure for a variety of parallel sections. Visualization of the dataset is now implemented in software running most current CT scanners, but the task selection dimensional areas imaging area of interest, a set of predetermined contours in sections, under radiologic visualization of the treatment of patients, usually in the software are not implemented.
  4. Visualization of experimental and modeling data from other areas, such as fluid dynamics, geology, meteorology, molecular analysis.

The main task of visualization of 3D-objects is formulated as follows - it is necessary to find the optimal approximation for the unknown surface so as to minimize the measurement error due to limitations in accuracy in measuring devices or insufficient surface quality of the physical model.

A distinctive feature of all objects visualization algorithms is their exceptional resource consumption due to the need to process a large number of similar data, therefore improving performance implementation of these algorithms is an important task.

2. Analysis of the literature

For visualization of objects having a large number of features as a set of parameters on a plane, there are many methods. [9].

Currently, the following classes of data visualization: visualization of the surface (surface rendering), volume rendering (volume rendering) and hybrid imaging (hybrid rendering).

Algorithms imaging surface (surface rendering) build a three-dimensional image of the surface area (one of the representations of the surface of the equation is where - given level). First opening surface is approximated by polygons, polygons and then rendering is performed by using one of the graphics library. [10].

Volume rendering algorithms (volume rendering) are used to represent the full picture with all the surrounding objects. There are four types of volume rendering algorithms: the emission of rays, the decomposition into layers with shear deformation, design voxels, texture mapping. [11].

Surgical planning of the operation on a virtual patient and aerodynamic simulations using hybrid imaging (hybrid rendering), with which to build a three-dimensional image of the object (represented by the triangulation), embedded in a translucent volume. [13].

The main algorithms that are used in the restoration of surfaces, are:

  1. Algorithms for dropping rays [2];
  2. Triangulation algorithms [3];
  3. Marching cubes algorithm [4];

Algorithms dropping rays are fairly well understood, and as shown on the market of free and commercial software implementation, well parallelized using OpenGL and shader language. Such implementations allow these algorithms to work in real time, even on not so powerful workstations.

Triangulation algorithms are less resource-intensive, while there are even faster in the single embodiment. One example of this is the implementation of an algorithm for constructing the Delaunay triangulation, as described in [5], which is on the personal computer of average power (Core2Quad 2,83 GHz, 8GB of RAM) allows you to perform a triangulation of a surface of 100,000 points in 8 seconds.

More resource-intensive and less optimized algorithm is marching cubes[4], which, however, is interesting for the problems of interactive and automatic recovery surfaces of objects represented a cloud of points, as well as for the construction of convex hulls. Therefore, in the paper we consider ways to improve the performance of this algorithm is due to parallelization.

3. Overview of the triangulation method

In practice, most often we partition images into triangles.

This is due to the following reasons:

  1. The triangle is the simplest polygon vertices are uniquely define the brink;
  2. Any area can be guaranteed to triangulate;
  3. The computational complexity of the partition into triangles is much smaller than other landfills;
  4. implementation of procedures for rendering the most simple to the region bounded by a triangle;
  5. for the triangle is easy to identify three of its nearest neighbors, having common ground with him.

The process of partitioning a polygonal region with a complex configuration in a set of triangles is called triangulation. In the analysis or synthesis of complex surfaces they approximate the grid of triangles, and subsequently operate with simple polygonal regions, ie with each of the triangles. In practice, a lot of triangulation algorithms, one of which is shown in Figure 1

Итеративная бисекция основания

Figure 1 - Visualization of 3 iterations of the base of the triangle bisection algorithm ROAM.
(animation: 7 shots, 5 cycles of repetition, 146 KB)

Of particular interest is determined by triangulation algorithms that are used in many procedures, computer graphics, such as the formation of surfaces, shading, removing invisible parts, cut-off.

Any surface can be approximated with desired accuracy mesh triangles. The accuracy of approximation is determined by the number of triangles and the method of their choice. For high quality imaging object located near the observation point, requires consideration of many times triangles than in a situation where the same object is located at a distance. Even a fairly coarse grid is useful in practice, since the smoothing methods used in the mapping process can significantly improve the performance of the curvature of the surface. [12].

4. Description of the algorithm

According to [4], the algorithm consists of two main stages. First stage: the construction of an implicit function F: D->R, where D is R3 -neighborhood of the surface. The function F is an estimate of the distance from any point to D surface. Second stage: the surface triangulation of the zero level of the function F with the marching cubes algorithm.

To construct estimates of the distance we associate with each point of the set {x1,…,xn} oriented tangent plane Tp(xi) , which can be found using principal component analysis applied to the k nearest neighbors of a point x i. Calculation of the distance function is calculated as follows:

F(p) = (p-oi)ni ,                (1)

which oi – closest to p «center» of the tangent plane (the centroid of the k nearest neighbors), and ni– normal

Algorithm "Marching Cubes", can be divided into two stages:

1. Partition of G in on a finite set of cells, the cells crossed by the search of the desired surface.

2. Approximation of surfaces found in the cells.

These two sub-tasks are independent. Let us examine them in more detail.

The first stage.

General problems of this phase is as follows [4]:

1. Break the G into the cell.

2. Select the cells that intersect with the desired surface.

Once the region is divided into G cell function value generally defining surface can be known only at the vertices of the cells. Thus, the cell is the main building block of all algorithms at this stage.

In those problems, in which the function defining the surface, set the table on a regular grid, the problem of the partition of G into cells at once disappears, because of the uniqueness of the solution - a parallelepiped cell should be - in order to know the value of the function at the vertices of the cell. If the function is given explicitly, the cell can choose any shape and size. However, one should take into account some of the problems associated with the approximation of a surface in a cell. If the cell size is very large, it can be a great loss of accuracy.

When a large amount of cells, some portion of the target surface can not be seen. However, to choose a very small cell size is not very good in terms of performance. Therefore, the cell size must be chosen not less than the margin of error to construct the desired surface.

Cell shape in the algorithm "Marching Cubes" - a box. However, this is not the only option. Cell shape determines further triangulation of the cell. And, if the top of the cell is outside the limited scope of the desired surface, the value of this bit is 0, or - 1. Then the number of different types of triangulation is 2N. This shows that the use as a cell, for example, the icosahedron is not optimal.

So, let us assume that G is already broken into the cell. Then the main problem is the search for the desired cells intersected surface. Let C - set of cells, then Cv - many cells traversed the surface F (P) = v. Then we can assume that the surface intersects the cell if there are P1 and P2 - the top of the cell that:

   F(p1) <v< F(p2),                                      (2)

This condition is satisfied when executed:

   Mini F(pi) <v< Maxj F(pj),                              (3)

where pi and pj – the top of the cell.

Thus, the problem reduces to the following: a plurality of cells C Cv select a subset of cells satisfying the condition (3).

The second stage. The space is divided into cells, and selects only those cells in which it is necessary to make an approximation. Thus, the task of the second step is to approximate to the same cell surface. The most optimal way to approximate - triangulation[4].

You need to determine how many ways the triangulation has a box. Suppose there is an 8-bit code. Then each vertex associate one bit in the index. And, if the top of the cell is outside the limited scope of the desired surface, the value of this bit is 0, or - 1. Then the number of different types of triangulation is 28=256.

Receiving a triangulation method may be approximated by the surface already in the cell. At this point, we already know the number of triangles, and for each edge of the triangle are known cells, which lie on top of him. It remains to find a point on the edge of the cell in which it intersects the surface.

5. Paralleling application

As seen from the marching cubes algorithm, it comprises many steps, which are performed independent tasks. The presence of independent tasks is a sufficient condition for the algorithm parallelization. They are:

  1. calculation point identifiers;
  2. reorder points;
  3. allocation voxel grid;
  4. calculation templates cells;
  5. generation of triangles.

Since these tasks involve the same operation on a large amount of data, then it would be to parallelize them well enough, even using the computer systems that are classified as SIMD. Such systems include advanced graphics accelerators[6]. For the most universal acceleration GPGPU calculations using the variant of the algorithm parallelization using OpenCL, which will use accelerators nVidia, AMD and Intel. Using GPUs to solve this problem is argued that the performance of calculations using the GPU gives good results in algorithms that use parallel processing of large data sets. In our case, the ratio of the number of arithmetic instructions that will execute the construction of the surface is sufficiently large relative to the number of memory accesses, which usually gives the best results in the implementation using GPGPU computing.

The algorithm should include the following steps:

  1. Implementation of the accelerating structure of the input data set.
  2. Restoration of the normal field.
  3. Calculation of estimates of the distances.
  4. Finding the surface of zero-distance estimates (algorithm "marching cubes").

In the first step as the accelerating structure is proposed to use a regular grid. Parallel generation of a regular grid consists of five stages: the construction of the bounding box, the calculation point identifiers, sorting identifiers points, reorder points, the allocation of voxel grid. As a result, in the memory will be retained only those voxels that contain data points, which can significantly reduce the use of memory.

The second step is to find the tangent plane for each point of the input data.

A good implementation of the parallel algorithm for finding the tangent is given in [7]:

  1. Get out of the global memory handle periods.
  2. Determine the integer coordinates of the voxel (x, y, z).
  3. Determine the integer coordinates of the voxel (x, y, z).
  4. Copy the points with indices obtained in the local memory and to sort the point in ascending distance.
  5. Choose from a local storage location of the closest points.
  6. Compute the centroid and place it in the output buffer.
  7. Calculate the covariance matrix for the selected points, find the minimum number of its own and put the corresponding eigenvector to the output buffer.

To calculate the distance estimation is proposed to place the centroid in accelerating structure that allows you to use the following parallel circuit:

  • Get out of the global memory handle periods.
  • Determine the integer coordinates of the voxel (x, y, z).
  • Find the nearest centroid and the corresponding normal.
  • Calculate the estimate of the distance.

    • Marching cubes algorithm, parallelized using OpenCL, consists of the following steps: calculation of patterns of cells, calculating addresses vertex buffer, the generation of triangles. This technique allows you to output different lengths of the thread in one buffer in parallel.

    It should be noted that, despite its popularity and widespread use, marching cubes algorithm has a significant drawback: a fairly simple surface areas it performs too many divisions. For example, the surface of which can be approximated by polygons 440, classic algorithm can generate about 67000[8]. This highlights the performance benefits of parallelization, but also talks about the need to improve the basic algorithm.

    Conclusion

    As a result, the work shows that the task of improving the performance of methods that reconstruct the imaging surface and is up to date. It is shown that the objective can be achieved by paralleling solving algorithms used to implement these methods. The substantiation that it is appropriate to decide, first of all, the problem of algorithm parallelization "marching cubes". It is revealed that the algorithm can be efficiently parallelized using GPGPU computing. Is a parallel algorithm that is implemented using OpenCL.

    List of sources

    1. Сравнительный анализ методов интерактивной триангуляции сеточных функций/ Интернет-ресурс. - Режим доступа: www/URL:http://cgm.computergraphics.ru/content/view/63#_.
    2. Volume ray casting / Интернет-ресурс. – Режим доступа: www/URL: http://en.wikipedia.org/wiki/Volume_ray_casting
    3. А. В. Скворцов Триангуляция Делоне и её применение. – Томск: Изд-во Томского ун-та, 2002. – 128с.
    4. Lorensen, W. E., And Cline, H. E. 1987. Marching cubes: A highresolution 3d surface construction algorithm. In Proceedings of SIG-GRAPH’87, 163–169.
    5. V. Domiter, B. Zalik Sweep-line algorithm for constrained Delaunay triangulation / Int. Journal of Geographical Information Science, Vol. 22, No. 4, April 2008. – P. 449-462.
    6. NVIDIA Corporation. NVIDIA CUDA Compute Uni?ed Device Architecture Programming Guide. Version 3.2.2010.
    7. GPU-алгоритм восстановления поверхности из облака точек/Интернет-ресурс.-URL:http://nano.msu.ru/files/conferences/GPU-2010-05/abstracts.pdf
    8. S. Schaefer, J. Warren, Dual Marching Cubes: Primal Contouring of Dual Grids / PG '04 Proceedings of the Computer Graphics and Applications, 12th Pacific Conference, 2004. – P.70-76.
    9. Метод и устройство визуализации пространственно распределенных образов со сложными топологическими портретами. //Научная библиотека диссертаций и авторефератов. Интернет-ресурс. - Режим доступа: www/URL: http://www.dissercat.com/content/metod-i-ustroistvo-vizualizatsii-prostranstvenno-raspredelennykh-obrazov-so-slozhnymi-topolo#ixzz2XKkRwcKZ.
    10. Визуализация данных поверхности. Интернет-ресурс. - Режим доступа: www/URL: http://docs.autodesk.com/CIV3D/2013/RUS/index.html?url=filesCTU/GUID-58270E7F-E5E0-4196-B194-4965255695F6.htm,topicNumber=CTUd30e10204.
    11. Гаврилов Н.И. Организация потоковых вычислений на GPU для интерактивной визуализации медицинских объемных данных. Интернет-ресурс. - Режим доступа: www/URL: http://escience.ifmo.ru/cms/content/Gavrilov.pdf
    12. Романюк Александр, Сторчак Александр Алгоритмы триангуляции Интернет-ресурс. - Режим доступа: www/URL:http://thalion.kiev.ua/idx.php/4/249/article
    13. Бугров Н.В., Голубев В.И., Дижевский А.Ю., Какауридзе Д.Г., Клименко А.С., Обоймов А.С., Фролов П.В. Обзор алгоритмов гибридной визуализации поверхности, вложенной в полупрозрачный объем Интернет-ресурс. - Режим доступа: www/URL: https://googledrive.com/host/0B8dxsp-U3fIiRnc5WEpmTThQRVU/MEDIAS2012-22-FrolovPV-Tomo3D.pdf