Transcript Surface Simplification - TAMU Computer Science Faculty Pages

Surface Simplification
Dr. Scott Schaefer
1
Surface Simplification

Given a closed polygon model, reduce the
number of polygons and maintain appearance
of the shape
5804 tris
2500 tris
1000 tris
500 tris
2/35
Reducing Polygons
Perform local, topological operations to
reduce number of polygons
 Vertex removal

3/35
Reducing Polygons
Perform local, topological operations to
reduce number of polygons
 Vertex removal
 Edge Collapse

4/35
Reducing Polygons
Perform local, topological operations to
reduce number of polygons
 Vertex removal
 Edge Collapse
 Face Collapse, …

5/35
Reducing Polygons
Perform local, topological operations to
reduce number of polygons
 Vertex removal
 Edge Collapse
 Face Collapse, …

6/35
Surface Simplification
How do we determine the order of edge
collapse operations?
 Where do we place new vertex after
collapse?

7/35
Error Metrics For Simplification
QEF: Quadratic Error Function
 Measures distance to infinite planes

E (v)   ni  (v  pi )    ni  v  d i 
2
i
2
i
v
ni
pi
8/35
Error Metrics For Simplification
QEF: Quadratic Error Function
 Measures distance to infinite planes


 
T 
2
T
E (v)  v   ni ni v  2v   ni d i     d i 
 i

 i
  i

T
v
ni
pi
9/35
Error Metrics For Simplification
QEF: Quadratic Error Function
 Measures distance to infinite planes


 
T 
2
T
E (v)  v   ni ni v  2v   ni d i     d i 
 i

 i
  i

T
symmetric 3x3
3x1
v
1x1
ni
pi
10/35
Error Metrics For Simplification
QEF: Quadratic Error Function
 Measures distance to infinite planes


 
T 
2
T
E (v)  v   ni ni v  2v   ni d i     d i 
 i

 i
  i

T
symmetric 3x3
3x1
v
1x1
ni
Requires 10 floats independent of
number of polygons!!!
pi
11/35
Combining QEFS
 
T
T 
T
2
E (v1 )  v1   ni ni v1  2v1   ni d i     d i 
 i

 i
  i

 
T
T 
T
2
E (v2 )  v2   n j n j v2  2v2   n j d j     d j 
 j

 j
  j

v1
ni
pj
v2
pi
12/35
Combining QEFS
 
T
T 
T
2
E (v1 )  v1   ni ni v1  2v1   ni d i     d i 
 i

 i
  i

 
T
T 
T
2
E (v2 )  v2   n j n j v2  2v2   n j d j     d j 
 j

 j
  j



 
T
T 
2
2
T
T
E (v)  v   ni ni   n j n j v  2v   ni di   n j d j     di   d j 
j
j
j
 i

 i
  i

v1
Add 10 numbers to combine QEFs!!!
ni
pj
v2
pi
13/35
Placement of Vertices Using QEFs

Place new vertex at minimum of error
function

 
T 
2
T
min E (v)  v   ni ni v  2v   ni d i     d i 
v
 i

 i
  i

T
14/35
Placement of Vertices Using QEFs

Place new vertex at minimum of error
function

 
T 
2
T
min E (v)  v   ni ni v  2v   ni d i     d i 
v
 i

 i
  i

T
E (v)



T 
 2  ni ni v  2  ni d i   0
v
 i

 i

15/35
Placement of Vertices Using QEFs

Place new vertex at minimum of error
function

 
T 
2
T
min E (v)  v   ni ni v  2v   ni d i     d i 
v
 i

 i
  i

T
E (v)



T 
 2  ni ni v  2  ni d i   0
v
 i

 i

1


T  
v    ni ni    ni di 
 i
  i

16/35
Placement of Vertices Using QEFs

Place new vertex at minimum of error
function

 
T 
2
T
min E (v)  v   ni ni v  2v   ni d i     d i 
v
 i

 i
  i

T
E (v)



T 
 2  ni ni v  2  ni d i   0
v
 i

 i

1


T  
v    ni ni    ni di 
 i
  i

Not invertible in flat areas
or straight edges!!!
17/35
Placement of Vertices Using QEFs

Place new vertex at minimum of error
function

 
T 
2
T
min E (v)  v   ni ni v  2v   ni d i     d i 
v
 i

 i
  i

T



T  
v    ni ni    ni d i 
 i
  i

Pseudoinverse minimizes |v|
18/35
Placement of Vertices Using QEFs

Let v  c   where c is a point we want to
minimize the distance to

 
T 
2
T
min E (v)  (c  )   ni ni (c  )  2(c  )   ni d i     d i 

 i

 i
  i

T
19/35
Placement of Vertices Using QEFs

Let v  c   where c is a point we want to
minimize the distance to

 
T 
2
T
min E (v)  (c  )   ni ni (c  )  2(c  )   ni d i     d i 

 i

 i
  i

T
E (v)



T 
 2  ni ni (c  )  2  ni d i   0

 i

 i

20/35
Placement of Vertices Using QEFs

Let v  c   where c is a point we want to
minimize the distance to

 
T 
2
T
min E (v)  (c  )   ni ni (c  )  2(c  )   ni d i     d i 

 i

 i
  i

T
E (v)



T 
 2  ni ni (c  )  2  ni d i   0

 i

 i


T 
    ni ni 
 i



 
T  
   ni d i     ni ni c 
  i
 
 i
21/35
Placement of Vertices Using QEFs

Let v  c   where c is a point we want to
minimize the distance to

 
T 
2
T
min E (v)  (c  )   ni ni (c  )  2(c  )   ni d i     d i 

 i

 i
  i

T
E (v)



T 
 2  ni ni (c  )  2  ni d i   0

 i

 i


T 
v  c      ni ni 
 i



 
T  
   ni d i     ni ni c   c
  i
 
 i
22/35
Plane-Based Quadratic Error Function
Compact representation (10 numbers)
 Fast to combine multiple functions (addition)
 Relatively easy to minimize (pseudoinverse)


Suffers from numerical instabilities
23/35
Surface Simplification Algorithm
Build QEFs for each vertex
 For each edge
 Compute combined QEF and error
 Insert edge into priority queue sorted by
error
 While poly # > target #
 Collapse edge

24/35
Surface Simplification: Edge Collapse

Place new vertex at minimizer of QEF
25/35
Surface Simplification: Edge Collapse
Place new vertex at minimizer of QEF
 QEF of new vertex is combined QEF

26/35
Surface Simplification: Edge Collapse
Place new vertex at minimizer of QEF
 QEF of new vertex is combined QEF
 Remove all edges touching collapsed edge
from priority queue

27/35
Surface Simplification: Edge Collapse
Place new vertex at minimizer of QEF
 QEF of new vertex is combined QEF
 Remove all edges touching collapsed edge
from priority queue
 Recompute QEF/error for all edges touching
new vertex and insert into priority queue

28/35
Surface Simplification: Lazy Method
Place new vertex at minimizer of QEF
 QEF of new vertex is combined QEF
 Mark all edges touching collapsed edge as
dirty

29/35
Surface Simplification: Lazy Method
Place new vertex at minimizer of QEF
 QEF of new vertex is combined QEF
 Mark all edges touching collapsed edge as
dirty
 Mark edges to be removed as invalid

30/35
Surface Simplification: Lazy Method
Place new vertex at minimizer of QEF
 QEF of new vertex is combined QEF
 Mark all edges touching collapsed edge as
dirty
 Mark edges to be removed as invalid
 When removing an edge from the priority
queue, throw away if invalid. If dirty,
recompute QEF and insert into priority queue

31/35
Surface Simplification: Edge Collapse
Edge collapse may alter topology of surface
 Test for topology change and exclude unsafe
edge collapses
 Unsafe edge may become safe after another
collapse
 Alternatively, perform two edge collapses

32/35
Surface Simplification: Edge Collapse
Edge collapse may alter topology of surface
 Test for topology change and exclude unsafe
edge collapses
 Unsafe edge may become safe after another
collapse
 Alternatively, perform two edge collapses

unsafe edge collapses
33/35
Surface Simplification: Edge Collapse
Edge collapse may alter topology of surface
 Test for topology change and exclude unsafe
edge collapses
 Unsafe edge may become safe after another
collapse
 Alternatively, perform two edge collapses

34/35
Surface Simplification
Extremely fast
 Somewhat memory intensive
 Limits maximum surface size
 Greedy algorithm
 Does not guarantee optimal sequence of
edge collapses!!!

35/35