Geometric conditions for injectivity of 3D Bézier volumes

1.   Introduction

In geometric modeling, 3D Bézier volumes are important and frequently used tools. They are often used in video tracking ^[1,2,3], which is one of the fundamental issues in computer vision. Video tracking can be applied for target recognition and face recognition, which have broad application prospects in social security and aerospace. Capturing real motion from video sequences is a powerful approach in the automatic construction of a facial deformation model. Three-dimensional Bézier volumes are effective tools for the synthesis and analysis of facial movements, as they are capable of animating geometric facial models of different shapes and structures ^[4]. A shape is $k$-dimensional if there is a continuous one-to-one mapping of the $k$-dimensional cube (ball) on this shape ^[5]. A shape can exist in an $n$-dimensional space if $k \leq n$. Mapping functions are maps for which the definition domain is the same as the parameter domain. Three-dimensional Bézier volumes are mapping functions in which both domains have three dimensions.

Toric surfaces were proposed by Krasauskas ^[6] in 2002. These are polygon surfaces, the essence of which is the projection of the toric variety from higher-dimensional space to low-dimensional affine space. The parameter domain is the convex polytope, which defines the toric ideal. The shape of a toric surface can be modified by its control points and weights. The basis functions of the toric surface are defined by the positive lattice points and the boundary functions of the convex polytope, which are also the generation of the Bernstein basis. The well-known 3D Bézier volumes are a special class of Bézier polytopes proposed by Krasauskas ^[6].

Many applications in 3D games, model-based video coding, and human–computer interfaces demand realistic human facial animation. A crucial issue in facial animation is deformation modeling. This concerns a feasible approach for imbedding a facial model in a 3D volume, and then completing the deformation by volume deformation. Tao and Huang ^[4] proposed a 3D Bézier volume deformation (BVD) model for both synthesis and analysis of facial movements. In their work, the facial model was embedded into sixteen 3D Bézier volumes. The deformation of their facial model was completed by the shape morphing of these 3D Bézier volumes. Their model is a kind of piecewise 3D Bézier volume model. In Figure 1, we show two solid models structured by 3D Bézier volumes. Figure 1(a) shows a human hand model defined by a 3D Bézier volume with degree $11\times 11\times 11$. In Figure 1(b), we show a human foot model defined by a 3D Bézier volume with $1131$ control points. These two models are formed by a single 3D Bézier volume. As an effective tool in deformation ^[4], BVDs reduce the number of deformation volumes and the degrees of freedom in the control points, which is preferable in motion tracking. Moreover, irregular 3D manifolds can be formed. Note that a crucial issue is that the deformation volume is non-self-intersecting. That is, 3D Bézier volumes should be non-self-intersecting. In this paper, we consider the injectivity of 3D Bézier volumes. In Figure 2, we show two 3D Bézier volumes. The Bézier volume in Figure 2(a) has no self-intersection with any choice of positive weights. The non-self-intersecting Bézier volume in Figure 2(b) has self-intersections with certain choices of positive weights. Therefore, the question is: when does a 3D Bézier volume have no self-intersections for any choice of positive weights? In this paper, we attempt to answer this question.

The concept of injectivity comes from the chemical reaction networks developed by Müller et al. ^[7]. In chemical engineering, if the polynomial map in a dynamical system is injective, then multi-stationarity cannot occur. In geometry, injectivity implies that curves, surfaces, or volumes have no self-intersection. Hoffmann ^[8] mentioned that the intersection problem is one of the most fundamental issues in the integration of geometry and solid modeling systems. Xu et al. ^[9] noted that finding a good placement of the inner control points inside the computational domain is a key issue. A basic requirement of the resulting volume parameterization for iso-geometric analysis is that there are no self-intersections, so that it is an injective map from the parameterization domain to the computational domain. Moreover, the self-intersection problem is a major problem in computer-aided design ^[10,11]. Many researchers have studied the estimation and computation of self-intersections. Patrikalakis and Prakash ^[12] used an adaptive subdivision algorithm for Bézier surfaces and successfully solved actual intersection problems with diverse features. Motivated by a query from Sabin about constructing an injective transfinite interpolant for use in changing a parametrization, Goodman and Unsworth ^[13] derived conditions on the Bézier points of a polynomial mapping from $R^2$ to $R^2$. When using surfaces to represent a solid volume, it is necessary to dispose of the self-intersection problem. A divide-and-conquer algorithm for finding the self-intersection curves of surfaces has been developed ^[14], in which self-intersection is defined as a global intrinsic property of a surface. This led to a necessary condition for surface self-intersection that can be computed from the normal and tangent bounding cones of the surface. Galligo and Pavone ^[10] presented two different contributions towards the determination of the self-intersection locus of a Bézier bi-cubic surface patch. There are a number of articles considering methods and algorithms for the intersection of two patches (see, e.g., ^{[15,16,17,18]}).

Our motivation is different from the above. We consider conditions on the control points for 3D Bézier volumes that are equivalent to there being no self-intersection for any choice of positive weights. When the number of control points is small, the condition is geometrically intuitive. Craciun et al. ^[19] used ideas from geometry and dynamical systems to explain the influence of control points on the shape of Bézier curves and patches. They proved an injective condition for a certain map and adapted this for toric Bézier function ^[20]. They also derived the sufficient and necessary injective condition for toric functions in $R^d$. Their result is a geometric condition on the control points such that the corresponding toric patches are injective for any choice of positive weights. However, there is a minor flaw in that this only guarantees injectivity in the interior of a patch. To refine the result in ^[20], the injective condition of 2D toric Bézier patches has been proposed by Sottlie and Zhu ^[21]. The sufficient and necessary conditions for injective 2D and 3D Bézier curves/surfaces have been proposed by Zhu and Zhao ^[22,23], and the injectivity conditions for toric volumes have been established by Yu et al. ^[24].

The remainder of this paper is organized as follows. In Section 2, we introduce 3D Bézier volumes ^[6] and some properties related to our paper. In Section 3, we illustrate our main result, which implies the injectivity of 3D Bézier volumes. An algorithm for checking the injectivity of 3D Bézier volumes is also proposed. Some explicit examples are presented in Section 4.

2.   Three-dimensional Bézier volumes

The definition of 3D Bézier volumes can be found in a number of related references. In this section, we illustrate the definition of 3D Bézier volumes given by Krasauskas ^[6]. Toric surface patches were proposed by Krasauskas ^[6], who derived them from toric varieties and toric ideals. Rational Bézier forms are special classes of these toric forms; for example, 3D Bézier volumes are a kind of 3D situation.

Consider a cube $\Box_{m, n, l}\subset R^3$ whose vertices have integer coordinates. $\mathcal{A} = \Box_{m, n, l} \cap Z^3$ is called a lattice points set. $\Box_{m, n, l}$ is a lattice polytope $I_m\times I_n \times I_l$. It is also the convex hull of $\mathcal{A}$. Let $h_i (t_1, t_2, t_3) = 0, (t_1, t_2, t_3)\in R^3, i = 1, \cdots, 6$ be the facets of $\Box_{m, n, l}$. Then, $\Box_{m, n, l}$ can be defined by $h_i (t_1, t_2, t_3)\geq0, i = 1, \cdots, 6$. According to Krasauskas ^[6], the toric Bernstein basis function can be defined as $\beta(t_1, t_2, t_3) = c_{i, j, k}h_1(t_1, t_2, t_3)^{h_1(i, j, k)}\cdots h_6(t_1, t_2, t_3)^{h_6(i, j, k)}, (i, j, k)\in\mathcal{A}$, where $c_{i, j, k}$ is a positive coefficient. In this paper, $c_{i, j, k} = \frac{\binom{m}{i}\binom{n}{j}\binom{l}{k}}{m^m n^n l^l}$. We illustrate the definition of 3D Bézier volumes in the following form.

Definition 1. ^[6] A 3D Bézier volume associated with a lattice points set $\mathcal{A}_{m, n, l} = \{(i, j, k)\in Z^3|0 \leq i\leq m, 0 \leq j\leq n, 0 \leq k\leq l, \}$ is a rational map $\mathcal{B}_{\mathcal{A}_{m, n, l}, \mathcal{P}, \omega}: \Box_{m, n, l}\rightarrow R^3$.

where $\beta_{i, j, k}(t_1, t_2, t_3) = \frac{\binom{m}{i}\binom{n}{j}\binom{l}{k}}{m^m n^n l^l}t_1^i(m-t_1)^{(m-i)}t_2^j(n-t_2)^{n-j}t_3^k (l-t_3)^{(l-k)}$, $(i, j, k)\in \mathcal{A}_{m, n, l}$.

Here, $\mathcal{P} = \{\mathit{\boldsymbol{p}}_{i, j, k}\in R^3|i, j, k\in Z, 0\leq i\leq m, 0\leq j\leq n, 0\leq k\leq l\}$ is called the control points set, and $\beta_{i, j, k}(t_1, t_2, t_3))$ is the toric Bernstein basis function. Let $\tau_1 = \frac{t_1}{m}, \tau_2 = \frac{t_2}{n}, \tau_3 = \frac{t_3}{l}$. Then, $\mathcal{B}_{\mathcal{A}_{m, n, l}, \mathcal{P}, \omega}$ is called a 3D Bézier volume.

If we do not fix all the coefficients $c_{i, j, k}$ of the basis functions $\beta(t_1, t_2, t_3)$, they can vary from case to case. It is called Bézier polytope, a straightforward generalization of toric surfaces. Bézier volumes are particular cases with the special coefficients $c_{i, j, k} = \frac{\binom{m}{i}\binom{n}{j}\binom{l}{k}}{m^m n^n l^l}$ ^[6]. Definition 1 is equivalent to the traditional definition introduced in much of the literature ^[25,26,27]. When the lattice polytope is $\Box_{m, n, l}$, the toric surface will be a 3D Bézier volume. Therefore, 3D Bézier volumes have the same properties as toric surfaces. We will illustrate some of the properties as follows (see ^[25]):

$(1)$Affine invariance.

$(2)$Convex hull property. The 3D Bézier volume $\mathcal{B}_{\mathcal{A}_{m, n, l}, \mathcal{P}, \omega}$ is a subset of $R^3$ contained in the convex hull of its control points $\mathit{\boldsymbol{p}}_{i, j, k}\in \mathcal{P}$.

$(3)$Boundary property. The boundary of the 3D Bézier volume $\mathcal{B}_{\mathcal{A}_{m, n, l}, \mathcal{P}, \omega}$ consists of rational Bézier surfaces $\mathcal{B}_{\mathcal{A}_{m, n, l}|_{\delta_i}, \mathcal{P}|_{\delta_i}, \omega|_{\delta_i}}|_{\delta_i}$, i = 1, ..., 6, defined by control points $\mathcal{P}|_{\delta_i}$ and weights $\omega|_{\delta_i}$ indexed by lattice points $\delta_i$; $\delta_i, i = 1, \cdots, 6$, are the facets of $\Box_{m, n, l}\subset R^3$.

Example 1. Let the lattice polytope be $\Box_{1, 2, 1}\subset R^3$. First, suppose that the control points set is the same as the lattice points set. This 3D Bézier volume is shown in Figure 3(a), and it is obviously injective. Second, we move one of the corner control points [see Figure 3(b)]. The resulting 3D Bézier volume is no longer injective [see Figure 3(c)].

Example 1 implies that the location of each control point has an important impact on the injectivity of the 3D Bézier volume.

Example 2. Let $\Box_{3\times 3\times 3}\subset R^3$. The lattice points set $\mathcal{A}_{3, 3, 3} = \Box_{3\times 3\times 3}\cap Z^3$ is shown in Figure 4(a). Suppose that all the weights are equal to $1$. With the given control points set $\mathcal{P}$ as shown in Figure 4(b), the 3D Bézier volume $\mathcal{B}_{\mathcal{A}_{3, 3, 3}, \omega, \mathcal{P}}$ defined by $\mathcal{A}_{3, 3, 3}$ and $\mathcal{P}$ is shown in Figure 4(c).

Example 2 implies that a 3D Bézier volume lies in the convex hull of its control points. This leads us to ask, is a 3D Bézier volume non-self-intersecting if its control nets have no self-intersections? Our answer is No! In the following section, we will prove some conditions that guarantee the injectivity of 3D Bézier volumes.

3.   Injectivity of 3D Bézier volumes

Three-dimensional Bézier volumes are useful tools in solid modeling, such as for human face models. When users manipulate the expression or visual speech level of the face model, self-intersection is an undesirable result. In other words, the injectivity of 3D Bézier volumes is a precondition for solid modeling. Therefore, checking the injectivity of a given Bézier volume is an important problem that needs to be carefully considered.

In 2010, Craciun et al. ^[20] proposed a sufficient and necessary condition that guarantees the injectivity of toric surfaces. In $R^3$, an order list $(i_1, j_1, k_1)$, $(i_2, j_2, k_2)$, $(i_3, j_3, k_3)$, $(i_4, j_4, k_4)$ of affinely independent points^[28] determines a positive orientation through the basis

Definition 2. The control points $\mathcal{P}$ and the lattice points $\mathcal{A}$ are compatible if:

● There exist affinely independent lattice points $(i_1, j_1, k_1)$, $(i_2, j_2, k_2)$, $(i_3, j_3, k_3)$, $(i_4, j_4, k_4)\in \mathcal{A}_{m, n, l}$ such that $\mathit{\boldsymbol{p}}_{i_1, j_1, k_1}, \mathit{\boldsymbol{p}}_{i_2, j_2, k_2}, \mathit{\boldsymbol{p}}_{i_3, j_3, k_3}, \mathit{\boldsymbol{p}}_{i_4, j_4, k_4}$ is also affinely independent;

● For any affinely independent points $(i'_1, j'_1, k'_1$), $(i'_2, j'_2, k'_2)$, $(i'_3, j'_3, k'_3)$, $(i'_4, j'_4, k'_4)\in \mathcal{A}_{m, n, l}$ with the same orientation as $(i_1, j_1, k_1), (i_2, j_2, k_2), (i_3, j_3, k_3), (i_4, j_4, k_4)$, if $\mathit{\boldsymbol{p}}_{i'_0, j'_0, k'_0}, \mathit{\boldsymbol{p}}_{i'_1, j'_1, k'_1}, \mathit{\boldsymbol{p}}_{i'_2, j'_2, k'_2}, \mathit{\boldsymbol{p}}_{i'_3, j'_3, k'_3}$ is also affinely independent, then it has the same orientation as $\mathit{\boldsymbol{p}}_{i_0, j_0, k_0}, \mathit{\boldsymbol{p}}_{i_1, j_1, k_1}, \mathit{\boldsymbol{p}}_{i_2, j_2, k_2}, \mathit{\boldsymbol{p}}_{i_3, j_3, k_3}$.

Theorem 1 (Craciun et al., 2010). The map $\mathcal{B}_{\mathcal{A}_{m, n, l}, \mathcal{P}, \omega}$ is injective if and only if $\mathcal{P}$ and $\mathcal{A}$ are compatible.

We can find an example that explains the compatibility of point sets and shows that Theorem 1 does not hold for some control points $\mathcal{P}$ that are compatible with $\mathcal{A}$.

Example 3. In this example, the lattice points set is as shown in Figure 5(a). Three different control points set are shown in Figure 5(b), Figure 5(c), and Figure 5(d). It is easy to see that the control points in Figure 5(b) define the same orientation as the lattice points, while the control points in Figure 5(c) define the opposite orientation to the lattice points. The control points set in Figure 5(b) and 5(c) are both compatible. However, the control points set in Figure 5(d) is not compatible.

If we set $p_{i_3, j_3, k_3} = p_{i_5, j_5, k_5}$, then $\mathcal{P}$ and $\mathcal{A}$ are still compatible. According to the interpolation property of toric surfaces, this is not injective. Similarly, any control points indexed by the corner point of $\mathcal{A}$ coincide with each other, and the toric surface is not injective. Thus, Theorem 1 holds in the interior of the toric surface. Therefore, it also holds in the interior of 3D Bézier volumes. For 3D Bézier volumes, the correct statement of Theorem 1 is Theorem 2.

Theorem 2. The map $\mathcal{B}^{\circ}_{\mathcal{A}_{m, n, l}, \mathcal{P}, \omega}: \Box_{m, n, l} \rightarrow R^3$ is injective for all positive weights if and only if $\mathcal{P}$ and $\mathcal{A}$ are compatible.

To prove the injectivity of 3D Bézier volumes, we need to add conditions on their facets. Each boundary surface of a 3D Bézier volume is a tensor product Bézier surface. We add some geometric conditions on the facets of 3D Bézier volumes to complete the injectivity conditions.

Definition 3. The control points set $\mathcal{P}|_{\delta_i}, (i = 1, 2, \cdots, 6)$ is well-posed if it satisfies the following conditions:

● All the points are in a general position;

● For each subset $\widetilde{\mathcal{A}}_{m, n, l}|_{\delta_i}$ of $\mathcal{A}_{m, n, l}|_{\delta_i}$, the corresponding control net $\widetilde{N}|_{\delta_i}$ connected by the neighboring control points indexed by $\widetilde{\mathcal{A}}_{m, n, l}|_{\delta_i}$ has no self-intersection;

● For each subset $\widetilde{\mathcal{A}}_{m, n, l}|_{\delta_i}$ of $\mathcal{A}_{m, n, l}|_{\delta_i}$, the intersection of some control point $\mathit{\boldsymbol{p}}_{i, j, k}$ or a line segment composed of two neighboring control points $\overline{\mathit{\boldsymbol{p}}_{i, j, k}\mathit{\boldsymbol{p}}_{\bar{i}, \bar{j}, \bar{k}}}$ of $\tilde{\mathcal{P}}|_{\delta_i}$ and the interior of a triangle or a tetrahedron formed by the control points of $\{\mathit{\boldsymbol{p}}_{i_0, j_0, k_0}$, $\mathit{\boldsymbol{p}}_{i_1, j_1, k_1}$, $\mathit{\boldsymbol{p}}_{i_2, j_2, k_2}, \mathit{\boldsymbol{p}}_{i_3, j_3, k_3}\vert$ $i > min\{i_0, i_1, i_2, i_3\}$ or $i > max\{i_0, i_1, i_2, i_3\}$, $j < min\{j_0, j_1, j_2, j_3\}$ or $j > max\{j_0, j_1, j_2, j_3\}\}$ and $k < min\{k_0, k_1, k_2, k_3\}$ or $k > max\{k_0, k_1, k_2, k_3\}\}$ is empty.

The second condition in Definition 3 means that control nets including piecewise bilinear patches connected by neighboring four control points have no self-intersection.

Theorem 3. The map $\mathcal{B}_{\mathcal{A}_{m, n, l}, \mathcal{P}|_{\delta_i}, \omega}: \Box_{m, n, l} \rightarrow R^3$ is injective for all positive weights if and only if $\mathcal{P}|_{\delta_i}$ is well-posed.

We omit the details of the proof of Theorem 3; they can be found in ^[23].

Definition 4. The control points set $\mathcal{P}$ is well-posed if $\mathcal{P}$ and $\mathcal{A}$ are compatible and the boundary control points sets $\mathcal{P}|_{\delta_i} (i = 1, 2, \cdots, 6)$ are well-posed.

Theorem 4. Let $\mathcal{A}_{m, n, l}$ be lattice points, $\mathcal{P}$ be a control points set, and $\omega > 0$ be a weight. The map $\mathcal{B}_{\mathcal{A}_{m, n, l}, \mathcal{P}, \omega}: {\Box_{m, n, l}} \mapsto R^3$ is injective if and only if its control points set $\mathcal{P}$ is well-posed.

Proof of Theorem 4. We use contradiction to complete the proof. First, suppose that $\mathcal{P}$ is well-posed and the map $\mathcal{B}_{\mathcal{A}_{m, n, l}, \mathcal{P}, \omega}$ is not injective. Then, there exist two points $(t_1, t_2, t_3), (t'_1, t'_2, t'_3)$ $\in \mathcal{A}_{m, n, l}$ such that $\mathcal{B}_{\mathcal{A}_{m, n, l}, \mathcal{P}, \omega}(t_1, t_2, t_3)$ $= \mathcal{B}_{\mathcal{A}_{m, n, l}, \mathcal{P}, \omega}(t'_1, t'_2, t'_3)$. By Definition $4$, the control points set $\mathcal{P}$ and the lattice points $\mathcal{A}_{m, n, l}$ are compatible and $\mathcal{P}|_{\delta_i}, i = 1, 2, \cdots 6$, are well-posed. It is easy to observe that there are three situations for the position of $(t_1, t_2, t_3)$ and $(t'_1, t'_2, t'_3)$.

a) If $(t_1, t_2, t_3), (t'_1, t'_2, t'_3)\in\Box_{m, n, l}^{\circ}$, the assumption means that $\mathcal{B}_{\mathcal{A}_{m, n, l}, \mathcal{P}, \omega}(t_1, t_2, t_3)$ $= \mathcal{B}_{\mathcal{A}_{m, n, l}, \mathcal{P}, \omega}(t'_1, t'_2, t'_3)$ is tenable in the interior of $\mathcal{B}_{\mathcal{A}_{m, n, l}, \mathcal{P}, \omega}$. However, the control points set $\mathcal{P}$ and the lattice points $\mathcal{A}_{m, n, l}$ are also compatible. Therefore, from Theorem 2, the map $\mathcal{B}_{\mathcal{A}_{m, n, l}, \mathcal{P}, \omega}: {\Box^\circ_{m, n, l}} \mapsto R^3$ is injective. This contradicts the hypothesis.

b) If $(t_1, t_2, t_3), (t'_1, t'_2, t'_3)\in\delta_i$, $\delta_i, i = 1, 2, \cdots, 6$, are the facets of $\Box_{m, n, l}$. Then, the assumption means that $\mathcal{B}_{\mathcal{A}_{m, n, l}, \mathcal{P}|_{\delta_i}, \omega}(t_1, t_2, t_3)$ $= \mathcal{B}_{\mathcal{A}_{m, n, l}, \mathcal{P}|_{\delta_i}, \omega}(t'_1, t'_2, t'_3)$ is tenable on the boundary of $\mathcal{B}_{\mathcal{A}_{m, n, l}, \mathcal{P}, \omega}$. However, $\mathcal{P}|_{\delta_i}, i = 1, 2, \cdots 6$, are well-posed. Therefore, from Theorem 3, the map $\mathcal{B}_{\mathcal{A}_{m, n, l}, \mathcal{P}|_{\delta_i}, \omega}$ is injective. This contradicts the hypothesis.

c) Only one of $(t_1, t_2, t_3)$ and $(t'_1, t'_2, t'_3)$ is a point of $\Box_{m, n, l}^{\circ}$. Without loss of generality, we suppose that $(t_1, t_2, t_3)\in \Box_{m, n, l}^{\circ}$. Let $V \subset \Box_{m, n, l}$ be a neighborhood of $(t_1, t_2, t_3)$, and $(t'_1, t'_2, t'_3)\notin \overline{V}$, where $\overline{V}$ is the closure of $V$. Thus, the image of $V$ under the map $\mathcal{B}_{\mathcal{A}_{m, n, l}, \mathcal{P}, \omega}$, $\mathcal{B}_{\mathcal{A}_{m, n, l}, \mathcal{P}, \omega}(V)$, is a 3D open sphere satisfying $\mathcal{B}_{\mathcal{A}_{m, n, l}, \mathcal{P}, \omega}(t_1, t_2, t_3)$ $= \mathcal{B}_{\mathcal{A}_{m, n, l}, \mathcal{P}, \omega}(t'_1, t'_2, t'_3)$ $\subset \mathcal{B}_{\mathcal{A}_{m, n, l}, \mathcal{P}, \omega}(V)$. However, if we suppose that $U\subset \Box_{m, n, l}$ is a 3D open sphere such that $(t'_1, t'_2, t'_3)\in U$, then $U\subset \mathcal{B}_{\mathcal{A}_{m, n, l}, \mathcal{P}, \omega}^{-1}(V)\backslash V$. Thus, the points in $U\cap \Box_{m, n, l}^{\circ}$ satisfy $\mathcal{B}_{\mathcal{A}_{m, n, l}, \mathcal{P}, \omega}(U\cap \Box^\circ_{m, n, l})\subset \mathcal{B}_{\mathcal{A}_{m, n, l}, \mathcal{P}, \omega}(V)$. This implies that $\mathcal{B}_{\mathcal{A}_{m, n, l}, \mathcal{P}, \omega}: {\Box^\circ_{m, n, l}} \mapsto R^3$ is not injective, which contradicts Theorem 2 because $\mathcal{P}$ and the lattice points $\mathcal{A}_{m, n, l}$ are compatible.

Therefore, the assumption is incorrect, and so the proof of Theorem 4 is complete.

From the conclusion of Theorem 4, we obtain a method of checking the injectivity of 3D Bézier volumes. We illustrate the main idea of the method in Algorithm 1. This algorithm is a direct application of Theorem 4. The complexity of Algorithm 1 is about $O(n^4)$, where $n = size(\mathcal{A}_{m, n, l})$. Although the algorithm has a high computational cost, it is a direct approach. Note that the algorithm terminates quickly in the case of non-well-posed control points. An improved algorithm for checking compatible control points in 2D was recently completed by Yu et al. ^[29]; an improved algorithm for checking the injectivity of 3D Bézier volumes was left as a topic for future work.

4.   Examples

Example 4. (Continued from Example 2) By Definition 4, we know that the control points set $\mathcal{P}$ (as shown in Figure 4(b)) is compatible. By Theorem 4, the 3D Bézier volume $\mathcal{B}_{\mathcal{A}_{3, 3, 3}, \omega, \mathcal{P}}$ is injective. We show some layers of the injective 3D Bézier volume $\mathcal{B}_{\mathcal{A}_{3, 3, 3}, \omega, \mathcal{P}}$ in Figure 4(c).

Example 5. Let $\Box_{3\times 3\times 3}\subset R^3$. The lattice points set $\mathcal{A}_{3, 3, 3} = \Box_{3\times 3\times 3}\cap Z^3$ is shown in Figure 6(a). Suppose that all of the weights are equal to $1$ with the given control points set $\mathcal{P}$ as shown in Figure 6(b). By Definition 4, $\mathcal{P}$ is compatible with its lattice points set $\mathcal{A}_{3, 3, 3}$, because $16$ interior control points are coincident. They degenerate to a single point [the red control point in Figure 6(a)]. By Theorem 4, the 3D Bézier volume $\mathcal{B}_{\mathcal{A}_{3, 3, 3}, \omega, \mathcal{P}}$ defined by $\mathcal{A}_{3, 3, 3}$ and $\mathcal{P}$ is injective for any positive weights. The 3D Bézier volume $\mathcal{B}_{\mathcal{A}_{3, 3, 3}, \omega, \mathcal{P}}$ is shown in Figures 6(c) and 6(d).

Example 6. Let $\Box_{2\times 2\times 2}\subset R^3$. The lattice points set $\mathcal{A}_{2, 2, 2} = \Box_{2\times 2\times 2}\cap Z^3$ is shown in Figure 7(a). Consider a choice of the control points set $\mathcal{P}$, as shown in Figure 7(b). It is easy to find that $\mathcal{P}$ is incompatible with $\mathcal{A}_{2, 2, 2}$, because one of the control points (shown in red) lies in the convex hull of the other four control points. From Theorem 4, the Bézier volume $\mathcal{B}_{\mathcal{A}_{2, 2, 2}, \omega, \mathcal{P}}$ defined by $\mathcal{A}_{2, 2, 2}$ and $\mathcal{P}$ is not injective with some positive weights. When the weights are set to $\omega = \{1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2,$ $1, 1, 1, 1, 20, 1, 1, 1, 1\}$, we can find some self-intersections, as shown in Figure 7(c).

Example 7. For the lattice points set $\mathcal{A}_{3, 3, 3} = \Box_{3\times 3\times 3}\cap Z^3$ shown in Figure 6(a), we change the control points set $\mathcal{P}$ as shown in Figure 8(a). It is obvious that $\mathcal{P}$ is incompatible with $\mathcal{A}_{3, 3, 3}$. By Theorem 4, the Bézier volume $\mathcal{B}_{\mathcal{A}_{3, 3, 3}, \omega, \mathcal{P}}$ defined by $\mathcal{A}_{3, 3, 3}$ and $\mathcal{P}$ is not injective with some positive weights. Suppose that all of the weights are equal to $1$. In this case, the 3D Bézier volume $\mathcal{B}_{\mathcal{A}_{3, 3, 3}, \omega, \mathcal{P}}$ defined by $\mathcal{A}_{3, 3, 3}$ and $\mathcal{P}$ has self-intersections, as shown in Figures 8(b) and 8(c).

Example 8. For the lattice points set $\mathcal{A}_{3, 3, 3} = \Box_{3\times 3\times 3}\cap Z^3$ shown in Figure 6(a), we use a control points set $\mathcal{P}$ in which two corner control points coincide [see the red point in Figure 9(a)]. Then, the 3D Bézier volume $\mathcal{B}_{\mathcal{A}_{3, 3, 3}, \omega, \mathcal{P}}$ defined by $\mathcal{A}_{3, 3, 3}$ and $\mathcal{P}$ is not injective for some positive weights. When all the weights are equal to $1$, we find some self-intersections, as shown in Figure 9(b).

Example 9. For the lattice points set $\mathcal{A}_{3, 3, 3} = \Box_{3\times 3\times 3}\cap Z^3$ shown in Figure 6(a), suppose that the points on one boundary of the control points set shown in Figure 6(b) degenerate to a single point [the red point in Figure 10(a)]. Then, we obtain a new control points set $\mathcal{P}$. This control points set is incompatible with $\mathcal{A}_{3, 3, 3}$. By Theorem 4, the 3D Bézier volume $\mathcal{B}_{\mathcal{A}_{3, 3, 3}, \omega, \mathcal{P}}$ defined by $\mathcal{A}_{3, 3, 3}$ and $\mathcal{P}$ is not injective for some positive weights. When all the weights are equal to $1$, we can find some self-intersections [see Figure 10(b)].

Example 10. Consider a 3D sphere $S$ embedded into a 3D Bézier volume [as shown in Figure 10]. By Theorem 4, we know that $\mathcal{B}_{\mathcal{A}_{3, 3, 3}, \omega, \mathcal{P}}$ is injective. Therefore, the sphere $S$ embedded in the interior of $\mathcal{B}_{\mathcal{A}, \omega, \mathcal{P}}$ is also injective. For the convenience of shape modeling using the control points, we can embed a half-sphere into four 3D Bézier volumes [as shown in Figure 11(b)]. These four injective Bézier volumes guarantee the injectivity of the half-sphere. This is a simple application in which we can use the injective condition of 3D Bézier volumes to check the injectivity of 3D models.

Example 11. Consider an injective bi-cubic Bézier surface $\mathcal{S}$ [see Figure 11](the injectivity of $\mathcal{S}$ can be checked by the conclusion in ^[21,23]). We can embed this into a 3D Bézier volume $\mathcal{B}_{\mathcal{A}_{3, 3, 3}, \omega, \mathcal{P}}$ [see Figure 12(b)]. By Theorem 4, we know that $\mathcal{B}_{\mathcal{A}_{3, 3, 3}, \omega, \mathcal{P}}$ is injective. Therefore, the Bézier surface $\mathcal{S}$ embedded in the interior of $\mathcal{B}_{\mathcal{A}_{3, 3, 3}, \omega, \mathcal{P}}$ is also injective. This is another application in which the injectivity of 3D Bézier volumes can be used to check the injectivity of 3D surfaces.

5.   Conclusions

In this paper, we proposed and proved the geometric conditions for injective 3D Bézier volumes. The result is a sufficient and necessary condition that guarantees 3D Bézier volumes are non-self-intersecting for any positive weights. A direct algorithm for checking the injectivity of 3D Bézier volumes was also proposed. The conditions derived in the paper form a beneficial complement to the result in ^[19]. Our results have potential applications in facial animation and video tracking. More applications and the optimization of Algorithm 1 will be investigated in future work.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (Grant Nos. 11801053, 12071057) and the Fundamental Research Funds for the Central Universities (Grant No. 3132019180, 3132021195).

Conflict of interest

All authors declare no conflicts of interest in this paper.