Andrea Tagliasacchi
Skip Abstract Section
Skip Supplemental Material SectionAbstract
We present an algorithm for curve skeleton extraction from imperfect point clouds where large portions of the data may be missing. Our construction is primarily based on a novel notion of generalized rotational symmetry axis (ROSA) of an oriented point set. Specifically, given a subset S of oriented points, we introduce a variational definition for an oriented point that is most rotationally symmetric with respect to S. Our formulation effectively utilizes normal information to compensate for the missing data and leads to robust curve skeleton computation over regions of a shape that are generally cylindrical. We present an iterative algorithm via planar cuts to compute the ROSA of a point cloud. This is complemented by special handling of non-cylindrical joint regions to obtain a centered, topologically clean, and complete 1D skeleton. We demonstrate that quality curve skeletons can be extracted from a variety of shapes captured by incomplete point clouds. Finally, we show how our algorithm assists in shape completion under these challenges by developing a skeleton-driven point cloud completion scheme.
Supplemental Material
Available for Download
zip
71-353.zip (18 MB)
Supplemental material
- Amenta, N., and Kil, Y. J. 2004. Defining point-set surfaces. ACM Trans. on Graph. 23, 3, 264--270. Google Scholar
Digital Library
- Au, O. K.-C., Tai, C.-L., Chu, H.-K., Cohen-Or, D., and Lee, T.-Y. 2008. Skeleton extraction by mesh contraction. ACM Trans. on Graph. 27, 3, 44:1--44:10. Google ScholarDigital Library
- Blum, H. 1967. A transformation for extracting new descriptors of shape. Models for the perception of speech and visual form. MIT Press, 362--380.Google Scholar
- Bouix, S., Siddiqi, K., Tannenbaum, A., and Zucker, S. 2006. Medial axis computation and evolution. Statistics and Analysis of Shapes.Google Scholar
- Carr, J. C., Beatson, R. K., Cherrie, J. B., Mitchell, T. J., Fright, W. R., McCallum, B. C., and Evans, T. R. 2001. Reconstruction and representation of 3D objects with radial basis functions. In Proc. of SIGGRAPH, 67--76. Google ScholarDigital Library
- Chuang, J.-H., Ahuja, N., Lin, C.-C., Tsai, C.-H., and Chen, C.-H. 2004. A potential-based generalized cylinder representation. Computers & Graphics 28, 6, 907--918. Google ScholarDigital Library
- Cornea, N. D., Min, P., and Silver, D. 2007. Curve-skeleton properties, applications, and algorithms. IEEE Trans. Vis. & Comp. Graphics 13, 3, 530--548. Google ScholarDigital Library
- de Aguiar, E., Theobalt, C., Thrun, S., and Seidel, H.-P. 2008. Automatic conversion of mesh animations into skeleton-based animations. Computer Graphics Forum (Proc. of Eurographics) 27, 2 (4), 389--397.Google Scholar
- Dey, T., and Sun, J. 2006. Defining and computing curve-skeletons with medial geodesic function. In Symp. on Geom. Proc., 143--152. Google ScholarDigital Library
- Giblin, P. J., and Brassett, S. A. 1985. Local symmetry of plane curves. American Mathematical Monthly, 689--707.Google Scholar
- Hilaga, M., Shinagawa, Y., Kohmura, T., and Kunii, T. L. 2001. Topology matching for fully automatic similarity estimation of 3D shapes. In Proc. of SIGGRAPH, 203--212. Google ScholarDigital Library
- Hoppe, H., DeRose, T., Duchamp, T., McDonald, J., and Stuetzle, W. 1992. Surface reconstruction from unorganized points. In Proc. of SIGGRAPH, 71--78. Google ScholarDigital Library
- James, D., and Twigg, C. 2005. Skinning mesh animations. ACM Trans. on Graph. 24, 3, 399--407. Google ScholarDigital Library
- Katz, S., and Tal, A. 2003. Hierarchical mesh decomposition using fuzzy clustering and cuts. ACM Trans. on Graph. 22, 3, 954--961. Google ScholarDigital Library
- Kazhdan, M., Funkhouser, T., and Rusinkiewicz, S. 2004. Symmetry descriptors and 3D shape matching. In Symp. on Geom. Proc., 115--123. Google ScholarDigital Library
- Kazhdan, M., Bolitho, M., and Hoppe, H. 2006. Poisson surface reconstruction. In Symp. on Geom. Proc., 61--70. Google ScholarDigital Library
- Kim, Y. J., Varadhan, G., Lin, M. C., and Manocha, D. 2003. Fast swept volume approximation of complex polyhedral models. In Proc. of Symp. on Solid Modeling and App., 11--22. Google ScholarDigital Library
- Lee, I. 2000. Curve reconstruction from unorganized points. Computer Aided Geometric Design 17, 2, 161--177. Google ScholarDigital Library
- Lehtinen, J., Zwicker, M., Turquin, E., Kontkanen, J., Durand, F., Sillion, F., and Aila, T. 2008. A meshless hierarchical representation for light transport. ACM Trans. on Graph. 27, 3, 37:1--37:10. Google ScholarDigital Library
- Lewis, J. P., Cordner, M., and Fong, N. 2000. Pose space deformation: a unified approach to shape interpolation and skeleton-driven deformation. In Proc. of SIGGRAPH, 165--172. Google ScholarDigital Library
- Li, X., Woon, T., Tan, T., and Huang, Z. 2001. Decomposing polygon meshes for interactive applications. In Proc. of Symposium on Interactive 3D graphics, 35--42. Google ScholarDigital Library
- Lipman, Y., Cohen-Or, D., Levin, D., and Tal-Ezer, H. 2007. Parameterization-free projection for geometry reconstruction. ACM Trans. on Graph. 26(3), 22:1--22:6. Google ScholarDigital Library
- Lu, L., Choi, Y.-K., Wang, W., and Kim, M.-S. 2007. Variational 3D shape segmentation for bounding volume computation. Computer Graphics Forum (Proc. of Eurographics) 26, 3, 329--338.Google ScholarCross Ref
- Malandain, G., and Fernández-Vidal, S. 1998. Euclidean skeletons. Image and Vision Computing 16, 5, 317--327.Google ScholarCross Ref
- Mitra, N., Guibas, L., and Pauly, M. 2006. Partial and approximate symmetry detection for 3D geometry. ACM Trans. on Graph. 25, 3, 560--568. Google ScholarDigital Library
- Mitra, N. J., Flöry, S., Ovsjanikov, M., Gelfand, N., Guibas, L., and Pottmann, H. 2007. Dynamic geometry registration. In Symp. on Geom. Proc., 173--182. Google ScholarDigital Library
- Nehab, D., Rusinkiewicz, S., Davis, J., and Ramamoorthi, R. 2005. Efficiently combining positions and normals for precise 3D geometry. ACM Trans. on Graph. 24, 3, 536--543. Google ScholarDigital Library
- Ogniewicz, R., Ilg, M., and Zurich, E. 1992. Voronoi skeletons: theory and applications. In Proc. IEEE Conf. on Comp. Vis. and Pat. Rec., 63--69.Google Scholar
- Ovsjanikov, M., Sun, J., and Guibas, L. 2008. Global intrinsic symmetries of shapes. In Computer Graphics Forum (Proc. of Symp. on Geom. Proc.), vol. 27, 1341--1348. Google ScholarDigital Library
- Patane, G., Spagnuolo, M., and Falcidieno, B. 2008. Reeb graph computation based on a minimal contouring. In Proc. IEEE Conf. on Shape Modeling and App., 73--82.Google Scholar
- Pekelny, Y., and Gotsman, C. 2008. Articulated object reconstruction and motion capture from depth video. Computer Graphics Forum (Proc. of Eurographics) 27, 2, 399--408.Google ScholarCross Ref
- Podolak, J., Shilane, P., Golovinskiy, A., Rusinkiewicz, S., and Funkhouser, T. 2006. A planar-reflective symmetry transform for 3D shapes. ACM Trans. on Graph. 25, 3, 549--559. Google ScholarDigital Library
- Raab, R., Gotsman, C., and Sheffer, A. 2004. Virtual woodwork: Making toys from geometric models. Int. J. of Shape Modeling 10, 1, 1--30.Google ScholarCross Ref
- Sharf, A., Lewiner, T., Shamir, A., and Kobbelt, L. 2007. On-the-fly curve-skeleton computation for 3D shapes. Computer Graphics Forum (Proc. of Eurographics) 26, 3, 323--328.Google ScholarCross Ref
- Sharf, A., Lewiner, T., Shklarski, G., Toledo, S., and Cohen-Or, D. 2007. Interactive topology-aware surface reconstruction. ACM Trans. on Graph. 26, 3, 43:1--43:10. Google ScholarDigital Library
- Sharf, A., Alcantara, D. A., Lewiner, T., Greif, C., Sheffer, A., Amenta, N., and Cohen-Or, D. 2008. Space-time surface reconstruction using incompressible flow. ACM Trans. on Graph. 27, 5, 110:1--110:10. Google ScholarDigital Library
- Siddiqi, K., and Pizer, S. 2009. Medial Representations: Mathematics, Algorithms and Applications. Springer. Google Scholar
- Simari, P. D., and Singh, K. 2005. Extraction and remeshing of ellipsoidal representations from mesh data. In Proc. of Graphics Interface, 161--168. Google ScholarDigital Library
- Sorkine, O., and Cohen-Or, D. 2004. Least-squares meshes. In Proc. IEEE Conf. on Shape Modeling and App., 191--199. Google ScholarDigital Library
- Thrun, S., and Wegbreit, B. 2005. Shape from symmetry. In Proc. of Int. Conf. on Comp. Vis., vol. 2, 1824--1831. Google ScholarDigital Library
- Wand, M., Jenke, P., Huang, Q., Bokeloh, M., Guibas, L., and Schilling, A. 2007. Reconstruction of deforming geometry from time-varying point clouds. In Symp. on Geom. Proc., 49--58. Google ScholarDigital Library
Index Terms
- Curve skeleton extraction from incomplete point cloud
Recommendations
L1-medial skeleton of point cloud
We introduce L1-medial skeleton as a curve skeleton representation for 3D point cloud data. The L1-median is well-known as a robust global center of an arbitrary set of points. We make the key observation that adapting L1-medians locally to a point set ...
Curve skeleton extraction from incomplete point cloud
SIGGRAPH '09: ACM SIGGRAPH 2009 papersWe present an algorithm for curve skeleton extraction from imperfect point clouds where large portions of the data may be missing. Our construction is primarily based on a novel notion of generalized rotational symmetry axis (ROSA) of an oriented point ...
Curve skeleton extraction by coupled graph contraction and surface clustering
In this paper, we present a practical algorithm to extract a curve skeleton of a 3D shape. The core of our algorithm comprises coupled processes of graph contraction and surface clustering. Given a 3D shape represented by a triangular mesh, we first ...
Comments