# Testing tensor product Bézier surfaces for coincidence: A comprehensive
solution

Krassimira Vlachkova<EMAIL_ADDRESS>
###### Abstract

It is known that Bézier curves and surfaces may have multiple representations
by different control polygons. The polygons may have different number of
control points and may even be disjoint. Up to our knowledge, Pekerman et al.
(2005) were the first to address the problem of testing two parametric
polynomial curves for coincidence. Their approach is based on reduction of the
input curves into canonical irreducible form. They claimed that their approach
can be extended for testing tensor product surfaces but gave no further
detail.

In this paper we develop a new technique and provide a comprehensive solution
to the problem of testing tensor product Bézier surfaces for coincidence. In
(Vlachkova, 2017) an algorithm for testing Bézier curves was proposed based on
subdivision. There a partial solution to the problem of testing tensor product
Bézier surfaces was presented. Namely, the case where the irreducible surfaces
are of same degree $(n,m)$, $n,m\in\mathbb{N}$, was resolved under certain
additional condition. The other cases where one of the surfaces is of degree
$(n,m)$ and the other is of degree either $(n,n+m)$, or $(n+m,m)$, or
$(n+m,n+m)$ remained open.

We have implemented our algorithm for testing tensor product Bézier surfaces
for coincidence using Mathematica package. Experimental results and their
analysis are presented.

###### keywords:

Bézier curve , Bézier surface , coincident surfaces , blossoming

††journal: arXiv.org

[inst1]organization=Faculty of Mathematics and Informatics, Sofia University
“St. Kliment Ohridski”, addressline=Blvd. James Bourchier 5, city=Sofia,
postcode=1164, country=Bulgaria

##  1 Introduction

Assume we are given the control polygons of two tensor product Bézier (TPB)
surfaces that are generated by different sources, e. g. different algorithms
or software packages. The two polygons may have different number of control
points and may even be disjoint but nevertheless it is possible that they
represent surfaces with coincidence. Here we consider the problem of finding
whether two control polygons represent different surfaces or
partially/entirely coincident surfaces. In the latter case we need to
determine their coincident part. By coincident surfaces we mean that they
occupy same locus of points in $\mathbb{R}^{3}$ but they may be parameterized
differently, i. e. they are geometrically equivalent as defined in (Denker and
Herron, 1997).

This problem arises in various applications where the two surfaces need to be
stitched together so that the obtained new surface is continuous. The problem
is important also for the intersection algorithms based on subdivision which
do not work well if the surfaces have coincident part.

The problem of testing polynomial curves for coincidence received a
considerable attention by many authors. Up to our knowledge, Pekerman et al.
(2005) were the first to address the problem of testing two parametric
polynomial curves for coincidence. They represented the curves into
irreducible form111Different representations of a polynomial curve may occur
if it has been degree elevated and/or reparameterized by a composition with a
polynomial. A curve is irreducible if it is not a result of a polynomial
composition and has not been degree elevated. Checking curves for
irreducibility is well understood, see e. g. (Barton and Zippel, 1985; Kozen
and Landau, 1989; von zur Gathen, 1990). In our experiments we use the built-
in functions in Mathematica package., tested them for coincidence and
determined their shared domain in the case where coincidence occurs. In (Berry
and Patterson, 1997) a general approach and result for comparing rational
Bézier curves based on their control polygons was proposed. Then, in a series
of papers this approach for testing Bézier curves for coincidence has been
developed and discussed, see (W.-K. Wang et al., 2011; S${\rm\acute{a}}$nchez-
Reyes, 2011; Chen et al., 2013; S${\rm\acute{a}}$nchez-Reyes, 2014; Chen et
al., 2016; S${\rm\acute{a}}$nchez-Reyes, 2015a; Chen and Ma, 2015).

The use of control polygons when comparing Bézier curves is preferable over
their reparametrization as proposed in (Pekerman et al., 2005) due to
stability and numerical issues, see (S${\rm\acute{a}}$nchez-Reyes, 2015b;
Farouki, 2012). In addition, the transformations involved become ill-
conditioned for high degrees. In (Vlachkova, 2017) an algorithm for testing
Bézier curves for coincidence based on control polygons and subdivision was
presented, analysed and experimentally tested.

Pekerman et al. (2005) suggested in the concluding remarks that their approach
for testing polynomial curves for coincidence can be extended to TPB surfaces.
No further detail was given. Vlachkova (2017) proposed an algorithm for
testing TPB surfaces as a generalization of the algorithm for curves presented
in the same paper. The algorithm is based on comparing the control polygons of
the two surfaces. TPB surface $S(u,v)$, $0\leq u\leq 1$, $0\leq v\leq 1$, is
irreducible if all comprising Bézier curves in $u$ and $v$ directions are
irreducible. Two irreducible TPB surfaces can have coincident part either (i)
if they are of same degree $(n,m)$, $n,m\in\mathbb{N}$; or (ii) if one is of
degree $(n,m)$ and the other is of degree either $(n,n+m)$, or $(n+m,m)$, or
$(n+m,n+m)$. The algorithm in (Vlachkova, 2017) works only for TPB surfaces of
same degree $(n,m)$ with overlapping boundary curves, see Fig. 2a. All other
cases remained open.

Here we apply a different approach and present a complete solution to the
problem of comparing TPB surfaces for coincidence. First, we show that all
cases where two irreducible TPB surfaces have coincidence can be reduced to
two main cases: (i) the surfaces are of same degree; (ii) the surfaces are of
degree $(n,m)$ and $(n+m,n+m)$, respectively. Then, we reduce the problem to
solving a nonlinear system of equations of degree $n+m$. The number of the
unknowns is four and eight in cases (i) and (ii), respectively. Finally, we
propose a method for solving these systems. Based on their solutions, we
decide whether the input surfaces are different or partially/entirely
coincident. In the latter case we determine the control points of the
coincident part using the blossoming principle. We also derive sufficient
geometric criteria for checking whether the surfaces are different.

We have implemented our approach using Mathematica package. We reformulate the
arising nonlinear systems of high degree so that Mathematica finds correctly
their solutions. The experimental results are presented, analysed and
visualized.

The paper is organized as follows. In Section 2 we formulate the problem and
consecutively resolve cases (i) and (ii) in Subsection 2.1 and Subsection 2.2,
respectively. In Section 3 we discuss the implementation and present our
experimental results. Summary and conclusions are presented in Section 4.

##  2 Coincidence of TPB surfaces

Tensor product Bézier surface $S(u,v)$ of degree $(n,m)$ for
$n,m\in\mathbb{N}$, and control points ${\bf p}_{ij}\in\mathbb{R}^{3}$,
$i=0,\dots,n$, $j=0,\dots,m$ is defined by

$S(u,v)=\sum_{i=0}^{n}\sum_{j=0}^{m}{\bf p}_{ij}B_{i}^{n}(u)B_{j}^{m}(v),$ (1)

where $0\leq u\leq 1$, $0\leq v\leq 1$, and $B_{i}^{n}(u):={n\choose
i}u^{i}(1-u)^{n-i}$ are the Bernstein polynomials. Hereafter we assume that
the binomial coefficients ${n\choose i}=0$ if $i<0$ or $i>n$.

We denote by $L(S)$ the locus of points $(u,v,S(u,v))$ in $\mathbb{R}^{3}$ for
$0\leq u\leq 1$, $0\leq v\leq 1$.

###### Definition 1

TPB surfaces $S_{1}$ and $S_{2}$ have coincidence if there exists TPB surface
$S$ such that $L(S_{k})\subseteq L(S)$, $k=1,2$. We distinguish the following
three cases.

  1. 1.

if $L(S_{1})\equiv L(S_{2})$ then ${S}_{1}$ and ${S}_{2}$ are coincident,

  2. 2.

if $L(S_{1})\cap L(S_{2})\not=\emptyset$ then ${S}_{1}$ and ${S}_{2}$ have
coincident part,

  3. 3.

if $L(S_{1})\cap L(S_{2})=\emptyset$ then ${S}_{1}$ and ${S}_{2}$ are
disjoint.

${S}_{1}$ and ${S}_{2}$ are different if they do not have coincidence.

Recall that a Bézier curve is irreducible if it is not a result of a
polynomial composition and has not been degree elevated.

###### Definition 2

TPB surface $S(u,v)$ is irreducible if the Bézier curves ${C}^{u}_{j}(u)$,
$j=0,\dots,m$ with control points $\\{{\bf p}_{ij}\\}_{i=0}^{n}$, and
${C}^{v}_{i}(v)$, $i=0,\dots,n$ with control points $\\{{\bf
p}_{ij}\\}_{j=0}^{m}$ are irreducible.

For TPB surface $S$ with control points ${\bf p}_{ij}$ we denote by
$\bm{\rho}$, ${\bm{\rho}}^{1,0}$, and ${\bm{\rho}}^{0,1}$ the finite
differences at point ${\bf p}_{00}$ of order $(n,m)$, $(n-1,m)$, and $(n,m-1)$
respectively, defined by (see (Farin, 2002, pp. 66, 256))

$\displaystyle\bm{\rho}:=\Delta^{n,m}{\bf
p}_{00}=\sum_{i=0}^{n}\sum_{j=0}^{m}(-1)^{n+m-i-j}{n\choose i}{m\choose j}{\bf
p}_{ij},$ $\displaystyle{\bm{\rho}}^{1,0}:=\Delta^{n-1,m}{\bf
p}_{00}=\frac{1}{n}\sum_{i=0}^{n}\sum_{j=0}^{m}(-1)^{n+m-i-j}{n\choose
i}{m\choose j}(i-n){\bf p}_{ij},$ (2)
$\displaystyle{\bm{\rho}}^{0,1}:=\Delta^{n,m-1}{\bf
p}_{00}=\frac{1}{m}\sum_{i=0}^{n}\sum_{j=0}^{m}(-1)^{n+m-i-j}{n\choose
i}{m\choose j}(j-m){\bf p}_{ij}.$

###### Remark 1

If $S$ is irreducible then $\bm{\rho}$ is non-collinear to both
${\bm{\rho}}^{1,0}$ and ${\bm{\rho}}^{0,1}$.

It is known that two irreducible TPB surfaces $S_{1}$ and $S_{2}$ of degrees
$(n,m)$ and $(n_{1},m_{1})$, respectively, may have coincidence only if
$(n_{1},m_{1})$ equals to one of the following: $(n,m)$, $(n,n+m)$, $(n+m,m)$,
$(n+m,n+m)$, see (Farin, 2002, pp. 253). We consider first the cases (i)
$(n_{1},m_{1})=(n,m)$, $n,m\in\mathbb{N}$ and (ii) $(n_{1},m_{1})=(n+m,n+m)$.
Then we show that the other two cases reduce to (ii).

The next proposition is shown in (Berry and Patterson, 1997) and
(S${\rm\acute{a}}$nchez-Reyes, 2011) for curves. It can be easily extended to
case (i) and to case (ii) (see Theorem 1 in (Yang and Zeng, 2008)) as follows.

###### Proposition 1

  1. 1.

The irreducible TPB surfaces $S_{1}(u,v)$ and $S_{2}(s,t)$ of same degree
$(n,m)$ have coincidence if and only if there exists affine transformation

$\varphi:\left\\{\begin{array}[]{l}u(s)=(1-s)a+sb,\\\
v(t)=(1-t)c+td,\end{array}\right.$ (3)

such that $S_{2}(s,t)=S_{1}(u(s),v(t))$ for $0\leq s\leq 1$, $0\leq t\leq 1$,
see Fig. 1(i).

  2. 2.

The irreducible TPB surfaces $S_{1}(u,v)$ and $S_{2}(s,t)$ of degrees $(n,m)$
and $(n+m,n+m)$, respectively, have coincidence if and only if there exists
bilinear transformation

$\psi:\left\\{\begin{array}[]{l}u(s,t)=(1-s)(1-t)a_{1}+(1-s)td_{1}+stc_{1}+s(1-t)b_{1},\\\
v(s,t)=(1-s)(1-t)a_{2}+(1-s)td_{2}+stc_{2}+s(1-t)b_{2}\end{array}\right.$ (4)

such that $S_{2}(s,t)=S_{1}(u(s,t),v(s,t))$ for $0\leq s\leq 1$, $0\leq t\leq
1$, see Fig. 1(ii).

###  2.1 Irreducible TPB surfaces of same degree $(n,m)$

Let $S_{1}(u,v)$ and $S_{2}(s,t)$ be irreducible TPB surfaces of same degree
$(n,m)$ defined as in (1) with control points ${\bf p}^{1}_{ij}$ and ${\bf
p}^{2}_{ij}$, respectively. Let the corresponding vectors ${\bm{\rho}}_{k}$,
${\bm{\rho}}^{1,0}_{k}$, and ${\bm{\rho}}^{0,1}_{k}$, $k=1,2$, be defined by
(2). We assume that $S_{1}$ and $S_{2}$ have different control polygons. In
the next lemma we derive necessary geometric conditions for $S_{1}$ and
$S_{2}$ to have coincidence.

###### Lemma 1

If the irreducible TPB surfaces $S_{1}$ and $S_{2}$ of degree $(n,m)$ have
coincidence then the following statements hold.

  1. 1.

${\bm{\rho}_{1}}$ and ${\bm{\rho}_{2}}$ are collinear;

  2. 2.

$\bm{\rho}_{1}$, $\bm{\rho}_{2}$, ${\bm{\rho}}_{1}^{1,0}$, and
${\bm{\rho}}_{2}^{1,0}$ are coplanar;

  3. 3.

$\bm{\rho}_{1}$, $\bm{\rho}_{2}$, ${\bm{\rho}}_{1}^{0,1}$, and
${\bm{\rho}}_{2}^{0,1}$ are coplanar.

Proof. Assume that $S_{1}$ and $S_{2}$ have coincidence. According to
statement (i) of Proposition 1 there are four numbers $a,b,c,d\in\mathbb{R}$
such that the domain $\\{(u,v):a\leq u\leq b,\ c\leq v\leq d\\}$ is an image
of the domain $\\{(s,t):0\leq s\leq 1,\ 0\leq t\leq 1\\}$ under the affine
transformation (3) (see Fig. 1(i)) and $S_{2}(s,t)=S_{1}(u(s),v(t))$.

(i)

(ii)

Figure 1: (i) The domain $\\{(u,v):a\leq u\leq b,\ c\leq v\leq d\\}$ is an
image of the domain $\\{(s,t):0\leq s\leq 1,\ 0\leq t\leq 1\\}$ under the
affine transformation $u=u(s)=(1-s)a+sb$, $v=v(t)=(1-t)c+td$. (ii) The convex
quadrilateral $ABCD$ is an image of the domain $\\{(s,t)\,:\,0\leq s\leq 1,\
0\leq t\leq 1\\}$ under a bilinear transformation.

We have

$\sum_{i=0}^{n}\sum_{j=0}^{m}{\bf
p}^{2}_{ij}B_{i}^{n}(s)B_{j}^{m}(t)=\sum_{i=0}^{n}\sum_{j=0}^{m}{\bf
p}^{1}_{ij}B_{i}^{n}((1-s)a+sb)B_{j}^{m}((1-t)c+td),\ 0\leq s\leq 1,\ 0\leq
t\leq 1.$ (5)

We take $\frac{\partial^{n+m}}{\partial s^{n}\partial t^{m}}$ derivative in
(5) and obtain

$n!m!{\bm{\rho}_{2}}=n!m!(b-a)^{n}(d-c)^{m}{\bm{\rho}_{1}}.$

Hence, vectors ${\bm{\rho}_{1}}$ and ${\bm{\rho}_{2}}$ are collinear with
${\bm{\rho}_{2}}=\kappa{\bm{\rho}_{1}}$ where we denoted

$\kappa=(b-a)^{n}(d-c)^{m}.$ (6)

This proves statement (i).

Since ${\bm{\rho}_{1}}$ and ${\bm{\rho}_{2}}$ are the coefficients of
$u^{n}v^{m}$ and $s^{n}t^{m}$ in $S_{1}(u,v)$ and $S_{2}(s,t)$, respectively,
and $S_{1}$ and $S_{2}$ are irreducible then ${\bm{\rho}_{1}}\not={\bf 0}$ and
${\bm{\rho}_{2}}\not={\bf 0}$. So the number $\kappa$ is determined as the
ratio of any two corresponding nonzero coordinates of ${\bm{\rho}_{2}}$ and
${\bm{\rho}_{1}}$.

Next, we take $\frac{\partial^{n+m-1}}{\partial s^{n-1}\partial t^{m}}$
derivative in (5) and obtain

$\begin{split}m!(n-1)!\sum_{i=0}^{n}\sum_{j=0}^{m}(-1)^{n+m-i-j}{n\choose
i}{m\choose j}(ns-n+i){\bf p}^{2}_{ij}=\\\
m!(n-1)!(b-a)^{n-1}(d-c)^{m}\sum_{i=0}^{n}\sum_{j=0}^{m}(-1)^{n+m-i-j}{n\choose
i}{m\choose j}(n(s(b-a)+a)-n+i){\bf p}^{1}_{ij},\\\ 0\leq s\leq 1,\end{split}$

which for $s=0$ implies

${\bm{\rho}_{2}^{1,0}}=(b-a)^{n-1}(d-c)^{m}(a{\bm{\rho}_{1}}+{\bm{\rho}_{1}^{1,0}}).$
(7)

Hence, vectors $\bm{\rho}_{1}$, ${\bm{\rho}}_{1}^{1,0}$, and
${\bm{\rho}}_{2}^{1,0}$ are coplanar and (ii) follows from (i).

Similarly, we take $\frac{\partial^{n+m-1}}{\partial s^{n}\partial t^{m-1}}$
derivative in (5) and for $s=0$ obtain

${\bm{\rho}_{2}^{0,1}}=(b-a)^{n}(d-c)^{m-1}(c{\bm{\rho}_{1}}+{\bm{\rho}_{1}^{0,1}}).$
(8)

Therefore vectors $\bm{\rho}_{1}$, ${\bm{\rho}}_{1}^{0,1}$, and
${\bm{\rho}}_{2}^{0,1}$ are coplanar and (iii) follows from (i). $\Box$

###### Remark 2

Surface $S_{2}$ can be considered as obtained from surface $S_{1}$ by
subdivision with respect to $u$ at $a$ and $b$, and with respect to $v$ at $c$
and $d$.

Next we obtain necessary and sufficient conditions for surfaces $S_{1}$ and
$S_{2}$ to have coincidence. In the proof of Lemma 1 we have shown that if
$S_{1}$ and $S_{2}$ have coincidence then there exist numbers $a,b,c,d$
defining affine transformation (3) and satisfying the system

$\left|\begin{array}[]{l}{\bm{\rho}_{2}^{1,0}}=(b-a)^{n-1}(d-c)^{m}(a{\bm{\rho}_{1}}+{\bm{\rho}_{1}^{1,0}}),\\\
{\bm{\rho}_{2}^{0,1}}=(b-a)^{n}(d-c)^{m-1}(c{\bm{\rho}_{1}}+{\bm{\rho}_{1}^{0,1}}),\\\
\kappa=(b-a)^{n}(d-c)^{m},\end{array}\right.$ (9)

where $\kappa$ is determined from $\bm{\rho}_{2}=\kappa\bm{\rho}_{1}$.

###### Lemma 2

If system (9) is consistent then it has a unique solution.

Proof. We multiply the first vector equation in (9) by $b-a$ and the second
one by $d-c$, use $\bm{\rho}_{2}=\kappa\bm{\rho}_{1}$, and obtain

$b{\bm{\rho}_{2}^{1,0}}-a({\bm{\rho}_{2}}+{\bm{\rho}_{2}^{1,0}})=\kappa{\bm{\rho}_{1}^{1,0}},$
(10)
$d{\bm{\rho}_{2}^{0,1}}-c({\bm{\rho}_{2}}+{\bm{\rho}_{2}^{0,1}})=\kappa{\bm{\rho}_{1}^{0,1}}.$
(11)

Hence, (9) is equivalent to the following system

$\left|\begin{array}[]{l}b{\bm{\rho}_{2}^{1,0}}-a({\bm{\rho}_{2}}+{\bm{\rho}_{2}^{1,0}})=\kappa{\bm{\rho}_{1}^{1,0}},\\\
d{\bm{\rho}_{2}^{0,1}}-c({\bm{\rho}_{2}}+{\bm{\rho}_{2}^{0,1}})=\kappa{\bm{\rho}_{1}^{0,1}},\\\
\kappa=(b-a)^{n}(d-c)^{m},\end{array}\right.$ (12)

Each of the two vector equations in (12) is equivalent to a linear system of
three equations of the unknowns $a$, $b$, and $c$, $d$, respectively, for each
of the three vector coordinates. By Remark 1 the ranks of the matrices of
these systems are greater than one. Hence the systems have either unique, or
no solution. Therefore, if system (12) is consistent then it has a unique
solution. $\Box$

The following theorem holds.

###### Theorem 1

The irreducible TPB surfaces $S_{1}$ and $S_{2}$ of degree $(n,m)$ have
coincidence if and only if system (12) is consistent and the control polygon
of the surface corresponding to the unique solution to (12) coincide with the
control polygon of $S_{2}$ (up to eight different enumerations of the control
polygons).

Proof. $\Rightarrow$ Let $S_{1}$ and $S_{2}$ have coincidence. Then according
to statement (i) of Proposition 1 there exist four numbers
$a,b,c,d\in\mathbb{R}$ defining transformation $\varphi$ which are a solution
to system (9) and $S_{2}(s,t)=S_{1}(\varphi)$. According to Lemma 2, the
equivalent to (9) system (12) has a unique solution $(a,b,c,d)$. The control
polygon of the surface corresponding to this solution coincides with the
control polygon of $S_{2}$.

$\Leftarrow$ Let system (12) be consistent. Then, according to Lemma 2, it has
a unique solution. Since the control polygon of the surface $S$ corresponding
to this solution coincide with the control polygon of $S_{2}$ (up to eight
different enumerations of the control polygons) then $S$ and $S_{2}$ coincide
according to Theorem 1 in (Vlachkova, 2017). $\Box$

We continue by providing an efficient approach for testing $S_{1}$ and $S_{2}$
for coincidence. First, we consider the two linear systems (10) and (11) which
have either unique or no solution. Clearly if any of them has no solution then
by Proposition 1 no transformation $\varphi$ exists and $S_{1}$ and $S_{2}$
are different. If both systems have unique solutions, say $(a^{*},b^{*})$,
$(c^{*},d^{*})$, then we need to check if they satisfy
$(b^{*}-a^{*})^{n}(d^{*}-c^{*})^{m}=\kappa$. If they do not, then system (12)
is inconsistent and $S_{1}$ and $S_{2}$ are different. Otherwise, following
Theorem 1, we need to compute the control polygon of surface $S^{*}$
corresponding to $(a^{*},b^{*},c^{*},d^{*})$ and to check if it coincides with
the control polygon of $S_{2}$. If these polygons coincide (up to eight
different enumerations of the control points) then $S_{1}$ and $S_{2}$ have
coincidence, otherwise they are different. We compute the control points of
$S^{*}$ using the blossoming principle, see (Goldman, 2003). In (Goldman,
2003, p. 339) and (Yang and Zeng, 2008) it is pointed out that for any
polynomial surface patch $S(u,v)=\sum_{i=0}^{n}\sum_{j=0}^{m}{\bf
c}_{ij}u^{i}v^{j}$ of degree $(n,m)$ defined for $a\leq u\leq b$ and $c\leq
v\leq d$, the Bézier control points ${\bf p}_{\nu\mu}$, $\nu=0,\dots,n$,
$\mu=0,\dots,m$, of this surface patch are

${\bf
p}_{\nu\mu}=b^{\Box}(\underbrace{a,\dots,a}_{\text{$\nu$}},\underbrace{b,\dots,b}_{\text{$n-\nu$}},\underbrace{c,\dots,c}_{\text{$\mu$}},\underbrace{d,\dots,d}_{\text{$m-\mu$}}),$
(13)

where
$b^{\Box}(u_{1},\dots,u_{n},v_{1},\dots,v_{m})=\sum_{i=0}^{n}\sum_{j=0}^{m}{\bf
c}_{ij}b_{ij}^{\Box}(u_{1},\dots,u_{n},v_{1},\dots,v_{m})$ is the blossom of
$S(u,v)$, and

$b_{ij}^{\Box}(u_{1},\dots,u_{n},v_{1},\dots,v_{m})=\sum_{\\{\alpha_{1},\dots,\alpha_{i}\\}\subseteq\\{1,\dots,n\\}}\frac{u_{\alpha_{1}}\dots
u_{\alpha_{i}}}{\binom{n}{i}}\sum_{\\{\beta_{1},\dots,\beta_{j}\\}\subseteq\\{1,\dots,m\\}}\frac{v_{\beta_{1}}\dots
v_{\beta_{j}}}{\binom{m}{j}}$ (14)

is the blossom of the monomial $u^{i}v^{j}$. In the case where either $i=0$,
or $j=0$, the corresponding sum in (14) equals 1, e. g. $b_{00}^{\Box}=1$. In
the next corollary we present (13) and (14) in an equivalent closed form that
is more suitable for computations.

###### Corollary 1

Bézier control points ${\bf p}_{\nu\mu}$, $\nu=0,\dots,n$, $\mu=0,\dots,m$,
defined by (13) are

${\bf p}_{\nu\mu}=\sum_{i=0}^{n}\sum_{j=0}^{m}\frac{{\bf
c}_{ij}}{\binom{n}{i}\binom{m}{j}}\sum_{k=\max(0,i+\nu-n)}^{\min(i,\nu)}\
\sum_{r=\max(0,j+\mu-m)}^{\min(j,\mu)}\binom{\nu}{k}\binom{n-\nu}{i-k}\binom{\mu}{r}\binom{m-\mu}{j-r}a^{k}b^{i-k}c^{r}d^{j-r}.$
(15)

We outline our procedure for testing $S_{1}$ and $S_{2}$ for coincidence in
algorithmic form below.

Algorithm 1 Testing two irreducible TPB surfaces of degree $(n,m)$ for coincidence Input: |  Irreducible TPB surfaces $S_{1}$ and $S_{2}$ of degree $(n,m)$ given by their control polygons
---|---
Output: |  (i) $S_{1}$ and $S_{2}$ are different;
|  (ii) $S_{1}$ and $S_{2}$ are disjoint;
|  (iii) $S_{1}$ and $S_{2}$ have coincident part. Report its control points.
Step 1. |  Compute vectors $\bm{\rho}_{i}$, ${\bm{\rho}}_{i}^{1,0}$, and ${\bm{\rho}}_{i}^{0,1}$, $i=1,2$.
Step 2. |  Check the conditions of Lemma 1.
|  2.1. If $\bm{\rho}_{1}$, $\bm{\rho}_{2}$ are non-collinear
|  then return (i);
|  else compute $\kappa$ such that $\bm{\rho}_{2}=\kappa\bm{\rho}_{1}$.
|  2.2. If either $\bm{\rho}_{1}$, $\bm{\rho}_{2}$, ${\bm{\rho}}_{1}^{1,0}$,
${\bm{\rho}}_{2}^{1,0}$, or $\bm{\rho}_{1}$, $\bm{\rho}_{2}$,
${\bm{\rho}}_{1}^{0,1}$, ${\bm{\rho}}_{2}^{0,1}$ are non-coplanar
|  then return (i);
|  else system (12) has either unique, or no solution.
Step 3. |  Solve linear systems (10) and (11).
|  If any of them is inconsistent
|  then return (i);
|  else denote their unique solutions by $(a^{*},b^{*})$ and $(c^{*},d^{*})$.
Step 4. |  If $(b^{*}-a^{*})^{n}(d^{*}-c^{*})^{m}\not=\kappa$
|  then return (i);
|  else system (9) is consistent with unique solution
$(a^{*},b^{*},c^{*},d^{*})$.
Step 5. | Compute the control polygon of the transformed TPB surface
|  $S^{*}(s,t)=S_{1}(u(\varphi(s,t),v(\varphi(s,t))$ using (15) and compare it
to the control polygon of $S_{2}$.
|  If they coincide (up to eight different enumerations)
|  then $S_{1}$ and $S_{2}$ have coincidence;
|  else return (i).
Step 6. |  Compute the shared domain $G$ of $S^{*}$ and $S$.
|  If $D=\emptyset$
|  then return (ii);
|  else compute the control points of the coincident part using (15) and
return (iii).

###  2.2 Irreducible Bézier surfaces of degrees $(n,m)$ and $(n+m,n+m)$

Let $S_{1}(u,v)=\sum_{i=0}^{n}\sum_{j=0}^{m}{\bf
p}^{1}_{ij}B_{i}^{n}(u)B_{j}^{m}(v)$ defined for $0\leq u\leq 1$, $0\leq v\leq
1$, and $S_{2}(s,t)=\sum_{i=0}^{n+m}\sum_{j=0}^{n+m}{\bf
p}^{2}_{ij}B_{i}^{n+m}(s)B_{j}^{n+m}(t)$ defined for $0\leq s\leq 1$, $0\leq
t\leq 1$, be irreducible TPB surfaces. For the four boundary curves of $S_{2}$
we denote by ${\bm{\delta}_{k}}$ and ${\bm{\delta}_{k}^{1}}$, $k=1,\dots,4$
the following finite differences

$\displaystyle{\bm{\delta}_{1}}:=\Delta^{n+m,0}{\bf
p}^{2}_{00}=\sum_{i=0}^{n+m}(-1)^{n+m-i}{{n+m}\choose i}{\bf p}^{2}_{i0},$
$\displaystyle{\bm{\delta}_{2}}:=\Delta^{0,n+m}{\bf
p}^{2}_{00}=\sum_{i=0}^{n+m}(-1)^{n+m-i}{{n+m}\choose i}{\bf p}^{2}_{0i},$
$\displaystyle{\bm{\delta}_{3}}:=\Delta^{n+m,0}{\bf
p}^{2}_{0,n+m}=\sum_{i=0}^{n+m}(-1)^{n+m-i}{{n+m}\choose i}{\bf
p}^{2}_{i,n+m},$ $\displaystyle{\bm{\delta}_{4}}:=\Delta^{0,n+m}{\bf
p}^{2}_{n+m,0}=\sum_{i=0}^{n+m}(-1)^{n+m-i}{{n+m}\choose i}{\bf
p}^{2}_{n+m,i},$
$\displaystyle{\bm{\delta}_{1}^{1}}:=(n+m)\Delta^{n+m-1,0}{\bf
p}_{00}^{2}=\sum_{i=0}^{n+m}(-1)^{n+m-i}{{n+m}\choose i}(i-n-m){\bf
p}^{2}_{i0},$ $\displaystyle{\bm{\delta}_{2}^{1}}:=(n+m)\Delta^{0,n+m-1}{\bf
p}_{00}^{2}=\sum_{i=0}^{n+m}(-1)^{n+m-i}{{n+m}\choose i}(i-n-m){\bf
p}^{2}_{0i},$ $\displaystyle{\bm{\delta}_{3}^{1}}:=(n+m)\Delta^{n+m-1,0}{\bf
p}_{0,n+m}^{2}=\sum_{i=0}^{n+m}(-1)^{n+m-i}{{n+m}\choose i}(i-n-m){\bf
p}^{2}_{i,n+m},$
$\displaystyle{\bm{\delta}_{4}^{1}}:=(n+m)\Delta^{0,n+m-1}{\bf
p}_{n+m,0}^{2}=\sum_{i=0}^{n+m}(-1)^{n+m-i}{{n+m}\choose i}(i-n-m){\bf
p}^{2}_{n+m,i}.$

The finite differences $\bm{\rho}$, $\bm{\rho}^{1,0}$, and $\bm{\rho}^{0,1}$
for $S_{1}$ are defined by (2).

In the next lemma we derive necessary geometric conditions for $S_{1}$ and
$S_{2}$ to have coincidence.

###### Lemma 3

If the irreducible TPB surfaces $S_{1}$ and $S_{2}$ of degrees $(n,m)$ and
$(n+m,n+m)$, respectively, have coincidence then the five vectors $\bm{\rho}$,
and $\bm{\delta}_{i}$, $i=1,\dots,4$, are collinear.

Proof. Assume that $S_{1}$ and $S_{2}$ have coincidence. Since $S_{1}$ is of
degree $(n,m)$ and $S_{2}$ is of degree $(n+m,n+m)$ then, according to
statement (ii) of Proposition 1, there exist convex quadrilateral $ABCD$ with
vertices $A(a_{1},a_{2})$, $B(b_{1},b_{2})$, $C(c_{1},c_{2})$,
$D(d_{1},d_{2})$ which is an image of the domain $\\{(s,t)\,:\,0\leq s\leq 1,\
0\leq t\leq 1\\}$ under the bilinear transformation (4) (see Fig. 1(ii)) and
$S_{2}(s,t)=S_{1}(u(s,t),v(s,t))$. Hence, for $0\leq s\leq 1$, $0\leq t\leq 1$
we have

$\sum_{i=0}^{n}\sum_{j=0}^{m}{\bf
p}^{1}_{ij}B_{i}^{n}(u)B_{j}^{m}(v)=\sum_{i=0}^{n+m}\sum_{j=0}^{n+m}{\bf
p}^{2}_{ij}B_{i}^{n+m}(s)B_{j}^{n+m}(t),$ (16)

where $u$ and $v$ are defined by (4).

The image of the boundary segment $\\{(s,t):0\leq s\leq 1,\ t=0\\}$ under the
bilinear transformation (4) is the segment $AB$ and we have
$u=(1-s)a_{1}+sb_{1}$, $v=(1-s)a_{2}+sb_{2}$. Hence, from (16) it follows

$\sum_{i=0}^{n}\sum_{j=0}^{m}{\bf
p}^{1}_{ij}B_{i}^{n}((1-s)a_{1}+sb_{1})B_{j}^{m}((1-s)a_{2}+sb_{2})=\sum_{i=0}^{n+m}{\bf
p}^{2}_{i0}B_{i}^{n+m}(s),\ 0\leq s\leq 1.$ (17)

After differentiation of (17) $n+m$ times we obtain

$(b_{1}-a_{1})^{n}(b_{2}-a_{2})^{m}\bm{\rho}=\bm{\delta}_{1}.$ (18)

Hence, vectors $\bm{\rho}$ and $\bm{\delta}_{1}$ are collinear with
$\kappa_{1}\bm{\rho}=\bm{\delta}_{1}$ where we denoted

$\kappa_{1}=(b_{1}-a_{1})^{n}(b_{2}-a_{2})^{m}.$ (19)

Since $\bm{\rho}$ and $\bm{\delta}_{1}$ are the coefficients of $u^{n}v^{m}$
in $S_{1}(u,v)$ and $s^{n+m}$ in $S_{2}(s,0)$, respectively, and $S_{1}$ and
$S_{2}$ are irreducible then $\bm{\rho}\not={\bf 0}$ and
$\bm{\delta}_{1}\not={\bf 0}$. So the number $\kappa_{1}$ is determined as the
ratio of any two corresponding nonzero coordinates of $\bm{\delta}_{1}$ and
$\bm{\rho}$.

For the remaining three boundary segments we obtain, analogously to (18),

$\displaystyle(d_{1}-a_{1})^{n}(d_{2}-a_{2})^{m}\bm{\rho}=\bm{\delta}_{2},$
$\displaystyle(c_{1}-d_{1})^{n}(c_{2}-d_{2})^{m}\bm{\rho}=\bm{\delta}_{3},$
(20)
$\displaystyle(c_{1}-b_{1})^{n}(c_{2}-b_{2})^{m}\bm{\rho}=\bm{\delta}_{4}.$

Hence, vectors $\bm{\rho}$, $\bm{\delta}_{2}$, $\bm{\delta}_{3}$, and
$\bm{\delta}_{4}$ are collinear with $\kappa_{i}\bm{\rho}=\bm{\delta}_{i}$,
$i=2,3,4$, where we denoted

$\displaystyle\kappa_{2}=(d_{1}-a_{1})^{n}(d_{2}-a_{2})^{m},$
$\displaystyle\kappa_{3}=(c_{1}-d_{1})^{n}(c_{2}-d_{2})^{m},$ (21)
$\displaystyle\kappa_{4}=(c_{1}-b_{1})^{n}(c_{2}-b_{2})^{m}.$

Similarly to $\kappa_{1}$, the numbers $\kappa_{i}$ for $i=2,3,4$ are
determined as the ratio of any two corresponding nonzero coordinates of
$\bm{\delta}_{i}$ and $\bm{\rho}$, respectively. $\Box$

Next we obtain a necessary and sufficient conditions for surfaces $S_{1}$ and
$S_{2}$ to have coincidence. We differentiate (17) $n+m-1$ times and obtain
for $s=0$

$(b_{1}-a_{1})^{n-1}(b_{2}-a_{2})^{m-1}\big{(}n\bm{\rho}^{1,0}(b_{2}-a_{2})+m\bm{\rho}^{0,1}(b_{1}-a_{1})+n\bm{\rho}a_{1}(b_{2}-a_{2})+m\bm{\rho}a_{2}(b_{1}-a_{1})\big{)}=\bm{\delta}_{1}^{1}.$

Similarly, for the remaining three boundary segments we obtain

$\begin{array}[]{r}(d_{1}-a_{1})^{n-1}(d_{2}-a_{2})^{m-1}\big{(}n\bm{\rho}^{1,0}(d_{2}-a_{2})+m\bm{\rho}^{0,1}(d_{1}-a_{1})+n\bm{\rho}a_{1}(d_{2}-a_{2})+m\bm{\rho}a_{2}(d_{1}-a_{1})\big{)}=\bm{\delta}_{2}^{1},\\\\[2.15277pt]
(c_{1}-d_{1})^{n-1}(c_{2}-d_{2})^{m-1}\big{(}n\bm{\rho}^{1,0}(c_{2}-d_{2})+m\bm{\rho}^{0,1}(c_{1}-d_{1})+n\bm{\rho}d_{1}(c_{2}-d_{2})+m\bm{\rho}d_{2}(c_{1}-d_{1})\big{)}=\bm{\delta}_{3}^{1},\\\\[2.15277pt]
(c_{1}-b_{1})^{n-1}(c_{2}-b_{2})^{m-1}\big{(}n\bm{\rho}^{1,0}(c_{2}-b_{2})+m\bm{\rho}^{0,1}(c_{1}-b_{1})+n\bm{\rho}b_{1}(c_{2}-b_{2})+m\bm{\rho}b_{2}(c_{1}-b_{1})\big{)}=\bm{\delta}_{4}^{1}.\end{array}$

Therefore, if $S_{1}$ and $S_{2}$ have coincidence then the eight numbers
$a_{i},b_{i},c_{i},d_{i}$, $i=1,2$, defining bilinear transformation (4)
satisfy the system

$\left|\begin{array}[]{l}(b_{1}-a_{1})^{n-1}(b_{2}-a_{2})^{m-1}(n\bm{\rho}^{1,0}(b_{2}-a_{2})+m\bm{\rho}^{0,1}(b_{1}-a_{1})+n\bm{\rho}a_{1}(b_{2}-a_{2})+m\bm{\rho}a_{2}(b_{1}-a_{1}))=\bm{\delta}_{1}^{1},\\\\[2.15277pt]
(d_{1}-a_{1})^{n-1}(d_{2}-a_{2})^{m-1}(n\bm{\rho}^{1,0}(d_{2}-a_{2})+m\bm{\rho}^{0,1}(d_{1}-a_{1})+n\bm{\rho}a_{1}(d_{2}-a_{2})+m\bm{\rho}a_{2}(d_{1}-a_{1}))=\bm{\delta}_{2}^{1},\\\\[2.15277pt]
(c_{1}-d_{1})^{n-1}(c_{2}-d_{2})^{m-1}(n\bm{\rho}^{1,0}(c_{2}-d_{2})+m\bm{\rho}^{0,1}(c_{1}-d_{1})+n\bm{\rho}d_{1}(c_{2}-d_{2})+m\bm{\rho}d_{2}(c_{1}-d_{1}))=\bm{\delta}_{3}^{1},\\\\[2.15277pt]
(c_{1}-b_{1})^{n-1}(c_{2}-b_{2})^{m-1}(n\bm{\rho}^{1,0}(c_{2}-b_{2})+m\bm{\rho}^{0,1}(c_{1}-b_{1})+n\bm{\rho}b_{1}(c_{2}-b_{2})+m\bm{\rho}b_{2}(c_{1}-b_{1}))=\bm{\delta}_{4}^{1},\\\\[2.15277pt]
\kappa_{1}=(b_{1}-a_{1})^{n}(b_{2}-a_{2})^{m},\\\\[2.15277pt]
\kappa_{2}=(d_{1}-a_{1})^{n}(d_{2}-a_{2})^{m},\\\\[2.15277pt]
\kappa_{3}=(c_{1}-d_{1})^{n}(c_{2}-d_{2})^{m},\\\\[2.15277pt]
\kappa_{4}=(c_{1}-b_{1})^{n}(c_{2}-b_{2})^{m},\end{array}\right.$ (22)

where $\kappa_{i}$ is determined from $\kappa_{i}\bm{\rho}=\bm{\delta}_{i}$,
$i=1,\dots,4$.

Straightforward application of Mathematica packages and build-in functions
doesn’t yield solutions to system (22) efficiently. Hence, it is important to
develop a method to simplify and solve it.

###### Lemma 4

If system (22) is consistent and
rank($\bm{\rho},\bm{\rho}^{1,0},\bm{\rho}^{0,1}$)=3 then it has a unique
solution. If rank($\bm{\rho},\bm{\rho}^{1,0},\bm{\rho}^{0,1}$)=2 then it has
at most two solutions.

Proof. We consider the first equation of system (22), denote $x:=b_{1}-a_{1}$,
$y:=b_{2}-a_{2}$, and obtain

$x^{n-1}y^{m-1}(n{\bm{\rho}^{1,0}}y+m{\bm{\rho}^{0,1}}x+n\bm{\rho}a_{1}y+m\bm{\rho}a_{2}x)=\bm{\delta}_{1}^{1}.$
(23)

Vector equation (23) is equivalent to the following system

$\left|\begin{array}[]{l}\kappa_{1}(n\rho^{1,0}_{1}y+m\rho^{0,1}_{1}x+n{{\rho}_{1}}a_{1}y+m{{\rho}_{1}}a_{2}x)=\delta_{1}xy,\\\\[4.30554pt]
\kappa_{1}(n\rho^{1,0}_{2}y+m\rho^{0,1}_{2}x+n{{\rho}_{2}}a_{1}y+m{{\rho}_{2}}a_{2}x)=\delta_{2}xy,\\\\[4.30554pt]
\kappa_{1}(n\rho^{1,0}_{3}y+m\rho^{0,1}_{3}x+n{{\rho}_{3}}a_{1}y+m{{\rho}_{3}}a_{2}x)=\delta_{3}xy,\end{array}\right.$
(24)

where ${\bm{\rho}^{1,0}}=(\rho^{1,0}_{1},\rho^{1,0}_{2},\rho^{1,0}_{3})$,
${\bm{\rho}^{0,1}}=(\rho^{0,1}_{1},\rho^{0,1}_{2},\rho^{0,1}_{3})$,
$\bm{\rho}=({\rho}_{1},{\rho}_{2},{\rho}_{3})$, and
$\bm{\delta}_{1}^{1}=(\delta_{1},\delta_{2},\delta_{3})$.

To solve (24) we consider two cases according to the rank of the matrix $M$,
where

$M=\left(\begin{array}[]{cccc}n\rho^{1,0}_{1}&m\rho^{0,1}_{1}&n{\rho}_{1}&m{\rho}_{1}\\\
n\rho^{1,0}_{2}&m\rho^{0,1}_{2}&n{\rho}_{2}&m{\rho}_{2}\\\
n\rho^{1,0}_{3}&m\rho^{0,1}_{3}&n{\rho}_{3}&m{\rho}_{3}\end{array}\right).$
(25)

By Remark 1 the rank of M is greater that 1. Further on, $\alpha$, $\beta$,
$C$, $\alpha_{i}$, $\beta_{i}$, $C_{i}$, $i=1,2$ denote real constants that
depend on the input data only, more precisely on $\bm{\rho}^{1,0}$,
$\bm{\rho}^{0,1}$, $\bm{\rho}$, and $\bm{\delta}_{1}^{1}$.

Case 1. rank(M)=3

Since $\bm{\rho}$ is nonzero vector then some of its coordinates, say
${\rho}_{1}$, is nonzero. We eliminate $a_{1}y$ and $a_{2}x$ from the last two
equations of (24) by multiplying the first equation by
$-{\rho}_{2}/{{\rho}_{1}}$ and $-{\rho}_{3}/{{\rho}_{1}}$ consecutively and
adding it to the second and third equations, respectively. We obtain a system
of the following type

$\left|\begin{array}[]{l}\alpha_{1}x+\beta_{1}y=C_{1}xy,\\\
\alpha_{2}x+\beta_{2}y=C_{2}xy,\end{array}\right.$ (26)

which has a unique solution $(x,y)$.

We solve in an analogous way the remaining three vector equations of (22) with
respect to the unknowns $d_{1}-a_{1}$ and $d_{2}-a_{2}$; $c_{1}-d_{1}$ and
$c_{2}-d_{2}$; $c_{1}-b_{1}$ and $c_{2}-b_{2}$, respectively. Note that the
corresponding three equivalent systems have same matrix $M$ as system (24) and
differ by their right sides only. Hence, each of them has also a unique
solution which can be found straightforwardly. Therefore, if system (22) is
consistent then it has a unique solution.

Case 2. rank(M)=2

In this case, (24) has two linearly independent equations. Similar to Case 1,
since the coefficients of $a_{1}y$ and $a_{2}x$ are in ratio $n:m$, then by
multiplying one of these equations by a suitable constant and adding it to the
other equation we exclude $a_{1}y$ and $a_{2}x$ and obtain one equation of the
following type

$\alpha x+\beta y=Cxy.$ (27)

So we have to solve the following system

$\left|\begin{array}[]{l}x^{n}y^{m}=\kappa_{1},\\\ \alpha x+\beta
y=Cxy.\end{array}\right.$ (28)

###### Claim 1

System (28) has at most two solutions in real numbers.

Proof. Omitted.

In the general case where $\alpha\not=0$ and $\beta\not=0$ from (27) we have
$y=\alpha x/(Cx-\beta)$. Hence, system (28) reduces to the following
polynomial equation of degree $n+m$

$x^{n}(\alpha x)^{m}=\kappa_{1}(Cx-\beta)^{m}.$ (29)

We solve (29) using Mathematica and find all its real solutions. We note that
if $n+m$ is odd then the solution is unique, otherwise (29) may have two
solutions.

So far we have found all admissible values for the unknown $x=b_{1}-a_{1}$ and
$y=b_{2}-a_{2}$. We solve in an analogous way the remaining three vector
equations of (22) with respect to the unknowns $d_{1}-a_{1}$ and
$d_{2}-a_{2}$; $c_{1}-d_{1}$ and $c_{2}-d_{2}$; $c_{1}-b_{1}$ and
$c_{2}-b_{2}$, respectively. Recall that the four systems have same matrix $M$
and differ by their right sides only.

Further, we select all combinations of quadruplets $(x_{1},x_{2},x_{3},x_{4})$
and $(y_{1},y_{2},y_{3},y_{4})$ such that $(x_{i},y_{i})$, $i=1,\dots,4$ are
solutions to the first four equations of (22), respectively, and in addition
satisfy the following conditions

$x_{1}-x_{2}-x_{3}+x_{4}=0,\quad y_{1}-y_{2}-y_{3}+y_{4}=0.$ (30)

Next we show how to obtain the eight unknowns $a_{i},b_{i},c_{i},d_{i}$,
$i=1,2$, from the selected quadruplets $(x_{1},x_{2},x_{3},x_{4})$ and
$(y_{1},y_{2},y_{3},y_{4})$, if any. Let $(x_{1},x_{2},x_{3},x_{4})$ and
$(y_{1},y_{2},y_{3},y_{4})$ be a couple of the selected quadruplets. Since
$b_{i},c_{i},d_{i}$, $i=1,2$, can be represented through $a_{1},a_{2}$ as

$b_{1}=a_{1}+x_{1},b_{2}=a_{2}+y_{1};\
c_{1}=a_{1}+x_{2}+x_{3},c_{2}=a_{2}+y_{2}+y_{3};d_{1}=a_{1}+x_{1},d_{2}=a_{2}+y_{2},$
(31)

then we have to find $a_{1},a_{2}$ only. We replace $(x_{i},y_{i})$,
$i=1,\dots,4$, and the relations (31) in the four vector equations of (22) and
for each of them we obtain a linear equation of $a_{1}$ and $a_{2}$. If the
system of these four linear equations is consistent, i. e. its rank is 2, and
in addition the corresponding $a_{i},b_{i},c_{i},d_{i}$, $i=1,2$, satisfy the
last four equations of (22) then
$(a_{1},a_{2},b_{1},b_{2},c_{1},c_{2},d_{1},d_{2})$ is a solution to (22).
Otherwise, the selected couple of quadruplets does not produce a solution to
(22). In this case, if system (22) is consistent it may have at most two
solutions and we have shown how to find both of them. $\Box$

The following theorem holds.

###### Theorem 2

The irreducible TPB surfaces $S_{1}$ and $S_{2}$ of degrees $(n,m)$ and
$(n+m,n+m)$, respectively, have coincidence if and only if system (22) is
consistent and the control polygon of the surface corresponding to any
solution to (22) coincide with the control polygon of $S_{2}$ (up to eight
different enumeration of the control points).

Proof. $\Rightarrow$ Let $S_{1}$ and $S_{2}$ have coincidence. Then according
to statement (ii) of Proposition 1 there exist eight numbers
$a_{i},b_{i},c_{i},d_{i}\in\mathbb{R}$, $i=1,2$, defining transformation
$\psi$ which are a solution to system (22) and $S_{2}(s,t)=S_{1}(\psi)$. The
control polygon of the surface corresponding to the solution
$(a_{1},a_{2},b_{1},b_{2},c_{1},c_{2},d_{1},d_{2})$ coincides with the control
polygon of $S_{2}$.

$\Leftarrow$ Let system (22) be consistent. Then, according to Lemma 4, it may
have at most two solutions. Since there is a solution such that the control
polygon of the surface $S$ corresponding to this solution coincides with the
control polygon of $S_{2}$ (up to eight different enumerations of the control
polygons) then $S$ and $S_{2}$ coincide according to Theorem 1 in (Vlachkova,
2017). $\Box$

We continue by providing an efficient approach for testing $S_{1}$ and $S_{2}$
for coincidence. First, we find all real solutions to system (22) using the
proposed technique in Lemma 4. Clearly, if system (22) has no real solution
then by Proposition 1 no transformation $\psi$ exists and $S_{1}$ and $S_{2}$
are different. Otherwise, let
$(a_{1},a_{2},b_{1},b_{2},c_{1},c_{2},d_{1},d_{2})$ be a solution to system
(22). Following Theorem 2, we need to compute the control polygon of surface
$S$ corresponding to this solution and to check if it coincides with the
control polygon of $S_{2}$. If these polygons coincide (up to eight different
enumerations of the control points) then $S_{1}$ and $S_{2}$ have coincidence,
otherwise they are different and we continue by checking the second solution
to system (22), if any.

Next we describe how we compute the control points of the corresponding
surface $S$ defined in quadrangle $\Box ABCD$ with vertices $A(a_{1},b_{1})$,
$B(b_{1},b_{2})$, $C(c_{1},c_{2})$, and $D(d_{1},d_{2})$ by (13). First, we
compute the shared domain $G$ of $S$ and $S_{2}$. If $G$ is the empty set then
$S_{1}$ and $S_{2}$ are disjoint. Otherwise $S_{1}$ and $S_{2}$ have
coincident part and we find it by using the blossoming principle. In this
case, unlike the case where $S_{1}$ and $S_{2}$ are of same degree, the shared
domain can be a polygon with at most eight vertices, see Fig. 6. If the number
of the polygon vertices is even we represent the coincident part as a union of
TPB surfaces. For example, the surface in Fig. 6c. is represented as a union
of two TPB surfaces. If the number of the polygon vertices is odd we represent
the coincident part as a union of TPB surfaces and a triangular Bézier (TB)
surface. Similar to TPB surface, we compute the control points of the TB
surface using the blossoming principle. In (Goldman, 2003, p. 331) and (Yang
and Zeng, 2008) it is pointed out that for any polynomial surface path
$S(u,v)=\sum_{i=0}^{n}\sum_{j=0}^{m}{\bf c}_{ij}u^{i}v^{j}$ of total degree
$n+m$ defined in a triangle $\triangle MNP$, the Bézier control points ${\bf
q}_{\nu\mu}$ of this surface patch are

${\bf
q}_{\nu\mu}=b^{\triangle}(\underbrace{M,\dots,M}_{\nu},\underbrace{N,\dots,N}_{\mu},\underbrace{P,\dots
P}_{n+m-\nu-\mu}),$ (32)

where
$b^{\triangle}((u_{1},v_{1}),\dots,(u_{n+m},v_{n+m}))=\sum_{i=0}^{n}\sum_{j=0}^{m}{\bf
c}_{ij}b_{ij}^{\triangle}((u_{1},v_{1}),\dots,(u_{n+m},v_{n+m}))$ is the
blossom of $S(u,v)$, and

$b_{ij}^{\triangle}((u_{1},v_{1}),\dots,(u_{n+m},v_{n+m}))=\sum_{\begin{array}[]{c}{\scriptstyle\\{\alpha_{1},\dots,\alpha_{i}\\}\subseteq
K}\\\ {\scriptstyle\\{\beta_{1},\dots,\beta_{j}\\}\subseteq
K\backslash\\{\alpha_{1},\dots,\alpha_{i}\\}}\end{array}}\frac{u_{\alpha_{1}}\dots
u_{\alpha_{i}}v_{\beta_{1}}\dots v_{\beta_{j}}}{\binom{n+m}{i,j}},$ (33)

$K=\\{1,\dots,n+m\\}$, $\binom{n+m}{i,j}=\frac{(n+m)!}{i!j!(n+m-i-j)!}$, is
the blossom of the monomial $u^{i}v^{j}$. In the case where either $i=0$, or
$j=0$ the corresponding sum in (33) equals 1. In the next corollary we present
(32) in an equivalent closed form that is more suitable for evaluations of the
control points.

###### Corollary 2

Bézier control points ${\bf q}_{\nu\mu}$, $\nu=0,\dots,n$,
$\mu=0,\dots,m$,defined by (32) are

${\bf q}_{\nu\mu}=\sum_{i=0}^{n}\sum_{j=0}^{m}\frac{{\bf
c}_{ij}}{\binom{n+m}{i,j}}b_{ij}^{\triangle}=\sum_{j_{\beta}=\underline{j}_{\beta}}^{\bar{j}_{\beta}}\sum_{j_{\alpha}=\underline{j}_{\alpha}}^{\bar{j}_{\alpha}}\sum_{i_{\beta}=\underline{i}_{\beta}}^{\bar{i}_{\beta}}\sum_{i_{\alpha}=\underline{i}_{\alpha}}^{\bar{i}_{\alpha}}\binom{\nu}{i_{\alpha}}\binom{\mu}{i_{\beta}}\binom{\lambda}{i_{\gamma}}\binom{\nu-
i_{\alpha}}{j_{\alpha}}\binom{\mu-i_{\beta}}{j_{\beta}}\binom{\lambda-
i_{\gamma}}{j_{\gamma}}a_{1}^{i_{\alpha}}b_{1}^{i_{\beta}}c_{1}^{i_{\gamma}}a_{2}^{j_{\alpha}}b_{2}^{j_{\beta}}c_{2}^{j_{\gamma}},$
(34)

where

$\begin{array}[]{l}\lambda=n+m-\nu-\mu,\ i_{\gamma}=i-i_{\alpha}-i_{\beta},\
j_{\gamma}=j-j_{\alpha}-j_{\beta},\\\
\underline{i}_{\alpha}=\max(0,i-\mu-\lambda),\
\bar{i}_{\alpha}=\min(i,\nu),\\\ \underline{i}_{\beta}=\max(0,i-\nu-\lambda),\
\bar{i}_{\beta}=\min(i-i_{\alpha},\mu),\\\
\underline{j}_{\alpha}=\max(0,j-(\mu-i_{\beta})-(\lambda-i_{\gamma})),\
\bar{j}_{\alpha}=\min(j,\nu-i_{\alpha}),\\\
\underline{j}_{\beta}=\max(0,j-(\nu-i_{\alpha})-(\lambda-i_{\gamma})),\
\bar{j}_{\beta}=\min(j-j_{\alpha},\mu-i_{\beta}).\end{array}$

We outline our procedure for testing $S_{1}$ and $S_{2}$ for coincidence in
algorithmic form in Algorithm 2.

Algorithm 2 Testing two irreducible TPB surfaces of degree $(n,m)$ and $(n+m,n+m)$ for coincidence Input: |  Irreducible TPB surfaces $S_{1}$ and $S_{2}$ of degree $(n,m)$ and $(n+m,n+m)$ given by their control polygons
---|---
Output: |  (i) $S_{1}$ and $S_{2}$ are different;
|  (ii) $S_{1}$ and $S_{2}$ are disjoint;
|  (iii) $S_{1}$ and $S_{2}$ have coincident part. Report its control
| points.
Step 1. |  Compute vectors $\bm{\rho}$, ${\bm{\rho}}^{1,0}$, ${\bm{\rho}}^{0,1}$, ${\bm{\delta}}_{i}$, and ${\bm{\delta_{i}}}^{1}$, $i=1,\dots,4$.
Step 2. |  If $\bm{\rho}$ and ${\bm{\delta}}_{i}$ for any $i$, $i=1,\dots,4$, are non-collinear
|  then return (i);
|  else compute $\kappa_{i}$ such that $\kappa_{i}\bm{\rho}=\bm{\delta}_{i}$,
$i=1,\dots,4$.
Step 3. |  Solve the first four vector equations of (22) according to Case 1 and Case 2 of Lemma 4
|  and find all admissible couples of quadruplets $(x_{1},x_{2},x_{3},x_{4})$
and $(y_{1},y_{2},y_{3},y_{4})$.
Step 4. | For any admissible couple of quadruplets
|  if either $x_{1}-x_{2}-x_{3}+x_{4}\not=0$, or
$y_{1}-y_{2}-y_{3}+y_{4}\not=0$
|  then return (i);
|  else if $x_{i}^{n}y_{i}^{m}\not=k_{i}$ for any $i$, $i=1,\dots,4$
|  then return (i);
|  else substitute (31) in the vector equations of (22) and
|  obtain a system of four linear equations of $a_{1}$ and $a_{2}$.
|  If this system is inconsistent
|  then return (i);
|  else $(a_{1},a_{2},b_{1},b_{2},c_{1},c_{2},d_{1},d_{2})$ is a solution to
(22).
Step 5. |  Compute the control polygon of the transformed TPB surface $S(s,t)=S_{1}(\psi(s,t))$ using (15) and (34)
|  and compare it to the control polygon of $S_{2}$.
|  If they coincide (up to eight different enumerations)
|  then $S_{1}$ and $S_{2}$ have coincidence;
|  else return (i).
Step 6. |  Compute the shared domain $G$ of $S$ and $S_{2}$.
|  If $D=\emptyset$
|  then return (ii);
|  else divide $G$ into quadrangles and a triangle (if necessary), compute the
control points of
|  the corresponding coincident Bézier surfaces using (15) and (34), and
return (iii).

###### Remark 3

In the case where the shared domain is not a rectangle, multiple
representations of the coincident part as a union of Bézier surfaces exist.

###### Remark 4

The case where $S_{1}$ is of degree $(n,m)$ and $S_{2}$ is of degree either
$(n,n+m)$, or $(n+m,m)$ is analogous to the case where $S_{2}$ is of degree
$(n+m,n+m)$. The only difference is that (16) becomes (e. g. for degree
$(n+m,m)$)

$\sum_{i=0}^{n}\sum_{j=0}^{m}{\bf
p}^{1}_{ij}B_{i}^{n}(u)B_{j}^{m}(v)=\sum_{i=0}^{n+m}\sum_{j=0}^{m}{\bf
p}^{2}_{ij}B_{i}^{n+m}(s)B_{j}^{m}(t).$

Further, the arguments are the same as in the case where $S_{1}$ is of degree
$(n,m)$ and $S_{2}$ is of degree $(n+m,n+m)$.

##  3 Examples and results

We have implemented our method using Mathematica package. In this section we
present and analyze the results from our experimental work. In our examples we
consider irreducible TPB surfaces.

###### Example 1

This example illustrates the only case where the direct generalization of the
algorithm for curves works, see (Vlachkova, 2017). More precisely, this is the
case where the two TPB surfaces of same degree have overlapping boundary
curves. Here we apply the new method outlined in Algorithm 1. The irreducible
surfaces $S_{1}$ and $S_{2}$ are of degree $(4,2)$. Their control points are
shown in Table 1. The unique solution of system (9) is
$(a^{*},b^{*},c^{*},d^{*})=(0,1/2,1/6,3/4)$. Surfaces $S_{1}$ and $S_{2}$ are
shown in Fig. 2a. and Fig. 2b., respectively. Their coincident part is surface
$S_{2}$. Both surfaces and their coincident part with its control polygon are
shown in Fig. 3a.

a.

b.

c.

Figure 2: (illustrates examples 1 and 2) Three irreducible TPB surfaces of
degree $(4,2)$ with control points shown in Table 1. a. Surface $S_{1}$; b.
Surface $S_{2}$; c. Surface $S_{3}$;

a.

b.

Figure 3: Testing for coincidence the surfaces shown in Fig. 2. a. Example 1:
The coincident part of $S_{1}$ and $S_{2}$ is $S_{2}$; b. Example 2: The
coincident part of $S_{1}$ and $S_{3}$ is $S_{2}$.

Table 1:  The control points of irreducible TPB surfaces $S_{1}$, $S_{2}$, $S_{3}$ of degree $(4,2)$ from examples 1 and 2 $S_{1}$ | ${\bf p}_{00}=(0,0,0)$ | ${\bf p}_{01}=(0,\frac{7}{10},-\frac{1}{2})$ | ${\bf p}_{02}=(0,2,-\frac{4}{5})$
---|---|---|---
| ${\bf p}_{10}=(1,0,1)$ | ${\bf p}_{11}=(1,1,0)$ | ${\bf p}_{12}=(1,1,1)$
| ${\bf p}_{20}=(2,0,\frac{3}{4})$ | ${\bf p}_{21}=(2,1,\frac{6}{5})$ | ${\bf p}_{22}=(2,2,\frac{3}{4})$
| ${\bf p}_{30}=(3,-1,\frac{3}{20})$ | ${\bf p}_{31}=(3,1,\frac{2}{5})$ | ${\bf p}_{32}=(3,2,\frac{1}{5})$
| ${\bf p}_{40}=(4,0,\frac{1}{5})$ | ${\bf p}_{41}=(4,2,\frac{1}{4})$ | ${\bf p}_{42}=(4,3,\frac{3}{4})$
$S_{2}$ | ${\bf p}_{00}=(\frac{2}{3},-\frac{5}{324},\frac{6157}{12960})$ | ${\bf p}_{01}=(\frac{2}{3},\frac{2179}{5184},\frac{9829}{51840})$ | ${\bf p}_{02}=(\frac{2}{3},\frac{1073}{1296},\frac{9689}{103680})$
| ${\bf p}_{10}=(\frac{5}{4},\frac{-23}{432},\frac{425}{576})$ | ${\bf p}_{11}=(\frac{5}{4},\frac{1567}{3456},\frac{5881}{11520})$ | ${\bf p}_{12}=(\frac{5}{4},\frac{1447}{1728},\frac{6673}{13824})$
| ${\bf p}_{20}=(\frac{11}{6},-\frac{1}{6},\frac{3907}{5760})$ | ${\bf p}_{21}=(\frac{11}{6},\frac{107}{256},\frac{15241}{23040})$ | ${\bf p}_{22}=(\frac{11}{6},\frac{515}{576},\frac{30277}{46080})$
| ${\bf p}_{30}=(\frac{29}{12},-\frac{27}{64},\frac{1837}{3840})$ | ${\bf p}_{31}=(\frac{29}{12},\frac{165}{512},\frac{2837}{5120})$ | ${\bf p}_{32}=(\frac{29}{12},\frac{703}{768},\frac{17401}{30720})$
| ${\bf p}_{40}=(3,-\frac{27}{64},\frac{849}{2560})$ | ${\bf p}_{41}=(3,\frac{2287}{5120},\frac{4253}{10240})$ | ${\bf p}_{42}=(3,\frac{1433}{1280},\frac{9489}{20480})$
$S_{3}$ | ${\bf p}_{00}=(\frac{2}{3},-\frac{11941}{32400},\frac{475469}{648000})$ | ${\bf p}_{01}=(\frac{2}{3},\frac{247}{960},\frac{29557}{129600})$ | ${\bf p}_{02}=(\frac{2}{3},\frac{1073}{1296},\frac{9689}{103680})$
| ${\bf p}_{10}=(\frac{5}{4},-\frac{3443}{7200},\frac{411113}{432000})$ | ${\bf p}_{11}=(\frac{5}{4},\frac{1727}{5760},\frac{11267}{21600})$ | ${\bf p}_{12}=(\frac{5}{4},\frac{1447}{1728},\frac{6673}{13824})$
| ${\bf p}_{20}=(\frac{11}{6},-\frac{1877}{2880},\frac{199789}{288000})$ | ${\bf p}_{21}=(\frac{11}{6},\frac{2621}{11520},\frac{849}{1280})$ | ${\bf p}_{22}=(\frac{11}{6},\frac{515}{576},\frac{30277}{46080})$
| ${\bf p}_{30}=(\frac{29}{12},-\frac{9997}{9600},\frac{26091}{64000})$ | ${\bf p}_{31}=(\frac{29}{12},\frac{653}{7680},\frac{659}{1200})$ | ${\bf p}_{32}=(\frac{29}{12},\frac{703}{768},\frac{17401}{30720})$
| ${\bf p}_{40}=(3,-\frac{36737}{32000},\frac{33149}{128000})$ | ${\bf p}_{41}=(3,\frac{909}{5120},\frac{10141}{25600})$ | ${\bf p}_{42}=(3,\frac{1433}{1280},\frac{9489}{20480})$

###### Example 2

We test for coincidence the irreducible surfaces $S_{1}$ and $S_{3}$ of degree
$(4,2)$ with control points shown in Table 1. We apply Algorithm 1. The unique
solution of system (9) is $(a^{*},b^{*},c^{*},d^{*})=(-1/5,1/2,1/6,3/4)$.
Surfaces $S_{1}$ and $S_{3}$ are shown in Fig. 2b. and Fig. 2c., respectively.
Their coincident part is $S_{2}$ and it is shown with its control polygon in
Fig. 2b.

###### Example 3

We consider the irreducible surfaces $S_{1}$ and $S_{2}$ of degree $(2,3)$ and
$(5,5)$, respectively. Their control points are shown in Table 2. This example
matches Case 1 of Lemma 4, and hence system (22) has a unique solution
$(a_{1},a_{2},b_{1},b_{2},c_{1},c_{2},d_{1},d_{2})$=$(0,1/2,1/2,0,1,1/2,1/2,1)$.
Surfaces $S_{1}$ and $S_{3}$ are shown in Fig. 4a. and Fig. 4b., respectively.
They have coincidence and their coincident part is surface $S_{2}$, see Fig.
4c.

a.

b.

c.

Figure 4: The irreducible TPB surfaces $S_{1}$ of degree $(2,3)$ and $S_{2}$ of degree $(5,5)$ from Example 3. The corresponding control points are shown in Table 2. a. Surface $S_{1}$; b. Surface $S_{2}$; c. The coincident part of $S_{1}$ and $S_{2}$ is $S_{2}$. Table 2:  The control points of irreducible TPB surfaces of degree $(2,3)$ and $(5,5)$ from Example 3 $S_{1}$ | ${\bf p}_{00}=(0,0,0)$ | ${\bf p}_{01}=(\frac{3}{2},0,-3)$ | ${\bf p}_{02}=(\frac{3}{2},0,3)$ | ${\bf p}_{03}=(3,0,0)$
---|---|---|---|---
| ${\bf p}_{10}=(0,\frac{3}{2},-3)$ | ${\bf p}_{11}=(\frac{4}{3},\frac{4}{3},0)$ | ${\bf p}_{12}=(\frac{7}{6},\frac{5}{3},-\frac{10}{3})$ | ${\bf p}_{13}=(3,1,1)$
| ${\bf p}_{20}=(0,\frac{3}{2},3)$ | ${\bf p}_{21}=(\frac{5}{3},\frac{7}{6},\frac{10}{3})$ | ${\bf p}_{22}=(\frac{11}{6},\frac{11}{6},0)$ | ${\bf p}_{23}=(3,2,1)$
$S_{2}$ | ${\bf p}_{00}=(0,\frac{9}{8},-\frac{3}{4})$ | ${\bf p}_{01}=(\frac{7}{16},\frac{49}{40},-\frac{1}{5})$ | ${\bf p}_{02}=(\frac{31}{40},\frac{13}{10},\frac{11}{16})$ | ${\bf p}_{03}=(\frac{137}{128},\frac{879}{640},\frac{187}{160})$
| ${\bf p}_{04}=(\frac{11}{8},\frac{29}{20},\frac{3}{2})$ | ${\bf p}_{05}=(\frac{27}{16},\frac{25}{16},\frac{7}{4})$ | ${\bf p}_{10}=(\frac{7}{16},\frac{37}{40},-\frac{4}{5})$ | ${\bf p}_{11}=(\frac{157}{200},\frac{217}{200},-\frac{27}{50})$
| ${\bf p}_{12}=(\frac{3367}{3200},\frac{3901}{3200},\frac{49}{800})$ | ${\bf p}_{13}=(\frac{2073}{1600},\frac{431}{320},\frac{13}{40})$ | ${\bf p}_{14}=(\frac{1251}{800},\frac{1177}{800},\frac{21}{40})$ | ${\bf p}_{15}=(\frac{37}{20},\frac{13}{8},\frac{7}{10})$
| ${\bf p}_{20}=(\frac{3}{4},\frac{3}{4},-\frac{81}{80})$ | ${\bf p}_{21}=(\frac{3287}{3200},\frac{3053}{3200},-\frac{679}{800})$ | ${\bf p}_{22}=(\frac{199}{160},\frac{181}{160},-\frac{163}{400})$ | ${\bf p}_{23}=(\frac{4659}{3200},\frac{4149}{3200},-\frac{223}{800})$
| ${\bf p}_{24}=(\frac{171}{100},\frac{29}{20},-\frac{59}{400})$ | ${\bf p}_{25}=(\frac{1277}{640},\frac{1039}{640},\frac{3}{160})$ | ${\bf p}_{30}=(\frac{637}{640},\frac{351}{640},-\frac{189}{160})$ | ${\bf p}_{31}=(\frac{1957}{1600},\frac{251}{320},-\frac{197}{200})$
| ${\bf p}_{32}=(\frac{903}{640},\frac{3173}{3200},-\frac{99}{160})$ | ${\bf p}_{33}=(\frac{517}{320},\frac{1887}{1600},-\frac{14}{25})$ | ${\bf p}_{34}=(\frac{6023}{3200},\frac{4301}{3200},-\frac{343}{800})$ | ${\bf p}_{35}=(\frac{2703}{320},\frac{97}{64},-\frac{7}{40})$
| ${\bf p}_{40}=(\frac{99}{80},\frac{23}{80},-\frac{3}{4})$ | ${\bf p}_{41}=(\frac{1149}{800},\frac{439}{800},-\frac{101}{200})$ | ${\bf p}_{42}=(\frac{647}{400},\frac{311}{400},-\frac{87}{400})$ | ${\bf p}_{43}=(\frac{5887}{3200},\frac{125}{128},-\frac{183}{800})$
| ${\bf p}_{44}=(\frac{859}{400},\frac{91}{80},-\frac{7}{100})$ | ${\bf p}_{45}=(\frac{101}{40},\frac{103}{80},\frac{7}{20})$ | ${\bf p}_{50}=(\frac{3}{2},0,0)$ | ${\bf p}_{51}=(\frac{27}{16},\frac{23}{80},\frac{3}{20})$
| ${\bf p}_{52}=(\frac{241}{128},\frac{343}{640},\frac{7}{32})$ | ${\bf p}_{53}=(\frac{687}{320},\frac{237}{320},\frac{1}{40})$ | ${\bf p}_{54}=(\frac{101}{40},\frac{71}{80},\frac{3}{20})$ | ${\bf p}_{55}=(3,1,\frac{3}{4})$

###### Example 4

We test for coincidence the irreducible surfaces $S_{1}$ and $S_{2}$ of degree
$(2,2)$ and $(4,4)$, respectively. Their control points are shown in Table 3.
The corresponding vectors $\bm{\rho},\bm{\rho}^{1,0},\bm{\rho}^{0,1}$ are
coplanar and hence, matrix $M$, defined by (25) has rank 2. We apply Algorithm
2 and obtain the following two solutions
$(a_{1},a_{2},b_{1},b_{2},c_{1},c_{2},d_{1},d_{2})$ to system (23),

$\begin{array}[]{ll}&(-1,1/3,4/3,1/2,3/4,3/2,-1/4,13/12),\\\
&{\small(34/71,271/183,75/284,-181/549,-291/284,15/122,-277/568,329/366).}\end{array}$

The first of these solutions generates TPB surface whose control polygon
coincides with the control polygon of $S_{2}$. Hence, $S_{1}$ and $S_{2}$ have
coincidence. Surfaces $S_{1}$, $S_{2}$, and their coincident part $S$ are
shown in Fig. 5 The control points of $S$ are shown in Table 3.

a.

b.

c.

Figure 5: The irreducible TPB surfaces $S_{1}$ of degree $(2,2)$ and $S_{2}$
of degree $(4,4)$ and their coincident part $S$ from Example 4. The
corresponding control points are shown in Table 3. a. Surface $S_{1}$; b.
Surface $S_{2}$; c. Surfaces $S_{1}$, $S_{2}$, and $S$ which is shown with its
control polygon.

Table 3:  The control points of irreducible TPB surfaces of degree $(2,2)$ and $(4,4)$ from Example 4 $S_{1}$ | ${\bf p}_{00}=(0,0,0)$ | ${\bf p}_{01}=(1,0,1)$ | ${\bf p}_{02}=(2,0,\frac{3}{4})$ |
---|---|---|---|---
| ${\bf p}_{10}=(0,\frac{7}{10},-\frac{1}{2})$ | ${\bf p}_{11}=(1,1,0)$ | ${\bf p}_{12}=(2,1,\frac{6}{5})$ |
| ${\bf p}_{20}=(0,2,-\frac{4}{5})$ | ${\bf p}_{21}=(1,1,1)$ | ${\bf p}_{22}=(2,2,\frac{3}{4})$ |
$S_{2}$ | ${\bf p}_{00}=(\frac{2}{3},-\frac{86}{45},\frac{95}{36})$ | ${\bf p}_{01}=(\frac{25}{24},-\frac{35}{18},\frac{409}{180})$ | ${\bf p}_{02}=(\frac{17}{12},-\frac{121}{90},\frac{5951}{5760})$ | ${\bf p}_{03}=(\frac{43}{24},-\frac{10109}{11520},\frac{8609}{23040})$
| ${\bf p}_{04}=(\frac{13}{6},-\frac{1123}{2304},\frac{5957}{23040})$ | ${\bf p}_{10}=(\frac{3}{4},-\frac{85}{108},\frac{2027}{2160})$ | ${\bf p}_{11}=(\frac{37}{32},-\frac{93}{160},\frac{9631}{11520})$ | ${\bf p}_{12}=(\frac{25}{16},-\frac{5743}{17280},\frac{9151}{17280})$
| ${\bf p}_{13}=(\frac{63}{32},-\frac{23423}{138240}),\frac{116701}{276480})$ | ${\bf p}_{14}=(\frac{19}{8},\frac{53}{7680},\frac{23203}{46080})$ | ${\bf p}_{20}=(\frac{5}{6},\frac{1051}{2430},-\frac{1273}{38880})$ | ${\bf p}_{21}=(\frac{61}{48},\frac{87029}{155520},\frac{89543}{311040})$
| ${\bf p}_{22}=(\frac{41}{24},\frac{427381}{933120},\frac{1410439}{1866240})$ | ${\bf p}_{23}=(\frac{103}{48},\frac{3137}{7680},\frac{5157}{5120})$ | ${\bf p}_{24}=(\frac{31}{12},\frac{1151}{2560},\frac{154297}{138240})$ | ${\bf p}_{30}=(\frac{11}{12},\frac{317}{240},\frac{101}{2160})$
| ${\bf p}_{31}=(\frac{133}{96},\frac{5191}{4320},\frac{22847}{34560})$ | ${\bf p}_{32}=(\frac{89}{48},\frac{108571}{103680},\frac{18113}{13824})$ | ${\bf p}_{33}=(\frac{223}{96},\frac{5179}{5120},\frac{150163}{92160})$ | ${\bf p}_{34}=(\frac{67}{24},\frac{259}{256},\frac{12917}{7680})$
| ${\bf p}_{40}=(1,\frac{83}{45},\frac{63}{80})$ | ${\bf p}_{41}=(\frac{3}{2},\frac{947}{576},\frac{5461}{5760})$ | ${\bf p}_{42}=(2,\frac{12431}{5760},\frac{18029}{34560})$ | ${\bf p}_{43}=(\frac{5}{2},\frac{4631}{1920},\frac{2587}{3840})$
| ${\bf p}_{44}=(3,\frac{741}{320},\frac{621}{640})$ |  |  |
$S$ | ${\bf p}_{00}=(\frac{17}{21},0,\frac{4267}{7056})$ | ${\bf p}_{01}=(\frac{31}{28},0,\frac{10609}{14112})$ | ${\bf p}_{02}=(\frac{59}{42},0,\frac{34927}{42336})$ | ${\bf p}_{03}=(\frac{143}{84},0,\frac{277}{336})$
| ${\bf p}_{04}=(2,0,\frac{3}{4})$ | ${\bf p}_{10}=(\frac{71}{84},\frac{1051}{2352},\frac{11633}{35280})$ | ${\bf p}_{11}=(\frac{127}{112},\frac{2227}{4704},\frac{71797}{141120})$ | ${\bf p}_{12}=(\frac{239}{168},\frac{6931}{14112},\frac{143093}{211680})$
| ${\bf p}_{13}=(\frac{575}{336},\frac{1}{2},\frac{5587}{6720})$ | ${\bf p}_{14}=(2,\frac{1}{2},\frac{39}{40})$ | ${\bf p}_{20}=(\frac{37}{42},\frac{4537}{5292},\frac{9115}{42336})$ | ${\bf p}_{21}=(\frac{65}{56},\frac{1163}{1323},\frac{182957}{423360})$
| ${\bf p}_{22}=(\frac{121}{84},\frac{28897}{31752},\frac{817367}{1270080})$ | ${\bf p}_{23}=(\frac{289}{168},\frac{479}{504},\frac{8563}{10080})$ | ${\bf p}_{24}=(2,1,\frac{21}{20})$ | ${\bf p}_{30}=(\frac{11}{12},\frac{109}{90},\frac{103}{392})$
| ${\bf p}_{31}=(\frac{19}{16},\frac{6127}{5040},\frac{4673}{9408})$ | ${\bf p}_{32}=(\frac{35}{24},\frac{4783}{3780},\frac{24463}{35280})$ | ${\bf p}_{33}=(\frac{83}{48},\frac{457}{336},\frac{5731}{6720})$ | ${\bf p}_{34}=(2,\frac{3}{2},\frac{39}{40})$
| ${\bf p}_{40}=(\frac{20}{21},\frac{662}{441},\frac{991}{2205})$ | ${\bf p}_{41}=(\frac{17}{14},\frac{1313}{882},\frac{5867}{8820})$ | ${\bf p}_{42}=(\frac{31}{21},\frac{2074}{1323},\frac{41659}{52920})$ | ${\bf p}_{43}=(\frac{73}{42},\frac{73}{42},\frac{137}{168})$
| ${\bf p}_{44}=(2,2,\frac{3}{4})$ |  |  |

###### Example 5

In our final example we test for coincidence the irreducible surfaces $S_{1}$
and $S_{2}$ of degree $(2,4)$ and $(6,6)$, respectively. Their control points
are shown in Table 4. Surfaces $S_{1}$ and $S_{2}$ are shown in Fig. 6a. and
Fig. 6b.. The corresponding system (22) has a unique solution
$(a_{1},a_{2},b_{1},b_{2},c_{1},c_{2},d_{1},d_{2})$=$(1/2,-1/2,0,1/3,1/2,7/6,-1,2/3)$.
The shared domain of $S_{1}$ and $S_{2}$ is a hexagon. We represent the
coincident part $S$ as a union of two TPB surfaces and compute their control
points using blossoming, see Fig 6c.

a.

b.

c.

Figure 6: a. Irreducible TPB surfaces $S_{1}$ of degree $(2,4)$ and $S_{2}$ of degree $(6,6)$ from Example 5. The control points of $S_{1}$ and $S_{2}$ are shown in Table 3. a. $S_{1}$; b. $S_{1}$ and $S_{2}$ with its control polygon; c. The coincident part $S$ is presented as two TPB surfaces. Table 4:  The control points of irreducible TPB surfaces of degree $(2,4)$ and $(6,6)$ from Example 5 $S_{1}$ | ${\bf p}_{00}=(0,0,0)$ | ${\bf p}_{01}=(0,\frac{7}{10},-\frac{1}{2})$ | ${\bf p}_{02}=(0,2,-\frac{4}{5})$ | ${\bf p}_{03}=(0,\frac{23}{10},-\frac{4}{5})$
---|---|---|---|---
| ${\bf p}_{04}=(0,3,1)$ | ${\bf p}_{10}=(1,0,1)$ | ${\bf p}_{11}=(1,1,0)$ | ${\bf p}_{12}=(1,1,1)$
| ${\bf p}_{13}=(1,\frac{6}{5},\frac{6}{5})$ | ${\bf p}_{14}=(1,\frac{3}{2},\frac{4}{3})$ | ${\bf p}_{20}=(2,0,\frac{3}{4})$ | ${\bf p}_{21}=(2,1,\frac{6}{5})$
| ${\bf p}_{22}=(2,2,\frac{3}{4})$ | ${\bf p}_{23}=(2,3,1)$ | ${\bf p}_{24}=(2,4,\frac{3}{2})$ |
$S_{2}$ | ${\bf p}_{00}=(1,-\frac{79}{32},\frac{2717}{768})$ | ${\bf p}_{01}=(\frac{7}{6},-\frac{4151}{2880},\frac{19667}{17280})$ | ${\bf p}_{02}=(\frac{4}{3},-\frac{277}{1800},\frac{4481}{14400})$ | ${\bf p}_{03}=(\frac{3}{2},\frac{1361}{3600},\frac{44467}{64800})$
| ${\bf p}_{04}=(\frac{5}{3},\frac{5447}{6075},\frac{255913}{291600})$ | ${\bf p}_{05}=(\frac{11}{6},\frac{1991}{1215},\frac{26399}{29160})$ | ${\bf p}_{06}=(2,\frac{8}{3},\frac{1687}{1620})$ | ${\bf p}_{10}=(\frac{5}{6},-\frac{3973}{2880},\frac{4081}{1728})$
| ${\bf p}_{11}=(1,-\frac{3143}{4320},\frac{191717}{207360})$ | ${\bf p}_{12}=(\frac{7}{6},\frac{2489}{8640},\frac{250213}{777600})$ | ${\bf p}_{13}=(\frac{4}{3},\frac{9049}{12150},\frac{1379747}{2332800})$ | ${\bf p}_{14}=(\frac{3}{2},\frac{175433}{145800},\frac{668537}{874800})$
| ${\bf p}_{15}=(\frac{5}{3},\frac{13499}{7290},\frac{307297}{349920})$ | ${\bf p}_{16}=(\frac{11}{6},\frac{3341}{1215},\frac{32099}{29160})$ | ${\bf p}_{20}=(\frac{2}{3},-\frac{2269}{3600},\frac{22961}{21600})$ | ${\bf p}_{21}=(\frac{5}{6},-\frac{1883}{14400},\frac{157141}{388800})$
| ${\bf p}_{22}=(1,\frac{26249}{38880},\frac{2976581}{23328000})$ | ${\bf p}_{23}=(\frac{7}{6},\frac{2027447}{1944000},\frac{1061101}{2332800})$ | ${\bf p}_{24}=(\frac{4}{3},\frac{520417}{364500},\frac{6107587}{8748000})$ | ${\bf p}_{25}=(\frac{3}{2},\frac{96541}{48600},\frac{264529}{291600})$
| ${\bf p}_{26}=(\frac{5}{3},\frac{5609}{2025},\frac{115331}{97200})$ | ${\bf p}_{30}=(\frac{1}{2},-\frac{203}{900},\frac{14257}{32400})$ | ${\bf p}_{31}=(\frac{2}{3},\frac{55237}{194400},\frac{96383}{583200})$ | ${\bf p}_{32}=(\frac{5}{6},\frac{1863737}{1944000},\frac{17473}{233280})$
| ${\bf p}_{33}=(1,\frac{272407}{216000},\frac{4416611}{10368000})$ | ${\bf p}_{34}=(\frac{7}{6},\frac{3084847}{1944000},\frac{1652957}{2332800})$ | ${\bf p}_{35}=(\frac{4}{3},\frac{33577}{16200},\frac{27907}{28800})$ | ${\bf p}_{36}=(\frac{3}{2},\frac{89399}{32400},\frac{246491}{194400})$
| ${\bf p}_{40}=(\frac{1}{3},\frac{1819}{12150},\frac{18443}{145800})$ | ${\bf p}_{41}=(\frac{1}{2},\frac{12494}{18225},-\frac{1339}{437400})$ | ${\bf p}_{42}=(\frac{2}{3},\frac{904483}{729000},\frac{35749}{4374000})$ | ${\bf p}_{43}=(\frac{5}{6},\frac{318233}{216000},\frac{29029}{77760})$
| ${\bf p}_{44}=(1,\frac{1014119}{583200},\frac{48464383}{69984000})$ | ${\bf p}_{45}=(\frac{7}{6},\frac{100631}{46656},\frac{6996317}{6998400})$ | ${\bf p}_{46}=(\frac{4}{3},\frac{133901}{48600},\frac{1543601}{1166400})$ | ${\bf p}_{50}=(\frac{1}{6},\frac{2891}{4860},-\frac{1411}{7290})$
| ${\bf p}_{51}=(\frac{1}{3},\frac{1613}{1458},-\frac{42221}{174960})$ | ${\bf p}_{52}=(\frac{1}{2},\frac{37217}{24300},-\frac{18343}{145800})$ | ${\bf p}_{53}=(\frac{2}{3},\frac{328277}{194400},\frac{169903}{583200})$ | ${\bf p}_{54}=(\frac{5}{6},\frac{2213237}{1166400},\frac{2383159}{3499200})$
| ${\bf p}_{55}=(1,\frac{87773}{38880},\frac{1983853}{1866240})$ | ${\bf p}_{56}=(\frac{7}{6},\frac{8009}{2880},\frac{224443}{155520})$ | ${\bf p}_{60}=(0,\frac{17}{15},-\frac{203}{405})$ | ${\bf p}_{61}=(0,\frac{17}{15},-\frac{203}{405})$
| ${\bf p}_{62}=(\frac{1}{3},\frac{22679}{12150},-\frac{24437}{145800})$ | ${\bf p}_{63}=(\frac{1}{2},\frac{31721}{16200},\frac{34481}{97200})$ | ${\bf p}_{64}=(\frac{2}{3},\frac{206657}{97200},\frac{499307}{583200})$ | ${\bf p}_{65}=(\frac{5}{6},\frac{190249}{77760},\frac{62737}{46656})$
| ${\bf p}_{66}=(1,\frac{7553}{2592},\frac{112733}{62208})$ |  |  |

##  4 Conclusions and future work

In this paper we considered and solved the problem for testing TPB surfaces
for coincidence. We presented two different methods and develop two algorithms
based on these methods that test two irreducible TPB surfaces for coincidence
and report their coincident part if it is present. The first algorithm works
for surfaces of same degree $(m,n)$ and the second one - for surfaces of
degree $(m,n)$ and $(m+n,m+n)$, respectively. We presented numerical
experiments and gave examples to visualize and support the obtained results.
Our next task for future research is to develop and implement an algorithm for
testing TB surfaces for coincidence.

## Acknowledgments

This work was partially supported by Sofia University Science Fund Grant No.
80-10-103/2023.

## References

  * Barton and Zippel (1985) Barton, D., Zippel, R., 1985\.  Polynomial decomposition algorithms.  J. Symbolic Comput. 1, 159–168.  doi:10.1016/S0747-7171(85)80012-2.
  * Berry and Patterson (1997) Berry, T., Patterson, R., 1997\.  The uniqueness of Bézier control points.  Comput. Aided Geom. Des. 14, 877–879.  doi:10.1016/S0167-8396(97)00016-2.
  * Chen and Ma (2015) Chen, X.D., Ma, W., 2015.  Rebuttal to “comment on the ‘coincidence condition of two Bézier curves of an arbitrary degree’ ”.  Comput. Graph. 53, 167–169.  doi:https://doi.org/10.1016/j.cag.2015.10.007.
  * Chen et al. (2013) Chen, X.D., W. Ma, W., Deng, C., 2013.  Conditions for the coincidence of two quartic Bézier curves.  Appl. Math. and Comput. 225, 731–736.  doi:10.1016/j.amc.2013.09.053.
  * Chen et al. (2016) Chen, X.D., Yang, C., Ma, W., 2016.  Coincidence condition of two Bézier curves of an arbitrary degree.  Comput. Graph. 54, 121–126.  doi:10.1016/j.cag.2015.07.013.
  * Denker and Herron (1997) Denker, W., Herron, G., 1997\.  Generalizing rational degree elevation.  Comput. Aided Geom. Des. 14, 399–406.  doi:10.1016/S0167-8396(96)00036-2.
  * Farin (2002) Farin, G., 2002.  Curves and Surfaces for CAGD: A Practical Guide.  5th ed., Morgan-Kaufmann, San Francisco.
  * Farouki (2012) Farouki, R., 2012.  The Bernstein polynomial basis: a centennial retrospective.  Comput. Aided Geom. Des. 29, 379–419.  doi:10.1016/j.cagd.2012.03.001.
  * von zur Gathen (1990) von zur Gathen, J., 1990.  Functional decomposition of polynomials: the tame case.  J. Symbolic Comput. 9, 281–299.  doi:10.1016/S0747-7171(08)80014-4.
  * Goldman (2003) Goldman, R., 2003.  Pyramid algorithms: A dynamic programming approach to curves and surfaces for geometric modeling.  Elsevier Science (USA).
  * Kozen and Landau (1989) Kozen, D., Landau, S., 1989\.  Polynomial decomposition algorithms.  J. Symbolic Comput. 7, 445–456.  doi:https://doi.org/10.1016/S0747-7171(89)80027-6.
  * Pekerman et al. (2005) Pekerman, D., Seong, J.K., Elber, G., Kim, M.S., 2005\.  Are two curves the same?  Comput.-Aided Des. Appl. 2, 85–94.  doi:10.1080/16864360.2005.10738356.
  * S${\rm\acute{a}}$nchez-Reyes (2011) S${\rm\acute{a}}$nchez-Reyes, J., 2011.  On the conditions for the coincidence of two cubic Bézier curves.  J. of Comput. Appl. Math. 236, 1675–1677.  doi:10.1016/j.cam.2011.08.024.
  * S${\rm\acute{a}}$nchez-Reyes (2014) S${\rm\acute{a}}$nchez-Reyes, J., 2014.  The conditions for the coincidence or overlapping of two Bézier curves.  Appl. Math. Comput. 248, 625–630.  doi:10.1016/j.amc.2014.10.008.
  * S${\rm\acute{a}}$nchez-Reyes (2015a) S${\rm\acute{a}}$nchez-Reyes, J., 2015a.  Comment on the “coincidence condition of two Bézier curves of an arbitrary degree”.  Comput. Graph. 53, 166\.  doi:10.1016/j.cag.2015.10.006.
  * S${\rm\acute{a}}$nchez-Reyes (2015b) S${\rm\acute{a}}$nchez-Reyes, J., 2015b.  Detecting symmetries in polynomial Bézier curves.  J. of Comput. Appl. Math. 288, 274–283.  doi:10.1016/j.cam.2015.04.025.
  * Vlachkova (2017) Vlachkova, K., 2017.  Comparing Bézier curves and surfaces for coincidence, in: Georgiev, K., Todorov, M., Georgiev, I. (Eds.), Advanced Computing in Industrial Mathematics. Springer International Publishing. volume 681 of LNCS, Studies in Computational Intelligence, pp. 239–250.  doi:10.1007/978-3-319-49544-6_20.
  * W.-K. Wang et al. (2011) W.-K. Wang, W.K., Zhang, H., Liu, X.M., Paul, J.C., 2011\.  Conditions for coincidence of two cubic Bézier curves.  J. Comput. Appl. Math.. 235, 5198–5202.  doi:10.1016/j.cam.2011.05.006.
  * Yang and Zeng (2008) Yang, L.Q., Zeng, X.M., 2008\.  Trimming Bézier surfaces on Bézier surfaces via blossoming, in: Chen, F., J$\ddot{\rm u}$ttler, B. (Eds.), LNCS 4975, Springer, Berlin Heidelberg. pp. 578–584.  doi:10.1007/978-3-540-79246-8_50.