Sphere-Meshes: shape approximation using spherical quadric error metrics

Abstract

Shape approximation algorithms aim at computing simple geometric descriptions of dense surface meshes. Many such algorithms are based on mesh decimation techniques, generating coarse triangulations while optimizing for a particular metric which models the distance to the original shape. This approximation scheme is very efficient when enough polygons are allowed for the simplified model. However, as coarser approximations are reached, the intrinsic piecewise linear point interpolation which defines the decimated geometry fails at capturing even simple structures. We claim that when reaching such extreme simplification levels, highly instrumental in shape analysis, the approximating representation should explicitly and progressively model the volumetric extent of the original shape. In this paper, we propose Sphere-Meshes, a new shape representation designed for extreme approximations and substituting a sphere interpolation for the classic point interpolation of surface meshes. From a technical point-of-view, we propose a new shape approximation algorithm, generating a sphere-mesh at a prescribed level of detail from a classical polygon mesh. We also introduce a new metric to guide this approximation, the Spherical Quadric Error Metric in R⁴, whose minimizer finds the sphere that best approximates a set of tangent planes in the input and which is sensitive to surface orientation, thus distinguishing naturally between the inside and the outside of an object. We evaluate the performance of our algorithm on a collection of models covering a wide range of topological and geometric structures and compare it against alternate methods. Lastly, we propose an application to deformation control where a sphere-mesh hierarchy is used as a convenient rig for altering the input shape interactively.

References

1. Alliez, P., de Verdière, E. C., Devillers, O., and Isenburg, M. 2003. In Shape Modeling International, 2003, IEEE, 49--58.
2. Amenta, N., and Bern, M. 1999. Surface reconstruction by voronoi filtering. Discrete & Computational Geometry 22, 4, 481--504.
3. Amenta, N., Choi, S., and Kolluri, R. 2001. The power crust. In Proceedings of the sixth ACM symposium on Solid modeling and applications, ACM, 249--266.
4. Attali, D., and Montanvert, A. 1996. Modeling noise for a better simplification of skeletons. In Image Processing, 1996. Proceedings., International Conference on, vol. 3, IEEE, 13--16.
5. Baran, I., and Popovíc, J. 2007. Automatic rigging and animation of 3d characters. In ACM Transactions on Graphics (TOG), vol. 26, ACM, 72.
6. Ben-Chen, M., and Gotsman, C. 2008. Characterizing shape using conformal factors. In Eurographics workshop on 3D object retrieval, 1--8.
7. Blum, H. 1967. A Transformation for Extracting New Descriptors of Shape. In Models for the Perception of Speech and Visual Form, W. Wathen-Dunn, Ed. MIT Press, Cambridge, 362--380.
8. Bradshaw, G., and O'Sullivan, C. 2002. Sphere-tree construction using dynamic medial axis approximation. In Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, ACM, 33--40.
9. Bradshaw, G., and O'Sullivan, C. 2004. Adaptive medial-axis approximation for sphere-tree construction. ACM Transactions on Graphics (TOG) 23, 1, 1--26.
10. Chazal, F., and Lieutier, A. 2005. The λ-medial axis. Graphical Models 67, 4, 304--331.
11. Cohen-Steiner, D., Alliez, P., and Desbrun, M. 2004. Variational shape approximation. In ACM Transactions on Graphics (TOG), vol. 23, ACM, 905--914.
12. De Floriani, L., Magillo, P., Puppo, E., and Sobrero, D. 2004. A multi-resolution topological representation for non-manifold meshes. Computer-Aided Design 36, 2, 141--159.
13. Dey, T., and Zhao, W. 2004. Approximate medial axis as a voronoi subcomplex. Computer-Aided Design 36, 2, 195--202.
14. Garland, M., and Heckbert, P. 1997. Surface simplification using quadric error metrics. In Proceedings of the 24th annual conference on Computer graphics and interactive techniques, ACM Press/Addison-Wesley Publishing Co., 209--216.
15. Gärtner, B., and Herrmann, T. 2001. Computing the width of a point set in 3-space.
16. Hoppe, H., DeRose, T., Duchamp, T., McDonald, J., and Stuetzle, W. 1993. Mesh optimization. In ACM SIGGRAPH, 19--26.
17. James, D. L., and Pai, D. K. 2004. Bd-tree: output-sensitive collision detection for reduced deformable models. ACM Transactions on Graphics (TOG) 23, 3, 393--398.
18. Ji, Z., Liu, L., and Wang, Y. 2010. B-mesh: A modeling system for base meshes of 3d articulated shapes. In Computer Graphics Forum, vol. 29, Wiley Online Library, 2169--2177.
19. Lewis, J., Cordner, M., and Fong, N. 2000. 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, ACM Press/Addison-Wesley Publishing Co., 165--172.
20. Lindstrom, P. 2000. Out-of-core simplification of large polygonal models. In ACM SIGGRAPH, 259--262.
21. Lipman, Y., Levin, D., and Cohen-Or, D. 2008. Green coordinates. ACM Transactions on Graphics (TOG) 27, 3, 78:1--78:10.
22. Lu, L., Choi, Y., Wang, W., and Kim, M. 2007. Variational 3d shape segmentation for bounding volume computation. In Computer Graphics Forum, vol. 26, Wiley Online Library, 329--338.
23. Miklos, B., Giesen, J., and Pauly, M. 2010. Discrete scale axis representations for 3d geometry. ACM Transactions on Graphics (TOG) 29, 4, 101.
24. Pixologic, 2001. Zbrush.
25. Rossignac, J., and Borrel, P. 1993. Multi-resolution 3d approximation for rendering complex scenes. Modeling in Computer Graphics, 455--465.
26. Rusinkiewicz, S., and Levoy, M. 2000. Qsplat: a multiresolution point rendering system for large meshes. In SIGGRAPH, 343--352.
27. Schaefer, S., and Warren, J. 2003. Adaptive vertex clustering using octrees. In Proceedings of SIAM Geometric Design and Computing, 491--500.
28. Stolpner, S., Kry, P., and Siddiqi, K. 2012. Medial spheres for shape approximation. Pattern Analysis and Machine Intelligence, IEEE Transactions on 34, 6, 1234--1240.
29. Sud, A., Foskey, M., and Manocha, D. 2007. Homotopy-preserving medial axis simplification. International Journal of Computational Geometry & Applications 17, 05, 423--451.
30. Tam, R., and Heidrich, W. 2003. Shape simplification based on the medial axis transform. In Visualization, 2003. VIS 2003. IEEE, IEEE, 481--488.
31. Turk, G. 1992. Re-tiling polygonal surfaces. Computer Graphics (SIGGRAPH 92) 26, 2 (July), 55--64.
32. Wang, R., Zhou, K., Snyder, J., Liu, X., Bao, H., Peng, Q., and Guo, B. 2006. Variational sphere set approximation for solid objects. The Visual Computer 22, 9, 612--621.
33. Wu, J., and Kobbelt, L. 2005. Structure recovery via hybrid variational surface approximation. Computer Graphics Forum 24, 3, 277--284.
34. Yan, D.-M., Liu, Y., and Wang, W. 2006. Quadric surface extraction by variational shape approximation. In Geometric Modeling and Processing, vol. 4077 of Lecture Notes in Computer Science. 73--86.
35. Yan, D.-M., Lévy, B., Liu, Y., Sun, F., and Wang, W. 2009. Isotropic remeshing with fast and exact computation of restricted voronoi diagram. In Proc. Symposium on Geometry Processing, 1445--1454.
36. Zorin, D., Schröder, P., and Sweldens, W. 1997. Interactive multiresolution mesh editing. In ACM SIGGRAPH '97, 259--268.

Index Terms

• Computing methodologies

  • Computer graphics

    • Image manipulation

    • Shape modeling

      • Parametric curve and surface models

      • Volumetric models

• Theory of computation

  • Randomness, geometry and discrete structures

    • Computational geometry