Transcript Nameeta Shah and Yong Kil

MAPS – Multiresolution Adaptive
Parameterization of Surfaces
(SIGGRAPH ’98)
By
Aaron W. F. Lee; Wim Sweldens; Peter
Schröder; Lawrence Cowsar; David Dobkin
Presented by
Nameeta Shah and Yong J. Kil
CIPIC visualization and graphics research group
January 30, 2003
Multiresolution (ECS 289L) - Winter 2003
1
Introduction (1/2)
What does MAPS do?
• Construct smooth parameterizations of irregular connectivity triangulations of
arbitrary genus 2-manifolds.
• Construct hierarchy of models of different fineness in O(N log N) time and
space complexity.
Original m esh (level 14)
Irregular Original Mesh (M)
Smooth Parameterized Mesh (MJ)
CIPIC visualization and graphics research group
January 30, 2003
Multiresolution (ECS 289L) - Winter 2003
2
Introduction (2/2)
What is a smooth parameterization?
A “nice” parameterization. E.g. having subdivision connectivity, that is,
a mesh produced by 4-to-1 splitting.
4-to-1 splittingof a triangular face: (a) the initial face; (b)
after one 4-to-1 split; (c) after two 4-to-1 splits.
Advantages:
Texture mapping, morphing, adaptive remeshing, and other classical
multiresolution analysis.
CIPIC visualization and graphics research group
January 30, 2003
Multiresolution (ECS 289L) - Winter 2003
3
General Overview
Original m esh (level 14)
M
M0
1. Take the original mesh (M)
2. Define a base (coarse) mesh
(M0) with a mapping
(parameterization) of all the
original points.
3. Subdivide (e.g. 4-to-1) the faces
of the base mesh and do a
inverse mapping.
MJ
CIPIC visualization and graphics research group
January 30, 2003
Multiresolution (ECS 289L) - Winter 2003
4
Previous Work
Multiresolution Analysis of Arbitrary Meshes (SIGGRAPH ’95)
by Matthias Eck and Hoppe.
1.
2.
Base domain by
Voronoi tiling.
Parameterization
by sequence of
local harmonic
maps.
Cons:
•
Time complexity.
•
No explicit control
over the base
domain. E.g.
feature edges.
CIPIC visualization and graphics research group
January 30, 2003
Multiresolution (ECS 289L) - Winter 2003
5
Overview of MAPS
Original m esh (level 14)
Interm ediate m esh (level 6)
Coarsest m esh (level 0)
Constructs the base mesh (M0)
by using ideas based on
mesh simplification. I.e.
Dobkin-Kirkpatrick (DK)
algorithm: Iterative vertex
removal with guarantees on
number of intermediate mesh
levels.
Constructs the parameterization
iteratively along with the
vertex removal strategy.
CIPIC visualization and graphics research group
January 30, 2003
Multiresolution (ECS 289L) - Winter 2003
6
Features of MAPS
Features of MAPS:
• Fast coarsification strategy to define the base domain
(M0), avoiding difficulties of finding Voronoi tiles.
• Vertex and edge tags to constrain the
parameterization to align with selected features.
• Adaptive subdivision connectivity.
CIPIC visualization and graphics research group
January 30, 2003
Multiresolution (ECS 289L) - Winter 2003
7
Notations
• Triangular mesh is represented as a pair (P, K) where P is a set
of N point positions pi = (xi,yi,zi), 1 I  N and K contains the
adjacency information. ((PL, KL) is the original mesh and (P0, K0)
is the base mesh)
•  (|K|) is the polyhedron consisting of points, edges and
triangles in R3
• A set of vertices is independent if no two vertices are neighbors
• A set of vertices is maximally independent if no larger
independent set contains it.
• 1-ring neighborhood of a vertex {i} is the set
N (i) = { j | {i, j}  K}
• The star of a vertex {i} is the set of simplices containing i.
• The curvature estimate at a vertex {i} is
K(i) = |k1| + |k2|
CIPIC visualization and graphics research group
January 30, 2003
Multiresolution (ECS 289L) - Winter 2003
8
Hierarchical Representation
• Vertex Removal
– Based on the Dobkin – Kirkpatrick (DK) algorithm
• Basic idea for going from level l to l -1
– Take any maximal independent set among the vertices of degree
atmost b (b=11) in Pl (l is the level in the hierarchy)
– Remove the star of all the vertices in the set
– Retriangulate the hole
• Advantage – guarantees L i.e. the number of levels to be O(logN)
• Drawback - Randomly chosen vertices, not using the geometric
information
• Solution
– Put vertices in priority queue based on their weights calculated as
follows:
w(, i) =  * a(i) / amax + (1- ) * k(i) / kmax
– Intuitively, vertices with small and flat star area will be weighed less
CIPIC visualization and graphics research group
January 30, 2003
Multiresolution (ECS 289L) - Winter 2003
9
Flattening and Retriangulation
• Conformal map za which minimizes metric distortion to map the
neighborhood of a removed vertex into the plane. *
• Piecewise linear approximation of za is denoted by i for the
removed vertex {i}.
• Vertex {i} is at the origin and its 1-ring neighbors are mapped as
follows:
i(pj ) = rka exp(ika), where
k
ki = # of 1-ring neighbors
a = 2 / ki
rk = || pi - pj ||
k
• Retriangulate using Constrained Delaunay triangulation
CIPIC visualization and graphics research group
January 30, 2003
Multiresolution (ECS 289L) - Winter 2003
10
Mesh levels
CIPIC visualization and graphics research group
January 30, 2003
Multiresolution (ECS 289L) - Winter 2003
11
Initial Parameterization
• Construction of a bijection  from  (|KL|) to  (|K0|)
• Want to have a mapping l from the top level L to mesh level l
which will allow us to map points between meshes at any level
of the hierarchy
• Barycentric coordinates are used for parameterization
• Constructing l - 1 for each vertex {i} at level L
Case 1. {i} is in the current level, nothing to do
l - 1 (pi) = l (pi) = pi
Case 2. {i} just got removed in the current level
l - 1 (pi) = pj + pk + pm where pi is in {j, k, m} in
the new level
CIPIC visualization and graphics research group
January 30, 2003
Multiresolution (ECS 289L) - Winter 2003
12
Parameterization contd.
• {i} was removed before previous level
– If the triangle that contained {i} at the previous level is still in the
new level, do nothing.
– Otherwise, assign barycentric coordinates based on
the new triangle that {i} is in.
CIPIC visualization and graphics research group
January 30, 2003
Multiresolution (ECS 289L) - Winter 2003
13
Tagging and Feature Lines
•
Mark important vertices
•
Mark important paths
CIPIC visualization and graphics research group
January 30, 2003
Multiresolution (ECS 289L) - Winter 2003
14
Remeshing
•
Uniform remeshing
•
Smoothing the parameterization
•
Adaptive Remeshing
CIPIC visualization and graphics research group
January 30, 2003
Multiresolution (ECS 289L) - Winter 2003
15
Conformal Structures of Surfaces
Xianfeng Gu and Shing-tung Yau, Computing Conformal Structures of Surfaces, Communications in
Information and Systems vol. 2, no. 2, pp. 121-146, december 2002
CIPIC visualization and graphics research group
January 30, 2003
Multiresolution (ECS 289L) - Winter 2003
16
Results(1/3)
CIPIC visualization and graphics research group
January 30, 2003
Multiresolution (ECS 289L) - Winter 2003
17
Results(2/3)
CIPIC visualization and graphics research group
January 30, 2003
Multiresolution (ECS 289L) - Winter 2003
18
Results(3/3)
CIPIC visualization and graphics research group
January 30, 2003
Multiresolution (ECS 289L) - Winter 2003
19
Statistics
Dataset
3-hole
fandisk
fandisk
head
horse
horse
Input size
(triangl es)
Hierarchy
creation
Levels
11776
12946
12946
100000
96966
96966
18 (s)
23 (s)
23 (s)
160 (s)
163 (s)
163 (s)
14
15
15
22
21
21
P0 size
(triangles)
Remeshing
tolerance
Remesh
creation
Output size
(triangl es)
120
168
168
180
254
254
(NA)
1%
5%
0 5%
1%
0 5%
8 (s)
10 (s)
5 (s)
440 (s)
60 (s)
314 (s)
30720
3430
1130
74698
15684
63060
Table 1: Selected statistics for the examples discussed in the text. All times are in seconds on a 200 MHz PentiumPro.
CIPIC visualization and graphics research group
January 30, 2003
Multiresolution (ECS 289L) - Winter 2003
20
Conclusion (Pros vs. Cons)
Contribution
• Describe an O(N log N) time and storage algorithm to construct
a logarithmic level hierarchy of arbitrary topology.
• Construct a smooth parameterization of the original mesh within
an error tolerance.
• Using the smooth parameterization, it can do adaptive,
hierarchical remeshing of arbitrary meshes into subdivision
connectivity meshes.
• Allows feature preservation of vertices and edges
Useful
• Multiresolution editing and compression, morphing, texture
mapping.
CIPIC visualization and graphics research group
January 30, 2003
Multiresolution (ECS 289L) - Winter 2003
21
Misc2
Figure 10: Remeshing of 3 holed torus using midpoint subdivision.
The parameterization is smooth within each base domain triangle,
but clearly not across base domain triangles.
Figure 12: Example remesh of a surface with boundaries.
CIPIC visualization and graphics research group
January 30, 2003
Multiresolution (ECS 289L) - Winter 2003
22