Computational Design ofReconfigurables!
Akash Garg1!
Alec Jacobson1,2!

1Columbia University!
2University of Toronto!

Eitan Grinspun1!
!

!
1!

reconfigurable | riːkən'fɪg(ə)rəb(ə)l |noun
an object or collection of objects whose transformation between
various states defines its functionality or aesthetic appeal.

2!

Foldable bicycle is a classic example
of a reconfigurable!

state #1

transition

state #23!

Transforming!
furniture is !
also a !
reconfigurable !

https://youtu.be/A3PDiDLiOEI

4!

Transforming!
furniture is !
also a !
reconfigurable !

https://youtu.be/A3PDiDLiOEI

5!

Space-saving kitchen is"also a reconfigurable

6!

7!

8!

9!

10!

Problems occur if we design !
each state in isolation…!

state #1

11!

...collisions prevent transitioning!
to other states!

state #212!

...collisions prevent transitioning!
to other states!

state #2

first contact
13!

We model reconfigurables !
as a graph of transitions!

1214!

We model reconfigurables !
as a graph of transitions!
54

12

315!

Our goal is to help the designerkeep all transitions collision free!

1216!

need UI to notify
designer of new collisions

need UI to trackprogress of collisions

need modeling tools
to resolve collisions

17!

Harmonization of all three enables!
to rapid and creative editing sessions!
need UI to notify
designer of new collisions

need UI to trackprogress of collisions

need modeling tools
to resolve collisions

18!

Traditional CAD tools have !
limited collision support!
offline detection
notification via “audible bell”
no automatic resolution
solidworks
19!

Animation tools detect and respond !
to collisions for physically-based effects!
time is linear and “one-way”
no salient states
overlaps OK if not noticeable

maya

20!

Previous computational design tools either:!

ignore collisions

leverage aspecialized subspace21!

We begin with objects as rigid triangle meshes!

22!

Along each transition an object is a
4D spacetime volume!

tyyxx
23!

Collisions correspond tointersections in spacetime!

tyyxx
24!

Collision Intervals form the foundation of !
our notification and tracking UIs!
spacetime bounding box

temporal projection

tyx

spatial projection25!

Collision Intervals form the foundation of !
our notification and tracking UIs!
temporal projection

spacetime bounding box

see paper about 4D k-DOP
for collision interval detection

spatial projection

26!

Spatial and temporal projections ofcollision intervals alert the designer!

27!

First priority: alert designer whencollision is occurring!

28!

Next: alert designer where !
collision is occurring !

29!

Designer’s current view may be poor,!
hotkey tumbles to optimized view!

30!

Designer’s current view may be poor,!
hotkey tumbles to optimized view!

31!

What makes a poor view?!

Collision interval
not central
32!

What makes a poor view?!

Collision interval
not central

Collision interval
occluded33!

What makes a poor view?!

Collision interval
not central

Collision interval
occludedView direction
along trajectory
34!

What makes a poor view?!

Collision interval
not central

Collision interval
occludedView direction
along trajectory
35!

For two objects, center collision interval
along view direction orthogonal to motions…!

36!

Generally, two choices left: !
pick direction with least occlusion!
rA ⇥ rB

rA ⇥ r B

partially occluded

not occluded

37!

For degenerate views or multiple objects,!
we search over all views via Monte Carlo!

38!

For degenerate views or multiple objects,!
we search over all views via Monte Carlo!

39!

For degenerate views or multiple objects,!
we search over all views via Monte Carlo!

count “red” pixels using hardware “occlusion queries” (GL_SAMPLES_PASSED)

40!

Picture-in-picture allows rapid editing!

41!

original

addarmrestbetter view

where!

when!

swap view

edit

again

swap vieworiginal

addarmrestbetter view

where!

when!

swap view

edit

when!

again

gone.

swap vieworiginal

addarmrestbetter view

where!

when!

swap view

edit

when!

again

gone.

swap vieworiginal

addarmrestbetter view

where!

when!

swap view

edit

when!

again

gone.

swap vieworiginal

addarmrestbetter view

where!

when!

swap view

edit

when!

again

gone.

swap vieworiginal

addarmrestbetter view

where!

when!

swap view

edit

when!

again

gone.

swap vieworiginal

addarmrestbetter view

where!

when!

swap view

edit

again

gone.

swap vieworiginal

addarmrestbetter view

where!

when!

swap view

edit

when!

again

swap vieworiginal

addarmrest
better view

where!

when!

swap view

edit

when!

again

gone.

swap view

Stroboscopic ghosting complements !
interactive collision interval tracking!

51!

Stroboscopic ghosting complements !
interactive collision interval tracking!

52!

Stroboscopic ghosting complements !
interactive collision interval tracking!

53!

Fixing collisions can be tedious and unintuitive,
how about a hint?!
decrease/remove collisions
agnostic to direction of timein terms of UI DOFs

54!

First contacts between objectsproduce unreliable, biased directions!

t=0

t=155!

First contacts between objects
produce unreliable, biased directions!

t=0

t=156!

First contacts between objects
produce unreliable, biased directions!

t=0

t=157!

Global solution should untangle
spacetime intersection!

t=0

t=158!

Global solution should untangle
spacetime intersection!

t=0

t=159!

Global solution should untangle
spacetime intersection!

t=0

t=160!

2D reconfigurables could be
untangled like 3D cloths!
A, B ⇢ R3yxtyx

61!

2D reconfigurables could be
untangled like 3D cloths!
@A, @B 2 S2D@A \ @B 2 C1Dtyx

2D reconfigurables could be
untangled like 3D cloths!
@A, @B 2 S2D@A \ @B 2 C1Dtyx@A \ @B ! ?
+A\B !?

Minimizing length of intersection
curve results in untangling!
IC intersection
contour64!

Minimizing length of intersection
curve results in untangling!
IC intersection
contourargmin kIC kV

length3D meshvertices

65!

Minimizing length of intersection
curve results in untangling!
IC intersection
contourargmin kIC kVlength3D meshvertices
update via gradient descentVV

rV kIC k66!

Minimizing length of intersection
curve results in untangling!
IC intersection
contourargmin kIC kVlength

3D meshvertices
update via gradient descentVV

rV kIC k[Volino & M-T 2006]67!

Naive extension to 3D objects is problematic!
A, B ⇢ R468!

Naive extension to 3D objects is problematic!
@A, @B 2 S3D@A \ @B 2 S2DDifficult to compute or
optimize over69!

Naive extension to 3D objects is problematic!

Difficult to compute oroptimize over
How to minimize surface
area of intersection?
argmin |IS |UI70!

Intersections of generic surfaces are!
non-trivial to parameterize…!

71!

Intersections of generic surfaces are!
non-trivial to parameterize…!
need to resolveintersections72!

… but spacetime surfaces are !
explicit functions of monotonic time!

73!

… but spacetime surfaces are !
explicit functions of monotonic time!
trivialparameterization74!

Spacetime intersection surface area reduces
to integral of 1D intersection contours!
argmin |IS |
UI

UI

UI

rUI |IS |75!

Spacetime intersection surface area reduces
to integral of 1D intersection contours!
argminUIUIZ 10UIkIC (t)k dt

Z 10rUI kIC (t)k dt76!

Applying the chain rule reveals !
UI couples surface positions across time!
argminUIUIZ 10UIkIC (t)k dt

Z 10

rUI kIC (t)k dt
apply chain rule77!

Applying the chain rule reveals !
UI couples surface positions across time!
argminUIUI

Z 10UIkIC (t)k dt

Z 10(rUI Vt ) (rVt kIC (t)k) dt78!

Applying the chain rule reveals !
UI couples surface positions across time!
argminUIUIZ 10UIkIC (t)k dt

Z 10(rUI Vt ) (rVt kIC (t)k) dt[Volino & M-T 2006]

79!

Applying the chain rule reveals !
UI couples surface positions across time!
argminUIUIZ 10UIkIC (t)k dt

Z 10(rUI Vt ) (rVt kIC (t)k) dt

See paper for details…
[Harmon et al. 2011][Umetani et al. 2011]80!

Gradient direction with respect to UI
immediately helps as hint!

81!

Gradient direction with respect to UI
immediately helps as hint!

82!

Gradient direction with respect to UI
immediately helps as hint!

83!

Collisions involving many objects can bevery tedious to fix…!

84!

Collisions involving many objects can bevery tedious to fix…!

85!

… manually fixing one collision may
cause more at another place or time!

86!

… manually fixing one collision may
cause more at another place or time!

87!

… instead we may follow gradient descent !
until all collisions disappear!

88!

… instead we may follow gradient descent !
until all collisions disappear!

89!

Sometimes, one part’s geometry isless important than another’s…!

90!

Sometimes, one part’s geometry isless important than another’s…!

91!

Sometimes, one part’s geometry isless important than another’s…!
See paper for details. Made possible in part by“Mesh Arrangements for Solid Geometry” [Zhou et al. 2016]
presented on Monday

92!

Swept volume carving invites !
creative space-saving solutions!

93!

Swept volume carving invites !
creative space-saving solutions!

94!

95!

96!

97!

98!

Limitations & Future Work!
modeling spaceextend to full modeling / deformation tools99!

Limitations & Future Work!
modeling spaceextend to full modeling / deformation tools

data

integrate with 3D scanning / model repos100!

Limitations & Future Work!
modeling spaceextend to full modeling / deformation tools

data

integrate with 3D scanning / model repos

physics

feasibility extends beyond collisions101!

Acknowledgements!
We thank Keenan Crane and Henrique Maia forilluminating discussions.
The Columbia Computer Graphics Group is supported
by Disney Research, Pixar, Adobe, and Altair.
Funded in part by NSF grants CMMI-11-29917,IIS-12-08153, IIS-14-09286, and IIS-17257.
102!

Computational Design ofReconfigurables!

!

!

Akash Garg!
Alec Jacobson jacobson@cs.toronto.edu!
Eitan Grinspun!