Transcript Centroidal Voronoi Diagram

Mesh Coarsening
zhenyu shu
2007.5.12
Mesh Coarsening




Large meshes are commonly used in
numerous application area
Modern range scanning devices are used
High resolution mesh model need more time
and more space to handle
Large meshes need simplification to improve
speed and reduce memory storage
Mesh Coarsening

Size, quality and speed

Mesh optimization

Many simplification methods now
QEM

Garland M, Heckbert P. Surface simplification
using quadric error metrics. In: Proceedings
of the Computer Graphics, Annual
Conference Series. Los Angeles: ACM Press,
1997. 209~216
QEM




Quadric Error Metric method
Using Pair Contraction to simplify the mesh
Minimize Quadric function when contracting
Define Quadric
Q   A, b, c    nn , dn, d
T
Q  v   v Av  2b v  c
T
T
2

Quadric

Define Quadric of each vertex
n v  d 
T
i
i
i
2


  Qi  v     Qi   v 
i
 i

Pair Contraction
Pair Selection

Condition




 v1 , v2 
is an edge or
v1  v2  t , where t is a threshold
When performing  v1 , v2   v , Q  Q1  Q2
Choose position of v minimizingQ  v 
Q  v   0  v  A1b

If A is not invertible, choose among two
endpoints and midpoint of two endpoints
Algorithm Summary





Compute the Q matrices for all the initial vertices.
Select all valid pairs.
Compute the optimal contraction targetv for each
valid pair  v1 , v2 
Place all the pairs in a heap keyed on cost with the
minimum cost pair at the top.
Iteratively remove the pair  v1 , v2  of least cost from
the heap, contract this pair, and update the costs of
all valid pairs involving v1.
Advantage

Efficiency, local, extremely fast

Quality, maintain high fidelity to the original
mesh

Generality, can join unconnected regions of
original mesh together
Result
Original model
with 69451 triangles
triangles
An approximation
with 1000
Topology manipulation

Hattangady N V. A fast, topology
manipulation algorithm for compaction of
mesh/faceted models[J]. Computer-Aided
Design. 1998, 30(10): 835-843.
Edge collapsing
Edge swapping
Edge smoothing

let N be the average of all Ci
Data Structure of mesh model
A type of
data structure to
present mesh
model for
reference

Remeshing

Surazhsky V, Gotsman C. Explicit surface
remeshing[C]. Aachen, Germany:
Eurographics Association, 2003

Improve mesh quality by a series of local
modification of the mesh geometry and
connectivity
Vertex Relocation


v
with neighbors v1 , v2 ,
, vk
Find new location of v to satisfy some
constraints, e.g. improving the angles of the
triangles incident on v
Vertex Relocation

Map these vertices into a plane, v is
mapped to the origin, v1 , v2 , , vk satisfy
v  vi  0  vinew ,1  i  k

The angles of all triangles at v are
proportional to the corresponding angles and
sum to 2
Vertex Relocation

Let new position of v be the average of
v1 , v2 , , vk to improve the angles of the
adjacent faces

Bring new position of v back to the original
surface by maintain same barycentric
coordinate
Detail


(c) is original mesh, (b) is new mesh, (d) is
2D mesh which defines a parameterization of
(c)
Use the same barycentric coordinates in (a)
and (d)
Area-based Remeshing


Area equalization is done iteratively by
relocating every vertex such that the areas of
the triangles incident on the vertex are as
equal as possible
Extending method above to relocating
vertices such that the ratios between the
areas are as close as possible to some
specified values 1 , 2 , , i
Area-based Remeshing
k

 x, y   arg min   Ai  x, y   i A 
2
i 1

Here Ai is the area of triangle p, pi , pi 1 , A
is the area of polygon  p1 , , pk 
Area-based Remeshing
Curvature sensitive remeshing


More curved region contain small triangles
and a dense vertex sampling, while almost
flat regions have large triangles
Define density function as1/  K  v    H 2  v  
here K and H are approximated discrete
Gaussian and mean curvatures
Meyer M, Desbrun M, Schroder P, et al. Discrete differential geometry
operator for triangulated 2-manifolds [A]. In: Proceedings of Visual
Mathematics'02, Berlin, 2002. 35～57
Result
Result
CVD

Valette S, Chassery J M. Approximated
Centroidal Voronoi Diagrams for Uniform
Polygonal Mesh Coarsening[J]. Computer
Graphics Forum. 2004, 23(3): 381-389
Voronoi Diagram

Given an open set  of Rm, and n different
points zi; i=0,...,n-1, the Voronoi Diagram can
be defined as n different regions Vi such that:
Vi  x   d ( x, z i )  d ( x, z j ) j  0,..., n  1, j  i
where d is a function of distance.


Centroidal Voronoi Diagram

A Centroidal Voronoi Diagram is a Voronoi
Diagram where each Voronoi site zi is also
the mass centroid of its Voronoi Region:
zi
x  ( x)dx


  ( x)dx
V
V
here  ( x ) is a density function of Vi
Centroidal Voronoi Diagram

Centroidal Voronoi Diagrams minimize the
Energy given as:
E
n 1

i 0

Vi
 ( x) x  z i dx
2
On mesh, Energy above becomes to

n 1 
E 2     C V  j  j
j
i
i 0 

2



C j Vi
 j j
C j Vi
j
2





Construct CVD

Here
j



Cj
Cj

xdx
 j  area  C j 
dx
Construct CVD based on global minimization
of the Energy term E2
Algorithm Summary




Randomly choose n different cells in mesh
and these cells form n regions
Cluster all cells in mesh by extending these
regions and choosing correct cells’ owner to
minimize the energy term E2
Now calculate each center of these regions
and replace each region with it’s center
Triangulate and get new mesh
Clustering
Triangulate
Sample
Sample
Result Quality and Speed
Pros and Cons

Pros



High quality of result
Optimization of original mesh
Cons


Slow
Global
Thanks