Three dimensional extension of Bresenham’s algorithm with Voronoi diagram
Au, C.K. & Woo, T. (2010). Three dimensional extension of Bresenham’s algorithm with Voronoi diagram. Computer-Aided Design, available online 3 December 2010.
Permanent Research Commons link: https://hdl.handle.net/10289/4852
Bresenham’s algorithm for plotting a two-dimensional line segment is elegant and efficient in its deployment of mid-point comparison and integer arithmetic. It is natural to investigate its three-dimensional extensions. In so doing, this paper uncovers the reason for little prior work. The concept of the mid-point in a unit interval generalizes to that of nearest neighbours involving a Voronoi diagram. Algorithmically, there are challenges. While a unit interval in two-dimension becomes a unit square in three-dimension, “squaring” the number of choices in Bresenham’s algorithm is shown to have difficulties. In this paper, the three-dimensional extension is based on the main idea of Bresenham’s algorithm of minimum distance between the line and the grid points. The structure of the Voronoi diagram is presented for grid points to which the line may be approximated. The deployment of integer arithmetic and symmetry for the three-dimensional extension of the algorithm to raise the computation efficiency are also investigated.
This is an author’s accepted version of an article published in the journal: Computer-Aided Design. © 2010 Elsevier.