Similar presentations:

# Computation on arbitrary surfaces

## 1. Computation on Arbitrary Surfaces

Brandon LloydCOMP 258

October 2002

1

## 2. Computation on Arbitrary Surfaces

• Mathematical framework for Euclideangeometry 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 Hoppein 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 controlmesh

• 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 controlmesh

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

SubdividedDomain 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 – Thedisplacement 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

22

• Prefilter and downsample

image Ln to produce Ln-1

• Upsample Ln-1 and

subtract from Ln

13

## 14. Burt-Adelson Pyramids

22

• 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

22

• 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 PeterSchrö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 intriangle 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 (weightsdepend 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) withdiscrete 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 divideddifference over edge e is:

• With coefficients

21

## 22. Relaxation Procedure

• The relaxation operator R minimizes secondorder 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 togi 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 notaffect 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-uniformscheme 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 anedge 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 thepyramid are an

approximate frequency

spectrum

• Scale details for various

filtering effects

29

## 30. Smoothing and Filtering

• The details from thepyramid 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 thepyramid 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 directlyon a mesh.

35

## 36. Texture Synthesis Algorithm

• Based on work by Weiand 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 neighborhood1 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 randompoints 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 toget 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 pointson 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 verticesvi 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 tomodify 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 besimplified to:

44

## 45. Operations on Mesh Hierarchy: Upsampling and Downsampling

• Vertices store a color for each level they arein.

• 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 furtherdownstream 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 inSIGGRAPH 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 levelsinterpolate from higher levels.

• Random works well for isotropic textures.

• Relaxation produces n-way symmetry:

54

## 55. Local Coordinate Frames

Isotropictextures

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, projectparent 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