=Paper= {{Paper |id=Vol-2744/paper52 |storemode=property |title=Construction of the Functional Voxel Model for a Spline Curve |pdfUrl=https://ceur-ws.org/Vol-2744/paper52.pdf |volume=Vol-2744 |authors=Alexey Tolok,Nataliya Tolok,Anastasiya Sycheva }} ==Construction of the Functional Voxel Model for a Spline Curve== https://ceur-ws.org/Vol-2744/paper52.pdf

Construction of the Functional Voxel Model for a Spline
Curve*

Alexey Tolok 1[0000-0002-7257-9029], Nataliya Tolok 1[0000-0002-5511-4852], Anastasiya
1[0000-0003-3230-4271]
Sycheva
1 V.A. Trapeznikov Institute of Control Science of Russian Academy of Sciences, 65 Profso-

yuznaya street, Moscow, 117997, Russia
tolok61@mail.ru, nat_tolok@mail.ru, a.a.sycheva@mail.ru

Abstract. Analytical models are the most accurate method of geometric infor-
mation representation. Parameterized smooth curves cannot be used in the field
of analytical geometry, which explains the necessity for finding of analytical rep-
resentation of such curves. The article considered the construction of a smooth
curve presented in an analytical form and some approaches to finding an analyt-
ical model for a parametric Bezier curve. А presentation of a function in the form
of its functional areas was chosen as prototype of the analytical model. The se-
lected representation formed on the basis of the De Casteljau's method of con-
structing the Bezier curve and set-theoretic modeling. The Rvachev functions (R-
functions) are used as the mathematical apparatus of set-theoretic operations on
function areas. The functional-voxel method makes it possible to simplify the
computation of R-functional procedures. An algorithm for constructing the func-
tional area of the Bezier curve is developed on the basis of the presented com-
bined R-voxel approach. The obtained results allow for the conclusions about the
adequacy of this approach and its development protentional to construct more
complicated structures.

Keywords: Bezier curve, De Casteljau's algorithm, R-functional modelling,
Functional voxel modelling, R- voxel modelling.

1 Introduction

Computer synthesis of simple and complex geometrical objects and their transfor-
mations is essential for the wide range of design problems. The necessity to construct
the maximally accurate computer geometrical models for the contemporary design
problems remains to be the primary.
Nowadays the Set-theoretic operations for the analytical modelling of a space of the
complex function (Rvachev function [1,2]) are one of the most curious approaches to
constructing the analytically set objects of complex geometrical shape.

Copyright c 2020 for this paper by its authors. Use permitted under Creative Commons License
Attribution 4.0 International (CC BY 4.0).
2 A.Tolok, N. Tolok, A. Sycheva

CAD is traditionally considered to be the main application field of computer geom-
etry though the construction of smooth curves and surfaces in this sphere is based on
the parametrical descriptions of functions which makes impossible to apply them both
in the analytical geometry and in the R-Functional modelling.
The Functional Voxel Method [3] allows to solve this problem by providing the
mechanism for replacing the space of the analytical function 𝜔 = 𝑓(𝑋𝑚 with the space
of the local functions 𝑛1 𝑥1 + ⋯ + 𝑛𝑚 𝑥𝑚 = 𝑛𝑚+1 .

2 Previous Work

Smooth curves are one of the basic design tools applied in contemporary CAD. For
example, the reference [4] describes the application of Spline Approximation in the
CAD Systems for the Linear Constructions.
The Bezier curves represent the classic type of smooth curves are of the greatest
interest in this current research. The Bezier curves’ segmentation is described in [5].
However, we shouldn’t overlook the application of other types of curves in solving
various design problems. In [6] and [7] the application of parametrically described B-
spline in the CAD parametrical geometry optimization problems and pavement model-
ling is considered. T-splines being the generalization of B-splines are becoming more
widespread. The authors of [7] represented their own isogeometric approach to shape
optimization on the basis of this type of splines.

3 Analytical representation of smooth curve

3.1 Smoothing cubic spline

One of the simplest analytical approaches to a smooth curve representation is to define
it in the polynomial form. Having the purpose to obtain smoother shape and more flex-
ible design, let’s consider cubic polynomial:

𝑦=𝑎𝑥3+𝑏𝑥2+𝑐𝑥+𝑑 (1)

The cubic spline construction is specified by four points P0(x0, y0), P1(x1, y1), P2(x2, y2),
P3(x3, y3). At the same time, points P0 and P3 are situated on the segment borders and
points P1 and P2 allow to define the position of a tangent to a curve in the boundary
points.
Smoothing cubic spline construction demands implementation of several conditions:

1. The curve passes through the boundary points of the segment
2. First derivatives of the neighbor segments of the spline should be equal in the bound-
ary points
These conditions can be described by the system of four equations (2).
Construction of Functional Voxel Model for a Spline Curve 3

𝑦0 = 𝑎𝑥03 + 𝑏𝑥02 + 𝑐𝑥0 + 𝑑
𝑦3 = 𝑎𝑥33 + 𝑏𝑥32 + 𝑐𝑥3 + 𝑑
𝑦1 −𝑦0 (2)
= 3𝑎𝑥02 + 𝑏𝑥0 + 𝑐
𝑥 −𝑥
1 0
𝑦2 −𝑦3 2
{ 𝑥2−𝑥3 = 3𝑎𝑥3 + 𝑏𝑥3 + 𝑐

The results of visualizing the cubic polynomial which coefficients are determined
by represented system of equations are illustrated in Fig.1. The construction of smooth
curve can be achieved when the conditions (2) are met.
However, constructing the closed contours is hindered – the curve is buckling on a
tangent in reverse preventing self-intersections.

Fig. 1. Construction of the smooth cubic spline by 4 points.

The application of the proposed approach gives us the possibility to depict the curve
that consists of several segments (Fig.2) successfully. Unfortunately, it doesn’t solve
the problem of constructing the complex closed structures.x

Fig. 2. Construction of the smooth cubic spline by 4 points.

3.2 Bezier curve
Bezier spline is the classical type of smooth curves represented parametrically. The
construction of Bezier curve is carried out by means of Bernstein polynomials [4]:

𝑏𝑖,𝑛 (𝑡) = (𝑛𝑖)𝑡 𝑖 (1 − 𝑡)𝑛−𝑖 ,
𝑛! (3)
(𝑛𝑖) = ,
𝑖!(𝑛−𝑖)!

where (𝑛𝑘) – the amount of combinations of n choose i, n – exponent of the polynomi-
als, i - consecutive number of the anchor vertex. At the same time, abscissa and ordinate
are described parametrically by the system of equations (4).
𝑥 (𝑡) = ∑𝑛𝑖=0 𝑥𝑖 𝑏𝑖,𝑛 (𝑡), 0 ≤ 𝑡 ≤ 1
{ (4)
𝑦(𝑡) = ∑𝑛𝑖=0 𝑦𝑖 𝑏𝑖,𝑛 (𝑡), 0 ≤ 𝑡 ≤ 1
4 A.Tolok, N. Tolok, A. Sycheva

where xi and yi - coordinates of anchor vertex i.
However, the application of this type of curves in the analytical calculations of the
R-functional modelling demands its representation in the form ω = 𝑓 (x, y).
The most evident approach to solving this problem is to express parameter t in terms
of one of the coordinates. To simplify evaluations let’s consider the expression of t-
parameter in terms of x-coordinate in case of Bezier curve of degree 2 with anchor
vertices P0(x0, y0), P1(x1, y1), P2(x2, y2).
The parameter t in the current point A will be expressed as:

𝑃0 −𝑃1 ±√(𝑃0 −2𝑃1 +𝑃2 )𝐴+𝑃12 −𝑃0 𝑃2
, 𝑃0 − 2𝑃1 + 𝑃2 ≠ 0
𝑃0 −2𝑃1 +𝑃2
𝐴−𝑃0
𝑡= , 𝑃0 − 2𝑃1 + 𝑃2 = 0 и 𝑃1 ≠ 𝑃0 (5)
2(𝑃1 −𝑃0 )
𝐴−𝑃
0
√ , 𝑃0 = 𝑃1 ≠ 𝑃3
{ 𝑃2−𝑃1

Even in case of Quadratic Bezier Curve the complexity of parameter expression is ob-
served.
The parameter t can also be expressed by means of local computer geometry as
t=f(x). For this purpose, it’s possible to use the equation of a tangent to the curve in the
point A(tA, XA):

𝐴𝑡 + 𝐵𝑥 + 𝐶 = 0 (6)

The coefficients of the equation will be defined via inclination angles n1, n2, n3 between
the normal to the tangent at the point of a curve and the coordinate axes OX, OY, OZ.
Considering that the tangent line passes through some point B(tA+ΔtA, XA+ΔXA) in
the neighborhood of the point A, let’s write the determinant:
𝑡 𝑥 1
| 𝑡𝐴 𝑋𝐴 1| = −Δ𝑋𝐴 𝑡 + Δ𝑡𝐴 𝑋 + (𝑡𝐴 (𝑋𝐴 + Δ𝑋𝐴 ) − 𝑋𝐴 (𝑡𝐴 + Δ𝑡𝐴 )) (7)
𝑡𝐴 + Δ𝑡𝐴 𝑋𝐴 + Δ𝑋𝐴 1
Thus, the coefficients of the equation are:
𝐴 = −Δ𝑋𝐴
𝐵 = Δ𝑡𝐴 (8)
𝐶 = 𝑡𝐴 𝑋𝐴 + Δ𝑋𝐴 ) − 𝑋𝐴 (𝑡𝐴 + Δ𝑡𝐴 )
(

We determine the inclination angles n1, n2, n3 by normalizing the coefficients:
𝐴 𝐵 𝐶
𝑁 = √𝐴2 + 𝐵2 + 𝐶 2 , 𝑛1 = 𝑁 , 𝑛2 = 𝑁 , 𝑛3 = 𝑁 (9)

On this basis we can obtain the expression t=f(x):
𝑛1 𝑡 + 𝑛2 𝑥 + 𝑛3 = 0
𝑡=
−𝑛2 𝑥+𝑛3 (10)
−𝑛1
Construction of Functional Voxel Model for a Spline Curve 5

The local geometrical characteristics are calculated and kept over the entire interval
from 0 till 1 of the t-parameter. Using the given value of the x coordinate and the cor-
responding inclination angles n1, n2, n3, we determine the value of the y coordinate:
−𝑛2 𝑥+𝑛3 2 −𝑛2 𝑥+𝑛3 −𝑛2 𝑥+𝑛3 2
𝑦(𝑥 ) = (1 − ) 𝑦0 + (2 − ) 𝑡𝑦1 + ( ) 𝑦2 (11)
−𝑛1 −𝑛1 −𝑛1

The result of such algorithm implementation is represented in Fig. 3:

Fig. 3. Construction of the Bezier curve by means of local-geometric approach

Bezier curve can be successfully visualized in case of sequent location of anchor points
along the axis x. Otherwise, the construction of the curve disrupts because of its’ cur-
vature which is peculiar to the parametrical nature. In this case, it’s possible to apply
the rotation of the coordinate system so that the second anchor point will always lie
between the first and the last one [9]. But with an increase of the amount of anchor
points the complexity of multiple coordinate system rotations together with their cor-
respondence will arise.
Let’s consider another approach to the analytical representation of the Bezier curve.
Parameters tx and ty separately determine the values of coordinates X and Y corre-
spondingly to the parametrical expression of the Bezier curve. The points where pa-
rameters tx and ty are matching, form the Bezier curve. The sign of the Difference of
parameters tx and ty will determine the external and internal fields of the surface z = ty
– tx of the Bezier curve.
Fig.4 illustrates the implementation of such an approach:

Fig. 4. Constructing the surface z.

It’s possible to draw a conclusion that the application of this algorithm also doesn’t
allow to obtain an appropriate image of the Bezier curve in consequence of the curva-
ture peculiar to it.
Speaking about the Bezier curve, we cannot help but mention the De Casteljau's
algorithm (Fig.5) [4]. On the basis of this algorithm lies the finding the Bezier curve
tangents at each value of t-parameter. In case of the quadratic Bezier curve, t-parameter
defines the location of the tangent segment Q0Q1, which ends are situated on the
6 A.Tolok, N. Tolok, A. Sycheva

segments P0P1, P1P2 of anchor polygon. The point of tangency R in the segment Q0Q1
can also be determined by the t-parameter.

Fig. 5. De Casteljau's algorithm.

This algorithm is not only easy to implement but also convenient to apply in case of
Bezier curve of higher degrees. To construct the cubic Bezier curve (Fig.5) the t-pa-
rameter determines location of the tangent point A on the segment R0R1, location of the
endpoints R0 and R1 on the segments Q0Q1 and Q1Q2 and location of the endpoints Q0,
Q1, Q2 on the segments P0P1, P1P2, P2P3.
De Casteljau's algorithm does not define the analytical representation of the Bezier
curve, but can well be applied for this purpose. As an analytical representation of a
function, we can use ranges of a function. Each tangent to a Bezier curve determines
two half-planes with positive and negative value of the function space and the zero
value on the boundary. Intersection of areas of two tangent lines will give its’ aggregate
positive area. The sequential intersection of the areas of the tangent functions form the
different-sign space of the curve function. Internal area of the curve will be defined by
the positive sign of the area, external – by the negative sign. Zero boundary will de-
scribe the curve.
The Fig.6 illustrates the intersection of areas of tangent functions obtained when t=t1
и t=t2. Hatched areas visualize the positive areas of functions for each tangent. The
cross-hatched area is the result of their intersection, so it is the aggregate positive area
of the functions.

Fig. 6. Intersection of the areas of two tangent functions to the Bezier curve.
Construction of Functional Voxel Model for a Spline Curve 7

4 R-voxel modelling

4.1 The principles R-voxel modelling
The proposed algorithm application demands set-theoretic operations on the areas of
analytically represented functions.
The analytical representation of the space of each function allow to obtain the
method functional voxel modelling in the form of space of the local function as it was
mentioned above. At the same time, the function is described by a set of voxel images
(Image-model or M-image), mapping the local geometrical characteristics at each point
of the function space – the components of a normal of higher dimensionality [3].
Realization of set-theoretic operations on the analytical representation of the func-
tions is possible with the application of R-functional modelling [1, 2].
Negation operation for the function as well as union and intersection operations for
the areas of two functions form the complete 𝛼-system of R-functions:

𝑋̅ ≡ −𝑌
1
X ∨𝛼 𝑌 = 1+𝛼 (𝑋 + 𝑌 + √𝑋 2 + 𝑌 2 − 2𝛼𝑋𝑌) (12)
1
X ∧𝛼 𝑌 = (𝑋 + 𝑌 − √𝑋 2 + 𝑌 2 − 2𝛼𝑋𝑌)
1+𝛼

Application of the R-functional calculations in pure form is a complex computational
procedure. At the same time, the computational complexity of the resulting expression
directly depends on the complexity of the original functions. Application of the func-
tional voxel method (FVM) to the calculation of R-functional expressions significantly
simplifies computing of the resulting function. These two approaches can be united by
one general condition – preserving positive value in the internal area of a function, the
negative value – in the external area and zero value on the boundaries. Moreover, this
condition is met at any value of the parameter α of complete system of R-functions that
allow to simplify calculations assuming α=1.
Intersection operation for areas of two functions with the accepted simplification is
described by the expression:

𝑋 ∧1 𝑌 = 0.5(𝑋 + 𝑌 − √𝑋 2 + 𝑌 2 − 2𝑋𝑌) =
(13)
0.5(𝑋 + 𝑌 − √(𝑋 − 𝑌)2 ) = 0.5(𝑋 + 𝑌 − |𝑋 − 𝑌|)

Within solving problem it is possible to ignore the multiplication of the resulting
expression on the positive number because it doesn’t affect the sign of expression:

X ∧1 𝑌 = 𝑋 + 𝑌 − |𝑋 − 𝑌| (14)

As it seen from the expression, intersection operation for areas of two functions consti-
tutes the sequential realization of four operations:

1. Union of areas of original functions;
2. Complement of areas of original functions;
3. Absolute value of the complement of areas of original functions;
8 A.Tolok, N. Tolok, A. Sycheva

4. Complement of areas obtained at the stages 1 and 3.
Let us consider the simple example of an implementation of such algorithm.
We carry out the intersection of areas for functions X and Y for horizontal and ver-
tical lines. The first function is described by four images 𝐶𝑋1 , 𝐶𝑋2 , 𝐶𝑋3 , 𝐶𝑋4 , the second –
similarly by images 𝐶𝑌1 , 𝐶𝑌2 , 𝐶𝑌3 , 𝐶𝑌4 . The fig. 7 illustrates M-images of the functions X
and Y as well as visualization of space of their functional areas 𝑍𝑋 , 𝑍𝑌 . The first three
images for each line describe the components of a normal n1, n2, n3 at each point of
space, while fourth images are mapping the component n4, which provide a character-
istic of binding of tangent location to the corresponding point of the space.

Fig. 7. The Functional-voxel model of two lines.

Let n1X , nX2 , nX3 , nX4 denote the components of a normal of the first straight line, and n1Y ,
nY2 , nY3 , nY4 - the components of a normal of the second straight line.
For each operation of the introduced algorithm, we calculate the values of n1, n2, n3,
n4, relatively to the colour intensity palette 𝐶𝑖 (𝑖 = 1 … 4) for the application in further
calculations. Then, the first step of the algorithm (union) will be implemented by the
following expressions [3]:

𝑛1𝑋+𝑌 = 𝑛1𝑋 𝑛3𝑌 + 𝑛1𝑌 𝑛3𝑋
𝑛2𝑋+𝑌 = 𝑛2𝑋 𝑛3𝑌 + 𝑛2𝑌 𝑛3𝑋
(15)
𝑛3𝑋+𝑌 = 𝑛3𝑋 𝑛3𝑌
𝑛4 = 𝑛4𝑋 𝑛3𝑌 + 𝑛4𝑌 𝑛3𝑋
𝑋+𝑌

In turn, the Complement will be almost similarly implemented by changing the sign to
minus:

𝑛1𝑋−𝑌 = 𝑛1𝑋 𝑛3𝑌 − 𝑛1𝑌 𝑛3𝑋
𝑛2𝑋−𝑌 = 𝑛2𝑋 𝑛3𝑌 − 𝑛2𝑌 𝑛3𝑋
(16)
𝑛3𝑋−𝑌 = 𝑛3𝑋 𝑛3𝑌
𝑛4𝑋−𝑌 = 𝑛4𝑋 𝑛3𝑌 − 𝑛4𝑌 𝑛3𝑋
Construction of Functional Voxel Model for a Spline Curve 9

Computing the Absolute value of the complement of original expressions is carried out
in dependence if the sign of the local function:
𝑛 𝑋−𝑌 𝑛 𝑋−𝑌 𝑛 𝑋−𝑌
𝑧 = − 𝑛1𝑋−𝑌 𝑥 − 𝑛2𝑋−𝑌 𝑦 + 𝑛4𝑋−𝑌
3 3 3
|𝑋−𝑌|
𝑛3 = 𝑛3𝑋−𝑌 (17)
|𝑋−𝑌| 𝑋−𝑌
𝑧 < 0, 𝑛1,2,4 = 1 − 𝑛1,2,4
|𝑋−𝑌| 𝑋−𝑌
𝑧 > 0, 𝑛1,2,4 = 𝑛1,2,4

The last step is the Complement of expressions obtained at the stages 1 and 3:
𝑋+𝑌−|𝑋−𝑌| |𝑋−𝑌|
|𝑋−𝑌| 𝑋+𝑌
𝑛1 = 𝑛1𝑋+𝑌 𝑛3 𝑛3 − 𝑛1
𝑋+𝑌−|𝑋−𝑌| 𝑋+𝑌 |𝑋−𝑌| |𝑋−𝑌| 𝑋+𝑌
𝑛2 = 𝑛 2 𝑛3 − 𝑛2 𝑛3
𝑋+𝑌−|𝑋−𝑌|
(18)
𝑋+𝑌 |𝑋−𝑌|
𝑛3 = 𝑛3 𝑛3
𝑋+𝑌−|𝑋−𝑌| 𝑋+𝑌 |𝑋−𝑌| |𝑋−𝑌| 𝑋+𝑌
𝑛4 = 𝑛 4 𝑛3 − 𝑛4 𝑛3
𝑋+𝑌−|𝑋−𝑌|
Four M-images with calculated values n1,2,3,4 , as well as the visualization of the
obtained functional area are represented in the Fig.8.

Fig. 8. The result of intersection of two straight lines.

Thus, we can observe R-voxel implementation for Intersection operation for areas of
two functions.

4.2 R-voxel modelling of the Bezier curve
The construction of the Bezier curve by an approach proposed in paragraph 3.2 is im-
plemented by means of the algorithm represented in paragraph 4.1. Thus, the algorithm
of creating functional-voxel representation of the Bezier curve has the following order:

1. Constructing the initial functional-voxel model of the first tangent line (t=0) by
means of a set of M-images of the function X (𝐶𝑋1 , 𝐶𝑋2 , 𝐶𝑋3 , 𝐶𝑋4 ).
2. Increase the value of the t-parameter by the value of chosen step.
3. Do while t<1 :
a. Construct the functional voxel model of the tangent at the current value of t as M-
images of the function Y (𝐶𝑌1 , 𝐶𝑌2 , 𝐶𝑌3 , 𝐶𝑌4 ).
b. Carry out the intersection of the areas of functions X and Y.
10 A.Tolok, N. Tolok, A. Sycheva

c. Keep the result of intersection as M-images of the function X (𝐶𝑋1 , 𝐶𝑋2 , 𝐶𝑋3 , 𝐶𝑋4 ).
d. Increase the value of t-parameter by the value of chosen step.
4. Visualize the functional area of the resulting function X.
Figure 9 represents the four M-images and visualization of the Range of a curve
constructed by means of this algorithm. The last image (on the right side) illustrates the
anchor points of the curve and the set of used tangents.

Fig. 9. Analytical representation of the Bezier curve.

Thus, the construction of the smooth curve can be successfully realized. Due to the De
Casteljau's method lying in the base it is possible to similarly construct the curves by
more points. The figure 10 represents the set of different curves constructed by 4 anchor
points.

Fig. 10. Cubic Bezier curve.

As it seen from the represented images, it is also possible to construct closed contours
applying this method. Further, via intersection of the areas of the few Bezier curves
with each other or with the areas of other functions, it will be possible to construct more
complicated structures.

5 Conclusion

The represented approach provides the great opportunities of complete application of
parametrically defined Bezier curve for the analytical modelling in the R-functional
modelling procedures, which broadens the set of complicated curvilinear contours ap-
plied for the construction in CAD models.
Construction of Functional Voxel Model for a Spline Curve 11

References
1. Rvachev V.: Theory of R-functions and Some Applications. Naukova Dumka, Kiev (1982).
2. Sheiko T., Maksimenko-Sheiko K., Litvinova Yu., Lisin D.: R-functions and chevron sur-
faces in machine building. Problemy mashinostroeniya 20(2), 54-60 (2017).
3. Tolok A.: Functional Voxel Method in Computer Modeling. Fizmatlit, Moscow (2016).
4. Karpov D., Struchenkov V.: Dynamic Programming as a Method of Spline Approximation
in the CAD Systems of Linear Constructions. Russian Technological Journal 7(3), 77-88
(2019).
5. Guo M., Wang W., Zhao G. and Du X.: Bézier Segmentation of T-spline Solids in Paramet-
ric Domain. Computer-Aided Design & Applications 17(3), 502-512 (2019).
6. Zhang X.: CAD-based geometry parametrisation for shape optimisation using Non-uniform
Rational B-splines. Doctoral dissertation, Queen Mary University of London (2018).
7. Wedel A., Franke U., Badino H., Cremers D.: B-spline modeling of road surfaces for
freespace estimation. 2008 IEEE Intelligent Vehicles Symposium, 828-833 (2008)
8. Lian H., Kerfriden P., Bordas S.: Shape optimization directly from CAD: An isogeometric
boundary element approach using T-splines. Computer Methods in Applied Mechanics and
Engineering 317, 1-41 (2017).
9. Tolok A., Tolok N., Loktev M.: Modeling Function Domain for Curves Constructed Based
on a Linear Combination of Basis Bernstein Polynomials. Programming and Computer Soft-
ware 44(6), 526–532 (2018).