Journal Home > Volume 4 , Issue 4
Computational Visual Media 2018, 4(4): 305-321 https://doi.org/10.1007/s41095-018-0127-7
Research Article | Open Access | Issue | Published: 23 December 2018

Deforming generalized cylinders without self-intersection by means of a parametric center curve

Show Author's Information Ruibin Ma1( ),  Qingyu Zhao1,  Rui Wang1,  James Damon2,  Julian Rosenman1,3,  Stephen Pizer1,3
Computer Science, University of North Carolina at Chapel Hill, Chapel Hill, NC 27705, United States.
Mathematics, University of North Carolina at Chapel Hill, Chapel Hill, NC 27705, United States.
Radiation Oncology, University of North Carolina at Chapel Hill, Chapel Hill, NC 27705, United States.
Keywords:
generalized cylinder, deformation, skeleton, self-intersection
Cite this article:
Ma R, Zhao Q, Wang R, et al. Deforming generalized cylinders without self-intersection by means of a parametric center curve. Computational Visual Media, 2018, 4(4): 305-321. https://doi.org/10.1007/s41095-018-0127-7
Download citation
EndNote(RIS)
BibTeX

612

Views

19

Downloads

Citations

2

Crossref

N/A

WoS

2

Scopus

0

CSCD

Abstract Full text About this article

Large-scale deformations of a tubular object, or generalized cylinder, are often defined by a target shape for its center curve, typically using a parametric target curve. This task is non-trivial for free-form deformations or direct manipulation methods because it is hard to manually control the centerline by adjusting control points. Most skeleton-based methods are no better, again due to the small number of manually adjusted control points. In this paper, we propose a method to deform a generalized cylinder based on its skeleton composed of a centerline and orthogonal cross sections. Although we are not the first to use such a skeleton, we propose a novel skeletonization method that tries to minimize the number of intersections between neighboring cross sections by means of a relative curvature condition to detect intersections. The mesh deformation is first defined geometrically by deforming the centerline and mapping the cross sections. Rotation minimizing frames are used during mapping to control twisting. Secondly, given displacements on the cross sections, the deformation is decomposed into finely subdivided regions. We limit distortion at these vertices by minimizing an elastic thin shell bending energy, in linear time. Our method can handle complicated generalized cylinders such as the human colon.


menu
Abstract
Full text
Outline
About this article

Deforming generalized cylinders without self-intersection by means of a parametric center curve

Show Author's information Ruibin Ma1( ), Qingyu Zhao1, Rui Wang1, James Damon2, Julian Rosenman1,3, Stephen Pizer1,3
Computer Science, University of North Carolina at Chapel Hill, Chapel Hill, NC 27705, United States.
Mathematics, University of North Carolina at Chapel Hill, Chapel Hill, NC 27705, United States.
Radiation Oncology, University of North Carolina at Chapel Hill, Chapel Hill, NC 27705, United States.

Abstract

Large-scale deformations of a tubular object, or generalized cylinder, are often defined by a target shape for its center curve, typically using a parametric target curve. This task is non-trivial for free-form deformations or direct manipulation methods because it is hard to manually control the centerline by adjusting control points. Most skeleton-based methods are no better, again due to the small number of manually adjusted control points. In this paper, we propose a method to deform a generalized cylinder based on its skeleton composed of a centerline and orthogonal cross sections. Although we are not the first to use such a skeleton, we propose a novel skeletonization method that tries to minimize the number of intersections between neighboring cross sections by means of a relative curvature condition to detect intersections. The mesh deformation is first defined geometrically by deforming the centerline and mapping the cross sections. Rotation minimizing frames are used during mapping to control twisting. Secondly, given displacements on the cross sections, the deformation is decomposed into finely subdivided regions. We limit distortion at these vertices by minimizing an elastic thin shell bending energy, in linear time. Our method can handle complicated generalized cylinders such as the human colon.

Keywords: generalized cylinder, deformation, skeleton, self-intersection

References(63)

[1]
M.-S. Kim,; E.-J. Park,; H.-Y. Lee, Modelling and animation of generalized cylinders with variable radius offset space curves. The Journal of Visualization and Computer Animation Vol. 5, 189-207, 1994.
DOI Google Scholar
[2]
D. H. Ballard,; C. M. Brown, Computer Vision. Prentice-Hall, Inc., 1982.
[3]
U. Shani,; D. H. Ballard, Splines as embeddings for generalized cylinders. Computer Vision, Graphics, and Image Processing Vol. 27, No. 2, 129-156, 1984.
DOI Google Scholar
[4]
T.-I. Chang,; J.-H. Lee,; M.-S. Kim,; S. J. Hong, Direct manipulation of generalized cylinders based on B-spline motion. The Visual Computer Vol. 14, Nos. 5-6, 228-239, 1998.
DOI Google Scholar
[5]
B. Jüttler,; M. G. Wagner, Computer-aided design with spatial rational B-spline motions. Journal of Mechanical Design Vol. 118, No. 2, 193-201, 1996.
DOI Google Scholar
[6]
T. O’Donnell,; T. E. Boult,; X.-S. Fang,; A. Gupta, The extruded generalized cylinder: A deformable model for object recovery. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 174-181, 1994.
DOI
[7]
T. W. Sederberg,; S. R. Parry, Free-form deformation of solid geometric models. ACM SIGGRAPH Computer Graphics Vol. 20, No. 4, 151-160, 1986.
DOI Google Scholar
[8]
W. M. Hsu,; J. F. Hughes,; H. Kaufman, Direct manipulation of free-form deformations. In: Proceedings of the 19th Annual Conference on Computer Graphics and Interactive Techniques, 177-184, 1992.
DOI
[9]
O. Sorkine,; D. Cohen-Or,; Y. Lipman,; M. Alexa,; C. Rössl,; H.-P. Seidel, Laplacian surface editing. In: Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, 175-184, 2004.
DOI
[10]
Y. Yu,; K. Zhou,; D. Xu,; X. Shi,; H. Bao,; B. Guo,; H.-Y. Shum, Mesh editing with Poisson-based gradient field manipulation. In: Proceedings of the ACM SIGGRAPH 2004 Papers, 644-651, 2004.
DOI
[11]
O. Sorkine, Laplacian mesh processing. In: Proceedings of the Eurographics 2005: State of the Art Reports, 53-70, 2005.
[12]
K. Zhou,; J. Huang,; J. Snyder,; X. Liu,; H. Bao,; B. Guo,; H.-Y. Shum, Large mesh deformation using the volumetric graph Laplacian. In: Proceedings of the ACM SIGGRAPH 2005 Papers, 496-503, 2005.
DOI
[13]
R. W. Sumner,; J. Popović, Deformation transfer for triangle meshes. In: Proceedings of the ACM SIGGRAPH 2004 Papers, 399-405, 2004.
DOI
[14]
O. Sorkine,; M. Alexa, As-rigid-as-possible surface modeling. In: Proceedings of the 5th Eurographics Symposium on Geometry Processing, 109-116, 2007.
[15]
W.-W. Xu,; K. Zhou, Gradient domain mesh deformation—A survey. Journal of Computer Science and Technology Vol. 24, No. 1, 6-18, 2009.
DOI Google Scholar
[16]
M. Botsch,; O. Sorkine, On linear variational surface deformation methods. IEEE Transactions on Visualization and Computer Graphics Vol. 14, No. 1, 213-230, 2008.
DOI Google Scholar
[17]
S. Zhang,; J. Huang,; D. N. Metaxas, Robust mesh editing using Laplacian coordinates. Graphical Models Vol. 73, No. 1, 10-19, 2011.
DOI Google Scholar
[18]
L. Kavan,; S. Collins,; J. Žára,; C. O’Sullivan, Skinning with dual quaternions. In: Proceedings of the Symposium on Interactive 3D Graphics and Games, 39-46, 2007.
[19]
L. Kavan,; O. Sorkine, Elasticity-inspired deformers for character articulation. ACM Transactions on Graphics Vol. 31, No. 6, Article No. 196, 2012.
DOI Google Scholar
[20]
D. Rohmer,; S. Hahmann,; M.-P. Cani, Local volume preservation for skinned characters. Computer Graphics Forum Vol. 27, No. 7, 1919-1927, 2008.
DOI Google Scholar
[21]
Y. Kho,; M. Garland, Sketching mesh deformations. In: Proceedings of the Symposium on Interactive 3D Graphics and Games, 147-154, 2005.
DOI
[22]
S. Yoshizawa,; A. G. Belyaev,; H.-P. Seidel, Skeleton-based variational mesh deformations. Computer Graphics Forum Vol. 26, No. 3, 255-264, 2007.
DOI Google Scholar
[23]
G. Aujay,; F. Hétroy,; F. Lazarus,; C. Depraz, Harmonic skeleton for realistic character animation. In: Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 151-160, 2007.
[24]
L. Antiga,; B. Ene-Iordache,; A. Remuzzi, Centerline computation and geometric analysis of branching tubular surfaces with application to blood vessel modeling. In: Proceedings of the 11th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision, 13-16, 2003.
[25]
W. Zeng,; J. Marino,; K. C. Gurijala,; X. Gu,; A. Kaufman, Supine and prone colon registration using quasi-conformal mapping. IEEE Transactions on Visualization and Computer Graphics Vol. 16, No. 6, 1348-1357, 2010.
DOI Google Scholar
[26]
Y. Zhou,; K. Yin,; H. Huang,; H. Zhang,; M. Gong,; D. Cohen-Or, Generalized cylinder decomposition. ACM Transactions on Graphics Vol. 34, No. 6, Article No. 171, 2015.
DOI Google Scholar
[27]
J. Damon, Swept regions and surfaces: Modeling and volumetric properties. Theoretical Computer Science Vol. 392, Nos. 1-3, 66-91, 2008.
DOI Google Scholar
[28]
W. Wang,; B. Jüttler,; D. Zheng,; Y. Liu, Computation of rotation minimizing frames. ACM Transactions on Graphics Vol. 27, No. 1, Article No. 2, 2008.
DOI Google Scholar
[29]
M. Bergou,; M. Wardetzky,; D. Harmon,; D. Zorin,; E. Grinspun, A quadratic bending model for inextensible surfaces. In: Proceedings of the Eurographics Symposium on Geometry Processing, 227-230, 2006.
[30]
Q. Zhao,; T. Price,; S. Pizer,; M. Niethammer,; R. Alterovitz,; J. Rosenman, Surface registration in the presence of missing patches and topology change. In: Proceedings of the Medical Image Understanding and Analysis Conference, 2015.
[31]
R. Ma,; Q. Zhao,; R. Wang,; J. Damon,; J. Rosenman,; S. Pizer, Skeleton-based generalized cylinder deformation under the relative curvature condition. In: Proceedings of the Pacific Graphics, 2018.
[32]
S. Yoshizawa,; A. G. Belyaev,; H.-P. Seidel, Free-form skeleton-driven mesh deformations. In: Proceedings of the 8th ACM Symposium on Solid Modeling and Applications, 247-253, 2003.
DOI
[33]
X. Shi,; K. Zhou,; Y. Tong,; M. Desbrun,; H. Bao,; B. Guo, Mesh puppetry: Cascading optimization of mesh deformation with inverse kinematics. In: Proceedings of the ACM SIGGRAPH 2007 Papers, Article No. 81, 2007.
DOI
[34]
J. P. Lewis,; M. Cordner,; N. Fong, Pose space deformation: A unified approach to shape interpolation and skeleton-driven deformation. In: Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques, 165-172, 2000.
DOI
[35]
O. Weber,; O. Sorkine,; Y. Lipman,; C. Gotsman, Context-aware skeletal shape deformation. Computer Graphics Forum Vol. 26, No. 3, 265-273, 2007.
DOI Google Scholar
[36]
Z. Wei,; J. Rossignac, Fleshing: Spine-driven bending with local volume preservation. Computer Graphics Forum Vol. 32, No. 2pt3, 295-304, 2013.
DOI Google Scholar
[37]
A. Angelidis,; K. Singh, Kinodynamic skinning using volume-preserving deformations. In: Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 129-140, 2007.
[38]
R. Vaillant,; L. Barthe,; G. Guennebaud,; M.-P. Cani,; D. Rohmer,; B. Wyvill,; O. Gourmel,; M. Paulin, Implicit skinning: Real-time skin deformation with contact modeling. ACM Transactions on Graphics Vol. 32, No. 4, Article No. 125, 2013.
DOI Google Scholar
[39]
A. Verroust,; F. Lazarus, Extracting skeletal curves from 3D scattered data. The Visual Computer Vol. 16, No. 1, 15-25, 2000.
DOI Google Scholar
[40]
M. Mortara,; G. Patanè, Shape-covering for skeleton extraction. International Journal of Shape Modeling Vol. 8, No. 2, 139-158, 2002.
DOI Google Scholar
[41]
J.-H. Chuang,; C.-H. Tsai,; M.-C. Ko, Skeletonisation of three-dimensional object using generalized potential field. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 22, No. 11, 1241-1251, 2000.
DOI Google Scholar
[42]
L. Antiga,; B. Ene-Iordache,; A. Remuzzi, Computational geometry for patient-specific reconstruction and meshing of blood vessels from MR and CT angiography. IEEE Transactions on Medical Imaging Vol. 22, No. 5, 674-684, 2003.
DOI Google Scholar
[43]
L. Antiga,; M. Piccinelli,; L. Botti,; B. Ene-Irodache,; A. Remuzzi,; D. Steinman, An image-based modeling framework for patient-specific computational hemodynamics. Medical & Biological Engineering & Computing Vol. 46, 1097-1112, 2008.
DOI Google Scholar
[44]
G. Wang,; E. G. McFarland,; B. P. Brown,; Z. Zhang,; M. Vannier, Curved cross-section based system and method for gastrointestinal tract unraveling. U.S. Patent 6,212,420. 2001.
[45]
J. Damon, Lorentzian geodesic flows and interpolation between hypersurfaces in Euclidean spaces. Preliminary preprint in MIDAG paper collection. 2018.
[46]
W. Hong,; X. Gu,; F. Qiu,; M. Jin,; A. Kaufman, Conformal virtual colon flattening. In: Proceedings of the ACM Symposium on Solid and Physical Modeling, 85-93, 2006.
DOI
[47]
S. Halier,; S. Angenent,; A. Tannenbaum,; R. Kikinis, Nondistorting flattening maps and the 3-D visualization of colon CT images. IEEE Transactions on Medical Imaging Vol. 19, No. 7, 665-670, 2000.
DOI Google Scholar
[48]
J. Peng,; D. Kristjansson,; D. Zorin, Interactive modeling of topologically complex geometric detail. In: Proceedings of the ACM SIGGRAPH 2004 Papers, 635-643, 2004.
DOI
[49]
Y. Gingold,; A. Secord,; J. Y. Han,; E. Grinspun,; D. Zorin, A discrete model for inelastic deformation of thin shells. Technical Report. Courant Institute of Mathematical Sciences, 2004.
[50]
E. Grinspun, A discrete model of thin shells. In: Proceedings of the ACM SIGGRAPH 2005 Courses, Article No. 4, 2005.
DOI
[51]
M. Meyer,; M. Desbrun,; P. Schröder,; A. H. Barr, Discrete differential-geometry operators for triangulated 2-manifolds. In: Visualization and Mathematics III. Mathematics and Visualization. H. C. Hege,; K. Polthier, Eds. Springer Berlin Heidelberg, 35-57, 2003.
DOI
[52]
M. Wardetzky,; S. Mathur,; F. Kälberer,; E. Grinspun, Discrete Laplace operators: No free lunch. In: Proceedings of the 5th Eurographics Symposium on Geometry Processing, 33-37, 2007.
DOI
[53]
S. Nadeem,; J. Marino,; X. Gu,; A. Kaufman, Corresponding supine and prone colon visualization using eigenfunction analysis and fold modeling. IEEE Transactions on Visualization and Computer Graphics Vol. 23, No. 1, 751-760, 2017.
DOI Google Scholar
[54]
S. Nadeem,; X. D. Gu,; A. E. Kaufman, LMap: Shape-preserving local mappings for biomedical visualization. IEEE Transactions on Visualization and Computer Graphics Vol. 24, No. 12, 3111-3122, 2018.
DOI Google Scholar
[55]
H. Wang,; L. Li,; H. Han,; R. Shi,; B. Song,; H. Peng,; Y. Liu,; X. Gu,; Y. Wang,; Z. Liang, A 2.5D colon wall flattening model for CT-based virtual colonoscopy. In: Machine Learning in Medical Imaging. Lecture Notes in Computer Science, Vol, 8184. G. Wu,; D. Zhang,; D. Shen,; P. Yan,; K. Suzuki,; F. Wang, Eds. Springer Cham, 203-210, 2013.
DOI
[56]
J. Marino,; W. Zeng,; X. Gu,; A. Kaufman, Context preserving maps of tubular structures. IEEE Transactions on Visualization and Computer Graphics Vol. 17, No. 12, 1997-2004, 2011.
DOI Google Scholar
[57]
J. Marino,; A. Kaufman, Planar visualization of treelike structures. IEEE Transactions on Visualization and Computer Graphics Vol. 22, No. 1, 906-915, 2016.
DOI Google Scholar
[58]
X. Xu,; J. M. Reinhardt,; Q. Hu,; B. Bakall,; P. S. Tlucek,; G. Bertelsen,; M. D. Abràmoff, Retinal vessel width measurement at branchings using an improved electric field theory-based graph approach. PLoS ONE Vol. 7, No. 11, e49668, 2012.
DOI Google Scholar
[59]
M. Mortara,; G. Patané,; M. Spagnuolo,; B. Falcidieno,; J. Rossignac, Blowing bubbles for multi-scale analysis and decomposition of triangle meshes. Algorithmica Vol. 38, No. 1, 227-248, 2004.
DOI Google Scholar
[60]
M. Mortara,; G. Patané,; M. Spagnuolo,; B. Falcidieno,; J. Rossignac, Plumber: A method for a multi-scale decomposition of 3D shapes into tubular primitives and bodies. In: Proceedings of the 9th ACM Symposium on Solid Modeling and Applications, 339-344, 2004.
[61]
L. M. Sangalli,; P. Secchi,; S. Vantini,; A. Veneziani, Efficient estimation of three-dimensional curves and their derivatives by free-knot regression splines, applied to the analysis of inner carotid artery centrelines. Journal of the Royal Statistical Society: Series C (Applied Statistics) Vol. 58, No. 3, 285-306, 2009.
DOI Google Scholar
[62]
K. Wampler, Fast and reliable example-based mesh IK for stylized deformations. ACM Transactions on Graphics Vol. 35, No. 6, Article No. 235, 2016.
DOI Google Scholar
[63]
L. Gao,; Y.-K. Lai,; D. Liang,; S.-Y. Chen,; S. Xia, Efficient and flexible deformation representation for data-driven surface modeling. ACM Transactions on Graphics Vol. 35, No. 5, Article No. 158, 2016.
DOI Google Scholar
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Revised: 31 October 2018
Accepted: 20 November 2018
Published: 23 December 2018
Issue date: December 2018

Copyright

© The Author(s) 2018

Acknowledgements

We gratefully thank Dr. Saad Nadeem and Dr. Arie Kaufman from Stony Brook University and Dr. Sarah McGill from UNC Medical School for sharing their results, data, and suggestions. This work was supported by National Institutes of Health grant R01 CA158925.

Rights and permissions

This article is published with open access at Springerlink.com

The articles published in this journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Other papers from this open access journal are available free of charge from http://www.springer.com/journal/41095. To submit a manuscript, please go to https://www.editorialmanager.com/cvmj.

Return