Surface Reconstruction

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

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 &quot;by hand&quot; or via a physical process (e.g. 3D scanning). Assume: Real surface

¥ ¢ ¢

is &quot;nice&quot; ( = &quot;smooth&quot;)

¢

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

¦ ¦

Output

¢

¢

¢

Triangulation of CSG model

Fitted &quot;splines&quot; (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

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

&quot;Mesh&quot; 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

&quot;Mesh&quot; 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

&quot;Mesh&quot; methods Crust Methods

Surface Reconstruction ­ p.17/60

Contour Data Reconstruction

Piece together image from parallel slices Assumes data is &quot;pre-structured&quot; 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

&quot;Mesh&quot; 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

&quot;Mesh&quot; methods Crust Methods

Surface Reconstruction ­ p.20/60

Fitting Gaussian balls

! &quot; ¨

Take linear combination of 3D Gaussians

% ) ' 0(&amp; ! &quot; \$ #&quot; © ¨ 2 © 1 3 2 © ¨ \$ #&quot; 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

&quot;Mesh&quot; 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

&quot;Mesh&quot; methods Crust Methods

Surface Reconstruction ­ p.23/60

-shape triangulation

Start with Delaunay triangulation Take subset of the edges &quot;on&quot; 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

&quot;Mesh&quot; 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

&quot;Mesh&quot; 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

&quot;Mesh&quot; 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

&quot;Mesh&quot; 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

&quot;Mesh&quot; 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 &quot;shape&quot; of .

Surface Reconstruction ­ p.35/60

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

¢ ¢ ¢

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

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

5

if cells of

5 b

interesect

P A b

¢

P

A

A 1

if cells of

¢

P

¢

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

W

Fix a parameter

7 X ¨

(i.e.

W 8 ! 6 W

)

¢

6

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. &quot;The Union of Balls and Its Dual Shape.&quot; In Discrete Computational Geometry, 13:415­440 (1995).

¢

Nina Amenta, Sunghee Choi and Ravi Kolluri. &quot;The power crust.&quot; 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

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