This work is licensed under the Creative Commons Attribution 4.0 International License.
Introduction
The mimetic discretization of differential operators is a process that maintains the fundamental properties of continuous differential operators. The main goal in this process is to ensure that the protected properties are maximized and, if not, to give up most of the properties. Geometric partial differential equations are very important to find discrete analogues of differential geometric operators such as mean curvature, Gaussian curvature and Laplace Beltrami, which are defined by surface normal. The de facto methods, such as finite differences and finite elements, are directly related to the discretization of the equation system. A disadvantage of this method is that the selected discretization process may have little connection to the underlying physical problem. However, mimetic methods start with discrete analogue of the continuous theory underlying the problem. Once discrete operators conform to extended physical laws, these mimetic operators can be applied to partial differential equations or integral equation systems. Consequently, it is possible to obtain the discretization of the boundary value problem, which is in accordance with the physical laws on the considered set of definitions. Mimetic methods are a fundamental tool for simulations that do not change their physical properties, whose solution is suddenly variable, irregular grid structures, or long-running simulations, and it is getting more and more important [1]. Mimetic methods are generally used in logically uniform grids [2, 3, 4], in regular or unstructured grids [5, 67], in triangular grids [8, 9, 10], and in polygonal grids [11, 12].
In [1], authors particularly point out that mimetic discretization is more effective in practice. The time scale calculus which is an efficient mathematical theory that unifies discrete and continuous calculus emerges as a powerful tool for mimetic discretization process. The first link between effective discretization and generalization of time scale theory and mimetic methods is presented in [13]. The theory of time scales calculus has also provided considerable development in recent years [14, 15, 16, 17, 18]. The first work on the geometric interpretation of the theory [19] provided the introduction of the concept of partial dynamic derivatives on time scales [20] and various geometric studies are introduced [21, 22, 23, 24, 28].
In this study, we present a framework to express the vertices of non-uniform rectangular grids as the points of surface parameterized on a tensor product of two time scales. The mimetic discretization aspect of the theory of time scales calculus in the geometric sense is first presented in [25] in the terms of symmetric differentiation. The rest of paper is as follows: in Section 2, we present the symmetric differentiation on time scales and the geometric aspect of the theory. We also explain how to compute normal vector fields of surfaces on time scales. In Section 3, we introduce a method to find normal fields of set of discrete points by using symmetric dynamic derivatives. To this end, we determine the set of discrete points in ℝ3, namely point clouds, as the subset of a grid like structure emerge from a surface on time scales. In Section 4, we present the numerical results of our method and compare them with the results of well-known method Delaunay triangulation. Finally, in Section 5, we give the conclusions of our study.
Symmetric Calculus on Time Scales
An n-dimensional time scale is defined by the Cartesian product as
[{\mathbb{T}^n} = {\mathbb{T}_1} \times \ldots \times {\mathbb{T}_n},
where for i ∈ {1,..., n} the sets 𝕋i are time scales. A time scale 𝕋i is a non-empty closed subset of reals. We refer readers to [26, 27] for details on the theory of single and multivariable dynamic calculus on time scales. Throughout this study we denote σi and ρi as the forward and backward jump operators of the time scale 𝕋i, respectively. Besides, we set that if 𝕋i has a left scattered maximum M and right scattered minimum m, then ({\mathbb{T}_i})_\kappa ^\kappa = {\mathbb{T}_i}\backslash \{ m,M\} , else ({\mathbb{T}_i})_\kappa ^\kappa = {\mathbb{T}_i}.
Definition 1
[25] A function f : 𝕋n → ℝ is symmetric differentiable at a point {t_0} \in ({\mathbb{T}_1})_\kappa ^\kappa \times \ldots \times ({\mathbb{T}_n})_\kappa ^\kappa if there exist numbers A1,..., An independent of t ∈ 𝕋n such that for all t ∈ Uδ (t0) and i ∈ {1,..., n},
[\begin{gathered}
f(t_1^0, \ldots ,{\sigma _i}(t_i^0), \ldots ,t_n^0) - f({t_1}, \ldots ,{t_n}) + f(2t_1^0 - {t_1}, \ldots ,2t_i^0 - {t_i}, \ldots ,2t_n^0 - {t_n}) \hfill \\
- f(t_1^0, \ldots ,{\rho _i}(t_i^0), \ldots ,t_n^0) \hfill \\
= \sum\limits_{i = 1}^n {A_i}[{\sigma _i}(t_i^0) + 2t_i^0 - 2{t_i} - {\rho _i}(t_i^0)] + \sum\limits_{i = 1}^n {\alpha _i}[{\sigma _i}(t_i^0) + 2t_i^0 - 2{t_i} - {\rho _i}(t_i^0)] \hfill \\
\end{gathered}
where δ is sufficiently small positive number, Uδ (t0) is the δ-neighborhood of t0, and αi = αi(t0, t) defined on Uδ (t0) such that it is equal to zero for t = t0 and \mathop {\lim }\nolimits_{t \to {t^0}} {\alpha _i} = 0 for all i ∈ {1,..., n}.
Definition 2
[25] Let f : 𝕋1 × 𝕋2 → ℝ be a real valued function and ({t_0},{s_0}) \in \left( {{\mathbb{T}_1}} \right)_\kappa ^\kappa \times \left( {{\mathbb{T}_2}} \right)_\kappa ^\kappa . For all ε1 > 0, there is an open (relative to the topology of 𝕋1 × 𝕋2) neighborhood U1 of (t0, s) such that for all (t, s) ∈ U1[\begin{gathered}
\left| {\left[ {f({\sigma _1}({t_0}),s) - f(t,s) + f(2{t_0} - t,s) - f({\rho _1}({t_0}),s)} \right] - {f^{{\diamondsuit _1}}}\left[ {{\sigma _1}({t_0}) + 2{t_0} - 2t - {\rho _1}({t_0})} \right]} \right| \hfill \\
\leqslant {\varepsilon _1}\left| {{\sigma _1}({t_0}) + 2{t_0} - 2t - {\rho _1}({t_0})} \right|. \hfill \\
\end{gathered}
Definition 3
[25] Let f : 𝕋1 × 𝕋2 → ℝ be a real valued function and ({t_0},{s_0}) \in \left( {{\mathbb{T}_1}} \right)_\kappa ^\kappa \times \left( {{\mathbb{T}_2}} \right)_\kappa ^\kappa . For all ε2 > 0, there is an open (relative to the topology of 𝕋1 × 𝕋2) neighborhood U2 of (t, s0) such that for all (t, s) ∈ U2[\begin{gathered}
\left| {\left[ {f(t,{\sigma _2}({s_0})) - f(t,s) + f(t,2{s_0} - s) - f(t,{\rho _2}({s_0}))} \right] - {f^{{\diamondsuit _2}}}\left[ {{\sigma _2}({s_0}) + 2{s_0} - 2s - {\rho _2}({s_0})} \right]} \right| \hfill \\
\leqslant {\varepsilon _2}\left| {{\sigma _2}({s_0}) + 2{s_0} - 2s - {\rho _2}({s_0})} \right|. \hfill \\
\end{gathered}
In Δ− and ∇− calculus on time scales, the differentiability of functions defined on time scales comes up with concepts called completely Δ− and completely ∇− differentiability [20, 29]. Basically, completely differentiability hypotheses assume the equality of right and left hand side dynamic derivatives. If the point is left dense and right scatter the σi-completely differentiability or if the point is right dense and left scatter the ρi-completely differentiability concepts of the functions on 𝕋n emerge. However, these hypotheses have strong restriction to define geometric operators on time scales. Besides, geometric operators are not well-defined on isolated time scales. For instance, in [24], authors defined the curvature of curves on time scales by using Δ-derivatives. Analogously, the backward curvature can be defined by using ∇-derivatives. However, such definitions of the curvature are not in unified way, hence would not be useful tool to mimetic discretization process. The introduction of the symmetric dynamic calculus on time scales to overcome such geometric drawbacks are discussed in [25] in details.
Definition 4
[25] Let 𝒮 be a closed subset of ℝ3. 𝒮 is a surface if for each point P in 𝒮, there is a neighborhood A of P and a function φ : U → 𝒮 where U is a closed set in ℝ2 and an open set in time scale topology satisfying the following conditions:
φ : U → ℝ3 is ⋄-differentiable and for all (t, s) ∈ U[\frac{{\partial \varphi (t,s)}}{{{\diamondsuit _1}t}} \times \frac{{\partial \varphi (t,s)}}{{{\diamondsuit _2}s}} \ne 0,
i.e., φ is ⋄-regular.
φ(U) = 𝒮 ∩ A and φ : U → φ(U) is a homeomorphism.
The function φ : U → 𝒮 is called a surface patch. 𝒮 is called a ⋄-smooth surface if, for all points P in 𝒮 there exists a surface patch such that P ∈ φ(U).
Proposition 1
Let U ⊂ 𝕋2and f be a ⋄-differentiable function. Then, the set[\mathcal{S} = \{ (t,s,f(t,s))\;|\;(t,s) \in {\mathbb{T}_1} \times {\mathbb{T}_2}\} determines a ⋄-smooth surface. Proof. Let {t, s} be the Euclidean coordinate system of 𝕋2. Since the coordinate functions and fare ⋄-differentiable, φ : U → 𝒮 is also ⋄-differentiable. Jacobian matrix of φ respect to symmetric differentiation is[J(\varphi ) = \left( {\begin{array}{*{20}{c}}
{\frac{{\partial t}}{{{\diamondsuit _1}t}}}&{\frac{{\partial t}}{{{\diamondsuit _2}s}}} \\
{\frac{{\partial s}}{{{\diamondsuit _1}t}}}&{\frac{{\partial s}}{{{\diamondsuit _2}s}}} \\
{\frac{{\partial f(t,s)}}{{{\diamondsuit _1}t}}}&{\frac{{\partial f(t,s)}}{{{\diamondsuit _2}s}}} \\
{}&{}
\end{array}} \right) = \left( {\begin{array}{*{20}{c}}
1&0 \\
0&1 \\
{\frac{{\partial f(t,s)}}{{{\diamondsuit _1}t}}}&{\frac{{\partial f(t,s)}}{{{\diamondsuit _2}s}}} \\
{}&{}
\end{array}} \right).rank J(φ) = 2 for all (t, s) ∈ U, hence φ is ⋄-regular. Besides it is trivial that φ mapping is a homeomorphism.
In this study, we determine the metric tensor of a surface 𝒮 on time scales by the partial ⋄-derivatives of φ. If \frac{{\partial \varphi }}{{{\diamondsuit _1}t}} \times \frac{{\partial \varphi }}{{{\diamondsuit _2}s}} \ne \vec 0, the tangent plane to 𝒮 is spanned by \frac{{\partial \varphi }}{{{\diamondsuit _1}t}} and \frac{{\partial \varphi }}{{{\diamondsuit _2}s}}. Hence, mimetically, the surface normal vector can be compute as
[{\vec N_{TS}} = \frac{{\partial \varphi }}{{{\diamondsuit _1}t}} \times \frac{{\partial \varphi }}{{{\diamondsuit _2}s}}.
In the calculation of the normal vector fields of surfaces, two cases emerge on finiteness of time scales. If the time scales are isolated and infinite, then the normal vector fields can be computed directly by symmetric differentiation. However, if the time scales are isolated and finite, then we need to compute the vector fields on boundaries by using Δ or ∇ differentiation. To see this, we give the following theorems:
Theorem 2
Let U and Ũ be nonempty closed subsets of ℝ2and φ : U → 𝒮 be a ⋄-regular surface patch. If φ :Ũ → U is diffeomorphism, then the function[\tilde \varphi = \varphi \circ \phi :\tilde U \to {\mathbb{R}^3}is a ⋄-regular surface patch. Proof. Since φ is continuous and φ is in C_{rld}^\infty , it is straightforward that \tilde \varphi is in C_{rld}^\infty . Now let \phi (\tilde t,\tilde s) = (t,s) for (t, s) ∈ U and(\tilde t,\tilde s) \in \tilde U. Let\tilde \varphi be ⋄-differentiable. By the chain rule, we obtain[\frac{{\partial \tilde \varphi }}{{{\diamondsuit _{(1)}}\tilde t}} = \frac{{\partial t}}{{{\diamondsuit _{(1)}}\tilde t}}\frac{{\partial \varphi }}{{{\diamondsuit _1}t}} + \frac{{\partial s}}{{{\diamondsuit _{(1)}}\tilde t}}\frac{{\partial \varphi }}{{{\diamondsuit _2}s}}and[\frac{{\partial \tilde \varphi }}{{{\diamondsuit _{(2)}}\tilde s}} = \frac{{\partial t}}{{{\diamondsuit _{(2)}}\tilde s}}\frac{{\partial \varphi }}{{{\diamondsuit _1}t}} + \frac{{\partial s}}{{{\diamondsuit _{(2)}}\tilde s}}\frac{{\partial \varphi }}{{{\diamondsuit _2}s}}.Hence,[\frac{{\partial \tilde \varphi }}{{{\diamondsuit _{(1)}}\tilde t}} \times \frac{{\partial \tilde \varphi }}{{{\diamondsuit _{(2)}}\tilde s}} = \left( {\frac{{\partial t}}{{{\diamondsuit _{(1)}}\tilde t}}\frac{{\partial s}}{{{\diamondsuit _{(s)}}\tilde s}} - \frac{{\partial t}}{{{\diamondsuit _{(s)}}\tilde s}}\frac{{\partial s}}{{{\diamondsuit _{(1)}}\tilde t}}} \right)\frac{{\partial \varphi }}{{{\diamondsuit _1}t}} \times \frac{{\partial \varphi }}{{{\diamondsuit _2}s}}.
The coefficient at the right side of the equation (1) is equal to determinant of the jacobian matrix[J(\phi ) = \left( {\begin{array}{*{20}{c}}
{\frac{{\partial t}}{{{\diamondsuit _{(1)}}\tilde t}}}&{\frac{{\partial t}}{{{\diamondsuit _{(2)}}\tilde s}}} \\
{\frac{{\partial s}}{{{\diamondsuit _{(1)}}\tilde t}}}&{\frac{{\partial s}}{{{\diamondsuit _{(2)}}\tilde s}}} \\
{}&{}
\end{array}} \right)\;.
As a result of Theorem 2, we may remark that if 𝕋1 × 𝕋2 is an infinite isolated time scale, then it is possible to find a coordinate change which makes the point in ({\widetilde \mathbb{T}_1})_\kappa ^\kappa \times ({\widetilde \mathbb{T}_2})_\kappa ^\kappa . Hence, normal vector field of a surface on time scales can be computed directly by symmetric differentiation. If 𝕋1 × 𝕋2 is a finite time scale, the natural boundaries of the surface arise at the end points of time scales. Let t_0^m and s_0^m be the minimum points and t_0^M and s_0^M be the maximum points of 𝕋1 and 𝕋2, respectively. By Theorem 3,
[\frac{{\partial \varphi (t,s)}}{{{\diamondsuit _1}t}} = \frac{{\partial \varphi (t,s)}}{{{\Delta _1}t}}
for all (t,s) \in t_0^m \times {\mathbb{T}_2},
[\frac{{\partial \varphi (t,s)}}{{{\diamondsuit _1}t}} = \frac{{\partial \varphi (t,s)}}{{{\nabla _1}t}}
for all (t,s) \in t_0^M \times {\mathbb{T}_2},
[\frac{{\partial \varphi (t,s)}}{{{\diamondsuit _2}s}} = \frac{{\partial \varphi (t,s)}}{{{\Delta _2}s}}
for all (t,s) \in {\mathbb{T}_1} \times s_0^m, and
[\frac{{\partial \varphi (t,s)}}{{{\diamondsuit _2}s}} = \frac{{\partial \varphi (t,s)}}{{{\nabla _2}s}}
for all (t,s) \in {\mathbb{T}_1} \times s_0^M.
Figure 1
, we present a surface parameterized on a finite isolated time scale 𝕋1 × 𝕋2, where 𝕋1 = {t1, t2, t3, t4} and 𝕋2 = {s1, s2, s3, s4}. This figure also serves a good example of a non-regular rectangular grids which has vertices on a surface parameterized on an isolated time scale. In this figure, the arrows represent the normal vectors at respected points. 𝕋1 and 𝕋2 both have the usual time scale topology which is respect to partial order of the indices. Hence, the only non-boundary point is φ(t2, s2) on the surface. Thus, the normal vectors can be computed as
[\begin{gathered}
{{\vec N}_1} = \frac{{\partial \varphi ({t_1},{s_2})}}{{{\Delta _1}t}} \times \frac{{\partial \varphi ({t_1},{s_2})}}{{{\diamondsuit _2}s}},\;\;{{\vec N}_2} = \frac{{\partial \varphi ({t_2},{s_2})}}{{{\diamondsuit _1}t}} \times \frac{{\partial \varphi ({t_2},{s_2})}}{{{\diamondsuit _2}s}} \hfill \\
{{\vec N}_3} = \frac{{\partial \varphi ({t_4},{s_2})}}{{{\nabla _1}t}} \times \frac{{\partial \varphi ({t_4},{s_2})}}{{{\diamondsuit _2}s}},\;\;{{\vec N}_4} = \frac{{\partial \varphi ({t_3},{s_4})}}{{{\diamondsuit _1}t}} \times \frac{{\partial \varphi ({t_3},{s_4})}}{{{\nabla _2}s}} \hfill \\
{{\vec N}_5} = \frac{{\partial \varphi ({t_2},{s_1})}}{{{\diamondsuit _1}t}} \times \frac{{\partial \varphi ({t_2},{s_1})}}{{{\Delta _2}s}}. \hfill \\
\end{gathered}
Fig. 1
A finite surface with the patch φ on 𝕋1 × 𝕋2.
Method
3D point clouds represent a discrete representation of the surfaces, namely discrete manifolds, present in the real world. If this sample is obtained from range sensors such as 3D scanners, noise is expected in the sample. Because of this type of noise, clear information about surface orientation and curvature can be lost. The normal vector estimate tries to reconstruct this information by creating a set of vectors perpendicular to the tangential plane of each surface [30, 31, 32]. In particular, the resulting normal vector is a reasonable procedure for integrating each data item into a feature space corresponding to a point of the point cloud. In this section, we present a method by using the concept of symmetric differential for predicting normal vectors on a discrete representation of surfaces existing in the real world.
Our approach is based on considering the points of point clouds as the points on a surface patch parameterized on two isolated time scales. However, the direct implementation of this approach has two major drawbacks. First drawback emerges when the points on discrete manifold are not aligned on grid-like structure. In this case it becomes impossible to determine the forward or backward jumps of the coordinate variable, therefore the dynamic differentiation even in symmetric sense is not well-defined. To cope with this drawback, we give the following proposition:
Proposition 4
Let M ⊂ ℝ3be the set of non-uniform points and 𝒮 be a surface with an atlas on 𝕋1 × 𝕋2. Then, M can be given a symmetric differentiable structure in such way that the inclusion i : M → 𝒮 is an embedding. Proof. Let F : ℝ2 → M and 𝒮 be a surface with an atlas on 𝕋1 × 𝕋2with the coordinate chart (x, y). Let us first fix x ∈ M. Now choose the homeomorphism{\xi _x}:F_x^{ - 1} \to \mathcal{S}with x ∈ F−1 ∩ (𝕋1 × 𝕋2). Since the symmetric covariant derivative ⋄yξx is injective, we can choose a bijection γ : {1, 2, 3} → {1, 2, 3} such that the rows γ(1), γ(2), γ(3) of ⋄yξx are linearly independent. Define π : 𝒮 → 𝒮′ by π(x, y, z) → (x′, y′, z′). Then, the ⋄y(π ○ ξx) is an isomorphism. Hence there are open sets in the time scale topology A ⊆ F−1(M) and B ⊆ π(𝒮) and the map ηx : B → A is the inverse of π ○ ξx.
Define 𝒜 = {φx = ηx ○ π | x ∈ M}. For x1 ≠ x2, we have{\varphi _{{x_2}}} \circ \varphi _{{x_2}}^{ - 1} = {\varphi _{{x_2}}} \circ {\xi _{{x_1}}}. Therefore, 𝒜 is a symmetric differentiable atlas making M into a symmetric differentiable surface. The inclusion i : M → 𝒮 is a homeomorphism, and for any patch we haveId \circ {\mathbf{i} \circ \eta _x^{ - 1}, which has injective symmetric derivative.
The second drawback is subject to determining the parameterizations of the surface patches. When the unorganized points are the subject, there are several ways to interpolate them [35, 36, 37]. In this study, we use the quadratic surface fitting.
A quadratic surface passing through origin is
[z(x,y) = {A_1}x + {A_2}y + {A_3}{x^2} + {A_4}xy + {A_5}{x^2}y + {A_6}x{y^2} + {A_7}{y^2} + {A_8}{x^2}{y^2}.
It can be seen that the surface with the Equation 2 requires eight other given points (xi, yi, zi), i = 1,...,8, and is expressed by the system
[\left( {\begin{array}{*{20}{c}}
{{x_1}}&{{y_1}}&{x_1^2}&{{x_1}{y_1}}&{x_1^2{y_1}}&{{x_1}y_1^2}&{y_1^2}&{x_1^2y_1^2} \\
{{x_2}}&{{y_2}}&{x_2^2}&{{x_2}{y_2}}&{x_2^2{y_2}}&{{x_2}y_1^2}&{y_2^2}&{x_2^2y_2^2} \\
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\
{{x_8}}&{{y_8}}&{x_8^2}&{{x_8}{y_8}}&{x_8^2{y_8}}&{{x_8}y_8^2}&{y_8^2}&{x_8^2y_8^2} \\
{}&{}&{}&{}&{}&{}&{}&{}
\end{array}} \right)\left( {\begin{array}{*{20}{c}}
{{A_1}} \\
{{A_2}} \\
\vdots \\
{{A_8}} \\
{}
\end{array}} \right) = \left( {\begin{array}{*{20}{c}}
{{z_1}} \\
{{z_2}} \\
\vdots \\
{{z_8}} \\
{}
\end{array}} \right).
The accuracy of the fitting method is directly depending conditioning of the matrix in Equation 3.
Let us assume that the patch in Equation 2 is expressed in vector form as
[R(x,y) = \left( {\begin{array}{*{20}{c}}
x \\
y \\
{z(x,y)} \\
{}
\end{array}} \right).
From Proposition 1, we may conclude that the eight-point neighborhood of the R(0, 0) is a ⋄-smooth surface. Now, let us consider this neighborhood as in
Figure 2
.
Fig. 2
Eight neighbouring non-uniform data points of O = R(0, 0).
Therefore, accuracy of our method is order two with O(\max \{ \sigma _1^2(x),\rho _1^2(x),\sigma _2^2(y),\rho _2^2(y)\} ). If 𝕋1 ×𝕋2 ≡ hℤ×hℤ or 𝕋1 × 𝕋2 ≡ ℝ × hℤ or 𝕋1 × 𝕋2 ≡ hℤ × ℝ, then the accuracy becomes of order two with O(h2).
Given an non-uniform set of points M in ℝ3, it is possible to determine the ⋄-smooth surface 𝒮 containing M by parametrization of F : ℝ2 → M. We can say from Proposition 4 that the symmetrical differential structure of 𝒮 is also in M by the embedding i : M → 𝒮. With the parametrization of M, the geometric structure of 𝒮, that is, the vertices of the non-regular rectangular grid structure, which contains the M, can be determined as S be the cardinally smallest ⋄-smooth surface due to reduce computational costs.
A quadratic surface patch to model an entire surface is not convenient but it is good for modeling neighborhood around a point. If an entire surface needs to be modelled, then we may implement our method to cubic splines [33,34]. However this is totally subject to another study. To determine neighborhood of the data point in M for fitting quadratic surface, we use the closeness relation of 3D data points. That is, we obtain an appropriate graph G = (V, E), where V is the set of points and E is the set of edges with E = {e = (vi, vj) | vi, vj ∈ V}.
In our study, the procedure in
Table 1
is applied to achieve the bundle S = ∪𝒮. The computational complexity of the procedure is directly dependent on the size of M and the size of neighborhood of i-th point. Since quadratic fitting needs only eight points, this complexity can be reduced to 𝒪(|M|
).
The procedure to obtain the bundle of ⋄-smooth surfaces on M.
Input:
M
Build:
G=(V,E), V=M
for
i=1
to
|M|
do
N(i) = {wi: wi is adjacent to i in G} ∪ i
Πl : l−th coordinate function
Fit
quadratic z(x, y) in N(i)
for
j=1
to
|N(i)|
do
for
k=1
to |
N(i)
do
𝒮 ← {Π1(wj), Π2(wk), z(wj, wk)
end for
end for
end for
Output:
Bundle S = ∪𝒮
Results
In computer graphics and engineering analyses, the triangular meshing of surfaces plays a key role. A surface meshing can be achieved by mapping meshes in parameter space onto surfaces where the meshes can be triangular or rectangular grids [38, 39]. A good looking mesh in the parameter space may have a problematic image on surface under these mappings since the transformation of geometry from the parameter space to the surface may be twisted along some directions. In many engineering applications including Finite Element analysis the triangular mesh is the most popular choice to get over this problem.
The de facto method to obtain triangular surface meshes is the Delaunay triangulation. Traditionally, the Delaunay triangulation is a cell complex that subdivides the convex hull of the discrete points in ℝ3 in which every circum-circle of a triangle is an empty circle [40]. The algorithmic complexity of the Delaunay triangulation of M ⊂ ℝ3 is 𝒪(|M|2). However, if the points in M are well distributed on a smooth surface, then the Delaunay triangulation has the reduced complexity 𝒪(|M|log|M|
) [41].
Let M ⊂ ℝ3 be the set of discrete points and the Delaunay triangulation of D(M) composed of the points P. For a local triangular mesh of a surface interpolating M with K triangles, the normal vector \vec n at P ∈ M is equal to
[{\vec N_D} = \frac{{\sum\limits_{i = 1}^K {w_i}{{\vec n}_i}}}{{\sum\limits_{i = 1}^K {w_i}}},
where {\vec n_i} and wi are the normal vector and weight of the i-th triangle PiPPi+1, respectively. The weight wi of the i-th triangle can be computed as {w_i} = \frac{{|\vec P{P_i} \times \vec P{P_{i + 1}}|}}{2} [31].
In this section, to make the comparative analysis, we give the computational results of the normal fields of our method and Delaunay triangulation. To see the comparison, we use the two parametric surfaces and measure the vector errors with infinity norm. The first surface has the parametrization as {\varphi _1}(t,s) = (t{s^2},{t^2}s,1 - \sqrt {{t^2} + {s^2}} ) for t, s ∈ [−1, 1], and the second surface has the parametrization as φ2(t, s) = ((1,16s)coss(1 + cost), −1.16s sins(1 + cost), −2(1, 16s)(1 + sint)) for t ∈ [0, 2π] and s ∈ [−15, 6]. The smooth surfaces and points of M sampled on them are presented in
Figure 3
. The Delaunay triangulations of M are also presented in
Figure 4
.
Fig. 3
The surfaces with the parameterizations φ1(t, s) (on the left) and φ2(t, s) (on the right), and the points sampled on them.
Fig. 4
The Delaunay triangulations of the point set M sampled on φ1(t, s) and φ2(t, s).
The graphs derived from the Delaunay triangulation are called the Delaunay graph of M. The procedure presented in
Table 1
initially starts with a graph representation of M. Hence, to see the effectiveness of our method, we use the Delaunay graph of M as G = (V, E), where M is chosen as well distributed to reduce time complexity. Besides, the quadratic surface fit requires eight other given points. Therefore, if the 1-neighborhood N(i) does not composed of nine points, then we extend the neighborhood to k-neighborhood in which composed of optimally many points.
In order to measure the error in normal vectors, we need to measure the size or norm of the vectors ||\vec N - {\vec N_D}{||_\infty } and ||\vec N - {\vec N_{TS}}{||_\infty } at P ∈ M, where \vec N is the unit normal vector of the parameterized surfaces, {\vec N_D} is the unit normal vector obtained by the Delaunay triangulation, and {\vec N_{TS}} is the unit normal vector obtained by our method. The measured errors are presented in Figures 5–6.
Fig. 5
The error in unit normal vectors for φ1(t, s).
Fig. 6
The error in unit normal vectors for φ2(t, s).
The error measurements show us that the present method based on symmetric dynamic derivatives yields better approximations for certain points of both φ1(t, s) and φ2(t, s). The numbers of sampled points on φ1(t, s) and φ2(t, s) are 2571 and 2295, respectively. The lesser error are obtained at 962 many points of φ1(t, s) and 113 many points of φ2(t, s) by using our method. Besides, the \min \{ ||\vec N - {\vec N_{TS}}{||_\infty }\} = 9.24888 \times {10^{ - 5}} and \min \{ ||\vec N - {\vec N_D}{||_\infty }\} = 0.5777 \times {10^{ - 1}} for φ1(t, s), and the \min \{ ||\vec N - {\vec N_{TS}}{||_\infty }\} = 1.19273 \times {10^{ - 2}} and \min \{ ||\vec N - {\vec N_D}{||_\infty }\} = 3.38129 \times {10^{ - 1}} for φ2(t, s). The points where our method yields better approximation than the {\vec N_D} to unit normal vectors is presented in
Figure 7
.
Fig. 7
The points where the unit normal is approximated better for φ1(t, s) and φ2(t, s).
Conclusions
The mimetic discretization of continuous operators yields us efficient way to model continuous theory underlying the physical problem. For the mimetic discretization process the theory of time scale calculus emerge as an efficient mathematical theory. If the nature of the problem involves the forward or backward discretization, then the delta or nabla dynamic differentiation may dominate the modelling and solutions. However, in geometric point of view, the symmetric dynamic differentiation mimics the discrete counterpart of the geometric modelling, since it ensures that the protected geometric properties such as curvatures are maximized.
In this study, we consider a surface on time scales as the vertex set of non-regular rectangular grids. Then, we determine the normal vector fields of surfaces parameterized by the tensor product of two time scales by using symmetric dynamic differentiation. If we have such a closed subset set of ℝ2 as the parameter domain of a surface, then the most basic mapping φ(t, s) = (t, s, f (t, s)) yields us a ⋄-smooth surface. Besides, if a surface patch has a finite geometry, then the symmetric differential acts as forward or backward dynamic derivatives on boundaries.
In real world applications, a set of discrete points in ℝ3 does not involve a regular geometric structure. In this paper, we also present an algorithmic procedure to approximate normal fields of such sets which are sampled on a smooth surface. Our procedure first start with the geometric closeness relation of discrete points. This relation is expressed as a finite graph. Then, by using the neighborhood of points in the graph, we fit a quadratic surface to approximate the parameter of underlying smooth surface. Afterwards, we assign a non-regular rectangular grid like structure to this parametrization and consider the embedding as a surface on time scales. We also show that such immersion of discrete points to surface on time scales is an embedding. Therefore, these discrete points also have the symmetric dynamic differential structure of a surface on time scales. Subsequently, the normal vector fields are determined by symmetric dynamic derivatives.
