#### Read MedialAxis.pdf text version

Surface Reconstruction

Power Diagrams, the Medial Axis Transform and the Power Crust Algorithm

Matthew Seegmiller and Adam Smith

xaco,adsmith @mit.edu. 6.838 Geometric Computation Lecture 19 -- 13 November 2001

¡

Surface Reconstruction p.1/60

Overview Introduction Weighted distance and power diagrams Medial Axis Transform PowerCrust Algorithm

¢ ¢ ¢ ¢

Surface Reconstruction p.2/60

Introduction

Surface Reconstruction p.3/60

Introduction

What is Surface Reconstruction? Applications Difficulties Survey of techniques

¢ ¢ ¢ ¢

Surface Reconstruction p.4/60

Surface Reconstruction

Given a set of points assumed to lie near an unknown surface , construct a surface model approximating .

£

Surface Reconstruction p.5/60

How it usually works

Input points sampled from the surface either "by hand" or via a physical process (e.g. 3D scanning). Assume: Real surface

¥ ¢ ¢

is "nice" ( = "smooth")

¢

Samples are "dense enough", especially near features such as edges, points, bumps, etc. in usable format for processing

¦ ¦

Output

¢

¢

¢

Triangulation of CSG model

Fitted "splines" (i.e. low-dimensional surfaces)

¢

¢

¤

Surface Reconstruction p.6/60

Applications of 3D Scanning

Reverse engineering / Industrial design

¢

Surface Reconstruction p.7/60

Applications of 3D Scanning

Reverse engineering / Industrial design Performance analysis and simulations (e.g. drag)

¢ ¢

Surface Reconstruction p.7/60

Applications of 3D Scanning

Reverse engineering / Industrial design Performance analysis and simulations (e.g. drag) Realistic virtual environments

¢ ¢ ¢

Surface Reconstruction p.7/60

Applications of 3D Scanning

Reverse engineering / Industrial design Performance analysis and simulations (e.g. drag) Realistic virtual environments Medical Imaging

¢ ¢ ¢ ¢

Surface Reconstruction p.7/60

Applications of 3D Scanning

Reverse engineering / Industrial design Performance analysis and simulations (e.g. drag) Realistic virtual environments Medical Imaging ...

¢ ¢ ¢ ¢ ¢

Surface Reconstruction p.7/60

Modeling a claw I

Surface Reconstruction p.8/60

Modeling a Claw II

Surface Reconstruction p.9/60

Modeling hand-made parts

Surface Reconstruction p.10/60

Medical Shape Reconstruction

Surface Reconstruction p.11/60

Difficulties

Surface not smooth Noisy data Lack of orientation data Surface not watertight

¢ ¢ ¢ ¢

Surface Reconstruction p.12/60

Techniques

Surface Reconstruction p.13/60

Techniques for Surface Reconstruction

Technique Fit parametric surface Assumptions Data fits model

Piece together parallel contours Data from known device Fit Gaussian Kernels -shape Triangulation

§

Given normal at each point Noise-free Dense Sample Dense Sample

"Mesh" methods Crust Methods

Surface Reconstruction p.14/60

Fitting Parametric Surfaces

?

Assume surface is from some known family (e.g. sphere, cylinder, plane, hyperboloid, etc) Find best parameters to fit data

¢ ¢

Surface Reconstruction p.15/60

Fitting Parametric Surfaces

?

Fast, accurate for good data Useless when data is of unknown type

¢ ¢

Surface Reconstruction p.15/60

Techniques for Surface Reconstruction

Technique Fit parametric surface Assumptions Data fits model

Piece together parallel contours Data from known device Fit Gaussian Kernels -shape Triangulation

§

Given normal at each point Noise-free Dense Sample Dense Sample

"Mesh" methods Crust Methods

Surface Reconstruction p.16/60

Techniques for Surface Reconstruction

Technique Fit parametric surface Assumptions Data fits model

Piece together parallel contours Data from known device Fit Gaussian Kernels -shape Triangulation

§

Given normal at each point Noise-free Dense Sample Dense Sample

"Mesh" methods Crust Methods

Surface Reconstruction p.17/60

Contour Data Reconstruction

Piece together image from parallel slices Assumes data is "pre-structured" Applications: medical, topographic terrain maps

¢

¢

¢

Surface Reconstruction p.18/60

Techniques for Surface Reconstruction

Technique Fit parametric surface Assumptions Data fits model

Piece together parallel contours Data from known device Fit Gaussian Kernels -shape Triangulation

§

Given normal at each point Noise-free Dense Sample Dense Sample

"Mesh" methods Crust Methods

Surface Reconstruction p.19/60

Techniques for Surface Reconstruction

Technique Fit parametric surface Assumptions Data fits model

Piece together parallel contours Data from known device Fit Gaussian Kernels -shape Triangulation

§

Given normal at each point Noise-free Dense Sample Dense Sample

"Mesh" methods Crust Methods

Surface Reconstruction p.20/60

Fitting Gaussian balls

! " ¨

Take linear combination of 3D Gaussians

% ) ' 0(& ! " $ #" © ¨ 2 © 1 3 2 © ¨ $ #" 4 5

¢

Surface (inside = positive, outside = negative)

£

¢

%

Surface Reconstruction p.21/60

Fitting Gaussian balls

Problems: Must know surface normal at each point Output always watertight, bubbly-shaped Useful for range scanner data

¢ ¢ ¢

Surface Reconstruction p.21/60

Techniques for Surface Reconstruction

Technique Fit parametric surface Assumptions Data fits model

Piece together parallel contours Data from known device Fit Gaussian Kernels -shape Triangulation

§

Given normal at each point Noise-free Dense Sample Dense Sample

"Mesh" methods Crust Methods

Surface Reconstruction p.22/60

Techniques for Surface Reconstruction

Technique Fit parametric surface Assumptions Data fits model

Piece together parallel contours Data from known device Fit Gaussian Kernels -shape Triangulation

§

Given normal at each point Noise-free Dense Sample Dense Sample

"Mesh" methods Crust Methods

Surface Reconstruction p.23/60

-shape triangulation

Start with Delaunay triangulation Take subset of the edges "on" the surface (In fact, just take shortest edges in graph)

£

¢

¢

Surface Reconstruction p.24/60

-shape triangulation

Bad when samples unevenly spaced (can be fixed using weights on sample points) Works only for noise-free data

¢

¢

Surface Reconstruction p.24/60

Techniques for Surface Reconstruction

Technique Fit parametric surface Assumptions Data fits model

Piece together parallel contours Data from known device Fit Gaussian Kernels -shape Triangulation

§

Given normal at each point Noise-free Dense Sample Dense Sample

"Mesh" methods Crust Methods

Surface Reconstruction p.25/60

Techniques for Surface Reconstruction

Technique Fit parametric surface Assumptions Data fits model

Piece together parallel contours Data from known device Fit Gaussian Kernels -shape Triangulation

§

Given normal at each point Noise-free Dense Sample Dense Sample

"Mesh" methods Crust Methods

Surface Reconstruction p.26/60

Mesh methods

Exploit local information to find a mesh approximating surface Simplify mesh afterwards

¢

¢

Surface Reconstruction p.27/60

£

Mesh methods

Handles noisy data Assumes only sample dense near features (edges, bumps) Methods ad hoc; Rigorous analysis difficult

¢

¢

¢

Surface Reconstruction p.27/60

Techniques for Surface Reconstruction

Technique Fit parametric surface Assumptions Data fits model

Piece together parallel contours Data from known device Fit Gaussian Kernels -shape Triangulation

§

Given normal at each point Noise-free

"Mesh" methods Crust Methods

Sample Dense near Features Dense Sample

Surface Reconstruction p.28/60

Techniques for Surface Reconstruction

Technique Fit parametric surface Assumptions Data fits model

Piece together parallel contours Data from known device Fit Gaussian Kernels -shape Triangulation

§

Given normal at each point Noise-free

"Mesh" methods Crust Methods

Sample Dense near Features Dense Sample

Surface Reconstruction p.29/60

Crust methods

Focus of this lecture Assume only dense sampling Provide other information on : Volume, Skeletal Structure

£

¢

¢

¢

Surface Reconstruction p.30/60

Techniques for Surface Reconstruction

Technique Fit parametric surface Assumptions Data fits model

Piece together parallel contours Data from known device Fit Gaussian Kernels -shape Triangulation

§

Given normal at each point Noise-free

"Mesh" methods Crust Methods

Sample Dense Near Feature

Sample Dense Near Feature

Surface Reconstruction p.31/60

Overview Introduction Weighted distance and power diagrams Medial Axis Transform PowerCrust Algorithm

¢ ¢ ¢ ¢

Surface Reconstruction p.32/60

Weighted Distance and Power Diagrams

Surface Reconstruction p.33/60

Weighted Distance and Power Diagram

Weighted distance Power Diagrams ( = Weighted Voronoi) -shapes

6 ¢ ¢ ¢

Surface Reconstruction p.34/60

Unions of balls

Key concept: Solids can be roughly approximated (exact in the limit) as a union of balls (discs in 2D). Given a set of points , we can view as centers of balls. How can we use this?

Surface Reconstruction p.35/60

Unions of balls

Key concept: Solids can be roughly approximated (exact in the limit) as a union of balls (discs in 2D). Given a set of points , we can view as centers of balls. How can we use this? Try to visualize "shape" of .

Surface Reconstruction p.35/60

Adding weights

Some points are "bigger" than others. sampled from a surface points where sampling is less dense are "bigger". = centers of atoms in a molecule heavier atoms are "bigger".

¢ ¢ ¢

In Power Crust (later), this will be crucial. gets a weight (its radius).

7 ! 8

Each point

Surface Reconstruction p.36/60

Weighted Distance

Work with weighted distance. Distance from a

A [email protected]¨ ¢

point

to a ball

C D8 E

9

!

8

:

G E I H G

F

Surface Reconstruction p.37/60

Normal Distance:

distance from x

x

y

H

z

In 1D, the (normal) squared distance induced by each point gives a parabola centered at .

G

Surface Reconstruction p.38/60

G

F

H

8

E

x

H

r y z

Point has radius parabola gets lowered to intersect axis at distance from .

P Q R8 8 P

I

G

Surface Reconstruction p.39/60

Power Diagram

W A ¨ S A ¨

Distance:

U VT S

¢

9

9

X

A ¨

Weighted Voronoi cell of is set of points that have smaller weighted distance to than to any other point in :

! 8 a Y Y @¨ 1 3 A [email protected]¨ U T S ` A @¨ a

¢

9

!

8

W

for all

U VT S

9

9

9

When all weights are equal, get the usual Voronoi diagram.

¢

Surface Reconstruction p.40/60

7

5

Power Diagram Demo

Demo

Surface Reconstruction p.41/60

G

F

H

8

E

x

H

r y z

Point has radius parabola gets lowered to intersect axis at distance from .

P Q R8 8 P

I

G

Surface Reconstruction p.42/60

G

F

H

8

E

r x y z

Weighted Voronoi cell for contain .

b

H

b

I

G

doesn't necessarily

Surface Reconstruction p.43/60

G

F

H

8

E

x

y z

Some Voronoi cells may be empty!

H

I

G

Surface Reconstruction p.44/60

Power Diagram Demo

More Demo

Surface Reconstruction p.45/60

Intersections

Power diagram edges always go through the intersections of circles

Surface Reconstruction p.46/60

Weighted Delaunay Complex

Weighted Delaunay Complex = Dual of Power Diagram

A B 1

Add an edge

5

if cells of

5 b

interesect

P A b

¢

P

A

Add a triangle intersect

A 1

if cells of

¢

P

Add a tetrahedron...

¢

A B

A

P

Surface Reconstruction p.47/60

Weighted Delaunay Complex

Surface Reconstruction p.48/60

Weighted Distance and Power Diagram

Weighted distance Power Diagrams ( = Weighted Voronoi) -shapes

6 ¢ ¢ ¢

Surface Reconstruction p.49/60

Dual Complex

Subset of weighted Delaunay graph

A @¨ ¢

Only keep edge

S A @¨ P 8 c8 Q !

if balls at

intersect:

¢

P

A

.

P

Surface Reconstruction p.50/60

Changing the radii

W

Fix a parameter

7 X ¨

(i.e.

W 8 ! 6 W

)

¢

6

Consider new radii

T S ` A @¨ T S A @¨ 9 X 9

8 a

¢

Power diagram stays the same since . Weighted Delaunay graph stays the same. Dual Complex grows if shrinks if

d eW ¢ 6 ¢ 6 4 6 W

¢

¢

¢

f eW

4

!

A

6

7

Surface Reconstruction p.51/60

-shapes

As grows from to , progress from empty graph to full weighted Delaunay graph:

6 X W

Surface Reconstruction p.52/60

-shapes

As grows from to , progress from empty graph to full weighted Delaunay graph:

6 X W

Surface Reconstruction p.53/60

-shapes

9 5 11 15 1 3 13 14 12 10 8 4 6

7

2

Surface Reconstruction p.54/60

-shapes

Surface Reconstruction p.55/60

-shapes

4 5 6

1 3 2

Surface Reconstruction p.56/60

-shapes

9 5 11

4 6

12 1 3 10 8

7

2

Surface Reconstruction p.57/60

Who cares?

This ordering is useful for visualizing structure of the point set. Example: Simple surface reconstruction

Other apps: chemical modeling, visualization

Surface Reconstruction p.58/60

Overview Introduction Weighted distance and power diagrams Medial Axis Transform PowerCrust Algorithm

¢ ¢ ¢ ¢

Surface Reconstruction p.59/60

Selected References

¢

Hughes Hoppe. Surface reconstruction from unorganized points. Ph.D. Thesis, University of Washington, June 1994.

¢

H. Edelsbrunner. "The Union of Balls and Its Dual Shape." In Discrete Computational Geometry, 13:415440 (1995).

¢

Nina Amenta, Sunghee Choi and Ravi Kolluri. "The power crust." To appear in the sixth ACM Symposium on Solid Modeling and Applications 2001.

¢

http://www.alphashapes.org

¢

http://www.geomagic.com

¢

http://www.cs.utexas.edu/users/amenta/powercrust/

¢

http://pages.cpsc.ucalgary.ca/ laneb/Power/

g

Surface Reconstruction p.60/60

#### Information

69 pages

#### Report File (DMCA)

Our content is added by our users. **We aim to remove reported files within 1 working day.** Please use this link to notify us:

Report this file as copyright or inappropriate

761395