“Abstraction of man-made shapes”
Conference:
Type(s):
Title:
- Abstraction of man-made shapes
Session/Category Title: Shape analysis
Presenter(s)/Author(s):
Moderator(s):
Abstract:
Man-made objects are ubiquitous in the real world and in virtual environments. While such objects can be very detailed, capturing every small feature, they are often identified and characterized by a small set of defining curves. Compact, abstracted shape descriptions based on such curves are often visually more appealing than the original models, which can appear to be visually cluttered. We introduce a novel algorithm for abstracting three-dimensional geometric models using characteristic curves or contours as building blocks for the abstraction. Our method robustly handles models with poor connectivity, including the extreme cases of polygon soups, common in models of man-made objects taken from online repositories. In our algorithm, we use a two-step procedure that first approximates the input model using a manifold, closed envelope surface and then extracts from it a hierarchical abstraction curve network along with suitable normal information. The constructed curve networks form a compact, yet powerful, representation for the input shapes, retaining their key shape characteristics while discarding minor details and irregularities.
References:
1. Arnheim, R. 1956. Art and Visual Perception: A Psychology of the Creative Eye. Faber and Faber.Google Scholar
2. Attene, M., Falcidieno, B., and Spagnuolo, M. 2006. Hierarchical mesh segmentation based on fitting primitives. The Visual Computer 22, 3, 181–193. Google ScholarDigital Library
3. Attneave, F. 1954. Some informational aspects of visual perception. Psychological review 61, 3, 183–193.Google Scholar
4. Bengtsson, A., and Eklundh, J.-O. 1991. Shape representation by multiscale contour approximation. IEEE Trans. on PAMI 13, 1 (Jan), 85–93. Google ScholarDigital Library
5. Bernardini, F., Mittleman, J., Rushmeier, H., Silva, C., and Taubin, G. 1999. The ball-pivoting algorithm for surface reconstruction. IEEE Trans. on Visualization and Computer Graphics 5, 4, 349–359. Google ScholarDigital Library
6. Besl, P. J., and McKay, N. D. 1992. A method for registration of 3-d shapes. IEEE Trans. on PAMI 14, 2, 239–256. Google ScholarDigital Library
7. Biasotti, S., Falcidieno, B., and Spagnuolo, M. 2002. Shape abstraction using computational topology techniques. From geometric modeling to shape modeling, 209–222. Google ScholarDigital Library
8. Bischoff, S., Pavic, D., and Kobbelt, L. 2005. Automatic restoration of polygon models. ACM Trans. Graph. 24, 4. Google ScholarDigital Library
9. Bokeloh, M., Berner, A., Wand, M., Seidel, H.-P., and Schilling, A. 2009. Symmetry detection using line features. Computer Graphics Forum, Proc. of Eurographics 28, 2, 697–706.Google ScholarCross Ref
10. Brown, G., Forte, P., Malyan, R., and Barnwell, P. 1993. A non-linear shape abstraction technique. In CAIP, 223–230. Google ScholarDigital Library
11. Cohen, J., Varshney, A., Manocha, D., Turk, G., Weber, H., Agarwal, P., Brooks, F., and Wright, W. 1996. Simplification envelopes. In Proc. SIGGRAPH, 119–128. Google ScholarDigital Library
12. Cohen-Steiner, D., Alliez, P., and Desbrun, M. 2004. Variational shape approximation. ACM SIGGRAPH Trans. Graph., 905–914. Google ScholarDigital Library
13. Cole, F., Golovinskiy, A., Limpaecher, A., Barros, H. S., Finkelstein, A., Funkhouser, T., and Rusinkiewicz, S. 2008. Where do people draw lines? ACM SIGGRAPH Trans. Graph. 27, 3, #88, 1–11. Google ScholarDigital Library
14. Costa, L., and Cesar, R. M. 2001. Shape Analysis and Classification: Theory and Practice. CRC Press. Google ScholarDigital Library
15. DeCarlo, D., Finkelstein, A., Rusinkiewicz, S., and Santella, A. 2003. Suggestive contours for conveying shape. ACM SIGGRAPH Trans. Graph. 22, 3 (July), 848–855. Google ScholarDigital Library
16. Demirci, M., Shokoufandeh, A., and Dickinson, S. J. 2009. Skeletal shape abstraction from examples. IEEE Trans. on PAMI 31, 5, 944–952. Google ScholarDigital Library
17. Falcidieno, B., and Spagnuolo, M. 1998. A shape abstraction paradigm for modelling geometry and semantics. In Computer Graphics International, 646–656. Google ScholarDigital Library
18. Gal, R., Sorkine, O., Popa, T., Sheffer, A., and Cohen-Or, D. 2007. 3d collage: expressive non-realistic modeling. In Proc. of NPAR, ACM, New York, NY, USA, 7–14. Google ScholarDigital Library
19. Gal, R., Sorkine, O., Mitra, N. J., and Cohen-Or, D. 2009. iwires: An analyze-and-edit approach to shape manipulation. ACM SIGGRAPH Trans. Graph. 28, 3, #33, 1–10. Google ScholarDigital Library
20. Garland, M., and Heckbert, P. S. 1997. Surface simplification using quadric error metrics. In Proc. SIGGRAPH, 209–216. Google ScholarDigital Library
21. Grabler, F., Agrawala, M., Sumner, R. W., and Pauly, M. 2008. Automatic generation of tourist maps. ACM SIGGRAPH Trans. Graph. 27, 3, 1–11. Google ScholarDigital Library
22. Hou, S., and Ramani, K. 2008. Structure-oriented contour representation and matching for engineering shapes. Computer Aided Design 40, 1, 94–108. Google ScholarDigital Library
23. Julius, D., Kraevoy, V., and Sheffer, A. 2005. D-charts: Quasi-developable mesh segmentation. In Computer Graphics Forum, Proc. of Eurographics, vol. 24, 581–590.Google ScholarCross Ref
24. Koenderink, J. J., and van Doorn, A. J. 1979. The internal representation of solid shape with respect to vision. Journal Biological Cybernetics 32, 4, 211–216.Google ScholarDigital Library
25. Kraevoy, V., Sheffer, A., Shamir, A., and Cohen-Or, D. 2008. Non-homogeneous resizing of complex models. ACM SIGGRAPH Trans. Graph. 27, 5, 1–9. Google ScholarDigital Library
26. Kruskal, J. B., and Wish, M. 1978. Multidimensional scaling. Sage University Paper series on Quantitative Application in the Social Sciences 07–011.Google Scholar
27. Merrell, P., and Manocha, D. 2008. Continuous model synthesis. ACM Trans. Graph. 27, 5, 1–7. Google ScholarDigital Library
28. Mitra, N. J., Guibas, L., and Pauly, M. 2006. Partial and approximate symmetry detection for 3d geometry. In ACM SIGGRAPH Trans. Graph., vol. 25, 560–568. Google ScholarDigital Library
29. Mitra, N. J., Guibas, L., and Pauly, M. 2007. Symmetrization. In ACM SIGGRAPH Trans. Graph., vol. 26, #63, 1–8. Google ScholarDigital Library
30. Na, K., Jung, M., Lee, J., and Songa, C. G. 2005. Redeeming valleys and ridges for line-drawing. In Advances in Mulitmedia Information Processing, 327–338. Google ScholarDigital Library
31. Nackman, L., and Pizer, S. 1985. Three-dimensional shape description using the symmetric axis transform. IEEE Trans. on PAMI 7, 2, 187–201.Google ScholarDigital Library
32. Nealen, A., Igarashi, T., Sorkine, O., and Alexa, M. 2007. Fibermesh: designing freeform surfaces with 3d curves. ACM SIGGRAPH Trans. Graph. 26, 3, 41. Google ScholarDigital Library
33. Orzan, A., Bousseau, A., Winnemöller, H., Barla, P., Thollot, J., and Salesin, D. 2008. Diffusion curves: A vector representation for smooth-shaded images. In ACM SIGGRAPH Trans. Graph., vol. 27. Google ScholarDigital Library
34. Pauly, M., Mitra, N. J., Wallner, J., Pottmann, H., and Guibas, L. 2008. Discovering structural regularity in 3D geometry. ACM SIGGRAPH Trans. Graph. 27, 3, #43, 1–11. Google ScholarDigital Library
35. Poggio, T., Torre, V., and Koch, C. 1985. Computational vision and regularization theory. Nature 317, 314–319. Google ScholarDigital Library
36. Popa, T., Julius, D., and Sheffer, A. 2006. Material-aware mesh deformations. In SMI, 22. Google ScholarDigital Library
37. Sharf, A., Lewiner, T., Shamir, A., Kobbelt, L., and Cohen-Or, D. 2006. Competing fronts for coarse-to-fine surface reconstruction. Computer Graphics Forum, Proc. of Eurographics 25, 3, 389–398.Google ScholarCross Ref
38. Sheffer, A., Lévy, B., Mogilnitsky, M., and Bogomyakov, A. 2005. Abf++: fast and robust angle based flattening. ACM Trans. Graph. 24, 2, 311–330. Google ScholarDigital Library
39. Shen, C., O’Brien, J. F., and Shewchuk, J. R. 2004. Interpolating and approximating implicit surfaces from polygon soup. In ACM SIGGRAPH Trans. Graph., ACM Press, 896–904. Google ScholarDigital Library
40. Shewchuk, J. 1996. Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator. In Applied Computational Geometry: Towards Geometric Engineering, vol. 1148. Springer-Verlag, 203–222. Google ScholarDigital Library
41. Sorkine, O., Lipman, Y., Cohen-Or, D., Alexa, M., Rössl, C., and Seidel, H.-P. 2004. Laplacian surface editing. In Proc. of Symp. of Geometry Processing, 179–188. Google ScholarDigital Library
42. Sumner, R. W., and Popović, J. 2004. Deformation transfer for triangle meshes. In ACM SIGGRAPH Trans. Graph., 399–405. Google ScholarDigital Library
43. Surazhsky, V., and Gotsman, C. 2003. Explicit surface remeshing. In Proc. of Symp. of Geometry Processing, 17–28. Google ScholarDigital Library
44. Theobalt, C., Rössl, C., de Aguiar, E., and Seidel, H.-P. 2007. Animation collage. In Proc. of Symp. of Computer Animation, 271–280. Google ScholarDigital Library
45. Toledo, S., Chen, D., and Rotkin, V., 2003. Taucs: A library of sparse linear solvers. http://www.tau.ac.il/stoledo/taucs/.Google Scholar
46. Várady, T., and Martin, R. R. 2002. Reverse engineering. In Handbook of Computer Aided Geometric Design, G. Farin, J. Hoschek, and M. S. Kim, Eds. Springer, 651–681.Google Scholar
47. Wu, J., and Kobbelt, L. 2005. Structure recovery via hybrid variational surface approximation. Computer Graphics Forum, Proc. of Eurographics 24, 3, 277–284.Google ScholarCross Ref
48. Yan, D. M., Liu, Y., and Wang, W. 2006. Quadric surface extraction by variational shape approximation. In Geometric Modeling and Processing, 73–86. Google ScholarDigital Library
