# Polygon Morphing and Its Application in Orebody Modeling

Authors: Hacer İlhan; Haşmet Gürçay
Journal: Mathematical Problems in Engineering
 (2012)

---

## Abstract

Three different polygon morphing methods are examined. The first one is based on the utilization of the trimmed skeleton of the symmetric difference of the source and target polygons as an intermediate polygon. The second one reduces the problem to the problem of morphing compatible planar triangulations and utilizes the representation of planar triangulations as a matrix constructed using barycentric coordinates of the planar triangulation's vertices relative to their neighbors. The third and last one describes the polygon by the parametric curve representation based on estimated Fourier parameters and thus transfers the morphing process to Fourier parametric space. The different features and comparative results of these methods are shown by the tests with different examples. These methods are used for generating a set of polygonal sections from two nonplanar polygonal sections which are nearly planar in 3D before constructing a three-dimensional object from these nonplanar sections.


---

## Body

## 1. Introduction

Morphing or metamorphosis is usually defined as the gradual, smooth, and continuous transformation of a source object into a target object [1, 2]. Morphing is used in a variety of applications such as computer graphics, computer animation, industrial design, geometric modelling, and medicine.The morphing problem has been examined in many domains, such as two-dimensional images [3–5], polygons and polylines [1, 6–12], free-form curves [13], polyhedra and volumetric representations [6, 14, 15]. The morphing process for polygons and polyhedras consists of solving two main problems. The first one, known as the vertex correspondence problem, is to generate a correspondence between geometric elements of the source and target objects. The second one, known as the vertex path problem, is to find paths that corresponding geometric elements travel during the morphing process. In this work, three different morphing methods for polygons with some correspondence between their vertices are compared, and a morphing method for nonplanar polygonal sections in 3D without correspondence between their vertices is generated.Several approaches have been described on the polygon morphing problem. Shapira and Rappoport [11] presented a polygon morphing technique that takes into account both the interiors and the boundaries of the polygons. This is achieved by representing the interiors of the polygons with compatible skeletons which are called star skeletons and applying the morphing to the parametric description of these skeletons. The generation of corresponding skeletons of two polygons is used, and though theoretically possible for all shapes, it seems natural for similar shapes, but uncertain for rather different shapes. Alexa et al. [1] morphed the interiors of the polygons rather than their boundaries to achieve locally least distorting intermediate polygons. They compatibly triangulated the source and target polygons and developed the vertex paths during the morph in an attempt to maintain compatibility and preserve shape. Firstly they apply an algorithm to divide the source and target polygons into separate isomorphic triangles. Then, they develop a method for interpolating the locations of corresponding boundary and interior vertices along their paths from the source to the target polygons. Blanding et al. [6] described the skeleton-based polygon morphing and then generalized the same procedure directly to three dimensions. They used the trimmed skeleton of the symmetric difference of the source and target polygons as intermediate polygons. Gotsman and Surazhsky [9] described polygon morphing using compatible triangulation to reduce the polygon morphing problem to the problem of morphing compatible planar triangulations and utilized the representation of planar triangulations as a matrix constructed using barycentric coordinates of the planar triangulation’s vertices relative to their neighbors. Chen and Sun [7] described polygon morphing using Fourier parametrization to define the polygon by the parametric curve representation based on estimated Fourier parameters and thus transfer the morphing process to Fourier parametric space. In this work, the last three polygon morphing methods mentioned above are examined, and the last one is used for morphing nonplanar sections which are nearly planar in 3D.


## 2. Polygon Morphing

Given a source polygonP0 and a target polygon P1 with a correspondence between their vertices, the morphing procedure can be defined by the continuous function 𝒫:t→Pt, 0≤t≤1, where 𝒫(0)=P0 and 𝒫(1)=P1 are the source and target polygons, and for all 0<t<1, 𝒫(t)=Pt are intermediate polygons. Additionally, the intermediate polygon 𝒫(t)=Pt is similar to 𝒫(0)=P0 as t→0 and similar to 𝒫(1)=P1 as t→1.


### 2.1. Skeleton-Based Polygon Morphing

Skeleton-based polygon morphing method [6] is based on utilization of the trimmed skeleton of the symmetric difference of the source and target polygons as intermediate polygons.Each boundary point of the intermediate polygon generated by the morphing process can be defined as points equidistant from the nearest points of the source and target polygons. Similarly, skeletons consist of points minimally equidistant from two boundary points of a given shape. Therefore the skeleton of a shape that incorporates the boundaries of both the source and target polygons can be used for constructing middle polygon generated on the morphing process.In this method, firstly the intermediate polygon𝒫(1/2)=P1/2 is computed by using the source polygon 𝒫(0)=P0 and the target polygon 𝒫(1)=P1 as shown in Figure 1. To achieve this, first the skeleton of the symmetric difference of a combination of the source and target polygons is  computed. Then, the intermediate polygon 𝒫(1/2)=P1/2 is generated from the skeleton by applying a trimming operation to the skeleton. Similiary, the intermediate polygon 𝒫(1/4)=P1/4 is generated by using the polygons 𝒫(0)=P0 and 𝒫(1/2)=P1/2, and the intermediate polygon 𝒫(3/4)=P3/4 is generated by using the polygons 𝒫(1/2)=P1/2 and 𝒫(1)=P1. The same process is applied recursively until a desired sequence of intermediate polygons is produced.Figure 1
The main steps of skeleton-based polygon morphing. Two rectanglesP0 and P1 are combined by taking their symmetric difference (a) and the resulting shape is skeletonized (b) and trimmed (c) to obtain the intermediate polygon P1/2.


### 2.2. Polygon Morphing Using Compatible Triangulation

Polygon morphing method using compatible triangulation [9] reduces the problem to the problem of morphing compatible planar triangulations.The first task in polygon morphing using compatible triangulation is to compatibly triangulate the interiors of the given source polygonP0 and the target polygon P1 with the matching vertices. Then the polygons P0 and P1 are enclosed by identical convex polygons Q0 and Q1, and subsequently the annuli between Q0 and P0 and between Q1 and P1 are compatibly triangulated as shown in Figure 2. These two compatible triangulations with common convex boundary are represented by matrices constructed using barycentric coordinates of the these triangulation’s vertices relative to their neighbors. The next step is to generate the convex combination morph between these two compatible triangulations with common convex boundary to produce desired intermediate compatible triangulation with common convex boundary. Finally, all edges of these intermediate triangulations which do not belong to polygons P0 and P1 are discarded to obtain the desired intermediate polygon. Given polygons P0 and P1 with matching vertices, an overview of all the steps of the method of polygon morphing using compatible triangulation is shown in Table 1.Table 1
The main steps of the method of morphing polygonsP0 and  P1  using compatible triangulation.
(1) Compatibly triangulate the interiors ofP0 and P1 with the matching vertices.(2) EncloseP0 and P1 by identical convex polygons Q0 and Q1, respectively.(3) Compatibly triangulate the annuli betweenQ0 and P0 and between Q1 and P1, respectively.(4) Morph the two compatible triangulations using the method of morphing compatible triangulation.(5) Discard all edges of the two triangulations not belonging toP0 and P1.Compatible triangulations of the interiors ofP0 and the annuli between Q0 and P0 (a)  and compatible triangulations of the interiors of P1 and the annuli between Q1 and P1 (b).
(a)(b)


### 2.3. Polygon Morphing Using Fourier Parametrization

Polygon morphing method using Fourier parametrization [7] describes the polygon by the parametric curve representation based on estimated Fourier parameters and thus transfers the morphing process to Fourier parametric space.In this method, firstly the polygon coordinates are transformed to local coordinates, and then polygons are divided into matching segments using the correspondence between their vertices. The Fourier parametrization for each matching segment is computed, and the Fourier parameters are linearly interpolated to generate intermediate Fourier parametrizations. Lastly, the intermediate polygons are constructed using the interpolated Fourier parameters. Given polygonsP0 and P1 with matching vertices, an overview of all the steps of the method of polygon morphing using Fourier parametrization is shown in Table 2.Table 2
The main steps of the method of morphing polygonsP0 and  P1using Fourier parametrization.
(1) Transform the coordinates ofP0 and P1 with matching vertices to local coordinates.(2) Approximate the matching segments with the Fourier parameters.(3) Interpolate the local origins.(4) Interpolate the Fourier parameters.(5) Reconstruct the interpolated intermediate polygons.


### 2.4. Results and Discussion

The morphing problem can be solved by using a lot of different methods, but some constraints or desirable properties can be given for morphing procedure. Firstly, if the target polygon is a translation or rotation of the source polygon, then the intermediate polygons should also be an appropriate translation or rotation of the source polygon. Secondly, the area of the polygon generated by morphing should change smoothly as the source polygon turns into the target polygon. As Figure3 shows, among the examined three methods, polygon morphing method using Fourier parametrization is the only one which guarantees these properties. Thirdly, if the source and target polygons are closed and simple, then the intermediate polygons should also be closed and simple. Figure 3 shows that all of the examined methods achieve this property. The comparative results of these methods are shown in the following experiments. The results of all methods seem natural for similar shapes, but the results of skeleton-based polygon morphing method seem ambiguous for rather different shapes.Several comparative examples of skeleton-based polygon morphing method (a), (d), (g), polygon morphing method using compatible triangulation (b), (e), (h), and polygon morphing method using Fourier parametrization (c), (f), (i).
(a)(b)(c)(d)(e)(f)(g)(h)(i)As a distinction from the other two methods, skeleton-based polygon morphing method is capable of morphing between two polygons with different topologies, as shown in Figure4, where the source polygon consists of multiple parts and the target polygon consists of a single part. This method can also be generalized directly to three dimensions. While relative position, orientation, and combination of the source and target polygons can change the results of skeleton-based polygon morphing, the matching vertices between the source and target polygons can have a dramatic effect on the results of polygon morphing method using compatible triangulation and using Fourier parametrization.Figure 4
Skeleton-based morphing of two polygons with different topologies.


## 2.1. Skeleton-Based Polygon Morphing

Skeleton-based polygon morphing method [6] is based on utilization of the trimmed skeleton of the symmetric difference of the source and target polygons as intermediate polygons.Each boundary point of the intermediate polygon generated by the morphing process can be defined as points equidistant from the nearest points of the source and target polygons. Similarly, skeletons consist of points minimally equidistant from two boundary points of a given shape. Therefore the skeleton of a shape that incorporates the boundaries of both the source and target polygons can be used for constructing middle polygon generated on the morphing process.In this method, firstly the intermediate polygon𝒫(1/2)=P1/2 is computed by using the source polygon 𝒫(0)=P0 and the target polygon 𝒫(1)=P1 as shown in Figure 1. To achieve this, first the skeleton of the symmetric difference of a combination of the source and target polygons is  computed. Then, the intermediate polygon 𝒫(1/2)=P1/2 is generated from the skeleton by applying a trimming operation to the skeleton. Similiary, the intermediate polygon 𝒫(1/4)=P1/4 is generated by using the polygons 𝒫(0)=P0 and 𝒫(1/2)=P1/2, and the intermediate polygon 𝒫(3/4)=P3/4 is generated by using the polygons 𝒫(1/2)=P1/2 and 𝒫(1)=P1. The same process is applied recursively until a desired sequence of intermediate polygons is produced.Figure 1
The main steps of skeleton-based polygon morphing. Two rectanglesP0 and P1 are combined by taking their symmetric difference (a) and the resulting shape is skeletonized (b) and trimmed (c) to obtain the intermediate polygon P1/2.


## 2.2. Polygon Morphing Using Compatible Triangulation

Polygon morphing method using compatible triangulation [9] reduces the problem to the problem of morphing compatible planar triangulations.The first task in polygon morphing using compatible triangulation is to compatibly triangulate the interiors of the given source polygonP0 and the target polygon P1 with the matching vertices. Then the polygons P0 and P1 are enclosed by identical convex polygons Q0 and Q1, and subsequently the annuli between Q0 and P0 and between Q1 and P1 are compatibly triangulated as shown in Figure 2. These two compatible triangulations with common convex boundary are represented by matrices constructed using barycentric coordinates of the these triangulation’s vertices relative to their neighbors. The next step is to generate the convex combination morph between these two compatible triangulations with common convex boundary to produce desired intermediate compatible triangulation with common convex boundary. Finally, all edges of these intermediate triangulations which do not belong to polygons P0 and P1 are discarded to obtain the desired intermediate polygon. Given polygons P0 and P1 with matching vertices, an overview of all the steps of the method of polygon morphing using compatible triangulation is shown in Table 1.Table 1
The main steps of the method of morphing polygonsP0 and  P1  using compatible triangulation.
(1) Compatibly triangulate the interiors ofP0 and P1 with the matching vertices.(2) EncloseP0 and P1 by identical convex polygons Q0 and Q1, respectively.(3) Compatibly triangulate the annuli betweenQ0 and P0 and between Q1 and P1, respectively.(4) Morph the two compatible triangulations using the method of morphing compatible triangulation.(5) Discard all edges of the two triangulations not belonging toP0 and P1.Compatible triangulations of the interiors ofP0 and the annuli between Q0 and P0 (a)  and compatible triangulations of the interiors of P1 and the annuli between Q1 and P1 (b).
(a)(b)


## 2.3. Polygon Morphing Using Fourier Parametrization

Polygon morphing method using Fourier parametrization [7] describes the polygon by the parametric curve representation based on estimated Fourier parameters and thus transfers the morphing process to Fourier parametric space.In this method, firstly the polygon coordinates are transformed to local coordinates, and then polygons are divided into matching segments using the correspondence between their vertices. The Fourier parametrization for each matching segment is computed, and the Fourier parameters are linearly interpolated to generate intermediate Fourier parametrizations. Lastly, the intermediate polygons are constructed using the interpolated Fourier parameters. Given polygonsP0 and P1 with matching vertices, an overview of all the steps of the method of polygon morphing using Fourier parametrization is shown in Table 2.Table 2
The main steps of the method of morphing polygonsP0 and  P1using Fourier parametrization.
(1) Transform the coordinates ofP0 and P1 with matching vertices to local coordinates.(2) Approximate the matching segments with the Fourier parameters.(3) Interpolate the local origins.(4) Interpolate the Fourier parameters.(5) Reconstruct the interpolated intermediate polygons.


## 2.4. Results and Discussion

The morphing problem can be solved by using a lot of different methods, but some constraints or desirable properties can be given for morphing procedure. Firstly, if the target polygon is a translation or rotation of the source polygon, then the intermediate polygons should also be an appropriate translation or rotation of the source polygon. Secondly, the area of the polygon generated by morphing should change smoothly as the source polygon turns into the target polygon. As Figure3 shows, among the examined three methods, polygon morphing method using Fourier parametrization is the only one which guarantees these properties. Thirdly, if the source and target polygons are closed and simple, then the intermediate polygons should also be closed and simple. Figure 3 shows that all of the examined methods achieve this property. The comparative results of these methods are shown in the following experiments. The results of all methods seem natural for similar shapes, but the results of skeleton-based polygon morphing method seem ambiguous for rather different shapes.Several comparative examples of skeleton-based polygon morphing method (a), (d), (g), polygon morphing method using compatible triangulation (b), (e), (h), and polygon morphing method using Fourier parametrization (c), (f), (i).
(a)(b)(c)(d)(e)(f)(g)(h)(i)As a distinction from the other two methods, skeleton-based polygon morphing method is capable of morphing between two polygons with different topologies, as shown in Figure4, where the source polygon consists of multiple parts and the target polygon consists of a single part. This method can also be generalized directly to three dimensions. While relative position, orientation, and combination of the source and target polygons can change the results of skeleton-based polygon morphing, the matching vertices between the source and target polygons can have a dramatic effect on the results of polygon morphing method using compatible triangulation and using Fourier parametrization.Figure 4
Skeleton-based morphing of two polygons with different topologies.


## 3. Morphing of Nonplanar Sections

In mining, for 3D orebody modelling, three-dimensional objects are generated from nonplanar sections by building 3D triangulated or tetrahedral models. In the case where nonplanar sections are away from each other, three-dimensional models cannot be smooth as shown in Figure5. To build higher quality 3D models, these nonplanar sections should be morphed to generate intermediate sections. Polygon morphing method using Fourier parametrization is utilized for morphing two nonplanar sections which are nearly planar.Nonplanar sections (a) and their three-dimensional models (b) which are used in 3D orebody modelling.
(a)(b)To morph nonplanar sections which are nearly planar, firstly the source and target nonplanar sections are triangulated separately. The nonplanar section is specified in 3D, even though the triangulation is 2D. Thus, the nonplanar section is transformed in a plane, the transformed section is triangulated, and the topology of this triangulation is used for the original nontransformed section. To find a plane for triangulation, the most appropriate face of the oriented bounding box of the the nonplanar section can be used. These steps of the triangulation of the nonplanar section are shown in Figure6.Figure 6
The main steps of the triangulation of the nonplanar section. The nonplanar section (a) is transformed (c) into an appropriate face of the oriented bounding box (b), and the topology of the triangulation of the planar projection section (d) is used to triangulate the original nontransformed section (e).Let the triangulations of the source and target nonplanar sections consist of thes and t triangles, respectively, and let the normal vectors of the triangles of the source triangulations be n00,n01,…,n0s, and let the normal vectors of the triangles of the target triangulations be n10,n11,…,n1t. Then, the source nonplanar section is transformed in the face D0 of the source-oriented bounding box which has the minimum angle with the line with the normal vector n0=(n00+n01+⋯+n0s)/s, and similarly the target nonplanar section is transformed in the face D1 of the target-oriented bounding box which has the minimum angle with the line with the normal vector n1=(n10+n11+⋯+n1t)/t. Thus, these transformed planar sections can be specified in 2D. Then, each transformed section in 2D is separately parametrized proportionally to arclength as g:[0,1]→ℝ2, t↦g(t)=(x(t),y(t)), and the Fourier parametrization for each curve is separately computed as(3.1)[x(t)y(t)]=[a0c0]+∑n=1∞([anbncndn][cos⁡⁡(2πnt)sin⁡⁡(2πnt)]),where Fourier parameters are(3.2)a0=∫01x(t)dt,an=2∫01x(t)cos⁡⁡(2πnt)dt,bn=2∫01x(t)sin⁡⁡(2πnt)dt,c0=∫01y(t)dt,cn=2∫01y(t)cos⁡⁡(2πnt)dt,dn=2∫01y(t)sin⁡⁡(2πnt)dtfor anyn∈ℕ-{0}, and upper left vertex of each transformed section in 2D is chosen as initial vertex. The Fourier parameters are linearly interpolated to generate the intermediate Fourier parametrizations, and the intermediate transformed sections in 2D are constructed using the interpolated Fourier parameters. Let S be the number of intermediate nonplanar sections, then the tth intermediate transformed sections in 2D are transformed into the plane with normal
(3.3)nt=S-s+1S+1⋅n0+sS+1⋅n1and center(3.4)mt=S-s+1S+1⋅m0+sS+1⋅m1,wherem0 and m1 are the center of the planes D0 and D1, respectively. Thus the intermediate sections are obtained. An overview of all these steps to morph nonplanar sections is shown in Table 3.Table 3
The main steps of our method of morphing nonplanar sections.
(1) Triangulate the source and target nonplanar sections separately.(2) Transform the source and target nonplanar sections in 2D using the triangulations.(3) Establish initial vertex for each transformed section in 2D.(4) Approximate each transformed section in 2D with Fourier parameters.(5) Interpolate the normals and centers of planes which have the transformed source and target sections in 2D.(6) Interpolate Fourier parameters.(7) Reconstruct the interpolated intermediate polygons.Figure7 shows a set of intermediate sections generated from two nonplanar polygonal sections in 3d, and Figure 8 shows a three-dimensional object of the source, target and intermediate sections. the transformations of nonplanar sections can have an important effect on the results of morphing nonplanar section, namely this method relies on having data organized in nearly planar sections.Two different results of our method of morphing nonplanar sections.
(a)(b)Figure 8
Three-dimensional objects of the source, target, and intermediate sections.


## 4. Conclusion

We have presented the different features and comparative results of three different morphing methods which are skeleton-based polygon morphing, polygon morphing using compatible triangulation, and polygon morphing using Fourier parametrization. According to results, we developed a generalization of the intermediate sections from two nonplanar polygonal sections in 3D which are nearly planar, before constructing a three-dimensional object from these nonplanar polygonal sections to build higher quality 3D models. To achieve this, firstly we needed to solve the vertex path problem. In the skeleton-based polygon morphing method, the source and target objects are combined into a single object as desired instead of generating a correspondence between the geometric elements of the source and target objects. This process is important and has a major effect on the morph history generated. But in mining, there are nonplanar sections with many different initial relative positions and orientations in 3D. Therefore transformed combination of two nonplanar sections in 2D can be constructed, and polygon morphing method using Fourier parametrization is utilized for morphing these two 2D sections, and so intermediate sections are obtained in 2D. Then these intermediate sections are transformed to appropriate location between the source and target nonplanar polygonal sections. In this manner, intermediate polygonal sections in 3D are generated on the morphing process of the source and target nonplanar polygonal sections in 3D. Our method relies on having data organized in nearly planar sections, since transformation of folded sections in 2D cannot be simple, and the method is based on the transformations of nonplanar sections.



---

*Source: 732365-2012-05-10.xml*