# Adaptive Geometry Images for Remeshing

Authors: Lina Shi; Dehui Kong; Shaofan Wang; Baocai Yin
Journal: International Journal of Digital Multimedia Broadcasting
 (2017)

---

## Abstract

Geometry images are a kind of completely regular remeshing methods for mesh representation. Traditional geometry images have difficulties in achieving optimal reconstruction errors and preserving manually selected geometric details, due to the limitations of parametrization methods. To solve two issues, we propose two adaptive geometry images for remeshing triangular meshes. The first scheme produces geometry images with the minimum Hausdorff error by finding the optimization direction for sampling points based on the Hausdorff distance between the original mesh and the reconstructed mesh. The second scheme produces geometry images with higher reconstruction precision over the manually selected region-of-interest of the input mesh, by increasing the number of sampling points over the region-of-interest. Experimental results show that both schemes give promising results compared with traditional parametrization-based geometry images.


---

## Body

## 1. Introduction

Triangular meshes are important tools for representing geometric data in computer graphics, due to the ease of generation procedure from point clouds and simple manipulation. However, many applications of meshes such as mesh morphing and mesh compression tend to use triangular meshes with regular structure. Traditional triangular meshes, which have irregular connectivity due to the generation procedure, need to be remeshed. This technique is referred to asremeshing. Geometry images are a completely regular remeshing method, which represents a triangular mesh as an image array, where the vertex-set of the mesh is stored as the pixels of the image and where the connectivity of the mesh is intrinsically embedded in the image array. Such a regular structure of meshes is helpful for reducing the representation of geometric data and coworking well with many image-based applications such as image compression and rendering process.In general, geometry images include three steps: mesh parametrization, resampling, and quantification. The first step maps 3D vertices of the input mesh to regular parametrization domain (square, rectangle, or sphere), the second step imposes sampling over the parametrization domain via interpolation methods, and the third step transforms the coordinates of sampling points to pixel values of an image array. To reconstruct a mesh for geometry images, the vertex-set is obtained from the pixels of the image array, and the edge-set is obtained from the connectivity of the adjacent pixels of the array.Although fruitful research work was proposed for geometry images, many of them focuses on the mesh parametrization and ignores the importance of the resampling step, which increases the burden of parametrization technique, as the parametrization leads to a complicated and nonconvex optimization which heavily depends on the connectivity of the input mesh (while the resampling scheme depends more on the connectivity of the regular sampling fashion instead of the input mesh). In particular, traditional geometry images have difficulties in achieving optimal reconstruction errors, or in preserving manually selected geometric details. To solve such two issues, we propose two adaptive geometry images. The first scheme produces geometry images with the minimum Hausdorff error, by finding the optimization direction for sampling points based on the Hausdorff distance between the original mesh and the reconstructed mesh. The second scheme produces geometry images with higher reconstruction precision over the manually selected region-of-interest of the input mesh, by increasing the number of sampling points over the region-of-interest. We compare our schemes with traditional geometry images using state-of-the-art mesh parametrization scheme and adaptive sampling scheme in terms of both reconstruction error and mesh compression. Experimental results on both qualitative comparison and quantitative comparison show that our schemes outperform traditional geometry images.


## 2. Related Work

### 2.1. Geometry Images

Gu et al. [1] propose the pioneering work of geometry images, which maps a triangular mesh onto a square domain by using a minimizing-geometric-stretch parametrization and gives a regular sampling for surface geometry. Praun and Hoppe [2] propose spherical parametrization for geometry images, which facilitates the representation of genus-zero closed meshes. Gauthier and Poulin [3] fill nonzero genus meshes and propose spherical parametrization for treating meshes of arbitrary genus. Zhou et al. [4] propose an adaptive sampling scheme for geometry images, which keeps most details of models. Gauthier and Poulin [5] propose another sampling scheme for geometry images to maintain both edge features and sharp features. Meng et al. [6] adopt differential coordinates to correct the vector direction of the reconstruction model, which makes the reconstruction model accurately preserve the detailed features of the original model.The aforementioned work of geometry images maps models into single-chart geometry images, which tends to produce high geometric stretch and ignore details of models. Alternatively, Tewari et al. [7] propose multichart geometry images by cutting the model into some irregular subslices, but it required a lot of space to store the information of subslices. Carr et al. [8] convert the irregular subslices to quadrilateral subslices. Yao and Lee [9] decompose a mesh into square GIM charts with different resolutions, each of which is adaptively determined by a local reconstruction error. Feng et al. [10] propose geometry images for generating triangular patches based on a curvilinear feature. The feature preserves salient features and supports GPU-based LOD representation of meshes.


### 2.2. Other Remeshing Methods

Alliez et al. [11] propose an interactive remeshing of irregular geometry, which represents the original mesh as a series of 2D parametrization maps. The algorithm facilitates the real-time interaction and intricate control using a map which controls the sampling density over the surface patch. Alliez et al. [12] propose a polygonal remeshing method using the intrinsic anisotropy of natural or man-made geometry. The authors use curvature directions to drive the remeshing process and determine appropriate edges for the remeshed version in anisotropic regions. The method provides the flexibility to produce meshes ranging from isotropic to anisotropic, from coarse to dense, and from uniform to curvature adapted. Dong et al. [13] propose a new quadrilateral remeshing method for manifolds of arbitrary genus. The method computes the gradient of smooth harmonic scalar fields defined over the mesh and forms the polygons of the output mesh using two nets of integral lines. Huang et al. [14] propose a quadrangulation method, by extending the spectral surface quadrangulation approach with the coarse quadrangular structure derived from the Morse-Smale complex of an eigenfunction of the Laplacian operator on the input mesh. The quadrilateral mesh is reconstructed from the Morse-Smale complex by computing a globally smooth parametrization. Zhang et al. [15] propose a new method for remeshing a surface into a quadrangle, by constructing a special standing wave on the surface to generate the global quadrilateral structure, which controls the quad size in two directions and precisely aligning the quads with feature lines.


## 2.1. Geometry Images

Gu et al. [1] propose the pioneering work of geometry images, which maps a triangular mesh onto a square domain by using a minimizing-geometric-stretch parametrization and gives a regular sampling for surface geometry. Praun and Hoppe [2] propose spherical parametrization for geometry images, which facilitates the representation of genus-zero closed meshes. Gauthier and Poulin [3] fill nonzero genus meshes and propose spherical parametrization for treating meshes of arbitrary genus. Zhou et al. [4] propose an adaptive sampling scheme for geometry images, which keeps most details of models. Gauthier and Poulin [5] propose another sampling scheme for geometry images to maintain both edge features and sharp features. Meng et al. [6] adopt differential coordinates to correct the vector direction of the reconstruction model, which makes the reconstruction model accurately preserve the detailed features of the original model.The aforementioned work of geometry images maps models into single-chart geometry images, which tends to produce high geometric stretch and ignore details of models. Alternatively, Tewari et al. [7] propose multichart geometry images by cutting the model into some irregular subslices, but it required a lot of space to store the information of subslices. Carr et al. [8] convert the irregular subslices to quadrilateral subslices. Yao and Lee [9] decompose a mesh into square GIM charts with different resolutions, each of which is adaptively determined by a local reconstruction error. Feng et al. [10] propose geometry images for generating triangular patches based on a curvilinear feature. The feature preserves salient features and supports GPU-based LOD representation of meshes.


## 2.2. Other Remeshing Methods

Alliez et al. [11] propose an interactive remeshing of irregular geometry, which represents the original mesh as a series of 2D parametrization maps. The algorithm facilitates the real-time interaction and intricate control using a map which controls the sampling density over the surface patch. Alliez et al. [12] propose a polygonal remeshing method using the intrinsic anisotropy of natural or man-made geometry. The authors use curvature directions to drive the remeshing process and determine appropriate edges for the remeshed version in anisotropic regions. The method provides the flexibility to produce meshes ranging from isotropic to anisotropic, from coarse to dense, and from uniform to curvature adapted. Dong et al. [13] propose a new quadrilateral remeshing method for manifolds of arbitrary genus. The method computes the gradient of smooth harmonic scalar fields defined over the mesh and forms the polygons of the output mesh using two nets of integral lines. Huang et al. [14] propose a quadrangulation method, by extending the spectral surface quadrangulation approach with the coarse quadrangular structure derived from the Morse-Smale complex of an eigenfunction of the Laplacian operator on the input mesh. The quadrilateral mesh is reconstructed from the Morse-Smale complex by computing a globally smooth parametrization. Zhang et al. [15] propose a new method for remeshing a surface into a quadrangle, by constructing a special standing wave on the surface to generate the global quadrilateral structure, which controls the quad size in two directions and precisely aligning the quads with feature lines.


## 3. Hausdorff Error Driven Geometry Images

We propose Hausdorff error driven geometry images in this section. The key step of our scheme is to find the points, edges, or faces of the original mesh and reconstruction mesh which achieve the maximum Hausdorff distance and then compute the gradient direction of the Hausdorff distance. Our scheme consists of three phases: an initial adaptive sampling, approximate representation of Hausdorff distance, and the adjustment of sampling vertices, which are described in the following three subsections and illustrated in Figure1. We shall use the calligraphy letter M for representing a mesh and denote VM, FM, PM to be the vertex-set, the face-set, and the point-set (i.e., all points within each face) of a mesh M, respectively, and denote Ef, Ve, Vf to be the edge-set of a face f, the set of two end-vertices of an edge e, and the set of three end-vertices of a face f, respectively.Figure 1
A framework for Hausdorff error driven geometry images.


### 3.1. Vertex Density Equalization Based Adaptive Sampling

We propose an initial adaptive sampling scheme using a vertex density equalization metric in this subsection. The equalization is adopted along bothx-axis direction and y-axis direction direction over the parametrization domain Ω≔0,12. The algorithm is illustrated as follows:(1)
Employ an/2×n/2 uniform partition over Ω, that is, Ω=⋃i,j=1n/2Ωij with Ωij=(i-1)/n/2,i/n/2×(j-1)/n/2,j/n/2, i,j=1,…,n/2.(2)
DenoteΩix=⋃jΩij to be the x-axis partition and find the partition set Ωi∗x which contains the greatest number of parametrization vertices.(3)
Divide the partition setΩi∗x into two sets, that is, Ω=⋃i,j=1n/2+1,n/2Ωij with Ωi∗,j=[(i∗-1)/⌊n/2⌋,(i∗-1/2)/⌊n/2⌋]×[(j-1)/⌊n/2⌋,j/⌊n/2⌋], and Ωi∗+1,j=[(i∗-1/2)/⌊n/2⌋,i∗/⌊n/2⌋]×[(j-1)/⌊n/2⌋,j/⌊n/2⌋].(4)
Repeat Steps (2) and (3) until the x-axis partition contains n-1 partition sets.(5)
Apply Steps (2), (3), and (4) on the y-axis partition in a similar fashion.The algorithm yields 2n-1 partition sets Ωixi=1n-1 along x-axis and the other n-1 sets Ωiyi=1n-1 along y-axis. The location of sampling vertices is then given by the intersections of bounding lines of a partition set along x-axis and a partition set along y-axis, and the sampling rate is n×n. We show the sampling result of venus in Figure 2.Figure 2
The vertex density equalization based adaptive sampling overvenus with sampling rate n×n. From (a) to (c): the parametrization mesh, the [n/2]×[n/2] regular sampling mesh, and the vertex density equalization based adaptive sampling mesh, with n=70.
(a)
(b)
(c)


### 3.2. Representation of Hausdorff Distance between Meshes

Hausdorff distance measures the distance between two 3D meshes (see [16]), which is defined by(1)dHM,M′=max⁡dM,M′,dM′,M,(2)dM,M′=maxp∈PMdistp,M′=maxp∈PMminp′∈PM′p-p′.According to the definition, the Hausdorff distance depends only on each face of a mesh together with a small number of faces of the other mesh relatively closed to it. Therefore, in order to speed up the computation of the Hausdorff distance, for each target face of the target mesh, we only choose a few number of faces from the other mesh (i.e., we enlarge the parametrization domain of the target face of the target mesh twice, and the faces are chosen as the faces of the other mesh which share common points with the enlarged target face over the parametrization domain). We illustrate the idea in Figure 3, where S, S′ denote a target face of the target mesh and the selected faces of the sampling mesh, respectively. During the computation of Hausdorff distance from a face S of original mesh to reconstruction mesh, we need to record three pieces of data: the Hausdorff distance d(S,S′) from S to S′, the point p∗ of S which achieves the Hausdorff distance p∗=arg⁡maxp∈PSdist(p,S′), and the face f∗ of S′ which achieves the Hausdorff distance together: f∗=arg⁡minf∈FS′dist(p∗,f). Such process is repeated during the computation of Hausdorff distance from a face S of reconstruction mesh to original mesh.Figure 3
Selection of the associated faces with respect to the target face. Black triangles denote the parametrization mesh, green triangles denote the sampling mesh, and red solid triangle denotes a target faceS. The red dash triangles denote the enlarged face, and the green bold lines denote the collection S′ of the selected faces of the sampling mesh.


### 3.3. Iterative Adjustment of Sampling Vertices

The key step of our scheme is the iterative adjustment of sampling vertices. We first give the distance type judgement between the point and the face which achieve the maximum Hausdorff distance obtained in Section3.2 and then compute the gradient direction of the Hausdorff distance with respect to the vertex/vertices associated with the maximum Hausdorff distance. The adjustment of the vertices is then applied using gradient descent method with suitable step length. The whole algorithm stops when no vertices can be adjusted.(1) Determination of the Distance Type between the Target Point and the Target Face. Similar to [17], the Hausdorff distance between a point and a triangle includes three types: Point-Face, Point-Edge, and Point-Point. We describe the main idea in Figure 4 (see also [17]). We denote p′ to be the projection of p over the plane containing abc. We first judge whether p′ and a lie in the same side or different sides of line bc and judge the relationship of p′ and b with respect to the line ca, as well as the relationship of p′ and c with respect to the line ab. Three judgements give eight cases of results with one of them (i.e., p′ and each of the end-vertices of abc lie in different sides of the corresponding edge) always being invalid. Thus the seven cases of results correspond to the seven cases of locations of p′ corresponding to seven types of Hausdorff distance from p to abc. In detail, we denote (3)lbcx,y=0,lcax,y=0,labx,y=0to be the equations of edges bc, ca, ab, respectively. Then we denote (4)λ1=lbcalbcp′,λ2=lcablcap′,λ3=labclabp′to be three real numbers for distance type determination. The distance type between the point p and the face abc is given by(5)Point-Facep-abcifmax⁡λ1,λ2,λ3>0,Point-Edgep-bcifmin⁡λ2,λ3>0≥λ1,Point-Edgep-caifmin⁡λ3,λ1>0≥λ2,Point-Edgep-abifmin⁡λ1,λ2>0≥λ3,Point-Pointp-aifmin⁡λ2,λ3≤0,Point-Pointp-bifmin⁡λ3,λ1≤0,Point-Pointp-cifmin⁡λ1,λ2≤0.Finally, we obtain the following two distance sets:(6)D1=df,M′:f∈FM,D2=df′,M:f′∈FM′,where D1 (D2, resp.) is the collection of the directed Hausdorff distances from each face of M (M′, resp.) to the reconstruction mesh M′ (original mesh M, resp.), with the directed Hausdorff distances d(f,M′), d(f′,M) defined by (1).Figure 4
Different types of distances between a pointp and a triangle abc.(2) Selection of the Gradient Direction. There are three kinds of objective functions: Point-Face, Point-Edge, and Point-Point and two cases of Hausdorff distance relationship: max⁡D1>max⁡D2 and max⁡D1≤max⁡D2, which produces six kinds of gradient direction. We introduce them in the following three paragraphs.Although verbose equations shall be listed, the main idea is simple. The three cases (Point-Point, Point-Edge, and Point-Face) determine the distance equation [(8), (11), and (14)], and the two cases (max⁡D1>max⁡D2 or max⁡D1≤max⁡D2) determine which point(s) can be moved: when max⁡D1>max⁡D2, we update the location of the target end-vertex (edge, face) on M′ according to the Point-Point (Point-Edge, Point-Face) case; when max⁡D1≤max⁡D2, we update the locations of the end-vertices of the face containing the target point (i.e., the point achieving the greatest Hausdorff distance) on M′.Within the following three paragraphs, we denotep∗=(xp∗,yp∗,zp∗) to be the target point, and denote f∗=q1q2q3 to be the target face; that is, f∗ is the face of the corresponding mesh of p∗ which achieves the maximum distance from p∗. Note that p∗, f∗ belong to different meshes of M, M′. We also denote p1p2p3 to be the face containing p∗ and denote α, β, γ  to be the barycentric coordinate of p∗ with respect to p1p2p3; that is, p∗=αp1+βp2+γp3. We denote (x□,y□,z□) to be the coordinates of the point □ and denote (7)xij=xqi-xqj,yij=yqi-yqj,zij=zqi-zqj,i,j=1,2,3to be the differences of coordinates of q1, q2, q3.(a) Point-Point Optimization. The Point-Point distance from p∗ to an end-vertex q of f∗ is given by(8)dpp2=xq-xp∗2+yq-yp∗2+zq-zp∗2.We compute the gradient of dpp2 in two cases. If max⁡D1>max⁡D2, then p∗∈PM, q∈VM′ and we update the location of q using the gradient of dpp2 with respect to q, which is given by(9)∇qdpp2=2xq-xp∗yq-yp∗zq-zp∗⊤.Otherwise, max⁡D1≤max⁡D2 holds; then we have p∗∈PM′, q∈VM and we shall update the locations of p1, p2, p3. Thus we compute the gradient of dpp2 with respect to p1, p2, p3 by(10)∇p1;p2;p3dpp2=2αM1βM1γM1withM1=xp∗-xqyp∗-yqzp∗-zq,where we use the notation ∇{q1;…;qm}d for concatenating the gradient of d(q1,…,qm) with respect to m points {q1,…,qm}⊆R3 to form a vector of R3m.(b) Point-Edge Optimization. Let q1=(x1,y1,z1), q2=(x2,y2,z2) be two end-vertices of the triangle q1q2q3. The Point-Edge distance from p∗ to the edge q1q2 is given by(11)dpe2=yp∗-yq1z12-zp∗-zq1y122+zp∗-zq1x12-xp∗-xq1z122+xp∗-xq1y12-yp∗-yq1x122x122+y122+z122.If max⁡D1>max⁡D2, then p∗∈PM, q1q2∈EM′ hold, and we shall update the locations q1, q2 with the gradient of dpe2 given by (16). Otherwise, we have p∗∈PM′, q1q2∈EM, and we update all the end-vertices of the face containing p∗. The gradient of dpe2 with respect to all the end-vertices of the face is given by(12)∇p1;p2;p3dpe2=2x122+y122+z122αM2βM2γM2x12y12z12withM2=0xp∗-xq1y12xp∗-xq1z12yp∗-yq1x12-yp∗-yq1x12-zp∗-zq1x12-xp∗-xq1y120yp∗-yq1z12zp∗-zq1x12zp∗-zq1y12-zp∗-zq1y12-xp∗-xq1z12-yp∗-yq1z120.(c) Point-Face Optimization. We denote(13)a=yq1z23+yq2z31+yq3z12,b=zq1x23+zq2x31+zq3x12,c=xq1y23+xq2y31+xq3y12,g=xq1yq3zq2-yq2zq3+xq2yq1zq3-yq3zq1+xq3yq2zq1-yq1zq2to be the coefficients of the equation of the plane where the face q1q2q3 lies, and the Point-Face distance from p∗ to the face q1q2q3 is given by(14)dpf2=axp∗+byp∗+czp∗+g2a2+b2+c2.If max⁡D1>max⁡D2, then p∗∈PM, q1q2q3∈FM′ and we shall update the locations of q1, q2, q3 using the gradient of dpf2 given by (17). Otherwise, we update the locations of p1, p2, p3 with the gradient of dpf2 given by(15)∇p1;p2;p3dpf2=2a2+b2+c2αM3βM3γM3xp∗yp∗zp∗1withM3=a2abacagabb2bcbgacbcc2cg.In summary, we show Algorithm1 for generating the Hausdorff distance geometry images, where we compute the gradient of the directional Hausdorff distance square d2 in six cases according to the distance type and the quantitative relationship of max⁡D1 and max⁡D2. Note that when max⁡D1>max⁡D2, we update the end-vertices of the target face f∗ on M′ (see Algorithm 2); when max⁡D1≤max⁡D2, we update the end-vertices of the face p1p2p3 containing p∗ on M′ (see Algorithm 3). For each of the six cases, we compute the stepsize ρk,k=0,…,K which admits decreasing of the Hausdorff distance; the algorithm terminates provided that no such stepsize can be found.(16)∇q1;q2dpe2=2x122+y122+z122zp∗-zq2yp∗-yq2x21xp∗-xq2zp∗-zq2y21yp∗-yq2xp∗-xq2z21zq1-zp∗yq1-yp∗x12xq1-xp∗zq1-zp∗y12yq1-yp∗xq1-xp∗z12zp∗-zq1x12-xp∗-xq1z12yp∗-yq1x12-xp∗-xq1y12dpe2.(17)∇q1;q2;q3dpf2=2h0z32y23zq2yq3-yq2zq3z230x32xq2zq3-zq2xq3y32x230yq2xq3-xq2yq30z13y31zq3yq1-yq3zq1z310x13xq3zq1-zq3xq1y13x310yq3xq1-xq3yq10z21y12zq1yq2-yq1zq2z120x21xq1zq2-zq1xq2y21x120yq1xq2-xq1yq2xp∗yp∗zp∗1+2h20z23y32z320x23y23x3200z31y13z130x31y31x1300z12y21z210x12y12x210abcwithh=axp∗+byp∗+czp∗+ga2+b2+c2Algorithm 1:Optimal Hausdorff error driven geometry images.
Input. A mesh M and stepsize threshold K=100
Output. The 3D location of vertices of GIM mesh M′
(
1
) Apply vertex density equalization on M (Section 3.1);
(
2
) Compute D1,D2 using (6) (Section 3.2);
(
3
)  If  max⁡D1>max⁡D2  then
(
4
)   Compute the target point p∗←argmaxp∈PM⁡dist(p,M′);
(
5
)   Compute the target face f∗←argmaxf∈FM′⁡dist(p∗,f);
(
6
)  Judge the distance type between p∗ and f∗ using (5);
(
7
)   Update the position of the end-vertices of f∗ using Algorithm 2;
(
8
)  else
(
9
)    Compute the target point p∗←argmaxp∈PM′⁡dist(p,M);
(
10
)  Compute the target face f∗←argmaxf∈FM⁡dist(p∗,f);
(
11
)  Judge the distance type between p∗ and f∗ using (5);
(
12
)  Update the position of the end-vertices of f∗ using Algorithm 3;
(
13
)  endAlgorithm 2:Update the position of end-vertices of target face f∗ when max⁡D1>max⁡D2.
Input.  A target point p∗, a target face f∗, a mesh M and stepsize threshold K=100, ρ=1/2
Output. New locations of the end-vertices of the face f∗
(
1
)    switch   Distance Type  do
(
2
)   case  Point-Point
(
3
)    Find the closest end-vertex  q of f∗ from p∗ by q←argminq∈Vf∗p∗-q;
(
4
)    Compute the gradient ∇qdpp2 using (9);
(
5
)      for  k=0,…,K  do
(
6
)     Update the Hausdorff distance set D1pp(k) using (6) with q replaced by q-ρk∇qdpp2;
(
7
)       if  max⁡D1pp(k)<max⁡D1  then
(
8
)      Update q by q←q-ρk∇qdpp2;
(
9
)      Break;
(
10
)    end
(
11
)   end
(
12
)   if  max⁡D1pp(k)≥max⁡D1,∀k=0,…,K  then
End the algorithm;
(
13
)    case  Point-Edge
(14)    Find the closest edge off′ from p∗ by e′←argmine∈Ef∗dist(p∗,e);
(15)    Denoteq1,q2 to be the end-vertices of e′;
(16)    Compute the gradient∇[q1;q2]dpe2 using (16);
(17)for  k=0,…,K  do
(18)      Update the Hausdorff distance setD1pe(k) using (6) with q1,q2 replaced by [q1;q2]-ρk∇[q1;q2]dpe2;
(19)if  max⁡D1pe(k)<max⁡D1then
(20)      Updateq1,q2 by [q1;q2]←[q1;q2]-ρk∇[q1;q2]dpe2;
(21)       Break;
(22)end
(23)end
(24)if  max⁡D1pe(k)≥max⁡D1,∀k=0,…,K  then
End the algorithm;
(25)case  Point-Face
(26)    Denoteq1,q2,q3 to be the end-vertices of f∗;
(27)    Compute the gradient∇[q1;q2;q3]dpf2 using (17);
(28)for  k=0,…,K  do
(29)     Update the Hausdorff distance setD1pf(k) using (6) with q1,q2,q3 replaced by [q1;q2;q3]-ρk∇[q1;q2;q3]dpf2;
(30)if  max⁡D1pf(k)<max⁡D1  then
(31)      Updateq1,q2,q3 by [q1;q2;q3]←[q1;q2;q3]-ρk∇[q1;q2;q3]dpf2;
(32)      Break;
(33)end
(34)end
(35)if  max⁡D1pf(k)≥max⁡D1,∀k=0,…,K  then
End the algorithm;
(36)endsw
(37)endswAlgorithm 3:Update the position of end-vertices of the face containing p∗ when max⁡D1≤max⁡D2.
Input.  A target point p∗, a target face f∗, a mesh M and stepsize threshold K=100, ρ=1/2
Output. New locations of the end-vertices of the face p1p2p3
(
1
)   switch   Distance Type  do
(
2
)    case  Point-Point
(
3
)     Compute the gradient ∇[p1;p2;p3]dpp2 using (10);
(
4
)        for  k=0,…,K  do
(
5
)      Update the Hausdorff distance set D2pp(k) using (6) with p1,p2,p3 replaced by [p1;p2;p3]-ρk∇[p1;p2;p3]dpp2;
(
6
)       if  max⁡D2pp(k)<max⁡D2  then
(
7
)       Update p1,p2,p3 by [p1;p2;p3]←[p1;p2;p3]-ρk∇[p1;p2;p3]dpp2;
(
8
)       Break;
(
9
)       end
(
10
)     end
(
11
)     if  max⁡D2pp(k)≥max⁡D2,∀k=0,…,K  then
End the algorithm;
(
12
)    case  Point-Edge
(
13
)     Compute the gradient ∇[p1;p2;p3]dpe2 using (12);
(14)for  k=0,…,K do
(15)      Update the Hausdorff distance setD2pe using (6) with p1,p2,p3 replaced by [p1;p2;p3]-ρk∇[p1;p2;p3]dpe2;
(16)if max⁡D2pe(k)<max⁡D2  then
(17)       Updatep1,p2,p3 by [p1;p2;p3]←[p1;p2;p3]-ρk∇[p1;p2;p3]dpe2;
(18)       Break;
(19)end
(20)end
(21)if  max⁡D2pe(k)≥max⁡D2,∀k=0,…,K  then
End the algorithm;
(22)case  Point-Face
(23)     Compute the gradient∇[p1;p2;p3]dpf2 using (15);
(24)for  k=0,…,K  do
(25)      Update the Hausdorff distance setD2pf using (6) with p1,p2,p3 replaced by [p1;p2;p3]-ρk∇[p1;p2;p3]dpf2;
(26)if  max⁡D2pf(k)<max⁡D2  then
(27)       Updatep1,p2,p3 by [p1;p2;p3]←[p1;p2;p3]-ρk∇[p1;p2;p3]dpf2;
(28)       Break;
(29)end
(30)end
(31)if  max⁡D2pf(k)≥max⁡D2,∀k=0,…,K  then
End the algorithm;
(32)endsw
(33)endsw


## 3.1. Vertex Density Equalization Based Adaptive Sampling

We propose an initial adaptive sampling scheme using a vertex density equalization metric in this subsection. The equalization is adopted along bothx-axis direction and y-axis direction direction over the parametrization domain Ω≔0,12. The algorithm is illustrated as follows:(1)
Employ an/2×n/2 uniform partition over Ω, that is, Ω=⋃i,j=1n/2Ωij with Ωij=(i-1)/n/2,i/n/2×(j-1)/n/2,j/n/2, i,j=1,…,n/2.(2)
DenoteΩix=⋃jΩij to be the x-axis partition and find the partition set Ωi∗x which contains the greatest number of parametrization vertices.(3)
Divide the partition setΩi∗x into two sets, that is, Ω=⋃i,j=1n/2+1,n/2Ωij with Ωi∗,j=[(i∗-1)/⌊n/2⌋,(i∗-1/2)/⌊n/2⌋]×[(j-1)/⌊n/2⌋,j/⌊n/2⌋], and Ωi∗+1,j=[(i∗-1/2)/⌊n/2⌋,i∗/⌊n/2⌋]×[(j-1)/⌊n/2⌋,j/⌊n/2⌋].(4)
Repeat Steps (2) and (3) until the x-axis partition contains n-1 partition sets.(5)
Apply Steps (2), (3), and (4) on the y-axis partition in a similar fashion.The algorithm yields 2n-1 partition sets Ωixi=1n-1 along x-axis and the other n-1 sets Ωiyi=1n-1 along y-axis. The location of sampling vertices is then given by the intersections of bounding lines of a partition set along x-axis and a partition set along y-axis, and the sampling rate is n×n. We show the sampling result of venus in Figure 2.Figure 2
The vertex density equalization based adaptive sampling overvenus with sampling rate n×n. From (a) to (c): the parametrization mesh, the [n/2]×[n/2] regular sampling mesh, and the vertex density equalization based adaptive sampling mesh, with n=70.
(a)
(b)
(c)


## 3.2. Representation of Hausdorff Distance between Meshes

Hausdorff distance measures the distance between two 3D meshes (see [16]), which is defined by(1)dHM,M′=max⁡dM,M′,dM′,M,(2)dM,M′=maxp∈PMdistp,M′=maxp∈PMminp′∈PM′p-p′.According to the definition, the Hausdorff distance depends only on each face of a mesh together with a small number of faces of the other mesh relatively closed to it. Therefore, in order to speed up the computation of the Hausdorff distance, for each target face of the target mesh, we only choose a few number of faces from the other mesh (i.e., we enlarge the parametrization domain of the target face of the target mesh twice, and the faces are chosen as the faces of the other mesh which share common points with the enlarged target face over the parametrization domain). We illustrate the idea in Figure 3, where S, S′ denote a target face of the target mesh and the selected faces of the sampling mesh, respectively. During the computation of Hausdorff distance from a face S of original mesh to reconstruction mesh, we need to record three pieces of data: the Hausdorff distance d(S,S′) from S to S′, the point p∗ of S which achieves the Hausdorff distance p∗=arg⁡maxp∈PSdist(p,S′), and the face f∗ of S′ which achieves the Hausdorff distance together: f∗=arg⁡minf∈FS′dist(p∗,f). Such process is repeated during the computation of Hausdorff distance from a face S of reconstruction mesh to original mesh.Figure 3
Selection of the associated faces with respect to the target face. Black triangles denote the parametrization mesh, green triangles denote the sampling mesh, and red solid triangle denotes a target faceS. The red dash triangles denote the enlarged face, and the green bold lines denote the collection S′ of the selected faces of the sampling mesh.


## 3.3. Iterative Adjustment of Sampling Vertices

The key step of our scheme is the iterative adjustment of sampling vertices. We first give the distance type judgement between the point and the face which achieve the maximum Hausdorff distance obtained in Section3.2 and then compute the gradient direction of the Hausdorff distance with respect to the vertex/vertices associated with the maximum Hausdorff distance. The adjustment of the vertices is then applied using gradient descent method with suitable step length. The whole algorithm stops when no vertices can be adjusted.(1) Determination of the Distance Type between the Target Point and the Target Face. Similar to [17], the Hausdorff distance between a point and a triangle includes three types: Point-Face, Point-Edge, and Point-Point. We describe the main idea in Figure 4 (see also [17]). We denote p′ to be the projection of p over the plane containing abc. We first judge whether p′ and a lie in the same side or different sides of line bc and judge the relationship of p′ and b with respect to the line ca, as well as the relationship of p′ and c with respect to the line ab. Three judgements give eight cases of results with one of them (i.e., p′ and each of the end-vertices of abc lie in different sides of the corresponding edge) always being invalid. Thus the seven cases of results correspond to the seven cases of locations of p′ corresponding to seven types of Hausdorff distance from p to abc. In detail, we denote (3)lbcx,y=0,lcax,y=0,labx,y=0to be the equations of edges bc, ca, ab, respectively. Then we denote (4)λ1=lbcalbcp′,λ2=lcablcap′,λ3=labclabp′to be three real numbers for distance type determination. The distance type between the point p and the face abc is given by(5)Point-Facep-abcifmax⁡λ1,λ2,λ3>0,Point-Edgep-bcifmin⁡λ2,λ3>0≥λ1,Point-Edgep-caifmin⁡λ3,λ1>0≥λ2,Point-Edgep-abifmin⁡λ1,λ2>0≥λ3,Point-Pointp-aifmin⁡λ2,λ3≤0,Point-Pointp-bifmin⁡λ3,λ1≤0,Point-Pointp-cifmin⁡λ1,λ2≤0.Finally, we obtain the following two distance sets:(6)D1=df,M′:f∈FM,D2=df′,M:f′∈FM′,where D1 (D2, resp.) is the collection of the directed Hausdorff distances from each face of M (M′, resp.) to the reconstruction mesh M′ (original mesh M, resp.), with the directed Hausdorff distances d(f,M′), d(f′,M) defined by (1).Figure 4
Different types of distances between a pointp and a triangle abc.(2) Selection of the Gradient Direction. There are three kinds of objective functions: Point-Face, Point-Edge, and Point-Point and two cases of Hausdorff distance relationship: max⁡D1>max⁡D2 and max⁡D1≤max⁡D2, which produces six kinds of gradient direction. We introduce them in the following three paragraphs.Although verbose equations shall be listed, the main idea is simple. The three cases (Point-Point, Point-Edge, and Point-Face) determine the distance equation [(8), (11), and (14)], and the two cases (max⁡D1>max⁡D2 or max⁡D1≤max⁡D2) determine which point(s) can be moved: when max⁡D1>max⁡D2, we update the location of the target end-vertex (edge, face) on M′ according to the Point-Point (Point-Edge, Point-Face) case; when max⁡D1≤max⁡D2, we update the locations of the end-vertices of the face containing the target point (i.e., the point achieving the greatest Hausdorff distance) on M′.Within the following three paragraphs, we denotep∗=(xp∗,yp∗,zp∗) to be the target point, and denote f∗=q1q2q3 to be the target face; that is, f∗ is the face of the corresponding mesh of p∗ which achieves the maximum distance from p∗. Note that p∗, f∗ belong to different meshes of M, M′. We also denote p1p2p3 to be the face containing p∗ and denote α, β, γ  to be the barycentric coordinate of p∗ with respect to p1p2p3; that is, p∗=αp1+βp2+γp3. We denote (x□,y□,z□) to be the coordinates of the point □ and denote (7)xij=xqi-xqj,yij=yqi-yqj,zij=zqi-zqj,i,j=1,2,3to be the differences of coordinates of q1, q2, q3.(a) Point-Point Optimization. The Point-Point distance from p∗ to an end-vertex q of f∗ is given by(8)dpp2=xq-xp∗2+yq-yp∗2+zq-zp∗2.We compute the gradient of dpp2 in two cases. If max⁡D1>max⁡D2, then p∗∈PM, q∈VM′ and we update the location of q using the gradient of dpp2 with respect to q, which is given by(9)∇qdpp2=2xq-xp∗yq-yp∗zq-zp∗⊤.Otherwise, max⁡D1≤max⁡D2 holds; then we have p∗∈PM′, q∈VM and we shall update the locations of p1, p2, p3. Thus we compute the gradient of dpp2 with respect to p1, p2, p3 by(10)∇p1;p2;p3dpp2=2αM1βM1γM1withM1=xp∗-xqyp∗-yqzp∗-zq,where we use the notation ∇{q1;…;qm}d for concatenating the gradient of d(q1,…,qm) with respect to m points {q1,…,qm}⊆R3 to form a vector of R3m.(b) Point-Edge Optimization. Let q1=(x1,y1,z1), q2=(x2,y2,z2) be two end-vertices of the triangle q1q2q3. The Point-Edge distance from p∗ to the edge q1q2 is given by(11)dpe2=yp∗-yq1z12-zp∗-zq1y122+zp∗-zq1x12-xp∗-xq1z122+xp∗-xq1y12-yp∗-yq1x122x122+y122+z122.If max⁡D1>max⁡D2, then p∗∈PM, q1q2∈EM′ hold, and we shall update the locations q1, q2 with the gradient of dpe2 given by (16). Otherwise, we have p∗∈PM′, q1q2∈EM, and we update all the end-vertices of the face containing p∗. The gradient of dpe2 with respect to all the end-vertices of the face is given by(12)∇p1;p2;p3dpe2=2x122+y122+z122αM2βM2γM2x12y12z12withM2=0xp∗-xq1y12xp∗-xq1z12yp∗-yq1x12-yp∗-yq1x12-zp∗-zq1x12-xp∗-xq1y120yp∗-yq1z12zp∗-zq1x12zp∗-zq1y12-zp∗-zq1y12-xp∗-xq1z12-yp∗-yq1z120.(c) Point-Face Optimization. We denote(13)a=yq1z23+yq2z31+yq3z12,b=zq1x23+zq2x31+zq3x12,c=xq1y23+xq2y31+xq3y12,g=xq1yq3zq2-yq2zq3+xq2yq1zq3-yq3zq1+xq3yq2zq1-yq1zq2to be the coefficients of the equation of the plane where the face q1q2q3 lies, and the Point-Face distance from p∗ to the face q1q2q3 is given by(14)dpf2=axp∗+byp∗+czp∗+g2a2+b2+c2.If max⁡D1>max⁡D2, then p∗∈PM, q1q2q3∈FM′ and we shall update the locations of q1, q2, q3 using the gradient of dpf2 given by (17). Otherwise, we update the locations of p1, p2, p3 with the gradient of dpf2 given by(15)∇p1;p2;p3dpf2=2a2+b2+c2αM3βM3γM3xp∗yp∗zp∗1withM3=a2abacagabb2bcbgacbcc2cg.In summary, we show Algorithm1 for generating the Hausdorff distance geometry images, where we compute the gradient of the directional Hausdorff distance square d2 in six cases according to the distance type and the quantitative relationship of max⁡D1 and max⁡D2. Note that when max⁡D1>max⁡D2, we update the end-vertices of the target face f∗ on M′ (see Algorithm 2); when max⁡D1≤max⁡D2, we update the end-vertices of the face p1p2p3 containing p∗ on M′ (see Algorithm 3). For each of the six cases, we compute the stepsize ρk,k=0,…,K which admits decreasing of the Hausdorff distance; the algorithm terminates provided that no such stepsize can be found.(16)∇q1;q2dpe2=2x122+y122+z122zp∗-zq2yp∗-yq2x21xp∗-xq2zp∗-zq2y21yp∗-yq2xp∗-xq2z21zq1-zp∗yq1-yp∗x12xq1-xp∗zq1-zp∗y12yq1-yp∗xq1-xp∗z12zp∗-zq1x12-xp∗-xq1z12yp∗-yq1x12-xp∗-xq1y12dpe2.(17)∇q1;q2;q3dpf2=2h0z32y23zq2yq3-yq2zq3z230x32xq2zq3-zq2xq3y32x230yq2xq3-xq2yq30z13y31zq3yq1-yq3zq1z310x13xq3zq1-zq3xq1y13x310yq3xq1-xq3yq10z21y12zq1yq2-yq1zq2z120x21xq1zq2-zq1xq2y21x120yq1xq2-xq1yq2xp∗yp∗zp∗1+2h20z23y32z320x23y23x3200z31y13z130x31y31x1300z12y21z210x12y12x210abcwithh=axp∗+byp∗+czp∗+ga2+b2+c2Algorithm 1:Optimal Hausdorff error driven geometry images.
Input. A mesh M and stepsize threshold K=100
Output. The 3D location of vertices of GIM mesh M′
(
1
) Apply vertex density equalization on M (Section 3.1);
(
2
) Compute D1,D2 using (6) (Section 3.2);
(
3
)  If  max⁡D1>max⁡D2  then
(
4
)   Compute the target point p∗←argmaxp∈PM⁡dist(p,M′);
(
5
)   Compute the target face f∗←argmaxf∈FM′⁡dist(p∗,f);
(
6
)  Judge the distance type between p∗ and f∗ using (5);
(
7
)   Update the position of the end-vertices of f∗ using Algorithm 2;
(
8
)  else
(
9
)    Compute the target point p∗←argmaxp∈PM′⁡dist(p,M);
(
10
)  Compute the target face f∗←argmaxf∈FM⁡dist(p∗,f);
(
11
)  Judge the distance type between p∗ and f∗ using (5);
(
12
)  Update the position of the end-vertices of f∗ using Algorithm 3;
(
13
)  endAlgorithm 2:Update the position of end-vertices of target face f∗ when max⁡D1>max⁡D2.
Input.  A target point p∗, a target face f∗, a mesh M and stepsize threshold K=100, ρ=1/2
Output. New locations of the end-vertices of the face f∗
(
1
)    switch   Distance Type  do
(
2
)   case  Point-Point
(
3
)    Find the closest end-vertex  q of f∗ from p∗ by q←argminq∈Vf∗p∗-q;
(
4
)    Compute the gradient ∇qdpp2 using (9);
(
5
)      for  k=0,…,K  do
(
6
)     Update the Hausdorff distance set D1pp(k) using (6) with q replaced by q-ρk∇qdpp2;
(
7
)       if  max⁡D1pp(k)<max⁡D1  then
(
8
)      Update q by q←q-ρk∇qdpp2;
(
9
)      Break;
(
10
)    end
(
11
)   end
(
12
)   if  max⁡D1pp(k)≥max⁡D1,∀k=0,…,K  then
End the algorithm;
(
13
)    case  Point-Edge
(14)    Find the closest edge off′ from p∗ by e′←argmine∈Ef∗dist(p∗,e);
(15)    Denoteq1,q2 to be the end-vertices of e′;
(16)    Compute the gradient∇[q1;q2]dpe2 using (16);
(17)for  k=0,…,K  do
(18)      Update the Hausdorff distance setD1pe(k) using (6) with q1,q2 replaced by [q1;q2]-ρk∇[q1;q2]dpe2;
(19)if  max⁡D1pe(k)<max⁡D1then
(20)      Updateq1,q2 by [q1;q2]←[q1;q2]-ρk∇[q1;q2]dpe2;
(21)       Break;
(22)end
(23)end
(24)if  max⁡D1pe(k)≥max⁡D1,∀k=0,…,K  then
End the algorithm;
(25)case  Point-Face
(26)    Denoteq1,q2,q3 to be the end-vertices of f∗;
(27)    Compute the gradient∇[q1;q2;q3]dpf2 using (17);
(28)for  k=0,…,K  do
(29)     Update the Hausdorff distance setD1pf(k) using (6) with q1,q2,q3 replaced by [q1;q2;q3]-ρk∇[q1;q2;q3]dpf2;
(30)if  max⁡D1pf(k)<max⁡D1  then
(31)      Updateq1,q2,q3 by [q1;q2;q3]←[q1;q2;q3]-ρk∇[q1;q2;q3]dpf2;
(32)      Break;
(33)end
(34)end
(35)if  max⁡D1pf(k)≥max⁡D1,∀k=0,…,K  then
End the algorithm;
(36)endsw
(37)endswAlgorithm 3:Update the position of end-vertices of the face containing p∗ when max⁡D1≤max⁡D2.
Input.  A target point p∗, a target face f∗, a mesh M and stepsize threshold K=100, ρ=1/2
Output. New locations of the end-vertices of the face p1p2p3
(
1
)   switch   Distance Type  do
(
2
)    case  Point-Point
(
3
)     Compute the gradient ∇[p1;p2;p3]dpp2 using (10);
(
4
)        for  k=0,…,K  do
(
5
)      Update the Hausdorff distance set D2pp(k) using (6) with p1,p2,p3 replaced by [p1;p2;p3]-ρk∇[p1;p2;p3]dpp2;
(
6
)       if  max⁡D2pp(k)<max⁡D2  then
(
7
)       Update p1,p2,p3 by [p1;p2;p3]←[p1;p2;p3]-ρk∇[p1;p2;p3]dpp2;
(
8
)       Break;
(
9
)       end
(
10
)     end
(
11
)     if  max⁡D2pp(k)≥max⁡D2,∀k=0,…,K  then
End the algorithm;
(
12
)    case  Point-Edge
(
13
)     Compute the gradient ∇[p1;p2;p3]dpe2 using (12);
(14)for  k=0,…,K do
(15)      Update the Hausdorff distance setD2pe using (6) with p1,p2,p3 replaced by [p1;p2;p3]-ρk∇[p1;p2;p3]dpe2;
(16)if max⁡D2pe(k)<max⁡D2  then
(17)       Updatep1,p2,p3 by [p1;p2;p3]←[p1;p2;p3]-ρk∇[p1;p2;p3]dpe2;
(18)       Break;
(19)end
(20)end
(21)if  max⁡D2pe(k)≥max⁡D2,∀k=0,…,K  then
End the algorithm;
(22)case  Point-Face
(23)     Compute the gradient∇[p1;p2;p3]dpf2 using (15);
(24)for  k=0,…,K  do
(25)      Update the Hausdorff distance setD2pf using (6) with p1,p2,p3 replaced by [p1;p2;p3]-ρk∇[p1;p2;p3]dpf2;
(26)if  max⁡D2pf(k)<max⁡D2  then
(27)       Updatep1,p2,p3 by [p1;p2;p3]←[p1;p2;p3]-ρk∇[p1;p2;p3]dpf2;
(28)       Break;
(29)end
(30)end
(31)if  max⁡D2pf(k)≥max⁡D2,∀k=0,…,K  then
End the algorithm;
(32)endsw
(33)endsw


## 4. Enhanced ROI Geometry Images

Region-of-Interest (ROI) is the area that attracts the attention of human visual attention, and the other area is called non-Region-of-Interest (non-ROI). While it is difficult to directly select ROI on the geometry image, the normal vector coordinates from normal images can accurately reflect the original triangular mesh surface’s details. Figure5 shows the geometry image and the normal image of the foot model. When we select the ROI, the normal vector image can be used. The first and second subfigures of Figure 6 illustrate the selection of ROI, where the left subfigure marks the region which contains more information of the model than the region in the middle subfigure.Figure 5
Geometry image (b) and normal-map image (c) for foot.
(a)
(b)
(c)Figure 6
ROI selection for foot. From (a) to (c): ROI selection with more details, ROI selection with less details, and the ROI/non-ROI selection scheme.
(a)
(b)
(c)After the ROI is selected, we transform the ROI of the normal images into the parametrization domain and divide it into five regions according to the right subfigure of Figure6. We calculate the number of vertices of the parameterized mesh and the number of vertices of the reconstructed mesh within the five regions, respectively. To give a suitable setting of weights of non-ROI vertices, we denote nideal=(nc/VM)n2 as the ideal number of sampling points in each non-ROI, where nc is the number of the parameterized mesh vertex and n is the sampling rate. For the four non-ROI, we use the actual number of the reconstructed mesh vertex minus nideal to obtain four values and arrange them in a descending order. Negative value indicates the insufficient number of sampling points in this area, while positive value indicates the redundant number of sampling points. Finally, the weights are assigned from low to high according to this order. While the weight of ROI is the highest, the weight of each non-ROI region is the same.Vertex movement must be in its first order domain to ensure that the topology of the final mesh is unchanged. We definepnew=(∑i=16‍wip0-pipi)/∑i=16‍wip0-pi to be the new position of the moving point, where wi is the weight of the region in which the point locates and pi are the 2D coordinates of one-ring neighborhood of p0 (note that the definition of pnew tends to move each sampling vertex towards the greater-weight direction within its 1-ring neighborhood). The increasing number of sampling points in the ROI is defined by user. After the increase of the sampling points in the ROI, we use the adaptive sampling scheme of Section 3.3 over ROI, where the optimization function is the directed Hausdorff distance from ROI to the original mesh instead of the symmetric Hausdorff distance, so that the distribution of sampling points of ROI is more suitable.


## 5. Experimental Results

We show experimental results in this section. The first subsection shows the Hausdorff error driven geometry images while the second subsection shows geometry images with enhanced ROI reconstruction. Both qualitative results and quantitative results are compared. The second subsection also shows results with image compression with JPEG2000 codec.


### 5.1. Optimal Hausdorff Error Driven Geometry Images

We use two kinds of parametrization method: barycentric parametrization [18] and geometric-stretch parametrization [19] and three sampling methods: regular sampling, [4]’s adaptive sampling, and vertex density equalization adaptive sampling. We do three groups of experiments. Qualitative results are shown in Figure 7, where each column from left to right is the original model, [4]’s sampling model, the regular sampling model, and our sampling model.Figure 7
Qualitative results with different models. From (a) to (d): the original model, [4]’s sampling model, the regular sampling model, and our sampling model.
(a)
(b)
(c)
(d)Table1 shows details of the five models, such as the number of faces and vertices, as well as the reconstruction PSNRs and Hausdorff errors of models before adaptive sampling and after adaptive sampling. Under the specified sampling rate, we can see that our method achieves the greatest PSNR among all methods. By optimizing the reconstructed mesh, the Hausdorff error is reduced. With the same parametrization method, we see from the comparative results that our sampling method is better than [4]’s sampling method. Because [4]’s method adjusts the sampling points which is based on regular sampling; the effect of the sampling rate is decided by the effect of the sampling rate. Different adjustment times can be obtained for different reconstructed meshes. However, with the increase of adjustment times, the sampling points are distributed within the region of the parametrization domain where more vertices concentrate. In [4], in order to preserve the edge information, detailed regions may not reach the expected reconstruction accuracy. If the detailed regions are up to reconstruction accuracy, the edge information may be lost. Figure 8 shows different reconstructions in terms of different times of adjustment, where the first row of black mesh is a parametrization mesh and the red mesh is sampling mesh.Table 1
Comparative results of PSNR values of reconstructed models.
Model
Face
Vertex
Sampling
Regular
PSNR by
PSNR by
Hausdorff error
Num
Num
Rate
Sampling
Zhou et al. [4]
Our model
Before AS
After AS
C
a
t
h
e
a
d
248
131
45
∗
45
47.1377
47.6548
51.7978
0.1379
0.0625
V
e
n
u
s
1396
711
70
∗
70
50.3154
50.5554
58.9261
0.8178
0.0577
C
a
m
e
l
22704
11381
180
∗
180
61.4743
56.6976
71.2418
0.0102
0.0055
F
o
o
t
19974
10010
180
∗
180
66.4185
51.8281
71.3321
0.0170
0.0129
M
a
n
n
e
q
u
i
n
25888
12977
300
∗
300
59.0039
50.2263
68.4832
1.6027
0.2300Figure 8
Adaptive sampling for different times of adjustment. From (a) to (c) are original mesh, reconstruction mesh after twice adaptive sampling, and reconstruction mesh after 15 times of adaptive sampling.
(a)
(b)
(c)Two methods use different parametrization strategies, and the effect of the barycentric mapping method is worse than the geometric-stretch parametrization method. Figure9 shows comparative results of the regular sampling and our adaptive sampling, where the reconstruction effect within some detailed regions of ours method is better than the regular sampling method.Figure 9
Qualitative results of regular sampling method (a) and our method (b).
(a)
(b)


### 5.2. Enhanced ROI Geometry Images

Experiments of enhanced ROI geometry images are given by enhancing the number of ROI sampling points before adaptive sampling and after adaptive sampling. We mainly used the barycentric mapping and regular sampling. The sampling rates are40∗40 (cathead), 80∗80 (fist), 150∗150 (foot), and 300∗300 (davidhead).Figure10 shows the qualitative results of ROI reconstructions using different sampling schemes, where the second row is the ROI of original meshes, the third row is the ROI reconstructions using regular sampling, and the fourth row is the ROI reconstructions using enhanced ROI adaptive sampling. We can see from the figure that the sampling number of ROI can be increased, which improves the quality of the reconstruction of ROI.Figure 10
Qualitative results of ROI reconstruction. (a) to (d): original meshes, amplified details, reconstructions with traditional sampling rate, and reconstructions with increasing sampling.
(a)
(b)
(c)
(d)Figure11 shows the qualitative results of ROI reconstructions using JPEG2000 with non-ROI and ROI codecs, where the second row is the ROI reconstructions using non-ROI JPEG2000 codec, and the third row is the ROI reconstructions using ROI JPEG2000 codec, both of which are under the same compression rate. We can see that the reconstruction meshes using ROI codec keep more detailed information than the reconstruction meshes using non-ROI codec.Figure 11
Qualitative results of ROI compression with JPEG2000 codec. (a) to (c): original meshes, reconstructions using non-ROI compression, and reconstructions using ROI compression.
(a)
(b)
(c)Table2 shows quantitative results of enhanced ROI geometry images and traditional geometry images, which indicates that the Hausdorff error is reduced after our adaptive sampling is applied. Moreover, the more sampling points the ROI has, the higher reconstruction precision of ROI we obtain.Table 2
Hausdorff error of different models using ROI sampling scheme.
Model
ROI sampling num
Hausdorff error
Rate
Hausdorff error
Before AS
After AS
Before AS
After AS
Non-ROI compress
ROI compress
C
a
t
h
e
a
d
30
147
0.0933
0.0657
1.2
1.1077
0.0931
F
i
s
t
16
717
0.0963
0.0129
0.7
0.0381
0.0341
F
o
o
t
169
1218
0.1557
0.0367
0.1
0.0767
0.0517
D
a
v
i
d
h
e
a
d
110
360
0.0168
0.0103
0.1
0.0252
0.0251


## 5.1. Optimal Hausdorff Error Driven Geometry Images

We use two kinds of parametrization method: barycentric parametrization [18] and geometric-stretch parametrization [19] and three sampling methods: regular sampling, [4]’s adaptive sampling, and vertex density equalization adaptive sampling. We do three groups of experiments. Qualitative results are shown in Figure 7, where each column from left to right is the original model, [4]’s sampling model, the regular sampling model, and our sampling model.Figure 7
Qualitative results with different models. From (a) to (d): the original model, [4]’s sampling model, the regular sampling model, and our sampling model.
(a)
(b)
(c)
(d)Table1 shows details of the five models, such as the number of faces and vertices, as well as the reconstruction PSNRs and Hausdorff errors of models before adaptive sampling and after adaptive sampling. Under the specified sampling rate, we can see that our method achieves the greatest PSNR among all methods. By optimizing the reconstructed mesh, the Hausdorff error is reduced. With the same parametrization method, we see from the comparative results that our sampling method is better than [4]’s sampling method. Because [4]’s method adjusts the sampling points which is based on regular sampling; the effect of the sampling rate is decided by the effect of the sampling rate. Different adjustment times can be obtained for different reconstructed meshes. However, with the increase of adjustment times, the sampling points are distributed within the region of the parametrization domain where more vertices concentrate. In [4], in order to preserve the edge information, detailed regions may not reach the expected reconstruction accuracy. If the detailed regions are up to reconstruction accuracy, the edge information may be lost. Figure 8 shows different reconstructions in terms of different times of adjustment, where the first row of black mesh is a parametrization mesh and the red mesh is sampling mesh.Table 1
Comparative results of PSNR values of reconstructed models.
Model
Face
Vertex
Sampling
Regular
PSNR by
PSNR by
Hausdorff error
Num
Num
Rate
Sampling
Zhou et al. [4]
Our model
Before AS
After AS
C
a
t
h
e
a
d
248
131
45
∗
45
47.1377
47.6548
51.7978
0.1379
0.0625
V
e
n
u
s
1396
711
70
∗
70
50.3154
50.5554
58.9261
0.8178
0.0577
C
a
m
e
l
22704
11381
180
∗
180
61.4743
56.6976
71.2418
0.0102
0.0055
F
o
o
t
19974
10010
180
∗
180
66.4185
51.8281
71.3321
0.0170
0.0129
M
a
n
n
e
q
u
i
n
25888
12977
300
∗
300
59.0039
50.2263
68.4832
1.6027
0.2300Figure 8
Adaptive sampling for different times of adjustment. From (a) to (c) are original mesh, reconstruction mesh after twice adaptive sampling, and reconstruction mesh after 15 times of adaptive sampling.
(a)
(b)
(c)Two methods use different parametrization strategies, and the effect of the barycentric mapping method is worse than the geometric-stretch parametrization method. Figure9 shows comparative results of the regular sampling and our adaptive sampling, where the reconstruction effect within some detailed regions of ours method is better than the regular sampling method.Figure 9
Qualitative results of regular sampling method (a) and our method (b).
(a)
(b)


## 5.2. Enhanced ROI Geometry Images

Experiments of enhanced ROI geometry images are given by enhancing the number of ROI sampling points before adaptive sampling and after adaptive sampling. We mainly used the barycentric mapping and regular sampling. The sampling rates are40∗40 (cathead), 80∗80 (fist), 150∗150 (foot), and 300∗300 (davidhead).Figure10 shows the qualitative results of ROI reconstructions using different sampling schemes, where the second row is the ROI of original meshes, the third row is the ROI reconstructions using regular sampling, and the fourth row is the ROI reconstructions using enhanced ROI adaptive sampling. We can see from the figure that the sampling number of ROI can be increased, which improves the quality of the reconstruction of ROI.Figure 10
Qualitative results of ROI reconstruction. (a) to (d): original meshes, amplified details, reconstructions with traditional sampling rate, and reconstructions with increasing sampling.
(a)
(b)
(c)
(d)Figure11 shows the qualitative results of ROI reconstructions using JPEG2000 with non-ROI and ROI codecs, where the second row is the ROI reconstructions using non-ROI JPEG2000 codec, and the third row is the ROI reconstructions using ROI JPEG2000 codec, both of which are under the same compression rate. We can see that the reconstruction meshes using ROI codec keep more detailed information than the reconstruction meshes using non-ROI codec.Figure 11
Qualitative results of ROI compression with JPEG2000 codec. (a) to (c): original meshes, reconstructions using non-ROI compression, and reconstructions using ROI compression.
(a)
(b)
(c)Table2 shows quantitative results of enhanced ROI geometry images and traditional geometry images, which indicates that the Hausdorff error is reduced after our adaptive sampling is applied. Moreover, the more sampling points the ROI has, the higher reconstruction precision of ROI we obtain.Table 2
Hausdorff error of different models using ROI sampling scheme.
Model
ROI sampling num
Hausdorff error
Rate
Hausdorff error
Before AS
After AS
Before AS
After AS
Non-ROI compress
ROI compress
C
a
t
h
e
a
d
30
147
0.0933
0.0657
1.2
1.1077
0.0931
F
i
s
t
16
717
0.0963
0.0129
0.7
0.0381
0.0341
F
o
o
t
169
1218
0.1557
0.0367
0.1
0.0767
0.0517
D
a
v
i
d
h
e
a
d
110
360
0.0168
0.0103
0.1
0.0252
0.0251


## 6. Conclusions

We propose two kinds of adaptive geometry images for remeshing triangular meshes. The first scheme, referred to as Hausdorff error driven geometry images, achieves minimum Hasdorff distance between original meshes and reconstructed meshes. The second scheme, referred to as enhanced ROI geometry images, preserves more details over ROI regions. Experimental results show the effectiveness of our method compared with traditional regular sampling based geometry images. In future work, we shall improve our models by computing Hausdorff distance between meshes using local maximum instead of global one; also we shall consider the parallel implementation of adjusting sample vertices.



---

*Source: 2724184-2017-08-02.xml*