Fast Planar Harmonic Deformations With Alternating Tangential . - People

Fast Planar Harmonic Deformations with Alternating Tangential Projections EDEN FEDIDA HEFETZ , EDWARD CHIEN, OFIR WEBER BAR-ILAN UNIVERSITY, ISRAEL 1

The Mapping Problem 𝑓: 𝛺 ℝ2 Desirable properties: Locally-injective Bounded conformal distortion Bounded isometric distortion Real-time 2

Previous Work Cage based methods (barycentric coords): Bounded distortion: [Hormann and Floater 2006] [Lipman 2012] [Joshi et al.2007] [Kovalsky at al. 2015] [Lipman et al. 2007] [Chen and Weber 2015] [Weber et al. 2011] [Levi and Weber 2016] [Weber et al. 2009] 3

Notations Planar mapping: 𝑓: Ω ℝ2 Jacobian: 𝑎 𝑏 𝑐 𝑑 𝐽𝑓 𝑏 𝑎 𝑑 𝑐 Similarity 𝑓𝑧 𝑐 𝑖𝑑 Singular values of 𝐽𝑓 Anti-similarity Complex Wirtinger derivatives: 𝑓𝑧 𝑎 𝑖𝑏 Distortion measures: 0 𝜎𝑏 𝜎𝑎 𝜎𝑎 𝑓𝑧 𝑓𝑧 𝜎𝑏 𝑓𝑧 𝑓𝑧 4

Bounded Distortion Harmonic Mappings The BD space: 𝑧 𝛺 𝜎𝑎 𝜎𝑏 𝜎𝑎 𝜎𝑏 𝑓𝑧 𝑓𝑧 conformal 𝑘 𝑧 𝐶𝑘 isometric 𝜎𝑎 z 𝑓𝑧 𝑓𝑧 𝐶𝑎 𝜎𝑏 z 𝑓𝑧 𝑓𝑧 𝐶𝑏 𝝉 𝐦𝐚𝐱 𝝈𝒂 , 𝟏 𝝈𝒃 Non-convex space Source Harmonic mapping 𝑪𝒂 𝟐. 𝟏𝟎𝟓 enforce bounds only on Ω [Chen and Weber 2015] 5

The ℒ𝜈 Space [Levi and Weber 2016] Change of variables: BD ℒ𝜈 𝒍 𝒍𝒐𝒈 𝒇𝒛 ℒ𝜈 BD 𝒇𝒛 𝒆𝒍 𝝂 𝒇𝒛 𝒇𝒛 𝒇𝒛 𝝂𝒆𝒍 BD homeomorphic to ℒ𝜈 6

The ℒ𝜈 Space Near convex space 𝑤 𝛺 𝑘 𝑤 𝜈(𝑤) 𝐶𝑘 𝜎𝑎 w 𝑒 𝑅𝑒(𝑙(𝑤)) (1 𝜈(𝑤) ) 𝐶𝑎 𝜎𝑏 w 𝑒 𝑅𝑒 𝑙 𝑤 (1 𝜈(𝑤) ) 𝐶𝑏 Convex 7

Discretization n vertices Enforce distortion constraints on m densely sampled points Use Cauchy complex barycentric coordinate : 𝑛 𝑙 𝑧 𝑛 𝑠𝑗 𝐶𝑗 𝑧 & 𝜈 𝑧 𝑗 1 𝑡𝑗 𝐶𝑗 𝑧 𝑠𝑗 , 𝑡𝑗 ℂ 𝑗 1 Subspace of holomorphic functions 4n-dimensional m sample points Affine 8

Our problem Convex Affine 4m-dimensional 4n-dimensional Bounded distortion convex subspace of ℝ4𝑚 Harmonic mapping 9

Our problem Input: 𝑙 and 𝜈 values from cage data Find the closest point in the intersection of an affine space and a convex space A 𝑎𝑖 B 10

Alternating Projections MAP ATP 𝐻𝑖 11

Alternating Projections MAP ATP [Von Neumann 1950] [Bauschke and Borwein 1993] Proof of convergence 12

Large-Scale Bounded Distortion Mappings [Kovalsky et al. 2015] Alternating Projections between an affine space and non-convex space No convergence guarantees Upon convergence, not necessarily locally injective Only bounds the conformal distortion and not isometric 13

Gathering Input Data Extract 𝑙 and 𝜈 values from cage data Linear transformations 𝑒𝑖 𝑒𝑖 that preserves the unit normal 𝒆𝒊 𝟏 𝒆𝒊 𝟏 𝒆𝒊 1 𝒆𝒊 1 1 2 𝒆𝒊 𝟏 𝒆𝒊 𝟏 14

Implementation Local: Project each sample point to the bounded distortion space GPU kernel Global: Linear fixed left hand side GPU - Matrix-Vector products using cuBLAS 15

Results 16

Near-optimality of alternating projection methods source MOSEK ATP MAP 0.005 fps 3 fps 35 fps 17

Near-optimality of alternating projection methods source MAP MOSEK 0.2 fps ATP 15 fps 140 fps 18

Speedup 𝟏𝟎𝟑 170 𝟑 𝟏𝟎𝟑 30 19

𝐶𝑎 5 𝐶𝑏 0.2 𝝉 𝝉 𝐦𝐚𝐱 𝝈𝒂 , 𝟏 𝝈𝒃 20

Source Cauchy Coords [Kovalsky et al. 2015] ATP 21

Summary Planar deformation GPU accelerated – speedup of 3 103 Guaranteed local injectivity and bounded distortion Homeomorphism of BD and ℒ𝜈 General proof of convergence Future Work: Positional constraints Extension to 3D / parametrization of surfaces 22

MAP ATP Near-optimality of alternating projection methods 17 MOSEK source 0.005 fps 3 fps 35 fps . Near-optimality of alternating projection methods 18 MOSEK source MAP ATP 0.2 fps 15 fps 140 fps . Speedup . 7/30/2017 10:06:02 AM .