# Log-Aesthetic Curves for Shape Completion Problem

Authors: R. U. Gobithaasan; Yip Siew Wei; Kenjiro T. Miura
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

An object with complete boundary or silhouette is essential in various design and computer graphics feats. Due to various reasons, some parts of the object can be missing hence increasing the complexity in designing process. It is therefore important to reconstruct the missing parts of an object while retaining its aesthetic appearance. In this paper, we propose Log-Aestheic Curves (LAC) for shape completion problem. We propose an algorithm to construct LAC segment and subsequently fit into the gap of the missing parts with C-shape or S-shape. For C-shape completion, we define LAC segment by specifying two endpoints and their respective tangent directions between the gaps while, for S-shape, the user defines an inflection point in between the endpoints. The final section illustrates three examples to showcase the efficiency of the proposed algorithm. The results are further compared with Kimia’s method to prove that the algorithm produces equally good result. Additionally, the proposed algorithm provides an extra degree of freedom in which the user would be able to choose the type of spiral that they desire to solve the shape completion problem.


---

## Body

## 1. Introduction

In a design environment, there are situations in which the outlines of an object are missing or occluded. These scenarios are commonly known as shape completion, gap completion, or curve completion problem. It is important to recomplete the shape of the missing object while retaining its aesthetic appearance since a complete object can be used further for applications in modeling, mesh analysis, and computer-aided design as well as manufacturing purposes. The complete boundary or silhouette provides geometrical information of a model which is significant in engineering analysis and manufacturing process. In order to reconstruct the missing boundaries of an object, the associated curve segment must satisfy the boundary conditions so that the curve passes through the endpoints with specified tangent direction. To date, there are numbers of algorithms available for shape completion problem (see the works of [1–6]).A notable work which received much attention is by Kimia et al. [3], where they proposed an algorithm which utilizes Euler spiral to solve shape completion problem. Euler spiral is also known as Cornu’s spiral or clothoid. The Euler spiral is widely applied in highway/railway or robotic trajectories design due to its linear curvature property (curvature varies linearly with respect to arc length). The algorithm proposed by Kimia et al. [3] is the implementation of Euler spiral to solve the shape completion problem. In their proposed algorithm, two endpoints (P
0, P
2) and their tangential angles (θ
0, θ
2) are the inputs. In order to construct Euler spiral for the given problem, curvature and arc length of the curve are required to be identified. Since the proposed Euler spiral algorithm is an iterative process, initial guess for these two parameters (curvature and arc length) is needed. Kimia et al. [3] recommended the use of biarc to obtain the initial curve with its corresponding curvature and arc length for the proposed algorithm. Note that the goal of their proposed algorithm is to minimalize the distance between last point and resulting curve in order for the gap to be filled using gradient descent method.Log-Aesthetic Curves (LAC) are curves where the logarithmic curvature graph (LCG) can be represented by a straight line. The idea of LCG was formulated by Harada et al. (1999) when they attempted to classify all the curves used in automobile design. It was first known as logarithmic distribution diagram of curvature (LDDC). It is a graph to measure the relationship between curvature radius (denoted byρ) and arc length of the curve segment (denoted by s). They found that all the curves employed in automobile design depict linear gradient of LDDC. Kanaya et al. [7] refined the formulation of LDDC which is now known as LCG. The horizontal axis of LCG represents log
⁡
⁡
ρ and the vertical axis represents log
⁡
⁡
ρ
(
d
s
′
/
d
ρ
′
) [8]. Figure 1 illustrates the two segments of Euler spiral.Euler spiral defineds
∈
[
0.2,1
] (solid line) and s
∈
[
1,3
] (dotted) and its corresponding LCG.
(a)
Two segments of Euler spiral
(b)
Its corresponding logarithmic curvature graphIn 2005, Miura et al. [9] derived a fundamental formula of LAC based on a linear representation of LCG. A year later, Yoshida and Saito [10] investigated the characteristics and overall shape of LAC. They also proposed a method to construct LAC segment interactively by specifying endpoints and their tangent vectors. In 2009, they further extended LAC into space curve and proposed a method to interactively control the curves, which is similar to quadratic Bezier curves.LAC has become a promising curve in graphic and industrial design due to its monotonic curvature property. There are two shape parameters of LAC denoted byα and Λ. The shape parameter α is used to determine the type of spiral within the family of LAC, and Λ is used to satisfy the G
1 constraint during the design process. LAC comprises Euler spiral (α
=
-
1), Nielsen spiral (α
=
0), logarithmic or equiangular spiral (α
=
1), circle involute (α
=
2), and others.In 2011, Gobithaasan and Miura [11] expanded the family of LAC into Generalized Log-Aesthetic Curve (GLAC) by adding generalized Cornu spiral (GCS) to the family of LAC. This includes Euler spiral, logarithmic spiral, circle involute, Nielsen spiral, LAC, and GCS as the members of GLAC. To note, GCS is proposed by Ali et al. [12] where it becomes Euler spiral when the shape parameter of GCS is zero. GLAC has an extra shape parameter compared to LAC in which it can be used to satisfy additional constraints that occur during design process [13]. The curvature function of GLAC is also monotonic similar to LAC. In 2012, they further extended GLAC into space curve.In 2012, Ziatdinov et al. [14] defined LAC in the form of incomplete gamma functions. They claimed that this new expression of LAC is capable of reducing the computation time up to 13 times faster. In 2013, the problem of G
2 Hermite interpolation was dealt with by Miura and Gobithaasan [15] by introducing log-aesthetic splines which consists of triple LAC segments. Readers are referred to [16] for a detailed review on aesthetic curves.In this paper, we introduce the implementation ofG
1 LAC algorithm to fit the gap in between the outlines of missing/occlusion objects. We compare the performance of this algorithm with the results obtained by Kimia et al.’s [3] method on the same examples in order to show the effectiveness of LAC to solve shape completion problem.The rest of this paper is organized as follows. First, the formulation of LAC is reviewed followed by a detailed explanation on the LAC algorithm for solving the shape completion problem. In Section3, we demonstrate the implementation of the proposed algorithm with various α values with three examples to show the implementation of this method. The data and calculation used in the examples are also depicted in this section. The output of shape completion using Kimia’s method is also depicted for comparison purposes. We also make comparison of the results obtained using Kimia et al.’s [3] method and our algorithm. We further show some shape variations which can be obtained by using S-shape LAC in which the designer tweaks the segment in order to obtain the desired shape.


## 2. Log-Aesthetic Curves in Shape Completion

In this section, we show the parametric expression of LAC and the algorithm used to obtain the solution for shape completion problem with variousα values.


### 2.1. The Analytical Formulas and Parameters

There are two shape parameters used to define LAC segment:α and Λ. The shape parameter α determines the type of spiral and Λ is used to control the curve so that the constraints are satisfied. Let ρ and θ represent radius of curvature and tangent angle of the curve, respectively.Equation (1) shows the radius of curvature function in terms of its turning angle. To note, (1) is used to define the parametric expression of LAC in terms of its turning angle as shown in (2) as follows:
(1)
ρ
(
θ
)
=
{
e
Λ
θ
,
if
α
=
1
(
(
α
-
1
)
Λ
θ
+
1
)
1
/
(
α
-
1
)
,
otherwise
(2)
LAC
(
θ
)
=
P
a
+
∫
0
θ
e
i
u
ρ
(
u
)
d
u
,
where P
a represents starting point and i and e represent the imaginary unit and exponent, respectively. LAC can also be represented in the arc length parameter, s, as follows:
(3)
LAC
(
s
)
=
{
P
a
+
∫
0
s
e
i
(
(
1
/
Λ
)
(
1
-
e
-
Λ
u
)
)
d
u
,
if
α
=
0
P
a
+
∫
0
s
e
i
(
log
⁡
⁡
[
Λ
u
+
1
]
/
Λ
)
d
u
,
if
α
=
1
P
a
+
∫
0
s
e
i
(
(
(
Λ
α
u
+
1
)
(
α
-
1
)
/
α
-
1
)
/
Λ
(
α
-
1
)
)
d
u
,
otherwise
.
Both (2) and (3) generate the same LAC. The curve can be drawn in complex plane by the x-axis representing real numbers and the y-axis representing imaginary numbers. Readers are referred to [10] for a detailed derivation of the parametric expression of LAC.


### 2.2. The LAC Algorithm

C-Shape. We customize the algorithm of constructing LAC segment to fill the gap by specifying two endpoints, its tangent vector, and α value. The C-shape LAC curve is a direct process in which the user may interactively input the endpoints and the tangent direction of those points. We can further automate the identification of tangents at the endpoints by using three-point circular arc approximation around the endpoints as explained in Steps 1 and 2 in the algorithm below. Using these tangents, we may calculate the midpoint. These three points are then used to fit LAC segment in the gap for shape completion problem. The idea of this method is to find a LAC segment defined in a triangle composed of three control points as proposed by Yoshida and Saito [10]. Therefore, by using this method, it is only possible to generate a C-curve. Figures 2 and 3 show the configuration of the triangle formed by three control points for cases α
>
1 and α
≤
1, respectively. Step 5 in the algorithm below elaborates these configurations.The configuration of triangle consists of three control points for caseα
>
1. The curve inside the triangle represents the generated LAC segment.
(a)
Original position of control points
(b)
Position of control points after transformationThe configuration of triangle consists of three control points for caseα
≤
1. The curve inside the triangle represents the generated LAC segment.
(a)
Original position of control points
(b)
Position of control points after transformationS-Shape. Basically, a S-shape LAC segment consists of two C-shape curves joined with G
1 continuity. In order to construct the S-curve for a given gap, the inflection point is essential. A simple approach used is that users are given the freedom to define the inflection point so that the algorithm is carried out twice consisting of two C-shape segments of LAC. Thus, this approach needs two endpoints, its tangent vectors, α value, and an inflection point.The process involves breaking the S-curve into two C-curves so the first piece of curve is constructed between starting point (black) and inflection point (gray), while the second piece is between inflection point (gray) and endpoint (black). Figure4 illustrates the inflection point that we define for one of the numerical examples in this paper.Figure 4
The input for S-shape completion problem.Algorithm1 demonstrates the LAC algorithm.Algorithm 1
REMARK: Endpoints {
P
a
,
P
c
}, inflection point P
inflect and α are user defined. The tangent angle at both endpoints {
θ
0
,
θ
2
} can be
obtained either from three point circular arc approximation around the endpoints or the user defines it. Let(
X
,
Y
) represent the
coordinate of a point.
INPUT: P
a, P
c, P
inflect, α.
OUTPUT: θ
d, Λ, r
scale, LAC segment.
Begin
Step  1. Set f
(
t
)
←
{
h
+
r
cos
⁡
(
t
)
,
k
+
r
sin
⁡
⁡
(
t
)
}, where (
h
,
k
) is the center of circle, r is radius and t represents angle.
Step  2. Identify unit tangent vector, UTV
(
t
)
←
f
′
(
t
)
/
∥
f
′
(
t
)
∥ and set (
X
new
,
Y
new
)
←
(
X
,
Y
)
+
UTV
(
t
).
Step  3. Calculate directional angle, θ
←
tan
-
1
⁡
(
(
Y
new
-
Y
)
/
(
X
new
-
X
)
).
Step  4. Solve simultaneous equations Y
=
m
X
+
c, where m
←
(
Y
new
-
Y
)
/
(
X
new
-
X
) to get position of second control point P
b.
Step  5. If ∥
P
a
P
b
∥
≤
∥
P
b
P
c
∥, then P
a
←
P
a
;
P
c
←
P
c,
elseP
a
←
P
c; P
c
←
P
a.
Ifα
>
1, then P
start
←
P
c; P
end
←
P
a,
else P
start
←
P
a; P
end
←
P
c.
Step  6. Translate P
start
=
(
0,0
), rotate triangle such that P
b
=
(
-
X
,
0
) for α
>
1; P
b
=
(
X
,
0
) for α
≤
1.
IfP
end
=
(
X
,
-
Y
) or P
end
=
(
-
X
,
-
Y
), then reflect the triangle through x-axis.
Step  7. Compute θ
d
←
π
-
cos
⁡
-
1
⁡
(
(
-
∥
P
a
P
c
∥
2
+
∥
P
b
P
c
∥
2
+
∥
P
a
P
b
∥
2
)
/
(
2
∥
P
b
P
c
∥
∥
P
a
P
b
∥
)
).
Step  8. If α
>
1, then θ
f
←
cos
⁡
-
1
⁡
(
(
-
∥
P
a
P
b
∥
2
+
∥
P
b
P
c
∥
2
+
∥
P
a
P
c
∥
2
)
/
(
2
∥
P
a
P
c
∥
∥
P
b
P
c
∥
)
),
elseθ
e
←
cos
-
1
⁡
(
(
-
∥
P
b
P
c
∥
2
+
∥
P
a
P
b
∥
2
+
∥
P
a
P
c
∥
2
)
/
(
2
∥
P
a
P
b
∥
∥
P
a
P
c
∥
)
).
Step  9. Identify bound of Λ. If α
<
1, then a
←
1
×
10
-
10; b
←
1
/
(
θ
d
(
1
-
α
)
),
else ifα
>
1, then a
←
1
×
10
-
10; b
←
1
/
(
θ
d
(
α
-
1
)
),
elsea
←
1
×
10
-
10; b
←
1
×
10
5.
Step  10. Set tolerance Tol
←
10
-
10;
iteration numberN
←
(
1
/
In
⁡
2
)
In
⁡
(
∣
a
-
b
∣
/
Tol
).
Step  11. Calculate Λ using Bisection method.
Step  12. Determine scaling factor, r
scale
←
∥
P
a
P
c
∥
/
∥
P
0
P
2
∥.
Step  13. Scale r
scale to the curve and transform inversely the triangle to its original position.
Step  14. Construct LAC segment using (2).
Step  15. OUTPUT (θ
d, Λ, r
scale, LAC segment).
End


#### 2.2.1. Computation of Tangent Angles (Step 1–Step 3)

To automate the process of defining the tangents at the endpoints, we may use circular arc approximation (osculating circle) that best fits the endpoints and points surrounding them in order to determine the tangent angle at both endpoints. Since it is an osculating circle, we substitute the points into the equation of circle. Then, we identify the center (h
,
k), radius r, and turning angle t of circle from three points which include the endpoint. Next, we determine the unit tangent vector at the endpoints and subsequently calculate the corresponding tangent angle by using specified formula as indicated in the algorithm. Alternately, we may also allow the user to directly define tangent vectors at those points.


#### 2.2.2. Identification of Second Control Point (Step 4)

Once the unit tangent vector at endpoints is identified, we determine the coordinate of the second control pointP
b which is the intersection point of the tangential line at both endpoints by solving the equations simultaneously.


#### 2.2.3. Affirmation of Initial and Last Point Position (Step 5)

We assume the distance betweenP
a and P
b is less than P
b and P
c as proposed by Yoshida and Saito [10]. The position of P
a and P
c is switched if the criterion is not satisfied. Otherwise, the position remains unchanged. Note that there are two cases of constructing LAC segment based on the α value as illustrated in Figures 2 and 3. For case α
≤
1, the initial endpoint P
a is the starting point during the curve construction process P
start. On the other hand, starting point of curve construction process for case α
>
1 is the last endpoint P
c.


#### 2.2.4. Transformation Process (Step 6)

The transformation process includes translation, rotation, and reflection of the original triangle that consist ofP
a, P
b, P
c. Initially, the original triangle is translated to the origin so that the starting point P
start is located at the origin. Next, we rotate the triangle so that the second control point is placed on the x-axis. Finally, we ensure the last point of the curve construction process P
end is located at the positive y-axis region. If not, the reflection process is needed to reflect the last point with negative y-coordinate through the x-axis. The configuration after transformation is illustrated in Figures 2 and 3.


#### 2.2.5. Computation of Tangent and Turning Angle (Step 7 and Step 8)

We apply the law of cosine of a triangle to calculate corresponding angles as shown in Figures2 and 3. The tangent angle θ
d and turning angle θ
e for case α
≤
1 or θ
f for case α
>
1 will be used in the subsequent step for calculating shape parameter Λ.


#### 2.2.6. Upper Bound of Shape ParameterΛ (Step 9)

For the case whenα
=
1, there is no upper bound for shape parameter Λ. So, the value of Λ can be arbitrarily large. However, there are upper bounds for Λ when α
<
1 and α
>
1. Therefore, the Λ value of these two cases is restricted within the range of (a
,
b) where a and b are assigned a specified value as indicated in the algorithm above.


#### 2.2.7. Shape ParameterΛ Calculation (Step 10 and Step 11)

We determine theΛ value that satisfies the constraints of endpoints and angles by using bisection method. First, tolerance and bound of Λ are used in the calculation of iteration number for bisection method. Then, the calculating process will run until the iteration number is met. Once the Λ value of the curve is obtained, it is an interpolating curve that satisfies boundary constraints as shape parameter Λ is used to control the curve so that the constraints are satisfied. The obtained Λ value ensures the generated LAC segment starts at the starting point and ends at the last point while the shape of curve follows the specified tangent vectors at two endpoints.


#### 2.2.8. Computation of Scale Factor (Step 12)

We calculate the scaling factor by using the formula as shown in the algorithm whereP
a and P
c are endpoints of the original triangle while P
0 and P
2 are endpoints of the transformed triangle.


#### 2.2.9. Construction of LAC Segment (Step 13–Step 15)

In order to obtain the curve which is defined in the original triangle, we inversely transform the triangle to its original position. The curve segment is constructed using (2) with the obtained value of Λ, θ
d, r
scale.


## 2.1. The Analytical Formulas and Parameters

There are two shape parameters used to define LAC segment:α and Λ. The shape parameter α determines the type of spiral and Λ is used to control the curve so that the constraints are satisfied. Let ρ and θ represent radius of curvature and tangent angle of the curve, respectively.Equation (1) shows the radius of curvature function in terms of its turning angle. To note, (1) is used to define the parametric expression of LAC in terms of its turning angle as shown in (2) as follows:
(1)
ρ
(
θ
)
=
{
e
Λ
θ
,
if
α
=
1
(
(
α
-
1
)
Λ
θ
+
1
)
1
/
(
α
-
1
)
,
otherwise
(2)
LAC
(
θ
)
=
P
a
+
∫
0
θ
e
i
u
ρ
(
u
)
d
u
,
where P
a represents starting point and i and e represent the imaginary unit and exponent, respectively. LAC can also be represented in the arc length parameter, s, as follows:
(3)
LAC
(
s
)
=
{
P
a
+
∫
0
s
e
i
(
(
1
/
Λ
)
(
1
-
e
-
Λ
u
)
)
d
u
,
if
α
=
0
P
a
+
∫
0
s
e
i
(
log
⁡
⁡
[
Λ
u
+
1
]
/
Λ
)
d
u
,
if
α
=
1
P
a
+
∫
0
s
e
i
(
(
(
Λ
α
u
+
1
)
(
α
-
1
)
/
α
-
1
)
/
Λ
(
α
-
1
)
)
d
u
,
otherwise
.
Both (2) and (3) generate the same LAC. The curve can be drawn in complex plane by the x-axis representing real numbers and the y-axis representing imaginary numbers. Readers are referred to [10] for a detailed derivation of the parametric expression of LAC.


## 2.2. The LAC Algorithm

C-Shape. We customize the algorithm of constructing LAC segment to fill the gap by specifying two endpoints, its tangent vector, and α value. The C-shape LAC curve is a direct process in which the user may interactively input the endpoints and the tangent direction of those points. We can further automate the identification of tangents at the endpoints by using three-point circular arc approximation around the endpoints as explained in Steps 1 and 2 in the algorithm below. Using these tangents, we may calculate the midpoint. These three points are then used to fit LAC segment in the gap for shape completion problem. The idea of this method is to find a LAC segment defined in a triangle composed of three control points as proposed by Yoshida and Saito [10]. Therefore, by using this method, it is only possible to generate a C-curve. Figures 2 and 3 show the configuration of the triangle formed by three control points for cases α
>
1 and α
≤
1, respectively. Step 5 in the algorithm below elaborates these configurations.The configuration of triangle consists of three control points for caseα
>
1. The curve inside the triangle represents the generated LAC segment.
(a)
Original position of control points
(b)
Position of control points after transformationThe configuration of triangle consists of three control points for caseα
≤
1. The curve inside the triangle represents the generated LAC segment.
(a)
Original position of control points
(b)
Position of control points after transformationS-Shape. Basically, a S-shape LAC segment consists of two C-shape curves joined with G
1 continuity. In order to construct the S-curve for a given gap, the inflection point is essential. A simple approach used is that users are given the freedom to define the inflection point so that the algorithm is carried out twice consisting of two C-shape segments of LAC. Thus, this approach needs two endpoints, its tangent vectors, α value, and an inflection point.The process involves breaking the S-curve into two C-curves so the first piece of curve is constructed between starting point (black) and inflection point (gray), while the second piece is between inflection point (gray) and endpoint (black). Figure4 illustrates the inflection point that we define for one of the numerical examples in this paper.Figure 4
The input for S-shape completion problem.Algorithm1 demonstrates the LAC algorithm.Algorithm 1
REMARK: Endpoints {
P
a
,
P
c
}, inflection point P
inflect and α are user defined. The tangent angle at both endpoints {
θ
0
,
θ
2
} can be
obtained either from three point circular arc approximation around the endpoints or the user defines it. Let(
X
,
Y
) represent the
coordinate of a point.
INPUT: P
a, P
c, P
inflect, α.
OUTPUT: θ
d, Λ, r
scale, LAC segment.
Begin
Step  1. Set f
(
t
)
←
{
h
+
r
cos
⁡
(
t
)
,
k
+
r
sin
⁡
⁡
(
t
)
}, where (
h
,
k
) is the center of circle, r is radius and t represents angle.
Step  2. Identify unit tangent vector, UTV
(
t
)
←
f
′
(
t
)
/
∥
f
′
(
t
)
∥ and set (
X
new
,
Y
new
)
←
(
X
,
Y
)
+
UTV
(
t
).
Step  3. Calculate directional angle, θ
←
tan
-
1
⁡
(
(
Y
new
-
Y
)
/
(
X
new
-
X
)
).
Step  4. Solve simultaneous equations Y
=
m
X
+
c, where m
←
(
Y
new
-
Y
)
/
(
X
new
-
X
) to get position of second control point P
b.
Step  5. If ∥
P
a
P
b
∥
≤
∥
P
b
P
c
∥, then P
a
←
P
a
;
P
c
←
P
c,
elseP
a
←
P
c; P
c
←
P
a.
Ifα
>
1, then P
start
←
P
c; P
end
←
P
a,
else P
start
←
P
a; P
end
←
P
c.
Step  6. Translate P
start
=
(
0,0
), rotate triangle such that P
b
=
(
-
X
,
0
) for α
>
1; P
b
=
(
X
,
0
) for α
≤
1.
IfP
end
=
(
X
,
-
Y
) or P
end
=
(
-
X
,
-
Y
), then reflect the triangle through x-axis.
Step  7. Compute θ
d
←
π
-
cos
⁡
-
1
⁡
(
(
-
∥
P
a
P
c
∥
2
+
∥
P
b
P
c
∥
2
+
∥
P
a
P
b
∥
2
)
/
(
2
∥
P
b
P
c
∥
∥
P
a
P
b
∥
)
).
Step  8. If α
>
1, then θ
f
←
cos
⁡
-
1
⁡
(
(
-
∥
P
a
P
b
∥
2
+
∥
P
b
P
c
∥
2
+
∥
P
a
P
c
∥
2
)
/
(
2
∥
P
a
P
c
∥
∥
P
b
P
c
∥
)
),
elseθ
e
←
cos
-
1
⁡
(
(
-
∥
P
b
P
c
∥
2
+
∥
P
a
P
b
∥
2
+
∥
P
a
P
c
∥
2
)
/
(
2
∥
P
a
P
b
∥
∥
P
a
P
c
∥
)
).
Step  9. Identify bound of Λ. If α
<
1, then a
←
1
×
10
-
10; b
←
1
/
(
θ
d
(
1
-
α
)
),
else ifα
>
1, then a
←
1
×
10
-
10; b
←
1
/
(
θ
d
(
α
-
1
)
),
elsea
←
1
×
10
-
10; b
←
1
×
10
5.
Step  10. Set tolerance Tol
←
10
-
10;
iteration numberN
←
(
1
/
In
⁡
2
)
In
⁡
(
∣
a
-
b
∣
/
Tol
).
Step  11. Calculate Λ using Bisection method.
Step  12. Determine scaling factor, r
scale
←
∥
P
a
P
c
∥
/
∥
P
0
P
2
∥.
Step  13. Scale r
scale to the curve and transform inversely the triangle to its original position.
Step  14. Construct LAC segment using (2).
Step  15. OUTPUT (θ
d, Λ, r
scale, LAC segment).
End


### 2.2.1. Computation of Tangent Angles (Step 1–Step 3)

To automate the process of defining the tangents at the endpoints, we may use circular arc approximation (osculating circle) that best fits the endpoints and points surrounding them in order to determine the tangent angle at both endpoints. Since it is an osculating circle, we substitute the points into the equation of circle. Then, we identify the center (h
,
k), radius r, and turning angle t of circle from three points which include the endpoint. Next, we determine the unit tangent vector at the endpoints and subsequently calculate the corresponding tangent angle by using specified formula as indicated in the algorithm. Alternately, we may also allow the user to directly define tangent vectors at those points.


### 2.2.2. Identification of Second Control Point (Step 4)

Once the unit tangent vector at endpoints is identified, we determine the coordinate of the second control pointP
b which is the intersection point of the tangential line at both endpoints by solving the equations simultaneously.


### 2.2.3. Affirmation of Initial and Last Point Position (Step 5)

We assume the distance betweenP
a and P
b is less than P
b and P
c as proposed by Yoshida and Saito [10]. The position of P
a and P
c is switched if the criterion is not satisfied. Otherwise, the position remains unchanged. Note that there are two cases of constructing LAC segment based on the α value as illustrated in Figures 2 and 3. For case α
≤
1, the initial endpoint P
a is the starting point during the curve construction process P
start. On the other hand, starting point of curve construction process for case α
>
1 is the last endpoint P
c.


### 2.2.4. Transformation Process (Step 6)

The transformation process includes translation, rotation, and reflection of the original triangle that consist ofP
a, P
b, P
c. Initially, the original triangle is translated to the origin so that the starting point P
start is located at the origin. Next, we rotate the triangle so that the second control point is placed on the x-axis. Finally, we ensure the last point of the curve construction process P
end is located at the positive y-axis region. If not, the reflection process is needed to reflect the last point with negative y-coordinate through the x-axis. The configuration after transformation is illustrated in Figures 2 and 3.


### 2.2.5. Computation of Tangent and Turning Angle (Step 7 and Step 8)

We apply the law of cosine of a triangle to calculate corresponding angles as shown in Figures2 and 3. The tangent angle θ
d and turning angle θ
e for case α
≤
1 or θ
f for case α
>
1 will be used in the subsequent step for calculating shape parameter Λ.


### 2.2.6. Upper Bound of Shape ParameterΛ (Step 9)

For the case whenα
=
1, there is no upper bound for shape parameter Λ. So, the value of Λ can be arbitrarily large. However, there are upper bounds for Λ when α
<
1 and α
>
1. Therefore, the Λ value of these two cases is restricted within the range of (a
,
b) where a and b are assigned a specified value as indicated in the algorithm above.


### 2.2.7. Shape ParameterΛ Calculation (Step 10 and Step 11)

We determine theΛ value that satisfies the constraints of endpoints and angles by using bisection method. First, tolerance and bound of Λ are used in the calculation of iteration number for bisection method. Then, the calculating process will run until the iteration number is met. Once the Λ value of the curve is obtained, it is an interpolating curve that satisfies boundary constraints as shape parameter Λ is used to control the curve so that the constraints are satisfied. The obtained Λ value ensures the generated LAC segment starts at the starting point and ends at the last point while the shape of curve follows the specified tangent vectors at two endpoints.


### 2.2.8. Computation of Scale Factor (Step 12)

We calculate the scaling factor by using the formula as shown in the algorithm whereP
a and P
c are endpoints of the original triangle while P
0 and P
2 are endpoints of the transformed triangle.


### 2.2.9. Construction of LAC Segment (Step 13–Step 15)

In order to obtain the curve which is defined in the original triangle, we inversely transform the triangle to its original position. The curve segment is constructed using (2) with the obtained value of Λ, θ
d, r
scale.


## 2.2.1. Computation of Tangent Angles (Step 1–Step 3)

To automate the process of defining the tangents at the endpoints, we may use circular arc approximation (osculating circle) that best fits the endpoints and points surrounding them in order to determine the tangent angle at both endpoints. Since it is an osculating circle, we substitute the points into the equation of circle. Then, we identify the center (h
,
k), radius r, and turning angle t of circle from three points which include the endpoint. Next, we determine the unit tangent vector at the endpoints and subsequently calculate the corresponding tangent angle by using specified formula as indicated in the algorithm. Alternately, we may also allow the user to directly define tangent vectors at those points.


## 2.2.2. Identification of Second Control Point (Step 4)

Once the unit tangent vector at endpoints is identified, we determine the coordinate of the second control pointP
b which is the intersection point of the tangential line at both endpoints by solving the equations simultaneously.


## 2.2.3. Affirmation of Initial and Last Point Position (Step 5)

We assume the distance betweenP
a and P
b is less than P
b and P
c as proposed by Yoshida and Saito [10]. The position of P
a and P
c is switched if the criterion is not satisfied. Otherwise, the position remains unchanged. Note that there are two cases of constructing LAC segment based on the α value as illustrated in Figures 2 and 3. For case α
≤
1, the initial endpoint P
a is the starting point during the curve construction process P
start. On the other hand, starting point of curve construction process for case α
>
1 is the last endpoint P
c.


## 2.2.4. Transformation Process (Step 6)

The transformation process includes translation, rotation, and reflection of the original triangle that consist ofP
a, P
b, P
c. Initially, the original triangle is translated to the origin so that the starting point P
start is located at the origin. Next, we rotate the triangle so that the second control point is placed on the x-axis. Finally, we ensure the last point of the curve construction process P
end is located at the positive y-axis region. If not, the reflection process is needed to reflect the last point with negative y-coordinate through the x-axis. The configuration after transformation is illustrated in Figures 2 and 3.


## 2.2.5. Computation of Tangent and Turning Angle (Step 7 and Step 8)

We apply the law of cosine of a triangle to calculate corresponding angles as shown in Figures2 and 3. The tangent angle θ
d and turning angle θ
e for case α
≤
1 or θ
f for case α
>
1 will be used in the subsequent step for calculating shape parameter Λ.


## 2.2.6. Upper Bound of Shape ParameterΛ (Step 9)

For the case whenα
=
1, there is no upper bound for shape parameter Λ. So, the value of Λ can be arbitrarily large. However, there are upper bounds for Λ when α
<
1 and α
>
1. Therefore, the Λ value of these two cases is restricted within the range of (a
,
b) where a and b are assigned a specified value as indicated in the algorithm above.


## 2.2.7. Shape ParameterΛ Calculation (Step 10 and Step 11)

We determine theΛ value that satisfies the constraints of endpoints and angles by using bisection method. First, tolerance and bound of Λ are used in the calculation of iteration number for bisection method. Then, the calculating process will run until the iteration number is met. Once the Λ value of the curve is obtained, it is an interpolating curve that satisfies boundary constraints as shape parameter Λ is used to control the curve so that the constraints are satisfied. The obtained Λ value ensures the generated LAC segment starts at the starting point and ends at the last point while the shape of curve follows the specified tangent vectors at two endpoints.


## 2.2.8. Computation of Scale Factor (Step 12)

We calculate the scaling factor by using the formula as shown in the algorithm whereP
a and P
c are endpoints of the original triangle while P
0 and P
2 are endpoints of the transformed triangle.


## 2.2.9. Construction of LAC Segment (Step 13–Step 15)

In order to obtain the curve which is defined in the original triangle, we inversely transform the triangle to its original position. The curve segment is constructed using (2) with the obtained value of Λ, θ
d, r
scale.


## 3. Numerical Examples and Discussion

This section shows the input data and numerical and graphical results of implementing the algorithm presented in Section2 for three examples. For comparison purpose, we present the results of Kimia’s algorithm [3] algorithm on the same examples as well.


### 3.1. The Graphical Results

Figure5 shows the first example of fitting Euler spiral and LAC segment to two parts of a jug. The results of the second example (artifact) and third example (vase) are depicted in Figures 6 and 7, respectively.The results of fitting Euler spiral and LAC segment for two missing parts of a jug.
(a)
Euler spiral algorithm
(b)
LAC algorithm with two tangents setting for s-shaped curve andα
=
-
1
(c)
LAC algorithm with two tangents setting for s-shaped curve andα
=
2The results of fitting Euler spiral and LAC segment for an artifact.
(a)
Euler spiral algorithm
(b)
LAC algorithm whenα
=
-
1
(c)
LAC algorithm whenα
=
0The results of fitting Euler spiral and LAC segment to a vase.
(a)
Euler spiral algorithm
(b)
Three types of tangents at the inflection points andα
=
-
1
(c)
Tangents setting as in 7(b) andα
=
-
1
(d)
Tangents setting as in 7(b) andα
=
1


### 3.2. The Numerical Results

The input data and the obtained parameter values to render LAC segment for C-shaped and S-shaped gaps are shown in Tables1, 2, and 3, respectively.Table 1
The input data for LAC algorithm.
Figure
Part/gap shape
Starting point
Inflection point
Terminating point
P
a
P
inflect
P
c
Figure5
Outer C
(475.33, 290.67)
—
(408, 512)
Inner C
(444, 319.3)
—
(406.7, 490.7)
S
(68.67, 198)
(115.139, 317.874)
(132, 445.33)
Figure6
Left C
(150.4, 320.8)
—
(123.2, 589.6)
Right C
(853, 307)
—
(824, 583)
Figure7
C
(504, 126)
—
(176, 120)
Right S
(576.67, 379.33)
(501.722, 483.092)
(445.33, 598)
Left S
(215.33, 599.33)
(166.565, 481.2)
(94, 376)Table 2
The value of parameters obtained in LAC algorithm for C-shaped gap.
Figure
Part
Shape parameter
Angles (radian)
Scale factor
Λ
θ
d
θ
e or θ
f
r
scale
Figure5(b)
Outer C
0.181102
1.97352
1.09383
106.443
Inner C
0.187822
2.50305
1.53612
57.7559
Figure5(c)
Outer C
0.236827
1.97352
0.879684
179.903
Inner C
0.307163
2.50305
0.966927
144.024
Figure6(b)
Left C
0.319685
1.55147
1.00107
105.562
Right C
0.204861
2.35562
1.47579
89.6424
Figure6(c)
Left C
0.53364
1.55147
1.00107
90.2434
Right C
0.610563
2.35562
1.47579
65.4159
Figure7(c)
—
0.140054
1.1637
0.601359
271.762
Figure7(d)
—
0.169061
1.1637
0.601359
270.036Table 3
The value of parameters obtained in LAC algorithm for S-shaped gap.
Figure
Part
Line style
Shape parameter
Angles (radian)
Scale factor
Λ
θ
d
θ
e or θ
f
r
scale
Figure5(b)
—
Piece 1
Thick
0.646746
0.739623
0.451367
107.501
Dashed
1.13587
0.43963
0.288258
152.739
Piece 2
Thick
0.140372
1.32647
0.689653
93.5698
Dashed
0.473033
1.02648
0.63682
76.6964
Figure5(c)
—
Piece 1
Thick
2.19523
0.43963
0.151372
568.396
Dashed
1.07216
0.739623
0.288256
293.721
Piece 2
Thick
0.811123
1.02648
0.389659
222.587
Dashed
0.156681
1.32647
0.63682
116.479
Figure7(c)
Right S
Piece 1
Thick
0.0000429688
0.571501
0.285752
227.044
Dashed
0.698712
0.871501
0.585746
39.271
Dotted
2.45758
0.371528
0.285746
23.657
Piece 2
Thick
0.0118778
0.908437
0.455056
145.074
Dashed
0.403597
1.20905
0.755673
65.1694
Dotted
0.700923
0.707704
0.45338
100.657
Figure7(d)
Right S
Piece 1
Thick
2.53147
0.871501
0.585746
41.1231
Dashed
0.0000429592
0.571501
0.285752
227.044
Dotted
10.7779
0.371528
0.285746
25.7032
Piece 2
Thick
1.2606
1.20905
0.755673
47.4646
Dashed
0.0120078
0.908437
0.455056
145.071
Dotted
2.48785
0.707704
0.45338
67.3212
Figure7(c)
Left S
Piece 1
Thick
0.188412
0.981157
0.509674
121.657
Dashed
0.603719
0.781142
0.471473
103.99
Dotted
0.361402
1.38114
0.909666
52.4523
Piece 2
Thick
0.0000462514
0.594672
0.297337
218.104
Dashed
0.884532
0.394671
0.297335
35.514
Dotted
0.564167
0.994666
0.697331
27.5123
Figure7(d)
Left S
Piece 1
Thick
1.61781
0.781142
0.471473
83.3887
Dashed
0.234412
0.981157
0.509674
120.616
Dotted
1.42816
1.38114
0.909666
31.5215
Piece 2
Thick
9.26646
0.394671
0.297335
31.4849
Dashed
0.0000462423
0.594672
0.297337
218.104
Dotted
2.66752
0.994666
0.697331
26.6104


### 3.3. Discussion

We implemented LAC algorithm with variousα values for each example. In Figures 5, 6, and 7, we showed a subfigure of LAC with α
=
-
1 in between the gaps for the missing part of the objects. These examples are indeed Euler spiral similar to the work of Kimia et al. [3]. Users are indeed fitting a circle involute when α
=
2 as shown in each figure; Nielsen spiral is fitted when α
=
0 and logarithmic spiral when α
=
1. The shape parameter α definitely dictates the type of spiral the user desires to fit into the gap.Based on the comparison of graphical results in Figures5, 6 and 7 we found that Kimia’s algorithm [3] and the LAC algorithm behave similarly. However, the proposed LAC algorithm gives more flexibility to designers as they can manipulate the shape parameter α and the tangent direction at the inflection point in order to get various S-shaped LAC segments.


## 3.1. The Graphical Results

Figure5 shows the first example of fitting Euler spiral and LAC segment to two parts of a jug. The results of the second example (artifact) and third example (vase) are depicted in Figures 6 and 7, respectively.The results of fitting Euler spiral and LAC segment for two missing parts of a jug.
(a)
Euler spiral algorithm
(b)
LAC algorithm with two tangents setting for s-shaped curve andα
=
-
1
(c)
LAC algorithm with two tangents setting for s-shaped curve andα
=
2The results of fitting Euler spiral and LAC segment for an artifact.
(a)
Euler spiral algorithm
(b)
LAC algorithm whenα
=
-
1
(c)
LAC algorithm whenα
=
0The results of fitting Euler spiral and LAC segment to a vase.
(a)
Euler spiral algorithm
(b)
Three types of tangents at the inflection points andα
=
-
1
(c)
Tangents setting as in 7(b) andα
=
-
1
(d)
Tangents setting as in 7(b) andα
=
1


## 3.2. The Numerical Results

The input data and the obtained parameter values to render LAC segment for C-shaped and S-shaped gaps are shown in Tables1, 2, and 3, respectively.Table 1
The input data for LAC algorithm.
Figure
Part/gap shape
Starting point
Inflection point
Terminating point
P
a
P
inflect
P
c
Figure5
Outer C
(475.33, 290.67)
—
(408, 512)
Inner C
(444, 319.3)
—
(406.7, 490.7)
S
(68.67, 198)
(115.139, 317.874)
(132, 445.33)
Figure6
Left C
(150.4, 320.8)
—
(123.2, 589.6)
Right C
(853, 307)
—
(824, 583)
Figure7
C
(504, 126)
—
(176, 120)
Right S
(576.67, 379.33)
(501.722, 483.092)
(445.33, 598)
Left S
(215.33, 599.33)
(166.565, 481.2)
(94, 376)Table 2
The value of parameters obtained in LAC algorithm for C-shaped gap.
Figure
Part
Shape parameter
Angles (radian)
Scale factor
Λ
θ
d
θ
e or θ
f
r
scale
Figure5(b)
Outer C
0.181102
1.97352
1.09383
106.443
Inner C
0.187822
2.50305
1.53612
57.7559
Figure5(c)
Outer C
0.236827
1.97352
0.879684
179.903
Inner C
0.307163
2.50305
0.966927
144.024
Figure6(b)
Left C
0.319685
1.55147
1.00107
105.562
Right C
0.204861
2.35562
1.47579
89.6424
Figure6(c)
Left C
0.53364
1.55147
1.00107
90.2434
Right C
0.610563
2.35562
1.47579
65.4159
Figure7(c)
—
0.140054
1.1637
0.601359
271.762
Figure7(d)
—
0.169061
1.1637
0.601359
270.036Table 3
The value of parameters obtained in LAC algorithm for S-shaped gap.
Figure
Part
Line style
Shape parameter
Angles (radian)
Scale factor
Λ
θ
d
θ
e or θ
f
r
scale
Figure5(b)
—
Piece 1
Thick
0.646746
0.739623
0.451367
107.501
Dashed
1.13587
0.43963
0.288258
152.739
Piece 2
Thick
0.140372
1.32647
0.689653
93.5698
Dashed
0.473033
1.02648
0.63682
76.6964
Figure5(c)
—
Piece 1
Thick
2.19523
0.43963
0.151372
568.396
Dashed
1.07216
0.739623
0.288256
293.721
Piece 2
Thick
0.811123
1.02648
0.389659
222.587
Dashed
0.156681
1.32647
0.63682
116.479
Figure7(c)
Right S
Piece 1
Thick
0.0000429688
0.571501
0.285752
227.044
Dashed
0.698712
0.871501
0.585746
39.271
Dotted
2.45758
0.371528
0.285746
23.657
Piece 2
Thick
0.0118778
0.908437
0.455056
145.074
Dashed
0.403597
1.20905
0.755673
65.1694
Dotted
0.700923
0.707704
0.45338
100.657
Figure7(d)
Right S
Piece 1
Thick
2.53147
0.871501
0.585746
41.1231
Dashed
0.0000429592
0.571501
0.285752
227.044
Dotted
10.7779
0.371528
0.285746
25.7032
Piece 2
Thick
1.2606
1.20905
0.755673
47.4646
Dashed
0.0120078
0.908437
0.455056
145.071
Dotted
2.48785
0.707704
0.45338
67.3212
Figure7(c)
Left S
Piece 1
Thick
0.188412
0.981157
0.509674
121.657
Dashed
0.603719
0.781142
0.471473
103.99
Dotted
0.361402
1.38114
0.909666
52.4523
Piece 2
Thick
0.0000462514
0.594672
0.297337
218.104
Dashed
0.884532
0.394671
0.297335
35.514
Dotted
0.564167
0.994666
0.697331
27.5123
Figure7(d)
Left S
Piece 1
Thick
1.61781
0.781142
0.471473
83.3887
Dashed
0.234412
0.981157
0.509674
120.616
Dotted
1.42816
1.38114
0.909666
31.5215
Piece 2
Thick
9.26646
0.394671
0.297335
31.4849
Dashed
0.0000462423
0.594672
0.297337
218.104
Dotted
2.66752
0.994666
0.697331
26.6104


## 3.3. Discussion

We implemented LAC algorithm with variousα values for each example. In Figures 5, 6, and 7, we showed a subfigure of LAC with α
=
-
1 in between the gaps for the missing part of the objects. These examples are indeed Euler spiral similar to the work of Kimia et al. [3]. Users are indeed fitting a circle involute when α
=
2 as shown in each figure; Nielsen spiral is fitted when α
=
0 and logarithmic spiral when α
=
1. The shape parameter α definitely dictates the type of spiral the user desires to fit into the gap.Based on the comparison of graphical results in Figures5, 6 and 7 we found that Kimia’s algorithm [3] and the LAC algorithm behave similarly. However, the proposed LAC algorithm gives more flexibility to designers as they can manipulate the shape parameter α and the tangent direction at the inflection point in order to get various S-shaped LAC segments.


## 4. Conclusion

A LAC segment can be constructed by specifying the endpoints and their tangent directions. LAC is a family of aesthetic curves where their curvature changes monotonically. It comprises Euler spiral, logarithmic spiral, Nielsen spiral, and circle involute with differentα values. The algorithm for constructing LAC segment to solve shape completion problem is defined in Section 2. The results of implementing both Kimia et al.’s [3] algorithm and the proposed LAC algorithm on the same images are depicted in Section 3. LAC has an upper hand due to its flexibility although both algorithms are capable of solving shape completion problems. Since LAC represents a bigger family rather than Euler spiral alone, it is clear that more shapes are available to fill the missing gap. Moreover, the resulting LAC segments are satisfying G
1 continuity where the curve segments interpolate both endpoints in the specified tangent directions. In case the user wants a G
2 LAC solution, one may plug in the technique proposed by Miura et al. [15] or employ G
2 GLAC [17] in which we may use shape parameter v in GLAC to satisfy the desired curvatures.



---

*Source: 960302-2014-08-11.xml*