Mini Review on Efficient Data Structure For 3D Modelling of Polygonal Mesh. Nurhamiezrah MIDIN & Abdullah BADE. Download pdf. Keywords: Polygonal mesh; data structure; remeshing; random access; streaming representation. A b s t r a c t 3D graphics has become an increasingly important part in geometric modelling visualization. 3D model is mainly represented by polygonal mesh. Highly complex meshes result in expensive rendering cost, exceeding the memory storage, difficulty to transmit data and unable to be edited. The development of data structure to store meshes information and handling those problems have begun since 30 years ago. This paper aims to highlight the major approaches of various types of algorithm used to address specific problems in storing mesh data over a decade. Trend has shown that remeshing, random access and streaming representation are the methods that been used widely recently. We believe this paper will help other researchers to be familiar with polygonal mesh and their connotation. References Aghdaii, N., Younesy, H. & Zhang, H. 2012. 5�6�7 Meshes: Remeshing and analysis. Computers & Graphics. 36(8): 1072-1083. Ahn, M., Guskov, I. & Lee, S. 2006. Out-of-core remeshing of large polygonal meshes. IEEE Transaction on Visualization and Computer Graphics. 12(5): 1221-1228. Ahn, J. K., Koh, Y. J. & Kim, C. S. 2013. Efficient Fine-Granular Scalable Coding of 3D Mesh Sequences. IEEE Transactions on Multimedia. 15(3): 485-497. Allegre, R., Chaine, R. & Akkouche, S. 2007. A Streaming Algorithm for Surface Reconstruction. SGP '07 Proceedings of the Fifth Eurographics Symposium on Geometry Processing. 4 July, 2017, Switzerland. Alliez, P. & Gotsman, C. 2005. Recent advances in compression of 3D meshes. In: Neil, A. D., Michael, S. F. & Malcolm, A. S. (eds.) Advances in Multiresolution for Geometric Modelling. Berlin: Springer Berlin Heidelberg. Alliez, P., Ucelli, G., Gotsman, C. & Attene, M. 2008. Recent advances in remeshing of surfaces. In: Floriani, L. D. & Spagnuolo, M. (eds.) Shape analysis and structuring. Berlin: Springer Berlin Heidelberg. Amjoun, R. & Strasser, W. 2008. Predictive-DCT coding for 3D mesh sequences compression. Journal of Virtual Reality and Broadcasting. 5(6): 13pp. Amjoun, R. & Strasser, W. 2009. Single-rate near lossless compression of animated geometry. Computer-Aided Design, 41(10): 711-718. Attene, M., Campen, M. & Kobbelt, L. 2013. Polygon mesh repairing: An application perspective. ACM Computing Surveys (CSUR). 45(2): A15. Bici, M. O. & Akar, G. B. 2011. Improved prediction methods for scalable predictive animated mesh compression. Journal of Visual Communication and Image Representation, 22(7): 577-589. Bolitho, M., Kazhdan, M., Burns, R. & Hoppe, H. 2007. Multilevel streaming for out-of-core surface reconstruction. Symposium on Geometry Processing. 4-6 July, Barcelona, Spain. Botsch, M., Steinberg, S., Bischoff, S. & Kobbelt, L. 2002. Openmesh - a generic and efficient polygon mesh data structure. OpenSG Symposium. January 202, Darmstadt, Germany. Boubekeur, T. & Alexa, M. 2009. Mesh simplification by stochastic sampling and topological clustering. Computers & Graphics. 33(3): 241-249. Building 3D Primitive. 2014. Introduction to Computer Graphics (cs.edu.my). Accesssed on January 2015. Chen, X., Golovinskiy, A. & Funkhouser, T. 2009. A benchmark for 3D mesh segmentation. ACM Transactions on Graphics (TOG). 28(3): 12pp. Cheng, S. C., Kuo, C. T. & Wu, D. C. 2010. A novel 3D mesh compression using mesh segmentation with multiple principal plane analysis. Pattern Recognition. 43(1): 267-279. Choe, S., Kim, J., Lee, H. & Lee, S. 2009. Random accessible mesh compression using mesh chartification. IEEE Transactions on Visualization and Computer Graphics. 15(1): 160-173. Courbet, C. & Hudelot, C. 2009. Random accessible hierarchical mesh compression for interactive visualization. Symposium on Geometry Processing. 15 July 2009, Switzerland. De Floriani, L., Kobbelt, L. & Puppo, E. 2005. A survey on data structures for level-of-detail models. In: Dodgson, N. A., Floater, M. S. & Sabin, M. A. (eds.) Advances in multiresolution for geometric modeling. Berlin: Springer Berlin Heidelberg. Diaz-Gutierrez, P., Gopi, M. & Pajarola, R. 2005. Hierarchyless Simplification, Stripification and Compression of Triangulated Two-Manifolds. Computer Graphics Forum, 24(3): 457�467. Du, Q. & Wang, D. 2003. Tetrahedral mesh generation and optimization based on centroidal Voronoi tessellations. International journal for numerical methods in engineering. 56(9): 1355-1373. Erwig, M., Gu, R. H., Schneider, M. & Vazirgiannis, M. 1999. Spatio-temporal data types: An approach to modeling and querying moving objects in databases. GeoInformatica. 3(3): 269-296. Francois, V. & Cuilliere, J. C. 2000. 3D automatic remeshing applied to model modification. Computer-Aided Design. 32(7): 433-444. Gurung, T., Laney, D., Lindstrom, P. & Rossignac, J. 2011. SQuad: Compact representation for triangle meshes. Computer Graphics Forum. 30(2): 355-364. Gurung, T., Luffel, M., Lindstrom, P. & Rossignac, J. 2011. LR: compact connectivity representation for triangle meshes. ACM Transactions on Graphics (TOG). 30(4): A67. Gurung, T., Luffel, M., Lindstrom, P. & Rossignac, J. 2013. Zipper: A compact connectivity data structure for triangle meshes. Computer-Aided Design. 45(2): 262-269. Isenburg, M. & Lindstrom, P. 2005. Streaming meshes. IEEE Visualization 2005. 23-28 October, 2005, Minneapolis, United States. Jolliffe, I. 2002. Principal component analysis. John Wiley & Sons, Ltd, Hoboken, New Jersey. Kalberer, F., Polthier, K., Reitebuch, U. & Wardetzky, M. 2005, September. FreeLence-Coding with Free Valences. Computer Graphics Forum. 24(3): 469-478. Kim, J., Choe, S. & Lee, S. 2006. Multiresolution random accessible mesh compression. Computer Graphics Forum. 25(3): 323-331. Kim, T. J., Moon, B., Kim, D. & Yoon, S. E. 2010. RACBVHs: Random-accessible compressed bounding volume hierarchies. IEEE Transactions on Visualization and Computer Graphics. 16(2): 273-286. Kot, A., Chernikov, A. N. & Chrisochoides, N. P. 2005. Out-of-core parallel Delaunay mesh generation. 17th IMACS World Congress Scientific Computation, Applied Mathematics and Simulation. 25-29 April, 2005, Paris, France. Li, L., He, M. & Wang, P. 2010. Mesh simplification algorithm based on absolute curvature-weighted quadric error metrics. 5th IEEE Conference on Industrial Electronics and Applications (ICIEA). 15-17 June, 2010, Taichung, Taiwan. Luebke, D. P. 2001. A developer's survey of polygonal simplification algorithms. IEEE Transactions on Computer Graphics and Applications. 21(3): 24-35. Luffel, M., Gurung, T., Lindstrom, P. & Rossignac, J. 2014. Grouper: A Compact, Streamable Triangle Mesh Data Structure. IEEE Transactions on Visualization and Computer Graphics. 20(1): 84-98. Maglo, A., Grimstead, I. & Hudelot, C. 2013. POMAR: Compression of progressive oriented meshes accessible randomly. Computers & Graphics. 37(6): 743-752. Maglo, A., Lavoue, G., Dupont, F. & Hudelot, C. 2015. 3D Mesh Compression: Survey, Comparisons, and Emerging Trends. ACM Computing Surveys (CSUR). 47(3): A44. Mamou, K., Zaharia, T. & Preteux, F. 2009. TFAN: A low complexity 3D mesh compression algorithm. Computer Animation and Virtual Worlds. 20(2-3): 343-354. Muller, K., Smolic, A., Kautzner, M., Eisert, P. & Wiegand, T. 2005. Predictive compression of dynamic 3D meshes. IEEE International Conference on Image Processing (ICIP 2005). 11-14 September, Genova, Italy. Neperud, B. 2005. Visualizing mesh data structures and algorithms. Proceedings of MICS. 8-9 April, 2005, Eau Claire, Winconsin. Pakhira, M. K. 2010. Out-of-core assessment of clustering tendency for large data sets. 2nd IEEE International Conference on Advance Computing Conference (IACC). 19-20 February, 2010, Patiala, India. Payan, F. & Antonini, M. 2005. Wavelet-based compression of 3d mesh sequences. ACIDCA-ICMI'2005. 5-7 November, 2005, Tozeur, Tunisia. Peng, J., Kim, C. S. & Kuo, C. C. J. 2005. Technologies for 3D mesh compression: A survey. Journal of Visual Communication and Image Representation. 16(6): 688-733. Repair Defects in Meshes. 2010. Modelling (autodesk.com). Accesssed on March 2015. Roy, M., Foufou, S. & Truchetet, F. 2010. Recent advances in multiresolution analysis of 3D meshes and their applications. IS&T/SPIE Electronic Imaging, International Society for Optics and Photonics. 17-21 January, 2010, California, USA. Rus, J. & Vasa, L. 2010. Analysing the influence of vertex clustering on pca-based dynamic mesh compression. In: Lopez, P., Jose, F., Fisher, Robert B., Moeslund, Thomas B. (eds.) Articulated Motion and Deformable Objects. Berlin: Springer Berlin Heidelberg. Serna, S. P., Stork, A. & Fellner, D. W. 2011. Considerations toward a dynamic mesh data structure. SIGRAD Conference. 17-18 November, 2011, Stockholm, Sweden. Stefanoski, N. & Ostermann, J. 2008. Spatially and temporally scalable compression of animated 3D meshes with MPEG-4/FAMC. IEEE International Conference on Image Processing (ICIP 2008). 12-15 October, 2008, San Diego, USA. Static Mesh (SM). 2014. Unreal Engine 4 Documentation (docs.unrealengine.com). Accesssed on March 2015. Vasa, L. & Brunnett, G. 2013. Exploiting connectivity to improve the tangential part of geometry prediction. IEEE Transactions on Visualization and Computer Graphics. 19(9): 1467-1475. Vasa, L. & Skala, V. 2009, September. Cobra: Compression of the basis for PCA represented animations. Computer Graphics Forum. 28(6): 1529-1540. Vidal, V., Lavoue, G. & Dupont, F. 2015. Low budget and high fidelity relaxed 567-remeshing. Computers & Graphics. 47: 16-23. Wang, C., Liu, Y., Guo, X., Zhong, Z., Le, B. & Deng, Z. 2015. Spectral Animation Compression. Journal of Computer Science and Technology. 30(3): 540-552. Yoon, S. E. & Lindstrom, P. 2007. Random-accessible compressed triangle meshes. IEEE Transactions on Visualization and Computer Graphics. 13(6): 1536-1543. Zheng, Z. 2012. Simplification Algorithm for General Meshes. Fifth IEEE International Joint Conference on Computational Sciences and Optimization (CSO). 23-26 June, 2012. Harbin, China.