Journal of the Korea Institute of Information and Communication Engineering (한국정보통신학회논문지)

The Korea Institute of Information and Commucation Engineering (한국정보통신학회)
권호 표지
DOI QR코드

DOI QR Code

Fast 3D mesh generation using projection for line laser-based 3D Scanners

라인 레이저 기반 3차원 스캐너에서 투영을 이용한 고속 3D 메쉬 생성

  • Lee, Kyungme (Department of Computer Science, Graduate School, Sangmyung University) ;
  • Yoo, Hoon (Department of Media Software, Sangmyung University)
  • Received : 2015.12.23
  • Accepted : 2016.01.27
  • Published : 2016.03.31
Download PDF
⟨ Previous Next ⟩

Abstract

This paper presents a fast 3D mesh generation method using projection for line laser-based 3D scanners. The well-known method for 3D mesh generation utilizes convex hulls for 4D vertices that is converted from the input 3D vertices. This 3D mesh generation for a large set of vertices requires a lot of time. To overcome this problem, the proposed method takes (${\theta}-y$) 2D depth map into account. The 2D depth map is a projection version of 3D data with a form of (${\theta}$, y, z) which are intermediately acquired by line laser-based 3D scanners. Thus, our 2D-based method is a very fast 3D mesh generation method. To evaluate our method, we conduct experiments with intermediate 3D vertex data from line-laser scanners. Experimental results show that the proposed method is superior to the existing method in terms of mesh generation speed.

본 논문은 라인 레이저 기반 3차원 스캐너에서 투영을 이용한 고속 메쉬 생성 방법을 제안한다. 3차원 공간에서의 메쉬를 생성하기 위한 가장 알려진 방법은 3차원의 점을 4차원으로 변환하고 4차원 컨벡스 헐(convex hull)을 구축하는 방법을 활용한다. 이런 방법은 많은 수의 점 데이터를 가지는 3D 스캔 결과에서는 메쉬를 만들 때 시간이 많이 요구된다. 제안하는 방법에서는 라인 레이저 스캐너에서 중간에 얻어지는 (${\theta}$, y, z)축의 점 정보를 투영하여 얻어진 (${\theta}-y$) 2차원 깊이 지도를 메쉬 생성에 활용한다. 제안된 방법은 2D 영역에서 수행되기 때문에 메쉬를 구성하는 시간이 상당히 단축된다. 제안하는 방법을 평가하기 위해서 라인 레이저 기반 스캐너의 중간 데이터를 이용하여 실험을 진행하였다. 실험 결과는 제안된 방법이 기존방법보다 고속 메시 생성에서 우수함을 보여준다.

Keywords

References

  1. T. Varady, R. Martin, and J Cox, "Reverse engineering of geometric models-an introduction," Computer-Aided Design. Elsevier, vol.29, no.4, pp.255-268, Apr. 1997. https://doi.org/10.1016/S0010-4485(96)00054-1
  2. K. Ho-Le, "Finite element mesh generation methods: a review and classification," Computer-aided design. Elsevier, vol.20, no.1, pp.27-38, Jan. 1988. https://doi.org/10.1016/0010-4485(88)90138-8
  3. S. Devadoss, and J. O'Rourke, Discrete and computational geometry, Princeton University Press, 2011.
  4. B. Wordenweber, "Finite element mesh generation," Computer-Aided Design. Elsevier, vol.19, no.5, pp.285-291, Sep. 1984.
  5. H. Samet, "The quadtree and related hierarchical data structures," ACM Computing Surveys (CSUR). ACM, vol.16, no.2, pp.187-260, Jan. 1984. https://doi.org/10.1145/356924.356930
  6. M. Yerry, and M. Shephard, "Automatic threedimensional mesh generation by the modified-octree technique," International Journal for Numerical Methods in Engineering, vol.20, no.11, pp.1965-1990, Nov. 1984. https://doi.org/10.1002/nme.1620201103
  7. AC de Oliveira Miranda, and L. Martha, "Hierarchical template-based quadrilateral mesh generation," Engineering with Computers. Springer, pp.1-15, Jan. 2015.
  8. J. Boissonnat, C. Wormser, and M. Yvinec, "Anisotropic Delaunay mesh generation," SIAM Journal on Computing, vol.44, no.2, pp. 467-512, Feb. 2015. https://doi.org/10.1137/140955446
  9. P. Su, and R. Drysdale, "A comparison of sequential Delaunay triangulation algorithms," Proceedings of the eleventh annual symposium on Computational geometry. ACM, pp.61-70, Sep. 1995.
  10. B. Joe, "Construction of three-dimensional Delaunay triangulations using local transformations," Computer Aided Geometric Design. Elsevier, vol.8, no.2, pp.123-142, May. 1991. https://doi.org/10.1016/0167-8396(91)90038-D
  11. M. Facello, "Implementation of a randomized algorithm for Delaunay and regular triangulations in three dimensions," Computer Aided Geometric Design. Elsevier, vol.12, no.4, pp.349-370, Jun. 1995. https://doi.org/10.1016/0167-8396(94)00018-N
  12. P. Cignoni, C. Montani, and R. Scopigno, "DeWall: A fast divide and conquer Delaunay triangulation algorithm in Ed," Computer-Aided Design. Elsevier, vol.30, no.5, pp.333-341, Apr. 1998. https://doi.org/10.1016/S0010-4485(97)00082-1
  13. B. Barber, D. Dobkin, and H. Huhdanpaa, "The quickhull algorithm for convex hulls," ACM Transactions on Mathematical Software (TOMS). ACM, vol.22, no.4, pp.469-483, Dec. 1996. https://doi.org/10.1145/235815.235821
  14. V. Rajan, "Optimality of the Delaunay triangulation in $R^d$," Discrete & Computational Geometry. Springer, vol.12, no.2, pp.189-202, Dec. 1994. https://doi.org/10.1007/BF02574375

Cited by

  1. 전처리를 활용한 고해상도 영상을 위한 효율적인 영상 스티칭 vol.21, pp.9, 2016, https://doi.org/10.6109/jkiice.2017.21.9.1738
  2. 드론 촬영 기반 사진 스캐닝 기술을 활용한 3D 모델링데이터 생성방법에 관한 연구 vol.22, pp.6, 2016, https://doi.org/10.6109/jkiice.2018.22.6.874