Producing Curved Models from Line Drawings

Matthew Kaplan Elaine Cohen

Inria Rhone-Alpes

University of Utah

+

=

+

=

Overview

1. Goals

2. Related work

3. Line labelling

4. Solver

5. Finding constraints with user guidance

6. Results

7. Future work

Overview

1. Goals

2. Related work

3. Line labelling

4. Solver

5. Finding constraints with user guidance

6. Results

7. Future work

Goals

Input – a sketch of contours representative of the surface geometry of a single object

Output – 2 ½D model of the object represented by the sketch

Allow the artist to draw naturally

No restriction on ordering of stroke input

Allow either curved or planar surfaces

No restriction to orthographic projection

Single view modeling

System Overview

Overview

1. Goals

2. Related work

3. Line labelling

4. Solver

5. Finding constraints with user guidance

6. Results

7. Future work

Related Work

There is a vast literature on sketch based modeling, line labelling, and reconstructing surfaces

The reader should be familiar with :

Single View Modeling

Zhang et al. 2002

Interpreting Line Drawings of Curved Objects

Malik 1987

Related Work – Reconstruction

Reconstruct a model from an existing drawing

Huffman 1971 – Line labels

Clowes 1971 – Line labels

Mackworth 1973 – Gradient space

Turner 1974 – Curved object line labels

Malik 1987 – Curved object line labels

Shapira & Freeman 1978

Lamb & Bandopadhay 1990

Varley &+ - many

Lipson & Shpitalni 1996 – Correlation

Shesh & Chen 2004 - SmartPaper

Related Work – Gestural

Use strokes as input parameters to CAD operations

Zeleznik et al. 1996 – Sketch

Igarishi et al 1999 – Teddy

Igarish & Hughes 2001 - Chateau

De Araujo & Jorge 2003 – Blobmaker

Karpenko et al 2002, 2006 - SmoothSketch

Alexe et al. 2004 – Spherical implicits

Tai et al 2004 – Convolution implicits

Related Work - Other

Shape From Shading

Atick et al. 1997

Image Based Modeling

Williams 1990

Kang 1998

Horry et al. 1997

Reconstructing Surfaces

Zhang et al 2002, 2003

Koenderink 1997

Perception

Koenderink et al 1984, 1996, 1998

Overview

1. Goals

2. Related work

3. Line labelling

4. Solver

5. Finding constraints with user guidance

6. Results

7. Future work

Line Labelling

Classifying each contour as corresponding to either a depth or orientation discontinuity

- A convex edge. Orientation (normal) discontinuity

- A concave edge. Orientation (normal) discontinuity

- An occluding convex edge. Depth discontinuity.

- A silhouette. Depth discontinuity.

Line Labelling

Uses the pattern of strokes to define some constraints on output surfaces.

Classification of legal connections between labels at junctions disallows certain labellings.

i.e. Identifies drawings of impossible geometries

A labelling that corresponds to a realizeable scene is known as a legal labelling.

Line Labelling – The Problems

NP complete solution – produces a combinatorial explosion of legal labellings

A legal labelling still yields infinite possible reconstructions.

Line Labelling – The Problems

The benefits only exist for drawings of polyhedral models!

Dense labelling problem – arc consistency

Split contours at critical points to reduce to sparse labelling

Line Labelling

Line labelling produces ambigous constraints

Each label tells us the type of discontinuity along the contour

But what does that tell us about the incident surfaces?

Incident Surface Constraints

Orientation discontinuity – Convex & Concave

Depth discontinurity – Silhouette

Line Labelling

So, use constraints on incident surfaces instead of constraints on contours.

Intuition – now we know what parameters to set to define the reconstructed surface!

Orientation discontinuity – each incident surface has a normal constraint

Depth discontinuity – attached surface has a normal constraint, detached surface has a depth constraint

Overview

1. Goals

2. Related work

3. Line labelling

4. Solver

5. Finding constraints with user guidance

6. Results

7. Future work

Solver

Zhang et al 2002

Place normal and depth constraints in a 2D field

Also place discontinuity constraints along contours

Our system places constraints along contours automatically

Solve a variational equation for a smooth output surface

Normal constraints - position and a vector

Depth constraints – position and a scalar depth value

Depth discontinuity

Normal discontinuity

Overview

1. Goals

2. Related work

3. Line labelling

4. Solver

5. Finding constraints with user guidance

6. Results

7. Future work

Finding Constraints with User Guidance

Which constraints to use?

Only the artist knows what their intent is

We co-opt the artists perceptive ability to determine the correct constraints

User never has to learn special system rules

The method :

Present the user with candidate reconstructions

User chooses “best fit” reconstruction

System determines 1) constraint type and 2) constraint parameter value

User Interface

'Good' – Labels (type) correct. Parameters correct.

'Bad' – Labels incorrect.

'Refine' – Generate more reconstructions like this one. Labels correct. Parameters wrong.

'Refine+' - Generate more reconstructions similar to this one. Implies a search of nearby parameter space

'Refine-' - Generate reconstructions far away (in parameter space) from this one.

Probable Constraint Generator

PCG – continually generates candidate reconstructions to test undefined constraints

Iteratively, produces tentative constraints for

A set of contours

A set of faces

An individual face

An individual line

Only test one set or item at a time

Create a history set that records what constraint configurations have been tried

Finding the Right Constraint

PCG first determines the constraint type for an incident surface

Then, it determines the constraint parameter

Depth – a scalar difference in depth between the surfaces at the contour, (0,infinity (or far clip plane) ]

Normal – since the normal is perpendicular to the contour, an angle in radians describes this completely, [0,2pi]

Search the domain by using new parameter values for the constraints

History set tells what part of the domain has already been searched

Constraint Tests - Inflation

Convex and/or concave inflation on all silhouettes

Normal constraint guaranteed at all silhouettes

Constraint Tests - Faces

Planarity assumed for faces bounded by straight lines

An interior face may also represent a hole

Constraint Tests - Single

Single line can be one of 3 options : A depth discontinuity (silhouette), occluding from either side or an orientation discontinuity (crease)

Constraint Tests – Junction Catalogue

Line labelling defines limitations on possible reconstructions using a junction catalogue

Many constraints automatically determined!

Does not always work! But still useful...

Minimize Interaction

Good initial parameter guesses!!

Test many simultaneously

Example : Heuristics for polyhedra

Interior regular angles converge to 0 or 180

degrees under projection

Average over parallel bundle

to get perspective correct

normal guess

Overview

1. Goals

2. Related work

3. Line labelling

4. Solver

5. Finding constraints with user guidance

6. Results

7. Future work

Two Point Perspective

Problem Corner

Dense labelling

Automatic splits at pseudo junctions

Pass 1

Pass 2

Results

All drawing in real time

Only limited by solver convergence average :1-5 sec, worst : 10 sec

But, gross differences quickly visible

Simple models – 1 minute total

Bear model – 4 minutes

Head model – 6 minutes, 3 minutes to recreate

Future

Two main areas for improvement – 1) generating better constraints, 2 ) creating better reconstructions.

Require less user interaction – better first guesses

Handle curvature discontinuities

Handle lines indicative of shading,texture,color

Beautification step

Hidden geometry

Thank you!

Matthew Kaplan

2005-08-11T02:39:11

Matt Kaplan