Triangular modeling using Delaunay based region growing approach

  • Authors

    • Vandana Agrawal Motilal Nehru National Institute of Technology Allahabad, India
    2019-07-14
    https://doi.org/10.14419/ijet.v7i4.20322
  • Triangulation, Reverse Engineering, Region growing.

  • Abstract

    In the present work a Delaunay based region growing algorithm is proposed to create triangulated model from the unorganized data set obtained by coordinate measuring machine (CMM).The algorithm maintains the advantages of both Delaunay based and region growing approaches. In this algorithm a data structure is created which contains the information about the edges and the vertices of all the triangles created by Delaunay triangulation. Further a region growing process is used by initiating a seed triangle. The new triangles selected from Delaunay data structure are incrementally added to the region. One of the advantage of suggested algorithm is that no post processing is required as hole filling and topological examination is done during the growing process itself. The region growing takes place more smoothly along the faces of the object when algorithm is applied by incorporating hole filling process and topological examination. Further, the holes and topological disorders like neck vertices and non-manifold surface disappeared when algorithm is applied by incorporating hole filling process and topological examination in comparison to the modelling excluding them. The triangulated model created so can be used for subsequent processes of reverse engineering like segmentation and surface fitting.

     

  • References

    1. [1] M. Vieira, K. Shimada, Surface mesh segmentation and smooth surface extraction through region growing, Computer Aided Geometric Design, 22 (2005) 771-792https://doi.org/10.1016/j.cagd.2005.03.006.

      [2] G. Lavoue, F. Dupont, A. Baskurt, A new CAD mesh segmentation method, based on curvature tensor analysis, Computer Aided Design, 37, (2005) 975-987. https://doi.org/10.1016/j.cad.2004.09.001.

      [3] M.E. Algorri, F. Schmitt, Surface reconstruction from unstructured 3D data, Computer Graphics forum, 15, 1 (1996) 47-60. https://doi.org/10.1111/1467-8659.1510047.

      [4] J. Dan, W. Lancheng, An algorithm of NURBS surface fitting for reverse engineering, International Journal of Advances in Manufacturing Technology 31(2006) 92-97. https://doi.org/10.1007/s00170-005-0161-3.

      [5] J.D. Boissonnat, Gometric structures for three dimensional shape representation, ACM Transactions on Graphics,3, 4 (1984) 266-286. https://doi.org/10.1145/357346.357349.

      [6] N. Amenta, M. Bern, M. Kamvysselis, A new Voronoi based surface reconstruction algorithm, In: Proceedings of SIGGRAPH, (1998) 415-421.https://doi.org/10.1145/280814.280947.

      [7] N. Amenta, S. Choi, R.V. Kolluri, The power crust, Proceedings of sixth ACM symposium on solid modelling and applications, Ann Arbor, MI, USA (2001) 249-266. https://doi.org/10.1145/376957.376986.

      [8] E. Menel, H. Muller, Graph based surface reconstruction using structures in scattered point sets, Proceedings of CGI’98 (Computer Graphics International) (1998) 298-311

      [9] F. Bernardini, C. Bajaj, F. Chen, D. Schikore, Automatic reconstruction of 3D CAD models from digital scans, International Journal of Computational Geometry and Applications, 9, 4-5 (1999) 327-369 https://doi.org/10.1142/S0218195999000236.

      [10] F. Bernardini, J. Mittleman, H. Rushmeier, C. Silva, G. Taubin, The ball pivoting algorithm for surface reconstruction, IEEE Transactions on Visualisation and Computer Graphics, 5, 4 (1999) 349-359. https://doi.org/10.1109/2945.817351.

      [11] M. Gopi, S. Krishnan, A fast and efficient projection based approach for surface reconstruction, High Performance Computer Graphics, Multimedia and Visualisation, 1,1(2000) 1-12.

      [12] S. Petitjean, E. Boyer, Regular and non-regular point sets: Properties and reconstruction, Computational Geometry, 19, 2-3 (2001),101-126. https://doi.org/10.1016/S0925-7721(01)00016-5.

      [13] J. Huang, C.H. Menq, Combinatorial manifold mesh reconstruction and optimization from unorganized points with arbitrary topology, Computer Aided Design, 34, 2 (2002) 149-165.https://doi.org/10.1016/S0010-4485(01)00079-3.

      [14] C.S. David, A greedy delaunay based surface reconstruction algorithm, Research Report INRIA , 2002

      [15] W. Sun, C. Bradley, Y.F. Zhang, H.T. Loh, Cloud data modelling employing a unified, non-redundant triangular mesh, Computer Aided Design, 33 (2001) 183-193. https://doi.org/10.1016/S0010-4485(00)00088-9.

      [16] https://en.wikipedia.org/wiki/Delaunay_triangulation

      [17] C.C. Kuo, H.T. Yau, Reconstruction of virtual parts from unorganized scanned data for automated dimensional inspection, Journal of Computing and Information Science in Engineerin, Transactions of the ASME,3, 1 (2003) 76-86. https://doi.org/10.1115/1.1565354.

      [18] C. K. Chuan, H.T. Yau, A delaunay based region growing approach to suface reconstruction from unorganized points, Computer Aided Design, 37, (2005) 825-835. https://doi.org/10.1016/j.cad.2004.09.011.

      W. Zhao, S. Gao, H. Lin, A robust hole filling algorithm for triangular mesh, The Visual Computer, 23,12 (2007) 987-997. https://doi.org/10.1007/s00371-007-0167-y

  • Downloads

  • How to Cite

    Agrawal, V. (2019). Triangular modeling using Delaunay based region growing approach. International Journal of Engineering & Technology, 7(4), 6747-6755. https://doi.org/10.14419/ijet.v7i4.20322

    Received date: 2018-09-26

    Accepted date: 2019-05-29

    Published date: 2019-07-14