Computation on arbitrary surfaces

1. Computation on Arbitrary Surfaces

Brandon Lloyd
COMP 258
October 2002
1

2. Computation on Arbitrary Surfaces

• Mathematical framework for Euclidean
geometry enables us to perform important
operations
• Usually peformed on regular grid
• Triangle meshes have irregular connectivity,
hence irregular sampling
• Triangle meshes are general 2-manifolds
2

3. Computation on Arbitrary Surfaces

• Displaced Subdivision Surfaces
• Multi-resolution signal processing on meshes
• Texture synthesis on meshes
3

4. Displaced Subdivision Surfaces

• Aaron Lee, Henry Moreton and Hughes Hoppe
in SIGGRAPH 2000.
• The idea is to use a scalar-valued
displacement over a smooth domain mesh
Control mesh
Smooth domain
surface
Displaced
subdivision surface
4

5.

Representation
• Control mesh for domain surface
• Regular scalar displacement mesh
– Subdivided along with the control mesh to produce a
continuous displacement function
– Uses parameterization of the domain surface
– Displacement map may be used as a bump map
5

6. Conversion Process

• Obtain the control
mesh
• Optimize the control
mesh to more closely
resemble original
Original mesh
Displaced subdivision
surface
• Sample displacement
map
6

7. Simplifying the Control Mesh

• Done with edge collapses
• Map vertex normals from neighborhood of
candidate edge collapse to Gauss sphere
• Disallow collapse if original normals are not
enclosed in spherical triangle
7

8. Optimizing the Domain Surface

Initial control
mesh
Optimized control
mesh
• Move vertices of
control mesh to
more accurately fit
the original mesh
• Densely sample
original mesh and
minimize least
squared distances
• Affects normals, but
does not produce
noticeable problems
8

9. Sampling the Displacement Map

Subdivided
Domain surface
Displacement
field
• Perform subdivision
on optimized control
mesh
• Intersect ray formed
by point and normal
with original mesh
• Store distance in
displacement map
9

10. Applications

• Compression – The
displacement map
contains small,
similar values
• Editing – simply
modify the scalar
field
• Animation – easier
to kinematics with
control mesh
10

11. Compression Results

11

12. Burt-Adelson Pyramids

2
• Prefilter and downsample
image Ln to produce Ln-1
12

13. Burt-Adelson Pyramids

2
2
• Prefilter and downsample
image Ln to produce Ln-1
• Upsample Ln-1 and
subtract from Ln
13

14. Burt-Adelson Pyramids

2
2
• Prefilter and downsample
image Ln to produce Ln-1
• Upsample Ln-1 and
subtract from Ln
• Repeat till you reach L0
14

15. Burt-Adelson Pyramids

2
2
• Prefilter and downsample
image Ln to produce Ln-1
• Upsample Ln-1 and
subtract from Ln
• Repeat till you reach L0
• The result is an image
pyramid with a frequency
subband at each level
15

16. Multiresolution Signal Processing for Meshes

• Igor Guskov, Wim Sweldens and Peter
Schröder in SIGGRAPH 1999.
• Generalizes basic signal processing tools such
as downsampling, upsampling, and filters to
irregular triangle meshes
• Uses a non-uniform relaxation procedure for
geometric smoothing
• Smoothing combined with hierarchical
algorithms are used to build subdivision and
pyramid methods
16

17. Importance of Smoothness

• Geometric smoothness measures variance in
triangle normals.
• Geometric smoothness implies that there
exists a smooth (differentiable)
parameterization for the mesh
• Smooth parameterization is important for
many algorithms
17

18. Importance of Smoothness

• Refinement can use semi-uniform (weights
depend only on local connectivity) subdivision
to obtain geometric smoothness
• It is much harder if we want to coarsify a
mesh and later refine it again.
• Forced to use non-uniform (weights depend on
connectivity and geometry) subdivision.
• The challenge is to ensure smooth local
parameterization.
18

19. Divided Differences

• First order divided difference of g(u,v) with
discrete gi at the vertices is the gradient:
• The normal to the triangles formed by vertices
is given by:
• Second order differences are the the
difference between two normals on
neighboring triangles. Only the magnitude
matters.
19

20. Divided Differences

20

21. Divided Differences

• The magnitude of the second divided
difference over edge e is:
• With coefficients
21

22. Relaxation Procedure

• The relaxation operator R minimizes second
order differences over a small neighborhood
• Define R as the minimizer of a quadratic
energy function E:
• Expand in terms of gi:
2
22

23. Relaxation Procedure

• Set the partial derivative of E with respect to
gi to zero and solve:
• Relaxation for geometry use vertices pi in
place of gi
• For each divided difference use the hinge map
is use for local parameterization. Rotate
triangles about their common edge till they lie
in the same plane
23

24. Relaxation Procedure

• This non-uniform smoothing operator does not
affect triangle shapes much because it takes
geometry into account.
• A semi-uniform scheme makes edge lengths
as uniform as possible and distorts the mesh
Original mesh
Semi-uniform
smoothing
Non-uniform
smoothing
24

25. Upsampling and Downsampling

• Uses Hoppe’s Progressive Mesh (PM)
approach
• Vertex split provides upsampling
• Edge collapse provides
downsampling
• Different than most multi-resolution
schemes where downsampling
removes a fraction of the samples
25

26. Subdivision

• Starts from a coarse mesh and builds finer,
smoother mesh
• Can be viewed as upsampling followed by
relaxation
• Coarse mesh comes from PM.
• The goal is to start from coarse mesh and
produce a smooth mesh with same
connectivity as original with as little distortion
as possible
• Performed one vertex at a time
26

27. Subdivision

• The non-uniform
scheme has access
to parameterization
info of the original
mesh which guides
the subdivision to
give the desired
result
27

28. Building a Pyramid

• Downsampling: vertex n is removed by an
edge collapse
• Subdivision: Points affected by the edge
collapse are subdivided
• Detail Computation: Differences between
points before edge collapse and after
subdivision are stored
28

29. Smoothing and Filtering

• The details from the
pyramid are an
approximate frequency
spectrum
• Scale details for various
filtering effects
29

30. Smoothing and Filtering

• The details from the
pyramid are an
approximate frequency
spectrum
• Scale details for various
filtering effects
• Smoothing does not
mess up texture
mapping!
30

31. Enhancement

• Single resolution scheme
– Smooth mesh a number
of times
– Extrapolate differences
between smoothed and
original mesh
31

32. Enhancement

• Single resolution scheme
– Smooth mesh a number
of times
– Extrapolate differences
between smoothed and
original mesh
• Multi-resolution scheme
– Scale details with values
greater than 1
32

33. Multiresolution Editing

• User manipulates vertices at a level in the
pyramid and system adds finer details back in
• Details are defined with respect to local
frames
Original
Coarsest
Coarsest
edit
Multi-res Single-res
reconst.
reconst.
33

34. Texture Synthesis on Surfaces

• Paper by Greg Turk, SIGGRAPH 2001
• Motivation
– Texture greatly improves appearance
– The ideal system is texture-from-sample
– Existing texture synthesis operates on 2D
grids
– It is difficult to map 2D texture
– It is not always possible to use 3D texture
34

35. Texture Synthesis on Surfaces

• Solution = Synthesize texture directly
on a mesh.
35

36. Texture Synthesis Algorithm

• Based on work by Wei
and Levoy [Wei00]
• Initialize destination
image to white noise
• Process pixels in raster
scan order
• Find best match for
neighborhood in original
image
• Replace pixel in
destination with pixel
from original image
36

37. Texture Synthesis Algorithm

Full 5x5 neighborhood
1 Level
2 Levels
• Use multi-resolution to
get a full neighborhood.
• Create an image pyramid
• Start at the top of the
pyramid
• Use data from higher
levels to fill in
unprocessed pixels in full
neighborhood
• Multi-resolution improves
quality
3 Levels
37

38. Creating the Mesh Hierarchy

• Place uniform random
points on the surface of
the mesh
– Choose a random
polygon based on area
– Choose a random point
within the polygon
38

39. Creating the Mesh Hierarchy

• Use repulsion forces to
get an even distribution
– Map nearby points to a
plane
– Compute forces within
the plane
• Compute Voronoi
diagram to establish
sample connectivity
– Once again map nearby
points to a plane
– Compute diagram within
the plane
• Details in [Turk91]
39

40. Creating the Mesh Hierarchy

• Start by placing n points
on the mesh
• Add an additional 3n
points and repel them
from themselves and
original n
• Create a new mesh
including all 4n points
• Repeat to create several
levels
40

41. Operations on Mesh Hierarchy

• Interpolation
• Low-pass filtering
• Downsampling
• Upsampling
41

42. Operations on Mesh Hierarchy: Interpolation

• Take a weighted average of all mesh vertices
vi within a particular radius r of point p
• The weighting function causes vertex
contributions to falloff smoothly to 0 as
distance from p approaches r.
42

43. Operations on Mesh Hierarchy: Low-pass Filtering

• Borrow techniques from mesh smoothing to
modify vertex positions. Weights wi are
inverse edge length:
• Similarly for colors of adjacent mesh vertices
43

44. Operations on Mesh Hierarchy: Low-pass Filtering

• Regrouping terms, the expression can be
simplified to:
44

45. Operations on Mesh Hierarchy: Upsampling and Downsampling

• Vertices store a color for each level they are
in.
• To downsample from mesh Mk the vertices in
the lower resolution mesh Mk+1 inherit the
blurred mesh colors in Mk.
• To upsample from mesh Mk+1, the colors of the
vertices in Mk are interpolated from Mk+1.
45

46. Vector Field Creation

• Vector field is needed to establish orientation
• A few vectors are assigned at lowest level. All
others set to zero
• Vectors are “pulled” to coarsest mesh by a
number of downsamplings
• Remaining zero vectors are “filled” by diffusing
vectors over the mesh
• Vectors are “pushed” to lower levels by
repeated upsampling
46

47. Surface Sweeping

• Similar to raster scanning in original algorithm
• All vertices are assigned a sweep distance
s(v).
• Anchor vertex has a sweep distance of 0
User-assigned
vectors
Resulting
vector field
Sweep values
47

48. Surface Sweeping

• Calculate an estimate Δw of how much further
downstream a vertex is than its assigned
neighbors:
48

49. Surface Sweeping

• Assign a sweep distance using estimates:
• Propogate sweep distances over coarsest
mesh
• Assign sweep distances to finer meshes with
upsampling
49

50. Neighborhood Colors

• Neighbor positions are defined as offsets (i,j)
from the current sample.
• Local orientation is provided by the vector field
• Step to neighborhood location by marching
along mesh in the direction of the vector field
for i and perpendicular to it for j.
• Each step is the length of the average distance
between vertices
• Retrieve color by interpolation
50

51. Complete Algorithm

51

52.

52

53. Texture Synthesis over Arbitrary Manifold Surfaces

• Paper by Li-Yi Wei and Marc Levoy also in
SIGGRAPH 2001 [WL01]
• Major differences from [Turk01]
– Synthesis ordering – Vertices are visted in random
ordering
– Local coordinate frames
– Neighborhood construction
53

54. Local Coordinate Frames

• Assigned at coarsest level. Finer levels
interpolate from higher levels.
• Random works well for isotropic textures.
• Relaxation produces n-way symmetry:
54

55. Local Coordinate Frames

Isotropic
textures
Anisotropic textures
Random
Spherical Mapping
Relaxed
55

56. Neighborhood Construction

• Local flattening of the mesh and resampling.
• Orthographically project neighboring triangles
of a point p into its local plane.
• Grow region until neighborhood template is
fully covered.
56

57. Neighborhood Construction

• For lower-resolution neighborhood, project
parent face intersected by ray from p in the
direction of the normal.
57

58. Results

58

59. References

[GSS99]
I. Guskov, W. Sweldens and P. Schröder,
Multiresolution Signal Processing for Meshes,
Proceedings of SIGGRAPH ’99, pp. 325-334, 1999.
[LMH00]
A. Lee, H. Morenton and H. Hoppe. Displaced
Subdivision Surfaces, Proceedings of SIGGRAPH
2000, pp.84-97, 2000.
[Turk91]
G. Turk, Generating Textures for Arbitrary Surfaces
Using Reaction-Diffusion, Proceedings of
SIGGRAPH ’91, pp 289-298, 1991.
[Turk01]
G. Turk, Texture Synthesis on Surfaces, Proceedings
of SIGGRAPH ’01, pp.347-354, 2001.
[WL01]
L. Wei and M. Levoy. Texture Synthesis over
Arbitrary Manifold Surfaces, Proceedings of
SIGGRAPH ’01, pp. 355-360, 2001.
59