Computation on Arbitrary Surfaces
Computation on Arbitrary Surfaces
Computation on Arbitrary Surfaces
Displaced Subdivision Surfaces
Conversion Process
Simplifying the Control Mesh
Optimizing the Domain Surface
Sampling the Displacement Map
Applications
Compression Results
Burt-Adelson Pyramids
Burt-Adelson Pyramids
Burt-Adelson Pyramids
Burt-Adelson Pyramids
Multiresolution Signal Processing for Meshes
Importance of Smoothness
Importance of Smoothness
Divided Differences
Divided Differences
Divided Differences
Relaxation Procedure
Relaxation Procedure
Relaxation Procedure
Upsampling and Downsampling
Subdivision
Subdivision
Building a Pyramid
Smoothing and Filtering
Smoothing and Filtering
Enhancement
Enhancement
Multiresolution Editing
Texture Synthesis on Surfaces
Texture Synthesis on Surfaces
Texture Synthesis Algorithm
Texture Synthesis Algorithm
Creating the Mesh Hierarchy
Creating the Mesh Hierarchy
Creating the Mesh Hierarchy
Operations on Mesh Hierarchy
Operations on Mesh Hierarchy: Interpolation
Operations on Mesh Hierarchy: Low-pass Filtering
Operations on Mesh Hierarchy: Low-pass Filtering
Operations on Mesh Hierarchy: Upsampling and Downsampling
Vector Field Creation
Surface Sweeping
Surface Sweeping
Surface Sweeping
Neighborhood Colors
Complete Algorithm
Texture Synthesis over Arbitrary Manifold Surfaces
Local Coordinate Frames
Local Coordinate Frames
Neighborhood Construction
Neighborhood Construction
Results
References
6.52M
Категория: МатематикаМатематика

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
English     Русский Правила