IJAT Vol.14 No.5 pp. 816-823
doi: 10.20965/ijat.2020.p0816


Improved Algorithm to Trace Boundary Curves on Two-Dimensional Square Meshes

Masatomo Inui, Munekazu Kawano, Issei Watanabe, and Nobuyuki Umezu

Department of Mechanical Systems Engineering, Ibaraki University
4-12-1 Nakanarusawa, Hitachi, Ibaraki 316-8511, Japan

Corresponding author

April 28, 2020
July 2, 2020
September 5, 2020
boundary evaluation, marching squares, cutter path generation, geometric modeling

In the contoured cutter path computation of a mold part, the Minkowski sum shape of the mold part CAD model and an inverted cutter model is sliced by a horizontal plane at a specific height. The cutter path can be obtained by tracing the boundary curve of the cross-sectional figure in the two-dimensional (2D) square mesh model. In the boundary curve tracing of the square mesh, the 2D marching cubes method based on the classification of the cell pattern of the mesh is typically used. We extended the classification pattern so that the existence of very small shapes in the cell, which is ignored by the conventional 2D marching cubes method, is evaluated in tracing the boundary curve. By using this technology, a robust and accurate contoured cutter path can be obtained without any increase in the computation time.

Cite this article as:
Masatomo Inui, Munekazu Kawano, Issei Watanabe, and Nobuyuki Umezu, “Improved Algorithm to Trace Boundary Curves on Two-Dimensional Square Meshes,” Int. J. Automation Technol., Vol.14, No.5, pp. 816-823, 2020.
Data files:
  1. [1] M. Inui and N. Umezu, “Contour-type cutter path computation using ultra-high-resolution dexel model,” Computer-Aided Design and Applications, Vol.17, No.3, pp. 621-638, 2020.
  2. [2] W. Li and S. McMains, “A GPU-based voxelization approach to 3D Minkowski sum computation,” Proc. of the 14th ACM Symp. on Solid and Physical Modeling, pp. 31-40, 2010.
  3. [3] M. Inui, N. Umezu, and Y. Kitamura, “Visualizing sphere-contacting areas on automobile parts for ECE inspection,” J. of Computational Design and Engineering, Vol.2, No.1, pp. 55-66, 2015.
  4. [4] M. Inui and A. Ohta, “Using a GPU to accelerate die and mold fabrication,” IEEE Computer Graphics and Applications, Vol.27, Issue 1, pp. 82-88, 2007.
  5. [5] T. Van Hook, “Real-time shaded milling display,” Computer Graphics, Proc. of ACM SIGGRAPH ’86, Vol.20, No.4, pp. 15-20, 1986.
  6. [6] D. Dragomatz and S. Mann, “A classified bibliography of literature on NC milling path generation,” Computer-Aided Design, Vol.29, No.3, pp. 239-247, 1997.
  7. [7] I. Pitas, “Digital image processing algorithms and applications,” John Wiley & Sons, 2000.
  8. [8] M. Das, M. Paulik, and N. Loh, “A bivariate autoregressive technique for analysis and classification of planar shapes,” IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol.12, pp. 97-103, 1990.
  9. [9] E. Gose, R. Johnsonbaugh, and S. Jost, “Pattern recognition and image analysis,” Prentice Hall, 1996.
  10. [10] [Accessed April 27, 2020]
  11. [11] J. Seo et al., “Fast contour-tracing algorithm based on a pixel-following method for image sensors,” Sensors, Vol.16, pp. 353-379, 2016.
  12. [12] W. E. Lorensen and H. E. Cline, “Marching cubes: A high resolution 3D surface construction algorithm,” Computer Graphics, Proc. of ACM SIGGRAPH ’87, Vol.21, No.4, pp. 163-169, 1987.
  13. [13] S. Gong and T. S. Newman, “Dual Marching Squares: Description and analysis,” Proc. 2016 IEEE Southwest Symp. on Image Analysis and Interpretation (SSIAI), pp. 53-56, 2016.
  14. [14] [Accessed April 27, 2020]
  15. [15] [Accessed April 27, 2020]
  16. [16] [Accessed April 27, 2020]
  17. [17] CUDA samples, 2_ Graphics, marchingCubes, NVIDIA.
  18. [18] [Accessed April 27, 2020]
  19. [19] M. O. Benouamer and D. Michelucci, “Bridging the gap between CSG and Brep via a triple ray representation,” Proc. of ACM Symp. on Solid Modeling and Applications, pp. 68-79, 1997.
  20. [20] CUDA compute unified device architecture programming guide. [Accessed April 27, 2020] ≠wpage

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on Mar. 05, 2021