Three dimensional extension of Bresenham’s Algorithm with Voronoi diagram

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.

Research highlights► The efficiency of Bresenham’s Algorithm for plotting a 2D line is examined. ► An extension of the algorithm for representing a 3D line is proposed. ► The efficiency of the algorithm is based on the space symmetry. ► It is further improved by setting a simple grid point hierarchy and Voronoi diagram.