Abstract=
Given an arb=
itrary
mesh, we present a method to construct a progressive mesh (PM) such that all
meshes in the PM sequence share a common texture parametrization. Our method considers two important=
goals
simultaneously. It minimizes
texture stretch (small texture distances mapped onto large surface distance=
s)
to balance sampling rates over all locations and directions on the
surface. It also minimizes te=
xture
deviation (“slippage” error based on parametric correspondence)=
to
obtain accurate textured mesh approximations. The method begins by partitioning =
the
mesh into charts using planarity and compactness heuristics. It creates a stretch-minimizing
parametrization within each chart, and resizes the charts based on the
resulting stretch. Next, it s=
implifies
the mesh while respecting the chart boundaries. The parametrization is re-optimize=
d to
reduce both stretch and deviation over the whole PM sequence. Finally, the charts are packed int=
o a
texture atlas. We demonstrate=
using
such atlases to sample color and normal maps over several models.
Additional
Keywords: mesh simplification, surface flattening, surfa=
ce
parametrization, texture stretch.
1.&n=
bsp;
Introduction
The progress=
ive mesh
(PM) representation encodes an arbitrary mesh as a simple base mesh M0
and a sequence of n refinement operations called vertex splits [10]. It
defines an array {M0…Mn} of
level-of-detail (LOD) approximations, and supports geomorphs and progressive
transmission [1]. Un=
like
multiresolution frameworks based on subdivision, the meshes in a PM have
irregular connectivities that can accurately model sharp features (e.g. cre=
ases
and corners) at all scales.
One challeng=
e in the
PM framework is dealing with texture maps.=
Hardware rasterization features (including bump maps, normal maps, a=
nd
multitexturing) let fine detail be captured in texture images parametrized =
over
the mesh. Sources for texture=
s include
sampling detailed scanned meshes, evaluating solid textures, ray tracing, a=
nd
3D painting. In this paper, w=
e address
the problem of parametrizing texture images over all meshes in a PM sequenc=
e.
A single unf=
olding
of an arbitrary mesh onto a texture image may create regions of high
distortion, so generally a mesh must be partitioned into a set of charts=
. Each chart is parametrized by a re=
gion
of a texture domain, and these parametrizations collectively form an atl=
as
(see Figure
4c). =
For instance,
several schemes [2][22][25][27] simplify a mesh and then construct a texture image
chart over each simplified face by sampling attributes (e.g. normals) from =
the
original mesh.
For a PM, on=
e might
then consider re-using chart images defined on faces of M0
for all meshes M1…Mn. However, the problem is that a PM =
is
generally not chart-compliant, in that its vertex splits can change =
the
chart topology when applied indiscriminately near chart boundaries, thereby
forcing parametric discontinuities.
For example, the vertex split shown on the right changes the adjacen=
cy
of the three colored charts, resulting in the discontinuous texture. Fortunately, it is possible to con=
struct
a single atlas parametrization for the entire PM sequence. Chart-compliance can be obtained by
first defining the charts on the original mesh, and then constraining a
simplification sequence to comply with those chart boundaries [3].
Therefore, o=
ur
problem is the following: given an arbitrary mesh, parametrize it onto a te=
xture
atlas, and create a PM sequence compliant with the atlas charts. In doing so, we have two goals:
- Minimize texture stretch: =
The
parametrization determines sampling density over the surface, but is
constructed before knowing what texture map(s) will be applied. Therefore, we seek a balanced
parametrization rather than one that samples finely in some surface regions=
or
directions while undersampling others.&nbs=
p;
A conservative, local measure of how finely the parametrization samp=
les
the texture signal is the larger singular value of its Jacobian, which meas=
ures
how much a sampling direction in the texture domain is stretched on the mesh
surface in the worst case. By
minimizing the largest texture stretch across all domain points, we create a
balanced parametrization where no domain direction is too stretched and thus
undersamples its corresponding mapped 3D direction. (See Figure
1 and Figure
6.)
- Minimize texture deviation:
Traditional mesh simplification measures geometric error by
approximating closest-point (Hausdorff) distance. For textured surfaces, it is more =
appropriate
to use the stricter texture deviation error, which measures geometric
error according to parametric correspondence [3]. Fo=
r a
PM, texture deviation can be graphed as a function of mesh complexity. Our goal is to lower this graph cu=
rve.
Recall that =
the
motivation for partitioning the surface into charts is to reduce texture
stretch. However, the presenc=
e of
chart boundaries hinders simplification quality since chart-compliance requ=
ires
that these boundaries appear as edges in all meshes including M0. In the extreme, if each face of Mn
is made its own chart, stretch is zero, but no simplification can occur. Hence, there exists a trade-off be=
tween
texture stretch and deviation.
Minimizing s=
tretch
and deviation is a difficult nonlinear problem over both discrete and
continuous variables. The dis=
crete
variables are the mesh partition and the edge collapse sequence. The continuous variables are the t=
exture
coordinates of the vertices. =
Our
approach is to set the discrete variables early, using heuristics, and then
proceed to optimize the continuous variables. Specifically, our method has the
following steps:
(1) partition original mesh into charts=
(considering geometry)
(2) form initial chart parametrizations&nb=
sp;
(minimizing stretch)
(3) resize chart polygons (ba=
sed on
stretch)
(4) simplify mesh (minimizing
texture deviation, creating PM)
(5) optimize parametrization
(stretch & deviation over all PM)
(6) pack chart polygons (form=
ing
texture atlas)
(7) sample texture images (us=
ing
atlas parametrization)
The contributions of our work are:
·
an
algorithm for partitioning a mesh into charts, which considers simplificati=
on
quality and does not alter the mesh.
·
a
texture stretch metric that uniformly penalizes undersampling everywhere ov=
er
the surface.
·
an
algorithm for minimizing this stretch metric in the L2
and L=
¥ norms, which can be used for both static
meshes and PMs.
·
a =
scheme
for optimizing the parametrization to minimize both texture stretch and tex=
ture
deviation at all PM levels, with appropriate
weighting of each mesh in M0R=
30;Mn.
·
the
first automatic solution for creating a PM representation with a consistent
surface parametrization for all LODs.
2.&n=
bsp;
Previous work
Mesh part=
itioning
into charts. Several authors have proposed meth=
ods
for parametrizing meshes by partitioning into charts. Krishnamurthy and Levoy [17] describe an interactive system in which the user
manually lays out chart boundaries by tracing curves. Maillot et al. [21] partition mesh faces according to a bucketing of =
face
normals. Eck et al. [4] use a Voronoi-based partition. These last two algorithms make lit=
tle
effort to adapt charts to surface geometry, so the chart boundaries can hin=
der
simplification, leading to poor LOD approximations.
MAPS [18] and Normal Meshes [8] map edges of the simplified base domain back to t=
he
original mesh. While the resu=
lting
charts adapt to surface geometry, their boundaries cut across faces of orig=
inal
mesh, requiring addition of new vertices and faces. For the applications in [8][18], these additional vertices are only temporary,
because the mesh geometry is subsequently resampled. However, our application is to gen=
erate
a PM from a user-specified mesh, whose connectivity is often carefully opti=
mized,
so the imposition of new vertices is a drawback.
Chart
parametrization. Several schemes have been proposed=
to
flatten surface regions to establish a parametrization. The schemes typically obtain the
parametrization by minimizing an objective functional. The main distinction between the
functionals is how they measure the distance of the parametrization from an
isometry (a mapping preserving lengths and angles).
Maillot et a=
l. [21] base their metric on edge springs of nonzero rest
length, where rest length corresponds to edge length on the surface. To ensure that the parametrization=
is
1-to-1, (i.e., to avoid parametric “buckling”, also called
“face flipping”), they add an area-preservation term to the
metric. When the texture doma=
in
boundary is fixed as in our application, it is unclear how edge rest-lengths
should be scaled. More import=
antly,
the weighting between the edge springs and the area-preservation term must =
be
adjusted to produce an embedding.
Eck et al. <=
span
style=3D'mso-field-code:" REF _Ref501778256 \\r \\h \\* MERGEFORMAT "'=
>[4] propose the harmonic map, which weights edge spri=
ngs
non-uniformly. The weights ca=
n sometimes
be negative, in which case an embedding is not guaranteed. Floater [5] proposes a similar scheme with a different
edge-spring weighting that guarantees embedding for convex boundaries. For either method, the parametriza=
tion
can be found by solving a linear system.
Lévy =
and
Mallet [19] combine orthogonality and isoparametric terms in
their metric. To solve the
resulting nonlinear optimization, they iteratively fix one texture componen=
t (s
or t) and solve for the other using a linear optimization. As in [20], a term is added which must be sufficiently weigh=
ted
to guarantee an embedding.
Hormann and =
Greiner [11] propose the MIPS parametrization, which roughly
attempts to preserve the ratio of singular values over the parametrization.=
However, the metric disregards abs=
olute
stretch scale over the surface, with the result that small domain areas can=
map
to large regions on the surface.
To allow all=
meshes
in the PM to share a common texture map, it is necessary that we create dom=
ains
with straight boundaries between chart corners, unlike [11][19][21].
Our main
contribution is to directly optimize the two relevant goals for texture map=
ping
PMs: minimal texture stretch and minimal texture deviation. Our novel stretch metric attempts =
to
balance sampling rates everywhere on the surface, unlike previous technique=
s.
Appearanc=
e-preserving
simplification. Cohen et al. [3] introduce texture deviation as the appropriate
measure of geometric accuracy when simplifying textured meshes. The texture deviation between a
simplified mesh Mi and the original mesh Mn=
at a point pi Î=
Mi is defined as || pi – pn ||
where pn is the point on Mn with the sa=
me
parametric location in the texture domain.=
Cohen et al. track texture deviation conservatively by storing a
bounding error box at each mesh vertex.&nb=
sp;
They demonstrate results on parametric surfaces already organized in=
to
charts.
We begin wit=
h an
unparametrized mesh, and seek to form an atlas parametrization that
specifically minimizes texture deviation and stretch over all meshes in a P=
M.
To optimize =
a parametrization’s
ability to balance frequency content everywhere over the surface in every
direction, we define a new “texture stretch” metric on triangle
meshes.
Given a triangle T with 2D textu=
re
coordinates ![](3D"tmpm_errata_files/image002.gif")
=
, ![](3D"tmpm_errata_files/image004.gif")
=
, and corresponding 3D coordinates ![](3D"tmpm_errata_files/image006.gif")
=
, the unique affine mapping![](3D"tmpm_errata_files/image008.gif")
=
is
&=
nbsp; &nbs=
p; &=
nbsp; &nbs=
p; &=
nbsp; &nbs=
p; &=
nbsp; &nbs=
p; &=
nbsp; &nbs=
p; &=
nbsp; &nbs=
p; &=
nbsp; &nbs=
p; &=
nbsp; &nbs=
p; &=
nbsp; &nbs=
p; &=
nbsp; &nbs=
p; ![](3D"tmpm_errata_files/image010.gif")
=
where ![](3D"tmpm_errata_files/image012.gif")
=
denotes area of triangle abc. Since the mapping is affine, its p=
artial
derivatives are constant over (<=
i>s,t)
and given by
![](3D"tmpm_errata_files/image014.gif")
=
The larger and smaller singular values =
of the
Jacobian ![](3D"tmpm_errata_files/image016.gif")
=
are given respectively by
![](3D"tmpm_errata_files/image018.gif")
=
where ![](3D"tmpm_errata_files/image020.gif")
=
, ![](3D"tmpm_errata_files/image022.gif")
=
, and ![](3D"tmpm_errata_files/image024.gif")
=
. The singu=
lar
values =
G and g
represent the largest and smallest length obtained when mapping unit-length
vectors from the texture domain to the surface, i.e. the largest and smalle=
st
local “stretch”. =
We
define two stretch norms over triangle T :
&=
nbsp; &nbs=
p; &=
nbsp; &nbs=
p; &=
nbsp; &nbs=
p; &=
nbsp; &nbs=
p; &=
nbsp; &nbs=
p; &=
nbsp; &nbs=
p; &=
nbsp; &nbs=
p; &=
nbsp; &nbs=
p; &=
nbsp; &nbs=
p; &=
nbsp; &nbs=
p; ![](3D"tmpm_errata_files/image026.gif")
=
.
The norm L2(T) corresponds to the
root-mean-square stretch over all directions in the domain, and the worst-c=
ase
norm L¥(T) is the greatest stretch, i.e. the maxi=
mum
singular value. Note that bot=
h L2(T) and L<=
i>=
¥(T) increase to infinity as the parametriz=
ation
of T becomes degenerate, since its parametric area A drops to
zero. If the triangle T
flips parametrically (i.e. if A becomes negative), we define both L2(T) and L<=
i>=
¥(T) to remain infinite.<=
/p>
|
|
|
|
|
(a)
exact
|
|
|
|
|
|
(b)
Floater [5] L2=3D2.26 L¥=3D9.86
|
|
|
|
|
|
(c)
MIPS [11] L2=3D2.31 L¥=3D7.46
|
|
|
|
|
|
(d)
Maillot [20] L2=3D¥&nbs=
p;
L¥=
=3D¥=
|
|
|
|
|
|
(e)
area-preserving
L2=3D1.57 =
L¥=3D4.19
|
|
|
|
|
|
(f)
our L2 stretch L2=3D1.22 L¥=3D2.13
|
|
|
|
|
|
(g)
our L¥=
stretch L2=3D1.28 L¥=3D1.65
Figure 1: Chart parametrization comparison.
|
We define two analogous norms over the
surface of the entire mesh ![](3D"tmpm_errata_files/image028.gif")
=
:
![](3D"tmpm_errata_files/image030.gif")
=
where![](3D"tmpm_errata_files/image032.gif")
=
is the surface area of triangle![](3D"tmpm_errata_files/image034.gif")
=
in 3D. The=
L2
norm measures the overall ability of the parametrization to support high-fr=
equency
textures, while L¥ measures its worst-case ability.<=
/o:p>
We normalize stretch values by scaling =
the
texture domain so that its area equals the surface area in 3D. Thus, 1.0 is a lower bound for eit=
her
norm on any parametrization. =
Alternately,
stretch can be normalized without explicitly scaling the texture domain by
multiplying with the factor
![](3D"tmpm_errata_files/image036.gif")
=
.
To minimize our nonlinear metrics L2(M) and L<=
i>=
¥(M), we begin with a uniform-edge-spring
solution, and then perform several optimization iterations. Within each iteration, we consider=
vertices
in decreasing order of neighborhood stretch. For each vertex, we perform a line
search minimization along a randomly chosen search direction in the (s,t) parametric domain.=
Because all other vertices are held
fixed, the stretch metric only needs local computation over the neighborhoo=
d. Since the metric is infinite for
degenerate or flipped triangles, the line search is naturally constrained
within the kernel of the vertex’s neighborhood. In successive iterations, we gradu=
ally
decrease the convergence tolerance in the 1D line search using the schedule=
1/i where i is the iteration number.&nbs=
p;
For the L¥ optimization, we obtain even better re=
sults
by using our L2 solution as its starting point.
Fig=
ure 1 compares our metric with alternatives. For each metric, we used the same
optimization procedure described above.&nb=
sp;
In all cases, boundary vertices were fixed by arc-length. For each parametrization, we creat=
ed a
128´128 image in the texture domain by sampling a procedural 3D
checkered pattern on the parametrized surface. For improved filtering, we used 4x=
4 supersampling. As can be seen in the resulting te=
xtured
models, parametrizations optimized using our metrics are better at capturing
high-frequency detail everywhere over the surface. In (b-d), note the loss of resolut=
ion on
the ears where stretch error is high. The area-preserving parametrizatio=
n in
(e) minimizes the Maillot buckling term only. Although it has better spatial dis=
tribution
than (b-d), note how it undersamples certain directions, causing directional
blur on the chin, sides, and ears.
4.&n=
bsp;
Our PM parametrization scheme
In this sect=
ion we
present the steps of our PM parametrization scheme. We first introduce some definition=
s and
assumptions.
Let a cha=
rt
corner be any vertex adjacent to 3 or more charts, and let a chart boundary
be the path of edges separating charts between two corners. We define the neighborhood =
of a
vertex as the ring of faces adjacent to the vertex.
Our PM is ba=
sed on
the half-edge collapse operation (v1 , v2)
à v1
which affects the neighborhood of v2 as shown on t=
he
right and leaves the position and attributes of v1 unchan=
ged [16]. We
prefer the half-edge to the full-edge collapse to avoid writes to the vertex
buffer during runtime LOD changes.
Therefore, (s,t)
texture coordinates at any vertex must be the same at all LOD levels. Since a vertex on a chart boundary=
has
different (s,t) co=
ordinates
on each chart, these must be stored at the corners of mesh faces [10].
To create a =
texture
atlas over a PM, we must enforce the following constraints:
(1) mesh fac=
es
cannot span more than one chart, since it is impractical to specify and ren=
der
disjoint pieces of texture over any single triangle.
(2) chart bo=
undaries
must be straight in the parametric domain, since each chart boundary is
generally simplified to a single edge in the PM base mesh.
These constr=
aints
restrict the partition of the mesh into charts (Section 4.1) and the mesh simplification sequence (Section 4.4).
The first st=
ep is to
partition the mesh into a set of charts: regions with disk-like topology. Ideally one could simultaneously s=
earch
over the discrete space of possible chart decompositions and the continuous
space of parametrizations allowed by each decomposition. Clearly this is intractable. In our system we first partition t=
he
mesh using a greedy chart-merging approach. It is similar to simplification sc=
hemes
based on the greedy growth of “superfaces” [9][15], and to the independent work by Garland et al. [6].
Initially, e=
ach face
is assigned to be its own chart.
For each pair of adjacent charts, we consider the operation of mergi=
ng
the two charts into one, and enter this candidate operation into a priority
queue according to a computed cost.
As in [6], the merge operation is assigned a cost that meas=
ures
both its planarity and compactness.
We measure planarity as the mean-squared distance of the chart to the
best-fitting plane through the chart, defined as a continuous surface integ=
ral
(unlike [6] which evaluates it only at the vertices). We measure compactness simply as t=
he
squared perimeter length.
We iterative=
ly apply
the merge operation with lowest cost, and update costs of neighboring candi=
date
merge operations. The process=
ends
when the cost exceeds a user-specified threshold.
A chart merge
operation is disallowed if it results in any chart with fewer than 3
corners. It is also disallowe=
d if
the boundary between the new chart and any adjacent chart consists of more =
than
one connected component (e.g. one isolated vertex and one path of edges). This constraint also guarantees th=
at
charts remain homeomorphic to discs.
Once the cha=
rts are
formed, they define the set of chart corner vertices. Note that these corner vertices in=
Mn
must appear as vertices in the base mesh M0 due to the
constrained half-edge collapses.
Therefore, we would like each chart boundary to closely align with t=
he
straight line segment between its adjacent two corners, so as to not be a
limiting factor in the simplification quality. We straighten each boundary by com=
puting
a shortest path over mesh edges, constrained not to intersect other chart b=
oundaries.
Results of t=
he
initial chart partition, and the subsequent boundary straightening are show=
n in
Figure 2: Top row shows initial chart partitions, and bottom row sh=
ows
result of chart boundary optimization.
Once the chart boundaries are defined i=
n Mn,
we create an initial parametrization of each chart onto a 2D polygon. We define the 2D polygon boundary =
to be
a convex polygon with vertices on a circle, where the length of each polygon
edge is proportional to the arc-length of the corresponding chart boundary =
in
3D, as in [4]. We
initially scale the polygon to have unit area. Within each chart, we parametrize =
the
interior vertices by minimizing the L2(M) stretch metric, using the algorithm described in
Section 3.
Now
that we have chart parametrizations on Mn, we determine h=
ow
much relative space each chart should be granted in the texture domain. For each chart, we compute L2(Mn<=
/sup>chart), the rms stretch over the chart, and u=
se
that value to uniformly resize the chart while preserving its shape. We had hoped to use L¥(Mnchart) to resize
the charts, but unfortunately there are a few triangles for which the maxim=
um
stretch remains high. Althoug=
h the
relative chart sizes have no effect on simplification (Section 4.4), they do affect E(PM) in the final=
PM
optimization (Section 4.5).
4.4 Simplify mesh<=
span
style=3D'display:none;mso-hide:all'>
Given the in=
itial
chart parametrizations, we simplify the mesh to define a PM. Our goal during simplification is =
to
minimize texture deviation. O=
ur
algorithm closely follows that of Cohen et al. [3]. We=
select
edge collapses that minimize texture deviation by using a priority queue. To enforce chart compliance, we di=
sallow
an edge collapse (v1<=
/sub>,v2)
à v1 in=
Mi+1 à=
Mi if vertex v2 is a
chart corner (to preserve corners), or if v2 is on a chart
boundary and edge (v1,v2) is not on a c=
hart
boundary (to preserve boundary straightness). In addition, we also prevent the
creation of parametrically flipped or degenerate triangles.
To measure t=
exture
deviation for each candidate edge collapse, rather than using conservative
bounds as in [3], we use the fast heuristic of measuring the
incremental texture deviation d(Mi+1,Mi) between the two
meshes. (The heuristic is aki=
n to
the “memoryless” error that has proven effective for geometric
simplification [20].) T=
he
maximum deviation between Mi+1 and Mi is
known to lie either at the removed vertex v2
or at an edge-edge intersection point in the parametric neighborhood (e.g. =
the
red points shown in the figure to the right). We confirmed empirically that the =
incremental
deviation heuristic works well by comparing to a slow simplification that
orders edge collapses using the true deviation error (between Mi and Mn).
Having deter=
mined
the PM simplification sequence, we now re-optimize the chart parametrizatio=
ns
to minimize stretch and deviation on the entire sequence M0&#=
8230;Mn. Our nonlinear optimization algorit=
hm
follows the strategy of moving vertices of Mn one-by-one =
in
the parametric domain as in Sections 3 and 4.2, but using a different objective function.
Our objective
function is a weighted sum of the texture stretch and deviation on all mesh=
es M0…Mn:
E(PM) =3D <=
span
style=3D'font-size:14.0pt;mso-bidi-font-size:10.0pt;font-family:Symbol;
display:none;mso-hide:all'>Si=3D0..n y(i)
[ l L2(Mi<=
/i>)2 +=
(1 - l) d(Mi,Mn)2 / A=
′
(Mn) ]
where L2(Mi)
is the normalized average stretch of Mi (Section 3) computed using the resized charts from Section <=
span
style=3D'mso-field-code:" REF _Ref503082124 \\r \\h \\* MERGEFORMAT "'=
>4.3, d(Mi,Mn) is its texture deviation, the parameter =
0 =
£ l =
£ 1 is used to weight stretch error rela=
tive
to deviation error, and y(i) is
the relative weight assigned to each LOD mesh in the sequence. Dividing by the mesh surface area =
A′(Mn)
makes the second term scale-invariant like the first term.
We now intro=
duce a
model for setting the relative weight y(i)
assigned to each mesh Mi, consisting of two factors: usage
and scale. Depending on the
application, other weighting schemes could be used, without changing the
optimization method.
·
In=
LOD
applications, coarser meshes are likely to be used proportionately more
often. For example, meshes wi=
th 10–100
faces are likely to be used more than those with 900–990 faces. We believe that a reasonable model=
for usage
probability is a uniform distribution over a logar=
ithmic
scale of model complexity, e.g. meshes with 10-100 faces are as equally lik=
ely
as meshes with 100-1000 faces. This
distribution is obtained using the factor 1/|Mi|
where |M| is the number of vertices in M.
·
Th=
e fact
that coarser meshes are typically used when the object is farther away redu=
ces
the screen-space scale of their deviation and stretch. For a smooth spherical surface, te=
xture
deviation varies as 1 / |M|2=
. Since LOD algorithms attempt to ma=
intain
a constant screen-space error, deviation and stretch in model space should
therefore be down-weighted for coarser mesh meshes using the weighting fact=
or |Mi|2 in y(i).
To optimize =
the
texture coordinates of a given vertex v, our optimization algorithm
needs to repeatedly evaluate E.&nbs=
p;
Computing E using the above sum over all meshes would be expe=
nsive. Fortunately, the neighborhood of <=
i>v
changes only a few times within the sequence of meshes, generally O(log |Mn|)
times. Thus we only need to
consider E on each refinement neighborhood Mi à=
Mi+1 of which v =
is a
member. For each vertex v<=
/i>,
we gather the relevant refinement neighborhoods as a list during a
coarse-to-fine preprocess traversal of the PM.
Since the re=
finement
neighborhoods adjacent to a vertex v have an approximately logarithm=
ic
distribution over the PM sequence, we can account for the usage factor by
summing the stretch and deviation on these refinement neighborhoods. Therefore, we weight the error ove=
r each
such neighborhood by y ′=
; (i) =3D |Mi|2
to account for the remaining scale factor.
The following
pseudo-code gives an overview of our algorithm.
// Optimize
parametrization over whole PM sequence.
procedure param=
etrize_pm()
gather_refinement_neighborhoods() // coarse-to-=
fine
traversal
repeat
v =3D some_vertex_in_mesh(Mn)
optimize_vertex(v)
until convergenc=
e
// Optimize the
parametrization param(v) of vertex v
procedure optimize_vertex(vertex v)
repeat
vector dir =3D random_search_direction() // in 2D doma=
in
// perform line search minimization
repeat
=
select float t =
// e.g. using binary line search
=
param(v) =3D param(v) + dir * t&nbs=
p;
// perturb parametrization of v
&n=
bsp;
until error_over_PM(v) is minimized
until convergenc=
e
// Sum of erro=
rs
affected by param(v) in all meshes M0…Mn.
function
error_over_PM(vertex v)
error =3D 0
for (vertex w in
refinement_neighborhoods(v))
error +=3D error_over_neighborhood(w, v)
return error
// Error due t=
o v in
neighborhood of w (where w is first introduced)
function
error_over_neighborhood(vertex w, vertex v)
return y’(level(w)) *
[ l * stretch_error(w, original_neighbors(w), v) +
=
(1-l) * deviation_error(w, original_neighbo=
rs(w),
v) / A′(Mn)=
]
As in Sectio=
n 4.4, we approximate the deviation error d(M=
i,Mn) with the increment=
al
deviation error d(Mi,Mi+1). Because we define our stretch metr=
ic to
be infinite when a face is flipped in the parameter domain, stretch minimiz=
ation
prevents parametric flipping in all meshes. One final detail is that we also o=
ptimize
the parametrization of vertices along chart boundaries. Since these vertices have texture
coordinates in two adjacent charts, we must consider the refinement
neighborhoods in both charts simultaneously. Specifically, we must constrain th=
e parametrizations
to remain on the boundaries, and optimize over shared barycentric coordinat=
es
along the boundary to prevent “parametric cracks”.
4.6 Pack chart polygons
Since the
optimization in Section 4.5 modifies the parametrization, we perform a final
chart resizing step as in Section 4.3.
The next ste=
p is to
pack these resized charts into a rectangular texture image. In the context of texture mapping,
various heuristics have been presented for the special case of packing 3-si=
ded
charts [2][22][25][27]. Ho=
wever,
our chart boundaries can be arbitrary polygons. The general problem is known as the
NP-hard pants packing problem [23].
We simplify =
the
problem by conservatively approximating each chart polygon with the least-a=
rea
rectangle that encloses it. T=
his
rectangle is found efficiently by considering each edge of the polygon̵=
7;s
convex hull. Fortunately, our=
chart
polygons are reasonably shaped, so the rectangle approximation is not too
costly. We rotate the chart to
align the long axis of the rectangle with the vertical direction. The problem then becomes that of
rectangle packing, which is still NP-hard, but for which there exist good
heuristic approximations (e.g. [14][24]). We
develop our own simple heuristic, which works as follows.=
We sort the
rectangles by height. In orde=
r of
decreasing height, we place the rectangles sequentially into rows in altern=
ating
left-to-right and right-to-left order as shown in Figure 4c [14]. Th=
rough
binary search, we optimize over the texture width such that the packing
minimizes the area of the enclosing square.
When the des=
ired
texture sampling density is later determined, we leave a one texel gap betw=
een
adjacent charts. Section 5 reports results of our chart packing efficiency.<=
o:p>
The packed c=
harts
define a texture atlas for the surface.&nb=
sp;
We use the atlas to sample attributes from the surface Mn
into the texture domain, at the 2D grid of texel locations. For improved filtering, we supersa=
mple
the attributes using a 4x4 box filter.&nbs=
p;
Section 5 shows results of sampling colors and normals.
If the highe=
st
frequency f of the attribute function over the surface mesh is known,
the stretch-based scale of the texture atlas makes it possible to estimate =
the
required 2D grid sampling density.
With the charts resized as in Section 4.3, the 2D grid spacing should be set no more than <=
i>1/(2f).<=
/p>
In general, =
schemes
that pack multiple charts into a single texture image may give rise to
mip-mapping artifacts, since coarser mip-map levels will average together s=
patially
disjoint charts. The most imm=
ediate
artifact is that chart boundaries are revealed if the inter-chart area is l=
eft
unpainted (e.g. black). To mi=
tigate
this, we apply a pull-push algorithm [7] to fill-in these unsampled regions with reasonable
values. As an example, the ef=
fect
on the atlas image from Figure
4c is shown on the right.
Fig=
ure 4 shows an example result, where the texture image
captures pre-shaded colors from the original mesh Mn. Although we only show the textured=
base
mesh, the same texture atlas can of course be used on all other meshes M=
1…
Mn in the PM, as shown on the accompanying video.=
Fig=
ure 5 shows several mesh approximations in a PM sequenc=
e,
where the texture image captures a normal map. Because the PM meshes can have irr=
egular
connectivities, they quickly converge to good geometric approximations. Hence the figure shows LOD meshes =
with
relatively low face-counts, compared to the original mesh of nearly 97,000
faces.
compares gra=
phs of
texture stretch and deviation for meshes in a PM using various parametrizat=
ion
schemes. The curve labeled
“uniform” corresponds to uniform edge-spring parametrization
followed by simplification minimizing texture deviation. (The harmonic [4] and Floater [5] parametrizations typically have even greater stre=
tch
than the uniform parametrization.) <=
/span>The
curve labeled “min-stretch param.” replaces the initial paramet=
rization
with our scheme of Section 4.2. As=
is
evident in the graph, parametric stretch is reduced for the finest mesh Mn. (This difference is often more sig=
nificant
as shown in Table
1.) T=
he
curve may appear bumpy because stretch is ignored during simplification. Finally, the curve labeled
“min-stretch + optimiz.” adds our parametrization optimization =
of
Section 4.5. No=
te
that it improves stretch at lower LODs, while also improving texture deviat=
ion
over the whole range.
As demonstra=
ted in Fig=
ure 6, ignoring texture stretch during parametrization
results in non-uniform surface sampling, which becomes apparent as loss of
detail over regions of high stretch distortion.
|
<=
/o:p>
|
|
<=
/span>
|
|
2001/06/18:
The stretch efficiencies=
in
the following table were computed incorrectly in the original paper.=
The corrected numbers ap=
pear
below. In all cases, the
corrected numbers represent improvements (higher efficiencies) over the e=
rroneous
results reported previously.Fig=
ure 3: Error graphs of
texture stretch and deviation over the horse PM sequence, both measured u=
sing
L2 norms and weighted by the =
y(i) factor from Section 4.5.
|
| Models
|
bunny
|
parasaur
|
horse
|
hand
|
|
#
faces in Mn
|
69,630
|
43,866
|
96,956
|
60,856
|
|
|
34,817
|
21,935
|
48,480
|
30,430
|
|
#
charts
|
75
|
75
|
120
|
60
|
|
#
faces in M0
|
288
|
298
|
470
|
230
|
|
#
vertices in M0
|
146
|
151
|
237
|
117
|
|
(stretch efficiency with
uniform parametrization)
|
0.63
|
0.003
|
0.61
|
0.11
|
|
stretch efficiency
|
0.84
|
0.63
|
0.80
|
0.68
|
|
intra-rectangle efficiency=
|
0.77
|
0.71
|
0.77
|
0.76
|
|
<=
span
style=3D'mso-spacerun:yes'> rectangle-packing effic.
|
=
0.87
|
=
0.89
|
=
0.91
|
=
0.82
|
|
pac=
king efficiency
|
0.67
|
0.63
|
0.70
|
0.62
|
|
texture
efficiency
|
0.56
|
0.40
|
0.56
|
0.42
|
|
Tabl=
e 1: Quantitative results.
|
ST&nb=
sp;A′
(T) / =
ST
A(T), given that charts are resized as in Section 4.3. It=
is
less than unity if some surface regions are sampled more than necessary (i.=
e.
if texture stretch is not uniform everywhere and in every direction). Packing efficiency is the s=
um of
chart areas in 2D divided by the rectangular texture domain area. It is less than unity due to two
factors: the enclosure of chart polygons into rectangles, and the wasted sp=
ace
between the packed rectangles. Texture
efficiency is the product of stretch and packing efficiencies, or total
surface area divided by texture domain area.
A 1-texel gu=
tter is
required between texture charts in the texture domain. The overhead of these gutters depe=
nds on
the resolution assigned to the texture.&nb=
sp;
The packing efficiencies reported in Table
1 ignore this overhead, and therefore assume a
reasonably high sampling rate.
Stretch effi=
ciency
can of course be improved by partitioning the surface into more charts, but
this increases the complexity of the coarsest LOD mesh, and may lower overa=
ll
texture efficiency due to the additional gutter area. Our stretch-minimizing parametriza=
tion
allows larger charts with fewer undersampling artifacts.<=
/p>
6.&n=
bsp;
Summary and future work
We have pres=
ented a
scheme for defining a texture atlas parametrization over the PM representat=
ion
of an arbitrary mesh. This at=
las
permits the same texture image(s) to be used for all LOD mesh approximation=
s in
the PM sequence. In forming t=
he
parametrization, we optimized for both texture stretch and deviation on all
meshes in the sequence. We
demonstrated that optimizing our new stretch metric creates a balanced
parametrization that attempts to prevent undersampling at all locations and
along all directions.
There remain=
a
number of areas for future work:
·Examining how best to address the trade=
-off
between texture quality (stretch) and geometric quality (deviation).
·Constraining anisotropy in the
parametrization.
·Applying our stretch-based parametrizat=
ion
approach to other multiresolution frameworks such as those using subdivisio=
n.
·Speeding up the parametrization optimiz=
ation
of Section 3 using a hierarchical coarse-to-fine approach as i=
n [12].
·Given a known texture, optimizing the
parametrization to consider local texture frequency content, as in [13][26].
·Addressing the problems involved when
mip-mapping texture images containing multiple charts.
·Considering out-of-core execution for c=
omplex
models.
Ackno=
wledgments
We would lik=
e to
thank the MIT Laboratory for Computer Science for use of their equipment. We
also thank Stanford University and Viewpoint for the models used in our exp=
eriments. The first and third authors were
supported in part by grants from the NSF, Sloan Foundation, and Microsoft R=
esearch.
References
[1]Abadjev, V., del Rosario, M., Lebede=
v,
A., Migdal, A., and Paskhaver, V. Metastream. VRML 1999 Proceedings, pp. 53-62.
[2]Cignoni, P., Montani, C., Rocchini, =
C.,
and Scopigno, R. A general method for recovering
attribute values on simplified meshes.&nbs=
p;
IEEE Visualizati=
on
1998, pp. 59-66.
[3]Cohen, J., Olano, M., and Manocha, D=
.
Appearance-preserving simplification. SIGGRAPH 1998, pp. 115-122.=
[4]Eck, M., DeRose, T., Duchamp, T., Ho=
ppe,
H., Lounsbery, M., and Stuetzle, W. Multiresolution analysis of arbitr=
ary
meshes. SIGGRAPH 1995, pp. 173-182.
[5]Floater, M.
Parametrization and smooth approximation of surface triangulations.<=
span
style=3D'mso-spacerun:yes'> CAGD
14(3), pp. 23=
1-250,
1997.
[6]Garland, M., Willmott, A., and Heckb=
ert,
P.
Hierarchical face clustering on polygonal surfaces. Symposium on Interactive 3D Graphics 2001, pp. 49-58.
[7]Gortler, S., Grzeszczuk, R., Szelisk=
i,
R., and Cohen, M. The Lumigraph. SIGGRAPH
1996, pp. 43-54.
[8]Guskov, I., Vidimče, K., Swelde=
ns,
W., and Schröder, P. Normal meshes. SIGGRAPH 2000, pp. 95-102.<=
/span>
[9]Hinker, P., and Hansen, C.
Geometric optimization. IEEE Visualization 1993, pp. 189-195.
[10]Hoppe, H.
Progressive meshes. SIGGRAPH 1996, pp. 99-108.
[11]Hormann, K., and Greiner, G.<=
/a> M=
IPS
– an efficient global parametrization method. Technical Report 27/1998,
Universität Erlangen-Nürnberg.
[12]Hormann, K., Greiner, G., and Campag=
na,
S.
Hierarchical parametrization of triangulated surfaces. Vision, Modeling, and Visualization 1999, pp. 219-226.
[13]Hunter, A., and
Cohen, J.
Uniform frequency images: adding geometry to images to produce
space-efficient textures. IEEE Visualization 2000, pp. 243-250.=
[14]Igarashi, T., =
and
Cosgrove, D. Adaptive unwrapping for interactive
texture painting. Symposium on Interactive 3D Gra=
phics
2001, pp. 209-216.=
=
[15]Kalvin, A., and
Taylor, R.
SuperFaces: Polyhedral approximation with bounded error. SPIE Proceedings 2164, pp. 2-13, 19=
94.=
[16]Kobbelt, L.,
Campagna, S., and Seidel, H.-P. A general framework for mesh
decimation. Proceedings of Graphics Interface ̵=
6;98, pp. 43-50.=
[17]Krishnamurthy,=
V.,
and Levoy, M. Fitting smooth surfaces to dense polygon meshes. SIGGRAPH 1996=
, pp. 313-324.=
=
[18]Lee, A., Sweld=
ens,
W., Schröder, P., Cowsar, L., and Dobkin, D.<=
/span> MAPS: Multiresolution adaptive parametrization of surfaces. SIGGRAPH 1998, pp. 95-104.<=
/span>=
[19]Lévy, B=
., and
Mallet, J.-L. Non-distorted texture mapping for sheared triangulated meshes. SIGGRAPH 1998=
, pp. 343-352.=
=
[20]Lindstrom, P., and Turk, G. F=
ast
and memory efficient polyg=
onal
simplification. IEEE
Visualization 1998, pp. 279-286.
[21]Maillot, J., Y=
ahia,
H., and Verroust, A.
Interactive texture mapping. SIGGRAPH 1993, pp. 27-34.=
[22]Maruya, M. Generating texture map from
object-surface texture data. =
Computer Graphics Forum (Proceedings of
Eurographics ’95) 14(3), pp. 39=
7-405.=
[23]Milenkovic, V.=
Rotational polygon containment and=
minimum
enclosure. Proc. of 14th Annual Symposium on Compu=
tational
Geometry, ACM, 1998.=
[24]Murata, H.,
Fujiyoshi, K., Nakatake, S., and Kajitani, Y. Rectangle-packing-based module
placement. IEEE ICCAD 1995, pp. 472-479.=
=
[25]Sander, P., Gu=
, X.,
Gortler, S., Hoppe, H., and Snyder, J. Silhouette clipping. SIGGRAPH
2000, pp. 327-334.=
=
[26]Sloan, P.-P.,
Weinstein, D., and Brederson, J. Importance driven texture coordinate optimization. Computer Graphics Forum (Procee=
dings
of Eurographics ’98) 17(3), pp. 97=
-104.=
[27]Soucy, M., God=
in,
G., and Rioux, M. A texture-mapping appro=
ach
for the compression of col=
ored
3D triangulations. The Vis=
ual Computer 12, pp. 503-514, 1986.