Express Mail No. ED 348423973 US
.UNITED STATES PATENT APPLICATION
FOR STRETCH-DRIVEN MESH PARAMETERIZATION USING SPECTRAL
ANALYSIS
CROSS-REFERENCE TO RELATED APPLICATION
[000 1 ] This application claims the benefit of U.S. Provisional Patent
Application No. 601577,775 filed June 8, 2004, the contents of which are
hereby incorporated by reference.
BACKGROUND
[0002] The present application relates to the generation of computer
graphics. In particular it relates to rendering a three dimensional object
realistically in two dimensions.
[0003] Computer graphic techniques for mapping textures to threedimensional
surfaces have been developed and implemented in software
and hardware. These conventional implementations usually map
rectangular texture samples, defined by a mesh structure, to the surface
being rendered. Such texture samples or maps tend to present certain
limitations that may be reflected in the quality of the rendered image
from these maps.
UTl LlTY PATENT
MS Docket No. 308293.02
1) Express Mail No. ED 348423973 US
SUMMARY
[0004] The following presents a simplified summary of the
disclosure in order to provide a basic understanding to the reader. This
summary is not an extensive overview of the disclosure and it does not
identify keylcritical elements of the invention or delineate the scope of
the invention. Its sole purpose is to present some concepts disclosed
herein in a simplified form as a prelude to the more detailed description
that is presented later.
[0005] The present examples provide a way of rendering three
dimensional objects in two dimensions. One or more grids are typically
disposed on an object to map its contours. The surface of an object may
be broken up into a number of subsurfaces (that each have their own
grids), that may be chosen to lessen stretch distortion due to variation in
surface heights.
[0006] The present examples provide a fully automatic method,
called iso-charts, that can create texture atlases on arbitrary meshes. It
considers stretch not only when parameterizing charts (such as
measuring distortion), but also when forming charts. An output atlas may
bound the stretch by a user specified constant, allowing the user to
balance the number of charts against their stretch.
[0007] Many of the attendant features of this invention will be more
readily appreciated as the same becomes better understood by reference
UTl LlTY PATENT
MS Docket No. 308293.02
d Express Mail No. ED 348423973 US
to the following detailed description considered in connection with the
accompanying drawings.
DESCRIPTION OF THE DRAWINGS
[0008] The patent or application file contains at least one drawing
executed in color. Copies of this patent or patent application publication
with color drawings will be provided by the Office on request and
payment of the necessary fee. These and other features and advantages
of the present invention will be better understood from the following
detailed description read in light of the accompanying drawings, wherein:
[0009] FIG. 1 is a block diagram showing stretch driven mesh
parameterization using spectral analysis.
[OOl 01 FIG. 2 shows the chartification and parameterization results
for a bunny model.
[OOl 11 FIG. 3: illustrates finding the optimal partition boundary as a
graph cut problem.
[0012] FIG. 4: Illustrates a comparison of different graph-cut
capacities.
[0013] FIG. 5 illustrates the partitioning of tubular shapes for the
example of a bunny ear shape having spectral clustering partitioning into
five charts.
UTl LlTY PATENT
MS Docket No. 308293.02
u)
Express Mail No. ED 348423973 US
[OO 1 41 FIG. 6 illustrates an exemplary computing environment 600
in which the systems and methods described in this application, may be
implemented.
[OOl 51 Like reference numerals are used to designate like parts in
the accompanying drawings.
DETAILED DESCRIPTION
[00 1 61 The detailed description provided below in connection with
the appended drawings is intended as a description of the present
examples and is not intended to represent the only forms in which the
present invention may be constructed or utilized. The description sets
forth the functions of the invention and the sequence of steps for
constructing and operating the invention in connection with the examples
illustrated. Those skilled in the art will appreciate that the sequence of
acts or steps illustrated is exemplary, and that the order may be varied to
achieve the same result. Also, the same or equivalent functions and
sequences may be accomplished by different examples of the invention.
[0017] Although the present examples are described and illustrated
herein as being implemented in a two dimensional computer graphics
system, the system described is provided as an example and not a
limitation. As those skilled in the art will appreciate, the present
4
UTl LlTY PATENT
MS Docket No. 308293.02
* Express Mail No. ED 348423973 US
invention is suitable for application in a variety of different types of
image generation systems, including three dimensional models generated
from computer graphics and the like.
INTRODUCTION
[0018] The example provided includes a method for parameterizing
arbitrary meshes ("mesh paramaterization") using multiple charts.
Decomposition into charts and parameterizing each chart may be
automatic and based on the concepts of spectral analysis on a matrix of
geodesic distances between vertices and the parameterization stretch.
[0019] Mesh parameterization may be utilized in the rendition of
three dimensional graphics. Many signals may be used in rendering three
dimensional graphics, including normals, colors, or shading parameters,
and can be associated with three dimensional surfaces in an effort to
produce more realistic images. In particular "texture maps" may be used
to describe a surface's texture, so that a more realistic image is
reproduced.
[0020] The example described below provides an automatic method
that generates texture maps which tend to provide fidelity using
minimum texture samples. The example provided may also be applied to
texture synthesis, geometry compression, remeshing and many other
geometric processes.
[002 1 ] This type of breakdown may tend to minimize the stretch
depending upon how the map areas are selected. Thus, in modeling an
5
UTl LlTY PATENT
MS Docket No. 308293.02
Express Mail No. ED 348423973 US
image for computer graphic rendition a single unfolding of an arbitrary
mesh onto a texture image may create regions of high distortion in a
reproduced image. So, generally a mesh is partitioned into a set of
charts. The set of charts make up a texture atlas. Each chart is assigned
a set of parameters by a region of a texture domain, and these
parameterizations collectively form an atlas.
[002 21 A fully automatic method, called iso-charts, may create
texture atlases on arbitrary meshes. It considers stretch not only when
parameterizing charts (such as measuring distortion), but also when
forming charts. An output atlas may bound stretch by a user specified
constant, allowing the user to balance the number of charts against their
stretch.
[0023] The approach of stretch driven mesh parameterization using
spectral analysis combines two techniques: 1) stretch-minimizing
parameterization, based on the surface integral of the trace of the local
metric tensor, and 2) the "isomap" or MDS ("multi-dimensional scaling")
parameterization, based on an eigen-analysis of the matrix of squared
geodesic distances between pairs of mesh vertices. Typically only a few
iterations of nonlinear stretch optimization need be applied to the MDS
parameterization to obtain low-stretch atlases. The close relationship
found between these two parameterizations allows application of spectral
clustering based on MDS to partition the mesh into charts having low
stretch. A graph cut algorithm is applied to optimize chart boundaries
6
UTILITY PATENT
MS Docket No. 308293.02
I
Express Mail No. ED 348423973 US
and further minimize stretch, follow sharp features, and avoid
meandering.
[0024] The method of stretch driven mesh parameterization using
spectral analysis tends to create texture atlases quickly, with fewer charts
and lower stretch useful in applications like geometric re-meshing.
Another example describes an extension, signal-specialized atlas
creation, that tends to promote efficient sampling of surface signals, and
tends to produce better texture maps by considering signal stretch in
chart formation.
[002 51 Parameterization may be used in many geometry processing
algorithms, such as texture mapping, morphing, editing, remeshing and
compression. To parameterize an arbitrary mesh, a texture atlas may be
built. A target surface that is to be modeled is typically first partitioned
into a set of charts, called chartification, which are parameterized and
packed into a texture domain.
[0026] In particular creating a texture atlas may include
considerations of how much a distance is shrunk or "stretched" when a
mesh is applied to a surface in an attempt to produce a more realistic
image.
[002 71 Distortion in a final image recreated from the texture atlas
may be corrected or minimized in various ways. One way involves the
proper selection of the charts in a texture atlas. In another the number of
charts in an atlas may be varied. Thus, the way that a targeted surface is
7
UTl LlTY PATENT
MS Docket No. 308293.02
Express Mail No. ED 348423973 US
partitioned into charts has an effect on the appearance of the three
dimensional object being rendered in two dimensions.
[002 81 Because a 3D surface is not isometric to a 2D plane,
parameterization causes distortion. Distortion can be measured in many
ways, including how well angles or areas are preserved, or how much
parametric distances are stretched or shrunk onto the surface. Stretch
driven mesh parameterization using spectral analysis focuses on distance
distortion, specifically a definition of geometric stretch, which measures
the average and worst-case stretching of local distances over the surface.
[0029] Minimizing stretch typically utilizes nonlinear optimization.
Stretch minimization tends to be slow, and it tends to disregard stretch
when forming charts in favor of unrelated heuristics that cut across sharp
features or cluster based on chart compactness and planarity. The latter
is true because if computing a stretch-minimizing embedding for a chart
is costly, then computing it over all possible chart partitionings tends to
be completely impractical.
[0030] In an attempt to improve this, a form of nonlinear
dimensionality reduction called IsoMap is applied. IsoMap tends to
minimize geodesic distance distortion between pairs of vertices on the
mesh. The key to this application is the observation that geodesic
distance distortion is closely related to stretch, though they are defined
quite differently. IsoMap thus tends to provide two features in atlas
generation. It provides an effective way, called spectral analysis, to
8
UTl LlTY PATENT
MS Docket No. 308293.02
Express Mail No. ED 348423973 US
decompose the model into large, geometrically meaningful parts like
animal appendages that can be parameterized with little stretch. Without
extra computation, it also supplies an initial parameterization for each
part. In fact, it typically provides a good starting point for stretch
minimization, so that a few iterations of nonlinear stretch optimization
may quickly converge and remove problem "foldovers" easily.
[003 1 1 A feature in stretch driven mesh parameterization using
spectral analysis is a stretch-driven chartification method which clusters
based on a spectral analysis of the matrix of geodesic distances. It can
allow a user to bound stretch while typically keeping the number of
charts small. Such spectral analysis simultaneously obtains a low-stretch
parameterization of charts quickly. A graph cut may be used to optimize
chart boundaries, and modify the capacity metric to consider geodesic
distance distortion and therefore stretch, given the relationship
discovered between the two metrics. Stretch driven mesh
parameterization using spectral analysis utilizes "special spectral
clustering" to create typically better charts in cases when geometric parts
have periodic (tubular) structure. Finally, the approach has been
generalized to signal-specialized atlas creation. Stretch driven mesh
parameterization using spectral analysis atlases may be the first whose
chart partitioning, as well as parameterization, is adapted to a particular
signal such as a normal or color map.
Process Overview
9
UTILITY PATENT
MS Docket No. 308293.02
Express Mail No. ED 348423973 US
[003 21 FIG. 1 is a block diagram showing stretch driven mesh
parameterization using spectral analysis. The approach to stretch driven
mesh parameterization using spectral analysis may be thought of as a
top-down, stretch-driven method. Given a surface and a user-specified
stretch value at block 101, the following are performed: at block 102 the
surface spectral analysis is computed, providing an initial
parameterization. Block 102 is described in further detail below in the
section titled "Surface Spectral Analysis". At block 103 a few iterations of
a conventional stretch optimization are performed. At block 104 if the
stretch of this derived parameterization is less than the threshold, the
process stops. At block 105 spectral clustering to partition the surface
into charts is performed. At block 106 the optimization of chart
boundaries using the graph cut technique is performed. At block 106 the
charts are recursively split until the stretch criterion is met.
1003 31 The result of the process is a set of charts whose
parameterizations have bounded stretch. Chart topology need not be
explicitly checked; the stretch-driven process ensures that all charts are
eventually subdivided into topological disks since otherwise
parameterization stretch is infinite. A check is made to see that the
parameterization domain does not overlap itself and subdivide in that
typically rare case. As a post-processing step, small charts are merged
together if the parameterization stretch of the merged chart is less than
the user specified stretch value.
10
UTl LlTY PATENT
MS Docket No. 308293.02
Y
Express Mail No. ED 348423973 US
[0034] Distortion is bounded using two norms on geometric or
signal stretch. The L2 norm integrates (y2 m a +y'min)/ 2 over the surface,
followed by an over- all square root. The Lm norm maximizes max {ymax,
1 /y,in) over the entire surface. Here, ymax and ymin are scalar functions
over the surface representing the largest and smallest singular values of
the Jacobian of the affine mapping from texture space to model or signal
space at any point. The inclusion of shrink, 1 /ymin, in the Lm norm is a
modification which penalizes undersampling. The bounding of distortion
using two norms on geometric or signal stretch is described in "System
and Method for Providing Signal-Specialized Paramaterization", U.S.
Patent Application Number 1011 38,289, filed May 1, 2002, the contents
of which are incorporated herein by reference.
[003 51 FIG. 2 shows the chartification and parameterization results
for a bunny model. An Iso-chart atlas 200 created for the bunny model
201 is shown. As can be seen the surface of the bunny has been
partitioned into 15 large charts, which can be flattened with typically
lower stretch than previous methods (L2 = 1.01, Loo = 2.26). As can be
seen parts of the model like its head, ears, and body are decomposed
into large charts. In the example shown the computation took about 1
minute.
Chartification and Parameterization
[0036] Chartification and Paramaterization includes application of
surface spectral analysis, reduction of stretch with spectral analysis,
11
UTl LlTY PATENT
MS Docket No. 308293.02
1C
Express Mail No. ED 348423973 US
surface spectral clustering, computing optimal parameter boundaries,
medial region embedding, spectral clustering for tubular shapes,
implementation, and signal specialized atlas creation.
Surface Spectral Analysis
[003 71 This process builds upon the conventional dimensionality
reduction method IsoMap (isometric feature mapping). Given a set of
high-dimensional points, IsoMap computes the geodesic distances along
a manifold as sequences of hops between neighboring points. It then
applies MDS (multidimensional scaling) to these geodesic distances to
find a set of points embedded in low-dimensional space with similar
pairwise distances.
[003 81 This application of IsoMap is termed "surface spectral
analysis" and outline its computation is described as follows. Given a
surface with N vertices, xi, where each xi is a position in 3D space
compute the symmetric matrix DN of squared geodesic distances
between surface vertices.
Next apply double centering and normalization to DN to yield BN =-
(1 /~)JNDN JN, where JN is a NxNcentering matrix defined by JN =I
-(1 /M 1 lTI ,is the identity matrix, and 1 is a vector of ones of
length N. This constrains the center of gravity of the computed
point set to lie at the origin.
UTl LlTY PATENT
MS Docket No. 308293.02
'Y
Express Mail No. ED 348423973 US
Compute the eigenvalues Xiand their corresponding eigenvectors vi
of B ~ , ( i = l , 2, ..., N).
For each vertex i o f the original surface, its embedding in the new
space is an N-dimensional vector yi whose j-th component is given
by i/ =&v'j(j=1,2 ,..., N).
[0039] The eigenvalues Xi and their corresponding eigenvectors ?of
BN ,(i= 1, 2, ..., N) form the spectral decomposition of the surface shape.
The vectors yi represent the warped model, and are in one-to-one
correspondence with the original vertices xi. Eigenvectors corresponding
to large eigenvalues represent global, low-frequency features on the
surface while eigenvectors corresponding to small eigenvalues represent
high-frequency details. It is natural to consider the high-energy, lowfrequency
components as a basis of chartification and parameterization.
[0040] Although Neigenvalues are needed to fully represent a
surface with Nvertices, a small number of them typically dominate the
energy. For the bunny model shown in FIG. 2, the top 5 eigenvalues
constitute over 85% of the squared energy; in other words,
(xI=5I A1. I C;,A), > 85%. Therefore only the n cc N largest eigenvalues
and corresponding eigenvectors are calculated, leading to an ndimensional
embedding for all vertices.
[004 1 ] The distortion of this n-dimensional embedding can be
calculated as the sum of the geodesic distance distortion over all vertices.
UTl LlTY PATENT
MS Docket No. 308293.02
Express Mail No. ED 348423973 US
For each vertex i, its geodesic distance distortion ("CDD") under the
embedding is defined as:
[0042] where is the n-dimensional embedding coordinate of
vertex i, and dgeo(i,/) is the geodesic distance between vertex iand j. This
definition can be extended from a vertex to a triangle by averaging the
distortions of its three vertices, and is used in the later section entitled
"Computing Optimal Partition Boundaries".
[0043] When n =2, surface spectral analysis yields a surface
parameterization minimizing the sum of squared CDD over all vertices.
Thus it is noted that surface spectral analysis, can be simultaneously
applied to two problems: decomposition for chartification, and
parameterization.
[0044] To calculate the geodesic distances between surface points
of polygonal models, a conventional fast matching method, which runs at
O(hQ lg N) and obtains typically more precise results than the Dijkstra
graph search method, since it allows paths that cut across mesh triangles
is used.
Spectral Analysis and Stretch
[004 51 CDD-minimizing and stretch-minimizing parameterizations
both focus on distance distortion. Still, CDD differs from stretch in
14
UTILITY PATENT
MS Docket No. 308293.02
* Express Mail No. ED 348423973 US
several ways. It is global rather than local, since it considers distance
between vertices that are arbitrarily far on the surface, rather than local
stretch induced by the Jacobian at a point. It is difference-based rather
than ratio-based since it penalizes differences between the original and
parametric distances rather than how much unit-length tangent vectors
are stretched. And it is discrete rather than continuous since it only
considers distance distortions between vertex pairs rather than stretch in
every triangle and in every direction.
[0046] The discrete nature of spectral analysis, which measures
distance distortion only between vertex pairs, gives rise to a problem
with triangle flips. Our process for calculating spectral analysis and
stretch provides a simple solution. Since triangle flips are defined to
cause infinite stretch, and our algorithm typically splits charts whose
stretch is above the user's threshold, any finite threshold guarantees the
final atlas will not contain flips.
[0047] Spectral analysis typically requires solution of a lowdimensional
eigenvalue problem rather than general nonlinear
optimization. The computation can be accelerated further using the
"landmark" extension described below. Despite differences between
stretch and CDD, spectral analysis typically reduces stretch effectively.
Surface Spectral Clustering
[0048] If the parameterization induced by spectral analysis fails to
satisfy the user's stretch threshold, it is partitioned into several smaller
15
UTl LlTY PATENT
MS Docket No. 308293.02
e
Express Mail No. ED 348423973 US
charts. Recalling that global features of a model such as the head, ears,
legs, and tails of animals correspond to the larger eigenvalues, they are
used to partition. A few representative vertices using the spectral analysis
results are computed. Then charts are grown simultaneously around
these representatives, with a method termed "surface spectral clustering".
The process is as follows:
1. Rank the eigenvalues Ai and corresponding eigenvectors { from
surface spectral analysis such that (A1 2 A2 r 2 AN ).
2. Get the top n eigenvalues and eigenvectors such that Xn/A,+l is
maximized.
3. For each vertex i o f the mesh, compute its n-dimensional
embedding coordinates: 2 = J;i;T(j =&&...,TI).
4. For each of the n embedding coordinates, find the two vertices
with maximum and minimum coordinate values and set them as 2n
representatives.
5. Remove representatives which are too close together, yielding m
I 2n representatives.
6. Partition the mesh into m parts by growing charts
simultaneously around the representatives using the geodesic
distance calculated in surface spectral analysis.
[0049] Step 2 amounts to a relative error threshold that finds the
"knee" in the curve relating energy to the number of eigenvalues. The
UTl LlTY PATENT
MS Docket No. 308293.02
k
Express Mail No. ED 348423973 US
value of n is a measure of shape complexity: n < 3 implies a fairly flat
shape; large n implies a complicated shape with significant detail.
Eliminating the remaining N -n eigenvalues ignores high frequency
detail and avoids partitioning into too many charts. The present
implementation also restricts n I 10 (see the section titled
"Implementation Details"), which in turn restricts the maximum number
of sub-charts.
[OOS 01 Since representatives computed from different dimensions in
Step 4 may be close and so redundant, Step 5 removes them. A distance
threshold of 10 times the average edge length of the input mesh is used.
In Step 6, the geodesic distance from a triangle to a representative vertex
is computed as the average of the geodesic distances of the triangle's
three vertices to the representative.
Computing Optimal Partition Boundaries
[OOS 11 After splitting charts, the boundaries between them are
optimized. Chart boundaries should satisfy two objectives: 1) they should
cut through areas of high curvature without being too jaggy, and 2) they
should minimize the embedding distortions of the charts they border.
[0052] The first objective has been addressed by conventional
methods, which minimize various measures of chart compactness while
choosing chart cuts of shortest length or along edges having high
dihedral angle. A conventional graph cut method is used to decompose
UTl LlTY PATENT
MS Docket No. 308293.02
Express Mail No. ED 348423973 US
meshes, an idea applied to mesh parameterization. The second objective
relates to having a stretch-minimizing partition.
[0053] The second objective may be solved by formulating the
optimal boundary problem as a graph cutting problem. For simplicity, the
binary case which splits the surface into two is presented. When
subdividing into more than two charts, we consider each pair of
neighboring charts in turn.
[005 41 FIG. 3: illustrates finding the optimal partition boundary as a
graph cut problem. In finding the boundary: 300 the shape is
decomposed into three parts, lateral areas 301 (red), 302 (blue) and
medial area 303 (green). A graph 304 is constructed for the medial area
303. An optimal boundary between two charts 302 and 301 is sought.
The initial partition is generated by using surface spectral clustering.
Then a medial region, 303 is generated, by expanding an area to either
side of the initial split boundary. The medial region's size is proportional
to the total area of the unsplit patch; 30% is used for all examples. Now
an undirected flow network graph 305 can be constructed from 303
using an extension of the conventional method of hierarchal mesh
decomposition using fuzzy clustering and cuts. In this method the
definition of "capacity" between the two adjacent triangles of the mesh fi
and 6 is defined as
~(fi,6 )'acang(f;; 6)+(1 -a)~distort (fi, 6)
UTl LlTY PATENT
MS Docket No. 308293.02
Express Mail No. ED 348423973 US
[OOS 51 The first term in equation (2) corresponds to the first
objective of a nonjaggy cut through edges of high dihedral angle. This is
accomplished with:
-1
[00 5 63
[005 71 where dans(f; 6)is defined as (1 -cos ad), cxd is the angle
between normals of the triangles fiand fi, and avg(d,,,,) is the average
angular distance between adjacent triangles.
[00 5 81 The second term in equation (2) measures embedding
distortion, defined as
[00 5 91 ddSlO,V;,f,) (4)
CdiSlOrt K fi )=
avg~~disto,
[0060] d&,orKt , r,r IGDD,(A - GDD, (A) I +IGDD, (f, - GDD,(~1 , (5)
[006 1 ] where GDDA(Q and CDDe(0 are the CDDs of triangle fi under
the embedding induced by 302 or 301, respectively. avg(ddistort) is the
average ddiston (fi, 0 over all pairs of adjacent triangles. This definition of
cdis[on(fi, fi) prefers boundary edges whose adjacent triangles balance
CDD between embeddings determined by 302 and 301. In other words,
the cut should avoid placing a triangle on the wrong side where it creates
unnecessary distortion.
[0062] FIG. 4: Illustrates a comparison of different graph-cut
capacities. The weight parameter oc trades off the two objectives. Setting
a= 1 may achieve good results for models with sharp features. For
19
UTILITY PATENT
MS Docket No. 308293.02
.r
Express Mail No. ED 348423973 US
shapes whose dihedral angles vary smoothly in the medial area, it tends
toward a cut of shortest length 401. But this split produces too much
stretch in the right chart, which must be split again to satisfy the user's
threshold 404.
[0063] On the other hand, setting a=O minimizes CDD 402, which
avoids chart proliferation but makes the boundary jaggier. A com bination
is shown with a= 0.5, 403. Although the parameterization stretch is a
little larger than 402, a smoother boundary may be desirable in many
applications.
Landmark IsoMap for Medial Region Embedding
[0064] Returning to FIG. 4, to compute an optimal partition, two
embeddings over the unsplit chart may be needed: one corresponding to
side A 302 and one to side B 301. These two embeddings define CDDA
and CDDB. Neither sub-chart "core", A or B, contains the inner vertices of
the medial region C 303. So the embedding coordinates of C's vertices
using spectral analysis on A or B alone may not be computed. Since it is
not yet known which triangles of C will be joined with A and which with B,
embeddings for each sub-chart that are unduly distorted by triangles
that end up inserted in the other sub-chart should be avoided. An
extension of IsoMap, called landmark IsoMap, embeds the medial region
implicitly given only embeddings for each core and the geodesic distance
relationship of C's to each core's vertices.
UTILITY PATENT
MS Docket No. 308293.02
Express Mail No. ED 348423973 US
[0065] Suppose there are NA vertices in A. After performing surface
spectral analysis, there are nA eigenvalues Ai and corresponding
eigenvectors {. The n~-dimensional embeddings of all vertices in A form
the columns of an nA XNA matrix LA:
[0067] A vertex p outside A can be located in its n~ -dimensional
embedding space by using its known geodesic distances to the vertices in
A as constraints. This same idea identifies geographic location using a
finite number of distance readings in GPS. Let A, denote the column
vector of squared distances between p and the vertices in A. The n~ -
dimensional embedding coordinate < can be computed by the formula:
[0069] where A is the column mean of DNd, and L: is the
pseudoinverse transpose pf LA:
[0071] Now GDDs for all vertices in C under the embedding induced
by A may be calculated, and similarly for B.
Special Spectral Clustering for Tubular Shapes
[0072] FIG. 5 illustrates a bunny ear shape having spectral clustering
partitioning into five charts. In particular the figure illustrates the
partitioning of tubular shapes. Column a 501 shows general spectral
2 1
UTl LlTY PATENT
MS Docket No. 308293.02
Express Mail No. ED 348423973 US
clustering (as described in the section entitled "Surface Spectral
Clustering"), while columns b-d 502,503, 504 show binary clustering
based on the first, second, and third eigenvalues. Given the n dominant
eigenvalues, surface spectral clustering partitions the shape into at most
2n charts. This works well for complex shapes but can produce too many
charts for simple shapes with n I 3. As shown 501, spectral clustering
partitions the bunny ear into 5 charts. To avoid excessive partitioning, we
can instead subdivide the chart into two, according to the first of the
embedding coordinates. This approach often works, but it is not ideal for
tubular/cylindrical protrusions, a common feature in typical meshes.
[0073] Another method 504 observes that dominant eigenpairs of
the distance matrix can be used to detect and segment data points with
cyclic distributions. The following heuristic has proven effective, which
regards a shape as tubular if its eigenvalues Xi meet the following
conditions:
C:=l > 0.9, i.e. the top three eigenvalues represent the I&[ shape well.
X1/X2 > 3, means the shape is long enough.
A2/h3 < 2, means the shape is cyclic.
A3/h4 > 3, i.e. the 4-th eigenvalue decreases quickly enough to be
ignored.
[0074] As long as a shape is detected as a cylinderltube, it may be
partitioned into two sub-charts. The second and third dimensions can be
22
UTILITY PATENT
MS Docket No. 308293.02
Express Mail No. ED 348423973 US
regarded as cyclic axes. Partitioning the shape according to the third
principal dimension, which corresponds to the shorter cyclic axis,
produces more planar patches. As shown 504 the results using the third
component, provides a more natural split than using the first or second
component 502, 503.
[0075] The overall chart subdivision process may be summarized as
follows. If the top three eigenvalues contain less than 90% of the energy,
we perform "general" spectral clustering (as previously described in the
section entitled "Surface Spectral Clustering"). Otherwise, if the chart is
tubular, a "special" spectral clustering described in this section is
performed. In all other cases, binary spectral clustering is performed,
using the single embedding coordinate corresponding to the largest
eigenvalue. Typically, only a single nonbinary chart subdivision is
performed (at the first iteration); thereafter, binary subdivision suffices.
Implementation Details
[0076] A naive implementation of stretch-driven chartification and
parameterization algorithm is'expensive, especially as the number of
model vertices grows. To accelerate the computation, the Landmark
IsoMap process is utilized as described in the last section, to compute the
embedding coordinates for vertices in the medial region. Landmark
IsoMap selects qvertices as landmark points, where q << N. Instead of
computing the NxN matrix of squared geodesic distances, DN ,an qxN
matrix D , , is computed measuring distances from each vertex to the
23
UTl LlTY PATENT
MS Docket No. 308293.02
* Express Mail No. ED 348423973 US
landmark points only. Em bedding coordinates of the q landmark points
are computed using surface spectral analysis while the remaining vertices
can be computed using the method described in the section entitled
"Landmark IsoMap for Medial Region Embedding".
LO0771 To get the landmark points, models may be simplified by
performing half edge collapse operations based on the quadric error
metric. Progressive meshes may free the user from having to simplify
each chart from scratch. Enough vertex splits are performed and
recorded in the PM to obtain enough landmark points within the chart.
[0078] For all charts, we use q = 100 landmark points, which makes
the processing fast even on large charts. When the chart has fewer than
100 vertices, simply include them all as landmark points. Though the
landmark embedding can exhibit more stretch than the full analysis, this
is likely only for large chart that have high stretch and will need to be
refined anyway. Landmark embedding with q independent of chart size
thus provides a fast but typically reasonable heuristic.
[0079] Since the top 10 eigenvalues typically constitute over 95% of
the squared energy in the test models, another method to speed up the
process is to calculate only the first 10 eigenpairs in surface spectral
analysis. In summary, the geodesic distance computation is reduced to
O(qN IogN) and spectral decomposition to a@).
Signal-Specialized Atlas Creation
UTILITY PATENT
MS Docket No. 308293.02
* Express Mail No. ED 348423973 US
[0080] So far, geometric stretch has been used to drive chartification
and parameterization. Iso-Charts for stretch-driven mesh
parameterization using spectral analysis can also be generalized to
produce a signal-specialized parameterization which represents a given
surface signal using textures as compact as possible.
[008 1 ] Iso-Charts for stretch-driven mesh parameterization using
spectral analysis may be extended to surface signals by computing the
pairwise signal distances between vertices. Given two vertices iand jand
the geodesic path between them, the signal distance between them is
defined as the sum of signal differences between pairs of adjacent points
along the path. Applying spectral analysis to a matrix of signal distances
creates a parameterization that preserves them, and therefore ties Iso-
Charts for stretch-driven mesh parameterization using spectral analysis
to signal distortion in the same way as the process was previously
described as applying to geometric distortion.
[0082] Typical signals such as textured colors may exhibit much
more variation than the underlying geometry. Surface spectral analysis
using signal distances typically produces a complex embedding with
many dominant eigenvalues which may lead to excessive partitioning.
This leads to the combination of geometric and signal stretch as
described in "System and Method for Optimizing Geometric Stretch of a
Parametrization Scheme", U.S. Patent Application Number 10/138,751,
filed May 1, 2002, the contents of which are incorporated herein by
25
UTl LlTY PATENT
MS Docket No. 308293.02
Express Mail No. ED 348423973 US
reference. The solution achieved here defines distance with a similar
combination of geodesic and signal distances:
[0084] where d,iA/;/)is the signal distance between iand j. Good
results are typically achieved with 8=0.5.
[OOSS] FIG. 6 illustrates an exemplary computing environment 600
in which the systems and methods described in this application, may be
implemented. Exemplary computing environment 600 is only one
example of a computing system and is not intended to limit the examples
described in this application to this particular computing environment.
[0086] The computing environment 600 can be implemented with
numerous other general purpose or special purpose computing system
configurations. Examples of well known computing systems, may
include, but are not limited to, personal computers, hand-held or laptop
devices, microprocessor-based systems, multiprocessor systems, set top
boxes, programmable consumer electronics, gaming consoles, Consumer
electronics, cellular telephones, PDAs, and the like.
[0087] The computer 600 includes a general-purpose computing
system in the form of a computing device 601. The components of
computing device 601 can include one or more processors (including
CPUs, CPUs, microprocessors and the like) 607, a system memory 609,
and a system bus 608 that couples the various system components.
26
UTl LlTY PATENT
MS Docket No. 308293.02
Express Mail No. ED 348423973 US
Processor 607 processes various computer executable instructions to
control the operation of computing device 601 and to communicate with
other electronic and computing devices (not shown). The system bus 608
represents any number of several types of bus structures, including a
memory bus or memory controller, a peripheral bus, an accelerated
graphics port, and a processor or local bus using any of a variety of bus
architectures.
[0088] The system memory 609 includes computer-readable media
in the form of volatile memory, such as random access memory (RAM),
and/or non-volatile memory, such as read only memory (ROM). A basic
inputloutput system (BIOS) is stored in ROM. RAM typically contains data
and/or program modules that are immediately accessible to and/or
presently operated on by one or more of the processors 607.
[0089] Mass storage devices 604 may be coupled to the computing
device 601 or incorporated into the computing device by coupling to the
buss. Such mass storage devices 604 may include a magnetic disk drive
which reads from and writes to a removable, non volatile magnetic disk
(e.g., a "floppy disk") 605, or an optical disk drive that reads from and/or
writes to a removable, non-volatile optical disk such as a CD ROM or the
like 606. Computer readable media 605, 606 typically embody computer
readable instructions, data structures, program modules and the like
supplied on floppy disks, CDs, portable memory sticks and the like. The
UTl LlTY PATENT
MS Docket No. 308293.02
Express Mail No. ED 348423973 US
Iso-Chart process may reside on one or more computer readable media,
as well as in the system memory 609, or its equivalent.
[0090] Any number of program modules can be stored on the hard
disk 61 0, Mass storage device 604, ROM and/or RAM 609, including by
way of example, an operating system, one or more application programs,
other program modules, and program data. Each of such operating
system, application programs, other program modules and program data
(or some combination thereof) may include an embodiment of the
systems and methods described herein.
[009 1 ] A display device 602 can be connected to the system bus
608 via an interface, such as a video adapter 61 1. A user can interface
with computing device 702 via any number of different input devices 603
such as a keyboard, pointing device, joystick, game pad, serial port,
and/or the like. These and other input devices are connected to the
processors 607 via input/output interfaces 61 2 that are coupled to the
system bus 608, but may be connected by other interface and bus
structures, such as a parallel port, game port, and/or a universal serial
bus (USB).
[0092] Computing device 600 can operate in a networked
environment using connections to one or more remote computers
through one or more local area networks (LANs), wide area networks
@VANS) and the like. The computing device 601 is connected to a
UTl LlTY PATENT
MS Docket No. 308293.02
Express Mail No. ED 348423973 US
network 61 4 via a network adapter 61 3 or alternatively by a modem, DSL,
ISDN interface or the like.
[0093] Those skilled in the art will realize that storage devices
utilized to store program instructions can be distributed across a
network. For example a remote computer may store a tool such as the
adaptive instrumentation runtime monitoring and analysis software. A
local or terminal computer may access the remote computer and
download a part or all of the software to run the program. Alternatively
the local computer may download pieces of the software as needed, or
distributively process by executing some software instructions at the
local terminal and some at the remote computer (or computer network).
Those skilled in the art will also realize that by utilizing conventional
techniques known to those skilled in the art that all, or a portion of the
software instructions may be carried out by a dedicated circuit, such as a
DSP, programmable logic array, or the like.
[0094] As can be seen in the example above spectral analysis on the
matrix of geodesic distances between points on a surface tends to
provide a fast, simple, and effective way to simultaneously solve two
problems in atlas generation: partitioning the model into charts, and
parameterizing those charts. The method may also be simply generalized
to account for signal rather than geometric distance, to optimize the atlas
for a particular signal. As shown spectral analysis tends to reduce stretch
and provides a starting point for further stretch minimization. Finally, a
29
UTl LlTY PATENT
MS Docket No. 308293.02
Express Mail No. ED 348423973 US
stretch-driven atlas generator that improves results over previous
techniques in geometry remeshing and texture map creation has been
shown.
UTl LlTY PATENT
MS Docket No. 308293.02

Express Mail No. ED 348423973 US
CLAIMS
1. A method of performing stretch-driven mesh parameterization
comprising:
computing a spectral analysis to parameterize a mesh; and
iterating a stretch optimization calculation to further optimize the
initial parameterization.
2. The method of performing stretch-driven mesh parameterization of
claim 1 in which the spectral analysis computes a geodesic distance along
a manifold between a plurality of points.
3. The method of performing stretch-driven mesh parameterization of
claim 2 in which the geodesic distances are calculated using a fast
matching method.
4. The method of performing stretch-driven mesh parameterization of
claim 2 further comprising applying multidimensional scaling to the
geodesic distances to find a set of points embedded in low dimensional
space having a similar pairwise distance.
5. A method of performing stretch-driven mesh parameterization
comprising:
3 1
UTILITY PATENT
MS Docket No. 308293.02
Express Mail No. ED 348423973 US
computing a surface spectral analysis to provide an initial
parameterization; and
iterating a stretch optimization calculation to further optimize the
initial parameterization.
6. The method of performing stretch-driven mesh parameterization of
claim 5 further comprising comparing a stretch to a threshold.
7. The method of performing stretch-driven mesh parameterization of
claim 5 further comprising stopping the calculation if the stretch is less
than the threshold.
8. A method of performing stretch-driven mesh parameterization
comprising
partitioning a surface for chartification into a plurality of charts by
spectral clustering.
9. The method of performing stretch-driven mesh parameterization of
claim 8 in which spectral clustering includes partitioning a surface by
larger eigenvalues.
UTl LlTY PATENT
MS Docket No. 308293.02
Express Mail No. ED 348423973 US
10. The method of performing stretch-driven mesh parameterization of
claim 9 in which spectral clustering further includes using a spectral
analysis to compute a plurality of representative vertices.
11. The method of performing stretch-driven mesh parameterization of
claim 9 in which spectral clustering further includes using the plurality of
representative vertices to grow a plurality of charts.
12. A method of performing stretch-driven mesh parameterization
comprising:
a means for ranking eigenvalues from a surface spectral analysis;
a means for selecting n top eigenvatues and n top eigenvectors;
a means for computing a plurality of n-dimensional embedding
coordinates of each vertex of a mesh;
a means for setting representatives of the plurality of ndimensional
embedding coordinates;
a means for removing a plurality of representatives found to be too
close together; and
a means for partitioning the mesh into m parts.
13. A method of creating a texture map comprising:
optimizing a boundary between a corresponding plurality of charts
by graph cutting.
33
UTILITY PATENT
MS Docket No. 308293.02
a
Express Mail No. ED 348423973 US
14. The method of creating a texture map of claim 13 in which graph
cutting further comprises partitioning a chart into a first region and
a second region by spectral clustering.
15. The method of creating a texture map of claim 14 in which graph
cutting further comprises generating a third medial region.
16. The method of creating a texture map of claim 15 in which the third
medial region is formed along a boundary between the first region and
the second region.
17. The method of creating a texture map of claim 14 in which the chart
boundary is chosen so that adjacent triangles balance CDD between
embeddings determined by the first region and the second region.
18. The method of creating a texture map of claim 17 in which the chart
boundary is chosen by using a CDD balance metric measuring embedding
distortion having the form of
UTILITY PATENT
MS Docket No. 308293.02
1,
Express Mail No. ED 348423973 US
19. The method of creating a texture map of claim 14 in which the chart
boundary includes a smooth cut through a plurality of edges having a
high dihedral angle.
20. The method of creating a texture map of claim 19 in which the
plurality of smooth edges is chosen utilizing:
21. The method of creating a texture map of claim 14 in which the chart
boundary is chosen by a weighted sum of a first term having a first form
-1
of: cmgV;, &)= , and a second term having a second form
22. The method of creating a texture map of claim 14 in which the first
term is weighted by multiplication by a constant, and the second term is
weighted by multiplication by the sum of unity minus the constant.
23. A method of performing stretch-driven mesh parameterization
comprising:
35
UTl LlTY PATENT
MS Docket No. 308293.02
&
Express Mail No. ED 348423973 US
recursively refining each chart of a plurality of charts until a stretch
criteria is met.
24. A method of creating a texture map comprising:
chartifying to produce a plurality of charts by a method that
proxies a stretch.
25. The method of creating a texture map of claim 24 in which
optimizing the stretch of the plurality of charts includes producing a first
plurality of charts.
26. The method of creating a texture map of claim 24 in which
optimizing the stretch of the plurality of charts includes performing
iterations to determine if an additional plurality of charts are needed for
optimization.
27. The method of creating a texture map of claim 26 in which
optimizing a derived stretch parameterization includes comparing the
stretch to a threshold.
28. The method of creating a texture map of claim 27 in which
optimization is concluded when the derived stretch parameterization is
less than the threshold.
36
UTl LlTY PATENT
MS Docket No. 308293.02
Express Mail No. ED 348423973 US
29. A method of performing spectral analysis for chartification
comprising:
ranking a plurality of eigenvalues Ai and corresponding plurality of
eigenvectors derived from a surface spectral analysis such that (A1 2 A2
2 * * * 2 AN);
selecting a set of top n eigenvalues and a set of eigenvectors such
that the quantity An/An+l is maximized;
computing, for each vertex i of a plurality of meshes, a set of ndimensional
embedding coordinates;
finding, for each of the n embedding coordinates, a first vertices
with a maximum coordinate value and a second vertices with a minimum
coordinate values, and setting the first vertice with a maximum
coordinate value and the second vertice with a maximum coordinate
value as a first plurality of 2n representatives;
removing each of the plurality of representatives which are too
close together to yield a second set of m representatives, where m r 2n;
and
growing charts simultaneously around the representatives using
the geodesic distance calculated with surface spectral analysis to
partition the mesh into m parts.
UTILITY PATENT
MS Docket No. 308293.02
Express Mail No. ED 348423973 US
30. A method of performing stretch-driven mesh parameterization
comprising:
forming a warp of a model by spectral analysis;
performing clustering on the warp of the model.
31. A method of chartification comprising:
partitioning a surface into a plurality of charts based upon a priori
knowledge of a signal.
32. The method of chartification of claim 31 in which partitioning is
based on computing a pairwise signal distance between a plurality of
vertices.
33. The method of chartification of claim 32 in which the plurality of
pairwise signal distances between a plurality of vertices is the sum of a
plurality of signal differences between a plurality of pairs of adjacent
points along a path.
34. The method of chartification of claim 31 in which the signal is color.
35. The method of chartification of claim 34 in which the plurality of
pairwise signal distances between a plurality of vertices is a combination
of geodesic and signal distances.
38
UTl LlTY PATENT
MS Docket No. 308293.02
Express Mail No. ED 348423973 US
36. The method of chartification of claim 35 in which the combination of
geodesic and signal distances is represented by:
37. A method of performing stretch-driven mesh parameterization
comprising:
computing a spectral analysis to parameterize a mesh by
computing a signal distance along a manifold between a plurality of
points.