A new class of functions - "FLOZ- functions" (Functions of LOcal Zeroing out), which makes it possible to form the zero domain of a scalar-valued multidimensional function of complex configuration by means of R-functional modelling is considered. We represent the solution of the inverse problem of analytical geometry for a non-convex contour construction obtained by mathematical apparatus of R-functions. The problems of constructing an algorithm for automation the proposed by V.L. Rvachev solutions are described. Presented arguments show the complexity of constructing an algorithm based on recursive attachment. The functional voxel model was created in the RANOK 2D system. An approach to the function of local zeroing out (FLOZ-function) construction for the general (multidimensional) case is described. A two-dimensional function of local zeroing out is selected for solving the problem of a non-convex contour constructing. It is shown that the function of local zeroing out allows to create the sequential algorithm of automation the non-convex contour construction. Examples of automation the considered problems of V.L. Rvachev to the nonconvex contour construction are given. The function of local zeroing out for three-dimensional space (3D FLOZ-function) is considered. An example of functional voxel modelling of a 3D sphere model based on a triangulated network consisted of 80 triangles is given. voxel modelling (FVM), M-image R-functional modelling (RFM), function of local zeroing out (FLOZ-function), functional GraphiCon 2021: 31st International Conference on Computer Graphics and Vision, September 27-30, 2021, Nizhny Novgorod, Russia
The modeling of geometric objects with scalar-valued functions initially attracted specialists
primarily by the fact that such an object chiefly provides the maximum computational accuracy of scalar
values and the completeness of its differential characteristics’ representation at each point of a given
space. Secondly, the spatial constraints imposed on a geometric object in the case of modeling by other
approaches (such as, for example, parametric) can be removed now. In the 60s of the last century, V.L.
Rvachev proposed a new class of functions (R-functions) [
However, nowadays the construction of scalar-valued functions remains not an easy task that
requires a decent mathematical background and spatial intuition, allowing you to predict the
formulation of the expected result. In 1982, in work [
2021 Copyright for this paper by its authors.
The dashed lines complement the polygon 1 2 … 14 1 to a convex one with segments 2 10 и 2 2 11 14. The positive half-planes of these segments Σ210 and Σ1114 (notation adopted by the author) are located to the left of the straight lines 2 10 and 11 14. In this case, the convex polygon 1 2 10 11 14 1 is defined by the conjunction formula:
Σ12 ∩ Σ2210 ∩ Σ120 ∩ Σ12114 ∩ Σ124. (1) Embedding a convex polygonal region 10 7 6 5 2 into the resulting region leads to the 2 replacement of the symbol Σ210 in the formula (1) with the disjunction:
Σ225 ∪ Σ52 ∪ Σ62 ∪ Σ7210. (2) So, the polygon area 1 2 5 6 7 10 11 14 1 is defined by the formula
Σ12 ∩ (Σ225 ∪ Σ52 ∪ Σ62 ∪ Σ7210) ∩ Σ120 ∩ Σ12114 ∩ Σ124.
The process of sequentially cutting out the remaining convex polygonal areas will result in the following:
Figure 2 shows the result of calculating the surface of a scalar function that provides a null boundary, marked in red.
The presented surface tends to monotonicity and smoothness throughout the entire interval of the range of values, despite the sharp corners of the given contour.
The disadvantage of this approach is the complex algorithmization of recursive data processing of a set of contour points when automating such an algorithm. It is required to implement some "simulator" of nested brackets of the obtained formula, which provides recursive immersion with dynamically increasing depth and constantly changing number of nodes of the next nested contour. This often leads to the organization of additional scripts, in fact, substituting for the work of the compiler, and therefore does not give application efficiency.
To get rid of the recursive construction of a complex non-convex contour, it is necessary to transform the algorithm into a simple sequence of computing a single logical operation (for example, an intersection). To do this, it is enough to construct a scalar function that calculates a zero value in a given limited area, and fills the rest of the area with positive values. Such a function should provide generality with the multidimensional space, forming its own class - the Function of Local Zeroing out (FLOZfunction). 2. Function of Local Zeroing out (FLOZ-function)
FLOZ-function – a multidimensional function that acquires zero for a local neighborhood defined by vertices on the range of positive values.
A local neighborhood of a FLOZ-function should be understood as a simple geometric figure, the number of vertices which corresponds to the dimension of the FLOZ space (Fig. 3). For example, in
space it is a segment defined by two points, in The neighborhood is defined by a local function: space it is a triangle, etc.
( ) = 1 1 + ⋯ −1 −1 + = 0.
A local function is understood as a linear polynomial whose coefficients are local geometric characteristics , obtained by normalizing the coefficients from the equation: | = 1 1 + ⋯ + + +1 = 0, so of the norm √ 12 + ⋯ + 2 as:
The area (volume) of an n-dimensional neighborhood of FLOZ-function can be formulated in terms = √ 12 + ⋯ + 2 .
( − 1)! Successively replacing the coordinates of one of the control points of the determinant with the neighborhood.. coordinates of the considered point of the space ( ), ∈ , we obtain n terms of the
Statement: The sum of the folded neighborhoods ∑ replacement of control points with a point is equal to
=0 , obtained in turn by successive if belongs to the local neighborhood of FLOZ. Then the function of local zeroing out (FLOZ-function) in general form can be written as: =0 = 0.
We will show how FLOZ-functions work using the examples of the implementation of simple spaces 2 and 3. 1. The space 2, that is, the two vertices define a line segment. The equation of a straight line to which the segment belongs can be written in such form:
| 1 1 2 2 1 In turn, the length of the segment according to the general formulation can be written as If we substitute = 0, into the expression, then we get
It is necessary to make sure that there is at least one zero value of the function-arguments 0∩ = 0.
A similar result is expected for = 0. This means that when the function 0∩ works with flozfunctions, the zero values on both neighborhoods are preserved. For positive FLOZes + > preserving their basic property of zeroing a given local neighborhood. √ 2 + 2. This follows from the right-angled triangle rule. Hence, we can conclude that it is the Rintersection function ∩ that can correctly connect two FLOZes on the positive range of values while Hence the area of the triangular element from the given vertices
( ) = 1 + 2 + 3 − ∆ = 0.
Three equations of the plane, specified by brute-force search or exhaustive search through pairs of
vertices with one current point ( 3) to determine the coefficients and areas, can be written as:
By analogy with a two-dimensional space, a triangular FLOZ is modeled in the RANOK 3D system,
described in a specialized FORTU language [
CONSTANT X1=1., Y1=0., Z1=1.;
X2=-1., Y2=1., Z2=-1.; X3=-1., Y3=-1., Z3=-1.; A=Y1*(Z2-Z3)-Y2*(Z1-Z3)+Y3*(Z1-Z2); B=-(X1*(Z2-Z3)-X2*(Z1-Z3)+X3*(Z1-Z2)); C=X1*(Y2-Y3)-X2*(Y1-Y3)+X3*(Y1-Y2);
S=1./2.*SQRT(A*A+B*B+C*C); VARIABLE AA=Y*(Z2-Z3)-Y2*(Z-Z3)+Y3*(Z-Z2);
BB=-(X*(Z2-Z3)-X2*(Z-Z3)+X3*(Z-Z2)); CC=X*(Y2-Y3)-X2*(Y-Y3)+X3*(Y-Y2); S1=1./2.*SQRT(AA*AA+BB*BB+CC*CC); AA=Y1*(Z-Z3)-Y*(Z1-Z3)+Y3*(Z1-Z); BB=-(X1*(Z-Z3)-X*(Z1-Z3)+X3*(Z1-Z));
CC=X1*(Y-Y3)-X*(Y1-Y3)+X3*(Y1-Y); = 1, = 2, = 3, (15) (16) (17) (18) (19) (20) (21) (22) AA=Y1*(Z2-Z)-Y2*(Z1-Z)+Y*(Z1-Z2); BB=-(X1*(Z2-Z)-X2*(Z1-Z)+X*(Z1-Z2));
CC=X1*(Y2-Y)-X2*(Y1-Y)+X*(Y1-Y2); VARIABLE S3=1./2.*SQRT(AA*AA+BB*BB+CC*CC); VARIABLE SS=S1+S2+S3-S;
RETURN SS; 3. Flozation of a complex non-convex contour w12=s1+s2-((x13-x12)^2+(y13-y12)^2)^0.5 s1=((x-x13)^2+(y-y13)^2)^0.5 s2=((x14-x)^2+(y14-y)^2)^0.5 w13=s1+s2-((x14-x13)^2+(y14-y13)^2)^0.5 s1=((x-x14)^2+(y-y14)^2)^0.5 s2=((x1-x)^2+(y1-y)^2)^0.5 w14=s1+s2-((x1-x14)^2+(y1-y14)^2)^0.5 w=w1&w2&w3&w4&w5&w6&w7&w8&w9&w10&w11&w12&w13&w14
RETURN w.
There is a significant increase in computational operations, which negatively affects the running time of the algorithm. The time period in comparison with the recursive algorithm increases by two orders of magnitude. Thus, avoiding recursive complexity, we get exponentially increasing time for each added flozation step. This problem is typical for R-functional modeling in general, since the design of calculations is based on the structural attachment of functions. This problem can be avoided only by sequentially saving intermediate calculated values in a given function area at each step of the Rfunctional set-theoretic operation. In the process of flozation, this is expressed by the construction of the next FLOZ.
Let us consider one of the methods of computer modeling of the analytical function area, which allows us to fulfill the task. 4. The method of the functional voxel modeling at each point of such a domain
The essence of the method is described extensively in the works [
+1 +1 + +2 = 0 In this case, the local geometric characteristics are represented by a set of + 2 voxel images of dimension m. This allows you to replace a complex mathematical expression with such a graphical representation. In this case, the local function at a single point is capable of combining the main part of the properties of the replaced complex mathematical expression, greatly simplifying the calculations. For example, we represent a function of the form = ( − 1) −[ 2+( +1)2] + 10(0,2 − 3 − 5) −( 2+ 2) + − ( 2+ 2) 3 ; on a computer by images (Fig. 10).
С 1 С2 С3 С4
The local function takes the form: 1 + 2 + 3 − 4 = 0, = 2 −
, where form (23) (24) (25) (26) (27) (28) = 256 – the number of the palette intensity gradation. This means that the function takes the = 4 − 3 3 1 − 2 . 3
To implement the phased flozation shown in Figure 9, it is sufficient to calculate by expression (27) the value of for the intersected regions 1 and 2. Then, to carry out the R-intersection: = 1 + 2 − √( 1)2 + ( 2)2. Repeating this calculation for two more neighbour points of the M-image, we obtain the minimal spatial triangle, which plane can also be expressed by equation (25).
Expressing the numerical information through the intensity gradation of the monochrome palette = ( +1) 2 , где = 256 we will obtain four M-images, fixing a new stage of flozation. Figure 11 shows an example of the proposed FV-approach implementation to stepwise flozation. Unlike FVR-modeling, where the calculation is performed for one point of the image, here the R-function is recalculated three times and an additional calculations generate new components .
At the same time, I would like to note a significant reduction in the operating time of the algorithm with the same technical characteristics of the computer. The time spent on calculating the contour is now no more than 30 seconds, which is approximately 2 seconds for each performed flozation step for an image resolution of 400x400 pixel. In this case, the main advantage is achieved: the running time of the algorithm increases linearly and depends on the number of FLOZes, as well as the resolution of Mimages used for the computer representation of the functional-voxel model.