Report

AS-RIGID-AS-POSSIBLE SHAPE MANIPULATION TAKEO IGARASHI TOMER MOSCOVICH JOHN F. HUGHES THE UNIVERSITY OF TOKYO BROWN UNIVERSITY BROWN UNIVERSITY INTRODUCTION INTRODUCTION RELATED WORK OVERVIEW ALGORITHM EXTENSIONS RESULTS FUTURE WORK We present a two-step closed-form algorithm that achieves real-time interaction. The first step finds an appropriate rotation for each triangle. The second step adjusts its scale. Each step uses a quadratic error metric so that the minimization problem is formulate as a set of simultaneous linear equations. RELATED WORK INTRODUCTION SHAPE MANIPULATION TECHNIQUES FALL ROUGHLY INTO TWO CATEGORIES: RELATED WORK OVERVIEW ALGORITHM EXTENSIONS Deform the space in which the target shape is embedded. [Lewis et al. 2000]--using predefined skeleton. [McCracken and Joy 1996]--each point is associated with a closed region in a FFD grid. RESULTS FUTURE WORK Deform the shape while taking its structure into account. [Gibson and Mirtich1997]--mass-spring models. OVERVIEW INTRODUCTION RELATED WORK OVERVIEW ALGORITHM EXTENSIONS RESULTS FUTURE WORK a)Triangulation and registration(pre-computed) Input a 2D model Silhouette : marching squares algorithm Triangulation : Delaunay triangulation Registration : accelerate the computation during interaction OVERVIEW INTRODUCTION RELATED WORK b)Compilation(pre-computed) User clicks on the shape to place handles. So far, user can only place handles at existing mesh vertices. OVERVIEW ALGORITHM EXTENSIONS RESULTS FUTURE WORK c)Manipulation User drags the handles to make a deformation of the shape. Also support multiple-point input devices. During interaction, update the handle configuration to solve the quadratic error functions. ALGORITHM INTRODUCTION RELATED WORK OVERVIEW ALGORITHM EXTENSIONS RESULTS FUTURE WORK Overview of the algorithm ALGORITHM INTRODUCTION Step 1 : scale-free construction(allow rotation and uniform scaling) RELATED WORK OVERVIEW ALGORITHM EXTENSIONS RESULTS FUTURE WORK v2 v0 x01 v0v1 y01R90 v0v1 v2 desired 0 1 R90 1 0 v0 ' x 01 v0 ' v1 ' y01 R90 v0 ' v1 ' ALGORITHM INTRODUCTION RELATED WORK OVERVIEW ALGORITHM Step 1 : scale-free construction(allow rotation and uniform scaling) The error between v2desired and v2’ is then represented as E{v2 } v2 desired v2 ' 2 EXTENSIONS We can define v0desired and v1desired similarly, so the error RESULTS associated with the triangle is FUTURE WORK E{v0 ,v1 ,v2 } i 1, 2 , 3 vi desired vi ' 2 ALGORITHM INTRODUCTION RELATED WORK OVERVIEW Step 1 : scale-free construction(allow rotation and uniform scaling) The error for the entire mesh is simply the sum of errors for all triangles in the mesh. We can express it in matrix form: ALGORITHM EXTENSIONS RESULTS FUTURE WORK T E1{v '} u G00 v' Gv' q G10 T G01 u G11 q The minimization problem is solved by setting the partial Derivatives of the function E1{v’} with respect to the free variables u in v’ to zero. E1 T T (G00 G00 )u (G01 G10 ) q 0 u ALGORITHM INTRODUCTION RELATED WORK OVERVIEW ALGORITHM Step 1 : scale-free construction(allow rotation and uniform scaling) Rewrite as G' u Bq 0 EXTENSIONS G’ and B are fixed and only q changes during manipulation. RESULTS Therefore, we can obtain u by simple matrix multiplication by FUTURE WORK pre-computing G’-1B at the beginning. ALGORITHM INTRODUCTION RELATED WORK Step 2 : scale adjustment Fitting the original triangle to the intermediate triangle OVERVIEW ALGORITHM EXTENSIONS RESULTS FUTURE WORK v2 fitted v0 fitted x 01 v0 fitted v1 fitted y01 R90 v0 fitted v1 fitted ALGORITHM INTRODUCTION RELATED WORK OVERVIEW Step 2 : scale adjustment Fitting the original triangle to the intermediate triangle Given a triangle{v0’,v1’,v2’}in the intermediate result and ALGORITHM corresponding triangle in the rest shape{v0,v1,v2},the first EXTENSIONS problem is to find a new triangle{v0fitted,v1fitted,v2fitted}that is RESULTS congruent to{v0,v1,v2}and minimizes the following function. FUTURE WORK E f {v fitted 0 , v1 fitted ,v2 fitted } i 1, 2 , 3 vi fitted vi ' 2 ALGORITHM INTRODUCTION RELATED WORK OVERVIEW Step 2 : scale adjustment Fitting the original triangle to the intermediate triangle We minimize Ef by setting the partial derivatives of Ef to zero. ALGORITHM EXTENSIONS RESULTS FUTURE WORK E f w Fw C 0 By solving this equation, we obtain a newly fitted triangle {v0fitted,v1fitted, v2fitted} that is similar to the original triangle {v0, v1, v2}. We make it congruent simply by scaling the fitted triangle by the factor of v0 fitted v1 fitted / v0 v1 ALGORITHM INTRODUCTION RELATED WORK Step 2 : scale adjustment Generating the final result using the fitted triangles OVERVIEW ALGORITHM EXTENSIONS RESULTS FUTURE WORK We can define the quadratic error function by E2{v0 '',v1 '',v2 ''} ( i , j ){( 0,1),(1, 2 ),( 2, 0 )} vi ' ' v j ' ' vi 2 fitted vj fitted ALGORITHM INTRODUCTION RELATED WORK Step 2 : scale adjustment Generating the final result using the fitted triangles The error for the entire mesh can be represented as : OVERVIEW ALGORITHM EXTENSIONS RESULTS FUTURE WORK u E2{v ''} v' ' Hv' ' fv' 'c q T T H 00 H 10 H 01 u u ( f 0 f1 ) c H11 q q We minimize E2 by setting the partial derivatives of E2 to zero. E2 T T ( H 00 H 00 )u ( H 01 H10 )q f 0 0 u Rewrite as H ' u Dq f 0 0 ALGORITHM INTRODUCTION RELATED WORK OVERVIEW ALGORITHM EXTENSIONS RESULTS FUTURE WORK Algorithm summary EXTENSIONS INTRODUCTION RELATED WORK OVERVIEW ALGORITHM EXTENSIONS RESULTS FUTURE WORK Collision detection and depth adjustment EXTENSIONS INTRODUCTION RELATED WORK OVERVIEW ALGORITHM EXTENSIONS RESULTS FUTURE WORK Weights for controlling rigidity EXTENSIONS INTRODUCTION RELATED WORK OVERVIEW ALGORITHM EXTENSIONS RESULTS FUTURE WORK Animations EXTENSIONS INTRODUCTION RELATED WORK OVERVIEW ALGORITHM EXTENSIONS RESULTS FUTURE WORK As-rigid-as-possible curve editing EXTENSIONS INTRODUCTION RELATED WORK OVERVIEW ALGORITHM EXTENSIONS RESULTS FUTURE WORK As-rigid-as-possible curve editing RESULTS INTRODUCTION RELATED WORK OVERVIEW ALGORITHM EXTENSIONS RESULTS FUTURE WORK FUTURE WORK INTRODUCTION Determine the depth order of the overlapping regions. RELATED WORK OVERVIEW ALGORITHM Extend the technique to 3D shapes. Allow users to put handles at arbitrary locations. Volume preservation. EXTENSIONS RESULTS FUTURE WORK