Effective algorithm for collisions account of several geometric figures in a hexahedral mesh cell in the computation of their volumes

Abstract

In this current work an effective algorithm for the computation of volumes of several geometric figures (they form collisions in a hexahedral mesh cell) has been proposed. The main feature (particularity) of the algorithm is its high performance due to the use of several techniques: 1) points sputtering techniques in a cell; 2) the preparation of the special data structure to calculate the points belonging to geometric figures.

Introduction

Today in order to build 3D model of ground and localization of contamination source one can use geological examination data as well as plans of industrial buildings, anthropogenic constructions and earthfill. Thus, in order to generate correctly a computational mesh it is necessary to solve the problem of intersections and overlapping of geometric objects (collision problem of geometric objects) manually, i.e., for example, cut a layer of ground by foundation or pile. Manual collision solution is a time-consuming problem and the automation of this process is expensive and difficult to implement. Even the worldwide software leaders, such as Hydrus, GMS, COMSOL that are capable of solving heat and mass transfer problem, do lack such a possibility.

It is considered that such operations should be implemented on a specialized CAD software, such as Autodesk 3ds Max, AutoCAD, SolidWorks, T-FLEX and others. In these software special techniques to accelerate the implementation of Boolean operations are implemented.
For example, hierarchy trees are built for geometric objects, such as CSG [1, 2, 3], where new Boolean operations on more complex objects are reduced to a system of solutions for more simple composite objects. The obvious disadvantage of such approaches is their inapplicability for arbitrary geometries. Therefore, for general cases the solution of Boolean operations on arbitrary geometric objects is more time-consuming.

However, if it is known that the computational mechanism will be based on hexahedral computational mesh (finite element, finite difference numerical schemes), we can significantly speed up and automate the process of transporting correct geometrical objects to the computational mesh.

In order to solve this problem we introduce a fast way to compute the occupied volumes of any geometric objects, placed randomly in a hexahedral mesh cell. This will quickly and correctly process collisions cases of two or more geometric objects (Figure 1) when performing cells marking of the computational mesh by means of geometric objects.

Fig. 1 – Boolean difference of geometries

Problem statement

Let us give a more detailed problem description: the cell is given (it is bounded by points and also some geometric objects (the so-called «geometries») , specified by a set of triangles and their normals. The objects can intersect with the cell and they are not necessary full. Original geometric objects are sorted in descending order of priority. Objects with a higher priority «cut out» parts of their intersections with other objects with the lower priority. It is necessary to compute the volume of objects on which the operations of Boolean difference were conducted.

Input data: coordinates of points, limiting the cell and certain geometric objects , specified by a set of triangles and their normals.

Output data: - the volume of figures with Boolean operations.

Description of the algorithm

In this work it is proposed to use an algorithm based on "sputtering" of the set of points within the cell (Fig. 2).

Fig. 2 - Uniform sputtering of points inside the cell

The idea of the algorithm is as follows: in a specified cell K points are located uniformly (Fig. 2). For each point the objects to which it belongs are defined. Among these objects the object of the highest priority is defined, and the given point is assigned to it. Further, it is assumed that the entire volume surrounding this point belongs to the figure, and the final volume of i object is computed approximately as , where - the number of points assigned to the i object with account of the priorities, V - the cell volume, K – the total number of points.

Thus, it is required to solve the point location problem. The following algorithm is the obvious solution to this problem:

1. For each point, we go around all the triangles in geometry. Find the nearest triangle.

2. Depending on how the normal of the triangle is directed, determine whether a point is inside or outside the figure.

The action period of such an algorithm will be O (n), where n - the number of triangles in geometry.

In order to reduce the processing time of one point it was decided to develop an algorithm with a more rapid determination of a point location. In order to achieve a reduction of processing time of each point, we will use the data structure, which is computed for a geometry object once before processing the requests for points (data preprocessing).

An algorithm for obtaining such data structure is as follows:

1. Through each vertex we draw parallel planes and get layering. For each layer, we compute the triangles that belong to it.

Fig. 3 - Layering

Let us define the meaning of a «projection plane» - a plane orthogonal to the planes that bound the layer.

2. In each layer, all the triangles of the layer we divide on monotonous sequence of triangles. These sets of triangles have projections that in the projection plane do not overlap each other.

Fig. 4 - Allocation of monotone sequences in the layer

As a result, the obtained structure is a sorted list of layers. In each layer there is a list of monotone sequences. In each sequence there is a sorted list of triangles.

Now let us consider the procedure for determining point location. It is necessary to find a visible from this point triangle to consider the angle between the vector of the triangle’s normal and the vector, drawn from a point to the center of the triangle.

Fig. 5 – Determination of a point location

The advantage of this approach in comparison with some other methods (e.g., the scanning beam), is that it will work correctly for objects that are not completely in the cell.

In order to find such a triangle, complete the following steps:

1. First, by means of binary search we find a layer in which the requested point is located. The complexity of this step is . Cases in which the point is located above or below the layers of the figure are also should be considered because the geometry of the object may be incomplete. In this case displace this point to the nearest layer.

Fig.6 - Determination of the layer, where the point lies, by binary search

2. Then, in the obtained layer for each monotone sequence using a binary search we find a triangle, in the projection of which lies the point in the projection plane.

Fig. 7 - Determination of a triangle, where the point lies, by binary search

Among these triangles we find the nearest by the coordinate. The coordinate axis should be orthogonal to the plane of projection. Keep in mind the case when the point lies outside the projection of all monotone sequences. This case should be handled separately because the geometry of the object may be incomplete. The complexity of this step is , where – the number of monotone sequences.

We get the final computational complexity of determining the relation of one point . As is small, we may conclude that this algorithm is much more efficient than the algorithms that solve this problem in .

As a result, the average complexity of the preprocessing of data can be estimated as , and the resulting complexity of the volume computing algorithm is . is the total number of sputtering points. Also the algorithm is stable for computing errors, because improper processing of requests for points, lying, for example, on the borders of the geometry, will not influence significantly on solving the problem in general with a sufficiently large number of sputtering points.

Note that in order to improve performance, the above algorithm can be modified as follows: before a preprocessing phase a set of geometric transformations of coordinates is applied. This set of geometric transformations correspond to the rotation of the object at certain angles. The number of monotone sequences in all layers is computed for each transformed objects as . The best coordinate transformation is chosen, and then to this transformation is applied to each point. The resulting complexity of the modifications is , where c is the number of angles at which the object is rotated. For small c, the time spent for this modification is extremely small in comparison with the total time of the algorithm.

Fig. 8 - The transformation of "bad" geometry

Conclusions.

A fast algorithm for computing the volume of a few geometric shapes in a hexahedral mesh cell in account with collisions between them has been introduced. It was shown that the total complexity of the algorithm is of , where on practice is negligible, and is a precision control parameter. This is significantly more effective than the algorithms that solve this problem in . Despite the fact that the computational complexity of the preprocessing phase is , and with the modification is added as well, it is necessary to consider that this is done only once and not for each cell in the computational mesh. And there may be millions of cells.

Literature

1. Constructive Solid Geometry..
2. Constructive Solid Geometry program. .
3. UnBBoolean. Author: Danilo Balby..