Introduction

In the modern world the increasing value is got with the information, its ways of representation and distribution. The visual perception of the information is the basic way of reception by the person of representations about world around. Therefore problems computer schedules get special value in a modern information society which basic motive power is the science.

Among the primary goals computer in scientific sphere it is possible to allocate schedules such as:

• representation of a training material by the way most accessible to understanding;
• computer representation of objects of the real world;
• modeling of behavior of objects in virtual three-dimensional environments;
• data presentations of experiment in the most effective for the analysis to the form.

One of the major scientific problems is carrying out of research of any phenomenon or object. Thus it is important to have computer model of a studied subject. In the real world all physical objects it is possible to divide from the point of view of computer schedules into two classes: simple, such as a cube, a sphere, тор, and complex, that is what cannot be presented by means of the simple mathematical description (a surface of the Earth, the person of the person and so forth). If reception of model of simple object the analytical algebra, the discrete mathematics does not make special work representation of a subject of the complex geometrical form is the complex problem connecting means of such fields of knowledge as analytical geometry in space, and so forth vectorially complex objects make overwhelming majority of investigated objects, and, as a rule, they are set by points in space. In this connection the urgency of the decision of a problem increases.

Goals and Tasks of the Work

The goals and tasks of the work are in making the software system, allowing to construct net model of a complex surface on a set of points in three-dimensional space, and an estimation of its speed.

From the point of view of the formal description, the problem of construction of net model in set of points in three-dimensional space can be presented as follows. To receive surface S' which approximates unknown surface S with use of set of points in three-dimensional space P = {p_i | i=1..n, n≥3}, sizes of a maximum deviation both δ and density of an arrangement of points and ρ.

Scientific Novelty

Scientific novelty of the given work consists in creation of the program complex realizing the advanced method of restoration of complex surfaces in space on a set of points on the basis of a method "marching cubes".

Practical Value

Practical value of my master's thesis consists that the system can be used in systems of medical diagnostics, a virtual reality, and also for work of three-dimensional scanners for reading different objects of the complex form and so forth.

Survey of Existing Researches

Jordi Esteve, Pere Brunet and Alvar Vinacua in clause [4] published in August, 2005 have described a method of reception of the closed surface which approximates any set of the points set in 3D space. The described method as entrance parameters does not demand neither topological attitudes between points, nor a normal to a required surface. Except for that the method has no the purpose precisely to interpolate a required surface, however approaches the received surface with strictly fixed maximal mistake.

Initial points can be received by various ways by means of optical, ultrasonic or the sensor controls often used as a source of data. Programs of geometrical modelling should process this set of points so that to receive approximating surface. In that case:

• the generated surface will be more compact, than initial set of points;
• more realistic visualization will be carried out;
• at work with the received surface simple geometrical operations will be accessible.

The algorithm developed by authors allows to restore a surface of any closed solid-state object. The basic stages of algorithm the following:

1. Splitting of area of the space containing points of set, on voxels (voxel - units of space, a cube with enough small length of an edge). Reference voxels to group internal ("heavy") or not ("lungs") of cubes.
2. Construction of the discrete closed membrane. Set six-coherent (adjoining to sides set voxel) voxel which form resulting surface. Right at the beginning of construction the membrane has the form of "brick". Step by step the membrane is narrowed, while the certain condition is satisfied.
3. Smoothing a discrete membrane for reception of a smooth surface.
4. Building of resulting surfaces on the received discrete membrane. It is possible to allocate following advantages of the offered algorithm:
• a reconstruction of surfaces on a set of points with non-uniform density;
• a reconstruction of objects which contain the untied closed environments;
• the method guarantees getting resulting closed object;
• approximation with the limited size of a mistake supporting smoothing.

In clause [5] Hugues Hoppe, etc. the algorithm which accepts as entrance parameter unorganized set of points laying inside or about unknown set of M is described and presented, and gives out as result the simplified surface which approximates M. It is supposed, that in advance are not known neither the topology and presence of borders, nor geometry of M, - all is automatically deduced from data.

This problem naturally arises in various practical situations, such as scanning of object from various points of supervision, restoration of biological forms from bidimentional cuts, interactive sketching of a surface. In a broad sense, the interesting class of problems can be certain as following: under the set partial information on a unknown surface to construct most compact of possible representation of a surface. Similar problems of a reconstruction arise in various scientific and engineering applied areas, including:

• The surfaces constructed according to area. The data received by system of laser scanning, usually are a rectangular grid of distances from a sensor control up to scanned object. If the sensor control and object are motionless, only the objects which are being in sight, can be completely digitized. More perfect systems, for example, such which makes Cyberware Laboratory, can digitize cylindrical objects, rotating either a sensor control, or object. However, topologically more complex objects, for example, a usual coffee cup with the handle, cannot be presented in perfection to any of these methods. For reception of qualitative representation of object by means of the scanner, it is necessary to use many points of supervision. Association of the data received from various points, with the purpose of construction of many-sided representation of a surface is not trivial problem.
• The surfaces constructed of contours: In medical researches the method of a cut of biological samples (fabrics) on thin layers by means of microvolume is often used. Outlines of interesting structures then are digitized for creation of a stack of contours. The problem is reduced to restoration of three-dimensional structure on a stack of bidimentional contours. Though a lot of attention already has been given to this problem, existing methods of its decision contain rigid restrictions. Probably, first of all, among them it is possible to allocate complexity of work with branching structures.
• Interactive sketching of a surface. Many researchers have studied creation of curves in R² by means of trace of a way of a feather or a mousy while the user throws the sketch of the desirable form. The system allowing has been described to create any curves in R³ by means of record of movement of the feather equipped by sensor control. Functionality of this system can be expanded to designing any surfaces, ignoring the order of records of positions, enabling thus to drive a feather forward and back on a surface. The problem is reduced to construction of representation of the surface including unorganized set of points.

Algorithms of a reconstruction of the surfaces, solving above described problems, as a rule, were developed off and on for use of partial structure of data. For example, algorithms of creation of a surface on a set of contours does complex use of the data organized in contours (i.e. the closed ranges), and that fact, that contours lay on parallel planes. Similarly, algorithms, specialized on a reconstruction of surfaces according to, received of various points of supervision, should consider the neighbourhood of points inside of each representation.

As comparison, approach Hugues Hoppe has the purpose to set the general problem which will not be adhered to one of structures of points of data. This approach has both theoretical, and practical value. From the point of view of the theory, abstraction up to the general problem often throws light on truly critical aspects of a problem. From the practical point of view, one algorithm solving the general problem, can be used for the decision of each concrete subtask.

The offered algorithm consists of two stages. At the first stage function f is defined: D-> R, where D, concluded in R³, is an area about data, such that, f estimates geometrical distance up to unknown surface M. The set of zero Z(f) as an estimation for approximation of M is entered.

At the first stage the subtask of construction of the plane least removed from set of points is used. It make a basis on which the further stages of work lean all. Key parameters of a plane are a base point through which passes a plane, and also a normal vector of a plane that it is possible to write down as pair (c, n). The base point turns out by a finding of the geometrical center of a file of points of a subset.

For definition of a normal vector it is necessary to solve an extreme problem where parameter of minimization is the sum of squares of distances from each point of set up to a plane (a method of the least squares). For realization representation of parameter of minimization in the form of function Lagrange [2] where to the sum of squares of distances expression which value is actually equal to zero is added is convenient. The problem of a finding of an extremum is reduced to the decision of system of the equations formed of private derivatives of function Lagrange on unknown persons, equal to zero. The decision of the received system is reduced to a finding Lagrange coefficient which is own number of the matrix deduced from system. The method of the decision of system is in detail described in Bugrova J.S. and Nikolsky's С.М book [3].

At the second stage the planimetric algorithm is used to approximate Z (f) a simplicity surface.

The key component for definition of function of sign distance is associated with the focused plane from each of points. These planes of a contact are used as linear approximations to a surface. Though the design of tangents of planes is rather simple, a choice of their directions as well as definition of is global-compatible orientation for a surface is one of the basic obstacles with which it is necessary to collide in algorithm. Planes of a contact not directly define a surface though their association can have complex structure. In algorithm the plane of a contact is used to define function of calculation of sign distance up to a plane.

As the final stage, trace of a contour, the variation of known algorithm "marching cubes" which allows to present function in tops of a cubic grid has been chosen and to find planimetric crossings inside tetrahedron decomposition of cubic cells. For an effective estimation of borders, the size of an edge of a cube should be not less sums of the set sizes of a mistake of approximation and density of points.

In practice it is often convenient to take value of an edge more than this size to accelerate process of calculation and to reduce number of the generated sides.

List of Unsolved Problems

In the given subject domain it is possible to allocate a number of unresolved problems, among which:

• a problem of definition of normals of planes (a choice of one of two);
• a problem of construction of a grid at a non-uniform arrangement of points;
• a problem of increase of speed of work of algorithm;
• the problem of restoration of a complex surface in real time, means a case when new coordinates of points act on a course of the decision of a problem.

Current and Planning Results of the Work

Current result of work is the system of construction of set of planes on an any set of the points, developed in NetBeans 4.1 environment in language Java, and also the structure of program system of restoration of a surface on points in Rational Rose 7.0 environment (modules, classes of system and their interrelation) is developed. It is planned to program the given system, to estimate its efficiency, setting various entrance parameters.

List of References

1. Хромова Е.Н., Пауков Д.П., Башков Е.А. Воссоздание поверхности по произвольному набору точек. Подзадача построения плоскости, наименее удаленной от совокупности точек ІІ Республіканська наукова конференція студентів , аспірантів та молодих вчених «Комп’ютерний моніторинг та інформаційні технології» Донецк ДонНТУ 15 мая 2006г.
2. Никулин Е.А. Компьютерная геометрия и алгоритмы машинной графики. – СПб.: БХВ-Петербург, 2003. – 560 с.: ил.
3. Бугров Я.С., Никольский С.М. Дифференциальное интегральное исчисление: Учебник для вузов. - М.:Наука, 1988 - 431с.: ил.
4. Jordi Esteve, Pere Brunet and Alvar Vinacua ` Approximation of a Variable Density Cloud of Points by Shrinking a Discrete Membrane, Universitat Polit`ecnica de Catalunya, Barcelona, August 2005
5. Hugues Hoppe Tony DeRose Tom Duchamp John McDonald Werner Stuetzle Surface Reconstruction from Unorganized Points University of Washington 1992