# Global Parameterization-based Texture Space Optimization

Wei Chen  Yuxue Ren  Na Lei<EMAIL_ADDRESS>Zhongxuan Luo  Xianfeng Gu
Academy for Multidisciplinary Studies, Capital Normal University  Beijing
Advanced Innovation Center for Imaging Theory and Technology, Capital Normal
University  DUT-RU ISE, Dalian University of Technology  School of Software
Technology, Dalian University of Technology  State University of New York at
Stony Brook, Stony Brook

###### Abstract

Texture mapping is a common technology in the area of computer graphics, it
maps the 3D surface space onto the 2D texture space. However, the loose
texture space will reduce the efficiency of data storage and GPU memory
addressing in the rendering process. Many of the existing methods focus on
repacking given textures, but they still suffer from high computational cost
and hardly produce a wholly tight texture space. In this paper, we propose a
method to optimize the texture space and produce a new texture mapping which
is compact based on global parameterization. The proposed method is
computationally robust and efficient. Experiments show the effectiveness of
the proposed method and the potency in improving the storage and rendering
efficiency.

###### keywords:

texture space optimization, global parameterization, harmonic mapping, texture
mapping

††journal: Comput. Math. Math. Phys.

textheight=677pt, textwidth=463pt

##  1 Introduction

With rapid development in three-dimensional data acquisition techniques over
the last few decades, high resolution model with one or multiple texture
images has been produced for a large number of applications. However, many
existing model reconstruction methods introduce blank spaces and needless
pixels in the attached texture images of the reconstructed models, which make
them intractable to perform subsequent storage and computation tasks, such as
graphics processing unit (GPU) rendering.

As one of the geometry processing techniques, the space-oriented texture
optimization aims to decrease or remove the blank spaces and the needless
pixels of the existing texture images so that an optimized texture space will
be generated. Success in space-oriented texture optimization is significantly
beneficial to the data storage efficiency and GPU memory addressing in the
rendering process. In the research area of optimizing textures of 3D models,
we have witnessed a variety of methods over the past decades. Most of these
methods optimize the texture space by stretching, shrinking and packing parts
of a texture image [1, 23, 21, 16, 32]. However, a few limitations exist in
these methods, which lie in either incomplete utilization ratio which cannot
take full use of texture space, or multiple texture atlases which reduce the
efficiency of GPU memory addressing. In some extreme situations, unguaranteed
computation of texture mapping due to poor quality of models’ triangulation is
also a restriction for the application.

In more recent years, 3D modeling has attracted broad attention from the 3D
computer vision community due to the popularity of virtual reality (VR),
augmented reality (AR) and metaverse. And photogrammetry is one of the widely
used technologies in the field of 3D modeling, it usually produces
sophisticated or large scene 3D models with multiple textures. When the data
is imported into the VR, AR or metaverse platforms, the real-time performance
becomes crucial and important. Therefore, in the area of texture optimization
of photogrammetry, generating a tight and global texture space via surface
parameterization not only benefits the data storage efficiency on the hard
disk and the random access memory (RAM), but also enables the improvement of
GPU rendering via speeding up the texture addressing.

In this work, we propose a novel fast and robust space-oriented texture
optimization method. The algorithm is detailed in some steps involving
computations of hole filling, topological denoising, cut graph, and
parameterization. The main contributions in this work are as follows:
(1). Novel framework. Our proposed algorithm is novel and first applied to the
space-oriented texture optimization based on global parameterization. It
avoids repacking the atlas charts which is considered a NP-hard problem [15,
24].
(2). Fast and robust computation. Benefit from the fast and robust algorithms
of harmonic map and topological denoising, our method is computationally
efficient and robust.
(3). Efficient result. Compared with existing methods based on texture patches
repacking, our algorithm produces one or multiple new textures with no
redundant space or pixel.

##  2 Related Work

Numerous methods have been proposed for the texture space optimization. Frueh
et al. [14] proposed an approach to packing multiple textures of a model into
one single texture atlas in order to optimize the model for rendering
purposes, then it simply use a greedy algorithm which copies contiguous
texture patches and places them into available space in the atlas. Lévy et al.
[21] designed a surface parameterization method based on least-squares
approximation of the Cauchy-Riemann equations. And then they segmented the
computed texture atlas into several charts with natural shapes. Thirdly each
chart is rescaled to make its area in texture space equals to its area in
surface space. At last, before inserting these charts one by one, they are
oriented vertically based on the maximum diameter and sorted in decreasing
order. Balmelli et al. [1] presented a new texture optimization algorithm
based on the reduction of the physical space allotted to the texture image,
the result image is stretched in high frequency areas and shrunk in low
frequency regions, but there still exists redundancy spaces and pixels. Nöll
et al. [27] introduced the new search space of modulo valid packings, the key
idea was to allow the texture charts to wrap around in the atlas, then based
on this search space they proposed an algorithm that can be used to pack
texture atlases automatically.

Recently, Odaker et al. [29] proposed an approach that aims to remove the
redundancies in order to reduce the amount of memory required to store the
texture data. In that work, the per-triangle textures are compiled into a new
set of texture images of user defined size. The final texture data is packed
as tightly as possible. Limper et al. [22] utilized the box cutter technology
to refine the texture atlas by eliminating spaces iteratively. This method
improves packing efficiency without changing distortion by strategically
cutting and repacking the atlas charts. Therefore it preserves the local
mapping between the 3D surface and the atlas charts.

All the methods above can be summarized into the problem of how to pack 2D
charts efficiently inside the texture rectangle. It is also considered to be a
problem of polygon packing which is a combinatorial optimization problem in
the field of computational geometry. However, maximizing the packing
efficiency for a given set of charts is a NP-hard problem [15, 24], thus it
can only be deal with empirically.

##  3 Theoretic Background

This section briefly explains the basic concepts and theorems referred in this
paper.

Suppose $S$ is a smooth surface, and polygonal mesh $M$ is a discretization of
the surface $S$, Fig. 1 gives an example of a smooth surface and a polygonal
mesh.

(a) (b)

Figure 1:  Smooth surface and its discretization: 1(a) a smooth surface of a
girl, 1(b) a discretization version of the surface which is a polygon mesh
here.

######  Definition 1 (Genus)

Given a surface $S$, the number of its handles is called the _genus_ of the
surface.

The surface’s genus is the major topological invariant. We can imagine that
the surface is made of elastic rubber, it can be stretched and compressed but
not be tore up. Topology only consider the global properties of a space. For
example, there is a model in the left picture in Fig. 2, it can be deformed
elastically to a unit sphere surface without tearing the surface.

(a) (b) (c)

Figure 2:  Surfaces with different genus: 2(a) genus zero surfaces, 2(b) genus
one surfaces, and 2(c) genus two surfaces. The two surfaces in each picture
have the same genus.

Given any point $p$ on surface $S$, if the local neighbourhood of $p$ is
always homeomorphous to a unit disk, then $S$ is a _closed_ surface. Or simply
speaking, a surface is closed if there is no boundary on it. However, not all
of the surface are closed.

######  Definition 2 (Boundary)

Suppose surface $S$ is a subset of a topological space $X$, the _boundary_ of
the surface $\partial S$ is the closure of $S$ minus the interior of $S$ in
$X$.

A surface with boundaries is called an _open_ surface. The number of
boundaries is also a topological invariant. In Fig. 3(b), the surface is
sliced by its cut graph, then it obviously has one boundary, and is
topologically equivalent to a unit disk.

######  Definition 3 (Cut Graph)

Given a closed mesh $M$, a _cut graph_ is a set of edges ${e_{i}}$, which
could cut the mesh into a topological disk.

If a closed mesh is sliced by its cut graph, the result mesh is called its
_fundamental domain_. For example, in Fig. 3 the right image shows the
fundamental domain of the input mesh.

(a) (b)

Figure 3:  Cut graph of a mesh: 3(a) an input mesh, 3(b) the fundamental
domain produced by slicing along the cut graph in red.

Let $S$ be a simply connected, closed and orientable surface, embedded in the
Euclidean space $\mathbb{R}^{3}$. We compactify $\mathbb{R}^{3}$ to a three-
dimensional sphere $\mathbb{S}^{3}$ by adding one infinity point $\infty$,
then the open set of the infinity

$U_{r}=\\{(x,y,z)|x^{2}+y^{2}+z^{2}>r^{2}\\},$

where $r$ is the radius of sphere $\mathbb{S}^{3}$.

Surface $S$ separate $\mathbb{S}^{3}$ into two parts, the inside part $I$ and
the outside part $O$. We define two sets

$I_{S}=I\cup S,O_{S}=O\cup S.$

######  Definition 4 (Handle Loop)

A loop on $S$ is a _handle loop_ if the homology class carried by it is
trivial in $I_{S}$’s homology group $H_{1}(I_{S})$ and non trivial in
$O_{S}$’s homology group $H_{1}(O_{S})$.

######  Definition 5 (Tunnel Loop)

A loop on $S$ is a _tunnel loop_ if the homology class carried by it is
trivial in $H_{1}(O_{S})$ and non trivial in $H_{1}(I_{S})$.

The following theorem shows that the tunnel and handle loops are unique and
form a homology basis [6].

######  Theorem 1 (Handle and Tunel Loops)

For any connected closed surface $S\hookrightarrow\mathbb{S}^{3}$ embedded in
the three-dimensional sphere $\mathbb{S}^{3}$ of genus $g$, there exists $g$
handle loops $\\{h_{1},h_{2},...,h_{g}\\}$ forming a basis for $H_{1}(O_{S})$
and $g$ tunnel loops $\\{t_{1},t_{2},...,t_{g}\\}$ forming a basis for
$H_{1}(I_{S})$. Furthermore, $\\{h_{1},h_{2},...,h_{g}\\}$ and
$\\{t_{1},t_{2},...,t_{g}\\}$ form a basis for $H_{1}(S)$.

The first proof is given in the work [6] by Dey et al.

For instance, in Fig. 4, the left figure is a genus three surface, it has
three handle loops and three tunnel loops which are colored in green and red
respectively. All of the six loops form a basis of its homology group.

(a) (b)

Figure 4:  Handle and tunnel loops: 4(a) a closed surface of genus three, 4(b)
the green lines show the handle loops, and the red lines show the tunnel
loops.

In differential geometry, a parametric curve is defined as a function from
$\mathbb{R}$ to $\mathbb{R}^{2}$ (plane curve) or $\mathbb{R}$ to
$\mathbb{R}^{3}$ (space curve). This definition can be extended to surface
situation.

######  Definition 6 (Parameterized Surface)

A _parameterized surface_ $S:U\subset\mathbb{R}^{2}\to\mathbb{R}^{3}$ is a
differentiable map from an open set $U\subset\mathbb{R}^{2}$ into
$\mathbb{R}^{3}$.

In this paper, we use harmonic map, which will be described in Section 4.2, to
construct a desired parameterized surface.

##  4 Proposed Method and Algorithm

In a general way, the texture space of a 3D model produced by the technology
of photogrammetry is divided into several parts. Also, there are a mess of
blank spaces between these parted domains.

In this section, we will give an overview framework for optimizing the texture
space first, and then the details of each step will be discussed separately.

Since the pipeline of 3D modeling in photogrammetry is mainly divided into two
steps: image registration and texture selection. This method hardly avoids the
fragmentation of texture space. We propose a novel method to compute a new
texture mapping and corresponding texture image, it will fully eliminate the
blank space in the texture space and unnecessary pixels.

###  4.1 Data Preparation

In the step of data preparation, a model of topological disk is needed for
computing a global parameterization. Therefore there are three sub-steps for
data preparation. The first one is to fix the non-manifold elements. The
second one is hole filling. The last one, which is also the most difficult
part of the three, is topological denoising.

There maybe exists non-manifold elements in the input 3D model, but this can
be worked out by simply slicing the non-manifold vertices and edges. If the
model is sliced into two or more parts, then we process them separately.

Sometimes a few holes, most of them are small, also exist on the models, they
can be filled directly. Suppose the hole or boundary is denoted as
$B=\\{e_{0},e_{1},...,e_{n-1}\\}$, it consists of $n$ edges, each edge
$e_{i}=(v_{i},v_{i+1}),i=0,1,...n-1,v_{0}=v_{n}$, so there are also $n$
vertices on the boundary. We create a new vertex $v_{new}$ which its
coordinate equals to $\frac{1}{n}\sum_{i=0}^{n-1}coord(v_{i})$, then $n$ new
faces $f_{i}=(v_{new},v_{i},v_{i+1})$ are inserted into the model to close one
hole.

After eliminating the non-manifold elements and filling the small holes, the
input mesh becomes a closed mesh with genus $g$. Usually, these minor handles
are topological noises, there are several methods to detect them, some of the
methods are based on homotopy and homology [13, 4, 8], and some are based on
graph structures such as Reeb graph, core graph, medical axis or curve
skeletons [5, 6, 7, 12, 37]. In our work, we use the homology based method to
remove the topological noises since its robustness and efficiency compared
with other methods. Fig. 5 shows two examples for detecting the handles.

(a) (b)

Figure 5:  Topological denoising based on homology detection, the green loops
are the handle or tunnel loops, which their number is equal to the genus of
the surface. 5(a) a simple surface with genus $2$, 5(b) a complicated surface
with genus $25$.

###  4.2 Global Parameterization Based on Harmonic Map

A harmonic map $H:M\to D$ can be considered as an planar embedding from a
space surface $M$ of topological disk to a planar domain $D$, where $D$ is a
convex domain, and in our paper, we always consider $D$ is a unit square. A
harmonic map is always the extreme point for the harmonic energy function,

$E(H)=\int_{M}|dH|^{2}d\mu_{M},$

where the norm of differential $dH$ is given by the metric on $M$ and $D$, and
$d\mu_{M}$ is the measure on $M$ [11, 10, 33, 30]. $H$ can be solved by
minimizing $E(H)$.

In order to solve the harmonic map $H$, $H$ can be represented as a pair of
functions $(H_{1},H_{2})$, where $H_{i}:M\to\mathbb{R},i\in\\{1,2\\}$. In this
paper, $(H_{1},H_{2})$ is the parametric coordinate $(u,v)$ in the unit square
$D$. Therefore, the harmonic energy can be expressed as

$E(H)=\int_{M}(|\nabla H_{1}|^{2}+|\nabla H_{2}|^{2}).$

To minimizing the harmonic energy, a harmonic map can be solved by the Euler-
Lagrange differential equation of the energy functional, i.e. $\Delta H=0$,
where $\Delta$ is the Laplace-Beltrami operator [11, 10, 33, 30].

In discrete case, the source domain $M$ is represented as a triangle mesh, the
discrete harmonic energy can be approximated [10, 35, 17] as

$E(H)=\sum_{e_{ij}\in M}w_{e_{ij}}|H(v_{1})-H(v_{0})|^{2},$ (1)

where $e_{ij}=[v_{i},v_{j}]$ is an edge with two endpoints $v_{i}$ and
$v_{j}$, and $w_{ij}$, the edge weight defined on the edge $e_{ij}$, is
defined as

$k_{e_{ij}}=\left\\{\begin{matrix}\frac{1}{2}(\cot{\alpha}+\cot{\beta}),&\forall
e_{ij}\notin\partial M\\\ \frac{1}{2}\cot{\alpha},&otherwise\\\
\end{matrix}\right.,$

where $\alpha$ and $\beta$ are two angles against the edge $e_{ij}$, as shown
in Fig. 6.

Figure 6: Illustration the two angles $\alpha$ and $\beta$ against the edge
$e_{ij}$.

In order to minimize a discrete harmonic energy, we also need to solve the
Euler-Lagrange differential equation for the energy functional, i.e. $\Delta
H=0$, in the discrete situation. This will lead to solving a sparse linear
least-square system for the harmonic map $H$ of all vertices on $M$. According
to Rad$\acute{\textrm{o}}$’s Theorem [33], if an arbitrary convex target
domain is adopted to compute the harmonic map, then the resulting map depends
on the boundary in a continuous manner. In other words, if the boundary
condition

$H|_{\partial M}:\partial M\to\partial D,$

is given and $\partial D$ is convex, then the solution exists and is unique
[10, 35, 17].

The harmonic energy optimization is a linear problem and can be solved
directly using Newton’s method. Algorithm 2 gives the details for computing a
harmonic map from a topological disk to a planar unit square domain.

Algorithm 1 Boundary Condition for Harmonic Map

Input: The boundary $\partial M$ of mesh $M$, and four boundary vertices
$\\{c_{0},c_{1},c_{2},c_{3}\\}$ which will be mapped to four corners of the
unit square.
Output: A map $\boldsymbol{b}$ which maps the boundary $\partial M$ to an unit
square $\partial D$.

1:procedure SquareBoundary($\partial M,\\{c_{0},c_{1},c_{2},c_{3}\\}$)

2: Set the coordinates of $c_{0},c_{1},c_{2},c_{3}$ to
$(0,0),(1,0),(1,1),(0,1)$ respectively.

3: while $k\in\\{0,1,2,3\\}$ do

4: $s\leftarrow len(c_{k},c_{k+1})$, where $len(c_{k},c_{k+1})$ represents
path length from $c_{k}$ to $c_{i+k}$ on $\partial M$. $\triangleright$
$c_{4}=c_{0}$

5: Collect a set of vertices between $c_{i}$ and $c_{i+1}$ in $\partial M$,
denoted as $vlist$.

6: while $v\in vlist$ do

7: $t=len(c_{k},v_{i})/s$,
$\boldsymbol{b}(v)=(1-t)\boldsymbol{b}(c_{k})+t\boldsymbol{b}(c_{k+1})$.

8: end while

9: end while

10: return $\boldsymbol{b}$

11:end procedure

Algorithm 2 Harmonic map for a topological disk

Input: A genus zero mesh $M$ with one boundary $\partial M$, and four boundary
vertices $\\{c_{0},c_{1},c_{2},c_{3}\\}$ which will be mapped to four corners
of the unit square.
Output: A harmonic map $H$ which maps the mesh $M$ to an unit square $D$.

1:procedure HarmonicMap($M,\partial D$)

2: Traverse the boundary of $M$, store the boundary vertices to a cycle list
$\partial M=\\{v_{0},v_{1},...,v_{m-1}\\}$ orderly, where $m$ is the number of
boundary vertices.

3: Compute a map $\boldsymbol{b}$ which maps the boundary $\partial M$ to the
unit square $\partial D$ by Algorithm 1.

4: Optimize the harmonic energy Section 4.2 using Newton’s method with fixed
boundary condition. This is equivalent to solving the following linear system
with the boundary vertices fixed.  $\left\\{\begin{matrix}\Delta
H(v_{i})&=&0,&\forall v_{i}\notin\partial M,\\\ H|_{\partial
M}&=&\boldsymbol{b},&otherwise.\\\ \end{matrix}\right.$

5: return $H$.

6:end procedure

The square harmonic map could be used for the purpose of texture mapping
directly, it maps the surface $M$ to an unit square domain $D$ 111In practice,
one can get a rectangular texture map by simply stretching an unit square
texture map. So, in order to simplify, we only consider the unit square as the
target domain in this paper., and provides the texture coordinates for texture
mapping, but we still need to generate a texture image adapting to the texture
coordinates.

###  4.3 Texture Image Generating

The texture space of original model is loose, and this feature leads to
inefficiency of data storage and GPU memory addressing. In Section 4.2, we
have computed a new and global parameterization as the texture coordinates,
but the original texture images do not adapt the new texture coordinates, so
in this subsection, we will generate a texture image for that.

The rough idea to generate a new texture image is that we filling colors into
the triangles on the new texture space, then the final image is the result.
This idea can be simplified to the _polygon filling algorithm_. There are many
polygon filling algorithms, such as scan line[31, 26], boundary fill [20],
edge fill [9], flood fill [28, 20] and so on. Each method has its own merits
and demerits, and all of them can finish our task. In this paper, we will use
the scan line algorithm to fill colors into all triangles of the model, then a
new texture image is generated.

The scan line filling algorithm works by intersecting each scan line with
polygon edges and then fills the segment cut by the polygon. The Algorithm 3
describes the overview pipeline of the scan line filling algorithm.

Algorithm 3 Scan Line Filling Algorithm

Input: A given planar polygon $f$ with vertices $v_{0},v_{1},...$, and each
vertex
$v_{i}=(\textrm{u}^{new}_{i},\textrm{v}^{new}_{i},\textrm{u}^{ori}_{i},\textrm{v}^{ori}_{i})$
owns its new and original texture coordiantes.
Output: A list of points $pts$ which discretize the segments on scan lines cut
by $f$.

1:procedure ScanLineFilling(Polygon $f$)

2: Find out the minimum $y_{min}$ and maximum $y_{max}$ from the polygon $f$.

3: Initialize a list of scan lines $\\{l_{0},l_{1},...\\}$ from $y_{min}$ to
$y_{max}$.

4: while $l_{i}\in\\{l_{0},l_{1},...\\}$ do

5: Compute the intersections $\\{p_{0},p_{1},...,p_{n_{1}}\\}$ between one
scan line $l_{i}$ and each edge $e$ of polygon $f$, and intersections are
sorted in the ascending order of $x$ coordinate. Then we get a group of
segments $\\{[p_{0},p_{1}],[p_{1},p_{2}],...,[p_{n-2},p_{n-1}]\\}$.

6: Fill all the segments which are inside polygon $f$, and discretize the
segments by interpolation method based on the new texture coordinates.
Meanwhile, the original texture coordinates of the discrete segments can be
obtained by the same interpolation coefficient. Collect the discrete points to
$pts$.

7: end while

8: return $pts$.

9:end procedure

A detailed figure is given in Fig. 7 to explain steps 5 and 6 in Algorithm 3.
In step 6, the _odd-even rule_ could be used to determine whether a segment is
inside polygon $f$ or not. In Fig. 7, for example, we want to determine
whether segment $[p_{1},p_{2}]$ lies inside the polygon or not. Firstly we
select any point $p_{i}$ in $[p_{1},p_{2}]$, then we count the edge crossing
along the scan line from point $p_{i}$ to infinity (either of the two
orientations is fine), and the number of intersections is two which is an even
number, so segment $[p_{1},p_{2}]$ is outside polygon $f$. If we investigate
segments $[p_{0},p_{1}]$ and $[p_{2},p_{3}]$, they both are inside polygon
$f$.

Figure 7: The scan line $l_{i}$ intersects polygon $f$ with two segments
$[p_{0},p_{1}]$ and $[p_{2},p_{3}]$ which is discretized to several points,
here the segment $[p_{1},p_{2}]$ is outside the polygon, so we ignore it.

For each discrete point generated by Algorithm 3, it has four components
$\textrm{u}^{new},\textrm{v}^{new},\textrm{u}^{ori}$ and $\textrm{v}^{ori}$,
point $p^{new}=(\textrm{u}^{new},\textrm{v}^{new})$ on new texture space
corresponds to point $p^{ori}=(\textrm{u}^{ori},\textrm{v}^{ori})$ on original
texture space. Therefore, the color on $p^{new}$ equals to the color on
$p^{ori}$. In this way, a new texture image can be generated efficiently. Fig.
8 shows the pipeline of generating a new texture image.

(a) (b)

(c) (d)

Figure 8:  Pipeline of generating a new texture image: 8(a) a surface $M$
where its texture space is separated into three parts, 8(b) the original
fragmented texture space, 8(c) the new texture mapping computed using
Algorithm 2 is tight, 8(d) the color of pixel $p$ in $UV2$ domain is achieved
via $UV1$ domain, then final texture image is generated.

##  5 Experiments

All the experiments in this paper are carried out on a Windows laptop with an
Intel(R) Core(TM) i7-10710U CPU and a 16GB system memory. The models used in
the experiments are created by two types of methods. One is based on
structured light scanning system [36], and the other is the method of multi-
view stereo [25, 3] which uses oblique aerial images as the input.

Fig. 9 provides a visual comparison between the input vase model and its
corresponding output. This model is generated through a structured light
scanning system, with a geometric accuracy of approximately 0.5mm. The
scanning process involves capturing the vase from various perspectives,
reconstructing point clouds using a three-step phase-shifting algorithm [18].
Subsequently, the normal iterative closest point (NICP) algorithm [2, 34] is
employed for point cloud fusion, resulting in a complete point cloud. The
model is then reconstructed by solving a Poisson equation [19]. Finally, the
original texture is generated by projecting multi-view images onto the vase
surface. This comprehensive scanning and reconstruction process explains why
the original texture border intricately divides the texture space into
numerous irregular patches.

Notably, the resulting texture image (Fig. 9(j)) seamlessly occupies the
entire texture space without any redundant space or pixels. The visual
coherence between the input and output is striking. The transformation not
only simplifies the texture border but also optimally fills the texture space,
showcasing a significant enhancement in visual aesthetics and efficiency.

(a) (b) (c) (d) (e) (f) (g) (h) (i) (j)

Figure 9:  Comparison between original (9(a)-9(e)) and result vase models
(9(f)-9(j)): 9(a), 9(b) front and back views of original model, 9(c), 9(d) the
pink lines show the texture border of original model, 9(e) the top one is the
input texture (4K resolution), but the other one is the actual texture which
used in original model, 9(f), 9(g) front and back views of result model,
visually they look the same as 9(a) and 9(b) respectively, 9(h), 9(i) there is
only one texture border, 9(j) in the result texture (resolution is $4096\times
4096$ pixels), there is no redundant space or pixel.

Fig. 10 presents a comparative analysis between the input vase model and the
generated result. The model is also created by a structured light scanning
system, achieving a geometric accuracy of approximately 0.5mm. In the original
model, the texture border intricately divides the texture space into numerous
irregular patches. In contrast, the resultant texture border forms a simple
loop, traversing from one endpoint to the other and backtracking to the
source. Remarkably, the output texture image (Fig. 10(h)) effectively occupies
the entire texture space without any redundant space or pixels. The visual
representation of the input and output appears consistent.

(a) (b) (c) (d) (e) (f) (g) (h)

Figure 10:  Comparison between original (11(a)-11(d)) and result vase models
(11(e)-11(i)): 11(a) front view of original model, 11(b), 11(c) the pink lines
show the texture border of original model, 11(d) the top one is the input
texture (resolution is $4711\times 4711$ pixels), but the other one is the
actual texture which used in original model, 11(e), 11(f) front and back views
of result model, visually they look the same as the input model, 11(g) there
is only one texture border, 11(i) the output texture (resolution is
$4096\times 4096$ pixels).

Fig. 11 illustrates an extreme case where the initial texture of the input
vase model is formed by individual triangles, each with its own distinct
texture space. Upon employing our method, the resultant texture border is
streamlined into a cohesive loop. The output texture image appears more
unified, showcasing the effectiveness of our approach in enhancing texture
space optimization.

(a) (b) (c) (d) (e) (f) (g) (h) (i)

Figure 11:  Comparison between original (11(a)-11(e)) and output vase models
(11(f)-11(i)): 11(a) the front view of original model, 11(b) in this case,
each triangle of the original model has a distinct texture space, and 11(c)
shows two enlarged parts, 11(d) the input texture (resolution is $8192\times
16384$ pixels), from the enlarged parts 11(e) we can find that all texture
spaces are triangles, 11(f), 11(g) the front and back views of result model,
11(h) the texture border is reduced to a simple one, 11(i) the result texture
(resolution is $4096\times 4096$ pixels) has no redundant space or pixel, and
looks more unified.

Fig. 12 shows another experiment of a building reconstructed by multi-view
stereo method. The model has two components, so we process these parts
according to the pipeline in Fig. 8 respectively. From Fig. 12(b), we can
observe that the texture space is messy and fragmented, and in Fig. 12(d) the
proposed method improves the situation heavily. There is no redundancy space
but there exists many irrelevant pixels in the original textures (Fig. 12(e)),
such as roads, cars, trees and even other buildings (Fig. 12(f)). In Fig.
12(g), we generate two textures with resolution of $4096\times 4096$ pixels
for the new texture coordinates.

(a) (b) (c) (d) (e) (f) (g)

Figure 12:  Comparison between original (12(a),12(b),12(e) and ,12(f)) and
result building models (12(c), ,12(d) and 12(g)): 12(a) the model has two
parts, the green lines show the surface boundaries of the two parts, 12(b) the
pink lines show the texture border of the building model, 12(c) the result
model which owns the same geometry and topology, 12(d) the texture border
simply separates the texture space into two subspaces, 12(e) contains nine
texture images (each one is 4K resolution) of the original model, 12(f) shows
that there are lots of irrelevant pixels exist in 12(e), 12(g) the two result
textures (4K resolution), there is no redundant space or pixel.

In the aforementioned experiments, the newly generated textures demonstrate
the substantial optimization achieved by our method in terms of texture space
utilization. This optimization involves the elimination of unused pixels and
the efficient utilization of the available texture space, leading to
streamlined data storage and enhancing GPU rendering efficiency.

However, it’s important to acknowledge a drawback associated with our proposed
method. The use of harmonic map in the global parameterization may introduce
area distortions, causing certain regions of the generated texture to shrink
significantly. This distortion can result in a loss of texture quality in
those specific areas.

##  6 Conclusions

In this work, we propose a novel texture space optimization method. The
proposed method is based on harmonic map which is an algorithm of global
parameterization. The algorithms and technology details in this proposed
method are described. Experimental results show that our method can generate
textures without redundancy space and pixels. As a result, this method will
save both data storage and GPU memory addressing time in the rendering
process, making the method amenable for storage-critical applications in
computer graphics and other fields. However, the harmonic mapping introduces
area distortion in the result texture, this may weaken the quality of the
texture images. For future work, we will improve the parameterization to
achieve more efficient data storage for texture space optimization task.

## Acknowledgments

This research was supported by the National Natural Science Foundation of
China T2225012, 61936002, and the Fundamental Research Funds for the Central
Universities DUT22QN212.

## References

  * [1] L. Balmelli, G. Taubin, and F. Bernardini.  Space-optimized texture maps.  In Computer Graphics Forum, volume 21, pages 411–420. Wiley Online Library, 2002.
  * [2] P. J. Besl and N. D. McKay.  Method for registration of 3-d shapes.  In Sensor fusion IV: control paradigms and data structures, volume 1611, pages 586–606. Spie, 1992.
  * [3] D. Cernea.  OpenMVS: Multi-view stereo reconstruction library.  2020\.
  * [4] C. Chen and D. Freedman.  Quantifying homology classes.  arXiv preprint arXiv:0802.2865, 2008.
  * [5] T. K. Dey, F. Fan, and Y. Wang.  An efficient computation of handle and tunnel loops via reeb graphs.  ACM Transactions on Graphics (TOG), 32(4):1–10, 2013.
  * [6] T. K. Dey, K. Li, and J. Sun.  On computing handle and tunnel loops.  In 2007 International Conference on Cyberworlds (CW’07), pages 357–366. IEEE, 2007.
  * [7] T. K. Dey, K. Li, and J. Sun.  Computing handle and tunnel loops with knot linking.  Computer-Aided Design, 41(10):730–738, 2009.
  * [8] T. K. Dey, K. Li, J. Sun, and D. Cohen-Steiner.  Computing geometry-aware handle and tunnel loops in 3d models.  In ACM SIGGRAPH 2008 papers, pages 1–9. 2008.
  * [9] M. R. Dunlavey.  Efficient polygon-filling algorithms for raster displays.  ACM Transactions on Graphics (Tog), 2(4):264–273, 1983.
  * [10] M. Eck, T. DeRose, T. Duchamp, H. Hoppe, M. Lounsbery, and W. Stuetzle.  Multiresolution analysis of arbitrary meshes.  In Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, pages 173–182, 1995.
  * [11] J. Eells and J. H. Sampson.  Harmonic mappings of riemannian manifolds.  American journal of mathematics, 86(1):109–160, 1964.
  * [12] J. Erickson.  Combinatorial optimization of cycles and bases.  Advances in applied and computational topology, 70:195–228, 2012.
  * [13] J. Erickson and K. Whittlesey.  Greedy optimal homotopy and homology generators.  In SODA, volume 5, pages 1038–1046, 2005.
  * [14] C. Frueh, R. Sammon, and A. Zakhor.  Automated texture mapping of 3d city models with oblique aerial imagery.  In Proceedings. 2nd International Symposium on 3D Data Processing, Visualization and Transmission, 2004. 3DPVT 2004., pages 396–403. IEEE, 2004.
  * [15] M. R. Garey and D. S. Johnson.  Michael r. garey and david s. johnson, computers and intractability: A guide to the theory of np-completeness.  Bulletin (New Series) of the American Mathematical Society, 3(2):898–904, 1980.
  * [16] X. Gu, S. J. Gortler, and H. Hoppe.  Geometry images.  In Proceedings of the 29th annual conference on Computer graphics and interactive techniques, pages 355–361, 2002.
  * [17] X. Gu and S.-T. Yau.  Surface classification using conformal structures.  In Computer Vision, IEEE International Conference on, volume 2, pages 701–701. IEEE Computer Society, 2003.
  * [18] P. S. Huang and S. Zhang.  Fast three-step phase-shifting algorithm.  Applied optics, 45(21):5086–5091, 2006.
  * [19] M. Kazhdan, M. Bolitho, and H. Hoppe.  Poisson surface reconstruction.  In Proceedings of the fourth Eurographics symposium on Geometry processing, volume 7, 2006.
  * [20] B. Kumar, U. K. Tiwari, S. Kumar, V. Tomer, and J. Kalra.  Comparison and performance evaluation of boundary fill and flood fill algorithm.  Int. J. Innov. Technol. Explor. Eng, 8:9–13, 2020.
  * [21] B. Lévy, S. Petitjean, N. Ray, and J. Maillot.  Least squares conformal maps for automatic texture atlas generation.  ACM transactions on graphics (TOG), 21(3):362–371, 2002.
  * [22] M. Limper, N. Vining, and A. Sheffer.  Box cutter: atlas refinement for efficient packing via void elimination.  ACM Trans. Graph., 37(4):153–1, 2018.
  * [23] J. Martinez and C. Andujar.  Space-optimized texture atlases for 3d scenes with per-polygon textures.  In 2010 18th Pacific Conference on Computer Graphics and Applications, pages 14–23. IEEE, 2010.
  * [24] V. J. Milenkovic.  Rotational polygon containment and minimum enclosure using only robust 2d constructions.  Computational Geometry, 13(1):3–19, 1999.
  * [25] P. Moulon, P. Monasse, R. Perrot, and R. Marlet.  OpenMVG: Open multiple view geometry.  In International Workshop on Reproducible Research in Pattern Recognition, pages 60–74. Springer, 2016.
  * [26] N. Nisha and S. Varshney.  A review: Polygon filling algorithms using inside-outside test.  Int. J. Adv. Eng. Res. Sci, 4(2):73–75, 2017.
  * [27] T. Nöll and D. Strieker.  Efficient packing of arbitrary shaped charts for automatic texture atlas generation.  In Computer Graphics Forum, volume 30, pages 1309–1317. Wiley Online Library, 2011.
  * [28] E.-M. Nosal.  Flood-fill algorithms used for passive acoustic detection and tracking.  In 2008 New Trends for Environmental Monitoring Using Passive Systems, pages 1–5. IEEE, 2008.
  * [29] T. Odaker, M. Wiedemann, C. Anthes, and D. Kranzlmüller.  Texture analysis and repacking for improved storage efficiency.  In Proceedings of the 22nd ACM Conference on Virtual Reality Software and Technology, pages 361–362, 2016.
  * [30] B. O’neill.  Elementary differential geometry.  Elsevier, 2006.
  * [31] J. Pineda.  A parallel algorithm for polygon rasterization.  In Proceedings of the 15th annual conference on Computer graphics and interactive techniques, pages 17–20, 1988.
  * [32] P. V. Sander, Z. J. Wood, S. Gortler, J. Snyder, and H. Hoppe.  Multi-chart geometry images.  2003\.
  * [33] R. M. Schoen and S.-T. Yau.  Lectures on differential geometry, volume 2.  International press Cambridge, MA, 1994.
  * [34] J. Serafin and G. Grisetti.  Nicp: Dense normal based point cloud registration.  In 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 742–749. IEEE, 2015.
  * [35] D. Zhang and M. Hebert.  Harmonic maps and their applications in surface matching.  In Proceedings. 1999 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (Cat. No PR00149), volume 2, pages 524–530. IEEE, 1999.
  * [36] S. Zhang.  High-speed 3d shape measurement with structured light methods: A review.  Optics and Lasers in Engineering, 106:119–131, 2018.
  * [37] Q.-Y. Zhou, T. Ju, and S.-M. Hu.  Topology repair of solid models using skeletons.  IEEE Transactions on Visualization and Computer Graphics, 13(4):675–685, 2007.