Open Access Open Access  Restricted Access Subscription or Fee Access

A Rapid Convex Decomposition Technique for Shape Simplification

Elsayed E. Hemayed, Aladdin M. Abd-ElAal

Abstract


In this paper we address the problem of decomposing a polyhedral surface into convex patches. We describe a modified convex patch definition and based on that definition we develop a convex decomposition algorithm that decomposes a given surface model into "exact convex" or "approximate convex" patches according to a user defined angle threshold. The resulting patches provide similar benefits as former surface convex decompositions and takes less processing time. The proposed decomposition technique takes few seconds to decompose complex models such as Armadillo model. In order to show the effectiveness of the proposed technique, we use it along with edge collapse technique and develop a shape simplification algorithm. The proposed simplification algorithm decomposes the model first into convex patches, categorizes them into large and small convex patches and then applies a simplification scheme only to the large ones, thus maintaining important geometrical and topological information of original model. The proposed simplification technique is faster than the general decimation approach. The details of the proposed techniques along with experimental results are discussed in this paper.

Keywords


Polyhedral Surface Decomposition, Convex Decomposition, Shape Simplification, Computer Graphics.

Full Text:

PDF

References


A. Shamir, “A Survey on Mesh Segmentation Techniques”, Computer Graphics Forum, vol. 27, no. 6, pp. 1539-1556, 2008.

B. Chazelle and L. Palios, “Decomposition algorithms in geometry”, In: C. Bajaj, editor, Algebraic Geometry and its Applications, chapter 27. Springer-Verlag, pp. 419–447, 1994.

D. Hoffman and W. Richards, “Parts of recognition”, Cognition, vol. 18, pp. 65–96, 1984.

B. Chazelle, D. P. Dobkin, N. Shouraboura, and A. Tal, “Strategies for Polyhedral Surface Decomposition: An Experimental Study”, Computational Geometry, vol. 7, no. (4-5), pp. 327-342, 1997.

J. M. Lien, “Approximate Convex Decomposition and Its Applications”, Ph.D. Thesis, Department of Computer Science and Engineering, Texas A&M University, Dec 2006.

J. M. Lien and N. A. Amato, “Approximate convex decomposition of polyhedral”, In Proceedings of ACM symposium on Solid and physical modeling, pp. 121-131, 2007.

M. Attene, M. Mortara, M. Spagnuolo, and B. Falcidieno, “Hierarchical Convex Approximation of 3D Shapes for Fast Region Selection”, Computer Graphics Forum, vol. 27, no. 5, pp. 1303-1323, 2008.

E. Zuckerberger, A. Tal, and S. Shlafman, “Polyhedral surface decomposition with applications”, Computers and Graphics, vol. 26, no. 5, pp. 733-743, 2002.

V. Kraevoy, D. Julius, and A. Sheffer, “Shuffler: Modeling with interchangeable parts”, Ayia-Napa Summer Seminar, Recent Results in Rendering and Modeling in Computer Graphics, 2006.

H. Liu, W. Liu, and L. J. Latecki, “Convex Shape Decomposition”, IEEE Conf. Computer Vision and Pattern Recognition 2010.

S. Katz and A. Tal, “Hierarchical mesh decomposition using fuzzy clustering and cuts”, ACM Transactions on Graphics, vol. 22, no. 3, pp. 954–961, 2004.

S. Katz and A. Tal, “Segmentation using feature point and core extraction”, The Visual Computer, vol. 21, no. (8-10), pp. 865–875, 2005.

H. Zhang and R. Liu, “Mesh segmentation via recursive and visually salient spectral cuts”, In Proceedings of Vision, Modeling and Visualization, pp. 429–436, 2005.

Y. K. Lai, S. M. Hu, R. R. Martin, and P. L. Rosin, “Rapid and Effective Segmentation of 3D Models using Random Walks”, Computer Aided Geometry Design, vol. 26, no. 6, pp. 665-679, 2009.

L. D. Floriani and E. Puppo, “Mesh Simplification Course”, AIMatshape Virtual,lecture-2004.http://www.aimatshape.net/resources/v-lectures/meshsimplification.

P. Heckbert and M. Garland, “Survey of Polygonal Surface Simplification Algorithms”, Siggraph 97 Course Notes, no. 25, ACM Press, New York, 1997.

A. Thakura, A. G. Banerjeea, and S. K. Gupta, “A survey of CAD model simplification techniques for physics-based simulation applications”, Computer Aided Design, vol. 41, no. 2, pp. 65-80, 2009.

J. Rossignac amd P. Borrel, “Multi-resolution 3D approximations for rendering complex scenes”, In B. Falcidieno and T. Kunii, editors, Modeling in Computer Graphics: Methods and Applications, Berlin. June 1993, pp. 455–465.

D. Cohen-Steiner, P. Alliez, and M. Desbrun, “Variational shape approximation”, ACM Transactions on Graphics, vol. 23, no. 3, pp.905–914, 2004.

W. J. Schroeder, J. A. Zarge, and W. E. Lorensen, “Decimation of Triangle Meshes”, ACM Computer Graphics, vol. 26, no. 2, pp. 65-70, 1992

H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, and W. Stuetzle, “Mesh optimization”, Computer Graphics, vol. 27, pp. 19–26, 1993.

H. Hoppe, “Progressive meshes”, In SIGGRAPH, pp. 99–108, 1996.

J. Cohen, M. Olano, and D. Manocha, “Appearance-perserving simplification”, In Proceedings of the 25th annual conference on Computer graphics and interactive techniques, pp. 115–122, 1998.

J. Cohen, A. Varshney, D. Manocha, G. Turk, H. Weber, P. Agarwal, F. Brooks, and W. Wright, “Simplification envelopes”, In SIGGRAPH, pp. 119–128, 1996.

S. Zelinka, and M. Garland, “Permission grids: Practical, error-bounded simplification”, ACM Transactions on Graphics, vol. 21, no. 2, pp. 207-229, 2002.

A. D. Kalvin and R. H. Taylor, “Superfaces: polygonal mesh simplification with bounded error”, IEEE Computer Graphics and Applications, vol. 16, no. 3, pp. 64-77, 1996.

G. Turk, “Re-tiling polygonal surfaces”, Computer Graphics, vol. 26, no. 2, pp. 55–64, 1992.

M. Garland and Y. Zhou, “Quadric based surface simplification in any dimension”, ACM Transactions on Graphics, vol. 24, no. 2, pp. 209-239, 2005.

G. Barequet, D. Shapiro, and A. Tal, “Multi-Level Sensitive Reconstruction of Polyhedral Surfaces from Parallel Slices”, The Visual Computer, vol. 16, no. 2, pp. 116-133, 2000.

T. Garthwaite and J. Reposa, “Mesh Decimation”, Major Qualifying Project Report, MOW-2733, Worcester Polytechnic Institute, 2000.


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.