# Design and Analysis of Optimization Methods for Subdivision Surface Fitting

# Abstract

We present a complete framework for computing\\\\r\\\\na subdivision surface to approximate unorganized\\\\r\\\\npoint sample data, which is a separable nonlinear least\\\\r\\\\nsquares problem. We study the convergence and stability\\\\r\\\\nof three geometrically-motivated optimization schemes and\\\\r\\\\nreveal their intrinsic relations with standard methods\\\\r\\\\nfor constrained nonlinear optimization. A commonly-used\\\\r\\\\nmethod in graphics, called point distance minimization,\\\\r\\\\nis shown to use a variant of the gradient descent step\\\\r\\\\nand thus has only linear convergence. The second method,\\\\r\\\\ncalled tangent distance minimization, which is well-known\\\\r\\\\nin computer vision, is shown to use the Gauss-Newton step,\\\\r\\\\nand thus demonstrates near quadratic convergence for zero\\\\r\\\\nresidual problems but may not converge otherwise. Finally,\\\\r\\\\nwe show that an optimization scheme called squared\\\\r\\\\ndistance minimization, recently proposed by Pottmann et\\\\r\\\\nal., can be derived from the Newton method. Hence, with\\\\r\\\\nproper regularization, tangent distance minimization and\\\\r\\\\nsquared distance minimization are more efficient than\\\\r\\\\npoint distance minimization. We also investigate the effects\\\\r\\\\nof two step size control methods – Levenberg-Marquardt\\\\r\\\\nregularization and the Armijo rule – on the convergence\\\\r\\\\nstability and efficiency of the above optimization schemes

## Images and movies

## BibTex references

@Article {CWQWYL07, author = "Cheng, Kin-Shing D. and Wang, Wenping and Qin, Hong and Wong, Kwan-Yee K. and Yang, Huaiping and Liu, Yang", title = "Design and Analysis of Optimization Methods for Subdivision Surface Fitting", journal = "IEEE Transactions on Visualization and Computer Graphics", number = "5", volume = "13", pages = "878 -- 890 ", month = "sep", year = "2007", keywords = "subdivision surface, fitting, optimization,squared distance", url = "http://cvc.cs.stonybrook.edu/Publications/2007/CWQWYL07" }