b-morphs between b-compatible curves in the plane

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

b-morphs between b-compatible curves in the plane

Full text

Pdf (15.26 MB)

Source

ACM Symposium on Solid and Physical Modeling archive
2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling table of contents

San Francisco, California

SESSION: Curves and surfaces II table of contents

Pages 187-198

Year of Publication: 2009

ISBN:978-1-60558-711-0

Authors

Brian Whited	Georgia Institute of Technology
Jarek Rossignac	Georgia Institute of Technology

Sponsor

: SIAM Activity Group on Geometric Design

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 17, Citation Count: 0

Additional Information:

abstract references index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1629255.1629279 What is a DOI?

ABSTRACT

We define b-compatibility for planar curves and propose three ball morphing techniques (b-morphs) between pairs of b-compatible curves. B-morphs use the automatic ball-map correspondence, proposed by Chazal et al. [12], from which they derive vertex trajectories (Linear, Circular, Parabolic). All are symmetric, meeting both curves with the same angle, which is a right angle for the Circular and Parabolic. We provide simple constructions for these b-morphs using the maximal disks in the finite region bounded by the two curves. We compare the b-morphs to each other and to other simple morphs (Linear Interpolation (LI), Closest Projection (CP), Curvature Interpolation (CI), Laplace Blending (LB), Heat Propagation (HP)) using seven measures of quality deficiency (travel distance, distortion, stretch, local acceleration, surface area, average curvature, maximal curvature). We conclude that the ratios of these measures depends heavily on the test case, especially for LI, CI, and LB, which compute correspondence from a uniform geodesic parameterization. Nevertheless, we found that the Linear b-morph has consistently the shortest travel distance and that the Circular b-morph has the least amount of distortion.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	S. Akkouche and E. Galin. Implicit surface reconstruction from contours. Vis. Comput., 20(6):392--401, 2004.
	2	M. Alexa. Differential coordinates for local mesh morphing and deformation. The Visual Computer, 19:105--114, 2003.
	3	M. Alexa, D. Cohen-Or, and D. Levin. As-rigid-as-possible shape interpolation. In SIGGRAPH '00: Proceedings of the 27th annual conference on Computer graphics and interactive techniques, pages 157--164, New York, NY, USA, 2000. ACM Press/Addison-Wesley Publishing Co.
	4	H. Alt, C. Knauer, and C. Wenk. Bounding the fréchet distance by the hausdorff distance. In Proc. 17th European Workshop on Computational Geometry, pages 166--169, 2001.
	5	B. Aronov, R. Seidel, and D. Souvaine. On compatible triangulations of simple polygons. Comput. Geom. Theory Appl., 3(1):27--35, 1993.
	6	H. Asada and M. Brady. The curvature primal sketch. IEEE Trans. Pattern Anal. Mach. Intell., 8(1):2--14, 1986.
	7	G. Barequet and M. Sharir. Piecewise-linear interpolation between polygonal slices. Comput. Vis. Image Underst., 63(2):251--272, 1996.
	8	G. Barequet and A. Vaxman. Nonlinear interpolation between slices. In SPM '07: Proceedings of the 2007 ACM symposium on Solid and physical modeling, pages 97--107, New York, NY, USA, 2007. ACM.
	9	A. H. Barr. Global and local deformations of solid primitives. In SIGGRAPH '84: Proceedings of the 11th annual conference on Computer graphics and interactive techniques, pages 21--30, New York, NY, USA, 1984. ACM.
	10	T. Beier and S. Neely. Feature-based image metamorphosis. SIGGRAPH Computer Graphics, 26(2):35--42, 1992.
	11	E. Catmull. The problems of computer-assisted animation. SIGGRAPH Comput. Graph., 12(3):348--353, 1978.
	12	F. Chazal, A. Lieutier, J. Rossignac, and B. Whited. Ball-map: Homeomorphism between compatible surfaces. International Journal of Computational Geometry and Applications, 2009 (to appear).
	13	F. Chazel, A. Lieutier, and J. Rossignac. Orthomap: Homeomorphism-guaranteeing normal-projection map between surfaces. Technical Report GIT-GVU-04-28, Georgia Institute of Technology, Graphics, Visibility, and Usability Center, 2004.
	14	W. Che, X. Yang, and G. Wang. Skeleton-driven 2d distance field metamorphosis using intrinsic shape parameters. Graphical Models, 66(2):102--126, 2004.
	15	S. E. Chen and R. E. Parent. Shape averaging and it's applications to industrial design. IEEE Comput. Graph. Appl., 9(1):47--54, 1989.
	16	X. Chen, M. R. Varley, L.-K. Shark, G. S. Shentall, and M. C. Kirby. An extension of iterative closest point algorithm for 3d-2d registration for pre-treatment validation in radiotherapy. In MEDIVIS '06: Proceedings of the International Conference on Medical Information Visualisation--BioMedical Visualisation, pages 3--8, Washington, DC, USA, 2006. IEEE Computer Society.
	17	S.-W. Cheng and T. K. Dey. Improved constructions of delaunay based contour surfaces. In SMA '99: Proceedings of the fifth ACM symposium on Solid modeling and applications, pages 322--323, New York, NY, USA, 1999. ACM.
	18	D. Cohen-Or, A. Solomovic, and D. Levin. Three-dimensional distance field metamorphosis. ACM Trans. Graph., 17(2):116--141, 1998.
	19	G. Cong and B. Parvin. A new regularized approach for contour morphing. In Computer Vision and Pattern Recognition, 2000. Proceedings. IEEE Conference on, volume 1, pages 458--463 vol. 1, 2000.
	20	M. Cui, J. Femiani, J. Hu, P. Wonka, and A. Razdan. Curve matching for open 2d curves. Pattern Recogn. Lett., 30(1):1--10, 2009.
	21	A. Efrat, S. Har-Peled, L. J. Guibas, and T. M. Murali. Morphing between polylines. In SODA '01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, pages 680--689, Philadelphia, PA, USA, 2001. Society for Industrial and Applied Mathematics.
	22	E. Ezra, M. Sharir, and A. Efrat. On the icp algorithm. In SCG '06: Proceedings of the twenty-second annual symposium on Computational geometry, pages 95--104, New York, NY, USA, 2006. ACM.
	23	H. Federer. Geometric Measure Theory. Springer Verlag, 1969.
	24	M. Foskey, M. Lin, and D. Manocha. Efficient computation of a simplified medial axis. In ACM Symposium on Solid Modeling and Applications, pages 96--107, 2003.
	25	H. Fu, C.-L. Tai, and O. K. Au. Morphing with laplacian coordinates and spatial temporal texture. In Proc. Pacific Graphics '05, pages 100--102, 2005.
	26	H. Fuchs, Z. M. Kedem, and S. P. Uselton. Optimal surface reconstruction from planar contours. Commun. ACM, 20(10):693--702, 1977.
	27	N. C. Gabrielides, A. I. Ginnis, P. D. Kaklis, and M. I. Karavelas. G1-smooth branching surface construction from cross sections. Comput. Aided Des., 39(8):639--651, 2007.
	28	N. Gelfand, N. J. Mitra, L. J. Guibas, and H. Pottmann. Robust global registration. In SGP '05: Proceedings of the third Eurographics symposium on Geometry processing, page 197, Aire-la-Ville, Switzerland, Switzerland, 2005. Eurographics Association.
	29	J. Gomes, L. Darsa, B. Costa, and L. Velho. Warping and morphing of graphical objects. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1998.
	30	H. Guo, X. Fu, F. Chen, H. Yang, Y. Wang, and H. Li. As-rigid-as-possible shape deformation and interpolation. J. Vis. Comun. Image Represent., 19(4):245--255, 2008.
	31	M. Guthe, P. Borodin, and R. Klein. Fast and accurate hausdorff distance calculation between meshes. Journal of WSCG, 13(2):41--48, February 2005.
	32	R. Klein, A. Schilling, and W. Straßer. Reconstruction and simplification of surfaces from contours. In PG '99: Proceedings of the 7th Pacific Conference on Computer Graphics and Applications, page 198, Washington, DC, USA, 1999. IEEE Computer Society.
	33	A. Kort. Computer aided inbetweening. In NPAR '02: Proceedings of the 2nd international symposium on Non-photorealistic animation and rendering, pages 125--132, New York, NY, USA, 2002. ACM.
	34	M. Leyton. Symmetry, Causality, Mind. MIT Press, 1992.
	35	M. Meyer, M. Desbrun, P. Schröder, and A. H. Barr. Discrete differential-geometry operators for triangulated 2-manifolds. Technical report, CalTech.
	36	F. Mokhtarian, S. Abbasi, and J. Kittler. Efficient and robust retrieval by shape content through curvature scale space. In Proc. International Workshop IDB-MMSÕ96, pages 35--42, 1996.
	37	G. Mori, S. Belongie, and J. Malik. Efficient shape matching using shape contexts. IEEE Trans. Pattern Anal. Mach. Intell., 27(11):1832--1837, 2005.
	38	W. T. Reeves. Inbetweening for computer animation utilizing moving point constraints. SIGGRAPH Comput. Graph., 15(3):263--269, 1981.
	39	J. Rossignac and A. Kaul. Agrels and bips: Metamorphosis as a bézier curve in the space of polyhedra. Comput. Graph. Forum, 13(3):179--184, 1994.
	40	J. Rossignac and A. A. G. Requicha. Piecewise-circular curves for geometric modeling. IBM J. Res. Dev., 31(3):296--313, 1987.
	41	J. R. Rossignac and A. A. Requicha. Offsetting Operations in Solid Modelling. Computer Aided Geometric Design, 3:129--148, 1986.
	42	J. Schreiner, A. Asirvatham, E. Praun, and H. Hoppe. Inter-surface mapping. In SIGGRAPH '04: ACM SIGGRAPH 2004 Papers, pages 870--877, New York, NY, USA, 2004. ACM.
	43	T. W. Sederberg, P. Gao, G. Wang, and H. Mu. 2--d shape blending: an intrinsic solution to the vertex path problem. In SIGGRAPH '93: Proceedings of the 20th annual conference on Computer graphics and interactive techniques, pages 15--18, New York, NY, USA, 1993. ACM.
	44	T. W. Sederberg and E. Greenwood. A physically based approach to 2-d shape blending. In SIGGRAPH '92: Proceedings of the 19th annual conference on Computer graphics and interactive techniques, pages 25--34, New York, NY, USA, 1992. ACM.
	45	M. Shapira and A. Rappoport. Shape blending using the star-skeleton representation. IEEE Comput. Graph. Appl., 15(2):44--50, 1995.
	46	K. Siddiqi and S. Pizer. Medial Representations: Mathematics, Algorithms and Applications. Springer, 2008. 450pp. In Press.
	47	R. W. Sumner, M. Zwicker, C. Gotsman, and J. Popović. Mesh-based inverse kinematics. In SIGGRAPH '05: ACM SIGGRAPH 2005 Papers, pages 488--495, New York, NY, USA, 2005. ACM.
	48	F. Thomas and O. Johnston. The Illusion of Life: Disney Animation. Disney Editions, revised edition, 1995.
	49	R. Tilove. Set membership classification: A unified approach to geometric intersection problems. Computers, IEEE Transactions on, C-29(10):874--883, Oct. 1980.
	50	A. Vinacua and J. Rossignac. Sam: Steady affine morph. Submitted for review., 2009.
	51	S. Wang, Y. Wang, M. Jin, X. Gu, and D. Samaras. 3d surface matching and recognition using conformal geometry. In CVPR '06: Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 2453--2460, Washington, DC, USA, 2006. IEEE Computer Society.
	52	Y. Weng, W. Xu, Y. Wu, K. Zhou, and B. Guo. 2d shape deformation using nonlinear least squares optimization. Vis. Comput., 22(9):653--660, 2006.
	53	J. Williams and J. Rossignac. Tightening: curvature-limiting morphological simplification. In ACM Symposium on Solid and Physical Modeling, pages 107--112, 2005.
	54	D. Xu, H. Zhang, Q. Wang, and H. Bao. Poisson shape interpolation. In SPM '05: Proceedings of the 2005 ACM symposium on Solid and physical modeling, pages 267--274, New York, NY, USA, 2005. ACM.
	55	Y. Yang, O. Brock, and R. N. Moll. Efficient and robust computation of an approximated medial axis. In SM '04: Proceedings of the ninth ACM symposium on Solid modeling and applications, pages 15--24, Aire-la-Ville, Switzerland, Switzerland, 2004. Eurographics Association.